Neo4Jでマルコフ連鎖をシミュレートする

Question

A Markov chainは、ある確率で他の状態に遷移することができる一連の状態で構成されています。

各状態のノードを作成し、各遷移の関係を作成し、遷移関係に適切な確率で注釈を付けることで、マルコフチェーンをNeo4Jで簡単に表現できます。

あなたはをシミュレートできますか？ Neo4Jを使用してマルコフチェーンをシミュレートしますか？たとえば、ある状態でNeo4Jを強制的に開始し、確率に基づいて次の状態および次の状態に遷移させることはできますか？ Neo4Jは、この状態空間を通過した経路をプリントアウトすることができますか？

おそらく、これは簡単な例で分かりやすいでしょう。 my company's tech blogのテキストに基づいて2グラムの英語モデルを作成したいとしましょう。私は次のスクリプトをスピンアップします：

1. ブログのテキストをプルダウンします。
2. これは隣接するすべての文字のペアを繰り返し、Neo4Jにノードを作成します。
3. これは、隣接する文字の3タプルごとに再度繰り返し、最初の2文字で表されるノードと最後の2文字で表されるノードとの間にNeo4Jの指向関係を作成します。この関係のカウンタを1に初期化します。関係がすでに存在する場合は、カウンタがインクリメントされます。
4. 最後に、各ノードを反復し、発生したアウトバウンドトランジションの数をカウントし、特定のノードの各リレーションシップに新しい注釈を作成します（count/totalcount）。これが遷移確率です。

これでNeo4Jグラフが完成しました.2グラムの英語モデルから「文章」を作成するにはどうすればよいですか？出力は次のようになります。

レパタジンの造影剤の繁殖した雌ブタがウサギの頭上にあります。

Answer 1

Neo4jは、すぐに使用できる機能を提供していませんが、データベースに正しくデータを入力することができますので、必要なトラバーサルはほんの数行です。

実験番号hereをいくつか変更して再作成しました。まず、テキストを1度パススルーしてデータベースを作成しますが（ステップ2と3）、それはマイナーです。さらに重要なのは、確率をあらかじめ計算する必要がないと考えているため、各関係に出現回数とノードの総数のみを格納することです（手順4）。あなたはそこに私の「サンプル文は、」から来た知っていれば

/** 
* 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()); 
    } 
}