HW4-Submission.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bài tập 4\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Câu 1 (1 điểm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Theo đề bài, với $N > d_{VC}$ thì $m_\\mathcal{H}(N) \\approx N^{d_{VC}}$. \n",
    "Còn khi $N \\leq d_{VC}$ thì  $m_\\mathcal{H}(N) = N^{d_{VC}} + 1$ \n",
    "\n",
    "- \"95% confidence\" nghĩa là $1 - \\delta = 0.95$ => $\\delta = 0.05$; \"your generalization error is at most 0.05\" nghĩa là $\\epsilon = 0.05$.\n",
    "\n",
    "- Tìm $N$ bằng cách giải phương trình: $\\epsilon = \\sqrt{\\frac{8}{N} ln \\frac{4m_\\mathcal{H}(2N)}{\\delta} } $. (1)\n",
    "\n",
    "(1) <=> $N = \\frac{8}{\\epsilon^2}(ln\\frac{4((2N)^{d\\mathcal{vc}}+1)}{\\delta}) $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Giới hạn tổng quát của VC: N = 452956.83215921914\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "# delta = 0.05\n",
    "# dvc = 10\n",
    "# epsilon = 0.05\n",
    "# initial_N=1000 (Giá trị dự đoán N cho vòng đệ quy)\n",
    "\n",
    "#Dùng đệ quy để tính toán N cho đến khi N - N(dự đoán) < 1:\n",
    "def get_N(delta = 0.05, dvc = 10, epsilon = 0.05, initial_N=1000):\n",
    "    N = 8 / epsilon**2 * np.log((4 * ((2 * initial_N) ** dvc + 1) / delta))\n",
    "    if (N - initial_N) < 1:\n",
    "        return N\n",
    "    else:\n",
    "        return get_N(delta, dvc, epsilon, N)\n",
    "print(\"Giới hạn tổng quát của VC: N = {}\".format(get_N()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "2e83d862b3c5fd4fb57d72c50e8115f8",
     "grade": true,
     "grade_id": "c1",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE Giá trị của N gần với 460000 nhất. Do đó, em chọn đáp án [d]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Câu 2 (1 điểm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Với $N > d_{VC}$ thì ta có thể áp dụng xấp xỉ $m_\\mathcal{H}(N) \\approx N^{d_{VC}}$ (như đã nêu trong **Câu 1**).\n",
    "\n",
    "Đối với câu a, b:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "N = 10000\n",
    "dvc = 50\n",
    "delta = 0.05\n",
    "epsilon_a = lambda N,dvc,delta: (math.sqrt(8/N * math.log(4 / delta * (2*N)**dvc)))\n",
    "epsilon_b = lambda N,dvc,delta: (math.sqrt(2/N * math.log(2*N * N**dvc)) + math.sqrt(-2/N * math.log(delta)) + 1/N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Đối với câu c: \n",
    "- Bình phương 2 vế ta được bất phương trình bậc 2 theo $\\epsilon$ sau: $\\epsilon^2 - \\frac{2\\epsilon}{N} - \\frac{1}{N} ln(\\frac{6m_\\mathcal{H}(2N)}{\\delta}) \\leq 0$ \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def epsilon_c(N,dvc,delta):\n",
    "    #Giải hệ phương trình dạng ax^2 + bx + c = 0 \n",
    "    a = 1\n",
    "    b = -2/N\n",
    "    c = - 1/N *math.log(6 * (2*N)**dvc/delta)\n",
    "    d = b**2-4*a*c \n",
    "    #chỉ xét nghiệm dương\n",
    "    return (-b + math.sqrt(d)) / (2 * a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Đối với câu d: \n",
    "- Bình phương 2 vế ta được bất phương trình bậc 2 theo $\\epsilon$ sau: $\\epsilon^2 (1 - \\frac{2}{N}) - \\frac{2\\epsilon}{N} - \\frac{1}{2N}ln(\\frac{4m_\\mathcal{H}(N^2)}{\\delta}) \\leq 0$ \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def epsilon_d(N,dvc,delta):\n",
    "    #Giải hệ phương trình dạng ax^2 + bx + c = 0 \n",
    "    a = 1 - 2/N\n",
    "    b = -2/N\n",
    "    c = - 1/(2*N) * (math.log(4 * N**(2*dvc)) - math.log(delta))\n",
    "    d = b**2-4*a*c \n",
    "    #chỉ xét nghiệm dương\n",
    "    return (-b + math.sqrt(d)) / (2 * a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Giá trị của các ràng buộc:\n",
      " -Original VC bound: 0.632174915200836 \n",
      " -Rademacher Penalty Bound: 0.3313087859616395 \n",
      " -Parrondo and Van den Broek: 0.2236982936807856 \n",
      " -Devroye: 0.21522804980824667\n"
     ]
    }
   ],
   "source": [
    "print(\"Giá trị của các ràng buộc:\\n -Original VC bound:\",epsilon_a(N,dvc,delta),\n",
    "      \"\\n -Rademacher Penalty Bound:\",epsilon_b(N,dvc,delta),\n",
    "     \"\\n -Parrondo and Van den Broek:\",epsilon_c(N,dvc,delta),\n",
    "     \"\\n -Devroye:\",epsilon_d(N,dvc,delta))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "47d4e2bb3e4812ef7b37e032a898cfec",
     "grade": true,
     "grade_id": "c2",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE Vậy tại N lớn (N=10000) thì ràng buộc Devroye là nhỏ nhất. Do đó, em chọn đáp án [d]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Câu 3 (1 điểm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Giá trị của các ràng buộc:\n",
      " -Original VC bound: 13.828161484991483 \n",
      " -Rademacher Penalty Bound: 7.048776564183685 \n",
      " -Parrondo and Van den Broek: 5.101361981989992 \n",
      " -Devroye: 5.59312554318267\n"
     ]
    }
   ],
   "source": [
    "N = 5\n",
    "print(\"Giá trị của các ràng buộc:\\n -Original VC bound:\",epsilon_a(N,dvc,delta),\n",
    "      \"\\n -Rademacher Penalty Bound:\",epsilon_b(N,dvc,delta),\n",
    "     \"\\n -Parrondo and Van den Broek:\",epsilon_c(N,dvc,delta),\n",
    "     \"\\n -Devroye:\",epsilon_d(N,dvc,delta))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "0997a909d9ab1f250c2bfd0645fee970",
     "grade": true,
     "grade_id": "c3",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE Vậy tại N nhỏ (N=5) thì ràng buộc Parrondo and Van den Broek là nhỏ nhất. Do đó, em chọn đáp án [c]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Câu 4 (1 điểm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_dataset(N):\n",
    "    X = np.random.uniform(-1, 1, (N, 1))\n",
    "    Y = np.sin(np.pi * X)\n",
    "    return X, Y\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-0.52135366]\n",
      " [-0.14092496]]\n",
      "[[-0.99775068]\n",
      " [-0.42840679]]\n"
     ]
    }
   ],
   "source": [
    "X, Y = generate_dataset(2)\n",
    "print(X)\n",
    "print(Y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x1f69bb51f08>]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAe0AAAFJCAYAAAC2OXUDAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nOzdd1xT998F8BMIoARQRNziqGKtowrWjXtXrVtQcaI4EFFQqANRkSWooOIAJyrDunelKqigrVj3rNbR1ipuhoyQPH/Y8tSfkxD4JnDef5V7k9zzaV54uDc390qUSqUSREREpPF0RAcgIiKiz8PSJiIi0hIsbSIiIi3B0iYiItISLG0iIiItwdImIiLSElLRAT4mOTlF7a9pamqI58/T1f66InAWzcRZNBNn0Uyc5V3m5sYfXFfs9rSlUl3REdSGs2gmzqKZOItm4ix5U+xKm4iISFuxtImIiLQES5uIiEhLsLSJiIi0BEubiIhIS7C0iYiItARLm4iISEuwtImIiLREvkr7woULsLe3f2f50aNH0b9/fwwePBgxMTEAgIyMDEyePBlDhgzB2LFj8ezZs/xsmoiIqNhRubTDwsIwe/ZsZGZmvrU8Ozsbvr6+WLduHSIiIhAdHY3k5GRERkbC0tISW7duRZ8+fRAaGprv8ERERMWJytcet7CwwLJlyzBjxoy3lt++fRsWFhYoVaoUAMDa2hpnz55FUlISHBwcAABt2rRhaRMRfUJqairu3PkNDx8+RHLyY7x+nY6MjEyYmhpBLpfAzKwsypevgJo1v0DZsmVFx6VCoHJpd+3aFX/88cc7y1NTU2Fs/P8XO5fJZEhNTX1ruUwmQ0rKp28GYmpqWCDXcv3Yxdi1DWfRTJxFM2n6LLdu3cLhw4dx8uRJnDlzBnfv3v3s55YtWxbW1tZo3bo1OnbsiKZNm0JXVzuu663p70teFPQsar/Ll5GREdLS0nJ/TktLg7Gx8VvL09LSYGJi8snXKog7v5ibGxfI3cNE4CyaibNoJk2d5bffbuGHH6Kwa9cO3LlzO3e5mZkZbGzaoXbt2qhUqQrKlSsHmcwIBgb6kMn08fffT/HkSTIePnyIO3d+w7VrV3H48GEcPnwYc+bMgZmZGbp1+xYDB9qiefOW0NHRzPOONfV9UYW6ZvlY8au9tL/44gvcu3cPL168gKGhIc6ePYsxY8bgr7/+QlxcHBo2bIj4+HhYW1ure9NERFpBLpfj4MF9CA9fjcTEUwAAQ0MZevTohU6duqBly1aoUeMLSCSS9z7/Q+WQnJyMM2cScexYLH788RC2bNmELVs2oXr1Ghg9eizs7IahVKnSBTobFSy1lfbevXuRnp6OwYMHw8PDA2PGjIFSqUT//v1Rvnx52NnZwd3dHXZ2dtDT00NQUJC6Nk1EpBWys7MRExOJ4OAg3L37OwCgTZv2sLMbim7dvoVMJsvX65ubm6Nnz97o2bM3FAoFEhJOIiYmErt2bYen50wsWuQHB4dxcHSchDJlzNQxEhUyiVKpVIoO8SEFcciEh2I0E2fRTJxFfY4ejcWcOR64desm9PX1YWs7DI6OE1G7tmWeXyuvszx79hSbN2/EqlUr8ORJMoyNTTBliivGjh2PkiVL5nn76iT6fVGnwjg8rpkfchARFRG//34Hw4fbwta2H27f/g3Dh4/Gzz9fQGDgUpUKWxVlypjB2Xkazp69hHnzfCCV6sLbey5sbJohPv54oWQg9WBpExEVALlcjqAgf9jYNMWhQwfQokUrxMaeQGDgUlSqVFlIJkNDQ0yY4ISff76A8eOd8OefDzBgQG+4uEzCixfPhWSivGFpExGp2b17d/Hdd93h778QZmZlERa2Abt2HUD9+g1ERwMAlCpVGvPn++DQoaOoV68Btm6NQOvWTXHw4H7R0egTWNpERGqiVCoRExOJ9u1b4ZdfzqBPn36Ii0vEd9/1++CZ4CJ9/XVj/PjjccyaNRcvX77AiBF2mDPne2RnZ4uORh/A0iYiUoM391cYDycnRwDA8uWrsXr1epQubSo42cfp6elhyhRXxMaeQO3alli9egX69v0WDx/+JToavQdLm4gonx49eoS+fb9FTEwkrKyscfToSQwaZKeRe9cfUqfOlzh8+Bj69OmHn38+jY4dbXDiRJzoWPQ/WNpERPlw6dJFdOvWHklJv6B//0HYtesgqlevITqWSoyMjLF69Xr4+ATg5csXGDSoDyIjN4uORf/B0iYiUtHBg/vRq1cX/PXXn5g92wuhoWEoUaKE6Fj5IpFI4OAwHjt27IeJiQmmTJmIoCB/aPAlPYoVljYRkQqiorZg1KihACRYv34LnJ2nadXh8E9p1qw59u07gqpVLeDvvxDTp0+FXC4XHavYY2kTEeXRunVhcHaeABMTE+zYsRc9evQUHalA1K5tiQMHYlG/fkNs2rQOo0cPQ0ZGhuhYxRpLm4goD5YtWwoPD1eYm5fDrl0HYWXVRHSkAlW+fAXs3n0ANjbtcOjQAYwePQyZmZmiYxVbLG0ios/k778QCxZ4onLlKtiz5yC++qqe6EiFwtjYBFu2xKB9+46Ijf2RxS0QS5uI6DOEhCxBUJA/qlevgT17DuGLL2qLjlSoSpQogY0bI9GuXQccOXIYDg7DkZWVJTpWscPSJiL6hI0b18Hbey4qV66CHTv2oWpVC9GRhPi3uNu0aY/Dhw/CwWEEr55WyFjaREQfsWPHNsyYMRVly5bFtm27UaVKVdGRhCpZsiQ2bYr85zPu/XB1debXwQoRS5uI6AN+/PEgnJwcYWxsgujoXahVq3gdEv8QQ0NDbNoUicaNrRAVtQX+/t6iIxUbLG0iovc4d+4sHBxGQF9fH1u2bEODBg1FR9IoMpkMmzdvQ/XqNbB48SJs2LBWdKRigaVNRPQ//vjjAeztbZGVlYWwsA1o1qy56EgaydzcHFFRO1C2bFl4eLjy1p6FgKVNRPQfKSmvMHToICQnP8aCBb7o3Lmb6EgarWbNL7BlyzaUKFECjo6j8OuvSaIjFWksbSKif8jlcowbNwrXrl3BqFEOcHAYLzqSVmjc2Brh4RuRlZWFESOG4NGjv0VHKrJY2kRE//D0/B4//XQEHTp0wsKFAUXqWuIFrVOnrpg9ex7+/vshRo3ixVcKCkubiAhvbgASHr4aX35ZF2vWrIdUKhUdSetMmuSM/v0H4ezZn+Hh4cqvghUAljYRFXuXLl3EjBlTYWJSChs3RsLEpJToSFpJIpFg8eJl+PrrxtiyZRPWrVsjOlKRw9ImomLtxYvnGDXqzd2rQkPXoEaNmqIjabWSJUti48atMDcvh9mzPZCYeEp0pCKFpU1ExZZCocCkSeNw//5dTJs2HV26dBcdqUioVKky1q6NAAA4Oo5GcnKy4ERFB0ubiIqtJUsW4ciRw2jXrgOmT58pOk6R0rx5C8ya5YW//36ISZPGQqFQiI5UJKh8poVCoYCXlxdu3LgBfX19eHt7o1q1agCAa9euwcfHJ/ex58+fx4oVK9CwYUN07doVlpaWAIBOnTphxIgR+RyBiCjvTp6MR0CAD6pUqYpVq9ZCV1dXdKQiZ+LEyUhMPIkjRw4jJGQxXFzcREfSeiqXdmxsLLKyshAdHY3z58/Dz88PK1euBADUrVsXERFvDo0cPHgQ5cqVQ5s2bZCQkICePXtizpw56klPRKSCZ8+eYtKkcdDV1UVY2AaUKWMmOlKRpKOjg2XLVqFDh9bw8/NGs2Yt0KJFK9GxtJrKh8eTkpJgY2MDAGjUqBEuX778zmPS09OxbNkyzJo1CwBw+fJlXLlyBcOGDYOzszMeP36s6uaJiFSiVCrh4uKEhw//grv7LFhbfyM6UpFWpowZVq9eD4lEgnHjRvHz7XxSeU87NTUVRkZGuT/r6upCLpe/9d3GH374Ad26dUOZMmUAADVr1kT9+vXRsmVL7NmzB97e3ggJCfngNkxNDSGVqv+Qlbm5sdpfUxTOopk4i2YyNzfGypUrcejQfrRv3x7z5s3R2sPi2vS+9OzZGT4+PnB3d4eHhwt279791oVrtGmWTynoWVQubSMjI6SlpeX+rFAo3rkYwd69e98q5ebNm6NkyZIAgM6dO3+0sAHg+fN0VeN9kLm5MZKTU9T+uiJwFs3EWTSTubkx4uPPYNq0aTA1NcXSpSvx7Jn6/40pDNr4vowY4Yh9+w5g7969WLJkOeztRwLQzlk+RF2zfKz4VT48bmVlhfj4eABvTjT79+Syf6WkpCArKwsVK1bMXTZ79mwcPnwYAJCYmIh69eqpunkiojzJyMjA+PGjkZGRgaVLQ1GxYiXRkYoVHR0dhISsRKlSpTFnzve4c+e26EhaSeXS7ty5M/T19WFrawtfX198//33WL9+PX766ScAwO+//47KlSu/9RxXV1dERkbC3t4eUVFRuZ91ExEVtDlz5uDatasYMWIMunf/VnScYqly5Srw9w9CenoaJk0aB7lcLjqS1pEoNfjisAVxyISHYjQTZ9FMRWWWM2dOo3fvrqhWrTqOHUuATCYTHSlftP19cXQchZ07t8PDYzZ8fRdo9Sz/pdGHx4mItEF6ejqcnd/cYjMkZJXWF3ZR4O+/GJUqVUZgoB/Onj0rOo5WYWkTUZG2cKEXfv/9DqZNm4bmzVuIjkMASpc2RUjISsjlcowcOZK38cwDljYRFVmnTp1AWNgq1K5tiQULFoiOQ//Rpk07jBgxBleuXMHSpYGi42gNljYRFUmpqamYMmVi7lW5/v26KWkOT895qFq1KoKDg3D58iXRcbQCS5uIiiRf3/m4f/8eJk+eCiurJqLj0HsYG5tgzZo1kMvlcHGZxLPJPwNLm4iKnKSkXxAevhq1atWGq6u76Dj0Ed26dYOt7VBcvHgeoaEfv+AWsbSJqIjJysrCtGnOUCqVCAoKQYkSJURHok+YP98H5cqVx6JFvrh584boOBqNpU1ERcqKFcG4du0K7O1H8Y5SWqJ0aVMEBCxBZmYm3Nym8N7bH8HSJqIi4/btW1i8OADly1eAp+c80XEoD3r06IkePXrh9OkEREVtER1HY7G0iahIUCgUcHWdgszMTPj4LEKpUqVFR6I88vEJgExmhHnzZuPJkyei42gkljYRFQlRUVuQkHAS3bp9i549e4uOQyqoVKkyPDxm4fnz55g3b7boOBqJpU1EWu/582dYsMAThoYy+PoueutezaRdxoxxRP36DREdvRWnTp0QHUfjsLSJSOv5+CzA06dP4ebmgcqVq4iOQ/kglUoRGLgUEokEM2ZM5SVO/wdLm4i02q+/JmHTpnWwtKyDceMmiI5DamBl1QSjRjng1q2bWLEiWHQcjcLSJiKtlZOTA3f3aVAqlfD3Xwx9fX3RkUhNZs70hLl5OQQHB+HBg/ui42gMljYRaa2IiA04f/5X9Os3EK1a2YiOQ2pkYlIKc+bMw+vXr+HlxZPS/sXSJiKt9OTJE/j4zIORkTHmzVsoOg4VgEGD7GBt/Q327t2F+PjjouNoBJY2EWklPz9vvHjxAu7uM1G+fAXRcagA6OjowM8vEBKJBLNmzUB2drboSMKxtIlI61y5chmbN2+ApWUdjB49TnQcKkBff90Yw4aNxI0b17Fu3RrRcYRjaRORVlEqlZgzxwMKhQLz5/tAT09PdCQqYDNneqJ06dIICPDF48ePRccRiqVNRFrl0KEDOHkyHp06dUGHDp1Fx6FCYGZmBnf32UhJeQUfn+J9TXmWNhFpjczMTMydOxNSqRTz5vmIjkOFaMSI0ahbtx4iIzfj0qWLouMIw9ImIq0RHr4ad+/+jtGjx6J2bUvRcagQvflDbSGUSiW8vGZBqVSKjiQES5uItEJycjIWLw6AqakpXF3dRcchAdq164COHTvjxIk4HDlySHQcIVjaRKQV/P0XIiXlFWbMmAlT0zKi45AgXl4Loauri3nz5hTLr4CxtIlI4/37Fa86db7EiBFjRMchgerU+RLDho3ErVs3sWnTetFxCp1U1ScqFAp4eXnhxo0b0NfXh7e3N6pVq5a73tvbG+fOnYNMJgMAhIaGIjs7G25ubsjIyEC5cuXg6+uLkiVL5n8KIiqy/vsVr3nzfCCVqvzPFhURM2bMxPbtMQgM9MWAAYNQqlRp0ZEKjcp72rGxscjKykJ0dDRcXV3h5+f31vorV64gPDwcERERiIiIgLGxMUJDQ9GzZ09s3boVX331FaKjo/M9ABEVbf9+xatz567o0KGT6DikAczNzeHi4oqnT59i6dIg0XEKlcqlnZSUBBubNxfob9SoES5fvpy7TqFQ4N69e/D09IStrS1++OGHd57Tpk0bJCQk5Cc7ERVxcrkcCxZ4QldXF15evL44/b9x4yaialULhIWtxL17d0XHKTQqH2dKTU2FkZFR7s+6urqQy+WQSqVIT0/HsGHDMGrUKOTk5GD48OGoX78+UlNTYWxsDACQyWRISUn56DZMTQ0hleqqGvGDzM2N1f6aonAWzcRZ1GPNmjX47bdbGD9+PFq2tM736/F90UyqzWIMf38/DBkyBIsWeWvMkduCfl9ULm0jIyOkpaXl/qxQKHI/aypZsiSGDx+e+3l18+bNcf369dznlChRAmlpaTAxMfnoNp4/T1c13geZmxsjOfnjfyxoC86imTiLeqSlpcHTcy4MDQ0xaZJrvnPwfdFM+ZmlY8dvYW3dBDExMRgxYiy++aaZmtPljbrel48Vv8qHx62srBAfHw8AOH/+PCwt//9CB3fv3sWQIUOQk5OD7OxsnDt3DvXq1YOVlRXi4uIAAPHx8bC2zv9fzkRUNK1ZE4pHj/7G+PFOKF++vOg4pIEkEgnmzfMFAHh6ziwWF1xReU+7c+fOOHXqFGxtbaFUKuHj44P169fDwsICHTt2RK9evTBo0CDo6enhu+++Q+3atTFhwgS4u7sjJiYGpqamCAoqXicQENHnefr0KZYtWwozMzNMmuQsOg5psKZNm6Fnz++wb99uHDp0AN27fys6UoGSKDX4T5OCOPzDw0qaibNoJlGzzJ7tjjVrVsLHJwAODuPV8pp8XzSTOmb57bdbsLFpilq1auP48UTo6qr/XKjPodGHx4mICsK9e3exfn04qlWrjuHDR4uOQ1qgVq3asLMbhhs3rmPbtijRcQoUS5uINIqv7wJkZ2dj5kxP6Ovri45DWsLNzQMGBgYICPBBRkaG6DgFhqVNRBrj0qUL2LFjGxo2bITvvusnOg5pkUqVKmPMGEf88ccDbNy4VnScAsPSJiKNMX++JwBgzpx50NHhP0+UN87OU2FsbIKlSwORkvJKdJwCwd8KItIIx48fRVzcMbRr1wFt27YXHYe0UJkyZpg82QVPnz5FaOgy0XEKBEubiIR787XReQDe7GUTqWrs2AkwNy+HlSuXIzk5WXQctWNpE5FwBw/ux/nzv6JPn35o0OBr0XFIi8lkMri6uiM9PQ1Lly4SHUftWNpEJFROTg78/b2ho6OD6dNnio5DRcCwYSNQrVp1bNiwFvfv3xMdR61Y2kQk1O7dO3Dt2lUMHGiL2rUtP/0Eok/Q19eHh8dsZGdnw9+/aN0djqVNRMLI5XIEBPhAKpXCzc1DdBwqQvr2HYB69Rrghx+icePGddFx1IalTUTCxMRE4s6d2xg69M3hTCJ10dHRgbv7LCiVSixa5Cs6jtqwtIlIiMzMTAQG+sHAwABTp7qJjkNFUNeu3dG4sRX27NmJy5cviY6jFixtIhJi8+aN+OOPBxg50gGVKlUWHYeKIIlEAnf3WQBQZPa2WdpEVOjS09OxZMkiGBoawtl5mug4VIS1b98JTZo0xcGD+3Dhwq+i4+QbS5uICt369eF4/PjRPxfCMBcdh4owiUQCD4/ZAFAkziRnaRNRoUpNTcGyZYthYlIKkyY5i45DxYCNTVu0bNkasbE/4pdfzoiOky8sbSIqVGvWrMSzZ88wYYITSpc2FR2HioH/frbt7+8jOE3+sLSJqNC8evUSK1cuR5kyZeDoOFF0HCpGWrRohTZt2iM+/hgSE0+JjqMyljYRFZqwsFV4+fIFJk50hpGRseg4VMx4ePy7t70QSqVScBrVsLSJqFC8evUSq1atgKmpKUaPHis6DhVDTZo0RadOXZCQcBInTsSJjqMSljYRFYrw8NXcyybhZsx4c1MaPz9vrdzbZmkTUYFLSXmFVauWw9TUFGPGjBMdh4qxRo2s0K3btzh79mccP35UdJw8Y2kTUYELD1+NFy9eYPx4J+5lk3DTp7+5OU1goJ/W7W2ztImoQKWmpmDVquUoXbo0HBwcRcchQoMGX6Nr1+745ZczOHkyXnScPGFpE1GBWrt2DZ4/f47x451gbGwiOg4RAMDV1R3Am71tbcLSJqICk5qagtDQEO5lk8Zp1MgKnTp1QWLiKSQknBQd57NJVXmSQqGAl5cXbty4AX19fXh7e6NatWq56zds2ID9+/cDANq2bQsnJycolUq0adMG1atXBwA0atQIrq6u+Z+AiDTWunVheP78OdzdZ8HEpJToOERvmTZtBmJjf0RQkD9atmwtOs5nUam0Y2NjkZWVhejoaJw/fx5+fn5YuXIlAODBgwfYs2cPtm3bBolEgiFDhqBTp04oWbIk6tWrh1WrVql1ACLSTKmpqQgNDUGpUqUxdux40XGI3tGkSVO0a9cBx48fxenTiWjevIXoSJ+k0uHxpKQk2NjYAHizx3z58uXcdRUqVEB4eDh0dXWho6MDuVwOAwMDXLlyBY8ePYK9vT3Gjh2LO3fuqGcCItJI69aF4dmzZ3B0nMi9bNJYbm7fAwCCgrTjs22JUoXz3WfNmoUuXbqgbdu2AIB27dohNjYWUun/77grlUoEBAQgLS0N8+fPxy+//IInT56ge/fuOHv2LHx9fbF9+/aPbkcuz4FUqpvXeEQkWGpqKmrUqIHs7GzcvXsXpUuXFh2J6IM6deqEn376CQkJCWjRQrP3tlU6PG5kZIS0tLTcnxUKxVuFnZmZiZkzZ0Imk2Hu3LkAgPr160NX900BN2nSBI8ePYJSqYREIvngdp4/T1cl3keZmxsjOTlF7a8rAmfRTJwFWLZsKZ48eYLp079HdrauRvz/4PuimTRhFmdnN/z000+YM2cuIiM/vjP5Meqaxdz8w9cyUOnwuJWVFeLj33y37fz587C0tMxdp1QqMXHiRNSpUwfz58/PLerly5dj48aNAIDr16+jUqVKHy1sItJOaWlpWLkyBCYmpTBu3ATRcYg+qUWLVmjVygY//XQE586dFR3no1Ta0+7cuTNOnToFW1tbKJVK+Pj4YP369bCwsIBCocDPP/+MrKwsnDhxAgAwbdo0jBs3DtOnT0dcXBx0dXXh6+ur1kGISDNs2LAWT548gZubB0qV4mFx0g6uru44deoEFi8OwObNMaLjfJBKn2kXloI4ZKIJh2LUhbNopuI8S3p6Opo0aYDMzEwkJV1C6dKmBZgub4rz+6LJNGUWpVKJ3r274cyZRMTGxqNhw0Z5fg2NPTxORPQ+W7ZsxJMnyXBwGKdRhU30KRKJBG5u/16T3F9wmg9jaRORWmRmZmLFihAYGhpi3LhJouMQ5VmbNu3QpElTHDq0H5cuXRQd571Y2kSkFjExkfjrrz8xfPhomJmZiY5DlGdv9rbfXJN8yZJFgtO8H0ubiPJNLpcjJGQx9PX1MXHiZNFxiFTWvn0nWFlZY9++3bh27aroOO9gaRNRvu3atR337t3FkCH2qFChoug4RCqTSCSYNm0GACA4OFBwmnextIkoXxQKBYKDg6CrqwsnJxfRcYjyrXPnbqhXrwF27dqBO3dui47zFpY2EeXLgQP7cOPGdQwYMBgWFtU+/QQiDSeRSODi4gqFQoFly5aIjvMWljYRqUypVGLp0kBIJBJMmcJb7VLR0bPnd6hVqzZiYiLxxx8PRMfJxdImIpUdOxaLixfPo3fvvqhVq7boOERqo6urC2fnacjOzsaKFcGi4+RiaRORSpRKJRYvfvO1GO5lU1HUv/8gVK1qgS1bNuHx48ei4wBgaRORihITT+Hnn0+jS5duqF+/geg4RGqnp6cHJycXZGRkYNWq5aLjAGBpE5GK/r34hIuLm+AkRAXHzm4YypevgPXrw/H8+TPRcVjaRJR3586dRVzcMdjYvLnsI1FRVaJECUyYMBlpaakID18tOg5Lm4jybunSNxedmDqVe9lU9A0fPgqmpqYIC1uJ1FSxdyRjaRNRnly9egWHDh3AN980Q6tWNqLjEBU4IyMjjBs3ES9evMD69WuFZmFpE1Ge/Htpx6lT3SCRSASnISocY8aMg5GRMVatWo7Xr18Ly8HSJqLPdvv2LezatQMNGnyNjh27iI5DVGhKlzbF6NFjkZz8GFu3bhKWg6VNRJ8tJGQJlEolXFy4l03Fj6PjJJQsWRLLlwcjKytLSAaWNhF9lgcP7mPbtihYWtbBt9/2Eh2HqNCZm5vD3n4k/vzzD/zwQ7SQDCxtIvosK1YEQy6Xw9l5GnR0+E8HFU8TJzpDT08PwcFByMnJKfTt8zePiD7p0aO/sWXLJlhYVEe/fgNFxyESplKlyrC1HYrff7+D3bt3FPr2WdpE9EkrVy5HZmYmnJ2nQiqVio5DJJSTkwt0dHQQHBwEhUJRqNtmaRPRRz179hQbNqxFxYqVMHjwENFxiISrUaMm+vYdgGvXruLw4YOFum2WNhF9VFjYKqSnp2HixMkwMDAQHYdII/x7Z7ulSxdBqVQW2nZZ2kT0Qa9evUJ4+GqULVsWw4aNFB2HSGN8+WVdfPttb/z66zkkJp4qtO2ytInog0JDQ/Hy5Qs4Ok6CTCYTHYdIo3h4zEbduvVQokSJQtumymeUKBQKeHl54caNG9DX14e3tzeqVauWuz4mJgZRUVGQSqWYMGEC2rdvj2fPnsHNzQ0ZGRkoV64cfH19UbJkSbUMQkTqlZ6ejsWLF8PEpBRGjXIQHYdI49Sp8yXi4hILdZsq72nHxsYiKysL0dHRcHV1hZ+fX+665ORkREREICoqCmvXrsXixYuRlZWF0NBQ9OzZE1u3bsVXX32F6GgxX04nok/bvHkDkpOT4eAwDiYmpUTHISLko7STkpJgY/PmDj+NGgggHN8AACAASURBVDXC5cuXc9ddvHgRjRs3hr6+PoyNjWFhYYHr16+/9Zw2bdogISEhn/E/n1KpxNq1a3D16tVC2yaRtsrMzMSKFSGQyWQYO3ai6DhE9A+VD4+npqbCyMgo92ddXV3I5XJIpVKkpqbC2Ng4d51MJkNqaupby2UyGVJSPn5fUlNTQ0iluqpGfEtKSgpmzpyObdu24uzZs0Xmusnm5saffpCW4CyaIywsCg8f/gVXV1d8+WV10XHURtvfl//iLJqpoGdRubSNjIyQlpaW+7NCoci96ML/rktLS4OxsXHu8hIlSiAtLQ0mJiYf3cbz5+mqxnuv3r37YvfuHYiJ2YkOHTqr9bVFMDc3RnKy2Buyqwtn0RxyuRwLF/rAwMAArq6uWj3Lf2n7+/JfnEUzqWuWjxW/yofHraysEB8fDwA4f/48LC0tc9c1bNgQSUlJyMzMREpKCm7fvg1LS0tYWVkhLi4OABAfHw9ra2tVN6+Sf79Xt3hx4X6vjkib7Nq1Hffu3YWd3TBUrFhRdBwi+g+V97Q7d+6MU6dOwdbWFkqlEj4+Pli/fj0sLCzQsWNH2NvbY8iQIVAqlZg6dSoMDAwwYcIEuLu7IyYmBqampggKClLnLJ9Uv34D9OzZE/v27UNi4im0bNm6ULdPpOkUCgWCg4Ogq6sLJycX0XGI6H9IlBq8y1kQh0xu376CFi1aoG3b9ti2bbfaX78w8bCSZtLmWfbv34tRo4Zi8OAhWLZslVbP8r84i2biLO9/nQ8pdhdXad68OWxs2iEu7hjOnTsrOg6RxlAqlVi6NBASiST3oyQi0izFrrQBYOpUNwDA0qWBgpMQaY5jx37ChQu/olevPqhVq7boOET0HsWytFu1skGTJk1x6NABXL16RXQcIo3w7x+x3Msm0lzFsrQlEgmmTZsOAAgO5t420enTCTh9OgGdO3dFgwYNRcchog8olqUNAB07dkGDBl9j164duH37lug4REItWbIIAODi4iY4CRF9TLEtbYlEAhcXVyiVSoSELBEdh0iY8+fP4dixn9C6dRt8800z0XGI6COKbWkDwLff9oalZR1s2xaFBw/ui45DJMTSpW+ul8C9bCLNV6xLW0dHB87O0yCXy7FiRbDoOESF7vr1azhwYC+srZvAxqat6DhE9AnFurQBoF+/gbCwqI4tWzbh0aO/RcchKlTBwf/uZU8vMjfRISrKin1pS6VSTJ7sgszMTKxcuVx0HKJC8/vvd7Bz5w/46qv66NKlm+g4RPQZin1pA4Ct7VBUqFARGzasxbNnT0XHISoUy5cvhUKhgIuLK/eyibQESxuAgYEBJk1yRnp6GtasWSk6DlGB++uvPxEVtQVffFELvXr1ER2HiD4TS/sfw4aNhJmZGdauXYOUlFei4xAVqNDQEGRnZ8PZeRp0dXVFxyGiz8TS/odMJsP48U54+fIF1q8PFx2HqMAkJycjImIDqlSpigEDBouOQ0R5wNL+j1GjHGBiUgqrVi1Henq66DhEBWLNmlC8fv0akyZNgZ6enug4RJQHLO3/MDEpBQeHcXjy5Ak2b94gOg6R2r18+QLr1oXB3LwchgyxFx2HiPKIpf0/xo6dCENDQ6xYEYLMzEzRcYjU6t9zNiZMmIySJUuKjkNEecTS/h9mZmYYMWIMHj78CzExkaLjEKlNamoq1qwJRenSpTFy5GjRcYhIBSzt95g4cTIMDAwQErIYcrlcdBwitYiI2IBnz55h7NgJMDIyFh2HiFTA0n6P8uUrwM5uGO7du4udO38QHYco3zIyMhAaGgKZzAgODo6i4xCRiljaH+Dk5AJdXV2EhCyGQqEQHYcoXyIjN+PRo78xapQDTE3LiI5DRCpiaX+AhUU1DBxoixs3ruPAgX2i4xCpLCsrC8uWLUHJkiUxfryT6DhElA8s7Y9wdp4GiUSCJUsWQalUio5DpJLo6K34448HGD58NMqVKyc6DhHlA0v7I2rVqo3evfvi0qULOHr0iOg4RHmWnZ2N4OAgGBgYwMlpiug4RJRPLO1PcHFxAwAsXsy9bdI+27ZF4f79e7C3H4ny5SuIjkNE+cTS/oR69eqjW7ce+OWXMzhxIk50HKLPJpfLsWTJIujr68PJyUV0HCJSA5VKOyMjA5MnT8aQIUMwduxYPHv27J3H+Pv7Y/Dgwejfvz9iYmIAAC9evECzZs1gb28Pe3t7bNy4MX/pC4mrqzsAYNEiX+5tk9bYvj0G9+7dxdChw1GpUmXRcYhIDVQq7cjISFhaWmLr1q3o06cPQkND31p/+vRp3L9/H9HR0YiMjERYWBhevnyJq1evomfPnoiIiEBERARGjBihliEK2tdfN0aXLt1w5kwiTp6MFx2H6JP+3cvW09PD5MlTRcchIjVRqbSTkpJgY2MDAGjTpg0SExPfWt+4cWP4+Pjk/pyTkwOpVIrLly/jypUrGDZsGJydnfH48eN8RC9cbm4eALi3Tdph167tuHPnNmxth6FKlaqi4xCRmkiUn2igbdu2vXMY28zMDJ6envjiiy+gUCjQrl07xMe/uweanZ0Nd3d31KlTB46OjoiNjYWhoSFatmyJPXv2IDY2FiEhIR/ctlyeA6lUV8XR1K9nz57Yv38/jh49ivbt24uOQ/ReOTk5qF+/Pn777TfcunUL1atXFx2JiNRE+qkHDBw4EAMHDnxrmZOTE9LS0gAAaWlpMDExeed5L1++hLOzM5o2bQpHxzeXTWzevHnunYU6d+780cIGgOfP1X9Pa3NzYyQnp6j0XGdnN+zfvx+zZ3ti164Dak6Wd/mZRdNwFvXZufMHXL9+HUOHDodMZpavLKJnUSfOopk4y/tf50NUOjxuZWWFuLg3Z1LHx8fD2tr6rfUZGRkYOXIk+vfvj0mTJuUunz17Ng4fPgwASExMRL169VTZvDCNG1ujU6cuSEg4iVOnToiOQ/QOhUKBxYsDoKuriylTXEXHISI1U6m07ezscOvWLdjZ2SE6OhpOTm8ujRgQEICLFy8iKioKDx48wLZt23LPFH/w4AFcXV0RGRkJe3t7REVFYdasWWodpjD8+9l2YKCf4CRE79q/fw9u3LiOgQNtUb16DdFxiEjNPvmZtkgFcchEHYcv7Oz646efjmDXrgNo2bK1mpLlHQ8raSZRsygUCnTo0BrXr19FQsJZ1KxZK9+vyfdFM3EWzaSxh8eLO+5tkyY6eHA/rl69jH79BqqlsIlI87C0VWBt/Q06dOiEkyfjkZh4SnQcIiiVSgQF+UMikWDatBmi4xBRAWFpq4h726RJfvzxEC5fvoi+ffujVq3aouMQUQFhaauoSZOmaN++I06ciMPp0wmi41AxplQqERDgA4lEAheX6aLjEFEBYmnnw/9fJY172yTOgQP7cOnSBfTt2x9ffllXdBwiKkAs7Xz45ptmaNeuA06cOI7TpxM//QQiNVMoFAgIWAgdHR24uX0vOg4RFTCWdj79+w8lP9smEfbs2Ylr165iwIDB/CybqBhgaedT06bN0LZte8THH+Nn21SocnJysGiRL3R1dXNvH0tERRtLWw3c3d9c2c3HZz7vAEaFZvv2GNy6dRN2dsNQo0ZN0XGIqBCwtNWgSZOm6NKlG06fTkBc3DHRcagYkMvlCAz0g56eHqZO5RnjRMUFS1tN3N1nAwB8fbm3TQUvJiYSd+/+jmHDRqBqVQvRcYiokLC01aRBg4bo3bsvfv31HA4fPig6DhVhWVlZCAryh4GBAVxc3ETHIaJCxNJWoxkzZkJHRwd+ft5QKBSi41ARtXVrBB48uI8RI0ajYsVKouMQUSFiaauRpWUd9O8/CFevXsaePTtFx6EiKCMjA0uWLELJkiUxefI00XGIqJCxtNXMzc0DUqkUAQE+kMvlouNQEbN58wY8fPgXRo8eh/Lly4uOQ0SFjKWtZjVq1ISdnT1+++0WfvghWnQcKkJSU1OxZEkgZDIjODm5iI5DRAKwtAvAtGnToa+vj8BAP2RlZYmOQ0VEWNhKJCc/xoQJTjAzMxMdh4gEYGkXgMqVq2DkyDG4f/8etm6NEB2HtNzOnVK0bm0AX19P6OpeRpUq/F42UXHF0i4gkydPg6GhIRYvDsDr169FxyEttXOnFI6OJXHzpj4AKXJy6sHFpQx27pSKjkZEArC0C0j58uXh4DAef//9EGvXrhEdh7TU0qX6710eHPz+5URUtLG0C5CT0xSULl0awcFBeP78meg4pIVu3nz/r+iHlhNR0cbf/AJUurQpXFym4+XLFwgJWSI6Dmmh6tXf/9GKpSUv3kNUHLG0C9jo0WNRpUpVhIevwh9/PBAdh7SMiUnoe5dPmcJvJRAVRyztAlaiRAm4u89CZmYmAgJ8RMchLXLu3Fn8+ut01Kw5G199lQOpVImvvsrB6tWv0bcvL9xDVByxtAvBgAGDUbduPURHb8XVq1dExyEtoFQq4e3tBQBYsqQ1jh9Px19/peL48XQWNlExxtIuBLq6uvD0nAelUomFC71ExyEtcPz4UZw8GY+OHTujRYtWouMQkYZQ6cueGRkZmD59Op4+fQqZTAZ/f3+UKVPmrceMHz8eL168gJ6eHgwMDBAeHo579+7Bw8MDEokEtWvXxty5c6GjUzz+bujQoTNatbLBkSOHkZBwEi1bthYdiTSUQqHI3cueOXOuyChEpGFUaszIyEhYWlpi69at6NOnD0JD3z1Z5v79+4iMjERERATCw8MBAL6+vnBxccHWrVuhVCrx008/5S+9FpFIJPD0nA8AmD9/DpRKpeBEpKm2bYvCpUsX0L//IDRo0FB0HCLSICqVdlJSEmxsbAAAbdq0QWJi4lvrnzx5glevXmH8+PGws7PDsWPHAABXrlxB06ZNc5+XkJCQn+xap3Fja/Tu3RfnziVh3749ouOQBkpPT4ePz3yUKFECs2ZxL5uI3vbJw+Pbtm3Dxo0b31pmZmYGY2NjAIBMJkNKSspb67OzszF69GgMHz4cL1++hJ2dHRo2bAilUgmJRPLB5/0vU1NDSKW6eRroc5ibG6v9NT9XYKA/DhzYCz+/+bC3Hww9Pb18vZ7IWdSNswALFizFw4d/YebMmWjc+Cs1p1IN3xfNxFk0U0HP8snSHjhwIAYOHPjWMicnJ6SlpQEA0tLSYGJi8tb6smXLwtbWFlKpFGZmZqhbty5+//33tz6/ft/z/tfz5+mfPcjnMjc3RnLyx/9YKEilS1eAvf1IrF8fjqCgYIwZ46jya4meRZ04C/Do0d/w8/NH2bLmcHCYpBH/P/i+aCbOopnUNcvHil+lw+NWVlaIi4sDAMTHx8Pa2vqt9QkJCXBxeXO/37S0NNy6dQs1a9bEV199hTNnzuQ+r0mTJqpsXuu5uX0PY2MTBAT48PKmlMvPzxvp6Wnw8JgNI6Ois+dBROqjUmnb2dnh1q1bsLOzQ3R0NJycnAAAAQEBuHjxItq2bYtq1aph0KBBGDNmDKZNm4YyZcrA3d0dy5Ytw+DBg5GdnY2uXbuqdRhtYW5ujmnTZuD58+cIDPQTHYc0wOXLl7B1awS+/LIuhgyxFx2HiDSURKnBpzEXxCETTTkUk5WVBRubprh//x7i4k7D0rJOnl9DU2ZRh+I8i1KpxIAB3+HEieOIitqBDh06FWC6vCnO74sm4yyaSWMPj1P+6evrw8trIXJycuDlNUt0HBIoNvYwTpw4jvbtO2pUYROR5mFpC9StWw/Y2LRDbOyPOHr0iOg4JIBcLse8eXOgo6MDL6+FouMQkYZjaQskkUgwf74PdHR04Ok5E9nZ2aIjUSGLiNiAmzdvYOjQEahbVzO+4kVEmoulLVi9evUxbNhI3Lx5A5s2rRMdhwrRixfPERCwEDKZEdzd+REJEX0aS1sDeHjM5lfAiqGAAB88ffoUU6e6oVy5cqLjEJEWYGlrgLJly8LV1Z1fAStGrl69gvXrw1Gz5hdwdJwkOg4RaQmWtoZwcHBEjRo1sW5dGG7evCE6DhUgpVKJmTOnIycnBwsX+sPAwEB0JCLSEixtDaGvr49583yQk5OD7793413AirDdu3cgIeEkunbtjo4du4iOQ0RahKWtQbp27Y5OnbrgxIk47N69Q3QcKgBpaWnw8poNAwMDzJ/vKzoOEWkZlrYGkUgkWLgwAAYGBvD0nInU1KJxlSD6f8HBQfjrrz8xceJk1KhRU3QcItIyLG0NU6NGTTg7T8Pffz9EQAD3xIqS3367hdDQEFSuXAXOzq6i4xCRFmJpa6DJk6eiWrXqCAtbiatXr4iOQ2qgVCrh7j4NWVlZWLDADzKZTHQkItJCLG0NVKJECfj6LkJOTg48PFx5UloRsG1bFE6ciEOXLt3w7be9RMchIi3F0tZQnTp1RffuPXH6dAJiYiJFx6F8eP78Gby8ZsHQ0BC+voGQSCSiIxGRlmJpazBvbz8YGsowd+5MPHnyRHQcUtGCBXPx5MkTuLl9j6pVLUTHISItxtLWYFWrWuD772fj2bNn8PT8XnQcUsHp04nYvHkj6tatB0fHiaLjEJGWY2lrOAeH8Wjc2Ao//BCNo0djRcehPMjKysKMGS4AgEWLlkJPT09wIiLSdixtDaerq4ugoGXQ1dXFjBlTkZaWJjoSfaaQkMW4fv0a7O1HoWnTZqLjEFERwNLWAvXrN8CkSVNw//49BAT4iI5Dn+Hq1StYsmQRKlashLlz54uOQ0RFBEtbS7i6uqNGjZpYvXoFLlz4VXQc+gi5XA4Xl4nIzs5GYOBSmJiUEh2JiIoIlraWKFmyJAIDg6FQKODsPAGZmZmiI9EHLFmyBOfP/4oBAwajc+duouMQURHC0tYiNjZtMWLEGFy7dpX33dZQv/12C3PmzEHZsubw9uZ7RETqxdLWMnPnLoCFRXUsW7YEZ86cER2H/kOhUMDFZRIyMzPh7x+EMmXMREcioiKGpa1ljIyMEBISCoVCgREjRuD169eiI9E/Vq1agZ9/Po1+/fqhV68+ouMQURHE0tZCLVu2xrhxE3Djxg34+i4QHYcAXLlyGT4+81C2rDlWrlwpOg4RFVEsbS01c+Zc1K5dG6tXr8Dp0wmi4xRrGRkZmDhxLLKyshAcvALlypUTHYmIiiipKk/KyMjA9OnT8fTpU8hkMvj7+6NMmTK56+Pj4xEWFgbgzS0Jk5KSsG/fPmRkZGD8+PGoXr06AMDOzg49evTI/xTFkKGhITZs2AAbGxtMmjQOx46d4leLBPHz88a1a1cwfPhoni1ORAVKpT3tyMhIWFpaYuvWrejTpw9CQ0PfWt+mTRtEREQgIiIC7dq1w9ixY/HFF1/g6tWrGDVqVO46Fnb+tGzZEi4ubnjw4D6mT3fhLTwFOHXqBFauXIaaNb/AvHkLRcchoiJOpdJOSkqCjY0NgDcFnZiY+N7H/f3339i9ezecnJwAAJcvX8bx48cxdOhQzJw5E6mpqSrGpn+5uXngm2+aYefO7YiO3io6TrHy8uULODk5QkdHBytWrIFMJhMdiYiKOInyE7tn27Ztw8aNG99aZmZmBk9PT3zxxRdQKBRo164d4uPj33mur68vLC0t0b9/fwDA9u3bUadOHdSvXx8rV67Eq1ev4O7u/sFty+U5kEp1VZmrWLl79y4aNWoEuVyOc+fOwdLSUnSkIk+pVGLAgAHYsWMH5s6dCy8vL9GRiKgY+ORn2gMHDsTAgQPfWubk5JR744q0tDSYmJi88zyFQoHjx49j6tSpucs6d+6c+9jOnTtjwYKPn/n8/Hn6pyfII3NzYyQnp6j9dUX4dxaZzAwBAUvg6DgagwbZYv/+I9DX1xcdL0+07X0JD1+FHTt2oGXL1nB0nPJWdm2b5WM4i2biLJpJXbOYmxt/cJ1Kh8etrKwQFxcH4M1JZ9bW1u885ubNm6hRowZKlCiRu2zMmDG4ePEiACAxMRH16tVTZfP0Hn37DoCt7VBcuPArvL29BKcp2s6fP4e5c2ehbNmyWLVqLaRSlc7nJCLKM5VK287ODrdu3YKdnR2io6NzP7MOCAjILeXff/8dVatWfet5Xl5e8PHxgb29Pc6dO4eJEyfmMz79l4/PItSqVRurVi3H3r27Rccpkl6+fAEHh5GQy+VYsSIMFSpUFB2JiIqRT36mLVJBHDIp6odirl+/hm7d2kMi0cGPPx5H7dra8fm2NrwvSqUSY8YMx759uzF1qhu+/97zvY/Thlk+F2fRTJxFM2ns4XHSXF9+WRdLlixHWloqRo0ayjP01WjVqhXYt283WrRohenTZ4qOQ0TFEEu7COrbdwAcHSfi5s0bmDrVid/fVoNjx37CvHmzUb58BaxevY6fYxORECztIsrTcwGaNWuB3bt3YPXqFaLjaLU7d25j3LhRkEql2LBhCz/HJiJhWNpFlJ6eHsLDN6JcufLw8pqN2NjDoiNppZSUVxg+3BYvX75AYGAwrK2/ER2JiIoxlnYRVr58BWzaFAl9fX2MHTsKV65cFh1JqygUCkyaNA43b96Ao+NE2NoOFR2JiIo5lnYRZ2XVBCtWrEFaWiqGDRuER48eiY6kNby9vXDo0AHY2LTD3LneouMQEbG0i4Nevfpg1qy5+PPPPzB8+GCkp6v/SnNFTVjYSixfvhS1atVGWNh6nnhGRBqBpV1MODtPw+DBQ/Drr+cwceJY5OTkiI6ksfbs2YnZsz1Qrlx5REXtQJkyZqIjEREBYGkXGxKJBEFBIWjVygYHDuyFq6szFAqF6FgaJyHhJCZOHAuZzAiRkdthYVFNdCQiolws7WJEX18fmzZF4uuvG2Pr1gjMnTuT3+H+j6tXr2D4cDsoFAqsX78ZDRo0FB2JiOgtLO1ixtjYBFFRO1CnzpdYvToUgYF+oiNphOvXr2HAgF549eolgoND0bZte9GRiIjewdIuhszMzBATswsWFtWxaJEvVq1aLjqSUDduXEe/fj3x5MkTLFq0FAMH2oqORET0XiztYqpixUr44YfdKF++Ajw9Z2L58mDRkYS4devmP4WdDH//xRgxYrToSEREH8TSLsaqV6+BnTv3o1Klypg/fw78/LyL1Wfct27dRN++3yI5+TF8fQMxapSD6EhERB/F0i7matWqjT17DqF69RpYvDgAnp7F4+S0s2d/Rq9eXfD48SP4+ARgzJhxoiMREX0SS5tgYVENe/Yc+ufktBVwdXWGXC4XHavAHDp0AP3798LLly+xZMlyODiMFx2JiOizsLQJAFChQkXs2nUQDRs2wubNG2Fr2x8vXjwXHUvtNm1aj5Ejh0AikWDTpkgMHTpcdCQios/G0qZcZmZm2LVrP7p27Y74+GPo3r0jbt++JTqWWsjlcixYMBdublNgamqKHTv2oXPnbqJjERHlCUub3mJkZIwNG7Zi8uSpuH37N3Tr1hFxccdEx8qXx48fY9CgPli2bAlq1KiJ/fuPwMqqiehYRER5xtKmd+jq6mLOnHlYtmwVXr9Ox+DBfeHn543s7GzR0fLszJnT6NTJBidPxqN795748cfjqFmzluhYREQqYWnTBw0ePAS7dh1AlSpVsXhxAHr37oo7d26LjvVZ5HI5QkKWoG/fHkhOfgxPzwXYsGELSpUqLToaEZHKWNr0UU2aNMXRoycxYMBgJCWdRYcOrbF1a4RGfy3s8uVL6N69I7y958LUtAy2b98LJ6cpkEgkoqMREeULS5s+ycSkFEJDw7Bq1VpIpVK4uEzCd991x6VLF0RHe0tGRgZ8fOajS5e2uHDhVwwaZIcTJ86gZcvWoqMREakFS5s+W79+A3H8eAJ69OiF06cT0KlTG7i5ueDp06dCcymVSuzduwtt2jTD0qWBqFChIqKidmD58tW8FzYRFSksbcqTKlWqYsOGLdi2bTcsLetg06Z1aNasERYt8i3073UrlUocOXII3bt3wJgxw/HHHw/g6DgR8fGn0aFDp0LNQkRUGFjapJK2bdvj6NFT8Pb2g1Sqi0WLfGFlVR+zZ7vjzp3fCnTb6enp2LJlEzp0aI2hQwfh3Lkk9Oz5HU6e/BkLFvjByMi4QLdPRCRKvkr7yJEjcHV1fe+6mJgY9OvXD4MGDcKxY2++5/vs2TOMHj0aQ4YMgYuLC16/fp2fzZNgenp6GDduIs6evQxPzwWQyWRYs2Ylmje3Qu/e3bBx4zo8evQo9/E7d0rRtq0hKlY0Qtu2hti5U/rZ28rKykJc3DG4uExCgwaWmDrVCdevX0WfPv1w/Hgi1q2L4Fe5iKjIkyhVPA3Y29sbJ0+eRN26dbFkyZK31iUnJ2P06NHYvn07MjMzMWTIEGzfvh0BAQH46quv0K9fP6xZswb6+voYOXLkB7eRnJyiSrSPMjc3LpDXFUHTZsnKysKBA3uxadN6nDp1IvcM80aNGsPc3BlHjox85zmrV79G377yd2Z58eI5rl+/jnPnzuLMmUScOBGH1NQ36ytVqozBg+0wYsQYVKpUuVBmywtNe1/yg7NoJs6imdQ1i7n5h48Wfv6uzv+wsrJCp06dEB0d/c66ixcvonHjxtDX14e+vj4sLCxw/fp1JCUlwdHREQDQpk0bLF68+KOlTdpFX18fffr0R58+/fHnn39gz55diI09jMTEU5DLrd77HFfXh9izZyp0dJR4+TIVT58+wd9///XOyW3VqlWHnd1Q9OjRCy1atIKODj/ZIaLi55OlvW3bNmzcuPGtZT4+PujRowfOnDnz3uekpqbC2Pj//1KQyWRITU19a7lMJkNKysf/IjE1NYRUqvvJIfLqY3/FaBtNncXcvC4aNaoLT8/vkZaWBhOTklAo3n1campV7N+/J/dnY2NjVKxYEc2aNUPdunVhbW2NVq1awcLCohDT55+mvi+q4CyaibNopoKe5ZOlPXDgQAwcODBPL2pkZIS0tLTcn9PS0mBsbJy7vESJEv/8Q27y0dd5/jw9T9v9HDwUI0adOkpcu/bu8i+/BHbu/B0VK5oiNVUOfX399z5fW+YE+OvYugAACclJREFUtOt9+RTOopk4i2YqjMPjBXKMsWHDhkhKSkJmZiZSUlJw+/ZtWFpawsrKCnFxcQCA+Ph4WFtbF8TmSQO5uGS9d/nUqXKYmZmhVKlSHyxsIiJ6Q+XPtN9n/fr1sLCwQMeOHWFvb48hQ4ZAqVRi6tSpMDAwwIQJE+Du7o6YmBiYmpoiKChInZsnDda3rxzAawQH6+PmTR1YWiowZUrWP8uJiOhzqHz2eGHg2eMfx1k0E2fRTJxFM3GW97/Oh/AUXCIiIi3B0iYiItISLG0iIiItwdImIiLSEixtIiIiLcHSJiIi0hIsbSIiIi3B0iYiItISLG0iIiItodFXRCMiIqL/xz1tIiIiLcHSJiIi0hIsbSIiIi3B0iYiItISLG0iIiItwdImIiLSElLRAQrSkSNHcOjQIQQFBb2zLiYmBlFRUZBKpZgwYQLat2+PZ8+ewc3NDRkZGShXrhx8fX1RsmRJAcn/X0ZGBqZPn46nT59CJpPB398fZcqUyV0fHx+PsLAwAIBSqURSUhL27duHjIwMjB8/HtWrVwcA2NnZoUePHiJGyPWpWQBg/PjxePHiBfT09GBgYIDw8HDcu3cPHh4ekEgkqF27NubOnQsdHbF/b37OLP7+/jh37hzkcjkGDx6MQYMG4cWLF+jatSssLS0BAJ06dcKIESMKPb9CoYCXlxdu3LgBfX19eHt7o1q1arnrteX3A/j0LBs2bMD+/fsBAG3btoWTkxOUSiXatGmT+/vRqFEjuLq6ioj/lk/N4u3tjXPnzkEmkwEAQkNDkZ2drXXvy7Vr1+Dj45P72PPnz2PFihVo2LChRvx+fMiFCxcQGBiIiIiIt5YfPXoUK1asgFQqRf/+/TFo0KDP+jdCJcoiasGCBcquXbsqXVxc3ln3+PFjZc+ePZWZmZnKV69e5f73ggULlNu3b1cqlUrl6tWrlevXry/k1O9at26dMiQkRKlUKpX79u1TLliw4IOPDQsLUwYFBSmV/9fe3YU0+cVxAP/mNmfNFaVFdTFwQqGO4VREgrrRoUYQJWOaNux1YiI1kMVKC7e8ECRIe6EXortadlFCZTfZIJcwF8lGwzC1vEgz0PZSez3/C/Gh1Zza/++2x//53O1sB35fzn7Pced5QEKI0Wgkd+7ciUmNS7WULOXl5SQUCoWNqdVq8ubNG0IIIc3NzeTFixcrX+wiFstiNptJfX09IYQQr9dLSkpKyMzMDHn9+jVpbW2Neb2/6+3tJVqtlhBCyNu3b0ldXR3zHpv6g5DoWT59+kQOHDhAAoEACQaDRKlUkvfv35OxsTGiVqvjVfKComUhhJDKykry7du3sDE2rsuvnj59SjQaDSGEJEx/RHLz5k2yb98+olAowsZ9Ph/T316vlxw8eJBMTU0t69q9HKv2eDwvLw8XL16M+N7Q0BBkMhmSk5MhFAohEongcDgwODiI3bt3AwD27NmD/v7+GFYc2e81mc3miJ/78uULHj9+jIaGBgCAzWZDX18fqqurodPp4HK5YlbzQhbLMj09je/fv6Ourg5VVVV4+fIlAMBut6OwsJCZx4Z1kclkYb8kgsEguFwubDYb7HY7ampq0NjYiKmpqZjWPe/X+nNzc2Gz2Zj32NQfQPQsW7duxe3bt8HhcJCUlIRAIAA+nw+73Y7JyUkcPnwYJ06cwMePH+NVfphoWUKhEMbHx9HS0oLKykp0d3f/MYct6zLP4/Ggs7MT586dA4CE6Y9IRCIROjs7/xgfGRmBSCTChg0bkJycjPz8fFgsliVfu5eL9cfjDx8+xL1798LG2trasHfvXgwMDESc43K5IBQKmdcCgQAulytsXCAQwOl0rlzhEUTKkpaWtqSa7t69i9raWiQnJwMApFIpFAoFJBIJrl+/jqtXr0Kr1a5sgF/8TRa/34+jR49CpVJhdnYWVVVVkEqlIIRgzZo1C85baX+Thc/ng8/nw+/34+zZs1AqlRAIBBCLxZBIJNi1axeePHkCg8GAK1euxCzLPJfLhdTUVOY1h8NBIBAAl8tN2P5YSLQsPB4PmzZtAiEE7e3tyM7ORkZGBqanp3Hy5EmUl5fDYrGgqakJjx49imOKOdGyeDwe1NTU4MiRIwgGg1CpVJBIJKxcl3nd3d0oKytjjo0TpT8iKS0txcTExB/jse4X1m/aCoUCCoViWXNSU1PhdruZ1263G0KhkBlPSUmB2+3G+vXr/+tyo4qUpaGhgal1oZpCoRD6+vpw5swZZkwulzOflcvl0Ov1K1j5n/4mS3p6OiorK8HlcpGWloasrCyMjo6G3b9m07rMzs6isbERhYWFUKvVAICioiLmfqNcLo/bBen3HgiFQszFNFH7YyHRsgCA1+uFTqeDQCDAhQsXAAASiQQcDgcAUFBQgMnJybA/DuMlWpa1a9dCpVIx35+ioiI4HA7WrgsA9PT0hPVAovTHcizWL/Nj/9W6rNrj8WikUikGBwfh9XrhdDoxMjKCHTt2IC8vD69evQIw94BXfn5+nCvFkmoaHh5GRkYGUlJSmLFjx45haGgIAGA2m5GTkxObgqNYLEt/fz9Onz4NYO5L/uHDB4jFYmRnZzOnJiaTCQUFBbEtPILFsvz8+RO1tbWoqKjAqVOnmPHz58+jt7cXQHzXJS8vDyaTCcDcQ0DzD/4A7OoPIHoWQgjq6+uxc+dOtLa2Mht1V1cXc3ricDiwffv2uG/YQPQsY2NjOHToEILBIPx+P6xWK3Jycli5LgDgdDrh8/mwbds2ZixR+mM5MjMzMT4+jpmZGfh8PlgsFshkshVbl1X9D0MGBgZw//59XL58GcDcEbJIJEJxcTGMRiMePHgAQgjUajVKS0sxPT0NrVYLt9uNjRs3oqOjA+vWrYtrhh8/fkCr1eLr16/g8Xjo6OjA5s2b0d7ejrKyMkilUjx79gxWq5W5LwTM3QfW6/Xg8XhIT0+HXq8PO6qKh6VkuXTpEt69e4ekpCQcP34cJSUlGB0dRXNzM/x+P8RiMQwGA3PxTdQsVqsVXV1dyMrKYubM3+PW6XQA5n45GQwGbNmyJeb1zz/ZOzw8DEII2traYDKZWNcfi2UJhULQaDTIzc1lPq/RaCAWi9HU1ASPxwMOh4OWlhZkZmbGMcWcxdbl1q1beP78OXg8Hvbv34+qqipWrktxcTGGhoZw48YNXLt2jZnz+fPnhOiPhUxMTECj0cBoNKKnpwcejwdKpZJ5epwQgoqKClRXVy94jfi3VvWmTVEURVGryf/yeJyiKIqi2Ihu2hRFURTFEnTTpiiKoiiWoJs2RVEURbEE3bQpiqIoiiXopk1RFEVRLEE3bYqiKIpiCbppUxRFURRL/ANxvjy29x8KpwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 576x396 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Trực quan hóa hàm f và 2 điểm dữ liệu được phát sinh ở trên\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "plt.style.use(\"seaborn\")\n",
    "\n",
    "xx = np.arange(-1, 1, 0.01).reshape(-1, 1)\n",
    "yy = np.sin(np.pi * xx)\n",
    "plt.plot(xx, yy, color=\"black\")\n",
    "plt.plot(X, Y, \"o\", color=\"blue\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "**Code dùng cho câu 4,5,6:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Tìm a^ của g^ = a^.x\n",
    "def get_a_list(N):\n",
    "    a = []\n",
    "    for i in range(N):\n",
    "        X, Y = generate_dataset(2)\n",
    "        # Tìm w (tương tự a)\n",
    "        X_dagger = np.dot(np.linalg.inv(np.dot(X.T, X)), X.T)\n",
    "        w = np.dot(X_dagger, Y)\n",
    "        a.append(w)\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "g^ =  1.42 x\n"
     ]
    }
   ],
   "source": [
    "# g_mean = a_mean*x\n",
    "# a_list và a_hat dùng chung cho câu 5 và 6.\n",
    "a_list = get_a_list(10000)\n",
    "a_hat = np.mean(a_list)\n",
    "print(\"g^ = \", np.round(a_hat, 2), \"x\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "efabab5c4035a6864ac8cb3e0061c6f0",
     "grade": true,
     "grade_id": "c4",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE Giá trị của a^ xoay quanh 1.4, không khớp với các đáp án mà đề cho. Do đó, em chọn đáp án [e]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Câu 5 (1 điểm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Theo công thức lý thuyết đã học:\n",
    "$$bias = \\mathbb{E}_\\mathbf{x}\\left[(\\bar{g}(\\mathbf{x}) - f(\\mathbf{x}))^2\\right]$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "bias = 0.27\n"
     ]
    }
   ],
   "source": [
    "X, Y = generate_dataset(10000)\n",
    "bias = np.mean((a_hat * X - Y)**2)\n",
    "print(\"bias =\", np.round(bias, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "0b484b8390bec96142e8a1213ee8cd2c",
     "grade": true,
     "grade_id": "c5",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE Giá trị của bias xoay quanh 0.27. Do đó, em chọn đáp án [b]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Câu 6 (1 điểm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$var =  \\mathbb{E}_\\mathbf{x}\\left[\\mathbb{E}_\\mathcal{D}\\left[(g^{(\\mathcal{D})}(\\mathbf{x}) - \\bar{g}(\\mathbf{x}))^2\\right]\\right]$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "variance = 0.24\n"
     ]
    }
   ],
   "source": [
    "# variance = np.mean((np.outer(a_list, X) - a_hat * X)**2)\n",
    "variance = np.mean((X*a_list - a_hat * X)**2)\n",
    "print(\"variance =\", np.round(variance, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "26f542221236fb24d0ddbee584eed7d0",
     "grade": true,
     "grade_id": "c6",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE Giá trị của variance xoay quanh 0.24. Do đó, em chọn đáp án [a]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Câu 7 (1 điểm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "$$\\mathbb{E}_\\mathbf{D}\\left[\\mathbb{E}_\\mathcal{out}(g^{(\\mathcal{D})})\\right] = bias + variance$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "- Tại $H(x) = b$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_b_list(N=10000):\n",
    "    b = []\n",
    "    for i in range(N):\n",
    "        X, Y = generate_dataset(2)\n",
    "        b.append(np.mean(Y))\n",
    "    return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eout = bias + varinace = 0.49 + 0.26 = 0.75\n"
     ]
    }
   ],
   "source": [
    "b_list = get_b_list()\n",
    "b_hat = np.mean(b_list)\n",
    "bias = np.mean((b_hat - Y)**2)\n",
    "variance = np.mean((b_list - b_hat)**2)\n",
    "print(\"Eout = bias + varinace = {} + {} = {}\".format(np.round(bias, 2),\n",
    "                                                   np.round(variance, 2),\n",
    "                                                   np.round(bias + variance, 2))) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "- Tại $H(x) = ax$\n",
    "\n",
    "Dạng này tương tự câu 4,5 và 6. Do đó ta có kết quả: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eout = bias + varinace = 0.28 + 0.24 = 0.52\n"
     ]
    }
   ],
   "source": [
    "a_list = get_a_list(10000)\n",
    "a_hat = np.mean(a_list)\n",
    "bias = np.mean((a_hat * X - Y)**2)\n",
    "variance = np.mean((X*a_list - a_hat * X)**2)\n",
    "print(\"Eout = bias + varinace = {} + {} = {}\".format(np.round(bias, 2),\n",
    "                                                   np.round(variance, 2),\n",
    "                                                   np.round(bias + variance, 2))) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "- Tại $H(x) = ax + b$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_a_b_list(N=10000):\n",
    "    a_list = []\n",
    "    b_list = []\n",
    "    for i in range(N):\n",
    "        X, Y = generate_dataset(2)\n",
    "        a = (Y[1]-Y[0])/(X[1]- X[0])\n",
    "        b = Y[1] - a*X[1]\n",
    "        a_list.append(a)\n",
    "        b_list.append(b)\n",
    "    return a_list, b_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eout = bias + varinace = 0.2 + 1.68 = 1.89\n"
     ]
    }
   ],
   "source": [
    "a_list, b_list = get_a_b_list()\n",
    "a_hat = np.mean(a_list)\n",
    "b_hat = np.mean(b_list)\n",
    "bias = np.mean((a_hat*X + b_hat - Y)**2)\n",
    "variance = np.mean((a_list*X + b_list - a_hat*X  - b_hat)**2)\n",
    "print(\"Eout = bias + varinace = {} + {} = {}\".format(np.round(bias, 2),\n",
    "                                                   np.round(variance, 2),\n",
    "                                                   np.round(bias + variance, 2))) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "- Tại $H(x) = ax^2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "#Tìm a^ của g^ = (a^)x^2\n",
    "def get_a_list2(N):\n",
    "    a = []\n",
    "    a_value = 0\n",
    "    for _ in range(N):\n",
    "        # two random points\n",
    "        X,Y = generate_dataset(2)\n",
    "        a_value = (X[0]**2 * Y[0] + X[1]**2 * Y[1]) / (X[0]**4 + X[1]**4)\n",
    "        a.append(a_value)\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eout = bias + varinace = 0.5 + 19.08 = 19.58\n"
     ]
    }
   ],
   "source": [
    "a_list = get_a_list2(100000)\n",
    "a_hat = np.mean(a_list)\n",
    "X, Y = generate_dataset(100000)\n",
    "bias = np.mean((a_hat*(X**2) - Y)**2)\n",
    "variance = np.mean((a_list * X**2 - (a_hat * X**2))**2)\n",
    "print(\"Eout = bias + varinace = {} + {} = {}\".format(np.round(bias, 2),\n",
    "                                                   np.round(variance, 2),\n",
    "                                                   np.round(bias + variance, 2))) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "- Tại $H(x) = ax^2 + b$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Tìm a^ của g^ = (a^)x^2 + b^\n",
    "def get_a_b_list2(N):\n",
    "    a = []\n",
    "    a_value = 0\n",
    "    b = []\n",
    "    b_value = 0\n",
    "    for _ in range(N):\n",
    "       # two random points\n",
    "        X,Y = generate_dataset(2)\n",
    "       \n",
    "        i = (X[0]**2 + X[1]**2)\n",
    "        j = (Y[0] + Y[1])\n",
    "        k = (X[0]**4 + X[1]**4)\n",
    "        m = (X[0]**2 * Y[0] + X[1]**2 * Y[1])\n",
    "\n",
    "        a_value = (2 * m - i * j) / (2 * k - i ** 2)\n",
    "        b_value = (j * k - i * m) / (2 * k - i ** 2)\n",
    "        a.append(a_value)\n",
    "        b.append(b_value)\n",
    "    return a,b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eout = bias + varinace = 3.62 + 9790.06 = 9793.68\n"
     ]
    }
   ],
   "source": [
    "a_list, b_list  = get_a_b_list2(10000)\n",
    "a_hat = np.mean(a_list)\n",
    "b_hat = np.mean(b_list)\n",
    "X, Y = generate_dataset(10000)\n",
    "bias = np.mean((a_hat*(X**2) + b_hat - Y)**2)\n",
    "variance = np.mean((a_list * X**2 + b_list - (a_hat * X**2 + b_hat))**2)\n",
    "print(\"Eout = bias + varinace = {} + {} = {}\".format(np.round(bias, 2),\n",
    "                                                   np.round(variance, 2),\n",
    "                                                   np.round(bias + variance, 2))) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "322a244b0fae3a20ec568a5099aaaec1",
     "grade": true,
     "grade_id": "c7",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE Ta thấy kết quả tại H(x) = ax bằng 0.5 là nhỏ nhất. Do đó, em chọn đáp án [b]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Câu 8 (1 điểm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Theo đề bài:\n",
    "- $m_\\mathcal{H}(1)=2$.\n",
    "- $m_\\mathcal{H}(N+1) = 2m_\\mathcal{H}(N) - \\binom{N}{q}$ với $q$ là một số nguyên cố định $\\ge1$. Để dễ nhìn hơn, ta có thể viết lại công thức này như sau: $m_\\mathcal{H}(N) = 2m_\\mathcal{H}(N-1) - \\binom{N-1}{q}$.\n",
    "\n",
    "Bây giờ, thử tăng $N$ dần lên ($N = 1, 2, 3, ...$). Khi nào thì $m_\\mathcal{H}(N)$ sẽ bị break?\n",
    "\n",
    "Với $N = d$ là break point thì  $m_\\mathcal{H}(d)=2^d$. Khi đó phương trình trên trở thành:\n",
    "\n",
    "- $2^d = 2.2^{d-1} - \\binom{d-1}{q}$ <=> $\\binom{d-1}{q} = 0$ <=> $d<q+1$\n",
    "\n",
    "hay:\n",
    "\n",
    "- $d\\le q$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "q = 2   N = 1   m_H = 2  2^N = 2 shattered? True\n",
      "q = 2   N = 2   m_H = 4  2^N = 4 shattered? True\n",
      "q = 2   N = 3   m_H = 7  2^N = 8 shattered? False\n",
      "q = 2   N = 4   m_H = 11  2^N = 16 shattered? False\n",
      "q = 2   N = 5   m_H = 16  2^N = 32 shattered? False\n",
      "q = 2   N = 6   m_H = 22  2^N = 64 shattered? False\n",
      "q = 2   N = 7   m_H = 29  2^N = 128 shattered? False\n",
      "q = 2   N = 8   m_H = 37  2^N = 256 shattered? False\n",
      "q = 2   N = 9   m_H = 46  2^N = 512 shattered? False\n",
      "\n",
      "Result: VC dimension d_vc = 2, q = 2\n",
      "q = 3   N = 1   m_H = 2  2^N = 2 shattered? True\n",
      "q = 3   N = 2   m_H = 4  2^N = 4 shattered? True\n",
      "q = 3   N = 3   m_H = 8  2^N = 8 shattered? True\n",
      "q = 3   N = 4   m_H = 15  2^N = 16 shattered? False\n",
      "q = 3   N = 5   m_H = 26  2^N = 32 shattered? False\n",
      "q = 3   N = 6   m_H = 42  2^N = 64 shattered? False\n",
      "q = 3   N = 7   m_H = 64  2^N = 128 shattered? False\n",
      "q = 3   N = 8   m_H = 93  2^N = 256 shattered? False\n",
      "q = 3   N = 9   m_H = 130  2^N = 512 shattered? False\n",
      "\n",
      "Result: VC dimension d_vc = 3, q = 3\n",
      "q = 4   N = 1   m_H = 2  2^N = 2 shattered? True\n",
      "q = 4   N = 2   m_H = 4  2^N = 4 shattered? True\n",
      "q = 4   N = 3   m_H = 8  2^N = 8 shattered? True\n",
      "q = 4   N = 4   m_H = 16  2^N = 16 shattered? True\n",
      "q = 4   N = 5   m_H = 31  2^N = 32 shattered? False\n",
      "q = 4   N = 6   m_H = 57  2^N = 64 shattered? False\n",
      "q = 4   N = 7   m_H = 99  2^N = 128 shattered? False\n",
      "q = 4   N = 8   m_H = 163  2^N = 256 shattered? False\n",
      "q = 4   N = 9   m_H = 256  2^N = 512 shattered? False\n",
      "\n",
      "Result: VC dimension d_vc = 4, q = 4\n",
      "q = 5   N = 1   m_H = 2  2^N = 2 shattered? True\n",
      "q = 5   N = 2   m_H = 4  2^N = 4 shattered? True\n",
      "q = 5   N = 3   m_H = 8  2^N = 8 shattered? True\n",
      "q = 5   N = 4   m_H = 16  2^N = 16 shattered? True\n",
      "q = 5   N = 5   m_H = 32  2^N = 32 shattered? True\n",
      "q = 5   N = 6   m_H = 63  2^N = 64 shattered? False\n",
      "q = 5   N = 7   m_H = 120  2^N = 128 shattered? False\n",
      "q = 5   N = 8   m_H = 219  2^N = 256 shattered? False\n",
      "q = 5   N = 9   m_H = 382  2^N = 512 shattered? False\n",
      "\n",
      "Result: VC dimension d_vc = 5, q = 5\n"
     ]
    }
   ],
   "source": [
    "def N_choose_k(N, k):\n",
    "    if k > N: return 0\n",
    "    return math.factorial(N) // (math.factorial(k) * math.factorial(N-k))\n",
    "\n",
    "def m_H(N, q):\n",
    "    if N == 1:\n",
    "        return 2 \n",
    "    return 2 * m_H(N-1, q) - N_choose_k(N-1, q)\n",
    "\n",
    "\n",
    "def get_N(Nmax,q): #Nmax: giá trị giới hạn, chạy từ 1->Nmax\n",
    "    d_vc = -1\n",
    "    for N in range(1,Nmax):\n",
    "        shattered = (m_H(N, q) == 2**N)\n",
    "        if shattered:\n",
    "            d_vc = N\n",
    "        print(\"q = {}   N = {}   m_H = {}  2^N = {} shattered? {}\".format(q,N,m_H(N, q),2**N,shattered))\n",
    "\n",
    "    print(\"\\nResult: VC dimension d_vc = {}, q = {}\".format(d_vc,q))\n",
    "\n",
    "get_N(10,2)\n",
    "get_N(10,3)\n",
    "get_N(10,4)\n",
    "get_N(10,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "d81773f072cd15e4a27b6cd240a5d990",
     "grade": true,
     "grade_id": "c8",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE Ta thấy các kết quả thử đều cho ra d_vc = q. Do đó, em chọn đáp án [c]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Câu 9 (1 điểm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\bigcap_{k=1}^{K} H_k$ là tập giả thuyết nhỏ nhất trong các tập $H$ đang xét vì là phép giao. Nên nó có thể bị phá vỡ bỡi bất cứ $d_{vc}$ của tập $H_i$ nào.\n",
    "\n",
    "Do đó: \n",
    "- $d_{vc}(\\bigcap_{k=1}^{K} H_k) \\leq d_{vc}(H_i)$   (với $1\\leq i \\leq K$)\n",
    " \n",
    "Hay: \n",
    "- $d_{vc}(\\bigcap_{k=1}^{K} H_k) \\leq min\\{d_{vc}(H_i)\\}$ \n",
    "\n",
    "Ở trường hợp xấu nhất, có thể tồn tại 2 tập $H$ không trùng nhau hay $H_1 \\cap H_2 = \\theta => d_{vc}(\\bigcap_{k=1}^{K} H_k) = 0$. \n",
    "\n",
    "**Vậy**: \n",
    "- $0 \\leq d_{vc}(\\bigcap_{k=1}^{K} H_k) \\leq min\\{d_{vc}(H_i)\\}$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e814a2db0b8a53e4fddfee4bcbf405fc",
     "grade": true,
     "grade_id": "c9",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE Do đó, em chọn đáp án [b]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Câu 10 (1 điểm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Chặn dưới:**\n",
    "\n",
    "Vì chúng ta hợp các giả thuyết lại với nhau, nên tập hợp các bộ giả thuyết phải có $d_{vc}$ lớn nhất bằng $d_{vc}$ lớn nhất trong số các bộ. Ít nhất, chúng ta bảo toàn khả năng phá vỡ một tập hợp các điểm lớn bằng tập hợp các điểm lớn nhất có thể bị phá vỡ bởi một trong những giả thuyết ban đầu được đặt riêng lẻ. \n",
    "\n",
    "Do đó: \n",
    "- $max\\{ d_{vc}(H_k)\\}_{k=1}^{K} \\leq d_{vc}(\\bigcup_{k=1}^{K} H_k)$\n",
    "\n",
    "**Chặn trên:**\n",
    "- (phần này em không biết chứng minh ạ!)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "41cbf5c6d2b94eeae0a712be2181fef6",
     "grade": true,
     "grade_id": "c10",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "YOUR ANSWER HERE Do đó, em chọn đáp án [e]"
   ]
  }
 ],
 "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.6"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}