11institutetext:  Instituto Federal de Educação, Ciência e Tecnologia do Ceará
(IFCE), Brazil 11email<EMAIL_ADDRESS>
11email<EMAIL_ADDRESS>
# Logic-based Explanations for Linear Support Vector Classifiers with Reject
Option

Francisco Mateus Rocha Filho  0009-0002-2261-3767 Thiago Alves Rocha
0000-0001-7037-9683 Reginaldo Pereira Fernandes Ribeiro  0009-0000-0250-5713
Ajalmar Rêgo da Rocha Neto  0000-0002-4512-5531

###### Abstract

Support Vector Classifier (SVC) is a well-known Machine Learning (ML) model
for linear classification problems. It can be used in conjunction with a
reject option strategy to reject instances that are hard to correctly classify
and delegate them to a specialist. This further increases the confidence of
the model. Given this, obtaining an explanation of the cause of rejection is
important to not blindly trust the obtained results. While most of the related
work has developed means to give such explanations for machine learning
models, to the best of our knowledge none have done so for when reject option
is present. We propose a logic-based approach with formal guarantees on the
correctness and minimality of explanations for linear SVCs with reject option.
We evaluate our approach by comparing it to Anchors, which is a heuristic
algorithm for generating explanations. Obtained results show that our proposed
method gives shorter explanations with reduced time cost.

###### Keywords:

Logic-based explainable AI Support vector machines Classification with reject
option.

##  1 Introduction

††footnotetext: This preprint has not undergone peer review or any post-
submission improvements or corrections. The Version of Record of this
contribution is published in Intelligent Systems, LNCS, vol 14195, and is
available online at https://doi.org/10.1007/978-3-031-45368-7 10.

It is undeniable that Artificial Intelligence is increasingly being inserted
into the daily lives of people [17], influencing the most complex decision
taking tasks [25]. Consequently, the most varied classification models in
machine learning may come across instances that are difficult to correctly
classify, be it due to lack of good data, to feature bias (color, size,
gender) [8] or to noise present on the given patterns [25].

The SVC is one of the most well-known ML models. The linear Support Vector
Machine (SVM), specifically, has been used in a variety of classification
problems [3, 23, 26]. However, the model can also fall into the same
previously said pitfalls, failing to give a correct classification. As such,
the reject option strategy depicted in [4] can be used to remedy such cases.
Classification with reject option (RO) is a paradigm that aims to improve
reliability in decision support systems by rejecting the classification
results of more complex cases and avoiding a higher error rate. These cases
are separated to be dealt with in another specialized way, be it through other
models or with the assistance of a human specialist [20]. Since classification
with reject option comprises a set of techniques, in this work we consider the
strategy where the classifier is trained as usual and the rejected cases are
determined after the training phase. Usually, this process requires finding a
trade-off between the costs of misclassifications and rejections.

The linear SVC can already be globally interpreted to a certain extent based
on the decision function, where the most important features are often
associated with the highest weights [7]. Such analysis, however, is not
capable of giving decisive answers on more specific cases [14]. An example of
this is depicted and more thoroughly explored in Section 3. This gives a
margin for questionable explanations, especially for when reject option is
present due to the added level of complexity. Therefore the need for a more
thorough, instance-based explanation method.

Then, in this work, we consider instance-based explanations. Specifically, the
objective of instance-based explanations is to provide interpretable insights
by highlighting relevant features that influenced the output of an ML model on
a given instance. By linking the output to specific instances and their
features, users can gain a better understanding of the reasons behind the
predictions of ML models.

The popularization of concepts of Explainable Artificial Intelligence (XAI)
increased efforts to explain most complex models [12]. These have mostly been
done through heuristic methods, the more prevalent approach, such as LIME
[22], SHAP [18], and Anchors [21]. These tend to be model-agnostic and not
able to guarantee a trustworthy explanation with regard to the characteristics
of the model or the correctness of the answers [11]. Then, their explanations
can be often proven wrong through counterexamples that expose their
contradictions [11, 12], leading to even more doubts regarding how much the ML
model can be trusted.

Thus, the importance of trustworthy ML models increases the need for logic-
based approaches to explain the decisions made by these models [10, 12]. The
computation of explanations in these approaches rigorously explores the entire
feature space. Due to this, such explanations are provably correct and hold
for any point in the space, which therefore makes them trustworthy [8].
Moreover, logic-based approaches can guarantee minimality of explanations.
Minimality is important since succinct explanations seem easier to be
interpreted by humans. Recent years have seen a surge in research dedicated to
investigating logic-based XAI for ML models, such as neural networks, naive
Bayes, random forests, decision trees, and boosted trees [1, 9, 10, 13, 16,
19].

Due to the importance of reject option and logic-based explainability for
trustworthy ML models, this work proposes a logic-based approach to explain
linear SVCs with reject option. Given that rejected instances may be further
analyzed by specialists, explanations regarding the causes of rejections can
reduce the workload of these professionals. Our proposal builds on work from
the literature of logic-based explainability for traditional ML models, i.e.
without reject option [10, 11]. We compute explanations for linear SVCs with
reject option by solving a set of logical constraints, specifically, boolean
combinations of linear constraints. Despite the fact that we consider a linear
SVC with reject option in this work, our approach can be easily adapted for
other ML models with reject option, such as neural networks.

We conducted experiments to compare our approach against Anchors, a heuristic
method that generates explanations by locally exploring the feature subspace
close to a given instance [21], through six different datasets. The results
show that our approach is capable to generate succinct explanations up to 286
times faster than Anchors, in scenarios with and without the presence of
reject option.

##  2 Background

###  2.1 Machine Learning and Binary Classification Problems

In machine learning, binary classification problems are defined over a set of
features $\mathcal{F}=\\{f_{1},...,f_{n}\\}$ and a set of two classes
$\mathcal{K}=\\{-1,+1\\}$. In this paper, we consider that each feature
$f_{i}\in\mathcal{F}$ takes its values $x_{i}$ from the domain of real
numbers. Moreover, each feature $f_{i}$ has an upper bound $u_{i}$ and a lower
bound $l_{i}$ such that $l_{i}\leq x_{i}\leq u_{i}$. Then, each feature
$f_{i}$ has domain $[l_{i},u_{i}]$. Besides, the notation
$\mathbf{x}=\\{f_{1}=x_{1},f_{2}=x_{2},...,f_{n}=x_{n}\\}$ represents a
specific point or instance such that each $x_{i}$ is in the domain of $f_{i}$.

A binary classifier $C$ is a function that maps elements in the feature space
into the set of classes $\mathcal{K}$. For example, $C$ can map instance
$\\{f_{1}=x_{1},f_{2}=x_{2},...,f_{n}=x_{n}\\}$ to class $+1$. Usually, the
classifier is obtained by a training process given as input a training set
$\\{\mathbf{x}_{i},y_{i}\\}^{l}_{i=1}$, where $\mathbf{x}_{i}\in{\rm
I\\!R}^{n}$ is an input vector or pattern and $y_{i}\in\\{-1,+1\\}$ is the
respective class label. Then, for each input vector $\mathbf{x}_{i}$, its
input values $x_{i,1}$, $x_{i,2}$, …, $x_{i,n}$ are in the domain of
corresponding features $f_{1}$, …, $f_{n}$. A well-known classifier and its
training process are presented in Subsection 2.2.

###  2.2 Support Vector Machine

The SVM [5] is a supervised machine learning model often used for
classification problems. It uses the concept of an optimal separating
hyperplane depicted in [2, 5] to separate the data. On a ${\rm I\\!R}^{n}$
space, such a hyperplane is defined by a set of points $\mathbf{x}$ that
satisfies

$\mathbf{w}_{o}\cdot\mathbf{x}+b=0,$ (1)

where $\mathbf{w}_{o}\in{\rm I\\!R}^{n}$ is the optimal weight vector,
$\mathbf{x}\in{\rm I\\!R}^{n}$ is a feature vector with $n$ features and an
intercept (bias) $b\in{\rm I\\!R}$.

A given training set $\\{\mathbf{x}_{i},y_{i}\\}^{l}_{i=1}$ is said to be
linearly separable if there is $\mathbf{w}_{o}\in{\rm I\\!R}^{n}$ and
$b\in{\rm I\\!R}$ that guarantees the separation between positive and negative
class patterns without error. In other words, the following inequalities

$\text{for }i\in\\{1,...,l\\},\begin{cases}\begin{aligned}
\mathbf{w}_{o}\cdot\mathbf{x}_{i}+b\geq+1,\quad&\text{if }y_{i}=+1,\\\
\mathbf{w}_{o}\cdot\mathbf{x}_{i}+b\leq-1,\quad&\text{if
}y_{i}=-1,\end{aligned}\end{cases}$ (2)

must be satisfied to obtain the optimal hyperplane
$h_{o}=\\{\mathbf{x}\mid\mathbf{w}_{o}\cdot\mathbf{x}+b=0\\}$.

A Hard Margin SVM (SVM-HM) [24] can be used when the data is linearly
separable and misclassifications are not allowed, maximizing the margin
between two hyperplanes, $h_{+}$ and $h_{-}$, parallel to $h_{o}$. There can
be no training patterns between $h_{+}$ and $h_{-}$. Once maximizing the
margin is similar to minimizing $\frac{1}{2}||\mathbf{w}||^{2}$, the
optimization problem for obtaining the optimal parameters for the SVM can be
described as follows:

$\displaystyle\min_{\mathbf{w},b}$
$\displaystyle\quad{\frac{1}{2}||\mathbf{w}||^{2}}$ (3) s.t.
$\displaystyle\quad y_{i}(\mathbf{w}\cdot\mathbf{x}_{i}+b)\geq
1,\quad\text{for }i\in\\{1,...,l\\}.$

Thus, the decision function used for classifying input instances $\mathbf{x}$
is defined in the following:

$\displaystyle d(\mathbf{x})=\mathbf{w}\cdot\mathbf{x}+b,$ (4)

while the predicted label $\hat{y}\in\mathcal{K}$ of an input $\mathbf{x}$ is
given by

$\hat{y}=\begin{cases}\begin{aligned} +1,\quad\text{if }d(\mathbf{x})>0,\\\
-1,\quad\text{if }d(\mathbf{x})<0.\end{aligned}\end{cases}$ (5)

However, in real-world problems, the training patterns from the two classes
can not be linearly separated by a hyperplane due to data overlapping. In
order to overcome this situation, one must use Soft-Margin SVMs (SVM-SM) in
which misclassifications are allowed to happen. To do so, slack variables can
be used to relax the constraints of the SVM-HM [5, 24]. Given this, the
optimization problem for Soft-Margin SVMs is described as

$\displaystyle\min_{\mathbf{w},b,\mathbf{\xi}}$
$\displaystyle\quad\frac{1}{2}||\mathbf{w}||^{2}-C\sum^{l}_{i=1}\xi_{i}$ (6)
s.t. $\displaystyle\quad y_{i}(\mathbf{w}\cdot\mathbf{x}_{i}+b)\geq
1-\xi_{i},\quad$ $\displaystyle\text{for }i\in\\{1,...,l\\}$
$\displaystyle\quad\xi_{i}\geq 0,\quad$ $\displaystyle\text{for
}i\in\\{1,...,l\\}$

where $C$ is a trade-off between $\frac{1}{2}||\mathbf{w}||^{2}$ and
$\sum_{i}^{n}\xi_{i}$. Thus, for a high enough value of $C$, minimizing the
sum of errors while maximizing the separation margin leads toward the optimal
hyperplane. This can be the same as the one found through SVM-HM if the data
is linearly separable. Moreover, the decision function and predicted label for
SVM-HM and SVM-SM are the same.

###  2.3 Reject Option Classification

Reject option for classification problems, as depicted in [4], is a set of
techniques that aim to improve reliability in decision support systems. In the
case of a binary problem, it consists in withholding and rejecting a
classification result that is ambiguous enough, i.e. when the instance is too
close to the decision boundary of the classifier. For the linear SVC, it is
when the instance is too close to the separating hyperplane. Then, these
rejected instances are analyzed through another classification method or even
by a human specialist [20].

In applications where a high degree of reliability is needed and
misclassifications can be too costly, rejecting to classify a pattern can be
more beneficial than the risk of a higher error rate due to wrong
classifications [6]. According to [4], the optimal classifiers that best
handle such a relation can be achieved by the minimization of the empirical
risk

$\displaystyle\hat{R}=E+w_{r}R$ (7)

where $R$ is the ratio of the number of rejected training patterns to the
number of patterns in the entire training dataset; $E$ is the ratio of the
number of misclassified patterns to the number of all the training patterns
without including those ones rejected; and $w_{r}$ is a weight denoting the
cost of rejection. A lower $w_{r}$ gives room for a decreasing error rate at
the cost of a higher quantity of rejected instances, with the opposite
happening for a higher $w_{r}$.

A method is presented in [20] for single, standard binary classifiers that do
not provide probabilistic outputs. For SVCs, the proposed rejection techniques
are based on the distance of patterns to the optimal separating hyperplane. If
the distance value is lower than a predefined threshold, then the pattern is
rejected. As such, a rejection region is determined after the training step of
the classifier, with a threshold containing appropriate values being applied
to the output of the classifier. Therefore, applying this strategy to a
standard binary SVC leads to the following prediction cases:

$\hat{y}=\begin{cases}\begin{aligned} &+1,\quad\text{if
}f(\mathbf{x})>t_{+},\\\ &-1,\quad\text{if }f(\mathbf{x})<t_{-},\\\ &\hskip
12.80365pt0,\quad\text{otherwise},\end{aligned}\end{cases}$ (8)

where $t_{+}$ and $t_{-}$ are the thresholds for the positive class and
negative class, respectively, and 0 is the rejection class. Furthermore, these
thresholds are chosen to generate the optimal reject region, which corresponds
to the region that minimizes the empirical risk by producing both the ratio of
misclassified patterns $E$ and the ratio of rejected patterns $R$.

###  2.4 Heuristic-Based XAI

Some ML models are able to be interpreted by nature, such as decision trees
[22]. Others, such as neural networks and boosted trees, have harder-to-
explain outputs, leading to the use of specific methods to get some degree of
explanation [11]. One of the most predominant ways to achieve this is through
the use of heuristic methods for generating instance-dependent explanations,
which can be defined as a local approach. These analyze and explore the sub-
space close to the given instance [8, 11].

Some of the most well-known heuristic methods are LIME, SHAP, and Anchors.
These approaches are model-agnostic, generating local explanations while not
taking into account the instance space as a whole [18, 21, 22]. This, in turn,
allows the explanations to fail when applied, since they can be consistent
with instances predicted in different classes. Moreover, they can include
irrelevant elements which could be otherwise removed while still maintaining
the correctness of the answer [12]. Explanations with irrelevant elements may
be harder to understand.

Anchors have been shown as a superior version to LIME, having a better
accuracy with the resultant explanations [21]. This rule-based method is
designed to highlight which parts (features) of a given instance are
sufficient for a classifier to make a certain prediction while being intuitive
and easy to understand. However, it still gives room for wrong explanations
due to the local characteristic, which can lead to cases where, for the same
set of rules given by the explanation, different classes are predicted [11].
Therefore, both explanation validity and size can be set as of questionable
utility if they can not be fully relied upon.

###  2.5 First-Order Logic

In order to give explanations with guarantees of correctness, we use first-
order logic (FOL) [15]. We use quantifier-free first-order formulas over the
theory of linear real arithmetic. Then, first-order variables are allowed to
take values from the real numbers. Therefore, we consider formulas as defined
below:

$\displaystyle\varphi,\psi$
$\displaystyle:=s\mid(\varphi\wedge\psi)\mid(\varphi\vee\psi)\mid(\neg\varphi)\mid(\varphi\to\psi),$
(9)

$\displaystyle s$ $\displaystyle:=\sum^{n}_{i=1}a_{i}z_{i}\leq
c\mid\sum^{n}_{i=1}a_{i}z_{i}<c,$ (10)

such that $\varphi$ and $\psi$ are quantifier-free first-order formulas over
the theory of linear real arithmetic. Moreover, $s$ represents the atomic
formulas such that $n\geq 1$, each $a_{i}$ and $c$ are concrete real numbers,
and each $z_{i}$ is a first-order variable. For example,
$(2.5z_{1}+3.1z_{2}\geq 6)\wedge(z_{1}=1\vee z_{1}=2)\wedge(z_{1}=2\to
z_{2}\leq 1.1)$ is a formula by this definition. Observe that we allow
standard abbreviations as $\neg(2.5z_{1}+3.1z_{2}<6)$ for
$2.5z_{1}+3.1z_{2}\geq 6$.

Since we are assuming the semantics of formulas over the domain of real
numbers, an assignment $\mathcal{A}$ for a formula $\varphi$ is a mapping from
the first-order variables of $\varphi$ to elements in the domain of real
numbers. For instance, $\\{z_{1}\mapsto 2.3,z_{2}\mapsto 1\\}$ is an
assignment for $(2.5z_{1}+3.1z_{2}\geq 6)\wedge(z_{1}=1\vee
z_{1}=2)\wedge(z_{1}=2\to z_{2}\leq 1.1)$. An assignment $\mathcal{A}$
satisfies a formula $\varphi$ if $\varphi$ is true under this assignment. For
example, $\\{z_{1}\mapsto 2,z_{2}\mapsto 1.05\\}$ satisfies the formula in the
above example, whereas $\\{z_{1}\mapsto 2.3,z_{2}\mapsto 1\\}$ does not
satisfy it.

A formula $\varphi$ is satisfiable if there exists a satisfying assignment for
$\varphi$. Then, the formula in the above example is satisfiable since
$\\{z_{1}\mapsto 2,z_{2}\mapsto 1.05\\}$ satisfies it. As another example, the
formula $(z_{1}\geq 2)\wedge(z_{1}<1)$ is unsatisfiable since no assignment
satisfies it. The notion of satisfiability can be extended to sets of formulas
$\Gamma$. A set of first-order formulas is satisfiable if there exists an
assignment of values to the variables that makes all the formulas in $\Gamma$
true simultaneously. For example, $\\{(2.5z_{1}+3.1z_{2}\geq 6),(z_{1}=1\vee
z_{1}=2),(z_{1}=2\to z_{2}\leq 1.1)\\}$ is satisfiable given that
$\\{z_{1}\mapsto 2,z_{2}\mapsto 1.05\\}$ jointly satisfies each one of the
formulas in the set. It is well known that, for all sets of formulas $\Gamma$
and all formulas $\varphi$ and $\psi$,

$\displaystyle\Gamma\cup\\{\varphi\vee\psi\\}\text{ is unsatisfiable iff }$
$\displaystyle\Gamma\cup\\{\varphi\\}\text{ is unsatisfiable and }$ (11)
$\displaystyle\Gamma\cup\\{\psi\\}\text{ is unsatisfiable.}$

Given a set $\Gamma$ of formulas and a formula $\varphi$, the notation
$\Gamma\models\varphi$ is used to denote logical consequence, i.e., each
assignment that satisfies all formulas in $\Gamma$ also satisfies $\varphi$.
As an illustrative example, let $\Gamma$ be $\\{z_{1}=2,z_{2}\geq 1\\}$ and
$\varphi$ be $(2.5z_{1}+z_{2}\geq 5)\wedge(z_{1}=1\vee z_{1}=2)$. Then,
$\Gamma\models\varphi$ since each satisfying assignment for all formulas in
$\Gamma$ is also a satisfying assignment for $\varphi$. Moreover, it is widely
known that, for all sets of formulas $\Gamma$ and all formulas $\varphi$,

$\displaystyle\Gamma\models\varphi\text{ iff
}\Gamma\cup\\{\neg\varphi\\}\text{ is unsatisfiable.}$ (12)

For instance, $\\{z_{1}=2,z_{2}\geq 1,\neg((2.5z_{1}+z_{2}\geq
5)\wedge(z_{1}=1\vee z_{1}=2))\\}$ has no satisfying assignment since an
assignment that satisfies $(z_{1}=2\wedge z_{2}\geq 1)$ also satisfies
$(2.5z_{1}+z_{2}\geq 5)\wedge(z_{1}=1\vee z_{1}=2)$ and, therefore, does not
satisfy $\neg((2.5z_{1}+z_{2}\geq 5)\wedge(z_{1}=1\vee z_{1}=2))$.

Finally, we say that two first-order formulas $\varphi$ and $\psi$ are
equivalent if, for each assignment $\mathcal{A}$, both $\varphi$ and $\psi$
are true under $\mathcal{A}$ or both are false under $\mathcal{A}$. We use the
notation $\varphi\equiv\psi$ to represent that $\varphi$ and $\psi$ are
equivalent. For example, $\neg((z_{1}+z_{2}\leq 2)\wedge z_{1}\geq 1)$ is
equivalent to $(\neg(z_{1}+z_{2}\leq 2)\vee\neg(z_{1}\geq 1))$. Besides, these
formulas are equivalent to $((z_{1}+z_{2}>2)\wedge z_{1}<1)$.

##  3 Linear SVCs may not be Instance-based Interpretable

Efforts have been made to bring explanations to linear SVCs prediction
outputs. These have often been done through the analysis of the weights that
compose the decision function, where the most important features are
associated with the highest weights [7]. However, this may not be enough to
enable correct interpretations. Although feature weights can give a rough
indication of the overall relevance of features, they do not offer insight
into the local decision-making process for a specific set of instances [14].

Assume a binary classification problem where $\mathcal{F}=\\{f_{1},f_{2}\\}$,
and a linear SVC where $w=\\{w_{1}=-0.8,w_{2}=2\\}$ and $b=0.05$. The features
$f_{i}$ can take values in range $[0,1]$. A visual representation is depicted
in Figure 1. Analyzing solely through the values of the weights, it could be
assumed that the feature $f_{2}$ is determinant and $f_{1}$ is not, since
$|w_{2}|>|w_{1}|$. This would mean that, for any instance, feature $f_{2}$ is
more important than feature $f_{1}$. However, for the instance
$\\{f_{1}=0.0526,f_{2}=0.3\\}$ predicted as class $+1$, feature $f_{2}$ is not
necessary for the prediction, since for any value of $f_{2}$ the class will
not change. Therefore, feature $f_{1}$ is sufficient for the prediction of
this instance. Moreover, feature $f_{2}$ is not sufficient for the prediction
of this instance, since for $f_{1}=1.0$ and $f_{2}=0.3$ the prediction would
change to $-1$. Therefore, for instance $\\{f_{1}=0.0526,f_{2}=0.3\\}$,
feature $f_{1}$ would be determinant and $f_{2}$ would not.

Figure 1:  Classification through features $f_{1}$ and $f_{2}$.

While it is trivial to observe if feature $f_{1}$ and $f_{2}$ can be
determinant, due to the simplicity of the given decision function, it becomes
harder to do so as the number of features increases. Furthermore, the presence
of reject option adds another layer of complexity to the problem, turning the
interpretation task very non-trivial. Hence, explanations given by weights
evaluation may give room for incorrect interpretations. This raises the need
for an approach to compute explanations with guarantees of correctness for
linear SVCs with reject option.

##  4 Explanations For Linear SVMs with Reject Option

As depicted before, most methods that generate explanations for ML models are
heuristic, which can bring issues about how correct and trustworthy the
generated answers are. Added that they tend not to take into account whether
reject option is present, these problems are further aggravated. As such, an
approach that guarantees the correctness of explanations for ML models with
reject option is due.

In this work, we are considering instance-based explanations, i.e. given a
trained linear SVC with reject option and an instance
$I=\\{f_{1}=v_{1},f_{2}=v_{2},...,f_{n}=v_{n}\\}$ classified as class
$c\in\\{-1,+1,0\\}$, an explanation $E$ is a subset of the instance
$E\subseteq I$ sufficient for the prediction $c$. Therefore, by fixing the
values of the features in $E$, the prediction is guaranteed to be $c$,
regardless of the values of the other features.

Our approach is achieved through the encoding of the linear SVC with reject
option as a first-order formula, following the ideas of [10] for neural
networks. Here we need to take into account the reject option and its encoding
as a first-order formula. For example, given a trained linear SVC with reject
option defined by $w$, $b$, $t_{+}$ and $t_{-}$ as in Equations 4 and 8, and
an instance $I$ classified as class $c=0$, i.e. in the rejection class, we
define the first-order formula $P$:

$\displaystyle P=(\sum^{n}_{i=1}w_{i}f_{i}+b\leq
t_{+})\wedge(\sum^{n}_{i=1}w_{i}f_{i}+b\geq t_{-}).$ (13)

Therefore, given an instance $I=\\{f_{1}=v_{1},f_{2}=v_{2},...,f_{n}=v_{n}\\}$
such that its features are defined by $D=\\{l_{1}\leq f_{1}\leq
u_{1},l_{2}\leq f_{2}\leq u_{2},...,l_{n}\leq f_{n}\leq u_{n}\\}$, an
explanation is a subset $E\subseteq I$ such that $E\cup D\models P$. In other
words, prediction is guaranteed to be in the rejection class. Instances
predicted in other classes are treated in a similar way. For example, if
instance $I$ is classified as class $c=+1$, $P$ is defined as
$\sum^{n}_{i=1}w_{i}f_{i}+b>t_{+}$. It is worth noting that, in these
formulas, each $f_{i}$ is a first-order variable, and $b$, $t_{+}$, $t_{-}$
and each $w_{i}$ are concrete real numbers.

Since succinct explanations seem easier to understand, one would like $E$ to
be minimal, that is, for all subset $E^{\prime}\subseteq E$, $E^{\prime}\cup
D\not\models P$. Therefore, if $E$ is minimal, then each of its subsets does
not guarantee the same prediction. Informally, a minimal explanation provides
an irreducible explanation that is sufficient for guaranteeing the prediction.

Earlier work [10] outlined Algorithm 1 for computing minimal explanations for
neural networks. By leveraging the insights from this earlier work, we can
effectively employ Algorithm 1 to find a minimal explanation for linear SVCs
with reject option given $I$, $D$ and $P$. The minimal explanation $E$ of $I$
is calculated by setting $E$ to $I$ and then removing feature by feature from
$E$. For example, given a feature $f_{i}=v_{i}$ in $E$, if
$E\setminus\\{f_{i}=v_{i}\\},D\models P$, then the value $v_{i}$ of feature
$f_{i}$ is not necessary to ensure the prediction, and then it is removed from
$E$. Otherwise, if $E\setminus\\{f_{i}=v_{i}\\},D\not\models P$, then
$f_{i}=v_{i}$ is kept in $E$ since it is necessary for the prediction. This
process is performed for all features as described in Algorithm 1. Then, at
the end of Algorithm 1, for the values of features in $E$, the prediction is
the same and invariant with respect to the values of the remaining features.

By the result in 12, verifying entailments of the form
$(E\setminus\\{f_{i}=v_{i}\\})\cup D\models P$ can be done by testing whether
the set of first-order formulas $(E\setminus\\{f_{i}=v_{i}\\})\cup
D\cup\\{\neg P\\}$ is unsatisfiable. If $\neg P$ is equivalent to a
disjunction $P_{1}\vee P_{2}$ as in 13, then we must check whether
$(E\setminus\\{f_{i}=v_{i}\\})\cup D\cup\\{P_{1}\\}$ is unsatisfiable and
$(E\setminus\\{f_{i}=v_{i}\\})\cup D\cup\\{P_{1}\\}$ is unsatisfiable, by the
result in 11.

Moreover, since $(E\setminus\\{f_{i}=v_{i}\\})\cup D$ is a set of linear
constraints and $P_{1}$ and $P_{2}$ are linear constraints, the
unsatisfiability checkings can be achieved by two queries answered by a linear
programming (LP) solver. Therefore, if, for example, the set of linear
constraints $(E\setminus\\{f_{i}=v_{i}\\})\cup D\cup\\{P_{1}\\}$ has a
solution, then $(E\setminus\\{f_{i}=v_{i}\\})\cup D\not\models P$. From a
computational complexity view-point, the linear programming problem is
solvable in polynomial time. Then, our approach for computing minimal
explanations for linear SVCs with reject option can also be solved in
polynomial time. This is achieved by a linear number of calls to an LP solver,
which further contributes to the efficiency and feasibility of our approach.

Algorithm 1 Computing a minimal explanation

Input: instance $I$, domain constraints $D$, prediction $P$

Output: minimal explanation $E$

$E\leftarrow I$

for $f_{i}=v_{i}\in E$ do

if $(E\backslash\\{f_{i}=v_{i}\\})\cup D\models P$ then

$E\leftarrow E\backslash\\{f_{i}=v_{i}\\}$

end if

end for

return $E$

##  5 Experiments

In this paper, a total of 6 datasets are used. The Vertebral Column and the
Sonar datasets are available on the UCI machine learning
repository.111https://archive.ics.uci.edu/ml/datasets.php The Pima Indians
Diabetes dataset is available on
Kaggle.222https://www.kaggle.com/datasets/uciml/pima-indians-diabetes-database
The Iris, the Breast Cancer Wisconsin, and the Wine datasets are available
through the scikit-learn package.333https://github.com/scikit-learn/scikit-
learn/tree/main/sklearn/datasets/data All attributes were scaled to the range
$[0,1]$.

The Iris and the Wine dataset have three classes and have been adapted to be
binary classification problems, changed to setosa-versus-all and
class_0-versus-all, respectively. The other datasets have two classes. The
classes were changed to follow values in $\\{-1,+1\\}$. A summary of the
datasets is presented in Table 1.

Table 1: Datasets details. Dataset | Acronym | $|\mathcal{F}|$ | Negative Patterns | Positive Patterns
---|---|---|---|---
Iris | IRIS | 4 | 50 | 100
Vertebral Column | VRTC | 6 | 100 | 210
Pima | PIMA | 8 | 500 | 268
Wine | WINE | 13 | 59 | 119
Breast Cancer Wisconsin | BRCW | 30 | 212 | 357
Sonar | SONR | 60 | 111 | 97

The classifiers. For each dataset, a linear SVC was trained based on 70% of
the original data, with a regularization parameter $C=1$ and stratified
sampling. For finding the rejection region, a value of $w_{r}=0.24$ was used
together with the decision function outputs based on training data. The
selected rejection thresholds were obtained by minimizing the empirical risk,
as described in Subsection 2.3. All patterns were used for generating
explanations, including both the ones used for training and testing. This is
due to the focus on explaining rather than model evaluation.

For defining the values of $t_{+}$ and $t_{-}$, we determine a range of
thresholds $T=\\{(t_{+}^{1},t_{-}^{1}),...,(t_{+}^{k},t_{-}^{k})\\}$
containing the respective possible candidates. The maximum absolute value for
$t_{+}$ and $t_{-}$ in $T$, respectively, is the highest and lowest output
value of the decision function, i.e. the $upper\\_limit$ and the
$lower\\_limit$, based on the training patterns. Thus, the attainable
thresholds are achieved through

$\displaystyle T$ $\displaystyle=\\{(i\cdot 0.01\cdot upper\\_limit,\text{
}i\cdot 0.01\cdot lower\\_limit)\mid i\in\\{1,...,100\\}\\}.$ (14)

Hence, the selected values of $t_{+}$ and $t_{-}$ are the pair that minimizes
the empirical risk $\hat{R}$. In addition, using $w_{r}=0.24$, we obtained the
best reject region defined by $t_{+}$ and $t_{-}$, the test accuracy of the
classifier with RO, and the rejection ratio based on test data. The test
accuracy of a classifier with RO is the standard test accuracy applied only to
non-rejected instances. Afterward, we determine the number of patterns per
class from both training and test data, i.e. the entire datasets. Table 2
details these results and also the test accuracy of the classifier without
reject option.

Table 2: Reject region thresholds using training data. Classifier accuracy
without reject option, accuracy with reject option, and rejection ratio for
test data. Patterns by class for each entire dataset.

Dataset | $t_{-}$ | $t_{+}$ | Accuracy w/o RO | Accuracy w/ RO | Rejection | Negative | Rejected | Positive
---|---|---|---|---|---|---|---|---
IRIS | -0.0157 | 0.0352 | 100.0% | 100.00% | 00.00% | 50 | 0 | 100
VRTC | -0.3334 | 0.8396 | 76.34% | 89.65% | 47.92% | 22 | 139 | 149
PIMA | -1.1585 | 0.8312 | 76.62% | 92.20% | 59.59% | 232 | 474 | 62
WINE | -0.0259 | 0.0243 | 96.29% | 96.29% | 00.56% | 56 | 1 | 121
BRCW | -0.4914 | 0.2370 | 97.66% | 98.76% | 04.02% | 190 | 25 | 354
SONR | -0.3290 | 0.2039 | 74.60% | 79.59% | 20.00% | 76 | 43 | 89

Observe that the reject region for the IRIS dataset did not return any
rejected patterns in the dataset. This is likely due to the problem being
linearly separable. Therefore, since our experiments rely on explaining the
instances present in the dataset, this case of the IRIS dataset is treated as
if reject option is not present.

The reject region obtained for the WINE dataset did not reject any of the test
patterns, therefore having no change in accuracy, likely due to the fact that
the value chosen for $w_{r}$ penalizes rejections too harshly. For the other
datasets, the presence of reject option lead to a higher accuracy in all
cases. This is expected since the rejected patterns are not taken into account
for evaluation. In addition, there was a substantial increase for both the
VRTC and the PIMA dataset at the cost of rejecting roughly 48% and 60% of all
the test patterns, respectively. Different values for $w_{r}$ can be used to
achieve desirable results, depending on how much a rejection must be penalized
in each dataset.

Anchors. We compared our approach against the heuristic method Anchors for
computing explanations. Anchors was designed to work with traditional
multiclass classification problems, i.e. classifiers without reject option.
Then, since we are explaining predictions of a linear SVC with reject option,
we used the Anchors explanation algorithm to treat the classifier with reject
option as if it were a traditional classifier with classes in $\\{-1,0,+1\\}$.

Our approach. The prototype implementation of our
approach444https://github.com/franciscomateus0119/Logic-based-Explanations-
for-Linear-Support-Vector-Classifiers-with-Reject-Option is written in Python
and follows Algorithm 1. As an LP solver to check unsatisfiability of sets of
first-order sentences, we used Coin-or Branch-and-Cut
(CBC)555https://github.com/coin-or/Cbc. Moreover, the solver is accessed via
the Python API PuLP666https://github.com/coin-or/pulp.

###  5.1 Results

A per-instance explanation is done for each dataset. Both mean elapsed time
(in seconds) and the mean of the number of features in explanations are used
as the basis for comparison. The results based on the former and the latter
are presented in Table 3 and Table 4, respectively. Following the IRIS dataset
description in Table 2, there are no results for the rejected class.

Table 3: Time comparison between our approach and Anchors (seconds). Less is
better.

Dataset | Negative | Rejected | Positive
---|---|---|---
Anchors | Ours | Anchors | Ours | Anchors | Ours
IRIS | 0.13 $\pm$ 0.045 | 0.04 $\pm$ 0.004 | - | - | 0.05 $\pm$ 0.024 | 0.04 $\pm$ 0.005
VRTC | 0.27 $\pm$ 0.049 | 0.07 $\pm$ 0.004 | 0.33 $\pm$ 0.147 | 0.12 $\pm$ 0.018 | 0.28 $\pm$ 0.156 | 0.07 $\pm$ 0.002
PIMA | 0.85 $\pm$ 0.162 | 0.10 $\pm$ 0.001 | 0.27 $\pm$ 0.302 | 0.16 $\pm$ 0.021 | 0.61 $\pm$ 0.108 | 0.10 $\pm$ 0.002
WINE | 3.01 $\pm$ 0.335 | 0.17 $\pm$ 0.002 | 1.60 $\pm$ 0.000 | 0.21 $\pm$ 0.000 | 0.38 $\pm$ 0.532 | 0.17 $\pm$ 0.002
BRCW | 26.58 $\pm$ 4.268 | 0.42 $\pm$ 0.015 | 20.66 $\pm$ 3.506 | 0.55 $\pm$ 0.072 | 5.84 $\pm$ 9.686 | 0.41 $\pm$ 0.013
SONR | 233.26 $\pm$ 70.550 | 0.86 $\pm$ 0.011 | 257.51 $\pm$ 16.267 | 1.27 $\pm$ 0.258 | 246.14 $\pm$ 51.82 | 0.86 $\pm$ 0.019

Table 4: Explanation size comparison between our approach and Anchors. Less is
better.

Dataset | Negative | Rejected | Positive
---|---|---|---
Anchors | Ours | Anchors | Ours | Anchors | Ours
IRIS | 3.52 $\pm$ 0.854 | 3.00 $\pm$ 0.000 | - | - | 1.89 $\pm$ 0.733 | 2.2 $\pm$ 0.400
VRTC | 4.95 $\pm$ 1.580 | 5.18 $\pm$ 0.574 | 4.56 $\pm$ 1.941 | 4.99 $\pm$ 0.515 | 4.24 $\pm$ 2.077 | 4.20 $\pm$ 1.118
PIMA | 7.50 $\pm$ 1.534 | 5.13 $\pm$ 0.944 | 3.02 $\pm$ 2.249 | 4.71 $\pm$ 0.897 | 6.37 $\pm$ 2.541 | 4.85 $\pm$ 1.119
WINE | 12.98 $\pm$ 0.132 | 7.44 $\pm$ 1.252 | 13.00 $\pm$ 0.000 | 12.00 $\pm$ 0.000 | 2.80 $\pm$ 2.803 | 7.04 $\pm$ 1.605
BRCW | 29.17 $\pm$ 4.372 | 22.29 $\pm$ 3.739 | 29.64 $\pm$ 1.763 | 27.08 $\pm$ 1.016 | 7.70 $\pm$ 11.024 | 23.08 $\pm$ 2.208
SONR | 51.10 $\pm$ 20.075 | 50.39 $\pm$ 4.283 | 57.95 $\pm$ 9.233 | 56.16 $\pm$ 1.413 | 54.86 $\pm$ 14.625 | 51.78 $\pm$ 1.413

Our approach has shown to be up to, surprisingly, roughly $286$ times faster
than Anchors. This happened for the SONR dataset, where the mean elapsed time
of our method is $0.86$ seconds against $246.14$ seconds for Anchors. These
results show how much harder it can be for Anchors to give an explanation as
the number of features increases. Furthermore, it is worth noting that our
approach needs much less time to explain positive, negative, and rejected
classes overall.

While our approach obtained more extensive explanations in certain cases, it
also demonstrated the ability to be more succinct, generating explanations
that were up to $43\%$ smaller in other cases. In addition, our method is able
to maintain the correctness of explanations. This highlights an expressive
advantage of our approach over the heuristic nature of Anchors. While Anchors
may provide explanations with fewer features in some cases, this is achieved
due to the lack of formal guarantees on correctness.

It is important to note that cases similar to what we discussed in Section 3
occurred for the IRIS dataset. Through weights
$\mathbf{w}=\\{w_{1}=0.8664049,w_{2}=-1.42027753,w_{3}=2.18870793,w_{4}=1.7984087\\}$
and $b=-0.77064659$, obtained from the trained SVC, it could be assumed that
feature $f_{1}$ might possibly be not determinant for the classification.
Explanation results for both negative and positive classes are presented in
Table 5, depicting the number of times each feature was present in
explanations with our approach.

Table 5: Number of times each feature is determinant for the IRIS dataset
classification.

Class | $f_{1}$ | $f_{2}$ | $f_{3}$ | $f_{4}$ | Patterns
---|---|---|---|---|---
Positive | 0 | 28 | 100 | 92 | 100
Negative | 1 | 49 | 50 | 50 | 50

For example, for the instance
$\\{f_{1}=0.05555556,f_{2}=0.05833333,f_{3}=0.05084746,f_{4}=0.08333333\\}$ in
class $-1$, feature $f_{1}$ was in the explanation, while feature $f_{2}$ was
not present. Then, for any value that $f_{2}$ assumes, the predicted class
will not change. Furthermore, similar cases happened where $f_{2}$ was in the
explanation while $f_{4}$ was not, even though $|w_{4}|>|w_{2}|$.

Similar occurrences are present in other datasets, reinforcing that the points
discussed in Section 3 are not uncommon. As one more illustrate example,
consider the linear SVC with reject option trained on the VRTC dataset such
that $\mathbf{w}=\\{w_{1}=0.72863148,$ $w_{2}=1.97781269,$ $w_{3}=0.85680605,$
$w_{4}=-0.32466632,$ $w_{5}=-3.42937211,$ $w_{6}=2.43522629\\}$,
$b=1.10008469$, $t_{-}=-0.3334$ and $t_{+}=0.8396$. For the instance
$\\{f_{1}=0.25125386,f_{2}=0.4244373,f_{3}=0.7214483,f_{4}=0.20007403,f_{5}=0.71932466,f_{6}=0.15363128\\}$
in the reject class, feature $f_{3}$ was not in the explanation, while $f_{4}$
is present in the explanation, despite the fact that $|w_{3}|>|w_{4}|$. This
is substantial for our approach since it demonstrates its capability of
finding such cases.

##  6 Conclusions

In this paper, we propose a logic-based approach to generate minimal
explanations for a classifier with reject option while guaranteeing
correctness. A trained linear SVC with reject option is used as a target model
for explainability. Our approach is rooted in earlier work on computing
minimal explanations for standard machine learning models without reject
option. Therefore, we encode the task of computing explanations for linear
SVCs with reject option as a logical entailment problem. Moreover, we use an
LP solver for checking the entailment, since all first-order sentences are
linear constraints with real variables and at most one disjunction occurs.

Our method is compared against Anchors, one of the most well-known heuristic
methods, through six different datasets. We found that not only the proposed
method takes considerably less time than Anchors, but also reduces the size of
explanations for many instances. Our approach achieved astonishing results in
terms of efficiency, surpassing Anchors by an impressive factor of up to
approximately 286 times.

Our approach can be further improved in future work. For example, it can be
easily adapted to other classifiers with reject option, such as neural
networks and random forests. In addition, it can be adjusted for a non-linear
SVM. Another improvement is the generalization of explanations by allowing a
range of values for each feature, rather than solely considering equality.
This improvement may enable a more comprehensive understanding of the model.

####  6.0.1 Acknowledgments.

The authors thank FUNCAP and CNPq for partially supporting our research work.

## References

  * [1] Audemard, G., Bellart, S., Bounia, L., Koriche, F., Lagniez, J.M., Marquis, P.: On preferred abductive explanations for decision trees and random forests. In: Thirty-First International Joint Conference on Artificial Intelligence $\\{$IJCAI-22$\\}$. pp. 643–650 (2022)
  * [2] Boser, B.E., Guyon, I.M., Vapnik, V.N.: A training algorithm for optimal margin classifiers. In: Proceedings of the fifth annual workshop on Computational learning theory. pp. 144–152 (1992)
  * [3] Chlaoua, R., Meraoumia, A., Aiadi, K.E., Korichi, M.: Deep learning for finger-knuckle-print identification system based on PCANet and SVM classifier. Evolving Systems 10(2), 261–272 (2019)
  * [4] Chow, C.: On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory 16(1), 41–46 (1970)
  * [5] Cortes, C., Vapnik, V.: Support-vector networks. Machine learning 20, 273–297 (1995)
  * [6] De Oliveira, A.C., Gomes, J.P.P., Neto, A.R.R., de Souza, A.H.: Efficient minimal learning machines with reject option. In: 2016 5th Brazilian Conference on Intelligent Systems (BRACIS). pp. 397–402. IEEE (2016)
  * [7] Guyon, I., Weston, J., Barnhill, S., Vapnik, V.: Gene selection for cancer classification using support vector machines. Machine learning 46, 389–422 (2002)
  * [8] Ignatiev, A.: Towards trustable explainable ai. In: IJCAI. pp. 5154–5158 (2020)
  * [9] Ignatiev, A., Izza, Y., Stuckey, P.J., Marques-Silva, J.: Using maxsat for efficient explanations of tree ensembles. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 36, pp. 3776–3785 (2022)
  * [10] Ignatiev, A., Narodytska, N., Marques-Silva, J.: Abduction-based explanations for machine learning models. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 33, pp. 1511–1519 (2019)
  * [11] Ignatiev, A., Narodytska, N., Marques-Silva, J.: On validating, repairing and refining heuristic ML explanations. CoRR abs/1907.02509 (2019)
  * [12] Ignatiev, A., Narodytska, N., Marques-Silva, J.: On formal reasoning about explanations. In: RCRA (2020)
  * [13] Izza, Y., Ignatiev, A., Marques-Silva, J.: On explaining decision trees. arXiv preprint arXiv:2010.11034 (2020)
  * [14] Krause, J., Dasgupta, A., Swartz, J., Aphinyanaphongs, Y., Bertini, E.: A workflow for visual diagnostics of binary classifiers using instance-level explanations (2017)
  * [15] Kroening, D., Strichman, O.: Decision procedures. Springer (2016)
  * [16] La Malfa, E., Michelmore, R., Zbrzezny, A.M., Paoletti, N., Kwiatkowska, M.: On guaranteed optimal robust explanations for NLP models. In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. pp. 2658–2665 (2021)
  * [17] LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. nature 521(7553), 436–444 (2015)
  * [18] Lundberg, S.M., Lee, S.I.: A unified approach to interpreting model predictions. Advances in neural information processing systems 30 (2017)
  * [19] Marques-Silva, J., Gerspacher, T., Cooper, M., Ignatiev, A., Narodytska, N.: Explaining naive bayes and other linear classifiers with polynomial time and delay. Advances in Neural Information Processing Systems 33, 20590–20600 (2020)
  * [20] Mesquita, D.P., Rocha, L.S., Gomes, J.P.P., Rocha Neto, A.R.: Classification with reject option for software defect prediction. Applied Soft Computing 49, 1085–1093 (2016)
  * [21] Ribeiro, M., Singh, S., Guestrin, C.: Anchors: High-precision model-agnostic explanations. Proceedings of the AAAI Conference on Artificial Intelligence 32 (04 2018)
  * [22] Ribeiro, M.T., Singh, S., Guestrin, C.: "why should I trust you?" explaining the predictions of any classifier. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. pp. 1135–1144 (2016)
  * [23] Richhariya, B., Tanveer, M., Rashid, A.H., Initiative, A.D.N., et al.: Diagnosis of alzheimer’s disease using universum support vector machine based recursive feature elimination (USVM-RFE). Biomedical Signal Processing and Control 59, 101903 (2020)
  * [24] Vapnik, V.: Statistical learning theory. Wiley (1998)
  * [25] Weld, D.S., Bansal, G.: Intelligible artificial intelligence. CoRR abs/1803.04263 (2018)
  * [26] Yang, W., Si, Y., Wang, D., Guo, B.: Automatic recognition of arrhythmia based on principal component analysis network and linear support vector machine. Computers in biology and medicine 101, 22–32 (2018)


# Q&A: Query-Based Representation Learning for Multi-Track Symbolic
Music re-Arrangement

Jingwei Zhao2,3 Gus Xia4,5&Ye Wang1,2,3 1School of Computing, NUS
2Institute of Data Science, NUS
3Integrative Sciences and Engineering Programme, NUS Graduate School
4Music X Lab, NYU Shanghai
5MBZUAI
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Music rearrangement is a common music practice of reconstructing and
reconceptualizing a piece using new composition or instrumentation styles,
which is also an important task of automatic music generation. Existing
studies typically model the mapping from a source piece to a target piece via
supervised learning. In this paper, we tackle rearrangement problems via self-
supervised learning, in which the mapping styles can be regarded as conditions
and controlled in a flexible way. Specifically, we are inspired by the
representation disentanglement idea and propose Q&A, a query-based algorithm
for multi-track music rearrangement under an encoder-decoder framework. Q&A
learns both a _content_ representation from the mixture and function (_style_)
representations from each individual track, while the latter queries the
former in order to rearrange a new piece. Our current model focuses on popular
music and provides a controllable pathway to four scenarios: 1) re-
instrumentation, 2) piano cover generation, 3) orchestration, and 4) voice
separation. Experiments show that our query system achieves high-quality
rearrangement results with delicate multi-track structures, significantly
outperforming the baselines.

##  1 Introduction

It is sometimes easy to craft an idea of the melody but usually hard to frame
a good arrangement. Formally, arrangement refers to the form of a musical
piece, typically with textures and voicing carefully designed for multiple
instruments as a unique style. On top of that, a piece can also be rearranged
to convey new feelings. Such _rearrangement_ scenarios include piano cover
generation from multi-track music, multi-track orchestration from piano, and
re-instrumentation using varied instruments, which are all common tasks in
music practice.

While much progress has been witnessed in automatic music generation Huang et
al. (2019); Huang and Yang (2020); Hsiao et al. (2021), rearrangement remains
a challenging problem. Among various ways to rearrange a piece, most studies
have focused on the reduction from complex forms to simpler ones, such as
generating piano covers from multi-track music. The reduction is typically
done by masking least significant notes, either identified by rule-based
criteria Nakamura and Yoshii (2018) or learned by supervision Terao et al.
(2022). While rearrangement in this way is generally faithful, it tends to
produce sparse or repetitive textures that fall short of creativity. More
recent works have also taken on simple-to-complex rearrangement, such as
orchestration Crestel and Esling (2017); Dong et al. (2021). While these works
are still fully supervised, the scarce of paired piano and multi-track data
remains a major problem in this direction.

Another considerable challenge for music rearrangement lies in _multi-track_
modelling. Previous works have typically interpreted “track” as “instrument”
and merge individual tracks of the same instrument class to simplify the
problem Dong et al. (2018); Ren et al. (2020). However, instrument alone is
not necessarily a good representative of a multi-track system in symbolic
music. For example, pop music often has two guitar tracks of quite different
functions – a _melodic_ one and a _harmonic_ one. When merged together, the
distinctive texture structures of each track become less transparent, which
may add extra burden to the model.

Figure 1: Q&A is a unified framework for re-instrumentation, orchestration,
piano cover generation, and voice separation.

In this paper, we aim to approach multi-track music rearrangement while
balancing faithfulness with creativity. We render the content of a source
piece using the style from a reference piece that is free to choose. In terms
of the “style” of a multi-track piece, apart from instruments, we believe the
_function_ of each component track is also important. Specifically, we
consider the function of a track as its texture density distribution along the
time- and pitch-axes, respectively, which can describe both the distinctive
intra-track structures (e.g., melodic v.s. harmonic) and the inter-track
dependencies (e.g., pitch range and voicing). We use track functions as
queries in a _query-based track separation process_ to reconstruct individual
tracks from a track-wise condensed mixture. Under the VAE framework Wang et
al. (2020c), we devise a pipeline consisting of four components: 1) an encoder
that maps a mixture to the latent space; 2) a query-net Lee et al. (2019) that
encodes function features of each track; 3) a Transformer-based Vaswani et al.
(2017) query system that separates each track from the mixture at the latent
representation level; and 4) a decoder that reconstructs each separated track.
At inference time, our model can query a piece and rearrange it with diverse
track functions.

We name our model after _Q &A_ (Query & re-Arrange), which provides a unified
solution to a range of multi-track music rearrangement tasks, including: 1)
_re-instrumentation_ – to rearrange a multi-track piece with a new track
system; 2) _piano cover generation_ – to rearrange a multi-track piece into
piano solo; and 3) _orchestration_ – to rearrange a piano piece with a
variable types of instruments in a variable number of tracks. By inferring
track functions as voice hints, our model can additionally handle 4) _voice
separation_ – to separate distinctive voicing tracks (assuming a preset total
number of voices) from an ensemble mixture by generating each track. Figure 1
shows the relations among the four tasks.

Our current model focuses on pop music rearrangement. We also test our model’s
voice separation performance on string quartets and Bach chorales.
Experimental results show that our model not only generates high-quality
arrangements, but also maintains fine-grained symbolic track structures with
musically intuitive and playable textures for each track. In summary, our
contributions in this paper are as follows:

  * •

A versatile rearrangement model: We present _Q
&A_111https://github.com/zhaojw1998/Query-and-reArrange, the first unified
framework for re-instrumentation, piano cover generation, orchestration, and
voice separation. The rearrangement results demonstrate state-of-the-art
quality over existing models for similar purposes.

  * •

Function-aware multi-track music modelling: We design instrument-agnostic
track functions for multi-track modelling, which can better describe the
distinctions of parallel tracks and their dependencies. This method is
applicable to a wider range of music generation tasks.

  * •

Query-based representation learning: We introduce a self-supervised query
system separating parts from the mixture at latent representation level.
Experiments show that our model learns style representations of each part
disentangled from the mixture content, demonstrating interpretable and
controllable generative modelling.

##  2 Related Work

###  2.1 Symbolic Music Rearrangement

Existing studies on music rearrangement commonly rely on supervised learning
to map a source piece to a target one. For example, Crestel and Esling Crestel
and Esling (2017) project piano solo to orchestra by training a seq2seq model
on a classical repertoire of paired data Crestel et al. (2017). Dong et al.
Dong et al. (2021) approach automatic instrumentation by predicting the
instrument attribute of each note in a track-wise condensed mixture. Models
for piano reduction can have more rule-based designs Nakamura and Sagayama
(2015); Takamori et al. (2017), but are still generally under supervised
frameworks. Except for several works that consider difficulty level as
condition Nakamura and Yoshii (2018); Terao et al. (2022), most models cannot
steer the rearrangement process or change the composition style.

In this paper, instead of supervised mapping, we render the content of a
source piece using the style from a reference piece. In terms of content, we
preserve the general melodic and harmonic structures. As for style, we
introduce a new track system, i.e., textural functions of each track along
with the instruments to play them, to reconceptualize the source piece. Our
methodology can be formalized as composition style transfer Dai et al. (2018)
while existing research most relevant to us is Hung et al. (2019), which
approaches re-instrumentation by transferring instrument timbres from
different references. While Hung et al. Hung et al. (2019) still require
supervision from audio-symbolic pairs, our model is fully symbolic-based,
self-supervised, and unified for re-instrumentation, piano cover generation,
and orchestration.

Figure 2: The architecture of Q&A consists of four key components: mixture
encoder $\mathrm{Enc}^{\mathrm{m}}$, function query-net with encoder
$\mathrm{Enc}^{\mathrm{f}}$ and decoder $\mathrm{Dec}^{\mathrm{f}}$, track
separator $\mathrm{Sep}$, and track decoder $\mathrm{Dec}^{\mathrm{tk}}$. Q&A
learns both a content representation from the mixture and function
representations from each individual track, while the latter queries the
former in order to rearrange a new piece.

###  2.2 Multi-Track Music Modelling

Multi-track music is an arrangement form commonly seen in accompaniment,
symphony, ensembles, etc. However, it is very challenging for machines to
understand multi-track data. To capture inter-track dependency, mainstream
approaches either distribute vari-instrument tracks into parallel data
channels Dong et al. (2018); Zhu et al. (2018); Hung et al. (2019) or
incorporate instrument labels as part of note event tokens Donahue et al.
(2019); Payne (2019); Ren et al. (2020). Such methods are ideal for CNN-based
and language models, respectively, yet both inevitably merging co-instrument
tracks together. The event-based approach additionally enforces a positional
relation to parallel tracks that are not sequentially ordered, which can
damage the intrinsic structure of multi-track music Wang and Xia (2021). More
recently, several works target at these issues and support generating co-
instrument tracks without a sequential assumption Ens and Pasquier (2020); Liu
et al. (2022). However, these models are not applicable to general music
rearrangement.

In this work, apart from instrument, we introduce track function as an equally
(if not more) important feature to describe and distinguish individual tracks
in multi-track music. We define and use the function of a track to represent
its texture and voicing structures. We further model multi-track music via
self-supervised learning, i.e., using each function to query and separate
corresponding tracks from a mixture.

##  3 Methodology

We propose Q&A, a query-based algorithm for multi-track music rearrangement
under an encoder-decoder framework. An overview of our model is shown in
Figure 2. In this section, we first introduce our data representation of
multi-track music and track functions in Section 3.1. Then, we introduce our
model architecture and training objectives in Section 3.2 and 3.3. Finally, in
Section 3.4, we elaborate on how Q&A can be applied to music rearrangement at
inference time.

###  3.1 Data Representation

####  3.1.1 Multi-Track Music

Given multi-track music $x$ with $N$ tracks, our model aims to reconstruct
each track $x_{n}$, where $n=1,2,\cdots,N$, from a track-wise condensed
mixture $x_{\mathrm{mix}}$. We represent $x_{n}$ in the modified piano-roll
format proposed by Wang et al. (2020b), and $x$ as an $N$-track collection.
Formally,

$x=x_{1:N}\coloneqq\\{x_{n}\\}_{n=1}^{N},$ (1)

where individual track $x_{n}$ is a $P\times T$ matrix. $P=128$ represents 128
MIDI pitches, and $T$ is the time dimension. Each data entry $(p,t)$ of
$x_{n}$ is an integer value representing note duration on the onset positions.
The condensed mixture $x_{\mathrm{mix}}$ is also a $P\times T$ matrix where
each entry is the position-wise maximum value across $N$ tracks. In this
paper, we consider 2-bar (8-beat) music data segments in $\frac{4}{4}$ time
signature quantized at $\frac{1}{4}$ beat unit, deriving $T=32$ time steps for
each music sample. We also focus on composition-level aspects while
disregarding performance-level dynamics like MIDI velocity.

####  3.1.2 Track Function

We define the function of each track $x_{n}$ as its texture density features
computed from the modified piano-roll format. Specifically, we define
descriptors of pitch function $f^{\mathrm{p}}(\cdot)$ and time function
$f^{\mathrm{t}}(\cdot)$ as follows:

$\displaystyle f^{\mathrm{p}}(x_{n})$
$\displaystyle=\mathrm{rowsum}(\mathbf{1}_{\\{x_{n}>0\\}})/T,$ (2)
$\displaystyle f^{\mathrm{t}}(x_{n})$
$\displaystyle=\mathrm{colsum}(\mathbf{1}_{\\{x_{n}>0\\}})/P,$ (3)

where $\mathbf{1}_{\\{\cdot\\}}$ is the indicator function expressing
individual note onset entries as 1. $\mathrm{rowsum}(\cdot)$ and
$\mathrm{colsum}(\cdot)$ each sums up one dimension, resulting in a $P$-D and
$T$-D vector, respectively. $f^{\mathrm{p}}(x_{n})$ is essentially a pitch
histogram, which is related to key, chord, and the pitch range of $x_{n}$.
$f^{\mathrm{t}}(x_{n})$ indicates voice densities of $x_{n}$ and is related to
rhythmic patterns and grooves. Each vector is normalized to $[0,1]$.

###  3.2 Model Architecture

Figure 2 shows the overall architecture of our model consisting of four key
components: 1) a mixture encoder, 2) a function query-net, 3) a track
separator, and 4) a track decoder.

####  3.2.1 Mixture Encoder

As $x_{\mathrm{mix}}$ is a single-track polyphony, we use the encoder module
of PianoTree VAE Wang et al. (2020c), the state-of-the-art polyphonic
representation learning model, to encode a 256-D mixture representation
$z_{\mathrm{mix}}^{x}$. The PianoTree encoder first converts
$x_{\mathrm{mix}}$ to a compact and ordered note event format, where each
event contains pitch and duration attributes. It then applies a pitch-wise bi-
directional GRU to summarize concurrent notes at time step $t$ to an
intermediate representation $\mathrm{simu\\_note}_{t}$. On top of
$\mathrm{simu\\_note}_{1:T}$, it further applies a time-wise GRU to encode the
full mixture representation $z_{\mathrm{mix}}^{x}$. The encoding process of
PianoTree VAE reflects hierarchical musical understanding from note via chord
to grouping, which is interpretable and has proved beneficial for a range of
downstream generation tasks Yi et al. (2022); Wuerkaixi et al. (2021); Zhao et
al. (2022); Wang et al. (2022).

####  3.2.2 Function Query-Net

The function query-net consists of two VAEs that encode 128-D representations
${z^{\mathrm{p}(x)}_{n}}$ and ${z^{\mathrm{t}(x)}_{n}}$ for track functions
$f^{\mathrm{p}}(x_{n})$ and $f^{\mathrm{t}}(x_{n})$, respectively. The pitch
and time function encoders each consist of a 1-D convolutional layer with
kernel size 12 and 4, respectively. Both are followed by ReLU activation Nair
and Hinton (2010) and 1-D max-pooling with kernel size 4 and stride 4. The
decoders consist of two fully-connected layers with ReLU activation in
between.

It is noted that, with the encoder design, we leverage the translation
invariance property of convolution and the blurry effect of pooling Krizhevsky
et al. (2017) to discourage the separator from simply retrieving notes that
are implied in the track functions. By doing so, our model learns a general
style representation instead of the exact density values from the track
function. Similar method is also adopted in other VAE architectures to realize
disentanglement Wang et al. (2020b).

####  3.2.3 Track Separator

The track separator is a 2-layer Transformer encoder with 8 attention heads,
0.1 dropout ratio, and GELU activation Hendrycks and Gimpel (2016). The hidden
dimensions of self-attention $d_{\mathrm{model}}$ and feed-forward layers
$d_{\mathrm{ff}}$ are 512 and 1024, respectively. The input to the separator
is a sequence of $N+1$ latent codes including mixture $z_{\mathrm{mix}}^{x}$
and track functions $z^{f(x)}_{1:N}$, where $z^{f(x)}_{n}$ denotes the
concatenation $[z^{\mathrm{p}(x)}_{n};z^{\mathrm{t}(x)}_{n}]$ as a unified
track function representation. We also add learnable instrument embeddings to
the corresponding tracks. It is noted that Transformer is permutation-
invariant to the index of track functions so that no sequential assumption is
enforced. While the self-attention mechanism allows each track function as
query to attend to the mixture, it also encourages queries to attend to each
other for inter-track dependency. We denote the output of the Transformer as
$z^{x}_{1:N}$, which are the expected latent representations for individual
tracks $x_{1:N}$.

####  3.2.4 Track Decoder

We use the decoder module of PianoTree VAE to reconstruct each track $x_{n}$
from representation $z^{x}_{n}$. The decoder involves time- and pitch-wise
uni-directional GRUs, which mirror the structure of the encoder. To better
distinguish parallel tracks, we additionally provide the decoder with an
auxiliary time sequence of symbolic features, which are priorly predicted from
$z^{x}_{n}$. Specifically, we consider three auxiliary features: _pitch
centre_ , _voice intensity_ , and _rhythm_ , which can serve as strong hints
to determine if one track has _melodic_ , _harmonic_ , and _static_ properties
Couturier et al. (2022a, b). Both pitch centre and voice intensity are time
sequences of scalar values, which indicate centre pitch curve and voice number
progression of a track, both normalized to $[0,1]$. The rhythm feature is a
time sequence of onset probabilities, which represents the rhythmic pattern in
time. We use a uni-directional GRU to predict the symbolic features from
$z^{x}_{n}$ and feed them to the corresponding time steps of the time-wise GRU
in the PianoTree Decoder. Similar method is also applied for disentanglement
and reconstruction in Yang et al. (2019); Wang et al. (2022).

###  3.3 Training Objectives

The loss terms in our model include 1) reconstruction loss for each track,
track functions, and auxiliary symbolic features, and 2) KL loss between all
latent representations and standard normal distribution. Our model is
essentially a variational autoencoder since the loss function can be
formalized as the evidence lower bound (ELBO) of distribution $p(x)$, where
$x=x_{1:N}$ is the multi-track music.

The posterior distribution of the VAE is defined as the product of three
modules including mixture encoder, query-net encoder, and track separator:

$\displaystyle q_{\boldsymbol{\phi}}(\mathbf{z}\mid x):=\;$ $\displaystyle
q_{\phi_{1}}(z^{x}_{\mathrm{mix}}\mid
x_{\mathrm{mix}})\prod_{n=1}^{N}q_{\phi_{2}}(z^{f(x)}_{n}\mid f(x_{n}))$
$\displaystyle\prod_{n=1}^{N}q_{\phi_{3}}(z^{x}_{n}\mid
z^{x}_{\mathrm{mix}},z^{f(x)}_{1:N}),$ (4)

where ${\boldsymbol{\phi}}:=[\phi_{1},\,\phi_{2},\,\phi_{3}]$ denotes the
parameters of the three modules, and
$\mathbf{z}:=[z^{x}_{\mathrm{mix}},\,z^{x}_{1:N},\,z^{f(x)}_{1:N}]$. In
Equation (3.3), we collectively express two types of track functions as
$f(x_{n})$ for conciseness. It is noted that both $x_{\mathrm{mix}}$ and
$f(x_{n})$ are deterministically transformed from $x$ and hence are not
explicitly written in the left-hand side of Equation (3.3).

The reconstruction distribution is defined as the product of three
reconstruction terms of query-net decoder, symbolic feature decoder, and track
decoder:

$\displaystyle p_{\boldsymbol{\theta}}(x\mid\mathbf{z}):=$
$\displaystyle\prod_{n=1}^{N}p_{\theta_{1}}(f(x_{n})\mid
z^{f(x)}_{n})\prod_{n=1}^{N}p_{\theta_{2}}(r(x_{n})\mid z^{x}_{n})$
$\displaystyle\prod_{n=1}^{N}p_{\theta_{3}}(x_{n}\mid z^{x}_{n},r(x_{n})),$
(5)

where ${\boldsymbol{\theta}}:=[\theta_{1},\,\theta_{2},\,\theta_{3}]$ denotes
the parameters of the three decoders. $r(x_{n})$ denotes the auxiliary
symbolic features for track $x_{n}$. The $p_{\theta_{1}}$ term can be
interpreted as a regularizer to the overall output distribution
$p_{\boldsymbol{\theta}}(x\mid\mathbf{z})$.

Finally, the overall loss function is as follows:

$\displaystyle\mathcal{L}({\boldsymbol{\theta}},{\boldsymbol{\phi}};x)$
$\displaystyle=-\mathbb{E}_{\mathbf{z}\sim q_{\boldsymbol{\phi}}}\log
p_{\boldsymbol{\theta}}(x\mid\mathbf{z})$
$\displaystyle+\beta\>{\mathbb{K}}{\mathbb{L}}(q_{\boldsymbol{\phi}}(\mathbf{z}\mid
x)\;\|\;\mathcal{N}(\boldsymbol{0},\,\boldsymbol{1})),$ (6)

where $\beta$ is a balancing parameter Higgins et al. (2017).

###  3.4 Style Transfer

At inference time, Q&A can rearrange a multi-track source piece $x=x_{1:N}$
using the track system (style) from a reference piece $y=y_{1:M}$, which can
be freely selected. Let $\mathrm{Enc}^{\mathrm{m}}$,
$\mathrm{Enc}^{\mathrm{f}}$, $\mathrm{Sep}$, and $\mathrm{Dec}^{\mathrm{tk}}$
be the mixture encoder, function encoder, track separator, and track decoder,
respectively, the rearrangement process takes a pipeline as follows:

$\displaystyle z^{x}_{\mathrm{mix}}$
$\displaystyle=\mathrm{Enc}^{\mathrm{m}}(x_{\mathrm{mix}}),$ $\displaystyle
z^{f(y)}_{m}$
$\displaystyle=\mathrm{Enc}^{\mathrm{f}}(f(y_{m})),\;m=1,2,\cdots,M,$
$\displaystyle z^{x^{\prime}}_{1:M}$
$\displaystyle=\mathrm{Sep}(z^{x}_{\mathrm{mix}},\;z^{f(y)}_{1:M}),$
$\displaystyle x^{\prime}_{m}$
$\displaystyle=\mathrm{Dec}^{\mathrm{tk}}(z^{x^{\prime}}_{m}),\;m=1,2,\cdots,M,$
(7)

where $x^{\prime}=x^{\prime}_{1:M}$ is the rearrangement result. $x^{\prime}$
inherits the general harmonic structures from $x$, while also introducing
$y$’s track system with new textures, grooves, and track voicing played by a
different set of instruments.

In addition to manual selection, reference $y$ can be automatically searched
from a database ${\mathcal{D}}$. To guarantee faithful and natural
rearrangement results, we develop a simple heuristic to sample $y$ that is
“matched” with $x$ as follows:

$y=\underset{y\in{\mathcal{D}}}{\mathrm{argmax}}[\cos(f(y_{\mathrm{mix}}),f(x_{\mathrm{mix}}))+\alpha\cdot\epsilon_{y}],$
(8)

where $\cos(\cdot,\,\cdot)$ measures cosine similarity between the functions
(essentially, texture densities) of mixture $y_{\mathrm{mix}}$ and
$x_{\mathrm{mix}}$, $\epsilon_{y}\sim{\mathcal{N}}(0,\,1)$ is a noise term for
balancing with generality, and $\alpha$ is a balancing parameter. In cases
when $y$ and $x$ are very dissimilar, our model robustly follows $x$’s harmony
and $y$’s texture and voicing in a general sense of style transfer.

##  4 Experiments

###  4.1 Dataset

Our model is trained on Slakh2100 Manilow et al. (2019) and POP909 Wang et al.
(2020a) datasets. In specific, Slakh2100 contains 2K MIDI files of multi-track
music, most of which are in pop style. Instruments in Slakh2100 are
categorized into 34 classes (while co-instrument tracks are not merged) and
each piece contains at least one track of piano, guitar, bass, and drum. In
our experiment, we discard the drum track because it does not follow the
standard 128-pitch protocol used in other tracks. POP909 is a dataset of 1K
pop songs in piano arrangement created by professional musicians. Each piece
consists of three piano tracks for vocal melody, lead instrument melody, and
piano accompaniment, respectively. By jointly training our model on both
datasets, our model can rearrange multi-track music to piano and vice versa.

###  4.2 Training

For training Q&A, we use the official training split of Slakh2100 while
randomly splitting POP909 (at song level) into training, validation, and test
sets with a ratio of 8:1:1. We further augment training data by transposing
each piece to all 12 keys. Our model comprises 19M learnable parameters and is
trained with a mini-batch of 64 2-bar segments for 30 epochs on an RTX A5000
GPU with 24GB memory. We use Adam optimizer Kingma and Ba (2014) with a
learning rate from 1e-3 exponentially decayed to 1e-5. We apply teacher
forcing Toomarian and Barhen (1992) for the decoder GRUs in PianoTree VAE with
a rate from 0.8 to 0. For the parameter $\beta$ in Equation (3.3), we apply KL
annealing following Wang et al. (2022) and set $\beta$ increasing from 0 to
0.5 for $z^{f(x)}_{n}$ and from 0 to 0.01 for the other two factors.

###  4.3 Rearrangement Showcase

An 8-bar rearrangement example (by processing every 2 bars independently) is
shown in Figure 3. In specific, this is an orchestration example, where we use
Q&A to rearrange a piano piece into multi-track music. The piano source $x$ is
from POP909 while we sample reference $y$ of the same length from Slakh2100
following Equation (8) with $\alpha=0.2$. We add $f(x_{\mathrm{mel}})$, the
function of $x$’s melody track, to $y$’s track functions as an additional
query to guarantee the preservation of the theme melody. Meanwhile, we conduct
posterior sampling over $z^{x^{\prime}}_{\mathrm{mel}}$ to encourage melody
improvisation.

In this example, our model rearranges the piano piece into 11 tracks with
coherent and delicate multi-track textures. Among the 11 tracks, guitar and
organ are each used twice for melodic and harmonic purposes, respectively. Our
model preserves the original harmony quite faithfully. Particularly, it
captures the added chord notes in $x$ (highlighted by red dotted lines in
Figure 3) and retains the tension from the original piece. At the same time,
it introduces new groove patterns, bass lines, lead instrument melodies, and a
theme melody variation to reconceptualize the piece with more creativity.

Figure 3: An orchestration example for song_283 from POP909 by our proposed
Q&A model. The result has 11 tracks with varied instruments. Annotations
illustrate that the rearrangement is both faithful and creative with a
delicate multi-track structure.

###  4.4 Subjective Evaluation on Rearrangement

Based on composition style transfer, Q&A is a unified solution for a range of
music rearrangement tasks. In this paper, we focus on orchestration, piano
cover generation, and re-instrumentation. For evaluation, we introduce three
existing models as baselines for each of the three tasks as follows:

BL-Orch.: We introduce Arranger by Dong et al. (2021) as our baseline for the
orchestration task. We select the BiLSTM variant pre-trained on Lakh MIDI
dataset Raffel (2016), which is a superset of Slakh2100 that we use.
Orchestration by Arranger is a note-by-note mapping process, where each note
in the piano source is mapped to a multi-track target by assigning instruments
under a classification framework.

BL-Pno.: We introduce _Poly-Dis_ by Wang et al. (2020b) as our baseline for
the piano cover generation task. This model is pre-trained on POP909 and is
also based on style transfer. Specifically, it can generate piano cover for a
multi-track source piece by reconceptualizing its chord progression using the
texture from a piano reference. In our case, we provide Poly-Dis with the same
piano reference as our model and extract the chord progression of the source
music using the algorithm in Jiang et al. (2019).

BL-ReIns.: We introduce the model by Hung et al. (2019) as our baseline for
the re-instrumentation task. This model rearranges a source piece using the
synthesized audio timbre feature from a reference piece as instrumentation
style. We train this model on Slakh2100 using both the MIDI and the aligned
audio that is synthesized using professional-level sample-based virtual
instruments Manilow et al. (2019).

Besides the baselines, we also introduce three variants of our model to
analyze the impact of each key component. Specifically, Q&A-T uses only time
function as query to rearrange a piece. Q&A-P, on the other hand, uses pitch
function only. The final variant Q&A w/o Ins. uses both functions but is
trained without instrument embedding.

####  4.4.1 Evaluation Details

We invite participants to subjectively evaluate the rearrangement quality of
all models through a double-blind online survey. Our survey consists of 15
rearrangement sets, each of which contains one original source piece followed
by five rearrangement samples (four by our model variants and the rest by one
of the baselines). Among the 15 sets, there are 5 for piano cover generation,
orchestration, and re-instrumentation, respectively. The original piece $x$ is
an 8-bar musical phrase randomly selected from the validation/test set of
either POP909 or Slakh2100 depending on the task. The reference piece $y$ is
sampled from the other dataset following Equation (8), where we set
$\alpha=0.2$. For re-instrumentation, both $x$ and $y$ are in Slakh2100 but
from different splits (validation and test sets, respectively). We use the
same $y$ for each model that requires a reference piece for style transfer.

In our survey, we request each participant to listen to 5 rearrangement sets
and evaluate each sample. Both the set order and the sample order in each set
are randomized. The evaluation is based on a 5-point scale from 1 (very low)
to 5 (very high) for four criteria as follows:

  * •

DOA: The degree of arrangement. A low DOA refers to a note-by-note copy-paste
from the original music, while a high DOA means the music is appropriately
restructured to fit the new track system and instruments.

  * •

Creativity: How creative the rearrangement is.

  * •

Naturalness: How likely a human arranger creates it.

  * •

Musicality: The overall musicality.

####  4.4.2 Overall Rearrangement Performance

A total of 26 participants (8 females and 18 males) with various musical
backgrounds have completed our survey. We first show the statistical results
for _overall_ rearrangement performance disregarding the specific tasks. As
shown in Figure 4, the height of each bar represents the mean rating value and
the error bar represents the standard error computed via within-subject
(repeated-measures) ANOVA Scheffe (1999). Among our model variants, Q&A-T
queries the mixture by time function only, and Q&A w/o Ins. has no instrument
embedding. Both models essentially have fewer constraints during training and
hence can produce more diverse results, which may explain the higher ratings
on DOA and Creativity for both models. However, such results can also be less
natural or musical. On the other hand, Q&A-P uses pitch function only and
yields results inferior to other variants. This finding shows that pitch
function alone is not sufficient to capture track structures in multi-track
music. Indeed, pop music (at least in our datasets) is generally better
characterized in grooves than in chords, as the latter can often fit in a few
off-the-shelf template progressions. In terms of Naturalness and Musicality,
our standard Q&A model makes a better balance and acquires significantly
better results (p-value $p<0.01$) than all variants and the baselines
ensemble.

####  4.4.3 Task-Specific Performance

We are also interested in our model’s performance on each concrete
rearrangement task. As shown in Figure 5, we show our model’s _task-specific_
ratings (top in four variants) on the same set of criteria in comparison to
corresponding baseline models. We notice that BL-Orch. earns the highest
rating for Naturalness in the orchestration task, which is not surprising
because it adopts a note-by-note mapping strategy that virtually reproduces
the original human-created music. Accompanied by this strategy is a lower
degree of orchestration (DOA) and Creativity. On the other hand, our model
demonstrates a more balanced and superior performance. It also outperforms BL-
Orch. in Musicality as it can introduce more diversified instruments and
properly rearrange the source music with new texture and voicing. In
particular, we report a significantly better performance (p-values $p<0.05$)
of our model in Musicality than all baselines in all three tasks.

Figure 4: Evaluation on overall rearrangement performance.

###  4.5 Objective Evaluation on Voice Separation

One may wonder if the exceptional performance of our model in creativity and
musicality sacrifices the faithfulness to the original music. To this end, we
conduct an additional experiment on the task of voice separation and compare
our model with note-by-note decision models — a BiLSTM and a Transformer
encoder tailored for this task in Dong et al. (2021). Specifically, voice
separation is a special case of orchestration, where we only aim to separate a
mixture into individual voicing tracks without any creative factor. Note that,
in such a case, note-by-note classification methods have a natural advantage
over representation learning based methods because the latter gives less
importance to accurate control on low-level tokens. Still, the faithfulness of
our model can be validated if it can also tackle this problem.

In voice separation, since the goal is to separate individual tracks, the
ground-truth track functions cannot be the model input. Hence we introduce a
new variant Q&A-V, which applies an additional GRU decoder to infer function
representations $z^{f(x)}_{1:N}$ from mixture representation
$z_{\mathrm{mix}}^{x}$, and then generate each track with inferred track
functions. In our case, $N=4$ is preset and the inference process is conducted
from high voice to low voice autoregressively. We load the rest part of the
model with pre-trained parameters from standard Q&A and fine-tune the whole
model on string quartets in MusicNet Thickstun et al. (2017) and Bach chorales
in Music21 Cuthbert and Ariza (2010), respectively. We process the data into
8-beat segments irrespective of time signature. At test time, if a certain
note in the mixture is not recalled by our model, we look for its nearest-
neighbour note that is generated and assign its voice. If two note assignments
form polyphonic voice, we then re-assign the note with least added distance to
its second-nearest voice, which is a simple greedy-based rule. As both
datasets are tiny and prone to unbalanced train-test split, we evaluate our
model by 10-fold cross validation.

We show the test results (percentage accuracy) in Table 1. Compared to the
baselines, our Q&A-V model yields generally comparable results, although with
a noticeable gap on Bach chorales. Specifically, Bach chorales come with very
regular and transparent counterpoints, which are a good fit for note-by-note
classification frameworks to separate voices. On the other hand, string
quartets have much more complex and even overlapped voices that are harder to
separate. For this case, our model yields highly competitive performance in
general. When entry hints are provided, our model achieves the best with a
good margin to both baselines.

Figure 5: Evaluation on task-specific rearrangement performance. Model | Chorales | Quartets
---|---|---
Q&A-V | 94.84† | 73.47†
Transformer | 96.81 | 58.86
BiLSTM | 97.13 | 74.38
Q&A-V (+ entry hints) | 95.11† | 78.71†
Transformer (+ entry hints) | 93.81 | 56.72
BiLSTM (+ entry hints) | 97.39 | 71.51
Table 1: Objective evaluation on voice separation comparing to note-by-note
architectures. We use † to denote test results under 10-fold cross validation.
Baseline results are from Dong et al. (2021).

##  5 Conclusion

In conclusion, we contribute Q&A, a novel query-based framework for multi-
track music rearrangement. The main novelty lies first in our application of a
style transfer methodology to interpret the general rearrangement problem. By
defining and utilizing track functions, we effectively capture the texture and
voicing structure of multi-track music as composition style. Under a self-
supervised query system, the number of tracks and instruments to rearrange a
piece is virtually unconstrained. Q&A serves as a unified solution for piano
cover generation, orchestration, re-instrumentation, and voice separation.
Extensive experiments prove that it can both creatively rearrange a piece and
faithfully conserve the essential structures. We believe that our
contributions will inspire further advancements in computer music research,
opening doors to broader possibilities for universal music co-creation.

## References

  * Couturier et al. [2022a] Louis Couturier, Louis Bigo, and Florence Levé.  Annotating symbolic texture in piano music: a formal syntax.  In Proceedings of the 19th Sound and Music Computing Conference, pages 577–584, 2022.
  * Couturier et al. [2022b] Louis Couturier, Louis Bigo, and Florence Levé.  A dataset of symbolic texture annotations in mozart piano sonatas.  In Proceedings of the 23rd International Society for Music Information Retrieval Conference, pages 509–516, 2022.
  * Crestel and Esling [2017] Léopold Crestel and Philippe Esling.  Live orchestral piano, a system for real-time orchestral music generation.  In Proceedings of the 14th Sound and Music Computing Conference, pages 434–442, 2017.
  * Crestel et al. [2017] Léopold Crestel, Philippe Esling, Lena Heng, and Stephen McAdams.  A database linking piano and orchestral MIDI scores with application to automatic projective orchestration.  In Proceedings of the 18th International Society for Music Information Retrieval Conference, pages 592–598, 2017.
  * Cuthbert and Ariza [2010] Michael Scott Cuthbert and Christopher Ariza.  Music21: A toolkit for computer-aided musicology and symbolic music data.  In Proceedings of the 11th International Society for Music Information Retrieval Conference, pages 637–642, 2010.
  * Dai et al. [2018] Shuqi Dai, Zheng Zhang, and Gus G Xia.  Music style transfer: A position paper.  arXiv preprint arXiv:1803.06841, 2018.
  * Donahue et al. [2019] Chris Donahue, Huanru Henry Mao, Yiting Ethan Li, Garrison W. Cottrell, and Julian J. McAuley.  Lakhnes: Improving multi-instrumental music generation with cross-domain pre-training.  In Proceedings of the 20th International Society for Music Information Retrieval Conference, pages 685–692, 2019.
  * Dong et al. [2018] Hao-Wen Dong, Wen-Yi Hsiao, Li-Chia Yang, and Yi-Hsuan Yang.  Musegan: Multi-track sequential generative adversarial networks for symbolic music generation and accompaniment.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, pages 34–41, 2018.
  * Dong et al. [2021] Hao-Wen Dong, Chris Donahue, Taylor Berg-Kirkpatrick, and Julian J. McAuley.  Towards automatic instrumentation by learning to separate parts in symbolic multitrack music.  In Proceedings of the 22nd International Society for Music Information Retrieval Conference, pages 159–166, 2021.
  * Ens and Pasquier [2020] Jeff Ens and Philippe Pasquier.  Mmm: Exploring conditional multi-track music generation with the transformer.  arXiv preprint arXiv:2008.06048, 2020.
  * Hendrycks and Gimpel [2016] Dan Hendrycks and Kevin Gimpel.  Gaussian error linear units (gelus).  arXiv preprint arXiv:1606.08415, 2016.
  * Higgins et al. [2017] Irina Higgins, Loïc Matthey, Arka Pal, Christopher P. Burgess, Xavier Glorot, Matthew M. Botvinick, Shakir Mohamed, and Alexander Lerchner.  beta-vae: Learning basic visual concepts with a constrained variational framework.  In 5th International Conference on Learning Representations, Conference Track Proceedings. OpenReview.net, 2017.
  * Hsiao et al. [2021] Wen-Yi Hsiao, Jen-Yu Liu, Yin-Cheng Yeh, and Yi-Hsuan Yang.  Compound word transformer: Learning to compose full-song music over dynamic directed hypergraphs.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 178–186, 2021.
  * Huang and Yang [2020] Yu-Siang Huang and Yi-Hsuan Yang.  Pop music transformer: Beat-based modeling and generation of expressive pop piano compositions.  In Proceedings of the 28th ACM International Conference on Multimedia, pages 1180–1188, 2020.
  * Huang et al. [2019] Cheng-Zhi Anna Huang, Ashish Vaswani, Jakob Uszkoreit, Ian Simon, Curtis Hawthorne, Noam Shazeer, Andrew M. Dai, Matthew D. Hoffman, Monica Dinculescu, and Douglas Eck.  Music transformer: Generating music with long-term structure.  In 7th International Conference on Learning Representations. OpenReview.net, 2019.
  * Hung et al. [2019] Yun-Ning Hung, I-Tung Chiang, Yi-An Chen, and Yi-Hsuan Yang.  Musical composition style transfer via disentangled timbre representations.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 4697–4703, 2019.
  * Jiang et al. [2019] Junyan Jiang, Ke Chen, Wei Li, and Gus Xia.  Large-vocabulary chord transcription via chord structure decomposition.  In Proceedings of the 20th International Society for Music Information Retrieval Conference, pages 644–651, 2019.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * Krizhevsky et al. [2017] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Communications of the ACM, 60(6):84–90, 2017.
  * Lee et al. [2019] Jie Hwan Lee, Hyeong-Seok Choi, and Kyogu Lee.  Audio query-based music source separation.  In Proceedings of the 20th International Society for Music Information Retrieval Conference, pages 878–885, 2019.
  * Liu et al. [2022] Jiafeng Liu, Yuanliang Dong, Zehua Cheng, Xinran Zhang, Xiaobing Li, Feng Yu, and Maosong Sun.  Symphony generation with permutation invariant language model.  In Proceedings of the 23rd International Society for Music Information Retrieval Conference, pages 551–558, 2022.
  * Manilow et al. [2019] Ethan Manilow, Gordon Wichern, Prem Seetharaman, and Jonathan Le Roux.  Cutting music source separation some slakh: A dataset to study the impact of training data quality and quantity.  In 2019 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, pages 45–49. IEEE, 2019.
  * Nair and Hinton [2010] Vinod Nair and Geoffrey E Hinton.  Rectified linear units improve restricted boltzmann machines.  In Proceedings of the 27th International Conference on Machine Learning, pages 807–814, 2010.
  * Nakamura and Sagayama [2015] Eita Nakamura and Shigeki Sagayama.  Automatic piano reduction from ensemble scores based on merged-output hidden markov model.  In Proceedings of the 41st International Computer Music Conference, 2015.
  * Nakamura and Yoshii [2018] Eita Nakamura and Kazuyoshi Yoshii.  Statistical piano reduction controlling performance difficulty.  APSIPA Transactions on Signal and Information Processing, 7, 2018\.
  * Payne [2019] Christine Payne.  Musenet.  https://openai.com/blog/musenet/, 2019.  Accessed: 2023-05-29.
  * Raffel [2016] Colin Raffel.  Learning-Based Methods for Comparing Sequences, with Applications to Audio-to-MIDI Alignment and Matching.  PhD thesis, Columbia University, USA, 2016.
  * Ren et al. [2020] Yi Ren, Jinzheng He, Xu Tan, Tao Qin, Zhou Zhao, and Tie-Yan Liu.  Popmag: Pop music accompaniment generation.  In Proceedings of the 28th ACM International Conference on Multimedia, pages 1198–1206, 2020.
  * Scheffe [1999] Henry Scheffe.  The analysis of variance, volume 72.  John Wiley & Sons, 1999.
  * Takamori et al. [2017] Hirofumi Takamori, Haruki Sato, Takayuki Nakatsuka, and Shigeo Morishima.  Automatic arranging musical score for piano using important musical elements.  In Proceedings of the 14th Sound and Music Computing Conference, pages 35–41, 2017.
  * Terao et al. [2022] Moyu Terao, Yuki Hiramatsu, Ryoto Ishizuka, Yiming Wu, and Kazuyoshi Yoshii.  Difficulty-aware neural band-to-piano score arrangement based on note-and statistic-level criteria.  In International Conference on Acoustics, Speech and Signal Processing, pages 196–200. IEEE, 2022.
  * Thickstun et al. [2017] John Thickstun, Zaïd Harchaoui, and Sham M. Kakade.  Learning features of music from scratch.  In 5th International Conference on Learning Representations. OpenReview.net, 2017.
  * Toomarian and Barhen [1992] Nikzad Benny Toomarian and Jacob Barhen.  Learning a trajectory using adjoint functions and teacher forcing.  Neural networks, 5(3):473–484, 1992.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pages 5998–6008, 2017.
  * Wang and Xia [2021] Ziyu Wang and Gus Xia.  Musebert: Pre-training music representation for music understanding and controllable generation.  In Proceedings of the 22nd International Society for Music Information Retrieval Conference, pages 722–729, 2021.
  * Wang et al. [2020a] Ziyu Wang, Ke Chen, Junyan Jiang, Yiyi Zhang, Maoran Xu, Shuqi Dai, and Gus Xia.  POP909: A pop-song dataset for music arrangement generation.  In Proceedings of the 21st International Society for Music Information Retrieval Conference, pages 38–45, 2020.
  * Wang et al. [2020b] Ziyu Wang, Dingsu Wang, Yixiao Zhang, and Gus Xia.  Learning interpretable representation for controllable polyphonic music generation.  In Proceedings of the 21st International Society for Music Information Retrieval Conference, pages 662–669, 2020.
  * Wang et al. [2020c] Ziyu Wang, Yiyi Zhang, Yixiao Zhang, Junyan Jiang, Ruihan Yang, Gus Xia, and Junbo Zhao.  PIANOTREE VAE: structured representation learning for polyphonic music.  In Proceedings of the 21st International Society for Music Information Retrieval Conference, pages 368–375, 2020.
  * Wang et al. [2022] Ziyu Wang, Dejing Xu, Gus Xia, and Ying Shan.  Audio-to-symbolic arrangement via cross-modal music representation learning.  In International Conference on Acoustics, Speech and Signal Processing, pages 181–185. IEEE, 2022.
  * Wuerkaixi et al. [2021] Abudukelimu Wuerkaixi, Christodoulos Benetatos, Zhiyao Duan, and Changshui Zhang.  Collagenet: Fusing arbitrary melody and accompaniment into a coherent song.  In Proceedings of the 22nd International Society for Music Information Retrieval Conference, pages 786–793, 2021.
  * Yang et al. [2019] Ruihan Yang, Dingsu Wang, Ziyu Wang, Tianyao Chen, Junyan Jiang, and Gus Xia.  Deep music analogy via latent representation disentanglement.  In Proceedings of the 20th International Society for Music Information Retrieval Conference, pages 596–603, 2019.
  * Yi et al. [2022] Li Yi, Haochen Hu, Jingwei Zhao, and Gus Xia.  Accomontage2: A complete harmonization and accompaniment arrangement system.  In Proceedings of the 23rd International Society for Music Information Retrieval Conference, pages 248–255, 2022.
  * Zhao et al. [2022] Jingwei Zhao, Gus Xia, and Ye Wang.  Domain adversarial training on conditional variational auto-encoder for controllable music generation.  In Proceedings of the 23rd International Society for Music Information Retrieval Conference, pages 925–932, 2022.
  * Zhu et al. [2018] Hongyuan Zhu, Qi Liu, Nicholas Jing Yuan, Chuan Qin, Jiawei Li, Kun Zhang, Guang Zhou, Furu Wei, Yuanchun Xu, and Enhong Chen.  Xiaoice band: A melody and arrangement generation framework for pop music.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2837–2846, 2018.