Descubrir donde Bob está durmiendo el uso de cadenas de Markov ocultos

Question

Bob vive en cuatro casas diferentes $A, B, C$ $D$ que están conectadas como en el siguiente gráfico se muestra:

Bob le gusta dormir en alguna de sus casas, pero están lejos entre sí, de modo que sólo duerme en una casa adyacente a aquella en la que durmió la noche anterior. Para aclarar, esto significa que si Bob durmió en casa de $A$ en la noche $1$, se puede dormir en casa $A$, $B$ o $C$ en la noche $2$ (no casa de $D$). La probabilidad de cada caso es el mismo (un tercio); en cada día, Bob toma una caminata aleatoria a partir de donde se quedó la noche anterior (y que podría quedarse).

Ahora, Bob es un criminal buscado así que en una noche que el FBI gustaría estimar que Bob está durmiendo. Los datos de un satélite que nos da las siguientes probabilidades de que Bob es dormir en la noche $1$ y de noche $2$ (y las noches):

         Night 1   Night 2   ...
House A  0.8       0.05      ...
House B  0.1       0.4       ...
House C  0.05      0.05      ...
House D  0.05      0.5       ...

¿Cómo podemos utilizar estos datos para calcular la probabilidad de que Bob estaba durmiendo en la noche $2$, por ejemplo el cálculo de la probabilidad de Bob dormía en casa de Una? Podríamos utilizar el método que de forma iterativa para calcular donde Bob estaba durmiendo en la noche $n$ si se siguen recibiendo datos de satélite para cada noche?

Nota: hice este problema para comprender mejor cómo ocultos de Markov las cadenas de trabajo porque estoy interesado en ver los cálculos en un ejemplo concreto. Muchas gracias por la entrada.

Answer 1

El objetivo es actualizar la probabilidad de Bob dado las mediciones satelitales.

El estado de Bob en el tiempo $k$ está dado por $x_{k}$. La medición de un satélite es $y_{k}$. Ya que no hay información previa es dado, inicializamos con una distribución uniforme $$ \text{for } i={A,B,C,D},\,\, p(x_{0}=i|y_{0})=1/4.$$

Ahora que hemos inicializado, vamos a usar Baye la regla para obtener $p(x_{1}=i|y_{0},y_{1})$. Sólo voy a hacer esto para i=A. Baye la regla de los rendimientos

$$ p(x_{1}=A|y_{0},y_{1}) = \frac{p(x_{1}=A \cap y_{1}|y_{0})}{p(y_{1}/y_{0})}. $$ Ahora sólo nos queda rellenar los espacios en blanco. En primer lugar, me gustaría calcular mi "predicción", que es

$$ p(x_{1}=A | y_{0}) = \sum_{x_{0}\in{A,B,C,D}} P(x_{1}=A|x_{0})P(x_{0}|y_{0}).$$

Suponiendo que bob tiene la misma probabilidad de permanecer en la casa, o ir a un lado de la casa, este valor es 3*(1/3)*1/4 = 1/4, y para esta iteración, al menos, la predicción para los demás estados, es el mismo valor. Ahora echemos un vistazo a la Baye la Regla de la ecuación que hemos descrito anteriormente

$$ p(x_{1}=A \cap y_{1}|y_{0}) = p(y_{1}|x_{1}=A)p(x_{1}=A|y_{0})=1/5$$

Finalmente,

$$ p(y_{1}/y_{0}) = \sum_{x_{1}\in{A,B,C,D}} p(y_{1}/x_{1})p(x_{1}/y_{0}). $$

Esto viene a ser de 1/4. Finalmente,

$$ p(x_{1}=A|y_{0},y_{1}) = \frac{1/5}{1/4} = 4/5. $$

Answer 2

Hasta el momento nadie ha dado una respuesta al problema que contiene una solución, así que voy a publicar lo que yo creo ser la solución.

La hipótesis de una distribución uniforme inicialmente, por lo que el real probabilidades en la noche $1$ igual exactamente el valor en la tabla de la primera noche. El próximo paso es calcular para cada casa $k = \{A, B, C, D \} $ el siguiente valor:

$ S_2(i) \cdot \sum_{i \in N(k)} \frac{S_{1}(i)}{n(i)+1}$

donde $N(k)$ es el conjunto de vecinos de $k$ además $k$ sí, $S_x(i)$ es el satélite de la probabilidad de Bob dormir en la ubicación de $i$ día $x$, e $n(i)$ es el número de vecinos de $i$. El motivo de esta fórmula es relativamente simple es porque Bob toma una caminata al azar en cada noche con cada una de sus opciones igualmente probable - si había una preferencia por una casa sobre otra, la fórmula anterior sería más complicado.

Comenzamos por calcular la fórmula para $k=A$ y consigue $0.05 \cdot (0.05/(2+1) + 0.1/(2+1) + 0.8/(2+1)) = 0.0158$. Los valores de $k=B, k=C$ $k=D$ se pueden encontrar igualmente se $0.1267, 0.0158, 0.0333$. La normalización, encontramos que la suma de los cuatro valores es $0.1917$, por lo que la verdadera probabilidad de que Bob está durmiendo en casa de Una de la noche en las $2$$0.0158/0.1917 = 8.2 \%$, e igualmente otras probabilidades para $B$, $C$ y $D$ $66.1 \%$, $8.2 \%$ y $17.4\%$ respectivamente.

Realizamos una breve comprobación de validez y ver que las probabilidades que se corresponden a grandes rasgos con lo que sería de esperar; parece más probable que Bob era el hecho de dormir en casa de $B$, $D$ ser el siguiente candidato más probable, y $A$ $C$ debe ser igual de raro.

Answer 3

Si $K \in \{ A, B, C, D \}$, escribo $K_n$ para el caso de 'Bob es en K en la noche n'.
Entonces, lo que tienes es:

\begin{align*} P[A_{n+1}] &= P[A_{n+1} \cap A_n] + P[A_{n+1} \cap B_n] + P[A_{n+1} \cap C_n] + P[A_{n+1} \cap D_n] \\ &= P[A_{n+1} \mid A_n] P[A_n] + P[A_{n+1} \mid B_n] P[B_n] + P[A_{n+1} \mid C_n] P[C_n] + P[A_{n+1} \mid D_n] P[D_n] \\ &= P[A_n]/3 + P[B_n]/3 + P[C_n]/3 + 0. \end{align*}

Answer 4

Es posible que desee ver en esto. http://en.wikipedia.org/wiki/Viterbi_algorithm