Complexity of evaluting DBNs

The engine.
Post Reply
sverrevr
Posts: 26
Joined: Mon Aug 24, 2020 7:37 am

Complexity of evaluting DBNs

Post by sverrevr »

Hi!
I am attempting to use DBNs for on-line decision making, where the system also needs to reason a bit backward in time as well as forwards. But I'm struggling with the computational time for some models and some scenarios suddenly becomes very high, or result in coopers algorithm not finding a solution. While for other models, that to me don't seem much simpler, the solution is found very quickly even for a much longer time-horizon.

So I'm wondering if anyone has any tips on what makes the problem difficult or unsolvable for SMILE?

Edit: in the last part of the post i talked about the forward-backward algorithm, but I don't think that is applicable with multiple nodes?
Furthermore, I was wondering how the time-complexity of the solver used by SMILE compares to the Forward-Backward algorithm. For a DBN with connections of order 1, the forward-backward algorithm should be useable, which should have a complexity that grows linearly with the number of time-steps. Do you suspect that solving the DBN with a forward-backward algorithm between time-steps would keep the computational time down?
marek [BayesFusion]
Site Admin
Posts: 430
Joined: Tue Dec 11, 2007 4:24 pm

Re: Complexity of evaluting DBNs

Post by marek [BayesFusion] »

Hi sverrevr,

The primary factor in complexity of probabilistic inference is the maximum clique size and this depends strongly on the connectivity of the network. One imperfect way of getting an idea about how a model will do is looking at the maximum in-degree. In case of a DBN, I suggest that you unroll it and have a look at the unrolled network. Should there be a node with high in-degree, you can improve inference greatly by reducing that in-degree. This is just a heuristic but it usually works well.

SMILE does not use any specialized inference algorithms because it allows for very general DBNs with influences of any order. I believe that our implementation is quite unique in this respect. Please have a look at the MenstrualCycle model in our repository to get an idea how useful are higher order influences. I believe that they are indispensable when the modeled problem has memory.

I suspect that you are right in expecting that Forward-Backward algorithm, usable when the temporal influences are of the first order only, might beat the brute force clustering algorithm that we are using. On the other hand, SMILE's clustering algorithm is very, very efficient. What do you mean by "coopers" algorithm in the context of DBNs?
Cheers,

Marek
sverrevr
Posts: 26
Joined: Mon Aug 24, 2020 7:37 am

Re: Complexity of evaluting DBNs

Post by sverrevr »

Hi Marek, thanks for the great reply!
I completely understand the usefulness of your general approach enabling a wide range of models :)

I don't really know what coopers algorithm is, it was taken from the error message I got from Python when the problem became too complicated: "Error when running Cooper's algorithm". I exported the unrolled net and opened it in genie, where I got the error: "Error (-42): UpdateBeliefs failed - network structure is too complex."

I checked out the in-degree but it is what I presume quite low, avg 1.27, max 3.

What might be causing the difficulties is that the network at each time-step is not identical. I'm modeling a system where there are a set of different tasks. The system is visiting each task multiple times, and has to remember the state of the tasks between visits. I modeled this by having a node for each task that is connected to itself with a 1. order arc. In python I save a list of the current task at each time-step in the DBN. After the net is unrolled in python, I go through all time-steps and connect the correct task to the network (the rest of the tasks are then only connected to their past and future selves). The network also contains states that do not change with the task.

But it is not always problematic to solve this problem. It first became problematic when I introduced to nodes that acted quite similarly, I think.

Do you think this makes it difficult for SMILE to solve the network, or should it not matter? If so, do you have any ideas on how this could be modeled in a compatible way with SMILE :)

Best regards
Sverre
marek [BayesFusion]
Site Admin
Posts: 430
Joined: Tue Dec 11, 2007 4:24 pm

Re: Complexity of evaluting DBNs

Post by marek [BayesFusion] »

Hi Sverre,

Cooper's algorithm is used in influence diagrams. Does your DBN contain any decision or utility nodes?

Your in-degree is indeed small. Another factor is the number of states. Do your variables have many states? If not, then it is just the size and the connectivity of your network. Things that you can do to reduce complexity is decreasing the number of time steps. Is it perhaps unusually large? I guess there is little you can do about the connectivity but one thing that you could try is removing some of the weaker arcs. Finally, when everything fails, you can try an approximate sampling algorithm. I would suggest EPIS-BN, which is quite likely the most efficient sampling algorithm in existence. The calculation time is going to be larger but quite predictable. You can control it by manipulating the number of samples (Network Properties/Inference).

I hope this helps,

Marek
sverrevr
Posts: 26
Joined: Mon Aug 24, 2020 7:37 am

Re: Complexity of evaluting DBNs

Post by sverrevr »

Hi Marek, thank for the help!

My DBN does contain a decision node but no utility. Does this affect things? I could just replace it with a chance node and set evidence on that node:)

My variables have 7 states, i tried reducing them to 5 but that did not affect much. I also tried setting target nodes, but that did not help much either.

Thanks for the tips on using the EPIS-BN algorithm, it work great! It is a bit slow and the result is a bit inprecie, but the inprecission is not very problematic for my problem. And it is quite useful for on-line applications to have a constant run-time! That way there wont be any random slow exeuctions. The EPIS-BN algorithm manage to solve the problem when the exact solver failed, and the result was reasonable :)

For those wanting to use the EPIS algorithm in pycharm do the following to set the algorithm and sample count:

Code: Select all

net = pysmile.Network()
net.set_bayesian_algorithm(pysmile.BayesianAlgorithmType.EPIS_SAMPLING)
net.set_sample_count(10000)
marek [BayesFusion]
Site Admin
Posts: 430
Joined: Tue Dec 11, 2007 4:24 pm

Re: Complexity of evaluting DBNs

Post by marek [BayesFusion] »

Hi Sverre,

The decision node explains why you have a message relating to "Cooper's algorithm" :-). It is a special algorithm used in influence diagrams. It may help to replace it with a chance node but it sounds like your network is quite complex, so you may have to try other simplifications. By replacing the decision node with a chance node that you will set, you should reduce the calculation time n-fold, where n is the number of states in that node.

Glad to hear that EPIS-BN offers reasonable calculation times!

Marek
Post Reply