Хабрахабр

Яндекс.Блиц: машинное обучение

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

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

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

Итоги соревнования будут подведены 25 июня. Квалификацию ML-блица можно будет пройти с 11 по 17 июня, а 23 июня состоится финал. Для участия необходимо вовремя зарегистрироваться!

image

Задача #1. Кластеризация

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

Необходимо построить разбиение множества $X$ на кластера, то есть найти такие непересекающиеся подмножества $X_1, X_2, ..., X_k$, что их объединение совпадает с $X$ и при этом является в некотором смысле оптимальным. Часто задача кластеризации формулируется в следующих терминах: дан набор объектов $X$, для некоторых пар объектов известно значение метрики близости: $f : X^2 \rightarrow [0, 1]$.

Имеется набор точек $X$ в $n$-мерном евклидовом пространстве. В первой задаче мы предлагаем вам решить задачу кластеризации для достаточно простого случая. Также известно, что разбиение с указанным свойством гарантированно существует и при этом является единственно возможным. Известно, что этот набор точек можно разбить на два подмножества, $X_1$ и $X_2$, таких, что расстояние между любыми двумя точками из разных подмножеств превосходит некоторую величину $b$. Требуется его найти.

Решение

Изначально все точки $X$ являются отдельными кластерами. Построим следующий алгоритм кластеризации. Затем, если существует два кластера $C_1 \subset X$ и $C_2 \subset X$, таких, что есть хотя бы одна пара точек из них с расстоянием менее $b$, эти два кластера объединяются в один:

$\exists x_1 \in C_1, \exists x_2 \in C_2: \| x_1, x_2 \|_2 < b$

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

На первом этапе построим дерево поиска (KD- или VP-дерево) из всех точек исходного множества; кроме того, инициализируем лес непересекающихся множеств размера $|X|$. Реализовать такой алгоритм можно, используя структуры данных лес непересекающихся множеств и KD-дерево, либо, например, VP-дерево. Затем для каждой точки из $x \in X$ осуществим следующий алгоритм:

  1. Определим при помощи дерева поиска все точки, лежащие на расстоянии не более чем $b$ от $x$.
  2. Для каждой найденной точки $x'$ осуществим операцию $Unite$ в лесе непересекающихся множеств для пары индексов, соответствующих объектам $x$ и $x'$.
    В конце работы этого алгоритма лес непересекающихся множеств будет содержать разбиение исходного множества на два кластера.

Например, подойдёт алгоритм DBSCAN из библиотеки scikit-learn для python. Для решения задачи подходят и некоторые готовые реализации алгоритмов кластеризации.

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

Задача #2. Определение лишних объектов

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

Мы взяли сто тысяч новостных сообщений, извлекли из них все именованные сущности и перенумеровали их, построив некоторое множество чисел $ N \subset \mathbb $. В этой задаче вам потребуется определить, какой из объектов является лишним. Если $T$ – множество всех текстов, то: Таким образом, каждый текст – это некоторое множество чисел.

$T = \Big\{ t_1, ..., t_n \Big\}, t_i \subset N$

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

Решение

В ней важно получить как можно большее значение некоторой метрики качества – в данном случае, доли правильно угаданных лишних объектов. Это пример задачи, в которой невозможно дать стопроцентно точный ответ. Поскольку контест ограничен по времени, разумно при решении такой задачи начать с простого метода, лёгкого в реализации и при этом гарантирующего получение некоторого результата.

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

Поэтому рассчитаем, например, функцию условной вероятности встречаемости объектов:

$P(b | a) = \frac{\sum_{i=1}^n{(b \in t_i) \land (a \in t_i)}}{\sum_{i=1}^n{(a \in t_i)}}$

В практических целях эту функцию стоит сгладить – например, сделать так, чтобы она никогда не принимала значений, меньших некоторого небольшого числа, например, $10^{-5}$. Таким образом, $ P(b | a) $ – это вероятность встретить в тексте объект $b$ при условии, что в тексте встречается объект $a$.

Если использовать наивное предположение о независимости условных вероятностей, то с помощью формулы Байеса можно для каждого объекта определить вероятность его появления при условии наличия в тексте всех остальных объектов:

$P(a | t_i) = \frac{P(a)P(t_i | a)}{P(t_i)} = \frac{P(a)}{P(t_i)}\prod_{b\in t_i}P(b | a)$

Отсюда следует, что в качестве «лишнего» объекта можно взять

$answer(t_i) = \arg\underset{a\in t_i}{\min}(\log{P(a)} + \sum_{b\in t_i}\log{P(b | a)})$

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

Факторами будут, например, оценки сродни той, что получена выше. Затем можно построить более сложное решение с применением настоящего машинного обучения. В качестве положительных можно использовать пары, реально наблюдаемые в данных, а в качестве отрицательных можно использовать пары, в которых объект выбирается случайным образом из множества всех объектов $N$. Чтобы сформулировать задачу бинарной классификации, потребуется выбирать «положительные» и «отрицательные» пары текстов и объектов. На такой выборке можно обучить, например, CatBoost.

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

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

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

Теги
Показать больше

Похожие статьи

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть