Apprendimento di automi - Riassunto

Fonte: raw/Learning Automata.md

Punti chiave

• Nell'apprendimento di automi un Learner cerca di ricostruire un linguaggio regolare noto a un Teacher.
• Le query principali sono:
• Membership Query (MQ): chiede se una parola appartiene al linguaggio;
• Equivalence Query (EQ): propone un automa e chiede se riconosce esattamente il linguaggio target.
• L'equivalenza di Myhill-Nerode e' alla base dell'identificazione degli stati del DFA minimo.
• L'algoritmo L* di Angluin organizza le informazioni in una tabella di osservazione, collegata alle matrici di Hankel.
• Quando la tabella e' completa e minimale, il Learner costruisce un'ipotesi e la sottopone al Teacher.

Concetti collegati

• Apprendimento di automi
• Algoritmo L* di Angluin
• Matrici di Hankel

Apprendimento di automi

L'apprendimento di automi consiste nell'inferire un automa che riconosce un linguaggio target. Nel modello attivo, un Learner puo interrogare un Teacher che conosce il linguaggio.

Modello MAT

Nel modello del Minimally Adequate Teacher, il Learner puo usare: - membership query: chiede se una parola e' nel linguaggio; - equivalence query: propone un automa e riceve conferma o un controesempio.

Le membership query da sole non bastano a garantire l'identificazione del linguaggio, perche' dopo un numero finito di esempi restano molti linguaggi compatibili. Le equivalence query da sole basterebbero enumerando automi, ma con costo brute-force. La forza di L* sta nel combinare le due: le MQ raffinano localmente la tabella, le EQ danno un controllo globale e un controesempio utile.

Connessione con Myhill-Nerode

Le righe della tabella di osservazione raggruppano parole che non sono distinguibili dai suffissi testati. Quando la tabella e' abbastanza raffinata, questi gruppi diventano gli stati del DFA minimo.

Rilevanza

L'apprendimento di automi e' utile in V&V quando il sistema e' trattato come black box e si vuole costruire un modello finito su cui verificare proprieta.

Nel mondo reale il MAT e' idealizzato: una EQ viene spesso approssimata con testing, fuzzing o conformance testing. Se si trova un controesempio, lo si usa per raffinare il modello; se non lo si trova, l'ipotesi resta una buona approssimazione, non una prova assoluta.

Fonti

• Apprendimento di automi - Riassunto

Algoritmo L* di Angluin

L'algoritmo L* e' un algoritmo classico per l'apprendimento attivo di linguaggi regolari. Il Learner interagisce con un Teacher che conosce il linguaggio target.

Query

• Membership query: il Learner chiede se una parola $w$ appartiene al linguaggio.
• Equivalence query: il Learner propone un DFA; il Teacher risponde si oppure fornisce un controesempio.

Meccanismo

Il Learner mantiene una tabella di osservazione basata su prefissi e suffissi. Le righe rappresentano comportamenti rispetto ai suffissi di test e tendono a corrispondere alle classi di Myhill-Nerode.

La tabella deve diventare: - chiusa / T-completa: ogni transizione da uno stato rappresentato resta rappresentabile nella tabella; - consistente / T-minimale: righe uguali non possono divergere dopo l'aggiunta dello stesso simbolo.

Quando queste condizioni valgono, si costruisce un DFA ipotesi. Se l'equivalence query fallisce, il controesempio viene usato per raffinare la tabella.

Collegamenti

• Apprendimento di automi
• Matrici di Hankel
• Teorema di Myhill-Nerode

Matrici di Hankel

La matrice di Hankel di un linguaggio ha righe indicizzate da prefissi e colonne indicizzate da suffissi. L'elemento $(u,v)$ indica se $uv$ appartiene al linguaggio.

Ruolo nell'apprendimento

Righe uguali rappresentano prefissi indistinguibili rispetto ai suffissi osservati. Questo collega le matrici di Hankel alle classi di Myhill-Nerode e agli stati del DFA minimo.

L'algoritmo L* manipola solo una finestra finita della matrice: righe $S$, righe di frontiera $S \cdot \Sigma$ e colonne $T$. Aggiungere suffissi a $T$ significa aggiungere colonne e rendere piu' fine il test; aggiungere prefissi a $S$ significa introdurre nuovi rappresentanti di stati.

La chiusura della tabella richiede che ogni riga di frontiera sia gia' rappresentata in $S$; la consistenza richiede che righe uguali restino uguali dopo l'estensione con lo stesso simbolo.

Collegamenti

• Apprendimento di automi
• Algoritmo L* di Angluin
• Teorema di Myhill-Nerode

Transduttori sequenziali

Un transduttore sequenziale e' un automa finito che produce una parola di output mentre legge una parola di input.

Definizione intuitiva

A ogni transizione non e' associato solo uno stato successivo, ma anche una porzione di output.

Uso

I transduttori modellano funzioni su parole e sono vicini agli automi di Mealy usati nella sintesi di controllori.

Collegamenti

• Automi di Mealy
• Apprendimento di automi

Approfondimento completo settimana 2 - Apprendimento di automi, MAT, L* e Hankel

Questa e' la versione estesa e autocontenuta del capitolo 3. E' pensata come punto di partenza per la domanda a scelta dell'orale: prima costruisce l'intuizione, poi formalizza MAT, Myhill-Nerode relativizzato, L*, Hankel e transduttori. Ogni definizione importante viene riletta in parole.

Di cosa parla davvero questo capitolo

Il capitolo 3 risponde a una domanda molto concreta:

se una macchina si comporta come un automa finito, ma non vedo i suoi stati interni, posso ricostruire un modello finito del suo comportamento facendo esperimenti?

Questa e' l'idea dell'automata learning. Non stiamo addestrando una rete neurale con tanti esempi etichettati. Stiamo cercando di identificare una struttura discreta:

• stati;
• transizioni;
• stati finali;
• comportamento su tutte le parole.

Il capitolo ruota attorno all'algoritmo L* di Angluin, che impara un linguaggio regolare interagendo con un teacher tramite due tipi di domande:

• membership query;
• equivalence query.

La mappa del capitolo e':

1. Parte I: perche' apprendere automi e' diverso da classificare esempi.
2. Parte II: il modello MAT e le due query.
3. Parte III: Myhill-Nerode come fondamento dell'apprendimento.
4. Parte IV: equivalenza relativizzata, insiemi $S$ e $T$.
5. Parte V: observation table e matrice di Hankel.
6. Parte VI: algoritmo L* riga per riga.
7. Parte VII: esempio completo sul linguaggio $(ab)^\ast$.
8. Parte VIII: perche' l'algoritmo termina e perche' e' efficiente.
9. Parte IX: black-box learning e uso in V&V/security.
10. Parte X: transduttori sequenziali e generalizzazioni.
11. Parte XI: errori tipici, esercizi e mappa orale.

0. Richiami minimi

DFA. Un automa finito deterministico e':

$$\mathcal{A}=(Q,\Sigma,\delta,q_0,F).$$

Riconosce un linguaggio regolare $L(\mathcal{A})\subseteq\Sigma^\ast$.

Linguaggio target. Nel learning supponiamo che esista un linguaggio segreto:

$$L_0\subseteq\Sigma^\ast.$$

Il teacher lo conosce. Il learner conosce inizialmente solo l'alfabeto $\Sigma$.

Funzione caratteristica. Un linguaggio e' una funzione:

$$\chi_{L_0}:\Sigma^\ast\to\{0,1\}$$

dove $\chi_{L_0}(w)=1$ se $w\in L_0$ e 0 altrimenti.

Obiettivo. Il learner deve costruire un DFA $\mathcal{A}$ tale che:

$$L(\mathcal{A})=L_0.$$

Non serve trovare lo stesso automa fisico del teacher. Serve trovare un automa equivalente, cioe' che riconosce lo stesso linguaggio.

Parte I - Perche imparare automi

1. Learning di funzioni semplici

Negli appunti viene fatto un confronto utile.

Una rete neurale puo' imparare funzioni molto complesse, ad esempio:

$$f:\mathbb{R}^k\to\{0,1\}$$

che decide se un'immagine rappresenta un cane.

Un automa finito, invece, riconosce funzioni piu' strutturate:

$$f:\Sigma^\ast\to\{0,1\}.$$

L'input non e' un vettore reale, ma una parola. L'output dice se la parola appartiene a un linguaggio.

Questa differenza cambia tutto:

2. Struttura fissata contro struttura appresa

In molti modelli neurali scegliamo prima l'architettura:

• quanti layer;
• quanti nodi;
• quali connessioni.

Poi impariamo i pesi.

Nel learning di automi, invece, vogliamo scoprire anche la struttura:

• quanti stati servono;
• quali transizioni ci sono;
• quali stati sono finali.

Questo e' il motivo per cui Myhill-Nerode diventa centrale: il numero minimo di stati non e' arbitrario. E' il numero di classi della relazione di Myhill-Nerode.

3. Apprendimento passivo e apprendimento attivo

Apprendimento passivo. Il learner riceve esempi, cioe' parole gia' etichettate come positive o negative.

Apprendimento attivo. Il learner sceglie quali parole chiedere. Fa esperimenti.

Moore, nel lavoro sui "Gedanken-experiments on sequential machines", poneva proprio questa idea: interagisco con una macchina sconosciuta, osservo le risposte, e costruisco un modello astratto del suo comportamento.

L* e' attivo:

• il learner non aspetta esempi casuali;
• costruisce parole mirate;
• usa le risposte per raffinare il modello.

4. Breve storia da usare all'orale

Una mini-storia utile:

1. Moore 1956: esperimenti su macchine sequenziali; l'idea di interrogare una macchina come black box.
2. Gold 1967: learning in the limit, soprattutto passivo.
3. Angluin 1987: learning regolare efficiente con query, algoritmo L*.
4. Pitt e altri, anni '90: collegamenti con PAC learning e difficolta' computazionale.
5. Maler e altri 1995: estensione verso linguaggi omega-regolari.

Non devi ricordare date come elenco sterile. Servono a dire:

il problema nasce come identificazione di macchine finite tramite esperimenti, e Angluin fornisce il primo algoritmo efficiente nel modello con query.

Parte II - MAT: Minimally Adequate Teacher

5. Il gioco fra learner e teacher

Nel modello MAT:

• il teacher conosce un linguaggio regolare segreto $L_0$;
• il learner conosce solo l'alfabeto $\Sigma$;
• il learner puo' fare domande;
• il teacher risponde sempre correttamente;
• alla fine il learner deve proporre un DFA equivalente al target.

La parola "adequate" significa che il teacher e' perfetto:

• sa rispondere a ogni membership query;
• sa decidere se un DFA ipotesi e' equivalente al target;
• se non e' equivalente, sa dare un controesempio.

Questo e' idealizzato. Nelle applicazioni black-box reali si approssima.

6. Membership query

Una membership query ha forma:

$$w\in L_0?$$

Il learner sceglie una parola $w\in\Sigma^\ast$ e chiede se appartiene al linguaggio target.

Il teacher risponde:

• si', se $w\in L_0$;
• no, se $w\notin L_0$.

In pratica, la membership query riempie una singola cella della tabella:

$$Membership(w)=\chi_{L_0}(w).$$

7. Equivalence query

Una equivalence query ha forma:

$$L(\mathcal{A})=L_0?$$

Il learner propone un DFA $\mathcal{A}$. Il teacher risponde:

• si', se il linguaggio dell'automa e' corretto;
• no, altrimenti, e fornisce un controesempio.

Il controesempio e' una parola:

$$w\in (L_0-L(\mathcal{A}))\cup(L(\mathcal{A})-L_0).$$

Quindi $w$ e' nella differenza simmetrica: una parola su cui learner e teacher non sono d'accordo.

8. Perche non bastano solo membership query

Con sole membership query, in un numero finito di passi hai visto solo un numero finito di parole.

Ma i linguaggi possibili sono infiniti. Esistono sempre molti linguaggi regolari che concordano su tutti gli esempi visti e divergono su una parola non ancora testata.

Quindi non puoi sapere di aver finito.

L'equivalence query serve come controllo globale:

questa ipotesi e' davvero corretta su tutte le parole?

9. Perche solo equivalence query sono troppo lente

In teoria, con sole equivalence query potresti enumerare tutti i DFA possibili:

1. proponi il primo DFA;
2. se e' sbagliato, proponi il secondo;
3. prima o poi arrivi a un DFA corretto.

Ma questa e' ricerca brute force. Il numero di automi cresce enormemente con il numero di stati.

Il punto di L* e':

membership query e equivalence query insieme permettono una strategia efficiente.

10. Teorema informale di Angluin

Nel modello MAT, se il linguaggio target e' riconosciuto da un DFA minimo con $n$ stati, il learner ha una strategia che identifica il linguaggio in un numero di passi polinomiale in:

• $n$;
• la dimensione dell'alfabeto;
• la lunghezza dei controesempi forniti.

Questa strategia e' l'algoritmo L*.

Parte III - Myhill-Nerode come motore del learning

11. La relazione giusta non e' "stanno entrambi nel linguaggio"

Una relazione troppo grossolana sarebbe:

$$u =_{L_0} v \quad\Longleftrightarrow\quad (u\in L_0 \Leftrightarrow v\in L_0).$$

Questa relazione distingue solo parole accettate e parole rifiutate.

Non basta per costruire un DFA minimo, perche' due parole entrambe accettate possono avere futuri diversi.

Serve sapere cosa succede dopo ogni suffisso.

12. Equivalenza di Myhill-Nerode

La relazione di Myhill-Nerode e':

$$ u\sim_{L_0} v \quad\Longleftrightarrow\quad \forall t\in\Sigma^\ast,\ ut\in L_0 \Leftrightarrow vt\in L_0. $$

Lettura:

due prefissi sono equivalenti se nessun suffisso futuro riesce a distinguerli.

Quindi $u$ e $v$ sono nello stesso stato del DFA minimo se hanno lo stesso comportamento rispetto a tutti i possibili futuri.

13. Perche raffina l'appartenenza al linguaggio

Se:

$$u\sim_{L_0} v,$$

allora prendendo $t=\varepsilon$ otteniamo:

$$u\in L_0 \Leftrightarrow v\in L_0.$$

Quindi ogni classe di Myhill-Nerode e' uniformemente accettante o rifiutante: non puo' contenere sia parole dentro il linguaggio sia parole fuori.

In parole:

se due parole sono indistinguibili da tutti i futuri, allora sono indistinguibili anche guardando il presente.

14. Invarianza a destra

La relazione di Myhill-Nerode e' invariante a destra:

$$u\sim_{L_0} v \Rightarrow ua\sim_{L_0} va.$$

Lettura:

se due prefissi rappresentano lo stesso stato, leggere la stessa lettera da entrambi porta ancora a prefissi equivalenti.

Questa proprieta' e' esattamente cio' che permette di definire transizioni deterministiche fra classi.

15. Indice finito e DFA minimo

Il teorema di Myhill-Nerode dice:

$L_0$ e' regolare se e solo se $\sim_{L_0}$ ha indice finito.

L'indice e' il numero di classi di equivalenza. Nel DFA minimo:

• ogni stato corrisponde a una classe di Myhill-Nerode;
• lo stato iniziale e' $[\varepsilon]$;
• la transizione su $a$ manda $[u]$ in $[ua]$;
• gli stati finali sono le classi contenute in $L_0$.

L* puo' essere letto cosi':

il learner cerca di scoprire le classi di Myhill-Nerode usando solo un numero finito di test.

Parte IV - Relativizzare Myhill-Nerode: il ruolo di T

16. Perche serve una versione finita

La definizione vera usa tutti i suffissi:

$$t\in\Sigma^\ast.$$

Ma $\Sigma^\ast$ e' infinito. Il learner non puo' testare tutti i suffissi.

Allora mantiene un insieme finito:

$$T\subseteq\Sigma^\ast.$$

Gli elementi di $T$ sono suffissi di test.

17. Equivalenza relativizzata

Definiamo:

$$ u\sim_{L_0,T} v \quad\Longleftrightarrow\quad \forall t\in T,\ ut\in L_0 \Leftrightarrow vt\in L_0. $$

Lettura:

$u$ e $v$ sembrano uguali rispetto ai test che ho raccolto finora.

Questa relazione e' una approssimazione di Myhill-Nerode:

• se $T$ e' piccolo, l'equivalenza e' grossolana;
• se aggiungo suffissi a $T$, l'equivalenza diventa piu' fine;
• nel limite, con suffissi sufficienti, separa le classi giuste.

18. Esempi di T

Se:

$$T=\emptyset,$$

allora ogni coppia di parole e' equivalente, perche' la condizione universale e' vacuamente vera. E' l'equivalenza piu' grossolana possibile.

Se:

$$T=\{\varepsilon\},$$

allora:

$$u\sim_{L_0,T}v \quad\Longleftrightarrow\quad u\in L_0 \Leftrightarrow v\in L_0.$$

Quindi distingui solo accettazione/rifiuto immediati.

Se aggiungi piu' suffissi, inizi a distinguere parole che ora sembrano uguali ma reagiscono diversamente a qualche futuro.

19. Gli insiemi S e T

L* mantiene due insiemi finiti:

• $S\subseteq\Sigma^\ast$: rappresentanti candidati degli stati;
• $T\subseteq\Sigma^\ast$: suffissi usati per testare le differenze.

Intuizione:

• $S$ contiene "pebbles", cioe' parole che rappresentano stati;
• $T$ contiene esperimenti per capire se due pebbles sono davvero diversi.

Ogni elemento di $S$ dovrebbe rappresentare una classe distinta di $\sim_{L_0,T}$.

20. T-minimalita'

$S$ e' T-minimale se due elementi distinti di $S$ non hanno la stessa riga:

$$ \forall s\neq s'\in S,\quad s\not\sim_{L_0,T}s'. $$

Lettura:

non ho due rappresentanti per la stessa classe osservata.

T-minimalita' evita stati duplicati nell'ipotesi.

21. T-completezza

$S$ e' T-completo se per ogni rappresentante e per ogni lettera, il prefisso esteso e' gia' rappresentato da qualche elemento di $S$:

$$ \forall s\in S,\ \forall a\in\Sigma,\ \exists s'\in S \text{ tale che } s'\sim_{L_0,T}sa. $$

Lettura:

se da uno stato leggo una lettera, so gia' in quale stato rappresentante devo andare.

T-completezza permette di definire la transizione del DFA ipotesi.

22. Perche queste due proprieta' sono opposte

T-minimalita':

non avere troppi stati.

T-completezza:

avere abbastanza stati per rappresentare tutte le transizioni.

L* alterna questi due movimenti:

• se manca un rappresentante, aggiunge elementi a $S$;
• se un controesempio mostra che due righe erano confuse, aggiunge suffissi a $T$.

Parte V - Observation table e matrice di Hankel

23. Riga di una parola

Per una parola $s$, definiamo la sua riga rispetto a $T$:

$$ \langle s\rangle_T:T\to\{0,1\} $$

con:

$$ \langle s\rangle_T(t)=Membership(st). $$

Quindi $\langle s\rangle_T$ e' il vettore delle risposte del teacher su tutti i suffissi di test.

Due parole sono equivalenti rispetto a $T$ se e solo se hanno la stessa riga:

$$ s\sim_{L_0,T}s' \quad\Longleftrightarrow\quad \langle s\rangle_T=\langle s'\rangle_T. $$

24. Observation table

La tabella ha:

• righe indicizzate da parole in $S$ e da parole di frontiera $S\cdot\Sigma$;
• colonne indicizzate da $T$;
• celle date da membership query.

La cella $(u,t)$ contiene:

$$Membership(ut).$$

Questa e' una finestra finita della matrice di Hankel infinita del linguaggio.

25. Che cosa rappresentano le righe

Una riga non e' solo una lista di 0 e 1. E' una approssimazione del linguaggio residuo:

$$u^{-1}L_0=\{t\in\Sigma^\ast\mid ut\in L_0\}.$$

Due prefissi hanno lo stesso residuo se hanno la stessa classe di Myhill-Nerode.

L* non vede tutto il residuo. Vede solo la sua restrizione a $T$.

26. Chiusura della tabella

La tabella e' chiusa, o $S$ e' T-completo, se ogni riga di frontiera $sa$ con $s\in S$ e $a\in\Sigma$ coincide con una riga gia' presente in $S$.

In formula:

$$ \forall s\in S,\forall a\in\Sigma,\exists s'\in S: \langle sa\rangle_T=\langle s'\rangle_T. $$

Se manca $s'$, aggiungiamo $sa$ a $S$.

27. Consistenza della tabella

Nella formulazione classica di L*, oltre alla chiusura si usa anche la consistenza:

se due righe di $S$ sono uguali, allora restano uguali dopo ogni estensione con la stessa lettera.

Formula:

$$ \langle s\rangle_T=\langle s'\rangle_T \Rightarrow \forall a\in\Sigma,\ \langle sa\rangle_T=\langle s'a\rangle_T. $$

Nel taglio degli appunti, T-minimalita' e T-completezza sono il modo principale di raccontare l'invariante. La consistenza e' la versione tabellare dello stesso bisogno: le transizioni devono essere ben definite.

28. Matrice di Hankel

La matrice di Hankel completa del linguaggio ha:

• righe = prefissi $u\in\Sigma^\ast$;
• colonne = suffissi $v\in\Sigma^\ast$;
• cella $(u,v)$ = 1 se $uv\in L_0$, 0 altrimenti.

L* lavora su una sottomatrice finita:

$$S\cup S\Sigma \quad\text{per le righe},\qquad T\quad\text{per le colonne}. $$

Il significato e':

• aggiungere righe a $S$ = scoprire nuovi stati;
• aggiungere colonne a $T$ = scoprire nuovi test che separano stati.

29. Lettura visuale

Se due righe sono uguali, il learner non ha ancora un test per distinguerle.

Se un controesempio rivela che l'automa sbaglia, allora c'e' una distinzione non vista. Aggiungere suffissi del controesempio a $T$ aggiunge colonne. Quelle colonne possono separare righe prima uguali.

Questa e' la dinamica centrale:

colonne nuove raffinano le classi; righe nuove aggiungono stati.

Parte VI - Algoritmo L*

30. Pseudocodice

Una versione coerente con gli appunti:

S = T = {epsilon}

loop:
  while S non e' T-completo:
    scegli s in S e a in Sigma tali che
      nessun s1 in S soddisfa s1 ~_{L0,T} s a
    S = S union {s a}

  costruisci il DFA A:
    stati = S
    stato iniziale = epsilon
    finali = {s in S | Membership(s)=1}
    delta(s,a) = l'unico s1 in S tale che s1 ~_{L0,T} s a

  chiedi Equivalence(A)
  se il teacher risponde si':
    restituisci A
  altrimenti:
    ricevi controesempio w
    T = T union {suffissi di w}

31. Step 1: rendere S T-completo

Cerchiamo un problema di chiusura:

$$s\in S,\quad a\in\Sigma,$$

tale che:

$$ \nexists s_1\in S:\ s_1\sim_{L_0,T}sa. $$

Lettura:

leggendo $a$ da $s$, finisco in una classe che non ha ancora un rappresentante in $S$.

Allora aggiungo:

$$S:=S\cup\{sa\}.$$

Questo aggiunge uno stato candidato.

32. Perche aggiungere sa non rompe T-minimalita'

Quando aggiungo $sa$, l'ho scelto proprio perche':

$$ \nexists s_1\in S:\ s_1\sim_{L_0,T}sa. $$

Quindi $sa$ non e' equivalente a nessun vecchio rappresentante.

Percio' non sto duplicando uno stato gia' rappresentato. Sto aggiungendo una classe nuova rispetto ai test attuali.

33. Step 2: costruire il DFA ipotesi

Quando $S$ e' T-completo e T-minimale, posso costruire un DFA.

Stati:

$$Q=S.$$

Stato iniziale:

$$q_0=\varepsilon.$$

Stati finali:

$$F=\{s\in S\mid Membership(s)=1\}.$$

Transizione:

$$\delta(s,a)=s_1$$

dove $s_1$ e' l'unico elemento di $S$ tale che:

$$s_1\sim_{L_0,T}sa.$$

34. Perche la transizione esiste ed e' unica

Esistenza:

• viene da T-completezza.
• per ogni $s$ e $a$, qualche $s_1\in S$ rappresenta $sa$.

Unicita':

• viene da T-minimalita'.
• non possono esserci due elementi distinti di $S$ nella stessa classe osservata.

Quindi $\delta$ e' ben definita.

35. Step 3: equivalence query

Il learner chiede:

$$L(\mathcal{A})=L_0?$$

Se si', l'algoritmo termina.

Se no, il teacher restituisce:

$$w\in L(\mathcal{A})\triangle L_0.$$

Il simbolo $\triangle$ indica differenza simmetrica.

36. Step 4: usare il controesempio

Se $w$ e' un controesempio, allora l'equivalenza attuale era troppo grossolana: ha confuso due situazioni che il linguaggio target distingue.

L* aggiunge a $T$ i suffissi di $w$:

$$T:=T\cup Suff(w).$$

Perche' suffissi?

Perche' Myhill-Nerode distingue prefissi osservando suffissi futuri. Un controesempio e' una parola completa su cui l'ipotesi sbaglia; i suoi suffissi sono i test naturali per scoprire dove, lungo la computazione, due stati sono stati fusi erroneamente.

37. Cosa succede dopo un controesempio

Aggiungere suffissi a $T$ aggiunge colonne alla tabella. Due righe prima uguali possono diventare diverse.

Gli appunti sottolineano un fatto chiave:

dopo un controesempio, $S$ diventa T-incompleto e nella prossima fase dovra' crescere.

Quindi ogni equivalence query fallita forza progresso strutturale: prima o poi si aggiungono nuovi rappresentanti a $S$.

38. Perche l'algoritmo non cresce all'infinito

Ogni elemento di $S$ rappresenta una classe distinta di $\sim_{L_0,T}$.

Questa equivalenza e' piu' grossolana della vera equivalenza di Myhill-Nerode. Quindi il numero di classi osservate non puo' superare il numero di classi vere.

Se il DFA minimo di $L_0$ ha $n$ stati, allora:

$$|S|\le n.$$

Ogni controesempio utile porta, dopo la fase di completamento, ad aumentare $|S|$. Quindi non si puo' fallire per sempre.

39. Complessita' intuitiva

La complessita' e' polinomiale nel modello MAT rispetto a:

• numero di stati del DFA minimo;
• dimensione dell'alfabeto;
• lunghezza massima dei controesempi.

La ragione e':

• ogni ciclo interno fa controlli su $S$, $\Sigma$, $S$ e $T$;
• ogni controllo usa membership query;
• il numero di volte in cui $S$ cresce e' limitato dal numero di stati minimi;
• le equivalence query fallite forniscono controesempi che raffinano $T$.

Parte VII - Esempio completo: imparare $(ab)^\ast$

40. Linguaggio target

Sia:

$$L_0=(ab)^\ast.$$

Quindi:

• $\varepsilon\in L_0$;
• $ab\in L_0$;
• $abab\in L_0$;
• $a\notin L_0$;
• $b\notin L_0$;
• $bb\notin L_0$.

Alfabeto:

$$\Sigma=\{a,b\}.$$

41. Inizializzazione

Partiamo da:

$$S=T=\{\varepsilon\}.$$

Calcoliamo le righe per $S$ e per la frontiera $S\Sigma=\{a,b\}$.

La riga di $\varepsilon$ e' diversa dalla riga di $a$ e $b$.

Quindi $S$ non e' T-completo: da $\varepsilon$ leggendo $a$ si arriva a una classe non rappresentata.

Aggiungiamo:

$$S=\{\varepsilon,a\}.$$

42. Controllo con S = {epsilon, a}

Con:

$$S=\{\varepsilon,a\},\qquad T=\{\varepsilon\},$$

calcoliamo anche $aa$ e $ab$.

Ora:

• $b$ ha la stessa riga di $a$;
• $aa$ ha la stessa riga di $a$;
• $ab$ ha la stessa riga di $\varepsilon$.

Quindi, rispetto al test attuale, $S$ e' T-completo.

43. Primo DFA ipotesi

Stati:

$$\varepsilon,\ a.$$

Stato iniziale:

$$\varepsilon.$$

Finale:

$$\varepsilon$$

perche' $\varepsilon\in(ab)^\ast$.

Transizioni:

Questo DFA accetta parole come:

$$bb.$$

Infatti:

$$\varepsilon \xrightarrow{b} a \xrightarrow{b} \varepsilon.$$

Ma:

$$bb\notin(ab)^\ast.$$

Quindi il teacher risponde no e fornisce controesempio:

$$w=bb.$$

44. Aggiornare T con i suffissi di bb

I suffissi non vuoti e quello vuoto sono:

$$bb,\ b,\ \varepsilon.$$

Aggiorniamo:

$$T=\{\varepsilon,b,bb\}.$$

Ora la tabella diventa:

Ora $b$ non ha piu' la stessa riga di $a$. Il controesempio ha separato una classe che prima era fusa.

S non e' piu' T-completo, perche' da $\varepsilon$ leggendo $b$ otteniamo una riga non rappresentata in $S$.

Aggiungiamo:

$$S=\{\varepsilon,a,b\}.$$

45. Secondo DFA ipotesi

Con $S=\{\varepsilon,a,b\}$, le transizioni sono:

Stato finale:

$$\varepsilon.$$

Questo e' il DFA minimo di $(ab)^\ast$:

• $\varepsilon$ = sono allineato su blocchi completi;
• $a$ = ho letto una $a$ e aspetto $b$;
• $b$ = stato pozzo/errore.

Il teacher risponde si'. L'algoritmo termina.

46. Che cosa insegna l'esempio

L'esempio mostra il ciclo completo:

1. pochi test fanno sembrare uguali $a$ e $b$;
2. l'ipotesi sbaglia su $bb$;
3. il controesempio aggiunge suffissi a $T$;
4. le colonne nuove separano $a$ e $b$;
5. $S$ cresce;
6. l'automa corretto emerge.

La frase da dire all'orale:

i controesempi non vengono solo memorizzati come esempi negativi; vengono spezzati in suffissi che raffinano la capacita' della tabella di distinguere stati.

Parte VIII - Perche L* e' corretto

47. Invariante 1: T-minimalita'

Durante l'algoritmo, $S$ resta T-minimale.

Quando aggiungiamo $sa$, lo facciamo solo perche' nessun elemento di $S$ e' equivalente a $sa$ rispetto a $T$.

Quindi non introduciamo duplicati osservati.

48. Invariante 2: T-completezza prima della query

Prima di costruire il DFA, il ciclo interno garantisce T-completezza.

Questo assicura che ogni transizione:

$$\delta(s,a)$$

abbia una destinazione in $S$.

49. Se il teacher accetta, il DFA e' corretto

Questo e' immediato dal significato dell'equivalence query:

$$Equivalence(\mathcal{A})=\text{si'}$$

vuol dire:

$$L(\mathcal{A})=L_0.$$

Quindi l'algoritmo puo' restituire $\mathcal{A}$.

50. Se il teacher rifiuta, c'e' progresso

Se il teacher restituisce un controesempio $w$, allora la tabella non distingueva abbastanza.

Aggiungendo suffissi di $w$ a $T$, rendiamo piu' fine $\sim_{L_0,T}$. Alla prossima fase, almeno una transizione prima "coperta" puo' non esserlo piu', e $S$ dovra' crescere.

Questo e' il cuore della terminazione.

51. Perche il limite e' il DFA minimo

Nel caso peggiore, L* scopre tutte le classi di Myhill-Nerode.

Quando $S$ contiene un rappresentante per ogni classe vera, la tabella ha abbastanza stati per costruire il DFA minimo.

In quel momento l'equivalence query deve rispondere si'.

Parte IX - Black-box learning e V&V

52. MAT ideale contro pratica reale

Nel MAT, il teacher e' perfetto.

In pratica, se il sistema e' una black box:

• una membership query si puo' implementare eseguendo il sistema su input $w$;
• una equivalence query perfetta e' quasi mai disponibile.

Allora si approssima:

• testing random;
• conformance testing;
• fuzzing;
• ricerca sistematica di controesempi.

Se non trovi controesempi, non hai una prova assoluta di equivalenza. Hai evidenza sperimentale.

53. Perche interessa alla verifica

In V&V, automata learning viene spesso chiamato:

• model learning;
• system identification;
• protocol state fuzzing;
• grammar inference.

L'idea:

ho un sistema reale o una black box, e costruisco un modello automata-based del suo comportamento osservabile.

Poi posso:

• ispezionare il modello;
• confrontarlo con una specifica;
• fare model checking sul modello appreso;
• generare test migliori.

54. Esempio: protocol state fuzzing

Un protocollo di rete puo' avere stati interni:

• handshake non iniziato;
• autenticato;
• sessione aperta;
• errore;
• chiuso.

Non vedo direttamente questi stati. Posso pero' inviare sequenze di messaggi e osservare risposte.

Ogni sequenza di messaggi e' una parola. La risposta del sistema permette di classificarla o di costruire un transduttore.

Learning automata serve a ricostruire una macchina finita che approssima il protocollo.

55. Limite pratico

Il punto debole e':

senza equivalence query perfetta, non ho garanzia assoluta di aver imparato il modello vero.

Pero' anche un modello approssimato puo' essere utile:

• scopre stati inattesi;
• evidenzia transizioni non documentate;
• trova bug;
• guida test successivi.

Parte X - Da linguaggi a funzioni: transduttori

56. Perche parlare di transduttori

Un DFA riconosce un linguaggio:

$$f:\Sigma^\ast\to\{0,1\}.$$

Ma molti sistemi non rispondono solo si/no. Producono output.

Un transduttore sequenziale modella funzioni:

$$f:\Sigma^\ast\to\Gamma^\ast.$$

L'input e' una parola, l'output e' una parola.

57. Transduttore sequenziale

Un transduttore sequenziale e' un automa finito in cui le transizioni producono anche output.

Lettura:

mentre leggo input, accumulo output.

Questo e' vicino agli automi di Mealy del capitolo 10, dove ogni input produce un output e la macchina implementa una strategia.

58. Relazione con Myhill-Nerode per funzioni

Per le funzioni, non basta chiedere se $ut$ e $vt$ sono accettati.

Bisogna confrontare il comportamento residuo dell'output dopo aver letto un prefisso.

Gli appunti indicano una relazione del tipo:

$$ u\sim_{f_0,T}v \quad\Longleftrightarrow\quad \forall t\in T,\ f(ut)-f(u)=f(vt)-f(v). $$

Lettura intuitiva:

dopo aver letto $u$ o $v$, i futuri test $t$ producono lo stesso output residuo.

La forma precisa dipende dal modello di output, ma l'idea resta la stessa: stati = residui del comportamento futuro.

59. Perche ricordarlo per l'orale

Learning automata non e' solo un algoritmo isolato su DFA.

E' un paradigma:

1. identificare stati come classi di comportamento futuro;
2. usare query per distinguere classi;
3. costruire una macchina finita;
4. raffinarla con controesempi.

Questo paradigma riappare:

• nei transduttori;
• nei protocolli;
• nella sintesi;
• nei modelli reattivi.

Parte XI - Quadro finale

60. Errori tipici

Confondere membership ed equivalence query

Membership chiede:

$$w\in L_0?$$

Equivalence chiede:

$$L(\mathcal{A})=L_0?$$

La prima e' locale. La seconda e' globale.

Pensare che il learner debba trovare lo stesso automa del teacher

No. Deve trovare un automa equivalente.

Se il teacher usa un DFA non minimo e il learner trova il minimo, va benissimo.

Confondere $=_{L_0}$ e $\sim_{L_0}$

$=_{L_0}$ guarda solo se due parole sono entrambe dentro o fuori.

$\sim_{L_0}$ guarda tutti i suffissi futuri.

La seconda e' molto piu' fine ed e' quella che produce gli stati del DFA minimo.

Pensare che T-completezza significhi correttezza globale

No. T-completezza significa solo che la tabella e' chiusa rispetto ai test attuali.

L'equivalence query serve proprio a controllare se l'ipotesi e' corretta globalmente.

Pensare che il controesempio sia solo un esempio in piu'

Il controesempio serve a generare suffissi da aggiungere a $T$.

Quindi cambia le colonne della tabella e puo' separare stati prima confusi.

Dimenticare il collegamento con Myhill-Nerode

L* non e' magia tabellare. E' Myhill-Nerode imparato progressivamente tramite test finiti.

61. Mini-esercizi guidati

Esercizio 1: membership o equivalence?

Domanda:

"La parola $abba$ appartiene al linguaggio target?"

Risposta: membership query.

Esercizio 2: membership o equivalence?

Domanda:

"Questo DFA riconosce esattamente il linguaggio target?"

Risposta: equivalence query.

Esercizio 3: distinguere due prefissi

Sia $L=(ab)^\ast$. $a$ e $b$ sono distinguibili?

Si'. Basta il suffisso:

$$t=b.$$

Infatti:

$$ab\in L,$$

ma:

$$bb\notin L.$$

Quindi:

$$a\not\sim_L b.$$

Esercizio 4: T piccolo

Con $T=\{\varepsilon\}$, nel linguaggio $(ab)^\ast$, $a$ e $b$ sono distinguibili?

No, perche':

$$a\notin L,\qquad b\notin L.$$

Rispetto al solo test $\varepsilon$, hanno entrambi riga 0.

Esercizio 5: suffisso che separa

Dopo il controesempio $bb$, perche' aggiungere il suffisso $b$ aiuta?

Perche':

$$ab\in(ab)^\ast$$

ma:

$$bb\notin(ab)^\ast.$$

Quindi il suffisso $b$ separa i prefissi $a$ e $b$.

Esercizio 6: T-completezza

Se esiste $s\in S$ e $a\in\Sigma$ tale che la riga di $sa$ non coincide con nessuna riga di $S$, che cosa fai?

Risposta:

$$S:=S\cup\{sa\}.$$

Esercizio 7: ruolo di Hankel

Che cosa rappresenta una riga della matrice di Hankel?

Risposta: il comportamento di un prefisso rispetto ai suffissi, cioe' una approssimazione del linguaggio residuo.

62. Mappa per l'orale

Per partire bene con Learning Automata:

1. Apri con l'idea: ricostruire una macchina finita tramite esperimenti.
2. Distingui passive learning e active learning.
3. Presenta MAT: teacher perfetto, linguaggio target regolare, learner.
4. Definisci membership query ed equivalence query.
5. Spiega perche servono entrambe.
6. Collega tutto a Myhill-Nerode: stati = classi di comportamento futuro.
7. Definisci $\sim_{L_0,T}$ come approssimazione finita.
8. Spiega $S$ come rappresentanti di stati e $T$ come suffissi di test.
9. Definisci T-minimalita' e T-completezza.
10. Introduci la observation table/Hankel.
11. Descrivi L*: completa $S$, costruisci DFA, chiedi equivalence, usa controesempio.
12. Fai l'esempio di $(ab)^\ast$ almeno fino al controesempio $bb$.
13. Spiega terminazione: $S$ cresce ma non supera le classi Myhill-Nerode.
14. Chiudi con applicazioni V&V: model learning, protocol state fuzzing, black-box testing.

63. Risposta orale pronta

Una risposta compatta:

L'automata learning studia come ricostruire un automa finito che riconosce un linguaggio target, partendo solo dall'alfabeto e da interazioni con un teacher. Nel modello MAT il teacher conosce il linguaggio regolare $L_0$ e risponde a membership query, cioe' domande del tipo $w\in L_0?$, ed equivalence query, cioe' domande del tipo $L(\mathcal{A})=L_0?$. Se l'ipotesi e' sbagliata, il teacher fornisce un controesempio nella differenza simmetrica.

L'algoritmo L* di Angluin si basa su Myhill-Nerode. Due prefissi rappresentano lo stesso stato se nessun suffisso futuro li distingue. Siccome non possiamo testare tutti i suffissi, manteniamo un insieme finito $T$ di suffissi di test e un insieme $S$ di rappresentanti di stati. La tabella di osservazione, o finestra della matrice di Hankel, contiene i valori $Membership(st)$. Quando $S$ e' T-completo e T-minimale, si costruisce un DFA ipotesi. Se l'equivalence query fallisce, i suffissi del controesempio vengono aggiunti a $T$, raffinando le classi osservate. Il processo termina perche' $S$ puo' crescere al massimo fino al numero di classi di Myhill-Nerode, cioe' agli stati del DFA minimo.

64. Riassunto finale

Learning Automata e' Myhill-Nerode trasformato in un processo interattivo.

La teoria dice:

$$\text{stati minimi}=\text{classi di Myhill-Nerode}.$$

L'algoritmo dice:

non conosco le classi, quindi le approssimo con test finiti, costruisco ipotesi, e uso controesempi per raffinarle.

La catena da ricordare e':

$$ \text{membership query} \to \text{righe Hankel} \to \text{classi osservate} \to \text{DFA ipotesi} \to \text{equivalence query} \to \text{controesempio} \to \text{nuovi suffissi in }T. $$

Per l'orale, il messaggio forte e':

L* impara il DFA minimo non enumerando automi, ma scoprendo progressivamente le classi di comportamento futuro del linguaggio.