IT大数据学习分享：关于机器学习的知识点（1）

04 支持向量机

1. 支持向量机(SVM)

当前现代机器学习中最流行的算法之一，其在大小合理的数据集上经常提供比其他机器学习算法更好的分类性能。

2. 支持向量

在每个类中距离分类线最近的那些点则被称为支持向量。

如果有一个非线性可分数据集，那么就不能满足所有数据点的约束条件，解决方法是引入一些松弛变量η>=0。

3. 选择核

任何一个对称函数如果是正定的，都可以用来做核。这就是Mercer定理的结果，Mercer定理也指出一些核旋绕到一起的结果可能是另一个核。

4. 支持向量机算法

5. 分类

对于给定的测试数据z，使用支持向量对相关内核的数据进行分类，计算测试数据与支持向量的内积，进行分类，返回标记或值。

05 优化和搜索

1. 下山法

朝哪个方向移动才能下降尽可能快：

采用线性搜索，知道方向，那么久沿着他一直走，直到最小值，这仅是直线的搜索;

信赖域，通过二次型建立函数的局部模型并且找到这个局部模型的最小值。由于我们不知道防线，因此可以采用贪婪选择法并且在每个点都沿着下降最快的方向走，这就是所知的最速下降，它意味着pk=-▽f(xk)。最速下降基于函数中的泰勒展开，这是一种根据导数近似函数值的方法。

2. Lenenberg-Marquardt算法

3. 共轭梯度

二维空间中，如下图所示，一步沿x轴方向，另一部沿y方向，这样足以足以达到最小值。而在n维空间我们应该走n步以达到最小值，它尝试在线性情况下实现这个想法，但是我们通常感兴趣的非线性情况下，只需要多一点迭代就可以达到最小。

▲左边：如果方向之间是相互正交的并且步长是正确的，每一个维度只需要走一步，这里走了两步。右边：在椭圆上共轭的方向不是相互正交的。

具体算法：

4. 搜索的三种基本方法

穷举法：检查所有方法，保证找到全局最优

贪婪搜索：整个系统只找一条路，在每一步都找局部最优解。所以对于TSP,任意选择第-个城市，然后不断重复选择和当前所在城市最近并且没有访问过的城市，直到走完所有城市。它的计算量非常小，只有O(NlogN),但它并不保证能找到最优解，并且我们无法预测它找到的解决方案如何，有可能很糟糕。

爬山法：爬山法的基本想法是通过对当前解决方案的局部搜索，选择任一个选项来改善结果，进行局部搜索时做出的选择来自于一个移动集(moveset)。它描述了当前解决方案如何被改变从而用来产生新的解决方案。所以如果我们想象在2D欧几里得空间中移动，可能的移动就是东、南、西、北。

对于TSP，爬山法要先任意选一个解决方案， 然后调换其中一对城市的顺序，看看总的旅行距离是否减少。当交换的对数达到预先给定的数时，或找不到一个调换可以改善相对于预先给定的长度的结果时停止算法。

就像贪婪算法一样，我们无法预测结果将会怎样：有可能找到全局最优解，也有可能陷在第一个局部最大值上， 从而并不定能找到全局最优解，爬山法的核心循环仅仅是调换对城市， 并且仅当它使得距离变小时才保留调换。

5. 模拟退火算法

开始时选择一个任意的很高的温度T，之后我们将随机选择状态并且改变它们的值，监视系统变化前后的能量。如果能量变低了，系统就会喜欢这种解决方法，所以我们接受这个变化。目前为止，这和梯度下降法很像。

然而，如果能量不变低，我们仍然考虑是否接受这个解决方法，并且接受的概率是exp((Ebefore- Eafter)/T)。这叫作波尔兹曼分布(Boltzmann distribution)。注意到Ebefore Eafter 是负的，所以我们定义的概率是合理的。偶尔接受这个不好的状态是因为我们可能找到的是局部最小，并且通过接受这个能量更多的状态，我们可以逃离出这个区域。

在重复上述方法几次后，我们采用一个退火时间表以便降低温度并且使得该方法能延续下去直到温度达到0。由于温度变低，所以接受任一个特殊的较高的能量状态的机会就会变少。最常用的退火时间表是T(l+1)=cT(t)，这里0

6. 四种算法TSP结果比较

第一行为最好的解决方案和距离，第二行为运行时间，城市为10个。

06 进化学习

1. 遗传算法(GA)

模拟进化是如何搜索的，通过改变基因来改变个体的适应度。

GA使用字符串(类似染色体的作用)，字符串中的每个元素都是从某些字母表中选择，字母表中的值通常是二进制的相当于等位基因，对于解决方法，将被变为一个字符串，然后我们随机生产字符串作为初始种群。

评价适应度可以被看成一个预测，它作用于一个字符串并且返回一个值，它是遗传算法中唯一因具体问题不同而不同的部分。最好的字符串有最高的适应值，当解决方案不好时，适应度也随之下降，GA工作于由种群组成的字符串，然后评价每个字符串的适应度，并进行培养。

产生后代的常用3种方法：

联赛选择：反复从种群中挑选四个字符串，替换并将最适合的两个字符串放人交配池中。

截断选择：仅按比例f挑出适应度最好的一-部分并且忽略其他的。比如，f= 0.5经常被使用，所以前50%的字符串被放入交配池，并且被等可能地选择。这很显然是一个非常简单的实施方法，但是它限制了算法探索的数量，使得GA偏向于进化。

适应度比例选择：最好的方法是按概率选择字符串，每个字符串被选择的概率与它们的适应度成比例。通常采用的函数是(对于字符串a)：

这里F^α是适应度，如果适应度不是正值，则F需要在整个过程中被exp⁡(sF)替换，这里s是选择强度(selection strength)参数，并且你会意识到这个等式作为第4章的softmax激活)：

2. 遗传算子产生

最常用时实现方法是在字符串中随机找一个点，在这个点之前的部分用字符串1的，而在交叉点之后，用字符串2的剩下部分。我们实际上产生了两个后代，第2个是由字符串2的第一部分和字符串1的第二部分组成的。这个方式称为单点交叉，显然，它的扩展是多点交叉。

最极端的情形是均匀交叉，它的字符串中的每一个元素都随机地选自与他的父母，下图展示了三中类型的交叉法：

▲交叉算子的不同形式。(a)单点交叉。随机选择字符串中的一个位置，然后用字符串1的第一部分和字符串2的第二部分组成后代。(b)多点交叉。选择多个点，后代的生成方式和前面一样。(c)均匀交叉。每个元素都随机的选自于它的父母。

对当前最好的字符串实现进化通过编译算子实现，字符串中每个元素的值以概率p(通常很小)改变。

3. 基本遗传算法

4. 使用遗传算法进行图着色

把方案编码成字符串，选择合适的适应度函数，选择合适的遗传算子。

5. 与采样结合的进化学习

最基础的版本是我们熟知的基于种群的增长学习算法(PBIL).该算法非常简单，像基本的GA一样，它采用一个二进制字母表，但不保留种群，而是利用一个概率向来给出每一个元素是0或1的概率。

起初，向量的每一个值都是0.5，所以每一个元素有相等的机会变成0或1，之后通过从分布指定的向量中取样来构建群体,并计算群体中每个成员的适合度。

我们使用这个种群中的一个子集(通常只有前两个适应度最高的向量)和一个学习速率p来更新概率向量，学习速率通常被设置为0.005(这里best和second代表种群中最好的和第二好的成员):p= pX(1 - η)+ η(best十second)/2。

之后丢弃这些种群，并且利用更新的概率向量重新取样来产生新的种群，算法的核心就是简单地利用适应度最高的两个字符串和更多的向量来寻找新的字符串。

07 强化学习

强化学习是状态(state)或情形(situation)与动作(action)之间的映射，目的是最大化一些数值形式的奖赏(reward)。也就是说，算法知道当前的输人(状态)，以及它可能做的一些事(动作)，目的是最大化奖赏。进行学习的智能体和环境之间有着明显的区别，环境是智能体完成动作的地方，也是产生状态和奖赏的地方。

1. 马尔可夫决策过程

马尔可夫性：当前的状态对于计算奖赏提供了足够的信息而不需要以前的状态信息，一个具有马尔可夫性的强化学习成为马尔可夫决策过程。它意味着基于以前的经历，我们只需要知道当前的状态和动作就可以计算下一步奖赏的近似，以及下一步的状态。

2. 值

强化学习尝试决定选择哪一个动作来最大化未来的期望奖赏，这个期望奖赏就是值，可以考虑当前状态，对所有采取的动作进行平均，让策略来自己解决这个问题，即状态值函数，或者考虑当前状态和可能采取的动作即动作值函数。

3. O-learning算法

4. Sarsa算法

两种算法的相同

都是bootstrap方法，因为他们都是从对正确答案很少的估计开始，并且在算法进行过程中不断迭代。

不同

两个算法一开始都没有环境的任何信息，因此会利用ε-greedy策略随机探索。然而，随着时间的推移，两个算法所产生的决策出现了很大的不同。

产生不同的主要原因是Q-learning总是尝试跟着最优的路径，也就是最短的路，这使它离悬崖很近。并且，ε-greedy也意味着有时将会不可避免地翻倒。通过对比的方式，sarsa 算法将会收敛到一个非常安全的路线，它远离悬崖，即使走的路线很长。

sarsa 算法产生了一个非常安全的路线，因为在它的Q的估计中包含了关于动作选择的信息，而Q-learning生成了一条冒险但更短的路线。哪种路线更好由你决定，并且依赖于跌落悬崖的后果有多么严重。

08 树的学习

决策树的主要思想是从树根开始，把分类任务按顺序分类成一个选择，一步步进行到叶子节点最终得到分类的结果，树结构可以表示成if-then规则的集合，适合应用于规则归纳系统。

1. ID3

在决策树下一次分类是，对于每一个特征，通过计算真个训练集的熵减少来选择特征，这成为信息增益，描述为整个集合的熵减去每一个特定特征被选择后的熵减去每一个特定特征被选中后的熵。

具体算法

决策树复杂度

假设树是近似平衡的，那么每个节点的成本包括搜索d个可能的特征(尽管每个层级减少1，但这不会影响O(·)符号的复杂性)，然后计算每个分裂的数据集的信息赠与，这需要花费O(dnlogn)，其中n为该节点上数据及的大小，对于根节点，n=N，并且如果树是平衡的，则在树的每个阶段将n除于2。在树种的大约logN层级上对此求和，得到计算成本O(dN^2logN)。

09 委员会决策：集成学习

下图为集成学习的基本思想，给定一个相对简单的二类分类问题和一些学习器，一个学习器的椭圆覆盖数据的一个子集，组合多个椭圆给出相当复杂的决策边界。

▲通过组合许多简单的分类器(这里简单地将椭圆决策边界放在数据上)，决策边界可以变得更加复杂，使得正例与圆圈难以分离。

1. AdaBoost(自适应提升)

每次迭代中，一个新的分类器在训练集上训练，而训集中的每-个数据点在每一步迭代时都会调整权重，改变权重的根据是数据点被之前的分类器成功分类的难度。一开始， 这些权重都被初始化为1/N,其中N是训练集中点的个数然后，每次迭代时，用所有被错分的点的权重之和作为误差函数ε。

对于错误分类的点，其权重更新乘子为a=(1-ε)/ ε。对于正确分类的点，其权重不变。接着在整个数层集上做归一化(这是降低被正确分类的数据点的重要性的有效方法)。在设定的迭代次数结束之后训练终止，或者当所有的数据点都被正确分类后训练终止，或者一个点的权重大于最大可用权重的一半时训练也终止。

具体算法：

2. 随机森林

如果一棵树是好的，那么许多树木应该更好，只要他们有足够的变化。

3. 基本的随机森林训练算法

4. 专家混合算法

10 无监督学习

无监督学习在不知道数据点属于这一类而那些数据点属于另一类的情况下找到数据中相似输入的簇。

1. k-means算法

2. 在线k-Means算法

3. 自组织特征映射算法