从间断与连续数据流中学习动态模式，适用于智能监控等在线场景。
Learning from Snapshots of Discrete and Continuous Data Streams
- 提出两种学习框架：更新部署与盲预测，分别处理有反馈和无反馈的数据采样。
- 证明有限Littlestone维数的概念类可在均匀采样下实现有界误差学习。
- 揭示盲预测下非平凡类别不可学习，但自适应算法可有效捕捉时变函数模式。
想象一个智能相机陷阱，仅在自适应选择的时间点捕获图像，以理解特定栖息地内动物移动模式。这些‘快照’是数据流在选定时刻的片段，提供了随时间演变的不同动物行为的片段。通过快照学习连续时间过程，如智能相机陷阱，是众多在线学习情境的核心主题。本文从学习理论角度探讨从离散和连续数据流中学习各类函数的根本特性。在首个框架——‘更新与部署’设置中，学习算法离散地从过程中查询，以更新预测器，该预测器根据数据流输入进行预测。我们构建了一种均匀采样算法，可对任意有限Littlestone维度的概念类实现有界误差学习。第二个框架称为‘盲预测’设置，学习算法独立于过程生成预测，仅在决定查询时才与过程交互。有趣的是，我们发现可学习性存在显著差异：非平凡概念类在此设置下不可学习。然而，我们证明自适应学习算法对于学习依赖时间与数据的函数集合（即模式类）在任一框架中都是必要的。最后，我们为离散数据流下的盲预测设置建立了模式类的理论体系。
原文摘要 · Abstract (English)
Imagine a smart camera trap selectively clicking pictures to understand animal movement patterns within a particular habitat. These "snapshots", or pieces of data captured from a data stream at adaptively chosen times, provide a glimpse of different animal movements unfolding through time. Learning a continuous-time process through snapshots, such as smart camera traps, is a central theme governing a wide array of online learning situations. In this paper, we adopt a learning-theoretic perspective in understanding the fundamental nature of learning different classes of functions from both discrete data streams and continuous data streams. In our first framework, the \textit{update-and-deploy} setting, a learning algorithm discretely queries from a process to update a predictor designed to make predictions given as input the data stream. We construct a uniform sampling algorithm that can learn with bounded error any concept class with finite Littlestone dimension. Our second framework, known as the \emph{blind-prediction} setting, consists of a learning algorithm generating predictions independently of observing the process, only engaging with the process when it chooses to make queries. Interestingly, we show a stark contrast in learnability where non-trivial concept classes are unlearnable. However, we show that adaptive learning algorithms are necessary to learn sets of time-dependent and data-dependent functions, called pattern classes, in either framework. Finally, we develop a theory of pattern classes under discrete data streams for the blind-prediction setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。