Exhibition Program

Science of Machine Learning

01

Learning and finding congestion-free routes

- Online shortest path algorithm with binary decision diagrams -

Abstract

We consider adaptively finding congestion-free routes connecting specified two locations on a network. In many practical scenarios, congestion on a network, or transmission time taken to send messages, changes dynamically. Therefore, we need to effectively learn congestion using past congestion data and efficiently find a congestion-free route each time we send a message. While there exist learning algorithms that can be used for predicting congestion, they incur too much computation cost due to the presence of a huge number of possible routes. We overcome this difficulty by using the zero-suppressed binary decision diagram (ZDD), which is a compact representation of all possible routes. We develop a learning algorithm that can work on ZDDs without examining all possible routes explicitly, which enbles us to find congestion-free routes far more efficiently than the existing algorithms.

References

  • [1] S. Sakaue, M. Ishihata, S. Minato, “Efficient bandit combinatorial optimization algorithm with zero-suppressed binary decision diagrams,” in Proc. 21st International Conference on Artificial Intelligence and Statistics (AISTATS), 2018.
  • [2] N. Cesa-Bianchi, G. Lugosi, “Combinatorial bandits,” Journal of Computer and System Sciences, Vol. 78, No. 5, pp. 1404—1422, 2012.

Poster

Photos

Contact

Shinsaku Sakaue, Linguistic Intelligence Research Group, Innovative Communication Laboratory
Email: