526互联

Graph Construction and b-Matching for Semi-Supervised Learning

发布时间 2023-09-11 14:58:00作者: 馒头and花卷

目录

Jebara T., Wang J. and Chang S. Graph construction and b-matching for semi-supervised learning. ICML, 2009.

概

本文综合性地论述和比较了不同地的图 (邻接矩阵) 的构造方法, 设计稀疏化 (sparsification), reweighting. 最后, 在此基础上讨论了 label 的半监督学习问题.

符号说明

  • \(\{(\mathbf{x}_1, y_1), \ldots, (\mathbf{x}_l, y_l)\}\), 带标签数据;
  • \(\{\mathbf{x}_{l+1}, \ldots, \mathbf{x}_{l+u}\}\), 不带标签数据.
  • \(\mathcal{X}_l := \{ \mathbf{x}_1, \ldots, \mathbf{x}_l\}\);
  • \(\mathcal{X}_u := \{ \mathbf{x}_{l+1}, \ldots, \mathbf{x}_{l+u}\}\);
  • \(\mathcal{X} = \mathcal{X}_l \cup \mathcal{X}_u\);
  • \(\mathcal{G} = (V, E)\), 图;
  • \(W \in \mathbb{R}^{n \times n}\), 带权的对称邻接矩阵 (对角线元素为 \(0\));

图的构建

  • 一般图的构建分成如下几步:

    1. 首先计算结点间的相似度:

      \[A_{ij} = k(\mathbf{x}_i, \mathbf{x}_j), \]

      其中 \(k(\cdot, \cdot)\) 为一核函数, 这些构建成了相似度矩阵 \(A \in \mathbb{R}^{n \times n}\).

    2. 此时, 整个邻接矩阵是稠密的, 此时我们通常会将其稀疏化来得到更加鲁棒的结果.

Graph Sparsification

  • 图的稀疏化, 或者说邻接矩阵 \(A\) 的稀疏化, 就是找一个二元的稀疏矩阵

    \[P \in \mathbb{R}^{n \times n}, \]

    \(P_{ij} = 1\) 表示边 \((v_i, v_j)\) 被保留, 否则被移除.

  • 在实际中, 距离矩阵 (distance matrix) 会比 \(A\) 更为常用一些:

    \[D_{ij} = \sqrt{A_{ii} + A_{jj} - 2A_{ij}} = \sqrt{k(\mathbf{x}_i,\mathbf{x}_i) + k(\mathbf{x}_j, \mathbf{x}_j) - 2k(\mathbf{x}_i, \mathbf{x}_j)}. \]

\(\epsilon\)-neighborhood graph

  • 这种方式非常直接, 就是令

    \[P_{ij} = 1 \text{ if } D_{ij} < \epsilon. \]

\(k\)NN graph

  • 这种方式的直接意义就是希望每个结点都有 \(k\) 个一阶邻居, 它实际上实在优化如下的问题:

    \[\begin{array}{rl} \min_{P \in \mathbb{B}} & \sum_{ij} P_{ij} D_{ij} \\ \text{s.t.} & \sum_{j} P_{ij} = k, P_{ii} = 0, \forall i, j \in [n]. \end{array} \]

    这里 \([n] := \{1, 2, \ldots, n\}\).

  • 实际上, 我们一般用贪心算法, 为每个结点找到它的最合适 (也就是距离最小的) \(k\) 个邻居, 由此得到 \(\hat{P}\).

  • 但是, 很明显, 这种情况得到的 \(\hat{P}\) 是不一定对称的, 所以实际上我们通常令

    \[P = \max(\hat{P}, \hat{P}^T), \]

    以保证 \(P\) 的对称性.

  • 不过, 这种做法会导致有些结点的一阶邻居个数大于 \(k\) 个.

\(b\)-Matching

  • 这种方式旨在求解如下的问题:

    \[\begin{array}{rl} \min_{P \in \mathbb{B}} & \sum_{ij} P_{ij} D_{ij} \\ \text{s.t.} & \sum_{j} P_{ij} = k, P_{ii} = 0, P_{ij} = P_{ji}, \forall i, j \in [n]. \end{array} \]

  • 精确求解该问题是不易的, 通常使用 loopy belief propagation 来求解.

Graph Edge Re-Weighting

  • 有了 \(P\) 之后, 一种直接的做法就是令

    \[W = P \odot A, \]

    不过这么简单粗暴地丢掉别的信息似乎也不怎么好.

  • Gaussian kernel:

    \[W_{ij} = P_{ij} \exp(- \frac{d(\mathbf{x}_i, \mathbf{x}_j)}{2 \sigma^2}), \]

    利用高斯核重新估计. 这里的距离函数有很多种, 比如:

    \[d_1(\mathbf{x}_i, \mathbf{x}_j) = |\mathbf{x}_i - \mathbf{x}_j| \\ d_2(\mathbf{x}_i, \mathbf{x}_j) = \|\mathbf{x}_i - \mathbf{x}_j\| \\ d_3(\mathbf{x}_i, \mathbf{x}_j) = \sum_{k} \frac{(x_{ik} - x_{jk})^2}{x_{ik} + x_{jk}}. \]

  • 另外一种方式是通过优化的方式:

    \[\min_{W} \sum_i \epsilon_i = \sum_i\|\mathbf{x}_i - \sum_{j=1}^n P_{ij} W_{ij} \mathbf{x}_j\|^2, \\ \text{s.t.} \sum_{j} W_{ij} = 1, W_{ij} \ge 0. \]

    即, 我们希望 \(W\) 能够使得重构误差是最小的.

注: 关于剩下的半监督学习的部分, 之后独立地整理.