周志华-机器学习ppt-Chap01绪论

机器学习导论(2016春季学期)一、绪论机器学习机器学习是从人工智能中产生的一个重要学科分支，是实现智能化的关键机器学习机器学习（MachineLearning）究竟是什么东东？看个例子“文献筛选”的故事[C.Brodleyetal.,AIMagazine2012]在“循证医学”（evidence-basedmedicine）中，针对特定的临床问题，先要对相关研究报告进行详尽评估查询PubMed以获取候选摘要人工找出值得全文审读的文章“文献筛选”的故事在一项关于婴儿和儿童残疾的研究中，美国Tufts医学中心筛选了约33,000篇摘要尽管Tufts医学中心的专家效率很高，对每篇摘要只需30秒钟，但该工作仍花费了250小时每项新的研究都要重复这个麻烦的过程！需筛选的文章数在不断显著增长！“文献筛选”的故事为了降低昂贵的成本,Tufts医学中心引入了机器学习技术邀请专家阅读少量摘要，标记为“有关”或“无关”分类模型对是否“有关”进行预测人类专家只需阅读50篇摘要，系统的自动筛选精度就达到93%人类专家阅读1,000篇摘要，则系统的自动筛选敏感度达到95%(人类专家以前需阅读33,000篇摘要才能获得此效果)色泽根蒂敲声好瓜青绿蜷缩浊响是乌黑蜷缩浊响是青绿硬挺清脆否乌黑稍蜷沉闷否决策树，神经网络，支持向量机，Boosting，贝叶斯网，……模型训练数据（label）训练新数据样本(浅白,蜷缩,浊响,?)?=是类别标记未知典型的机器学习过程使用学习算法（learningalgorithm）类别标记机器学习与数据挖掘机器学习能做什么？我们可能每天都在用机器学习机器学习模型搜索引擎机器学习技术正在支撑着各种搜索引擎搜索：南京大学例如：互联网搜索……例如：自动汽车驾驶（即将改变人类生活）机器学习模型方向盘旋转幅度油门幅度刹车幅度车载摄像头车载雷达控制汽车美国在20世纪80年代就开始研究基于机器学习的汽车自动驾驶技术DARPAGrandChallenge–2004机器学习能做什么？小数据上就已经很有用例如：画作鉴别（艺术）画作鉴别(paintingauthentication)：确定作品的真伪勃鲁盖尔（1525-1569）的作品？出自[J.Hughesetal.,PNAS2009]梵高（1853-1890）的作品？出自[C.Johnsonetal.,IEEE-SP,2008]例如：画作鉴别（艺术）除专用技术手段外，笔触分析(brushstrokeanalysis)是画作鉴定的重要工具；它旨在从视觉上判断画作中是否具有艺术家的特有“笔迹”。该工作对专业知识要求极高-具有较高的绘画艺术修养-掌握画家的特定绘画习惯只有少数专家花费很大精力才能完成分析工作！很难同时掌握不同时期、不同流派多位画家的绘画风格！[C.Johnsonetal.,IEEE-SP,2008]例如：画作鉴别（艺术）真迹+赝品特有“笔迹”待鉴定画作为了降低分析成本,机器学习技术被引入自动鉴定分类模型KröllerMüller美术馆与Cornell等大学的学者对82幅梵高真迹和6幅赝品进行分析，自动鉴别精度达95%[C.Johnsonetal.,IEEE-SP,2008]Dartmouth学院、巴黎高师的学者对8幅勃鲁盖尔真迹和5幅赝品进行分析，自动鉴别精度达100%[J.Hughesetal.,PNAS2009][J.Mairaletal.,PAMI’12](对用户要求低、准确高效、适用范围广)例如：古文献修复（文化）古文献是进行历史研究的重要素材，但是其中很多损毁严重DeadSeaScrolls(死海古卷)-1947年出土-超过30,000个羊皮纸片段CairoGenizah-19世纪末被发现-超过300,000个片段-散布于全球多家博物馆高水平专家的大量精力被用于古文献修复[L.Wolfetal.,IJCV2011]例如：古文献修复（文化）一个重要问题：原书籍已经变成分散且混杂的多个书页，如何拼接相邻的书页？人工完成书页拼接十分困难-书页数量大，且分布在多处-部分损毁较严重，字迹模糊-需要大量掌握古文字的专业人才近年来，古文献的数字化浪潮给自动文学修复提供了机会例如：古文献修复（文化）以色列特拉维夫大学的学者将机器学习用于自动的书页拼接已确定相邻已确定不相邻分类模型判断是否相邻专家确认相邻在CairoGenizah测试数据上，系统的自动判断精度超过93%新完成约1,000篇CairoGenizah文章的拼接(对比：过去整个世纪，数百人类专家只完成了几千篇文章拼接)机器学习能做什么？大数据上更惊人例如：帮助奥巴马胜选（政治）《时代》周刊例如：帮助奥巴马胜选（政治）通过机器学习模型：在总统候选人第一次辩论后，分析出哪些选民将倒戈，为每位选民找出一个最能说服他的理由精准定位不同选民群体，建议购买冷门广告时段，广告资金效率比2008年提高14%向奥巴马推荐，竞选后期应当在什么地方展开活动——那里有很多争取对象借助模型帮助奥巴马筹集到创纪录的10亿美元例如：利用模型分析出，明星乔治克鲁尼（GeorgeClooney）对于年龄在40-49岁的美西地区女性颇具吸引力，而她们恰是最愿意为和克鲁尼/奥巴马共进晚餐而掏钱的人……乔治克鲁尼为奥巴马举办的竞选筹资晚宴成功募集到1500万美元……例如：帮助奥巴马胜选（政治）队长：RayidGhani卡内基梅隆大学机器学习系首任系主任TomMitchell教授的博士生这个团队行动保密，定期向奥巴马报送结果；被奥巴马公开称为总统竞选的“核武器按钮”(“Theyareournuclearcodes”)约翰麦卡锡(1927-2011)“人工智能之父”1971年图灵奖1956年夏美国达特茅斯学院J.McCarthy,M.Minsky,N.Lochester,C.E.Shannon,H.A.Simon,A.Newell,A.L.Samuel等10余人达特茅斯会议标志着人工智能这一学科的诞生JohnMcCarthy(1927-2011):1971年获图灵奖,1985年获IJCAI终身成就奖。人工智能之父。他提出了“人工智能”的概念，设计出函数型程序设计语言Lisp，发展了递归的概念，提出常识推理和情境演算。出生于共产党家庭，从小阅读《10万个为什么》，中学时自修CalTech的数学课程，17岁进入CalTech时免修两年数学，22岁在Princeton获博士学位，37岁担任Stanford大学AI实验室主任。机器学习源自“人工智能”ArtificialIntelligence(AI),1956-赫伯特西蒙(1916-2001)1975年图灵奖第一阶段：推理期1956-1960s:LogicReasoning出发点:“数学家真聪明！”主要成就:自动定理证明系统(例如，西蒙与纽厄尔的“LogicTheorist”系统)渐渐地，研究者们意识到，仅有逻辑推理能力是不够的…阿伦纽厄尔(1927-1992)1975年图灵奖出发点:“知识就是力量！”爱德华费根鲍姆(1936-)1994年图灵奖主要成就:专家系统(例如，费根鲍姆等人的“DENDRAL”系统)渐渐地，研究者们发现，要总结出知识再“教”给系统，实在太难了…第二阶段：知识期1970s-1980s:KnowledgeEngineering出发点:“让系统自己学！”第三阶段：学习期1990s-now:MachineLearning主要成就:……机器学习是作为“突破知识工程瓶颈”之利器而出现的恰好在20世纪90年代中后期，人类发现自己淹没在数据的汪洋中，对自动数据分析技术——机器学习的需求日益迫切汽车自动驾驶(DARPAGrandChallenge)机器学习已经“无处不在”入侵检测Web搜索生物信息学决策助手(DARPA)火星机器人(JPL)今天的“机器学习”已经是一个广袤的学科领域经常被谈到的“深度学习”(DeepLearning)仅是机器学习中的一个小分支例如，这是第32届国际机器学习大会的“主题领域”2006年，美国CMU(卡内基梅隆大学)成立“机器学习系”大数据时代的关键技术奥巴马提出“大数据计划”后，美国NSF进一步加强资助UCBerkeley研究如何整合将”数据”转变为”信息”的三大关键技术——机器学习、云计算、众包(crowdsourcing)整合三大关键技术大数据时代，机器学习必不可少收集、传输、存储大数据的目的，是为了“利用”大数据没有机器学习技术分析大数据，“利用”无从谈起基本术语•••••••数据集;训练,测试示例(instance),样例(example)样本(sample)属性(attribute),特征(feature);属性值属性空间,样本空间,输入空间特征向量(featurevector)标记空间,输出空间••监督学习(supervisedlearning)无监督学习(unsupervisedlearning)•••假设(hypothesis)真相(ground-truth)学习器(learner)•••••分类,回归•二分类,多分类•正类,反类未见样本(unseeninstance)未知“分布”独立同分布(i.i.d.)泛化(generalization)假设空间(色泽=?)⋀(根蒂=?)⋀(敲声=?)↔好瓜学习过程在所有假设(hypothesis)组成的空间中进行搜索的过程目标:找到与训练集“匹配”(fit)的假设假设空间的大小：n1xn2xn3+1例如:(青绿;蜷缩;沉闷)应该采用哪一个模型(假设)?版本空间版本空间(versionspace):与训练集一致的假设集合浊响浊响在面临新样本时，会产生不同的输出归纳偏好(inductivebias)机器学习算法在学习过程中对某种类型假设的偏好A更好？B更好？一般原则：奥卡姆剃刀(Ocam’srazor)任何一个有效的机器学习算法必有其偏好学习算法的归纳偏好是否与问题本身匹配，大多数时候直接决定了算法能否取得好的性能！哪个算法更好？没有免费的午餐！NFL定理：一个算法若在某些问题上比另一个算法好，必存在另一些问题，比好。NFL定理简单起见，假设样本空间和假设空间离散,令代表算法基于训练数据X产生假设h的概率，f代表要学的目标函数，在训练集之外所有样本上的总误差为考虑二分类问题，目标函数可以为任何函数，，函数空间为，对所有可能的f按均匀分布对误差求和，有NFL定理总误差与学习算法无关！所有算法一样好！NFL定理的寓意NFL定理的重要前提：所有“问题”出现的机会相同、或所有问题同等重要脱离具体问题，空泛地谈论“什么学习算法更好”毫无意义！实际情形并非如此；我们通常只关注自己正在试图解决的问题前往第二站……