Multi-class kernel margin maximization for kernel learning

Two-stage multiple kernel learning (MKL) algorithms have been intensively studied due to its high efficiency and effectiveness. Pioneering work on this regard attempts to optimize the combination coefficients by maximizing the multi-class margin of a kernel, while obtaining unsatisfying performance. In this paper, we attribute this poor performance to the way in calculating the multi-class margin of a kernel. In specific, we argue that for each sample only the k-nearest neighbors, while not all samples with the same label, should be selected for calculating the margin. After that, we also develop another sparse variant which is able to automatically identify the nearest neighbors and the corresponding weights of each sample. Extensive experimental results on ten UCI data sets and six MKL benchmark data sets demonstrate the effectiveness and efficiency of the proposed algorithms.