Подробное объяснение FTRL, алгоритма онлайн-обучения, широко используемого крупными компаниями.

Пожалуйста, укажите ссылку на эту статью для перепечатки: http://www.cnblogs.com/EE-NovRain/p/3810737.html

Логистическая регрессия (Logistic Regression) часто используется в онлайн-обучении и CTR, а традиционные пакетные (batch) алгоритмы не могут эффективно обрабатывать крупномасштабные наборы данных и онлайн-потоки данных.У Google есть три года (2010-2013 годы) от теоретического исследования до практическая инженерная реализацияFTRL (Следуй за регуляризованным лидером)Алгоритм имеет отличную производительность при решении задач выпуклой оптимизации с негладкими условиями регуляризации (такими как 1 норма, контроль сложности модели и разреженность), такими как логистическая регрессия.Сообщается, что крупные отечественные интернет-компании впервые.Применяется к фактический продукт, наша система также использует этот алгоритм. Вот некоторое введение в соответствующую историю разработки FTRL и некоторые руководящие принципы для инженерной реализации.Теоретические детали выпуклой оптимизации подробно не представлены.Если вам интересно, вы можете обратиться к соответствующему документу.Список связанных документов будет прикрепить в конце статьи. Машинное обучение не является моим профессиональным направлением в школе, но фундамент, накопленный в школе, не так уж и плох, и многое схоже, и я могу понять основной смысл, вникая в него. Конечно, если есть неточности, можно их обсудить и исправить.

Эта статья будет в основном представлена в трех частях.Если вас не интересует теоретическая основа, вы можете непосредственно взглянуть на инженерную реализацию третьей части (эта часть инженерной статьи в Google 13 очень подробная):

Соответствующая предыстория: включая общее описание проблемы, пакетный алгоритм, традиционный алгоритм онлайн-обучения и т. д.
Краткое введение в такие алгоритмы, как Truncated Gradient, FOBOS и RDA (Regularized Dual Averaging), которые тесно связаны с FTRL.
Теоретическая формула FTRL и инженерная реализация (если вас не интересуют предшественники и теоретические аспекты, вы можете непосредственно ознакомиться с частью инженерной реализации в этом разделе)

1. Связанный фон

【Описание проблемы】

Существуют две эквивалентные формы описания задачи оптимизации минимизации структурного риска функции потерь + регуляризация (логистическая регрессия также является этой формой), на примере 1 нормы, это:

A. Согласие мягкой регуляризации в неограниченной форме оптимизации:

B. Формулировка выпуклого ограничения с ограниченными элементами Формулировка выпуклого ограничения:

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

【Пакетный (пакетный) алгоритм】

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

А. Форма оптимизации без ограничений: 1. Глобальный градиентный спуск., очень часто используемый алгоритм, не буду вдаваться в подробности, находить глобальный градиент целевой функции на каждом шаге и итерировать с невозрастающей скоростью обучения, 2. метод Ньютона (касательная аппроксимация), LBFGS (секущая квази -Ньютон, используйте результаты предыдущей итерации. Аппроксимация, обратная матрице Гессе, BFGS, кажется, является аббревиатурой инициалов нескольких имен людей) и другие методы. Ньютоновские и квазиньютоновские методы обычно хорошо работают для гладких регулярных ограничений (таких как норма 2). модифицированный. Если вам интересно, вы можете проверить книги, связанные с численным расчетом безусловной оптимизации, Я не изучал соответствующие детали подробно, поэтому я не буду здесь на них останавливаться.

b. Форма выпуклой оптимизации с ограничением неравенства: 1. Традиционный алгоритм оптимизации с ограничением неравенства, метод внутренней точки и т. д. 2. Проецируемый градиентный спуск (при представлении оптимизации с ограничением), gt является субградиентным, интуитивное значение состоит в том, что после каждого шага итерации результат итерации может быть расположен в ограничении вне набора, а затем взять проекцию результата итерации на ограниченное выпуклое множество в качестве нового результата итерации (символ во второй формуле идентифицирует проекцию на X):

【Онлайн-алгоритм】

Как упоминалось выше, пакетный алгоритм имеет свои ограничения, а характеристики алгоритма онлайн-обучения таковы: для каждой обучающей выборки модель итерируется один раз с потерями и градиентом, генерируемыми выборкой, и обучение выполняется на данных. на основе данных, поэтому он может обрабатывать большие объемы данных и онлайн-обучение. Обычно используются онлайн-градиентный спуск (OGD) и стохастический градиентный спуск (SGD) и т. Д. Основная идея заключается в приведенном выше [Описании проблемы] вФункция потерь L(w, zi) несуммированных одиночных данных выполняет градиентный спуск,Поскольку направление каждого шага не является глобально оптимальным, общее представление будет выглядеть как случайный маршрут спуска. Типичная формула итерации выглядит следующим образом:

Здесь используются смешанные термины регуляризации:, например, может быть смесью 1-норм и 2-норм сильно выпуклых членов(Как вы увидите позже, многие из них представляют собой смешанные форматы регуляризации и имеют определенные интуитивные значения). В итерационной формуле: gt — это субградиент функции потерь (одноточечные потери, не суммированные), элемент, добавленный к gt, — это градиент второго элемента в термине гибридной регуляризации, а набор проекций C — это пространство ограничений (например, «Возможно, ограниченное пространство 1 нормы»), аналогично проецируемому градиентному спуску, представленному выше.

Преимущество метода градиентного спуска заключается в том, что точность действительно хорошая, но в соответствующей статье в основном упоминаются два момента:

1. Простой онлайн-градиентный спуск трудно создать действительно разреженное решение.Разреженность - очень важная вещь в машинном обучении.Особенно когда мы делаем инженерные приложения, разреженные функции значительно уменьшат память и сложность прогнозирования. Это на самом деле очень легко понять, грубо говоря, даже если добавить норму L1 (простой пример того, что норма L1 может вводить разреженные решения, можно найти во второй главе книги PRML, я также упоминал об этом в ppt из моего предыдущего блога. ), поскольку это операция с плавающей запятой, для обученного вектора w трудно получить абсолютный нуль. В этот момент вы можете сказать, что это непросто.Когда вычисленное значение соответствующей размерности w очень мало, мы можем принудительно обнулить его, и оно будет разреженным. Да на самом деле многие так и делают, последнее Усе И Gradient, и FOBOS являются приложениями схожих идей;

2. Будут некоторые проблемы с итерацией недифференцируемых точек.Какие конкретно проблемы?Есть статья, в которой говорится: итерации субградиентного метода очень редко бывают в точках недифференцируемости. Я долго читал и ничего не понял.Могут подсказать какие-нибудь знакомые ученики.

2. Усеченный градиент, FOBOS и RDA (регуляризованное двойное усреднение)

Как упоминалось выше, разреженность — очень важная вещь в машинном обучении.Вот три распространенных способа создания разреженных решений:

1), просто добавьте норму L1

– Ограничения Как упоминалось выше, два числа с плавающей запятой a+b не могут быть абсолютно равны нулю, что не может генерировать действительно разреженные веса признаков.2), обрезать по 1 норме, самая интуитивная и нетехническая идея, затем установите порог и обрежьте, чтобы обеспечить разреженность.Вы можете комбинировать метод простого усечения нормы L1, обрезать K данных для каждого онлайн-обучения и итеративные результаты OGD, каждые K шагов. усечение до нуля:

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

3), подходит оболочка черного ящика:– Метод черного ящика удаляет некоторые функции, а затем переобучает, чтобы увидеть, эффективны ли удаленные функции. – Необходимо много раз запускать алгоритм на наборе данных, поэтому это нецелесообразно.

Далее будут упомянуты FOBOS (метод Forward-Backward Splitting, на самом деле его следует называть FOBAS, исторические причины) и RDA, поскольку последний FTRL фактически эквивалентен объединению преимуществ этих двух алгоритмов:

а) Работа ФОБОС, Google и Беркли в 2009 году:

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

B, RDA (регуляризованное двойное усреднение), Microsoft 10 лет работы, который является более теоретическим, я пропущу его здесь и дам лишь краткое введение в его характеристики:

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

Хорошо, фон и некоторые предзнаменования наконец завершены, и основное внимание уделяется части FTRL ниже. . .

3. FTRL (Следуй за регуляризованным лидером)

【путь развития】

Теоретическое продвижение и инженерное применение FTRL в первую очередь следует поблагодарить этого человека: Х. Брендан МакМахан, этот приятель Google охранял яму в течение трех лет, пока в 2013 году не вышла инженерная статья. Процесс разработки и основное описание следующие:

– 10 лет теоретической работы, но явно не поддерживала итерацию термина регуляризации, 11 лет, чтобы доказать границу регрессии и введение общих терминов регуляризации, еще одна статья в 2011 году раскрыла связь между OGD, FOBOS, RDA и другими алгоритмами и FTRL; 13-летняя статья дала инженерную реализацию вместе с подробным псевдокодом и начала применяться в больших масштабах.

- можно рассматривать как смесь RDA и FOBOS, но FTRL более эффективен, чем первые два, при норме L1 или других условиях негладкой регуляризации[Основная идея и итеративная формула] Я просто нарисовал картинку:

Сравнение с итерационными формулами других онлайн-алгоритмов (на самом деле процесс перехода ОГД шаг за шагом к аналогичной форме итерационной формулы ограничен по времени, поэтому я не буду здесь вдаваться в подробности. Наконец, я прикреплю п.п. I сделал, когда сам делал шеринг сессию.Да можете скачать и посмотреть если интересно) разные способы есть в этой унифицированной форме описания, разница только в обработке второго и третьего пунктов:

- первый термин: градиент или кумулятивный градиент; - второй термин: обработка термина регуляризации L1; значение проксимального в проксимальном) или слишком далеко от 0 (центральный), этот пункт на самом деле нужен для небольшого сожаления 【Реализация проекта】Всех не интересует вышеописанная большая куча причин и следствий и формул, ок, не важно, гугл очень вдумчиво дал бумажку с сильным инжинирингом в 2013 году, на самом деле большинство компаний используют FTRL, им пофиг на все вышеперечисленное большой раздел вещей можно написать прямо по псевдокоду, настроить параметры и убедиться, что результаты очень хорошие. Это то, что наша компания делала в начале, ха-ха, но люди всегда должны быть немного любопытными, не так ли? Совершенно другое ощущение, когда вникаешь в причину и следствие и основную теоретическую формулу. Псевдокод покоординатного FTRL_Proximal при логистической регрессии выглядит следующим образом.На основе выражения формулы сделаны некоторые преобразования и приемы реализации.Подробности в статье.При реализации собственного можно распараллелить его на фактических данных Ускорение:

Настройка четырех параметров сочетается с указаниями в статье и повторными экспериментальными испытаниями, и вы можете найти набор параметров, подходящий для вашей собственной задачи. Здесь я хотел бы отметить, что упомянутые выше т.н.per-coordinate, что значитFTRL обновляется отдельно для каждого измерения w, и каждое измерение использует разную скорость обучения., который также является элементом перед lamda2 в приведенном выше коде. По сравнению с w, использующим одинаковую скорость обучения для всех измерений признаков,Этот метод учитывает неравномерность распределения самих обучающих выборок по разным признакам., если есть несколько обучающих выборок, содержащих функцию размерности w, и каждая выборка очень ценна, то скорость обучения, соответствующая размерности функции, может поддерживать относительно большое значение в одиночку, Градиент выборки - большой шаг вперед без необходимости соответствовать шагу вперед других размеров функции. [стратегия экономии памяти в инженерной реализации]Вот введение в некоторые детали реализации экономии памяти, упомянутые Google.

Экономия памяти во время Predict:

-L1 норма плюс стратегия, результат обучения w очень разреженный, экономия памяти при использовании w как прогноз, очень интуитивно понятно, в подробности вдаваться не буду.

Экономия памяти во время обучения:

Отбрасывая вероятностные включения функций, которые редко появляются в обучающих данных онлайн, но для онлайн-набора очень дорого предварительно обрабатывать все данные, чтобы увидеть, какие функции появляются редко, а какие бесполезны.Если вы хотите сделать разреженность, когда хотите чтобы тренироваться, нужно подумать о некоторых онлайн-методах (FTRL отдельно обновляется по w измерениям, разные размеры шага для каждого измерения, по координате)

1) Включение Пуассона: для обучающих выборок из определенного признака размерности примите и обновите модель с вероятностью p;

2) Включение фильтра Блума: используйте фильтр Блума, чтобы функция вероятностно появлялась k раз перед обновлением.

2. Перекодирование чисел с плавающей запятой

1) Веса признаков не нужно хранить в 32-битных или 64-битных числах с плавающей запятой, что тратит место в памяти 2) 16-битное кодирование, но обратите внимание на влияние технологии округления на сожаление 3. Обучите несколько подобных модели 1) Для одной и той же последовательности обучающих данных одновременно обучайте несколько похожих моделей 2) Эти модели имеют некоторые уникальные функции и некоторые общие функции 3) Отправная точка: некоторые измерения функций могут быть исключительными для каждой модели, а некоторые функции являются общими для каждую модель можно обучить с одними и теми же данными. 4. Single Value Structure (говорят, что некоторые компании уже сделали это на практике, и хороший AUC можно гарантировать даже при больших объемах данных) 1) Несколько моделей совместно используют хранилище признаков (например, поместите их в cbase или redis), и каждая модель обновляется Эта общая структура признаков 2) Для определенной модели, для определенного измерения вектора признаков, который он обучил, непосредственно вычислить итеративный результат и сделать среднее со старым значением 5. Использовать количество положительных и отрицательные образцы для вычисления суммы градиентов (все модели имеют одинаковые N и P)

6. Подвыборка обучающих данных 1) На практике CTR намного меньше 50%, поэтому положительные выборки более ценны. Путем подвыборки набора обучающих данных размер набора обучающих данных может быть значительно уменьшен. 2) Отбираются все положительные выборки (по крайней мере одно объявление щелкнуло по данным запроса), а отрицательные выборки отбираются с использованием отношения r (нет объявление нажимается на данные запроса вообще) данные). Однако обучение непосредственно на такой выборке приведет к относительно большому смещенному прогнозу.3) Решение: При обучении умножьте выборку на вес. Вес напрямую умножается на потери, поэтому градиент также умножается на этот вес.

Очень хорошей идеей будет сначала сделать выборку, чтобы уменьшить количество отрицательных выборок, а затем использовать веса для компенсации отрицательных выборок во время обучения.[Ссылки] Я примерно обозначил основное содержание каждой статьи. Если вам интересно, вы можете просмотреть его выборочно. Если вы сосредоточены только на реализации проекта, можно прочитать красный:

[1] Лэнгфорд Дж., Ли Л. и Чжан Т. Разреженное онлайн-обучение с помощью усеченного градиента, JMLR, 10, 2009 г. (статья об усеченном градиенте)

[2] Х. Б. МакМахан, Следование за регуляризованным лидером и зеркальный спуск: теоремы эквивалентности и регуляризация L1, В AISTATS, 2011 (статья, сравнивающая различные методы, такие как FOBOS, RDA, FTRL и т. д.)

[3] Л. Сяо, Метод двойного усреднения для регуляризованного стохастического обучения и онлайн-оптимизации, В NIPS, 2009 (метод RDA).

[4] Дучи Дж., Зингер Ю. Эффективное обучение с использованием расщепления вперед-назад, Достижения в системах обработки нейронной информации, 22, стр. 495–503, 2009 г. (метод FOBOS).

[5] H. Brendan McMahan, Gary Holt, D. Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, Sharat Chikkerur, Dan Liu, Martin Wattenberg, Arnar Mar Hrafnkelsson, Tom Boulos, Jeremy Kubica, Ad Click Prediction: a View from the Trenches, Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) (2013) (Это инженерная статья)

[6] Х. Брендан МакМахан. Объединенный анализ регуляризованного двойного усреднения и составного зеркального спуска с неявными обновлениями. Представлено, 2011 г. (развитие теории FTRL, граница сожаления и добавление общего условия регуляризации).

[7] Х. Брендан МакМахан и Мэтью Стритер, Оптимизация адаптивных границ для выпуклой онлайн-оптимизации, InCOLT, 2010 (теоретическая статья в начале)

PPT, который я сделал, когда я поделился в группе, прикреплен позже.Если вам интересно, вы можете взглянуть:pan.baidu.com/s/1eQvfo6e