目录

• 关于想了好几年学机器学习，如今才翻开书的这件事
• • 第二章 模型评估与选择
  • • 模型评估方法（训练集S和测试集T划分）
    • • 1、留出法
      • 2、交叉验证法
      • 3、自助法
  • 第四章 决策树
  • • 1、重要概念
    • 2、剪枝策略
    • • 预剪枝
      • 后剪枝
      • 连续与缺失值处理
  • 第五章 神经网络
  • 第六章 支持向量机SVM
  • • 1、解决问题
    • 2、基本概念
  • 第七章 贝叶斯分类器
  • • 1、基础知识
    • 2、朴素贝叶斯
  • 第八章 集成学习
  • • 1、Boosting
    • 2、Bagging
    • 3、随机森林
    • 4、常用的结合策略
    • • （1）平均法
      • （2）投票法
      • （3）学习法
  • 第九章 聚类
  • • 1、基础知识
    • 2、原型聚类
    • • （1）K-Means
      • （2）学习向量量化
      • （3）高斯混合聚类
    • 3、密度聚类
    • • DBSCAN
    • 4、层次聚类
    • • AGNES
  • 第十章 降维与度量学习
  • • 1、kNN临近算法
    • 2、常用降维方法
    • • 主成分分析Principal Component Analysis, PCA)
      • • 协方差矩阵相关内容前导
        • 特征值的再思考
        • 主成分分析工作原理
      • 因子分析Factor Analysis)
      • 独立成分分析Independ Component Analysis, ICA)
  • 第十一章 特征选择与稀疏学习
  • • 1、过滤式选择
    • 2、包裹式选择
    • 3、嵌入式选择
    • 4、稀疏表示与字典学习
    • 5、压缩感知
  • 第十二章 计算学习理论
  • • 1、有限假设空间
    • 2、VC维
    • 3、Rademacher复杂度
  • 第十三章 半监督学习
  • • 1、生成式方法
    • 2、半监督SVM
    • 3、图半监督学习
    • 4、半监督聚类
  • 第十四章 概率图模型
  • • 1、隐马尔可夫模型
    • 2、马尔科夫随机场
    • 3、条件随机场
  • 第十五章 规则学习
  • • 最小一般泛化
  • 第十六章 强化学习
  • • 1、T步积累奖赏
    • 2、$\gamma$折扣积累奖赏
    • 3、蒙特卡罗强化学习

关于想了好几年学机器学习，如今才翻开书的这件事

更新学习中~

起因是在夏令营面试过程中，被老师问道，你学过机器学习吗？看过西瓜书吗？被伤了自尊心…但是在朋友的熏陶下对这方面也有部分自己的思考，但是一直没有系统地学习，原理其实是不是很懂的。

我： 神经网络的原理你能给我讲讲吗？连的每条线都什么意思呀？
朋友：它就是个黑盒！你会用就行了！
我：既然能设计出来！那肯定能解释！
朋友：·······

抱着它一定可以被我解释的心态，我翻开了西瓜书…

介绍一个有比较好的资源的GitHub地址：
https://github.com/apachecn/AiLearning/blob/master/README.md

当然西瓜书讲得非常详细，但是自己能力也有限，选取了一些自己认为可能比较重点的内容进行深读。

第二章 模型评估与选择

模型评估方法（训练集S和测试集T划分）

1、留出法

直接将数据集划分成两个互斥的集合，使用其中一个作为训练集S，另一个作为测试集T。在S上进行模型训练后，用T进行评估。
ATTENTION：
（1）S/T的划分要尽可能保证数据的一致性，避免因数据划分过程引入额外的偏差而对最终结果产生影响。例如：分类任务中至少保持样本类别的比例相似。
（2）即便给定训练/测试集样本比例后，仍有多种方式对数据集D进行分割。所以使用单词留出法的估计结果并不够稳定可靠，在使用留出法时，一般要采用若干次随机划分、重复进行试验评估后取平均值作为评估结果。
缺点：
（1）训练集S过于接近数据集D，此时测试集T较小，使得测试结果不够稳定。
（2）测试集T过于接近数据集D，此时训练集S较小，使得训练结果与预期模型差别较大。
常用解决方法：将2/3~4/5的样本用于训练。

2、交叉验证法

将数据集D划分成k个互斥大小相似的集合，尽可能保持数据分布的一致性，然后将前k-1个子集作为训练集S，余下的子集作为测试集T，这样就可以得到k组训练集/测试集，进行k次训练，并返回k次的均值。
k常用的取值是10、5、20。

比较特殊的情况是，若数据集D有m个样本，取k值为m，则每个测试集为1，此时不受随机样本划分影响，易得这种方法得出的样本与期望评估的D非常相似，往往比较准确。但是缺点也十分明显，当m足够大时，计算开销时无法忍受的。

3、自助法

自助法在某种程度上减少训练样本规模不同造成的影响，同时还能比较高效地进行实验估计。
以自助采样为基础，从有m个样本的数据集D，对其进行采样，随机挑选一个拷贝到D’，并放回，进行m次，得到一个大小为m的数据集，其中有一部分样本会重复多次，而另一部分不出现。其中始终不被采集到的概率经微积分取极限计算大概为0.368。此时D’作为训练集，D/D’作为测试集，测试集中有近1/3的数据未曾出现过。
这种方法适用于数据集较小，难以有效划分训练/测试集的情况。
但是改变了初始数据集分布，会引入估计误差。
在数据量足够时，方法1、2使用更多。

第四章 决策树

参考博客：https://blog.csdn.net/u012328159/article/details/70184415

线性模型的话我再琢磨琢磨，先把自己看的整理一下。我的最初的理解的话，决策树就像是一个if指导的分类，根据所有的if指向然后能得出一个结论。

名称	代谢方式	生活环境	类别
牵牛花	呼吸作用	陆地	人类
也就是如果“牵牛花”有这样的特征，按照上述决策树，它就是一个人类。

1、重要概念

决策树里面有几个贯穿始终的概念，所有的策略几乎都是为了改变这个几个衡量标准而设计的。我们希望决策树的分支节点尽可能包含样本属于同一个类别，也就是结点的纯度越来越高。（举个西瓜书的例子：现在有好瓜和坏瓜两类瓜，我们希望分支节点尽量都是好瓜或者坏瓜，这样的话分类能够更加简单，比如深绿色的都是好瓜，那么一个瓜是深绿色，就不需要进行其它判断，可以直接判定好瓜。）

信息熵：度量样本集合纯度最常用的一种指标，也就是信息的混乱程度。假定样本集合D中第k类样本所占比例为pkk=1,2,…,γ)p_kk=1,2,…,\gamma)pk​k=1,2,...,γ)，则D的信息熵定义为：

EntD)=−∑k=1∣γ∣pklog2pkEntD)=-\textstyle\sum_{k=1}^{|\gamma|}{p_klog_2p_k}EntD)=−∑k=1∣γ∣​pk​log2​pk​

$EntD)$的值越小，D的纯度越高。

信息增益：不同分支节点包含的样本数量不同，可以赋予分支节点不同的权重∣Dv∣/∣D∣|D^v|/|D|∣Dv∣/∣D∣，也就是样本数越多的分支节点影响越大，可以计算出属性a对样本集D进行划分所获得的“信息增益”。

GainD,a)=EntD)−∑v=1V∣Dv∣∣D∣EntD)GainD,a)=EntD)-\textstyle\sum_{v=1}^{V}{{|D^v|}\over {|D|}}EntD)GainD,a)=EntD)−∑v=1V​∣D∣∣Dv∣​EntD)

一般来说，信息增益越大，则意味着使用这个属性进行划分所得得“纯度提升”就越大。

增益率：用于C4.5算法，定义为: Gain_ratioD,a)=GainD,a)IVa)Gain\_ratioD,a)= {{GainD,a)} \over {IVa)}}Gain_ratioD,a)=IVa)GainD,a)​

其中：IVa)=−∑v=1V∣Dv∣∣D∣log2∣Dv∣∣D∣IVa)=-\textstyle\sum_{v=1}^{V}{{|D^v|}\over {|D|}}log_2{{|D^v|}\over {|D|}}IVa)=−∑v=1V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​

通常，a的取值越多，IV（a)的值越大。但进行选择是并不是直接选取增益率最高的，而是先选择信息增益高于平均水平的，然后再通过增益率进行选择。

为什么有增益率这个策略？
举个例子，将所有瓜按照编号属性划分，则此时分支结点是属性（假设17个样本），此时每个叶子节点都是一个样本，有唯一的分类，结点纯度达到最大，但这种划分显然不具有任何的泛化性质。

2、剪枝策略

剪枝过程可以帮助我们减少一些非必要的分类过程，减少开销，提升泛化能力。

预剪枝

在决策树生成过程中，对每个结点在划分前进行估计，若当前结点，不能提升泛化性能，则停止划分，并将此节点标记为叶结点。

使用书上的数据集：

根据信息增益准则和训练集，构造未剪枝决策树：

预剪枝过程：举个例子，如果脐部不划分，其中好瓜占多数，那么我们就这直接定义这个结点为好瓜，那么验证集合中{4，5，8}分类正确，也就是3/7分类正确。但是如果进行脐部划分，则验证集合中{4，5，8，11，12}均正确，也就似乎5/7划分正确。所以此时应当划分。以此类推向下的结点。

后剪枝

在决策树生成后，自底向上对非叶结点进行考察 ，若将结点替换为叶结点能够更高提升泛化性能，则进行替换。

不剪枝：

后剪枝过程：因为整个决策树的精度为42.9%。考察结点⑥，将其替换为好瓜，此时验证集合中的{7，15}均判断正确，也就是验证集精度提升可以提升至57.1%，进行剪枝。类推向上进行剪枝。

连续与缺失值处理

我们无法直接根据连续属性进行划分，此时使用连续属性离散化技术可以派上用场。最简单的是采用二分法对连续属性进行处理。

具体怎么处理呢，我觉得这个大哥写的非常好，我就不再赘述了，我也是看他的看懂的：https://blog.csdn.net/u012328159/article/details/79396893
西瓜书上面的例子，计算过程非常详细。

缺失值要解决两个问题：
（1）属性值缺失如何划分？
根据属性缺失和属性完整的比例判断属性优劣进行划分。

（2）给定划分属性，若样本在该属性上的值，如何划分？
其实大体上还是计算信息增益，但是此时只计算信息完整的信息增益，再乘上信息完整部分所占的比例作为信息增益。

具体参照，缺失值：https://blog.csdn.net/u012328159/article/details/79413610（我是懒蛋）

第五章 神经网络

这个太高深了，研究研究再写。

第六章 支持向量机SVM

1、解决问题

支持向量机最基本上是用来解决二分类问题，用一个N-1维的平面划分N维空间的样本。

2、基本概念

N-1维的平面划分N维空间怎么理解呢？
如图，所有的+和-有x1，x2两种属性，仅仅使用一条线就把他们划分开了，说明±是平面上的样本是二维的，红线是一维的。

间隔：指的是距离样本最近的点到超平面的距离总和。

γ=2∣∣w∣∣\gamma={2\over||w||}γ=∣∣w∣∣2​

在SVM中，我们需要使间隔最大化。为什么最大？

因为在分类过程中，我们需要忍受一定的扰动，数据不可能非常集中，而当我们选取的超平面能够忍受最大范围内的扰动，则是最优的。

比如上图，红色和虚线，紫线和蓝线拥有相同的距离，但是显然，在两条虚线之间没有样本点，而两条蓝线之间有样本点，蓝线要更加靠近才能不包含样本点，说明，紫线平面的抗扰能力低于红线，小间隔的抗扰能力低于大间隔，我们要使间隔最大化。

关于推导随后研究。

第七章 贝叶斯分类器

1、基础知识

贝叶斯公式的推导：
主要依托于乘法公式和全概率公式。

说到底，这里就是使用贝叶斯来评价分类错误时的损失期望，当然我们需要使得这个期望尽可能的小。

问题：
1、如何分类才能使期望变小？如何确定分类的条件？

极大似然估计：
一直在想，只知道损失期望有什么用呢？我们需要寻早使损失期望最小的参数呀，这个时候，极大似然估计就来了。

这个东西实在是，太妙了。

到底什么是极大似然估计呢？就是例如有：X1, X2,…,Xn个样本（比如一只猫的毛发长短、颜色、尾巴长短），分别使得X1=x1（长毛），X2=x2（橘色），…，Xn=xn（长尾），如果想要这种情况成立的概率最大，那么我们需要计算一系列参数θ1，θ2，…，θn来使这个概率最大。

根据学过的知识：

离散型：

连续型：

2、朴素贝叶斯

基本原理：

对于离散的数据：
对于每个属性，计算其条件概率（如：好瓜条件下青绿的概率等）。然后对某一个属性，计算其联合分布。

对于连续的数据：
对于连续的属性，选择合适的分布，计算其联合密度函数。

先验概率（假如两类，一类好一类坏，好（坏）的概率）：
P（c）=∣Dc∣∣D∣P（c）= {{|D_c|}\over|D|}P（c）=∣D∣∣Dc​∣​

条件概率：
P（xi∣c）=∣Dc,xi∣∣D∣P（x_i | c）= {{|D_c,xi|}\over|D|}P（xi​∣c）=∣D∣∣Dc​,xi∣​

当然，不排除样本存在某个属性值在训练集中没有出现过，此时条件概率为0，需要进行拉普拉斯修正。

先验概率：
P（c）=∣Dc∣+1∣D∣+NiNi是类别数，Dc原条件下样本数，D是原样本总量）P（c）= {{|D_c|+1}\over|D|+N_i} N_i是类别数，D_c原条件下样本数，D是原样本总量）P（c）=∣D∣+Ni​∣Dc​∣+1​Ni​是类别数，Dc​原条件下样本数，D是原样本总量）

比如：一共17个瓜，8个好瓜，9个坏瓜，其中好瓜概率：8/17；修正后概率：9/19。

条件概率：
P（xi∣c）=∣Dc,xi∣+1∣D∣+NiNi是类别数，Dc原条件下样本数，D是原样本总量）P（x_i | c）= {{|D_c,xi|+1}\over|D|+N_i} N_i是类别数，D_c原条件下样本数，D是原样本总量）P（xi​∣c）=∣D∣+Ni​∣Dc​,xi∣+1​Ni​是类别数，Dc​原条件下样本数，D是原样本总量）

先验概率是用来计算条件概率的。

朴素贝叶斯分类：

P样本=好瓜)=P（好瓜条件下 青绿（样本特征） 的概率）×P（好瓜条件下蜷曲概率）×···P（好瓜xxx的概率）
P样本=坏瓜)=P（坏瓜条件下 青绿（样本特征） 的概率）×P（坏瓜条件下蜷曲概率）×···P（坏瓜xxx的概率）

这个时候，我们就可以根据样本信息进行分类，选择概率大的作为样本分类。

第八章 集成学习

在我的理解里，集成学习就是把两个及以上方法结合在一起。例如：方法A对a样本敏感，方法B对b样本敏感，当AB方法进行结合，可能在单纯的a样本或者b样本上的效果没有对应方法好，但在ab混合样本上的效果可能会比B->a、A->b效果要好。

西瓜书在本章主要讲述了几种常见的集成方法和集成方法优劣的度量方法。

主要的集成分为两种，一种是同质的，一种是异质的。

同质：几种相同方法的学习器集成，例如决策树集成、神经网络集成等。
异质：不同方法的学习器的集成，例如决策树+神经网络等。

目前集成学习分为两大类，一类是有强依赖关系、必须串行生成，如Boosting，另一类是不存在强依赖关系、可同时生成的并行化方法，如Bagging和随机森林。

1、Boosting

Boosting是一族可以将弱学习器提升为强学习器的方法。

工作机制：从训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续收到更多关注；然后基于调整后的样本分布训练下一个基学习器，重复训练够T个基学习器。最终将这T个学习器加权结合。

Boosting 族算法最著名的代表是AdaBoost，常用的是基学习的线性组合来最小化指数损失函数，也就是最小化分类错误率。

引用：https://github.com/apachecn/AiLearning/blob/master/README.md

Boosting算法要求基学习器能对特定的数据分布进行学习，可以通过两种方法实施：
1、根据样本分布对每个训练样本重新赋予一个权值；
2、无法带权的样本采用“重采样法”，每轮学习中，对训练集重新进行采样，再使用重采用得到的样本基学习器进行训练。

每轮都需要检查基学习器是否满足条件，一旦不满足就需要抛弃当前基学习器，学习过程停止。

“重采样法”若出现不满足基础条件的基学习器可以将其抛弃，使用重采样得到的样本进行下次训练，可以持续到预设的T轮学习完成。而重赋值法无法做到。

2、Bagging

Bagging是最著名的并行式集成学习方法的代表。

工作机制：给定包含m个样本的数据集，我们先随机选取一个样本放入采样集，再把样本放回原数据集，使下次采样使该样本仍有可能被选中。m次随机采样操作后，得到m个样本集合。（基本上只有63.2%的数据进入到T个采样集）我们采样出T个m个样本的采样集，并针对每个采样集训练一个学习器，再将学习器进行结合。在预测输出进行结合时，通常采用简单投票法，对回归任务使用简单平均法。（未使用在采样集的36.8%的数据可以用作测试集）

3、随机森林

随机森林是Bagging的一个变体，是以决策树为基学习器构建的Bagging集成基础上，进一步在决策树的训练过程中引入了随机属性决策。

传统决策树在选择划分时，是在当前结点的属性集合中选择最优的属性，而随机森林引入了随机性，从某结点的属性集合中随机选择包含k个属性的子集，然后选取最优属性。

k=d，随机森林=传统决策树；
k=1，随机选择一个属性进行划分，
一般选择 k=log2dk=log_2dk=log2​d

4、常用的结合策略

（1）平均法

简单平均法、加权平均法。常用于数值型输出。
加权法中的权重一般是从训练数据中习得。个体性能差异较大时是用加权，较小时宜使用简单平均法。

（2）投票法

对于分类任务，常见的是投票法。分为绝对多数投票法、相对多数投票法和加权投票法。
绝对：投票超过1/2则为预测标记，否则不标记。
相对：预测为得票数最多得一个。

（3）学习法

先从初始数据集生成一个初级学习器，然后生成一个新的数据集用于训练次级学习器。防止只使用初级学习器生成数据集进行训练造成得过拟合，选择通过使用交叉验证或留一法，用训练初级学习器未使用的样本产生次级学习器的训练样本。

第九章 聚类

https://github.com/apachecn/AiLearning/blob/master/docs/ml/10.md

1、基础知识

聚类中最重要的问题是质心的寻找。

常见距离的度量：

闵可夫斯基距离：

p=2，闵可夫斯基距离就是欧氏距离；
dx,y)=x1−y1)2+x2−y2)2+⋯+xn−yn)2=∑i=1nxi−yi)2dx,y) ={\sqrt{ x_{1}-y_{1})^{2}+x_{2}-y_{2})^{2} + \cdots +x_{n}-y_{n})^{2} }} ={\sqrt{ \sum_{ {i=1} }^{n}x_{i}-y_{i})^{2} }} dx,y)=x1​−y1​)2+x2​−y2​)2+⋯+xn​−yn​)2​=i=1∑n​xi​−yi​)2​
p=1，就是曼哈顿距离（街区距离）。
闵可夫斯基距离仅用于有序距离（可度量）。

对于无序属性使用VDM。

簇: 所有数据的点集合，簇中的对象是相似的。
质心: 簇中所有点的中心（计算所有点的均值而来）。
SSE: Sum of Sqared Error（误差平方和）, 它被用来评估模型的好坏，SSE 值越小，表示越接近它们的质心. 聚类效果越好。由于对误差取了平方，因此更加注重那些远离中心的点（一般为边界点或离群点）。详情见kmeans的评价标准。

2、原型聚类

（1）K-Means

算法简述：
（1）随机选取k个样本作为质心；
（2）对于每个样本都计算到这k个质心的距离；
（3）将样本划分到这k个质心所在的簇；
（4）根据每个簇的样本，重新计算新的均值向量作为质心重复（2-4），直到划分结果相同。

优点:

• 属于无监督学习，无须准备训练集
• 原理简单，实现起来较为容易
• 结果可解释性较好

缺点:

• 需手动设置k值。 在算法开始预测之前，我们需要手动设置k值，即估计数据大概的类别个数，不合理的k值会使结果缺乏解释性
• 可能收敛到局部最小值, 在大规模数据集上收敛较慢
• 对于异常点、离群点敏感

（2）学习向量量化

算法简述：初始化原型向量，找到最近的应该归类簇的样本点，如果标记一样，则使得簇的质点向这个样本靠拢p′=qi+axj−pi∗)p'=q_i+ax_j-p_i*)p′=qi​+axj​−pi​∗)，否则使质点远离p′=qi−axj−pi∗)p'=q_i-ax_j-p_i*)p′=qi​−axj​−pi​∗)（迭代优化、更新原型向量）。

可以了解一下Voronoi剖分。

（3）高斯混合聚类

不常用，以后看。

3、密度聚类

DBSCAN

简述：
（1）选取一个种子和一个邻域表示核心样本，根据邻域划分，将所有落在邻域以及邻域样本邻域的样本均划入一个核心簇。
（2）在核心簇中未划分簇的样本中选择一个种子，根据邻域划分，将所有落在邻域以及邻域样本邻域的样本均划入一个簇，直到仅剩下噪声样本和。

4、层次聚类

AGNES

自底向上聚合策略的算法，将数据集中的所有样本都看作一个初始簇，然后在每一步中选择最近的簇进行合并，重复，达到预设的聚类簇为止。

第十章 降维与度量学习

所有的机器学习都面临一个严重的问题：高维情形下，数据样本稀疏、距离计算困难。被称作维数灾难，此时我们需要通过降维解决。

1、kNN临近算法

https://github.com/apachecn/AiLearning/blob/master/docs/ml/2.md

原理简述：
（1）假设一个带有标签的样本数据集，包含数据及其相应的标签分类；
（2）输入没有标签的数据后，（i）计算新数据与原样本数据集的距离；（ii）针对新数据与原数据的距离由近及远对原数据排序；（iii）取前k个样本数据对应的分类标签。
（3）求k个数据中出现次数最多的分类标签作为新数据的分类。

要点：

• k值的选择（到底取几个）
• 距离的度量（欧氏距离？曼哈顿距离？）
• 分类决策（投票法？平均法？）

kNN没有显式的训练过程。

2、常用降维方法

主成分分析Principal Component Analysis, PCA)

https://github.com/apachecn/AiLearning/blob/master/docs/ml/13.md

---

https://zhuanlan.zhihu.com/p/37609917

---

https://www.zhihu.com/question/21874816/answer/181864044

协方差矩阵相关内容前导

协方差：用来描述两个随机变量之间的相似程度。

σx,y)=1n−1∑i=1nxi−xˉ)yi−yˉ)\sigmax,y)=\frac{1}{n-1}\sum^n_{i=1}x_i-\bar{x})y_i-\bar{y})σx,y)=n−11​∑i=1n​xi​−xˉ)yi​−yˉ​)

协方差矩阵：给定d个随机变量，这些随机变量两两之间的随机变量构成协方差矩阵。

σxm,xk)=1n−1∑i=1nxmi−xmˉ)xki−xkˉ)\sigmax_m,x_k)=\frac{1}{n-1}\sum^n_{i=1}x_{mi}-\bar{x_m})x_{ki}-\bar{x_k})σxm​,xk​)=n−11​∑i=1n​xmi​−xm​ˉ​)xki​−xk​ˉ​)

即：

∑=[σx1,x1)⋯σx1,xd)⋮⋱⋮σxd,x1)⋯σxd,xd)]\sum=\begin{bmatrix}{\sigmax_1,x_1)}&\cdots&{\sigmax_1,x_d)}\\\vdots&\ddots&\vdots\\{\sigmax_d,x_1)}&\cdots&{\sigmax_d,x_d)}\end{bmatrix}∑=⎣⎢⎡​σx1​,x1​)⋮σxd​,x1​)​⋯⋱⋯​σx1​,xd​)⋮σxd​,xd​)​⎦⎥⎤​

其中对角线上为各个随机变量的方差。由公式计算易得，$\sum$是一个实对称矩阵。

定理：对于任何一个实对称矩阵A都会有一个正交矩阵X，使得X−1AX=XTAX=Λ，Λ=[λ1⋯0⋮⋱⋮0⋯λn]X^{-1}AX=X^TAX=\Lambda，\Lambda=\begin{bmatrix}{\lambda_1}&\cdots&0\\\vdots&\ddots&\vdots\\0&\cdots&{\lambda_n}\end{bmatrix}X−1AX=XTAX=Λ，Λ=⎣⎢⎡​λ1​⋮0​⋯⋱⋯​0⋮λn​​⎦⎥⎤​为A特征值所组成的对角阵。

正交矩阵：满足AAT=EAA^T=EAAT=E的n阶实矩阵为正交矩阵。

性质：

1. 组成正交矩阵的n个向量两两正交无论行列),且都是单位向量（标准正交向量）。
2. A−1=ATA^{-1}=A^TA−1=AT，且均为正交阵。

由以上可得到：必然有一个正交阵X能使$\sum$成为对角阵。

所以，有∑=XΛXT，Λ\sum=X\Lambda X^T，\Lambda∑=XΛXT，Λ为特征值对角阵成立。
同阶对角矩阵有性质：AB=BA，那么我们可以将$\Lambda$分解为Λ12Λ12\Lambda^{\frac{1}{2}}\Lambda^{\frac{1}{2}}Λ21​Λ21​，则有：

∑=XΛXT=（XΛ12）（Λ12XT）=（XΛ12）（XΛ12）T\sum=X\Lambda X^T=（X\Lambda^{\frac{1}{2}}）（\Lambda^{\frac{1}{2}} X^T）=（X\Lambda^{\frac{1}{2}}）（X\Lambda^{\frac{1}{2}}）^T∑=XΛXT=（XΛ21​）（Λ21​XT）=（XΛ21​）（XΛ21​）T

设矩阵 U=XΛ12U=X\Lambda^{\frac{1}{2}}U=XΛ21​，则有 ∑=UUT\sum=UU^T∑=UUT，所以可以说任何一个协方差矩阵都是线性变换的结果。

特征值的再思考

如果矩阵对某一个向量或某些向量只发生伸缩变换，不对这些向量产生旋转的效果，那么这些向量就称为这个矩阵的特征向量，伸缩的比例就是特征值。

---

也就是说矩阵是一种线性变换，矩阵乘上向量后，会使向量发生变化。但是对于这个矩阵可能有一部分向量经过这个线性变换矩阵与向量相乘)后方向没有变化，变化的只是模的大小。此时，这种向量称为特征向量，向量投影模大小的变化比例就是特征值。

---

特征值越大，说明这个矩阵在这个向量方向进行线性变换后的投影越大，也说明这个特征向量越典型，这个特征越应该在计算中被保留。

---

特征值分解很大程度上的目的是为了简化计算。
在得到某个矩阵的特征值和其对应的n个线性无关特征向量后，我们是可以将原矩阵计算出来的。但有时，为了达到某种目的，比如我们想要避免空间浪费，某些不太重要的信息不进行保存，我们就可以根据特征值，选取最重要的k（k<=n）个特征值组成Λ′\Lambda'Λ′，以及其对应的特征向量，进行计算仅保留k个特征值的矩阵。也就是，此时我们得到了仅保留重要特征的“原矩阵”。∑=XΛ′XT\sum=X\Lambda' X^T∑=XΛ′XT

截图来源于第三个知乎链接)

主成分分析工作原理

是最常用的一种降维方法。通俗地讲就是选择一个最主要的特征进行分析。

例如：看一个人成绩好坏，只看其数学成绩。

原理简述：
一共有
（1）找出第一个主成分（最大特征值）的方向，方差最大（最靠中心）的方向；
（2）找出第二个主成分（次大特征值）的方向，方差次大的方向，并且与第一个主成分的方向正交（实对称矩阵特征值对应的特征向量之间必然正交，所有特征值对应特征向量必然线性无关）；
（3）通过上述方式找出所有的主方向；
（4）通过数据集的协方差及特征值分析可以得到这些主成分的值（特征值）；
（5）得到协方差矩阵的特征值和特征向量，我们就可以保留最大的N个特征（特征向量），这些特征向量也能够显示出N个最重要的特征，从而将它转换到新的空间上。

正交：

• 为了使数据有效性损失最小
• 特征值的特征向量是正交的

因子分析Factor Analysis)

将多个实测变量转换为少数几个综合指标。它反映一种降维的思想，通过降维将相关性高的变量聚在一起,从而减少需要分析的变量的数量,而减少问题分析的复杂性。

例如: 考察一个人的整体情况，就直接组合3样成绩隐变量)，看平均成绩就行存在: 数学、语文、英语成绩)

应用的领域: 社会科学、金融和其他领域

在因子分析中，我们

• 假设观察数据的成分中有一些观察不到的隐变量latent variable)。
• 假设观察数据是这些隐变量和某些噪音的线性组合。
• 那么隐变量的数据可能比观察数据的数目少，也就说通过找到隐变量就可以实现数据的降维。

独立成分分析Independ Component Analysis, ICA)

ICA 认为观测信号是若干个独立信号的线性组合，ICA 要做的是一个解混过程。

例如: 我们去ktv唱歌，想辨别唱的是什么歌曲？ICA 是观察发现是原唱唱的一首歌【2个独立的声音（原唱／主唱）】。

• ICA 是假设数据是从 N 个数据源混合组成的，这一点和因子分析有些类似，这些数据源之间在统计上是相互独立的，而在 PCA 中只假设数据是不 相关（线性关系）的。

• 同因子分析一样，如果数据源的数目少于观察数据的数目，则可以实现降维过程。

第十一章 特征选择与稀疏学习

在上一章中我们遇到比较难以解决的问题：维数灾难。
维数是由我们选取的特征决定的，每一个特征都可以当作一个维度、如果我们从根源上，选择更少的特征，那么我们就能降低解决问题的难度。
那么，哪些特征是我们可以忽略不计算的呢？这套理论就是特征选择。
对于所有特征我们分为三类：有关特征、冗余特征、无关特征。
其中冗余特征指的是可有可无的特征，如果有了是有益的，如果没有是可以通过其它特征得到的部分特征。
这本书主要描述了三种特征选择方法分别是：过滤式、包裹式、嵌入式。

1、过滤式选择

先对数据集特征进行选择，然后再训练学习器，特征选择过程与学习过程无关。
这个方法中使用相关统计量衡量特征的重要性。

确定相关统计量：
（1）在同类样本中选择一个猜中邻近；
（2）在异类样本中选择一个猜错临近；
（3）若xi与猜中临近在属性j上的距离小于xi与猜错临近在属性j上的距离，则说明属性j是有益的，此时增大j的统计分量；否则，反之。

最终，得到各个属性的统计分量，分量越大，对应属性的分类能力就越强。

2、包裹式选择

包裹式选择是直接把最终将要使用的学习器的性能作为子集的评价标准。

例子：拉斯维加斯方法。（LVW）

包裹式选择的特征选择结果优于过滤式选择，但是计算开销远大于过滤式选择。在LVW方法中，设置了计算停止条件，在某些情况下，计算结束时不不能完全计算出其结果。

3、嵌入式选择

嵌入式选择是讲选择过程与学习过程融为一体，两者在同一个优化过程中完成，也就是学习器训练过程中，自动选择了特征。

我们在使用的模型中，引入LPL_PLP​范数，防止过拟合，并且计算稀疏解。假设我们需要计算的线性变换为w，正则化后w取得稀疏解说明初始的d个特征中，只有对应着w的非零分量特征才会出现在最终的模型中。

4、稀疏表示与字典学习

是为了降低计算的复杂度，将原本普通稠密的样本数据稀疏化。而稀疏化是依照特殊的映射将样本转换为稀疏格式，从而使样本计算复杂度降低。参照的映射称为字典，这个过程称为字典学习。

5、压缩感知

根据部分信息恢复全部信息。
限定等距性
矩阵补全技术
核范数

第十二章 计算学习理论

主要解决的是二分类问题。这章主要讲述了概率近似正确PAC的算法。介绍了：

1、有限假设空间

2、VC维

3、Rademacher复杂度

有点高深，没弄太明白，需要的时候再学。

第十三章 半监督学习

在半监督学习中，我们想要训练一个模型替我们打标签，从而降低人力成本。也就是不依赖外界交互，自动地利用未标记样本来提升学习性能。
纯半监督学习：依靠已标记和未标记地数据，处理待测数据。
直推学习：依靠已标记和未标记地数据，处理未标记数据。

1、生成式方法

假定一个生成式，作为生成模型。所以关键在于生成式的选择问题。
涉及到概率密度、EM算法、先验和后验概率等问题。

2、半监督SVM

算法简述：
1、先利用标记样本学一个SVM；
2、利用SVM对未标记数据进行标记，称为伪标记，并且设置这个伪标记的折中参数较小（也就是使它的决定作用减小）；
3、找出两个伪标记不同且最可能出错的样本，交换伪标记，重新求出划分超平面和松弛向量；
4、重复3，直到标记的折中参数和伪标记的折中参数相同。

3、图半监督学习

半监督学习在图上的应用，像是颜色的传播过程。已标记为染色部分，未标记为未染色。图和矩阵相对应，可以使用矩阵描述。
了解喇叭普拉斯矩阵。

4、半监督聚类

使用“必连”和“勿连”关系，迭代计算聚类。

第十四章 概率图模型

1、隐马尔可夫模型

2、马尔科夫随机场

3、条件随机场

没有很弄明白。

第十五章 规则学习

有点像离散中的命题。
也就是规定某种规则进行分类。当一个结果被不同规则覆盖时，进行冲突消解。比如：投票法、排序法、元规则法等。

在制定规则的时候有两种方法：
（1）自顶向下，从比较一般的规则开始，添加新的更加具体特殊的约束规则，容易产生泛化性好的规则；
（2）自底向上，从比较特殊的规则开始，寻找普遍规律，增强泛化能力，适用于训练样本较少的情况。

使用预、后剪枝，缓解过拟合的风险。
预剪枝：使用的规则集必须显著优于直接基于训练样例集的后验概率分布；
后剪枝（REP）：穷举所有剪枝方法组合，留下效果最好的一个（时间复杂度过高）。优化：在进行REP前，将数据集分为训练集和测试集，在训练集上生成一个规则 r’ , 将覆盖 r’ 的规则去除，重复这个过程。

最小一般泛化

感觉就是归纳总结，如果实在看不懂，建议好好看看离散数学。

第十六章 强化学习

强化学习：也就是执行某种操作后，能够反馈给系统一定奖赏。需要注意的是，单步操作并不一定能够能够达到奖励最大化，按照算法思维，这是动态规划的问题，但是在实际应用中动态规划的复杂度太高，所以仍然需要采用贪心的策略。也就是找到的可能不是最有解，而是相对优的解。

1、T步积累奖赏

也就是执行T步的最大奖赏。

在K-摇臂赌博机（按某种概率给某种奖赏）中：
我们在选择的过程中有两种方式：
（1)选取平均期望最大的：这个时候可能选择的不是最好的（存在概率很小但是奖赏很大的情况，不一定能摇出大的奖赏）；
（2）选取目前最优的：这个时候的选择可能不是最大奖赏（但是是目前期望奖赏最大的）。
这两种选取方式各有优劣，第一种在大量实验中，可能会在全局上体现出优势，但第二个相对目前是最优的方式，过于局部。所以可以使用参数e，平衡这两种方式。e*（1）+（1-e)*2)。当摇臂奖赏不确定性较大，我们可以偏向更全局的方式；当有一定的确定性，我们可以相对减小e，更有偏向性地选取奖赏大的摇臂。

2、$\gamma$折扣积累奖赏

3、蒙特卡罗强化学习

蒙特卡罗强化学习分为：同策略和异策略。也就是说，我们可以在强化过程策略改进中，改变策略；在评估策略时，使用原策略。