Skip to content

Latest commit

 

History

History
executable file
·
407 lines (211 loc) · 8.42 KB

glossary_index.md

File metadata and controls

executable file
·
407 lines (211 loc) · 8.42 KB

索引

前言

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

每个内容单独一条

Glossary

Gram矩阵

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

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

欧式空间

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

凸优化

$P_{100}$

CH07

拉格朗日对偶性

$P_{225}$附录C

拉格朗日乘子法

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

样本

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

KKT 条件

见附录C

经验

提到经验，说的都是和训练数据集相关的

对偶

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

分离超平面

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

内积

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

指示函数

$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}$单纯形是$n$维欧式空间中的$n+1$个仿射无关的点的集合的凸包。

熵，条件熵

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

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

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

特征函数

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

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

动态规划

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

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

贝叶斯估计

目标函数

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

函数间隔

$P_{27},P_{97}$在感知机和支持向量机部分，都有函数间隔的概念，在AdaBoost部分，实际上也有间隔的概念在里面。

概率分布密度

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

对数似然损失

$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_{90}$ IIS算法导出部分确定界

约束最优化问题

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

广义拉格朗日函数

泛化误差上界

$P_{15}$

代理损失函数

$P_{115}$

$P_{213}$也有说明

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

极大似然估计

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

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

Timeline

  1. First pattern recognition althgrithm; Fisher; 1936
  2. Perceptron; Rosenblatt; 1957
  3. KNN; Cover, Hart; 1967
  4. EM; Dempster; 1977
  5. DT: CART; Breiman; 1984
  6. DT: ID3; Quinlan; 1986
  7. BP; LeCun; 1987
  8. SVM: Kernel; Boser, Guyon, Vapnik; 1992
  9. DT: C4.5; Quinlan; 1993
  10. SVM: Linear; Cortes, Vapnik; 1995
  11. AdaBoost; Freund, Schapire; 1995
  12. SVM: Regression; Drucker; 1996
  13. SMO; Platt; 1998
  14. Margin Theory; Schapire; 1998
  15. Boosted Tree; Friedman; 2000
  16. CRF; Lafferty; 2001

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 线性链条件随机场

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 线性链条件随机场的参数化形式

定理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 条件随机场预测的维特比算法

算法A.1 梯度下降法

算法B.1 牛顿法

算法B.2 DFP算法

算法B.3 BFGS算法