MULTI

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

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

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

---

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

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

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

---

Далее алгоритм переходит на второй ряд и к полиному каждой из k_best лучших моделей \(y(x_i)\) добавляется по одному новому слагаемому \(w_jx_j\) для \(j\neq{i}\). То есть, если лучшими моделями на первом ряду были \(y(x_1)\) и \(y(x_3)\), то на втором ряду получим модели кандидаты вида

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

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

---

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

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

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

---

Максимально возможное число рядов для данного алгоритма равно \(n\). Количество моделей-кандидатов на каждом ряду \(i\) равно \(M_i\leq\) k_best\(\cdot n\). Общее максимальное количество моделей-кандидатов на всех рядах равно \(M\leq\) k_best\(\cdot n^2\).

---

Пример

Пусть имеется четыре признака \(x_1\), \(x_2\), \(x_3\), \(x_4\), по которым нужно спрогнозировать значение \(y\). Гиперпараметрам алгоритма зададим значения: k_best \(=2\), p_average \(=1\), limit \(=0\). Значения внешнего критерия модели обозначим через \(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\\ y(x_4)=w_0+w_4x_4, \;\;\;\; e=13\\ \end{split}\]

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

Качество первого ряда оцениваем по одной лучшей модели: \(E_1=10\).

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

• Усложненные модели на основе \(y(x_1)\):

\[\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_1,x_4)=w_0+w_1x_1+w_4x_4, \;\;\;\; e=6\\ \end{split}\]

• Усложненные модели на основе \(y(x_4)\):

\[\begin{split} y(x_4,x_2)=w_0+w_4x_4+w_2x_2, \;\;\;\; e=5\\ y(x_4,x_3)=w_0+w_4x_4+w_3x_3, \;\;\;\; e=8\\ \end{split}\]

Отбираем 2 лучшие модели из всех 5 моделей-кандидатов: \(y(x_4,x_2)\) и \(y(x_1,x_4)\).

Качество второго ряда оцениваем по одной лучшей модели: \(E_2=5\).

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

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

• Усложненные модели на основе \(y(x_4,x_2)\):

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

• Усложненные модели на основе \(y(x_1,x_4)\):

\[\begin{split} y(x_1,x_4,x_3)=w_0+w_1x_1+w_4x_4+w_3x_3, \;\;\;\; e=6\\ \end{split}\]

Отбираем 2 лучшие модели из всех 3 моделей-кандидатов: \(y(x_1,x_4,x_3)\) и \(y(x_4,x_2,x_3)\).

Качество второго ряда оцениваем по одной лучшей модели: \(E_3=6\).

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

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

\[ y(x_4,x_2)=w_0+w_4x_4+w_2x_2. \]