機器學習基礎概念和統計機器學習基本演算法
整理:侯宇軒
一、背景
機器學習(machine learning)形象的來說,就是使用機器(計算機)利用資料,自行對資料特徵進行學習(與手工編寫程式直接解決問題區分),來解決現實生活中的問題(如手寫數字識別、例項分割等等)。
機器學習演算法已經對人們對資料的利用方式造成了重大改變。例如醫院開始將診療資料儲存下來,包括病人的基本資訊、醫生的診斷結果、CT影象等等。使用學習型演算法對這些資料進行分析,就可以得到一段時間內的病例發展趨勢,或者嘗試利用CT資料對病人的病灶進行自動檢測等等。
二、分類
機器學習可以簡單的認為是基於資料的學習。依據學習時是否有資料標籤,分為監督學習、無監督學習和半監督學習
監督學習指不僅把訓練資料丟給計算機,而且還把分類的結果(資料具有的標籤)也一併丟給計算機分析。 計算機進行學習之後,再丟給它新的未知的資料,它也能計算出該資料導致各種結果的概率,給你一個最接近正確的結果。 由於計算機在學習的過程中不僅有訓練資料,而且有訓練結果(標籤),因此訓練的效果通常不錯。監督學習的結果可分為兩類:分類或迴歸。
非監督學習指的是隻給計算機訓練資料,不給結果(標籤),因此計算機無法準確地知道哪些資料具有哪些標籤,只能通過發現數據內部的一些相似特徵,把資料劃分為若干類。非監督學習一般表示為聚類演算法。
對於半監督學習,其訓練資料的一部分是有標籤的,另一部分沒有標籤,而沒標籤資料的數量常常遠遠大於有標籤資料數量(這也是符合現實情況的)。 隱藏在半監督學習下的基本規律在於:資料的分佈必然不是完全隨機的,通過一些有標籤資料的區域性特徵,以及更多沒標籤資料的整體分佈,就可以得到可以接受甚至是非常好的分類結果。
半監督學習分為很多種不同的情況。這裡舉一個例子:對下圖,我們使用了先聚類再標註的手段。雖然有標籤的資料很少,但是能夠取得比較好的效果。
三、梯度下降演算法
如何評判機器學習演算法效果的好壞?一般會依據學習目標定義損失函式(loss function) J。例如,在分類問題中,損失函式定義為預測向量與標準向量之間的相似度。找到函式J的全域性最優值,也就找到了機器學習演算法最合適的引數。
梯度下降演算法:在每一次訓練的迭代中,計算損失函式的梯度,並且在引數空間中向梯度方向移動一定步長。
梯度下降演算法的公式:
Line"/>
四、學習率與過擬合
學習率(Learning rate)作為機器學習中重要的超參,其決定著目標函式能否收斂到區域性最小值以及何時收斂到最小值。合適的學習率能夠使目標函式在合適的時間內收斂到區域性最小值。梯度下降公式中α即為學習率,決定引數空間中的步長。
當學習率設定的 過小 時,收斂過程十分緩慢,且容易陷入區域性極小值中。
當學習率設定的 過大 時,演算法可能在引數空間的最小值附近來回震盪,無法收斂。
泛化能力(generalization ability)是指機器學習演算法對新鮮樣本的適應能力。學習的目的是學到隱含在資料對背後的規律,對具有同一規律的學習集以外的資料,經過訓練的模型也能給出合適的輸出,該能力稱為泛化能力。
欠擬合:精度不足,泛化能力好。
過擬合:過於追求精度導致泛化能力不足。
如何防止過擬合?
最好的方法:增大訓練樣本。足夠大的訓練樣本可以解決大多數問題。
正則化:在損失函式J中加入正則項,一般與引數的某個範數有關。
比如在最小二乘迴歸當中,函式的各個高階(最高n階)項之前的係數可以使用正則化進行限制。
五、統計機器學習基礎方法:K近鄰法
K近鄰法(K-nearest-neighbors)主要用於分類問題。
對於新加入的點,尋找距離該點最近的k個已經進行分類的點。這k個點中數量最多的一類作為新點的類標籤。
特點:分類器不需要使用訓練集進行訓練,訓練時間複雜度為0。
重要的超引數:K。如下圖,K=3與K=5會造成新點被分為不同的類。
改進演算法:增加權重的knn。這個權重可以是距離權重(距離近的權重大),也可以是類別權重(更重視的一類權重大)
六、統計機器學習基礎方法:支撐向量機SVM
支撐向量機(Support Vector Machine)主要用於分類問題。
它是一種二分類模型,它的目的是尋找一個超平面來對樣本進行分割,分割的原則是間隔最大化,最終轉化為一個凸二次規劃問題來求解。根據資料的分佈特點,SVM分為線性可分SVM、線性不可分SVM、非線性SVM三種,這裡我們介紹第一種。
如果一個線性函式能夠將樣本分開,稱這些資料樣本是線性可分的。什麼是線性函式呢?其實很簡單,在二維空間中就是一條直線,在三維空間中就是一個平面,以此類推,如果不考慮空間維數,這樣的線性函式統稱為超平面。我們看一個簡單的二維空間的例子,O代表正類,X代表負類,樣本是線性可分的,但是很顯然不只有這一條直線可以將樣本分開,而是有無數條,我們所說的線性可分支援向量機就對應著能將資料正確劃分並且間隔最大的直線。 我們所說的線性可分支援向量機就對應著能將資料正確劃分並且 間隔最大 的直線。
為什麼要間隔最大呢?一般來說,一個點距離分離超平面的遠近可以表示分類預測的確信度,如圖中的A B兩個樣本點,B點被預測為正類的確信度要大於A點,所以SVM的目標是尋找一個超平面,使得離超平面較近的異類點之間能有更大的間隔,即不必考慮所有樣本點,只需讓求得的超平面使得離它近的點間隔最大。
如何計算間隔?
在樣本空間中,劃分超平面可通過如下線性方程來描述:
其中w為法向量。假設超平面能將訓練樣本正確的分類,即對於訓練樣本(xi,yi ),滿足
yi=+1代表正樣本,yi=-1代表負樣本(二分類)。這裡的公式成為最大間隔假設。實際上,大於、小於號後面的+1、-1只是為了計算方便,理論上無論是多少,都可以通過變換w、b使其變為+1、-1。
將上式左右乘以yi,得到
實際上等於
如圖,距離超平面最近的這幾個點滿足剛才的最大間隔假設,這幾個點即稱作支撐向量。虛線稱為邊界,虛線之間的距離稱為間隔。
計算即可發現,間隔
補充證明: 設x+ 、x- 為兩個異類支撐向量,那麼間隔實際上即為兩個異類支撐向量的差在W上的投影。
在得到間隔之後,要確定我們的計算目標:
此時,SVM的求解已經化為一個二次規劃(QPLC)問題,可以使用各種求解器進行求解。有興趣的讀者可以瞭解一下對偶方法,可以將該問題進一步化為LPQC問題,此處不再贅述。
七、 統計機器學習基礎方法:決策樹
決策樹(decision tree)主要用於分類問題。
決策樹由節點和(有向)邊組成,將整個資料集劃分為樹狀。內部節點表示一個特徵或者屬性,葉節點表示一個類,每個分叉處代表選擇了一個特徵。
測試時(建樹完成後),將新節點依據決策樹的分叉向下查詢,直到到達葉節點確定最後分類。如下圖是一棵簡單的決策樹,可以根據是否擁有房產、是否已婚、年收入是否大於等於80單位來將人分為能夠償還貸款和無法償還貸款的兩類。
目標:訓練出一個與訓練資料矛盾較小的決策樹,同時需要保證泛化能力。
損失函式J:通常是正則化的極大似然函式。
通常演算法:遞迴的選擇最優特徵。首先在根節點選擇一個最優特徵,使得各個子集在當前條件下有最好的分類。如果這些子集已經基本正確分類,那麼停止分叉,構建葉節點;否則,需要對子集依照上面的原則重新分割。
以上方法可能會出現過擬合的現象。我們需要對生成的樹進行剪枝,去掉過於細分的節點。可以看出,決策樹學習演算法包含特徵選擇、決策樹生成、剪枝三部分。
特徵選擇原理:選取分類能力更強的特徵。通常選取的準則是資訊增益。
除了以上的後剪枝之外,使用的更多的方法是預剪枝。方法包括:
1.指定每一個結點所包含的最小樣本數目,例如10,則該結點總樣本數小於10時,則不再分;
2.指定樹的高度或者深度,例如樹的最大深度為4;
3.指定結點的熵若小於某個值則不再劃分。