収束加速法の紹介

メモリ事業部の 眞鍋 です。

本日は 「収束加速法」という話題を取り上げたいと思います。

同じ結果を得るにしても、その目的に特化することで高速にする技法、というのは世の中にたくさんあります。

例えば代表的なものは各種ソートアルゴリズムたちであり、

本ブログでも紹介されている「Segment Tree」につきましても、

ある目的に対して計算量を抑えることのできる技法です。

詳しくは記事をご覧ください！

こうしたアルゴリズムは、例えば 蟻本 などのプログラミング本で紹介されており、勉強することができます。

今回紹介する「収束加速法」は、

こうした本には載っていない話であり、

どちらかといえばコンピューター界隈の方からするとメジャーではない話だと思いますが、

目的はこうしたアルゴリズムと同じ内容になります。

説明の前に、

例えばどういったことに使えるのでしょうか？

応用：Google Page Rank の計算高速化

Google の創始者である Brin と Page は、

例えば The Anatomy of a Large-Scale Hypertextual Web Search Engine という論文の中で

ある行列の固有値を引き離すための (収束の速さを改善するための)

ハイパーパラメータを用意し、その値を 0.85 として計算することで、

「超々大規模な」疎行列の乗算回数を劇的に減らし高速化を行いました。

あまりにも大規模な行列のため、一回の行列演算を省くだけでとてつもない高速化になります。

この Brin と Page の方法をさらに高速化するために、

今回紹介する「収束加速法」を使ってさらに高速化する研究が知られています。

例えば  Google’s PageRank and Beyond: The Science of Search Engine Rankings という

PageRank アルゴリズムに関する歴史・背景などを詳しく書いている本には、

この収束加速法を適用する話に 1章使っています (Chapter 9. Accelerating the Computation of PageRank)

つまり 収束を加速することで、計算回数を劇的に減らす技法、というのが「収束加速法」であります。

PageRankアルゴリズムを題材にするにはいささか導入に時間がかかりますので、

おもちゃで遊んでみたいと思います。

おもちゃで収束加速法を体験しよう

有名な式にライプニッツ級数というものがあります。

この式で円周率の計算をするのはいい方法とは言えませんが、

この式を題材として扱ってみたいと思います。

ライプニッツ級数：

$$\pi = \displaystyle 4\sum_{n=0}^\infty \frac{(-1)^n}{2n+1}$$

この級数は $\pi $ に収束する級数なのですが非常に非常に収束測度が遅いことで有名です。

その収束の遅さをみるために次をご覧ください：

例えば 10000 項の結果を使った

$$\frac{4}{1} – \frac{4}{3} + \frac{4}{5} – \frac{4}{7} + \frac{4}{9} + \dotsb + \frac{4}{20001}$$

を計算しても $3.141$ までの結果しか得られません。

収束を改善してみる！

n = 9 までで得られた結果のみを使って、収束精度を上げてみます。

使う計算式は上図の ○・△・□の式で、適用してみます：

もう一度適用してみます：

この操作で、何故か改善された結果を得られました。

さらにこれを繰り返しますと次のような結果になります：

つまり、9項の情報だけで 「3.141592」と 7桁精度が得られました。

先ほどは愚直に 10000項の計算で 4桁精度しか得られていないことを考えると黒魔術的です！

さらに遊んでみる！

上のアルゴリズム、ライプニッツ級数にしか使えないような特殊な計算なのでは？

という心の声が聞こえてきそうです。

そうではないことを、別の話で遊んでみましょう。

$$\sum_{n=0}^\infty (-1)^n (n+1) = 1-2+3-4+5-\dotsb$$

という式は何を表しているかご存知でしょうか？

高校数学までは、収束しない、つまり「発散級数」と習います。

しかしながら、wikipedia の「1-2+3-4+・・・」をみてみますと次のように書かれています：

しかし計算方法によってはこの級数が収束すると考えることもでき、その場合の収束値は 1/4 である。

すなわち、 1/4 に収束する数とみなす考え方もあるんだ！ということがわかります。

詳細を知りたい方はゼータ関数などを勉強いただければと思います。

この数をこの方法で計算するとどうなるのでしょうか。

まずは先ほどと同様に部分的に計算した数を用意します。

これに先ほどの計算を行うと？

そうなのです。 1/4 になるのです！

面白いですね！

まとめ

• Google Page Rank アルゴリズムをとりあげ収束加速法の応用事例を紹介した
• 収束加速法の感覚を理解するために「ライプニッツ級数」で遊んでみた
• 発散級数にも適用できた

Fixstars ではこうした技も駆使して高速化しております！

興味のある方は是非一緒に仕事しましょう。

よろしくお願いします。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。