機械学習と次元の呪い

初めに

以前の投稿では，MC/QMCには球面集中現象が現れることを見た．これはある種の「次元の呪い」とされる．

具体的には，原点から各データ点までの距離（Euclid距離）を測ることにすると，高次元になるほど，原点から最も近傍にある点までの距離と，最も遠方にある点までの距離の比が1に近づく¹．これは，高次元では様々な特徴量がのっぺりした特徴量に見えてくることを示している．

Samples drawn from $\mathcal{U}$	Samples drawn from $\mathcal{N}$

同様に，あるデータ点からその他のデータ点までの距離を測る，ということを繰り返していくと，高次元では最近傍の点との距離と最遠方の点との距離の比が1に近づく（Erik Bernhardsson: Nearest neighbors and vector models – epilogue – curse of dimensionality）．

Samples drawn from $\mathcal{U}$	Samples drawn from $\mathcal{N}$

次元の呪いの一つの例として，赤穂2022は，

通常データは数値を表形式に並べたデータセットとして与えられる．表の縦方向のサイズがデータ数を表し，それぞれのデータが1行に配置され，データの属性値が列方向に並ぶ．データ数を$N$，属性値の数（次元数）を$P$と表すと，表は$N \times P$の行列のサイズとなる．つまり，見かけのデータの量は$N \times P$となり，$N$が増えても$P$が増えてもデータが増えるように思えるが，一般的には，機械学習の精度は$N$が大きくなるにつれて向上するが，次元数$P$については逆に低下してしまうということが起きる．

と述べている．直感的には，$N \times P$という見かけのデータ量が変わらない限り，機械学習の精度は同じになりそうに感じる．赤穂2022の言っていることは本当だろうか？実験的に検証してみる．

Methods

問題設定

表形式のデータセットで考えるのが分かり易い．scikit-learnから

• wine dataset（ワインの3クラス分類）
• breast cancer wisconsin dataset（乳がん診断結果の2クラス分類）

を取り上げる．データ数$N$，次元数$P$は，それぞれ，

• wine dataset: $N = 178$，$P = 13$，$N \times P = 2,314$
• breast cancer wisconsin dataset: $N = 569$，$P = 30$，$N \times P = 17,070$

だけの見かけのデータ量がある．

素朴なアプローチ

本題ではないので，結果だけ気になる場合は，次章へジャンプ．

先ずは素朴に，与えられたデータ全てを使って分類問題に取り組んでみる．これは，以降の議論のベースラインになる．

機械学習手法として，

• k-nearest neighbors²（KNN, Fix&Hodges1956, Cover&Hart1967）
• Support Vector Machine³（SVM, Boser+1992, Cortes&Vapnik1995, Vapnik1997, Ben-Hur+2001）

を用いる（複数の機械学習手法で同じ傾向が見られるか否かを確認したい，というマインドセットであり，両者の性能を比較する意図は無い）．

特徴量の相関を調べておく．

wine	breast cancer

特徴量の間の相関が強いものが幾つかあり，多重共線性が怖いが，目を瞑っておく（線形な超平面を形成する訳でも無いし，面倒に感じてしまった）．

Feature scalingの効果

良く知られているように，機械学習において特徴量の前処理は重要である（cf. Importance of Feature Scaling）．wine datasetを対象に，元のデータをそのままKNN/SVMに与えた場合と，幾つかのfeature scalingを施してからKNN/SVMに与えた場合を比較する．同時に，近傍点の数$k$や正則化パラメータ$C$を変えながらtest setへの精度の変動を観察する（KNNの重みは一様分布，SVMのカーネルはRadial Basis Function（RBF）カーネルに固定した⁴）．

KNN	SVM

明らかに，feature scalingをせずに機械学習モデルを適用すると精度は中々上がらないことが分かる．一方，

• MinMaxScaler（min-max normalization）
• StandardScaler（standardization / z-normalization）
• PowerTransformer（Yeo-Johnson's power transformation, Yeo&Johnson2000）

のいずれかを行うと，広いパラメータの範囲で精度が90%を超える．"最適"なscalingを選ぶのは難しいが，外れ値に対する堅牢性では，PowerTransformer > StandardScaler > MinMaxScalerの順に堅牢らしいので（cf. Compare the effect of different scalers on data with outliers），今回はpower transformationを採用する⁵．

$k$を選んでおく．$k$が小さいほどlocalな構造が見えてくるが，decision boundaryが複雑になり，少しの変化やノイズに敏感となるだろう．一方，$k$を大きくするとdecision boundaryが滑らかに，ノイズに鈍感になる代わりにlocalな構造は見え辛くなりそうだとイメージできる．$k = \sqrt{N}$としたり，cross-validationを通したりして決定するようだが（cf. How to choose the right value of k in K Nearest Neighbor, How to find the optimal value of K in KNN?）今回はえいやっと$k = 1, 2, 4, 8$辺りを選んでおく．

$C$を選んでおく．こちらは逆に，$C$が小さいほどdecision boundaryは滑らかで鈍感に，$C$が大きいほど激しく振動する敏感な境界面を形成する（cf. RBF SVM parameters）．今回は$C = 0.1, 1, 10, 100$辺りにしておく．

Results

Wine dataset

データ数と精度の関係

次元数$P$を$P=13$に固定し，データ数$N$を変化させる．全体の内，20, 40, 60, 80%だけのデータを見ることにする．適当に分割してみたところ，ラベルたちに若干の偏りはあるが，酷く偏っている様子ではなかったので，このまま進む．

KNN	SVM

両手法で，データ数$N$（に対する割合）の増加に伴い，精度が向上する傾向が見られる．これは直感通りだし，赤穂2022の主張（というか，広く知られる事実だと思うのだが）にも合致する．

次元数と精度の関係

データ数$N$を$N=178$に固定し，次元数$P$を変化させる．

KNN	SVM

両手法で，次元数$P$の増加に伴い，精度が向上する傾向が見られる．最近傍法（$k=1$のKNN）でも次元数が増加するにつれて精度が向上しており，これは赤穂2022の内容と食い違う．なぜだろう．．．

Breast cancer dataset

データ数と精度の関係

$P=30$に固定し，$N$を変化させる．

KNN	SVM

先ほどと異なり，$N$に殆ど依存せずに高い精度が出ている．

次元数と精度の関係

$N=569$に固定し，$P$を変化させる．

KNN	SVM

やはり，$P$の増加に伴い，精度が向上する傾向がある．最近傍法（$k=1$のKNN）では$P = 10 \sim 15$の間と$P = 25 \sim 30$の間で，$P$の増加に反して精度が低下しており，少なくともこの部分に限っては赤穂2022に一致している．それ以外は食い違っている気がする．．．

終わりに

赤穂2022の言っていることは分かる．寧ろ，実験でそれが再現されないことの方が分からない，という残念な結末である．

乖離があるとすれば，赤穂2022やErik Bernhardssonは実問題スケールの話をしているのに対し，本稿は比較的小さいToy datasetを使ったところにある．今後，時間を見つけて，Real world datasetsを試すなどしたい．

綺麗に纏まった内容ではないが，個人的には話題として面白いと思っているので，実験のやり直しは宿題として公開することにした．

1. 地球では，東京-ソウル間の距離は1,100 km，東京-サンパウロ間の距離は18,500 kmであり，20倍近くの違いがある．短い休暇で東京（原点）から遊びに行くなら，移動時間のかかるサンパウロより近場のソウルに行きたくなるだろう．一方，高次元の地球では，東京（原点）からソウルまでの距離とサンパウロまでの距離はそう変わらない．もっと言うと，どの国もどの街もほぼ等距離に位置することになるので，ふらっと散歩するのと同じ労力で観光地から観光地へ，外国から外国へ移動できる（距離は延びるので労力も増えている，労力の比が1に近づく）． ↩

2. 名前が似たものに，k-meansがある．混同しないようメモしておくと，k-nearest neighborsは教師有り学習の分類，k-meansは教師無し学習のクラスタリング，という位置付けになる．また，k-meansは初めに散撒く重心点の初期値による性能の散付きが知られている（初期値シードを改良したk-means++（Arthur&Vassilvitskii2007）がある）． ↩

3. 深層学習が現代のレベルまで発展するまでは，機械学習の中ではSVMなどに代表されるカーネル法（cf. Schölkopf&Smola2002, 赤穂2008, Fukumizu2012）が所謂最強の方法であった．勿論，現代でも強力な選択肢の一つであるし，深層学習が真価を発揮できるほどのデータ量が無いとき（Big DataではなくSmall Dataな状況）には最良の選択肢の一つとなるだろう．なお，カーネル法の，特徴量を高次元に射影し，自由度の高い空間で様々な処理（decision boundaryを決定するなど）を行う，という考えは，現代の深層学習にも引き継がれている（と私は解釈している）． ↩

4. 本当は，grid search（例えば，Larochelle+2007）やrandom search（例えば，Bergstra&Bengio2012）などを通して検討するべきなのだろうが． ↩

5. 最近まで，外れ値にも比較的強いstandardizationを実行するのがデファクトスタンダードだと思っており，あまり深く調べたことが無かった．そもそも本稿を執筆するまで，power transformationというものの存在を知らなかった．勉強して良かった． ↩