Обучение в реальном времени

Обучение в реальном времени, онлайн-обучение (англ. online machine learning) — вид машинного обучения, при котором данные поступают в последовательном порядке и используются для обновления лучшего предсказания на каждом шаге.

Разница между пакетным и онлайн-обучением

Общая информация

Классификация методов онлайн-обучения

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

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

В зависимости от типа обратной связи существующие методы онлайн-обучения можно разделить на три группы:

• Онлайн-обучение с учителем (англ. supervised online learning)
• Онлайн-обучение с частичным привлечением учителя (англ. online learning with limited feedback)
• Онлайн-обучение без учителя (англ. unsupervised online learning)

Математическая основа

Функция ожидаемого риска (англ. Expected Risk Function)

Цель системы обучения состоит в поиске минимума функции [math]J(w)[/math], называемой функцией ожидаемого риска.

[math]J(w) \stackrel{\triangle}{=} E_z\ Q(z,w) \stackrel{\triangle}{=} \int Q(z,w)\,\mathrm{d}P(z) [/math]

Переменная минимизации [math]w[/math] предназначена для представления части системы обучения, которая должна быть адаптирована в качестве реакции на наблюдение событий [math]z[/math], происходящих в реальном мире. Функция потерь [math]Q(z, w)[/math] измеряет производительность системы обучения с параметром [math]w[/math] при обстоятельствах, описанных событием [math]z[/math].

События [math]z[/math] моделируются как случайные независимые наблюдения, взятые из неизвестного распределения вероятности [math]\mathrm{d}P(z)[/math]. Функция риска [math]J(w)[/math] - это ожидание функции потерь [math]Q(z, w)[/math] для фиксированного значения параметра [math]w[/math].

Функция ожидаемого риска [math]J(w)[/math] не может быть минимизирована напрямую, потому что распределение [math]\mathrm{d}P(z)[/math] неизвестно. Однако возможно вычислить приближение [math]J(w)[/math], используя конечный обучающий набор независимых наблюдений [math]z_1, ... , z_L[/math].

[math] J (w) \thickapprox \hat{J_L}(w) \stackrel{\triangle}{=} \frac{1}{L} \sum_{n=1}^L Q(z_n,w) [/math]

Пакетный градиентный спуск (англ. Batch Gradient Descent)

Пакетный градиентный спуск

Минимизировать эмпирический риск [math]\hat{J_L}(w)[/math] можно с помощью алгоритма пакетного градиентного спуска. Последовательные оценки [math]w_t[/math] оптимального параметра вычисляются по следующей формуле, где [math]\gamma_t[/math] - положительное число:

[math] w_{t+1} = w_t - \gamma_t \bigtriangledown_w \hat{J_L}(w_t) = w_t - \gamma_t\ \frac{1}{L} \sum_{i=1}^L \bigtriangledown_w\ Q(z_i,w_t)\ [/math]

Когда скорость обучения [math]\gamma_t[/math] достаточно мала, алгоритм сходится к локальному минимуму эмпирического риска [math]\hat{J_L}(w)[/math]. Значительное ускорение сходимости может быть достигнуто путем замены скорости обучения [math]\gamma_t[/math] подходящей положительно определенной матрицей.

Каждая итерация алгоритма пакетного градиентного спуска включает в себя вычисление среднего значения градиентов функции потерь [math]\bigtriangledown_w Q(z_n,w)[/math] по всей обучающей выборке. Для хранения достаточно большой обучающей выборки и вычисления этого среднего должны быть выделены значительные вычислительные ресурсы и память.

Градиентный спуск в реальном времени (англ. Online Gradient Descent)

Градиентный спуск в реальном времени

Алгоритм градиентного спуска в реальном времени получается при удалении операции усреднения в алгоритме пакетного градиентного спуска. Вместо усреднения градиента потерь по всей обучающей выборке каждая итерация градиентного спуска в реальном времени состоит из случайного выбора примера [math]z_t[/math] и обновления параметра [math]w_t[/math] в соответствии со следующей формулой:

[math] w_{t+1} = w_t - \gamma_t \bigtriangledown_w Q(z_t, w_t) \ [/math]

Усреднение этого обновления по всем возможным вариантам обучающего примера [math]z_t[/math] позволяет восстановить алгоритм пакетного градиентного спуска. Упрощение градиентного спуска в реальном времени основано на предположении, что случайный шум, вносимый этой процедурой, не будет мешать усредненному поведению алгоритма. Эмпирические данные подтверждают это предположение.

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

Общий алгоритм градиентного спуска в реальном времени используется для минимизации следующей функции стоимости [math]C(w)[/math]:

[math] C(w) \stackrel{\triangle}{=} E_z Q(z,w) \stackrel{\triangle}{=} \int Q(z, w)\,\mathrm{d}P(z)\ [/math]

Каждая итерация этого алгоритма состоит из извлечения события [math]z_t[/math] из распределения [math]\mathrm{d}P(z)[/math] и применения следующей формулы обновления, где [math]\gamma_t[/math] - либо положительное число, либо положительно определенная матрица:

[math] w_{t+1} = w_t - \gamma_t H(z_t, w_t) \ [/math]

[math]H(z, w)[/math] удовлетворяет следующему условию:

[math] E_z H(z, w) = \bigtriangledown_w C(w) \ [/math]

Примеры

Adaline

Adaline

Алгоритм обучения Adaline подбирает параметры одного порогового элемента. Входные данные [math]x[/math] распознаются как класс [math]y = +1[/math] или [math]y = −1[/math] в зависимости от знака [math]w' x + \beta[/math]. Целесообразно рассмотреть расширенный набор входных данных [math]x[/math], содержащий дополнительный постоянный коэффициент, равный 1. Смещение [math]\beta[/math] тогда представляется как дополнительный коэффициент в векторе параметров [math]w[/math]. Тогда вывод порогового элемента имеет вид:

[math]\hat{y_w}(x) \stackrel{\triangle}{=} sign(w' x) = sign \sum_{i} w_i x_i \ [/math]

Параметр [math]w[/math] корректируется после использования дельта-правила:

[math]w_{t+1} = w_t\ + \gamma_t(y_t - w'_t x_t) x_t \ [/math]

Дельта-правило - это итерация алгоритма градиентного спуска в реальном времени со следующей функцией потерь, где [math]z = (x, y)[/math]:

[math]Q_{adaline}(z, w) \stackrel{\triangle}{=} (y - w'x)^2\ [/math]

Многослойные сети (англ. Multi-Layer Networks)

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

Разрыв порогового элемента может быть представлен плавным нелинейным приближением:

[math]sign(w'x) \thickapprox tanh (w' x) \ [/math]

Использование таких сигмоидальных элементов не уменьшает вычислительные возможности многослойной сети.

Многослойная сеть сигмоидальных элементов реализует дифференцируемую функцию [math]f(x, w)[/math] от входных данных [math]x[/math] и параметров [math]w[/math]. Алгоритм обратного распространения ошибки обеспечивает эффективный способ вычисления градиентов функции среднего квадрата потерь.

[math]Q_{mse}(z, w) = \frac{1}{2}(y - f(x, w))^2 \ [/math]

K-Means

K-Means

Алгоритм K-Means можно получить, выполнив градиентный спуск в реальном времени со следующей функцией потерь:

[math]Q_{kmeans}(x, w) \stackrel{\triangle}{=} \stackrel{K}{\min_{k = 1}}(x - w(k))^2\ [/math]

Эта функция потерь измеряет ошибку в положении точки [math]x[/math], когда мы заменяем ее ближайшим центроидом, и удовлетворяет следующему условию:

[math] \forall z, \forall \upsilon \in \vartheta (w), \mid Q(z, \upsilon) - Q(z, w)\mid \le \mid w - \upsilon \mid \Phi(z, w) \ [/math]

Поэтому можно игнорировать недифференцируемые точки и применять алгоритм градиентного спуска в реальном времени.

[math] w_{t+1}^- = w_t^- + \gamma_t(x_t - w_t) \ [/math]

См. также

• Обучение с частичным привлечением учителя
• Активное обучение
• Обучение с подкреплением
• Глубокое обучение

Источники информации 

• Steven C. H. Hoi, Doyen Sahoo, Jing Lu, and Peilin Zhao. Online Learning: A Comprehensive Survey. 2018
• Leon Bottou. Online Learning and Stochastic Approximations. 1998
• Introduction to Online Machine Learning: Simplified