Towards Exploratory Landscape Analysis forLarge-scale Optimization:
A Dimensionality Reduction Framework

Ryoji Tanabe
Yokohama National University
Yokohama, JapanIntroduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Exploratory Landscape Analysis (ELA) [Mersmann 11]
ELA provides a set of numerical features F based on a sample X• The features are used to characterize a fitness landscape of ablack-box optimization problem by machine learning• Applications of the ELA approach include:• high-level property classification, algorithm selection, performance
prediction, per-instance algorithm configuration, etc.

• For details of ELA• Session: GECH4+IMPACT (from 13:20)• “(A Brief Look at) The Evolution of Exploratory LandscapeAnalysis” by Pascal Kerschke and Mike Preuss• The R-package flacco [Kerschke 19] is used to compute features• https://github.com/kerschke/flacco• https://github.com/Reiyan/pflacco (Python interface)2 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

The R-package flacco [Kerschke 19]: Feature computation software
flacco provides 17 feature classes (343 features in total)• This work excludes the 3 classes that require additional fevals• This presentation excludes the 5 cell mapping classes
9 feature classes used in this presentation (107 features in total)
Feature className

ela level [Mersmann 11]
ela meta [Mersmann 11]
ela distr [Mersmann 11]
nbc [Kerschke 15]
disp [Kerschke 15]
ic [Munoz 15]
basic [Kerschke 19]
limo [Kerschke 19]
pca [Kerschke 19]

levelsetmeta-model
y-distribution
nearest better clustering (NBC)dispersion
information content
basic
linear model
principal component analysis

Num. features201157187151410• Each feature class consists of more than one feature• ela level and ela meta are effective feature classes
3 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Two contributions of this work
1. Revealing computational cost issue in ELA• Most previous studies focused on moderate-dim. problems (n ≤ 20)• The scalability of the ELA approach has been overlooked• Our results reveal that ela level and ela meta cannot be applied
to large-scale optimization due to their high computational cost2. Proposing a dimensionality reduction framework• It can speed up the computation of the two feature classes

4 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

First experiment: Investigating the feature computation time
• Research questions:• How does the feature computation time scale w.r.t. dimensions?
• Are the 9 feature classes available for large-scale optimization?

• The 24 BBOB functions in COCO [Hansen 21]• For n ∈ {2, 3, 5, 10}: The noiseless BBOB function set [Hansen 09]• For n ∈ {20, 40, 80, 160, 320, 640}: Its large-scale version [Varelas 20]• But, this first experiment used only the first instance of f1 (Sphere)• The (not improved) Latin hypercube sampling method• Sample size |X | = 50 × dimension n as in most previous studies• Time to make X and calculate f (X ) are not considered• Other settings• This work used the Python interface of flacco (pflacco)• A workstation with a 40-Core Xeon 2.1GHz and 384GB RAM• Ubuntu 18.04, Python 3.8, R 3.6.

5 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Average computation time (sec) on the first instance of f1 over 31 runs
• The computation time of all the 9 feature classes (except forela distr) increases exponentially w.r.t. dimension n• The computation of ela meta and ela level are time-consuming• For n = 160, they took approximately 1.1 hours and 1.5 hours, res.
• For n ≥ 320, they did not finish within 3 days

2351020

40

80

160
640
320

6 / 15Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Q. Why is the computation of ela level and ela meta time-consuming?
A. Because they use machine learning techniques• X is a set of solutions, and f (X ) is a set of their objective values• ela level repeatedly applies three classifiers to D = {X , f (X )}• The ela level features are the mean classification errors ofclassifiers over a 10-fold cross-validation• ela meta fits linear and quadratic regression models to D
• The ela meta features are the model-fitting results

When both |X | and the dimension are large, ela level andela meta are computationally expensive• When only either of |X | and the dimension is large, ela level andela meta are still computationally cheap• It is possible to reduce their computation time by setting |X | to 100• But, |X | should be large for large dimensions to obtain effective fea.
• Recall that |X | increases linearly w.r.t. dimension n (|X | = 50 ×n)
7 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Proposed: A dimensionality reduction framework
Goal: computing ela level and ela meta in a practical time
• ela level and ela meta are important feature classes in ELA• It is worth making them available for large-scale optimization
It is inspired by dimensionality reduction strategies in Bayesian opt.
• E.g., GPEME [Liu 14], REMBO [Wang 16], PCA-BO [Raponi 20]• reduce the original dimension n to a lower dim. m (m < n)• fit the Gaussian process model in the reduced m-dimensional space• can reduce the computation time for large-scale optimization
Is it possible to reduce the computation time ofela level and ela meta in the same way?

8 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Proposed: A dimensionality reduction framework
Simple two-step procedure to compute features
1. Apply a dimensionality reduction method to X to obtain X̂
• We used the weighting strategy-based PCA approach [Raponi 20]• It efficiently utilizes the information about the objective values f (X )• A solution x ∈ Rn is mapped to a point x̂ ∈ Rm
• Let X̂ be a set of m-dimensional points

2. Compute features based on X̂ and f (X ), instead of X and f (X )• When m is small enough, it is expected that the computation ofela level and ela meta can be fast
• The proposed framework does not require additional fevals

9 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Second experiment: Investigating the computation time of the proposed fr.
• Research question• Can the proposed framework reduce the computation time ofela level and ela meta for large dimensions?

• The same experimental setting as in the first experiment (recall p.5)
• The reduced dimension m in the proposed framework• m was set to 2
• Its performance is not sensitive to m unless m ∈ {2, ..., 5}

10 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Average computation time (sec) on the first instance of f1 over 31 runs
Computation time of d ela meta and d ela level is acceptable• n = 320: the computation of ela level didn’t finish within 3 days
• That of d ela level requires only approx. 5 minutes
23510204080

160640320

Features computed by the proposed
Dimensionality reduction framework
11 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Third experiment: Evaluating the effectiveness of features for predicting thehigh-level properties of the 24 large-scale BBOB functions [Varelas 20]• Research question:• Are the two feature classes computed by the proposed framework(d ela meta and d ela level) effective for property classification?

• 7 high-level property classification of the 24 BBOB fun. [Mersmann 11]• (1) multimodality, (2) global structure, (3) separability, (4) variable scaling,(5) search space homogeneity, (6) basin sizes, (7) glo. to loc. opt. contrast• For each function, the degree of a property was labeled by experts• E.g., (1) multimodality: “none”, “low”, “medium”, and “high”• While that of f1 (Sphere) is “none”, that of f3 (Rastrigin) is “high”• Task: Predicting the degree of a property of an unseen problem• E.g., What is the degree of multimodality of f2 (Ellipsoidal func.)?

• Leave-one-problem-out cross-validation (a 24-fold cross-validation)• In the i-th fold, fi is used for test, {f1 , ..., f24 } \ fi are used for train.
• 15 instances were used for each f• The performance of a classifier is evaluated based on the mean accur.

• Classifier: Random forest [Breiman 01]• The scikit-learn implementation
12 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Three feature sets: C7, C7-E2, and C7-D2

NameFeature classes

N. features

C7{ela distr, basic, ic, disp, nbc, pca, limo}

76

C7-E2

C7 ∪ {ela level, ela meta}

107

C7-D2

C7 ∪ {d ela level, d ela meta}107• C7: a set of the 7 computationally Cheap feature classes• C7-E2: C7 with the 2 computationally Expensive feature classes• C7-E2 is available only for n < 320• C7-D2: C7 with the Dimensionality reduction versions of the 2
computationally expensive feature classes• Feature selection was not performed

13 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Average accuracy of classifiers using C7, C7-E2, and C7-D2 (Multimodality)
Features computed by the propped framework are effective• C7-D2 is more effective than C7 for n ≥ 320• Similar results were observed for 5 properties (exc. separability )• C7-E2 is more effective than C7-D2 for n < 320• It would be better to use C7-E2 when it is available (i.e., n < 320)

2
3
5
10
20
40
80
160
320
640

C7C7-E2C7-D2

0.642
0.569
0.536
0.522
0.531
0.556
0.600
0.522
0.544
0.514

0.703
0.597
0.625
0.631
0.725
0.689
0.783
0.650
NaNaNa
0.578
0.622
0.647
0.639
0.617
0.622
0.561
0.578
0.583

14 / 15

Introduction

Exp1. Computational cost

Proposed method

Exp2. Computational cost

Exp3. Property prediction

Conclusion

Conclusion
Contribution 1. Revealing computational cost issue in ELA• Two important feature classes (ela level and ela meta) are notavailable for large-scale opt. due to their time-consuming process
Contribution 2. Proposing a dimensionality reduction framework• Our results on the BBOB functions with up to 640 dim. show:• the framework can speed up the computation of features classes• the effectiveness of features computed by the proposed framework

Sub-contributions not shown in this presentation• The framework can extend the cell mapping features to large dim.
• An analysis of the similarity between features and their d. r. versions
Future work
• Feature-based algorithm selection for large-scale optimization• Design of a new computationally cheap feature class
15 / 15