###################################################
概率基础
###################################################


我们在高中的时候就已经学习过一些概率的相关知识，这里帮大家回顾一些基础的概念。

.. warning::
    注意，本章主要是为了大家回顾和理解一些基础概念，并不是学术定义，所以一些描述可能并不严谨。


概率分布
###################################################



我们从一个例子开始。

.. topic:: 箱子里取球的例子

    假设我们有两个箱子分别为 :math:`a_1,a_2` ，箱子中分别装有红色球和白色球。假设 :math:`a_1` 箱子中有4个红色球和6个白色球，
    :math:`a_2` 箱子中有8个红色球和2个白色球。 另外我们有一个特殊的硬币，投放后正面向上的概率是0.6，反面向上的概率是0.4。
    现在我们进行如下实验：

     - 步骤1. 投掷硬币，然后观察硬币的朝向，根据硬币的朝向决定从哪个箱子里取球。
     - 步骤2. 从箱子中取出一个球，并记录球的颜色。如果正面向上就从 :math:`a_1` 箱子随机取出一个球；如果反面朝上，就从 :math:`a_2` 箱子中随机取出一个球。

    我们设硬币朝向(或者说是决定的箱子)为随机变量A，则有 :math:`P(A=a_1)=0.6;P(A=a_2)=0.4` 。球的颜色记为随机变量B，
    则有 :math:``


个"随机事件"，比如投掷硬币这样的行为就可以看做是一个随机事件，
此外，我们可以用一个变量来代表一个"随机事件"。比如上述例子中我们把投掷硬币这一随机事件用随机变量A表示；
取出球的颜色用随机变量B表示。
我们可以把一个拥有不确定性(随机)结果的事件称为一


随机变量各个可能取值的概率表称为概率分布，比如随机变量A的概率分布为：

.. math::

    P(A=a_1)=0.6

    P(A=a_2)=0.4





式(1.25)可以称为随机变量的 **概率分布表** (用类似表格的形式表达随机变量各个可能取值的概率)。此外，一个随机变量的所有可能取值的概率相加一定是1。

.. math::
    \sum_A P(A) = 1



在这个例子中随机变量A的可能取值只有两个，当然有些时候是一个随机变量的可能取值可以有很多。
另外，随机变量的概率分布不仅限于上述的 "概率分布表" 的形式，还可以是一个函数的形式：

.. math::

    P(A) = f(a)



函数输入随机变量的可能取值，输出这个取值的概率，同时满足 :math:`\sum_{a \in A} f(a) = 1` ，
比如 :math:`f(a_1)=0.6;f(a_2)=0.4` 。


随机变量不仅可以是离散值变量，还可以是连续值变量，离散随机变量的概率分布函数称为 **概率质量函数(probability mass function,可简写成pmf)** ；
连续值随机变量的概率分布函数称为 **概率密度函数(probability density function,可简写成pdf)** 。

.. important::

    离散随机变量的概率质量函数输出值就是这个取值的概率，而连续值的概率密度函数输出的不是概率值，需要对概率密度函数积分才能得到概率值。
    具体可以参考《程序员的数学2:概率统计》这本书，这本书讲的通俗易懂。


.. hint::

     所有概率分布(包括下文介绍的边缘概率分布、条件概率分布、联合概率分布)都能用一个函数进行表达。




.. glossary::

    边缘概率
        通常来说，我们把单个变量的概率分布称为边缘概率分布。例如 P(A)，P(B) 等等。



.. glossary::

    条件概率
        当已经确定一个随机变量的取值的条件下，另一个随机变量的概率分布，表示成 :math:`P(B|A)` ,已知B的条件下A的概率分布。
        比如 :math:`P(A|B=b2)` 表示，已知 :math:`B=b_2` 的条件下，A的概率分布。


在这个例子中条件概率分布 :math:`P(B|A)` 的 *概率分布表* 是：

.. math::


    P(\text{红}|A=a_1)&=0.4

    P(\text{白}|A=a_1)&=0.6

    P(\text{红}|A=a_2)&=0.8

    P(\text{白}|A=a_2)&=0.2

.. glossary::

    联合概率

        多个随机变量联合在一起的概率分布就是联合概率分布。
        比如，随机变量A和随机变量B组成联合概率分布 :math:`P(A,B)` ，联合概率分布也可以有自己的概率分布函数 :math:`P(A,B)=f(A,B)` 。


.. hint::
    :math:`P(A=a_1,B=b_2)` ，表示 :math:`A=a_1` 并且同时 :math:`B=b_2` 的概率值，
    这时 :math:`P(A=a_1,B=b_2)` 表示的是具体的一个概率值。
    我们用 :math:`P(A,B)` 表示随机变量 A和B任意两两值组合的联合概率，其代表了 2*2=4 种组合情况的概率，
    这时 :math:`P(A,B)` 表示的就是联合概率分布。

在这个例子中，随机变量A和随机变量B的联合 *概率分布表* 如下形式：

.. math::

    P(A=a_1,B=\text{红色}) &= 0.24

    P(A=a_1,B=\text{白色}) &= 0.36

    P(A=a_2,B=\text{红色}) &= 0.32

    P(A=a_2,B=\text{白色}) &= 0.08


回顾一下要点：

- 边缘概率分布是单个变量的概率分布。
- 条件概率分布是在一个变量的取值已经确定的情况下，其它随机变量的概率分布。
- 联合概率分布是多个随机变量联合在一起的概率分布。


思考一下不难得出，联合概率分布是可以用边缘概率分布和条件概率分布的乘积表达的。

.. math::

    P(A,B) = P(A)P(B|A)


联合概率分布 :math:`P(A,B)` 表示其中的随机变量A和B取值组合形成的概率分布，那我们可以按照 "随机事件发生的顺序" 一个一个去计算。
比如我要算 :math:`P(A=a_1,B=\text{红色})` 的概率：

.. math::

    P(A=a_1,B=\text{红色}) &= P(A=a_1)P(B=\text{红色}|A=a_1)

    &= 0.6 \times 0.4 = 0.24



总的来说，联合概率分布可以分解成其包含的随机变量之间的一系列边缘概率分布和条件概率分布的乘积，其中每个乘项也叫"因子(factor)"，
这个分解过程也称为"因子分解(factorization)" 。




虽然上面例子中只包含两个随机变量，实际上是可以把很多个随机变量联合在一起的。
比如，假设有4个随机变量A，B，C，D，其可以组成4个变量的联合概率分布 :math:`P(A,B,C,D)` ，
其中部分变量也可以组成联合概率 :math:`P(A,B),P(A,C,D),P(B,D)` 等等。
而条件概率分布中的变量也可以是多个，比如 :math:`P(C,D|A,B),P(B,C,D|A)` 。


.. math::

    P(A,B,C,D) &= P(A)P(B,C,D|A)

        &=P(A)P(B|A)P(C,D|A,B)

        &=P(A)P(B|A)P(C|A,B)P(D|A,B,C)


此外一个大的联合概率分布，也可以拆解成多个子项联合概率分布的乘积：

.. math::

    P(A,B,C,D) = P(C,D)P(A,B)


.. important::

    总的来说，多个随机变量的联合概率分布可是因子分解成多个因子的乘积！



独立性
###################################################


如果随机变量A和B存在某种关系，互相有影响。

假设A影响着B

.. math::

    P(A,B) = P(A)P(B|A)



如果A和B是独立的随机变量，则有

.. math::


    P(A|B) = P(A)

    P(B|A) = P(B)

    P(A,B) = P(A)P(B)





.. todo::

    条件独立性，待补充


边缘化(marginalization)
###################################################



.. glossary::

    边缘化(marginalization)
        又称为边际化(英文翻译问题)，已知多个随机变量组成的联合概率分布，求解出其中部分随机变量的联合概率分布，
        这个过程被称为边缘化。字面意思就是：在一个大的随机变量集合中，把其中部分随机变量"边缘化(marginalization)" ，

        注意："边缘化" 这个词的目标变量是你要求的变量子集，而不是被"去掉"的那些。

比如，已知4个变量的联合概率分布 :math:`P(A,B,C,D)` ，我想要求 :math:`P(A,B)` 的概率分布，这时就需要"边缘化" 随机变量A和B。
就是要从 :math:`P(A,B,C,D)` "消除掉" 随机变量C和D，进而得到 :math:`P(A,B)` 。



那么如何进行边缘化呢？即我要如何"消除掉"其余的变量呢。


.. todo::

    待补充




在一个多变量的概率分布中，通过边缘化得到的部分变量子集的概率分布也可以称为是边缘概率分布，我们重新定义一下边缘概率分布：

**边缘概率分布:**

    边缘分布（Marginal Distribution）指在概率论和统计学的多维随机变量中，只包含其中 **部分变量（可以是多个联合）** 的概率分布。
    边缘概率分布可以通过对联合概率分布在除目标变量以外的其他变量（边缘化）求和(积分)得到

.. math::

    P(A)= \sum_B P(A,B) = \sum_B P(A|B)P(B)


.. warning::

    当已知P(B)和P(A,B),并且无法直接求得P(A)时，可以用上述边缘概率的方式求得。

对于N个变量的情况下：

.. math::

    P(x_n) = \sum_{x_1} \cdots \sum_{x_{n-1}} \sum_{x_{n+1}} \cdots \sum_{x_N}p(x_1,x_2,...,x_N)





贝叶斯定理
###################################################



假设A影响着B（A是因B是果；或者A先发生，B后发生）：

.. math::

    P(A|B) = \frac{P(A,B)}{P(B)} = \frac{P(B|A)P(A)}{P(B)} = \frac{P(B|A)P(A)}{ \sum^A P(B|A)P(A)}


.. tip::
    分母其实是分子的归一化。保证 P(A|B) 是小于1的浮点数，并且所有取值求和是1。



在机器学习中，常见问题是，我们能获得B的值，也就是观测值，需要求A的值或者概率分布，我们称A为潜在变量。

这时，我将A的边缘概率分布看成是A的先验概率P(A)，我们的目标是推断A的后验概率。
利用贝叶斯公式进行求解

.. math::

    P(A|B) = \frac{P(B|A)P(A)}{ \sum^A P(B|A)P(A)}  = \frac{P(B|A)P(A)}{ Z}


分母Z可以看成是分子的归一化系数，保证求出的结果是概率分布，对于任意分子其值都是相同的，所以有

.. math::

    P(A|B) \propto P(B|A)P(A)

通常我们会有很多B的观测值，

.. math::

    \begin{matrix} \text{后验概率}\\ \overbrace{P(A|B) }\end{matrix} \propto
    \begin{matrix} \text{似然} \\  \overbrace{\prod^N_{i=1} P(B_i|A)} \end{matrix}
    \begin{matrix} \text{先验概率} \\  \overbrace{ P(A)} \end{matrix}


.. note::

    当有多个观测值(样本)时，:math:`P(B_i|A)` 进行连乘，这里为什么是乘？
    因为我们一般假设 :math:`B_i` 条件独立于A，也就是在A的条件下，我们认为，不同观测样本互相间是独立的。


期望与方差
###################################################




常见概率分布
###################################################

离散变量
===========================

连续变量
===========================


计数变量
===========================




大数定律
###################################################

独立同分布
=======================


https://ocw.mit.edu/courses/mathematics/18-443-statistics-for-applications-fall-2006/lecture-notes/lecture3.pdf


http://staff.ustc.edu.cn/~zwp/teach/Prob-Stat/Lec11_slides.pdf


中心极限定理
===========================

https://zhuanlan.zhihu.com/p/69229677





信息论基础
###################################################
信息论是一门用数理统计方法来研究信息的度量、传递和变换规律的科学。
它主要是研究通讯和控制系统中普遍存在着信息传递的共同规律以及研究最佳解决信息的获限、度量、变换、储存和传递等问题的基础理论。
这似乎与概率论和机器学习的关注点相去甚远，但实际上两者之间有着密切的联系。
因为简单地表示数据，需要将短码字分配给高概率的位串，并将长码字保留给低概率的位串。
这与自然语言中的情况类似，常见的单词(如“a”、“the”、“and”)通常比罕见的单词短得多。
这种情况下需要一个模型来预测哪些数据是可能的，哪些是不可能的，这也是机器学习的一个中心问题。

信息熵
===================================================
符合分布 :math:`p` 的随机变量 :math:`X` 的熵，表示为 :math:`H(X)`，是度量随机变量不确定性的指标。
对于有 :math:`K` 个状态的离散随机变量，可以定义为：

.. math::

    H(X) = - \sum_{k=1}^{K}p(X = k)\log_{2}p(X=k)

通常使用以2为底的对数。对于离散随机变量符合均匀分布的时候信息熵最大。
因此，对于有 :math:`K` 个状态的离散随机变量，如果 :math:`p(x=k) = 1 / K`，此时的信息熵最大。
相反，最小的信息熵是随机变量的分布没有不确定性，此时的信息熵为0。

对于符合伯努利分布的随机变量 :math:`X \in \{0, 1\}`，也可以表示为 :math:`p(X=1) = \theta` 和 :math:`p(X=0) = 1 - \theta`。
因此，信息熵可以表示为：

.. math::

    H(X) &= -[p(X = 1)\log_{2}p(X=1) + p(X = 0)\log_{2}p(X=0)]

    &= -[\theta\log_{2}\theta + (1-\theta)\log_{2}(1-\theta)]


当 :math:`\theta=0.5` 时，也就是随机变量符合均匀分布，此时有最大的信息熵为1。


数据编码
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

数据编码在某些情况下需要对数据进行压缩，使用最有效的编码表示原始的数据。

压缩就是找出文件内容的概率分布，将那些出现概率高的部分代替成更短的形式。所以，内容越是重复的文件，就可以压缩地越小。

相应地，如果内容毫无重复，就很难压缩。极端情况就是，遇到那些均匀分布的随机字符串，往往连一个字符都压缩不了。

压缩就是一个消除冗余的过程，相当于用一种更精简的形式，表达相同的内容。而信息熵可以看作是数据压缩的一个临界值。

一般情况下，假设文件中的字符符合均匀分布，而一个字符在文件中出现的概率为 :math:`p`，那么在这个位置上最多可能出现 :math:`1/p` 种情况，
也就是需要 :math:`log_{2}\frac{1}{p}` 个比特表示文件中的字符。

假设一个文件由 :math:`n` 个部分组成，每个部分在文件中出现的概率为 :math:`p_{i}`，则压缩文件所需的比特数至少为：

.. math::
    log_{2}(\frac{1}{p_{1}}) + log_{2}(\frac{1}{p_{2}}) + ... + log_{2}(\frac{1}{p_{n}}) = \sum log_{2}(\frac{1}{p_{i}})

则平均每个部分所占用的比特数为，即：

.. math::
    p_{1} * log_{2}(\frac{1}{p_{1}}) + p_{2} * log_{2}(\frac{1}{p_{2}}) + ... + p_{n} * log_{2}(\frac{1}{p_{n}}) = \sum p_{i} * log_{2}(\frac{1}{p_{i}}) = E(log_{2}(\frac{1}{p}))

霍夫曼编码就是利用了这种大概率事件分配短码的思想，而且可以证明这种编码方式是最优的。
霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，
出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

KL散度
===================================================
两个概率分布 :math:`p` 和 :math:`q` 的差异度量指标可以使用KL散度，或者称之为相对熵，定义为：

.. math::

   KL(p||q) &= \sum_{k}p_{k}\log \frac{p_{k}}{q_{k}}

            &= \sum_{k}p_{k}\log p_{k} - \sum_{k}p_{k}\log q_{k}

            &= -H(p) + H(p, q)

KL散度不是距离，因为它不是对称的，KL散度的对称版本是JS散度，定义为：

.. math::

   JS(p_1, P_2) = 0.5KL(p_1 || q) + 0.5KL(p_2 || q), \ q = 0.5p_1 + 0.5p_2

:math:`H(p, q) = \sum_{k}p_{k}\log q_{k}` 称之为交叉熵。
交叉熵是指使用分布 :math:`q` 编码来自分布 :math:`p` 的数据所需的平均比特数。

KL散度是指使用分布 :math:`q` 编码来自分布 :math:`p` 的数据所需的平均额外比特数。
自然地，:math:`KL(p||q) \geq 0`，并且只有当 :math:`p=q` 的时候KL散度等于0。

互信息
===================================================

考虑两个随机变量 :math:`X` 和 :math:`Y`，假设想知道一个变量对另一个变量的了解程度，可以计算相关系数，但这只对实值随机变量有定义，而且，这是一个非常有限的相关性度量。
一个更一般的方法是确定联合概率分布 :math:`p(X, Y)` 和分布 :math:`p(X)p(Y)` 的相似程度，这被称之为互信息，定义为：

.. math::

  I(X; Y) = KL(p(X, Y) || p(X)p(Y)) = \sum_{x}\sum_{y}p(x, y)\log \frac{p(x, y)}{p(x)p(y)}

这里的 :math:`I(X, Y) \geq 0`，并且在 :math:`p(X, Y) = p(X)p(Y)` 时取等号，意味着随机变量相互独立的时候互信息为0。

为了深入理解互信息的含义，可以用联合熵和条件熵来重新表达互信息：

.. math::

  I(X; Y) = H(X) - H(X| Y) = H(Y) - H(Y|X)

:math:`H(Y|X)` 是条件熵，定义为 :math:`H(Y|X)=\sum_{x}p(x)H(Y|X =x)`，因此，可以将 :math:`X` 和 :math:`Y` 之间的互信息解释为观察 :math:`Y` 后 :math:`X` 的不确定性的减少，
或者说是观察 :math:`X` 后 :math:`Y` 的不确定性的减少。

连续型随机变量的互信息
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

对于连续型随机变量，首先需要离散化或者量化，具体是通过将每个变量的范围划分到不同的箱中，然后计算多少值落入每个箱中，最后再用离散随机变量的方式计算互信息。
不幸的是，使用箱的数目，在每个箱边界的位置，可能对最后的结果产生重大影响。

解决此问题的一种方法是尝试直接估计MI，而无需先执行密度估计。另一种方式是尝试多种不同大小和位置的箱，得到其中最大的互信息。