Instance Space Analysis: A toolkit for the assessment of algorithmic power

Instance Space Analysis is a methodology for the assessment of the strengths and weaknesses of an algorithm, and an approach to objectively compare algorithmic power without bias introduced by restricted choice of test instances. At its core is the modelling of the relationship between structural properties of an instance and the performance of a group of algorithms. Instance Space Analysis allows the construction of footprints for each algorithm, defined as regions in the instance space where we statistically infer good performance. Other insights that can be gathered from Instance Space Analysis include:

• Objective metrics of each algorithm’s footprint across the instance space as a measure of algorithmic power;
• Explanation through visualisation of how instance features correlate with algorithm performance in various regions of the instance space;
• Visualisation of the distribution and diversity of existing benchmark and real-world instances;
• Assessment of the adequacy of the features used to characterise an instance;
• Partitioning of the instance space into recommended regions for automated algorithm selection;
• Distinguishing areas of the instance space where it may be useful to generate additional instances to gain further insights.

The unique advantage of visualizing algorithm performance in the instance space, rather than as a small set of summary statistics averaged across a selected collection of instances, is the nuanced analysis that becomes possible to explain strengths and weaknesses and examine interesting variations in performance that may be hidden by tables of summary statistics.

This repository provides a set of MATLAB tools to carry out a complete Instance Space Analysis in an automated pipeline. It is also the computational engine that powers the Melbourne Algorithm Test Instance Library with Data Analytics (MATILDA) web tools for online analysis. For further information on the Instance Space Analysis methodology can be found here.

If you follow the Instance Space Analysis methodology, please cite as follows:

K. Smith-Miles and M.A. Muñoz. Instance Space Analysis for Algorithm Testing: Methodology and Software Tools. ACM Comput. Surv. 55(12:255),1-31 DOI:10.1145/3572895, 2023.

Also, if you specifically use this code, please cite as follows:

M.A. Muñoz and K. Smith-Miles. Instance Space Analysis: A toolkit for the assessment of algorithmic power. andremun/InstanceSpace on Github. Zenodo, DOI:10.5281/zenodo.4484107, 2020.

Or if you specifically use MATILDA, please cite as follows:

K. Smith-Miles, M.A. Muñoz and Neelofar. Melbourne Algorithm Test Instance Library with Data Analytics (MATILDA). Available at (https://matilda.unimelb.edu.au). 2020.

DISCLAIMER: This repository contains research code. In occassions new features will be added or changes are made that may result in crashes. Although we have have made every effort to reduce bugs, this code has NO GUARANTIES. If you find issues, let us know ASAP through the contact methods described at the end of this document.

Installation Instructions

The main requirement for the software to run is to have MATLAB R2025a or later, with the Global Optimization, Parallel Computing, Optimization, and Statistics and Machine Learning toolboxes installed. The Communications and Financial toolboxes are not required (an earlier version used the Communications Toolbox's de2bi; it has since been replaced with a pure-MATLAB equivalent). LIBSVM support is deprecated: new runs always use MATLAB's native classifier registry (opts.pythia.classifier), so the LIBSVM MEX-files are only needed to load and migrate models saved by a pre-v1.7 version of the toolkit (see ISAmigrateModel).

Repository layout

InstanceSpace.m, buildIS.m, exploreIS.m   entry points (see below)
example.m, test_integration.m             getting-started / regression suite
startup.m                                 adds the folders below to the MATLAB path
core/                                     PRELIM, SIFTED, PILOT, PILOTviewpoint,
                                          CLOISTER, PYTHIA, TRACE, TRACE_legacy, FILTER
output/                                   scriptcsv, scriptpng, scriptweb, scriptfcn
utils/                                    ISAdefaults, ISAgetClassifierFcn,
                                          ISAmigrateModel, ISAsubsetData
deprecated/                               PYTHIA2, PYTHIAtest, SIFTED2 (warn-and-forward
                                          shims kept for backward compatibility)

InstanceSpace.m/buildIS.m/exploreIS.m add core/, output/, utils/, and deprecated/ to the MATLAB path automatically the first time any of them is used in a session — example.m, test_integration.m, and any script that starts with buildIS/exploreIS/InstanceSpace need no extra setup. If you want to call a function from one of those folders directly (PILOT, SIFTED, ...) without going through one of those three first, run startup.m (e.g. run('startup.m'), or just startup with the repo root as your current folder) at the start of your session.

Working with the code

Start with example.m: it runs the full pipeline (buildIS + exploreIS) once, on the bundled reference dataset, with sensible defaults and just a handful of commonly-adjusted settings (classifier, tuning strategy, projection dimensionality, feature selection on/off) exposed as plain variables near the top. Outputs — images (.png), tables (.csv), and raw intermediate data (.mat) — land in test/data/example/. To analyse your own data, point it at a folder containing your metadata.csv instead (see "The metadata file" below), and revisit the performance-metric settings, which are tuned for the bundled dataset's error-rate semantics.

test_integration.m is the exhaustive option-coverage regression suite used during development — every classifier, tuning strategy, 2D/3D, PLS, viewpoint groups, and more, each in its own subdirectory under test/data/ (e.g. test/data/classifier_svm/) so no run overwrites another's outputs. It's a good reference for how a given option is meant to be used, but not the place to start.

options.json is a generated artifact, not a source file, for both scripts above. Each run writes its own options.json from the opts struct built in MATLAB. Hand-editing an options.json file has no lasting effect — the next run silently overwrites it. To change what gets run, edit the MATLAB script instead (example.m directly, or for test_integration.m, the defaultOpts() local function for shared settings and a specific test case's override function for that case only).

The InstanceSpace class

buildIS/exploreIS are thin backward-compatibility wrappers (kept for callers like the MATILDA web platform that invoke them directly) around the InstanceSpace class, which is the recommended interface for new code:

obj = InstanceSpace(rootdir);              % reads options.json if present, else defaults
obj = obj.build();                          % run the full pipeline
obj = obj.explore(testRootDir);              % evaluate a trained model on new data
results = obj.getResults();                  % training results (== obj.model)
obj.save();                                  % write rootdir/model.mat
obj = InstanceSpace.load(rootdir);           % read it back

Options can be changed between individual pipeline stages, and only the stages that need to re-run do:

obj = InstanceSpace(rootdir);
obj = obj.build('stages', {'prelim', 'sifted', 'pilot'});
obj.opts.pilot.alpha = 2.0;                  % adjust after inspecting the projection
obj = obj.build('stages', {'pilot'});         % re-runs PILOT only; sifted output is reused
obj = obj.build('stages', {'cloister', 'pythia', 'trace'});

See the class's own help text (help InstanceSpace) for the full method list, including plot() and getResults(idx) for accessing a specific explore() call's results.

The metadata file

The metadata.csv file should contain a table where each row corresponds to a problem instance, and each column must strictly follow the naming convention mentioned below:

• instances instance identifier - We expect instance identifier to be of type "String". This column is mandatory.
• source instance source - This column is optional
• feature_name The keyword "feature_" concatenated with feature name. For instance, if feature name is "density", header name should be mentioned as "feature_density". If name consists of more than one word, each word should be separated by "_" (spaces are not allowed). There must be more than two features for the software to work. We expect the features to be of the type "Double".
• algo_name The keyword "algo_" concatenated with algorithm name. For instance, if algorithm name is "Greedy", column header should be "algo_greedy". If name consists of more than one word, each word should be separated by "_" (spaces are not allowed). You can add the performance of more than one algorithm in the same .csv. We expect the algorithm performance to be of the type "Double".

Moreover, empty cells, NaN or null values are allowed but not recommended. We expect you to handle missing values in your data before processing. You may use this file as reference.

Common data-preparation mistake: using NA instead of NaN, or leaving Excel error codes (#REF!, #NULL!, #DIV/0!) or empty rows in the sheet. Any of these cause readtable to infer a column as text (string/cell) instead of numeric (double), which will crash the pipeline downstream rather than failing with a clear error at load time.

Options

Every setting below is a field of the opts structure passed to buildIS (as options.json, built by example.m or test_integration.m). Broadly, there are settings required for the analysis itself, settings for the pre-processing of the data, and output settings. For the first these are divided into general, dimensionality reduction, bound estimation, algorithm selection and footprint construction settings. For the second, the toolkit has routines for bounding outliers, scale the data and select features.

General settings

• opts.general.seed master RNG seed (default 42). Governs every stochastic stage of the pipeline (PILOT's BFGS random starts, PYTHIA's Sobol/Bayes tuning, SIFTED's GA, etc.), so a run with the same seed and inputs is reproducible.
• opts.general.verbose turns on (TRUE, default) or off (FALSE) the detailed, stage-level console output (per-trial/per-iteration progress, hyperparameter results, projection matrix display). One-line stage start/complete messages are always printed regardless of this setting. opts.pilot.verbose and opts.pythia.verbose inherit this value by default and can be overridden independently if needed.
• opts.general.parallel determines whether parallel processing will be available (set as TRUE), or not (set as FALSE). The toolkit makes use of MATLAB's parpool functionality to create a multisession environment in the local machine.
• opts.general.ncores number of available cores for parallel processing.
• opts.perf.MaxPerf determines whether the algorithm performance values provided are efficiency measures that should be maximised (set as TRUE), or cost measures that should be minimised (set as FALSE).
• opts.perf.AbsPerf determines whether good performance is defined absolutely, e.g., misclassification error is lower than a 20%, (set as TRUE), or if it is defined relatively to the best performing algorithm, e.g., misclassification error is within at least 5% of the best algorithm, (set as FALSE).
• opts.perf.epsilon corresponds to the threshold used to calculate good performance. It must be of the type "Double".
• opts.perf.betaThreshold corresponds to the fraction of algorithms in the portfolio that must have good performance in the instance, for it to be considered an easy instance. It must be a value between 0 and 1.
• opts.selvars.feats / opts.selvars.algos optional cell arrays of feature/algorithm names to restrict the analysis to a hand-picked subset, matching the metadata.csv column headers with their feature_/algo_ prefix (e.g. {'feature_density', 'feature_diameter'}, not {'density', 'diameter'}). Omit either field to use all available features/algorithms.
• opts.selvars.smallscaleflag by setting this flag as TRUE, you can carry out a small scale experiment using a randomly selected fraction of the original data. This is useful if you have a large dataset with more than 1000 instances, and you want to explore the parameters of the model.
• opts.selvars.smallscale fraction taken from the original data on the small scale experiment.
• opts.selvars.fileidxflag by setting this flag as TRUE, you can carry out a small scale experiment. This time you must provide a .csv file that contains in one column the indices of the instances to be taken. This may be useful if you want to make a more controlled experiment than just randomly selecting instances.
• opts.selvars.fileidx name of the file containing the indexes of the instances.
• opts.selvars.densityflag by setting this flag as TRUE, instances are subset by feature-space density via FILTER instead of the small-scale/file-index options above: pairs of instances closer than opts.selvars.mindistance in feature space are treated as redundant, and one of each such pair is dropped, keeping a representative spread rather than a uniform random sample.
• opts.selvars.mindistance feature-space distance threshold below which two instances are considered too close (redundant) for the density-based filter.
• opts.selvars.type selects which extra condition, on top of feature-space closeness, FILTER requires before treating an instance as redundant and dropping it: 'Ftr' (feature-space closeness alone), 'Ftr&AP' (also requires similar algorithm performance), 'Ftr&Good' (default; also requires both instances to be uniformly good across the whole portfolio), or 'Ftr&AP&Good' (all of the above).

Dimensionality reduction settings

The toolkit uses PILOT as a dimensionality reduction method, with BFGS as numerical solver. Technical details about it can be found here.

• opts.pilot.analytic determines whether the analytic (set as TRUE) or the numerical (set as FALSE) solution to the dimensionality reduction problem should be used. We recommend to leave this setting as FALSE, due to the instability of the analytical solution due to possible poor-conditioning. Only applies when opts.pilot.method = 'standard'.
• opts.pilot.ntries number of iterations that the numerical solution is attempted.
• opts.pilot.dims projection dimensionality, 2 (default) or 3. Replaces the legacy boolean opts.pilot.ISA3D, which is still accepted as an alias (ISA3D = true maps to dims = 3). A 3D projection lets you additionally call PILOTviewpoint to find the best 2D camera angle(s) onto it (see below).
• opts.pilot.method selects the projection algorithm: 'standard' (default) is the BFGS/analytic method described above; 'pls' uses Partial Least Squares (plsregress) instead, which maximises covariance between the projection and the performance matrix and does not require the feature matrix to be full column rank. Both methods work at 2D or 3D via opts.pilot.dims.
• opts.pilot.alpha (default 1.0) scales the performance-reconstruction term of PILOT's cost function relative to the feature-reconstruction term, for opts.pilot.method = 'standard' only: min ||F̃-BrZ||² + α||Y-CrZ||². Increase it to emphasise performance trends over feature trends in the projection.
• opts.pilot.topoWeight (default 0, disabled) is reserved for future experimental use and has no effect in the current version.

When opts.pilot.dims = 3, buildIS automatically calls PILOTviewpoint(Z, Y, opts.pilot) to find the best 2D camera viewpoint(s) of the 3D projection, storing the result in model.pilot.viewpoint. By default one viewpoint is found across all algorithms; opts.pilot.viewGroups (a cell array of algorithm index vectors, e.g. {[1 2 3], [4 5 6]}) requests one viewpoint per group instead, useful for inspecting a subset of algorithms in isolation.

Empirical bound estimation settings.

The toolkit uses CLOISTER, an algorithm based on correlation to detect the empirical bounds of the Instance Space.

• opts.cloister.corrThreshold Determines the maximum Pearson correlation coefficient that would indicate non-correlated variables. The lower this value is, the more stringent is the algorithm; hence, it would be less likely to produce a good bound.
• opts.cloister.pval Determines the p-value of the Pearson correlation coefficient that indicates no correlation.
• opts.cloister.maxFeatures (default 20) guard on the number of features CLOISTER's correlation-based bit-matrix enumeration will process; above this count it would become intractable, so CLOISTER instead falls back to a plain convex hull of the projected instances as the boundary, with a warning.

Algorithm selection settings

The toolkit selects one binary classifier per algorithm (good/not-good performance) from a registry of MATLAB-native classifiers, resolved via ISAgetClassifierFcn. LIBSVM is deprecated for new runs: buildIS never dispatches to it. ISAmigrateModel (see below) only renames legacy field names on an old model (e.g. .svm/.knn → .classifiers) — it does not retrain anything. A migrated model whose classifiers are still legacy LIBSVM structs can still be evaluated through exploreIS/PYTHIA eval mode (which dispatches to svmpredict when it detects a struct instead of a MATLAB classifier object), but this requires the LIBSVM MEX-files to be present; retrain from scratch with buildIS if you want to drop that dependency entirely.

• opts.pythia.classifier selects the classifier: 'knn' (default, via fitcknn), 'svm' (fitcsvm), 'tree' (fitctree), 'nb' (Naive Bayes, fitcnb), 'linear' (fitclinear), or 'ensemble' (fitcensemble; see opts.pythia.ensembleMethod, default 'Bag'). All algorithms in the portfolio use the same classifier.
• opts.pythia.tuning selects the hyperparameter search strategy: 'sobol' (default; a scrambled Sobol quasi-random sequence, opts.pythia.nTuningIter evaluations with k-fold CV), 'bayes' (MATLAB bayesopt, Gaussian-process surrogate, same evaluation budget and CV), or 'none' (use opts.pythia.params directly, skipping tuning).
• opts.pythia.nTuningIter number of Sobol/Bayes evaluations (default 20).
• opts.pythia.kFold number of folds of the CV experiment.
• opts.pythia.params pre-calculated hyperparameters; required when opts.pythia.tuning = 'none', and always takes precedence over tuning when supplied. Shape depends on opts.pythia.classifier: [nalgos x 1] for the single-parameter classifiers ('tree', 'nb', 'linear'), or [nalgos x 2] for the two-parameter ones ('knn', 'svm', 'ensemble').
• opts.pythia.skip bypasses classifier training entirely (TRACE then falls back to the true labels directly, with a warning).
• opts.pythia.ispolykrnl (SVM only) determines whether to use a polynomial (set as TRUE) or Gaussian (set as FALSE) kernel. Usually, the latter one is significantly faster to calculate and more accurate; however, it also has the disadvantage of producing discontinuous areas of good performance which may look overfitted. We tend to recommend a polynomial kernel if the dataset is higher than 1000 instances.
• opts.pythia.useweights determines whether weighted (set as TRUE) or unweighted (set as FALSE) classification is performed. The weights are calculated as .
• opts.pythia.seed RNG seed for classifier training/tuning; defaults to opts.general.seed and rarely needs to be set independently.
• opts.pythia.verbose per-classifier training progress and tuning output; defaults to opts.general.verbose.

Removed options (no longer read by the toolkit; kept here only so old options.json/example.m files can be understood): opts.pythia.uselibsvm and opts.pythia.useknn — superseded by opts.pythia.classifier. Existing model.mat files using the old fields can be updated with ISAmigrateModel.

Footprint construction settings

The toolkit uses TRACE3, an algorithm based on MATLAB's alphaShape to define the regions in the space where we statistically infer good algorithm performance, applicable to both 2D and 3D instance spaces. TRACE3 always reuses PYTHIA's predicted labels for the good-performance region (Zu = {z_i : yhat_i=1 AND ybin_i=1}) rather than retraining its own classifier — this coupling is unconditional and not configurable. When opts.pythia.skip = true, TRACE falls back to the true labels only (Zu = {z_i : ybin_i=1}), with a warning.

• opts.trace.method selects 'trace3' (default, above) or 'legacy' (the pre-refactor DBSCAN + alpha-shape triangulation method, 2D only).
• opts.trace.PI minimum purity required for a section of a footprint.
• opts.trace.minInstances (default 4) minimum number of instances a candidate footprint must contain to be considered valid.
• opts.trace.minAreaFrac (default 0.01) minimum footprint size, as a fraction of the total instance-space area/volume, for a candidate footprint to be kept.
• opts.trace.contra ('legacy' method only, defaults to TRUE there) turns on contradiction removal — trimming overlapping sections of two algorithms' footprints where the evidence is weak. Not read by the default 'trace3' method.

Removed option: opts.trace.usesim — the PYTHIA/TRACE coupling described above is now unconditional, so there is no "simulated vs. actual data" switch to configure.

Automatic data bounding and scaling

The toolkit implements simple routines to bound outliers and scale the data. These routines are by no means perfect, and users should pre-process their data independently if preferred. However, the automatic bounding and scaling routines should give some idea of the kind of results may be achieved. In general, we recommend that the data is transformed to become close to normally distributed due to the linear nature of PILOT's optimal projection algorithm.

• opts.auto.preproc turns on (set as TRUE) the automatic pre-processing.
• opts.bound.flag turns on (set as TRUE) data bounding. This sub-routine calculates the median and the interquartile range (IQR) of each feature and performance measure, and bounds the data to the median plus or minus opts.prelim.iqrMultiplier (default 5) times the IQR. Warning: this sub-routine often has issues with features that have low value diversity (e.g. most instances share the exact same value), since the IQR can collapse to zero. Consider either removing such features or setting opts.bound.flag = false.
• opts.norm.flag turns on (set as TRUE) scalling. This sub-routine scales into a positive range each feature and performance measure. Then it calculates a box-cox transformation to stabilise the variance, and a Z-transformation to standarise the data. The result are features and performance measures that are close to normally distributed.
• opts.prelim.nanThreshold (default 0.20) maximum fraction of missing (NaN) values allowed for a feature before it is dropped entirely.

Automatic feature selection

The toolkit implements SIFTED (SIFTED.m; SIFTED2 is a deprecated alias kept for backward compatibility), a routine to select features, given their cross-correlation and correlation to performance. Ideally, we want the smallest number of orthogonal and predictive features. This routine is by no means perfect, and users should pre-process their data independently if preferred. In general, we recommend using no more than 10 features as input to PILOT's optimal projection algorithm, due to the numerical nature of its solution and issues in identifying meaningful linear trends.

• opts.sifted.flag turns on (set as TRUE) the automatic feature selection. SIFTED runs in two stages:
  1. Correlation filter. SIFTED calculates the Pearson correlation coefficient between each feature and each algorithm's performance, keeping the single most-correlated feature for every algorithm unconditionally, plus any other feature whose absolute correlation with any algorithm exceeds opts.sifted.rho at significance opts.sifted.pval. If 3 or fewer features remain at this point (or arrive with 3 or fewer to begin with), SIFTED stops here.
  2. Correlation clustering + GA. The Pearson correlation coefficient is used as a dissimilarity metric between the surviving features, and k-means clustering (opts.sifted.K clusters, opts.sifted.MaxIter/opts.sifted.Replicates controlling convergence) groups similar features together. A Genetic Algorithm then searches for the best one-feature-per-cluster combination: each candidate combination is scored by projecting it with PILOT's analytic branch (a single closed-form solve, no restarts needed) at the same dimensionality as the outer pipeline's opts.pilot.dims, then taking the worst-case (maximum) k-fold cross-validated KNN classification loss across all algorithms — lower is better. Previously-evaluated combinations are cached for the duration of the call. This stage is skipped if 3 or fewer features survive the correlation filter, or if there are no more features than opts.sifted.K.
• opts.sifted.rho correlation threshold indicating the lowest acceptable absolute correlation between a feature and performance. It should be a value between 0 and 1.
• opts.sifted.pval significance level for the correlation filter; a feature/algorithm correlation is only counted if its p-value is at or below this threshold.
• opts.sifted.K number of clusters which corresponds to the final number of features returned. The routine assumes at least 3 clusters and no more than the number of features. Ideally it should not be a value larger than 10.
• opts.sifted.MaxIter number of iterations used to converge the k-means algorithm. Usually, this setting does not need tuning.
• opts.sifted.Replicates number of repeats carried out of the k-means algorithm. Usually, this setting does not need tuning.

Removed option: opts.sifted.NTREES — a leftover from an earlier, since-replaced Random-Forest-based feature-cluster scoring step; the current GA+KNN fitness function (above) doesn't use it.

Output settings

These settings result in more information being stored in files or presented in the console output.

• opts.outputs.csv This flag produces the output CSV files for post-processing and analysis. It is recommended to leave this setting as TRUE.
• opts.outputs.png This flag produces the output figures files for post-processing and analysis. It is recommended to leave this setting as TRUE.
• opts.outputs.web This flag produces the output files employed to draw the figures in MATILDA's web tools (click here to open an account). It is recommended to leave this setting as FALSE.

Contact

If you have any suggestions or ideas (e.g. for new features), or if you encounter any problems while running the code, please use the issue tracker or contact us through the MATILDA's Queries and Feedback page.

Acknowledgements

Funding for the development of this code was provided by the Australian Research Council through the Australian Laureate Fellowship FL140100012.