Loading article…
アルゴリズム学習理論は、機械学習の問題とアルゴリズムを分析するための数学的枠組みです 。同義語には、形式学習理論やアルゴリズム帰納的推論などがあります[引用が必要]。アルゴリズム学習理論は、統計的仮定と分析を利用しない点で統計学習理論とは異なります。アルゴリズム学習理論と統計学習理論はどちらも機械学習に関係しているため、計算学習理論の分野と見なすことができます[引用が必要]。
特徴的な特徴
統計的学習理論や一般的な統計理論の多くとは異なり、アルゴリズム学習理論では、データがランダムサンプルであること、つまりデータポイントが互いに独立していることを前提としていません。このため、この理論は、言語学習[1]や自動化された科学的発見など、観測が（比較的）ノイズフリーだがランダムではない領域に適しています。[2] [3]
アルゴリズム学習理論の基本的な概念は、極限での学習です。データポイントの数が増えるにつれて、学習アルゴリズムは、問題空間と一致するすべての可能なデータシーケンスに対して正しい仮説に収束する必要があります。これは統計的一貫性の非確率バージョンであり、これも極限で正しいモデルに収束することを必要としますが、学習者が確率測度0のデータシーケンスで失敗することを許可します[引用が必要]。
アルゴリズム学習理論は、チューリングマシンの学習能力を研究する。他のフレームワークでは、チューリングマシンよりもはるかに制限されたクラスの学習アルゴリズム、たとえば多項式時間などで仮説をより速く計算する学習者を検討する。そのようなフレームワークの例としては、おそらく近似正しい学習 [引用が必要]が挙げられる。
限界の中での学習
この概念は、 E. マーク ゴールドの独創的な論文「極限における言語識別」で紹介されました。 [4]言語識別の目的は、あるプログラムを実行するマシンが、任意の文が「文法的」か「非文法的」かをテストできる別のプログラムを開発できるようにすることです。学習する言語は英語や他の自然言語である必要はありません。実際、「文法的」の定義は、テストする人が知っているものであれば何でもかまいません。
ゴールドの学習モデルでは、テスターは各ステップで学習者に例文を与え、学習者は仮説で応答します。仮説とは、文法的正しさを判断するための提案プログラムです。テスターは、最終的にすべての可能性のある文（文法的かどうかに関係なく）がリストに表示されることを要求されますが、特定の順序は必要ありません。学習者は、各ステップで、仮説がこれまでのすべての文に対して正しいことを要求されます。[引用が必要]
ある学習者が「極限まで言語を学習できる」と言われるのは、ある一定のステップ数を超えるとその仮説がそれ以上変化しない場合です。[要出典]この時点で、学習者は実際に言語を学習しています。なぜなら、考えられるすべての文が入力シーケンス (過去または未来) のどこかに現れ、仮説はすべての入力 (過去または未来) に対して正しいため、仮説はすべての文に対して正しいからです。学習者は正しい仮説に到達したかどうかを判断できる必要はなく、必要なのはそれが真実であることだけです。
ゴールドは、チューリングマシンプログラムによって定義される任意の言語は、列挙法を使用して別のチューリング完全なマシンによって極限まで学習できることを示しました。[説明が必要]これは、学習者がすべての可能なチューリングマシンプログラムを順番にテストして、これまでのところ正しいものが見つかるまで行われます。これが現在のステップの仮説を形成します。最終的には正しいプログラムに到達し、その後は仮説が二度と変更されることはありません (ただし、学習者は変更する必要がないことを知らないことに注意してください)。
ゴールドはまた、学習者に正例のみが与えられる場合（つまり、入力に文法的な文のみが出現し、非文法的な文は出現しない）、言語の可能な文の数が有限である場合にのみ、その言語が極限で学習されることが保証されることを示した（これは、たとえば、文の長さが限られていることがわかっている場合に可能となる）。[説明が必要]
極限における言語識別は、高度に抽象的なモデルです。実行時間やコンピュータメモリの限界は考慮されておらず、入力にエラーがあると列挙法は失敗する可能性があります。しかし、このフレームワークは非常に強力です。なぜなら、これらの厳密な条件が維持されれば、計算可能であることがわかっているあらゆるプログラムの学習が可能になるからです[要出典] 。これは、チューリングマシンプログラムは、従来のプログラミング言語のあらゆるプログラムを模倣するように記述できるためです。チャーチ＝チューリングのテーゼを参照してください。
その他の識別基準
学習理論家は、次のような 他の学習基準も研究してきた[5] 。
- 効率性: 正しい仮説に収束するまでに必要なデータ ポイントの数を最小限に抑えます。
- マインドチェンジ：収束前に発生する仮説変更の数を最小限に抑える。[6]
心の変化の境界は、統計的学習理論で研究されている間違いの境界と密接に関連しています。[7]ケビン・ケリーは、心の変化を最小限に抑えることは、オッカムの剃刀の意味で最大限に単純な仮説を選択することに密接に関連していると示唆しています。[8]
年次会議
1990年以来、アルゴリズム学習理論（ALT）に関する国際会議が開催されており、最初の数年間（1990～1997年）はワークショップと呼ばれていました。 [9] 1992年から2016年の間、議事録はLNCSシリーズで出版されていました。[10] 2017年からは、Proceedings of Machine Learning Researchで出版されています。第34回会議は2023年2月にシンガポールで開催されます。 [11]会議のトピックは、統計的および計算学習理論、オンライン学習、能動学習、強化学習、ディープラーニングなど、理論的な機械学習のすべてをカバーしています。
参照
参考文献
- ^ ジェイン、サンジェイ（1999）。学習するシステム：学習理論入門。MITプレス。ISBN 978-0-262-10077-9。[ページが必要]
- ^ ラングレー、パット（1987）。科学的発見：創造プロセスの計算による探究。MITプレス。ISBN 978-0-262-62052-9。[ページが必要]
- ^ Schulte, Oliver (2009 年 7 月 11 日)。スミス行列分解による保存則と隠れ粒子の同時発見。第 21 回人工知能国際合同会議の議事録。pp. 1481–1487。
- ^ Gold, E Mark (1967年5月). 「限界における言語識別」.情報と制御. 10 (5): 447–474. doi :10.1016/S0019-9958(67)91165-5.
- ^ Jain, S. et al (1999): Systems That Learn、第2版。ケンブリッジ、マサチューセッツ州: MIT Press。
- ^ Luo, W. & Schulte, O. (2005)、マインドチェンジによる効率的な学習、Peter Auer & Ron Meir 編、学習理論に関する会議 (COLT) の議事録、398-412 ページ
- ^ Jain, Sanjay; Sharma, Arun ( 2001年5 月)。「誤りの境界に関する一般化された概念について」。情報と計算。166 (2): 156–166。doi :10.1006/inco.2000.3001。
- ^ Kelly, Kevin T. (2007 年 9 月). 「オッカムの剃刀、経験的複雑性、および真実発見効率」.理論計算機科学. 383 (2–3): 270–289. doi :10.1016/j.tcs.2007.04.009.
- ^ 北海道大学におけるALTワークショップと会議のアーカイブ
- ^ Springerの ALT 議事録ページ
- ^ ALT'23 ホームページ
外部リンク
- コンピュータサイエンスにおける学習理論。
- スタンフォード哲学百科事典は、アルゴリズム学習理論の主要概念、特に帰納的推論の哲学的問題に適用される主要概念を非常に分かりやすく紹介しています。