n次元空間での登山：隣の発見

1次元の登山では、現在のポイントの左と右の小さなデルタを2つ試してみましょう。目的関数のより高い値。どのようにn次元空間に拡張するのですか？どのようにして、n次元空間の隣人を定義しますか？ 2^n近傍（次元のそれぞれに適用されるデルタ）を試す必要がありますか？n次元空間での登山：隣の発見

出典

2017-01-21 max_max_mir

[高次元データに最も近い隣を見つけるためのこの回答]（http://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data）を参照してください。 – macco

隣人の各ペアを比較する必要はなく、隣人のセットを計算する必要があります。半径がデルタのサークル（より高い次元の球/超球）上に移動し、次に最高値を持つものを「登る」。いずれの場合でも、現在の解の近傍を離散化し、各隣人のスコア関数を計算します。 1）グラジエントを算出する（最も急峻な上昇の方向） 2）グラジエントの方向に小さなステップを進める 3）停止する解が変化しない

これらのアルゴリズムの共通の問題は、多くの場合、極大/極小を見つけることだけであることです。 http://sebastianruder.com/optimizing-gradient-descent/

出典

2017-01-21 22:50:28

これは、多次元空間の近傍として考えるべきものを説明しません。例えば、質問で示唆されているように、n個の基本方向に2n個の近傍、または{-delta、+ delta}^n超立方体については2^n近傍、または{-delta、 0、+δ} – Gassa

実数を扱う場合、私たちには選択可能な無数の隣人があります。 1Dの場合、デルタが与えられた場合、我々は2つの近傍のみを有する。 2次元では、すでに円に無限の数の無限大を持つ円が得られます。もちろん、我々は方向（2^2 = 4）のためだけに入ることができます。おそらく近傍を離散化することができます（2Dではグリッド、3Dではボクセルグリッドが解決策になります）。 –

O（2^n）近傍ではなくO（n）近傍のみを必要とする多次元探索アルゴリズムの一例は、下記のTorczonシンプレックス法です。 http://www.caam.rice.edu/tech_reports/1990/TR90-07.pdf。私は、Torczonのシンプレックス法はコンバージェンスの証明（いくつかの合理的な条件が与えられれば局所的な最適への収束）があるので、より広く知られているNelder-Mead法でこれを選択しました。

出典

2017-01-22 05:34:52 mcdowella

n次元空間での登山：隣の発見

答えて

関連する問題