COMBI

Комбинаторный алгоритм Combi является базовым алгоритмом МГУА. Он рассматривает только линейные модели, то есть выражает зависимость целевой величины \(y\) в виде линейной комбинации переменных \(x_1,...,x_n\).

Этапы обучения

---

На первом ряду перебираются все модели-кандидаты вида

\[ y(x_i)=w_0+w_ix_i, \;\; i\in[1,n]. \]

Методом наименьших квадратов (МНК) рассчитывается параметр \(w_i\) для каждой из моделей. После этого вычисляется заданный внешний критерий criterion, по значению которого модели сортируются в порядке возрастания. Средняя величина внешнего критерия первых p_average моделей принимается за качество текущего ряда. Обозначим данную величину \(E_1\).

---

Далее алгоритм переходит на второй ряд и новые модели-кандидаты усложняются до вида

\[ y(x_i, x_j)=w_0+w_ix_i+w_jx_j, \;\; i,j\in[1,n], \;\; j>i. \]

Снова с помощью МНК вычисляются параметры \(w_i\) и \(w_j\) и затем для всех моделей-кандидатов второго ряда рассчитывается внешний критерий criterion. После сортировки значений критерия определяется качество второго ряда \(E_2\) как среднего результата p_average лучших моделей.

---

Далее качество текущего ряда сравнивается с качеством предыдущего ряда:

• если \(E_1\) - \(E_2\) \(\ge\) limit, то качество моделей текущего ряда значительно улучшилось и алгоритм продолжит обучение, перейдя на третий ряд для перебора ещё более сложных моделей \(y(x_i, x_j, x_k)\).

• если \(E_1\) - \(E_2\) < limit, то качество моделей улучшилось незначительно либо вовсе ухудшилось. В таком случае процесс обучения прекращается и моделью оптимальной сложности становится модель предыдущего ряда с наименьшим значением внешнего критерия.

---

Максимально возможное число рядов для данного алгоритма равно \(n\). Количество моделей-кандидатов на каждом ряду \(i\) равно \(M_i=C_n^i\). Общее максимальное количество моделей-кандидатов на всех рядах равно \(M=\sum_{i=1}^nC_n^i=2^n-1\).

---

Пример

Пусть имеется три признака \(x_1\), \(x_2\), \(x_3\), по которым нужно спрогнозировать значение \(y\). Гиперпараметрам алгоритма зададим значения: p_average \(=2\), limit \(=1\). Значения внешнего критерия модели обозначим через \(e\) (для простоты в данном примере значения \(e\) выбраны случайно).

На ряду №1 получим модели-кандидаты:

\[\begin{split} y(x_1)=w_0+w_1x_1, \;\;\;\; e=10\\ y(x_2)=w_0+w_2x_2, \;\;\;\; e=14\\ y(x_3)=w_0+w_3x_3, \;\;\;\; e=20\\ \end{split}\]

Отбираем 2 лучшие модели: \(y(x_1)\) и \(y(x_2)\).

Тогда качество первого ряда равно \(E_1=\frac{10+14}{2}=12\).

На ряду №2 получим модели-кандидаты:

\[\begin{split} y(x_1,x_2)=w_0+w_1x_1+w_2x_2, \;\;\;\; e=8\\ y(x_1,x_3)=w_0+w_1x_1+w_3x_3, \;\;\;\; e=9\\ y(x_2,x_3)=w_0+w_2x_2+w_3x_3, \;\;\;\; e=4\\ \end{split}\]

Отбираем 2 лучшие модели: \(y(x_1,x_3)\) и \(y(x_1,x_2)\).

Тогда качество второго ряда равно \(E_2=\frac{4+18}{2}=6\).

\(E_1-E_2=6\ge{1}\), значит качество второго ряда значительно лучше первого и нужно продолжить обучение.

На ряду №3 получим одну модель-кандидат:

\[\begin{split} y(x_1,x_2,x_3)=w_0+w_1x_1+w_2x_2+w_3x_3, \;\;\;\; e=5.5\\ \end{split}\]

Так как модель только одна, качество третьего ряда будет равно значению внешнего критерия единственной модели, то есть \(E_3=5.5\).

\(E_1-E_2=0.5<1\), следовательно качество ряда улучшилось незначительно. Обучение заканчивается.

Оптимальной моделью становится лучшая модель предыдущего ряда:

\[ y(x_2,x_3)=w_0+w_2x_2+w_3x_3. \]