Как развивать «Поиск» в продукте - часть вторая

Привет! Я Женя Гурьянов, Chief Product Officer в компании DocDoc. В своей предыдущей статье я рассказывал про то, как наполнять бэклог развития Поиска в продукте и как приоритизировать поисковые задачи. В этой статье я расскажу, что такое релевантность, как построить поиск книг в электронной библиотеке и поиск объявлений в онлайн-классифайде.

Пора нам ввести понятие релевантности. Согласно Википедии:

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

И сразу, для общего развития, будет полезным узнать ещё одно определение:

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

Разницу обычно раскрывают на следующем примере:

Пользователь вводит в поисковик запрос [сергей шнуров]. Вся выдача Google будет релевантна запросу пользователя (во всех документах, которые вернул поисковик есть наш запрос).

Теперь вопрос: Будет ли выдача пертинентна запросу пользователя? Соответствует ли она тому, что подразумевал пользователь? А пользователь мог подразумевать всякое-разное:

может быть он хотел найти фото Шнурова, почитать последние новости о его жизни, почитать биографию или послушать его песни.

Вот, кстати, что вернул Google на запрос [сергей шнуров]:

В выдаче гугла не просто новости, включающие в себя наши ключевые слова. Google покрывает большое количество всевозможных кейсов. Тут и фото, и клипы, и биография, и песни-онлайн, ... Алгоритм пытается отгадать, что подразумевал пользователь своим запросом.

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

Теперь переходим к делу! Будем строить свой первый алгоритм поиска.

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

Но вот проблема, у вас 1 млн. книг и пользователям нужно дать возможность найти ту книгу, которая им нужна.

Книгу в данной задаче называют документом, а всю электронную библиотеку корпусом документов.

Пользователь вводит запрос. Пока из одного слова. Например, [роза].

Как же нам помочь пользователю? Давайте рассуждать.

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

Не будем долго останавливаться на этом пункте, но для общего понимания рассмотрим упрощенный алгоритм стемминга для нашего примера (отсечение суффиксов и окончаний).

розы → роз
розу → роз
розой → роз

Теперь [розы], [розу] и [розой] можно легко сравнивать.

Идем дальше.

Очевидно, что если искомое слово встречается в книге (документе из библиотеки), то это хорошо. Чем чаще встречается, тем лучше.

Так мы дошли до следующего понятия:

TF (term frequency - частота слова) - отношение числа вхождений некоторого слова к общему числу слов документа.

Чем больше TF, тем более релевантен документ.

Продолжаем рассуждения...

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

Например, слово [трансцендентный] точно должно встречаться редко.

Понятно, что чем более редкое слово, тем более релевантен документ, в котором оно найдено.

Поэтому введем еще одно понятие:

IDF (inverse document frequency - обратная частота документа) - инверсия частоты, с которой некоторое слово встречается в документах коллекции.

Чем больше IDF, тем более релевантен документ.

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

Итого, для каждого слова и документа в нашей библиотеке (корпусе документов) можно рассчитать меру TF-IDF:

TF-IDF = TF x IDF.

Чем больше TF-IDF, тем более релевантен документ по конкретному запросу.

Документы в поисковой выдаче должны сортироваться по убыванию этой меры TF-IDF. Такая сортировка поисковой выдачи в информационном поиске называется ранжированием.

Ранжирование - сортировка документов в поисковой выдаче.

Всё размышление выше касалось ситуации, когда пользователь ввел 1 слово в поисковую строку.

А что делать, если пользователь ввёл запрос [черная роза].

Во-первых надо разбить этот запрос на 2 слова.

Во-вторых, для каждого из двух слов рассчитать TF и IDF. Теперь у нас есть следующие величины: TF1, TF2, IDF1, IDF2.

В-третьих, умные дяди придумали поисковую функцию, которая позволяет ранжировать такие запросы. Эта поисковая функция называется BM25.

BM25 - поисковая функция на множестве документов, которые она оценивает на основе встречаемости слов запроса в каждом документе, без учёта взаимоотношений между ними (например, близости).

В формулу входят TF, IDF каждого из слов, свободные коэффициенты, длина документа и средняя длина документа в корпусе:

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

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

Так получается для придуманного алгоритма [роза черная] и [черная роза] будут одинаковыми...

Более того, если у вас есть 2 документа:

в первом документе есть ваш исходный запрос "...черная роза..." (подряд идущие слова)
а во втором "черная ночь ... (150 слов) ... роза завяла"

То для этих двух документов BM25 даст одинаковый скоринг и документы в поисковой выдаче будут находиться рядом.

Обычно для решения этой проблемы вводят понятие близости слов (proximity).

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

lcs (integer), Longest Common Subsequence (or Subset) - наибольшая общая подпоследовательность - длина максимального дословного соответствия между документом и запросом, измеряется в количестве слов.

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

в первом документе есть ваш исходный запрос "...черная роза..." (подряд идущие слова). lcs = 2.
а во втором "черная ночь ... (150 слов) ... роза завяла". lcs =1.

exact_hit (boolean) - точное совпадение документа и запроса. Принимает значение 1, если весь текст в поле документа соответствует пользовательскому запросу, 0 - если нет.

В случае поиска книг в библиотеке этот фактор может быть важен, если подразумевается полное совпадение с названием книги. Пусть все книги состоят из трех полей: название книги, автор книги, весь текст книги. Если пользователь ввел поисковый запрос [черная роза] и у нас в библиотеке есть книга с названием "Черная роза", то exact_hit для этой книги (документа) равен 1.

Раз уж мы заговорили о том, что документ может состоять из нескольких полей, то давайте рассмотрим ещё один важный фактор - вес поля. В Sphinx он обозначается как user_weight (integer). Веса для каждого поля присваиваются самим пользователем при настройке поискового движка. Что это значит? Если мы, например, уверены, что нахождение запроса в названии книги в 100 раз круче, чем нахождение его же в тексте книги, то прописываем вес поля для названия 100, для текста книги 1.

Как же скомпоновать итоговую цифру для учета близости слов (proximity)?

Обычно это взвешенная сумма факторов.

Например, для книг:

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

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

Final Score (релевантность) = Score (bm25) + proximity

Допустим вы придумали новый Авито или Юлу. И вам требуется проработать алгоритм ранжирования объявлений в случае, когда пользователь решил воспользоваться текстовым поиском.

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

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

Пользователь вводит запрос [синий горный велосипед], мы формируем ему выдачу:

Но давайте подумаем, что ещё влияет на покупку пользователем той или иной вещи на Юле и Авито? Какие ещё факторы ранжирования стоит учесть при составлении алгоритма?

Чем новее объявление, тем выше вероятность, что оно ещё актуально. С течением времени продавец может продать вещь, отдать знакомым или друзьям, потерять, пропить и тд

Чем новее объявление, тем оно лучше.

Как вносить подобные факторы в формулу руками?

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

График такой функции может иметь следующий вид:

Теперь у нас есть 2 числа - Релевантность и Актуальность. Актуальность мы "загоняли" в рамки от 0 до 1, поэтому эти 2 числа можно перемножить. Получается, что мы в зависимости от того, сколько времени прошло с подачи объявления, пропорционально уменьшаем релевантность этого объявления.

Есть и другие варианты "скрещивания" Релевантности и Актуальности. Если не маппировать Актуальность в [0,1], то можно итоговый ранк рассчитывать, как сумма Релевантности и Актуальности (но потребуется другая нормализация). В любом случае необходимо проверять качество такого ранжирования на данных (об этом поговорим в последующих статьях).

Товар без фото портит общее впечатление от площадки, а также отсутствие фото в большинстве случаев снижает вероятность продажи товара.

Почему бы не учитывать хотя бы фактор наличия фото в ранжировании объявлений?

Например, если фото есть, то к релевантности прибавляется какое-то большое число. Если фото отсутствует, то прибавляется 0.

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

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

Как ввести в формулу? Практически также, как и Актуальность/Свежесть объявления. Главное не забыть нормировать значения.

Казалось бы, почему бы и нет? Почему бы не учесть цену товара! Но прежде чем внедрять фактор цена, надо подумать вот о чем:

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

Не стоит забывать, что практически любой бизнес создается для зарабатывания денег.

Поэтому вполне логично монетизировать позицию объявления продавца в выдаче.

У Юлы есть Быстрая продажа объявления:
«Поднятие в ленте»: объявление поднимается вверх списка объявлений в категории, где размещен ваш товар
Аналогично у Авито - услуга называется "Поднятие в поиске".

Как бы мы её реализовали в нашей формуле? Да также как и свежесть!

При том что надо "дать возможность" продавцам платить как можно чаще, то есть функция поднятия должна быть убывающая по времени. Что вполне логично.

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

Вы считаете, что в алгоритме ранжирования должны принимать участие следующие факторы/признаки:

частота слова (TF)
обратная частота документа (IDF)
LCS, exact_hit ... (см выше)
время, которое прошло от подачи объявления до текущего момента
наличие фото
расстояние до продавца
платность
и многие другие

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

Этот черный ящик обучается на примерах - когда ему на вход дают конкретные признаки и затем дают "правильный" выход (правильную последовательность объявлений).

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

В следующей статье мы поговорим о метриках поисковой выдачи, а также я расскажу о том, как можно проверить, что вы не придумали ерунды - офлайн и онлайн оценки поисковой выдачи.