makenowjust-labs/blog

$L^\#$ というオートマトン学習のアルゴリズムがあります。

2022年にVaandragerらによって提案された、最新のオートマトン学習のアルゴリズムです。 apartness relationという概念を用いて、よく知られているAngluinの $L^\ast$ とは少し違ったアイディアでオートマトンの学習を実現します。 学習に用いるデータ構造として、従来のobservation tableやdiscrimination treeではなく、observation treeというmembership query (output query) のキャッシュのようなものを利用するのも特徴です。

この記事では $L^\#$ の詳細や実装について、論文 [Vaandrager et al., 2022] を参考に解説します。

想定読者: オートマトン理論やオートマトン学習について理解・関心がある。

Angluinの $L^\ast$ はオートマトン学習 (automata learning) のアルゴリズムとして最も有名なものです。 以前、このブログでもAngluinの $L^\ast$ について説明しました。

$L^\ast$ は歴史のあるアルゴリズムのため、派生アルゴリズムがいくつか存在します。 この記事ではAngluinの $L^\ast$ について簡単に説明した上で、派生アルゴリズムとしてRivest-SchapireとKearns-Vaziraniを紹介します。

• Rivest-Schapireは $L^\ast$ の反例 (counterexample) の解析手法の提案で、二分探索を用いて反例の中のobservation tableに追加すべき接頭辞を探すことで、計算量を改善します。
• Kearns-Vaziraniはobservation tableを置き換えるデータ構造としてdiscrimination treeというデータ構造を提案するものです。

これらの手法により $L^\ast$ の様々な効率が改善できます。

想定読者: オートマトン理論やオートマトン学習について理解・関心がある。

Automata Learning とは、未知の (ブラックボックス) システムに対する入力とその出力から、システムの振舞いを有限状態オートマトンとして再現する手法です。 これは、仕様が形式化されていないシステムに対して形式的な手法を適用するための足掛りになるなど、近年重要な技術となっています。

Angluin による$L\ast$は Automata Learning のアルゴリズムの中でも最も代表的な存在です。 $L\ast$は未知の正規言語を教師を使って学習するアルゴリズムで、多くの Automata Learning の基礎となっています。

この記事では$L\ast$の、その原理やアルゴリズムの詳細について解説します。