Otimização de modelos estocásticos de computador

11

Este é um tópico difícil para o google, pois ter as palavras otimização e estocástico em uma pesquisa quase automaticamente padroniza as pesquisas por otimização estocástica. Mas o que realmente quero saber são quais métodos existem para otimizar modelos de computador quando a saída do modelo de computador é estocástica, ou seja, não determinística?

Por exemplo, se você considerar um modelo de computador em que existe alguma função desconhecida que representa a saída do modelo de computador, existem muitos métodos estatísticos para resolver problemas comof(x)

minf(x)xX

quando f(x) é determinístico. Mas o que acontece quando f(x) é estocástico? Existe uma solução para o problema ou, na melhor das hipóteses, podemos apenas resolver

minE[f(x)]xX

onde E() é o operador de expectativa usual.

RustyStatistician
fonte
1
Esta é uma questão muito interessante. A otimização de é a única coisa que será realmente possível. Uma aplicação estatística relacionada a essa pergunta é o algoritmo MCEM, em que a função de probabilidade total só é observável com o erro MCMC em cima dela. Da mesma forma, os algoritmos de filtro de partículas do MCMC têm o mesmo problema. Ainda não li o suficiente sobre a literatura para saber quais são os métodos de ponta para responder a isso. E[f(x)]
Cliff AB
2
Depende do seu objetivo. é apenas uma das muitas opções possíveis. Em alguns aplicativos, convém ter uma solução "confiável", não apenas uma que seja "boa em média". Nesse cenário, você otimizaria wrt para algum quantil da distribuição de . A otimização bayesiana lida com avaliações de funções caras (e às vezes barulhentas). Verifique, por exemplo, esta pergunta . E[f(x)]f(x)
lacerbi
1
@lacerbi algum desses exemplos é barulhento? Eu acho que eles são apenas determinísticos.
RustyStatistician
@RustyStatistician: você está certo, a maioria dos exemplos é determinística ou fala sobre otimização bayesiana em geral. Veja abaixo referências mais focadas na parte "barulhenta".
lacerbi
Você acessa o programa de computador para poder executá-lo você mesmo para as entradas selecionadas ? Em seguida, os métodos para o planejamento de experimentos ficam disponíveis para uso! Procure este site. x
Kjetil b halvorsen

Respostas:

10

( Expandindo meu comentário para uma resposta adequada. )

Como eu mencionei, isso depende do seu objetivo.

O valor esperado é apenas uma das muitas opções possíveis para o destino de otimização. Por exemplo, supondo que os sejam normalmente distribuídos, você pode:E[f(x)]f(x)

xopt=argminx{E[f(x)]+κVar[f(x)]}
para alguns que manipulam a sensibilidade ao risco. Se você está procurando uma solução robusta que provavelmente seja a melhor e desencoraje grandes flutuações positivas. Vice-versa, um negativo favoreceria uma otimização "otimista" que procura grandes flutuações negativas (negativo é bom, pois estamos minimizando). Você pode escolher base nos quantis da distribuição normal (consulte a referência 2 abaixo).κRκ>0κκ

Em geral, a otimização bayesiana (BO, relacionada a processos e krigs gaussianos ) lida com avaliações de funções caras e às vezes barulhentas; embora a maior parte do foco da literatura tenha sido a parte anterior. Você pode encontrar críticas para otimização bayesiana nesta pergunta .

Várias pessoas aplicaram BO a funções ruidosas. Como introdução ao tópico, David Ginsbourger fez uma bela palestra intitulada "Variações sobre a melhoria esperada" no Workshop sobre processos gaussianos para otimização global (Sheffield, 17 de setembro de 2015). Você pode encontrar a palestra dele aqui , e todas as palestras estão disponíveis nesta página (eu também recomendo todas as outras palestras como uma excelente introdução geral ao BO.)

Como referência, eu começaria com o trabalho de Ginsbourger e colegas, e Gramacy e colegas:

  1. Picheny, V. e Ginsbourger, D., 2014. "Métodos de otimização baseados em krigagem ruidosa: uma implementação unificada dentro do pacote DiceOptim". Estatística Computacional e Análise de Dados , 71, pp.1035-1053. ( link )

  2. Picheny, V., Ginsbourger, D., Richet, Y. e Caplin, G., 2013. "Otimização baseada em quantis de experimentos barulhentos de computador com precisão ajustável". Technometrics , 55 (1), pp.2-13. ( link )

  3. Gramacy, RB e Lee, HK, 2012. "Modelos de processo gaussiano com formação bayesiana com aplicação em modelagem computacional". Jornal da Associação Estatística Americana . ( link )

  4. Gramacy, RB e Apley, DW, 2015. "Aproximação de processo gaussiano local para grandes experimentos com computadores". Jornal de Estatísticas Computacionais e Gráficas , 24 (2), pp.561-578. ( link )

Ginsburger e Gramacy têm pacotes R que implementam seus métodos BO, respectivamente DiceOptim e tgp .

lacerbi
fonte
1
Onde está na sua resposta ou você quer dizer ? kκ
RustyStatistician
1
Mais um algoritmo, que eu não usei *, mas vence no divertido departamento de nomes, é o SNOBFIT . (* O autor é notável na comunidade otimização no entanto, o software fez OK em uma referência determinista , assim que a recomendação não é apenas com base no nome legal!)
GeoMatt22
4

As respostas atuais concentram-se na definição (matemática) adequada de um alvo de otimização estocástica - quero fornecer uma perspectiva um pouco mais aplicada.

Esse problema ocorre com freqüência ao ajustar modelos estocásticos, por exemplo, usando probabilidades informais ou sintéticas. A referência (1) fornece uma lista de opções que podem ser usadas para definir a distância entre um modelo estocástico e os dados.

Depois de definir seu alvo dessa maneira, o problema que resta é encontrar o melhor de alguma média de um destino barulhento. Existem duas rotas a seguir: a) otimização eb) amostragem MCMC. Você estava perguntando especificamente sobre otimização, mas eu quero trazer os MCMCs porque eles costumam se comportar melhor para esta tarefa.

a) Se você permanecer com a otimização, precisará garantir que não fique travado e que o otimizador possa lidar com um alvo estocástico. O capítulo 4 da tese de doutorado de Matteo Fasiolo dá algumas dicas, veja (2).

b) Como observamos em (1), os MCMCs geralmente são mais robustos contra um alvo estocástico - sob condições moderadas em relação à distribuição do ruído, o MCMC calcula a média do ruído e o alvo amostrado será indistinguível de um não-barulhento alvo com média do alvo barulhento. No entanto, os MCMCs também podem ficar presos ao encontrar uma avaliação particularmente boa. O que você NÃO DEVE FAZER agora está obtendo a seguinte idéia "óbvia": basta calcular o valor atual e o proposto em cada iteração do MCMC. A palavra-chave para procurar aqui é "pseudo-marginal", veja também aqui e aqui .

1) Hartig, F.; Calabrese, JM; Reineking, B .; Wiegand, T. & Huth, A. (2011) Inferência estatística para modelos de simulação estocástica - teoria e aplicação . Ecol. Lett., 14, 816-827.

2) Fasiolo, M. (2016) Métodos Estatísticos para Dinâmica Populacional Complexa . Universidade de Bath

Florian Hartig
fonte
4

Digamos que estamos em um espaço de probabilidade discreto para que . Intuitivamente, você precisa de alguma função para otimizar . Você só pode otimizar um único objetivo!f(x)RnU:RnRU(f(x))

A otimização de uma única função objetiva pode parecer bastante constrangedora, mas não é ! Em vez disso, um único objetivo pode representar preferências incrivelmente diversas que você pode ter sobre o que é uma solução melhor ou pior.

Avançando, um ponto simples para começar pode ser escolher uma variável aleatória e resolver:λ

minimize (over x)E[λf(x)]subject toxX
Esta é uma nova ponderação linear simples de . De qualquer forma, aqui está um argumento sobre por que o colapso de vários objetivos em um único objetivo geralmente é aceitável.E[f(x)]

Configuração básica:

  • Você tem uma variável escolha e um conjunto viável .xX
  • Sua escolha de leva a um resultado aleatórioxy~=f(x)
  • Você tem preferências racionais sobre o resultado aleatório. (Basicamente, você pode dizer se prefere um resultado aleatório a outro.)y~

Seu problema é escolher modo que:xX

xXf(x)f(x)
Em inglês, você deseja escolher para que nenhuma opção viável leve a um resultado preferido a .xxf(x)

Equivalência à maximização da utilidade (sob certas condições técnicas)

Por simplicidade técnica, direi que estamos em um espaço de probabilidade discreto com resultados, para que eu possa representar um resultado aleatório com um vetor .ny~yRn

Sob certas condições técnicas (que não são limitativas no sentido prático), o problema acima é equivalente a maximizar uma função utilitária . (A função utilitário atribui resultados mais preferenciais a um número maior.)U(y)

Essa lógica se aplica a qualquer problema em que sua escolha leva a várias variáveis ​​de resultado.

maximize (over x)U(f(x))subject toxX

Dando mais estrutura à função de utilidade : Hipótese de utilidade esperada :U

Se estamos em um cenário probabilístico e aceitamos os axiomas de Neumann-Morgernstern , a função geral de utilidade deve assumir uma forma especial:U

U(y)=E[u(yi)]=ipiu(yi)
Onde é a probabilidade do estado e é uma função de utilidade côncava. A curvatura de mede a aversão ao risco. Simplesmente substituindo esta forma especializada de você obtém:piiuuU

maximize (over x)ipiu(yi)subject toxXy=f(x)

Observe que o caso simples está maximizando o valor esperado (ou seja, sem aversão ao risco).u(yi)=yi

Outra abordagem: pesosλ

Outra coisa a fazer é:

maximize (over x)iλiyisubject toxXy=f(x)

Intuitivamente, você pode escolher pesos maiores ou menores que a probabilidade de um estado ocorrer, e isso captura a importância de um estado.λipi

A justificativa mais profunda dessa abordagem é que, sob certas condições técnicas, existem pesos lambda modo que o problema acima e os problemas anteriores (por exemplo, maximizar ) tenham a mesma solução.λU(f(x))

Matthew Gunn
fonte
Mas nesta configuração nem todas as funções utilitárias levam à mesma resposta correta?
RustyStatistician
E existem opções típicas para funções utilitárias? Meu problema é um simulador estocástico de computador, que na verdade é um simulador de caixa preta; portanto, não conheço nenhuma informação sobre a mecânica subjacente; posso até atribuir a ele uma função de utilitário?
RustyStatistician
Você precisa pensar na lógica do seu problema, o que constitui um bom resultado, e depois encontrar alguma função objetiva que atribua melhores resultados a um número maior. (Ou equivalentemente, você pode configurá-lo como um problema de minimização e atribuir piores resultados um número maior por exemplo minimizar alguma noção de erro quadrado etc ....)
Matthew Gunn