{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Машинное обучение \n", "## Факультет математики НИУ ВШЭ, 2019-20 учебный год\n", "\n", "_Илья Щуров, Соня Дымченко, Руслан Хайдуров, Александр Каган, Павел Балтабаев_\n", "\n", "[Страница курса](http://wiki.cs.hse.ru/Машинное_обучение_на_матфаке_2020)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Домашнее задание 5. Линейные модели и немножко деревьев" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Задание выполнил(а): _(впишите свои фамилию и имя)_" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Внимание!__ Домашнее задание выполняется самостоятельно. При попытке сдать хотя бы частично списанный текст, или текст, полученный в результате совместного решения задач, вся работа будет оценена на 0 баллов. Мы также уведомим администрацию факультета и попросим применить дисциплинарное взыскание (предупреждение, выговор, отчисление) ко всем вовлеченным студентам." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 1 (20 баллов)\n", "Рассмотрим следующую модель. Значения $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$ определяются следующим образом:\n", "\n", "$$\\newcommand{\\eps}{\\varepsilon}y_i = \\langle w, x_i \\rangle + \\eps_i,$$\n", "\n", "где $\\eps_i$ — независимые случайные величины, распределённые по нормальному закону, $\\eps_i \\sim \\mathcal N(0, \\sigma_i^2)$ (то есть у каждого $\\eps_i$ своя дисперсия, равная $\\sigma_i^2$, все $\\sigma_i$ фиксированы и известны).\n", "\n", "1. Найти функцию правдоподобия $p((y_1, \\ldots, y_n) \\mid w, x, \\sigma)$, равную плотности вероятности получения данных $y_1, \\ldots, y_n$ при заданных фиксированных $w$, $x$ и $\\sigma$.\n", "2. Найти логарифм правдоподобия.\n", "3. Записать задачу максимизации логарфима правдоподобия по $w$. Выкинуть лишние слагаемые и записать аналог $RSS$ для этой задачи. \n", "4. Записать задачу максимизации правдоподобия в матричном виде. Для этого ввести матрицы $X$ (матрица объект-признак, по строкам записаны $x_1, \\ldots, x_n$) и $\\Sigma$ — диагональная матрица, у которой на диагонали стоят $\\sigma_1, \\ldots, \\sigma_n$.\n", "5. Решить эту задачу в матричном виде. (Найти градиент аналога $RSS$ в матричном виде, приравнять нулю, решить получившееся уравнение. Найти гессиан, показать, что он отрицательно определён в точке максимума.)\n", "6. Является ли полученная оценка для $w$ несмещённой?\n", "7. Найти ковариационную матрицу для оценки $w$.\n", "\n", "**Подсказка.** Для самопроверки можеет подставить в качестве вектора $\\sigma$ постоянный вектор (все компоненты равны одному и тому же числу). Должны получиться формулы, которые доказывались на лекциях." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*(впишите решение сюда)*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 2 (10 баллов)\n", "Рассмотрим такую модель. Значения $x_1, \\ldots, x_n \\in \\mathbb R$ — фиксированные числа, $\\beta \\in \\mathbb R$ — фиксированное число, $\\eps_i \\sim \\mathcal N(0, 1)$ — независимые случайные ошибки,\n", "\n", "$$y_i = \\beta x_i + \\eps_i, \\quad i = 1, \\ldots, n.$$\n", "\n", "Пусть $\\widehat \\beta$ — МНК-оценка $\\beta$ для данной модели. Для предсказания значения $y$ в точке $x_{new}$ используется следующий алгоритм:\n", "\n", "$$\\widehat y_{new} = \\gamma \\cdot \\widehat \\beta x_{new},$$\n", "\n", "где $\\gamma \\in \\mathbb R$ — некоторая константа (не зависящая от $x_1, \\ldots, x_n$ и $y_1, \\ldots, y_n$).\n", "\n", "1. Для заданного $x_{new}$ найти квадрат смещения предсказания и разброс (дисперсию) предсказания (как функции от $x_{new}$, $\\beta$ и $\\gamma$ и $(x_1, \\ldots, x_n)$).\n", "2. Найти такое значение $\\gamma$, при котором ожидаемая квадратичная ошибка предсказания минимальна. (Эта величина будет зависеть от $\\beta$, $x_{new}$ и $(x_1, \\ldots, x_n)$)\n", "\n", "(Эта задача демонстрирует ещё одно проявление bias-variance tradeoff: мы можем пожертвовать несмещённостью, чтобы уменьшить ошибку предсказания.)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*(впишите решение сюда)*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 3 (10 баллов)\n", "\n", "Гарри Поттер хочет найти философский камень, расположенный в точке минимума функции $f(x_1, x_2)=x_1^2 + x_2^2$. В момент времени 0 он стартует из точки $x^{(0)}=(2, 2)$. На $i$-й минуте Гарри мгновенно перемещается (аппарирует) из точки $x^{(i)}$ в точку\n", "\n", "$$x^{(i+1)} = x^{(i)} - \\eta \\nabla f(x^{(i)}),$$\n", "где $\\nabla f(x^{(i)})$ — градиент $f$ в точке $x^{(i)}$, $\\eta \\ge 0$ — фиксированное число. Опишите судьбу Гарри в зависимости от значения $\\eta$. При каких значениях $\\eta$ Гарри подойдёт к философскому камню сколь угодно близко? Сколько времени ему понадобится, чтобы подойти к философскому камню на расстояние не больше $\\eps$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*(впишите решение сюда)*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 4 (10 баллов)\n", "Маша, Неля и Катя решают задачу линейной регрессии. Данные у них одинаковые, в них $n$ наблюдений и два признака $x^{(1)}$ и $x^{(2)}$, а также вектор ответов $y$. Признаки имеют нулевое выборочное среднее и нулевую [выборочную ковариацию](https://ru.wikipedia.org/wiki/Ковариация#Ковариация_выборок). Маша находит вектор весов $(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$. Будет ли это верно в случае, если признаки будут по-прежнему иметь нулевое среднее, но окажутся скоррелированными (то есть не будут иметь нулевую ковариацию)?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*(впишите решение сюда)*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 5 (6 баллов)\n", "Николай решает задачу линейной регрессии $y_i=w_0 + w_1 x_i + \\eps_i$. У него есть четыре наблюдения: $(1, 2)$, $(2, 3)$, $(4, 5)$ и $(5, 4)$ (в каждом наблюдении первая компонента — это x, вторая — y). Он решил исползовать hold-out кросс-валидацию, разбив свои данные на обучающую и тестовую выборку, в обучающую выборку попали первые два наблюдения, в тестовую — третье и четвёртое.\n", "\n", "1. Найдите вручную (без компьютера) МНК-оценку для $w_0$ и $w_1$, которые получит Николай.\n", "2. Найдите вручную (без компьютера) $R^2$ на обучающей и тестовой выборке. Как вы можете проинтерпретировать знак $R^2$ для тестовой выборки?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*(впишите решение сюда)*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 6 (10 баллов)\n", "Маша и Катя решают задачу линейной регрессии. Изначально у них одинаковый набор данных, состоящий из $n$ наблюдений $x_i$, $i=1, \\ldots, x_n$ по $d$ признаков и вектора ответов $y=(y_1, \\ldots, y_n)$. Маша записала линейную модель\n", "\n", "$$y_i = x^{(1)}_i w_1 + \\ldots + x^{(d)}_i w_d + \\eps_i.$$\n", "\n", "и стала искать МНК-оценку для $(w_1, \\ldots, w_d)$. А Катя считает, что реальная зависимость между $y$ и признаками является нелинейной, поэтому она добавила новые признаки в модель (но не стала убирать старые). В качестве новых признаков она использовала различные линейные и нелинейные функции от старых признаков, которые ей приходили в голову. Таким образом, Катина модель выглядит так: \n", "\n", "$$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,$$\n", "\n", "где $x^{(d+1)}, \\ldots, x^{(d+k)}$ — новые признаки, добавленные Катей. Она также ищет вектор весов с помощью метода наименьших квадратов.\n", "\n", "После нахождения вектора весов каждая девушка вычислила RSS для своей модели (по обучающей выборке). \n", "1. Докажите, что RSS Кати оказался не больше RSS Маши.\n", "2. Могут ли RSS оказаться одинаковыми? Если нет, докажите. Если да, приведите пример." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*(впишите решение сюда)*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 7 (10 баллов)\n", "У Александра есть вектор ответов $(y_1, \\ldots, y_n)$, состоящий из $n$ различных чисел, причём $n$ нечётное число. Он хочет научиться предсказывать $y$ таким образом, чтобы минимизировать эмпирический риск для функции потерь $L(y, \\widehat y)=|y-\\widehat y|$, то есть минимизировать величину\n", "\n", "$$Q(y)=\\sum_{i=1}^n |y_i - \\widehat y|.$$\n", "\n", "Одна проблема: Александр потерял матрицу признаков, поэтому вынужден использовать алгоритм, обучающийся только по ответам и предсказывающий во всех точках одно и то же число $\\widehat y$. Как найти $\\widehat y$ по набору чисел $y_1, \\ldots, y_n$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*(впишите решение сюда)*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 8 (15 баллов)\n", "\n", "Пусть числа $y_1, \\ldots, y_n$ получены как выборка из нормального распределения $\\mathcal N(\\mu, \\sigma^2)$ с неизвестными параметрами $\\mu$ и $\\sigma^2$. Мы хотим найти оценку наибольшего правдоподобия для $\\mu$ и $\\sigma^2$, то есть такие значения этих параметров, при которых функция правдоподобия\n", "\n", "$$p(y_1, \\ldots, y_n \\mid \\mu, \\sigma^2)$$\n", "\n", "будет максимальной. На лекциях была найдена функция правдоподобия и показано, что оптимальное $\\mu$ можно найти независимо от $\\sigma^2$ и оно равно выборочному среднему. Завершите нахождение оценки наибольшего правдоподобия: найдите теперь оптимальное $\\sigma^2$. \n", "\n", "Является ли полученная оценка несмещённой? Докажите." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*(впишите решение сюда)*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 9 (10 баллов)\n", "У рассеянного Александра из задачи 7 есть вектор ответов $(y_1, \\ldots, y_n)$ для задачи классификации, каждый $y_i\\in \\{0, 1\\}$, $n$ нечётное число, всего среди $y_i$ есть $m$ единиц и $(n-m)$ нулей. Как и в прошлый раз, Александр потерял матрицу признаков, поэтому вынужден использовать алгоритм, обучающийся только по ответам. Он хочет, чтобы алгоритм предсказывал вероятность $p$ получения единицы, и думает, какую функцию потерь ему выбрать из двух возможных:\n", "\n", "1. Log-loss: $$L_{LL}(y, p)=\\begin{cases}\n", "-\\log p,&\\text{ if }y=1;\\\\\n", "-\\log(1-p),&\\text{ if }y=0.\n", "\\end{cases}$$\n", "\n", "2. Абсолютное отклонение: $$L_{AD}(y, p)=|y-p|.$$\n", "\n", "Для нахождения оптимального $p$ Александр решает задачу минимизиации эмпирического риска:\n", "\n", "$$\\sum_{i=1}^n L(y_i, p) \\to \\min_{p},$$\n", "где $L$ — это либо $L_{LL}$, либо $L_{AD}$.\n", "\n", "Какое $p$ получится у Александра для каждой из данных функций потерь? Какую из функций потерь следует использовать, если Александр хочет, чтобы $p$ была состоятельной оценкой для вероятности получения единицы?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 10 (5 баллов)\n", "Кларисса решает задачу двухлассовой классификации (классы обозначаются $+1$ и $-1$) с помощью алгоритма машинного обучения, который для $i$-го объекта выдаёт степень уверенности $s_i$ алгоритма в том, что этот объект принадлежит к классу $+1$ (например, это может быть оценка вероятности, данная логистической регрессией). Кларисса выбирает пороговое значение $t$, после чего все объекты, для которых $s_i>t$, относит к положительному классу, а остальные — к отрицательному. Иными словами, окончательное предсказание классификатора имеет вид:\n", "$$\\hat y_i = [s_i>t] - [s_i\\le t].$$\n", "\n", "В таблице для каждого элемента обучающей выборки даны значения $s_i$ и их истинные классы. Построить ROC-кривую для данного алгоритма. (Вы можете сделать это вручную — это хорошее упражнение (посмотрите пример [здесь](https://github.com/esokolov/ml-course-hse/blob/master/2019-fall/seminars/sem05-linclass-metrics.pdf)) — либо самостоятельно написать код, который строит ROC-кривую. Использовать готовые решения из библиотек типа scikit-learn нельзя.)\n", "\n", "$$\\begin{array}{|c|c|}\n", "\\hline\n", "s_i & y_i \\\\\n", "\\hline\n", "0.6 & +1\\\\\n", "0.5 & -1\\\\\n", "0.1 & -1\\\\\n", "0.2 & -1\\\\\n", "0.4 & +1\\\\\n", "0.7 & +1\\\\\n", "\\hline\n", "\\end{array}$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 11 (10 баллов)\n", "\n", "$$\\begin{array}{|c|c|}\n", "\\hline\n", "i & x_i & y_i \\\\\n", "\\hline\n", "1 & 1 & good \\\\\n", "2 & 2 & good \\\\\n", "3 & 3 & bad \\\\\n", "4 & 10 & good \\\\\n", "\\hline\n", "\\end{array}$$\n", "Профессор Стамп обучает случайный лес для решения задачи предсказания погоды на следующий день в завимости от того, сколько раз кукушка прокуковала перед закатом. Погода бывает *хорошей* и *плохой*, в подробости он не вдаётся. Его обучающая выборка приведена в таблице. Лес состоит из трёх *решающих пней*, то есть решающих деревьев с единственной нетерминальной вершиной. В результате процедуры бэггинга первому пню досталась выборка, полученная из исходной выбором наблюдений 1, 2, 3 и снова 3, второму — наблюдения 2, снова 2, 3 и 4, а третьему — наблюдения 1, 3, снова 3 и опять 3. Каждый пень делит выборку на две части в зависимости от результата сравнения $x_i$ с порогом $t$. Значение порога выбирается таким образом, чтобы минимизировать функцию\n", "\n", "$$Q(L, R)=|L|\\cdot I_G(L)+|R|\\cdot I_G(R),$$\n", "где $I_G(M)$ — значение [Gini impurity function](https://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity) на соответствующем множестве, $L$ и $R$ — части, на которые делится выборка, $|R|$ и $|L|$ — количество элементов в соответствующем множестве. Значения $t$ выбираются ровно посередине между ближайшими значениями $x_i$ в выборке. Если есть несколько одинаково оптимальных с точки зрения функции $Q$ значений $t$, выбирается меньшее из них. В качестве предсказания каждый из пней выдаёт наиболее часто встречающийся класс в соответствующей части выборки; если объектов каждого класса поровну, то предсказывается good (пни оптимистичны). Предсказание всего леса определяется в результате голосования каждого из пней.\n", "\n", "1. Найти пороговые значения для каждого пня.\n", "2. Какой класс предскажет лес для наблюдения с x=7?\n", "\n", "Подробнее:\n", "\n", "Введём обозначения: \n", "$$\\begin{align}\n", "\\mathcal D &= \\{(x_1, y_1), \\ldots, (x_n, y_n)\\},\\\\\n", "L(t)&=\\{(x_i, y_i) \\in \\mathcal D\\mid x_i < t\\},\\\\\n", "R(t)&=\\{(x_i, y_i) \\in \\mathcal D\\mid x_i \\ge t\\},\\\\\n", "\\pi(y, M)&=\\frac{|\\{(x_i, y_i) \\in M\\mid y_i = y\\}|}{|M|},\n", "\\end{align}\n", "$$\n", "то есть $\\mathcal D$ — обучающая выборка, $L(t)$ и $R(t)$ — множества, на которые она разбивается по пороговому значению $t$, то есть $\\pi(y, M)$ — это доля элементов $M$, имеющих данный класс $y$. Тогда $I_G$ определяется следующим образом:\n", "\n", "$$I_G(M)=\\sum_{y\\in \\{good,\\, bad\\}} \\pi(y, M)\\cdot(1-\\pi(y, M)).$$\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 12 (10 баллов)\n", "Профессор Буст считает, что профессор Стамп из предыдущей задачи выбрал неудачный алгоритм для предсказания погоды и вместо случайного леса лучше использовать градиентный бустинг. В качестве стартового базового алгоритма $a_0(x)$ бустинга он выбрал такой, который предсказывает, что вероятность наступления хорошей погоды равна одной второй, вне зависимости от значения x, то есть $a_0(x)=\\frac{1}{2}$ для всех $x$. В качестве функции потерь $L(y, p)$ он выбрал log loss (см. задачу 9). Общие потери на всей выборке вычисляются как сумма потерь на каждом объекте:\n", "\n", "$$\\mathcal L(p_1, \\ldots, p_n)=\\sum_{i=1}^n L(p_i, y_i)$$\n", "\n", "1. Рассмотрим выборку из предыдущей задачи. Найти вектор предсказаний $p^0$ базового алгоритма $a_0$ на элементах выборки, то есть $p^0=(a_0(x_1), a_0(x_2), a_0(x_3), a_0(x_4))$. \n", "2. Найти антиградиент $(-\\nabla \\mathcal L)$ по $p$ в точке $p=p^0$. Обозначим полученный вектор через $s=(s_1, s_2, s_3, s_4)$.\n", "3. Пусть $b_1(x)$ — решающий пень, обученный на выборке, у которой значения $x_i$ совпадают со значениями в исходной выборке, а значения целевой переменной равны $s_i$, то есть пень должен предсказывать $s_i$ по $x_i$ (это задача регрессии). В качестве предсказаний пень будет использовать среднее значение целевой переменной среди всех объектов выборки, которые попали в соответствующую часть. Пороговое значение $t$ выбирается таким образом, чтобы минимизировать квадратичную ошибку:\n", "$$\\newcommand{\\RSS}{\\mathop{\\mathrm{RSS}}}Q(L, R)=\\RSS(L)+\\RSS(R),$$\n", "где \n", "$$\\begin{align}\n", "\\RSS(M)&=\\sum_{(x_i, s_i) \\in M} (s_i - \\bar s)^2;\\\\\n", "\\bar s&=\\frac{1}{|M|}\\sum_{(x_i, s_i)\\in M} s_i.\n", "\\end{align}$$\n", "Найти пороговое значение $t$ и выписать функцию $b_1(x)$ явно.\n", "4. Пусть $a_1(x)=a_0(x)+b_1(x)$ — результат одного шага градиентного бустинга (коэффициент при $b_1$ для простоты выбрали равным 1). Найти $a_1(7)$. Какая погода, согласно предсказанию этого алгоритма, скорее всего будет завтра (хорошая или плохая), если вчера кукушка прокуковала 7 раз?" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.2" } }, "nbformat": 4, "nbformat_minor": 2 }