Escolha a distribuição de probabilidade para maximizar a função de avaliação (no concurso de previsão de gripe do CDC)

7

Suponha que você tenha uma variável aleatória discreta com função de massa de probabilidade no suporte . Que função tal que maximiza Para evitar lidar com casos extremos, assuma .Xp(x)=P(X=x)0,,nq(x)0x=0nq(x)=1

E(log[q(X1)+q(X)+q(X+1)])?
P(X=0)=P(X=n)=0

Perguntas relacionadas:

  • Eu acredito que o que maximiza a expectativa acima também maximiza pois é monotônico. Isso está correto?q(x)E[q(X1)+q(X)+q(X+1)]log
  • Alguma coisa pode bater ?p(x)=q(x)

Para aqueles que estão interessados, essa pergunta surge da competição CDC Flu Forecasting, onde eles usam o log da soma das probabilidades para o valor-alvo e os valores vizinhos como a função de utilidade para avaliar previsões.

jaradniemi
fonte
Você poderia fornecer um link? Por motivos provavelmente muito óbvio, eu estou particularmente interessado ...
Cliff AB
2
Não vejo por que a solução de deve ser a mesma que a solução demaxqE[q(X1)+q(X)+q(X+1)]maxqE[log{q(X1)+q(X)+q(X+1)}]
Xi'an
Eu adicionei um link para um comunicado de imprensa. Infelizmente, o link no artigo, que é o site real da competição, está atualmente inativo. Esperamos que volte em breve.
jaradniemi 16/09/16
A idéia é que queremos avaliar seu pmf para um objetivo, por exemplo, semana de pico, mas como os dados são barulhentos, o objetivo é incerto.
jaradniemi 16/09/16
11
@jaradniemi: ah, então é exatamente o caso do problema dos dados com intervalo de censura, e a solução para o seu problema é o NPMLE com intervalo de censura.
Cliff AB

Respostas:

3

Problema legal! Como a derivação de Xi'an mostra, está relacionada à minimização da divergência de KL de Q para P. Cliff também fornece um contexto importante.

O problema pode ser resolvido trivialmente usando software de otimização, mas não vejo uma maneira de escrever uma fórmula de formulário fechado para a solução geral. Se nunca for , existe uma fórmula intuitiva.qi0

Quase certamente ideal (embora veja meus exemplos de gráficos no final, ele pode estar próximo). E não é o mesmo problema que . Observe que não é um objetivo equivalente a . Não é uma transformação monotônica. Expectativa é de uma soma eo log vai dentro a soma, então não é uma transformação monotônica da função objetivo.qpmaxE[x]maxE[log(x)]x+ylog(x)+log(y)

Condições KKT (isto é, condições necessárias e suficientes) para uma solução:

Defina e . O problema é: q0=0qn+1=0

maximize (over qi)i=1npilog(qi1+qi+qi+1)subject toqi0i=1nqi=1

Lagrangiano: Este é um problema de otimização convexo em que a condição de Slater se mantém, portanto, as condições KKT são necessárias e condições suficientes para um ótimo. Condição de primeira ordem:

L=ipilog(qi1+qi+qi+1)+iμiqiλ(iqi1)
pi1qi2+qi1+qi+piqi1+qi+qi+1+pi+1qi+qi+1+qi+2=λμi

complementar: E, claro, . (Parece nos meus testes que mas não vejo imediatamente o porquê.) e são multiplicadores de Lagrange.

μiqi=0
μi0λ=1μiλ

Solução se nunca for .qi0

Então considere a solução

pi=qi1+qi+qi+13μi=0λ=1
Conectando-se à condição de primeira ordem, obtemos . Portanto, funciona (desde que e também sejam satisfeitos).13+13+13=1iqi=1qi0

Como escrever o problema com matrizes:

Sejam e vetores. Seja uma matriz diagonal de três bandas de unidades. Por exemplo. parapqAn=5

A=[1100011100011100011100011]

O problema pode ser escrito com mais notação matricial:

maximize (over q)plog(Aq)subject toqi0iqi=1

Isso pode ser resolvido rapidamente numericamente, mas não vejo um caminho para uma solução limpa de formulário fechado?

A solução é caracterizada por: mas não vejo como isso seja muito útil além de verificar seu software de otimização.

Ay=λux=Aqyi=pixi

Código para resolvê-lo usando CVX e MATLAB

A = eye(n) + diag(ones(n-1,1),1) + diag(ones(n-1,1),-1);

cvx_begin
 variable q(n)
 dual variable u;
 dual variable l;
 maximize(p'*log(A*q))

 subject to:
  u: q >= 0;
  l: sum(q) <= 1;
cvx_end

Por exemplo. entradas:

p = 0.0724    0.0383    0.0968    0.1040    0.1384    0.1657    0.0279    0.0856    0.2614    0.0095

tem solução:

q = 0.0000    0.1929    0.0000    0.0341    0.3886    0.0000    0.0000    0.2865    0.0979    0.0000

Solução que recebo (azul) quando tenho uma tonelada de caixas, basicamente seguindo o pdf normal (vermelho): insira a descrição da imagem aqui Outro problema mais arbitrário: insira a descrição da imagem aqui

Muito vagamente, para você obtém , mas se se move em torno de uma tonelada, você obtém algumas coisas complicadas onde a otimização tenta colocar o massa em no bairro de massa, estrategicamente colocando-a entre com massa.pi1pipi+1qipipiqipipi

Outro ponto conceitual é que a incerteza em sua previsão suavizará efetivamente sua estimativa de , e um mais suave terá uma solução mais próxima de . (Eu acho que está certo.)ppqp

Matthew Gunn
fonte
Eu não entendo a e teria omitido a inclusão da no Lagrangiano. μi=0qi0
Xi'an
@ Xi'an Quando eu resolvi esse problema numericamente usando CVX, a se liga em certos casos, portanto o multiplicador é positivo para alguns . O é apenas uma maneira idiota de dizer que, se então e vice-versa. qi0μiiμiqi=0μi>0qi=0
Matthew Gunn
Obrigado pela resposta. Eu esperava replicar seus resultados, mas usando R, mas parece que isso não é tão simples.
jaradniemi
@jaradniemi Meu R não é muito bom, mas você provavelmente poderia obter um código simples de alguém que já fez alguma otimização em R antes. Com a matriz definida como eu, você deseja resolver o problema de minimização convexa sujeito a e . Dito isso, das minhas brincadeiras sobre esse problema, parece que escolher está bem próximo de que é bastante suave (por exemplo, consulte a primeira figura), para que você não possa ganhar muito. Aminimizeplog(Aq)q0iqi=1q=pp
Matthew Gunn
3

Como resolve e quanto a resolver para encontrar a solução para Se a solução para este sistema de equações não pertencer ao simplex , o argumento será encontrado na face do simplex .q=p

argminqpilog{pi/qi}
qi1+qi+qi+1=3pii=1,,n1
argmaxqpilog{pi/(qi1+qi+qi+1)}
Rn+1
Xi'an
fonte
11
Erro de digitação, deve ser arg min. é um problema equivalente aminqipi(logpilogqi)maxqipilogqi
Matthew Gunn
Obrigado, Matthew. Acabei encontrando tempo para ler minha entrada corretamente!
Xian'16
2

Se eu entendi isso corretamente, não acho que isso terá uma solução de formulário fechado. Ou, além disso, é pelo menos uma especialização de um problema que não está na forma fechada.

A razão pela qual digo isso é que é exatamente a probabilidade que aparece no NPMLE para dados censurados por intervalo, sendo a especialização que todos os intervalos têm a forma . Em geral, o NPMLE é o maximizador da função[X1,X+1]

i=1nlog(P(ti[Li,Ri]))

onde é a hora do evento para o sujeito , onde tudo que se sabe é que o evento ocorreu dentro do intervalo . Isso equivale exatamente ao seu problema, com e .tii[Li,Ri]Li=Xi1Ri=Xi+1

Em geral, isso não está em forma fechada. No entanto, pelo menos um caso especial é; a dos dados de status atuais ou quando todos os intervalos estiverem no formato ou .[0,ci][ci,)

Dito isto, existem muitos algoritmos para resolver o NPMLE! Você pode ajustar isso usando Ro icenRegpacote de s com a ic_npfunção (nota: eu sou o autor). Certifique-se de definir a opção B = c(1,1), declarando que os intervalos estão fechados.

Note-se que é não o caso em que a função de que maximiza também maximiza . Como um exemplo trivial, suponha Então, e 0, de outro modo, maximiza mas é indefinido para .qE[q(X1)+...]E[log(q(X1)+...]X1=1,X2=1,X3=10q(1)=1E[q(X1)+...]E[log(q(X1)+...]

Cliff AB
fonte