Revisiting column subset selection through the lens of submodularity

あなたは、巨大なパズルを解こうとしている探偵だと想像してください。しかし、手元にあるのは小さなメモ帳だけです。犯罪現場からの手がかりをすべて書き留めることはできません。なぜなら、あなたのメモ帳はあまりにも小さすぎるからです。ですから、全体像を再構成するために役立つ「最高の」数少ない手がかりを選び出さなければなりません。これは、スマートなコンピュータの訓練や、携帯電話の基地局をどこに設置すべきかを判断することなど、科学やテクノロジーのあらゆる場面で現れる問題です。課題は、そのわずかな手がかりを選ぶ方法が何百万通りも存在することであり、すべての組み合わせをチェックしようとすれば、宇宙の寿命よりも長い時間がかかってしまうということです。

この問題を管理可能なものにするために、数学者たちは「劣モジュラ性（submodularity）」と呼ばれる特別な論理を使用します。これは、「収穫逓減（しゅうかくていげん）の法則」のようなものだと考えてください。最初に手に入れる情報の価値は、通常、最も高いものです。2つ目の情報は依然として有用ですが、すでに一部の絵が見えているため、おそらく1つ目ほどではありません。3つ目はさらに役に立たなくなり、そのように続いていきます。もし問題がこのルールに従っているならば、すべての可能性をチェックする必要はありません。各ステップで利用可能な「最善のもの」を強欲に（グリーディに）掴み取っていけば、膨大な作業を行うことなく、かなり良い結果を得ることができます。

ここで、イルス・イプセン（Ilse Ipsen）とアーヴィンド・サイババ（Arvind Saibaba）による新しい論文が登場します。彼らは特定の種類のパズルに取り組んでいます。それは、巨大な数字の格子（行列）から、全体をできるだけ正確に代表する最高の列を選択するというものです。彼らは「正確さ」を「体積（volume）」というもので測定することに決めました。格子の列を、床から立っている棒だと想像してください。いくつかの棒を選べば、それらは一つの形を作ります。「体積」とは、その形がどれだけの空間を占めるかということです。体積が大きいほど、それらの棒はよりユニークで情報量が多いことを意味します。著者たちは、この体積の「対数」（巨大な数字を扱いやすいサイズに押しつぶす数学的な方法）が、その「収穫逓減」のルールを完璧に満たしていることを証明しました。これは、最高の列を選ぶ問題が、実は劣モジュラな問題であることを意味しており、シンプルで高速な戦略を使って優れた解を見つける道を開くものです。

次に、この論文は、どの列を選ぶのがより優れているかを検証するために、2つの有名なコンピュータアルゴリズムをテストしています。最初の方法は「ブシンガー・ゴールブ（Businger-Golub）」法で、これは、常に今この瞬間に最も急勾配で有望に見える次のステップを選ぶ、強欲なハイカーのようなものです。2つ目の方法は「グー・アイゼンスタット（Gu-Eisenstat）」法で、これは、ある経路を選んで少し歩いた後、以前に踏み出したステップを別のものと入れ替えることで、旅全体がより良くなるかどうかを振り返って確認するハイカーのようなものです。

研究者たちは、なぜより単純な方法が現実の世界でよりうまく機能することが多いのかを説明する、驚くべき発見をしました。データが、その最小特異値が少なくとも1以上になるようにスケール調整されている場合（これは行列に定数を掛けることで達成可能です）、強欲なブシンガー・ゴールブのハイカーは、この特定の指標の下で、絶対的な最大体積の37%以内に到達することが保証されます。ステップの入れ替えを試みて経路を改善しようとする、より複雑なグー・アイゼンスタットのハイカーは、同じ指標の下では、最大値の50%以内にしか到達できないことが保証されています。言い換えれば、フルランクまたは適切にスケールされた行列の場合、単純な強欲なアプローチは、この特定の測定基準において、より複雑な戦略よりも実際により正確なのです！

しかし、この論文は、これがあらゆる状況における魔法の杖ではないことも警告しています。もしデータが乱雑であったり、「ランク不足（rank-deficient）」（つまり、いくつかの列が単なるコピーである状態）であったりする場合、「体積」のルールは崩れ、奇妙な挙動をし始めることがあります。このような難しいケースにおいて、著者たちは「トレース（trace）」と呼ばれる別の測定法を見ることを提案しています。これは、特定の数学的な分解における対角成分の総和に過ぎません。この新しい測定法を用いても、強欲なブシンガー・ゴールブ法は依然として優位性を保ち、その誤差範囲内に留まり、一方で入れ替えを行う戦略は50%にとどまります。

著者たちは、この知見を「対称正定値（symmetric positive-definite）」行列と呼ばれる特殊な格子へと拡張しました。これは、天候パターンの予測やセンサーデータの分析などで登場するものです。彼らは、チョレスキー分解（Cholesky factorization）を用いた同様の「強欲な」アプローチが、一般的な行列における列選択の方法と同様に、これらの格子に対しても同様にうまく機能することを示しました。

結局のところ、この論文は全く新しいアルゴリズムを発明したわけではありません。むしろ、私たちが数十年にわたって使用してきた古い単純なアルゴリズムが、なぜこれほど効果的なのかに光を当てたのです。問題が（適切にスケールされた場合には）「劣モジュラ」の型に適合することを証明することで、著者たちは、強欲なアプローチを信頼するための数学的な理由を与えました。彼らは、時には「常に今ある最善のものを選ぶ」という単純な戦略が、単に速いだけでなく、自分自身を疑い、修正しようとするより複雑な戦略よりも、この特定の指標の下では実際に信頼できるものであることを示しました。これは、ビッグデータの世界において、真っ直ぐな道がしばしば最も正確な目的地へと導いてくれるということを思い出させてくれます。