模式識別與人工智能之四

1、Pattern Recognition & artificial IntelligenceLecture 4: 特征選擇與提取（三）,1,主要內(nèi)容,1.引言2 類別可分離性判據(jù)3.特征提取4 特征選擇,2,特征提取回顧 ： K-L變換, PCA, SVD,數(shù)據(jù)X：n行p列，代表p個樣本，每個樣本有n個特征KL變換和PCA：計算數(shù)據(jù)X的協(xié)方差矩陣C=E(XTX)，找出協(xié)方差矩陣的特征向量和特征值，提取前k (k&

2、lt;<n)個最大特征值對應(yīng)的特征向量做為新的變換基，稱為主成分，所對應(yīng)的特征值稱為主成分因子，或者主成分得分。,Note： KL and PCA don’t process the original data X directly, but the covariance matrix instead.,Cons: -> huge computing resources -> one di

3、mension reduce,3,特征提取回顧 ： K-L變換, PCA, SVD,SVD: 直接對數(shù)據(jù)樣本X進行變換，解決了PCA計算量大的問題，能夠同時對樣本和特征進行降維。可以用SVD來實現(xiàn)PCA。二者的具體關(guān)系如下：,PCA:,covariance matrix C can be decomposed with C = VLVT V: principle directions or principle axes (

4、eigenvector of C) L: diagonal matrix with eigenvalues λi in the decreasing order on the diagonal Principle components : Projections of the data X on the principal axe V

5、 PC = XV The j-th principal component is given by j-th column of PC,4,特征提取回顧 ： K-L變換, PCA, SVD,SVD: 直接對數(shù)據(jù)樣本X進行變換，解決了PCA計算量大的問題，能夠同時對樣本和特征進行降維?？梢杂肧VD來實現(xiàn)PCA。二者的具體關(guān)系如下：,SVD:,Singular value

6、decomposition of  data X is: X = USVT S is the diagonal matrix of singular values siIn SVD, the covariance matrix of X can be write as: C= E(XTX) =E( VSUTUSVT) = E (VS2VT) = VE(S2) VTIn P

7、CA, the covariance matrix of X is: C = VLVT,,,right singular vectors V are principal directionsprinciple components XV = USVTV = USSigular values are related with eigenvalues of covariance matrix via

8、 λi = E(si2),5,,特征選擇,6,特征選擇的過程：,產(chǎn)生過程( Generation Procedure )：按一定的搜索策略產(chǎn)生候選特征子集。評價函數(shù)( Evaluation Function ) ：通過某個評價函數(shù)來評估特征子集的優(yōu)劣。停止準則( Stopping Criterion )：停止準則是與評價函數(shù)相關(guān)的，一般是一個閾值，當(dāng)評價函數(shù)值達到這個

9、閾值后就可停止搜索。子集驗證：用來驗證最終所選子集的有效性。,7,評價函數(shù)：Filter 和 wrapper,Filter：通過分析特征子集內(nèi)部的信息來衡量特征子集的好壞,Wrapper：評價函數(shù)是一個分類器，采用特定特征子集對樣本集進行分類，根據(jù)分類的結(jié)果來衡量該特征子集的好壞,8,距離或可分性度量：距離度量有時候也稱作類別可分離判據(jù)、離散度準則,在統(tǒng)計模式識別中對類別的可分離性研究的比較深入。--歐幾里得距離、馬氏距離、巴氏距

10、離等相關(guān)性度量：用來度量特征和類別之間的相關(guān)性。--相關(guān)系數(shù)信息論度量：--信息增益、最小描述長度、互信息,評價函數(shù)：Filter,9,評價函數(shù)：對比,10,特征選擇方法 （搜索策略）,窮舉算法：對特征空間進行窮舉搜索（當(dāng)然也會采用剪枝等優(yōu)化），搜索出來的特征集對于樣本集是最優(yōu)的。這類算法的時間復(fù)雜度是指數(shù)級的。序列算法：這類算法實際上是一種貪心算法，算法時間復(fù)雜度較低，但是可能會陷入局部最優(yōu)值，不一定能找到全局最優(yōu)解。

11、隨機算法：隨機算法屬于一種近似算法，能找出問題的近似最優(yōu)解。每個隨機算法都需要設(shè)置一定的參數(shù)，這些參數(shù)的選擇很重要。,11,特征選擇方法 （搜索策略）,窮舉算法：窮舉搜索 Exhaustive Search (ES)分支限界法 Branch and Bound (B&B)序列算法：前向順序選擇后向順序選擇增L去R算法雙向搜索算法序列浮動選擇算法隨機算法：隨機產(chǎn)生序列選擇算法模擬退火算

12、法遺傳算法,12,從D個特征中選擇d個，可能組合q,窮舉搜索（ES）,計算所有可能的特征組合的J，選擇J最大的那組為最優(yōu)組合。這種方法計算量大，只適用于特征個數(shù)比較少的情況，運算量隨著特征維數(shù)的增加呈指數(shù)遞增，因此窮舉法雖然簡單卻難以實際應(yīng)用。,13,分支限界法（Branch and bounding, BAB）,Start from the full set of features and remove features usin

13、g depth first strategyMonotonicity property should be satisfied to apply the algorithmBranching is the constructing process of treeFor each tree level, a limited number of sub-trees is generated by deleting one fea

14、ture from the set of features from the parent nodeBounding is the process of finding optimal feature set by traversing the constructed tree,14,分支限界法（Branch and bounding, BAB）,Feature set => {x1, x2, x3, x4,……..xn }

15、 J(x1) < J(x1 ,x2) < J(x1, x2, x3) < ……..< J(x1, x2, x3, …. xn),15,分支限界法（Branch and bounding, BAB）,Construct an ordered tree by satisfying the Monotonicity property Let xj be the set

16、 of features obtained by removing j features y1 , y2 … yj from the set Y of all featuresXj = Y \ {y1 , y2 … yj }The monotonicity condition assumes that, for feature subsets x1 , x2 … xj where, x1 ? x2 ? x3 …

17、. ? xj The criterion function J fulfills, J(x1) < J(x2) < J(x3) < … < J(xj),16,分支限界法（Branch and bounding, BAB）,Traverse the tree from right to left in depth first search patternIf the value of the cr

18、iterion is less than the threshold (relevant to the most recent best subset) at a given node, All its successors will also have a value less than criterion valuePruningAnytime the criterion value J(xm) in some int

19、ernal node is found to be lower than the current bound, due to the Monotonicity condition the whole sub tree may be cut off and many computations may be omitted B&B creates tree with all possible combinations

20、of r element subsets from the n set, but searches only some of them,17,Root of the tree represents the set of all features (n) and leaves represent target subsets (r) of featuresFor each tree level, a limited number

21、of sub-trees is generated by deleting one feature from the set of features from the parent node,All features (n),Target subset (r),,Removed feature,BAB：properties,18,BAB：properties,In practice, we have only allowed varia

22、bles to be removed in increasing order. This removes unnecessary repetitions in the calculation. Therefore tree is not symmetrical,{ X1,X2,X3,X4 },{ X2,X3,X4 },{ X1,X3,X4 },Not in increasing order,X1,X2,{ X3,X4 },X2,{ X3

23、,X4 },X1,Repetition,,,19,BAB：properties,Number of leaf nodes in tree = Cnr Number of levels = n – rEx: No of leaf nodes = C32 = 3 No of levels = 3 – 2 = 1,3 features reduced to 2 featur

24、es,20,BAB：example,How to reduce 5 features in to 2 features using B & B Algorithm?Finding best 2 features from full set of features,1, 2, 3, 4, 5,? , ?,,21,BAB：example,Step1: Identify the Tree propertiesNo o

25、f levels = 5-2 = 3 (5 ? 4 ? 3? 2)No of leaf nodes = 5C2 = 10Choose a criterion function J(x).,22,BAB：example,1,2,3,4,5,2,3,4,5,1,3,4,5,1,2,4,5,3,L 0,2,1,L 1,Note : If feature 4 and 5 remove from initial states

26、, tree does not become a complete tree. There will be no features to remove in the next levels.,Step2: Branching,23,BAB：example,1,2,3,4,5,2,3,4,5,1,3,4,5,1,2,4,5,3,L 0,2,1,3,4,5,2,4,5,2,3,5,1,4,5,1,3,5,1,2,5,2,3,4,3

27、,4,4,L 1,L 2,Step2: Branching,24,BAB：example,Step3: Branching,1,2,3,4,5,2,3,4,5,1,3,4,5,1,2,4,5,3,L 0,2,1,3,4,5,2,4,5,2,3,5,1,4,5,1,3,5,1,2,5,4,5,3,5,3,4,2,5,2,4,2,3,1,5,1,4,1,3,1,2,2,3,4,3,4,4,3,4,5,4,5,5,4,5,5,5,L 1,L

28、2,L 3,25,BAB：example,Step3: Criterion Values,Assume the Criterion function J(X) will give following results which satisfied the Monotonicity Property,Criterion values,26,BAB：example,Step4: Back Tracking,Calculate the cri

29、terion values using J(x) function (values are Assumed)Set the right most value as the Bound (this branch has the minimum number of child nodes and edges),Set Bound,Current V = 8 Bound = 8,12,11,6,7,8,8,10,3,4,5,5,6

30、,7,6,7,9,27,BAB：example,Step4: Back Tracking,Backtrack along the tree (depth search) ifCurrent Node Value ≥ Bound Update the bound when backtracking reach to a leaf node,Update Bound,Current V = 9 Bound = 9,28,BA

31、B：example,Step4: Back Tracking,If Current Node Value ≤ BoundDiscard the below branches (Prune) Bound will not change,,X,Current V = 8 Bound = 9,29,BAB：example,Step4: Back Tracking,Repeat the previous steps,,X,,X,

32、Current V = 8 Bound = 9,30,BAB：example,Step4: Back Tracking,Maximum bound in leaf nodes = 9Optimal feature subset = {1,3}Note that the some subsets in L3 can be omitted without calculating,,X,,X,Current V = 6

33、 Bound = 9,,X,,X,{1,3},31,BAB：example,Reduce 10 features to 6 featuresNo of levels = 10 - 6 = 4 No of leaf nodes = 10C6 = 210,1, 2, 3, 4, 5,6,7,8,9,10,? ?,?,?,??,,n = 10 r = 6,32,BAB：Pseudo Code,3

34、3,BAB：pros and cons,Every B & B algorithm requires additional computationsNot only the target subsets of r features, but also their supersets n have to be evaluatedDoes not guarantee that enough sub-trees will be

35、cut off to keep the total number of criterion computations lower than their number in exhaustive searchIn the worst case, Criterion function would be computed in every tree nodeSame as the Exhaustive search,34,BAB：pro

36、s and cons,Criterion value computation is usually slower near to the rootEvaluated feature subsets are larger J(X1,X2…Xn)Sub tree cut-offs are less frequent near to the rootHigher criterion values following from lar

37、ger subsets are compared to the bound, which is updated in leavesThe B & B algorithm usually spends most of the time by tedious, less promising evaluation of the tree nodes in levels closer to the rootThis effect

38、 is to be expected, especially for r <<< n,35,Sequential Forward Selection（SFS）,36,SFS: Example,37,Sequential Backward Selection（SBS）,38,Plus-L Minus-R,39,bidirectional selection, （ BDS ),40,Sequential floating

39、select: SFFS, SFBS,41,爬山算法： Hill Climbing,爬山算法是一種簡單的貪心搜索算法，每次從當(dāng)前解的臨近解空間中選擇一個最優(yōu)解作為當(dāng)前解，直到達到一個局部最優(yōu)解。主要缺點是會陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。Example: 假設(shè)C點為當(dāng)前解，爬山算法搜索到A點這個局部最優(yōu)解就會停止搜索，因為在A點無論向那個方向小幅度移動都不能得到更優(yōu)的解。,【模擬退火算法】,42,模擬退火：Simula

40、ted Annealing,也是一種貪心算法，但是它的搜索過程引入了隨機因素。模擬退火算法以一定的概率來接受一個比當(dāng)前解要差的解，因此有可能會跳出這個局部的最優(yōu)解，達到全局的最優(yōu)解。Example：模擬退火算法在搜索到局部最優(yōu)解A后，會以一定的概率接受到E的移動。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動后會到達D點，于是就跳出了局部最大值A(chǔ),【模擬退火算法】,43,什么是物理退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機排

41、列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達到某種穩(wěn)定狀態(tài)。加溫過程、等溫過程、冷卻（退火）過程,【模擬退火算法】,44,算法的提出：模擬退火算法最早的思想是由Metropolis等(1953)提出的重要性采樣法，即以概率接受新狀態(tài)，稱為Metropolis準則，直到Kirkpatrick等(1983)將其應(yīng)用于組合優(yōu)化問題的求解，才得以廣泛應(yīng)用。算法的目的：解決NP復(fù)雜性問題；克服優(yōu)化過程陷入局部極?。豢朔?/p>

42、初值依賴性。,【模擬退火算法】,45,Metropolis準則(1953)—以概率接受新狀態(tài)：若在溫度T，當(dāng)前狀態(tài)i → 新狀態(tài)j的接受概率為P 注：概率 p=exp[-(Ej-Ei)/KT] 大于[0,1)區(qū)間的隨機數(shù)c 在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。,【模擬退火算法】,46,【模擬退火算法】,隨機產(chǎn)生一個初始解x0，令xbest＝

43、x0 ，并計算目標(biāo)函數(shù)值E(x0);設(shè)置初始溫度T(0)=To，迭代次數(shù)i = 1;Do while T(i) > Tmin for j = 1~k對當(dāng)前最優(yōu)解xbest按照某一鄰域函數(shù)，產(chǎn)生一新的解xnew。計算新的目標(biāo)函數(shù)值E(xnew) ，并計算目標(biāo)函數(shù)值的增量: ΔE = E(xnew) - E(xbest) 如果ΔE ＜0，則xbest = xnew；

44、 如果ΔE ＞0，則p = exp(- ΔE /T(i)); 如果c = random[0,1] < p， xbest = xnew; 否則xbest = xbest。 End for i = i ＋ 1； End Do輸出當(dāng)前最優(yōu)點，計算結(jié)束,47,【模擬退火算法】,三函數(shù)：狀

45、態(tài)（解）產(chǎn)生函數(shù)狀態(tài)接受函數(shù)溫度更新函數(shù)二準則：內(nèi)循環(huán)終止準則外循環(huán)終止準則,算法的關(guān)鍵點：三函數(shù)兩準則,48,【模擬退火算法】,狀態(tài)產(chǎn)生函數(shù)：盡可能保證產(chǎn)生的候選解遍布全部的解空間，即，具有廣泛的代表性。通常，狀態(tài)產(chǎn)生函數(shù)由兩部分組成，即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布產(chǎn)生侯選解的方式：由問題本身決定，通常在當(dāng)前解（狀態(tài)）的領(lǐng)域中間尋找產(chǎn)生侯選解的概率分布：一定概率接受候選解（均勻分布、正態(tài)分布、指數(shù)分布等）,4

46、9,【模擬退火算法】,狀態(tài)接受函數(shù)：原則：函數(shù)一般以概率的方式給出，不同接受函數(shù)的差別主要在于接受概率的形式不同。設(shè)計狀態(tài)接受概率，應(yīng)該遵循以下原則：在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率；隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??；當(dāng)溫度趨于零時，只能接受目標(biāo)函數(shù)下降的解。方法：狀態(tài)接受函數(shù)的引入是模擬退火算法實現(xiàn)全局搜索的最關(guān)鍵的因素，模擬退火算法中通常采用min[1,ex

47、p(-△C/t)]作為狀態(tài)接受函數(shù),50,【模擬退火算法】,溫度更新函數(shù)：溫度更新函數(shù)，即溫度的下降方式，用于在外循環(huán)中修改溫度值。常用的算法溫度下降函數(shù)：,,溫度與退溫時間對數(shù)成反比，溫度下降的速度很慢，當(dāng)常量a較大時，溫度t變得接近于0需要很長的時間。,α越接近1溫度下降越慢，且其大小可以不斷變化；,其中t0為起始溫度，K為算法溫度下降的總次數(shù)。,,,51,【模擬退火算法】,內(nèi)循環(huán)終止準則（Metropolis抽樣穩(wěn)定準則）：

48、1）檢驗?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；2）連續(xù)若干步的目標(biāo)值變化較?。?）按一定的步數(shù)抽樣，不管均值是否穩(wěn)定，也不管值是否不變或變化較小，反正迭代次數(shù)固定。外循環(huán)終止準則： 1）設(shè)置終止溫度的閾值； 2）設(shè)置外循環(huán)迭代次數(shù)； 3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變； 4）系統(tǒng)已達到穩(wěn)定狀態(tài)（概率分析方法）。,52,【模擬退火算法】,模擬退火怎么應(yīng)用在特征選擇中？,模擬退火里面的狀態(tài)i相當(dāng)于特征選擇里面的什么？模擬退火里面的

49、目標(biāo)函數(shù)該怎么選擇才能實現(xiàn)特征選擇？模擬退火里面的初始溫度和溫度下降方式?jīng)Q定了什么？,53,【模擬退火算法】,模擬退火怎么應(yīng)用在特征選擇中？,模擬退火里面的狀態(tài)I 選擇的特征子集,,假設(shè)有n個特征，需要提取d個特征，形成n*1的向量，選中的特征值為1，未選中的為0,初始特征子集,,特征子集更新,模擬退火里面的目標(biāo)函數(shù) 可由特征子集的相關(guān)系數(shù)矩陣來表示,,根據(jù)某一規(guī)則在初始特征子集附近選擇一個

50、新的特征，關(guān)閉一個原有特征，通過目標(biāo)函數(shù)判斷接受這個特征替換與否,,模擬退火里面的初始溫度和溫度下降方式?jīng)Q定了什么 決定了特征子集更換的次數(shù)，盡量避免落入局部最優(yōu)解。,,54,【遺傳算法】,Background： 種群(Population)：生物的進化以群體的形式進行，這樣的一個群體稱為種群?！　€體：組成種群的單個生物?！　』?#160;( Gene ) ：一個遺傳因子。 

51、　　染色體 ( Chromosome ) ：包含一組的基因。　　生存競爭，適者生存：對環(huán)境適應(yīng)度高的的個體參與繁殖的機會比較多，后代就會越來越多。適應(yīng)度低的個體參與繁殖的機會比較少，后代就會越來越少?！　∵z傳與變異：新個體會遺傳父母雙方各一部分的基因，同時有一定的概率發(fā)生基因變異。,簡單說來就是：繁殖過程，會發(fā)生基因交叉( Crossover ) ，基因突變 ( Mutation ) ，適應(yīng)度( Fitness

52、 )低的個體會被逐步淘汰，而適應(yīng)度高的個體會越來越多。那么經(jīng)過N代的自然選擇后，保存下來的個體都是適應(yīng)度很高的，其中很可能包含史上產(chǎn)生的適應(yīng)度最高的那個個體。,55,Background,基因鏈碼：1000101110110101000111,,個體（染色體）,,基因,【遺傳算法】,n個特征-> 基因鏈碼 (n個0和1組成的二進制碼)d 維特征子集->長度為d的染色體每個特征->基因,56,【遺傳算法】,基本遺傳算

53、法的組成（1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運行參數(shù),編碼：需要將問題的解編碼成字符串的形式才能使用遺傳算法。最簡單的一種編碼方式是二進制編碼,選擇：選擇一些染色體來產(chǎn)生下一代。一種常用的選擇策略是 “比例選擇”，也就是個體被選中的概率與其適應(yīng)度函數(shù)值成正比。假設(shè)群體的個體總數(shù)是M，那么那么一個體Xi被選中的概率為f(Xi)/( f(X1) + f(X2) + …….. +

54、 f(Xn) ) 。,適應(yīng)度函數(shù) ( Fitness Function )：用于評價某個染色體的適應(yīng)度，用f(x)表示。適應(yīng)度函數(shù)與目標(biāo)函數(shù)是正相關(guān)的，可對目標(biāo)函數(shù)作一些變形來得到適應(yīng)度函數(shù)。,57,【遺傳算法】,交叉(Crossover)：2條染色體交換部分基因，來構(gòu)造下一代的2條新的染色體。例如：交叉前： 00000|011100000000|10000 11100|000

55、001111110|00101交叉后： 00000|000001111110|10000 11100|011100000000|00101染色體交叉是以一定的概率發(fā)生的，這個概率記為Pc 。 變異(Mutation)：在繁殖過程，新產(chǎn)生的染色體中的基因會以一定的概率出錯，稱為變異。變異發(fā)生的概率記為Pm 。例如：變異前： 00000111

56、0000000010000變異后： 000001110000100010000,58,GA的框圖,【遺傳算法】,59,【遺傳算法】,基本遺傳算法偽代碼* Pc：交叉發(fā)生的概率；Pm：變異發(fā)生的概率* M：種群規(guī)模；G：終止進化的代數(shù)* Tf：進化產(chǎn)生的任何一個個體的適應(yīng)度函數(shù)超過Tf，則可以終止進化過程初始化Pm，Pc，M，G，Tf等參數(shù)。隨機產(chǎn)生第一代種群Popdo{ 計算種群

57、Pop中每一個體的適應(yīng)度F(i)?！　〕跏蓟辗N群newPop　　do　　{ 根據(jù)適應(yīng)度以比例選擇算法從種群Pop中選出2個個體　　　　if ( random ( 0 , 1 ) < Pc )　　　　{　　　　　　對2個個體按交叉概率Pc執(zhí)行交叉操作　　　　}　　　　if ( random ( 0 , 1 ) < Pm )　　　　{　　　　　　對2個個體按變異概率Pm執(zhí)行變異操作　　　　}

58、 將2個新個體加入種群newPop中 } until ( M個子代被創(chuàng)建 ) 用newPop取代Pop}until ( 任何染色體得分超過Tf， 或繁殖代數(shù)超過G ),60,討論：怎么利用特征選擇方法進行人臉識別？主要思想是什么？,61,總 結(jié),類可分性判據(jù)： 距離和概率（重點）特征提?。篜CA和SVD (思想和應(yīng)用,重點)特征選擇: (BAB, SA, GA,