Метод кросс-энтропии

Метод Монте-Карло для выборки по значимости и оптимизации

Метод кросс-энтропии ( CE ) — это метод Монте-Карло для выборки и оптимизации важности . Он применим как к комбинаторным , так и к непрерывным задачам, как со статической, так и с шумовой целью.

Метод приближает оптимальную оценку выборки важности путем повторения двух фаз: ^[1]

1. Сделайте выборку из распределения вероятностей .
2. Минимизируйте перекрестную энтропию между этим распределением и целевым распределением, чтобы получить лучшую выборку в следующей итерации.

Реувен Рубинштейн разработал метод в контексте моделирования редких событий , где необходимо оценить крошечные вероятности, например, в анализе надежности сети, моделях очередей или анализе производительности телекоммуникационных систем. Метод также применялся к задачам коммивояжера , квадратичного назначения , выравнивания последовательностей ДНК , максимального разреза и распределения буфера.

Оценка посредством выборки по важности

Рассмотрим общую задачу оценки количества

${\displaystyle \ell =\mathbb {E} _{\mathbf {u} }[H(\mathbf {X} )]=\int H(\mathbf {x} )\,f(\mathbf {x} ;\mathbf {u} )\,{\textrm {d}}\mathbf {x} }$,

где — некоторая функция производительности , а — член некоторого параметрического семейства распределений. Используя выборку по важности, эту величину можно оценить как ${\displaystyle H}$ ${\displaystyle f(\mathbf {x} ;\mathbf {u} )}$

${\displaystyle {\hat {\ell }}={\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{g(\mathbf {X} _{i})}}}$,

где — случайная выборка из . Для положительного значения теоретически оптимальная плотность выборки по важности (PDF) определяется как ${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$ ${\displaystyle g\,}$ ${\displaystyle H}$

${\displaystyle g^{*}(\mathbf {x} )=H(\mathbf {x} )f(\mathbf {x} ;\mathbf {u} )/\ell }$.

Однако это зависит от неизвестного . Метод CE направлен на приближение оптимальной PDF путем адаптивного выбора членов параметрического семейства, которые наиболее близки (в смысле Кульбака–Лейблера ) к оптимальной PDF . ${\displaystyle \ell }$ ${\displaystyle g^{*}}$

Общий алгоритм CE

1. Выбрать начальный вектор параметров ; установить t = 1. ${\displaystyle \mathbf {v} ^{(0)}}$
2. Сгенерировать случайную выборку из ${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$ ${\displaystyle f(\cdot ;\mathbf {v} ^{(t-1)})}$
3. Решить для , где ${\displaystyle \mathbf {v} ^{(t)}}$
   ${\displaystyle \mathbf {v} ^{(t)}=\mathop {\textrm {argmax}} _{\mathbf {v} }{\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}}\log f(\mathbf {X} _{i};\mathbf {v} )}$
4. Если сходимость достигнута, то остановиться ; в противном случае увеличить t на 1 и повторить с шага 2.

В ряде случаев решение шага 3 можно найти аналитически . Ситуации, в которых это происходит, следующие:

• Когда принадлежит к естественному экспоненциальному семейству ${\displaystyle f\,}$
• Когда дискретно с конечным носителем ${\displaystyle f\,}$
• Когда и , то соответствует оценке максимального правдоподобия, основанной на тех . ${\displaystyle H(\mathbf {X} )=\mathrm {I} _{\{\mathbf {x} \in A\}}}$ ${\displaystyle f(\mathbf {X} _{i};\mathbf {u} )=f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}$ ${\displaystyle \mathbf {v} ^{(t)}}$ ${\displaystyle \mathbf {X} _{k}\in A}$

Непрерывная оптимизация — пример

Тот же алгоритм CE может быть использован для оптимизации, а не для оценки. Предположим, что задача заключается в максимизации некоторой функции , например, . Чтобы применить CE, сначала рассмотрим связанную стохастическую задачу оценки для заданного уровня и параметрического семейства , например, одномерного гауссовского распределения , параметризованного его средним значением и дисперсией (так здесь). Следовательно, для заданного цель состоит в том, чтобы найти так, чтобы было минимизировано. Это делается путем решения выборочной версии (стохастического аналога) задачи минимизации расхождения KL, как на шаге 3 выше. Оказывается, что параметры, которые минимизируют стохастический аналог для этого выбора целевого распределения и параметрического семейства, являются выборочным средним значением и выборочной дисперсией, соответствующими элитным образцам , которые являются теми образцами, которые имеют значение целевой функции . Худший из элитных образцов затем используется в качестве параметра уровня для следующей итерации. Это дает следующий рандомизированный алгоритм, который совпадает с так называемым алгоритмом оценки многомерного нормального распределения (EMNA), алгоритмом оценки распределения . ${\displaystyle S}$ ${\displaystyle S(x)={\textrm {e}}^{-(x-2)^{2}}+0.8\,{\textrm {e}}^{-(x+2)^{2}}}$ ${\displaystyle \mathbb {P} _{\boldsymbol {\theta }}(S(X)\geq \gamma )}$ ${\displaystyle \gamma \,}$ ${\displaystyle \left\{f(\cdot ;{\boldsymbol {\theta }})\right\}}$ ${\displaystyle \mu _{t}\,}$ ${\displaystyle \sigma _{t}^{2}}$ ${\displaystyle {\boldsymbol {\theta }}=(\mu ,\sigma ^{2})}$ ${\displaystyle \gamma \,}$ ${\displaystyle {\boldsymbol {\theta }}}$ ${\displaystyle D_{\mathrm {KL} }({\textrm {I}}_{\{S(x)\geq \gamma \}}\|f_{\boldsymbol {\theta }})}$ ${\displaystyle \geq \gamma }$

Псевдокод

// Инициализация параметровμ := −6σ2 := 100т := 0макситы := 100N := 100Не := 10// Пока maxits не превышены и не сошлись , пока t < maxits и σ2 > ε // Получаем  N выборок из текущего распределения выборок X := SampleGaussian(μ, σ2, N) // Оценить целевую функцию в выбранных точках S := ехр(−(X − 2) ^ 2) + 0,8 ехр(−(X + 2) ^ 2) // Сортировать X по значениям целевой функции в порядке убывания X := сорт(X, S) // Обновить параметры распределения выборки через элитные выборки  μ := среднее(X(1:Ne)) σ2 := var(X(1:Ne)) т := т + 1// Возвращает среднее значение окончательного распределения выборки как решение return μ

Связанные методы

• Имитация отжига
• Генетические алгоритмы
• Поиск гармонии
• Оценка алгоритма распределения
• Поиск табу
• Стратегия естественной эволюции
• Алгоритмы оптимизации колонии муравьев

Смотрите также

• Перекрестная энтропия
• Расхождение Кульбака–Лейблера
• Рандомизированный алгоритм
• Выборка по важности

Журнальные статьи

• Де Бур, П.-Т., Кроезе, Д.П., Маннор, С. и Рубинштейн, Р.Й. (2005). Учебное пособие по методу кросс-энтропии. Annals of Operations Research , 134 (1), 19–67.[1]
• Рубинштейн, Р.Ю. (1997). Оптимизация моделей компьютерного моделирования с редкими событиями, Европейский журнал операционных исследований , 99 , 89–112.

Реализации программного обеспечения

• Пакет CEoptim R
• Библиотека Novacta.Analytics .NET

Ссылки

1. Рубинштейн, Р.Ю. и Крез, Д.П. (2004), Метод кросс-энтропии: унифицированный подход к комбинаторной оптимизации, моделированию Монте-Карло и машинному обучению, Springer-Verlag, Нью-Йорк ISBN  978-0-387-21240-1 .