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

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

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

Текущая версия

Содержание

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

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

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

Введение

Пусть заданы множество $\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»

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

@@ Строка 9: / Строка 9: @@
 Нужно отметить, что  примеры суперпозиций не предназначены для интерпретации,
 так как они являются преобразованиями строк символов.
-{{tip|Внимание! Данная статья является частью [[Прикладной регрессионный анализ (курс лекций, B.В.Стрижов, 2008)|совместного проекта]] и будет изменена к концу декабря 2008 г. --[[Участник:Strijov|Strijov]] 23:03, 4 ноября 2008 (MSK)}}
 == Введение ==
@@ Строка 38: / Строка 36: @@
 где&nbsp;<tex>i_\cdot</tex>&nbsp;- число-индекс переменной, <tex>i\in\{1,\ldots,N\}</tex> и <tex>r_\cdot</tex>&nbsp;- число, степень переменной, <tex>r\in\{1,\ldots,R\}</tex>.
-Задано ограничение: каждый полином не должен содержать тождественных мономов, т.е.
+Заданы следующие ограничения:
-<center><tex>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}.</tex></center>
+* каждый полином не должен содержать тождественных мономов, т.е. <tex>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}.</tex>
+* Среди построенных полиномов не должно быть совпадающих.
-Например, задано множество&nbsp;<tex>\mathfrak{N}=\{1,2\}</tex> (и множество свободных переменных <tex>\mathfrak{G}={x,y}</tex>).
+Например, задано множество&nbsp;<tex>\mathfrak{N}=\{1,2\}</tex> (и множество свободных переменных <tex>\mathfrak{G}=\{x,y\}</tex>).
-Множество всех полиномов степени не более&nbsp;<tex>R=2</tex> имеет вид
+Множество всех полиномов степени не более&nbsp;<tex>R=2</tex> имеет вид:
-<center><tex> \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\}. </tex></center>
+<center><tex>\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\}.</tex></center>
 == Задача 2, множество сумм произведений переменных заданной степени ==
@@ Строка 49: / Строка 48: @@
 Задано множество&nbsp;<tex>\mathfrak{P}</tex> степеней переменных.
 Требуется построить все возможные суммы произведений переменных, имеющих степени из&nbsp;&nbsp;<tex>\mathfrak{P}</tex>.
-Ограничение на отсутствие тождественных произведений переменных сохраняется.
+Ограничения предыдущей задач сохряняются.
 Легко заметить, что эта задача&nbsp;- вариант предыдущей.
@@ Строка 60: / Строка 59: @@
 Например, дано
 <center><tex>\mathfrak{N} = \{1,2\}, \mathfrak{G} = \{g_1,g_2\}.</tex></center>
-%
 Найти отображение
 <center><tex>\mathfrak{A}:\mathfrak{N} \to \mathfrak{S}</tex></center>
-множества индексов переменных&nbsp;<tex>\mathfrak{N}</tex> в множество наборов&nbsp;<tex>\mathfrak{S}</tex>, соответствующих суперпозициям с числом элементов, не превосходящим <tex>R=2</tex>.\\
+множества индексов переменных&nbsp;<tex>\mathfrak{N}</tex> в множество наборов&nbsp;<tex>\mathfrak{S}</tex>, соответствующих суперпозициям с числом элементов, не превосходящим <tex>R=2</tex>.
-%
 Результат&nbsp;- <center><tex>\mathfrak{S} = \left\{ 1, 2, 1(1), 2(2), 1(2), 2(1) \right\},</tex></center>
 соответствующее множество суперпозиций&nbsp;-
 <center><tex>\left\{ g_1, g_2, g_1(g_1), g_2(g_2), g_1(g_2), g_2(g_1) \right\}.</tex></center>
+== Задача 4, упрощение элементов суперпозиции функций одного аргумента ==
-== Задача 3a, упрощение элементов суперпозиции функций одного аргумента ==
+Требуется упростить суперпозиции из входного множества &nbsp;<tex>\mathfrak{S}</tex> суперпозиций функций одного аргумента из множества&nbsp;<tex>\mathfrak{G}</tex> в соответствии с множеством подстановок <tex>\mathfrak{T}</tex>.
-Требуется упростить суперпозиции из множества, полученного в предыдущей задаче.
+Для этого подстановки из <tex>\mathfrak{T}</tex> определены на множестве функций из&nbsp;<tex>\mathfrak{G}</tex> и заданы в виде
-Для этого операция суперпозиции частично определена на множестве функций из&nbsp;<tex>\mathfrak{G}</tex> и задана в виде
 списка&nbsp;<tex>\{g_i(g_j)\mapsto g_k\}</tex>.
 Например, суперпозицию элементов&nbsp;<tex>g_1(g_2)</tex> можно заменить на&nbsp;некоторый другой элемент&nbsp;<tex>g_3</tex>,
-если определена операция суперпозиции <tex>g_1(g_2)\mapsto g_3</tex>.
+если в <tex>\mathfrak{T}</tex> определена подстановка <tex>g_1(g_2)\mapsto g_3</tex>.
-Так как удобнее работать с индексами функций, то&nbsp;операция суперпозиций задается на&nbsp;числах из&nbsp;<tex>\mathfrak{N}</tex>
+Так как удобнее работать с индексами функций, то множество подстановок из&nbsp;<tex>\mathfrak{T}</tex> определено на&nbsp;числах из&nbsp;<tex>\mathfrak{N}</tex>
-и&nbsp;представляется в&nbsp;виде множества подстановок&nbsp;<tex>\{i_1(i_2)\mapsto i_3\}</tex>.
+и&nbsp; состоит из подстановок вида&nbsp;<tex>\{i_1(i_2)\mapsto i_3\}</tex>.
-== Задача 4, множество суперпозиций функций одного и двух аргументов ==
+== Задача 5, множество суперпозиций функций одного и двух аргументов ==
 Задано множество функций одного и двух аргументов.
 Требуется построить все суперпозиции этих функций, число функций в каждой суперпозиции не превышает заданное&nbsp;<tex>R</tex>.
 Эта задача является вариантом задачи&nbsp;3 и использует элементы задачи&nbsp;1.
-Задано ограничение: все функции двух аргументов считаются коммутативными.
+Некорректными суперпозициями будем считать все выражения в которых на вход функции от &nbsp;<tex>k</tex> переменных подано более чем &nbsp;<tex>k</tex> аргументов.
+Все прочие суперпозиции будем считать корректными.
+Например, если <tex>1,2</tex> - функции одной переменной, а <tex>3</tex> - функция двух переменных, то выражение
+<tex>1(2,2)</tex> - некорректно, в то время как выражение <tex>3(1, 3(2))</tex> - корректно. В самом деле, выражению <tex>3(1, 3(2))</tex>
+можно поставить в соответсвие, например, функцию <tex>3(1(x), 3(2(x),x))</tex> аргумента &nbsp;<tex>x</tex>.
-Например, <tex>3(1,2) = 3(2,1)</tex>, но <tex>3(1,2(1)) \neq 3(2,1(1))</tex>.
+== Задача 6, множество преобразований элементов полиномов ==
-== Задача 5, множество преобразований элементов полиномов ==
 Задано множество&nbsp;<tex>\mathfrak{G}</tex> из&nbsp;<tex>N</tex> функций одного аргумента и множество полиномов.
 Множество полиномов, например, может быть получено в результате решения задач&nbsp;1 или&nbsp;2.
-Требуется для каждого полинома найти все суперпозиции, полученные преобразованием
+Требуется для каждого полинома найти все суперпозиции, полученные преобразованием:
-* сомножителей мономов,
+* сомножителей мономов
-* мономов,
+* мономов
 * полинома
-одним элементом из множества&nbsp;<tex>\mathfrak{G}</tex>.
+одним элементами из множества&nbsp;<tex>\mathfrak{G}</tex>.
 == Программная реализация ==
@@ Строка 113: / Строка 113: @@
 Задача 3
 <source lang="matlab">
-S = InductOneArg(N1, R, [T]);
+S = InductOneArg(N1, R);
 </source>
 Задача 4
 <source lang="matlab">
-S = InductOneTwoArg(N1, N2, R, [T]);
+S = SimplifySuperpositions(Sup, T);
 </source>
 Задача 5
 <source lang="matlab">
-S = InductOneArgPolynomials(N, SP);
+S = InductOneTwoArg(N1, N2, R);
+</source>
+Задача 6
+Порождение полиномов путем суперпозиции сомножителей мономов:
+<source lang="matlab">
+S = InductOneArgPolynomials_MonomsComponents(N, SP);
+</source>
+Порождение полиномов путем суперпозиции мономов:
+<source lang="matlab">
+S = InductOneArgPolynomials_Monoms(N, SP);
+</source>
+Порождение полиномов путем суперпозиции полиномов:
+<source lang="matlab">
+S = InductOneArgPolynomials_Polynoms(N, SP);
 </source>
@@ Строка 133: / Строка 148: @@
 R - максимальная степень полинома, число элементов в суперпозиции;
 P - множество степеней переменных;
-T - множество подстановок суперпозиций, множество троек (i1, i2, i3), [опционально];
+T - множество подстановок суперпозиций, множество троек (i1, i2, i3);
+Sup - множество суперпозиций;
 SP - множество полиномов S.
 </source>