Extracting weighted finite automata from Recurrent Neural Networks

Recurrent Neural Networks (RNNs) are increasingly used to model complex sequential processes, but their inherent "black-box" architecture poses significant challenges for their interpretability, security auditing, reliable debugging, and formal verification. To address this, this Master's Thesis presents the design and implementation of a novel algorithmic framework to extract Max-Plus (or tropical) Weighted Finite Automata (WFAs) directly from trained RNNs. By translating the opaque continuous logic of the neural network into a transparent and interpretable directed graph, this approach allows engineers to extract critical system information. This includes exact logical mapping, the identification of parallel redundancies, the computation of worst-case asymptotic costs using the Maximum Mean-Weight Cycle, and the highly efficient resolution of constrained combinatorial searches. WFAs defined over the Max-Plus semiring are mathematically inherently suited to model Discrete Event Systems (DESs) because their operations naturally capture the sequential accumulation of costs (via standard addition) and the synchronization of parallel bottlenecks (via the maximum function). However, extracting a WFA directly from real-world DES event logs is often unfeasible. The stochastic nature of real processes creates a one-to-many mapping between event sequences and execution costs, causing classical extraction algorithms to infinitely split states. To overcome this limitation, RNNs are employed as a crucial intermediate step. By training an RNN on the system's operational data, the network learns the underlying distribution and acts as a deterministic filter, transforming the stochastic real-world process into a one-to-one oracle. Ultimately, this allows the Max-Plus WFA to be safely and accurately extracted using the proposed framework. The proposed framework is validated through diverse experiments, including synthetic DESs scenarios for contextual cost analysis, parallel server bottlenecks, and cybersecurity audits. Furthermore, its practical utility is demonstrated by resolving complex optimization queries using real-world clinical data from the OhioT1DM dataset.

Le Reti Neurali Ricorrenti (RNN - Recurrent Neural Networks) sono sempre più utilizzate per modellare processi sequenziali complessi, ma la loro intrinseca architettura a "scatola nera" presenta sfide significative per la loro interpretabilità, l'auditing di sicurezza, il debugging affidabile e la verifica formale. Per affrontare questo problema, questa Tesi di Laurea Magistrale presenta la progettazione e l'implementazione di un nuovo framework algoritmico per estrarre Automi a Stati Finiti Pesati (WFAs - Weighted Finite Automata) Max-Plus (o tropicali) direttamente da RNN. Traducendo l'opaca logica continua della rete neurale in un grafo orientato trasparente e interpretabile, questo approccio consente agli ingegneri di estrarre informazioni critiche del sistema. Ciò include la mappatura logica esatta, l'identificazione di ridondanze parallele, il calcolo dei costi asintotici nel caso peggiore mediante il Ciclo di Peso Medio Massimo e la risoluzione altamente efficiente di ricerche combinatorie vincolate. I WFA definiti sul semianello Max-Plus sono ideali per modellare i Sistemi a Eventi Discreti (DESs - Discrete Event Systems), poiché le loro operazioni catturano naturalmente l'accumulo sequenziale dei costi (tramite addizione standard) e la sincronizzazione dei colli di bottiglia (tramite funzione di massimo). Tuttavia, l'estrazione diretta dai log degli eventi reali è spesso irrealizzabile: la stocasticità di questi processi crea mappature uno-a-molti, spingendo gli algoritmi classici a dividere gli stati all'infinito. Per superare questa limitazione, le RNN fungono da intermediario cruciale. Addestrandole sui dati operativi, apprendono la distribuzione sottostante e agiscono come filtro deterministico, trasformando il processo stocastico in un oracolo uno-a-uno. Ciò consente infine di estrarre accuratamente il WFA Max-Plus tramite il framework proposto. Il framework proposto viene validato attraverso diversi esperimenti, tra cui scenari DES sintetici per l'analisi dei costi contestuali, colli di bottiglia nei server paralleli e audit di sicurezza informatica. Inoltre, la sua utilità pratica è dimostrata risolvendo complesse query di ottimizzazione utilizzando dati clinici reali provenienti dal dataset OhioT1DM.