本帖最后由 小猪猪de孤独 于 2015-12-23 23:17 编辑
—————————————————————————— 寒假补充点ML的知识，把自己的一点理解写下来吧，参考书籍主要有李航的《统计学习方法》和张玲、张燕平（以前教我体系结构的老师）的《机器学习理论与算法》。 先来看一些统计学习或者统计机器学习的理论吧，如果说数据挖掘和ML有什么区别的话，那就是术与道的区别。ML更理论，而DM更注意应用。 1、什么是学习？ 引用希尔伯特对学习的定义：“如果一个系统能够通过执行某个过程改进它的性能，这个过程就是学习。”机器学习的目的就是使系统从不断获取的知识中提升自己的性能。 2、数据 统计学习的对象是数据，数据是知识的来源，因此，数据的获取和处理是相当重要的，不过在讨论理论时我们假设数据已经获取好了。在统计学习中用变量或变量组来表示数据，根据其组成元素类型可细分为离散型和连续型两类。 统计学习理论中有两个关于数据的重要假设，分别为： a.同类数据具有一定的统计规律，可以用概率分布来描述这种规律。 b.作为学习对象的训练数据集合中的数据是独立同分布的。 来分析一下吧，首先数据要符合一定的统计规律，如果数据没有规律那还学习干嘛，不是做无用功吗？ 第二条假设数据独立同分布，很多统计学的公式都是建立在数据独立同分布之上的，因此，进行统计分析必须假设数据是独立同分布的，这样分析起来就会很方便，省去很多复杂的东西。注意数据可能不是完全独立同分布的，但是对于大量数据，这种假设是广泛适用的。何乐而不为呢？ 3、输入输出相关概念 学习的输入和输出的所有可能取值的集合分别叫做输入空间和输出空间，一般而言，输出空间小于输入空间。如果具体到输入实例，可以将输入空间看成特征空间，其中的每一维为一个特征。 4、学习的三要素。 统计学习三要素包括： 模型：即假设空间，或者说是一组函数的集合，这组集合中的函数都能将输入空间映射到输出空间，但是映射的准确性却大不相同，统计学习的目标在于从假设空间中选取最优模型，该模型能尽可能准确的将输入空间映射到输出空间； 策略：即寻找最优模型的准则，怎么评价假设空间中函数的优劣，在这个准则下找到满足条件的最优模型，这个准则和损失函数、风险函数紧密相关； 算法：按照某个评价准则（如损失函数输出最小）选取最优模型的方法。 在监督学习中，继续细分模型为条件概率分布和决策函数。这样模型的假设空间即为所有可能的条件概率分布或决策函数。条件概率模型的输出为实例属于那个类别的概率，取概率最大的那个类别作为最终输出，而另一种情况则直接使用决策函数的值作为输出。在条件概率模型中，输入和输出都是随机变量，而决策函数模型中，输入输出都是变量。 判定模型好坏的准则很重要，它直接决定了我们对最优模型有哪些要求。传统的统计学习追求经验风险最小化ERM，给模型的求解带来了很多问题，现在的统计学习则追求结构风险最小化SRM，不论是前者还是后者，都是追求期望风险最小化，只不过前者是用经验风险来逼近期望风险，后者用结构风险（经验风险+置信风险）逼近期望风险。 下面来详细说明这些概念，包括损失函数，风险函数、VC维理论和生长函数 —————————————————————————————————— 机器学习笔记（二）基础知识2 1、损失函数 最简单的理解就是，给定一个实例，训练的模型对它的预测结果错了，就要受到惩罚， 因此需要定义一个量度量预测错误的程度，而损失函数就是用来衡量错误的程度。常见的损失函数有如下几类（用
来表示损失函数）： 假设输入是X，输出是f(X)，真实值是Y。 （1 ）0-1 损失函数（0-1 loss function ）
（2 ）平方损失函数（quadratic loss function ）
（3 ）绝对损失函数（absolute loss function ）
（4 ）对数损失函数（logarithmic loss function ）
2.传统的经验风险最小化 很容易看出来，损失函数越小，模型就越好，接下来用期望风险来描述模型在整个数据集上的损失，假设我们已经得到了数据的概率测度P(X,Y), 那么就可以计算损失函数的期望即期望风险：
需要说明的是，这里假设数据集包含了所有可能的数据，即P(x，y)是已知的，显然这是不可能的，我们只能尽量多的获取数据集中的数据，但是不可能获得所有输入空间中的数据。有了期望风险学习的目标就确定了，即找到使期望风险最小的模型，但是就像前面说明的，全部数据的分布是未知的，那么求解期望风险的问题就是一个病态问题。那该怎么办呢，虽然我么不知道数据集的概率测度，但是我们拥有给定的一定的独立同分布的样本，因此，我们可以用模型f(x)在这个给定的样本集上的平均损失最小化来代替无法求得得期望风险最小化。 注意上面我们再一次提到了独立同分布，这样我们就不用考虑数据集的概率测度了，计算瞬间变简单了，当然，这肯定造成了一定的计算损失，但是结果还是可信的，可取的。 假设给定的数据集是：
则经验风险或经验损失函数为：
使用经验风险泛函最小的函数来逼近期望风险泛函最小的函数，这一原则成为经验风险最小化归纳原则(ERM原则)。 根据大数定律，当样本数趋于无穷大时，经验风险趋于期望风险。但是，在实际应用中，训练样本的个数是有限的，甚至还会很少，所以使用经验风险逼近期望风险的效果就不好了。 这里还涉及到一个学习理论的关键定理，该定理指出了ERM原则一致性的条件是必要的并且充分的取决于函数集中最坏的函数。这一块只要知道它指出了经验风险和期望风险的误差是有界的就行。 上面说到，对于小样本问题，经验风险效果并不理想，因为经验风险最小化容易带来过拟合现象。过拟合现象其实就是模型的选择太在意训练误差了，反而导致预测误差随着训练误差减小而增大，造成训练结果不理想。这里不再多说，可以到网上找一个多项式拟合的例子形象的理解。我也转了一篇关于过拟合的文章，解决过拟合问题是加入惩罚项或者增加数据。 3.结构风险最小化 为了解决经验风险最小化逼近引发的一系列问题，vpnik等几位大牛发展了现代的统计学习理论，提出了结构风险最小化，更加适合解决小样本问题，并且提出了寻找结构风险最小化的方法，这一套理论发展出了有名的分类器：基于VC维理论和结构风险最小化的支持向量机SVM，它能够更快更迅速的解决小样本问题，在大样本集上也有一些基于稀疏矩阵的改进方法，成为2000年来的研究热点之一。 首先要引入函数的VC维概念： 函数集Q(f)的VC维是指能够被集合中的函数以所有可能的2^h种方式分成两类的样本的最大数目h.另一个说法是：假如存在一个有h个样本的样本集能够被函数集中的函数按照所有可能的2^h方式分成两类，则称该函数集能把样本为h的样本集打散。VC维就是h的最大值，对于h+1，函数集就无法打乱了。对于线性函数，其VC维很简单，就是函数维数+1,。 定义N(f)代表函数集Q(f)中的函数能够把给定的样本分成多少种类，称H(f)=ln(N(f))为随机熵，描述了函数集在给定数据上的多样性，引入生长函数G(n)=ln(N(f))，则生长函数与VC维的关系为： G(h)=hln2 G(h+1)小于(h+1)ln2 即生长函数或者是线性的，或者以对数为上界。如果函数集的生长函数是线性的，则函数集的VC维是无穷大的，因为函数集能够打散的数据集数目可以无限大，反之，如果生长函数是以参数h的对数函数为界，则函数集的VC维就是h。 VC衡量了一个函数集的复杂程度，VC维越大，函数集越复杂，虽然函数打散的样本数增加了，但是计算函数的复杂度却增加了，反而不能得到好的结果(引起过拟合)，VC维越小，函数集越简单，求解速度快而且方便。支持向量机只关注对偶公示中参数不为0的支持向量的那些样本，因此VC维很小。奥卡姆剃刀原理：在所有可能选择的模型中，能够很好地解释已知数据并且十分简单的才是最好的模型。 引入VC维之后我们再去看看上面红色的部分，即经验风险和期望风险的误差是依概率有界的，通过一系列复杂的公示推导我们得到如下公式：
n 为样本数，h 为VC 维 不等式右边第一项为经验风险，第二项为置信风险，是一个减函数，整个公示反映了经验风险和真实误差的差距上界，表征了根据经验风险最小化原则得到的模型的泛化能力。称为泛化误差上界。 上述公示表明：当样本数较大时，n/h很大，置信范围就会很小，经验风险最小化接近实际最优解，而当n/h比较小时，置信范围就会很大，经验风险最小化泛化能力就差。 结构风险=经验风险+置信风险，这部分会在SVM那一块仔细介绍。 在李航的书中讲到了模型选择两种典型方法，这里简单介绍一下： a.正则化 正则化是结构风险最小化策略的实现，在经验风险上加一个正则化项，该项与模型复杂度相关或者模型VC维相关，复杂度越大，正则化值就越大。常用的正则化项有模型参数的范数等。 b.交叉验证 交叉验证的思想就是将训练数据集随机划分成若干个块，这些块称为训练集和验证集，训练集用于训练模型，验证集用于评判训练明星的好坏，在每一块上找到风险最小化函数，然后综合再把结果综合起来考虑。常见的交叉验证包括1/3和2/3划分，k-则交叉验证以及留一法。第一种方法取数据集的2/3进行训练，剩余1/3进行验证，第二种方法取k-1份训练，剩下一份验证，将可能的K种组合都做一次，因此共需要训练k次模型，留一法是k则交叉验证的极端情况，即K=N。 最后注意一下生成模型和判别模型的区别 生成模型更像是找到数据的组织形式，而判别模型是用实现固定好的模型模拟数据。 生成模型由数据学习到联合分布，然后求解条件概率分布，因此学习速度快且能更快的收敛到真实模型。 判别模型直接学习决策函数或条件概率，侧重于预测，因此准确率高。 —————————————————————————————————— 机器学习笔记（三）k近邻算法和感知器模型 1.kNN算法 k近邻算法的想法很简单，类似于多数表决，关键点是参与多数表决的人是离你最近的k个人。 给定一个实例，首先从训练集中找到离这个实例最近的k个实例，然后根据这k个实例中哪个标签出现次数最多决定该实例的标签。需要注意的点是： a. 距离的度量 b. k值得选取 c. 存储和速度 度量距离有很多，这里介绍三种，即1 范数，二范数和无穷大范数。假设两个实例的特征向量为：
1 范数：
2 范数：
无穷大范数：
当然还有好多其他的距离度量方式，比如向量夹角等。关于范数的定义可以参见线性代数的书，会有详细的介绍。我觉得那个范数一致性倒是蛮重要的。 使用的距离不同，k近邻的结果也会不同的，即“由不同的距离度量所确定的最邻近点是不同的。” k值得选择非常重要，不合适的k值结果可能会很不理想。 如果选择的比较小的话，相当于用较小邻域中的训练实例进行预测，学习的近似误差会减少，只有与输入实例较近的训练实例才会对预测结果起作用，缺点是学习的估计误差会增大，易受噪声影响，极端情况是k=1； 如果k值选取的比较大，相当于用较大邻域中德训练实例进行预测，学习的估计误差会减少，但是近似误差会增大，而且与输入实例较远的训练实例也会对预测起作用，是预测结果错误，k值的增大意味着整体模型变得简单。因为划分的区域少了，更容易进行预测结果。极端情况是k=n. 如果每次都计算每个训练实例和输入实例的距离显然是非常耗时间的，对于样本数量比较大的训练集这是不可行的。一般构造kd树(属于二叉树)来实现k近邻算法。提升速度，减少存储量。 kd树的构造是一个递归过程，其思想是对k维空间（假设数据集在这个k维空间中）进行划分，每次划分在一个维度中进行，取该维所有实例中位数为切分点，切分由通过切分点并与该维坐标轴垂直的超平面实现。 kd树的每个节点都是一个实例，相邻的节点，父节点与子节点之间是近邻的。给定一个目标点，搜索其最近邻，首先找到包含目标点的叶节点，然后从该叶节点出发，依次回退到父节点，不断查找与目标节点最邻近的节点，当确定不可能存在更近的节点时终止。这样搜索就被限制在空间的局部区域上，提高了搜索近邻的效率。 kd树更加详尽的中文介绍参见博文： http://www.cnblogs.com/eyeszjwang/articles/2429382.html 2.感知器模型 感知器是经典的线性分类模型，是神经网络和支持向量机的基础。 下面从统计学习三要素来分析感知器模型： 1.模型 感知器的模型是线性函数：
file://localhost/Users/ml/Library/Caches/TemporaryItems/msoclip/0/clip_image032.png 其中w是权值向量，b是偏置bias，线性方程wx+b=0是特征空间中的超平面，该超平面将特征空间划分成两个部分。 继续介绍之前先说明数据集的线性可分性，如果存在某个超平面S将数据集的正实例点和负实例点完全正确的划分到超平面两侧，则称数据集是线性可分的，否则数据集线性不可分。线性可分时，满足划分的超平面一般不只一个，因此有的算法会寻找最优超平面，比如SVM。线性不可分时，一般引入核函数，将输入空间投影到更高维的线性可分的特征空间中，这个容易理解，世界上没有两种完全相同的东西，我们总能通过各种标签来区分两个事物，除了引入核函数外，SVM还使用了软间隔，使算法可以容忍造成线性不可分的点，提高算法灵活度。 2. 感知器的损失函数是每个实例点的函数间隔（注意和集合间隔的区别）之和：
其中，M为误分类点的集合，该函数就是感知器的经验风险函数。 3. 利用梯度下降求解经验风险函数最小化，对w 和b 求偏导可得损失函数的梯度：
因此，在学习时，对于一个误分类点，通过梯度对权值向量和偏置进行更新，更新时一般有一个系数称为学习率，它决定了按梯度下降的步长，学习率可以为实现指定的定值，也可以为一个和学习次数相关的减函数。 当训练集中没有误分类点或者学习次数大于阈值时，停止训练。 最终的权值向量和偏置就是所求的超平面的参数。 需要说明的地方： a.权值向量和偏置在一开始需要进行初始化，初始化的值不同，训练所得的超平面也会不同。 b.不同的误分类点以及不同的输入顺序也会造成学习所得的超平面不同。 因此，在每次训练一个感知器的时候，结果并不是固定的，因此评价其性能一般需要多训练几次取结果的平均值。 还有一个重要的点是感知器算法的收敛性，即经过有限次的迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知器模型。这里面涉及的公示很多，不再贴出来，有兴趣的话可以证明一下，还是有必要的。 下面的章节讨论朴素贝叶斯法和决策树法。 关于感知机的扩展会有一章介绍极速学习ELM神经网络。 —————————————————————————————————— 机器学习笔记（四）朴素贝叶斯法和决策树 1.朴素贝叶斯法 朴素贝叶斯法是基于贝叶斯定理和特征条件独立假设的分类方法。给定训练数据集，首先基于特征条件独立假设学习输入/输出的联合概率分布，然后根据此模型，对给定的输入x，利用贝叶斯定理求出后验概率最大的输出y。 朴素贝叶斯法属于生成方法，关键在于找到输入输出的联合分布，或者说确定联合分布的参数也就确定了联合分布。在特征条件独立的假设下，对每一个特征通过频率求解其条件概率分布，这些条件概率分布最终用于求解后验概率。 开始之前最好先回顾一下条件概率公式和全概率公式，它们是计算贝叶斯模型的基础。 条件概率wiki的链接：http://zh.wikipedia.org/wiki/条件分布 给定有限训练样本集，输入为特征向量，输出为类标记，在朴素贝叶斯方法中将输入和输出定义为在输入空间和输出空间的随机变量X和Y，贝叶斯方法在变量之上学习联合分布P(X,Y)，具体地，学习 先验概率分布：
和 条件概率分布：
,K是标签的种类。 假设特征条件独立，则条件概率分布可写成：
有了条件概率分布和先验概率分布就可以推导后验概率了（注意这里面用到了条件概率公式和全概率公式）：
，k=1,...K 这样的话，给定一个实例x ，我们就可以得到在该实例给定下类标是各个值得概率，选择概率最大的类标最为该实例的类标，用公式表示如下：
需要知道的一点： 朴素贝叶斯法将实例分到后验概率最大的类中，等价于0-1损失函数时的期望风险最小化。 这里肯定会有疑问，训练数据集在哪里？ 别急，上面只是给了模型的数学推导过程，具体求解各个分布的参数时才使用到训练数据集。 a. 先验概率的极大似然估计：
b. 设第j 个特征可能取值的集合为{
} ，条件概率
的极大似然估计为：
，j=1,...n; l=1,...,Sj; k=1,...K 即通过训练数据集中各类中不同特征出现的频率比值作为该特征的条件概率，这里假设类条件下各特征独立的作用就显而易见了。 c.贝叶斯估计 由于，概率分布的计算是基于频率的，因此在对某个实例预测时，很可能输入的特征在训练数据集的特征中找不到对应的值，所以概率就会为零，解决这一问题的方法是采用贝叶斯估计，在分子和分母上加入一个参数：
等价于在随机变量各个取值的频数上赋予一个正整数λ>0。其值为零就是极大似然估计，其值为1就是拉普拉斯平滑。 这个时候注意，先验概率变成了：
无论是极大似然估计还是贝叶斯估计，都满足概率分布的条件，即所有概率之和为1，满足结合律。 总结一下朴素贝叶斯模型就是先通过训练数据集计算先验概率分布和条件概率分布，得到联合概率分布，然后通过联合概率分布求得后验概率分布。概率估计的方法可以是极大似然估计或贝叶斯估计。 2.决策树模型 决策树模型也属于生成模型，是一种特殊的二叉树。树上的节点分为叶子节点和内部节点（非叶子结点），内部节点表示特征和属性，叶子节点表示类，可以这样理解，内部节点把特征空间划分开来，叶子节点则一般为同类的样本集合。每个从决策树顶点到叶子节点的路径就是一个判别过程，该路径把一个实例和类标对应了起来。if-then规则下的决策树模型满足完备性和互斥性，完备性表示对每个输入实例都能找到一条路径求得其类标，互斥性表示这样的路径对于确定的决策树是唯一的。条件概率分布下的决策树则未必，。 决策树模型的分类过程如下： 从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子节点，子节点对应着该特征的一个取值，然后递归的进行下去，直到到达叶子节点，最终实例被分到叶子节点的类中。 —————————————————————————————————— ELM算法1 ELM(Extreme Learning Machine)是一种新型神经网络算法，最早由Huang于2004年提出【Extreme learning machine: a new learning scheme of feed-forwardneural networks】。与SVM，传统神经网络相比，ELM的训练速度非常快，需要人工干扰较少，对于异质的数据集其泛化能力很强。Huang在【Extreme learningmachines: a survey，2011】这篇论文中对ELM进行了总结，包括最初的ELM算法和后来被发展延伸的ELM算法(比如在线序列ELM算法、增量ELM算法和集成ELM算法等)，里面的很多知识点值得学习。 ELM的原理 从神经网络的结构上来看，ELM 是一个简单的SLFN ，SLFN 示意图如下：
该SLFN包括三层：输入层、隐含层和输出层（忽略输入层则为两层）。其中隐含层包括L个隐含神经元，一般情况下L远小于N，输出层的输出为m维的向量，对于二分类问题，显然该向量是一维的。 对于一个训练数据样本，忽略输入层和隐含层而只考虑隐含层神经元的输出和输出层，则神经网络的输出函数表达式为：
ai 和bi 是隐含层节点的参数，表示第i 个隐含层神经元和输出神经元之间的连接权值，即它是一个m 维的权值向量。公式里面的G 是隐含层神经元的输出。针对加法型隐含层节点，G 为：
其中，小g 为激励函数，激励函数可以是线性函数，也可以是sigmoid 函数；针对RBF 型隐含层节点，G 为：
ai 和bi 分别表示了第i 个径向基函数节点的中心和影响因子。 神经网络输出函数可以写成：
，其中：
如果神经网络能够无误差的预测训练样本，那么隐含层和输出层的权值是有解的，特别的，当L=N 时，肯定有解。但是实际问题中，L 往往是远小于N 的，那么求解权值向量的问题是无解的，即网络输出和实际值之间有误差，可以定义代价函数为：
接下来如何求解最优的权值向量，使得损失函数J最小呢？ 针对这个问题ELM分两种情况解决： a. 如果H 是列满秩的，那么可以通过最小二乘找到最佳的权值，其解为：
，其中：
b.如果H是非列满秩的，则使用奇异值分解求解H的广义逆来计算最佳权值。 和BP使用梯度下降迭代更新所有层之间权值不同，ELM不调整SLFN的输入层和隐含层的权值，这些权值是随即设定的，因此ELM的训练速度非常快。ELM注重于隐含层到输出层的权值的选取，其采用的方法是最小二乘。 ELM 算法一般可以描述如下：
在Huang的survey中描述了一种思想，该思想把SVM也看成了神经网络，该思想把神经网络的输入层到最后一层隐含层的部分或者SVM核函数映射的部分都看成了从输入空间到一个新的空间的转换，然后，BP会将误差反向传播更新权值使得误差最小化，而SVM则力求找到最大分界间隔的分界面，将新空间映射到输出空间，从这个角度来看，SVM确实可以看成是一种神经网络。 ELM最初算法就如上所述，从2004年至今，后来的学者对其进行了很多改进，主要包括对输入层和隐含层权值随即确定权值的优化、求解隐含层和输出层权值的优化（使得ELM更适应于噪声数据集）、核函数ELM以及加入了正则化项的损失函数（求解结构风险而不再是经验风险）、ELM和其他方法相结合等。ELM为神经网络的结构设计提供了一个新的思路，使我们更好地理解神经网络，但是还有很多问题需要解决，比如隐含层节点个数的确定，正则化项的选择等等。作为一个性能很好的机器，我们也可以将其应用到诸多交叉学科的应用中。
| 
/1 
|Archiver|手机版|小黑屋|陕ICP备15012670号-1
发表于 2015-12-22 22:02:26
收藏