- PVSM.RU - https://www.pvsm.ru -

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

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

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

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

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

image [5]

Задача #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$

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

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

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

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

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

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

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

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

В этой задаче вам потребуется определить, какой из объектов является лишним. Мы взяли сто тысяч новостных сообщений, извлекли из них все именованные сущности и перенумеровали их, построив некоторое множество чисел $ 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_{bin t_i}P(b | a)$

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

$answer(t_i)=argunderset{ain t_i}{min}(log{P(a)} + sum_{bin t_i}log{P(b | a)})$

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

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

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


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

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

Автор: ashagraev

Источник [12]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/matematika/281174

Ссылки в тексте:

[1] Яндекс.Блиц: https://yandex.ru/promo/jobs/blitz/newhire

[2] прошлый раз: https://habr.com/company/yandex/blog/337690/

[3] ML-блица: https://yandex.ru/promo/jobs/blitz/2018/ml/index

[4] зарегистрироваться: https://yandex.ru/promo/jobs/blitz/2018/ml/index#register

[5] Image: https://habr.com/company/yandex/blog/359435/

[6] лес непересекающихся множеств: https://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D1%81_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D0%B5%D0%BA%D0%B0%D1%8E%D1%89%D0%B8%D1%85%D1%81%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2

[7] KD-дерево: https://ru.wikipedia.org/wiki/K-%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

[8] VP-дерево: https://ru.wikipedia.org/wiki/VP-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

[9] DBSCAN: http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html

[10] CatBoost: https://tech.yandex.ru/CatBoost/

[11] Яндекс.Контест: https://contest.yandex.ru/

[12] Источник: https://habr.com/post/359435/?utm_campaign=359435