Порождение нелинейных регрессионных моделей (пример)
Материал из 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
Порождение нелинейных регрессионных моделей - порождение функций, зависящих от параметров и от одной или нескольких свободных переменных. Зависимость от параметров предполагается нелинейной.
Содержание |
Постановка задачи
Задана выборка из пар
. Задан набор порождающих функций одного и двух аргументов
, которые зависят от параметров
и свободных переменных
. Функции гладкие параметрические. Требуется создать алгоритм, порождающий лексикографически упорядоченные суперпозиции возрастающей сложности. Каждая суперпозиция является регрессионной моделью одной независимой переменной. Сравнить качество моделей и регрессионные остатки на порожденном множестве.
Дополнительные предположения
Предполагается, что функции корректно работают в случае вызова в виде
.
Интерпретация на языке деревьев
Заметим вначале, что суперпозиция функций может быть задана двоичным деревом
, вершины которого
∈
, корень – самая внешняя функция суперпозиции. Под глубиной вершины будем понимать расстояние от неё до корня. Если у вершины один потомок, то соответствующая функция запишется как
, если два – то
, если ноль – то
или
.
Так, дереву А соответствует суперпозиция , а дереву Б – суперпозиция
.
Возможна и другая постановка алгоритма. Она особенно ценна, если нельзя вызвать в виде
. Изменение состоит в том, что листья дерева суперпозиции считаются не функциями, а свободными переменными. В этом случае дереву А будет соответствовать суперпозиция
дереву Б – суперпозиция
.
Порождение множества деревьев суперпозиций
Комбинаторная простота этого шага алгоритма заключается в том, что изоморфные деревья задают разные суперпозиции. Однако простые смещения вершин не дают новых деревьев.
Так, деревья А и В различны с точки зрения задаваемых суперпозиций, но деревья А и Б идентичны. Поэтому при машинной реализации можно вообще исключить деревья типа Б, т.е. если из вершины исходит одно ребро, будем «рисовать» его «сверху вниз, справа налево», как в деревьях А и В.
Порождение деревьев осуществим по уровням глубины. Т.е. для задачи порождения деревьев высоты не больше породим все деревья высоты не больше
и запишем их в список
. В список
поместим все деревья высоты ровно
. Далее возьмём дерево из списка
, построим всевозможные деревья высоты
из него, получаемые добавлением рёбер к вершинам нижнего уровня глубины, и поместим их в конец списка
. То же проделаем со всеми остальными деревьями списка
.
