Graph Embedding and Extensions: A General Framework for ...

Graph Embedding and Extensions: A General Framework for Dimensionality Reduction Keywords: Dimensionality reduction, manifold learning, subspace learning, graph embedding framework. 1.Introduction Techniques for dimensionality reduction Linear: PCA/LDA/LPP... Nonlinear: ISOMAP/Laplacian Eigenmap/LLE... Linear Nonlinear: kernel trick

Graph embedding framework A unified view for understanding and explaining many po pular algorithms such as the ones mentioned above. A platform for developing new dimension reduction algori thms. 2.Graph embedding 2.1Graph embedding Let X [ x1 ,...x N ], xi R m

need to find m is often very large so we F : x y, y R m ' , m' m N N G

X , W , W R Intrinsic graph: --similarity matrix

Penalty graph: G p X , W p , W p R N N --the similarity to be suppressed in the dimension-reduced feature space Y Our graph-preserving criterion is: 2 * y arg min yi y j Wij arg min y T Ly y T By d

y T By d i j L D W , Dii Wij i j L is called Laplacian matrix B typically is diagonal for scale normalization or Lmatrix of the penalty graph Linearization:

y X T w 2 T w* arg min yi y j Wij arg min w XLX w w ' XBXwd i i or w ' w d w ' XBXwd or w ' w d

Kernelization: : x T T 2 T * arg min K i K j Wij arg min KLK ' KBK d i i

or ' K d ' KBK d or ' K d k ( xi , x j ) ( xi ) ( xi ) Both can be obtained by solving: Lv Bv L L, XLX T , KLK ; B I , B, K , XBX T Tensorization:

( w1...wn )* arg min X w ...w f ( w1 ...wn ) d i j i 1 n

2 X j w1... wn Wij 2.2General Framework for Dimensionality Reductio n The adjacency graphs for PCA and LDA. (a) Constraint and intrinsic graph in PCA. (b) Penalty and intrinsic graphs in LDA. 2.3 Related Works and Discussions 2.3.1 Kernel Interpretation and Out-of-Sample Extensi

on Ham et al. [13] proposed a kernel interpretation of KPC A,ISOMAP, LLE, and Laplacian Eigenmap Bengio et al. [4] presented a method for computing the l ow dimensional representation of out-of-sample data. Comparison: Kernel Interpretation Graph embeding normalized similarity matrix unsupervised learning laplacian matrix

both supervised&unsupervised 2.3.2 Brands Work [5] Brands Work can be viewed as a special case of the graph embedding framework y * arg max y T Wy y T Dy 1 y * arg min y T ( D W ) y

y T Dy 1 2.3.3 Laplacian Eigenmap [3] and LPP [10] Single graph B=D Nonnegative similarity matrix Although [10] attempts to use LPP to explain PC A and LDA, this explanation is incomplete. The constraint matrix B is fixed to D in LPP, while the constraint matrix of LDA is comes from a penalty graph t hat connects all samples with equal weights;hence, LPP cannot explain LPP. Also,a minimization algorithm, does not explain why PCA maximizes the objective function.

3 MARGINAL FISHER ANALYSIS 3.1 Marginal Fisher Analysis Limitation of LDA:data distribution assumption limited available projection directions MFA overcomed the limitation by characterizing intraclass c ompactness and interclass separability. intrinsic graph: each sample is connected to its k1 nearest neighbors of the same class (intraclass compactness) penalty graph: each sample is connected to its k2 nearest neighbors of other classes

(interclass separability) Procedure of MFA PCA projection Constructing the intraclass compactness and int erclass separability graphs. Marginal Fisher Criterion Output the final linear projection direction Advantages of MFA The available projection directions are

much greater than that of LDA There is no assumption on the data distribution of each class Without prior information on data distributions KMFA Projection direction: The distance between sample xi and xj is For a new data point x, its projection to the derived

optimal direction is obtained as TMFA: 4.Experiments 4.1face recognition 4.1.1 MFA>Fisherface(LDA+PCA)>PCA PCA+MFA>PCA+LDA>PCA 4.1.2 Kernel trick KDA>LDA,KMFA>MFA

KMFA>PCA,Fisherface,LPP Trainingset Adequate: LPP > Fisherface ,PCA Inadequate: Fisherface > LPP>PCA anyway, MFA>=LPP Performance can be substantially improved by e xploring a certain range of PCA dimensions first. PCA+MFA>MFA,Bayesian face >PCA,Fisherface,LPP Tensor representation brings encouraging impro vements compared with vector-based algorithms

it is critical to collect sufficient samples for all su bjects! 4.2 A Non-Gaussian Case 5.CONCLUSION AND FUTURE WORK All possible extensions of the algorithms m entioned in this paper Combination of the kernel trick and tensori zation The selection of parameters k1 and k2 How to utilize higher order statistics of the

data set in the graph embedding framewor k?

Recently Viewed Presentations

• Como los otros mandatos de tú, Ud. Y Uds., conecta el complemento al fin del verbo afirmativo o antes del verbo negativo: No quita la -S. Por Ejemplo: Let´swashthe car. Let´swashit. Lavémoslo. (el coche) Let´snotseethemovie. Let´snotseeit. No la veamos. (la...
• The benefits of exercise on cardiometabolic risk factors are acute (lasting hours to days) and chronic, highlighting the value of regular exercise participation on most days of the week (as opposed to one long exercise activity a week)
• The State of the Art in Supporting "Big Data" by Michael Stonebraker * What is "Big Data" Too much Volume (I have too much data) Too much Velocity (Its coming at me too fast) Too much Variety (Its coming at...
• Performance evaluation: Formulas, computational techniques, asymptotic behavior… Design and control. Inference and estimation: Less than 100 serious papers. 1st: " The Statistical Analysis of Congestion ", D. R. Cox, 1955. Bib: " Parameter and State Estimation in Queues and Related...
• Chapter 25. Biomolecules: Carbohydrates ... monosaccharide pentose aldose all of these none of these How many stereoisomers are possible for the aldotetrose class of carbohydrates? one two three four five Which of the following sugars is the key carbohydrate energy-reserve...
• Data menunjukkan bahwa kejadian itu terjadi kira-kira 2100 tahun sebelum masehi. Dari beberapa buku juga mengemukan bahwa sampai kira-kira tahun 1600 sesudah Masehi, busur dan panah merupakan senjata utama setiap negara dan bangsa untuk berperang.
• Sample Quote. The Great Gatsby, Nick repeating what George Wilson says: "Maybe you got some friend that I could telephone for, George?" This was a forlorn hope—he was almost sure that Wilson had no friend: there was not enough of...
• C. Horstmann, Big Java + W. Savitch, Absolute Java CS1 Use Blue J, CS2 Dr. Java Roles of Variables in OOP Petri Gerdt, Pauli Byckling, Jorma Sajaniemi, University of Joensuu, Roles can be assigned to occurrences of variables in programs...