RPS: A Generic Reservoir Patterns Sampler

• URL: http://arxiv.org/abs/2411.00074v1
• Date: Thu, 31 Oct 2024 16:25:21 GMT
• Title: RPS: A Generic Reservoir Patterns Sampler
• Authors: Lamine Diop, Marc Plantevit, Arnaud Soulet,
• Abstract summary: We introduce an approach that harnesses a weighted reservoir to facilitate direct pattern sampling from streaming batch data. We present a generic algorithm capable of addressing temporal biases and handling various pattern types, including sequential, weighted, and unweighted itemsets.
• Score: 1.09784964592609
• License:
• Abstract: Efficient learning from streaming data is important for modern data analysis due to the continuous and rapid evolution of data streams. Despite significant advancements in stream pattern mining, challenges persist, particularly in managing complex data streams like sequential and weighted itemsets. While reservoir sampling serves as a fundamental method for randomly selecting fixed-size samples from data streams, its application to such complex patterns remains largely unexplored. In this study, we introduce an approach that harnesses a weighted reservoir to facilitate direct pattern sampling from streaming batch data, thus ensuring scalability and efficiency. We present a generic algorithm capable of addressing temporal biases and handling various pattern types, including sequential, weighted, and unweighted itemsets. Through comprehensive experiments conducted on real-world datasets, we evaluate the effectiveness of our method, showcasing its ability to construct accurate incremental online classifiers for sequential data. Our approach not only enables previously unusable online machine learning models for sequential data to achieve accuracy comparable to offline baselines but also represents significant progress in the development of incremental online sequential itemset classifiers.

Related papers

• Iterative Forgetting: Online Data Stream Regression Using Database-Inspired Adaptive Granulation [1.6874375111244329]
  We present a database-inspired datastream regression model that uses inspiration from R*-trees to create granules from incoming datastreams. Experiments demonstrate that the ability of this method to discard data produces a significant order-of-magnitude improvement in latency and training time.
  arXiv  Detail & Related papers  (2024-03-14T17:26:00Z)
• Stochastic Amortization: A Unified Approach to Accelerate Feature and Data Attribution [62.71425232332837]
  We show that training amortized models with noisy labels is inexpensive and surprisingly effective. This approach significantly accelerates several feature attribution and data valuation methods, often yielding an order of magnitude speedup over existing approaches.
  arXiv  Detail & Related papers  (2024-01-29T03:42:37Z)
• Diffusion Generative Flow Samplers: Improving learning signals through partial trajectory optimization [87.21285093582446]
  Diffusion Generative Flow Samplers (DGFS) is a sampling-based framework where the learning process can be tractably broken down into short partial trajectory segments. Our method takes inspiration from the theory developed for generative flow networks (GFlowNets)
  arXiv  Detail & Related papers  (2023-10-04T09:39:05Z)
• On the challenges to learn from Natural Data Streams [6.602973237811197]
  In real-world contexts, sometimes data are available in form of Natural Data Streams. This data organization represents an interesting and challenging scenario for both traditional Machine and Deep Learning algorithms. In this paper, we investigate the classification performance of a variety of algorithms that receive as training input Natural Data Streams.
  arXiv  Detail & Related papers  (2023-01-09T16:32:02Z)
• Continual Learning with Optimal Transport based Mixture Model [17.398605698033656]
  We propose an online mixture model learning approach based on nice properties of the mature optimal transport theory (OT-MM) Our proposed method can significantly outperform the current state-of-the-art baselines.
  arXiv  Detail & Related papers  (2022-11-30T06:40:29Z)
• Data Sampling Affects the Complexity of Online SGD over Dependent Data [54.92366535993012]
  We show how different data sampling schemes affect the sample complexity of online gradient descent over highly dependent data. Even subsampling a subset of data samples can accelerate the convergence of online SGD over highly dependent data.
  arXiv  Detail & Related papers  (2022-03-31T07:48:30Z)
• One Backward from Ten Forward, Subsampling for Large-Scale Deep Learning [35.0157090322113]
  Large-scale machine learning systems are often continuously trained with enormous data from production environments. The sheer volume of streaming data poses a significant challenge to real-time training subsystems and ad-hoc sampling is the standard practice. We propose to record a constant amount of information per instance from these forward passes. The extra information measurably improves the selection of which data instances should participate in forward and backward passes.
  arXiv  Detail & Related papers  (2021-04-27T11:29:02Z)
• Learning summary features of time series for likelihood free inference [93.08098361687722]
  We present a data-driven strategy for automatically learning summary features from time series data. Our results indicate that learning summary features from data can compete and even outperform LFI methods based on hand-crafted values.
  arXiv  Detail & Related papers  (2020-12-04T19:21:37Z)
• Continual Prototype Evolution: Learning Online from Non-Stationary Data Streams [42.525141660788]
  We introduce a system to enable learning and prediction at any point in time. In contrast to the major body of work in continual learning, data streams are processed in an online fashion. We obtain state-of-the-art performance by a significant margin on eight benchmarks, including three highly imbalanced data streams.
  arXiv  Detail & Related papers  (2020-09-02T09:39:26Z)
• Automatic Recall Machines: Internal Replay, Continual Learning and the Brain [104.38824285741248]
  Replay in neural networks involves training on sequential data with memorized samples, which counteracts forgetting of previous behavior caused by non-stationarity. We present a method where these auxiliary samples are generated on the fly, given only the model that is being trained for the assessed objective. Instead the implicit memory of learned samples within the assessed model itself is exploited.
  arXiv  Detail & Related papers  (2020-06-22T15:07:06Z)
• Tracking Performance of Online Stochastic Learners [57.14673504239551]
  Online algorithms are popular in large-scale learning settings due to their ability to compute updates on the fly, without the need to store and process data in large batches. When a constant step-size is used, these algorithms also have the ability to adapt to drifts in problem parameters, such as data or model properties, and track the optimal solution with reasonable accuracy. We establish a link between steady-state performance derived under stationarity assumptions and the tracking performance of online learners under random walk models.
  arXiv  Detail & Related papers  (2020-04-04T14:16:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.