glossary_index.md · 李梦凡/Lihang

# 索引
![Hits](https://www.smirkcao.info/hit_gits/Lihang/glossary_index.md)

[TOC]

## 前言

有时候读书会卡住，也许只是我们看问题的角度问题。同样的问题，在书中不同的地方会有提到，或相关，或无关。这个文档类似书中的最后的索引， 会加入一些个人的理解。

每个内容单独一条。

如果只有一个页码参考第二版2019.05第一次印刷，如果有两个页码，那么第一个对应第一版，第二个对应第二版。

## Timeline

1. PCA; Pearson; 1901
1. PCA over random variable; Hotelling; 1933
1. First pattern recognition althgrithm; Fisher; 1936
1. Perceptron; Rosenblatt; 1957
1. Kmeans; MacQueen; 1967
1. KNN; Cover, Hart; 1967
1. EM; Dempster; 1977
1. DT: CART; Breiman; 1984
1. DT: ID3; Quinlan; 1986
1. BP; LeCun; 1987
1. LSA; Deerwester; 1990
1. SVM: Kernel; Boser, Guyon, Vapnik; 1992
1. DT: C4.5; Quinlan; 1993
1. SVM: Linear; Cortes, Vapnik; 1995
1. AdaBoost; Freund, Schapire; 1995
1. SVM: Regression; Drucker; 1996
1. SMO; Platt; 1998
1. Margin Theory; Schapire; 1998
1. NMF; Lee; 1999
1. PLSA; Hofmann; 1999
1. Boosted Tree; Friedman; 2000
1. CRF; Lafferty; 2001
1. LDA; Blei; 2002

## 基本想法

### 无监督学习

对给定的数据进行某种”压缩“，从而找到数据的潜在结构。

### 主成分分析

- 将数据规范化为每个变量均值为0，方差为1。
- 对数据做正交变换，原来由线性相关的变量表示的数据，通过正交变换变成由若干个线性无关的新变量表示的数据。新变量是可能的正交变换中变量的方差的和最大的，方差表示在新变量上信息的大小。

### 概率潜在语义分析

发现由隐变量表示的话题，即潜在语义。一个文本的内容由其相关话题决定，一个话题的内容由其相关单词决定。

### LDA的收缩吉布斯抽样算法
$P_{412}$

### 变分推理
$P_{412}$

### PageRank算法
$P_{415}$ 在有向图上定义一个随机游走模型，即一阶马尔可夫链，描述随机游走者沿着有向图随机访问各个结点的行为。

### PageRank一般定义
$P_{421}$ 基本定义的基础上导入平滑项

### Topic Modeling
$P_{321}$ 试图从大量的文本数据中发现潜在的话题，以话题向量表示文本的语义内容，以话题向量空间的度量更准确的表示文本之间的语义相似度。这是话题分析(Topic Modeling)的基本想法。

## Glossary

### 贝叶斯学习
$P_{391}$ LDA属于贝叶斯学习
$P_{369}$ 贝叶斯学习中经常需要进行三种积分运算：规范化，边缘化，数学期望。
$P_{401}$ 变分推理是贝叶斯学习中常用的含有隐变量模型的学习和推理方法。

### 信息

$P_{297}$ 新变量上信息的大小。

$P_{306}$ 信息是指原有变量的方差。

### Gram矩阵

$P_{34}$，$P_{45}$ 在感知机中第一次提到

$P_{119}$，$P_{139}$	讲核函数的时候也有用到

### 欧式空间

$P_{4}$ 输入输出空间可以是**有限元素的集合**，也可以是整个**欧式空间**。集合和欧式空间对应了两种情况，离散和连续。

### 凸优化

$P_{100}$

[CH07](CH07/README.md)

### 拉格朗日对偶性

$P_{225}$附录C

### 拉格朗日乘子法

$P_{182}$ BW算法中求Q函数极大化，因为$\pi,A,B$都满足等式约束条件

$P_{301}$ PCA中关于总体主成分的定理的证明。
$P_{346}$ EM算法M步

### 样本

$P_{4}$ 输入和输出对又称为样本

### KKT 条件

见附录C

### 经验

提到经验，说的都是和训练数据集相关的
$P_{352}$ 从样本得到经验分布，从而估计总体分布；或者从样本计算样本均值，从而估计总体期望。

### 对偶

感知机里面有提到，支持向量机里面有提到

### 生成模型
$P_{339}$

### 共现模型
$P_{339}$ 概率潜在语义分析

### 图模型
$P_{341}$ 生成模型属于概率有向图模型
$P_{386}$ 潜在狄利克雷模型是含有隐变量的概率图模型。

### 随机游走
$P_{351}$

### 分离超平面

$P_{26}, P_{102}$ 支持向量机里面也有

### 内积

$P_{25}, P_{78}, P_{117}$在感知机、逻辑回归、支持向量机里面都有用到
$P_{323}$ 词向量的相似度

### 非负矩阵分解

$P_{331}$

### 满条件分布
$P_{372}$

### 指示函数

$P_{10}$ 讨论测试数据集中的误差率和准确率的时候，提到指示函数。

$P_{40}, P_{37}$

这个函数在不同的教材上有不同的表示方式，比如在《深度学习》中表示为$\mathbf 1_{condition}$

另外， 张潼老师在IBM时候的文章，定义的和书中不是太一样， 注意体会之间的差异。
$$
I(f(x),y)=\begin{cases}
&1\ if\ yf(x)<0,\\
&1\ if\ f(x)=0\ and\ y=-1,\\
&0\ otherwise
\end{cases}
$$

指示函数还有一种表示空心方括号，这个在$LaTeX$里面要用个包来引用， 不写了。在AdaBoost参考文献[9]中用了这样的表达。

注意指示函数其实定义了0-1损失， 在AdaBoost算法的训练误差分析那部分，定理8.1实际上说的是指数损失是0-1损失的上界，然后用递推拿到了归一化系数连乘的形式。

### $L_p$距离

$P_{38}$

### 启发式方法

$P_{57}$决策树学习通常采用启发式方法，得到的决策树是次最优的。

### 单纯形

$P_{81}$，$P_{96}$单纯形是$n$维欧式空间中的$n+1$个仿射无关的点的集合的凸包。
$P_{348}$ 模型的参数分布可以由参数空间中的单纯形表示。
$P_{344}$ 单词单纯形与话题单纯形

### 熵，条件熵

$P_{60}$在决策树中首先提到

$P_{80}$最大熵原理部分也有提到，并有引用到第五章中的内容

$P_{166}$ $F$函数的定义中,有定义分布$\hat P(Z)$的熵

### KL散度

$P_{332}$ 或者相对熵

### 特征函数

$P_{82}$ $f(x,y)$描述输入$x$和输出$y$之间的某一事实。

$P_{196}$ 转移特征和状态特征

### 特征值分解
$P_{314}$ 将矩阵分解成特征值和特征向量。特征值说明特征的重要度，书中也说是主成分的方差贡献率。但是特征值分解要求矩阵是方阵。

### 动态规划

$P_{67}$决策树的剪枝算法可以由一种动态规划的算法实现。

$P_{184}$维特比算法实际上是用动态规划求解隐马尔可夫模型预测问题，即用动态规划求概率最大路径。

### 贝叶斯估计
$P_{59}$ 强调朴素贝叶斯和贝叶斯估计是不同的概念。

### 目标函数

$P_9$在经验风险最小化的策略或者结构风险最小化策略的情况下，经验或结构风险函数是最优化的目标函数

### 函数间隔

$P_{27},P_{97}$在[感知机](CH02/README.md)和[支持向量机](CH07/README.md)部分，都有函数间隔的概念，在[AdaBoost](CH08/README.md)部分，实际上也有间隔的概念在里面。

### 概率分布密度

$P_{162}$ 高斯分布密度, 书中的内容扩展下去看二维混合高斯模型, 对协方差矩阵的理解会有帮助.

### 多项分布

$P_{385}$ 多项分布定义
$P_{340}$ 条件概率分布属于多项分布

### 二项分布
$P_{388}$

### 指数族分布
$P_{389}$ 狄利克雷分布属于指数族分布

### 对数似然损失

$P_7$ 对数损失函数或者对数似然损失函数 $L(Y,P(Y|X))=-\log P(Y|X)$

### 对数似然函数

$P_{158}$ 面对一个含有隐变量的概率模型, 目标是极大化观测数据(不完全数据)Y关于参数$\theta$的对数似然函数, 即极大化
$$
\begin{aligned}L(\theta)=&\log P(Y|\theta)=\log \sum_Z P(Y, Z|\theta) \\
=&\log\left(\sum_ZP(Y|Z,\theta)P(Z|\theta)\right)
\end{aligned}
$$

### 对数线性模型

$P_{196}$ 线性链条件随机场是对数线性模型。

$P_{88}$ 最大熵模型与逻辑斯谛回归有类似的形式，它们又称为对数线性模型。

### One-hot Encoding

$P_{163}$ 注意这里书中没有明确的说明$\gamma_{jk}$是One-hot encoding, 也叫做1-of-K representation

$\gamma_j=\sum_{k=1}^K\gamma_{jk}=1, j=1,2,3,\dots, n$

### 基函数

$P_{144}$

### 基本分类器

$P_{147}$ 上面这两个不是一个概念

### 琴声不等式

$P_{159}$ EM算法导出部分讨论收敛性
$P_{455}$ KL散度定义
$P_{90}$ IIS算法导出部分确定界

### 约束最优化问题

$P_{83}$ 最大熵模型的学习可以形式化为约束最优化问题。

$P_{302}$ 求解主成分的过程是求解约束最优化问题

### 广义拉格朗日函数
### 拉格朗日乘子法
$P_{301}$ 采用拉格朗日乘子法求主成分。

### 泛化误差上界

$P_{15}$

### 代理损失函数

$P_{115}$

$P_{213}$也有说明

$P_{206}$预测最优解，条件概率最大的输出序列(标记序列)$y^*$

### 极大似然估计

$P_{9}$ 极大似然估计是经验风险最小化的例子。这个书中没有太多的解释，在《深度学习》里面有讲解，其实挺多书上都有提到。扩展下这个点，最大似然这个思想最早是高斯提出来的，費希尔将其发扬光大。1922年的文章60多页，提出了最大似然估计这个思想，讨论了一些性质。文章可以找到，費希尔凭借这个方法彻底撼动了皮尔逊的统治地位。

費希尔是英国统计学家，生物进化学家，数学家，遗传学家和优生学家。看头像还真是个可以靠颜值度日却不小心坠入学术的帅哥。

### 充分统计量

$P_{456}$

### 无偏估计

$P_{320}$

### 向量空间模型
Vector Space Model， VSM

$P_{322}$

### 仿射函数

$P_{116}$

### 线性变换

$P_{279}$ 线性变换很重要，在[SVD](./CH15/README.md)中第一次提到。
$P_{300}$ 在总体主成分的定义中也提到了线性变换，这真的是线性代数中一个非常重要的概念。

### 张成

$P_{451}$ 向量空间
$P_{325}$ 张成话题空间向量

### 因子负荷量

$P_{305}$ 第$k$个主成分$y_k$与变量$x_i$的相关系数$\rho(y_k,x_i)$称为因子负荷量，表示第$k$个主成分$y_k$与变量$x_i$的相关关系。

### 方差贡献率
$_{308}$ 第$k$主成分$y_k$的方差贡献率定义为$y_k$的方差与所有方差之和的比值，记作$\mu_k$

### EM算法
$P_{345}$ PLSA也是含有隐变量的模型，通常使用EM算法求解。
$P_{401}$ 变分EM算法
### 文本集合
### 单词文本矩阵
### 词向量
$P_{321}$ 
### 非负矩阵分解
$P_{321}$

### 反射变换

$P_{279}$

### 正交变换

$P_{297}$ 把线性相关的变量表示的观测数据转换成少数几个线性无关变量表示的数据，线性无关的变量称为主成分。

### 正交矩阵

$P_{304}$ 正交矩阵满足$A^\mathrm{T}A=AA^\mathrm{T}=I$

### 分块

$P_{288}$

### Manifold

$P_{247}$ 在降维部分有提到，但是没有展开

## Definition, Theory, Algorithm

### Definition

定义2.1 感知机

定义2.2 数据集的线性可分性

定义5.1 决策树

定义5.2 信息增益

定义5.3 信息增益比

定义5.4 基尼指数

定义6.1 逻辑斯谛分布

定义6.2 逻辑斯谛回归模型

定义6.3 最大熵模型

定义7.1 线性可分支持向量机

定义7.2 函数间隔

定义7.3 几何间隔

定义7.4 支持向量

定义7.5 线性支持向量机

定义7.6 核函数

定义7.7 正定核的等价定义

定义7.8 非线性支持向量机

定义9.1 Q函数

定义9.2 高斯混合模型

定义9.3 F函数

定义10.1 隐马尔可夫模型

定义10.2 前向概率

定义10.3 后向概率

定义11.1 概率无向图模型

定义11.2 团与最大团

定义11.3 条件随机场

定义11.4 线性链条件随机场

定义16.1 总体主成分
定义16.2 主成分的方差贡献率
定义16.3 主成分对原有变量的贡献率

### Theory

定理2.1 Novikoff

定理7.1 最大间隔分离超平面的存在唯一性

定理7.2

定理7.3

定理7.4

定理7.5 正定核的充要条件

定理7.6

定理8.1 AdaBoost的训练误差界

定理8.2 二类分类问题AdaBoost的训练误差界

定理8.3

定理9.1

定理9.2

引理9.1

引理9.2

定理9.3

定理9.4

定理11.1 Hammersley-Clifford定理

定理11.2 线性链条件随机场的参数化形式
定理16.1

定理16.2

定理16.3

定理C.1

推论C.1

定理C.2

定理C.3

### Algorithm

算法2.1 感知机学习算法的原始形式

算法3.1 k近邻算法

算法3.2 构造平衡kd树

算法3.3 用kd树的最近邻搜索

算法4.1 朴素贝叶斯算法

算法5.1 信息增益的算法

算法5.2 ID3算法

算法5.3 C4.5的生成算法

算法5.4 树的剪枝算法

算法5.5 最小二乘回归树生成算法

算法5.6 CART生成算法

算法5.7 CART剪枝算法

算法6.1 改进的迭代尺度算法 IIS

算法6.2 最大熵模型学习的BFGS算法

算法7.1 线性可分支持向量机学习算法-最大间隔法

算法7.2 线性可分支持向量机学习算法

算法7.3 线性支持向量机学习算法

算法7.4 非线性支持向量机学习算法

算法7.5 SMO算法

算法8.1 AdaBoost

算法8.2 前向分步算法

算法8.3 回归问题的提升树算法

算法8.4 梯度提升算法

算法9.1 EM算法

算法9.2 高斯混合模型参数估计的EM算法

算法9.3 GEM算法1

算法9.4 GEM算法2

算法9.5 GEM算法3

算法10.1 观测序列的生成

算法10.2 观测序列概率的前向算法

算法10.3 观测序列概率的后向算法

算法10.4 Baum-Welch算法

算法10.5 维特比算法

算法11.1 条件随机场模型学习的改进的迭代尺度法

算法11.2 条件随机场模型学习的BFGS算法

算法11.3 条件随机场预测的维特比算法

算法17.1 非负矩阵分解的迭代算法

算法A.1 梯度下降法

算法B.1 牛顿法

算法B.2 DFP算法

算法B.3 BFGS算法

李梦凡/Lihang

About

Releases

Contributors

Activities