Kernel Fisher discriminant analysis

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

: $$

\mathbf{m}_i = \frac{1}{l_i}\sum_{n=1}^{l_i}\mathbf{x}_n^i,

where $l\_i$ is the number of examples of class $\backslash 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.{{cite book|last=Bishop|first=CM|title=Pattern Recognition and Machine Learning|year=2006|publisher=Springer|location=New York, NY}} This is formulated as maximizing, with respect to $\backslash mathbf\{w\}$, the following ratio:

: $$

J(\mathbf{w}) = \frac{\mathbf{w}^{\text{T}}\mathbf{S}_B\mathbf{w}}{\mathbf{w}^{\text{T}}\mathbf{S}_W\mathbf{w}},

where $\backslash mathbf\{S\}\_B$ is the between-class covariance matrix and $\backslash mathbf\{S\}\_W$ is the total within-class covariance matrix:

: $$

\begin{align}

\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{align}

The maximum of the above ratio is attained at

: $$

\mathbf{w} \propto \mathbf{S}^{-1}_W(\mathbf{m}_2-\mathbf{m}_1).

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

Maximizing $J(\backslash mathbf\{w\})\; =\; \backslash frac\{\backslash mathbf\{w\}^\{\backslash text\{T\}\}\backslash mathbf\{S\}\_B\backslash mathbf\{w\}\}\{\backslash mathbf\{w\}^\{\backslash text\{T\}\}\backslash mathbf\{S\}\_W\backslash mathbf\{w\}\}$ is equivalent to maximizing

: $\backslash mathbf\{w\}^\{\backslash text\{T\}\}\backslash mathbf\{S\}\_B\backslash mathbf\{w\}$

subject to

:$\backslash mathbf\{w\}^\{\backslash text\{T\}\}\backslash mathbf\{S\}\_W\backslash mathbf\{w\}\; =\; 1\; .$

This, in turn, is equivalent to maximizing $I(\backslash mathbf\{w\},\; \backslash lambda)\; =\; \backslash mathbf\{w\}^\{\backslash text\{T\}\}\backslash mathbf\{S\}\_B\backslash mathbf\{w\}\; -\; \backslash lambda\; (\backslash mathbf\{w\}^\{\backslash text\{T\}\}\backslash mathbf\{S\}\_W\backslash mathbf\{w\}\; -\; 1)$, where $\backslash lambda$ is the Lagrange multiplier.

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

: $\backslash mathbf\{S\}\_B\backslash mathbf\{w\}\; -\; \backslash lambda\; \backslash mathbf\{S\}\_W\; \backslash mathbf\{w\}\; =\; \backslash mathbf\{0\},$

which is trivially satisfied by $\backslash mathbf\{w\}\; =\; c\; \backslash mathbf\{S\}^\{-1\}\_W(\backslash mathbf\{m\}\_2-\backslash mathbf\{m\}\_1)$ and $\backslash lambda\; =\; (\backslash mathbf\{m\}\_2-\backslash mathbf\{m\}\_1)^\{\backslash text\{T\}\}\; \backslash mathbf\{S\}^\{-1\}\_W(\backslash mathbf\{m\}\_2-\backslash mathbf\{m\}\_1).$

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

: $J(\backslash mathbf\{w\})\; =\; \backslash frac\{\backslash mathbf\{w\}^\{\backslash text\{T\}\}\backslash mathbf\{S\}\_B^\{\backslash phi\}\backslash mathbf\{w\}\}\{\backslash mathbf\{w\}^\{\backslash text\{T\}\}\backslash mathbf\{S\}\_W^\{\backslash phi\}\backslash mathbf\{w\}\},$

where

: $$

\begin{align}

\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{align}

and

: $\backslash mathbf\{m\}\_i^\{\backslash phi\}\; =\; \backslash frac\{1\}\{l\_i\}\backslash sum\_\{j=1\}^\{l\_i\}\backslash phi(\backslash mathbf\{x\}\_j^i).$

Further, note that $\backslash mathbf\{w\}\backslash in\; F$. Explicitly computing the mappings $\backslash phi(\backslash mathbf\{x\}\_i)$ and then performing LDA can be computationally expensive, and in many cases intractable. For example, $F$ may be infinite dimensional. Thus, rather than explicitly mapping the data to $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,$k(\backslash mathbf\{x\},\backslash mathbf\{y\})\; =\backslash phi(\; \backslash mathbf\{x\})\; \backslash cdot\backslash phi(\backslash mathbf\{y\})$.

LDA can be reformulated in terms of dot products by first noting that $\backslash mathbf\{w\}$ will have an expansion of

the form{{cite book|last=Scholkopf|first=B|author2=Herbrich, R. |author3=Smola, A. |title=Computational Learning Theory|chapter=A Generalized Representer Theorem|volume=2111|pages=416–426|year=2001|doi=10.1007/3-540-44581-1_27|citeseerx=10.1.1.42.8617|series=Lecture Notes in Computer Science|isbn=978-3-540-42343-0}}

: $\backslash mathbf\{w\}\; =\; \backslash sum\_\{i=1\}^l\backslash alpha\_i\backslash phi(\backslash mathbf\{x\}\_i).$

Then note that

: $\backslash mathbf\{w\}^\{\backslash text\{T\}\}\backslash mathbf\{m\}\_i^\{\backslash phi\}\; =\; \backslash frac\{1\}\{l\_i\}\backslash sum\_\{j=1\}^\{l\}\backslash sum\_\{k=1\}^\{l\_i\}\backslash alpha\_jk\; \backslash left\; (\backslash mathbf\{x\}\_j,\backslash mathbf\{x\}\_k^i\; \backslash right\; )\; =\; \backslash mathbf\{\backslash alpha\}^\{\backslash text\{T\}\}\backslash mathbf\{M\}\_i,$

where

: $(\backslash mathbf\{M\}\_i)\_j\; =\; \backslash frac\{1\}\{l\_i\}\backslash sum\_\{k=1\}^\{l\_i\}k(\backslash mathbf\{x\}\_j,\backslash mathbf\{x\}\_k^i).$

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

: $\backslash mathbf\{w\}^\{\backslash text\{T\}\}\backslash mathbf\{S\}\_B^\{\backslash phi\}\backslash mathbf\{w\}\; =\; \backslash mathbf\{w\}^\{\backslash text\{T\}\}\; \backslash left\; (\backslash mathbf\{m\}\_2^\{\backslash phi\}-\backslash mathbf\{m\}\_1^\{\backslash phi\}\; \backslash right\; )\; \backslash left\; (\backslash mathbf\{m\}\_2^\{\backslash phi\}-\backslash mathbf\{m\}\_1^\{\backslash phi\}\; \backslash right\; )^\{\backslash text\{T\}\}\backslash mathbf\{w\}\; =\; \backslash mathbf\{\backslash alpha\}^\{\backslash text\{T\}\}\backslash mathbf\{M\}\backslash mathbf\{\backslash alpha\},\; \backslash qquad\; \backslash text\{where\}\; \backslash qquad\; \backslash mathbf\{M\}\; =\; (\backslash mathbf\{M\}\_2-\backslash mathbf\{M\}\_1)(\backslash mathbf\{M\}\_2-\backslash mathbf\{M\}\_1)^\{\backslash text\{T\}\}.$

Similarly, the denominator can be written as

: $\backslash mathbf\{w\}^\{\backslash text\{T\}\}\backslash mathbf\{S\}\_W^\{\backslash phi\}\backslash mathbf\{w\}=\backslash mathbf\{\backslash alpha\}^\{\backslash text\{T\}\}\backslash mathbf\{N\}\backslash mathbf\{\backslash alpha\},\backslash qquad\; \backslash text\{where\}\; \backslash qquad\; \backslash mathbf\{N\}\; =\; \backslash sum\_\{j=1,2\}\backslash mathbf\{K\}\_j(\backslash mathbf\{I\}-\backslash mathbf\{1\}\_\{l\_j\})\backslash mathbf\{K\}\_j^\{\backslash text\{T\}\},$

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

: $$

\begin{align}

\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_ik(\mathbf{x}_i,\mathbf{x}_n^j)-\frac{1}{l_j}\sum_{p=1}^{l_j}\alpha_ik(\mathbf{x}_i,\mathbf{x}_p^j)\right)

\left(\alpha_kk(\mathbf{x}_k,\mathbf{x}_n^j)-\frac{1}{l_j}\sum_{q=1}^{l_j}\alpha_kk(\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_kk(\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_kk(\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{align}

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

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

Then, differentiating and setting equal to zero gives

: $(\backslash mathbf\{\backslash alpha\}^\{\backslash text\{T\}\}\backslash mathbf\{M\}\backslash mathbf\{\backslash alpha\})\backslash mathbf\{N\}\backslash mathbf\{\backslash alpha\}\; =\; (\backslash mathbf\{\backslash alpha\}^\{\backslash text\{T\}\}\backslash mathbf\{N\}\backslash mathbf\{\backslash alpha\})\backslash mathbf\{M\}\backslash mathbf\{\backslash alpha\}.$

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

: $\backslash mathbf\{\backslash alpha\}\; =\; \backslash mathbf\{N\}^\{-1\}(\backslash mathbf\{M\}\_2-\; \backslash mathbf\{M\}\_1).$

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

: $\backslash mathbf\{N\}\_\{\backslash epsilon\}\; =\; \backslash mathbf\{N\}+\backslash epsilon\backslash mathbf\{I\}.$

Given the solution for $\backslash mathbf\{\backslash alpha\}$, the projection of a new data point is given by

: $y(\backslash mathbf\{x\})\; =\; (\backslash mathbf\{w\}\backslash cdot\backslash phi(\backslash mathbf\{x\}))\; =\; \backslash sum\_\{i=1\}^l\backslash alpha\_ik(\backslash mathbf\{x\}\_i,\backslash mathbf\{x\}).$

The extension to cases where there are more than two classes is relatively straightforward.{{cite book|last=Duda|first=R. |author2=Hart, P. |author3=Stork, D.|title=Pattern Classification|year=2001|publisher=Wiley|location=New York, NY}}{{cite journal|last=Zhang|first=J.|author2=Ma, K.K.|title=Kernel fisher discriminant for texture classification|year=2004}} Let $c$ be the number of classes. Then multi-class KFD involves projecting the data into a $(c-1)$-dimensional space using $(c-1)$ discriminant functions

: $$

y_i = \mathbf{w}_i^{\text{T}}\phi(\mathbf{x}) \qquad i= 1,\ldots,c-1.

This can be written in matrix notation

: $$

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

where the $\backslash mathbf\{w\}\_i$ are the columns of $\backslash mathbf\{W\}$. Further, the between-class covariance matrix is now

: $$

\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 $\backslash mathbf\{m\}^\backslash phi$ is the mean of all the data in the new feature space. The within-class covariance matrix is

: $$

\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

: $$

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

: $$

\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 $A\; =\; [\backslash mathbf\{\backslash alpha\}\_1,\backslash ldots,\backslash mathbf\{\backslash alpha\}\_\{c-1\}]$ and

: $$

\begin{align}

M & = \sum_{j=1}^cl_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{align}

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

: $$

(\mathbf{M}_{*})_j = \frac{1}{l}\sum_{k=1}^{l}k(\mathbf{x}_j,\mathbf{x}_k).

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

: $$

\mathbf{y}(\mathbf{x}_t) = \left(\mathbf{A}^{*}\right)^{\text{T}}\mathbf{K}_t,

where the $i^\{th\}$ component of $\backslash mathbf\{K\}\_t$ is given by $k(\backslash mathbf\{x\}\_i,\backslash mathbf\{x\}\_t)$.

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

: $$

f(\mathbf{x}) = arg\min_j D(\mathbf{y}(\mathbf{x}),\bar{\mathbf{y}}_j),

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

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

• Face recognition{{cite journal|last=Liu|first=Q.|author2=Lu, H. |author3=Ma, S. |title=Improving kernel Fisher discriminant analysis for face recognition|journal=IEEE Transactions on Circuits and Systems for Video Technology|year=2004|volume=14|issue=1|pages=42–49|doi=10.1109/tcsvt.2003.818352|s2cid=39657721 }}{{cite journal|last=Liu|first=Q.|author2=Huang, R. |author3=Lu, H. |author4=Ma, S. |title=Face recognition using kernel-based Fisher discriminant analysis|journal=IEEE International Conference on Automatic Face and Gesture Recognition|year=2002}} and detection{{cite book|last=Kurita|first=T.|author2=Taguchi, T. |title=Proceedings of Fifth IEEE International Conference on Automatic Face Gesture Recognition |chapter=A modification of kernel-based Fisher discriminant analysis for face detection |pages=300–305|year=2002|doi=10.1109/AFGR.2002.1004170|citeseerx=10.1.1.100.3568|isbn=978-0-7695-1602-8|s2cid=7581426 }}{{cite journal|last=Feng|first=Y.|author2=Shi, P. |title=Face detection based on kernel fisher discriminant analysis|journal=IEEE International Conference on Automatic Face and Gesture Recognition|year=2004}}
• Hand-written digit recognition{{cite journal|last=Yang|first=J.|author2=Frangi, AF |author3=Yang, JY |author4= Zang, D., Jin, Z. |title=KPCA plus LDA: a complete kernel Fisher discriminant framework for feature extraction and recognition|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|year=2005|volume=27|issue=2|pages=230–244|doi=10.1109/tpami.2005.33 |pmid=15688560|citeseerx=10.1.1.330.1179|s2cid=9771368 }}
• Palmprint recognition{{cite journal|last=Wang|first=Y.|author2=Ruan, Q. |title=Kernel fisher discriminant analysis for palmprint recognition|journal=International Conference on Pattern Recognition|year=2006}}
• Classification of malignant and benign cluster microcalcifications{{cite journal|last=Wei|first=L.|author2=Yang, Y. |author3=Nishikawa, R.M. |author4= Jiang, Y. |title=A study on several machine-learning methods for classification of malignant and benign clustered microcalcifications|journal=IEEE Transactions on Medical Imaging|year=2005|volume=24|issue=3|pages=371–380|doi=10.1109/tmi.2004.842457|pmid=15754987 |s2cid=36691320 }}
• Seed classification
• Search for the Higgs Boson at CERN{{cite journal|last=Malmgren|first=T.|title=An iterative nonlinear discriminant analysis program: IDA 1.0|journal=Computer Physics Communications|year=1997|volume=106|issue=3|pages=230–236|doi=10.1016/S0010-4655(97)00100-8|bibcode=1997CoPhC.106..230M }}

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

{{Reflist}}

• [http://crsouza.blogspot.com/2010/01/kernel-discriminant-analysis-in-c.html Kernel Discriminant Analysis in C#] - C# code to perform KFD.
• [http://homepage.tudelft.nl/19j49/Matlab_Toolbox_for_Dimensionality_Reduction.html Matlab Toolbox for Dimensionality Reduction]{{Dead link|date=May 2025 |bot=InternetArchiveBot |fix-attempted=yes }} - Includes a method for performing KFD.
• [http://www.codeproject.com/KB/recipes/handwriting-kda.aspx Handwriting Recognition using Kernel Discriminant Analysis] - C# code that demonstrates handwritten digit recognition using KFD.

Category:Statistical classification