DREM для линейной регрессии: как развязать веса перцептрона и ускорить обучение

Ключевые слова: DREM, линейная регрессия, перцептрон, градиентный спуск, идентификация параметров.

Зачем нужен еще один способ обучать линейную регрессию?

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

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

В этой статье рассматривается метод DREM — Dynamic Regressor Extension and Mixing. Изначально он был предложен для задач параметрической идентификации в системах управления [1]. Основная идея метода состоит в том, чтобы заменить одну многопараметрическую задачу набором независимых скалярных задач.

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

Обычная линейная регрессия и стохастический градиентный спуск

Рассмотрим обучающую выборку

$(x_i, y_i), \quad i=1,\ldots,N,$

где $x_i \in R^p$ — вектор признаков, $y_i \in R$ — целевое значение. Добавим свободный член и будем использовать расширенный вектор признаков

$\varphi_i = \begin{bmatrix} 1 & x_{i1} & x_{i2} & \ldots & x_{ip} \end{bmatrix}^{T} \in R^{p+1}.$

Линейный перцептрон для регрессии имеет вид

$\hat y_i = \varphi_i^T w,$

где $w = \begin{bmatrix} w_0 & w_1 & \ldots & w_{p} \end{bmatrix}^{T} \in R^{p+1}$ — вектор весов.

Функция потерь:

$L(w) = \frac{1}{N} \sum_{i=1}^{N} \left(y_i-\varphi_i^T w\right)^2.$

В стохастическом градиентном спуске на каждой итерации выбирается мини-пакет , содержащий объектов. Для этого мини-пакета выполняется обновление

$w^{k+1} = w^k + \alpha \frac{1}{n_B} \sum_{i\in B_k} \varphi_i \left(y_i-\varphi_i^T w^k\right),$

где

$\alpha>0$ — скорость обучения.

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

Классический DREM: от векторной регрессии к скалярным

Исходная задача идентификации

В классической постановке DREM рассматривается линейная регрессия для функций времени :

$y(t)=m^T(t)w, \tag{1}$

где $y(t)\in R, m(t)\in R^q$ — измеряемые сигналы, $w\in R^q$ — неизвестный постоянный вектор параметров. В контексте машинного обучения этот же вектор можно интерпретировать как веса линейного перцептрона. Задача состоит в том, чтобы построить оценку $\hat w(t)$ , сходящуюся к истинному значению .

Классический градиентный оцениватель для (1) можно записать как

$\dot{\hat w} = \Gamma m(t) \left( y(t)-m^T(t)\hat w \right),$

где

$\Gamma=\Gamma^T>0$ — матрица коэффициентов адаптации.

Такой подход работает, но сходимость всех компонент $\hat w_i$ связана через один и тот же вектор . Кроме того, для параметрической сходимости обычно требуется достаточно сильное условие возбуждения регрессора [2]. DREM предлагает другую процедуру: сначала расширить исходную регрессию, а затем преобразовать ее так, чтобы получить независимые скалярные регрессии для отдельных параметров.

Шаг 1: динамическое расширение регрессора

DREM начинает с того, что к исходной регрессии (1) применяются устойчивых линейных операторов $H_1,\ldots,H_{q-1}$ . Например, это могут быть устойчивые фильтры первого порядка

$H_j(s)=\frac{\lambda_j}{s+\lambda_j}, \quad \lambda_j>0,$

где — оператор дифференцирования, или операторы запаздывания

$H_j[v](t)=v(t-d_j), \quad d_j>0,$

причем значения $\lambda_j$ (или ) должны быть различными для всех $j = 1, \dots, q-1$

После применения операторов получаем

$y_{f_j}(t)=H_j[y](t), \quad m_{f_j}(t)=H_j[m](t), \quad j=1,\ldots,q-1.$

Теперь у нас есть не одно, а уравнений:

$\begin{cases} y(t)=m^T(t)w,\\ y_{f_1}(t)=m_{f_1}^{T}(t)w,\\ \vdots\\ y_{f_{q-1}}(t)=m_{f_{q-1}}^{T}(t)w. \end{cases}$

Их можно записать в матричной форме:

$Y_e(t)=M(t)w, \tag{2}$

где — выход расширенной регрессионной модели, — расширенный регрессор. Это и называется динамическим расширением регрессора. Мы искусственно строим квадратную систему, в которой число уравнений равно числу неизвестных параметров.

Шаг 2: смешивание

Теперь используем стандартное свойство союзной матрицы:

$\operatorname{adj}\{M(t)\}M(t) = \det\{M(t)\}I.$

Умножив (2) слева на $\operatorname{adj}\{M(t)\}$ , с учетом свойства союзной матрицы, получаем

$Y(t)=\Delta(t)w, \tag{3}$

где

$Y(t)=\operatorname{adj}\{M(t)\}Y_e(t), \quad \Delta(t)=\det\{M(t)\}.$

Уравнение (3) распадается на независимых скалярных регрессий:

$Y_i(t)=\Delta(t)w_i, \quad i=1,\ldots,q. \tag{4}$

Это ключевой результат DREM. Вместо одной векторной регрессии мы получили набор скалярных задач. Каждая из них содержит только один неизвестный параметр . Именно поэтому говорят, что DREM развязывает параметры.

Шаг 3: скалярные законы обновления весов

Для каждой скалярной регрессии (4) можно использовать независимый градиентный спуск. В непрерывном времени:

$\dot{\hat w}_i(t) = \gamma_i \Delta(t) \left( Y_i(t)-\Delta(t)\hat w_i(t) \right), \quad \gamma_i>0.$

Для дискретной реализации закон обновления весов можно записать в виде

$\hat w_i^{k+1} = \hat w_i^k + \alpha \Delta(t_k) \left( Y_i(t_k)-\Delta(t_k)\hat w_i^k \right), \quad \alpha>0.$

Динамика ошибки $\tilde w_i = w_i - \hat w_i$ имеет вид

$\tilde w_i^{k+1} = \left( 1-\alpha\Delta^2(t_k) \right) \tilde w_i^k.$

Отсюда видно, что для устойчивого монотонного уменьшения ошибки на шаге необходимо, чтобы выполнялось условие $\left| 1-\alpha\Delta^2(t_k) \right|<1$ , что эквивалентно

$0<\alpha<\frac{2}{\Delta^2(t_k)}.$

Проблема стандартного дискретного закона состоит в том, что $\Delta(t_k)$ может сильно меняться во времени. Поэтому один и тот же шаг $\alpha$ может быть корректным на одних участках данных и слишком большим на других. Чтобы уменьшить чувствительность к масштабу $\Delta(t_k)$ , можно использовать адаптивно-нормированное обновление:

$\hat w_i^{k+1} = \hat w_i^k + \frac{ \alpha\Delta(t_k) }{ 1+\alpha\Delta(t_k) } \left( Y_i(t_k))-\Delta(t_k)\hat w_i^k \right), \quad \alpha>0.$

В этом случае в отсутствие шума получаем

$\tilde w_i^{k+1} = \frac{1}{1+\alpha\Delta_k^2} \tilde w_i^k.$

Множитель $\frac{1}{1+\alpha\Delta_k^2}$ при

$\alpha>0$ всегда принадлежит интервалу . Поэтому адаптивная форма обновления автоматически обеспечивает эффективный шаг.

Таким образом, стандартный DREM-алгоритм обновления весов проще, но требует более аккуратного выбора скорости обучения. Адаптивный вариант добавляет нормировку и обычно оказывается более устойчивым в дискретной реализации.

Простой пример DREM

Чтобы идея была более понятной, рассмотрим случай двух неизвестных параметров:

Здесь $m^T(t)= \begin{bmatrix} m_1(t) & m_2(t) \end{bmatrix}, \quad w^T= \begin{bmatrix} w_1 & w_2 \end{bmatrix}.$

Для DREM при нужен один дополнительный оператор. Возьмем устойчивый фильтр первого порядка:

$H(s)=\frac{\lambda}{s+\lambda}, \quad \lambda>0. \tag{5}$

Так как и постоянны, отфильтрованное уравнение сохраняет линейную структуру:

$y_f(t)=m_{1f}(t)w_1+m_{2f}(t)w_2.$

Теперь составим расширенную систему:

$\begin{bmatrix} y(t)\\ y_f(t) \end{bmatrix} = \begin{bmatrix} m_1(t) & m_2(t)\\ m_{1f}(t) & m_{2f}(t) \end{bmatrix} \begin{bmatrix} w_1\\ w_2 \end{bmatrix}.$

Обозначим

$M(t)= \begin{bmatrix} m_1(t) & m_2(t)\\ m_{1f}(t) & m_{2f}(t) \end{bmatrix}.$

Определитель этой матрицы равен

$\Delta(t) = m_1(t)m_{2f}(t)-m_2(t)m_{1f}(t).$

Союзная матрица имеет вид

$\operatorname{adj}\{M(t)\} = \begin{bmatrix} m_{2f}(t) & -m_2(t)\\ -m_{1f}(t) & m_1(t) \end{bmatrix}.$

Умножим расширенное уравнение на союзную матрицу:

$\begin{bmatrix} m_{2f}(t) & -m_2(t)\\ -m_{1f}(t) & m_1(t) \end{bmatrix} \begin{bmatrix} y(t)\\ y_f(t) \end{bmatrix} = \Delta(t) \begin{bmatrix} w_1\\ w_2 \end{bmatrix}.$

Получаем две скалярные регрессии:

$Y_1(t) = m_{2f}(t)y(t)-m_2(t)y_f(t) = \Delta(t)w_1,$ $Y_2(t) = -m_{1f}(t)y(t)+m_1(t)y_f(t) = \Delta(t)w_2.$

Теперь и можно оценивать любым из вышеприведенных способов.

Как адаптировать DREM к табличной регрессии

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

Пусть число весов равно . На каждой итерации возьмем мини-пакет из объектов: $X_b\in R^{q\times q}, \quad y_b\in R^q.$ Тогда для мини-пакета линейная модель записывается как

Это соответствует форме регрессионной модели с квадратной матрицей регрессора. Применим к ней DREM-смешивание:

$\operatorname{adj}\{X_b\}y_b = \operatorname{adj}\{X_b\}X_b w = \det\{X_b\}w.$

Обозначим

$\Delta_b=\det\{X_b\}, \quad Z_b=\operatorname{adj}\{X_b\}y_b.$

Получаем

$Z_b=\Delta_b w.$

Или покомпонентно:

$Z_{b,i}=\Delta_b w_i, \quad i=1,\ldots,q.$

Это полная аналогия с классическим DREM. Только роль расширенной матрицы теперь играет матрица мини-пакета .

Вычисление через правило Крамера

Вычислять союзную матрицу явно не обязательно. По правилу Крамера элемент $Z_{b,i}$ можно получить как

$Z_{b,i}=\det\{X_{b,i}\},$

где $X_{b,i}$ — матрица , в которой -й столбец заменен на вектор .

Таким образом, на каждом мини-пакете нужно вычислить:

один определитель $\Delta_b=\det\{X_b\}$ ;
определителей $\det\{X_{b,i}\}$ для всех весов.

Это вычислительно дороже, чем один шаг стохастического градиентного спуска, но может компенсироваться меньшим числом эпох.

Законы настройки весов для пакетного DREM

После DREM-преобразования получаем набор скалярных уравнений

$Z_{b,i}=\Delta_b w_i, \quad i=1,\ldots,q,$

Далее можно использовать один из двух законов настройки. Первый вариант — стандартное DREM-обновление:

$\hat w_i^{k+1} = \hat w_i^k + \alpha\Delta_b \left( Z_{b,i}-\Delta_b \hat w_i^k \right), \quad i=1,\ldots,q.$

Этот вариант напрямую повторяет стандартный скалярный закон DREM, только вместо временных величин и $\Delta(t)$ используются mini-batch величины $Z_{b,i}$ и $\Delta_b$ .

Второй вариант — адаптивно-нормированное обновление:

$\hat w_i^{k+1} = \hat w_i^k + \frac{\alpha\Delta_b}{1+\alpha\Delta_b^2} \left( Z_{b,i}-\Delta_b \hat w_i^k \right), \quad i=1,\ldots,q.$

Нормировка на $1+\alpha\Delta_b^2$ уменьшает зависимость обновления от масштаба определителя матрицы пакета. Поэтому в вычислительных экспериментах этот вариант обычно оказывается устойчивее стандартного обновления.

Важное практическое ограничение связано с определителем матрицы пакета $\Delta_b$ . Если строки или столбцы матрицы оказываются линейно зависимыми или почти линейно зависимыми, то определитель становится равным нулю или очень малым. В таком случае преобразованная скалярная регрессия становится малоинформативной: правая часть $\Delta_b w_i$ почти не зависит от значения веса, а обновление параметров может стать неэффективным или численно неустойчивым. На практике это означает, что качество работы DREM существенно зависит от того, насколько хорошо обусловлены матрицы .

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

Во-вторых, можно контролировать структуру данных при формировании пакета. Поэтому пакеты можно формировать не полностью случайно, а с дополнительной проверкой на линейную зависимость строк или на число обусловленности матрицы.

В-третьих, можно использовать простой численный критерий и отбрасывать пакеты, для которых $|\Delta_b|<\varepsilon$ , где

$\varepsilon>0$ — заранее выбранный малый порог. Такой пакет не используется для обновления весов, поскольку он почти не несет полезной информации для DREM-преобразования.

Результирующий алгоритм обучения

Для линейной регрессии алгоритм можно записать следующим образом.

Добавить к матрице признаков столбец единиц.
Нормализовать признаки.
Инициализировать оценку весов $\hat w$ случайно или нулями.
На каждой эпохе перемешать данные.
Разбить данные на мини-пакеты размера .
Для каждого мини-пакета:
1. сформировать квадратную матрицу и вектор ;
2. вычислить $\Delta_b=\det\{X_b\}$ ;
3. если $|\Delta_b|<\varepsilon$ , пропустить мини-пакет;
4. для каждого веса $\hat w_i$ вычислить $Z_{b,i}=\det\{X_{b,i}\}$ ;
5. обновить $\hat w_i$ по Standard DREM или Adaptive DREM.
Повторять до заданного числа эпох или до стабилизации функции потерь.

Экспериментальная апробация

Для проверки метода использовались три набора данных.

make_regression. Синтетический датасет из библиотеки sklearn, позволяющий управлять числом объектов, числом признаков и уровнем шума.
auto-mpg. Реальный датасет для предсказания расхода топлива автомобиля. Он полезен тем, что содержит признаки с потенциальной мультиколлинеарностью: масса, мощность, объем двигателя и т.д.
Salary_Data. Небольшой реальный датасет для предсказания зарплаты по характеристикам человека, например опыту работы.

Сравнивались четыре алгоритма: пакетный градиентный спуск (mini-batch SGD), DREM (Standart и Adaptive), ADAM.

В экспериментах анализировалось влияние на процесс обучения: числа эпох, уровня шума в синтетических данных, объема выборки, числа признаков. Также исследовались затраты времени на обучение в зависимости от размера датасета и количества признаков.

График 1: MSE от количества эпох — standart*

График 2: MSE от количества эпох — adapt*

Алгоритмы DREM (Standard и Adapt) демонстрируют более высокую скорость сходимости, при этом Standart может становиться неустойчивым. ADAM снижает ошибку плавно на протяжении всего цикла обучения. SGD показывает наименьшую, но достаточно плавную динамику сходимости.

График 3: MSE от уровня шума — standart*

График 4: MSE от уровня шума — adapt*

Алгоритм ADAM наиболее устойчив к высокому уровню дисперсии в данных. Обе модификации DREM (Standard и Adapt) показывают небольшой рост ошибки при высокой зашумленности данных. Ошибка SGD остается стабильно высокой независимо от параметров шума.

График 5: MSE от размера выборки — standart*

График 6: MSE от размера выборки — adapt*

DREM (Standard и Adapt) способны минимизировать ошибку на малых выборках (от 100 элементов). Методы ADAM и SGD требуют значительного увеличения объема данных (до 10 000 элементов) для достижения аналогичных показателей точности.

График 7: MSE от количества признаков — standart*

График 8: MSE от количества признаков — adapt*

У алгоритмов DREM (Standard и Adapt) зафиксирован сильный взрыв ошибки при числе признаков более 10 из-за математической нестабильности при расчете определителей. ADAM сохраняет стабильность вычислений независимо от размерности. SGD имеет тенденцию к росту ошибки.

График 9: Время обучения от размера датасета — standart*

График 10: Время обучения от размера датасета — adapt*

Временные затраты предсказуемо возрастают у всех методов. SGD является наиболее быстрым, ADAM — наиболее ресурсоемким. Показатели DREM (Standard и Adapt) почти идентичны и находятся на среднем уровне.

График 11: Время обучения от количества признаков — standart*

График 12: Время обучения от количества признаков — adapt*

Время вычислений ADAM и SGD монотонно возрастает. Время работы DREM Standard увеличивается пропорционально размерности. У DREM Adapt зафиксировано аномальное снижение времени вычислений из-за пропуска итераций адаптации при возникновении вырожденных матриц.

Сравнительный анализ методов оптимизации

Критерий	SGD	ADAM	DREM (Standard)	DREM (Adapt)
Скорость сходимости (в эпохах)	Низкая	Средняя	Высокая со скачками	Высокая
Устойчивость к зашумленности	Низкая	Высокая	Средняя	Высокая
Эффективность на малых выборках	Низкая	Средняя	Высокая	Высокая
Устойчивость к числу признаков	Средняя	Высокая	Низкая (взрыв ошибки)	Низкая (взрыв ошибки)
Вычислительная сложность (время)	Низкая	Высокая	Средняя	Средняя
Математические ограничения	Проблема локальных минимумов	Требует настройки гиперпараметров	Чувствителен к вырожденным матрицам	Чувствителен к вырожденным матрицам

Ссылка на код: https://github.com/AlexeyMarg/DREM_ML_optimizer.

Заключение

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

Во-первых, DREM имеет смысл использовать в задачах с относительно небольшим числом признаков. Во-вторых, DREM может быть полезен на небольших датасетах, так как обеспечивает более быструю сходимость на меньшем количестве данных. В-третьих, перспективным выглядит гибридный сценарий обучения. На первых эпохах DREM можно использовать как быстрый стартовый оптимизатор, который резко снижает ошибку за счет скаляризации задачи. После этого можно переключиться на более устойчивый метод, например Adam, чтобы аккуратно довести параметры до финального решения. Такой подход позволяет совместить сильные стороны обоих методов: быструю начальную сходимость DREM и устойчивость Adam на последующих этапах обучения.

Литература

Aranovskiy S., Bobtsov A., Ortega R., Pyrkin A. Performance enhancement of parameter estimators via dynamic regressor extension and mixing. IEEE Transactions on Automatic Control, 2017, Vol. 62, No. 7, pp. 3546–3550. DOI: 10.1109/TAC.2016.2614889.
Ljung L. System Identification: Theory for the User. Prentice Hall, 1987.

ссылка на оригинал статьи https://habr.com/ru/articles/1043042/