Optimization Online


Bounding and Counting Linear Regions of Deep Neural Networks

Thiago Serra(tserra***at***gmail.com)
Christian Tjandraatmadja(ctjandra***at***andrew.cmu.edu)
Srikumar Ramalingam(srikumar***at***cs.utah.edu)

Abstract: In this paper, we study the representational power of deep neural networks (DNN) that belong to the family of piecewise-linear (PWL) functions, based on PWL activation units such as rectifier or maxout. We investigate the complexity of such networks by studying the number of linear regions of the PWL function. Typically, a PWL function from a DNN can be seen as a large family of linear functions acting on millions of such regions. We directly build upon the work of Montufar et al. (2014), Montufar (2017) and Raghu et al. (2017) by refining the upper and lower bounds on the number of linear regions for rectified and maxout networks. In addition to achieving tighter bounds, we also develop a novel method to perform exact enumeration or counting of the number of linear regions with a mixed-integer linear formulation that maps the input space to output. We use this new capability to visualize how the number of linear regions change while training DNNs.

Keywords: deep learning, linear regions, piecewise-linear activations, mixed-integer linear programming, solution couting

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Applications -- Science and Engineering (Statistics )


Download: [PDF]

Entry Submitted: 01/08/2018
Entry Accepted: 01/09/2018
Entry Last Modified: 01/08/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society