hw3/hw3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Машинное обучение на факультете математики\n",
    "## НИУ ВШЭ, 2018-19 учебный год\n",
    "### Домашнее задание №3\n",
    "[Страница курса](http://wiki.cs.hse.ru/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%B0_%D0%BC%D0%B0%D1%82%D1%84%D0%B0%D0%BA%D0%B5_2018/2019)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Задание выполнил(а): _(впишите свои фамилию и имя)_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Внимание!__ Домашнее задание выполняется самостоятельно. При попытке сдать хотя бы частично списанный текст, или текст, полученный в результате совместного решения задач, вся работа будет оценена на 0 баллов. Мы также уведомим администрацию факультета и попросим применить дисциплинарное взыскание (предупреждение, выговор, отчисление) ко всем вовлеченным студентам."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 1 (10 баллов)\n",
    "Пусть дана выборка $x_1, \\ldots, x_n$, все $x_i \\in \\mathbb R$ распределены как случайная величина $X$ и независимы в совокупности. $\\mathbb E[X]<\\infty$, $\\mathbb D[X]<\\infty$. Для фиксированного вектора $w\\in \\mathbb R^n$ и вектора $x=(x_1, \\ldots, x_n)$ рассмотрим функцию\n",
    "$$\\varphi_w(x)=\\langle w, x \\rangle.$$\n",
    "\n",
    "1. При каком условии на $w$ эта функция будет несмещённой оценкой для $\\mathbb E[X]$?\n",
    "2. Среди всех $w$, при которых $\\varphi_w(x)$ является несмещённой оценкой для $\\mathbb E[X]$, найти такое, при котором дисперсия $\\varphi_w(x)$ будет наименьшей. (Подсказка: вам понадобятся множители Лагранжа.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(впишите решение сюда)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 2 (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": [
    "### Задача 3 (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$).\n",
    "2. Найти такое значение $\\gamma$, при котором ожидаемая квадратичная ошибка предсказания минимальна. (Эта величина будет зависеть от $\\beta$.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(впишите решение сюда)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 4 (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": [
    "### Задача 5 (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": [
    "### Задача 6 (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": [
    "### Задача 7 (10 баллов)\n",
    "Маша и Катя решают задачу линейной регрессии. Изначально у них одинаковый набор данных, состоящий из $n$ наблюдений $x_i$, $i=1, \\ldots, 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": [
    "### Задача 8 (10 баллов)\n",
    "У Александра есть вектор ответов $(y_1, \\ldots, y_n)$, состоящий из $n$ различных чисел, причём $n$ нечётное число. Он хочет научиться предсказывать $y$ таким образом, чтобы минимизировать эмпирический риск для функции потерь $L(y, \\widehat y)=|y-\\widehat y|$, то есть минимизировать величину\n",
    "\n",
    "$$Q(\\widehat 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": [
    "### Задача 9 (10 баллов)\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$. Является ли полученная оценка несмещённой?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(впишите решение сюда)*"
   ]
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}