Решение одной из самых серьезных проблем для поисковых систем на основе ИИ: актуальность

Давайте узнаем, как реализовать ClickModels, чтобы извлекать релевантность из данных о потоках кликов.

Построение системы поисковой системы обычно по большей части следует за некоторыми хорошо известными шагами:

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

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

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

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

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

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

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

Итак, без лишних слов, давайте посмотрим, как вывести поисковые системы на новый уровень.

Итак, актуальность почему?

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

В этой среде (и мы можем утверждать, что большинство поисковых движков работают в аналогичном контексте) наблюдаемые данные содержат:

Что ищут пользователи.
Контекст поиска (регион пользователя, демографические данные, его предпочтения и т. Д.).
Продукты, которые они нажимают.
Товары, которые они покупают после нажатия.

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

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

Что ж, теперь все становится сложнее.

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

Другой подход, который нас интересует, подразумевает неявную релевантность на основе данных «посещаемости». Данные Clickstream - это, по сути, запись взаимодействий между пользователями и самой поисковой системой. Вот один пример:

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

ClickModels для спасения!

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

Излагаемые далее идеи и концепции взяты из книги Александра Чуклина и других Click Models for Web Search.

У нас есть множество способов моделирования взаимодействия пользователей с ранжированным списком документов. Здесь для обсуждения и реализации будет выбран подход динамической байесовской сети (DBN). Однако имейте в виду, что как только вы поймете концепции и теорию, лежащую в основе модели, вы сможете экстраполировать эти знания, используя любые переменные, которые сочтете подходящими. В книге Александра, например, рассматриваются несколько других моделей.

Для начала вот графическое представление DBN, используемого для извлечения релевантности из данных:

Все переменные в этой модели подчиняются распределению Бернулли, что означает, что они могут быть либо 0, либо 1 с некоторой вероятностью p. Вот основные концепции, которые нужно понять из сети:

r означает позицию, связанную с данным документом на странице поиска; r=0 означает первый документ, r+1 относится к следующему документу с позиции r.
u - идентификатор документа.
E_r - случайная величина, известная как «Обследование». Как следует из названия, он определяет, исследовал ли пользователь документ (например, E = 1) или нет (E = 0). Документ не может иметь кликов или покупок, если он не был проверен.
A_u указывает, является ли соответствующий документ u привлекательным для результата. Если документ привлекательный (A = 1), то наблюдается событие щелчка.
S_ur указывает, удовлетворяет ли документ в позиции r клиентам. Когда они удовлетворены (S = 1), они прекращают изучение новых документов. Документы о покупке уже признаны удовлетворительными.
C_r - это наблюдаемая переменная кликов, полученная из набора данных потока кликов.
P_r относится к наблюдаемым покупкам. Если P = 1, то S = 1. Эта переменная имеет смысл только тогда, когда документы выставлены на продажу.
γ - это вероятность того, что пользователи продолжат изучение документов на позициях выше r, когда еще не удовлетворены.

Используя наш предыдущий пример смартфонов, вот как будет представлен DBN:

Обратите внимание, что для каждого документа мы связываем набор скрытых переменных (A привлекательность, S удовлетворенность, E xamination), которые моделируют, как и почему пользователи взаимодействуют так же, как и с результатами работы движка. Клики и Покупки закрашены серым цветом, поскольку они являются наблюдаемыми переменными (данные потока кликов).

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

Например, предположим, что мы связываем α, чтобы представить вероятность того, что данный документ привлекателен, и σ для пользователя, удовлетворенного. Если мы воспользуемся каким-либо методом оптимизации, чтобы узнать на основе данных, какими должны быть эти значения, мы, как следствие, сможем найти релевантность для каждого документа.

Для этого давайте начнем описывать нашу сеть с помощью набора правил (эти правила будут использоваться в процессе оптимизации):

Вот краткое объяснение каждого правила:

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

(2) α - параметр, определяющий вероятность того, что привлекательность равна 1.

(3) Мы должны наблюдать щелчок, если документ проверен и привлекателен.

(4) Если на документ не нажали и не купили, то он не может считаться удовлетворительным для данного запроса.

(5) Вероятность того, что документ будет удовлетворительным, равна σ, если на документ щелкнули, но не купили.

(6) Удовлетворенность составляет 1, если наблюдаются клики и покупки.

(7) Если предыдущий документ был удовлетворительным, пользователи не продолжали изучать новые продукты.

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

(9) Вероятность наблюдения за щелчком определяется вероятностью щелчка при условии умножения на вероятность проверки (правило Байеса, которое распространяется на то же, что и вероятность того, что на него щелкнули и исследовали), выраженную как α * ε .

Имея уравнения, которые управляют моделью DBN, можно использовать некоторые методы, чтобы найти значения для α, σ и γ, которые наилучшим образом объясняют наблюдаемые данные.

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

В нашем случае наш DBN имеет следующее выражение логарифмической вероятности:

X - это каждая переменная Бернулли, используемая для описания данных (в нашем случае это «A», «S» и «E»).
C и P - это наблюдаемые клики и покупки.
ψ - это набор переменных, которые мы ищем для описания данных (α, σ и γ).

Суммирование происходит по «s», что означает сеанс и представляет взаимодействие пользователя с поисковой системой.

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

На самом деле это известная проблема. И, как оказалось, помимо MLE, есть еще одна техника - алгоритм ожидание-максимизация (EM) (он работает вроде как популярный алгоритм kMeans).

Он начинается с присвоения случайных ожидаемых значений скрытым переменным α, σ и γ. Затем он переходит к итерации процесса оптимизации с использованием определенной функции стоимости. Переменным присваиваются новые значения, и процесс повторяется до тех пор, пока не будет достигнута сходимость или общее количество итераций.

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

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

Вот функция стоимости Q, определенная в нашей модели:

Par (X) = p относится к родительским элементам переменной X. Например, в нашем DBN переменная S (удовлетворение) имеет в качестве родителей клики и покупки, учитывая соединения границ сети. Переменная θ представляет собой скрытые параметры, которые мы пытаемся найти (α и т. Д.). I - это индикаторная функция, а Z - это просто ссылка для значений, не связанных с θ, которые будут отброшены в процессе вывода.

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

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

Давайте посмотрим, как адаптируется каждая переменная, используя определение уравнения 10.

Привлекательность - α

Начнем с того, что переменная привлекательности определяется как:

q расширяется для запроса, а u представляет документ. Обратите внимание, что в нашем представлении DBN у α нет родителей, поэтому он определен напрямую.

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

Где cr - коэффициент конверсии данного документа u для данного запроса q, определяемый как общий объем продаж, деленный на общее количество появлений документа на страницах результатов для данного запроса q. Он определяется только в том случае, если документы выставлены на продажу, в противном случае просто считается равным нулю.

Пока что у нас есть это:

Где | S | - количество всех сеансов, в которых страница результатов поиска по запросу q вернула документ u.

Обратите внимание, что, учитывая архитектуру нашей DBN, переменные C и P независимы от C, что означает, что нам нужно учитывать только первое:

Уравнение 13 можно продолжить следующим образом:

C_{>r} равно 1, если над r наблюдается какой-либо щелчок, и 0 в противном случае.

Числитель числа 14 можно развить следующим образом:

А знаменатель немного сложнее:

Уравнение 14.4 следует реализовать рекурсивно. Вы можете увидеть, как это было сделано на pyClickModels, вот пример:

Наконец, мы можем использовать все эти уравнения и смешать их вместе, чтобы прийти к окончательному правилу адаптации переменной привлекательности:

Вы можете увидеть здесь, как это правило было реализовано на pyClickModels:

Удовлетворение - σ

Переменная удовлетворенности σ действительно имеет родителей, как это определено в нашем DBN. Следовательно, из уравнения 10 нам нужно использовать сеансы только там, где переменная определена, с соответствующими родителями.

В частности, уравнение 5 уже описывало это. У нас есть что:

Таким образом, используя уравнение 10:

S'_{uq} охватывают все сеансы, в которых документ u был нажат, но не куплен.

Числитель (16) может быть развит как:

Что напрямую сводится к правилу адаптации для удовлетворения:

Это было проще, чем привлекательность. Вот как было реализовано это уравнение:

Настойчивость - 𝛾

Теперь перейдем к самой сложной переменной из всех.

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

Как было показано ранее, это дает:

Чтобы получить правило обновления для 𝛾, мы будем использовать следующую ожидаемую достаточную статистику (ESS):

Где E_r и S_ur - родители E_{r+1}.

Вспомогательная функция Φ может быть реализована для дальнейшего развития 19. У нас будет следующее:

Где:

Стратегия состоит в том, чтобы разделить уравнение 20 на 3 основные части:

Третий разработан как:

Чтобы разработать уравнение внутренней вероятности, мы имеем следующее:

А также что:

Используя 22 и 23 в 21, мы наконец получаем:

Первый разработан как (обратите внимание, что переменный коэффициент конверсии здесь обозначен как «w»):

И, наконец, второе уравнение представляет собой прямую реализацию уравнений от 1 до 9.

Вы можете увидеть, как эти 3 уравнения были реализованы здесь:

После этого просто обновить параметр:

И, наконец, это все, что нужно для реализации DBN, как было определено ранее.

Что ж, теперь вернемся к нашей основной цели, как нам извлечь из всего этого релевантность?

Наконец-то… Актуальность

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

Релевантность ранжирования или суждения будут просто продуктом обоих, то есть:

В pyClickModels можно экспортировать значения суждений после подбора модели. Файл JSON с разделителями новой строки создается для каждого поискового запроса / контекста и всех соответствующих документов.

Собираем все вместе: время кодирования

Давайте теперь посмотрим на все эти концепции в действии.

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

Вот код, необходимый для нашего теста:

Для этого требуется клиент GCS и pyClickModels, оба могут быть установлены с помощью:

pip install pyClickModels google-cloud-storage

Просто скопируйте и вставьте код на свой локальный компьютер и запустите его с помощью Python. Файл будет сохранен в /tmp/pyclickmodels/model/model.gz. Открыв файл, вы должны увидеть несколько строк JSON, например эту:

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

Вывод

Вот и все!

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

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

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

Полную реализацию кода можно найти в репозитории с открытым исходным кодом pyClickModels:

WillianFuks / pyClickModels
Реализация ClickModels Cython, использующая вероятностные графические модели для определения поведения пользователя при взаимодействии… github.com