Привет, меня зовут Александр Брыль, я дата-саентист в команде NLP СберМегаМаркета и сегодня хочу рассказать, как мы искали быстрое и удобное решение для исправления ошибок в поисковых запросах маркетплейса: зачем нам это понадобилось, как мы сравнивали автокорректоры Яндекс.Спеллер, корректор от DeepPavlov, SymSpell и на чем в итоге решили остановиться.
Зачем исправлять очепятки
Согласно данным Яндекса, примерно каждый десятый пользовательский запрос написан с ошибкой. Часть из них — это обычные опечатки или неправильная раскладка, остальное приходится на орфографические ошибки.
Идеальный алгоритм по исправлению опечаток и ошибок мгновенно распознает то, что имел в виду пользователь, и быстро предлагает вариант на замену ошибочного запроса. Это особенно важно для интернет-магазинов, агрегаторов предложений и маркетплейсов. Поскольку сейчас покупатели все чаще предпочитают искать товары не через интернет-поисковик, а обращаются к поиску в рамках определенного маркетплейса и выбирать из предложенного ассортимента наиболее подходящее предложение. Это обусловлено тем, что пользователь хорошо знает, какая информация представлена на платформе по продукции, продавцу или нужным ему категориям товаров. А при использовании поисковых систем потребитель не может быть уверен в том, надежный ли интернет-магазин выпадет в выдаче и получит ли он полную информацию.
Если на торговой площадке первый запрос не принес результата, а исправление ошибок реализовано примитивно, то пользователю придется вручную переформулировать запрос — самому исправлять опечатки. Угадайте, какой процент покупателей готов это делать.
Спойлер: согласно данным Школы информации Вашингтонского университета, в поисковой системе 10% всех запросов переформулированы пользователями, потому что первые запросы не дали результата. Вероятно, для маркетплейсов этот процент будет ниже: закрыть приложение «бестолкового» магазина часто легче, чем печатать заново.
Проще говоря, потенциально каждый десятый покупатель может уйти с маркетплейса, ничего не купив — просто потому, что в ответ на его запрос система ничего не нашла и не предложила.
Как нам кажется, связь «быстрый и устраивающий всех алгоритм исправления ошибок → удобство для пользователя → повышение продаж» довольно прозрачная. Поэтому мы и взялись за эту задачу.
С чего мы начали
Для начала пара слов об особенностях автокорректоров поисковых запросов:
Они отличаются от корректоров, которые исправляют связный литературный текст. Поисковый запрос очень короткий, обычно состоит из 1-3 слов, а большинство автокорректоров тестируются на художественных или диалоговых датасетах. Модели, обученные на таких данных, как правило довольно тяжелые.
Лексика в поисковых запросах отличается от литературного русского языка. Этот уникальный словарь формируется, прежде всего, из ассортимента маркетплейса. Часто это смешанный язык: так как многие бренды пишутся по-английски, в поиск вбивают русские слова вперемежку с англоязычными названиями.
В поисковый движок СберМегаМаркета уже встроен простой механизм коррекции. Нашей задачей минимум было превзойти этот базовый алгоритм. Задача максимум — выбрать лучшую модель из доступных в открытых источниках.
Оценка качества: проверяем, как работают популярные автокорректоры
Вначале экспериментов у нас еще не было размеченного датасета из реальных запросов. Чтобы не терять время, мы решили начать работу с искусственными данными, сгенерированных из наименований каталога товаров СберМегаМаркета. Для этого мы написали генератор опечаток, который случайно выбирал символ или несколько в строке и применял какую-то трансформацию: замену, удаление, вставку, транспозицию — с некой вероятностью каждой из этих ошибок.
Статистику по количеству опечаток взяли из исследования, а вероятности отдельных трансформаций считали сами с учетом всяких тонкостей: например, замена на символ, стоящий близко к исходному на клавиатуре более вероятна, чем на символ, стоящий дальше от него. Таким образом мы рандомно трансформировали наименования из каталога использовали эти данные для первых экспериментов.
Для тестирования мы выбрали:
действующий на платформе корректор, работающий на базе Hunspell;
корректор от DeepPavlov на основе редакционного расстояния с предобученной языковой моделью;
Яндекс.Спеллер.
Решения для сравнения мы взяли из топа DeepPavlov и протестировали их по четырем параметрам:
Самый важный — это accuracy, доля полностью правильно исправленных поисковых запросов.
Эта метрика должна учитывать контекст, то есть принимать во внимание слова, значение которых зависит от окружения, общего смысла всей фразы. По данным Яндекса, около 26% опечаток от общего количества ошибок контекстно-зависимые. Алгоритм их исправления не так прост, как исправление простой опечатки. Например, фраза «прошок стиральный» может быть исправлена на «пробок стиральный», так как слово «пробок» есть в обучающей выборке. Но это исправление не соотносится с контекстом, пользователь имел в виду совсем другое. Поисковая выдача по исправленному таким образом запросу не даст нужного результата. Нам важно не просто исправить неправильно написанные слова, но и показать пользователю именно то, что он искал — предложить верную замену, исходя в том числе и из контекста.
Еще одна метрика — precision, доля верно исправленных слов с ошибками. Показывает, как много мы исправляем правильно.
Recall — доля верных слов, написанных без ошибок. Показывает, не исправили ли мы лишнего.
RPS — количество обрабатываемых запросов в секунду, скорость работы. Нет смысла писать очень хороший алгоритм, который дает ответ даже за секунду. При постановке задачи мы выбрали в качестве нижней границы 35 запросов в секунду.
Через несколько дней коллеги подготовили для нас базу с реальными поисковыми запросами, так что мы решили прогнать тесты сразу на двух наборах данных — сгенерированном и реальном. Вот какие результаты мы получили по этим метрикам:
Первое, на что обращаешь внимание, — существенная разница в оценках между сгенерированными и реальными данными. Скорее всего, причина в том, что в каталогах много слов и словосочетаний, которые покупатели ищут достаточно редко. Например, полное наименование какого-нибудь старого телефона. Ошибки в такой строке дают низкий precision, а следовательно и accuracy, на любой модели. Кроме того, в сгенерированных строках было в среднем больше слов, и это сказалось на скорости.
В целом же, видно, что качество Яндекс.Спеллера высокое, но использовать его мы не можем — из-за ограничения на количество запросов и крайне низкой скорости. Модель от DeepPavlov оказалась посередине — не очень высокий precision, но высокий recall. Результаты уже неплохие, но плюс этой модели в том, что ее можно кастомизировать.
Для разработки MVP мы решили сосредоточиться на двух корректорах: DeepPavlov и одной из его модификаций — SymSpell.
Тестируем DeepPavlov, алгоритм на основе расчета расстояния Дамерау-Левенштейна
Мы решили взять за основу нашего решения автокорректор DeepPavlov и немного его подтюнить.
DeepPavlov работает так: при обучении для каждого слова из обучающего набора строится префиксное дерево со всеми типами ошибок глубиной не более n. При коррекции фразы запрашивается набор кандидатов каждого слова, которые прогоняются через языковую модель и лучевым поиском подбираются наиболее вероятные кандидаты.
Первое, что мы решили кастомизировать — число n. Поиск кандидатов для слова глубиной более 2 уже занимает непозволительно много времени (эту проблему как раз мог решить SymSpell). Поэтому мы по умолчанию ищем кандидатов с глубиной поиска 1. Если никого не нашлось — увеличиваем глубину до 2 и на этом останавливаемся. Так мы экономим время, но не гарантируем нахождение лучшего кандидата. Если пользователь совершит больше 2-х ошибок, алгоритм уже не сможет помочь. Нужно быть внимательнее.
Второе — нужна ли языковая модель вообще. Возможно, достаточно выбирать кандидатов по минимальному редакционному расстоянию. Чтобы выяснить это, мы строили разные диаграммы распределения позиций искомых слов в списке кандидатов и получили интересные результаты:
0 — искомое слово среди кандидатов находится на нулевой позиции, 5 — дальше 5 позиции соответственно
По диаграмме видно, что лучший кандидат не всегда на первом месте. Языковая модель улучшает ранжирование кандидатов, но плохие по ее мнению кандидаты могут быть смещены ближе к концу списка (доля 5 позиции увеличивается). Значит, нам все же нужно как-то взвешивать слова.
Здесь показано, как работает поиск кандидатов по редакционному расстоянию. Лучший кандидат находится далеко не всегда на первой позиции, так что для адекватной работы алгоритма необходима языковая модель.
DeepPavlov предлагает языковые модели на основе архитектуры kenlm, которая считает вероятности n-грам токенов используя метод сглаживания Кнезера-Нея. К сожалению, эти языковые модели весят несколько гигабайт и не учитывают особенности наших поисковых запросов, о которых говорилось выше. Мы решили обучить свою модель и сравнить результаты.
Обучение языковой модели
В нашем случае критически важно, чтобы в данных не было опечаток. Поэтому мы не использовали сырые поисковые запросы в качестве обучающих данных. Попытка очистить данные от предположительно ошибочных запросов при помощи фильтрации запросов по частоте не давала в итоге хорошую обучающую выборку.
Кроме того, нам нужны были данные, учитывающие ассортимент товаров. Для этого лучше всего подходил каталог товаров. Он содержит карточки товаров с наименованиями такого вида:
«Платье женское VAY 191-3525 черное 52 RU».
Здесь 191-3525 — это артикул товара. Мы предположили, что некоторые пользователи будут искать товар по артикулу и вбивать его в строку поиска. А вот возможность опечаток в артикуле мы не учитывали. Исходя из этого, мы токенизировали строки, убрали все лишнее. Интересно, что в данном случае предлоги, союзы и прочие стоп-слова оказались не лишними. В них тоже могут быть ошибки, приводящие к непредсказуемым исправлениям, если их не учитывать. Например, «корм доя собак» → «корм соя собак».
Еще одна сложность — несбалансированность данных. Например, в каталоге нашелся крупный производитель женских платьев, который заполонил все своими платьями. Если оставить все, как есть, вероятность n-граммы «платье женское» будет очень высока. Это может привести к неверным исправлениям. Чтобы этого избежать, мы учли в нашей модели, насколько товар популярен и сопоставили наименования каталога с количеством покупок. Получили такие данные:
Сезонные всплески популярности товаров или ажиотаж при акционной распродаже тоже могут испортить всю модель. Конечно, она будет переучиваться по расписанию, но такую аномалию стоит сгладить при первой же возможности. Поэтому для составления тренировочного датасета, мы логарифмировали и нормировали количество покупок и сохранили некоторое количество строк в выборку с помощью сэмплирования по полученным вероятностям. В результате сахар песок в обучающей выборке встречается только 6 раз на миллион строк, вместо 4 тысяч.
В качестве слов для построения префиксного дерева мы использовали токены обучающей выборки.
Сравнение результатов
Мы добавили результаты кастомизированного алгоритма в сводную таблицу:
Здесь и далее приводятся только результаты работы с реальными поисковыми запросами. От сгенерированных данных для проверки точности моделей мы отказались
Вес кастомной модели заметно сократился, немного улучшилась скорость работы, но в целом результаты остались примерно теми же.
Однако, в некоторых случаях кастомная модель допускала совсем глупые ошибки, исправляя тот же «прошок стиральный» на «пророк стиральный». Кроме того, иногда оценки совершенно разных кандидатов, выдаваемых языковой моделью, не отличались друг от друга. Это натолкнуло нас на мысль не использовать языковую модель вовсе.
Для этого мы взвесили каждый токен обучающей выборки как вероятность его встречи во всей тренировочной выборке, при коррекции слова разделили вес кандидата на расстояние Дамерау-Левенштейна и выбрали самый вероятный токен. Эта идея дала такие результаты:
Теперь модель знает больше слов, и не исправляет лишнего, а главное, дает больше совпадений по целым запросам. Скорость немного упала, но в пределах допустимого. При этом, получившийся алгоритм, в отличие от варианта с языковой моделью, не использует контекст при исправлении, и все равно работает лучше.
Как еще можно улучшить результат? Самое простое — расширить обучающую выборку, увеличить словарь. Большая часть ошибок вызвана отсутствием слова в словаре. Например, в каталоге, скорее всего, нет корректного с точки зрения правописания наименования «роял канин».
Мы планируем разбавить выборку реальными запросами и тщательнее отбирать данные для обучения. В каталогах продавцов встречаются банальные опечатки и орфографические ошибки и разные варианты написания трудных слов, такие как «силикагель» и «силикогель».
Тестируем SymSpell
Еще один алгоритм исправления ошибок, SymSpell, по заверению его автора Вольфа Гарби (Wolf Garbe), должен давать те же результаты, что и другие спеллчекеры, но в «миллион раз быстрее». Прирост скорости достигается благодаря тому, что для обучающей выборки создается словарь — хэш таблица, куда складываются все возможные вариации каждого слова, полученные путем удаления символов глубиной n. При поиске кандидатов для нового слова производятся аналогичные удаления символов и поиск по полученным ключам в словаре.
На тестовой выборке мы убедились, что прирост скорости действительно высокий: она составила 2500 запросов в секунду при аналогичном рекурсивном подборе кандидатов. Но при этом нет гарантии, что алгоритм проверит всех кандидатов. Мы решили, что скоростью можно пожертвовать и сразу искали всех кандидатов с глубиной 2.
Кроме того, для подбора лучших кандидатов Гарби предлагает использовать взвешивание слов, аналогичное тому, что мы сделали для алгоритма Дамерау-Левенштейна, и взвешивание биграмм. Мы взяли те же тренировочные данные, получили оттуда все токены и биграммы и обучили алгоритм SymSpell.
В результате SymSpell показал более высокую скорость и точность исправления отдельных слов и такую же общую точность, как у других рассмотренных алгоритмов. Еще мы заметили, что Symspell чаще других алгоритмов делит слова. На еще одном тестовом датасете, состоящем из ошибочно написанных отдельных слов, разница в точности с алгоритмом DeepPavlov составила 2-3%, что может объясняться невозможностью взвесить биграммы слов.
Наши выводы
На исследования ушел один спринт — две недели. За это время мы искали готовые решения, открытые решения с какими-то доработками и тестировали все на наших данных. В итоге мы посчитали, что алгоритм SymSpell — самый перспективный. Да, он зависим от обучающей выборки и на других данных точность может падать на 2-3 %. Чтобы это исправить, нужно тщательно отбирать обучающие данные. Тем не менее, это с лихвой компенсируется его скоростью работы. В итоге мы вплотную приблизились к результатам Яндекс.Спеллера. SymSpell показал быструю и качественную работу, и мы уже внедряем его на проде.
В конечном счете, толковый алгоритм исправления опечаток пригодится не только для исправления поисковых запросов, но и для проверки продуктовых каталогов, редактуры отзывов и обращений от пользователей.