IDMer (数据挖掘者)--机器学习介绍（编译）

	机器学习介绍（编译）

	数据挖掘者发表于 2005/6/26 9:24:51

	机器学习介绍来源：http://www.cs.utexas.edu/users/mooney/cs391L/编译：Sunstone Zhang （2002年于人大数据库所）什么是学习？ 1为什么要研究学习？ 2相关领域 2副主题 2定义学习任务 3设计学习系统 3训练集（TRAINING EXPERIENCE） 4选择目标函数 4可能的目标函数定义V(B) 4目标函数的表达 4获取训练值 5学习算法 5学习程序的结构 6小结 6学习系统的评价 6机器学习的简单历史回顾 7 什么是学习？·H. Simon给出的定义：“能使系统改进性能的任何处理过程”·学习的任务是什么？ - 分类（医疗诊断，信用卡业务或交易，投资，DNA序列，口语，手写，天文图象） - 问题解决，计划和行为（解决微分问题，下跳棋，象棋，平衡杠杆，驾车） ·如何进行性能评价？- 分类精度 - 解答的正确性和质量 - 性能的速度为什么要研究学习？ ·让计算机系统具有新的能力- 某些系统开发非常困难或者无法手工创建，原因在于它们需要特定的细节知识或技能来完成特别复杂的任务（知识获取的瓶颈）- 系统要能够根据经验来自动适应和定制自身，以满足单个用户的需求，例如个性化新闻或邮件过滤，个性化教程- 在数据库中发现知识和模式，数据库挖掘，例如发现购买模式来指导市场经营·更好地理解人和其它生物的学习和教学过程- Power law of practice. - Relative difficulty of learning disjunctive concepts. ·时机恰当- 已经具备初步的算法和理论基础- 在线数据量的不断增长- 计算能力已经具备相关领域·人工智能（Artificial Intelligence）·概率与统计（Probability and statistics）·计算复杂性理论（Computational complexity theory）·控制论（Control theory）·信息理论（Information theory）·哲学（Philosophy）·心理学（认知，进化）（Psychology (cognitive, developmental)）·神经生物学（Neurobiology）·语言学（Linguistics）副主题·概念学习Concept learning and the General to Specific Ordering ·决策树学习Decision Tree Learning ·学习算法的实验评价Experimental Evaluation of Learning Algorithms ·规则学习：Rule Learning: Propositional and First Order ·人工神经网络Artificial Neural Networks ·贝叶斯学习Bayesian Learning ·计算学习理论Computational Learning Theory ·基于实例的学习Instance-based Learning ·分析学习Analytical Learning ·归纳和分析学习的联合Combining Inductive and Analytical Learning ·强化学习Reinforcement Learning ·遗传算法Genetic Algorithms 定义学习任务·任务T，性能测度P，基于经验E·T: 下跳棋P: 赢对手的比率 E: 和自身下的练习 ·T: 识别手写字P: 正确识别的比率E: 手写字识别数据库 ·T: 通过视觉传感器在高速公路驾驶车辆P: 平均安全行驶距离E: 司机驾驶的图象和操纵指令序列·T: 诊断病人所患病症P: 正确诊断的比率E: 带有医生诊断的病人记录数据库·T: 已知前提和结果，为实现目标生成计划P: 生成计划所需的平均时间 E: 问题集合样本（初态，目标，操作员）设计学习系统·选择训练集（training experience）·选择要学习的确切目标，即目标函数（target function）·选择该如何表示目标函数·选择学习算法，从训练集中学习目标函数训练集（Training Experience）·直接或间接经验Direct or Indirect Experience- 直接: 根据棋谱标注了正确走法的棋盘- 间接: 潜在的任意走法序列以及最终输赢结果·赞赏/责备赋值: 当只有间接反馈时该如何评价每步走法的好坏？ ·训练集来源:- 不受学习者控制的''随机''样本（只有反面例子？）- 由指导教师选取的例子 (near misses available?). - Ability to query oracle about correct classifications. - Ability to design and run experiments to collect one's own data. ·训练数据的分布: 一般会假定训练数据是测试样本的代表选择目标函数·明确要学习什么以及学习后如何使用？·在下跳棋的例子中，假设给定了一个能生成下一步合理走法的函数，要学习该如何选择正确的下法。·能够通过学习得到这样的函数，它可以将一个棋局对应到下一个合理走法， ChooseMove(board) ? best-move. ·能够学习评价函数，V，按照愿望给棋局打分。使用评价函数就可以判断出最合适的走法。可能的目标函数定义V(b) 1) 若b为棋局结果且为赢，则V(b)=100 2) 若b为棋局结果且为输，则V(b)=-100 3) 若b为棋局结果且为和，则V(b)=0 4) 若b非棋局结果，则V(b) =V(b')，其中b'是从b开始能达到的最佳结局评分。·但是，这需要对游戏树进行穷举式的搜索，代价太大，难以实用化。·实用化要求必须在可接受的时间内完成。·一般只要能够与理想目标函数近似就可以了。目标函数的表达·目标函数可以有多种表达形式：对照表，符号规则，连续数值函数，神经网络等。·表达的易读性和学习的方便性之间的折衷。表达方式越复杂，它就能更好地逼近任意函数，但同时也需要更多的样本来学习特定的假设。 ·在下跳棋的例子中，假设我们采用某些棋局特征的线性函数： bp(b): 棋盘b上的黑棋个数rp(b): 棋盘b上的红棋个数bk(b): 棋盘b上的黑王个数rk(b): 棋盘b上的红王个数bt(b): 受红棋威胁的黑棋个数（即它下一步可以变为红棋）rt(b): 受黑棋威胁的红棋个数获取训练值·一般地，目标函数的训练值可以直接从训练集中得到。<<bp=3,rp=0,bk=1,rk=0,bt=0,rt=0>,+100> (黑棋赢) ·在间接反馈的情况下，需要估计训练值。在下棋问题中，中间棋局状态的值无法得到，所以当前棋局状态的值用其下一步的估计值来代替：这样越到最后值就越精确，训练值被逐步回滚（back-ups）到以前的棋局。学习算法·学习算法用目标函数的训练值来逼近样本值。·对于数值函数预测，通常会最小化训练值与预测值之间的误差方差： ·对于线性函数的权重，可以采用一种递增式的算法来逐步调整权重以拟合训练样本，如LMS（最小均方差）方法，它进行梯度下降搜索。Until convergence do For each training example b 1)Compute the non-squared error 2)For each board feature, fi , update its weight, wi, as follows , where c is some small constant, e.g. 0.5 ·从直观上看，LMS的处理流程如下：1) 对于某一个样本来说，如果输出值正确，则不进行任何更改；2) 如果输出值太高，成比例地降低各个特征的权重，从而使得整个输出值降低；3) 如果输出值太低，成比例地增加各个特征的权重，从而使得整个输出值升高。·在正确的假设下，本方法将以最小方差收敛于假设。学习程序的结构小结·近似函数可被视为在预定义的假设空间中查找某个假设，该假设能够最好地拟合训练数据。·不同的学习方法采用了不同的假设空间或不同的查找技术。·表达方式可以不同：- 数值函数- 规则或逻辑函数- 最近邻居（基于实例）·查找算法可以不同：- 梯度下降（Gradient descent）- 分而治之（Divide and conquer）- 遗传算法（Genetic algorithm）学习系统的评价·实验型：通过精心控制的实验来比较不同方法的基准问题（benchmark problems），收集性能数据（例如精度、运行时间），并对结果的重大差别进行分析。 ·理论型：用数学方法分析算法，论证其计算复杂度，证明它确实能生成假设来拟合训练数据，或者需要多少样本才能生成假设来拟合未知数据（样本复杂度）。机器学习的简单历史回顾 ·1950's: Samuels checker player ·1960's: Neural networks, perceptron; pattern recognition; learning in the limit theory; Minsky & Papert. ·1970's: Symbolic concept induction; Winston's arch learner; knowledge acquistion bottleneck; Quinlan's ID3; Michalski's AQ and soybean diagnosis results; Scientific discovery with BACON; mathematical discovery with AM. ·1980's: Continued progress on decision-tree and rule learning; Explantion-based learning; speedup learning; utility problem, analogy; resurgence of connectionism (PDP, ANN); Valiant's PAC learning theory; experimental evaluation. ·1990's: Data mining; adaptive software agents & IR; reinforcement learning; theory refinement; inductive logic programming; voting, bagging, boosting, and stacking; learning Bayesian networks.

	阅读全文(5485) \| 回复(0) \| 编辑 \| 精华

发表评论：

昵称：
密码：
主页：
标题：

验证码： (不区分大小写,请仔细填写,输错需重写评论内容！)