# INTEGRATION OF EVOLUTIONARY AUTOMATED MACHINE LEARNING WITH STRUCTURAL
SENSITIVITY ANALYSIS FOR COMPOSITE PIPELINES

Nikolay O. Nikitin1 Maiia Pinchuk1 Valerii Pokrovskii1 Peter Shevchenko1
Andrey Getmanov1 Yaroslav Aksenkin1 Ilia Revin1 Andrey Stebenkov1 Ekaterina
Poslavskaya2 Anna V. Kalyuzhnaya1
1ITMO University  Saint Petersburg  Russia
2Huawei Technologies Co  Ltd
e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
##  1 Abstract

Automated machine learning (AutoML) systems propose an end-to-end solution to
a given machine learning problem, creating either fixed or flexible pipelines.
Fixed pipelines are task independent constructs: their general composition
remains the same, regardless of the data. In contrast, the structure of
flexible pipelines varies depending on the input, making them finely tailored
to individual tasks. However, flexible pipelines can be structurally
overcomplicated and have poor explainability. We propose the EVOSA approach
that compensates for the negative points of flexible pipelines by
incorporating a sensitivity analysis which increases the robustness and
interpretability of the flexible solutions. EVOSA quantitatively estimates
positive and negative impact of an edge or a node on a pipeline graph, and
feeds this information to the evolutionary AutoML optimizer. The correctness
and efficiency of EVOSA was validated in tabular, multimodal and computer
vision tasks, suggesting generalizability of the proposed approach across
domains.

##  2 Introduction

AutoML is a promising direction of research for democratization of data
science across fields. However, greater predictive performance is often
associated with a decreased stability and interpretability of the pipelines
[32]. Explainability and transparency of a solution are both critical for
AutoML democratization and its wider use in real world tasks. Therefore,
AutoML should prioritize not only the predictive power, but also the
simplicity of a pipeline during its construction. Structural sensitivity
analysis (SA) is a promising instrument for such pipeline optimization.

In prior research, SA was used to assess how the uncertainty in the input data
or in parts of a system affected the system as a whole [23]. We consider an
AutoML pipeline as a graph, therefore, the scope of SA in our study is to
quantitatively estimate the positive or the negative effect of an edge or a
node in a pipeline graph. Throughout the paper, we will consider pipelines as
directed computational graphs, consisting of preprocessing components and of
machine learning models arranged as a sequence of consecutively executed
stages, where the output of one component becomes input for the next.

This paper discusses the approaches for constructing pipelines with genetic
algorithms extended with the SA module, and compares the quality of the
proposed solution with other AutoML systems in terms of their robustness and
interpretability.

The module comprises two algorithms, performing the local and the global SA.
The former seeks to simplify the pipeline structure given a fixed metric
value. Thus, the local SA evaluates the contribution of each preprocessor or
model to the final metric, suggesting redundant pipeline components. The
global SA algorithm selects a more efficient pipeline structure based on
accumulated meta-knowledge. For example, it proposes operations that have
worked best in prior tasks.

We structured the paper as follows: Section III gives an overview of the
existing algorithms, Section V provides the description of the proposed EVOSA
module, Section VI covers the experimental setup and the benchmarking results,
Section VII summarizes the experimental findings and discusses future
improvements, Section VIII highlights the key fundamental and empirical points
of the paper.

##  3 Related work

This section analyses the historical and the state-of-the-art AutoML
solutions, focusing on the underlying algorithms of the pipeline construction.
We discuss only open-source frameworks and libraries, since the real
effectiveness and internal structure of proprietary AutoML solutions can not
be assessed directly.

###  3.1 Existing AutoML approaches

In this paper, we group the existing AutoML systems based on their pipeline
construction approach into solutions that create fixed (linear) pipelines or
flexible (variable-shaped) pipelines [24]. The former result in a standard
sequence of stages (preprocessors followed by estimators) invariable across
tasks. For example, we preprocess the data with a standard scaler for
continuous variables, and with one-hot encoding for categorical variables;
then we fit a range of models to the transformed dataset, and either select
the most accurate model, or orchestrate all trained models in an ensemble (via
stacking or simple averaging). In contrast, variable-shaped pipelines have
high structural variability depending on the dataset: they create linear or
tree-like structures individually tailored to a given task. For example, the
same dataset is preprocessed in several ways, applying feature selection,
feature generation, a variety of scaling or encoding schemes, these versions
are fed to the estimators, which may follow one another (the output of the
first estimator serves as an input for the second), often resulting in tree-
like structures with multi-level interconnections (see 2).

Some of the earliest attempts to develop AutoML with linear pipelines were
Auto-Weka [18, 37] and auto-sklearn [12], sharing the same Bayesian optimizer
to discover a perfect combination of feature preprocessors, ML models and
their hyperparameters to maximize the predictive performance on unseen data.
The fixed pipeline structure from auto-sklearn allows several data
preprocessing operators, one feature prepossessing operator, and a single
model. Additionally, in auto-sklearn 2.0 simple pipelines can be ensembled
together [11]. AutoWeka uses a similar approach to pipeline construction and
model ensembling, but with a wider range of base models and hyperparameter
configurations.

A more recent solution, creating a linear pipeline, and demonstrating state-
of-the-art performance is H2O AutoML[21]. Some H2O AutoML competitiveness can
probably be attributed to the high quality of their base models. Unlike many
other AutoML solutions, which rely on the existing open source libraries, H2O
developed high-performing versions of the well-known algorithms. For example,
XGBoost, Random Forest, Extremely Randomized Trees, and so on. It creates a
fixed pipeline for handling any dataset: the base estimators are fitted to the
data after they perform all the required preprocessing; these fitted
estimators can be ensembled together via stacking. The stacking algorithm
includes either all fitted base models, or a single copy of each model type.
Despite its simplicity, the resulting linear pipeline demonstrates a
competitive benchmark performance.

The first AutoML solution designing variable-shaped pipelines was TPOT [25],
which used multi-objective genetic programming, treating the parameter
configuration optimization as a search problem. ML operators in TPOT are
defined as genetic programming primitives. These primitives are combined into
a tree-based pipeline. Models come from the scikit-learn library [29] and
belong to one of three groups: supervised classification operators, feature
preprocessing operators, and feature selection operators. The optimization
starts with the generation of 100 random pipelines. Only the top 20 (based on
the cross-validation metric score and the pipeline size) are selected for the
next generation. During the optimization, TPOT creates multiple copies of a
dataset: each copy can be modified by the operators, these modified outputs
can be combined, can be followed by other operators, until they finally become
an input for the prediction primitive.

AutoGluon [10] is a more recent AutoML solution, creating variable-shaped
pipelines and demonstrating state-of-the-art performance. Their system
supports model orchestration in multi-layered stacking ensembles with multi-
layer skip-connections, which connect the output of one layer and the input of
another non-adjacent layer. The framework can automatically preprocess raw
data, identify the problem type (binary, multiclass classification, or
regression), partition data into folds for model training or validation, fit
base models, and create an optimized ensemble model that typically outperforms
any fitted base model. The algorithm fits base models in the following
predefined order: AutoGluon-Tabular Deep neural networks, LightGBM, CatBoost,
Random Forest, Extremely Randomized Trees, and K-nearest Neighbors. The
AutoGluon-Tabular AutoML was the first system introducing a multi-layer stack
ensemble with skip-connections: better generalization performance and reduced
overfitting are achieved by the internal k-fold cross-validation.

LightAutoML, or LAMA [39], extends the multi-layered pipeline approach
implemented in AutoGluon by adding presets, which the authors define as fixed
strategies for building dynamic pipelines. These are sequences of stages that
have demonstrated their effectiveness in prior tasks. LAMA enables a lot of
customization options: for example, the user can predifine pipelines that will
be incorporated in the AutoML assembler.

One of the most recent frameworks, FEDOT [24], prioritizes maximal variability
in candidate pipelines compared to alternative solutions. Similarly to TPOT,
FEDOT AutoML uses evolutionary optimization; however, its pipelines are
considered as directed acyclic graph-based structures, where nodes represent
data transformers and models, and edges indicate data flows. Additionally,
FEDOT can handle many data types (including, time series, text, and image
data) and problems (both classification, regression). FEDOT uses Pareto
optimization (using predictive quality and number of models as concurring
objectives) to limit the complexity of the resulting pipelines, which tend to
grow overly complex under the traditional evolutionary approach. However, this
does not completely resolve the problems of complicated pipelines, as well as
long convergence times for some datasets. The structure of a pipeline could be
simplified by incorporating a system component that gives quantitative cost-
benefit estimation for each node in a pipeline graph, such as the local SA
operator. The convergence time could be significantly decrease by using meta-
knowledge from prior tasks, regarding which operations tend to work best, such
as via the global SA component.

To summarize, we discussed two main groups of approaches to AutoML system
design. The first group tends to create fixed, linear pipelines that provide a
solid, general solution to any given task. The second group seeks individually
tailored solutions for given problems, resulting in dynamic, variable-shaped
pipelines. The downside of the second approach is a possible excessive
complexity and long convergence of AutoML systems. This is particularly
relevant for frameworks with evolutionary optimizers, such as TPOT and FEDOT.
The rest of the paper focuses on the effects of adding EVOSA to the novel
evolutionary AutoML framework FEDOT, where we expect to observe the greatest
gains from using both local and global SA. We predict that local SA will
increase the explainability and transparancy of the resulting pipelines, while
global SA will enhance the convergence times via meta-learning.

###  3.2 Explainability of AutoML

The term ’explainability’ covers different aspects of an AutoML solution: It
includes understanding the reasoning underlying the decisions of ML models
[8], as well as the choice of a specific pipeline by an AutoML framework [40].
For the purposes of this study, we will mostly focus on the pipeline
transparancy and explainability, because possible obscurity of model decision
criteria are not reserved to AutoML.

The transparency and explainability of pipeline design (so-called "white-box
AutoML" [5]) are important problems for integration of AutoML in production
workflows. The researches have proposed different approaches to justification
and clarification of the final pipeline selection [7]. For example, the
recently proposed PipelineProfiler provides an interactive analysis of
pipeline search across AutoML systems: Its matrices - where rows represent the
various pipelines listed from best to worst, and the columns indicate if the
respective pipeline component was used - allow identifying patterns in the
data that have been shown useful even for experts [27]. Alternative methods of
dimensionality reduction are particularly helpful for evolutionary approaches
to pipeline design [6].

In some papers, explainability and interpretability of AutoML are associated
with specific features useful for a data analyst [40], such as data
visualization, progress report, final model interpretation, feature
importance, and analysis exploration. The underlying idea is that "AutoML
should automate, not obfuscate" [40], that is, an analyst can check the
appropriateness of the proposed AutoML solution, while at the same time get a
higher-level perspective on the data.

However, the existing AutoML solutions have limited tools for visualization
and interpretation of the pipeline design process. It is particularly
important for the frameworks which create dynamic variable-shaped pipelines
(especially evolution-based, such as TPOT and FEDOT) that prioritize pipeline
customization for each task.

###  3.3 Meta-learning in AutoML

The other way to make AutoML more effective and understandable is meta-
learning, which consists in transferring knowledge from prior tasks to the
current problem during pipeline optimization.

The AutoML researchers have primarily attempted to achieve this by restricting
the search space (for pipelines, models, or hyperparameters) or by
prioritizing more successful setups during optimization. The restriction and
modification of a search space increases the convergence of an AutoML
solution. The search space reduction in AutoML is often based on human-guided
machine learning [4]; however, the search space can also be refined using
knowledge from prior tasks [2], and some patterns can be extracted in an
automated way [41]. For example, useful knowledge can come from previous
optimization runs: A pairwise correlation matrix for pipelines’ performance in
existing experiments identifies effective pipelines for unseen datasets [13].

A useful offline store of meta-knowledge can be significantly enhanced by the
accumulated public efforts. H2O Driverless
AI111https://h2o.ai/platform/h2o-driverless-ai-recipes uses the experience
gained by the community to solve common ML problems. The AutoML system
implements the efficient data handling strategies and assigns them higher
priority. This approach may assist the design of initial assumptions for
optimization; however, it requires manual curation of the knowledge database
and does not guarantee the efficient transfer of best practices from one
problem to another.

Auto-sklearn adopts a similar strategy, with an offline training phase on a
large pool of tasks. It fits a separate model that identifies datasets with
similar characteristics as the target dataset, and proposes successful
pipelines and hyperparameters to warm-start the Bayesian optimization [28].

###  3.4 Sensitivity analysis for modelling pipelines

In general, sensitivity analysis investigates the influence of uncertainty in
the input data or in parts of the system on the behaviour of a system as a
whole [23]. The various SA techniques are widely accepted in ML and AutoML
[33]. For example, SA algorithms are used to visualize and explore AutoML
pipelines [26] or decrease the optimization time by dropping unpromising
pipelines [14]. In their pipeline optimization capacity, the SA methods look
similar to meta-learning. Hence, it is useful to differentiate between the
global SA tools, which indeed constitute meta-learning methods, based on prior
(offline) experience, and the local SA tools, which optimize pipeline based on
evidence from an ongoing training session. The rest of the section will
discuss the existing local SA functionalities available in modern AutoML.

AutoGluon proposes an advanced ensemble model selection algorithm based on the
local SA information to maximize the final metric. Specifically, they use
model selection with replacement, sorted ensemble initialization, and bagged
ensemble selection. AutoGluon individually fits various models and combines
them into one ensemble that outperforms the individual trained models via
stacking/bagging [9]. This method is simple and transparent; on the downside,
it is computationally expensive [3] during training and inference.

TPOT modification, LTPOT aims to reduce the number of pipelines evaluated on
the entire dataset by the selection process so that only the most promising
pipelines must be evaluated on the full dataset. It is achieved by evaluating
pipelines on a small subset of the data: only pipelines exhibiting good
performance on the subset will be evaluated on the whole dataset [14].

LightAutoML uses the realization of Tree-structured Parzen estimation by the
Optuna framework for GBM models to compare the parameters fine-tuned during
the fitting process and expert hyperparameters. A mixed tuning strategy
provides models in the pipeline, which both are blended or stacked, or dropped
if it does not increase the final model performance.

The ideas of local and global SA already have a lot of application in AutoML
systems. Notably, incorporating both offline information (via meta-learning)
and online data (coming from the current training session) consistently
improve system performance despite the differences in configurations and
algorithms, underlying the local and the global SA in specific AutoML
frameworks. This paper explores the effects of both the local (online) and the
global (offline) SA knowledge on the pipeline optimization, estimating their
contribution to variable-structured pipelines.

##  4 Problem statement

AutoML is a computationally expensive optimization task, which is highly
affected by "the curse of dimensionality". The computational complexity
becomes particularly apparent with systems, creating variable-shaped
pipelines. The formulation of the optimization task for the design of custom
pipelines has the following symbolic representation:

$\begin{gathered}\boldsymbol{N_{opt}},\boldsymbol{E_{opt}}=\operatorname*{argmin}_{(N,E)\in\boldsymbol{S}}{F(P(\boldsymbol{N},\boldsymbol{E}),\boldsymbol{X},\boldsymbol{Y},T)},\\\
\boldsymbol{S}=R(\boldsymbol{S_{full}}),\end{gathered}$ (1)

where $P$ is a pipeline design function that accepts nodes $N$ and edges $E$;
$S\\_full$ is a combinatorial space that includes all correct combinations of
the nodes (models and data operations) and edges (data flows between nodes).

In practice, $S\\_full$ has a very high dimensionality and the computational
complexity of the objective function. The $S\\_full$ can be reduced to $S$
using meta-heuristic approaches (represented as function $R$). We can search
for the optima of $S$ with a variety of numerical optimization methods. The
AutoML tasks are usually considered under a specific timeout $T$. The short
timeout can cause the identification of a pipeline far from global optima.
However, excessively large timeout can lead to over-complicated pipeline as a
result.

The proper balance between the exploration- and exploitation-based behaviours
in AutoML pipeline design remains an open scientific problem [17]. First, we
wish to restrict the search space $S$ as much as possible; second, we seek an
effective optimization strategy that avoids expensive evaluations of over-
complicated pipelines; third, we wish to retain high predictive power, while
reducing the inference time on unseen data.

The SA methods help restrict the search space during optimization [22] and
estimate the importance of different pipeline blocks [1] or hyperparameters
[30] of specific models.

In this paper, we propose a controllable approach of evolutionary optimization
for ML pipelines that reduces the full combinatorial space
$\boldsymbol{S_{full}}$ to the reduced space $S$ (described in the Equation 2)
using the SA techniques.

$\begin{gathered}\boldsymbol{S}=R_{sa}(\boldsymbol{N_{opt}},\boldsymbol{E_{opt}}),\end{gathered}$
(2)

where $\boldsymbol{S}$ is a restricted search space, $R_{sa}$ is a function
that two proposed SA methods: global and local SA. $\boldsymbol{N_{opt}}$ and
$\boldsymbol{E_{opt}}$ can be obtained from final or intermediate solutions
for pipeline optimization.

The involvement of SA in pipeline design allows performing the following
operations: (1) estimating the importance of each block in a pipeline
(particularly useful for a data expert); (2) simplifying a pipeline while
controlling for its predictive power; (3) improving the AutoML convergence
time.

We formulate the following hypothesis for the performance of the SA:

Hypothesis The local SA allow improving the convergence of optimisation and
reduce the structural complexity of solutions without compromising the
predictive power of the final solution.

##  5 Proposed approach

The proposed Evolution with Sensitivity Analysis (EVOSA) approach is
implemented as a graph-based evolutionary optimizer for ML pipelines, which
comprises four modules, performing the following tasks: (1) evolutionary
design of pipelines; (2) local sensitivity analysis of a pipeline structure;
(3) global analysis of the evolution history for a set of prior tasks; (4)
interactive visualization of SA and evolution results.

To get the most of the SA approach, we required AutoML with evolutionary
optimization. Therefore, the component (1) in EVOSA was procured by the FEDOT
system [24]. Below we describe the components (2)-(4) and their integration
into AutoML.

The schematic overview of the approach is presented in Figure 1.

Figure 1: The scheme of proposed EVOSA approach.

###  5.1 Local SA component

We consider the pipeline structure as a graph, and the local SA component
quantitatively estimates the importance of each node, subgraph and edge. This
information is used to prioritize the replacement and deletion operations
during optimization (see Figure 2),

Figure 2: Details of the proposed local SA approach: a) example for each
variation of operation; (b) the proposed sequence of the pipeline analysis

The local SA can assist in multi-objective optimization - by taking into
account not only the prediction error, but also the structural complexity of
the pipeline, and the training time. For the purposes of this study, the
prediction error serves as a primary criterion, the structural complexity and
training time - as secondary criteria.

The SA component functions as mutation operators in the evolutionary optimizer
(see the integration scheme in Figure 3).

Figure 3: Integration of the local SA approach with evolution: SA is applied
on $N$ best individuals every $K$-th generation, which allows to improve
convergence and get simpler results without metric loss

In implemented SA algorithm all graph optimization operations (Node Deletion,
Node Replacement, Edge Deletion and Edge Replacement) are applied one after
another. For example, Node Deletion method is applied to all nodes, then the
Node Replacement method, and so on.

Node deletion and node replacement operations allow estimating the node’s
redundancy in a pipeline [1]. Each node’s sensitivity index is estimated as
follows:

$\begin{split}\boldsymbol{S}^{node\\_del}_{i}=1-\frac{Q(P(N,E))}{Q(P(N\smallsetminus\\{N_{i}\\},E^{\prime}))},\\\
\end{split}$ (3)

where $\boldsymbol{S}^{node\\_del}_{i}$ is sensitivity of a vertex during its
deletion, $Q$ is the quality measure for the pipeline $P$ formed by a set of
nodes $N$ and edges $E$, where $N_{i}$ is chosen for analysis and thus
excluded from the pipeline (value in denominator is quality measure after node
deletion). The remaining set of edges after the node removal is denoted as
$E^{\prime}$, since its adjacent edges are also removed.

For the node replacement operation, the following representation is used:

$\begin{split}\boldsymbol{S}^{node\\_rep}_{i}=1-\frac{Q(P(N,E))}{Q(P(N\smallsetminus\\{N_{i}\\}\cup\\{\tilde{N_{i}}\\}),E)},\\\
\end{split}$ (4)

where $N_{i}$ is replaced by new node $\tilde{N_{i}}$ obtained from search
space.

For the edge deletion and replacement, the equations are as follows:

$\begin{split}\boldsymbol{S}^{edge\\_del}_{i}=1-\frac{Q(P(N,E))}{Q(P(N,E\smallsetminus\\{E_{i}\\}))},\\\
\end{split}$ (5)

$\begin{split}\boldsymbol{S}^{edge\\_rep}_{i}=1-\frac{Q(P(N,E))}{Q(P(N,E\smallsetminus\\{E_{i}\\}\cup
E_{j})}\end{split}$ (6)

###  5.2 Global SA component

The global SA component enhances the performance and stability of the
evolutionary algorithms, using accumulated knowledge from previous tasks or
runs. In the paper, global SA refers to a specific version of meta-
optimization.

####  5.2.1 Appearance analysis

The structure of pipelines is a directed acyclic graph that can be divided
into simple sup-parts - a pair of nodes and an edge between them. The
algorithm uses prior history to estimate the importance of all edges in
pipelines. The history here is a collection of previous launches that contain
information about the pipeline structure and their metric on test samples -
fitness score. Based on this information, we can apply heuristics to decide on
the suitability of operations.

These heuristics increase the mutation efficiency by advising the most
suitable operations for a graph. The function is calculated for all pairs of
operations for that particular score. The score between operation $A$ and
operation $B$ ($A\rightarrow B$) is defined as

$F_{suit}=\overline{Rn_{A\rightarrow B}},$ (7)

where $\overline{Rn_{A\rightarrow B}}$ is a mean normalized rank of pipelines
with edge $A\rightarrow B$.

The normalized rank $Rn$ is the position of a pipeline compared to other
pipelines based on the fitness divided by the number of pipelines in a
history.

All values are registered in a table (see visualization in Figure 4). Value in
a cell can be interpreted as follows: how many times we get an increase in
performance if we set an operation from column X after the operation from row
Y.

The AutoML optimizer assigns weights for the operations based on their
’suitability scores’ during mutation, thus prioritizing more promising
combinations. The algorithm is applied to two types of mutations. The first
type changes operation in the node. The second type inserts a new node in the
graph (as a child, a parent, or an intermediate node). The proposed approach
changes only the algorithm for selecting an operation for a new or existing
node.

For the node change mutation, the algorithm randomly selects a node to mutate.
Next, it finds child and parent nodes for the target node. Finally, it selects
the best node based on the information about the child and the parent nodes
and the ’suitability values’ table.

In case of the addition mutation, the algorithm first randomly selects a place
for a node insertion. Second, it identifies new child and parent nodes. Third,
it selects the best node based on the information about the child and the
parent nodes, and the ’suitability values’ table.

The algorithm for selecting suitable nodes selects candidates for mutation and
calculates their scores based on the ’suitability values’ table. Each
candidate receives its score (weight).

The weight for the $i$-th candidate is calculated as a sum of the suitability
scores of the child and the parent nodes:

$W_{i}=\sum_{\text{i=1}}^{|\textbf{N{child}}|}F{ij}+\sum_{\text{j=1}}^{\textbf{|N{parent}|}}F{ij},$
(8)

where Nparent is a set of parent nodes, and the Nchild is a set of child
nodes, and $F{ij}$ is the suitability score for $i$-th candidate according to
$j$-th parent (child) node this candidate would get if it will be selected.

Candidates with scores below zero are dropped. The final node is selected
randomly according to the normalized weights. The pseudocode of the algorithm
is described in Alg. 1.

####  5.2.2 Meta-model

We implemented additional global SA algorithms to improve the results on
future runs. We denote $G_{i}=\\{(V_{i},E_{i})\\}$ as a graph, $V_{i}$ its
vertexes and $E_{i}$ its edges; we denote $F_{(i,d)}=F_{d}(G_{i})$ as a
fitness score for the graph $G_{i}$ on a dataset $d$ and $Rn_{(d,i)}$ as a
normalized rank of the graph $G_{i}$ on the dataset $d$. We represent each
graph in the table format. In the proposed approach, we used encoding of all
edges as a graph representation: if a graph has two edges "$(A,B)$", then in
the column "$(A,B)$" the row representation will have the value "2". Let us
denote $X$ as a table with representations for each graph and $Y$ as a table
with $Rn_{(d,i)}$ for each graph and dataset. The Cartesian product of $X$ and
$Y$ will be our train dataset. Ranks are the target values, and graph
representations are the features. We fit a model (in our case, a Random
Forest) to predict $Rn_{(d,i)}$ based on the graph representation.

We use the fitted model for optimization. On each mutation iteration, we get
several possible graphs (depending on which node we insert or replace). Now we
can calculate $Rn_{i}$ for each graph. This information can help us choose
more promising graphs. We randomly select the final graph from the best $N$
graphs based on the $Rn_{i}$. The pseudocode of the algorithm is described in
Alg. 2. The schema of the approach is presented in Figure 6.

Algorithm 1 Pseudocode of procedure for selecting node according to
suitability table

1:procedure ChooseNodeDirected

2: Input: $parent\\_nodes,child\\_nodes,candidates,$
$suitable\\_table$

3: Output: $name\\_of\\_operation$

4: $cand\leftarrow\textsc{SET}(candidates,suitable\\_table.columns)$

5: $child\leftarrow\textsc{SET}(child\\_nodes,\newline
suitable\\_table.columns)$

6: $parent\leftarrow\textsc{SET}(parent\\_nodes,\newline
suitable\\_table.columns)$

7: $scores\\_parent\leftarrow suitable\\_table[parent,cand]$

8: $scores\\_child\leftarrow suitable\\_table[cand,child]$

9: $scores\leftarrow\textsc{SUM}(scores\\_parent)+\newline
\textsc{SUM}(scores\\_child)$

10: $scores\leftarrow\textsc{DROP\\_BAD\\_CONNECTIONS}(scores)$

11: if $MAX(scores)<$ 0.1 then

12: return $\textsc{RAND}(cand)$

13: else

14: $weights\leftarrow scores/\textsc{SUM}(scores)$

15: return $\textsc{RAND}(cand,weights=weights)$

16: end if

17:end procedure

Algorithm 2 Pseudocode of procedure for metamodel mutation (general schema)

1:procedure MutationMetamodel

2: Input: $initial\\_graph,candidates,metamodel$

3: Output: $graph$

4: local variables

5: $op\\_scores$, empty dictionary with candidates values as keys

6: end local variables

7: for candidate in candidates do

8: $template\\_graph\leftarrow\textsc{MUTATE}(initial\\_graph)$

9: $op\\_scores[candidate]\leftarrow\textsc{COMPUTE\\_SCORE}(\newline
template\\_graph)$

10: end for

11: $final\\_choose\leftarrow\textsc{GET\\_RANDOM\\_FROM\\_TOP5}(\newline
op\\_scores)$

12: $new\\_graph\leftarrow\textsc{MUTATE}(initial\\_graph,\newline
final\\_choose)$

13: return $new\\_graph$

14:end procedure

Figure 4: Example of a table with suitability score

The schema of the approach is presented in Figure 5.

Figure 5: Workflow of the proposed approach to global SA (appearance analysis)
Figure 6: Workflow of the proposed approach to global SA (metamodel)

####  5.2.3 Criteria for analysis

The score between the operations $A$ and $B$ ($A\rightarrow B$) could be
defined as

$F_{suit}=\overline{Rn_{A\rightarrow B}}$

, where $\overline{Rn_{A\rightarrow B}}$ is the mean normalized rank of
pipelines with the edge $A\rightarrow B$.

The normalized rank $Rn$ is the pipeline place number in pipeline history,
sorted by fitness divided by the number of pipelines in history.

##  6 Experimental studies

###  6.1 Experimental setup

The experiments are aimed to validate the hypothesis formulated in Section 5
and explored the efficiency and practical applicability of the EVOSA approach.
These experiments focus on the local SA, since the full-scale evaluation of
the meta-learning approach requires a more complicated set of experiments.

We use various datasets for binary and multi-class classification from
AutoMLBenchmark [15], and add other real-world datasets for multi-modal
modelling and neural architecture search tasks.

F1, ROC AUC, and precision measures were used for the classification tasks;
RMSE, MAE, MAPE, and $R^{2}$ were used for the regression tasks. The training
time, inference time, and convergence time were analyzed as additional
criteria for comparison.

The computational part of the experiments was conducted using Xeon Cascade
Lake (2900MHz) with 12 cores and 24GB memory.

###  6.2 Benchmarking

To analyze the applicability of local SA techniques for individual cases, each
dataset was analyzed separately. We compared the F1 values for the proposed
EVOSA approach and the alternative solutions - FEDOT (without enhancements),
AutoGluon and H2O (see Table 1). We confirmed that FEDOT selected as the
foundation of the proposed approach is comparable with state-of-the-art
solutions. Also, the SA component improved the quality and reduced the number
of failed runs (marked with dash).

Figure 7 demonstrates an example of the SA output for a single dataset.

Figure 7: Visualization made with sensitivity analysis for a graph on credit-g
dataset.

The original version of FEDOT was compared to FEDOT  with EVOSA in order to
estimate the role of local SA in pipeline optimization. We observe that the SA
component reduces the F1 variance by 6% (see Table 2.). This indicates the
increased stability of the AutoML with the SA component. When compared to
AutoGluon and H2O, no significant differences were observed. This suggests
that the SA brings greater benefits to solutions that prioritize variable-
shaped pipelines. The analysis of statistical significance for F1 metric in 2
confirms that the local SA component does not compromise the predictive power
of the pipelines.

The summary table in Table 3 additionally confirms that the SA component
successfully reduces the complexity of the final pipeline for the majority of
the datasets.

The convergence time was also considered during the analysis. Reducing this
time is extremely important, as it allows obtaining the results of the same
quality more quickly. The results of the analysis are presented in Table 4.
Due to local sensitivity analysis the average convergence time has decreased
by 19.5%, and was statistically significant for 6 datasets, where the training
time decrease was consistently associated with the metric improvement.
However, a significant increase in metrics and convergence was achieved only
for small and medium datasets, advising caution about generalizing these
patterns.

Table 1: The summary table for all datasets with F1 metric. Failed runs are marked with dash. dataset | EVOSA | FEDOT | AutoGluon | H2O
---|---|---|---|---
adult | 0.874 | 0.874 | 0.875 | 0.874
airlines | 0.669 | 0.669 | 0.675 | 0.617
airlinescodrnaadult | 0.812 | - | 0.818 | 0.809
albert | 0.670 | 0.669 | 0.697 | 0.667
amazon_employee_access | 0.949 | 0.947 | 0.951 | 0.953
apsfailure | 0.994 | 0.994 | 0.995 | 0.995
australian | 0.871 | 0.870 | 0.865 | 0.860
bank-marketing | 0.910 | 0.910 | 0.910 | 0.899
blood-transfusion | 0.747 | 0.697 | 0.797 | 0.746
car | 1.000 | 1.000 | 0.998 | 0.998
christine | 0.746 | 0.746 | 0.748 | 0.737
click_prediction_small | 0.835 | 0.835 | 0.777 | 0.777
cnae-9 | 0.957 | 0.954 | 0.957 | 0.954
connect-4 | 0.792 | 0.788 | 0.865 | 0.867
covertype | 0.964 | 0.966 | 0.976 | 0.952
credit-g | 0.753 | 0.759 | 0.766 | 0.727
dilbert | 0.985 | 0.982 | 0.996 | 0.984
fabert | 0.688 | 0.685 | 0.939 | 0.534
fashion-mnist | 0.885 | - | 0.734 | 0.718
guillermo | 0.821 | - | 0.915 | 0.897
helena | 0.332 | 0.333 | 0.837 | 0.823
higgs | 0.731 | 0.732 | 0.369 | 0.336
jannis | 0.718 | 0.718 | 0.743 | 0.719
jasmine | 0.817 | 0.821 | 0.734 | 0.727
jungle_chess_2pcs_raw_endgame_complete | 0.953 | 0.939 | 0.817 | 0.817
kc1 | 0.866 | 0.867 | 0.996 | 0.947
kddcup09_appetency | 0.982 | 0.982 | 0.866 | 0.818
kr-vs-kp | 0.995 | 0.996 | 0.982 | 0.962
mfeat-factors | 0.980 | 0.979 | 0.980 | 0.980
miniboone | 0.948 | 0.948 | 0.952 | 0.949
nomao | 0.969 | 0.970 | 0.975 | 0.974
numerai28_6 | 0.523 | 0.522 | 0.522 | 0.505
phoneme | 0.915 | 0.916 | 0.916 | 0.910
riccardo | 0.997 | - | 0.998 | 0.997
robert | 0.405 | - | 0.559 | 0.487
segment | 0.982 | 0.982 | 0.982 | 0.980
shuttle | 1.000 | 1.000 | 1.000 | 1.000
sylvine | 0.952 | 0.951 | 0.952 | 0.948
vehicle | 0.851 | 0.849 | 0.846 | 0.835
volkert | 0.694 | 0.694 | 0.758 | 0.697
Table 2: The summary table for all datasets for the standard deviation of F1 metric. The average improvement is near 6%. The statistical significance for F1 metric is also indicated. dataset | EVOSA | FEDOT | % decline | p-value
---|---|---|---|---
amazon_employee_access | 0.003 | 0.008 | 63.865 | 0.888
connect-4 | 0.004 | 0.009 | 58.162 | 0.193
albert | 0.003 | 0.005 | 44.172 | 0.211
sylvine | 0.005 | 0.008 | 37.831 | 1.000
vehicle | 0.023 | 0.032 | 25.919 | 1.000
higgs | 0.005 | 0.007 | 20.406 | 0.906
blood-transfusion | 0.085 | 0.107 | 20.305 | 0.593
apsfailure | 0.001 | 0.001 | 20.287 | 0.783
credit-g | 0.026 | 0.030 | 13.887 | 0.598
kc1 | 0.015 | 0.017 | 12.939 | 0.753
numerai28_6 | 0.004 | 0.004 | 11.302 | 0.820
jungle_chess_2pcs_raw_endgame_complete | 0.038 | 0.042 | 9.793 | 0.767
dilbert | 0.006 | 0.006 | 9.173 | 0.261
airlines | 0.002 | 0.002 | 6.705 | 0.675
nomao | 0.002 | 0.002 | 6.051 | 1.000
australian | 0.029 | 0.030 | 5.903 | 0.833
covertype | 0.005 | 0.005 | 5.182 | 0.678
bank-marketing | 0.004 | 0.004 | 4.478 | 0.846
jasmine | 0.020 | 0.020 | 2.444 | 0.695
shuttle | 0.000 | 0.000 | 0.000 | 1.000
click_prediction_small | 0.000 | 0.000 | 0.000 | 1.000
christine | 0.018 | 0.018 | 0.000 | 0.799
jannis | 0.004 | 0.004 | 0.000 | 1.000
segment | 0.008 | 0.008 | 0.000 | 1.000
kddcup09_appetency | 0.000 | 0.000 | 0.000 | 1.000
volkert | 0.007 | 0.007 | 0.000 | 0.767
miniboone | 0.002 | 0.002 | -0.524 | 0.439
cnae-9 | 0.022 | 0.021 | -2.478 | 0.398
adult | 0.004 | 0.004 | -6.305 | 0.922
mfeat-factors | 0.009 | 0.008 | -17.085 | 0.675
kr-vs-kp | 0.006 | 0.005 | -19.291 | 0.833
fabert | 0.014 | 0.011 | -25.601 | 0.515
phoneme | 0.019 | 0.015 | -27.117 | 1.000
helena | 0.023 | 0.013 | -71.389 | 1.000
dataset | EVOSA | FEDOT | % decline | p-value
---|---|---|---|---
credit-g | 0.039 | 0.065 | 40.000 | 0.020
blood-transfusion | 0.009 | 0.012 | 25.000 | 0.625
helena | 0.577 | 0.708 | 18.503 | 0.695
shuttle | 0.068 | 0.078 | 12.821 | 0.004
sylvine | 0.021 | 0.024 | 12.500 | 0.131
australian | 0.019 | 0.021 | 9.524 | 0.652
jungle_chess_2pcs_raw_endgame_complete | 0.108 | 0.118 | 8.475 | 0.557
amazon_employee_access | 0.102 | 0.11 | 7.273 | 0.049
kr-vs-kp | 0.043 | 0.046 | 6.522 | 0.004
cnae-9 | 0.416 | 0.443 | 6.095 | 0.016
airlines | 1.306 | 1.356 | 3.687 | 0.275
kc1 | 0.053 | 0.055 | 3.636 | 0.219
bank-marketing | 0.237 | 0.242 | 2.066 | 0.084
nomao | 1.257 | 1.26 | 0.238 | 0.557
phoneme | 0.021 | 0.021 | 0.000 | 0.734
segment | 0.025 | 0.025 | 0.000 | 0.010
connect-4 | 1.048 | 1.046 | -0.191 | 0.922
adult | 0.255 | 0.254 | -0.394 | 0.770
jasmine | 0.095 | 0.094 | -1.064 | 0.770
miniboone | 0.749 | 0.736 | -1.766 | 0.275
higgs | 0.765 | 0.749 | -2.136 | 0.004
numerai28_6 | 0.217 | 0.212 | -2.358 | 0.012
fabert | 1.87 | 1.825 | -2.466 | 0.014
jannis | 0.52 | 0.507 | -2.564 | 0.002
christine | 2.633 | 2.546 | -3.417 | 0.006
kddcup09_appetency | 1.877 | 1.790 | -4.860 | 0.002
click_prediction_small | 15.418 | 14.551 | -5.958 | 0.084
mfeat-factors | 0.098 | 0.092 | -6.522 | 0.049
dilbert | 2.966 | 2.777 | -6.806 | 0.105
albert | 14.231 | 12.018 | -18.414 | 0.000
car | 0.016 | 0.013 | -23.077 | 0.084
covertype | 7.582 | 5.449 | -39.145 | 0.002
vehicle | 0.028 | 0.020 | -40.000 | 0.469
volkert | 2.203 | 1.379 | -59.753 | 0.002
apsfailure | 3.410 | 2.030 | -67.980 | 0.002
Table 3: The summary table for all datasets for inference time metric. The results are sorted in order of inference duration reduction. The statistically significant results are highlighted. dataset | EVOSA | FEDOT | % decline | p-value
---|---|---|---|---
vehicle | 1462.531 | 12647.102 | 88.436 | 0.031
mfeat-factors | 2766.071 | 18474.823 | 85.028 | 0.131
blood-transfusion | 2346.217 | 12889.076 | 81.797 | 0.250
jasmine | 5193.225 | 23060.815 | 77.480 | 0.922
credit-g | 3740.598 | 13108.432 | 71.464 | 0.020
cnae-9 | 4189.021 | 12772.144 | 67.202 | 0.016
dilbert | 2505.432 | 6156.280 | 59.303 | 0.049
kc1 | 2600.527 | 6372.382 | 59.191 | 0.156
australian | 2617.357 | 6214.310 | 57.882 | 0.496
kr-vs-kp | 10705.224 | 19728.782 | 45.738 | 0.027
helena | 13160.250 | 20251.298 | 35.015 | 0.002
jungle_chess_2pcs_raw_endgame_complete | 8828.419 | 13543.298 | 34.813 | 0.232
apsfailure | 8013.792 | 11696.746 | 31.487 | 0.846
phoneme | 11797.471 | 16968.637 | 30.475 | 0.570
covertype | 23090.240 | 30720.282 | 24.837 | 0.084
miniboone | 10227.532 | 12929.883 | 20.900 | 0.432
bank-marketing | 5903.615 | 7188.698 | 17.876 | 0.695
segment | 24170.218 | 28551.054 | 15.344 | 0.492
shuttle | 16798.069 | 19616.598 | 14.368 | 0.557
connect-4 | 6922.035 | 7562.561 | 8.470 | 0.695
sylvine | 16186.471 | 17548.978 | 7.764 | 0.492
airlines | 14491.557 | 15569.290 | 6.922 | 1.000
adult | 7642.738 | 8094.004 | 5.575 | 0.322
car | 14671.193 | 15198.661 | 3.470 | 0.922
christine | 8631.138 | 8685.650 | 0.628 | 0.770
nomao | 5901.600 | 5930.465 | 0.487 | 0.770
jannis | 13009.647 | 12499.170 | -4.084 | 0.846
amazon_employee_access | 6042.829 | 5698.814 | -6.037 | 0.432
volkert | 11547.871 | 10650.005 | -8.431 | 1.000
numerai28_6 | 5553.752 | 4735.128 | -17.288 | 1.000
albert | 29824.311 | 23469.102 | -27.079 | 0.133
higgs | 8734.603 | 6834.383 | -27.804 | 0.625
fabert | 7197.197 | 5156.928 | -39.564 | 1.000
kddcup09_appetency | 13099.101 | 5079.595 | -157.877 | 0.625
Table 4: The summary table for all datasets for convergence time metric. The
results are sorted in descending order of decline. Average improvement is
19.5%. The statistically significant results are highlighted.

We observed a statistically significant improvement for the standard deviation
of results, inference, and convergence time. The quality metrics are
comparable with SOTA solutions. This confirms our hypothesis that the
involvement of SA can improve the evolutionary AutoML without compromising the
predictive power of obtained pipelines.

In the implemented solution, each SA-based AutoML run can be visualized
interactively. The visualization results are presented in Figure 8.

Figure 8: Visualization of evolutionary history for the jungle-chess dataset.
Sensitivity Analysis is applied.

For a better understanding of how fitness improves in the process of
evolution, the following visualizations are also presented in Figure 9 Thus,
it can be seen that the use of sensitivity analysis can significantly speed up
the convergence process.

Figure 9: Visualization of the evolution process with the comparison of basic
FEDOT and EVOSA. The convergence of fitness function is averaged for 10 runs.

Since the proposed sensitivity analysis techniques are implemented in a multi-
objective way, several metrics can be used and visualized as a result. An
example is provided in Figure 10, however, it has been simplified for greater
readability.

Figure 10: Example of visualization of multi-objective SA. The accuracy and f1
metrics are provided.

###  6.3 Real-world cases

We explored the generalizability of the observed patterns, by testing the
efficiency of EVOSA outside the well-known pull of AutoML tasks. Our extended
experimental sample included a regression task for prediction of molecular
energies, as well as multimodal classification and regression datasets. We
additionally evaluated the local SA-based approach for the task of neural
architecture search (NAS) for the convolutional neural networks (CNNs),

####  6.3.1 SA for multimodal pipelines

The experimental data were taken from the multimodal AutoML
benchmark222https://github.com/sxjscience/automl_multimodal_benchmark, which
includes tabular datasets with textual columns. Due to limited computing power
and large volumes of the benchmark, half of the datasets were used (the ratio
of datasets’ sizes and metrics was preserved). In some datasets, some columns
were excluded (the same was done by benchmark
authors)333https://github.com/sxjscience/automl_multimodal_benchmark/blob/main/multimodal_text_benchmark/src/auto_mm_bench/datasets.py.
Results of the application of local SA are presented in Table 5. The obtained
metrics indicate a significant advantage of EVOSA optimizer.

[HTML]FFFFFFDataset |  [HTML]FFFFFFMetric |  [HTML]FFFFFF  | Proposed
---
EVOSA
optimiser
[HTML]FFFFFF  | Auto
---
Gluon
[HTML]FFFFFF  | Impr.,
---
%
[HTML]FFFFFFjigsaw |  [HTML]FFFFFFROC-AUC |  [HTML]FFFFFF0.947 |  [HTML]FFFFFF0.967 |  [HTML]FFFFFF-2.07
[HTML]FFFFFFprod |  [HTML]FFFFFFaccuracy |  [HTML]FFFFFF0.897 |  [HTML]FFFFFF0.909 |  [HTML]FFFFFF-1.32
[HTML]FFFFFFqaa |  [HTML]FFFFFFR2 |  [HTML]FFFFFF0.445 |  [HTML]FFFFFF0.438 |  [HTML]FFFFFF+1.60
[HTML]FFFFFFqaq |  [HTML]FFFFFF[HTML]FFFFFFR2 |  [HTML]FFFFFF0.554 |  [HTML]FFFFFF0.456 |  [HTML]FFFFFF+21.49
[HTML]FFFFFFmercari |  [HTML]FFFFFF[HTML]FFFFFFR2 |  [HTML]FFFFFF0.999 |  [HTML]FFFFFF0.605 |  [HTML]FFFFFF+65.12
[HTML]FFFFFFjc |  [HTML]FFFFFF[HTML]FFFFFFR2 |  [HTML]FFFFFF0.619 |  [HTML]FFFFFF0.624 |  [HTML]FFFFFF-0.80
[HTML]FFFFFFaverage |  [HTML]FFFFFF[HTML]FFFFFF |  [HTML]FFFFFF |  [HTML]FFFFFF |  [HTML]FFFFFF+14.00
Table 5: Comparison of AutoGluon with EVOSA approach for the multimodal
datasets.

####  6.3.2 Molecular energy prediction

The precise estimation of molecular energies is significant for reliable
modelling of various chemical and biological processes in general and for
solving different applied tasks; however, the application of existing
analytical methods is highly computationally expensive and impractical [19].
Therefore, machine learning methods are becoming popular in this field due to
their ability to learn general patterns in a given dataset and to predict
properties of unknown structures, particularly the molecular energy[38].

The fast development of deep neural networks allowed the researchers to make
more accurate predictions of the energy of stable molecules. Most proposed
models were evaluated on the QM9 dataset, which contains 134k small organic
molecules in the potential energy stable (equilibrium) state[31]. In recent
years, the best obtained MAE of these models was reduced from 0.0134 eV[34] to
0.0059 eV[36].

The possibility of effective use of AutoML on molecular energy prediction was
discovered in the MolHack 2022 competition organized by Artificial
Intelligence Research
Institute444https://www.kaggle.com/competitions/molhack-2022/. Using EVOSA on
raw data leads to the Top-3 results on the leaderboard. Models with better
metrics are based on the sophisticated preprocessing and feature engineering,
which require expert knowledge, and cannot be easily applied in an automated
machine learning.

In this experiment, the performance of the SA-based evolutionary solution
EVOSA was compared to three popular AutoML frameworks (AutoGluon, H2O and
TPOT). The training dataset contains 200,232 rows, split in a ratio of
0.75:0.25 (150,174 and 50,058 rows for train and test subsets), the validation
dataset contained 32,884 rows. The frameworks were fitted under 1 hour and 4
hour restrictions, with the “best quality” preset (where possible), and on 12
concurrently running workers. No manual preprocessing was performed, and
features did not contain information about molecular space structure. The
results in Table 6 suggest that EVOSA significantly outperforms AutoGluon (AG)
and H2O frameworks with the 1-hour time limit; although RMSE of TPOT is better
in the 1-hour experiment, it does not improve with time (in the 4-hour
experiment). In the 4-hour experiment, EVOSA outperforms all competitors. All
frameworks were fitted to raw data, and we expect additional profit for the
AutoML system from the expert manual feature engineering and preprocessing.

Time |  Metric | AG | EVOSA | H2O | TPOT
---|---|---|---|---|---
1 h |  MAE | 0.553 | 0.044 | 2.657 | 0.065
RMSE | 6.554 | 0.272 | 13.863 | 0.090
4 h |  MAE | 0.468 | 0.042 |  | 0.066
RMSE | 6.289 | 0.070 |  | 0.090
Table 6: Comparison of AutoML solutions with EVOSA approach for the real-world
regression dataset.

EVOSA model inference is much faster than deep neural network models. However,
EVOSA cannot be used as a potential energy predictor due to a relatively high
error. It can be used in a preliminary stage to classify molecules by their
stability and filter non-acceptable ones to finally reduce the total time
required for molecules’ energy search[35].

####  6.3.3 NAS

Finally, explored EVOSA outside the scope of ML pipeline design, applying it
to neural architecture search for the CNNs.

Our implementation of the NAS is based on the evolutionary optimizer described
above. The structure of a CNN is represented as a graph. Each node corresponds
to a neural network layer, and node parameters correspond to layer parameters
such as the number of neurons and activation function for a dense layer,
stride, padding, and pooling type for conv2d layers with different kernel
sizes. Also, each node can have dropout and batch normalization layers as
additional parameters. Thus, the proposed algorithm can generate deep CNNs
using a variable number of different layers: conv2d 1x1, conv2d 3x3, conv2d
5x5 conv2d 7x7, batch normalization, dense, dropout, average and max pooling,
and has support for skip connections with different shortcut lengths and the
number of overlaps.

The experiment was conducted with the butterfly classification dataset from
Kaggle555https://www.kaggle.com/datasets/gpiosenka/butterfly-images40-species,
which contains about 10000 images of 75 different species of butterflies. The
following parameters were used for the NAS experiments: population size - 15,
number of generations - 15, number of epochs to train - 30, batch size - 16,
and image size 256 with an ResNet-34 [16] as initial assumption.

Figure 11: NAS-generated graph after local SA.

Due to the neural network’s graph representation, we can also use sensitivity
analysis for further adjustments to the architecture of CNN. We can analyze
each node and each edge of the neural network in terms of how the fitness
function changes if we apply transformations to the nodes or edges. It allows
optimizing the neural network architecture, dropping or replacing redundant
layers or connections.

The experiment took about 8 hours. After applying sensitivity analysis, we
increased the neural network’s performance on the same task by changing the
parameters of several layers. This resulted in an optimized architecture
similar to NAS in terms of performance, but with an improved convergence and
inference durations (see Table 7 and Figure 11)

Metric | Before SA | After SA
---|---|---
Fitness | 5.53 | 3.82
ROC-AUC | 0.974 | 0.987
Accuracy | 0.586 | 0.713
logloss | 2.156 | 1.276
Table 7: Application of SA to the results of NAS

##  7 Discussion

In this study, we aimed to confirm that the integration of SA and evolutionary
optimization can increase the effectiveness of AutoML. The experimental study
was designed to analyze this hypothesis from different sides. The set of
benchmarks and real-world cases were involved in comparison, as well as
various criteria were considered: quality-based, stability-based, convergence-
based, and time-based.

The obtained results were analyzed to confirm or reject the hypothesis
formulated in Section 4. First of all, there is no statistically significant
difference in prediction quality metrics between the EVOSA and state-of-the-
art solutions (FEDOT, AutoGluon, H2O). However, the predictive quality highly
depends on the set of “building blocks” (models and operations) used during
optimization. Also, the relatively small number of datasets in AutoMLBenchmark
and values of quality measures that are already close to optima make the use
of statistical tests not that illustrative.

For this reason, we are focusing the analysis not on the comparison between
state-of-the-art solutions itself, but on the analysis of improvement in
convergence time and decreased variance of results and complexity of pipelines
after the involvement of SA in evolutionary optimization. This part of the
analysis confirms the practical applicability of SA techniques, since the
faster convergence is quite critical for AutoML tool [20]. Also, we
successfully investigated the applicability of EVOSA to real-world cases and
tasks from different fields: from multi-modal modelling to neural architecture
search. So, we can conclude the hypothesis in empirically confirmed (since
convergence time, inference time and standard deviation of quality metrics and
reduced without loss in predictive quality).

We used FEDOT AutoML framework as a case study in the paper. However, the
EVOSA can be applied for other AutoML tools that face the similiar problems
(over-complicated and non-explainable pipelines).

The future extension of this research can be directed to the full-scale
implementation of meta-learning techniques based on global SA and its
extension to other AutoML tasks (e.g. time series forecasting and time series
classification). It requires both implementation of this approach and an
extensive set of experiments to confirm its applicability. Also, the surrogate
models based on graph neural networks can be used to reduce the computational
cost of SA.

##  8 Conclusion

This paper implements the techniques for integrating evolutionary AutoML and
SA. We propose the EVOSA approach that can be used to design variable-shaped
pipelines. Besides their theoretical applicability, the setup for experimental
validation is described.

The following datasets are used for experiments: (1) Tabular datasets from
OpenML (classification/regression); (2) Tabular from hackathon (regression);
(3) Multimodal datasets from the benchmark (classification/regression); (4)
Image dataset from Kaggle (classification).

The achieved results can be explained in the following way. For the
AutoMLBenchmark, the quality metrics do not significantly differ from the
state-of-the-art solutions. However, the improvement in convergence time is
near 20%, as well as a 5% improvement in the stability of results. Also,
statistical significance was achieved for 15 datasets by inference time and
for 6 datasets by convergence time. It was also noted that local SA tends to
work better on small and medium datasets. It is important to note that EVOSA
avoids running structural optimization if the training time for the model is
comparable with a full time limit.

Also, for more complicated real-world cases, the improvement exceeds 5%. Also,
we run the experiments to confirm the applicability of implemented solution
not only for ML pipelines, but also for search of optimal architectures of
convolutional neural networks. For these reasons, EVOSA can be considered a
valuable tool set for the interpretation of the data-driven models (both ML
pipelines and neural networks). As an extension of this research, it is
promising to conduct the wide-scale set of experiments for global SA to
evaluate the applicability of SA-based meta-learning. The experimental studies
should involve not only tabular classification and regression tasks, but also
time series forecasting and time series classification as more complicated and
diverse problems.

##  9 REFERENCES

## References

  * [1] Irina V Barabanova, Pavel Vychuzhanin and Nikolay O Nikitin  “Sensitivity Analysis of the Composite Data-Driven Pipelines in the Automated Machine Learning”  In _Procedia Computer Science_ 193 Elsevier, 2021, pp. 484–493
  * [2] José P Cambronero, Jürgen Cito and Martin C Rinard  “Ams: Generating automl search spaces from weak specifications”  In _Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2020, pp. 763–774
  * [3] Rich Caruana and Alexandru Niculescu-Mizil  “Ensemble Selection from Libraries of Models”, 2004
  * [4] Vito D’Orazio, James Honaker, Raman Prasady and Michael Shoemate  “Modeling and forecasting armed conflict: AutoML with human-guided machine learning”  In _2019 IEEE International Conference on Big Data (Big Data)_ , 2019, pp. 4714–4723  IEEE
  * [5] Piali Das et al.  “Amazon SageMaker Autopilot: a white box AutoML solution at scale”  In _Proceedings of the fourth international workshop on data management for end-to-end machine learning_ , 2020, pp. 1–7
  * [6] Andrea De Lorenzo, Eric Medvet, Tea Tušar and Alberto Bartoli  “An analysis of dimensionality reduction techniques for visualizing evolution”  In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2019, pp. 1864–1872
  * [7] Jaimie Drozdal et al.  “Trust in AutoML: exploring information needs for establishing trust in automated machine learning systems”  In _Proceedings of the 25th International Conference on Intelligent User Interfaces_ , 2020, pp. 297–307
  * [8] Mengnan Du, Ninghao Liu and Xia Hu  “Techniques for interpretable machine learning”  In _Communications of the ACM_ 63.1 ACM New York, NY, USA, 2019, pp. 68–77
  * [9] Nick Erickson et al.  “AutoGluon-Tabular: Robust and Accurate AutoML for Structured Data”  In _7th ICML Workshop on Automated Machine Learning_ , 2020
  * [10] Nick Erickson et al.  “Autogluon-tabular: Robust and accurate automl for structured data”  In _arXiv preprint arXiv:2003.06505_ , 2020
  * [11] Matthias Feurer et al.  “Auto-Sklearn 2.0: The Next Generation”  In _arXiv_ , 2020, pp. 1–18  arXiv: http://arxiv.org/abs/2007.04074
  * [12] Matthias Feurer et al.  “Efficient and robust automated machine learning”  In _Advances in neural information processing systems_ 28, 2015
  * [13] Nicolo Fusi, Rishit Sheth and Melih Elibol  “Probabilistic matrix factorization for automated machine learning”  In _Advances in neural information processing systems_ 31, 2018, pp. 3348–3357
  * [14] Pieter Gijsbers, Joaquin Vanschoren and Randal S. Olson  “Layered TPOT: Speeding up Tree-based Pipeline Optimization”, 2018  URL: http://arxiv.org/abs/1801.06007
  * [15] Pieter Gijsbers et al.  “An open source AutoML benchmark”  In _arXiv preprint arXiv:1907.00909_ , 2019
  * [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren and Jian Sun  “Deep residual learning for image recognition”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778
  * [17] Xin He, Kaiyong Zhao and Xiaowen Chu  “AutoML: A survey of the state-of-the-art”  In _Knowledge-Based Systems_ 212 Elsevier, 2021, pp. 106622
  * [18] Lars Kotthoff et al.  “Auto-WEKA: Automatic model selection and hyperparameter optimization in WEKA”  In _Automated machine learning_ Springer, Cham, 2019, pp. 81–95
  * [19] Siddhartha Laghuvarapu, Yashaswi Pathak and U Deva Priyakumar  “Band nn: A deep learning framework for energy prediction and geometry optimization of organic small molecules”  In _Journal of computational chemistry_ 41.8 Wiley Online Library, 2020, pp. 790–799
  * [20] Teddy Lazebnik, Amit Somech and Abraham Itzhak Weinberg  “SubStrat: A Subset-Based Strategy for Faster AutoML”  In _arXiv preprint arXiv:2206.03070_ , 2022
  * [21] E. Ledell and S. Poirier  “H2O AutoML: Scalable Automatic Machine Learning”  In _7th ICML Workshop on Automated Machine Learning_ , 2020  URL: https://www.automl.org/wp-content/uploads/2020/07/AutoML_2020_paper_61.pdf
  * [22] Peio Loubiere, Astrid Jourdan, Patrick Siarry and Rachid Chelouah  “A sensitivity analysis method for driving the Artificial Bee Colony algorithm’s search process”  In _Applied Soft Computing_ 41 Elsevier, 2016, pp. 515–531
  * [23] Daniel P Loucks, Eelco Van Beek, Daniel P Loucks and Eelco Beek  “System sensitivity and uncertainty analysis”  In _Water Resource Systems Planning and Management: An Introduction to Methods, Models, and Applications_ Springer, 2017, pp. 331–374
  * [24] Nikolay O Nikitin et al.  “Automated evolutionary approach for the design of composite machine learning pipelines”  In _Future Generation Computer Systems_ 127 Elsevier, 2022, pp. 109–125
  * [25] Randal S Olson and Jason H Moore  “TPOT: A tree-based pipeline optimization tool for automating machine learning”  In _Workshop on automatic machine learning_ , 2016, pp. 66–74  PMLR
  * [26] Jorge Piazentin Ono et al.  “PipelineProfiler : A Visual Analytics Tool for the Exploration of AutoML Pipelines”
  * [27] Jorge Piazentin Ono et al.  “Pipelineprofiler: A visual analytics tool for the exploration of automl pipelines”  In _IEEE Transactions on Visualization and Computer Graphics_ 27.2 IEEE, 2020, pp. 390–400
  * [28] Youngjun Park, Anne-Christin Hauschild and Dominik Heider  “Transfer learning compensates limited data, batch effects and technological heterogeneity in single-cell sequencing”  In _NAR Genomics and Bioinformatics_ 3.4, 2021  DOI: 10.1093/nargab/lqab104
  * [29] Fabian Pedregosa et al.  “Scikit-learn: Machine learning in Python”  In _Journal of machine learning research_ 12.Oct, 2011, pp. 2825–2830
  * [30] Philipp Probst, Anne-Laure Boulesteix and Bernd Bischl  “Tunability: Importance of hyperparameters of machine learning algorithms.”  In _J. Mach. Learn. Res._ 20.53, 2019, pp. 1–32
  * [31] Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp and O Anatole Von Lilienfeld  “Quantum chemistry structures and properties of 134 kilo molecules”  In _Scientific data_ 1.1 Nature Publishing Group, 2014, pp. 1–7
  * [32] Waddah Saeed and Christian Omlin  “Explainable AI (XAI): A systematic meta-survey of current challenges and future opportunities”  In _Knowledge-Based Systems_ 263 Elsevier, 2023, pp. 110273
  * [33] Andrea Saltelli, Anthony Jakeman, Saman Razavi and Qiongli Wu  “Sensitivity analysis: A discipline coming of age”  In _Environmental Modelling & Software_ 146 Elsevier, 2021, pp. 105226
  * [34] Kristof Schütt et al.  “Schnet: A continuous-filter convolutional neural network for modeling quantum interactions”  In _Advances in neural information processing systems_ 30, 2017
  * [35] Kristof T Schütt et al.  “Quantum-chemical insights from deep tensor neural networks”  In _Nature communications_ 8.1 Nature Publishing Group, 2017, pp. 1–8
  * [36] Zeren Shui and George Karypis  “Heterogeneous molecular graph neural networks for predicting molecule properties”  In _2020 IEEE International Conference on Data Mining (ICDM)_ , 2020, pp. 492–500  IEEE
  * [37] Chris Thornton, Frank Hutter, Holger H. Hoos and Kevin Leyton-Brown  “Auto-WEKA: Combined selection and hyperparameter optimization of classification algorithms”  In _Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ Part F1288, 2013, pp. 847–855  DOI: 10.1145/2487575.2487629
  * [38] Oliver T Unke and Markus Meuwly  “PhysNet: A neural network for predicting energies, forces, dipole moments, and partial charges”  In _Journal of chemical theory and computation_ 15.6 ACS Publications, 2019, pp. 3678–3693
  * [39] Anton Vakhrushev et al.  “LightAutoML: AutoML Solution for a Large Financial Services Ecosystem”  In _arXiv preprint arXiv:2109.01528_ , 2021
  * [40] Iordanis Xanthopoulos et al.  “Putting the Human Back in the AutoML Loop.”  In _EDBT/ICDT Workshops_ , 2020
  * [41] Marc-André Zöller, Tien-Dung Nguyen and Marco F Huber  “Incremental Search Space Construction for Machine Learning Pipeline Synthesis”  In _arXiv preprint arXiv:2101.10951_ , 2021


# Examples of hyperbolic spaces without the properties of quasi-ball or
bounded eccentricity

Qizheng You and Jiawen Zhang  School of Mathematical Sciences, Fudan
University, 220 Handan Road, Shanghai, 200433, China.
<EMAIL_ADDRESS>School of Mathematical Sciences, Fudan University,
220 Handan Road, Shanghai, 200433, China<EMAIL_ADDRESS>
###### Abstract.

In this note, we present examples of non-quasi-geodesic metric spaces which
are hyperbolic (_i.e._ , satisfying the Gromov’s $4$-point condition) while
the intersection of any two metric balls therein does not either “look like” a
ball or has uniformly bounded eccentricity. This answers an open question
posed in [2].

Keywords: Gromov’s hyperbolic spaces, Non-(quasi)-geodesic, Quasi-ball
property, Bounded eccentricity property

##  1\. Introduction

In the seminal work [4], Gromov introduced a notion of hyperbolicity for
metric spaces which encodes the information of metric curvatures for the
underlying spaces, with prototypes from classic hyperbolic geometry. Gromov’s
hyperbolic spaces have attractd a lot of interest since they are discovered
and have fruitful applications in various aspects of mathematics (see, _e.g._
, [1, 3]).

Recall that a geodesic metric space $(X,d)$ is called _hyperbolic_ (in the
sense of Gromov [4]) if there exists $\delta>0$ such that for any geodesic
triangle in $(X,d)$, the union of the $\delta$-neighbourhoods of any two sides
of the triangle contains the third. Gromov also provided a characterisation
for his hyperbolicity using the so-called _Gromov product_ :

$(x|y)_{p}=\frac{1}{2}(d(x,p)+d(y,p)-d(x,y))\quad\text{for}\quad
x,y,p\in(X,d).$

He proved in [4] that a geodesic metric space $(X,d)$ is hyperbolic _if and
only if_ the following condition holds:

Gromov’s $4$-point condition: There exists $\delta>0$ such that

$(x|y)_{p}\geq\min\\{(x|z)_{p},(y|z)_{p}\\}-\delta\quad\text{for all}\quad
x,y,z,p\in(X,d).$

Note that the statement of the Gromov’s $4$-point condition does not require
that the underlying space $(X,d)$ is geodesic. Hence in the general context,
we say that a (not necessarily geodesic) metric space is _hyperbolic_ if the
Gromov’s $4$-point condition holds.

Later in [2], Chatterji and Niblo discovered new characterisations of Gromov’s
hyperbolicity for geodesic metric spaces using the geometry of intersections
of balls. More precisely, for a geodesic metric space, they showed that it is
hyperbolic in the sense of Gromov _if and only if_ the following holds:

Quasi-ball property: The intersection of any two metric balls is at uniformly
bounded Hausdorff distance from a ball.

They also considered the eccentricity of the intersection of balls. Recall
that for a metric space $(X,d)$ and $\delta>0$, we say that the _eccentricity_
of a subset $S$ of $X$ is less than $\delta$ if there exist $c,c^{\prime}\in
X$ and $R\geq 0$ such that

(1.1) $B(c,R)\subseteq S\subseteq B(c^{\prime},R+\delta).$

Here we use $B(x,r):=\\{y\in X:d(x,y)\leq r\\}$ to denote the metric ball. The
_eccentricity_ of $S$ is the infimum of $\delta$ satisfying (1.1). By
convention, the eccentricity of the empty set is $0$. Chatterji and Niblo
proved in [2] that a geodesic metric space is hyperbolic _if and only if_ the
following holds:

Bounded eccentricity property: The intersection of any two metric balls has
uniformly bounded eccentricity.

In [2, Section 4], Chatterji and Niblo also discussed the situation of non-
geodesic metric spaces. They recorded an example due to Viktor Schroeder (see
[2, Example 18]) that there exists a non-geodesic metric space with the quasi-
ball property but not hyperbolic (_i.e._ , does not satisfy the Gromov’s
$4$-point condition). However, the other direction is unclear and hence, they
asked the following:

######  Question 1.1.

Does there exist a non-geodesic hyperbolic metric space which does not satisfy
the quasi-ball property or the bounded eccentricity property?

In this short note, we provide an affirmative answer to Question 1.1 by
constructing concrete examples. The main result is the following:

######  Theorem 1.2.

There exists a non-quasi-geodesic hyperbolic (_i.e._ , satisfying the Gromov’s
$4$-point condition) space which does not satisfy either the quasi-ball
property or the bounded eccentricity property.

Our construction is motivated by Gromov’s observation in [4, Section 1.2]
(also suggested in [2, Section 4]) that for a metric space $(X,d)$, we can
endow another metric $d^{\prime}$ on $X$ defined by

(1.2) $d^{\prime}(x,y)=\ln(1+d(x,y))\quad\text{for}\quad x,y\in X$

such that $(X,d^{\prime})$ satisfies the Gromov’s $4$-point condition. We show
that if $(X,d)$ is geodesic and unbounded, then $(X,d^{\prime})$ cannot be
quasi-geodesic (see Corollary 3.3). Then we study the relation of the quasi-
ball property and the bounded eccentricity property between $(X,d)$ and
$(X,d^{\prime})$ (see Lemma 3.5, Lemma 3.7 and Lemma 3.9). Finally, we show in
Example 3.10 that for the Euclidean space $X=\mathbb{R}^{2}$ with the
Euclidean metric $d$, the construction $(X,d^{\prime})$ in (1.2) provides an
example to conclude Theorem 1.2.

##  2\. Preliminaries

Here we collect some necessary notions and notation for this note.

Let $(X,d)$ be a metric space. For $x\in X$ and $R\geq 0$, denote the (metric)
ball by $B(x,R)=\\{y\in X:d(x,y)\leq R\\}$. We say that $(X,d)$ is _bounded_
if there exist $x\in X$ and $R\geq 0$ such that $X=B(x,R)$, and _unbounded_ if
it is not bounded. For a subset $A\subset X$ and $R\geq 0$, denote
$\mathcal{N}_{R}(A)=\\{x\in X:d(x,A)\leq R\\}$ the $R$-_neighbourhood_ of $A$
in $X$. For subsets $A,B\subset X$, the _Hausdorff distance_ between $A$ and
$B$ is

$d_{H}(A,B)=\inf\\{R\geq 0:A\subseteq\mathcal{N}_{R}(B)\text{ and
}B\subseteq\mathcal{N}_{R}(A)\\}.$

Recall that a _path_ in a metric space $(X,d)$ is a continuous map
$\gamma:[a,b]\to X$. A path $\gamma$ is called _rectifiable_ if its _length_

$\ell(\gamma):=\sup\left\\{\sum_{i=1}^{n}d(\gamma(t_{i-1}),\gamma(t_{i})):a=t_{0}<t_{1}<\cdots<t_{n}=b,n\in\mathbb{N}\right\\}$

is finite. Usually it is convenient to change the parameter $t\in[a,b]$ to the
_standard arc parameter_ $s\in[0,\ell(\gamma)]$ as follows. Define a map
$\varphi:[a,b]\rightarrow[0,\ell(\gamma)]$ by $t\mapsto
s=\ell(\gamma|_{[a,t]})$, and set $\tilde{\gamma}:[0,\ell(\gamma)]\to X$ by
$\tilde{\gamma}:=\gamma\circ\varphi^{-1}$. Then we have
$\ell(\tilde{\gamma}|_{[s_{1},s_{2}]})=|s_{1}-s_{2}|$ for any $0\leq s_{1}\leq
s_{2}\leq\ell(\gamma)$.

Now we recall the notion of (quasi-)geodesics.

######  Definition 2.1.

Let $(X,d)$ be a metric space.

  1. (1)

Given $x,y\in X$, a _geodesic_ between $x$ and $y$ is an isometric embedding
$\gamma:[0,d(x,y)]\rightarrow X$ with $\gamma(0)=x$ and $\gamma(d(x,y))=y$.
The space $(X,d)$ is called _geodesic_ if for any $x,y$ in $X$, there exists a
geodesic between $x$ and $y$.

  2. (2)

Given $x,y\in X,L\geq 1$ and $C\geq 0$, an _$(L,C)$ -quasi-geodesic_ between
$x$ and $y$ is a map $\gamma:[0,T]\rightarrow X$ such that
$\gamma(0)=x,\gamma(T)=y$ and

$\frac{1}{L}|a-b|-C\leq d(\gamma(a),\gamma(b))\leq L|a-b|+C\quad\text{for
all}\quad a,b\in[0,T].$

The space $(X,d)$ is called _$(L,C)$ -quasi-geodesic_ if for any $x,y$ in $X$,
there exists an $(L,C)$-quasi-geodesic between $x$ and $y$. We also say that
$(X,d)$ is _quasi-geodesic_ if it is $(L,C)$-quasi-geodesic for some $L$ and
$C$.

We also need the notion of ultrametric space. Recall that a metric space
$(X,d)$ is called _ultrametric_ if there exists $\delta>0$ such that for any
points $x,y,z\in X$, we have

$d(x,y)\leq\mathrm{max}\\{d(x,z),d(y,z)\\}+\delta.$

The following is due to Gromov:

######  Lemma 2.2 ([4, Section 1.2]).

An ultrametric space satisfies the Gromov’s $4$-point condition.

Recall from Section 1 that for a metric space $(X,d)$, Gromov considered
another metric $d^{\prime}$ on $X$ defined in (1.2) and noticed that

$\displaystyle d^{\prime}(x,y)$ $\displaystyle\leq$
$\displaystyle\ln(1+d(x,z)+d(z,y))$ $\displaystyle\leq$
$\displaystyle\ln(2+2\mathrm{max}\\{d(x,z),d(y,z)\\})$ $\displaystyle=$
$\displaystyle\mathrm{max}\\{d^{\prime}(x,z),d^{\prime}(y,z)\\}+\ln 2.$

Combining with Lemma 2.2, we obtain the following:

######  Lemma 2.3 ([4, Section 1.2]).

For a metric space $(X,d)$, the new metric $d^{\prime}$ on $X$ defined in
(1.2) satisfies the Gromov’s $4$-point condition.

##  3\. Proof of Theorem 1.2

This whole section is devoted to the proof of Theorem 1.2, which is divided
into several parts.

Firstly, we would like to study the property of (quasi-)geodesic for the new
metric $d^{\prime}$ defined in (1.2). To simplify the notation, for a path
$\gamma$ in $X$, we denote $\ell(\gamma)$ and $\ell^{\prime}(\gamma)$ its
length with respect to the metric $d$ and $d^{\prime}$, respectively.

We need the following lemma:

######  Lemma 3.1.

Let $(X,d)$ be a metric space and $d^{\prime}$ be the metric on $X$ defined in
(1.2). A path $\gamma:[a,b]\rightarrow X$ in $X$ is rectifiable with respect
to $d$ _if and only if_ it is rectifiable with respect to $d^{\prime}$. In
this case, we have $\ell(\gamma)=\ell^{\prime}(\gamma)$.

###### Proof.

Firstly, we assume that $\gamma$ is rectifiable with respect to $d$, _i.e._ ,
$\ell(\gamma)<\infty$. Note that $\ln(1+x)\leq x$ holds for all $x\geq 0$.
Hence for any partition $a=t_{0}<t_{1}<\cdots<t_{n}=b$, we have

$\sum_{i=1}^{n}d^{\prime}(\gamma(t_{i-1}),\gamma(t_{i}))\leq\sum_{i=1}^{n}d(\gamma(t_{i-1}),\gamma(t_{i}))\leq\ell(\gamma),$

which implies that $\ell^{\prime}(\gamma)\leq\ell(\gamma)$. In particular,
$\gamma$ is rectifiable with respect to $d^{\prime}$.

Conversely, we assume that $\gamma$ is rectifiable with respect to
$d^{\prime}$, _i.e._ , $\ell^{\prime}(\gamma)<\infty$. Without loss of
generality, we can assume that $\gamma$ is parametrised by the standard arc
parameter with $a=0$ and $b=\ell^{\prime}(\gamma)$. Note that for any
$\alpha\in(0,1)$, there exists $\delta>0$ such that $\alpha x\leq\ln(1+x)$
holds for all $x\in[0,\delta]$. Given a partition
$a=s_{0}<s_{1}<\cdots<s_{m}=b$, we choose a refinement
$a=t_{0}<t_{1}<\cdots<t_{n}=b$ such that $|t_{i-1}-t_{i}|<\ln(1+\delta)$ holds
for all $i$. Hence we have

$d^{\prime}(\gamma(t_{i-1}),\gamma(t_{i}))\leq
l^{\prime}(\gamma|_{[t_{i-1},t_{i}]})=|t_{i-1}-t_{i}|<\ln(1+\delta),$

which implies that $d(\gamma(t_{i-1}),\gamma(t_{i}))<\delta$ due to (1.2).
Therefore, we obtain

$\sum_{i=1}^{m}d(\gamma(s_{i-1}),\gamma(s_{i}))\leq\sum_{i=1}^{n}d(\gamma(t_{i-1}),\gamma(t_{i}))\leq\frac{1}{\alpha}\cdot\sum_{i=1}^{n}d^{\prime}(\gamma(t_{i-1}),\gamma(t_{i}))\leq\frac{1}{\alpha}\cdot\ell^{\prime}(\gamma)$

for all $\alpha\in(0,1)$. Letting $\alpha\to 1$ and taking the supremum of the
left hand side, we obtain that $\ell(\gamma)\leq\ell^{\prime}(\gamma)$, which
concludes the proof. ∎

As a direct corollary, we obtain the following:

######  Corollary 3.2.

Let $(X,d)$ be a geodesic metric space which contains at least two elements,
and $d^{\prime}$ be the metric defined in (1.2). Then the metric space
$(X,d^{\prime})$ is _not_ geodesic.

###### Proof.

By assumption, we take two distinct points $x,y\in X$. If $(X,d^{\prime})$ is
geodesic, we choose a geodesic $\gamma$ between $x$ and $y$. In particular,
$\gamma$ is rectifiable with respect to $d^{\prime}$. Hence by Lemma 3.1, we
know that $\gamma$ is also rectifiable with respect to $d$ and we have

$\ell^{\prime}(\gamma)=\ell(\gamma)\geq d(x,y)>d^{\prime}(x,y),$

where the last inequality follows from the assumption that $x\neq y$. This is
a contradiction to the assumption that $\gamma$ is a geodesic between $x$ and
$y$ with respect to the metric $d^{\prime}$. Hence we conclude the proof. ∎

Moreover, with an extra hypothesis, the new metric $d^{\prime}$ cannot be even
quasi-geodesic.

######  Corollary 3.3.

Let $(X,d)$ be an unbounded geodesic metric space, and $d^{\prime}$ be the
metric defined in (1.2). Then for any $L\geq 1$ and $C\geq 0$, the metric
space $(X,d^{\prime})$ cannot be $(L,C)$-quasi-geodesic.

To prove Corollary 3.3, we need the following lemma to tame quasi-geodesics.
The idea is similar to [1, Lemma III.H.1.11], but the setting is slightly
different.

######  Lemma 3.4.

Let $(X,d)$ be a geodesic metric space and $d^{\prime}$ be the metric defined
in (1.2). Given an $(L,C)$-quasi-geodesic $\gamma:[a,b]\rightarrow X$ with
respect to $d^{\prime}$, there exists a continuous and rectifiable
$(L,C^{\prime})$-quasi-geodesic $\gamma^{\prime}:[a,b]\rightarrow X$ with
respect to $d^{\prime}$ satisfying the following:

  1. (1)

$\gamma^{\prime}(a)=\gamma(a)$ and $\gamma^{\prime}(b)=\gamma(b)$;

  2. (2)

$C^{\prime}=3(L+C)$;

  3. (3)

$\ell^{\prime}(\gamma^{\prime}|_{[t,t^{\prime}]})\leq
k_{1}d^{\prime}(\gamma^{\prime}(t),\gamma^{\prime}(t^{\prime}))+k_{2}$ for all
$t,t^{\prime}\in[a,b]$, where $k_{1}=L(L+C)$ and $k_{2}=(LC^{\prime}+4)(L+C)$;

  4. (4)

$d^{\prime}_{H}(\mathrm{Im}(\gamma),\mathrm{Im}(\gamma^{\prime}))\leq L+C$.

Careful readers might already notice that in the situation of [1, Lemma
III.H.1.11], we need to assume that the _new_ metric $d^{\prime}$ on $X$ is
geodesic instead of the current setting that the _original_ metric $d$ is
geodesic. Although the proof is similar, here we also provide one for
convenience to readers.

###### Proof of Lemma 3.4.

Define $\gamma^{\prime}$ to agree with $\gamma$ on
$\Sigma:=\\{a,b\\}\cup(\mathbb{Z}\cap(a,b))$, then choose geodesic segments
with respect to $d$ joining the images of successive points in $\Sigma$ and
define $\gamma^{\prime}$ by concatenating linear reparameterisations of these
geodesic segments.

Let $[t]$ denote the point of $\Sigma$ closest to $t\in[a,b]$. Note that the
$d^{\prime}$-distance of the images of successive points in $\Sigma$ is at
most $L+C$, and hence we have

$d^{\prime}(\gamma^{\prime}(t),\gamma^{\prime}([t]))=\ln\left(1+d(\gamma^{\prime}(t),\gamma^{\prime}([t]))\right)\leq\ln(1+\exp(L+C)-1)\leq
L+C,$

which implies that
$d^{\prime}_{H}(\mathrm{Im}(\gamma),\mathrm{Im}(\gamma^{\prime}))\leq L+C$.
Since $\gamma$ is an $(L,C)$-quasi-geodesic with respect to $d^{\prime}$, and
$\gamma([t])=\gamma^{\prime}([t])$ for all $t\in[a,b]$, we have

$d^{\prime}(\gamma^{\prime}(t),\gamma^{\prime}(t^{\prime}))\leq
d^{\prime}(\gamma^{\prime}([t]),\gamma^{\prime}([t^{\prime}]))+2(L+C)\leq
L|[t]-[t^{\prime}]|+C+2(L+C)\leq L|t-t^{\prime}|+3(L+C),$

and similarly, we have

(3.1)
$d^{\prime}(\gamma^{\prime}(t),\gamma^{\prime}(t^{\prime}))\geq\frac{1}{L}|t-t^{\prime}|-3(L+C)$

for all $t,t^{\prime}\in[a,b]$. Hence $\gamma^{\prime}$ is an
$(L,C^{\prime})$-quasi-geodesic with respect to $d^{\prime}$.

For any integers $s,s^{\prime}\in\Sigma$ with $s\leq s^{\prime}$, Lemma 3.1
tells us that

$\ell^{\prime}(\gamma^{\prime}|_{[s,s^{\prime}]})=\ell(\gamma^{\prime}|_{[s,s^{\prime}]})=\sum_{k=s}^{s^{\prime}-1}\ell(\gamma^{\prime}|_{[k,k+1]})\leq|s-s^{\prime}|(L+C).$

Similarly for any $s,s^{\prime}\in\Sigma$, we have
$\ell^{\prime}(\gamma^{\prime}|_{[s,s^{\prime}]})\leq(|s-s^{\prime}|+2)(L+C)$.
Hence for any $t,t^{\prime}\in[a,b]$, we have

$\ell^{\prime}(\gamma^{\prime}|_{[t,t^{\prime}]})\leq(|[t]-[t^{\prime}]|+2)(L+C)+(L+C)\leq(|t-t^{\prime}|+4)(L+C).$

Combining with Inequality (3.1), we obtain that
$\ell(\gamma^{\prime}|_{[t,t^{\prime}]})\leq
k_{1}d^{\prime}(\gamma^{\prime}(t),\gamma^{\prime}(t^{\prime}))+k_{2}$ for
$k_{1},k_{2}$ defined in (3). Hence we conclude the proof. ∎

###### Proof of Corollary 3.3.

Assume that $(X,d^{\prime})$ is $(L,C)$-quasi-geodesic for some $L\geq 1$ and
$C\geq 0$. For any $x,y\in X$, choose an $(L,C)$-quasi geodesic
$\gamma:[0,T]\rightarrow X$ (with respect to $d^{\prime}$) connecting them.
Lemma 3.4 implies that there is a rectifiable path
$\gamma^{\prime}:[0,T]\rightarrow X$ which is an $(L,3L+3C)$-quasi-geodesic
(with respect to $d^{\prime}$) connecting $x$ and $y$. Moreover, we have
$\ell^{\prime}(\gamma^{\prime})\leq k_{1}d^{\prime}(x,y)+k_{2}$ for
$k_{1}=L(L+C)$ and $k_{2}=(3L(L+C)+4)(L+C)$. Hence Lemma 3.1 implies that

$k_{1}d^{\prime}(x,y)+k_{2}\geq\ell^{\prime}(\gamma^{\prime})=\ell(\gamma^{\prime})\geq
d(x,y)=\exp(d^{\prime}(x,y))-1.$

Note that $(X,d)$ is unbounded, which implies that $(X,d^{\prime})$ is also
unbounded. Hence taking $d^{\prime}(x,y)\to\infty$, we conclude a
contradiction and finish the proof. ∎

Next, we move to study the relation of the quasi-ball property and the bounded
eccentricity property between the metric spaces $(X,d)$ and $(X,d^{\prime})$.
Again to save the notation, for $x\in X$ and $r\geq 0$, we denote $B(x,r)$ and
$B^{\prime}(x,r)$ the closed balls with respect to the metrics $d$ and
$d^{\prime}$, respectively. For $A\subset X$ and $\delta\geq 0$, we denote
$\mathcal{N}_{\delta}(A)$ and $\mathcal{N}^{\prime}_{\delta}(A)$ the
$\delta$-neighbourhood of $A$ with respect to the metrics $d$ and
$d^{\prime}$, respectively.

######  Lemma 3.5.

Let $(X,d)$ be a metric space and $d^{\prime}$ be the metric on $X$ defined in
(1.2). Then $(X,d)$ has the quasi-ball property _if and only if_
$(X,d^{\prime})$ has the quasi-ball property.

###### Proof.

Firstly, we assume that $(X,d^{\prime})$ has the quasi-ball property, _i.e._ ,
there exists $\delta\geq 0$ such that the intersection of any two balls in
$(X,d^{\prime})$ is $\delta$-close to another ball (_i.e._ , their Hausdorff
distance is bounded by $\delta$). Note that there exists
$\alpha=\alpha(\delta)>1$ such that $x\leq\alpha\ln(1+x)$ for all
$x\in[0,\delta]$. This implies that for $A,B\subseteq X$ with
$A\subseteq\mathcal{N}^{\prime}_{\delta}(B)$, we have
$A\subseteq\mathcal{N}_{\alpha\delta}(B)$.

Given two balls $B(x,s)$ and $B(y,t)$ in $(X,d)$, it is clear that
$B(x,s)=B^{\prime}(x,\ln(1+s))$ and $B(y,t)=B^{\prime}(y,\ln(1+t))$. Hence by
the assumption, there exists another ball $B^{\prime}(c,r)$ in
$(X,d^{\prime})$ such that

$d^{\prime}_{H}\left(B^{\prime}(x,\ln(1+s))\cap
B^{\prime}(y,\ln(1+t)),B^{\prime}(c,r)\right)\leq\delta.$

It follows from the previous paragraph that in this case, we have

$d_{H}\left(B(x,s)\cap
B(y,t),B(c,\exp(r)-1)\right)=d_{H}\left(B^{\prime}(x,\ln(1+s))\cap
B^{\prime}(y,\ln(1+t)),B^{\prime}(c,r)\right)\leq\alpha\delta.$

Hence $(X,d)$ has the quasi-ball property.

The converse holds similarly, using the fact that $\ln(1+x)\leq x$ holds for
all $x\geq 0$. ∎

Combining Lemma 2.3, Corollary 3.3 and Lemma 3.5, we obtain the following,
which concludes part of Theorem 1.2.

######  Corollary 3.6.

Let $(X,d)$ be a geodesic metric space which is not hyperbolic (_e.g._ , the
Euclidean space $\mathbb{R}^{2}$ with the Euclidean metric) and $d^{\prime}$
be the metric on $X$ defined in (1.2). Then $(X,d^{\prime})$ is a non-quasi-
geodesic metric space which satisfies the Gromov’s $4$-point condition but
_not_ the quasi-ball property.

Concerning the bounded eccentricity property, we have the following:

######  Lemma 3.7.

Let $(X,d)$ be a metric space and $d^{\prime}$ be the metric on $X$ defined in
(1.2). If $(X,d)$ satisfies the bounded eccentricity property, so does
$(X,d^{\prime})$.

###### Proof.

Given two balls $B^{\prime}(x,\ln(1+r))$ and $B^{\prime}(y,\ln(1+s))$ in
$(X,d^{\prime})$, we assume that their intersection $Y$ is non-empty. Note
that

$Y=B^{\prime}(x,\ln(1+r))\cap B^{\prime}(y,\ln(1+s))=B(x,r)\cap B(y,s)$

is again an intersection of balls in $(X,d)$. Hence by the assumption, there
exist $c,c^{\prime}\in X$ and $R\geq 0$ such that

$B(c,R)\subseteq Y\subseteq B(c^{\prime},R+\delta_{0}).$

Therefore in $(X,d^{\prime})$, we have

$B^{\prime}(c,\ln(1+R))\subseteq Y\subseteq
B^{\prime}(c^{\prime},\ln(1+R+\delta_{0})).$

Then the eccentricity of $Y$ in $(X,d^{\prime})$ is bounded above by

$\ln(1+R+\delta_{0})-\ln(1+R)=\ln(1+\frac{\delta_{0}}{1+R})\leq\ln(1+\delta_{0})\leq\delta_{0},$

which concludes the proof. ∎

######  Remark 3.8.

Readers might wonder whether the converse to Lemma 3.7 holds. Unfortunately,
in general this is false. Note that if we have

$B^{\prime}(c,\ln(1+R))\subseteq Y\subseteq
B^{\prime}(c^{\prime},\ln(1+R)+\delta_{0})$

in $(X,d^{\prime})$, then it implies that

$B(c,R)\subseteq Y\subseteq B(c^{\prime},\exp(\delta_{0})\cdot(1+R)-1)$

in $(X,d)$. Hence the eccentricity of $Y$ in $(X,d)$ is bounded by
$(\exp(\delta_{0})-1)(1+R)$. However, if $R$ (_i.e._ , the radius of the ball
contained in $Y$) does not have a uniform upper bound, then neither does the
eccentricity of $Y$.

Remark 3.8 suggests the following partial converse to Lemma 3.7:

######  Lemma 3.9.

Let $(X,d)$ be a metric space and $d^{\prime}$ be the metric on $X$ defined in
(1.2). Assume that there exists a sequence of subsets
$\\{Y_{n}\\}_{n\in\mathbb{N}}$ of $X$ satisfying the following:

  1. (1)

each $Y_{n}$ is the intersection of two balls in $(X,d)$;

  2. (2)

there exists $M>0$ such that for all $n\in\mathbb{N}$, the radius (with
respect to $d$) of any ball contained in $Y_{n}$ is bounded above by $M$;

  3. (3)

the eccentricity of $Y_{n}$ in $(X,d)$ is not uniformly bounded.

Then $(X,d^{\prime})$ does _not_ satisfy the bounded eccentricity property.

###### Proof.

Assume the opposite, _i.e._ , there exists $\delta_{0}>0$ such that the
eccentricity of the intersection of any two balls in $(X,d^{\prime})$ is
uniformly bounded by $\delta_{0}$. Hence by condition (1) we know that for
each $n\in\mathbb{N}$, there exist $c_{n},c_{n}^{\prime}\in X$ and $r_{n}\geq
0$ such that

$B^{\prime}(c_{n},\ln(1+r_{n}))\subseteq Y_{n}\subseteq
B^{\prime}(c_{n}^{\prime},\ln(1+r_{n})+\delta_{0}).$

Hence in $(X,d)$, we have

$B(c_{n},r_{n})\subseteq Y_{n}\subseteq
B(c_{n},\exp(\delta_{0})\cdot(1+r_{n})-1).$

By condition (2), we know that $r_{n}\leq M$ for all $n\in\mathbb{N}$.
Therefore, we have

$\exp(\delta_{0})\cdot(1+r_{n})-1-r_{n}=(\exp(\delta_{0})-1)(1+r_{n})\leq(\exp(\delta_{0})-1)(1+M),$

which is a contradiction to condition (3) in the assumption. ∎

######  Example 3.10.

Now we show that there exists a non-quasi-geodesic metric space which
satisfies the Gromov’s $4$-point condition but _not_ the bounded eccentricity
property. For example, take $(X,d)$ to be the Euclidean space $\mathbb{R}^{2}$
equipped with the Euclidean metric, and let $d^{\prime}$ be the metric on $X$
defined in (1.2). Lemma 2.3 and Corollary 3.3 imply that $(X,d^{\prime})$ is
not quasi-geodesic but satisfies the Gromov’s $4$-point condition.

For each $n\in\mathbb{N}$, take $x_{n}=(0,0)$ and $y_{n}=(2n,0)$ and set

$Y_{n}=B(x_{n},n+1)\cap B(y_{n},n+1).$

It is easy to see that in $(X,d)$, the biggest ball contained in $Y_{n}$ is
$B((n,0),1)$. Moreover, the diameter of $Y_{n}$ is

$d\left((n,\sqrt{2n+1}),(n,-\sqrt{2n+1})\right)=2\sqrt{2n+1},$

which implies that the eccentricity of $Y_{n}$ cannot be uniformly bounded.
Therefore applying Lemma 3.9, we conclude the result.

###### Proof of Theorem 1.2.

Combining Corollary 3.6 and Example 3.10, we conclude the proof for Theorem
1.2. ∎

Finally, recall that in [5] the following weaker form of the bounded
eccentricity property was considered: For a metric space $(X,d)$, there exist
$\lambda>0$ and $\delta>0$ such that for any two balls $B_{1},B_{2}\subseteq
X$ with non-empty intersection there exist $z,z^{\prime}\in X$ and $r\geq 0$
such that

$B(z,r)\subseteq B_{1}\cap B_{2}\subseteq B(z^{\prime},\lambda r+\delta).$

Wenger showed in [5] that this condition also implies Gromov’s hyperbolicity
for geodesic metric spaces.

We remark that this weaker form of the bounded eccentricity property does not
hold either for the space $(X,d^{\prime})$ constructed in Example 3.10.

## References

  * [1] Martin R. Bridson and André Haefliger.  Metric Space of Non-Positive Curvature.  Springer-Verlag, Berlin, 1999.
  * [2] Indira Chatterji and Graham A. Niblo.  A characterization of hyperbolic spaces.  Groups Geom. Dyn., 1(3):281–299, 2007.
  * [3] É. Ghys and P. de la Harpe, editors.  Sur les groupes hyperboliques d’après Mikhael Gromov, volume 83 of Progress in Mathematics.  Birkhäuser Boston, Inc., Boston, MA, 1990.
  * [4] M. Gromov.  Hyperbolic groups.  In Essays in group theory, pages 75–263. Springer, 1987.
  * [5] Stefan Wenger.  Characterizations of metric trees and Gromov hyperbolic spaces.  Math. Res. Lett., 15(5):1017–1026, 2008.