MachineLearning讲座笔记刘佳倩最终版.docxVIP

Machine Learning讲座笔记Written by刘佳倩Instructed by 夏粉演讲者：浙江大学 何晓飞演讲时间： 2012-02-14 目录理论知识部分2分类问题2线性可分模型2线性不可分模型4回归问题6分类问题V.S.回归问题6学习模型7流形Manifold9降维PCA9ISOMAP9流形正则化9实际应用部分10图像有哪些信誉好的足球投注网站Image Search10基本知识介绍10图像有哪些信誉好的足球投注网站的步骤10近似有哪些信誉好的足球投注网站10排序学习Learning to Rank11背景描述11模型设计11矩阵分解和推荐Matrix Factorization and Recommendation12基本概念12实际例子12解决方法12注：本文所有插图，除特别注明，均为作者画图板所做，存在一定程度上的比例不调，请多包涵。理论知识部分分类问题线性可分模型如果用一个线性函数可以将两类样本完全分开，就称这些样本是“线性可分”的。以二维为例，假设training data是二维的，分为两类：红和蓝。则图1中的红点和蓝点是线性可分的。（图1）可行划分如何找到一个可行划分呢？有一种方法叫感知机(Perceptron)，下面是wikipedia上对感知机的介绍：(/wiki/%E6%84%9F%E7%9F%A5%E5%99%A8源地址)我们首先定义一些变量：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就被叫被做/w/index.php?title=%E7%BA%BF%E6%80%A7%E5%88%86%E9%9A%94action=editredlink=1 \o 线性分隔线性分隔的。Novikoff (1962)证明如果/w/index.php?title=%E8%AE%AD%E7%BB%83%E9%9B%86action=editredlink=1 \o 训练集训练集是线性分隔的，那么感知器算法可以在有限次迭代后收敛，错误的数量由限定，其中R为输入向量的最大平均值。然而，如果训练集不是线性分隔的，那么这个算法则不能确保会收敛。最优划分不同划分对于未知数据会有不同的预测结果。那么如何找到一条效果好的划分呢？（当然我们这里说的效果好只是针对训练数据而言╮(╯▽╰)╭……）图1中的点可能有多种划分方法，见图2：（图2）其中，绿色直线到最近点的距离最大，我们认为它是一条效果很好的划分。注意到，所有可行划分中，存在这样一对平行线，它们距离最远，图2中的绿色直线就位于这两条平行线中间（平分）位置。求解过程中，只需要枚举所有可能的平行线，取距离最远的那一对，即可得出最优划分。为了使平行线距离尽可能大，我们认为这两条平行线一定是夹在三个点之间的，而我们不必枚举所有训练点集，只需要枚举落在包围壳（图3黄色部分）上的点。（图3）最优划分只与包围壳上的部分点(平行线上的点)有关，这些点称为支持向量，有一种算法叫Hard Margin SVM（硬性边缘支持向量机）算法，可以求出这个较优划分。有兴趣的同学可以看看/wiki/Support_vector_machine \l Linear_SVMwikipedia。线性不可分模型图4中的两种颜色的点是无法线性划分的。（图4）模型转化可以将训练数据映射至高维空间，把线性不可分转化为高维空间的线性可分。比如，将图4中的点，以映射到二维空间，它们就线性可分了，如图5：（图5）核函数Kernel Function先来看一下核函数的简介。再来看夏粉对核函数的评价：核函数是机器学习里一个里程碑式的进步，它简化了问题的认识，将核函数生产的空间定义为再生核希尔伯特空间， 比如我们常见的欧式空间就是它的一个特例。有了再生核希尔伯特空间后，算法设计者只需要关心在这个空间里设计线性算法即可，对于算法如何实现其非线性形式只需定义不同的核函数即可。再生核希尔伯特空间完美地解释了核函数,并由此产生了机器学习中核方法这个方向,由此将学习方法与假设空间独立开,使得在线性空间中的任何方法可以无障碍地推广到非线性空间。不过核函数有一个缺点：线性可分的最低维数未知，有可能是无限维。回归问题分类