Мяне клічуць Павел Пархоменка, я 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