Notes of Beauty of Math

近日打算完整地阅读吴军的《数学之美》，做一下笔记。

Chapter 1 - 文字和语言 vs 数学和信息

• 信息的冗余是安全的保障
• 语料是翻译的基础，尤其是双语版本
• 最短编码原理 - 高频字符用短码
• 信道窄对应信息的高压缩率 - 例如文言文与白话文
• 语料比语法更重要 - 对翻译系统来说

Chapter 2 - NLP - 从规则到统计

• 早期方法 - 语法+词性+构词法
• 上下文相关的文法复杂性极大 - 上下文无关的翻译难度为On^2，相关为On^6
• 统计模型 - 通信系统+隐马尔可夫

Chapter 3 - 统计语言模型

• P(s) = P(w1,…,wn) = P(w1)P(w2

  w1)…P(wn

  w1,w2…wn-1)

• P(wn	wn-N+1…wn-1) - N元模型 N-1阶马尔科夫假设

• 语料库中 P(wi

  wi-1)≈#(wi-1,wi)/#(wi-1)

• O(

  V

  ^N) - Google使用四元模型 - remains long-dependency problem

• 长尾低频问题：设置阈值，低于则给以权重λ<1，留白作为未知量降低过拟合
• 商业级别翻译系统：大数据量，训练数据和翻译目标匹配，降噪都很重要

Chapter 4 - 谈谈分词

• 分词二义性 - 语言歧义性
• P(A1,A2,…) > P(B1,B2,…) - > select A rather B
• 使用动态规划寻找最佳分词
• 此方法主要应用于中文，也可使用于英文手写词分界
• 翻译：大颗粒度更好；搜索：小颗粒度更好
• 分词问题基本上已经完全解决

Chapter 5 - 隐马尔可夫模型

• 翻译问题的数学本质 - argmaxP(s1,s2…

  o1,o2…) 求s1,s2,…

• 贝叶斯化 - P(o1…

  s1…)P(s1…)/P(o1…) 分母可忽略 因为定值

• 马尔可夫 A-0.6->B-1.0->C …

• 隐马尔可夫：sA->sB->sC

  ​ oA oB oC

• P(s1…

  o1…)=PI(t) (St

  St-1)P(Ot

  St)

  P(s1…) = PI(t) P(St

  St-1)

• P(Ot

  St)≈#(Ot,St)/(St) P(wi

  wi-1)≈#(wi-1,wi)/#wi-1 - 有监督学习

• 无监督方法：Banm-Welch 找输出序列的Mθ0模型，计算P(O

  Mθ0)，找到所有路径和概率，迭代使P(O

  Mθ1)>P(O

  Mθ0)，以此寻找局部最优解

Chapter 6 - 信息的度量和作用

信息的信息量和不确定性有直接关系

信息熵 H bit

H(x) = - ΣP(x)logP(x)

7000常用汉字→单字13bit(2^13)

分布不均→8-9bit

50万字250Mbit→320Kbit 国际编码1Mbit 差距=冗余度

不同的语言冗余度不同，汉字较少

若完全不相关则等式成立

互信息 I(X;Y) = ΣP(x,y)log(P(x,y)/P(x)P(y))

即了解前提下，消除X不确定性需要信息量∈[0,min(H(X),H(Y))]

完全相关=H（X）=H（Y）

完全不相关=0

用互信息可以解决翻译软件中的二义性问题

相对熵/交叉熵 衡量正值函数相关性

KL(f(x),g(x))=Σf(x)*log(f(x)/g(x)) 相同函数交叉熵为0

前后不可交换

可度量随机分布的差异性

Chapter 7 - 加里尼科和现代语言处理

年少的时间应用于成长而非学习，因为性价比低

足够的经费是出成果的必要条件

学习不犯错比学习成功更重要

Chapter 8 - 简单之美 布尔代数与搜索引擎

布尔值将计算与逻辑联系起来

用布尔运算可以进行大文件筛选

搜索索引包括一串关键词 1/0 为了加速，索引表可以分布式存储搜索并结构化

Chapter 9 - 图论和网络爬虫

图论的起点为交通遍历问题

爬虫为类似的遍历访问，用HashTable避免重复访问

BFS可以有限时间下载更多高相关性的内容

DFS可以减少握手时间，避免过多次数访问同一server

一般使用包括优先排序和队列的调度系统，更偏向于BFS

访问后解析，保存有用信息，HashTable保存，分布式存储更新

Chapter 10 - Google的民主表决式PageRank

PageRank算法 → 基于连接来源与数量计算权重排名

可以从任意初始化值迭代到真实值

稀疏矩阵+并行计算加速

A= [a11 … aM1, … , a1M … aMM] 为链接数

求 B = (b1, … , bn)^T 为排名

设B0 = N * [1/N], B = B*A

可优化为Bi = [α/N * I + (1-α)A]*Bi-1 矩阵相乘更新

chapter 11 - 如何确定网页和查询的相关性

需要以下信息：完备的索引，网页质量评估指标，用户偏好，相关性评估

IF 词频 → IDF 逆文本频率 词语出现的权重除以总出现率得到修正后的单词检索匹配权重 log(出现量/总出现率)

IDF 从信息论的角度上来看就是特定条件下关键词概率分布的交叉熵

综合权重约等于相关性*网页质量分数

chapter 12 - 有限状态机和动态规划 以寻路和导航为例

有限状态机有一个开始和终结状态，以及若干中间状态，和有向状态变化的条件

如果序列输入能从开始走到结束，则有效，否则无效

在寻路中需要实现模糊匹配，需要基于概率的有限状态机，基本等效于离散马尔科夫链

动态规划将大问题拆分为状态下的小问题来解决，降低计算复杂度

chapter 13 - Google AK-47的设计者

好的方法应该简单有效可靠易读

先解决80%的问题，长尾问题成本过高

chapter 14 - 余弦定理和新闻分类

新闻构建关键词特征向量

将相关性超过阈值的新闻分为小类，再作为整体合并成更大的类

可以用于论文的自动分类

优化技巧：保存向量长度，只计算非零元素，删除虚词

可以对文本进行位置加权，例如开头结尾综述权重更高

chapter 15 - 矩阵运算和文本处理中的分类问题

奇异值分解 - 将大矩阵分解为三个小矩阵相乘 A=XBY

X: 每个词与词义类的相关性

Y：文本分类结果，每一篇和每一个主题

B：词义类和主题的相关性

可以极大程度降低矩阵计算的时间复杂度

Chapter 16 - 信息指纹与其应用

伪随机数生成Hash值用于检索

信息指纹可以用于判断内容相似度与反盗版

Chapter 17 - 密码学的数学原理

凯撒密码 频率信息

最好的密码需要分布均匀且统计独立

N = P*Q

M = (p-1)*(q-1)

E 与 M互素作为公钥

E*D mod M = 1

D作为私钥

N公开

X^E mod N = Y 密码

Y^D mod N = X 原文

攻击算法很难，但是工程实现有漏洞

Chap 18 - 闪光的不一定是金子： 搜索引擎反作弊和搜索结果权威性

作弊方法：重复关键词，买卖链接

通信模型反作弊：在信息源上加强通信自身抗干扰能力 在传输上过滤噪声

分析噪声分布，通过向量模拟作弊特征，改进PageRank算法

权威性问题：判断引用来源，权威领域分类，构建权威性矩阵

Chap 19 - 数学模型的重要性

古埃及根据天狼星和太阳的位置判断时间，一个季度为365*4+1天，同样实现了闰年的计算

托勒密发明了球坐标，定义了经纬线，黄道，弧度制，制定了儒略历

格里高利十三世改进了儒略历，实现了现在的天文历法

开普勒三定律改进了日心说

正确的模型应当在形式上是简单的

大量的数据对优化很重要

修正方法不如寻找噪声根源

Chap 20 - 不要把鸡蛋放一个篮子：最大熵模型

最大熵模型： 保留全部的不确定性，将风险降到最小

对随机事件的概率分布进行预测，应当满足全部已知条件，不做主观假设

最大熵模型可以同时满足成千上万种不同条件，可应用于NLP和量化交易

Chap 21 - 拼音输入法的数学原理

双拼节省编码长度，但增加了歧义性，而且本身转化不够自然

五笔更不自然，甚至会中断思维

全拼虽然编码更长，但是门槛低，容错性好，输入转化自然

汉字的信息熵<10bit 每个字母可以表示log26≈4.7bit信息 理论上最低平均2.1键可以打字

以词为输入单位，再联系上下文信息，理论上可以降低至1.3次

实现需要特殊编码，欲速而不达。

全拼大概需要三次

拼音转汉字可以使用动态规划或者有限状态机的设计，寻找最大概率路径

可以构建个性化语言模型，寻找和用户输入接近的文本，在通用模型上插值

Chap 22 - NLP 的发展

标准语料库很重要

好的方法原理简洁精妙

Chap 23 - 布隆过滤器

散列表检查会导致存储空间过大

对每一个输入X，用随机生成器生成8个信息指纹，映射到16亿长度上的8bit位，设置为1

每一个检测，生成8个指纹，检查映射是否都为8

好处在于快速，省空间，但有一定的误识别率

补救方法为补充白名单存储冲突值

Chap 24 - 马尔科夫链拓展到贝叶斯网络

加权有向状态图中马尔科夫假设成立，则为贝叶斯网络

每个节点的概率都可以用贝叶斯公式计算

贝叶斯网络的拓扑结构比马尔科夫链灵活

理论上是NP完备问题

词，主题，文章可以构建为贝叶斯网络，进而构建关键词聚类

贝叶斯网络的训练因为NP完备，可以使用贪心算法优化

蒙特卡洛随机方法可以避免陷入局部最优

Chap 25 - 条件随机场，文法分析和其他

文法分析流程：分词 构成词组 给每个词组一个句子成分

文法分析只能用于正确规范的写作

深层分析后来转变到浅层分析

与隐马尔科夫链不用，在条件随机场中，观察值yi可能和前后xi+-n都相关

通过边缘分布寻找概率分布函数

可以应用于范围条件预测

Chapter 26 - 维特比算法

维特比算法属于动态规划算法，用于解决图中的最短路径问题

穷举有向图的所有路径成本太高

维特比基础：

1. 如果最短路径经过某节点，那么起点到该节点选择的路径一定是最短路径；
2. 如果记录了起点到某个状态所有节点的最短路径，最终的最短路径一定是其中之一；
3. 到状态i+1的最短路径只要基于所有i状态下节点的最短路径继续计算；

码分多址CDMA技术

在拓展频带上进行的拓频传输：

1. 较宽频带上传输，抗干扰
2. 难截获
3. 浪费频带少

频分多址FDMA：每路通信使用一个频率

时分多址TDMA：一个频带时间切片轮流使用

Chapter 27 - 期望最大化算法 ExpectationMaximization

文本的自收敛分类：

KNN聚类

收敛的必然性：

期望结果 - 点到中心距离d最小 中心之间距离D最大

聚类不变，d变小或者不变，若有聚类变化，则d变小，D变大；

EM函数可以对凸函数取得全局最优解，非凸函数则可能收敛到局部最优解。

Chapter 28 - 逻辑回归和搜索广告

广告选择会综合出价和点击率

F(z)=e^z / e^z + 1

用来估计点击率

可以用训练最大熵模型的IIS方法训练大量参数

Chapter 29 - 击破算法和云计算

分治算法-例如归并排序

MapReduce - 矩阵乘法计算可以将其分别分割为行列，单独取出计算再concat

如何拆分和高效合并则为工程问题

Chapter 30 - GoogleBrain和ANN

输入层-隐藏层-输出层

输出层需要一个非线性函数

理论上ANN可以拟合任何复杂曲线或者高维曲面

无监督学习需要人工设计合适的成本函数

相比贝叶斯网络，神经网络结构更简单标准，但序列处理能力更弱

大型神经网络需要分治算法，参数要保存在独立大型服务器

Chapter 31 - 大数据重要性

日常的感觉可能会和数据给出的结论相反

样本量越大，随机变量和数学期望值误差越小

统计样本的抽样代表性也很重要

大量数据在翻译和语音识别中起到明显作用

问卷调查会受到主观想法影响

Appendix

时间复杂度衡量算法复杂度

NP：算法计算量不超过N的多项式（n^k, k为常数）函数，如果存在一个多项式复杂度的算法就是P问题，可以用计算机高效解决；如果计算量比N的多项式函数高，则为NP问题，理论上可计算实际上做不到。

NP完备：NP问题可以用多项式时间内归约到NP完备问题

后记

错误丑陋的模型在特定场合也许勉强有效，但负面影响会逐渐展现直到系统崩溃