Learning From Data——Hypothesis Testing
上周讲的内容，和之前一样，从无到有推出来一堆东西。老师在白板上写Statistical Learning, Hypothesis Testing，当然是有关系的，但是这届课讲得内容应该只是上述二者的一小部分。比较神奇的是，最后竟然推到了VC Divergence。Amazing!
Binary Hypothesis Testing
假设$Y = {0,1}$，数据是以$P(X|Y=0)$或者$P(X|Y=1)$生成（iid）出来。
定义下面的表示：
$$P_X(X) = P(X|Y=0),Q_X(X) = P(X|Y=1)$$
我们观察的是一个数据序列$X={x_1,x_2,…,x_n} \in X^n$，长度为n的序列，判断它是以哪个hypothesis生成的($H_0$或者$H_1$).其中：
$$
H_0: Xiid,P_X(X) = P(X|Y=0),P_0 = P(Y=0);\iid,Q_X(X) = P(X|Y=1),P_1 = P(Y=1).
H_1: X
$$
上式中，$P_０,P_1$为先验分布(Prior Distribution)。
要做到这件事，我们需要做的就是最小化做出错误决定（decision error probability）的概率。
如何做出决定其实不难理解，由下面的式子：
$$
P[H_0|(x_1,…,x_n)] > P[H_1|(x_1,…,x_n)] \rightarrow H_0;\
P[H_0|(x_1,…,x_n)] < P[H_1|(x_1,…,x_n)] \rightarrow H_1.\
$$
不过这个想要从数据中计算出这个值并不容易，而想要计算出$P[(x_1,…,x_n)|H_0]$是很容易的。还好我们有贝叶斯公式（Bayes’s Rule）:
$$
P[H_0|(x_1,…,x_n)] = \frac{P_X(x_1)…P_X(x_n)P_0}{P(x_1,…,x_n)}
$$
同理我们可以得到：
$$
P[H_1|(x_1,…,x_n)] = \frac{Q_X(x_1)…Q_X(x_n)P_1}{P(x_1,…,x_n)}
$$
根据这个来决定哪个Hypothesis，称为MAP Decision Rule。最后我们整理一下得到：
$$
\frac{P_X(x_1)}{Q_X(x_1)}…\frac{P_X(x_n)}{Q_X(x_n)} > \frac{P_1}{P_0} \rightarrow H_0;\
\frac{P_X(x_1)}{Q_X(x_1)}…\frac{P_X(x_n)}{Q_X(x_n)} < \frac{P_1}{P_0} \rightarrow H_1.
$$
为了简化，我把上面两行写成一行，大于或者小于写成$?$.
学习机器学习到现在，对于上面的式子第一个反应当然是加$\log$，得到log-likelihood function：
$$
\sum_{i=1}^n \log \frac{P_X(x_i)}{Q_X(x_i)} ? \log \frac{P_1}{P_0}
$$
这时候我们得到一个minimal sufficient statistic.
所以在已知$P_X(X),Q_X(X),P_0,P_1$的情况下，这个问题是很好解决的。
M-Hypothesis Testing
我们将上面的２元情况拓展到$M$元，实际上这个结果并没有什么改变。
现在假设$Y = {1,…,M}$，我们有下面的Hypothesis:
| Hypothesis | x | $P_{X\vert Y}(X\vert Y=?)$ | $P(Y=?)$ |
|---|---|---|---|
| $H_1$ | $x\tilde{} iid$ | $P_1(X)$ | $ P_1$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $H_M$ | $x\tilde{} iid$ | $P_M(X)$ | $ P_M$ |
计算$P[H_i|(x_1,…,x_n)]$，而实际上：
$$
P[H_i|(x_1,…,x_n)] = \frac{P_i(x_i)…P_i(x_n)P(Y=i)}{P(x_1…x_n)}
$$
接下来的步骤和之前一样，注意在做决定的时候选择的策略一样有OVA,OVO两种。上面介绍的这种算是OVA。
Error Probability Of Optimal Decision
就二元的情况来说，发生的错误可能有两种：
- Type 1: $H_0$是对的，选择了$H_1$
- Type 2: $H_1$是对的，选择了$H_0$
这两种不同类型的错误在不同的场景下有不同的名字。
为什么会选错？实际上选错是因为，它是由$H_0$生成的，但是它却更像$H_1$生成的，也就是经验分布是$Q_x(X)$，而实际分布是$P_X(X)$。因此出现错误Type 1的概率为：
$$
P(\text{empirical distribution of }(x_1,…,x_n)\text{ is }Q_x|{x_1,…,x_n}\tilde~P_x)
$$
如何计算上面的概率？我们考虑的是当$n$非常大的时候比较理想的情况。这时候，如果Hypothesis 1是正确的，假如$X$有ｋ个取值分布为1到k，定义$q_i = Q_X(i)$，则序列中出现i的个数的期望值为$nq_i$，而Hypothesis 2滋生出这样序列的概率为：
$$
P = \prod_{i=1}^kP_x^{nq_i}(i) = e^{\sum_{i=1}^k nq_i \log P_x(i)}
$$
一共又有多少种这样可能的序列？答案是：
$$
\begin{align}
C_n^{nq_1}C_{n-nq_1}^{nq_2}…C_{n-nq_1-…-nq_{k-1} }^{nq_k}
&= \frac{n!}{(nq_1)!…(nq_k)!}\
&\approx \underbrace{\frac{\sqrt{2\pi n} }{\prod_{i=1}^k \sqrt{2\pi n q_i} } }{\alpha}\cdot \underbrace{\frac{n^n}{(nq_1)^{nq_1}…(nq_k)^{nq_k} } }{\beta}
\end{align}
$$
从(1)到(2)，是使用了Stirling’s Formula:
$$
n! \approx \sqrt{2\pi n} (\frac{n}{e})^n.
$$
在(2)中，由于$\alpha$与$\beta$相比之下几乎是可以忽略的，因此我们专注于后者：
$$
\begin{aligned}
\beta &= \frac{n^n}{(nq_1)^{nq_1}…(nq_k)^{nq_k} }\
&= \frac{1}{q_1^{nq_1}…q_k^{nq_k} }\
&= \exp(-\sum_{i=1}^k nq_i\log q_i)\
&= e^{nH(Q)}
\end{aligned}
$$
非常神奇，一个熵出现了。
因此我们可以得到：
$$
\begin{aligned}
&P(\text{empirical distribution of }(x_1,…,x_n)\text{ is }Q_x|{x_1,…,x_n}\tilde~P_x)\
&= \beta \times P\
&= \exp(-\sum_{i=1}^k nq_i\log q_i) \cdot \exp(\sum_{i=1}^k nq_i \log P_x(i))\
&= \exp(-n\sum_{i=1}^k q_i\log q_i + n\sum_{i=1}^k q_i \log P_x(i))\
&= \exp(-n\sum_{i=1}^k q_i\log \frac{q_i}{P_x(i)})\
&= \exp(-n D(Q_x\Vert P_x))
\end{aligned}
$$
KL-Divergence出现了！这个就是Chernoff Stein Lemma:
给定错误2$\leq \alpha$，则错误1~$ \exp(-n D(Q_x\Vert P_x))$. 实际的数学推导是非常复杂的，这里只是大概给个直观的解释。详细请参考：
Chernoff-Stein Lemma
这更像是一节信息论的课。