Порождение нелинейных регрессионных моделей (пример)

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 8: Строка 8:
Предполагается, что функции <tex>g^{_{(2)}}_i(w_i,x, y)</tex> корректно работают в случае вызова в виде <tex>g^{_{(2)}}_i(w_i,x)</tex>.
Предполагается, что функции <tex>g^{_{(2)}}_i(w_i,x, y)</tex> корректно работают в случае вызова в виде <tex>g^{_{(2)}}_i(w_i,x)</tex>.
-
== Интерпретация на языке графов ==
+
== Интерпретация на языке деревьев ==
Заметим вначале, что суперпозиция функций <tex>G_i</tex> может быть задана двоичным деревом <tex>T(V,X)</tex>, вершины которого <tex>V_i</tex>∈<tex>G_i</tex>, корень – самая внешняя функция суперпозиции. Под глубиной вершины будем понимать расстояние от неё до корня. Если у вершины один потомок, то соответствующая функция запишется как <tex>g_i(g_j)</tex>, если два – то <tex>g_i(g_j,g_k)</tex>, если ноль – то <tex>g_i(x)</tex> или <tex>g_i(x,x)</tex>.
Заметим вначале, что суперпозиция функций <tex>G_i</tex> может быть задана двоичным деревом <tex>T(V,X)</tex>, вершины которого <tex>V_i</tex>∈<tex>G_i</tex>, корень – самая внешняя функция суперпозиции. Под глубиной вершины будем понимать расстояние от неё до корня. Если у вершины один потомок, то соответствующая функция запишется как <tex>g_i(g_j)</tex>, если два – то <tex>g_i(g_j,g_k)</tex>, если ноль – то <tex>g_i(x)</tex> или <tex>g_i(x,x)</tex>.
Строка 15: Строка 15:
Так, дереву '''А''' соответствует суперпозиция <tex>2(1(1),2(1,1))</tex>, а дереву '''Б''' – суперпозиция <tex>1(2(1,1))</tex>.<br /> <br />
Так, дереву '''А''' соответствует суперпозиция <tex>2(1(1),2(1,1))</tex>, а дереву '''Б''' – суперпозиция <tex>1(2(1,1))</tex>.<br /> <br />
Возможна и другая постановка алгоритма. Она особенно ценна, если нельзя вызвать <tex>g^{_{(2)}}_i(x,x)</tex> в виде <tex>g^{_{(2)}}_i(x)</tex>. Изменение состоит в том, что листья дерева суперпозиции считаются не функциями, а свободными переменными. В этом случае дереву '''А''' будет соответствовать суперпозиция <tex>2(1(x), 2(x,x))</tex> дереву '''Б''' – суперпозиция <tex>1(2(x,x))</tex>.
Возможна и другая постановка алгоритма. Она особенно ценна, если нельзя вызвать <tex>g^{_{(2)}}_i(x,x)</tex> в виде <tex>g^{_{(2)}}_i(x)</tex>. Изменение состоит в том, что листья дерева суперпозиции считаются не функциями, а свободными переменными. В этом случае дереву '''А''' будет соответствовать суперпозиция <tex>2(1(x), 2(x,x))</tex> дереву '''Б''' – суперпозиция <tex>1(2(x,x))</tex>.
 +
 +
== Порождение множества деревьев суперпозиций ==
 +
Комбинаторная простота этого шага алгоритма заключается в том, что изоморфные деревья задают разные суперпозиции. Однако простые смещения вершин не дают новых деревьев.
 +
 +
[[Изображение:Clip_image002.gif|400px]]
 +
 +
Так, деревья '''А''' и '''В''' различны с точки зрения задаваемых суперпозиций, но деревья '''А''' и '''Б''' идентичны. Поэтому при машинной реализации можно вообще исключить деревья типа '''Б''', т.е. если из вершины исходит одно ребро, будем «рисовать» его «сверху вниз, справа налево», как в деревьях '''А''' и '''В'''.<br />
 +
Порождение деревьев осуществим по уровням глубины. Т.е. для задачи порождения деревьев высоты не больше <tex>n</tex> породим все деревья высоты не больше <tex>n-1</tex> и запишем их в список <tex>1</tex>. В список <tex>2</tex> поместим все деревья высоты ровно <tex>n-1</tex>. Далее возьмём дерево из списка <tex>2</tex>, построим всевозможные деревья высоты <tex>n</tex> из него, получаемые добавлением рёбер к вершинам нижнего уровня глубины, и поместим их в конец списка <tex>1</tex>. То же проделаем со всеми остальными деревьями списка <tex>2</tex>.

Версия 16:35, 20 апреля 2010

Порождение нелинейных регрессионных моделей - порождение функций, зависящих от параметров и от одной или нескольких свободных переменных. Зависимость от параметров предполагается нелинейной.


Содержание

Постановка задачи

Задана выборка из m пар (\mathbf{x}_i,y_i). Задан набор порождающих функций одного и двух аргументов [G_i]_{i=1}^{n} = [[g_l^{_{(1)}}(w_l,x)]_{l=1}^k,[g_m^{_{(2)}}(w_m,x,y)_{m=k+1}^n]], которые зависят от параметров \mathbf{w_i}=(w_1,...,w_{W_i}) и свободных переменных x,y. Функции гладкие параметрические. Требуется создать алгоритм, порождающий лексикографически упорядоченные суперпозиции возрастающей сложности. Каждая суперпозиция является регрессионной моделью одной независимой переменной. Сравнить качество моделей и регрессионные остатки на порожденном множестве.

Дополнительные предположения

Предполагается, что функции g^{_{(2)}}_i(w_i,x, y) корректно работают в случае вызова в виде g^{_{(2)}}_i(w_i,x).

Интерпретация на языке деревьев

Заметим вначале, что суперпозиция функций G_i может быть задана двоичным деревом T(V,X), вершины которого V_iG_i, корень – самая внешняя функция суперпозиции. Под глубиной вершины будем понимать расстояние от неё до корня. Если у вершины один потомок, то соответствующая функция запишется как g_i(g_j), если два – то g_i(g_j,g_k), если ноль – то g_i(x) или g_i(x,x).

Так, дереву А соответствует суперпозиция 2(1(1),2(1,1)), а дереву Б – суперпозиция 1(2(1,1)).

Возможна и другая постановка алгоритма. Она особенно ценна, если нельзя вызвать g^{_{(2)}}_i(x,x) в виде g^{_{(2)}}_i(x). Изменение состоит в том, что листья дерева суперпозиции считаются не функциями, а свободными переменными. В этом случае дереву А будет соответствовать суперпозиция 2(1(x), 2(x,x)) дереву Б – суперпозиция 1(2(x,x)).

Порождение множества деревьев суперпозиций

Комбинаторная простота этого шага алгоритма заключается в том, что изоморфные деревья задают разные суперпозиции. Однако простые смещения вершин не дают новых деревьев.

Так, деревья А и В различны с точки зрения задаваемых суперпозиций, но деревья А и Б идентичны. Поэтому при машинной реализации можно вообще исключить деревья типа Б, т.е. если из вершины исходит одно ребро, будем «рисовать» его «сверху вниз, справа налево», как в деревьях А и В.
Порождение деревьев осуществим по уровням глубины. Т.е. для задачи порождения деревьев высоты не больше n породим все деревья высоты не больше n-1 и запишем их в список 1. В список 2 поместим все деревья высоты ровно n-1. Далее возьмём дерево из списка 2, построим всевозможные деревья высоты n из него, получаемые добавлением рёбер к вершинам нижнего уровня глубины, и поместим их в конец списка 1. То же проделаем со всеми остальными деревьями списка 2.