Моделирование цепи Маркова с Neo4J

Question

A Markov chain состоит из множества состояний, которые могут с определенной вероятностью перейти в другие состояния.

Цепочка Маркова может быть легко представлена ​​в Neo4J путем создания узла для каждого состояния, отношения для каждого перехода, а затем аннотации отношений перехода с соответствующей вероятностью.

НО, вы можете имитировать цепь Маркова с использованием Neo4J? Например, можно ли заставить Neo4J начать в определенном состоянии, а затем переходить в следующее состояние и следующее состояние на основе вероятностей? Может ли Neo4J вернуться с распечаткой пути, который прошел через это состояние?

Возможно, это проще понять на простом примере. Предположим, я хочу сделать 2-граммовую модель английского языка на основе текста my company's tech blog. Я прокручиваю сценарий, который выполняет следующие действия:

1. Он снимает текст блога.
2. Он выполняет итерацию по каждой паре смежных букв и создает узел в Neo4J.
3. Итерирует снова через каждые 3 кортежа смежных букв, а затем создает направленную связь Neo4J между узлом, представленным первыми двумя буквами, и узлом, представленным двумя последними буквами. Он инициализирует счетчик для этого отношения равным 1. Если отношение уже существует, счетчик увеличивается.
4. И, наконец, он выполняет итерацию через каждый узел, подсчитывает, сколько общих исходящих переходов произошло, а затем создает новую аннотацию для каждой связи конкретного узла, равную count/totalcount. Это вероятность перехода.

Теперь, когда график Neo4J завершен, как мне заставить его создать «предложение» из моей 2-граммовой модели английского языка? Вот как выглядит результат:

В НЕТ IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME DEMONSTURES OF REPTAGIN - РЕГЛАМЕНТИРОВАНИЕ 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()); 
    } 
}