筆記1 -- The Learning Problem

最近在看NTU林軒田的《機器學習基石》課程，個人感覺講的非常好轨奄。整個基石課程分成四個部分：

· When Can Machine Learn?

· Why Can Machine Learn?

· How Can Machine Learn?

· How Can Machine Learn Better?

每個部分由四節(jié)課組成，總共有16節(jié)課拒炎。那么挪拟，從這篇開始，我們將連續(xù)對這門課做課程筆記击你，共16篇玉组，希望能對正在看這們課的童鞋有所幫助。下面開始第一節(jié)課的筆記：The Learning Problem丁侄。

一惯雳、What is Machine Learning

什么是“學習”？學習就是人類通過觀察绒障、積累經(jīng)驗吨凑，掌握某項技能或能力。就好像我們從小學習識別字母户辱、認識漢字鸵钝，就是學習的過程。而機器學習（Machine Learning）庐镐，顧名思義恩商，就是讓機器（計算機）也能向人類一樣，通過觀察大量的數(shù)據(jù)和訓練必逆，發(fā)現(xiàn)事物規(guī)律怠堪，獲得某種分析問題、解決問題的能力名眉。

image.png

機器學習可以被定義為：Improving some performance measure with experence computed from data. 也就是機器從數(shù)據(jù)中總結(jié)經(jīng)驗粟矿，從數(shù)據(jù)中找出某種規(guī)律或者模型，并用它來解決實際問題损拢。

image.png

什么情況下會使用機器學習來解決問題呢陌粹？其實，目前機器學習的應用非常廣泛福压，基本上任何場合都能夠看到它的身影掏秩。其應用場合大致可歸納為三個條件：

· 事物本身存在某種潛在規(guī)律

· 某些問題難以使用普通編程解決

· 有大量的數(shù)據(jù)樣本可供使用

image.png

二、Applications of Machine Learning

機器學習在我們的衣荆姆、食蒙幻、住、行胆筒、教育邮破、娛樂等各個方面都有著廣泛的應用，我們的生活處處都離不開機器學習。比如决乎，打開購物網(wǎng)站队询，網(wǎng)站就會給我們自動推薦我們可能會喜歡的商品；電影頻道會根據(jù)用戶的瀏覽記錄和觀影記錄构诚，向不同用戶推薦他們可能喜歡的電影等等蚌斩，到處都有機器學習的影子。

三范嘱、Components of Machine Learning

本系列的課程對機器學習問題有一些基本的術語需要注意一下：

· 輸入x

· 輸出y

· 目標函數(shù)f送膳，即最接近實際樣本分布的規(guī)律

· 訓練樣本data

· 假設hypothesis，一個機器學習模型對應了很多不同的hypothesis丑蛤，通過演算法A叠聋，選擇一個最佳的hypothesis對應的函數(shù)稱為矩g，g能最好地表示事物的內(nèi)在規(guī)律受裹，也是我們最終想要得到的模型表達式碌补。

image.png

實際中，機器學習的流程圖可以表示為：

image.png

對于理想的目標函數(shù)f棉饶，我們是不知道的厦章，我們手上拿到的是一些訓練樣本D，假設是監(jiān)督式學習照藻，其中有輸入x袜啃，也有輸出y。機器學習的過程幸缕，就是根據(jù)先驗知識選擇模型群发，該模型對應的hypothesis set（用H表示），H中包含了許多不同的hypothesis发乔，通過演算法A熟妓，在訓練樣本D上進行訓練，選擇出一個最好的hypothes栏尚，對應的函數(shù)表達式g就是我們最終要求的起愈。一般情況下，g能最接近目標函數(shù)f抵栈，這樣，機器學習的整個流程就完成了坤次。

四古劲、Machine Learning and Other Fields

與機器學習相關的領域有：

· 數(shù)據(jù)挖掘（Data Mining）

· 人工智能（Artificial Intelligence）

· 統(tǒng)計（Statistics）

其實，機器學習與這三個領域是相通的缰猴，基本類似产艾，但也不完全一樣。機器學習是這三個領域中的有力工具，而同時闷堡，這三個領域也是機器學習可以廣泛應用的領域隘膘，總得來說，他們之間沒有十分明確的界線杠览。

五弯菊、總結(jié)

本節(jié)課主要介紹了什么是機器學習，什么樣的場合下可以使用機器學習解決問題踱阿，然后用流程圖的形式展示了機器學習的整個過程管钳，最后把機器學習和數(shù)據(jù)挖掘、人工智能软舌、統(tǒng)計這三個領域做個比較才漆。本節(jié)課的內(nèi)容主要是概述性的東西，比較簡單佛点，所以筆記也相對比較簡略醇滥。

筆記2 -- Learning to Answer Yes/No

上節(jié)課，我們主要簡述了機器學習的定義及其重要性超营，并用流程圖的形式介紹了機器學習的整個過程：根據(jù)模型H鸳玩，使用演算法A，在訓練樣本D上進行訓練糟描，得到最好的h怀喉，其對應的g就是我們最后需要的機器學習的模型函數(shù)，一般g接近于目標函數(shù)f船响。本節(jié)課將繼續(xù)深入探討機器學習問題躬拢，介紹感知機Perceptron模型，并推導課程的第一個機器學習算法：Perceptron Learning Algorithm（PLA）见间。

一聊闯、Perceptron Hypothesis Set

引入這樣一個例子：某銀行要根據(jù)用戶的年齡、性別米诉、年收入等情況來判斷是否給該用戶發(fā)信用卡×馐撸現(xiàn)在有訓練樣本D，即之前用戶的信息和是否發(fā)了信用卡史侣。這是一個典型的機器學習問題拴泌，我們要根據(jù)D，通過A惊橱，在H中選擇最好的h蚪腐，得到g，接近目標函數(shù)f税朴，也就是根據(jù)先驗知識建立是否給用戶發(fā)信用卡的模型回季。銀行用這個模型對以后用戶進行判斷：發(fā)信用卡（+1）家制，不發(fā)信用卡（-1）。

在這個機器學習的整個流程中泡一，有一個部分非常重要：就是模型選擇颤殴，即Hypothesis Set。選擇什么樣的模型鼻忠，很大程度上會影響機器學習的效果和表現(xiàn)涵但。下面介紹一個簡單常用的Hypothesis Set：感知機（Perceptron）。

還是剛才銀行是否給用戶發(fā)信用卡的例子粥烁，我們把用戶的個人信息作為特征向量x贤笆，令總共有d個特征，每個特征賦予不同的權(quán)重w讨阻，表示該特征對輸出（是否發(fā)信用卡）的影響有多大芥永。那所有特征的加權(quán)和的值與一個設定的閾值threshold進行比較：大于這個閾值，輸出為+1钝吮，即發(fā)信用卡埋涧；小于這個閾值，輸出為-1奇瘦，即不發(fā)信用卡棘催。感知機模型，就是當特征加權(quán)和與閾值的差大于或等于0耳标，則輸出h(x)=1醇坝；當特征加權(quán)和與閾值的差小于0，則輸出h(x)=-1次坡，而我們的目的就是計算出所有權(quán)值w和閾值threshold呼猪。

image.png

為了計算方便，通常我們將閾值threshold當做w0w0砸琅，引入一個x0=1x0=1的量與w0w0相乘宋距，這樣就把threshold也轉(zhuǎn)變成了權(quán)值w0w0，簡化了計算症脂。h(x)的表達式做如下變換：

image.png

為了更清晰地說明感知機模型谚赎，我們假設Perceptrons在二維平面上，即h(x)=sign(w0+w1x1+w2x2)h(x)=sign(w0+w1x1+w2x2)诱篷。其中壶唤，w0+w1x1+w2x2=0w0+w1x1+w2x2=0是平面上一條分類直線，直線一側(cè)是正類（+1）棕所，直線另一側(cè)是負類（-1）闸盔。權(quán)重w不同，對應于平面上不同的直線橙凳。

image.png

那么蕾殴，我們所說的Perceptron，在這個模型上就是一條直線岛啸，稱之為linear(binary) classifiers钓觉。注意一下，感知器線性分類不限定在二維空間中坚踩，在3D中荡灾，線性分類用平面表示，在更高維度中瞬铸，線性分類用超平面表示批幌，即只要是形如wTxwTx的線性模型就都屬于linear(binary) classifiers。

同時嗓节，需要注意的是荧缘，這里所說的linear(binary) classifiers是用簡單的感知器模型建立的，線性分類問題還可以使用logistic regression來解決拦宣，后面將會介紹截粗。

二、Perceptron Learning Algorithm(PLA)

根據(jù)上一部分的介紹鸵隧，我們已經(jīng)知道了hypothesis set由許多條直線構(gòu)成绸罗。接下來，我們的目的就是如何設計一個演算法A豆瘫，來選擇一個最好的直線珊蟀，能將平面上所有的正類和負類完全分開，也就是找到最好的g外驱，使g≈fg≈f育灸。

如何找到這樣一條最好的直線呢？我們可以使用逐點修正的思想略步，首先在平面上隨意取一條直線描扯，看看哪些點分類錯誤。然后開始對第一個錯誤點就行修正趟薄，即變換直線的位置绽诚，使這個錯誤點變成分類正確的點。接著杭煎，再對第二個恩够、第三個等所有的錯誤分類點就行直線糾正，直到所有的點都完全分類正確了羡铲，就得到了最好的直線蜂桶。這種“逐步修正”，就是PLA思想所在也切。

image.png

下面介紹一下PLA是怎么做的扑媚。首先隨機選擇一條直線進行分類腰湾。然后找到第一個分類錯誤的點，如果這個點表示正類疆股，被誤分為負類费坊，即wTtxn(t)<0wtTxn(t)<0，那表示w和x夾角大于90度旬痹，其中w是直線的法向量附井。所以，x被誤分在直線的下側(cè)（相對于法向量两残，法向量的方向即為正類所在的一側(cè)）永毅，修正的方法就是使w和x夾角小于90度。通常做法是w←w+yx, y=1w←w+yx, y=1人弓，如圖右上角所示沼死，一次或多次更新后的w+yxw+yx與x夾角小于90度，能保證x位于直線的上側(cè)崔赌，則對誤分為負類的錯誤點完成了直線修正漫雕。

同理，如果是誤分為正類的點峰鄙，即wTtxn(t)>0wtTxn(t)>0浸间，那表示w和x夾角小于90度，其中w是直線的法向量吟榴。所以魁蒜，x被誤分在直線的上側(cè)，修正的方法就是使w和x夾角大于90度吩翻。通常做法是w←w+yx, y=?1w←w+yx, y=?1兜看，如圖右下角所示，一次或多次更新后的w+yxw+yx與x夾角大于90度狭瞎，能保證x位于直線的下側(cè)细移，則對誤分為正類的錯誤點也完成了直線修正。

按照這種思想熊锭，遇到個錯誤點就進行修正弧轧，不斷迭代。要注意一點：每次修正直線碗殷，可能使之前分類正確的點變成錯誤點精绎，這是可能發(fā)生的。但是沒關系锌妻，不斷迭代代乃，不斷修正，最終會將所有點完全正確分類（PLA前提是線性可分的）仿粹。這種做法的思想是“知錯能改”搁吓，有句話形容它：“A fault confessed is half redressed.”

實際操作中原茅，可以一個點一個點地遍歷，發(fā)現(xiàn)分類錯誤的點就進行修正堕仔，直到所有點全部分類正確员咽。這種被稱為Cyclic PLA。

image.png

下面用圖解的形式來介紹PLA的修正過程：

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

對PLA贮预，我們需要考慮以下兩個問題：

· PLA迭代一定會停下來嗎？如果線性不可分怎么辦契讲？

· PLA停下來的時候仿吞，是否能保證f≈gf≈g？如果沒有停下來捡偏，是否有f≈gf≈g唤冈？

三、Guarantee of PLA

PLA什么時候會停下來呢银伟？根據(jù)PLA的定義你虹，當找到一條直線，能將所有平面上的點都分類正確彤避，那么PLA就停止了傅物。要達到這個終止條件，就必須保證D是線性可分（linear separable）琉预。如果是非線性可分的董饰，那么，PLA就不會停止圆米。

image.png

對于線性可分的情況卒暂，如果有這樣一條直線，能夠?qū)⒄惡拓擃愅耆珠_娄帖，令這時候的目標權(quán)重為wfwf也祠，則對每個點，必然滿足yn=sign(wTfxn)yn=sign(wfTxn)近速，即對任一點：

image.png

PLA會對每次錯誤的點進行修正诈嘿，更新權(quán)重wt+1wt+1的值，如果wt+1wt+1與wfwf越來越接近削葱，數(shù)學運算上就是內(nèi)積越大永淌，那表示wt+1wt+1是在接近目標權(quán)重wfwf，證明PLA是有學習效果的佩耳。所以遂蛀，我們來計算wt+1wt+1與wfwf的內(nèi)積：

image.png

從推導可以看出，wt+1wt+1與wfwf的內(nèi)積跟wtwt與wfwf的內(nèi)積相比更大了干厚。似乎說明了wt+1wt+1更接近wfwf李滴，但是內(nèi)積更大螃宙，可能是向量長度更大了，不一定是向量間角度更小所坯。所以谆扎，下一步，我們還需要證明wt+1wt+1與wtwt向量長度的關系：

image.png

wtwt只會在分類錯誤的情況下更新芹助，最終得到的||w2t+1||||wt+12||相比||w2t||||wt2||的增量值不超過max||x2n||max||xn2||堂湖。也就是說，wtwt的增長被限制了状土，wt+1wt+1與wtwt向量長度不會差別太大无蜂！

如果令初始權(quán)值w0=0w0=0，那么經(jīng)過T次錯誤修正后蒙谓，有如下結(jié)論：

wTf||wf||wTwT≥T??√?constantwfT||wf||wTwT≥T?constant

下面貼出來該結(jié)論的具體推導過程：

image.png

image.png

上述不等式左邊其實是wTwT與wfwf夾角的余弦值斥季，隨著T增大，該余弦值越來越接近1累驮，即wTwT與wfwf越來越接近酣倾。同時，需要注意的是谤专，T??√?constant≤1T?constant≤1躁锡，也就是說，迭代次數(shù)T是有上界的置侍。根據(jù)以上證明稚铣，我們最終得到的結(jié)論是：wt+1wt+1與wfwf的是隨著迭代次數(shù)增加，逐漸接近的墅垮。而且惕医，PLA最終會停下來（因為T有上界），實現(xiàn)對線性可分的數(shù)據(jù)集完全分類算色。

四抬伺、Non-Separable Data

上一部分，我們證明了線性可分的情況下灾梦，PLA是可以停下來并正確分類的峡钓，但對于非線性可分的情況，wfwf實際上并不存在若河，那么之前的推導并不成立能岩，PLA不一定會停下來。所以萧福，PLA雖然實現(xiàn)簡單省核，但也有缺點：

image.png

對于非線性可分的情況综液，我們可以把它當成是數(shù)據(jù)集D中摻雜了一下noise嫂拴，事實上暖途，大多數(shù)情況下我們遇到的D宦赠，都或多或少地摻雜了noise。這時，機器學習流程是這樣的：

image.png

在非線性情況下，我們可以把條件放松篷就，即不苛求每個點都分類正確，而是容忍有錯誤點近忙，取錯誤點的個數(shù)最少時的權(quán)重w：

image.png

事實證明竭业，上面的解是NP-hard問題，難以求解及舍。然而未辆，我們可以對在線性可分類型中表現(xiàn)很好的PLA做個修改，把它應用到非線性可分類型中击纬，獲得近似最好的g。

修改后的PLA稱為Packet Algorithm钾麸。它的算法流程與PLA基本類似更振，首先初始化權(quán)重w0w0，計算出在這條初始化的直線中饭尝，分類錯誤點的個數(shù)肯腕。然后對錯誤點進行修正，更新w钥平，得到一條新的直線实撒，在計算其對應的分類錯誤的點的個數(shù)，并與之前錯誤點個數(shù)比較涉瘾，取個數(shù)較小的直線作為我們當前選擇的分類直線知态。之后，再經(jīng)過n次迭代立叛，不斷比較當前分類錯誤點個數(shù)與之前最少的錯誤點個數(shù)比較负敏，選擇最小的值保存。直到迭代次數(shù)完成后秘蛇，選取個數(shù)最少的直線對應的w其做，即為我們最終想要得到的權(quán)重值。

image.png

如何判斷數(shù)據(jù)集D是不是線性可分赁还？對于二維數(shù)據(jù)來說妖泄，通常還是通過肉眼觀察來判斷的。一般情況下艘策，Pocket Algorithm要比PLA速度慢一些蹈胡。

五、總結(jié)

本節(jié)課主要介紹了線性感知機模型，以及解決這類感知機分類問題的簡單算法：PLA审残。我們詳細證明了對于線性可分問題梭域，PLA可以停下來并實現(xiàn)完全正確分類。對于不是線性可分的問題搅轿，可以使用PLA的修正算法Pocket Algorithm來解決病涨。

筆記3 -- Types of Learning

上節(jié)課我們主要介紹了解決線性分類問題的一個簡單的方法：PLA。PLA能夠在平面中選擇一條直線將樣本數(shù)據(jù)完全正確分類璧坟。而對于線性不可分的情況既穆，可以使用Pocket Algorithm來處理。本節(jié)課將主要介紹一下機器學習有哪些種類雀鹃，并進行歸納幻工。

一、****Learning with Different Output Space Y

我們在上節(jié)課引入的銀行根據(jù)用戶個人情況判斷是否給他發(fā)信用卡的例子黎茎，這是一個典型的二元分類（binary classification）問題囊颅。也就是說輸出只有兩個，一般y={-1, +1}傅瞻，-1代表不發(fā)信用卡（負類）踢代，+1代表發(fā)信用卡（正類）。

二元分類的問題很常見嗅骄，包括信用卡發(fā)放胳挎、垃圾郵件判別、患者疾病診斷溺森、答案正確性估計等等慕爬。二元分類是機器學習領域非常核心和基本的問題。二元分類有線性模型也有非線性模型屏积，根據(jù)實際問題情況医窿，選擇不同的模型。

image.png

除了二元分類炊林，也有多元分類（Multiclass Classification）問題留搔。顧名思義，多元分類的輸出多于兩個铛铁，y={1, 2, … , K}, K>2. 一般多元分類的應用有數(shù)字識別隔显、圖片內(nèi)容識別等等。

image.png

二元分類和多元分類都屬于分類問題饵逐，它們的輸出都是離散值括眠。二對于另外一種情況，比如訓練模型倍权，預測房屋價格掷豺、股票收益多少等捞烟，這類問題的輸出y=R，即范圍在整個實數(shù)空間当船，是連續(xù)的题画。這類問題，我們把它叫做回歸（Regression）德频。最簡單的線性回歸是一種典型的回歸模型苍息。

除了分類和回歸問題，在自然語言處理等領域中壹置，還會用到一種機器學習問題：結(jié)構(gòu)化學習（Structured Learning）竞思。結(jié)構(gòu)化學習的輸出空間包含了某種結(jié)構(gòu)在里面，它的一些解法通常是從多分類問題延伸而來的钞护，比較復雜盖喷。本系列課程不會詳細介紹Structured Learning，有興趣的讀者可以自行對它進行更深入的研究难咕。

簡單總結(jié)一下课梳，機器學習按照輸出空間劃分的話，包括二元分類余佃、多元分類暮刃、回歸、結(jié)構(gòu)化學習等不同的類型咙冗。其中二元分類和回歸是最基礎沾歪、最核心的兩個類型漂彤，也是我們課程主要介紹的部分雾消。

image.png

二、****Learning with Different Data Label yn

如果我們拿到的訓練樣本D既有輸入特征x挫望，也有輸出yn立润，那么我們把這種類型的學習稱為監(jiān)督式學習（Supervised Learning）。監(jiān)督式學習可以是二元分類媳板、多元分類或者是回歸桑腮，最重要的是知道輸出標簽yn。與監(jiān)督式學習相對立的另一種類型是非監(jiān)督式學習（Unsupervised learning）蛉幸。非監(jiān)督式學習是沒有輸出標簽yn的破讨，典型的非監(jiān)督式學習包括：聚類（clustering）問題，比如對網(wǎng)頁上新聞的自動分類奕纫；密度估計提陶，比如交通路況分析；異常檢測匹层，比如用戶網(wǎng)絡流量監(jiān)測隙笆。通常情況下，非監(jiān)督式學習更復雜一些，而且非監(jiān)督的問題很多都可以使用監(jiān)督式學習的一些算法思想來實現(xiàn)撑柔。

image.png

介于監(jiān)督式和非監(jiān)督式學習之間的叫做半監(jiān)督式學習（Semi-supervised Learning）瘸爽。顧名思義，半監(jiān)督式學習就是說一部分數(shù)據(jù)有輸出標簽yn铅忿，而另一部分數(shù)據(jù)沒有輸出標簽yn剪决。在實際應用中，半監(jiān)督式學習有時候是必須的辆沦，比如醫(yī)藥公司對某些藥物進行檢測昼捍，考慮到成本和實驗人群限制等問題，只有一部分數(shù)據(jù)有輸出標簽yn肢扯。

監(jiān)督式妒茬、非監(jiān)督式、半監(jiān)督式學習是機器學習領域三個主要類型蔚晨。除此之外乍钻，還有一種非常重要的類型：增強學習（Reinforcement Learning）。增強學習中铭腕，我們給模型或系統(tǒng)一些輸入银择，但是給不了我們希望的真實的輸出y，根據(jù)模型的輸出反饋累舷，如果反饋結(jié)果良好浩考，更接近真實輸出，就給其正向激勵被盈，如果反饋結(jié)果不好析孽，偏離真實輸出，就給其反向激勵只怎。不斷通過“反饋-修正”這種形式袜瞬，一步一步讓模型學習的更好，這就是增強學習的核心所在身堡。增強學習可以類比成訓練寵物的過程邓尤，比如我們要訓練狗狗坐下，但是狗狗無法直接聽懂我們的指令“sit down”贴谎。在訓練過程中汞扎，我們給狗狗示意，如果它表現(xiàn)得好擅这，我們就給他獎勵澈魄，如果它做跟sit down完全無關的動作，我們就給它小小的懲罰蕾哟。這樣不斷修正狗狗的動作一忱，最終能讓它按照我們的指令來行動莲蜘。實際生活中，增強學習的例子也很多帘营，比如根據(jù)用戶點擊票渠、選擇而不斷改進的廣告系統(tǒng)

簡單總結(jié)一下，機器學習按照數(shù)據(jù)輸出標簽yn劃分的話芬迄，包括監(jiān)督式學習问顷、非監(jiān)督式學習、半監(jiān)督式學習和增強學習等禀梳。其中杜窄，監(jiān)督式學習應用最為廣泛。

image.png

三算途、****Learning with Different Protocol f(xn,yn)

按照不同的協(xié)議塞耕，機器學習可以分為三種類型：

· Batch Learning

· Online

· Active Learning

batch learning是一種常見的類型。batch learning獲得的訓練數(shù)據(jù)D是一批的嘴瓤，即一次性拿到整個D扫外，對其進行學習建模，得到我們最終的機器學習模型廓脆。batch learning在實際應用中最為廣泛筛谚。

online是一種在線學習模型，數(shù)據(jù)是實時更新的停忿，根據(jù)數(shù)據(jù)一個個進來驾讲，同步更新我們的算法。比如在線郵件過濾系統(tǒng)席赂，根據(jù)一封一封郵件的內(nèi)容吮铭，根據(jù)當前算法判斷是否為垃圾郵件，再根據(jù)用戶反饋氧枣，及時更新當前算法沐兵。這是一個動態(tài)的過程别垮。之前我們介紹的PLA和增強學習都可以使用online模型便监。

active learning是近些年來新出現(xiàn)的一種機器學習類型，即讓機器具備主動問問題的能力碳想，例如手寫數(shù)字識別烧董，機器自己生成一個數(shù)字或者對它不確定的手寫字主動提問。active learning優(yōu)勢之一是在獲取樣本label比較困難的時候胧奔，可以節(jié)約時間和成本逊移，只對一些重要的label提出需求。

簡單總結(jié)一下龙填，按照不同的協(xié)議胳泉，機器學習可以分為batch, online, active拐叉。這三種學習類型分別可以類比為：填鴨式，老師教學以及主動問問題扇商。

image.png

四凤瘦、****Learning with Different Input Space X

上面幾部分介紹的機器學習分類都是根據(jù)輸出來分類的，比如根據(jù)輸出空間進行分類案铺，根據(jù)輸出y的標記進行分類蔬芥，根據(jù)取得數(shù)據(jù)和標記的方法進行分類。這部分控汉，我們將談談輸入X有哪些類型笔诵。

輸入X的第一種類型就是concrete features。比如說硬幣分類問題中硬幣的尺寸姑子、重量等乎婿；比如疾病診斷中的病人信息等具體特征。concrete features對機器學習來說最容易理解和使用街佑。

第二種類型是raw features次酌。比如說手寫數(shù)字識別中每個數(shù)字所在圖片的mxn維像素值；比如語音信號的頻譜等舆乔。raw features一般比較抽象岳服，經(jīng)常需要人或者機器來轉(zhuǎn)換為其對應的concrete features，這個轉(zhuǎn)換的過程就是Feature Transform希俩。

第三種類型是abstract features吊宋。比如某購物網(wǎng)站做購買預測時，提供給參賽者的是抽象加密過的資料編號或者ID颜武，這些特征X完全是抽象的璃搜，沒有實際的物理含義。所以對于機器學習來說是比較困難的鳞上，需要對特征進行更多的轉(zhuǎn)換和提取这吻。

簡單總結(jié)一下，根據(jù)輸入X類型不同篙议，可以分為concetet, raw, abstract唾糯。將一些抽象的特征轉(zhuǎn)換為具體的特征，是機器學習過程中非常重要的一個環(huán)節(jié)鬼贱。在《機器學習技法》課程中移怯，我們再詳細介紹。

image.png

五这难、總結(jié)：

本節(jié)課主要介紹了機器學習的類型舟误，包括Out Space、Data Label姻乓、Protocol嵌溢、Input Space四種類型眯牧。

image.png

筆記4 -- Feasibility of Learning

上節(jié)課，我們主要介紹了根據(jù)不同的設定赖草，機器學習可以分為不同的類型炸站。其中，監(jiān)督式學習中的二元分類和回歸分析是最常見的也是最重要的機器學習問題疚顷。本節(jié)課旱易，我們將介紹機器學習的可行性，討論問題是否可以使用機器學習來解決腿堤。

一阀坏、****Learning is Impossible

首先，考慮這樣一個例子笆檀，如下圖所示忌堂，有3個label為-1的九宮格和3個label為+1的九宮格。根據(jù)這6個樣本酗洒，提取相應label下的特征士修，預測右邊九宮格是屬于-1還是+1？結(jié)果是樱衷，如果依據(jù)對稱性棋嘲，我們會把它歸為+1；如果依據(jù)九宮格左上角是否是黑色矩桂，我們會把它歸為-1沸移。除此之外，還有根據(jù)其它不同特征進行分類侄榴，得到不同結(jié)果的情況雹锣。而且，這些分類結(jié)果貌似都是正確合理的癞蚕，因為對于6個訓練樣本來說蕊爵，我們選擇的模型都有很好的分類效果。

image.png

再來看一個比較數(shù)學化的二分類例子桦山，輸入特征x是二進制的攒射、三維的，對應有8種輸入度苔，其中訓練樣本D有5個匆篓。那么浑度，根據(jù)訓練樣本對應的輸出y寇窑，假設有8個hypothesis，這8個hypothesis在D上箩张，對5個訓練樣本的分類效果效果都完全正確甩骏。但是在另外3個測試數(shù)據(jù)上窗市，不同的hypothesis表現(xiàn)有好有壞。在已知數(shù)據(jù)D上饮笛，g≈fg≈f咨察；但是在D以外的未知數(shù)據(jù)上，g≈fg≈f不一定成立福青。而機器學習目的摄狱，恰恰是希望我們選擇的模型能在未知數(shù)據(jù)上的預測與真實結(jié)果是一致的，而不是在已知的數(shù)據(jù)集D上尋求最佳效果无午。

image.png

這個例子告訴我們媒役，我們想要在D以外的數(shù)據(jù)中更接近目標函數(shù)似乎是做不到的，只能保證對D有很好的分類結(jié)果宪迟。機器學習的這種特性被稱為沒有免費午餐（No Free Lunch）定理酣衷。NFL定理表明沒有一個學習算法可以在任何領域總是產(chǎn)生最準確的學習器。不管采用何種學習算法次泽，至少存在一個目標函數(shù)穿仪，能夠使得隨機猜測算法是更好的算法。平常所說的一個學習算法比另一個算法更“優(yōu)越”意荤，效果更好啊片，只是針對特定的問題，特定的先驗信息玖像，數(shù)據(jù)的分布钠龙，訓練樣本的數(shù)目，代價或獎勵函數(shù)等御铃。從這個例子來看碴里，NFL說明了無法保證一個機器學習算法在D以外的數(shù)據(jù)集上一定能分類或預測正確，除非加上一些假設條件上真，我們以后會介紹咬腋。

二、Probability to the Rescue

從上一節(jié)得出的結(jié)論是：在訓練集D以外的樣本上睡互，機器學習的模型是很難根竿，似乎做不到正確預測或分類的。那是否有一些工具或者方法能夠?qū)ξ粗哪繕撕瘮?shù)f做一些推論就珠，讓我們的機器學習模型能夠變得有用呢寇壳？

如果有一個裝有很多（數(shù)量很大數(shù)不過來）橙色球和綠色球的罐子，我們能不能推斷橙色球的比例u妻怎？統(tǒng)計學上的做法是壳炎，從罐子中隨機取出N個球，作為樣本逼侦，計算這N個球中橙色球的比例v匿辩，那么就估計出罐子中橙色球的比例約為v腰耙。

image.png

這種隨機抽取的做法能否說明罐子里橙色球的比例一定是v呢？答案是否定的铲球。但是從概率的角度來說挺庞，樣本中的v很有可能接近我們未知的u。下面從數(shù)學推導的角度來看v與u是否相近稼病。

已知u是罐子里橙色球的比例选侨，v是N個抽取的樣本中橙色球的比例。當N足夠大的時候然走，v接近于u侵俗。這就是Hoeffding’s inequality：

P[|v?u|>?]≤2exp(?2?2N)P[|v?u|>?]≤2exp(?2?2N)

Hoeffding不等式說明當N很大的時候，v與u相差不會很大丰刊，它們之間的差值被限定在??之內(nèi)隘谣。我們把結(jié)論v=u稱為probably approximately correct(PAC)。

image.png

三啄巧、Connection to Learning

下面寻歧，我們將罐子的內(nèi)容對應到機器學習的概念上來。機器學習中hypothesis與目標函數(shù)相等的可能性秩仆，類比于罐子中橙色球的概率問題码泛；罐子里的一顆顆彈珠類比于機器學習樣本空間的x；橙色的彈珠類比于h(x)與f不相等澄耍；綠色的彈珠類比于h(x)與f相等噪珊；從罐子中抽取的N個球類比于機器學習的訓練樣本D，且這兩種抽樣的樣本與總體樣本之間都是獨立同分布的齐莲。所以呢痢站，如果樣本N夠大，且是獨立同分布的选酗，那么阵难，從樣本中h(x)≠f(x)h(x)≠f(x)的概率就能推導在抽樣樣本外的所有樣本中h(x)≠f(x)h(x)≠f(x)的概率是多少。

image.png

映射中最關鍵的點是講抽樣中橙球的概率理解為樣本數(shù)據(jù)集D上h(x)錯誤的概率芒填，以此推算出在所有數(shù)據(jù)上h(x)錯誤的概率呜叫，這也是機器學習能夠工作的本質(zhì)，即我們?yōu)樯对诓蓸訑?shù)據(jù)上得到了一個假設殿衰，就可以推到全局呢朱庆？因為兩者的錯誤率是PAC的，只要我們保證前者小闷祥，后者也就小了娱颊。

image.png

這里我們引入兩個值Ein(h)Ein(h)和Eout(h)Eout(h)。Ein(h)Ein(h)表示在抽樣樣本中，h(x)與ynyn不相等的概率维蒙；Eout(h)Eout(h)表示實際所有樣本中掰吕，h(x)與f(x)不相等的概率是多少果覆。

image.png

同樣颅痊，它的Hoeffding’s inequality可以表示為：

P[|Ein(h)?Eout(h)|>?]≤2exp(?2?2N)P[|Ein(h)?Eout(h)|>?]≤2exp(?2?2N)

該不等式表明，Ein(h)=Eout(h)Ein(h)=Eout(h)也是PAC的局待。如果Ein(h)≈Eout(h)Ein(h)≈Eout(h)斑响，Ein(h)Ein(h)很小，那么就能推斷出Eout(h)Eout(h)很小钳榨，也就是說在該數(shù)據(jù)分布P下舰罚，h與f非常接近，機器學習的模型比較準確薛耻。

一般地营罢，h如果是固定的，N很大的時候饼齿，Ein(h)≈Eout(h)Ein(h)≈Eout(h)饲漾，但是并不意味著g≈fg≈f。因為h是固定的缕溉，不能保證Ein(h)Ein(h)足夠小，即使Ein(h)≈Eout(h)Ein(h)≈Eout(h)，也可能使Eout(h)Eout(h)偏大喇勋。所以娶眷，一般會通過演算法A，選擇最好的h枉层，使Ein(h)Ein(h)足夠小泉褐，從而保證Eout(h)Eout(h)很小。固定的h鸟蜡，使用新數(shù)據(jù)進行測試兴枯，驗證其錯誤率是多少。

image.png

四矩欠、****Connection to Real Learning

image.png

假設現(xiàn)在有很多罐子M個（即有M個hypothesis）财剖，如果其中某個罐子抽樣的球全是綠色，那是不是應該選擇這個罐子呢癌淮？我們先來看這樣一個例子：150個人拋硬幣躺坟，那么其中至少有一個人連續(xù)5次硬幣都是正面朝上的概率是

1?(3132)150>99%1?(3132)150>99%

可見這個概率是很大的，但是能否說明5次正面朝上的這個硬幣具有代表性呢乳蓄？答案是否定的咪橙！并不能說明該硬幣單次正面朝上的概率很大，其實都是0.5。一樣的道理美侦，抽到全是綠色求的時候也不能一定說明那個罐子就全是綠色球产舞。當罐子數(shù)目很多或者拋硬幣的人數(shù)很多的時候，可能引發(fā)Bad Sample菠剩，Bad Sample就是EinEin和EoutEout差別很大易猫，即選擇過多帶來的負面影響，選擇過多會惡化不好的情形具壮。

根據(jù)許多次抽樣的到的不同的數(shù)據(jù)集D准颓，Hoeffding’s inequality保證了大多數(shù)的D都是比較好的情形（即對于某個h，保證Ein≈EoutEin≈Eout）棺妓，但是也有可能出現(xiàn)Bad Data攘已，即EinEin和EoutEout差別很大的數(shù)據(jù)集D，這是小概率事件怜跑。

image.png

也就是說样勃，不同的數(shù)據(jù)集DnDn，對于不同的hypothesis性芬，有可能成為Bad Data峡眶。只要DnDn在某個hypothesis上是Bad Data，那么DnDn就是Bad Data批旺。只有當DnDn在所有的hypothesis上都是好的數(shù)據(jù)幌陕，才說明DnDn不是Bad Data，可以自由選擇演算法A進行建模汽煮。那么搏熄，根據(jù)Hoeffding’s inequality，Bad Data的上界可以表示為連級（union bound）的形式：

image.png

其中暇赤，M是hypothesis的個數(shù)心例，N是樣本D的數(shù)量，??是參數(shù)鞋囊。該union bound表明止后，當M有限，且N足夠大的時候溜腐，Bad Data出現(xiàn)的概率就更低了译株，即能保證D對于所有的h都有Ein≈EoutEin≈Eout，滿足PAC挺益，演算法A的選擇不受限制歉糜。那么滿足這種union bound的情況，我們就可以和之前一樣望众，選取一個合理的演算法（PLA/pocket）匪补，選擇使EinEin最小的hmhm作為矩g伞辛，一般能夠保證g≈fg≈f，即有不錯的泛化能力夯缺。

所以蚤氏，如果hypothesis的個數(shù)M是有限的，N足夠大踊兜，那么通過演算法A任意選擇一個矩g竿滨，都有Ein≈EoutEin≈Eout成立；同時润文，如果找到一個矩g姐呐，使Ein≈0Ein≈0殿怜，PAC就能保證Eout≈0Eout≈0典蝌。至此，就證明了機器學習是可行的头谜。

image.png

但是骏掀，如上面的學習流程圖右下角所示，如果M是無數(shù)個柱告，例如之前介紹的PLA直線有無數(shù)條截驮，是否這些推論就不成立了呢？是否機器就不能進行學習呢际度？這些內(nèi)容和問題葵袭，我們下節(jié)課再介紹。

五乖菱、總結(jié)

本節(jié)課主要介紹了機器學習的可行性坡锡。首先引入NFL定理，說明機器學習無法找到一個矩g能夠完全和目標函數(shù)f一樣窒所。接著介紹了可以采用一些統(tǒng)計上的假設鹉勒，例如Hoeffding不等式，建立EinEin和EoutEout的聯(lián)系吵取，證明對于某個h禽额，當N足夠大的時候，EinEin和EoutEout是PAC的皮官。最后脯倒，對于h個數(shù)很多的情況，只要有h個數(shù)M是有限的捺氢，且N足夠大藻丢，就能保證Ein≈EoutEin≈Eout，證明機器學習是可行的讯沈。