認識可能列の代数と応用

認識可能列 (recognizable series)の定義

$S$ を半環、 $\Sigma$ を有限アルファベットとする。$\Sigma^*$ から $S$ への関数の集合を $S\langle\!\langle\Sigma^*\rangle\!\rangle$ と表す。$S\langle\!\langle\Sigma^*\rangle\!\rangle$ の元を 列 という。

定義.
列 $f\in S\langle\!\langle\Sigma^*\rangle\!\rangle$ について、ある正の整数 $n$ と $\lambda\in S^{1\times n}$, $\mu\colon \Sigma\to S^{n\times n}$, $\gamma\in S^{n\times 1}$ が存在し、

$$
f(w) = \lambda \,\mu(w_1)\mu(w_2)\dotsm \mu(w_{|w|})\,\gamma\qquad\forall w\in\Sigma^*
$$

が成り立つとき(積は行列積)、$f$ を 認識可能列 (recognizable series) という。
また、このような $(\lambda,\mu,\gamma)$ を $f$ の 線形表現 という。
認識可能列の集合を $S^{\mathrm{rec}}\langle\!\langle\Sigma^*\rangle\!\rangle$ と表す。

この分野では $f(w)$ と表す代わりに $(f, w)$ と表すことが一般的である。

線形表現の学習

$S$ を体とすると、$f\colon\,\Sigma^*\to S$ にオラクルアクセスすることで $f$ の線形表現を学習することができる。この章だけ独立した内容なので読み飛ばしてもよい。素朴な線形代数なので、特筆するような内容はない。

$$
S^{\Sigma^*}:= \Sigma^*\to S\text{ が貼る $S$ 上の線形空間}
$$

とする。
$f$ が $n$次元線形表現を持つとき、 $S^{\Sigma^*}$ の部分空間

\begin{align*}
V_{\mathrm{left}} &:= \mathrm{span}\bigl\{b\longmapsto f(ab))\mid a\in\Sigma^*\bigr\}
\end{align*}

の次元は高々 $n$ となる。
$V_\text{left}$ の基底を発見して、その基底のもとでベクトル、行列表現を導出すればよい。具体的な方法として、まず $(a,b)$ 成分が $f(ab)$ である行列 $M$ を構築する。考える $a$ と $b$ の文字列長は $n$ 以下で十分である。実用的には $n$ は未知であることが多いので、ある程度大きく取る必要がある。実際は線形表現の次元 $n$ とは別に「深さ」というパラメータを導入して、深さ以下の長さの文字列 $a,b$ を使って行列 $M$ を作るとよい。深さは $n$ 以下であるが、そのギャップが大きい場合もある。適当な深さを設定して学習するとよい。

$M$ のランクは高々 $n$ である。 $M$ の正則部分行列でランクが $M$ のランクに等しいもの $U=M_{A,B}$ を発見する。この時に選択した行集合 $A$ が $V_\text{left}$ の基底に対応する。また、この時に選択した列集合 $B$ は

\begin{align*}
V_{\mathrm{right}} &:= \mathrm{span}\bigl\{a\longmapsto f(ab))\mid b\in\Sigma^*\bigr\}
\end{align*}

の基底に対応する。二種類の基底が得られたので、これらの基底に基づく行列表現

\mu'(c)_{a,b} = f(a c b)\qquad\forall a\in A, b\in B, c\in\Sigma

が得られる。行側の基底と列側の基底を列側に揃えることにする(行側でもよい)。
$A$ と $B$ は空文字列 $\epsilon$ を含むように選んで、0行目と0列目に対応させると、

\begin{align*}
\lambda &=\text{$U$ の $0$ 行目}&
\mu(c) &= U^{-1}\mu'(c)&
\gamma &=\begin{bmatrix}1\\0\\\vdots\\0\end{bmatrix}
\end{align*}

という線形表現が得られる。

実際の実装としては $M$ を陽に作らずに深さを右の文字列にだけ設定して、 $V_\text{left}$ の基底 $A$ を幅優先探索で探すとよい。

認識可能列上の演算

この章では $S$ と $\Sigma$ を固定し、認識可能列上の演算を定義する。この章の内容は

Manfred Droste and Dietrich Kuske,
Weighted Automata,
Handbook of Automata Theory. Vol. I. Theoretical foundations, 113–150. EMS Press, Berlin, 2021.

を参考にした。
任意の $w\in\Sigma^*$ について $1_w\in S\langle\!\langle\Sigma^*\rangle\!\rangle$ を

\begin{align*}
1_w(w) &= 1\\
1_w(v) &= 0\qquad \forall v\in\Sigma^*
\end{align*}

と定義する。任意の $a\in S$ と $w\in\Sigma^*$ について、$a1_w$ を 単項式 という。

和

$S\langle\!\langle\Sigma^*\rangle\!\rangle$ 上に和を以下で定義する。

$$
(f+g)(w) := f(w) + g(w).
$$

認識可能列は和について閉じている。
$(\lambda_0,\mu_0,\gamma_0)$ と $(\lambda_1,\mu_1,\gamma_1)$ がそれぞれ $f$ と $g$ の線形表現であるとき、直和 $(\lambda_0\oplus\lambda_1,\mu_0\oplus\mu_1,\gamma_0\oplus\gamma_1)$ は $f+g$ の線形表現になる。つまり

\begin{align*}
\lambda&=\begin{bmatrix}\lambda_0&\lambda_1\end{bmatrix},&
\mu(c)&=\begin{bmatrix}\mu_0(c)&0\\0&\mu_1(c)\end{bmatrix},&
\gamma&=\begin{bmatrix}\gamma_0\\\gamma_1\end{bmatrix}
\end{align*}

について $(\lambda,\mu,\gamma)$ は $f+g$ の線形表現。
$f$ と $g$ の最小の表現から構成した上記の線形表現が最小の表現とは限らない。例えば $f+(-f)=0$。

アダマール積

$S\langle\!\langle\Sigma^*\rangle\!\rangle$ 上にアダマール積を以下で定義する。

$$
(f\odot g)(w) := f(w) g(w).
$$

半環 $S$ が可換であるとき、認識可能列はアダマール積について閉じている。
$(\lambda_0,\mu_0,\gamma_0)$ と $(\lambda_1,\mu_1,\gamma_1)$ がそれぞれ $f$ と $g$ の線形表現であるとき、テンソル積(クロネッカー積) $(\lambda_0\otimes\lambda_1,\mu_0\otimes\mu_1,\gamma_0\otimes\gamma_1)$ は $f\odot g$ の線形表現になる。
$f$ と $g$ の最小の表現から構成した上記の線形表現が最小の表現とは限らない。例えば $f(w)\in\{0,1\}$ である $f$ について $f\odot f=f$。

コーシー積

$S\langle\!\langle\Sigma^*\rangle\!\rangle$ 上にコーシー積を以下で定義する。

$$
(f\cdot g)(w) := \sum_{u,\,v\in\Sigma^*\colon\, uv=w} f(u) g(v).
$$

これはある種の畳み込みなので、形式的冪級数(というか群環というかモノイド半環)の積

\begin{align*}
\left(\sum_{u\in\Sigma^*}f(u) x^u\right)
\left(\sum_{v\in\Sigma^*}g(v) x^v\right)
&=
\sum_{u,\,v\in\Sigma^*}f(u)g(v) x^{uv}\\
&=
\sum_{w\in\Sigma^*}\left(\sum_{u,\,v\in\Sigma^*\colon\,uv=w}f(u)g(v)\right) x^{w}\\
&=\sum_{w\in\Sigma^*} (f\cdot g)(w) x^w
\end{align*}

と考えると理解しやすい。
認識可能列はコーシー積について閉じている。

$(\lambda_0,\mu_0,\gamma_0)$ と $(\lambda_1,\mu_1,\gamma_1)$ がそれぞれ $f$ と $g$ の線形表現であるとき

\begin{align*}
\lambda&=\begin{bmatrix}\lambda_0&0\end{bmatrix},&
\mu(c)&=\begin{bmatrix}\mu_0(c)&\gamma_0\lambda_1\mu_1(c)\\0&\mu_1(c)\end{bmatrix},&
\gamma&=\begin{bmatrix}\gamma_0(\lambda_1\gamma_1)\\\gamma_1\end{bmatrix}
\end{align*}

について $(\lambda,\mu,\gamma)$ は $f\cdot g$ の線形表現。半環の積が非可換でも成り立つ。

証明:

$|w|$ に関する帰納法で証明する。

\lambda \cdot \gamma = (\lambda_0\gamma_0)(\lambda_1\gamma_1) = f(\epsilon)g(\epsilon) = (f\cdot g)(\epsilon)

である。また

\begin{align*}
&\lambda \,\mu(w_1)\mu(w_2)\dotsm \mu(w_{|w|})\,\gamma\\
&=
\lambda \,\mu(w_1)\mu(w_2)\dotsm \mu(w_{|w|})\,\begin{bmatrix}\gamma_0g(\epsilon)\\\gamma_1\end{bmatrix}\\
&=
\lambda \,\mu(w_1)\mu(w_2)\dotsm \mu(w_{|w|})\,\left(\begin{bmatrix}\gamma_0\\0\end{bmatrix}g(\epsilon)+\begin{bmatrix}0\\\gamma_1\end{bmatrix}\right)\\
&=f(w)g(\epsilon)+
\lambda \,\mu(w_1)\mu(w_2)\dotsm \mu(w_{|w|-1})\,\begin{bmatrix}\gamma_0\lambda_1\mu_1(w_{|w|})\gamma_1\\\mu_1(w_{|w|})\gamma_1\end{bmatrix}\\
&=f(w)g(\epsilon) + (f\cdot g')(w_1\dotsm w_{|w|-1}) \qquad (g'(v) := g(vw_{|w|}))\\
&=(f\cdot g)(w).
\end{align*}

であることから示された。

クリーネのスター

コーシー積を用いて $n\in\mathbb{Z}_{\ge 0}$ について

$$f^n:=\overbrace{f\cdot f \cdot\dotsm \cdot f}^{n}$$

と定義する。ただし $f^0 = 1_\epsilon$ である(これはコーシー積の単位元である)。
認識可能列 $f$ が $f(\epsilon)=0$ を満たすとき、

$$
f^* := \sum_{n\ge 0} f^n
$$

が定義できる。任意の $w\in\Sigma^*$について $f^m(w)=0$ が $m>|w|$ について成り立つため、

$$
f^*(w) = \sum_{n=0}^{|w|} f^n(w)
$$

と右辺が有限和になり定義できていることが分かる。

$f$ が $f(\epsilon)=0$ を満たす認識可能列であるとき、$f^*$ も認識可能列である。
$(\lambda,\mu,\gamma)$ が $f$ の線形表現であるとき、

$$
\mu'(c) := \mu(c) + \gamma\lambda \mu(c)
$$

について $(\lambda,\mu',\gamma)$ は $f^* - 1_\epsilon$ の線形表現となる。$1_\epsilon$ は認識可能であり、認識可能列の和は認識可能列なので、$f^*$ は認識可能列である。

Kleene–Schützenberger の定理

定義.
$S\langle\!\langle\Sigma^*\rangle\!\rangle$ の部分集合で、すべての単項式を含み、和、コーシー積、クリーネのスターに閉じた最小の集合を $S^{\mathrm{rat}}\langle\!\langle\Sigma^*\rangle\!\rangle$ と表す。

単項式が認識可能列であることと、認識可能列がこれらの演算に閉じていることから

$$S^{\mathrm{rec}}\langle\!\langle\Sigma^*\rangle\!\rangle \supseteq S^{\mathrm{rat}}\langle\!\langle\Sigma^*\rangle\!\rangle.$$

が分かる。また実際には逆の包含関係も成り立つ。

Kleene–Schützenberger の定理.
$$S^{\mathrm{rec}}\langle\!\langle\Sigma^*\rangle\!\rangle = S^{\mathrm{rat}}\langle\!\langle\Sigma^*\rangle\!\rangle.$$

組合せ数え上げへの応用

正規言語 $L\subseteq\Sigma^*$ について、それを認識する有限オートマトンが存在する。よって $0\ne 1$ である任意の半環 $S$ 上で $1_L(w) = \mathbb{I}\{w\in L\}$ は認識可能列である。

正規言語 $L_1,\,L_2\subseteq\Sigma^*$ について、

$$
1_{L_1\cap L_2} = 1_{L_1}\odot 1_{L_2}
$$

である。よって $L_1$ と $L_2$ を認識する線形表現を持っていれば、$L_1\cap L_2$ に対する線形表現もアダマール積を計算することで得られる。

また、$L_1\cap L_2=\varnothing$ のとき、

$$
1_{L_1\cup L_2} = 1_{L_1}+ 1_{L_2}
$$

である。よって $L_1$ と $L_2$ を認識する線形表現を持っていれば、disjoint union $L_1\cup L_2$ に対する線形表現も和を計算することで得られる。
同様にコーシー積やクリーネのスターは正規言語の結合やクリーネ閉包に対応する。

さらに、 プレフィックス和

$$
f_{\mathrm{prefix}}(w) := \sum_{p\colon \text{ prefix of } w} f(p)
$$

はコーシー積を使うことで $f_{\mathrm{prefix}} = f \cdot 1$ と分解することができる。同様に $f_{\mathrm{suffix}}$ を定義すると $f_{\mathrm{suffix}} = 1\cdot f$ である。また、連続部分文字列に関する和

$$
f_{\mathrm{substr}}(w) := \sum_{s\colon \text{ substring of } w} f(s)
$$

は $f_{\mathrm{substr}}=1\cdot f\cdot 1$ である。よって、 $1_L$ の線形表現を持っていれば、連続部分文字列和に対する線形表現もコーシー積を計算することで得られる。

以上のことから、 $f_{\mathrm{substr}}$ の線形表現を直接学習しなくても、$f$ の線形表現を学習すればコーシー積を計算することで $f_{\mathrm{substr}}$ の線形表現が得られる。

実装例

オートマトンとの比較

正規言語 $L\subseteq\Sigma^*$ について、 $1_L$ の線形表現の特別な場合として決定性オートマトンがある。決定性オートマトンも線形表現と似たような方法で学習することができる($M$の線形独立な行を選ぶ代わりに相異なる行を選ぶ)。線形表現はオートマトン表現より遥かに次元が小さくなる場合もあるので上位互換のように思える。以下ではオートマトン表現から簡単に計算できるが、線形表現からは自明に計算できないものについて解説する。

正規言語 $L\subseteq\Sigma^*$ について

\text{Longest}_L(w) := \max_{s:\,\text{substring of } w} \{|s|: s\in L\}

と定義する。 $L$ のオートマトン表現を持っているとき、適当な動的計画法で上記の $\text{Longest}_L$ を計算できる。一方で $1_L$ の体 $S$ 上の線形表現から同様のアルゴリズムを考えることはできない(非零要素の和が零になることがあるため)。

この場合に $1_L$ の線形表現に基づいて $\text{Longest}_L$ を計算する方法を考える。まず、$1_{L,\,\text{prefix}}=1_L\cdot 1$ の線形表現を計算する。この $1_{L,\,\text{prefix}}$ を用いて

\text{Longest}_L(w) = \max_{0\le i\le j\le |w|-1} \biggl\{j-i+1: 1_{L,\,\text{prefix}}(w_{[i,\,j)}) < 1_{L,\,\text{prefix}}(w_{[i,\,|w|)})\biggr\}

と表すことができる。
ここで、$h(i,\,j):=1_{L,\,\text{prefix}}(w_{[i,\,j)})$ が計算時間 $T$ で計算できるとする。固定した $i$ について $j$ を大きくしていくことによって、 $i$ 番目から始まる部分文字列で $L$ に入る最長のものを計算できる。それが得られたら区間を一つ右にずらして $i+1$ 番目から始まる部分文字列で $L$ に入る最長のものを計算する(ただし、今まで得られた区間より短いものには興味がない)。この計算において $h$ にクエリされる区間の始点と終点は単調に大きくなる。
こういった考察からSWAGと呼ばれるデータ構造を用いると、$O(|w|)$ 回の行列積の計算で $\text{Longest}_L(w)$ が得られる(はずであるが実装による確認はしていない)。