模式識別習題答案

1、1、 pca和lda的區(qū)別？pca是一種無監(jiān)督的映射方法，lda是一種有監(jiān)督的映射方法。pca只是將整組數(shù)據(jù)映射到最方便表示這組數(shù)據(jù)的坐標軸上，映射時沒有利用任何數(shù)據(jù)內部的分類信息。因此，雖然做了pca后，整組數(shù)據(jù)在表示上更加方便（降低了維數(shù)并將信息損失降到了最低），但在分類上也許會變得更加困難；lda在增加了分類信息之后，將輸入映射到了另外一個坐標軸上，有了這樣一個映射，數(shù)據(jù)之間就變得更易區(qū)分了（在低緯上就可以區(qū)分，減少了很大的運算量），它的目標是使得類別內的點距離越近越好，類別間的點越遠越好。2、 最大似然估計和貝葉斯方法的區(qū)別？p(x|x)是概率密度函數(shù)，x是給定的訓練樣本的集合，在哪種

2、情況下，貝葉斯估計接近最大似然估計？最大似然估計把待估的參數(shù)看做是確定性的量，只是其取值未知。利用已知的樣本結果，反推最有可能（最大概率）導致這樣結果的參數(shù)值(模型已知，參數(shù)未知）。貝葉斯估計則是把待估計的參數(shù)看成是符合某種先驗概率分布的隨機變量。對樣本進行觀測的過程，把先驗概率密度轉化為后驗概率密度，利用樣本的信息修正了對參數(shù)的初始估計值。當訓練樣本數(shù)量趨于無窮的時候，貝葉斯方法將接近最大似然估計。如果有非常多的訓練樣本，使得p(x|x)形成一個非常顯著的尖峰，而先驗概率p(x)又是均勻分布，此時兩者的本質是相同的。3、 為什么模擬退火能夠逃脫局部極小值？在解空間內隨機搜索，遇到較優(yōu)解就接受

3、，遇到較差解就按一定的概率決定是否接受，這個概率隨時間的變化而降低。實際上模擬退火算法也是貪心算法，只不過它在這個基礎上增加了隨機因素。這個隨機因素就是：以一定的概率來接受一個比單前解要差的解。通過這個隨機因素使得算法有可能跳出這個局部最優(yōu)解。4、 最小錯誤率和最小貝葉斯風險之間的關系？基于最小風險的貝葉斯決策就是基于最小錯誤率的貝葉斯決策，換言之，可以把基于最小錯誤率決策看做是基于最小風險決策的一個特例，基于最小風險決策本質上就是對基于最小錯誤率公式的加權處理。5、 som的主要功能是什么？怎么實現(xiàn)的？是winner-all-take-all 策略嗎？som是一種可以用于聚類的神經(jīng)網(wǎng)絡模型。

4、自組織映射（som）或自組織特征映射（sofm）是一種使用非監(jiān)督式學習來產(chǎn)生訓練樣本的輸入空間的一個低維（通常是二維）離散化的表示的人工神經(jīng)網(wǎng)絡（ann）。自組織映射與其他人工神經(jīng)網(wǎng)絡的不同之處在于它使用一個鄰近函數(shù)來保持輸入控件的拓撲性質。som網(wǎng)絡中, 某個輸出結點能對某一類模式作出特別的反應以代表該模式類, 輸出層上相鄰的結點能對實際模式分布中相近的模式類作出特別的反映,當某類數(shù)據(jù)模式輸入時, 對某一輸出結點產(chǎn)生最大刺激( 獲勝結點) , 同時對獲勝結點周圍的一些結點產(chǎn)生較大刺激。在訓練的過程中, 不斷對獲勝結點的連接權值作調整, 同時對獲勝結點的鄰域結點的連接權值作調整; 隨著訓練的進

5、行, 這個鄰域范圍不斷縮小, 直到最后, 只對獲勝結點進行細微的連接權值調整。不是winner-all-take-all 策略。獲勝結點產(chǎn)生刺激，其周圍的結點也會產(chǎn)生一定程度的興奮。6、 期望算法需要哪兩步？請列出可能的公式并做必要的解釋。e- step和m-step。e-step叫做期望化步驟，m-step為最大化步驟。整體算法的步驟如下所示：1、初始化分布參數(shù)。2、(e-step)計算期望e，利用對隱藏變量的現(xiàn)有估計值，計算其最大似然估計值，以此實現(xiàn)期望化的過程。3、(m-step)最大化在e-步驟上的最大似然估計值來計算參數(shù)的值4、重復2,3步驟直到收斂。f- step，根據(jù)之前的值求數(shù)

6、據(jù)的期望m- step：求使期望最大化，作為下一次e-step的值。7、 在核密度估計（kernel density estimation）中，核獨立就代表特征獨立嗎？樸素貝葉斯分類器的基本假設是什么？不能。（？）the naïve bayes classifier makes the assumption that the features are class-conditionally independent。8、 假設數(shù)據(jù)維度（dimensionality）比給定的訓練樣本的個數(shù)多很多，請用pca使計算復雜度依賴于數(shù)據(jù)的數(shù)量，而不是依賴于數(shù)據(jù)的維度。1）計算協(xié)方差矩陣，得到協(xié)方

7、差矩陣2）求協(xié)方差矩陣的特征值和特征向量3）選擇主成分，將特征值按照從大到小的順序排序，選擇其中最大的k個，然后將其對應的k個特征向量分別作為列向量組成特征向量矩陣。4）將樣本點投影到選取的特征向量上。9、 假設一個數(shù)據(jù)集（covariance matrix）的協(xié)方差矩陣是請回答下列問題：1） 這個協(xié)方差矩陣的每個元素有什么意義？協(xié)方差矩陣的每個元素是各個向量元素之間的協(xié)方差，數(shù)據(jù)集是二維的，四個元素從左到右從上到下分別是向量的第一個和第一個元素之間的協(xié)方差，12,21,222） 計算這數(shù)據(jù)集兩個主成分（principal components）矩陣：ah=a，h是特征向量矩陣的特征方程的表達

8、式為|e-a|=0（-1）（-1）-1/4=0 =3/2或者1/23） 為什么pca能夠移除特征之間的相關性？pca在降維的時候要盡量保存數(shù)據(jù)集中的有效信息，映射的方法是基變換，數(shù)據(jù)集在某個基上的投影值(也是在這個基上的坐標值)越分散, 方差越大, 這個基保留的信息也就越多。信息量保存能力最大的基向量一定是就是數(shù)據(jù)集的協(xié)方差矩陣的特征向量, 并且這個特征向量保存的信息量就是它對應的特征值。10、 一個k-class分類模型的先驗概率是p（k）=k，并且類概率密度是p（x|k）。給定一個訓練集xn，tn n=1,2,3n，tn is a binary target vector of lengt

9、h k that uses the 1-of-k coding scheme，so that is xn is from class k，tnk=1，and tnj=0，for all other j，jk。假設數(shù)據(jù)點的描繪是獨立于這個模型的，用最大似然估計在先驗概率是k=nk/n的情況下求解，nk是數(shù)據(jù)點的數(shù)量由k確定。解：11、 對于下列模式：(0,0)t，(1,1)t，(-1,-1)t，(2,2)t，(-2,-2)t，(1,-1)t，(-1,1)t，使用k-l轉換（或者說就是pca）降低特征維數(shù)至一維，并給出詳細的計算步驟。step1：求x和y的平均值。然后對于所有的樣例，都減去對應的均

10、值。x的均值是0，y的均值是0x：0 1 -1 2 -2 1 -1y：0 1 -1 2 -2 -1 1step2：求協(xié)方差矩陣（應該除以n-1，不是n，所以錯的）step3：求協(xié)方差矩陣的特征值和特征向量特征值：20/7 4/7特征向量：（e-a）x=0，=20/7時，特征向量是1,1t，=4/7時，特征向量是1,-1tstep4：將特征值按照從大到小的順序排序，選擇其中最大的k個，然后將其對應的k個特征向量分別作為列向量組成特征向量矩陣。所以選=20/7，特征向量矩陣是1,1t。step5：將樣本點投影到選取的特征向量上。dataadjust就是減去均值后的樣本矩陣，eigenvector就

11、是特征向量矩陣最后的結果就是0 2 -2 4 -4 0 012、 使用基本分支定界法去執(zhí)行特征選擇的先決條件（prerequisite）是什么？為什么它適用于降低計算代價？先決條件是假設單調性，增加特征只會增加目標函數(shù)的值。在這樣的假設條件下，增加特征的順序對結果不會造成影響，就避免去搜索僅僅特征順序不同的解，減少了計算代價。13、 在特征選擇方面，sfs（sequential forward selection）和sbs（sequential backward selection）有什么區(qū)別？當最佳的特征子集從大量的特征中選出以后，兩種方法哪一個是令人滿意的？特征子集x從空集開始，每次選擇一

12、個特征x加入特征子集x，使得特征函數(shù)j( x)最優(yōu)。簡單說就是，每次都選擇一個使得評價函數(shù)的取值達到更優(yōu)的特征加入，是一種簡單的貪心算法。從特征全集o開始，每次從特征集o中剔除一個特征x，使得剔除特征x后評價函數(shù)值達到最優(yōu)。sfs適用于最佳特征子集包含的特征個數(shù)較少的情況。sbs適用于最佳特征子集包含特征個數(shù)較多的情況。sfs：缺點是只能加入特征而不能去除特征。sbs：序列后向選擇與序列前向選擇正好相反，它的缺點是特征只能去除不能加入。另外，sfs與sbs都屬于貪心算法，容易陷入局部最優(yōu)值。雙向搜索( bds , bidirectional search ）：算法描述：使用序列前向選擇(sfs

13、)從空集開始，同時使用序列后向選擇(sbs)從全集開始搜索，當兩者搜索到一個相同的特征子集c時停止搜索。增l去r選擇算法( lrs）：該算法有兩種形式:<1>算法從空集開始，每輪先加入l個特征，然后從中去除r個特征，使得評價函數(shù)值最優(yōu)。( l> r )<2> 算法從全集開始，每輪先去除r個特征，然后加入l個特征，使得評價函數(shù)值最優(yōu)。( l< r )序列浮動選擇( sequential floating selection )：序列浮動選擇由增l去r選擇算法發(fā)展而來，該算法與增l去r選擇算法的不同之處在于：序列浮動選擇的l與r不是固定的，而是“浮動”的，也就是

14、會變化的。14、 線性svm的目標函數(shù)是什么？支持非線性svm的基本解決思路是什么？非支持向量是可移除的嗎？為什么？既然計算代價會隨著樣本的數(shù)量縮放，哪種方法被用來減輕（alleviate）這個負擔？目標函數(shù)：min 1/2 | subject to yi(xi+b) 1,i=1,2,，n 最大化margin非線性svm的基本思想是低維線性不可分，把它投影到高維空間中使線性可分。是的，可移除，因為它對構成超平面不做貢獻。先聚類，找出中心點，對中心點用svm進行分類，以減輕負載。15、 非線性svm是否和徑向基函數(shù)（radial basis function）具有一些相似性，如果有的話是什么？s

15、vm和rbf超平面表達方式一樣，都是將低維線性不可分的數(shù)據(jù)映射到高維。只是優(yōu)化時目標函數(shù)不同，svm是最大化margin，rbf是最小化錯誤率。16、 如果需要設計一個臉部識別系統(tǒng)并且在這個系統(tǒng)中輸入的圖片樣本的維度和訓練樣本的數(shù)量相比通常非常高，都有哪些處理步驟？對于每一步，你能列出一個或者多個解決方法嗎？怎么評價你設計的這個系統(tǒng)的錯誤率？圖像輸入：使用攝像頭或者從圖庫中獲取。圖像預處理：由于光照，環(huán)境以及人為影響，大多數(shù)情況下，系統(tǒng)采集的原始照片來自不同背景，不同條件，收到隨機的干擾，這些圖片不能被直接利用。光線補償、高斯平滑處理。特征提?。嚎梢允褂胮ca進行特征提取。訓練分類器：使用sv

16、m對已知樣本進行分類。后處理如何評價：采用交叉驗證，對原始數(shù)據(jù)進行分組,一部分做為訓練集(train set),另一部分做為驗證集(validation set),首先用訓練集對分類器進行訓練,在利用驗證集來測試訓練得到的模型(model),以此來做為評價分類器的性能指標。17、 given a set of data pointsxn，we can define the convex hull to be the set of all points x given by x=nxn where n=1,n0.consider a second set of pointsyntogether

17、with their corresponding convex hull. show that if their convex hull intersect ,the two sets of pointsx1andy1 cannot be linearly separable.18、 考慮收斂性（convergence property）和優(yōu)化準則，感知器（perceptron）學習和mse（均方誤差）的區(qū)別？感知器學習：能夠處理線性可分的情況，如果線性不可分，則不具有收斂性，其優(yōu)化準則是最小化錯誤。mse：能夠保證收斂性，但線性可分時不一定能夠找到實現(xiàn)分類的超平面，其優(yōu)化準則是最小化訓練數(shù)據(jù)

18、到超平面的平方和。19、 多層感知器中，什么方法用來避免過擬合？權重衰減，及早終止，增加噪聲。20、 在rbf（徑向基函數(shù)）中，為什么在線性轉換之后要跟一個非線性轉換？哪些非監(jiān)督方法能夠用來選擇rbf center？低維線性不可分，映射到高維線性可分。隨機選擇、聚類、密度估計21、 結構風險最小化的基本原則是什么？同時最小化經(jīng)驗風險和vc緯度，使二者達到平衡。22、 在kernel density estimation中，核獨立就表明特征獨立嗎？最大似然估計是怎樣被用來為kde選擇bandwidth parameter的？樸素貝葉斯分類器的基本假設是什么？基本的knn方法對噪聲特征敏感，哪種方法能夠用來改進這個？不是；結合似然函數(shù)進行交叉驗證。經(jīng)常使用留一交叉驗證的方法最大化偽似然。特征是類條件獨立的，公式在上面。對特征設置權重，以表達該特征的信息內容或作用價值。如果度量相似度的距離公式中對特征賦予不同權重，特征的權重一般根據(jù)各個特征在分類中的作用確定，或者根據(jù)特征在訓練樣本中的分類作用確定。23、 考慮錯誤率，隨機子抽樣(random subsampling)方法和自助抽樣法（bootstrap method）的區(qū)別？隨機二次抽樣：無放回的