Optimally regularised kernel fisher discriminant analysis
Kamel Saadi, Nicola L. C. Talbot, Gavin C. Cawley · 2004
Mika et al. [3] introduce a non-linear formulation of Fisher’s linear discriminant, based the now familiar “kernel trick”, demonstrating state-of-the-art performance on a wide range of real-world benchmark datasets. In this paper, we show that the usual regularisation parameter can be adjusted so as to minimise the leave-one-out cross-validation error with a computational complexity of only O(ℓ 2) operations, where ℓ is the number of training patterns, rather than the O(ℓ 4) operations required for a na¨´eve implementation of the leave-one-out procedure. This procedure is then used to form a component of an ef£cient heirarchical model selection strategy where the regularisation parameter is optimised within the inner loop while the kernel parameters are optimised in the outer loop. where SB = (m1 −m2)(m1 −m2) T, is the between class scatter matrix, mj is the mean of patterns belonging to Cj, mj = 1 ℓj ℓj∑ i=1 x j i, and SW is the within class scatter matrix SW = i∈{1,2} j=1 ℓi (x i j − mi)(x i j − mi) T. The innovation introduced by Mika et al. [3] is to construct Fisher’s linear discriminant in a £xed feature space F (φ: X → F) induced by a positive de£nite Mercer kernel K: X × X → R de£ning the inner product K(x, x ′ ) = φ(x) · φ(x ′ ) (see e.g. Cristianini and Shawe-Taylor [2]). Let the kernel matrices for the entire dataset, K, and for each class, K1 and K2 be de£ned as follows: K = [kij = K(xi, xj)] ℓ i,j=1