11institutetext: Technische Universiteit Eindhoven 22institutetext: University
of Pennsylvania

# Layered TPOT

Speeding up Tree-based Pipeline Optimization

Pieter Gijsbers 11 Joaquin Vanschoren 11 Randal S. Olson 22

###### Abstract

With the demand for machine learning increasing, so does the demand for tools
which make it easier to use. Automated machine learning (AutoML) tools have
been developed to address this need, such as the Tree-Based Pipeline
Optimization Tool (TPOT) which uses genetic programming to build optimal
pipelines. We introduce Layered TPOT, a modification to TPOT which aims to
create pipelines equally good as the original, but in significantly less time.
This approach evaluates candidate pipelines on increasingly large subsets of
the data according to their fitness, using a modified evolutionary algorithm
to allow for separate competition between pipelines trained on different
sample sizes. Empirical evaluation shows that, on sufficiently large datasets,
Layered TPOT indeed finds better models faster.

##  1 Introduction

The field of Automated Machine Learning (AutoML) aims to automate many of the
tasks required to construct machine learning models, hence lowering the
barrier to entry and yielding better models, faster. AutoML methods typically
automate one or more steps in the creation of useful machine learning
pipelines, such as the selection of preprocessing or learning algorithms,
hyperparameter optimization, or a combination of them. A few methods even
construct and optimize entire pipelines, such as the Tree-based Pipeline
Optimization Tool (TPOT)[14]. TPOT uses genetic programming to evolve optimal
pipelines, aiming to find machine learning pipelines yielding accurate
predictive models while trying to keep the pipeline as simple as possible.

In this paper, we introduce a novel improvement of TPOT, aimed at reducing the
time needed to evaluate pipelines, without reducing the quality of the final
pipeline. Indeed, the most time-consuming part in the optimization process is
evaluating the performance of candidate machine learning pipelines. In our
modification, this time is reduced by initially evaluating the pipelines on a
small subset of the data, and only allowing promising pipelines to be
evaluated on the full dataset. In order to do this in a fair manner,
modifications to the evolutionary algorithm are implemented to prevent direct
comparison between pipelines which are evaluated on different subsets of the
data. As such, we aim to find pipelines of similar quality in much less time,
making the tool more accessible and practical by requiring less computational
time. We call this improvement Layered TPOT (LTPOT).

This paper is organized as follows. First, we review related work in Sect. 2.
Then, in Sect. 3, we discuss the proposed modification to TPOT in detail.
Next, in Sect. 4, we lay out how LTPOT will be evaluated, discuss the results
of these evaluations, and propose aspects of LTPOT which can be researched in
future work. Finally, we conclude the study in Sect. 5.

##  2 Related Work

The field of AutoML is a culmination of work in the fields of algorithm
selection, hyperparameter optimization and machine learning. Several AutoML
systems support at least some form of automatic pipeline construction.

Auto-WEKA [18] uses Sequential Model-based Algorithm Configuration (SMAC) to
do combined algorithm selection and hyperparameter optimization [10], which is
an adaptation of Sequential Model-Based Optimization from statistical
literature. Auto-WEKA uses algorithms from the WEKA library [8], to build
pipelines with one learner (possibly an ensemble) and optionally a single
feature selection technique.

Auto-sklearn [6], built on the Python library scikit-learn [15], is a re-
implementation of Auto-WEKA with two extensions. The first is the use of meta-
learning to warm-start the Bayesian optimization procedure, a technique which
has earlier been proven useful in [7]. The second addition is the automatic
construction of ensembles from models evaluated during the optimization
process. Furthermore, auto-sklearn allows for more preprocessing steps to be
included in the pipeline: it allows for one feature preprocessor, which
includes feature extraction techniques as well as feature selection
techniques, in addition to up to three data preprocessor methods, such as
missing value imputation and rescaling.

TPOT differs from Auto-sklearn and Auto-WEKA by using an evolutionary
algorithm instead of SMAC. Additionally, TPOT uses a tree-based structure to
represent pipelines, and considers pipelines with any number of preprocessing
steps. Hence, TPOT is not constrained in the number nor the order of
preprocessing steps.

The main idea of LTPOT is to first evaluate pipelines on a subset of the data,
to get an indication of whether or not the pipeline is promising relative to
other pipelines. This idea has been explored before, for example in Sample-
based Active Testing [1], or algorithm selection using learning curves [16],
where promising algorithm configurations are first evaluated on a smaller data
sample to create a proxy for their performance on the full dataset.

The use of subsets to evaluate machine learning configurations is also used in
Hyperband [11]. Hyperband dynamically allocates resources to more promising
algorithm configurations, based on experiments executed on gradually more
resources. One application that is explored is using data samples as a
resource, and using increasingly bigger subsets of the data to evaluate the
algorithm configurations with. In a specific selection of datasets they showed
that using this technique improved over Random Search, SMAC and Tree-
structured Parzen Estimators, as introduced in [3].

In the context of evolutionary algorithms, evaluating individuals on a subset
of the data to filter out bad individuals is also implemented in GTMOEP [20].
Rather than a successive halving approach, they perform a selection of
individuals based on evaluation on 1% of the data. However, there is very
little evaluation done to have a clear picture of the effects of this approach
on the resulting pipelines across datasets.

##  3 Methods

In this section, we describe the modifications made to TPOT. First, we give a
brief description of how TPOT constructs and optimizes machine learning
pipelines. Then, we describe the Layered TPOT (LTPOT) structure and motivate
its design.

###  3.1 Structure of TPOT

To construct and optimize machine learning pipelines, TPOT uses tree-based
genetic programming [2]. Pipelines are represented by genetic programming
trees. An example of a tree representation of a machine learning pipeline is
shown in Fig. 1. The tree consists of several nodes, which can either be
Primitives or Terminals, in Fig. 1 depicted as squares and ellipses,
respectively. Primitives are operators which require input, such as an
algorithm requiring data and hyperparameter values. Terminals are constants
which can be passed to primitives. Finally, a primitive can also be used as
input to a primitive, as can be seen in Fig.1, where the StandardScaler
primitive provides the scaled dataset to the Bernoulli Naive Bayes algorithm.
Information of required input and output types is used to ensure that only
valid pipelines are constructed.

Figure 1: A visual representation of a tree-based machine learning pipeline
that applies standard scaling to the data before learning a Bernoulli Naive
Bayes model.

The evolutionary algorithm then works by using these machine learning
pipelines as their individuals. It will perform mutation, for example changing
a hyperparameter or adding a preprocessing step, as well as crossover, by
selecting two pipelines which share a primitive, which allows them to exchange
subtrees or leaves. Finally, pipelines are evaluated and assigned a fitness
score, so that a selection procedure can determine which individuals should be
in the next generation.

As mentioned earlier, in theory these pipeline trees could be arbitrarily
large. However, very extensive machine learning pipelines are often
undesirable. With more hyperparameters, long pipelines can be harder to tune,
be more prone to overfitting, hinder understanding of the final model, and
require more time to be evaluated, slowing down the optimization process.

Because of these reasons, we use a multiobjective optimization technique,
NSGA-II[4], to select individuals based on the Pareto front of the trade-off
between the pipeline length and its performance.

###  3.2 Layered TPOT Concept

During the TPOT optimization process, most time is spent on evaluating machine
learning pipelines. Every machine learning pipeline is evaluated on the full
dataset, which can take a lot of time. Layered TPOT (LTPOT) aims to reduce the
amount of pipelines evaluated on the entire dataset by doing a selection
process, so that only the most promising pipelines need to be evaluated on the
full dataset. It achieves this by evaluating pipelines on a small subset of
the data, and only if a pipeline exhibits good performance on that subset it
will be evaluated on more data.

####  3.2.1 Age-Layered Population

To incorporate a fair evaluation of pipelines on subsets gradually increasing
in size, we designed a layered structure to separate competition among
individuals. In this, we were inspired by the Age-Layered Population Structure
(ALPS) [9], where individuals are segregated into layers to reduce the problem
of _premature convergence_. The problem of premature convergence occurs when
the individuals in the population converge to a good local optimum, which
means that any new individuals are unlikely to be competitive with this local
optimum, and through selection are filtered out of the population before they
themselves can converge to a local optimum. In ALPS, all individuals were
given an _age_ which would increase as an individual or its offspring would
remain in the population, and perform breeding and selection only in separate
age groups called layers. This segregation is important, because otherwise the
old, locally well optimized, individuals would often prevent young individuals
from being able to survive the multiple generations they needed to get closer
to their local optimum.

####  3.2.2 Layers in LTPOT

In LTPOT, we wish to evaluate pipelines on subsets of the data. However, the
performance of a machine learning pipeline is influenced by the amount of
training data it receives. This means that when evaluating individuals on
different subsets of the data, their performance cannot directly be compared
to one another. Therefore, the individuals are segregated into _layers_.

At each layer, individuals will be evaluated on a subset of different size.
The layers are ordered, such that in the first layer the subset used to
evaluate the individuals is the smallest, and every layer above that will
increase the subset size. When an individual performs well in one layer, it
will eventually be transferred to the next. This way, only the best pipelines
will be evaluated on the entire dataset in the last layer. A visual overview
of the structure and flow of LTPOT is given in Fig.2.

Figure 2: A visual overview of the Layered TPOT structure. After a certain
number of generations, each layer passes their best $k$ individuals on to the
next layer, while the first layer will be provided with a newly generated set
of individuals.

####  3.2.3 Correlation of performance between layers

In the extreme, the selection procedure implicitly assumes that the relative
performance of two pipelines is the same when evaluated on a subset of the
dataset as it is on the entire dataset. However, this assumption does not
always hold. The learning curves for two pipelines may cross, meaning that one
pipeline performs better after being trained on a small subset of the data,
while the other performs better when trained on the full dataset. Generally
speaking, as the pipelines are evaluated on more data, the relative
performance correlates more strongly with the relative performance obtained
when they are trained on the entire dataset. This is why our design will
evaluate the pipelines on gradually larger subsets of data, so that when a
pipeline performs worse than expected as the dataset increases, it need not be
evaluated on bigger datasets. Unfortunately, in the case where a pipeline has
poor performance on a small subset, but good performance on the entire
dataset, LTPOT will not pick up this pipeline.
We set up an experiment to verify whether or not there is indeed a correlation
between the performance of a pipeline on a sample of the dataset and its
performance on the entire dataset. In this experiment, we evaluated 50
pipelines on 12 datasets with ten times 10-fold cross-validation, with various
samples sizes of the dataset as well as the entire dataset. All datasets were
part of the Penn Machine Learning Benchmark (PMLB) [13]. The average AUROC of
each pipeline for each sample size was determined for each dataset. Sample
sizes were $\\{N/2^{1},\dots,N/2^{5}\\}$, where $N$ is the number of instances
in the dataset. Because the evolutionary algorithm performs pipeline selection
based on the ranking of the algorithms, rather than the value of the score
metric, we ranked the averaged scores and computed the correlation of the
rankings.

dataset | instances | features | $\rho_{\frac{N}{2}}$ | $\rho_{\frac{N}{4}}$ | $\rho_{\frac{N}{8}}$ | $\rho_{\frac{N}{16}}$ | $\rho_{\frac{N}{32}}$
---|---|---|---|---|---|---|---
satimage | 6435 | 36 | 0.984 | 0.903 | 0.833 | 0.759 | 0.641
clean2 | 6598 | 168 | 0.972 | 0.946 | 0.890 | 0.825 | 0.765
ann-thyroid | 7200 | 21 | 0.982 | 0.967 | 0.946 | 0.924 | 0.828
twonorm | 7400 | 20 | 0.978 | 0.929 | 0.898 | 0.759 | 0.829
mushroom | 8124 | 22 | 0.973 | 0.962 | 0.935 | 0.867 | 0.781
agaricus-lepiota | 8145 | 22 | 0.989 | 0.980 | 0.920 | 0.877 | 0.805
coil2000 | 9822 | 85 | 0.939 | 0.878 | 0.815 | 0.568 | 0.529
pendigits | 10992 | 16 | 0.984 | 0.983 | 0.945 | 0.844 | 0.771
nursery | 12958 | 8 | 0.995 | 0.995 | 0.857 | 0.917 | 0.917
magic | 19020 | 10 | 0.988 | 0.974 | 0.961 | 0.947 | 0.934
letter | 20000 | 16 | 0.990 | 0.959 | 0.918 | 0.899 | 0.801
krkopt | 28056 | 6 | 0.984 | 0.942 | 0.917 | 0.913 | 0.750
Table 1: An overview of the spearman $\rho$ calculated by comparing the
ranking of pipelines trained on subsets of the data compared to the entire
dataset, $p<0.0001$ in all cases. The subscript in the column denote the size
of the subset.

In Table 1 the Spearman $\rho$-values are displayed, that signify the
correlation between the ranking of pipelines trained on a sample of the
dataset, and the ranking of pipelines when trained on the entire dataset. The
$p$-values are omitted because in all cases they are smaller than $0.0001$ and
all correlations are thus significant. From Table 1 we see that that there is
a positive correlation between the rankings for all sample sizes and datasets,
and the correlation gets stronger as the sample size gets closer to the full
dataset size.

We experimented with various curve fitting methods to extrapolate the learning
curves of pipelines so that crossing learning curves might be predicted
earlier, but they did not improve the results. In future work the use of meta-
learning for learning curve extrapolation, such as in [16], will be tried.

###  3.3 Layered TPOT Algorithm

We will now give a more in-depth break down of the algorithm used in LTPOT.
Algorithm 1 shows the core of the layered algorithm LayeredEA, and Algorithm 2
gives descriptions of the subroutines called from LayeredEA.

Algorithm 1 Layered Evolutionary Algorithm

1:function LayeredEA(population, S, g, G, D)

2:population: a set of pipelines that will be the first generation

3:S: set containing the sample size for each layer

4:g: interval in generations for when a transfer should occur

5:G: total number of generations

6:D: dataset to construct a pipeline for

7: $M\leftarrow\|S\|$ $\triangleright$ Denote the number of layers.

8: $P\leftarrow\|population\|$ $\triangleright$ Denote population size.

9: $L_{1}\leftarrow$ population

10: $L_{2},\dots,L_{M}\leftarrow\emptyset$

11: for $i$ in $1..G$ do

12: for $l$ in $1..M$ do

13: if $L_{l}\neq\emptyset$ and $i\bmod g<2^{(M-l+1)}$ then

14: offspring $\leftarrow$ VarOr($L_{l}$, $P$)

15: Evaluate(offspring, $S_{l}$, $D$)

16: $L_{l}\leftarrow$ Selection($L_{l}$ $\cup$ offspring, $P$)

17: end if

18: end for

19: if $i\bmod g$ = 0 then

20: for $l$ in $(M-1)..1$ do

21: $L_{l+1}\leftarrow L_{l+1}$ $\cup$ Top($L_{l}$, $P/2$)

22: end for

23: $L_{1}\leftarrow\textsc{NewPopulation}(P)$

24: end if

25: end for

26: return Top($L_{M}$, $1$)

27:end function

Algorithm 2 Functions called in Layered EA

1:function VarOr($Population,N$)

2:Performs mutation and crossover on the individuals in $Population$, creating
$N$ new individuals.

3:end function

4:

5:function Evaluate($Population,s,D$)

6:Evaluates each individual on a subset of dataset $D$, created by taking $s$
instances by stratified sampling. Individuals are evaluated based on 3-fold CV
accuracy and number of components in the pipeline. Results are saved as
attributes of individuals.111Is it fine to use attributes like this in the
pseudocode? It is like this in the actual code. I’m not sure if this makes it
harder to understand for the reader than introducing eg. a dictionary which
maps individual to fitness.

7:end function

8:

9:function Selection($Population,p$)

10:Creates pareto-fronts based on the accuracy-pipeline complexity trade-off.
Then takes the first $p$ individuals after ordering the population by which
pareto-front they are in (individuals in the first front come first).

11:end function

12:

13:function Top($Population,k$)

14:Returns the $k$ best individuals of the population, by constructing a
pareto-front based on the accuracy-pipeline complexity trade-off.

15:end function

16:

17:function NewPopulation($P$)

18:Creates a new population of $P$ individuals.

19:end function

20:

####  3.3.1 Selecting parameter values

Before calling LayeredEA, the number of layers as well as their _sample size_
is defined. The sample size of a layer dictates how many instances are sampled
from the dataset, to create the subset that the pipelines in that layer will
be evaluated on. The subset is created by stratified uniform random sampling
without replacement, and pipelines will be evaluated on this subset with
5-fold cross-validation. In this study, the sample sizes used in each layer
are dictated by the size of the dataset. Let the dataset contain N instances,
then the final layer will always train on the entire dataset, and each
subsequent layer will use half of the data the layer above did. In this study,
the number of layers used is $4$, for every dataset. The respective sample
sizes used at each layer are thus $\frac{N}{8}$, $\frac{N}{4}$, $\frac{N}{2}$
and $N$. In this paper we use the term _higher_ layer loosely to denote layers
which sample more of the entire dataset (i.e. the layer with sample size
$\frac{N}{2}$ is higher than the layer with sample size $\frac{N}{4}$).

There are two ways to specify for how long the main loop of lines 7 through 20
should run: a set amount of generations $G$, or an amount of time. We chose
not to work with a specific number of generations $G$, but instead let the
main loop in lines 7 through 20 run for eight hours. For parameter $g$, the
amount of generations between transfer, we experimented with values $2$ and
$16$. With a $g$ value of $2$, LTPOT acts almost as a filter, allowing only
very little optimization in early layers. A value of $16$, however, allows
many generations of early optimization, before passing individuals through to
the next layer.

For the final part of the initialization, a population of size $P$ is
generated randomly.

####  3.3.2 LayeredEA

When calling LayeredEA, as shown in Algorithm 1, the first step is to denote
constants based on the input, specifically the number of layers $M$ (line 1)
and the size of the population $P$ (line 2), as well assigning the initial
population to the first layer (line 4) and marking all other layers as empty
(line 5).

Then, the evolutionary algorithm will start iterating through the generations
(line 6-20), at each generation again progressing the evolutionary algorithm
in each layer (line 7-13) and then if required transferring individuals from
one layer to the next (line 14-19).

Progressing the evolutionary algorithm in each layer (line 7-13), only happens
for layers which are _active_. This means that there must be a population in
the layer (first clause on line 8), which it may not yet have if not enough
transfers have taken place yet. Additionally, layers which evaluate on more
data are not active every generation (second clause on line 8), this is
motivated below.

When progressing the evolutionary algorithm, it executes the same steps as
TPOT would. First, a new population is created from the individuals evaluated
during the last generation in the same layer, by performing mutation and
cross-over (line 9). However, every time a layer is passed new individuals
from a previous layer, as well as in the very first generation, the provided
population is taken as is without creating offspring.222This is not
incorporated in the pseudo-code of algorithm 1, to keep the general structure
clear. The new individuals are then evaluated based on the sample of the data
as defined by their layer (line 10). Finally, based on the Pareto-front of the
trade-off between the performance score of the pipeline as well as the
pipeline length, the best individuals are picked among the new individuals as
well as last generation’s (line 11). Then, every $g$ generations, the best
individuals from each layer get passed to the next one. In our configuration
we chose to transfer half of the layer’s population.

The final pipeline chosen by LTPOT is the pipeline which has the best score in
the highest layer (line 21).

####  3.3.3 Optimizations

There are a few scenario’s that either require some additional clarification,
or deviate from the above algorithm:

The first time a layer receives individuals from the layer before it, the
selection procedure will oversample from this population so that the
population in the layer will also grow to size $P$ (line 11). This is done so
that in subsequent generations, more variations of the original pipelines will
exist, allowing for a better search for optimal pipelines.

Secondly, if LTPOT runs for a specified amount of generations, layers will be
turned off whenever their population can no longer reach the highest layer.
For example, let LTPOT be configured with $4$ layers. When LTPOT is less than
$3*g$ generations away from completion, any individual in the lowest layer
will never reach the highest layer, thus rendering any results obtained in
this layer useless. Whenever this happens, the respective layer will no longer
have their individuals evaluated or transferred to a next layer.

Next, there is the earlier mentioned restriction on activating layers as shown
in the second clause on line 8. LTPOT has a selection process in place for
which pipelines will be evaluated on the entire dataset. This means that at
higher layers, the pipelines in the population are likely already quite good.
Because of these two factors, we want to limit the exploration in higher
layers. To do this, instead of running the evolutionary algorithm in each
layer every generation, higher layers can be turned off for some generations.
In this study, for a layered structure with $M$ layers, layer $l$ is
progressed for $\min(2^{(M-l+1)},g)$ generations every $g$ generations, with
$l\in\\{1,\cdots,M\\}$. This is demonstrated with $g=12$ and $M=4$ in Fig.3,
and checked in the second clause on line 8. We have not yet evaluated if this
leads to significant improvements.

Figure 3: Not every layer should run experiments every generation. This figure
illustrates that the higher layers will be ’turned off’ in higher layers,
meaning that no iterations of the evolutionary algorithm are executed.

Finally, to prevent any one pipeline from halting the algorithm, a pipeline’s
evaluation is automatically stopped if it exceeds a given time limit. If the
evaluation is stopped this way, the pipeline is marked as failure and will not
be considered as parent for the next generation. This behavior is present in
the original TPOT, and adopted to LTPOT by further decreasing the time limit
by layer. In the top layer, each individual is allowed the same evaluation
time as it would in TPOT. However, for lower layers, the time allowed is
decreased quadratically proportional to the sample size (a layer with half the
data gets a fourth of the time per individual).

##  4 Empirical evaluation

###  4.1 Experimental Questions

The goal of LTPOT is to find pipelines at least as good as TPOT’s, but in less
time. This also means that, given the same amount of time, LTPOT could very
well find better pipelines. To assess whether or not this is achieved, we will
evaluate LTPOT in three ways.

First, we want to evaluate if, given the same amount of time, LTPOT will
outperform TPOT when their best found pipelines are compared. To do this, a
ranking is constructed between TPOT and LTPOT for each dataset over time, by
ranking the performance of the best pipeline found so far at regular time
intervals. We omit a comparison to Random Search, as TPOT compared favorably
to Random Search in earlier work [12].

Secondly, to quantify how much faster LTPOT is, we compare the time needed for
LTPOT to find a pipeline at least as good as the best pipeline found by TPOT.
We then compare it to the time TPOT needs to find this pipeline.

Finally, we will also compare the Area Under the Receiver Operating
Characteristic curve (AUROC) of the final pipelines found by each method, so
we can quantify the difference in model quality between the methods.

###  4.2 Experimental setup

We compare LTPOT to the original TPOT by evaluating both on a selection of 18
large datasets. We specifically chose larger datasets so that there will be a
distinct difference in time needed to evaluate individuals on the entire
dataset versus just a subset. All datasets in the selection contain at least
one hundred thousand instances, though most contain exactly one million. The
selection includes pseudo-artificial datasets described in [17]. The datasets
are available for download and inspection on
OpenML333https://www.openml.org/s/69, an open database for machine learning
experiments [19]. We previously evaluated LTPOT on a selection of datasets
from the Penn Machine Learning Benchmark [13], which TPOT was initially
evaluated on. Because those datasets were relatively small, pipeline
evaluations were quick even on the full dataset, so there was no significant
benefit of using LTPOT. On each dataset, each method is evaluated nine times,
starting with a different initial generation each time.

As described earlier, there are many hyperparameters with which to tune LTPOT.
In this study, we only experiment with $g$, the amount of generations between
transfer. The choices for $g$ will be $2$ and $16$, and these configurations
will be referred to as LTPOT-2 and LTPOT-16, respectively. This is meant to
give insight in the effectiveness of two functions of LTPOT: filtering and
early optimization. For LTPOT-2, layers act almost solely as a filter, by
passing the best individuals to the next layer every other iteration, not much
optimization takes place in lower layers, but it does allow for the early
discarding of pipelines which seem to perform poorly. With LTPOT-16, we
instead see that a lot of optimization can take place based on results found
in lower layers, as relatively more time is spent evaluating and improving
individuals in lower layers compared to LTPOT-2. In other words, LTPOT-2’s
first layer allows for more early exploration, while LTPOT-16’s first layer is
more focused on exploitation.

The amount of individuals transferred, $k$, will be set to $15$, which is half
of the total population size $P=30$. Each LTPOT configuration, as well as
TPOT, is run nine times per dataset, each time with a different _random seed_
, guaranteeing a different initial population and subsequent choices for
crossover and mutation. Each run set to last 8 hours, but each individual
pipeline may only be evaluated for at most 10 minutes. We explored different
values for $P$ and different amounts of evaluation time per individual, while
keeping the total run time constant at 8 hours, and found that for the chosen
datasets these values strike a balance between having a diverse enough
population and being able to evaluate enough generations.

###  4.3 Results

First, we compare the various configurations by their average rank over time,
which can be seen in Fig. 4. In this figure, for each configuration, for every
dataset and seed, the best found pipelines so far are ranked against each
other every minute. For each method, the average Friedman rank [5] across all
these datasets and seeds is calculated based on the highest AUROC score
achieved by the best pipeline so far, using the fixed hyperparameter values
stated above. To calculate the rank, we consider the result a tie if the
difference in AUROC values is smaller than 0.1. A lower rank is better.

Figure 4: Ranking of each method averaged over all datasets based on internal
AUC scores of the best individual found so far.

In Fig. 4, we see that LTPOT on average achieves the best scores throughout
the entire 8 hour period. LTPOT-16 starts by outperforming LTPOT-2 slightly,
but as time goes on its relative performance drops, even being surpassed by
TPOT. From this, it seems that while LTPOT works well as a filter,
optimization in early layers does not pay off beyond the early stages. Thus, a
lower value for $g$ is better based on these results. Furthermore, we see that
towards the end TPOT is decisively improving over LTPOT-16, but only very
slowly over LTPOT-2, as the average rank of LTPOT-2 increases only very
slowly.

A different rank does not necessarily mean the found model performance differs
a lot. To clarify this, we look at the difference in AUROC by dataset per
configuration, as seen for 9 of 18 datasets in Fig. 5.444A similar figure for
the other 9 datasets can be found in Appendix A.

In Fig. 5 we show a boxplot that describes the distribution of AUROC scores of
the final pipelines by each method. No single method is dominant over the
others, and differences in AUROC scores are small for almost all datasets.
Using a student t-test, we determined that there is no statistically
significant difference ($p<0.05$) between the final pipelines (after the full
8 hour time budget).

Figure 5: An overview of achieved AUROC score for each run of each method by
dataset.

However, looking at the average ranking by configuration in Fig. 4, we see
that under smaller time budgets LTPOT-2 often finds pipelines which are better
than TPOT. In this scenario, it is interesting to see how much time LTPOT
needs to find a pipeline at least as good as the best pipeline TPOT found. We
compared LTPOT-2 to TPOT for each dataset and seed, and looked at how long it
took for the method which found the best pipeline to find a pipeline at least
as good as the best found pipeline by the other method. Figure 6 shows the
time difference (in minutes) between finding these equally good pipelines.
Positive values indicate that LTPOT is faster. Yellow distributions correspond
to seeds where LTPOT eventually found the best pipeline, and show how much
sooner LTPOT found a pipeline at least as good as the best pipeline of TPOT.
Blue distributions correspond to cases where TPOT eventually found the best
pipeline, and show how much later TPOT found a pipeline at least as good as
LTPOT’s best.

Figure 6: Violin plots of the time difference between finding two equally good
pipelines. Datasets are shown together with their OpenML ID number.

In general, when LTPOT finds the best pipeline, it finds a pipeline at least
as good as TPOT’s best pipeline much sooner. In particular for LTPOT-16 we see
that it often is at least 200 minutes faster. Even in the cases where TPOT
eventually finds the best pipelines, we see that it often finds a pipeline at
least as good as LTPOT’s best only after LTPOT already found it. This again is
especially true for LTPOT-16, where almost all yellow distributions are
entirely positive.

However, even when one method finds a pipeline at least as good as the other
method’s eventual best pipeline, it can still be the case that the eventual
worst method at that same time already has quite a good pipeline. Therefore,
we compare the performance of the best pipeline of each method found at time
$t$, where time $t$ is the time where the best method finds a pipeline at
least as good as the eventual best pipeline of the worst method. Between 18
datasets and 9 seeds, there are 162 comparisons between TPOT and LTPOT-2 or
LTPOT-16. The comparison in AUROC at time $t$ is shown in Figure 7.

Figure 7: Shows the AUROC difference at time $t$, which is the time the best
method (color coded) finds a pipeline at least as good as the other method
will find.

We see that when TPOT finds a pipeline at least as good as LTPOT’s best, in
most cases it does so when LTPOT already has found a pipeline at most 0.01
AUROC worse. However, when LTPOT finds a pipeline at least as good as TPOT’s
best, TPOT has relatively worse pipelines more often, and in some cases as
much as over 0.2 AUROC worse.

From this we conclude that in many cases LTPOT finds good pipelines faster.
While LTPOT-2 does not always find the best pipeline, when it doesn’t, it
finds comparable pipelines at least as quickly as TPOT. LTPOT-16 finds
comparable pipelines even quicker, although it becomes less competitive under
larger time budgets.

###  4.4 Future work

The structure of Layered TPOT allows for more hyperparameters to be tuned, and
their effect remains unexplored at this point. The number of layers as well as
the effect of their granularity could possibly be tuned to the dataset.
Whether or not to turn off higher layers, and with which frequency, should be
explored as well. The amount of individuals to transfer between layers may
also change how quickly higher layers can optimize pipelines. The choice of
the amount of generations before transfer, $g$, will influence how much
optimization will be done in the lower layers. Perhaps these parameters should
change over time in a single run. All of these choices come in addition to the
hyperparameters already available for TPOT, such as the population size,
mutation rate and crossover rate.

Finally, there are possible changes not yet captured in hyperparameters. For
instance, it might be better to favor crossover over mutation in higher
layers, so that the focus of exploration shifts to combining promising
pipelines in higher layers. It could be that having a big population in the
higher layers is unnecessary, and shrinking population size there might yield
similar results in a faster time frame. Currently, the way to evaluate
individuals quickly is to sample a number of instances of the data. Instead,
one could create a subset by selecting features, or apply compression
techniques to represent the data. We will explore these aspects in subsequent
work.

Results of this study will be made available on OpenML555www.openml.org, and
the code for Layered TPOT can be found on Github666https://github.com/PG-
TUe/tpot/tree/layered.

##  5 Conclusion

In this paper we presented an extension to TPOT called Layered TPOT. In the
extension, instead of evaluating each pipeline on all data, only pipelines
which have shown good results on subsets of the data are evaluated on all
data. It does this by introducing layers. In each layer a distinct group of
individuals is subject to the evolutionary algorithm, but individuals are only
evaluated on a subset of the data as defined by the layer. Each subsequent
layer will evaluate the individuals on more data, and if an individual
performs well in one layer, it will be transferred to the next, to be trained
on more data and compete with other promising pipelines trained on the same
subset size.

To determine the usefulness of LTPOT, two configurations have been compared to
TPOT, on a selection of 18 large datasets. The results showed that LTPOT is
not strictly better than TPOT, but it often finds good pipelines much faster,
and under smaller time budgets, it outperforms TPOT on average. Moreover,
LTPOT allows for a lot of flexibility in the configuration of its structure,
and the effects of changes to these configurations remain to be explored.

## References

  * [1] Abdulrahman, S.M., Brazdil, P., Van Rijn, J.N., Vanschoren, J.: Algorithm selection via meta-learning and sample-based active testing. In: Proceedings of the 2015 International Conference on Meta-Learning and Algorithm Selection \- Volume 1455. pp. 55–66. MetaSel’15, CEUR-WS.org, Aachen, Germany, Germany (2015), http://dl.acm.org/citation.cfm?id=3053836.3053845
  * [2] Banzhaf, W., Francone, F.D., Keller, R.E., Nordin, P.: Genetic Programming: An Introduction: on the Automatic Evolution of Computer Programs and Its Applications. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1998)
  * [3] Bergstra, J.S., Bardenet, R., Bengio, Y., Kégl, B.: Algorithms for hyper-parameter optimization. In: Shawe-Taylor, J., Zemel, R.S., Bartlett, P.L., Pereira, F., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems 24, pp. 2546–2554. Curran Associates, Inc. (2011), http://papers.nips.cc/paper/4443-algorithms-for-hyper-parameter-optimization.pdf
  * [4] Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation 6(2), 182–197 (Apr 2002)
  * [5] Demsar, J.: Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research 7, 1–30 (2006)
  * [6] Feurer, M., Klein, A., Eggensperger, K., Springenberg, J., Blum, M., Hutter, F.: Efficient and robust automated machine learning. In: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems 28, pp. 2962–2970. Curran Associates, Inc. (2015), http://papers.nips.cc/paper/5872-efficient-and-robust-automated-machine-learning.pdf
  * [7] Feurer, M., Springenberg, J.T., Hutter, F.: Initializing bayesian hyperparameter optimization via meta-learning. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. pp. 1128–1135. AAAI’15, AAAI Press (2015), http://dl.acm.org/citation.cfm?id=2887007.2887164
  * [8] Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., Witten, I.H.: The weka data mining software: An update. SIGKDD Explor. Newsl. 11(1), 10–18 (Nov 2009), http://doi.acm.org/10.1145/1656274.1656278
  * [9] Hornby, G.S.: Alps: The age-layered population structure for reducing the problem of premature convergence. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. pp. 815–822. GECCO ’06, ACM, New York, NY, USA (2006), http://doi.acm.org/10.1145/1143997.1144142
  * [10] Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration (extended version). Tech. Rep. TR-2010-10, University of British Columbia, Department of Computer Science (2010), available online: http://www.cs.ubc.ca/~hutter/papers/10-TR-SMAC.pdf
  * [11] Li, L., Jamieson, K.G., DeSalvo, G., Rostamizadeh, A., Talwalkar, A.: Efficient hyperparameter optimization and infinitely many armed bandits. CoRR abs/1603.06560 (2016), http://arxiv.org/abs/1603.06560
  * [12] Olson, R.S., Bartley, N., Urbanowicz, R.J., Moore, J.H.: Evaluation of a tree-based pipeline optimization tool for automating data science. CoRR abs/1603.06212 (2016), http://arxiv.org/abs/1603.06212
  * [13] Olson, R.S., Cava, W.L., Orzechowski, P., Urbanowicz, R.J., Moore, J.H.: PMLB: A large benchmark suite for machine learning evaluation and comparison. CoRR abs/1703.00512 (2017), http://arxiv.org/abs/1703.00512
  * [14] Olson, R.S., Urbanowicz, R.J., Andrews, P.C., Lavender, N.A., Kidd, L.C., Moore, J.H.: Applications of Evolutionary Computation: 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 – April 1, 2016, Proceedings, Part I, chap. Automating Biomedical Data Science Through Tree-Based Pipeline Optimization, pp. 123–137. Springer International Publishing (2016), http://dx.doi.org/10.1007/978-3-319-31204-0_9
  * [15] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E.: Scikit-learn: Machine learning in python. J. Mach. Learn. Res. 12, 2825–2830 (Nov 2011), http://dl.acm.org/citation.cfm?id=1953048.2078195
  * [16] van Rijn, J., Abdulrahman, S., Brazdil, P., Vanschoren, J.: Fast algorithm selection using learning curves. In: Lecture Notes in Computer Science (IDA 2015). vol. 9385, pp. 298–309 (2015)
  * [17] van Rijn, J., Holmes, G., Pfahringer, B., Vanschoren, J.: Algorithm selection on data streams. Lecture Notes in Computer Science (Proceedings of Discovery Science 2014) 8777, 325–336
  * [18] Thornton, C., Hutter, F., Hoos, H.H., Leyton-Brown, K.: Auto-weka: Combined selection and hyperparameter optimization of classification algorithms. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 847–855. KDD ’13, ACM, New York, NY, USA (2013), http://doi.acm.org/10.1145/2487575.2487629
  * [19] Vanschoren, J., van Rijn, J.N., Bischl, B., Torgo, L.: Openml: Networked science in machine learning. SIGKDD Explorations 15(2), 49–60 (2013), http://doi.acm.org/10.1145/2641190.2641198
  * [20] Zutty, J., Long, D., Rohling, G.: Increasing the throughput of expensive evaluations through a vector based genetic programming framework. In: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion. pp. 1477–1478. GECCO ’16 Companion, ACM, New York, NY, USA (2016), http://doi.acm.org/10.1145/2908961.2931641

##  Appendix 0.A Additional Experiment Results

Below is a figure similar to Figure5 for the other 9 datasets in the
benchmark.

Figure 8: An overview of achieved AUROC score for each run of each method by
dataset.

Figures 9 and 10 show the score of the best pipeline and what time it was
found per dataset, method and seed.

Figure 9: Shows per dataset per seed per method when the best pipeline was
found, and its ’1-AUROC’ score. Figure 10: Shows per dataset per seed per
method when the best pipeline was found, and its ’1-AUROC’ score.


# Dynamic Inference

Aolin Xu

###### Abstract

Traditional statistical estimation, or statistical inference in general, is
static, in the sense that the estimate of the quantity of interest does not
change the future evolution of the quantity. In some sequential estimation
problems however, we encounter the situation where the future values of the
quantity to be estimated depend on the estimate of its current value. Examples
include stock price prediction by big investors, interactive product
recommendation, and behavior prediction in multi-agent systems. We may call
such problems as _dynamic inference_. In this work, a formulation of this
problem under a Bayesian probabilistic framework is given, and the optimal
estimation strategy is derived as the solution to minimize the overall
inference loss. How the optimal estimation strategy works is illustrated
through two examples, stock trend prediction and vehicle behavior prediction.
When the underlying models for dynamic inference are unknown, we can consider
the problem of _learning for dynamic inference_. This learning problem can
potentially unify several familiar machine learning problems, including
supervised learning, imitation learning, and reinforcement learning.

##  1 Introduction

Traditional statistical estimation, or statistical inference in general, is
static, in the sense that the estimate of the quantity of interest does not
affect the future evolution of the quantity. In some sequential estimation
problems however, we encounter the situation where the future values of the
quantity to be estimated depend on the estimate of its current value. Examples
include: 1) stock price prediction by big investors, where the prediction of
today’s price of a stock affects today’s investment decision, which further
changes the stock’s supply-demand status and hence its price tomorrow; 2)
interactive product recommendation, where the estimate of a customer’s
preference based on their activity leads to certain product recommendations,
which would in turn shape the customer’s future activity and preference; 3)
behavior prediction in multi-agent systems, e.g. predicting the intentions of
vehicles on the road adjacent to the ego vehicle, where the prediction of an
adjacent vehicle’s intention based on its current driving situation leads to a
certain action of the ego vehicle, which can change the future driving
situation and intention of that adjacent vehicle.

Broadly speaking, this type of interactive sequential estimation problems
arises in any autonomous agent that interacts with a system of interest,
through a measurement-inference-action loop. During the interaction, the
inference, either estimation or prediction, of a property of the system based
on the measurements of its current and past states affects the action to be
taken by the autonomous agent, which further influences the future states and
properties of the system of interest. We may call such problems as _dynamic
inference_.

In Section 2, a mathematical formulation of dynamic inference is given under a
Bayesian probabilistic framework. It is shown in Section 3 that this problem
can be converted to a Markov decision-making process (MDP), and the optimal
estimation strategy that minimizes the overall inference loss can be derived
as the optimal policy of this MDP through dynamic programming. Two examples,
stock trend prediction and vehicle behavior prediction, are given in Section 4
to illustrate how the optimal estimation strategy for dynamic inference works,
and how it differs from the solution to the traditional statistical inference.

Section 5 briefly discusses the problem of _learning for dynamic inference_ ,
which is to address the situation where the underlying probabilistic models
for dynamic inference become unknown. Learning for dynamic inference can
potentially serve as a unifying meta problem of machine learning, such that
supervised learning, imitation learning, and reinforcement learning can be
cast as its special instances. Having a good understanding of dynamic
inference and its learning extension will thus be helpful in gaining better
understandings of a broad spectrum of machine learning problems. The
formulation of dynamic inference appears to be new, but it can be related to a
variety of existing interactive decision-making problems and prediction
problems that take the consequence of the prediction into account. Moreover,
any MDP may be thought of as a dynamic inference problem. These related
problems are discussed in Section 6.

##  2 Problem formulation

###  2.1 Traditional statistical inference

In traditional statistical inference, the goal is to estimate a quantity of
interest $Y$ based on an observation $X$ that statistically depends on $Y$.
Under the Bayesian formulation, the pair
$(X,Y)\in{\mathsf{X}}\times{\mathsf{Y}}$ is modeled as a jointly distributed
random vector with distribution $P_{X,Y}$. Given a loss function
$\ell:{\mathsf{Y}}\times{\widehat{{\mathsf{Y}}}}\rightarrow\mathbb{R}$, the
optimal estimator $\psi_{\rm B}$, a.k.a. the Bayes estimator, is a map
${\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}$ that achieves the minimum
expected loss:

$\displaystyle\psi_{\rm
B}=\operatorname*{arg\,min}_{\psi:{\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}}\mathbb{E}[\ell(Y,\psi(X))].$
(1)

A basic result from estimation theory is that for any $x\in{\mathsf{X}}$, the
optimal estimate of $Y$ given $X=x$ is a minimizer of the expected posterior
loss, i.e. $\psi_{\rm
B}(x)=\operatorname*{arg\,min}_{\hat{y}\in{\widehat{{\mathsf{Y}}}}}\mathbb{E}[\ell(Y,\hat{y})|X=x]$.
The above statistical inference problem is _static_ , in the sense that only
one round of estimation is considered. When there is a need to estimate a
sequence of quantities $Y^{n}\triangleq(Y_{1},\ldots,Y_{n})$ based on
observations $X^{n}\triangleq(X_{1},\ldots,X_{n})$, if the pairs
$(X_{i},Y_{i})$ are i.i.d. for $i=1,\ldots,n$, the sequential estimation
problem to minimize the accumulated expected loss can be optimally solved by
repeatedly using the same single-round optimal estimator $\psi_{\rm B}$.

###  2.2 Dynamic inference

The problem of $n$-round dynamic inference is to sequentially estimate $n$
quantities of interest $Y^{n}$ based on observations $X^{n}$, where in each
round, the quantity of interest $Y_{i}$ only depends on the observation
$X_{i}$, while $X_{i}$ depends on the observation $X_{i-1}$ and the estimate
${\widehat{Y}}_{i-1}$ of $Y_{i-1}$ in the previous round; the estimate
${\widehat{Y}}_{i}$ of $Y_{i}$ is made potentially based on all the
information available so far, namely $(X^{i},Y^{i-1})$, with the goal of
minimizing the expected accumulated loss over the $n$ rounds. Here it is
assumed that after the $i$th round of estimation, $Y_{i}$ is revealed to the
estimator. It can also happen that $Y^{n}$ are never revealed during the
process, in which case ${\widehat{Y}}_{i}$ is estimated only based on $X^{i}$.
Nevertheless, it will be shown in Section 3 that an optimal estimation
strategy can estimate $Y_{i}$ only based on the instantaneous observation
$X_{i}$, no matter $Y^{i-1}$ are available or not.

Formally, we assume the knowledge of the distribution $P_{X_{1}}$ of the
initial observation, the probability transition kernel
$P{\raisebox{-2.0pt}{$\scriptstyle X_{i}|X_{i-1},{\widehat{Y}}_{i-1}$}}$ of
the $i$th observation given the observation and the estimate in the previous
round, $i=2,\ldots,n$, and the probability transition kernel $P_{Y_{i}|X_{i}}$
of the $i$th quantity of interest given the $i$th observation, $i=1,\ldots,n$.
We may call these two types of probability transition kernels the
_observation-transition model_ and the _quantity-generation model_ ,
respectively. The estimates ${\widehat{Y}}^{n}$ are sequentially made
according to an _estimation strategy_ :

######  Definition 1.

An estimation strategy for an $n$-round dynamic inference is a sequence of
estimators $\psi^{n}=(\psi_{1},\ldots,\psi_{n})$, where
$\psi_{i}:{\mathsf{X}}^{i}\times{\mathsf{Y}}^{i-1}\rightarrow{\widehat{{\mathsf{Y}}}}$
is the estimator used in the $i$th round, $i=1,\ldots,n$, which maps the
history of observations and revealed quantities of interest $(X^{i},Y^{i-1})$
to an estimate ${\widehat{Y}}_{i}$ of $Y_{i}$, such that
${\widehat{Y}}_{i}=\psi_{i}(X^{i},Y^{i-1})$.

Any specification of $P_{X_{1}}$, $(P{\raisebox{-2.0pt}{$\scriptstyle
X_{i}|X_{i-1},{\widehat{Y}}_{i-1}$}})_{i=2}^{n}$,
$(P_{Y_{i}|X_{i}})_{i=1}^{n}$ and $\psi^{n}$ defines a joint distribution of
all the random variables $(X^{n},Y^{n},{\widehat{Y}}^{n})$ under
consideration. The Bayesian network of the random variables in dynamic
inference with a Markov estimation strategy, meaning that each estimate has
the form $\psi_{i}:{\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}$, is
illustrated in Fig. 1.

Figure 1: Bayesian network of the random variables under consideration with
$n=4$. Here we assume the estimates are made with Markov estimators, such that
${\widehat{Y}}_{i}=\psi_{i}(X_{i})$.

We use a loss function
$\ell:{\mathsf{X}}\times{\mathsf{Y}}\times{\widehat{{\mathsf{Y}}}}\rightarrow\mathbb{R}$
to evaluate the estimate made in each round in dynamic inference. This loss
function is a generalization of the one used in statistical inference, in the
sense that the estimate in each round is evaluated in the context of the
observation in that round. Given an estimation strategy $\psi^{n}$, we define
its _inference loss_ as the expected accumulated loss over the $n$ rounds,
$\mathbb{E}\big{[}\sum_{i=1}^{n}\ell(X_{i},Y_{i},{\widehat{Y}}_{i})\big{]}$.
The goal of dynamic inference is to find an estimation strategy to minimize
the inference loss:

$\displaystyle\operatorname*{arg\,min}_{\psi^{n}}\,\,\mathbb{E}\Big{[}\sum_{i=1}^{n}\ell(X_{i},Y_{i},{\widehat{Y}}_{i})\Big{]},$
(2)

where ${\widehat{Y}}_{i}=\psi_{i}(X^{i},Y^{i-1})$. Comparing with the
statistical inference problem in (1), we summarize the two distinctive
features of dynamic inference:

  * •

The joint distribution of the pair $(X_{i},Y_{i})$ changes in each round in a
controlled manner, as it depends on $(X_{i-1},{\widehat{Y}}_{i-1})$.

  * •

The loss in each round is contextual, as it depends on $X_{i}$.

##  3 Optimal estimation strategy

In this section we show that the dynamic inference problem can be converted to
a Markov decision process, and the optimal estimation strategy can be found
via dynamic programming.

###  3.1 MDP reformulation

####  3.1.1 Equivalent expression of inference loss

For a given loss function
$\ell:{\mathsf{X}}\times{\mathsf{Y}}\times{\widehat{{\mathsf{Y}}}}\rightarrow\mathbb{R}$
and a joint distribution of $(X,Y,{\widehat{Y}})$, we can define a
corresponding _observation-estimate loss function_
$\bar{\ell}:{\mathsf{X}}\times{\widehat{{\mathsf{Y}}}}\rightarrow\mathbb{R}$
as

$\displaystyle\bar{\ell}(x,\hat{y})\triangleq\mathbb{E}[\ell(x,Y,\hat{y})|X=x,{\widehat{Y}}=\hat{y}]$
(3)

for $(x,\hat{y})\in{\mathsf{X}}\times{\widehat{Y}}$. From the specification of
the joint distribution of the random variables in the previous section, we
know that in dynamic inference $Y_{i}$ is conditionally independent of
${\widehat{Y}}_{i}$ given $X_{i}$, therefore for any realization
$(x_{i},\hat{y}_{i})$ of $(X_{i},{\widehat{Y}}_{i})$, the value of the $i$th
observation-estimate loss $\bar{\ell}(x_{i},\hat{y}_{i})$ can be computed as

$\displaystyle\bar{\ell}(x_{i},\hat{y}_{i})=\mathbb{E}[\ell(x_{i},Y_{i},\hat{y}_{i})|X_{i}=x_{i}].$
(4)

We see that $\bar{\ell}$ as a function of $(x_{i},\hat{y}_{i})$ is determined
by $\ell$ and $P_{Y_{i}|X_{i}}$, and does not depend on the estimator
$\psi_{i}$. This fact is crucial for the optimality proof later. With the
above definition, the inference loss can be expressed in terms of the
observation-estimate loss:

######  Lemma 1.

For any estimation strategy, the inference loss in (2) can be rewritten as

$\displaystyle\mathbb{E}\Big{[}\sum_{i=1}^{n}\ell(X_{i},Y_{i},{\widehat{Y}}_{i})\Big{]}=\mathbb{E}\Big{[}\sum_{i=1}^{n}\bar{\ell}(X_{i},{\widehat{Y}}_{i})\Big{]}.$
(5)

###### Proof.

For each $i=1,\ldots,n$,

$\displaystyle\mathbb{E}[\ell(X_{i},Y_{i},{\widehat{Y}}_{i})]$
$\displaystyle=\mathbb{E}\big{[}\mathbb{E}[\ell(X_{i},Y_{i},{\widehat{Y}}_{i})|X^{i},Y^{i-1}]\big{]}$
(6)
$\displaystyle=\mathbb{E}\big{[}\mathbb{E}[\ell(X_{i},Y_{i},{\widehat{Y}}_{i})|X_{i},{\widehat{Y}}_{i}]\big{]}$
(7) $\displaystyle=\mathbb{E}[\bar{\ell}(X_{i},{\widehat{Y}}_{i})]$ (8)

where (7) is a consequence of the fact that ${\widehat{Y}}_{i}$ is determined
by $(X^{i},Y^{i-1})$ and the fact that $Y_{i}$ is conditionally independent of
$(X^{i-1},Y^{i-1})$ given $X_{i}$; and (8) is due to the definition of
$\bar{\ell}$. The claim then follows from the fact that
$\mathbb{E}\big{[}\sum_{i=1}^{n}\ell(X_{i},Y_{i},{\widehat{Y}}_{i})\big{]}=\sum_{i=1}^{n}\mathbb{E}\big{[}\ell(X_{i},Y_{i},{\widehat{Y}}_{i})\big{]}.$
∎

With Lemma 1, the optimization problem in (2) becomes equivalent to

$\displaystyle\operatorname*{arg\,min}_{\psi^{n}}\,\,J(\psi_{n}),$ (9)

where
$J(\psi_{n})\triangleq\mathbb{E}\big{[}\sum_{i=1}^{n}\bar{\ell}(X_{i},{\widehat{Y}}_{i})\big{]}$
equals to the inference loss, and ${\widehat{Y}}_{i}=\psi_{i}(X^{i},Y^{i-1})$.

####  3.1.2 Optimality of Markov estimators

Next, we show that the search space of the optimization problem in (9) can be
restricted to Markov estimators
$\bar{\psi}_{i}:{\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}$, such that
${\widehat{Y}}_{i}=\bar{\psi}_{i}(X_{i})$. We start with a lemma known as
Blackwell’s principle of irrelevant information [1], and provide a proof for
completeness.

######  Lemma 2.

For any fixed function $f:{\mathsf{U}}\times{\mathsf{V}}\rightarrow\mathbb{R}$
and for any jointly distributed pair $(U,Z)$,

$\displaystyle\min_{g:{\mathsf{U}}\times{\mathsf{Z}}\rightarrow{\mathsf{V}}}\mathbb{E}\big{[}f\big{(}U,g(U,Z)\big{)}\big{]}=\min_{g:{\mathsf{U}}\rightarrow{\mathsf{V}}}\mathbb{E}\big{[}f\big{(}U,g(U)\big{)}\big{]}.$
(10)

###### Proof.

The left side of (10) is the Bayes risk of estimating $U$ based on $(U,Z)$,
defined with respect to the loss function $f$, and can be written as
$R_{f}(U|U,Z)$; while the right side of (10) is the Bayes risk of estimating
$U$ based on $U$ itself, also defined with respect to the loss function $f$,
and can be written as $R_{f}(U|U)$. It is clear from their definitions that
$R_{\ell}(U|U,Z)\leq R_{\ell}(U|U)$. It also follows from a data processing
inequality of Bayes risk [2, Lemma 1] that

$\displaystyle R_{\ell}(U|U,Z)\geq R_{\ell}(U|U),$ (11)

as $U-U-(U,Z)$ form a Markov chain. Hence $R_{f}(U|U,Z)=R_{f}(U|U)$, which
proves the claim. ∎

The first application of Lemma 2 is to prove that the last estimator of an
optimal estimation strategy can be replaced by a Markov one, which preserves
the optimality.

######  Lemma 3 (Last-round lemma).

Given any estimation strategy $\psi^{n}$, there exists a Markov estimator
$\bar{\psi}_{n}:{\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}$, such that
$J(\psi_{1},\ldots,\psi_{n-1},\bar{\psi}_{n})\leq J(\psi^{n}).$

###### Proof.

According to Lemma 1, the inference loss of $\psi^{n}$ can be written as

$\displaystyle J(\psi^{n})$
$\displaystyle=\mathbb{E}\Big{[}\sum_{i=1}^{n-1}\bar{\ell}(X_{i},{\widehat{Y}}_{i})\Big{]}+\mathbb{E}\big{[}\bar{\ell}(X_{n},\psi_{n}(X^{n},Y^{n-1}))\big{]}.$
(12)

Since the first expectation in (12) does not depend on $\psi_{n}$, it suffices
to show that there exists a Markov estimator
$\bar{\psi}_{n}:{\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}$, such that

$\displaystyle\mathbb{E}\big{[}\bar{\ell}\big{(}X_{n},\bar{\psi}_{n}(X_{n})\big{)}\big{]}\leq\mathbb{E}\big{[}\bar{\ell}\big{(}X_{n},\psi_{n}(X^{n},Y^{n-1})\big{)}\big{]}.$
(13)

The existence of such an estimator is guaranteed by Lemma 2. ∎

Lemma 2 can be further used to prove that whenever the last estimator is
Markov, its preceding estimator can also be replaced by a Markov one which
preserves the optimality.

######  Lemma 4 ($(i-1)$th-round lemma).

For any $i\geq 2$, given any estimation strategy
$(\psi_{1},\ldots,\psi_{i-1},\bar{\psi}_{i})$ for an $i$-round dynamic
inference, if the last estimator is a Markov one
$\bar{\psi}_{i}:{\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}$, then there
exists a Markov estimator
$\bar{\psi}_{i-1}:{\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}$ for the
$(i-1)$th round, such that
$J(\psi_{1},\ldots,\psi_{i-2},\bar{\psi}_{i-1},\bar{\psi}_{i})\leq
J(\psi_{1},\ldots,\psi_{i-1},\bar{\psi}_{i}).$

###### Proof.

According to Lemma 1, the inference loss of the given
$(\psi_{1},\ldots,\psi_{i-1},\bar{\psi}_{i})$ is

$\displaystyle
J(\psi_{1},\ldots,\psi_{i-1},\bar{\psi}_{i})=\mathbb{E}\Big{[}\sum_{j=1}^{i-2}\bar{\ell}(X_{j},{\widehat{Y}}_{j})\Big{]}+\mathbb{E}\big{[}\bar{\ell}(X_{i-1},{\widehat{Y}}_{i-1})\big{]}+\mathbb{E}\big{[}\bar{\ell}(X_{i},\bar{\psi}_{i}(X_{i})\big{)}\big{]}.$
(14)

Since the first expectation in (14) does not depend on $\psi_{i-1}$, it
suffices to show that there exists a Markov estimator
$\bar{\psi}_{i-1}:{\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}$, such that

$\displaystyle\mathbb{E}\big{[}\bar{\ell}(X_{i-1},\bar{\psi}_{i-1}(X_{i-1})\big{)}\big{]}+\mathbb{E}\big{[}\bar{\ell}(\bar{X}_{i},\bar{\psi}_{i}(\bar{X}_{i})\big{)}\big{]}\leq\mathbb{E}\big{[}\bar{\ell}(X_{i-1},{\widehat{Y}}_{i-1}\big{)}\big{]}+\mathbb{E}\big{[}\bar{\ell}(X_{i},\bar{\psi}_{i}(X_{i})\big{)}\big{]},$
(15)

where $\bar{X}_{i}$ on the left side is the observation in the $i$th round
when the Markov estimator $\bar{\psi}_{i-1}$ is used in the $(i-1)$th round.
To get around with the dependence of $X_{i}$ on $\psi_{i-1}$, we write the
second expectation on the right side of (15) as

$\displaystyle\mathbb{E}\big{[}\mathbb{E}\big{[}\bar{\ell}(X_{i},\bar{\psi}_{i}(X_{i})\big{)}\big{|}X_{i-1},{\widehat{Y}}_{i-1}\big{]}\big{]}$
(16)

and notice that the inner conditional expectation as a function of
$(X_{i-1},{\widehat{Y}}_{i-1})$ does not depend on $\psi_{i-1}$. This is
because the conditional distribution of $X_{i}$ given
$(X_{i-1},{\widehat{Y}}_{i-1})$ is specified by the probability transition
kernel $P{\raisebox{-2.0pt}{$\scriptstyle
X_{i}|X_{i-1},{\widehat{Y}}_{i-1}$}}$. It follows that the right side of (15)
can be written as

$\displaystyle\mathbb{E}\Big{[}\bar{\ell}\big{(}X_{i-1},{\widehat{Y}}_{i-1}\big{)}+\mathbb{E}\big{[}\bar{\ell}\big{(}X_{i},\bar{\psi}_{i}(X_{i})\big{)}\big{|}X_{i-1},{\widehat{Y}}_{i-1}\big{]}\Big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}\big{[}f\big{(}X_{i-1},{\widehat{Y}}_{i-1}\big{)}\big{]}$
(17) $\displaystyle=$
$\displaystyle\mathbb{E}\big{[}f\big{(}X_{i-1},\psi_{i-1}(X^{i-1},Y^{i-2})\big{)}\big{]},$
(18)

where the function $f$ does not depend on $\psi_{i-1}$. It follows from Lemma
2 that there exists an estimator
$\bar{\psi}_{i-1}:{\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}$, such that

$\displaystyle\mathbb{E}\big{[}f\big{(}X_{i-1},\psi_{i-1}(X^{i-1},Y^{i-2})\big{)}\big{]}$
$\displaystyle\geq$
$\displaystyle\mathbb{E}\big{[}f\big{(}X_{i-1},\bar{\psi}_{i-1}(X_{i-1})\big{)}\big{]}$
(19) $\displaystyle=$
$\displaystyle\mathbb{E}\Big{[}\bar{\ell}(X_{i-1},\bar{\psi}_{i-1}(X_{i-1})\big{)}+\mathbb{E}\big{[}\bar{\ell}(\bar{X}_{i},\bar{\psi}_{i}(\bar{X}_{i})\big{)}\big{|}X_{i-1},\bar{\psi}_{i-1}(X_{i-1})\big{]}\Big{]}$
(20) $\displaystyle=$
$\displaystyle\mathbb{E}\big{[}\bar{\ell}(X_{i-1},\bar{\psi}_{i-1}(X_{i-1})\big{)}\big{]}+\mathbb{E}\big{[}\bar{\ell}(\bar{X}_{i},\bar{\psi}_{i}(\bar{X}_{i})\big{)}\big{]},$
(21)

which proves (15) and the claim. ∎

With Lemma 3 and Lemma 4, we can finally prove the optimality of Markov
estimators.

######  Theorem 1.

The minimum of $J(\psi^{n})$ in (9) can be achieved by an estimation strategy
$\bar{\psi}^{n}$ with Markov estimators
$\bar{\psi}_{i}:{\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}$,
$i=1,\ldots,n$, such that ${\widehat{Y}}_{i}=\bar{\psi}_{i}(X_{i})$.

###### Proof.

Picking an optimal estimation strategy $\psi^{n}$, we first replace its last
estimator by a Markov one that preserves the optimality of the strategy, as
guaranteed by Lemma 3. Then, for $i=n,\ldots,2$, we repeatedly replace the
$(i-1)$th estimator by a Markov one that preserves the optimality of the
previous strategy, as guaranteed by Lemma 4 and the additive structure of the
inference loss as in $J(\psi^{n})$. Finally we obtain an estimation strategy
consisting of Markov estimators achieving the same inference loss as the
originally picked strategy. ∎

####  3.1.3 Conversion to MDP

Theorem 1 with Lemma 1 imply that the original dynamic inference problem in
(2) is equivalent to

$\displaystyle\operatorname*{arg\,min}_{\psi^{n}}\mathbb{E}\Big{[}\sum_{i=1}^{n}\bar{\ell}(X_{i},{\widehat{Y}}_{i})\Big{]},\quad{\widehat{Y}}_{i}=\psi_{i}(X_{i}).$
(22)

With this reformulation, we see that the unknown quantities $Y_{i}$ do not
appear in the loss function in (22) any more, and the optimization problem
becomes a standard MDP: the observations $X^{n}$ become the states in this
MDP, the estimates ${\widehat{Y}}^{n}$ become the actions, the probability
transition kernel $P{\raisebox{-2.0pt}{$\scriptstyle
X_{i}|X_{i-1},{\widehat{Y}}_{i-1}$}}$ now defines the controlled state
transition, and any Markov estimation strategy $\psi^{n}$ becomes a policy of
this MDP. The goal of dynamic inference then becomes finding the optimal
policy of this MDP to minimize the expected accumulated loss with respect to
$\bar{\ell}$. Conversely, the solution to the MDP will be an optimal
estimation strategy for dynamic inference.

###  3.2 Solution via dynamic programming

####  3.2.1 Optimal estimation strategy

From the theory of MDP [3] it is known that the optimal policy for the MDP in
(22), or the optimal estimation strategy for dynamic inference, can be found
via dynamic programming. To derive the optimal estimators, define the
functions $Q^{*}_{i}:{\mathsf{X}}\times{\widehat{Y}}\rightarrow\mathbb{R}$ and
$V^{*}_{i}:{\mathsf{X}}\rightarrow\mathbb{R}$ recursively in backward as
$Q^{*}_{n}(x,\hat{y})\triangleq\bar{\ell}(x,\hat{y})$,

$\displaystyle
V^{*}_{i}(x)\triangleq\min_{\hat{y}\in{\widehat{{\mathsf{Y}}}}}Q^{*}_{i}(x,\hat{y}),\quad
i=n,\ldots,1,$ (23)

and

$\displaystyle Q^{*}_{i}(x,\hat{y})$
$\displaystyle\triangleq\bar{\ell}(x,\hat{y})+\mathbb{E}[V^{*}_{i+1}(X_{i+1})|X_{i}=x,{\widehat{Y}}_{i}=\hat{y}],\quad
i=n-1,\ldots,1.$ (24)

The optimal estimate to make in the $i$th round when $X_{i}=x$ is then

$\displaystyle\psi_{i}^{*}(x)\triangleq\operatorname*{arg\,min}_{\hat{y}\in{\widehat{{\mathsf{Y}}}}}Q^{*}_{i}(x,\hat{y}),\quad
i=1,\ldots,n.$ (25)

####  3.2.2 Minimum inference loss and loss-to-go

For any estimation strategy $\psi^{n}$, we can define its loss-to-go at the
$i$th round of estimation when $X_{i}=x$ as the conditional expected loss
accumulated from the $i$th round to the final round given that the observation
in the $i$th round is $x$:

$\displaystyle
V_{i}(x;\psi^{n})\triangleq\mathbb{E}\Big{[}\sum_{j=i}^{n}\ell(X_{j},Y_{j},{\widehat{Y}}_{j})\Big{|}X_{i}=x\Big{]}.$
(26)

The following theorem states that the estimation strategy
$(\psi^{*}_{1},\ldots,\psi^{*}_{n})$ derived from dynamic programming not only
achieves the minimum inference loss, but also achieves the minimum loss-to-go
in each round with any observation in that round.

######  Theorem 2.

The estimators $(\psi^{*}_{1},\ldots,\psi^{*}_{n})$ defined in (25) constitute
an optimal estimation strategy for dynamic inference, which achieves the
minimum in (2). Moreover, for any Markov estimation strategy $\psi^{n}$ with
$\psi_{i}:{\mathsf{X}}\rightarrow{\widehat{{\mathsf{Y}}}}$, its loss-to-go
satisfies

$\displaystyle V_{i}(x;\psi^{n})\geq V^{*}_{i}(x)$ (27)

for all $x\in{\mathsf{X}}$ and $i=1,\ldots,n$, with equality if
$\psi_{j}(x)=\psi_{j}^{*}(x)$ for all $x\in{\mathsf{X}}$ and $j\geq i$.

###### Proof.

The first claim stating that the estimation strategy
$(\psi^{*}_{1},\ldots,\psi^{*}_{n})$ achieves the minimum in (2) follows from
the equivalence between the original problem in (2) and the MDP reformulation
in (22) as discussed in Section 3.1.3, and from the well-known optimality of
the solution via dynamic programming to MDP [3].

The second claim can be proved via backward induction. Consider an arbitrary
Markov estimation strategy $\psi^{n}$.

  * •

In the final round, for all $x\in{\mathsf{X}}$,

$\displaystyle V_{n}(x;\psi^{n})$
$\displaystyle=\mathbb{E}[\ell(x,Y_{n},\psi_{n}(x))|X_{n}=x]$ (28)
$\displaystyle=\bar{\ell}(x,\psi_{n}(x))$ (29) $\displaystyle\geq
V^{*}_{n}(x),$ (30)

where (28) follows from the definition of $V_{n}$ in (26); (29) follows from
the way how $\bar{\ell}$ can be computed as in (4); and (30) follows from the
definition of $V^{*}_{n}$ above (24), while the equality holds if
$\psi_{n}(x)=\psi^{*}_{n}(x)$.

  * •

For $i=n-1,\ldots,1$, as the inductive assumption, suppose (27) holds in the
$(i+1)$th round. We first show a self-recursive expression of
$V_{i}(x;\psi^{n})$:

$\displaystyle V_{i}(x;\psi^{n})$
$\displaystyle=\mathbb{E}\Big{[}\sum_{j=i}^{n}\ell(X_{j},Y_{j},{\widehat{Y}}_{j})\Big{|}X_{i}=x\Big{]}$
(31)
$\displaystyle=\mathbb{E}[\ell(X_{i},Y_{i},{\widehat{Y}}_{i})|X_{i}=x]+\mathbb{E}\Big{[}\sum_{j=i+1}^{n}\ell(X_{j},Y_{j},{\widehat{Y}}_{j})\Big{|}X_{i}=x\Big{]}$
(32)
$\displaystyle=\mathbb{E}\big{[}\mathbb{E}[\ell(X_{i},Y_{i},{\widehat{Y}}_{i})|X_{i}=x,{\widehat{Y}}_{i}]\big{|}X_{i}=x\big{]}+$
$\displaystyle\quad\,\,\mathbb{E}\Big{[}\mathbb{E}\Big{[}\sum_{j=i+1}^{n}\ell(X_{j},Y_{j},{\widehat{Y}}_{j})\Big{|}X_{i}=x,X_{i+1}\Big{]}\Big{|}X_{i}=x\Big{]}$
(33)
$\displaystyle=\mathbb{E}\big{[}\bar{\ell}(x,{\widehat{Y}}_{i})\big{|}X_{i}=x\big{]}+\mathbb{E}\Big{[}\mathbb{E}\Big{[}\sum_{j=i+1}^{n}\ell(X_{j},Y_{j},{\widehat{Y}}_{j})\Big{|}X_{i+1}\Big{]}\Big{|}X_{i}=x\Big{]}$
(34)
$\displaystyle=\bar{\ell}(x,\psi_{i}(x))+\mathbb{E}\big{[}V_{i}(X_{i+1};\psi^{n})|X_{i}=x\big{]}$
(35)

where the first term of (34) follows from the definition of $\bar{\ell}$ in
(3), while the second term of (34) follows from the fact that $X_{i}$ is
conditionally independent of
$(X_{i+1}^{n},Y_{i+1}^{n},{\widehat{Y}}_{i+1}^{n})$ given $X_{i+1}$, which is
a consequence of the assumption that the estimators under consideration are
Markov and the specification of the joint distribution of
$(X^{n},Y^{n},{\widehat{Y}}^{n})$ in Section 2. Then,

$\displaystyle V_{i}(x;\psi^{n})$
$\displaystyle\geq\bar{\ell}(x,\psi_{i}(x))+\mathbb{E}\big{[}V^{*}_{i}(X_{i+1})|X_{i}=x\big{]}$
(36)
$\displaystyle=\bar{\ell}(x,\psi_{i}(x))+\mathbb{E}\big{[}V^{*}_{i}(X_{i+1})|X_{i}=x,{\widehat{Y}}_{i}=\psi_{i}(x)\big{]}$
(37) $\displaystyle=Q^{*}_{i}(x,\psi_{i}(x))$ (38) $\displaystyle\geq
V^{*}_{i}(x)$ (39)

where (36) follows from the inductive assumption; (37) follows from the fact
that ${\widehat{Y}}_{i}$ is determined given $X_{i}=x$ through the Markov
estimator $\psi_{i}$; (38) follows from the definition of $Q^{*}_{i}$ in (24);
and the final equality condition follows from the definitions of $V^{*}_{i}$
above (24) and $\psi^{*}_{i}$ in (25).

This proves the second claim. ∎

A consequence of Theorem 2 is that the minimum loss-to-go at the $i$th round
can be expressed in terms of $V^{*}_{i}$. Moreover, once the values of
$V^{*}_{i}(x)$ for all $x\in{\mathsf{X}}$ and $i=1,\ldots,n$ are computed, the
optimal estimation strategy for any $(n-i+1)$-round dynamic inference with the
same model for $j=i,\ldots,n$ can be determined by these values and the
observation-estimate loss function $\bar{\ell}$. These results are stated in
the following corollary.

######  Corollary 1.

For any $i=1,\ldots,n$ and any initial distribution $P_{X_{i}}$,

$\displaystyle\min_{\psi_{i},\ldots,\psi_{n}}\,\,\mathbb{E}\Big{[}\sum_{j=i}^{n}\ell(X_{j},Y_{j},{\widehat{Y}}_{j})\Big{]}=\mathbb{E}[V^{*}_{i}(X_{i})],$
(40)

and the minimum is achieved by the estimators
$(\psi^{*}_{i},\ldots,\psi^{*}_{n})$ defined in (25).

###  3.3 An illustrative example

We now work out an example to illustrate how an optimal estimation strategy
for dynamic inference works. Consider a situation where the observations, the
quantities of interest, and the estimates all take binary values, i.e.
${\mathsf{X}}={\mathsf{Y}}={\widehat{{\mathsf{Y}}}}=\\{0,1\\}$. The
observation-transition model is assumed to be stationary and deterministic,
such that $X_{i}=1-X_{i-1}$ if ${\widehat{Y}}_{i-1}=0$, while $X_{i}=X_{i-1}$
if ${\widehat{Y}}_{i-1}=1$, as depicted in Fig. 2. The quantity-generation
model is also stationary and is described by $P(Y=1|X=0)=0.1$ and
$P(Y=1|X=1)=0.6$. The loss function neglects the observation and takes the
form $\ell(x,y,\hat{y})=\mathbf{1}\\{y\neq\hat{y}\\}.$

Figure 2: An example of stationary and deterministic observation-transition
model. Figure 3: Unrolled observation-transition diagram for the dynamic
inference example given in Section 3.3, with $n=6$. The value of $V^{*}$ and
the optimal estimate at each observation are labeled. A solid branch indicates
an optimal estimate, while a dashed branch indicates a non-optimal one. The
three blue branches indicate the optimal estimates for dynamic inference that
are different from the optimal single-round estimates.

With this setup, the goal of dynamic inference is to minimize the expected
number of wrong estimates during $n$ rounds of estimation. The optimal
estimation strategy can be easily found by the dynamic programming procedure
presented in Section 3.2. With $n=6$, the resulting values of the $V^{*}$
function are labeled at each observation in the unrolled observation-
transition diagram in Fig. 3. The optimal estimate at each observation is also
labeled: a solid branch indicates an optimal estimate, while a dashed branch
indicates a non-optimal one. We see that at each observation, the optimal
estimate for dynamic inference can be different from that for the single-round
estimation. For example, at $X_{1}=1$, $X_{3}=1$ and $X_{5}=1$, the optimal
estimate for dynamic inference is ${\widehat{Y}}=0$, whereas the optimal
estimate for the single-round estimation at these observations would be
${\widehat{Y}}=1$ to minimize $\mathbb{E}[\mathbf{1}\\{Y\neq\psi(X)\\}]$.

This example reveals a key difference between dynamic inference and the
traditional statistical inference: in dynamic inference, the optimal estimate
in each round strives to balance the loss-to-incur in that round and the loss-
to-go from that round. Consequently, an optimal estimation strategy may need
to, at least occasionally, make non-optimal single-round estimates, in order
to steer the future observations toward those with which the associated
quantities of interest are easier to estimate or less costly if inaccurately
estimated.

##  4 Two applications

Having formulated the dynamic inference problem and derived its solution, in
this section we study its applications to real challenges. The two examples
given below are simplistic, but they capture the essence of how dynamic
inference can be used to model and solve various sequential and interactive
estimation or prediction problems.

###  4.1 Stock trend prediction

The first application is the prediction by big investors of the trend of
stock, which could be the trend of the price of an individual stock or the
index of a bundle of stocks. The trend, either rising or falling,
statistically depends on some observable market signal, e.g. the supply-demand
profile of the stocks under consideration. The prediction is sequentially made
for several rounds, e.g. one round each day for that day’s trend, each based
on the past observed market signals. Once a prediction is made, it influences
that day’s investment decision and hence the supply-demand profile of the
stocks under consideration, which will be reflected by the market signal in
the next day and will further influence the next day’s trend.

Formally, for $n$ rounds of prediction, let $Y_{i}\in\\{0,1\\}$ be the trend
in the $i$th round, which is to be predicted as ${\widehat{Y}}_{i}$ based on
the observable market signal $X_{i}$ in that round. To have the simplest
observation model, we consider the situation where $X_{i}$’s take only two
values $\\{0,1\\}$. The transition model of the next round’s market signal
given the signal and prediction in the current round can then be described by
$P{\raisebox{-2.0pt}{$\scriptstyle X_{i}|X_{i-1},{\widehat{Y}}_{i-1}$}}$. A
stationary such model is shown in Fig. 4. Additionally, the dependence of the
trend on the market signal can be described by $P_{Y_{i}|X_{i}}$, e.g.
$P(Y=1|X=0)=0.4$ and $P(Y=1|X=1)=0.7$ where the trend positively correlates
with the market signal. The loss function can be simply
$\ell(x,y,\hat{y})=\mathbf{1}\\{y\neq\hat{y}\\}$.

Figure 4: A stationary observation-transition model for stock trend
prediction. The solid arrows represent the deterministic transition
$X_{i}={\widehat{Y}}_{i-1}$. Figure 5: Unrolled observation-transition diagram
for the stock trend prediction example, with $n=6$. The value of $V^{*}$ and
the optimal prediction at each observation are labeled. A solid branch
indicates an optimal prediction, while a dashed branch indicates a non-optimal
one. The three blue branches indicate the optimal predictions for dynamic
inference that are different from the optimal single-round predictions.

With all these elements specified, the problem is recognized as a dynamic
inference problem similar to the example presented in Section 3.3, only with a
more general observation-transition model. Figure 5 shows the optimal
estimation strategy of this example when the observation-transition model is
deterministic, such that $X_{i}={\widehat{Y}}_{i-1}$. Similar to the example
given in Section 3.3, we see from Fig. 5 that at $X_{1}=0$, $X_{2}=0$ and
$X_{3}=0$, the optimal prediction for dynamic inference is different from the
optimal single-round prediction. These predictions are made to steer the
market signal to $1$, with which it is more certain that the trend will be
rising according to $P_{Y|X}$, hence smaller prediction error probability to
occur. Only when $i\geq 4$, the optimal predictions coincide with the optimal
single-round predictions, as the future prediction errors to accumulate weigh
less toward the end of dynamic inference.

###  4.2 Vehicle behavior prediction

Another challenging problem that could be cast as dynamic inference is
behavior prediction of vehicles on the road. For example, a desired feature of
a self-driving system is to predict whether the following vehicle in the
neighbor lane would yield if the ego vehicle initiates a cut-in to that lane,
whenever there is a need for lane change. This task may be termed as _yield
prediction_ , which can be sequential and interactive especially when the
traffic is dense: the predicted intention determines the action to be taken by
the ego vehicle, e.g. to turn on the blinker and initiate the cut-in when the
following vehicle is predicted to yield, or not to cut-in and shoot for
another gap when it is predicted not to yield; in response to the ego
vehicle’s behavior and according to the driving situation, the following
vehicle would either slow down or accelerate, which can change the driving
situation of the two vehicles and affect their subsequent behaviors; the
interaction continues until the cut-in is completed due to a yield by some
vehicle, or given up due to an opposite.

As in the stock trend prediction, we can formally define a dynamic inference
problem for yield prediction. Suppose the prediction can be deconstructed into
$n$ rounds. For the $i$th round, let $X_{i}$ denote the driving situation,
which could be the positions and velocities of the vehicles under
consideration, and let
$Y_{i}\in\\{{\mathsf{yield}},{\mathsf{not\,\,yield}}\\}$ represent the
intention of the following vehicle. In the simplest setting, $X_{i}$ could be
just the longitudinal bumper to bumper distance between the two vehicles, and
the probabilistic model relating $Y_{i}$ to $X_{i}$ could be
$P_{Y_{i}|X_{i}}({\mathsf{yield}}|x)=\sigma(\beta(x-d_{\rm c}))$where
$\sigma(s)=\frac{1}{1+e^{-s}}$ is the logistic function, $\beta>0$ is a
tunable parameter, and $d_{\rm c}$ is a critical distance that can be
empirically determined. The observation-transition model in yield prediction
is _non-stationary_ and depends on the design of the planner in the self-
driving system. For example, when $X_{i}$ is small and
${\widehat{Y}}_{i}=\mathsf{not\,\,yield}$, depending on the planner, $X_{i+1}$
could be either larger if the planner decides to increase the gap and still
aims to cut-in, or smaller if the planner decides to slow down to shoot for
another gap behind the following vehicle. Another feature of this problem is
that the loss function should be _contextual_ and carefully designed. For
example, when $Y_{i}=\mathsf{yield}$ and
${\widehat{Y}}_{i}=\mathsf{not\,\,yield}$, the loss can be small and
proportional to $X_{i}$, to moderately penalize a wasted chance for cut-in. On
the other hand, when $Y_{i}=\mathsf{not\,\,yield}$ and
${\widehat{Y}}_{i}=\mathsf{yield}$, the loss should be large especially when
$X_{i}$ is small, to heavily penalize a wrong prediction that can lead to a
dangerous situation. With all the elements specified, the problem can in
principle be solved through dynamic programming as in Section 3.2, to minimize
the overall prediction cost.

To better illustrate the idea, three typical cases that can be encountered by
the yield prediction are depicted in Fig. 6. In the first case, $X_{1}>d_{\rm
c}$, $Y_{1}=\mathsf{yield}$, and ${\widehat{Y}}_{1}=\mathsf{yield}$. The ego
vehicle initiates the cut-in by turning on the blinker, which results in a
slow-down of the following vehicle, allowing the cut-in to be completed. There
is only one round of prediction in this case. In the second case,
$X_{1}<d_{\rm c}$, $Y_{1}=\mathsf{not\,\,yield}$, and
${\widehat{Y}}_{1}=\mathsf{yield}$. The ego vehicle initiates the cut-in by
turning on the blinker, which results in an acceleration of the following
vehicle, not allowing the cut-in to be completed, and leads to a dangerous
driving situation. The ego vehicle then starts a second round of prediction
under this situation. In the third case, $X_{1}<d_{\rm c}$ and
${\widehat{Y}}_{1}=\mathsf{not\,\,yield}$. Since the ego vehicle predicts that
the following vehicle will not yield if the blinker is on, it does not
initiate a cut-in, and slows down to shoot for a gap behind the following
vehicle. It then starts a second round of prediction, which can potentially be
easier and less costly compared with the first round of prediction. By
properly specifying the models and the loss function, a yield predictor
designed under the framework of dynamic inference should enable the ego
vehicle to drive in the first and the third case most of the time according to
different driving situations, and avoid the behavior as in the second
situation, unless it is deliberately designed to support aggressive cut-in.

Figure 6: Three typical cases of interactive vehicle behaviors in yield
prediction.

##  5 Learning for dynamic inference

Solving the dynamic inference problem requires the knowledge of two important
elements: the observation-transition model and the quantity-generation model.
However, in many practically interesting situations, we may not have such
knowledge. Instead, we either have a training dataset from which we can learn
these models offline before doing inference, or we can learn them on-the-fly
during inference if $Y_{i}$’s are revealed after each round of estimation.
Such problems may be termed as _learning for dynamic inference_ , either
offline or online. These problems can also be studied under a Bayesian
framework, where the unknown models are assumed to be members of parametrized
model families with certain priors, and the optimal learning rule that
minimizes the expected inference loss can be mathematically derived [4].

Perhaps more importantly, the problem of learning for dynamic inference can
potentially serve as a meta problem for machine learning, such that almost all
familiar learning problems can be cast as its special cases, examples
including supervised learning, imitation learning, and reinforcement learning.
For instance, the offline learning for dynamic inference can be viewed as an
extension of the behavior cloning method in imitation learning [5, 6, 7, 8],
in that it not only learns the demonstrator’s action-generation model and
state-transition model, but simultaneously learns a policy based on the
learned models to minimize the overall contextual-aware imitation error. As
another instance, any loss function of the form
$\bar{\ell}:{\mathsf{X}}\times{\widehat{{\mathsf{Y}}}}\rightarrow\mathbb{R}$
can be expressed in the integral form of (4), with some contextual loss
function
$\ell:{\mathsf{X}}\times{\mathsf{Y}}\times{\widehat{{\mathsf{Y}}}}\rightarrow\mathbb{R}$
and probability transition kernel $P_{Y|X}$. The unknown quantity $Y$ that
depends on $X$ can then be viewed as a latent variable of the loss function.
With this view, any reinforcement learning problem [9] can be solved as an
instance of online learning for dynamic inference, where the quantities to be
estimated are the latent variables of the loss function, and the quantity-
generation model to be learned is the conditional distribution of the latent
variable. More detailed discussions on the connection between learning for
dynamic inference and other learning problems are made in [4]. The study of
dynamic inference and its learning extension thus help us gain deeper and
unifying understandings of a broad spectrum of machine learning problems.

##  6 Multiple views of dynamic inference and related works

The formulation of dynamic inference appears to be new, but it can be viewed
from different angles, and is related to a variety of existing problems.

##### Sequential interactive prediction as dynamic inference

The problems that can be most naturally formulated as dynamic inference are
estimation or prediction problems in sequential and interactive settings.
Traditionally some of those problems are formulated and studied using game
theory [10]. This type of problems become more common in recent years with
widespread adoption of AI systems, e.g., they arise in behavior prediction of
vehicles [11, 12, 13], interactive recommendation with user feedback [14], and
prediction in finance [15]. Dynamic inference provides a rigorous mathematical
formulation of such problems, and provides an optimal solution to it.

##### Dynamic inference as performative prediction

Dynamic inference also shares a similar spirit with a recent trend of research
called performativity [16, 17, 18], where the problem is to deal with the
tendency that the decision to make in optimization or prediction problems can
change the underlying distribution the decision is made for. A method called
repeated risk minimization is proposed to solve the performative prediction,
either with [18] or without [17] state transitions. The goal there is to
minimize the loss in each single round of prediction, based on the
distribution from the last round, and the hope is that such a method can reach
a minimax equilibrium under certain conditions. On the contrary, dynamic
inference aims to minimize the overall inference loss, and it explicitly
considers multiple rounds of estimation and state transitions in these
problems.

##### Dynamic inference as imitation game

The formulation of dynamic inference can also be viewed as a game of
imitation, where the learner drives a system with state, observes an action
from a demonstrator at each encountered state, and tries to imitate the
demonstrator’s actions by minimizing the accumulated state-aware imitation
error. When the underlying models are unknown, such a view can provide a
rigorous formulation of imitation learning, both online and offline, and the
optimal learning strategy is derived in [4]. In practice, this formulation has
already been implicitly adopted by practitioners in imitation learning [19].

##### MDP as dynamic inference

In this work, the solution to dynamic inference is derived by reformulating it
to an MDP which can be solved by dynamic programming. Conversely, any MDP can
be thought of as a dynamic inference problem, by viewing the loss function in
an integral form that involves an unknown latent variable, as discussed in the
previous section. The goal of MDP is then to estimate the latent variables by
minimizing the overall estimation error. This view also helps us to understand
reinforcement learning, especially Bayesian reinforcement learning in the
model-based form [20, 21, 22], from a learning for dynamic inference
perspective. The practical benefit of viewing MDP and reinforcement learning
in this way would be an interesting research problem.

## Acknowledgement

The author is indebted to Peng Guan for many helpful discussions; the
discussion with whom on imitation learning in early 2018 motivated this study.
The author is grateful to Prof. Lav Varshney, for the detailed comments and
many helpful suggestions, and for pointing out [17] on performative
prediction. The author also would like to thank Prof. Maxim Raginsky, for his
encouragement in looking into dynamic aspects of statistical problems.

††author email<EMAIL_ADDRESS>
## References

  * [1] M. Raginsky, Lecture notes for ECE 555 Control of Stochastic Systems, Spring 2019, University of Illinois at Urbana-Champaign, 2019.
  * [2] A. Xu and M. Raginsky, “Minimum excess risk in Bayesian learning,” _arXiv 2012.14868_ , 2020.
  * [3] D. P. Bertsekas, _Dynamic Programming and Optimal Control, Vol. 1_. Athena Scientific, 2017.
  * [4] A. Xu and P. Guan, “Bayesian learning for dynamic inference,” _arXiv preprint_ , 2021.
  * [5] T. Osa, J. Pajarinen, G. Neumann, J. A. Bagnell, P. Abbeel, and J. Peters, “An algorithmic perspective on imitation learning,” _Foundations and Trends in Robotics_ , vol. 7, no. 1-2, 2018.
  * [6] D. B. Grimes, D. R. Rashid, and R. P. Rao, “Learning nonparametric models for probabilistic imitation,” _In Advances in Neural Information Processing Systems_ , 2006.
  * [7] P. Englert, A. Paraschos, J. Peters, and M. P. Deisenroth, “Probabilistic model-based imitation learning,” _Adaptive Behavior_ , 2013.
  * [8] F. Torabi, G. Warnell, and P. Stone, “Behavioral cloning from observation,” in _International Joint Conference on Artificial Intelligence_ , 2018.
  * [9] R. S. Sutton and A. G. Barto, _Reinforcement Learning: An Introduction_ , 2nd ed. MIT Press, 2018.
  * [10] C. Camerer, _Behavioral game theory: Experiments in strategic interaction_. Princeton University Press, 2003.
  * [11] Y. Hu, W. Zhan, L. Sun, and M. Tomizuka, “Multi-modal probabilistic prediction of interactive behavior via an interpretable model,” in _IEEE Intelligent Vehicles Symposium_ , 2019.
  * [12] J. Li, F. Yang, M. Tomizuka, and C. Choi, “Evolvegraph: Multi-agent trajectory prediction with dynamic relational reasoning,” in _Conference on Neural Information Processing Systems_ , 2020.
  * [13] X. Ma, J. Li, M. J. Kochenderfer, D. Isele, and K. Fujimura, “Reinforcement learning for autonomous driving with latent state inference and spatial-temporal relationships,” in _IEEE International Conference on Robotics and Automation_ , 2021.
  * [14] R. Zhang, T. Yu, Y. Shen, H. Jin, and C. Chen, “Text-based interactive recommendation via constraint-augmented reinforcement learning,” in _Conference on Neural Information Processing Systems_ , 2019.
  * [15] E. Ippoliti, _Methods and Finance: A View from Outside_. Cham: Springer International Publishing, 2017.
  * [16] L. R. Varshney, N. S. Keskar, and R. Socher, “Pretrained AI models: Performativity, mobility, and change,” _arXiv:1909.03290_ , 2019.
  * [17] J. Perdomo, T. Zrnic, C. Mendler-Dünner, and M. Hardt, “Performative prediction,” in _International Conference on Machine Learning_ , 2020.
  * [18] I. K. Gavin Brown, Shlomi Hod, “Performative prediction in a stateful world,” _arXiv:2011.03885_ , 2020.
  * [19] Y. Pan, C. Cheng, K. Saigol, K. Lee, X. Yan, E. Theodorou, and B. Boots, “Imitation learning for agile autonomous driving,” _International Journal of Robotics Research_ , 2019.
  * [20] M. Strens, “A Bayesian framework for reinforcement learning.” _in Proceedings of the 17th International Conference on Machine Learning_ , pp. 943–950, 2000.
  * [21] P. Poupart, N. Vlassis, J. Hoey, and K. Regan, “An analytic solution to discrete Bayesian reinforcement learning,” _International Conference on Machine Learning_ , 2006.
  * [22] M. Ghavamzadeh, S. Mannor, J. Pineau, and A. Tamar, _Bayesian Reinforcement Learning: A Survey_. Now Foundations and Trends, 2015.