skip to main content
10.1145/2883817.2883843acmconferencesArticle/Chapter ViewAbstractPublication PagescpsweekConference Proceedingsconference-collections
research-article
Public Access

A Decision Tree Approach to Data Classification using Signal Temporal Logic

Published: 11 April 2016 Publication History

Abstract

This paper introduces a framework for inference of timed temporal logic properties from data. The dataset is given as a finite set of pairs of finite-time system traces and labels, where the labels indicate whether the traces exhibit some desired behavior (e.g., a ship traveling along a safe route). We propose a decision-tree based approach for learning signal temporal logic classifiers. The method produces binary decision trees that represent the inferred formulae. Each node of the tree contains a test associated with the satisfaction of a simple formula, optimally tuned from a predefined finite set of primitives. Optimality is assessed using heuristic impurity measures, which capture how well the current primitive splits the data with respect to the traces' labels. We propose extensions of the usual impurity measures from machine learning literature to handle classification of system traces by leveraging upon the robustness degree concept. The proposed incremental construction procedure greatly improves the execution time and the accuracy compared to existing algorithms. We present two case studies that illustrate the usefulness and the computational advantages of the algorithms. The first is an anomaly detection problem in a maritime environment. The second is a fault detection problem in an automotive powertrain system.

References

[1]
E. Asarin, A. Donzé, O. Maler, and D. Nickovic. Parametric identification of temporal properties. In Runtime Verification, pages 147--160. Springer, 2012.
[2]
E. Bartocci, L. Bortolussi, L. Nenzi, and G. Sanguinetti. System design of stochastic models using robustness of temporal properties. Theoretical Computer Science, 587:3--25, July 2015.
[3]
E. Bartocci, L. Bortolussi, and G. Sanguinetti. Data-driven statistical learning of temporal logic properties. In Formal Modeling and Analysis of Timed Systems, pages 23--37. Springer, 2014.
[4]
L. Breiman, J. Friedman, C. J. Stone, and R. A. Olshen. Classification and regression trees. CRC press, 1984.
[5]
S. Bufo, E. Bartocci, G. Sanguinetti, M. Borelli, U. Lucangelo, and L. Bortolussi. Temporal Logic Based Monitoring of Assisted Ventilation in Intensive Care Patients. In Leveraging Applications of Formal Methods, Verification and Validation, number 8803 in Lecture Notes in Computer Science, pages 391--403. Springer, Oct. 2014.
[6]
V. Chandola, A. Banerjee, and V. Kumar. Anomaly Detection: A Survey. ACM Comput Surv, 41(3):15:1--15:58, July 2009.
[7]
T. H. Cormen. Introduction to Algorithms. MIT Press, third edition, July 2009.
[8]
A. Donzé, T. Ferrere, and O. Maler. Efficient robust monitoring for STL. In Computer Aided Verification, pages 264--279. Springer, 2013.
[9]
A. Donzé and O. Maler. Robust Satisfaction of Temporal Logic over Real-Valued Signals. In K. Chatterjee and T. A. Henzinger, editors, Formal Modeling and Analysis of Timed Systems, number 6246 in Lecture Notes in Computer Science, pages 92--106. Springer Berlin Heidelberg, 2010.
[10]
G. E. Fainekos and G. J. Pappas. Robustness of temporal logic specifications for continuous-time signals. Theor. Comput. Sci., 410(42):4262--4291, Sept. 2009.
[11]
E. A. Gol, E. Bartocci, and C. Belta. A formal methods approach to pattern synthesis in reaction diffusion systems. In Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on, pages 108--113. IEEE, 2014.
[12]
R. Grosu, S. A. Smolka, F. Corradini, A. Wasilewska, E. Entcheva, and E. Bartocci. Learning and detecting emergent behavior in networks of cardiac myocytes. Commun. ACM, 52(3):97--105, 2009.
[13]
B. Hoxha, H. Abbas, and G. Fainekos. Benchmarks for temporal logic requirements for automotive systems. Proc Appl. Verification Contin. Hybrid Syst., 2014.
[14]
L. Hyafil and R. L. Rivest. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5(1):15--17, May 1976.
[15]
L. Ingber. Adaptive simulated annealing (ASA): Lessons learned. Control Cybern., 25:33--54, 1996.
[16]
R. Isermann. Fault-diagnosis systems. Springer, 2006.
[17]
X. Jin, A. Donzé, J. Deshmukh, and S. A. Seshia. Mining Requirements from Closed-Loop Control Models. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., PP(99):1--1, 2015.
[18]
A. Jones, Z. Kong, and C. Belta. Anomaly detection in cyber-physical systems: A formal methods approach. In Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on, pages 848--853. IEEE, 2014.
[19]
Z. Kong, A. Jones, and C. Belta. Temporal Logics for Learning and Detection of Anomalous Behaviors. IEEE Trans. Autom. Control, 2016. inpress.
[20]
Z. Kong, A. Jones, A. Medina Ayala, E. Aydin Gol, and C. Belta. Temporal Logic Inference for Classification and Prediction from Data. In Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control, HSCC '14, pages 273--282, New York, NY, USA, 2014. ACM.
[21]
K. Kowalska and L. Peel. Maritime anomaly detection using Gaussian Process active learning. In 2012 15th International Conference on Information Fusion (FUSION), pages 1164--1171, July 2012.
[22]
O. Maler and D. Nickovic. Monitoring Temporal Properties of Continuous Signals. In Y. Lakhnech and S. Yovine, editors, Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems, number 3253 in Lecture Notes in Computer Science, pages 152--166. Springer Berlin Heidelberg, 2004.
[23]
J. R. Quinlan. C4.5: Programs for Machine Learning. Elsevier, June 2014.
[24]
B. D. Ripley. Pattern recognition and neural networks. Cambridge university press, 1996.
[25]
R. Storn and K. Price. Differential Evolutiontextendash A Simple and Efficient Heuristic for global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4):341--359, Dec. 1997.
[26]
H. Yang, B. Hoxha, and G. Fainekos. Querying Parametric Temporal Logic Properties on Embedded Systems. In Testing Software and Systems, number 7641 in Lecture Notes in Computer Science, pages 136--151. Springer, 2012.
[27]
P. Zuliani, A. Platzer, and E. M. Clarke. Bayesian statistical model checking with application to Stateflow/Simulink verification. Form Methods Syst Des, 43(2):338--367, Aug. 2013.

Cited By

View all
  • (2025)STL and wSTL control synthesis: A disjunction-centric mixed-integer linear programming approachNonlinear Analysis: Hybrid Systems10.1016/j.nahs.2025.10157656(101576)Online publication date: May-2025
  • (2024)An investigation on using artificial intelligence models to predict crater wear of tungsten carbide toolTribology - Materials, Surfaces & Interfaces10.1177/1751583124124194718:2(104-114)Online publication date: 28-Mar-2024
  • (2024)Classification of Production Process Phases with Multivariate Time Series Techniques2024 22nd International Conference on Research and Education in Mechatronics (REM)10.1109/REM63063.2024.10735481(210-217)Online publication date: 24-Sep-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
HSCC '16: Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control
April 2016
324 pages
ISBN:9781450339551
DOI:10.1145/2883817
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 April 2016

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. anomaly detection
  2. decision trees
  3. impurity measure
  4. logic inference
  5. machine learning
  6. signal temporal logic
  7. supervised learning

Qualifiers

  • Research-article

Funding Sources

Conference

HSCC'16
Sponsor:

Acceptance Rates

HSCC '16 Paper Acceptance Rate 28 of 65 submissions, 43%;
Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)274
  • Downloads (Last 6 weeks)26
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2025)STL and wSTL control synthesis: A disjunction-centric mixed-integer linear programming approachNonlinear Analysis: Hybrid Systems10.1016/j.nahs.2025.10157656(101576)Online publication date: May-2025
  • (2024)An investigation on using artificial intelligence models to predict crater wear of tungsten carbide toolTribology - Materials, Surfaces & Interfaces10.1177/1751583124124194718:2(104-114)Online publication date: 28-Mar-2024
  • (2024)Classification of Production Process Phases with Multivariate Time Series Techniques2024 22nd International Conference on Research and Education in Mechatronics (REM)10.1109/REM63063.2024.10735481(210-217)Online publication date: 24-Sep-2024
  • (2024)Concurrent Learning of Control Policy and Unknown Safety Specifications in Reinforcement LearningIEEE Open Journal of Control Systems10.1109/OJCSYS.2024.34183063(266-281)Online publication date: 2024
  • (2024)Mining signal temporal logic specifications for hybrid systems2024 Forum on Specification & Design Languages (FDL)10.1109/FDL63219.2024.10673843(1-8)Online publication date: 4-Sep-2024
  • (2024)Neural-symbolic temporal decision trees for multivariate time series classificationInformation and Computation10.1016/j.ic.2024.105209(105209)Online publication date: Aug-2024
  • (2024)A Robot Ground Medium Classification Algorithm Based on Feature Fusion and Adaptive Spatio-Temporal Cascade NetworksNeural Processing Letters10.1007/s11063-024-11679-w56:5Online publication date: 17-Sep-2024
  • (2024)What Is Formal Verification Without Specifications? A Survey on Mining LTL SpecificationsPrinciples of Verification: Cycling the Probabilistic Landscape10.1007/978-3-031-75778-5_6(109-125)Online publication date: 18-Nov-2024
  • (2024)ECATS: Explainable-by-Design Concept-Based Anomaly Detection for Time SeriesNeural-Symbolic Learning and Reasoning10.1007/978-3-031-71170-1_16(175-191)Online publication date: 9-Sep-2024
  • (2024)Learning Branching-Time Properties in CTL and ATL via Constraint SolvingFormal Methods10.1007/978-3-031-71162-6_16(304-323)Online publication date: 9-Sep-2024
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media