【读书笔记】数学之美（上）

lionvsme

2019-09-08

作者：LogM

文章中的数学公式若无法正确显示，请参见：正确显示数学公式的小技巧

本文为《数学之美》的读书笔记。

图灵测试：判断机器是否智能
人工智能概念的提出：1956年，达特茅斯夏季人工智能研究会议
20世纪60年代，大家认为自然语言处理需要机器理解人的语言，研究重点在句法分析和语义分析，大多用人工规则。但自然语言中的规则实在太多了。
"The pen is in the box.", "The box is in the pen."
1970年，IBM华生实验室使用统计的方法将语音识别提高非常多。自然语言处理分成了规则和统计两个派别。到90年代，基于统计的方法成为主流。这一转变与语料和计算力增加有关。

判断一个句子是否合理：
$$P(S) = P(w_1, w_2, ... , w_n) = P(w_1) \cdot P(w_2|w_1) \cdot \cdot \cdot P(w_n|w_1, w_2, ..., w_n)$$
马尔科夫假设：一个词出现的概率只与前n个词有关，实际使用时，受计算速度限制，一般使用二元模型或者三元模型。比如二元模型可以写做：
$$P(S) = P(w_1) \cdot P(w_2|w_1) \cdot P(w_3|w_2) \cdot \cdot \cdot P(w_n|w_{n-1})$$
统计语言模型的平滑问题：
- 古德-图灵估计：假定语料中出现 $r$ 次的词有 $N_r$ 个，语料总大小为 $N$，则 $N = \sum{rN_r}$。当 $r$ 比较小时，统计可能不可靠，我们用 $dr$ 代替 $r$，$d_r = (r+1) \cdot N_{r+1} / N_r$，此时仍有 $N = \sum{d_r \cdot N_r}$。
  根据 Zipf 定律，$N_{r+1} < N_r$，故 $d_r < r$，$d_0 > 0$。
- 卡茨退避法：将古德-图灵估计应用在统计语言模型的平滑。
- 删除差值法：（低阶模型不容易发生零概率问题，用低阶来平滑高阶）

$$P(w_i|w_{i-2}, w_{i-1}) = \lambda(w_{i-2}, w_{i-1}) \cdot f(w_i|w_{i-2}, w_{i-1}) + \lambda(w_{i-1}) \cdot f(w_i)|w_{i-1} + \lambda \cdot f(w_i)$$

演变过程
- 查字典，最长匹配
  "上海大学城书店" -> "上海大学城书店"
- 查字典，最少词数
- 统计语言模型：判断哪种分词法出现的概率最大，使用 Viterbi 算法加速。
分词可以是粗粒度，也可以细粒度，一般对复合词使用嵌套结构
"北京大学", "北京大学"

用途：机器翻译、拼写纠错、手写体识别、图像处理、序列分析、股票分析...
通信模型。举例，英文翻译为中文的问题：S为中文，O为英文。
$$P(s_1, s_2, ...| o_1, o_2, ...) = \frac{P(o_1, o_2, ...| s_1, s_2, ...) \cdot P(s_1, s_2, ...)}{P(o_1, o_2, ...)}$$
马尔科夫过程（马尔科夫链）：符合状态 $s_t$ 只与上一状态 $s_{t-1}$ 有关的假设的随机过程。
隐马尔科夫模型：$s_t$ 是一个马尔科夫过程，$o_t$ 与 $s_t$ 相关且仅与 $s_t$ 相关。
$$P(s_1,s_2,...,o_1,o_2,...) = \prod{P(s_t|s_{t-1}) \cdot P(o_t|s_t)}$$
隐马尔科夫模型的三个基本问题：
- 给定一个模型，如何计算某个特定输出序列的概率：前向计算，简单
- 给定一个模型和某个特定的输出序列，如何找到最可能的状态序列：Viterbi 算法
- 给定足够量的观测数据，如何估计模型参数：转移概率 $P(s_t|s_{t-1})$，生成概率 $P(o_t|s_t)$
  - 如果有大量已标注的 $o_t$ 和对应的 $s_t$，简单
  - 如果只有观测到的 $o_1, o_2, ...$，鲍姆-韦尔奇算法（EM算法）

信息熵：
有32个球队参加比赛，夺冠可能性相等，我每猜一次花费1元，对方回答"对，小了，大了"，我最多猜5次（$log_2 32 = 5$）就可以知道答案，所以这个信息价值5元。
- $H = -(p_1 \cdot log p_1 + p_2 \cdot log p_2 + ... + p_{32} \cdot log p_{32})$
- $H(X) = -\sum{P(x)logP(x)}$
条件熵：
$$H(X|Y) = \sum_x{p(x) \cdot H(Y|X=x)} = - \sum_x{p(x)} \sum_y{p(y|x)log(p|x)}$$
$$H(X|Y) = -\sum_{x,y}{P(x,y)logP(x|y)}$$
互信息：
$$I(X;Y) = \sum{P(x,y) \cdot log \frac{P(x,y)}{P(x)P(y)}}$$
$$I(X;Y) = H(X) - H(X|Y)$$
相对熵（交叉熵，KL散度）：
$$KL(f(x)||g(x)) = \sum{f(x) \cdot log \frac{f(x)}{g(x)}}$$