Algorithme d'apprentissage automatique pour prédire L'Ordre des événements?

Si vous avez seulement un temps fixe pour regarder en arrière, fenêtre de temps d'approches pourraient suffire. Vous prenez les données de séquence et les divisez en fenêtres de chevauchement de longueur N. (eg. vous divisez une séquence ABCDEFG en ABC, BCD, CDE, DEF, EFG). Ensuite, vous formez un approximateur de fonction (par exemple réseau neuronal ou régression linéaire) pour mapper les premières parties n-1 de cette fenêtre sur le n-ième partie.

votre prédicteur ne sera pas capable de regarder en arrière dans le temps plus longtemps que la taille de votre fenêtre. RNNs et HMMs peuvent le faire en théorie, mais sont difficiles à accorder ou parfois ne fonctionnent tout simplement pas.

(les implémentations RNN de L'état de la technique 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 pourrait y avoir des typos et des trucs, mais la structure globale devrait travail.)

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()

cela formera le réseau récurrent pour 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_item = net.activate(i) > 0.5
  print next_item

ceci affichera un tableau de booléens pour chaque événement.

au lieu de garder une histoire complète, on peut garder informations agrégées sur le passé (avec une histoire de glissement relativement courte, à utiliser comme entrée dans la logique du prédicteur).

Une tentative de mise en œuvre pourrait aller comme ceci:

En un mot: la Gestion d'un ensemble de chaînes de Markov ordre croissant et classement et moyenne leur les prédictions

• tenir un tableau des comptes d'événements individuels, le but est de calculer la probabilité de l'un des 4 événements différents, sans égard à toute séquence.
• garder une table de bigram compte, c'est à dire le nombre total des événements observés [jusqu'à présent]
  
  La Table commence vide, sur le deuxième événement observez, nous pouvons stocker le premier bigramme, avec un compte de 1. au-delà du troisième événement, le bigramme composé des 2ème et 3ème events est "ajouté" à la table: soit incrémenter le compte d'un bigramme existant ou ajouté avec le compte original 1, comme un nouveau (jamais-vu-jusqu'à présent) bigramme. etc.
  
  En parallèle, gardez un compte total de bigrammes dans la table.
  
  Ce tableau et le total permettent de calculer la probabilité d'un événement donné, basé sur l'événement précédent.
• de la même façon, conservez un tableau du nombre de trigrammes, et un décompte courant du nombre total de trigrammes vu (notez que ceci serait égal au nombre de bigrams, moins un, depuis le premier trigramme est ajouté un événement après la première bigram, et après qu'un de chaque est ajouté à chaque nouvel événement). Ce tableau de trigramme permet de calculer la probabilité d'un événement donné basé sur les deux événements précédents.
• de même, gardez les tables pour n-grammes, jusqu'à, disons, 10 grammes (l'algorithme indiquera si nous devons augmenter ou diminuer ceci).
• garder des fenêtres coulissantes dans les 10 derniers événement.
• Les tableaux ci-dessus fournissent la base pour la prévision, l'idée générale est de:
  • utilisez 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écompensez la meilleure longueur individuelle de n-gramme en augmentant le poids correspondant dans la formule; punissez les longueurs les plus mauvaises de la manière inverse. (Attention à la probabilité marginale des événements individuels nécessite a prendre en compte de peur que nous ne favorisions les N-grammes qui arrivent à prédire les événements les plus fréquents, indépendamment de la valeur de prévision relativement faible qui leur est associée)
  • une fois que le système a "vu" assez d'événements, voir les valeurs courantes pour les poids associés aux N-grammes longs, et si ceux-ci sont relativement élevés, envisager d'ajouter des tableaux pour garder l'information agrégée sur les N-grammes plus gros. (Cela nuit malheureusement à l'algorithme à la fois en termes d'espace et temps)

il peut y avoir plusieurs variantes de la logique générale décrite ci-dessus. En particulier dans le choix de la métrique particulière utilisée pour "classer" la qualité de la prédiction des longueurs N-Gramme individuelles.

D'autres considérations devraient être formulées en ce qui concerne détection et de s'adapter aux éventuels changements dans les événements de la distribution (ce qui précède suppose une source d'événement généralement ergodique). Une approche possible est utiliser deux ensembles de tableaux (en combinant les probabilités en conséquence) et supprimer périodiquement le contenu de tous les tableaux de l'un des ensembles. Choisir la bonne période pour ces réinitialisations est une entreprise délicate, équilibrant essentiellement le besoin de volumes statistiquement significatifs de l'histoire et le besoin de période assez courte de peur que je manque sur les modulations plus courtes...

la question se pose de savoir combien de temps le prédicteur doit conserver

La seule réponse est "ça dépend".

Cela dépend de l'exactitude de cette doit être. Je ne crois pas que cette stratégie puisse être exacte à 100% même avec une histoire infinie. Essayez un historique de 10 et vous obtiendrez X % de précision, puis essayez 100 et vous obtiendrez y % de précision,etc...

Finalement, vous devriez trouver le système est aussi précis que vous le désir de l'être ou vous trouverez l'augmentation de la précision ne vaudra pas l'augmentation de la longueur de l'histoire (et l'utilisation accrue de la mémoire, le temps de traitement, etc...). À ce stade, soit de travail, ou vous avez besoin de trouver une nouvelle stratégie.

pour ce que ça vaut, je pense que regarder dans un simple réseau neuronal "doux" pourrait être un meilleur plan.

Nous avons étudié sur branche-prédicteurs en architecture informatique(parce que le processeur prendrait trop de temps pour évaluer une condition si (EXPRESSION), il essaie de "deviner" et de gagner du temps de cette façon). Je suis sûr que d'autres recherches ont été faites 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 pourriez avoir besoin de faire quelques expériences préliminaires sur votre propre. Essayez d'exécuter votre solution pour X nombre de secondes avec un historique de n slots, Quel est le rapport d'exactitude? Et comparez cela avec le même X fixe et la variation N des fentes d'histoire pour essayer de trouver le meilleur rapport mémoire-histoire (Les représentant graphiquement ).

si plusieurs événements peuvent se produire simultanément... c'est un peu l'esprit de flexion, il y a quelques contraintes : si ce nombre infini d'événements se produisent à un moment? Uhoh, c'est mathématiquement impossible pour vous. J'essaierais la même approche qu'un seul événement à la fois, sauf lorsque le prédicteur est activé, prédire plusieurs événements à la fois.

les processeurs utilisent quelques trucs vraiment légers pour prédire si une instruction de branche va se brancher ou non. Cette aide efficace de gainage. Ils ne sont peut-être pas aussi généraux que les modèles Markov, par exemple, mais ils sont intéressants en raison de leur simplicité. Voici L'article de Wikipedia sur la prédiction de branche. Voir le Compteur De Saturation et Prédicteur Adaptatif À Deux Niveaux