MIA#
Многорядный итеративный алгоритм Mia является исторически первым алгоритмом МГУА. Он позволяет строить сложные нелинейные модели за счёт использования лучших моделей одного ряда в качестве новых переменных следующего ряда. В основе метода генерации моделей-кандидатов лежит базовый полином polynomial_type, выбираемый до начала обучения.
Сначала на первом ряду рассматриваются все модели, соответствующие выбранному виду полинома. Начиная со второго ряда, метод продолжает строить новые модели в соответствии с заданным полиномом, но при этом в качестве переменных использует уже не исходную выборку данных 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 и Ria, построена на аппроксимационной теореме Вейерштрасса, согласно которой любая непрерывная функция, определённая на замкнутом множестве, может быть приближена некоторым полиномом с любой точностью. Из этого следует, что искать оптимальную модель при обучении алгоритма МГУА можно в виде полиномиальных функций.
Общий вид таких функции задаёт полином Колмогорова-Габора:
Фиксируя степень полинома и количество переменных, мы можем получить конкретное уравнение. Так, при \(n=2\) и максимальной степени полинома, равной двум, получаем:
Данное уравнение соответсвует функции Polynomial_type.QUADRATIC. Остальные базовые полиномы образуются аналогичным образом.
Этапы обучения#
На первом ряду перебираются все модели-кандидаты c выбранным базовым полиномом \(f(x_i,x_j)\) для каждой пары \((x_i, x_j)\):
Методом наименьших квадратов (МНК) рассчитываются параметры \(w\) для каждой из моделей. После этого вычисляется заданный внешний критерий criterion, по значению которого модели сортируются в порядке возрастания. Затем отбирается k_best лучших моделей. А средняя величина внешнего критерия первых p_average моделей принимается за качество текущего ряда. Обозначим данную величину \(E_1\).
Далее алгоритм переходит на второй ряд и k_best лучших полиномов \(y(x_i,x_j)\) первого ряда становятся новыми переменными \(y_1,...,y_{k\_best},\) к каждой паре которых применяется всё тот же базовый полином polynomial_type для построения моделей-кандидатов вида
Снова с помощью МНК вычисляются параметры \(w\) и затем для всех моделей-кандидатов второго ряда рассчитывается внешний критерий criterion. После сортировки значений критерия снова отбирается k_best лучших моделей, а качество второго ряда \(E_2\) определяется как средний результат p_average лучших моделей.
Далее качество текущего ряда сравнивается с качеством предыдущего ряда:
если \(E_1\) - \(E_2\) \(\ge\)
limit, то качество моделей текущего ряда значительно улучшилось и алгоритм продолжит обучение, перейдя на третий ряд для перебора ещё более сложных моделей \(f(z_i,z_j)\).если \(E_1\) - \(E_2\) <
limit, то качество моделей улучшилось незначительно либо вовсе ухудшилось. В таком случае процесс обучения прекращается и моделью оптимальной сложности становится модель предыдущего ряда с наименьшим значением внешнего критерия.
Максимально возможное число рядов для данного алгоритма равно не ограничено. Количество моделей-кандидатов на каждом ряду \(i\) равно
Пример#
Пусть имеется четыре признака \(x_1\), \(x_2\), \(x_3\), \(x_4\), по которым нужно спрогнозировать значение \(y\). Гиперпараметрам алгоритма зададим значения: polynomial_type=Polynomial_type.QUADRATIC, k_best \(=3\), p_average \(=2\), limit \(=1\). Значения внешнего критерия модели обозначим через \(e\) (для простоты в данном примере значения \(e\) выбраны случайно).
На ряду №1 получим модели-кандидаты:
Отбираем 3 лучшие модели: \(y_1\), \(y_5\) и \(y_2\).
Качество первого ряда оцениваем по двум лучшим моделям: \(E_1=\frac{10+11}{2}=10,5\).
На ряду №2 получим модели-кандидаты:
Отбираем 3 лучшие модели: \(z_1\), \(z_2\) и \(z_3\).
Качество второго ряда оцениваем по двум лучшим моделям: \(E_2=\frac{6+7}{2}=6,5\).
\(E_1-E_2=4\ge{1}\), значит качество второго ряда значительно лучше первого и нужно продолжить обучение.
На ряду №3 получим модели-кандидаты:
Отбираем 3 лучшие модели: \(g_1\), \(g_2\) и \(g_3\).
Качество третьего ряда оцениваем по двум лучшим моделям: \(E_3=\frac{3+9}{2}=6\).
\(E_2-E_3=0,5<1\), следовательно качество ряда улучшилось незначительно. Обучение заканчивается.
Оптимальной моделью становится лучшая модель предыдущего ряда:
где