sn02.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 概率论复习\n",
    "\n",
    "这篇笔记将介绍一些推导机器学习算法时用到的概率论相关概念，主要针对本课程CS229中将会使用到的知识。概率论所涉及的数学理论十分复杂，而且已经发展为一门单独的学科——**测度论（measure theory）**。在这篇笔记中，我们将对概率论做最基本的讨论，而并不会涉及那些复杂的理论。\n",
    "\n",
    "## 1. 概率的基本要素\n",
    "\n",
    "为了对集合的概率做出定义，我们需要先准备几个基本要素：\n",
    "* **样本空间（Sample space）$\\Omega$：**一个由某随机实验的所有输出组成的集合。其中的每个输出$\\omega\\in\\Omega$都可以看做是真实实验最终状态的完全描述。\n",
    "* **事件集/事件空间（Set of events/event space）$\\mathcal F$：**集合的元素（也称为事件）$A\\in\\mathcal F$是$\\Omega$的子集（即$A\\subseteq\\Omega$是实验的一组可能的输出集合，$\\mathcal F$满足三个特性，$\\varnothing\\in\\mathcal F$、$A\\in\\mathcal F\\implies \\Omega\\setminus A\\in\\mathcal F$、$A_1,A_2,\\cdots\\in\\mathcal F\\implies\\cup_iA_i\\in\\mathcal F$）。\n",
    "* **概率测度（Probability measure）：**函数$P:\\mathcal F\\to\\mathbb R$具有一下特性：\n",
    "  * $\\forall A\\in\\mathcal F, P(A)\\gt0$；\n",
    "  * $P(\\Omega)=1$；\n",
    "  * 若$A_1,A_2$为不相交事件（即$A_i\\cap A_j=\\varnothing, i\\neq j$），则有$\\displaystyle P(\\cup_iA_i)=\\sum_iP(A_i)$。\n",
    "\n",
    "上面这三条特性称为**概率公理（Axioms of Probability）**。\n",
    "\n",
    "**举例：**掷六面骰子时，其样本空间为$\\Omega={1,2,3,4,5,6}$。我们可以在样本空间上定义各种事件空间。比如最简单的事件空间——平凡事件空间$\\mathcal F=\\{\\varnothing,\\Omega\\}$，另一个事件空间是$\\Omega$的所有子集组成的集合。可以看出第一个事件空间满足上面的概率测度，$P(\\varnothing)=0,P(\\Omega)=1$。对于第二个事件空间，一种有效的概率测度就是给事件空间中的每个集合赋值$\\frac{i}{6}$，其中$i$是该集合中事件的个数，于是有$P(\\{1,2,3,4\\})=\\frac{4}{6}$，$P(\\{1,2,3\\})=\\frac{3}{6}$。\n",
    "\n",
    "**性质：**\n",
    "* $A\\subseteq B\\implies P(A)\\leq P(B)$；\n",
    "* $P(A\\cap B)\\leq\\min(P(A),P(B))$；\n",
    "* 联合界（Union Bound）：$P(A\\cup B)\\leq P(A)+P(B)$；\n",
    "* $P(\\Omega\\setminus A)=1-P(A)$；\n",
    "* 全概率：若$A_1,\\cdots,A_k$为一组不相交事件，$\\cup_{i=1}^kA_i=\\Omega$，$\\sum_{i=1}^kP(A_k)=1$\n",
    "\n",
    "### 1.1 条件概率与独立性\n",
    "\n",
    "令$B$为具有非零概率的事件，则在$B$条件下$A$的概率定义为：\n",
    "\n",
    "$$\n",
    "P(A\\mid B)\\triangleq\\frac{P(A\\cap B)}{P(B)}\n",
    "$$\n",
    "\n",
    "换句话说，$P(A\\mid B)$是观察到事件$B$的结果之后，事件$A$的概率测度。若$P(A\\cap B)=P(A)P(B)$（或等价的$P(A\\mid B)=P(A)$）则称这两个事件相互独立。因此，独立性就是指对事件$B$的观测完全不影响事件$A$的概率。\n",
    "\n",
    "## 2. 随机变量\n",
    "\n",
    "考虑一个抛硬币实验，我们抛了10枚硬币，并想要知道面向上有多少枚。此时的样本空间$\\Omega$的元素为长度为$10$的序列，记录每一个硬币$H$或$T$向上的状态。比如我们可能有$\\Omega_0=\\langle H,H,T,H,T,H,H,T,T,T\\rangle\\in\\Omega$。不过在实际实验中，我们并不关心特定的$H,T$序列。我们关系的是关于实验输出的实函数，比如$10$枚硬币中面相上的个数，或是连续最长的底向上的个数。这些函数，在特定语境下（比如现在）也可以称为**随机变量（random variables）**。\n",
    "\n",
    "更加正式的定义，随机变量$X$是一个函数$X:\\Omega\\to\\mathbb R$（不过，并不是每个函数都可以作为随机变量，从测度的角度出发，随机变量必须是波莱尔可测函数/Borel-measurable functions。直观的说，这个约束保证了对于给定的随机变量及其输出空间，我们可以不严格的将事件空间中的每个事件定义为输出$\\omega\\in\\Omega$的一组集合，其中$X(\\omega)$满足某些性质，如$\\{\\omega:X(\\omega)\\geq3\\}$）。通常，我们用大写字母$X(\\omega)$（表示基于实验输出$\\omega$的随机变量）或简写$X$来表示随机变量。我们使用小写字母$x$来表示随机变量可能取的值。\n",
    "\n",
    "**举例：**在上面的实验中，假设$X(\\omega)$表示在抛硬币结果序列$\\omega$中得到的面朝上的硬币的个数。因为只抛了$10$枚硬币，所以$X(\\omega)$只能取有限个值，这种随机变量也被称作**离散随机变量（discrete random variable）**。这里，实验结果集合相应的随机变量$X$取到$k$的概率为：\n",
    "$$\n",
    "P(X=k):=P(\\{\\omega:X(\\omega)=k\\})\n",
    "$$\n",
    "**举例：**假设随机变量$X(\\omega)$表示某放射性元素原子衰变所需要的时间。在这种情形下，$X(\\omega)$可以取到无数种可能的值，所以也被称作**连续随机变量（continuous random variable）**。我们将随机变量$X$取在实常量$a,b\\ (a\\lt b)$之间的概率记为：\n",
    "$$\n",
    "P(a\\leq X\\leq b):=P(\\{\\omega:a\\leq X(\\omega)\\leq b\\})\n",
    "$$\n",
    "\n",
    "### 2.1 积累分布函数（Cumulative distribution functions）\n",
    "\n",
    "为了确定随机变量服的概率测度，通常需要确定其[积累分布函数](https://zh.wikipedia.org/wiki/%E7%B4%AF%E7%A7%AF%E5%88%86%E5%B8%83%E5%87%BD%E6%95%B0)（[CDF](https://en.wikipedia.org/wiki/Cumulative_distribution_function)）或[概率质量函数](https://zh.wikipedia.org/wiki/%E6%A6%82%E7%8E%87%E8%B4%A8%E9%87%8F%E5%87%BD%E6%95%B0)（[PMF](https://en.wikipedia.org/wiki/Probability_mass_function)）或[概率密度函数](https://zh.wikipedia.org/wiki/%E6%A9%9F%E7%8E%87%E5%AF%86%E5%BA%A6%E5%87%BD%E6%95%B8)（[PDF](https://en.wikipedia.org/wiki/Probability_density_function)）中的至少一个。在这个小节及后两个小节中，我们会简要介绍这三种函数。\n",
    "\n",
    "积累分布函数指$F_X:\\mathbb R\\to[0,1]$，所代表的概率测度为：\n",
    "$$\n",
    "F_X(x)\\triangleq P(X\\leq x)\\tag{1}\\label{1}\n",
    "$$\n",
    "\n",
    "我们可以通过这个公式计算$\\mathcal F$中的任意事件的概率，下图为某个CDF的图像：\n",
    "\n",
    "<img src=\"./resource/sn02_image01.png\" width=\"350\" alt=\"\" align=center />\n",
    "\n",
    "**性质：**\n",
    "* $0\\lt F_X(x)\\lt1$；\n",
    "* $\\displaystyle\\lim_{x\\to-\\infty}F_X(x)=0$；\n",
    "* $\\displaystyle\\lim_{x\\to\\infty}F_X(x)=1$；\n",
    "* $x\\leq y\\implies F_X(x)\\leq F_Y(y)$。\n",
    "\n",
    "### 2.2 概率质量函数（Probability mass functions）\n",
    "\n",
    "对于离散随机变量，可以用一种更简便的方法表示随机变量的概率测度——直接表示出随机变量每个取值的概率。**概率质量函数**就是这样一种函数$p_X:\\Omega\\to\\mathbb R$，其中：\n",
    "$$\n",
    "p_X(x)\\triangleq P(X=x)\n",
    "$$\n",
    "\n",
    "在离散随机变量的情形下，我们使用$Val(X)$来表示随机变量$X$能够取到的值的集合，比如令随机变量$X(\\omega)$表示抛$10$次硬币面朝上的次数，则$Val(X)=\\{0,1,2,\\cdots,10\\}$。\n",
    "\n",
    "**性质：**\n",
    "* $0\\leq p_X(x)\\leq1$；\n",
    "* $\\displaystyle\\sum_{x\\in Val(X)}p_X(x)=1$；\n",
    "* $\\displaystyle\\sum_{x\\in A}p_X(x)=P(X\\in A)$。\n",
    "\n",
    "### 2.3 概率密度函数（Probability density functions）\n",
    "\n",
    "对于某些连续随机变量来说，它们的积累分布函数$F_X(x)$处处可导。在这种情形下，我们可以定义**概率密度函数**为对积累分布函数求导：\n",
    "$$\n",
    "f_X(x)\\triangleq\\frac{\\mathrm dF_X(x)}{\\mathrm dx}\\tag{2}\\label{2}\n",
    "$$\n",
    "这里需要注意的是，并不是所有连续随机变量都有概率密度函数（比如$F_X(x)$并不是处处可导的情形）。\n",
    "\n",
    "根据求导的性质，对于很小的$\\Delta x$有：\n",
    "$$\n",
    "P(x\\leq X\\leq x+\\Delta x)\\approx f_X(x)\\Delta x\\tag{3}\\label{3}\n",
    "$$\n",
    "我们可以使用CDF和PDF（如果存在）来计算不同事件的概率。不过需要强调的是，对于PDF给定任意一点$x$所求出的值并不是一个事件的概率，即$f_X(x)\\neq P(X=x)$。比如$f_X(x)$可以取到比一还大的值，但是$f_X(x)$在$\\mathbb R$上任意子集的积分永远不会超过一。\n",
    "\n",
    "**性质：**\n",
    "* $f_X(x)\\geq0$；\n",
    "* $\\displaystyle\\int_{-\\infty}^{\\infty}f_X(x)=1$；\n",
    "* $\\displaystyle\\int_{x\\in A}f_X(x)\\mathrm dx=P(X\\in A)$。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 期望\n",
    "\n",
    "假设$X$是一个PMF为$p_X(x)$的离散随机变量，$g:\\mathbb R\\to\\mathbb R$为任意函数。在这样的条件下，可以将$g(X)$看做是一个随机变量，我们定义$g(X)$的**期望（expectation）**或**期望值（expected value）**为：\n",
    "$$\n",
    "\\mathrm E[g(X)]\\triangleq\\sum_{x\\in Val(X)}g(x)p_X(x)\n",
    "$$\n",
    "如果$X$是一个PDF为$f_x(X)$的连续随机变量，则$g(X)$的期望值定义为：\n",
    "$$\n",
    "\\mathrm E[g(X)]\\triangleq\\int_{-\\infty}^{\\infty}g(x)f_X(x)\\mathrm dx\n",
    "$$\n",
    "直观来看，$g(X)$的期望可以看做是$g(X)$在不同的$x$取值上的平均权重，其中权重由$p_X(x)$或$f_X(x)$给出。作为期望定义的一个特例，我们注意到随机变量本身的期望$\\mathrm E[X]$就是当$g(x)=x$时的情形，这也被称为随机变量$X$的均值。\n",
    "\n",
    "**性质：**\n",
    "* 对任意常数$a\\in\\mathbb R$有$\\mathrm E[a]=a$；\n",
    "* 对任意常数$a\\in\\mathbb R$有$\\mathrm E[af(x)]=a\\mathrm E[f(x)]$；\n",
    "* 期望的线性性质$\\mathrm E[f(x)+g(x)]=\\mathrm E[f(x)]+\\mathrm E[g(x)]$；\n",
    "* 对于离散随机变量$X$有$\\mathrm E[1\\{X=k\\}]=P(X=k)$\n",
    "\n",
    "### 2.5 方差\n",
    "\n",
    "随机变量$X$的**方差（variance）**是一个度量随机变量在其均值处集中程度的量。随机变量$X$的方差的公式定义为：\n",
    "$$\n",
    "\\mathrm{Var}[X]\\triangleq\\mathrm E\\left[(X-\\mathrm E[X])^2\\right]\n",
    "$$\n",
    "使用上一小节的性质，我们可以从上面的公式推导出另一种方差的表达：\n",
    "$$\n",
    "\\begin{align}\n",
    "\\mathrm E\\left[(X-\\mathrm E[X])^2\\right]&=\\mathrm E\\left[X^2-2\\mathrm E[X]X+\\mathrm E[X]^2\\right]\\\\\n",
    "&=\\mathrm E\\left[X^2\\right]-2\\mathrm E[X]\\mathrm E[X]+\\mathrm E[X]^2\\\\\n",
    "&=\\mathrm E\\left[X^2\\right]-\\mathrm E[X]^2\n",
    "\\end{align}\n",
    "$$\n",
    "其中第二步使用了“常数的期望仍是常数”这一性质，即$\\mathrm E[\\mathrm E[X]]=\\mathrm E[X]$。\n",
    "\n",
    "**性质：**\n",
    "* 对任意常数$a\\in\\mathbb R$有$\\mathrm{Var}[a]=0$；\n",
    "* 对任意常数$a\\in\\mathbb R$有$\\mathrm{Var}[af(x)]=a^2\\mathrm{Var}[f(x)]$。\n",
    "\n",
    "**举例：**随机变量$X$服从均匀分布，其PDF在$x\\in[0,1]$上为$f_X(x)=1$，其他情况下为$0$，计算$X$的均值及方差：\n",
    "$$\n",
    "\\begin{align}\n",
    "\\mathrm E[X]&=\\int_{-\\infty}^{\\infty}xf_X(x)\\mathrm dx=\\int_0^1x\\mathrm dx=\\frac{1}{2}\\\\\n",
    "\\mathrm E\\left[X^2\\right]&=\\int_{-\\infty}^{\\infty}x^2f_X(x)\\mathrm dx=\\int_0^1x^2\\mathrm dx=\\frac{1}{3}\\\\\n",
    "\\mathrm{Var}[X]&=\\mathrm E\\left[X^2\\right]-\\mathrm E[X]^2=\\frac{1}{3}-\\frac{1}{4}=\\frac{1}{12}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "**举例：**假设$g(x)=1\\{x\\in A\\}, A\\subseteq\\Omega$，求$\\mathrm E[g(x)]$：\n",
    "* 离散情况：\n",
    "$$\n",
    "\\mathrm E[g(X)]=\\sum_{x\\in Val(X)}1\\{x\\in A\\}p_X(x)=\\sum_{x\\in A}p_X(x)=P(x\\in A)\n",
    "$$\n",
    "* 连续情况：\n",
    "$$\n",
    "\\mathrm E[g(X)]=\\int_{-\\infty}^{\\infty}1\\{x\\in A\\}f_X(x)\\mathrm dx=\\int_{x\\in A}f_X(x)\\mathrm dx=P(x\\in A)\n",
    "$$\n",
    "\n",
    "### 2.6 一些常见的随机变量\n",
    "\n",
    "* **离散随机变量**\n",
    "  * $X\\sim\\mathrm{Bernoulli}(p), 0\\leq p\\leq1$，即将一枚硬币面朝上的概率为$p$的硬币抛一次，观察面向上的实验。\n",
    "  $$\n",
    "  p(x)=\\begin{cases}p&\\textrm{if }p=1\\\\1-p&\\textrm{if }p=0\\end{cases}\n",
    "  $$\n",
    "  * $X\\sim\\mathrm{Binomial}(n,p), 0\\leq p\\leq1$，即将一枚面朝上概率为$p$的硬币独立的抛$n$次，观察面向上的实验。\n",
    "  $$\n",
    "  p(x)=\\binom{n}{k}p^x(1-p)^{n-x}\n",
    "  $$\n",
    "  * $X\\sim\\mathrm{Geometric}(p), p\\gt0$，即持续将一枚面朝上概率为$p$的硬币抛出，直到首次出现面向上为止，观察抛出次数的实验。\n",
    "  $$\n",
    "  p(x)=p(1-p)^{x-1}\n",
    "  $$\n",
    "  * $X\\sim\\mathrm{Poisson}(\\lambda), \\lambda\\gt0$，在非负整数上的概率分布，用于描述小概率事件在一定时长内发生的次数。\n",
    "  $$\n",
    "  p(x)=e^{-\\lambda}\\frac{\\lambda^x}{x!}\n",
    "  $$\n",
    "* **离散随机变量**\n",
    "  * $X\\sim\\mathrm{Uniform}(a,b),a\\lt b$，在区间$(a,b)$上概率密度处处相等的分布。\n",
    "  $$\n",
    "  f(x)=\\begin{cases}\\frac{1}{b-a}&\\textrm{if }a\\leq x\\leq b\\\\0&\\textrm{otherwise}\\end{cases}\n",
    "  $$\n",
    "  * $X\\sim\\mathrm{Exponential}(\\lambda),\\lambda\\gt0$，一种在非负实轴上呈衰减状的概率分布。\n",
    "  $$\n",
    "  f(x)=\\begin{cases}\\lambda e^{-\\lambda x}&\\textrm{if }x\\geq0\\\\0&\\textrm{otherwise}\\end{cases}\n",
    "  $$\n",
    "  * $X\\sim\\mathrm{Normal}(\\mu,\\sigma^2)$，也就是著名的高斯分布/正态分布/自然分布。\n",
    "  $$\n",
    "  f(x)=\\frac{1}{\\sqrt{2\\pi}\\sigma}\\exp\\left(-\\frac{1}{2\\sigma^2}(x-\\mu)^2\\right)\n",
    "  $$\n",
    "<img src=\"./resource/sn02_image02.png\" width=\"500\" alt=\"\" align=center />\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\\begin{align}\\end{align}"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}