10

マルコフ連鎖は、一定の確率で他の状態に遷移できる一連の状態で構成されます。

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

しかし、Neo4J を使用してマルコフ連鎖をシミュレートできますか? たとえば、Neo4J を強制的に特定の状態で開始し、確率に基づいて次の状態と次の状態に遷移させることはできますか? Neo4J は、この状態空間を通過したパスの出力を返すことができますか?

おそらく、これは簡単な例で理解しやすいでしょう。私の会社の技術ブログのテキストに基づいて、英語の 2 グラム モデルを作成したいとします。次のことを行うスクリプトを作成します。

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

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

NO IST LAT ホエイ CRATICT FROURE BIRS GROCID PONDENOME OF DEMONSTURES OF THE REPTAGIN IS REGOACTIONA OF CRE.

4

1 に答える 1

6

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

いくつかの変更を加えて、ここであなたの実験を再現しました。最初に、テキストを 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());
    }
}
于 2013-07-05T11:30:59.350 に答える