Spectral Approach To Model Selection And Combination For Kernel Methods

Kernel methods are important machine learning methods. Model selection and combination are crucial to kernel methods. Current model selection criterions for ker-nel methods are derived from complexity perspective, which are difficult to represent and compute. Existing model combination methods for kernel methods usually per-form the combination on all the available kernels. This combination strategy exhibits trivial generalization capability. Most optimization algorithms for kernel model com-bination formulate the problem as semi definite programs, which are very computa-tionally expensive.In this thesis, a spectral approach to model selection and combination for kernel methods is derived. First, the spectra based selection criterions for kernel matrix are provided. Then, the COSK methods for the convex combination of kernel matrix is proposed. Finally, the second order cone programs for large margin model with kernel matrix combination are designed. Following are the main results.1. For kernel model selection criterion, the first-order and second-order criterions to select kernel matrix are derived. The first-order criterions are based on significant eigenvalue and position-2 eigenvalue. The dependence of generalization bound on significant eigenvalue and position-2 eigenvalue are proven. The second-order cri-terion is based on quality functional and almost minimizer set. The generalization capability of convex combination of kernel matrices in the almost minimizer set is proven. This work provide a spectral approach to represent and compute kernel model complexity. Theoretical analysis of the dependence of AIC and MDL crite-rion on the spectra, and experimental validation of the consistency of AIC and MDL with spectral criterion are provided.2. For kernel model combination method, the COSK method for for the convex com-bination of kernel matrix is proposed. Based on the first-order criterion and the second-order criterion, the COSK method carries out the combination on the almost minimizer set of kernel matrices. COSK method is proven to have the optimal gen-eralization bound of O(1/n), which goes significantly beyond the O(1/1/2n) bound by existing methods. Experiments on bench mark data set are designed for verifying the generalization of COSK.3. For optimization algorithm of kernel model combination, the second order cone programs for large margin model are designed. The second order cone programs is based on the reformulation of large margin model with convex constrained, politic constrained and elliptic constrained kernel matrix combination. The algorithm com-plexity of the second-order cone programs are O(Nn3.5), which is more efficient than the O(Nl1.5n4.5) complexity of semi definite programs. Experiments on artifi-cial data and bench mark data set are designed for verifying the efficiency of the proposed second order programs.