ML-Блиц: разбор задач первого квалификационного раунда

в 11:00, , рубрики: Блог компании Яндекс, Занимательные задачки, конкурсы, конкурсы разработчиков, математика, машинное обучение, Спортивное программирование, Яндекс.Блиц

23 июня 2018 года состоялся финал ML-Блица, конкурса по машинному обучению, организованного Яндексом. Ранее мы анонсировали его на Хабре и рассказывали, какие примерно задачи могут встретиться на реальном соревновании.

Теперь мы хотим поделиться с вами разборами задач одного из квалификационных раундов — самого первого. Двое участников сумели решить все задачи этого соревнования; 57 участников решили хотя бы одну задачу, а 110 совершили хотя бы по одной попытке сдать задание.

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

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

Все мои решения доступны на GitHub

image

Задача A. Решающий пень

Задача
Решение на python
Решение на C++

Решающий пень — одна из простейших решающих функций в машинном обучении. Это кусочно-постоянная функция, определяемая следующим образом:

$ f(x)=left{ begin{array}{ll} a, & quad x lt c \ b, & quad x ge c end{array} right. $

В данной задаче необходимо было построить оптимальный решающий пень по обучающей выборке. То есть, по данным парам чисел $(x_1, y_1), ldots, (x_n, y_n)$, требовалось определить оптимальные значения параметров решающего пня для оптимизации значения квадратического функционала потерь

$ Q(f, x, y)=sum_{i=1}^{n} (f(x_i) - y_i)^2 $

В качестве ответа необходимо было вывести оптимальные значения $a, b, c$.

Решение

Итак, нам необходимо построить кусочно-гладкую аппроксимацию известной функции. Если параметр $c$ известен, то найти параметры $a$ и $b$ достаточно просто. Можно записать решения математически как решения соответствующих задач оптимизации. Параметр $a$ — это величина предсказаний решающего пня на тех объектах $(x_i,y_i)$ обучающей выборки, для которых $x_i < c$. Аналогично, $b$ — это величина предсказаний на тех объектах $(x_i,y_i)$ обучающей выборки, для которых $x_i ge c$.

Введём обозначения для соответствующих подмножеств обучающей выборки: $L(c)$ — это подмножество объектов слева от точки $c$, $R(c)$ — подмножество объектов справа от точки $c$.

$L(c)={(x_i,y_i) | x_i<c}$

$R(c)={(x_i,y_i) | x_i ge c}$

Тогда оптимальное значение $a$ будет равняться среднему арифметическому ответов в множестве $L(c)$, а оптимальное значение $b$ — соответственно, среднему арифметическому ответов в множестве $R(c)$.

Обосновать это можно следующим образом

$ a=arg min_{t in mathbb{R}}{sum_{(x_i,y_i) in L(c)} (t - y_i)^2} $

$ b=arg min_{t in mathbb{R}}{sum_{(x_i,y_i) in R(c)} (t - y_i)^2} $

Хорошо известно, что ответом в таких задачах оптимизации является среднее арифметическое:

$ a=frac{sum_{(x_i,y_i) in L(c)} y_i}{|L(c)|} $

$ b=frac{sum_{(x_i,y_i) in R(c)} y_i}{|L(c)|} $

Это достаточно легко доказать. Возьмём частную производную функционала потерь по величине предсказания:

$frac{partial}{partial t}sum_{y in Y}{(t - y)^2}=2 cdot sum_{y in Y}{(t - y)}=2 cdot |Y| cdot t - 2 cdot sum_{y in Y}{y} $

После приравнивания производной нулю, получим, что

$ t=frac{1}{|Y|} sum_{y in Y} y $

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

Итак, теперь ясно, как находить параметры $a$ и $b$ при известном параметре $c$. Осталось понять, как найти оптимальное значение параметра $c$.

Первое, что нужно заметить: параметр $c$ может принимать любые вещественные значения, но множество различных разбиений конечно. Обучающую выборку из $n$ объектов можно разбить не более чем $n + 1$ способами на "левую" и "правую" части. В действительности же таких разбиений может быть ещё меньше: например, для некоторых объектов значения признаков могут совпадать. Кроме того, для нас эквивалентны разбиения, в которых все объекты обучающей выборки оказываются в левой или в правой части.

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

$ (x_{i_1}, y_{i_1}), ldots (x_{i_n}, y_{i_n}) $

$ x_{i_1} le x_{i_2} le ldots le x_{i_n} $

Теперь ясно, что потенциально интересные значения параметра $c$ — это величины

$ frac{x_{i_1} + x_{i_2}}{2}, frac{x_{i_2} + x_{i_3}}{2}, ldots, frac{x_{i_{n-1}} + x_{i_n}}{2} $

Теперь ясно, что необходимо делать для получения решения. Нужно перебрать все потенциально интересные значения параметра $c$, для каждого из них определить соответствующие величины $a$ и $b$, а также значение функционала потерь. Затем нужно выбрать набор параметров, соответствующий минимальному из значений функционала потерь.

Остаётся только вопрос того, как сделать это решение эффективным. Непосредственная реализация описанного алгоритма приведёт к квадратичной сложности алгоритма, что недопустимо.

Чтобы сделать вычисления эффективными, вспомним, что для нахождения параметров $a$ и $b$ необходимо лишь вычислять средние величины по множеству. При добавлении очередного элемента в множество (или после удаления элемента из множества) величину среднего можно эффективно пересчитать за константное время, если хранить не само среднее, а отдельно сумму значений и отдельно их количество. Аналогично обстоит дело и с суммой квадратов отклонений. Для его вычисления, согласно известной формуле для вычисления дисперсии, можно отдельно хранить сумму величин и сумму квадратов величин. Кроме того, можно использовать любой онлайн-метод вычисления. Ранее я уже писал об этом на хабре.

Реализация

В реализации я буду использовать метод Уэлфорда, т.к. он нравится мне больше, чем вычисления по "стандартным" формулам. Кроме того, я не буду использовать numpy и какие-либо другие библиотеки, чтобы продемонстрировать, что для получения решения достаточно знания элементарных конструкций языка python.

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

class MeanCalculator:
    def __init__(self):
        self.Count = 0.
        self.Mean = 0.

    def Add(self, value, weight = 1.):
        self.Count += weight
        self.Mean += weight * (value - self.Mean) / self.Count

    def Remove(self, value, weight = 1.):
        self.Add(value, -weight)

class SumSquaredErrorsCalculator:
    def __init__(self):
        self.MeanCalculator = MeanCalculator()
        self.SSE = 0.

    def Add(self, value, weight = 1.):
        curDiff = value - self.MeanCalculator.Mean
        self.MeanCalculator.Add(value, weight)
        self.SSE += weight * curDiff * (value - self.MeanCalculator.Mean)

    def Remove(self, value, weight = 1.):
        self.Add(value, -weight)

Теперь нужен класс для хранения и обработки обучающей выборки. Для начала опишем его поля и метод ввода:

class Instances:
    def __init__(self):
        self.Items = []
        self.OverAllSSE = SumSquaredErrorsCalculator()

    def Read(self):
        fin = open('stump.in')

        for line in fin.readlines()[1:]:
            x, y = map(float, line.strip().split())
            self.Items.append([x, y])
            self.OverAllSSE.Add(y)
        self.Items.sort()

Одновременно с вводом данных мы сразу формируем структуру SumSquaredErrorsCalculator для всех объектов выборки. После загрузки всей выборки мы сортируем её по неубыванию значений признаков.

Теперь самое интересное: метод для нахождения оптимальных значений параметров.

Начнём с инициализации. В начальном состоянии все объекты находятся в правой подвыборке. Тогда параметр $a$ может быть равен чему угодно, параметр $b$ равен средней величине ответов во всей выборке, а параметр $c$ таков, чтобы все объекты выборки находились правее него.

Кроме того, инициализируем переменные left и right — они будут хранить статистики для левой и правой подвыборок, соответственно.

left = SumSquaredErrorsCalculator()
right = self.OverAllSSE

bestA = 0
bestB = right.MeanCalculator.Mean
bestC = self.Items[0][0]

bestQ = right.SSE

Теперь переходим к инкрементальному алгоритму. Будем обрабатывать элементы выборки по одному. Каждый элемент переносится в левое подмножество. Затем нужно проверить, что соответствующее разбиение действительно существует — то есть, значение признака отличается от значения признака следующего объекта.

for i in range(len(self.Items) - 1):
    item = self.Items[i]
    nextItem = self.Items[i + 1]

    left.Add(item[1])
    right.Remove(item[1])

    if item[0] == nextItem[0]:
        continue

    a = left.MeanCalculator.Mean
    b = right.MeanCalculator.Mean
    c = (item[0] + nextItem[0]) / 2

    q = left.SSE + right.SSE

    if q < bestQ:
        bestA = a
        bestB = b
        bestC = c
        bestQ = q

Теперь осталось только скомпоновать код для получения решения:

instances = Instances()
instances.Read()
a, b, c = instances.BestSplit()
print >> open('stump.out', 'w'), a, b, c

Замечу, что представленное решение на python действительно принимается системой, но оно подходит к верхней границе по времени решения: самые большие тесты требует порядка 800 миллисекунд на исполнение. Конечно, с использованием дополнительных библиотек можно добиться намного более впечатляющей производительности.

Поэтому я также реализовал предложенный алгоритм на C++. Это решение затратило в худшем случае 60 миллисекунд на один из тестов.

Задача B. Восстановление коэффициентов

Задача
Решение на python с использованием sklearn

Необходимо восстановить параметры $a$, $b$, $c$ функции $f$, имея набор известных пар $(x_1, f(x_1)),$ $ldots,$ $(x_n, f(x_n))$ и зная, что значения функции определяются по следующей формуле:

$ f(x)=Big((a + varepsilon_a)sin x + (b + varepsilon_b)ln xBig)^2 + (c + varepsilon_c)x^2 $

Решение

Раскроем скобки, проигнорировав случайные величины:

$ f(x)=a^2 cdot sin^2(x) + b^2 cdot ln^2(x) + 2abcdot sin(x) cdot ln(x) + c cdot x^2 $

Теперь мы получили задачу многомерной линейной регрессии без свободного коэффициента. Признаками в этой задаче являются величины $sin^2(x)$, $ln^2(x)$, $sin(x) cdot ln^2(x)$, $x^2$.

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

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

$ f(x)=t_1 cdot sin^2(x) + t_2 cdot ln^2(x) + t_3 cdot sin(x) cdot ln(x) + t_4 cdot x^2 $

После этого можно будет найти коэффициенты $a$, $b$, $c$:

$ a=sqrt(t_1), b=sqrt(t_2), c=t_4 $

Дополнительно стоит проверить, что $2cdot a cdot b approx t_3$

Реализация

Для начала следует считать данные и сформировать признаки:

x = []
y = []

for line in open('data.txt'):
    xx, yy = map(float, line.strip().split())
    x.append(xx)
    y.append(yy)

features = []
for xx in x:
    curFeatures = [
        math.sin(xx) ** 2,              # a^2
        math.log(xx) ** 2,              # b^2
        math.sin(xx) * math.log(xx),    # 2ab
        xx ** 2                         # c
    ]
    features.append(curFeatures)

Теперь необходимо решить задачу многомерной линейной регрессии. Существует большое количество способов сделать это — начиная от инструментов типа Weka и библиотечных функций sklearn, заканчивая моей собственной реализацией. Впрочем, в данном случае мне хотелось получить "замкнутое" решение: один скрипт, который полностью решает задачу. Поэтому я использовал sklearn.


linearModel = lm.LinearRegression()
linearModel.fit(features, y)

coeffs = linearModel.coef_

a = math.sqrt(coeffs[0])
b = math.sqrt(coeffs[1])
c = coeffs[3]

print "free coeff: ", linearModel.intercept_
print "2ab error: ", coeffs[2] - 2 * a * b
print a, b, c

В данном случае оказалось, что свободный коэффициент равен -0.0007, а ошибка при вычислении $t_3$ составила 0.00135. Таким образом, найденное решение вполне непротиворечиво.

Итоговая строчка с коэффициентами:

3.14172883822 2.71842889253 3.999957864335599

Подставляя её в качестве ответа для задачи, получаем заслуженный OK!

Задача C. Детектор свежести

Задача
Скрипт для получения решения с использованием CatBoost

В этой задаче требовалось построить детектор свежих запросов, имея готовую выборку со значениями факторов и значениями целевой функции. Каждая строчка входного файла описывала один запрос. Факторами являлись частоты заданий этого запроса в прошлом: за последний час, два часа, шесть часов, 12, 24, 72 часа. Целевая функция — бинарная: если был совершён клик по свежему документу, она равняется единице, в противном случае — нулю.

Требовалось для каждой строчки тестового файла вывести либо ноль, либо единицу, в зависимости от предсказания. Также требовалось получить на тестовом наборе $F_1$-меру более 0.25.

Решение

Поскольку требуемое значение $F_1$-меры не слишком велико, наверняка для решения задачи подойдёт какой-нибудь достаточно простой метод. Так что я попробовал просто запустить CatBoost на предоставленных факторах, а затем бинаризовать его предсказания.

Для работы CatBoost нужно предоставить два файла: обучающий и тестовый, а также описания колонок. Описания колонок составить нетрудно: первые две колонки — это текст запроса и timestamp, их проще проигнорировать. Последняя колонка — ответ. Поэтому получаем вот такое описание колонок:

0   Auxiliary
1   Auxiliary
8   Target

Поскольку тестовый файл не содержит ответов и, следовательно, последней колонки, добавим эту колонку, просто заполнив её нулями. Я использую для этого обычный awk:

awk -F "t" -vOFS="t" '{print $0, 0}' fr_test.tsv > fr_test.fixed

Теперь уже можно обучить CatBoostL

catboost calc --input-path fr_test.fixed --cd fields.cd

После этого предсказания окажутся в файле output.tsv. Однако, это будут вещественные предсказания, которые необходимо ещё бинаризовать.

Будем исходить из того, что доля положительных примеров в обучающей и тестовой выборках совпадают. В обучающей выборке около 3/4 всех запросов содержат клики по свежим документам. Поэтому подберём порог классификации так, чтобы примерно 3/4 всех запросов из тестовой выборки оказались с положительными предсказаниями. Например, для порога 0.04 таковых оказывается 178925 из 200000.

Поэтому формируем следующим образом файл решения:

awk -F "t" -vOFS="t" 'NR > 1 {if ($2 > 0.04) print 1; else print 0}' output.tsv > solution.tsv

Здесь потребовалось пропустить первую строку, т.к. в неё CatBoost записывает собственные имена столбцов.

Полученный таким образом файл solution.tsv отправляется в проверяющую систему и получает законный OK в качестве вердикта.

Задача D. Отбор признаков

Задача
Скрипт для получения решения

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

Решение

Как известно, существует большое разнообразие методов отбора признаков.

Например, можно воспользоваться каким-либо готовым методом. Скажем, я попробовал запустить feature selection в Weka и после небольшого тюнинга параметров сумел получить в этой задаче 1.8 балла.

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

Однако при использовании решающих лесов с регуляризацией (к числу которых относится и CatBoost) существует также один крайне быстрый метод отбора признаков: необходимо выбрать те факторы, которые часто используются в модели. В алгоритме CatBoost предусмотрен встроенный режим оценки влияния факторов на предсказания модели, им и воспользуемся.

Сначала нужно обучить модель:

catboost fit --cd train.cd -f train.txt

Затем запустить оценку признаков:

catboost fstr --input-path train.txt --cd train.cd

Важности признаков будут записаны после этого в файл feature_strength.tsv. В первой колонке будут записаны значимости признаков, во второй — их названия. Файл сразу отсортирован по невозрастанию важности признаков.

head feature_strength.tsv
9.897213004     f193
9.669603844     f129
7.500907599     f292
5.903810044     f48
5.268100711     f337
2.508377813     f283
2.024904488     f111
1.933500313     f208
1.878848285     f345
1.652808387     f110

Осталось лишь взять первые несколько десятков признаков и сформировать ответ. При этом имеет смысл взять настолько мало признаков, насколько возможно — как известно, сложность моделей негативно сказывается на их обобщающей способности.

Скажем, если выбрать топ-50 признаков, то на публичном тестовом наборе можно было получить 3.6 балла; если выбрать топ-40, топ-30 или топ-20, получалось ровно 4 балла. Поэтому я выбрал в качестве решения топ-20 признаков — это решение получило 4 балла и на закрытом тестовом наборе.

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

Помимо этого, нужно помнить и о других способах уменьшения размерности пространства признаков — например, существует большое разнообразие методов извлечения признаков.

Автор: ashagraev

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js