Обзор алгоритмов сортировки

Современные рекомендательные системы обычно делятся на два этапа: отзыв и ранжирование. На этапе отзыва некоторые недорогие и быстрые модели обычно используются для предварительного отбора из сотен тысяч или миллионов наборов-кандидатов, оставляя тысячи или сотни рядов и, наконец, покидая топК.

Можно сказать, что за последние десять лет развитие модели ранжирования в отрасли стало скачком вперед. можно рассматривать как первую половину современной рекомендательной системы.

С 2015 года по настоящее время его можно рассматривать как вторую половину бурного развития.За несколько лет возникли сети глубокого обучения, представленные DNN и другими моделями, и одна за другой появились различные архитектуры моделей и пересечения признаков, и различные новые идеи. , уловка ослепительна, и глубокое обучение постепенно стало основным методом в области CTR и рекомендаций.

В этой статье мы кратко представим, разберем и обобщим эти модели ранжирования на этом пути.

Традиционная модель

1. LR

До появления глубокого обучения LR почти монополизировал ранние поля CTR и рекомендаций из-за своей простоты, скорости и хорошей интерпретируемости.

h_{\theta}(x)=\frac{1}{1+e^{-\theta^{T}x}}

Интуитивно понятно, что форма целевой функции модели LR представляет собой взвешенную сумму каждой функции, а затем сигмовидная функция используется для отображения результата в диапазоне от 0 до 1, чтобы выразить вероятность того, что пользователь щелкнет элемент, который равен простой и понятный, и может быть реализован параллельно высокая скорость.
Кроме того, наблюдая за изученными весами каждой функции, мы можем легко узнать, какие функции более «важны», а когда прогноз предвзят, мы также можем легко увидеть, какие факторы влияют на результаты. интерпретируемая веская причина.
Однако недостатки LR также очевидны: поскольку это простая линейная модель, она не может иметь дело с нелинейной взаимосвязью между функциями и целями, а функции не являются полностью независимыми, а перекрестное использование некоторых функций будет иметь особые эффекты. Поэтому, чтобы придать модели определенную нелинейность, специалистам по обработке и анализу данных в то время нужно было вручную выполнять множество функций, таких как дискретизация непрерывных функций, пересечение между функциями и т. д. Однако для извлечения эффективных кросс-функций необходимо полностью понимать данные и сценарии, трудозатраты высоки, и опытному инженеру сложно исчерпать все кросс-комбинации функций.

Поскольку это сложно сделать вручную, можем ли мы автоматически найти пересечение признаков или использовать для этого модель? В следующие несколько лет появились два метода автоматического пересечения признаков, представленные FM и GBDT.

2. FM/FFM

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

y(\mathbf{x}) = w_0+ \sum_{i=1}^n w_i x_i + \sum_{i=1}^n \sum_{j=i+1}^n w_{ij} x_i x_j

Из формулы видно, что модель пересекает все признаки попарно и присваивает веса всем комбинациям признаков.

Но есть две проблемы с этим методом грубой силы:

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

В ответ на две вышеупомянутые проблемы Штеффен Рендл из Констанцского университета в Германии предложил FM (машину факторизации) в 2010 году.

y(\mathbf{x}) = w_0+ \sum_{i=1}^n w_i x_i + \sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j

Подобно идее матричной факторизации (MF), FM изучает вектор скрытого веса для каждого признака, Когда признаки пересекаются, внутренний продукт двух скрытых векторов признаков используется в качестве веса перекрестного признака вместо одна функция Веса.

Вводя скрытый вектор признаков, исходныйКоличество весов для уровня было уменьшено до(скрытое векторное измерение, $n \gg k$ ). В процессе обучения за счет оптимизации процесса вычисления члена второго порядка сложность обучения ФМ может быть дополнительно снижена доуровне, что значительно снижает стоимость обучения.
И FM решает проблему разреженности данных в приведенной выше полиномиальной модели. Как видно из формулы, все содержат "ненулевых комбинационных признаков» (существует $j \neq i$ , так что $x_ix_j \neq 0$ ) образцы могут быть использованы для изучения скрытых векторов, что в значительной степени позволяет избежать влияния разреженности данных.
Кроме того, введение скрытых векторов также позволяет обобщить модель для включения комбинаций, которые никогда не появлялись ранее, принимая во внимание память и обобщение модели.
С инженерной точки зрения, FM также может обучаться с помощью градиентного спуска, что делает его гибким в режиме реального времени. По сравнению со сложной сетевой структурой модели глубокого обучения процесс вывода, который легче реализовать в FM, также избавляет его от проблемы обслуживания, и до сих пор он часто используется на этапе отзыва.

3. GBDT + LR

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

В 2014 году Facebook предложил модель дерева с каскадной структурой для решения этой проблемы.

Идея проста:

Сначала обучите модель GBDT, каждое дерево расположено сверху вниз, и разделение каждого узла является естественным процессом выбора признаков, а несколько слоев естественным образом объединяются для эффективных комбинаций признаков, так что каждый конечный узел соответствует дереву. представляет собой перекрестную комбинацию различных функций, так что все листовые узлы могут быть позже пронумерованы как новые функции, а затем объединены с исходными функциями, введите LR для обучения окончательной модели.

Комбинация признаков древовидной модели не может быть ограничена пересечением 2-го порядка, как FM: например, глубина каждого дерева равна 5, затем через 4 разделения узлов конечный листовой узел фактически является результатом признака 4-го порядка. комбинация. Однако нельзя сказать, что GBDT лучше, чем FM, потому что древовидная модель также имеет свои недостатки, такие как легкое переоснащение многомерных разреженных данных, например, невозможность распараллеливания и замедление, например, плохое обобщение и т. д.

Но важное значение GBDT+LR заключается в том, что

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

резюме

От самой ранней ручной сортировки по правилам до модели LR для ручного комбинирования признаков, до модели FM для автоматического комбинирования признаков второго порядка и до LR+GBDT для автоматического комбинирования признаков высокого порядка позже, это в основном ранняя система сортировки рекомендаций. основная жила модели.

Позже введение модели DNN ознаменовало появление модели ранжирования на основе глубокого обучения. Чистая простая модель DNN фактически основана на функции Embedded модели FM, добавляя скрытый слой MLP для выполнения неявной и нелинейной автоматической комбинации функций.

Ниже мы сосредоточимся на моделях глубокого обучения, которые доминировали в последние годы.

2. Глубокая модель

После 2015 года постепенно появился ряд моделей глубокого обучения, представленных DNN, лично я считаю, что их можно разделить на две категории:

Серия моделей, представленная Wide&Deep, их общая черта в том, что они автоматически учатся комбинировать новые признаки высокого порядка из исходных признаков, а их отличие в том, что широкая часть или глубокая часть изменены частично.
Модели совместного обучения, основанные на многозадачном обучении, представлены такими моделями, как ESMM и MMOE.

1. Модель класса Wide&Deep

Этот тип модели характеризуется двухбашенной структурой, то есть неглубокая модель (широкая часть), представленная LR, используется для обучения выражению низкоуровневых признаков, подчеркивая «память», другая сторона представлена MLP. Модель (глубокая часть) делает акцент на «обобщении», и структуру глубокой части также можно разделить на следующие модули:

raw input->embedding: процесс отображения разреженных объектов в низкоразмерные плотные векторы вложения.
input_layer: на этом уровне обычно выполняются некоторые операции агрегирования при встраивании каждой функции.
input_layer->output: Обычно полносвязный фреймворк из нескольких слоев MLP подключается к softmax в качестве выходного слоя.

Отличие большинства моделей в глубокой части только в том, чтоinput_layerВ этой части разные модели находятся на пути пересечения (неявные/явные, на уровне элемента/вектора) или на способе связи между функциями (конкатенация/взвешенная сумма/продукт/BI-взаимодействие/внимание и т. д.). или показать пересечение функций Порядок (второй порядок/более высокий порядок) будет другим.В качестве примеров мы рассмотрим Wide&Deep, (x)DeepFM, DCN и DIN, эти модели будут кратко представлены ниже.

Вот краткое введение в способ взаимодействия функций:

Один из методов похож на MLP.Из-за своей особой структуры он, естественно, имеет возможность изучать комбинации признаков высокого порядка и вводит определенную нелинейность, но что касается того, как происходит комбинация взаимодействий и сколько порядков возникает крестов, Нам не ясно, и это моделирование побитовое, а это значит, что элементы в векторе встраивания, соответствующие одному и тому же домену, также будут влиять друг на друга. Следовательно, мы говорим, что этот способ пересечения признаков является «неявным, поэлементным».
Другой соответствующий метод похож на DeepFM и xDeepFM, В структуре модели некоторые подсети или подструктуры явно предназначены для характеристики любой комбинации функций высокого порядка. Взяв в качестве примера FM, он предназначен для явного моделирования комбинации признаков второго порядка на векторном уровне, который мы называем «явным векторным уровнем».

Wide&Deep

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

DeepFM

Платформа Wide&Deep является мощной, но, поскольку широкая часть является моделью LR, по-прежнему требуется ручная разработка функций. В модели DeepFM широкая часть заменена на FM, которая может автоматически выполнять пересечение признаков второго порядка. Но он также ограничен тем, что есть кроссоверы только второго порядка и нет кроссоверов более высокого порядка.
FM и глубокая части имеют общий слой внедрения, а весовая матрица обновляется на двусторонней основе. Эта идея долевого дна также распространена в последней модели.

DCN

Если вы хотите получить какую-либо кросс-комбинацию функций высокого порядка, а не только второго порядка, но и избежать размерной катастрофы комбинационного взрыва, параметры сети слишком велики для изучения, и также будет много недействительных кросс-функции.Разработайте сетевую структуру, обладающую способностью «сжимать» и достаточно эффективную. DCN является одним из них:

Векторный кроссовер выглядит следующим образом:

На основе сохранения структуры MLP дополнительно вводится межуровневая сеть.Теоретически может быть выражена любая комбинация высокого порядка, в то время как каждый слой сохраняет комбинацию младшего.Векторизация параметров и уникальная структура сети также определяют сложность модели.Степень растет линейно, так что нет размерного взрыва с увеличением порядка кроссовера.
Однако в документе xDeepFM указано, что пересечение признаков DCN ограничено специальной формой и также построено побитовым способом.

xDeepFM

Модель xDeepFM представляет собой ансамбль, который автоматически создает кросс-функции и может обучаться сквозным образом.Он эффективно решает проблемы, упомянутые в DCN, реализует автоматическое обучение явных взаимодействий признаков высокого порядка и позволяет взаимодействиям происходить на векторном уровне. .

Модель создает уникальную структуру CIN, которая извлекает пересечение признаков с помощью таких операций, как внешнее произведение и свертка.

И порядок пересечения признаков можно явно контролировать, контролируя количество слоев CIN, а пространственно-временная сложность расчета растет линейно, без ситуации, когда взрыв комбинации приводит к взрыву параметра и не может быть обучен.

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

DIN

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

резюме

2. Модель многозадачного класса

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

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

Здесь в основном представлены две модели, ESMM и MMOE.

ESMM

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

Образец пространства показан ниже:

Традиционные задачи CVR рассматривают только процесс от просмотра до преобразования, т.е.

Эта модель также учитывает процесс кликов и вводит понятие коэффициента конверсии просмотра (pCTCVR), который представляет собой вероятность как клика, так и конверсии в условиях просмотра, а именно

p(conversion=1,click=1|impression) = p(click=1|impression) * p(conversion=1|click=1, impression)

Это следующая формула:

Модель, построенная по этой формуле, выглядит следующим образом:

Две задачи совместно используют базовое встраивание, а затем умножают соответствующий логит, чтобы соответствовать процессу pCTCVR.

Сборка образца такова:

Задача	положительный образец	отрицательный образец
pCTR	нажмите	не нажал
pCTCVR	нажмите и конвертируйте	Не преобразовано

Особенности модели:

Моделирование в пространстве полной выборки позволяет избежать проблемы «предвзятости выбора выборки» и в полной мере использует бизнес-данные.
Поделитесь базовым вектором встраивания, потому что коэффициент конверсии в рекомендации очень низкий, а соответствующие данные очень малы.Этот механизм совместного представления признаков позволяет сети CVR обновлять вектор встраивания из образцов, которые только выставлены, но не нажаты, что способствует облегчению обучения CVR.проблема разреженных данных.
Подсеть в ESMM может не ограничиваться MLP в этой статье и может быть заменена другими моделями по желанию, что означает, что эта статья предоставляет нам масштабируемую многозадачную архитектуру модели. Есть еще одна статья после АлиБумага следует аналогичной схеме.

MMOE

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

Поэтому в данной работе предлагаются две структуры на основе OMOE на рисунке (b) и MMOE на рисунке (c).Основная идея состоит в том, что каждая задача имеет независимую экспертную промежуточную сеть, аналогичную функции «переключатель». обучение, разное. Задача может извлекать признаки с разными акцентами из одного и того же базового встраивания, вместо того, чтобы полностью разделять базовый слой, то есть добиваться эффекта «бери то, что тебе нужно», что чем-то похоже на сеть внимания, упомянутую выше .

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

резюме

Хотя многозадачная модель рекомендательной системы является основной тенденцией развития модели ранжирования, сложность многоцелевого обучения заключается в том, что соотношение выборок для каждой цели различно, как интегрировать потери во время обучения, когда прекращать обучение, и онлайн-цели.Как комбинировать результаты A/B-тестирования, как измерить общий эффект A/B-тестирования и т. д., все это должно подвергаться более сложным измерениям и рассмотрениям, и в них все еще есть много места для развитие, и мы должны попробовать.

Практика сортировки модели в перцовом прямом эфире

За последние два года Zanthoxylum Live внимательно следил за отраслевой тенденцией и предпринимал различные попытки на этапе сортировки, такие как (GBDT+)LR, Wide&Deep, (x)DeepFM, DIN, ESMM, MMOE и т. д. Далее в качестве примера используется модель Wide&Deep, чтобы кратко представить всю нашу систему сортировки.

Первая — автономная часть, мы в основном используем spark/hdfs для обработки и хранения данных. В основном это пользовательские данные, якорные данные, данные в реальном времени, поведенческие последовательности и т. д. Вот некоторые из функций, которые мы использовали:

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

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

После этого набор меток и портрет объединяются, чтобы сформировать набор данных за один день.Обучающий набор за несколько дней можно использовать для формирования окончательного общего набора данных, чтобы удовлетворить требования объема данных и охвата.Будьте осторожны, чтобы не проникновение данных. Окончательный набор данных имеет уровень T и хранится в HDFS. На этапе обучения конфигурация одной машины с несколькими картами не может соответствовать требованиям к скорости, поэтому мы приняли частное облако 360.hboxРаспределенная обучающая платформа для ежедневного глубокого обучения модели.

Вот схема структуры нашей модели:

Вот эффект некоторых наших моделей:

не в сети:

Модель	`AUC*100`
FM	78.9
Wide&Deep	84.5
DeepFM	84.7

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

постскриптум

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

И следует отметить, что нет «лучшей модели», есть «наиболее подходящая модель», это не значит, что чем навороченее и сложнее модель, тем лучше будет онлайн-эффект. Например, Али предложил модель DIN, потому что инженеры впервые обнаружили это явление в данных:

Интересы, проявляемые пользователями в процессе просмотра веб-сайтов электронной коммерции, очень разнообразны, и только часть исторических данных будет влиять на то, был ли нажат рекомендуемый элемент, а не все исторические записи, то есть «мультимодальное распространение», «Частично активированный ".

Именно потребность в этом конкретном сценарии заставляет Alibaba разрабатывать модель DIN, чтобы отразить эволюцию интересов пользователей и добиться прорывных результатов.

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