Interpretable Sequence Classification via Discrete Optimization

• Early classification is important when sequence-based decisions can enable timely intervention, including neonatal sepsis diagnosis.Source: §1 · p. 1
• Neural networks such as LSTMs are powerful sequence classifiers, but their rationales can be difficult to discern, complicating accountable decision-making.Source: §1 · p. 1
• Discrete optimization learns finite-state automata that favour early classification and capture classification rationales in a compact, extractable form.Source: §1 · p. 1
• Their formal-language structure supports explanation, counterfactual reasoning, property verification, and human modification.Source: §1 · p. 1
• Prior automata-learning approaches focused on minimum-sized models that perfectly fit training data; the paper proposes regularization and an efficient mixed-integer linear program, and presents automata for early classification as novel.Source: §1 · p. 1
• Experiments show the learned classifiers are robust to noisy sequences, suited to early prediction, and comparable in performance to an LSTM while remaining interpretable.Source: §1 · p. 1

• Sequence classification predicts the class label corresponding to a trace of symbols from a finite set.Source: §2 · pp. 1–2
• Figure 1’s DFA classifies whether the agent is pursuing goal K, updating its yes/no decision after each observed location.Source: Figure 1 · p. 2, §2 · p. 2
• In early classification, the aim is a high-confidence prediction from a short trace prefix; the paper proposes DFAs as sequence classifiers.Source: §2 · p. 2
• A DFA is a compact graphical encoding of a language, and formal-language theory motivates interpretability services for these classifiers.Source: §2 · p. 2
• In the office example, the goal is to predict whether an agent starting at A, B, or E will reach one of the other regions, following shortest Manhattan-distance hallway paths.Source: §2 · p. 2
• The example DFA correctly classifies optimal paths and also generalizes to some unseen suboptimal traces; a separate DFA can detect goal E upon observing H3, except when the agent started at E.Source: §2 · p. 2

3.1 Learning one-vs-rest binary classifiers

• Each class gets a separate DFA learned from a prefix tree of labeled traces, with state assignments optimized for low early-prediction error under a state limit.The model uses prefix-node positive and negative counts, whose trace contributions are divided by trace length.Source: §3.1 · p. 3
• Limiting DFA states, rewarding absorbing states, and penalizing transitions between states regularize the classifiers and improve generalization.The two absorbing states—one accepting and one non-accepting—prevent decisions from changing once reached.Source: §3.1 · p. 3

3.2 Posterior inference of the class label

• One-vs-rest DFA decisions are combined into a normalized posterior over labels using conditional-independence assumptions and probabilities estimated on held-out data.The method treats decisions as conditionally independent given the true label, with decision probabilities depending on whether a classifier's label matches it.Source: §3.2 · p. 3, §3.1 · p. 3
• Conditioning inference on observations seen so far or relaxing its second assumption would require more probability estimates and may reduce accuracy in low-data settings.The second assumption is that each classifier's decision probability depends only on whether its label is the true label.Source: §3.2 · p. 4

3.3 Discussion

• Prefix trees reduce the optimization problem enough to handle datasets with nearly 100,000 observation tokens, although the approach scales less well than gradient-based optimization.The formulation can also incorporate domain-knowledge constraints and use off-the-shelf optimizers.Source: §3.3 · p. 4
• The DFA decisions also support early probability-based classification, top-k predictions, and multi-label sequence classification.The paper reports that the probabilities are useful in an early-classification setting.Source: §3.3 · p. 4

4 Classifier Interpretability

• DFA classifiers can be transformed into regular expressions, context-free grammars, or temporal logic representations, with natural language added to aid interpretation.Which representation works best is user- or task-specific and should be evaluated in situ.Source: §4 · p. 4

4.1 Explanation

• For explanations, a selected vocabulary can omit irrelevant trace symbols, while counterfactuals identify edits that yield an accepted trace with minimum Levenshtein distance.The paper illustrates replacing an observed symbol with K to obtain an accepted trace.Source: §4.1 · pp. 4–5

4.2 Classifier Verification and Modification

• Classifier properties can be specified in linear temporal logic and checked against a DFA, with a witness returned when a property is false.For example, the paper discusses checking whether either of two symbols occurs before K.Source: §4.2 · p. 5
• A DFA criterion can be combined with a classifier by taking their product, enforcing the criterion, but post-training modification may reject dataset traces labeled positive.The paper recommends verifying such modifications against the dataset; criteria can also be specified in linear temporal logic.Source: §4.2 · p. 5

5. Experimental Evaluation

• The evaluation compared DISC with LSTM, HMM, unigram and bigram models, and DFA-FT across goal-recognition and behaviour-classification domains.The reported metrics were cumulative convergence accuracy and percentage convergence accuracy, averaged over 30 runs unless otherwise specified.Source: §5 · p. 5, §5.1 · pp. 5–6

5.2 Results

• DISC generally outperformed n-gram, HMM, and DFA-FT, achieving near-LSTM performance on most domains; LSTM had an advantage on datasets with long traces.DFA-FT excelled on malware but performed poorly on noisy datasets such as MIT-AR and Crystal Island due to overfitting.Source: §5.2 · p. 6
• In an early-classification experiment rewarding correct predictions made with fewer observations, DISC showed strong performance on each domain, comparable only to LSTM.The experiment used classifier confidence to choose when to predict.Source: §5.2 · p. 6

5.3 Discussion and Limitations

• DISC makes a Markov assumption like HMM but uses discrete transitions, omits an observation-emission distribution, and regularizes model size; the authors identify these as factors in handling noise.The authors report that DISC’s transition- and absorbing-state-based regularization was crucial to learning robust DFAs that generalized to unseen data; the learned DFAs were qualitatively orders of magnitude smaller than DFA-FT’s.Source: §5.3 · p. 6
• DISC assumes each class’s traces form a regular language, and its limited capacity makes tasks requiring large or unbounded memory or occurrence counting difficult.Choosing the transition penalty also depends on the amount of noise in the data.Source: §5.3 · p. 6

6 Related Work

• Prior automata-learning approaches commonly build prefix trees and use heuristics or SAT solvers to minimize automata; DISC instead uses a MILP with a different objective and new regularization.The authors state that their MILP is guaranteed to find optimal solutions given enough time and does not assume noise-free traces or prior problem knowledge.Source: §6 · p. 6
• Earlier automata-learning approaches could overfit noisy data; cited alternatives either incorporate domain knowledge or assume at most k training instances have wrong labels and do not support regularization.DISC eschews domain knowledge while allowing it to be incorporated during learning.Source: §6 · p. 6
• Prior interpretable early-classification work includes discrete-optimization methods for extracting salient time-series features, while association-rule classifiers do not address early prediction and focus on binary classification.The paper presents DISC as producing structured DFA classifiers that support explanation and modification.Source: §6 · p. 7
• Unlike goal-recognition approaches that typically rely on rich domain knowledge, DISC learns from data and targets early prediction, interpretability services, and generalization in noisy sequence-classification settings.The paper also distinguishes malware process-mining and trace-formula approaches as not addressing early prediction.Source: §6 · p. 7

7 Concluding Remarks

• DISC combines MILP-learned DFA sequence classifiers with Bayesian inference and introduces automata-learning techniques for regularization, efficiency, and early classification.The classifiers support explanation, counterfactual reasoning, property verification, and human modification.Source: §7 · p. 8
• DISC achieves similar performance to LSTMs and superior performance to HMMs and n-grams on synthetic and real-world datasets, while remaining interpretable.Source: §7 · p. 8

Technical Appendix

• The technical appendices add DFA-learning details, counterfactual-generation examples, LTL exposition, and experimental setup, dataset, early-classification, and multi-label results.Source: Technical Appendix · p. 11

A Learning DFAs from Training Data

• For each possible label, DISC trains a separate DFA to recognize traces with that label, then uses the DFAs to compute probabilities for online classification of partial traces.Source: A Learning DFAs from Training Data · p. 11

A.1 From Training Data to Prefix Trees

• A prefix tree represents training-trace prefixes, with each node labeled by the costs of positive and negative predictions based on trace length and label.The construction processes each training trace by adding its symbols to the tree and updating node costs.Source: §A.1 · p. 11, §A.2 · p. 12

A.2 From Prefix Trees to DFAs

• The MILP assigns DFA states to prefix-tree nodes while enforcing deterministic, feasible transitions and minimizing prediction error, transitions between different states, and non-terminal-state occupancy.The model allows at most qmax states and uses λe and λt for regularization, with λ+ and λ− weighting errors for positive and negative examples.Source: §A.2 · pp. 11–12

A.3 Derivation of the Posterior Probability Distribution over the Set of Class Labels

• The posterior derivation assumes class-specific DFA decisions are conditionally independent given the true label, and their likelihood depends only on whether the candidate label is correct.The appendix states that the posterior for each candidate label is computed under these assumptions.Source: §A.3 · p. 13

B.1 Natural Language Generation for Counterfactual Explanation

• The counterfactual-language procedure maps replace, insert, and delete edits into an English sentence describing how the classifier would have accepted the trace.For example, replacing the final ♂ observation with K yields a sentence describing acceptance had K been observed instead.Source: §B.1 · p. 13

Malware

• In the BatteryLow malware example, a trace is rejected because it reaches non-accepting q5 rather than accepting q6, and removing read is offered as a counterfactual for acceptance.The illustrated DFA is limited to 10 states.Source: Malware · p. 14, Figure 4 · p. 14
• For BootCompleted, the five-state DFA rejects the example trace, and its counterfactual says acceptance would follow if getuid32 replaced writev; the five-state model is not used in experiments.The appendix notes that the 10-state malware DFA setting performed better than the 5-state setting in experiments.Source: Malware · pp. 14–15, Figure 5 · p. 15

Crystal Island

• The five-state Crystal Island DFA rejects the example trace; acceptance requires talk ford or move sittingarea, expressed by the entailed LTL property ♦(talk ford ∨move sittingarea).The counterfactual proposes observing move sittingarea after move hall.Source: Crystal Island · p. 15, Figure 6 · p. 16

StarCraft

• The StarCraft DFA rejects the example trace, while its extracted properties require move produce or harvest produce and guarantee acceptance for traces beginning with harvest produce.The counterfactual proposes harvest move instead of attack move move.Source: StarCraft · p. 15, Figure 7 · p. 16

B.3 Linear Temporal Logic

• LTL provides temporal operators for expressing properties, and satisfying LTL formulas can explain DFA behavior; finite-trace LTL formulas are within DFA expressive capacity.For infinite traces, DFAs capture only a subset of LTL formulas.Source: §B.3 · pp. 15, 17

C.1 Experimental Setup

• DISC learns DFAs with Gurobi under a 15-minute per-DFA limit, using qmax of 5 for Crystal Island and MIT-AR and 10 for other domains.Its regularizers penalize transitions between different states and nodes not assigned to absorbing states; λa is fixed at 0.001, while λt is selected by validation except on MIT-AR.Source: §C.1 · p. 17
• DFA-FT uses the full observation tree, assigns unique states to mixed-suffix nodes, and runs one DFA per label in parallel for multiclass prediction.Source: §C.1 · p. 17
• The LSTM uses two recurrent layers and trains with equal weight on every trace prefix to encourage early prediction; architecture and training settings are selected using validation accuracy.MIT-AR hyperparameters are hand-tuned.Source: §C.1 · p. 17
• HMMs are trained separately by class and selected by likelihood, with validation tuning of hidden-state count and smoothing except for hand-tuned MIT-AR settings; n-grams use α = 0.5 smoothing without validation.Source: §C.1 · pp. 17–18

C.2 Datasets

• The StarCraft, Crystal Island, malware, ALFRED, and MIT-AR datasets were obtained from prior authors or public sources.The passage identifies the StarCraft and Crystal Island authors and states that the other listed datasets are publicly available.Source: §C.2 · p. 18

Malware

• The evaluation includes two malware datasets, each built from traces of malware actions responding to an Android system event and labeled by malware family.The datasets are BootCompleted and BatteryLow.Source: Malware · p. 18

StarCraft

• StarCraft traces come from scripted agents competing in MicroRTS; each player’s action sequence is labeled with the agent type that generated it.The agents competed in a five-iteration round-robin tournament across maps.Source: StarCraft · p. 18

Crystal Island

• Crystal Island traces contain student game actions labeled with narrative sub-goals, and interleaved exploration and problem solving make the observations noisy.Each observation token combines one of 19 action types with one of 39 locations.Source: Crystal Island · p. 18

ALFRED

• ALFRED examples are planner-generated household-task action sequences labeled with one of seven task types.The expert demonstrations use task-specific PDDL goal conditions.Source: ALFRED · pp. 18–19

MIT Activity Recognition (MIT-AR)

• MIT-AR contains noisy sensor-event sequences from everyday activities, manually labeled with 14 high-level activity classes.Sensors recorded opening and closing events from objects during a two-week collection period.Source: MIT Activity Recognition (MIT-AR) · p. 19

• DISC-learned DFAs were generally an order of magnitude smaller than DFA-FT-learned DFAs.The comparison uses average state and transition counts.Source: §C.3 · p. 19
• The domain results report cumulative convergence accuracy through the maximum trace length and prefix classification accuracy at five observation fractions.The reported prefix fractions are 20%, 40%, 60%, 80%, and 100%; error bars give 90% confidence intervals over 30 runs.Source: §C.3 · p. 19
• Table 2 reports average state and transition counts for learned DFAs from DISC and DFA-FT; DISC-learned DFAs were generally an order of magnitude smaller.Source: §C.3 · p. 19

C.4 Early Classification

• The evaluation considers both early-classification accuracy and confidence accuracy, avoiding dependence on a chosen stopping rule.Early prediction trades off accuracy against earliness, and differing decision times complicate objective model comparison.Source: §C.4 · p. 19
• For a non-increasing correct-prediction utility U(t), the optimal decision time maximizes U(t)p(t), while the classifier uses estimated confidence conf(t) ≈ p(t).This setting requires both accurate predictions and accurate confidence estimates.Source: §C.4 · p. 19
• The experiment uses U(t) = max{1 − t/40, 0}, assumes predictions at time t use only the first t observations, and lets decision selection access confidence estimates for all times.Only DISC, LSTM, and n-gram baselines are included because they produce label-probability distributions.Source: §C.4 · p. 19
• DISC performs strongly in each tested early-classification domain, with only LSTM comparable.The authors take this as evidence that DISC confidence approximates its true predictive accuracy.Source: §C.4 · p. 19

C.5 Multi-label Classification

• The multi-label setting generalizes single-goal recognition to traces whose actions interleave pursuit of multiple goals.The evaluation uses a synthetic kitchen dataset with seven goals and 25 unique observations.Source: §C.5 · p. 23
• DISC uses independent one-vs-rest DFA outputs for multi-label prediction and achieves performance similar to LSTM on the kitchen task.The reported mean accuracy is averaged over goals and 30 runs; Figure 11 presents CCA with 90% confidence intervals.Source: §C.5 · p. 23, Figure 11 · p. 24