Искусство понимать с полуслова. Расширение запроса в Яндексе

:

Сегодня мы расскажем о механизме, который позволяет поиску Яндекса находить именно то, что имел в виду пользователь, как бы кратко и небрежно он ни сформулировал свой запрос.

В мире поиска такой механизм называют расширением поискового запроса. Термин достаточно широкий, включает в себя переформулировки, синонимы, транслит и даже однокоренные слова (последние иногда ошибочно называют поддержкой морфологии).

Из каких частей этот механизм состоит? Что помогает ему угадывать? И почему на каждую из его редких ошибок приходятся тысячи запросов, на которых он сильно помог?

image
Почему нельзя просто так взять и расширить запрос.

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

Заметив это много лет назад, разработчики поисковых систем решили, что можно сильно упростить жизнь пользователю, если сразу, автоматически, искать не только заданный запрос, но и различные его вариации и переформулировки. Теперь уже никого не удивляет точная поисковая выдача в руках пользователя, не искушённого в премудростях составления поискового запроса — однако борьба за экономию времени и увеличение свободы при формулировании запроса продолжается.

Сегодня мы рассмотрим только механизмы расширения запроса, то есть дополнение исходного запроса другими словами. О способах изменения запроса (исправлении опечаток в слове «одноклассники» и словоизменении Брич-Муллу, Брич-Муллою) постараемся рассказать в другой раз.

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

Аббревиатуры (рфРоссийская Федерация)


Раскрытие аббревиатур, пожалуй, самый обманчивый вид расширений — кажется на первый взгляд точным и однозначным («очевидно», «МГУ» — это «Московский Государственный Университет»), но быстро выясняется: есть и «Мордовский», и «Мариупольский», и «Международный Гуманитарный», и другие.

Мы различаем несколько типов аббревиатур:

  • Акронимы («МГУ», «ОСАГО») — состоят из первых букв образующих их слов. У акронимов, особенно 2-3 буквенных — больше всего вариантов расшифровок. Чем больше неоднозначность акронима, тем меньший вес мы даём ему при ранжировании.
  • Композитные («матмех», «сельхоз») — представляют собой части слов, как правило корни. Иногда корни соединяются дополнительной буквой (как "бензопила" = "бензиновая пила")
  • Пунктуационные («г.», «б/у», «р-н») — когда в состав аббревиатуры входит знак пунктуации.
  • Отделение префиксов, каждый из которых сокращается до начальной буквы: «авто-», «мото-», «все-», «тепло-». Например, так получается «тэц» = "теплоэлектроцентраль"

Как учитывать региональность; как отсекать ложные гипотезы
Помимо многозначности, в этом виде расширений интересен учёт региональности, ведь в каждом регионе у аббревиатуры может быть своя расшифровка. Пользователи из «Мордовии», у которых есть свой «МГУ» ( им. Огарёва), интересуются его московским тёзкой не меньше, чем жители других регионов России. Но региональных данных может оказаться мало, приходится подбирать баланс между местным объектом и его более известным аналогом из другого региона — чтобы было легко найти и тот, и другой.

При сборе вариантов расширений бывает немало ложных гипотез, с которыми мы боремся разными эвристиками:

  • «фото» = "фотография Обамы" (при сокращении все слова фразы должны сокращаться до частей примерно одинаковой длины)
  • "блага дарим" = "благодарим", «маманя» = "мама аня" (одна гласная не может пропадать, как минимум целый слог)
  • "химическая технология природных энергоносителей" = «хтн» (первая буква слова с отделяемым префиксом, «э», также должна присутствовать в аббревиатуре)
  • «сгорел» = "скорее всего ремонту уже не подлежит" (много пропусков, первые буквы вне сокращения)
  • «назой» = «назойливый» (сокращение из одного слова не переводится в столь длинное слово)

Транслитерация (Пежо → Peugeot)


В отличие от аббревиатур, тут интуиция оказывается права: на транслитерацию приходится несколько десятков процентов всей пользы от расширений. У неё хорошая точность и полнота; она хорошо помогает в любом контексте.

Пользователи не любят переключать раскладку на клавиатуре, а при поиске иностранной фамилии или населённого пункта проще набрать их по-русски («Демонжо» вместо «Demongeot» и «Кёльн» вместо «Cologne»), чем вспоминать правильное написание в оригинале. Нередка и обратная ситуация: жителям русскоязычных диаспор за рубежом привычнее общаться в форумах на русском, но с использованием транслита. Искать же по таким форумам нужно и для кириллических запросов. Транслитерация пригождается и когда слово запроса содержится в адресе найденного сайта.

На практике нам нужна даже не транслитерация, а так называемая практическая транскрипция — максимально близкая передача оригинального звучания средствами другого языка. Иначе, например, французские слова будут искажаться до неузнаваемости.

Реализация: по буквам, по слогам, по цепочкам (сегментам) гласных-согласных
Варианты реализации

Ограничимся поверхностным обзором, оставляя нюансы для самостоятельного поста. Самый известный и простой способ — транслитерация с помощью побуквенных правил. Есть несколько стандартов перевода между латиницей и кириллицей, большинство являются взаимно-однозначными (полностью или для почти всех букв). К сожалению, этот метод даёт очень плохое качество для имён — даже «Renault» и «Pegueot» никогда не станут «Рено» и «Пежо».

Более продвинутый способ — по слогам. Перевод каждого слога независимо от контекста работает довольно точно. Но есть сложности:

  1. В каждом языке свои правила деления на слоги, а их реализация с достаточно высокой точностью — нетривиальна.
  2. Одинаковые слоги тоже произносятся по-разному в разных языках, поэтому для каждого языка нужно досконально описать правила.
  3. По этим причинам особенно важно безошибочное определение языка

Метод сегментов

Мы выбрали третий путь, метод разбиения на сегменты. Сегмент — это группа подряд идущих гласных / согласных букв. Нужно найти большое количество примеров пар слов, когда мы достоверно знаем, что одно является транскрипцией другого. И по этим примерам, с помощью машинного обучения, построить правила преобразования одних сегментов в другие.

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

Далее, сегменты транскрипции с соответствующими сегментами оригинала поступают в обучающую выборку: как сами по себе, так и с окружающим контекстом (соседними сегментами). В результате машинное обучение определяет вероятности разных вариантов транскрипции каждого сегмента:
image

О неоднозначности сегментов
Тут есть пара хитростей, из-за которых сегменты могут оказаться не взаимно однозначными. Первая простая: некоторые слова начинаются с непроизносимых согласных, как «L'Humanite» > «Юманите». Такие сегменты переводятся в пустые. Вторая посложнее: в середине слова бывают «беглые» гласные (как в «stat ement» не читается выделенная «e») или согласные (как в «guillaume» выше). С беглыми буквами помогает выравнивание по сегментам с помощью алгоритма Левенштейна: сначала устанавливаем побуквенное соответствие, а затем склеиваем рядом стоящие буквы в сегменты с учётом отличий разбиения слова на другом языке.
image

Из этого примера видно, что «й» правильнее считать гласной. А «ъ», «ь», дефис и апостроф мы считаем согласными — ведь они разрывают звучание.


О качестве

По нашему опыту, метод сегментов даёт самую лучшую точность. Он хорошо работает для всех распространённых языков — в том числе, для таких сложных, как китайский и вьетнамский (разумеется, в их буквенной записи). И даже позволяет с приемлемой точностью восстановить из русского написание на оригинальном языке. При этом метод не требует определения языка слова.

На тестовых коллекциях имен-фамилий, географических названий, популярных брендов и названиях музыкальных коллективов метод показывает точность до 99%. Если же оценивать точность на всём наборе гипотез, которые расширяются по реальным запросам и поисковому индексу, она падает по мере того, как мы увеличиваем словарь всё менее точными гипотезами. Сейчас пользователям доступны порядка 3 млн расширений на базе транслитерации, на них точность составляет около 90%.

Орфографические варианты (икея → икеа)


Орфоварианты — это слова, которые имеют идентичное значение, а писаться могут и так, и эдак, причём оба написания считаются грамотными.

Во-первых, это иностранные слова, которые записываются со слуха, и часто не имеют единственного канонического написания («ике я» / «ике а»; «толк иен» / «толк ин»).

35 способов написать Scarlett Johansson

«скарлетт йоханссон»
«скарлетт йохансон»
«скарлет йоханссон»
«скарлет йоханссен»
«скарлетт джоханссон»
«скарлетт джохансон»
«скарлет йохонсон»
«скарлет йохансон»
«скарлет йоханнсон»
«скарелтт йоханссон»
«скарлетт йоханссен»
«скарлетт йоххансон»
«скарлет йохансен»
«скарлетт ёханссон»
«скарлетт йоханнсон»
«скарлет йохансан»
«скарлет джохансон»
«скарлетт йохансоон»
«скартлетт йоханссон»
«скарлетт йханссон»
«скарлетт йохассон»
«скарлетт йохансен»
«скарлет ёхансен»
«скарлет ехансен»
«скарлет джохэнсон»
«скарлетт йохансан»
«скарлетт йоанссон»
«скарлет йохенсон»
«скарлет иоханссон»
«скарлет ёхансон»
«скарлет ехансон»
«скарлет ёхансан»
«скарлетт джохэнссон»
«скарлетт йохансонн»
«скарлет джоханссон»


В отличие от транслитерации, тут мы имеем дело с парами на одном языке. Несколько слов, которые с помощью транскрипции можно привести к одному латиническому написанию, называются орфовариантами.

Во-вторых, русские слова, допускающие разные написания («бил ьярд» → «билл иард», «день рожден ия» → «день рожден ья»)

Чем интересны орфоварианты?

Нужно отличать их от опечаток и падонкаффского сленга. А ещё бывает устаревшее написание.
  1. Нужно чётко разделять их с опечатками:
    • для опечаток пользователь привык видеть явное сообщение: «В запросе была исправлена опечатка» и иметь возможность переключиться на поиск оригинального запроса. Для орфовариантов такое предупреждение будет неуместным, т.к. все возможные написания являются допустимыми.
    • когда мы уверены, что пользователь опечатался, мы просто заменяем запрос на правильный. Для орфовариантов так делать нельзя, мы потеряем большую часть полезных документов с другим написанием («рожденья» вместо «рождения»). А вот расширять другими написаниями будет правильно. В отличие от опечаток — там неграмотные документы могут расстроить пользователя, задавшего запрос без ошибок.

  2. Важно уметь отличать орфоварианты от интернет-сленга («падонкаффский / олбанский йезыг») и мемов («котеги»; «котэ»). Сленговые и общепринятые написания нельзя расширять друг другом:
    • по запросу с мемом нельзя показывать документы с общеупотребимым написанием, они будут мешать интересующемуся мемом;
    • и наоборот, если подмешивать к общеупотребительному написанию его аналоги-мемы, это будет ухудшать выдачу по запросам на «общечеловеческие» темы.

Благо, у сленга довольно специфический контекст использования, это помогает отличать его от орфовариантов.

Особняком стоит третий тип — устаревшее написание: «великодержавнаго», «благочестиваго» (например, «царя»). Благодаря расширениям находятся и оригинальные древнерусские тексты с параллельным переводом на современный язык, и сами переводы без оригинала — последние неподготовленному читателю легче распечатать и читать.

Словообразование (Москва-московский)


Описанные выше виды расширений (аббревиатуры, транслиты, словоизменение, орфоварианты) старались отражать точные слова запроса всеми возможными способами, считая смысл неприкосновенным. Но быстро стало понятно, что нужно смелее допускать смысловые добавки к исходному запросу. Так расширения пополнились словообразованием («моск ва метро» → «моск овское метро») и синонимами («бегемот» → «гиппопотам»).

Идея расширения по принципу словообразования состоит в добавлении к запросу однокоренных слов, включая даже другие части речи («моск ва метро» → «моск овское метро»).

Механизм словообразования зачастую называют просто морфологией, хотя это не совсем верно: кроме слово образования к морфологии относится и слово изменение (то самое «Брич-Муллою»). Словоизменение крайне редко добавляет к запросу новые смысловые оттенки, обычно оно ищет оригинальное слово запроса во всех формах (как говорят, «всю парадигму»), поэтому в этом посте мы его не затронем.

Словообразование, напротив, может добавлять семантически далекие варианты — вопреки общим соображениям, слова с одним корнем не обязаны быть близкими по смыслу. Лишь малое число типов словообразования оказывается на практике хорошими поисковыми расширениями, поэтому нужно быть аккуратными.

Несколько примеров
Среди полезных типов — <существительное> → <однокоренное прилагательное>, например «Москва» → «московский»: «мэр москвы» → «московский мэр». Но даже здесь есть свои тонкости, в первую очередь связанные с именованными сущностями:
  • названиями организаций: [универмаг Москва] ≠ [универмаг Московский], в Москве это два разных магазина, оба весьма известные
  • фамилиями людей: у чиновника, который работает в правительстве, может оказаться фамилия «Московский» — и это повлияет на запрос [Московский правительство]
  • географическими названиями: в Подмосковье есть город «Московский» — для него запрос [Московский мэр] значит не то же самое, что [мэр москвы]

Пары <существительное> → <имя деятеля> («велосипед» → «велосипедист») — сильно уводят от смысла первоначального запроса. Если <существительное> → <прилагательное> «велосипед» → «велосипедный» полезно (например, [покупка велосипеда] → [велосипедный магазин]) — то «велосипед» → «велосипедист» ухудшит поиск, потому что по запросу [покупка велосипеда] в выдачу будет добавляться, например, документы про «посадку велосипедиста», про «травмы велосипедиста» и т.п.
  • [занятие по рисованию]: хорошо расширить словом «рисовать», но плохо «рисовальщик»
  • [зам командующего по тылу]: хорошо «тыловой», плохо «тыловик»
  • [заказ мулине в Украине]: хорошо «заказывать», плохо «заказчик»

Аналогично, есть масса плохих примеров на смену рода. Возьмём «работник» → «работница»: если запрос [соглашение с работником] даёт широкий класс документов о любых предметах договорённостей, то расширяя его словом «работница», в выдачу попадают нежелательные документы, например про нормативную базу о выходе в декрет (которая с общим случаем про любого работника, скорее всего, не поможет).

Таким образом, схожесть слов по форме часто бывает обманчивой, и с точки зрения поиска содержание очень сильно меняется даже с самыми, казалось бы, невинными преобразованиями.


В других языках всё бывает иначе
Любопытно, что русский язык далеко не всегда оказывается самым сложным с точки зрения словообразования. Например, в турецком однокоренные слова с формально другим смыслом оказываются просто частью одной словарной парадигмы:
  • «yüz» — сто, «yüzde» — процент,
  • «top» — мяч/ядро, «topçu» — футболист/артиллерист.

И если в русском мы можем безболезненно использовать все формы того слова, для которого подготовили расширение — то в турецком приходится рассчитывать контекстную близость не между разными словами, а между формами одного и того же слова. И ограничивать использование далёких форм того же слова, чтобы не допускать искажений смысла.

Синонимы (мобильный → сотовый)


Можно ли взять за основу академические синонимы из традиционных словарей, и просто загрузить их в поиск? Ведь в словарях собраны обширные ряды надёжных синонимов.
Оказывается, поисковый язык совершенно не такой, как нормативный письменный.
Часто словари дают точные синонимы, но снабжают их стилистической пометой: арх., разг., науч., поэт. А некоторые слова, даже будучи современными и, формально, общеупотребительными, используются в письменной речи лишь в некоторых смыслах или жанрах:
  • «волшебник» → «колдун»: второй употребляется преимущественно в фольклорных текстах, и только в негативном ключе
  • «подъезд» → «парадное»: второй не используется в официальных адресах; ограничивает круг документов петербуржским регионом — по происхождению или месту действия.
  • «врач» → «медик»: второй используется преимущественно для профиля образования, но не для обозначения профессии или вида услуги
  • «дрессировщик» → «укротитель»: второй имеет дело только с опасными животными
    В результате человек получит документы с ярко выраженной стилистикой (архаичные / научные / диалектные...), чем хотел — что не всегда будет полезно в решении его задач.

Поэтому мы ушли от чисто словарного, лингвистического понимания синонимов, гораздо лучше работает статистический поиск эквивалентов. Собираются любые варианты, которые могут не быть синонимами в академическом смысле, но помогают найти то, что пользователь ищет. Именно это и является главным критерием качества — полезность расширений для ранжирования (а не их словарная близость по смыслу).

Но и коллекции статистически собранных синонимов в традиционном смысле (как слов с идентичным значение) бывает мало. Для узкоспецифичных запросов, по которым в интернете чрезвычайно мало информации, бывает полезно заменить некоторые слова запроса на более общие понятия ( «гиперонимы»).

Пример замены общим; почему нельзя заменять общее частным
Например, запрос [конъюнктивит у цвергшнауцеров]: у слова «цвергшнауцер» есть очень точный синоним «цверг», но его добавление не сильно улучшит выдачу. Зато если добавить его обобщение на правах расширения, [конъюнктивит у собак], найдётся много полезного, ведь манипуляции по уходу и лечению похожи для разных пород собак.

А в обратную сторону, от общего к частному, расширять рискованно. Запросом [одежда для детей] разные пользователи ищут магазины для различных возрастов, поэтому будет правильнее всего показать максимально универсальные сайты, покрывающие весь возможный спектр разных ситуаций пользователя. Если мы будем пытаться расширять запрос более частными понятиями «школьник» или «младенец», это может осложнить пользователю решение его задачи.

Как собрать варианты расширений


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

Из рассказанного выше легко догадаться, что варианты возможных расширений для наших нужд можно построить только через анализ реальных данных, существующих «в диком виде» в интернете. Отвечать на запрос пользователя нужно быстро, поэтому мы готовим такие варианты (т.н. «словарь расширений») заранее — а в момент поиска просто выбираем из готового словаря все пары для слов запроса.

Сбор гипотез

Для составления словаря мы используем ряд источников:

Для русского языка это даёт порядка 150 млн пар — гипотез расширений.
Частотная фильтрация

Пары, которые встречаются слишком редко и в запросах, и в текстах в интернете — не очень достоверный источник, поэтому после сбора гипотез мы ограничиваем их по частоте встречаемости.

Нет особого смысла и как-либо учитывать форму (падеж, склонение), в котором слово встретилось вместе с той или иной парой (по крайней мере, для русского языка). Поэтому мы оставляем единственную форму слова (как правило, начальную).

В результате этого обычно получается порядка 100 млн пар.

Отбор самых вероятных расширений

Но 100 млн сырых гипотез — это руда, которую нельзя просто отдать на этап обработки запроса.
Нет смысла помогать высокочастотным запросам; нужно исключать далёкие по смыслу замены
  1. Мы отбираем расширения, которые сильнее всего помогают пользователю. Ценность расширений напрямую зависит от частотности запроса. Для высокочастотных запросов у нас много различных данных, и добавление даже большого числа расширений практически не меняет ранжирования. А в случае запросов редких либо сформулированных с ошибкой вклад расширений в улучшение выдачи очень заметный — именно их и стараемся расширять прежде всего.
  2. Даже для нечастотных запросов нужно балансировать качество и скорость ответа на запрос. В идеале нужно расширять любой запрос максимально широким облаком расширений — и этап ранжирования выберет именно то, что действительно улучшает релевантность выдачи. На практике же размер облака приходится ограничивать ради скорости ответа — удаляя варианты, далёкие по смыслу от оригинала.

Как многое другое в этой теме, степень близости по смыслу расчитывается машинным обучением.

С одной стороны, для каждой гипотезы расширения (A, B) мы вычисляем порядка 60 факторов, которые так или иначе коррелируют с тем, что гипотеза являются полезным расширением. В числе этих факторов — контекстная близость, построенная на N-граммах; выбор пользователем одних и тех же документов по разным запросам; расстояние Левенштейна (например, для орфовариантов).

С другой стороны, специальные эксперты ( асессоры) готовят обучающую выборку характерных примеров «какое слово B является хорошим расширением слова A, а какие пары недопустимо считать синонимичными».

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


В результате этого отбора мы получаем 10 млн расширений — и этот «словарь» используется при обработке запросов. Об этом поговорим в следующем разделе.

image

Как расширения участвуют в поиске


Получив от пользователя поисковый запрос, мы выбираем из словаря расширения, подходящие по контексту.

Например, [мгу] расширилось в [мгу ^ mgu ^ msu ^ «московский государственный университет»].

А уже по расширенному запросу поиск находит документы с различными вариантами формулировок, включая оригинальную («точную форму»). В ранжировании документов участвует множество факторов, учитывающих и оригинальное слово, и расширения. При прочих равных совпадение точной формы («мгу») более приоритетно, чем вхождение расширения (даже полного написания, как «московский государственный университет») — хотя другие факторы могут оказаться сильнее точного совпадения.

image

Мы стараемся подсвечивать в сниппетах не только слова запроса, но и все используемые синонимы, что помогает пользователю понять, почему он видит тот или иной документ.

Как определить, какие расширения уместны для данного запроса, а какие нет; что именно, в каких случаях и в каком объёме добавлять? Чем больше видов расширений, тем сложнее построить алгоритм их замешивания. Обычно начинают с подобранной вручную логики ветвлений и коэффициентов, а когда их становится слишком много — ищут качественно другой способ. По нашему опыту, сложную логику не получается развивать уже после первого десятка факторов: становится слишком трудоёмко подбирать параметры, чтобы рост одного показателя качества не оборачивался сравнимым падением другого. Не так давно мы возложили решение этой задачи на машинное обучение, что позволило быстрее добавлять новые факторы и на 20% повысило вклад расширений в качество поиска. Получившийся механизм мы назвали «контекстной моделью».

На каких факторах и примерах она работает
Модель, как и в случае с любым машинным обучением с учителем, опирается на примеры от экспертов (асессоров) и на факторы, с помощью которых эти примеры экстраполируются на любые другие случаи.

Основные признаки, используемые для определения уместности расширения:

  • число слов в запросе и в расширении;
  • насколько это редкие слова;
  • тематика запроса;
  • вид расширений (из перечисленных выше разделов) — тоже класифицируется автоматически;
  • степень корреляции в текстах между словом запроса и расширениями (т.н. Mutual Information) — насколько часто они встречаются вместе.

Для наиболее характерных запросов асессоры размечают, какие варианты синонимов будут хорошим расширением в данном контексте, а какие плохим. Ведь в каких-то случаях можно дополнять запрос максимально, а в каких-то только заведомо «непортящими» расширениями.

В результате контекстной фильтрации из всех расширений, возможных для всех слов запроса, остаётся 27% пар, которые уместны именно для данного запроса.

image

Есть несколько больших классов запросов, контекст которых делает неуместным большинство расширений:

Имена собственные; цитаты; многозначные слова
  • имена собственные:
    [ООО Бегемот] → [ООО Гиппопотам] (хотя можно «повадки бегемотов» = «повадки гиппопотамов»)
    [лодка ветерок цена] (хотя можно «легкий ветерок» = «легкий бриз»)
  • точные цитаты. Вот чем могли бы расшириться известные фразы:
    [мой дядя самых честных правил] → «дядечка, мужчина, дядько»; «наиболее»; «чистосердечный»; «кодекс, регламент, регулярность, стандарт, установленный порядок»
    [все смешалось в доме Облонских] → «всякая, каждый, итого»; «домашний»; «здание», «постройка»
  • терминологические значения общеупотребительных слов — когда расхожее слово означает также ускоспецифическую вещь:
    [монтёрская кошка]
    [тормозной башмак]
    Только если из запроса удалось понять, что слово встретилось в узкоспецифическом смысле, его можно расширить обобщающим термином («монтёрская кошка» → «монтёрское снаряжение»).
  • более широко, вообще многозначные (омонимичные) исходные слова. Примеры, почему их нельзя расширять:
    [Приказ о назначении председателя ОСМД]: «назначении» → «предназначение»
    [заставки на рабочий стол]: «стол» → «столик»
    [как очистить картину написанную маслом]: «написанную» → «пишущий»
    [феномен личности на конкретном примере]: «примере» → «задача»
    [средняя зарплата дворника]: «дворник» → «щетка»
    [гражданское общество]: «гражданский» → «незарегистрированный» (напр., «брак»)
    [где взять выписку из домовой книги]: «взять» → «приобретать»
    [тост на французском языке]: «тост» → «сухарик» (в запросе [тост] — в значении «речь во время застолья»)

Определение каждого класса «что нельзя расширять» также обеспечивается машинным обучением — на основе большого числа примеров от асессоров.

Подробнее о многозначных словах

Если слово многозначно, его можно расширять синонимами только к тому значению, которое подразумевалось в запросе. В противном случае мы испортим выдачу документами с кардинально другим смыслом, что может раздражить пользователя, и уж точно ему не поможет. То же правило верно в обратную сторону, когда однозначное слово расширяется многозначным.

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

Подробнее об именах собственных

Имена собственные требуют особой аккуратности. Если опираться только на контекстную близость, то «МТС» и «Билайн», «Google» и «Яндекс», «ВКонтакте» и «Facebook» ведут себя как синонимы. И в случае Билайна, и в случае МТС пользователей интересуют одинаковые аспекты: «смс», «личный кабинет», «интернет», «тарифы», «роуминг». А при выборе сотового оператора они задают одинаковые запросы (тарифы, зона покрытия и т.п.), меняя только название компании — что неотличимо от классических переформулировок запроса синонимами.

Но примеры, в которых замена вроде «МТС» → «Билайн» действительно помогает лучше ответить на запрос пользователя, встречаются довольно редко. В подавляющем большинстве случаев такая замена не только не помогает, но и выглядит глупостью. Например:
image
(да простят нас коллеги за эту соринку — у себя мы интересного бревна не нашли)

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

Как мы действуем с синонимами для имён собственных

Мы стремимся расширять имя объекта только когда уверены, что расширение является альтернативным обозначением его же (например, уменьшительно-ласкательными «Вконташа» → «Вконтакт» или разговорными «керосинка» → «РГУ нефти и газа»), а не названием другого объекта. Научить алгоритм отличать одно от другого непросто, как и достоверно определять, что первоначальный объект вообще является именем собственным. Мы учим автоматику различать имена собственные разных объектов на примерах от асессоров и данных Википедии: если в Википедии для каждого из наших слов существует собственная статья, это с большой вероятностью означает, что мы имеем дело с разными сущностями.

Учёт языка запроса

Обычно расширения предлагаются именно для того языка, на котором задан запрос. Но что если есть основания полагать, что пользователь понимает и другой язык, а результатов на нём существенно больше? Тогда разумно предложить документы на этом языке. Например, украинский запрос [в'язання схеми] можно расширить русским [вязание схемы], по которому в разы больше хороших результатов.

Качество расширений и качество поиска


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

Очень упрощённо, поиск как процесс состоит из двух основных этапов: фильтрация и ранжирование. Фильтрация отбирает из индекса документы, сколько-нибудь полезные для заданного запроса, ранжирование упорядочивает их по релевантности.

Механизм расширений — ключевой участник этапа фильтрации. Расширения находят все возможные замены, и ранжирование умеет выбрать из них то, что действительно будет полезно пользователю.

Поэтому ключевой параметр качества механизма расширений — полнота словаря возможных замен. Ради неё мы готовы давать даже неграмотные расширения, если они помогают пользователю найти нужное. Например, «war kraft» — неканоническое название (правильно «War craft»), но какое-то время назад оно было очень распространено на геймерских форумах — и по некоторым запросам (вроде [варкрафт прохождение]) расширение «варкрафт» → «war kraft» позволяло найти то, что не удавалось найти без него.

Если расширение помогает найти нужное, нам не важна его «правильность», «грамотность» или «каноничность», даже академическая близость по смыслу к оригинальному запросу.

Следим за качеством расширений и до передачи в поиск, и в самом поиске

Но даже несмотря на то, что ранжирование очень терпимо к неполезным расширениям, мы предпочитаем перестраховываться и отдельно следим за качеством самих расширений ещё до их попадания в поиск. Всякий раз, когда мы внедряем какое-то изменение в расширениях, мы не только стремимся к бо́льшей полноте самих расширений, но и аккуратно смотрим, чтобы не упала их точность. Если метрика совокупного качества поиска оценивает отсутствие плохих результатов на первой странице выдачи, то собственная метрика качества расширений помогает исключать раздражающие расширения вообще из результатов поиска.


Как измерять качество расширений и поиска в целом
Мы пока не нашли достоверную метрику качества самих расширений относительно других поисковых систем, которая бы одновременно и походила на наши интуитивные оценки и основывалась на реальных ожиданиях пользователей (а не на умозрительных примерах). Поэтому мы руководствуемся совокупной оценкой качества поиска pfound. Она оценивает вероятность, что пользователь найдёт то, что искал, взятую в среднем по всему потоку запросов, задаваемых Яндексу. Для каждого запроса метрика суммирует полезность первых документов, показанных на выдаче — с поправкой на то, насколько высоко документ отранжирован. Чем ниже он на выдаче, тем меньше его вес в метрике — вероятность, что пользователь до него доберётся. Полезность каждого документа в контексте запроса мы оцениваем по оценкам от асессоров:
image
Здесь: pRel — релевантность i-того документа (вероятность того, что пользователь найдет ответ в этом документе). pLook — вероятность просмотра i-того документа в выдаче.

Мы надеемся, что расширения работают на то же благо, что и все остальные компоненты поиска. Собственный вклад расширений в совокупное качество поиска довольно существенный — он составляет несколько процентов. То есть, если очень сильно упрощать, в день несколько миллионов запросов к Яндексу получают качественный ответ исключительно благодаря расширениям. А тем или иным образом помогают в ответе они на 30% всего потока запросов в Яндекс, причём на 15% потока — дают ощутимое улучшение.

Литература


  1. Евгений Соловьёв, Тезаурусные расширения в информационном поиске. Яндекс, 2010 (презентация).
  2. Voorhees, Query Expansion using Lexical-Semantic Relations — автор одной из первых добилась улучшения результата на TREC при помощи расширений из WordNet.
  3. Jones et al. Generating Query Suggestions — как в Yahoo! решали проблему увеличения полноты поиска по рекламным объявлениям.
  4. Dang, Xue, Croft. Context-based Quasi-Synonym Extraction — сбор синонимов при помощи корпуса N-грамм (например, такого).
  5. Dang, Croft. Query Reformulation Using Anchor Text — пример использования статистики по приссылочным текстам для сбора расширений от Microsoft Research.
  6. Р.С. Гиляревский, Б.А. Старостин. Иностранные имена и названия в русском тексте. М., Высшая школа, 1985 — о практической транскрипции.