Простая эвристика исправления поискового запроса для ограниченных ресурсов

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

Вот некоторые из наших самых популярных запросов с ошибками:

  • Сирача ♨️
  • Зучинни 🥒
  • Джалепено 🌶
  • Кантелопа 🍈
  • пармезский 🧀

В первые дни существования Instacart наша команда была небольшой и разборчивой, и мы вручную добавляли условия исправления для часто неправильно написанных запросов. Но такой подход не масштабируется. Мой первый проект в качестве первого инженера по машинному обучению в команде Instacart Search & Discovery 5 лет назад был направлен на решение этой проблемы. С технической точки зрения мы хотели улучшить функцию Отзыв нашей поисковой системы для запросов с ошибками.

Проблема исправления запроса

В общем, мы сталкиваемся с двумя основными проблемами исправления запросов:

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

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

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

Для любой данной проблемы могут быть стандартные современные решения, которые не всегда легко реализовать. Вначале нам приходилось решать ряд технических проблем при создании торговой площадки Instacart, и было невозможно определить приоритеты каждой из этих проблем. Таким образом, при решении этих проблем нам приходилось выбирать между лоскутками и современными технологиями. В те дни мы обычно использовали подход к решению проблем: можем ли мы использовать простой подход, который решает 80% -90% проблемы за короткий период времени? Мы часто прибегали к быстрой, но очень эффективной эвристике. Это не только решило большинство проблем с неправильным написанием, но и дало нам дополнительное преимущество, помогая решить проблему переформулирования запроса, которую мы объясним ниже.

Путь к успешному запросу

После ввода поискового запроса покупатель выполнит одно из следующих действий:

  • Добавьте товар в корзину, если запрос дает точные результаты с хорошей запоминаемостью (это событие называется конверсией).
  • Найдите вариант того же запроса, если они не получают результатов или не удовлетворены результатами.
  • Искать совсем другой запрос, если они решат не выполнять конвертацию по данному запросу.
  • Перейдите на страницу оформления заказа, чтобы разместить заказ
  • Откажитесь от Instacart.com, если они не удовлетворены опытом.

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

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

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

Эвристический

Мы придумали следующую эвристику, чтобы построить эту цепь Маркова и легко сгенерировать пары исправлений запроса:

  • Определите все последовательные пары поисковых запросов на основе исторических данных поисковых запросов (чем больше у вас данных, тем лучше)
  • Оставьте только те пары запросов, где второй запрос приводит к конверсии.
  • Определите частоту появления этих пар запросов в истории
  • Используйте порог минимальной частоты (скажем, 10 или 100) и отбросьте другие пары запросов.
  • Для каждого запроса вычислите вероятность перехода к каждому последующему запросу из данных пары запросов.
  • Вычислить расстояние Левенштейна между запросами в каждой паре (в основном это количество букв, которые вам нужно изменить, чтобы перейти к новому запросу)
  • Если расстояние Левенштейна меньше небольшого порога (мы выбрали 2), то пары можно классифицировать как пары коррекции заклинания.

Представление

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

>>> correct_query(‘avacado’)
‘avocado’
>>> correct_query(‘siracha’)
‘sriracha’
>>> correct_query(‘zuchinni’)
‘zucchini’
>>> correct_query(‘jalepeno’)
‘jalapeno’
>>> correct_query(‘cantelope’)
‘cantaloupe’
>>> correct_query(‘guac’)
‘guacamole’
>>> correct_query(‘parmesean’)
‘parmesan’

Мы также поняли, что, глядя на пары, у которых расстояние Левенштейна больше, чем выбранный порог (скажем, 2), вы также можете сделать вывод о возможных переформулировках запроса. Например:

>>> correct_query(‘organic ground pork’)
‘ground pork’
>>> correct_query(‘canned soup’)
‘soup’
>>> correct_query(‘cremini’)
‘mushrooms’
>>> correct_query(‘prawns’)
‘shrimp’

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

Получение результатов

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

Мы смогли загрузить нашу эвристику исправления и переформулирования запроса, используя наши собственные данные. Другими словами, мы создали нашу первую эвристику исправления поискового запроса :)

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

Хотите работать над следующими поколениями Instacart Search? Наша команда алгоритмов принимает на работу! Перейдите на instacart.com/careers, чтобы увидеть наши текущие вакансии.