Агрегировать / экстраполировать разреженные образцы в многомерном пространстве

Question

Представьте, что есть функция, которая оценивает высоту поверхности по координате x и y с плавающей точкой (и дополнительные компоненты в соответствии с размерностью):

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

Это не аналитическая функция, и поэтому производные не могут быть вычислены. Что мне нужно сделать, так это найти направление, в котором поверхность является самой крутой для любой данной пары {x, y}. Одна оценка может быть очень дорогой (подумайте секунды или даже минуты в худшем случае).

Мой типичный подход в двумерном случае - это выборка поверхности в N местах рядом с {x, y}, затем подгонка кривой по этим выборкам и поиск кривой для самой высокой точки, поскольку этот поиск не страдает дорогая оценка:

На изображении выше P0 - заданная координата. {S0, S1, S2, S3} - это 4 случайно расположенных выборки вокруг P0, а PM - самая высокая точка на кривой. Таким образом, вектор PM-P0 является направлением наискорейшего подъема.

Но я понятия не имею, как масштабировать это до N измерений или есть ли намного более умные алгоритмы для этого.

Число измерений потенциально довольно большое (от десятков до сотен), поэтому любой метод, который я в конечном итоге использую, должен работать, когда выборок меньше, чем измерений. Я не ищу точного ответа, это было бы невозможно, но приличная аппроксимация на полпути уже была бы весьма желательна.

пс. Я делаю это в C #, не то чтобы это имело большое значение, но у меня нет доступа к функциям, не связанным с C #.

Answer 1

Похоже, вы пытаетесь оценить градиент из набора случайных выборок вблизи заданной точки.

К сожалению, если у вас есть n размеры, вам нужно минимум n+1 точек, чтобы правильнооценить градиент.При меньшем количестве точек размеры должны выпадать, и вы будете оценивать проекцию градиента с меньшими размерами.Тем не менее, если вы захватите k измерений, есть вероятность, что ваш проект получит sqrt(k/n) длины истинного градиента.

Вот один подход.Предположим, что вы отобрали k+1 случайных точек вокруг вашей точки и далее предположите, что они линейно независимы.Выберите один из них в качестве «источника», и тогда у вас будет k размеров.Найдите еще n-k больше точек, которые ортогональны всем предыдущим, и укажите значение вашего источника.(Это приведет к тому, что эти измерения не будут представлены в градиенте.)

Теперь у вас есть n векторов и оценка точечного произведения градиента с каждым.Возьмите каждый стандартный единичный вектор и запишите его как линейную комбинацию ваших векторов.Та же самая линейная комбинация ваших уклонов даст вам оценку для этого компонента градиента.Сделайте это для всех ваших единичных векторов, сложите их вместе, и вуаля, у вас есть оценка вашего градиента.

Обратите внимание, что если вы пытаетесь использовать некоторые ближние и некоторые дальние точки, некоторые из которыхне являются линейно независимыми, тогда этот подход не будет работать, и вам нужно будет сделать что-то гораздо более сложное.

Answer 2

Мне не совсем понятно, почему вычисление кривой дешевле, чем выборочных точек случайным образом, но это напоминает мне о http://en.wikipedia.org/wiki/Gradient_descent. Вы можете думать о своей проблеме как о попытке оптимизировать разницу высот между текущими местоположение и новая точка. Это может быть быстрее, чем пробовать случайные точки, и это действительно легко обобщить для нескольких измерений

Поскольку функция, вероятно, немонотонно увеличивается, вы можете определить ее в зависимости от границы (в пределах x единиц от начальной точки).