半监督学习是指在模型训练阶段同时利用有标签数据和无标签数据。我之前介绍过的半监督学习方法包括

基于分歧的半监督学习方法
机器学习教程之半监督学习 Tri-training方法 (论文、数据集、代码)
机器学习教程之半监督学习 Co-training 协同训练 (论文、算法、数据集、代码)
机器学习教程之半监督学习 Coreg 协同回归算法 (论文、算法、数据集、代码)
基于图的半监督学习方法
DeepLearning | 图注意力网络Graph Attention Network（GAT）论文、模型、代码解析
 DeepLearning | 图卷积神经网络(GCN)解析(论文、算法、代码)
DeepLearning | 图卷积网络基于拓扑结构的分类（T-GCN)
机器学习教程之半监督学习基于图正则项的半监督极限学习机

今天介绍的半监督极限学习机也是一种基于图的半监督学习方法，论文：
Semi-supervised and unsupervised extreme learning machines
不同于以上三种，这里的图指的是图正则项而不是图卷积。在实际运用中，作者发现很多该模型的很好的性质，比如可以运用于我们熟悉的归纳式学习，求解十分迅速并且是最优解析解等，也可以很容易的从分类任务拓展到回归任务。因此，在这里作一个详细的介绍。

对于模型的复现，作者参考了众多论文，给该模型做了一个非常强大的实现，下载连接放在文末的公众号里。同时，值得一提的是，极限学习与之前介绍的宽度学习是非常相似的，之前写过相关博客，可以参考

DeepLearning | Broad Learning System 宽度学习系统 : 高效增量式浅层神经网络

一、极限学习机

对于有监督的学习任务，一个包含 $N$ 个样本的训练集表示为 $\{\bm{X},\bm{Y}\} = \{\bm{x}_{i},\bm{y}_{i}\}^{N}_{i=1}$ 。这里， $\bm{x}_{i}$ 是一个一维向量表示样本， $\bm{y}_{i}$ 是一个一维的01向量，其中表示 $\bm{x}_{i}$ 类别的那个维度为1，其余的为0，即独热编码后的标签。极限学习机（ELM）想要基于该训练机学习一个从 $\bm{x}$ 到 $\bm{y}$ 的映射函数

通常ELM的训练分为两个阶段。

第一个阶段是通过随机映射来产生指定数量的特征，映射可以是任意的非线性连续函数，比如Sigmoid和Gaussian函数
1）Sigmoid函数
$g(\bm{x},\theta)= \frac{1}{1+exp(-(\bm{a}\bm{x}+b))}$
2）Gaussian 函数
$g(\bm{x},\theta)= exp(-b||\bm{x}-\bm{a}||)$
这里 $\theta=\{\bm{a},b\}$ 是随机产生的映射参数， $||·||$ 表示二范数。

随机产生各式的特征使得ELM和普通前向网络不同，只需要训练特征和输出之前的映射，大大减少了训练的时间和步骤。这里记 $\bm{x}_{i}$ 随机产生的特征为 $\bm{h}(\bm{x}_{i})$ ，特征维度是任意的指定值。

ELM的第二个阶段是线性求解特征和输出直接的映射，目标函数记为
$min \frac{C}{2}\sum^{N}_{i=1}||\bm{y}_{i}-\bm{h}(\bm{x}_{i})\beta|| + \frac{1}{2}||\beta||$
这里的 $\beta$ 是我们需要求解的模型参数，损失的第一项表示模型的预测损失， $C$ 是预测损失的罚系数，第二项表示的是对模型参数的二范数正则。
该损失函数的矩阵形式为
$min L_{ELM} =\frac{C}{2}||\bm{Y}-\bm{H}\beta|| + \frac{1}{2}||\beta||$
其中 $\bm{H}=[\bm{h}(\bm{x}_{1}),...,\bm{h}(\bm{x}_{N})]$ 是所有样本的特征。

ELM的解
当 $\bm{H}$ 的行大于列时，模型是过定义的，解为：
$\beta^{*} = (\bm{H}^{T}\bm{H}+\frac{I}{C})^{-1}\bm{H}^{T}\bm{Y}$

这里 $\bm{I}$ 是单位阵。
但当 $\bm{H}$ 的列大于行时，模型是欠定义的，解为：
$\beta^{*} = \bm{H}^{T}(\bm{H}\bm{H}^{T}+\frac{\bm{I}}{C})^{-1}\bm{Y}$

以上就是对ELM的介绍和求解，ELM的性能影响比较大的是随机特征的产生，这里操作空间比较大，不同方式产生的特征和特征的数量都会很大程度上影响模型性能。

二、图正则项

半监督学习的建立往往基于两个假设
1）有标签数据 $\bm{X}_{l}$ 和无标签数据 $\bm{X_{u}}$ 服从同一分布 $P$
2）如果两个样本点 $\bm{x}_{1}$ 和 $\bm{x}_{2}$ 是相似的，那么它们的条件概率 $P(\bm{y}_{1}|\bm{x}_{1})$ 和 $P(\bm{y}_{2}|\bm{x}_{2})$ 也应该是相似的。

该思想被图正则项定义为损失函数如下
$L_{m}=\frac{1}{2}\sum_{i,j}w_{ij}||P(\bm{y}|\bm{x}_{i})-P(\bm{y}|\bm{x}_{j})||$

这里 $w_{ij}$ 是 $\bm{x}_{i}$ 和 $\bm{x}_{j}$ 的相似度。

值得一提的是相似度矩阵 $\bm{W}=[w_{ij}]$ 往往是稀疏的。因为我们仅仅当 $\bm{x}_{i}$ 和 $\bm{x}_{j}$ 很接近的时候，才将 $w_{ij}$ 设置为一个非零值，比如， $\bm{x}_{i}$ 需要是 $\bm{x}_{j}$ 的 $k$ 近邻。 $w_{ij}$ 的值通常根据高斯指数函数计算 $exp(-||\bm{x}_{i}-\bm{x}_{j}||/2\sigma)$ ，或者直接简单设置为1.

直观的，当 $\bm{x}$ 的变化很小时，正则项 $L_{m}$ 惩罚了条件概率 $P(\bm{y}|\bm{x})$ 大的变化。由于真实的条件概率难以计算，该正则项可以被估计为
$\hat{L}_{m}=\frac{1}{2}\sum_{i,j}w_{ij}||\hat{\bm{y}}_{i}-\hat{\bm{y}}_{j}||$

其中, $\hat{\bm{y}}$ 是对 $\bm{x}$ 的预测值。

上式的矩阵形式可以写为
$\hat{L}_{m}=Tr(\hat{\bm{Y}}^{T}\bm{L}\hat{\bm{Y}})$

其中 $Tr(·)$ 表示矩阵的迹， $\bm{L}=\bm{D}-\bm{W}$ 被称为拉普拉斯图矩阵， $\bm{D}$ 是对角矩阵，对角元素为 $D_{ii}=\sum^{l+u}_{j=1}w_{ij}$ 。通常， $\bm{L}$ 会被规范化为 $\bm{L}=D^{-1/2}\bm{L}D^{-1/2}$ 。

以上就是对图正则项的介绍，我们可以看到，定义的 $\hat{L}_{m}$ 是同时适用于有标签或者无标签数据的，因此，它可以很方便的被应用半监督学习。

三、半监督极限学习机

这里我们记有标签数据集为 $\{\bm{X}_{l},\bm{Y}_{l}\} = \{\bm{x}_{i},\bm{y}_{i}\}^{l}_{i=1}$ ，无标签数据集记为 $\{\bm{X}_{u},\bm{Y}_{u}\} = \{\bm{x}_{i},\bm{y}_{i}\}^{u}_{i=1}$ ，其中 $l$ 和 $u$ 是样本数量。

半监督极限学习机(SSELM)的目标函数为：
$min L_{ELM} =\frac{1}{2}||\bm{C}^{\frac{1}{2}}(\bm{Y}-\bm{H}\beta)|| + \frac{1}{2}||\beta|| + \frac{\lambda}{2}Tr(\beta^{T}\bm{H}^{T}\bm{L}\bm{H}\beta)$

上式中 $\tilde{\bm{Y}} \in \mathbb{R}^{(l+u)\times n_{0}}$ ，它的前 $l$ 行等于 $Y_{l}$ , 后 $u$ 行等于0。 $\bm{C}$ 是一个 $(l+u)\times(l+u)$ 的对角矩阵，它的前 $l$ 个对角元素为 $C_{0}/N_{ti}$ , 后 $u$ 个对角元素为0. $C_{0}$ 是任意给定值， $N_{ti}$ 是第 $i$ 个类别中样本的数量，这意味着SSELM是损失敏感的。