В восхождении на холм для 1 измерения я стараюсь, чтобы два соседа - небольшая дельта слева и одна справа от моей текущей точки, а затем держите ту, которая дает более высокое значение целевой функции. Как расширить его до n-мерного пространства? Как определить сосед для n-мерного пространства? Должен ли я попробовать 2^n соседей (дельта применяется к каждому измерению)?Холм, поднимающийся в n-мерном пространстве: поиск соседа
Вам не нужно сравнивать каждую пару соседей, вам нужно вычислить набор соседей, например. на круг (сферу/гиперсферу в более высоких измерениях) с радиусом дельта, а затем взять тот, который имеет самые высокие значения, чтобы «подняться вверх». В любом случае вы будете дискретизировать окрестности вашего текущего решения и вычислить функцию оценки для каждого соседа. Если вы можете дифференцировать свою функцию, то алгоритмы, основанные на градиентном восхождении/спуске, могут решить вашу проблему: 1) Вычислить градиент (направление самого крутого подъема) 2) Пройти небольшой шаг в направлении градиента 3) Остановить, если решение не изменяется
Общей проблемой с этими алгоритмами является то, что вы часто находите локальные максимумы/минимумы. Вы можете найти отличный обзор алгоритмов спуска/подъема градиента здесь: http://sebastianruder.com/optimizing-gradient-descent/
Это не объясняет, что считать соседи в многомерном пространстве. Например, должно быть только 2n соседей в n кардинальных направлениях или 2^n соседей для гиперкуба {-delta, + delta}^n, как предложено в вопросе, или, может быть, 3^n - 1 соседей для {-delta, 0, + delta}^n? – Gassa
Имея дело с действительными числами, у нас есть бесконечное количество соседей на выбор. В случае 1D, учитывая дельта, у нас есть только два соседа. В 2D мы получаем уже круг с бесконечным числом негров на этом круге. Конечно, мы можем идти только по направлениям (2^2 = 4). Возможно, дискретизируя окрестности (в 2D сетке, в 3D сетка вокселей может быть решением). –
Одним из примеров многомерного алгоритма поиска, которому нужны только соседи O (n) вместо O (2^n), является симплексный метод Торцона, описанный в http://www.caam.rice.edu/tech_reports/1990/TR90-07.pdf. Я выбрал это по более широко известному методу Нельдера-Мида, потому что метод симметрии Торчона имеет доказательство конвергенции (сходимость к локальному оптимуму при некоторых разумных условиях).
Отметьте [этот ответ для поиска ближайшего соседа в данных высокого размера] (http://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data). – macco