Персоналізований агрегований пошук. доповідь Яндексу

Ми підготували для вас адаптований переклад доповіді Яндексу (Personalizing Aggregated Search), представлений у квітні на конференції ECIR-2014 (Амстердам). У доповіді йдеться про те, наскільки корисне використання персоналізованих характеристик для поліпшення якості агрегованого пошукового ранжирування.

Автори дослідження: Станіслав Макєєв (stasd07@yandex-team.ru), Андрій Плахов (finder@yandex-team.ru), Павло Сердюков (pavse@yandex-team.ru).

1. ВСТУП
Сучасні пошукові системи часто надають доступ до спеціалізованих пошукових сервісів або вертикальногоу пошуку, що дозволяє інтернет-користувачам отримати результати різного формату (Картинки, Відео) або такі, що стосуються певної сфери (Новини, Погода). Втім, за деякими запитам результати вертикального пошуку можуть бути включені в стандартну пошукову видачу. Останнім часом це стає все більш звичною практикою провідних пошукових систем, і саме такий підхід, як правило, називають агрегованим (або інтегрованим) пошуком.

Основні переваги такого підходу наступні:

Перше – у користувача є можливість отримати релевантні результати певного типу безпосередньо на сторінці результатів пошуку (SERP).
Друге – на одній сторінці результатів надається велика різноманітність інформації самого різного типу, що особливо важливо під час роботи з пошуковими запитами, які не дають чіткого уявлення про те, що саме необхідно користувачу.

Обидві ці переваги можна спостерігати на скріншоті (див. Нижче). Ось як виглядає сторінка результатів пошуку за запитом « Metallica ». Зверніть увагу, що поряд з традиційною текстовою видачею тут присутні результати вертикального пошуку (Відео, Фото).

Наскільки нам відомо, жодна з попередніх робіт не була присвячена оцінці цінності індивідуальної релевантності вертикальних результатів пошуку для кожного конкретного користувача. У своїй роботі ми пропонуємо витягти подібну інформацію з журналу історії пошукових запитів користувача і використовувати її для формування різних варіантів агрегованого вертикального пошуку.

 Мал.1. SERP з результатами вертикального пошуку Картинки і Відео

Головна цінність даної роботи полягає в наступному:

• Новаторська робота по персоналізованому агрегованому пошуку.
• Містить в собі персоналізовану функцію машинного осмислення ранжирування вертикалей, яка значно покращує показники стандартного ранжирування вертикалей.
• Пропонується три класи персоналізованих характеристик, які повинні поліпшити ранжування вертикалей, а також дається порівняльний аналіз їх впливу.
• Оцінка впливу персоналізованого методу на якість вертикального ранжирування для різних типів пошукових запитів і користувачів.

2. РОБОТИ ЗІ СХОЖОЇ ТЕМАТИКИ

Хотілося б відзначити, що всі ці роботи розглядалися окремо або в контексті персоналізованого веб-пошуку, або в контексті агрегованого пошуку. І жодна з попередніх робіт не досліджувала цінність персоналізованих даних в контексті агрегованого пошуку. У підрозділі №2.1 можна знайти інформацію про деякі загальні підходи у вирішенні проблеми ранжирування вертикальних результатів пошуку, а в підрозділі №2.2 дається короткий огляд робіт, присвячених персоналізації пошукових результатів.

2.1.  Вибір вертикалей
Одними з найбільш складних речей в агрегованому пошуку є визначення релевантних вертикалей до призначеного для користувача пошукового запиту і розміщення відповідних результатів належним чином на сторінці результатів пошуку (SERP). Традиційно ця проблема вирішується за рахунок навчання моделі машинного осмислення на основі характеристик, які повинні визначати вертикальну релевантність до запиту. У цьому розділі ми б хотіли привести огляд таких характеристик.
Класифікація носить досить умовний характер, тому що деякі характеристики можуть бути одночасно віднесені до різних груп.

Дані запитів [1,2,11,12]. Характеристики цього типу надають деяку інформацію про вертикальну релевантності за рахунок використання лише тексту запиту.
Один з найбільш поширених підходів до цієї проблеми полягає в вимірі ймовірності запиту, заданого вертикальними моделями мови. Ці моделі, як правило, базуються на вертикальних документах або запитах, для яких вертикаль була останнім місцем, куди клікнув користувач.
Цей тип включає в себе також кілька простих характеристик, що базуються на тексті запиту, наприклад, таких, як: довжина запиту, запити, що складаються з регулярних виразів і т.д.

Дані вертикалі [1,2,11,12]. Зазвичай вертикаль нараховує бали, які оцінюють актуальність за запитом, що базується на властивостях своєї індексованої колекції документів.
Наприклад, для текстових колекцій передбачені такі характеристики, як текстова релевантність або текстова схожість між пошуковим запитом і документами, що знаходяться в топі видачі.

Дані по переходам. Ці характеристики базуються на пошуковій поведінковій історії користувача, включають у себе дані по його переходам, прокручуванню сторінок і т.д. Тут закладений величезний потенціал, наприклад, для калібрування існуючих класифікаторів пошуку [7,8]. У своїй роботі Jawahar Ponnuswami і ін. [11] використовують CTR як характеристику для вивчення моделі, а також попарно використовують для цієї мети таку політику за переходами і рухом курсором миші.

Веб-дані [11]. Цю групу характеристик можна виділити окремо. Сюди належать характеристики, отримані з результатів органічного веб-пошуку, як, наприклад: текстова релевантність, переходи за веб-документами і т.д. Дані характеристики можуть дуже стати в нагоді для визначення коректного розміщення вертикальних результатів щодо результатів веб-пошуку.

Наскільки нам відомо, жодне з попередніх досліджень не використовувало хоч яку-небудь персоналізовану інформацію користувача для побудови системи вертикального ранжирування.

2.2. Персоналізація
Персоналізація результатів пошуку завжди має на увазі розширення контексту пошуку за рахунок обліку даних історії пошуку конкретного користувача. Наприклад, Bennet та ін. [4] використовують у своїй роботі географічні дані для розширення контексту пошуку, а Харитонов та ін. [10] запропонували використовувати дані про гендерну приналежність користувача для усунення неоднозначності пошукового запиту.

3. НАШ ПІДХІД
Персоналізація ранжирування вертикалей була здійснена за тим же принципом, що і в роботах [4], [6] або [10]. Оригінальний алгоритм ранжирування представив 10 веб-результатів і цілий ряд впроваджених між ними вертикальних результатів. Під «вертикаллю результатів» ми будемо мати на увазі блок, що складається з не менше 1 вертикального «документа».

Оригінальні сторінки пошуку мають наступні обмеження:

По-перше, на них може бути присутнім не більше ніж один вертикальний результат, вставлений для кожної вертикалі.
По-друге, вертикальні результати можуть відображатися лише в чотирьох слотах:

• над першим результатом видачі;
• між 3 і 4 результатом видачі;
• між 6 і 7 результатом видачі;
• після 10 результату видачі.

Аналогічні обмеження були описані в ряді попередніх робіт, як, наприклад, в [1]. На малюнку №1 чітко видно, що сторінка результатів пошуку повністю відповідає даним обмеженням.

У своїх експериментах ми намагалися вирішити більш широке питання, що дозволяє нашим функціям переранжирування об’єднувати стандартні і вертикальні результати пошуку в будь-якому бажаному порядку, тобто в разі потреби порушувати вищеописані обмеження.
Для цього ми розглядали тільки ті запити, за якими був представлений як мінімум один вертикальний результат. У своїх експериментах ми працювали з наступним набором вертикалей: Картинки, Відео, Музика, Новини, Словники, Події і Погода. Хотілося б відзначити, що наш підхід може бути легко використаний будь-яким іншим набором вертикалей.

Для того щоб здійснити переранжирування функцій, ми склали багатовимірні вектор-функції φ (q, u, ri) для кожного результату ri , що відповідає запиту q від користувача u. Зверніть увагу, що під результатом ri може трактуватись як стандартний веб-результат, так і вертикальний результат для будь-якої вертикалі. Якщо результат пошуку відповідав вимогам запиту користувача (тобто був релевантним), ми позначали його вектор «1» (одиницею), якщо ні – «0». Після цього ми використовували точковий підхід для складання моделі ранжирування і переранжировували всі результати відповідно до даних моделі.

3.1. Базові характеристики
Тут ми опишемо принцип побудови базової вектор-функції, що не залежить від поведінки користувача  – φB (q, r).

Дані запитів. Для кожної вертикалі ми побудували вертикальну статистичну мовну модель. Кожна модель була побудована на основі запитів, для яких результат по вертикалі розраховується як кількість кліків за час перебування користувача на документі за запитом (dwelltime) більш ніж за 30 секунд.
Для побудови своїх моделей ми вважали за краще використовувати тексти запитів, а не тексти документів, тому що деякі з наших вертикалей працювали з нетекстовим контентом, а ми б хотіли розглядати вертикалі послідовно. Іншою причиною є те, що моделі, побудовані таким чином, мають дуже схожу семантику, за характеристиками, за ключовими словами, а це веде до того, що і наші функції переранжиривання мають сигнал цього ж типу. Як характеристики ми також додали сюди довжину пошукового запиту.

Дані вертикалей і дані Веб (тобто дані стандартних результатів пошуку). У якості першої характеристики сюди можна віднести позицію результату в оригінальному рейтингу пошукової видачі. Тут в якості характеристики використовується показник релевантності результату, що оцінюється оригінальним алгоритмом ранжирування, який застосовується тільки для веб-документів. Зверніть увагу на те, що наш базовий набір характеристик включає в себе характеристики, необхідні для отримання неперсоналізованої версії показника вертикальної релевантності. Саме тому для коректного порівняння даних персоналізованого і неперсоналізованого підходів ми гранично точно й докладно визначаємо і співставляємо релевантність вертикалей цих двох методів.

Дані журналу пошуку. Наступні характеристики, які ми використовували, були засновані на п’яти клікових функціях.

3.2. Характеристики персоналізації
Ми пропонуємо ввести три класи персоналізованих характеристик, які, на наш погляд, поліпшать алгоритм вертикального ранжирування.

Потреба агрегованого пошуку. Передбачається, що даний набір функцій буде повідомляти, чи зацікавлений у цілому користувач в агрегованих результатах пошуку і чи віддає перевагу він їх стандартним результатами веб-пошуку. Позначимо вектор цих функцій як φa (u).

Перевага конкретних вертикалей. Цей набір властивостей описує вимоги користувача для отримання результатів певного типу за всіма пошуковими запитами. Ми вважаємо, що дана характеристика тісно пов’язана з інтересами користувача і її додавання в призначений для користувача персоналізований профіль може допомогти в усуненні деякої неоднозначності запитів для кожного конкретного користувача.

Перша характеристика даного класу висловлює різницю між користувальницькою статистичної мовної моделлю (будується за запитами користувача протягом відрізка часу, що досліджується) і мовною моделлю для результатів вертикалі.
Ще одним способом виразити вищеописану мотивацію можна за рахунок використання даних інформації за переходами. Для цього ми використовуємо спеціальні функції. Вектор-функція для цих характеристик позначається як φc (u, ri).

Вертикальна навігаційність. Необхідно пам’ятати, що часом призначені для користувача потреби можуть не збігатися з його загальними перевагами за деякими специфічними пошуковими запитами. Наприклад, результати пошуку за вертикалями Новини або Погода можуть бути більш актуальними, ніж результати з вертикалі Картинки для користувача з Амстердама за запитом [Амстердам], навіть якщо раніше цим користувачем віддавалася перевага вертикалі Картинки. Вектор-функція для цих характеристик позначається як φn (q, u, ri).

Також ми додали абсолютні значення відповідних кліків і відобразили кожен з них на вектор-функції. Таким чином, нашим моделям був повідомлений рівень активності користувача, що стосується вертикальних результатів, які також могли представляти цінність для роботи алгоритму навчання. Зверніть увагу, що ці вектори функцій мають сенс тільки для вертикальних результатів.

3.3. Функції переранжирування
Ми «навчили» цілий ряд функцій переранжиривання, що відрізняються один від одної набором показників,  що використовуються. Для навчання своїх моделей ми віддали перевагу оригінальній версії алгоритму дерева прийняття рішень GBDT (GradientBoostedDecisionTrees-basedalgorithm), яка налаштована на мінімізацію MSE (MinimizeMeanSquaredError (MSE) – мінімізація середнього квадрата помилки (різниці між дійсними і передбаченими значеннями)) (аналогічні GBDT-алгоритми застосовувалися в роботах [3,11]).

Базова вектор-функція RB була навчена за допомогою вектора функцій φB (q, r). Ця вектор-функція включає в себе позицію результату в оригінальному рейтингу пошукової системи Яндекс. З іншої сторони вона також включає в себе типовий набір характеристик, раніше описаних в підрозділі №2.1. Так що дані функції надають нам для роботи достатньо серйозний набір базових характеристик.

Для того щоб гідно оцінити потенціал персоналізації для поліпшення результатів агрегованого пошуку і з’ясувати, який саме клас характеристик персоналізації володіє найбільшим впливом, ми навчили ще 4 функції ранжирування. А саме:

• Racn – була навчена на з’єднання вектор-функцій φB, φa, φc, φn
• Rac – була навчена на з’єднання вектор-функцій φB, φa, φc
• Ran – на з’єднання вектор-функцій φB, φa, φn
• Rcn – на з’єднання вектор-функцій φB, φc, φn

3.4. Набір даних і протокол експерименту
Для проведення своїх експериментів ми скористалися даними сесії користувачів, взятих з журналів пошуку Яндексу. По кожному запиту в журналах містилися такі дані: сам запит, топові результати пошуку по даному запиту, інформація про кліки за результатами.
Всім користувачам пошукової системи був призначений анонімний UID (ідентифікатор користувача), куки, дані про який також зберігаються в журналах, що дозволило нам виділяти дії, що здійснюються різними користувачами.

Ми розглядали набір призначених для користувача сесій, взятих за проміжок у вісім тижнів, тобто ті, що були зафіксовані з травня по червень 2012 року. При цьому ми брали до уваги тільки ті результати пошуку, які містили в собі принаймні один вертикальний результат.

Оскільки ми збиралися дати оцінку персоналізованим характеристикам, для нас не було можливим скористатися даними асессорів, тому нам довелося витягувати інформацію про релевантність результатів з журналів пошуку. Ми вважали результат релевантним пошуковому запиту, якщо по ньому був клік при показнику dwelltime> 30 секунд або якщо клік по даному результату був останньою дією користувача в його сесії. У всіх інших випадках ми вважали, що результат, який вивчається, нерелевантний.

Для того щоб в ході своїх експериментів отримати неупереджені результати, ми чітко слідували протоколу, який описаний в роботі [5]. Для побудови навчальних і тестових наборів ми скористалися даними сесій, взятих за сьомий і восьмий тиждень відповідно. При цьому ми вибудували набори даних таким чином, щоб не тестувати моделі по сесіям одного і того ж періоду. Зроблено це було з тієї причини, що дані сесій, які використовуються для навчання, могли б упереджено вплинути на кінцеві результати.

За обома наборами даних ми розглядали тільки ті запити, у яких хоча б один результат мав позитивну оцінку, а вертикальний результат при цьому вважався «поміченим». Щоб побудувати функції на основі інформації з пошукових журналів (як персоналізованих, так і неперсоналізованих), для навчального набору ми скористалися даними сесій, взятих за проміжок в 1-6 тижнів, а для тестового набору – за 2-7 тижнів (тобто у них був рівний обсяг даних).

І нарешті, наш власний набір (UP) складається з користувачів, які переглянули результат з будь-якої вертикалі не менше 5 разів протягом двох досліджуваних періодів часу за розділами функцій (тобто за 1-6 тижнів і 2-7 тижнів).
У кінцевому рахунку, у нас «на руках» виявилися дані близько 3 млн користувачів, а також навчальні та тестові набори, що містять в собі результати пошуку по приблизно 7 млн запитів.

Усі функції ранжирування були навчені, а потім оцінювалися за допомогою користувальницької специфічної версії п’ятикратної перехресної перевірки, яка була створена спеціальним чином. Даний тип перевірки дозволив нам бути впевненими в тому, що отримані результати спотворювалися в сторону призначених для користувача даних, що використовувались для навчання.

4. РЕЗУЛЬТАТИ
Якість переранжирування було виміряно за допомогою макроусередненої середньої точності (MeanAveragePrecision – MAP) переранжированих документів за запитами в кожної тестової частини, а потім усереднено по частинах.
Ми також виміряли продуктивність наших моделей відносно до цілого ряду параметрів запиту з точки зору їх потенціалу щодо поліпшення даних персоналізації. Ще ми адаптували загальну клікову ентропію до потреб агрегованого пошуку, тобто ми не використовували клікову ймовірність для кожного результату. Замість цього ми використовували агреговані ймовірності кліка по всім веб-результатам і ймовірність кліка по кожній вертикалі.

4.1. Загальна продуктивність
Наша Racn функція переранжирування вплинула на 29% всіх пошукових запитів у кожної частини, що тестується. А по всім запитам MAP зріс на 18%. Таким чином, за допомогою своїх функцій переранжирування ми поліпшили пошукову видачу на 62%.

Всі 4 персоналізовані моделі значно поліпшили якість ранжирування. І ступінь цього поліпшення варіюється за різними класами запиту, також вона значно зростає з ростом клікової ентропії, що повністю відповідає результатам попередніх досліджень.
Що стосується сили персоналізованих характеристик, то ігнорування такої характеристики, як «вертикальна перевага», веде до значного погіршення продуктивності моделі. А ось виняток двох інших типів характеристик веде до меншого зниження якості, але, тим не менш, також погіршує продуктивність моделі за всіма пошуковими запитами і для більшості підкласів.

4.2. Аналіз рівня запиту
По-перше, ми б хотіли більш детально вивчити залежність впливу персоналізованого підходу від змін в кліковій ентропії. На малюнку №2 показані поліпшення MAP як функції адаптованої клікової ентропії. Цей графік показує, що в цілому зростання ентропії веде до збільшення сили впливу персоналізації на ранжування вертикалей. Більш того, позитивний ефект спостерігається навіть на запити з низьким показником ентропії.

Як вже було сказано вище, наша функція переранжирування вплинула на 29% всіх пошукових запитів в кожній тестованій частині, що приблизно становить 1,2 млн запитів. З іншого боку, в кожній частині, що тестується, міститься приблизно 680000 унікальних запитів; наша функція переранжірованія вплинула на 32% з них, при цьому 61% змін носив позитивний характер. Необхідно звернути увагу на те, що один і той же запит, введений різними користувачами, в пошуковій видачі міг бути ранжований по-різному або зовсім відсутній на сторінці результатів пошуку.

Мал. №2. Зміна MAP як функції ентропії   

4.3. Аналіз рівня користувача
Ще одним важливим аспектом аналізу персоналізованих моделей є їх вплив на окремих користувачів. Отже, у нас були дані про 3 млн користувачів (UP), які ми розділили на 5 непересічних частин. Таким чином, в кожній частині виявилося по 600000 користувачів. Однак в кожній частині набору даних були запити, введені приблизно 450000 користувачами, тому що не всі користувачі проявляли активність на 8 тижні, що тестується. Сесії 54% користувачів підпали під вплив нашої функції переранжиривання, і для 64% з них персоналізоване переранжирування мало позитивний характер. На малюнку №4 видно середнє зростання MAP для частини користувачів між 5-и і 95-и процентилями зразків користувачів, які ввели щонайменше 5 пошукових запитів на 8 тижні.

Мал. №4. Зміна MAP по користувачах (відсортовані по зміні MAP)

4.4. Аналіз SERP
У ході своєї роботи ми також вивчили, в якій залежності перебуває вплив персоналізації від представлених в пошуковій видачі вертикалей. Для цього ми в першу чергу виміряли, як персоналізоване переранжирування змінило порядок вертикальних результатів, за умови, що сторінка результатів спочатку містила в собі не менше двох вертикалей. Для даної мети ми підрахували показник MAP, враховуючи тільки результати вертикалей і таким чином отримали зростання в 1,24.

Ми також досліджували залежність зростання показника MAP від числа поданих вертикалей в SERP. Результати виявилися наступними: по 1 результату вертикалі (а це 75% запитів) показник зростання MAP складає 2,72%, для 2 вертикалей (22% запитів) MAP зростає на 3,80%, для 3 вертикалей (2,5% запитів) – зростання MAP складає 4.31%, а для 4 вертикалей (приблизно 0,5% запитів) – 3,43%. Всі ці зміни досить відчутні.
Ми також вивчили, які саме вертикалі в більшій чи меншій мірі відчули переваги персоналізованого підходу в процесі ранжирування і з’ясували, що найкращим чином даний підхід вплинув на вертикалі Відео та Погода (5,35% і 8,2%), а найменше на вертикалі Словники та Події.

ВИСНОВОК
У даній роботі ми розглянули що раніше не досліджувану проблему персоналізованого агрегованого пошуку і розробили структуру з трьома класами персоналізованих характеристик. Це дозволило нам побудувати безпрецедентну функцію ранжирування, яка в середньому перевищує існуючу систему по MAP в 3% на всі запити в агрегованому пошуку. Розроблена нами функція переранжирування змінила результати пошукової видачі для 29% запитів, при цьому покращивши їх ранжування на 61%. У ході дослідження ми також з’ясували, що клас характеристик «конкретні вертикальні переваги» – це один з найголовніших класів при побудові конкурентоспроможного персоналізованого ранжирування, втім, два класи, що залишилися,  також значно впливають на ранжування.

Персоналізований агрегований пошук набагато ефективніший і якісніший за стандартний метод ранжирування.

ЛІТЕРАТУРА

1. Arguello J., Diaz F., Callan J.: Learning to aggregate vertical results into web search result. In: Proceedings of CIKM 2011(2011)
2. Arguello J., Diaz F., Callan, J., Crespo J.F.: Sources of evidence for vertical selection. In: Proceedings of SIGIR 2009 (2009)
3. Arguello J., Diaz F., Paiement J.F.: Vertical selection in the presence of unlabeled verticals. In: Proceedings of SIGIR 2010 (2010)
4. Bennett P.N., Radlinski F., White R.W., Yilmaz E.: Inferring and using location metadata to personalize web search. In: Proceedings of SIGIR 2011 (2011)
5. Bennett P.N., White R.W., Chu W., Dumais S.T., Bailey P., Borisyuk F., Cui X.: Modeling the impact of short- and long-term behavior on search personalization. In: Proceedings of SIGIR 2012 (2012)
6. Collins-Thompson K., Bennett P.N., White R.W., de la Chica S., Sontag D.: Personalizing web search results by reading level. In: Proceedings of CIKM 2011 (2011)
7. Diaz F.: Integration of news content into web results. In: Proceedings of WSDM 2009 (2009)
8. Diaz F., Arguello J.: Adaptation of offline vertical selection predictions in the presence of user feedback. In: Proceedings of SIGIR 2009 (2009)
9. Dou Z., Song R., Wen J.R.: A large-scale evaluation and analysis of personalized search strategies. In: Proceedings of WWW 2007 (2007)
10. Kharitonov E., Serdyukov P.: Gender-aware re-ranking. In: Proceedings of SIGIR 2012 (2012)
11. Ponnuswami A., Pattabiraman K., Wu Q., Gilad-Bachrach R., Kanungo T.: On composition of a federated web search result page: using online users to provide pairwise preference for heterogeneous verticals. In: Proceedings of WSDM 2011 (2011)
12. Styskin A., Romanenko F., Vorobyev F., Serdyukov P.: Recency ranking by diversification of result set. In: Proceedings of CIKM 2011 (2011)
13. Vallet D., Castells P.: Personalized diversification of search results. In: Proceedings of SIGIR 2012 (2012)

 

Авторський переклад статті – Євген Аралов

Еще по теме:

• Історія алгоритмів Яндексу
• Що робити, якщо різко просів трафік з Яндексу? Покрокова інструкція щодо діагностики причин
• Як налаштувати Google Analytics: відповідаємо на часті питання