读书笔记数学之美上

共计 2175 个字符，预计需要花费 6 分钟才能阅读完成。

作者：LogM

本文原载于 https://segmentfault.com/u/logm/articles，不允许转载~

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

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

图灵测试：判断机器是否智能
人工智能概念的提出：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)}}$$

第 1 章文字和语言 vs 数字和信息