1612835_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bài tập 1\n",
    "\n",
    "\n",
    "Bùi Trọng Xuyến - 1612835\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. \n",
    "- (i) Vì chúng ta đã có yếu tố định lượng giá trị cho các đồng xu, nghĩa là đã có công thức xác định cụ thể nên không phải là máy học.\n",
    "- (ii) Đưa ra các input và output đúng, học dựa trên data nên nó là học có dám sát.\n",
    "- (iii) Từ dữ liệu, phát triển ra thêm các dữ liệu khác nên nó là học tăng cường.\n",
    "\n",
    "Do đó, đáp án đúng là: [d] (i) Not learning, (ii) Supervised Learning, (iii) Reinforcement Learning.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.\n",
    "- (i) Phân loại số nguyên tố hay không nguyên tố - đã có công thức xác định.\n",
    "- (ii) Phát hiện gian lận trong chí phí card - chưa có công thức, học từ dữ liệu nên có thể áp dụng máy học.\n",
    "- (iii) Xác định thời gian rơi - dùng công thức rơi tự do trong toán học.\n",
    "- (iv) Xác định chu kì tối ưu cho đèn giao thông - tình hình mỗi nơi khác nhau nên sẽ không có công thức cụ thể, học từ dữ liệu nên có thể áp dụng máy học.\n",
    "\n",
    "Do đó, đáp án đúng là [a] (ii) và (iv)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.\n",
    "Dùng Xác suất có điều kiện:\n",
    "- Xác suất lấy viên đầu tiên là màu đen: P(A) = 1/2 + 1/2*1/2 = 3/4\n",
    "- Xác suất lấy cả 2 viên màu đen (nghĩa là chung 1 bin): P(FA) = 1/2\n",
    "- Suy ra xác suất lấy viên bi đen khi biết trước đó đã lấy được 1 viên đen: P(F|A) = P(FA)/P(A) = 2/3\n",
    "\n",
    "Do đó, đáp áp đúng là [d] 2/3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.\n",
    "- Xác xuất để không nhận được viên bi đỏ là p = 0.45.\n",
    "- Vậy xác suất để nhận mẫu 10 viên không viên nào màu đỏ là\n",
    "p_result = p^10 = 0.45^10 = 3.405 x 10^-4.\n",
    "\n",
    "Do đó, đá án đúng là [b]. 3.405 x 10^-4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.\n",
    "- Để tính xác suất trong 1000 mẫu có ít nhất 1 mẫu có v = 0, ta sẽ tính xác xuất không có mẫu nào có v = 0.\n",
    "- Xác suất để 1 mẫu v khác 0 là: p = 1 - 3.405 x 10^-4 = 0.9996595.\n",
    "- Xác suất để 1000 mẫu không có mẫu nào v = 0 là: ptmp = 0.9996595 ^ 1000.\n",
    "- Kết quả cuối cùng là: pResult = 1 - ptmp = 0.289.\n",
    "\n",
    "Do đó, đáp án chính xác là [c]. 0.289"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.\n",
    "- Vì giá trị trả về là 0 hoặc 1 nên có thể quy định:\n",
    "    Trả về 0 cho 3 điểm\n",
    "    Trả về 1 cho 3 điềm\n",
    "    Trả về 0 nếu là lẻ hoặc\n",
    "    Trả về 1 nếu là chẵn.\n",
    "\n",
    "Do đó, đáp án đúng là [e]. They are all equivalent (equal scores for g in [a] through [d])."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7-10. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Import các thư viện cần thiết"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Định nghĩa các hàm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hàm phát sinh ra `target_w`, véc-tơ tham số của $f$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_target_w():\n",
    "    \"\"\"\n",
    "    Generates target_w from two random, uniformly distributed points in [-1, 1] x [-1, 1].\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    target_w : numpy array, shape (3, 1) \n",
    "        The vector of parameters of f.\n",
    "    \"\"\"\n",
    "    # Generate two points from a uniform distribution over [-1, 1]x[-1, 1]\n",
    "    p1 = np.random.uniform(-1, 1, 2)\n",
    "    p2 = np.random.uniform(-1, 1, 2)\n",
    "    # Compute the target W from these two points\n",
    "    target_w = np.array([p1[1]*p2[0] - p1[0]*p2[1], p2[1] - p1[1], p1[0] - p2[0]]).reshape((-1, 1))\n",
    "    \n",
    "    return target_w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hàm phát sinh ra tập dữ liệu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_data(N, target_w):\n",
    "    \"\"\"\n",
    "    Generates a data set by generating random inputs and then using target_w to generate the \n",
    "    corresponding outputs.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    N : int\n",
    "        The number of examples.\n",
    "    target_w : numpy array, shape (3, 1) \n",
    "        The vector of parameters of f.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    X : numpy array, shape (N, 3)\n",
    "        The matrix of input vectors (each row corresponds to an input vector); the first column of \n",
    "        this matrix is all ones.\n",
    "    Y : numpy array, shape (N, 1)\n",
    "        The vector of outputs.        \n",
    "    \"\"\"\n",
    "    bad_data = True # `bad_data = True` means: data contain points on the target line \n",
    "                    # (this rarely happens, but just to be careful)\n",
    "                    # -> y's of these points = 0 (with np.sign); \n",
    "                    #    we don't want this (y's of data must be -1 or 1)\n",
    "                    # -> re-generate data until `bad_data = False`\n",
    "    \n",
    "    while bad_data == True:\n",
    "        X = np.random.uniform(-1, 1, (N, 2))\n",
    "        X = np.hstack((np.ones((N, 1)), X)) # Add 'ones' column\n",
    "        Y = np.sign(np.dot(X, target_w))\n",
    "        if (0 not in Y): # Good data\n",
    "            bad_data = False\n",
    "    \n",
    "    return X, Y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hàm chạy PLA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def h(w, x):\n",
    "    return np.sign(np.dot(w.T, x))\n",
    "def has_converged(X, Y, w):\n",
    "    return np.array_equal(h(w, X).T, Y)\n",
    "def run_PLA(X, Y):\n",
    "    \"\"\"\n",
    "    Runs PLA.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    X : numpy array, shape (N, 3)\n",
    "        The matrix of input vectors (each row corresponds to an input vector); the first column of \n",
    "        this matrix is all ones.\n",
    "    Y : numpy array, shape (N, 1)\n",
    "        The vector of outputs.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    w : numpy array, shape (3, 1) \n",
    "        The vector of parameters of g.\n",
    "    num_iterations : int\n",
    "        The number of iterations PLA takes to converge.\n",
    "    \"\"\"\n",
    "    w = np.zeros((X.shape[1], 1)) # Init w\n",
    "    iteration = 0\n",
    "    \n",
    "    # TODO\n",
    "    X = X.T\n",
    "    while True:\n",
    "        \"\"\"\n",
    "        PLA algorithm\n",
    "        \"\"\"\n",
    "        mix_id = np.random.permutation(X.shape[1])\n",
    "        for i in range(X.shape[1]):\n",
    "            xi = X[:, mix_id[i]].reshape(X.shape[0], 1)\n",
    "            yi = Y[mix_id[i], 0]\n",
    "            if h(w, xi)[0][0] != yi:\n",
    "                iteration += 1\n",
    "                w = w + yi*xi\n",
    "        if has_converged(X, Y, w) == True:\n",
    "            break\n",
    "    X = X.T\n",
    "    \n",
    "    return w, iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hàm main"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def main(N):\n",
    "    \"\"\"\n",
    "    Parameters\n",
    "    ----------\n",
    "    N : int\n",
    "        The number of training examples.\n",
    "    \"\"\"\n",
    "    num_runs = 1000\n",
    "    avg_num_iterations = 0.0 # The average number of iterations PLA takes to converge\n",
    "    avg_test_err = 0.0 # The average test error of g - the final hypothesis picked by PLA\n",
    "    \n",
    "    for r in range(num_runs):\n",
    "        # Generate target_w\n",
    "        target_w = generate_target_w()\n",
    "        \n",
    "        # Generate training set\n",
    "        X, Y = generate_data(N, target_w)\n",
    "        \n",
    "        # Run PLA to pick g\n",
    "        w, num_iterations = run_PLA(X, Y)\n",
    "        \n",
    "        # Generate test set\n",
    "        X_test, Y_test = generate_data(1000, target_w)\n",
    "        \n",
    "        # Test g\n",
    "        test_err = np.mean(np.sign(np.dot(X_test, w)) != Y_test)\n",
    "        \n",
    "        # Update average values\n",
    "        avg_num_iterations += (num_iterations * 1.0 / num_runs)\n",
    "        avg_test_err += (test_err * 1.0 / num_runs)\n",
    "    \n",
    "    # Print results\n",
    "    print('avg_num_iterations = %f' % (avg_num_iterations))\n",
    "    print('avg_test_err = %f' % (avg_test_err))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chạy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "avg_num_iterations = 9.155000\n",
      "avg_test_err = 0.109053\n"
     ]
    }
   ],
   "source": [
    "main(N=10) # We can use `main(10)`, but `main(N=10)` is clearer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Câu 7: ta thấy kết quả gần nhất với đáp án [b] 15.\n",
    "\n",
    "Câu 8: ta thấy kết quả gần nhất với đáp án [c] 0.1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "avg_num_iterations = 112.642000\n",
      "avg_test_err = 0.013811\n"
     ]
    }
   ],
   "source": [
    "main(N=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Câu 9: ta thấy kết quả gần nhất với đáp án [b] 100\n",
    "\n",
    "Câu 10: ta thấy kết quả gần nhất với đáp án [b] 0.01"
   ]
  }
 ],
 "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.1"
  },
  "toc": {
   "nav_menu": {
    "height": "12px",
    "width": "160px"
   },
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "165px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}