Algorithme d'apprentissage automatique pour prédire l'ordre des événements ?

Question

Question simple sur l'apprentissage automatique. Il y a probablement de nombreuses façons de la résoudre :

Il existe un infini flux de 4 événements possibles :

'event_1', 'event_2', 'event_4', 'event_4'

Les événements ne se succèdent pas dans un ordre totalement aléatoire. Nous supposerons qu'il existe des schémas complexes dans l'ordre d'apparition de la plupart des événements, et que le reste des événements est simplement aléatoire. Nous ne connaissons cependant pas ces modèles à l'avance.

Après la réception de chaque événement, je veux prédire quel sera l'événement suivant en me basant sur l'ordre dans lequel les événements sont arrivés dans le passé. Ma question est donc la suivante : Quel algorithme d'apprentissage automatique dois-je utiliser pour ce prédicteur ?

Le prédicteur sera alors informé de l'événement suivant :

Predictor=new_predictor()

prev_event=False
while True:
    event=get_event()
    if prev_event is not False:
        Predictor.last_event_was(prev_event)
    predicted_event=Predictor.predict_next_event(event)

La question se pose de savoir quelle durée d'historique le prédicteur doit conserver, puisqu'il ne sera pas possible de conserver un historique infini. Je vous laisse le soin de répondre à cette question. La réponse ne peut pas être infinie pour des raisons pratiques.

Je pense donc que les prédictions devront être faites avec une sorte d'historique glissant. L'ajout d'un nouvel événement et l'expiration d'un ancien événement devraient donc être plutôt efficaces, et ne pas nécessiter la reconstruction de l'ensemble du modèle de prédiction, par exemple.

Un code spécifique, au lieu de documents de recherche, ajouterait pour moi immense valeur à vos réponses. Les bibliothèques Python ou C sont bien, mais n'importe quoi fera l'affaire.

Merci !

Mise à jour : Et si plus d'un événement pouvait se produire simultanément à chaque tour. Cela change-t-il la solution ?

Answer 1

Il s'agit essentiellement d'un problème de prédiction de séquence, ce qui nécessite des réseaux neuronaux récurrents ou des modèles de Markov cachés.

Si vous ne disposez que d'une période fixe pour regarder en arrière, les approches par fenêtre temporelle peuvent suffire. Vous prenez les données de la séquence et les divisez en fenêtres de longueur n qui se chevauchent (par exemple, vous divisez une séquence ABCDEFG en ABC, BCD, CDE, DEF, EFG). Ensuite, vous entraînez un approximateur de fonction (par exemple, un réseau neuronal ou une régression linéaire) pour faire correspondre les n-1 premières parties de cette fenêtre à la nième partie.

Votre prédicteur ne pourra pas remonter dans le temps plus longtemps que la taille de votre fenêtre. Les RNN et les HMM peuvent le faire en théorie, mais ils sont difficiles à régler ou parfois ne fonctionnent tout simplement pas.

(Des implémentations RNN de pointe peuvent être trouvées dans PyBrain. http://pybrain.org )

Mise à jour : Voici le code pybrain pour votre problème. (Je ne l'ai pas testé, il peut y avoir des fautes de frappe et autres, mais la structure générale devrait fonctionner).

from pybrain.datasets import SequentialDataSet
from pybrain.supervised.trainers import BackpropTrainer
from pybrain.tools.shortcuts import buildNetwork
from pybrain.structure import SigmoidLayer

INPUTS = 4
HIDDEN = 10
OUTPUTS = 4

net = buildNetwork(INPUTS, HIDDEN, OUTPUTS, hiddenclass=LSTMLayer, outclass=SigmoidLayer, recurrent=True)

ds = SequentialDataSet(INPUTS, OUTPUTS)

# your_sequences is a list of lists of tuples which each are a bitmask
# indicating the event (so 1.0 at position i if event i happens, 0.0 otherwise)

for sequence in your_sequences:
    for (inpt, target) in zip(sequence, sequence[1:]):
        ds.newSequence()
        ds.appendLinked(inpt, target)

net.randomize()

trainer = BackpropTrainer(net, ds, learningrate=0.05, momentum=0.99)
for _ in range(1000):
    print trainer.train()

Ceci entraînera le réseau récurrent pendant 1000 époques et imprimera l'erreur après chaque époque. Ensuite, vous pouvez vérifier les prédictions correctes comme ceci :

net.reset()
for i in sequence:
  next = net.activate(i) > 0.5
  print next

Ceci imprimera un tableau de booléens pour chaque événement.

Answer 2

Plutôt que de garder un historique complet, on peut garder information agrégée sur le passé (ainsi qu'un historique de glissement relativement court, à utiliser comme entrée dans la logique du prédicteur).

Une mise en œuvre provisoire pourrait se dérouler comme suit :
En un mot : Gestion d'un ensemble de chaînes de Markov d'ordre croissant et classement et calcul de la moyenne leurs prévisions

• garder un tableau de comptage des événements individuels, le but est de calculer la probabilité de n'importe lequel des 4 événements différents, sans tenir compte d'une quelconque séquence.
• conserver un tableau de bigrammes comptes c'est-à-dire un compte cumulatif des événements observés [jusqu'à présent].
  La table commence vide, au moment où le deuxième événement est observé, nous pouvons stocker le premier bigramme, avec un compte de 1. Au troisième événement, le bigramme constitué des 2e et 3e événements est "ajouté" à la table : soit en incrémentant le compte d'un bigramme existant, soit en l'ajoutant avec le compte original de 1, comme un nouveau bigramme (jamais vu jusqu'ici). etc.
  En parallèle, gardez un compte total des bigrammes dans la table.
  Ce tableau et le décompte total permettent de calculer la probabilité d'un événement donné, en fonction de l'événement précédent.
• De la même manière, gardez un tableau des comptes de trigrammes, et un compte courant du nombre total de trigrammes vus (notez que cela serait égal au nombre de bigrammes, moins un, puisque le premier trigramme est ajouté un événement après le premier bigramme, et après cela un de chaque est ajouté avec chaque nouvel événement). Ce tableau de trigrammes permet de calculer la probabilité d'un événement donné en fonction des deux événements précédents.
• De même, gardez des tableaux pour les N-Grammes, jusqu'à, disons, 10-grammes (l'algorithme nous dira si nous devons augmenter ou diminuer ce nombre).
• garder une fenêtre coulissante sur les 10 derniers événements.
• Les tableaux ci-dessus fournissent la base de la prédiction ; l'idée générale est la suivante :
  • utiliser une formule qui exprime les probabilités de l'événement suivant comme une moyenne pondérée des probabilités individuelles basées sur les différents N-grammes.
  • récompenser la meilleure longueur individuelle de N-gram en augmentant le poids correspondant dans la formule ; punir les moins bonnes longueurs de la manière inverse. (Attention, la probabilité marginale des événements individuels doit être prise en compte, afin de ne pas favoriser les N-grammes qui prédisent les événements les plus fréquents, quelle que soit la valeur de prédiction relativement faible qui leur est associée).
  • Une fois que le système a "vu" suffisamment d'événements, voyez les valeurs actuelles des poids associés aux longs N-Grammes, et si ceux-ci sont relativement élevés, envisagez d'ajouter des tables pour conserver des informations agrégées sur les plus grands N-Grammes. (Malheureusement, cela nuit à l'algorithme en termes d'espace et de temps).

Il peut y avoir plusieurs variations de la logique générale décrite ci-dessus . En particulier dans le choix de la métrique particulière utilisée pour "noter" la qualité de la prédiction des longueurs individuelles de N-Gram.
D'autres considérations doivent être prises en compte en ce qui concerne détecter et s'adapter à d'éventuels changements dans la distribution des événements (ce qui précède suppose une source d'événements généralement ergodique). Une approche possible consiste à utiliser deux ensembles de tables (en combinant les probabilités en conséquence), et à abandonner périodiquement le contenu de toutes les tables de l'un des ensembles. Le choix de la bonne période pour ces réinitialisations est délicat, car il s'agit essentiellement de trouver un équilibre entre le besoin de volumes d'histoire statistiquement significatifs et le besoin d'une période suffisamment courte pour ne pas manquer les modulations les plus courtes...

Answer 3

La question se pose de savoir combien de temps l'historique que le prédicteur devrait maintenir

La seule réponse est "cela dépend".

Cela dépend de la précision dont on a besoin. Je ne crois pas que cette stratégie puisse être précise à 100%, même avec un historique infini. Essayez un historique de 10 et vous obtiendrez x% de précision, puis essayez 100 et vous obtiendrez y% de précision, etc etc ...

Finalement, vous devriez constater que le système est aussi précis que vous le souhaitez ou que l'augmentation de la précision ne vaut pas l'augmentation de la longueur de l'historique (et l'utilisation accrue de la mémoire, le temps de traitement etc...). À ce stade, soit le travail est terminé, soit vous devez trouver une nouvelle stratégie.

Pour ce que ça vaut, je pense qu'un simple réseau neuronal "doux" pourrait être un meilleur plan.

Answer 4

Nous venons d'étudier prédicteurs de branche dans l'architecture des ordinateurs (parce que le processeur prendrait trop de temps pour évaluer réellement une condition if(EXPRESSION), il essaie de "deviner" et de gagner du temps de cette façon). Je suis sûr que d'autres recherches ont été menées dans ce domaine, mais c'est tout ce à quoi je peux penser pour le moment.

Je n'ai pas vu de configuration unique comme la vôtre, donc je pense que vous devriez faire quelques expériences préliminaires par vous-même. Essayez d'exécuter votre solution pendant un nombre X de secondes avec un historique de N slots, quel est le taux de correction ? Et comparez cela avec le même nombre X fixe et des créneaux d'historique N variables pour essayer de trouver le meilleur rapport mémoire-historique (en les représentant graphiquement).

Si plus d'un événement peut se produire simultanément... c'est un peu compliqué, il doit y avoir des contraintes : que se passe-t-il si un nombre infini d'événements se produisent en même temps ? Uhoh, c'est impossible à calculer pour vous. J'essaierais la même approche qu'un seul événement à la fois, sauf que le prédicteur est capable de prédire plusieurs événements à la fois.

Answer 5

Les processeurs utilisent quelques astuces vraiment légères pour prédire si une instruction de branchement va se brancher ou non. Cela les aide à réaliser un pipe-lining efficace. Ils ne sont peut-être pas aussi généraux que les modèles de Markov par exemple, mais ils sont intéressants en raison de leur simplicité. Voici l'article de Wikipedia sur la prédiction des branches . Voir le Compteur de saturation et le Prédicteur adaptatif à deux niveaux