Инженерный тур. 2 этап

После минимакс-нормализации уравнение для предсказания выглядит как:

\[y(x) = \sum_{i=1}^n c_i x_i + c_{n+1}.\]

Подставим вместо \(x_i\) нормализованную версию \(x_i = \frac{x'_i-l_i}{u_i-l_i}\), где \(x'\) — оригинальные данные до нормализации:

\[y(x) = \sum_{i=1}^n c_i \frac{x'_i-l_i}{u_i-l_i} + c_{n+1}.\]

Но полученное предсказание будет для нормализованного целевого признака, поэтому его нужно преобразовать обратным преобразованием:

\[y_d(x) =(u_{n+1} - l_{n+1}) \cdot y(x) + l_{n+1} = (u_{n+1} - l_{n+1}) \cdot \left ( \sum_{i=1}^n c_i \frac{x'_i-l_i}{u_i-l_i} + c_{n+1} \right ) + l_{n+1}.\]

Так как нормализация и обратное к ней преобразование являются линейными, их можно скомбинировать в новое линейное уравнение:

\[y_d(x) =\sum_{i=1}^n \frac{ (u_{n+1} - l_{n+1})c_i}{u_i-l_i} x'_i + (u_{n+1} - l_{n+1}) \left(-\sum_{i=1}^n \frac{c_i l_i}{u_i-l_i} +c_{n+1}\right) + l_{n+1}.\]

В этом уравнении коэффициент при \(x'_i\) равен: \(\frac{ (u_{n+1} - l_{n+1})c_i}{u_i-l_i}\), его можно просто вычислить за \(\mathcal O(1)\) при ответе на соответствующий запрос.

В том же уравнении свободный коэффициент равен \[(u_{n+1} - l_{n+1}) \left(c_{n+1} - \sum_{i=1}^n \frac{c_i \cdot l_i}{u_i-l_i} \right)+ l_{n+1}.\] Наивное его вычисление потребует \(\mathcal O(N)\) времени, так как содержит в себе сумму \(\sum_{i=1}^n \frac{c_i \cdot l_i}{u_i-l_i}\). Но эту сумму можно предподсчитать, а затем обновлять соответствующие слагаемое при запросе на изменение. Тогда на запрос значения свободного коэффициента можно отвечать за \(\mathcal O(1)\).

Среднее квадратическое вычисляется как корень из суммы квадратов, деленной на число слагаемых в этой сумме. Рассмотрим \(p\)-е разбиение. Оно будет состоять из двух частей. В первой части будет \(l\, = \,p\, +\, 1\) элемент, а во второй — \(r = n - l = n - p - 1\). Тогда сумма для оценки среднеквадратической разности для первой части будет содержать \(l(l-1)/2\) слагаемых, для второй будет \(r(r-1)/2\), а между частями будет \(lr\). Потому что ровно столько будет различных пар разностей для соответствующих средних квадратических.

Теперь необходимо научиться быстро вычислять сумму квадратов разностей для различных разбиений и между ними. Для начала решим задачу только для первой части каждого разбиения. Если рассматривать все разбиения в порядке возрастания номера, то каждый раз к первой части будет добавляться один элемент из второй. Получается, что сумма квадратов разностей будет состоять из предыдущей суммы плюс суммы квадратов разности добавляемого элемента \(h_{l}\) с существующими \(\left\{h_i\right\}_{i=1}^{l-1}\):

\[\sum_{i=1}^l\sum_{j=1}^{i-1} (h_i - h_j)^2 = \sum_{i=1}^{l-1}\sum_{j=1}^{i-1} (h_i - h_j)^2 + \sum_{i=1}^{l-1} (h_i - h_l)^2.\]

Добавляемую сумму можно переписать как:

\[\begin{aligned} \sum_{i=1}^{l-1} (h_i - h_l)^2 = \sum_{i=1}^{l-1} (h_i^2 - 2 h_i h_l + h_l^2) =\sum_{i=1}^{l-1} h_i^2 - \sum_{i=1}^{l-1} 2 h_i h_l + \sum_{i=1}^{l-1} h_l^2 =\\ {}=\sum_{i=1}^{l-1} h_i^2 - 2h_l \sum_{i=1}^{l-1} h_i + (l-1) h_l ^ 2. \end{aligned}\]

В свою очередь, суммы \(\sum_{i=1}^{l-1} h_i\) и \(\sum_{i=1}^{l-1} h_i^2\) также можно не вычислять заново, а воспользоваться уже вычисленными суммами \(\sum_{i=1}^{l-2} h_i\) и \(\sum_{i=1}^{l-2} h_i^2\) с предыдущего разбиения: \(\sum_{i=1}^{l-1} h_i = \sum_{i=1}^{l-2} h_i + h_{l-1}\) и \(\sum_{i=1}^{l-1} h_i^2 = \sum_{i=1}^{l-2} h_i^2 + h_{l-1}^2\). Получается, что каждое обновление каждой суммы производится за \(\mathcal O(1)\).

Для вычисления суммы квадратов разностей второй части каждого разбиения можно развернуть массив и применить алгоритм, который использовался для первых частей. Заметим, что в конце этого же алгоритма при добавлении всех элементов в одну часть получится сумма квадратов разностей между всеми элементами \(\sum_{i=1}^{n} \sum_{j=1}^{i-1} (h_i-h_j)^2\), которая также пригодится в дальнейшем.

Для любого разбиения сумму квадратов разностей между частями можно вычислить как разницу суммы квадратов разностей между всеми элементами и между элементами первой и второй частей, так как оба элемента из каждой пары лежат либо в одной части, либо в разных: \[\sum_{i=1}^{n} \sum_{j=1}^{i-1} (h_i-h_j)^2 = \sum_{i=1}^{l} \sum_{j=1}^{i-1} (h_i-h_j)^2 + \sum_{i=1}^{l} \sum_{j=l+1}^{n} (h_i-h_j)^2 + \sum_{i=l+1}^{n} \sum_{j=i+1}^{n} (h_i-h_j)^2 \Rightarrow\] \[\Rightarrow \sum_{i=1}^{l} \sum_{j=l+1}^{n} (h_i-h_j)^2 = \sum_{i=1}^{n} \sum_{j=1}^{i-1} (h_i-h_j)^2 - \sum_{i=1}^{l} \sum_{j=1}^{i-1} (h_i-h_j)^2 - \sum_{i=l+1}^{n} \sum_{j=i+1}^{n} (h_i-h_j)^2.\] Получается, что для каждого разбиения сумму квадратов разностей между частями также можно вычислить за \(\mathcal O(1)\) из уже вычисленных сумм.

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

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

Пример программы-решения

Ниже представлено решение на языке Python.

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.decomposition import PCA
from sklearn.linear_model import LogisticRegression

# Загрузка данных
train_data = pd.read_csv("train.csv")
sim_data = pd.read_csv("sim.csv")

#Построение полной матрицы схожести
similar = pd.pivot_table(sim_data, values='sim', index='id1', columns='id2').fillna(0)

X = similar.loc[train_data['id']].fillna(0)
y = train_data['class']
X_train, X_val, y_train, y_val = train_test_split(X, y, test_size=0.05, random_state=42)

# Извлечение признаков
pca = PCA(n_components=95, random_state=2750)
pca.fit_transform(X_train)
X_train = pca.transform(X_train)
X_val = pca.transform(X_val)

# Обучение модели и построение предсказаний
model = LogisticRegression(C=0.844, max_iter=4000)
model.fit(X_train, y_train)

test_id = range(10000, 15000)
test_data = similar.loc[test_id]
predictions = model.predict(pca.transform(test_data.fillna(0)))

ans = pd.DataFrame({'id': test_id, 'class':predictions})
ans.to_csv('predictions.csv', index=False)

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

Так как наборы данных не содержали информации о целевой задачи, для обучения эмбендингов необходимо было использовать самообучение. В качестве суррогатной задачи можно было использовать задачу обучения автокодировщика, который по значению эмбендингов должен предсказать их же самих. Архитектура автокодировщика должна была содержать регуляризирующий фактор, например, «бутылочное горлышко», чтобы тождественная функция, которую аппроксимирует автокодировщик, не была тривиальной. Другая важная часть автокодировщика — пакетная нормализация, которая призвана предотвратить вырождение эмбедигов, поскольку тривиальным решением будет заполнение всех эмбендингов нулями

Пример программы-решения

Ниже представлено решение на языке Python.

import os
import numpy as np
import pandas as pd
import torch
import torch.nn as nn

class AutoEncoder(nn.Module):
    def __init__(self, dims):
        super(AutoEncoder,self).__init__()

        self.k = len(dims)
        self.embedings = []
        self.dims = dims

        for dim in dims:
            self.embedings.append(nn.Embedding(dim, 1))
            
        self.embedings = nn.ModuleList(self.embedings)
        
        self.input_layer = nn.Linear(self.k, 5)
        self.relu = nn.ReLU()
        self.output_layer = nn.Linear(5, self.k)
        self.bn = nn.BatchNorm1d(self.k,affine=False)

    def embded(self,x):
        s = torch.zeros((x.size()[0], self.k))

        for i in range(self.k):
            s[:,i] = self.embedings[i](x[:,i]).flatten()
        
        return s
    
    def forward(self,x):
        out = self.embded(x)
        out = self.relu(self.input_layer(out))
        out = self.output_layer(out)
        out = self.bn(out)
        return out

directory = "games"

game_id = []
deck_id = []
order = []

for filename in os.listdir(directory):
    f = os.path.join(directory, filename)
    data = pd.read_csv(f) - 1
    g,n,m = map(int,filename[:-4].split("_"))
    
    t = torch.tensor(data.to_numpy())
    dims = data.max() + 1
    model = AutoEncoder(dims)
    
    learning_rate = 0.1
    criterion = nn.MSELoss()
    optimizer = torch.optim.Adam(model.parameters(),lr=learning_rate)

    for epoch in range(100):
        optimizer.zero_grad()
        output_train = model(t)
        loss = criterion(output_train, model.embded(t))
        loss.backward()
        optimizer.step()

    for d, embd in enumerate(model.embedings):
        game_id.append(g)
        deck_id.append(d + 1)
      order.append(" ".join(map(str, np.argsort(embd.weight.detach().numpy().flatten()) + 1)))
    
pd.DataFrame({"game" : game_id, "deck" : deck_id, "order" : order}).to_csv("submission.csv", index=False)