Modèle statistique pour prédire le prochain déplacement sur le réseau uniquement en utilisant l'historique des mouvements

Est-il possible de construire un modèle statistique qui prédit le prochain mouvement dans un graphique uniquement basé sur les mouvements passés et la structure du graphique?

J'ai fait un exemple pour illustrer le problème:

1. Le temps est discret . À chaque tour, vous restez à votre nœud / sommet actuel ou vous vous déplacez vers l'un des nœuds connectés. Puisque le temps est discret et que vous pouvez tout au plus avancer d'un nœud à chaque tour, il n'y a pas de vitesse.
2. Historique des itinéraires / mouvements passés: {A, B, C} - Et la position actuelle est: C

3. Prochains coups valides: C, B, X, Y, Z

   1. Si vous choisissez C vous restez fixe,
   2. si B vous reculez,
   3. et si X, Y ou Z implique d'avancer.

4. Il n'y a pas de pondération sur les liens ou les nœuds.

5. Il n'y a pas de nœud de destination finale. Une partie du comportement de mouvement observé est aléatoire et une partie de celui-ci aura une certaine régularité.

Un modèle très simple - qui ne tient pas compte de l'historique des mouvements - prédirait simplement que C, B, X, Y et Z avaient chacun une probabilité de 1/5 d'être le prochain mouvement.

Mais sur la base de la structure et de l'historique du mouvement, je suppose qu'il est possible de faire un meilleur modèle statistique. Par exemple, X devrait avoir une probabilité plus faible, car on aurait pu s'y déplacer directement à partir du nœud B au tour précédent. De même, B devrait également avoir une probabilité plus faible car la personne aurait pu rester fixe au tour précédent.

Si l'utilisateur se déplace à dos B , puis l'histoire du mouvement ressemblera à ceci {A, B, C, B} et les mouvements valides seront A, B, C, D, E, X . Passer à C devrait avoir une probabilité plus faible, car vous auriez pu rester fixe. Passer à X devrait également avoir une probabilité plus faible, car vous auriez pu vous déplacer à partir de C lors du tour précédent. Des antécédents antérieurs peuvent également influer sur la prédiction, mais ils devraient avoir moins de poids que les antécédents récents, c'est-à-dire 2 tours il y a vous aurait pu rester en B , ou vous pourriez avoir déménagé à A, D, E, X - il y a 3 tours , vous aurait pu rester à un .

En regardant autour de moi, j'ai découvert que des problèmes similaires se posent dans:

• télécommunication mobile, où les opérateurs tentent de prédire dans quelle tour de cellule l'utilisateur se rendra ensuite afin de pouvoir passer en douceur la transmission des appels / données.
• navigation sur le Web, où les navigateurs / moteurs de recherche essaient de prédire la page à laquelle vous vous rendrez ensuite afin qu'ils puissent pré-charger et mettre en cache la page, de sorte que le temps d'attente soit réduit. De même, les applications cartographiques essaient de prédire les tuiles de carte que vous demanderez ensuite et de les précharger.
• et bien sûr l'industrie des transports.

Voulez-vous vraiment un modèle statistique, ou juste un algorithme pour deviner le nœud suivant étant donné tous les précédents? Si ces derniers envisagent alors de procéder comme suit.

Supposons que vous ayez choisi et que vous ayez besoin de décider lequel de , ou est le prochain nœud le plus probable.$\ldots\rightarrow A\rightarrow B\rightarrow C$$X$$Y$$Z$

1. Markov de premier ordre. Par le passé, disons passe de ont été à , à et à . Définissez . En ajoutant une constante d'aplatissement à chaque comptage, les probabilités prédites (Dirichlet-Multinomial) pour le prochain mouvement sont etc.$n_C(X)$$C$$X$$n_C(Y)$$Y$$n_C(Z)$$Z$$n_C=n_C(X)+n_C(Y)+n_C(Z)$$\kappa$$p_C(X) = \frac{\kappa+n_C(X)}{3\kappa+n_C}$

2. Markov de second ordre. Comme ci-dessus, mais nous examinons les mouvements après la . Les etc. seront plus faibles (nous prenons une tranche plus petite et plus spécifique de l'historique), donc l'effet d'aplatissement de l'ajout de aux historiques sera proportionnellement plus grand. Comme précédemment, nous définissons et ainsi de suite.$BC$$n_{BC}(X)$$\kappa$$p_{BC}(X) = \frac{\kappa+n_{BC}(X)}{3\kappa+n_{BC}}$

3. Continuez ainsi, en formant les probabilités jusqu'à ce que l'historique soit suffisamment long pour qu'il n'y ait qu'un seul choix pour le nœud suivant. Aller plus loin est désormais inutile. Soit le maximum de toutes les probabilités . Votre prédiction pour le nœud suivant est .$p_{C}(\cdot), p_{BC}(\cdot), p_{ABC}(\cdot), \ldots$$p_\textrm{history}(W)$$p_\cdot(\cdot)$$W$

Cela laisse juste la question de: quelle valeur doit prendre ? serait le point de départ traditionnel. Essayez la validation croisée (entraînez-vous sur une partie de vos données, testez sur le reste) pour affiner cette valeur.$\kappa$$\kappa=1$

Astuce pour la version non variable dans le temps: Vous pouvez traiter cela comme une mise à jour (utilisez le théorème de Bayes) des estimations de probabilité compte tenu de certaines données. Une probabilité multinomiale et un a priori de Dirichlet seraient l'approche standard. https://en.wikipedia.org/wiki/Dirichlet-multinomial_distribution

Pour l'a priori, il semble que vous souhaitiez que la probabilité a priori attribue des probabilités égales de transition à chaque nœud possible.

Ajouter les effets du temps (les anciennes transitions importent moins que les plus récentes) est plus complexe. Vous pouvez ajouter une fonction de désintégration pour obtenir des transitions partielles.

En général, la structure seule du diagramme ne vous dira rien sur les probabilités de transition.

Quelques réponses et quelques questions.

Pour plus de simplicité, commençons par supposer que vous ne voyez qu'une longue chaîne de mouvements. Le modèle le plus simple impliquerait une distribution multinomiale pour chaque nœud (essentiellement à chaque nœud, il y a un dé spécifique à lancer pour déterminer où vous allez ensuite). Notre objectif serait d'estimer les paramètres de ces dés. Comme Ash l'a mentionné, l'approche bayésienne serait de mettre une distribution de Dirichlet prioritaire sur chaque dé, et de la mettre à jour avec de nouvelles données pour obtenir une distribution postérieure de Dirichlet . Vous pouvez considérer une distribution Dirichlet comme une fabrique de dés. Le fait que la distribution postérieure est également un Dirichlet est parce que la distribution de Dirichlet est le Conjugué Priorà la distribution multinomiale. Bien que cela puisse sembler assez déroutant, c'est en fait très simple. Le prieur peut être interprété comme un pseudo-comptage, prétendant essentiellement que vous avez déjà vu certaines données (même si vous ne l'avez pas fait).

Par exemple, si vous êtes à Z, vous pouvez aller à C, D, Z (notre dé est à trois faces ici). Nous pouvons utiliser un Dirichlet avant qui agit comme si nous avions déjà vu une transition de Z à chacun de ces états. Donc, chaque probabilité sera égale à 1/3. Si le joueur passe à C, nous mettrons à jour notre distribution avec un compte de plus, donc la transition de Z à C aurait une probabilité 2/4 et l'autre aurait chacun une probabilité 1/4. Si nous utilisons un a priori avec plus de pseudo-comptes comme si nous avions vu 10 transitions de Z à chacun des autres états, les probabilités mises à jour (31/11, 10/31, 10/31), seraient beaucoup plus proches de l'original ceux-là, c'est un prior plus fort . La force de l'a priori est normalement déterminée par validation croisée .

Le modèle que j'ai décrit ci-dessus est appelé sans mémoire , car la probabilité de transition d'un état à un autre ne dépend que de votre état actuel. Si vous vouliez faire quelque chose de plus élaboré, vous pourriez incorporer non seulement où vous vous trouvez actuellement, mais aussi où vous étiez la dernière étape, bien qu'à ce stade le nombre de paramètres que vous devez estimer augmentera considérablement, et donc la variance dans l'estimation sera aussi bien.

Question:

Vous avez donné une certaine intuition de la forme "Pourquoi devrais-je passer de B-> C-> X alors que je pourrais simplement passer de B-> X?" Ces idées semblent être spécifiques au problème sur lequel vous travaillez, je peux donc en parler directement. Bien que si cela vous inquiète, vous voudrez peut-être utiliser le modèle non-sans mémoire (sans mémoire?), Ou incorporer ces informations dans votre précédent. Si vous souhaitez expliquer la signification réelle de ce graphique, et donc d'où vient cette intuition, nous pouvons peut-être être plus utiles.

Remarque:

Vous voulez rechercher des modèles de Markov, peut-être pas autant de modèles de Markov cachés. Ceux-ci ont un état caché qui contrôle les données observées, et essayer d'apprendre à les utiliser pourrait entraver ce projet.