Блог

Градиентный бустинг (AdaBoost)

  • Цветков Максим
  • 21.03.2020

Градиентный бустинг нужен для задач классификации и регрессии, похож на случайный лес. Это сложная тема, в том числе и из-за сложной интерпретации метода, то есть возможности понятным языком объяснить менеджеру банка, на основе каких правил было принято решение. В прошлых уроках про линейную регрессию было явно видно, у какого признака какой вес и на сколько он влияет на результат. Градиентный бустинг нужен для регрессии, классификации, применим везде, где есть размеченные данные. Например, ранжирование ответов от нейросети в голосовых помощниках. Исключение — компьютерное зрение, НЛП, это лучше реализовать на нейронках. В практических задачах чаще берут легко интерпретируемые алгоритмы, например в финтехе. А в маркетинге уместны сложные алгориты, типа градиентного бустинга.

Мы рассмотрим частный случай градиентного бустинга под названием AdaBoost (adaptive boosting), который очень прост в реализации и совмещает сразу несколько разных моделей, и это далеко не только деревья, но в основном хороший результат получается на деревьях. Хорошая вычислительная сложность и результат по прогнозированию. Работает по принципу перевзвешивания результатов. Есть деревья решений, а ансамбль из них это градиентный бустинг.

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

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

Два класса (квадрат и круг), первое дерево работает по сравнению с неким порогом. Каждое новое дерево фиксит ошибки предыдущих.

Давайте разберем подробнее основной принцип AdaBoost: подгонка слабых «учащихся» (т.е. модели, которые лишь немного лучше, чем случайные догадки) под многократно модифицированные версии данных. Следующим шагом прогнозы по всем из них объединяются с помощью голосования для получения окончательного прогноза. Модификации данных на каждой так называемой повышающей итерации состоят из применения N-весов к каждому из тренировочных образцов. Первоначально все эти веса устанавливаются на 1/N, так что на первом этапе просто тренируется слабый ученик на исходных данных. Для каждой последовательной итерации выборочные веса индивидуально модифицируются, и алгоритм обучения применяется еще раз к повторно взвешенным данным. На данном этапе те тренировочные данные, которые были неправильно спрогнозированы моделью с прошлого этапа, имеют увеличенные веса, в то время как веса, которые были спрогнозированы правильно, уменьшаются. По мере выполнения итераций все большее вливания приоритета идет на те участки, которые трудно предсказать. 

from sklearn import model_selection
from sklearn.datasets import load_digits
plt.imshow(X[9].reshape(8,8))
 
X, y = load_digits(return_X_y=True)
from sklearn.preprocessing import MinMaxScaler
scaler = MinMaxScaler()
X = scaler.fit_transform(X)
X_train, X_test, y_train, y_test = model_selection.train_test_split(X, y, test_size=0.32)
def get_error(pred, y):
    return sum(pred != y) / len(y)

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

Возьмем метрику accuracy, это не лучшая метрика, она больше для сбалансированых классов, но вы можете поменять метрику на ту, которую сочтете нужной (roc_auc/f1/average precision). sample_size это размер выборки, а classes_amount будет содержать классы. В моем примере начальные веса деревьев будут равны 1, все деревья имеют одинаковый вес и записаны в models.

from sklearn.tree import DecisionTreeClassifier
 
def adaboost(X, y, N):
    sample_size = len(X)
    classes_amount = len(np.unique((y)))
 
    w = np.ones(sample_size, dtype=np.float32)
    w = np.ones(sample_size) / sample_size
    models = []
 
    for n in range(N):
 
        clf = DecisionTreeClassifier(max_depth=2, splitter='best', criterion='gini').fit(X,y, sample_weight=w)
        print('Accuracy using the defualt gini impurity criterion...',clf.score(X, y))
 
        predictions = clf.predict(X)
        e = get_error(predictions, y)
        if e==0 or e>=  1 - 1 / classes_amount:
            break
 
        alpha = 0.5 * np.log((1 - e) / e) + np.log(classes_amount - 1) 
        match = predictions == y
 
        w[~match] *= np.exp(alpha)
 
        w /= w.sum()
        models.append((alpha, clf))
 
    return models

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

Обучим алгоритм на 500 деревьев. AdaBoost генерирует последовательность слабых классификаторов, где на каждой итерации алгоритм находит лучший классификатор, основываясь на текущих весах выборки. Правильная классификация получает меньший вес, неправильная — больший, и так до тех пор, пока не будет найдена оптимальная модель. Увеличение веса происходит за счет w[~match] *= np.exp(alpha). Мы просто «объединяем» нескольких слабых учащихся в одного сильного ученика. Слабый учащийся это обычно не дерево, а пенёк, в бустинге принято над деревьями использовать пеньки (глубиной ~3).

import numpy as np
N = 500
 
models = adaboost(X_train, y_train, N)
def predict(X, models):
    sample_size = len(X)
 
    y_pred = np.zeros((sample_size, 10))
 
    for alpha, clf in models:
        prediction = clf.predict(X)
        y_pred[range(sample_size), prediction] += alpha
 
    y_pred = np.argmax(y_pred, axis=1)
    return y_pred
 
print(f'Обучающая выборка, точность алгоритма: {(1 - get_error(predict(X_train, models), y_train)) * 100:.3f}')
print(f'Тестовая выборка, точность алгоритма: {(1 - get_error(predict(X_test, models), y_test)) * 100:.3f}')
Accuracy using the defualt gini impurity criterion... 0.26863226863226863
Accuracy using the defualt gini impurity criterion... 0.2334152334152334
Accuracy using the defualt gini impurity criterion... 0.28501228501228504
Accuracy using the defualt gini impurity criterion... 0.1294021294021294
Accuracy using the defualt gini impurity criterion... 0.24815724815724816
Accuracy using the defualt gini impurity criterion... 0.19737919737919737
Accuracy using the defualt gini impurity criterion... 0.1891891891891892
Обучающая выборка, точность алгоритма: 97.707
Тестовая выборка, точность алгоритма: 92.188

И визуализируем:

import matplotlib.pyplot as plt
train_errors = []
test_errors = []
 
for n in range(1, 26):
    mods = adaboost(X_train, y_train, n)
    train_errors.append(get_error(predict(X_train, mods), y_train))
    test_errors.append(get_error(predict(X_test, mods), y_test))
 
x = list(range(1, 26))
 
plt.xlim(0, 25)
plt.plot(x, train_errors, color= 'r', linestyle=":", lw = 2, label='train errors')
plt.plot(x, test_errors, color= 'c', linestyle="--", lw = 2, label='test errors')
plt.title('Classifier')
plt.xlabel('N')
plt.ylabel('Accuracy')
plt.legend(loc='upper right')
Accuracy using the defualt gini impurity criterion… 0.20802620802620803
Accuracy using the defualt gini impurity criterion… 0.24897624897624898
Accuracy using the defualt gini impurity criterion… 0.3407043407043407
Accuracy using the defualt gini impurity criterion… 0.21703521703521703
Accuracy using the defualt gini impurity criterion… 0.23832923832923833
Accuracy using the defualt gini impurity criterion… 0.32186732186732187
Accuracy using the defualt gini impurity criterion… 0.27764127764127766
Accuracy using the defualt gini impurity criterion… 0.20147420147420148
Accuracy using the defualt gini impurity criterion… 0.2547092547092547
Accuracy using the defualt gini impurity criterion… 0.3284193284193284

На графике видно, что ошибок на тесте больше, чем на трейне. Но при достижении количества деревьев в районе 80 графики выходят на условное плато. Значит, меньше 80 деревьев нет смысла применять. На практике применяют и 1000, и 5000 деревьев, но на таких количествах обычно никакой разницы нет, ошибка становится минимальной.

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

import tensorflow as tf 
import numpy as np
import sklearn
import matplotlib.pyplot as plt
 
(x_train, y_train), (x_test, y_test) = tf.keras.datasets.mnist.load_data()
 
x_train = x_train.reshape(60000, 784).astype('float32') / 255
x_test = x_test.reshape(10000, 784).astype('float32') / 255
 
y_train = y_train.astype('float32')
y_test = y_test.astype('float32')
 
from sklearn.ensemble import GradientBoostingClassifier
clf = GradientBoostingClassifier(learning_rate=0.41, n_estimators=150, verbose=1, subsample=0.5)
clf.fit(x_train_flat, y_train)
 
from sklearn.metrics import accuracy_score
accuracy_score(y_test, clf.predict(x_val_flat))

Точность 0.9238.

Плюсы использования AdaBoost:

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

Из минусов можно отметить:

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

Если брать готову реализацию, то по табличным данным для серьезных проектов я бы брал современный градиентный бустинг (CatBoost, XGboost, LightGBM). Если не табличные, то это нейронные сети. Либо их комбинации: для голосового помощника требуется отдельная сеть на распознание ключевого слова «Алиса», «Siri» не в диалоге, а при обращении. Распознавание голоса, выявление интента, поиска ответа и синтез ответа в речь.

Где место adaBoost в жизни продуктового дизайнера? На реальных задачах часто нужно сказать бизнесу прогноз по retention. В этом случае процесс может быть такой: определить, по каким значениям мы считаем отток клиентов → бинарная классификация + пройденный нами градиентный бустинг → детализация фичами → a/b тест с группой клиентов, которые вроде как собираются уходить. Или более примитивные задачи, оценка стоимости авто по его характеристикам.

7 комментариев

  1. Ольга

    14.04.2021

    Привет, мне надо выгрузку CSV заархивировать, 80 гигов. Архиватор из убунты не справился за несколько попыток. Что нибудь посоветуете?)

    Ответить

    • Цветков Максим

      14.04.2021

      Я бы попробовал по очереди pigz, 7z с lzma2 и zstd.
      Если комп попросту такое не тянет, то делать выборку из данных.

      Ответить

  2. Yevhenii Selivanov

    07.07.2021

    Ищут ли точки роста бизнеса с помощью AI?

    Ответить

    • Цветков Максим

      07.07.2021

      Рост бизнеса это долгосрочный заработок. Это новые продукты, рост среднего чека, удержание клиента, рост конверсии, масштабирование и уменьшение расходов, отсутствие проблем с операционной масштабируемостью бизнеса (внутренние продукты).
      Новые продукты — любой продукт растет и выходит на стагнацию, и умирает. Это S-кривая. Понимать, когда продукт умрет — важно. И еще важнее понять, как сделать продукт быстрее, приятнее, дешевле (например, подсчет рисков выдачи кредита или поведения водителя). Если водит нормально — можно закладывать меньше рисков и соответственно, услуга дешевле.

      Средний чек — его надо растить. Можно считать цену под каждого клиента, давать рекомендации и сопутствующие товары.

      Удержание — анализ оттока, таргетированные акции, мониторинг отзывов, кластеризация клиентов, рекомендации. Это легко померить метрикой return rate, где мы делим текущее кол-во активных пользователей из датасета на общее кол-во пользователей из датасета * 100. Например, 800 922 / 1 203 211 * 100 = 66%. Либо обратная метрика churn rate: кол-во людей, которые ушли в отток делим на общее кол-во пользователей из датасета * 100.

      Конверсия — омниканальные рекомендации, скоринг заявок на работу только с конверсионными, анализ воронки продаж.

      Уменьшение расходов — таргетинг, замена людей алгоритмами/RPA, анализ аномалий, чат-боты, управление остатками и прогноз спроса, оптимизация процессов.

      Масштабирование — поиск места для нового магазина.

      Ответить

  3. Анар

    28.06.2022

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

    Ответить

    • Цветков Максим

      28.06.2022

      Я бы пошел таким путем: задача это выделить сегменты, описывающие интересы пользователя, т.e. это векторное представление пользователя.
      Если есть возможность для многоклассовой классификации, с разметкой новостных данных, то прекрасно. Но это долго и обычно все приходят к кластеризации новостей и описанию пользователей через выделенные сегменты, обучение без учителя (нету целевых значений). Обычная задача математического моделирования LDA (Latent Dirichlet allocation).

      Мы можем из статьи выделить некоторые темы на основе слов. Так, статья про кулинарию наверняка будет включать «духовка», «мука», «тесто», «миска» и тп. На выходе LDA выдает что-то вроде:
      • Предложения 2,3,4,5,6: 100% Topic A
      • Предложения 1,7,8,10: 100% Topic B
      • Предложение 9: 60% Topic A, 40% Topic B

      И при желании можно получить статистику: Topic A состоит из слов «духовка» на 20%, «мука» на 10%. Тут уже можно понять, что Topic A про еду. После получения такого распределения мы начинаем его улучшать: под каждое слово делаем проход с подсчетом вероятностей, что тема на самом деле принадлежит статье.

      Будет две вероятности принадлежности темы статье: для первой берем все слова, и слова которые уже выбраны под тему статьи, и подсчитывается вероятность попадания тем в статью (theme|document). Вторая вероятность по слову в теме (word|theme). Перемножаем две вероятности и получаем новую: (|) ∗ (|) = вероятность что тема (t) генерирует слово (w). Все это повторяем для каждого слова в каждой статье множеством проходов, приходим к стабильному состоянию.

      На практике:

      import pandas as pd 
//подгрузили данные
news = pd.read_csv("data.csv")
print(news.shape)
news.head(10)
news.iloc[0]['title']

      Аналогичное проделываем для статей, которые читались. Должны быть idшники пользователей и список прочитанных статей за отведенный период времени:

      users = pd.read_csv("users_articles.csv")
users.head(3)

      Наверняка данные нужно чистить, используем либо Стемминг (убираем лишние куски слова: побежал -> бежал), либо Лемматизацию для морфологического анализа (перевод слова в неопределенную форму для гл. и в им.падеж для сущ.). Стемминг быстро и очень слабо, поэтому выбираем лемматизацию из библиотеки pymorphy2. razdel для сегментации русскоязычного текста на токены и предложения:

      !pip install razdel pymorphy2
import re
import numpy as np
from gensim.corpora.dictionary import Dictionary
from razdel import tokenize
import pymorphy2

      Для удаления союзов и предлогов:

      import nltk
from nltk.corpus import stopwords
nltk.download('stopwords')
stopword_ru = stopwords.words('russian')
print(len(stopword_ru))
with open('stopwords.txt') as f:
    additional_stopwords = [w.strip() for w in f.readlines() if w]
 
stopword_ru += additional_stopwords
len(stopword_ru)

      Очистка текста и леммитизация:

      def clean_text(text):
    '''
    очистка текста
 
    на выходе очищеный текст
    '''
    if not isinstance(text, str):
        text = str(text)
 
    text = text.lower()
    text = text.strip('n').strip('r').strip('t')
    text = re.sub("-srn|-srn|rn", '', str(text))
 
    text = re.sub("[0-9]|[-—.,:;_%©«»?*!@#№$^•·&()]|[+=]|[[]|[]]|[/]|", '', text)
    text = re.sub(r"rnt|n|s|rt|n", ' ', text)
    text = re.sub(r'[xad]|[s+]', ' ', text.strip())
    text = re.sub('n', ' ', text)
 
    return text
 
cache = {}
morph = pymorphy2.MorphAnalyzer()
 
def lemmatization(text):    
 
    # [0]
    if not isinstance(text, str):
        text = str(text)
 
    # [1]
    tokens = list(tokenize(text))
    words = [_.text for _ in tokens]
 
    words_lem = []
    for w in words:
        if w[0] == '-': # [2]
            w = w[1:]
        if len(w) > 1: # [3]
            if w in cache: # [4]
                words_lem.append(cache[w])
            else: # [5]
                temp_cach = cache[w] = morph.parse(w)[0].normal_form
                words_lem.append(temp_cach)
 
    words_lem_without_stopwords = [i for i in words_lem if not i in stopword_ru] # [6]
    
    return words_lem_without_stopwords
 
news['title'] = news['title'].progress_apply(lambda x: lemmatization(x))

      Далее мы должны обучить нашу модель:

      texts = list(news['title'].values)
 
common_dictionary = Dictionary(texts)
common_corpus = [common_dictionary.doc2bow(text) for text in texts]

      И самое сладкое — обучение второй модели:

      N_topic = 20
 
%%time
from gensim.models import LdaModel
lda = LdaModel(common_corpus, num_topics=N_topic, id2word=common_dictionary)#, passes=10)

from gensim.test.utils import datapath
temp_file = datapath("model.lda")
lda.save(temp_file)
lda = LdaModel.load(temp_file)
 
other_texts = list(news['title'].iloc[:3])
other_corpus = [common_dictionary.doc2bow(text) for text in other_texts]
 
unseen_doc = other_corpus[2]
print(other_texts[2])
lda[unseen_doc]

      И вытаскиваем результат, особенно нужны самые популярные слова по темам:

      x = lda.show_topics(num_topics=N_topic, num_words=7, formatted=False)
topics_words = [(tp[0], [wd[0] for wd in tp[1]]) for tp in x]
 
# Печатаем только слова
for topic, words in topics_words:
    print(f"topic_{topic}: " + " ".join(words))

      И описываем пользователя вектором тем:

      doc_dict = dict(zip(topic_matrix['doc_id'].values, topic_matrix[[f'topic_{i}' for i in range(N_topic)]].values))
 
def get_user_embedding(user_articles_list, doc_dict):
    user_articles_list = eval(user_articles_list)
    user_vector = np.array([doc_dict[doc_id] for doc_id in user_articles_list])
    # print(user_vector)
    user_vector = np.mean(user_vector, 0)  # можно не среднее
    return user_vector

      И получаем финальный результат:

      %%time
user_embeddings = pd.DataFrame([i for i in users['articles'].apply(lambda x: get_user_embedding(x, doc_dict))])
user_embeddings.columns = [f'topic_{i}' for i in range(N_topic)]
user_embeddings['uid'] = users['uid'].values
user_embeddings = user_embeddings[['uid']+[f'topic_{i}' for i in range(N_topic)]]
user_embeddings.head(3)
      Ответить

  4. Аноним

    13.12.2023

    код нерабочий , много ошибок , можете на ноутбук ссылку кинуть?

    Ответить

Оставить комментарий

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.