Piecewise Linear Regression in Multiple Dimensions: Neural Networks vs. Mathematical Optimization
Abstract: This seminar explores the problem of piecewise linear (PWL) regression in general dimensions and introduces the novel and useful concept of “well-behaved PWL interpolation.”
Imagine you have a data set of N points representing an output variable z based on a d-dimensional input variable x. You want to identify a relationship between x and z using PWL regression. Ideally, you want to identify the “best” PWL function, i.e., with the minimum approximation error and a minimal number of linear pieces. What tool can you use to achieve this?
The first tool you can use is a ReLU neural network (NN) and the PWL function can be identified by training a NN with d input neurons, 1-output neurons and one or more hidden layers. Such NN is nowadays easy to implement (PyTorch, TensorFlow) and fast to train. However, the identified PWL function is generally not the best: locally minimal approximation error and an unnecessary large number of linear pieces.
The second tool is a mixed integer linear programming (MILP) formulation. This problem is harder to solve, especially in high dimension with large data sets. However, some clever tightening strategies can significantly accelerate the solution time, especially when considering the novel class of “well-behaved” PWL interpolation. The strength of the MILP approach is the identification of a true optimal PWL fitting composed a controlled or minimal number of linear pieces.
See all upcoming talks at: https://www.anl.gov/mcs/lans-seminars.