Que combinação de estruturas de dados armazena eficientemente redes bayesianas discretas?

22

Entendo a teoria por trás das redes bayesianas e estou me perguntando o que é preciso para construir uma na prática. Digamos, neste exemplo, que eu tenho uma rede bayesiana (dirigida) de 100 variáveis ​​aleatórias discretas; cada variável pode ter um de até 10 valores.

Armazeno todos os nós em um DAG e, para cada nó, armazenamos sua Tabela de Probabilidade Condicional (CPT)? Existem outras estruturas de dados que eu deveria usar para garantir o cálculo eficiente dos valores quando alguns CPTs mudam (além daqueles usados ​​por um DAG)?

data-structures machine-learning cinza
fonte
Estou usando o banco de dados sqlite na memória para armazenar tabelas de CP, pois espera-se que os DBs tenham algoritmos e estruturas de dados eficientes para lidar com tabelas. Funciona bem! :)
Pratik Deoghare 21/03
Defina o que você quer dizer com eficiente (memória, desempenho, etc.) e inclua suas restrições. Sem eles, isso poderia facilmente acabar com um concurso para os mais eficientes, que se degradarão em códigos enigmáticos com os quais eu nunca gostaria de lidar no dia-a-dia.
23712 Justin Bozonier
1
@JustinBozonier requer menos memória e é rápido?
Pratik Deoghare 21/03

Respostas:

12

A "melhor" estrutura de dados provavelmente depende de qual problema específico você está tentando resolver com ela. Aqui está uma abordagem que eu já vi (e me usei), que simplesmente armazena todas as informações e deixa para o algoritmo o que fazer com elas.

  1. Primeiro, você indexa os nós por números inteiros exclusivos, de 0 a n-1. Em seguida, você simplesmente armazena, para cada nó, a lista de seus pais como uma matriz de números inteiros --- em C ++, por exemplo, você pode ter um std::vector<std::vector<int> >: primeiro vetor sobre nós, o segundo vetor lista os respectivos pais). Isso captura toda a estrutura do DAG.

  2. Além disso, como cada nó tem exatamente uma tabela de probabilidade condicional associada, você pode indexar aqueles com os mesmos IDs inteiros. Para cada tabela de probabilidade, você precisa armazenar seu escopo, ou seja, o conjunto de variáveis ​​aleatórias definidas acima. Em segundo lugar, você provavelmente teria uma grande lista de números de ponto flutuante que contém as probabilidades condicionais reais (e você deve ter certeza de obter a indexação correta). Para dar um exemplo de C ++ novamente, algo como isto poderia fazer:

    struct CondProbTable {
    std::vector<int> scope;    // list of random variables the CPT is defined over
    std::vector<double> table; // appropriately sized and indexed table of
                               // conditional probabilities
};

    Com isso, você pode usar a std::vector<CondProbTable>para armazenar todos os seus CPTs.

Novamente, isso basicamente armazena apenas a rede Bayes, não assume nada sobre o que você quer fazer com ela. A inclusão do escopo da CPT no CondProbTable é um pouco redundante, pois pode ser inferido a partir da lista de nós pai descritos no ponto 1.

muito
fonte
0

CPT basicamente discretos são hipermatrixes, e você deve examiná-los dessa maneira.

Uma maneira bastante comum de representar uma hipermatriz é usar uma hashtable usando o índice de string. por exemplo, em 2 dimensões t [1] [2] seria t.get ("1_2")

É possível uma solução mais eficiente em memória: se a hipermatriz for esparsa, você poderá usar representação esparsa especial (por exemplo, Fuchs 72); se tiver estrutura, poderá usar ADD (diagrama de decisão algébrico) ou regras baseadas em lógica.

Sua última pergunta não é muito clara; no entanto, se você espera que seu CPT mude com frequência, provavelmente será melhor uma representação plana do CPT com uma tabela ou uma hashtable.

Nicolas
fonte