Штучний інтелект в пошуку. Як Яндекс навчився застосовувати нейронні мережі, щоб шукати за змістом, а не за словами

Сьогодні ми анонсували новий пошуковий алгоритм «Палех». Він включає в себе всі ті поліпшення, над якими ми працювали останнім часом.

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



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

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

Штучний інтелект або машинне навчання?
Майже всі знають, що сучасні пошукові системи працюють з допомогою машинного навчання. Чому про використання нейронних мереж для його завдань треба говорити окремо? І чому тільки зараз, адже хайп навколо цієї теми не вщухає вже кілька років? Спробую розповісти про історію питання.

Пошук в інтернеті — складна система, яка з'явилася дуже давно. Спочатку це був просто пошук сторінок, потім він перетворився в вирішувача задач, і зараз стає повноцінним помічником. Чим більше інтернет, і чим більше в ньому людей, тим вищі вимоги, тим складніше доводиться ставати пошуку.

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

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

Епоха машинного навчання. Інтернет став комерційно важливим, і з'явилося багато шахраїв, що намагаються обдурити прості алгоритми, що існували у той час. Відбувся другий важливий прорив — пошуковики почали використовувати свої знання про поведінку користувачів, щоб розуміти, які сторінки хороші, а які — ні.

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

Один з найкращих алгоритмів машинного навчання винайшли в Яндексі — Матрікснет. Можна сказати, що ранжування допомагає колективний розум користувачів і «мудрість натовпу». Інформація про сайти і поведінці людей перетворюється на безліч факторів, кожен з яких використовується Матрикснетом для побудови формули ранжирування. Фактично, формулу ранжирування пише машина (виходило близько 300 мегабайт).

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



Але люди складніше, і хочуть від пошуку все більше. Зараз вже до 40% всіх запитів унікальні, тобто не повторюються хоча б двічі протягом всього періоду спостережень. Це означає, що у пошуку немає даних про поведінку користувачів в достатній кількості, і Матрікснет позбавляється цінних факторів. Такі запити в Яндексі називають «довгим хвостом», оскільки всі разом вони становлять істотну частку звернень до нашого пошуку.

Епоха штучного інтелекту
І тут час розповісти про прорив: кілька років тому комп'ютери стають досить швидкими, а даних стає досить багато, щоб використовувати нейронні мережі. Засновані на них технології ще називають машинним інтелектом або штучним інтелектом — тому що нейронні мережі побудовані за образом нейронів в нашому мозку і намагаються емулювати роботу деяких його частин.

Машинний інтелект набагато краще старих методів справляється з завданнями, які можуть робити люди: наприклад, розпізнаванням мови або образів на зображеннях. Але як це допоможе пошуку?

Як правило, низькочастотні і унікальні запити досить складні для пошуку – знайти хороший відповідь за ним помітно важче. Як це зробити? У нас немає підказок від користувачів (який документ краще, а який гірше), тому для рішення пошукової задачі потрібно навчитися краще розуміти смислова відповідність між двома текстами: запитом документом.

Легко сказати
Строго кажучи, штучні нейромережі – це один з методів машинного навчання. Зовсім недавно їм була присвячена лекція в рамках Малого ШАДа. Нейронні мережі показують вражаючі результати в області аналізу природної інформації — звуку і образів. Це відбувається вже кілька років. Але чому їх досі не так активно застосовували в пошуку?

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

Кілька слів про те, як це працює в пошуку по картинках. Ви берете зображення і з допомогою нейронних мереж перетворюєте його в вектор в N-мірному просторі. Берете запит (який може бути як в текстовому вигляді, так і у вигляді іншої картинки) і робите з ним те ж саме. А потім порівнюєте ці вектора. Чим ближче вони один до одного, тим більше картинка відповідає запиту.

Ок, якщо це працює в картинках, чому б не застосувати цю ж логіку в web-пошуку?

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

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

Далі — про те, що ми пробували, як домоглися успіху і як змогли навчити те, що вийшло.

DSSM
У 2013 році дослідники з Microsoft Research описали свій підхід, який отримав назву Deep Structured Semantic Model.



На вхід моделі подаються тексти запитів і заголовків. Для зменшення розмірів моделі, над ними проводиться операція, яку автори називають word hashing. До тексту додаються маркери початку і кінця, після чого він розбивається на літерні триграми. Наприклад, для запиту [палех] ми отримаємо триграми [па, альо, лех, ех]. Оскільки кількість різних триграм обмежена, то ми можемо представити текст запиту у вигляді вектора розміром у кілька десятків тисяч елементів (розмір нашого алфавіту в 3 ступеня). Відповідні триграммам запиту елементи вектора дорівнюють 1, решта — 0. По суті, ми відзначаємо таким чином входження триграм з тексту в словник, що складається з усіх відомих триграм. Якщо порівняти такі вектора, то можна дізнатися тільки про наявність однакових триграм в запиті та заголовку, що не представляє особливого інтересу. Тому тепер їх треба перетворити в інші вектори, які вже будуть мати потрібні нам властивості семантичної близькості.

Після вхідного шару, як і годиться в глибоких архітектурах, розташовано кілька прихованих шарів як для запиту, так і для заголовка. Останній шар розміром в 128 елементів і служить вектором, який використовується для порівняння. Виходом моделі є результат скалярного множення останніх векторів заголовка запиту (якщо бути зовсім точним, то обчислюється косинус кута між векторами). Модель навчається таким чином, щоб для позитивні навчальних прикладів вихідне значення було великим, а для негативних — маленьким. Інакше кажучи, порівнюючи вектори останнього шару, ми можемо обчислити помилку передбачення і модифікувати модель таким чином, щоб помилка зменшилася.

Ми в Яндексі також активно досліджуємо моделі на основі штучних нейронних мереж, тому зацікавилися моделлю DSSM. Далі ми розповімо про свої експерименти в цій області.

Теорія та практика
Характерна властивість алгоритмів, описаних у науковій літературі, полягає в тому, що вони не завжди працюють «з коробки». Справа в тому, що «академічний» дослідник і дослідник з індустрії перебувають в істотно різних умовах. У якості відправної точки (baseline), з якої автор наукової публікації порівнює своє рішення, повинен виступати якийсь загальновідомий алгоритм — так забезпечується відтворюваність результатів. Дослідники беруть результати раніше опублікованого підходу, і показують, як їх можна перевершити. Наприклад, автори оригінального DSSM порівнюють свою модель за метрикою NDCG з алгоритмами BM25 і LSA. У випадку ж з прикладним дослідником, який займається якістю пошуку в реальному пошуковій машині, відправною крапкою служить не один конкретний алгоритм, а всі ранжування в цілому. Мета розробника Яндекса полягає не в тому, щоб обігнати BM25, а в тому, щоб домогтися поліпшення на тлі всього безлічі раніше впроваджених факторів та моделей. Таким чином, базовий для дослідника в Яндексі надзвичайно високий, і багато алгоритми, які мають наукову новизну і показують хороші результати при «академічній» підході, виявляються даремними на практиці, оскільки не дозволяють реально поліпшити якість пошуку.

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

Великий вхідний шар
В оригінальної моделі DSSM вхідний шар являє собою безліч буквених триграм. Його розмір дорівнює 30 000. В підходу на основі триграм є кілька переваг. По-перше, їх відносно мало, тому робота з ними не вимагає великих ресурсів. По-друге, їх застосування спрощує виявлення помилок і помилок у словах. Однак, наші експерименти показали, що подання текстів у вигляді «мішка» триграм помітно знижує виразну силу мережі. Тому ми радикально збільшили розмір вхідного шару, включивши в нього, крім буквених триграм, ще близько 2 мільйонів слів і словосполучень. Таким чином, ми представляємо тексти запиту і заголовка у вигляді спільного «мішка» слів, словесних биграмм і буквених триграм.



Використання великого вхідного шару призводить до збільшення розмірів моделі, тривалості навчання і вимагає значно більших обчислювальних ресурсів.

Важко в навчанні: як нейронна мережа боролася сама з собою і навчився на своїх помилках
Навчання вихідного DSSM полягає в демонстрації мережі великої кількості позитивних і негативних прикладів. Ці приклади беруться з пошукової видачі (судячи з усього, для цього використовувався пошуковик Bing). Позитивними прикладами служать заголовки кликнутых видачі документів, негативними — заголовки документів, за якими не було кліка. У цього підходу є певні недоліки. Справа в тому, що відсутність кліка далеко не завжди свідчить про те, що документ нерелевантний. Справедливо і зворотне твердження — наявність кліка не гарантує релевантності документа. По суті, навчаючись описаним у вихідній статті чином, ми прагнемо передбачати аттрактивность заголовків за умови того, що вони будуть присутні у видачі. Це, звичайно, теж непогано, але має досить непряме відношення до нашої головної мети — навчитися розуміти семантичну близькість.

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

Перша спроба
Спочатку в якості негативного прикладу просто візьмемо заголовок випадкового документа. Наприклад, для запиту [палехская розпис] випадковим заголовком може бути «Правила дорожнього руху 2016 РФ». Зрозуміло, повністю виключити те, що випадково обраний з мільярдів документ буде релевантним запиту, не можна, але ймовірність цього настільки мала, що нею можна знехтувати. Таким чином ми можемо дуже легко отримувати велику кількість негативних прикладів. Здавалося б, тепер ми можемо навчити нашу мережу саме того, чого хочеться — відрізняти хороші документи, які цікавлять користувачів, від документів, що не мають до запиту ніякого відношення. На жаль, навчена на таких прикладах модель виявилася досить слабкою. Нейронна мережа – штука розумна, і завжди знайде спосіб спростити собі роботу. В даному випадку, вона просто почала вишукувати однакові слова у запитах і заголовках: є — гарна пара, немає — погана. Але це ми й самі вміємо робити. Для нас важливо, щоб мережа навчилася розрізняти неочевидні закономірності.

Ще одна спроба
Наступний експеримент полягав у тому, щоб додавати заголовки негативних прикладів слова із запиту. Наприклад, для запиту [палехская розпис] випадковий заголовок виглядав як [Правила дорожнього руху 2016 РФ розпис]. Нейронної мережі довелося трохи складніше, але, тим не менш, вона досить швидко навчилася добре відрізняти природні пари від складених вручну. Стало зрозуміло, що такими методами ми доб'ємося успіху на.

Успіх
Багато очевидні рішення стають очевидними тільки після їх виявлення. Так вийшло і на цей раз: через деякий час виявилося, що найкращий спосіб генерації негативних прикладів — це змусити мережа «воювати» проти самої себе, вчитися на власних помилках. Серед сотень випадкових заголовків ми вибирали такий, який поточна нейромережа вважала найкращим. Але, так як цей заголовок все одно випадковий, з високою ймовірністю він не відповідає запиту. І саме такі заголовки ми стали використовувати в якості негативних прикладів. Іншими словами, можна показати мережі кращі з випадкових заголовків, навчити її, знайти нові кращі випадкові заголовки, знову показати мережі і так далі. Раз за разом повторюючи цю процедуру, ми бачили, як помітно поліпшується якість моделі, і все частіше кращі з випадкових пар ставали схожі на справжні позитивні приклади. Проблема була вирішена.

Подібна схема навчання у науковій літературі зазвичай називається hard negative mining. Також не можна не відзначити, що подібні ідеї рішення отримали широке поширення в науковому співтоваристві для генерації реалістично виглядають зображень, подібний клас моделей отримав назву Generative Adversarial Networks.

Різні цілі
В якості позитивних прикладів дослідники з Microsoft Research використовувалися певні документи. Однак, як вже було сказано, це досить ненадійний сигнал про смисловому відповідно заголовка запиту. Зрештою, наше завдання полягає не в тому, щоб підняти в пошуковій видачі найбільш відвідувані сайти, а в тому, щоб знайти дійсно корисну інформацію. Тому ми пробували в якості мети навчання використовувати інші характеристики поведінки користувача. Наприклад, одна з моделей пророкувала, залишиться користувач на сайті або піде. Інша – наскільки довго він затримається на сайті. Як виявилося, можна помітно поліпшити результати, якщо оптимізувати таку цільову метрику, яка свідчить про те, що користувач знайшов те, що йому було потрібно.

Профіт
Ок, що це нам дає на практиці? Давайте порівняємо поведінку нашої нейронної моделі і простого текстового фактора, заснованого на відповідності слів запиту і тексту — BM25. Він прийшов до нас з тих часів, коли ранжування було простим, і зараз його зручно використовувати за базовий рівень.

В якості прикладу візьмемо запит [келлська книга] і подивимося, яке значення приймають фактори на різних заголовках. Для контролю додамо до списку заголовків явно нерелевантні результат.

Заголовок сторінки BM25 Нейронна модель
келлська книга вікіпедія 0.91 0.92
вчені досліджують келлську книгу навколо світу 0.88 0.85
book of kells wikipedia 0 0.81
ірландські ілюстровані євангелія vii viii вв 0 0.58
ікеа гіпермаркети товарів для дому і офісу ikea
0 0.09
Всі фактори в Яндексі нормуються в інтервал [0;1]. Цілком очікувано, що BM25 має високі значення для заголовків, які містять слова запиту. І цілком передбачувано, що цей фактор отримує нульове значення на заголовках, що не мають спільних слів із запитом. Тепер зверніть увагу на те, як веде себе нейронна модель. Вона однаково добре розпізнає зв'язок запиту з російськомовним заголовком релевантної сторінки з Вікіпедії, так і з заголовком статті англійською мовою! Крім того, здається, що модель «побачила» зв'язок запиту із заголовком, в якому не згадується келлська книга, але є близьке за змістом словосполучення («ірландські євангелія»). Значення ж моделі для нерелевантного заголовка істотно нижче.

Тепер давайте подивимося, як будуть себе вести наші фактори, якщо ми переформулюємо запит, не змінюючи його змісту: [євангеліє з келлса].

Заголовок сторінки BM25 Нейронна модель
келлська книга вікіпедія 0 0.85
вчені досліджують келлську книгу навколо світу 0 0.78
book of kells wikipedia 0 0.71
ірландські ілюстровані євангелія vii viii вв 0.33
0.84
ікеа гіпермаркети товарів для дому і офісу ikea 0 10
Для BM25 переформулювання запиту перетворилася в справжню катастрофу — фактор став нульовим на релевантних заголовках. А наша модель демонструє відмінну стійкість до переформулировке: релевантні заголовки, як і раніше, мають високе значення фактора, а нерелевантні заголовок — низьке. Здається, що саме таку поведінку ми і очікували від штуки, яка претендує на здатність «розуміти» семантику тексту.

Ще приклад. Запит [розповідь в якому розчавили метелика].
Заголовок сторінки BM25 Нейронна модель
фільм в якому розчавили метелика 0.79 0.82
і грянув грім вікіпедія 0 0.43
бредбері рей вікіпедія 0 0.27
машина часу роман вікіпедія 0 0,24
домашнє малинове варення рецепт заготівлі на зиму 0 0.06
Як бачимо, нейронна модель виявилася здатна високо оцінити заголовок з правильною відповіддю, незважаючи на повну відсутність спільних слів із запитом. Більше того, добре видно, що заголовки, які не відповідають на запит, але все ж пов'язані з ним за змістом, отримують досить високе значення фактора. Ніби наша модель «прочитала» оповідання Бредбері і «знає», що це саме про нього йдеться в запиті!

А що далі?
Ми знаходимося в самому початку великого і дуже цікавого шляху. Судячи з усього, нейронні мережі мають відмінний потенціал для поліпшення ранжирування. Вже зрозумілі основні напрямки, які потребують активного розвитку.

Наприклад, очевидно, що заголовок містить неповну інформацію про документі, і добре б навчитися будувати модель за повного тексту (як виявилося, це не зовсім тривіальна задача). Далі, можна уявити собі моделі, що мають істотно більш складну архітектуру, ніж DSSM — є підстави припускати, що таким чином ми зможемо краще обробляти деякі конструкції природних мов. Свою довгострокову мету ми бачимо в створенні моделей, спроможних «розуміти» семантичне відповідність запитів і документів на рівні, порівнянному з рівнем людини. На шляху до цієї мети буде багато складнощів — тим цікавіше буде його пройти. Ми обіцяємо розповідати про свою роботу в цій області. Слідкуйте за наступними публікаціями.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.