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

Казвам се Павел Пархоменко, аз съм ML разработчик. В тази статия бих искал да ви разкажа за устройството на услугата Yandex Zen и да споделя техническите подобрения, които позволиха да се увеличи качеството на препоръките. От поста ще научите как за само няколко милисекунди да намерите сред милиони документи най-релевантните за потребителя; как да извършвате непрекъснато разлагане на голяма матрица (състояща се от милиони колони и десетки милиони редове), така че новите документи да получават своя вектор за десетки минути; как да преизползвате разлагането на матрицата потребител-статия, за да получите добро векторно представяне за видео.

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

• Да се разделят изчислителните задачи: всички тежки операции да се извършват офлайн, а в реално време да се прави само бързо прилагане на модели, за да се отговаря в рамките на 100-200 мс.
• Да се отчитат бързо действията на потребителя. За това е необходимо всички събития веднага да достигат до р recommending и да влияят на резултата от работата на моделите.
• Да се направи фийдът такъв, че за новите потребители той бързо да се адаптира към поведението им. Хората, които току-що са се присъединили към системата, трябва да усещат, че обратната им връзка влияе на препоръките.
• Бързо да се разбере кому да се препоръча нова статия.
• Оперативно да се реагира на постоянното появяване на ново съдържание. Десетки хиляди статии излизат всеки ден и много от тях имат ограничен срок на живот (например новини). В това се състои разликата им от филми, музика и друго дълготрайно и скъпо за създаване съдържание.
• Да се пренасят знания от една домейн област на друга. Ако в препоръчителната система има обучени модели за текстови статии и добавяме видео съдържание, можем да преизползваме съществуващите модели, за да се увеличи ранжирането на новия тип съдържание.

Ще разкажа как решихме тези задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пренос на друга домейн област

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

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

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

Заключение

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

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

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