模型學習 Angluins' L-star 演算法

DFA#

一個正規語言（Regular Language）的語法可以用一個正則表達式（Regular Expression）來描述，或者用一個確定有限自動機（Definite Finite Automation，DFA）來表達，例如：

一個僅包含字符 a 和 b，且他們各自出現次數均為偶數的字符串。

可以表示為

其中 q0 既是起始態，也是終結態。

如果將該 DFA 視為一個黑盒，用戶輸入一個字符串之後僅能夠得到該字符串是否符合該文法的布爾值（accept /reject），那麼通過不斷的嘗試符號的組合，並且根據是否符合文法的判斷來反向推斷文法 / DFA，就可以看作是學習狀態模型（state model）的過程。

一個 DFA 由五元組 $(Q,\Sigma,\delta,F,q_0)$ 表示：

L* 算法的核心是一張表 ——Observation Table（OT），一個 OT 可以表示為三元組 $(S_D,E_D,T_D)$：

$S_D$ 包含前綴封閉的字符串集合，是表格的行索引的一部分。這些字符串表示可能存在的狀態，被稱作 access string。
$E_D$ 包含後綴封閉的字符串集合，是表格的列索引的集合。這些字符串用於區分不同的狀態（即定義狀態的等價關係），被稱作 distinguish string。OT 中任意取出兩行 $s,t$，若他們對應的每個 distinguish string 的項的取值都相等（也就是說這兩行的內容完全相同），那麼這兩行對應的狀態就是等價的，記作 $s\cong t$ 。等價的狀態可以被歸並為 1 個狀態，在 DFA 中表示為 1 個節點。
$T_D$ $T_{D}$ ： $(S_D \cup S_D \cdot \Sigma)\times E_D\rightarrow \{0,1\}$ $(S_{D} \cup S_{D} \cdot Σ) \times E_{D} \to {0, 1}$ 表示表中每行每列的項。其中行索引不僅包含 $S_D$ $S_{D}$ ，還包含 $S_D\cdot\Sigma$ $S_{D} \cdot Σ$ ，後者為每個可能的 $S_D$ $S_{D}$ 後加上一個符號組成的字符串的集合。 $T_D(s,e)$ $T_{D} (s, e)$ 的取值由字符串 $s\cdot e$ $s \cdot e$ （直接相連）能否被 accept 決定，是一個布爾值。
- OT 表中真正表示狀態的行為 $S_D$ ， $S_D\cdot\Sigma$ 跟多的只是用於輔助判斷狀態之間跳轉關係的。

要使得 OT 能夠表示成一個合理的 DFA，需要滿足兩個性質：

封閉性（closed）：因為 $S_D\cdot\Sigma$ 表示從一個狀態出發，添加一個符號，到達的下一個狀態，這個新的狀態如果與所有 $S_D$ 中的狀態都不等價，那就說明存在至少一個新狀態，即 OT 不封閉，還可以繼續拓展。將來在構造 DFA 時，就知道每一個狀態 $S_D$ 添加任意一個符號 $\Sigma$ 之後會跳轉到的目的狀態，如果目的狀態已經存在在 $S_D$ 中了，那無妨，但如果不存在在 $S_D$ 中，那就說明還有新的狀態沒有探索到。
一致性（consistent）：對於任意兩個等價的狀態 $s,t\in S_D$ ，對於每一個符號 $i\in\Sigma$ ，都要有 $s\cdot i\cong t\cdot i$ 。如果不成立，那就說明 s、t 不是等價的，因為從他們出發通過同一個符號可能會到達不同的狀態。等價關係根據當前 OT 的列索引（distinguish string）產生，因此在列索引產生變化之後等價關係同樣也會發生變化。一般而言，對於一個狀態的認識是從模糊到精確的過程，所以先前被認為是等價的關係往往隨著 distinguish string 的增加會變為不等。

初始化 $S_D=E_D=\{\epsilon\}$ ，並且連同 $S_D\cdot\Sigma$ 一道構造 OT 的所有行。
為了獲得每一行的項的取值，向 oracle 進行 membership query：對於 $(s,e)$ ，詢問 oracle 從狀態 s 出發經過符號 e 的路徑是否能夠 accept。填充整張表。
判斷是否為封閉和一致：
1. 如果不封閉，就從 $S_D\cdot\Sigma$ 中取出一個不封閉的行，移動到 $S_D$ 部分。
2. 如果不一致，即 $T_D(s\cdot i,e)\neq T_D(t\cdot i,e)$ ，就將 $i\cdot e$ 加入到 distinguish string 中。橫向拓展 OT，並通過 membership query 填充表內內容。
如果一致，通過 OT 構造 DFA，向 oracle 提出 equivalence query（等價查詢）：
1. 如果不等價，oracle 會返回 counter example（反例），將反例的所有前綴 string 添加到 $S_D$ 中，並拓展 $S_D\cdot\Sigma$ ，回到步驟二。
2. 如果等價，那麼就結束了。

Reverse Engineering Enhanced State Models of Black Box Software Components to support Integration Testing 給出的例子的完整過程如下。假設 oracle 有如下的 DFA。

其 $\Sigma=\{a,b\}$ ， $S_D\cdot\Sigma$ 為 $\epsilon$ 加上 $\Sigma$ 中的每個符號（ ${\epsilon\cdot a,\epsilon\cdot b}$ ），初始狀態 $q0=[\epsilon]$ 。

該 OT 既是一致的，但不封閉，因為 $\epsilon\cdot a$ 在 $S_D$ 中沒有與其等價的行（ $\epsilon\cdot b$ ），因此把 $\epsilon\cdot a$ （即 $a$ ）移入 $S_D$ 中。
由於 a 被新添加到了 $S_D$ ，所以 $S_D\cdot\Sigma$ 需要添加 $a\cdot a, a\cdot b$ ，對 oracle 做 membership query，得到 $T_D(a\cdot a,\epsilon)=1,\ T_D(a\cdot b,\epsilon)=0$ 。
此時 OT 是封閉且一致的，且只有 2 個等價類，一類是 $\{\epsilon,a\cdot a\}$ ，另一類是 $\{a,b,a\cdot b\}$ ，這兩個等價類反映到圖上就是 2 個狀態，並且結合後一個類上添加字符 a 和 b 到達的不同的狀態，可以得到 DFA。

此時做等價查詢，得到反例 $b\cdot b$ 沒有被構造出的 DFA 滿足。將 $b\cdot b$ 的所有前綴（ $\{b,b\cdot b\}$ ）添加到 OT 的 $S_D$ 中，並且將 $b\cdot a,b\cdot b\cdot a,b\cdot b\cdot b$ 加入到 $S_D\cdot\Sigma$ 。

此時 OT 是否封閉的，但不一致，因為等價狀態 $a,b$ 添加同一個符號 $a$ 後的 $T_D(a, a)\neq T_D(b,a)$ ，說明 $a,b$ 實際上並不等價，需要做進一步區分，區分的依據即為狀態 $a,b$ 再添加一個符號 $a$ 之後可能跳轉的狀態。
$E_D$ 添加了 $a$ 之後，對 oracle 做 membership query，填滿整個 OT，上一個 OT 中等價的 a、b 此時也已經不等價了。
此時 OT 是一致且封閉的，可以構造成 DFA。

對 oracle 做 equivalence query，得到反例 $a\cdot b\cdot b$ 雖然是構造出的 DFA 所能 accept，但是 oracle 對其 reject。將 $a\cdot b\cdot b$ 的所有前綴加入 $S_D$ （這裡只需要再添加 $a\cdot b\cdot b$ 即可），並且向 $S_D\cdot\Sigma$ 添加 $\{a\cdot b\cdot a,a\cdot b\cdot b\cdot a,a\cdot b\cdot b\cdot b\}$ 。

此時 OT 是封閉但不一致的，因為 $T_D(b,b)\neq T_D(a\cdot b,b)$ ，則需要把 $b$ 也加入 $E_D$ ，橫向拓展 OT。
對 oracle DFA 做 membership query，填充整張表，此時表式封閉且一致的，構造出的 DFA 與 oracle DFA 經過 equivalence query 判別也是等價的。

OT 表分為上下兩個部分，上半部分 $S_D$ 用字符串（符號串）來表示，下半部分 $S_D\cdot\Sigma$ 則是用於輔助判斷 $S_D$ 的跳轉目標是否已知，若已知的話應對應於某個 $S_D$ ，若未知則說明 $S_D$ 中還應有新的成員。
L* 算法學習的過程本質上是對各個狀態的認識從模糊到逐步清晰的過程。
- 當 OT 不封閉時，說明需要添加新狀態了，視野進一步擴大。
- 當 OT 不一致時，說明對於等價狀態的認識需要進一步細化了。
$E_D$ 是區分不同狀態的特徵值，在 DFA 中，兩個狀態的等價可以理解為：這兩個狀態分別經過相同的符號都能夠跳轉到終結態，或者都不能夠跳轉到終結態。

參考資料：