Pay money To my Life

Spend time for myself, and you... "Knowledge was the only way to remember that your past is true"

トップ > 記録 > AI-Feynman: A physics-inspired method for symbolic regression（日本語訳）

AI-Feynman: A physics-inspired method for symbolic regression（日本語訳）

記録 論文

はじめに

　本記事は、2020年4月15日にScienceAdvancesより出版された、MITのSilviu-Marian UdrescuとMax Tegmarkによる論文"AI Feynman: A physics-inspired method for symbolic regression"の日本語訳である。この論文は、インターネット上で公開されているうえに、pythonで記述されたプログラムがGithub上で公開されている。なお、この論文は2019年にも出版されているが、内容に大差はないため、本記事では2020年のものを対象にする。
　このGithubで公開されているサンプルプログラムを実行しようとしたところ、うまく動作しなかった。そこで、備忘録がてらに元論文を翻訳することにした。AI-Feynmanの使用感も、うまく使えた時に記事化する予定。

本文翻訳に際して

　まず、本論文を翻訳するに際して、事前にお断りさせていただきたいこととして、この分野の論文に触れる機会が滅多にないため、単語を適切に翻訳できていない可能性がある、ということ。よって、一部単語について、以下のルールで翻訳する。

  • mystery ... mystery equationなど、イマイチどの日本語がピッタリハマるのかが不明だったため、mystery方程式、などといったようにそのままmysteryを使用します（探索対象となる方程式やデータセットに対して使用されているため、ベールに包まれているもの、これから正体が明らかになるもの、といったような意味合いでのmysteryという単語の採用かと推測しますが、、真実は如何に、、）
  • symbolic regression ... 直訳すると記号回帰、ここでは関数同定(問題)という訳を採用

Abstruct

　物理学と人工知能(AI)の核心的な課題は、未知の関数からデータと一致する記号式を見つけるという関数同定問題である。この問題は、原理的にはNP困難であると思われるが、実用的に関心のある関数は、しばしば対称性、分離可能性、構成性、および他の単純化された特性を示す。この精神に基づき、我々はニューラルネットワークのフィッティングと物理学からヒントを得た一連の技術を組み合わせた再帰的な多次元関数同定アルゴリズムを開発した。我々はそれをファインマン物理学講義からの100の方程式に適用したところ、以前に公開されていたソフトウェアが71しか解けなかったのに対し、すべての方程式を発見することができた。

Introduction

　1601年、ヨハネス・ケプラーは惑星軌道に関する世界最高のデータ表を手に入れ、火星のデータを様々な楕円形に適合させようと4年と約40回の試みに失敗した後、火星の軌道が楕円であることを発見して科学革命を起こした ^{[1]}。これは、与えられたデータセットと正確に一致する記号的な仮定を発見する、という関数同定問題 (symbolic regression; 記号回帰とも呼ばれる) の例である。より具体的には、我々には \{x_1, ...., x_n, y \} という形式の数字の表が与えられ、その行は \{x_1, ...., x_n, y \}という形式であり、我々の課題は、任意の複雑なノイズを含有する、未知のmystery関数 fの正しい記号式を発見することである。
　データセットの増加に伴い、このような回帰タスクを自動化しようとする試みが活発化し、顕著な成功を収めている。未知の関数 fが\{x_1, ...., x_n \}の既知の関数の線形結合であるという特殊なケースでは、記号回帰は単に一次方程式の系を解くだけで済む。線形回帰（ fが単にアフィン関数である場合）は、金融から心理学まで、科学文献(論文)のどこにでもある（ユビキタスである）。 fが \{x_1, ...., x_n \}の単項式の線形結合である場合は、相互作用項を持つ線形回帰や、より一般的な多項式フィットに対応する。フーリエ展開からウェーブレット変換まで、既知の関数の線形結合である一般的な回帰関数の例は、他にも数え切れないほどある。このような特殊なケースでの成功にもかかわらず、一般的な関数同定問題は未解決のままであるが、その理由は簡単に理解できる。関数を記号の文字列として符号化すると、そのような文字列の数は文字列の長さに応じて指数関数的に増加するためである。

　指数関数的に大きな探索空間の組合せ問題は、コードブレーキングやルービックキューブから、進化的に最も適合する遺伝子コードを見つける自然淘汰問題に至るまで、多くの有名な問題を特徴づけている。このことが、指数関数的に大きな空間での標的検索のための遺伝的アルゴリズム ^{[2,3]}の動機付けとなっている。このアルゴリズムは、上述のブルートフォース検索を突然変異、選択、継承、組換え（ざっくり言うと、遺伝子の役割は、求められている式やプログラムの一部を形成しているかもしれない有用な記号文字列によって決まっている）などの生物学にインスパイアされた戦略に置き換える。このようなアルゴリズムは、アンテナ ^{[4,5]}や車両 ^{[6]}の設計から、ワイヤレスルーティング ^{[7]}、車両ルーティング ^{[8]}、ロボットナビゲーション ^{[9]}、コードブレーキング ^{[10]}、偏微分方程式の発見 ^{[11]}、投資戦略 ^{[12]}、マーケティング ^{[13]}、分類 ^{[14]}、ルービックキューブ ^{[15]}、プログラム合成 ^{[16]}、代謝ネットワーク ^{[17]}に至るまで、様々な分野に応用されてきた。

　数学関数の関数同定問題（この論文の焦点）は、スパース回帰 ^{[21-24]}や遺伝的アルゴリズム ^{[25,26]}など、さまざまな手法 ^{[18-20]}で取り組まれてきた。これらの中で最も成功しているのは、結果で見るように、 ^{[27]}で概説した遺伝的アルゴリズムであり、商用のEureqaソフトウェア ^{[26]}に実装されている。
　この論文の目的は、ニューラルネットワークによって可能になった物理学にインスパイアされた戦略を使用して、この技術の状態をさらに向上させることである。我々の最も重要な貢献は、ニューラルネットワークを使用して、mysteryデータの対称性や分離可能性などの隠れた単純さをカバーすることであり、これにより、より困難な問題をより少ない変数でより単純な問題に再帰的に分解することができる。
　本論文の残りの部分は以下のように構成されている。

  • Results : 最先端のEureqaアルゴリズムよりも大幅な改善が見られた、6つの戦略を再帰的に組み合わせた我々のアルゴリズムを適用した結果を紹介する
  • Discussion : 結論をまとめ、さらなる進展の機会について議論する

Results

本節では、我々の結果と、それを得るためのアルゴリズムを紹介する。

overall algorithms

　汎用関数 y=f(x_1, ..., x_n) は非常に複雑で、関数同定問題（記号回帰）では発見が不可能に近い。しかし、物理学や他の多くの科学的応用に登場する関数は、発見を容易にする次のような単純化された特性を持っていることが多い。

  1. 単位 Units： fとそれに依存する変数は既知の物理的単位を持っている
  2. 低次多項式 Low-order polynomial : f（またはその一部）は低次の多項式である
  3. 構成性 Compositionality : fは，それぞれが通常2つ以下の引数を取る小さな素関数の集合の構成である
  4. 平滑性 Smoothness : fは連続的であり, おそらくその領域では分析的でさえある
  5. 対称性 Symmetry : fは，その変数のいくつかに関して並進，回転，またはスケーリングの対称性を示す
  6. 分離可能性(因数分解) Separability : fは、共通の変数を持たない2つの部分の和または積として書くことができる

　なぜこれらの特性が共通するのかという疑問は、まだ論争の余地があり、完全には理解されていない ^{[28,29]}。しかしこれらの疑問は、後述するように、記号回帰を容易にするためにこれらの特性を発見・利用することを妨げるものではない。
　特性(1)は，次元分析を可能にし，それはしばしば問題をより少ない独立変数でより単純なものに変換する．
　特性(2)は多項式フィットを可能にし、これは多項式係数を決定するために線形方程式のシステムを解くことによって問題を素早く解決する。
　特性(3)は、 fを少数のノードタイプを持つ構文木として表現することを可能にし、時にはブルートフォース検索によって fや部分式を見つけることを可能にします。
　特性(4)は、滑らかな活性化関数を持つフィードフォワードニューラルネットワークを用いて fを近似することができる。
　特性(5)は、前記ニューラルネットワークを用いて確認することができ、問題を独立変数が1つ少ない（ n > 2回転対称の場合はさらに少ない）より単純なものに変換することができる。
　特性(6)は、前述のニューラルネットワークを用いて確認することができ、独立変数を2つの不連続な集合に分割し、問題を2つのより単純な集合に変換することができる（それぞれがこれらの集合の1つからの変数を含む）。
　図1に全体的なアルゴリズムの模式図を示す。これは、上述の特性をそれぞれ利用しようとする一連のモジュールで構成されている。人間の科学者のように、多くの異なる戦略（モジュール）を順番に試し、それが一度に完全な問題を解決できない場合は、それを変換しようとし、それを別々に取り組むことができるより単純な部分に分割し、再帰的に各部分上の完全なアルゴリズムを再起動する。図2は、あるmysteryデータセット（9つの変数を持つニュートンの重力の法則）がどのようにして解かれるかの例を示している。以下、これらのアルゴリズムモジュールを順番に説明する。

f:id:K_PTL:20200422113452j:plain
図1. AI-Feynman アルゴリズム：反復的な4つのステップで新しいデータセットが生成され、アルゴリズムの新しいインスタンスに送られる。

f:id:K_PTL:20200422113459j:plain
図2. AI-Feynman アルゴリズムがmystery方程式を発見する方法（例：万有引力の法則...Dimensional analysisで万有引力 fの次元を持つ部分と無次元部分に分離、Translational symmetryで問題を簡単にする（変数の置換）、Separabilityで簡単な問題に分離する、こうして得られた式に対して次元解析や多項式フィッティング、組み合わせ総当たりで解🙂を求める）

Dimension analysis; 次元解析

　我々の次元解析モジュールは、『物理学の多くの問題は、方程式の両辺の単位を一致させることで単純化できる』というよく知られた事実を利用している。これにより、多くの場合、問題は無次元変数かつその個数がより少ない、より単純なものに変換される。最良のシナリオでは、変換された問題は、変数を含まない関数、すなわち定数を解くことを含む。次元解析を以下のように自動化する。
　表3は，100の謎に登場するすべての変数の物理的な単位を示しており，基本単位（メートル，秒，キログラム，ケルビン，ボルト）とさまざまな整数倍の積として表現されている．したがって、各変数の単位は、表のように5つの整数からなるベクトルuで表されます。 y=f(x_1, ..., x_n) というmystery formに対して、 i番目の変数 \textbf{x}_{i}に対応するカラムのベクトル \textbf{u}と、その中でも yに対応する \textbf{u}をベクトル \textbf{b}として定義した行列 \textbf{M}を定義する。ここで、ベクトル \textbf{p}を方程式 \textbf{Mp} = \textbf{b}の解とし、マトリックス \textbf{U}のカラムが零空間の基底を形成するので、 \textbf{MU}=0となる。さらに、以下の定義のもとで新たなmystery y' = f'(x'_1, x'_2, ... , x'_n)を定義する。

\displaystyle x'_{i} \equiv \prod_{i=j}^{n} x_{j}^{U_{ij}} \ , \ y' \equiv \frac{y}{y_{*}} \ , \ y_{*} \equiv \prod_{I=1}^{n} x_{i}^{p_{I}} \ \tag{1}

　新しい変数 x'_iと y'_iは無次元であり、そしてそれらの個数 n'は零空間の次元数に一致する。 n' > 0である時、零空間の基底を自由に選択することができ、さらに任意のベクトル \textbf{a}に対して、ベクトル \textbf{p}を \textbf{p}=\textbf{Ua}に置換することができる。これを利用して、例えば既存の変数にできる限り依存しない新たな変数を作成するように、 \textbf{p}と \textbf{U}の可能な限り多くの要素を0に等しく設定する。この選択は、一般的に無次元変数の累乗が整数となり、累乗が分数や無理数である場合に比べて、最終的な式を見つけるのが非常に簡単になるので有用である。

Polynominal fit; 多項式フィッティング

　物理や他の科学では、多くの関数は低次多項式である。例えば、運動エネルギ K = \frac{m}{2} \bigl( {v_x}^2 + {v_y}^2 + {v_z}^2 \bigr ) のように関数そのものであったり、万有引力 F = \frac{Gm_1m_2 }{ {(x_1 - x_2)}^2 + {(y_1 - y_2)}^2 + {(z_1 - z_2)}^2 } のように分母等関数の一部分に含んでいたりする。そのため、低次の多項式で謎が解けるかどうかをテストするモジュールを導入する。我々の方法は、線形方程式の系を解く標準的な方法を用いて、最適な多項式の係数を見つける。これは、次数 0, 1,..., d_{\rm{max}} = 4の多項式にmysteryデータを適合させようとした時に、最適な多項式が「二乗平均平方根(root mean square; rms)の適合誤差 ≤ \rm{\boldsymbol{\epsilon}}_{\rm{p}}」を与える場合にそのフィッティングが適切であるとするものである（このしきい値の設定については後述）。

Brute force; 組み合わせ総当たり

　組み合わせ総当たり関数同定モデル(Brute-force symbolic regression model)は、あるクラス内で可能なすべての記号式を複雑な順に試行し，最大適合誤差がしきい値 \rm{\boldsymbol{\epsilon}}_{\rm{p}}以下になったとき、または最大ランタイム t_{\rm{max}}を超えたときに終了する。このモジュールだけでも原理的にはすべてのmisteriesを解くことができるが、多くの場合、実際には宇宙の年齢よりも長い時間がかかります（非現実的）。したがって、我々の組み合わせ総当たり法は一般的には、後述するモジュールによってmysteryが変換されたり、より単純な断片に分解されたりした後に、最も有用である。
　試す式を記号の文字列として表現し、最初に長さ1のすべての文字列を試し、次に長さ2のすべての文字列を試すなどして、構文的に正しい文字列だけを生成して時間を節約/短縮する。使用されている記号は、独立変数と表1に記載されている変数のサブセットで、それぞれが定数または関数を表している。ポーランド記法の逆ポーランド記法を用いて文字列の長さを最小限に抑えているため、括弧は不要である。 例えば、

  • 関数 x + y → 文字列 "xy+"
  • 数値 -2/3 → 文字列 "0<<1>>/"
  • 相対論的運動量 \frac{mv}{1 - \sqrt{\frac{v^2}{c^2}} } → 文字列 "mv*1vv*cc*/-R/"

f:id:K_PTL:20200422151929p:plain

　表1を見てみると、多くの記号が冗長であることがわかる（例えば、"1"="0>"、 "x~"="0x-"）。また、 \pi = 2 \arcsin{1}であることから、もし \piを表現する"P"をdropしたとしても、 \piが含まれているmysteriesは"P"="1N1>"で表現し解くことが出来るとはいえ、ただ時間がかかるだけ（ナンセンス）である。
　 s個のシンボル(アルファベット)を使った長さ nの s^nの文字列があるため、シンボルの数が多すぎ（ sを増やす）たり、シンボルの数が少なすぎ（必要な nを増やしたり、解を不可能にしたりする）たりと、かなりのコストがかかることがある。妥協案として、組み合わせBrute forceモジュールでは、表1のキャプションで説明されているように、3つの異なるシンボルサブセットを使用して謎を解こうとしている。多くの方程式やその一部が乗算定数や加算定数を持っているという事実を利用するために、Brute force法には、そのような定数を自動で数学的に解く2つのバリエーションがある。
　overfitting問題は連続的なパラメータ空間を探索するときに最もよく知られているが、シンボル文字列の離散空間を探索するときにも同じ現象が発生する。これを緩和するために，提案 ^{[30]}に従って，式(2)に示す合計記述長さ; DLが最小となるrmsのフィッティング誤差 \rm{\boldsymbol{\epsilon}} \lt \rm{\boldsymbol{\epsilon}}_{\rm{b}}を持つ関数をwinning functionと定義する。

DL \equiv \log_{2} N + \ \lambda \log_{2} \ \bigl[ \ \rm{max}( 1, \frac{ \rm{\boldsymbol{\epsilon}} }{ \rm{\boldsymbol{\epsilon}}_{\rm{d}} } ) \ \bigr] \ \tag{2} \

ここで、 \rm{\boldsymbol{\epsilon}}_{\rm{d}} =10^{-15} であり、 Nは、試したすべての文字列のリスト上の文字列のランクである。この2つの項は，ハイパーパラメータ \lambdaをデータ点数 N_dと等しく設定した場合、それぞれシンボル文字列を格納するのに必要なビット数と予測誤差におおよそ対応している。以下の実験では、より単純な式を優先するために \lambda = N_d^{1/2}を使用する。mysteryがニューラルネットワーク（後述）を用いて生成されている場合、精度閾値 \rm{\boldsymbol{\epsilon}}_{\rm{b}}を検証誤差の10倍に設定し、そうでない場合は 10^{-5}に設定する。

Neural network-based tests and transformations;

to be continued.....

Neural network training; NNでの学習

Translational symmetry and generalizations; 並進対称性と一般化

Separability; 因数分解

Setting variable equal; 変数を等価にする

Extra transformations

Tha Feynman Symbolic Regression Database

Algorithm comparison

Dependence on data size

Dependence on noise level

Bonus mysteries

Discussion

Key findings

Opportunities for further work

Materials and methods

Reference and Note

  1. 　A. Koyré, The Astronomical Revolution: Copernicus-Kepler-Borelli (Routledge, 2013).
  2. 　N. M. Amil, N. Bredeche, C. Gagné, S. Gelly, M. Schoenauer, O.Teytaud, European Conference on Genetic Programming (Springer, 2009), pp. 327–338.
  3. 　S. K. Pal, P. P. Wang, Genetic algorithms for pattern recognition (CRC press, 2017).
  4. 　J. D. Lohn, W. F. Kraus, D. S. Linden, IEEE Antenna & Propagation Society Mtg. 3, 814 (2002).
  5. 　D. S. Linden, Proceedings 2002 NASA/DoD Conference on Evolvable Hardware (IEEE, 2002), pp. 147–151.
  6. 　H. Yu, N. Yu, The Pennsylvania State University, (University Park, 2003) pp. 1–9.
  7. 　S. Panthong, S. Jantarang, CCECE 2003-Canadian Conference on Electrical and Computer Engineering. Toward a Caring and Humane Technology (Cat. No. 03CH37436) (IEEE, 2003), vol. 3, pp. 1597–1600.
  8. 　B. Oh, Y. Na, J. Yang, S. Park, J. Nang, J. Kim, Genetic algorithm-based dynamic vehicle route search using car-to-car communication. Adv. Electr. Comput. En. 10, 81–86 (2010).
  9. 　A. Ram, R. Arkin, G. Boone, M. Pearce, Using genetic algorithms to learn reactive control parameters for autonomous robotic navigation. Adapt. Behav. 2, 277–305 (1994).
  10. 　B. Delman, Genetic algorithms in cryptography. Rochester Institute of Technology (2004). 11. S. Kim, P. Lu, S. Mukherjee, M. Gilbert, L. Jing, V. Ceperic, M. Soljacic, arXiv preprint arXiv:1912.04825 (2019).
  11. 　R. J. Bauer, Genetic algorithms and investment strategies, (John Wiley & Sons, ed. 1, 1994), vol. 19, p. 320.
  12. 　R. Venkatesan, V. Kumar, A genetic algorithms approach to forecasting of wireless subscribers. Int. J. Forecast. 18, 625–646 (2002).
  13. 　W. L. Cava, T. R. Singh, J. Taggart, S. Suri, J. Moore, International Conference on Learning Representations (2019), https://openreview.net/forum?id=Hke-JhA9Y7.
  14. 　S. McAleer, F. Agostinelli, A. Shmakov, P. Baldi, International Conference on Learning Representations (2019); https://openreview.net/forum?id=Hyfn2jCcKm.
  15. 　J. R. Koza, J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press, 1992), vol. 1.
  16. 　M. D. Schmidt, R. R. Vallabhajosyula, J. W. Jenkins, J. E. Hood, A. S. Soni, J. P. Wikswo, H. Lipson, Automated refinement and inference of analytical models for metabolic networks. Phys. Biol. 8, 055011 (2011).
  17. 　R. K. McRee, Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation (ACM, New York, NY, USA, 2010), GECCO ‘10, pp. 1983–1990; http://doi.acm.org/10.1145/1830761.1830841.
  18. 　S. Stijven, W. Minnebo, K. Vladislavleva, Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation (ACM, New York, NY, USA, 2011), GECCO ‘11, pp. 623–630; http://doi.acm.org/10.1145/2001858.2002059.
  19. 　W. Kong, C. Liaw, A. Mehta, D. Sivakumar, International Conference on Learning Representations (2019); https://openreview.net/forum?id=rkluJ2R9KQ.
  20. 　T. McConaghy, Genetic Programming Theory and Practice IX (Springer, 2011), pp. 235–260.
  21. 　I. Arnaldo, U.-M. O’Reilly, K. Veeramachaneni, Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (ACM, 2015), pp. 983–990.
  22. 　S. L. Brunton, J. L. Proctor, J. N. Kutz, Discovering governing equations from data by sparse identification of nonlinear dynamical systems. Proc. Natl. Acad. Sci. U.S.A. 113, 3932–3937 (2016).
  23. 　M. Quade, M. Abel, J. Nathanutz, S. L. Brunton, Sparse identification of nonlinear dynamics for rapid model recovery. Chaos 28, 063116 (2018).
  24. 　D. P. Searson, D. E. Leahy, M. J. Willis, Proceedings of the International multiconference of engineers and computer scientists (Citeseer, 2010), vol. 1, pp. 77–80.
  25. 　R. Praksova, Eureqa: Software review. Genet. Program. Evol. M. 12, 173–178 (2011).
  26. 　M. Schmidt, H. Lipson, Distilling free-form natural laws from experimental data. Science 324, 81–85 (2009).
  27. 　H. Mhaskar, Q. Liao, T. Poggio, Technical report, Center for Brains, Minds and Machines (CBMM), arXiv (2016).
  28. 　H. W. Lin, M. Tegmark, D. Rolnick, Why does deep and cheap learning work so well? J. Stat. Phys. 168, 1223–1247 (2017).
  29. 　T. Wu, M. Tegmark, Toward an artificial intelligence physicist for unsupervised learning. Phys. Rev. E. 100, 033311 (2019).
  30. 　L. N. Smith, N. Topin, Super-convergence: Very fast training of residual networks using large learning rates (2018); https://openreview.net/forum?id=H1A5ztj3b.
  31. 　L. N. Smith, A disciplined approach to neural network hyper-parameters: Part 1 – learning rate, batch size, momentum, and weight decay. arXiv:1803.09820 (2018).
  32. 　J. Howard et al., Fastai, https://github.com/fastai/fastai (2018).
  33. 　R. Feynman, R. Leighton, M. Sands, The Feynman Lectures on Physics: The New Millennium Edition: Mainly Mechanics, Radiation, and Heat, vol. 1 (Basic Books, 1963); https://books.google.com/books?id=d76DBQAAQBAJ.
    35.　 R. Feynman, R. Leighton, M. Sands, The Feynman Lectures on Physics, vol. 2 in The Feynman Lectures on Physics (Pearson/Addison-Wesley, 1963b); https://books.google.com/books?id=AbruAAAAMAAJ.
  34. 　R. Feynman, R. Leighton, M. Sands, The Feynman Lectures on Physics, vol. 3 in The Feynman Lectures on Physics (Pearson/Addison-Wesley, 1963); https://books.google.com/books?id=_6XvAAAAMAAJ.
  35. 　H. Goldstein, C. Poole, J. Safko, Classical Mechanics (Addison Wesley, 2002); https://books.google.com/books?id=tJCuQgAACAAJ.
  36. 　J. D. Jackson, Classical electrodynamics (Wiley, New York, NY, ed. 3, 1999); http://cdsweb.cern.ch/record/490457.
  37. 　S. Weinberg, Gravitation and Cosmology: Principles and Applications of the General Theory of Relativity (New York: Wiley, 1972).
  38. 　M. Schwartz, Quantum Field Theory and the Standard Model, Quantum Field Theory and the Standard Model (Cambridge Univ. Press, 2014); https://books.google.com/books?id=HbdEAgAAQBAJ.
  39. 　J. McDermott, D. R. White, S. Luke, L. Manzoni, M. Castelli, L. Vanneschi, W. Jaskowski, K. Krawiec, R. Harper, K. De Jong, Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation (ACM, 2012), pp. 791–798.