機器學習中遺忘的數學知識
最大似然估計( Maximum likelihood )
最大似然估計,也稱為最大概似估計,是一種統計方法,它用來求一個樣本集的相關機率密度函數的參數。這個方法最早是遺傳學家以及統計學家羅納德·費雪爵士在1912年至1922年間開始使用的。
最大似然估計的原理
給定一個機率分布
,假定其機率密度函數(連續分布)或機率品質函數(離散分布)為 ,以及一個分布參數 ,我們可以從這個分布中抽出一個具有 個值的采樣 ,通過利用 ,我們就能計算出其機率: 但是,我們可能不知道 的值,盡管我們知道這些采樣資料來自于分布 。那麼我們如何才能估計出 呢?一個自然的想法是從這個分布中抽出一個具有 ,然後用這些采樣資料來估計.
一旦我們獲得
,我們就能從中找到一個關于 的估計。最大似然估計會尋找關于 的最可能的值(即,在所有可能的 取值中,尋找一個值使這個采樣的"可能性"最大化)。這種方法正好同一些其他的估計方法不同,如 的非偏估計,非偏估計未必會輸出一個最可能的值,而是會輸出一個既不高估也不低估的值。
要在數學上實作最大似然估計法,我們首先要定義似然函數:
并且在 的所有取值上,使這個函數最大化(一階導數)。這個使可能性最大的 值即被稱為的最大似然估計。
注意:
- 這裡的似然函數是指 不變時,關于 的一個函數。
- 最大似然估計函數不一定是惟一的,甚至不一定存在。
離散分布,離散有限參數空間
考慮一個抛硬币的例子。假設這個硬币正面跟反面輕重不同。我們把這個硬币抛80次(即,我們擷取一個采樣
并把正面的次數記下來,正面記為H,反面記為T)。并把抛出一個正面的機率記為
,抛出一個反面的機率記為
(是以,這裡的
即相當于上邊的
)。假設我們抛出了49個正面,31個反面,即49次H,31次T。假設這個硬币是我們從一個裝了三個硬币的盒子裡頭取出的。這三個硬币抛出正面的機率分别為
,
.這些硬币沒有标記,是以我們無法知道哪個是哪個。使用最大似然估計,通過這些試驗資料(即采樣資料),我們可以計算出哪個硬币的可能性最大。這個似然函數取以下三個值中的一個:
我們可以看到當
時,似然函數取得最大值。這就是
1.3. 離散分布,連續參數空間
現在假設例子1中的盒子中有無數個硬币,對于
中的任何一個
, 都有一個抛出正面機率為
的硬币對應,我們來求其似然函數的最大值:
其中
. 我們可以使用微分法來求最值。方程兩邊同時對
取微分,并使其為零。
其解為
,以及
.使可能性最大的解顯然是
(因為
和
這兩個解會使可能性為零)。是以我們說最大似然估計值為
。
這個結果很容易一般化。隻需要用一個字母
代替49用以表達伯努利試驗中的被觀察資料(即樣本)的"成功"次數,用另一個字母
代表伯努利試驗的次數即可。使用完全同樣的方法即可以得到最大似然估計值:
對于任何成功次數為
,試驗總數為
的伯努利試驗。
連續分布,連續參數空間
最常見的連續機率分布是正态分布,其機率密度函數如下:
現在有
個正态随機變量的采樣點,要求的是一個這樣的正态分布,這些采樣點分布到這個正态分布可能性最大(也就是機率密度積最大,每個點更靠近中心點),其
個正态随機變量的采樣的對應密度函數(假設其獨立并服從同一分布)為:
或:
這個分布有兩個參數:
.有人可能會擔心兩個參數與上邊的讨論的例子不同,上邊的例子都隻是在一個參數上對可能性進行最大化。實際上,在兩個參數上的求最大值的方法也差不多:隻需要分别把可能性
在兩個參數上最大化即可。當然這比一個參數麻煩一些,但是一點也不複雜。使用上邊例子同樣的符号,我們有
最大化一個似然函數同最大化它的自然對數是等價的。因為自然對數log是一個連續且在似然函數的值域内嚴格遞增的上凸函數。[注意:可能性函數(似然函數)的自然對數跟資訊熵以及Fisher資訊聯系緊密。]求對數通常能夠一定程度上簡化運算,比如在這個例子中可以看到:
這個方程的解是
.這的确是這個函數的最大值,因為它是
裡頭惟一的一階導數等于零的點并且二階導數嚴格小于零。
同理,我們對
求導,并使其為零。
是以,其關于
的最大似然估計為:
Jensen不等式
回顧優化理論中的一些概念。設f是定義域為實數的函數,如果對于所有的實數x,,那麼f是凸函數。當x是向量時,如果其hessian矩陣H是半正定的(),那麼f是凸函數。如果或者,那麼稱f是嚴格凸函數。
Jensen不等式表述如下:
如果f是凸函數,X是随機變量,那麼
特别地,如果f是嚴格凸函數,那麼當且僅當,也就是說X是常量。
這裡我們将簡寫為。
如果用圖表示會很清晰:
圖中,實線f是凸函數,X是随機變量,有0.5的機率是a,有0.5的機率是b。(就像擲硬币一樣)。X的期望值就是a和b的中值了,圖中可以看到成立。
當f是(嚴格)凹函數當且僅當-f是(嚴格)凸函數。
Jensen不等式應用于凹函數時,不等号方向反向,也就是。
奇異值分解
奇異值分解,singular value decomposition(SVD)是線性代數中一種重要的矩陣分解。
奇異值和特征值基礎知識
特征值分解和奇異值分解在機器學習領域都是屬于滿地可見的方法。兩者有着很緊密的關系,我在接下來會談到,特征值分解和奇異值分解的目的都是一樣,就是提取出一個矩陣最重要的特征。先談談特征值分解吧:
特征值
如果說一個向量v是方陣A的特征向量,将一定可以表示成下面的形式:
這時候λ就被稱為特征向量v對應的特征值,一個矩陣的一組特征向量是一組正交向量。特征值分解是将一個矩陣分解成下面的形式:
其中Q是這個矩陣A的特征向量組成的矩陣,Σ是一個對角陣,每一個對角線上的元素就是一個特征值。我這裡引用了一些參考文獻中的内容來說明一下。首先要明确的是,一個矩陣其實就是一個線性變換,因為一個矩陣乘以一個向量後得到的向量,其實就相當于将這個向量進行了線性變換。比如說下面的一個矩陣:
它其實對應的線性變換是下面的形式:
因為這個矩陣M乘以一個向量(x,y)的結果是:
上面的矩陣是對稱的,是以這個變換是一個對x,y軸的方向一個拉伸變換(每一個對角線上的元素将會對一個次元進行拉伸變換,當值>1時,是拉長,當值<1時時縮短),當矩陣不是對稱的時候,假如說矩陣是下面的樣子:
它所描述的變換是下面的樣子:
這其實是在平面上對一個軸進行的拉伸變換(如藍色的箭頭所示),在圖中,藍色的箭頭是一個最主要的變化方向(變化方向可能有不止一個),如果我們想要描述好一個變換,那我們就描述好這個變換主要的變化方向就好了。反過頭來看看之前特征值分解的式子,分解得到的Σ矩陣是一個對角陣,裡面的特征值是由大到小排列的,這些特征值所對應的特征向量就是描述這個矩陣變化方向。
當矩陣是高維的情況下,那麼這個矩陣就是高維空間下的一個線性變換,這個線性變化可能沒法通過圖檔來表示,但是可以想象,這個變換也同樣有很多的變換方向,我們通過特征值分解得到的前N個特征向量,那麼就對應了這個矩陣最主要的N個變化方向。我們利用這前N個變化方向,就可以近似這個矩陣(變換)。也就是之前說的:提取這個矩陣最重要的特征。總結一下,特征值分解可以得到特征值與特征向量,特征值表示的是這個特征到底有多重要,而特征向量表示這個特征是什麼,可以将每一個特征向量了解為一個線性的子空間,我們可以利用這些線性的子空間幹很多的事情。不過,特征值分解也有很多的局限,比如說變換的矩陣必須是方陣。 \
奇異值
下面談談奇異值分解。特征值分解是一個提取矩陣特征很不錯的方法,但是它隻是對方陣而言的,在現實的世界中,我們看到的大部分矩陣都不是方陣,比如說有N個學生,每個學生有M科成績,這樣形成的一個N * M的矩陣就不可能是方陣,我們怎樣才能描述這樣普通的矩陣呢的重要特征呢?奇異值分解可以用來幹這個事情,奇異值分解是一個能适用于任意的矩陣的一種分解的方法:
假設A是一個N * M的矩陣,那麼得到的U是一個N * N的方陣(裡面的向量是正交的,U裡面的向量稱為左奇異向量),Σ是一個N * M的矩陣(除了對角線的元素都是0,對角線上的元素稱為奇異值),V'(V的轉置)是一個N * N的矩陣,裡面的向量也是正交的,V裡面的向量稱為右奇異向量),從圖檔來反映幾個相乘的矩陣的大小可得下面的圖檔
那麼奇異值和特征值是怎麼對應起來的呢?首先,我們将一個矩陣A的轉置 * A,将會得到一個方陣,我們用這個方陣求特征值可以得到:
這裡得到的v,就是我們上面的右奇異向量。此外我們還可以得到:
這裡的σ就是上面說的奇異值,u就是上面說的左奇異向量。奇異值σ跟特征值類似,在矩陣Σ中也是從大到小排列,而且σ的減少特别的快,在很多情況下,前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了。也就是說,我們也可以用前r大的奇異值來近似描述矩陣,這裡定義一下部分奇異值分解:
r是一個遠小于m、n的數,這樣矩陣的乘法看起來像是下面的樣子:
右邊的三個矩陣相乘的結果将會是一個接近于A的矩陣,在這兒,r越接近于n,則相乘的結果越接近于A。而這三個矩陣的面積之和(在存儲觀點來說,矩陣面積越小,存儲量就越小)要遠遠小于原始的矩陣A,我們如果想要壓縮空間來表示原矩陣A,我們存下這裡的三個矩陣:U、Σ、V就好了。
Spark MLlib實作SVD計算
示例資料
1 0 0 0 2
0 0 3 0 0
0 0 0 0 0
0 4 0 0 0
示例代碼
Java code
public static void main(String[] args) {
SparkConf conf = new SparkConf().setAppName("SVDTest").setMaster("local[2]");
JavaSparkContext sc = new JavaSparkContext(conf);
JavaRDD<String> data = sc.textFile("/home/yurnom/data/svd.txt");
JavaRDD<Vector> rows = data.map(s -> {
double[] values = Arrays.asList(SPACE.split(s))
.stream()
.mapToDouble(Double::parseDouble)
.toArray();
return Vectors.dense(values);
});
RowMatrix mat = new RowMatrix(rows.rdd());
//第一個參數3意味着取top 3個奇異值,第二個參數true意味着計算矩陣U,第三個參數意味小于1.0E-9d的奇異值将被抛棄
SingularValueDecomposition<RowMatrix, Matrix> svd = mat.computeSVD(3, true, 1.0E-9d);
RowMatrix U = svd.U(); //矩陣U
Vector s = svd.s(); //奇異值
Matrix V = svd.V(); //矩陣V
System.out.println(s);
System.out.println("-------------------");
System.out.println(V);
}
示例結果
[4.0,3.0,2.23606797749979]
-------------------
0.0 0.0 -0.44721359549995787
-1.0 0.0 0.0
0.0 1.0 0.0
0.0 0.0 0.0
0.0 0.0 -0.8944271909999159
參考文獻
[1] Machine Learning Open Class by Andrew Ng in Stanford http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=MachineLearning
[2] Yu Zheng, Licia Capra, Ouri Wolfson, Hai Yang. Urban Computing: concepts, methodologies, and applications. ACM Transaction on Intelligent Systems and Technology. 5(3), 2014
[3] Jerry Lead http://www.cnblogs.com/jerrylead/
[3]《大資料-網際網路大規模資料挖掘與分布式處理》 Anand Rajaraman,Jeffrey David Ullman著,王斌譯
[4] UFLDL Tutorial http://deeplearning.stanford.edu/wiki/index.php/UFLDL_Tutorial
[5] Spark MLlib之樸素貝葉斯分類算法 http://selfup.cn/683.html
[6] MLlib - Dimensionality Reduction http://spark.apache.org/docs/latest/mllib-dimensionality-reduction.html
[7] 機器學習中的數學(5)-強大的矩陣奇異值分解(SVD)及其應用 http://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html
[8] 淺談 mllib 中線性回歸的算法實作 http://www.cnblogs.com/hseagle/p/3664933.html
[9] 最大似然估計 http://zh.wikipedia.org/zh-cn/%E6%9C%80%E5%A4%A7%E4%BC%BC%E7%84%B6%E4%BC%B0%E8%AE%A1
[10] Deep Learning Tutorial http://deeplearning.net/tutorial/
附 錄
Andrew Ng 在斯坦福大學的CS229機器學習課程内容
Andrew Ng -- Stanford University CS 229 Machine Learning
This course provides a broad introduction to machine learning and statistical pattern recognition.
Topics include:
supervised learning (generative/discriminative learning, parametric/non-parametric learning, neural networks, support vector machines);
learning theory (bias/variance tradeoffs; VC theory; large margins);
unsupervised learning (clustering, dimensionality reduction, kernel methods);
reinforcement learning and adaptive control. The course will also discuss recent applications of machine learning, such as to robotic control, data mining, autonomous navigation, bioinformatics, speech recognition, and text and web data processing.
中英文詞語對照
neural networks 神經網絡
activation function 激活函數
hyperbolic tangent 雙曲正切函數
bias units 偏置項
activation 激活值
forward propagation 前向傳播
feedforward neural network 前饋神經網絡(參照Mitchell的《機器學習》的翻譯)
Softmax回歸 Softmax Regression
有監督學習 supervised learning
無監督學習 unsupervised learning
深度學習 deep learning
logistic回歸 logistic regression
截距項 intercept term
二進制分類 binary classification
類型标記 class labels
估值函數/估計值 hypothesis
代價函數 cost function
多元分類 multi-class classification
權重衰減 weight decay
深度網絡 Deep Networks
深度神經網絡 deep neural networks
非線性變換 non-linear transformation
激活函數 activation function
簡潔地表達 represent compactly
"部分-整體"的分解 part-whole decompositions
目标的部件 parts of objects
高度非凸的優化問題 highly non-convex optimization problem
共轭梯度 conjugate gradient
梯度的彌散 diffusion of gradients
逐層貪婪訓練方法 Greedy layer-wise training
自動編碼器 autoencoder
微調 fine-tuned
自學習方法 self-taught learning
作者:雪松
出處:http://www.cnblogs.com/xuesong/
本文版權歸作者和部落格園共有,歡迎轉載,轉載請标明作者、出處和原文連結。
未經作者同意請您務必保留此聲明。