Simulazione di una catena Markov con Neo4J

Question

A Markov chain è composto da un insieme di stati che possono passare ad altri stati con una certa probabilità.

Una catena di Markov può essere facilmente rappresentata in Neo4J creando un nodo per ogni stato, una relazione per ogni transizione e quindi annotando le relazioni di transizione con la probabilità appropriata.

MA, puoi simulare la catena di Markov utilizzando Neo4J? Ad esempio, Neo4J può essere costretto a iniziare in un determinato stato e quindi a passare allo stato successivo e allo stato successivo in base alle probabilità? Neo4J può tornare con una stampa del percorso che ha attraversato questo spazio di stato?

Forse questo è più facile da capire con un semplice esempio. Diciamo che voglio fare un modello di inglese di 2 grammi basato sul testo di my company's tech blog. Creo uno script che effettua quanto segue:

1. Abbassa il testo del blog.
2. It ita su ogni coppia di lettere adiacenti e crea un nodo in Neo4J.
3. Ripete di nuovo ogni tupla in 3 lettere adiacenti e quindi crea una relazione diretta Neo4J tra il nodo rappresentato dalle prime due lettere e il nodo rappresentato dalle ultime due lettere. Inizializza un contatore su questa relazione su 1. Se la relazione esiste già, il contatore viene incrementato.
4. Infine, itera su ciascun nodo, conta quante transizioni totali in uscita si sono verificate e quindi crea una nuova annotazione su ciascuna relazione di un nodo particolare uguale a count/totalcount. Questa è la probabilità di transizione.

Ora che il grafico Neo4J è completo, come faccio a creare una "frase" dal mio modello di inglese da 2 grammi? Ecco come potrebbe apparire l'output:

IN NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME DI DEMONSTURES DEL REPTAGIN È REGOACTIONA DI CRE.

Answer 1

Neo4j non fornisce la funzionalità richiesta, ma poiché si è giunti a compilare correttamente il database, l'attraversamento di cui si ha bisogno è costituito da poche righe di codice.

Ho ricreato l'esperimento here, con alcune modifiche. Prima di tutto, popolo il database con un singolo passaggio attraverso il testo (passaggi 2 e 3), ma quello è un minore. Ancora più importante, memorizzo solo il numero di occorrenze su ogni relazione e il numero totale sul nodo (fase 4), poiché non penso che sia necessario precalcolare le probabilità.

Il codice che stai chiedendo sembra poi qualcosa di simile:

/** 
* A component that creates a random sentence by a random walk on a Markov Chain stored in Neo4j, produced by 
* {@link NGramDatabasePopulator}. 
*/ 
public class RandomSentenceCreator { 

    private final Random random = new Random(System.currentTimeMillis()); 

    /** 
    * Create a random sentence from the underlying n-gram model. Starts at a random node an follows random outgoing 
    * relationships of type {@link Constants#REL} with a probability proportional to that transition occurrence in the 
    * text that was processed to form the model. This happens until the desired length is achieved. In case a node with 
    * no outgoing relationships it reached, the walk is re-started from a random node. 
    * 
    * @param database storing the n-gram model. 
    * @param length desired number of characters in the random sentence. 
    * @return random sentence. 
    */ 
    public String createRandomSentence(GraphDatabaseService database, int length) { 
     Node startNode = randomNode(database); 
     return walk(startNode, length, 0); 
    } 

    private String walk(Node startNode, int maxLength, int currentLength) { 
     if (currentLength >= maxLength) { 
      return (String) startNode.getProperty(NAME); 
     } 

     int totalRelationships = (int) startNode.getProperty(TOTAL, 0); 
     if (totalRelationships == 0) { 
      //terminal node, restart from random 
      return walk(randomNode(startNode.getGraphDatabase()), maxLength, currentLength); 
     } 

     int choice = random.nextInt(totalRelationships) + 1; 
     int total = 0; 
     Iterator<Relationship> relationshipIterator = startNode.getRelationships(OUTGOING, REL).iterator(); 

     Relationship toFollow = null; 
     while (total < choice && relationshipIterator.hasNext()) { 
      toFollow = relationshipIterator.next(); 
      total += (int) toFollow.getProperty(PROBABILITY); 
     } 

     Node nextNode; 
     if (toFollow == null) { 
      //no relationship to follow => stay on the same node and try again 
      nextNode = startNode; 
     } else { 
      nextNode = toFollow.getEndNode(); 
     } 

     return ((String) nextNode.getProperty(NAME)).substring(0, 1) + walk(nextNode, maxLength, currentLength + 1); 
    } 

    private Node randomNode(GraphDatabaseService database) { 
     return random(GlobalGraphOperations.at(database).getAllNodes()); 
    } 
}