-- coding: utf-8 --

"""Копия блокнота "Regularization (HW).ipynb"

Automatically generated by Colab.

Original file is located at
https://colab.research.google.com/drive/16thpe5RaQJCbOXJJr1G-7r7yuLEvRljP
"""

import numpy as np
from sklearn.datasets import make_regression

"""# Регуляризация

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

Рассмотрим такой пример:

1 x_{0} + 10000 x_{1} + 2 x_{2} = y

Очевидно, что вес $θ_{1}$ оказывает очень сильное влияние на конечный результат, что делает модель нестабильной. И задача регуляризации в линейных моделях – бороться с такими аномально большими значениями весов, уменьшая их. Достигается это путем штрафования функции потерь за большие веса. Рассмотрим три вида регуляризации в линейных моделях.

L1 регуляризация (или Lasso регрессия)

В L1 мы добавляем сумму модулей весов к функции потерь:

L o s s = \frac{1}{m} \sum_{i = 1}^{m} {(y_{i} - {\hat{y}}_{i})}^{2} + α_{1} \sum_{j = 1}^{n} | θ_{j} |

$α$ отвечает за то, насколько сильно регуляризация будет влиять на модель.

Градиент по функции MSE – это вектор частных производных по независимым переменным. Теперь к нему добавился градиент по функции регуляризации:

\nabla (L a s s o M S E) = \nabla (M S E) + α_{1} \nabla (\sum_{j = 1}^{n} | θ_{j} |)

\nabla (L a s s o M S E) = [\begin{matrix} \frac{\partial M S E}{\partial θ_{0}} \\ \frac{\partial M S E}{\partial θ_{1}} \\ ⋮ \\ \frac{\partial M S E}{\partial θ_{n}} \end{matrix}] + α_{1} [\begin{matrix} \frac{\partial L 1}{\partial θ_{0}} \\ \frac{\partial L 1}{\partial θ_{1}} \\ ⋮ \\ \frac{\partial L 1}{\partial θ_{n}} \end{matrix}]

\frac{\partial L 1}{\partial θ_{j}} = \frac{θ_{j}}{| θ_{j} |} = sign (θ_{j})

Соответственно градиент будет таким:

\nabla (L a s s o M S E) = [\begin{matrix} \frac{2}{m} \sum_{i = 1}^{m} ({\hat{y}}_{i} - y_{i}) x_{i 0} \\ \frac{2}{m} \sum_{i = 1}^{m} ({\hat{y}}_{i} - y_{i}) x_{i 1} \\ ⋮ \\ \frac{2}{m} \sum_{i = 1}^{m} ({\hat{y}}_{i} - y_{i}) x_{i n} \end{matrix}] + α_{1} [\begin{matrix} sign (θ_{0}) \\ sign (θ_{1}) \\ ⋮ \\ sign (θ_{n}) \end{matrix}]

sign (θ_{i}) = {\begin{cases} - 1 & if θ_{i} < 0 \\ 0 & if θ_{i} = 0 \\ 1 & if θ_{i} > 0 \end{cases}

или в виде матричного перемножения:

\nabla (L a s s o M S E) = \frac{2}{m} (\hat{Y} - Y) X + α_{1} sign (θ)

где θ – вектор весов.

L2 регуляризация (или Ridge регрессия)

То же самое что и L1, только берется не модуль весов, а квадрат:

L o s s = \frac{1}{m} \sum_{i = 1}^{m} {(y_{i} - {\hat{y}}_{i})}^{2} + α_{2} \sum_{j = 1}^{n} θ_{j}^{2}

А градиент, соответственно, будет таким:

\nabla (R i d g e M S E) = \frac{2}{m} (\hat{Y} - Y) X + α_{2} 2 θ

ElasticNet

Это комбинация регуляризаций L1 и L2:

L o s s = \frac{1}{m} \sum_{i = 1}^{m} {(y_{i} - {\hat{y}}_{i})}^{2} + α_{1} \sum_{j = 1}^{n} | θ_{j} | + α_{2} \sum_{j = 1}^{n} θ_{j}^{2}

Градиент:

\nabla (E l a s t i c N e t M S E) = \frac{2}{m} (\hat{Y} - Y) X + α_{1} sign (θ) + α_{2} 2 θ

Реализация

Добавьте в класс LinReg три параметра:

reg – принимает одно из трех значений: l1, l2, elasticnet. По умолчанию: None.
l1_coef – принимает значение от 0.0 до 1.0. По умолчанию: 0.
l2_coef – принимает значение от 0.0 до 1.0. По умолчанию: 0.

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

Примечания:

Для вычисления регуляризации L1 нужно задать reg="l1" и указать только l1_coef.
Для вычисления регуляризации L2 нужно задать reg="l2" и указать только l2_coef.
Для вычисления регуляризации Elasticnet нужно задать reg="elasticnet" и указать оба параметра l1_coef и l2_coef.

Проверка

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

Пример входных данных:

None

Ожидаемый результат:

474.8503115919559
"""

class LinReg:

Ваш код здесь

"""Тестирование"""

def prepare_data():
X, y = make_regression(n_samples=100, n_features=10, noise=1, random_state=42)
return X, y

def test_lin_reg_regular():
X, y = prepare_data()

expected_scores = [474.8503115919559, 472.01263129842266, 314.3302508642142, 313.08392714109925]

for id, reg_params in enumerate([{"reg": "None"},
{"reg": "l1", "l1_coef":0.5},
{"reg": "l2", "l2_coef":0.5},
{"reg": "elasticnet", "l1_coef":0.5,"l2_coef":0.5}]):
lin_reg = LinReg(n_iter=50, learning_rate=0.1, metric="mse", **reg_params)
lin_reg.fit(X, y)
expected_score = expected_scores[id]
try:
assert np.round(np.sum(lin_reg.get_coef()),10) == np.round(expected_score,10)
except:
print(f"Тест №{id+1} не пройден")
else:
print(f"Тест №{id+1} пройден")

test_lin_reg_regular()

"""# Скорость обучения

До сих пор у нас была статичная скорость обучения. Но это может быть не оптимальным решением. Слишком большое значение чревато тем, что мы либо проскочим минимум, либо вовсе будем отдаляться от него. Слишком малое значение приведет к длительному процессу обучения. Более разумным было бы динамически менять шаг обучения в зависимости от сделанного количества шагов: в начале двигаемся быстро, чтобы ускорить обучение, а в конце замедляемся, чтобы не пропустить минимум.

Реализуем динамический подход мы посредством лямбда-функции. Примерно такой:

lambda iter: 0.5 * (0.85 ** iter),

где iter – это номер текущей итерации градиентного спуска. Можете у себя локально проверить: запустите код в цикле и убедитесь, что чем больше итерация, тем меньше получается возвращаемое значение.

Возьмите код из предыдущего шага и модифицируйте в нем параметр learning_rate следующим образом:

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

Можете дополнительно для контроля вывести значение learning_rate в лог обучения.

Примечания:

Т.к. теперь результат зависит от нумерации шагов, то формализуем их нумерацию: они должна считаться от 1 до n_iter (включительно).

Проверка

Входные данные: три различных значения для скорости обучения, два из которых — динамические.
Выходные данные: коэффициенты обученной линейной регрессии (их сумма).
"""

class LinReg:

Ваш код здесь

"""Тестирование"""

def prepare_data():
X, y = make_regression(n_samples=100, n_features=10, noise=1, random_state=42)
return X, y

def test_lin_reg_lr():
X, y = prepare_data()

expected_scores = [467.5815395326395, 471.88506173264466, 474.7602357788915]

for id, lr_params in enumerate([{"learning_rate" : 0.05},
{"learning_rate" : lambda iter: 0.5 / (1 + 0.5 * iter)},
{"learning_rate" : lambda iter: 0.05 * 0.9 * (np.floor(iter/10))}]):
lin_reg = LinReg(n_iter=50, metric="mse", **lr_params)
lin_reg.fit(X, y)
expected_score = expected_scores[id]
try:
assert np.round(np.sum(lin_reg.get_coef()),10) == np.round(expected_score,10)
except:
print(f"Тест №{id+1} не пройден")
else:
print(f"Тест №{id+1} пройден")

test_lin_reg_lr()

"""# Стохастический градиентный спуск

Это метод оптимизации, используемый в различных алгоритмах машинного обучения. Он призван ускорить и упростить процесс обучения. В реальных задачах обучающая выборка может иметь довольно большой объем. И вычисление градиента функции потерь может потребовать довольно много процессорного времени и других ресурсов компьютера. А это может существенно замедлить обучение модели. Основная идея стохастического градиентного спуска (Stochastic Gradient Descent, SGD) состоит в том, что мы на каждом шаге вычисляем градиент функции потерь не на всей обучающей выборке, а на небольшом её подмножестве.

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

Есть несколько вариаций стохастического градиентного спуска.

Во-первых, выделяют подходы по количеству используемых объектов:

Классический стохастический градиентный спуск предполагает использование на каждом шаге ровно одного образца из выборки.
Мини-пакетный подход (Mini-Batch) – на каждом шаге мы используем пакет из небольшого числа элементов обучающей выборки. Это позволяет уменьшить излишнюю «стохастичность» (случайность) градиентного спуска.

Во-вторых, SGD различаются по способу отбора объектов:

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

В нашей реализации мы задействуем случайный отбор заданного количества элементов.

Реализация

Добавьте в класс LinReg два новых параметра:

sgd_sample – кол-во образцов, которое будет использоваться на каждой итерации обучения. Может принимать либо целые числа, либо дробные от 0.0 до 1.0.
По-умолчанию: None.
random_state – для воспроизводимости результата зафиксируем сид. По-умолчанию: 42.

Внесем изменение в алгоритм обучения:

В начале обучения фиксируем сид.
В начале каждого шага формируется новый мини-пакет, состоящий из случайно выбранных элементов обучающего набора. Кол-во отобранных элементов определяется параметром sgd_sample:
- Если задано целое число, то из исходного датасета берется ровно столько примеров сколько указано.
- Если задано дробное число, то рассматриваем его как долю от количества образцов в исходном датасете (округленное до целого числа).
Расчет градиента (и последующее изменение весов) делаем на основе мини-пакета.
Все остальные параметры, если они заданы (например, регуляризация), также должны учитываться при обучении.
Ошибку и метрику необходимо считать на всем датасете, а не на мини-пакете.
Если sgd_sample = None, то обучение выполняется как раньше (на всех данных).

Случайная генерация

Т.к. у нас формальная проверка кода, то у всех должны получиться одинаковые случайные подвыборки. Поэтому и способ у всех будет одинаковый.

В начале обучения посредством модуля random фиксирум сид:

random.seed(<random_state>)

В начале каждой итерации сформируем порядковые номера строк, которые стоит отобрать:

sample_rows_idx = random.sample(range(X.shape[0]), self.sgd_sample)

или

sample_rows_idx = random.sample(range(X.shape[0]), int(X.shape[0] * self.sgd_sample))

В этом случае при каждом запуске будут генерироваться одни и те же номера объектов. Что позволит нам добиться воспроизводимости.

Проверка

Входные данные: различные значения параметра sgd_sample.
Выходные данные: коэффициенты обученной линейной регрессии (их среднее).
"""

import random

class LinReg:

Ваш код здесь

"""Тестирование"""

def prepare_data():
X, y = make_regression(n_samples=100, n_features=10, noise=1, random_state=42)
return X, y

def test_lin_reg_sgd():
X, y = prepare_data()

expected_scores = [47.48608054738073, 47.48842798505551]

for id, sgd_params in enumerate([{"sgd_sample": 80},
{"sgd_sample":0.75}]):
lin_reg = LinReg(n_iter=50, metric="mse", learning_rate=0.1, random_state=42, **sgd_params)
lin_reg.fit(X, y)
expected_score = expected_scores[id]
try:
assert np.round(np.mean(lin_reg.get_coef()),10) == np.round(expected_score,10)
except:
print(f"Тест №{id+1} не пройден")
else:
print(f"Тест №{id+1} пройден")

test_lin_reg_sgd()