21.08.2019 00:58
samofsergey 3 1700 Источник
Поисковые подсказки — это здорово. Как часто мы набираем полный адрес сайта в адресной строке? А название товара в интернет-магазине? Для таких коротких запросов обычно хватает ввести несколько символов, если подсказки поиска хороши. И если вы не обладаете двадцатью пальцами или неимоверной скоростью набора текста, то наверняка будете ими пользоваться.
В этой статье мы расскажем о нашем новом сервисе подсказок для поиска по вакансиям hh.ru, который мы сделали в предыдущем выпуске Школы программистов.

У старого сервиса был ряд проблем:

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


В новом сервисе мы исправили эти недостатки (параллельно добавив новые).

Словарь популярных запросов


Когда совсем нет подсказок, можно вручную отобрать top-N запросов пользователей и формировать подсказки из этих запросов, используя точное вхождение слов (с учетом порядка или без него). Это неплохой вариант — он прост в реализации, дает хорошую точность подсказок и не испытывает проблем с производительностью. Долгое время наш саджест так и работал, но существенный минус такого подхода — недостаточная полнота выдачи.

Например, в такой список не попал запрос «javascript разработчик», поэтому при вводе «javascript раз» нам нечего показать. Если дополнять запрос, учитывая лишь последнее слово, мы увидим на первом месте «javascript разнорабочий». По той же причине не удастся реализовать исправление ошибок сложнее стандартного подхода с поиском ближайших слов по расстоянию Дамерау-Левенштейна.

Языковая модель


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

word_count

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

$P(w_1\dots w_m)=\prod_{i=1}^mP(w_i|w_1\dots w_{i-1})\approx\prod_{i=1}^mP(w_i|w_{i-(n-1)}\dots w_{i-1})$



В качестве простейшей модели можем взять статистическое определение вероятности, тогда

$P(w_i|w_1\dots w_{i-1})=\frac{count(w_1\dots w_i)}{count(w_1\dots w_{i-1})}$



Однако, такая модель не подходит для оценки запросов, которые отсутствовали в нашей выборке: если мы не наблюдали 'junior developer java', то окажется, что

$P(\text{junior developer java})=\frac{count(\text{junior developer java})}{count(\text{junior developer})}=0$



Для решения данной проблемы можно использовать различные модели сглаживания и интерполяции. Мы использовали Backoff:

$P_{bo}(w_n|w_1\dots w_{n-1}) = \begin{cases} {P}(w_n|w_1\dots w_{n-1}), count(w_1\dots w_{n-1})>0 \\ \alpha{P_{bo}}(w_n|w_2\dots w_{n-1}), count(w_1\dots w_{n-1})=0 \end{cases} $


$\alpha = \frac{P(w_1\dots w_{n-1})}{1 - \sum_wP_{bo}(w|w_2\dots w_{n-1})}$


Где P — сглаженная вероятность $w_1...w_{n-1}$ (мы использовали сглаживание Лапласа):

$P(w_n | w_1\dots w_{n-1}) = \frac{count(w_n) + \delta}{count(w_1\dots w_{n-1})+\delta |V|}$


где V — наш словарь.

Генерация вариантов


Итак, мы умеем оценивать вероятность конкретного запроса, но как генерировать эти самые запросы? Разумно сделать следующее: пусть пользователь ввел запрос $w_1...w_n$, тогда подходящие нам запросы можно найти из условия

$w_1\dots w_m = \underset{w_{n+1}\dots w_m \in V}{argmax}P(w_1\dots w_n w_{n+1} \dots w_m)$



Разумеется, перебирать $|V| ^ {m-n}, m=1 \dots M$ вариантов и отбирать из них лучшие для каждого входящего запроса не представляется возможным, поэтому используем Beam Search. Для нашей n-граммной языковой модели он сводится к следующему алгоритму:

def beam(initial, vocabulary):
    variants = [initial]
    for i in range(P):
        candidates = []
        for variant in variants:
            candidates.extends(generate_candidates(variant, vocabulary))
        variants = sorted(candidates)[:N]
    return candidates 

def generate_candidates(variant, vocabulary):
    top_terms = []
    # сначала отбираем наиболее вероятные термы с контекстом из 1, 2, ... n термов
    for n0 in range(n):
        top_n = sorted(vocabulary, key=lambda c: P(с|variant[-n0:])
        top_terms.extends(top_n)
    candidates = [variant + [term] for term in top_terms]
    # затем отбираем наиболее вероятные составленные предложения
    candidates = sorted(candidates, key=lambda v: P(variant))[:N]
    return candidates

beam search

Здесь узлы, подсвеченные зеленым, — итоговые выбранные варианты, число перед узлом $w_n$ — вероятность $P(w_n|w_{n-1})$, после узла — $P(w1 ... w_n)$.

Стало намного лучше, но в generate_candidates необходимо быстро получать N лучших термов для заданного контекста. В случае хранения только вероятностей n-грамм нам необходимо пройти по всему словарю, вычислить вероятности всех возможных фраз, а затем их отсортировать. Очевидно, что для онлайн-запросов такое не взлетит.

Бор для вероятностей


Для быстрого получения N лучших по условной вероятности вариантов продолжений фразы мы использовали бор на термах. В узле $w_1 \to w_2$ хранится коэффициент $\alpha$, значение $P(w_2|w_1)$ и отсортированный по условной вероятности $P(\bullet|w_1 w_2)$ список термов $w_3$ вместе с $P(w_3|w_1 w_2)$. Специальный терм eos обозначает конец фразы.
trie

Но есть нюанс


В описанном выше алгоритме мы исходим из того, что в запросе все слова были закончены. Однако, это не верно для последнего слова, которое пользователь вводит его прямо сейчас. Нам снова необходимо пройти по всему словарю, чтобы продолжить текущее вводимое слово. Для решения этой проблемы мы используем посимвольный бор, в узлах которого храним M отсортированных по униграммной вероятности термов. Например, так будет выглядеть наш бор для java, junior, jupyter, javascript при M=3:

trie

Тогда перед началом Beam Search, находим M лучших кандидатов для продолжения текущего слова $w_n$ и отбираем N лучших кандидатов по $P(w_1 \dots w_n)$.

Опечатки


Отлично, мы построили сервис, который позволяет давать неплохие подсказки для пользовательского запроса. Мы даже готовы к появлению новых слов. И все бы хорошо… Но пользовтели опечтыватся и не переключают hfcrkflre клавиатуры.

Как это решить? Первым делом на ум приходит поиск исправлений с помощью нахождения ближайших вариантов по расстоянию Дамерау-Левенштейна, которое определяется как минимальное количество операций вставки/удаления/замены символа или транспозиции двух соседних, необходимых для получения из одной строки другой. К сожалению, данное расстояние не учитывает вероятность той или иной замены. Так, для введенного слова «сапрщик», получим, что варианты «сборщик» и «сварщик» равноценны, хотя интуитивно кажется, что имели в виду второе слово.

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

Если подойти к задаче исправления опечаток с вероятностной точки зрения, то вполне естественно прийти к модели зашумленного канала:

  1. задан алфавит $\Sigma$;
  2. множество всех конечных строк $\Sigma^*$ над ним;
  3. множество строк, являющихся правильными словами $D \subseteq \Sigma^*$;
  4. заданы распределения $P(s|w)$, где $s \in \Sigma^*, w \in D$.

Затем задача исправления ставится как нахождение правильного слова w для входа s. В зависимости от источника ошибок, мера $P$ может строиться по-разному, в нашем случае разумно попробовать оценить вероятность опечаток (назовем их элементарными заменами) $P_e(t|r)$, где t, r — символьные n-граммы, а затем оценивать $P(s|w)$ как вероятность получить s из w наиболее вероятными элементарными заменами.

Пусть $Part_n(x)$ — разбиение строки x на n подстрок (возможно нулевых). Модель Брилла-Мура предполагает вычисление вероятности $P(s|w)$ следующим образом:

$P(s|w) \approx \max_{R\in Part_n(w),T\in Part_n(s)} \prod_{i=1}^{n} P_e(T_i | R_i)$


Но нам необходимо найти $P(w|s)$:

$P(w|s) = \frac{P(s|w)P(w)}{P(s)} = const \cdot P(s|w)\cdot P(w)$


Научившись оценивать P(w|s), мы решим и проблему ранжирования вариантов с одинаковым расстоянием Дамерау-Левенштейна и сможем учитывать контекст при исправлении опечатки.

Вычисление $P_e(T_i | R_i)$


Для подсчета вероятностей элементарных замен нам вновь помогут пользовательские запросы: составим пары слов (s, w) которые

  1. близки по Дамерау-Левенштейну;
  2. одно из слов встречается чаще другого в N раз.

Для таких пар рассмотрим оптимальное выравнивание по Левенштейну:


Составим всевозможные разбиения s и w (мы ограничились длинами n=2, 3): п>п, пр>рп, про>рпо, ро>по, м>'', мм>м и т.д. Для каждой n-граммы найдем

$P_e(t|r) = \frac{count(r\to t)}{count(r)}$



Вычисление $P(s|w)$


Вычисление $P(s|w)$ напрямую занимает $O(2^{|w|+|s|})$: нам нужно перебрать все возможные разбиения w со всеми возможными разбиениями s. Однако, динамикой на префиксе можно получить ответ за $O(|w| * |s| * n^2)$, где n — максимальная длина элементарных замен:

$d[i,j]=\begin{cases} d[0,j] = 0 & j >= k\\ d[i,0] = 0 & i >= k\\ d[0,j] = P(s[0:j]\space |\space w[0]) & j < k\\ d[i,0] = P(s[0]\space |\space w[0:i]) & i < k\\ d[i,j] = \underset{k, l \le n, k\lt i, l \lt j}{max}(P(s[j-l:j]\space | \space w[i-k:i])\cdot d[i-k-1,j-l-1]) \end{cases}$


Здесь P — вероятность соответствующей строки в k-граммной модели. Если приглядеться, то это очень похоже на алгоритм Вагнера-Фишера с отсечением Укконена. На каждом шаге мы получаем $P(w[0:i] | s[0:j])$ путем перебора всех вариантов исправлений $w[i-k:i]$ в $s[j-l : j]$ при условии $k, l \le n$ и выбора из них наиболее вероятного.

Возвращаемся к $P(w|s)$


Итак, мы умеем вычислять $P(s|w)$. Теперь нам нужно выбрать несколько вариантов w, максимизирующих $P(w|s)$. Точнее, для исходного запроса $s_1s_2 \dots s_n$ необходимо выбрать такие $w_1 \dots w_n$, где $P(w_1 \dots w_n|s_1 \dots s_n)$ максимальна. К сожалению, честный выбор вариантов не укладывался в наши требования по времени отклика (а срок проекта подходил к концу), поэтому мы решили остановиться на следующем подходе:

  1. из исходного запроса получаем несколько вариантов, изменяя k последних слов:
    1. исправляем раскладку клавиатуры, если у получившегося терма вероятность в несколько раз выше исходного;
    2. находим слова, расстояние Дамерау-Левенштейна которых не превосходит d;
    3. выбираем из них top-N вариантов по $P(s | w)$;
  2. передаем на вход BeamSearch вместе с исходным запросом;
  3. при ранжировании результатов дисконтируем полученные варианты на $\prod_{i=0}^{k-1} P(s_{n-i}|w_{n-i})$.

Для п.1.2 мы использовали алгоритм FB-Trie (forward and backward trie), основанный на нечетком поиске по прямому и обратному префиксному дереву. Это оказалось быстрее, чем оценивать P(s|w) по всему словарю.

Статистика запросов


С построением языковой модели все просто: собираем статистику по пользовательским запросам (сколько раз делали запрос данной фразы, какое количество пользователей, какое количество зарегистрированных пользователей), разбиваем запросы на n-граммы и строим боры. Сложнее с моделью ошибок: как минимум, для ее построения необходим словарь правильных слов. Как было сказано выше, для выбора обучающих пар мы использовали предположение, что такие пары должны быть близки по расстоянию Дамерау-Левенштейна, и одно должно встречаться чаще другого в некоторое количество раз.

Но данные все равно слишком шумные: попытки xss-инъекций, неверная раскладка, случайный текст из буфера обмена, опытные пользователи с запросами «программист c not 1c», запросы от прошедшего по клавиатуре кота.

Например, что пытались найти по такому запросу?


Поэтому для очистки исходных данных мы исключали:

  • низкочастотные термы;
  • содержащие операторы языка запросов;
  • обсценную лексику.

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

В прод


Прямо перед защитой проектов запустили сервис в продакшн для внутреннего тестирования, а спустя пару дней — на 20% пользователей. В hh.ru все значимые для пользователей изменения проходят через систему АБ-тестов, что позволяет не только быть уверенным в значимости и качестве изменений, но и находить ошибки.

metric

Прокрасилась метрика среднего количества поисков из саджеста на соискателей (увеличилось с 0.959 до 1.1355), а доля поисков из саджеста от всех поисковых запросов увеличилась с 12.78% до 15.04%. К сожалению, основные продуктовые метрики не выросли, но пользователи определенно стали чаще пользоваться подсказками.

Напоследок


В статье не нашлось места для рассказа о процессах Школы, о других опробованных моделях, об инструментах, которые мы написали для сравнений моделей, и о встречах, где решали, какие фичи взять в разработку, чтобы успеть к промежуточным демо. Посмотрите записи прошедшей школы, оставляйте заявку на https://school.hh.ru, выполняйте интересные задачи и приходите учиться. Кстати, сервис для проверки задач также сделали выпускники предыдущего набора.

Что почитать?


  1. Введение в Language Model
  2. Модель Брилла-Мура
  3. FB-Trie
  4. Что происходит с вашим запросом в поиске

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


  1. andreyle
    21.08.2019 05:55
    #20530219

    Когда же вы исправите глюк, когда по резюме «Системный администратор» перестанут предлагать вакансии администраторов баров, гостиниц и прочих заведений?


    1. 3aBulon
      21.08.2019 06:10
      #20530239

      да и не только ) в похожих вакансиях снизу полный бред


  1. mad_nazgul
    21.08.2019 09:09
    #20530501

    В общем HH как обычно. Много слов, а в результате пшик.