Faculty Recruiting Support CICS

Bounding and Counting Linear Regions of Deep Neural Networks

22 Mar
Friday, 03/22/2019 11:00am to 12:00pm
Isenberg School of Management N135
Special Event
Speaker: Dr. Thiago Serra

One form of characterizing the expressiveness of a piecewise linear neural network is by the number of linear regions, or pieces, of the function modeled. In this talk, we investigate the number of linear regions that these networks can attain, both theoretically and empirically. We present upper and lower bounds for the maximum number of linear regions on rectifier and maxout networks and a method to perform exact counting of the number of regions by modeling the DNN as a mixed-integer linear program. These bounds come from leveraging the dimension of the space defining each linear region, and they indicate that a shallow network may define more linear regions than any deep network. We also show how to approximate the number of linear regions of a rectifier network with an algorithm for probabilistic lower bounds on the number of solutions of mixed-integer linear programs. This algorithm is several orders of magnitude faster than exact counting and the values reach similar orders of magnitude, hence making it a viable method to compare the expressiveness of such networks. This talk is based on joint work with Christian Tjandraatmadja (Google) and Srikumar Ramalingam (The University of Utah). The papers can be found on  arXiv:https://arxiv.org/abs/1711.02114 and https://arxiv.org/abs/1810.03370.

Thiago Serra is a Visiting Research Scientist at Mitsubishi Electric Research Labs and will join Bucknell University's Freeman College of Management as Assistant Professor of Business Analytics in Fall 2019. His current work focuses on theory and applications of mathematical optimization, including deep learning, decision diagrams, and scheduling. Thiago recently obtained his Ph.D. in Operations Research at Carnegie Mello University's Tepper School of Business and received the Gerald L. Thompson Doctoral Dissertation Award in Management Science. He was also awarded the INFORMS Judith Liebman Award in 2016 for student chapter service and best poster awards at the INFORMS 2016 Annual Meeting and the 2018 Princeton Day of Optimization.