CODEWITHSUNDEEP
pythonartificial-intelligencebayesian-networks
AmateurCoder
AmateurCoder

Reputation: 29

Bayesian network algorithm for dummies?

Is there a simple and easy explanation for the algorithm for Bayesian networks without all the bombastic terms? I am not allowed to use libraries, so please do not just give me a library and tell me how easy it is to use it.

So I understand we have conditional probability tables (CPT), and we are supposed to multiply them together and perform variable elimination, but how do I implement this in code? So I tried representing each CPT as a list of dictionaries:

{
            {
                "Cavity": "True",
                "own_value": "True",
                "probability": 0.9
            },
            {
                "Cavity": "True",
                "own_value": "False",
                "probability": 0.1
            },
            {
                "Cavity": "False",
                "own_value": "True",
                "probability": 0.4
            },
            {
                "Cavity": "False",
                "own_value": "False",
                "probability": 0.6
            }
}

And then inserting these CPTs into another dict.

However, I am unable to go forward as to how to multiply these CPTs and where to keep them? E.g. P(A|B, C, D) * P(D|E, F) = P(A, D|B, C, E, F)

The product of 2 CPTs can result in a factor that has multiple heads, so a dict no longer works...

Basically the following code snippet is the algorithm that I can come up with so far, where I store a queue of nodes and pass them into this function until all known probabilities of all nodes are found. And of course, the queue is already in topological order such that the parents is always guaranteed to be a known probability.

But as you have realized right now, this algorithm is only able to answer P(A = true) or P(C = false), etc

        cpt = self.conditional_probabilities[nodeName] #get my cpt
        for parent in self.dependencies[nodeName]:
            parentProb = self.knownProbabilities[parent]

            #matching of the parent and multiplying the probability
            for probability in parentProb:
                varName = probability
                varProb = parentProb[probability]
                for item in cpt:
                    if parent in item and (item[parent] == varName):
                        item["probability"] = item["probability"] * varProb

            #eliminate the parent node
            #some code here

        #insert known probability into my known probabilities table 
        #e.g. insert P(A) into a dict() of P(B), P(C), ... where A, B, C are keys
        nodeProbability = dict()
        for item in cpt:
            state = item["own_value"]
            nodeProbability[state] = item["probability"]

        self.knownProbabilities[nodeName] = nodeProbability

And this is unable to perform Bayesian network queries like P(A = true, B = false| C = false, D = "donkey", E = "cat").

Where D, E has a domain of ["donkey", "cat", "dog", "mouse"] and the rest are Boolean.

TL;DR Can anyone explain to me using simple data structures (list, pq, dict, etc), how to implement a Bayesian Network?

Upvotes: 0

Views: 861

Answers (1)

frankk
frankk

Reputation: 123

It's a little late, but for others searching on how to model a Bayesian Network and do inference, here are some hints:
There is a very good course on Probabilistic Graphical Models by Daphne Koller on Coursera.
The course uses a data structure called factor to store values of a discrete probability distribution (marginal distribution or CPT).
A factor contains a vector to store the values of a discrete probability distribution. Furthermore, it contains some metadata, a vector of indices of variables contained in the factor and the cardinalities of these variables.
A tutorial explaining the use of factors to model Bayesian networks can be found here.
An implementation of the Variable Elimination algorithm using factors can be found here.
It is not in Python, but if you understand some C++, then you can probably think of how to implement it in Python. And an example of usage of factors and the Variable Elimination algorithm can be found here:
readme, code

Upvotes: 0

Related Questions