Universal Multiclass Transductive Online Learning

技術的要約：ユニバーサル・マルチクラス・トランズダクティブ・オンライン学習

問題設定
本論文は、可算無限のラベル空間を持つユニバーサル・トランズダクティブ・オンライン分類の問題を調査している。この設定では、学習者は決定論的なゲームにおいて敵対者（アドバーサリ）と対峙する。ゲームが始まる前に、敵対者はインスタンスのシーケンス $X = \{X_t\}_{t \in \mathbb{N}}$ を選択し、その全シーケンスを事前に学習者に開示する。各ラウンド $t$ において、学習者は既知のインスタンス・シーケンスと真のラベルの履歴 $Y_{<t}$ に基づいて、ラベル $\hat{Y}_t$ を予測する。その後、敵対者は真のラベル $Y_t$ を明らかにする。学習者のパフォーマンスは、ミス回数（実現可能設定の場合）、またはリグレット（アグノスティック設定の場合）によって測定される。

核心となる目的は、概念クラス $\mathcal{H}$ のユニバーサル学習可能性を特徴付けることである。特定のデータ・シーケンスに依存しない一様レートとは異なり、ユニバーサル学習可能性は、あらゆる実現可能なシーケンスに対して、ミス回数が時間地平 $T$ に対して劣線形（または特定の境界）で成長するアルゴリズムが存在することを要求する。本論文は、主にバイナリ分類や一様レートに焦点を当ててきた既存の文献におけるギャップを埋めるため、これらの概念を無制限なラベルを持つマルチクラス設定へと拡張することに特化している。

手法と主要概念
著者らは、学習可能性の条件を導出するために、組合せゲーム理論と概念クラスの構造解析を用いている。

1. 組合せ構造:

   • リトルストーン・ツリー (Littlestone Tree): インスタンスをノード、ラベルをエッジとする、オンライン学習における標準的な構造。
   • レベル制約付きリトルストーン (LCL) ツリー: すべてのノードが同じ深さで同じインスタンスを共有するバリエーション。
   • LCL-リトルストーン (LCLL) ツリー: 本研究で導入された新しい構造。これは、無制限なラベルを持つマルチクラス設定へとリトルストーン・ツリーを拡張したものである。LCLLツリーにおいて、深さ $k$ のノードは $k+1$ 個のインスタンスのシーケンスに関連付けられ、エッジは深さ $k+1$ のLCLツリーにおけるパスに対応するラベルのシーケンスを表す。
   • 無関心性 (Indifferent Property): バイナリ分類の研究（Bousquet et al., 2023）から適応された重要な特性。あるツリーが「無関心」であるとは、幅優先探索（BFS）順序においてノード $v$ がノード $u$ よりも前に現れる場合、すべての $u$ の子孫が $v$ のラベルについて一致することを指す。この特性により、学習者がインスタンス・シーケンスを知っている場合でも、敵対者がランダムウォーク戦略を用いてミスを強いることが可能になる。

2. ゲーム理論的アプローチ (Gale-Stewart ゲーム):
   著者らは、学習可能性を特徴付けるために、新しいGale-Stewart ゲームを設計している。インスタンスのシーケンスを提案する従来のゲームとは異り、ここでは敵対者が「レベル制約付きツリー」（インスタンスのシーケンスと、可能なラベル・シーケンスの集合）を提案する。学習者（プレイヤーB）は、概念クラスと矛盾しないパスを選択しようと試みる。

   • このゲームの技術的な主要貢献は、無関心性を捉えるように設計された点にある。著者らは、標準的なバイナリ分類ツリーの拡張（DSLやLCLツリーなど）が、無制限なマルチクラス設定において学習可能性を特徴付けるには不十分であることを示している。なぜなら、この文脈では無限ツリーにおいて「無関心」な特性が自動的には成立しないからである。
   • 著者らは、概念クラスが無限の無関心なLCLLツリーを持たない場合、学習者（プレイヤーB）に勝利戦略が存在することを確立するために、ボレル決定性定理 (Borel Determinacy Theorem) を利用している。

3. アルゴリズム設計:

   • 実現可能設定 (Realizable Setting): 著者らは、Gale-Stewart ゲームの進捗を追跡するアルゴリズムを提案している。ゲームが進展する場合（破砕された部分シーケンスの存在を示す）、アルゴリズムは状態を更新する。ゲームが停滞する場合、アルゴリズムは、破砕された部分シーケンスに基づく重み関数を用いた加重多数決戦略に切り替え、残りの部分的な概念クラスを学習する。
   • アグノスティック設定 (Agnostic Setting): 著者らは、「エキスパートを用いた学習」の枠組みを用いて実現可能アルゴリズムを拡張している。彼らは、幻覚された（hallucinated）シーケンスとミス・インデックスに基づく実現可能アルゴリズムの挙動に基づき、可算なエキスパート集合を構築し、非一様な初期重みを用いてSquint アルゴリズム (Koolen & van Erven, 2015) を用いてリグレットを最小化する。

主要な結果

1. 実現可能設定における三分論 (Trichotomy):
   本論文は、無制限なラベルを持つユニバーサル・トランズダクティブ・オンライン学習の最適なミス率に関する三分論を確立している：

   • 定数回のミス ($O(1)$): $\mathcal{H}$ が無限の無関心なリトルストーン・ツリーを持たない場合に達成可能。
   • 対数的なミス ($\Theta(\log T)$): $\mathcal{H}$ が無限の無関心なリトルストーン・ツリーを持つが、無限の無関心なLCLLツリーを持たない場合に達成可能。
   • 線形なミス ($\Omega(T)$): $\mathcal{H}$ が無限の無関心なLCLLツリーを持つ場合、ミスを劣線形に抑えるアルゴリズムは存在しない。

2. アグノスティック設定:

   • 概念クラス $\mathcal{H}$ がアグノスティックにユニバーサル・トランズダクティブ・オンライン学習可能であるための必要十分条件は、それが無限の無関心なLCLLツリーを持たないことである。
   • このようなクラスに対して、著者らは、幻覚されたシーケンスとミス・インデックスに基づく挙動を用いて、$\tilde{O}(\sqrt{T})$ のリグレット境界（多項式対数因子を隠蔽）を達成するアルゴリズムを提供する。
   • 少なくとも2つの異なる概念を含む任意のクラスにおいて、リグレットは $o(\sqrt{T})$ にはならないという下界が証明されている。

3. 確率過程への拡張:
   結果は、学習者がインスタンス・シーケンスそのものではなく、そのインスタンス・シーケンスを生成する確率過程のみを知っている設定へと拡張される。「すべてのプロセスがユニバーサル・オンライン学習を許容する」ための条件は、無限の無関心なLCLLツリーの不在と等価であることが示されている。

意義と主張
本論文は、オンライン学習理論におけるいくつかの重要な貢献を主張している：

• マルチクラス無制限ケースの解決: 無制限な可算ラベル空間を持つマルチクラス問題に対する、ユニバーサル・トランズダクティブ・オンライン学習の最初の完全な特徴付けを提供し、バイナリ中心または有限ラベルの研究による空白を埋めた。
• 新しい組合せ的特徴付け: この設定における正しい特徴付けとして、レベル制約付きリトルストーン・リトルストーン (LCLL) ツリーと無関心性を導入した。著者らは、以前の候補（DSLツリー、LCLツリー、または標準的なリトルストーン・ツリー）は不十分であることを明示的に述べている。これは、あるクラスが無限のLCLLツリーを持ちながらも学習可能であるケースや、無限のリトルストーン・ツリーを持ちながらも下界に必要な無関心性を欠くケースといった反例によって示されている。
• 新しいゲーム設計: インスタンスだけでなく、インスタンスの区間に対するラベル・シーケンスを敵対者が提案するという、特定のGale-Stewart ゲームの設計を強調している。この設計は、標準的なゲーム構造では捉えきれない無関心性を捉えるために必要な、概念的な貢献として提示されている。
• 楽観的ユニバーサル学習: 本研究は、トランズダクティブな学習可能性を、より広範な「楽観的ユニバーサル・オンライン学習」（学習が可能である限り学習を行うこと）の問題へと結びつけている。インスタンス・シーケンスを知ること（トランズダクティブ）と、確率過程を知ること（楽観的）が、LCLLツリー構造によって定義される同一の学習可能性条件に帰着することを明らかにしている。

著者らはアグノスティック設定に関して謙虚な姿勢を保っており、上界（$\tilde{O}(\sqrt{T})$）と下界（$\Omega(\sqrt{T})$）の間の多項式対数的なギャップを認め、そのギャップを狭めることを今後の課題としている。また、無制限なラベルを持つプロセスに対するユニバーサル・オンライン学習の特徴付けは、未解決の問題であると特定している。