Modelo estatístico para prever o próximo movimento na rede usando apenas o histórico de movimentos

É possível construir um modelo estatístico que preveja a próxima jogada em um gráfico apenas com base em movimentos passados ​​e na estrutura do gráfico?

Fiz um exemplo para ilustrar o problema:

1. O tempo é discreto . Em cada rodada, você permanece no seu nó / vértice atual ou passa para um dos nós conectados. Como o tempo é discreto e você pode, no máximo, avançar um nó a cada rodada, não há velocidade.
2. Histórico de rotas / movimentos anteriores: {A, B, C} - E a posição atual é: C

3. Próximos movimentos válidos: C, B, X, Y, Z

   1. Se você escolher C, você permanece fixo,
   2. se B se move para trás,
   3. e se X, Y ou Z implica avançar.

4. Não há pesos nos links ou nos nós.

5. Não há nó de destino final. Parte do comportamento do movimento observado é aleatório e parte dele terá alguma regularidade.

Um modelo muito simples - que não leva em consideração o histórico do movimento - apenas previa que C, B, X, Y e Z tinham uma probabilidade de 1/5 de ser o próximo movimento.

Mas com base na estrutura e na história do movimento, acho que é possível criar um melhor modelo estatístico. A instância anterior X deve ter uma probabilidade menor, já que alguém poderia ter se mudado para lá diretamente do nó B na rodada anterior. Da mesma forma, B também deve ter uma probabilidade mais baixa, pois a pessoa poderia ter permanecido fixa na rodada anterior.

Se o usuário se move de volta para B , então a história movimento será parecido com este {A, B, C, B} e os movimentos válidos será A, B, C, D, E, X . Mover para C deve ter menor probabilidade, pois você pode ter permanecido fixo. Mudar para X também deve ter uma probabilidade menor, já que você poderia passar para lá de C na rodada anterior. A história anterior também pode influenciar a previsão, mas deve receber menos peso do que a história recente - ie. 2 rodadas atrás, você poderia ter ficado em B , ou você poderia ter se mudou para A, D, E, X - 3 rodadas atrás, você poderia ter ficado em A .

Olhando em volta, descobri que problemas semelhantes são enfrentados em:

• telecomunicação móvel, em que os operadores tentam prever para qual torre de celular o usuário passará para o próximo, para que possam entregar a transmissão de chamadas / dados sem problemas.
• navegação na web, onde navegadores / mecanismos de pesquisa tentam prever qual página você irá para a próxima, de modo que eles possam pré-carregar e armazenar em cache a página, de forma que o tempo de espera seja reduzido. Da mesma forma, os aplicativos de mapa tentam prever quais blocos de mapa você solicitará a seguir e pré-carregue-os.
• e, claro, a indústria de transportes.

Deseja realmente um modelo estatístico ou apenas um algoritmo para adivinhar o próximo nó, considerando todos os anteriores? Se este último, considere proceder da seguinte maneira.

$\ldots\rightarrow A\rightarrow B\rightarrow C$$X$$Y$$Z$

1. $n_C(X)$$C$$X$$n_C(Y)$$Y$$n_C(Z)$$Z$$n_C=n_C(X)+n_C(Y)+n_C(Z)$$\kappa$$p_C(X) = \frac{\kappa+n_C(X)}{3\kappa+n_C}$

2. $BC$$n_{BC}(X)$$\kappa$$p_{BC}(X) = \frac{\kappa+n_{BC}(X)}{3\kappa+n_{BC}}$

3. $p_{C}(\cdot), p_{BC}(\cdot), p_{ABC}(\cdot), \ldots$$p_\textrm{history}(W)$$p_\cdot(\cdot)$$W$

$\kappa$$\kappa=1$

Dica para a versão que não varia no tempo: Você pode tratar isso como estimativas de probabilidade atualizadas (use o teorema de Bayes), dados alguns dados. Uma probabilidade multinomial e Dirichlet anteriores seriam a abordagem padrão. https://en.wikipedia.org/wiki/Dirichlet-multinomial_distribution

Para o anterior, parece que você deseja que a probabilidade anterior atribua probabilidades iguais de transição a cada nó possível.

Acrescentar os efeitos do tempo (as transições mais antigas importam menos que as mais recentes) é mais complexo. Você pode adicionar uma função de decaimento para obter transições parciais.

Em geral, apenas a estrutura do diagrama não informa nada sobre as probabilidades de transição.

Algumas respostas e algumas perguntas.

Para simplificar, vamos começar assumindo que você está apenas vendo uma longa cadeia de movimentos. O modelo mais simples envolveria uma distribuição multinomial para cada nó (essencialmente em cada nó, existe um dado específico a ser rolado para determinar para onde você vai a seguir). Nosso objetivo seria estimar os parâmetros desses dados. Como Ash mencionou, a abordagem bayesiana seria colocar uma distribuição prévia de Dirichlet em cada dado e atualizá-la com novos dados para obter uma distribuição posterior de Dirichlet . Você pode pensar em uma distribuição Dirichlet como uma fábrica de dados. O fato de a distribuição posterior também ser um Dirichlet é porque a distribuição de Dirichlet é o Conjugado Anteriorà distribuição Multinomial. Embora isso possa parecer bastante confuso, é realmente muito simples. O anterior pode ser interpretado como pseudo-contagem, essencialmente fingindo que você já viu alguns dados (mesmo que não tenha).

Por exemplo, se você está em Z, pode ir para C, D, Z (nosso dado é de três lados aqui). Podemos usar um Dirichlet anterior que age como se já tivéssemos visto uma transição de Z para cada um desses estados. Portanto, cada probabilidade será igual a 1/3. Se o jogador fizer a transição para C, atualizaremos nossa distribuição com mais uma contagem; portanto, a transição de Z para C terá probabilidade 2/4 e o outro terá probabilidade 1/4. Se usarmos um prior com mais pseudo-contagens como se tivéssemos visto 10 transições de Z para cada um dos outros estados, as probabilidades atualizadas (31/11, 10/31, 10/31) estariam muito mais próximas do original queridos, este é um prior mais forte . A força do prior é normalmente determinada pela validação cruzada .

O modelo que descrevi acima é referido como sem memória , porque a probabilidade de fazer a transição de um estado para outro depende apenas do seu estado atual. Se você quisesse fazer algo mais elaborado, poderia incorporar não apenas onde você está atualmente, mas também onde estava no último passo, embora neste momento o número de parâmetros que você precisa estimar aumentará drasticamente e, portanto, a variação na estimativa será bem.

Questão:

Você deu alguma intuição da forma de "Por que eu iria de B-> C-> X quando eu poderia apenas ir de B-> X?" Essas idéias parecem específicas do problema em que você está trabalhando, para que eu possa falar diretamente com ele. Embora isso seja uma preocupação, talvez você queira usar o modelo sem memória (memoryfull?) Ou incorporar essas informações no seu anterior. Se você gostaria de explicar qual é o significado real deste gráfico e, portanto, de onde vem essa intuição, talvez possamos ser mais úteis.

Nota:

Você deseja procurar os modelos Markov, talvez não tanto os modelos Markov ocultos. Aqueles têm um estado oculto que está controlando os dados observados e tentar aprender a usá-los pode atrapalhar esse projeto.