针对中等验证延迟和概念漂移问题的稳定区域增强型在线学习方法

《Pattern Recognition》：Stable region enhanced online learning method for intermediate verification latency and concept drift

　　钟子欣|宋丽燕|唐凤珍|袁博
中国深圳南方科技大学计算机科学与工程系

摘要
在非平稳数据流中，概念漂移的挑战因中间验证延迟（IVL）而加剧，IVL指的是数据特征与其对应标签之间的延迟。本文从一个新的角度探讨了IVL问题，通过研究特征空间内的稳定区域来识别不受概念漂移影响的数据。我们提出了基于质心的漂移指数（CDI），这是一种无监督的度量方法，用于量化漂移以识别这些稳定区域。在此基础上，我们引入了基于STable区域的数据利用（DUST）框架，该框架通过微聚类有效利用了暂时未标记和延迟标记的数据。在合成数据和真实世界数据集上进行的全面实验验证了CDI和DUST的有效性。结果表明，DUST在各种基础模型上的准确率提高了0.59%到2.29%，在合成数据流上的平均准确率为84.10%，在真实世界数据流上的平均准确率为63.18%。源代码和补充材料可在https://github.com/ZeroZill/CDI_DUST获取。

引言
尽管在线学习已在数据流分析中得到广泛应用并进行了广泛研究[1]、[2]，但大多数现有方法的一个显著局限性是过于乐观地假设数据点到达时即可立即获得真实标签。实际上，获取这些真实标签通常存在不可忽视的延迟。例如，在网络性能优化中，资源预加载旨在通过预加载数据密集型网络应用中的资源来提高带宽效率；然而，对这些预加载资源的反馈往往会有延迟[3]。同样，在工具状态监控中，使用切削力、振动和功率信号等间接测量值来评估工具磨损。手动标记所需的大量成本和时间经常导致验证过程中的显著延迟，主要是因为缺乏即时的故障状态标签[4]。在这些情况下，从接收到数据点到获取其对应真实标签之间的有限延迟被称为中间验证延迟（IVL）[5]，这是传统在线学习研究中很少考虑的因素。
IVL显著复杂化了在线学习，尤其是在频繁出现概念漂移的情况下。概念漂移描述了底层数据分布随时间变化的现象，这是非平稳数据流的常见特征[6]、[7]。在IVL的情况下，由于无法立即访问真实标签，这使得检测概念漂移和模型适应新概念变得困难，可能导致性能下降。在这种情况下，只有暂时未标记的数据和延迟标记的数据可用。因此，有效利用这两种类型的数据对于应对IVL带来的挑战至关重要。
一种有前景的策略是识别并利用特征空间内的稳定区域数据。正如[8]所指出的，特征空间的某些区域在较长时间内不受概念漂移的影响。这些稳定区域内的数据点可以保持其特征更长时间，使其成为模型更新的可靠指标。通过在IVL背景下关注这些稳定区域的数据，我们可以更有效地利用暂时未标记的数据和延迟标记的数据，从而减少已经受到概念漂移影响的数据引入的标签噪声和不准确性。虽然一些研究在传统在线学习环境中探讨了稳定区域的理解和识别[9]、[10]，但据我们所知，我们是首批在IVL存在且监督有限的情况下考虑利用稳定区域的研究者之一。

现有的解决IVL的方法大致可以分为三类：（1）等待数据到达；（2）带有回滚的伪标记；（3）带有校正的伪标记。最简单的方法是等待数据到达后再更新模型[11]、[12]、[13]。这种方法仅依赖于延迟标记的数据，忽略了暂时未标记数据的潜在价值，可能导致对概念漂移的适应速度较慢。第二种方法是带有回滚的伪标记，它为暂时未标记的数据分配伪标签并立即更新模型。如果后来发现这些伪标签不正确，则会回滚模型状态[4]、[14]。然而，如果没有有效的过滤过程，伪标记可能会引入大量噪声，导致频繁回滚和不稳定。最近的一种方法是带有校正的伪标记，它将伪标签的分配限制在每个类别的中心区域，这些区域被认为受概念漂移的影响较小。当识别出伪标签错误时，这种方法还会通过基于延迟标记的数据重新采样合成数据来校正模型[15]。尽管有这些改进，但如果概念漂移严重，这种方法仍然有可能使模型暴露于噪声中，并可能过度依赖过时的数据。
这三类方法都没有明确解决稳定区域的识别和利用问题。然而，适当利用稳定区域可以帮助减轻它们的局限性并提高模型性能。
为了填补这一空白，我们提出了一种无监督的测试统计量——基于质心的漂移指数（CDI），它通过测量两个时间步长之间的质心偏移来量化给定区域的漂移程度。这使我们能够确定数据点是否位于稳定区域内。在此基础上，我们引入了一个新的框架——基于STable区域的数据利用（DUST）。该框架利用微聚类以最小的空间使用量高效总结数据分布，并利用CDI来区分稳定区域数据，从而更有效地管理暂时未标记和延迟标记的数据。

本文的主要贡献如下：
1. 我们是第一个在IVL背景下解决区分和利用稳定区域数据挑战的研究者，提出了CDI作为一种新的测试统计量，用于评估区域稳定性和识别稳定区域数据点。
2. 我们提出了DUST，这是一个在线学习框架，它利用微聚类高效总结数据分布，并利用CDI识别稳定区域数据。这种方法提高了暂时未标记和延迟标记数据的有效利用，从而减轻了IVL的影响。
3. 我们在各种合成数据和真实世界数据集上进行了广泛的实验，以验证CDI和DUST框架的有效性。

问题表述
考虑一个具有概念漂移和IVL的数据流S=(xt,yt)∣t=1,2,…，其中xt∈X=R^d表示第t个时间步长到达的d维特征向量，yt∈Y=0,1,…,C表示其真实标签。每对观测值(xi,yt)遵循联合概率分布Pt(x,y)。由于概念漂移，不同时间步长tu和tv的观测值可能来自不同的联合概率分布，表示为Ptu(x,y)≠Ptv(x,y)[16]。
用T(?)表示任一特征的到达时间。

中间验证延迟
如第1节所讨论的，针对IVL的研究相对较少，可以大致分为以下三类：

提出的测试统计量
本节提出了我们的方法，用于识别稳定区域，称为基于质心的漂移指数（CDI），它是我们DUST框架的基础（见第6节）。具体来说，第4.1节定义了CDI；第4.2节介绍了确定给定数据点是否位于稳定区域的方法。

CDI的实验验证
本节评估了CDI的有效性。首先，我们展示了其实验分布和理论分布之间的对齐情况。接下来，我们可视化了它在指示稳定区域数据方面的效果，并进行了定量评估，将其与LDD[9]进行了比较。为了保持一致性和公平比较，我们将CDI和LDD的超参数设置为k=100和α=0.95，与[9]一致。

针对IVL的在线学习框架
在CDI的基础上，我们引入了DUST框架，扩展了等待数据到达的策略。核心思想是使用CDI识别稳定区域数据，并通过针对其特定特征定制的不同策略来利用它。对于暂时未标记的数据，我们为足够可靠的实例分配伪标签以立即更新模型。对于延迟标记的数据，我们强调那些位于稳定区域内的数据。DUST的工作流程如图5所示。

实验设置
我们在总共33个数据集上进行了实验，包括22个合成数据集和11个真实世界数据集，分别如表1和表2所示。这些数据集在具有IVL的在线学习背景下被广泛使用[30]。
为了系统地评估DUST在各种漂移场景下的表现，我们构建了22个类平衡的合成数据集，涵盖了四种类型的概念漂移：突然的、渐进的、反复的和递增的，每种类型的严重程度各不相同。这些数据集是使用六种方法生成的。

DUST的运行时间开销
DUST的运行时间消耗相对较高。如第7.3节所讨论的，其运行时间复杂度为O(d^3+ρNd^2+TH)，其中d是特征维度，ρ是邻域比率，N是维护的微聚类的最大数量，TH是与分类器推理和更新相关的成本。在DUST中，主要开销来自CDI计算，特别是两个操作：协方差聚合O(ρNd^2)和矩阵求逆O(d^3)。

结论
本文解决了中间验证延迟（IVL）的挑战，这在现实世界应用中经常发生，当延迟标记的数据流需要模型更新以适应概念漂移时尤为明显。我们提出了一种新的在线学习方法，以增强稳定区域数据的识别和利用。
具体来说，我们提出了基于质心的漂移指数（CDI），这是一种无监督的测试统计量，用于识别稳定区域并评估位于其中的数据点。

CRedI作者贡献声明
钟子欣：写作——审稿与编辑、撰写初稿、验证、方法论、调查、形式分析、数据整理、概念化。
宋丽燕：写作——审稿与编辑、撰写初稿、监督、项目管理、资金获取、概念化。
唐凤珍：验证、监督、资金获取。
袁博：验证、监督、项目管理、资金获取。

利益冲突声明
作者声明他们没有已知的竞争性财务利益或个人关系可能会影响本文报告的工作。

致谢
本工作得到了中国国家自然科学基金（NSFC）（项目编号62572154）、黑龙江省自然科学基金（项目编号JJ2024LH1948）、国家重点实验室机器人技术（项目编号2023-O11）以及哈尔滨工业大学人才启动项目（项目编号AUGA5710010924）的支持。
钟子欣自2022年起在中国深圳南方科技大学攻读计算机科学与技术硕士学位。他于2021年获得了南方科技大学的计算机科学与技术学士学位。他的研究兴趣集中在在线机器学习、数据挖掘、概念漂移和验证延迟上。