Задача A. OneRule boosting

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

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

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

Алгоритм:

  1. Обозначить
  2. Вычислить независимое приближение h0 = log|{yj|yj∈ y,yj = 1}||{yj|yj∈ y,yj = 0}|;
  3. Обозначить H0(x) = h0F0(x) = 11 + e − H0(x);
  4. Для каждого i = 0, k − 1
    1. Вычислить остатки ri,j =  − ∂ L(yj, Fi(Xj))∂ F(Xj) = yj − Fi(Xj), j = 1,m;
    2. Обучить OneRule регрессоры на остатках, R = {{trt |t∈ Tl,rt = {ri,j|Xj,l = t}} | l∈ I};
    3. Выбрать лучший регрессор h = arg minh∈ R{mj = 1(ri,j − h(xj))2m};
    4. Обозначить
      • hi + 1 = {tsum(rt)sum(Pt)|(t, rt)∈ h,Pt = {Fi(Xj)(1 − Fi(Xj))|Xj,l = t}};
      • Hi + 1(x) = Hi(x) + hi + 1(x);
      • Fi + 1(x) = 11 + e − Hi + 1(x);
      • I = I{l}, где l — номер признака, на котором был обучен лучший регрессор;
  5. Fk — искомый классификатор

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

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

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

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

Ограничения

10⩽ m⩽ 1750

5⩽ n⩽ 6034n⩽ k⩽ n

3⩽ s50

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

Стандартный вход Стандартный выход
1
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

0.074s 0.008s 13