2025-11-19T16:52:14.243866

Learning Weighted Automata over Number Rings, Concretely and Categorically

Aristote, van Gool, Petrişan et al.
We develop a generic reduction procedure for active learning problems. Our approach is inspired by a recent polynomial-time reduction of the exact learning problem for weighted automata over integers to that for weighted automata over rationals (Buna-Marginean et al. 2024). Our procedure improves the efficiency of a category-theoretic automata learning algorithm, and poses new questions about the complexity of its implementation when instantiated to concrete categories. As our second main contribution, we address these complexity aspects in the concrete setting of learning weighted automata over number rings, that is, rings of integers in an algebraic number field. Assuming a full representation of a number ring OK, we obtain an exact learning algorithm of OK-weighted automata that runs in polynomial time in the size of the target automaton, the logarithm of the length of the longest counterexample, the degree of the number field, and the logarithm of its discriminant. Our algorithm produces an automaton that has at most one more state than the minimal one, and we prove that doing better requires solving the principal ideal problem, for which the best currently known algorithm is in quantum polynomial time.
academic

数環上の加重オートマタ学習：具体的かつ圏論的アプローチ

基本情報

  • 論文ID: 2504.16596
  • タイトル: Learning Weighted Automata over Number Rings, Concretely and Categorically
  • 著者: Quentin Aristote, Sam van Gool, Daniela Petrişan, Mahsa Shirmohammadi
  • 分類: cs.FL（形式言語とオートマタ理論）
  • 発表日: 2025年4月23日（arXiv プレプリント）
  • 論文リンク: https://arxiv.org/abs/2504.16596

要約

本論文は、汎用的な能動学習問題の帰約手続きを開発している。この手法は、Buna-Marginean等（2024）による整数上の加重オートマタの精密学習問題を有理数上の加重オートマタ学習問題に多項式時間で帰約する最近の研究に着想を得ている。本手続きは圏論的オートマタ学習アルゴリズムの効率を向上させ、具体的な圏インスタンス化時に実装複雑性に関する新たな問題を提起する。第二の主要な貢献として、著者らは数環（代数数体における整数環）上の加重オートマタ学習の具体的設定におけるこれらの複雑性問題を解決している。数環O_Kの完全な表現を仮定すると、O_K-加重オートマタの精密学習アルゴリズムが得られ、このアルゴリズムは目標オートマタのサイズ、最長反例長の対数、数体の次数、および判別式の対数に関して多項式時間複雑性を有する。アルゴリズムが生成するオートマタは最小オートマタより最大で1状態多く、より良い結果を得るには主理想問題を解く必要があることが証明され、現在既知の最良アルゴリズムは量子多項式時間である。

研究背景と動機

問題背景

  1. 古典的オートマタ学習: Angluinの L* アルゴリズムは、最小充分教師（MAT）フレームワークの下で決定性有限状態オートマタを効率的に学習する。これは計算学習理論の古典的結果である。
  2. 加重オートマタ学習の課題: 学習アルゴリズムをより表現力の高いモデル（加重オートマタなど）に拡張することは課題であり、特に重みが体ではなく環にある場合に困難である。
  3. 既存手法の限界:
    • 体上の加重オートマタについては多項式時間学習アルゴリズムが存在する
    • 一般的な環上の加重オートマタについては、既存手法は複雑度が高すぎるか適用範囲が限定的である
    • 圏論的手法は汎用的だが、具体的実装時に指数複雑度をもたらす可能性がある

研究動機

  1. 理論的必要性: 圏論的手法の汎用性を保ちながら、具体的な場合に多項式複雑度を有するフレームワークが必要である
  2. 実用的応用: 数環は暗号学などの分野で重要な応用を有し、その上の加重オートマタの効率的学習は実用的価値がある
  3. 理論的境界: 加重オートマタ最小化の理論的極限、特にFatou性質の一般化を探索する

核心的貢献

  1. 汎用帰約アルゴリズム: Algorithm 3を提案。これは圏論フレームワークにおける汎用帰約手続きで、ある学習問題クラスをより扱いやすい学習問題クラスに帰約する
  2. 数環上の具体的アルゴリズム: Algorithm 4を開発。数環O_K上の加重オートマタの多項式時間学習アルゴリズムを特に対象とする
  3. ほぼ最適性結果: アルゴリズムが生成するオートマタは最小オートマタより最大で1状態多いことを証明（ほぼ最小性）
  4. 理論的複雑度境界: 完全に最小なオートマタを得ることは主理想問題（PIP-hard）を解くことと等価であることを証明し、問題の理論的下界を確立する
  5. Fatou性質の一般化: Dedekind域が「ほぼ強Fatou環」であることを証明し、古典的Fatou性質を一般化する

方法の詳細

タスク定義

入力: 未知のO_K-加重言語 L: Σ* → O_K（オラクルアクセス経由） 出力: L を計算するO_K-加重オートマタ 制約: アルゴリズム複雑度は目標オートマタサイズ、最長反例長の対数、数体の次数、判別式の対数の多項式

核心的技術フレームワーク

1. 圏論的基礎

論文は関手的視点を採用し、オートマタを関手 A: I → C として見なす。ここで：

  • I は字母表Σで生成される自由圏
  • C は出力圏（例：加群圏 Mod_R）

2. 汎用帰約アルゴリズム（Algorithm 3）

アルゴリズムの考え方：
1. 「扱いやすい」圏Dでオートマタを学習する
2. 関手 F: C → D により関連付ける
3. 右伴随 G: D → C を使用して結果を目標圏Cに引き戻す

主要な仮定（Assumption 12）:

  • F は特定の射クラスを保存する
  • F は右伴随を有する
  • 単位と余単位の射が特定の性質を有する

3. 数環上の具体的実装（Algorithm 4）

ステップ1: 後向共役化

オートマタAの後向空間の基Bを計算する
行列Bによる共役を通じてAからA'を得る

ステップ2: 前向加群生成

Algorithm 5を呼び出してA'の前向O_K-加群の生成集合を計算する
二段階戦略を使用：
- 第一段階：Kで秩を増加させる語を見つける
- 第二段階：O_Kで加群の生成を完成させる

ステップ3: 疑似基計算

疑似Hermite標準形（pseudo-HNF）を使用して生成集合から疑似基を計算する
疑似基の形式：{(a_i, v_i) | 1 ≤ i ≤ ℓ}、ここでa_iは分数イデアル

ステップ4: ほぼ最小生成集合

Algorithm 6を通じて疑似基をサイズ最大ℓ+1の生成集合に変換する
イデアル因子精密化と中国剰余定理を使用する

技術的革新点

  1. 二段階生成戦略: 先に体Kで秩を決定し、その後環O_Kで加群構造を完成させることで、指数複雑度を回避する
  2. 疑似基技術: Dedekind域の構造理論を利用し、疑似基を通じて非主理想域の場合を処理する
  3. 圏論と具体的アルゴリズムの結合: 抽象的な圏論フレームワークを実装可能な多項式アルゴリズムに具体化する

実験設定

理論的検証

本論文は主に理論的研究であり、以下の方法により検証される：

  1. 複雑度分析: Algorithm 4 と Algorithm 5 の時間複雑度を詳細に分析する
  2. 正当性証明: Theorem 18 を通じて汎用アルゴリズムの正当性を証明する
  3. 具体例検証: Zi√5上の状況を説明する具体例（Example 1など）を提供する

複雑度界限

定理2: O_Kの完全な表現が与えられたとき、O_K-加重オートマタの精密学習は以下のパラメータの多項式時間内で解決可能である：

  • 目標オートマタのサイズ
  • 最長反例長の対数
  • 数体の次数 d
  • 判別式Δ_Kの対数

実験結果

主要な理論的結果

  1. ほぼ最適性（Proposition 10）: Dedekind域Rに対して、秩nのR-加重言語Lが存在すれば、Lを計算する最大n+1状態のR-加重オートマタが存在する
  2. 複雑度下界（Proposition 26）: O_K-加重オートマタが状態最小であるかどうかを判定することはPIP-困難である
  3. Fatou性質の一般化（Corollary 16）: Dedekind域はほぼ強Fatou環である

具体的例の分析

Example 1: 数環 R = Zi√5 において：

  • 3状態のR-加重オートマタを構築する
  • 等価な2状態のK-加重オートマタが存在する（K = Q(i√5)）
  • 強Fatou性質は常に成立するわけではないが、ほぼ強Fatou性質は成立することを示す

関連研究

古典的オートマタ学習

  • Angluinの L* アルゴリズム：決定性有限オートマタの多項式学習
  • Beimel等：体上の加重オートマタの学習アルゴリズム

環上の加重オートマタ

  • van Heerdt等：主理想域上の学習、ただし複雑度界限なし
  • Buna-Marginean等：ZからQへの帰約、本論文の直接的な着想源

圏論的手法

  • Colcombet-Petrişan：オートマタ最小化の関手的手法
  • Urbat-Schröder等：学習の代数的手法

結論と考察

主要な結論

  1. 数環上の加重オートマタ学習の初の多項式時間アルゴリズムを開発した
  2. 完全に最小なオートマタを得ることの困難性（PIP-hard）を証明した
  3. 圏論と具体的アルゴリズムの間に橋渡しを確立した

限界

  1. 表現要件: 数環O_Kの「完全な表現」が必要であり、これは実践では得難い可能性がある
  2. ほぼ最適性: アルゴリズムが生成するオートマタは最小のものより1状態多い可能性がある
  3. 特定の構造: 手法はDedekind域に特化しており、一般的な環への推広は明確でない

今後の方向性

  1. 他の環クラス: 非Dedekind域への推広を研究する
  2. 実装: 具体的なソフトウェア実装と実験的検証を開発する
  3. 応用探索: 暗号学などの分野における具体的応用

深層的評価

利点

  1. 理論的深さ: 圏論、代数数論、計算複雑性理論を巧妙に結合している
  2. 技術的革新: 二段階学習戦略と疑似基技術の使用は創意的である
  3. 完全性: アルゴリズムと下界の両方を提供し、問題の完全な図景を示す
  4. 厳密性: 数学的証明は厳密で、複雑度分析は詳細である

不足点

  1. 実用性: 実装と実験的検証が欠けている
  2. 可読性: 非専門家にとって圏論の部分は理解が難しい可能性がある
  3. 適用範囲: 手法の適用性は特定の代数構造に限定される

影響力

  1. 理論的貢献: 加重オートマタ学習理論に重要な貢献をしている
  2. 方法論: 抽象的な圏論的手法を具体化する方法を示す
  3. 学際的: オートマタ理論、代数数論、計算複雑性を結びつける

適用場面

  1. 暗号学: 格暗号学における数環の応用
  2. 記号計算: 代数数体上の計算問題
  3. 理論研究: さらなるオートマタ学習研究の基礎を提供する

技術的詳細の補足

数環の表現

論文が要求するO_Kの「完全な表現」には以下が含まれる：

  • 積分基 Ω = {ω₁,...,ωₐ}
  • 原始元素θとその最小多項式
  • 複雑度尺度 C_K = d⁴(log d + log Δ_K)

アルゴリズム複雑度

主要な複雑度界限は以下から生じる：

  • 疑似HNF計算：多項式時間（Biasse-Fieker-Hofmann）
  • 厳密増加鎖の長さ：Lemma 24により log(N(d)) で界定される
  • イデアル操作：C_K 内で多項式時間

本論文は理論計算機科学分野、特にオートマタ学習と代数計算の交差領域において重要な貢献をしている。実用性の検証は今後の課題だが、その理論的価値と方法論的意義は顕著である。