Компания
498,21
рейтинг
22 июля 2013 в 13:50

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

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

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

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

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

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

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

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

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

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


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

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

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

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


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


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

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

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

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

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

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

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

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

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

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

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

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

О качестве

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

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


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


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

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

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

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

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

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

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

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


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


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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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


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


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

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

Сбор гипотез

Для составления словаря мы используем ряд источников:
  • скобочные написания в документах: «Скарлетт Йохансон (Scarlett Johansson)»
  • встречаемость обоих слов в одинаковых контекстах (N-граммах — цепочках из N подряд идущих слов: "… билетов в театр": «цена» → «стоимость») — отдельно в текстах, отдельно в запросах. Её иногда называют «статистика взаимозаменяемости».
  • ссылочные — когда несколько ссылок, ведущих на одну и ту же страницу, называются по-разному: «магазин велосипедов → веломагазин»
  • параллельные тексты (размеченные с помощью машинного выравнивания)
    Наш сервис машинного перевода обучается на так называемых параллельных текстах — парах «текст и его перевод», между которыми статистическими методами размечено соответствие предложений, словосочетаний и слов, означающих одно и то же. Такой переход одного слова в другое мы считаем хорошей гипотезой для расширения запроса.
  • пользовательские статистики — как часто пользователь пытается переформулировать запрос с использованием данной замены, и документы с какими синонимами к слову запроса предпочитает
  • традиционные словари синонимов, другие словарные источники
  • Wikipedia: для какого термина стоит перенаправление на другой термин

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

Частотная фильтрация

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

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

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

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

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

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

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

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

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

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

image

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


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

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

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

image

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

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

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

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

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

image

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

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

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

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

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

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

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

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

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


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

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


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


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

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

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

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

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

Как измерять качество расширений и поиска в целом
Мы пока не нашли достоверную метрику качества самих расширений относительно других поисковых систем, которая бы одновременно и походила на наши интуитивные оценки и основывалась на реальных ожиданиях пользователей (а не на умозрительных примерах). Поэтому мы руководствуемся совокупной оценкой качества поиска 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 — о практической транскрипции.
Автор: @yurkennis
Яндекс
рейтинг 498,21

Комментарии (28)

  • –4
    Научите пожалуйста Yandex отличать Сокольники от Сокол, а запрос «Купить пиццу» от «Купить проститутку». Ну невозможно так дальше. Пруф versusit.ru/google-vs-yandex
    • +5
      это вброс или сарказм?
      но всё-равно отвечу, пожалуй.
      яндекс не перепутал сокол и сокольники. он выцепил не из заголовка, а из текста, да, но более ничего.
      и «купить проститутку» — просто был мусорный сайт с ключевыми словами, его убрали.

      • +1
        Вот я забыл как зовут певца «Moby», и вначале протестировал коллег — спросил — «лысый белый певец с очками, зарубежный». Один в шутку сказал — Элтон Джон. Так вот оказалось гугл также думает, что это Элтон Джон :) У Яндекса в картинках нашло. У Yahoo, Bing, Duckduckgo на втором месте упоминание какое-то.
        • 0
          Ну теперь-то в гугле на первом месте ваш комментарий )
  • 0
    Мы стараемся подсвечивать в сниппетах не только слова запроса, но и все используемые синонимы, что помогает пользователю понять, почему он видит тот или иной документ.

    Часто кроме синонимов выделяются дополнительные слова, например для «вечерний макияж» это «самостоятельно», «фото» — как выбираются такие слова?
    • 0
      Совершенно верно, спасибо за наблюдение.

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

      Это часть механизма «интентный поиск»: clubs.ya.ru/company/55417
      • 0
        Тогда если можно еще один вопрос. Возьмем поисковый запрос «телевизор», по нему в результатах поиска подсвечиваются «купить» и «смотреть онлайн», т.е. это различные намерения пользователя. Вы пишите, что акронимы учитываются при ранжировании документов:
        У акронимов, особенно 2-3 буквенных — больше всего вариантов расшифровок. Чем больше неоднозначность акронима, тем меньший вес мы даём ему при ранжировании.

        А как обстоят дела со словами, которых нет в запросе пользователя, но которые выражают возможные намерения? Имеются ввиду те слова, которые выделяются в сниппетах, в данном примере это «купить» и «смотреть онлайн». Использование этих слов в тексте документа оказывает влияние на его релевантность запросу? Если да, то может возникнуть интересный курьез. Все тот же запрос «телевизор» в результатах поиска есть страница интернет-магазина на которой пользователю предлагают совершить покупку (потребность «купить»), если добавить на эту же страницу слова «смотреть», «посмотреть», «онлайн», то получится, что данный документ с точки зрения текстовой релевантности начинает отвечать сразу 2 потребностям (просмотр онлайн и покупка), хотя на деле это может быть совсем не так. Учитывается ли данный момент?
        • 0
          Отвечает ли страница интенту — Яндекс определяет не по ключевым словам. Поэтому, если вас беспокоит, что конкуренты будут насыщать текст страницы словами интентов, не волнуйтесь — с точки зрения ранжирования это бессмысленно.

          Но вообще ваш вопрос относится к интентам — которые похожи на обсуждаемые здесь расширения лишь тем, что тоже подсвечиваются в сниппетах.
          • 0
            Можете тогда уточнить еще один момент. В сниппетах подсвечиваются только «синонимы» и «интенты», или может быть что-то еще?
            • 0
              Подсвечиваться могут любые элементы сниппета, которые, с нашей точки зрения, помогают пользователю выбрать страницы, наиболее полезные в решении его задачи.
  • +1
    Большое спасибо за интересный и информативный пост.

    Не могли бы вы, на основании поста подсказать, как попадают следующие сайты в выдачу по написанным ниже запросам?

    «тренажер Гоша Воронеж» (робот тренажер для оказания первой помощи) — кроме нормальных результатов выдаются вакансии компании «Рив Гош».
    «купить глобус Воронеж» — 1 турагентство, 1 туроператор, 2 сайта про тороговый дом и 1 про книжный магазин. В названии у всех фигурирует глобус.
    «купить скелет человека Воронеж» — новость о том, что в Воронеже нашли скелет человека.
    «Стерилизатор Воронеж» (явно же имеется в виду прибор) — выдаются сайты о стерилизации кошек
    «купить географические карты Воронеж» — зачем в запрос подмешиваются Яндекс-Карты?
    • 0
      Даже про глобус более общо спрошу:
      Когда идет запрос «купить+название товара+город», то зачастую выдаются компании, в названии которых есть название товара.
      Вот ещё примеры таких запросов:
      «купить морковь воронеж»
      «купить магнит воронеж»
      «купить ландыши воронеж»
      «купить лес воронеж»
      Почему так получается? Неужели Яндекс допускает, что человек, по запросу «купить морковь воронеж» хочет заказать услуги в агентстве Любовь-Морковь?
      • +2
        Из перечисленных примеров к расширениям относится разве что стерилизатор. Это хороший пример ошибки на имя деятеля (в данном случае инструмента). Мы расширяем слово, используемое в одном контексте (стерилизатор для бутылочек), другим словом, которое имеет отношение уже ко множеству контекстов (стерилизация кошек, банок). В идеальной ситуации должна была сработать контекстная модель, которая бы исключила это расширение в контексте данного запроса. Но она ошиблась.

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

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

        В любом случае, спасибо за фидбек!
        • +1
          Вам спасибо за обстоятельный ответ!

          Про контекст — был ещё один запрос, который теперь показывается правильно. «Кружки воронеж» (кружки из которых пьют, имелось в виду).
          Год назад примерно, по этому запросу выходило 10 сайтов ночных клубов(и подсвечивалось слово клуб).
          Я правильно понимаю, что сначала использовался Матрикснет и в общую выдачу добавлялись сайты о крУжках и о кружкАх, потом срабатывали синонимы (кружкИ -> клубы), в выдачу добавлялись сайты клубов(всяких). А потом все это вместе ранжировалось и сайты ночных клубов, как наиболее продвигаемые, выходили на первые позиции?
          • +2
            Совершенно верно, у нас был ошибочный синоним кружки-клубы. Теперь вы даже знаете, что к его появлению привела близость контекстов, в которых эти два слова встречаются.
        • 0
          Вот вы ещё говорите про определение ролей объекта. Это что-то типа запросы «избитые милиционерами» и «избитые милиционеры»? (извините за пример, ничего лучше в голову не пришло)
          Меняются роли и выдача должны быть совершенно разная. Сейчас же там все вперемешку.
          • 0
            Очень тонкое замечание, тут действительно объекты выступают в разных ролях. Немного улучшить выдачу в данном случае помог бы более жесткий приоритет точной формы, но вмешиваются другие факторы ранжирования. Однако данная проблема не связана напрямую с поисковыми расширениями, об учете синтаксических связей в запросе мы расскажем в другой раз.
  • +1
    Всё супер, ИИ рулит, поиск фореве.

    Но, БЛИН, КАК ОТКЛЮЧИТЬ всю эту машинерию, когда она гонит туфту??? Как ею управлять?

    Вот у nigma.ru/ в результатах поиска все их расширения в левой колонке выводятся, можно выключить неважные, запретить отвлекающие — очень здорово. Как минимум, увидеть их все. Очень здорово.
    Скажите, у них патент на это? Что вам мешает сделать так же и даже лучше?
    • 0
      Мы даем возможность управлять выдачей, когда знаем, что меняем ее радикально — т.е. большинство результатов найдены не по исходным словам запроса, а по расширениям. В этом случае цена ошибки очень велика, и мы даем пользователю поискать точно так, как он нас спросил.

      Например, с теми же цвейгами из статьи — в начале выдачи есть приписка:
      В выдачу по запросу «конъюнктивит у цвергшнауцеров» были добавлены результаты по похожим запросам. Искать только «конъюнктивит у цвергшнауцеров»
      Аналогичные подсказки есть в случае опечаточного исправления.

      Но даже такие подсказки оказываются редко востребованы пользователями.
      • 0
        А как вы оцениваете результативность выдачи? Как определяете степень удовлетворения пользователя вашими эвристиками?
        • 0
          Уточню: вы говорите о результативности работы конкретно расширений, или об удовлетворённости пользователя результатами поиска в целом?
          • 0
            А разве «результативности работы конкретно расширений» может оцениваться иначе, как через влияние на «удовлетворённости пользователя результатами поиска в целом»?
            • +1
              А разве «результативности работы конкретно расширений» может оцениваться иначе, как через влияние на «удовлетворённости пользователя результатами поиска в целом»?

              Качество расширений может оцениваться, например, их точностью и полнотой (и, конечно, их комбинацией — мы используем F-меру).

              Результативность расширений мы оцениваем как их вклад в совокупное качество поиска.

              Для измерения совокупного качества поиска мы используем метрику pfound (см. популярный и подробный рассказ), в ней на расширения приходится несколько процентов. Pfound — не единственная метрика, основанная на оценках асессоров, известны также nDCG и другие.

              Используем и анализ поведения пользователей, например метрику TDI и A/B тестирование (совсем популярно про них недавно рассказывал Илья Сегалович).
              • 0
                За ссылки — спасибо. Но по сути — 8-О…

                F-мера требует измерения «полноты» и «точности». А вот их оценить — задачка не однозначная ни разу. «Оценка совокупного качества поиска» — того же поля ягода. Вы вот pfound используете.

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

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

                (Поиск с опорой на личную историю поиска — тоже возмутил — это же палка о двух концах! Этой фичей вы искусственно сужаете кругозор пользователя, делаете вид, что интернет у него маленький. А потом оказывается, что маленький интернет у каждого свой. Как пользователю найти что-то новое, если вы новое от него прячете?)

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

                В выступлении Ильи Сегаловича упоминается «система проверки качества на поисках.»

                Дальше она раскрывается, в частности так:

                TDI: «Делается простое действие. Вместо того, чтобы показывать систему А одной группе пользователей, а B — другой, результаты смешиваются. При смешивании выдачи двух систем, с разной вероятностью подставляя либо систему А, либо систему B, такой способ оказывается лучше потому, что Яндекс одному и тому же пользователю показывает сразу две выдачи, и пользователь выбирает тот результат, который ему нравится. Так улучшается и меняется формула выдачи для того, чтобы она удовлетворяла пожеланиям реальных людей, а не чьим-то представлениям о прекрасном. „

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

                Дальше проскакивает фраза “кликабельность с учетом персонализации выросла на 5-6%». Это ещё одна метрика, ранее не упоминавшаяся. Неужто считается, что чем больше ссылок со страницы выдачи откроет пользователь, тем лучше? Или это иначе посчитанное то, что дальше описано как «Если при поиске на треть чаще выбирается первый результат — это значительный прорыв.»?

                Идеальный поиск, на мой взгляд — это тот, что выдаст первой строкой самое релевантное для меня, если оно есть, а в остальных — представит максимально широкий обзор аналогов и альтернатив, и позволит его уточнить и скорректировать. Но первое и второе — слабо достижимо, хоть вы к этому и стремитесь, а третье — вы почему-то не даёте. Вот как посмотреть, какие библии бывают, если все самые хорошие поисковики показывают только христианскую, и считают это большим достижением?
                • +1
                  Вы совершенно правы. И у методов основанных на асессорских оценках, и на поведении конечных пользователей, есть масса ограничений — связанных прежде всего с человеческим фактором. Мы их прекрасно знаем и осознаём. Пока в отрасли не найдено более совершенных способов измерения, хотя исследования в этой области активно ведутся.

                  Из инструментов корректировки и уточнения выдачи мы уже упоминали интентные подсказки — с ними мы собираемся действовать смелее, давая возможность сортировать выдачу не только по интентам пользователя, но и по основным параметрам объекта, например цене, актуальности и т.п. Кроме того, у нас давно есть связные запросы. Этот механизм мы тоже будем развивать, и его репрезентативностью планируем заниматься.
    • 0
      Ух ты, как у Нигмы интересно сделано, оказывается.
  • 0
    Есть такая модель автомобиля (продается в России) — Ставик. Но Яндекс из него делает «ставки»

    yandex.ru/yandsearch?text=ставик
    • 0
      Да, имеет место ошибочное автоисправление опечатки. Марка машины редкая, а слово «ставки» очень частотное. Тем не менее, возможность поискать «Ставик» остается за ссылкой:
      В запросе «ставик» была исправлена опечатка

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

Самое читаемое Разработка