A scalable version of MADD for big-data classification

新しい人が混み合った部屋に入ってきたとき、その人の「最も近い友人」を見つけようとしている場面を想像してみてください。コンピュータサイエンスの世界では、これは**分類（classification）**と呼ばれます。新しいデータポイントがどのグループに属するかを、それがどのグループに最も近いかを見て判断することです。

長い間、コンピュータは距離を測るための単純な定規として**ユークリッド距離（Euclidean distance）**を使用してきました。しかし、ここにひねりがあります。高次元の世界（遺伝子配列や高解像度画像のように、数百または数千の特徴を持つデータ）では、その定規は役に立ちません。それは、全員が非常に遠くに立っているため、全員が等しく遠くに見えてしまう部屋で、誰が一番近いかを判断しようとするようなものです。コンピュータは混乱し、「近傍（neighborhood）」の構造が崩れ、分類に失敗してしまいます。

これを解決するために、科学者たちは**MADD（Mean Absolute Difference of Distances：距離の平均絶対差）**という、よりスマートな定規を考案しました。AからBへの距離を単に測るのではなく、MADDは「Aから他の全員への距離は、Bから他の全員への距離と比較してどうなっているか？」と問いかけます。もしAとBが同じグループであれば、この差はごくわずかです。もし異なるグループであれば、この差は非常に大きくなります。これは、高次元において完璧に機能する素晴らしいトリックです。

しかし、落とし穴があります。

MADDは動きが遅いです。2点間の距離を測定するために、部屋にいる「すべての他の人」を見なければなりません。データセットが小さい（小さな部屋）場合は問題ありません。しかし、大規模な群衆（ビッグデータ）の場合、MADDはあらゆるペアに対して数学の問題を解かなければなりません。論文によると、16,384個の訓練サンプルがある場合、MADDはわずか5,000人の新しい人々を分類するためだけに、6.5時間以上を要します。これは、まるで虫眼鏡を使って一本一本の藁をすべてチェックしながら、干し草の山の中から針を探しているようなものです。機能はしますが、非常に時間がかかります。

大きなアイデア：「代表者部隊（Representative Squad）」

この論文の著者たちはこう問いかけました。「本当に群衆全員に聞く必要があるのだろうか？ それとも、少数の賢い代表者に聞くだけでいいのではないだろうか？」

彼らは、**スケーラブルなバージョンのMADD（MADDscと呼ばれる）**を提案しました。新しい人をすべての16,384人と比較する代わりに、コンピュータは非常に小さく、かつ非常にスマートな「代表者部隊（squad）」を選び出します。この部隊は、**決定論的点過程（Determinantal Point Process: DPP）**という高度な数学ツールを使用して選ばれます。

DPPを、非常に好みにうるさいパーティー・プランナーだと考えてみてください。もしあなたがランダムに人を選んで友人のグループを作ろうとしたら、同じコーナーに座って見た目がそっくりな5人を集めてしまうかもしれません。しかし、DPPは異なります。DPPは、似たような人を積極的に避けます。これにより、部隊が部屋のあらゆるコーナーから多様な人々を含むようにし、全員に話を聞かなくても、群衆全体の「雰囲気」を捉えることができるのです。

この部隊（数千人ではなく、わずか50人や100人程度の規模）を使用することで、コンピュータはMADDの計算をわずかな時間で行うことができます。

• 結果： 彼らのテストでは、この新しい手法は、遅いオリジナルのMADDとほぼ同等の精度を維持しながら、劇的に高速化されました。4,096個のサンプルを持つデータセットにおいて、新しい手法は約472秒かかったのに対し、旧来の手法は1,249秒を要しました。これは大幅なスピードアップです！

巨大なデータセットのための「超高速」トリック

もし群衆があまりにも巨大で、部隊を選ぶことさえ時間がかかりすぎる場合はどうすればよいでしょうか？ 著者たちは、**ランダム・フーリエ特徴量（Random Fourier Features: RFF）**と呼ばれる第2のトリックを追加しました。

膨大な数の本がある図書館で、似た本を探さなければならないと想像してください。すべてのページを読む代わりに、テキストをシンプルなコードに変換する魔法のスキャナーを使用します。このコードは、本の「本質」を保持したまま、ポケットに収まるほど短く簡潔なものです。RFFは、部隊の選定における数学的プロセスに対してこれを行います。

25,000個の訓練サンプルを持つデータセットでテストを行った際：

• オリジナルのMADD法は、メモリ不足でクラッシュしました（文字通り、データを保持することができませんでした）。
• 「魔法のスキャナー」を使わないMADDsc法は、15時間以上かかりました。
• 「魔法のスキャナー（RFF）」を用いたMADDsc法は、25分未満（具体的には1,468.68秒）で完了しました。

本当にうまくいったのか？

著者たちは単に推測したわけではありません。確信を持つために、各シナリオに対して25回のシミュレーションを実施しました。彼らは以下のデータで手法をテストしました：

1. 合成データ（Synthetic Data）： 正解が分かっている、作られたデータ。
2. 実データ（Real Data）： 心拍、電力使用量、センサーの読み取り値など、UCR Time Series Classification Archiveから取得した実世界の時系列データ。

シミュレーションにおいて、新しい手法（MADDsc）は一貫して競争力があり、特にデータの形状が複雑であったり混合されていたりする場合、ランダムフォレストやサポートベクターマシン（SVM）といった他の人気のある手法をしばしば上回りました。実世界のテストでも非常に優れた性能を示し、多くの場合、1位または2位に入りました。例えば、「Synthetic Control Chart」データセットでは、標準的な最近傍法（nearest-neighbor method）が**9.13%のエラーを出したのに対し、MADDscはわずか1.29%**のエラーしか出しませんでした。

彼らがやらなかったこと（および回避したこと）

この論文が主張していないことを知っておくことも重要です。

• 彼らは、単純なランダムサンプリング（目を閉じて指をさして選ぶ方法）を否定しました。ランダムな選択は、データの重要な構造を見落としやすく、パフォーマンスが悪化することを示しました。
• 彼らは、この手法が「あらゆる」種類のデータに対して永遠に機能すると主張したわけではありません。彼らは、より複雑なバージョンの手法（gMADDと呼ばれる）については、適切なコードを導き出すための数学が複雑すぎるため、まだ「魔法のス Scanner（RFF）」のトリックを使用できないと述べています。これは将来の研究者が解決すべき課題である可能性を示唆しています。
• 彼らは、この手法が「完璧」あるいは「解決済み」であるとは言っていません。彼らのシミュレーションにおいて、エラー率は元の遅い手法と非常に近い（通常1%以内）ことを示しましたが、真の主役は「スピードの向上」でした。

結論

この論文は、両方を手に入れることができる（ケーキを食べながら、それを食べることもできる）ことを証明しています。遅くて正確な方法か、速くて不正確な方法かのどちらかを選ぶ必要はありません。群衆全員に聞く代わりに、スマートで多様な「代表者部隊」を選び、最大のデータセットに対しては巧妙な数学的ショートカットを使用することで、精度を損なうことなく大量のデータを迅速に分類できるのです。

著者たちがテストで示したように、このアプローチにより、以前は遅すぎたりメモリが足りなかったりした「ビッグデータ」の問題に対して、強力なツールであるMADDを使用することが可能になります。これはスピードへの勝利であり、同時に精度への勝利でもあり、数学的な誠実さを保ったまま実現されています。