Мене звуть Павло Пархоменко, я ML-розробник. У цій статті я хотів би розповісти про влаштування сервісу Яндекс.Дзен та поділитися технічними покращеннями, впровадження яких дозволило збільшити якість рекомендацій. З поста ви дізнаєтеся, як всього за кілька мілісекунд знаходити серед мільйонів документів найбільш релевантні для користувача; як робити безперервне розкладання великої матриці (що складається з мільйонів стовпців та десятків мільйонів рядків), щоб нові документи отримували свій вектор за десятки хвилин; як перевикористовувати розкладання матриці користувач-стаття, щоб отримати хорошу векторну виставу для відео.
Наша рекомендаційна база містить мільйони документів різного формату: текстові статті, створені на нашій платформі та взяті із зовнішніх сайтів, відео, наративи та короткі пости. Розвиток подібного сервісу пов'язаний із великою кількістю технічних викликів. Ось деякі з них:
- Розділити обчислювальні завдання: всі тяжкі операції робити в офлайні, а в реальному часі виконувати тільки швидке застосування моделей, щоб відповідати за 100-200 мс.
- Швидко враховувати дії користувача. Для цього необхідно, щоб усі події миттєво доставлялися до рекоммендера та впливали на результат роботи моделей.
- Зробити стрічку такою, щоб у нових користувачів вона швидко підлаштовувалась під їхню поведінку. Люди, які щойно прийшли в систему, повинні відчувати, що їх фідбек впливає на рекомендації.
- Швидко розуміти, кому порадити нову статтю.
- Оперативно реагувати на постійну появу нового контенту. Десятки тисяч статей виходять щодня, і багато хто з них має обмежений термін життя (скажімо, новини). У цьому їхня відмінність від фільмів, музики та іншого довгоживучого та дорогого для створення контенту.
- Переносити знання з однієї доменної області в іншу. Якщо у рекомендаційній системі є навчені моделі для текстових статей і ми додаємо до неї відео, можна перевикористовувати існуючі моделі, щоб контент нового типу краще ранжувався.
Я розповім, як ми вирішували ці завдання.
Відбір кандидатів
Як за кілька мілісекунд скоротити безліч документів, що розглядаються в тисячі разів, практично не погіршивши якість ранжирування?
Припустимо, ми навчили багато ML-моделей, згенерували на їх основі ознаки та навчили ще одну модель, яка ранжує документи для користувача. Все б добре, але не можна просто так взяти і порахувати всі ознаки для всіх документів у реальному часі, якщо ці документи мільйони, а рекомендації потрібно будувати за 100-200 мс. Завдання - вибрати з мільйонів якесь підмножина, яке і ранжуватиметься для користувача. Цей етап зазвичай називають відбором кандидатів. До нього висувається кілька вимог. По-перше, відбір повинен відбуватися дуже швидко, щоб на ранжування залишалося якомога більше часу. По-друге, сильно скоротивши кількість документів для ранжирування, ми маємо максимально повно зберегти релевантні для користувача документи.
Наш принцип відбору кандидатів еволюційно розвивався, і на даний момент ми дійшли багатоступінчастої схеми:
Спочатку всі документи розбиваються на групи, і з кожної групи беруться найпопулярніші документи. Групами можуть бути сайти, теми, кластери. Для кожного користувача на основі його історії підбираються найближчі йому групи і вже з них беруться найкращі документи. Також ми використовуємо kNN-індекс для підбору найближчих користувачеві документів у реальному часі. Існує кілька методів побудови kNN-індексу, у нас найкраще заробив (Hierarchical Navigable Small World graphs). Це ієрархічна модель, що дозволяє за кілька мілісекунд знаходити N найближчих векторів для користувача з мільйонної бази. Попередньо ми в офлайні індексуємо всю базу документів. Оскільки пошук в індексі працює досить швидко, то за наявності кількох сильних ембеддингів можна зробити кілька індексів (по одному індексу на кожен ембеддинг) і звертатися до кожного з них у реальному часі.
У нас залишаються десятки тисяч документів для кожного користувача. Це, як і раніше, багато для підрахунку всіх ознак, тому на цьому етапі ми застосовуємо легке ранжування — полегшену модель важкого ранжування з меншою кількістю ознак. Завдання — передбачити, які документи будуть мати важку модель у топі. Документи з найбільшим предиктом буде використано у важкій моделі, тобто на останньому етапі ранжирування. Цей підхід дозволяє за десятки мілісекунд скоротити базу документів, що розглядаються для користувача, з мільйонів до тисяч.
Крок ALS у рантаймі
Як враховувати фідбек користувача відразу після натискання?
Важливий фактор у рекомендаціях – час відгуку на фідбек користувача. Це особливо важливо для нових користувачів: коли людина тільки-но починає користуватися рекомендаційною системою, вона отримує неперсоналізовану стрічку різноманітних за тематикою документів. Як тільки він робить перший клік, необхідно відразу врахувати це і підлаштуватися під його інтереси. Якщо обчислювати всі фактори в офлайні, швидка реакція системи стане неможливою через затримку. Отже, необхідно в реальному часі обробляти дії користувача. Для цього ми використовуємо крок ALS в рантаймі для побудови векторного представлення користувача.
Припустимо, для всіх документів ми маємо векторну виставу. Наприклад, ми можемо в офлайні на основі тексту статті побудувати ембеддінги за допомогою ELMo, BERT або інших моделей машинного навчання. Як можна отримати векторне подання користувачів у цьому ж просторі на основі їхньої взаємодії в системі?
Загальний принцип формування та розкладання матриці користувач-документНехай у нас є m користувачів та n документів. Для деяких користувачів відоме їхнє ставлення до деяких документів. Тоді цю інформацію можна подати у вигляді матриці mxn: рядки відповідають користувачам, а стовпці документам. Оскільки більшість документів людина не бачила, то більшість клітин матриці залишаться порожніми, а інші будуть заповнені. Для кожної події (лайка, дизлайка, кліка) у матриці передбачено якесь значення – але розглянемо спрощену модель, в якій лайку відповідає 1, а дизлайку –1.
Розкладемо матрицю на дві: P (mxd) і Q (dxn), де 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, використовуючи інформацію про перегляд відео. Так ми легко отримали векторне представлення відео. А в рантаймі ми просто обчислюємо близькість між вектором користувача, отриманим на основі текстових статей, та вектором відео.
Висновок
Розробка ядра реалтаймової рекомендаційної системи пов'язана з безліччю завдань. Потрібно швидко обробляти дані та застосовувати ML-методи для ефективного використання цих даних; будувати складні розподілені системи, здатні за мінімальний час обробляти користувацькі сигнали та нові одиниці контенту; та багато інших завдань.
У поточній системі, пристрій якої я описав, якість рекомендацій для користувача зростає разом із його активністю та тривалістю перебування на сервісі. Але звичайно, тут криється і головна складність: системі важко відразу зрозуміти інтереси людини, яка мало взаємодіяла з контентом. Покращення рекомендацій для нових користувачів – наше ключове завдання. Ми продовжимо оптимізувати алгоритми, щоб релевантний людині контент швидше потрапляв до його стрічки, а нерелевантний не показувався.
Джерело: habr.com