Summary_Basic.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Math\n",
    "\n",
    "### Union Bound\n",
    "\n",
    "$$\n",
    "P(A \\cup B) \\le P(A) + P(B)\n",
    "$$\n",
    "\n",
    "### Chernoff Bound\n",
    "\n",
    "$Z_1, \\cdots, Z_m \\in \\{0, 1\\}$ i.i.d. $p(z=1) = \\Phi, p(z=0) = 1 - \\Phi$, let $\\widehat{\\Phi} = \\dfrac{1}{m} \\sum_i Z_i$, we have \n",
    "$$P(|\\Phi - \\widehat{\\Phi}| > \\gamma) \\le 2\\exp (-2\\gamma^2m)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Jensen's Inequality\n",
    "\n",
    "For convex function $f$ and random variable $X$, $\\mathbb{E}[f(X)] \\ge f(\\mathbb{E} X)$. Equality exists when $X = \\mathbb{E}X, \\ w.p.1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Multivariant Gaussian Distribution\n",
    "\n",
    "$$\n",
    "p(x;\\mu,\\Sigma) = \\dfrac{1}{(2\\pi)^{n/2} |\\Sigma|^{1/2}} \\exp(-\\dfrac{1}{2}(x-\\mu)^T \\Sigma^{-1} (x-\\mu))\n",
    "$$\n",
    "\n",
    "Derivatives:\n",
    "\n",
    "$$\n",
    "\\frac{ \\partial \\log p({\\boldsymbol x};{\\boldsymbol \\mu},{\\boldsymbol \\Sigma}) }{ \\partial {\\boldsymbol \\mu}}\n",
    "= {\\boldsymbol \\Sigma}^{-1}  \\left( {\\boldsymbol x} - {\\boldsymbol \\mu} \\right) \n",
    "$$\n",
    "\n",
    "$$\n",
    "\\frac{ \\partial \\log p({\\boldsymbol x};{\\boldsymbol \\mu},{\\boldsymbol \\Sigma}) }{ \\partial {\\boldsymbol \\Sigma}}\n",
    "= \\frac{1}{2} \\left( \n",
    "{\\boldsymbol \\Sigma}^{-1} \n",
    "\\left( {\\boldsymbol x} - {\\boldsymbol \\mu} \\right)\n",
    "\\left( {\\boldsymbol x} - {\\boldsymbol \\mu} \\right)^T\n",
    "{\\boldsymbol \\Sigma}^{-1}  \n",
    "- {\\boldsymbol \\Sigma}^{-1} \\right)\n",
    "$$\n",
    "\n",
    "Conditional distribution, $x_1|x_2 \\sim \\mathcal{N}(\\mu_{1|2}, \\Sigma_{1|2})$, wherre $\\mu_{1|2} = \\mu_1 + \\Sigma_{12} \\Sigma_{22}^{-1} (x_2 - \\mu_2)$ and $\\Sigma_{1|2} = \\Sigma_{11}- \\Sigma_{12}\\Sigma_{22}^{-1} \\Sigma_{21}$\n",
    "\n",
    "Marginal distribution, $x_1 \\sim \\mathcal{N}(\\mu_1, \\Sigma_{11})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Matrix\n",
    "\n",
    "* $\\nabla_A tr(AB) = B^T$\n",
    "* $\\nabla_{A^T} f(A) = (\\nabla_A f(A))^T$\n",
    "* $\\nabla_A tr(ABA^TC) = CAB + C^T A B^T$\n",
    "* $\\nabla_A |A| = |A|(A^{-1})^T$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bayes' Theorem\n",
    "\n",
    "$$P(A|B) = \\dfrac{P(B|A)P(A)}{P(B)}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### KL Divergence\n",
    "\n",
    "$$\n",
    "KL(P||Q) = -\\sum_i P(i) \\log \\dfrac{Q(i)}{P(i)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hoeffding's Inequality\n",
    "\n",
    "Define $p(H(n) \\le k) = \\sum_{i=0}^k C_n^i p^i (1-p)^{n-i}$, we have $p(H(n) \\le k) \\le exp(-2(p-\\dfrac{1}{2})^2 n)$ and $p(H(n) \\ge k) \\le exp(-2(\\dfrac{1}{2}-p)^2 n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## AI-Book Chapter 3\n",
    "\n",
    "### Searching\n",
    "\n",
    "* 两种搜索的范式：Tree Search和Graph Search\n",
    "\n",
    "```\n",
    "def tree_search:\n",
    "    while:\n",
    "        if frontier is empty:\n",
    "            return FAILURE\n",
    "        choose a leaf node and remove if from frontier\n",
    "        if goal(node):\n",
    "            return corresponding solution\n",
    "        expand the node\n",
    "        add the resulting nodes to frontier\n",
    "```\n",
    "\n",
    "```\n",
    "def graph_search:\n",
    "    explored_set = []\n",
    "    while:\n",
    "        if frontier is empty:\n",
    "            return FAILURE\n",
    "        choose a leaf node and remove if from frontier\n",
    "        if goal(node):\n",
    "            return corresponding solution\n",
    "        explored_set += [node]\n",
    "        expand the node\n",
    "        add the resulting nodes to frontier if not in frontier of explored_set\n",
    "```\n",
    "\n",
    "* 搜索算法的衡量标准\n",
    "    - completeness：如果存在解，是否能够找到\n",
    "    - optimality：是否能够找到最优解\n",
    "    - time complexity / space complexity\n",
    "\n",
    "### Uninformed Search Strategies\n",
    "\n",
    "* BFS\n",
    "    - complete if branching factor $b$ is finite\n",
    "    - optimal if step costs are identical\n",
    "    - time and space $O(b^d)$, where $d$ is depth\n",
    "* Uniform-cost Search\n",
    "    - frontier采用一个优先队列，每次弹出cost最小的节点，并且扩展的时候如果节点比之前的cost小，会进行更新；在BFS的基础上这样做保证了step cost不相同时返回结果的最优性\n",
    "    - complete if $b$ is finite and step cost $\\ge \\epsilon > 0$\n",
    "    - always optimal\n",
    "    - time and space $O(b^{1 + \\lfloor C^* / \\epsilon \\rfloor})$, where $C^*$ is the optimal solution\n",
    "* DFS (with tree search frame)\n",
    "    - not complete: 由于tree search中不会记录已访问的态，因此可能陷入循环；如果记录的话，就没有相对于BFS的空间优势了\n",
    "    - not optimal: 先访问到的不一定最优\n",
    "    - time $O(b^m)$; space $O(bm)$ （frontier中最多装bm个节点），其中$m$为搜索的最深深度\n",
    "* Depth Limited DPS (with tree search frame)\n",
    "    - 和DFS相同，只不过$m$代表的是限制的深度\n",
    "* Iterative Deepening\n",
    "    - complete if $b$ is finite\n",
    "    - optimal if cost are identical\n",
    "    - time $O(b^d)$; space $O(bd)$\n",
    "* Bidirectional Search: not applicable in all cases\n",
    "    - complete if $b$ is finite and both directions are BFS\n",
    "    - optimal if step costs are identical and BFS\n",
    "    - space and time $O(b^{d/2})$\n",
    "\n",
    "### Informed (Heuristic) Search\n",
    "\n",
    "* A-Star\n",
    "    - complete if #node equal or less than $C^*$ is finite, i.e. all step cost $\\ge \\epsilon$ and $b$ is finite\n",
    "    - optimal: addmisible $h(n) \\le h^*(n)$ for tree-search; consistent $h(n) \\le c(n, a, n') + h(n')$ for graph-search\n",
    "    - proof: 1. 证明路径上$f(n) = g(n) + h(n)$是越来越大的；2. 证明一个节点被找到，通往这个节点的最优路径就被找到了（反证法，由于f小的先被扩展）\n",
    "    - time and space $O(b^m)$\n",
    "\n",
    "## AI-Book Chapter 4\n",
    "\n",
    "### Local Search \n",
    "* Hill-climbing Search：每次只考虑邻域，如果结果变好就走到该邻域，使用random restart技术可以使得算法变得complete\n",
    "* Simulated Annealing：考虑邻域，如果结果变好就接受它，如果没有变好，以概率$e^{- |\\Delta E| / T}$接受\n",
    "* Local Beam Search：使用k个agent来一起做Hill-climbing Search，如果有某些agent发现哪里比较好，会让其他agent也来搜索这一块地方\n",
    "* Genetic Algorithm：random select by fitness func, mutate and reproduce\n",
    "\n",
    "### Searching with Nondeterministic Actions or Partial Observation\n",
    "* 环境的因素不确定的时候，使用AND-OR search的方法，OR节点表示agent可以自己选择的节点，AND节点表示环境随机选择的节点。目标是找到一棵树，使得每个叶子节点都是一个目标状态，在OR节点上表明要做出的选择，每个AND节点的分支都要考虑。\n",
    "* 在观察受限的时候，可以使用belief state，它是多个可能实际状态的集合；每一个action把一个belief state转到另一个，旧的belief state中每一个状态都包含在新的中；观察到新状态的部分信息之后，可以把belief state缩减为一个更小的belief state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Andrew Ng Lecture 1\n",
    "\n",
    "### Minimize Loss Function/Maximize Log Liklihood\n",
    "\n",
    "* 对Linear Regression的损失函数求梯度\n",
    "* 对Linear Regression的似然函数求梯度（认为y随$\\theta^T x$正态分布，即正态噪声）\n",
    "* 对Logistic Regression的似然函数求梯度\n",
    "\n",
    "### Generalized Linear Model\n",
    "\n",
    "* Exponential Family：$p(y,\\eta) = b(y) \\exp(\\eta^T T(y) - a(\\eta))$\n",
    "* 通常$T(y)=y$, $\\eta = \\theta^T x$（这就是为什么叫linear）\n",
    "* 用处：假设数据服从一个分布，用一组参数$\\Phi$表示；把它化为exponential family，写出$\\eta, a(\\eta), b(y)$分别是什么；然后可以写出$p(y|x,\\theta)$具体的形式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Andrew Ng Lecture 2\n",
    "\n",
    "### Generative and Discriminative Model\n",
    "\n",
    "* Discriminative model 是学习$p(y|x)$，希望直接从input space $\\rightarrow$ label\n",
    "* Generative model 是学习$p(x|y)$，通过贝叶斯公式$p(y|x)=p(x|y)p(y)/p(x)$来做判别\n",
    "\n",
    "### Guassian Discriminate Analysis\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "y & \\sim Bernoulli(\\Phi) = p(y) = \\Phi^y (1-\\Phi)^{1-y} \\\\\n",
    "x|y=0 & \\sim N(\\mu_0, \\Sigma) = \\dfrac{1}{(2\\pi)^{n/2} |\\Sigma|^{1/2}} \\exp(-\\dfrac{1}{2}(x-\\mu_0)^T \\Sigma^{-1} (x-\\mu_0)) \\\\\n",
    "x|y=1 & \\sim N(\\mu_1, \\Sigma)\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write down log-likelihood and take derivative\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\Phi & = \\dfrac{1}{m} \\sum_i y^{(i)} \\\\\n",
    "\\mu_0 &= \\dfrac{\\sum_i (1-y^{(i)}) x^{(i)}}{\\sum_i (1-y^{(i)})} \\\\\n",
    "\\mu_1 &= \\dfrac{\\sum_i y^{(i)} x^{(i)}}{\\sum_i y^{(i)}} \\\\\n",
    "\\Sigma &= \\dfrac{1}{m} \\sum_i (x^{(i)} - \\mu_{y^{(i)}}) (x^{(i)} - \\mu_{y^{(i)}})^T\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "GDA can be changed into the form of logistic regression. Relationship: GDA is stronger and data efficient when at leat assumption is approximately correct; LR is weaker but do better in non-Gaussian data, e.g. Poisson data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Naive Bayes and Multinomial Event Model\n",
    "\n",
    "* 都来做email spam任务\n",
    "* Naive Bayes：一篇文章用一个向量$x\\in \\mathbb{R}^{|V|}$表示，如果出现某个词就是1，如果没出现就是0；要学习的参数是$\\Phi = p(y=1)$，$\\Phi_{i|y=c} = p(x_i=1|y=c)$；取似然函数对数求导，得到结果，最后的结论是分子分母计数统计。\n",
    "* Multinomial Event Model：一篇文章用一个向量$x\\in \\mathbb{R}^{n_j}$表示，其中n是第j篇文章的长度，每一位代表这个词在词库中的编号；要学习的参数$\\Phi = p(y=1)$，$\\Phi_{i=k|y=c} = p(x_i=k|y=c)$，结论也差不多，就是计数统计。\n",
    "* Laplace Smoothing：有些词出现很少或者没出现过，所以在计数的时候认为每个基本的类都先出现过一次，即在分子+1，在分母加上类的个数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Andrew Ng Lecture 3\n",
    "\n",
    "### Lagrange Duelity\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\min_w f(w) \\\\\n",
    "& s.t. g_i(w) \\le 0, \\ \\forall i \\in [k] \\\\\n",
    "& \\ \\  h_i(w) = 0, i \\in [l]\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Lagrange function $L(w,\\alpha,\\beta)=f(w) + \\sum \\alpha_i g_i(w) + \\sum \\beta_i h_i(w)$, define $\\theta_P(w) = \\max_{\\alpha, \\beta: \\alpha_i \\ge 0} L(w,\\alpha,\\beta)$ and $\\theta_D (\\alpha, \\beta) = \\min_w L(w,\\alpha,\\beta)$. We have $\\max_{\\alpha, \\beta: \\alpha_i \\ge 0} \\theta_D (\\alpha, \\beta) = d^* \\le p^* = \\min_w \\theta_P(w)$. Under certain conditions ($f$ and $g_i$ are convex; $\\{g_i\\}$ is feasible), $d^* = p^*$. On this optimal point, KKT condision should be satisfied\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\dfrac{\\partial L }{\\partial w_i} = 0 \\\\\n",
    "& \\dfrac{\\partial L }{\\partial \\beta_i} = 0 \\\\\n",
    "& \\alpha_i g_i(w) = 0 \\\\\n",
    "& g_i(w) \\le 0 \\\\\n",
    "& a_i \\ge 0 \n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SVM Deduction\n",
    "\n",
    "Start from \n",
    "\n",
    "$$\n",
    "\\max_{\\gamma, w, b} \\gamma \\quad s.t. y^{(i)}(w^T x^{(i)} + b) \\ge \\gamma, \\ ||w|| = 1\n",
    "$$\n",
    "\n",
    "Considering scaling invariance, we can scale by $\\dfrac{1}{||w||}$ and let $\\gamma = 1$.\n",
    "\n",
    "$$\n",
    "\\max_{w, b} \\dfrac{1}{2} ||w||^2 \\quad s.t. y^{(i)}(w^T x^{(i)} + b) \\ge 1\n",
    "$$\n",
    "\n",
    "By using Lagrange duality,\n",
    "\n",
    "$$\n",
    "\\max_\\alpha W(\\alpha) = \\sum_i \\alpha_i - \\dfrac{1}{2} \\sum_{i,j} y^{(i)}y^{(j)}\\alpha_i\\alpha_j x^{(i)} \\cdot x^{(j)}\n",
    "\\quad s.t. \\alpha_i \\ge 0, \\sum_i \\alpha_i y^{(i)} = 0\n",
    "$$\n",
    "\n",
    "When faced by soft margin,\n",
    "\n",
    "$$\n",
    "\\max_{w, b} \\dfrac{1}{2} ||w||^2 + C \\sum \\xi_i \\quad s.t. y^{(i)}(w^T x^{(i)} + b) \\ge 1 - \\xi_i, \\ \\xi_i \\ge 0\n",
    "$$\n",
    "\n",
    "we have \n",
    "\n",
    "$$\n",
    "\\max_\\alpha W(\\alpha) = \\sum_i \\alpha_i - \\dfrac{1}{2} \\sum_{i,j} y^{(i)}y^{(j)}\\alpha_i\\alpha_j x^{(i)} \\cdot x^{(j)}\n",
    "\\quad s.t. 0 \\le \\alpha_i \\le C, \\sum_i \\alpha_i y^{(i)} = 0\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Kernel\n",
    "\n",
    "Kernel function corresponds to the product of feature vector. Theorem: $K: \\mathbb{R}^n \\times \\mathbb{R}^n \\to \\mathbb{R}$ is a valid kernel $\\Longleftrightarrow \\forall \\{x^{(1)}, \\cdots, x^{(m)}\\}$ corresponding kernel matrix is symmetric positive semidefinite."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SMO\n",
    "\n",
    "SMO是用来解SVM的一个算法，主要思路是coordinate ascend，每次选定$\\alpha_1, \\alpha_2$，然后在不违反约束的情况下，最大化$W(\\alpha)$。需要满足的约束是$\\sum_i \\alpha_i y_i = 0 \\Rightarrow \\alpha_1 = (\\xi - \\alpha_2 y_2) y_1$和$\\alpha_1, \\alpha_2 \\in [0, C] \\Rightarrow L \\le \\alpha_2 \\le H$。把第一个约束条件带入，$W(\\alpha) = W((\\xi - \\alpha_2 y_2) y_1, \\alpha_2, \\cdots, \\alpha_m) = a\\alpha_2^2 + b\\alpha_2 + c$，二次型能够求出最值$\\alpha_2^*$，最后$\\alpha_2 \\leftarrow clip(\\alpha_2^*, L, H)$。迭代进行。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Andrew Ng Lecture 4\n",
    "\n",
    "### Bias and variance\n",
    "\n",
    "* Bias: expected generalization error enven if we fit on a large training set. Simple model with few parameters suffers large bias.\n",
    "* Variance: a model has large variance if the model vary much under different data from the same distribution. Complex model with large number of parameters suffers large variance.\n",
    "\n",
    "### Empirical risk and generalization error\n",
    "\n",
    "* empirical risk: $\\newcommand{\\epsilonhat}{\\widehat{\\epsilon}} \\epsilonhat(h) = \\dfrac{1}{m} \\sum_{i} I(h(x^{(i)}) \\neq y^{(i})$\n",
    "* generalization error: $\\epsilon(h) = P_{(x,y)\\sim D}(h(x)\\neq y)$\n",
    "* empirical risk minimization (ERM) is to find parameter $\\theta$ that minimize empirical risk, or find hypothesis among hypothesis space that minimize empirical risk.\n",
    "\n",
    "### PAC\n",
    "\n",
    "* Theorem: 当样本数$m$满足以下关系时，能够保证empirical risk能够以大概率($1-\\delta$)，近似$|\\epsilonhat - \\epsilon| \\le \\gamma$等于generalization error。\n",
    "* 证明：其实最后是要证明$P(\\neg \\exists h\\in \\mathcal{H} |\\epsilonhat(h) - \\epsilon(h)| > \\gamma) \\le 1 - 2 k \\exp(-2\\gamma^2 m)$，用Union Bound把它转化为单个的，再用Chernoff bound写出两者接近程度的bound。\n",
    "\n",
    "* Theorem：$\\epsilon(\\widehat{h}) \\le \\min_{h\\in\\mathcal{H}} \\epsilon(h) + 2 \\sqrt{\\dfrac{1}{2m} \\log(\\dfrac{2k}{\\delta})}$, where $\\widehat{h} = arg\\min \\epsilonhat(h)$, define $\\widehat{h^*} = arg\\min \\epsilon(h)$.\n",
    "* 证明：$\\epsilon(\\widehat{h}) \\le \\epsilonhat(\\widehat{h}) + \\gamma \\le \\epsilonhat(h^*) + \\gamma \\le \\epsilon(h^*) + 2 \\gamma$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### VC-dimension\n",
    "\n",
    "* VC-dimension解决了上述理论里面$k=|\\mathcal{H}|$在参数连续情况下发散的情况\n",
    "* shatter：$\\mathcal{H}$ shatters $S$ if $\\mathcal{H}$ can realize any binary label on $S = \\{x^{(1)}, \\cdots, x^{(d)}\\}$\n",
    "* $VC(\\mathcal{H}) = k$ 表示最多能找到一个包含k个点的$S$使得$\\mathcal{H}$能够把$S$分开。注意，找到一个这样k个点的集合即可，并不要求任意的k个点的集合，$\\mathcal{H}$都能分开。\n",
    "* Theorem: $\\gamma = |\\epsilon(h)-\\epsilonhat(h)| \\le O(\\dfrac{d}{m} \\log \\dfrac{m}{d} + \\dfrac{1}{m} \\log \\dfrac{1}{d})$, where d is the VC-dimension"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Andrew Ng Lecture 5\n",
    "\n",
    "### Model selection by k-fold CV\n",
    "\n",
    "```\n",
    "def model_selectio_kfold(M1, M2, ..., Md):\n",
    "    randomly split S into k set S1, ..., Sk\n",
    "    for each Mi:\n",
    "        for j = 1 to k:\n",
    "            train on S/Sj test on Sj\n",
    "        epsilon[Mi] = mean(epsilon[Mi, j], j)\n",
    "    pick Mi with lowest epsilon[Mi] and retrain the model\n",
    "```\n",
    "\n",
    "### Full Bayes, MAP and ML\n",
    "\n",
    "* Full Bayes:\n",
    "on training \n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\newcommand{\\sampleyi}{y^{(i)}}\n",
    "\\newcommand{\\samplexi}{x^{(i)}}\n",
    "\\newcommand{\\sumoversample}{\\sum_{i=1}^m}\n",
    "\\newcommand{\\prodoversample}{\\prod_{i=1}^m}\n",
    "p(\\theta| S) & = \\dfrac{p(S|\\theta)p(\\theta)}{p(S)} \\\\\n",
    "& = \\dfrac{p(\\theta) \\prodoversample p(\\sampleyi | \\samplexi, \\theta)}{\\int_\\theta (\\prodoversample p(\\sampleyi | \\samplexi, \\theta) ) p(\\theta) d\\theta}\n",
    "\\end{aligned}\n",
    "$$\n",
    "on new example\n",
    "$$ p(y|x, S) = \\int_\\theta p(y|x,\\theta) p(\\theta|S) d\\theta $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* MAP (maximum a posteriori): choose only the maximizer $\\theta$, $\\theta_{MAP} = arg\\max_\\theta \\prodoversample p(\\sampleyi | \\samplexi, \\theta) p(\\theta)$. Choosing $p(\\theta) \\sim \\mathcal{N}(0, \\tau^2 I)$ serves as a regularization.\n",
    "* ML (maximum a likelihood): $\\theta_{ML} = arg\\max_\\theta \\prodoversample p(\\sampleyi | \\samplexi, \\theta)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Andrew Ng Lecture 6\n",
    "\n",
    "### Online Learning\n",
    "\n",
    "* from batch learning to online learning\n",
    "* perceptron algorithm for online learning: define $h_\\theta(x) = sign(\\theta^T x)$ returns -1 or 1, label $y \\in \\{-1, +1\\}$, if the algorithm goes wrong at some example do $\\theta \\leftarrow \\theta + \\sampleyi \\samplexi$\n",
    "* Theorem: $||\\samplexi|| \\le D$, $\\exists u$ s.t. $||u||^2 = 1$, $\\sampleyi (u^T \\samplexi) \\ge \\gamma$, total number of mistaks the algorithm makes $\\le (\\dfrac{D}{\\gamma})^2$\n",
    "* 证明：假设出现第k个错误时为$\\theta^{(k)}$，数学归纳法证${\\theta^{(k+1)}}^T u \\ge k\\gamma$, $||\\theta^{(k+1)}||^2 \\le k D^2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Andrew Ng Lecture 7\n",
    "\n",
    "### k-means\n",
    "\n",
    "* 算法：repeat $c^{(i)} = arg \\min_j ||\\samplexi - \\mu_j||^2, \\ \\forall i \\in [m]$ and $\\mu_j = \\dfrac{\\sumoversample I(c^{(i)} = j) \\samplexi}{\\sumoversample I(c^{(i)} = j)}$\n",
    "* 分析：k-means is exactly coordinate descent on $J(c, \\mu) = \\sumoversample ||\\samplexi - \\mu_{c^{(i)}}||^2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mixture of Gaussian\n",
    "\n",
    "![](figures/fig20180407_EM.png)\n",
    "\n",
    "![](figures/fig2018027_EM.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Andrew Ng Lecture 8\n",
    "\n",
    "### EM Algorithm\n",
    "\n",
    "当隐变量存在的时候，对数似然函数$l(\\theta) = \\sumoversample \\log \\sum_z p(x; x, \\theta)$。注意到log函数是凹函数，使用Jensen不等式，可以得到该似然函数的下界，令似然函数能够取到该下界，得到x的分布$Q(z^{(i)}) = p(z^{(i)} | \\samplexi, \\theta) = \\dfrac{p(\\samplexi, z^{(i)}, \\theta)}{\\sum_z p(\\samplexi, z, \\theta)}$（E-step)。在M-step求一个参数能够最大化该下界，$\\theta = arg\\max_\\theta \\sum_i \\sum_{z^{(i)}} Q(z^{(i)}) \\log \\dfrac{p(\\samplexi, z^{(i)}, \\theta)}{Q(z^{(i)})}$。\n",
    "\n",
    "EM算法还可以看做是对$J(Q, \\theta) = \\sum_i \\sum_{z^{(i)}} Q(z^{(i)}) \\log \\dfrac{p(\\samplexi, z^{(i)}, \\theta)}{Q(z^{(i)})}$做coordinate ascend。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Andrew Ng Lecture 9\n",
    "\n",
    "### Factor Analysis\n",
    "\n",
    "如果样本的数目m没有输入样本的维度n多的时候，用Gaussian模型来求解的时候协方差矩阵很容易是Singlar Matrix。考虑用一个维度比较低的隐变量$z\\in\\mathbb{R}^k, \\ k<n$来反映某个向量的信息，然后把它变换到原来高维的空间中。即$z\\sim \\mathcal{N}(0, I)$, $x|z \\sim \\mathcal{N}(0, \\Psi)$, $x = \\mu + \\Lambda z + \\epsilon$。考虑联合分布有\n",
    "\n",
    "$$\n",
    "\\left[ \\begin{matrix} z \\\\ x \\end{matrix} \\right]\n",
    "= \\mathcal{N} \\left(\n",
    "\\left[ \\begin{matrix} 0 \\\\ \\mu \\end{matrix} \\right], \n",
    "\\left[ \\begin{matrix} I & \\Gamma^T \\\\ \\Gamma & \\Gamma\\Gamma^T + \\Psi \\end{matrix} \\right]\n",
    "\\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用EM算法来求解，E-step中$Q(z)$的求解需要使用到高斯分布的条件分布，M-step中对J函数求导可以得到其他参数的更新公式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Andrew Ng Lecture 10\n",
    "\n",
    "### PCA\n",
    "\n",
    "* PCA可以识别数据分布的若干主轴方向\n",
    "* 假设希望找到一个主轴方向为$u$，满足$||u||^2=1$，其实就是解最优化问题$\\max \\frac{1}{m} \\sumoversample ({\\samplexi}^T u)^2 = \\frac{1}{m} u^T \\Sigma u$，其中$\\Sigma  =\\frac{1}{m}\\sumoversample {\\samplexi}^T \\samplexi \\in \\mathbb{R}^{n\\times n}$。称$\\Sigma$为Covariance matrix，设$\\{u_k\\}$是其前k个特征向量，因此可以用每个样本的特征向量和这k个特征向量分别做内积，得到的k个数字组成新的k维特征向量。\n",
    "* 应用：compression for visualization. for supervised learning (faster and avoid overfitting), serve as a kind of noise reduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Andrew Ng Lecture 11\n",
    "\n",
    "### Cocktail Party Problem\n",
    "\n",
    "* n sources $s\\in\\mathbb{R}^n$, n recorder $x\\in\\mathbb{R}^n$, $x=As$, where $A$ is mixing matrix\n",
    "* objective given sample of sources and recorder compute a unmixing matrix $W = A^{-1}$\n",
    "* 分析：声源之间做permutation是无法区分的；声源的信号大小（音量）是无法复原的；声源和录音设备不能各向同性\n",
    "* 通过声源数值的概率分布计算录音设备数值的概率分布：$p(x)=\\prod_{i=1}^n p_s(w_i^T x) |W|$，其中$w_i^T$是$W$矩阵的行向量\n",
    "* 选择声源数值的分布：$p_s(s) = \\sigma'(s)$，sigmoid函数的导数\n",
    "* 写出对数似然函数求导，得到W矩阵的梯度上升迭代公式\n",
    "$$\n",
    "W = W + \\alpha \\left(\n",
    "\\left[ \\begin{matrix} 1-2\\sigma(w_1^T \\samplexi) \\\\ 1-2\\sigma(w_2^T \\samplexi) \\\\ \\cdots \\\\ 1-2\\sigma(w_n^T \\samplexi) \\end{matrix} \\right]\n",
    "{\\samplexi}^T + (W^T)^{-1} \\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Andrew Ng Lecture 12\n",
    "\n",
    "### Reinforcement Learning\n",
    "\n",
    "* Bellman Equation: $V^\\pi(S) = R(s) + \\gamma \\sum_{s' \\in S} p(s, \\pi(s), s') V^\\pi(s')$"
   ]
  },
  {
   "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.4.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}