大规模数据的标签传播

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$

标签传播算法（Label Propagation）及 Python 实现

张贤达著.矩阵分析与应用[M].北京：清华大学出版社.2004. ↩
维基百科.张量.[DB/OL].https://zh.wikipedia.org/zh-hans/張量. ↩
Wikipedia.One-hot.[DB/OL].https://en.wikipedia.org/wiki/One-hot. ↩
朱文涛，袁勇.Python计算机视觉编程[M].北京：人民邮电出版社，2014.7:152-154. ↩
Chung, F. (1997). Spectral graph theory (Vol. 92 of the CBMS Regional Conference Series in Mathematics). Conference Board of the Mathematical Sciences, Washington ↩

分析角度的标签传播

分析角度的标签传播

大规模数据的标签传播

1.2.1 预备知识

1.2.2 半监督学习

$l \ll u$ 的情境

相关阅读更多精彩内容

友情链接更多精彩内容