Методы оптимизации соответствуют методам выборки?

Из любого общего алгоритма выборки можно получить алгоритм оптимизации.

Действительно, чтобы максимизировать произвольную функцию , достаточно извлечь образцы из . При достаточно малых значениях эти выборки окажутся вблизи глобального максимума (или на практике локального максимума) функции . $f: \textbf{x} \rightarrow f(\textbf{x})$ $g \sim e^{f/T}$ $T$ $f$

Под «выборкой» я подразумеваю рисование псевдослучайной выборки из распределения с учетом функции логарифмического правдоподобия, известной с точностью до константы. Например, выборка MCMC, выборка Гиббса, выборка луча и т. Д. Под «оптимизацией» я подразумеваю попытку найти параметры, максимизирующие значение данной функции.

Возможно ли обратное? Учитывая эвристику, чтобы найти максимум функции или комбинаторного выражения, можем ли мы извлечь эффективную процедуру выборки?

Например, HMC, кажется, использует информацию градиента. Можем ли мы построить процедуру выборки, которая использует BFGS-подобное приближение гессиана? (редактировать: очевидно да: http://papers.nips.cc/paper/4464-quasi-newton-methods-for-markov-chain-monte-carlo.pdf ) Мы можем использовать MCTS в комбинаторных задачах, можем ли мы перевести это в процедуру отбора проб?

Контекст: сложность выборки часто заключается в том, что большая часть распределения вероятностей находится в очень маленькой области. Существуют интересные методы для поиска таких регионов, но они напрямую не переводятся в объективные процедуры отбора проб.

Редактировать: Теперь у меня есть ощущение, что ответ на этот вопрос несколько эквивалентен равенству классов сложности #P и NP, что делает ответ вероятным «нет». Это объясняет, почему каждый метод выборки дает метод оптимизации, а не наоборот.

sampling optimization Артур Б.
источник

Хотя я думаю, что у меня есть общепринятое понимание большинства слов в этом вопросе, я не уверен, что он получает после. Не могли бы вы сказать немного более точно, что вы подразумеваете под «выборкой» и что именно будет «оптимизировано»? Похоже, вы неявно предполагаете, что ваши читатели имеют в виду конкретную обстановку, в которой участвует «распространение» (или его семейство?) И в которой предполагается конкретная цель, но можно только догадываться о том, что вы действительно намереваетесь, когда делаете такие широкие заявления, как те, которые появляются в последнем абзаце.

whuber

Артур Б.

Существует естественное сопоставление между имитацией отжига и отбором проб MCMC. Менее прямое отображение между HMC и градиентным спуском (если вы щурились). Мой вопрос заключается в том, можно ли сделать это более систематическим. Трудность выборки часто заключается в том, что большая часть распределения вероятностей находится в очень маленькой области. Существуют интересные методы для нахождения этого региона, но они напрямую не переводятся в объективные процедуры отбора проб.

Артур Б.

Пожалуйста, измените ваш вопрос, чтобы включить эти пояснения. Это очень важно, потому что ваше (несколько специализированное) использование слова «выборка», хотя и уместно в вашем контексте, отличается от того, что многие читатели могут понять. Кроме того, ваше объяснение «оптимизации», хотя и правильное, по-видимому, не помогает сделать его значение достаточно точным здесь: характеристика того, что такое «заданная функция» и как она может быть связана с «выборкой», была бы полезной дополнением.

whuber

Теперь лучше?

Артур Б.

Методы оптимизации соответствуют методам выборки?

Ответы: