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: X~iid,P_X(X) = P(X|Y=0),P_0 = P(Y=0);\\ H_1: X~iid,Q_X(X) = P(X|Y=1),P_1 = P(Y=1). \] 上式中，\(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~$ (-n D(Q_xP_x))$. 实际的数学推导是非常复杂的，这里只是大概给个直观的解释。详细请参考： Chernoff-Stein Lemma
这更像是一节信息论的课。