Kernel Fisher discriminant analysis

In statistics, kernel Fisher discriminant analysis (KFD), ^[1] also known as generalized discriminant analysis ^[2] and kernel discriminant analysis, ^[3] is a kernelized version of linear discriminant analysis (LDA). It is named after Ronald Fisher.

Linear discriminant analysis

Intuitively, the idea of LDA is to find a projection where class separation is maximized. Given two sets of labeled data, ${\displaystyle \mathbf {C} _{1}}$ and ${\displaystyle \mathbf {C} _{2}}$, we can calculate the mean value of each class, ${\displaystyle \mathbf {m} _{1}}$ and ${\displaystyle \mathbf {m} _{2}}$, as

${\displaystyle \mathbf {m} _{i}={\frac {1}{l_{i}}}\sum _{n=1}^{l_{i}}\mathbf {x} _{n}^{i},}$

where ${\displaystyle l_{i}}$ is the number of examples of class ${\displaystyle \mathbf {C} _{i}}$. The goal of linear discriminant analysis is to give a large separation of the class means while also keeping the in-class variance small. ^[4] This is formulated as maximizing, with respect to ${\displaystyle \mathbf {w} }$, the following ratio:

${\displaystyle J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} }},}$

where ${\displaystyle \mathbf {S} _{B}}$ is the between-class covariance matrix and ${\displaystyle \mathbf {S} _{W}}$ is the total within-class covariance matrix:

${\displaystyle {\begin{aligned}\mathbf {S} _{B}&=(\mathbf {m} _{2}-\mathbf {m} _{1})(\mathbf {m} _{2}-\mathbf {m} _{1})^{\text{T}}\\\mathbf {S} _{W}&=\sum _{i=1,2}\sum _{n=1}^{l_{i}}(\mathbf {x} _{n}^{i}-\mathbf {m} _{i})(\mathbf {x} _{n}^{i}-\mathbf {m} _{i})^{\text{T}}.\end{aligned}}}$

The maximum of the above ratio is attained at

${\displaystyle \mathbf {w} \propto \mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1}).}$

as can be shown by the Lagrange multiplier method (sketch of proof):

Maximizing ${\displaystyle J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} }}}$ is equivalent to maximizing

${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} }$

subject to

${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} =1.}$

This, in turn, is equivalent to maximizing ${\displaystyle I(\mathbf {w} ,\lambda )=\mathbf {w} ^{\text{T}}\mathbf {S} _{B}\mathbf {w} -\lambda (\mathbf {w} ^{\text{T}}\mathbf {S} _{W}\mathbf {w} -1)}$, where ${\displaystyle \lambda }$ is the Lagrange multiplier.

At the maximum, the derivatives of ${\displaystyle I(\mathbf {w} ,\lambda )}$ with respect to ${\displaystyle \mathbf {w} }$ and ${\displaystyle \lambda }$ must be zero. Taking ${\displaystyle {\frac {dI}{d\mathbf {w} }}=\mathbf {0} }$ yields

${\displaystyle \mathbf {S} _{B}\mathbf {w} -\lambda \mathbf {S} _{W}\mathbf {w} =\mathbf {0} ,}$

which is trivially satisfied by ${\displaystyle \mathbf {w} =c\mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1})}$ and ${\displaystyle \lambda =(\mathbf {m} _{2}-\mathbf {m} _{1})^{\text{T}}\mathbf {S} _{W}^{-1}(\mathbf {m} _{2}-\mathbf {m} _{1}).}$

Extending LDA

To extend LDA to non-linear mappings, the data, given as the ${\displaystyle \ell }$ points ${\displaystyle \mathbf {x} _{i},}$ can be mapped to a new feature space, ${\displaystyle F,}$ via some function ${\displaystyle \phi .}$ In this new feature space, the function that needs to be maximized is ^[1]

${\displaystyle J(\mathbf {w} )={\frac {\mathbf {w} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {w} }{\mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} }},}$

where

${\displaystyle {\begin{aligned}\mathbf {S} _{B}^{\phi }&=\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)^{\text{T}}\\\mathbf {S} _{W}^{\phi }&=\sum _{i=1,2}\sum _{n=1}^{l_{i}}\left(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi }\right)\left(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi }\right)^{\text{T}},\end{aligned}}}$

and

${\displaystyle \mathbf {m} _{i}^{\phi }={\frac {1}{l_{i}}}\sum _{j=1}^{l_{i}}\phi (\mathbf {x} _{j}^{i}).}$

Further, note that ${\displaystyle \mathbf {w} \in F}$. Explicitly computing the mappings ${\displaystyle \phi (\mathbf {x} _{i})}$ and then performing LDA can be computationally expensive, and in many cases intractable. For example, ${\displaystyle F}$ may be infinitely dimensional. Thus, rather than explicitly mapping the data to ${\displaystyle F}$, the data can be implicitly embedded by rewriting the algorithm in terms of dot products and using kernel functions in which the dot product in the new feature space is replaced by a kernel function,${\displaystyle k(\mathbf {x} ,\mathbf {y} )=\phi (\mathbf {x} )\cdot \phi (\mathbf {y} )}$.

LDA can be reformulated in terms of dot products by first noting that ${\displaystyle \mathbf {w} }$ will have an expansion of the form ^[5]

${\displaystyle \mathbf {w} =\sum _{i=1}^{l}\alpha _{i}\phi (\mathbf {x} _{i}).}$

Then note that

${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {m} _{i}^{\phi }={\frac {1}{l_{i}}}\sum _{j=1}^{l}\sum _{k=1}^{l_{i}}\alpha _{j}k\left(\mathbf {x} _{j},\mathbf {x} _{k}^{i}\right)=\mathbf {\alpha } ^{\text{T}}\mathbf {M} _{i},}$

where

${\displaystyle (\mathbf {M} _{i})_{j}={\frac {1}{l_{i}}}\sum _{k=1}^{l_{i}}k(\mathbf {x} _{j},\mathbf {x} _{k}^{i}).}$

The numerator of ${\displaystyle J(\mathbf {w} )}$ can then be written as:

${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {w} =\mathbf {w} ^{\text{T}}\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)\left(\mathbf {m} _{2}^{\phi }-\mathbf {m} _{1}^{\phi }\right)^{\text{T}}\mathbf {w} =\mathbf {\alpha } ^{\text{T}}\mathbf {M} \mathbf {\alpha } ,\qquad {\text{where}}\qquad \mathbf {M} =(\mathbf {M} _{2}-\mathbf {M} _{1})(\mathbf {M} _{2}-\mathbf {M} _{1})^{\text{T}}.}$

Similarly, the denominator can be written as

${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} =\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } ,\qquad {\text{where}}\qquad \mathbf {N} =\sum _{j=1,2}\mathbf {K} _{j}(\mathbf {I} -\mathbf {1} _{l_{j}})\mathbf {K} _{j}^{\text{T}},}$

with the ${\displaystyle n^{\text{th}},m^{\text{th}}}$ component of ${\displaystyle \mathbf {K} _{j}}$ defined as ${\displaystyle k(\mathbf {x} _{n},\mathbf {x} _{m}^{j}),\mathbf {I} }$ is the identity matrix, and ${\displaystyle \mathbf {1} _{l_{j}}}$ the matrix with all entries equal to ${\displaystyle 1/l_{j}}$. This identity can be derived by starting out with the expression for ${\displaystyle \mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} }$ and using the expansion of ${\displaystyle \mathbf {w} }$ and the definitions of ${\displaystyle \mathbf {S} _{W}^{\phi }}$ and ${\displaystyle \mathbf {m} _{i}^{\phi }}$

${\displaystyle {\begin{aligned}\mathbf {w} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {w} &=\left(\sum _{i=1}^{l}\alpha _{i}\phi ^{\text{T}}(\mathbf {x} _{i})\right)\left(\sum _{j=1,2}\sum _{n=1}^{l_{j}}\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)^{\text{T}}\right)\left(\sum _{k=1}^{l}\alpha _{k}\phi (\mathbf {x} _{k})\right)\\&=\sum _{j=1,2}\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}\phi ^{\text{T}}(\mathbf {x} _{i})\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)\left(\phi (\mathbf {x} _{n}^{j})-\mathbf {m} _{j}^{\phi }\right)^{\text{T}}\alpha _{k}\phi (\mathbf {x} _{k})\right)\\&=\sum _{j=1,2}\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})-{\frac {1}{l_{j}}}\sum _{p=1}^{l_{j}}\alpha _{i}k(\mathbf {x} _{i},\mathbf {x} _{p}^{j})\right)\left(\alpha _{k}k(\mathbf {x} _{k},\mathbf {x} _{n}^{j})-{\frac {1}{l_{j}}}\sum _{q=1}^{l_{j}}\alpha _{k}k(\mathbf {x} _{k},\mathbf {x} _{q}^{j})\right)\\&=\sum _{j=1,2}\left(\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}\alpha _{k}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{n}^{j})-{\frac {2\alpha _{i}\alpha _{k}}{l_{j}}}\sum _{p=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{p}^{j})+{\frac {\alpha _{i}\alpha _{k}}{l_{j}^{2}}}\sum _{p=1}^{l_{j}}\sum _{q=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{p}^{j})k(\mathbf {x} _{k},\mathbf {x} _{q}^{j})\right)\right)\\&=\sum _{j=1,2}\left(\sum _{i=1}^{l}\sum _{n=1}^{l_{j}}\sum _{k=1}^{l}\left(\alpha _{i}\alpha _{k}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{n}^{j})-{\frac {\alpha _{i}\alpha _{k}}{l_{j}}}\sum _{p=1}^{l_{j}}k(\mathbf {x} _{i},\mathbf {x} _{n}^{j})k(\mathbf {x} _{k},\mathbf {x} _{p}^{j})\right)\right)\\[6pt]&=\sum _{j=1,2}\mathbf {\alpha } ^{\text{T}}\mathbf {K} _{j}\mathbf {K} _{j}^{\text{T}}\mathbf {\alpha } -\mathbf {\alpha } ^{\text{T}}\mathbf {K} _{j}\mathbf {1} _{l_{j}}\mathbf {K} _{j}^{\text{T}}\mathbf {\alpha } \\[4pt]&=\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } .\end{aligned}}}$

With these equations for the numerator and denominator of ${\displaystyle J(\mathbf {w} )}$, the equation for ${\displaystyle J}$ can be rewritten as

${\displaystyle J(\mathbf {\alpha } )={\frac {\mathbf {\alpha } ^{\text{T}}\mathbf {M} \mathbf {\alpha } }{\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } }}.}$

Then, differentiating and setting equal to zero gives

${\displaystyle (\mathbf {\alpha } ^{\text{T}}\mathbf {M} \mathbf {\alpha } )\mathbf {N} \mathbf {\alpha } =(\mathbf {\alpha } ^{\text{T}}\mathbf {N} \mathbf {\alpha } )\mathbf {M} \mathbf {\alpha } .}$

Since only the direction of ${\displaystyle \mathbf {w} }$, and hence the direction of ${\displaystyle \mathbf {\alpha } ,}$ matters, the above can be solved for ${\displaystyle \mathbf {\alpha } }$ as

${\displaystyle \mathbf {\alpha } =\mathbf {N} ^{-1}(\mathbf {M} _{2}-\mathbf {M} _{1}).}$

Note that in practice, ${\displaystyle \mathbf {N} }$ is usually singular and so a multiple of the identity is added to it ^[1]

${\displaystyle \mathbf {N} _{\epsilon }=\mathbf {N} +\epsilon \mathbf {I} .}$

Given the solution for ${\displaystyle \mathbf {\alpha } }$, the projection of a new data point is given by ^[1]

${\displaystyle y(\mathbf {x} )=(\mathbf {w} \cdot \phi (\mathbf {x} ))=\sum _{i=1}^{l}\alpha _{i}k(\mathbf {x} _{i},\mathbf {x} ).}$

Multi-class KFD

The extension to cases where there are more than two classes is relatively straightforward. ^{[2] [6] [7]} Let ${\displaystyle c}$ be the number of classes. Then multi-class KFD involves projecting the data into a ${\displaystyle (c-1)}$-dimensional space using ${\displaystyle (c-1)}$ discriminant functions

${\displaystyle y_{i}=\mathbf {w} _{i}^{\text{T}}\phi (\mathbf {x} )\qquad i=1,\ldots ,c-1.}$

This can be written in matrix notation

${\displaystyle \mathbf {y} =\mathbf {W} ^{\text{T}}\phi (\mathbf {x} ),}$

where the ${\displaystyle \mathbf {w} _{i}}$ are the columns of ${\displaystyle \mathbf {W} }$. ^[6] Further, the between-class covariance matrix is now

${\displaystyle \mathbf {S} _{B}^{\phi }=\sum _{i=1}^{c}l_{i}(\mathbf {m} _{i}^{\phi }-\mathbf {m} ^{\phi })(\mathbf {m} _{i}^{\phi }-\mathbf {m} ^{\phi })^{\text{T}},}$

where ${\displaystyle \mathbf {m} ^{\phi }}$ is the mean of all the data in the new feature space. The within-class covariance matrix is

${\displaystyle \mathbf {S} _{W}^{\phi }=\sum _{i=1}^{c}\sum _{n=1}^{l_{i}}(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi })(\phi (\mathbf {x} _{n}^{i})-\mathbf {m} _{i}^{\phi })^{\text{T}},}$

The solution is now obtained by maximizing

${\displaystyle J(\mathbf {W} )={\frac {\left|\mathbf {W} ^{\text{T}}\mathbf {S} _{B}^{\phi }\mathbf {W} \right|}{\left|\mathbf {W} ^{\text{T}}\mathbf {S} _{W}^{\phi }\mathbf {W} \right|}}.}$

The kernel trick can again be used and the goal of multi-class KFD becomes ^[7]

${\displaystyle \mathbf {A} ^{*}={\underset {\mathbf {A} }{\operatorname {argmax} }}={\frac {\left|\mathbf {A} ^{\text{T}}\mathbf {M} \mathbf {A} \right|}{\left|\mathbf {A} ^{\text{T}}\mathbf {N} \mathbf {A} \right|}},}$

where ${\displaystyle A=[\mathbf {\alpha } _{1},\ldots ,\mathbf {\alpha } _{c-1}]}$ and

${\displaystyle {\begin{aligned}M&=\sum _{j=1}^{c}l_{j}(\mathbf {M} _{j}-\mathbf {M} _{*})(\mathbf {M} _{j}-\mathbf {M} _{*})^{\text{T}}\\N&=\sum _{j=1}^{c}\mathbf {K} _{j}(\mathbf {I} -\mathbf {1} _{l_{j}})\mathbf {K} _{j}^{\text{T}}.\end{aligned}}}$

The ${\displaystyle \mathbf {M} _{i}}$ are defined as in the above section and ${\displaystyle \mathbf {M} _{*}}$ is defined as

${\displaystyle (\mathbf {M} _{*})_{j}={\frac {1}{l}}\sum _{k=1}^{l}k(\mathbf {x} _{j},\mathbf {x} _{k}).}$

${\displaystyle \mathbf {A} ^{*}}$ can then be computed by finding the ${\displaystyle (c-1)}$ leading eigenvectors of ${\displaystyle \mathbf {N} ^{-1}\mathbf {M} }$. ^[7] Furthermore, the projection of a new input, ${\displaystyle \mathbf {x} _{t}}$, is given by ^[7]

${\displaystyle \mathbf {y} (\mathbf {x} _{t})=\left(\mathbf {A} ^{*}\right)^{\text{T}}\mathbf {K} _{t},}$

where the ${\displaystyle i^{th}}$ component of ${\displaystyle \mathbf {K} _{t}}$ is given by ${\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{t})}$.

Classification using KFD

In both two-class and multi-class KFD, the class label of a new input can be assigned as ^[7]

${\displaystyle f(\mathbf {x} )=arg\min _{j}D(\mathbf {y} (\mathbf {x} ),{\bar {\mathbf {y} }}_{j}),}$

where ${\displaystyle {\bar {\mathbf {y} }}_{j}}$ is the projected mean for class ${\displaystyle j}$ and ${\displaystyle D(\cdot ,\cdot )}$ is a distance function.

Applications

Kernel discriminant analysis has been used in a variety of applications. These include:

• Face recognition ^{[3] [8] [9]} and detection ^{[10] [11]}
• Hand-written digit recognition ^{[1] [12]}
• Palmprint recognition ^[13]
• Classification of malignant and benign cluster microcalcifications ^[14]
• Seed classification ^[2]
• Search for the Higgs Boson at CERN ^[15]

See also

• Factor analysis
• Kernel principal component analysis
• Kernel trick
• Linear discriminant analysis

References

1. Mika, S; Rätsch, G.; Weston, J.; Schölkopf, B.; Müller, KR (1999). "Fisher discriminant analysis with kernels". Neural Networks for Signal Processing IX: Proceedings of the 1999 IEEE Signal Processing Society Workshop (Cat. No.98TH8468). Vol. IX. pp. 41–48. CiteSeerX   10.1.1.35.9904 . doi:10.1109/NNSP.1999.788121. ISBN   978-0-7803-5673-3. S2CID   8473401.
2. Baudat, G.; Anouar, F. (2000). "Generalized discriminant analysis using a kernel approach". Neural Computation. 12 (10): 2385–2404. CiteSeerX   10.1.1.412.760 . doi:10.1162/089976600300014980. PMID   11032039. S2CID   7036341.
3. Li, Y.; Gong, S.; Liddell, H. (2003). "Recognising trajectories of facial identities using kernel discriminant analysis". Image and Vision Computing. 21 (13–14): 1077–1086. CiteSeerX   10.1.1.2.6315 . doi:10.1016/j.imavis.2003.08.010.
4. Bishop, CM (2006). Pattern Recognition and Machine Learning. New York, NY: Springer.
5. Scholkopf, B; Herbrich, R.; Smola, A. (2001). "A Generalized Representer Theorem". Computational Learning Theory. Lecture Notes in Computer Science. Vol. 2111. pp. 416–426. CiteSeerX   10.1.1.42.8617 . doi:10.1007/3-540-44581-1_27. ISBN   978-3-540-42343-0.
6. Duda, R.; Hart, P.; Stork, D. (2001). Pattern Classification. New York, NY: Wiley.
7. Zhang, J.; Ma, K.K. (2004). "Kernel fisher discriminant for texture classification".{{cite journal}}: Cite journal requires |journal= (help)
8. Liu, Q.; Lu, H.; Ma, S. (2004). "Improving kernel Fisher discriminant analysis for face recognition". IEEE Transactions on Circuits and Systems for Video Technology. 14 (1): 42–49. doi:10.1109/tcsvt.2003.818352. S2CID   39657721.
9. Liu, Q.; Huang, R.; Lu, H.; Ma, S. (2002). "Face recognition using kernel-based Fisher discriminant analysis". IEEE International Conference on Automatic Face and Gesture Recognition.
10. Kurita, T.; Taguchi, T. (2002). "A modification of kernel-based Fisher discriminant analysis for face detection". Proceedings of Fifth IEEE International Conference on Automatic Face Gesture Recognition. pp. 300–305. CiteSeerX   10.1.1.100.3568 . doi:10.1109/AFGR.2002.1004170. ISBN   978-0-7695-1602-8. S2CID   7581426.
11. Feng, Y.; Shi, P. (2004). "Face detection based on kernel fisher discriminant analysis". IEEE International Conference on Automatic Face and Gesture Recognition.
12. Yang, J.; Frangi, AF; Yang, JY; Zang, D., Jin, Z. (2005). "KPCA plus LDA: a complete kernel Fisher discriminant framework for feature extraction and recognition". IEEE Transactions on Pattern Analysis and Machine Intelligence. 27 (2): 230–244. CiteSeerX   10.1.1.330.1179 . doi:10.1109/tpami.2005.33. PMID   15688560. S2CID   9771368.
13. Wang, Y.; Ruan, Q. (2006). "Kernel fisher discriminant analysis for palmprint recognition". International Conference on Pattern Recognition.
14. Wei, L.; Yang, Y.; Nishikawa, R.M.; Jiang, Y. (2005). "A study on several machine-learning methods for classification of malignant and benign clustered microcalcifications". IEEE Transactions on Medical Imaging. 24 (3): 371–380. doi:10.1109/tmi.2004.842457. PMID   15754987. S2CID   36691320.
15. Malmgren, T. (1997). "An iterative nonlinear discriminant analysis program: IDA 1.0". Computer Physics Communications. 106 (3): 230–236. Bibcode:1997CoPhC.106..230M. doi:10.1016/S0010-4655(97)00100-8.

External links

• Kernel Discriminant Analysis in C# - C# code to perform KFD.
• Matlab Toolbox for Dimensionality Reduction - Includes a method for performing KFD.
• Handwriting Recognition using Kernel Discriminant Analysis - C# code that demonstrates handwritten digit recognition using KFD.