Как работим върху качеството и скоростта на предлагане на препоръки

Меня зовут Павел Пархоменко, я ML-разработчик. В этой статье я хотел бы рассказать об устройстве сервиса Яндекс.Дзен и поделиться техническими улучшениями, внедрение которых позволило увеличить качество рекомендаций. Из поста вы узнаете, как всего за несколько миллисекунд находить среди миллионов документов наиболее релевантные для пользователя; как делать непрерывное разложение большой матрицы (состоящей из миллионов столбцов и десятков миллионов строк), чтобы новые документы получали свой вектор за десятки минут; как переиспользовать разложение матрицы пользователь-статья, чтобы получить хорошее векторное представление для видео.

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

• Разделить вычислительные задачи: все тяжелые операции делать в офлайне, а в реальном времени выполнять только быстрое применение моделей, чтобы отвечать за 100-200 мс.
• Быстро учитывать действия пользователя. Для этого необходимо, чтобы все события моментально доставлялись в рекоммендер и влияли на результат работы моделей.
• Сделать ленту такой, чтобы у новых пользователей она быстро подстраивалась под их поведение. Только что пришедшие в систему люди должны ощущать, что их фидбек влияет на рекомендации.
• Быстро понимать, кому порекомендовать новую статью.
• Оперативно реагировать на постоянное появление нового контента. Десятки тысяч статей выходят каждый день, и многие из них имеют ограниченный срок жизни (скажем, новости). В этом их отличие от фильмов, музыки и другого долгоживущего и дорогого для создания контента.
• Переносить знания с одной доменной области на другую. Если в рекомендательной системе есть обученные модели для текстовых статей и мы добавляем в нее видео, можно переиспользовать существующие модели, чтобы контент нового типа лучше ранжировался.

Я расскажу, как мы решали эти задачи.

Отбор кандидатов

Как за няколко милисекунди да намалим множество разглеждани документи хиляди пъти, практически без да влошим качеството на класирането?

Да предположим, че сме обучили много ML модели, генерирали сме на тяхна основа характеристики и сме обучили още една модел, която класира документите за потребителя. Всичко би било наред, но не можем просто така да вземем и изчислим всички характеристики за всички документи в реално време, ако тези документи са милиони, а препоръките трябва да се изградят за 100-200 мс. Задачата е да изберем от милиони подмножество, което ще бъде класирано за потребителя. Тази стъпка обикновено се нарича отбор на кандидати. Към него има няколко изисквания. Първо, отборът трябва да се извършва много бързо, за да остане колкото се може повече време за самото класиране. Второ, значително намалявайки броя на документите за класиране, трябва да запазим максимално релевантните за потребителя документи.

Нашият принцип за отбор на кандидати еволюционно се развиваше и в момента сме стигнали до многостепенна схема:

Първо, всички документи се разделят на групи и от всяка група се вземат най-популярните документи. Групите могат да бъдат сайтове, теми, клъстери. За всеки потребител на основание на неговата история се подбират най-близките му групи и вече от тях се вземат най-добрите документи. Също така използваме kNN индекс за подбиране на най-близките на потребителя документи в реално време. Съществуват няколко метода за изграждане на kNN индекс, при нас най-добре работи HNSW (Hierarchical Navigable Small World графове). Това е йерархичен модел, който позволява за няколко милисекунди да се намерят N най-близки вектори за потребителя от милионна база. Предварително индексираме цялата наша база документи офлайн. Тъй като търсенето в индекса работи доста бързо, при наличие на няколко силни ембеддинга можем да направим няколко индекса (по един индекс на всеки ембеддинг) и да се обръщаме към всеки от тях в реално време.

При нас остават десетки хиляди документа за всеки потребител. Това все още е много за броене на всички признаци, така че на този етап прилагаме леко класиране — значително опростена версия на тежкото класиране с по-малко признаци. Заветът е да предвидим кои документи ще бъдат в топа на тежката модел. Документите с най-висок предикт ще бъдат използвани в тежкия модел, тоест на последния етап на класирането. Този подход позволява в рамките на десетки милисекунди да се сведе числото на разглежданите от потребителя документи от милиони до хиляди.

Стъпка ALS в реално време

Как да се отчита обратната връзка на потребителя веднага след кликване?

Важно е времето на отговор на обратната връзка на потребителя. Това е особено важно за новите потребители: когато човек започне да използва системата за препоръки, той получава неперсонализиран поток от разнообразни по тематика документи. След като направи първия клик, е необходимо веднага да се вземе предвид това и да се настрои по неговите интереси. Ако изчисляваме всички фактори офлайн, бързата реакция на системата ще стане невъзможна поради забавяне. Затова е наложително да се обработват действията на потребителя в реално време. За тези цели използваме стъпка ALS в реално време за изграждане на векторно представяне на потребителя.

Да предположим, че за всички документи имаме векторно представяне. Например, можем офлайн на базата на текста на статията да изградим вграждания с помощта на ELMo, BERT или други модели на машинно обучение. Как можем да получим векторно представяне на потребителите в същото пространство на базата на тяхното взаимодействие в системата?

Общ принцип за формиране и разлагане на матрицата потребител-документНека имаме m потребители и n документа. За някои потребители е известно тяхното отношение към определени документи. Тази информация може да се представи под формата на матрица m x n: редовете съответстват на потребителите, а колоните — на документите. Тъй като повечето документи потребителят не е разглеждал, по-голямата част от клетките в матрицата ще останат празни, а другите ще бъдат запълнени. За всяко събитие (харесване, неодобрение, кликване) в матрицата е предвидена стойност — но нека разгледаме опростен модел, в който харесването съответства на 1, а неодобрението на -1.

Разделяме матрицата на две: P (m x d) и Q (d x n), където d е размерността на векторното представяне (обикновено малко число). Тогава на всеки обект ще съответства d-мерен вектор (за потребителя — ред в матрицата P, за документа — колона в матрицата Q). Тези вектори ще бъдат ембеддинги на съответните обекти. За да предскажем дали даден документ ще хареса на потребителя, можем просто да умножим техните ембеддинги.

Един от възможните начини за разлагане на матрицата е ALS (Alternating Least Squares). Ще оптимизираме следната функция на загуба:

Тук rui е взаимодействието на потребителя u с документа i, qi е векторът на документа i, pu е векторът на потребителя u.

Тогава оптималният вектор на потребителя (при фиксирани вектори на документите) се намира аналитично чрез решаване на съответната линейна регресия.

Това се нарича 'стъпка ALS'. А самият алгоритъм ALS се състои в това, че последователно фиксираме една от матриците (потребители и статии) и обновяваме другата, намирайки оптималното решение.

За щастие, намирането на векторното представяне на потребителя е доста бърза операция, която може да се извършва в реално време, използвайки векторни инструкции. Трихът позволява незабавно да се вземе предвид обратната връзка на потребителя в подреждането. Такъв същият ембеддинг може да се използва и в kNN индекса за подобряване на отбора на кандидатите.

Распределена колаборативна филтрация

Как да правим инкрементална разпределена матрична факторизация и бързо да намираме векторното представяне на новите статии?

Съдържанието не е единственият източник на сигналите за препоръки. Другият важен източник е колаборативната информация. Добри индикатори за класиране традиционно могат да бъдат получени от разлагането на матрицата потребител-документ. Но при опит за извършване на такова разлагане се сблъскахме с проблеми:

1. Имаме милиони документи и десетки милиони потребители. Матрицата не може да се побере на една машина и разлагането ще отнеме много време.
2. За по-голямата част от съдържанието в системата животът е кратък: документите остават актуални само за няколко часа. Затова е необходимо да изградим векторното им представяне възможно най-бързо.
3. Ако извършваме разлагане непосредствено след публикуване на документа, не е възможно да бъде оценен от достатъчен брой потребители. Следователно, векторното му представяне с голяма вероятност ще бъде не особено добро.
4. Ако потребителът е дал похвала или неодобрение, няма как веднага да вземем това предвид в разлагането.

За да решим посочените проблеми, реализирахме разпределено разлагане на матрицата потребител-документ с често инкрементално обновяване. Как точно работи това?

Предположим, че имаме клъстер от N машини (N се измерва на стотици) и искаме да направим разпределено разлагане на матрицата, която не може да се побере на една машина. Въпросът е – как да извършим това разлагане, така че, от една страна, на всяка машина да има достатъчно данни и, от друга страна, изчисленията да бъдат независими?

Ще използваме описания по-горе алгоритъм за разлагане ALS. Нека разгледаме как разпределено да извършим една стъпка от ALS – останалите стъпки ще бъдат сходни. Да предположим, че имаме фиксирана матрица на документите и искаме да изградим матрица на потребителите. За целта ще я разделим на N части по редове, всяка част ще съдържа приблизително равен брой редове. Ще изпратим на всяка машина непразните клетки на съответните редове, а също така и матрицата на вгражданията на документите (изцяло). Тъй като нейният размер не е много голям, а матрицата потребител-документ обикновено е силно разредена, тези данни ще се поберат на обикновена машина.

Тази стратегия може да се повтаря в продължение на няколко епохи, докато моделът достигне своята конвергенция, като последователно променяме фиксираната матрица. Но дори тогава, разлагането на матрицата може да отнеме няколко часа. И това не решава проблема с бързото получаване на вграждания на нови документи и обновяването на вгражданията на тези от тях, за които е имало малко информация при изграждането на модела.

На нас ни помогна внедряването на бързо инкрементално обновление на модела. Да предположим, че имаме текуща обучена модел. От момента на нейното обучение са се появили нови статии, с които нашите потребители са взаимодействали, както и статии, които по време на обучението са имали малко взаимодействия. За бързото получаване на вграждането на такива статии, ние използваме вгражданията на потребителите, получени по време на първото голямо обучение на модела, и правим една стъпка ALS, за да изчислим матрицата на документите, при фиксирана матрица на потребителите. Това позволява бързо получаване на вграждания — в рамките на няколко минути след публикуването на документа — и често обновяване на вгражданията на новите документи.

За да се вземат предвид действията на потребителя веднага при препоръките, в реално време не използваме вгражданията на потребителите, получени офлайн. Вместо това правим стъпка ALS и получаваме актуалния вектор на потребителя.

Прехвърляне на друга домейна област

Как да използваме обратната връзка от потребителя към текстовите статии, за да построим векторно представяне на видео?

Първоначално препоръчвахме само текстови статии, така че много от нашите алгоритми са насочени в тази посока. Но при добавянето на съдържание от друг тип се срещнахме с необходимостта от адаптация на моделите. Как решихме този проблем на примера на видео? Един от вариантите — да преобучим всички модели от нула. Но това отнема време, а част от алгоритмите са чувствителни към обема на обучителната извадка, която още няма в нужното количество за новия тип съдържание в първите моменти от живота му на услугата.

Ние поехахме по друг път и повторно използвахме текстови модели за видео. При създаването на векторни представления на видео ни помогна същият трик с ALS. Взехме векторното представление на потребителите, основавайки се на текстови статии, и направихме стъпка ALS, използвайки информация за прегледите на видеото. Така без усилие получихме векторно представление на видеото. А в реално време просто изчисляваме близостта между вектора на потребителя, получен на база текстови статии, и вектора на видеото.

Заключение

Разработването на ядрото на реалновременната препоръчителна система е свързано с множество задачи. Необходимо е бързо да се обработват данни и да се прилагат методи с машинно обучение за ефективно използване на тези данни; да се изграждат сложни разпределени системи, способни да обработват потребителски сигнали и ново съдържание за минимално време; и много други задачи.

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

Източник: habr.com