- PVSM.RU - https://www.pvsm.ru -
Не так давно мы проводили Яндекс.Блиц [1] – соревнование по алгоритмическому программированию. Соревнование удалось: в финал пробилось более трёхсот участников, из которых двое сумели решить все предложенные задачи! Двадцать финалистов приехали в офис Яндекса, познакомились с руководителями различных сервисов и больше узнали об устройстве современных поисковых систем.
Однако в Яндексе разработчики решают самые разные задачи: от разработки высоконагруженных систем обработки данных до построения сложных моделей релевантности и смешивания поисковых источников. Поэтому нам показалось вполне логичным продолжить цикл соревнований от Яндекса соревнованием по машинному обучению и анализу данных.
Так же, как и в прошлый раз [2], мы заранее рассказываем на Хабре о том, какие задачи могут встретиться в контесте, и как их можно было бы решать, чтобы у потенциальных участников было представление о том, что их ждёт.
Квалификацию ML-блица [3] можно будет пройти с 11 по 17 июня, а 23 июня состоится финал. Итоги соревнования будут подведены 25 июня. Для участия необходимо вовремя зарегистрироваться [4]!
Кластеризация – достаточно часто встречающийся метод обработки данных в Яндексе. Например, Яндекс.Новости используют методы кластеризации, чтобы собирать новостные сообщения в сюжеты, а Поиск кластеризует пользовательские запросы, чтобы понимать, какие задачи решают пользователи и какие из них являются более частотными.
Часто задача кластеризации формулируется в следующих терминах: дан набор объектов , для некоторых пар объектов известно значение метрики близости: . Необходимо построить разбиение множества на кластера, то есть найти такие непересекающиеся подмножества , что их объединение совпадает с и при этом является в некотором смысле оптимальным.
В первой задаче мы предлагаем вам решить задачу кластеризации для достаточно простого случая. Имеется набор точек в -мерном евклидовом пространстве. Известно, что этот набор точек можно разбить на два подмножества, и , таких, что расстояние между любыми двумя точками из разных подмножеств превосходит некоторую величину . Также известно, что разбиение с указанным свойством гарантированно существует и при этом является единственно возможным. Требуется его найти.
Построим следующий алгоритм кластеризации. Изначально все точки являются отдельными кластерами. Затем, если существует два кластера и , таких, что есть хотя бы одна пара точек из них с расстоянием менее , эти два кластера объединяются в один:
Эта операция повторяется до тех пор, пока существует хотя бы одна пара кластеров с указанным свойством. Ясно, что после окончания алгоритма останется только два кластера – в противном случае было бы возможно разбить множество точек более чем одним способом с соблюдением условий задачи.
Реализовать такой алгоритм можно, используя структуры данных лес непересекающихся множеств [6] и KD-дерево [7], либо, например, VP-дерево [8]. На первом этапе построим дерево поиска (KD- или VP-дерево) из всех точек исходного множества; кроме того, инициализируем лес непересекающихся множеств размера . Затем для каждой точки из осуществим следующий алгоритм:
Для решения задачи подходят и некоторые готовые реализации алгоритмов кластеризации. Например, подойдёт алгоритм DBSCAN [9] из библиотеки scikit-learn для python.
Стоит заметить, что при решении этой задачи можно обойтись без леса непересекающихся множеств. Можно использовать, например, обход неявного графа в глубину: на каждом шаге определять вершины, соседние с текущей, и рекурсивно запускать обход из них.
Яндекс.Новости – сервис, который агрегирует сотни тысяч новостных текстов в сутки, обрабатывает их, в том числе извлекая именованные сущности. Бывает так, что в сюжет попадает нерелевантное сообщение, либо в тексте конкретного сообщения по ошибке оказывается не связанный с его основной темой отрывок. В таком случае к сюжету может привязаться ошибочная именованная сущность (например, персона), и пользователь будет воспринимать это как ошибку. При правильном срабатывании мы можем добавить в сюжет о свадьбе принца Гарри и Меган Маркл, например, ссылку с информацией о невесте:
В этой задаче вам потребуется определить, какой из объектов является лишним. Мы взяли сто тысяч новостных сообщений, извлекли из них все именованные сущности и перенумеровали их, построив некоторое множество чисел . Таким образом, каждый текст – это некоторое множество чисел. Если – множество всех текстов, то:
Затем мы добавили в каждый текст один случайный объект. Ясно, что случайный объект с большой вероятностью не имеет никакого отношения к тексту новости. Вашей задачей является определить для каждой новости, какой из объектов является лишним.
Это пример задачи, в которой невозможно дать стопроцентно точный ответ. В ней важно получить как можно большее значение некоторой метрики качества – в данном случае, доли правильно угаданных лишних объектов. Поскольку контест ограничен по времени, разумно при решении такой задачи начать с простого метода, лёгкого в реализации и при этом гарантирующего получение некоторого результата.
В данном случае можно использовать, например, следующую простую эвристику. Если два объекта в некотором смысле семантически связаны (например, объекты и определённо связаны), то они будут иногда встречаться в одних и тех же текстах. С другой стороны, объектов чрезвычайно много, поэтому случайно выбранная пара вряд ли будет часто встречаться вместе.
Поэтому рассчитаем, например, функцию условной вероятности встречаемости объектов:
Таким образом, – это вероятность встретить в тексте объект при условии, что в тексте встречается объект . В практических целях эту функцию стоит сгладить – например, сделать так, чтобы она никогда не принимала значений, меньших некоторого небольшого числа, например, .
Если использовать наивное предположение о независимости условных вероятностей, то с помощью формулы Байеса можно для каждого объекта определить вероятность его появления при условии наличия в тексте всех остальных объектов:
Отсюда следует, что в качестве «лишнего» объекта можно взять
Таким образом можно получить простое решение, которое с некоторым качеством будет справляться с поставленной задачей.
Затем можно построить более сложное решение с применением настоящего машинного обучения. Факторами будут, например, оценки сродни той, что получена выше. Чтобы сформулировать задачу бинарной классификации, потребуется выбирать «положительные» и «отрицательные» пары текстов и объектов. В качестве положительных можно использовать пары, реально наблюдаемые в данных, а в качестве отрицательных можно использовать пары, в которых объект выбирается случайным образом из множества всех объектов . На такой выборке можно обучить, например, 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
Нажмите здесь для печати.