Задача 05D. Lasso ≡

Условие

Пусть имеется задача регрессии f(x) = a ⋅ x + b ≈ y. Требуется найти коэффициенты регрессии a, такие, что |{a_i | a_i ∈ a, a_i = 0}| = k,  0 < k ⩽ |a| = m. При этом должно выполняться условие R² = 1 − n∑i = 1(y_i − f(X_i))²n∑i = 1(y_i − y)² ⩾ s. При решении задачи предполагается использование алгоритма Lasso.

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

Данные для обучения содержатся в файле. Качество модели будет рассчитано на скрытом наборе данных

Первая строка входных данных содержит натуральное число N — количество тестов. В следующих N блоках содержится описание тестов. Первая строка блока содержит целые числа n — количество примеров обучающей выборки, m — размерность пространства, k — необходимое количество нулевых коэффициентов, и вещественное число s — минимальное значение метрики R². Следующие n строк содержат по m + 1 вещественному числу — координаты точки пространства и значение целевой переменной y.

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

Решение должно представлять собой текстовый файл содержащий N строк — коэффициенты a и b линейной регрессии разделённые символом пробел.

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

1
10 5 1 0.8
-0.5  -0.26 -0.11 -0.66  0.49 -24.89
 0.08 -0.38  0.6   1.29  0.42  62.2
 0.82  0.12  0.54  1.33 -0.82  47.55
-0.36  0.54 -0.6   0.55 -0.01 -15.96
-0.91 -0.71  0.59  1.0   0.43 -11.11
-0.97 -0.78  0.2  -0.93  1.24 -17.04
 0.29  0.77 -0.87 -0.05 -0.71 -38.97
 0.19 -0.16  1.0   0.63  1.79 188.63
 0.22 -2.38  3.0   0.22 -0.53  23.32
 0.36 -0.84  1.05 -1.06 -0.06  15.31

43.69 0.0 10.48 16.86 46.25 6.39