Nearest Neighbor Ensembles: An Effective Method for Difficult Problems in Streaming Classification with Emerging New Classes

正文索引 [隐藏]

文章链接:https://www.researchgate.net/publication/338950752_Nearest_Neighbor_Ensembles_An_Effective_Method_for_Difficult_Problems_in_Streaming_Classification_with_Emerging_New_Classes

Problem & Motivation

文章的大背景是 SENC Problem,也就是运行在可能出现新类的数据流上的分类问题。
在这样的问题中,大部分算法判断一个样本是否属于新类,通常以特征空间中样本间的几何关系作为依据,我的理解是将新类当成一个异常样本进行检测。这样做无形中引出了一个假设:新类的样本在特征空间中和已知类的样本应该比较远。

据此,文章指出,新类样本在特征空间中和已知类分得比较开仅仅只是一种新类的出现方式,叫做 high-\alpha SENC Problem,而且这也是容易检测的一种。而新类样本也可以会离已知类比较近(这里的比较近指绝对距离较近,即样本的密度比较高,特征空间上几何依旧能分离出来的),叫做 low-\alpha SENC Problem。例如下图,流 A 上的新类距离已知类的距离较远容易区分,为 high-\alpha SENC Problem,而流 B 上距离则较近,为 low-\alpha SENC Problem,如果没有针对新的解决方案则较难区别。现有的技术通常在检测新类的时候仅考虑 high-\alpha,所以在检测的时候容易将异常样本判定为新类,精度受损。


Low Alpha & High Alpha

文章的动机就是要降低,仅考虑 high-\alpha SENC Problem 所造成的损失,设计一种算法能够同时高效地处理 low-\alpha 与 high-\alpha 混杂的 SENC Problem,以提升分类器的性能。文章解决问题的难点在于:a) 如何提升 low-\alpha 上的新类检测准确率; b) 在 low-\alpha 与 high-\alpha 混合的问题中自适应。

Technique

识别问题难度

文章定义了 \alpha-SENC Problem,其中 \alpha 衡量新类与已知类别之间的间隔程度,定义如下:
\alpha(D_K, D_N) = \frac{M(D_K, D_N)}{C(D_K)}
其中,D_K 是可能包含新类的数据集,D_N 是已知类的数据集。
M(D_K, D_N) 衡量了两个数据集间样本的最小距离 M(D_K, D_N)=\min\limits_{\textbf{x}\in D_K, \textbf{x}’\in D_N}||\textbf{x} – \textbf{x}’||
C(D) 衡量了数据集内每个样本的最邻近样本平均距离,C(D) = \frac{1}{|D|}\sum_{\textbf{x} \in D }\tau(\textbf{x})
\tau(\textbf{x}) 则定义为数据里中 \textbf{x} 到其最邻近样本的欧几里得距离。

在这种定义下,\alpha 定义了样本间隔程度,当 \alpha 很大的时候新类与已知类相距较大,问题容易,否则问题困难。

检测新类、识别已知类

检测新类、识别已知类使用的是一个集成模型,与 iNNE 文章中的方法类似(评分环节不同)。

已知类的数据集为 \mathcal D^{(k)}, k=1,\cdots , K,从每一个类别的数据 \mathcal D^k 中随机采样 p 次,每次采样 \psi 个得到若干个样本子集 \mathcal D_{i}^{(k)}

针对每一个 \mathcal D_{i}^{(k)},都生成一个高维球体的集合,它的半径为对应的 \tau(\text{c})。对于 \mathcal D^{(k)},那我们就有一个集合的集合:

\mathbb B^{(k)} =\{\{B(\textbf{c}):\textbf{c}\in \mathcal D_i^{(k)}\},i=1,\cdots,p\}

根据得到的 K\times p\times \psi 个维度球体模型,我们对于新来的样本计算 Knew-class socre N^{(k)}Kknown-class score P^{(k)}

先看 new-class score 是怎么算的:

N^{(k)}(\textbf{x}) = \frac{1}{p} \sum_{i=1}^pN_i^{(k)}(\textbf{x}),\\
N_i^{(k)}(\textbf{x}) =
\begin{cases}
[1-\frac{\tau(\eta_{cnn(\textbf{x})})}{||\textbf{x} – cnn(\textbf{x})||}]_{+}, &if~\textbf{x}\in \bigcup\limits_{\textbf{c}\in \mathcal D_{i}^{(k)} }B(\textbf{c}),\\
1, &otherwise.
\end{cases}

其中,\eta_{cnn}(\textbf{x}) 就是这个等待检测的样本落入的最小半径的高维球体的中心样本。
说白了,上面的式子就是给 D_{i}^{(k)} 里的每一个元素都设置了检测球体,半径为距离它最近的同类样本的距离,一个测试样本对于类别 k 的新类得分为:它落入半径最小的检测球体距离中心距离 / 球半径,然后每一类的 p 个模型进行一次平均集成。

再看 known-classes score 的计算方法:

P^{(k)}(\textbf{x}) = \frac{1}{p}\sum_{i=1}^{p} \mathbb I[N_i^{k}(\textbf{x}) < t], for~k=1,\cdots,K

这里,计算了样本在半径最小的检测球中是否落入在阈值 t 限定的一个内球的概率。

最终的模型得到的结果为:

f(\textbf{x}) =
\begin{cases}
NC, &if~N_i^{(k)} \geq t, \forall k = 1,\cdots, K,\\
\argmax\limits_{k=1,\cdots,K}P^{(k)}(\textbf{x}), &otherwise.
\end{cases}

也就是当所有类的集成模型评分一致大于阈值的时候,才认为是新类,否则将通过模型评分低于阈值的概率作为置信度,输出置信度最高的分类。

我认为集成在这里的意义是做到了一件事情:分开了低概率与新类,对于检测新类,阈值放在了集成之后,对于分类已知类阈值放在集成前,通过集成才有了置信度。感觉可以这样做,但是没有什么非常一定这样的道理……

更新模型

更新模型的部分就比较简单多了,一旦某个新类数据有一定积累后,我们新建 \mathbb B^{K+1} 即可。

Result

这篇文章在人造数据集、Benchmark 数据集(Forest Cover, HAR, MNIST, Fashion-MNIST)和真实数据集(用New York Times API 和 Word2Vec 造的)中与其他同类算法进行了比较,同时实验还分成了固定 \alpha 与动态 \alpha 两个部分进行。


Paper Result

可以发现,在 low-\alpha 的问题中算法还是非常占优势,准确率均达到了 SOTA,在 high-\alpha 与 mixed-\alpha 中效果也不明显输与其他算法,可以说做到了 \alpha 自适应。

另外,文章还比较了不同 \alpha 下的性能与真实世界数据集上的性能。


Paper Result Graph

Conclusion

文章重新研究了 SENC Problem,定义了 \alpha-SENC Problem 来衡量问题的困难程度,同时提出了一种可以自适应 \alpha 的最邻近集成方法。

我认为文章使用集成的方法,有效地将新类与已知异常类进行了区别,这是有效提升了性能的一个原因。另外,\alpha 这个参数其实一定程度上也可以衡量异常类存在的异常程度。

这个方法依过于依赖样本的集合性质,没有需要学习与优化的参数,这限制了方法可以应用的数据集的范围,一点改进可以考虑增加一些可训练参数,让模型学习到关于样本的知识。

另外,\alpha 的问题同样存在于半监督的 SENC 问题中,但是面临的问题更大了,因为 SSENC 问题中必将缺少关于标记数据与新类的标记数据,衡量 \alpha 不准确,最邻近方法也不易直接应用。