模式識別-習(xí)題答案.doc

1、 PCA和LDA的區(qū)別？PCA是一種無監(jiān)督的映射方法，LDA是一種有監(jiān)督的映射方法。PCA只是將整組數(shù)據(jù)映射到最方便表示這組數(shù)據(jù)的坐標(biāo)軸上，映射時(shí)沒有利用任何數(shù)據(jù)內(nèi)部的分類信息。因此，雖然做了PCA后，整組數(shù)據(jù)在表示上更加方便（降低了維數(shù)并將信息損失降到了最低），但在分類上也許會變得更加困難；LDA在增加了分類信息之后，將輸入映射到了另外一個(gè)坐標(biāo)軸上，有了這樣一個(gè)映射，數(shù)據(jù)之間就變得更易區(qū)分了（在低緯上就可以區(qū)分，減少了很大的運(yùn)算量），它的目標(biāo)是使得類別內(nèi)的點(diǎn)距離越近越好，類別間的點(diǎn)越遠(yuǎn)越好。2、 最大似然估計(jì)和貝葉斯方法的區(qū)別？p(x|X)是概率密度函數(shù)，X是給定的訓(xùn)練樣本的集合，在哪種情況下，貝葉斯估計(jì)接近最大似然估計(jì)？最大似然估計(jì)把待估的參數(shù)看做是確定性的量，只是其取值未知。利用已知的樣本結(jié)果，反推最有可能（最大概率）導(dǎo)致這樣結(jié)果的參數(shù)值(模型已知，參數(shù)未知）。貝葉斯估計(jì)則是把待估計(jì)的參數(shù)看成是符合某種先驗(yàn)概率分布的隨機(jī)變量。對樣本進(jìn)行觀測的過程，把先驗(yàn)概率密度轉(zhuǎn)化為后驗(yàn)概率密度，利用樣本的信息修正了對參數(shù)的初始估計(jì)值。當(dāng)訓(xùn)練樣本數(shù)量趨于無窮的時(shí)候，貝葉斯方法將接近最大似然估計(jì)。如果有非常多的訓(xùn)練樣本，使得p(x|X)形成一個(gè)非常顯著的尖峰，而先驗(yàn)概率p(x)又是均勻分布，此時(shí)兩者的本質(zhì)是相同的。3、 為什么模擬退火能夠逃脫局部極小值？在解空間內(nèi)隨機(jī)搜索，遇到較優(yōu)解就接受，遇到較差解就按一定的概率決定是否接受，這個(gè)概率隨時(shí)間的變化而降低。實(shí)際上模擬退火算法也是貪心算法，只不過它在這個(gè)基礎(chǔ)上增加了隨機(jī)因素。這個(gè)隨機(jī)因素就是：以一定的概率來接受一個(gè)比單前解要差的解。通過這個(gè)隨機(jī)因素使得算法有可能跳出這個(gè)局部最優(yōu)解。4、 最小錯(cuò)誤率和最小貝葉斯風(fēng)險(xiǎn)之間的關(guān)系？基于最小風(fēng)險(xiǎn)的貝葉斯決策就是基于最小錯(cuò)誤率的貝葉斯決策，換言之，可以把基于最小錯(cuò)誤率決策看做是基于最小風(fēng)險(xiǎn)決策的一個(gè)特例，基于最小風(fēng)險(xiǎn)決策本質(zhì)上就是對基于最小錯(cuò)誤率公式的加權(quán)處理。5、 SOM的主要功能是什么？怎么實(shí)現(xiàn)的？是winner-all-take-all 策略嗎？SOM是一種可以用于聚類的神經(jīng)網(wǎng)絡(luò)模型。自組織映射（SOM）或自組織特征映射（SOFM）是一種使用非監(jiān)督式學(xué)習(xí)來產(chǎn)生訓(xùn)練樣本的輸入空間的一個(gè)低維（通常是二維）離散化的表示的人工神經(jīng)網(wǎng)絡(luò)（ANN）。自組織映射與其他人工神經(jīng)網(wǎng)絡(luò)的不同之處在于它使用一個(gè)鄰近函數(shù)來保持輸入控件的拓?fù)湫再|(zhì)。SOM網(wǎng)絡(luò)中, 某個(gè)輸出結(jié)點(diǎn)能對某一類模式作出特別的反應(yīng)以代表該模式類, 輸出層上相鄰的結(jié)點(diǎn)能對實(shí)際模式分布中相近的模式類作出特別的反映,當(dāng)某類數(shù)據(jù)模式輸入時(shí), 對某一輸出結(jié)點(diǎn)產(chǎn)生最大刺激( 獲勝結(jié)點(diǎn)) , 同時(shí)對獲勝結(jié)點(diǎn)周圍的一些結(jié)點(diǎn)產(chǎn)生較大刺激。在訓(xùn)練的過程中, 不斷對獲勝結(jié)點(diǎn)的連接權(quán)值作調(diào)整, 同時(shí)對獲勝結(jié)點(diǎn)的鄰域結(jié)點(diǎn)的連接權(quán)值作調(diào)整; 隨著訓(xùn)練的進(jìn)行, 這個(gè)鄰域范圍不斷縮小, 直到最后, 只對獲勝結(jié)點(diǎn)進(jìn)行細(xì)微的連接權(quán)值調(diào)整。不是winner-all-take-all 策略。獲勝結(jié)點(diǎn)產(chǎn)生刺激，其周圍的結(jié)點(diǎn)也會產(chǎn)生一定程度的興奮。6、 期望算法需要哪兩步？請列出可能的公式并做必要的解釋。E- Step和M-Step。E-Step叫做期望化步驟，M-Step為最大化步驟。整體算法的步驟如下所示：1、初始化分布參數(shù)。2、(E-Step)計(jì)算期望E，利用對隱藏變量的現(xiàn)有估計(jì)值，計(jì)算其最大似然估計(jì)值，以此實(shí)現(xiàn)期望化的過程。3、(M-Step)最大化在E-步驟上的最大似然估計(jì)值來計(jì)算參數(shù)的值4、重復(fù)2,3步驟直到收斂。F- step，根據(jù)之前的值求數(shù)據(jù)的期望M- step：求使期望最大化，作為下一次E-step的值。7、 在核密度估計(jì)（kernel density estimation）中，核獨(dú)立就代表特征獨(dú)立嗎？樸素貝葉斯分類器的基本假設(shè)是什么？不能。（？）The Nave Bayes classifier makes the assumption that the features are class-conditionally independent。8、 假設(shè)數(shù)據(jù)維度（dimensionality）比給定的訓(xùn)練樣本的個(gè)數(shù)多很多，請用PCA使計(jì)算復(fù)雜度依賴于數(shù)據(jù)的數(shù)量，而不是依賴于數(shù)據(jù)的維度。1）計(jì)算協(xié)方差矩陣，得到協(xié)方差矩陣2）求協(xié)方差矩陣的特征值和特征向量3）選擇主成分，將特征值按照從大到小的順序排序，選擇其中最大的k個(gè)，然后將其對應(yīng)的k個(gè)特征向量分別作為列向量組成特征向量矩陣。4）將樣本點(diǎn)投影到選取的特征向量上。9、 假設(shè)一個(gè)數(shù)據(jù)集（covariance matrix）的協(xié)方差矩陣是請回答下列問題：1） 這個(gè)協(xié)方差矩陣的每個(gè)元素有什么意義？協(xié)方差矩陣的每個(gè)元素是各個(gè)向量元素之間的協(xié)方差，數(shù)據(jù)集是二維的，四個(gè)元素從左到右從上到下分別是向量的第一個(gè)和第一個(gè)元素之間的協(xié)方差，12,21,222） 計(jì)算這數(shù)據(jù)集兩個(gè)主成分（principal components）矩陣：AH=A，H是特征向量矩陣的特征方程的表達(dá)式為|E-A|=0（-1）（-1）-1/4=0 =3/2或者1/23） 為什么PCA能夠移除特征之間的相關(guān)性？PCA在降維的時(shí)候要盡量保存數(shù)據(jù)集中的有效信息，映射的方法是基變換，數(shù)據(jù)集在某個(gè)基上的投影值(也是在這個(gè)基上的坐標(biāo)值)越分散, 方差越大, 這個(gè)基保留的信息也就越多。信息量保存能力最大的基向量一定是就是數(shù)據(jù)集的協(xié)方差矩陣的特征向量, 并且這個(gè)特征向量保存的信息量就是它對應(yīng)的特征值。10、 一個(gè)K-class分類模型的先驗(yàn)概率是p（k）=k，并且類概率密度是p（x|k）。給定一個(gè)訓(xùn)練集xn，tn n=1,2,3N，tn is a binary target vector of length 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è)數(shù)據(jù)點(diǎn)的描繪是獨(dú)立于這個(gè)模型的，用最大似然估計(jì)在先驗(yàn)概率是k=Nk/N的情況下求解，Nk是數(shù)據(jù)點(diǎn)的數(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轉(zhuǎn)換（或者說就是PCA）降低特征維數(shù)至一維，并給出詳細(xì)的計(jì)算步驟。Step1：求x和y的平均值。然后對于所有的樣例，都減去對應(yīng)的均值。X的均值是0，y的均值是0X：0 1 -1 2 -2 1 -1Y：0 1 -1 2 -2 -1 1Step2：求協(xié)方差矩陣（應(yīng)該除以n-1，不是n，所以錯(cuò)的）Step3：求協(xié)方差矩陣的特征值和特征向量特征值：20/7 4/7特征向量：（E-A）X=0，=20/7時(shí)，特征向量是1,1T，=4/7時(shí)，特征向量是1,-1TStep4：將特征值按照從大到小的順序排序，選擇其中最大的k個(gè)，然后將其對應(yīng)的k個(gè)特征向量分別作為列向量組成特征向量矩陣。所以選=20/7，特征向量矩陣是1,1T。Step5：將樣本點(diǎn)投影到選取的特征向量上。DataAdjust就是減去均值后的樣本矩陣，EigenVector就是特征向量矩陣最后的結(jié)果就是0 2 -2 4 -4 0 012、 使用基本分支定界法去執(zhí)行特征選擇的先決條件（prerequisite）是什么？為什么它適用于降低計(jì)算代價(jià)？先決條件是假設(shè)單調(diào)性，增加特征只會增加目標(biāo)函數(shù)的值。在這樣的假設(shè)條件下，增加特征的順序?qū)Y(jié)果不會造成影響，就避免去搜索僅僅特征順序不同的解，減少了計(jì)算代價(jià)。13、 在特征選擇方面，SFS（sequential forward selection）和SBS（sequential backward selection）有什么區(qū)別？當(dāng)最佳的特征子集從大量的特征中選出以后，兩種方法哪一個(gè)是令人滿意的？特征子集X從空集開始，每次選擇一個(gè)特征x加入特征子集X，使得特征函數(shù)J( X)最優(yōu)。簡單說就是，每次都選擇一個(gè)使得評價(jià)函數(shù)的取值達(dá)到更優(yōu)的特征加入，是一種簡單的貪心算法。從特征全集O開始，每次從特征集O中剔除一個(gè)特征x，使得剔除特征x后評價(jià)函數(shù)值達(dá)到最優(yōu)。SFS適用于最佳特征子集包含的特征個(gè)數(shù)較少的情況。SBS適用于最佳特征子集包含特征個(gè)數(shù)較多的情況。SFS：缺點(diǎn)是只能加入特征而不能去除特征。SBS：序列后向選擇與序列前向選擇正好相反，它的缺點(diǎn)是特征只能去除不能加入。另外，SFS與SBS都屬于貪心算法，容易陷入局部最優(yōu)值。雙向搜索( BDS , Bidirectional Search ）：算法描述：使用序列前向選擇(SFS)從空集開始，同時(shí)使用序列后向選擇(SBS)從全集開始搜索，當(dāng)兩者搜索到一個(gè)相同的特征子集C時(shí)停止搜索。增L去R選擇算法( LRS）：該算法有兩種形式:<1>算法從空集開始，每輪先加入L個(gè)特征，然后從中去除R個(gè)特征，使得評價(jià)函數(shù)值最優(yōu)。( L> R )<2> 算法從全集開始，每輪先去除R個(gè)特征，然后加入L個(gè)特征，使得評價(jià)函數(shù)值最優(yōu)。( L< R )序列浮動選擇( Sequential Floating Selection )：序列浮動選擇由增L去R選擇算法發(fā)展而來，該算法與增L去R選擇算法的不同之處在于：序列浮動選擇的L與R不是固定的，而是“浮動”的，也就是會變化的。14、 線性SVM的目標(biāo)函數(shù)是什么？支持非線性SVM的基本解決思路是什么？非支持向量是可移除的嗎？為什么？既然計(jì)算代價(jià)會隨著樣本的數(shù)量縮放，哪種方法被用來減輕（alleviate）這個(gè)負(fù)擔(dān)？目標(biāo)函數(shù)：min 1/2 | subject to yi(xi+b) 1,i=1,2,，N 最大化Margin非線性SVM的基本思想是低維線性不可分，把它投影到高維空間中使線性可分。是的，可移除，因?yàn)樗鼘?gòu)成超平面不做貢獻(xiàn)。先聚類，找出中心點(diǎn)，對中心點(diǎn)用SVM進(jìn)行分類，以減輕負(fù)載。15、 非線性SVM是否和徑向基函數(shù)（radial basis function）具有一些相似性，如果有的話是什么？SVM和RBF超平面表達(dá)方式一樣，都是將低維線性不可分的數(shù)據(jù)映射到高維。只是優(yōu)化時(shí)目標(biāo)函數(shù)不同，SVM是最大化Margin，RBF是最小化錯(cuò)誤率。16、 如果需要設(shè)計(jì)一個(gè)臉部識別系統(tǒng)并且在這個(gè)系統(tǒng)中輸入的圖片樣本的維度和訓(xùn)練樣本的數(shù)量相比通常非常高，都有哪些處理步驟？對于每一步，你能列出一個(gè)或者多個(gè)解決方法嗎？怎么評價(jià)你設(shè)計(jì)的這個(gè)系統(tǒng)的錯(cuò)誤率？圖像輸入：使用攝像頭或者從圖庫中獲取。圖像預(yù)處理：由于光照，環(huán)境以及人為影響，大多數(shù)情況下，系統(tǒng)采集的原始照片來自不同背景，不同條件，收到隨機(jī)的干擾，這些圖片不能被直接利用。光線補(bǔ)償、高斯平滑處理。特征提?。嚎梢允褂肞CA進(jìn)行特征提取。訓(xùn)練分類器：使用SVM對已知樣本進(jìn)行分類。后處理如何評價(jià)：采用交叉驗(yàn)證，對原始數(shù)據(jù)進(jìn)行分組,一部分做為訓(xùn)練集(train set),另一部分做為驗(yàn)證集(validation set),首先用訓(xùn)練集對分類器進(jìn)行訓(xùn)練,在利用驗(yàn)證集來測試訓(xùn)練得到的模型(model),以此來做為評價(jià)分類器的性能指標(biāo)。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 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)化準(zhǔn)則，感知器（perceptron）學(xué)習(xí)和MSE（均方誤差）的區(qū)別？感知器學(xué)習(xí)：能夠處理線性可分的情況，如果線性不可分，則不具有收斂性，其優(yōu)化準(zhǔn)則是最小化錯(cuò)誤。MSE：能夠保證收斂性，但線性可分時(shí)不一定能夠找到實(shí)現(xiàn)分類的超平面，其優(yōu)化準(zhǔn)則是最小化訓(xùn)練數(shù)據(jù)到超平面的平方和。19、 多層感知器中，什么方法用來避免過擬合？權(quán)重衰減，及早終止，增加噪聲。20、 在RBF（徑向基函數(shù)）中，為什么在線性轉(zhuǎn)換之后要跟一個(gè)非線性轉(zhuǎn)換？哪些非監(jiān)督方法能夠用來選擇RBF center？低維線性不可分，映射到高維線性可分。隨機(jī)選擇、聚類、密度估計(jì)21、 結(jié)構(gòu)風(fēng)險(xiǎn)最小化的基本原則是什么？同時(shí)最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)和VC緯度，使二者達(dá)到平衡。22、 在kernel density estimation中，核獨(dú)立就表明特征獨(dú)立嗎？最大似然估計(jì)是怎樣被用來為KDE選擇bandwidth parameter的？樸素貝葉斯分類器的基本假設(shè)是什么？基本的KNN方法對噪聲特征敏感，哪種方法能夠用來改進(jìn)這個(gè)？不是；結(jié)合似然函數(shù)進(jìn)行交叉驗(yàn)證。經(jīng)常使用留一交叉驗(yàn)證的方法最大化偽似然。特征是類條件獨(dú)立的，公式在上面。對特征設(shè)置權(quán)重，以表達(dá)該特征的信息內(nèi)容或作用價(jià)值。如果度量相似度的距離公式中對特征賦予不同權(quán)重，特征的權(quán)重一般根據(jù)各個(gè)特征在分類中的作用確定，或者根據(jù)特征在訓(xùn)練樣本中的分類作用確定。23、 考慮錯(cuò)誤率，隨機(jī)子抽樣(random subsampling)方法和自助抽樣法（Bootstrap Method）的區(qū)別？隨機(jī)二次抽樣：無放回的采樣，一次數(shù)據(jù)只會被選擇一次。自助法：有放回的采樣，一個(gè)數(shù)據(jù)可能被選擇多次，更符合現(xiàn)實(shí)情況（在每次驗(yàn)證時(shí)增大方差）24、 Show that if X1 and X2 are two points in high dimensional space,the hyperplane(超平面）bisecting（二分）the segment(分段）with end points X1,X2,leaving X1 at its positive side, is given by (X1-X2)TX-1/2|X1|2+1/2|X2|2=0。25、 梯度下降和拉格朗日乘子法26、 點(diǎn)到超平面距離