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

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

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

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

Содержание

1 Постановка задачи
2 Сведения о структурных расстояниях ( метриках ) на множестве помеченных графов
3 Алгоритм выбора оптимальной модели
4 Вычислительный эксперимент
5 См. также
6 Исходный код
7 Литература

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

Задана выборка — множество $\{\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.

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

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

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

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