從高斯分布、機器人誤差、EM演算法到小球檢測
Coursera上的課程(Robotics: Estimation and Learning),感覺講得特別棒,寫下自己的理解。
高斯分布被廣泛應用於對機器人誤差的建模。在這篇筆記中,我們將會:
- 介紹如何使用一元高斯分布、多元高斯分布和高斯混合模型對機器人誤差進行建模。
- 介紹求解這些高斯分布的演算法。
- 以小球檢測這一實際應用來實踐我們的模型和演算法。
1. 一元高斯分布
在這一節我們將介紹如何使用一元高斯分布對機器人誤差進行建模。
在進入正題之前,我們需要首先了解為什麼學習高斯分布?什麼使得高斯分布有效並且重要?為什麼使用高斯分布對雜訊和不確定性進行建模(而不是其他概率分布模型,比如均勻分布)?
- 高斯分布使得只需要兩個參數就能確定一個連續的概率分布。這兩個參數分別是均值和方差,這很簡潔。這也使得高斯分布易於計算和推斷。
- 高斯分布有一些較好的數學性質。例如,兩個高斯分布的積還是高斯分布。這使得你在對高斯分布做運算的時候不需要考慮其他的概率分布。
- 理論上來說,根據中心極限定理,大量相互獨立的隨機變數,其均值的分布以高斯分布為極限。而雜訊和不確定性就是包含大量相互獨立的隨機變數的數據,用高斯分布對它們進行建模是不二選擇。
說了這麼多,我們來舉個栗子吧,怎樣使用高斯分布來對一個目標顏色進行建模?
下圖是足球機器人通過頭頂攝像機拍攝到的照片。
顯然,圖片中有兩種顏色的球,黃球和紅球。我們設想這個足球機器人想檢測圖片中的黃球。對於人類來說,一眼就能分辨出黃球在哪,但對一個機器人來說這並不簡單。機器人讀入的圖片是一個一個像素的數值,它需要建立從像素的數值到「黃色」或者「紅色」的映射。不妨讓我們來看看「黃球」裡面的像素數值是怎樣的。我們記錄黃球的每個像素的色相值(Hue,HSV模型中表示色彩的基本屬性,就是平常所說的顏色名稱,如紅色、黃色等),然後畫出每一個色相值出現次數的柱狀圖如右下。
我們可以看到,」黃色「這一種顏色可以有很多個色相值(換成RGB模型也是一樣的),這就是我們所說的雜訊或者不確定性。從分布上來看,」黃色「的色相值以大約53為中心然後向兩邊擴散。為了記錄「黃色」,一種方法是記錄每一個「黃色」像素的色相值,然而這將十分消耗存儲空間,確切來說,有多少像素就消耗多大的空間。
另一種簡潔有效的方法是使用高斯分布。
讓我們先來溫故一下高斯分布的數學表達形式再返回來解釋這個例子吧。
高斯分布的數學形式如下:
其中,是變數,表示的出現的概率,是均值,是標準差(是方差)。和是之前我們提到的表示一個高斯分布的兩個參數。
在我們上面的栗子中,假設我們已經完成了對黃色的高斯分布建模,是一個採樣像素的色相值,那麼就表示該像素屬於「黃色」的概率。
我們繼續介紹高斯分布,為了更加直觀地了解高斯分布長什麼樣子,我們把高斯分布畫出來。下圖是的情況下的高斯分布圖(標準高斯分布)。
當均值變化而方差不變的時候,可以看作將圖像進行了平移。當均值不變,而標準差變化的時候,可以看作將圖像進行了「擠」或「壓」(方差越大越扁)。總結來說,決定了高斯分布的對稱軸,決定了高斯分布的擴散程度。
讓我們返回到小球檢測的栗子。我們只使用一個高斯分布(即兩個值)就可以近似地存儲所有的「黃色」像素,如下圖。那麼如何通過數據來求和這兩個參數呢?我們將在下一節中介紹最大似然估計方法求解一元高斯分布。2. 求解一元高斯分布:最大似然估計
在這一節,我們將介紹使用最大似然估計(Maximum Likelihood Estimation,MLE)的方法來求解觀測數據的一元高斯分布。
首先,我們引入似然函數(或者說似然,Likelihood)的概念。
似然指的是在給定模型參數的情況下觀測值出現的概率。它被定義成了一個條件概率。比如,在上一節的小球例子中,表示所有「黃色」像素點的色相值,如果給定了高斯分布的和,我們就能算出出現的概率。
那麼我們的問題就可以表述為,給定觀測值,求和,使得似然函數最大:其中,和表示估計值。
這裡,觀測值是所有的觀測值的集合,我們假設這些觀測值兩兩相互獨立(在我們的小球檢測栗子中也確實是這樣的)。那麼:
這裡,表示觀測值集合的大小為。那麼我們的目標就變成了:
根據對數函數的單調性(),取對數再求最大值等價於直接求最大值,即:
那麼我們的目標就變成了:
而將帶入高斯分布我們有:
那麼我們的目標就變成了:
讓我們給後面的目標函數做個記號,令
我們的目標就是使得最小,而函數取最小值時其關於的偏導數等於0:
求得:
將帶入函數得到函數,其取最小值時關於的導數等於0:求得:
總結來說,最後的答案為:
回到我們小球檢測的栗子,我們可以求出的高斯分布如下圖:
在這一節中,我們介紹了怎樣使用MLE來求解一元高斯分布。然而實際情況中,可能需要提取的特徵值不止色相值這一個(比如RGB三個值)。這樣一元高斯分布不再適用。為了解決這個問題,我們將在下一節中介紹多元高斯分布。3. 多元高斯分布
讓我們回到小球檢測的栗子,在一元高斯分布下,我們只使用了色相值這一個性質。然而,顏色其實是用多個維度來定義的。比如,在HSV模型下,除了色相值還有飽和度(Saturation)和亮度(Value)。而我們通常使用的三原色光模式(RGB模型)將顏色表示成紅色(R)、綠色(G)和藍色(B)的疊加。如果我們用RGB值來表示一個顏色,怎樣表示我們栗子中的小球呢?我們將圖片中所有像素點的RGB值用散點圖的形式畫出來可以得到下面的圖:
那我們怎樣對這種圖形進行建模呢?如這一節的題目所說,我們將一元高斯分布擴展到多元高斯分布並對RGB值進行建模。
讓我們首先來介紹多元高斯分布的數學形式吧:多元高斯分布和一元高斯分布是十分相似的,我們用加粗的來表示變數(一個向量),表示維度(元的數目),加粗的表示平均向量,大寫的表示協方差矩陣(Covariance Matrix,是一個方陣),表示的行列式值,表示矩陣的轉置。
值得一提的是協方差矩陣,它由兩部分組成,方差(Variance)和相關性(Correlation),對角線上的值表示方差,非對角線上的值表示維度之間的相關性。拿一個二維協方差矩陣作栗子:
回到小球檢測的栗子,我們考慮用RGB來對「紅色」小球進行多元高斯分布的建模,那麼各個參數就如下圖所示了:
我們來看一下標準二元高斯分布圖:各個參數的變化對多元高斯分布的影響請參考課程內容本身。值得一提的是,協方差矩陣中的相關性參數是一元高斯分布中沒有的。那麼怎樣求解多元高斯分布呢?確切地說,怎樣求解多元高斯分布中的平均向量和協方差矩陣呢?4. 求解多元高斯分布:最大似然估計
和求解一元高斯分布類似,我們將問題描述為:給定觀測值,求和,使得似然函數最大:
同樣,假設觀測值兩兩相互獨立,根據獨立概率公式,我們有:
同樣(1)取對數,(2)將多元高斯分布的形式帶入,我們有:
我們給目標函數做個記號,令
我們仍然分別對和求偏導來計算和。(這裡需要矩陣求導的知識,可以參考Matrix Calculus Manual)
求得,
5. 高斯混合模型
在第一節和第四節,我們介紹了一元高斯分布和多元高斯分布,他們都屬於單高斯模型(Single Gaussian Model)。使用單高斯模型來建模有一些限制,例如,它一定只有一個眾數,它一定對稱的。舉個例子,如果我們對下面的分布建立單高斯模型,會得到顯然相差很多的模型:
於是,我們引入混合高斯模型(Gaussian Mixture Model,GMM)。高斯混合模型就是多個單高斯模型的和。它的表達能力十分強,任何分布都可以用GMM來表示。例如,在下面這個圖中,彩色的線表示一個一個的單高斯模型,黑色的線是它們的和,一個高斯混合模型:在小球檢測的栗子中,我們試圖對紅色小球建立單高斯模型(紅和綠這二元),會發現紅色小球的觀測值不是很符合所建立的模型,如下圖:此時,如果我們採取高斯混合模型(兩個二元高斯分布),會發現效果好了很多,如下圖:下面,我們來詳細地介紹一下高斯混合模型,高斯混合模型的數學形式如下:
其中,是均值為,協方差矩陣為的單高斯模型,是的權重係數(),是單高斯模型的個數。
前面我們提到了GMM的優點(能夠表示任何分布),當然GMM也有缺點。其一,參數太多了,每一個單高斯模型都有均值、協方差矩陣和權重係數,另外還有單高斯模型的個數也是其中一個參數,這使得求解GMM十分複雜。其二,有時候所建立的高斯混合模型對觀測值的建模效果很好,但是其他值可能效果不好,我們稱這個缺點為過度擬合(Overfitting)。
這一節我們介紹了高斯混合模型,與前面類似,我們將在下節介紹求解混合高斯模型的方法。
6. 求解高斯混合模型:EM演算法
在求解單高斯分布的時候,我們用最大似然估計(MLE)的方法得到了理論上的最優解。當我們使用相同的方法試圖求解高斯混合模型的時候,會卡在中間步驟上(具體來說,是單高斯分布求和出現在了對數函數裡面)。索性我們可以用迭代的方法來求解GMM,具體來說,最大期望演算法(Expectation Maximization algorith,EM)。
上一節提到,我們想要求解GMM如下:
這其中需要求解的變數很多:、、、。為了簡化問題,我們假定是預先設定好的,並且每個單高斯分布的權重相等,即假定:
這樣,我們需要確定的就只剩下每個單高斯分布的參數(、)了。
前面提到,這個模型是沒有解析解(理論最優)的。取而代之,我們採取迭代的方法逼近最優解(大家可以回想一下牛頓法求近似求解方程,或者遺傳演算法)。
在牛頓法中,我們需要預先猜測一個初始解,同樣在EM演算法中,我們也需要預先猜測一個初始解()。
在EM演算法中,我們引入一個中間變數,其中是單高斯分布的個數,是觀測值的數目。
直觀地可以這樣理解:在確定了所有單高斯分布之後,可以計算觀測值發生的概率(分母部分)和第個單高斯分布下觀測值發生的概率(分子部分),這樣就可以理解為第個高斯分布對觀測值發生的概率的貢獻了。如下表所示:
表中最後一行可以理解為第個單高斯分布對整個GMM的貢獻。
例如,當GMM中時(即由兩個單高斯分布組成):
在這個圖中,對於觀測值,是第一個單高斯分布下發生的概率,是第二個單高斯分布下發生的概率,是在整個GMM下發生的概率;表示對發生概率的貢獻,表示對發生概率的貢獻。當我們算出了所有的之後,我們再反過來用它更新每一個單高斯分布。更新的公式為:大家可以想一想,對於第個高斯分布,可以理解為第個觀測值的貢獻,而表示的平均值,用來更新就很好理解了,進而再更新協方差矩陣。
這樣,兩組值互相更新,當相鄰兩個步驟值的差小於事先設定一個閾值(threshold)時(收斂),我們停止循環,輸出和為所求。值得一提的是,EM演算法的結果和初值有很大關係,不同初值會得到不同的解。(想像一下GMM模型其實是多峰的,不同的初值可能最終收斂到不同的峰值,有的初值會收斂到全局最優,有的初值會收斂到局部最優)
7. 實戰:小球檢測
具體任務在這個網址:小球檢測
簡單來說,給你一些圖片作為訓練集,讓你對黃色小球進行建模,建模完成後,讀入最左邊的原始圖片,要求能像最右邊的圖片一樣標識出小球的位置:
(註:我們使用matlab完成所有代碼)
第一步:建立顏色模型
前面幾節我們提到,要建立高斯分布模型,首先要有很多觀測值,所以,我們將在這一步裡面採集很多觀測值,再建立高斯模型。課程裡面提供了19張圖片作為訓練集供採樣:
我們編寫代碼mark.m,作用為讀入一張一張圖片,然後手動圈出圖片中的黃色小球,將圈中部分的像素RGB值存入觀測值。imagepath = "./train";Samples = [];for k=1:19 I = imread(sprintf("%s/%03d.png",imagepath,k)); % read files into RGB R = I(:,:,1); G = I(:,:,2); B = I(:,:,3); % Collect samples disp(""); disp("INTRUCTION: Click along the boundary of the ball. Double-click when you get back to the initial point.") disp("INTRUCTION: You can maximize the window size of the figure for precise clicks.") figure(1), mask = roipoly(I); figure(2), imshow(mask); title("Mask"); sample_ind = find(mask > 0); % select marked pixels R = R(sample_ind); G = G(sample_ind); B = B(sample_ind); Samples = [Samples; [R G B]]; % insert selected pixels into samples disp("INTRUCTION: Press any key to continue. (Ctrl+c to exit)") pauseendsave("Samples.mat", "Samples"); % save the samples to filefigure, scatter3(Samples(:,1),Samples(:,2),Samples(:,3),".");title("Pixel Color Distribubtion");xlabel("Red");ylabel("Green");zlabel("Blue");
mu = mean(Samples); % musig=zeros(3,3); % sigmafor i=1:N data=double(Samples(i,:)); sig=sig+(data-mu)"*(data-mu)/N;end% save the coefficients to filessave("mu.mat", "mu");save("sig.mat", "sig");
接下來,我們需要編寫函數detecBall,以圖像為參數,以劃分好的黑白圖像和小球中心為輸出,如下,I是輸入的圖像,segI是劃分好的黑白圖像,loc是球的中心點。detecBall.m的具體代碼如下:
function [segI, loc] = detectBall(I)load("mu.mat");load("sig.mat");Id=double(I); % array in size of (row, col, 3)row=size(Id,1); col=size(Id,2);% x_i - mufor i=1:3 Id(:,:,i) = Id(:,:,i) - mu(i);end% reshape the image to a matrix in size of (row*col, 3)Id=reshape(Id,row*col,3); % calc possibility using gaussian distribution% be careful of using * and .* in matrix multiplyId = exp(-0.5* sum(Id*inv(sig).*Id, 2)) ./ (2*pi)^1.5 ./ det(sig)^0.5;% reshape back, now each pixels is with the value of the possibilityId=reshape(Id,row,col);% set thresholdthr=8e-06;% binary image about if each pixel "is ball"Id=Id>thr;% find the biggest ball areasegI = false(size(Id));CC = bwconncomp(Id);numPixels = cellfun(@numel,CC.PixelIdxList);[biggest,idx] = max(numPixels);segI(CC.PixelIdxList{idx}) = true;%figure, imshow(segI); hold on;S = regionprops(CC,"Centroid");loc = S(idx).Centroid;%plot(loc(1), loc(2),"r+");
需要注意的一點是,求像素屬於小球的概率的時候,盡量用矩陣運算,而不要用循環,否則會效率低下,請讀者仔細揣摩計算技巧,靈活運用矩陣的運算。
接下來,我們就可以測試小球檢測的效果啦!
我們編寫test.m測試訓練集的19張圖片:
imagepath = "./train";for k=1:19 I = imread(sprintf("%s/%03d.png",imagepath,k)); [segI, loc] = detectBall(I); figure, imshow(segI); hold on; plot(loc(1), loc(2), "+b","MarkerSize",7); disp("Press any key to continue. (Ctrl+c to exit)") pauseend
效果如下:
成功!當然,我們也可以用其他種類的高斯模型對黃色小球進行建模,這裡就不做示範啦!
感謝閱讀!
推薦閱讀:
※機器學習系列-word2vec篇
※機器學習43條軍規:解密谷歌機器學習工程最佳實踐(上)
※使用「對象檢測」實現智能結賬體驗
※最簡單的 GAN 解釋 (生成對抗網路)