集約/多次元空間においてスパースサンプルを外挿する

Question

は（次元に応じて追加の構成要素）浮動点xが与えられ、y座標面の高さを評価する機能がある想像：

double ComputeElevation(double x, double y, ...., double z) { } 

これは解析関数ではないため、微分は計算できません。私がする必要があるのは、与えられた任意の{x、y}ペアの表面が最も急な方向を見つけることです。単一の評価は非常に高価になる可能性があります（最悪のシナリオでは数秒または数分も考えます）。

2Dの場合の私の典型的なアプローチは、{x、y}に隣接するN個の位置でサーフェスをサンプリングし、それらのサンプルに曲線をフィットさせ、この検索で​​苦しんでいない最高点の曲線を検索することです高価な評価から：

上記画像P0の座標を与えられています。 {S0、S1、S2、S3}は、P0の周りに4つのランダムに配置されたサンプルであり、PMは曲線上の最も高い点である。したがって、ベクトルPM-P0は最急上昇の方向である。

しかし、これをN次元にスケールアップする方法やこれを行うためのよりスマートなアルゴリズムがあるかどうかはわかりません。

次元数は非常に大きく（数十から数百まで）、潜在的にどのような方法でも、次元数よりもサンプル数が少ない場合には機能する必要があります。私は正確な答えを探しているわけではありませんが、それは不可能ですが、半分まともな近似はすでに大歓迎です。

ps。私はC＃でこれをやっていますが、大したことではありませんが、C＃以外の言語機能にアクセスすることはできません。

Answer 1

与えられた点の近くにあるランダムサンプルの集合から勾配を推定しようとしているようです。

残念ながら、nディメンションがある場合は、勾配を正しく推定するには、最低でもn+1ポイントが必要です。ポイントが少なくなると、ディメンションがドロップアウトする必要があり、ディメンションのディメンションが小さくなると推定されます。つまり、kのディメンションをキャプチャすると、プロジェクトで真の勾配の長さがsqrt(k/n)になる可能性があります。

ここに1つのアプローチがあります。あなたのポイントの周りにk+1のランダムな点をサンプリングし、それらが直線的に独立していると仮定します。そのうちの1つを「原点」として選択すると、kの寸法が得られます。もう一つのn-k点を見つけて、それ以前のすべての点と直交する点を見つけて、元の値を入れてください。これらのディメンションはグラデーションでは表現されません。

ここで、nベクトルとグラジエントの内積の見積もりがそれぞれあります。それぞれの標準単位ベクトルをとり、それをベクトルの線形結合として書く。斜面の同じ線形結合は、グラデーションのそのコンポーネントの推定値を与えます。あなたの単位ベクトルのすべてに対してこれを行い、それらを一緒に追加してください。あなたは勾配の推定値を持っています。

いくつかの遠方ポイントを使用しようとしている場合、その一部は線形独立ではありませんが、このアプローチは機能しませんので、はるかに複雑な処理を行う必要があります。

Answer 2

曲線を計算するのがランダムにサンプリング点よりも安いのはなぜか分かりませんが、これは私にhttp://en.wikipedia.org/wiki/Gradient_descentを思い出させます。あなたの問題は、現在の場所と新しい場所との間の標高の差を最適化しようと考えると考えることができます。ランダムな点を試すよりも速いかもしれませんし、複数の次元に一般化するのは本当に簡単です

関数は単調に増加していない可能性が高いので、境界の関係で定義することができます）。