Кросс-энтропийный метод - Cross-entropy method

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

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

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

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

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

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

${\ Displaystyle \ Ell = \ mathbb {E} _ {\ mathbf {u}} [H (\ mathbf {X})] = \ int H (\ mathbf {x}) \, е (\ 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 г ^ {*} (\ 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 е (\ cdot; \ mathbf {v} ^ {(т-1)})}$
3. Решить , где${\ Displaystyle \ mathbf {v} ^ {(т)}}$
   ${\ displaystyle \ mathbf {v} ^ {(t)} = \ mathop {\ textrm {argmax}} _ {\ mathbf {u}} {\ 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} ^ {(t-1)})}$
4. Если конвергенция достигнута, остановитесь ; в противном случае увеличьте t на 1 и повторите действия с шага 2.

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

• Когда принадлежит к естественной экспоненциальной семье${\ displaystyle f \,}$
• Когда это дискретный с конечной поддержкой${\ displaystyle f \,}$
• Когда и , то соответствует оценке максимального правдоподобия, основанной на них .${\ Displaystyle Н (\ 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} ^ {(т)}}$${\ displaystyle \ mathbf {X} _ {k} \ in A}$

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

Тот же алгоритм CE можно использовать для оптимизации, а не для оценки. Предположим, проблема в том, чтобы максимизировать некоторую функцию , например ,. Чтобы применить CE, сначала рассматривается соответствующая стохастическая проблема оценки для данного уровня и параметрическое семейство , например, одномерное гауссовское распределение , параметризованное его средним значением и дисперсией (так здесь). Следовательно, для заданного цель состоит в том, чтобы найти так, чтобы это было минимизировано. Это делается путем решения типовой версии (стохастического аналога) задачи минимизации дивергенции KL, как на шаге 3 выше. Оказывается, параметрами, которые минимизируют стохастический аналог для этого выбора целевого распределения и параметрического семейства, являются выборочное среднее и выборочная дисперсия, соответствующие элитным выборкам , которые являются теми выборками, которые имеют значение целевой функции . Наихудший из элитных образцов затем используется в качестве параметра уровня для следующей итерации. Это дает следующий рандомизированный алгоритм, который совпадает с так называемым алгоритмом оценки многомерного нормального алгоритма (EMNA), оценкой алгоритма распределения . ${\ displaystyle S}$${\ Displaystyle S (х) = {\ 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 \ {е (\ cdot; {\ boldsymbol {\ theta}}) \ right \}}$${\ Displaystyle \ му _ {т} \,}$${\ Displaystyle \ sigma _ {т} ^ {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}$

Псевдокод

// 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                  
    μ := 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

Рекомендации