Bayesowskie wykrywanie punktów wymiany w Internecie (marginalny rozkład predykcyjny)

9

Czytam internetowy dokument wykrywający punkt wymiany w Bayesian przez Adamsa i MacKaya ( link ).

Autorzy zaczynają od napisania krańcowego rozkładu predykcyjnego: gdzie

P(xt+1|x1:t)=rtP(xt+1|rt,xt(r))P(rt|x1:t)(1)
  • xt jest obserwacją w czasie ;t
  • x1:t oznacza zestaw obserwacji do czasu ;t
  • rtN to bieżąca długość przebiegu (czas od ostatniego punktu zmiany, może wynosić 0); i
  • xt(r) to zestaw obserwacji związanych z uruchomieniem .rt

Równ. 1 jest formalnie poprawny (patrz odpowiedź poniżej autorstwa @JuhoKokkala), ale rozumiem, że jeśli chcesz faktycznie przewidzieć , musisz go rozwinąć w następujący sposób:xt+1

P(xt+1|x1:t)=rt,rt+1P(xt+1|rt+1,xt(r))P(rt|x1:t)P(rt+1|rt)(1b)

Moje rozumowanie jest takie, że może istnieć punkt wymiany w (przyszłym) czasie , ale tylna obejmuje tylko do .t+1P(rt|x1:t)t

Chodzi o to, że autorzy artykułu robią z Eq. 1 jak jest (patrz równania 3 i 11 w pracy), a nie 1b. Pozornie więc ignorują możliwość zmiany punktu w czasie gdy przewidują podstawie danych dostępnych w czasie . Na początku części 2 mówią en passantt+1xt+1t

Zakładamy, że możemy obliczyć rozkład predykcyjny [dla ] od danej długości przebiegu .xt+1rt

i być może jest to sztuczka. Ale ogólnie ten rozkład predykcyjny powinien wyglądać podobnie do równania. 1b; co nie jest tym, co robią (równ. 11).

Nie jestem więc pewien, czy rozumiem, co się dzieje. Być może z notacją dzieje się coś śmiesznego.


Odniesienie

  • Adams, RP i MacKay, DJ (2007). Bayesian wykrywanie punktów wymiany w Internecie. nadruk arXiv arXiv: 0710.3742.
Lacerbi
źródło
Potencjalnym wyjaśnieniem jest to rtreprezentuje długość przebiegu na końcu okresu czasut, który jest po zmianie punktu w czasiet. Z tym, Eq. 1 ma sens. W rzeczywistości jedna inicjalizacja algorytmu polega na ustawieniuP(r0=0)=1 który zakłada, że ​​przed startem jest punkt zmiany t=1. Jednak Ryc. 1 jest błędna (lub przynajmniej wprowadza w błąd), jeśli istnieje punkt wymiany między nimit=4 i t=5i pomiędzy t=10 i t=11 jak pokazano na ryc. 1a r4 i r10 powinno wynosić 0 zgodnie z tym zapisem, a nie r5 i r11jak na ryc. 1b.
lacerbi
1
W Eq dzieje się coś dziwnego. 3, ponieważ środkowym czynnikiem w summand w ostatniej linii jest P(xtrt1,xt(r)) podczas gdy myślałem xt(r) zawiera xt. Podejrzewam, żet i t1 zamieniłem miejsca jako P(xtrt,xt1(r))miałoby sens. W równ. 11, wydaje się, że prawa strona zależy odxt(r)który wcale nie pojawia się po lewej stronie, więc albo coś jest nie tak, albo wcale nie rozumiem zapisu.
Juho Kokkala
@JhohoKokkala: Cieszę się, że nie jestem jedyny z tym uczuciem ...
lacerbi
1
@ Lacerbi, mam inne pytanie dotyczące tego artykułu i myślę, że możesz być w stanie na nie odpowiedzieć, ponieważ wydaje ci się, że znasz pracę: stats.stackexchange.com/questions/419988 .
gwg

Odpowiedzi:

5

Zarówno (1), jak i (1b) są poprawne. OP ma rację, że (w tym modelu) może istnieć punkt wymiany nat+1, i xt+1zależy od tego, czy istnieje punkt wymiany. Nie oznacza to żadnych problemów z (1) jako możliwymi wartościamirt+1 są w pełni „objęte” przez P(xt+1rt,x1:t). P(xt+1|rt,x1:t) oznacza rozkład warunkowy xt+1 uwarunkowane (rt,x1:t). Ta warunkowa dystrybucja uśrednia dla „wszystkiego innego”, w tymrt+1, pod warunkiem (rt,x1:t). Tak jak można napisać, powiedzmy,P(xt+1000|xt), który uwzględniałby wszystkie możliwe konfiguracje punktów wymiany, a także wartości xiwystępuje między t i t+1000.

W pozostałej części najpierw wyprowadzam (1), a następnie (1b) na podstawie (1).

Wyprowadzenie (1)

Dla dowolnych zmiennych losowych A,B,C, mamy

P(AB)=cP(AB,C=c)P(C=cB),
tak długo jak Cjest dyskretny (w przeciwnym razie suma musi zostać zastąpiona całką). Stosując to doxt+1,x1:t,rt:

P(xt+1x1:t)=rtP(xt+1rt,x1:t)P(rtx1:t),
która ma znaczenie bez względu na zależności między rt, x1:t, xt+1to znaczy, że nie zastosowano jeszcze założeń modelowych. W obecnym modeluxt+1 dany rt,xt(r) zakłada się, że * jest warunkowo niezależny od wartości x z biegów wcześniej xt(r). To implikujeP(xt+1rt,x1:t)=P(xt+1rt,xt(r)). Zastępując to poprzednim równaniem, otrzymujemy

P(xt+1x1:t)=rtP(xt+1rt,xt(r))P(rtx1:t),(1)
który jest (1) w OP.

Wyprowadzenie (1b)

Rozważmy rozkład P(xt+1rt,xt(r)) ponad możliwe wartości rt+1:

P(xt+1rt,xt(r))=rt+1P(xt+1rt+1,rt,xt(r))P(rt+1rt,xt(r)).

Ponieważ zakłada się *, czy punkt zmiany występuje w t+1 (pomiędzy xt i xt+1) does not depend on the history of x, we have P(rt+1rt,xt(r))=P(rt+1rt). Furthermore, since rt+1 determines whether xt+1 belongs into the same run as xt, we have P(xt+1rt+1,rt,xt(r))=P(xt+1rt+1,xt(r)). Substituting these two simplifications into the factorization above, we get

P(xt+1rt,xt(r))=rt+1P(xt+1rt+1,xt(r))P(rt+1rt).
Substituting this into (1), we get
P(xt+1x1:t)=rt(rt+1P(xt+1rt+1,xt(r))P(rt+1rt))P(rtx1:t),(1b)
which is OP's (1b).

* Remark on the model's conditional independence assumptions

Based on quickly browsing the paper, I would personally like the conditional independence properties to be more explicitly stated somewhere, but I suppose that the intention is that r is Markovian and the x:s associated to different runs are independent (given the runs).

Juho Kokkala
źródło
1
(+1) Thanks. Yep, of course, I understand that Eq. 1 is formally correct if one assumes implicit marginalization over rt+1. The problem is that later on the authors make predictions (Eq. 11 in the paper, and implicitly in Eq. 3) and they are seemingly not marginalizing over rt+1 when they take them.
lacerbi
1
Oh. It seems then that I misunderstood the question - should I delete this? You may want to clarify the question, currently it sounds like (1) is somehow incorrect (instead of perhaps not useful)
Juho Kokkala
Please keep this answer, which is valuable. My mistake that I was't clear enough in my original post. I tried to clarify my question thanks to your comments, and in a way that still makes this answer meaningful.
lacerbi