Дедлайн: 20 марта 23:59
Машинное обучение, ФИВТ, Весна 2018
Оформление дз:
ml.course.mipt@gmail.comML2018_fall <номер_группы> <фамилия>, к примеру -- ML2018_fall 596 ivanovML2018_<фамилия>_<группа>_task<номер задания>.ipnb, к примеру -- ML2018_ivanov_596_task1.ipnbВопросы:
ml.course.mipt@gmail.com (или в телеграм-канал)ML2018_fall Question <Содержание вопроса>Предположим, что мы решаем задачу бинарной классификации и что у нас есть три алгоритма $b_1(x)$, $b_2(x)$ и $b_3(x)$, каждый из которых ошибается с вероятностью p. Мы строим композицию взвешенным голосованием: алгоритмам присвоены значимости $w_1$, $w_2$ и $w_3$, и для вынесения вердикта суммируются значимости алгоритмов, проголосовавших за каждый из классов:
$$a_0 = \sum_{i=1}^3 w_i [b_i(x)=0]$$$$a_1 = \sum_{i=1}^3 w_i [b_i(x)=1]$$Объект $x$ относится к классу, для которого такая сумма оказалась максимальной. Например, если первые два алгоритма голосуют за класс $0$, а третий — за класс $1$, то выбирается класс $0$, если $w_1 + w_2 > w_3$, и класс $1$ в противном случае. Какова вероятность ошибки такой композиции этих трех алгоритмов, если:
Рассмотрим задачу бинарной классификации. Будем считать, что все алгоритмы из базового семейства возвращают ответы из отрезка $[0,1]$, которые можно интерпретировать как вероятности принадлежности объектов классу $1$. В качестве функции потерь возьмем отрицательный логарифм правдоподобия: $$L(y,z) = -(y \log{z}+(1-y)\log{(1-z)})$$ В формуле $y$ - правильный ответ, $z$ - ответ алгоритма. Выпишите формулы для поиска базовых алгоритмов $b_n$ и коэффициентов $\gamma_n$ в градиентном бустинге.
In [2]:
# Ваш ответ здесь
Известно, что на $n$-й итерации двухклассового метода AdaBoost был выбран базовый классификатор, допускающий ошибку только на одном объекте $x_j$. Найдите нормированный вес $w_j^{(n+1)}$ при этом объекте на следующей итерации.
Перепишем форулы со слайдов, подставив в них условия задачи. Считаем, что веса нормируются на каждой итерации. Вычисляем волшебные формулы: $$\text{err}_n = \frac{\sum_{i=1}^{N} w_i [y_i \neq G_n(x_i)]}{\sum_{i=1}^{N} w_i} = \frac{w_j}{\sum_{i=1}^{N} w_i} = w_j;$$ $$ \alpha_n = \log \frac{1 - \text{err}_n }{\text{err}_n } = \log \frac{1 - w_j}{w_j} .$$ Пересчитываем веса: $$ w_j \leftarrow w_j e^{\alpha_n [y_j \neq G_n(x_j)]} = w_j e^{\alpha_n} = w_j \frac{1 - w_j}{w_j} = 1 - w_j; $$ $$ w_i \leftarrow w_i e^{\alpha_n [y_i \neq G_n(x_i)]} = w_i e^0 = w_i, \text{если } i \neq j.$$ Нормируем: $$ w_j \leftarrow \frac{1 - w_j}{\sum_{i=1, i \neq j}^{N} w_i + 1 - w_j} = \frac{1 - w_j}{2 - 2w_j} = 0.5.$$
Необходимо реализовать класс RandomForest (для решения задачи классификации)
Спецификация:
sklearn.BaseEstimator;конструктор содержит следующие параметры:
num_trees - количество деревьев в лесе;max_depth - максимальная глубина дерева (по умолчанию - numpy.inf); max_features - количество признаков, принимаемое к рассмотрению при разбиении (аналогичный параметр есть в sklearn имплементации). Параметр может принимать значения:criterion - критерий разбиения (для классификации - 'gini' или 'entropy', по умолчанию - 'gini'); функции с подсчетом энтропийного и критерия Джини можно взять из предыдущего дз;класс имеет методы fit и predict;
fit принимает матрицу объектов X и вектор ответов y (объекты numpy.ndarray) и возвращает экземпляр класса
RandomForest, представляющий собой Random Forest, обученный по выборке (X, y) с учётом заданных в конструкторе параметров; predict принимает матрицу объектов и возвращает вектор предсказанных ответов;
In [4]:
import numpy as np
def bagging(sample, sample_answers, subsamples_count):
'''
Делаем subsamples_count выборок с повторениями из sample и соответствующих им sample_answers.
'''
subsamples = np.empty([subsamples_count, sample.shape[0], sample.shape[1]])
subsamples_answers = np.empty([subsamples_count, sample_answers.shape[0]])
for i in np.arange(subsamples_count):
subsample_indexes = np.random.choice(sample.shape[0], sample.shape[0], replace=True)
subsample = sample[subsample_indexes]
subsample_answers = sample_answers[subsample_indexes]
subsamples[i] = subsample
subsamples_answers[i] = subsample_answers
return subsamples, subsamples_answers
In [5]:
import sklearn
from sklearn.tree import DecisionTreeClassifier
class RandomForest(sklearn.base.BaseEstimator, sklearn.base.ClassifierMixin):
# Сделал по умолчанию max_depth=None вместо np.inf для совместимости с sklearn.tree.DecisionTreeClassifier
def __init__(self, trees_count, max_features=None, max_depth=None, criterion='gini'):
self.trees_count = trees_count
self.max_features = max_features
self.max_depth = max_depth
self.criterion = criterion
self.trees = np.empty(self.trees_count, dtype=DecisionTreeClassifier)
def fit(self, train_sample, train_sample_answers):
'''
Создает деревья, используя bagging и random subspaces method.
'''
train_subsamples, train_subsamples_answers = bagging(sample, sample_answers, self.trees_count)
for i in np.arange(self.trees_count):
classifier = DecisionTreeClassifier(max_features=self.max_features, max_depth=self.max_depth, criterion=self.criterion)
classifier.fit(train_subsamples[i], train_subsamples_answers[i])
self.trees[i] = classifier
return self
def predict(self, test_sample):
'''
Предсказать класс, используя обученные деревья
'''
test_sample_answers = np.empty([self.trees_count, test_sample.shape[0]], dtype=np.int64)
for i in np.arange(self.trees_count):
test_sample_answers[i] = self.trees[i].predict(test_sample)
# https://stackoverflow.com/a/19202117
bincount = lambda tree_test_sample_answers: np.bincount(tree_test_sample_answers, minlength=4)
bins_by_column = np.apply_along_axis(bincount, 0, test_sample_answers)
classes = bins_by_column.argmax(axis=0)
return classes
Загрузите датасет Wine Data Set (https://archive.ics.uci.edu/ml/datasets/wine). Разделите выборку на обучающую и тестовую с помощью метода train_test_split, используйте значения параметров test_size=0.2, random_state=42. Попробуйте обучить Random Forest на предложенном датасете
In [6]:
import pandas as pd
from sklearn.model_selection import train_test_split
raw_dataframe = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data', header=None)
In [7]:
sample = raw_dataframe.values[:, 1:]
sample_answers = raw_dataframe.values[:, 0]
train_sample, test_sample, train_sample_answers, test_sample_answers = train_test_split(sample, sample_answers,
test_size=0.2,
random_state=42)
In [8]:
classifier = RandomForest(trees_count=10)
classifier.fit(train_sample, train_sample_answers)
print(classifier.predict(test_sample) == test_sample_answers)
Покажите, как менялись значения критерия качества accuracy при увеличении параметра num_trees. Видны ли следы переобучения?
In [9]:
from sklearn.metrics import accuracy_score
# Можно увеличить до 200, ничего не поменяется. Просто не хочется загромождать вывод.
for trees_count in np.arange(1, 40):
classifier = RandomForest(trees_count=trees_count)
classifier.fit(train_sample, train_sample_answers)
print('При {:2} деревьях точность {:.3f}.'.format(trees_count, accuracy_score(classifier.predict(test_sample), test_sample_answers)))
Следы переобучения не видны. :)
Сравните качество работы вашей реализации RandomForest и реализации из sklearn.
In [10]:
from sklearn.ensemble import RandomForestClassifier
for trees_count in np.arange(1, 40):
my_classifier = RandomForest(trees_count=trees_count)
my_classifier.fit(train_sample, train_sample_answers)
their_classifier = RandomForestClassifier(n_estimators=trees_count)
their_classifier.fit(train_sample, train_sample_answers)
print('При {:2} деревьях точность моего составляет {:.3f}, а точность библиотечного — {:.3f}.'\
.format(trees_count,
accuracy_score(my_classifier.predict(test_sample), test_sample_answers),
accuracy_score(their_classifier.predict(test_sample), test_sample_answers)))
Сейчас мой ансамбль оказался лучше, однако это может измениться при использовании прочих параметров.
Измените свою реализацию RandomForest так, чтобы случайное подмножество признаков выбиралось не в каждом сплите, а перед построением всего дерева. Сравните результат работы с обычным RandomForest.
In [11]:
import sklearn
from sklearn.tree import DecisionTreeClassifier
class ModifiedRandomForest(sklearn.base.BaseEstimator, sklearn.base.ClassifierMixin):
# Сделал по умолчанию max_depth=None вместо np.inf для совместимости с sklearn.tree.DecisionTreeClassifier
def __init__(self, trees_count, max_features=None, max_depth=None, criterion='gini'):
self.trees_count = trees_count
self.max_features = max_features
self.max_depth = max_depth
self.criterion = criterion
self.trees = np.empty(self.trees_count, dtype=DecisionTreeClassifier)
self.feature_indexes = np.empty([self.trees_count, self.max_features], dtype=np.int64)
def fit(self, train_sample, train_sample_answers):
'''
Создает деревья, используя bagging и random subspaces method.
'''
raw_train_subsamples, train_subsamples_answers = bagging(sample, sample_answers, self.trees_count)
for i in np.arange(self.trees_count):
if self.max_features is not None:
self.feature_indexes[i] = np.random.choice(raw_train_subsamples.shape[2], self.max_features)
else:
self.feature_indexes[i] = np.arange(raw_train_subsamples.shape[2])
train_subsamples = raw_train_subsamples[:, :, self.feature_indexes[i]]
classifier = DecisionTreeClassifier(max_features=None, max_depth=self.max_depth, criterion=self.criterion)
classifier.fit(train_subsamples[i], train_subsamples_answers[i])
self.trees[i] = classifier
return self
def predict(self, test_sample):
'''
Предсказать класс, используя обученные деревья
'''
test_sample_answers = np.empty([self.trees_count, test_sample.shape[0]], dtype=np.int64)
for i in np.arange(self.trees_count):
test_sample_answers[i] = self.trees[i].predict(test_sample[:, self.feature_indexes[i]])
# https://stackoverflow.com/a/19202117
bincount = lambda tree_test_sample_answers: np.bincount(tree_test_sample_answers, minlength=4)
bins_by_column = np.apply_along_axis(bincount, 0, test_sample_answers)
classes = bins_by_column.argmax(axis=0)
return classes
In [12]:
average_accuracy = 0
average_modified_accuracy = 0
iterations_count = 40
max_trees_count = 40
for i in np.arange(iterations_count):
for trees_count in np.arange(1, max_trees_count):
classifier = RandomForest(trees_count=trees_count, max_features=10)
classifier.fit(train_sample, train_sample_answers)
average_accuracy += accuracy_score(classifier.predict(test_sample), test_sample_answers) / iterations_count / max_trees_count
modified_classifier = ModifiedRandomForest(trees_count=trees_count, max_features=10)
modified_classifier.fit(train_sample, train_sample_answers)
average_modified_accuracy += accuracy_score(modified_classifier.predict(test_sample), test_sample_answers) / iterations_count / max_trees_count
if i == 0:
print('При {:2} деревьях точность моего составляет {:.3f}, а точность модифицированного — {:.3f}.'\
.format(trees_count,
accuracy_score(classifier.predict(test_sample), test_sample_answers),
accuracy_score(modified_classifier.predict(test_sample), test_sample_answers)))
print('В среднем точность обычного леса составляет {:.7f}, а точность модифицированного — {:.7f}.'\
.format(average_accuracy, average_modified_accuracy))
Конечно, сравнение не идеально, так как я усредняя по разному числу деревьев... Может, при других параметрах будет больше разница.