Czy techniki optymalizacji odwzorowują techniki próbkowania?

Z dowolnego ogólnego algorytmu próbkowania można wywnioskować algorytm optymalizacji.

Rzeczywiście, aby zmaksymalizować dowolną funkcję , wystarczy pobrać próbki z . Dla wystarczająco małego próbki te spadną w pobliżu globalnego maksimum (lub lokalnych maksimów w praktyce) funkcji . $f: \textbf{x} \rightarrow f(\textbf{x})$ $g \sim e^{f/T}$ $T$ $f$

Przez „próbkowanie” mam na myśli wyciągnięcie pseudolosowej próbki z rozkładu przy danej funkcji logarytmu wiarygodności znanej ze stałej. Na przykład próbkowanie MCMC, próbkowanie Gibbsa, próbkowanie wiązki itp. Przez „optymalizację” rozumiem próbę znalezienia parametrów maksymalizujących wartość danej funkcji.

Czy możliwe jest odwrócenie? Biorąc pod uwagę heurystykę znajdowania maksimum funkcji lub wyrażenia kombinatorycznego, czy możemy wyodrębnić wydajną procedurę próbkowania?

Na przykład konsola HMC wykorzystuje informacje gradientowe. Czy możemy skonstruować procedurę próbkowania, która wykorzystuje zbliżone do BFGS przybliżenie Hesji? (edytuj: pozornie tak: http://papers.nips.cc/paper/4464-quasi-newton-methods-for-markov-chain-monte-carlo.pdf ) Możemy używać MCTS w problemach kombinatorycznych, czy możemy to przetłumaczyć do procedury pobierania próbek?

Kontekst: trudność w próbkowaniu polega często na tym, że większość masy rozkładu prawdopodobieństwa leży w bardzo małym regionie. Istnieją interesujące techniki znalezienia takich regionów, ale nie przekładają się one bezpośrednio na obiektywne procedury próbkowania.

Edycja: Mam teraz wrażenie, że odpowiedź na to pytanie jest w pewnym stopniu równoważna równości klas złożoności #P i NP, co czyni odpowiedź prawdopodobnie „nie”. Wyjaśnia, dlaczego każda technika próbkowania daje technikę optymalizacji, ale nie odwrotnie.

sampling optimization Arthur B.
źródło

Chociaż myślę, że rozumiem większość słów w tym pytaniu, nie jestem pewien, o co chodzi. Czy mógłbyś powiedzieć nieco bardziej precyzyjnie, co rozumiesz przez „próbkowanie” i co dokładnie byłoby „zoptymalizowane”? Wydaje się, że domyślnie zakładasz, że Twoi czytelnicy mają na myśli szczególne otoczenie, w którym zaangażowana jest „dystrybucja” (lub jej rodzina?) I w którym zakłada się określony cel, ale można jedynie zgadywać, co naprawdę zamierzasz, dokonując takie ogólne stwierdzenia, jak te zamieszczone w ostatnim akapicie.

whuber

Arthur B.,

Istnieje naturalne odwzorowanie między symulowanym wyżarzaniem a próbkowaniem MCMC. Mniej bezpośrednie mapowanie między konsolą HMC a spadkiem gradientu (jeśli zmrużysz oczy). Moje pytanie brzmi, czy można to uczynić bardziej systematycznym. Trudność w próbkowaniu polega często na tym, że większość masy rozkładu prawdopodobieństwa leży w bardzo małym regionie. Istnieją ciekawe techniki znalezienia tego regionu, ale nie przekładają się one bezpośrednio na obiektywne procedury próbkowania.

Arthur B.,

Edytuj swoje pytanie, aby uwzględnić te wyjaśnienia. Jest to kluczowe, ponieważ twoje (nieco wyspecjalizowane) użycie słowa „próbkowanie”, chociaż właściwe w twoim kontekście, różni się od tego, co wielu czytelników może zrozumieć. Wyjaśnienie „optymalizacji”, choć prawidłowe, nie wydaje się pomocne w doprecyzowaniu jej znaczenia w tym miejscu: scharakteryzowanie, czym jest „dana funkcja” i jak można ją powiązać z „próbkowaniem”, byłoby przydatnym uzupełnieniem.

whuber

Czy teraz jest lepiej?

Arthur B.

Czy techniki optymalizacji odwzorowują techniki próbkowania?

Odpowiedzi: