Задача 02A. OneRule boosting ≡

Условие

Пусть имеется задача классификации f(x) = y, x ∈ Nⁿ, y ∈ {0,1}. Требуется написать программу, строящую классификатор методом градиентного бустинга, используя в качестве базовой модели OneRule регрессор. Получаемый классификатор имеет вид F(x) = 11 + e^− H(x), где H(x) = h₀ + k∑i = 1h_i(x), 1 ⩽ k ⩽ n, h₀ — независимое приближение, h_i обученные OneRule регрессоры. В качестве функции ошибки используется L(y, F(x)) =  − (ylog(F(x)) + (1 − y)log(1 − F(x))).

При построении классификатора необходимо использовать следующий алгоритм

Входные данные:

• X = {x_j}, x_j ∈ Nⁿ — список значений признаков примеров обучающий выборки,
• y = {y_j}, y_j ∈ {0, 1} — список значений классов обучающей выборки,
• k ∈ N, k ⩽ n — количество базовых регрессоров.

Алгоритм:

1. Обозначить
• m = |y| — количество примеров выборки
• I = {i|i = 1,n} — номера доступных для использования признаков;
• T_l = {X_j,l|j = 1,m} — уникальные значения признака с номером l;
• sum(V) = ∑v ∈ Vv — сумма элементов множества V;
2. Вычислить независимое приближение h₀ = log|{y_j|y_j ∈ y,y_j = 1}||{y_j|y_j ∈ y,y_j = 0}|;
3. Обозначить H₀(x) = h₀, F₀(x) = 11 + e^{− H₀(x)};
4. Для каждого i = 0, k − 1
1. Вычислить остатки r_i,j =  − ∂ L(y_j, F_i(X_j))∂ F(X_j) = y_j − F_i(X_j), j = 1,m;
2. Обучить OneRule регрессоры на остатках, R = {{t↦r_t |t ∈ T_l,r_t = {r_i,j|X_j,l = t}} | l ∈ I};
3. Выбрать лучший регрессор h = arg minh ∈ R{m∑j = 1(r_i,j − h(x_j))²m};
4. Обозначить
• h_i + 1 = {t↦sum(r_t)sum(P_t)|(t, r_t) ∈ h,P_t = {F_i(X_j) ⋅ (1 − F_i(X_j))|X_j,l = t}};
• H_i + 1(x) = H_i(x) + h_i + 1(x);
• F_i + 1(x) = 11 + e^{− H_i + 1(x)};
• I = I ∖ {l}, где l — номер признака, на котором был обучен лучший регрессор;
5. F_k — искомый классификатор

Формат входных данных

Первая строка входного файла содержит натуральные числа m,n,k — количество примеров, признаков и базовых регрессоров соответственно. В следующих m строках содержится n + 1 целое число — значения признаков и номер класса примера. Гарантируется, что уникальные значения каждого признака образуют множество {i|i ∈ 0,s − 1}.

Формат выходных данных

Первая строка выходного файла должна содержать независимое приближение h₀. В следующих k строках необходимо вывести описания базовых регрессоров — номер признака, на котором был обучен регрессор, и список предсказываемых регрессором значений в порядке возрастания значения признака. Вещественные числа необходимо вывести с точностью не менее трёх знаков после запятой.

Ограничения

10 ⩽ m ⩽ 1750

5 ⩽ n ⩽ 60, 34n ⩽ k ⩽ n

3 ⩽ s < 50

Примеры тестов

10 4 4
2 0 0 0 1
1 2 0 0 0
2 2 0 1 1
0 2 1 0 1
2 0 1 0 1
0 2 0 0 1
0 1 1 0 1
0 2 0 1 0
1 0 0 0 0
1 0 0 1 0

0.405
0 0.625 -2.5 1.667
3 0.813 -1.88
2 -0.113 1.14
1 -0.56 1.05 0.26