Lloyd's $K$-Means Clustering Algorithm Is Frank-Wolfe in Disguise

あなたは、手がかりを追う探偵だと想像してください。しかし、そこにあるのは指紋ではなく、地図上の点、写真のピクセル、あるいは本の中の言葉といった、何千もの散らばった手がかりです。あなたの仕事は、見た目が似ているものに基づいて、これらの手がかりを意味のあるグループに分類することです。これがクラスタリングの本質であり、機械学習の世界における「スーパーパワー」です。コンピュータが、教師から正解を教えられることなく、乱雑なデータの中から隠れたパターンを見つけ出すのを助けてくれます。

この手法の中で、最も古く、かつ最も有名なものの一つが**K-means（K平均法）**です。これは、少しひねりのある「椅子取りゲーム」のようなものだと考えてください。まず、いくつかの「キャプテン（中心点）」を選びます。すると、すべてのデータポイントは、自分が最も近いと感じるキャプテンのもとへと駆け寄ります。次に、キャプテンたちは自分たちの新しいチームの平均的な位置へと移動し、再び全員が駆け寄ります。これを、誰も動かなくなるまで繰り返します。これは、貪欲でステップバイステップなプロセスであり、通常は非常にうまく機能しますが、何十年もの間、数学者たちは、このアルゴリズムが正確に「どれほどの速さ」で最適解を見つけるのか、そしてなぜ時としてループに陥ってしまうのかについて、頭を悩ませてきました。

ここで登場するのが、Frank-Wolfe（フランク・ウルフ）アルゴリズムです。これは、壁に跳ね返る（「射影」と呼ばれる手法）必要のない、複雑な問題を解決するための、異なる種類の最適化ツールです。それは、常に丘の最も急な斜面を下る道を選び、大きな一歩を踏み出しながら、丘の底に到達しようとするハイカーのようなものです。長い間、これら二つの手法——K-meansとFrank-Wolfe——は、まるで別々の近所に住んでいるかのように、全く異なる世界のものに見えていました。しかし、ある新しい論文は、これらが実は「違う帽子を被っているだけの同一人物」であることを示唆しています。

---

大いなる真実：K-meansは変装したFrank-Wolfeである

この論文において、著者であるMichael Pokojovy、J. Marcus Jobe、およびSimon Lacoste-Julienは、幕を引き、LloydのK-meansアルゴリズム（誰もが使用している標準的なバージョン）が、実は巧妙に擬態したFrank-Wolfeアルゴリズムであることを明らかにしました。

この魔法を理解するために、あなたが大規模なパーティーを企画していると想像してみてください。ゲストをグループ分けして、同じ音楽が好きな人々が一緒に座れるようにしたいと考えています。

• 従来の方法（K-means）： いくつかのテーブル（中心）を用意し、全員に最も近いテーブルに座るよう頼みます。その後、テーブルを座っている人々の中心へと移動させます。テーブルが動かなくなるまで、これを繰り返します。
• 新しい洞察： 著者たちは、K-meansがテーブルをゲストの中心へと移動させる際、数学的にはFrank-Wolfeアルゴリズムが丘を駆け下りる大きな一歩を踏み出しているのと全く同じことをしているのだと気づきました。

なぜこれが重要なのでしょうか？ なぜなら、Frank-Wolfeアルゴリズムは、数学的に「クリーン」で、既知の速度制限を持つ、非常に扱いやすいツールだからです。K-meansが「パーティー用の帽子を被ったFrank-Wolfe」であると気づくことで、著者たちは、Frank-Wolfeの明快な数学を用いて、K-meansが仕事を終えるまでに正確にどれくらいの時間がかかるかを証明できるようになったのです。

「空席」問題

K-meansというゲームには、一つ厄介な問題があります。それは、時としてテーブルに誰も座っていない状態が発生することです。パーティーの例えで言えば、全員が別のテーブルに駆け寄ってしまったために、キャプテンが一人取り残されてしまうような状況です。数学的な用語では、これはFrank-Wolfeが通常転がっていく滑らかな丘の中に、「隙間」や「粗い箇所」を作り出します。

著者たちはこの問題を無視するのではなく、正面から取り組みました。彼らは、これらの「空席」の瞬間（彼らはこれを**セミスムース（semismooth）**な目的関数と呼んでいます）を処理できる、より柔軟で新しいバージョンのFrank-Wolfeアルゴリズムを開発しました。彼らは、たとえクラスターが空になっても、アルゴリズムが混乱したり速度が落ちたりしないことを証明しました。アルゴリズムは以前と同様に、効率的に丘を転がり続けます。

「速い」とはどの程度の速さか？

最もエキサイティングな発見は、そのスピードです。著者たちは、K-meansアルゴリズムが**O(1/t)**のレートで良い解に収束することを証明しました。

これを簡単な比喩で説明しましょう。あなたが宝箱に向かって歩いていると想像してください。

• もし、あなたが**O(1/√t)**のレートで歩いていたとしたら、最初は大きな一歩を踏み出しますが、すぐに足取りが重くなり、まるで深い泥の中を歩いているかのように、歩幅がどんどん小さくなってしまいます。
• しかし、K-meansは実際にはFrank-Wolfeであるため、**O(1/t)**のレートで歩きます。これは、あなたの歩幅は小さくなりますが、より予測可能な形で、確実に宝物に近づいていくことが保証されていることを意味します。

決定的なのは、この速度が「最適解からどれだけ離れた地点からスタートしたか」にのみ依存するということを、著者たちが示した点です。データポイントが100万個あろうと（巨大なパーティー）、あるいは数個であろうと、速度の保証は変わりません。これは大きな進展です。なぜなら、従来の理論では、データポイントが増えると非常に複雑で難解になっていたからです。

理論の検証

これが単なる美しい数学的なトリックではないことを確認するために、チームは大規模なシミュレーションを行いました。

• 彼らは、点がつながった「塊（ブロブ）」（カラフルな紙吹雪の雲のようなもの）に見える偽のデータを作成し、K-meansアルゴリズムを数千回実行しました。
• また、画像のピクセルをグループ化して空、草、建物などを分離する「画像セグメンテーション」という実世界のデータセットでもテストを行いました。

あらゆるテストにおいて、「アルゴリズムが現在いる場所」と「到達したい場所」の間の「ギャップ」は、数学が予測した通りに縮小しました。結果をグラフにプロットすると、その線は**-1.0**の傾斜で下降しました。これは、**O(1/t)**の速度を示す数学的な署名です。データが乱雑であったり、クラスターの形状が奇妙であったりしても、アルゴリズムは冷静さを保ち続けました。

アルゴリズムを停止させる新しい方法

最も実用的な教訓の一つは、いつパーティーを終了させるべきかを知る方法です。通常、コンピュータは中心点がほとんど動かなくなった時にK-meansを停止させます。しかし、著者たちはより優れた方法を提案しています。それは、「Frank-Wolfeギャップ」（現在の配置と、次に可能な配置とのスコアの差）が十分に小さくなった時に停止するという方法です。

この新しい停止ルールは、あとどれくらいの「作業」が残っているかを正確に教えてくれる燃料計のようなものです。これは推測よりも信頼性が高く、アルゴリズムが取るべきステップの限界値を明確に提示してくれます。

まとめ

この論文は、新しいK-meansの手法を発明したわけではありません。むしろ、私たちが数十年にわたって使い続けてきた信頼できる古い手法が、実は強力で現代的な数学的ツールの「変装した姿」であったことを明らかにしました。これら二つの世界を繋ぐことで、著者たちはK-meansに対して明確で証明された速度制限を与え、仕事が終わったことを知るためのより良い方法を提示しました。これは、科学における最も身近な道具が、実は私たちが思っていたものとは異なる衣装を着ていることもある、ということを思い出させてくれます。