e-PAL (epsilon-Pareto Active Learning) is an algorithm designed to quickly predict the Pareto-optimal solutions in a multi-objective design space. This is particularly useful when measuring the target objectives is expensive, and therefore only a few samples of the design space should be drawn for measurement.
e-PAL predicts a Pareto front of the design space with the level of accuracy or granularity desired by the user. This granularity is specified with a vector parameter epsilon.
Assume that two objective functions are to be maximized simultaneously. The figure below shows an example of the true Pareto front of a design space contrasted with an epsilon-accurate Pareto front that could be predicted by e-PAL, with epsilon=(3,3).
As shown in the figure, certain amount of redundancy can be removed when epsilon is greater than zero.
The challenge of multi-objective design spaces is that rather than having a single optimal solution, several solutions may simultaneously optimize the target objective functions.
A concrete example in the domain of hardware design, are the design spaces generated by the Spiral DFT and sorting network hardware generators, when exploring the different settings provided by the tool. The user needs to choose between different candidate designs that perform the same task but that trade differently throughput and area. This challenge is aggravated by the fact that evaluating each design is extremely expensive, since complex synthesis processes must be executed. Thus, it is impractical and sometimes infeasible to evaluate every possible design in order to find the Pareto-optimal solutions that maximize throughput and minimize area at the same time.
e-PAL has several key features. Having drawn a few samples of the design space, it builds models using Gaussian processes to predict the objective functions for the rest of the space. Further, it uses the predictive uncertainty associated with these nonparametric models in order to guide the iterative sampling. Specifically, e-PAL's sampling strategy aims to maximize progress on designs that are likely to be Pareto-optimal. e-PAL iteratively discards points that are either redundant or suboptimal, and it terminates when no more points can be removed in order to guarantee that, with high probability, the remaining points define an epsilon-accurate Pareto set of the given design space.We have derived theoretical bounds on the number of iterations required by the algorithm to generate a prediction with the level of accuracy (epsilon) and confidence (delta) specified by the user.
e-PAL is an improved version of PAL. Unlike PAL, e-PAL returns an epsilon-accurate Pareto front of the given design space. In addition, e-PAL reduces the number of computations required in each iteration of the algorithm, making it more suitable for large design spaces.
In the y-axis, we show the accuracy of the Pareto front predicted when the algorithm has terminated. Accuracy is measured as the average maximum distance found between a point in the true pareto front and the closest point in the predicted Pareto front. The x-axis shows the number of designs that had to be evaluated in order to generate the prediction.
The results show that different accuracy/training-cost tradeoffs can be obtained by varying the value of epsilon. A larger epsilon causes e-PAL to stop earlier.
We compare the efficiency of e-PAL with those obtained with PAL and with the evolutionary algorithm ParEGO . These results show that e-PAL in almost all cases significantly improves over PAL and ParEGO.
More details on these experiments can be found in .
This implementation is written in Matlab, and uses the GPML libraries written by Carl Edward Rasmussen and Chris Williams . e-PAL can be used for any number of objective functions, however this implementation is limited to two objective functions.