RIA

Релаксационный итеративный алгоритм Ria является усовершенствованием многорядного итеративного алгоритма Mia. Он позволяет строить сложные нелинейные модели за счёт использования лучших моделей одного ряда в качестве новых переменных следующего ряда, а в основе генерации моделей-кандидатов лежит базовый полином polynomial_type, выбираемый до начала обучения. Отличие же данного алгоритма от Mia заключается в модифицированном способе формирования моделей-кандидатов нового уровня, благодаря которому ускоряется процесс обучения.

Сначала на первом ряду рассматриваются все модели, соответствующие выбранному виду полинома. Начиная со второго ряда, метод продолжает строить новые модели в соответствии с заданным полиномом, но при этом в качестве переменных использует уже не только исходную выборку данных c \(n\) переменными, но и сами полиномы k_best лучших моделей предыдущего ряда. При этом модели-кандидаты формируются в виде базового полинома от двух переменных: одной переменной из исходного набора и одной новой переменной, представляющей собой полином модели предыдущего ряда.

Возможные виды базовых полиномов polynomial_type:

• LINEAR

  \(f(x_i, x_j)=w_0+w_1x_i+w_2x_j\);

• LINEAR_COV

  \(f(x_i, x_j)=w_0+w_1x_i+w_2x_j+w_{12}x_ix_j\);

• QUADRATIC

  \(f(x_i, x_j)=w_0+w_1x_i+w_2x_j+w_{12}x_ix_j+w_{11}x_i^2+w_{22}x_j^2\).

Note

Подробнее об использовании полиномов написано в примечании к Mia.

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

---

На первом ряду перебираются все модели-кандидаты c выбранным базовым полиномом \(f(x_i,x_j)\) для каждой пары \((x_i, x_j)\):

\[ y=f(x_i,x_j), \;\; i,j\in[1,n], \;\; j>i. \]

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

---

Далее алгоритм переходит на второй ряд и k_best лучших полиномов \(y(x_i,x_j)\) первого ряда становятся новыми переменными \(y_1,...,y_{k\_best}\) вдобавок к переменным \(x_1,...x_n\). Затем к каждой паре \((y_i,x_j)\) применяется базовый полином polynomial_type для построения моделей-кандидатов вида

\[ z=f(y_i,x_j), \;\; i\in{[1,k\_best]}, \;\; j\in[1,n]. \]

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

---

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

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

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

---

Максимально возможное число рядов для данного алгоритма равно не ограничено. Количество моделей-кандидатов на каждом ряду \(i\) равно

\[\begin{split} M_i= \begin{cases} C_{n}^2, \; i=1\\ k\_best\cdot n, \; i>1 \end{cases} \end{split}\]

---

Пример

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

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

\[\begin{split} y_1 = f(x_1, x_2)=w_0+w_1x_1+w_2x_2+w_{12}x_1x_2+w_{11}x_1^2+w_{22}x_2^2, \;\;\;\; e=10\\ y_2 = f(x_1, x_3)=w_0+w_1x_1+w_2x_3+w_{12}x_1x_3+w_{11}x_1^2+w_{22}x_3^2, \;\;\;\; e=13\\ y_3 = f(x_2, x_3)=w_0+w_1x_2+w_2x_3+w_{12}x_2x_3+w_{11}x_2^2+w_{22}x_3^2, \;\;\;\; e=12\\ \end{split}\]

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

Качество первого ряда оцениваем по двум лучшим моделям: \(E_1=\frac{10+12}{2}=11\).

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

\[\begin{split} z_1 = f(y_1, x_1)=w_0+w_1y_1+w_2x_1+w_{12}y_1x_1+w_{11}y_1^2+w_{22}x_1^2, \;\;\;\; e=9\\ z_2 = f(y_1, x_2)=w_0+w_1y_1+w_2x_2+w_{12}y_1x_2+w_{11}y_1^2+w_{22}x_2^2, \;\;\;\; e=8\\ z_3 = f(y_1, x_3)=w_0+w_1y_1+w_2x_3+w_{12}y_1x_3+w_{11}y_1^2+w_{22}x_3^2, \;\;\;\; e=8\\ z_4 = f(y_3, x_1)=w_0+w_1y_3+w_2x_1+w_{12}y_3x_1+w_{11}y_3^2+w_{22}x_1^2, \;\;\;\; e=7\\ z_5 = f(y_3, x_2)=w_0+w_1y_3+w_2x_2+w_{12}y_3x_2+w_{11}y_3^2+w_{22}x_2^2, \;\;\;\; e=9\\ z_6 = f(y_3, x_3)=w_0+w_1y_3+w_2x_3+w_{12}y_3x_3+w_{11}y_3^2+w_{22}x_3^2, \;\;\;\; e=6\\ \end{split}\]

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

Качество второго ряда оцениваем по двум лучшим моделям: \(E_2=\frac{6+7}{2}=6,5\).

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

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

\[\begin{split} g_1 = f(z_6, x_1)=w_0+w_1z_6+w_2x_1+w_{12}z_6x_1+w_{11}z_6^2+w_{22}x_1^2, \;\;\;\; e=7\\ g_2 = f(z_6, x_2)=w_0+w_1z_6+w_2x_2+w_{12}z_6x_2+w_{11}z_6^2+w_{22}x_2^2, \;\;\;\; e=7\\ g_3 = f(z_6, x_3)=w_0+w_1z_6+w_2x_3+w_{12}z_6x_3+w_{11}z_6^2+w_{22}x_3^2, \;\;\;\; e=9\\ g_4 = f(z_4, x_1)=w_0+w_1z_4+w_2x_1+w_{12}z_4x_1+w_{11}z_4^2+w_{22}x_1^2, \;\;\;\; e=8\\ g_5 = f(z_4, x_2)=w_0+w_1z_4+w_2x_2+w_{12}z_4x_2+w_{11}z_4^2+w_{22}x_2^2, \;\;\;\; e=8\\ g_6 = f(z_4, x_3)=w_0+w_1z_4+w_2x_3+w_{12}z_4x_3+w_{11}z_4^2+w_{22}x_3^2, \;\;\;\; e=9\\ \end{split}\]

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

Качество третьего ряда оцениваем по двум лучшим моделям: \(E_3=\frac{7+7}{2}=7\).

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

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

\[ z_6 = f(y_3, x_3)=w_0+w_1y_3+w_2x_3+w_{12}y_3x_3+w_{11}y_3^2+w_{22}x_3^2,, \]

где

\[ y_3 = f(x_2, x_3)=w_0+w_1x_2+w_2x_3+w_{12}x_2x_3+w_{11}x_2^2+w_{22}x_3^2. \]