# Extensions of $\omega$-Regular Languages

Mikołaj Bojańczyk  University of Warsaw, Poland  ,  Edon Kelmendi  University
of Oxford, UK  ,  Rafał Stefański  University of Warsaw, Poland  and  Georg
Zetzsche  Max Planck Institute for Software Systems (MPI-SWS), Germany

###### Abstract.

We consider extensions of monadic second order logic over $\omega$-words,
which are obtained by adding one language that is not $\omega$-regular. We
show that if the added language $L$ has a neutral letter, then the resulting
logic is necessarily undecidable. A corollary is that the $\omega$-regular
languages are the only decidable Boolean-closed full trio over $\omega$-words.

##  1\. Introduction

A famous theorem of Büchi [12, Theorem 2] says that the monadic second-order
theory of $(\omega,<)$ is decidable. What can be added to this logic while
retaining decidability? This question has seen a lot of interest, and we begin
by discussing some of the existing results.

### What predicates can be added?

The first natural idea is to add predicates beyond the order $<$, e.g. a unary
predicate for the primes, or a binary addition function. This idea was pursued
already by Robinson in [30], in what is possibly the first published paper to
mention mso on $(\omega,<)$. This is before Büchi’s theorem about decidability
of mso, and even before the decidability results about weak mso of Büchi [11,
Corollary 1], Elgot [15, Corollary 5.8] and Trakhtenbrot [35]. After
describing mso, which he credits to Tarski’s lectures, Robinson shows that
adding the doubling function $n\mapsto 2n$ to mso results in an undecidable
logic [30, p.242]. Other examples of unary functions that lead to
undecidability were given by Elgot and Rabin [16, Section 1]. One of these
examples is that mso becomes undecidable after adding any function $f$ such
that $f^{-1}(n)$ is infinite for all $n$. This result was strengthened by
Siefkes [32, Theorem 5] who showed that it is enough that $f^{-1}(n)$ is
infinite for all $n$ with certain periodicity properties, and then by Thomas
[33, Theorem 1] who showed that it is enough for $f^{-1}(n)$ to be infinite
for infinitely many $n$. Another example of undecidability is mso extended
with any unary function $f$ that is monotone and satisfies $f(n+1)>f(n)+1$ for
infinitely many $n$, see [33, Theorem 2]. This line of research is summarised
in [29] as follows: “for most examples of natural functions or binary
relations it turned out that the corresponding monadic theory is undecidable,
usually shown via an interpretation of first-order arithmetic”.

The undecidability issues mentioned above are avoided if one considers unary
predicates. The first examples of this kind were given by Elgot and Rabin, who
showed that mso remains decidable after adding unary predicates for the
factorials, or squares, or cubes, etc. see [16, Theorem 4]). Following this
result, a lot of attention has been devoted to identifying the unary
predicates that keep mso decidable. An equivalent phrasing of this question
is: which $\omega$-words have a decidable mso theory? An interesting example
is the Thue-Morse word; its mso theory is decidable, which follows from [25,
Theorem 3]. A general classification of $\omega$-words with a decidable mso
theory was given by Semenov in [31, p. 165], this line of research was
continued in [13, 29]. It is worth pointing out that the classification can be
hard to apply to some specific cases; an important one being the case of prime
numbers. It is unknown if mso extended with a predicate for the prime numbers
has a decidable theory; if this were the case then one could use the algorithm
to decide if there are infinitely many twin primes111This theory is known to
be decidable if one assumes Schinzel’s Hypothesis – a conjecture from number
theory which implies that there are infinitely many twin primes [4, Theorem
4]..

It is worth pointing out that in all of the results discussed above, it makes
no difference whether one uses mso or weak mso. The undecidability proofs for
unary functions in [16, 33, 32] use only weak mso. For the results about unary
predicates, it makes no difference if mso or weak mso is used, because for
every $\omega$-word, its mso theory is decidable if and only if its weak mso
theory is decidable, which follows from McNaughton’s determinisation theorem
[22, p. 524]222The equivalence of mso and wmso need not hold after adding non-
unary predicates. For example, wmso with addition can only define languages in
the Borel hierarchy, while mso with addition can easily be shown to contain
the logic mso+u that will be discussed later in the paper, and mso+u can
define languages beyond the Borel hierarchy [19, Theorem 2.1].. In a sense,
one could say that the results discussed above are really about extending weak
mso. This will no longer be true when adding quantifiers and languages.

### What quantifiers can be added?

Another line of research concerns adding new quantifiers. If the added
quantifier has some implicit arithemetic, such as the Härtig quantifier [18],
which expresses the existence of two sets of equal size with a given property,
then mso immediately becomes undecidable. This follows directly from
Robinson’s result about $n\mapsto 2n$, and it is also discussed in more detail
in [20, Theorem 14]. However, there are quantifiers which describe only
topological or asymptotic behaviour, and for such quantifiers proving
undecidability can be much harder. One example of an asymptotic quantifier is
the bounding quantifier from [5], which expresses the property “$\varphi(X)$
is true for finite sets $X$ of unbounded size” [5]. The resulting logic,
called mso+u, is undecidable [9, Theorem 1.1]. However, it is close to the
decidability border; in particular weak mso with the bounding quantifier is
decidable [6, Theorems 3 and 5]; and the same is true for its variants and
extensions [10, Theorems 11 and 13]. Other extensions of mso with asymptotic
quantifiers were proposed by Michalewski, Mio and Skrzypczak in [23, 24],
including a quantifier related to Baire category and a quantifier related to
probability. The Baire quantifier does not add to the expressive power of mso
[24, Theorem 4.1]. On the other hand, the probability quantifier leads to an
undecidable logic [23, Theorem 1], because it can express the undecidable
problem of checking if a probabilistic Büchi automaton accepts some word with
nonzero probability [3, Theorem 7.2]. The theme for quantifiers seems to be
that adding a well-behaved quantifier to (non-weak) mso either does not change
the expressive power, or leads to an undecidable logic; but in the latter case
the undecidability proof can be hard.

### What languages can be added?

We now turn to the final kind of feature that can be added to mso, namely
languages. This is the main topic of this paper. A language
$L\subseteq\\{a,b\\}^{\omega}$ over a binary alphabet can be viewed as a
second-order unary predicate $L(X)$, which inputs a set $X\subseteq\omega$ and
returns true if the language $L$ contains the word where positions from $X$
have label $a$ and the remaining positions have label $b$. This can be
generalized to alphabets with $k$ letters: Then, the predicate inputs $k$ sets
and returns true if the $k$ sets form a partition of $\omega$ and $L$ contains
the word encoding this partition. Let us write mso+$L$ for the extension of
mso which has the predicate described above.

Another equivalent way of describing the logic mso+$L$ uses closure properties
of languages. A folklore fact about mso is that existential monadic
quantification is the same as taking the image of a language under a letter-
to-letter homomorphism, see [28, p. 2] or [34, Section 2.3]. It follows that
mso+$L$ is exactly the smallest class of languages of $\omega$-words which
contains $L$ and all $\omega$-regular languages, and which is closed under (a)
Boolean combinations; (b) images of letter-to-letter homomorphisms; and (c)
inverse images of letter-to-letter homomorphisms. We will return to this
language theoretic approach in Section 2.

######  Example 1.1.

Suppose that $L\subseteq\Sigma^{\omega}$ is a singleton language, i.e. it
contains only one word $w$. Then mso+$L$ has the same expressive power as mso
extended with unary predicates

$\displaystyle P_{a}=\\{n\in\omega:\text{the $n$-th letter of $w$ is
$a$}\\}\quad\text{for $a\in\Sigma$.}$

Therefore, in the case of singleton languages mso+$L$, corresponds to the mso
extensions with unary predicates that were studied in [16, 33, 31, 13, 29].

######  Example 1.2.

Define $U\subseteq\\{a,b\\}^{\omega}$ to be the $\omega$-words where blocks of
$a$’s have unbounded size:

$\displaystyle
U\stackrel{{\scriptstyle\text{def}}}{{=}}\\{a^{k_{1}}ba^{k_{2}}\cdots:\limsup
k_{n}=\infty\\}.$

In [8, Theorem 1.3] it is shown that adding the language $U$ to mso gives
exactly the logic mso+u. Hence it is unambiguous to write mso+u, with both
meanings (adding a quantifier or a language) being equivalent. As mentioned
before, this logic is undecidable.

######  Example 1.3.

Consider the ultimately periodic words, i.e.

$\displaystyle P=\\{wv^{\omega}:w,v\in\\{a,b\\}^{*}\text{ and $v$ is
nonempty}\\}.$

It is not hard to see that mso+$P$ can express the language $U$ from Example
1.2, and therefore this logic is undecidable [8, Theorem 1.4]. In contrast,
adding $P$ to weak mso yields a decidable logic [10, Theorem 13].

Our goal in this paper is to classify the languages $L$ such that mso+$L$ is
undecidable. By the discussion in Example 1.1, this project is at least as
difficult as classifying the $\omega$-words with a decidable mso theory.
However, in the spirit of “asymptotic” conditions, we restrict attention to
languages which have a neutral letter, which means that there is a letter in
the alphabet, denoted by $1$, such that

$\displaystyle w_{1}1w_{2}1\cdots\in L\qquad\Leftrightarrow\qquad
w_{1}w_{2}\cdots\in L$

holds for every words $w_{1},w_{2},\ldots\in\Sigma^{*}$ where infinitely many
$w_{i}$ are nonempty333In the definition of neutral letters, we require that
the language is stable under inserting or deleting infinitely many neutral
letters. However, this also implies that the language is stable under
inserting or deleting finitely many neutral letters.. We now state the main
theorem of this paper.

######  Theorem 1.4.

If $L\subseteq\Sigma^{\omega}$ has a neutral letter and is not definable in
mso, then mso+$L$ is undecidable.

In the above theorem, by undecidable we mean that there is no algorithm which
decides the sentences of mso+$L$ that are true in $(\omega,<)$. Since mso can
quantify over words, this is the same as saying that satisfiability is
undecidable for mso+$L$ for $\omega$-words. The proof of Theorem 1.4 will be
given in Section 4.

######  Example 1.5.

Define $U^{\prime}\subseteq\\{a,b,1\\}^{\omega}$ to be the words such that
eliminating all $1$’s gives a word in the language $U$ from Example 1.2. We
claim that the logic is obtained by extending mso with (a) the bounding
quantifier; or (b) the language $U$; or (c) the language $U^{\prime}$. The
equality of (a) and (b) was discussed in Example 1.2. The language
$U^{\prime}$ can be defined using the bounding quantifier, hence the inclusion
(c) $\subseteq$ (a). The language $U$ is the intersection of $U^{\prime}$ with
language of words that do not contain the letter $1$, hence the inclusion (b)
$\subseteq$ (c). The equality of these three logics is discussed in more
detail in [8].

The language $U$ will play an important role in the proof of Theorem 1.4. We
will show that if $L$ is not definable in mso and contains a neutral letter,
then $U$ is definable in mso+$L$. Undecidability will then follow by Theorems
[9, Theorem 1.1] and [8, Theorem 1.3]. In this sense, $U$ is the simplest
undecidable extension of mso.

The paper is structured as follows. In Section 2, we discuss a version of our
main theorem for finite words, which was proved by Zetzsche et al. in [36].
Like [36], we prove our main theorem using syntactic congruences, and
therefore Section 3 is devoted to a discussion of syntactic congruences for
$\omega$-languages. In Section 4, we prove our main result, and in Section 5
we show that the main theorem implies that the $\omega$-regular languages are
the only Boolean-closed full trios that are decidable.

##  2\. Finite words

In this section, we describe the starting point for our work, which is a
theorem by Zetzsche et al., which says that the regular languages of finite
words are the only decidable Boolean-closed full trio. To define full
trios444Full trios are sometimes called cones in formal languages literature,
they are meant to be a formalisation of robust classes of languages., recall
that a _homomorphism_ is a function

$\displaystyle h:\Sigma^{*}\to\Gamma^{*}\qquad\text{such that
}h(wv)=h(w)h(v).$

Define the _arithmetic hierarchy_ , see [36, Section 2], to be the least class
of languages of finite words that contains all recursively enumerable
languages, and which is closed under complementation and homomorphic images.

######  Theorem 2.1.

[36, Corollary 3.2] Let $\mathcal{L}$ be a class of languages of finite words
which is a full trio, i.e. it is closed under:

  1. (1)

images under homomorphisms; and

  2. (2)

inverse images under homomorphisms; and

  3. (3)

intersections with regular languages.

If $\mathcal{L}$ is additionally Boolean-closed (closed under union and
complementation) and it contains at least one non-regular language, then it
contains the arithmetic hierarchy.

In the above theorem, there is no assumption on neutral letters. This is
because condition 2 deprecates the assumption, since a neutral letter can be
added to any language by taking the inverse image under the homomorphism which
eliminates the neutral letter. The closure properties used in Theorem 1.4 are
weaker, and hence the assumption on neutral letters is needed. As a warm-up
for the case of $\omega$-words, we give below a proof sketch for the above
theorem.

###### Proof sketch.

The proof uses rational relations [14, p.236]. Recall that a rational relation
is a binary relation on words that is recognised by a nondeterministic
automaton where each transition is labelled by a pair (input word, output
word), with both words being possibly empty. By Nivat’s theorem (Propositions
1 and 2 in [26]), if a language class $\mathcal{L}$ is a full trio, then it is
closed under images under rational relations, which can be visualised as the
following reasoning rule:

$\displaystyle\mathchoice{\frac{K\subseteq\Sigma^{*}\text{ is in
$\mathcal{L}$}\qquad R\subseteq\Sigma^{*}\times\Gamma^{*}\text{ is a rational
relation}}{\\{v\in\Gamma^{*}:\exists w\in L\text{ with }(w,v)\in R\\}\text{ is
in $\mathcal{L}$}}}{K\subseteq\Sigma^{*}\text{ is in $\mathcal{L}$}\qquad
R\subseteq\Sigma^{*}\times\Gamma^{*}\text{ is a rational
relation}/\\{v\in\Gamma^{*}:\exists w\in L\text{ with }(w,v)\in R\\}\text{ is
in $\mathcal{L}$}}{K\subseteq\Sigma^{*}\text{ is in $\mathcal{L}$}\qquad
R\subseteq\Sigma^{*}\times\Gamma^{*}\text{ is a rational
relation}/\\{v\in\Gamma^{*}:\exists w\in L\text{ with }(w,v)\in R\\}\text{ is
in $\mathcal{L}$}}{K\subseteq\Sigma^{*}\text{ is in $\mathcal{L}$}\qquad
R\subseteq\Sigma^{*}\times\Gamma^{*}\text{ is a rational
relation}/\\{v\in\Gamma^{*}:\exists w\in L\text{ with }(w,v)\in R\\}\text{ is
in $\mathcal{L}$}}$

Because $\mathcal{L}$ is closed under complementation, we can also use a
variant of the above rule where $\forall$ is used instead of $\exists$ in the
conclusion of the rule (i.e. below the line).

The key idea is to use the closure properties to formalise the syntactic right
congruence of the language. Let $L\subseteq\Sigma^{*}$ be some non-regular
language in $\mathcal{L}$, which exists by assumption, and let $\sim$ be its
syntactic right congruence, i.e. the equivalence relation defined by

$\displaystyle u\sim
u^{\prime}\quad\stackrel{{\scriptstyle\text{def}}}{{=}}\quad\forall
v\in\Sigma^{*}\ \ \ uv\in L\Leftrightarrow u^{\prime}v\in L.$

By the Myhill-Nerode theorem, $\sim$ has infinite index, i.e. infinitely many
equivalence classes. Using the reasoning rule with rational relations, one
shows that $\mathcal{L}$ contains the language

$\displaystyle L_{1}=\\{u\\#u^{\prime}:u\sim u^{\prime}\\},$

where $\\#$ is a fresh separator symbol. Consider now two separator symbols
$\\#$ and
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\\#}$.
Define $L_{2}$ to be the language

$\displaystyle\\{w_{1}\\#\cdots\\#w_{n}\\#v_{1}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\\#}\cdots{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\\#}v_{m}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\\#}:\begin{cases}w_{1}\sim
v_{1}\\\ w_{n}\sim v_{m}\\\ w_{i}\not\sim w_{j}\text{ for $i\neq j$}\\\
v_{i}\not\sim v_{j}\text{ for $i\neq j$}\\\ w_{i}\sim v_{j}\Rightarrow
w_{i+1}\sim v_{j+1}\end{cases}\\}.$

Using the closure properties, one shows $L_{2}\in\mathcal{L}$. A short
analysis of the conditions defining $L_{2}$ reveals that every word in $L_{2}$
satisfies

$\displaystyle m=n\qquad\text{and}\qquad w_{1}\sim v_{1},w_{2}\sim
v_{2},\ldots,w_{n}\sim v_{n}.$

Furthermore, since $\sim$ has infinitely many equivalence classes, it follows
that $n=m$ can be arbitrarily large. By projecting away the words
$w_{i},v_{i}$ using a homomorphisms, it follows that $\mathcal{L}$ contains
the language

$\displaystyle
L_{3}=\\{\\#^{n}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\\#}^{n}:n\in\\{1,2,\ldots\\}\\}.$

A string encoding of runs of two-counter machines, see [17, Theorem 2], can be
used to show that $\mathcal{L}$ contains every recursively enumerable
language. The arithmetic hierarchy follows, by closure of $\mathcal{L}$ under
homomorphic images and complementation. ∎

##  3\. Congruences for $\omega$-words

Like in Theorem 2.1, the proof of Theorem 1.4 also uses congruences. However,
there are several issues with congruences for $\omega$-words, which mean that
some new ideas are needed. The main problem is that there is no good notion of
syntactic congruence for languages of $\omega$-words.

We begin by discussing several existing approaches to congruences for
$\omega$-words, see also [21]. In all cases, we begin with a language
$L\subseteq\Sigma^{\omega}$, and use it to define an equivalence relation on
finite words. The first candidate is the _right congruence_ , which identifies
two finite words $u,u^{\prime}\in\Sigma^{*}$ if

$\displaystyle\forall v\in\Sigma^{\omega}\qquad\ uv\in L\Leftrightarrow
u^{\prime}v\in L.$

This right congruence does not characterise the $\omega$-regular languages,
although it does have some use, for example in automata learning [1]. There
could be finitely many equivalence classes despite a language not being
$\omega$-regular. For example, every prefix independent language will have one
equivalence class of right congruence, but there are prefix independent
languages which are not $\omega$-regular, such as

$\displaystyle\\{w(a^{n}b)^{\omega}:w\in\\{a,b\\}^{*}\text{ and $n$ is
prime}\\}.$

By induction on formula size one can show that if $L$ has a right congruence
of finite index, then the same is true for every language definable in
mso+$L$; which shows that right congruences will not be useful for our main
result. Similar problems arise for the two-sided version of right congruence.

A more useful congruence for $\omega$-words uses two-sided environments and
$\omega$-iteration; this leads to the _Arnold congruence_ [2, Section 2],
which identifies $u,u^{\prime}$ if

$\displaystyle\land\begin{cases}\forall w\in\Sigma^{*}\ \forall
v\in\Sigma^{\omega}\qquad wuv\in L\Leftrightarrow wu^{\prime}v\in L\\\ \forall
w,v\in\Sigma^{*}\qquad w(uv)^{\omega}\in L\Leftrightarrow
w(u^{\prime}v)^{\omega}\in L.\end{cases}$

The Arnold congruence still does not characterise the $\omega$-regular
languages. For example, the language $U$ is not $\omega$-regular, but it has
two equivalence classes under Arnold congruence: words which contain $b$, and
words which do not contain $b$.

Fortunately, there is a successful characterisation of $\omega$-regular
languages via congruences. This characterisation is stated below, and it
corresponds to $\omega$-semigroups.

######  Theorem 3.1.

[27, Theorem 7.5] A language $L\subseteq\Sigma^{\omega}$ is $\omega$-regular
if and only if there is an equivalence relation $\sim$ which has finite index
and satisfies the following conditions for all sequences of finite words
$u_{i}$:

(1) $\displaystyle\bigg{(}\bigwedge_{i\in\\{1,2\\}}u_{i}\sim
u_{i}^{\prime}\bigg{)}$ $\displaystyle\Rightarrow$ $\displaystyle
u_{1}u_{2}\sim u^{\prime}_{1}u^{\prime}_{2}$ (2)
$\displaystyle\bigg{(}\bigwedge_{i\in\mathbb{N}}u_{i}\sim
u_{i}^{\prime}\bigg{)}\ \ $ $\displaystyle\Rightarrow$
$\displaystyle\left(u_{1}u_{2}\cdots\in L\Leftrightarrow
u^{\prime}_{1}u^{\prime}_{2}\cdots\in L\right)$

We use the name _$\omega$ -congruence_ for an equivalence relation that
satisfies conditions (1) and (2) in the above theorem. We use the above
theorem in our main result. Although promising, the characterisation in terms
of $\omega$-congruences has one important drawback, namely non-uniqueness. For
the right congruence, the defining property

$\displaystyle\forall v\in\Sigma^{\omega}\qquad uv\in L\Leftrightarrow
u^{\prime}v\in L.$

gives a unique equivalence relation, and hence it makes sense to speak of
_the_ right congruence. A similar property holds for the Arnold congruence.
The uniqueness of the definition of right congruence, and the fact that its
definition can be formalised using rational relations, is what drives the
proof of Theorem 2.1.

In contrast, there is no uniqueness in Theorem 3.1, and there cannot be. A
language might not have a unique coarsest $\omega$-congruence (such an
equivalence relation is called the _syntactic $\omega$-congruence_). An
example is the language $U$, see [7, Running Example 2]. For $\omega$-regular
languages, the syntactic $\omega$-congruence exists and coincides with Arnold
congruence, see [27, Proposition 8.8], but this is not very helpful in our
setting, since we want to study congruences for languages that are _not_
$\omega$-regular. These are issues that we will need to overcome in the proof
of our main result.

We finish this section with a simple observation, which says that condition
(1) in Theorem 3.1 is superfluous. This observation will be useful later on,
since condition (2) will be easier to formalise.

######  Lemma 3.2.

If there is an equivalence relation of finite index which satisfies (2), then
there is an equivalence relation of finite index which satisfies both (1) and
(2).

###### Proof.

Induction on the number of equivalence classes in the equivalence relation,
call it $\sim$. In the base case, when $\sim$ has one equivalence class,
condition (1) holds vacuously. Consider the induction step. For this proof, it
is easier to work with the following equivalent form of (1):

$\displaystyle u\sim u^{\prime}\qquad\Rightarrow\qquad(uw\sim
u^{\prime}w)\land(wu\sim wu^{\prime}).$

If $\sim$ satisfies the above implication, then we are already done.
Otherwise, choose a violation of the implication, i.e. words $u\sim
u^{\prime}$ which do not satisfy the conclusion of the implication. By
symmetry, assume $uw\not\sim u^{\prime}w$. Define $\approx$ to be the
equivalence relation obtained from $\sim$ by merging the equivalence classes
of $uw$ and $u^{\prime}w$. We claim that $\approx$ still satisfies condition
(2), and therefore the induction assumption can be applied. We visualize (2)
as follows:

${u_{0}}$${u_{1}}$${u_{2}}$${\cdots}$${\in
L}$${u^{\prime}_{0}}$${u^{\prime}_{1}}$${u^{\prime}_{2}}$${\cdots}$${\in
L}$$\approx$$\approx$$\approx$$\approx$$\Leftrightarrow$

By definition of $\approx$ and assumption (2) for $\sim$, we can replace every
$u_{n}$ in the equivalence class of $uw$ by $uw$ and every $u_{n}$ in the
equivalence class of $u^{\prime}w$ by $u^{\prime}w$, without affecting
membership in $L$. Therefore we can assume without loss of generality that
every $u_{n}$ is either $uw$, or $u^{\prime}w$, or a word that is
$\sim$-equivalent to neither of these. The same can be done for
$u^{\prime}_{n}$. By definition of $\approx$, if $u_{n}=uw$ then
$u^{\prime}_{n}$ has to be one of $uw$ or $u^{\prime}w$. We can now split each
$u_{n}=uw$ into two words $u$ and $w$, likewise for $u_{n}=u^{\prime}w$, and
then use again the assumption that $\sim$ satisfies (2) to finish the proof. ∎

##  4\. Proof of the main theorem

In this section we prove Theorem 1.4. Fix a language
$L\subseteq\Sigma^{\omega}$ that is not $\omega$-regular, and which contains a
neutral letter. We will show that the logic mso+$L$ is undecidable.

To prove undecidability, we will show that mso+$L$ contains the language $U$,
and therefore undecidability follows thanks to the results about the logic
mso+u. To explain how $U$ can be defined, we use a game called the _congruence
game_. This game is played by two players called Spoiler and Duplicator, and
it is parametrised by an $\omega$-word $u\in\\{a,b\\}^{\omega}$. The
congruence game is designed so that player Duplicator wins if and only if
$u\in U$, which means that $u$ has $a$-labelled intervals of unbounded size.
This is achieved as follows. Roughly speaking, the goal of player Duplicator
is to show that from the perspective of the language $L$, each finite word
$w\in\Sigma^{*}$ is equivalent to some word $v\in\Sigma^{*}$ which can fit
infinitely often into $a$-labelled intervals in the word $u$. Since the
language $L$ is not $\omega$-regular, Duplicator needs intervals of unbounded
size to win.

Define an _interval_ to be a finite connected subset of $\omega$, i.e. it
contains all positions between its first and last position. If $W,V$ are
intervals, then we write $W<V$ if the last position of $W$ is strictly before
the first position of $V$.

######  Definition 4.1 (Congruence Game).

The _congruence game for $u\in\\{a,b\\}^{\omega}$_ is the following game
played by two players, called Spoiler and Duplicator.

  1. (1)

Spoiler chooses an infinite family $\mathcal{W}$ of pairwise disjoint
intervals.

  2. (2)

Duplicator chooses intervals

$\displaystyle W_{1}<V_{1}<W_{2}<V_{2}<\cdots$

such that $W_{1},W_{2},\ldots$ are from $\mathcal{W}$ and $V_{1},V_{2},\ldots$
contain only positions with label $a$ in the word $u$.

  3. (3)

Spoiler chooses words

$\displaystyle w_{1},w_{2},\ldots\in\Sigma^{*}$

such that $|w_{i}|<|W_{i}|$ for every $i\in\\{1,2,\ldots\\}$.

  4. (4)

Duplicator chooses words

$\displaystyle v_{1},v_{2},\ldots\in\Sigma^{*}$

such that $|v_{i}|<|V_{i}|$ for every $i\in\\{1,2,\ldots\\}$.

  5. (5)

Spoiler chooses a sequence of natural numbers

$\displaystyle i_{1}<i_{2}<\cdots.$

  6. (6)

Duplicator wins the game if and only if:

$\displaystyle w_{j_{1}}w_{j_{2}}w_{j_{3}}\cdots\in
L\qquad\Leftrightarrow\qquad v_{j_{1}}v_{j_{2}}v_{j_{3}}\cdots\in L.$

The key result about the congruence game is the following lemma. The lemma
does not use the assumption that $L$ contains a neutral letter; this
assumption will be used later when formalising the congruence game in mso+$L$.

######  Lemma 4.2.

Assume that $L\subseteq\Sigma^{\omega}$ is not $\omega$-regular. Then

$\displaystyle\text{Duplicator wins the congruence game for $u$}\ \
\Leftrightarrow\ \ u\in U.$

###### Proof.

($\Leftarrow$) Assume $u\in U$. We will show a winning strategy for player
Duplicator. Suppose that player Spoiler has chosen a family $\mathcal{W}$ in
round 1. Since $u\in U$, intervals with only $a$-labelled positions have
unbounded size, and therefore in round 2, player Duplicator can choose the
intervals so that $|V_{i}|\geq|W_{i}|$ for all $i$. For every choice of words
$w_{i}$ made by player Spoiler in round 3, Duplicator’s response in round 4 is
to choose the words $v_{i}$ so that $v_{i}=w_{i}$ for all $i$. This guarantees
victory for Duplicator, regardless of Spoiler’s move in round 5.

($\Rightarrow$) Assume $u\not\in U$. We will show a winning strategy for
player Spoiler. In round 1, Spoiler picks $\mathcal{W}$ so that the lengths of
the intervals tend to infinity, i.e. no size appears infinitely often. Let
$W_{i}$ and $V_{i}$ be the intervals that are chosen in round 2 by player
Duplicator. By choice of $\mathcal{W}$, the lengths of the intervals $W_{i}$
tend to infinity, while by assumption that $u\not\in U$, the lengths of the
intervals $V_{i}$ are bounded. In round 3, Spoiler chooses the words $w_{i}$
so that every word from $\Sigma^{*}$ appears infinitely often. This can be
done because the lengths of the intervals $W_{i}$ tend to infinity. Suppose
that Duplicator chooses some words $v_{i}$ in round 4. Since the intervals
$V_{i}$ have bounded size, the words $v_{i}$ chosen by Duplicator come from a
finite set $F\subseteq\Sigma^{*}$. This means that for every $w\in\Sigma^{*}$,
there is some $v\in\Sigma^{*}$ such that infinitely often $w_{i}=w$ and
$v_{i}=v$. Choose some function

$\displaystyle f:\Sigma^{*}\to F$

which realises the dependency $w\mapsto v$, i.e. for every $w\in\Sigma^{*}$,

(3) $\displaystyle w=w_{i}\quad\text{and}\quad f(w)=v_{i}\qquad\text{for
infinitely many $i$.}$

Apply Lemma 3.2 with $\sim$ being the kernel of $f$, i.e. the equivalence
relation that identifies two words if they have the same image under $f$.
Since $L$ is not $\omega$-regular, then by Lemma 3.2 there must be a violation
of (2), i.e. there must be words $u_{1},u_{2},\ldots$ such that

(4) $\displaystyle u_{1}u_{2}\cdots\in L\qquad\not\\!\\!\\!\\!\\!\iff\qquad
f(u_{1})f(u_{2})\cdots\in L.$

By (3), in Round 5, Spoiler can choose the indices $i_{1}<i_{2}<\cdots$ so
that

$\displaystyle u_{n}=w_{i_{n}}\qquad f(u_{n})=f(v_{i_{n}})\qquad\text{for all
$n\in\\{1,2,\ldots\\}$}$

and therefore win thanks to (4). ∎

The following corollary, and undecidability of the logic mso+u, complete the
proof of Theorem 1.4.

######  Corollary 4.3.

If $L\subseteq\Sigma^{\omega}$ is not $\omega$-regular and contains a neutral
letter, then mso+u $\subseteq$ mso+$L$.

###### Proof.

By [8, Theorem 1.3], it is enough to show that the language $U$ is definable
in mso+$L$. By Lemma 4.2, it is enough to show that mso+$L$ can express that
Duplicator has a winning strategy in the congruence game.

A family of disjoint intervals is represented by two sets of positions: the
set $X$ of leftmost positions in the intervals, and the set $Y$ of rightmost
positions in the intervals. The condition that all intervals are disjoint
means that

$\displaystyle\forall x_{1},x_{2}\in X\ x_{1}<x_{2}\ \Rightarrow\ \exists y\in
Y\ x_{1}\leq y<x_{2}.$

Using this representation, the choices of intervals in rounds 1 and 2 can be
represented by set quantification, with choices of player Duplicator using
existential quantifiers and choices of player Spoiler using universal
quantifiers. The words $w_{i}$ chosen in round 3 are represented by colouring
the intervals $W_{i}$ with letters from $\Sigma$; and using the neutral letter
for positions not in the intervals $W_{i}$. The same goes for round 4. The
subsequence in round 5 is represented by a subset of leftmost positions in the
intervals $W_{i}$. The winning condition in round 6 is checked by using the
predicate for $L$. ∎

##  5\. Boolean closed full trios

We finish the paper with a corollary of our main theorem, which is an analog
of Theorem 2.1 for infinite words: if a Boolean-closed full trio of languages
of infinite words contains at least one non-regular language, then it contains
the entire arithmetic hierarchy, subject to a certain representation.

As mentioned in the introduction, a language of $\omega$-words is definable in
mso+$L$ if and only if it belongs to the smallest class of languages that
contains $L$, contains all $\omega$-regular languages, is closed under Boolean
combinations, as well as images and inverse images under letter-to-letter
homomorphisms. If we lift the restriction on homomorphisms being letter-to-
letter, then we get a Boolean-closed full trio, as discussed below.

When applying a homomorphism that may erase some letters, an $\omega$-word can
be mapped to a finite word. Therefore, in the presence of such homomorphisms,
it makes sense to consider languages of words of length $\leq\omega$, i.e.
words which are either finite or $\omega$-words. For such words, define a
_regular language_ to be a union of two languages: a regular language of
finite words, plus a regular language of $\omega$-words. Define a
_homomorphism_ for words of length $\leq\omega$ to be a function

$\displaystyle h:\Sigma^{\leq\omega}\to\Gamma^{\leq\omega}\qquad$

which is obtained by applying to each letter a function of type
$\Sigma\to\Gamma^{*}$.

######  Theorem 5.1.

Let $\mathcal{L}$ be a class of languages of words of length at most
$\leq\omega$ which is closed under:

  1. (1)

images under homomorphisms; and

  2. (2)

inverse images under homomorphisms; and

  3. (3)

intersections with regular languages.

If $\mathcal{L}$ is additionally Boolean-closed (closed under union and
complementation) and it contains at least one non-regular language, then for
every $L\subseteq\Sigma^{*}$ in the arithmetic hierarchy,

$\displaystyle\underbrace{\\{wv^{\omega}:w\in\Sigma^{*},v\in L\\}}_{\text{loop
representation of $L$}}\in\mathcal{L}.$

###### Proof.

By closure under inverse images of homomorphisms and under intersection with
$\Sigma^{*}$ and $\Sigma^{\omega}$ for any $\Sigma$, if $\mathcal{L}$ contains
some non-regular language, then it contains some non-regular $\omega$-language
with a neutral letter. By Corollary 4.3, $\mathcal{L}$ contains all languages
definable in mso+u. By [9, Lemma 3.2], for every recursively enumerable
language $L\subseteq\Sigma^{*}$, the logic mso+u defines some
$\omega$-language $K$, over an alphabet extended with a neutral letter, such
that

$\displaystyle\text{loop representation of $L$}=h(K),$

where $h$ is the homomorphism that eliminates the neutral letter. Since
$\mathcal{L}$ is closed under homomorphic images, it follows that
$\mathcal{L}$ contains the loop representations of all recursive enumerable
languages. For the arithmetic hierarchy, it is enough to observe that the
class

$\displaystyle\\{L\subseteq\Sigma^{*}:\text{$\mathcal{L}$ contains the loop
representation of $L$}\\}$

is closed under Boolean combinations and homomorphic images. ∎

In contrast to the finite word setting, we cannot conclude that $\mathcal{L}$
contains $L$ itself: Standard arguments show that if a language
$K\subseteq\Sigma^{\leq\omega}$ has a finite-index right congruence, then
every language obtained from $K$ using Boolean full trio operations also has a
finite-index right congruence. Thus, for example, if we start with $U$, all
obtainable languages over finite words are regular.

One could also consider Boolean closed full trios of $\omega$-languages. Then,
homomorphisms would be defined by functions of type $\Sigma\to\Gamma^{*}$ and
the (inverse) image of a homomorphism on a subset of $\Sigma^{\omega}$ would
contain only those resulting words that are infinite. For this notion of
(inverse) image, Theorem 5.1 follows with essentially the same proof.

## References

  * [1] Dana Angluin and Dana Fisman, _Regular $\omega$-languages with an informative right congruence_, GandALF 2018, Saarbrücken, Germany, 2018, 2018, pp. 265–279.
  * [2] André Arnold, _A syntactic congruence for rational $\omega$-languages_, Theoret. Comput. Sci. 39 (1985), no. 2-3, 333–335.
  * [3] Christel Baier, Marcus Grösser, and Nathalie Bertrand, _Probabilistic $\omega$–automata_, J. ACM 59 (2012), no. 1, 1:1–1:52.
  * [4] P. T. Bateman, C. G. Jockusch, and A. R. Woods, _Decidability and undecidability of theories with a predicate for the primes_ , Journal of Symbolic Logic 58 (1993), no. 2, 672–687.
  * [5] Mikołaj Bojańczyk, _A bounding quantifier_ , Computer Science Logic, CSL 2004, Karpacz (Jerzy Marcinkowski and Andrzej Tarlecki, eds.), Lecture Notes in Computer Science, vol. 3210, Springer, 2004, pp. 41–55.
  * [6] by same author, _Weak MSO with the unbounding quantifier_ , Theory Comput. Syst. 48 (2011), no. 3, 554–576.
  * [7] by same author, _Recognisable languages over monads_ , CoRR abs/1502.04898 (2015).
  * [8] Mikołaj Bojańczyk, Laure Daviaud, Bruno Guillon, Vincent Penelle, and A. V. Sreejith, _Undecidability of MSO+”ultimately periodic”_ , Logical Methods in Computer Science abs/1807.08506 ((to appear)).
  * [9] Mikołaj Bojańczyk, Pawel Parys, and Szymon Toruńczyk, _The MSO+U theory of $(\mathbb{N},<)$ is undecidable_, 33rd STACS Orléans, France (Nicolas Ollinger and Heribert Vollmer, eds.), LIPIcs, vol. 47, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, pp. 21:1–21:8.
  * [10] Mikołaj Bojańczyk and Szymon Toruńczyk, _Deterministic automata and extensions of Weak MSO_ , FSTTCS 2009, IIT Kanpur, India, LIPIcs, vol. 4, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2009, pp. 73–84.
  * [11] J. Richard Büchi, _Weak second-order arithmetic and finite automata_ , Z. Math. Logik und Grundl. Math. 6 (1960), 66–92.
  * [12] by same author, _On a decision method in restricted second order arithmetic_ , Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr .), Stanford Univ. Press, Stanford, Calif., 1962, pp. 1–11.
  * [13] Olivier Carton and Wolfgang Thomas, _The monadic theory of morphic infinite words and generalizations_ , Information and Computation 176 (2002), no. 1, 51–65.
  * [14] Samuel Eilenberg, _Automata, languages, and machines. Vol. A_ , Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York, 1974.
  * [15] Calvin C. Elgot, _Decision problems of finite automata design and related arithmetics_ , Trans. Amer. Math. Soc. 98 (1961), 21–51.
  * [16] Calvin C. Elgot and Michael O. Rabin, _Decidability and undecidability of second (first) order theory of (generalized) successor_ , J. of Symbolic Logic 31 (1966), 169–181.
  * [17] Juris Hartmanis and John E. Hopcroft, _What makes some language theory problems undecidable_ , J. Comput. Syst. Sci. 4 (1970), no. 4, 368–376.
  * [18] Heinrich Herre, Michał Krynicki, Alexandr Pinus, and Jouko Väänänen, _The härtig quantifier: a survey_ , The Journal of symbolic logic 56 (1991), no. 4, 1153–1183.
  * [19] Szczepan Hummel and Michał Skrzypczak, _The topological complexity of MSO+U and related automata models_ , Fundamenta Informaticae 119 (2012), no. 1, 87–111.
  * [20] Felix Klaedtke and Harald Rueß, _Monadic second-order logics with cardinalities_ , 30th ICALP 2003, Eindhoven, The Netherlands, 2003, pp. 681–696.
  * [21] Oded Maler and Ludwig Staiger, _On syntactic congruences for $\omega$-languages_, Theoret. Comput. Sci. 183 (1997), no. 1, 93–112.
  * [22] Robert McNaughton, _Testing and generating infinite sequences by a finite automaton_ , Information and Control 9 (1966), 521–530.
  * [23] Henryk Michalewski and Matteo Mio, _Measure quantifier in monadic second order logic_ , International Symposium on Logical Foundations of Computer Science, Springer, 2016, pp. 267–282.
  * [24] Matteo Mio, Michał Skrzypczak, and Henryk Michalewski, _Monadic second order logic with measure and category quantifiers_ , Logical Methods in Computer Science 14 (2018), no. 2.
  * [25] Andrei Muchnik, Alexei Semenov, and Maxim Ushakov, _Almost periodic sequences_ , Theoretical Computer Science 304 (2003), no. 1-3, 1–33.
  * [26] Maurice Nivat, _Transductions des langages de chomsky_ , Annales de l’Institut Fourier 18 (1968), no. 1, 339–455 (fr). MR 38 #6909
  * [27] Dominique Perrin and Jean-Eric Pin, _Infinite words - automata, semigroups, logic and games_ , Pure and applied mathematics series, vol. 141, Elsevier Morgan Kaufmann, 2004.
  * [28] Michael O. Rabin, _Decidability of second-order theories and automata on infinite trees._ , Trans. Amer. Math. Soc. 141 (1969), 1–35.
  * [29] Alexander Rabinovich and Wolfgang Thomas, _Decidable theories of the ordering of natural numbers with unary predicates_ , Computer Science Logic (Berlin, Heidelberg) (Zoltán Ésik, ed.), Springer Berlin Heidelberg, 2006, pp. 562–574.
  * [30] Raphael M. Robinson, _Restricted set-theoretical definitions in arithmetic_ , Proceedings of the American Mathematical Society 9 (1958), no. 2, 238–238.
  * [31] Alexei L. Semenov, _Decidability of monadic theories_ , Mathematical foundations of computer science, 1984 (Prague, 1984), Springer, Berlin, 1984, pp. 162–175.
  * [32] Dirk Siefkes, _Undecidable extensions of monadic second order successor arithmetic_ , Mathematical Logic Quarterly 17 (1971), no. 1, 385–394.
  * [33] Wolfgang Thomas, _A note on undecidable extensions of monadic second order successor arithmetic_ , Archive for Mathematical Logic 17 (1975), no. 1, 43–44.
  * [34] by same author, _Languages, automata, and logic_ , Handbook of Formal Languages, Volume 3: Beyond Words. (Grzegorz Rozenberg and Arto Salomaa, eds.), Springer, 1997, pp. 389–455.
  * [35] Boris A. Trakhtenbrot, _Finite automata and the logic of single-place predicates_ , Dokl. Akad. Nauk SSSR 140 (1961), no. 2, 326–329.
  * [36] Georg Zetzsche, Dietrich Kuske, and Markus Lohrey, _On Boolean closed full trios and rational Kripke frames_ , Theory of Computing Systems 60 (2017), no. 3, 438–472.


# Bayesian Optimization in Materials Science: A Survey

Lars Kotthoff  Hud Wahab  Patrick A. Johnson
Center for Artificially Intelligent Manufacturing
University of Wyoming

###### Abstract

Bayesian optimization is used in many areas of AI for the optimization of
black-box processes and has achieved impressive improvements of the state of
the art for a lot of applications. It intelligently explores large and complex
design spaces while minimizing the number of evaluations of the expensive
underlying process to be optimized. Materials science considers the problem of
optimizing materials’ properties given a large design space that defines how
to synthesize or process them, with evaluations requiring expensive
experiments or simulations – a very similar setting. While Bayesian
optimization is also a popular approach to tackle such problems, there is
almost no overlap between the two communities that are investigating the same
concepts. We present a survey of Bayesian optimization approaches in materials
science to increase cross-fertilization and avoid duplication of work. We
highlight common challenges and opportunities for joint research efforts.

##  1 Introduction

In many areas of AI, decades of research have resulted in many different
approaches for solving hard problems. Perhaps the best example is machine
learning, where dozens of different approaches just to classification are
available, with little guidance on what to use for a particular problem. While
random forests are usually a good choice, there are many problems where other
approaches provide better performance. Even human experts struggle to choose
the best approach for a given problem without significant experimentation
though. Worse, once a particular approach is chosen, its hyperparameters need
to be set for optimal performance – or is a different approach actually better
once its hyperparameters have been optimized?

This issue is not unique to machine learning – the optimization of the
hyperparameters of processes is a ubiquitous problem in AI and many other
areas, including materials science. While this can be done efficiently for
some applications, for example because gradients are available or other
knowledge about the optimized process can be leveraged, there are many
scenarios where nothing is known about the process – it is a black box that
can be evaluated, but whose inner workings are not sufficiently understood to
aid in the optimization process. Such black boxes are much harder to optimize
in practice.

Black-box processes are optimized by repeatedly evaluating them for different
hyperparameter settings and observing the effect changes in hyperparameter
values have – much like scientists have studied natural phenomena for
millennia. In many cases, these evaluations are expensive and it is crucial to
minimize their number as the optimization would otherwise use too many
resources. Bayesian optimization (BO) is a methodology that allows for just
that. It is a sample-efficient optimization method that, in general, does not
require a large number of samples to obtain good results and is thus
particularly suitable for black-box functions that are extremely expensive to
evaluate, as found in many areas of AI, engineering, and materials science,
where an evaluation may entail synthesizing and testing a new material and
require specialized equipment and skilled operators.

At the heart of modern Bayesian optimization approaches are machine-learning-
induced surrogate models, that learn to emulate the black-box process to be
optimized based on a small number of evaluations. Such surrogate models have a
long tradition in materials science where they helped in the development of
new materials and designs long before the advent of machine learning.
Traditionally, models were based on first-principles understanding and
physical laws that were painstakingly developed by scientists rather than the
data-driven approaches we see today.

Bayesian optimization, like surrogate models, is not a new concept, nor did it
originate in AI – its origins can be traced back decades to engineering
applications. It has gained increasing popularity in materials science in the
last decade, similar to popularity gains in AI in the same time period.
However, research in both fields proceeds almost entirely independently, with
no cross-fertilization taking place even though the problems solved are the
same in many cases. This survey aims to bridge this gap and increase awareness
in the AI community on relevant research and approaches being developed in
materials science. We provide an overview of relevant recent research and
highlight challenges in materials science that AI research can help with and
open problems that may benefit from joint efforts.

##  2 Background

In modern Bayesian optimization, a surrogate model is fit based on the results
of evaluating the black-box process at different points in the hyperparameter
space. Such an initial design could be random, or based on another design of
experiments approach. In most cases, this surrogate model is induced by a
machine learning algorithm; Gaussian Processes and random forests are popular
choices. An acquisition function then determines the next point in
hyperparameter space to evaluate the expensive black-box process at, based on
the predictions of the cheap-to-evaluate surrogate model and possibly
uncertainty quantifications of those predictions. This acquisition function
balances exploitation, i.e. evaluating the neighborhood of points known to
yield good performance, and exploration, i.e. evaluating points that are far
from regions of the hyperparameter space with known performance to avoid
getting stuck in local optima. Commonly-used acquisition functions include
expected improvement and maximum uncertainty, which always explores.

The expensive black-box function is then evaluated at the point proposed in
this way to obtain ground-truth data that is combined with the data from the
initial design. The updated data is used to obtain the surrogate model for the
next iteration of the optimization process. The incremental augmentation of
the data the surrogate model takes into account iteratively improves and
refines it for the areas of interest, yielding more accurate approximations of
the black-box function and better optimization results. The Bayesian
optimization process can be stopped at any time when the desired quality is
achieved or resources are exhausted. While this makes it convenient to deploy
in practice, there are no guarantees of convergence to a global optimum except
if an infinite number of evaluations of the black-box function are allowed. As
we make no assumptions about the optimization landscape, the quality of the
result cannot be guaranteed or even assessed except by comparison to the
results other methods or repeated BO runs achieve.

Figure 1: Example Bayesian optimization iteration. The horizontal axis shows
the parameter space, projected into one dimension. In the top panel, the solid
line is the true objective function; the dashed line is its surrogate-model-
based approximation. The gray-shaded areas indicate the uncertainty of
predictions of the surrogate model. Red circles represent evaluated
configurations used to build the initial surrogate model; green squares
configurations evaluated and added to the training data for the surrogate
model in previous iterations; and the blue triangle the proposed next
configuration to evaluate. The bottom panel shows the expected improvement
over the best configuration found so far; the highest peak coincides with the
proposed next configuration. Illustration generated with the mlrMBO package
Bischl et al. (2017).

Figure 1 illustrates surrogate model and acquisition function for one
iteration of a toy example. There are many variations of this general approach
and hybrid methods that incorporate techniques from other areas of AI have
been developed, for example meta-learning to leverage known good
hyperparameter configurations from similar applications. A complete exposition
is beyond the scope of this survey. For more details on Bayesian optimization,
we refer the interested reader to Jones et al. (1998); Mockus and Mockus
(1991) and Forrester et al. (2008) for Bayesian optimization in engineering in
particular.

##  3 Bayesian Optimization in AI

The optimization of black-box processes is relevant in many areas of AI; in
particular for the automated hyperparameter tuning of algorithms. For many
applications, software to solve problems have hyperparameters that allow to
choose and tune, for example; a search heuristic, a stopping criterion, or a
pruning mechanism. These choices provide added flexibility and enable
adaptation of a generic algorithm to a particular problem, but setting them to
achieve good performance in a specific setting is a difficult task even for
human experts.

There are numerous approaches that apply Bayesian optimization methods to
automated hyperparameter tuning in AI, for example Hutter et al. (2011), who
introduce the SMAC system and demonstrate its power tuning the hyperparameters
of SAT and MIP solvers. Snoek et al. (2012) propose the spearmint system and
automatically tune the hyperparameters of a machine learning algorithm,
whereas Feurer et al. (2015); Kotthoff et al. (2017) automatically choose the
machine learning approach and pre- and post-processing methods in addition to
tuning its hyperparameters.

Bischl et al. (2017) propose a general and flexible system for hyperparamter
tuning using Bayesian optimization, and Falkner et al. (2018) combine Bayesian
optimization with bandit-based methods. The need for hyperparameter tuning in
machine learning has resulted in the field of automated machine learning
(AutoML), which relies to a significant part on Bayesian optimization and
related methods. We refer the interested reader to a recent book Hutter et al.
(2019) for more.

##  4 Bayesian Optimization in Materials Science

A large application area of Bayesian optimization in materials science is
similar to how it is applied in AI – the optimization of the hyperparameters
of computationally expensive processes. In particular, Density Functional
Theory (DFT) simulations can compute properties of interest for a given
material, but may take weeks to complete. DFT calculations are used to
determine the electronic structure of systems composed of many atoms or
molecules, in particular the spatially dependent density of electrons, from
which properties of the modeled material can be derived. Such simulations rely
only on first-principles knowledge in quantum physics and are widely
applicable to many different types of materials. DFT and similar first-
principles-based simulations are the cornerstone in many areas of materials
science. Note that the DFT simulations themselves are not optimized, i.e. BO
is not applied to improve the simulation itself, but the underlying material –
DFT is used to avoid having to synthesize and experimentally evaluate a
material.

Kiyohara et al. (2016); Kikuchi et al. (2018); Bondevik et al. (2019) use BO
to optimize the grain boundary structure in polycrystalline materials instead
of exhaustively evaluating the design space for the materials. They all
demonstrate that results of similar quality to exhaustive evaluation can be
achieved at significantly lower cost, with an increase in efficiency by up to
two orders of magnitude. Similarly, Ueno et al. (2016) optimize the grain
boundary energy over several thousand precomputed hyperparameter
configurations, which allows them to compare the performance of different
approaches. Talapatra et al. (2018) employ BO in a similar setting by
evaluating its performance on a set of a few hundred precomputed results. They
optimize the elastic properties of a material and demonstrate that BO is
quickly able to identify the optimal hyperparameters in their relatively small
approximation of the real search space. Balachandran et al. (2016) investigate
the same application and in subsequent publications demonstrate the
effectiveness of BO to optimize shape memory alloys Xue et al. (2016), the
band gap in perovskites, an important material in the creation of solar cells
Pilania et al. (2017), and the band gap in compounds for luminescent materials
Lookman et al. (2019). Ling et al. (2017) demonstrate the utility of BO to
optimize the DFT-calculated magnetic deformation of a material,
superconductors, thermoelectricity, and the strength of steel. Hankins et al.
(2019) apply BO to the problem of creating new materials via a parameterized
generator for patterns that describe the structure of the material. They
optimize the interfacial area of the material, which can be computed directly
and very cheaply compared to numerical simulations, but the large
hyperparameter space still necessitates a more efficient hyperparameter
optimization approach than exhaustive search. Dehghannasiri et al. (2017)
design materials with low energy dissipation by optimizing a dopant (an
impurity introduced into a pure material of a different type) and its
concentration using BO, showing improvements over random search and pure
exploitation.

Seko et al. (2014) perform one of the earliest investigations into whether BO
is suitable for optimizing the properties of materials that are evaluated
using DFT. In particular, they focus on the performance of the surrogate model
that replaces the DFT calculations, a crucial prerequisite for applying BO.
They predict and optimize the melting temperature of solid compounds and find
that support vector regression in particular provides high-quality predictions
of the DFT results. However, they use Gaussian Processes in a BO framework to
optimize the melting temperature, demonstrating better performance than random
search. A subset of the authors provide additional applications in a later
study Tanaka and Seko (2016) that more explicitly distinguishes between high-
throughput approaches where an exhaustive grid search is performed and
applications where this is infeasible and the use of BO or a similar technique
is necessary.

In contrast to most areas of AI, a lot of materials science is not only
computational, but involves physical experiments that synthesize and evaluate
materials. While DFT and similar simulations are increasingly accurate, their
results are often only approximations of what happens in the real world due to
different scales or a lack of first-principles understanding – DFT
calculations can only consider relatively small numbers of atoms or molecules
that may not accurately represent materials deployed in practical
applications. Even more so than for computational simulations, BO is useful to
reduce experimental effort in the optimization of materials that requires not
only physical resources, but also in many cases specialized equipment and the
time of a skilled operator.

Ren et al. (2018) use a manual version of BO to discover metallic glasses.
They train a random forest model to predict whether a particular composition
of precursor materials results in the formation of a glass based on prior
experimental results. The model is then used to manually identify the region
with the highest promise for gathering additional data through high-throughput
experimentation, allowing for many evaluations in a short amount of time. The
experimental results obtained in this way are used to refine the model. The
authors iterate this process three times and discover several new glass-
forming systems. Häse et al. (2018) use BO to optimize the conditions for a
chemical reaction to achieve a certain stability condition. While the
optimized experimental conditions could be evaluated through actual
experiments, the authors use a simulator to achieve higher throughput and
obtain more data. They show that BO is not only able to obtain the desired
results quickly, but also does so more robustly than other approaches, namely
particle swarm optimization and CMA-ES. Kotthoff et al. (2019) optimize the
reduction of graphene oxide to graphene in the context of creating nano-
circuits and flexible electronics. The evaluations of the black-box function
rely on physical experiments that are performed manually and thus the number
of data points is only a few dozen. However, the authors demonstrate that even
in this case, significant improvements of the experimental outcome over human
experts can be achieved. Wigley et al. (2016) optimize the production of Bose-
Einstein condensates with BO, which they refer to as machine learning online
optimization, with an order of magnitude fewer evaluations than previous
approaches. Ren et al. (2020) optimize the efficiency of solar cells by tuning
the growth temperature of gallium arsenide cells. Their customized BO approach
is able to achieve improvements after only five experimental evaluations.
Vellanki et al. (2017) optimize alloy casting and the production of polymer
fibers in a constrained batch process, but do not provide a baseline
comparison for their results.

Some approaches combine computational simulations with experiments or
different types of simulations with different fidelities and costs for
multiple layers of screening. This allows to improve the outcomes of the
optimization process while reducing the costs for evaluations of the black box
functions. Indeed, this is a major difference to applications of BO in AI,
where usually there is only a single way of evaluating the black box function
to be optimized. The closest to evaluations at multiple levels are techniques
like early stopping, used for example in SMAC, that stop the evaluation if the
hyperparameter setting under configuration does not show promise on a subset
of the data, e.g. a fraction of the folds for a machine learning problem or a
subset of the problem instances for a combinatorial optimization algorithm.

Gómez-Bombarelli et al. (2016) optimize the design of OLEDs. They pre-screen
designs using a machine learning surrogate model, then perform DFT
calculations on the remaining candidates, and finally synthesize and
experimentally evaluate the candidate designs that pass this second screening.
While the authors do not use BO directly, they demonstrate the power of a
multi-level, multi-fidelity approach in efficiently exploring a large search
space. Pilania et al. (2017) combine different types of DFT simulations, one
low-fidelity simulation that can be computed quickly, and one high-fidelity
simulation, to optimize the bandgap of solids. They use a modified Gaussian
Process that is able to take information at multiple fidelities into account
directly as a surrogate model and demonstrate better outcomes than when using
only the high-fidelity data. Patra et al. (2020) apply the same approach to
optimizing the bandgap of polymers and demonstrate similar results, noting
that their multi-fidelity surrogate model is able to generalize better to a
larger design space than surrogate models that use only high-fidelity data.

The majority of approaches in both AI and materials science consider single-
objective BO, as multi-objective optimization increases complexity
considerably and multiple objectives can be combined into a single objective.
However, a few approaches apply multi-objective BO to avoid requiring the user
to specify how to weight different objectives and being able to choose the
trade-off after the optimization from points on the Pareto front. Talapatra et
al. (2018) consider the two competing objectives of shear and bulk modulus,
which quantify the effect external forces have on the material. The authors
use expected hypervolume improvement as the acquisition function and show that
they can efficiently identify the points on the Pareto front. Solomou et al.
(2018) consider the simultaneous optimization of up to three properties of a
particular type of alloy based on computational simulations. They also use
expected hypervolume improvement as the acquisition function and demonstrate
the effectiveness of their approach. Ragasa et al. (2019) scale up to 10
objectives, but use a custom non-BO approach, though inspired by Bayesian
optimization, that iteratively refines the hyperparameter search space based
on found Pareto-optimal configurations.

In many applications, it may be desirable to batch evaluations of the black
box function to be optimized, i.e. have the BO process predict multiple
hyperparameter configurations at once. This can facilitate the parallel
evaluation of configurations to make optimal use of available resources. This
is common to both AI and materials science, though there are few approaches
that do it. Häse et al. (2018) propose batches of configurations to evaluate
by optimizing the acquisition functions for different values of a parameter
that trades off exploration and exploitation. The authors demonstrate that
this batch evaluation improves overall performance, as the correct setting for
this parameter is unclear and varies over time. A unique issue in BO for
materials science that does not usually come up in an AI setting is that the
first hyperparameter configuration to evaluate may constrain subsequent
configurations. Vellanki et al. (2017) give the examples of heat treatment of
alloys, where multiple samples can be processed at the same time in an oven
but at a fixed temperature, and the production of polymer fibers, where
different values for polymer flow and coagulant speed can be evaluated at the
same time but within a fixed geometry. They propose a nested BO approach that
optimizes the hyperparameters that are subject to constraints in an outer loop
and, given the optimized values, the unconstrained hyperparameters in an inner
loop.

In many applications of BO in materials science, standard BO approaches,
usually with Gaussian Processes as surrogate models and expected improvement
as acquisition function, are used. There are a few exceptions; for example
Häse et al. (2018) use Bayesian Neural Networks as a surrogate model with a
custom acquisition function and Pilania et al. (2017); Patra et al. (2020) use
custom Gaussian Processes that can take information at multiple fidelities
into account, with an acquisition function that takes the cost difference of
the different fidelities into account. Dehghannasiri et al. (2017) use mean
objective cost of uncertainty as the acquisition function, which quantifies
how much worse an outcome is because of uncertainty. Ren et al. (2020) replace
the traditional BO approach with multiple layers of surrogate models of
Bayesian networks infused with background knowledge that constrains the
(intermediate) outputs to physically feasible ones, combined with a neural
network that serves as a surrogate for expensive numerical simulations.
Vellanki et al. (2017) propose a nested approach that runs a series of BO
processes to propose a batch of hyperparameter configurations to evaluate.
Talapatra et al. (2018) use Bayesian model averaging inside the BO process to
select the most suitable surrogate model at the same time as optimizing the
black-box process. Ueno et al. (2016) augment BO with automated hyperparameter
tuning and a few changes to be able to sample and optimize the surrogate model
more efficiently with thousands of features.

Most publications compare their approaches only to a grid or random search,
but some study the effect variations of the BO process have. Ling et al.
(2017) propose a BO framework that uses random forests as surrogate models
with three different acquisition functions and demonstrate that using
likelihood of improvement instead of expected improvement performs better on
their case studies. Balachandran et al. (2016) on the other hand compare the
performance of different surrogate models with the same acquisition function.
They note that models that quantify the uncertainty of their predictions show
better performance than those that do not, and find that support vector
regression with an RBF kernel gives the best surrogate models, similar to the
findings of Seko et al. (2014).

In most cases, BO approaches in materials science are developed without
awareness of similar efforts in AI. A notable exception is Häse et al. (2018),
who compare to SMAC (Hutter et al., 2011) and spearmint (Snoek et al., 2012),
as well as non-BO optimization methods. They demonstrate that their proposed
system Phoenics achieves better performance, differing from the other BO
approaches in a different surrogate model (Bayesian Neural Networks) and an
acquisition function based on kernel densities.

##  5 Research Directions

The application of Bayesian optimization in materials science is guided by the
domain. In particular, this means that achieving performance improvements is
perhaps not as important as in AI, and there is more emphasis on understanding
the models and being able to incorporate additional constraints that encode
the physical knowledge governing the application, as many of the approaches
mentioned above do.

Explainable AI has emerged as an important research area in AI with the
increasing deployment of AI models that facilitate decision making. In
particular deep neural network models are difficult to understand, with real-
world ramifications on their performance. Almost all publications in materials
science incorporate some analysis of what surrogate models have learned, often
with respect to the importance of the features used to characterize the
optimized process (e.g. Kotthoff et al. (2019)). To the best of our knowledge,
these approaches are relatively straightforward and more sophisticated
techniques developed by the AI community, for example the SHAP framework
Lundberg and Lee (2017), have not been applied yet.

Another aspect that is emphasized more in materials science than in AI is the
quantification of the uncertainties of a surrogate model, which Ling et al.
(2017) specifically develop for random forest surrogate models. This may be
the reason that Gaussian Processes remain the most popular surrogate model,
although different authors have observed that support vector machine models
achieve better predictive accuracy. This is a potential research direction for
the AI community that would benefit materials science directly.

Lookman et al. (2016) highlight the successes machine learning in general has
had in materials science, but conclude that more applications are required to
give the community guidelines on how to apply BO and machine learning in the
wider sense in the context of materials science. While, as outlined above, a
standard incarnation of BO with Gaussian Processes as surrogate models and
expected improvement as acquisition function is emerging as a reasonable place
to start, there is likely no single approach that will perform best in all
settings – a fact that has been known in AI for decades and leveraged in the
emerging field of automated machine learning Hutter et al. (2019) for example.
While some approaches in materials science are already taking advantage of
these powerful techniques, a more ubiquitous integration of AutoML techniques
into materials science tools would likely increase the uptake of BO in this
area.

de Pablo et al. (2019) identify a lack of systematic methods for reporting the
performance of machine learning approaches and baselines to compare to as one
of the challenges in materials science. This is again an area where AI
research can help, as the same issues are relevant and have been investigated
longer. The authors note that “[e]stablished approaches from the statistics
and computer science communities combined with new methods developed
specifically for materials data issues must be disseminated to the materials
community[…]” – a challenge for our community to reach out more and organize
interdisciplinary events. Similarly, they note that most research in machine
learning focuses on large datasets which are usually not available in
materials science. Especially since the advent of deep learning, such small
data problems have been somewhat neglected by the AI community and there are
opportunities to develop new approaches at the intersection of materials and
AI.

Kalidindi (2019) mentions similar concerns and in particular notes that a
significant issue in materials science is the fragmented storage and
availability of the relevant data. Similar issues have been tackled by the AI
community and resulted in standard data formats and repositories that may be
applicable in a materials context as well, for example the OpenML project
Vanschoren et al. (2013). The author further highlights the challenge of
integrating the governing physical laws into a BO process and proposes a
framework to tackle this. Similar efforts to include background knowledge in
machine learning and data mining have been undertaken in AI, for example in
the ICON project Bessière et al. (2016), but no joint efforts exist to the
best of our knowledge.

While most research proceeds independently in AI and materials science, there
are a few joint efforts, notably Vellanki et al. (2017), which propose
constrained batch optimization and evaluate their approach both for a machine
learning and materials science applications. This demonstrates that both
fields can benefit from advances and makes a strong case for increased
collaboration between AI and materials science researchers.

##  6 Conclusion

We have presented an overview of applications of Bayesian optimization in
materials science, where researchers want to optimize poorly-understood black-
box processes to achieve desired properties of materials. Similar to
applications of BO in AI, the focus is on minimizing the number of evaluations
of the expensive black-box function while maximizing the quality of the
result, and similar results have been achieved, firmly establishing Bayesian
optimization as a state-of-the-art method that should be in the toolkit of
every materials science researcher.

A lot of recent progress in materials science has been enabled by Bayesian
optimization. However, a lot of work remains to be done to improve BO in
practice and scale to more difficult problems, in particular ones with
multiple objectives and large numbers of features, and integrate data-driven
methodologies with first-principles knowledge.

Materials science presents some unique challenges to applying Bayesian
optimization that can stimulate research in AI and, ultimately, benefit
applications of BO in AI as well. Research to date has progressed almost
independently in both application domains, and we hope that this survey will
stimulate interdisciplinary efforts and joint projects that advance either and
both fields.

## References

  * Balachandran et al. [2016] Prasanna V. Balachandran, Dezhen Xue, James Theiler, John Hogden, and Turab Lookman.  Adaptive Strategies for Materials Design using Uncertainties.  _Scientific Reports_ , 6:19660, January 2016.  URL https://doi.org/10.1038/srep19660.
  * Bessière et al. [2016] Christian Bessière, Luc De Raedt, Lars Kotthoff, Siegfried Nijssen, Barry O’Sullivan, and Dino Pedreschi, editors.  _Data Mining and Constraint Programming: Foundations of a Cross-Disciplinary Approach_ , volume 10101 of _Lecture Notes in Artificial Intelligence_.  Springer, 1 edition, 2016.  ISBN 978-3-319-50137-6.
  * Bischl et al. [2017] Bernd Bischl, Jakob Richter, Jakob Bossek, Daniel Horn, Janek Thomas, and Michel Lang.  mlrMBO: A Modular Framework for Model-Based Optimization of Expensive Black-Box Functions.  March 2017.  arXiv: 1703.03373.
  * Bondevik et al. [2019] Tarjei Bondevik, Akihide Kuwabara, and Ole Martin Løvvik.  Application of machine learning-based selective sampling to determine bazro3 grain boundary structures.  _Computational Materials Science_ , 164:57–65, 2019.  ISSN 0927-0256.
  * de Pablo et al. [2019] Juan J. de Pablo, Nicholas E. Jackson, Michael A. Webb, Long-Qing Chen, Joel E. Moore, Dane Morgan, Ryan Jacobs, Tresa Pollock, Darrell G. Schlom, Eric S. Toberer, James Analytis, Ismaila Dabo, Dean M. DeLongchamp, Gregory A. Fiete, Gregory M. Grason, Geoffroy Hautier, Yifei Mo, Krishna Rajan, Evan J. Reed, Efrain Rodriguez, Vladan Stevanovic, Jin Suntivich, Katsuyo Thornton, and Ji-Cheng Zhao.  New frontiers for the materials genome initiative.  _npj Computational Materials_ , 5(1):41, April 2019.  ISSN 2057-3960.  doi: 10.1038/s41524-019-0173-4.
  * Dehghannasiri et al. [2017] Roozbeh Dehghannasiri, Dezhen Xue, Prasanna V. Balachandran, Mohammadmahdi R. Yousefi, Lori A. Dalton, Turab Lookman, and Edward R. Dougherty.  Optimal experimental design for materials discovery.  _Computational Materials Science_ , 129:311–322, 2017.  ISSN 0927-0256.  doi: https://doi.org/10.1016/j.commatsci.2016.11.041.
  * Falkner et al. [2018] Stefan Falkner, Aaron Klein, and Frank Hutter.  BOHB: Robust and Efficient Hyperparameter Optimization at Scale.  In _35th International Conference on Machine Learning_ , volume 80, pages 1437–1446, July 2018.
  * Feurer et al. [2015] Matthias Feurer, Aaron Klein, Katharina Eggensperger, Jost Springenberg, Manuel Blum, and Frank Hutter.  Efficient and Robust Automated Machine Learning.  In _Advances in Neural Information Processing Systems 28_ , pages 2944–2952. Curran Associates, Inc., 2015.
  * Forrester et al. [2008] Alexander I. J. Forrester, Andras Sobester, and Andy J. Keane.  _Engineering Design via Surrogate Modelling - A Practical Guide_.  Wiley, 2008.  ISBN 978-0-470-06068-1.
  * Gómez-Bombarelli et al. [2016] Rafael Gómez-Bombarelli, Jorge Aguilera-Iparraguirre, Timothy D. Hirzel, David Duvenaud, Dougal Maclaurin, Martin A. Blood-Forsythe, Hyun Sik Chae, Markus Einzinger, Dong-Gwang Ha, Tony Wu, Georgios Markopoulos, Soonok Jeon, Hosuk Kang, Hiroshi Miyazaki, Masaki Numata, Sunghan Kim, Wenliang Huang, Seong Ik Hong, Marc Baldo, Ryan P. Adams, and Alán Aspuru-Guzik.  Design of efficient molecular organic light-emitting diodes by a high-throughput virtual screening and experimental approach.  _Nature Materials_ , 15:1120, August 2016.  URL https://doi.org/10.1038/nmat4717.
  * Hankins et al. [2019] Sarah Hankins, Lars Kotthoff, and Ray S. Fertig.  Bio-like Composite Microstructure Designs for Enhanced Damage Tolerance via Machine Learning.  In _American Society for Composites 34th Annual Technical Conference_ , September 2019.
  * Hutter et al. [2011] Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown.  Sequential Model-Based Optimization for General Algorithm Configuration.  In _LION 5_ , pages 507–523, 2011.
  * Hutter et al. [2019] Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren, editors.  _Automated Machine Learning: Methods, Systems, Challenges_.  The Springer Series on Challenges in Machine Learning. Springer, 2019.  ISBN 978-3-030-05317-8.
  * Häse et al. [2018] Florian Häse, Loïc M. Roch, Christoph Kreisbeck, and Alán Aspuru-Guzik.  Phoenics: A Bayesian Optimizer for Chemistry.  _ACS Central Science_ , 4(9):1134–1145, September 2018.  ISSN 2374-7943.  doi: 10.1021/acscentsci.8b00307.
  * Jones et al. [1998] Donald R. Jones, Matthias Schonlau, and William J. Welch.  Efficient Global Optimization of Expensive Black-Box Functions.  _J. of Global Optimization_ , 13(4):455–492, December 1998.  ISSN 0925-5001.  doi: 10.1023/A:1008306431147.
  * Kalidindi [2019] Surya R. Kalidindi.  A bayesian framework for materials knowledge systems.  _MRS Communications_ , 9(2):518–531, 2019.  doi: 10.1557/mrc.2019.56.
  * Kikuchi et al. [2018] Shun Kikuchi, Hiromi Oda, Shin Kiyohara, and Teruyasu Mizoguchi.  Bayesian optimization for efficient determination of metal oxide grain boundary structures.  _Physica B: Condensed Matter_ , 532:24–28, 2018.  ISSN 0921-4526.  Special issue on Frontiers in Materials Science: Condensed Matters.
  * Kiyohara et al. [2016] Shin Kiyohara, Hiromi Oda, Koji Tsuda, and Teruyasu Mizoguchi.  Acceleration of stable interface structure searching using a kriging approach.  _Japanese Journal of Applied Physics_ , 55(4):045502, March 2016.  doi: 10.7567/jjap.55.045502.
  * Kotthoff et al. [2017] Lars Kotthoff, Chris Thornton, Holger H. Hoos, Frank Hutter, and Kevin Leyton-Brown.  Auto-WEKA 2.0: Automatic model selection and hyperparameter optimization in WEKA.  _Journal of Machine Learning Research_ , 18(25):1–5, 2017.
  * Kotthoff et al. [2019] Lars Kotthoff, Vivek Jain, Alexander Tyrrell, Hud Wahab, and Patrick Johnson.  AI for Materials Science: Tuning Laser-Induced Graphene Production.  In _Data Science Meets Optimisation Workshop at IJCAI 2019_ , August 2019.
  * Ling et al. [2017] Julia Ling, Maxwell Hutchinson, Erin Antono, Sean Paradiso, and Bryce Meredig.  High-Dimensional Materials and Process Optimization Using Data-Driven Experimental Design with Well-Calibrated Uncertainty Estimates.  _Integrating Materials and Manufacturing Innovation_ , 6(3):207–217, September 2017.  ISSN 2193-9772.  doi: 10.1007/s40192-017-0098-z.
  * Lookman et al. [2016] Turab Lookman, P. V. Balachandran, D. Xue, G. Pilania, T. Shearman, J. Theiler, J. E. Gubernatis, J. Hogden, K. Barros, E. BenNaim, and Francis J. Alexander.  A Perspective on Materials Informatics: State-of-the-Art and Challenges.  In Turab Lookman, Francis J. Alexander, and Krishna Rajan, editors, _Information Science for Materials Discovery and Design_ , pages 3–12. Springer International Publishing, Cham, 2016.  ISBN 978-3-319-23871-5.  doi: 10.1007/978-3-319-23871-5˙1.
  * Lookman et al. [2019] Turab Lookman, Prasanna V. Balachandran, Dezhen Xue, and Ruihao Yuan.  Active learning in materials science with emphasis on adaptive sampling using uncertainties for targeted design.  _npj Computational Materials_ , 5(1):21, February 2019.  ISSN 2057-3960.  doi: 10.1038/s41524-019-0153-8.
  * Lundberg and Lee [2017] Scott M Lundberg and Su-In Lee.  A Unified Approach to Interpreting Model Predictions.  In _Advances in Neural Information Processing Systems_ , pages 4765–4774, 2017.
  * Mockus and Mockus [1991] Jonas B. Mockus and Linas J. Mockus.  Bayesian approach to global optimization and application to multiobjective and constrained problems.  _Journal of Optimization Theory and Applications_ , 70(1):157–172, July 1991.  ISSN 1573-2878.  doi: 10.1007/BF00940509.
  * Patra et al. [2020] Abhirup Patra, Rohit Batra, Anand Chandrasekaran, Chiho Kim, Tran Doan Huan, and Rampi Ramprasad.  A multi-fidelity information-fusion approach to machine learn and predict polymer bandgap.  _Computational Materials Science_ , 172:109286, 2020.  ISSN 0927-0256.
  * Pilania et al. [2017] Ghanshyam Pilania, James E. Gubernatis, and Turab Lookman.  Multi-fidelity machine learning models for accurate bandgap predictions of solids.  _Computational Materials Science_ , 129:156–163, 2017.  ISSN 0927-0256.  doi: https://doi.org/10.1016/j.commatsci.2016.12.004.
  * Ragasa et al. [2019] Eugene J. Ragasa, Christopher J. O’Brien, Richard G. Hennig, Stephen M. Foiles, and Simon R. Phillpot.  Multi-objective optimization of interatomic potentials with application to MgO.  _Modelling and Simulation in Materials Science and Engineering_ , 27(7):074007, August 2019.  doi: 10.1088/1361-651x/ab28d9.
  * Ren et al. [2018] Fang Ren, Logan Ward, Travis Williams, Kevin J. Laws, Christopher Wolverton, Jason Hattrick-Simpers, and Apurva Mehta.  Accelerated discovery of metallic glasses through iteration of machine learning and high-throughput experiments.  _Science Advances_ , 4(4), 2018.  doi: 10.1126/sciadv.aaq1566.
  * Ren et al. [2020] Zekun Ren, Felipe Oviedo, Maung Thway, Siyu I. P. Tian, Yue Wang, Hansong Xue, Jose Dario Perea, Mariya Layurova, Thomas Heumueller, Erik Birgersson, Armin G. Aberle, Christoph J. Brabec, Rolf Stangl, Qianxiao Li, Shijing Sun, Fen Lin, Ian Marius Peters, and Tonio Buonassisi.  Embedding physics domain knowledge into a Bayesian network enables layer-by-layer process innovation for photovoltaics.  _npj Computational Materials_ , 6(1):1–9, January 2020.  ISSN 2057-3960.  doi: 10.1038/s41524-020-0277-x.  URL https://www.nature.com/articles/s41524-020-0277-x.
  * Seko et al. [2014] Atsuto Seko, Tomoya Maekawa, Koji Tsuda, and Isao Tanaka.  Machine learning with systematic density-functional theory calculations: Application to melting temperatures of single- and binary-component solids.  _Phys. Rev. B_ , 89(5):054303, 2014.  doi: 10.1103/PhysRevB.89.054303.
  * Snoek et al. [2012] Jasper Snoek, Hugo Larochelle, and Ryan P. Adams.  Practical Bayesian Optimization of Machine Learning Algorithms.  In _Advances in Neural Information Processing Systems 25_ , pages 2951–2959, 2012.
  * Solomou et al. [2018] Alexandros Solomou, Guang Zhao, Shahin Boluki, Jobin K. Joy, Xiaoning Qian, Ibrahim Karaman, Raymundo Arróyave, and Dimitris C. Lagoudas.  Multi-objective bayesian materials discovery: Application on the discovery of precipitation strengthened niti shape memory alloys through micromechanical modeling.  _Materials and Design_ , 160:810–827, 2018.  ISSN 0264-1275.
  * Talapatra et al. [2018] Anjana Talapatra, Shahin Boluki, Thien Duong, Xiaoning Qian, Edward Dougherty, and Raymundo Arróyave.  Autonomous efficient experiment design for materials discovery with Bayesian model averaging.  _Phys. Rev. Materials_ , 2(11):113803, 2018.  doi: 10.1103/PhysRevMaterials.2.113803.
  * Tanaka and Seko [2016] Isao Tanaka and Atsuto Seko.  Toward Materials Discovery with First-Principles Datasets and Learning Methods.  In Turab Lookman, Francis J. Alexander, and Krishna Rajan, editors, _Information Science for Materials Discovery and Design_ , pages 173–186. Springer International Publishing, 2016.  doi: 10.1007/978-3-319-23871-5˙9.
  * Ueno et al. [2016] Tsuyoshi Ueno, Trevor David Rhone, Zhufeng Hou, Teruyasu Mizoguchi, and Koji Tsuda.  COMBO: An efficient Bayesian optimization library for materials science.  _Materials Discovery_ , 4:18–21, 2016.  ISSN 2352-9245.  doi: https://doi.org/10.1016/j.md.2016.04.001.
  * Vanschoren et al. [2013] Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo.  OpenML: Networked Science in Machine Learning.  _SIGKDD Explorations_ , 15(2):49–60, 2013.  doi: 10.1145/2641190.2641198.
  * Vellanki et al. [2017] Pratibha Vellanki, Santu Rana, Sunil Gupta, David Rubin, Alessandra Sutti, Thomas Dorin, Murray Height, Paul Sanders, and Svetha Venkatesh.  Process-constrained batch bayesian optimisation.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , pages 3414–3423. Curran Associates, Inc., 2017\.
  * Wigley et al. [2016] Paul B. Wigley, Patrick J. Everitt, Anton van den Hengel, John W. Bastian, Mahasen A. Sooriyabandara, Gordon D. McDonald, Kyle S. Hardman, Ciaron D. Quinlivan, Manju Perumbil, Carlos C. N. Kuhn, Ian R. Petersen, Andre N. Luiten, Joseph J. Hope, Nicholas P. Robins, and Michael R. Hush.  Fast machine-learning online optimization of ultra-cold-atom experiments.  _Scientific reports_ , 6:25890–25890, 2016.  ISSN 2045-2322.  doi: 10.1038/srep25890.
  * Xue et al. [2016] Dezhen Xue, Prasanna V. Balachandran, John Hogden, James Theiler, Deqing Xue, and Turab Lookman.  Accelerated search for materials with targeted properties by adaptive design.  _Nature Communications_ , 7:11241, April 2016.  URL https://doi.org/10.1038/ncomms11241.