Wählen Sie die Wahrscheinlichkeitsverteilung, um die Bewertungsfunktion zu maximieren (für den CDC-Grippewettbewerb).

7

Angenommen, Sie haben eine diskrete Zufallsvariable X mit Wahrscheinlichkeitsmassenfunktion p(x)=P(X=x) auf die Unterstützung 0,,n. Welche Funktionq(x)0 so dass x=0nq(x)=1 maximiert

E(log[q(X1)+q(X)+q(X+1)])?
Nehmen Sie an, um den Umgang mit Randfällen zu vermeiden P(X=0)=P(X=n)=0.

Verwandte Fragen:

  • Ich glaube das q(x) das maximiert die obige Erwartung auch maximiert E[q(X1)+q(X)+q(X+1)] schon seit logist monoton. Ist das korrekt?
  • Kann irgendetwas schlagen p(x)=q(x)?

Für diejenigen, die interessiert sind, ergibt sich diese Frage aus dem CDC Flu Forecasting-Wettbewerb, bei dem sie das Protokoll der Summe der Wahrscheinlichkeiten für den Zielwert und benachbarte Werte als Nutzenfunktion zur Bewertung von Prognosen verwenden.

jaradniemi
quelle
Könnten Sie einen Link angeben? Aus wahrscheinlich sehr offensichtlichen Gründen bin ich besonders interessiert ...
Cliff AB
2
Ich verstehe nicht warum die Lösung von maxqE[q(X1)+q(X)+q(X+1)]sollte die gleiche sein wie die Lösung vonmaxqE[log{q(X1)+q(X)+q(X+1)}]
Xi'an
Ich habe einen Link zu einer Pressemitteilung hinzugefügt. Leider ist der Link innerhalb des Artikels, der zur eigentlichen Wettbewerbsseite führt, derzeit nicht verfügbar. Hoffentlich ist es bald wieder soweit.
Jaradniemi
Die Idee ist, dass wir Ihre PMF für ein Ziel auswerten möchten, z. B. für die Spitzenwoche. Da die Daten selbst jedoch verrauscht sind, ist das Ziel unsicher.
Jaradniemi
1
@jaradniemi: ah, dann ist es genau der Fall, dass das Problem der intervallzensierten Daten und die Lösung für Ihr Problem das intervallzensierte NPMLE ist.
Cliff AB

Antworten:

3

Cooles Problem! Wie die Ableitung von Xi'an zeigt, hängt sie mit der Minimierung der KL-Divergenz von Q zu P. zusammen. Cliff bietet auch einen wichtigen Kontext.

Das Problem kann trivial mit einer Optimierungssoftware gelöst werden, aber ich sehe keine Möglichkeit, eine geschlossene Formel für die allgemeine Lösung zu schreiben. Wenn niemals bindet, gibt es eine intuitive Formel.qi0

Mit ziemlicher Sicherheit optimal (obwohl meine Beispieldiagramme am Ende zu sehen sind, könnte es nahe sein). Und ist nicht dasselbe Problem wie . Beachten Sie, dass kein äquivalentes Ziel ist wie . Es ist keine monotone Transformation. Erwartung ist eine Summe und das Protokoll geht in die Summe ein, es ist also keine monotone Transformation der Zielfunktion.qpmaxE[x]maxE[log(x)]x+ylog(x)+log(y)

KKT-Bedingungen (dh notwendige und ausreichende Bedingungen) für eine Lösung:

Definiere und . Das Problem ist: q0=0qn+1=0

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

Lagrange: Dies ist ein konvexes Optimierungsproblem, bei dem Slaters Bedingung gilt, daher sind die KKT-Bedingungen notwendig und ausreichende Bedingungen für ein Optimum. Bedingung erster Ordnung:

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

Komplementäre Schlaffheit: Und natürlich . (Aus meinen Tests geht hervor, dass aber ich verstehe nicht sofort, warum.) und sind Lagrange-Multiplikatoren.

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

Lösung, wenn niemals bindet.qi0

Dann überlegen Sie sich eine Lösung

pi=qi1+qi+qi+13μi=0λ=1
Wenn wir uns in die Bedingung erster Ordnung einfügen, erhalten wir . So funktioniert es (solange und ebenfalls erfüllt sind).13+13+13=1iqi=1qi0

So schreiben Sie das Problem mit Matrizen:

Sei und Vektoren. Sei eine Tri-Band-Diagonalmatrix von Einsen. Z.B. fürpqAn=5

A=[1100011100011100011100011]

Problem kann mit mehr Matrixnotation geschrieben werden:

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

Dies kann numerisch schnell gelöst werden, aber ich sehe keinen Weg zu einer sauberen Lösung in geschlossener Form?

Die Lösung ist gekennzeichnet durch: aber ich sehe nicht, wie schrecklich hilfreich das ist, außer Ihre Optimierungssoftware zu überprüfen.

Ay=λux=Aqyi=pixi

Code zur Lösung mit CVX und 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

Z.B. Eingänge:

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

hat Lösung:

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

Lösung Ich bekomme (blau), wenn ich eine Tonne Mülleimer habe, die im Grunde dem normalen PDF folgen (rot): Geben Sie hier die Bildbeschreibung ein Ein weiteres willkürlicheres Problem: Geben Sie hier die Bildbeschreibung ein

Sehr locker, für Sie , aber wenn sich um eine Tonne bewegt, werden einige knifflige Dinge ausgeführt, bei denen die Optimierung versucht, das zu setzen Masse auf 's in der Nähe von Masse, strategisch zwischen ' s mit Masse platzieren.pi1pipi+1qipipiqipipi

Ein weiterer konzeptioneller Punkt ist, dass die Unsicherheit in Ihrer Prognose Ihre Schätzung von effektiv glättet und ein glatteres eine Lösung , die näher an . (Ich denke das ist richtig.)ppqp

Matthew Gunn
quelle
Ich verstehe die Bedingung nicht und hätte die Aufnahme der Einschränkung in die Lagrange weggelassen . μi=0qi0
Xi'an
@ Xi'an Wenn ich dieses Problem mit CVX numerisch gelöst habe, ist die in bestimmten Fällen , daher ist der Multiplikator für einige positiv . Das ist nur eine dumme Art zu sagen, dass wenn dann und umgekehrt. qi0μiiμiqi=0μi>0qi=0
Matthew Gunn
Danke für die Antwort. Ich hatte gehofft, Ihre Ergebnisse zu replizieren, aber R zu verwenden, aber es scheint, dass dies nicht so einfach ist.
Jaradniemi
@jaradniemi Mein R ist nicht sehr gut, aber Sie könnten wahrscheinlich einfachen Code von jemandem bekommen, der zuvor einige Optimierungen in R vorgenommen hat. Mit Matrix definiert wie ich, wollen Sie die konvexe Minimierungsproblem lösen unter und . Nach meinem Herumspielen an diesem Problem scheint die Auswahl von für ziemlich nah zu sein , was ziemlich glatt ist (siehe z. B. erste Abb.), So dass Sie dies möglicherweise nicht tun viel gewinnen. Aminimizeplog(Aq)q0iqi=1q=pp
Matthew Gunn
3

Da löst was gerade Lösung , um die Lösung für Wenn die Lösung für dieses Gleichungssystem nicht zum Simplex gehört, wird das Argument auf einer Seite des Simplex gefunden .q=p

argminqpilog{pi/qi}
qi1+qi+qi+1=3pii=1,,n1
argmaxqpilog{pi/(qi1+qi+qi+1)}
Rn+1
Xi'an
quelle
1
Tippfehler, es sollte arg min sein. ist ein äquivalentes Problem zuminqipi(logpilogqi)maxqipilogqi
Matthew Gunn
Danke, Matthew, ich habe schließlich die Zeit gefunden, meinen Eintrag richtig zu lesen!
Xi'an
2

Wenn ich das richtig verstehe, denke ich nicht, dass dies eine geschlossene Lösung haben wird. Oder darüber hinaus ist es zumindest eine Spezialisierung eines Problems, das nicht in geschlossener Form vorliegt.

Der Grund, warum ich dies sage, ist, dass es genau die Wahrscheinlichkeit ist, die in der NPMLE für intervallzensierte Daten erscheint, wobei die Spezialisierung darin besteht, dass alle Intervalle die Form . Im Allgemeinen ist der NPMLE der Maximierer der Funktion[X1,X+1]

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

Dabei ist die Ereigniszeit für das Subjekt , wobei nur bekannt ist, dass das Ereignis innerhalb des Intervalls aufgetreten ist . Dies entspricht genau Ihrem Problem mit und .tii[Li,Ri]Li=Xi1Ri=Xi+1

Im Allgemeinen ist dies nicht in geschlossener Form. Mindestens ein Sonderfall ist jedoch; die der aktuellen oder wenn alle Intervalle die Form oder .[0,ci][ci,)

Davon abgesehen gibt es viele Algorithmen zur Lösung des NPMLE! Sie können diese unter Verwendung passen R‚s icenRegmit der Paket - ic_npFunktion (Anmerkung: Ich bin der Autor). Stellen Sie sicher, dass Sie die Option festlegen B = c(1,1)und erklären, dass die Intervalle geschlossen sind.

Es ist zu beachten, dass es nicht der Fall ist, dass die Funktion , die maximiert, auch maximiert . Als triviales Beispiel Angenommen, Dann maximiert und 0 andernfalls , ist aber für .qE[q(X1)+...]E[log(q(X1)+...]X1=1,X2=1,X3=10q(1)=1E[q(X1)+...]E[log(q(X1)+...]

Cliff AB
quelle