Structure Learning of High-Order Dynamic Bayesian Networks via Particle Swarm Optimization with Order Invariant Encoding

• David Quesada ^[1] ; Concha Bielza ^[1] ; Pedro Larrañaga ^[1]
  1. [1] Universidad Politécnica de Madrid

     Universidad Politécnica de Madrid

     Madrid, España

     
• Localización: Hybrid Artificial Intelligent Systems: 16th International Conference, HAIS 2021. Bilbao, Spain. September 22–24, 2021. Proceedings / coord. por Hugo Sanjurjo González, Iker Pastor López , Pablo García Bringas , Héctor Quintián Pardo , Emilio Santiago Corchado Rodríguez , 2021, ISBN 978-3-030-86271-8, págs. 158-171
• Idioma: inglés
• Texto completo no disponible (Saber más ...)
• Resumen

  • Dynamic Bayesian networks usually make the assumption that the underlying process they model is first-order Markovian, that is, that the future state is independent of the past given the present. However, there are situations in which this assumption has to be relaxed. When this order increases, the size of the search space grows greatly, not all structure learning algorithms may be suited to learn higher-order networks, and a new appropriate order has to be found. To address the computational issues of huge networks, we propose a structure learning method that uses particle swarm optimization to search in the space of possible structures. To avoid the additional costs of increasing the Markovian order, we provide an order-invariant encoding that represents the networks as vectors of natural numbers whose length remains constant. Due to this encoding, we only need to set a maximum desired order rather than the exact one. Our experimental results show that this method is efficient in high orders and performs better than similar algorithms in both execution time and quality of the obtained networks.