次元の呪い

次元の呪いとは、高次元空間でデータを分析および整理する際に生じるさまざまな現象を指しますが、これらは日常経験の3次元 物理空間などの低次元の設定では発生しません。この表現は、動的計画法の問題を検討する際にリチャード・E・ベルマンによって造られました。^{[1] [2]}この呪いは、一般的に、データポイントの数が（適切に定義された意味で）データの本質的な次元に比べて少ない場合に生じる問題を指します。

次元の呪い現象は、数値解析、サンプリング、組合せ論、機械学習、データマイニング、データベースなどの分野で発生します。これらの問題に共通するのは、次元が増加すると空間の体積が急速に増加するため、利用可能なデータがまばらになるということです。信頼性の高い結果を得るためには、必要なデータ量が次元とともに指数関数的に増加することがよくあります。また、データの整理や検索では、オブジェクトが類似した特性を持つグループを形成する領域を検出することが必要になることがよくあります。しかし、高次元データでは、すべてのオブジェクトがさまざまな点でまばらで異なっているように見えるため、一般的なデータ整理戦略が効率的ではありません。

問題によっては、各変数が複数の離散値のいずれかを取る場合や、可能な値の範囲が分割されて可能性の数が有限になる場合があります。変数をまとめると、膨大な数の値の組み合わせを考慮する必要があります。この効果は、組み合わせ爆発とも呼ばれます。最も単純なバイナリ変数の場合でも、可能な組み合わせの数はすでに であり、次元の指数関数です。単純に言えば、次元が追加されるごとに、すべての組み合わせを試すために必要な労力は 2 倍になります。 ${\displaystyle d}$ ${\displaystyle 2^{d}}$

数学的空間に次元を追加すると、体積が指数関数的に増加します。たとえば、点間の距離が 10 −2 = 0.01 以下の単位 間隔 (「1 次元」立方体を視覚化してみてください) をサンプリングするには、等間隔に配置された 10 2 = 100 個のサンプル ポイントで十分です^。隣接^{する点間の間隔が 10 −2 =} 0.01の格子を持つ10 次元単位ハイパーキューブの同等のサンプリングには、10 ²⁰ = [(10 ² ) ¹⁰ ] 個のサンプル ポイントが必要です。一般に、間隔が 10 ^{− nの場合、10 次元ハイパーキューブは、単位間隔である 1 次元ハイパーキューブよりも 10 n (10−1)} = [(10 ⁿ ) ¹⁰ /(10 ⁿ )]倍「大きい」ように見えます。上記の例では、n = 2 です。サンプリング距離を 0.01 にすると、10 次元ハイパーキューブは単位間隔より 10 ¹⁸「大きく」見えるようになります。この効果は、上記の組み合わせ問題と、以下で説明する距離関数の問題の組み合わせです。

数値後方誘導法によって動的最適化問題を解く場合、目的関数は値の組み合わせごとに計算されなければならない。これは、「状態変数」の次元が大きい場合には大きな障害となる。^[3]

機械学習の問題では、高次元の特徴空間で有限の数のデータサンプルから「自然の状態」を学習し、各特徴がさまざまな値を持つようにする必要があります。通常、値の組み合わせごとに複数のサンプルが存在するようにするには、膨大な量のトレーニングデータが必要です。抽象的な意味では、特徴や次元の数が増えると、正確に一般化するために必要なデータの量は指数関数的に増加します。^[4]

一般的な経験則としては、表現の各次元に少なくとも 5 つのトレーニング例が必要であるということです。 ^[5]機械学習および予測性能に関する限り、次元の呪いはピーキング現象^[5]と互換的に使用されます。これはヒューズ現象^[6]としても知られています。この現象は、トレーニングサンプルの数が固定されている場合、分類器または回帰器の平均（期待）予測力は、使用される次元または特徴の数が増えるにつれて最初は増加しますが、特定の次元を超えると、着実に向上するのではなく低下し始めることを示しています。^{[7] [8] [9]}

しかしながら、単純な分類器（例えば、共通の既知の共分散行列を仮定した多変量ガウスモデルの線形判別分析）のコンテキストでは、Zollanvariらは、追加の特徴セットの相対的な累積有効性（分類器にすでに含まれている特徴に関して）がこの追加の特徴セットのサイズよりも大きい（または小さい）限り、これらの追加の特徴を使用して構築された分類器の期待誤差は、それらなしで構築された分類器の期待誤差よりも小さい（または大きい）ことを分析的および経験的に示しました。言い換えれば、追加の特徴のサイズとその（相対的な）累積判別効果の両方が、平均予測力の減少または増加を観察する上で重要です。^[10]

計量学習では、次元が高いほどモデルのパフォーマンスが向上する場合があります。埋め込みを超球面の表面に正規化した後、FaceNetは、あるアブレーション研究で64、256、または512次元ではなく128次元を使用して最高のパフォーマンスを達成しました。^[11]単語埋め込み間のユニタリ不変相違度の損失関数は、高次元で最小化されることがわかりました。^[12]

データ マイニングでは、次元の呪いとは、特徴が多すぎるデータ セットのことを指します。

最初の表を考えてみましょう。この表には、200 人の個人と 2000 個の遺伝子 (特徴) が示されており、1 または 0 は、その遺伝子に遺伝子変異があるかどうかを示しています。このデータ セットに対するデータ マイニング アプリケーションは、特定の遺伝子変異間の相関関係を見つけ、個人が癌にかかっているかどうかを判断するための決定木などの分類アルゴリズムを作成することです。

この分野でのデータマイニングの一般的な方法は、がんの発症につながる遺伝子変異間の関連ルールを作成することです。これを行うには、各個人の遺伝子変異をループして、必要なしきい値を超えて発生する他の遺伝子変異を見つけ、ペアを作成する必要があります。ペアは 2 つから始まり、3 つ、4 つと増えていき、空のペアセットになります。このアルゴリズムは複雑で、個人または行ごとに遺伝子ペアのすべての順列を計算することが必要になる場合があります。グループサイズが r の n 項目の順列を計算する式が次のとおりである場合、任意の個人の 3 ペア順列の数を計算すると、個人ごとに評価する遺伝子のペアは 7988004000 になります。作成されるペアの数は、ペアのサイズが大きくなるにつれて階乗のオーダーで増加します。増加は順列表に示されています (右を参照)。 ${\displaystyle {\frac {n!}{(n-r)!}}}$

上記の順列表からわかるように、次元の呪いに関してデータ マイナーが直面する大きな問題の 1 つは、データ セット内の特徴の数が増えるにつれて、可能なパラメーター値の空間が指数関数的または階乗的に拡大することです。この問題は、考慮すべき関連性や最適な特徴を検索するときに、計算時間と空間の両方に重大な影響を及ぼします。

データ マイナーが、あまりにも多くの特徴を扱う場合に直面する可能性があるもう 1 つの問題は、データ セット内の特徴の数が増えるにつれて、誤った予測や分類の数が増える傾向があるという概念です。上で説明した分類の問題に関して言えば、すべてのデータ ポイントを保持すると、モデル内の 誤検知と誤検知の数が増える可能性があります。

これは直感に反するように思えるかもしれませんが、各個人のすべての遺伝子変異を示す上記の遺伝子変異表を検討してください。各遺伝子変異は、がんと相関しているかどうかに関係なく、アルゴリズムの意思決定プロセスを導くモデルに何らかの入力または重み付けされます。外れ値の変異や、実際にはがんと相関していないが遺伝子変異の全体的な分布を支配している変異がある場合があります。これらの特徴はモデルに不利に働き、最適な結果を得るのが難しくなる可能性があります。

この問題を解決するのはデータ マイナー次第であり、普遍的な解決策はありません。データ マイナーが最初に行うべきステップは、データを調べて、そのデータを使用して問題を解決する方法を理解することです。データ セットから何かを削除する必要があるかどうかを判断する前に、まずデータの意味と発見しようとしていることを理解する必要があります。次に、必要と思われる場合は、特徴選択アルゴリズムまたは次元削減アルゴリズムを作成または使用して、データ セットからサンプルまたは特徴を削除できます。このような方法の 1 つの例は、特徴または発生の標準偏差を計算してデータ セット内の 外れ値を削除するために使用される四分位範囲法です。

ユークリッド距離などの尺度が多数の座標を使用して定義される場合、異なる点のペア間の距離にはほとんど差がありません。

高次元ユークリッド空間の「広大さ」を示す方法の 1 つは、半径と次元 を持つ内接超球面の比率を、辺の長さ を持つ超立方体の比率と比較することです。 このような球の体積は で、 はガンマ関数であり、立方体の体積は です。空間の次元が増加するにつれて、超球面は超立方体の体積に比べて取るに足らない体積になります。これは、次元が無限大に近づくにつれて比率を比較すると明確にわかります。 ${\displaystyle r}$${\displaystyle d}$${\displaystyle 2r.}$${\displaystyle {\frac {2r^{d}\pi ^{d/2}}{d\;\Gamma (d/2)}}}$${\displaystyle \Gamma }$${\displaystyle (2r)^{d}}$${\displaystyle d}$${\displaystyle d}$

${\displaystyle {\frac {V_{\mathrm {hypersphere} }}{V_{\mathrm {hypercube} }}}={\frac {\pi ^{d/2}}{d2^{d-1}\Gamma (d/2)}}\rightarrow 0}$として。${\displaystyle d\rightarrow \infty }$

さらに、中心と角の間の距離はであり、r を固定すると無制限に増加します。 ${\displaystyle r{\sqrt {d}}}$

この意味で、高次元超立方体で点が均一に生成される場合、ほぼすべての点は中心から単位よりもはるかに離れている。高次元では、d次元単位超立方体（頂点の座標）の体積は、大きな次元dの半径を持つ球の近くに集中している。実際、各座標について、立方体内のの平均値は ^{[13]である。}${\displaystyle r}$${\displaystyle \pm 1}$${\displaystyle {\sqrt {d}}/{\sqrt {3}}}$${\displaystyle x_{i}}$${\displaystyle x_{i}^{2}}$

${\displaystyle \left\langle x_{i}^{2}\right\rangle ={\frac {1}{2}}\int _{-1}^{1}x^{2}dx={\frac {1}{3}}}$。

立方体における一様分布 の分散 は${\displaystyle x_{i}^{2}}$

${\displaystyle {\frac {1}{2}}\int _{-1}^{1}x^{4}dx-\left\langle x_{i}^{2}\right\rangle ^{2}={\frac {4}{45}}}$

したがって、原点からの距離の二乗は、平均値d /3、分散 4 d /45 になります。dが大きい場合、 の分布は、中心極限定理に従って、平均 1/3、標準偏差 の正規分布に近くなります。 したがって、高次元で点を均一に生成すると、超立方体の「中央」と角の両方が空になり、すべての体積が「中間」半径の球の表面付近に集中します。 ${\textstyle r^{2}=\sum _{i}x_{i}^{2}}$${\displaystyle r^{2}/d}$${\displaystyle 2/{\sqrt {45d}}}$${\textstyle {\sqrt {d/3}}}$

これはカイ二乗分布の理解にも役立ちます。実際、区間[-1, 1]内のランダムな点に関連付けられた (非心) カイ二乗分布は、d 立方体内のランダムな点の長さの二乗の分布と同じです。大数の法則により、この分布は元の導出の標準偏差の二乗 (σ ^{2 ) の}d倍の周りの狭い帯域に集中します。これによりカイ二乗分布が明らかになり、d立方体の体積のほとんどが半径 の球の境界付近に集中していることも示されます。 ${\displaystyle \sigma {\sqrt {d}}}$

この現象のさらなる展開は次のようになる。実数上の任意の固定分布は、内の点上の積分布を誘導する。任意の固定されたnに対して、ランダムな参照点Qとn 個のランダムなデータ点P ₁ ,..., P _{n の}リストとの間の最小距離と最大距離の差は、最小距離と比較して区別がつかなくなることがわかる。^[14]${\displaystyle \mathbb {R} ^{d}}$

${\displaystyle \lim _{d\to \infty }E\left({\frac {\operatorname {dist} _{\max }(d)-\operatorname {dist} _{\min }(d)}{\operatorname {dist} _{\min }(d)}}\right)\to 0}$。

これは、高次元では距離関数が有用性を失う（例えば、特徴比較アルゴリズムの最近傍基準の場合）ためであるとよく言われます。しかし、最近の研究では、これは1次元分布が独立しており同一に分布している人工的なシナリオでのみ当てはまることが示されています。^[15]属性が相関している場合、データはより簡単になり、より高い距離コントラストが得られ、信号対雑音比が重要な役割を果たすことが判明したため、特徴選択を使用する必要があります。^[15]${\displaystyle \mathbb {R} }$

最近では、コントラスト損失が高次元で呪いを生み出すという議論には概念上の欠陥があるかもしれないと示唆されています。機械学習は、インスタンスをそれぞれの起源の生成プロセスに割り当てる問題として理解でき、クラス ラベルは個々の生成プロセスの象徴的な表現として機能します。呪いの導出では、すべてのインスタンスが単一の高次元生成プロセスの独立した同一の結果であると想定しています。生成プロセスが 1 つしかない場合、(自然に発生する) クラスは 1 つしか存在せず、機械学習は高次元と低次元の両方で概念的に定義が不十分になります。したがって、コントラスト損失が呪いを生み出すという従来の議論は、根本的に不適切である可能性があります。さらに、生成モデルが複数の生成プロセスに対応するように変更されると、コントラスト損失が呪いから祝福に変わる可能性があることが示されています。これは、インスタンスの最近傍がほぼ確実に最も関連のあるインスタンスになることを保証するためです。この観点から見ると、コントラストの喪失は高次元の距離を特に意味のあるものにし、よく議論されるように特に無意味なものではないものにする。^[16]

この効果により、高次元空間での最近傍探索が複雑になる。1つの座標の差をすべての次元に基づく距離の下限として使用して候補を迅速に拒否することはできない。^{[17] [18]}

しかし、最近になって、次元の数だけでは必ずしも困難が生じるわけではないことが観察されている。 ^[19]関連する次元を追加することでコントラストを高めることもできるからだ。さらに、結果のランキングでは、近い次元と遠い次元を識別することが依然として有用である。しかし、無関係な（「ノイズ」）次元は、上記のようにコントラストを低下させる。時系列分析では、データが本質的に高次元であるため、信号対雑音比が十分に高い限り、距離関数も確実に機能する。^[20]

高次元が距離関数に及ぼすもう1つの影響は、距離関数を使用してデータセットから構築されたk近傍（k-NN）グラフに関するものです。次元が増加すると、不均衡な数のハブ（平均よりも多くのk -NNリストに現れるデータポイント）の出現により、 k -NNダイグラフの入次数分布は右側にピークを持つように歪んでいきます。 ^{[21]この現象は、}分類（ k -NN分類器を含む）、半教師あり学習、クラスタリングのさまざまな手法に大きな影響を与える可能性があります。^[22]また、情報検索にも影響します。^[23]

2012年の調査で、Zimekらは高次元データの異常値検索において以下の問題があることを明らかにした。 ^[15]

1. スコアと距離の集中：距離などの導出値は数値的に類似するようになる
2. 無関係な属性: 高次元データでは、かなりの数の属性が無関係である可能性があります。
3. 参照セットの定義: ローカルメソッドの場合、参照セットは最近傍ベースであることが多い
4. 異なる次元に対する比較不可能なスコア: 異なるサブスペースは比較不可能なスコアを生成する
5. スコアの解釈可能性: スコアはもはや意味を伝えないことが多い
6. 指数関数的な探索空間: 探索空間を体系的にスキャンすることはできなくなりました
7. データスヌーピングバイアス：大規模な検索空間を考えると、望ましい有意性ごとに仮説が見つかる可能性がある
8. ハブ性: 特定のオブジェクトは、近隣リスト内で他のオブジェクトよりも頻繁に出現します。

分析された専門的な方法の多くは、これらの問題のいずれかに対処していますが、未解決の研究課題が数多く残っています。

驚くべきことに、予想された「次元の呪い」の困難にもかかわらず、最も直接的な方法に基づく常識的なヒューリスティックスは、高次元の問題に対して「ほぼ確実に最適な結果をもたらすことができる」。^[24]「次元の祝福」という用語は、1990 年代後半に導入された。^[24] ドノホは「ミレニアム宣言」で、「次元の祝福」が将来のデータ マイニングの基礎となる理由を明確に説明した。^[25]次元の祝福の効果は多くのアプリケーションで発見され、測度の集中現象にその基礎が見出された。^[26]次元の祝福現象の 1 つの例は、大きな有限ランダム セットからランダム ポイントを高い確率で線形に分離できることである。このセットが指数関数的に大きい場合でも、このランダム セット内の要素の数は次元とともに指数関数的に増加する可能性がある。さらに、この線形関数は、最も単純な線形フィッシャー判別式の形式で選択できる。この分離可能性定理は、一般的な一様対数凹分布、立方体の積分布、その他多くの確率分布族（最近^[26]でレビューされた）など、幅広いクラスの確率分布に対して証明されました。

「次元の恩恵と次元の呪いは表裏一体である。」^[27]たとえば、高次元空間における本質的に高次元の確率分布の典型的な特性は、ランダムな点から選択された点までの二乗距離が、高い確率で平均（または中央値）二乗距離に近いというものである。この特性は、データの予想される幾何学と高次元データのインデックス作成を大幅に簡素化する（恩恵）^[28]が、同時に、高次元での類似性検索を困難にし、役に立たなくする（呪い）。^[29]

Zimekら^[15]は、次元の呪いの典型的な形式化はiidデータに影響を与えるが、各属性で分離されたデータを持つことは高次元でも容易になると指摘し、信号対雑音比が重要であると主張した。つまり、信号を追加する属性ごとにデータは容易になり、データにノイズ（無関係なエラー）のみを追加する属性では困難になる。特に、教師なしデータ分析では、この効果はスワンピングとして知られている。