Método de entropia cruzada - Cross-entropy method

O método de entropia cruzada ( CE ) é um método de Monte Carlo para amostragem de importância e otimização . É aplicável a problemas combinatórios e contínuos , com um objetivo estático ou ruidoso.

O método aproxima o estimador de amostragem de importância ideal, repetindo duas fases:

1. Extraia uma amostra de uma distribuição de probabilidade.
2. Minimize a entropia cruzada entre esta distribuição e uma distribuição de destino para produzir uma amostra melhor na próxima iteração.

Reuven Rubinstein desenvolveu o método no contexto de simulação de eventos raros , onde pequenas probabilidades devem ser estimadas, por exemplo, em análise de confiabilidade de rede, modelos de enfileiramento ou análise de desempenho de sistemas de telecomunicações. O método também foi aplicado ao caixeiro viajante , atribuição quadrática , alinhamento de sequência de DNA , corte máximo e problemas de alocação de buffer.

Estimativa por meio de amostragem de importância

Considere o problema geral de estimar a quantidade

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

onde é alguma função de desempenho e é membro de alguma família paramétrica de distribuições. Usando a amostragem de importância, essa quantidade pode ser estimada como ${\ 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})}}}$,

de onde é uma amostra aleatória . Para positivo , a densidade de amostragem de importância teoricamente ideal (PDF) é dada por ${\ 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}$.

Isso, no entanto, depende do desconhecido . O método CE visa aproximar o PDF ideal, selecionando adaptativamente os membros da família paramétrica que estão mais próximos (no sentido de Kullback-Leibler ) do PDF ideal . ${\ displaystyle \ ell}$${\ displaystyle g ^ {*}}$

Algoritmo CE genérico

1. Escolha o vetor de parâmetro inicial ; defina t = 1.${\ displaystyle \ mathbf {v} ^ {(0)}}$
2. Gere uma amostra aleatória de${\ displaystyle \ mathbf {X} _ {1}, \ dots, \ mathbf {X} _ {N}}$${\ displaystyle f (\ cdot; \ mathbf {v} ^ {(t-1)})}$
3. Resolva para onde${\ displaystyle \ mathbf {v} ^ {(t)}}$
   ${\ 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. Se a convergência for alcançada, pare ; caso contrário, aumente t em 1 e repita a partir da etapa 2.

Em vários casos, a solução para a etapa 3 pode ser encontrada analiticamente . Situações em que isso ocorre são

• Quando pertence à família exponencial natural${\ displaystyle f \,}$
• Quando é discreto com suporte finito${\ displaystyle f \,}$
• Quando e , então corresponde ao estimador de máxima verossimilhança com base naqueles .${\ 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}$

Otimização contínua - exemplo

O mesmo algoritmo CE pode ser usado para otimização, em vez de estimativa. Suponha que o problema seja maximizar alguma função , por exemplo ,. Para aplicar CE, considera-se primeiro o problema estocástico associado de estimativa para um dado nível , e família paramétrica , por exemplo a distribuição gaussiana unidimensional , parametrizada por sua média e variância ( aqui). Logo, para um dado , o objetivo é encontrar de forma que seja minimizado. Isso é feito resolvendo a versão de amostra (contraparte estocástica) do problema de minimização de divergência KL, como na etapa 3 acima. Acontece que os parâmetros que minimizam a contraparte estocástica para esta escolha de distribuição alvo e família paramétrica são a média da amostra e a variância da amostra correspondentes às amostras de elite , que são aquelas amostras que têm valor de função objetivo . O pior dos exemplos de elite é então usado como o parâmetro de nível para a próxima iteração. Isso produz o seguinte algoritmo aleatório que coincide com o chamado Algoritmo Normal Multivariado de Estimação (EMNA), um algoritmo de estimativa de distribuição . ${\ 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}$

Pseudo-código

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

Métodos relacionados

• Recozimento simulado
• Algorítmos genéticos
• Busca de harmonia
• Estimativa do algoritmo de distribuição
• Pesquisa tabu
• Estratégia de Evolução Natural

Veja também

• Entropia cruzada
• Divergência de Kullback-Leibler
• Algoritmo Randomizado
• Amostragem de importância

Artigos de jornal

• De Boer, PT., Kroese, DP, Mannor, S. e Rubinstein, RY (2005). Um tutorial sobre o método de entropia cruzada. Annals of Operations Research , 134 (1), 19-67. [1]
• Rubinstein, RY (1997). Otimização de Modelos de Simulação de Computador com Eventos Raros, European Journal of Operational Research , 99 , 89-112.

Implementações de software

• Pacote CEoptim R

Referências