makenowjust-labs/blog

計算機科学の分野において nominal set や nominal logic に現れる "nominal" は「名前の具体的な値を切り捨て、置換と有限supportによって構造を記述する方法」を表します。 nominalアプローチを用いると、例えばα変換を群論の言葉 (群作用など) を使って非常に見通しよく定義できます。

この意味で使われる "nominal" には今のところ定まった訳はありませんが、J-GLOBALでは『名目』および『公称』として訳されているようです (ソース1、ソース2)。 しかし、これらの訳はいくつかの理由 (「名前に関する」という意味が弱い、など) から、nominalの訳語としてはベストなものとは言い難いと考えられます。

そこで、本記事では「置換と有限supportによる構造を記述する方法」の "nominal" の訳語として、統計学の名義尺度 (nominal scale) を参考にした『名義』という訳を提案したいと思います。

有限状態オートマトンの一種にSymbolic Finite Automata (SFA)と呼ばれるものがあります。 これは遷移が文字ではなく条件式でラベル付けされるオートマトンで、現実世界でSFAを使うことで効率的に表現できる例があることから、研究が進められています。

SFAに対するオートマトン学習アルゴリズムとして、$\Lambda*$と$\mathrm{MAT}*$が知られています。 どちらも既存のオートマトン学習のアルゴリズムをベースとしてSFAに拡張したものですが、学習に用いるデータ構造の特徴を上手く利用した興味深いものになっています。

この記事ではまずSFAの定義を確認し、そのあとに$\Lambda*$と$\mathrm{MAT}*$について解説します。

想定読者: オートマトン学習について知識・関心がある方。

Angluinの$L^\ast$は、オートマトン学習の代表的なアルゴリズムです。 本ブログでも度々紹介してきました。

• https://makenowjust-labs.github.io/blog/post/2023-07-19-lstar/
• https://makenowjust-labs.github.io/blog/post/2024-07-22-lstar-variants/

今回、この$L^\ast$の動作を可視化するツールlstar-vizを実装しました。 この記事では、ツールの使い方や、ツールを作るにあたって用いた技術について紹介します。

想定読者: $L^\ast$アルゴリズムやフロントエンドの技術に興味がある方

$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$ の様々な効率が改善できます。

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