Bayesian network structure training based on a game of learning automata

Bayesian network (BN) is a probabilistic graphical model which describes the joint probability distribution over a set of random variables. Finding an optimal network structure based on an available training dataset is one of the most important challenges in the field of BNs. Since the problem of searching the optimal BN structure belongs to the class of NP-hard problems, typically greedy algorithms are used to solve it. In this paper two novel learning automata-based algorithms are proposed to solve the BNs’ structure learning problem. In both, there is a learning automaton corresponding with each possible edge to determine the appearance and the direction of that edge in the constructed network; therefore, we have a game of learning automata, at each stage of the proposed algorithms. Two special cases of the game of the learning automata have been discussed, namely, the game with a common payoff and the competitive game. In the former, all the automata in the game receive a unique payoff from the environment, but in the latter, each automaton receives its own payoff. As the algorithms proceed, the learning processes focus on the BN structures with higher scores. The use of learning automata has led to design the algorithms with a guided search scheme, which can avoid getting stuck in local maxima. Experimental results show that the proposed algorithms are capable of finding the optimal structure of BN in an acceptable execution time; and compared with other search-based methods, they outperform them.