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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (викификация)
 
(17 промежуточных версий не показаны.)
Строка 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>.
где&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, множество сумм произведений переменных заданной степени ==
== Задача 2, множество сумм произведений переменных заданной степени ==
Строка 49: Строка 48:
Задано множество&nbsp;<tex>\mathfrak{P}</tex> степеней переменных.
Задано множество&nbsp;<tex>\mathfrak{P}</tex> степеней переменных.
Требуется построить все возможные суммы произведений переменных, имеющих степени из&nbsp;&nbsp;<tex>\mathfrak{P}</tex>.
Требуется построить все возможные суммы произведений переменных, имеющих степени из&nbsp;&nbsp;<tex>\mathfrak{P}</tex>.
-
Ограничение на отсутствие тождественных произведений переменных сохраняется.
+
Ограничения предыдущей задач сохряняются.
Легко заметить, что эта задача&nbsp;- вариант предыдущей.
Легко заметить, что эта задача&nbsp;- вариант предыдущей.
Строка 60: Строка 59:
Например, дано
Например, дано
<center><tex>\mathfrak{N} = \{1,2\}, \mathfrak{G} = \{g_1,g_2\}.</tex></center>
<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>
<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>\mathfrak{S} = \left\{ 1, 2, 1(1), 2(2), 1(2), 2(1) \right\},</tex></center>
соответствующее множество суперпозиций&nbsp;-
соответствующее множество суперпозиций&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>
<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_i(g_j)\mapsto g_k\}</tex>.
Например, суперпозицию элементов&nbsp;<tex>g_1(g_2)</tex> можно заменить на&nbsp;некоторый другой элемент&nbsp;<tex>g_3</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;<tex>R</tex>.
Эта задача является вариантом задачи&nbsp;3 и использует элементы задачи&nbsp;1.
Эта задача является вариантом задачи&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;<tex>\mathfrak{G}</tex> из&nbsp;<tex>N</tex> функций одного аргумента и множество полиномов.
Множество полиномов, например, может быть получено в результате решения задач&nbsp;1 или&nbsp;2.
Множество полиномов, например, может быть получено в результате решения задач&nbsp;1 или&nbsp;2.
-
Требуется для каждого полинома найти все суперпозиции, полученные преобразованием
+
Требуется для каждого полинома найти все суперпозиции, полученные преобразованием:
-
* сомножителей мономов,
+
* сомножителей мономов
-
* мономов,
+
* мономов
* полинома
* полинома
-
одним элементом из множества&nbsp;<tex>\mathfrak{G}</tex>.
+
одним элементами из множества&nbsp;<tex>\mathfrak{G}</tex>.
== Программная реализация ==
== Программная реализация ==
Строка 113: Строка 113:
Задача 3
Задача 3
<source lang="matlab">
<source lang="matlab">
-
S = InductOneArg(N1, R, [T]);
+
S = InductOneArg(N1, R);
</source>
</source>
Задача 4
Задача 4
<source lang="matlab">
<source lang="matlab">
-
S = InductOneTwoArg(N1, N2, R, [T]);
+
S = SimplifySuperpositions(Sup, T);
</source>
</source>
Задача 5
Задача 5
<source lang="matlab">
<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>
</source>
Строка 133: Строка 148:
R - максимальная степень полинома, число элементов в суперпозиции;
R - максимальная степень полинома, число элементов в суперпозиции;
P - множество степеней переменных;
P - множество степеней переменных;
-
T - множество подстановок суперпозиций, множество троек (i1, i2, i3), [опционально];
+
T - множество подстановок суперпозиций, множество троек (i1, i2, i3);
 +
Sup - множество суперпозиций;
SP - множество полиномов S.
SP - множество полиномов S.
</source>
</source>

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

Содержание

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

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

Введение

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

Смотри также