Reasoning over complex temporal specifications and noisy data streams

Abstract

Contemporary applications commonly demand the detection of ‘situations of interest’ in real-time and with minimal latency. In maritime situational awareness, e.g., it is crucial to identify and report vessel behaviours that may indicate dangerous, illegal or environmentally hazardous activities in a timely manner. Monitoring situations of interest is challenging, as large, high-velocity streams of data are being generated continuously, and it is not feasible to store these streams in memory and process them at a later time. Stream reasoning involves the real-time detection of critical situations by reasoning over large volumes of incrementally-arriving, symbolic data, typically termed as ‘events’. In order to support contemporary applications, a stream reasoning system needs to employ efficient reasoning algorithms that are tailored for the streaming setting, a highly expressive pattern specification language with a formal and declarative semantics, as well as techniques for handling noise and uncertainty. This thesis is motivated by the absence of a framework with all the aforementioned features, and aims at extending state-of-the-art computational frameworks in order to support stream reasoning effectively. We focus on frameworks that employ the Event Calculus, a logic programming formalism for representing events and reasoning about their effects over time. The Event Calculus exhibits a formal, declarative semantics, while supporting both instantaneous and durative events, hierarchical and relational event specifications, temporal persistence and background knowledge. RTEC is a computational framework that is based on the Event Calculus and includes several optimisation techniques for stream reasoning. We propose three extensions of RTEC, i.e., RTECο, RTEC-> and RTECA, supporting, respectively, temporal specifications with cyclic dependencies, events with delayed effects and situations specified using the relations of Allen’s interval algebra. Moreover, we study PIEC, i.e., an Event Calculus-based system for probabilistic event recognition, and present oPIEC, i.e., an extension of PIEC for reasoning over noisy event streams. In order to support large data streams, we propose two bounded-memory versions of oPIEC. All of our proposed frameworks have a formal semantics and feature optimised stream reasoning algorithms that have been assessed both theoretically and empirically, using large, real and synthetic data streams, in experiments that included comparisons with state-of-the-art frameworks. Our analysis demonstrates that RTECο, RTEC-> and RTECA are suitable for stream reasoning with complex temporal specifications, while the variants of oPIEC exhibit high predictive accuracy and reasoning efficiency when reasoning over noisy data streams.

Οι σύγχρονες εφαρμογές απαιτούν την ανίχνευση «καταστάσεων ενδιαφέροντος» σε πραγματικό χρόνο και με ελάχιστη καθυστέρηση. Στην επιτήρηση ναυτιλιακών δραστηριοτήτων, π.χ., είναι σημαντικό να εντοπίζονται και να αναφέρονται εγκαίρως συμπεριφορές πλοίων που μπορεί να υποδεικνύουν επικίνδυνες, παράνομες ή περιβαλλοντικά επιβλαβείς δραστηριότητες. Η επιτήρηση καταστάσεων ενδιαφέροντος αποτελεί πρόκληση, καθώς μεγάλες ροές δεδομένων υψηλής ταχύτητας παράγονται συνεχώς, ενώ δεν είναι εφικτό να αποθηκεύσουμε αυτά τα δεδομένα και να τα επεξεργαστούμε σε επόμενο χρόνο. Η συλλογιστική πάνω σε ροές δεδομένων περιλαμβάνει την ανίχνευση κρίσιμων καταστάσεων σε πραγματικό χρόνο, εφαρμόζοντας τεχνικές συλλογιστικής πάνω σε μεγάλους όγκους από σταδιακά παραγόμενα, συμβολικά δεδομένα, που συνήθως ονομάζονται «γεγονότα». Προκειμένου να υποστηρίζει σύγχρονες εφαρμογές, ένα σύστημα συλλογιστικής σε ροές δεδομένων πρέπει να χρησιμοποιεί αποτελεσματικούς αλγόριθμους συλλογιστικής που είναι προσαρμοσμένοι σε περιβάλλοντα ροών δεδομένων, μια εξαιρετικά εκφραστική γλώσσα προδιαγραφών προτύπων με τυπική και δηλωτική σημασιολογία, καθώς και τεχνικές για τη διαχείριση του θορύβου και της αβεβαιότητας. Αυτή η διατριβή παρακινείται από την απουσία ενός συστήματος που να διαθέτει όλα τα προαναφερθέντα χαρακτηριστικά και στοχεύει στην επέκταση σύγχρονων υπολογιστικών συστημάτων προκειμένου να χειρίζονται αποτελεσματικά εφαρμογές συλλογιστικής σε ροές δεδομένων. Εστιάζουμε σε συστήματα που χρησιμοποιούν τον Λογισμό Γεγονότων, έναν φορμαλισμό βασισμένο στο λογικό προγραμματισμό για την αναπαράσταση γεγονότων και το συμπερασμό των συνεπειών τους με την πάροδο του χρόνου. Ο Λογισμός Γεγονότων παρουσιάζει μια τυπική, δηλωτική σημασιολογία, ενώ υποστηρίζει στιγμιαία και διαρκή γεγονότα, ιεραρχικές και σχεσιακές προδιαγραφές γεγονότων, τη χρονική ανθεκτικότητα των συνεπειών των γεγονότων, καθώς και βοηθητικές βάσεις γνώσης που προδιαγράφουν τον τομέα εφαρμογής. Το RTEC είναι ένα σύστημα που βασίζεται στον Λογισμό Γεγονότων και περιλαμβάνει πολλές τεχνικές βελτιστοποίησης για τη συλλογιστική σε ροές δεδομένων. Προτείνουμε τρεις επεκτάσεις του RTEC, δηλαδή τα συστήματα RTECο, RTEC-> και RTECA, τα οποία υποστηρίζουν, αντιστοίχως, χρονικές προδιαγραφές με κυκλικές εξαρτήσεις, γεγονότα με μελλοντικές συνέπειες και καταστάσεις που ορίζονται μέσω των σχέσεων της άλγεβρας διαστημάτων του Allen. Επιπλέον, μελετάμε το PIEC, δηλαδή ένα σύστημα βασισμένο στο Λογισμό Γεγονότων για πιθανοτική αναγνώριση γεγονότων, και προτείνουμε το σύστημα oPIEC, δηλαδή μια επέκταση του PIEC για συλλογιστική πάνω σε θορυβώδεις ροές δεδομένων. Για να υποστηρίξουμε μεγάλες ροές δεδομένων, προτείνουμε δύο εκδόσεις του oPIEC με περιορισμένη μνήμη. Όλα τα συστήματα που αναπτύξαμε έχουν τυπική σημασιολογία και διαθέτουν βελτιστοποιημένους αλγόριθμους συλλογιστικής σε ροές δεδομένων που έχουν αξιολογηθεί τόσο θεωρητικά όσο και εμπειρικά, χρησιμοποιώντας μεγάλες, πραγματικές και συνθετικές ροές δεδομένων, σε πειράματα που περιλαμβάνουν συγκρίσεις με σύγχρονα συστήματα. Η ανάλυσή μας φανερώνειπως τα συστήματα RTECο , RTEC-> και RTECA είναι κατάλληλα για συλλογιστική πάνω σε ροές δεδομένων με πολύπλοκες χρονικές προδιαγραφές, ενώ οι εκδόσεις του oPIEC επιτυγχάνουν υψηλή ακρίβεια πρόβλεψης και ταχύτητα συλλογισμού όταν λειτουργούν πάνω σε θορυβώδεις ροές δεδομένων.