使用Neo4J模拟马尔可夫链

Question

一个马尔科夫链由一组状态组成，这些状态可以以一定的概率转移到其他状态。

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

但是，您能否使用Neo4J模拟马尔科夫链呢？例如，可以强制Neo4J从某个特定状态开始，然后根据概率进行转换到下一个状态和下一个状态吗？Neo4J能否返回打印出其通过此状态空间所经历的路径？

也许通过一个简单的例子更容易理解。假设我想基于我们公司的技术博客的文本创建一个英语2-gram模型。我启动一个脚本，执行以下操作：

1. 它拉下博客的文本。
2. 它遍历每一对相邻字母，并在Neo4J中创建一个节点。
3. 它再次遍历每个由相邻3个字母组成的三元组，然后在表示前两个字母的节点和表示后两个字母的节点之间创建一个Neo4J有向关系。它在此关系上初始化一个计数器为1。如果关系已经存在，则计数器会增加。
4. 最后，它遍历每个节点，计算出发生的总传输次数，然后在特定节点的每个关系上创建一个新的注释，等于count/totalcount。这是转移概率。

现在Neo4J图形完成了，如何从我的英语2-gram模型中创建一个“句子”呢？以下是输出示例：

IN NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME OF DEMONSTURES OF THE REPTAGIN IS REGOACTIONA OF CRE.

- JnBrymn

---

如果您知道我的“示例句子”来自哪里，那么您将获得额外的积分。这是一篇著名的论文。 - JnBrymn

我被告知，如果我们将其扩展到英语的5-gram模型，那么我们得到的句子与我的Twitter帖子无法区分。 - JnBrymn

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

- Michal Bachman