Machine_Learning讲座笔记_刘佳倩_最终版

MachineLearningNote2012-02刘佳倩MachineLearning讲座笔记Writtenby刘佳倩Instructedby夏粉演讲者：浙江大学何晓飞演讲时间：2012-02-14目录理论知识部分...................................................................................................................................2分类问题...................................................................................................................................2线性可分模型...................................................................................................................2线性不可分模型...............................................................................................................4回归问题...................................................................................................................................6分类问题V.S.回归问题....................................................................................................6学习模型...........................................................................................................................7流形Manifold...........................................................................................................................9降维PCA...........................................................................................................................9ISOMAP.............................................................................................................................9流形正则化.......................................................................................................................9实际应用部分.................................................................................................................................10图像搜索ImageSearch..........................................................................................................10基本知识介绍.................................................................................................................10图像搜索的步骤.............................................................................................................10近似搜索.........................................................................................................................10排序学习LearningtoRank.....................................................................................................11背景描述.........................................................................................................................11模型设计.........................................................................................................................11矩阵分解和推荐MatrixFactorizationandRecommendation...............................................12基本概念.........................................................................................................................12实际例子.........................................................................................................................12解决方法.........................................................................................................................12注：本文所有插图，除特别注明，均为作者画图板所做，存在一定程度上的比例不调，请多包涵。MachineLearningNote2012-02刘佳倩理论知识部分分类问题线性可分模型如果用一个线性函数可以将两类样本完全分开，就称这些样本是“线性可分”的。以二维为例，假设trainingdata是二维的，分为两类：红和蓝。则图1中的红点和蓝点是线性可分的。（图1）可行划分如何找到一个可行划分呢？有一种方法叫感知机(Perceptron)，下面是wikipedia上对感知机的介绍：(源地址)MachineLearningNote2012-02刘佳倩最优划分不同划分对于未知数据会有不同的预测结果。那么如何找到一条效果好的划分呢？（当然我们这里说的效果好只是针对训练数据而言╮(╯▽╰)╭……）图1中的点可能有多种划分方法，见图2：我们首先定义一些变量：x(j)表示n维输入向量中的第j项w(j)表示权重向量的第j项f(x)表示神经元接受输入x产生的输出α是一个常数，符合(接受率)更进一步，为了简便我们假定偏置量b等于0。因为一个额外的维n+1维，可以用x(n+1)=1的形式加到输入向量，这样我们就可以用w(n+1)代替偏置量。感知器的学习通过对所有训练实例进行多次的迭代进行更新的方式来建模。令表示一个有m个训练实例的训练集。每次迭代权重向量以如下方式更新：对于每个中的每个(x,y)对，注意这意味着，仅当针对给定训练实例(x,y)产生的输出值f(x)与预期的输出值y不同时，权重向量才会发生改变。如果存在一个正的常数γ和权重向量w，对所有的i满足，训练集Dm就被叫被做线性分隔的。Novikoff(1962)证明如果训练集是线性分隔的，那么感知器算法可以在有限次迭代后收敛，错误的数量由限定，其中R为输入向量的最大平均值。然而，如果训练集不是线性分隔的，那么这个算法则不能确保会收敛。MachineLearningNote2012-02刘佳倩（图2）其中，绿色直线到最近点的距离最大，我们认为它是一条效果很好的划分。注意到，所有可行划分中，存在这样一对平行线，它们距离最远，图2中的绿色直线就位于这两条平行线中间（平分）位置。求解过程中，只需要枚举所有可能的平行线，取距离最远的那一对，即可得出最优划分。为了使平行线距离尽可能大，我们认为这两条平行线一定是夹在三个点之间的，而我们不必枚举所有训练点集，只需要枚举落在包围壳（图3黄色部分）上的点。（图3）最优划分只与包围壳上的部分点(平行线上的点)有关，这些点称为支持向量，有一种算法叫HardMarginSVM（硬性边缘支持向量机）算法，可以求出这个较优划分。有兴趣的同学可以看看wikipedia。线性不可分模型图4中的两种颜色的点是无法线性划分的。（图4）MachineLearningNote2012-02刘佳倩模型转化可以将训练数据映射至高维空间，把线性不可分转化为高维空间的线性可分。比如，将图4中的点，以ϕ(x)=x2映射到二维空间，它们就线性可分了，如图5：（图5）核函数KernelFunction先来看一下核函数的简介。再来看夏粉对核函数的评价：核函数是机器学习里一个里程碑式的进步，它简化了问题的认识，将核函数生产的空间定义为再生核希尔伯特空间，比如我们常见的欧式空间就是它的一个特例。有了再生核希尔伯特空间后，算法设计者只需要关心在这个空间里设计线性算法即可，对于算法如何实现其非线性形式只需定义不同的核函数即可。再生核希尔伯特空间完美地解释了核函数,并由此产生了机器学习中核方法这个方向,由此将学习方法与假设空间独立开,使得在线性空间中的任何方法可以无障碍地推广到非线性空间。MachineLearningNote2012-02刘佳倩不过核函数有一个缺点：线性可分的最低维数未知，有可能是无限维。回归问题分类问题V.S.回归问题分类问题：标签为类别值，如图6，有红、蓝、绿三种类别，对任意两个点，它们之间的关系是“同类”或“不同类”两种之一。（图6，图片来自网络）回归问题：标签为是实数值，具体来说，就是对于下表中的数据训练数据标签X1Y1=1X2Y2=2X3Y3=3我们认为X1和X2之间的差异是|Y1-Y2|=1，X1和X3之间的差异是|Y1-Y3|=2，X1和X2要更相似一些。MachineLearningNote2012-02刘佳倩学习模型岭回归ridgeregression模型该模型的目标函数是最小化∑(yi−f(xi))2i+λ‖ω‖2其中，f(xi)=ωTxi+b是训练出来的函数，λ‖ω‖2是损失函数，与ω的大小有关。机器学习认为，一个比较平缓的函数f，对未知数据的预测会好一些，而不平缓的f，可能会造成很大的误差，所以，损失函数衡量的就是函数f这一特点。Lassoregression模型该模型的目标函数是最小化∑(