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

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

Перейти к: навигация, поиск

Содержание

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

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


Внимание! Данная статья является частью совместного проекта и будет изменена к концу декабря 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\cdot 2\\ 1^2 + 1\\ 1^2 + 2\\ 1^2 + 1 + 2\\ 2^2 + 1\\ 2^2 + 2\\ 2^2 + 1 + 2\\ 1\cdot 2 + 1\\ 1\cdot 2 + 2\\ 1\cdot 2 + 1 + 2\\ 1^2 + 2^2\\ 1^2 + 2^2 + 1\\ 1^2 + 2^2 + 2\\ 1^2 + 2^2 + 1 + 2\\ 1^2 + 1\cdot 2\\ 1^2 + 1\cdot 2 + 1\\ 1^2 + 1\cdot 2 + 2\\ 1^2 + 1\cdot 2 + 1 + 2\\ 2^2 + 1\cdot 2\\ 2^2 + 1\cdot 2 + 1\\ 2^2 + 1\cdot 2 + 2\\ 2^2 + 1\cdot 2 + 1 + 2\\ 1^2 + 2^2 + 1\cdot 2\\ 1^2 + 2^2 + 1\cdot 2 + 1\\ 1^2 + 2^2 + 1\cdot 2 + 2\\ 1^2 + 2^2 + 1\cdot 2 + 1 + 2\end{array} \right\},\qquad\mathfrak{G}=\left\{\begin{array}{l}x,\\ y,\\ x+y,\\ x^2,\\ y^2,\\ x\cdot y\\ x^2 + x\\ x^2 + y\\ x^2 + x + y\\ y^2 + x\\ y^2 + y\\ y^2 + x + y\\ x\cdot y + x\\ x\cdot y + y\\ x\cdot y + x + y\\ x^2 + y^2\\ x^2 + y^2 + x\\ x^2 + y^2 + y\\ x^2 + y^2 + x + y\\ x^2 + x\cdot y\\ x^2 + x\cdot y + x\\ x^2 + x\cdot y + y\\ x^2 + x\cdot y + x + y\\ y^2 + x\cdot y\\ y^2 + x\cdot y + x\\ y^2 + x\cdot y + y\\ y^2 + x\cdot y + x + y\\ x^2 + y^2 + x\cdot y\\ x^2 + y^2 + x\cdot y + x\\ x^2 + y^2 + x\cdot y + y\\ x^2 + y^2 + x\cdot y + x + 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\}.

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

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

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

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

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

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

Некорректными суперпозициями будем считать все выражения в которых на вход функции от  k переменных подано более чем  k аргументов. Все прочие суперпозиции будем считать корректными. Например, если 1,2 - функции одной переменной, а 3 - функция двух переменных, то выражение 1(2,2) - некорректно, в то время как выражение 3(1, 3(2)) - корректно. В самом деле, выражению 3(1, 3(2)) можно поставить в соответсвие, например, функцию 3(1(x), 3(2(x),x)) аргумента  x.

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

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

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

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

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

Задача 1 

S = InductPolynomials(N, R);

Задача 2 

S = InductSumOfProducts(N, R, P);

Задача 3 

S = InductOneArg(N1, R);

Задача 4 

S = SimplifySuperpositions(Sup, T);

Задача 5 

S = InductOneTwoArg(N1, N2, R);

Задача 6

Порождение полиномов путем суперпозиции компонент мономов: 

S = InductOneArgPolynomials_MonomsComponents(N, SP);

Порождение полиномов путем суперпозиции мономов: 

S = InductOneArgPolynomials_Monoms(N, SP);

Порождение полиномов путем суперпозиции полиномов: 

S = InductOneArgPolynomials_Polynoms(N, SP);

Здесь 

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

Смотри также

Источник — «http://recognition.su/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»