Автор: Евгений Трофименко

Илья Сегалович в своем ЖЖ дает ссылку на статью Яндекс на РОМИП-2004. Некоторые аспекты полнотекстового поиска и ранжирования в Яндекс.
Ну наконец-то что-то полезное.
Хотя многое было интуитивно понятно.
По пунктикам:

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

– “ограничения контекста” – я сначала подумал, что речь идет о расстояниях в предложениях и словах, которые вставляет колдунщик. Но в конце статьи промелькнуло, что еще в пределах документа – один из возможных контекстов.
Кстати, в ЖЖ Илья объясняет подробнее про это:

Теперь о логическом уровне. О нем говорится фразой “многоместный оператор AND”. Ну то есть мы не делаем так: A /1 B /1 C => X = (A /1 B); Y = X /1 C

Пример:
Опорные слова в пассаже (1) выглядят так: _ _ a b a c _ _
Опорные слова в пассаже (2) выглядят так: _ _ a b c _ _

Двуместная логика при упрощенной реализации может привести (и приводило годах в 1995-1996) к нахождению лишних пассажей. Скажем, по указанному выше запросу может быть найден не только пассаж (2) но и пассаж (1). А ведь слова B и C должны стоять рядом!

Что касается неявного назначения контекста, то мы про это писали: контекст назначается как правило, не пользователем, а на стадии препроцессинга запроса.

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

Принципиальной особенностью Яндекса является оперирование только позициями слов, удовлетворяющих ограничениям контекста. Это позволяет резко сократить число операций над документами.

-о! ну и позже говорится, что частота вычисляется только по соовам удовлетворяющим огр. контекста.

о процедуре вычисления неявных контекстных ограничений, применяемой в распределенной версии поиска Яндекса. В этом случае на серверах «переднего края» [6] производится синтаксический разбор запроса на основе ATN-грамматики [7], адаптированной к свободному порядку слов русского языка. С учетом рваного «телеграфного» стиля в естественно-языковых фрагментах запросов выявляются несколько видов синтаксической связей (притяжание, перечисление, зависимости цели и места, счетные конструкции и др.) и устанавливаются эмпирически подобранные контекстные ограничения.

…и между словами вставляются расстояния в предложениях, словах и т.п. Так, пойти посмотреть, как они эти притяжания и перечисления в результатах переколдовки представляют. И алгоритм не нужно думать – спасибо, сами сказали. 🙂

синтаксический разбор запроса на основе ATN-грамматики [7], адаптированной к свободному порядку слов русского языка

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

Глобальная для всех коллекций статистика слов используется как для «выравнивания» ранжирования между коллекциями [6]

-не понял. Учет IDF или что… Коллекция – это же вся база документов.

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

-почему треугольную?… Видимо, это они многоместный оператор “И” так реализуют. Тогда получается, что некоторая кривизна в ограничении контекста между “далекими” словами будет присутствовать…

Яндекс осуществляет процесс нахождения всех пассажей в документах, удовлетворяющих этим ограничениям, с учетом оператора нечеткого поиска с неявно назначенным коэффициентом «мягкости» [8]. Коэффициент мягкости (число от 0 до 100) задается при помощи следующего синтаксиса:

(несколько слов с контекстными операторами)//МЯГКОСТЬ

-теперь понятно, что это за число после //. Хотя по их дальнейшим графикам это скорее жесткость. Проверить на выдаче.

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

-таки еще раз… В колдунщике никаких операторов OR нет, там только AND на расстоянии в несколько слов или предложений… Откуда берется OR? 1) либо это было “для поиграться” на РОМИПе, либо 2) видимый нами колдунщик не есть правильный либо 3) OR – это AND с расстоянием в 7 предложений вперед-назад. 🙂

Идея кворума в поиске не нова, ее аналогом в процедуре фильтрации релевантных пассажей можно считать принцип «weighted coordination match» [9], при котором «найденными» считаются все полные пассажи, а также все неполные, сумма весов слов которых превосходит необходимый кворум

-ну понятно, веса написаны в переколдованном запросе… Итак, одно редкое слово может перекрыть много частых. Только не написано, кворум этот самый – он тоже индивидуально рассчитывается для каждого запроса (логично было бы) или жестко установлен от числа слов в запросе? Судя по дальнейшему изложению, могут играть оба варианта – кворум то в словах, то в процентах нарисован… Или мягкость меняется от запроса?

QuorumWeight=(1-Softness)^((ЧислоСлов-1)^-1/2)

-собственно, жестко от числа слов, а мягкость они ставят неизвестно как… Не дочитал. Пока не проговоришь, не поймешь.

при Softness=50 число найденных документов должно быть примерно средним геометрическим чисел найденных документов при поиске всех возможных неполных пассажей

-Как это, softness же в интервале (0,1)…??? Наверное, число за // на 100 делится…

В частности, при равных по весу словах запроса и коэффициенте мягкости 0.06 (того, что использовался при выполнении заданий РОМИП), в пятисловном запросе достаточно 4-х слов (или 76% веса), а в 16-словном всего лишь 8 слов (или 52% веса) для преодоления кворума.

-говорили, 6 – стандартная мягкость…

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

-каком еще голосовании?

Если при ранжировании Яндекс использует классический для IR логарифм обратной частоты, то при вычислении суммы голосов в кворуме применяется степенная функция с показателем между квадратным и кубическим корнем. Отличия состоят в том, что «вариант с корнем» больше ориентирован на учет “тяжелых”, “редких”, “новых” слов, пусть и без полного набора соседей, тогда как логарифм тяготеет к максимальному возможному количеству слов в пассаже независимо от их тяжести

-видимо, это относится к расчету суммарного веса пассажа для сравнения его с “цифиркой” -кворумом… Или, может, не так – сумма весов это, типа, весь кворум, а степенная функция – это голос одного слова… Но на кой это надо… Перечитать.

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

-только по прошедшим границу…

Внутри-документная частота по релевантным пассажам

Формула расчета веса слова по отношению к документу («контрастности») в Яндексе использует внутри-документные частоты слов с учетом этапа фильтрации. Иными словами, в классической формуле SUM(TermFrequency*), вычисляющей вес документа по отношению к запросу как сумму контрастностей слов запроса в документе, в Яндексе используется заниженная TF, учитывающая только те словопозиции, которые попали в «интересные» нам пассажи. Фактически Яндекс считает полностью «нерелевантными» все словопозиции слов запроса, не удовлетворяющие контекстным ограничениям.

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

Ранжирование на уровне словопозиций: расчет веса словопозиции

Полученная контрастность слова распределяется на все его позиции, прошедшие фильтр.

-контрастность – это что, то, что мы при “голосовании по кворуму” получили для слова или что?

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

-таки идет некий возврат к исходному, незаколдованному запросу…

Наконец, веса словопозиций, взвешенные по сходству их полного контекста, «собираются» обратно и образуют вес документа.

-“Собираются”… 🙂 В шпиёны надо было пойти, однозначно. Складываются? Умножаются? 🙂

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

-дык.

Функция контрастности

В классической литературе по IR можно встретить разные функции нормирования и сглаживания внутри-документной частоты при вычислении контрастности TF*IDF.

-а, вот она, контрастность. Сначала употребили термин, а потом его объясним. 🙂 Получается, это какая-то переколдованная частота.

Функция Яндекса, подобно функциям Harman и BM25, нормализует внутри-документную частоту по размеру документа.

-что бы это значило… Судя по ссылкам, функция Яндекса похожа на (12) и (13)…

Следует отметить, что в Яндексе используется дополнительный анализ текстов при индексировании для подавления многократного повторения слов в тексте в расчете на повышение ранга документа в выдаче поисковых машин [8].

-о! Ага, ясно, что с учетом всех хитрвы#####ых алгоритмов преимущество получили бы тупые перечисления запросов в дорвеях… 🙂 Главное – правильно подобрать их количество и расстояние между ними…

Функциям весов пассажей, описанным в литературе:

Присущи следующие общие черты:

• Объемлющие пассажи игнорируются

• Позиции внутренних опор не принимаются во внимание

• Ранг неполных пассажей строго меньше ранга полных

• Вес пассажа — плавно убывающая функция, обратно пропорциональная длине (или корню длины) пассажа и его «неполноте»

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

-ага, ну с дефективностью неполных пассажей как-то все уже знакомы, а вот какой контекст используется?… Функция Яндекса – “табуированный” 🙂 набор коэффициентов.

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

-таки есть учет, что бы нам не говорил semaster в рассылке А&П 🙂

Яндекс также анализирует форматирование на этапе индексирования

-интересно, на кой? Разве что дорвеи и спам вычислять.

Для Веб-поиска мы вручную выбрали «лучший» вариант из 8-ми: два вида ограничения контекста (предложение и документ), с группированием или без группирования по хостам. Коэффициент мягкости брался в одном случае равным 6 (значение по умолчанию), а в другом — 10. Для нормативной коллекции выбиралось лишь лучшее контекстное ограничение, а группирование не имело значения. Вариант синтаксического преобразования запроса за нехваткой времени испробован не был.

Лучшим вариантом для обеих коллекций мы посчитали: «документный контекст, отсутствие группировки, мягкость 6».

-хе-хе! “Отсутствие группировки по сайтам” был лучше! 🙂
***
Одно непонятно – а чегой-то они так подобрели? Надо бы еще было коэффициенты выложить…