Mosaic

This is a tool to learn Piecewise Affine Models (piecewise linear function) from Input-Output Data. Given a set of input-output data points, it constructs a function that closely approximates all data points. It ensures that the error on each point is bounded by a given error bound δ. Technical details of the tool can be found in the following paper.

R. Alur, N. Singhania, Precise Piecewise Affine Models from Input-Output Data, EMSOFT 2014. [PDF]

Consider the data set shown in the figure below.

Here, each input point on the grid is labelled by the corresponding output value. For example (10, 10) maps to 25. A possible piecewise affine model for this data is as follows:

Mosaic automatically constructs similar models from input-output data. Like a mosaic, it first fits some linear pieces (affine functions) on the data points. Then it uses convex polygon pieces (conjuction of affine inequalities) to construct the input partition of each linear piece. The mosaic letter M shown on the top in the background of this webpage has been constructed using such convex shapes by this tool. Note that the letter M is not a convex shape and similarly, the input partition for each linear piece need not be convex.

Mosaic has been implemented in MATLAB. Code for this tool and Benchmarks used to evaluate it can be found here.

Page updated

Google Sites

Report abuse