Case study: Алгоритмы и архитектура рекомендательной системы для поиска вакансий

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

Каждый месяц сервис Indeed.com посещает более 200 миллионов уникальных пользователей, а рекомендательная система ресурса обрабатывает миллиарды входных сигналов каждый день. В этой статье мы рассмотрим эволюцию нашей рекомендательной системы от минимально жизнеспособного продукта (minimum viable product, MVP), созданного на основе Apache Mahout, до гибридной системы, сочетающей в себе онлайн и офлайн обработку. Вы узнаете, как эти изменения повлияли на общую эффективность сервиса, а также о том, как мы справлялись с возникающими на пути проблемами, последовательно оптимизируя алгоритмы, архитектуру системы и формат модели. В конце мы поделимся несколькими рекомендациями, которые будут полезны при разработке любых высоконагруженных систем машинного обучения.

От поисковой системы к рекомендательной системе

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

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

Наше решение выйти за рамки поиска и внедрить рекомендательную систему в качестве новой формы взаимодействия имело под собой несколько причин:

  • 25% всех запросов к Indeed содержат в себе только местоположение и не содержат ключевые слова. То есть многие пользователи не знают точно, какие ключевые слова использовать при поиске.
  • Предоставляя целевые рекомендации, мы реализуем персональное взаимодействие с пользователем.
  • Рекомендации могут помочь даже самому искушенному соискателю обнаружить дополнительные вакансии, которые иначе остались бы вне поля его зрения.
  • Кроме того, учитывая, что рекомендации обеспечивают 35% продаж на Amazon и 75% просмотров на Netflix, становится очевидно, что рекомендательные системы имеют огромный потенциал.

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

  • Быстрое изменение набора доступных рекомендаций. Ежедневно мы агрегируем миллионы новых вакансий. Набор рекомендуемых вакансий постоянно изменяется.
  • Новые пользователи. Каждый день миллионы новых пользователей приходят на наш сайт, чтобы подыскать себе работу. Нам необходима возможность генерировать рекомендации на основе очень ограниченного объема данных об активности пользователей.
  • Ограниченный жизненный цикл вакансий. Средняя длительность жизненного цикла вакансии на Indeed составляет 30 дней. Актуальность имеет большое значение, потому что, чем старше вакансия, тем вероятнее, что она уже занята.
  • Ограниченное предложение. Одна вакансия обычно подразумевает, что требуется один человек. В этом заключается существенное отличие от книг или фильмов, которые можно рекомендовать большому количеству пользователей одновременно. Если мы будем слишком интенсивно рекомендовать некоторую вакансию, работодатель может быть просто засыпан тысячами заявок.

Подходы к реализации рекомендательных алгоритмов

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

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

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

Коллаборативная фильтрация в Mahout

Для создания нашей рекомендательной системы мы выбрали подход на основе поведения, поскольку хотели использовать преимущество большого потока посетителей и кликов на нашем сайте. Первая версия системы была основана на алгоритме коллаборативной фильтрации (collaborative filtering), реализованном в Apache Mahout. Мы подавали поток кликов в конструктор (builder), выполняющийся в кластере Hadoop и формирующий отображение (map) пользователей на вакансии, которые им следует рекомендовать. Специально разработанная служба обеспечивала доступ к этой модели во время выполнения, а клиентские приложения обращались к ней, чтобы генерировать рекомендации.

Первые результаты и трудности

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

  • Рабочий цикл конструктора длился слишком долго и занимал около 18 часов. Следует учесть, что это было в 2013 году, когда наш поток кликов был в три раза меньше, чем сейчас.
  • Мы могли запускать конструктор лишь один раз в день, а это означало, что новые пользовали, приходящие в течение дня, не получали рекомендации до следующего дня.
  • Миллионы новых вакансий не были доступны в качестве рекомендаций до следующего выполнения конструктора.
  • Результирующая модель имела размер около 50 ГБ. Соответственно, требовалось несколько часов, чтобы скопировать ее через Интернет из дата-центра, где она была создана, в наши дата-центры, расположенные по всему миру.
  • Реализация Mahout позволяет настраивать несколько параметров алгоритма, например, пороги сходства, но нам необходима была большая гибкость и возможность применять другие алгоритмы.

Рекомендательная система на основе MinHash

В первую очередь, мы занялись решением самой серьезной проблемы, заключающейся в том, что конструктор был слишком медленным. Мы выяснили, что в Mahout сходство пользователей вычисляется путем сравнения каждого пользователя со всеми остальными пользователями за время n2. Только лишь для трафика из США (50 миллионов уникальных посетителей) необходимо выполнить 15 * 1015 сравнений, что требует больших вычислительных ресурсов. Кроме того, процесс вычислений является по своей природе пакетным. То есть при добавлении нового пользователя или нового клика необходимо заново повторить все вычисления.

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

Наш ведущий разработчик Дейв Гриффит (Dave Griffith) обнаружил алгоритм MinHash (min-wise independent permutations) в публикации сотрудников Google News. MinHash позволяет приближенно вычислить коэффициент сходства Жаккара (Jaccard similarity coefficient). Применяя эту меру к вакансиям, на которых кликнули два пользователя, мы видим, что чем больше одинаковых вакансий заинтересовало этих двух пользователей, тем больше их сходство по Жаккару. Вычисление коэффициентов Жаккара для всех пар пользователей требует время O(n2), а MinHash позволяет сократить его до O(n).

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

Алгоритм MinHash подробно объясняется в рамках курса от Coursera «Mining Massive Datasets» («Интеллектуальный анализ больших наборов данных»). Авторами курса выступили профессора Стэнфорда: Лесковек (Leskovec), Раджараман (Rajaraman) и Ульман (Ullman). В 3-й главе (PDF) их одноименной книги приводится математическое доказательство MinHash.

Наша реализация MinHash включает в себя три этапа:

  1. Вычисление сигнатур / формирование кластеров.
    Для каждого пользователя вычисляется h значений, соответствующих хеш-функциям из семейства H (см. псевдокод ниже):

    H = {H1, H2, ..H20}
    for user in Users
    for hash in H
            minhash[hash] = min{x∈Itemsi | hash(x)}

    Где H – это семейство, состоящее из h хеш-функций. В конце этого этапа каждый пользователь представлен сигнатурой, которая также называется кластером и содержит h значений.

  2. Расширение кластеров.
    Пользователи, имеющие одинаковую сигнатуру, считаются похожими, соответственно, вакансии, которыми интересовался каждый из них, перекрестно рекомендуются всем остальным. Таким образом мы расширяем каждый кластер, объединяя все вакансии от всех пользователей в этом кластере.
  3. Генерация рекомендаций.
    Чтобы сгенерировать рекомендации для данного пользователя, мы объединяем все вакансии из h кластеров, к которым принадлежит данный пользователь. Затем мы исключаем все вакансии, уже просмотренные данным пользователем, чтобы получить итоговый набор рекомендуемых вакансий.

Генерация рекомендаций для новых пользователей

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

После перехода на MinHash, мы создали гибридную рекомендательную модель, состоящую из офлайн-компонента, который ежедневно формируется в Hadoop, и онлайн-компонента, реализованного на основе memcache и содержащего клики за текущий день. Два компонента модели используются совместно для вычисления итогового набора рекомендаций для каждого пользователя. После внедрения описанной модели, рекомендации стали намного более динамичными, поскольку они постоянно обновляются, в соответствии с тем, какие вакансии просматривают пользователи.

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

Влияние инфраструктуры

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

Даже после такого сегментирования, модели для некоторых регионов по-прежнему были слишком большими, и на их передачу в удаленные дата-центры требовалось несколько часов. Для решения этой проблемы, мы решили отправлять данные постепенно, а не один раз в день. Чтобы реализовать данную концепцию, мы использовали журналы опережающей записи (write-ahead log) и деревья слияния с журнальной структурой (log-structured merge-tree). Этот подход уже доказал свою эффективность в других наших крупномасштабных приложениях, например, при обработке документов.

Чтобы не создавать большой файл модели, мы модифицировали конструктор таким образом, чтобы он записывал небольшие фрагменты данных. Каждый фрагмент файла записывается посредством последовательного доступа (sequential I/O) и оптимизируется для быстрой репликации. Затем службы, работающие в удаленных дата-центрах, объединяют эти фрагменты посредством дерева слияния с журнальной структурой.

Описанные изменения в инфраструктуре позволили пользователям получать новые рекомендации на несколько часов быстрее. В рамках тестирования этой модификации мы наблюдали 30% рост количества кликов, обеспеченный тем, что пользователи получали актуальные рекомендации быстрее.

Этот опыт продемонстрировал, что оптимизация инфраструктуры оказывает не менее существенное влияние на итоговый результат, чем оптимизация алгоритмов.

Повышение скорости A/B-тестирования

Создание системы для вычисления и обновления рекомендаций было только началом. Для расширения охвата и повышения качества рекомендаций, необходимо было повысить скорость A/B-тестирования. Логика многих решений относительно финального набора рекомендаций была реализована в конструкторе. Эти решения включали следующие: пороги сходства, количество вакансий, рекомендуемых данному пользователю, и различные методы фильтрации рекомендаций низкого качества. Мы хотели оптимизировать и точно настроить каждый параметр вычисления рекомендаций, но для этого пришлось бы заново создавать и отсылать модель в удаленные дата-центры после каждого изменения параметров. Тестирование наших идей по оптимизации потребовало бы большого количества операций с памятью и диском на серверах, обслуживающих запросы пользователей.

Чтобы повысить скорость A/B-тестирования, вместо конечных результатов, мы стали отправлять в дата-центры отдельные компоненты, участвующие в вычислении рекомендаций. Мы изменили службы, работающие в удаленных дата-центрах таким образом, чтобы они сами выполняли итоговые вычисления, объединяя полученные компоненты, а не просто читали модель и возвращали результат. Важнейшими компонентами, участвующими в вычислении рекомендаций, являются: принадлежность пользователя к кластерам, соответствие кластеров и вакансий, а также черный список для каждого пользователя, содержащий вакансии, которые не следует рекомендовать данному пользователю. После описанных модификаций конструктор формировал необходимые компоненты, а службы объединяли их в момент запроса, чтобы вычислить итоговый список рекомендаций.

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

В результате, нам удалось повысить скорость A/B-тестирования на несколько порядков. Благодаря этому мы за короткое время смогли протестировать и внедрить несколько идей, расширивших охват и повысивших качество рекомендаций. До этого в среднем мы могли позволить себе тестировать одно улучшение модели каждый квартал, в виду чрезмерных накладных расходов на реализацию экспериментов.

Практика показала, что при проектировании крупномасштабных систем машинного обучения очень важно учитывать скорость A/B-тестирования. Чем быстрее мы можем предоставлять наши идеи на оценку пользователям, тем быстрее мы можем развивать сервис в целом.

В этой статье мы кратко рассмотрели алгоритмические и архитектурные изменения, которые были внедрены нами в процессе создания нашей рекомендательной системы. Мы создавали нашу систему постепенно: начали с минимально жизнеспособного продукта, многому научились на этой стадии, а затем последовательно оптимизировали его. В результате примененных подходов, вклад рекомендательной системы в количество кликов вырос с 3% в начале 2014 года до 14% в настоящее время.

Наша команда не останавливается на достигнутом и продолжает совершенствовать рекомендательную систему. Мы создаем модели с помощью Apache Spark, применяем ансамбли моделей, а также совершенствуем методы борьбы со смещением по популярности (popularity bias).

Автор публикации

не в сети 13 часов

DataReview

Комментарии: 16Публикации: 954Регистрация: 05-06-2014

Вам также может понравиться

Добавить комментарий

Ваш e-mail не будет опубликован.

закрыть

Поделиться

Отправить на почту
закрыть

Вход

закрыть

Регистрация

+ =
Авторизация
*
*

Login form protected by Login LockDown.


Регистрация
*
*
*
*
Генерация пароля