# Controllable Missingness from Uncontrollable Missingness:
Joint Learning Measurement Policy and Imputation

Seongwook Yoon  Jae Hyun Kim  Heejeong Lim  Sanghoon Sull

###### Abstract

Due to the cost or interference of measurement, we need to control measurement
system. Assuming that each variable can be measured sequentially, there exists
optimal policy choosing next measurement for the former observations. Though
optimal measurement policy is actually dependent on the goal of measurement,
we mainly focus on retrieving complete data, so called as imputation. Also, we
adapt the imputation method to missingness varying with measurement policy.
However, learning measurement policy and imputation requires complete data
which is impossible to be observed, unfortunately. To tackle this problem, we
propose a data generation method and joint learning algorithm. The main idea
is that 1) the data generation method is inherited by imputation method, and
2) the adaptation of imputation encourages measurement policy to learn more
than individual learning. We implemented some variations of proposed algorithm
for two different datasets and various missing rates. From the experimental
results, we demonstrate that our algorithm is generally applicable and
outperforms baseline methods.

Machine Learning

##  1 Introduction

Data acquisition, or simply measurement, is one of the most important parts in
science and engineering. However, measurement has many of natural corruptions
to acquire complete data such as, mainly, additive noise and missingness.
Without using corrupted raw data, in the field of signal process, various
methods have been studied to retrieve complete data, e.g., denoising for
additive noise and imputation for missingness. Historically, Wiener filer
(Helstrom, 1967), wavelet transform (Donoho, 1995) and singular value
decomposition (Brand, 2002) are used to denoise image or audio signal. On the
other hand, in the field of physics or system design, there have been much
more studies to tackle the natural corruption in the sense of making sensors
better. While the field of signal processing has utilized machine learning
frequently (Elad & Aharon, 2006; Burger et al., 2012; Zhang et al., 2017), the
other fields have focused on hardware design and low-level data processing
rather than machine learning techniques.

Figure 1: In sequential measurement, policy chooses next variable to be
measured for given observed variables. After the iteration stops incompletely,
resulting missing data is imputed into complete data.

Missingness, one of the major natures of measurement, can occur in various
ways. A stereotype of missingness is caused by measurement failure, i.e.,
someone tries to measure but cannot. Otherwise, another type of missingness is
caused by measurement policy, i.e., someone decides not to measure. We can
call the second type of missingness as controllable missingness. Generally
speaking, controllable missingness needs an optimal measurement policy to
maximize measurement performance constrained by the cost and limitations. For
example, in factory manufacturing process, there exist various measurement
policies from static ones like uniform sampling to adaptive ones concerning
current state of manufacturing process (Nduhura-Munga et al., 2013). Also,
sampling techniques used in big data analysis can be interpreted as the
measurement policy (Settles, 2009; Rojas et al., 2017). In this paper, we
formulate a machine learning problem to find optimal measurement policy based
on imputation.

One of the major topics about missingness is imputation to retrieve complete
data from missing data. Since missingness frequently occurs in medical or
industrial data, imputation is studied in such fields (Barnard & Meng, 1999;
Lakshminarayan et al., 1999; Mackinnon, 2010). However, imputation may not be
the most critical part for the missingness caused by measurement failure. The
more important point of such missingness is detection and itself can produce
other clues for the following data analysis. Besides, provided that
measurement system is sufficiently reliable, corresponding missing rate would
be sufficiently low, i.e., highly missing data implies catastrophic
measurement failure. Conversely, controllable missingness caused by
measurement policy has different characteristics. As measurement is rejected
typically due to cost or interference of measurement, many measurement systems
would suffer from the missingness, even if the measurement system is reliable.
For example, the missing rate of measurement in semiconductor manufacturing
process is very high, because a wafer cannot be sampled frequently due to the
cost and interference of the measurement process (Lee et al., 2019; Yugma et
al., 2015). Thus, in the controllable missingness with high missing rate,
imputation becomes much more critical and challenging. Especially, when
uncertainties of missing values are too high to be represented uni-modal
distribution, multiple imputation is necessary (Buuren & Groothuis-Oudshoorn,
2010; Yoon & Sull, 2020).

In this paper, therefore, we focus on the controllable missingness driven by
measurement policy but the acquired data is highly missing so as to be imputed
well. To this end, we formulate a reinforcement learning problem for
measurement policy to maximize the resulting imputation performance. Also, we
will discuss about the detail of scenario which is the most reasonable but
challenging to tackle with. First of all, 1) We assume that we can observe the
data components sequentially. If we should observe data at once without any
prior observation, there is no need to make policy. Thus, in our scenario,
policy repeats observation and decision recursively, i.e., we decide to
observe from previous observations. Also, 2) We assume that we cannot observe
any complete data for learning. In some cases, there would be hard frequency
limitation for measurement which disallows us to compute exact imputation
performance to be maximized. For the purpose of generality, 3) we assume that
there is no prior knowledge for data. More precisely, as we do not have any
measurement policy except most uninformative one, the corresponding
missingness would be uniformly missing at completely random (MCAR). Note that
this does not imply that we focus only on the case of MCAR, because the
missingness driven by learned measurement policy can be the case of missing at
random, as we discuss in Section 4. In short, our proposal is to find optimal
controllable missingness by learning measurement policy from uncontrollable
missingness driven by uninformative measurement policy.

To this end, we propose simple but efficient learning algorithm for both
measurement policy and imputation. Our learning algorithm train both jointly
despite of the absence of complete dataset. While imputation can be learned
without complete dataset in various ways (Lakshminarayan et al., 1996; Raja &
Thangavel, 2020; Yoon et al., 2018), reinforcement learning for measurement
policy requires complete data mainly for two reasons. Without complete data,
reward for imputation performance should be replaced with less accurate one.
Also, more severe one is that measurement policy cannot even explore any
action space except the initial uninformative actions. To tackle this problem,
we propose a general complete data generation method from the idea that
imputation implies conditional generation of complete data. Another important
point of the reinforcement learning for measurement policy is that the
imputation actually belongs to environment but it can response
Unintentionally. Thus, imputation needs to adapt for possible missingness
driven by learned measurement policy.

In proposed learning algorithm, the measurement policy and the imputation are
jointly learned. Imputation is learned not only in the sense of adaptation to
measurement policy, as mentioned above, but also in the sense of continual or
incremental learning. Imputation should learn more from potentially better
measurement policy, while it plays a role of complete data generation also. On
the other hand, measurement policy is also learned by two perspectives. The
first one is to learn better measurement policy without adaptation of
imputation and the second one is to learn potentially better measurement
policy which leads adaptation positively.

In this paper, we introduce related works in Section 2, formulated our problem
in Section 3, analyze the problem generally in Section 4, propose the detail
of our learning algorithm in Section 5, show implementations and experimental
results for sinusoidal dataset and MNIST (LeCun et al., 1998) in Section 6,
and conclude in Section 7.

##  2 Related Works

In this section, we introduce several works from general definitions to
contemporary studies related with our proposal. Especially, we introduce
important concepts of missingness and imputation with respect to them. Plus,
we shortly about fundamentals of reinforcement learning and actor-critic
method which we mainly use at implementation.

###  2.1 Missingness

Typically, missingness can be represented with binary mask
$\boldsymbol{\mathrm{m}}$ of which component is 1 if observed, and 0 if not
observed. Then, in order to describe the statistics of missingness, the
distribution of mask is utilized. There are three types of missingness in
terms of dependency between mask and data. The first type is missing
completely at random, call as MCAR, of which mask is independent with entire
data. Since both observed data and unobserved data are independent with the
missingness, data analysis is unbiased regardless of imputation. The second
type is missing at random, called as MAR, of which mask is independent with
unobserved data. This type of missingness typically relies on assumption that
most of the important data dependent with mask could be observed well. The
third type is missing not at random, MNAR, of which mask is also dependent
with unobserved data. In short, we can represent those types of missingness
using the distribution of mask as below:

$P(\boldsymbol{\mathrm{m}}|\boldsymbol{\mathrm{x}})=\begin{cases}P(\boldsymbol{\mathrm{m}})&\quad\text{if
MCAR}\\\
P(\boldsymbol{\mathrm{m}}|\boldsymbol{\mathrm{x}}_{\text{o}})&\quad\text{if
MAR}\\\
P(\boldsymbol{\mathrm{m}}|\boldsymbol{\mathrm{x}}_{\text{o}},\boldsymbol{\mathrm{x}}_{\setminus\text{o}})&\quad\text{if
MNAR}\end{cases},$ (1)

where $\boldsymbol{\mathrm{x}}$ is complete data, $\boldsymbol{\mathrm{m}}$ is
mask for missing data, $\boldsymbol{\mathrm{x}}_{\text{o}}$ is observed data
for the mask, and $\boldsymbol{\mathrm{x}}_{\setminus\text{o}}$ is unobserved
data. Note that we refer $\boldsymbol{\mathrm{x}}_{\text{m}}$ as missing data
of which observed components are filled with observed data and unobserved
components are filled with NaN, not a number to represent unobserved
components explicitly. This can be represented as below:

$\boldsymbol{\mathrm{x}}_{\text{m}}^{i}=\begin{cases}\boldsymbol{\mathrm{x}}^{i}&\quad\text{if
}\boldsymbol{\mathrm{m}}^{i}=1\\\ \text{NaN}&\quad\text{if
}\boldsymbol{\mathrm{m}}^{i}=0\end{cases},$ (2)

where $\boldsymbol{\mathrm{x}}^{i}_{\text{m}}$, $\boldsymbol{\mathrm{x}}^{i}$
and $\boldsymbol{\mathrm{m}}^{i}$ are $i$-th component of
$\boldsymbol{\mathrm{x}}_{\text{m}}$, $\boldsymbol{\mathrm{x}}$ and
$\boldsymbol{\mathrm{m}}$, respectively. It is true that this classification
of missingness is important for complete data generation and imputation. Thus,
we discuss the relationship between this classification and measurement policy
in Section 4.

###  2.2 Imputation

As if missingness is represented with mask, imputation can be represented with
masking function for missing data which replaces missing values with other
feasible values. Since missingness does not include corruption of observed
components by definition, most of the imputation methods preserve observed
components. It can be represented with a masking function $M$ and a
substitution $\boldsymbol{\mathrm{y}}$ as below:

$M(\boldsymbol{\mathrm{x}}_{\text{m}},\boldsymbol{\mathrm{m}},\boldsymbol{\mathrm{y}})^{i}=\begin{cases}\boldsymbol{\mathrm{x}}^{i}&\quad\text{if
}\boldsymbol{\mathrm{m}}^{i}=1\\\ \boldsymbol{\mathrm{y}}^{i}&\quad\text{if
}\boldsymbol{\mathrm{m}}^{i}=0\end{cases},$ (3)

where $M(\boldsymbol{\mathrm{x}}_{\text{m}},m,\boldsymbol{\mathrm{y}})^{i}$
and $\boldsymbol{\mathrm{y}}^{i}$ is $i$-th component of
$M(\boldsymbol{\mathrm{x}}_{\text{m}},m,\boldsymbol{\mathrm{y}})$ and
$\boldsymbol{\mathrm{y}}$, respectively. Note that this substitution step is
performed not only at the final stage of imputation but also at the other
steps or even initial step to for the very first computation. For example, to
process missing data with neural network, symbolic missing value should be
replaced with a numeric number. Generally, imputation methods are mainly about
how to find feasible substitution. One of the most significant way is to
regress the substitution from observed data (Gelman & Hill, 2006; Zhang,
2011). The regression using data statistics can be extended to learning
problem to extract high-level features from observed data. Especially, as
complete data is hard to be observed, unsupervised learning from missing
dataset is widely studied (Carreira-Perpin et al., 2011; Wei et al., 2018).
Recently, several unsupervised learning methods using deep neural network show
top results for high dimensional and highly missing dataset (Yoon et al.,
2018; Li et al., 2019). For those challenging dataset, the uncertainty of
missing values is too high to be represented with uni-modality. Instead,
multiple imputation method is utilized to represent and learn the uncertainty
(Buuren & Groothuis-Oudshoorn, 2010; Yoon & Sull, 2020).

###  2.3 Reinforcement learning

Fundamental model of reinforcement learning is modeled as Markov Decision
Process composed of agent and environment transmitting stochastic state,
action and reward (Sutton & Barto, 2018). At each iteration, agent takes
action by recognizing current state, and then state is updated from the
previous state and the action taken. Agent also receives reward to maximize
expected cumulative reward by changing its own policy. There are many
reinforcement learning algorithms based on Monte Carlo method, temporal
difference, Q-learning and policy gradient method. Among the policy gradient
methods, actor-critic method (Konda & Tsitsiklis, 2000; Mnih et al., 2016) is
widely used from simple scenarios to complicated ones. These days,
reinforcement learning works well for some challenging scenarios, in terms of
deep reinforcement learning (Silver et al., 2016; Brown et al., 2017; Levine
et al., 2016; Pan et al., 2017; Deng et al., 2016; François-Lavet et al.,
2018). Among them, the most similar method with our proposal is to decide
which image patch needs to be obtained with higher resolution (Uzkent & Ermon,
2020). However, all of the image patches are initially obtained with low
resolution and selected at once.

##  3 Problem Statement

In this section, we state our problem in detail. Generally speaking, we want
to formulate a learning problem to measure data well against missingness.
However, we focus on controllable missingness driven by measurement policy
rather than accidental missingness caused by measurement failure. From such
perspective, we define our learning problem including reasonable dataset
acquisition procedure.

First of all, we assume that our measurement system can measure sequentially.
At each measurement, measurement policy decides next measurement from already
observed data. For simplicity, measurement policy measures one variable per
decision and does not memory the history except previous one. Using the mask
representation for missingness, stochastic measurement policy can be
represented as below:

$\boldsymbol{\mathrm{m}}^{(t+1)}{\sim}P(\boldsymbol{\mathrm{m}}|\boldsymbol{\mathrm{m}}^{(t)},\boldsymbol{\mathrm{x}}_{\text{o}}^{(t)}),$
(4)

where $\boldsymbol{\mathrm{m}}^{(t)}$ and
$\boldsymbol{\mathrm{x}}_{\text{o}}^{(t)}$ are mask and observed data at
discrete time $t$, respectively. Also, the distribution $P$ has a constraint
that new decision do not overlap with past measurements. Thus, the sum of
probabilities of possible masks which overlap all of the past measurements is
one as following:

$\sum_{\boldsymbol{\mathrm{m}}{\in}S(\boldsymbol{\mathrm{m}^{(t)}})}P(\boldsymbol{\mathrm{m}}|\boldsymbol{\mathrm{m}}^{(t)},\boldsymbol{\mathrm{x}}_{\text{o}}^{(t)})=1.$
(5)

Also, to simplify the measurement limitation, we set a maximum length of
measurement sequence $T$. Otherwise, actual cost and interference can be
modeled.

$S(\boldsymbol{\mathrm{m}^{(t)}})=\\{\boldsymbol{\mathrm{m}}^{(t)}+\boldsymbol{\mathrm{m}}\mid\boldsymbol{\mathrm{m}}^{(t)}*\boldsymbol{\mathrm{m}}=\boldsymbol{0},||\boldsymbol{\mathrm{m}}||=1\\}$
(6)

Secondly, we need to define performance metric. While there might be specific
goal to be analyzed, retrieving complete data from missing data equivalent to
imputation can be general goal before specific analysis. Thus, our performance
metric is simply imputation performance and the resulting optimality is also
defined by imputation performance. However, our problem is not only to find
optimal measurement policy but also to find corresponding optimal imputation
method. Thus, joint learning problem for both measurement decision and
imputation method can be as follows:

$\operatorname*{argmax}_{p_{im},\pi}{\mathbb{E}_{\boldsymbol{\mathrm{x}}\sim{}p(\boldsymbol{\mathrm{x}})}[p_{\text{im}}(\boldsymbol{\mathrm{x}}|\boldsymbol{\mathrm{x}}_{o}^{\pi})]},$
(7)

where $\boldsymbol{\mathrm{x}}_{o}^{\pi}$ is the data observed by measurement
policy ${\pi}$, $p_{\text{im}}$ is distribution of imputation and $p$ is true
distribution of complete data. The two individual learning procedures are
quite different and there might be no guarantee that alternating the two
procedures can generally find global or even local optima. Especially,
reinforcement learning should involve exploration resulting in less feasible
measurement. Thus, we assume that imputer is well-trained initially by
uninformative measurement policy so that imputer can provide reliable reward
for exploration at learning measurement policy. Then, provided that
measurement policy can be learned monotonically and make missingness somehow
easier, imputation also could be learned stably without betraying the
measurement policy. In addition to these assumptions, our learning algorithm
considers to stabilize the learning in various ways in terms of data
generation and meta-learning structure.

On the other hand, since we assume that any complete data cannot be observed,
dataset for learning should be missing dataset or even highly missing dataset.
One of the most reasonable scenario is uniformly randomly missing dataset
which is equivalent to a scenario of uninformative measurement policy. If we
have no idea about measurement system, we can just try to measure uniformly
randomly selected variables. However, we cannot compute value function in Eq.
7 without complete dataset. Our proposed algorithm reduces the original
problem into another solvable problem using complete data generation.

##  4 Analysis

In this section, we discuss about specific characteristics of our problem.
Even though it is not theoretically proved, some of the intuitions can inform
how to solve problem and why it can be solved.

First, we can think about the existence of optimal measurement policy. The
fundamental reason why we can regress imputation is because each variables of
complete data are correlated. Then, which unobserved variable should be
measured for given observed data? It can be said that the most desired
unobserved variable should be correlated mostly with the other unobserved
variables which are less correlated with observed variables. However, how can
we know about the correlation between observed variables and unobserved ones.
A trivial way is to check global correlation between them. For example, in
MNIST, reliable guess would be on a pixel around center but in distance from
observed pixels. Nevertheless, we need to make more reliable guess for given
observed variables. If there exist multiple hypotheses on correlation for
given observed variables, we can measure a variable to test the hypothesis and
discard if it is unreliable. An explicit form of hypothesis on correlation can
be that on complete data. Thus, the most desired variable is the most
uncertain variable among various hypotheses on complete data from multiple
imputation. Therefore, at least, learning measurement policy should involve
implicit learning of hypotheses. Hopefully, measurement policy learned by
imputation can learn implicit hypotheses but more optimal ones to decide which
variable is important. An important type of implicit hypotheses of correlation
should come from imputation method itself. Since any imputation method could
be somehow overfitted, measurement decision rule can reduce generalization
error possibly caused by the particular imputation method.

On the other hand, imputation should be learned jointly with measurement
policy. It has two major reasons: The first one is to adapt to missingness
changed by learning measurement policy, and second one is to learn more from
potentially better missingness. Considering the adaptation, the dependency of
missingness upon the data changes through learning. Initially, the missing
data driven by uninformative measurement policy is MCAR. Then, after
missingness is controlled by observed data, it belongs to MAR case. While the
adaption is ambiguous for contribution at imputation, it is obvious that
better measurement policy make imputation better. Practically, most imputation
methods practically do better at easier missing data without additional
learning. Even though fixed imputation method cannot do better at easier
missingness, we can hopefully believe that a proper learning method can make
imputation better.

As we can expect the desired behaviors of proper learning algorithm and
optimal policy as above, it is different from implementability in the
perspective of function approximation. Initially, a function approximating
measurement should be nearly irrelevant with input, because it should
represent MCAR missingness. After learning, the function should be quite
sensitive to response for slowly changing input. Especially, the score for
previously selected component should extremely fall down, unless the score is
rejected in hard-coded way. Thus, function and input need to be designed
carefully rather than typical function approximation methods in machine
learning which desires robust and smooth function approximation.

##  5 Methods

In this section, we propose a joint learning algorithm for both measurement
policy and imputation. The intuition of the learning procedure is in Figure 2.
Also, it is based on deep learning including function approximation using
neural networks and stochastic gradient descent. First of all, we let the
state for measurement policy be re-defined missing data representation as
below:

$\boldsymbol{\mathrm{x}}_{\text{m}}^{(t)}=[\boldsymbol{\mathrm{x}}^{(t)}_{\text{o}},\boldsymbol{\mathrm{m}}^{(t)}],$
(8)

where $\boldsymbol{\mathrm{x}}_{\text{m}}^{(t)}$ is missing data at discrete
time $t$ re-defined as a pair of observed data and mask.

###  5.1 Initialization

As we assume that our dataset is uniform MCAR dataset driven by the
uninformative measurement policy, we need to initialize measurement policy
network to represent the distribution. While an initialized neural network
easily produces uniform distribution, it can hardly produce irrelevant output.
Thus, we use dropout layers (Hinton et al., 2012) to inject additional
randomness to neural network and learn dependency through training. Since the
initialized measurement policy network is not completely uniform MCAR, we need
to use a sampling technique for the uninformative measurement policy. Then,
imputation is pre-trained by sampled missing dataset to prevent the
measurement policy network from being confused by unreliable imputation.
Fortunately, we can train imputation with unsupervised manner using only
missing dataset (Yoon et al., 2018; Li et al., 2019; Yoon & Sull, 2020).

###  5.2 Data generation

Unfortunately, we cannot explore measurement policies even by clever
exploration method, because none of the measurement is included except the
observed one in a given missing dataset. Furthermore, our reinforcement
learning algorithm cannot compute the reward defined by actual imputation
performance without complete dataset. To tackle these impossibilities, we
propose a simple but efficient complete data generation method. The intuition
is that imputation belongs to conditional generation of complete data from
missing data. The only difference is whether each generation is constrained by
true distribution or other desired distributions. Thus, the complete data
generated by imputation is the most realistic one among data generation
methods. Additionally, using stochastic or multiple imputation, we can make
larger dataset. In such case, how to generate complete dataset optimally also
belongs to machine learning. An active learning method can possibly evaluate
imputation quality of each data. Without any active sampling , a complete data
$\bar{\boldsymbol{\mathrm{x}}}$ is generated as below:

$\bar{\boldsymbol{\mathrm{x}}}\sim{}p_{\text{im}}(\boldsymbol{\mathrm{x}}|\boldsymbol{\mathrm{X}}_{\text{m}};\phi),$
(9)

where $p_{\text{im}}$ is imputation distribution parameterized with $\phi$.

Then, the individual learning measurement policy and imputation can be
realized by the data generation method. Firstly, the reinforcement learning
algorithm can explore any policies on the generated complete data. Also, the
reward function can compute imputation error between imputation from the
measurement policy and its corresponding complete data. In entire episodes, it
would be sufficient to use only terminal reward as final imputation error
rather than immediate rewards from every single measurement. Thus, the
gradient driven by REINFORCE algorithm (Sutton & Barto, 2018) is as below:

$\nabla_{\theta}L(\boldsymbol{\mathrm{x}})={\mathbb{E}}[R^{(t)}\nabla_{\theta}\log\pi(\boldsymbol{\mathrm{m}}^{(t)}|\boldsymbol{\mathrm{x}}^{(t)}_{\text{m}};\theta)],$
(10)

where $R^{(t)}$ is the cumulative reward at time $t$ computed with the
generated complete data $\boldsymbol{\mathrm{x}}$. Also, since we assume that
one variable is observed at each time, the policy $\pi$ is defined as below:

$\pi(\boldsymbol{\mathrm{m}}|\boldsymbol{\mathrm{x}}^{(t)}_{\text{m}};\theta)=\text{Cat}\left[\frac{(\boldsymbol{1}-\boldsymbol{\mathrm{m}}^{(t)})e^{f(\boldsymbol{\mathrm{x}}^{(t)}_{\text{m}};\theta)}}{\sum(\boldsymbol{1}-\boldsymbol{\mathrm{m}}^{(t)})e^{f(\boldsymbol{\mathrm{x}}^{(t)}_{\text{m}};\theta)}}\right],$
(11)

where $\pi$ is a stochastic policy represented by a categorical distribution
and
$f(\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptscriptstyle\bullet$}}}}};\theta)$
is a policy network parameterized by $\theta$. Furthermore, for exploration,
we flatten the distribution slightly as below:

$\pi_{e}=(1-e)\pi+e(1-\pi),$ (12)

where $e\in[0,1]$ is a hyper-parameter to control the magnitude of
exploration. Note that the flattened distribution is invalid so as to be
normalized.

On the other hand, the learning method equivalent to that of initialization
using real missing dataset is available, a supervision using generated
complete data is also available. However, it is important to maintain
imputation performance on the real missing data, because it is used to
generate complete data affecting learning recursively. Thus, the gradients can
be written as:

$\nabla_{\phi}L_{\text{im}}^{u}(\boldsymbol{\mathrm{x}}_{\text{m}})\;\text{or}\;\nabla_{\phi}L_{\text{im}}^{s}(\boldsymbol{\mathrm{x}}_{\text{m}},\boldsymbol{\mathrm{x}}),$
(13)

where $L_{\text{im}}^{u}$ and $L_{\text{im}}^{s}$ are loss functions based on
unsupervised and supervised learning, respectively.

In the case of learning from the better measurement policy learned as above,
there are two possible approaches for adaptation or additional learning. The
first one is to use a new imputation method more appropriate to easier
missingness and transfer the knowledge from the original imputation method.
The second approach is to share identical imputation method for both data
generation and imputation to take the benefit of data augmentation.

Figure 2: Above learning procedures are scheduled for joint learning of
measurement policy and imputation. ’Learning 1’ is for data generation based
on the imputation and ’Learning 2’ is for adapting the imputation for the
measurement policy. ’Reinforcement learning 1’ receives the reward from
imputation and ’Reinforcement learning 2’ receives the reward from the adapted
imputation by ’Learning 2’.

###  5.3 Joint learning

There needs to be several techniques to make joint learning possible and
stable. Simply, we want to replace the joint learning with an alternate
learning algorithm in the sense of inner loop. In addition to computational
efficiency, hopefully, it can be better than the alternating individual
learning in the sense of outer loop. Firstly, the progressive measurement
which occurs due to exploration of reinforcement learning can perturb
imputation. Thus, imputation should adapt to the current stationary policy.
Also, we adopt an additional learning procedure similar to meta-learning. By
definition, a potentially better measurement policy should encourage
imputation to adapt in positive way. Thus, the reward function for measurement
policy should consider the imputation performance after adaption. To this end,
we add another reward which is imputation error after an update of imputation,
which is computationally reasonable for iteration. The progressive adaptation
resulted by exploring the influence onto adaptation is discarded and the
actual adaptation occurs after the update of the measurement policy. These
procedures are described in Algorithm 1.

Algorithm 1 Joint learning

0: measurement policy $\pi$, imputation $p_{\text{im}}$

Input: policy parameter $\theta$, imputation parameter $\phi$, missing dataset
$\boldsymbol{\mathrm{X}}_{\text{m}}$

hyperparameters: $\alpha$, $\alpha^{\prime}$, $\beta$, $\beta^{\prime}$, $e$

Initialize $\phi$

repeat

Sample batch of missing data $\boldsymbol{\mathrm{x}}_{\text{m}}$ from
$\boldsymbol{\mathrm{X}}_{\text{m}}$

$\phi\leftarrow\phi-\alpha\nabla_{\phi}L_{\text{im}}\left(\boldsymbol{\mathrm{x}}_{\text{m}};p_{\text{im}}\right)$

until $L_{\text{im}}\left(\boldsymbol{\mathrm{x}}_{\text{m}}\right)$ converges

Initialize $\theta$

repeat

Sample batch of imputation $\boldsymbol{\mathrm{\bar{x}}}$ from
$p_{\text{im}}\left(\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptscriptstyle\bullet$}}}}}\mid\boldsymbol{\mathrm{x}}_{\text{m}};\phi\right)$

Exploring policy
$\pi_{e}\left(\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptscriptstyle\bullet$}}}}};\theta\right)\leftarrow(1-e)\pi+e(1-\pi)$

Sample episode
$E_{1}=\\{{\boldsymbol{\mathrm{\bar{x}}}_{\text{m}}^{(t)}}\\}_{t=1}^{t=T}$
using
$\pi_{e}\left(\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptscriptstyle\bullet$}}}}};\theta\right)$

$\phi_{\text{new}}\leftarrow\phi-\alpha\nabla_{\phi}L_{\text{im}}\left(\boldsymbol{\mathrm{x}}_{\text{m}};p_{\text{im}}\right)-\alpha^{\prime}\nabla_{\phi}L^{\prime}_{\text{im}}(\boldsymbol{\mathrm{\bar{x}}}_{\text{m}}^{(T)};p_{\text{im}})$

Sample episode
$E_{2}=\\{\boldsymbol{\mathrm{\bar{x}}^{\prime}}_{\text{m}}^{(t)}\\}_{t=1}^{t=T}$
using
$\pi\left(\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptscriptstyle\bullet$}}}}};\theta\right)$

$\theta\leftarrow\theta-\beta\nabla_{\theta}L\left(\boldsymbol{\mathrm{\bar{x}}},E_{1},p_{\text{im}}\left(\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptscriptstyle\bullet$}}}}};\phi\right)\right)\newline
\hskip
25.6073pt-\beta^{\prime}\nabla_{\theta}L\left(\boldsymbol{\mathrm{\bar{x}}},E_{2},p_{\text{im}}\left(\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptscriptstyle\bullet$}}}}};\phi_{\text{new}}\right)\right)$

Sample episode
$E_{3}=\\{{\boldsymbol{\mathrm{\bar{x}}^{\prime\prime}}_{\text{m}}^{(t)}}\\}_{t=1}^{t=T}$
using
$\pi\left(\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.8}{$\scriptscriptstyle\bullet$}}}}};\theta\right)$

$\phi\leftarrow\phi-\alpha\nabla_{\phi}L_{\text{im}}\left(\boldsymbol{\mathrm{x}}_{\text{m}};p_{\text{im}}\right)-\alpha^{\prime}\nabla_{\phi}L^{\prime}_{\text{im}}(\boldsymbol{\mathrm{\bar{x}}^{\prime\prime}}_{\text{m}}^{(T)};p_{\text{im}})$

until convergence

##  6 Experiments

In this section, we evaluate our proposal in two different datasets: MNIST
dataset for complex scenario and sinusoidal dataset for simple scenario. We
demonstrate the implementation details, results with various missing rates and
ablation studies. More details such hyperparmeters are described in
Supplementary material.

###  6.1 MNIST dataset

We implement the measurement system and learning algorithm using MNIST dataset
(LeCun et al., 1998). For imputation, we use generative adversarial network
structure (Yoon & Sull, 2020) which can learn multiple imputation in
unsupervised manner. The structure consists of unconditional generator for
candidate substitution and conditional generator for imputation with
respective discriminators. However, for adaptation, we only trained the
generator for imputation and corresponding imputation, because the candidate
generation is based on MCAR assumption. For measurement policy, we used actor-
critic method for REINFORCE method (Sutton & Barto, 2018). The reward function
is defined as top-$k$ RMSE in (Yoon & Sull, 2020) as below:

$R_{k}=\min_{i<k}\left\|{\hat{\boldsymbol{\mathrm{x}}}_{i}-\boldsymbol{\mathrm{\bar{x}}}}\right\|_{2},$
(14)

where $\hat{\boldsymbol{\mathrm{x}}}_{i}$ is top-$i$ imputation and
$\boldsymbol{\mathrm{\bar{x}}}$ is generated complete data. Also, we utilize
top-3 RMSE using ground truth $\boldsymbol{\mathrm{x}}$ for evaluation metric.

We use 60,000 examples for training and 10,000 for test as provided in MNIST
dataset. For simplicity, we crop and resize the image into 12x12 resolution.
Also, we use fully connected network for every network including generators,
discriminators, actor and critic. In the supplementary material, we
demonstrate experimental results of original resolution 28x28.

Figure 3: MNIST dataset: Top-3 imputation errors of baseline methods and our
proposal trained on various missing rates.

Figure 4: Examples of MNIST dataset: The top two rows are from proposed method and the bottom two rows are from uninformative method Method |  80% |  85% |  90%
---|---|---|---
UnInform |  .239 (.260) |  .262 (.284) |  .275 (.302)
Explicit |  .186 (.199) |  .222 (.238) |  .247 (.265)
Proposed |  .171 (.185) |  .194 (.213) |  .232 (.251)
|  |  |
Table 1: MNIST dataset: Top-3 imputation errors of baseline method and our
proposal trained in various missing rate. Single imputation error is in
parenthesis.

Firstly, we evaluate for varying missing rate in Table 1. ’UnInform’ is
uninformative measurement policy and corresponding imputation method.
’Explicit’ is an explicit policy choosing the most uncertain variable from
multiple imputations at every measurement. ’Proposed’ is our measurement
policy jointly learned with imputation and deterministic policy is evaluated.
Table 1 shows imputation performance of each policies and corresponding
imputation. For each missing rate, imputations of baseline methods and initial
imputations of our learning algorithm are identically trained at the missing
rate and the measurement policy observes the same number with training data.
While explicit policy shows remarkable results compared to uninformative one,
our proposal shows better performance, as expected. Also, Figure 4 shows
examples visualizing each measurement policy and imputation result.
Furthermore, we tested each policy at various missing rates different with the
missing rate used in training, as shown in Figure 3. From the result,
generalization on less observation is more reliable than on more observation.
Note that the performance of explicit policy is the minimum of training
results at the three different missing rate.

Method |  75% |  80% |  85%* |  90% |  95%
---|---|---|---|---|---
w/o adaptation |  .161 (.175) |  .183 (.199) |  .203 (.222) |  .238 (.260) |  .272 (.299)
w/o meta |  .159 (.173) |  .177 (.192) |  .199 (.217) |  .228 (.250) |  .267 (.295)
Proposed |  .157 (.170) |  .177 (.193) |  .194 (.213) |  .225 (.247) |  .266 (.295)
|  |  |  |  |
Table 2: MNIST dataset: Top-3 imputation errors of three variations of our
learning algorithm. Single imputation error is in parenthesis. *All variations
are trained on 85% missing data.

Secondly, we investigate the results of three variations trained at 85%
missing rate of our learning algorithm, as shown in Table 2. The first one is
identical to ’Proposed’ in Table 1 and ’w/o meta’ excludes the reward from
adapted imputation ($\beta^{\prime}=0$ in Algorithm 1). In ’w/o adaptation’,
policy is individually learned without joint learning with imputation and
imputation is fine-tuned later. Note that it also excludes the reward from
adaptation like ’w/o meta.’ From the result, proposed learning algorithm seems
to behave as expected, but the effect on generalization to other missing rate
is relatively ambiguous.

###  6.2 Sinusoidal dataset

In order to investigate the performance for simpler dataset, we utilize 1D
sinusoidal function $y(x)=A\sin(wx+b)$ parameterized with amplitude $A$,
frequency $w$ and phase $b$. Like (Finn et al., 2017), those parameters are
sampled uniformly from the range $A\in[0.1,1]$, $b\in[0,2\pi]$ and
$w\in[0.5,2]$, respectively. Since the sinusoidal function can be determined
with a few observations, it can be said to have uni-modal uncertainty, so we
can learn the best single imputation. Thus, the imputation method consists of
linear interpolation and simple imputation network. Also, assuming that the
complete data is smooth, we adopt smoothness loss function using Gaussian
filtering. We sample one hundred variables in regular grid $[-5,5]$. Also,
training dataset has 2,880 examples and test dataset has 720 examples,
respectively.

Method |  Single 80% |  Single 90% |  Double 80% |  Double 90%
---|---|---|---|---
UnInform |  .036 |  .125 |  .113 |  .264
Proposed |  .026 |  .077 |  .096 |  .209
|  |  |  |
Table 3: Sinusoidal dataset: Single imputation errors for two types of dataset
and missing rate.

In Table 3, we represent the experimental results for several data
characteristics. We utilize stochastic policy for evaluation and the explicit
method based on multiple imputation in Table 1 is not possible. ’Single’ is
sampled from sinusoidal functions above and ’Double’ is sampled by
superposition of two different sinusoidal functions, respectively. As missing
rate increases, gain from learning measurement policy increases. Figure 5
shows each example of ’Single’ and ’Double’. Above all, we investigate that
our learning algorithm can be applied to simple dataset by learning implicit
characteristic other than explicit one.

Figure 5: Examples of sinusoidal dataset: The tops are ground truth, the
middles are from proposed method and the bottoms are from uninformative
method.

##  7 Conclusion

In conclusion, we propose a learning algorithm for both sparse measurement
policy and corresponding imputation method. Since we want joint learning due
to their mutual relationship, our learning algorithm alternately update them
considering clever exploration method. Also, complete data generation method
allows learning from only uncontrollable, uninformative missing data. We
showed the best results at both simple and complex dataset with various
missing rates.

Although we can investigate our algorithm empirically, we cannot derive
theoretical analysis except intuitive ones. Interestingly, there might be
meaningful properties or theoretical bounds for the applicability of our
algorithm. On the other hand, we can extend our learning algorithm for true
active learning or interactive learning, assuming that measurement for
learning also can be controlled. Practically, however, if measurement should
wait those learning procedure which would be not real-time, it also increases
another type of cost so that the measurement becomes expensive or even
impossible. Thus, more practical future work could be more data-specific or
task-specific applications using challenging data characteristics, in addition
to theoretical study.

## References

  * Barnard & Meng (1999) Barnard, J. and Meng, X.-L.  Applications of multiple imputation in medical studies: from aids to nhanes.  _Statistical methods in medical research_ , 8(1):17–36, 1999.
  * Brand (2002) Brand, M.  Incremental singular value decomposition of uncertain data with missing values.  In _European Conference on Computer Vision_ , pp. 707–720. Springer, 2002.
  * Brown et al. (2017) Brown, N., Sandholm, T., and Machine, S.  Libratus: The superhuman ai for no-limit poker.  In _IJCAI_ , pp. 5226–5228, 2017.
  * Burger et al. (2012) Burger, H. C., Schuler, C. J., and Harmeling, S.  Image denoising: Can plain neural networks compete with bm3d?  In _2012 IEEE conference on computer vision and pattern recognition_ , pp. 2392–2399. IEEE, 2012.
  * Buuren & Groothuis-Oudshoorn (2010) Buuren, S. v. and Groothuis-Oudshoorn, K.  mice: Multivariate imputation by chained equations in r.  _Journal of statistical software_ , pp. 1–68, 2010.
  * Carreira-Perpin et al. (2011) Carreira-Perpin, M. A., Lu, Z., et al.  Manifold learning and missing data recovery through unsupervised regression.  In _2011 IEEE 11th International Conference on Data Mining_ , pp. 1014–1019. IEEE, 2011.
  * Deng et al. (2016) Deng, Y., Bao, F., Kong, Y., Ren, Z., and Dai, Q.  Deep direct reinforcement learning for financial signal representation and trading.  _IEEE transactions on neural networks and learning systems_ , 28(3):653–664, 2016.
  * Donoho (1995) Donoho, D. L.  De-noising by soft-thresholding.  _IEEE transactions on information theory_ , 41(3):613–627, 1995.
  * Elad & Aharon (2006) Elad, M. and Aharon, M.  Image denoising via sparse and redundant representations over learned dictionaries.  _IEEE Transactions on Image processing_ , 15(12):3736–3745, 2006.
  * Finn et al. (2017) Finn, C., Abbeel, P., and Levine, S.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _International Conference on Machine Learning_ , pp. 1126–1135. PMLR, 2017.
  * François-Lavet et al. (2018) François-Lavet, V., Henderson, P., Islam, R., Bellemare, M. G., and Pineau, J.  An introduction to deep reinforcement learning.  _arXiv preprint arXiv:1811.12560_ , 2018.
  * Gelman & Hill (2006) Gelman, A. and Hill, J.  _Data analysis using regression and multilevel/hierarchical models_.  Cambridge university press, 2006.
  * Helstrom (1967) Helstrom, C. W.  Image restoration by the method of least squares.  _Josa_ , 57(3):297–303, 1967.
  * Hinton et al. (2012) Hinton, G. E., Srivastava, N., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R. R.  Improving neural networks by preventing co-adaptation of feature detectors.  _arXiv preprint arXiv:1207.0580_ , 2012.
  * Konda & Tsitsiklis (2000) Konda, V. R. and Tsitsiklis, J. N.  Actor-critic algorithms.  In _Advances in neural information processing systems_ , pp. 1008–1014, 2000.
  * Lakshminarayan et al. (1996) Lakshminarayan, K., Harp, S. A., Goldman, R. P., Samad, T., et al.  Imputation of missing data using machine learning techniques.  In _KDD_ , pp. 140–145, 1996.
  * Lakshminarayan et al. (1999) Lakshminarayan, K., Harp, S. A., and Samad, T.  Imputation of missing data in industrial databases.  _Applied intelligence_ , 11(3):259–275, 1999\.
  * LeCun et al. (1998) LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Lee et al. (2019) Lee, D.-H., Yang, J.-K., Lee, C.-H., and Kim, K.-J.  A data-driven approach to selection of critical process steps in the semiconductor manufacturing process considering missing and imbalanced data.  _Journal of Manufacturing Systems_ , 52:146–156, 2019.
  * Levine et al. (2016) Levine, S., Finn, C., Darrell, T., and Abbeel, P.  End-to-end training of deep visuomotor policies.  _The Journal of Machine Learning Research_ , 17(1):1334–1373, 2016.
  * Li et al. (2019) Li, S. C.-X., Jiang, B., and Marlin, B.  Misgan: Learning from incomplete data with generative adversarial networks.  _arXiv preprint arXiv:1902.09599_ , 2019.
  * Mackinnon (2010) Mackinnon, A.  The use and reporting of multiple imputation in medical research–a review.  _Journal of internal medicine_ , 268(6):586–593, 2010.
  * Mnih et al. (2016) Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K.  Asynchronous methods for deep reinforcement learning.  In _International conference on machine learning_ , pp. 1928–1937, 2016.
  * Nduhura-Munga et al. (2013) Nduhura-Munga, J., Rodriguez-Verjan, G., Dauzere-Peres, S., Yugma, C., Vialletelle, P., and Pinaton, J.  A literature review on sampling techniques in semiconductor manufacturing.  _IEEE Transactions on Semiconductor Manufacturing_ , 26(2):188–195, 2013.
  * Pan et al. (2017) Pan, X., You, Y., Wang, Z., and Lu, C.  Virtual to real reinforcement learning for autonomous driving.  _arXiv preprint arXiv:1704.03952_ , 2017.
  * Raja & Thangavel (2020) Raja, P. and Thangavel, K.  Missing value imputation using unsupervised machine learning techniques.  _Soft Computing_ , 24(6):4361–4392, 2020.
  * Rojas et al. (2017) Rojas, J. A. R., Kery, M. B., Rosenthal, S., and Dey, A.  Sampling techniques to improve big data exploration.  In _2017 IEEE 7th symposium on large data analysis and visualization (LDAV)_ , pp. 26–35. IEEE, 2017.
  * Settles (2009) Settles, B.  Active learning literature survey.  Technical report, University of Wisconsin-Madison Department of Computer Sciences, 2009.
  * Silver et al. (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Uzkent & Ermon (2020) Uzkent, B. and Ermon, S.  Learning when and where to zoom with deep reinforcement learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 12345–12354, 2020.
  * Wei et al. (2018) Wei, Y., Tang, Y., and McNicholas, P. D.  Flexible high-dimensional unsupervised learning with missing data.  _IEEE transactions on pattern analysis and machine intelligence_ , 42(3):610–621, 2018.
  * Yoon et al. (2018) Yoon, J., Jordon, J., and Van Der Schaar, M.  Gain: Missing data imputation using generative adversarial nets.  _arXiv preprint arXiv:1806.02920_ , 2018.
  * Yoon & Sull (2020) Yoon, S. and Sull, S.  Gamin: Generative adversarial multiple imputation network for highly missing data.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 8456–8464, 2020.
  * Yugma et al. (2015) Yugma, C., Blue, J., Dauzère-Pérès, S., and Obeid, A.  Integration of scheduling and advanced process control in semiconductor manufacturing: review and outlook.  _Journal of Scheduling_ , 18(2):195–205, 2015\.
  * Zhang et al. (2017) Zhang, K., Zuo, W., Chen, Y., Meng, D., and Zhang, L.  Beyond a gaussian denoiser: Residual learning of deep cnn for image denoising.  _IEEE transactions on image processing_ , 26(7):3142–3155, 2017.
  * Zhang (2011) Zhang, S.  Shell-neighbor method and its application in missing data imputation.  _Applied Intelligence_ , 35(1):123–133, 2011\.


Furthermore, after  proposition <ref>, $"\P_{\mathcal{ACD}(\R_B)}"$ uses the optimal number of priorities to recognize $"\L(\B)"$, and we directly obtain this information from the "alternating cycle decomposition" of $\R_\B$, $\ACD(\R_\B)$.

In the "example <ref>" we show a case in which $|\P_{\mathcal{ACD}(\R_B)}| < |\P_\B|$ and for which the gain in the number of priorities is clear.

In [6] and [26], the lower bounds for the determinisation of "Büchi automata" to Rabin and parity automata where shown using the family of  ""full Büchi automata"", $\{\B_n\}_{n\in \NN}$, $|\B_n|=n$. The automaton $\B_n$ can simulate any other Büchi automaton of the same size. For these automata, the constructions $\P_{\B_n}$ and $\P_{\mathcal{ACD}(\R_{B_n})}$ coincide.

We present a non-deterministic Büchi automaton $\B$ such that the "ACD-parity automaton" of $"\R_\B"$ has strictly less states and uses strictly less priorities than $"\P_\B"$.

In figure <ref> we show the automaton $\B$ over the alphabet $\Sigma=\{a,b,c\}$. Accepting transitions for the "Büchi condition" are represented with a black dot on them. An accessible "strongly connected component" $\R_\B'$ of the determinisation to a "Rabin automaton" $"\R_\B"$ is shown in figure <ref>. It has 2 states that are "history trees" (as defined in [23]). There is a "Rabin pair" $(E_\tt,F_\tt)$ for each node appearing in some "history tree" (four in total), and these are represented by an array with four positions. We assign to each transition and each position $\tt$ in the array the symbols $\textcolor{Green2}{\boldcheckmark}$, $\textcolor{Red2}{\mathbf{X}}$ ,  or $\textcolor{Orange2}{\bullet}$ depending on whether this transition belongs to $E_\tt$, $F_\tt$ or neither of them, respectively (we can always suppose $E_\tt\cap F_\tt = \emptyset$).

In figure <ref> there is the "alternating cycle decomposition" corresponding to $\R_\B'$. We observe that the tree of $\ACD(\R_\B')$ has a single branch of height $3$.
This is, the Rabin condition over $\R_\B'$ is already a "$[1,3]$-parity condition" and $\P_{\mathcal{ACD}(\R_B')}=\R_\B'$. In particular it has $2$ states, and uses priorities in $[1,3]$.

On the other hand, in figure <ref> we show the automaton $\P_\B'$, that has $3$ states and uses priorities in $[3,7]$. The whole automata $\R_\B$ and $\P_\B$ are too big to be pictured in these pages, but the three states shown in figure <ref> are indeed accessible from the initial state of $\P_\B$.

[square/.style=regular polygon,regular polygon sides=4, align=center,node distance=2cm,inner sep=2pt]

at (0,0) [state, initial] (0) $q_0$;
at (2,1) [state] (1) $q_1$;
at (2,-1) [state] (2) $q_2$;
at (4,0) [state] (3) $q_3$;

(0)  edge [out=115,in=65,loop] 	node[above]  a,b,c    (0)
(0)  edge []  node[above] a
node[scale=2] •   (1)
(0)  edge []  node[above] a,c   (2)

(1)  edge [out=105,in=55,loop, distance=10mm] 	node[left, pos=0.2]  a,b,c      (1)
(1)  edge [thick]  node[above]  b
node[scale=2] •  (3)

(2)  edge []  node[right,pos=0.4] c   (1)
(2)  edge [out=165,in=200,loop] node[left]  a 	node[scale=2] •   (2)
(2)  edge [thick,out=20,in=-20,loop] node[right]  b 	   (2)

(3)  edge [thick,out=115,in=65,loop] node[above]  a,b,c    (3);

Büchi automaton $\B$ over the alphabet $\Sigma=\{a,b,c\}$.

[square/.style=regular polygon,regular polygon sides=4, align=center,node distance=2cm,inner sep=3pt]

(STATE 1) at (0,0) [draw,circle]
[scale=0.7, every node/.style=scale=0.9]

at (0,2) [draw,ellipse,text width=1.4cm,minimum height=0.6cm] (aR) $\hspace{-2mm}q_0,q_1,q_2,q_3$;

at (-0.8,1) [draw, ellipse,text width=0.55cm,minimum height=0.6cm] (a0) $\hspace{-2mm}q_1,q_3$ ;
at (0.5,1) [draw, ellipse,minimum width=0.7cm,minimum height=0.6cm] (a1) $q_2$;

at (-0.8,0) [ellipse, draw,minimum width=0.7cm,minimum height=0.6cm] (a00) $q_3$;

(aR) edge (a0)
(aR) edge (a1)
(a0) edge (a00);

(STATE 2) at (6,0) [draw,circle]
[scale=0.7, every node/.style=scale=0.9]
at (5,2) [draw,ellipse,text width=1.4cm,minimum height=0.6cm] (bR) $\hspace{-2mm}q_0,q_1,q_2,q_3$;

at (5,1) [draw, ellipse,text width=0.55cm,minimum height=0.6cm] (b0) $\hspace{-2mm}q_1,q_3$ ;

at (5,0) [ellipse, draw,minimum width=0.7cm,minimum height=0.6cm] (b00) $q_3$;

(bR) edge (b0)
(b0) edge (b00);

at (0.5,-0.8) [scale=1.5, color=red] (state1) 1;
at (6.8,-0.8) [scale=1.5, color=red] (state2) 2;

(STATE 1) edge [out=145,in=170,loop, distance=1.5cm] node[above,pos=0.2]a  node[left,pos=0.3,scale=0.8]$\left(
\begin{array}{c}
\textcolor{Orange2}{\bullet} \\
\textcolor{Orange2}{\bullet} \\
\textcolor{Green2}{\boldcheckmark} \\
\textcolor{Orange2}{\bullet}
\end{array} \right) \hspace{2mm}$ (STATE 1)

(STATE 1) edge [out=190,in=215,loop, distance=1.5cm] node[below,pos=0.8]b node[left,pos=0.7,scale=0.8]$\left(
\begin{array}{c}
\textcolor{Orange2}{\bullet} \\
\textcolor{Orange2}{\bullet} \\
\textcolor{Orange2}{\bullet} \\
\textcolor{Orange2}{\bullet}
\end{array} \right) \hspace{2mm}$ (STATE 1)

(STATE 1) edge [out=30,in=150] node[above,pos=0.4]c node[above,pos=0.6,scale=0.8]$\left(
\begin{array}{c}
\textcolor{Orange2}{\bullet} \\
\textcolor{Orange2}{\bullet} \\
\textcolor{Red2}{\mathbf{X}} \\
\textcolor{Orange2}{\bullet}
\end{array} \right) $ (STATE 2)

(STATE 2) edge [out=35,in=10,loop, distance=1.5cm] node[above,pos=0.2]b node[right,pos=0.3,scale=0.8]$\hspace{2mm} \left(
\begin{array}{c}
\textcolor{Orange2}{\bullet} \\
\textcolor{Orange2}{\bullet} \\
\textcolor{Red2}{\mathbf{X}} \\
\textcolor{Orange2}{\bullet}
\end{array} \right) \hspace{2mm}$ (STATE 2)

(STATE 2) edge [out=-10,in=-35,loop , distance=1.5cm] node[below,pos=0.8]c node[right,pos=0.7,scale=0.8]$\hspace{2mm} \left(
\begin{array}{c}
\textcolor{Orange2}{\bullet} \\
\textcolor{Orange2}{\bullet} \\
\textcolor{Red2}{\mathbf{X}} \\
\textcolor{Orange2}{\bullet}
\end{array} \right) \hspace{2mm}$ (STATE 2)

(STATE 2) edge [out=210,in=-30, scale=0.6] node[above,pos=0.6]a node[above,pos=0.4,scale=0.8]$\left(
\begin{array}{c}
\textcolor{Orange2}{\bullet} \\
\textcolor{Orange2}{\bullet} \\
\textcolor{Orange2}{\bullet} \\
\textcolor{Orange2}{\bullet}
\end{array} \right) $ (STATE 1);

Component $\R_\B'$ of the automaton $\R_\B$. States are "history trees" and transitions are labelled with the input letter and an array representing the Rabin condition. There is one component in the arrays for each node appearing in some history tree, taking the order  17mm!$\left(
\begin{array}{c}
\text{Root} \; \varepsilon \\
\text{Node }0\\
\text{Node }1 \\
\text{Node }00
\end{array} \right)$.

The components of the arrays can host a green checkmark $\textcolor{Green2}{\boldcheckmark}$ (if the node is in $E_\tt$), a red cross $\textcolor{Red2}{\mathbf{X}}$ (if the node is in $F_\tt$) or an  orange dot $\textcolor{Orange2}{\bullet}$ (if the node is not in $E_\tt$ or $F_\tt$).

[square/.style=regular polygon,regular polygon sides=4, align=center,node distance=2cm,inner sep=3pt]

at (0,3) [draw, rectangle, text height=0.3cm, text width=3cm] (R)  $a_1,b_1,c_1,a_2,b_2,c_2$;

at (0,2) [draw, ellipse,text height=0.2cm, text width=0.8cm] (0) $a_1,b_1$;

at (0,1) [draw, rectangle, text height=0.3cm, text width=0.5cm] (1)  $b_1$;

(R) edge (0)
(0) edge (1);

at (2,3) $1$;
at (1.2,2) $2$;
at (1.2,1) $3$;

The "alternating cycle decomposition" of $\R_\B'$, $\ACD(\R_\B')$. The labels $a_1,b_1,c_1$ correspond to transitions leaving the state 1 on figure <ref> and $a_2,b_2,c_2$ those leaving state 2. We observe that this allows to substitute the "Rabin condition" on $\R_\B'$ for an equivalent $[1,3]$-parity condition on the same underlying automaton.

[square/.style=regular polygon,regular polygon sides=4, align=center,node distance=2cm,inner sep=3pt]

(STATE 1) at (0,0) [draw,circle]
[scale=0.7, every node/.style=scale=0.82]

at (0,2.2) [draw,ellipse,text width=1.4cm,text height=0.12cm] (aR) $\hspace{-2mm}q_0,q_1,q_2,q_3$
$\quad \,$ 0

at (-0.8,1) [draw, ellipse,text width=0.55cm,minimum height=0.6cm] (a0) $\hspace{-2mm}q_1,q_3$
at (0.5,1) [draw, ellipse,minimum width=0.7cm,minimum height=0.6cm] (a1) $q_2$

at (-0.8,-0.2) [ellipse, draw,minimum width=0.7cm,minimum height=0.6cm] (a00) $q_3$
(aR) edge (a0)
(aR) edge (a1)
(a0) edge (a00);

(STATE 2) at (4.6,0) [draw,circle]
[scale=0.7, every node/.style=scale=0.82]
at (4,2.2) [draw,ellipse,text width=1.4cm,minimum height=0.6cm] (bR) $\hspace{-2mm}q_0,q_1,q_2,q_3$
$\quad \,$ 0

at (4,1) [draw, ellipse,text width=0.55cm,minimum height=0.6cm] (b0) $\hspace{-2mm}q_1,q_3$
$\;$ 1

at (4,-0.2) [ellipse, draw,minimum width=0.7cm,minimum height=0.6cm] (b00) $q_3$

(bR) edge (b0)
(b0) edge (b00);

(STATE 3) at (9.4,0) [draw,circle]
[scale=0.7, every node/.style=scale=0.82]
at (8.5,2.2) [draw,ellipse,text width=1.4cm,minimum height=0.6cm] (cR) $\hspace{-2mm}q_0,q_1,q_2,q_3$
$\quad \,$ 0

at (7.7,1) [draw, ellipse,text width=0.55cm,minimum height=0.6cm] (c0) $\hspace{-2mm}q_1,q_3$
$\;$ 1
at (9,1) [draw, ellipse,minimum width=0.7cm,minimum height=0.6cm] (c1) $q_2$

at (7.7,-0.2) [ellipse, draw,minimum width=0.7cm,minimum height=0.6cm] (c00) $q_3$

(cR) edge (c0)
(cR) edge (c1)
(c0) edge (c00);

(STATE 1) edge [out=145,in=170,loop, distance=1.5cm] node[above,pos=0.2]a : $4$  (STATE 1)

(STATE 1) edge [out=190,in=215,loop, distance=1.5cm] node[above,pos=0.2]b : $7 \;\quad$ (STATE 1)

(STATE 1) edge [] node[above,pos=0.4]c : $3$ (STATE 2)

(STATE 2) edge [out=105,in=75,loop, distance=1.5cm] node[above,pos=0.5]b,c : $5$ (STATE 2)

(STATE 2) edge [out=30,in=150] node[above,pos=0.5]a : $7$ (STATE 3)

(STATE 3) edge [out=210,in=-30, scale=0.6] node[below,pos=0.5]c : $5$  (STATE 2)

(STATE 3) edge [out=35,in=10,loop, distance=1.5cm] node[above,pos=0.2]a : $6$ (STATE 3)

(STATE 3) edge [out=-10,in=-35,loop, distance=1.5cm] node[above,pos=0.2]$\quad$ b : $7$ (STATE 3);

Component $\P_\B'$ of the automaton $\P_\B$. States are ordered "history trees", with the order labels in violet. It has three different states, since two different orders for the same "history tree" occur.

§.§ On relabelling of transition systems by acceptance conditions

In this section we use the information given by the "alternating cycle decomposition" to provide characterisations of "transition systems" that can be labelled with "parity", "Rabin", "Streett" or $"\mathit{Weak}_k"$ conditions, generalising the results of [28].
As a consequence, these yield simple proofs of two results about the possibility to define different classes of acceptance conditions in a deterministic automaton. Theorem <ref>, first proven in [3], asserts that if we can define a Rabin and a Streett condition on top of an underlying automaton $\A$ such that it recognizes the same language $L$ with both conditions, then we can define a parity condition in $\A$ recognizing $L$ too. Theorem <ref> states that if we can define Büchi and co-Büchi conditions on top of an automaton $\A$ recognizing the language $L$, then we can define a $"\mathit{Weak}"$ condition over $\A$ such that it recognizes $L$.

First, we extend the definition <ref> of section <ref> to the "alternating cycle decomposition".

Given a Muller transition system $\T=(V,E,\msource,\mtarget,I_0,\F)$, we say that its "alternating cycle decomposition" $\ACD(\T)$ is a

* ""Rabin ACD"" if for every state $q\in V$, the tree $"t_q"$ has "Rabin shape".

* ""Streett ACD"" if for every state $q\in V$, the tree $"t_q"$ has "Streett shape".

* ""parity ACD"" if for every state $q\in V$, the tree $"t_q"$ has "parity shape".

* ""$[1,\eta]$-parity ACD"" (resp. $[0,\eta-1]$-parity ACD) if it is a parity ACD, every tree has "height" at most $\eta$ and trees of height $\eta$ are (ACD)odd (resp. (ACD)even).

* ""Büchi ACD"" if it is a $[0,1]$-parity ACD.
* ""co-Büchi ACD"" if it is a $[1,2]$-parity ACD.

* ""$\mathit{Weak}_k$ ACD"" if it is a parity ACD and every tree $(t_i,\nu_i) \in \ACD(\T)$ has "height" at most $k$.

The next proposition follows directly from the definitions.

Let $\T$ be a Muller transition system. Then:

* $\ACD(\T)$ is a "parity ACD" if and only if it is a "Rabin ACD" and a "Streett ACD".

* $\ACD(\T)$ is a "$\mathit{Weak}_k$ ACD" if and only if it is a "$[0,k]$-parity ACD" and a "$[1,k+1]$-parity ACD".

Let $\T=(V,E,\msource,\mtarget,I_0,\F)$ be a Muller transition system. The following conditions are equivalent:

* We can define a "Rabin condition"
over $\T$ that is "equivalent to" $\F$ over $\T$.

* For every pair of loops $l_1,l_2\in \mloop(\T)$, if $l_1\notin \F $ and $l_2\notin \F$, then $l_1\cup l_2 \notin \F$.

* $\ACD(\T)$ is a "Rabin ACD".

($1 \Rightarrow 2$)
Suppose that $\T$ uses a Rabin condition with Rabin pairs $(E_1,F_1),\dots,(E_r,F_r)$. Let $l_1$ and $l_2$ be two rejecting loops. If $l_1\cup l_2$ was accepting, then there would be some Rabin pair $(E_j,F_j)$ and some edge $e\in l_1\cup l_2$ such that $e\in E_j$ and $e\notin F_j$. However, the edge $e$ belongs to $l_1$ or to $l_2$, and the loop it belongs to should be accepting too.

($2 \Rightarrow 3$) Let $q\in V$ of "index" $i$, and $"t_q"$ be the subtree of $\ACD(\T)$ associated to $q$. Suppose that there is a node $\tt \in t_q$ such that $\kl(node){p_i}(\tt)$ is even ("round" node) and that it has two different children $\ss_1$ and $\ss_2$. The "loops" $\nu_i(\ss_1)$ and $\nu_i(\ss_2)$ are maximal rejecting loops contained in $\nu_i(\tt)$, and since they share the state $q$, their union is also a loop that must verify $ \nu_i(\ss_1) \cup \nu_i(\ss_2)\in \F$, contradicting the hypothesis.

($3 \Rightarrow 1$) We define a "Rabin condition" over $\T$. For each tree $t_i$ in $\ACD(\T)$ and each "round" node $\tt\in t_i$ ($\kl(node){p_i}(\tt)$ even) we define the Rabin pair $(E_{i,\tt},F_{i,\tt})$ given by:

\[ E_{i,\tt}=\nu_i(\tt)\setminus \bigcup_{\ss \in "\mathit{Children}"(\tau)}\nu_i(\ss) \quad, \qquad  F_{i,\tt}=E \setminus \nu_i(\tt). \]

Let us show that this condition is "equivalent to" $\F$ over the transition system $\T$. We begin by proving the following consequence of being a "Rabin ACD":

If $\tt$ is a "round" node in the tree $t_i$ of $\ACD(\T)$, and $l\in \mloop(\T)$ is a "loop" such that $l\subseteq \nu_i(\tt)$ and $l\nsubseteq \nu_i(\ss)$ for any child $\ss$ of $\tt$, then there is some edge $e\in l$ such that $e\notin \nu_i(\ss)$ for any child $\ss$ of $\tt$.

Since for each state $q\in V$ the tree $"t_q"$ has "Rabin shape", it is verified that $\mstate_i(\ss)\cap \mstate_i(\ss')=\emptyset$ for every pair of different children $\ss, \ss'$ of $\tt$. Therefore, the union of $\nu_i(\ss)$ and $\nu_i(\ss')$ is not a loop, and any loop $l$ contained in this union must be contained either in $\nu_i(\ss)$ or in $\nu_i(\ss')$.

Let $\rr\in \mrun_{T}$ be a "run" in $\T$, let $l\in \mloop(\T)$ be the loop of $\T$ such that $\minf(\rr)=l$ and let $i$ be the "index" of the edges in this loop. Let $\tt$ be a maximal node in $t_i$ (for $\prefix$) such that $l\subseteq \nu_i(\tt)$. If $l\in \F$, let $\tt$ be a maximal node in $t_i$ (for $\prefix$) such that $l\subseteq \nu_i(\tt)$. This node $\tt$ is a round node, and from the previous claim it follows that there is some edge $e\in l$ such that $e$ does not belong to any child of $\tt$, so $e\in E_{i,\tt}$ and $e\notin F_{i,\tt}$, so the "run" $\rr$ is accepted by the Rabin condition too. If $l\notin \F$, then for every round node $\tt$, if $l\subseteq \nu_i(\tt)$ then $l\subseteq \nu_i(\ss)$ for some child $\ss$ of $\tt$. Therefore, for every Rabin pair $(E_{i,\tt},F_{i,\tt})$ and every $e\in l$, it is verified $e\in E_{i,\tt} \, \Rightarrow \, e\in F_{i,\tt}$.

The Rabin condition presented in this proof does not necessarily use the optimal number of Rabin pairs required to define a Rabin condition "equivalent to" $\F$ over $\T$.

Let $\T=(V,E,\msource,\mtarget,I_0,\F)$ be a Muller transition system. The following conditions are equivalent:

* We can define a "Streett condition"
over $\T$ that is "equivalent to" $\F$ over $\T$.

* For every pair of loops $l_1,l_2\in \mloop(\T)$, if $l_1\in \F $ and $l_2\in \F$, then $l_1\cup l_2 \in \F$.

* $\ACD(\T)$ is a "Streett ACD".

We omit the proof of proposition <ref>, being the dual case of proposition <ref>.

Let $\T=(V,E,\msource,\mtarget,I_0,\F)$ be a Muller transition system. The following conditions are equivalent:

* We can define a "parity condition"
over $\T$ that is "equivalent to" $\F$ over $\T$.

* For every pair of loops $l_1,l_2\in \mloop(\T)$, if $l_1\in \F \, \Leftrightarrow \, l_2\in \F$, then $l_1\cup l_2 \in \F \, \Leftrightarrow \,l_1\in \F$. That is, union of loops having the same “accepting status” preserves their “accepting status”.

* $\ACD(\T)$ is a "parity ACD".

Moreover, the parity condition we can define over $\T$ is a "$[1,\eta]$-parity" (resp. $[0,\eta-1]$-parity / $"\mathit{Weak}_k"$) condition if and only if $\ACD(\T)$ is a "$[1,\eta]$-parity ACD" (resp. $[0,\eta-1]$-parity ACD / "$\mathit{Weak}_k$ ACD").

($1 \Rightarrow 2$) Suppose that $\T$ uses a parity acceptance condition with the priorities given by $p:E \rightarrow \NN$. Then, since $l_1$ and $l_2$ are both accepting or both rejecting,  $p_1=\min p(l_1)$ and $p_2=\min p(l_2)$ have the same parity, that is also the same parity than $\min p(l_1 \cup l_2)=\min\{p_1,p_2\}$.

($2 \Rightarrow 3$) Let $q\in V$ of "index" $i$, and $"t_q"$ be the subtree of $\ACD(\T)$ associated to $q$. Suppose that there is a node $\tt \in t_q$ with two different children $\ss_1$ and $\ss_2$. The loops $\nu_i(\ss_1)$ and $\nu_i(\ss_2)$ are different maximal loops with the property $\nu_i(\ss)\subseteq \nu_i(\tt)$ and $\nu_i(\ss)\in \F \, \Leftrightarrow \, \nu_i(\tt) \notin \F$. Since they share the state $q$, their union is also a loop contained in $\nu_i(\tt)$ and then

\[ \nu_i(\ss_1) \cup \nu_i(\ss_2)\in \F \; \Leftrightarrow \; \nu_i(\tt) \in \F \; \Leftrightarrow \; \nu_i(\ss_1)\notin \F\]

contradicting the hypothesis.

($3 \Rightarrow 1$) From the construction of the "ACD-transformation", it follows that $"\P_{\mathcal {ACD}(\T )}"$ is just a relabelling of $\T$ with an equivalent parity condition.

For the implication from right to left of the last statement, we remark that if the trees of $\ACD(\T)$ have priorities assigned in $[\mu,\eta]$, then the parity transition system $"\P_{\mathcal {ACD}(\T )}"$ will use priorities in $[\mu,\eta]$. If $\ACD(\T)$ is a "$\mathit{Weak}_k$ ACD", then in each "strongly connected component" of $"\P_{\mathcal {ACD}(\T )}"$ the number of priorities used will be the same as the "height" of the corresponding tree of $\ACD(\T)$ (at most $k$).

For the other implication it suffices to remark that the priorities assigned by $\ACD(\T)$ are optimal (proposition <ref>).

Given a "transition system graph" $\T_G=(V,E,\msource,\mtarget,I_0)$ and a "Muller condition" $\F \subseteq \P(E)$, we can define a "parity condition" $p:E\rightarrow \NN$ "equivalent to" $\F$ over $\T_G$ if and only if we can define a "Rabin condition" $R$ and a "Streett condition" $S$ over $\T_G$ such that
$ (\T_G,\F) \,"\simeq"\, (\T_G,R)\, "\simeq"\, (\T_G,S) $.

Moreover, if the Rabin condition $R$ uses $r$ Rabin pairs and the Streett condition $S$ uses $s$ Streett pairs, we can take the parity condition $p$ using priorities in

* $[1,2r+1]$ if $r\leq s$.

* $[0,2s]$ if $s\leq r$.

The first statement is a consequence of the characterisations (2) or (3) from propositions <ref>, <ref> and <ref>.

For the second statement we remark that the trees of $\ACD(\T)$ have "height" at most $\min\{2r+1, 2s+1\}$. If $r\geq s$, then the height $2r+1$ can only be reached by (ACD)odd trees, and if $s\geq r$, the height $2s+1$ only by (ACD)even trees.

From the last statement of proposition <ref> and thanks to the second item of proposition <ref>, we obtain:

Given a "transition system graph" $\T_G$ and a Muller condition $\F$ over $\T_G$, there is an equivalent $"\mathit{Weak}_k"$ condition over $\T_G$ if and only if there are both $[0,k]$ and "$[1,k+1]$-parity" conditions "equivalent to" $\F$ over $\T_G$.

In particular, there is an equivalent "Weak condition" if and only if there are "Büchi" and "co-Büchi" conditions equivalent to $\F$ over $\T_G$.

It is important to notice that the previous results are stated for non-labelled transition systems. We must be careful when translating these results to automata and formal languages. For instance, in <cit.> there is an example of a non-deterministic automaton $\A$, such that we can put on top of it Rabin and Streett conditions $R$ and $S$ such that $\L(\A,R)=\L(\A,S)$, but we cannot put a parity condition on top of it recognising the same language. However, proposition <ref> allows us to obtain analogous results for "deterministic automata".

Let $\A$ be the "transition system graph" of a "deterministic automaton" with set of states $Q$. Let $R$ be a Rabin condition over $\A$ with $r$ pairs and $S$ a Streett condition over $\A$ with $s$ pairs such that $\L(\A,R)=\L(\A,S)$. Then, there exists a parity condition $p: Q \times \Sigma \rightarrow \NN$ over $\A$ such that $\L(\A,p)=\L(\A,R)=\L(\A,S)$.

* if $r\leq s$, we can take $p$ to be a "$[1,2r+1]$-parity condition".

* if $s\leq r$, we can take $p$ to be a "$[0,2s]$-parity condition".

Proposition <ref> implies that $(\A,R)"\simeq"(\A,S)$, and after corollary <ref>, there is a parity condition $p$ using the proclaimed priorities such that $(\A,p)"\simeq"(\A,R)$. Therefore $\L(\A,p)"\simeq"\L(\A,R)$ (since for both deterministic and non-deterministic $(\A,p)"\simeq"(\A,R)$ implies $\L(\A,p)"\simeq"\L(\A,R)$).

Let $\A$ be the "transition system graph" of a deterministic automaton and $p$ and $p'$ be $[0,k]$ and "$[1,k+1]$-parity conditions" respectively over $\A$ such that $\L(\A,p)= \L(\A,p')$. Then, there exists a $"\mathit{Weak}_k"$ condition $W$ over $\A$ such that $\L(\A,W)=\L(\A,p)$.

In particular, there is a $"\mathit{Weak}"$ condition $W$ over $\A$ such that $\L(\A,W)=L$ if and only if there are both "Büchi" and "co-Büchi" conditions $B,B'$ over $\A$ such that $\L(\A,B)= \L(\A,B')=L$.

If follows from proposition <ref> and corollary <ref>.

§ CONCLUSIONS

We have presented a transformation that, given a Muller "transition system", provides an equivalent "parity" transition system that has minimal size and uses an optimal number of priorities among those which accept a "locally bijective morphism" to the original Muller transition system. In order to describe this transformation we have introduced the "alternating cycle decomposition", a data structure that arranges all the information about the acceptance condition of the transition system and the interplay between this condition and the structure of the system.

We have shown in section <ref> how the alternating cycle decomposition can be useful to reason about acceptance conditions, and we hope that this representation of the information will be helpful in future works.

We have not discussed the complexity of effectively computing the "alternating cycle decomposition" of a Muller transition system. It is known that solving Muller games is $\mathrm{PSPACE}$-complete when the acceptance condition is given as a list of accepting sets of colours
[13]. However, given a Muller game $\G$ and the "Zielonka tree" of its Muller condition, we have a transformation into a parity game of polynomial size on the size of $\G$, so solving Muller games with this extra information is in $\mathrm{NP}\cap \mathrm{co}$-$\mathrm{NP}$. Also, in order to build $\ACD(\T)$ we suppose that the Muller condition is expressed using as colours the set of edges of the game (that is, as an explicit Muller condition), and solving explicit Muller games is in $\mathrm{PTIME}$ [11]. Consequently, unless $\mathrm{PSPACE}$ is contained in $\mathrm{NP}\cap \mathrm{co}$-$\mathrm{NP}$, we cannot compute the "Zielonka tree" of a Muller condition, nor the "alternating cycle decomposition" of a Muller transition system in polynomial time.

[1]
J. Richard Büchi.
On a decision method in restricted second order arithmetic.
Proc. Internat. Congr. on Logic, Methodology and Philosophy of
Science, 1960.

[2]
Udi Boker, Denis Kuperberg, Orna Kupferman, and Michał Skrzypczak.
Nondeterminism in the presence of a diverse or unknown future.
In ICALP, 2013.

[3]
Udi Boker, Orna Kupferman, and Avital Steinitz.
Parityizing Rabin and Streett.
In FSTTCS, 2010.

[4]
Olivier Carton and Max Michel.
Unambiguous büchi automata.
Theoretical Computer Science, 297(1):37 – 81, 2003.

[5]
Thomas Colcombet.
The theory of stabilisation monoids and regular cost functions.
In ICALP, 2009.

[6]
Thomas Colcombet and Konrad Zdanowski.
A tight lower bound for determinization of transition labeled
Büchi automata.
In ICALP, 2009.

[7]
Jean-Michel Couvreur, Nasser Saheb, and Grégoire Sutre.
An optimal automata approach to LTL model checking of probabilistic
In LPAR, 2003.

[8]
Stefan Dziembowski, Marcin Jurdziński, and Igor Walukiewicz.
How much memory is needed to win infinite games?
In LICS, 1997.

[9]
Yuri Gurevich and Leo Harrington.
Trees, automata, and games.
In STOC, 1982.

[10]
Thomas Henzinger and Nir Piterman.
Solving games without determinization.
In CSL, 2006.

[11]
Florian Horn.
Explicit Muller games are PTIME.
In FSTTCS, 2008.

[12]
Florian Horn.
Random games. PhD Thesis, 2008.

[13]
Paul Hunter and Anuj Dawar.
Complexity bounds for regular games.
In MFCS, 2005.

[14]
Jan Křetínský, Tobias Meggendorfer, Clara Waldmann, and
Maximilian Weininger.
Index appearance record for transforming Rabin automata into parity
In TACAS, 2017.

[15]
Denis Kuperberg and Michał Skrzypczak.
On determinisation of good-for-games automata.
In ICALP, 2015.

[16]
Christof Löding.
Optimal bounds for transformations of $\omega$-automata.
In FSTTCS, 1999.

[17]
Robert McNaughton.
Testing and generating infinite sequences by a finite automaton.
Information and control, 9:521–530, 1966.

[18]
Andrzej W. Mostowski.
Regular expressions for infinite trees and a standard form of
In SCT, 1984.

[19]
David E. Muller.
Infinite sequences and finite machines.
In Symposium on Switching Circuit Theory and Logical Design,

[20]
Damian Niwiński and Igor Walukiewicz.
Relating hierarchies of word and tree automata.
In STACS, 1998.

[21]
Nir Piterman.
From nondeterministic Büchi and Streett automata to
deterministic parity automata.
In LICS, 2006.

[22]
Schmuel Safra.
On the complexity of $\omega$-automata.
In FOCS, 1988.

[23]
Sven Schewe.
Tighter bounds for the determinisation of Büchi automata.
In Foundations of Software Science and Computational
Structures, pages 167–181, 2009.

[24]
Sven Schewe and Thomas Varghese.
Tight bounds for the determinisation and complementation of
generalised Büchi automata.
In ATVA, 2012.

[25]
Sven Schewe and Thomas Varghese.
Determinising parity automata.
In MFCS, 2014.

[26]
Thomas Varghese.
Parity and generalised Büchi automata. Determinisation and
complementation. PhD Thesis, 2014.

[27]
Klaus Wagner.
On $\omega$-regular sets.
Information and control, 43(2):123–177, 1979.

[28]
Wiesław Zielonka.
Infinite games on finitely coloured graphs with applications to
automata on infinite trees.
Theoretical Computer Science, 200(1-2):135–183, 1998.