Сегодня мы поговорим о новой технологии поиска Королева, которая включает в себя не только более глубокое использование нейронных сетей для поиска по смыслу, а не по словам, но и существенные изменения в архитектуре самого индекса.
Но зачем нам вообще были нужны технологии из области искусственного интеллекта, если двадцать лет назад мы прекрасно могли найти в поиске то, что искали? Чем Королев отличается от прошлогоднего алгоритма Палеха, в котором также использовались нейронные сети? И как архитектура индекса влияет на качество ранжирования? На все эти вопросы мы ответим специально для читателей Хабра.
И начнем с самого начала.
От частоты слов к нейронным сетям Интернет на заре своего существования сильно отличался от своего нынешнего состояния.
И дело было не только в количестве пользователей и веб-мастеров.
Во-первых, сайтов по каждой отдельной теме было так мало, что первым поисковым сервисам достаточно было вывести список всех страниц, содержащих искомое слово.
И даже если сайтов было много, достаточно было посчитать количество употреблений того или иного слова в тексте, а не заниматься сложным ранжированием.
Бизнеса в Интернете еще не было, поэтому продвижением никто не занимался.
Со временем сайтов стало заметно больше, как и желающих манипулировать результатами поиска.
И поисковые компании сталкиваются с необходимостью не просто искать страницы, но и выбирать среди них наиболее соответствующие запросу пользователя.
Технологии на рубеже веков еще не позволяли «понимать» тексты страниц и сопоставлять их с интересами пользователей, поэтому сначала было найдено более простое решение.
Поиск стал учитывать ссылки между сайтами.
Чем больше ссылок, тем авторитетнее ресурс.
А когда их стало недостаточно, он начал учитывать поведение людей.
И именно пользователи Поиска сейчас во многом определяют его качество.
В какой-то момент всех этих факторов накопилось настолько много, что человек уже не мог справиться с написанием формул ранжирования.
Конечно, мы еще могли бы взять лучших разработчиков и они бы написали более-менее работающий алгоритм поиска, но машина справилась бы лучше.
Поэтому в 2009 году Яндекс представил собственный метод машинного обучения Matrixnet, который и по сей день строит формулу ранжирования с учетом всех доступных факторов.
Мы давно мечтали добавить к этим факторам тот, который отражал бы актуальность страницы не через косвенные признаки (ссылки, поведение,.
), а через «понимание» ее содержания.
И с помощью нейросетей нам это удалось.
В самом начале мы говорили о факторе, учитывающем частотность слов в тексте документа.
Это крайне примитивный способ определить, соответствует ли страница запросу.
Современные вычислительные мощности позволяют использовать для этого нейронные сети, которые справляются с анализом естественной информации (текста, звука, изображений) лучше, чем любой другой метод машинного обучения.
Проще говоря, именно нейронные сети позволяют машине перейти от поиска по словам к поиску по смыслу.
И это именно то, что мы начали делать в алгоритме Палеха в прошлом году.
Запрос + заголовок Подробнее о «Палехе» написано Здесь , но в этом посте мы еще раз вкратце напомним об этом подходе, ведь именно «Палех» лежит в основе «Королева».
У нас есть запрос человека и заголовок страницы, которая претендует на то, чтобы находиться в топе результатов поиска.
Вам необходимо понять, насколько они соответствуют друг другу по смыслу.
Для этого представим текст запроса и текст заголовка в виде векторов, скалярное произведение которых будет тем больше, чем более релевантным запросу является документ с данным заголовком.
Другими словами, используя накопленную статистику поиска, мы обучаем нейронную сеть таким образом, что для близких по смыслу текстов она генерирует схожие векторы, а для семантически несвязанных запросов и заголовков векторы должны быть разными.
Как только человек вводит запрос в Яндекс, наши серверы в реальном времени конвертируют тексты в векторы и сравнивают их.
Результаты этого сравнения используются поисковой системой в качестве одного из факторов.
Представляя текст запроса и текст заголовка страницы в виде семантических векторов, модель Палеха позволяет улавливать достаточно сложные смысловые связи, которые иначе сложно выявить, что, в свою очередь, влияет на качество поиска.
«Палех» хорош, но в нем было много нереализованного потенциала.
Но чтобы понять это, нам сначала нужно вспомнить, как именно работает процесс ранжирования.
Этапы рейтинга Поиск — штука невероятно сложная: вам нужно за доли секунды найти самые релевантные среди миллионов страниц.
Поэтому ранжирование в современных поисковых системах обычно осуществляется с помощью целого каскада ранкеров.
Другими словами, поисковая система использует несколько этапов, на каждом из которых документы сортируются, после чего нижние документы отбрасываются, а верхние, состоящие из лучших документов, передаются на следующий этап.
На каждом последующем этапе используются все более тяжелые алгоритмы ранжирования.
Это сделано в первую очередь для экономии ресурсов поискового кластера: вычислительно тяжелые коэффициенты и формулы рассчитываются только для относительно небольшого числа лучших документов.
Палех — относительно тяжелый алгоритм.
Нам нужно перемножить несколько матриц, чтобы получить векторы запроса и документа, а затем также перемножить их.
Умножение матриц отнимает драгоценное время процессора, и мы не можем позволить себе выполнять эту операцию со слишком большим количеством документов.
Поэтому в Палехе мы применили наши нейронные модели только на самых поздних стадиях ранжирования (L3) — примерно к 150 лучшим документам.
С одной стороны, это неплохо.
В большинстве случаев все документы, которые необходимо показать в первой десятке, находятся где-то среди этих 150 документов, и вам нужно лишь правильно их отсортировать.
С другой стороны, иногда хорошие документы все равно теряются на первых этапах рейтинга и не попадают в топ.
Особенно это актуально для сложных и низкочастотных запросов.
Поэтому было очень заманчиво научиться использовать возможности моделей нейронных сетей для ранжирования как можно большего количества документов.
Но как это сделать? Королев: вычисления в обмен на память Если сложный алгоритм невозможно сделать простым, то можно хотя бы перераспределить потребление ресурсов.
И в этом случае мы можем выгодно обменять процессорное время на память.
Вместо того, чтобы брать заголовок документа и вычислять его семантический вектор во время выполнения запроса, вы можете предварительно вычислить этот вектор и сохранить его в базе данных поиска.
Другими словами, мы можем заранее проделать значительную часть работы, а именно перемножить матрицы для документа и сохранить результат. Тогда во время выполнения запроса нам нужно будет только получить вектор документа из индекса поиска и выполнить скалярное умножение с вектором запроса.
Это значительно быстрее, чем динамическое вычисление вектора.
Конечно, нам понадобится место для хранения заранее вычисленных векторов.
Подход, основанный на заранее вычисленных векторах, позволил радикально увеличить глубину вершины (L3, L2, L1), к которой применяются нейронные модели.
Новые модели Королева рассчитаны на фантастическую глубину — 200 тысяч документов за запрос.
Это позволило получить чрезвычайно полезный сигнал на ранних этапах ранжирования.
Но это не все.
Успешный опыт предварительного вычисления векторов и хранения их в памяти открыл нам путь к новой модели, о которой раньше мы могли только мечтать.
Королев: запрос + документ В Палехе в качестве входных данных для модели использовался только заголовок страницы.
Обычно заголовок является важной частью документа, кратко описывающей его содержание.
Однако тело страницы также содержит информацию, которая чрезвычайно полезна для эффективного определения семантической релевантности документа запросу.
Так почему же мы вообще ограничились названием? Дело в том, что на практике реализация полнотекстовых моделей связана с рядом технических трудностей.
Во-первых, это дорого с точки зрения памяти.
Чтобы применить нейронную модель к тексту во время выполнения запроса, необходимо иметь этот текст «под рукой», то есть в оперативной памяти.
И если поместить в оперативную память короткие тексты типа заголовков было вполне возможно при имеющихся в нашем распоряжении мощностях, то сделать это с полными текстами документов уже будет невозможно.
Во-вторых, это дорого с точки зрения процессора.
Начальный этап расчета модели — проецирование документа в первый скрытый слой нейронной модели.
Для этого нам нужно сделать один проход по тексту.
Фактически на этом этапе мы должны выполнить умножения n*m, где n — количество слов в документе, а m — размер первого слоя модели.
Таким образом, количество процессорного времени, необходимое для применения модели, линейно зависит от длины текста.
Это не проблема, когда дело касается коротких заголовков.
Но средняя длина тела документа значительно больше.
Все это звучит так, будто невозможно реализовать полнотекстовую модель без радикального увеличения размера поискового кластера.
Но мы обошлись без этого.
Ключом к решению проблемы стали те же заранее вычисленные векторы, которые мы уже тестировали для модели заголовка.
На самом деле нам не нужен полный текст документа — достаточно просто сохранить относительно небольшой массив чисел с плавающей запятой.
Мы можем взять полный текст документа на этапе его индексации, применить к нему ряд операций, состоящих из последовательного умножения нескольких матриц, и в результате получить веса в последнем внутреннем слое нашей нейронной модели.
При этом размер слоя фиксированный и не зависит от размера документа.
Более того, такое перераспределение нагрузки с процессоров на память позволило по-новому взглянуть на архитектуру нейронной сети.
Королев: многоуровневая архитектура Старые модели Палеха имели три скрытых слоя размером 150, 300 и 300 нейронов.
Такая архитектура была обусловлена необходимостью экономии вычислительных ресурсов: умножение больших матриц во время выполнения запроса обходится дорого.
Кроме того, оперативная память необходима и для хранения самой модели.
Особенно сильно размер модели зависит от размера первого скрытого слоя, поэтому в Палехе он был сравнительно небольшим — 150 нейронов.
Уменьшение первого скрытого слоя позволяет существенно уменьшить размер модели, но в то же время снижает ее выразительность.
В новых моделях Королева узким местом является только размер последнего скрытого слоя.
При использовании заранее вычисленных векторов ресурсы тратятся только на сохранение последнего слоя в индексе и скалярное умножение его на вектор запроса.
Таким образом, разумным шагом было бы придать новым моделям более «клиновидную» форму с увеличением первых скрытых слоев и уменьшением последнего скрытого слоя.
«Эксперименты показали, что можно получить хороший выигрыш в качестве, если сделать размеры скрытых слоев равными 500, 500 и 40 нейронам.
В результате увеличения первых внутренних слоев выразительная сила модели заметно возросла, а последний слой можно сократить до пары десятков нейронов практически без потери качества.
Однако, несмотря на всю нашу оптимизацию, такое глубокое использование нейронных сетей в поиске требует значительных вычислительных мощностей.
И кто знает, сколько еще времени потребовалось бы на реализацию, если бы не еще один проект, высвободивший ресурсы для их использования, хотя с его помощью мы решали совсем другую задачу.
Королев: дополнительный индекс Когда мы получаем запрос пользователя, мы начинаем постепенно выбирать лучшие страницы среди миллионов страниц в индексе.
Все начинается со стадии L0, которая собственно и является фильтрацией.
Он отфильтровывает большую часть нерелевантных документов, а остальные этапы занимаются основным ранжированием.
В классической модели поиска мы решаем эту проблему с помощью инвертированных индексов.
Для каждого слова сохраняются все документы, в которых оно встречается, и при поступлении запроса мы пытаемся перекрестить эти документы.
Основная проблема – частота слов.
Слово «Россия», например, может появиться на каждой десятой странице.
В результате нам приходится просматривать каждый десятый документ, чтобы не потерять ничего нужного.
Но с другой стороны, мы ждем пользователя, который только что ввел свой запрос и в тот же момент ожидает увидеть ответ, поэтому этап фильтрации строго ограничен по времени.
Мы не могли позволить себе просмотреть все документы на предмет часто встречающихся слов и использовали разные эвристики: сортировали документы по некоторому значению индифферентного релевантного запроса или останавливали поиск, когда нам казалось, что мы нашли достаточное количество хороших документов.
В целом такой подход работал хорошо, но иногда терялись полезные документы.
С новым подходом все по-другому.
В его основе лежит гипотеза: если для запроса из нескольких слов взять не очень большой список наиболее релевантных документов по каждому слову или фразе, то среди них найдутся документы, релевантные всем словам одновременно.
На практике это означает следующее.
Для всех слов и популярных пар слов формируется дополнительный индекс со списком страниц и их предварительной релевантностью запросу.
То есть часть работы мы переносим с этапа L0 на этап индексации.
Что это нам дает? Жесткие ограничения по времени вычислений связаны с простым фактом — вы не можете заставить пользователя ждать.
Но если эти расчеты можно произвести заранее и офлайн (то есть не в момент ввода запроса), то таких ограничений нет. Мы можем позволить машине сканировать все документы в индексе, и ни одна страница не будет потеряна.
Важна полнота поиска.
Но не менее важным является тот факт, что за счет потребления оперативной памяти мы существенно разгрузили нагрузку на генерацию вывода, освободив вычислительные ресурсы для тяжелых нейросетевых моделей запрос+заголовок и запрос+документ. И не только для них.
Королев: просьба + просьба Когда мы приступили к работе над новым поиском, мы еще не были уверены, какое направление окажется наиболее перспективным.
Поэтому мы выделили две команды для изучения нейронных моделей.
Некоторое время они работали независимо, развивая собственные идеи, и даже в какой-то степени конкурировали друг с другом.
Один из них работал над запросно-документным подходом, который мы уже описали выше.
Вторая команда подошла к проблеме совершенно с другой стороны.
К любой странице в Интернете можно придумать более одного запроса.
Тот же «ВКонтакте» можно искать по запросам [ВКонтакте], [Вход в Контакте] или [социальная сеть ВКонтакте].
Просьбы разные, но смысл за ними один и тот же.
И это можно использовать.
Коллегам из второй команды пришла в голову идея сравнить семантические векторы запроса, который только что ввёл пользователь, и другого запроса, для которого мы точно знаем лучший ответ. И если векторы (а значит и смыслы запросов) достаточно близки, то и результаты поиска должны быть схожими.
В результате оказалось, что оба подхода дают хорошие результаты, и наши команды объединили усилия.
Это позволило быстро завершить исследование и внедрить новые модели в поиск Яндекса.
Например, если вы сейчас введете запрос [ленивый кот из Монголии], то именно нейросети помогут вывести в топ информацию о мануле.
Что дальше? «Королев» — это не одна конкретная модель, а целый набор технологий для более глубокого использования нейронных сетей в поиске Яндекса.
Это еще один важный шаг к будущему, в котором Поиск будет ориентироваться на семантическое соответствие запросов и страниц не хуже человека.
Или даже лучше.
Все вышеперечисленное уже работает, а некоторые другие идеи ждут своего часа.
Например, мы хотели бы попробовать использовать нейронные сети на этапе поиска L0, чтобы семантические векторы помогали нам находить документы, близкие по смыслу к запросу, но вообще не содержащие слов запроса.
Еще мы хотели добавить персонализацию (представить другой вектор, соответствующий интересам человека).
Но все это требует не только времени и знаний, но и памяти, и вычислительных ресурсов, и здесь без нового дата-центра не обойтись.
А у Яндекса такой уже есть.
Но это уже другая история, о которой мы обязательно расскажем в ближайшем будущем.
Следите за публикациями.
Теги: #Машинное обучение #искусственный интеллект #Яндекс #Поисковые технологии #поиск #нейронные сети #Семантика #индексирование #рейтинг #Палех #Королев
-
Нетбуки С Китайскими Процессорами
19 Oct, 24 -
Lemongrab: Плагин Проверки Веб-Формы
19 Oct, 24
