MADR から ScaleRank へ

要約

t-SNE や UMAP に代わる次元削減を作るため、2020年から「各データ点を1体のエージェントとみなし、局所的なルールで動かして配置を決める」という方向で実験してきました。フォルダには約40本のノートブックが残っていました。

2022年の最終結果では、MADR は Q スコアで他手法に大差をつけていました。ところが同じノートブックで、近い順位（k=5）だけに絞った局所スコアを見ると順位がほぼ逆転します。

理由は Q スコアの定義にあります。Q スコアは「各点から見た他の全点の順位」が元の空間と埋め込みでどれだけずれたかの合計です。遠い順位のずれも近い順位のずれと同じ重さで数えるので、実質的には大域構造の指標になります。その指標を直接最適化すれば、その指標で勝つのは当然です。

そこで新手法より先に、同じ条件で手法を比べる基盤 drbench を作りました。データセット・手法・指標をそれぞれ登録制にして、組み合わせを自動で回し、結果をキャッシュします。距離はすべてユークリッド距離で、既存手法も既定値のまま呼んでいます。

中心になる指標 R_NX(K)

各点について「元の空間での K 近傍」と「2次元での K 近傍」がどれだけ重なるかを測り、ランダム配置なら 0、完全に一致すれば 1 になるよう補正したものです。K を 1 から N まで動かすと、局所（小さい K）から大域（大きい K）までの保存度を1本の曲線で見られます。

R_NX(K) 曲線を見ると、既存手法の得意なスケールがはっきり分かれます。t-SNE は小さい K で最も高く、K が 50 を超えたあたりで MDS や PCA に逆転されます。

8 データ全体で見ても、局所指標と大域指標で1位の手法が入れ替わります。下の表で指標を切り替えると、局所では t-SNE、大域では MDS / PCA が強いことが分かります。

既存手法は「どのスケールを守るか」を内部に暗黙に持っています。ScaleRank はそれをユーザーが指定する分布 p(K) として外に出し、その分布で重み付けした近傍保存を直接最適化します。

1つの三つ組で考える

点 i と近傍サイズ K を決めると、元の空間で i の上位 K 近傍に入る点 j と、入らない点 m があります。2次元で j が m より i の近くにあれば正解です。K を p(K) から引き、j と m を引き、間違っていれば i と j を近づけ、i と m を遠ざけます。初期版はこの三つ組を損失の単位にしていました。現行版では m を一度に20個引きます（後述）。

ノブは γ

p(K) を K^−γ に比例させると、γ=1 では小さい K に重みが集まり（局所寄り、AUC_RNX と同じ重み）、γ=0 では全 K が同じ重み（大域寄り）になります。スライダーで γ を動かすと、どのスケールに力を割くかが変わります。

最適化の失敗ではなく、代理指標の偏り

最初の版は γ=1 でも局所指標が t-SNE に届きませんでした（digits の R_NX@10 が 0.44 対 0.58）。そこで、既存手法の埋め込みを ScaleRank 自身の目的関数で採点しました。もし t-SNE の方が低い値なら最適化がうまくいっていないことになります。

原因は目的関数の作りでした。三つ組の正誤は「遠くの非近傍が少し順位を間違える」ことも同じ重さで数えますが、R_NX(K) が気にするのは2次元の上位 K に入り込んでくる点だけです。そこで一部の三つ組で、m を「いま2次元で i の近くにいるが、本当は近傍でない点」から選ぶようにしました（hard negative）。

初期版の散布図では、クラスタのまわりに点が散っていました。2次元での 10-NN 半径が中央値の 3 倍を超える点を「外れ点」として数えると、t-SNE よりはるかに多く出ていました。

2 種類の外れ点

• Pollen の外れ点は元の空間でも孤立していました（10-NN 半径が中央値の 3.9 倍）。MDS でも 16% 出ます。これはある程度忠実です。
• 階層クラスタ（hier_blobs）の外れ点は元の空間では普通の密度でした（1.06 倍）。手法が作った人工物です。

犯人は hard negative と「anti-hub」

hard negative を切ると、hier_blobs の外れ点は 23% から 2% に減りました。外れる点には共通点があり、他のどの点の近傍リストにもほとんど入らない点、いわゆる anti-hub でした。高次元のデータでは、一部の点が多くの点の近傍になり（hub）、逆にほとんど誰の近傍にもならない点（anti-hub）が大量に生まれます。これを hubness と呼びます。

どんな力が働いているか

学習中に各点が受ける力を、勾配の項ごとに分解し、「自分のクラスタの中心から外向き」の成分を測りました（初期版、hier_blobs、エポック 700）。

外れ点への正味の力は内向きですが、他の点より弱い（−0.013 対 −0.038）。学習の後半にクラスタの芯が縮んでいく（中心からの距離 3.5 → 0.6）中で、押し出されるというより取り残されています。近傍関係が非対称なことが根本原因で、t-SNE は点ごとの帯域幅（perplexity の較正）でこれを打ち消しています。

試した対策

初期版で局所指標の差が大きかったのは、高次元ガウス分布でできた2つの合成データです（hier_blobs で 0.24 対 0.34、density_blobs で 0.31 対 0.41）。目的関数を K≈10 に集中させた版（帯域プロファイル）で、t-SNE と同じ土俵にそろえて調べました。

• hier_blobs: hard negative があると、ScaleRank は自分の目的関数で t-SNE に負けます。hard negative が目的関数そのものを歪めているということです。外すと t-SNE にほぼ並び、目的関数でも上回りました。
• density_blobs: 目的関数では t-SNE を上回っているのに、R_NX@10 では負けています。目的関数と評価指標のずれがまだ残っています。
• スケールの配分: γ=1 は設計上、K>10 にも多くの重みを割きます（図6）。digits では K=10 に集中させると R_NX@10 が 0.599 になり、t-SNE（0.583）を上回りました。

hard negative をデータに合わせて調整するのではなく、損失関数の形で同じ効果を出せないかを考えました。1つの近傍 j に対して非近傍 m を Q 個まとめて引き、次の損失を使います（対照学習の InfoNCE と同じ形）。

• Q=1 のときは初期版の三つ組と同じ式です（テストで一致を確認）。
• Q を増やすと、いま2次元で i の近くにいる m ほど q_im が大きく、押し出す力も大きくなります。m は一様に引くだけなのに、近くに入り込んでいる非近傍が自動的に強く効く、hard negative の滑らかな版になります。
• Q を大きくするほど t-SNE に近づくことも知られています（Damrich ら 2023）。Q は γ と並ぶ、もう1つの「局所か大域か」のノブになります。

Q を振ってみる

調整に使ってきた4データで、hard negative なしの状態から Q を 1 → 5 → 20 → 100 と増やしました。

Q=20 で1点あたり8グループにすると、32グループとほぼ同じ質を 1/4 の計算で出せました。これを現行の既定値（n_neg=20, per_point=8, hard=0）にしました。8 データ × 3 seed での比較が次の表です。

低次元の多様体では局所が下がる

すべてのデータで良くなったわけではありません。s_curve（2次元の曲面を3次元に埋め込んだもの）では局所が 0.830 から 0.797 に下がりました。一様乱数の2次元正方形を復元させる単純なテストでも、同じ傾向がはっきり出ます。

現行版で γ = 1 / 0.5 / 0 を 8 データ × 3 seed で走らせ、既存7手法と比べました。縦軸に局所（R_NX@10）、横軸に大域（距離相関）をとると、γ=1 と 0.5 は8データすべてで、両方の軸で上回る既存手法がない位置にあります。γ=0 は2つのデータで既存手法に負けました（density_blobs で PaCMAP、s_curve で TriMap）。

γ を下げたときの振る舞い（新しい実験）

8 データの平均で見ると、現行版は軌跡全体が局所寄りに移動しています。γ=1 では初期版より局所が高い一方、γ=0 まで下げても大域は初期版ほど上がりません（距離相関 0.863 対 0.906）。負例を多くすると t-SNE に近づく性質が、γ を下げても残るためと考えられます。また、どちらの版でも γ を下げるほど外れ点が増えます。

散布図で見ると、t-SNE はクラスタをきれいに分けますがクラスタ同士の位置関係は保ちません。MDS は位置関係を保ちますがクラスタが重なります。ScaleRank はその中間で、クラスタを分けつつ配置も保とうとします。初期版で目立ったクラスタまわりの散らばりは、現行版では少なくなっています。

既定値の t-SNE や UMAP に負けなくても、パラメータを調整すれば ScaleRank の位置まで届くかもしれません。そこで t-SNE は perplexity {5, 30, 100, 300} × exaggeration {1, 2, 4} とランダム初期化の 13 設定、UMAP は n_neighbors {5, 15, 50, 200} × min_dist {0, 0.1, 0.5, 0.99} とランダム初期化の 17 設定を、8 データ × 3 seed で走らせました。

• どのデータでも、30 設定のどれも、局所と大域の両方で ScaleRank を上回りませんでした。データごとに最良の設定を選んでも同じです。
• t-SNE は perplexity を上げると大域が上がる（8 データ平均 0.52 → 0.71）代わりに局所が下がります（0.543 → 0.415）。exaggeration を上げると局所が大きく下がり、外れ点も増えます。
• UMAP は n_neighbors を上げても大域が 0.43 前後で頭打ちになり、min_dist はほとんど効きません。
• 差が小さいのは s_curve と density_blobs で、調整した t-SNE が ScaleRank の近くまで来ます。

ScaleRank のどこまでが新しいかを確かめるため、関連する研究を調べました。結論から言うと、個々の要素の多くはすでに知られています。

新しい可能性があるのは次の組み合わせです。利用者が任意のスケール分布 p(K) を与え、それで重み付けした近傍の保存を目的関数とし、そこからサンプリングの規則（K を p から引き、正例を上位 K から、負例をその外から引く）と三つ組の重みを導いていること。この組み合わせをそのまま述べた文献は見つかりませんでした。

ただし、多重スケール t-SNE のスケールの重みを p(K) に合わせて変えるのは素直な拡張です。それとの違いを実験で示せない限り、新しさは弱いと考えています。次に比べるべき相手は、p(K) で重みを変えた多重スケール t-SNE、DREAMS の λ の掃引、対比学習での負例の数の掃引です。

ここまでの ScaleRank は、各点から見た全点の順位表（N × N）を持っていたので、1 万点程度が限界でした。そこで順位表をやめ、O(N log N) の大きさの構造だけで同じ目的関数を最適化する版を作りました。

• 1〜100 位は、正確な k 近傍で求める。
• それより大きい順位は、何段階かのランダムな部分標本から推定する。大きさ n の部分標本で a 番目に近い点は、全体ではおよそ a·N/(n+1) 位にあたる。これで各点に「距離 → 順位」の表を作る。
• 負例は、エポックごとに一様に引き直した候補を表で順位付けし、順位が K を超えるものから選ぶ。

8 データ × 3 seed で元の版と比べると、差はどの指標でもほぼ ±0.01 に収まりました（表5）。評価も、1 万点を超えるデータでは 2000 行だけを使って推定するようにしました。各指標は行ごとの値の平均なので、この推定に偏りはありません。

MNIST と Fashion-MNIST の全 7 万点（PCA で 50 次元）で試した結果が表6と図21です。

• 大域（距離相関）は、ScaleRank が t-SNE や UMAP よりはっきり高くなりました。
• 一方、局所（R_NX@10）は N が大きくなると弱くなります。MNIST の γ=1 では 1 万点で 0.27 だったのが 7 万点で 0.10 になり、t-SNE（0.39）の約 4 分の 1、UMAP と同じくらいです。

図21 では、ScaleRank γ=1（neg_scale 0.5）は数字ごとのまとまりを保つものの、各クラスが小さな塊に分かれ、周りに散らばる点も多くなっています。γ=0 は全体の配置を保つ代わりに、クラスが重なります。

局所が N とともに弱くなる理由

負例の数 Q を固定したまま N を大きくすると、Q 個の負例が代表する「それ以外のすべての点」が増え、反発が相対的に弱まります。対比学習で知られている性質で（Damrich ら 2023）、負例を少なく引く UMAP に近い振る舞いになります。

そこで、負例の項に重み w = ((N−1−K)/Q)^a をかける設定（neg_scale = a）を入れました。a = 0.5 で局所はほぼ 2 倍（MNIST 0.10 → 0.20、Fashion-MNIST 0.12 → 0.20）になりますが、t-SNE にはまだ届きません。小さいデータでは密度相関が下がる（digits で 0.66 → 0.48）ので、既定値にはしていません。

MNIST の 1 万点では、ほかの設定も試しました。γ を上げると局所は最大 0.36（γ=2）、負例を 100 個にすると 0.35、neg_scale 0.5 で 0.36 になりました（既定の γ=1 は 0.28、t-SNE は 0.45）。1 点あたりの組の数を 4 倍にしたり、エポックを 800 から 2000 に増やしたりしても、ほとんど変わりませんでした（0.29）。

データをブラウザの外に出さずに使えるように、ScaleRank を Rust で書き直し、WebAssembly でブラウザ上で動くアプリにしました。比較用に t-SNE と UMAP も同じ Rust のコードに入れ、利用者が指示したときだけ計算します。近似 k 近傍（NN-descent）も実装しましたが、50 次元・7 万点では総当たり（10 スレッドで 4.3 秒）より速くならなかったので、今は総当たりを使っています。

Rust 版が参照実装と同じものを計算していることを、drbench で確かめました（表7）。t-SNE は openTSNE、UMAP は umap-learn（PCA 初期化）、ScaleRank は Python 版と比べています。

7 万点でも同じで、t-SNE の R_NX@10 は 0.386（openTSNE 0.391）、UMAP は 0.108（umap-learn 0.109）でした。10 スレッドでの計算時間は、t-SNE が 28 秒（openTSNE 64 秒）、UMAP が 22 秒（35 秒）、ScaleRank が 44 秒（Python 版 1347 秒）です。

ブラウザ版は今のところ単一スレッドで、6000 点なら ScaleRank 17 秒、UMAP 11 秒、t-SNE 7 秒ほどです。2 万点では ScaleRank に約 1 分かかるので、マルチスレッド化で短くする予定です。

割り引いて読むべき点

• 局所指標だけなら、t-SNE が全データで1位のまま（平均 0.543 対 現行版 0.511）。
• 現行版は低次元の多様体（s_curve、2次元の正方形）で局所が初期版より下がる。
• γ を下げて大域寄りにすると、外れ点が増え、初期版ほど大域に届かない。
• 外れ点はまだ t-SNE（0.3%）よりずっと多い（8.8%）。一部は本当に孤立した点だが、全部ではない。
• AUC_RNX は γ=1 の目的関数に近いものを測っているので、そこでの優位は割り引く必要がある。R_NX@10 と距離相関は直接は最適化していない。
• ハイパーパラメータは digits、Pollen、hier_blobs、density_blobs で調整した。調整に使っていない4データでも傾向は同じだった。
• 7 万点では局所が t-SNE の約 4 分の 1 まで下がる。neg_scale で約 2 倍になるが、まだ届かない。
• 個々の要素の多くは先行研究にある。p(K) で重みを変えた多重スケール t-SNE や DREAMS とはまだ比べていない。
• ブラウザ版は単一スレッドで、2 万点の ScaleRank に約 1 分かかる。

次の一手の候補

• 2次元での順位を直接推定する. 負例を Q 個引けば「2次元で j より近い非近傍の割合」から j の順位を推定できる。それが K を超えたときだけ罰すれば、R_NX(K) をほぼそのまま最適化できる。
• Q を K に合わせて変える. 大域寄り（大きい K）では Q を減らし、局所寄りでは増やす。γ を下げたときに大域へ届かない問題に効く可能性がある。
• 正例側の非対称性を直す. t-SNE のように点ごとの帯域で「近傍として引かれる量」をならし、anti-hub にも十分な引力を与える。
• 大きい N で局所を保つ. neg_scale の既定値を N に合わせて決める。t-SNE の early exaggeration にあたる段階を試す。
• 先行研究と直接比べる. p(K) で重みを変えた多重スケール t-SNE、DREAMS の λ の掃引、対比学習での負例の数の掃引を drbench に入れる。
• ブラウザで速くする. マルチスレッド化と SIMD で 10 万点を目指す。t-SNE には FFT 版を入れる。

リポジトリ tsjshg/madr の proto/scalerank ブランチで、次のコマンドで再現できます。元データの pickle は親フォルダにある前提です。

uv sync
uv run python scripts/convert_legacy.py      # 2020年の pickle → data/raw/*.npz
uv run drbench run                           # 既存手法（8データ × 3 seed）

# 現行版（ソフトマックス型、既定値）
uv run drbench run -m scalerank:gamma=1.0 scalerank:gamma=0.5 scalerank:gamma=0.0
# 初期版（三つ組 + hard negative）
uv run drbench run -m "scalerank:gamma=1.0,hard=0.3,n_neg=1,per_point=32"
uv run drbench report                        # results/report/ に図と表

# 調査用スクリプト
uv run python scripts/sweep_scalerank.py -d digits --grid n_neg=1,5,20 hard=0.0
uv run python scripts/score_under_objective.py digits --gammas 1
uv run python scripts/diagnose_outliers.py hier_blobs -m tsne "scalerank:gamma=1.0"
uv run python scripts/force_decomposition.py hier_blobs --epochs 700
uv run python scripts/plot_scale_profile.py

# 調整した t-SNE / UMAP との比較（30 設定 × 8 データ × 3 seed の drbench run の後）
uv run python scripts/compare_tuned_baselines.py

# N² を使わない版、Rust 版（scalerank-web の Python バインディングを入れた後）
uv run drbench run -m scalerank_fast:gamma=1.0 scalerank_fast:gamma=0.5 scalerank_fast:gamma=0.0
uv run drbench run -m scalerank_rs:gamma=1.0 tsne_rs umap_rs umap:init=pca
uv run python scripts/compare_fast.py
uv run python scripts/compare_rs.py
uv run drbench run -d mnist70k fmnist70k -s 0 -m tsne umap scalerank_rs:gamma=1.0 scalerank_rs:gamma=0.0 "scalerank_rs:gamma=1.0,neg_scale=0.5"

Rust 版とアプリのコードは tsjshg/scalerank-web にあります。