大规模数据的标签传播

---

1.2.1 预备知识

【定义 1】设 X 是数域 K（实数域或复数域）上的线性空间. 对 \forall x,y,z \in X;\;\alpha,\beta \in K. 如果存在映射 (\cdot,\cdot): X \times X \rightarrow K 满足以下三个条件：

• (第一变元线性}) (\alpha x + \beta y,z) = \alpha (x,z) + \beta (y,z)
• (共轭对称性) (x,y) = \overline{(y,x)}
• (正定性) \forall x \in X,\,(x,x) \geq 0,\,\text{且 }(x,x)=0 \Leftrightarrow x = {\mathbf 0}

则称 (\cdot,\cdot) 是 X 上的一个内积, 并称 (x,y) 为向量 x,y 的内积. 配置了内积的线性空间 X 称为内积空间. 称 ||x|| = \sqrt{(x,x)} 为 (\cdot,\cdot) 诱导的范数. 如果 (X, ||\cdot||) 是 Banach 空间, 那么称 X 为 Hilbert 空间.

【命题 1】(Cauchy-Schwart 不等式) 若 X 为内积空间, 则有
|(x,y)| \leq \sqrt{(x,x)}\cdot \sqrt{(y,y)} \;\; \forall x,y \in X

【命题 2】（极化恒等式）若 X 是内积空间, 则由内积诱导出的范数与内积满足下述等式:
(x,y) = \frac{||x+y||^2-||x-y||^2+i||x+iy||^2-i||x-iy||^2}{4}

【定理 1】（内积导出范数的特征）赋范线性空间 (X,||\cdot||) 中的范数 ||\cdot|| 是由某一内积诱导出来的（即可内积化）的充要条件是下述的平行四边形法则公式成立:
||x+y||^2 + ||x-y||^2 = 2(||x||^2+||y||^2),\;\;\forall x,y \in X.

【定义 2】设 V^m 是数域 K（实数域或复数域）上的 m 维内积空间, 它的一组基为 \xi_1,\xi_2,\cdots,\xi_m, 对于任意的 x,y \in V^m, x_i \in K, i \in \{1, 2, \cdots, m\}
\begin{cases} \mathcal{A} = \begin{pmatrix} \xi_1\\ \xi_2 \\ \vdots\\ \xi_m \end{pmatrix}\\ x = \displaystyle\sum_{i=1}^m x_i \xi_i = (x_1,x_2,\cdots,x_m)\mathcal{A} = X\mathcal{A}\\ y = \displaystyle\sum_{i=1}^m y_i \xi_i = (\xi_1,\xi_2,\cdots,\xi_m)(y_1,y_2,\cdots,y_m)^T = Y \mathcal{A} \end{cases}
则 X, Y 分别称为 x, y 在基 \mathcal{A} 下的坐标. 记 W = ((\xi_i,\xi_j))_{m\times n} 称之为 V^m 在基 \mathcal{A} 下的度量矩阵. 故而, 有内积
\begin{aligned} (x,y) &= (\displaystyle\sum_{i=1}^m x_i \xi_i, \displaystyle\sum_{i=1}^m y_i \xi_i) \\ &= \displaystyle\sum_{i=1}^m \displaystyle\sum_{j=1}^m x_i \overline{y_j} (\xi_i,\xi_j) \\ &=X W Y^H \end{aligned}

【定义 3】(矩阵的内积^[1]) 矩阵的内积记作 \langle \cdot,\cdot \rangle : \mathbb{C^{m\times n} \times C^{m\times n} \rightarrow C}, 令
\begin{cases} A = \begin{bmatrix} a_1\\\vdots \\ a_m \end{bmatrix},\, B =\begin{bmatrix} b_1\\\vdots \\ b_m \end{bmatrix} \in \mathbb{C^{m\times n}}\\ a = vec(A) = \begin{bmatrix} a_1 \cdots a_m \end{bmatrix}\\ b = vec(B) = \begin{bmatrix} b_1\cdots b_m \end{bmatrix} \end{cases}

定义 \langle A, B\rangle 为两个『拉长向量』a 和 b 之间的内积
\langle A, B\rangle = \langle vec(A), vec(B)\rangle = \displaystyle\sum_{i=1}^m a_ib_i^H=\sum_{i=1}^m \langle a_i,b_i\rangle = Tr(AB^H) = Tr(BA^H)

对于任意的 A, B, C \in \mathbb{C}^{m \times n} 和 k_1, k_2 \in \mathbb{C} 容易验证:

• \langle k_1 A + k_2 B, C\rangle = k_1 \langle A, C\rangle + k_2 \langle B, C\rangle
• \langle A, B\rangle = \overline{\langle B, A \rangle}
• \langle A, A\rangle \geq 0;\;\langle A,A\rangle=0 \Leftrightarrow A = \mathbf{0_{m\times n}}

因此, (\mathbb{C}^{m\times n},\langle \cdotp,\cdotp \rangle) 是 \mathbb{C} 上的内积空间.

1.2.2 半监督学习

有一个数据集 {\mathcal{D}} = \{(x_i,y_i)\}_{i=1}^m，其中 x_i 代表数据集 {\mathcal{D}} 的特征, 是一个张量；y_i 代表数据集 {\mathcal{D}} 的标签张量^[2].

由于本文仅仅考虑图片数据, 所以我们有:

• x_i 可以是一个包含图片像素值的一维张量, 亦可以是彩色图片的像素值组成的三维张量.
• y_i 可以是一个 x_i 对应的标签的字符串或者是字符串所代表的数值型特征, 亦或者是其字符串的 One-hot^[3] 形式等.

这里令下标 l 和 u 分别代表有标签数据和无标签数据 (同时 l 和 u 也分别代表有标签数据和无标签数据的样本数, 且 l + u = m). 不失一般性, 本文记

\begin{cases} X_l = [x_1, x_2, \cdots,x_l]\\ X_u = [x_{l+1}, x_{l+2}, \cdots,x_{l+u}]\\ Y_l = [y_1, y_2, \cdots,y_l]\\ \end{cases}

数域 \mathbb{R} 上的线性子空间 V = L(x_1, \,x_2,\,\cdots,\,x_m) 上定义一个映射 f
\begin{aligned} &f:&V \rightarrow{} \mathbb{R}^{C} && |\,\text{$C$ 表示类别的个数}\\ &&x_i \mapsto f_i && |\,i \in \{1, 2, \cdots, m\} \end{aligned}
记
\begin{cases} F_l = [f_1,f_2,\cdots,f_l] \in \mathbb{R}^{C \times l}\\ F_u = [f_{l+1},f_{l+2},\cdots,f_{l+u}] \in \mathbb{R}^{C \times u}\\ F = [f_1,\cdots,f_l,\cdots,f_{l+u}] \in \mathbb{R}^{C \times m} \end{cases}

下面先基于 \{x_i,y_i\}_{i=1}^l \;\cup\; \{x_j\}_{j=l+1}^{l+u} 构建一个图 {\mathcal{G}} = (V, E), 其中节点集 V = A_l \cup A_u \cup B_l, 边集 E 可表示为一个亲和矩阵 (affinity matrix, 矩阵中每个元素表示两两之间的相似性分数^[4]) W, 令 d_j = \displaystyle\sum_{j=1}^m (W)_{ij} 故而, 对角矩阵 D = diag(d_1, d_2, \cdots, d_m) 由 \Delta = D- W (\Delta 被称为拉普拉斯矩阵^[5]) 则可以定义 f 的能量函数为
\begin{aligned} E(f) &= \frac{1}{2} {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m (W)_{ij} ||f_i - f_j||^2}\\ &= \frac{1}{2}{\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m (W)_{ij}( ||f_i||^2 - 2 f_i^Tf_j + ||f_j||^2)}\\ &= {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m}(W)_{ij}||f_i||^2 - {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m}f_i^Tf_j(W)_{ij} & \text{$i$, $j$ 的对称性}\\ &= {\displaystyle\sum_{i=1}^{m}||f_i||^2d_i} - {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m}Tr(f_jf_i^T)(W)_{ij}\\ &= {Tr(F(D- W)F^T) }\\ &= \langle F\Delta,\, F \rangle \end{aligned}

上面的 F 和 W 的不同将可以设计出不同的模型. 由上面的分析可以知道:
W = W^T; F = [F_l, F_u]

l \ll u 的情境

令 \mu = [\mu_1; \mu_2;\cdots;\mu_l] \in \mathbb{R}^{l\times 1}，U = diag(\mu)
当 f_l, Y_l 可以不相等时, 记 L = E(f) + \displaystyle\sum_{i=1}^l \mu_i ||f_i-y_i||_2^2 = \langle F (\Delta+U), F \rangle

---

1. 张贤达著.矩阵分析与应用[M].北京：清华大学出版社.2004. ↩

2. 维基百科.张量.[DB/OL].https://zh.wikipedia.org/zh-hans/張量. ↩

3. Wikipedia.One-hot.[DB/OL].https://en.wikipedia.org/wiki/One-hot. ↩

4. 朱文涛，袁勇.Python计算机视觉编程[M].北京：人民邮电出版社，2014.7:152-154. ↩

5. Chung, F. (1997). Spectral graph theory (Vol. 92 of the CBMS Regional Conference Series in Mathematics). Conference Board of the Mathematical Sciences, Washington ↩