Задание выполнил(а): (впишите свои фамилию и имя)
Внимание! Домашнее задание выполняется самостоятельно. При попытке сдать хотя бы частично списанный текст, или текст, полученный в результате совместного решения задач, вся работа будет оценена на 0 баллов. Мы также уведомим администрацию факультета и попросим применить дисциплинарное взыскание (предупреждение, выговор, отчисление) ко всем вовлеченным студентам.
Рассмотрим следующую модель. Значения $x_1, \ldots, x_n \in \mathbb R^d$ фиксированы. Вектор $w \in \mathbb R^d$ фиксирован. Также фиксирован вектор $\sigma = (\sigma_1, \ldots, \sigma_n) \in \mathbb R^n$. Значения $y_i$ определяются следующим образом:
$$\newcommand{\eps}{\varepsilon}y_i = \langle w, x_i \rangle + \eps_i,$$где $\eps_i$ — независимые случайные величины, распределённые по нормальному закону, $\eps_i \sim \mathcal N(0, \sigma_i^2)$ (то есть у каждого $\eps_i$ своя дисперсия, равная $\sigma_i^2$, все $\sigma_i$ фиксированы и известны).
Подсказка. Для самопроверки можеет подставить в качестве вектора $\sigma$ постоянный вектор (все компоненты равны одному и тому же числу). Должны получиться формулы, которые доказывались на лекциях.
(впишите решение сюда)
Рассмотрим такую модель. Значения $x_1, \ldots, x_n \in \mathbb R$ — фиксированные числа, $\beta \in \mathbb R$ — фиксированное число, $\eps_i \sim \mathcal N(0, 1)$ — независимые случайные ошибки,
$$y_i = \beta x_i + \eps_i, \quad i = 1, \ldots, n.$$Пусть $\widehat \beta$ — МНК-оценка $\beta$ для данной модели. Для предсказания значения $y$ в точке $x_{new}$ используется следующий алгоритм:
$$\widehat y_{new} = \gamma \cdot \widehat \beta x_{new},$$где $\gamma \in \mathbb R$ — некоторая константа (не зависящая от $x_1, \ldots, x_n$ и $y_1, \ldots, y_n$).
(Эта задача демонстрирует ещё одно проявление bias-variance tradeoff: мы можем пожертвовать несмещённостью, чтобы уменьшить ошибку предсказания.)
(впишите решение сюда)
Гарри Поттер хочет найти философский камень, расположенный в точке минимума функции $f(x_1, x_2)=x_1^2 + x_2^2$. В момент времени 0 он стартует из точки $x^{(0)}=(2, 2)$. На $i$-й минуте Гарри мгновенно перемещается (аппарирует) из точки $x^{(i)}$ в точку
$$x^{(i+1)} = x^{(i)} - \eta \nabla f(x^{(i)}),$$где $\nabla f(x^{(i)})$ — градиент $f$ в точке $x^{(i)}$, $\eta \ge 0$ — фиксированное число. Опишите судьбу Гарри в зависимости от значения $\eta$. При каких значениях $\eta$ Гарри подойдёт к философскому камню сколь угодно близко? Сколько времени ему понадобится, чтобы подойти к философскому камню на расстояние не больше $\eps$?
(впишите решение сюда)
Маша, Неля и Катя решают задачу линейной регрессии. Данные у них одинаковые, в них $n$ наблюдений и два признака $x^{(1)}$ и $x^{(2)}$, а также вектор ответов $y$. Признаки имеют нулевое выборочное среднее и нулевую выборочную ковариацию. Маша находит вектор весов $(w^{М}_1, w^{М}_2)$ как МНК-оценку для задачи $y_i=w_1 x^{(1)}_i+w_2 x^{(2)}_i+\eps_i$. Неля решила выбросить второй признак и находит вес $w^{Н}_1$ как МНК-оценку для задачи $y_i=w_1 x^{(1)}_i + \eps_i$. Катя выбросила первый признак и находит вес $w^{К}_2$ как МНК-оценку для задачи $y_i = w_2 x^{(2)}_i + \eps_i$. Докажите, что $w^{М}_1 = w^{Н}_1$ и $w^{К}_2 = w^{М}_2$. Будет ли это верно в случае, если признаки будут по-прежнему иметь нулевое среднее, но окажутся скоррелированными (то есть не будут иметь нулевую ковариацию)?
(впишите решение сюда)
Николай решает задачу линейной регрессии $y_i=w_0 + w_1 x_i + \eps_i$. У него есть четыре наблюдения: $(1, 2)$, $(2, 3)$, $(4, 5)$ и $(5, 4)$ (в каждом наблюдении первая компонента — это x, вторая — y). Он решил исползовать hold-out кросс-валидацию, разбив свои данные на обучающую и тестовую выборку, в обучающую выборку попали первые два наблюдения, в тестовую — третье и четвёртое.
(впишите решение сюда)
Маша и Катя решают задачу линейной регрессии. Изначально у них одинаковый набор данных, состоящий из $n$ наблюдений $x_i$, $i=1, \ldots, x_n$ по $d$ признаков и вектора ответов $y=(y_1, \ldots, y_n)$. Маша записала линейную модель
$$y_i = x^{(1)}_i w_1 + \ldots + x^{(d)}_i w_d + \eps_i.$$и стала искать МНК-оценку для $(w_1, \ldots, w_d)$. А Катя считает, что реальная зависимость между $y$ и признаками является нелинейной, поэтому она добавила новые признаки в модель (но не стала убирать старые). В качестве новых признаков она использовала различные линейные и нелинейные функции от старых признаков, которые ей приходили в голову. Таким образом, Катина модель выглядит так:
$$y_i = x^{(1)}_i w_1 + \ldots + x^{(d)}_i w_d + x^{(d+1)}_i w_{d+1} +\ldots + x^{(d+k)}_i w_{d+k}+\eps_i,$$где $x^{(d+1)}, \ldots, x^{(d+k)}$ — новые признаки, добавленные Катей. Она также ищет вектор весов с помощью метода наименьших квадратов.
После нахождения вектора весов каждая девушка вычислила RSS для своей модели (по обучающей выборке).
(впишите решение сюда)
У Александра есть вектор ответов $(y_1, \ldots, y_n)$, состоящий из $n$ различных чисел, причём $n$ нечётное число. Он хочет научиться предсказывать $y$ таким образом, чтобы минимизировать эмпирический риск для функции потерь $L(y, \widehat y)=|y-\widehat y|$, то есть минимизировать величину
$$Q(y)=\sum_{i=1}^n |y_i - \widehat y|.$$Одна проблема: Александр потерял матрицу признаков, поэтому вынужден использовать алгоритм, обучающийся только по ответам и предсказывающий во всех точках одно и то же число $\widehat y$. Как найти $\widehat y$ по набору чисел $y_1, \ldots, y_n$?
(впишите решение сюда)
Пусть числа $y_1, \ldots, y_n$ получены как выборка из нормального распределения $\mathcal N(\mu, \sigma^2)$ с неизвестными параметрами $\mu$ и $\sigma^2$. Мы хотим найти оценку наибольшего правдоподобия для $\mu$ и $\sigma^2$, то есть такие значения этих параметров, при которых функция правдоподобия
$$p(y_1, \ldots, y_n \mid \mu, \sigma^2)$$будет максимальной. На лекциях была найдена функция правдоподобия и показано, что оптимальное $\mu$ можно найти независимо от $\sigma^2$ и оно равно выборочному среднему. Завершите нахождение оценки наибольшего правдоподобия: найдите теперь оптимальное $\sigma^2$.
Является ли полученная оценка несмещённой? Докажите.
(впишите решение сюда)
У рассеянного Александра из задачи 7 есть вектор ответов $(y_1, \ldots, y_n)$ для задачи классификации, каждый $y_i\in \{0, 1\}$, $n$ нечётное число, всего среди $y_i$ есть $m$ единиц и $(n-m)$ нулей. Как и в прошлый раз, Александр потерял матрицу признаков, поэтому вынужден использовать алгоритм, обучающийся только по ответам. Он хочет, чтобы алгоритм предсказывал вероятность $p$ получения единицы, и думает, какую функцию потерь ему выбрать из двух возможных:
-\log p,&\text{ if }y=1;\ -\log(1-p),&\text{ if }y=0. \end{cases}$$
Для нахождения оптимального $p$ Александр решает задачу минимизиации эмпирического риска:
$$\sum_{i=1}^n L(y_i, p) \to \min_{p},$$где $L$ — это либо $L_{LL}$, либо $L_{AD}$.
Какое $p$ получится у Александра для каждой из данных функций потерь? Какую из функций потерь следует использовать, если Александр хочет, чтобы $p$ была состоятельной оценкой для вероятности получения единицы?
Кларисса решает задачу двухлассовой классификации (классы обозначаются $+1$ и $-1$) с помощью алгоритма машинного обучения, который для $i$-го объекта выдаёт степень уверенности $s_i$ алгоритма в том, что этот объект принадлежит к классу $+1$ (например, это может быть оценка вероятности, данная логистической регрессией). Кларисса выбирает пороговое значение $t$, после чего все объекты, для которых $s_i>t$, относит к положительному классу, а остальные — к отрицательному. Иными словами, окончательное предсказание классификатора имеет вид: $$\hat y_i = [s_i>t] - [s_i\le t].$$
В таблице для каждого элемента обучающей выборки даны значения $s_i$ и их истинные классы. Построить ROC-кривую для данного алгоритма. (Вы можете сделать это вручную — это хорошее упражнение (посмотрите пример здесь) — либо самостоятельно написать код, который строит ROC-кривую. Использовать готовые решения из библиотек типа scikit-learn нельзя.)
$$\begin{array}{|c|c|} \hline s_i & y_i \\ \hline 0.6 & +1\\ 0.5 & -1\\ 0.1 & -1\\ 0.2 & -1\\ 0.4 & +1\\ 0.7 & +1\\ \hline \end{array}$$Профессор Стамп обучает случайный лес для решения задачи предсказания погоды на следующий день в завимости от того, сколько раз кукушка прокуковала перед закатом. Погода бывает хорошей и плохой, в подробости он не вдаётся. Его обучающая выборка приведена в таблице. Лес состоит из трёх решающих пней, то есть решающих деревьев с единственной нетерминальной вершиной. В результате процедуры бэггинга первому пню досталась выборка, полученная из исходной выбором наблюдений 1, 2, 3 и снова 3, второму — наблюдения 2, снова 2, 3 и 4, а третьему — наблюдения 1, 3, снова 3 и опять 3. Каждый пень делит выборку на две части в зависимости от результата сравнения $x_i$ с порогом $t$. Значение порога выбирается таким образом, чтобы минимизировать функцию
$$Q(L, R)=|L|\cdot I_G(L)+|R|\cdot I_G(R),$$где $I_G(M)$ — значение Gini impurity function на соответствующем множестве, $L$ и $R$ — части, на которые делится выборка, $|R|$ и $|L|$ — количество элементов в соответствующем множестве. Значения $t$ выбираются ровно посередине между ближайшими значениями $x_i$ в выборке. Если есть несколько одинаково оптимальных с точки зрения функции $Q$ значений $t$, выбирается меньшее из них. В качестве предсказания каждый из пней выдаёт наиболее часто встречающийся класс в соответствующей части выборки; если объектов каждого класса поровну, то предсказывается good (пни оптимистичны). Предсказание всего леса определяется в результате голосования каждого из пней.
Подробнее:
Введём обозначения: $$\begin{align} \mathcal D &= \{(x_1, y_1), \ldots, (x_n, y_n)\},\\ L(t)&=\{(x_i, y_i) \in \mathcal D\mid x_i < t\},\\ R(t)&=\{(x_i, y_i) \in \mathcal D\mid x_i \ge t\},\\ \pi(y, M)&=\frac{|\{(x_i, y_i) \in M\mid y_i = y\}|}{|M|}, \end{align} $$ то есть $\mathcal D$ — обучающая выборка, $L(t)$ и $R(t)$ — множества, на которые она разбивается по пороговому значению $t$, то есть $\pi(y, M)$ — это доля элементов $M$, имеющих данный класс $y$. Тогда $I_G$ определяется следующим образом:
$$I_G(M)=\sum_{y\in \{good,\, bad\}} \pi(y, M)\cdot(1-\pi(y, M)).$$Профессор Буст считает, что профессор Стамп из предыдущей задачи выбрал неудачный алгоритм для предсказания погоды и вместо случайного леса лучше использовать градиентный бустинг. В качестве стартового базового алгоритма $a_0(x)$ бустинга он выбрал такой, который предсказывает, что вероятность наступления хорошей погоды равна одной второй, вне зависимости от значения x, то есть $a_0(x)=\frac{1}{2}$ для всех $x$. В качестве функции потерь $L(y, p)$ он выбрал log loss (см. задачу 9). Общие потери на всей выборке вычисляются как сумма потерь на каждом объекте:
$$\mathcal L(p_1, \ldots, p_n)=\sum_{i=1}^n L(p_i, y_i)$$где $$\begin{align} \RSS(M)&=\sum_{(x_i, s_i) \in M} (s_i - \bar s)^2;\\ \bar s&=\frac{1}{|M|}\sum_{(x_i, s_i)\in M} s_i. \end{align}$$ Найти пороговое значение $t$ и выписать функцию $b_1(x)$ явно. 4. Пусть $a_1(x)=a_0(x)+b_1(x)$ — результат одного шага градиентного бустинга (коэффициент при $b_1$ для простоты выбрали равным 1). Найти $a_1(7)$. Какая погода, согласно предсказанию этого алгоритма, скорее всего будет завтра (хорошая или плохая), если вчера кукушка прокуковала 7 раз?