Graph Laplacian for Semi-Supervised Learning

• 概
• 符号说明
• Graph-Laplacian for SSL

Streicher O. and Gilboa G. Graph laplacian for semi-supervised learning. arXiv preprint arXiv:2301.04956, 2023.

概

标题取得有一点大, 其实是一个很小的点.

符号说明

• \(X = \{x_i\}_{i=1}^n \subset \mathbb{R}^n\), a set of points;

• \(G = (V = \{1, 2, \ldots, n\}, E, W)\), 图 = (点, 边, 权重);

• 通常采用 Gaussian kernel 来估计权重

  \[W_{ij} = \exp(-\frac{\|x_i - x_j\|_2^2}{2 \sigma^2}). \]

• degree matrix \(D\),

  \[D_{ii} = \sum_{j} W_{ij}. \]

• Laplacian matrix:

  \[L = D - W. \]

Graph-Laplacian for SSL

• 我们希望估计 \(f: X \rightarrow \mathbb{R}\), 视任务而定, 可以是标签 (分类任务), 也可以是具体的值 (回归任务), 本文主要考虑分类任务的情况.

• 假设在一个子集 \(S \subset X\) 上我们知道 \(f\) 的真实值, 则我们通常优化如下问题来估计:

  \[\min_f \quad \bm{f}^T L \bm{f} \\ \text{s.t.} \quad f(x) = g(x), \quad x \in S. \]

  这里 \(\bm{f}= [f(x_1), \cdots, f(x_n)]^T\).

• 针对不同的区域, 对权重矩阵作者做了如下改进:

  \[W_{SSL} = 2W + \alpha W^{labeled}, \\ W^{labeled} = \left \{ \begin{array}{ll} \max(W) & x_i, x_j \in S_k, \forall k \in \{1, \ldots, K\} \\ -\frac{2}{\alpha} W_{ij} & x_i \in S_k, x_j \in S_l, \forall k,l \in \{1,\ldots, K|k \not= l\} \\ W_{ij} & x_i \in S, x_j \in X \setminus S \text{ or } x_i \in X \setminus S, x_j \in S \\ 0 & x_i, x_j \in X \setminus S \end{array} \right .. \]

• 主要思想是:

  1. 已知同类的样本的权重大;
  2. 已知不同的样本的权重为 0;
  3. \(x, y\), \(x\) 的类别知道, 但是 \(y\) 的类别知道, 这个的权重也要稍大一点 (来自这篇文章);
  4. 其它的正常.

• 求解这里就不讲了.