Соавтор: Рич Гильмен
Поговорим о поиске.
Когда этот пост был опубликован, Pluralsight предлагал более десяти тысяч курсов, руководств и практических занятий, чтобы помочь людям улучшить свои технологические навыки. Мы освещаем такие темы, как облачные вычисления, безопасность, разработка программного обеспечения, а также наука о данных и машинное обучение, и наш каталог растет с каждым днем.
Так как же организовать всю эту информацию и сделать ее доступной для поиска?
Цель этой статьи - описать на высоком уровне, как работает поиск в Pluralsight и как мы используем методы машинного обучения, такие как байесовские сети и байесовская гиперпараметрическая оптимизация, для повышения качества наших результатов.
Индексирование с помощью Elasticsearch
Естественно начать описание любой хорошей поисковой системы с ее индекса, и для этого мы используем Elasticsearch.
Почему именно Elasticsearch?
Некоторые решения лучше придерживаться как можно более практичными. Elasticsearch, который вместе с Logstash и Kibana формирует стек ELK, обычно используется для хранения и обработки журналов событий, а не для общего поиска документов.
При выборе движка мы рассмотрели четыре варианта:
Хотя Algolia и Vespa за это время сделали себе имена как основные поисковые системы по тексту, на момент принятия нашего первоначального решения они были относительно новыми. Таким образом, мы решили не использовать их, потому что не чувствовали себя в состоянии сделать ставку на движок, который еще не проявил себя и получил широкое распространение в отрасли. Возможно, наше решение было бы другим с учетом нынешнего контекста.
Это оставило выбор между Elasticsearch и Solr, которые являются системами полнотекстового поиска, основанными на Apache Lucene. Оба являются зрелыми, масштабируемыми, с открытым исходным кодом и активно используются в производственных средах. Для большинства практических целей они эквивалентны. Solr может быть даже «правильным» вариантом, в зависимости от того, кого вы спрашиваете. У него более крупное, более активно вовлеченное сообщество для целей науки о данных, и если бы мы его выбрали, в нашем распоряжении было бы более широкий выбор плагинов.
Однако для нас использование Elasticsearch казалось более ответственным решением с точки зрения развертывания и обслуживания. Elasticsearch лучше подходит для нашей существующей среды DevOps на базе Amazon, где кластером можно управлять и масштабировать с помощью такого же эластичного (не связанного) балансировщика нагрузки, который обрабатывает нагрузку для других наших приложений. Это были инструменты и навыки, уже доступные нашей команде. Solr, с другой стороны, потребовал бы, чтобы Apache Zookeeper отдельно обрабатывал масштабирование кластера, чего наши инженеры DevOps настоятельно не рекомендовали, основываясь на предыдущем опыте. Сам Elasticsearch тоже был несовершенным, его нужно было правильно настроить, чтобы избежать проблемы связи узлов данных, известной как «разделение мозга», но это все равно считалось меньшим риском, чем управление Zookeeper. В конце концов, выбор инструментов для уменьшения накладных расходов DevOps и головной боли оказался хорошим решением и остается отличным ориентиром для выбора инструмента в целом.
Перевернутый индекс
Elasticsearch позволяет нам сопоставлять все токены, которые появляются в нашем каталоге - обычно слова в заголовках, тегах, описаниях и т. Д. - с документами (курсами, руководствами, лабораторными работами и т. Д.), Которые их содержат. По сути, он работает так же, как указатель, который вы можете найти в конце книги. С помощью этого сопоставления терминов, представляющих интерес, с соответствующими страницами, на которых они упоминаются, читатель может быстро найти информацию, которую он ищет.
На компьютере эта структура данных называется «инвертированным индексом», потому что вместо отображения документов на термины, которые они содержат (как в «прямом индексе»), выполняется обратное. Преимущество использования такого индекса заключается в том, что он позволяет нам выполнять быстрый поиск документов на основе заданных условий запроса.
Рейтинг с BM25
Учитывая, что мы можем использовать этот индекс для быстрого поиска документов, которые имеют отношение к указанным условиям запроса, как мы сопоставим эти результаты друг с другом?
Elasticsearch делает это, оценивая результаты каждого запроса с помощью алгоритма под названием BM25. BM25 - это немного улучшенная версия tf-idf, которая учитывает частоту терминов, обратную частоту документов, и длину рассматриваемых документов.
Вот полная формула BM25:
На первый взгляд это может показаться сложным, но на самом деле все сводится к трем основным факторам.
Первый - это частота термина, или f (q_i, D), которая представляет собой просто подсчет количества раз, когда каждый термин в запросе, q_i, появляется в каждом документе в корпусе, D. Чем больше раз в документе упоминается соответствующий токен, тем выше оценка этого документа.
Второй - обратная частота документов, или IDF (q_i), которая мала, когда термин запроса q_i появляется во многих документах, и увеличивается по мере уменьшения количества совпадающих документов. Это говорит о том, что сопоставление по более редким терминам должно быть более показательным, чем сопоставление по очень распространенным.
Третий - коэффициент нормализации длины документа в знаменателе справа. Он устанавливает, что чем больше размер документа, тем меньшее значение имеет каждый отдельный токен в нем. В конце концов, статья из 3000 слов, в которой «Elasticsearch» упоминается десять раз, вероятно, более актуальна для запроса «Elasticsearch», чем книга из 100 000 слов, в которой он упоминается такое же количество раз.
Члены b и k1 - это константы, которые определяют, как мы хотим масштабировать эти факторы и как они должны сравниваться друг с другом. Мы используем значения по умолчанию для Elasticsearch 0,75 и 1,2 соответственно.
Определение нашего алгоритма поиска
Одна из вещей, которая усложняет поиск, заключается в том, что мы не просто индексируем один большой блок текста для каждого документа. Курс Pluralsight может состоять из ряда как текстовых (например, заголовок, описание, теги и т. Д.), Так и нетекстовых (например, даты публикации, оценок пользователей, популярности и т. Д.) Полей. Так как же объединить все эти источники информации в единую оценку?
На практике мы указываем эти компромиссы («формулы» нашего алгоритма поиска) в файлах конфигурации с шаблонами Mustache, которые точно сообщают Elasticsearch, как обрабатывать многословные запросы, как сравнивать совпадения в различных числовых и нечисловых полях и как сравнивать оценки по разным модальностям контента. Здесь нам нужно точно сказать, насколько важен каждый из этих сигналов по сравнению с остальными. Например, сопоставление запроса с названием курса так же важно, как сопоставление с его описанием? Это вдвое важнее? В десять раз важнее?
В конечном итоге нам нужен способ оценить, насколько хороши наши алгоритмы поиска.
Онлайн-оценка
Чтобы сравнить эти алгоритмы-кандидаты друг с другом и определить, какие из них лучше работают в реальных условиях, мы можем создать несколько различных вариантов наших файлов Mustache и запустить A / B (или многовариантный) эксперимент. Во время этих экспериментов мы случайным образом разделяем наш веб-трафик на различные конкурирующие варианты и отслеживаем взаимодействие пользователей для каждого сеанса. Затем, в конце эксперимента, мы сравниваем и видим, какие варианты привели к наибольшему вовлечению.
Чтобы выполнить это случайное разделение нашего трафика во время запроса, мы хэшируем уникальный дескриптор пользователя, запрос, который он сделал, и уникальную сигнатуру для проводимого эксперимента, и используем это значение для индексации в массив вариантов, которые мы хотим сравнить. . Таким образом, каждый вариант потенциально доступен для каждого пользователя и для каждого запроса. Это также означает, что когда пользователь выполняет один и тот же запрос несколько раз, он всегда получает одни и те же результаты, не требуя от нас отслеживания какой-либо дополнительной информации.
Еще одно преимущество этого простого подхода к хешированию по сравнению с бандитским обслуживанием - это еще одна популярная стратегия для определения того, какой экспериментальный вариант обслуживать - заключается в том, что нам не нужно так сильно беспокоиться о периодическом или событийном поведении, искажающем нашу аналитику. Мы знаем, что наши пользователи взаимодействуют с поиском в рабочее время иначе, чем утром и вечером. Они также взаимодействуют с ним по-другому в выходные дни, чем в будние дни, и то же самое касается праздников и специальных мероприятий Pluralsight, таких как PS Live или наши бесплатные выходные. Поддерживая последовательную стратегию разделения, нам не нужно беспокоиться о том, что наши варианты будут неравномерно представлены в этих различных сценариях использования.
Автономная оценка
Проведение эксперимента A / B, как описано выше, является окончательной проверкой того, насколько полезны изменения для нашего алгоритма поиска. Но их запуск требует времени, они заставляют наших пользователей получать определенный опыт, и мы можем проверять только несколько вариантов за раз. Было бы полезно, если бы у нас был способ судить, какие последствия может иметь изменение, без необходимости запрашивать обратную связь в реальном времени.
Ограничение себя только живыми экспериментами также затрудняет отделение влияния полей от их веса. Предположим, мы добавляем новое поле описания в наш алгоритм поиска. Мы прикидываем ему какой-то вес и проводим тест. Если мы увидим улучшение взаимодействия с пользователем, мы развернем новое поле. Однако, если мы видим низкое вовлечение пользователей, было ли это из-за того, что поле было плохим, или из-за того, что вес был неправильного размера? Этот процесс предположения и проверки является повторяющимся и немного неуклюжим. Учитывая, насколько это дорого, было бы замечательно, если бы мы могли придумать лучший вес для нового поля до запуска эксперимента, чтобы в эксперименте нужно было только измерить качество поля. К счастью, мы можем добиться этого, оценив производительность алгоритма по некоторым показателям ранжирования, используя суждения о релевантности.
Оценка релевантности показывает, насколько документ релевантен конкретному запросу. Например, оценка релевантности может быть числом от 0 до 4, где 0 означает, что документ полностью не соответствует запросу, а 4 означает, что он полностью релевантен. Предположим, у нас есть эти суждения для многих пар запрос-документ, тогда их можно использовать для оценки наших алгоритмов поиска, не раскрывая их реальным пользователям. Для этого мы решили использовать метрику ранжирования под названием Нормализованная дисконтированная совокупная прибыль (nDCG), которую мы рассмотрим ниже.
Совокупный выигрыш (CG)
CG @ k измеряет общий объем информации до некоторой позиции k. Это сумма оценок релевантности первых k документов.
i - это позиция документа, а rel_i - его оценка релевантности.
Дисконтированная совокупная прибыль (DCG)
DCG @ k измеряет общий прирост информации до некоторой позиции k с документами, занимающими более высокий рейтинг (меньший i), и вносит больший вклад в окончательную оценку. Для задач ранжирования важно, чтобы релевантные результаты заняли первое место в рейтинге, потому что пользователи с большей вероятностью увидят эти результаты. Чтобы учесть это, DCG использует коэффициент дисконтирования на основе позиции. Чем ниже результат в рейтинге (больше i), тем выше скидка и чем выше результат в рейтинге (меньше i), тем меньше скидка. Вот формула DCG @ k.
По мере увеличения i знаменатель увеличивается, увеличивая скидку. Если мы помещаем очень релевантный документ на первое место в рейтинге, его вклад полностью сохраняется. Однако, если мы поместим его в конец рейтинга, его вклад сильно уменьшится.
Нормализованный дисконтированный совокупный прирост (nDCG)
nDCG нормализует оценку DCG до диапазона от 0 до 1. Это позволяет сравнивать производительность нашего алгоритма поиска по разным запросам, где будет разное количество возвращаемых результатов, а полученные результаты могут иметь разную степень релевантности. Мы нормализуем DCG, разделив его на идеальный DCG (IDCG). IDCG - это DCG, который мы получаем, когда ранжируем результаты с использованием истинных оценок релевантности; это максимально возможная DCG, которую может получить алгоритм. Следовательно, nDCG @ k рассчитывается как
Как эта офлайн-оценка работает на практике? Имея набор полей, по которым мы хотим выполнить поиск, мы можем настроить шаблон поиска с разными наборами весов. Используя nDCG, мы можем сравнить, как работают эти различные конфигурации веса. Наша цель здесь - выбрать набор весов, который максимизирует nDCG. Этот автономный процесс оценки позволяет нам выбрать оптимальные веса перед проведением экспериментов. Затем эксперимент должен только измерить качество полей.
Нажмите "Моделирование"
Вам может быть интересно, откуда мы получаем эти оценки релевантности, используемые для расчета nDCG. Один из подходов к получению этих суждений - собрать человеческие аннотации. Мы могли бы попросить экспертов в предметной области оценить, насколько каждый результат поиска соответствует нашим наиболее распространенным запросам по шкале (опять же, например, от 0 до 4). Однако сбор достаточного количества данных таким образом, чтобы судить о релевантности, является дорогостоящим, и его нужно будет делать регулярно, чтобы не отставать от нашего регулярно обновляемого каталога. Мы также обнаружили, что эксперты в предметной области часто расходятся во мнениях относительно того, насколько курс соответствует запросу.
Учитывая эти трудности со сбором вручную размеченных данных, мы решили использовать наши журналы кликов для выработки суждений о релевантности. Эти данные намного дешевле получить, и у нас их много. Он также менее склонен к индивидуальным предпочтениям, потому что мы объединяем всех наших пользователей. Чтобы извлечь суждения о релевантности из наших журналов кликов, мы построили динамическую байесовскую сетевую модель кликов, которая предсказывает, насколько курс релевантен запросу после учета смещения позиции, поскольку курсы в верхней части списка результатов, естественно, получают больше кликов. Вот диаграмма для модели щелчка:
График и уравнения могут выглядеть устрашающе, но давайте разберемся, что здесь происходит. Модель щелчка предполагает, что пользователи просматривают результаты поиска линейно сверху вниз, что означает, что они просматривают один результат за другим и не пропускают страницу. После того, как пользователь выполнит поиск запроса, он изучает первый результат. Если их привлекает результат, они нажимают на результат. Если их не привлекает результат, они переходят к изучению следующего результата. Щелкнув по результату, они могли быть либо удовлетворены, либо не удовлетворены. Если они удовлетворены, они останавливают процесс поиска. Если они не удовлетворены, они могут продолжить изучение следующего результата с некоторой вероятностью гамма или они могут отказаться и полностью покинуть поиск с некоторой вероятностью 1 - гамма.
Несмотря на то, что эта модель кликов не учитывает все действия, которые пользователь может выполнять на странице результатов поиска, она по-прежнему является довольно хорошей моделью поведения пользователя. Естественное определение релевантности также выпадает из этой модели. Это вероятность того, что пользователь будет удовлетворен результатом, если он его изучит. После того, как мы загрузим наши журналы кликов в эту модель, мы получим эту вероятность для каждой пары запрос-курс в журналах кликов. И эти оценки являются суждениями о релевантности в нашей автономной оценке.
Байесовская оптимизация
Итак, теперь, когда у нас есть показатель оценки (nDCG) и ранжирование «истинных» результатов, которые мы можем построить на основе оценок релевантности, которые мы получаем из нашей модели кликов, как нам выбрать, какие веса полей (как описано в разделе «Определение нашего алгоритма поиска» раздел) проверить?
В машинном обучении у нас есть несколько методов выбора, из которых мы можем выбирать. Один из подходов - случайный поиск, при котором мы просто генерируем случайные наборы весов, чтобы попытаться выбрать тот, который работает лучше всего. Другой подход - поиск по сетке, где мы определяем возможные значения для каждого веса и пробуем все возможные комбинации. Эти подходы хороши, но мы можем добиться большего с помощью байесовской оптимизации.
Байесовская оптимизация - это последовательный алгоритм настройки гиперпараметров для моделей машинного обучения. В отличие от случайного поиска или поиска по сетке, байесовская оптимизация оценивает распределение функции потерь на основе исторических испытаний. Он использует это распределение для оценки оптимальных гиперпараметров, которые минимизируют потери.
Вот как обычно работают эти алгоритмы. Например, вы обучили модель, используя некоторые настройки гиперпараметров. Основываясь на результате этого испытания, алгоритм обновляет свое предварительное мнение о распределении функции потерь, чтобы сформировать апостериорное распределение. Затем он угадывает, какая наилучшая настройка гиперпараметров основана на новом апостериорном распределении, и использует его для обучения другой модели. Учитывая результаты нового испытания, алгоритм снова обновляет свое распределение потерь и угадывает, какой должна быть новая оптимальная установка гиперпараметров, и использует новое предположение для обучения другой модели. Этот процесс продолжается до достижения определенного количества попыток.
Подход, который мы приняли, заключается в том, чтобы рассматривать веса шаблонов как гиперпараметры, и мы хотим выбрать веса, которые максимизируют автономную nDCG. Используя этот подход, мы значительно упростили наш процесс настройки релевантности.
Тем не менее, это не полная замена онлайн-оценки, поскольку мы по-прежнему хотим быть уверены, что любые вносимые нами изменения в конечном итоге улучшат взаимодействие с пользователем. Этот поэтапный подход позволяет нам использовать наилучшие веса при добавлении новых полей в наш алгоритм поиска и позволяет нашим онлайн-экспериментам сосредоточиться на качестве полей, а не на весах.
Вывод
В этой статье мы подробно рассказали, как работает поиск в Pluralsight. В качестве серверной части мы используем Elasticsearch, поскольку он оптимизирован для поиска и ранжирования документов с помощью BM25. Мы загружаем наши исторические журналы пользователей, чтобы построить модель кликов, которая выводит суждения о релевантности, используемые для оценки наших алгоритмов поиска. После того, как мы использовали байесовскую оптимизацию для настройки весов новых алгоритмов, мы тестируем их в производственной среде с фактическими отзывами пользователей, чтобы измерить их эффективность. Если они эффективны, мы распространяем их на всех пользователей. Если нет, мы анализируем данные наших экспериментов, чтобы выяснить, почему они повлияли на взаимодействие с пользователем. Затем мы начинаем заново. Так мы улучшаем поиск в Pluralsight. Мы итеративно добавляем новые функции и тестируем их. Мы надеемся, что вам так же понравилось читать эту статью, как и нам!
