Конструктивное построение множества суперпозиций

Материал из MachineLearning.

(Различия между версиями)

Strijov (Обсуждение | вклад)
(Новая: {{TOCright}} Методы индуктивного построения регрессионных моделей, например, [[мет...)
К следующему изменению →

Версия 20:03, 4 ноября 2008

Содержание

1 Введение
2 Цель
3 Задача 1, множество полиномов от свободных переменных
4 Задача 2, множество сумм произведений переменных заданной степени
5 Задача 3, множество суперпозиций функций одного аргумента
6 Задача 3a, упрощение элементов суперпозиции функций одного аргумента
7 Задача 4, множество суперпозиций функций одного и двух аргументов
8 Задача 5, множество преобразований элементов полиномов
9 Программная реализация
10 Смотри также

Методы индуктивного построения регрессионных моделей, например, метод группового учета аргументов или символьная регрессия, используют в качестве моделей-претендентов различные суперпозиции свободных переменных. В частности, МГУА использует линейные комбинации произведений свободных переменных, а символьная регрессия - их произвольные суперпозиции.

Ниже приведены несколько задач, иллюстрирующих способы построения суперпозиций. Нужно отметить, что примеры суперпозиций не предназначены для интерпретации, так как они являются преобразованиями строк символов.

Внимание! Данная статья является частью совместного проекта и будет изменена к концу декабря 2008 г. --Strijov 23:03, 4 ноября 2008 (MSK)

Введение

Пусть заданы множество $\mathfrak{N}$ первых $N$ натуральных чисел. Также задан набор $\mathfrak{S}$ множеств чисел из $\mathfrak{N}$ , разделенных скобками, знаками сложения, умножения и возведения в степень.

Например, $\mathfrak{S}=\{s_1,s_2,s_3\}$ , где $s_1 = 1$ , $s_2=1^2+2\cdot3$ , $s_3=2+3^2$ .

Задано множество $\mathfrak{G}=\{g_1,\ldots,g_N\}$ , элементы которого $g$ - функции или переменные, принимающие значения на числовой прямой, а их индексы - элементы множества $\mathfrak{N}$ . Алгоритм построения суперпозиций - это отображение множества $\mathfrak{N}$ на множество $\mathfrak{S}$ . Для каждой суперпозиции $s$ алгоритм определяет порядок следования индексов функций из $\mathfrak{G}$ .

Например, используя множество $\mathfrak{S}$ определенное в примере выше, и множество $\mathfrak{G}=\{\sin, \log, \ch\}$ получаем множество суперпозиций $\mathfrak{F}=\{f_1,f_2, f_3\}$ , где $f_1=\sin$ , $f_2=\sin^2+\cos\cdot\ch$ , $f_3=\cos+\ch^2$ .

Цель

Требуется создать несколько алгоритмов, которые конструктивно строят суперпозиции по заданным правилам.

Задача 1, множество полиномов от свободных переменных

Задано множество $\mathfrak{G}$ из $N$ переменных, принадлежащих действительной прямой. Требуется построить все полиномы степени не больше $R$ . Результат работы алгоритма - множество $\mathfrak{S}$ строк вида $s=i_a^{r_1}\cdot \ldots \cdot i_b^{r_2}+\ldots+i_c^{r_3}\cdot \ldots \cdot i_d^{r_4}$ , где $i_\cdot$ - число-индекс переменной, $i\in\{1,\ldots,N\}$ и $r_\cdot$ - число, степень переменной, $r\in\{1,\ldots,R\}$ .

Задано ограничение: каждый полином не должен содержать тождественных мономов, т.е.

$i_a^{r_1}i_b^{r_2}+i_b^{r_2}i_a^{r_1} \mapsto i_a^{r_1}i_b^{r_2}.$

Например, задано множество $\mathfrak{N}=\{1,2\}$ (и множество свободных переменных $\mathfrak{G}={x,y}$ ). Множество всех полиномов степени не более $R=2$ имеет вид

$\mathfrak{S}=\left\{ \begin{array}{l} 1 ,\\ 2 ,\\ 1 +2 ,\\ 1^2 ,\\ 2^2 ,\\ 1 +2^2 ,\\ 1^2+2 ,\\ 1^2+2^2 ,\\ 1\cdot 2 \\ \end{array} \right\}, \mathfrak{G}=\left\{ \begin{array}{l} x ,\\ y ,\\ x + y,\\ x^2 ,\\ y^2,\\ x +y^2,\\ x^2+y ,\\ x^2+y^2,\\ x\cdot y \\ \end{array} \right\}.$

Задача 2, множество сумм произведений переменных заданной степени

Задано множество из $N$ переменных, принадлежащих положительным действительным числам. Задано множество $\mathfrak{P}$ степеней переменных. Требуется построить все возможные суммы произведений переменных, имеющих степени из $\mathfrak{P}$ . Ограничение на отсутствие тождественных произведений переменных сохраняется. Легко заметить, что эта задача - вариант предыдущей.

Например, $\mathfrak{P} = \{0, 1, \frac{3}{2}\}$ .

Задача 3, множество суперпозиций функций одного аргумента

Найти все суперпозиции функций одного аргумента из конечного множества. При этом число функций в суперпозиции не должно превышать заданное $R$ .

Например, дано

$\mathfrak{N} = \{1,2\}, \mathfrak{G} = \{g_1,g_2\}.$

% Найти отображение

$\mathfrak{A}:\mathfrak{N} \to \mathfrak{S}$

множества индексов переменных $\mathfrak{N}$ в множество наборов $\mathfrak{S}$ , соответствующих суперпозициям с числом элементов, не превосходящим $R=2$ .\\ %

Результат - $\mathfrak{S} = \left\{ 1, 2, 1(1), 2(2), 1(2), 2(1) \right\},$

соответствующее множество суперпозиций -

$\left\{ g_1, g_2, g_1(g_1), g_2(g_2), g_1(g_2), g_2(g_1) \right\}.$

Задача 3a, упрощение элементов суперпозиции функций одного аргумента

Требуется упростить суперпозиции из множества, полученного в предыдущей задаче. Для этого операция суперпозиции частично определена на множестве функций из $\mathfrak{G}$ и задана в виде списка $\{g_i(g_j)\mapsto g_k\}$ .

Например, суперпозицию элементов $g_1(g_2)$ можно заменить на некоторый другой элемент $g_3$ , если определена операция суперпозиции $g_1(g_2)\mapsto g_3$ .

Так как удобнее работать с индексами функций, то операция суперпозиций задается на числах из $\mathfrak{N}$ и представляется в виде множества подстановок $\{i_1(i_2)\mapsto i_3\}$ .

Задача 4, множество суперпозиций функций одного и двух аргументов

Задано множество функций одного и двух аргументов. Требуется построить все суперпозиции этих функций, число функций в каждой суперпозиции не превышает заданное $R$ . Эта задача является вариантом задачи 3 и использует элементы задачи 1.

Задано ограничение: все функции двух аргументов считаются коммутативными.

Например, $3(1,2) = 3(2,1)$ , но $3(1,2(1)) \neq 3(2,1(1))$ .

Задача 5, множество преобразований элементов полиномов

Задано множество $\mathfrak{G}$ из $N$ функций одного аргумента и множество полиномов. Множество полиномов, например, может быть получено в результате решения задач 1 или 2. Требуется для каждого полинома найти все суперпозиции, полученные преобразованием

сомножителей мономов,
мономов,
полинома

одним элементом из множества $\mathfrak{G}$ .

Программная реализация

Задача 1

S = InductPolynomials(N, R);

Задача 2

S = InductSumOfProducts(N, R, P);

Задача 3

S = InductOneArg(N1, R, [T]);

Задача 4

S = InductOneTwoArg(N1, N2, R, [T]);

Задача 5

S = InductOneArgPolynomials(N, SP);

Здесь

S - массив строк символов: "Число, (, ), +, *, ^";
N - число переменных или функций;
N1, N2 - число функций от одного или двух аргументов;
R - максимальная степень полинома, число элементов в суперпозиции;
P - множество степеней переменных;
T - множество подстановок суперпозиций, множество троек (i1, i2, i3), [опционально];
SP - множество полиномов S.

Смотри также

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BE%D0%BD%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D0%B5_%D0%BF%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D1%81%D1%83%D0%BF%D0%B5%D1%80%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D0%B9»

Категории: Регрессионный анализ | Открытые проблемы и полемика | Учебные материалы