Исправляем опечатки в поисковых запросах |
||
МЕНЮ Искусственный интеллект Поиск Регистрация на сайте Помощь проекту ТЕМЫ Новости ИИ Искусственный интеллект Разработка ИИГолосовой помощник Городские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Техническое зрение Чат-боты Авторизация |
2019-03-07 06:17 алгоритмы машинного обучения, поисковые системы, компьютерная лингвистика Наверное, любой сервис, на котором вообще есть поиск, рано или поздно приходит к потребности научиться исправлять ошибки в пользовательских запросах. Errare humanum est; пользователи постоянно опечатываются и ошибаются, и качество поиска от этого неизбежно страдает — а с ним и пользовательский опыт. Может показаться, что мы отказали пользователю в его мечте о вертикальной реальности, но на самом деле буква К просто стоит на клавиатуре рядом с буквой У. Постановка задачи Итак, нам пришёл опечатанный запрос и его надо исправить. Обычно математически задача ставится таким образом: дано слово , переданное нам с ошибками; есть словарь правильных слов; для всех слов w в словаре есть условные вероятности того, что имелось в виду слово , при условии, что получили мы слово ; нужно найти слово w из словаря с максимальной вероятностью . Эта постановка — самая элементарная — предполагает, что если нам пришёл запрос из нескольких слов, то мы исправляем каждое слово по отдельности. В реальности, конечно, мы захотим исправлять всю фразу целиком, учитывая сочетаемость соседних слов; об этом я расскажу ниже, в разделе “Как исправлять фразы”. Теперь вместо исходной непонятной вероятности нам нужно оценить две новые, чуть более понятные: — вероятность того, что при наборе слова можно опечататься и получить , и — в принципе вероятность использования пользователем слова . Модель ошибок Первые модели ошибок считали , подсчитывая вероятности элементарных замен в обучающей выборке: сколько раз вместо Е писали И, сколько раз вместо ТЬ писали Т, вместо Т — ТЬ и так далее [1]. Получалась модель с небольшим числом параметров, способная выучить какие-то локальные эффекты (например, что люди часто путают Е и И). Давайте посмотрим на пример разбиения, возникающего при вычислении вероятности напечатать «аксесуар» вместо «аксессуар»: Как вы наверняка заметили, это пример не очень удачного разбиения: видно, что части слов легли друг под другом не так удачно, как могли бы. Если величины и ещё не так плохи, то и , скорее всего, сделают итоговый «счёт» этого разбиения совсем печальным. Более удачное разбиение выглядит как-то так: Здесь всё сразу стало на свои места, и видно, что итоговая вероятность будет определяться преимущественно величиной . Как вычислить Несмотря на то, что возможных разбиений для двух слов имеется порядка , с помощью динамического программирования алгоритм вычисления можно сделать довольно быстрым — за . Сам алгоритм при этом будет очень сильно напоминать алгоритм Вагнера-Фишера для вычисления расстояния Левенштейна. Мы заведём прямоугольную таблицу, строки которой будут соответствовать буквам правильного слова, а столбцы — опечатанного. В ячейке на пересечении строки i и столбца j к концу алгоритма будет лежать в точности вероятность получить s[:j] при попытке напечатать w[:i]. Для того, чтобы её вычислить, достаточно вычислить значения всех ячеек в предыдущих строках и столбцах и пробежаться по ним, домножая на соответствующие . Например, если у нас заполнена таблица , то для заполнения ячейки в четвёртой строке и третьем столбце (серая) нужно взять максимум из величин и . При этом мы пробежались по всем ячейкам, подсвеченным на картинке зелёным. Если также рассматривать модификации вида и , то придётся пробежаться и по ячейкам, подсвеченным жёлтым. Как максимизировать Мы научились находить за полиномиальное время — это хорошо. Но нам нужно научиться быстро находить наилучшие слова во всём словаре. Причём наилучшие не по , а по ! На деле нам достаточно получить какой-то разумный топ (например, лучшие 20) слов по , который мы потом отправим в модель языка для выбора наиболее подходящих исправлений (об этом ниже). Как получить Вычисление для всех рассматриваемых фрагментов — самая интересная и нетривиальная часть построения модели ошибок. Именно от этих величин будет зависеть её качество. Теперь мы сразу видим замены: а ? а, е ? и, с ? с, с ? пустая строка и так далее. Также мы видим замены двух и более символов: ак ? ак, се ? си, ес ? ис, сс ? с, сес ? сис, есс ? ис и прочая, и прочая. Все эти замены необходимо посчитать, причём каждую столько раз, сколько слово s встречается в корпусе (если мы брали слова из корпуса, что очень вероятно). Модель языка Итак, теперь для заданного словарного слова w нам нужно вычислить — вероятность его использования пользователем. Простейшее решение — взять встречаемость слова в каком-то большом корпусе. Вообще, наверное, любая модель языка начинается с собирания большого корпуса текстов и подсчёта встречаемости слов в нём. Но ограничиваться этим не стоит: на самом деле при вычислении P(w) мы можем учесть также и фразу, слово в которой мы пытаемся исправить, и любой другой внешний контекст. Задача превращается в задачу вычисления , где одно из — слово, в котором мы исправили опечатку и для которого мы теперь рассчитываем , а остальные — слова, окружающие исправляемое слово в пользовательском запросе. где — непосредственно частота слова, а — вероятность слова при условии, что перед ним идут — не что иное, как отношение частоты триграммы к частоте биграммы . (Заметьте, что эта формула — просто результат многократного применения формулы Байеса.) Логично? Логично. Однако трудности начинаются, когда фразы становятся длиннее. Что, если пользователь ввёл впечатляющий своей подробностью поисковый запрос в десять слов? Мы не хотим держать статистику по всем 10-граммам — это дорого, а данные, скорее всего, будут шумными и не показательными. Мы хотим обойтись n-граммами какой-то ограниченной длины — например, уже предложенной выше длины 3. Положив , для более длинной фразы получим формулу Как исправлять фразы Обговорим последний тонкий момент перед тем, как перейти к реализации. Постановка задачи, которую я описал выше, подразумевала, что есть одно слово и его надо исправить. Потом мы уточнили, что это одно слово может быть в середине фразы среди каких-то других слов и их тоже нужно учесть, выбирая наилучшее исправление. Но в реальности пользователи просто присылают нам фразы, не уточняя, какое слово написано с ошибкой; нередко в исправлении нуждается несколько слов или даже все. Здесь — слова, введённые пользователем, — подобранные для них исправления (которые мы сейчас перебираем), а — коэффициент, определяемый сравнительным качеством модели ошибок и модели языка (большой коэффициент — больше доверяем модели языка, маленький коэффициент — больше доверяем модели ошибок), предложенный в [4]. Итого для каждой фразы мы перемножаем вероятности отдельных слов исправиться в соответствующие словарные варианты и ещё домножаем это на вероятность всей фразы в нашем языке. Результат работы алгоритма — фраза из словарных слов, максимизирующая эту величину. Если мы домножим эту величину на и попытаемся максимизировать по , мы увидим, что достаточно перебрать всевозможные и и решить задачу для них — то есть для фраз . Итого задача решается динамическим программированием за . Реализация Собираем корпус и считаем n-граммы Сразу оговорюсь: данных в моём распоряжении было не так много, чтобы заводить какой-то сложный MapReduce. Так что я просто собрал все тексты отзывов, комментариев и поисковых запросов на русском языке (описания товаров, увы, приходят на английском, а использование результатов автоперевода скорее ухудшило, чем улучшило результаты) с нашего сервиса в один текстовый файл и поставил сервер на ночь считать триграммы простым скриптом на Python. Обучаем модель ошибок Дальше всю обработку данных я проводил в Jupyter. Статистика по n-граммам грузится из JSON, производится постобработка, чтобы быстро находить близкие друг к другу по Левенштейну слова, и для пар в цикле вызывается (довольно громоздкая) функция, выстраивающая слова и извлекающая короткие правки вида сс ? с (под спойлером). Код на Python def generate_modifications(intended_word, misspelled_word, max_l=2): # Выстраиваем буквы слов оптимальным по Левенштейну образом и # извлекаем модификации ограниченной длины. Чтобы после подсчёта # расстояния восстановить оптимальное расположение букв, будем # хранить в таблице помимо расстояний указатели на предыдущие # ячейки: memo будет хранить соответствие # i -> j -> (distance, prev i, prev j). # Дальше немного непривычно страшного Python кода - вот что # бывает, когда язык используется не по назначению! m, n = len(intended_word), len(misspelled_word) memo = [[None] * (n+1) for _ in range(m+1)] memo[0] = [(j, (0 if j > 0 else -1), j-1) for j in range(n+1)] for i in range(m + 1): memo[i][0] = i, i-1, (0 if i > 0 else -1) for j in range(1, n + 1): for i in range(1, m + 1): if intended_word[i-1] == misspelled_word[j-1]: memo[i][j] = memo[i-1][j-1][0], i-1, j-1 else: best = min( (memo[i-1][j][0], i-1, j), (memo[i][j-1][0], i, j-1), (memo[i-1][j-1][0], i-1, j-1), ) # Отдельная обработка для перепутанных местами # соседних букв (распространённая ошибка при # печати). if (i > 1 and j > 1 and intended_word[i-1] == misspelled_word[j-2] and intended_word[i-2] == misspelled_word[j-1] ): best = min(best, (memo[i-2][j-2][0], i-2, j-2)) memo[i][j] = 1 + best[0], best[1], best[2] # К концу цикла расстояние по Левенштейну между исходными словами # хранится в memo[m][n][0]. # Теперь восстанавливаем оптимальное расположение букв. s, t = [], [] i, j = m, n while i >= 1 or j >= 1: _, pi, pj = memo[i][j] di, dj = i - pi, j - pj if di == dj == 1: s.append(intended_word[i-1]) t.append(misspelled_word[j-1]) if di == dj == 2: s.append(intended_word[i-1]) s.append(intended_word[i-2]) t.append(misspelled_word[j-1]) t.append(misspelled_word[j-2]) if 1 == di > dj == 0: s.append(intended_word[i-1]) t.append("") if 1 == dj > di == 0: s.append("") t.append(misspelled_word[j-1]) i, j = pi, pj s.reverse() t.reverse() # Генерируем модификации длины не выше заданной. for i, _ in enumerate(s): ss = ts = "" while len(ss) < max_l and i < len(s): ss += s[i] ts += t[i] yield ss, ts i += 1 Сам подсчёт правок выглядит элементарно, хотя длиться может долго. Применяем модель ошибок Эта часть реализована в виде микросервиса на Go, связанного с основным бэкендом через gRPC. Реализован алгоритм, описанный самими Бриллом и Муром [2], с небольшими оптимизациями. Работает он у меня в итоге примерно вдвое медленнее, чем заявляли авторы; не берусь судить, дело в Go или во мне. Но по ходу профилировки я узнал о Go немного нового. Не используйте math.Max, чтобы считать максимум. Это примерно в три раза медленнее, чем if a > b { b = a }! Только взгляните на реализацию этой функции: // Max returns the larger of x or y. // // Special cases are: // Max(x, +Inf) = Max(+Inf, x) = +Inf // Max(x, NaN) = Max(NaN, x) = NaN // Max(+0, ±0) = Max(±0, +0) = +0 // Max(-0, -0) = -0 func Max(x, y float64) float64 func max(x, y float64) float64 { // special cases switch { case IsInf(x, 1) || IsInf(y, 1): return Inf(1) case IsNaN(x) || IsNaN(y): return NaN() case x == 0 && x == y: if Signbit(x) { return y } return x } if x > y { return x } return y } Если только вам ВДРУГ не нужно, чтобы +0 обязательно был больше -0, не используйте math.Max. Не используйте хэш-таблицу, если можете использовать массив. Это, конечно, довольно очевидный совет. Мне пришлось перенумеровывать символы юникода в числа в начале программы так, чтобы использовать их как индексы в массиве потомков узла trie (такой lookup был очень частой операцией). Коллбеки в Go недёшевы. В ходе рефакторинга во время код ревью некоторые мои потуги сделать decoupling ощутимо замедлили программу при том, что формально алгоритм не изменился. С тех пор я остаюсь при мнении, что оптимизирующему компилятору Go есть, куда расти. Применяем модель языка Здесь без особых сюрпризов был реализован алгоритм динамического программирования, описанный в разделе выше. На этот компонент пришлось меньше всего работы — самой медленной частью остаётся применение модели ошибок. Поэтому между этими двумя слоями было дополнительно прикручено кэширование результатов модели ошибок в Redis. Результаты По итогам этой работы (занявшей примерно человекомесяц) мы провели A/B тест опечаточника на наших пользователях. Вместо 10% пустых выдач среди всех поисковых запросов, которые мы имели до внедрения опечаточника, их стало 5%; в основном оставшиеся запросы приходятся на товары, которых просто нет у нас на платформе. Также увеличилось количество сессий без второго поискового запроса (и ещё несколько метрик такого рода, связанных с UX). Метрики, связанные с деньгами, впрочем, значимо не изменились — это было неожиданно и сподвигло нас к тщательному анализу и перепроверке других метрик. Заключение Стивену Хокингу как-то сказали, что каждая включенная им в книгу формула вдвое уменьшит число читателей. Что ж, в этой статье их порядка полусотни — поздравляю тебя, один из примерно читателей, добравшихся до этого места! Бонус Ссылки [1] M. D. Kernighan, K. W. Church, W. A. Gale. A Spelling Correction Program Based on a Noisy Channel Model. Proceedings of the 13th conference on Computational linguistics — Volume 2, 1990. Источник: habr.com Комментарии: |
|