Summary_Basic_Lite.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Math\n",
    "\n",
    "$$\n",
    "\\newcommand{\\sumoversample}{\\sum_{i=1}^m}\n",
    "\\newcommand{\\samplexi}{x^{(1)}}\n",
    "\\newcommand{\\sampleyi}{y^{(1)}}\n",
    "$$\n",
    "\n",
    "* 【Union Bound】$P(A \\cup B) \\le P(A) + P(B)$\n",
    "* 【Chernoff Bound】$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)$$\n",
    "* 【Jensen's Inequality】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$\n",
    "* 【Multivariant Gaussian Distribution】\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",
    "Derivatives:\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",
    "\\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",
    "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",
    "Marginal distribution, $x_1 \\sim \\mathcal{N}(\\mu_1, \\Sigma_{11})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Matrix】$\\nabla_A tr(AB) = B^T$；$\\nabla_{A^T} f(A) = (\\nabla_A f(A))^T$；$\\nabla_A tr(ABA^TC) = CAB + C^T A B^T$；$\\nabla_A |A| = |A|(A^{-1})^T$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Bayes' Theorem】$P(A|B) = \\dfrac{P(B|A)P(A)}{P(B)}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【KL Divergence】$KL(P||Q) = -\\sum_i P(i) \\log \\dfrac{Q(i)}{P(i)}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Hoeffding's Inequality】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": [
    "* 【Lagrange Duelity】\n",
    "$$\n",
    "\\min_w f(w) \\quad\n",
    "s.t. g_i(w) \\le 0, \\ \\forall i \\in [k] \\quad\n",
    "h_i(w) = 0, i \\in [l]\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",
    "\\dfrac{\\partial L }{\\partial w_i} = 0 \\quad\n",
    "\\dfrac{\\partial L }{\\partial \\beta_i} = 0 \\quad\n",
    "\\alpha_i g_i(w) = 0 \\quad\n",
    "g_i(w) \\le 0 \\quad\n",
    "a_i \\ge 0 \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Machine Learning\n",
    "\n",
    "$$\\newcommand{\\sumsamples}{\\sum_{i=1}^m}$$\n",
    "\n",
    "* 【Bias-Variance Decomposition】泛化误差的分解：$f(x;D)$-variance-$\\mathbb{E}_D[f(x)]$-bias-$y_{true}$-noise-$y_D$\n",
    "* 【Cross Validation】\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",
    "* 【Linear Regression】推导闭式解可用最小化均方误差$\\sumsamples (y_i - wx_i -b)^2$，也可以转化为概率模型$p(y|x,w) \\sim \\mathbb{N}(wx, \\sigma^2)$最大化对数似然函数$L(w)=\\sumsamples \\log p(y|x,w)$；线性回归中，牛顿法$w^{(t+1)}=w^{(t)}-(\\dfrac{\\partial^2 E}{\\partial w^2})^{-1}(\\dfrac{\\partial E}{\\partial w})$可以一次得到最优解\n",
    "* 【Logistic Regression】logistic回归假设$\\ln \\dfrac{p(y=1|x)}{p(y=0|x)} = w^T x + b$，写出其对数似然函数$L(w)=\\sumsamples \\log p(y_i|w,x_i)=\\sumsamples y_i\\log(1-g(wx_i)) + (1-y_i)\\log g(wx_i)$，其中$g(x) = \\dfrac{1}{1+e^x}$，求导可得到梯度下降公式$w\\leftarrow w -\\alpha \\sumsamples(1-g(wx_i) - y_i) x_i$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Decision Tree】信息增益公式$H(D)=-\\sum_{k=1}^K p_k \\log p_k$，$H^{split}(D) = \\sum_i \\dfrac{|D_i|}{|D|} H(D_i)$，增益$H^{split}(D) - H(D)$\n",
    "* 【Gradient Boosting Tree】每步目标$obj^{(t)}=\\sumsamples l(y_i, \\widehat{y}^{t-1} + f_t(x_i)) + \\Omega(f_t) \\approx \\sumsamples (g_i f_t(x_i) + \\frac{1}{2} h_i f_t^2(x_i)) + \\gamma T + \\dfrac{\\lambda}{2} \\sum_{j=1}^T w_j^2$，结果$w^* = - \\dfrac{G_j}{H_j + \\lambda}$，$obj^* = -\\dfrac{1}{2} \\sum_{j=1}^T \\dfrac{G_j^2}{H_j + \\lambda}$，其中$G_j$和$H_j$分别是落在j节点上样本的一阶和二阶导数之和；分支划分依据$gain=\\dfrac{1}{2} [\\dfrac{G_L^2}{H_L + \\lambda} + \\dfrac{G_R^2}{H_R + \\lambda} - \\dfrac{(G_L+G_R)^2}{H_L + H_R + \\lambda}]-\\gamma$\n",
    "* 【Additive Model】$f(x) = \\sum \\alpha_m G_m(x)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【BP】假设权重$W_j$连接j和j+1层，$\\dfrac{\\partial E}{\\partial W_j} = \\sumsamples 2(\\widehat{y}^{(i)} - y^{(i)}) \\cdot \\dfrac{\\partial \\widehat{y}^{(i)}}{\\partial x_{j+1}^{(i)}} \\circ x_{j+1}^{(i)} \\circ (1-x_{j+1}^{(i)}) \\otimes x_j$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【SVM】Start from \n",
    "$$\n",
    "\\max_{\\gamma, w, b} \\gamma \\quad s.t. y^{(i)}(w^T x^{(i)} + b) \\ge \\gamma, \\ ||w|| = 1\n",
    "$$\n",
    "Considering scaling invariance, we can scale by $\\dfrac{1}{||w||}$ and let $\\gamma = 1$.\n",
    "$$\n",
    "\\max_{w, b} \\dfrac{1}{2} ||w||^2 \\quad s.t. y^{(i)}(w^T x^{(i)} + b) \\ge 1\n",
    "$$\n",
    "By using Lagrange duality,\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",
    "When faced by soft margin,\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",
    "we have \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": [
    "* 【SVM kernel】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.\n",
    "* 【SVM SMO】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": [
    "* 【Full Bayes/MAP/ML】full Bayes：参数估计$p(\\theta|D)=\\dfrac{P(D|\\theta)P(\\theta)}{P(D)}\\propto p(\\theta) \\prod_{i=1}^m p(y_i|x_i,\\theta)$，样本预测$p(y|x;D)=\\int_\\theta p(y|x,\\theta)p(\\theta|D)d\\theta$，MAP和ML只取一个$\\theta$，MAP $\\theta = arg \\max p(\\theta) \\prod_{i=1}^m p(y_i|x_i,\\theta)$，ML $\\theta = arg \\max \\prod_{i=1}^m p(y_i|x_i,\\theta)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Bayesian Network】基于无向图的概率图模型，联合概率分布$p(x_1,\\cdots,x_d) = \\prod_{i=1}^d p(x_i|\\pi_i)$，其中$\\pi_i$表示i的父节点，条件概率分布在图中给出；条件概率分布可由联合概率分布得出；给定两个变量，如果相互独立有$p(x,y)=p(x)p(y)$；1父2子，给定父节点，子节点相互独立；2父1子，子节点不给定时父节点独立，子节点给定的时候父节点不独立；x-y-z顺序结构，给定y时，xz独立\n",
    "* 【Gibbs Sampling】吉布斯采样可以求给定证据变量情形下，待查询变量的期望。随机产生一个与证据变量E一致的各rv赋值，每次选取一个除证据变量以外的rv，根据其Markov Blanket中的变量数值计算该变量的条件概率分布，依此采样得到新的数值。待查询变量的期望为所有循环中，该变量的均值。MB包含，该节点的父节点、子节点和子节点的父节点。\n",
    "* 【k-means EM】算法：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)}$；分析：k-means is exactly coordinate descent on $J(c, \\mu) = \\sumoversample ||\\samplexi - \\mu_{c^{(i)}}||^2$\n",
    "* 【GMM EM】E-step：$w_{ij} = p(z_i = j| x_i; \\Phi, \\mu, \\Sigma)$；M-step：$\\Phi_j = \\frac{1}{m}\\sumsamples w_{ij}$，$\\mu_j = \\dfrac{\\sumsamples w_{ij} x_i}{\\sumsamples w_{ij}}$，$\\Sigma_j = \\dfrac{\\sumsamples w_{ij} (x_i - \\mu_j)(x_i - \\mu_j)^T }{\\sumsamples w_{ij}}$；预测：$p(z_i = j| x_i; \\Phi, \\mu, \\Sigma) = \\dfrac{p(x_i|z_i = j; \\mu, \\Sigma)p(z_i=j;\\Phi)}{\\sum_{l=1}^k p(x_i|z_i = l; \\mu, \\Sigma)p(z_i=l;\\Phi)}$\n",
    "* 【EM】由Jesen不等式得到对数似然函数$l(\\theta) = \\sumoversample \\log \\sum_z p(x; x, \\theta)$的下界$J(Q, \\theta) = \\sum_i \\sum_{z^{(i)}} Q(z^{(i)}) \\log \\dfrac{p(\\samplexi, z^{(i)}, \\theta)}{Q(z^{(i)})}$，当$Q(z^{(i)}) = p(z^{(i)} | \\samplexi, \\theta) = \\dfrac{p(\\samplexi, z^{(i)}, \\theta)}{\\sum_z p(\\samplexi, z, \\theta)}$（E-step)可以取到此下界；把Q固定可以优化参数$\\theta = arg\\max_\\theta \\sum_i \\sum_{z^{(i)}} Q(z^{(i)}) \\log \\dfrac{p(\\samplexi, z^{(i)}, \\theta)}{Q(z^{(i)})}$ (M-step)\n",
    "* 【EM Covergence】证明每一轮之后对数似然函数都不小于上一轮\n",
    "* 【Majority Vote】直接使用Hoeffding，错误率随分类器数目指数下降\n",
    "* 【AdaBoost】最小化指数损失函数$L = \\mathbb{E}_{x\\sim D}[e^{-y f(x)}]$能够推导到权重更新公式$G_m = arg\\min\\sumsamples w_i^{(m)} I(y_i \\neq G_m(x_i))$，$\\alpha_m = \\log \\dfrac{1-err_m}{err_m}$，$w_i^{(m+1)} = w_i^{(m)} \\exp (\\alpha_m I (y_i \\neq G_m(x_i))$，其中$err_m = \\dfrac{\\sum I(\\neq) w_i^{(m)}}{\\sum w_i^{(m)}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Bagging】平均均方误差$E=\\mathbb{E}[\\dfrac{1}{M} \\sum \\epsilon_i^2]$；bagging是各个模型取平均，假设相互独立，误差$E=\\mathbb{E}[(\\dfrac{1}{M} \\sum \\epsilon_i)^2]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Random Forest】每次随机抽样生成一个训练集（bootstrap），然后再随机抽取若干特征，训练一棵树，最后的结果取平均\n",
    "* 【kNN】如果样本足够密，其误差率不超过贝叶斯最优分类器的两倍：$c^* = arg\\max P(c|x)$，$E = 1 - \\sum_c p(c|x)p(c|nn(x)) = 1 - \\sum_c p(c|x)^2 \\le 1 - p(c^*|x) = (1+p(c^*|x))(1-p(c^*|x)) \\le 2 (1-p(c^*|x))$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【PCA】PCA特征值分解的方法等价于找到某个向低维空间的投影，使得各个样本的重构误差最小；也等价于找到某个向低维空间的投影，使得各个样本投影的方差最大\n",
    "    - $|x_n\\rangle = \\sum_1^d |u_i\\rangle\\langle u_i|x_n\\rangle + \\sum_{d+1}^p |u_i\\rangle\\langle u_i|\\bar{x}\\rangle$，重构误差$J = \\dfrac{1}{N} \\sumsamples || x_i - x_i^{recon}||^2$，转化为优化问题，然后用拉格朗日乘子法\n",
    "    - 方差$Var = \\dfrac{1}{N} \\sumsamples ( \\langle x_i | u_j \\rangle - \\langle \\bar{x} | u_j \\rangle )^2$； 假设希望找到一个主轴方向为$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维特征向量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Empirical risk and generalization error】\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",
    "* 【PAC】\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",
    "    - 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$\n",
    "* 【VC Dimension】能够找到一个维度为d的样本集，使得该假设能够实现所有$2^d$种binary标签组合（打散）；但是不能打散任意一个维度为d+1的样本组合；$\\gamma = |\\epsilon(h)-\\epsilonhat(h)| \\le O(\\dfrac{d}{m} \\log \\dfrac{m}{d} + \\dfrac{1}{m} \\log \\dfrac{1}{d})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Generative and Discriminative Model】前者是学习$p(y|x)$，希望直接从input space $\\rightarrow$ label，后者是学习$p(x|y)$，通过贝叶斯公式$p(y|x)=p(x|y)p(y)/p(x)$来做判别\n",
    "* 【Guassian Discriminate Analysis】模型，结论，方法对数似然函数求导\n",
    "$$\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)) \\quad\n",
    "x|y=1  \\sim N(\\mu_1, \\Sigma)\n",
    "$$\n",
    "$$\n",
    "\\Phi = \\dfrac{1}{m} \\sum_i y^{(i)} \\quad\n",
    "\\mu_0 = \\dfrac{\\sum_i (1-y^{(i)}) x^{(i)}}{\\sum_i (1-y^{(i)})} \\quad\n",
    "\\mu_1 = \\dfrac{\\sum_i y^{(i)} x^{(i)}}{\\sum_i y^{(i)}} \\quad\n",
    "\\Sigma = \\dfrac{1}{m} \\sum_i (x^{(i)} - \\mu_{y^{(i)}}) (x^{(i)} - \\mu_{y^{(i)}})^T\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【RL】Bellman Equation: $V^\\pi(S) = R(s) + \\gamma \\sum_{s' \\in S} p(s, \\pi(s), s') V^\\pi(s')$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "* 【Generalized Linear Model】Exponential Family：$p(y,\\eta) = b(y) \\exp(\\eta^T T(y) - a(\\eta))$；通常$T(y)=y$, $\\eta = \\theta^T x$（这就是为什么叫linear）；用处：假设数据服从一个分布，用一组参数$\\Phi$表示；把它化为exponential family，写出$\\eta, a(\\eta), b(y)$分别是什么；然后可以写出$p(y|x,\\theta)$具体的形式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Naive Bayes】email spam，一篇文章用一个向量$x\\in \\mathbb{R}^{|V|}$表示，如果出现某个词就是1，如果没出现就是0；要学习的参数是$\\Phi = p(y=1)$，$\\Phi_{i|y=c} = p(x_i=1|y=c)$；取似然函数对数求导，得到结果，最后的结论是分子分母计数统计。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Online Learning】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": [
    "* 【Factor Analysis】如果样本的数目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",
    "\\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",
    "$$\n",
    "使用EM算法来求解，E-step中$Q(z)$的求解需要使用到高斯分布的条件分布，M-step中对J函数求导可以得到其他参数的更新公式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 【Cocktail Party Problem】n sources $s\\in\\mathbb{R}^n$, n recorder $x\\in\\mathbb{R}^n$, $x=As$, where $A$ is mixing matrix；objective given sample of sources and recorder compute a unmixing matrix $W = A^{-1}$；分析：声源之间做permutation是无法区分的；声源的信号大小（音量）是无法复原的；声源和录音设备不能各向同性；通过声源数值的概率分布计算录音设备数值的概率分布：$p(x)=\\prod_{i=1}^n p_s(w_i^T x) |W|$，其中$w_i^T$是$W$矩阵的行向量；选择声源数值的分布：$p_s(s) = \\sigma'(s)$，sigmoid函数的导数；写出对数似然函数求导，得到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": [
    "### Other AI\n",
    "\n",
    "* 【Searching】两种搜索的范式：Tree Search和Graph Search\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",
    "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",
    "* 【搜索算法的衡量标准】 completeness：如果存在解，是否能够找到；optimality：是否能够找到最优解；time complexity / space complexity\n",
    "* 【BFS】complete if branching factor $b$ is finite；optimal if step costs are identical；time and space $O(b^d)$, where $d$ is depth\n",
    "* 【Uniform-cost Search】frontier采用一个优先队列，每次弹出cost最小的节点，并且扩展的时候如果节点比之前的cost小，会进行更新；在BFS的基础上这样做保证了step cost不相同时返回结果的最优性；complete if $b$ is finite and step cost $\\ge \\epsilon > 0$；always optimal；time and space $O(b^{1 + \\lfloor C^* / \\epsilon \\rfloor})$, where $C^*$ is the optimal solution\n",
    "* 【DFS (with tree search frame)】not complete: 由于tree search中不会记录已访问的态，因此可能陷入循环；如果记录的话，就没有相对于BFS的空间优势了；not optimal: 先访问到的不一定最优；time $O(b^m)$; space $O(bm)$ （frontier中最多装bm个节点），其中$m$为搜索的最深深度\n",
    "* 【Depth Limited DPS (with tree search frame)】和DFS相同，只不过$m$代表的是限制的深度\n",
    "* 【Iterative Deepening】complete if $b$ is finite；optimal if cost are identical；time $O(b^d)$; space $O(bd)$\n",
    "* 【Bidirectional Search】not applicable in all cases；complete if $b$ is finite and both directions are BFS；optimal if step costs are identical and BFS；space and time $O(b^{d/2})$\n",
    "* 【A-Star】complete if #node equal or less than $C^*$ is finite, i.e. all step cost $\\ge \\epsilon$ and $b$ is finite；time and space $O(b^m)$；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",
    "* 【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",
    "* 【Searching with Nondeterministic Actions】环境的因素不确定的时候，使用AND-OR search的方法，OR节点表示agent可以自己选择的节点，AND节点表示环境随机选择的节点。目标是找到一棵树，使得每个叶子节点都是一个目标状态，在OR节点上表明要做出的选择，每个AND节点的分支都要考虑。\n",
    "* 【Searching with Partial Observation】在观察受限的时候，可以使用belief state，它是多个可能实际状态的集合；每一个action把一个belief state转到另一个，旧的belief state中每一个状态都包含在新的中；观察到新状态的部分信息之后，可以把belief state缩减为一个更小的belief state"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}