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

Получение этой формулировки — отличное упражнение, так как оно поднимает много общих проблем при построении и обучении пользовательских нейронных сетей:

  • Как избежать проблемы исчезающего градиента?
  • Что является хорошим выбором для начальных весов?
  • Зачем использовать пакетную нормализацию?

Но прежде чем ответить на эти вопросы, давайте посмотрим, как перефразировать дерево решений в математической структуре «Нейронные сети: дифференцируемое программирование».

XGBoost очень эффективен, но…

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



Практическое повышение градиента: подробное изучение повышения градиента в Python
Эта книга о методах повышения градиента предназначена для студентов, ученых, инженеров и специалистов по данным, которые хотят…amzn.to



Однако, несмотря на усилия, предпринятые XGBoost, LightGBM или CatBoost для улучшения построения ансамбля деревьев решений, обучение такой модели по-прежнему основано на подходе грубой силы. Он включает в себя систематическую оценку выигрыша, связанного с разделением значений и функций.

Обратитесь к моей предыдущей статье на эту тему:



Самостоятельная библиотека XGBoost менее чем в 200 строках Python
Объяснение XGBoost, а также метод повышения градиента и настройка HP путем создания собственной библиотеки повышения градиента для…в направлении науки о данных .com



Современный подход к обучению модели машинного обучения и программ в целом предполагает использование дифференциального программирования. Если вы не знакомы с этой концепцией, я написал вводную статью на эту тему:



Дифференцируемое программирование с нуля
В прошлом году у меня была прекрасная возможность посетить лекцию с Яном Лекуном на Facebook Artificial Intelligence…towardsdatascience.com



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

Хотя ансамбль деревьев решений использует для обучения подход на основе градиента, процесс их построения не дифференцируем.

Построение деревьев решений — недифференцируемый процесс

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

  1. Функция, используемая для каждого узла принятия решений, чтобы минимизировать ошибку, которая включает выбор функции.
  2. Порог, используемый для разделения входных данных на каждом узле. Данные со значением выбранного признака, превышающим пороговое значение, будут назначены правому дочернему узлу, а остальные будут назначены левому дочернему узлу.
  3. Значение, присвоенное листьям дерева.

Первые два шага недифференцируемы. В текущих реализациях Gradient Boosted Trees первый шаг требует повторения функций и не является гладким. Второй шаг включает в себя оценку выигрыша с использованием полученного раздела данных и списков возможных значений. Этот процесс также недифференцируем.

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



Нейронные ансамбли забывчивых решений для глубокого обучения на табличных данных
В настоящее время глубокие нейронные сети (ГНС) стали основным инструментом для задач машинного обучения в широком диапазоне…arxiv.org



Я настоятельно рекомендую прочитать их статью, так как всегда полезно получить информацию из источника. Однако для облегчения понимания я написал некоторый код Python с использованием Jax.

Вопросы, рассматриваемые в статье, следующие:

  1. Как мы можем переформулировать выбор признаков, чтобы сделать его гладким и дифференцируемым?
  2. Как мы можем переформулировать сравнение, чтобы сделать его гладким и дифференцируемым?

Регуляризация выбора признаков

Как упоминалось ранее, выбор признаков в стандартных алгоритмах Gradient Boosting выполняется с помощью полного перебора: мы пробуем каждую функцию и оставляем ту, которая дает наибольший выигрыш.

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

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

features = np.array([1.1, 3.2, 4.5])
selection_weights = np.array([0, 0, 1])
selected_feature_value = np.dot(selection_weights, features)
print(selected_feature_value)
# Output: 4.5

Следовательно, мы можем получить конкретное значение из массива признаков, умножив их все на 0, кроме одного, который нам нужно сохранить, и просуммировав все произведения.

Изучение функции, обеспечивающей наибольшую производительность, включает в себя изучение вектора selection_weights с дополнительным ограничением, состоящим в том, что сумма его элементов должна быть равна 1. В идеале эта 1 должна быть сосредоточена в одном элементе вектора.

Обеспечение соблюдения этого ограничения на норму вектора выбора может быть достигнуто с помощью функции. Очевидным кандидатом является функция softmax, которая устанавливает норму вектора весов равной 1. Однако softmax генерирует гладкое распределение и не может генерировать 1 для самого высокого веса и 0 для остальных.

Следующий фрагмент кода иллюстрирует это:

import numpy as np
from jax.nn import softmax
from entmax_jax import entmax15, sparsemax

weights = np.array([2, 3, 5, 7, 11, 17])
print(np.linalg.norm(softmax(weights)))
# Output: 0.99747807
print(softmax(weights))
# Output: [3.0512990e-07 8.2942910e-07 6.1286983e-06 4.5285295e-05 2.4724933e-03 9.9747497e-01]

Мало того, что норма не равна точно 1,0, но распределение распределено по всем измерениям.

Поэтому в документе NODE вместо этого предлагается использовать функцию entmax:

import numpy as np
from jax.nn import softmax
from entmax_jax import entmax15, sparsemax

weights = np.array([2, 3, 5, 7, 11, 17])
print(np.linalg.norm(entmax15(weights)))
# Output: 1.0
print(entmax15(weights))
# Output: [0. 0. 0. 0. 0. 1.]

Кажется, это хороший выбор, так как он дает ожидаемый результат!

Используя скалярное произведение в сочетании с функцией entmax, мы можем получить значение данной функции.

Выбор дифференцируемых признаков может быть таким простым, как:

def pick_features(weights, features):
    feature = jnp.dot(entmax15(weights), features)
    return feature

На этапе обучения веса будут обучаться, чтобы узнать, какую функцию следует сохранить для данного решения.

Введение порога

Другой параметр, используемый в узле принятия решений, который необходимо изучить, — это порог. Если значение выбранного признака больше или равно этому порогу, прогноз следует по правильному пути дерева. И наоборот, если значение строго меньше, выбирается левый путь.

Аналогичный подход можно использовать для генерации 1, если значение выше или ниже порога, с помощью скалярного произведения и функции entmax, но с вектором размера 2. Первый элемент представляет разница между выбранным значением и порогом, а второй элемент равен 0.

Благодаря функции entmax, если значение ниже порога, первый элемент вектора отрицательный. При применении функции entmax 0 преобразуется в 1, а отрицательная часть становится равной 0. И наоборот, когда значение больше порогового значения, первый элемент равен 1, а второй элемент равно 0.

Вот пример реализации:

import numpy as np
import jax.numpy as jnp
from jax.nn import softmax
from entmax_jax import entmax15, sparsemax

def choose(feature, threshold, left, right):
    choices = jnp.array([left, right])
    steer = jnp.array([threshold - feature, 0])
    pred = jnp.dot(entmax15(steer), choices)
    return pred
print(choose(12, 10, -1, 1))
# Output: 1
print(choose(8, 10, -1, 1))
# Output: -1

В процессе обучения параметрами, которые необходимо изучить, являются не только порог, но и веса, прикрепленные к правому и левому листьям этого простого одноуровневого дерева.

Следующие шаги

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

Тем не менее, есть еще две проблемы, которые необходимо решить:

  1. Как расширить метод для поддержки многоуровневых деревьев решений?
  2. Как узнать параметры таких деревьев?
  3. Как мы можем гарантировать, что мы остаемся в линейной части entmaxфункции и гарантируем, что градиент не исчезнет?

Я предоставлю более подробную информацию по этим темам в следующей статье.

А пока, если вы хотите улучшить свое мастерство в повышении градиента, ознакомьтесь с моей книгой на эту тему:



Практическое повышение градиента: подробное изучение повышения градиента в Python
Эта книга о методах повышения градиента предназначена для студентов, ученых, инженеров и специалистов по данным, которые хотят…amzn.to