Метод группового учёта аргументов

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

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

Метод группового учета аргументов, МГУА (Group Method of Data Handling, GMDH) — метод порождения и выбора регрессионных моделей оптимальной сложности. Под сложностью модели в МГУА понимается число параметров. Для порождения используется [базовая модель], подмножество элементов которой должно входить в искомую модель. Для выбора моделей используются внешние критерии, специальные функционалы качества моделей, вычисленные на тестовой выборке.

МГУА рекомендуется к использованию в том случае, когда выборка содержит несколько элементов. Тогда при построении регрессионных моделей использовать статистические гипотезы о плотности распределения, плотности распределения например, гипотезу о Гауссовском распределении, невозможно. Поэтому используется индуктивный подход, согласно которому последовательно порождаются модели возрастающей сложности до тех пор, пока не будет найден минимум некоторого критерия качества модели. Этот критерий качества называется внешний критерий, так как при настройке моделей и при оценке качества моделей используются разные данные. Достижение глобального минимума внешнего критерия при порождении моделей означает, что модель, доставляющая такой минимум, является искомой.

Один из авторов этого метода А.Г. Ивахненко пишет: «Осуществляется целенаправленный перебор многих моделей-претендентов различной сложности по ряду критериев. В результате находится модель оптимальной структуры в виде одного уравнения или системы уравнений. Минимум критерия селекции определяет модель оптимальной структуры».

Содержание

Описание алгоритма МГУА

Индуктивный алгоритм отыскания модели оптимальной структуры в состоит из следующих основных шагов. <bf>1.</bf> Пусть задана выборка D=\{(\mathbf{x}_n,y_n)\}_{n=1}^N, \mathbf{x}\in\R^m. Выборка разбивается на обучающую и тестовую. Обозначим \ell, C — множества индексов из \{1,\ldots,N\}=W. Эти множества удовлетворяют условиям разбиения \ell\cup C=W, \ell\cap C=\emptyset. Матрица X_\ell состоит из тех векторов-строк \mathbf{x}_n, для которых индекс n\in\ell. Вектор \mathbf{y}_\ell состоит из тех элементов y_n, для которых индекс n\in\ell. Разбиение выборки представляется в виде

X_W=\left(\begin{array}{c} X_\ell \\ \hline X_C \\ \end{array}\right), \mathbf{y}_W=\left(\begin{array}{c} \mathbf{y}_\ell \\ \hline \mathbf{y}_C\\ \end{array}\right), \mathbf{y}_W\in\R^{N{\times}1}, X_W\in\R^{N{\times}m}, |\ell|+|C|=N.

<bf>2.</bf> Назначается базовая модель. Эта модель описывает отношение между зависимой переменной y и свободными переменными \mathbf{x}. Например, используется функциональный ряд Вольтерра, называемый также полиномом Колмогорова-Габора:

y=w_0+\sum_{i=1}^mw_ix_i + \sum_{i=1}^m\sum_{j=1}^mw_{ij}x_ix_j +\sum_{i=1}^m\sum_{j=1}^m\sum_{k=1}^mw_{ijk}x_ix_jx_k+\ldots.

В этой модели \mathbf{x}=\{x_i|i=1,\ldots,m\} — множество свободных переменных и \mathbf{w} — вектор параметров — весовых коэффициентов

\mathbf{w}=\langle{w_i,w_{ij},w_{ijk},\ldots|i,j,k,\ldots=1,\ldots,m}\rangle.

В некоторых случаях имеет смысл увеличить число элементов вектора свободной переменной \mathbf{x} за счет добавления нелинейных преобразований отдельных переменных. Например, задано конечное множество нелинейных функций G=\{g|\R\longrightarrow\R\}. Дополнительная свободная переменная получается путем применения некоторого преобразования из G к одной или к нескольким переменным из множества \{x\}. Базовая модель линейна относительно параметров w и нелинейна относительно свободных переменных x. <bf>3.</bf> Исходя из поставленных задач выбирается целевая функция — внешний критерий, описывающий качество модели. Ниже описаны несколько часто используемых внешних критериев. <bf>4.</bf> Индуктивно порождаются модели-претенденты. При этом вводится ограничение на длину полинома базовой модели. Например, степень полинома базовой модели на не должно превышать заданное число R. Тогда базовая модель представима в виде линейной комбинации заданного числа F_0 произведений свободных переменных:

y=f(x_1, x_2,\ldots,x_1^2,x_1x_2,x_2^2,\ldots,x_m^R),

здесь f — линейная комбинация. Аргументы этой функции переобозначаются следующим образом:

x_1\mapsto a_1, x_2\mapsto a_2,\ldots,x_1^2\mapsto a_\alpha,x_1x_2\mapsto a_\beta,x_2^2\mapsto a_\gamma,\ldots,x_m^q\mapsto a_{F_0},

то есть,

y=f(a_1, a_2,\ldots,a_{F_0}).

Для линейно входящих коэффициентов задается одноиндексная нумерация \mathbf{w}=\langle{w_1,\ldots,w_{F_0}}\rangle. Тогда модель может быть представлена в виде линейной комбинации

y = w_0 + \sum_{i=1}^{F_0}w_ia_i = w_0 + \mathbf{w}\cdot\mathbf{a}   — скалярное произведение.

Каждая порождаемая модель задается линейной комбинацией элементов \{(w_i,a_i)\}, в которой множество индексов \{i\}=s является подмножеством \{1,\ldots,F_0\}. <bf>5.</bf> Настраиваются параметры моделей. Для настройки используется внутренний критерий — критерий, вычисляемый с использованием обучающей выборки. Каждому элементу вектора \mathbf{x}_n — элемента выборки D ставится в соответствие вектор \mathbf{a}_n, алгоритм построения соответствия указан выше. Строится матрица A_W — набор векторов-столбцов \mathbf{a}_i. Матрица A_W разбивается на подматрицы A_\ell и A_C. Наименьшую невязку \|\mathbf{y}-\hat{\mathbf{y}}\|, где \hat{\mathbf{y}}=A\hat{\mathbf{w}} доставляет значение вектора параметров \hat{\mathbf{w}}, который вычисляется методом наименьших квадратов:

\hat{\mathbf{w}}_G=(A^T_GA_G)^{-1}A_G^T\mathbf{y}_G, где G\in\{\ell,C,W\}.

При этом в качестве внутреннего критерия выступает среднеквадратичная ошибка

\eps^2_G=\|\mathbf{y}_G-A_G\hat{\mathbf{w}}_G\|^2.

В соответствии с критерием \eps^2_G\longrightarrow\min происходит настройка параметров \mathbf{w} и вычисление ошибки на тестовой подвыборке, обозначенной G, здесь G=\ell. При усложнении модели внутренний критерий не дает минимума для моделей оптимальной сложности, поэтому для выбора модели он не пригоден. <bf>6.</bf> Для выбора моделей вычисляется качество порожденных моделей. При этом используется контрольная выборка и назначенный внешний критерий. Ошибка на подвыборке H обозначается

\Delta^2(H)=\Delta^2(H{\setminus}G)=\|\mathbf{y}_H-A_H\hat{\mathbf{w}}_G\|^2,

где H\in\{\ell,C\}, H{\cap}G=\emptyset. Это означает что ошибка вычисляется на подвыборке H при параметрах модели, полученных на подвыборке G. <bf>7.</bf> Модель, доставляющая минимум внешнему критерию, считается оптимальной.

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

  • данные слишком зашумлены,
  • среди данных нет необходимых для отыскания модели переменных,
  • неверно задан критерий выбора,
  • при анализе временных рядов существует значительная временная задержка отыскиваемой причинно-следственной связи.

Внешние критерии

Авторами метода рассмотрены весьма большое число различных критериев выбора моделей. Значительная часть этих критериев опубликована на сайте http://www.gmdh.net.

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

Алгоритм МГУА использует и внутренний критерий и внешний. Внутренний критерий используется для настройки параметров модели, внешний критерий используется для выбора модели оптимальной структуры. Возможен выбор моделей по нескольким внешним критериям.

Критерий регулярности

Критерий регулярности \Delta^2(C) включает среднеквадратичную ошибку на обучающей подвыборке C полученную при параметрах модели, настроенных на тестовой подвыборке \ell.

\Delta^2(C)=\|\mathbf{y}_C-A_C\hat{\mathbf{w}}_\ell\|^2=(\mathbf{y}_C-A_C\hat{\mathbf{w}}_\ell)^T(\mathbf{y}_C-A_C\hat{\mathbf{w}}_\ell),

где

\hat{\mathbf{w}}_\ell=(A_\ell^TA_\ell)^{-1}(A_\ell^T\mathbf{y}_\ell)

и

\hat{\mathbf{y}}_C(\ell)=A_C\hat{\mathbf{w}}_\ell.

Другие модификации критерия регулярности:

\Delta^2(C)=\frac{\|\mathbf{y}_C-A_C\hat{\mathbf{w}}_\ell\|^2}{\|\mathbf{y}_C\|^2}

и

\Delta^2(C)=\frac{\|\mathbf{y}_C-A_C\hat{\mathbf{w}}_\ell\|^2}{\|\mathbf{y}_C-\bar{\mathbf{y}}_C\|^2},

где \bar{\mathbf{y}} — среднее значение вектора \mathbf{y}.

Критерий \Delta^2(C) также обозначается \Delta^2(C{\setminus}\ell), то есть ошибка на подвыборке C, при параметрах, полученных на подвыборке \ell.

Критерий минимального смещения

Иначе критерий непротиворечивости модели: модель которая имеет на обучающей выборке одну невязку, а на контрольной — другую, называется противоречивой. Этот критерий включает разность между зависимыми переменными модели, вычисленными на двух различных выборках \ell и C. Критерий не включает ошибку модели в явной форме. Он требует, чтобы оценки коэффициентов в оптимальной модели, вычисленные на множествах \ell и C, различались минимально.

Критерий непротиворечивости как критерий минимума смещения имеет вид

\eta_{\text{bs}}^2=\|A_W\hat{\mathbf{w}}_\ell-A_W\hat{\mathbf{w}}_C\|^2=(\hat{\mathbf{w}}_\ell-\hat{\mathbf{w}}_C)^TA^T_WA_W(\hat{\mathbf{w}}_\ell-\hat{\mathbf{w}}_C).

Другие модификации этого критерия:

\eta_{\text{bs}}^2=\frac{\|A_W\hat{\mathbf{w}}_\ell-A_W\hat{\mathbf{w}}_C\|^2}{\|\mathbf{y}_C-\bar{\mathbf{y}}_C\|^2}

и

\eta_a^2=\|\hat{\mathbf{w}}_\ell-\hat{\mathbf{w}}_C\|^2,

где \hat{\mathbf{w}}_\ell и \hat{\mathbf{w}}_C — векторы коэффициентов, полученные с использованием подвыборок \ell и C. При использовании последнего варианта следует помнить, что число элементов вектора параметров \mathbf{w} в различных моделях может быть различно.

Критерий absolute noise-immune

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

V^2=(A_W\hat{\mathbf{w}}_\ell-A_W\hat{\mathbf{w}}_W)^T(A_W\hat{\mathbf{w}}_W-A_W\hat{\mathbf{w}}_C)=
=(\hat{\mathbf{w}}_\ell-\hat{\mathbf{w}}_W)^TA_W^TA_W(\hat{\mathbf{w}}_W-\hat{\mathbf{w}}_C).

где \hat{\mathbf{w}}_W — вектор коэффициентов, полученный на всей выборке W.

Критерий предсказательной способности

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

X_W=\left(\begin{array}{c} X_\ell \\ \hline X_C \\ \hline X_B \\ \end{array}\right),\mathbf{y}_W=\left(\begin{array}{c} \mathbf{y}_\ell \\ \hline \mathbf{y}_C \\ \hline \mathbf{y}_B \\\end{array}\right).

Критерий предсказательной способности имеет вид

\Delta^2(W{\setminus}B)=\frac{\|\mathbf{y}_W-A_W\hat{\mathbf{w}}_B\|^2}{\|\mathbf{y}_W-\bar{\mathbf{y}}_W\|^2}.

Комбинированный критерий

Этот критерий позволяет использовать при выборе моделей линейную комбинацию нескольких критериев. Комбинированный критерий

k^2=\sum\limits_{i=1}^K\alpha_ik_i^2, при условии нормировки \sum\limits_{i=1}^K\alpha_i=1.

Здесь k_i — принятые на рассмотрение критерии, а \alpha_i — веса этих критериев, назначенные в начале вычислительного эксперимента.

Используются также нормализованные значения критериев. При этом предыдущая формула имеет вид

k^2=\sum\limits_{i=1}^K\alpha_i\frac{k_i^2}{k_{i\text{max}}^2}.

Максимальное значение критерия k_{i\text{ max}}^2 берется по вычисленным значениям критериев для всех порожденных моделей. В данном случае оптимальная модель может быть найдена только после завершения настройки параметров всех моделей.

Пример распространенного комбинированного критерия — смещение плюс ошибка аппроксимации.

c_1^2=\bar{\eta}_{\text{bs}}^2+\bar{\eps}^2(W)=\frac{\eta_\text{bs}^2}{\eta_\text{bs max}^2}+ \frac{\eps^2}{\eps^2_{\max}},

где \bar\eps^2(W) — нормализованная среднеквадратичная ошибка аппроксимации на всей выборке W=\ell\cup C с использованием коэффициентов, полученных также на W.

Второй пример комбинированного критерия — смещение плюс регулярность.

c_2^2=\bar{\eta}_\text{bs}^2+\bar{\Delta}^2(C).

Третий пример — смещение плюс ошибка на тестовой выборке.

c_3^2=\bar{\eta}_\text{bs}^2+\bar{\Delta}^2(B{\setminus}W).

Такой критерий обеспечивает выбор наиболее несмещенных, устойчивых и точных моделей. Здесь \Delta(C{\setminus}W) — среднеквадратичная ошибка, вычисленная на выборке C, с весами, настроенными на всей выборке W.

Обычно при вычислении критерия c_3 выборку делят на три части в пропорциях \ell=40\%, C=40\% и B=20\%. Выборки \ell и C используются для вычисления критерия минимального смещения, а выборка B — для вычисления ошибки предсказания. Для критериев c_1 и c_2 выборка обычно делится на две равные части.

Парето-оптимальный фронт в пространстве критериев

Парето-оптимальный фронт — альтернатива комбинированным критериям. Выбирается множество внешних критериев, условиям оптимальности которых должна удовлетворять модель. Каждой модели ставится в соответствие вектор в пространстве выбранных критериев. Отыскиваются векторы, принадлежащие Парето-оптимальному фронту множества всех векторов, соответствующих порожденным моделям. При создании комбинированного критерия рассматриваются модели, критерии которых принадлежат полученному Парето-оптимальному фронту.

Алгоритм порождения моделей МГУА

Целю МГУА является получение модели в результате перебора моделей из индуктивно-порождаемого множества. Параметры каждой модели настраиваются так, чтобы доставить минимум выбранному внешнему критерию. Различают два основных типа алгоритмов МГУА — однорядный и многорядный.

Все алгоритмы МГУА воспроизводят схему массовой селекции: последовательно порождаются модели возрастающей сложности. Каждая модель настраивается — методом наименьших квадратов находятся значения параметров. Из моделей-претендентов выбираются лучшие в соответствии с выбранным критерием. Многорядные алгоритмы могут вычислять остатки регрессионных моделей после каждого ряда селекции или не вычислять; при этом используются исходные данные.

Каждая полиномиальная модель однозначно определяется набором индексов s входящих в нее мономов

y=a_0+\mathbf{w}(s)\cdot\mathbf{a}(s).

Элементы вектора \mathbf{w} — коэффициенты при мономе полинома Колмогорова-Габора; элементы вектора \mathbf{a} — результат произведения свободных переменных соответствующих мономов. Индексы s\subseteq\{1,\ldots,F_0\} есть индексы мономов, входящих в модель. Иначе, произвольная модель

y = w_0 + \mathbf{w}(s)\cdot\mathbf{a}(s)

порождается набором индексов s\subseteq\{1,\ldots,F_0\}, включающих соотвествующие элементы векторов

\mathbf{w}=\langle{w_1,\ldots,w_{F_0}}\rangle    и    \mathbf{a}=\langle{a_1,\ldots,a_{F_0}}\rangle.

При ограничении степени полинома числом R, число мономов полинома равно

F_0=\sum_{r=1}^R\bar{C}^P_r=\sum_{r=1}^R\frac{(r+P-1)!}{P!(r-1)!},

а число моделей первого ряда соответственно равно 2^{F_0}. Здесь \bar{C}^P_r — число сочетаний с повторениями из P по r, P — число свободных переменных — элементов вектора \mathbf{x}.

Комбинаторный алгоритм

Комбинаторный (однорядный) алгоритм использует только один ряд выбора. При этом порождаются все возможные линейные комбинации ограниченной сложности. Так как под сложностью понимается число линейно входящих параметров w, то сложность не превосходит заданное значение F_0. Пусть, как и ранее

y=w_0+w_1a_1+w_2a_2+w_3a_3,\ldots,w_{F_0}a_{F_0}.

Алгоритм выполняет следующие шаги. Для всех комбинаций входных аргументов строятся модели-претенденты неубывающей сложности. Например,

\begin{array}{lll} y_1 & = & w_{10} + w_{11} a_1, \\ y_2 & = & w_{20} + w_{22} a_2, \\ y_3 & = & w_{30} + w_{31} a_1 + w_{32} a_2, \\ y_4 & = & w_{40} + w_{43} a_3, \\ y_5 & = & w_{50} + w_{51} a_1 + w_{53} a_3, \\ y_6 & = & w_{60} + w_{62} a_2 + w_{63} a_3, \\ y_7 & = & w_{70} + w_{71} a_1 + w_{72} a_2 + w_{73} a_3.\\\end{array}

Параметры каждой модели настраиваются методом наименьших квадратов по обучающей выборке. Наилучшая модель выбирается исходя из минимума значения внешнего критерия. Как вариант — назначается порог и выбираются несколько моделей, значения критерия для которых не превышает этот порог.

При программировании данного алгоритма удобно ввести переменную выбора — вектор \mathbf{c}(s)=\langle{c_{1},\ldots,c_{F_0}}\rangle. Его элемент c_i\in\{0,1\} принимает значение 1, если i\in s, в противном случае 0. Тогда модель имеет вид

y=\mathbf{c}(s)\cdot\mathbf{w}\cdot\mathbf{a}.

Последовательность векторов \mathbf{c} для предыдущего примера выглядит как

\begin{array}{cccc} 0 & \cdots & 0 & 1 \\ 0 & \cdots & 1 & 0 \\ 0 & \cdots & 1 & 1 \\ \vdots & \ddots & \vdots &\vdots \\ 1 & \cdots & 1 & 1 \\ \end{array}.

Так как при порождении моделей необходимо выбирать из 2^{F_0} моделей, что может повлечь недопустимо большое время вычислений, предложены несколько эвристических алгоритмов, позволяющих сократить время вычислений, без уменьшения максимальной сложности моделей.

Многорядный алгоритм

На первом ряде алгоритма порождения моделей задано множество из F_0 переменных a_i. Порождаются модели как линейные комбинации всевозможных пар переменных

y_{(ij)} = w_0+w_ia_i+w_ja_j, i,j=1,\ldots,F_0, i\neq j.

Число моделей первого ряда M_1 есть число сочетаний C^{F_0}_2=\frac{1}{2}{F_0}({F_0}-1)=M_1. Каждая модель, порождаемая на ряде задается парой индексов (i,j). После порождения моделей их параметры настраиваются с использованием внутреннего критерия. Затем выбираются F_1 наилучших моделей с использованием внешнего критерия. Эти модели используются в следующем ряде. Множество выбранных моделей задано множеством пар индексов \{(i,j)\}. На первом ряде индексы выбранных моделей i,j принадлежат множеству s_1\subset \{1,\ldots,F_0\}.

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

z_{(pquv)} = y_{(pq)}+y_{(uv)} = w_0+w_pa_p+w_qa_q+w_ua_u+w_va_v, p,q,u,v=1,\ldots,s_1, p\neq q\neq\ u\neq\ v.

Порожденные модели снова настраиваются, выбираются наилучшие. Индексы, задающие выбранные модели принадлежат множеству \{(p,q,u,v)\}, где p,q,u,v\in s_2 \subset s_1 \subset \{1,\ldots,F_0\}.

Таким образом на l-м ряде c помощью вышеприведенного алгоритма выбирается множество моделей, задаваемых множеством наборов индексов \{p,\ldots,v\}, которые принадлежат полученному множеству s_l\subset s_{l-1}\subset s_1 \subset \{1,\ldots,F_0\}. При этом индексация элементов моделей остается сквозной,

z_{(p\ldots v)} = y_{(p\ldots q)} + y_{(u \ldots v)} = w_0+w_pa_p + \ldots + w_v a_v.

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

Смотри также

Литература

  • Ивахненко А.Г. Индуктивный метод самоорганизации моделей сложных систем. Киев: Наукова думка. 1981.
  • Ивахненко А.Г., Степашко В.С. Помехоустойчивость моделирования. Киев: Наукова думка. 1985.
  • Malada, H.R., Ivakhnenko, A.G. Inductive Learning Algorithms for Complex Systems Modeling. CRC Press. 1994.
  • Стрижов В. В. Методы индуктивного порождения регрессионных моделей. М.: ВЦ РАН. 2008. 55 с. Брошюра, PDF.

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%BE%D0%B2%D0%BE%D0%B3%D0%BE_%D1%83%D1%87%D1%91%D1%82%D0%B0_%D0%B0%D1%80%D0%B3%D1%83%D0%BC%D0%B5%D0%BD%D1%82%D0%BE%D0%B2»
Личные инструменты