レイ・ソロモノフ

提供: testwiki
ナビゲーションに移動 検索に移動

レイ・ソロモノフ（Ray Solomonoff、1926年7月25日 - 2009年12月7日）[1][2]はアメリカの人工知能学者であり、アルゴリズム情報理論の創始者の1人[3]。また、アルゴリズム的確率 を考案し[4]、機械学習と予測と確率に基づく人工知能の分野を創始した。1956年、非意味論的機械学習についての論文を発表している[5]。

1960年に algorithmic probability についてカリフォルニア工科大学での会議で発表し[6]、同年2月には "A Preliminary Report on a General Theory of Inductive Inference" という論文を発表[7]。1964年には "A Formal Theory of Inductive Inference" の第一部[8][9]と第二部を発表し、さらに考え方を明確化した。そこからコルモゴロフ複雑性とアルゴリズム情報理論が発展した。

algorithmic probability は、オッカムの剃刀[10][11][12][13]と多説明原理[14]の組合せを数学的に定式化したものである。それは与えられた観察結果を説明するそれぞれの仮説（アルゴリズム、プログラム）に確率値を割り当てる機械に依存しない手法であり、最も単純な仮説が最も高い確率を割り当てられ、仮説が複雑になるほど割り当てる確率が低くなる。

他にも帰納推論テンプレート:Enlinkの一般理論でも知られているが、確率的手法を用いて難しい問題を機械で解くという人工知能研究の過程で他にも様々な発見をしている。

ダートマス会議まで

1926年7月25日、オハイオ州クリーブランドでロシア人移民の子として生まれた。幼いころから好奇心が強く、数学的発見に純粋な喜びを見出す性質だった。16歳のとき（1942年）、数学の問題を解く万能の方法を探索しはじめた。1944年に高校を卒業するとアメリカ海軍に入隊し、そこでエレクトロニクスの指導員を務めた。1947年にシカゴ大学に進学し、ルドルフ・カルナップやエンリコ・フェルミの指導を受け、1951年には物理学の修士号を得て卒業した。

1950年から52年にかけて、3つの論文を書いている（うち2つはアナトール・ラパポートと共同執筆）[15]。これらはネットワークの静的解析に関する最初の論文とされている。

1952年、マービン・ミンスキーやジョン・マッカーシーといった機械知性に興味を持つ人々に出会った。1956年にミンスキーやマッカーシーらが開催したダートマス会議にも参加している。1カ月間行われた会議で、最初から最後まで参加したのはミンスキーとソロモノフだけだった。この会議参加者によって初めて人工知能が学問分野の名称とされた。当時のコンピュータは非常に限定された数学の問題を解くことはできたが、それだけだった。ソロモノフは、機械をより汎用的に知的にするにはどうすればよいか、そしてそのためにコンピュータがどのように確率を扱えばよいかという大きな問題を追求したいと考えていた。会議中に "An Inductive Inference Machine" と題したレポートを書き、参加者に回覧した[5]。それは機械学習を確率的なものとし、学習の重要性を強調し、過去の問題の解法の部分を新たな問題の解法構築の試行に利用するという考え方を提示したものである。1957年にはそれまでの結論をまとめて発表した[16]。それらは確率的機械学習について書かれた世界初の論文である。

1950年代後半、確率的言語とそれに関連する文法を考案[17]。確率的言語は、それぞれの可能な文字列に確率値を割り当てる。確率的文法の概念を一般化することで、1960年の Algorithmic Probability の発見へとつながった。

Algorithmic Probability

1960年代より以前、確率を計算するには頻度に基づくのが普通だった。試行回数に対して、希望の結果が得られた回数の比率を求めるのである。1960年のソロモノフの論文では、この確率の定義が大きく改訂されており、1964年の論文でさらに完全なものとなっている。

後にコルモゴロフ複雑性と呼ばれることになる基本定理は、ソロモノフの理論にも含まれていた。1960年の論文の導入部に次のような一節がある。

非常に長い記号列を考えてみよう。…その記号列についての非常に簡単な説明があり、もちろん所定の記述方法を使っているなら、我々はその記号列が「単純」であるとみなすことができ、アプリオリな高い確率で予測することができる。より正確に言えば、0と1だけで何かを表現する場合、それが N 桁の二進数が可能な限り最短の表現であれば、その確率として 2-N を割り当てることになる。[18]

この確率は、特定のテンプレート:仮リンクへの参照と結びついている。ソロモノフは機械の選択を示し、1964年には証明したが、定数因子を加えても確率の比率はあまり変化しないということも示した。それらの確率は機械独立である。

1965年、ロシア人数学者コルモゴロフが独自に同様の考え方を発表した。コルモゴロフは後にソロモノフの業績を知り、ソロモノフの業績を認めた。その後数年間は、西欧よりもソ連でソロモノフの業績がよく知られるようになった。しかし学会全体としては、記号列の無作為性をより強調したコルモゴロフの名が結び付けられる結果となった。ソロモノフの Algorithmic Probability は記号列の外挿による予測に重きを置いていた。

後に1960年の後の時点で、ソロモノフは単一最短符号理論の拡張版を発表している。それが Algorithmic Probability である。彼は「記号列を説明するいくつかの異なる方法があるとき、それぞれの方法が記号列の確率を決定する際に何らかの重みを与えられるべきと思われる」と記している[19]。そして、この考え方を使って汎用的でアプリオリな確率分布を生成する方法と、ベイズの定理を帰納推論に使えるようにする方法を示している。帰納推論は、特定の記号列を説明する全モデルの予測を加算することにより、それらのモデルの長さに基づいた適切な重み付けを使うことで、その記号列の拡張の確率分布を得る。この推論方法は後に「ソロモノフ推論」とも呼ばれるようになった。

その後もいくつかの論文を発表しつつ理論を発展させていき、1964年の発表へとつなげた。1964年の論文では Algorithmic Probability とソロモノフ推論についてより詳細に述べており、Universal Distribution と呼ばれるモデルを含む5つのモデルを提示している。

確率と人工知能

1956年夏のダートマス会議に参加した他の科学者ら（例えば、ニューウェルとサイモン）は、IF-THEN規則と事実ベースの人工知能の開発を行っていた。ソロモノフは確率と推論に基づく人工知能を開発していた。すなわち、Algorithmic Probability に基づく人工知能である。それは問題解決のための推論を確率つきで生成し、新たな問題と推論が出てきたら、推論群の確率分布を更新する。

1968年、Algorithmic Probability の有効性についての証明を得たが[20]、当時はそのことにあまり興味がなかったため、公表したのは10年後となった。その中で収束定理の証明を発表している。

Algorithmic Probability の発見以降、その確率およびソロモノフ推論を実際の人工知能プログラムでの推論や問題解決に応用することの注力している。また、この確率体系の持つ意味についてもより深く理解しようとしていた。

Algorithmic Probability の重要な様相の1つとして、完全かつ計算不能という点がある。

1968年の論文で Algorithmic Probability が「完全 (complete)」であることを示した。データに何らかの描写可能な規則正しさがあるとき、Algorithmic Probability はその規則性を最終的に発見でき、それには相対的に少数のデータ標本があればよい。その意味で Algorithmic Probability は唯一の既知の完全な確率体系である。その完全性の必然的帰結として、それは「計算不能 (incomputable)」である。計算不能性が生じるのは、部分再帰アルゴリズムのサブセットである一部のアルゴリズムがあまりにも評価に時間がかかるため、決して完全には評価できないためである。しかしそれらのプログラムも少なくとも解法として認められるだろう。一方、任意の「計算可能」な体系は「不完全」である。そのような体系では、たとえ無限の時間をかけても認識・考慮されない探索空間が必ず存在する。計算可能な推論モデルは、そのようなアルゴリズムを無視することでその事実を隠蔽する。

ソロモノフは多くの論文で問題の解の探索方法を記述し、1970年代から1980年代初めにかけて、彼が機械を更新する最良の方法と考える方法を開発した。

しかし人工知能における確率の利用には紆余曲折があった。初期の人工知能において、確率の関連付けは問題が多かった。また、人工知能研究者の多くは確率の利用を避けていた。パターン認識の分野では確率は使われなかったし、確率を組み入れるための幅広く基本的な理論がなかったため、多くの分野で確率は利用されなかった。

しかし、ジューディア・パールなどの研究者らは人工知能での確率の有効性を主張した。

1984年ごろのアメリカ人工知能学会 (AAAI) の年次会合で、確率と人工知能は無関係であるとの決議が採択されている。これに反対するグループが結成され、翌年のAAAIの会合で "Probability and Uncertainty in AI"（AIにおける確率と不確実性）と題したワークショップが開催されている。このワークショップはその後も続けられている[21]。

その最初のワークショップで、ソロモノフは人工知能における問題に universal distribution を適用する方法を示した論文を発表した[22]。それはソロモノフが後に発展させることになる体系の初期のバージョンだった。その中で自身が開発した探索技法を説明している。探索問題での最良の探索順序にかかる時間は Ti/Pi で表され、Ti は1回の試行にかかる時間、Pi はその試行が成功する確率である。ソロモノフはこれを問題の "Conceptual Jump Size" と呼んだ。Levinの探索技法はこの順序の近似であり[23]、ソロモノフは Levin の探索技法を研究して Lsearch と呼称した。

晩年

他にも、資源が限られた探索で解を探索するのにかかる時間を制限する方法を研究している。探索空間は最小記述長などの推論技法では意図的に制限されるが、探索にかけられる時間や計算コストによっても制限される。

ソロモノフは長年に渡って人工知能の潜在的利益と危険についても考察しており、多くの論文で議論している。1985年、人工知能の発展がいつ「無限大 (Infinity Point)」に達するかを予測する式を作り、人工知能の未来を分析した[24]。この考え方は後にレイ・カーツワイルが広めた技術的特異点のさきがけといえる。

アルゴリズム誘導の方法は本来、順序に従った文字列を外挿するものだった。そのため他の種類のデータを扱う同様の方法が必要とされていた。

1999年の論文で順序に従わない文字列を扱うため Universal Distribution を一般化し収束定理と組み合わせている[25]。2008年の論文では順序に従わない2つの文字列を扱っている[26]。

1997年（および2003年と2006年）の論文で、高性能推論システムには計算不能性と主観性が必須であり望ましい性質だとした[27]。

ソロモノフは1970年に個人企業 Oxbridge Research を立ち上げ、MIT、ザールラント大学、スイスの人工知能研究所といった研究機関に所属している期間以外は、その会社で活動していた。2003年、ロンドン大学ロイヤル・ホロウェイの Computer Learning Research Center (CLRC) から第1回コルモゴロフ賞を受賞。その後はCLRCで客員教授を務めていた。

ダートマス会議から50周年となった2006年、テンプレート:仮リンクが開催され、ダートマス会議に参加していたソロモノフも講演を行った。

参考文献

  • Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag, N.Y., 2008
  • "The Discovery of Algorithmic Probability", Journal of Computer and System Sciences, Vol 55, No. 1, pp 73–88, August 1997.

脚注

テンプレート:Reflist

外部リンク

テンプレート:Normdaten

  1. ↑ テンプレート:Cite web
  2. ↑ テンプレート:Cite news
  3. ↑ Vitanyi, P. "Obituary: Ray Solomonoff, Founding Father of Algorithmic Information Theory"
  4. ↑ detailed description of Algorithmic Probability in Scholarpedia
  5. ↑ 5.0 5.1 (pdf scanned copy of the original)
  6. ↑ Paper from conference on "Cerebral Systems and Computers", California Institute of Technology, Feb 8-11, 1960, cited in "A Formal Theory of Inductive Inference, Part 1, 1964, p. 1
  7. ↑ Solomonoff, R., "A Preliminary Report on a General Theory of Inductive Inference", Report V-131, Zator Co., Cambridge, Ma. Feb 4, 1960, revision, Nov., 1960.
  8. ↑ Solomonoff, R., "A Formal Theory of Inductive Inference, Part I" Information and Control, Vol 7, No. 1 pp 1-22, March 1964.
  9. ↑ Solomonoff, R., "A Formal Theory of Inductive Inference, Part II" Information and Control, Vol 7, No. 2 pp 224-254, June 1964.
  10. ↑ Induction: From Kolmogorov and Solomonoff to De Finetti and Back to Kolmogorov JJ McCall - Metroeconomica, 2004 - Wiley Online Library.
  11. ↑ Foundations of Occam's razor and parsimony in learning from ricoh.com D Stork - NIPS 2001 Workshop, 2001
  12. ↑ Occam's razor as a formal basis for a physical theory from arxiv.org AN Soklakov - Foundations of Physics Letters, 2002 - Springer
  13. ↑ Beyond the Turing Test from uclm.es J HERNANDEZ-ORALLO - Journal of Logic, Language, and …, 2000 - dsi.uclm.es
  14. ↑ Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag, N.Y., 2008p 339 ff.
  15. ↑ "An Exact Method for the Computation of the Connectivity of Random Nets", Bulletin of Mathematical Biophysics, Vol 14, p. 153, 1952.
  16. ↑ An Inductive Inference Machine," IRE Convention Record, Section on Information Theory, Part 2, pp. 56-62.(pdf version)
  17. ↑ "A Progress Report on Machines to Learn to Translate Languages and Retrieve Information", Advances in Documentation and Library Science, Vol III, pt. 2, pp. 941-953. (Proceedings of a conference in Sept. 1959.)
  18. ↑ "A Preliminary Report on a General Theory of Inductive Inference,", 1960 p. 1
  19. ↑ "A Preliminary Report on a General Theory of Inductive Inference,",1960, p. 17
  20. ↑ "Complexity-based Induction Systems, Comparisons and convergence Theorems" IEEE Trans. on Information Theory Vol. IT-24, No. 4, pp.422-432, July,1978. (pdf version)
  21. ↑ "The Universal Distribution and Machine Learning", The Kolmogorov Lecture, Feb. 27, 2003, Royal Holloway, Univ. of London. The Computer Journal, Vol 46, No. 6, 2003.
  22. ↑ "The Application of Algorithmic Probability to Problems in Artificial Intelligence", in Kanal and Lemmer (Eds.), Uncertainty in Artificial Intelligence,, Elsevier Science Publishers B.V., pp 473-491, 1986.
  23. ↑ Levin, L.A., "Universal Search Problems", in Problemy Peredaci Informacii 9, pp. 115-116, 1973
  24. ↑ "The Time Scale of Artificial Intelligence: Reflections on Social Effects," Human Systems Management, Vol 5, pp. 149-153, 1985 (pdf version)
  25. ↑ "Two Kinds of Probabilistic Induction," The Computer Journal, Vol 42, No. 4, 1999. (pdf version)
  26. ↑ "Three Kinds of Probabilistic Induction, Universal Distributions and Convergence Theorems" 2008. (pdf version)
  27. ↑ "The Discovery of Algorithmi Probability," Journal of Computer and System Sciences, Vol 55, No. 1, pp. 73-88 (pdf version)
「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=レイ・ソロモノフ&oldid=8049」から取得