学习记录
时间：7月26日至8月2日 学习内容概述：
1、学习周志华《机器学习》前6章的内容。
2、通读英文文献《Extreme Learning Machine》和《Outlier-robust extreme learning machine for regreion problem》
学习笔记
1机器学习第一章：绪论 人类具有学习的能力，我们可以通过对经验的利用，对新情况做出有效判断。机器学习就是对“学习算法”的研究，通过“学习算法”，我们可以让计算机通过经验数据，来生成一个“算法”的模型。而算法的作用是在我们输入一个新样本时，能够自动输出其对应的预测值，也就是预测新样本未知的“标记”。而算法适用于新样本的能力，就称为“泛化”能力。
学习可以进行分类。
1、若预测值为离散值，则此类学习为“分类”；若预测值为连续值，则此类学习为“回归”。
2、训练数据有标记信息，此类学习为“监督学习”，否则为“无监督学习”。
由于学习过程总是基于有限样本来进行训练的，那么就会出现多个假设都能与训练集都表现一致的情况，我们将这多个假设的集合称之为“版本空间”。为了得出确定的学习结果，学习算法在学习过程中就必须具有对某种类型假设的偏好，即“归纳偏好”。这个“偏好”在具体的学习算法中是如何体现的？
2机器学习第二章：模型评估与选择
我们把学习机实际预测输出与样本的真实输出之间的差异称为“误差”。其中学习器在训练集上的误差称为“训练误差”或“经验误差”，在新样本上的误差称为“泛化误差”。
训练误差为零的学习器，通常并不是一个好的学习器，因为其很可能出现“过拟合”的问题，即把训练样本本身的一些“特点”当做潜在样本的“性质”进行学习。反之，未能充分学习训练样本的“性质”，则会导致“欠拟合”的问题。
我们希望的是学习器的“泛化误差”尽可能小，在实际应用中，我们常以测试集上的“测试误差”作为“泛化误差”的近似。故对于数据集D，我们需要对其进行处理，从中产生出训练集S和测试集T。（原则：测试集应该尽可能与训练集互斥。）常用方法有留出法、k折交叉验证法、自助法（内含分层抽样和多次试验的问题）。
1、留出法就是简单划分。
2、交叉验证法，（p26页图2.2.）
将D划分为k个相同数量的子集，将k-1个子集用作训练集，1个子集用作测试集，然后不断更换作为测试集的子集，进行k次训练和测试。
3、自助法
假设D中包含m个样本，有放回地从D中采样m个样本放入D’中，将D’ 作为训练样本，根据概率会有接近36.8%的样本未被抽取，这一部分未被抽取的样本就作为测试集。自助法在数据集较小的时候作用很大。
但在学习算法确定后，我们还是要利用数据集D进行重新训练。
找好S和T后，我们就需要找到对测试进行评价的标准，就是“性能度量”。回归任务中最常用的性能度量就是“均方误差”。而分类任务（二分类为例）中，我们可以使用错误率、精度、查准率、查全率、ROC曲线、AUC曲线等来进行度量。
1、错误率、精度，略。
2、查准率P与查全率R。
TPTPPR
，P与R是一对矛盾（大体上负相关）的度量。
TPFPTPFNP-R曲线是以P为纵轴，R为横轴作的图。“平衡点BEP”是查全率=查准率
2PR时的取值，可以作为比较的标准。更常用的还有F1度量，F1，考虑
PR到侧重点不同还有F1的一般形式F。（见p32页）
当遇到需要综合考虑多个二分类混淆矩阵时，比如多分类任务的两两类别组合，则需要考虑“宏F1”和“微F1”的概念（见p32页）
3、ROC曲线，以及AUC值。 ROC 曲线纵轴是“真正例率”TPR，横轴是“假正例率”FPR。
TPFPTPRFPR，AUC为ROC曲线下各部分面积求和，反映TPFNTNFP的是样本预测的“排序质量”。
当然现实中也会出现不同的错误类型，造成不同代价的损失，所以我们可以为错误赋予“非均等代价”。在“非均等代价”下，我们希望最小化的不再是错误次数，而是“总体代价”。（见p36式2.23）
对单个学习器进行评价，我们假设测试样本是从泛化错误率为的样本总体中独立采样而成，求测试错误率为的概率，那么可得这种情况符合二项分布。那么反之，我们可以通过“二项检验”来对的假设进行检验。如p39页所示，可以根据测试错误率推测泛化错误率的大小和取该值的概率，每一个（显著度/置信度）对应一个临界值。这是单一测试错误率的性能测试方法。
当我们有多个测试错误率时，我们可以采用“t检验”法，进行检测。（明白用法，原理不明，需要重新学习概率论相应部分的内容）对于两个学习器学习性能是否相同，我们可以利用交叉检验t验证，也需要用到概率论相应内容。
3机器学习第三章：线性模型
线性模型试图学得一个通过属性的线性组合来预测的函数。“线性回归”试图学得一个线性模型以尽可能准确地预测实值输出标记。基于均方误差最小化来进行模型求解的方法称为“最小二乘法”。在线性回归中最小二乘法就是找到一条直线，使所有样本到直线上的欧氏距离最小。（p55中当样本由d个属性描述的情况下的矩阵求导运算不能读懂）
那么推广开来，我们可以得到“广义线性模型”，即考虑单调可微函数g(.)（称为联系函数），令yg1(wTxb)。前面谈到了如何用线性模型和处理回归问题，那么如何利用线性模型来处理分类问题呢？最理想的分类模型是阶跃函数，但是我们为了满足可微的条件，我们可以采用“对数几率函数”来替代阶跃函数。（关于p59页最优解的概率分析不明白；3.4中p61至p63的矩阵运算不理解）
在前面的学习中，我们大多讨论的都是“二分类”的学习器。面对现实中的多分类问题，我们可以要学习如何将多分类问题拆解成二分类问题。经典拆分策略有“一对一”、“一对其余”、“多对多”，OVO和OVR分类示意可以参考p64图3.4。MVM的正反类构造需要特殊设计，比如最常用的“纠错输出码”ECOC。编码、解码过程参考p65的图3.5，可能预测的编码不属于任何一类，即“出错”，但只需找到最接近的一类将其归入，这就是“纠错”的过程。
前面的分类都有一个共同的基本假设，即不同类别的训练样例相当。但是现实中“类别不平衡”的情况，即分类任务中不同类别的训练例数目差别很大的情况。这种情况下利用原始数据进行训练，可能让学习机将所有样本都分为数量上占绝对优势的一类来降低训练误差。特别若是训练集是真实样本无偏采样的假设不成立时，问题会更加突出。对于这种情况，我们可以采用“欠采样”、“过采样”、“阈值移动”。
4机器学习第四章：决策树
决策树是一种常见的机器学习方法。一般的一颗决策树包含一个根节点、若干个内部节点和若干个叶节点。叶节点对应于决策结果其他每个节点对应于一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集。根据p74图4.2可知，有三种情况会导致递归返。
1、节点包含的样本标记都相同。
2、节点内样本属性都相同。
3、节点内没有样本了。 在算法中，最关键的是要如何选择最优划分属性。我们希望决策树的分支节点包含的样本尽可能属于同一类标记，即节点“纯度”越来越高。
“信息熵ENT”（p75 式4.1）是度量样本集合纯度最常用的一种指标（ID3决策树）。选择划分属性时我们可以计算出假设划分每个属性a所对应的“信息增益Gain”（p75 式4.2），选择信息增益最大的属性来划分，因为这意味着“纯度提升”越大。
但是增益准则对选择可取数目较多的属性作为划分对象有所偏好，为了平衡我们引入属性的“固有值”概念以及“增益率”的概念，增益率准则对可取数目较少的属性有所偏好。故一种启发性选择是从信息增益高于平均水平的属性中选阵容增益率最高的。此外还有基尼指数（CART决策树）可用来度量纯度，选择划分属性。
那么为了缓解“过拟合”问题，在决策树学习中我们通常采用“剪枝”的手段。剪枝可分为“预剪枝”和“后剪枝”。
“预剪枝”方法采用测试集验证剪枝前后的精度，只有精度提高才允许划分。此法可以降低过拟合风险，还显著减少了决策树德训练时间开销和测试时间开销，但也带来了欠拟合的风险。
“后剪枝”方法首先需要训练一棵完整的决策树，然后再由叶至根地对决策树进行剪枝，这种方法通常比预剪枝保留更多的分支，一般情况下“后剪枝”欠拟合风险小，泛化性能优，但训练时间开销大得多。
前面讨论的都是离散的属性值，那么为了处理连续的属性值，我们应该采用“二分法”进行处理（C4.5决策树）。若有n个元素，则我们考虑采用n-1个中位点作为候选划分点，来计算信息增益，选择划分点。另外，若当前节点划分的属性为连续值，其后代仍可对此属性进行划分。
再来讨论如何对“有缺失属性值的训练样例”来进行划分。我们可以利用每个属性中未缺失属性的样本和其占该节点样本比例来计算GAIN选择划分属性（p87 式4.12）。在划分缺失该划分属性的样本时，以不同权值将该样本划入子节点，相当于将一个样本“分割”。
继续扩展，我们可以考虑，现在每个节点的划分我们都是基于单一属性值来进行的。但在学习类似p91图4.12 这样的分类任务时，会相当复杂，故我们可以考虑，将节点由“单变量决策”转为“多变量决策”，将“轴平行决策树”转化为“斜决策树”甚至更复杂的决策树。（未深入学习）
5机器学习第五章：神经网络
神经网络是具有适应性的简单单元组成的广泛并行互联的网络，他的组织能模拟生物神经系统对真实世界作出的交互反映。
“M-P神经元模型”，神经元接收到来自n个其他神经元传递过来的输入信号，这些输入信号通过带权值的连接进行传递，神经元接收到的总输入值将于神经元的“阈值”进行比较，然后通过“激活函数”处理以产生神经元的输出。将这样的神经元按一定的层次结构连接起来，就得到了神经网络。
“感知机”由两层神经元组成。输入层接受外界信号之后传递给输出层，输出层为M-P神经元。在yf(iwixi)这个简单的公式中，我们可以将θ视为一个固定输入为-1的“哑节点”所对应的连接权重wn1，这样阈值和权重的学习就可以统一为权重的学习（这在矩阵运算中尤其突出）。学习过程是通过错误的程度对权重进行调整。
感知学习机只能解决线性问题，那么要解决非线性可分问题，则必须考虑使用多层神经网络。常见的神经网络是形如p101图5.6 的层级结构，每层神经元与下一层神经元全互联，神经元之间不存在同层连接，也不存在跨层连接，这种神经网络结构通常称为“多层前馈神经网络MLFNs”。其输入层神经元仅是接受输入，不进行函数处理，隐层与输出层包含功能神经元。
神经网络的学习过程，就是根据训练数据来调整神经元之间的连接权；换言之，神经网络“学”到的东西，蕴藏在连接权与阈值中。
欲训练多层网络，简单感知机学习规则显然不够了，需要更强大的学习算法“误差逆传播算法BP”就是其中最杰出的代表。如p102的图5.7所示的网络，有（d+l+1）q+l个参数需确定。BP算法基于“梯度下降”策略以目标的负梯度方向参数进行调整。
对于每个训练样例，现将输入示例提供给输出层神经元，然后逐层将信号前传，直到产生输出层的结果；然后计算输出层的误差，然后将误差逆向传播至隐层神经元，最后根据隐误差对连接权和阈值进行调整，迭代过程循环进行。（具体迭代的数学计算过程还不是很明白）
“标准BP算法”每次仅针对一个训练样本更新连接权和阈值，而“累计误差逆传播”是每学习一轮才更新一遍参数，降低参数更新的频率。
已经证明只需一个包含足够多神经元的隐层，多层前馈网络就能以任意精度逼近任意复杂度的连续函数（如何设着隐层神经元个数仍是未决问题，实际中通常依靠“试错法”）。由于其强大的表示能力，BP神经网络经常遭遇“过拟合”问题。有两种策略可以用来缓解“过拟合”。
1、早停，思想与决策树的剪枝无二致。
2、正则化：在误差目标函数中增加一个用于描述网络复杂度的部分。例如连接权和阈值的平方和，使网络输出更加光滑，来缓解过拟合。如p107 式5.17。
其余常见的神经网络还有RBF网络、ART网络、SOM网络等。由于之前的聚类学习中接触无监督学习比较多，故只看了其中关于“自适应谐振理论网络ART”和“自组织映射网络SOM”的内容。竞争型学习是一种神经网络中常用的无监督学习策略，在使用该策略时，网络的输出神经元相互竞争，每一时刻仅有一个竞争获胜的神经元被激活，其他神经元被抑制。这种机制称为“胜者通吃”原则。
ART网络由比较层、识别层、识别阈值、和重置模块构成。比较层接收样本，将其传递给识别层，（识别层每个神经元对应一个模式类）计算输入向量与识别层的相似度，归入相似度最大且大于阈值的识别层神经元，同时更新连接权；若相似度都不大于阈值，则增设一个新的神经元，代表向量就为当前输入向量。可见，识别阈值作用很大，决定了分类的细致程度。
SOM网络，能将高维输入数据映射到低维空间（通常是二维），同时保持输入数据在高维空间的拓扑结构，将高维空间中相似的样本点映射到网络输出层中的临近神经元。SOM网络中的输出层神经元以矩阵方式排列在二维空间中，每个输出层神经元都拥有一个权向量，网络在接收输入向量后，，将会确定输出层获胜神经元，它决定了该输入向量在低维空间中的位置。
SOM的训练过程：在接受一个训练样本后，每个输出层神经元会计算该样本与自身携带的权向量之间的距离，距离最近的神经元成为竞争获胜者，然后最佳匹配单元及其邻近神经元的权向量将被调整，以使得这些权向量与当前输入样本的距离减小。此过程不断迭代，直至收敛。
前面介绍的神经网络大多是以单隐层为例。理论上来说，参数越多、复杂度越高的模型能完成更复杂的学习任务。随着云计算、大数据时代的到来，计算能力的大幅提高可以缓解训练的低效性，训练数据的大幅增加可降低过拟合风险，于是以“深度学习”为代表的复杂模型开始受到人们的关注。神经网络的提高容量的方法就是增加隐层的数目和层数。（关于深度学习只是提到一个概念，可以继续学习专门介绍深度学习的文章）
6 Extreme Learning Machine
首先，极限学习机ELM是针对BP学习速度缓慢提出的。BP学习速度缓慢主要是由两方面原因造成，一是“梯度下降”迭代策略本身的性质问题；二是每一次迭代的过程中，大量的参数（连接权、阈值）都需要参加迭代。ELM的主要优势在于，它可以随意设定隐藏层的连接权、阈值，忽略输出层偏置，然后通过数学分析，一次确定最优的输出层连接权。过程无需迭代，速度极快。
在引言中提到，文献《Universal approximation using incremental feedforward networks with arbitrary input weights 》中证明，SLFNs只要激励函数满足无限可微，理论上即使是随机生成的任意wi和bi其值固定不变，具有N个不同样本，包含N个隐含层神经元的SLFNs的训练误差依然可以无限接近零。作者以此作为随机产生wi和bi的依据。但这并不表示这随机产生的不会对学习结果造成影响，相反，这造成了学习结果有较大的随机性和不稳定性。
文献的第二部分紧接着对ELM中要使用的Moore-Penrose 矩阵广义求逆（看不懂）和最小二乘解进行了介绍，同时证明了通过Moore-Penrose 求逆方法对Ax=y中A矩阵求逆得出的矩阵G，就是Ax=y对应的最小二乘法的解之一，同时它还具有所有解矩阵中范数最小的性质。这个性质，使得wi值较小，可以一定程度上缓解“过拟合”的问题，使得算法有较好的泛化性能，上面的Ax=y矩阵运算，就对应了ELM学习中的HT。
介绍完ELM后，接着就是应用环节。文章应用了3个实例，以BP和SVM作为参照来证明了ELM的优越性。
第一个应用是利用加利福尼亚州的房子属性对房子的价格进行预测，一共进行了50轮学习来取得平均效果。毫无疑问ELM在速度上占尽优势，因为他不需要迭代只需要进行一次求逆，而BP每一轮都需要迭代8000次（训练样本数）。而且在效果上来说，ELM测试误差还更小些。
第二个应用采取了“糖尿病预测”的二分类问题，第三个采取了“森林覆盖类型预测”的多分类问题。结果都与第一个应用相似。（具体来说是怎么用ELM来产生离散的分类结果的？）
总体来说，例证环节的思路非常清晰。从“连续函数的回归问题”到“二分类问题”再到“多分类问题”，令人信服。
ELM的优越性总结为以下几点：
1、速度快
2、泛化性能好
3、因为没有迭代过程，不要求激励函数可微。
4、省去了一些复杂的参数比如学习率。
7 Outlier-robust extreme learning machine for regreion problems 这篇文献针对ELM对离群点（异常数据）敏感的问题提出了一种改进的“离群点鲁棒性极限学习机”(ORELM)。
文献指出，目前所有的ELM及其变体都是采用“二范数”的目标函数来对学习机进行训练的，但是“二范数”会放大离群点所带来的误差。因此此文献采用了“一范数”的目标函数来训练学习机，因为一范数对于异常数据的有更好的鲁棒性。另外为了得出目标函数的最优解，文献采用了增强的拉格朗日乘数法（ALM）来迭代求解。（还未理解此乘数法的具体数学过程）
文献第二部分，介绍了两种极限学习机的变体。分别是正则化极限学习机Regularized extreme learning machine (RELM)，和基于RELM提出的权重正则化极限学习机Weighted regularized extreme learning machine (WRELM)。RELM的提出是为了在ELM的基础上提高泛化性能，故在目标函数中添加了一个关于连接权矩阵二范数的正则化项，其余没有改变。WRELM则是在RELM运算结束后，将每个样本带入网络求出对应偏差，高偏差的样本将被赋予小权值，借此提高鲁棒性。然后重新利用RELM进行学习，得到最终结果。
文献指出了WRELM存在的问题，一方面很依赖RELM，另一方面当不存在离群点时，好的样本点的权值也会受到影响。
接着文献就提出了利用1范数作为目标函数的ORELM。这是一个带约束的凸优化问题，可以利用ALM方法进行迭代求解。文献提出，当数据存在异常时，ORELM有最好的鲁棒性，具有实用性。
应用环节也是采用了三个实例对方法进行验证。一是利用函数SinC对带有离群点的数据进行回归学习。对比了含有
10、20、40、80个离群点的训练集的回归效果，还分为固定偏离值的离群点和某区间内任意偏离值的离群点两种情况。（这里说的偏离都是标记值的偏离，没有讨论属性值的偏离） 二是利用乳腺癌良性恶性的二分类问题来进行学习。显然ORELM的精度更高，这一点在“受污染数据”比例上升后更加明显。
ORELM的优越性表现为：
1、计算速度较快，虽然比ELM慢很多，但比WRELM快。
2、面对含有异常数据的样本集时学习的鲁棒性比较强，比文献综述提及的其他ELM变体都要强。
