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

Обучение в реальном времени, онлайн-обучение (англ. 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]

Переменная минимизации w предназначена для представления части системы обучения, которая должна быть адаптирована в качестве реакции на наблюдение событий [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 + betta[/math]. Целесообразно рассмотреть расширенный набор входных данных [math]x[/math], содержащий дополнительный постоянный коэффициент, равный 1. Смещение [math]betta[/math] тогда представляется как дополнительный коэффициент в векторе параметров [math]w[/math]. Тогда вывод порогового элемента имеет вид:

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

Перцептрон

Перцептрон Розенблатта состоит из фиксированной предварительной обработки и обучаемого порогового элемента

Метод k-средних

Метод k-средних отправляет заранее определенное количество центроидов кластера, чтобы минимизировать ошибку