Modelo estadístico para predecir el siguiente movimiento en la red sólo utilizando el movimiento de la historia

Question

Es posible construir un modelo estadístico que predice que el próximo movimiento en un gráfico basado únicamente en los movimientos del pasado y la estructura de la gráfica?

He hecho un ejemplo para ilustrar el problema:

1. El tiempo es discreto. En cada ronda en la que o bien quedarse en su actual nodo/vértice o mover a uno de los nodos conectados. Dado que el tiempo es discreto y que en la mayoría de los puede avanzar un nodo en cada ronda hay ninguna velocidad.
2. Pasado la ruta / movimiento de la historia: {A, B, C} -- Y la posición actual es: C

3. Válido siguientes movimientos: C, B, X, Y, Z

   1. Si usted elige C permanecer fijo,
   2. si B se mueve hacia atrás,
   3. y si X, Y o Z, supone avanzar.

4. No hay pesos en cualquiera de los enlaces o nodos.

5. No hay ningún final nodo de destino. Parte del movimiento, el comportamiento observado es aleatorio y parte de ello será cierta regularidad.

Un modelo muy simple-que no toma en cuenta el movimiento de la historia, acaba de predecir que C, B, X, y y Z, cada uno tenía una probabilidad de 1/5 a ser el siguiente movimiento.

Pero basado en la estructura y el movimiento de la historia, supongo que es posible hacer un mejor modelo estadístico. Primer plano de la instancia de X debe tener una menor probabilidad, ya que se podría haber trasladado allí directamente desde el nodo B en la ronda anterior. Del mismo modo B también debe tener una menor probabilidad, ya que la persona podría haber mantenido fijo en la ronda anterior.

---

Si el usuario se mueve de nuevo a B, entonces el movimiento de la historia tendrá este aspecto {A, B, C, B} y la validez de movimientos serán a, B, C, D, E, X. Mover a C debe tener una menor probabilidad, ya que se podría haber mantenido fijo. Mover a X también debe tener una menor probabilidad, ya que podría tener el movimiento allí de C en la ronda anterior. Principio de la historia, también pueden influir en la predicción, pero debe administrarse con menos peso de la historia reciente-es decir. 2 vueltas atrás, usted pudo haber quedado en B, o que podría haber movido a a, D, E, X -- 3 rondas atrás, usted pudo haber quedado en Una.

---

Mirando a su alrededor, descubrí que problemas similares se enfrentan en:

• de las telecomunicaciones móviles, donde el operaters intentar predecir la celda de la torre el usuario se mueve a la siguiente para que puedan suavemente la mano sobre la llamada/transmisión de datos.
• de navegación de la web, donde navegadores y motores de búsqueda tratan de predecir la página que vas a ir a la próxima que se puede pre-cargar y caché de la página, de tal manera que el tiempo de espera se reduce. Del mismo modo mapa de aplicaciones intentan predecir que los mapas se le solicite siguiente, y a la precarga de estos.
• y, por supuesto, la industria del transporte.

Answer 1

¿Usted realmente quiere un modelo estadístico, o simplemente un algoritmo para adivinar el siguiente nodo dado a todos los anteriores? Si esta última, a continuación, considere el siguiente procedimiento.

Supongamos que se ha ido $\ldots\rightarrow A\rightarrow B\rightarrow C$ y la necesidad de decidir cuál de $X$, $Y$ o $Z$ es muy probable que el siguiente nodo.

1. De Markov de primer orden. Históricamente, vamos a decir $n_C(X)$ se mueve de $C$ han sido $X$, $n_C(Y)$ a$Y$$n_C(Z)$$Z$. Definir $n_C=n_C(X)+n_C(Y)+n_C(Z)$. La adición de un aplanamiento constante $\kappa$ a cada uno de los cargos, la (Dirichlet-Multinomial) predijo que las probabilidades para el siguiente movimiento se $p_C(X) = \frac{\kappa+n_C(X)}{3\kappa+n_C}$ etc.

2. De Markov de segundo orden. Como en el anterior, pero estamos mirando mueve siguiendo $BC$. Los condes $n_{BC}(X)$ etc será menor (estamos dando un más pequeño, más específico. rebanada de la historia), por lo que el aplanamiento efecto de la adición de $\kappa$ a la histórica cuenta será proporcionalmente mayor. Como antes, podemos definir la $p_{BC}(X) = \frac{\kappa+n_{BC}(X)}{3\kappa+n_{BC}}$ y así sucesivamente.

3. Continuar de esta manera, la formación de probabilidades de $p_{C}(\cdot), p_{BC}(\cdot), p_{ABC}(\cdot), \ldots$ hasta que la historia es lo suficientemente largo que sólo hay una opción para el siguiente nodo. Yendo más atrás ahora es inútil. Deje $p_\textrm{history}(W)$ ser la máxima de todas las $p_\cdot(\cdot)$ de probabilidades. Su predicción para el siguiente nodo es $W$.

Esto sólo deja la pregunta de: ¿qué valor debe $\kappa$? $\kappa=1$ sería el tradicional punto de partida. Trate de validación cruzada (el tren en el que parte de los datos de prueba, en el resto) para ajustar ese valor.

Answer 2

Sugerencia para el no-tiempo diferentes de la versión: Usted puede tratar esto como la actualización (utilice el teorema de Bayes) estimaciones de probabilidad dado algunos datos. Una probabilidad multinomial y de Dirichlet antes sería el enfoque estándar. https://en.wikipedia.org/wiki/Dirichlet-multinomial_distribution

Para la previa suena como usted desea que la probabilidad anterior para asignar la igualdad de probabilidades de transición para cada nodo.

Para agregar en los efectos de tiempo (más viejo tranitions importa menos que las más nuevas) es más complejo. Se podría añadir en un decaimiento de la función para que usted obtenga parcial de las transiciones.

En general la estructura de la diagrama le dirá nada acerca de las probabilidades de transición.

Answer 3

Un par de respuestas y un par de preguntas.

Por simplicidad, vamos a empezar por asumir que usted está a solo ver a una larga cadena de movimientos. El modelo más simple implicaría una Multinomial de distribución para cada nodo (esencialmente en cada nodo hay un tipo específico de morir a rodar a determinar dónde ir la próxima). Nuestro objetivo sería la estimación de los parámetros de estos dados. Como la Ceniza se menciona que el enfoque Bayesiano, sería poner un Dirichlet Antes de la Distribución en cada uno de los troqueles, y la actualización de este previo con los nuevos datos para obtener un Dirichlet Posterior Distribución. Usted puede pensar en una distribución Dirichlet como dados de fábrica. El hecho de que la distribución posterior es también una de Dirichlet es debido a que la distribución Dirichlet es el Conjugado Previo a la distribución Multinomial. Mientras que esto puede sonar un poco confuso, en realidad es muy simple. La anterior puede ser interpretado como pseudo-cuenta, esencialmente pretender que ya hemos visto algunos datos (aunque aún no).

Por ejemplo, si usted está en Z se puede ir a la C, D, Z (nuestra morir es de tres lados, aquí). Podemos utilizar una de Dirichlet antes de que actúa como si ya hemos visto la transición de Z para cada uno de esos estados. Para cada probabilidad será igual a 1/3. Si el jugador transiciones a C, queremos actualizar nuestra distribución con una más que contar, así que la transición de la Z a C tendría probabilidad de 2/4 y el otro cada uno tiene probabilidad de 1/4. Si utilizamos una previa con más de pseudo-cuenta como a pesar de que había visto a 10 transiciones de Z para cada uno de los otros estados, la actualización de las probabilidades (11/31, 10/31, 10/31), sería mucho más cerca de la original, esta es una más fuerte antes. La fuerza de la previa es normalmente determinado por Validación Cruzada.

El modelo que he descrito anteriormente se conoce como memoryless, debido a que la probabilidad de transición de un estado a otro sólo depende de su estado actual. Si quería hacer algo más elaborado, que se podría incorporar no sólo el lugar donde se encuentra actualmente, pero también donde estaban último paso, aunque en este punto el número de parámetros que se han de estimar aumentará drásticamente, y por lo tanto la varianza en la estimación.

Pregunta:

Le dio algo de intuición de la forma de "¿por Qué iba a ir al B->C->X cuando yo sólo podía ir de B->X?" Estas ideas parecen ser específicos para el problema en el que estás trabajando, así que puede hablar directamente con él. Aunque si que es un motivo de preocupación, tal vez desee utilizar la no-memoryless (memoryfull?) modelo de, o incorporar esta información en la previa. Si a usted le gustaría explicar qué es la vida real significado de este gráfico, y por lo tanto donde esta intuición proviene, tal vez, podemos ser de más ayuda.

Nota:

Usted desea buscar Modelos de Markov, tal vez no tanto Modelos Ocultos de Markov. Aquellos que tienen un estado oculto que es el control de los datos observados, y tratando de aprender a usar ellos podría ponerse en el camino de este proyecto.