1. Вступление
В самых различных проектах разработчику приходится сталкиваться с задачами ранжирования. Список подобных задач весьма обширен: от банальной сортировки новостей по дате публикации до сложных рейтингов на основе поведенческих факторов.
Эта заметка представляет собой личное мнение автора по поводу применения некоторых универсальных алгоритмов в задачах ранжирования. Цель подсказать разработчику возможные пути решения соответствующих задач и уберечь от наиболее типичных ошибок.
Пара слов про управление ожиданиями. Это не учебный курс и не инструкция, а рассказ о возможных подходах. Предпочтение отдавалось наиболее универсальным из них. Обращаю ваше внимание, что всё изложенное далее публикуется на правах личного мнения.
2. Первый взгляд
Скажите, пожалуйста, а сколько всего может быть способов перестановки результатов ранжирования? Для массивов из двух элементов интуиция легко поможет найти правильный ответ: [Первый, Второй] и [Второй, Первый]. А для массива из 30 элементов? Применим формулу комбинаторики: n! (факториал мощности множества). Для множества из 30 элементов количество возможных перестановок будет равно 265252859812191058636308480000000. Даже для рейтинга ТОП-10 есть 3628800 вариантов перестановки.
Представим, что порядок элементов задаётся случайно. Какая вероятность появления нужного элемента на первом месте? Пусть всего 10 элементов. Нас интересует один конкретный элемент. Порядок всех остальных уже не имеет значения. По сути, это аналогично случайному выбору из мешка синего шарика, где 9 красных и 1 синий шарик. Тогда вероятность составляет 1/10. Другими словами, при многократном повторении эксперимента примерно в 10% случаев мы увидим этот элемент на первом месте.
Кстати, а с какой вероятностью один и тот же элемент окажется на первом месте два раза подряд? Запуски алгоритмов мы считаем независимыми событиями, так как один запуск никак не влияет на другой. Следовательно, это произведение вероятностей независимых событий: 1/10 * 1/10. Это касается и всех последующих попыток, но тут красивее возводить вероятность в соответствующую степень.
Я дважды упоминал про случайную сортировку. А вдруг там другой алгоритм ранжирования? Можно ли вычислить формулу ранжирования, если код закрыт? Оказывается, что при определённых условиях это возможно. Нам потребуется многократно проводить эксперимент: передавать аргументы функции (факторы ранжирования) и фиксировать её ответ. Предлагаю посмотреть на пример с линейной регрессией.
3. Открываем чёрный ящик
Пусть существует неизвестный алгоритм ранжирования. На вход он принимает количество просмотров документа, а возвращает некий score, по которому и происходит сортировка. При этом, у вас нет доступа к исходному коду всё работает по принципу чёрного ящика. Необходимо вычислить формулу ранжирования. Проведём эксперимент: многократно передадим данные и запишем ответ.
Для начала есть смысл взглянуть на сами данные. Если вы отобразите массив данных с несколькими миллионами объектов, то человек не сможет всё это осмысленно прочитать. Придётся придумывать способ понятно описать его. Частая ошибка не изучив набор данных использовать среднее значение или медиану. Подобный подход чреват серьёзным искажением реальной картины.
Попробуем преобразовать большой массив в специальную структуру данных, которая содержит описательную статистику (среднеквадратическое отклонение, максимум, минимум, среднее, медиана, нижний и верхний квартиль). Но не будем торопиться с таким решением. Есть даже известный набор данных (квартет Энскомба), который хорошо иллюстрирует эту проблему. Очень советую про него прочитать.
В такой ситуации на помощь разработчику приходит гистограмма распределения. Она является удобным способом наглядно отобразить массив из гигантского количества измерений случайной величины. Суть очень простая: разбиваем массив на интервалы и отображаем количество элементов в каждом интервале. Визуально это выглядит следующим образом:
В итоге мы видим распределение случайной величины. Регулируя число интервалов можно добиться адекватного представления. Теперь нам нужен способ увидеть взаимосвязь этой случайной величины с другой. Отобразим наблюдения в виде точек на плоскости, где по оси X будет score, а по Y наш единственный предиктор (признак). И вот перед вами появляется график:
На нём показано, что обе переменных сильно коррелируют между собой, следовательно, делаем предположение о линейной зависимости (score=a+bx). Не все точки выстроились на одну линию, что говорит нам о небольшом влиянии неизвестного фактора. Это я специально сделал, для красоты.
Подобрать коэффициенты в нашем случае труда не составит. Так, например, класс LinearRegression (из scikit-learn) после обучения (fit) позволяет получить смещение (intercept) и массив коэффициентов (coef). Подставляем значения в формулу и проверяем результат с помощью метрик mean_absolute_error и median_absolute_error. Собственно, это и есть решение нашей задачи. В случае множества признаков суть не меняется: под капотом всё устроено аналогичным образом (смещение + скалярное произведение вектора признаков и соответствующих коэффициентов).
Предупреждение о подводных камнях: обязательно внимательно изучайте данные, а при необходимости выполняйте подготовку, включая масштабирование и преобразование категориальных признаков (one-hot). Кроме этого, увеличение количества признаков сильно затрудняет визуальный анализ даже специальные алгоритмы уменьшения размерности (PCA, Isomap, TSNE) не всегда помогут отобразить информацию в удобном для человека виде.
4. Простая формула ранжирования
А что мы будем ранжировать? Список задач весьма обширный: рекламные блоки, рейтинги товаров, результаты анализа общественного мнения, интересные новости, анкеты на сайтах, группы из социальных сетей, баннеры, рекомендации, результаты парсинга сайтов, блоки персонализации. И это далеко не полный список. Получается, что под каждый частный случай нужно придумывать свою формулу ранжирования?
Или придумать формулу только для определённого типа задач? Уверен, что вы сталкивались с полнотекстовом поиском в реляционных базах данных (PostgreSQL, MySQL, SQLite) или в специальных системах (Elasticsearch, Sphinx, Solr). Например, в Elasticsearch формула ранжирования видна в режиме explain, а явно задать её в запросе можно через script_score. Не исключено, что вы сами пробовали написать BM25 (TF-IDF-подобный алгоритм).
Даже когда вы сортируете новости по дате публикации это тоже можно назвать экспертной формулой ранжирования. Но сейчас интереснее попробовать универсальный алгоритм, который может быть применён в большом количестве разнообразных задач.
Мы уже говорили про линейную регрессию. Действительно, это вполне универсальный алгоритм. Несмотря на всю простоту его применяют в серьёзных проектах. Благодаря своей скорости работы это замечательное решение в тех задачах, где критически важна производительность. Линейные алгоритмы могут быть частью иерархических формул ранжирования ненужные объекты отбрасываются простыми моделями, чтобы не расходовать драгоценные ресурсы действительно сложных алгоритмов.
Ярким примером фильтра выступает логистическая регрессия. Это быстрая и лёгкая в реализации модель классификации. Под капотом это обычная линейная регрессия, только результат её работы передают в сигмоиду. Далее выполняется проверка если результат больше 0.5, то класс 1, иначе класс 0. По сути, это формула гиперплоскости, разделяющей классы. На вид это простые алгоритмы, но их применяют даже в сложных задачах классификации текстов. Разумеется, тексты предварительно подготавливаются и преобразуются в вектор признаков (примеры алгоритмов: CountVectorizer, TfidfVectorizer, Word2Vec).
Замечание: в коммерческих проектах важно учитывать соотношение затраченных ресурсов и полученной выгоды. Самые минимальные увеличения могут затребовать такие ресурсы, что они просто не окупятся. Либо проблема может заключаться в сроках: нужно сегодня к вечеру получить хотя бы слабую модель, а завтра уже нет смысла даже в самой идеальной.
5. Более сложное ранжирование
Сложными задачами ранжирования будем называть такие, которые нельзя решить написанием хорошего запроса на SQL или доработкой компонента для подсчёта рейтинга. Другими словами, нет конкретной формулы или алгоритма. Самый банальный пример: как бы разработчик не старался, но простая функция не сможет классифицировать фотографии наравне с ResNet50 из Keras. Даже для создания хорошего алгоритма учёта поведенческих факторов может потребоваться использовать K-means для кластеризации контента и метрик поведения пользователей.
По этой причине разработчику пригодятся знания алгоритмов машинного обучения. В современных проектах это нужно всё чаще. Обратите внимание, что мы сейчас не говорим про тонкости настройки или проверки алгоритмов машинного обучения. Это явно выходит за пределы моей заметки. Речь о том, что алгоритмы машинного обучения сами могут создать формулу ранжирования, при условии, что вы располагаете подходящим размеченном набором данных. Теперь задумаемся на тем, как задействовать сильную модель в своём проекте.
Идея состоит в том, чтобы получить возможность быстро добавлять готовые модели в любой проект. Без подключения дополнительных зависимостей. И проекты могут быть на разных языках программирования. Или это вообще специальные устройства. Когда мы говорили про линейные модели, то вы могли заметить, что такие алгоритмы очень легко добавить в любой проект. Достаточно просто скопировать массив с коэффициентами, который будет использован в соответствующем методе. А вот с комитетами решающих деревьев не всё так просто. В качестве конкретных реализаций будут выступать Catboost и Random forest.
Хочу вам предложить одно из решений, которое мне давилось делать для переноса модели на специальные устройства. Идея следующая: получим из обученной и проверенной модели её деревья, а в циклах (по шаблонам) сформируем исходный код. Собственно, код генерируется по шаблонам (получается простыня условий) и добавляется в проект в виде отдельного файла на нужном языке программирования.
Так, например, в случае Random forest мы получим много относительно глубоких деревьев. Каждое дерево будет получать на вход набор данных (отдельные деревья могут работать только со своими признаками) и возвращать тот результат, который предскажет его лист (терминальный узел). В итоге будет массив предсказаний, где каждый элемент является ответом дерева. В задачах регрессии следует вычислить среднее значение, а для классификации тот класс, за который проголосовало большинство деревьев (либо распределение голосов, которое можно рассматривать как вероятность принадлежности к классу).
Повторюсь, этот подход использовался для специальных устройств. Однако, в ряде случаев так можно делать для любых проектов не будет лишних зависимостей и производительность может быть выше, а так же есть возможность самому более тонко настраивать работу деревьев. Если с Random forest такое упражнение доводилось делать для реальных проектов, то с Catboost я просто побаловался в субботу на своём домашнем компьютере.
У ранее упомянутого Catboost есть возможность сохранения модели в формате JSON. В массиве oblivious_trees будут решающие деревья (обычно пни зависит от гиперпараметров), которые содержат индексы признаков (split_index) и границу разделения (border). Схема экспорта модели аналогичная, только специфика работы деревьев отличается, а именно, они друг за другом последовательно снижают энтропию.
6. Выводы
Лучше использовать принцип KISS, однако, если задача требует сложного решения, то можно вспомнить про предложенные подходы. При этом, всегда следует осознавать смысл (финальную цель) и учитывать соотношение затрат, рисков и ожидаемой пользы.
7. Послесловие
Очень надеюсь, что некоторые изложенные мной мысли подскажут вам способы решения задач в ваших проектах. Повторюсь, что заметка отражает моё личное мнение и может содержать неточности банальный человеческий фактор, особенно при написании текстов в выходные дни.
