neo4j - 使用 Neo4J 模拟马尔可夫链

Question

Markov chain由一组状态组成，这些状态可以以一定的概率转移到其他状态。

通过为每个状态创建一个节点，为每个转换创建一个关系，然后用适当的概率注释转换关系，可以在 Neo4J 中轻松表示马尔可夫链。

但是，您可以使用 Neo4J 模拟马尔可夫链吗？例如，是否可以强制 Neo4J 从某个状态开始，然后根据概率转换到下一个状态和下一个状态？ Neo4J 能否返回它通过这个状态空间的路径的打印输出？

也许用一个简单的例子更容易理解。假设我想根据 my company's tech blog 的文本制作一个 2-gram 的英语模型。 .我启动了一个脚本，它执行以下操作:

它拉下博客的文本。

它遍历每对相邻的字母并在 Neo4J 中创建一个节点。

它再次迭代相邻字母的每个 3 元组，然后在由前两个字母表示的节点和由最后两个字母表示的节点之间创建 Neo4J 有向关系。它将此关系上的计数器初始化为 1。如果该关系已存在，则计数器递增。

最后，它遍历每个节点，计算发生了多少总传出转换，然后在特定节点的每个关系上创建一个新的注释，等于 count/totalcount。 .这就是转移概率。

现在 Neo4J 图已经完成，我如何让它从我的 2-gram 英语模型中创建一个“句子”？输出可能如下所示:

在 NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME of DEMONSTURES REPTAGIN 是 REGOACTIONA of CRE。

Answer 1

Neo4j 没有提供您要求的开箱即用的功能，但是由于您已经能够正确填充数据库，因此您需要的遍历只是几行代码。
我重新创建了您的实验 here ，经过一些修改。首先，我通过一次文本(步骤 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());
    }
}