---
title: "数学之美"
description: "《数学之美》吴军的读书笔记"
image: "https://wileyzhang.com/posts/cover/e9d56066-6fc0-4734-9464-b375d2bf297a_7d561480d0e691749e3102debaf4ee75.jpg"
url: "https://wileyzhang.com/books/e9d56066-6fc0-4734-9464-b375d2bf297a"
date: "2021-04-23"
updated: "2021-04-23"
type: "book-note"
book: "数学之美"
author: "吴军"
status: "Finished"
douban_url: "https://book.douban.com/subject/10750155/"
tags: ["科普"]
reading_time_minutes: 9
estimated_tokens: 2940
---

# 数学之美

不确定性越大 信息熵越大，信息的作用就是消除不确定性

信息熵

“信息墒”  由香农1948年提出，指一个事物包含的信息量。一元信息墒的计算方式如下$`p_n`$代表事物n的概率

$$

H(U) = -\sum_{k=1}^n {p_n*log p_n}

$$

变量p的不确定性越大，墒也就越大，信息量也就越大

条件熵

对两个随机事件相关性的度量

确定其中一个随机事件的条件下，对消除另一个随机事件不确定性所提供的信息量

相对熵（交叉熵）

衡量两个取值为正数的函数的相似性

描述两个随机分布的差异性

### 语言的构成

语法+语义 = 语言

自然语言的发展有两种不同的方式，基于规则和基于统计两种处理方式

前期： 基于规则

最开始基于规则的方法 分析语法树。但是随着句子长度的增加，使用语法树，面临着高额的计算要求。

但是基于语义，对于严重依赖上下文和基本常识的信息的多义性 无法还好的解决

目前：基于统计

以语言纠错为例子

我有一个梦想

梦想又一个我

上述两个句子我们是如何判断对错的呢，其实我们判断对错的方法就是 在日常生活中 第一个句子出现的次数更多。类推，我们只要统计出句子(S=w1,w2,w3)出现的概率，就可以判断句子的对错。但是古往今来有那么多的句子，我们根本没办法计算。如何精简：

第一步：记录词与句子的概率，这样我们就不用存储固定句子的概率。但依然庞大

$$

P(S) = P(w_1,w_2,w_3)=P(w_1)*P(w_2|w_1)*P(w_3|w_1,w_2)

$$

第二步：马尔可夫对上述描述方法进一步进行了简化，只需要记录当前词与其前一个词一起出现的概率 即可

$$

P(S) = P(w_1)*P(w_2|w_1)*P(w_3|w_2)*P(w_i|w_{i-1})

$$

$$

P（w_i|w_{i-1}）= \frac{P(w_i,P(w_{i-1}))}{P(w_{i-1})}

$$

只需要计算联合概率$`P(w_{i-1},w_i)`$和边缘概率$`P(w_{i-1})`$即可.

### 在统计模型中处理零概率问题

为什么会有零概率？

当一个词不在数据中出现 就会导致该词的概率为0

零概率的影响？

零概率并不是意味着就不会发生

零概率会导致模型的不平滑

处理零概率

古德图灵估计：从概率的总量中分配很小的一部分给概率为0的事件

公式为：

$$

d_r=(r+1)\cdot N_{r+1}/N_r

$$

r是出现的次数

$`d_r`$是出现了r次的词的修改后次数

$`N_{r+1}`$ 是出现r+1次的词的数量

$`N_r`$ 是出现r次的词的数量

## 马尔可夫链

为了解决随机过程的问题

马尔可夫假设：随机过程中各个状态$`S_t`$的概率分布只与它前一个状态$`S_{t-1}`$有关

马尔可夫链：

![Untitled.png](https://wileyzhang.com/posts/images/e9d56066-6fc0-4734-9464-b375d2bf297a/e9d56066-6fc0-4734-9464-b375d2bf297a_b73632cddd708502df7d8eee2686017a.png)

这样我们就可以根据状态序列来推测 状态转移概率

### 隐马尔可夫

为了解决无法观察到状态序列的时候 推测状态转移概率

独立输出假设：每个时刻t会输出一个随机符号 $`O_t`$， 仅和$`S_t`$相关

隐马尔可夫模型：

![Untitled.png](https://wileyzhang.com/posts/images/e9d56066-6fc0-4734-9464-b375d2bf297a/e9d56066-6fc0-4734-9464-b375d2bf297a_ba2b7caa485ca461d555884096eb4eb1.png)

如何训练模型？

估计模型的参数

转移概率$`P(S_t|S_{t-1})=P(S_t,S_{t-1})/P(S_{t-1})`$

生成概率$`P(O_t|S_t) = P(O_t,S_t)/P(S_t)`$

如果有足够的标记数据，我们就可以计算出模型的参数。人工标记 成本过高

鲍姆-韦尔奇算法，通过观测大量的$`O_t`$，来推测转移概率和生成概率

鲍姆-韦尔奇算法步骤：

1. 找到一组能够输出序列O的模型参数（随机数），模型记为$`M_{\theta0}`$

> 💡 概率均匀分布时，可以产生任何输出

2. 可以算出$`M_{\theta0}`$产生序列O的概率（forward-backward算法），状态转移路径，状态输出

3. 现在将步骤2 的数据 当作 标注数据，重新计算新的模型参数，模型记为$`M_{\theta1}`$

4. 不断迭代，直到模型不在有明显的提高。期望最大化（EX。维比特算法）。局部最优

### 搜索的本质

下载，索引，排序

### 爬虫

   BFS (广度)   重要信息在首页，以及首页所链接的页面。 比如新闻网站

   DFS (深度)   不同的页面，需要建立多次握手，耗费大量的资源。比如维基百科

### PageRank算法

PageRank主要解决排序问题。

思想：投票机制，如果一个网页没其他很多网页链接，那么该网页的排名将会提高。为了更加准确，可以对来源网页进行权重的分配。

现实中一般还会将用户的点击行为添加进去计算排名，准确度更高

问题：

如何计算排名？

解：

假设每个网页的排名都是$`1/N`$,则所有网页的排名

$$

B_0=[\frac{1}{N},\frac{1}{N},...\frac{1}{N}]

$$

网页间的[邻接矩阵](https://wileyzhang.com/b9a5e325bc1345a6b5c4d4227499df93)为

$$

A=\begin{bmatrix}

a_{11} &\cdots & a_{1n} \\

\vdots & \ddots & \vdots \\

a_{m1} & \cdots & a_{mn}

\end{bmatrix}

$$

则，$`B_i`$为当前的网页的排名

$$

B_i=A \cdot B_{i-1}

$$

继续迭代，直到收敛，$`B=B\times A`$，一般来讲。只需要迭代10次即可

但是由于矩阵A非常的庞大，计算难度大，并且由于A 中很多数值都是0，所以可以采用[稀疏矩阵](https://wileyzhang.com/115eef788cc148d0bc8c40f0539e6d2f)进行平滑处理

$$

B_i=[\frac{\alpha}{N} \cdot I+(1-\alpha) \cdot B_{i-1}]

$$

其中$`\alpha`$为 一个较小的常数，N为网页的数量，$`I`$为单位矩阵

### TF-IDF（相关性计算）

词频$`TF=D_w/D`$

逆文本频率$`IDF=log(D/D_w)`$   这里使用log是指。一个特定条件下关键词的概率分布

D为总数，$`D_w`$为出现的次数

$$

TF-IDF=I(w)-TF(w)log \frac{M}{C(w)}

$$

I(w)为词的信息量，由大量文本训练得到

### 文本分类

首先TF-IDF 标记标记文本，后计算两个文本之间的余弦相似度。对于文本不同的部分，采用不同的权重，比如文本的标题和首尾段一般会比本体 提供更多的信息量

问题一：如何确定分类的特征文本？

人工标记，耗时耗力。采用自下而上不断合并的方法

1. 计算所有文本两两之间的相似度，把相似度达到阈值的文档划分为一个小类

2. 将分好后的小类各自合并，再在小类之间计算相似度，重复1 2 步骤

3. 迭代，直到某一个类的数量很大的时候停止

问题二：文本多，计算量大，如果减少复杂度？

1. 去除文中的虚词

2. 只考虑非零元素

3. SVD算法 奇异值分解

将矩阵分解为,其中（**文本分类中的意义**）

A为完整的矩阵

X矩阵为 每行代表一个词，每列代表一个语义相近的词类，值为词为和词类的相关性（近义词分类）

B矩阵为 表示词的类和文章的类的关系

Y矩阵为 每行代表一个主题，每列代表一个文本，值为文本和主题的相关性（找到每列值最大的行，就是该文本的分类）

![Untitled.png](https://wileyzhang.com/posts/images/e9d56066-6fc0-4734-9464-b375d2bf297a/e9d56066-6fc0-4734-9464-b375d2bf297a_7e8ebc3884c31f4fc71b8d45dbc9361e.png)

**数学中的意义**

X 为一个酉矩阵

Y 为酉矩阵的共轭矩阵

B 为对角矩阵

$$

A_{MN}=X_{MM} \times B_{MN} \times Y_{NN}

$$

### 地址的识别和导航

地址的识别一般采用 有限状态机

 1. 对于输入的错别字，采用基于概率的有限状态机

导航一般采用 动态规划

### 最大熵模型

在已知条件的概率模型集合中，找到熵最大的模型（即能包含所有事件的模型）

求解可以采用EM算法

### 贝叶斯网络

是一个概率图模型，且符合马尔可夫假设的有向图

![Untitled.png](https://wileyzhang.com/posts/images/e9d56066-6fc0-4734-9464-b375d2bf297a/e9d56066-6fc0-4734-9464-b375d2bf297a_69daefbc6ab268f9e1b1486f4dfe4398.png)

### 条件随机场

是一个概率图模型，且符合马尔可夫假设的无向图

![Untitled.png](https://wileyzhang.com/posts/images/e9d56066-6fc0-4734-9464-b375d2bf297a/e9d56066-6fc0-4734-9464-b375d2bf297a_bbd83a0647225a1a27881dd14622248e.png)

### 维特比算法

本质上也是一个动态规划的问题，通过局部最优，得到全局最优

凡是使用了隐含马尔可夫模型描述的问题 都可以用维特比算法解码

### 逻辑回归

一个事件出现的概率逐渐适应到一条逻辑曲线（S函数）上

$$

P=\frac{1}{\beta_0+\beta_1X_1+\beta2X_2}

$$

其中X为影响因素，$`\beta`$为参数值，可以通过IIS和GIS算法计算

### 期望最大化算法（EM）

1. 将矩阵映射到N维空间

2. 随机指定几个点设为中心点，计算所有点到中心点的距离，最近的划为一个类

3. 对已划分的每个类，重新计算类的中心点，使中心点到类中的每个其他点距离最小（中心点移动）

4. 重复2，3过程，直到 中心点的偏移很小（收敛）

---

> 本文由 WileyZhang 原创，首发于 [Wiley Blog](https://wileyzhang.com/books/e9d56066-6fc0-4734-9464-b375d2bf297a)。

```json
{
  "@context": "https://schema.org",
  "@type": "Article",
  "headline": "数学之美",
  "datePublished": "2021-04-23T00:00:00.000Z",
  "dateModified": "2021-04-23T00:00:00.000Z",
  "author": [
    {
      "@type": "Person",
      "name": "WileyZhang",
      "url": "https://wileyzhang.com/about"
    }
  ],
  "image": "https://wileyzhang.com/posts/cover/e9d56066-6fc0-4734-9464-b375d2bf297a_7d561480d0e691749e3102debaf4ee75.jpg",
  "about": {
    "@type": "Book",
    "name": "数学之美",
    "author": "吴军"
  },
  "mainEntityOfPage": {
    "@type": "WebPage",
    "@id": "https://wileyzhang.com/books/e9d56066-6fc0-4734-9464-b375d2bf297a"
  }
}
```