【DM论文阅读杂记】基于图聚类和半监督分类的自加权多核学习

Paper Title

Self-weighted Multiple Kernel Learning for Graph-based Clustering and Semi-supervised Classification

Basic algorithm and main steps

Basic ideas

The paper proposes a novel multiple kernel learning framework for clustering and semi-supervised learning.

Algorithm

1. Input: Kernel matrices $ {H^i}_{i=1}^r $, parameters $ α, β, γ $

2. Initialize: Random matrix $ S, K =\sum_i H^i / r $R

3. Repeat

   (1) For each i, update the i-th column of \(S\) by $ S_i = (\gamma I + K) ^{-1} (K_{i,:} - \frac{\alpha G_i}{4} ) $

   (2) Calculate \(K\) by $ K = \frac{2S^T - SS^T - I +2\beta \sum_i \omega_i H^i}{2\beta \sum_i \omega_i} $
   (3) Update \(\omega\) by (9) $ \omega_i = \frac{1}{2||H^i - K||F} $
   (4) For clustering, calculte \(P\) as the \(c\) smallest eigenvectors of \(L = D ? S\) correspond to the \(c\) smallest eigenvalues. For SSL, calculte \(P\) according to $ P_u = - L{uu}^{-1} L_{ul} Y_l $

4. Until stopping criterion is met.

Details

Assumptions

• Each kernel is a perturbation of the consensus kernel
• The kernel that is close to the consensus kernel should receive a large weight

SKML model

Self-weighted Multiple Kernel Learning

? $ s.t. P^T P = I, S \geq 0 $

$K $: rarget kernel matrix

$ S $: similarity graph matrix

$ \omega_i $: optimal weight

$ H^i $: the i-th kernel matric, input

$ \alpha, \beta,\gamma $: input parameters

$ P$: cluster indicator matrix or label matrix

Optimization

1. Fix P, K，optimize S

   Use $ \sum_{ij} 1/2 ||P_{i,:} - P_{j,:} ||2^2 s{ij} = T_r(P^TLP)$ and set the first derivative of \(S\) to be zero, obtain:

   $ S_i = (\gamma I + K) ^{-1} (K_{i,:} - \frac{\alpha G_i}{4} ) $

2. Fix S，P，optimize K

? $ K = \frac{2S^T - SS^T - I +2\beta \sum_i \omega_i H^i}{2\beta \sum_i \omega_i} $

3. Fix S，K，optimize P

? $ \min \limits_P T_r(P^TLP), s.t. P^TP = I $

Integrated SMKL model

Unify the two fundamental components of SSL(Graph construction and label inference) into a unified framework. Reformulate SMKL for semi-supervised classification as:

$ \min \limits_{S,P,K}T_r(K-2KS + S^TKS) + \gamma ||S||_F^2 + \alpha T_r(P^TLP) + \beta \sum_i \omega_i||H^i - K||_F^2 $

$ s.t. S \geq 0, P_l = Y_l $

$ Y_l = [y_1,y_2,...,y_l]^T $ : label matrix

$ y_i \in R^{c x 1} $ ：one-hot，$y_{ij} = 1 $ means the i-th sample belong to label j 。

$ P = [P_l ; P_u] = [Y_l; P_u] $ $ P_u $ : unlabeled

$ P_u = - L_{uu}^{-1} L_{ul} Y_l $

Predict： $ y_i = arg \max \limits_j P_{ij}$

Motivation

Existing parameter-weighted multiple kernel learning method suffers some problems.

• The linear combination of base kernels over reduces the feasible set of optimal kernels, which could result in the learned kernel with limited representation ability.
• The optimization of kernel weights may lead to inappropriate assignments due to noise and carelessly designed algorithms.

Contribution

• Proposed a novel way to construct the optimal kernel and assign weights to base kernels, without additional parameters and solving quadratic program.
• Integrated it into a unified framework for clustering and semi-supervised classification.

My own idea

• Qestions: How to choose a more suitable base kernel matrix H; The meaning of "allows the most suitable kernel to reside in some kernels’neighborhood "; Details of derivation of aforementioned self-expressiveness based graph learning method; Details of semi-supervised Classification; Provtion of the theory one metioned in this paper
• Shortcomings I assume: The paper only analysis the sensitity of parameters $\alpha , \beta, \gamma $ using YALE dataset, on which several methods (including the SMKL ) don‘t perform well.
• Relation. Comparing to traditional kernel learning method, the self-weighted methods proposed in the paper sufficiently considers the negotiation between the process of learning the optimal kernel and that of graph/label learning. Besides, We can directly calculate the weight from kernel matrices,thus avoiding solving quadratic program.

【DM论文阅读杂记】基于图聚类和半监督分类的自加权多核学习

原文：https://www.cnblogs.com/chensy86/p/13623621.html