<jupyter_start><jupyter_text>SLIDE (2) Производные для регрессии Окей, в лекции было очень много страшных формул, теперь можно осознать зачем это нужно.Пусть мы хотим бустить регрессию со стандартной функцией потерь $MSE$:$$\mathcal{L}(a, x,y) = (a(x_i) - y_i)^2$$Необходимо найти через взятие производных:1. Константный вектор $[f_0]_{i=1}^{N}$$$f_0(x) = \arg\min_{ c\in \mathbb{R}} \sum_{i=1}^n \mathcal{L}(c, y_i)$$ 2. Градиенты функции потерь$$g_{i}^{t} = -\Big[\frac{\partial \mathcal{L}(f_t, x_i, y_i)}{\partial f_t(x_i)}\Big]_{i=1}^N$$3. Коэффициенты при композиции $$\alpha_{t + 1} = \arg\min_\alpha \sum_{i=1}^N \mathcal{L}(f_{t}(x_i) + \alpha b_{t+1}(x_i), y_i)$$ Sample 1 Input:```pythony = np.array([1, 2, 3])f = np.array([2, 2, 2])b = np.array([0, 2, 4])``` Output:```pythonf_0 = 2.0g = [-2  0  2] alpha = -0.2```  TASK<jupyter_code>def init(y_i: np.array) -> float:
    n = len(y_i)
    f_0 = y_i.sum() / n
    return f_0

def grad(a: np.array, y: np.array) -> np.array:
    g = -2*(a - y)
    return g

def alpha(f :np.array, b: np.array, y: np.array) -> float:
    alpha = (b*(f-y)).sum() / (b**2).sum()
    return alpha<jupyter_output><empty_output><jupyter_text>TESTS<jupyter_code>y = np.array([1, 2, 3])
f = np.array([2, 2, 2])
b = np.array([0, 2, 4])

f_0 = init(y)
g = grad(f,y)
al = alpha(f,b,y)


assert np.abs(f_0 - 2.0)   < 1e-9
assert_array_almost_equal(g, np.array([-2, 0, 2]))
assert np.abs(al - (-0.2)) < 1e-9
######################################################
y = np.arange(20)
f = np.ones(20) * 10
b = np.arange(20) - 1

f_0 = init(y)
g = grad(f,y)
al = alpha(f,b,y)


assert np.abs(f_0 - 9.5)   < 1e-2
assert_array_almost_equal(g, np.arange(-20,20, 2))
assert np.abs(al - (-0.2748)) < 1e-2
print('Well Done!')<jupyter_output>-0.2
-0.27488151658767773
Well Done!<jupyter_text>SLIDE (2) GradientBoosting Реализуйте градиентный бустинг на решающих деревьях для регрессии с логгированием.Верните модель, которая будет хранить в себе `n_estimatos` обученных деревьев и коэффициенты, чтобы с их помощью потом найти результат предсказания.Также необходимо реализовать логгирование в течение обучения.* `self.estimators` - лист c деревьями* `self.alpha` - лист с коэффициентами альфа* `self.f_list` - лист со значениями комбинаций алгоритма $f_T(x_i) = f_0(x_i) + \sum_{t=1}^{T}\alpha_tb_t(x_i)$* `self.g_list` - лист с векторами градиентов на каждой итерации $g_{i}^{t} = -\Big[\frac{\partial \mathcal{L}(f_t, x_i, y_i)}{\partial f_t(x_i)}\Big]_{i=1}^N$* `self.b_list` - лист со значениями базового обучаемого дерева на тренировачной выборке на каждой итерации Примечания:* Обрывать алгоритм не нужно, необходимо обучить все деревья.* Начальный константный вектор из $f_0$ логгировать не нужно, однако не забудьте его добавить в `predict` c нужным количеством объектов! Sample 1 Input:```pythonn_estimators = 2max_depth=3X_train = np.array([[0], [1], [2], [3], [4]])y_train = np.array([0, 2, 4, 2, 0])X_test  = np.array([[1.2], [2.3]])y_test  = np.array([2.2, 3.7])``` Output:```pythony_test_pred = [2, 4]model.f_list = [array([0.0, 2.0, 3.0, 3.0, 0.0]),                 array([0.0, 2.0, 4.0, 2.0, 0.0])]model.g_list = [array([-3.2,  0.8, 4.8, 0.8, -3.2]),                 array([ 0.0,  0.0, 2.0,-2.0,  0.0])]model.b_list = [array([-3.2, 0.8, 2.8,  2.8, -3.2]),                 array([ 0.0, 0.0, 2.0, -2.0,  0.0])]```  TASK<jupyter_code>import numpy as np
from sklearn.tree import DecisionTreeRegressor as DTR, DecisionTreeClassifier as DTC
from sklearn.metrics import mean_squared_error

class MyGradBoost():
    def __init__(self, n_estimators=10, max_depth=3):
        self.n_estimators = n_estimators
        self.max_depth = max_depth
        self.estimators_ = np.array([DTR(max_depth=self.max_depth) for _ in range(n_estimators)])
        self.alpha = []
        self.f_list = []
        self.b_list = []
        self.g_list = []
        self.f_0_ = None
        
    def init(self, y_i: np.array) -> np.array:
        n = len(y_i)
        f_0 = y_i.sum() / n
        return f_0

    def grad(self, a: np.array, y: np.array) -> np.array:
        g = -2*(a - y)
        return g

    def alpha_f(self, f :np.array, b: np.array, y: np.array) -> float:
        alph = (b*(f-y)).sum() / (b**2).sum()
        return alph
        
    def fit(self, X_train: np.array, y_train: np.array):
        self.f_0_ = self.init(y_train)
        f_0 = np.array([self.f_0_ for _ in range(len(y_train))])
        for i in range(self.n_estimators):
            est = self.estimators_[i]
            if i == 0:
                f = f_0
            else:
                f = self.f_list[i-1]
                
            g = self.grad(f, y_train)
            self.g_list.append(g)
            
            est.fit(X_train, g)
            
            b_predict = est.predict(X_train)
            self.b_list.append(b_predict)
            
            alph = self.alpha_f(f, b_predict, y_train)
            self.alpha.append(alph)
            
            new_f = f - alph * b_predict
            self.f_list.append(new_f)
            
        return self
        
    def predict(self, X_test) -> np.array:
        alpha_sum = sum(self.alpha)
        self.alpha /= alpha_sum
        y_pred = np.array([self.f_0_ for _ in range(len(X_test))])
        for i in range(self.n_estimators):
            current_est = self.estimators_[i]
            y_pred += self.alpha[i] * current_est.predict(X_test)
        return y_pred
    
    def score(self, X_test, y_test)-> np.array:
        predict = self.predict(X_test)
        model_score = mean_squared_error(predict, y_test)
        print('model score ', model_score)
        return model_score<jupyter_output><empty_output><jupyter_text>TESTS<jupyter_code>n_estimators = 2
max_depth=3
X_train = np.array([[0], [1], [2], [3], [4]])
y_train = np.array([0, 2, 4, 2, 0])
X_test  = np.array([[1.2], [2.3]])
y_test  = np.array([2.2, 3.7])

model = MyGradBoost(n_estimators=n_estimators, max_depth=max_depth).fit(X_train, y_train)
assert model.score(X_test, y_test) < 0.2
######################################################
n_train, n_test, noise = 150, 1000, 0.1
# Generate data
def f(x):
    x = x.ravel()
    return np.exp(-x ** 2) + 1.5 * np.exp(-(x - 2) ** 2)

def generate(n_samples, noise):
    X = np.random.rand(n_samples) * 10 - 5
    X = np.sort(X).ravel()
    y = np.exp(-X ** 2) + 1.5 * np.exp(-(X - 2) ** 2)\
        + np.random.normal(0.0, noise, n_samples)
    X = X.reshape((n_samples, 1))

    return X, y

X_train, y_train = generate(n_samples=n_train, noise=noise)
X_test, y_test = generate(n_samples=n_test, noise=noise)


model = MyGradBoost().fit(X_train, y_train)

assert model.score(X_test, y_test) < 0.02


model = MyGradBoost(n_estimators=100, 
                    max_depth=1).fit(X_train, y_train)

assert model.score(X_test, y_test) < 0.017
print('Well Done')<jupyter_output>model score  0.06500000000000003
model score  0.18553243959029522<jupyter_text>Useful Graphs<jupyter_code>def predict_and_plot(model, X_test, y_test, title):
    y_predict = model.predict(X_test)

    plt.plot(X_test, f(X_test), "b")
    plt.scatter(X_train, y_train, c="b", s=20)
    plt.plot(X_test, y_predict, "g", lw=2)
    plt.xlim([-5, 5])
    plt.title("{} Loss: {:2f}".format(title, model.score(X_test, y_test)))
    plt.grid()


n_train, n_test, noise = 150, 1000, 0.1
# Generate data
def f(x):
    x = x.ravel()
    return np.exp(-x ** 2) + 1.5 * np.exp(-(x - 2) ** 2)

def generate(n_samples, noise):
    X = np.random.rand(n_samples) * 10 - 5
    X = np.sort(X).ravel()
    y = np.exp(-X ** 2) + 1.5 * np.exp(-(X - 2) ** 2)\
        + np.random.normal(0.0, noise, n_samples)
    X = X.reshape((n_samples, 1))

    return X, y

X_train, y_train = generate(n_samples=n_train, noise=noise)
X_test, y_test = generate(n_samples=n_test, noise=noise)

model = MyGradBoost(n_estimators=30, 
                    max_depth=1).fit(X_train, y_train)

ind =  [1,3,5,10,15,30]

# GradientBoostingRegressor
plt.plot(X_test, f(X_test), "b")
plt.scatter(X_train, y_train, c="b", s=20)
n_est = [1,3,5,10,15,30]
f = np.array(model.f_list)
for i, n in enumerate(n_est):
    colors = ['g', 'r', 'c', 'm', 'y', 'k']
    plt.plot(X_train, f[n-1], color=colors[i], label="tree count={}".format(n))

plt.xlim([-5, 5])   
plt.legend()
plt.grid()
plt.show()<jupyter_output><empty_output><jupyter_text>SLIDE (2) AdaBoost step Реализуйте одну итерацию алгоритма AdaBoost:1. Обучите дерево $b$ на $X_{train}$ и верните $y_{pred}$2. Найдите среднюю взвешанную ошибку$$error = Q(b_t, X, y) = \frac{1}{N}\sum_{i=1}^{N}w_i^{(t-1)}[y_i \neq b_t(x)]$$3. Найдите коэффициент $\alpha$ (для корректного выполнения добавим $eps$)$$\alpha = \frac{1}{2}\ln\Big(\frac{1-error + eps}{error + eps}\Big)$$4. Найдите новые веса:$$w_i^{new} = w_iexp\Big(-\alpha y_i b(x_i)\Big)$$$$\tilde{w}_i^{new} = \frac{w_i^{new}}{\sum_{i=1}^{N}w_i^{new}}$$ Sample 1 Input:```pythonX_train = np.array([[0, 0], [4, 0], [0, 4], [4, 4]])y_train = np.array([-1, -1, -1, 1])``` Output:```pythony_pred =  [-1 -1 -1 -1] error = 0.056 alpha = 1.417 new_weights = [0.05882403 0.41176819 0.02941201 0.49999576]```<jupyter_code>import math

def boost_step(estimator, weights, X_train, y_train, eps = 1e-6):
    n = len(X_train)
    estimator.fit(X_train, y_train)
    y_pred = estimator.predict(X_train)
    error = 0
    for i in range(n):
        if (y_train[i] != y_pred[i]):
            error += weights[i] 
    error /= sum(weights)
    alpha = math.log((1 - error + eps)/(error+eps)) / 2
    new_weights = []
    for i in range(n):
        new_weight = weights[i]*math.e**(-alpha*y_train[i]*y_pred[i])
        new_weights.append(new_weight)
    new_weights_sum = sum(new_weights)
    for i in range(n):
        new_weights[i] /= new_weights_sum
    return y_pred, error, alpha, new_weights<jupyter_output><empty_output><jupyter_text>TESTS<jupyter_code>######################################################
X_train = np.array([[0, 0], [4, 0], [0, 4], [4, 4]])
y_train = np.array([-1, -1, -1, 1])

estimator = DTC(max_depth=1, random_state=4)
sample_weights = [0.1, 0.7, 0.05, 0.05]
y_pred, error, alpha, new_weights = boost_step(estimator, sample_weights, X_train, y_train)
assert_array_almost_equal(y_pred, np.array([-1, -1, -1, -1])) 
assert np.abs(error - 0.056) < 1e-2 
assert np.abs(alpha - 1.417) < 1e-2 
assert_array_almost_equal(new_weights, np.array([0.05882403, 0.41176819, 0.02941201, 0.49999576]))
######################################################
X_train = np.array([[0, 0], [3, 3], [5, 5], [10, 10]])
y_train = np.array([-1, -1, 1, 1])
estimator = DTC(max_depth=1, random_state=6)
sample_weights = [0.1, 0.7, 0.05, 0.05]

y_pred, error, alpha, new_weights = boost_step(estimator, sample_weights, X_train, y_train)


assert_array_almost_equal(y_pred, np.array([-1, -1, 1, 1])) 
assert np.abs(error - 0.0) < 1e-2 
assert np.abs(alpha - 6.907) < 1e-2 
assert_array_almost_equal(new_weights, np.array([0.11111111, 0.77777778, 0.05555556, 0.05555556]))

print('Well Done!')<jupyter_output>Well Done!<jupyter_text>SLIDE (2) AdaBoost classifier Реализуйте AdaBoost для бинарной классификации на деревьях высоты 1. Верните модель, которая будет хранить в себе `n_estimatos` обученных деревьев и коэффициенты, чтобы с их помощью потом найти результат предсказания.Также необходимо реализовать логгирование в течение обучения.* `self.sample_weights_list` - лист с весами объектов на каждой итерации* `self.y_pred_list` - лист с предсказанием каждого следующего дерева (не комбинации)* `self.error_list` - лист с ошибкамиПримечания:* Обрывать алгоритм не нужно, необходимо обучить все деревья.* Начальные веса логгировать не нужно* `predict_proba` реализовывать не нужно Sample 1 Input:```pythonn_estimators = 2X_train = np.array([[0, 0], [4, 0], [0, 4], [4, 4]])y_train = np.array([-1, -1, -1, 1])X_test  = np.array([[1, 0], [5, 5]])y_test  = np.array([-1, 1])``` Output:```pythony_test_pred = [0, 1]model.sample_weight = [array([0.167, 0.167, 0.167, 0.5]),                        array([ 0.1,  0.5,  0.1, 0.3])]model.y_pred = [array([-1, -1, -1, -1]),                array([-1,  1, -1,  1])]model.alpha = [0.25, 0.167]```  TASK<jupyter_code>import numpy as np
from sklearn.tree import DecisionTreeClassifier as DTC

class MyAdaBoost():
    def __init__(self, n_estimators=10):
        self.estimators_ = np.array([DTC(max_depth=1) for _ in range(n_estimators)])
        self.alpha = []
        self.sample_weights_list = []
        self.y_pred_list = []
        self.error_list = []
        self.eps = 1e-6
        
    def fit(self, X_train: np.array, y_train: np.array):
        n = len(X_train)
        weights = np.array([1/n for _ in range(n)])
        
        for i in range(len(self.estimators_)):
            est = self.estimators_[i]
            est.fit(X_train, y_train, weights)
            y_pred = est.predict(X_train)
            self.y_pred_list.append(y_pred)
            
            error = 0
            for j in range(n):
                if (y_train[j] != y_pred[j]):
                    error += weights[j] 
            error /= sum(weights)
            self.error_list.append(error)
            
            alpha = math.log((1 - error + self.eps)/(error+self.eps)) / 2
            self.alpha.append(alpha)
            
            new_weights = []
            for j in range(n):
                new_weight = weights[j]*math.e**(-alpha*y_train[j]*y_pred[j])
                new_weights.append(new_weight)
                
            new_weights_sum = sum(new_weights)
            
            for j in range(n):
                new_weights[j] /= new_weights_sum
                
            self.sample_weights_list.append(new_weights)
            weights = new_weights
            
        return self
        
    def predict(self, X_test) -> np.array:
        pred = None
        for i in range(len(self.estimators_)):
            est = self.estimators_[i]
            alpha = self.alpha[i]
            current = est.predict(X_test) * alpha
            if (pred is None):
                pred = current
            else:
                pred += current
        result = []
        for elem in pred:
            if (elem > 0):
                result.append(1)
            elif (elem < 0):
                result.append(-1)
            else:
                result.append(0)
        return result<jupyter_output><empty_output><jupyter_text>TESTS<jupyter_code>######################################################
X_train = np.array([[0, 0], [4, 0], [0, 4], [4, 4]])
y_train = np.array([-1, -1, -1, 1])
X_test  = np.array([[1, 0], [5, 5]])
y_test  = np.array([-1, 1])

model = MyAdaBoost(n_estimators = 2).fit(X_train, y_train)

y_pred_my = model.predict(X_test)

assert_array_almost_equal(y_pred_my, np.array([-1, 1]))

######################################################
X_train = np.array([[0, 0], [4, 4], [5, 5], [10, 10]])
y_train = np.array([-1, -1, 1, 1])
X_test  = np.array([[3, 3], [6, 6]])
y_test  = np.array([-1, 1])

model = MyAdaBoost(n_estimators = 2).fit(X_train, y_train)

y_pred_my = model.predict(X_test)

assert_array_almost_equal(y_pred_my, np.array([-1, 1]))
######################################################
num_samples = 1000
theta = np.linspace(0, 2*np.pi, num_samples)
r1 = 1
r2 = 2

rng = np.random.RandomState(1)

circle = np.hstack([np.cos(theta).reshape((-1, 1)) + (rng.randn(num_samples)[:,np.newaxis] / 8), 
                    np.sin(theta).reshape((-1, 1)) + (rng.randn(num_samples)[:,np.newaxis] / 8)])
lil = r1 * circle
big = r2 * circle
X = np.vstack([lil, big])
y = np.hstack([(-1) * np.ones(num_samples), np.ones(num_samples)])




X_train, X_test, y_train, y_test = train_test_split(X, y,
                                                    test_size=0.3,
                                                    random_state=123,
                                                    shuffle=True)

y_test = y_test.astype('int')


y_pred_my = MyAdaBoost(n_estimators = 20).fit(X_train, y_train).predict(X_test)

assert accuracy_score(y_pred_my, y_test) > 0.95
print('Well Done!')<jupyter_output>weights  [[0.16666688888829628, 0.16666688888829628, 0.16666688888829628, 0.49999933333511115], [0.10000039999871999, 0.10000039999871999, 0.4999988000063999, 0.30000039999616007]]
error  [0.25, 0.16666688888829628]
pred  [array([-1, -1, -1, -1]), array([-1, -1,  1,  1])]
alpha  [0.5493048110042772, 0.8047157562324102]
weights  [[0.25, 0.25, 0.25, 0.25], [0.25, 0.25, 0.25, 0.25]]
error  [0.0, 0.0]
pred  [array([-1, -1,  1,  1]), array([-1, -1,  1,  1])]
alpha  [6.907755778981887, 6.907755778981887]
weights  [[0.0005434786399251412, 0.0005434786399251412, 0.0005434786399251412, 0.0005434786399251412, 0.0005434786399251412, 0.0010416659401435058, 0.0005434786399251412, 0.0005434786399251412, 0.0010416659401435058, 0.0010416659401435058, 0.0010416659401435058, 0.0005434786399251412, 0.0005434786399251412, 0.0005434786399251412, 0.0005434786399251412, 0.0005434786399251412, 0.0010416659401435058, 0.0010416659401435058, 0.0005434786399251412, 0.0005434786399251412, 0.0010416659401435058, 0.[...]<jupyter_text>Useful graph При корректной реализации логирования теперь можно посмотреть на ход обучения в картинках<jupyter_code>#Toy Dataset
x1 = np.array([.1,.2,.4,.8, .8, .05,.08,.12,.33,.55,.66,.77,.88,.2,.3,.4,.5,.6,.25,.3,.5,.7,.6])
x2 = np.array([.2,.65,.7,.6, .3,.1,.4,.66,.77,.65,.68,.55,.44,.1,.3,.4,.3,.15,.15,.5,.55,.2,.4])
y = np.array([1,1,1,1,1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1])
X = np.vstack((x1,x2)).T


boost = MyAdaBoost(n_estimators = 20).fit(X, y)
sample_weight_list = np.array(boost.sample_weight_list)
estimator_list = np.array(boost.estimators_)
alpha = np.array(boost.alpha)
fig = plt.figure(figsize = (14,14))
for m in range(0,9):
    fig.add_subplot(3,3,m+1)
    s_weights = (sample_weight_list[m,:] / sample_weight_list[m,:].sum() ) * 40
    plot_decision_boundary(estimator_list[m], X, y, N = 50, scatter_weights =s_weights )
    plt.title('Estimator decision boundary, m = {}'.format(m))
print('Well Done!')
plot_AdaBoost_scratch_boundary(estimator_list, alpha, X, y, N = 50 )<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.18740348555040812, 'fraction_numerical': 0.08498786675490845, 'mean_word_length': 3.1136569872958257, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 48, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 3, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '124495', 'license': 'MIT', 'n_tokens_mistral': 8378, 'n_tokens_neox': 7652, 'n_words': 1457, 'path': '09-BoostingTheory/HomeBoost.ipynb', 'repo_name': 'PetrovaDaria/mlmathmech', 'size': '18132'}