スプレッドシートを使ったことのある人なら誰もが認めるように、データを表に整理すると便利なことが多い。しかしビッグデータの時代には、その表が膨大になり、行数が数百万、あるいは数億に達することもある。
ビッグデータ分析を計算上実用的にする方法の一つは、データ表、数学用語でいう行列から、多数の行を除いてサイズを小さくすることだ。重要なのは、残した行が、除外した行を何らかの意味で代表していなければならないという点である。そうすれば、それらの行を使った計算で、おおむね正しい結果が得られる。
6月のACM計算理論シンポジウムで、MITの研究者らは、信頼できる計算を保証する、元の行列の可能な限り小さな近似を見つける新しいアルゴリズムを発表する。工学や機械学習で重要な問題群に対して、これは従来の手法を大きく上回る改善となる。また、あらゆる問題群について、このアルゴリズムは可能な限り高速に近似を見つける。
圧縮後の行列のある行が元の行列の行をどれほどよく代表しているかを判断するため、アルゴリズムは両者の「距離」を測る必要がある。しかし、「距離」の定義にはさまざまな方法がある。
一般的な方法の一つは、いわゆる「ユークリッド距離」だ。ユークリッド距離では、2つの行の対応する位置にある値の差をそれぞれ二乗して合計し、その合計の平方根を行間の距離とする。直角三角形の2辺の長さの二乗の和の平方根が斜辺の長さになるという、ピタゴラスの定理を思い浮かべるとよい。
もう一つの距離の尺度はあまり一般的ではないが、機械学習などの最適化問題を解くうえで特に有用だ。「マンハッタン距離」と呼ばれ、2つの行の対応する値の差の絶対値を合計したものにすぎない。
ノルムの内側
実際、マンハッタン距離とユークリッド距離は、統計学者が「ノルム」と呼ぶものの例である。マンハッタン距離、すなわち1ノルムは、差の1乗の和の1乗根であり、ユークリッド距離、すなわち2ノルムは、差の2乗の和の平方根である。3ノルムは差の3乗の和の立方根であり、以下同様に無限大まで続く。
論文でMITの研究者、応用数学のポスドク研究員Richard Pengと、電気工学・コンピューターサイエンスの大学院生Michael Cohenは、あらゆるノルムのもとで行列を圧縮する際に、自分たちのアルゴリズムが最適であることを示している。しかしPengによれば、「私たちが本当に重視していたのは1ノルムでした」。
どのノルムを使う場合も、行列の圧縮ではまず、元の行列の各行に「重み」を割り当てる。行の重みは、その行に類似する他の行の数を表し、その行が圧縮後の行列に含まれる確率を決める。含まれる場合、その値は重みに応じて乗算される。たとえば、10行が互いの代わりとして適切で、行列内の他のどの行の代わりにもならないとする。この場合、それぞれが圧縮後の行列に入る確率は10％となる。そのうち1行が選ばれれば、その値はすべて10倍され、代わりに表している残り9行の寄与を反映する。
マンハッタン距離はある意味でユークリッド距離より単純だが、行の重みの計算はより難しくなる。従来、1ノルムのもとで行列を圧縮する最良のアルゴリズムでは、元の行列の列数の2.5乗に比例した行数の行列が得られていた。一方、2ノルムのもとで行列を圧縮する最良のアルゴリズムでは、元の行列の列数とその対数の積に比例する行数の行列が得られていた。
つまり、列数が100の場合、PengとCohenの研究以前に可能だった最良の圧縮結果は、1ノルムでは数十万行の行列だった。2ノルムでは数百行の行列だった。列数が増えるほど、この差は大きくなる。
再帰を手なずける
PengとCohenのアルゴリズムは、1ノルムのもとでも2ノルムの場合と同程度に行列を圧縮する。2ノルムでは、従来のアルゴリズムと同程度に圧縮する。これは、2ノルムでは既存の最良アルゴリズムをそのまま使うためだ。1ノルムでは同じアルゴリズムを使うが、5、6回繰り返し適用する。
この論文の真の貢献は、2ノルムのアルゴリズムが1ノルムのもとでも信頼できる結果をもたらすことを数学的に証明した点にある。Pengによると、1ノルムの重みを計算する方程式は以前から知られていた。しかし「この定義のおかしなところは、再帰的だということです」と彼は言う。「つまり、正しい重みの集合が左辺にも右辺にも現れるのです」。すなわち、ある行列の行の重みをwとすると、それ自体にwを含む数式と等しくなる。 w とすると、それ自体に wを含む数式と等しくなる。
「この定義が存在することは知られていましたが、統計学の研究者たちはそれをどう扱えばよいかわかりませんでした」とPengは言う。「それを見て、『これを使ってどうやって計算すればいいのだろう』と思うのです」。
PengとCohenが証明したのは、まず方程式の右辺にある w を1に設定し、式を評価して、その答えを右辺のwに代入し、さらに同じことを何度も繰り返せば、正しい wのよい近似値にすぐ収束するということだ。
「非常に洗練された数学であり、従来の成果を大きく前進させるものです」と、カリフォルニア大学バークレー校のコンピューターサイエンス教授で、全米科学賞およびコンピューターサイエンス最高の栄誉であるチューリング賞の受賞者Richard Karpは言う。「元の問題を、非常にわかりやすい問題に落とし込んでいます。そこに至る数学的な展開に感銘を受けました」。
この記事は、 MIT News との共同制作で掲載されています。掲載は、世界経済フォーラムが見解を支持することを意味するものではありません。
アジェンダの最新情報を受け取るには、 週刊ニュースレターに登録してください。
著者：Larry HardestyはMIT Newsの寄稿者です。
画像：ノートパソコンを持つ男性にバイナリーコードが投影されている様子を描いたイラスト。REUTERS/Kacper Pempel。
