28.05.2018 10:29
ashagraev 0 6200 Источник

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


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


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


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


image


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


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


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


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


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

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


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


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


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



В этой задаче вам потребуется определить, какой из объектов является лишним. Мы взяли сто тысяч новостных сообщений, извлекли из них все именованные сущности и перенумеровали их, построив некоторое множество чисел $ N \subset \mathbb {N}$. Таким образом, каждый текст – это некоторое множество чисел. Если $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)}}$


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


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


$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.


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



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


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

Комментарии (0)