Statistisches Modell zur Vorhersage der nächsten Bewegung im Netzwerk nur anhand des Bewegungsverlaufs

Ist es möglich, ein statistisches Modell zu erstellen, das die nächste Bewegung in einem Diagramm ausschließlich auf der Grundlage vergangener Bewegungen und der Struktur des Diagramms vorhersagt?

Ich habe ein Beispiel gemacht, um das Problem zu veranschaulichen:

1. Die Zeit ist diskret . In jeder Runde bleiben Sie entweder an Ihrem aktuellen Knoten / Scheitelpunkt oder Sie bewegen sich zu einem der verbundenen Knoten. Da die Zeit diskret ist und Sie höchstens einen Knoten pro Runde vorrücken können, gibt es keine Geschwindigkeit.
2. Vergangene Route / Bewegungshistorie: {A, B, C} - Und die aktuelle Position ist: C.

3. Gültige nächste Züge: C, B, X, Y, Z.

   1. Wenn Sie C wählen , bleiben Sie fest,
   2. Wenn B Sie rückwärts bewegen,
   3. und wenn X, Y oder Z bedeuten, sich vorwärts zu bewegen.

4. Es gibt keine Gewichte für Links oder Knoten.

5. Es gibt keinen endgültigen Zielknoten. Ein Teil des beobachteten Bewegungsverhaltens ist zufällig und ein Teil davon weist eine gewisse Regelmäßigkeit auf.

Ein sehr einfaches Modell - das die Bewegungshistorie nicht berücksichtigt - würde nur vorhersagen, dass C, B, X, Y und Z jeweils eine Wahrscheinlichkeit von 1/5 haben, die nächste Bewegung zu sein.

Aufgrund der Struktur und der Bewegungsgeschichte ist es jedoch möglich, ein besseres statistisches Modell zu erstellen. Zum Beispiel sollte Instanz X eine geringere Wahrscheinlichkeit haben, da man in der vorherigen Runde direkt vom Knoten B dorthin hätte ziehen können . In ähnlicher Weise sollte B auch eine geringere Wahrscheinlichkeit haben, da die Person in der vorherigen Runde fest bleiben könnte.

Wenn der Benutzer zu sichern B , dann wird die Bewegung der Geschichte so aussieht {A, B, C, B} und die gültigen bewegt wird A, B, C, D, E, X . Ein Wechsel zu C sollte eine geringere Wahrscheinlichkeit haben, da Sie fest bleiben könnten. Ein Wechsel zu X sollte auch eine geringere Wahrscheinlichkeit haben, da Sie in der vorherigen Runde von C dorthin gezogen sein könnten . Die frühere Vorgeschichte kann ebenfalls die Vorhersage beeinflussen, sollte jedoch weniger Gewicht erhalten als die jüngste Vorgeschichte - d. H. Vor 2 Runden hättest du in B bleiben können , oder du hättest nach A, D, E, X ziehen können - vor 3 Runden hättest du in A bleiben können .

Als ich mich umsah, stellte ich fest, dass ähnliche Probleme auftreten:

• Mobile Telekommunikation, bei der die Betreiber versuchen, vorherzusagen, zu welchem ​​Mobilfunkmast sich der Benutzer als Nächstes bewegen wird, damit sie die Anruf- / Datenübertragung reibungslos übergeben können.
• Webnavigation, bei der Browser / Suchmaschinen versuchen, vorherzusagen, zu welcher Seite Sie als Nächstes wechseln, damit sie die Seite vorladen und zwischenspeichern können, sodass die Wartezeit verkürzt wird. In ähnlicher Weise versuchen Kartenanwendungen vorherzusagen, welche Kartenkacheln Sie als Nächstes anfordern, und laden diese vor.
• und natürlich die Transportindustrie.

Möchten Sie wirklich ein statistisches Modell oder nur einen Algorithmus zum Erraten des nächsten Knotens bei allen vorherigen? Wenn letzteres der Fall ist, gehen Sie wie folgt vor.

Angenommen, Sie sind zu gegangen und müssen entscheiden, welcher von , oder der wahrscheinlichste nächste Knoten ist.$\ldots\rightarrow A\rightarrow B\rightarrow C$$X$$Y$$Z$

1. Markov erster Ordnung. Historisch gesehen , sagen wir mal bewegt sich von haben gewesen , bis und bis . Definiere . Durch Hinzufügen einer Abflachungskonstante zu jeder Zählung sind die (Dirichlet-Multinomial) vorhergesagten Wahrscheinlichkeiten für den nächsten Zug usw.$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 zweiter Ordnung. Wie oben, aber wir sehen uns Bewegungen nach . Die Anzahl usw. ist niedriger (wir nehmen einen kleineren, spezifischeren Teil der Geschichte), sodass der Abflachungseffekt durch Hinzufügen von zu den historischen Zählungen proportional größer ist. Nach wie vor definieren wir und so weiter.$BC$$n_{BC}(X)$$\kappa$$p_{BC}(X) = \frac{\kappa+n_{BC}(X)}{3\kappa+n_{BC}}$

3. Fahren Sie auf diese Weise fort und bilden Sie die Wahrscheinlichkeiten bis der Verlauf lang genug ist, dass es nur eine Auswahl für die gibt nächster Knoten. Weiter zurück zu gehen ist jetzt sinnlos. Sei das Maximum aller -Wahrscheinlichkeiten. Ihre Vorhersage für den nächsten Knoten ist .$p_{C}(\cdot), p_{BC}(\cdot), p_{ABC}(\cdot), \ldots$$p_\textrm{history}(W)$$p_\cdot(\cdot)$$W$

Dies lässt nur die Frage offen: Welchen Wert sollte annehmen? wäre der traditionelle Ausgangspunkt. Versuchen Sie eine Kreuzvalidierung (trainieren Sie einen Teil Ihrer Daten, testen Sie den Rest), um diesen Wert zu optimieren.$\kappa$$\kappa=1$

Hinweis für die nicht zeitlich variierende Version: Sie können dies als Aktualisierung (unter Verwendung des Bayes-Theorems) Wahrscheinlichkeitsschätzungen bei bestimmten Daten behandeln. Eine multinomiale Wahrscheinlichkeit und Dirichlet Prior wären der Standardansatz. https://en.wikipedia.org/wiki/Dirichlet-multinomial_distribution

Für den Prior klingt es so, als ob Sie möchten, dass die vorherige Wahrscheinlichkeit jedem möglichen Knoten gleiche Übergangswahrscheinlichkeiten zuweist.

Das Hinzufügen der Auswirkungen der Zeit (ältere Übergänge sind weniger wichtig als neuere) ist komplexer. Sie können eine Abklingfunktion hinzufügen, um Teilübergänge zu erhalten.

Im Allgemeinen sagt die Struktur allein des Diagramms nichts über die Übergangswahrscheinlichkeiten aus.

Ein paar Antworten und ein paar Fragen.

Nehmen wir zur Vereinfachung zunächst an, Sie sehen nur eine lange Bewegungskette. Das einfachste Modell würde eine Multinomialverteilung für jeden Knoten beinhalten (im Wesentlichen gibt es an jedem Knoten einen bestimmten Würfel, um zu bestimmen, wohin Sie als nächstes gehen). Unser Ziel wäre es, die Parameter dieser Würfel zu schätzen . Wie Ash erwähnte, bestand der Bayes'sche Ansatz darin, jedem Würfel eine Dirichlet-Prior-Verteilung zuzuweisen und diese mit neuen Daten zu aktualisieren, um eine Dirichlet-Posterior-Verteilung zu erhalten . Sie können sich eine Dirichlet-Distribution als Würfelfabrik vorstellen. Die Tatsache, dass die hintere Verteilung auch ein Dirichlet ist, liegt daran, dass die Dirichlet-Verteilung der Conjugate Prior istzur Multinomialverteilung. Das mag ziemlich verwirrend klingen, ist aber eigentlich sehr einfach. Der Prior kann als Pseudo-Zählung interpretiert werden und im Wesentlichen so tun, als hätten Sie bereits einige Daten gesehen (obwohl Sie dies nicht getan haben).

Wenn Sie zum Beispiel bei Z sind, können Sie zu C, D, Z gehen (unser Würfel ist hier dreiseitig). Wir können ein Dirichlet verwenden, das so wirkt, als hätten wir bereits einen Übergang von Z zu jedem dieser Zustände gesehen. Jede Wahrscheinlichkeit ist also gleich 1/3. Wenn der Spieler zu C übergeht, würden wir unsere Verteilung mit einer weiteren Zählung aktualisieren, sodass der Übergang von Z zu C eine Wahrscheinlichkeit von 2/4 und der andere eine Wahrscheinlichkeit von 1/4 hätte. Wenn wir einen Prior mit mehr Pseudozählungen verwenden, als hätten wir 10 Übergänge von Z zu jedem der anderen Zustände gesehen, wären die aktualisierten Wahrscheinlichkeiten (11/31, 10/31, 10/31) viel näher am Original diejenigen, dies ist ein stärkerer Prior. Die Stärke des Prior wird normalerweise durch Kreuzvalidierung bestimmt .

Das Modell , das ich oben beschrieben , wird bezeichnet als gedächtnislose , weil die Wahrscheinlichkeit des Übergangs von einem Zustand zum anderen nur auf Ihrem aktuellen Zustand abhängt. Wenn Sie etwas Ausgefeilteres tun möchten, können Sie nicht nur einbeziehen, wo Sie sich gerade befinden, sondern auch, wo Sie sich im letzten Schritt befanden. Zu diesem Zeitpunkt wird die Anzahl der zu schätzenden Parameter jedoch dramatisch zunehmen, und daher wird die Varianz bei der Schätzung wie folgt Gut.

Frage:

Sie gaben eine Vorstellung von der Form von "Warum sollte ich von B-> C-> X gehen, wenn ich nur von B-> X gehen könnte?" Diese Ideen scheinen spezifisch für das Problem zu sein, an dem Sie arbeiten, sodass ich direkt mit ihm sprechen kann. Wenn dies jedoch ein Problem darstellt, möchten Sie möglicherweise das nicht speicherlose (memoryfull?) Modell verwenden oder diese Informationen in Ihren vorherigen aufnehmen. Wenn Sie erklären möchten, welche Bedeutung dieses Diagramm für das wirkliche Leben hat und woher diese Intuition stammt, können wir vielleicht hilfreicher sein.

Hinweis:

Sie möchten Markov-Modelle nachschlagen, vielleicht nicht so viele versteckte Markov-Modelle. Diese haben einen verborgenen Zustand, der die beobachteten Daten kontrolliert, und der Versuch, zu lernen, wie man sie verwendet, könnte diesem Projekt im Wege stehen.