<jupyter_start><jupyter_text>Машинное обучение, МКН СПбГУ Градиентный спуск своими руками. Четвёртое домашнее задание (практическое)  О заданииВ данном задании необходимо реализовать обучение линейной регрессии с помощью различных вариантов градиентного спуска. Оценивание и штрафыКаждая из задач имеет определенную «стоимость» (указана в скобках около задачи). Максимально допустимая оценка за работу — 14 баллов + 2 балла бонус.Сдавать задание после указанного срока сдачи нельзя. При выставлении неполного балла за задание в связи с наличием ошибок на усмотрение проверяющего предусмотрена возможность исправить работу на указанных в ответном сообщении условиях.Задание выполняется самостоятельно. «Похожие» решения считаются плагиатом и все задействованные студенты (в том числе те, у кого списали) не могут получить за него больше 0 баллов. Если вы нашли решение какого-то из заданий (или его часть) в открытом источнике, необходимо указать ссылку на этот источник в отдельном блоке в конце вашей работы (скорее всего вы будете не единственным, кто это нашел, поэтому чтобы исключить подозрение в плагиате, необходима ссылка на источник).Неэффективная реализация кода может негативно отразиться на оценке. Также оценка может быть снижена за плохо читаемый код и плохо считываемые диаграммы.Все ответы должны сопровождаться кодом или комментариями о том, как они были получены. Формат сдачиЗадания сдаются через сайт emkn. Посылка должна содержать:* Ноутбук `HW4_gradient_descent_pr_Username.ipynb`. `Username` — ваша фамилия и имя на латинице именно в таком порядкеДля удобства проверки самостоятельно посчитайте свою максимальную оценку (исходя из набора решенных задач) и укажите ниже:__Оценка:__ Напомним, что на лекциях и семинарах мы разбирали некоторые подходы к оптимизации функционалов по параметрам. В частности, был рассмотрен градиентный спуск и различные подходы к его реализации — стохастический и другие. В качестве модели у нас будет выступать линейная регрессия.В этом домашнем задании вам предстоит реализовать 4 различных вариации градиентного спуска, написать свою реализацию линейной регресии, сравнить методы градиентного спуска между собой на реальных данных и разобраться как подбирать гиперпараметры для этих методов.  Задание 1. Реализация градиентного спуска (4 балла) В этом задании вам предстоит написать собственные реализации различных подходов к градиентному спуску с опорой на подготовленные шаблоны в файле  `utils.py`:**Задание 1.1. (1 балл)** Полный градиентный спуск **GradientDescent**:$$    w_{k + 1} = w_{k} - \eta_{k} \nabla_{w} Q(w_{k})$$**Задание 1.2. (1 балл)** Стохастический градиентный спуск **StochasticDescent**:$$    w_{k + 1} = w_{k} - \eta_{k} \nabla_{w} q_{i_{k}}(w_{k})$$ $\nabla_{w} q_{i_{k}}(w_{k}) \,$ — это оценка градиента по батчу объектов, выбранных случайно.**Задание 1.3. (1 балл)** Метод Momentum **MomentumDescent**:$$    h_0 = 0, \\    h_{k + 1} = \alpha h_{k} + \eta_k \nabla_{w} Q(w_{k}), \\    w_{k + 1} = w_{k} - h_{k + 1}$$**Задание 1.4. (1 балл)** Метод Adaptive gradient algorithm **Adagrad**:$$    G_0 = 0, \\    G_{k + 1} = G_{k} + \left(\nabla_{w} Q(w_{k})\right) ^ 2, \\    w_{k + 1} = w_{k} - \dfrac{\eta_k}{\sqrt{\varepsilon + G_{k + 1}}} \nabla_{w} Q(w_{k}) \\    $$Обратите внимание, что здесь $G_{k}$ не число, а вектор. Во всех вышеназванных методах мы будем использовать следующую формулу для длины шага:$$    \eta_{k} = \lambda \left(\dfrac{s_0}{s_0 + k}\right)^p$$На практике достаточно настроить параметр $\lambda$, а остальным выставить параметры по умолчанию: $s_0 = 1, \, p = 0.5.$ Мы будем использовать функцию потерь MSE:$$    Q(w) = \dfrac{1}{\ell} \sum\limits_{i=1}^{\ell} (a_w(x_i) - y_i)^2$$Все вычисления должны быть векторизованы.  Задание 2. Реализация линейной регресии (2 балла) В этом задании вам предстоит написать свою реализацию линейной регресии, обучаемой с использованием градиентного спуска, с опорой на подготовленные шаблоны в файле `utils.py` — **LinearRegression**.Необходимо соблюдать следующие условия:* Все вычисления должны быть векторизованы.* Циклы средствами `python` допускаются только для итераций градиентного спуска.* В качестве критерия останова необходимо использовать (одновременно):    * Квадрат евклидовой нормы разности весов на двух соседних итерациях меньше `tolerance`    * Достижение максимального числа итераций `max_iter`* Чтобы проследить за сходимостью оптимизационного процесса будем использовать список `loss_history`, в котором будем хранить значения функции потерь до каждого шага, начиная с нулевого (до первого шага по антиградиенту)* Инициализировать веса нужно нулевым вектором или из нормального $\mathcal{N}(0, 1)$ распределения (тогда нужно зафиксировать seed)  Задание 3. Проверка кода<jupyter_code>%load_ext autoreload
%autoreload 2

import numpy as np

from utils import (
    Adagrad,
    GradientDescent,
    MomentumDescent,
    StochasticDescent,
)
from utils import LinearRegression
num_objects = 100
dimension = 5

X = np.random.rand(num_objects, dimension)
y = np.random.rand(num_objects)

lambda_ = 1e-2
w0 = np.zeros(dimension)

max_iter = 10
tolerance = 0
# GradientDescent

descent = GradientDescent(lambda_ = lambda_, w0 = w0)

gradient = descent.calc_gradient(X, y)

assert gradient.shape[0] == dimension, 'Gradient failed'

diff = descent.step(X, y, 0)

assert diff.shape[0] == dimension, 'Weights failed'
# StochasticDescent

descent = StochasticDescent(lambda_ = lambda_, w0 = w0)

gradient = descent.calc_gradient(X, y)

assert gradient.shape[0] == dimension, 'Gradient failed'

diff = descent.step(X, y, 0)

assert diff.shape[0] == dimension, 'Weights failed'
# MomentumDescent

descent = MomentumDescent(lambda_ = lambda_, w0 = w0)

gradient = descent.calc_gradient(X, y)

assert gradient.shape[0] == dimension, 'Gradient failed'

diff = descent.step(X, y, 0)

assert diff.shape[0] == dimension, 'Weights failed'
# Adagrad

descent = Adagrad(lambda_ = lambda_, w0 = w0)

gradient = descent.calc_gradient(X, y)

assert gradient.shape[0] == dimension, 'Gradient failed'

diff = descent.step(X, y, 0)

assert diff.shape[0] == dimension, 'Weights failed'
# LinearRegression

regression = LinearRegression(
    descent = StochasticDescent(lambda_ = lambda_, w0 = w0, batch_size = 2),
    tolerance = tolerance,
    max_iter = max_iter
)
print(lambda_)
print(w0.shape)
print(X.shape)
print(y.shape)
regression.fit(X, y)

assert len(regression.loss_history) == max_iter, 'Loss history failed'

prediction = regression.predict(X)

assert prediction.shape[0] == num_objects, 'Predict failed'<jupyter_output>0.01
(5,)
(100, 5)
(100,)<jupyter_text>Если ваше решение прошло все тесты локально, то теперь осталось протестировать его в Яндекс.Контесте — **https://contest.yandex.ru/contest/28888/**.Для каждой задачи из контеста вставьте ссылку на успешную посылку:* **GradientDescent**: * **StochasticDescent**:* **MomentumDescent**:* **Adagrad**:* **LinearRegression**:  Задание 4. Работа с данными (2 балла) Мы будем использовать датасет объявлений по продаже машин на немецком Ebay. В задаче предсказания целевой переменной для нас будет являться цена.Для дальнейшей работы сделайте следующее:* Проведите разумную предобработку данных* Замените целевую переменную на её логарифм* Разделите данные на обучающую, валидационную и тестовую выборки в отношении 3:1:1<jupyter_code>### YOUR CODE:<jupyter_output><empty_output><jupyter_text>Задание 5. Сравнение методов градиентного спуска (3 балла) В этом задании вам предстоит сравнить методы градиентного спуска на подготовленных вами данных из предыдущего задания.* **Задание 5.1. (2 балла)** Подберите по валидационной выборке наилучшую длину $\lambda$ шага для каждого метода. Для этого можно сделать перебор по логарифмической сетке, так как нас интересует скорее порядок величины, нежели её точное значение. Сравните качество методов по метрикам MSE и $R^2$ на обучающей и тестовой выборках, сравните количество итераций до сходимости. Все параметры кроме $\lambda$ стоит выставить равным значениям по умолчанию.* **Задание 5.2. (1 балл)** Постройте график зависимости значения функции ошибки от номера итерации (все методы на одном графике).Посмотрите на получившиеся результаты. Сравните методы между собой.<jupyter_code>w0 = np.zeros(x_train.shape[1])

### YOUR CODE:<jupyter_output><empty_output><jupyter_text>Задание 6. Сходимость стохастического градиентного спуска в зависимости от размера батча (1 балл) В этом задании вам предстоит исследовать влияние размера батча на работу стохастического градиентного спуска. * Сделайте по несколько запусков (например, k) стохастического градиентного спуска на обучающей выборке для каждого размера батча из списка. Замерьте время и количество итераций до сходимости. Посчитайте среднее и дисперсию этих значений для каждого размера батча.* Постройте график зависимости количества шагов до сходимости от размера батча.* Постройте график зависимости времени до сходимости от размера батча.Посмотрите на получившиеся результаты. Какие выводы можно сделать про подбор размера батча для стохастического градиентного спуска?<jupyter_code>batch_sizes = np.arange(5, 500, 10)

# YOUR CODE:<jupyter_output><empty_output><jupyter_text>Задание 7. Регуляризация (2 балла) В этом задании вам предстоит исследовать влияние регуляризации на работу различных методов градиентного спуска. (Напомним, регуляризация — это добавка к функции потерь, которая штрафует за норму весов). Мы будем использовать l2 регуляризацию, таким образом функция потерь приобретает следующий вид:$$    Q(w) = \dfrac{1}{\ell} \sum\limits_{i=1}^{\ell} (a_w(x_i) - y_i)^2 + \dfrac{\mu}{2} \| w \|^2$$ Допишите классы **GradientDescentReg**, **StochasticDescentReg**, **MomentumDescentReg**, **AdagradReg** в файле `utils.py`. Мы будем использовать тот же самый класс для линейной регрессии, так как для сравнения методов с регуляризацией и без неё нам нужна только MSE часть функции потерь. Найдите по валидационной выборке лучшие параметры обучения с регуляризацией. Сравните для каждого метода результаты на тестовой выборке по метрикам MSE и $R^2$ с регуляризацией и без регуляризации. Постройте для каждого метода график со значениями функции потерь MSE с регуляризацией и без регуляризации. Посмотрите на получившиеся результаты. Какие можно сделать выводы, как регуляризация влияет на сходимость? Чем вы можете объяснить это?<jupyter_code>%autoreload 2

from utils import (
    AdagradReg,
    GradientDescentReg,
    MomentumDescentReg,
    StochasticDescentReg,
)

# YOUR CODE:<jupyter_output><empty_output><jupyter_text>Задание 8. Бонус — Реализация метода SAG (2 балла) В качестве бонуса вам будет следующее задание — напишите собственную реализацию стохастического градиентного спуска по методу SAG в файле `utils.py`. Подробнее прочитать про SAG можно [здесь](https://arxiv.org/pdf/1309.2388.pdf). Сравните свою реализацию метода SAG с обычным полным градиентным спуском на наших данных. Проведите сравнение аналогично заданию 5. Что вы можете сказать про сходимость этого метода?<jupyter_code># YOUR CODE:<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08491418247515808, 'fraction_numerical': 0.013008130081300813, 'mean_word_length': 5.605608591885441, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 24, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '119647', 'license': 'MIT', 'n_tokens_mistral': 4454, 'n_tokens_neox': 5115, 'n_words': 1261, 'path': '2021-fall-part-1/hws/HW4_gradient_descent_pr/HW4_gradient_descent_pr.ipynb', 'repo_name': 'bagrorg/ml-course', 'size': '11070'}