Two Dimensions Govern Agnostic Multiclass Transductive Learning

機械学習の世界では、コンピュータは例題を研究することによって予測を行う方法を学びます。テスト問題の答えを推測しようとしている学生を想像してみてください。標準的な学習方法である「PAC学習」では、学生はフラッシュカードのセットを使って練習し、その後、新しい、未知のカードに対してテストを受けます。目標は、多くの可能なテストにおいて平均的に優れたパフォーマンスを発揮することです。しかし、そこには「トランスダクティブ学習（誘導的学習）」と呼ばれる、より特定の学習方法があります。ここでは、学生にはすべての問題を含むテスト用紙が事前に与えられますが、たった一つの特定の質問に対する答えだけが隠されています。学生は他のすべての答えを見て、その欠落した一つの答えを予測しなければなりません。この設定は、平均的なパフォーマンスに頼ることができないため、より厳格なものです。

「はい」か「いいえ」のような、わずか2つの答えしかない単純な問題については、これら2つの学習方法は、成功するために必要なデータ量の観点から本質的に同じであることが長年知られてきました。しかし、答えが多数の可能性を持つ場合（例えば、数千種類の鳥の種を特定したり、数百種類の疾患を診断したりする場合）、ルールは変わります。このような複雑な「マルチクラス」の問題では、学習の難易度は2つの異なる数学的な複雑さの尺度に依存します。一つの尺度は、しばしば「DS次元」と呼ばれ、完璧な答えが存在する場合に学習者がどれだけうまく対処できるかに関連しています。もう一つの尺度は、「ナタラジャン次元」と呼ばれ、完璧な答えが存在しない場合にどれほどの不確実性が残るかに関連しています。長年、厳格な「トランスダクティブ」のルールが、特に答えの数が膨大、あるいは無限である場合に、標準的な「PAC」のルールよりも多くのデータを必要とするのかどうかは、未解決の問いでした。

ジョンズ・ホプキンス大学の研究者が、この問いを解決しました。彼らは、マルチクラスの問題において、厳格なトランスダクティブのルールは、ごくわずかな調整を除いて、標準的なルールよりも多くのデータを必要としないことを示しました。彼らは、この厳格な設定で学習するために必要な情報の量は、標準的な設定を制御するのと同じ2つの複雑さの尺度によって支配されていることを証明しました。彼らの研究は、学習者が固定された一連の例題から一つの隠されたラベルを予測しなければならない場合でも、ランダムなデータのストリームから学習している場合と同じレベルの精度を達成できることを実証しています。この発見は、2つの異なる学習モデルを統合し、学習の根本的な限界は、データの提示方法ではなく、問題自体の性質によって決定されることを裏付けるものです。

この結論に達するために、研究者は大きな障壁を乗り越えなければなりませんでした。厳格なトランスダクティブの設定では、学習者は目に見えるすべての答えを見て最適なルールを選ぶことはできません。なぜなら、そうすることで一種の不安定さを招く可能性があるからです。もし学習者が目に見えるデータを完璧に適合させようとすると、意図せず、目に見えるすべての例題には適合するものの、隠されたものに対しては完全に失敗してしまうようなルールを作り出してしまう可能性があります。これは、練習問題の答えをすべて暗記したものの、根本的なパターンを理解していなかったためにテストに失敗する学生に似ています。研究者は、この罠を避けるためには、学習者が目に見えるデータの一部を意図的に無視しなければならないことを見出しました。

彼らが考案した解決策は、「ランダム予約（random reservation）」という戦略です。目に見える予測を構築するためにすべての目に見える例題を使用する代わりに、学習者は目に見えるデータの大きな塊をランダムに脇に置き、それを隠されたテストポイントであるかのように扱います。これらの予約されたラベルを無視することで、学習者は、自身が構築したルールとは統計的に独立した、大きな未知のデータブロックを作り出すことができます。これにより、彼らは「汎化（一般化）」という概念に依拠した強力な数学的ツールを使用できるようになります。つまり、モデルを構築するために使用されなかったデータに対してうまく予測することです。その後、学習者は3段階のプロセスを用いて予測を洗練させます。第一に、目に見えるデータの小さなサンプルを使用して、予測ルールの有限なリストを作成します。第二に、重み付き投票システムを使用して、各質問に対する可能な答えのリストを絞り込み、実質的に問題の複雑さを軽減します。最後に、残りの目に見えるデータを使用して、絞り込まれたリストから最適なルールを選択します。

このアプローチは、データを「非復元抽出（without replacement）」でサンプリングする場合の扱いに関する、新しい数学的な洞察に基づいています。多くの学習シナリオでは、カードを引いてから元に戻すように、データポイントは独立していると想定されます。しかし、トランスダクティブの設定では、一度データポイントが観測されると、二度と観測されることはありません。研究者は、このような制限がある場合でも、特定の種類の重み付き投票システムが依然として効果的に機能することを証明しました。彼らは、システム内の「エキスパート」やルールが、データの観測されない部分をどれだけうまくカバーしているかに基づいて、予測可能な量の「報酬」を得ることを示しました。これにより、学習者が目に見えるデータから隠された予測へと移行する際に、精度を失わないことが保証されます。

研究者はまた、具体的な例を構築することで、自身の結果が最善であることを証明しました。もし問題が「完璧な答え」という観点で高いレベルの複雑さを持っている場合、エラー率はその複雑さを例題数で割ったものに比例することを示しました。もし問題が「完璧な答えがない」という観点で高いレベルの不確実性を持っている場合、エラー率はその複雑さの平方根を例題数で割ったものに比例することを示しました。これら両方の要因が必要であり、どちらか一方を欠くと、特定のケースにおいて学習タスクが不可能になることを示しました。これは、標準的な学習理論で特定された2つの複雑さの次元が、厳格なトランスダクティブ設定においても正しい尺度であることを裏付けています。

この研究の意義は、2つの学習モデル間の隔たりが埋められたことにあります。複雑なマルチクラス問題のための学習アルゴリズムを設計するあらゆる人々にとって、これは、データがランダムなストリームとして提示されるか、あるいは一つの隠された答えを持つ固定されたセットとして提示されるかにかかわらず、同じ理論的限界が適用されることを意味します。研究者は、コンピュータ上で高速に動作することが保証された特定のアルゴリズムを提供したわけではありません。なぜなら、彼らの証明は計算効率ではなく、情報理論に基づいているからです。しかし、彼らは、標準的な学習の成功を厳格なトランスダクティブ設定へと転送するための、明確なロードマップとなる「ランダム予約」と「圧縮」を用いた構造的なアプローチを確立しました。

この研究はまた、異なる種類の複雑さが学習において果たす役割を明らかにしています。完璧なルールを学ぶ能力と、ノイズが存在する中で優れたルールを学ぶ能力は別々の課題であり、それぞれが異なる量のデータを必要とすることを示しています。研究者は、これらの課題が、トランスダクティブ設定を標準的な設定よりも難しくするような形で組み合わさることはないことを実証しました。むしろ、学習者はデータの固定された集団を戦略的に一部無視することで、困難で不安定な問題を、管理可能なものへと変えることができるのです。この結果は、答えの可能性が無限であるシナリオにおいても成立しており、従来のメソッドがしばしば失敗した場面でも有効です。

結局のところ、この研究は、機械がどのように学習するかを支配する法則が堅牢であることを裏付けています。学習者がランダムな例題のセットで練習していようと、あるいは一つの欠落したピースを持つ特定のパズルを解いていようと、成功に必要な情報量は、問題の持つ同じ基礎的な構造によって決定されます。研究者は、データの使い道を注意深く管理し、複雑さの特定の次元を理解することによって、最も厳格な学習環境においても最適なパフォーマンスを達成できることを示しました。これは、将来の機械学習の発展に対して強固な理論的基盤を提供し、アルゴリズムがより洗練されていく過程においても、何が可能であるかという明確な理解に基づいたものであることを保証しています。