Kernel (Fisher) discriminant analysis (kernel FDA) is a nonlinear generalization of linear discriminant analysis (LDA) using techniques of kernel methods. Using a kernel, the originally linear operations of LDA are done in a reproducing kernel Hilbert space with a nonlinear mapping.
 Download source code
 Download sample application
This code has also been incorporated in Accord.NET Framework, which includes the latest version of this code plus many other statistics and machine learning tools.
Analysis Overview
KDA is an extension of LDA to nonlinear distributions, just as KPCA is to PCA. For information about LDA, please check the previous post, Linear Discriminant Analysis in C#. The algorithm presented here is a multiclass generalization of the original algorithm by Mika et al. in Fisher discriminant analysis with kernels (1999).
The objective of KDA is to find a transformation maximizing the betweenclass variance and minimizing the withinclass variance. It can be shown that, with Kernels, the original objective function can be expressed as:
with:
where K_{c} is the Kernel matrix for class c, u_{c} is the column means vector for K_{c}, I is the identity matrix, l_{c} is the number of samples in class c and 1_{lc} is a l_{c} x l_{c} matrix with all entries 1/l_{c}.
The Kernel Trick
The Kernel trick transforms any algorithm that solely depends on the dot product between two vectors. Wherever a dot product is used, it is replaced with the kernel function.
K(x,y) = <φ(x),φ(y)>
Thus, a linear algorithm can easily be transformed into a nonlinear algorithm. So the algorithm can be carried in a higherdimension space without explicitly mapping the input points into this space. For more information and a cool video showing how the kernel trick works, please see the introductory text in the previous post, Kernel Principal Component Analysis in C#.
Adding regularization
As the problem proposed above is illposed (we are estimating l dimensional covariance structures from l samples), the Sw matrix may become singular, and computing the objective function may become problematic. To avoid singularities, we can add a multiple of the identity matrix to the Sw matrix:
The λ adds numerical stabilities as for large λ the matrix Sw will become positive definite. The λ term can also be seen as a regularization term, favoring solutions with small expansion coefficients [Mika et al, 1999].
Source Code
The code below implements a generalization of the original Kernel Discriminant Analysis algorithm by Mika et al. in Fisher discriminant analysis with kernels (1999).
1 
<span>/// <summary></span><br /><span>/// Computes the MultiClass Kernel Discriminant Analysis algorithm.</span><br /><span>/// </summary></span><br /><span>public</span> <span>override</span> <span>void</span> Compute()<br />{<br /> <span>// Get some initial information</span><br /> <span>int</span> dimension = Source.GetLength(0);<br /> <span>double</span>[,] source = Source;<br /> <span>double</span> total = dimension;<br /><br /><br /> <span>// Create the Gram (Kernel) Matrix</span><br /> <span>double</span>[,] K = <span>new</span> <span>double</span>[dimension, dimension];<br /> <span>for</span> (<span>int</span> i = 0; i < dimension; i++)<br /> {<br /> <span>for</span> (<span>int</span> j = i; j < dimension; j++)<br /> {<br /> <span>double</span> s = kernel.Kernel(source.GetRow(i), source.GetRow(j));<br /> K[i, j] = s;<br /> K[j, i] = s;<br /> }<br /> }<br /><br /><br /> <span>// Compute entire data set measures</span><br /> Means = Tools.Mean(K);<br /> StandardDeviations = Tools.StandardDeviation(K, Means);<br /><br /><br /> <span>// Initialize the kernel analogue scatter matrices</span><br /> <span>double</span>[,] Sb = <span>new</span> <span>double</span>[dimension, dimension];<br /> <span>double</span>[,] Sw = <span>new</span> <span>double</span>[dimension, dimension];<br /><br /><br /> <span>// For each class</span><br /> <span>for</span> (<span>int</span> c = 0; c < Classes.Count; c++)<br /> {<br /> <span>// Get the class subset</span><br /> <span>double</span>[,] subset = Classes[c].Subset;<br /> <span>int</span> count = subset.GetLength(0);<br /><br /> <span>// Create Kernel matrix for the class and get its mean</span><br /> <span>double</span>[,] Kc = <span>new</span> <span>double</span>[dimension, count];<br /> <span>double</span>[] mean = <span>new</span> <span>double</span>[dimension];<br /> <span>for</span> (<span>int</span> i = 0; i < dimension; i++)<br /> {<br /> <span>double</span> sum = 0.0;<br /> <span>for</span> (<span>int</span> j = 0; j < count; j++)<br /> {<br /> <span>double</span> s = kernel.Kernel(source.GetRow(i), subset.GetRow(j));<br /> Kc[i, j] = s;<br /> sum += s;<br /> }<br /> mean[i] = sum / count;<br /> }<br /><br /> <span>// Construct the Kernel equivalent of the WithinClass Scatter matrix</span><br /> <span>double</span>[,] Swi = Kc.Multiply(Matrix.Centering(count)).Multiply(Kc.Transpose());<br /> Sw = Sw.Add(Swi);<br /> <br /> <span>// Construct the Kernel equivalent of the BetweenClass Scatter matrix</span><br /> <span>double</span>[] d = mean.Subtract(Means);<br /> <span>double</span>[,] Sbi = d.Multiply(d.Transpose()).Multiply(total/count);<br /> Sb = Sb.Add(Sbi);<br /><br /><br /> <span>// Store additional information</span><br /> ClassScatter[c] = Swi;<br /> ClassCount[c] = count;<br /> ClassMeans[c] = mean;<br /> ClassStandardDeviations[c] = Tools.StandardDeviation(Kc, mean);<br /> }<br /><br /><br /> <span>// Add regularization</span><br /> <span>double</span>[,] Swu = Sw.Add(Matrix.Diagonal(dimension, regularization));<br /><br /><br /> <span>// Compute eigen value decomposition</span><br /> EigenValueDecomposition evd = <span>new</span> EigenValueDecomposition(Matrix.Inverse(Swu).Multiply(Sb));<br /><br /> <span>// Gets the eigenvalues and corresponding eigenvectors</span><br /> <span>double</span>[] evals = evd.RealEigenValues;<br /> <span>double</span>[,] eigs = evd.EigenVectors;<br /><br /><br /> <span>// Sort eigen values and vectors in ascending order</span><br /> eigs = Matrix.Sort(evals, eigs, <span>new</span> GeneralComparer(ComparerDirection.Descending, <span>true</span>));<br /><br /><br /> <span>// Calculate translation bias</span><br /> <span>this</span>.DiscriminantBias = eigs.Transpose().Multiply(Means).Multiply(1.0);<br /><br /><br /> <span>// Store information</span><br /> <span>base</span>.EigenValues = evals;<br /> <span>base</span>.DiscriminantMatrix = eigs;<br /> <span>base</span>.ScatterBetweenClass = Sb;<br /> <span>base</span>.ScatterWithinClass = Sw;<br /><br /><br /> <span>// Computes additional information about the analysis and creates the</span><br /> <span>// objectoriented structure to hold the discriminants found.</span><br /> createDiscriminants();<br />} 
After completing the analysis, we may wish to project new data into discriminant space. The following code projects a data matrix into this space using the basis found during the analysis.
1 
<span>/// <summary>Projects a given matrix into discriminant space.</summary></span><br /><span>/// <param name="matrix">The matrix to be projected.</param></span><br /><span>public</span> <span>override</span> <span>double</span>[,] Transform(<span>double</span>[,] data, <span>int</span> dimension)<br />{<br /> <span>// Get some information</span><br /> <span>int</span> rows = data.GetLength(0);<br /> <span>int</span> cols = data.GetLength(1);<br /> <span>int</span> N = Source.GetLength(0);<br /><br /><br /> <span>// Create the Kernel matrix</span><br /> <span>double</span>[,] K = <span>new</span> <span>double</span>[rows, N];<br /> <span>for</span> (<span>int</span> i = 0; i < rows; i++)<br /> {<br /> <span>for</span> (<span>int</span> j = 0; j < N; j++)<br /> {<br /> K[i, j] = kernel.Kernel(Source.GetRow(j), data.GetRow(i));<br /> }<br /> }<br /><br /><br /> <span>// Project into the kernel discriminant space</span><br /> <span>double</span>[,] result = <span>new</span> <span>double</span>[rows, dimension];<br /> <span>for</span> (<span>int</span> i = 0; i < rows; i++)<br /> <span>for</span> (<span>int</span> j = 0; j < dimension; j++)<br /> <span>for</span> (<span>int</span> k = 0; k < N; k++)<br /> result[i, j] += K[i, k] * DiscriminantMatrix[k, j];<br /><br /><br /> <span>return</span> result;<br />} 
Sample Application
The sample application shows the how Kernel Discriminant Analysis works. The application can load Excel worksheets containing tables in the same format as the included sample worksheet.
The first image shows the Wikipedia example for Kernel Principal Component Analysis. The second image shows the Analysis carried out with a Gaussian kernel with sigma = 3.6. The third image shows the Kernel between class and within class equivalent matrices. The last image shows the subset spawned by each class and its Kernel scatter matrix.
The picture on the left shows the projection of the original data set in the first two discriminant dimensions. Note that just one dimension would already be sufficient to linear separate the classes. On the right, the picture shows how a point in input space (given by the mouse cursor) gets mapped into feature space.
Linear Discriminant Analysis equivalent as a special case
We can also check that a projection equivalent to Linear Discriminant Analysis can be obtained by using a Linear kernel in the Kernel Discriminant Analysis.
See also
 Kernel Functions for Machine Learning Applications
 Principal Component Analysis (PCA)
 Kernel Principal Component Analysis (KPCA)
 Linear Discriminant Analysis (LDA)
 Kernel Support Vector Machines (kSVMs)
 Logistic Regression Analysis in C#
References

Sebastian Mika, G. Rätsch, J. Weston, B. Schölkopf, K.R. Müller; Fisher discriminant analysis with kernels (1999).
Available in: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.9904 
Yongmin Li, Shaogang Gong and Heather Liddell; Kernel Discriminant Analysis.
Available in: http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/LI1/kda/index.html
This stuff is really cool. Thanks for your efforts.
As I was testing the source code and also your demo for KDA I got an error while trying to transform.
“Index was outside the bounds of the array.
at Accord.Statistics.Analysis.KernelDiscriminantAnalysis.Transform(Double[,] data, Int32 discriminants) in C:UsersCesarDesktopAccord.NETSourcesAccord.StatisticsAnalysisKernelDiscriminantAnalysis.cs:line 239″
In your demo it occurs when I use the Yin Yang example.
Also while using LDA source a similar error occurs during the try to compute.
Could you please help me? Am I doing something wrong?
Hi MSA,
Thanks for letting me know. I had updated the library code but forgot to update the samples.
To fix it, you can open the file SamplesStatisticsKDAMainForm.cs and add the line:
kda.Threshold = 0;
right below the line 124 where it reads:
kda = new KernelDiscriminantAnalysis(data, labels, kernel);
I will update the downloadable sources soon. If you wish you can also download the latest version of the Accord.NET Framework, which contains the most updated version of the code (including the sample applications).
Thanks again,
César
Hello,
I’ve updated the source code. Please redownload it from the same link as before. The newest version also uses the generalized eigenvalue decomposition instead of the standard eigenvalue decomposition, resulting in a faster and more accurate results.
Best regards,
César
Thank you very much. I appreciate your fast response.
HI,
I have to find a signature in grey scaled image file and remove it.
I am using C# for image analysis, could you please help me out.
Hello premanshu,
I think you should ask your question in the AForge.NET Forums. Perhaps you will find better answers there.
http://aforgenet.com/forum/
Best regards,
César
hello,
Great work, i really appreciate it. But i have a small doubt in the code.
when i find the discriminant projection for the input data using kda.Result. i get the projection of the input data. But when i try to find the projection of some other data (test data) which i want to compare to input data projection) using kda.transfor(output_data) i get all vales in the resulting array as 0. can u please explain how to correct this thing.
Hi Cesar,
Absolutely great work you’ve done in Accord.NET.
I’ve been trying to implement LDA & KDA. I’ve gotten LDA to run successfully, but I keep getting an “Argument out of range” error when executing the KDA.Compute() line.
Here’s my KDA training function:
private void KDA_Training(ref KernelDiscriminantAnalysis KDA, Double[,] input, int[] output, Double regularisation, Double threshold, Double GaussianSigma)
{
IKernel kernel = new Gaussian(GaussianSigma);
KDA = new KernelDiscriminantAnalysis(input, output, kernel);
KDA.Threshold = threshold;
KDA.Regularization = regularisation;
KDA.Compute();
}
Parameters:
input[,] is [120,24], positive doubles.
output[] is threeclass: {0, 1, 2}.
regularization = 0.1
GaussianSigma = 3.6
threshold = 5
I can’t seem to figure out what’s going wrong. Also, do you have the source code for your KDA sample application (specifically the KDA object calls) available?
Thank you very much.
Jack
Hi Jack,
First of all, thanks for the feedback!
About your problem, may I ask which version of the code are you using? Are you using the latest versions from the Accord.NET project site, or are you using the standalone sources available in this post? I would highly recommend to download the latest sources as they might contain the latest fixes and enhancements.
In either case, the full sources of the framework and of all sample applications are available at Google Code. In particular, the sources for the KDA sample application are here:
http://code.google.com/p/accord/source/browse/#svn%2Ftrunk%2FSamples%2FStatistics%2FKDA
From your snippet it is somewhat hard to see what is wrong. But the output[] array is expected to be an array of the same size as the number of samples (rows) in your input matrix. Each entry on the output vector should contain the class indicator (an integer label, such as 0, 1 or 2).
If this doesn’t helps, you can also send your data example to me so I can take a further look on what is causing the problem.
Best regards,
César
Hi Cesar,
Thank you for your speedy reply!
I’ve been running the version linked in this blog post, and have been using an output array, containing int class labels, whose size matches the first dimension of my input array. Apologies for being unclear earlier. Also, I’ve tried both unnormalized and normalized input arrays.
After switching to the latest v2.2 build that you linked to, I’ve encountered an error in the KSVM section of my code. It seems that MultiClassVectorLearning.Configure and ksvm.Machines[][].Indices existed in past versions of the library, but no longer exists in 2.2.
Further, after I revert to using Accord.MachineLearning v2.1.1.0 to get around this problem, Visual Studio gives me this error:
Argument 2: cannot convert from ‘Accord.Statistics.Kernels.IKernel [c:CsharpMachineLearningAccord DLLsAccord.Statistics.dll]’ to ‘Accord.Statistics.Kernels.IKernel’
I’ve tried directly referencing your precompiled Accord.Statistics DLL, as well as recompiling your Accord.Statistics library locally and referencing the newly created DLL. Both ways give me the same error.
Do you know how to fix this?
Thank you very much.
Jack
Hi Jack,
Many, many apologies for the issues. However, the Machines property of the MulticlassSupportVectorMachine still exists. Which error were you getting, exactly? You can also access individual machines by using the class indexer (i.e. ksvm[i,j]) to get each machine responsible for each classification ivsj subproblem.
The Configure method was part of the MulticlassSupportVectorLearning class, but was renamed to Algorithm. It was part of a change to support additional configuration settings for the learning algorithms and improve the semantics of the property. Sorry about that.
In either case, I would still recommend you to stay with the latest version. The errors you are getting now are because of wrong assembly references in the project. Probably you are referencing two assemblies from different versions of the library. Most probably, your MachineLearning.dll is from one version and your Statistics.dll is from the other. Please recheck all versions of the assemblies match. As a last resort, try removing all Accord.NET references and adding them again, making sure they are all from the same version. You may also need to “clear” your build to make sure Visual Studio isn’t using any cached intermediate objects.
For an example on how to setup a multiclass machine, please check this example in the documentation.
And sorry for all the trouble. Please be assured I will assist you in everything needed to get your solution working again. If you wish we can also continue this discussion by email.
Best regards,
César
HI,
Can you help me to do project in kernel…but i cant have idea how to do