第1章 绪论

1.1 引言

机器学习致力于研究如何通过计算的手段，利用经验来改善系统自身的性能。其所研究的主要内容，是关于在计算机上从数据中产生“模型”(model)的算法，即“学习算法”(learning algorithm)。
本书中，“模型”泛指从数据中学得的结果，有的文献中用“模型”指全局性结果，而用“模式”指局部性结果。

1.2 基本术语

要进行机器学习，首先要有数据。
一批关于某种事物的数据的集合称为一个数据集(data set)。其中，每条记录是关于一个事件或对象的描述，称为一个示例(instance)或者一个样本(sample)。（注意：有时候整个数据集也被称为一个”样本“，因为它可以看作对样本空间的一个采样，故需要通过上下文判断”样本“为单个示例还是整个数据集。）
反映事物在某方面的表现或性质的事项称为属性(attribute)或特征(feature)。其上的具体取值，称为属性值或者特征值。
属性张成的空间称为属性空间、样本空间或输入空间。一般情况下，若某个样本有d个属性，则该样本空间即为d维样本空间，由于每一个示例都在该空间上对应一个点，每一个点对应一个坐标向量，故可以把一个示例称为一个特征向量。
从数据中学得模型的过程称作训练或者学习。

训练过程的数据称为训练数据(training data)，其中每个样本称为一个训练样本，训练样本组成的集合称为训练集(training set)。
学得的模型对应了数据中的某一潜在规律，故又称为假设(hypothesis)，该潜在规律自身，称为“真实”或“真相”。
关于示例结果的信息，称为标记(label)，所有标记的集合，称为“标记空间”或者“输出空间”。（类似方程，x11+x12+x13+…+x1d = y1 )

分类：若预测的是离散值，例如“1”“0”，此类学习任务称为分类(classification)。
回归：若预测的是连续值，则该学习任务称为回归(regression)。

分类中又可分为二分类与多分类任务，二分类顾名思义，只需分2类，一般分别称为“正类”与“反类”，且一般正类用“1”表示，反类用“0”表示。

学得模型后，用其进行预测的过程称为测试(test)，被预测的样本称为测试样本(test sample)。

此时引入聚类(clustering)概念，即将训练集中样本分为若干组，每一组称为一“簇”(cluster)。
在这里要明白聚类与分类的区别，就要先明白何为监督学习，何为无监督学习。

	监督学习：训练数据有标记信息的学习过程。亦称：有导师学习。
	无监督学习：训练数据没有标记信息的学习过程。亦称：无导师学习。

分类和回归属于典型的监督学习问题，而聚类属于无监督学习问题。故分类与聚类的区别显而易见。

分类是训练数据已有人为标记信息，计算机通过学习这些训练数据，将未出现在训练样本中的陌生的数据分到已有的类别中的过程。
聚类是训练数据没有任何标记信息，计算机需要自行寻找特征，将这些数据分为几个簇，然后将陌生的数据分到计算机自己划分的几个簇中的过程。

需要注意的是，机器学习的目的是使学得的模型可以更好的适用于未知样本。故引入"泛化“定义。

泛化：机器学习所学得模型适用于陌生数据的能力。

我们常说泛化性能优劣，即指模型对于陌生数据的适用性的好坏。
一般我们假设全体数据在样本空间上满足一个未知的分布，那么学习的目的就可以认为寻找最契合这个分布的一个函数来把训练样本完美的分到各自的类中。一般情况下，训练样本越多，我们得到的关于该分布的信息就越多，这样就越有可能找到这个函数，也就越有可能通过学习获得具有强泛化能力的模型。

1.3 假设空间

归纳与演绎是科学推理的两大基本手段， 前者是从特殊到一般的“泛化”过程，即从具体的事实归结出一般性规律；后者则是从一般到特殊的“特化”，即从基础原理推导出具体状况。
学习过程可以看作是一个在所有假设组成的空间中进行搜索的过程，目的是找到与训练集匹配的假设。而现实中，可能会有多个假设与训练集一致，即存在一个与训练集一致的“假设集合”，称之为“版本空间”。

1.4 归纳偏好

定义：机器学习算法在学习过程中对某种假设类型的偏好，称为归纳偏好。

需要注意，任何一个机器学习算法都必有其归纳偏好，否则将无法产生确定的学习结果。
一个神奇的结论：对于算法A来说，若其在某些方面比算法B好，那么必然存在一些方面B比A好。这个结论对任何算法均成立，无一例外！

“没有免费的午餐”定理(No Free Lunch Theorem, NFL)：无论学习算法A多么聪明，学习算法B多么笨拙，它们的期望性能完全一样（总误差与学习算法无关）。
但是需要注意，NFL定理的前提是所有问题出现的机会相同或者所有问题同等重要，但是实际情形并不是这样。
那么NFL定理有什么用呢？
NFL定理是让我们意识到：脱离具体问题而空泛的谈论哪一个算法更好毫无意义！

1.5 发展历程

1.6 应用现状

第2章 模型评估与选择

2.1 经验误差与过拟合

错误率(error rate)：分类错误的样本数占样本总数的比例称为错误率。
精度(accuracy)：精度 = 1 - 错误率。

如果在m个样本中有a个样本分类错误，那么错误率 E = a/m，精度 = 1 - E。
更一般地，把学习器的实际预测输出与样本的真实输出之间的差异称为误差(error)。
学习器在训练集上的误差称为训练误差(training error)或经验误差(empirical error)，在新样本上的误差称为泛化误差(generalization error)。
实际所希望的，是在新样本上能表现得很好的学习器，在这里引入两个重要概念：过拟合与欠拟合。

过拟合:学习器把训练样本学习的太好了，已经把训练样本自身的特点当做了所有潜在样本会存在的一般性质，会导致泛化性能下降，这种现象称为过拟合(overfitting)。
欠拟合:与过拟合恰恰相反。

上图即为学习发现过拟合时候的情况，可以看到随着学习轮数的增加，训练误差一直在下降，然而泛化误差在经历一小段下降后却开始升高，此时便需要采用一些措施来缓解过拟合问题。
而在过拟合的时候，训练集的loss和测试(验证)集的loss则有如下变化：
train_loss下降，test_loss下降一点后不再下降保持很高或者test_loss在下降一点后开始升高。

需要认识到，欠拟合通常是因为学习能力低下而导致的，这一点可以较容易克服，然而过拟合是无法彻底避免的，所能做的只有运用各种方法来缓解，常见的缓解过拟合的方法有正则化与dropout等。

2.2 评估方法

通常，我们使用一个测试集来测试学习器对新样本的判别能力，然后以测试集上的“测试误差”来作为泛化误差的近似。需要注意，测试集应与训练集互斥，即测试样本尽量不在训练集中出现或未在训练集中使用过。
很多时候，我们最初都会得到一个包含m个数据样本的数据集D，那么如何得到训练集S和测试集T呢？自然是选择合适的方法对D进行划分，产生出训练集S和测试集T。
以下介绍几种常见的划分方法：

2.2.1 留出法

何谓留出法(hold-out)？

留出法：直接将数据集D划分为两个互斥的集合，其中一个作为训练集S，另一个作为测试集T，保证S∩T=∅且S∪T=D。

注意：训练集与测试集的划分要尽可能保证数据分布的一致性，避免因数据划分过程引入额外的偏差而对最终结果产生影响。
如果从采样(sampling)的角度来看待数据集的划分过程，则保留类别比例的采样方法一般称为“分层采样”(stratified sampling)。
而单次使用留出法得到的估计结果往往不够稳定可靠，在使用留出法时，一般要采用若干次随机划分、重复进行实验评估后取平均值为留出法的评估结果。
例如：进行100次随机划分，每次产生一个训练集和测试集用于实验评估，100次会得到100个结果，而留出法的返回应当是这100个结果的平均。
常见分割数据比例大约为0.6~0.8，即每次取数据集中60%-80%作为训练集，剩下的作为测试集。

2.2.2 交叉验证法

何谓交叉验证法(cross validation)？
交叉验证法：将数据集D划分为k个大小相似的互斥子集，即D=D1∪D2∪…∪Dk，Di∩Dj=∅(i≠j)。每个子集Di都尽可能保持数据分布的一致性，即从D中分层采样得到。然后每次用k-1个子集的并集作为训练集，剩下的那个子集作为测试集，这样就可以得到k组训练/测试集，从而进行k次训练和测试，最终返回这k次测试的均值。
显然，交叉验证法评估结果的稳定性与保真性在很大程度上取决于k的取值，为了强调这一点，通常把交叉验证法称为k折交叉验证(k-fold cross validation)。k常取值：5,10,20。

与留出法相似，将D划分为k个子集有多种方法，假设k折交叉验证要随机使用不同的划分重复p次，则最终评估结果是这p次k折交叉验证结果的均值，常见有10次10折交叉验证（训练100次）。

交叉验证法也存在第一个特例：留一法(Leave-One-Out，简称LOO)：假定数据集D中有m个样本，令k=m，则会发现，m个样本只有唯一的划分方法来划分为m个子集——每个子集一个样本，所以留一法的训练集与数据集D相比只差一个样本，故留一法中被实际评测的模型与期望评估的用D训练出的模型很相似，因此，留一法的评估结果往往被认为较准确。但是在数据集很大的时候，训练m个模型的开销明显是难以忍受的。故NLF定理在这里也同样适用。

2.2.3 自助法

在留出法和交叉验证法中，由于保留了一部分样本作为测试，所以实际评估的模型中所使用的训练集比D小，而我们希望评估的是D训练出的模型，所以这必然会引入一些因训练样本规模不同而导致的估计偏差。所以我们在这里介绍自助法(bootstrapping)来解决这个问题。

自助法以自助采样(bootstrap sampling)为基础（自助采样也叫“可重复采样”与“有放回采样”）：
给定包含m个样本的数据集D，我们对它进行采样产生数据集D’：每次从D中随机选一个样本，将其拷贝如D’中，再将其放回D中，重复m次，那么就可以得到包含m个样本的数据集D’。显然D中一部分样本会在D’中多次出现，而另一部分不出现，由一个简单的估计可以得到样本在m次采样中不被采到的概率如下：

于是我们可以把D’当做训练集，D-D’作为测试集，这样，实际评估模型与期望评估模型都有m个训练样本，而我们仍然有数据总量1/3的样本用于测试，这样的测试结果，称为“包外估计”。
注意：自助法在数据量较少，难以有效划分训练集和测试集的时候很有用，然而自助法改变了初始数据分布，引入了估计偏差，故在数据量足够的时候，留出法和交叉验证法更常用一些。

2.2.4 调参与最终模型

给定包含m个样本的数据集D，在模型评估与选择过程中由于需要留出一部分数据进行评估测试，事实上我们只使用了一部分数据训练模型。
需要注意的是，我们通常把学得模型在实际使用中遇到的数据称为测试数据，为了加以区分，模型评估与选择中用于评估测试的数据集称为验证集(validation set)。例如，在研究对比不同算法的泛化性能时，我们用测试集上的判别效果来估计泛化性能，而把训练数据另外划分为测试集和验证集，基于验证集上的性能来进行模型选择和调参。

2.3 性能度量

对学习器的泛化能力进行评估，不仅需要有效可行的实验估计方法，还需要有衡量模型泛化能力的评价标准，这就是性能度量(performance measure)。要评估学习器f的性能，就需要把学习器预测结果f(x)同真实标记y进行比较。
本书介绍了如下几种在分类任务中常用的性能度量。

2.3.1 错误率与精度

错误率：分类错误的样本数占样本总数的比例。
精度：分类正确的样本数占样本总数的比例。

对数据集D，分类错误率定义为：

精度定义为：

2.3.2 查准率，查全率和F1

对于查准率和查全率的定义，书中有一个形象的例子：
信息检索中，我们经常会关心"检索出的信息中有多少比例是用户感兴趣的" 、“用户感兴趣的信息中有多少被检索出来了”，“查准率”(precision)与“查全率" (recall) 是更为适用于此类需求的性能度量。

对于二分类任务，可将样例根据其真实类别与学习器预测类别的组合划分为真正例(true positive)、假正例(false positive)、真反例(true negative)与假反例(false negative)四种情形。分别对应为TP、FP、TN、FN。

• TP：被模型预测为正类的正样本（实际为正，预测也为正）。
• TN：被模型预测为负类的负样本（实际为负，预测也为负）。
• FP：被模型预测为正类的负样本（实际为负，预测为正）。
• FN：被模型预测为负类的正样本（实际为正，预测为负）。
  分类结果的“混淆矩阵”如下定义：
  

查准率P（准确率）与查全率R（召回率）分别定义为：
一般来说，查准率高时，查全率低，这二者互相矛盾。
以查准率为纵轴，查全率为横轴，可以得到查准率-查全率曲线，简称“P-R”曲线。

A,B,C三条曲线代表三个不同的学习器，而如果一个学习器的P-R曲线完全包裹了另一个学习器，则认为前者性能优于后者，但是如果出现图中A，B曲线这种情况，出现交点时，就需要引入平衡点(Break-Event Point, BEP)来度量学习器的优劣。平衡点是查准率=查全率时的取值，图中A点平衡点高于B点，故可认为学习器A优于学习器B。

但BEP太过于简化，更常用的是F1度量：
为了表达我们对查准率/查全率的不同偏好，在这里引入F1度量的一般形式：
其中β>0度量了查全率对查准率的相对重要性。β=1时，退化为标准的F1；β<1时，认为查准率有更大影响；β>1时认为查全率有更大影响。

2.3.3 ROC与AUC

很多学习器是为测试样本产生一个实值或概率预测，然后将这个预测值与一个分类阈值(threshold)进行比较，若大于阈值则分为正类，否则为反类。实际上，根据这个实值或概率预测结果，可将测试样本进行排序，“最可能”是正例的排在前面，“最不可能”是正例的排在后面。排序本身的质量好坏，体现了学习器在不同任务下的“期望泛化性能”的好坏，ROC曲线则是从这个角度出发研究学习器泛化性能的有力工具。

ROC曲线的纵轴是“真正例率”(True Positive Rate, TPR)，横轴是“假正例率”(False Positive Rate, FPR)，两者定义如下：

进行学习器性能的比较时，与P-R图相似，若一个学习器的ROC曲线被另一个完全包裹，则可断言后者性能优于前者。若两个ROC曲线发生交叉，此时若要比较两者学习器性能的优劣，较为合理的判据是比较ROC曲线下的面积，即AUC(Area Under ROC Curve)。如图所示：

对角线对应于随机猜测模型，而点(0,1)则对应于将所有正例都排在反例之前。

2.3.4 代价敏感错误率与代价曲线

在现实中存在这样一类问题：不同类型的错误所造成的后果不同。例如在医疗诊断中，错误地把患者诊断为健康人与错误地把健康人诊断为患者，看起来都是犯了"一次错误"但后者的影响是增加了进一步检查的麻烦，前
者的后果却可能是丧失了拯救生命的最佳时机。
所以，为了权衡不同类型错误所造成的不同损失，可为错误赋予“非均等代价”(unequal cost)。

以二分类任务为例，可以根据任务的领域知识设定一个“代价矩阵”(cost matrix)。其中cost_ij表示将第i类样本分为第j类样本所付出的代价。一般来说，cost_ii=0；若将第0类判别为第1类所造成的损失更大，则cost₀₁>cost₁₀；损失程度相差越大，则cost₀₁与cost~10差别越大。
注意：一般情况下着重的是代价的比值而非代价的绝对值，例如cost₀₁:cost₁₀=5:1与50:10所起效果相同。

所以，在代价不均的情况下，我们所希望的不再是简单的最小化错误次数，而是最小化“总体代价”，例如：若cost₀₁:cost₁₀=6:1，那么将第0类错分到第1类所造成的代价（或者说损失）是把第1类错分到第0类所造成的代价的6倍，如果仅看错误次数，那么就会误认为m次错分第0类与m次错分第1类造成的损失是相同的，而实际上这两类大不相同。

在非均等代价的情况下，ROC曲线将不能直接反映出学习器的期望总体代价，而“代价曲线”(cost curve)则可达到这个目的，代价曲线的横轴是取值为[0,1]的正例概率代价：
其中p是样例为正例的概率；纵轴是取值为[0,1]的归一化代价：
在这里简单介绍规范化的概念：

规范化："规范化" (normalization)是将不同变化范围的位映射到相同的固定范围中，常见的是[0,1]。此时亦称"归一化"。

在上式中，FPR为之前定义的假正例率，FNR=1-TPR是假反例率。
因为代价曲线的绘制这一点用的地方较少，故具体的绘制过程本人就不再赘述，如果想要知道具体的绘制方法，可以自行搜素相关资料，本人在这里只是给出书中的代价曲线与期望总体代价图。

2.4 比较检验

有了实验评估方法和性能度量，看起来就能对学习器的性能进行评估比较了:先使用某种实验评估方法测得学习器的某个性能度量结果，然后对这些结果进行比较.但怎么来做这个"比较"呢?是直接取得性能度量的值然后"比大小"吗?实际上，机器学习中性能比较这件事要比大家想象的复杂得多.这里面涉及几个重要因素:首先，我们希望比较的是泛化性能，然而通过实验评估方法我们获得的是测试集上的性能，两者的对比结果可能未必相同;第二，测试集上的性能与测试集本身的选择有很大关系，且不论使用不同大小的测试集会得到不同的结果，即使用相同大小的测试集?若包含的测试样例不同，测试结果也会有不同;第二，很多机器学习算法本身有一定的随机性，即便用相同的参数设置在同一个测试集上多次运行，其结果也会有不同.那么，有没有适当的方法对学习器的性能进行比较呢?

统计假设检验(hypothesis test)为我们进行学习器性能比较提供了重要依据。下面我们介绍几种最基本的假设检验方法，本书默认以错误率为性能度量，用 ε 表示。此处错误率指泛化错误率。

2.4.1 假设检验

在实际问题中，我们无法获知泛化错误率，但是可以知道，测试错误率与泛化错误率相差较小，故在这里可以用测试错误率ε_t来推导泛化错误率ε。
泛化错误率为ε的学习器在一个样本上犯错的概率是ε；测试错误率ε_t意味着在m个样本中恰有ε_t*m个样本被误分类，可以估算出泛化错误率为ε的学习器恰将ε_t*m个样本误分类的概率如下式所示：
这也表达了在包含m个样本的测试集上，泛化错误率为ε的学习器被测得测试错误率为ε_t的概率。
上式对ε求偏导可知，该概率在ε = ε_t时取得最大值，符合二项分布。如图所示，若ε=0.3，则10个样本中测得3个被误分类的概率最大：

此处α为显著度，1-α为置信度。

更一般的，考虑假设ε<=ε₀，则在1-α的概率内所能观测到的最大错误率如下式计算：
直观的来看，对应于图中非阴影部分的范围。
此时若ε_t小于临界值，则可得出结论：能以1-α的置信度认为，学习器的泛化错误率不大于ε₀，反之亦然。

在很多时候我们并非仅做一次留出法估计，而是多次估计，这样会得到多个测试错误率ε₁…ε_k，则平均错误率μ和方差σ²为：

考虑到这k个测试错误率都可看作错误率ε₀的独立采用，则变量：

服从自由度为k-1的t分布，如图：

假设阴影部分的面积为(-∞,t_-α/2]和[t_α/2,∞]，则若上方变量位于临界值范围[t_-α/2,t_α/2]内，则可认为泛化错误率为ε₀，置信度为1-α。α常用取值为0.05，0.1。

2.4.2 交叉验证t检验

本人感觉与t分布相似，故此处略

2.4.3 McNemar检验

对二分类问题，使用留出法不仅可估计出学习器A 和B 的测试错误率，还可获得两学习器分类结果的差别，即两者都正确、都错误、一个正确另一个错误的样本数，所以有如下列联表：

故引入McNemar检验考虑变量：

服从自由度为1的卡方分布，具体显著度判别方法同t分布。

2.4.4 Friedman检验与Nemenyi后续检验

在很多时候，我们会在一组数据集上对多个算法进行比较。当有多个算法参与比较时，一种做法是在每个数据集上分别列出两两比较的结果，而在两两比较时可使用前述方法;另一种方法更为直接，即使用基于算法排序的Friedman 检验。
而如果Friedman检验所得算法性能都相同，那么急需要后续检验，常用的有Nemenyi后续检验，此处略。

2.5 偏差与方差

对学习算法除了通过实验估计其泛化性能，人们往往还想了解它为什么有这样的性能，此处用“偏差-方差分解”可以较好地解释。
学习算法的期望预测为：

使用样本数不同的训练集产生的方差为：

噪声为：

期望输出与真实标记的差别称为偏差(bias)，即：
经过推导可知：

即泛化误差可以分解为偏差，方差与噪声之和。

偏差度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力;方差度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响;噪声则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度。
偏差-方差分解说明，泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的。给定学习任务，为了取得好的泛化性能，则需使偏差较小，即能够充分拟合数据，并且使方差较小，即使得数据扰动产生的影响小。

第3章 线性模型

3.1 基本形式

给定由d个属性描述的示例x = (x₁;x₂;…;x_d)，其中x_i是x的第i个属性上的取值，线性模型(linear model)试图学得一个通过属性的线性组合来进行预测的函数，即：

一般用向量写成：


线性模型形式简单且易于建模，而且有很好的可解释性(comprehensibility)。
本章主要介绍几种经典的线性模型。我们先从回归任务开始，然后讨论三分类和多分类任务。

3.2 线性回归

给定数据集D = {(x₁,y₁),(x₂,y₂),…,(x_m,y_m)}，其中x_i = (x_i1;x_i1;…;x_id)，线性回归试图学得一个线性模型以尽可能准确地预测实值输出标记。即线性回归试图学得：
可见关键在于确定w和b，也就是衡量f(x)与y之间的差别。而之前介绍过，均方误差是回归任务中最常用的性能度量，因此我们可试图让均方误差最小化，即：
均方误差有非常好的几何意义，它对应了常用的欧几里得距离。而基于均方误差最小化求解模型的方法被称为最小二乘法(least square method)，在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧式距离之和最小。

求解w和b使得上式最小化的过程，被称为线性回归模型的最小二乘参数估计(parameter estimation)。我们可将上式（记为E_(w,b))分别对w和b求导，得到：

即可得到w和b的最优解的闭式(closed-form)解。

更一般的情形如开头的数据集D，样本由d个属性描述，此时被称为多元线性回归。
此处我们依然可以用最小二乘法来求解，不同的是我们把w和b吸收入向量形式定义为w^，把数据集D表示为一个m×(d+1)大小的矩阵X，每行对应一个示例，则有如下：
同理把标记也写成向量模式，则有：

令上式等于E_w^，则有：

上式为零即可得到最优解的闭式解。
如果X^TX为满秩矩阵或者正定矩阵，那么令上式为零可有：
即可轻易得到多元线性回归模型。
然而现实中X^TX往往不是满秩矩阵，许多任务中会遇到变量的数目超过样例数的情况，导致X的列数多于行数，显然不满秩，此时会解出多个**w^**满足均方误差最小的条件，选择哪一个作为输出就是问题，常见的做法是引入正则化项。

假设我们认为示例所对应的输出标记是在指数尺度上变化的，那就可以将输出标记的对数作为线性模型逼近的目标，即：
这就是对数线性回归(log-linear regression)，在形式上虽然仍然是线性回归，但实质是在求取输入空间到输出空间的非线性函数映射。如图所示：
对数线性回归是让y=ln y，而如果令y变换为其他的形式，可以得到更多的线性回归函数。我们统称为“广义线性模型”。

3.3 对数几率回归

上一节讨论了如何使用线性模型进行回归学习，但若要做的是分类任务该怎么办？只需找一个单调可微函数将分类任务的真实标记y与线性回归模型的预测值联系起来。
考虑二分类任务，输出标记为y∈{0,1}，而线性回归模型产生的预测值z = w^Tx+b是实值，故需将z转换为0/1值，于是想到单位阶跃函数：

即若预测值z 大于零就判为正例；小于零则判为反例；预测值为临界值零则可任意判别。具体图示如下图所示：
由于阶跃函数不连续，故不能用作广义线性模型，故我们找到一个对数几率函数来在一定程度上近似单位阶跃函数，可以看到，对数几率函数是常见的Sigmoid函数。将对数几率函数代入之前所讲y中，有：
由此看出，实际上是在用线性回归模型的预测结果去逼近真实标记的对数几率，因此，其对应的模型称为“对数几率回归”(logistic regression)。
注意：虽然名字是回归，但实际上是一种分类学习的方法。

那么上式的w和b如何确定呢？
若将y视为后延概率估计，则上式可以重写为：
显然可以得到：

于是，我们可以利用最大似然法(maximum likelihood method)来估计w和b。
此时对率回归模型最大化“对数似然”(log-likelihood)：
即令每个样本属于其真实标记的概率越大越好。
具体推导过程在这里略，见书。

3.4 线性判别分析

线性判别分析(Linear Discriminant Analysis，简称LDA)是一种经典的线性学习方法，由于其最早被Fisher提出，故又名“Fisher判别分析”。
LDA 的思想非常朴素: 给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离;在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别。

若将数据投影到直线w上，则两类样本的中心在直线上的投影分别为w^Tμ₀和w^Tμ₁；若将所有样本点都投影到直线上，则两类样本的协方差分别为w^T∑₀w和w^T∑₁w。
于是，要让同类样例投影点尽可能接近，可以让同类样例投影点的协方差尽可能小；而欲使异类样例的投影点尽可能远离，可以让类中心之间的距离尽可能大。于是我们得到了一个欲最大化的目标：
定义“类内散度矩阵”(within-class scatter matrix)
和“类间散度矩阵”(between-class scatter matrix)
则上式个重写为：
这就是LDA欲最大化的目标，即S_b和S_w的“广义瑞利商”。

那么关键就在于w的确定。由于上式分子与分母都是关于w的二次项，故其的解与w的长度无关，只与其方向有关，不防令w^TS_ww = 1，则上式等价于：
由拉格朗日乘子法，得到：
λ是拉格朗日乘子，书中未给详细推导过程，只在附录添加了拉格朗日乘子的一些定义和公式，我也没用动手去推导，因为我也不会推导。。。
由于S_bw的方向恒为μ₀-μ₁，故不妨令
代入式中可以得到：
由此即得到了w的具体计算方法。
此外再定义一个“全局散度矩阵”：
这是在将LDA推广到多分类任务时，可能需要的一个参数定义。可见使用以上三个散度矩阵的任意两个，都可以多分类实现LDA。
对于多分类任务，常见的一种实现时采用优化目标：
上式可以用下式求解：
可见W的闭式解其实是N-1个最大广义特征值所对应的特征向量组成的矩阵。
若将W视为一个投影矩阵，则LDA将样本投影到了N-1维空间上，N-1往往远小于数据原有的属性数 ，于是，LDA也常被视为一种经典的监督降维技术。

3.5 多分类学习

在现实中，我们所遇到的大多数问题其实是多分类学习任务。
考虑N个类别C₁…C_N，多分类学习的基本思路是“拆解法”，即将多分类任务拆为若干个二分类任务求解。
最经典的拆分策略有三种：“一对一”(one vs. one ,OvO)，“一对其余”(One vs. Rest, OvR)，和“多对多”(Many vs. Many, MvM)。
一对一的基本思想如下：将数据集中的N个类别两两配对，产生N(N-1)/2个二分类任务。在测试时，把新样本同时交给所有分类器，于是得到N(N-1)/2个分类结果，最终结果可以通过投票产生；即把被预测的最多的类别别作为最终结果。
一对其余的思想如下：每次将一个类的样例作为正类，其他都作为反类来训练N个分类器。在测试时若只有一个分类器预测为正类，则对应的类别标记为最终结果，若有多个分类器预测为正类，则考虑各分类器的预测置信度，选择置信度最大的类别标记作为分类结果。
下图为简单的示意图：

容易看出，OvR 只需训练N 个分类器，而OvO需训练N(N - 1)/2个分类器，因此，OvO的存储开销和测试时间开销通常比OvR 更大. 但在训练时，OvR 的每个分类器均使用全部训练样例，而OvO的每个分类器仅用到两个类的样例，因此，在类别很多时。OvO 的训练时间开销通常比OvR 更小，至于预测性能，则取决于具体的数据分布，在多数情形下两者差不多。
MvM 略。

3.6 类别不平衡问题

前面所述分类学习方法都有一个共同的基本假设：不同类别的训练样例数目相同。
类别不平衡(class-imbalance)就是指分类任务中不同类别的训练样例数目差别很大的情况。本文假设反例数目远大于正例。
介绍类别不平衡学习的一个基本策略——“再缩放”(rescaling)。
目前有三类做法：

• 直接对训练集的反类样例进行“欠采样”，即去除一些反例使得正反例数目接近。
• 对训练集的正例进行“过采样”，即增加一些正例使得正反例数目相似。
• 第三类则是基于原始训练集进行学习，在用训练好的分类器进行预测时再进行其他操作。

第4章 决策树

4.1 基本流程

决策树(decision tree)是一种常见的机器学习方法。以二分类任务西瓜分类为例，我们可以得到一个如图的决策树：
上面这棵决策树可以参考数据结构的二叉树，理解起来很简单。

一般来说，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点都对应一个属性测试；每个结点包含的样本集合根据测试结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的"分而治之" (divide-and-conquer) 策略。
决策树的生成其实是一个递归过程。在决策树基本算法中，有三种情形会导致递归返回：

• 当前结点包含的样本全属于同一类别，无需划分。
• 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分。
• 当前结点包含的样本集合为空，不能划分。
  下面附上决策树学习基本算法：
  结合算法可以很好的理解上方所述的三种情形的具体内涵，此处如果有数据结构二叉树的知识，会理解的更好。
  在这里，我简单说一下我对于上方三种情形的理解：
  首先，决策树的主要目的是分类，也就是说只要剩下的是一类，就可以返回，那么自然，如果剩下的不是一类，那自然进行递归。
  第一种情况，如果D中剩下的所有训练样本都是一个类，那自然不用继续递归，直接返回，对应算法的2-4行。
  第二种情况，属性集A为空是什么意思呢？首先要明白，决策树的划分过程是依据属性值的不同划分的，那么属性值如果为空就是说所有的属性值都已经划分过了，已经到整个树的最深了，到了叶子结点了，那么剩下的训练样本自然可以视为一类，直接返回。或者说属性值还没有划分结果，但是剩下的所有样本的所有属性值都对应相等，那么在属性空间上就可以认为剩下的所有样本都是一个点，那自然可以都划分为一类，直接返回。此处对应算法的5-7行。
  第三种情况，什么时候递归呢？自然是属性值上两种情况都不满足时递归，也就是说A剩下的属性不为空，并且D中剩下的所有样本对应A剩下的属性的具体值也不一样，在属性空间上不是一个点，那么自然不能认为D中剩下的所有样本是一个类，此时便需要继续递归。依照A剩下的属性来递归产生分支结点，直到出现前两种情况，才可以返回。此处对应算法的8-15行。

4.2 划分选择

决策树的关键在于上方算法的第8行，即如何选择最优划分属性。
一般来说，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能是同一类，即结点的“纯度”(purity)越来越高。

4.2.1 信息增益

“信息熵”(information entropy)是度量样本集合纯度最常用的一种指标。
计算时约定，p=0时，plog2p = 0。由极限可知，信息熵的最小值为0，最大值为log2|γ|。
假设离散属性a有V个可能的取值，若使用a对样本集D来划分，就会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为a^v的样本，记为D^v。
可以根据上式计算出D^v的信息熵，有可能不同的分支结点包含的样本数不同，所以赋予权重，即样本数越多的话分支结点的影响越大，那么就可以计算出属性a对样本集D进行划分所获得的"信息增益"(information gain)：
一般而言，信息增益越大，就认为用属性a来进行划分所获得的纯度提升最大。著名的ID3学习算法就是以信息增益为准则来选择划分属性。
具体示例可见书。

4.2.2 增益率

信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，使用“增益率”(gain ratio)来选择最优划分属性，增益率准则对可取值数目较少的属性有所偏好。增益率定义为：
IV(a)称为属性a的“固有值”。a的V越大， IV(a)通常会越大。

4.2.3 基尼指数

CART决策树(classification and regression tree)使用“基尼指数”(Gini index)来选择划分属性。公式如下：
属性a的基尼指数定义为：
一般选择划分后基尼指数最小的属性作为最优划分属性。

4.3 剪枝处理

剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段。
在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得"太好"了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。
基本策略：“预剪枝”(pre-pruning)和"后剪枝"(post-pruning)。
预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来划分性能提升，则停止划分当前结点为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
这其实很简单，
我们给出一个训练集：

4.3.1 预剪枝

预剪枝其实很简单，就是基于信息增益准则来进行划分属性选择。结合下图一目了然：
可见预剪枝其实就是计算划分前和划分后的验证集精度，只有划分后精度变大了，才会划分，其他的就直接一刀切不再划分。这一点其实在C语言的算法设计与分析和数据结构课程中就有过介绍。

4.3.2 后剪枝

后剪枝策略其实与预剪枝差不多，只不过后剪枝是从下而上进行考虑。

4.4 连续与缺失值

4.4.1 连续值处理

之前讨论的都是离散属性，但实际上现实中会有很多连续属性的任务。
对于连续属性，需要用到连续属性离散化技术。最简单的策略是二分法(bi-partition)对连续属性进行处理。
给定样本集D和连续属性a，假定a在D上有n个不同的取值，将这些值从小到大排列{a¹,…,aⁿ}。基于划分点t可将D分为子集D^-_t和D⁺_t，前者包含a上取值不大于t的样本，后者包含剩下的。因此，对于连续属性a，可考察包含n-1个元素的候选划分点集合：
即把区间[aⁱ,aⁱ⁺¹)的中位点作为候选划分点。然后就可以像离散属性值一样来考察这些划分点，选择最优划分点来对样本进行划分。信息增益变为如下公式：
需注意的是，如果当前结点划分属性还是连续属性，则该属性还可以为其后代结点的划分属性。

4.4.2 缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。如果简单放弃不完整样本，那明显是对数据的浪费。如图是一个不完整样本的数据集的示例：
我们需解决两个问题: (1) 如何在属性值缺失的情况下进行划分属性选择？
(2) 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

4.5 多变量决策树

若我们把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：轴平行(axis-parallel)，即它的分类边界由若干个与坐标轴平行的分段组成。
此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。
若能使用斜的划分边界，则决策树模型将大为简化。“多变量决策树”就是能实现这样的划分的决策树。在多变量决策树中，与传统的单变量决策树不同，其不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。如图所示：

第五章 神经网络

前提：机器学习中的神经网络指的是“人工神经网络”，而不是生物意义上的神经网络。

5.1 神经元模型

神经网络的定义(本书)：神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。
神经网络中最基本的成分是神经元(neuron)模型，即上述定义中的“简单单元”。
在生物神经网络中，每个神经元与其他神经元相连，当它"兴奋"时，就会向相连的神经元发送化学物质，从而改变这些神经元内的电位;如果某神经元的电位超过了一个"阈值" (threshold)，那么它就会被激活，然后向其他神经元发送化学物质。这一点也被很好的利用在了人工神经网络里。

目前所用的神经元模型：M-P神经元模型(创始人是McCulloch and Pitts)。如图：
在这个模型中，神经元接收到来自其他n个神经元传递进来的输入信号，这些信号通过带权重的连接进行传递，神经元接受到的总输入值将与神经元的阈值进行比较，然后通过“激活函数”(activation function)处理以产生神经元的输出。
此处式子类似第三章所讲的线性模型，还是很好理解的。
理想中的激活函数是如图所示的阶跃函数，其将输入值映射为输出值“0”或“1”，但阶跃函数因为不连续、不光滑等不好的性质，故常用Sigmoid函数作为激活函数。典型的Sigmoid函数如图所示，它把可能在较大范围内变化的输入值挤压到(0,1)的范围输出，故也可以称为“挤压函数”。

这里所讲只是一个神经元模型，而如果很多个神经元模型按一定的层次结构连接起来，就会形成网状结构，于是就得到了神经网络。如图：

5.2 感知机与多层网络

感知机(perceptron)由两层神经元组成，输入层接受外界输入信号后传递给输出层，输出层是M-P神经元，也叫做“阈值逻辑单元”(threshold logic unit)。
简单的感知机模型如图：
可以看到，感知机的本质其实就是一个数学式子：
它的几何解释如下图（二维）：
(参考：https://www.cnblogs.com/turingbrain/p/7355265.html）其中w是平面的法向量。
所以结合其几何解释就会发现，感知机的学习目的其实是求得一个能够将训练集正实例点和负实例点完成正确分开的分离超平面。
感知机也可以实现简单的逻辑运算，例如逻辑与、逻辑或和逻辑非运算。
这里仅用逻辑与运算进行讲解：
逻辑与：输入x1与x2均为True时输出才为True，结合理想感知机的激活函数为阶跃函数可知，当w1=1、w2=1且θ=2时（此时y=f(1×x1+1×x2-2))，即在x1=x2=1时该输出层才输出1，其他情况都输出0。同理可以得出感知机完成其他逻辑运算的条件。

一般情况，给定训练数据集，权重w_i(i=1,2,…,n)以及阈值θ可通过学习得到。阈值θ可看作一个固定输入为-1.0的“哑结点”(dummy node)所对应的连接权重w_n+1，这样，权重和阈值的学习就可统一为权重的学习。
对训练样例(x,y)，若当前感知机的输出为y^，则感知机权重应当如下调整：
其中η∈(0,1)被称为学习率。
（感知机的学习策略与梯度下降见另一篇博客）
需注意的是，感知机只有输出层神经元进行激活函数处理，即只拥有一层功能神经元(functional neuron)。若两类模型线性可分，则一定存在一个线性超平面可以将其分开，但是如上图(d)所示异或的非线性可分的模型就需要用到多层功能神经元。
要解决异或的非线性可分问题其实也很简单，只需要两层感知机就能解决异或问题，如图所示：
其中，输入层与输出层之间的那一层神经元，被称为隐层或隐含层(hidden layer)，隐含层和输出层神经元都是有激活函数的功能神经元。
更一般的神经网络就是如下图的层级结构，每层神经元与下层神经元全互连，神经元之间不存在同层连接，也不存在跨层连接。这样的网络结构通常称为“多层前馈神经网络”。由于下图所示的神经网络的前一层的每一个神经元都与后一层的所有神经元相连，故把这种神经网络通常称为全连接神经网络。
需要注意，输入层神经元仅仅是接受输入，而隐层与输出层则都包含功能神经元。神经网络的学习过程，就是根据训练数据来调整神经元之间的"连接权" (connection weight) 以及每个功能神经元的阈值。

5.3 误差逆传播算法

误差逆传播(Back Propagation)又称为反向传播算法，是迄今为止最成功的神经网络学习算法，适用于绝大多数的场景，非常重要。
通常说“BP网络”时，一般指用BP算法训练的多层前馈神经网络。

给定训练集D = {(x₁,y₁),…,(x_m,y_m)}，x_i∈R^d，y_i∈R^l，即输入示例由d个属性描述，输出l维实值向量。如下图：
给出一个拥有d个输入神经元，l个输出神经元，q个隐层神经元的多层前馈网络结构，其中输出层第j个神经元的阈值由θ_j表示，隐层第h个神经元的阈值由γ_h表示。输入层第i个神经元与隐层第h个神经元之间的权值为v_ih，隐层第h个神经元与输出层第j个神经元之间的权值为w_hj，假设激活函数都是sigmoid函数。
对训练例(x_k，y_k)，假定神经网络的输出为y^_k = (y^₁ ^k,…, y^_l ^k)，即：
则网络在(x_k，y_k)的均方误差为：
BP是一个迭代学习算法，采用感知机学习规则对参数进行更新估计，则任意参数v的更新估计为：
下面以w_hj为例来进行推导。
BP算法基于梯度下降策略，以目标的负梯度方向对参数进行调整，对上方的均方误差，给定学习率η，有：
可知有：
显然有：
又可知sigmoid函数的一个性质：
故有：

所以可以得到BP算法中对于w_hj的更新公式：

可以发现，权值与结果有关！
同理有：
其中：
下图给出了BP算法的基本流程：

对每个训练样例， BP 算法执行以下操作:先将输入示例提供给输入层神经元，然后逐层将信号前传，直到产生输出层的结果;然后计算输出层的误差(第4-5行)，再将误差逆向传播至隐层神经元(第6行)，最后根据隐层神经元的误差来对权值和阈值进行调整(第7行)。该迭代过程循环进行，直到达到某些停止条件为止，例如训练误差己达到一个很小的值。

上述所讲只是BP算法对w_hj的误差的处理，而实际上BP算法的目的是要最小化训练集D上的累积误差：
根据上方所讲，可以推导出对于累积误差最小化的更新规则，称为累积误差逆传播算法。
一般来说，标准BP算法每次更新只针对单个样例，参数更新的非常频繁，而且对不同样例进行更新的效果可能出现“抵消”线性，故标准BP算法往往要经过很多轮的迭代。累积BP算法直接针对累积误差最小化，在读取整个训练集一遍后才对参数进行更新，更新频率小很多。但在很多任务重，累积误差下降到一定程度后，进一步下降会很慢，这时标准BP往往有很好的解，尤其在D较大时更明显。
由于BP算法强大的表示能力，BP神经网络经常遭到或拟合，有两种策略来缓解BP网络的过拟合：

1. 早停(early stopping)：将数据分成训练集和验证集，训练集用来计算梯度、更新连接权和阈值，验证集用来估计误差，若连续多轮训练集误差降低但验证集误差升高，则停止训练，同时返回具有最小验证集误差的连接权和阈值。
2. 正则化(regularization)：在误差目标函数中增加一个用于描述网络复杂度的部分，例如权值与阈值的平方和。

5.4 全局最小与局部最小

若用E表示神经网络在训练集上的误差，其显然是关于权值w和阈值θ的函数。此时，神经网络的训练过程可以看做是一个参数寻优过程，即在参数空间中，寻找一组最优参数使得E最小。
有两种最优： “局部最小”(local minimum)和“全局最小”(global minimum)。
直观地看，局部极小解是参数空间中的某个点，其邻域点的误差函数值均不小于该点的函数值;全局最小解则是指参数空间中所有点的误差函数值均不小于该点的误差函数值。两者对应的E(ω;θ) 分别称为误差函数的局部极小值和全局最小值。
显然参数空间内梯度为0的点，只要其误差函数值小于相邻点的函数值，就是局部极小点，一个函数可能有多个局部极小点，但只有一个全局最小值，且全局最小一定是局部最小。

寻找局部最小点与全局最小点的常用方法是梯度下降法，相关内容可以查看我的另一篇博客：https://blog.csdn.net/yhdsss875/article/details/121244061

明显，如果误差函数有多个局部最小，则不能保证找到的解一定是全局最小，对这种情形，我们称参数寻优陷入了局部极小。现实中通常采用以下方法来试图跳出局部极小：

• 以多组不同参数值初始化多个神经网络，按标准方法训练后，取其中误差最小的解作为最终参数。这相当于从多个不同的初始点开始搜索，这样就可能陷入不同的局部极小从中进行选择有可能获得更接近全局最小的结果。
• 使用“模拟退火”(simulated annealing)技术。
• 使用SGD。随机梯度下降由于加入了随机因素，因此即使陷入局部最小点，其计算出的梯度仍然可能不为零，这样就有机会跳出局部极小继续搜索。

遗传算法(genetic algorithms)也常用来训练神经网络以更好的逼近全局最小。
注意：上述用于跳出局部最小的技术大多是启发式，理论上缺乏保障。

5.5 其他常见神经网络

5.5.1 RBF网络

RBF(Radial Basis Function， 径向基函数)网络是一种单隐层前馈神经网络，使用径向基函数作为隐层神经元激活函数，输出层则是对隐层神经元输出的线性组合。假定输入d维向量x，输出为实值，则RBF网络可表示为：
其中q为隐层神经元个数，c_i和w_i分别是第i个隐层神经元所对应的中心和权重，ρ(x,c_i)是径向基函数，这是某种沿径向对称的标量函数，通常定义为样本x到数据中心c_i之间欧式距离的单调函数。常用的高斯径向基函数形如：

5.5.2 ART网络

竞争型学习(competitive learning) 是神经网络中一种常用的无监督学习策略，在使用该策略时，网络的输出神经元相互竞争，每一时刻仅有一个竞争获胜的神经元被激活，其他神经元的状态被抑制。这种机制亦称"胜者通吃" (winner-take-all) 原则。
ART(Adaptive Resonance Theory，自适应谐振理论)网络是竞争型学习的代表，该网络由比较层、识别层、识别阈值和重置模块构成。
在接收到比较层的输入信号后识别层神经元之间相互竞争以产生获胜神经元。竞争的最简单方式是计算输入向量与每个识别层神经元所对应的模式类的代表向量之间的距离，距离最小者胜。获胜神经元将向其他识别层神经元发送信号，抑制其激活。若输入向量与获胜神经元所对应的代表向量之间的相似度大于识别阈值，则当前输入样本将被归为该代表向量所属类别，同时，网络连接权将会更新，使得以后在接收到相似输入样本时该模式类会计算出更大的相似度。从而使该获胜神经元有更大可能获胜;若相似度不大于识别阈值，则重置模块将在识别层增设一个新的神经元，其代表向量就设置为当前输入向量。

5.5.3 SOM网络

SOM(Self-Organizing Map, 自组织映射)网络是一种竞争学习型的无监督神经网络，他能将高维输入数据映射到低维空间(通常为二维)，同时保持输入数据在高维空间的拓扑结构，即将高维空间中相似的样本点映射到网络输出层中的邻近神经元。如图：
SOM 网络中的输出层神经元以矩阵方式排列在二维空间中，每个神经元都拥有一个权向量，网络在接收输入向量后，将会确定输出层获胜神经元，它决定了该输入向量在低维空间中的位置。SOM 的训练目标就是为每个输出层神经元找到合适的权向量以达到保持拓扑结构的目的。
SOM 的训练过程很简单:在接收到一个训练样本后。每个输出层神经元会计算该样本与自身携带的权向量之间的距离，距离最近的神经元成为竞争获胜者，称为最佳匹配单元(best matching unit)。然后，最佳匹配单元及其邻近神经元的权向量将被调整，以使得这些权向量与当前输入样本的距离缩小。这个过程不断迭代，直至收敛。

5.5.4 级联相关网络

一般的神经网络模型通常假定网络结构是事先固定的，训练的目的是利用训练样本来确定合适的连接权、阈值等参数。与此不同， 结构自适应网络则将网络结构也当作学习的目标之一，并希望能在训练过程中找到最符合数据特点的网络结构。
级联相关(Cascade-Correlation)网络就是结构自适应网络的重要代表。
两个主要成分：“级联”和“相关”。级联指建立层次连接的层级结构。在开始训练时，网络只有输入层和输出层，随着训练进行，新的隐层神经元逐渐加入，从而创建起层级结构。当新的隐层神经元加入时，其输入端连接权值是固定的。相关是指通过最大化新神经元的输出与网络误差之间的相关性啦训练相关参数。

5.5.5 Elman网络

与前馈神经网络不同，“递归神经网络”(recurrent neural networks)允许网络结构中出现环形结构，从而可让一些神经元的输出反馈回来作为输入信号。这样的结构与信息反馈过程，使得网络在t时刻的输出状态不仅与t时刻的输入有关，还与t-1时刻的网络状态有关。
Elman网络如图，其隐层神经元的输出被反馈回来，与下一刻的输入层神经元提供的信号一起，作为隐层神经元在下一时刻的输入。

5.5.6 Boltzmann机

神经网络中有一类模型是为网络状态定义一个"能量" (energy) ，能量最小化时网络达到理想状态，而网络的训练就是在最小化这个能量函数。
Boltzmann机是一种“基于能量的模型”，其神经元为两层：显层和隐层。显层用于表示数据的输入与输出，隐层则被理解为数据的内在表达。Boltzmann机中的神经元都是布尔型的，即只能取0,1两种状态，1表示激活，0表示抑制。
s = {0,1}ⁿ表示n个神经元的状态，w_ij表示神经元i与j之间的连接权，θ_i表示神经元i的阈值，则s所对应的能量定义为：
若网络中的神经元以任意不依赖于输入值的顺序进行更新，则网络最终将达到Boltzman分布（平衡态/平衡分布），此时状态向量s出现的概率仅由其能量与所有可能状态向量的能量确定：
标准Boltzmann机是一个全连接图，训练网络的复杂度很高，现实中常采用受限Boltzmann机(RBM)。仅保留隐层与显层的链接，如图：

5.6 深度学习

之后研读《深度学习》时进行详细讲解。

第6章 支持向量机(SVM)

西瓜书对于SVM的讲解有许多东西只是概念灌输，没有具体阐述，故本章内容将结合西瓜书，《吴恩达机器学习》与《机器学习——白板推导系列》等其他博客进行记录。
吴恩达机器学习视频连接：https://www.bilibili.com/video/BV164411b7dx?from=search&seid=6326447475270046491&spm_id_from=333.337.0.0
机器学习——白板推导系列视频链接：https://www.bilibili.com/video/BV1Hs411w7ci?from=search&seid=5268830131429087620&spm_id_from=333.337.0.0

6.1 间隔与支持向量

给定训练样本集D = {(x₁,y₁),…,(x_m,y₂)}，y_i = {-1,+1}，分类学习最基本的想法就是基于训练样本集D在样本空间中找到一个划分超平面，将不同类别的样本分开。如图：
可见有许多个超平面可以划分训练集，那么如何寻找最优的呢？
直观上看，应该找位于两类样本“正中间”的划分超平面，即上图中加粗的超平面。因为该划分超平面对于样本局部扰动的“容忍性”最好。换言之，这个划分超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。（鲁棒性：一个系统或组织抵御或克服不利条件的能力。）
其中，
划分超平面可通过如下线性方程来描述：
其中w为法向量，决定了超平面的方向；b为位移量，决定了超平面与原点之间的距离。显然划分超平面可以被法向量w和位移b确定，下面我们将其记为(w,b)。样本空间中任意点x到超平面(w,b)的距离可写为
假设超平面可以正确分类样本，即对于任何(x_i,y_i)∈D，若y_i = +1，则有w^Tx_i+b > 0；若y_i = -1,则有w^Tx_i+b < 0。令：
可见初始位置的超平面等式右侧就是0，改为+1与-1是放缩结果，在下方分类图中，只要正类位于左边，即该超平面所对应值大于0，就应当被分类为正类，而这种情况下，一定能通过放缩w和b使得距离超平面最近的样本点所对应的值恰好为+1与-1。
而距离最近的这几个样本点，被称为“支持向量”(support vector)，两个异类支持向量到超平面的距离之和为：
它被称为“间隔”(margin)。

欲找到具有“最大间隔”(maximum margin)的划分超平面，也就是要找到能满足上式的w和b使得γ最大，即：
等价于最小化||w||²，于是上式可以重写为：
这就是支持向量机(Support Vector Machine, SVM)的基本型。

6.2 对偶问题

希望求解上式来得到大间隔划分超平面所对应的模型，对其使用拉格朗日乘子法得到其“对偶问题”，具体来说，对上式每一个约束加拉格朗日乘子α_i ≥ 0，则该问题的拉格朗日函数可以写为：
令其对w和b的偏导为0可得：
将上方所得结论代入L中，就可以得到所求式的对偶问题：

解出α后， 就可以得到模型：
其中，对偶问题中的α_i是拉格朗日乘子，恰对应训练样本(x_i,y_i)。又原式有不等式约束，故上述过程要满足KKT(Karush-Kuhn-Tucker)条件，即要求：
Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。KKT条件将Lagrange乘数法(Lagrange multipliers)所处理涉及等式的约束优化问题推广至不等式。此处涉及许多数学推导问题，故不再赘述。具体KKT方程的讲解见：https://zhuanlan.zhihu.com/p/38163970

所以对于训练样本来说，总有α_i = 0或者y_if(x_i) = 1。若α_i = 0，则该样本不会对f(x)产生影响；若α_i>0，则必有y_if(x_i) = 1，所对应的样本点恰好在最大间隔边界上，是一个支持向量。这就显示出支持向量机的一个重要性质：训练完成后，大部分训练样本不需要保留，最终模型只与支持向量有关。

为了求解该对偶问题，提出了SMO算法。
SMO算法基本思路：先固定α_i之外的所有参数，然后求α_i上的极值。由于存在约束∑α_iy_i = 0，所以固定α_i以外的其他变量，α_i可由其他变量导出。于是，SMO每次选择两个变量α_i和α_j，这样，在参数初始化后，SMO不断执行以下步骤：

• 选取一对需要更新的变量α_i和α_j；
• 固定α_i和α_j以外的参数，求解以得更新后的α_i和α_j。

注意到只需选取的α_i和α_j中有一个不满足KKT条件，目标函数就会在迭代后缩小。直观来看，KKT条件违背的程度越大，则变量更新后可能导致的目标函数值减幅就越大。于是SMO先选取违背KKT条件程度最大的变量，第二个变量选取使目标函数值减小最快的变量，由于复杂度过高，因此SMO采用了一个启发式：
使选取的两变量所对应样本之间的间隔最大。因为这样的话，两样本差别会更大，所以对它们进行更新会给目标函数值带来更大的变化。
仅考虑两个变量时，约束可以重写为：
其中：
c是使∑α_iy_i = 0成立的常数。用新的约束消去∑α_iy_i = 0中的变量α_j，就可以得到一个关于α_i的单变量二次规划问题，仅有的约束是α_i≥0。
如何确定b？注意到对于任意支持向量(x_s,y_s)都有y_sf(x_s) = 1，即
现实中使用所有支持向量解的平均值来求解上式，以得到b:

6.3 核函数

在之前，都假设训练样本线性可分，即存在一个划分超平面能将训练样本正确分类。然而在现实任务中，原始样本空间不一定线性可分，即不一定存在一个能正确分两类样本的超平面，如图：
对这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。(与LDA相反）
例如在上图中，若将原始的二维空间映射到一个合适的三维空间，就能找到一个合适的划分超平面。幸运的是，如果原始
空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。

令φ(x)表示将x映射后的特征向量，于是，在特征空间中划分超平面的对应模型可以表示为：

有：
其对偶问题为：
求解上式涉及到计算φ(x_i)^Tφ(x_j)，这是样本x_i与x_j映射到特征空间之后的内积，直接计算很困难，故设计一个函数：
即x_i与x_j映射到特征空间之后的内积等于它们在原始样本空间中通过一个特殊函数来计算的结果，于是上式变为：

求解后得到：
这里引入的函数就是“核函数”(kernel function)。
上式显示出模型最优解科通训练样本的核函数展开，这一展开式又称为“支持向量模式”(support vector expansion)。
显然若已知合适映射的具体形式，就可以写出核函数，所以有以下定理：

上述定理表明，只要一个对称函数所对应的核矩阵半正定，它就能作为核函数使用。事实上，对于一个半正定核矩阵，总能找到一个与之对应的映射φ。即任何一个核函数都隐式的定义了一个称为“再生核希尔伯特空间”(RKHS)的特征空间。
核函数如果选择不佳，就意味着样本映射到了一个不合适的特征空间，很可能导致性能不佳。

下标列出几种常见的核函数：
此外还有如下函数组合也是核函数：

6.4 软间隔与正则化

在之前讨论中，都假定训练样本在样本空间或特征空间中线性可分，即存在一个超平面将不同类样本完全划分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分；退一步说，即使恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。
缓解该问题的一个方法是允许SVM在一些样本上出错，为此，引入“软间隔”(soft margin)的概念。如图：
前面所说的SVM形式是要求所有样本都划分正确，称为“硬间隔”(hard margin)，软间隔则是允许某些样本不满足约束：
在最大化间隔的同时，不满足约束的样本应尽可能少，于是优化目标写为：
C>0，为一常数，l_0/1是“0/1损失函数”。

显然C无穷大时，会迫使所有样本均满足上方约束，C取有限值时，允许出现一些不满足约束的样本。

有因为l_0/1非凸、非连续，所以会寻找一些函数来代替，被称为“替代损失”，替代损失函数一般有较好的数学性质，通常是凸的连续函数且是l_0/1的上界，常见替代损失函数如下：

若采用Hinge损失，则优化目标变成：
引入“松弛变量”(slack variables)ξ_i≥0，可将上式重写：

这就是常用的“软间隔支持向量机”。
类似的，运用拉格朗日乘子法可得：
α_i，μ_i是拉格朗日乘子。
求偏导并变换可得对偶问题：
与硬间隔的对偶问题的唯一差别：对偶变量α_i的约束不同。
软间隔的KKT条件：
关于正则化的相关问题我在其他博客上进行了阐述，本处不再多说，而且书上关于正则化也只用了极小极小的篇幅进行了一个简单的讲解。

6.5 支持向量回归

考虑回归问题。给定训练样本D，希望学得一个模型，使得f(x)与y尽可能接近，w和b是待确定的参数。
传统回归模型是直接基于f(x)与真实输出y的差别来计算损失，完全相同时损失才为0。而支持向量回归(Support Vector Regression, SVR)假设我们能容忍f(x)与y之间最多有ε的偏差，即仅当f(x)与y的差别绝对值大于ε时才计算损失，如图：
落入间隔带的被认为是预测正确的。

于是SVR问题形式化为：
C：正则化参数。l：如图所示的ε-不敏感损失函数：

引入松弛变量ξ_i和ξ^_i重写为：
间隔带两侧的松弛程度可有所不同。
再同样引入拉格朗日乘子并且满足KKT条件，可以得到SVR的最终解：

6.6 核方法：

回顾之前可以发现，给定训练样本后，若不考虑偏移项b，则无论SVM还是SVR，学得的模型总能表示成核函数的线性组合。我们有下面这个被称为“表示定理”的更一般的结论：
上式表示定理对损失函数没有性质，并且对正则化项Ω仅要求单调递增，甚至不要求其是凸函数，意味着对一般的损失函数和正则化项，优化问题的最优解都可表示为核函数的线性组合。

基于核函数的学习方法，统称为“核方法”。最常见的，是通过“核化”(引入核函数)来将线性学习器拓展为非线性学习器，从而得到“核线性判别分析”(Kernelized Linear Discriminant Analysis， KLDA)。
先假设可通过某种映射φ：X → F将样本映射到一个特征空间F，然后在F中进行LDA，以求得：
类似上式，KLDA的学习目标是：
S_b^φ和S_w^φ分别为训练样本在F中的类间散度矩阵和类内散度矩阵。
令X_i表示第i∈{0,1}类样本的集合，其样本数为m_i；总样本数m = m₀+m₁，第i类样本在特征空间F中的均值为：
且两个散度矩阵为：
通常很难知道映射的具体形式，所以使用核函数
来隐式表达这个映射和F，把J(w)作为上式的损失函数，再令Ω = 0，由表示定理，可知 h(x)写成：
所以有：
令K ∈ R^m×m为核函数所对应的核矩阵，1_i∈{1,0}^m×1为第i类样本的指示向量，即1_i的第j个分量为1当且仅当x_j∈ X_i，否则为0。
再令：
于是有：
然后用LDA的求解方法即可得到α，进而得到 h(x)。

第7章 贝叶斯分类器

7.1 贝叶斯决策论