AngluinのL*アルゴリズムと機械学習(特にRNN)への応用

はじめに

はじめまして。ashiato45です。今回は人工知能系会議のAAAI20にアクセプトされた(to appear)論文である[1]の紹介をしようと思ったのですが、そのためのテクニックであるAngluinのL*アルゴリズム[2]、あるいはその拡張であるBalle and Mohriのアルゴリズム[3]について日本語で書かれた手頃な資料がなかったので、このあたりを解説してみる記事を書こうと思います。¹

ちなみに、「手頃な資料がない」とは言ったのですが有償なら日本有数のオートマトン使いであるMasWag氏(https://twitter.com/MasWag) が執筆した「RNNからのオートマトン学習」が「ヤバイテック トーキョー vol.1」[4]に収録されており、電子版が入手可能ですのでそちらをお薦めします。

前提知識

DFA,NFAといった学部程度の形式言語理論と、学部1年程度の線形代数の知識(とはいっても、行列算ができてかつ数ベクトルの一次独立、従属あたりがわかっていれば十分です)を仮定します。

形式言語理論についてはMyhill-Nerodeぐらいまでです。一回学んだことがあって復習したい方は日本有数のオートマトン使いである秋田大の新屋良磨先生 (https://twitter.com/sinya8282) の解説論文である「オートマトン理論再考」[5]がWebからのアクセスもできて短かくて良いと思います。

記号について

受理/拒否やTrue/Falseを1/0であらわすことがあります。

AngluinのL*アルゴリズム

これは何？

手短に言うと「DFAを学習するアルゴリズム」なのですが、アルゴリズムといいつつ実は結構設定がややこしいので、とりあえず問題設定をゆっくり説明し、そのあと数学的に手短な設定の説明をして、原理の説明をしようと思います。

問題のお気持ち

問題の形が似ているので、プログラミングの(昔ながらの)入門書の定番である「数あてゲーム」を思いだしてみましょう。

出題者と回答者がいる。出題者は1-100の値Nをランダムに選び紙に書いて伏せておく。回答者は出題者に1つの値Mを言うと、出題者はNとMの大小を比較して「Mは私の選んだ値より小さいです」「Mは私の選んだ値より大きいです」「正解です。Mは私の選んだ値です」の3種類の返答をする。回答者はできるだけ少ない回数で出題者の選んだ値を当てたい。どのようにMを選んでいけばよいか？

もちろんM=1からはじめ、次は2、3…とやっていっても正解自体はできるのですが、二分探索を使ってM=50からはじめ、次に帰ってきた返答に応じてM=25、M=75としていったほうが平均的には高速です。

似たような感じで、今度は出題者が思いうかべた正規言語 L を回答者が当てにいく問題を考えましょう。ここからは論文[2]に合わせて出題者のことはTeacher、回答者のことはLearnerと呼ぶことにします。次はこの「ゲーム」のルール設定で、どのような質問をすることができるかですが、まずはmembership queryという質問をすることができることにしましょう:

LearnerはTeacherに「語 $w\in \Sigma^\star$ はあなたの思いうかべた正規言語Lに属しますか？」と聞くことができる

このmembership queryを繰り返すとLearnerは言語Lについて有限個の断片的な所属の情報を得ることができ、それらと整合するDFA Aを作ることができます。しかし、これをいくら繰り返してもL=L(A)かどうかをLearnerが知ることはできないので、次のequivalence queryという質問もできるということにしましょう:

LearnerはTeacherに「DFA Aはあなたの思いうかべた正規言語と同じ言語を定義しますか？」と聞くことができる。Teacherはもしもそうなら「はい、L(A)=Lです」と答える。そうでないならば、語wで $L(A)\setminus L$か$L \setminus L(A)$に属するものが存在するはずなので、そのようなものを1つ選んで「いいえ、wが反例です」と答える。

この2つの質問ができるという前提で、LearnerはL=L(A)なるAを作るためにどのような質問をすれば少ない回数の質問ですむでしょう。このために有限オートマトンの性質を利用して質問の作りかたを与えるのがAngluinのL*アルゴリズムです。

数学的っぽい表現

AngluinのL*アルゴリズムは、membership queryに対応するオラクル²

$m:\Sigma^\star\to \{0,1\}$

と、equivalence queryに対応するオラクル
$e:\{DFAs\}\to \{\mathrm{Equivalent}\}\sqcup \Sigma^\star $
(ここでEquivalentはそういうアトムです)を入力として、最小DFA $A$ を出力します。
そして、次の性質をもちます:

$L$を正規言語とする。もしも
$$m(w)=\chi_L(w)$$³かつ
$$
e(A')=\begin{cases}
\mathrm{Equivalent} &; L(A')=L\\
w &; w\in L \triangle L(A')
\end{cases}
$$
をm,eが満たすのなら、このアルゴリズムはmとeを多項式回呼び出して⁴停止し、$L=L(A)$となる。⁵

(m,e)の対のことをTeacherといいます。eが返す文字列のことを「反例(counterexample)」といいます。

動作例/おもちゃ

問題とアルゴリズムの入出力がはっきりしたところで、実際にmとeを定めたときにアルゴリズムがどんな動作をするのか、Learnerはどんな質問の列を作るのかという動作例を見てみましょう。アルファベット $\Sigma=\{a, b\}$上の言語L={w∈Σ | wにはaもbも偶数個あらわれる}を考え、これを学習することを考えます。
下のなかではオートマトンの画像が出ますが、Sと書いてある状態が初期状態で、Aと書いてあるのが受理状態です。

Learner	Teacher
ε∈Lですか？	はい
a∈Lですか？	いいえ
b∈Lですか？	いいえ
aa∈Lですか？	はい
ab∈Lですか？	いいえ
が答えですか？	いいえ。bbが反例です。
bb∈Lですか？	はい
ba∈Lですか？	いいえ
bba∈Lですか？	いいえ
bbb∈Lですか？	いいえ
aaa∈Lですか？	いいえ
aba∈Lですか？	いいえ
baa∈Lですか？	いいえ
bbaa∈Lですか？	はい
bbba∈Lですか？	いいえ
が答えですか？	いいえ。abbが反例です。
abb∈Lですか？	いいえ
abba∈Lですか？	はい
abaa∈Lですか？	いいえ
abbaa∈Lですか？	いいえ
abbb∈Lですか？	いいえ
abbba∈Lですか？	いいえ
aab∈Lですか？	いいえ
bab∈Lですか？	いいえ
bbab∈Lですか？	いいえ
abab∈Lですか？	はい
abbab∈Lですか？	いいえ
aaab∈Lですか？	いいえ
baab∈Lですか？	はい
bbaab∈Lですか？	いいえ
bbbb∈Lですか？	はい
bbbab∈Lですか？	いいえ
abaab∈Lですか？	いいえ
abbaab∈Lですか？	いいえ
abbbb∈Lですか？	いいえ
abbbab∈Lですか？	はい
が答えですか？	はい。正解です。

こんな感じで動作します。このTeacher (m,e)としてユーザの入力を使ったデモが
https://colab.research.google.com/drive/1zdFtXE1UpVJKmEFIWzaPh5ow8PS7Idf4
にあるのでよかったら試してみてください。

2020年6月29日更新: 上の例なのですが、スクリプトのバグにより経緯が間違っています。colabのほうは直したので正しい流れをみたいかたはそちらをご覧ください。

原理

正直何がしたいのかがわかってもらえれば割と十分なので、以下のことはオートマトンとか数学とかが好きな人向けです。

Hankel matrixからのオートマトンの構成

アルファベットΣについて、行も列も$\Sigma^\star$でラベルづけされているような無限行無限列の表を考えてみましょう。そして、Lをなんらかの言語として、p行s列($p,s\in \Sigma^\star$)にはp・s∈Lかどうかを0/1で書いてみましょう。例えばLとして先程使った言語をつかえば、この表はこのようになります:

prefix\suffix	ε	a	b	ab	…
ε	1	0	0	0	…
a	0	1	0	0	…
aa	1	0	0	0	…
ab	0	0	0	1	…
aba	0	0	1	0	…
abb	0	1	0	0	…
abaa	0	0	0	1	…
abab	1	0	0	0	…
…	…	…	…	…	…

本当はそんな名前ではないのですが、Balle and Moriから名前をかりて、この無限の表をLのHankel matrixとよぶことにします。

Myhill-Nerodeの定理の教えるところによれば、言語Lが正則であることは、「$a\sim_L b \iff (\forall w\in \Sigma^\star. (aw\in L \iff bw\in L))$ 」によって定まる関係で$\Sigma^\star$を割った同値類
$\Sigma^\star/\sim_L$が有限指標であることと等価だったわけですが、Hankel matrixのw行目にあらわれているものはwのこの同値類の情報に他なりません。したがって、Myhill-Nerodeの定理を次のように言いかえることができます:

Lは正則である<==>LのHanel matrixにあらわれる行は有限種類しかない。

また、その証明を思い出せばLのHankel matrixからLに対応するオートマトンを次のように構成することができます:
1. 行の内容すべて$\{\lambda s\in\Sigma^\star. \chi_L(ps); p\in \Sigma^\star\}$を集め(これはLが正則なら有限集合になる)、それらでラベルづけされたオートマトンの状態を用意する。
2. 各$f\in \{\lambda s\in\Sigma^\star. \chi_L(ps); p\in \Sigma^\star\}$と各σ∈Σについて、fでラベル付けされた状態からσを読んだときにどの状態に移動するかを知るには、$f=\lambda s\in\Sigma^\star. \chi_L(ps)$なる行ラベルpを1つ選び(どれを選んでもよい)、$\lambda s. \chi_L(p\sigma s)$(これはpσ行目に書いてある)でラベル付けされた状態を探せばよい。
3. ε行目に対応する状態を初期状態とする。
4. ε列目が1となっている状態(その状態のラベルfがf(ε)=1をみたす状態)を受理状態とする。

一般的に書くとややこしいですが上の言語の例でやってみれば、表には(1,0,0,0,…)、(0,1,0,0,…)、(0,0,1,0,…)、(0,0,0,1,…)の4つが表われる(かつこれしか表われない)ので、これらでラベルづけされた状態4つを用意します。(0,0,0,0,…)の状態からaを読んだときにどこに行くかを知るには、対応する行ラベルをとるのでした。今回はε、aa、ababが(上で表示された範囲では)表にあらわれているので、εを選んでみましょう。そして、これにaを連結したε・a=a行目を見ると、これは(0,1,0,0,…)になっています。したがって、(1,0,0,0,…)からaを読むと(0,1,0,0,…)に行くことがわかります。
となります。

観測表

上の無限の表Hankel matrixはLの内容を完全に含んでいて理想的ですが、無限の表などコンピュータのなかでは実現のしようがないのでその近似として有限の行集合$P\subset \Sigma^\star$と有限の列集合$S\subset \Sigma^\star$を考え、これらでラベル付けされた有限サイズの表を考えましょう。この表を「(P, S)をマスクとするHankel submatrix」、Hankel submatrix、あるいは観測表(observation table)とよびます。都合により、Pはprefix closed、すなわちPのどの元のどのprefixもPに属しているということにし、Sはsuffix closed、すなわちSのどの元のどのsuffixもSに属しているこということにします。

同じ方法でオートマトンをつくるときの障害2つ

観測表からこの内容に整合するオートマトンを上の1-4と同じ方法で、つまり各行に書かれている内容f: S→{0,1}を状態に対応させようとすると次のような問題がおこりえます:

• 遷移に対して状態集合が閉じていない: 集合$\{\lambda s\in S. \chi_L(ps); p\in\Sigma^\star\}$ をオートマトンの状態全体と思っているわけだが、あるp∈Pとあるσ∈Σについてλs. χ(pσs)がその集合にあらわれないときには困る。これはオートマトン的には、$\lambda s\in S. \chi_L(ps)$でラベルづけされた状態からσを読んだときの正しい行き先がないことを意味する。
• 2つの同じはずの状態から同じ文字を読んだのに別のところに遷移する: p行目、p'行目の内容が同じ、すなわちλs∈S. χL(ps) = λs∈S. χL(p's)となっているのに、それらの行から文字σを読んで遷移した先の行たちpσ行目とp'σ行目の内容が相異なる、すなわち$\lambda s\in S. \chi_L(p\sigma s) \neq \lambda s\in S. \chi_L(p'\sigma s)$のときには困る。これはオートマトン的には、$\lambda s\in S. \chi_L(ps)=\lambda s\in S.\chi_L(p's)$でラベル付けされた状態から同じσを読んで行く先が2つありDFAになってないということを意味する。⁶

逆に「遷移に対して状態集合が閉じていない」ということが起こらないことを、状態が遷移に閉じているという気持から「closed」といい、「2つの同じはずの状態から同じ文字を読んだのに別のところに遷移する」ということが起こらないことを、「consistent」といいます。もしも観測表がclosedかつconsistentならば、上の方法で観測表と整合するオートマトンを構成することができます。

AngluinのL*アルゴリズムの基本アイデア

そこで、まずP={ε}、S={ε}からはじめ、closedかつconsistentになるように観測表を拡張していけば、いまの観測表と整合するオートマトンが構成でき、かつmembership queryを作る回数を最小にすることができるのではないでしょうか。そして、そのような観測表が得られたらそこからオートマトンを構成して、そのオートマトンが正解かどうかをequivalence queryで問い合わせればよいのではないでしょうか。AngluinのL*アルゴリズムはのようになっています。

closedでない状態を解消するには、もしも「遷移に対して状態集合が閉じていない」に書いたようなpとσが見つかったら、pσをPに追加し、それで広がった観測表の未知の部分を埋めるためのmembership queryをTeacherに問い合わせればよいです。

consistentでない状態を解消するには、もしも「2つの同じはずの状態から同じ文字を読んだのに別のところに遷移する」に書いたようなp、p'とσがみつかったら、列ラベルの集合Sに{σs; s∈S}を追加します。この集合には$\lambda s\in S. \chi_L(p\sigma s)\neq \lambda s\in S. \chi_L(p'\sigma s)$となった原因が含まれているので、これでinconsistentな状態は解消されます。

AngluinのL*アルゴリズムの疑似コード

以上のことをまとめると次のような疑似コードが得られます。
1. P={ε}、S={ε}とし、観測表を埋める。
2. (P, S)で定まる観測表がclosedかどうかを調べる。closedでないなら上の方法でmembership queryをつくりPを更新する。
3. (P, S)で定まる観測表がconsistentかどうかを調べる。consistentでないなら上の方法でmembership queryをつくりSを更新する。
4. PとSの更新がとまるまで2,3を繰り返す。更新が止まったら観測表はclosedかつconsistentなので、それに対応するDFAを構成し、そのDFAでequivalence queryを作る。
5. equivalence queryの答えが「Equivalent」ならDFAが求まったので終了。そうでないならcounterexample wが返ってくるが、この結果を観測表に取り込むためにwとそのprefix全体をPに追加し2に戻る。

Balle and Mohriのアルゴリズム

Balle and Mohriのアルゴリズム[3]は先のL*アルゴリズムをweighted language(文字列から値を返すような関数。「重みつき」の言語)に拡張し、DFAのかわりにWFAを学習するものです。

WFA (Weighted Finite Automaton)

WFAは、文字列をとって実数値⁷を返す関数を定義するためのオートマトンで、次の4つ組からなります(nはなにか正整数です):

• Σ: アルファベット(有限集合)
• $\alpha \in \mathbb{R}^d$ : initial vector
• $\beta \in \mathbb{R}^d$ : final vector
• $(A_\sigma)_{\sigma \in \Sigma}\in \mathbb{R}^{d\times d}$: transition matrix (WFAをAとしたときこういう記号をつかいます)

ここから、オートマトンの実行状態に対応するconfiguraiton $\delta^\star\colon \Sigma^\star\to \mathbb{R}^d$が、
$$\delta^\star(w_1\dots w_n) = \alpha^\top A_{w_1}\dots A_{w_n}$$
と定まり、さらにWFA Aから誘導される関数$f_A\colon \Sigma^\star \to \mathbb{R}$が
$$f_A(w_1\dots w_n) = \delta^\star(w_1\dots w_n)\beta = \alpha^\top A_{w_1}\dots A_{w_n}\beta$$
と定まりま。

勘のいいかたはお気付きかと思いますが、これはDFAの行列表現で行列に書いてあった0,1の値を一般の実数値にしたものです。

Balle and Mohriのアルゴリズムの数学的っぽい表現

Balle and Mohriのアルゴリズムは、membership queryに対応するオラクル² $m:\Sigma^\star\to \mathbb{R}$と、equivalence queryに対応するオラクル $e:\{WFAs\}\to \{\mathrm{Equivalent}\}\sqcup \Sigma^\star $ を入力として、最小WFA⁸ $A$ を出力します。
そして、次の性質をもちます:

$B$をWFAとする。もしも
$$m(w)=f_B(w)$$かつ
$$
e(A')=\begin{cases}
\mathrm{Equivalent} &; f_B=f_{A'}\\
w &; f_B(w)\neq f_{A'}(w)
\end{cases}
$$
をm,eが満たすのなら、このアルゴリズムはmとeを多項式回呼び出して停止してWFA Aを返し、$f_A=f_B$となる。

Weighted languageでのHankel matrixとWFAとの関係

WFAについて、L*のときに考えたようにHankel matrixを考えると、Myhill-NerodeのHankel matrixを使った表現である

Lは正則である<==>LのHanel matrixにあらわれる行は有限種類しかない。

に対応する次のFleissの性質が成り立ちます。⁸

$f\colon \Sigma^\star\to \mathbb{R}$はあるWFAから誘導される<==>fのHanel matrixは行列として見たときに有限ランクである。

ちなみに、これが成り立つときfはrationalであるといいます。無限行列のランクってなんやねんとなるかもしれませんが、無限長の数列のなすベクトル空間$\mathbb{R}^{\Sigma^\star}$(和は普通のpointwiseです)においてHankel matrixの行たちの張る部分ベクトル空間が実は有限行で張れれば有限ランクです。

「Hankel matrixからのオートマトンの構成」の章では普通の言語のHankel matrixからDFAを作りましたが、同様にweighted languageのHankel matrixからWFAを作ることができます。普通の言語で「有限個の」となっていたところを「有限ランクの」と置き換えるとうまく行きます。具体的には:

1. Hankel matrixの行たちから、ε行目を含むような基底$r_{w_1},\dots,r_{w_n}\colon \Sigma^\star\to \mathbb{R}$を選ぶ(いまランクはnということにします)。$w_1=\epsilon$ということにしておく。ここで、w行目のことを$r_w$と書いています。
2. initial vector αを$\alpha = (1, 0, \dots, 0) \in \mathbb{R}^n$とし、final vector βを$\beta = (r_{w_1}(\epsilon), r_{w_2}(\epsilon), \dots, r_{w_n}(\epsilon))$とする。⁹
3. 各文字$\sigma \in \Sigma$について、transition matrix$A_\sigma$は次のように定める: 各$i=1,\dots,n$について、$r_{w_i \sigma}$は先に取った基底の線形結合で書けるので(基底ですからね)、$r_{w_i\sigma}=c_{i,1} r_{w_1} + \dots + c_{i,n} r_{w_n}$なる$c_{i,1},\dots,c_{i,n}\in \mathbb{R}$を連立方程式を解くことで求め、$A_\sigma = (c_{i,j})_{i,j}$とする。¹⁰

Balle and Mohriのアルゴリズム

Balle and Mohriのアルゴリズムは先のHankel matrixの有限版を観測表として作り、そこからのWFAの構成をするものです。

観測表からDFAを構成するときの障害はclosedでないことconsistentでないことでしたが、WFAを構成するときの障害は次のようになります。Pは観測表の行集合、Sは列集合です:

$P\cup P\Sigma$行で張られるベクトル空間$\mathbb{R}^{S}$の部分ベクトル空間が、P行で張られるベクトル空間に含まれない。式で書くなら、$P={w_1,\dots,w_n}, \Sigma={\sigma_1,\dots,\sigma_m}$としたとき、
$$\mathbb{span}(\underbrace{r_{w_1},\dots,r_{w_n}}, \underbrace{r_{w_1 \sigma_1},\dots, r_{w_n \sigma_1}},\dots, \underbrace{r_{w_1 \sigma_m},\dots,r_{w_n\sigma_m}}) \not\subset \mathbb{span}(\underbrace{r_{w_1},\dots,r_{w_n}})$$となること。

「1文字分だけ先に進んだらいままでの行から『はみでて』しまった」という意味でclosedでないことと似ていますね。逆に、この障害がのぞかれていて、$P\cup P\sigma$行で張られる部分ベクトル空間が、P行で張られるベクトル空間に含まれることを「complete」と言います。そして、これが成り立つように観測表を拡張していくのがBalle and Mohriのアルゴリズムです。このcompletenessは次のように言い換えることもできます:

観測表を行列としてみたときのランクが、観測表の行に$P\Sigma$を付け加えた表を行列としてみたときのランクと等しい

このほうが計算上の取扱は楽ですね。

で、これが機械学習とどう関係あるの？

詳しく説明するのは、やる気があればまた別の機会にしたいのですが簡単に書いてみます。

2018年のICMLでイスラエルのWeiss¹¹らが「Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples」[6]という論文を発表しました。これは、0/1を返すRNNから、その振舞が似ているようなDFAを構成する論文で、そのためにL*アルゴリズムにRNNの出力を流し込んでいます。Membership queryのほうはRNNの出力を流せばいいのですが、equivalence queryのほうをどうするのかというのが非自明で、このために彼等はequivalence queryの引数として渡されたDFAとRNNとを比較する手法を提案することでL*をRNNに対して適用しています。

これに対し、AAAI20にアクセプトされた奥殿¹²らの「Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces」[1]は、実数を返すRNNからその振舞が似ているようなWFAを構成する論文を類似の手法で実現しています。この際、DFAはconfigurationの空間とその状態とが一対一に対応するので性質が良いのですが、WFAはそうもいかないのでそこをなんとかするためにいろいろやっているのがこの論文です。

さいごに

大遅刻したけどクリスマスには間に合ったのでOKということにします。働きながらAdvent Calendar書ける人ってどうやってるんですか。

メリークリスマス～

追記: 機械学習工学との関係

DFAが数学的にいろいろなオペレーションを備えているためにモデル検査のための基本ツールとなっているように、WFAもDFAほどではないにせよいろいろなオペレーションができます。そこで、[1]のpotentialな応用としては、RNNの近似としてWFAを抽出して、そのWFAに対してモデル検査的な技法を適用することによってもとのRNNの性質を部分的に保証したり検査したりできるのではないかというものがあります。また、抽出したWFAをRNNの振舞をわかりやすく説明したものと捉え、説明可能性(explainability)の方向でも貢献できるのではないかという実験をしています。これらの応用可能性でもって、ニューラルネットでできたシステムの性質を調べるという工学的興味へのアプローチの提案と考えMLSEのアドベントカレンダーに投稿しました。

[1] Takamasa Okudono, Masaki Waga, Taro Sekiyama, Ichiro Hasuo: Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces. CoRR abs/1904.02931 (2019)
[2] Dana Angluin: Learning Regular Sets from Queries and Counterexamples. Inf. Comput. 75(2): 87-106 (1987)
[3] Borja Balle, Mehryar Mohri: Learning Weighted Automata. CAI 2015: 1-21
[4] yabaitech.tokyo: ヤバイテック トーキョー vol.1 https://booth.pm/ja/items/1041379
[5] 新屋 良磨: オートマトン理論再考, コンピュータ ソフトウェア, 2017, 34 巻, 3 号, p. 3_3-3_35 https://doi.org/10.11309/jssst.34.3_3
[6] Gail Weiss, Yoav Goldberg, Eran Yahav: Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples. ICML 2018: 5244-5253

---

1. 「いいから本題の論文を最短で解説しろ！」という方がいるのも知っているのですが、そういうタイプの人はそもそも論文読んだほうが早いと思います。 ↩

2. どう実装されてるかはよくわからないけどとにかく呼び出せて値が帰ってくる関数 ↩

3. χは判別関数で、$\chi_E(w)$はw∈Eのとき1、そうでないとき0です。 ↩

4. 何についての多項式なのというのは自然な問いなんですが、「いやそれでバウンドしてどうすんの」というような変数で押さえてるのであんまり気にしてもしかたない気がします。mとeにアクセスできる前提でできるだけ少ない呼出で言語Lを学習するという認識ぐらいでいいと思います。詳しくは[2]をみてください。 ↩

5. △は対称差(symmetric difference)で、$A\triangle B = (A-B)\cup (B-A)$です。 ↩

6. さらにオートマトンと言語の同値類的に言うと、これはSがあまりに小さすぎて本当は区別しなければいけなかった同値類を混同していた、言語の関係が粗すぎて右不変になっていなかったということになります ↩

7. 本当は一般のsemiringでよいのですが、Balle and Mohriのアルゴリズムは体にしか対応していないので簡単のために実数にしておきます。 ↩

8. 最小WFAというのは、そのweighted languageをあらわすWFAのなかで状態数(上の定義だとd)が最小のものです。DFAと違って、最小WFAの一意性は成立しません。 ↩

9. ベクトルのi番目の要素を$r_{w_i}$と対応させています。 ↩

10. 一応確認はしたんですけど転置だったらごめん ↩

11. 最近Twitterアカウントをみつけました: https://twitter.com/gail_w ↩

12. お気付きかもしれませんが私です ↩