Symbolic Register Automata for Complex Event Recognition and Forecasting

• URL: http://arxiv.org/abs/2110.04032v1
• Date: Fri, 8 Oct 2021 11:04:51 GMT
• Title: Symbolic Register Automata for Complex Event Recognition and Forecasting
• Authors: Elias Alevizos, Alexander Artikis, Georgios Paliouras
• Abstract summary: Symbolic Register Automata (SRA) is a combination of symbolic and register automata. We show how SRA can be used in Complex Event Recognition in order to detect patterns upon streams of events. We also show how the behavior of SRA, as they consume streams of events, can be given a probabilistic description.
• Score: 70.7321040534471
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose an automaton model which is a combination of symbolic and register automata, i.e., we enrich symbolic automata with memory. We call such automata Symbolic Register Automata (SRA). SRA extend the expressive power of symbolic automata, by allowing Boolean formulas to be applied not only to the last element read from the input string, but to multiple elements, stored in their registers. SRA also extend register automata, by allowing arbitrary Boolean formulas, besides equality predicates. We study the closure properties of SRA under union, intersection, concatenation, Kleene closure, complement and determinization and show that SRA, contrary to symbolic automata, are not in general closed under complement and they are not determinizable. However, they are closed under these operations when a window operator, quintessential in Complex Event Recognition, is used. We show how SRA can be used in Complex Event Recognition in order to detect patterns upon streams of events, using our framework that provides declarative and compositional semantics, and that allows for a systematic treatment of such automata. We also show how the behavior of SRA, as they consume streams of events, can be given a probabilistic description with the help of prediction suffix trees. This allows us to go one step beyond Complex Event Recognition to Complex Event Forecasting, where, besides detecting complex patterns, we can also efficiently forecast their occurrence.

Related papers

• Complex Event Recognition with Symbolic Register Transducers: Extended Technical Report [51.86861492527722]
  We present a system for Complex Event Recognition based on automata. Our system is based on an automaton model which is a combination of symbolic and register automata. We show how SRT can be used in CER in order to detect patterns upon streams of events.
  arXiv  Detail & Related papers  (2024-07-03T07:59:13Z)
• Automata Cascades: Expressivity and Sample Complexity [90.53326983143644]
  We show that cascades allow for describing the sample complexity of automata in terms of their components. Our results show that one can in principle learn automata with infinite input alphabets and a number of states that is exponential in the amount of data available.
  arXiv  Detail & Related papers  (2022-11-25T11:02:33Z)
• Learning Automata-Based Complex Event Patterns in Answer Set Programming [0.30458514384586405]
  We propose a family of automata where the transition-enabling conditions are defined by Answer Set Programming (ASP) rules. We present such a learning approach in ASP and an incremental version thereof that trades optimality for efficiency and is capable to scale to large datasets. We evaluate our approach on two CER datasets and compare it to state-of-the-art automata learning techniques, demonstrating empirically a superior performance.
  arXiv  Detail & Related papers  (2022-08-31T12:40:44Z)
• Complex Event Forecasting with Prediction Suffix Trees: Extended Technical Report [70.7321040534471]
  Complex Event Recognition (CER) systems have become popular in the past two decades due to their ability to "instantly" detect patterns on real-time streams of events. There is a lack of methods for forecasting when a pattern might occur before such an occurrence is actually detected by a CER engine. We present a formal framework that attempts to address the issue of Complex Event Forecasting.
  arXiv  Detail & Related papers  (2021-09-01T09:52:31Z)
• Learning event-driven switched linear systems [7.766921168069532]
  We propose an automata theoretic learning algorithm for the identification of black-box switched linear systems. Our algorithm first uses the oracle to obtain the node labels of the system run on a given input sequence of events, and then extends Angluin's (L*)-algorithm to determine the FA that accepts the language of the given FA.
  arXiv  Detail & Related papers  (2020-09-27T12:32:40Z)
• Induction and Exploitation of Subgoal Automata for Reinforcement Learning [75.55324974788475]
  We present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task's subgoals. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding.
  arXiv  Detail & Related papers  (2020-09-08T16:42:55Z)
• Inferring Temporal Compositions of Actions Using Probabilistic Automata [61.09176771931052]
  We propose to express temporal compositions of actions as semantic regular expressions and derive an inference framework using probabilistic automata. Our approach is different from existing works that either predict long-range complex activities as unordered sets of atomic actions, or retrieve videos using natural language sentences.
  arXiv  Detail & Related papers  (2020-04-28T00:15:26Z)

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.