Code covered by the BSD License  

Highlights from
Table Breakpoint Optimization

image thumbnail

Table Breakpoint Optimization

by

 

04 Apr 2012 (Updated )

A set of tools for finding the best way to reduce the size of a table.

find_best_table_demo.m
%% Table Optimization Demo
%
% This script demonstrates how to use |find_best_table_1d| and 
% |find_best_table_1de| functions as well as their 2-D and n-D equivalanets
% to best reduce the size of a table to a given number of break points or
% to the smallest table possible for an allowable amount of error. This
% script focuses on how to use the included functions, but there's a
% graphical user interface to the 1-D and 2-D functions as well, which can
% be launched by executing |TableOptimizerGui|.
%
% This builds off of work by Richard Willey, Stuart Kozola, Eric Johnson, 
% Sarah Zaranek, and Peter Maloney at The MathWorks, Inc.
%
%  Requires the Optimization Toolbox (TM).
%  Supports the Parallel Computing Toolbox (TM).
%
%  Tucker McClure @ The MathWorks
%  Copyright 2013 The MathWorks, Inc.

%% Initialize

clc;

%% 1D Data Tables: Specifying Number of Allowable Points
% A simple example in 1 dimension.

% Create our 'big' data table and show it.
x = 0:0.1:10;
z = 1./(x/100 + 0.01) + x.^2 - 0.1 * x.^3;

figure();
plot(x, z);
title('Original Table');
xlabel('Independent Variable');
ylabel('Dependent Variable');
 
%%
% Find the best way to reduce the table to only 6 breakpoints (in other
% words, find where the 6 breakpoints go to reduce the fit error). First,
% we'll fit using linear interpolation.
[x_f_l, z_f_l, mse_l] = find_best_table_1d(x, z, 6, 'linear');

% Show the original and result.
plot(x,     z,                       ...
     x_f_l, z_f_l);
legend('Original', 'Best Linear Fit Table');
xlabel('Independent Variable');
ylabel('Dependent Variable');

%%
% Next, we'll fit using a spline.
[x_f_s, z_f_s, mse_s] = find_best_table_1d(x, z, 6, 'spline');

% Show the original and result.
plot(x,     z,                       ...
     x_f_l, z_f_l,                   ...
     x,     spline(x_f_s, z_f_s, x));
legend('Original', 'Best Linear Fit Table', 'Best Spline Fit Table');
xlabel('Independent Variable');
ylabel('Dependent Variable');

%% 1D Data Tables: Specifying Maximum Mean Squared Error
% Instead of specifying the target table size, we'll specify a maximum
% allowable amount of mean-squared error. We'll try both linear and spline
% types.

% We want a maximum mean squared error of 0.1.
mse_target = 0.1;
[x_f_le, z_f_le, mse_le] = find_best_table_1de(x, z, mse_target, 'linear');
[x_f_se, z_f_se, mse_se] = find_best_table_1de(x, z, mse_target, 'spline');

% Report results.
fprintf(['Achieved MSE of < %f with %d points using linear interp ' ...
         '(MSE: %f).\n'], ...
        mse_target, length(x_f_le), mse_le);
fprintf(['Achieved MSE of < %f with %d points using cubic interp. ' ...
         '(MSE: %f).\n'], ...
        mse_target, length(x_f_se), mse_se);
    
% Show the original and result.
figure();
plot(x,      z,                       ...
     x_f_le, z_f_le,                  ...
     x,      spline(x_f_se, z_f_se, x));
legend('Original', ...
       'Best Linear Fit for Allowable MSE', ...
       'Best Spline Fit for Allowable MSE');
xlabel('Independent Variable');
ylabel('Dependent Variable');

%% 1D Data Tables: Specifying Maximum Error

% We want a maximum mean squared error of 0.1.
mse_target = inf;
max_error  = 1;
[x_f_me, z_f_me, mse_me] = find_best_table_1de(x, z, ...
                                               mse_target, max_error);

% Show the original and result.
figure();
plot(x,      z,                       ...
     x_f_me, z_f_me,                  ...
     x,      spline(x_f_me, z_f_me, x));
legend('Original', ...
       'Best Spline Fit for Maximum Allowable Error');
xlabel('Independent Variable');
ylabel('Dependent Variable');

%% 2D Data Tables: Initial Table
% Now let's look at a 2-D lookup table.

% Create independent variables.
x_0 = -3:0.1:3;
y_0 = -4:0.2:4;

% Turn them into meshes.
[x_0_mesh, y_0_mesh] = meshgrid(x_0, y_0);

% Just use 'peaks' as our table to optimize.
z_0 = peaks(x_0_mesh, y_0_mesh);

% Show it.
figure();
surf(x_0, y_0, z_0);
title('Original');

%% 2D Data Tables: Linear Fit
% Create an 8x9 fit with linear interpolation.

tic;
[x_f, y_f, z_f, mse] = find_best_table_2d(x_0, y_0, z_0, 8, 9, 'linear');
toc;

fprintf('Completed linear fit with MSE: %f\n', mse);

figure();
surf(x_f, y_f, z_f);
title('Linear Fit');

%% 2D Data Tables: Spline Fit
% Create an 8x8 fit with spline interpolation.

tic;
[x_f, y_f, z_f, mse] = find_best_table_2d(x_0, y_0, z_0, 8, 8, 'spline');
toc;

% Note that since we fit with a spline, we won't see the spline if we draw
% the raw points (we'll only see the points the spline made from). Let's
% show the spline and draw dots for the points.
figure();
[xfm, yfm] = meshgrid(x_f, y_f);
surf(x_0, y_0, interp2(xfm, yfm, z_f, x_0_mesh, y_0_mesh, 'spline'));
shading interp;
hold on;
plot3(xfm(:), yfm(:), z_f(:), 'k+', 'MarkerSize', 3);
hold off;
title('Spline Fit');

% Note that the MSE is actually evaluated differently, so this doesn't
% compare directly to the linear method above.
fprintf('Completed spline fit with MSE: %f\n', mse);

%% 2D Data Tables: Specifying Mean Squared Error
% Alternately, let's find the smallest table with less than a given mean
% squared error. We'll try both linear interpolation (the default) as well
% as spline. Note that this takes much longer, as it's running multiple
% optimizations to find a reasonable result.
mse_target = 0.05;
[x_f_le, y_f_le, z_f_le, mse_le] = find_best_table_2de(x_0, y_0, z_0, ...
                                                       mse_target);
[x_f_se, y_f_se, z_f_se, mse_se] = find_best_table_2de(x_0, y_0, z_0, ...
                                                       mse_target, ...
                                                       'spline');

figure();
surf(x_f_le, y_f_le, z_f_le);
title('Linear Fit');

figure();
[xfm, yfm] = meshgrid(x_f_se, y_f_se);
surf(x_0, y_0, interp2(xfm, yfm, z_f_se, x_0_mesh, y_0_mesh, 'spline'));
shading interp;
hold on;
plot3(xfm(:), yfm(:), z_f_se(:), 'k+', 'MarkerSize', 3);
hold off;

fprintf(['Achieved MSE of < %f with %dx%d points using linear interp ' ...
         '(MSE: %f).\n'], ...
        mse_target, length(x_f_le), length(y_f_le), mse_le);
fprintf(['Achieved MSE of < %f with %dx%d points using cubic interp ' ...
         '(MSE: %f).\n'], ...
        mse_target, length(x_f_se), length(y_f_se), mse_se);
    

%% 2D Data Tables: Specifying Maximum Error
% We can also specify a maximum error anywhere as opposed to a mean squared
% error.

% Specify target error characteristics.
mse_target = 0.05;
max_error = 1;

% Use linear interpolation and find the best table with less than the
% provided maximum error.
[x_f_lme, y_f_lme, z_f_lme, mse_lme, me_lme] = find_best_table_2de(...
                                                    x_0, y_0, z_0, ...
                                                    [], max_error);

% Show the linear table.
figure();
surf(x_f_lme, y_f_lme, z_f_lme);
title('Linear Fit');

% Print the results.
fprintf(['\nAchieved MSE of < %f and maximum error < %f\n' ...
         'with %dx%d points using linear interp ' ...
         '(MSE: %f, ME: %f).\n\n'], ...
        inf, max_error, length(x_f_lme), length(y_f_lme), ...
        mse_lme, me_lme);

%%
% Or we can specify both a maximum and mean-squared error.

% Use linear interpolation and find the best table with less than the
% provided maximum error *and* less than the provided mean-squared error.
[x_f_sme, y_f_sme, z_f_sme, mse_sme, me_sme] = find_best_table_2de(...
                                                    x_0, y_0, z_0,...
                                                    mse_target, ...
                                                    max_error, ...
                                                    'spline');

% Show the cubic table.
figure();
[xfm, yfm] = meshgrid(x_f_sme, y_f_sme);
surf(x_0, y_0, interp2(xfm, yfm, z_f_sme, x_0_mesh, y_0_mesh, 'spline'));
shading interp;
hold on;
plot3(xfm(:), yfm(:), z_f_sme(:), 'k+', 'MarkerSize', 3);
hold off;
title('Spline Fit');

fprintf(['\nAchieved MSE of < %f and maximum error < %f\n' ...
         'with %dx%d points using cubic interp ' ...
         '(MSE: %f, ME: %f).\n\n'], ...
        mse_target, max_error, length(x_f_sme), length(y_f_sme), ...
        mse_sme, me_sme);

%% n-D Data Tables: Linear Fit
% We'll use the n-dimension methods, but show a 2-D data set so that it's
% still easy to visualize. Note that for n-D methods, the grid format is
% expected to correspond to ndgrid instead of meshgrid. That is, z(2, 3)
% corresponds to x(2) and y(3) (whereas for meshgrid, z(2, 3) would be x(3)
% and y(2) for visual reasons).

% Create independent variables.
x_0 = -3:0.1:3;
y_0 = -4:0.2:4;

% Turn them into meshes.
[x_0_mesh, y_0_mesh] = ndgrid(x_0, y_0);

% Just use 'peaks' as our table to optimize.
z_0 = peaks(x_0_mesh, y_0_mesh);

tic;
[x_f, z_f, mse] = find_best_table_nd({x_0, y_0}, z_0, [9, 8]);
toc;

fprintf('Completed linear fit with MSE: %f\n', mse);

figure();
surf(x_f{1}, x_f{2}, z_f'); % surf expects meshgrid-like data, so transpose
title('Linear Fit');        % z_f (or we could swap x_f{1} and x_f{2} too).

%% n-D Data Tables: Specifying Maximum Error
% Specifying both mean-squared and maximum error yield good results here.

% Specify target error characteristics.
mse_target = 0.05;
max_error = 1;

% Find the table with less than the target MSE and max error using spline
% interpolation.
tic;
[x_f, z_f, mse, me] = find_best_table_nde({x_0, y_0}, z_0,...
                                          mse_target, ...
                                          max_error, ...
                                          'spline');
toc;

% Print out how we did.
fprintf(['\nAchieved MSE of < %f and maximum error < %f\n' ...
         'with '], mse_target, max_error);
fprintf('%dx', cellfun(@(x_f) length(x_f), x_f(1:end-1)));
fprintf('%d points using cubic interp (MSE: %f, ME: %f).\n\n', ...
        length(x_f{end}), mse, me);

% Show the result (interpolate since it's a spline).
figure();
[xfm, yfm] = ndgrid(x_f{1}, x_f{2});
z = interpn(x_f{1}, x_f{2}, z_f, x_0_mesh, y_0_mesh, 'spline');
surf(x_0, y_0, z');
shading interp;
hold on;
plot3(xfm(:), yfm(:), z_f(:), 'k+', 'MarkerSize', 3);
hold off;
title('Spline Fit');

%% n-D Data Tables: Linear fit
% Now we'll actually use 3-dimensional data, z = f(x, y, c). We'll create a
% linearly interpolated table of a specified size. Showing this is a bit
% trickier than showing 2-D tables, so we'll take advantage of color as our
% third dimension.

% Create independent variables.
x_0 = -3:0.1:3;
y_0 = -4:0.2:4;
c_0 = -5:1:5;

% Turn them into meshes. Again, note the use of ndgrid instead of meshgrid.
[x_0_mesh, y_0_mesh, c_0_mesh] = ndgrid(x_0, y_0, c_0);

% Create the dependent variable.
z_0 = x_0_mesh.^2 + 5*sin(2*y_0_mesh) + c_0_mesh;

% Show the result by drawing a bunch of surfaces with color.
figure();
for k = 1:size(z_0, 3)
    surf(x_0, y_0, z_0(:, :, k)', c_0_mesh(:, :, k)');
    hold on;
end
hold off;

% Fit a table of a given size.
tic;
[x_f, z_f, mse] = find_best_table_nd({x_0, y_0, c_0}, z_0, [5 20 3]);
toc;

% Print out how we did.
fprintf('\nComplete linear fit with ');
fprintf('%dx', cellfun(@(x_f) length(x_f), x_f(1:end-1)));
fprintf('%d points using cubic interp (MSE: %f, ME: %f).\n\n', ...
        length(x_f{end}), mse, me);

% Instead of drawing a volume, we'll draw a bunch of surfaces, one for each
% breakpoint along the third dimension.
figure();
for k = 1:size(z_f, 3)
    surf(x_f{1}, ...        % dimension 1
         x_f{2}, ...        % dimension 2
         z_f(:, :, k)', ... % using height for dimension 4
         x_f{3}(k) * ones(size(z_f(:, :, k)'))); % color for dimension 3
    hold on;
end
hold off;


%% n-D Data Tables: Spline Fit Specifying Maximum Error
% Finally, we'll take n-dimensional data and fit a table with at most the
% specified error using a spline.

% Specify the error.
max_error  = 0.5;
target_mse = 0.1;

tic;
[x_f, z_f, mse] = find_best_table_nde({x_0, y_0, c_0}, ...
                                      z_0, ...
                                      target_mse, ...
                                      max_error, ...
                                      'spline');
toc;

% Print out how we did.
fprintf(['\nAchieved MSE of < %f and maximum error < %f\n' ...
         'with '], mse_target, max_error);
fprintf('%dx', cellfun(@(x_f) length(x_f), x_f(1:end-1)));
fprintf('%d points using cubic interp (MSE: %f, ME: %f).\n\n', ...
        length(x_f{end}), mse, me);

% Create the 2D meshes for x and y.
[xfm, yfm] = ndgrid(x_f{1:2});

% Create the 3D mesh for color.
[~, ~, cfm] = ndgrid(x_f{1:3});

% For each breakpoint along dimension 3, draw one surface.
figure();
for k = 1:size(z_f, 3)
    
    % Since it's a spline, interpolate like we do in the spline examples
    % above.
    zfm  = interpn(xfm, yfm, z_f(:, :, k), ...
                   x_0_mesh(:, :, k), y_0_mesh(:, :, k), 'spline');
    cfmk  = interpn(xfm, yfm, cfm(:, :, k), ...
                    x_0_mesh(:, :, k), y_0_mesh(:, :, k), 'spline');
    surf(x_0, y_0, zfm', cfmk');
    shading interp;
    camlight right;
    lighting gouraud;
    hold on;
    zs = z_f(:, :, k);
    plot3(xfm(:), yfm(:), zs(:), 'k+', 'MarkerSize', 3);
    
end
hold off;
colorbar;

%%
% Note that |find_best_table_nd| and |find_best_table_nde| are actually
% faster than their 1-D and 2-D counterparts. Those counterparts are kept
% for backwards compatibility.

%% Graphical User Interface
% Alternately, instead of using the command line functions, one could use
% the graphical user interface (for 1D and 2D data) to explore all of these
% options.
% 
% >> TableOptimizerGui;
%
% <<TableOptimizerGuiScreenShot.png>>

Contact us