機(jī)器學(xué)習(xí)導(dǎo)論(2016春季學(xué)期)一、緒論

機(jī)器學(xué)習(xí)Chap01緒論機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)是從人工智能中產(chǎn)生的一個(gè)重要學(xué)科分支，是實(shí)現(xiàn)智能化的關(guān)鍵機(jī)器學(xué)習(xí)Chap01緒論機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)（MachineLearning）究竟是什么東東？看個(gè)例子機(jī)器學(xué)習(xí)Chap01緒論“文獻(xiàn)篩選”的故事[C.Brodleyetal.,AIMagazine2012]在“循證醫(yī)學(xué)”（evidence-basedmedicine）中，針對(duì)特定的臨床問(wèn)題，先要對(duì)相關(guān)研究報(bào)告進(jìn)行詳盡評(píng)估查詢(xún)PubMed以獲取候選摘要人工找出值得全文審讀的文章機(jī)器學(xué)習(xí)Chap01緒論“文獻(xiàn)篩選”的故事

在一項(xiàng)關(guān)于嬰兒和兒童殘疾的研 究中，美國(guó)Tufts醫(yī)學(xué)中心篩選 了約33,000篇摘要 盡管Tufts醫(yī)學(xué)中心的專(zhuān)家效率 很高，對(duì)每篇摘要只需30秒鐘，但該工作仍花費(fèi)了250小時(shí)每項(xiàng)新的研究都要重復(fù)

這個(gè)麻煩的過(guò)程！需篩選的文章數(shù)在不斷顯著增長(zhǎng)！機(jī)器學(xué)習(xí)Chap01緒論“文獻(xiàn)篩選”的故事為了降低昂貴的成本,Tufts醫(yī)學(xué)中心引入了機(jī)器學(xué)習(xí)技術(shù)邀請(qǐng)專(zhuān)家閱讀少量摘要，標(biāo)記為“有關(guān)”或“無(wú)關(guān)”分類(lèi)模型對(duì)是否“有關(guān)”進(jìn)行預(yù)測(cè)人類(lèi)專(zhuān)家只需閱讀50篇摘要，系統(tǒng)的自動(dòng)篩選精度就達(dá)到93%人類(lèi)專(zhuān)家閱讀1,000篇摘要，則系統(tǒng)的自動(dòng)篩選敏感度達(dá)到95%(人類(lèi)專(zhuān)家以前需閱讀33,000篇摘要才能獲得此效果)機(jī)器學(xué)習(xí)Chap01緒論色澤根蒂敲聲好瓜青綠蜷縮濁響是烏黑蜷縮濁響是青綠硬挺清脆否烏黑稍蜷沉悶否決策樹(shù)，神經(jīng)網(wǎng)絡(luò)，支持向量機(jī)，

Boosting，貝葉斯網(wǎng)，……模型訓(xùn)練數(shù)據(jù)（label）訓(xùn)練

新數(shù)據(jù)樣本(淺白,蜷縮,濁響,?)

?=是類(lèi)別標(biāo)記 未知典型的機(jī)器學(xué)習(xí)過(guò)程

使用學(xué)習(xí)算法（learningalgorithm）

類(lèi)別標(biāo)記機(jī)器學(xué)習(xí)Chap01緒論機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘機(jī)器學(xué)習(xí)Chap01緒論機(jī)器學(xué)習(xí)能做什么？我們可能每天都在用機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)Chap01緒論權(quán)16南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有20保留

機(jī)器 學(xué)習(xí)

模型

搜索引擎機(jī)器學(xué)習(xí)技術(shù)正在支撐著各種搜索引擎

搜索：南京大學(xué)例如：互聯(lián)網(wǎng)搜索

……機(jī)器學(xué)習(xí)Chap01緒論有器學(xué)習(xí)導(dǎo)論課程專(zhuān)保留權(quán)用所2016南京大學(xué)機(jī)例如：自動(dòng)汽車(chē)駕駛（即將改變?nèi)祟?lèi)生活）機(jī)器學(xué)習(xí)模型方向盤(pán)旋 轉(zhuǎn)幅度油門(mén)幅度剎車(chē)幅度車(chē)載攝像頭

車(chē)載雷達(dá) 控制汽車(chē)

美國(guó)在20世紀(jì)

80年代就開(kāi)始 研究基于機(jī)器 學(xué)習(xí)的汽車(chē)自 動(dòng)駕駛技術(shù)DARPAGrandChallenge–2004機(jī)器學(xué)習(xí)Chap01緒論2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有權(quán)保留機(jī)器學(xué)習(xí)能做什么？小數(shù)據(jù)上就已經(jīng)很有用機(jī)器學(xué)習(xí)Chap01緒論2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有權(quán)保留例如：畫(huà)作鑒別（藝術(shù)）

畫(huà)作鑒別(paintingauthentication)：確定作品的真?zhèn)?/p>

勃魯蓋爾（1525-1569） 的作品？

出自[J.Hughesetal.,PNAS2009]梵高（1853-1890）的作品？

出自[C.Johnsonetal.,IEEE-SP,2008]機(jī)器學(xué)習(xí)Chap01緒論機(jī)器學(xué)習(xí)導(dǎo)論2016南京大學(xué)課程專(zhuān)用所有權(quán)保留例如：畫(huà)作鑒別（藝術(shù)）除專(zhuān)用技術(shù)手段外，筆觸分析(brushstrokeanalysis)是畫(huà)作鑒定的重要工具；它旨在從視覺(jué)上判斷畫(huà)作中是否具有藝術(shù)家的特有“筆跡”。該工作對(duì)專(zhuān)業(yè)知識(shí)要求極高-具有較高的繪畫(huà)藝術(shù)修養(yǎng)-掌握畫(huà)家的特定繪畫(huà)習(xí)慣只有少數(shù)專(zhuān)家花費(fèi)很大精力才能完成分析工作！

很難同時(shí)掌握不同時(shí)期、不同流派多位畫(huà)家的繪畫(huà)風(fēng)格！[C.Johnsonetal.,IEEE-SP,2008]機(jī)器學(xué)習(xí)Chap01緒論論課程專(zhuān)用所有權(quán)16南京大學(xué)20機(jī)器學(xué)習(xí)導(dǎo)保留例如：畫(huà)作鑒別（藝術(shù)）真跡+贗品特有“筆跡”待鑒定畫(huà)作為了降低分析成本,機(jī)器學(xué)習(xí)技術(shù)被引入

自動(dòng)鑒定

分類(lèi)模型Kr?llerMüller美術(shù)館與Cornell等大學(xué)的學(xué)者對(duì)82幅梵高真跡和6幅贗品進(jìn)行分析，自動(dòng)鑒別精度達(dá)95%[C.Johnsonetal.,IEEE-SP,2008]Dartmouth學(xué)院、巴黎高師的學(xué)者對(duì)8幅勃魯蓋爾真跡和5幅贗品進(jìn)行分析，自動(dòng)鑒別精度達(dá)100%[J.Hughesetal.,PNAS2009][J.Mairaletal.,PAMI’12](對(duì)用戶(hù)要求低、準(zhǔn)確高效、適用范圍廣)機(jī)器學(xué)習(xí)Chap01緒論2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有權(quán)保留例如：古文獻(xiàn)修復(fù)（文化）

古文獻(xiàn)是進(jìn)行歷史研究的重要素材，但是其中很多損毀嚴(yán)重

DeadSeaScrolls(死海古卷)

-1947年出土

-超過(guò)30,000個(gè)羊皮紙片段

CairoGenizah -19世紀(jì)末被發(fā)現(xiàn)

-超過(guò)300,000個(gè)片段

-散布于全球多家博物館

高水平專(zhuān)家的大量精力 被用于古文獻(xiàn)修復(fù)[L.Wolfetal.,IJCV2011]機(jī)器學(xué)習(xí)Chap01緒論2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有權(quán)保留例如：古文獻(xiàn)修復(fù)（文化）一個(gè)重要問(wèn)題：

原書(shū)籍已經(jīng)變成分散且混雜的多個(gè)書(shū)頁(yè)，如何拼接相鄰的書(shū)頁(yè)？

人工完成書(shū)頁(yè)拼接十分困難

-書(shū)頁(yè)數(shù)量大，且分布在多處

-部分損毀較嚴(yán)重，字跡模糊

-需要大量掌握古文字的專(zhuān)業(yè)人才

近年來(lái)，古文獻(xiàn)的數(shù)字化浪潮給自動(dòng)文學(xué)修復(fù)提供了機(jī)會(huì)機(jī)器學(xué)習(xí)Chap01緒論所有權(quán)保留2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用例如：古文獻(xiàn)修復(fù)（文化）以色列特拉維夫大學(xué)的學(xué)者將機(jī)器學(xué)習(xí)用于自動(dòng)的書(shū)頁(yè)拼接已確定相鄰已確定不相鄰分類(lèi)模型

判斷是否相鄰專(zhuān)家確認(rèn)相鄰在CairoGenizah測(cè)試數(shù)據(jù)上，系統(tǒng)的自動(dòng)判斷精度超過(guò)93%新完成約1,000篇CairoGenizah文章的拼接(對(duì)比：過(guò)去整個(gè)世紀(jì)，數(shù)百人類(lèi)專(zhuān)家只完成了幾千篇文章拼接)機(jī)器學(xué)習(xí)Chap01緒論2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有權(quán)保留機(jī)器學(xué)習(xí)能做什么？大數(shù)據(jù)上更驚人機(jī)器學(xué)習(xí)Chap01緒論2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有權(quán)保留例如：幫助奧巴馬勝選（政治）《時(shí)代》周刊機(jī)器學(xué)習(xí)Chap01緒論2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有權(quán)保留例如：幫助奧巴馬勝選（政治）通過(guò)機(jī)器學(xué)習(xí)模型：

在總統(tǒng)候選人第一次辯論后，分析出哪些選民將倒戈，為每位選民找出一 個(gè)最能說(shuō)服他的理由

精準(zhǔn)定位不同選民群體，建議購(gòu)買(mǎi)冷門(mén)廣告時(shí)段，廣告資金效率比2008年 提高14%

向奧巴馬推薦，競(jìng)選后期應(yīng)當(dāng)在什么地方展開(kāi)活動(dòng)——那里有很多爭(zhēng)取 對(duì)象

借助模型幫助奧巴馬籌集到創(chuàng)紀(jì)錄的10億美元

例如：利用模型分析出，明星喬治克魯尼（GeorgeClooney）對(duì)于年齡在40- 49歲的美西地區(qū)女性頗具吸引力，而她們恰是最愿意為和克魯尼/奧巴馬共 進(jìn)晚餐而掏錢(qián)的人……

喬治克魯尼為奧巴馬舉辦的競(jìng)選籌資晚宴成功募集 到1500萬(wàn)美元

……機(jī)器學(xué)習(xí)Chap01緒論導(dǎo)論課程專(zhuān)用學(xué)習(xí)2016南京大學(xué)機(jī)器所有權(quán)保留例如：幫助奧巴馬勝選（政治）

隊(duì)長(zhǎng)：RayidGhani

卡內(nèi)基梅隆大學(xué)機(jī)器學(xué)習(xí)系 首任系主任TomMitchell

教授的博士生

這個(gè)團(tuán)隊(duì)行動(dòng)保密，定期向奧巴馬報(bào)送結(jié)果； 被奧巴馬公開(kāi)稱(chēng)為總統(tǒng)競(jìng)選的“核武器按鈕”(“Theyareournuclearcodes”)機(jī)器學(xué)習(xí)Chap01緒論權(quán)專(zhuān)用所有2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程保留

約翰麥卡錫

(1927-2011)“人工智能之父”1971年圖靈獎(jiǎng)1956年夏美國(guó)達(dá)特茅斯學(xué)院J.McCarthy,M.Minsky,N.Lochester,C.E.Shannon,H.A.Simon,A.Newell,A.L.Samuel等10余人達(dá)特茅斯會(huì)議標(biāo)志著人工智能這一學(xué)科的誕生JohnMcCarthy(1927-2011): 1971年獲圖靈獎(jiǎng),1985年獲IJCAI終身成就獎(jiǎng)。人工智能之父。他提出了“人工智能”的概念，設(shè)計(jì)出函數(shù)型程序設(shè)計(jì)語(yǔ)言Lisp，發(fā)展了遞歸的概念，提出常識(shí)推理和情境演算。出生于共產(chǎn)黨家庭，從小閱讀《10萬(wàn)個(gè)為什么》，中學(xué)時(shí)自修CalTech的數(shù)學(xué)課程，17歲進(jìn)入CalTech時(shí)免修兩年數(shù)學(xué)，22歲在Princeton獲博士學(xué)位，37歲擔(dān)任Stanford大學(xué)AI實(shí)驗(yàn)室主任。機(jī)器學(xué)習(xí)源自“人工智能”

ArtificialIntelligence(AI),1956-機(jī)器學(xué)習(xí)Chap01緒論權(quán)程專(zhuān)用所有保16南京大20學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課留赫伯特西蒙

(1916-2001)1975年圖靈獎(jiǎng)第一階段：推理期

1956-1960s:LogicReasoning

出發(fā)點(diǎn):“數(shù)學(xué)家真聰明！”

主要成就:自動(dòng)定理證明系統(tǒng)(例如， 西蒙與紐厄爾的“LogicTheorist”

系統(tǒng))漸漸地，研究者們意識(shí)到，僅有邏輯推理能力是不夠的…

阿倫紐厄爾

(1927-1992) 1975年圖靈獎(jiǎng)機(jī)器學(xué)習(xí)Chap01緒論用所有權(quán)保留2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)

出發(fā)點(diǎn):“知識(shí)就是力量！”愛(ài)德華費(fèi)根鮑姆

(1936-)

1994年圖靈獎(jiǎng)

主要成就:專(zhuān)家系統(tǒng)(例如，費(fèi)根鮑 姆等人的“DENDRAL”系統(tǒng))

漸漸地，研究者們發(fā)現(xiàn)，要總結(jié)出知識(shí)再“教”給 系統(tǒng)，實(shí)在太難了…第二階段：知識(shí)期

1970s-1980s:KnowledgeEngineering機(jī)器學(xué)習(xí)Chap01緒論2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有權(quán)保留

出發(fā)點(diǎn):“讓系統(tǒng)自己學(xué)！”第三階段：學(xué)習(xí)期

1990s-now:MachineLearning

主要成就:……

機(jī)器學(xué)習(xí)是作為“突破知識(shí)工程瓶頸” 之利器而出現(xiàn)的恰好在20世紀(jì)90年代中后期，人類(lèi)發(fā)現(xiàn)自己淹沒(méi)在數(shù)據(jù)的汪洋中，對(duì)自動(dòng)數(shù)據(jù)分析技術(shù)——機(jī)器學(xué)習(xí)的需求日益迫切機(jī)器學(xué)習(xí)Chap01緒論權(quán)專(zhuān)用所有16南京大學(xué)機(jī)器學(xué)保習(xí)導(dǎo)論留課程20

汽車(chē)自動(dòng)駕駛(DARPAGrandChallenge)機(jī)器學(xué)習(xí)已經(jīng)“無(wú)處不在”

入侵檢測(cè)

Web搜索 生物信息學(xué) 決策助手(DARPA)火星機(jī)器人(JPL)機(jī)器學(xué)習(xí)Chap01緒論2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有權(quán)保留今天的“機(jī)器學(xué)習(xí)”已經(jīng)是一個(gè)廣袤的學(xué)科領(lǐng)域經(jīng)常被談到的“深度學(xué)習(xí)”

(DeepLearning)僅是

機(jī)器學(xué)習(xí)中的一個(gè)小分支 例如，這是第32屆 國(guó)際機(jī)器學(xué)習(xí)大會(huì) 的“主題領(lǐng)域”

2006年，美國(guó)CMU (卡內(nèi)基梅隆大學(xué))成立“機(jī)器學(xué)習(xí)系”機(jī)器學(xué)習(xí)Chap01緒論導(dǎo)論課程專(zhuān)用所2016南京大學(xué)機(jī)器學(xué)習(xí)有權(quán)保留大數(shù)據(jù)時(shí)代的關(guān)鍵技術(shù)奧巴馬提出“大數(shù)據(jù)計(jì)劃”后，美國(guó)NSF進(jìn)一步加強(qiáng)資助UCBerkeley研究如何整合將”數(shù)據(jù)”轉(zhuǎn)變?yōu)椤毙畔ⅰ钡娜箨P(guān)鍵技術(shù)——機(jī)器學(xué)習(xí)、云計(jì)算、眾包(crowdsourcing)整合三大關(guān)鍵技術(shù)機(jī)器學(xué)習(xí)Chap01緒論權(quán)保2016南京留大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有大數(shù)據(jù)時(shí)代，機(jī)器學(xué)習(xí)必不可少收集、傳輸、存儲(chǔ)大數(shù)據(jù)的目的，是為了“利用”大數(shù)據(jù)沒(méi)有機(jī)器學(xué)習(xí)技術(shù)分析大數(shù)據(jù)，“利用”無(wú)從談起機(jī)器學(xué)習(xí)Chap01緒論權(quán)有所習(xí)導(dǎo)論課程專(zhuān)用保2016南京大學(xué)機(jī)器學(xué)留基本術(shù)語(yǔ)???????數(shù)據(jù)集;訓(xùn)練,測(cè)試示例(instance),樣例(example)樣本(sample)屬性(attribute),特征(feature);屬性值屬性空間,樣本空間,輸入空間特征向量(featurevector)標(biāo)記空間,輸出空間??監(jiān)督學(xué)習(xí)(supervisedlearning)無(wú)監(jiān)督學(xué)習(xí)(unsupervisedlearning)???假設(shè)(hypothesis)真相(ground-truth)學(xué)習(xí)器(learner)????

?

分類(lèi),回歸

?

二分類(lèi),多分類(lèi)

?

正類(lèi),反類(lèi)未見(jiàn)樣本(unseeninstance)未知“分布”獨(dú)立同分布(i.i.d.)泛化(generalization)機(jī)器學(xué)習(xí)Chap01緒論權(quán)2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論課程專(zhuān)用所有保留假設(shè)空間(色澤=?)?(根蒂=?)?(敲聲=?)?好瓜學(xué)習(xí)過(guò)程

在所有假設(shè)(hypothesis)組成的空間中進(jìn)行搜索的過(guò)程目標(biāo):找到與訓(xùn)練集“匹配”(fit)的假設(shè)假設(shè)空間的大?。簄1xn2xn3+1機(jī)器學(xué)習(xí)Chap01緒論權(quán)用所有保留論課程專(zhuān)機(jī)器學(xué)習(xí)導(dǎo)2016南京大學(xué)例如:(青綠;蜷縮;沉悶)應(yīng)該采用哪一個(gè) 模型(假設(shè))?版本空間

版本空間(versionspace):與訓(xùn)練集一致的假設(shè)集合

濁響 濁響

在面臨新樣本時(shí)，會(huì)產(chǎn)生不同的輸出機(jī)器學(xué)習(xí)Chap01緒論課程專(zhuān)用所有2016南京大學(xué)機(jī)器學(xué)習(xí)導(dǎo)論權(quán)保留歸納偏好(inductivebias)機(jī)器學(xué)習(xí)算法在學(xué)習(xí)過(guò)程中對(duì)某種類(lèi)型假設(shè)的偏好A更好？B更好？一般原則：奧卡姆剃刀

(Oca