【機器學習】（4）：監督式學習

     機器學習中監督式學習是非常重要的一類，因為ML的主要出發點是利用獲得的數據來補償未知的知識，所以從訓練集出發學習數據中的模式規律就是最為自然的一類 情況。今天開始自己決定利用兩周左右的時間，來記錄整理自己學習機器學習的筆記，主要的參考資料是Ethen Alpaydin的《機器學習導論》，如有錯誤或疏漏，還請各位童鞋批評指正。今天主要來宏觀地談談監督學習，大致的要點如下：

1. 一個監督式學習實例；

2. 監督式學習算法的維；

3. 學習算法的能力--VC維；

4. 學習算法樣本量的確定--概率逼近；

      好了，長話短說，下面我們來介紹機器學習中的監督式學習。

一、一個監督式學習實例

      從一個例子著手是最為形象最為容易理解的，比如現在我們有一個判斷“家用汽車”的任務，具體根據汽車價格和發動機功率兩個特征進行判斷，實際中也許有更多 的因素，在這里為了簡單起見我們暫且只考慮這兩個特征。算法的任務是通過訓練集的學習，能夠對一個新的樣本進行判斷是否是“家用汽車”。我們可以將認為是 家用汽車的標記為正例（Positive Example），其他的都被標記為負例（Negative Example），類學習就是要找到一個包含所有正例但是不包含任何負例的描述。

      上面的公式描述了我們這個實例，向量x的兩個分量分別表示汽車價格和發動機的功率，而向量r則表示輸出，當為正例時輸出1，負例時輸出0；第一個集合表示N個樣本訓練集，每個元素都由樣本特征x和標準判斷r組成。我們現在的目標是可以找到一個算法，可以通過訓練集找到某個分類方法，適用于所有的訓練集（包含所有正例但是不包含任何負例），然后利用這個分類方法去預測判斷新的樣本。

      這里在具體實現的時候，人們往往首先要有一個假設類（Hypothesis class），比如可以采用一個矩形集合（假定位于某個價格區間且同時位于某個發動機功率區間的汽車為家用汽車，即一個判別式），來包含所有的正例，同時 卻不包含任何的負例。符合這樣條件的矩形可能有多個，因此存在一個最小的矩形，即最特殊的假設（most specific hypothesis），比如S，再小就會有一個正例不包含在假設中；同時也存在一個最一般的假設（most general hypothesis），比如G，再大的假設就會包含一個或多個負例。因此我們尋找的假設應該位于S與G之間。一般認為可以選在S與G的中間，因為這樣可 以獲得較大的邊緣（margin），所謂邊緣就是邊界和它最近的實例之間的距離。

      由于在S與G之間存在多個可用的假設，但是不同的假設對于新的樣本可能做出不同的預測和判斷，因此這便引出了泛化（generalization）的問題，即我們的假設對不在訓練集中的未來實例的分類的準確率如何。

二、監督式學習算法的維度

      監督式學習簡單來說就是通過訓練集讓計算機學習數據間的規律和模式，然后以此進行分類和回歸預測。訓練集的表示就如同上面的結合X， 其中樣本應當是獨立同分布的，對于分類而言，兩類學習輸出就是0和1，而K類學習就是一個K維向量，其中只有一個分量為1，其余分量均為0，這個要求也就 是說任何一樣本最多只能屬于一個類別。對于回歸而言，輸出是一個實數值。可以這樣簡單地來區分分類和回歸問題：分類輸出是離散值，而回歸輸出是連續值。下 面我們來看看監督式學習的維度， 也就是監督學習的基本步驟。

1. 確定假設類，比如假設了函數模型G(x,A)，A表示一個參數向量，而x表示我們的樣本輸入，我們通過訓練集學習確定最好的A，使得假設可以對新的樣本進行判斷；

2. 滿足訓練集的假設可能會有很多，因此我們要選擇最合適的那個，標準就是一個損失函數L（Loss Function），比如L是x與G(x, A)的平方差或者絕對值，用于表示我們的假設與訓練集的差異，我們尋求最小的那個。當然，損失函數還可以有其他的定義，但是基本思想都是用來表示假設與訓練集數據的差異；

3. 有了損失函數L，接下來我們就進入了最優化過程，即使得L最小，這一步有多種方法可以實現，比如將L對所有的特征分量求偏導數，確定極小值；或者使用梯度下降、模擬退火以及遺傳算法等。

      不同的機器學習方法的之間的區別，要么是假設類不同（假設模型或歸納偏倚），要么是所使用的損失函數不同，再者就是使用的最優化過程不同。可以說，假設模型、損失度量和最優化過程是機器學習的三個基本維度。

三、學習算法的能力--VC維

      學習算法的能力通過VC維度來度量，即一個假設類散列的數據點的個數。假定一個數據集中有N個數據點，對于正例和負例的判斷而言，就有2的N次方種不同的學習問題，如果對于這些學習問題中的任何一個都可以找到假設類H中的一個假設h可以將正例和負例分開，我們就稱該假設類H散列這N個點。因此VC維度量假設類的學習能力。

四、學習算法樣本量的確定--概率逼近

      概率逼近主要用于針對特定的假設類，確定最少需要多少樣本量就可以保證學習的結果獲得一定的置信率，其實也就是說如果我們想達到一個較好的假設，那么最少需要多大的訓練集呢？根據我們期望的置信率和不同的假設，我們可以計算其概率逼近的最小樣本量。

      好了，今天的基本概念就到這里，明天繼續！

Refer：

《機器學習導論》，Ethen Alpaydin（土耳其），機械工業出版社