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

Материал из 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://poligon.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»

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

@@ Строка 9: / Строка 9: @@
 Нужно отметить, что  примеры суперпозиций не предназначены для интерпретации,
 так как они являются преобразованиями строк символов.
-{{tip|Внимание! Данная статья является частью [[Прикладной регрессионный анализ (курс лекций, B.В.Стрижов, 2008)|совместного проекта]] и будет изменена к концу декабря 2008 г. --[[Участник:Strijov|Strijov]] 23:03, 4 ноября 2008 (MSK)}}
 == Введение ==
@@ Строка 96: / Строка 94: @@
 Множество полиномов, например, может быть получено в результате решения задач&nbsp;1 или&nbsp;2.
 Требуется для каждого полинома найти все суперпозиции, полученные преобразованием:
-* сомножителей мономов,
+* сомножителей мономов
-* мономов,
+* мономов
 * полинома
 одним элементами из множества&nbsp;<tex>\mathfrak{G}</tex>.
@@ Строка 130: / Строка 128: @@
 Задача 6
-Порождение полиномов путем суперпозиции компонент мономов:
+Порождение полиномов путем суперпозиции сомножителей мономов:
 <source lang="matlab">
 S = InductOneArgPolynomials_MonomsComponents(N, SP);