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

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

Этот метод аппроксимирует оптимальную выборочную оценку важности, повторяя два этапа:

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

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

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

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

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

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

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

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

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

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

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

1. Выберите исходный вектор параметров $\mathbf {v} ^{(0)}$; установите т = 1.
2. Создать случайную выборку $\mathbf {X} _{1},\dots ,\mathbf {X} _{N}$ от $f(\cdot ;\mathbf {v} ^{(t-1)})$
3. Решите для $\mathbf {v} ^{(t)}$, где
   $\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 можно найти аналитически . Ситуации, в которых это происходит,

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

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

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

Псевдокод

// Initialize parameters
μ := −6
σ2 := 100
t := 0
maxits := 100
N := 100
Ne := 10
// While maxits not exceeded and not converged
while t < maxits and σ2 > ε do
    // Obtain N samples from current sampling distribution
    X := SampleGaussian(μ, σ2, N)
    // Evaluate objective function at sampled points
    S := exp(−(X − 2) ^ 2) + 0.8 exp(−(X + 2) ^ 2)
    // Sort X by objective function values in descending order
    X := sort(X, S)
    // Update parameters of sampling distribution via elite samples                  
    μ := mean(X(1:Ne))
    σ2 := var(X(1:Ne))
    t := t + 1
// Return mean of final sampling distribution as solution
return μ

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

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

См. также

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

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

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

Программные реализации

• CEoptim R Пакет
• Novacta.Аналитика .NET-библиотека