Modelo estadístico para predecir el próximo movimiento en la red solo usando el historial de movimientos

¿Es posible construir un modelo estadístico que prediga el próximo movimiento en un gráfico basado únicamente en movimientos pasados ​​y la estructura del gráfico?

He hecho un ejemplo para ilustrar el problema:

1. El tiempo es discreto . En cada ronda permaneces en tu nodo / vértice actual o te mueves a uno de los nodos conectados. Como el tiempo es discreto y, como máximo, puede avanzar un nodo en cada ronda, no hay velocidad.
2. Historial de ruta / movimiento pasado: {A, B, C} - Y la posición actual es: C

3. Próximos movimientos válidos: C, B, X, Y, Z

   1. Si eliges C, te mantienes fijo,
   2. si B te mueves hacia atrás,
   3. y si X, Y o Z implica avanzar.

4. No hay pesos ni en enlaces ni en nodos.

5. No hay un nodo de destino final. Parte del comportamiento de movimiento observado es aleatorio y parte tendrá cierta regularidad.

Un modelo muy simple, que no tiene en cuenta el historial de movimiento, solo predeciría que C, B, X, Y y Z tienen una probabilidad de 1/5 de ser el próximo movimiento.

Pero según la estructura y el historial del movimiento, supongo que es posible hacer un mejor modelo estadístico. Por ejemplo, X debería tener una probabilidad menor, ya que uno podría haberse movido allí directamente desde el nodo B en la ronda anterior. Del mismo modo, B también debería tener una probabilidad menor, ya que la persona podría haber permanecido fija en la ronda anterior.

Si el usuario se mueve atrás a B , entonces el historial de movimientos se verá así {A, B, C, B} y los movimientos válidos será A, B, C, D, E, X . Pasar a C debería tener una probabilidad menor, ya que podría haber permanecido fijo. Moverse a X también debería tener una probabilidad menor, ya que podría haberse movido allí desde C en la ronda anterior. La historia anterior también puede influir en la predicción, pero se le debe dar menos peso que la historia reciente, es decir. 2 rondas hace que podrían haber quedado en B , o que podrían haber trasladado a A, D, E, X - 3 rondas hace que podrían haber quedado en una .

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

• telecomunicación móvil, donde los operadores intentan predecir a qué torre celular se moverá el usuario a continuación para que puedan pasar sin problemas la transmisión de llamadas / datos.
• navegación web, donde los navegadores / motores de búsqueda intentan predecir a qué página irá después para que puedan precargar y almacenar en caché la página, de modo que se reduzca el tiempo de espera. Del mismo modo, las aplicaciones de mapas intentan predecir qué mosaicos de mapas solicitará a continuación y precargarlos.
• y, por supuesto, la industria del transporte.

¿Realmente quieres un modelo estadístico, o simplemente un algoritmo para adivinar el siguiente nodo dados todos los anteriores? Si es lo último, considere proceder de la siguiente manera.

Supongamos que te has ido $\ldots\rightarrow A\rightarrow B\rightarrow C$ y necesita decidir cuál de $X$, $Y$ o $Z$ es el siguiente nodo más probable.

1. Markov de primer orden. Históricamente, digamos$n_C(X)$ se mueve desde $C$ he estado en $X$, $n_C(Y)$ a $Y$ y $n_C(Z)$ a $Z$. Definir$n_C=n_C(X)+n_C(Y)+n_C(Z)$. Agregar una constante de aplanamiento$\kappa$ para cada conteo, las probabilidades pronosticadas (Dirichlet-Multinomial) para el siguiente movimiento son $p_C(X) = \frac{\kappa+n_C(X)}{3\kappa+n_C}$ etc.

2. Markov de segundo orden. Como arriba, pero estamos viendo movimientos siguiendo$BC$. Los recuentos$n_{BC}(X)$ etc. será menor (estamos tomando una porción más pequeña y más específica del historial), por lo que el efecto de aplanamiento de agregar $\kappa$Los recuentos históricos serán proporcionalmente mayores. Como antes, definimos$p_{BC}(X) = \frac{\kappa+n_{BC}(X)}{3\kappa+n_{BC}}$ y así.

3. Continúa de esta manera, formando probabilidades $p_{C}(\cdot), p_{BC}(\cdot), p_{ABC}(\cdot), \ldots$hasta que el historial sea lo suficientemente largo como para que solo haya una opción para el siguiente nodo. Ir más atrás ahora no tiene sentido. Dejar$p_\textrm{history}(W)$ ser el máximo de todos $p_\cdot(\cdot)$probabilidades Su predicción para el siguiente nodo es$W$.

Esto solo deja la pregunta de: ¿qué valor debería $\kappa$ ¿tomar? $\kappa=1$sería el punto de partida tradicional. Pruebe la validación cruzada (entrene en parte de sus datos, pruebe en el resto) para ajustar ese valor.

Sugerencia para la versión que no varía en el tiempo: puede tratar esto como una actualización (use el teorema de Bayes) de las estimaciones de probabilidad dados algunos datos. Una probabilidad multinomial y Dirichlet anterior sería el enfoque estándar. https://en.wikipedia.org/wiki/Dirichlet-multinomial_distribution

Para lo anterior, parece que desearía que la probabilidad previa asigne probabilidades iguales de transición a cada nodo posible.

Agregar los efectos del tiempo (las transiciones más antiguas importan menos que las más nuevas) es más complejo. Puede agregar una función de caída para obtener transiciones parciales.

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

Algunas respuestas y algunas preguntas.

Para simplificar, comencemos asumiendo que solo está viendo una larga cadena de movimientos. El modelo más simple implicaría una distribución multinomial para cada nodo (esencialmente en cada nodo hay un dado específico para tirar para determinar a dónde irá después). Nuestro objetivo sería estimar los parámetros de estos dados. Como Ash mencionó, el enfoque bayesiano consistiría en colocar una Distribución previa de Dirichlet en cada dado, y actualizar esto antes con nuevos datos para obtener una Distribución posterior de Dirichlet . Puedes pensar en una distribución de Dirichlet como una fábrica de dados. El hecho de que la distribución posterior también sea un Dirichlet se debe a que la distribución de Dirichlet es el Prior Conjugadoa la distribución multinomial. Si bien esto puede sonar bastante confuso, en realidad es muy simple. Lo anterior puede interpretarse como pseudo-conteos, esencialmente pretendiendo que ya has visto algunos datos (aunque no los hayas visto).

Por ejemplo, si estás en Z puedes ir a C, D, Z (nuestro dado tiene tres lados aquí). Podemos usar un Dirichlet previo que actúa como si ya hubiéramos visto una transición de Z a cada uno de esos estados. Entonces cada probabilidad será igual a 1/3. Si el jugador realiza la transición a C, actualizaríamos nuestra distribución con un conteo más, por lo que la transición de Z a C tendría una probabilidad de 2/4 y la otra tendría una probabilidad de 1/4. Si usamos un previo con más pseudo-conteos como si hubiéramos visto 10 transiciones de Z a cada uno de los otros estados, las probabilidades actualizadas (11/31, 10/31, 10/31) estarían mucho más cerca del original unos, este es un prior más fuerte . La fuerza del previo normalmente se determina por validación cruzada .

El modelo que describí anteriormente se conoce como sin memoria , porque la probabilidad de transición de un estado a otro depende solo de su estado actual. Si quisiera hacer algo más elaborado, podría incorporar no solo dónde se encuentra actualmente, sino también dónde fue el último paso, aunque en este punto el número de parámetros que tiene que estimar aumentará dramáticamente y, por lo tanto, la varianza en la estimación será bien.

Pregunta:

Usted dio una intuición de la forma de "¿Por qué iría de B-> C-> X cuando podría ir de B-> X?" Estas ideas parecen ser específicas del problema en el que está trabajando, por lo que puedo hablar directamente con él. Aunque si eso es una preocupación, quizás desee utilizar el modelo sin memoria (¿memoria llena?) O incorporar esta información en su anterior. Si desea explicar cuál es el significado de la vida real de este gráfico y, por lo tanto, de dónde proviene esta intuición, tal vez podamos ser más útiles.

Nota:

Desea buscar modelos de Markov, tal vez no tanto modelos de Markov ocultos. Esos tienen un estado oculto que controla los datos observados, y tratar de aprender a usarlos podría interferir en este proyecto.