# 8 -- Noise and Error
上一節課,我們主要介紹了VC Dimension的概念。如果Hypotheses set的VC Dimension是有限的,且有足夠多N的資料,同時能夠找到一個hypothesis使它的,那么就能說明機器學習是可行的。本節課主要講了數據集有Noise的情況下,是否能夠進行機器學習,并且介紹了假設空間H下演算法A的Error估計。
### **一、Noise and Probablistic target**
上節課推導VC Dimension的數據集是在沒有Noise的情況下,本節課討論如果數據集本身存在Noise,那VC Dimension的推導是否還成立呢?
首先,Data Sets的Noise一般有三種情況:
* **由于人為因素,正類被誤分為負類,或者負類被誤分為正類;**
* **同樣特征的樣本被模型分為不同的類;**
* **樣本的特征被錯誤記錄和使用。**

之前的數據集是確定的,即沒有Noise的,我們稱之為Deterministic。現在有Noise了,也就是說在某點處不再是確定分布,而是概率分布了,即對每個(x,y)出現的概率是。
因為Noise的存在,比如在x點,有0.7的概率y=1,有0.3的概率y=0,即y是按照分布的。數學上可以證明如果數據集按照概率分布且是iid的,那么以前證明機器可以學習的方法依然奏效,VC Dimension有限即可推斷和是近似的。

稱之為目標分布(Target Distribution)。它實際上告訴我們最好的選擇是什么,同時伴隨著多少noise。其實,沒有noise的數據仍然可以看成“特殊”的概率分布,即概率僅是1和0.對于以前確定的數據集:

在引入noise的情況下,新的學習流程圖如下所示:

### **二、ERROR Measure**
機器學習需要考慮的問題是找出的矩g與目標函數f有多相近,我們一直使用進行誤差的估計,那一般的錯誤測量有哪些形式呢?
我們介紹的矩g對錯誤的衡量有三個特性:
* **out-of-sample:樣本外的未知數據**
* **pointwise:對每個數據點x進行測試**
* **classification:看prediction與target是否一致,classification error通常稱為0/1 error**

PointWise error實際上就是對數據集的每個點計算錯誤并計算平均,和的pointwise error的表達式為:

pointwise error是機器學習中最常用也是最簡單的一種錯誤衡量方式,未來課程中,我們主要考慮這種方式。pointwise error一般可以分成兩類:0/1 error和squared error。0/1 error通常用在分類(classification)問題上,而squared error通常用在回歸(regression)問題上。

Ideal Mini-Target由和err共同決定,0/1 error和squared error的Ideal Mini-Target計算方法不一樣。例如下面這個例子,分別用0/1 error和squared error來估計最理想的mini-target是多少。0/1 error中的mini-target是取P(y|x)最大的那個類,而squared error中的mini-target是取所有類的加權平方和。

有了錯誤衡量,就會知道當前的矩g是好還是不好,并會讓演算法不斷修正,得到更好的矩g,從而使得g與目標函數更接近。所以,引入error measure后,學習流程圖如下所示:

### **三、Algorithmic Error Measure**
Error有兩種:false accept和false reject。false accept意思是誤把負類當成正類,false reject是誤把正類當成負類。 根據不同的機器學習問題,false accept和false reject應該有不同的權重,這根實際情況是符合的,比如是超市優惠,那么false reject應該設的大一些;如果是安保系統,那么false accept應該設的大一些。

機器學習演算法A的cost function error估計有多種方法,真實的err一般難以計算,常用的方法可以采用plausible或者friendly,根據具體情況而定。

引入algorithm error measure之后,學習流程圖如下:

### **四、Weighted Classification**
實際上,機器學習的Cost Function即來自于這些error,也就是算法里面的迭代的目標函數,通過優化使得Error(Ein)不斷變小。
cost function中,false accept和false reject賦予不同的權重,在演算法中體現。對不同權重的錯誤懲罰,可以選用virtual copying的方法。


### **五、總結**
本節課主要講了在有Noise的情況下,即數據集按照概率分布,那么VC Dimension仍然成立,機器學習算法推導仍然有效。機器學習cost function常用的Error有0/1 error和squared error兩類。實際問題中,對false accept和false reject應該選擇不同的權重。
**_注明:_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程。
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 1 -- The Learning Problem
- 2 -- Learning to Answer Yes/No
- 3 -- Types of Learning
- 4 -- Feasibility of Learning
- 5 -- Training versus Testing
- 6 -- Theory of Generalization
- 7 -- The VC Dimension
- 8 -- Noise and Error
- 9 -- Linear Regression
- 10 -- Logistic Regression
- 11 -- Linear Models for Classification
- 12 -- Nonlinear Transformation
- 13 -- Hazard of Overfitting
- 14 -- Regularization
- 15 -- Validation
- 16 -- Three Learning Principles
- 機器學習技法
- 1 -- Linear Support Vector Machine
- 2 -- Dual Support Vector Machine
- 3 -- Kernel Support Vector Machine
- 4 -- Soft-Margin Support Vector Machine
- 5 -- Kernel Logistic Regression
- 6 -- Support Vector Regression
- 7 -- Blending and Bagging
- 8 -- Adaptive Boosting
- 9 -- Decision Tree
- 10 -- Random Forest
- 11 -- Gradient Boosted Decision Tree
- 12 -- Neural Network
- 13 -- Deep Learning
- 14 -- Radial Basis Function Network
- 15 -- Matrix Factorization
- 16(完結) -- Finale