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

Angenommen, Sie haben eine diskrete Zufallsvariable $X$ mit Wahrscheinlichkeitsmassenfunktion $p(x) = P(X=x)$ auf die Unterstützung $0,\ldots,n$ . Welche Funktion $q(x)\ge 0$ so dass $\sum_{x=0}^n q(x) = 1$ maximiert

E (\log [q (X - 1) + q (X) + q (X + 1)]) ?

$E(\log[q(X-1)+q(X)+q(X+1)])?$ Nehmen Sie an, um den Umgang mit Randfällen zu vermeiden

P (X = 0) = P (X = n) = 0

$P(X=0)=P(X=n)=0$ .

Verwandte Fragen:

Ich glaube das $q(x)$ das maximiert die obige Erwartung auch maximiert $E[q(X-1)+q(X)+q(X+1)]$ schon seit $\log$ ist 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.

probability optimization expected-value kullback-leibler jaradniemi
quelle

Könnten Sie einen Link angeben? Aus wahrscheinlich sehr offensichtlichen Gründen bin ich besonders interessiert ...

Cliff AB

Ich verstehe nicht warum die Lösung von

max_{q} E [q (X - 1) + q (X) + q (X + 1)]

$\max_q \mathbb{E}[q(X-1)+q(X)+q(X+1)]$ sollte die gleiche sein wie die Lösung von

max_{q} E [\log {q (X - 1) + q (X) + q (X + 1)}]

$\max_q \mathbb{E}[\log\{q(X-1)+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

@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:

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. $q_i \geq 0$

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. $\mathbf{q} \neq \mathbf{p}$ $\max \mathrm{E}[x]$ $\max \mathrm{E}[\log(x)]$ $x + y$ $\log(x) + \log(y)$

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

Definiere und . Das Problem ist: $q_0 = 0$ $q_{n+1} = 0$

\begin{array}{llr} maximize (over q_{i}) & \sum_{i = 1}^{n} p_{i} \log (q_{i - 1} + q_{i} + q_{i + 1}) \\ subject to & q_{i} \geq 0 \\ \sum_{i = 1}^{n} q_{i} = 1 \end{array}

$\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{maximize (over $q_i$)} & \sum_{i=1}^n p_i \log \left( q_{i-1} + q_i + q_{i+1} \right) \\ \mbox{subject to} & q_i \geq 0 \\ & \sum_{i=1}^n q_i = 1 \end{array} \end{equation}$

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 = \sum_{i} p_{i} \log (q_{i - 1} + q_{i} + q_{i + 1}) + \sum_{i} μ_{i} q_{i} - λ (\sum_{i} q_{i} - 1)

$\mathcal{L} = \sum_i p_i \log \left( q_{i-1} + q_i + q_{i+1} \right) + \sum_i \mu_i q_i -\lambda \left( \sum_i q_i - 1\right)$

\frac{p_{i - 1}}{q_{i - 2} + q_{i - 1} + q_{i}} + \frac{p_{i}}{q_{i - 1} + q_{i} + q_{i + 1}} + \frac{p_{i + 1}}{q_{i} + q_{i + 1} + q_{i + 2}} = λ - μ_{i}

$\frac{p_{i-1}}{q_{i-2} + q_{i-1} + q_{i}} + \frac{p_i}{q_{i-1} + q_i + q_{i+1}} + \frac{p_{i+1}}{q_{i} + q_{i+1} + q_{i+2}} = \lambda - \mu_i$

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

μ_{i} q_{i} = 0

$\mu_i q_i = 0$

μ_{i} \geq 0

$\mu_i \geq 0$

λ = 1

$\lambda = 1$

μ_{i}

$\mu_i$

λ

$\lambda$

Lösung, wenn niemals bindet. $q_i \geq 0$

Dann überlegen Sie sich eine Lösung

p_{i} = \frac{q_{i - 1} + q_{i} + q_{i + 1}}{3} μ_{i} = 0 λ = 1

$p_i = \frac{q_{i-1} + q_i + q_{i+1}}{3} \quad \quad \mu_i = 0 \quad \quad \lambda = 1$ Wenn wir uns in die Bedingung erster Ordnung einfügen, erhalten wir . So funktioniert es (solange und ebenfalls erfüllt sind).

\frac{1}{3} + \frac{1}{3} + \frac{1}{3} = 1

$\frac{1}{3} + \frac{1}{3} + \frac{1}{3} = 1$

\sum_{i} q_{i} = 1

$\sum_i q_i = 1$

q_{i} \geq 0

$q_i \geq 0$

So schreiben Sie das Problem mit Matrizen:

Sei und Vektoren. Sei eine Tri-Band-Diagonalmatrix von Einsen. Z.B. für $\mathbf{p}$ $\mathbf{q}$ $A$ $n = 5$

A = [\begin{array}{ccccc} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{array}]

$A = \left[\begin{array}{ccccc} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0& 0 \\ 0 & 1 & 1 & 1 & 0 \\0 &0 & 1 & 1&1\\ 0 &0 &0 & 1 & 1 \end{array} \right]$

Problem kann mit mehr Matrixnotation geschrieben werden:

\begin{array}{llr} maximize (over q) & p^{'} \log (A q) \\ subject to & q_{i} \geq 0 \\ \sum_{i} q_{i} = 1 \end{array}

$\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{maximize (over $\mathbf{q}$)} & \mathbf{p}'\log\left(A \mathbf{q} \right) \\ \mbox{subject to} & q_i \geq 0 \\ & \sum_i q_i = 1 \end{array} \end{equation}$

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.

A y = λ - u x = A q y_{i} = \frac{p_{i}}{x_{i}}

$A\mathbf{y} = \lambda - \mathbf{u} \quad \quad \mathbf{x} = A \mathbf{q} \quad \quad y_i = \frac{p_i}{x_i}$

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): Ein weiteres willkürlicheres Problem:

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. $p_{i-1} \approx p_i \approx p_{i+1}$ $q_i \approx p_i$ $p_i$ $q_i$ $p_i$ $p_i$

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.) $p$ $p$ $q$ $p$

Matthew Gunn
quelle

Ich verstehe die Bedingung nicht und hätte die Aufnahme der Einschränkung in die Lagrange weggelassen .

μ_{i} = 0

$\mu_i=0$

q_{i} \geq 0

$q_i\ge 0$

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.

q_{i} \geq 0

$q_i \geq 0$

μ_{i}

$\mu_i$

i

$i$

μ_{i} q_{i} = 0

$\mu_iq_i =0$

μ_{i} > 0

$\mu_i > 0$

q_{i} = 0

$q_i = 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.

A

$A$

m i n i m i z e - p^{'} \log (A q)

$\mathrm{minimize} -\mathbf{p}' \log\left(A\mathbf{q} \right)$

q \geq 0

$\mathbf{q} \geq \mathbf{0}$

\sum_{i} q_{i} = 1

$\sum_i q_i = 1$

q = p

$\mathbf{q} = \mathbf{p}$

p

$\mathbf{p}$

Matthew Gunn

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 . $\mathbf{q}=\mathbf{p}$

\arg min_{q} \sum p_{i} \log {p_{i} / q_{i}}

$\arg\min_\mathbf{q} \sum p_i\log\{ p_i\big/q_i\}$

q_{i - 1} + q_{i} + q_{i + 1} = 3 p_{i} i = 1, \dots, n - 1

$q_{i-1}+q_i+q_{i+1}=3p_i\qquad i=1,\ldots,n-1$

\arg max_{q} \sum p_{i} \log {p_{i} / (q_{i - 1} + q_{i} + q_{i + 1})}

$\arg\max_\mathbf{q} \sum p_i\log\{ p_i\big/(q_{i-1}+q_i+q_{i+1})\}$

R^{n + 1}

$\mathbb{R}^{n+1}$

Xi'an
quelle

Tippfehler, es sollte arg min sein. ist ein äquivalentes Problem zu

min_{q} \sum_{i} p_{i} (\log p_{i} - \log q_{i})

$\min_q \sum_i p_i \left(\log p_i - \log q_i \right)$

max_{q} \sum_{i} p_{i} \log q_{i}

$\max_q \sum_i p_i \log q_i$

Matthew Gunn

Danke, Matthew, ich habe schließlich die Zeit gefunden, meinen Eintrag richtig zu lesen!

Xi'an

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 $[X-1, X+1]$

$\sum_{i = 1}^n \log(P(t_i \in [L_i, R_i]) )$

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 . $t_i$ $i$ $[L_i, R_i]$ $L_i = X_i-1$ $R_i = X_i + 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, c_i]$ $[c_i, \infty)$

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 . $q$ $E[q(X-1)+ ...]$ $E[\log(q(X-1) + ...]$ $X_1 = 1, X_2 = 1, X_3 = 10$ $q(1) = 1$ $E[q(X-1)+ ...]$ $E[\log(q(X-1) + ...]$

Cliff AB
quelle

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

Antworten:

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

Lösung, wenn niemals bindet.qi≥0qi≥0q_i \geq 0

So schreiben Sie das Problem mit Matrizen:

Code zur Lösung mit CVX und MATLAB

Lösung, wenn niemals bindet. $q_i \geq 0$