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

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

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

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

Ще ви кажа как решихме тези проблеми.

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

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

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

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

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

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

ALS стъпка по време на изпълнение

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

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

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

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

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

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

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

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

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

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

Разпределено съвместно филтриране

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

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

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

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

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

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

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

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

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

Прехвърляне към друга зона на домейн

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

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

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

Заключение

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

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

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