{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c61d7ff9",
   "metadata": {},
   "source": [
    "# MIT 6.036 — Неделя 1: Гиперплоскости\n",
    "## Теория + классические задачи + геометрическая визуализация\n",
    "\n",
    "**Цель:** Подготовка к муниципальному этапу ВсОШ по ИИ. Глубокое понимание линейной разделимости, отступов (margin) и алгоритма персептрона.\n",
    "\n",
    "В этом ноутбуке:\n",
    "1. Строгая математическая теория гиперплоскостей.\n",
    "2. 4 классические задачи из курса MIT 6.036 (с переводом и разбором).\n",
    "3. Бонусная задача на комбинаторную геометрию (\"Лестница\").\n",
    "4. Полная визуализация в `matplotlib`.\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4a1e1fcc",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')\n",
    "\n",
    "# Настройка стиля графиков для четкости\n",
    "plt.style.use('seaborn-v0_8-whitegrid')\n",
    "plt.rcParams['figure.dpi'] = 120\n",
    "plt.rcParams['font.size'] = 11\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9debfb6b",
   "metadata": {},
   "source": [
    "## 1. Теоретический базис\n",
    "\n",
    "В $d$-мерном пространстве **гиперплоскость** — это $(d-1)$-мерное аффинное подпространство. В 2D это прямая, в 3D — плоскость.\n",
    "\n",
    "### Параметризация\n",
    "Гиперплоскость однозначно задается парой $(\\boldsymbol{\\theta}, \\theta_0)$, где:\n",
    "- $\\boldsymbol{\\theta} \\in \\mathbb{R}^d$ — **вектор нормали** (перпендикулярен гиперплоскости, указывает в сторону класса $+1$).\n",
    "- $\\theta_0 \\in \\mathbb{R}$ — **сдвиг** (bias или свободный член).\n",
    "\n",
    "Уравнение гиперплоскости:\n",
    "$$\\boldsymbol{\\theta}^\\top \\mathbf{x} + \\theta_0 = 0$$\n",
    "\n",
    "### Классификатор\n",
    "Точка $\\mathbf{x}$ классифицируется по знаку скалярного произведения:\n",
    "$$h(\\mathbf{x}) = \\operatorname{sign}(\\boldsymbol{\\theta}^\\top \\mathbf{x} + \\theta_0) = \\begin{cases} +1, & \\text{если } \\boldsymbol{\\theta}^\\top \\mathbf{x} + \\theta_0 > 0 \\\\ -1, & \\text{если } \\boldsymbol{\\theta}^\\top \\mathbf{x} + \\theta_0 < 0 \\end{cases}$$\n",
    "\n",
    "### Геометрическое расстояние и Margin (отступ)\n",
    "Расстояние от точки $\\mathbf{x}$ до гиперплоскости:\n",
    "$$\\text{dist}(\\mathbf{x}, H) = \\frac{|\\boldsymbol{\\theta}^\\top \\mathbf{x} + \\theta_0|}{\\|\\boldsymbol{\\theta}\\|}$$\n",
    "\n",
    "Если точка $\\mathbf{x}^{(i)}$ имеет истинную метку $y^{(i)} \\in \\{+1, -1\\}$, её **отступ (margin)** определяется как:\n",
    "$$\\gamma^{(i)} = y^{(i)} \\cdot \\frac{\\boldsymbol{\\theta}^\\top \\mathbf{x}^{(i)} + \\theta_0}{\\|\\boldsymbol{\\theta}\\|}$$\n",
    "\n",
    "Набор данных **линейно разделим**, если $\\forall i: \\gamma^{(i)} > 0$.\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b317b4bf",
   "metadata": {},
   "source": [
    "## 2. Задача 1: Вычисление классификатора и расстояния\n",
    "> **Условие:** \n",
    "> Даны вектор нормали $\\boldsymbol{\\theta} = \\begin{bmatrix} 2 \\\\ 1 \\end{bmatrix}$, сдвиг $\\theta_0 = -3$ и точка $\\mathbf{x} = \\begin{bmatrix} 4 \\\\ 2 \\end{bmatrix}$.\n",
    "> Вычислите значение $\\boldsymbol{\\theta}^\\top \\mathbf{x} + \\theta_0$, предсказанный класс и геометрическое расстояние от точки $\\mathbf{x}$ до гиперплоскости.\n",
    "\n",
    "### Разбор и код\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ea951d1f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Значение θᵀx + θ₀ = 7.0\n",
      "Предсказанный класс h(x) = +1\n",
      "Геометрическое расстояние = 3.1305\n"
     ]
    }
   ],
   "source": [
    "theta = np.array([2., 1.])\n",
    "theta_0 = -3.\n",
    "x = np.array([4., 2.])\n",
    "\n",
    "# 1. Значение классификатора (до нормировки)\n",
    "score = theta @ x + theta_0\n",
    "pred_class = np.sign(score)\n",
    "\n",
    "# 2. Геометрическое расстояние\n",
    "dist = abs(score) / np.linalg.norm(theta)\n",
    "\n",
    "print(f\"Значение θᵀx + θ₀ = {score}\")\n",
    "print(f\"Предсказанный класс h(x) = {pred_class:+.0f}\")\n",
    "print(f\"Геометрическое расстояние = {dist:.4f}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e3cc500d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Визуализация Задачи 1\n",
    "fig, ax = plt.subplots(figsize=(7, 6))\n",
    "xs = np.linspace(-1, 6, 200)\n",
    "ys = (-theta[0]*xs - theta_0) / theta[1]\n",
    "ax.plot(xs, ys, 'r-', lw=2, label=r'Гиперплоскость: $2x_1 + x_2 - 3 = 0$')\n",
    "\n",
    "# Закраска полуплоскостей\n",
    "ax.fill_between(xs, ys, 8, alpha=0.10, color='green', label=r'$\\theta^\\top x + \\theta_0 > 0$ (Класс +1)')\n",
    "ax.fill_between(xs, -4, ys, alpha=0.10, color='red',   label=r'$\\theta^\\top x + \\theta_0 < 0$ (Класс -1)')\n",
    "\n",
    "# Точка и вектор нормали\n",
    "ax.scatter(*x, s=120, c='black', zorder=5, label=r'Точка $x = (4,2)$')\n",
    "ax.annotate('', xy=(x[0]+theta[0]/np.linalg.norm(theta), x[1]+theta[1]/np.linalg.norm(theta)),\n",
    "            xytext=x, arrowprops=dict(arrowstyle='->', color='blue', lw=2))\n",
    "ax.text(x[0]+0.2, x[1]+0.3, r'$\\theta$ (нормаль)', color='blue', fontsize=12)\n",
    "\n",
    "ax.set_xlim(-1, 6); ax.set_ylim(-1, 6)\n",
    "ax.set_xlabel(r'$x_1$'); ax.set_ylabel(r'$x_2$')\n",
    "ax.set_title('Задача 1: Гиперплоскость и расстояние до неё')\n",
    "ax.legend(loc='upper left'); plt.tight_layout(); plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7e19a41",
   "metadata": {},
   "source": [
    "## 3. Задача 2: Построение разделяющей гиперплоскости\n",
    "> **Условие:** \n",
    "> Даны две точки: $\\mathbf{a} = (1, 1)$ с меткой $y_a = +1$ и $\\mathbf{b} = (3, 3)$ с меткой $y_b = -1$.\n",
    "> Найдите гиперплоскость $\\boldsymbol{\\theta}^\\top \\mathbf{x} + \\theta_0 = 0$, которая разделяет эти точки и проходит ровно через середину отрезка между ними.\n",
    "\n",
    "### Идея\n",
    "Канонический разделяющий классификатор строится так: его нормаль $\\boldsymbol{\\theta}$ направлена от точки класса $-1$ к точке класса $+1$ (или наоборот, главное — согласовать знак), а сдвиг $\\theta_0$ подбирается так, чтобы середина отрезка лежала на гиперплоскости.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e3796ffe",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = np.array([1., 1.]); ya = +1\n",
    "b = np.array([3., 3.]); yb = -1\n",
    "\n",
    "# Середина отрезка\n",
    "m = (a + b) / 2\n",
    "\n",
    "# Нормаль направлена от b к a (так как a имеет класс +1)\n",
    "theta = (a - b)\n",
    "\n",
    "# Находим theta_0 из условия, что m лежит на гиперплоскости: theta^T m + theta_0 = 0\n",
    "theta_0 = -theta @ m\n",
    "\n",
    "print(f\"Вектор нормали θ = {theta}\")\n",
    "print(f\"Сдвиг θ₀ = {theta_0}\")\n",
    "print(f\"Проверка для a: sign(θᵀa + θ₀) = {np.sign(theta @ a + theta_0):+.0f} (ожидалось +1)\")\n",
    "print(f\"Проверка для b: sign(θᵀb + θ₀) = {np.sign(theta @ b + theta_0):+.0f} (ожидалось -1)\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0066b8a0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Визуализация Задачи 2\n",
    "fig, ax = plt.subplots(figsize=(7, 6))\n",
    "xs = np.linspace(0, 4, 200)\n",
    "ys = (-theta[0]*xs - theta_0) / theta[1]\n",
    "ax.plot(xs, ys, 'r-', lw=2, label='Разделяющая гиперплоскость')\n",
    "\n",
    "ax.scatter(*a, s=150, c='green', marker='o', zorder=5, label=r'$a, y=+1$')\n",
    "ax.scatter(*b, s=150, c='red',   marker='s', zorder=5, label=r'$b, y=-1$')\n",
    "ax.scatter(*m, s=100, c='black', marker='*', zorder=5, label='Середина отрезка')\n",
    "\n",
    "# Пунктирная линия между точками\n",
    "ax.plot([a[0], b[0]], [a[1], b[1]], 'k--', alpha=0.5)\n",
    "\n",
    "ax.set_xlim(0, 4); ax.set_ylim(0, 4)\n",
    "ax.set_xlabel(r'$x_1$'); ax.set_ylabel(r'$x_2$')\n",
    "ax.set_title('Задача 2: Канонический разделяющий классификатор')\n",
    "ax.legend(); plt.tight_layout(); plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3de76abb",
   "metadata": {},
   "source": [
    "## 4. Задача 3: Вычисление отступов (Margin) датасета\n",
    "> **Условие:** \n",
    "> Дана гиперплоскость с $\\boldsymbol{\\theta} = \\begin{bmatrix} 1 \\\\ 1 \\end{bmatrix}$ и $\\theta_0 = -2$.\n",
    "> Вычислите отступ (margin) для каждой точки датасета. Какая точка имеет наименьший отступ (является \"опорной\" или самой сложной для классификации)?\n",
    "> \n",
    "> | $i$ | $\\mathbf{x}^{(i)}$ | $y^{(i)}$ |\n",
    "> |---|---|---|\n",
    "> | 1 | $(0, 0)$ | $-1$ |\n",
    "> | 2 | $(3, 0)$ | $+1$ |\n",
    "> | 3 | $(2, 2)$ | $+1$ |\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c15fe8a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "theta = np.array([1., 1.])\n",
    "theta_0 = -2.\n",
    "X = np.array([[0., 0.], [3., 0.], [2., 2.]])\n",
    "y = np.array([-1., +1., +1.])\n",
    "\n",
    "norm_theta = np.linalg.norm(theta)\n",
    "# Формула margin: y * (theta^T x + theta_0) / ||theta||\n",
    "margins = y * (X @ theta + theta_0) / norm_theta\n",
    "\n",
    "print(\" i |   x    | y | θᵀx+θ₀ |  margin (отступ)\")\n",
    "print(\"---|--------|---|--------|-----------------\")\n",
    "for i in range(len(X)):\n",
    "    print(f\" {i+1} | {X[i]} | {y[i]:+.0f} | {X[i]@theta+theta_0:6.2f} | {margins[i]:6.4f}\")\n",
    "\n",
    "hardest_idx = np.argmin(margins)\n",
    "print(f\"\\nНаименьший отступ имеет точка {hardest_idx+1} -> margin = {margins[hardest_idx]:.4f}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "964c4aa4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Визуализация Задачи 3\n",
    "fig, ax = plt.subplots(figsize=(7, 6))\n",
    "xs = np.linspace(-1, 4, 200)\n",
    "ys = (-theta[0]*xs - theta_0) / theta[1]\n",
    "ax.plot(xs, ys, 'r-', lw=2, label='Гиперплоскость')\n",
    "\n",
    "for i, (xi, yi) in enumerate(zip(X, y)):\n",
    "    color = 'green' if yi > 0 else 'red'\n",
    "    marker = 'o' if yi > 0 else 's'\n",
    "    ax.scatter(*xi, s=150, c=color, marker=marker, zorder=5,\n",
    "               label=f'x{i+1}, y={yi:+.0f}, margin={margins[i]:.2f}')\n",
    "    \n",
    "    # Рисуем перпендикуляр (проекцию) точки на гиперплоскость\n",
    "    proj = xi - (theta @ xi + theta_0) / norm_theta**2 * theta\n",
    "    ax.plot([xi[0], proj[0]], [xi[1], proj[1]], 'k:', alpha=0.6)\n",
    "\n",
    "ax.set_xlim(-1, 4); ax.set_ylim(-1, 4)\n",
    "ax.set_xlabel(r'$x_1$'); ax.set_ylabel(r'$x_2$')\n",
    "ax.set_title('Задача 3: Отступы точек датасета')\n",
    "ax.legend(fontsize=9); plt.tight_layout(); plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a763f6e7",
   "metadata": {},
   "source": [
    "## 5. Задача 4: Правило обновления персептрона\n",
    "> **Условие:** \n",
    "> Начальные веса: $\\boldsymbol{\\theta} = \\begin{bmatrix} 0 \\\\ 0 \\end{bmatrix}$, $\\theta_0 = 0$. \n",
    "> Запустите алгоритм персептрона на следующем датасете (в указанном порядке). Выведите значения $\\boldsymbol{\\theta}$ и $\\theta_0$ после каждого шага, на котором произошла ошибка классификации.\n",
    ">\n",
    "> | $\\mathbf{x}^{(i)}$ | $y^{(i)}$ |\n",
    "> |---|---|\n",
    "> | $(1, 0)$ | $+1$ |\n",
    "> | $(0, 1)$ | $+1$ |\n",
    "> | $(-1, 0)$ | $-1$ |\n",
    "\n",
    "### Правило обновления\n",
    "Если классификатор ошибается, то есть $y^{(i)}(\\boldsymbol{\\theta}^\\top \\mathbf{x}^{(i)} + \\theta_0) \\le 0$, мы обновляем параметры:\n",
    "$$\\boldsymbol{\\theta} \\leftarrow \\boldsymbol{\\theta} + y^{(i)} \\mathbf{x}^{(i)}, \\qquad \\theta_0 \\leftarrow \\theta_0 + y^{(i)}$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e46d117a",
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.array([[1., 0.], [0., 1.], [-1., 0.]])\n",
    "y = np.array([+1., +1., -1.])\n",
    "theta = np.zeros(2)\n",
    "theta_0 = 0.\n",
    "\n",
    "print(\" Шаг | Ошибка? |   θ (веса)  | θ₀ (сдвиг)\")\n",
    "print(\"-----|---------|-------------|----------\")\n",
    "for step in range(3):\n",
    "    score = y[step] * (theta @ X[step] + theta_0)\n",
    "    mistake = score <= 0\n",
    "    if mistake:\n",
    "        theta   = theta   + y[step] * X[step]\n",
    "        theta_0 = theta_0 + y[step]\n",
    "    print(f\"  {step+1}   |   {'ДА' if mistake else 'НЕТ':<4}| {theta} | {theta_0:+.0f}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36afcf74",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Визуализация эволюции гиперплоскости в алгоритме персептрона\n",
    "fig, axes = plt.subplots(1, 3, figsize=(15, 4))\n",
    "theta = np.zeros(2); theta_0 = 0.\n",
    "history = [(theta.copy(), theta_0)]\n",
    "\n",
    "for step in range(3):\n",
    "    if y[step] * (theta @ X[step] + theta_0) <= 0:\n",
    "        theta   = theta   + y[step] * X[step]\n",
    "        theta_0 = theta_0 + y[step]\n",
    "    history.append((theta.copy(), theta_0))\n",
    "\n",
    "for k in range(3):\n",
    "    ax = axes[k]\n",
    "    th, th0 = history[k+1]\n",
    "    xs = np.linspace(-2, 2, 200)\n",
    "    \n",
    "    # Отрисовка текущей гиперплоскости\n",
    "    if abs(th[1]) > 1e-9:\n",
    "        ys = (-th[0]*xs - th0) / th[1]\n",
    "        ax.plot(xs, ys, 'r-', lw=2, label='Текущая граница')\n",
    "    else:\n",
    "        ax.axvline(-th0/th[0], color='r', lw=2, label='Текущая граница')\n",
    "        \n",
    "    # Отрисовка точек, обработанных к этому шагу\n",
    "    for i in range(k + 1):\n",
    "        c = 'green' if y[i] > 0 else 'red'\n",
    "        m = 'o' if y[i] > 0 else 's'\n",
    "        ax.scatter(*X[i], s=120, c=c, marker=m, zorder=5)\n",
    "        \n",
    "    ax.set_title(f'После шага {k+1}\\nθ={th}, θ₀={th0:+.0f}')\n",
    "    ax.set_xlim(-2, 2); ax.set_ylim(-2, 2); ax.grid(True)\n",
    "    ax.legend(fontsize=9)\n",
    "\n",
    "plt.tight_layout(); plt.show()\n"
   ]
  }
 ],
 "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.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}