Символьная регрессия и структурное расстояние между моделями (пример)

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

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

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

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

Содержание

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

Задана выборка — множество \{\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, которая доставляет максимум заданного функционала {\Sigma}_{k=1}^n({f_i({x_k}})-{y_k})^2 , а также исследовать вектор попарных расстояний между моделями популяции.

Сведения о структурных расстояниях ( метриках ) на множестве помеченных графов

Помеченный граф - это граф, вершинам и ребрам которого приписываются определенные метки. Пусть G_i(V_i,X_i) - конечный, связный, помеченный, неориентированный граф без петель и кратных ребер, имеющий множество вершин V_i = \{u, v,...\}, |V_i| = p_i > 0 и множество ребер X_i = \{x, y,...\}, |X_i| = q_i > 0

Рассмотрим графы G_i(V_i,X_i) и G_j(V_j,X_j). Пусть G_i_j(V_i_j,X_i_j) - их наибольший общий подграф (содержит больше ребер, чем любой другой общий подграф). Тогда функции r_i_j^X = q_i + q_j - 2q_i_j и R_i_j^X = r_i_j^X / (q_i + q_j - q_i_j) будут метриками (доказательство этого факта - в статье Макарова Л.И.).

Алгоритм выбора оптимальной модели

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

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

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. Вектор параметров этой функции \mathbf{b}_{ij} равен нулю или назначается при задании G.

4. При выборе моделей из объединенного множества родительских и порожденных моделей в соответствии со значением функционала {\Sigma}_{k=1}^n({f_i({x_k}})-{y_k})^2  M наилучших, которые используются в дальнейших итерациях.

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


На каждой итерации алгоритма также исследуются попарные структурные расстояния между моделями.

Вычислительный эксперимент

Исследовалась работа алгоритма на модельных и реальных данных.

В качестве базовых были использованы 7 функций  x_1 + x_2,x_1 * x_2, 1/x, ax, a + x,sin x ,exp x . Алгоритм имеет следующие параметры :

  • MODEL_MUTATION - вероятность мутации модели
  • NUMBER_OF_MODELS - число моделей в популяции
  • EPSILON - необходимая относительная точность на обучающей выборке

В эксперименте на модельных данных была задана функция  y = (x^3)exp(-x) + 0.3exp(0.1x)sin(x)+ 0.05randn(1,300) при x = linspace(1,15,300). Случайным образом была определена обучающая выборка из 150 объектов. Параметры алгоритма имели значения MODEL_MUTATION = 0.2, NUMBER_OF_MODELS = 150, EPSILON = 0.02.

Результаты работы представлены на графиках: Изображение:ModelDataRegression.png На этом графике изображены обучающая и тестовые выборки, а также график функции, найденной алгоритмом.

Однако если рассмотреть заданную и найденную функции вне пределов задания выборки, увидим следующий результат : Изображение:ModelDataExtraRegression.png

Также исследовались статистические характеристики матрицы попарных расстояний - медиана и среднее значение: Изображение:ModelDataExtraDistances.png

Был проведен и второй эксперимент на модельных данных при большем значении шума в заданной функции и больших требованиях к точности: была задана функция  y = (x^3)exp(-x) + 0.3exp(0.1x)sin(x)+ 0.1randn(1,300) и EPSILON = 0.005.

Результаты этого эксперимента: Изображение:ModelDataRegression1.png Изображение:ModelExtraDataRegression1.png Изображение:ModelDataDistances1.png На следующем рисунке изображена гистограмма значений вектора попарных расстояний на последней итерации. Изображение:HistogramOfDistances.png

См. также

Исходный код

Скачать программную реализацию можно здесь: [1]

Литература

  • Стрижов В.В. Поиск параметрической регрессионной модели в индуктивно заданном множестве. Журнал вычислительных технологий. 2007. No 1. С. 93-102. [2]
  • Макаров Л.И. Метрические свойства функций расстояний между молекулярными графами. Журнал структурной химии. 2007. Том 48. No 2. С.223 - 229.

[3]


Данная статья была создана в рамках учебного задания.
Студент: Участник:Александр Фирстенко
Преподаватель: Участник:В.В.Стрижов
Срок: 28 мая 2010


В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.