# ML алгоритм как пет-проект: как мы учили ML двоичному поиску

Представим простую задачу регрессии: оценить стоимость дома по его параметрам. Люди решают ее как-то так:

*Вася хочет продать свой дом. Он прикидывает - дома в поселке стоят не меньше миллиона рублей, но больше десяти миллионов рублей он не видел. Осматривая обявления о продаже других домов, он замечает, что двухэтажные дома с хорошим ремонтом, как у него, стоят не меньше трех миллионов. Его дом находится ближе к речке, так что скорее всего будет стоить побольше...*

Человек начинает с какого-то интервала и постепенно сужает его на основе особенностей дома. Этот метод можно представить как двоичный поиск. Дом стоит больше 5 миллионов или меньше? Скорее всего меньше. Больше 2.5 миллионов? Скорее больше. И так далее, пока интервал не станет достаточно узким.

Вы когда-нибудь слышали, чтобы кто-то сказал: мой дом стоит 3 милилона 843 тысячи 158 рублей 40 копеек? Думаю нет. Но в машинном обучении мы почему-то требуем от моделей именно таких ответов.

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

---

**кат**

---

## Сводим регрессию к классиификации

Самый популярный способ решать задачу регресии это аддитивная модель, вроде линейной регрессии. Пусть средняя стоимость дома k0 рублей, каждый этаж дома повышает его стоимость на k1 рублей, каждый квадратный метр площади на k2 рублей. Далее будем оптимизировать эти коэффициенты:

$$y = k_0 + k_1 x_1 * k_2 x_2$$

Если же мы ищем интервал, такая модель нам не подойдет. Начнем с интервала размером от минимального таргета до максимального и будем его сужать. Пусть дома в обучающей выборке бывают стоимостью от 1 до 10 миллионов.

Создадим промежуточную задачу: дом стоит больше 5 миллионов или меньше? Это бинарная классификация: пометим все дома стоимостью до 5 млн как 0, остальные как 1, обучим простой классификатор. Переходим к следующему уровню. Пусть дом стоит стоит меньше 5 миллионов. Получаем вторую задачу бинарной классификации: дом стоит больше 2.5 млн или меньше? Время обучить еще один классификатор. Будем продолжать делить выборку и обучать классификаторы до какого-то условия остановки.

В чем может быть преимущество такого метода над аддитивной моделью? Можно предположить, что для выбора между домами стоимостью 1 млн и 100 млн будут актуальны одни признаки, а для выбора между 1,5 млн и 2 млн - совсем другие. В нашем методе классификатор первого разбиения может использовать одни признаки, чтобы разделить большие категории, а классификаторы последних разбиений могут использовать другие признаки для гранулированного разделения.

Алгоритм обучения такой:
1) Сортируем примеры по таргету.
2) Разбиваем примеры на два бина, сопоставляем каждому бину метки: 0 или 1.
2) Обучаем классификатор разбиения на этих метках.
3) Проверяем условие остановки. Например, если в бины попало слишком мало примеров, останавливаем процесс.
4) Запускаем алгоритм на примерах, попавших в каждый бин.

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


Для предсказания пропустим пример через все разбиения и найдем последний бин, в котором он окажется. Например, дом пройдет через наше дерево и окажется в бине с домами стоимостью от 1.2 млн до 1.5 млн. В качестве предсказания можно взять интервал [1.2, 1.5], среднюю стоимость домов в бине или даже обучить маленькую регрессию.

Алгоритм можно обобщить далее. Зачем ограничиваться двумя бинами на каждом разбиении? Можно разбивать на K бинов и учить многоклассовый классификатор. Зачем ограничиваться бинами одинакового размера? Можно делать бины по размеру пропорциональными количеству примеров.

### Решаем проблемы

Рекурсивно применять классификатор к каждому примеру? Звучит как катастрофа. При таком подходе алгоритм нельзя будет применять к датасетам из реального мира - слишком медленно. А что если первый классификатор ошибся? Тогда предсказания всех остальных классификаторов бесполезны. Ошибка будет накапливаться.

Мы можем решить обе проблемы если используем оценку вероятности, полученную от классификатора. Пусть дом с 20% вероятностью стоит меньше 5 миллионов и с 80% вероятностью стоит больше. Запустим пример в оба поддерева, получим от них предсказания стоимости дома. Например, пусть согласно левому дереву дом стоит до 3 млн, а согласно правому 7 млн. Просуммируем эти оценки взвесив их вероятностям верхнего классификатора: $0.2*3 + 0.8*7 = 6.2$ млн.

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

Одно ограничение метода нельзя исправить: он не умеет экстраполировать за пределы обучающей выборки.

### Lets get technical

Мы обернули решение в класс *RecursiveClassRegressor* с sklearn интерфейсом.

Гиперпараметры модели:
n_bins - количество бинов, на которые делятся данные на каждом уровне
n_levels - количество уровней деления
bins_calc_method - метод разделения таргета на бины
leaf_size - минимальный размер листового (неделимого) бина
leaf_model_cls_name - модель регрессора для предсказаний на листовых бинах, по умолчанию просто среднее

**Fit**
На первом шаге распределение таргет-переменной делится на *n-bins* частей (бинов), каждый из которых помечается своей меткой (0, 1, ...), после чего на этих данных обучается логистическая регрессия, используя в качестве нового таргета полученные метки.

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

К примеру, если у нас есть исходное распределение таргета [1, 2, 3, 4, 5, 6, 7, 8], то при значении n_bins=2 (при котором реализуется бинарный поиск) на первом шаге получится два бина [1, 2, 3, 4], [5, 6, 7, 8], а на втором четыре - [1, 2], [3, 4], [5, 6], [7, 8].

Соответственно, на первом шаге один классификатор обучается различать данные в двух бинах между собой, на втором - уже два классификатора делают то же самое - каждый в рамках своего бина - и так далее (глубина поиска ограничивается параметром n_levels).

С помощью рекурсивного метода происходит обход всех бинов на всех уровнях (кол-во которых задаётся параметром n_levels).


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

Исходное деление на бины производится одним из двух способов (параметр bins_calc_method):
1. деление с фиксированным шагом по шкале таргет-переменной;
2. деление на бины, сбалансированные по количеству наблюдений в каждом.

В результате работы метода fit мы получаем ансамбль классификаторов, которые обучены вычислять вероятность попадания рассматриваемого наблюдения в каждый из листовых бинов (с помощью predict_proba). А также набор регрессоров, каждый из которых обучен находить решение на соответствующем бине.

**Predict**
Для каждого наблюдения в датасете, подаваемом в predict, срабатывает ранее обученный ансамбль классификаторов, определяя с помощью соответствующих значений predict_proba вероятность попадания в каждый из листовых бинов.

Затем на каждом из бинов вычисляется прогноз для текущего наблюдения, после чего все прогнозы усредняются с учётом весов, равных полученным ранее вероятностям попадания в бин.


### Бенчмарки

Для сравнения мы взяли два датасета: California Housing (CA, real estate data, Kelley Pace and Barry (1997)) и DF_2 (???).

Бейзлайны были такие:
* Sklearn: ElasticNet, GradientBoostingRegressor
* Lightgbm

Для всех методов подбирали гиперпараметры с помощью Random Search с такой сеткой:
*спойлер*

    hparam_spaces = [
        { # RecursiveClassRegressor
            'model__n_bins': [2, 3, 5],
            'model__n_splits': [2, 3, 5, 10],
            'model__bins_calc_method': ['equal', 'percentile'],
            'model__leaf_size': [10, 50, 100],
            'model__leaf_model_cls_name': ['DummyRegressor', 'LinearRegression'],
        },
        { # ElasticNet
            'model__alpha': scipy.stats.norm(0.5, 1),
            'model__l1_ratio': scipy.stats.norm(0.5, 0.15),
        },
        {  # GradientBoostingRegressor
            'model__max_depth': np.arange(-1, 20, 2),
            'model__subsample': np.arange(0.2, 1.2, 0.2),
            'model__n_estimators': np.arange(10, 310, 40),
        },
        { # LGBMRegressor
            'model__max_depth': np.arange(-1, 20, 2),
            'model__subsample': np.arange(0.2, 1.2, 0.2),
            'model__n_estimators': np.arange(10, 310, 40),
        },
    ]

*/спойлер*

Получили такие метрики:

| | CA_MAE_mean | CA_time_mean, с | DF_2_MAE_mean | DF_2_time_mean, с |
| -------- | -------- | -------- | -------- | -------- |
| RecursiveClassRegressor | 43746 | 0.289 | 4 | 0.3 |
| ElasticNet | 49501 | 0.087 | 5 | 0.1 |
| GradientBoostingRegressor | 29508 | 5.450 | 4 | 0.4 |
| LGBMRegressor | 30108 | 0.220 | 2 | 0.2 |

Как можно видеть, MAE у рассматриваемой модели регрессора получились лучше, чем у линейной регресии, но хуже, чем у каноничного GradientBoostingRegressor. В то же время последний оказался медленнее. LGBM остался лидером по всем параметрам.

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

### Выводы

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

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