雑記： Nyström が読めない話

雑記

カーネル法におけるグラム行列の低ランク近似手法の一つとして知られる Nyström 法は、近年 Transformer の計算量削減への応用もみられる [11] [12]。

ところで本質的ではないことだが、Nyström 法の仮名表記はこれといったものが確立されていないように思われる。文献 [7] には「ニストローム法」の表記がみられるがおそらくこの文献は自動翻訳である。文献 [10] には「ナイストロム法」とあるがこの表記がこの文献以外に（ウェブを検索する範囲で）みつからない。

他方、Nyström の仮名表記を探索していると Runge–Kutta–Nyström 法（ルンゲクッタ法を特定の形の 2 階常微分方程式に最適化した版）を、「ルンゲクッタ・ニストローム法」と表記する文献・記事が（カーネル法の文脈に比べれば）ぽつぽつとみられることがわかる [8] [9]。

であれば先例に倣って「ニストローム法」を採用すればよいと思われるが、両 Nyström 氏が同一人物なのかは確認する必要がある。スペルが同じだけの赤の他人かもしれないためである。だいたい「行列の固有値分解による低ランク近似」と「常微分方程式の逐次解法」では同じ数学とはいっても少し分野が異なるように感じる。

調べると、カーネル法における Nyström 法はもともと積分方程式の数値解法であり [2] [3] [4] [10] [12]、これを 1930 年に発表したフィンランドの数学者が Evert Johannes Nyström とのことである [4]。そして Runge–Kutta–Nyström 法（の原型）も Evert Johannes Nyström の 1925 年の博士論文であり [1] [6]、（同年代に同じ数値解析の研究に従事し同じドイツ語で論文を執筆する同姓同名の赤の他人でなければ）同一人物である。そういわれてカーネル法における Nyström 法をふりかえると（以下）なるほど積分方程式を数値的に解いていることがわかる（きちんと教科書を読んでいれば最初からわかる）。積分方程式の数値解法である Nyström 法によって私たちは「グラム行列の固有ベクトルは固有関数の数値解ではないか」という発想を得られるのである。

カーネル法における Nyström 法（[2] [3] の記述をもとに適宜解釈）
  • K^{(n)} + \sigma I の逆行列を計算するコストを削減するため、グラム行列 K^{(n)}（n \times n 行列）をより低ランクな行列の積で近似したい。それには固有値分解が有効であるが、固有値分解自体が \mathcal{O}(n^3) を要する。K の固有値や固有ベクトルを低コストに近似できないだろうか。
  • そこで、[2] の式 (3.24) の積分作用素の固有値問題を考える。この積分を X_1, \cdots, X_m 上の和で数値近似すると、任意の点における固有関数が X_1, \cdots, X_m に対するグラム行列 K^{(m)} の m 本の単位固有ベクトルの重み付き和で近似される（積分方程式の数値解法としての Nyström 法）。逆に K^{(m)} の m 本の単位固有ベクトルは近似的に X_1, \cdots, X_m 上の固有関数の 1/\sqrt{m} 倍に等しくなり、 K^{(m)} の固有値は近似的に X_1, \cdots, X_m 上の固有関数に対応する固有値の m 倍に等しくなる。
  • したがって、 n より小さい m を選んで「K^{(m)} の単位固有ベクトルで X_{m+1}, \cdots, X_{n} における固有関数を近似し、それを用いて K^{(n)} の単位固有ベクトルを近似する」ことで \mathcal{O}(m^3) で K の固有値分解を近似することができる。さらに使用する固有値を絞って K をより低ランクな行列の積にすることもできる。

というわけで、カーネル法の文脈でも安心して「ニストローム法」とよぶことにしてもよさそうである。なお、ニストロームであればフィンランド語の発音に近いのかはフィンランド語を話す知人がいないのでわからない。ここまで調べておいてなんだがフィンランドにはニューストロン姉妹 [13] なるビーチバレー選手がいるようなので「ニューストロン法（近似）」が適切なようにも思われる（現在これでグーグル検索しても一致はない）。しかしニューストロン姉妹へのリンクがある記事 [13] 自体は北欧系の姓 Nyström を「ニュストレム」としており、念のためグーグル検索するとRunge–Kutta–Nyström 法を「ニュストレム法」と表記する翻訳本がみつかった [14]。今川焼並みの統一性のなさである。


参考文献

  1. E. J. Nyström – Wikipedia, https://fi.wikipedia.org/wiki/E._J._Nystr%C3%B6m（2022年3月15日参照）
  2. 福水 健次. カーネル法入門. 朝倉書店, 2010.
    • カーネル法の書籍である。56ページ（初版第7刷）に「Nyström 近似は、もともと積分作用素の固有関数と固有値を近似する方法である」とある。[3] [9] の記述と合わせると、もともとの Nyström 近似の帰結は、「既知の k(\cdot) から未知の \phi(\cdot) を求める積分方程式 (3.24) があるとき、\phi(y) の値を式 (3.26) の下の式で近似することができる（式 (3.25) の固有値問題を解くことなしに）」である。
  3. Using the Nyström Method to Speed Up Kernel Machines, https://proceedings.neurips.cc/paper/2000/hash/19de10adbaa1b2ee13f77f679fa1483a-Abstract.html（2022年3月15日参照）
    • NIPS 2000（当時は NIPS）の論文であり、カーネル法の文脈での「Nyström 法」の原論文である。1 節の手法の記述が丁寧でわかりやすいように思われる。Nyström 近似のリファレンスは Baker, 1977, chapter 3 となっているがこれは書籍でありウェブ上で参照できなかった。
  4. Nyström method - Wikipedia, https://en.wikipedia.org/wiki/Nystr%C3%B6m_method（2022年3月15日参照）
    • （積分方程式の数値解法としての）Nyström 法の記事である。英語版なのは日本語版がないからであるが、この記事も記述が足りていない。リファレンスに 1930 年の E. J. Nyström の論文があるが内容を確認していない。
  5. Runge–Kutta methods - Wikipedia, https://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods（2022年3月15日参照）
    • 英語版ウィキペディアのルンゲクッタ法の記事であり、Runge–Kutta–Nyström 法の記述がある。
  6. Classical eight- and lower-order Runge-Kutta-Nystroem formulas with stepsize control for special second-order differential equations - NASA Technical Reports Server (NTRS), https://ntrs.nasa.gov/citations/19720012011（2022年3月15日参照）
    • Erwin Feblberg による論文であり、[5] の注釈 18. にある同氏の論文（Runge–Kutta–Nyström 法）の 2 つ前の論文にあたる。つまり、Runge–Kutta–Nyström 法の原型の論文の1つであるが、この論文の冒頭を読むと、この論文の参考文献 [4] である「NYSTRÖM E. J.: Über die numerische Integration von Differentialgleichungen. Acta Soc. Sci. Fenn. 50, no. 13, 1925.」で初めて 2 階常微分方程式に対するルンゲクッタ法が定式化されたとある。[1] の記述と合わせるとこれが Nyström の博士論文になる。その論文も検索すれば出てくるが出所がよくわからないのとドイツ語が読めないのでリンクは割愛する。
  7. scikit-learn - 6.7.カーネル近似 - （ページタイトルが長いため後略）, https://runebook.dev/ja/docs/scikit_learn/modules/kernel_approximation（2022年3月15日参照）
  8. 樹脂と金属の接着接合体の硬化過程での内部応力, https://www.jstage.jst.go.jp/article/jsms1963/46/7/46_7_820/_article/-char/ja/（2022年3月15日参照）
    • 「この方程式をルンゲ・クッタ・ニストローム法を用いて逐次的に解き」とある。
  9. 解き方を教えてください。 -2粒子があってｒ１粒子がｒ２粒子から受け- 物理学 | 教えて!goo, https://oshiete.goo.ne.jp/qa/382969.html（2022年3月15日参照）
    • 「連立2階微分方程式を数値的に解く。解く方法は『ルンゲ・クッタ・ニストローム法』です」とある。
  10. CiNii 論文 -  I_023 ナイストロム法を用いた時系列データの高速類似検索法の検討(I分野:画像認識・メディア理解), https://ci.nii.ac.jp/naid/110007688174（2022年3月15日参照）
    • 「本研究では，距離から求まるカーネル関数により定まる積分方程式を考え，積分方程式の数値解法であるナイストロム法に基づき，」「ナイストロム法は，第二種フレッドホルム積分方程式の数値解を得るための手法である」とある。
  11. Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr\"om Method, https://proceedings.neurips.cc/paper/2021/hash/10a7cdd970fe135cf4f7bb55c0e3b59f-Abstract.html（2022年3月15日参照）
    • NeurIPS 2021 の論文である。
  12. [2102.03902] Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention, https://arxiv.org/abs/2102.03902（2022年3月15日参照）
    • [11] に引用されている。
  13. ニュストレム - Wikipedia, https://ja.wikipedia.org/wiki/%E3%83%8B%E3%83%A5%E3%82%B9%E3%83%88%E3%83%AC%E3%83%A0（2022年3月16日参照）
    • 「ニュストレム（Nystrom, Nystroem, Nystrøm, Nyström）は、北欧系の姓」とある。
  14. 常微分方程式の数値解法 | 東京工業大学附属図書館 蔵書検索, https://topics.libra.titech.ac.jp/recordID/catalog.bib/BA84255132?hit=22&caller=xc-search（2022年3月16日参照）
    • 書誌詳細から目次をみると「ニュストレム法」とある。