Machine Learning Lab 3

lab3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Домашнее задание №3 по курсу \"Машинное обучение\"\n",
    "\n",
    "Новик Никита"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задание 1\n",
    "Докажем, что $VC_{dim} = d$.\n",
    "\n",
    "1) Покажем, что найдётся $C$ размера $d$, что его можно разукрасить с помощью $H$. Пусть $C = \\{(1,0,...,0), (0,1,...,0), ..., (0,0,...,1)\\}$. Рассмотрим произвольный элемент из $H_c$ $y^* = \\{y_1, y_2, ..., y_d\\}, y_i \\in \\{-1,+1\\}$. Тогда гипотеза $$h^* = sign(<w,x>+b) = sign(\\sum((1,1,...,1) * x_k) - 0.5) \\in H$$ где $x_k$ - элемент, у которого $y_k = +1$. Объединяя полученные гипотезы в семейство, получим семейство, разукрашивающее $C$.\n",
    "\n",
    "2) Покажем, что любое $C$ размера $d + 1$ нельзя разукрасить. От противного: предположим, что $C$ можно разукрасить. $C = \\{x_1, x_2, ..., x_d, x_{d+1}\\}$. Поскольку у нас элементы из $C$ лежат в $d$-мерном пространстве, то любой элемент из $C$ можно представить в виде линейной комбинации остальных элементов из $C$. Представим $x_{d+1}$: $$x_{d+1} = \\sum\\limits_{i=1}^d x_i*\\lambda_i, \\lambda_i \\in R^d$$ Из этого следует, что $<w, x_{d+1}> = <w, \\sum(x_i*\\lambda_i)> = \\sum(\\lambda_i*<w,x_i>)$.\n",
    "\n",
    "Выбирая из $H_c$ элемент $y^* = (sign(\\lambda_1), sign(\\lambda_2), ..., sign(\\lambda_d), -1)$ получаем: $$sign(<w, x_{d+1}>)=sign(\\sum(\\lambda_i*<w,x_i>))=[sign(<w,x_i>)=y_i]=+1$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задание 3\n",
    "Докажем, что $VC_{dim} = n$.\n",
    "\n",
    "1) Покажем, что найдётся $C$ размера $n$, что его можно разукрасить с помощью $H$, которая состоит из $h_I(x)=\\sum x_i$. Пусть $C = \\{(1,0,...,0), (0,1,...,0), ..., (0,0,...,1)\\}$. Рассмотрим произвольный элемент из $H_c$  $y^* = {y_1, y_2, ..., y_d}, y_i \\in \\{0,1\\}$. Покажем, что для $y^*$ можно найти функцию из $H$. Выбирая $k$ такие, что $y_k = 1$, сформируем множество $I_C = \\{k: y_k = 1\\}$. Строим по этому множество $h_{I_C}(x)$. В силу выбора нашего множества $C$, имеем: $$h_{I_C}(x) = (\\sum x_k) \\mbox{ mod 2} $$ равносильно $$h_{I_C}(x) = \\begin{cases} 1, & \\mbox{если порядковый номер x в множестве $C \\in I_C$} \\\\ 0, & \\mbox{иначе} \\end{cases}$$ Объединяя полученные гипотезы в семейство, получим семейство, разукрашивающее $C$.\n",
    "\n",
    "2) Покажем, что любое $C$ размера $n + 1$ нельзя разукрасить. Так как $|X| = 2^n$, то $VC_{dim}(H)\\le \\log_2 |X| = n$. Значит, любое множество $C$ размера $n + 1$ нельзя разукрасить."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задание 4\n",
    "1) ERM-алгоритм уже знает, что в его конечном классе гипотез H существует \"верная\" гипотеза (с нулевым true risk) для конкретного распределения и конкретной функции. No FLT говорит, что можно под алгоритм \"подстроить\" D (при m < |X|/2), что алгоритм будет ошибаться.\n",
    "2) ---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}