# Бинарный поиск в задачах регрессии

### Введение

В обычной жизни мы часто сталкиваемся с регрессионными задачами, когда надо сопоставлять некий набор данных с численным значением искомой величины. "Решая" эти задачи на бытовом уровне, мы обычно используем что-то типа двоичного поиска. На примере оценки стоимости объекта недвижимости этот процесс может выглядеть так:

*Вася хочет продать свой дом и прикидывает - его дом точно стоит менее 10-ти миллионов денег, но определённо не меньше 1-го млн. Далее он открывает объявление о продаже другого дома, смотрит на него и думает: "Этот дом выглядит явно лучше моего и при этом стоит 5 млн - следовательно, мой дом стоит от 1 до 5 млн". Потом открывает еще несколько объявлений и, сопоставляя ценность других домов со своим, он приходит к выводу, что цена его дома находится в диапазоне 2-3 миллиона.*

Таким образом, последовательно сдвигая границы возможных значений цены, можно получить его хорошее приближение, используя при этом на каждом шаге только бинарный выбор.
В то же время, двоичный поиск является одним из фундаментальных алгоритмов в компьютерных науках. Это верно и для многих методов машинного обучения, таких как логистическая регрессия, KNN, SVM и другие.

---

**кат**

---

Учитывая вышесказанное, мы подумали - что если попробовать применить идею бинарного поиска для ML, сделав модель для решения классических задач регрессии на основе двоичного классификатора. Почему это может работать лучше, чем линейная регрессия? Потому что в примере выше можно предположить, что для верхнеуровнего выбора между домами стоимостью 10 млн и 1 млн будут актуальны одни признаки, а для выбора между 1,5 млн и 2 млн -- совсем другие.

В общих чертах обозначился такой алгоритм:

1) Обучаем двоичный классификатор на исходных данных.
2) Разбиваем данные на два бина в соответствии с метками классификатора.
3) Рекуррентно повторяем этот процесс с каждым из бинов, пока не дойдём до какого-нибудь из условий остановки (или останова?).
4) На стадии предсказаний проходим соответствующую цепочку обученных классификаторов и получаем нужный ответ.

Мы обобщили эту схему до случая, когда на каждом шаге данные разбиваются на N бинов (при N=2 реализуется бинарный поиск).
Ниже приведено более подробное описание получившегося алгоритма, выполненного в виде двух классов на Python, и его бенчмарки.

### Описание алгоритма

Класс *RecursiveClassRegressor* имеет стандартные для моделей библиотеки sklearn методы fit и predict.

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

.
**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 (???).

Для поиска оптимальных значений основных гиперпараметров сравниваемых методов мы использовали RandomizedSearchCV со следующими параметрами:

*спойлер*

    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),
        },
    ]

*/спойлер*

### Результаты

Используя найденные гиперпараметры для каждого из датасетов (***их надо приводить?***), мы получили следующие значения метрики MAE:

| | 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). Например, мы видим потенциал для улучшения за счет использования более совершенных способов подготовки и обработки входных данных.