原文：http://proceedings.mlr.press/v70/gupta17a/gupta17a.pdf
摘要
一些应用程序需要在小型设备上进行实时预测，如物联网（物联网）传感器。这种应用程序需要具有小存储和计算复杂度的预测模型，而这对精度没有显著影响。在这项工作中，本文提出了一种新的算法ProtoNN，以解决在资源稀缺设备上实时和准确预测的问题。ProtoNN的灵感来自k-最近邻(kNN)，但存储和预测复杂性较低。ProtoNN模型甚至可以部署在一个ArduinoUno上，以获得良好的预测精度。ProtoNN的优势来自三个关键思想：
- 学习少量原型来表示整个训练集；
- 数据的稀疏低维投影；
- 具有显式模型大小约束的投影和联合判别学习。
我们对各种监督学习任务（二分类、多分类、多标签分类）对ProtoNN进行了系统的实证评估，结果表明它在消耗低存储和使用最小工作内存的同时，在资源稀缺的设备上提供了几乎最先进的预测精度。
引言
到目前为止，物联网场景中的机器学习仅限于基于云的预测，其中部署了大型深度学习模型来提供准确的预测。以感知和传输数据到云为任务的传感器/嵌入式设备的计算/存储能力有限。这样的解决方案没有考虑隐私、带宽、延迟和电池问题。例如，如果智能工厂中每台机器上的每个物联网设备都必须连续发送数据并从云接收预测，则通信的能源成本是很大的。
一个经典的物联网设备的内存不大于32KB，有一个16MHz的处理器。大多数现有模型都无法部署在这样小的设备上。尽管大型模型的压缩方法被提出，但在物联网设备上工作的不是很好。
本文提出的基于kNN的protoNN算法可以部署在小型设备上，16KB的内存下就可以有很好的精度。选择kNN是因为它通用，易于在小设备上实现，且超参数少，避免过拟合。但是kNN也有其缺陷：
- 无法确定一个很好的距离度量作为先验，任务1下用$l^2$距离效果好，但是任务2在$l^1$距离下表现良好，进而导致一些准确率问题；
- 模型大小：kNN需要所有训练数据，因此对容量的要求较高；
- 预测时间：kNN算法对于一个输入数据要计算所有训练数据与它的距离，使得算法无法实现实时预测。
目前已有针对上述问题的解决方案：
- 度量学习：针对某一特定任务学习距离度量以获得高精度，但模型大小和计算时间都会增大；
- kd-trees：减少了预测时间，但是预测精度不行；
- 随机近邻压缩（SNC）减少了数据集大小，但是预测精度不行。
protoNN算法用下面的三点解决上面提到的问题：
- 稀疏低维投影：用一个稀疏投影矩阵降维；
- 原型：学习原型（Prototypes）去表征整个训练集；
- 联合优化：投影矩阵、原型和它们的标签一起学习。对参数施加大小上的显性稀疏约束来保证内存够小，而不是训练完成后再修建模型。
不幸的是，优化问题非凸，但本文证明了具有迭代硬阈值化(IHT)的简单随机梯度下降(SGD)可以很好地进行优化。
如果固定投影矩阵和原型标签，原型本身可以在多项式时间内以至少一个常数的概率最优地学习。此外，假设一个强初始化条件，我们观察到我们的SGD+IHT方法，当提供少量样本时，与均值的稀疏性成正比，收敛于全局最优。虽然数据模型很简单，但它很好地捕获了问题公式背后的主要思想。此外，我们的分析是第一个对在这种情况下尝试学习压缩非线性模型的方法进行这样的分析。
最后，作者进行了广泛的实验，以基准测试ProtoNN与现有的最先进的方法的各种学习任务。首先，我们证明了在几个二进制（多类）问题上，具有2kB(16kB)内存预算的ProtoNN显著优于该情况下的所有现有方法。此外，在二进制类的情况下，我们证明了只有≈16kB的ProtoNN提供了与GBDT、RBF-SVM、1隐藏层NN等几乎相同的精度，这可能在相同的数据集上需要多达1GB的RAM。类似地，在多标签数据集上，ProtoNN可以提供100倍的压缩，准确率损失不超过1%。最后，我们证明了ProtoNN可以部署在一个小型的ArduinoUno设备上，并获得比现有方法更好的精度，同时显著降低了能量和预测时间成本。作者已经实现了ProtoNN作为一个开源嵌入式设备ML库的一部分：https://github.com/microsoft/ELL。
背景知识
kNN算法
kNN算法是一种懒惰学习算法，以分类任务为例：给定训练集$X$和一个正整数$K$，传入测试数据$x_i$，算法会从$X$中选出$K$个与$x_i$距离最近的数据，利用多数表决投票法决定$x_i$的类别。笔者也在https://github.com/Kaslanarian/ml-model-code/blob/main/knn.py中设计了简单的kNN分类和回归。
K-d trees
其缺陷主要是训练时间过长，上面提到的k-d树虽然减少了时间，但会导致准确率下降，此外它们仍需要所有的训练数据，这对小型设备来说难以承受。
大间隔最近邻
LMNN属于度量学习,学习一个欧式距离度量的函数，优化目标：对于一个输入$x_i$的$k$个近邻都属于同一类别，而不同类别的样本与$x_i$保持一定大的距离。与kNN相比，LMNN的转换矩阵可以将数据映射到更低的维度，并减少总体模型大小，但对于大多数资源稀缺的设备来说，它仍然太大了。
原型
原型是指样本空间中具有代表性的点，举个例子，kmeans算法中得到的$k$个中心店就是$k$个原型。
SNC, DSNC和BNC
都属于近邻压缩算法，都是要学习一组原型，使特定类概率模型的可能性最大化。
问题描述
给定$n$个数据和标签：
\[X=[\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n]^\top\\ Y=[\mathbf{y}_1,\mathbf{y}_2,\cdots,\mathbf{y}_n]^\top\\\]其中$\mathbf{x}_i\in\mathbb{R}^d$，$\mathbf{y}_i\in\mathcal{Y}$。我们规定$\mathbf{y}_i\in\{0,1\}^L$且$|\mathbf{y}_i|=1$。我们的目标训练一个可以占用内存小且可以准确预测的模型。考虑kNN决策函数的平滑版本（Smooth version）：
\[\hat{\mathbf{y}}=\rho(\hat{s})=\rho(\sum_{i=1}^n\sigma(\mathbf{y}_i)K(\mathbf{x},\mathbf{x}_i))\]其中$\sigma:\mathcal{Y}\to\mathbb{R}^L$，将一个标签与一个“积分向量”(score vector) 对应；$K:\mathbb{R}^d\times\mathbb{R}^d\to\mathbb{R}$，表征两个数据的相似程度；$\rho:\mathbb{R}^L\to\mathcal{Y}$将积分向量映射到标签空间。总的来说，上面的表达式评价输入样本$\mathbf{x}$与训练集中每个样本的相似度，并以此加权，从而返回最可能的类别。以标准的多分类kNN为例：$\sigma$是恒等映射，而$\rho$满足：
\[\rho(x)_i=\mathbb{I}(x_i=\max(x))\]也就是最大项所在的位置设为1，其余为0；$K(\mathbf{x},\mathbf{x}_i)=\mathbb{I}[\mathbf{x}_i\in\mathcal{N}_k(\mathbf{x})]$，其中$\mathcal{N}_k(\mathbf{x})$是$X$中$k$个与$\mathbf{x}$最近的数据集。
kNN在运算时需要所有的训练数据，从而带来训练时间和模型尺寸的增加，这在小型设备上式不允许的。因此，我们需要用几个“原型”去表征整个训练集，也就是学习原型$B=[\mathbf{b_1},\mathbf{b_2},\cdots,\mathbf{b_m}]$和对应的积分向量$Z=[\mathbf{z_1},\mathbf{z_2},\cdots,\mathbf{z_m}]\in\mathbb{R}^{L\times m}$，所以决策函数重写为
\[\hat{\mathbf{y}}=\rho(\sum_{j=1}^m\mathbf{z}_jK(\mathbf{x},\mathbf{b}_j))\]但是，$K$往往是一个固定的函数，比如RBF径向基函数，它不会随不同任务而改变，因而带来不准确的预测。因此，本文引入一个降维投影矩阵$W^{\hat{d}\times d}$来解决这一问题。也就是说，我们的决策函数再次重写：
\[\hat{\mathbf{y}}=\rho(\sum_{j=1}^m\mathbf{z}_jK(W\mathbf{x},\mathbf{b}_j))\]需要学习的参数就有三个：
- 投影矩阵：$W^{\hat{d}\times d}$；
- 原型向量：$B=[\mathbf{b_1},\mathbf{b_2},\cdots,\mathbf{b_m}]\in\mathbb{R}^{\hat{d}\times m}$；
- 原型的对应积分向量：$Z=[\mathbf{z_1},\mathbf{z_2},\cdots,\mathbf{z_m}]\in\mathbb{R}^{L\times m}$
$K$对模型性能有很大影响，protoNN使用高斯核函数：
\[K_\gamma(x,y)=\exp(-\gamma^2\|x-y\|_2^2)\]注意到如果$W$是一个方阵，也就是只投影不降维，那么上面的决策函数等价于二分类正定核支持向量机的决策函数。
训练目标和算法
现在定义优化问题的标准形式。定义经验误差：
\[\mathcal{R}_{emp}(Z,B,W)=\frac1n\sum_{i=1}^n\mathcal{L}\bigg(\mathbf{y}_i,\sum_{j=1}^m\mathbf{z}_jK_{\gamma}(\mathbf{b}_j,W\mathbf{x}_i) \bigg)\]其中$\mathcal{L}(\mathbf{y},\hat{s})$是积分向量和目标标签的误差，可以是hinge损失（二分类），平方损失等。文章利用稀疏约束作为优化问题的约束条件避免过拟合，同时显式控制模型的大小：
\[\min_{Z:\|Z\|_0\le s_Z,B:\|B\|_0\le s_B,W:\|W\|_0\le s_W}\mathcal{R}_{emp}(Z,B,W)\]其中$|\cdot|_0$是矩阵的0范数，等价于矩阵中非0元素个数。此外，本文将损失函数设置为均方误差函数，以便梯度的求解。
下图是该问题的优化算法：
该算法用随机梯度下降法交替优化三个参数，注意到$HT_{s_Z}$算子将梯度下降后的结果稀疏化以时刻满足稀疏约束。SGD的步长满足$\eta_t=\eta_0/t$，也就是随下降次数递减。由于该问题非凸，初始化对模型性能影响很大，对应简单的二分类和多分类问题，$W$初始化为一个满足高斯分布的随机矩阵；而在大型多分类任务中，会采用LMNN中的初始化方法，在此略去；至于原型$B$的初始化，有两种方法，应用于两种情况：
- 随机选择训练集数据作为原型，常用于多标签任务；
- 利用K均值聚类筛选出原型，常用于二分类和多分类。
收敛性证明
文章想证明了即使是这样一个非凸问题，但利用SGD，在某些条件下仍可以线性速率收敛到几乎最优的解。作者强调了本文只是研究收敛速率，还是在固定$W$和$Z$，只优化$B$的情况下。
设数据从一个简单的高斯混合模型中产生：
\[\mathbf{x}_i\mathop{\sim}\limits^{i.i.d}0.5\cdot\mathcal{N}(\mu_+,I)+0.5\cdot\mathcal{N}(\mu_-,I)\in\mathbb{R}^d\]对应的标签$\mathbf{y}_i$表明该数据是从哪个高斯分布中产生。当两个高斯分布划分得很好（well-seprated）时，理论上可以得到两个原型$\mathbf{b}^\star_+$和$\mathbf{b}^\star_-$，投影矩阵$W=I$，$Z=[\mathbf e_1,\mathbf e_2]$，其中$\mathbf e_i$是第$i$个标准正交基向量。此时该分类器近似于一个贝叶斯最优分类器。
证明时抛弃了$B$的稀疏性，也就是$s_B=2d$，运行所有元素都非0。设置高斯核函数参数$\gamma^2=\frac12$。
定理1
令
\[X=[\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n]^\top\\ Y=[\mathbf{y}_1,\mathbf{y}_2,\cdots,\mathbf{y}_n]^\top\\\]数据是由上面提到的高斯混合模型生成，设$W=I,Z=[\mathbf{e}_1,\mathbf{e}_2]$，$\mathbf{b}_+$和$\mathbf{b}_-$为两个原型，当$n\to\infty$时，设
\[\begin{aligned} \bar{\mu}&=\mu_+-\mu_-\\ \boldsymbol{\Delta}_+&=\mathbf{b}_+-\mu_+\\ \boldsymbol{\Delta}_-&=\mathbf{b}_+-\mu_-\\ \end{aligned}\]对于一个固定的$\delta>0$，使得
\[\boldsymbol{\Delta}_+^T\bar{\mu}\ge-\dfrac{(1-\delta)}{2}\|\bar{\mu}\|^2\]对于一个固定的$\alpha>0$，使得
\[d\ge8(\alpha-\delta)\|\bar{\mu}\|^2\]那么，在梯度下降$\textbf{b}_+^\prime=\textbf{b}_+-\eta\nabla_{\textbf{b}_+}\mathcal{R}$的时候，其中$\mathcal{R}=\mathbb{E}(\mathcal{R}_{emp})$，当$\eta$选择恰当，则有：
\[\text{if }\|\boldsymbol{\Delta}_+\|\ge8\|\bar{\mu}\|\exp\big\{-\dfrac{\alpha\|\bar{\mu}\|^2}{4} \big\},\|\mathbf{b}_+^\prime-\mu_+\|^2\le\|\mathbf{b}_+-\mu_+\|^2\bigg(1-0.01\exp\big\{-\dfrac{\alpha\|\bar{\mu}\|^2}{4}\big\} \bigg)\]该定理说明如果$\textbf{b}_+$和$\mu_+$之间的距离比和$\mu_-$之间的要小，那么梯度下降法会呈几何级地缩小$\textbf{b}_+$和$\mu_+$的距离，直到$\textbf{b}_+$收敛到$\mu_+$的一个邻域内，该领域的半径和$\Vert\bar{\mu}\Vert$呈指数关系。
定理2
$X,Y,\bar{\mu},\boldsymbol{\Delta}_+,\boldsymbol{\Delta}_-$的定义和上面相同，对于一个固定的$\delta>0$，使得
\[\boldsymbol{\Delta}_+^T\bar{\mu}\ge-\dfrac{(1-\delta)}{2}\|\bar{\mu}\|^2\]此外，$|\bar{\mu}|^2\ge\dfrac{4}{\ln(0.01)\delta}$且$|\boldsymbol\Delta_+|^2\le0.05$，那么当$W=I$且$Z=[\textbf{e}_1,\textbf{e}_2]$时，$\mathcal{R}$是关于$B$的强凸函数，且条件数限制在20之内。
有界条件数的强凸性保证了更快的收敛速度。该定理也保证了，在$O(s_B\log d)$数据量下，该算法可以在多项式时间内收敛到稀疏的$\mu_+$领域。
实验
在文章的最后，作者进行了一系列实验，主要是从下面几个方面验证模型效果：
- 在严重资源受限的设置中，要求模型大小小于2kb(ArduinoUno等物联网设备)，protoNN优于所有最先进的压缩方法;
- 对于16−32kB范围内的模型大小，模型拥有与最佳未压缩方法相当的精度；
- 在多类和多标签问题中，实现了接近最先进的精度，并减少了一个数量级的模型大小，从而表明该方法足够灵活和通用，可以处理各种各样的问题。
性能判别准则：模型大小，准确率，预测时间和能耗，可以发现本文的性能度量要比一般模型多。
