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

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

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

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

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

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

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

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

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

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

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

В реализации я буду использовать метод Уэлфорда, т.к. он нравится мне больше, чем вычисления по "стандартным" формулам. Кроме того, я не буду использовать 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 для всех объектов выборки. После загрузки всей выборки мы сортируем её по неубыванию значений признаков.

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

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

Кроме того, инициализируем переменные 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 миллисекунд на один из тестов.

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

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

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

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

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

Дополнительно стоит проверить, что

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

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, а ошибка при вычислении составила 0.00135. Таким образом, найденное решение вполне непротиворечиво.

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

3.14172883822 2.71842889253 3.999957864335599

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

Поскольку требуемое значение -меры не слишком велико, наверняка для решения задачи подойдёт какой-нибудь достаточно простой метод. Так что я попробовал просто запустить 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 в качестве вердикта.

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

Например, можно воспользоваться каким-либо готовым методом. Скажем, я попробовал запустить 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 балла и на закрытом тестовом наборе.

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

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