最小二乘法：
$W = L(\alpha_1, \cdots, \alpha_s)$ 为 $\mathbb R$ 上的欧式空间 $V$ 的子空间， $\lambda \in W$ ，则对于任意的 $\beta \in V$ ，有：

$\forall \, \delta \in W,\; ||\beta - \lambda|| \leq ||\beta - \delta|| \Longleftrightarrow \beta \, \bot \, W$

即向量到子空间各向量间的距离以垂线为最短。

下面的 $Q$ 表示待求解的问题， $A$ 代表求解方法：

求解线性方程组

$Q_1$ ：

$\begin{aligned} &AX = b &\text{其中} A \in {\mathbb R}^{m \times n} ;\; X \in {\mathbb R}^{n \times 1} ;\; b \in {\mathbb R}^{m \times 1} \end{aligned}$

$A_1$ ：

令 $A = (\alpha_1, \cdots, \alpha_n), X = (x_1, \cdots, x_n)^{T}$ ，则有 $Y = AX = x_1 \alpha_1 + \cdots + x_n \alpha_n$ ，即 $Y \in L(\alpha_1, \cdots, \alpha_n)$ ，这样 $Q_1$ 便可转化为最小二乘问题：

$Q_1^1$ ：

$\begin{aligned} &\displaystyle\min_{Y} ||Y - b|| \Longleftrightarrow b - Y \,\bot \, L(\alpha_1, \cdots, \alpha_n)\\ &(b - Y,\, \alpha_ i) = 0 \Longleftrightarrow A^T(AX - b) = 0 & i \in \{1, \cdots, s\} \end{aligned}$

这样原问题便简化了。

几个关键定义

定义1： $V$ 是数域 $P$ 上的一个线性空间，泛函 $f: V \times V \rightarrow {\mathbb R}$ ，满足：

$\begin{cases} f(\alpha,\, k_1 \beta_1 + k_2 \beta_2) = k_1 f(\alpha, \,\beta_1) + k_2 f(\alpha,\,\beta_2)\\ f(k_1 \alpha_1 + k_2 \alpha_2,\, \beta) = k_1 f(\alpha_1, \,\beta) + k_2 f(\alpha_2,\,\beta) \end{cases}$

其中 $\alpha,\; \alpha_1,\; \alpha_2,\; \beta,\; \beta_1,\; \beta_2 \in V$ 中任意的向量， $k_1,\; k_2 \in P$ ，则称 $f(\alpha, \beta)$ 为 $V$ 上的一个双线性函数.

定义2：设 $f(\alpha, \beta)$ 是数域 $P$ 上 $n$ 维线性空间 $V$ 上的一个双线性函数. $\varepsilon_1,\, \cdots, \, \varepsilon_n$ 是 $V$ 的一组基，则矩阵

$A = \begin{bmatrix} f(\varepsilon_1,\, \varepsilon_1) & \cdots & f(\varepsilon_1,\, \varepsilon_n)\\ &&&\\ \vdots & \ddots & \vdots \\ &&&\\ f(\varepsilon_n,\, \varepsilon_1) & \cdots & f(\varepsilon_n,\, \varepsilon_n) \end{bmatrix}$

叫做 $f(\alpha, \beta)$ 在 $\varepsilon_1,\, \cdots, \, \varepsilon_n$ 下的度量矩阵。当 $\alpha = \beta$ 时， $V$ 上的函数 $f(\alpha, \alpha)$ 称为与 $f(\alpha, \beta)$ 对应的二次齐次函数。

易推知：同一个双线性函数在不同的基下的度量矩阵是合同的。

设 $\varepsilon_1,\, \cdots, \, \varepsilon_n$ 及 $\eta_1,\,\cdots,\,\eta_n$ 是线性空间 $V$ 的两组基底，且 $( \eta_1,\,\cdots,\,\eta_n) = (\varepsilon_1,\, \cdots, \, \varepsilon_n)C$ ，则有

$\begin{cases} \alpha = (\varepsilon_1,\, \cdots, \, \varepsilon_n)\\ X = ( \eta_1,\,\cdots,\,\eta_n)X_1\\ \beta = (\varepsilon_1,\, \cdots, \, \varepsilon_n)\\ Y = ( \eta_1,\,\cdots,\,\eta_n)Y_1 \end{cases}$

即：

$X = CX_1,\;Y = CY_1$

若双线性函数 $f(\alpha, \beta)$ 在 $\varepsilon_1,\, \cdots, \, \varepsilon_n$ 及 $\eta_1,\,\cdots,\,\eta_n$ 下的度量矩阵分别为 $A, B$ . 则有

$f(\alpha, \beta) = X^TAY = (CX_1)^TA(CY_1) = X_1^TC^TACY_1 = X_1^TBY_1$

因此

$B = C^TAC$

定义3：设 $D = (V, E)$ 是一个标定的无环有向图，其中设 $V = \{v_1,v_2,\cdots,v_n\},\;E = \{e_1,e_2,\cdots,e_m\}$ ，则称 $M(D) = (m_{ij})_{n \times m}$ 为 $D$ 的关联矩阵，其中

$m_{ij} = \begin{cases} 1 &\text{$v_i$ 是边 $e_j$ 的始点} \\ -1 &\text{$v_i$ 是边 $e_j$ 的终点} \\ 0 &\text{其他} \end{cases}$

基于图的半监督学习

给定 $D_l = \{(x_1,y_1), \,(x_2,y_2),\,\cdots,\,(x_l,y_l)\}$ 和 $D_u = \{(x_{l+1},y_{l+1}), \,(x_{l+2},y_{l+2}),\,\cdots,\,(x_{l+u},y_{l+u})\}$ ， $l \ll u$ ， $l+u=m$ .我们先基于 $D = D_l \bigcup D_u$ 构建一个图 $G = (V, E)$ ，其中节点集 $V = \{(x_1,y_1), (x_2,y_2),\cdots,(x_{l+u},y_{l+u})\}$ ，边集的亲和矩阵（affinity matrix，或称为相似度矩阵），常基于高斯函数定义为

$(W)_{ij} = \begin{cases} exp(\frac{-||x_i - x_j||_2^2}{2\sigma^2}) &\text{if $i \neq j$} \\ 0 &\text{其他} \end{cases}$

其中 $i,\,j \in \{1, \,2, \,\cdots, \,m\}; \sigma > 0$ 是用户指定的高斯带宽参数。

子空间 $V = L(x_1, \,x_2,\,\cdots,\,x_m))$ 上定义一个映射 $f$

$\begin{aligned} f: V \rightarrow {\mathbb R^C}, && \text{$C$ 是类别个数} \end{aligned}$

则可以定义 $f$ 的能量函数为

$\begin{aligned} E(f) &= \frac{1}{2} {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m (W)_{ij} ||f(x_i) - f(x_j)||^2}\\ &= \frac{1}{2}{\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m (W)_{ij}( ||f(x_i)||^2 - 2 f(x_i)^Tf(x_j) + ||f(x_j)||^2)}\\ &= {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m}(W)_{ij}||f(x_i)||^2 - {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m}f(x_i)^Tf(x_j)(W)_{ij} & \text{$i$, $j$ 的对称性} \end{aligned}$

令

$\begin{aligned} &W = (w_1, \, \cdots, w_m)\\ &F = (f(x_1), \cdots, f(x_m)) = (f_1, \cdots, f_m) \end{aligned}$

则有

$\begin{aligned} FWF^T &= (\sum_{i=1}^m f_i(W)_{1,i},\cdots, \sum_{i=1}^m f_j(W)_{m,i})F^T \\ &= (Fw_1, \cdots, Fw_m)F^T \\ &= \sum_{i=1}^m Fw_if_i^T \\ &= \sum_{i,j=1}^m (W)_{i,j}f_i f_j^T \end{aligned}$

故而

$\begin{aligned} Tr(FWF^T) &= \sum_{i,j=1}^m Tr(f_i f_j^T)(W)_{i,j} \\ &= {\displaystyle\sum_{i=1}^{m}\sum_{j=1}^m}f(x_i)^Tf(x_j)(W)_{ij} \end{aligned}$