11institutetext: University of Alberta 22institutetext: Platform and Content
Group, Tencent
22email<EMAIL_ADDRESS>22email:
<EMAIL_ADDRESS>
# LA3: Efficient Label-Aware AutoAugment

Mingjun Zhao 11 Shan Lu 11 Zixuan Wang 22 Xiaoli Wang and Di Niu 2211

###### Abstract

Automated augmentation is an emerging and effective technique to search for
data augmentation policies to improve generalizability of deep neural network
training. Most existing work focuses on constructing a unified policy
applicable to all data samples in a given dataset, without considering sample
or class variations. In this paper, we propose a novel two-stage data
augmentation algorithm, named Label-Aware AutoAugment (LA3), which takes
advantage of the label information, and learns augmentation policies
separately for samples of different labels. LA3 consists of two learning
stages, where in the first stage, individual augmentation methods are
evaluated and ranked for each label via Bayesian Optimization aided by a
neural predictor, which allows us to identify effective augmentation
techniques for each label under a low search cost. And in the second stage, a
composite augmentation policy is constructed out of a selection of effective
as well as complementary augmentations, which produces significant performance
boost and can be easily deployed in typical model training. Extensive
experiments demonstrate that LA3 achieves excellent performance matching or
surpassing existing methods on CIFAR-10 and CIFAR-100, and achieves a new
state-of-the-art ImageNet accuracy of $79.97\%$ on ResNet-50 among auto-
augmentation methods, while maintaining a low computational cost.

##  1 Introduction

Figure 1: The effects of different augmentation operations on each class in
CIFAR-10, demonstrated by the test accuracy change in each class after each
single augmentation is applied to training WRN-40-2.

Data augmentation has proven to be an effective regularization technique that
can improve the generalization of deep neural networks by adding modified
copies of existing samples to increase the volume and diversity of data used
to train these networks. Traditional ways of applying data augmentation in
computer vision include using single augmentation techniques, such as
rotation, flipping and cutout [4], adopting randomly selected augmentations
[2], and employing a manually crafted augmentation policy consisting of a
combination of transformations. However, these methods either do not reach the
full potential of data augmentation, or require human expertise in policy
design for specific tasks.

Recently, automated learning of augmentation policies has become popular to
surpass the limitation of manual design, achieving remarkable advances in both
the performance and generalization ability on image classification tasks.
Different search algorithms such as reinforcement learning [1], population-
based training [9], and Bayesian Optimization [16] have been investigated to
search effective augmentation policies from data to be used to train target
networks. Dynamic augmentation strategies, e.g., PBA [9], AdvAA [25], are also
proposed to learn non-stationary policies that vary during model training.

However, most existing methods focus on learning a single policy that is
applied to all samples in the dataset equally, without considering variations
between samples, classes or labels, which may lead to sub-optimal solutions.
Figure 1 demonstrates the effects of different augmentation operations on
different classes of samples in CIFAR-10, from which we can see that the
effectiveness of augmentations is different on each class. For example, when
the operation “Posterize” is applied in training, the test accuracy of “dog”
class increases by $3.8\%$, whereas the test accuracy of “cat” drops
significantly by $5\%$. It is possible that a certain augmentation used in
training has completely different impacts on different labels. This
observation implies the limitation of label or sample-invariant dataset-level
augmentation policies. MetaAugment [26] proposes to learn a sample-aware
augmentation policy by solving a sample re-weighting problem. It uses an
augmentation policy network to take an augmentation operation and the
corresponding augmented image as inputs, and outputs a weight to adjust the
augmented image loss computed by the task network. Despite the benefit of a
fine-grained sample-dependent policy, MetaAugment is time-consuming and
couples policy network learning with target model training, which may not be
convenient in some production scenarios that require functional decomposition.

In this paper, we propose an efficient data augmentation strategy named Label-
Aware AutoAugment (LA3), which produces label-aware augmentation policies to
overcome the limitation of sample-invariant augmentation while still being
computationally efficient as compared to sample-aware or dynamic augmentation
strategies. LA3 achieves competitive performance matching or outperforming a
wide range of existing static and dynamic auto-augment methods, and attains
the highest ImageNet accuracy on ResNet-50 among all existing augmentation
methods including dynamic ones. In the meantime, LA3 is also a simple scheme
which separates augmentation policy search from target network model training,
and produces stationary augmentation policies that can easily be applied to
enhance deep learning with minimum perturbation to the original target model
training routine.

LA3 adopts a two-staged design, which first explores a search space of
combinations of operations and evaluates the effectiveness of promising
augmentation operations for each class, while in the second stage, forms a
composite policy to be used in target model training.

In the first stage of LA3, a neural predictor is designed to estimate the
effectiveness of operation combinations on each class and is trained online
through density matching as the exploration process iterates. We use Bayesian
Optimization with a predictor-based sampling strategy to guide search into
meaningful regions, which greatly improves the efficiency and reduces search
cost.

In the second stage, rather than only selecting top augmentation operations,
we introduce a policy construction method based on the minimum-redundancy
maximum-reward (mRMR) principle [17] to enhance the performance of the
composite augmentation policy when applied to the target model. This is in
contrast to most prior methods [1], [16], which simply put together best
performing augmentations in evaluation, ignoring their complementary effects.

Extensive experiments show that using the same set of augmentation operations,
the proposed LA3 achieves excellent performance outperforming other low-cost
static auto-augmentation strategies, including FastAA and DADA, on CIFAR-10
and CIFAR-100, in terms of the accuracy. On ImageNet, LA3, using stationary
policies, achieves a new state-of-the-art top-1 accuracy of $79.97\%$ on
ResNet-50, which outperforms prior auto-augmentation methods including dynamic
strategies such as AdvAA and MetaAug, while being $2\times$ and $3\times$ more
computationally efficient, respectively.

##  2 Related Work

Data augmentation is a popular technique to alleviate overfitting and improve
the generalization of neural network models by enlarging the volume and
diversity of training data. Various data augmentation methods have been
designed, such as Cutout [4], Mixup [24], CutMix [22], etc. Recently,
automated augmentation policy search has become popular, replacing human-
crafted policies by learning policies directly from data. AutoAugment [1]
adopts a reinforcement learning framework that alternatively evaluates a child
model and trains an RNN controller to sample child models to find effective
augmentation policies. Although AutoAugment significantly improves the
performance, its search process can take thousands of GPU hours which greatly
limits its usability.

Multiple strategies are proposed to lower the search cost. Fast AutoAugment
[16] proposes a density matching scheme to avoid training and evaluating child
models, and uses Bayesian Optimization as the search algorithm. Weight-sharing
AutoAugment [18] adopts weight-sharing settings and harvests rewards by fine-
tuning child models on a shared pre-trained target network. Faster AutoAugment
[7] further reduces the search time by making the search of policies end-to-
end differentiable through gradient approximations and targeting to reduce the
distance between the original and augmented image distributions. Similarly,
DADA [15] relaxes the discrete policy selection to a differentiable
optimization problem via Gumbel-Softmax [12] and introduces an unbiased
gradient estimator.

Instead of producing stationary augmentation policies that are consistent
during the target network training, PBA [9] learns a non-stationary
augmentation schedule, inspired by population based training [11], by modeling
the augmentation policy search task as a process of hyperparameter schedule
learning. AdvAA [25] adopts an adversarial framework that jointly optimizes
target network training and augmentation search to find harder augmentation
policies that produce the maximum training loss. However, AdvAA must rely on
the batch augment trick, where each training batch is enlarged by multiple
times with augmented copies, which significantly increases its computational
cost. In general, one concern of these dynamic strategies is that they
intervene the standard model training procedure, causing extra deployment
overhead and may not be applicable in many production environments.

While most previous studies focus on learning augmentation policies for the
entire dataset, MetaAugment [26] proposes to learn sample-aware augmentation
policies during model training by formulating the policy search as a sample
re-weighting problem, and constructing a policy network to learn the weights
of specific augmented images by minimizing the validation loss via meta
learning. Despite its benefits, MetaAugment is computationally expensive,
requiring three forward and backward passes of the target network in each
iteration. LB-Aug [19] is a concurrent work that also searches policies
dependent on labels, but focuses on a different task under multi-label
scenarios, where each sample has multiple labels rather than a single
classification label. LB-Aug uses an actor-critic reinforcement learning
framework and policy gradient approach for policy learning. Despite the
benefits from label-based policies, LB-Aug has potential stability issues due
to the use of reinforcement learning, which is generally harder and
computational costly to train. In fact, the search cost of LB-Aug is not
reported. In contrast, LA3 targets the classical single-label image
classification tasks, e.g., on CIFAR-10/100 and ImageNet benchmarks, on which
most other auto-augmentation methods are evaluated. It adopts Bayesian
Optimization coupled with a neural predictor to sample and search for label-
dependent augmentation policies efficiently. In addition, a policy
construction stage is proposed to further form a more effective composite
policy for target network training.

##  3 Methodology

In this section, we first review the task of conventional augmentation search
and introduce the formulation of the proposed label-aware augmentation search
task. Then we describe the two-stage design of LA3, and present the algorithm
in detail.

###  3.1 Conventional Augmentation Search

Given an image recognition task with a training dataset
$D^{tr}=\\{(x_{i},y_{i}\\}_{i=1}^{|D^{tr}|}$, with $x_{i}$ and $y_{i}$
representing the image and label respectively, augmented samples
$\mathcal{T}(x_{i})$ are derived by applying augmentation policy $\mathcal{T}$
to sample $x_{i}$. Usually, the policy $\mathcal{T}$ is composed of multiple
sub-policies $\tau$, and each sub-policy is made up by $K$ augmentation
operations $O$, optionally with their corresponding probabilities and
magnitudes, which are adopted in the original design of AutoAugment [1], but
not included in some of the recent methods such as Weight-sharing AutoAugment
[18] and MetaAugment [26].

Conventional augmentation search methods focus on the task whose goal is to
construct the optimal policy $\mathcal{T}^{*}$ from given augmentations so
that the performance $\mathcal{R}$ of the task network $\theta_{\mathcal{T}}$
on the validation dataset $D^{\textit{val}}$ is maximized:

$\displaystyle\mathcal{T}^{*}$
$\displaystyle=\operatorname*{arg\,max}_{\mathcal{T}}\mathcal{R}(\theta_{\mathcal{T}}|D^{val}),$
(1) $\displaystyle\text{where}\quad\theta_{\mathcal{T}}$
$\displaystyle=\operatorname*{arg\,min}_{\theta_{\mathcal{T}}}\frac{1}{|D^{tr}|}\sum_{i=1}^{|D^{tr}|}\mathcal{L}_{\theta}(\mathcal{T}(x_{i}),y_{i}),$

and $\mathcal{L}_{\theta}$ is the loss function of target network $\theta$.

Figure 2: An overview of the proposed LA3 method. It contains two stages,
where in the first stage, augmentation triples are individually evaluated for
each label via Bayesian Optimization with the help of an label-aware neural
predictor. In the second stage, the best combination of complementary
augmentation triples is selected based on the minimum-redundancy maximum-
reward principle.

###  3.2 Label-Aware Augmentation Search

Though learning a dataset-level policy achieves considerable improvements, it
is unlikely the optimal solution due to the lack of consideration of sample
variations and utilization of label information.

In this paper, we aim to learn a label-aware data augmentation policy
$\mathcal{T}^{*}=\\{\mathcal{T}^{*}_{y_{0}},\cdots,\mathcal{T}^{*}_{y_{n}}\\}$,
where for samples of each label $y_{j}$, an individual policy
$\mathcal{T}_{y_{j}}$ is learned by maximizing the label-specific performance
$\mathcal{R}_{y_{j}}$ of label $y_{j}$:

$\displaystyle\mathcal{T}^{*}_{y_{j}}$
$\displaystyle=\operatorname*{arg\,max}_{\mathcal{T}_{y_{j}}}\mathcal{R}_{y_{j}}(\theta_{\mathcal{T}}|D^{val}),$
(2) $\displaystyle\text{where}\quad\theta_{\mathcal{T}}$
$\displaystyle=\operatorname*{arg\,min}_{\theta_{\mathcal{T}}}\frac{1}{|D^{tr}|}\sum_{i=1}^{|D^{tr}|}\mathcal{L}_{\theta}(\mathcal{T}_{y_{i}}(x_{i}),y_{i}).$

Similar to conventional augmentation, in our label-aware setting, we define
that each policy for a label is composed of multiple augmentation triples,
each consisting of three augmentation operations. The magnitude of each
augmentation operation is chosen randomly from ranges defined in AutoAugment
[1], and is excluded from the search space in order to introduce randomness
and diversity into the policy, and allocate more computational resources to
assessing the fitness of operations to different classes of samples.

In this paper, we propose a label-aware augmentation policy search algorithm
called LA3, composed of two stages as presented in Figure 2. The first
augmentation exploration stage aims to search for effective augmentation
triples with density matching, and train a neural predictor to provide
evaluations on all seen and unseen augmentation triples in the search space.
And the goal of the second policy construction stage is to build a composite
policy for each label based on the evaluation results from stage 1 by
selecting a subset of complementary augmentation triples based on the minimum-
redundancy maximum-reward principle.

###  3.3 Stage 1: Augmentation Exploration

Density Matching is an efficient mechanism originally proposed by Fast
AutoAugment [16] to simplify the search process for effective augmentations,
since the problem defined by Equation 1 and Equation 2 is a bi-level
optimization problem, and is extremely hard to solve directly. It calculates
the reward of each augmentation triple without the need of repeatedly training
the target network. Specifically, given a model $\theta$ pre-trained on the
training set $D^{tr}$ and a validation set $D^{val}$, the performance of a
certain augmentation triple $\tau$ can be evaluated by approximately measuring
the distance between the density of $D^{tr}$ and density of augmented
validation set $\tau(D^{val})$ with the model performance
$\mathcal{R}(\theta|\tau(D^{val}))$. And the reward $r$ is measured by the
performance difference caused by applying the augmentation triple $\tau$:

$r_{\tau}=\mathcal{R}(\theta|\tau(D^{val}))-\mathcal{R}(\theta|D^{val}).$ (3)

Similarly, in our label-aware setting, the reward $r$ for a certain
augmentation triple $\tau_{y}$ at label $y$ is given by

$r_{\tau,y}=\mathcal{R}_{y}(\theta|\tau_{y}(D^{val}))-\mathcal{R}_{y}(\theta|D^{val}).$
(4)

Bayesian Optimization with a Neural Predictor is a widely adopted framework in
many applications such as neural architecture search [21, 20] to find the
optimal solution within a search space. In standard BO setting, over a
sequence of iterations, the results from previous iterations are used to model
a posterior distribution to guide the candidate selection of next iteration.
And a neural predictor is a neural network that is repeatedly trained on the
history evaluated candidates, and provides evaluations on unseen candidates,
which increases the utilization efficiency of history evaluations and notably
accelerates the search process.

In our LA3 algorithm, we incorporate a label-aware neural predictor
$f(r|\tau,y)$ which takes in an augmentation triple $\tau$ and the label $y$
it is evaluated on, and predicts the reward $r$. In each iteration, the
sampled augmentation triples for different labels are evaluated according to
Equation 4, and together with the previous evaluated augmentation triples, are
passed to train a new predictor.

Input: Pre-trained target network $\theta$, warm up iterations $T_{0}$, total
iterations $T$

Output: Well-trained predictor $f^{T}(r|\tau,y)$

1

/* warm-up phase */

2 for $t=0,\cdots,T_{0}$ do

3 randomly generate augmentation triples
$\\{\tau^{t}_{y_{0}},\cdots,\tau^{t}_{y_{n}}\\}$ for all labels
$\\{y_{0},\cdots,y_{n}\\}$

4 obtain rewards $\\{r_{\tau,y_{0}}^{t},\cdots,r_{\tau,y_{n}}^{t}\\}$ by
Equation 4

5

6

/* search phase */

7 for $t=T_{0},\cdots,T$ do

8 train $f^{t}(r|\tau,y)$ with data collected from previous $t$ iterations
$\\{(\tau,y,r_{\tau,y})\\}^{t}$

9 for $y_{i}=y_{0},\cdots,y_{n}$ do

10 generate $100$ candidate augmentation triples by exploration and
exploitation

11 obtain predicted rewards $\tilde{r}_{\tau,y_{i}}=f^{t}(\tau,y_{i})$ for
$100$ candidates

12 $\tau^{t}_{y_{i}}=\operatorname*{arg\,max}_{\tau}(\tilde{r}_{\tau,y_{i}})$

13

14

15 obtain real rewards
$\\{r_{\tau,{y_{0}}}^{t},\cdots,r_{\tau,{y_{n}}}^{t}\\}$ for
$\\{\tau^{t}_{y_{0}},\cdots,\tau^{t}_{y_{n}}\\}$ by Equation 4

16

17

18train predictor $f^{T}(r|\tau,y)$ with all collected data
$\\{(\tau,y,r_{\tau,y})\\}^{T}$

Algorithm 1 Stage 1: Augmentation Exploration

Next, we select $100$ candidate augmentation triples at the balance of
exploration and exploitation, based on the following selection procedure: 1)
Generate $10$ new candidates by randomly mutating $1$ or $2$ operations in the
chosen augmentation triples of the previous iteration; 2) Randomly sample $50$
candidates from all unexplored augmentation triples; 3) Sample $40$ candidates
from the explored augmentation triples according to their real reward values.
Then, for each label $y$, we choose the augmentation triple $\tau$ with the
highest predicted reward $\tilde{r}_{\tau,y}$ for evaluation.

Overall workflow of the first stage is summarized in Algorithm 1. To begin
with, a warm-up phase of $T_{0}$ iterations is incorporated to randomly
explore the search space, and retrieve the initial training data for learning
a label-aware neural predictor $f(r|\tau,y)$. Then, for the following
$T-T_{0}$ iterations, the search phase is adopted. In each iteration, we first
train a neural predictor from scratch with data collected from previous
iterations. Then, for each label, we apply the fore-mentioned selection
procedure to select a set of candidate augmentation triples, and use the
trained predictor to choose the augmentation triple for evaluation. After
enough training data is collected, a well-trained label-aware neural predictor
can be derived to provide accurate evaluations on all augmentation triples for
different labels.

Input: Well-trained predictor $f^{T}(r|\tau,y)$, search space $A$, number of
candidates $N_{\textit{cand}}$

Output: Label-aware policy $\mathcal{T^{*}}$

1

2for $y_{i}=y_{0},\cdots,y_{n}$ do

3 for $\tau\in A$ do

4 predict the reward $\tilde{r}_{\tau,y_{i}}=f^{T}(\tau,y_{i})$

5

6

7 initialize label-specific policy $\mathcal{T}_{y_{i}}\leftarrow\emptyset$

8 for $k=0,\cdots,N_{\textit{cand}}$ do

9 for $\tau\in(A\setminus\mathcal{T}_{y_{i}})$ do

10 calculate $v(\tau,y_{i})$ using Equation 5

11

12 find augmentation triple with highest score
$\tau^{k}=\operatorname*{arg\,max}_{\tau}(v(\tau,y_{i}))$

13 $\mathcal{T}_{y_{i}}\leftarrow\mathcal{T}_{y_{i}}\cup\tau^{k}$

14

15

16

17$\mathcal{T}^{*}=\\{\mathcal{T}_{y_{0}},\cdots,\mathcal{T}_{y_{n}}\\}$

Algorithm 2 Stage 2: Policy Construction

###  3.4 Stage 2: Policy Construction

Policy construction is a process of mapping the evaluation results of stage 1
to the final augmentation policy for training target networks. It is needed
because augmentation policies are usually searched on light-weight proxy tasks
such as density matching, but are evaluated on the complete tasks of image
classification. Even for methods that search on complete tasks such as
AutoAugment [1], they still naively concatenate multiple searched policies
into a final policy. However, the policies for concatenation usually share a
great potion of overlapped transformations, resulting in a high degree of
redundancy.

In this paper, we propose an effective policy construction method to
iteratively select candidate augmentation triples for the final policy, based
on the mutual information criteria of minimum-redundancy maximum-relevance
(mRMR) [17]. Specifically, in LA3, the relevance metric is defined as the
predicted reward $\tilde{r}$ as it provides a direct evaluation on the
performance of a certain augmentation triple. And the redundancy of an
augmentation triple $\tau$ is defined as the average number of intersecting
operations between it and the already selected augmentation triples
$\mathcal{T}_{s}$. Formally, in each iteration of policy construction, we
define the score $v(\tau,y)$ of each unselected augmentation triple $\tau$ at
label $y$ as

$v(\tau,y)=\tilde{r}_{\tau,y}-\alpha\times\overline{r}\times\frac{1}{|\mathcal{T}_{s}|}\sum_{\tau_{s}\in\mathcal{T}_{s}}|\tau\cap\tau_{s}|,$
(5)

where $|\tau\cap\tau_{s}|$ refers to the number of overlapped operations
between $\tau$ and $\tau_{s}$, $\overline{r}$ is the average predicted reward
of all augmentation triples in search space and is used to scale the
redundancy, and $\alpha$ is a hyper-parameter adjusting the weight between the
reward value and the redundancy value.

Algorithm 2 illustrates the overall process of the policy construction stage
where the goal is to find a label-aware policy containing a collection of
augmentation triples that maximizes the rewards while keeping a low degree of
redundancy. Specifically, for each label $y_{i}$, we retrieve the predicted
reward $\tilde{r}_{\tau,y_{i}}$ for each augmentation triple $\tau$ in the
search space $A$. Afterwards, a label-specific policy $\mathcal{T}_{y_{i}}$ is
constructed iteratively by calculating the score $v(\tau,y_{i})$ of unselected
augmentation triples with Equation 5 and add the augmentation triple with the
highest score to the policy until the required number of candidates
$N_{\text{cand}}$ is met. Eventually, the label-aware policy $\mathcal{T}^{*}$
is built with each label $y_{i}$ corresponding to a label-specific policy
$\mathcal{T}_{y_{i}}$.

##  4 Experiments

In this section, we first describe the details of our experiment settings.
Then we evaluate the proposed method, and compare it with previous methods in
terms of both performance and search cost. Finally, we perform thorough
analysis on the design of different modules in our algorithm. Code and
searched policies are released at https://github.com/Simpleple/LA3-Label-
Aware-AutoAugment.

###  4.1 Datasets, Metrics and Baselines

Following previous work, we evaluate our LA3 method on CIFAR-10/100 [14] and
ImageNet [3], across different networks including ResNet [8], WideResnet [23],
Shake-Shake [5] and PyramidNet [6]. Test accuracy is reported to assess the
effectiveness of the discovered policies, while the cost is assessed by the
number of GPU hours measured on Nvidia V100 GPUs. For a fair comparison, we
list results of stationary policies produced by static strategies, AutoAugment
[1], FastAA [16], and DADA [15]. We also include results from dynamic
strategies, PBA [9], AdvAA [25], and MetaAug [26], producing non-stationary
policies as target model training progresses.

###  4.2 Implementation Details

Policy Composition. For a fair comparison, we use the same $15$ augmentation
operations as PBA and DADA do, which is also the same set used by AA and
FastAA with SamplePairing [10] excluded. Additionally, “Identity” operation
that returns the original image is introduced in our search space to prevent
images from being excessively transformed. Each label-specific policy consists
of $N_{\textit{cand}}=100$ augmentation triples, while in evaluation, each
sample is augmented by an augmentation triple randomly selected from the
policy with random magnitudes.

Neural Predictor. The network structure of the neural predictor is composed of
two embedding layers of size $100$ that map labels and augmentation operations
to latent vectors and three fully-connected layers of hidden size $100$ with
Relu activation function. The representation of an augmentation triple is
constructed by combining the three augmentation operation embedding vectors
with mean-pooling and concatenating it with the label embedding vector. Then
it is passed into the FC layers to derive the predicted reward. The predictor
network is trained for $100$ epochs with Adam optimizer [13] and a learning
rate of $0.01$.

Search Details. For CIFAR-10/100, we split the original training set of
$50,000$ samples into a training set $D^{tr}$ of size $46,000$ to pre-train
the model $\theta$, and a valid set $D^{val}$ of $4,000$ for density matching.
We search our policy on WRN-40-2 network and apply the found policy to other
networks for evaluation. For ImageNet, we randomly sample $50$ examples per
class from the original training set, and collect $50,000$ examples in total
to form the valid set, where the remaining examples are used as the training
set. In the augmentation exploration stage, the total number of iterations is
set to $T=500$, and the warm-up iterations is set to $T_{0}=100$. In the
policy construction stage, $\alpha=2.5$ is used to calculate the reward values
of augmentation triples.

Evaluation. The evaluation is performed by training target networks with the
searched policies, and the results are reported as the mean test accuracy and
standard deviation over three runs with different random seeds. We do not
specifically tune the training hyperparameters and use settings consistent
with prior work. We include the details in the supplementary materials.

Table 1: Top-1 test accuracy (%) on CIFAR-10 and CIFAR-100. We mainly compare
our method LA3 with methods that also produce stationary augmentation
policies, including AA, FastAA and DADA. Results of dynamic policies (PBA,
AdvAA and MetaAug) are also provided for reference.

Dataset | Model | Baseline | AA | FastAA | DADA | LA3 | PBA | AdvAA | MetaAug
---|---|---|---|---|---|---|---|---|---
| static | static | static | static | dynamic | dynamic | dynamic
CIFAR-10 | WRN-40-2 | $94.7$ | $96.3$ | $96.4$ | $96.4$ | $\mathbf{97.08\pm 0.08}$ | $-$ | $-$ | $96.79$
| WRN-28-10 | $96.1$ | $97.4$ | $97.3$ | $97.3$ | $\mathbf{97.80\pm 0.15}$ | $97.42$ | $98.10$ | $97.76$
| Shake-Shake (26 2x96d) | $97.1$ | $98.0$ | $98.0$ | $98.0$ | $\mathbf{98.07\pm 0.11}$ | $97.97$ | $98.15$ | $98.29$
| Shake-Shake (26 2x112d) | $97.2$ | $98.1$ | $98.1$ | $98.0$ | $\mathbf{98.12\pm 0.08}$ | $97.97$ | $98.22$ | $98.28$
| PyramidNet+ShakeDrop | $97.3$ | $98.5$ | $98.3$ | $98.3$ | $\mathbf{98.55\pm 0.02}$ | $98.54$ | $98.64$ | $98.57$
CIFAR-100 | WRN-40-2 | $74.0$ | $79.3$ | $79.4$ | $79.1$ | $\mathbf{81.09\pm 0.28}$ | $-$ | $-$ | $80.60$
| WRN-28-10 | $81.2$ | $82.9$ | $82.8$ | $82.5$ | $\mathbf{84.54\pm 0.03}$ | $83.27$ | $84.51$ | $83.79$
| Shake-Shake (26 2x96d) | $82.9$ | $\mathbf{85.7}$ | $85.4$ | $84.7$ | $85.17\pm 0.13$ | $84.69$ | $85.90$ | $85.97$
| PyramidNet+ShakeDrop | $86.0$ | $\mathbf{89.3}$ | $88.3$ | $88.8$ | $89.02\pm 0.03$ | $89.06$ | $89.58$ | $89.46$

###  4.3 Experimental Results

CIFAR-10/100. Table 1 summarizes the CIFAR-10 and CIFAR-100 results of
different auto-augmentation methods on a wide range of networks. Among all
static methods that produce stationary policies, LA3 achieves the best
performance for all 5 target networks on CIFAR-10 and for 2 out of 4 target
networks on CIFAR-100. When extending the comparison to also include dynamic
strategies, LA3 still achieves the best CIFAR-10 and CIFAR-100 accuracies on
WRN-40-2, which is the original network on which policy search was performed.
When transferring these augmentation policies found on WRN-40-2 to other
target network models for evaluation, LA3 also achieves excellent performance
comparable to the current best methods. In particular, LA3 achieves the
highest score for WRN-28-10 on CIFAR-100. These results evidently proves the
effectiveness of LA3 as an augmentation strategy to improve model performance,
and demonstrates the strong transferability of our label-aware policies across
different neural networks.

ImageNet Performance. In Table 2, we list the top-1 accuracy of different
methods evaluated on ResNet-50, as well as their computational cost. For a
fair comparison, we also indicate whether the Batch Augment (BA) trick [25],
which forms a large batch with multiple copies of transformed samples, is used
for each method, with “(BA)” after the method name. We also indicate the
number of transformations used in the batch augment. Note that the search cost
for dynamic methods is included in the training cost, since they learn a
dynamic augmentation policy during the training of the target model. We
include the results for LA3 both with and without batch augment.

From Table 2 we can observe that among all methods without the batch augment
trick, LA3 achieves the best ImageNet top-1 accuracy of $78.71\%$, while the
search only took $29.3$ GPU hours, which is $15$ times faster than FastAA.
Although DADA is faster, LA3 is substantially better in terms of the ImageNet
accuracy achieved.

Meanwhile, LA3 (BA) achieves a new state-of-the-art ImageNet accuracy of
$79.97\%$ surpassing all existing auto-augmentation strategies including
dynamic strategies AdvAA and MetaAug, with a total computational cost $2$
times and $3$ times lower than theirs, respectively. The high cost of these
dynamic policies is due to the fact that augmentation policies may vary for
each sample or batch and must be learnt together with model training. By
generating static policies, LA3 is a simpler solution that decouples policy
search from model training and evaluation, which is easier to deploy in a
production environment, without introducing specialized structures, e.g., the
policy networks in AdvAA and MetaAug, into target model training.

Table 2: ResNet-50 top-1 test accuracy (%) and computational cost on ImageNet.
Batch Augment (BA) trick is used in the training of LA3 (BA), AdvAA (BA) and
MetaAug (BA). The number of transformations used in batch augment is also
given in the table.

| Baseline | AA | FastAA | DADA | LA3 | LA3 (BA) | AdvAA (BA) | MetaAug (BA)
---|---|---|---|---|---|---|---|---
| static | static | static | static | static | dynamic | dynamic
Batch Augment (BA) | n/a | n/a | n/a | n/a | n/a | $\times 4$ | $\times 8$ | $\times 4$
ResNet-50 Acc (%) | $76.3$ | $77.6$ | $77.6$ | $77.5$ | $\mathbf{78.71\pm 0.07}$ | $\mathbf{79.97\pm 0.07}$ | $79.40$ | $79.74$
Search Cost (h) | $-$ | $15,000$ | $450$ | $1.3$ | $29.3$ | $29.3$ | $-$ | $-$
Train Cost (h) | $160$ | $160$ | $160$ | $160$ | $160$ | $640$ | $1,280$ | $1,920$
Total Cost (h) | $160$ | $15,160$ | $610$ | $161.3$ | $189.3$ | $669.3$ | $1,280$ | $1,920$

###  4.4 Ablation Study and Analysis

The reason of the success can be attributed to the following designs in our
LA3 algorithm.

Label-Awareness. One of the main contributions of the paper is to leverage the
label information and separately learn policies for samples of different
classes, which captures distinct characteristics of data and produces more
effective label-aware policies. The results of LA3 variant without label-
awareness (i.e., searching for label-invariant policies) are shown in the
first row of Table 3, which are constantly lower than LA3 in all experimental
settings. This confirms that label-aware augmentation policies are effective
at improving target network accuracy.

(a) CIFAR-10 policy

(b) CIFAR-100 policy

(c) ImageNet policy

Figure 3: The proportion of different augmentation operations in policies for different labels in LA3 searched label-aware policies on CIFAR-10, CIFAR-100 and ImageNet. Table 3: Ablation analysis results in top-1 test accuracy (%) on CIFAR-10 and CIFAR-100 with different designs removed from the full LA3 method. | CIFAR-10 | CIFAR-100
---|---|---
WRN-40-2 | WRN-28-10 | WRN-40-2 | WRN-28-10
w/o Label-aware | $96.70$ | $97.11$ | $80.08$ | $82.76$
w/o Stage 2 (top-100) | $96.53$ | $97.49$ | $78.57$ | $82.76$
w/o Stage 2 (top-500) | $96.70$ | $97.26$ | $79.85$ | $84.04$
LA3 | $\mathbf{97.08}$ | $\mathbf{97.80}$ | $\mathbf{81.09}$ | $\mathbf{84.54}$

(a) Spearman Correlation

(b) Mean Absolute Error

Figure 4: The evaluation of the predictor during the policy search on ImageNet
given by the Spearman’s Rank Correlation and Mean Absolute Error over search
iterations.

Figure 3 gives an overview of the searched label-aware policies on CIFAR-10,
CIFAR-100 and ImageNet, where we calculate the occurrences of different
operations in each label-specific policy and plot their proportions in
different colors. We can see that the derived policies possess a high
diversity by having all the operations contributing to the final policy,
meanwhile making the individual policies notably different among labels. This
observation further proves the need for separately treating samples of
different labels in augmentation policy search.

Neural Predictor. In addition to using density matching to simplify
augmentation assessment during search, we have adopted a label-aware neural
predictor to learn the mapping from an augmentation triple to its label-
specific reward. We now conduct a thorough evaluation to assess the
performance of the neural predictor. For each search iteration, the predictor
is trained on $80\%$ of the history data and tested on the remaining $20\%$
data in terms of both the Spearman’s Rank Correlation and Mean Abusolute Error
(MAE). As shown in Figure 4, as the policy search on ImageNet progresses and
more samples are explored, the predictor can produce more accurate predictions
of rewards, obtaining a $0.78$ Spearman Correlation and a decreased MAE when
the search ends. This allows the predictor to properly guide the search
process and find effective policies.

Furthermore, the use of the predictor better utilizes the search history and
improves the sample efficiency during searching. As a result, the search cost
of our method is significantly reduced and is $15$ times lower than FastAA.

Policy Construction. We evaluate the impact of our two-stage design on
CIFAR-10 and CIFAR-100 datasets, by showing the performance of model variants
with different policy construction methods in row 2 and 3 of Table 3.

We compare our policy construction method based on mRMR to the commonly used
Top-k selection method adopted in AA [1], FastAA [16] and DADA [15]. We use
two different $k$ value settings of $k=100$ equaling the number of candidates
used in LA3, and $k=500$ following the FastAA setting. We can see that the
policy that includes 500 augmentation triples per label with top predicted
rewards yields a better performance than the policy with top 100 augmentation
triples on both CIFAR-10 and CIFAR-100. This can be attributed to the better
diversity as more possibilities of augmentations are contained. However,
increasing the k value is not the best solution to improve augmentation
diversity as the augmentation triples with high rewards tend to have similar
compositions and may result in a high redundancy in the final policy. Our LA3
incorporates a policy construction method that selects high-reward
augmentation triples, and at the same time, keeping the lowest redundancy of
the final policy. With the two-stage design, our LA3 method beats the top-k
variants and produces significant improvements in all settings.

Limitation. Unlike dataset-level augmentation policies that can be learned
from one dataset and transferred to other datasets [1, 9, 25], LA3 learns
label-aware policies where labels are specific to a dataset, and hence lacks
the transferability across datasets, although LA3 demonstrates transferability
across networks as shown in Table 1. However, when dealing with a large
dataset, LA3 can work on a reduced version of the dataset to search for label-
dependent policies efficiently, and requires no tuning on training recipes
when applying the found policy to the entire dataset.

##  5 Conclusion

In this paper, we propose a label-aware data augmentation search algorithm
where label-specific policies are learned based on a two-stage algorithm,
including an augmentation exploration stage based on Bayesian Optimization and
neural predictors as well as a composite policy construction stage. Compared
with existing static and dynamic augmentation algorithms, LA3 is
computationally efficient and produces stationary policies that can be easily
deployed to improve deep learning performance. LA3 achieves the state-of-the-
art ImageNet accuracy of $79.97\%$ on ResNet-50 among all auto-augmentation
methods, at a substantially lower search cost than AdvAA and MetaAugment.

## References

  * [1] Cubuk, E.D., Zoph, B., Mané, D., Vasudevan, V., Le, Q.V.: Autoaugment: Learning augmentation strategies from data. In: 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 113–123. IEEE (2019)
  * [2] Cubuk, E.D., Zoph, B., Shlens, J., Le, Q.V.: Randaugment: Practical automated data augmentation with a reduced search space. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops. pp. 702–703 (2020)
  * [3] Deng, J., Dong, W., Socher, R., Li, L.J., Li, K., Fei-Fei, L.: Imagenet: A large-scale hierarchical image database. In: 2009 IEEE conference on computer vision and pattern recognition. pp. 248–255. Ieee (2009)
  * [4] DeVries, T., Taylor, G.W.: Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv:1708.04552 (2017)
  * [5] Gastaldi, X.: Shake-shake regularization. arXiv preprint arXiv:1705.07485 (2017)
  * [6] Han, D., Kim, J., Kim, J.: Deep pyramidal residual networks. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 5927–5935 (2017)
  * [7] Hataya, R., Zdenek, J., Yoshizoe, K., Nakayama, H.: Faster autoaugment: Learning augmentation strategies using backpropagation. In: European Conference on Computer Vision. pp. 1–16. Springer (2020)
  * [8] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770–778 (2016)
  * [9] Ho, D., Liang, E., Chen, X., Stoica, I., Abbeel, P.: Population based augmentation: Efficient learning of augmentation policy schedules. In: International Conference on Machine Learning. pp. 2731–2741. PMLR (2019)
  * [10] Inoue, H.: Data augmentation by pairing samples for images classification. arXiv preprint arXiv:1801.02929 (2018)
  * [11] Jaderberg, M., Dalibard, V., Osindero, S., Czarnecki, W.M., Donahue, J., Razavi, A., Vinyals, O., Green, T., Dunning, I., Simonyan, K., et al.: Population based training of neural networks. arXiv preprint arXiv:1711.09846 (2017)
  * [12] Jang, E., Gu, S., Poole, B.: Categorical reparameterization with gumbel-softmax. arXiv preprint arXiv:1611.01144 (2016)
  * [13] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
  * [14] Krizhevsky, A., Hinton, G., et al.: Learning multiple layers of features from tiny images (2009)
  * [15] Li, Y., Hu, G., Hospedales, T., Robertson, N., Yang, Y., et al.: Dada: Differentiable automatic data augmentation. In: European Conference on Computer Vision 2020. Springer (2020)
  * [16] Lim, S., Kim, I., Kim, T., Kim, C., Kim, S.: Fast autoaugment. Advances in Neural Information Processing Systems 32, 6665–6675 (2019)
  * [17] Peng, H., Long, F., Ding, C.: Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy. IEEE Transactions on pattern analysis and machine intelligence 27(8), 1226–1238 (2005)
  * [18] Tian, K., Lin, C., Sun, M., Zhou, L., Yan, J., Ouyang, W.: Improving auto-augment via augmentation-wise weight sharing. Advances in Neural Information Processing Systems 33 (2020)
  * [19] Wang, Y., Chen, H., Zhang, F., Wang, Y., Sun, X., Lin, M., Li, H.: Fine-grained autoaugmentation for multi-label classification. arXiv preprint arXiv:2107.05384 (2021)
  * [20] Wen, W., Liu, H., Chen, Y., Li, H., Bender, G., Kindermans, P.J.: Neural predictor for neural architecture search. In: European Conference on Computer Vision. pp. 660–676. Springer (2020)
  * [21] White, C., Neiswanger, W., Savani, Y.: Bananas: Bayesian optimization with neural architectures for neural architecture search. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 35, pp. 10293–10301 (2021)
  * [22] Yun, S., Han, D., Oh, S.J., Chun, S., Choe, J., Yoo, Y.: Cutmix: Regularization strategy to train strong classifiers with localizable features. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 6023–6032 (2019)
  * [23] Zagoruyko, S., Komodakis, N.: Wide residual networks. In: British Machine Vision Conference 2016. British Machine Vision Association (2016)
  * [24] Zhang, H., Cisse, M., Dauphin, Y.N., Lopez-Paz, D.: mixup: Beyond empirical risk minimization. In: International Conference on Learning Representations (2018)
  * [25] Zhang, X., Wang, Q., Zhang, J., Zhong, Z.: Adversarial autoaugment. In: International Conference on Learning Representations (2019)
  * [26] Zhou, F., Li, J., Xie, C., Chen, F., Hong, L., Sun, R., Li, Z.: Metaaugment: Sample-aware data augmentation policy learning. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 35, pp. 11097–11105 (2021)


marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Integrating processed-based models and machine learning
for crop yield prediction

Michiel G.J. Kallenberg * 1  Bernardo Maestrini * 1  Ron van Bree 1  Paul
Ravensbergen 1  Christos Pylianidis 1  Frits van Evert 1  Ioannis N.
Athanasiadis 1

††footnotetext: *Equal contribution 1Wageningen University & Research, the
Netherlands. Correspondence to: Michiel Kallenberg
<EMAIL_ADDRESS>
Accepted after peer-review at the 1st workshop on Synergy of Scientific and
Machine Learning Modeling, SynS & ML ICML, Honolulu, Hawaii, USA. July, 2023.
Copyright 2023 by the author(s).

###### Abstract

Crop yield prediction typically involves the utilization of either theory-
driven process-based crop growth models, which have proven to be difficult to
calibrate for local conditions, or data-driven machine learning methods, which
are known to require large datasets. In this work we investigate potato yield
prediction using a hybrid meta-modeling approach. A crop growth model is
employed to generate synthetic data for (pre)training a convolutional neural
net, which is then fine-tuned with observational data. When applied in silico,
our meta-modeling approach yields better predictions than a baseline
comprising a purely data-driven approach. When tested on real-world data from
field trials (n=303) and commercial fields (n=77), the meta-modeling approach
yields competitive results with respect to the crop growth model. In the
latter set, however, both models perform worse than a simple linear regression
with a hand-picked feature set and dedicated preprocessing designed by domain
experts. Our findings indicate the potential of meta-modeling for accurate
crop yield prediction; however, further advancements and validation using
extensive real-world datasets is recommended to solidify its practical
effectiveness.

##  1 Introduction

Crop yield prediction plays an important role in ensuring food security,
optimizing agricultural practices, and managing risks in the farming industry.
By accurately estimating the expected crop yields, stakeholders ranging from
farmers and policymakers to traders and researchers can make informed
decisions and take proactive measures. In a world facing increasing population
growth and climate uncertainties, the ability to predict crop yields has
become indispensable for addressing global food challenges and fostering
sustainable agricultural practices.

In crop yield prediction, theory-driven process-based crop models and data-
driven machine learning models are usually seen as opposite approaches Leng &
Hall (2020); Paudel et al. (2022); Maestrini et al. (2022). In this work, we
investigate the use of a meta-modeling approach to combine the best of these
two worlds. The integration of the two approaches may help overcome their
individual approach limitations, for process-based models the limited
processes included in the model van Ittersum et al. (2013), and their
difficulty in adapting to local conditions, and for data-driven models the
need for large, variable and orthogonal datasets, that are often unavailable
in the agricultural context.

One common method of integrating data-driven and process-based approaches is
through the development of a metamodel Wallach et al. (2019); Pylianidis et
al. (2022). The workflow to create a metamodel is typically the following: a
synthetic dataset is created using a process-based model fed with different
inputs representative for the conditions where the model will be used, and
then a data-driven model is fit on the synthetic dataset Razavi et al. (2012);
Pylianidis et al. (2022). Usually only a subset of the input (e.g. weather,
management, soil texture) and a subset of the output (e.g. yield, or yield and
leached N) is retained in the metamodel.

To align model predictions with local conditions, crop yield prediction using
process-based crop growth models approaches typically involves a tedious
calibration process Seidel et al. (2018). Calibration of these models can be
challenging due to the complexity of cropping systems, spatial and temporal
variability, limited data availability, and parameter sensitivity. Calibrating
a data-driven method is often considered easier compared to calibrating a
process-based model. For data-driven models transfer learning techniques, such
as fine-tuning, can be leveraged to adapt a generic model to local conditions.

Figure 1: Schematic overview of experimental setup, data flow and model
development

In this work, we compare three methods for predicting potato yield, quantified
as fresh tuber weight at harvest time: (1) a process based crop growth model,
in our case Tipstar Jansen (2008) (2) a (fine-tuned) metamodel, pretrained
with synthetic data generated by Tipstar, and (3) a purely data-driven model,
not (pre)trained with Tipstar.

##  2 Materials and methods

A schematic overview of the experimental setup, data flow and model
development is shown in Figure 1.

###  2.1 Models

####  2.1.1 Process-based crop growth model

Tipstar Jansen (2008) is a crop growth model that simulates potato growth
under water and nitrogen limited conditions with daily time steps. The input
to the model are crop management (planting, fertilization, and irrigation),
weather (solar radiation, rainfall, maximum and minimum air temperature,
wind), and soil characteristics (texture, organic matter percentage, van
Genuchten parameters van Genuchten (1980)). The model was not calibrated for
this specific setup (i.e., no model parameters were adjusted to fit the data
of this study), but we re-used default parameters that were derived from
historical data from the same country (i.e., the Netherlands).

####  2.1.2 Metamodel

We developed a metamodel of Tipstar by creating a synthetic dataset of 86,000
entries, which was then used to pretrain a convolutional neural network. The
synthetic dataset was created by taking the full factorial of the model inputs
weather (7 locations, 32 years) and soil (32 soil types Wosten et al. (2013)).
For each of the resulting 7,168 combinations we generated 12 simulations using
random sampling while varying the following model inputs: nitrogen
fertilization, sowing date, irrigation, maximum rooting depth, and cultivar
earliness.

The metamodel was constructed as a multi-stream (n=3) convolutional neural
network. The first stream processed the temporal data (i.e. solar radiation,
rainfall, maximum and minimum air temperature, cumulative irrigation and
cumulative nitrogen input) with twice a 1D convolution (number of filters 20
and 7, kernel sizes 3 and 2) followed by an average pooling (5 and 5). The
second stream processes the scalars (i.e. maximum rooting depth, sowing day of
year and cultivar earliness) with two dense layers (20, and 20). The
(optional) third stream processes the soil characteristics (i.e., clay, loam,
organic matter percentage, soil moisture at saturation, and the Van Genuchten
parameters: $\alpha$, $\lambda$ and $n$ van Genuchten (1980)) with a 1D
convolution (number of filers 5, kernel size 5) followed by an average pooling
(24). The three streams are all flattened and concatenated, and subsequently
fed to three dense layers (25, 5 and 1).

####  2.1.3 Data-driven model

As a baseline for our model comparisons we trained a purely data-driven model.
This model was not pretrained with synthetic data, but was trained with
observational data. The model had the same architecture as the metamodel.

(Pre)training of the metamodel and the data-driven model was done with mean
squared error (MSE) as a loss function. We used the ADAM optimizer with an
initial learning rate of 0.001. Training was monitored on an hold-out
validation set. To prevent overfitting, we used early stopping
(min_delta=0.001, patience=20), and learning rate reduction (factor=0.5,
min_delta=0.001, patience=10).

###  2.2 Experiments

We conducted two experiments to investigate the merits of our meta-modeling
approach.

####  2.2.1 Transfer learning on synthetic data

The first experiment served as a proof-of-concept of our transfer learning
approach, and was done with synthetic data only. We selected ”soil” as our
domain of interest, since, in general, potato yield depends substantially on
the characteristics of the soil Porter et al. (1999). We divided the synthetic
dataset in two subsets; the first set (i.e., source domain) contained the
simulations on peat soils (category 2xx in BOFEK 2012 Wosten et al. (2013))
and the second (i.e., target domain) the sandy soils (category 3xx in BOFEK
2012 Wosten et al. (2013)). We confirmed that yields differed between the two
soil types, which was found to be partially caused by a different yield
response to water availability.

A metamodel (excluding the soil input stream) was pretrained on the peat soil
dataset (n=10k), and then fine-tuned with the sandy soil dataset. For the
fine-tuning we chose to freeze all layers of the network, except for the last
two layers, as this approach yielded slightly superior results compared to
alternatives such as training all layers, and training the first layers only.
For comparison, we trained a data-driven model with the same architecture of
the metamodel. The data-driven model was exclusively trained with the sandy
soil dataset. Both models were evaluated on a hold-out set (n=17k) with sandy
soils.

Transfer learning is especially instrumental in cases where there is a limited
availability of data from the target domain. We simulated such a scenario by
limiting the size of the dataset available for fine-tuning; we evaluated three
different levels of size n=50, 200, and 1000 respectively.

####  2.2.2 Yield prediction on real-world data

The second experiment was done with two real-world datasets; one from field
trials and one from commercial fields. The field trial dataset (n=303,
1994-2003) came from a collection of 36 potato experiments carried out by
Wageningen University and Research. The factors that were varied in the
experiments were cultivar, nitrogen fertilization rates and timings,
irrigation rates and timings, sowing date, and planting density. The field
trials were conducted under well-controlled conditions, with e.g. effective
pest management. The commercial field dataset (n=77, 2015-2020) was collected
from an arable farm located near Wageningen University and Research. As the
primary focus of the commercial cultivation was profit rather than scientific
research, crop management was carried out based on standard practices aiming
to achieve an optimal balance between yield and costs.

A metamodel was pretrained on the synthetic dataset, and subsequently fine-
tuned with the observational dataset. To prevent data leakage, we excluded the
years in which the experiments of the potato trials dataset were performed
from the synthetic dataset. For comparison, we trained a data-driven model
with the same architecture of the metamodel. Because the observational dataset
was relatively modest in size, we used leave-one-out cross-validation for
model development and testing. As weather is a major determinant of final
yield, we used weather years as criteria for the splits. To assess the
stability of the training, we replicated the trainings three times using
different random seeds.

As an additional baseline, representing one of the most commonly used data-
driven approaches in yield prediction, we trained a simple linear regression
model with a hand-picked feature set (i.e. earliness, sowing date,
precipitation, and average daily temperature) selected by domain experts. The
time series variables (i.e., precipitation, and average daily temperature)
were preprocessed by averaging over the period from May-August.

##  3 Results

We (pre)trained a metamodel for potato yield prediction, using synthetic data
obtained from the process-based crop growth model Tipstar. The obtained
metamodel was able to reproduce Tipstar with an RMSE of 5.1 fresh tonne/ha and
$r=0.95$ on a hold-out set (n=13,000) (see Fig.2).

Figure 2: Fitness of the metamodel on the (hold-out) synthetic dataset
(n=13,000; RMSE=5.1, black

$r=0.95$)

###  3.1 Transfer learning on synthetic data

In our first experiment we investigated the merits of incorporating fine-
tuning in the training process of our metamodel, to cover for domain shifts.
As an alternative approach we included a purely data-driven baseline that was
not pretrained with the crop growth model.

Table 1: Model performance as function of fine-tuning set size metric | model | fine-tuning set size
---|---|---
|  | 0a | 50 | 200 | 1,000
$r$ | Metamodel | 0.884 | 0.899 | 0.905 | 0.908
|  Data-drivenb | N/A | 0.767 | 0.790 | 0.902
RMSE | Metamodel | 10.3 | 7.6 | 7.4 | 7.2
|  Data-drivenb | N/A | 11.2 | 11.0 | 7.5
aExclusively pretrained (on source domain)
bExclusively trained on fine-tuning set

Table 1 reports on the performance of the models as function of the fine
tuning set size. When target domain data availability is limited, best results
are obtained with the fine-tuned metamodel. These results indicate that (1)
fine-tuning improves the performance of a pretrained metamodel, and (2)
pretraining with synthetic data obtained from a processed based crop model is
effective, even when that data is collected from a source domain that differs
from the target domain.

###  3.2 Yield prediction on real-world data

In our second experiment we evaluated our metamodel approach on real-world
data.

Figure 3: Fitness of the crop growth model and the metamodel on the field
trial set (n=303). The number in parentheses represents the standard deviation
of the three replicates of the metamodel trainings.

Figures 3 and 4 show scatter plots of the predicted and the observed yields
for both the crop growth model and the metamodel on the field trial set
(n=303), and the commercial field set (n=77), respectively. In general,
predictions of both models are better in the field trial set than in the
commercial field set. While for the field trial set the predictions of the
crop growth model are, on average, in line with the observed yields, for the
commercial fields the crop growth model systematically underestimates the
yield. This emphasizes the necessity of calibrating a crop growth model prior
to its application to real-world data. The (fine-tuned) metamodel, on the
contrary, exhibits no systematic bias, in either sets. Yet, the metamodel, has
a relatively high scatter.

Figure 4: Fitness of the crop growth model and the metamodel on the commercial field set (n=77). The number in parentheses represents the standard deviation of the three replicates of the metamodel trainings. Table 2: Model performance on real-world datasets metric | model | Trial | Commercial
---|---|---|---
$r$ | Crop growth model | 0.70 | 0.63
| Metamodel | 0.60 | 0.39
| Data-driven | 0.02 | 0.35
| Linear regression | 0.64 | 0.72
RMSE | Crop growth model | 12.98 | 24.90
| Metamodel | 9.40 | 14.10
| Data-driven | 15.80 | 14.10
| Linear regression | 8.93 | 9.75

As a reference, we trained a purely data-driven model (i.e., we did not use
the crop growth model for pretraining), with the same architecture of the
metamodel. With an RMSE=15.80, and r=0.02 on the field trial set, and
RMSE=14.10, and r=0.35 on the commercial set, the purely data-driven model
showed poor performance. Arguably the complexity of the model was excessive
considering the limited number of available training samples. We also trained
a significantly less complex model, specifically a linear regressor, for which
the feature set was hand picked by domain experts, with dedicated
preprocessing. This model yielded an RMSE=8.93, and r=0.64 on the field trial
set, and RMSE=9.75, and r=0.72 on the commercial field set, outperforming both
the crop growth model and the metamodel on the latter dataset.

##  4 Discussion and conclusion

In this work, we investigated potato yield prediction using a meta-modeling
approach that integrates a theory-driven process-based crop growth model into
a data-driven machine learning method. We found that, in silico, our metamodel
yields better predictions than a purely data-driven approach. When tested on
real-world data, comprising a field trial set and a commercial field set, the
metamodel yields competitive results with respect to the crop growth model. In
the latter set, which was characterized by a small sample size, however, a
simple linear regression model with a hand-picked feature set, representing
one of the most commonly used data-driven approaches in yield prediction,
outperformed both the crop growth model and the metamodeling approach.

Our results indicate a benefit of pretraining a machine learning model with
synthetic data obtained from a crop growth model, rather than using real-world
data only. In our in silico experiments, pretrained models fine-tuned with
only 50 data points had similar performance to data-driven models using 1,000
data points. This is important for data poor domains as agriculture. Also,
training data exclusively obtained from a real-world setting may lack
important contrasts in the input space, as, for example, especially in
commercial settings, management practices are typically standardised. In this
context, employing synthetic data may be seen as a data augmentation strategy
that prevents the model from exploiting spurious features, which is especially
relevant in models with high complexity. Model over-complexity combined with a
small, low-contrast training set, may be one of the reasons why our purely
data driven model did not perform well in the real-world datasets. Pretraining
our model with synthetic data turned out to be a successfully strategy. It
should be noted though that a simple approach, using an expert designed,
regression model may still be preferred in a real-world setting.

We conclude that meta-modeling has potential for accurate crop yield
prediction, yet further development and validation on large real-world
datasets is recommended.

##  5 Impact

Predicting crop yields is crucial for ensuring food security, optimizing
agricultural practices, and managing risks in the farming industry. In crop
yield prediction, theory-driven process-based crop models and data-driven
machine learning models are usually seen as opposite approaches. In this work,
we explore the utilization of a meta-modeling approach that combines the
strengths of both these approaches. By integrating these two methods, we aim
to overcome their respective limitations. Process-based models often suffer
from a restricted set of included processes, while data-driven models rely on
large, diverse, and independent datasets that are often scarce in the
agricultural domain. Our findings suggest the potential of meta-modeling for
accurate crop yield prediction, and may as such facilitate the uptake of
machine learning in agriculture.

## Acknowledgements

We are grateful to three anonymous reviewers for their insightful comments.
This work was partially supported by the Dutch Ministry of Agriculture, Nature
and Food Quality project Data driven and High Tech (KB-38-001-002), the
Wageningen University and Research Investment Theme Digital Twins, and the
European Union Horizon Research and Innovation program (Grant #101070496,
Smart Droplets).

## References

  * Jansen (2008) Jansen, D.  _Beschrijving van TIPSTAR : hét simulatiemodel voor groei en productie van zetmeelaardappelen_.  Number 547 in Nota / Plant Research International. Plant Research International, Netherlands, 2008.
  * Leng & Hall (2020) Leng, G. and Hall, J. W.  Predicting spatial and temporal variability in crop yields: an inter-comparison of machine learning, regression and process-based models.  _Environmental Research Letters_ , 15(4):044027, 2020.  doi: 10.1088/1748-9326/ab7b24.
  * Maestrini et al. (2022) Maestrini, B., Mimić, G., van Oort, P. A. J., Jindo, K., Brdar, S., Athanasiadis, I. N., and van Evert, F. K.  Mixing process-based and data-driven approaches in yield prediction.  _European journal of agronomy: the journal of the European Society for Agronomy_ , 139:126569, 2022.  doi: 10.1016/j.eja.2022.126569.
  * Paudel et al. (2022) Paudel, D., Boogaard, H., de Wit, A., van der Velde, M., Claverie, M., Nisini, L., Janssen, S., Osinga, S., and Athanasiadis, I. N.  Machine learning for regional crop yield forecasting in Europe.  _Field crops research_ , 276:108377, 2022.  doi: 10.1016/j.fcr.2021.108377.
  * Porter et al. (1999) Porter, G. A., Bradbury, W. B., Sisson, J. A., Opena, G. B., and McBurnie, J. C.  Soil management and supplemental irrigation effects on potato: I. soil properties, tuber yield, and quality.  _Agronomy Journal_ , 91(3):416–425, 1999.  doi: 10.2134/agronj1999.00021962009100030010x.
  * Pylianidis et al. (2022) Pylianidis, C., Snow, V., Overweg, H., Osinga, S., Kean, J., and Athanasiadis, I. N.  Simulation-assisted machine learning for operational digital twins.  _Environmental Modelling and Software_ , 148:105274, 2022\.  doi: 10.1016/j.envsoft.2021.105274.
  * Razavi et al. (2012) Razavi, S., Tolson, B. A., and Burn, D. H.  Review of surrogate modeling in water resources.  _Water Resources Research_ , 48(7):W07401, 2012\.  doi: 10.1029/2011WR011527.
  * Seidel et al. (2018) Seidel, S. J., Palosuo, T., Thorburn, P., and Wallach, D.  Towards improved calibration of crop models–where are we now and where should we go?  _European Journal of Agronomy_ , 94:25–35, 2018.
  * van Genuchten (1980) van Genuchten, M. T.  A closed-form equation for predicting the hydraulic conductivity of unsaturated soils.  _Soil Science Society of America Journal_ , 44(5):892–898, 1980.  doi: 10.2136/sssaj1980.03615995004400050002x.
  * van Ittersum et al. (2013) van Ittersum, M. K., Cassman, K. G., Grassini, P., Wolf, J., Tittonell, P., and Hochman, Z.  Yield gap analysis with local to global relevance—a review.  _Field Crops Research_ , 143:4–17, 2013.  doi: 10.1016/j.fcr.2012.09.009.
  * Wallach et al. (2019) Wallach, D., Makowski, D., Jones, J. W., and Brun, F.  Chapter 11 - Metamodeling.  In Wallach, D., Makowski, D., Jones, J. W., and Brun, F. (eds.), _Working with Dynamic Crop Models (Third Edition)_ , pp. 407–423. Academic Press, 3rd edition, 2019.  doi: 10.1016/B978-0-12-811756-9.00011-3.
  * Wosten et al. (2013) Wosten, J., de Vries, F., Hoogland, T., Massop, H., Veldhuizen, A., Vroon, H., Wesseling, J., Heijkers, J., and Bolman, A.  BOFEK2012, de nieuwe bodemfysische schematisatie van Nederland.  Technical report, Alterra, 2013.


Eindhoven University of Technology, The Netherlands and
https://www.win.tue.nl/
bjansen/b.m.p.jansen@tue.nlhttps://orcid.org/0000-0001-8204-1268 Eindhoven
University of Technology, The Netherlands and
https://sites.google.com/view/shiveshroys.k.roy@tue.nlhttps://orcid.org/0000-0003-0896-3437
Bart M. P. Jansen, and Shivesh K. Roy This project has received funding from
the European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement No 803421, ReduceSearch). 1
42nd Conference on Very Important Topics (CVIT 2016) CVIT 20XX CVIT 20xx 20xx
42 23 ¡ccs2012¿ ¡concept¿
¡concept_id¿10002950.10003624.10003633.10010917¡/concept_id¿
¡concept_desc¿Mathematics of computing Graph algorithms¡/concept_desc¿
¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿
¡concept_id¿10003752.10003809.10010052¡/concept_id¿ ¡concept_desc¿Theory of
computation Parameterized complexity and exact algorithms¡/concept_desc¿
¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿
¡concept¿ ¡concept_id¿10003752.10003809.10003636¡/concept_id¿
¡concept_desc¿Theory of computation Approximation algorithms
analysis¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿
¡/concept¿ ¡/ccs2012¿ [500]Mathematics of computing Graph algorithms
[500]Theory of computation Parameterized complexity and exact algorithms
[300]Theory of computation Approximation algorithms analysis

# On the Parameterized Complexity of Multiway Near-Separator

Bart M.P. Jansen Shivesh K. Roy

###### Abstract

We study a new graph separation problem called Multiway Near-Separator. Given
an undirected graph $G$, integer $k$, and terminal set $T$, it asks whether
there is a vertex set $S\subseteq V(G)\setminus T$ of size at most $k$ such
that in graph $G-S$, no pair of distinct terminals can be connected by two
pairwise internally vertex-disjoint paths. Hence each terminal pair can be
separated in $G-S$ by removing at most one vertex. The problem is therefore a
generalization of (Node) Multiway Cut, which asks for a vertex set for which
each terminal is in a different component of $G-S$. We develop a fixed-
parameter tractable algorithm for Multiway Near-Separator running in time
$2^{\mathcal{O}(k\log k)}\cdot n^{\mathcal{O}(1)}$. Our algorithm is based on
a new pushing lemma for solutions with respect to important separators, along
with two problem-specific ingredients. The first is a polynomial-time
subroutine to reduce the number of terminals in the instance to a polynomial
in the solution size $k$ plus the size of a given suboptimal solution. The
second is an algorithm that, given a graph $G$ and terminal set $S\subseteq
V(G)$ along with a single vertex $x\in V(G)$ that forms a multiway near-
separator, computes a 14-approximation for the problem of finding a multiway
near-separator not containing $x$.††margin:  $\bullet$ Maybe also write
something related to the construction of blocker here.done

###### keywords:

FPT algorithm

###### category:

###### keywords:

fixed-parameter tractability, multiway cut, near-separator

††margin:  $\bullet$ How to hide author names for the submission apart from
commenting them outDone; it works by adding ’anonymous’ to the parameters of
the documentclass command ††margin:  $\bullet$ ACM Subject classification and
KeywordsDone ††margin:  $\bullet$ Note for Shivesh: you can turn off all
todo’s and colors by commenting out the line that defines DEBUG, currently on
line number 54. Make sure to do it before submitting.

##  1 Introduction

Graph separation problems play an important role in the study of graph
algorithms. While the problem of finding a minimum vertex set whose removal
separates two terminals $s$ and $t$ can be solved in polynomial-time via the
Ford-Fulkerson algorithm, many variations of the problem are NP-complete. They
form a fruitful subject of investigation in the study of parameterized
algorithmics, where a typical goal is to develop an algorithm that finds a
suitable separator of size $k$ in an $n$-vertex input graph in time $f(k)\cdot
n^{\mathcal{O}(1)}$, or concludes that no such solution exists. Landmark
results in this area include the FPT algorithms for Multiway Cut [ChenLL09,
CyganPPW13a, Guillemot11a, Marx06, Xiao10] (in which the goal is to find a
vertex set which separates any pair of terminals from a given set $T$) and
Multicut [BousquetDT18, MarxR14] (in which only a specified subset of the
terminal pairs must be separated) in undirected graphs.

After the parameterized complexity of the most fundamental separation problems
in this area were settled, researchers started considering variations on the
theme of graph separation, including Steiner Multicut [BringmannHML16] (given
a sequence of subsets of terminals $T_{1},\ldots,T_{\ell}$, find a vertex set
separating at least one pair $\\{t_{i}\in T_{i},t_{j}\in T_{j}\\}$ for each
$i\neq j$), Multiway Cut-Uncut [ChitnisCHPP16, LokshtanovR0Z18] (given an
equivalence relation $\mathcal{R}$ on a set of terminal vertices, find a
vertex set whose removal leaves terminals $t_{i},t_{j}$ in the same connected
component if and only if $t_{i}\equiv_{\mathcal{R}}t_{j}$), and Stable
Multiway cut [MarxOR13] (find a multiway cut inducing an independent set).

In this paper we start to explore a new variation of the ††margin:  $\bullet$
Does it sound better when we ignore ”variation of the”? separation theme,
which to the best of our knowledge has not been considered before. Rather than
asking for a vertex set which fully separates some given terminal pairs, we
are interested in _nearly_ separating terminals: in the remaining graph, there
should not be _two or more_ internally vertex-disjoint paths connecting a
terminal pair. This setting is inspired by the well-studied Planar Vertex
Deletion problem [Jansen022, Kawarabayashi09, KociumakaP19, MarxS12] of making
a graph planar by a minimum number of vertex deletions. To planarize a graph,
it may be helpful to reduce the connectivity between certain vertex sets
without separating them completely, since the embedding of a planar graph can
be updated by ‘rotating’ around a cut vertex. We therefore study the following
problem.

Multiway Near-Separator (mwns) Parameter: $k$ Input: An undirected graph $G$,
terminal set $T\subseteq V(G)$, and a positive integer $k$. Question: Is there
a set $S\subseteq V(G)\setminus T$ with $|S|\leq k$ such that there does not
exist a pair of distinct terminals $t_{i},t_{j}\in T$ with _two_ internally
vertex-disjoint $t_{i}$-$t_{j}$ paths in $G-S$?

Note that the requirement that in $G-S$ there does not exist two internally
vertex-disjoint paths between any pair of distinct terminals, is equivalent to
demanding that $T$ is an independent set and there is no simple cycle
containing at least two vertices from $T$. Simple cycles containing two
vertices from $T$, henceforth called $T$-cycles, therefore play an important
role in our arguments. Based on this alternative characterization, the near-
separator problem is related to the Subset Feedback Vertex Set problem, which
asks for a minimum vertex set intersecting all cycles that contain at least
one terminal [CyganPPW13], although there the solution is allowed to contain
terminal vertices.

A simple reduction (Claim LABEL:Claim:NP-hardness_proof_of_MWNS) shows that
Multiway Near-Separator is NP-complete. It forms a generalization of the
(Node) Multiway Cut problem with undeletable terminals: an instance
$(G,T=\\{t_{1},\ldots,t_{\ell}\\},k)$ of the latter problemcan be reduced to
an equivalent instance $(G^{\prime},T,k)$ of mwns by inserting $|T|-1$ new
non-terminal vertices $w_{1},\ldots,w_{|T|-1}$ with
$N(w_{i})=\\{t_{i},t_{i+1}\\}$.

The Multiway Near-Separator problem can be shown to be non-uniformly fixed-
parameter tractable parameterized by $k$ using the technique of recursive
understanding [LokshtanovR0Z18], as the problem can be formulated in Monadic
Second-Order Logic and can be shown to become fixed-parameter tractable on
$(s(k),k+1)$-unbreakable graphs by branching on small connected vertex sets
with small neighborhoods. This only serves as a complexity classification,
however, as the resulting algorithms are non-uniform and have a large (and
unknown) parameter dependence $f(k)$. In this paper, our goal is to understand
the structure of Multiway Near-Separator and develop an efficient (and
uniform) parameterized FPT algorithm for the problem.

### Our results

The main result of our paper is the following theorem, showing that mwns has a
uniform FPT algorithm with parameter dependence $2^{\mathcal{O}(k\log k)}$.

theoremMWNSIsFPTState $(\bigstar)$ Multiway Near-Separator can be solved in
time $2^{\mathcal{O}(k\log k)}\cdot n^{\mathcal{O}(1)}$.

The starting point for the algorithm is the approach for solving Multiway Cut
via important separators. The _pushing lemma_ due to Marx [Marx06]
[CyganFKLMPPS15, Lemma 8.53] states that for any instance $(G,T,k)$ of
Multiway Cut and any choice of terminal $t\in T$, there is an optimal solution
which contains an _important_ $(t,T\setminus\\{t\\})$-separator. As the number
of important separators of size at most $k$ is bounded by $4^{k}$, we can
construct a solution by picking an arbitrary terminal which is not yet fully
separated from the remaining terminals and branching on all choices of
including a $(t,T\setminus\\{t\\})$-separator in the solution.

Adapting this strategy directly for Multiway Near-Separator fails for several
reasons. Most importantly, since terminal pairs are allowed to remain in the
same connected component, it is possible that in an instance with a solution
$S$ of size $k$, there exists a terminal $t\in T$ for which there are no
$(t,T\setminus\\{t\\})$-separators of size $f(k)$ for any function $f$. This
happens when such a terminal $t$ is located in a ‘central’ block in the block-
cut tree of $G-S$. However, there always exists a terminal $t^{\prime}\in T$
for which there does exist a
$(t^{\prime},T\setminus\\{t^{\prime}\\})$-separator of size at most $k+1$, and
for which furthermore a variation of the pushing lemma can be proven: there is
an optimal solution which contains all-but-one vertex of an important
$(t^{\prime},T\setminus\\{t^{\prime}\\})$-separator of size at most $k+1$.
Intuitively, such a terminal $t^{\prime}$ can be found in a leaf block of the
block-cut tree of $G-S$. Hence there _exists_ a terminal for which branching
on important separators can make progress in identifying the solution, but not
all terminals have this property and a priori it is not clear which is the
right one.

To resolve this issue, we will effectively have the algorithm try all choices
for the terminal $t$ which is near-separated from all other terminals by an
important separator. To ensure the branching factor of the resulting algorithm
is bounded in terms of the parameter $k$, while the number of terminals $T$
may initially be arbitrarily large compared to $k$, we therefore have to
reduce the number of terminals to $k^{\mathcal{O}(1)}$ in a preprocessing
phase.

For the standard Multiway Cut problem, a preprocessing step based on the
linear-programming relaxation of the problem can be used to reduce the number
of terminals to $2k$ [CyganPPW13a] (cf. [Razgon11]). For the near-separation
variant we consider, it seems unlikely that the linear-programming relaxation
has the same nice properties (such as half-integrality) as for the original
problem, let alone that the resulting fractional solutions are useful for a
reduction in the number of terminals. As one of our main technical
ingredients, we therefore develop a combinatorial preprocessing algorithm to
reduce the number of terminals to a polynomial in the solution size $k$ plus
the size of a given (suboptimal) near-separator $S$, which will be available
via the technique of iterative compression [ReedSV04] [CyganFKLMPPS15, §4].
The preprocessing step is based on concrete reduction rules operating in the
graph.

theoremTerminalBoundingState $(\bigstar)$ There is a polynomial-time algorithm
that, given an instance $(G,T,k)$ of mwns and a multiway near-separator
$\hat{S}$ for terminal set $T$ in $G$, outputs an equivalent instance
$(G^{\prime},T^{\prime},k^{\prime})$ such that:

  1. 1.

$G^{\prime}$ is an induced subgraph of $G$,

  2. 2.

$T^{\prime}$ is a subset of $T$ of size
$\mathcal{O}(k^{5}\cdot|\hat{S}|^{4})$, and

  3. 3.

$k^{\prime}\leq k$.

Moreover, there is a polynomial-time algorithm that, given a solution
$S^{\prime}$ for $(G^{\prime},T^{\prime},k^{\prime})$ outputs a solution $S$
of $(G,T,k)$. ††margin:  $\bullet$ How about having points 1, 2, and 3 in the
same line? Note that we are using it twice in the main text. So we eventually
save 2.3 = 6 lines.Rather than doing that, I suggest not repeating the
statement again later on in the paper. Just describe that the statements we
gave lead to a proof of Theorem 1.2 whose statement is in the introduction.

Note that the algorithm even runs in _polynomial-time_ , and may therefore be
a useful ingredient to build a polynomial kernelization for this problem or
variations thereof. To obtain this terminal-reduction algorithm, it turns out
to be useful to know whether the role of a vertex $x$ in a suboptimal near-
separator $S$ can be taken over by $\mathcal{O}(k)$ alternative vertices. If
not, then this immediately leads to the conclusion that such a vertex $x$
belongs to any optimal solution to the problem. On the other hand, knowing a
small vertex set $S_{x}$ for which $(S\setminus\\{x\\})\cup S_{x}$ is also a
near-separator reveals a lot of structure in the instance which can be
exploited by the reduction rule. This usage is similar as the use of the
_blocker_ [CyganFKLMPPS15, §9.1.3] in Thomassé’s kernelization algorithm for
Feedback Vertex Set [Thomasse10].

Given a suboptimal near-separator $S$, we are therefore interested in
determining, for a given $x\in S$, whether it is possible to obtain a near-
separator $S^{\prime}$ by replacing $x$ by a set of $\mathcal{O}(k)$ vertices.
This is equivalent to finding a near-separator of size $\mathcal{O}(k)$ which
avoids the use of vertex $x$ in the graph $G^{\prime}:=G-(S\setminus\\{x\\})$.
Hence this task effectively reduces to finding a solution not containing $x$
in the graph $G^{\prime}$ for which $\\{x\\}$ forms a near-separator. We give
a polynomial-time 14-approximation for this problem.

theoremBlockerState $(\bigstar)$ There is a polynomial-time algorithm that,
given a graph $G$, terminal set $T\subseteq V(G)$, and a vertex $x\in V(G)$
such that $\\{x\\}$ is a multiway near-separator for terminal set $T$ in $G$,
outputs a multiway near-separator $S_{x}\subseteq V(G)\setminus\\{x\\}$ for
$T$ in $G$ such that $|S_{x}|\leq 14|S^{*}_{x}|$, where $S^{*}_{x}\not\ni x$
is a smallest multiway near-separator for $T$ in $G$ that avoids $x$.
††margin:  $\bullet$ I rephrased this theorem to make it more reader-friendly
for the introduction like you have stated Theorem 1

Theorem 1 can be compared to a result for the Chordal Deletion problem, where
the goal is to delete a minimum number of vertices to break all induced cycles
of length at least four (holes). A key step in the polynomial kernelization
algorithm for the problem due to Jansen and Pilipczuk is a subroutine
([JansenP18, Lemma 1.3]) which, given a graph $G$ and vertex $x$ for which
$G-\\{x\\}$ is chordal, outputs a set of some $\ell\geq 0$ holes pairwise
intersecting only in $x$, together with a vertex set $S$ of size at most
$12\ell$ not containing $x$ whose removal makes $G$ chordal. Hence $S$ is a
12-approximation for the problem of finding a chordal deletion set which
avoids $x$.

### Related work

Apart from the aforementioned work on graph separation problems, the work of
Golovach and Thilikos [GolovachT19] is related to our setting. They consider
the problem of removing at most $k$ edges from a graph to ensure it split it
into exactly $t$ connected components $C_{1},\ldots,C_{t}$ such that $C_{i}$
has edge-connectivity at least $\lambda_{i}$ for a given sequence
$(\lambda_{1},\ldots,\lambda_{t})$. ††margin:  $\bullet$ Should we also give
some references to the directed version of MWC and Multicut? Besides recursive
understanding, which only leads to non-uniform FPT classifications, another
generic tool for deriving fixed-parameter tractability of separation problems
is the treewidth reduction technique by Marx and Razgon [MarxR14]. To be able
to apply the technique, the number of terminals must be bounded in terms of
the parameter $k$, which is not the case in general. Even if one uses Theorem
1 to bound the number of terminals first, it is not clear the technique can be
applied since the solutions to be preserved are not minimal separators in the
graph. Furthermore, successful application of the technique would give double-
exponential algorithms at best, due to having to perform dynamic programming
on a tree decomposition of width $2^{\Omega(k)}$.

The problem of computing a near-separator avoiding a vertex $x$ is related to
the problem of computing an _$r$ -fault tolerant_ solution to a vertex
deletion problem, which is a solution from which any $r$ vertices may be
omitted without invalidating the solution. The computation of $r$-fault
tolerant has been studied for the Feedback Vertex Set problem [BlazejCKKSV21],
which has a polynomial-time $\mathcal{O}(r)$-approximation.

The algorithm for Subset Feedback Vertex Set in undirected graphs due to Cygan
et al. [CyganPPW13] bears some similarity to ours, in that it also uses a
reduction rules to bound the number of terminals followed by an algorithm
which is exponential in the solution size and the number of terminals.
However, Subset Feedback Vertex Set behaves differently from the problem we
consider, since the structures to be hit always involve _pairs_ of terminals
to be near-separated. On the other hand, a solution to Subset Feedback Vertex
Set will reduce the connectivity in the graph to the extent that there will no
longer be two internally vertex-disjoint paths between any terminal pair, but
also has to ensure that there are no cycles through a single terminal. This
leads to significant differences in the approach.

### Organization

To-do. The proofs of statements marked with $(\bigstar)$ are located in the
appendix.

##  2 Preliminaries

#### Graphs.

We use standard graph-theoretic notation, and we refer the reader to Diestel
[Diestel17] for any undefined terms. We consider simple unweighted undirected
graphs. A graph $G$ has vertex set $V(G)$ and edge set $E(G)$. We use
shorthand $n=|V(G)|$ and $m=|E(G)|$. The set $\\{1,\ldots,\ell\\}$ is denoted
by $[\ell]$. The open neighborhood of $v\in V(G)$ is
$N_{G}(v):=\\{u\mid{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\\{u,v\\}}}\in
E(G)\\}$, where we omit the subscript $G$ if it is clear from context. For a
vertex set $S\subseteq V(G)$ the open neighborhood of $S$, denoted $N_{G}(S)$,
is defined as $S:=\bigcup_{v\in S}N_{G}(v)\setminus S$. For $S\subseteq V(G)$,
the graph induced by $S$ is denoted by $G[S]$. 11todo: 1Include all the
preliminaries which you are using in the main text

An instance $(G,T,k)$ of mwns is said to be _non-trivial_ if $\emptyset$ is
not a solution of $(G,T,k)$. A terminal $t\in T$ is said to be _nearly-
separated_ in $G$ if there does not exist another terminal $t^{\prime}\in
T\setminus\\{t\\}$ such that there are 2 internally vertex-disjoint
$t$-$t^{\prime}$ paths in $G$. Throughout this manuscript we use Multiway
Near-Separator (mwns) to denote the parameterized version of the multiway
near-separator problem, whereas given a graph $G$ and terminal set $T$ we use
multiway near-separator (MWNS) to refer to the graph-theoretic concept of
nearly-separating a terminal set $T$ in $G$. Formally, it is defined as
follows.

######  Definition 2.1 (Multiway near-separator (MWNS)).

Given a graph $G$ and terminal set $T\subseteq V(G)$, a set $S\subseteq V(G)$
is called a multiway near-separator (MWNS) of $(G,T)$ if $S\cap T=\emptyset$
and there does not exist a pair of distinct terminals $t_{i},t_{j}\in T$ such
that $G-S$ contains two internally vertex-disjoint $t_{i}$-$t_{j}$ paths.

######  Definition 2.2 ($r$-redundant MWNS).

Given a graph $G$ and terminal set $T\subseteq V(G)$, a set $S^{*}\subseteq
V(G)\setminus T$ is an $r$-redundant MWNS of $(G,T)$ if for all $R\subseteq
S^{*}$ with $|R|\leq r$, the set $S^{*}\setminus R$ is a MWNS of $(G,T)$.

######  Definition 2.3 ($x$-avoiding MWNS).

Given a graph $G$, terminal set $T\subseteq V(G)$, and a vertex $x\in V(G)$, a
set $S_{x}\subseteq V(G)\setminus T$ is called an $x$-avoiding MWNS of $(G,T)$
if $x\notin S_{x}$ and $S_{x}$ is a MWNS of $(G,T)$. Among all $x$-avoiding
MWNS of $(G,T)$, one with the minimum cardinality is called a minimum
$x$-avoiding MWNS of $(G,T)$.

Next, we define $T$-cycle and give a characterization of MWNS in terms of
hitting $T$-cycles.

######  Definition 2.4 ($T$-cycle and $T$-cycle on $x$).

Given a graph $G$ and terminal set $T\subseteq V(G)$, a cycle $C$ in $G$ is
called a $T$-cycle if $|V(C)\cap T|\geq 2$. Moreover, if $C$ also contains a
vertex $x\in V(G)$, then $C$ is called a $T$-cycle on $x$.

######  Remark 3.

$\bullet$ $T$-cycle _intersecting_ $x$ would have been a better name. We now
show that several ways of looking at a near-separator are equivalent.
propositionDifferentWaysOfLookingAtMWNSState $(\bigstar)$ Given a graph $G$,
terminal set $T\subseteq V(G)$, and a non-empty set $S\subseteq V(G)\setminus
T$, the following conditions are equivalent:

  1. 1.

For each pair of distinct terminals $t_{i},t_{j}\in T$, the graph $G-S$ does
not contain $t_{i}$-$t_{j}$ paths $P_{1},P_{2}$ which are pairwise

Due to space constraints we defer the remaining preliminaries about graphs
(including block-cut graphs) and parameterized algorithm to Appendix
LABEL:sec:AdditionalPreliminaries.

##  3 FPT algorithm for Multiway Near-SeparatorFPT algorithm for MWNS


* [Mil81] Arnold W. Miller.  Some properties of measure and category.  Trans. Amer. Math. Soc., 266(1):93–114, 1981.
  * [Voj93] Peter Vojtáš.  Generalized Galois-Tukey-connections between explicit relations on classical objects of real analysis.  In Set theory of the reals (Ramat Gan, 1991), volume 6 of Israel Math. Conf. Proc., pages 619–643. Bar-Ilan Univ., Ramat Gan, 1993\.

Institute of Discrete Mathematics and Geometry
TU Wien
Wiedner Hauptstrasse 8–10/104, A-1040 Wien
AUSTRIA
E–mail address<EMAIL_ADDRESS>
Creative Science Course (Mathematics), Faculty of Science
Shizuoka University
836 Ohya, Suruga-ku, Shizuoka 422-8529
JAPAN
E–mail address<EMAIL_ADDRESS>