1.1机器学习综述.ppt

管窥机器学习 邹博 2014年10月18日 机器学习 在具体学习机器学习的过程中，往往是因为推导造成的障碍 了解基本的高等数学知识是必要的 机器学习比想象中要简单的多 举例：kNN用于分类、基本的聚类过程 本次目标 了解机器学习中的相关基本概念和常用方法 初步掌握极大似然估计、梯度下降法的一般性计算套路 熟悉最小二乘法的目标函数建立和解决方案 了解期望最大化算法（EM算法）的思路 若干概念 交叉验证 泛化能力 VC维 监督学习 无监督学习 强化学习 机器学习算法的分类 监督 K近邻 回归 SVM 决策树 朴素贝叶斯 BP神经网络 非监督 聚类 Apriori FP-growth 交叉验证 交叉验证(Cross-validation)也称为交叉比对，主要用于建模应用中。在给定的建模样本中，拿出大部分样本进行建模型，留小部分样本用刚建立的模型进行预报，并求这小部分样本的预报误差，记录它们的平方加和。这个过程一直进行，直到所有的样本都被预报了一次而且仅被预报一次。把每个样本的预报误差平方加和，称为PRESS(predicted Error Sum of Squares)。 交叉验证是常用的精度测试方法，其目的是为了得到可靠稳定的模型。例如10折交叉验证(10-fold cross validation)，将数据集分成十份，轮流将其中9份做训练1份做测试，10次的结果的均值作为对算法精度的估计，一般还需要进行多次10折交叉验证求均值，例如：10次10折交叉验证，以求更精确一点。 交叉验证的形式 Holdout 验证 通常来说，Holdout 验证并非一种交叉验证，因为数据并没有交叉使用。 随机从最初的样本中选出部分，形成交叉验证数据，而剩余的就当做训练数据。 一般来说，少于原本样本三分之一的数据被选做验证数据。 K-fold cross-validation K折交叉验证，初始采样分割成K个子样本，一个单独的子样本被保留作为验证模型的数据，其他K-1个样本用来训练。交叉验证重复K次，每个子样本验证一次，平均K次的结果或者使用其它结合方式，最终得到一个单一估测。这个方法的优势在于，同时重复运用随机产生的子样本进行训练和验证，每次的结果验证一次，10折交叉验证是最常用的。 留一验证 意指只使用原本样本中的一项来当做验证资料， 而剩余的则留下来当做训练资料。 这个步骤一直持续到每个样本都被当做一次验证资料。 事实上，这等同于 K-fold 交叉验证是一样的，其中K为原本样本个数。 泛化能力 概括地说，所谓泛化能力（generalization ability）是指机器学习算法对新鲜样本的适应能力。学习的目的是学到隐含在数据对背后的规律，对具有同一规律的学习集以外的数据，经过训练的算法也能给出合适的输出，该能力称为泛化能力。 通常期望经训练样本训练的算法具有较强的泛化能力，也就是对新输入给出合理响应的能力。应当指出并非训练的次数越多越能得到正确的输入输出映射关系。算法的性能主要用它的泛化能力来衡量。 VC维 对于一个分类H，我们定义它的Vapnik Chervonenkis dimension, 记做VC(H)：指的是能够被H打散的最大集合的数目。 打散：shatter 如果H能够打散任意数目的集合，我们定义VC(H)=∞ VC维 考虑如图所示，3个点的集合： 3个点可完全分开(zero training error) 一个集合，不是所有 Note that the VC dimension of H here is 3 even though there may be sets of size 3 that it cannot shatter. For instance, if we had a set of three points lying in a straight line (left figure), then there is no way to find a linear separator for the labeling of the three points shown below (right figure): 再次强调 在VC维的定义下，为了证明VC(H)至少是d，我们只需要证明至少存在一个大小是d的集合是可以被打散的。 如果对于任意的样本数，总能找到一个样本集，它能够被某分类H打散，则该分类H的VC维就是无穷大，这个分类H的学习性能也就是最好的。 VC维反映了分类集的学习能力，VC维越大则学习机器越复杂（容量越大），遗憾的是，目前尚没有通用的关于任意分类集VC维计算的理论，只对一些特殊的分类集知道其VC维。例如在N维空间中线形分类器的VC维是N+1。 从下面几个问题入手机器学习 k近邻 向量距离