Learning state machines via efficient hashing of future traces

• URL: http://arxiv.org/abs/2207.01516v1
• Date: Mon, 4 Jul 2022 15:24:21 GMT
• Title: Learning state machines via efficient hashing of future traces
• Abstract summary: State machines are popular models to model and visualize discrete systems such as software systems, and to represent regular grammars. Most algorithms that passively learn state machines from data assume all the data to be available from the beginning and they load this data into memory. We propose a method to learn state machines from data streams using the count-min-sketch data structure to reduce memory requirements.
• Score: 10.57164270098353
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: State machines are popular models to model and visualize discrete systems such as software systems, and to represent regular grammars. Most algorithms that passively learn state machines from data assume all the data to be available from the beginning and they load this data into memory. This makes it hard to apply them to continuously streaming data and results in large memory requirements when dealing with large datasets. In this paper we propose a method to learn state machines from data streams using the count-min-sketch data structure to reduce memory requirements. We apply state merging using the well-known red-blue-framework to reduce the search space. We implemented our approach in an established framework for learning state machines, and evaluated it on a well know dataset to provide experimental data, showing the effectiveness of our approach with respect to quality of the results and run-time.

Related papers

• (PAC-)Learning state machines from data streams: A generic strategy and an improved heuristic (Extended version) [4.569217855609235]
  This is an extended version of our publication Learning state machines from data streams: A generic strategy.<n>It has been extended with a formal proof on PAC-bounds, and the discussion and analysis of a similar approach has been moved from the appendix to a full Section.
  arXiv  Detail & Related papers  (2026-04-02T16:35:07Z)
• From Big Data to Fast Data: Towards High-Quality Datasets for Machine Learning Applications from Closed-Loop Data Collection [0.9624643581968987]
  This paper introduces the concept of Fast Data for automotive systems engineering.<n>The approach shifts data selection and recording onto the vehicle as the data source.<n>By enabling real-time, context-aware decisions on whether and which data should be recorded, data collection can be aligned with data quality objectives.
  arXiv  Detail & Related papers  (2026-03-31T09:20:36Z)
• Learning-Augmented Moment Estimation on Time-Decay Models [55.06256430461023]
  We use an oracle for the heavy-hitters of datasets to give learning-augmented algorithms for a number of fundamental problems.<n>We complement our theoretical results with a number of empirical evaluations that demonstrate the practical efficiency of our algorithms on real and synthetic datasets.
  arXiv  Detail & Related papers  (2026-03-03T00:42:34Z)
• X-TIME: An in-memory engine for accelerating machine learning on tabular data with CAMs [19.086291506702413]
  Modern tree-based Machine Learning models shine in extracting relevant information from structured data. In this work, we focus on an overall analog-digital architecture implementing a novel increased precision analog CAM. Results evaluated in a single chip at 16nm technology show 119x lower latency at 9740x higher throughput compared with a state-of-the-art GPU.
  arXiv  Detail & Related papers  (2023-04-03T18:20:31Z)
• A Memory Transformer Network for Incremental Learning [64.0410375349852]
  We study class-incremental learning, a training setup in which new classes of data are observed over time for the model to learn from. Despite the straightforward problem formulation, the naive application of classification models to class-incremental learning results in the "catastrophic forgetting" of previously seen classes. One of the most successful existing methods has been the use of a memory of exemplars, which overcomes the issue of catastrophic forgetting by saving a subset of past data into a memory bank and utilizing it to prevent forgetting when training future tasks.
  arXiv  Detail & Related papers  (2022-10-10T08:27:28Z)
• Advancing Reacting Flow Simulations with Data-Driven Models [50.9598607067535]
  Key to effective use of machine learning tools in multi-physics problems is to couple them to physical and computer models. The present chapter reviews some of the open opportunities for the application of data-driven reduced-order modeling of combustion systems.
  arXiv  Detail & Related papers  (2022-09-05T16:48:34Z)
• Incremental Online Learning Algorithms Comparison for Gesture and Visual Smart Sensors [68.8204255655161]
  This paper compares four state-of-the-art algorithms in two real applications: gesture recognition based on accelerometer data and image classification. Our results confirm these systems' reliability and the feasibility of deploying them in tiny-memory MCUs.
  arXiv  Detail & Related papers  (2022-09-01T17:05:20Z)
• SOLIS -- The MLOps journey from data acquisition to actionable insights [62.997667081978825]
  In this paper we present a unified deployment pipeline and freedom-to-operate approach that supports all requirements while using basic cross-platform tensor framework and script language engines. This approach however does not supply the needed procedures and pipelines for the actual deployment of machine learning capabilities in real production grade systems.
  arXiv  Detail & Related papers  (2021-12-22T14:45:37Z)
• Bridge Data Center AI Systems with Edge Computing for Actionable Information Retrieval [0.5652468989804973]
  High data rates at modern synchrotron and X-ray free-electron lasers motivate the use of machine learning methods for data reduction, feature detection, and other purposes. We describe here how specialized data center AI systems can be used for this purpose.
  arXiv  Detail & Related papers  (2021-05-28T16:47:01Z)
• ALT-MAS: A Data-Efficient Framework for Active Testing of Machine Learning Algorithms [58.684954492439424]
  We propose a novel framework to efficiently test a machine learning model using only a small amount of labeled test data. The idea is to estimate the metrics of interest for a model-under-test using Bayesian neural network (BNN)
  arXiv  Detail & Related papers  (2021-04-11T12:14:04Z)
• Text Classification Using Hybrid Machine Learning Algorithms on Big Data [0.0]
  In this work, two supervised machine learning algorithms are combined with text mining techniques to produce a hybrid model. The result shows that the hybrid model gave 96.76% accuracy as against the 61.45% and 69.21% of the Na"ive Bayes and SVM models respectively.
  arXiv  Detail & Related papers  (2021-03-30T19:02:48Z)
• A Survey on Large-scale Machine Learning [67.6997613600942]
  Machine learning can provide deep insights into data, allowing machines to make high-quality predictions. Most sophisticated machine learning approaches suffer from huge time costs when operating on large-scale data. Large-scale Machine Learning aims to learn patterns from big data with comparable performance efficiently.
  arXiv  Detail & Related papers  (2020-08-10T06:07:52Z)
• Dataset Condensation with Gradient Matching [36.14340188365505]
  We propose a training set synthesis technique for data-efficient learning, called dataset Condensation, that learns to condense large dataset into a small set of informative synthetic samples for training deep neural networks from scratch. We rigorously evaluate its performance in several computer vision benchmarks and demonstrate that it significantly outperforms the state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-06-10T16:30:52Z)
• Guidelines for enhancing data locality in selected machine learning algorithms [0.0]
  We analyze one of the means to increase the performances of machine learning algorithms which is exploiting data locality. Repeated data access can be seen as redundancy in data movement. This work also identifies some of the opportunities for avoiding these redundancies by directly reusing results.
  arXiv  Detail & Related papers  (2020-01-09T14:16:40Z)

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.