# Learning Optimal Signal Temporal Logic Decision Trees for Classification: A Max-Flow MILP Formulation

arXiv: https://arxiv.org/abs/2407.21090 · HTML: https://mlsanity.com/paper/2407.21090/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 26 references that are in the map.
- First posted on arXiv 30 Jul 2024.

## Builds on (most cited first, 8 of 8)

- [Explaining Explanations: An Overview of Interpretability of Machine Learning](https://mlsanity.com/paper/1806.00069/) (2018)
- [The UCR Time Series Archive](https://mlsanity.com/paper/1810.07758/) (2018)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Interpretable Classification of Time-Series Data using Efficient Enumerative Techniques](https://mlsanity.com/paper/1907.10265/) (2019)
- [Mining Parametric Temporal Logic Properties in Model Based Design for Cyber-Physical Systems](https://mlsanity.com/paper/1512.07956/) (2015)
- [Learning Signal Temporal Logic through Neural Network for Interpretable Classification](https://mlsanity.com/paper/2210.01910/) (2022)
- [Classification of Time-Series Data Using Boosted Decision Trees](https://mlsanity.com/paper/2110.00581/) (2021)
- [Multi-class Temporal Logic Neural Networks](https://mlsanity.com/paper/2402.12397/) (2024)

## Abstract (arXiv)

This paper presents a novel framework for inferring timed temporal logic properties from data. The dataset comprises pairs of finite-time system traces and corresponding labels, denoting whether the traces demonstrate specific desired behaviors, e.g. whether the ship follows a safe route or not. Our proposed approach leverages decision-tree-based methods to infer Signal Temporal Logic classifiers using primitive formulae. We formulate the inference process as a mixed integer linear programming optimization problem, recursively generating constraints to determine both data classification and tree structure. Applying a max-flow algorithm on the resultant tree transforms the problem into a global optimization challenge, leading to improved classification rates compared to prior methodologies. Moreover, we introduce a technique to reduce the number of constraints by exploiting the symmetry inherent in STL primitives, which enhances the algorithm's time performance and interpretability. To assess our algorithm's effectiveness and classification performance, we conduct three case studies involving two-class, multi-class, and complex formula classification scenarios.