Символьная регрессия

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

Перейти к: навигация, поиск

Символьная регрессия — метод построения регрессионных моделей путем перебора различных произвольных суперпозиций функций из некоторого заданного набора. Суперпозиция функций при этом называется «программой», а стохастический оптимизационный алгоритм построения таких суперпозиций называется генетическим программированием.

Генетическое программирование — модификация генетического алгоритма. Различие заключается в том, что для решения задач символьной регрессии необходима изменяющаяся длина хромосом, описывающих суперпозиции. Так как подобные алгоритмы являются переборными и требуют значительных вычислительных ресурсов, то публикации по данной теме стали появляться в 90-х годах, а значительное развитие они получили после 2000-го года. Наиболее известным исследователем является Джон Коза.

Содержание

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

Задача отыскания оптимальной структуры регрессионной модели нескольких свободных переменных следующим образом. Задана выборка — множество \{\mathbf{x}_1,\ldots,\mathbf{x}_N|\mathbf{x}\in\R^M\} значений свободных переменных и множество \{y_1,\ldots, y_N| y\in\R\} соответствующих им значений зависимой переменной. Обозначим оба эти множества как множество исходных данных D.

Также задано множество G=\{g|g:\R\times\ldots\times\R\longrightarrow\R\} гладких параметрических функций g=g(\mathbf{b},\cdot,\cdot,\ldots,\cdot) . Первый аргумент функции g — вектор-строка параметров \mathbf{b}, последующие — переменные из множества действительных чисел, рассматриваемые как элементы вектора свободных переменных. Рассмотрим произвольную суперпозицию, состоящую из не более чем r функций g. Эта суперпозиция задает параметрическую регрессионную модель f=f(\mathbf{w},\mathbf{x}) . Регрессионная модель f зависит от вектора свободных переменных \mathbf{x} и от вектора параметров \mathbf{w}. Вектор \mathbf{w}\in\R^W состоит из присоединенных векторов-параметров функций g_1,\ldots, g_r, то есть, \mathbf{w}=\mathbf{b}_1\vdots\mathbf{b}_2\vdots\ldots\vdots\mathbf{b}_r, где \vdots — знак присоединения векторов. Обозначим \Phi=\{f_i\} — множество всех суперпозиций, индуктивно порожденное элементами множества G.

Требуется выбрать такую модель f_i, которая доставляет максимум заданного функционала p(\mathbf{w}|D) . Этот функционал определяет целевую функцию S(\mathbf{w}), которая используется при вычислениях.

Процедура поиска оптимальной модели

Поиск оптимальной модели происходит на множестве порождаемых моделей на каждой итерации алгоритма. Перед работой алгоритма заданы множество измеряемых данных D и множество гладких функций G. Задан начальный набор конкурирующих моделей, F_0=\{f_1,\ldots, f_{M}|f\in\Phi\}, в котором каждая модель f_i есть суперпозиция функций \{g_{ij}\}_{j=1}^{r_i}. Если нет начального набора моделей, то он порождается случайным образом. Далее выполняется последовательность шагов, приведенных ниже.

1. Методом сопряженных градиентов (или другим способом настройки параметров) минимизируются штрафные функции S_i(\mathbf{w}) для каждой модели f_i, i=1,\ldots,M. Отыскиваются параметры \mathbf{w}^\m_i и вычисляется значение штрафной функции каждой модели.

2. Заданы следующие правила построения производных моделей f'_1,\ldots, f'_{M}. Для каждой модели f_i строится производная модель f'_i. В f_i произвольно выбирается функция g_{ij}. Выбирается произвольная модель f_\xi из F_0\backslash\{f_i\} и ее произвольная функция g_{\xi\zeta}. Модель f' порождается из модели f путем замещения функции g_{ij} с ее аргументами на функцию g_{\xi\zeta} с ее аргументами.

3. С заданной вероятностью \eta каждая модель f'_i подвергается изменениям. В изменяемой модели выбирается j-тая функция, причем закон распределения вероятности выбора функции p(j) задан. Из множества G случайным образом выбирается функция g' и замещает функцию g_j. Гиперпараметр \alpha_{ij} этой функции определяется как \max\limits_j(\alpha_{ij}). Вектор параметров этой функции \mathbf{b}_{ij} равен нулю или назначается при задании G.

4. При выборе моделей из объединенного множества родительских и порожденных моделей в соответствии с критерием S(\mathbf{w}) выбираются M наилучших, которые используются в дальнейших итерациях.

Алгоритм остановливается при достижении ошибки, не превосходящей заданную, или через заданное количество раз.

Пример построения модели

Ниже описывается пример построения символьной регрессионной модели. На рис.1. сплошной кривой показаны исходные данные, пунктиром показаны значения регрессионной модели. По оси абсцисс отложено значение свободной переменной, по оси ординат — значение зависимой переменной. Выборка, представленная данной кривой, содержит четыре тысячи отсчетов. Экспертами было задано множество базовых функций G из элементов которого порождаются регрессионные модели. Список функций приведен в таблице. Множество F_0 моделей начального приближения также было задано экспертами.

Изображение:Symbolic_Regression_Table1.png

Выбор моделей производился из более тысячи порожденных моделей. В таблице 2 приведены три модели, полученные в результате работы алгоритма. Качество моделей оценивалось по ошибкам  \rho_1,\rho_2 и числу параметров в векторе параметров \mathbf{w}. Ошибка \rho_1 — среднеквадратичная относительная ошибка

\rho_1=\sqrt{\frac{1}{N}\sum_{i=1}^n\left(\frac{y_i-f(\x_i)}{\max(y_i)}\right)^2},

ошибка  \rho_2 — максимальная относительная ошибка

\rho_2=\max_{i=1,\ldots,N}\frac{|y_i-f(\x_i)|}{\max(y_i)}.

Изображение:Symbolic_Regression_Table2.png

В строке «Описание» таблицы 2 показана структура модели в виде дерева. В качестве примера рассмотрим модель 2. Эта модель состоит из суперпозиции восьми функций f_2=g_1(g_2(g_3(g_4(g_5(x), g_6(x)), g_7(x)), x), g_8(x)). Функции g_1=\times(\emptyset,\cdot,\cdot) и g_2,\ldots, g_4=+(\emptyset,\cdot,\cdot), сложения и умножения, имеют первым аргументом пустой вектор параметров; g_5,\ldots, g_7=h(\mathbf{b}_i,\cdot), i=1,\ldots,3, и g_8=l(\mathbf{b}_4,\cdot). Функции h=\frac{\lambda_i}{\sqrt{2\pi}\sigma_i}\mbox{exp}\left({-\frac{(x-\xi_i)^2}{2\sigma_i^2}}\right) имеют векторы параметров \mathbf{b}_i=\langle\lambda_i,\mu_i,\sigma_i, a_i\rangle, и функция l=(ax+b) имеет вектор параметров \mathbf{b}_4=\langle{a, b}\rangle.

Модель f_2 можно переписать в виде f(\mathbf{w},\x)=l(\mathbf{b}_4,x)^{-1}\times\left(x+\sum_{i=1}³h(\mathbf{b}_i, x)\right), где \x=x и \mathbf{w}=\mathbf{b}_1\vdots\mathbf{b}_2\vdots\mathbf{b}_3\vdots\mathbf{b}_4. Развернутый вид модели:

y=(ax+b)^{-1}\left(x+\sum_{i=1}^3\frac{\lambda_i}{\sqrt{2\pi}\sigma_i}\mbox{exp}\left({-\frac{(x-\xi_i)^2}{2\sigma_i^2}}\right)+a_i\right).

Литература

  • Zelinka, I., Nolle, L., Oplatkova, Z. Analytic Programming — Symbiloc Regression by Means of Arbitrfary Evolutionary Algorithms / Journal of Simulation. Vol. 6 No 9. P. 44—56.
  • Koza, J. R. Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Springer. 2005.
  • Riolo, R., Soule, T., Worzel, B. (Eds.) Genetic Programming Theory and Practice V. Series: Genetic and Evolutionary Computation. Springer. 2008.
  • Madar, J., Janos, A., Szeifert, F. Genetic Programming for the Identification of Nonlinear Input-Output Models. citeseer.ist.psu.edu. 2005.
  • Hazan, A. et al. Modelling Expressive Performance: A Regression Tree Approach Based on Strongly Typed Genetic Programming / Applications of Evolutionary Computing. Springer. Vol. 3907/2006. P. 676—687.
  • Kohavi, R. A study of cross-validation and bootstrap for accuracy estimation and model selection / Proceedings of 14 International Joint Conference of Artificial Intelligence. 2(12). P. 1137—1143.
  • Стрижов В.В. Поиск параметрической регрессионной модели в индуктивно заданном множестве. Журнал вычислительных технологий. 2007. No 1. С. 93-102. [1]
  • Стрижов В.В., Крымова Е.А. Методы выбора регрессионных моделей. М.: ВЦ РАН, 2010. 60 с. Брошюра, PDF.

Внешние ссылки

Личные инструменты