# Quantum Relaxation for Solving Multiple Knapsack Problems

Jin YAN1, Monit SHARMA1 Hoong Chuin LAU1,2 Corresponding author email:
<EMAIL_ADDRESS>1School of Computing and Information Systems, Singapore
Management University, Singapore  2Institute of High Performance Computing,
A*STAR, Singapore  Rudy RAYMOND3 Current affiliation is JP Morgan Chase & Co.,
USA 3IBM Quantum, IBM Japan

###### Abstract

Combinatorial problems are a common challenge in business, requiring finding
optimal solutions under specified constraints. While significant progress has
been made with variational approaches such as QAOA, most problems addressed
are unconstrained (such as Max-Cut). In this study, we investigate a hybrid
quantum-classical method for constrained optimization problems, particularly
those with knapsack constraints that occur frequently in financial and supply
chain applications. Our proposed method relies firstly on relaxations to local
quantum Hamiltonians, defined through commutative maps. Drawing inspiration
from quantum random access code (QRAC) concepts, particularly Quantum Random
Access Optimizer (QRAO), we explore QRAO’s potential in solving large
constrained optimization problems. We employ classical techniques like Linear
Relaxation as a presolve mechanism to handle constraints and cope further with
scalability. We compare our approach with QAOA and present the final results
for a real-world procurement optimization problem: a significant sized multi-
knapsack-constrained problem.

††preprint: APS/123-QED

##  I Introduction

The concept of leveraging quantum computers to generate approximate solutions
for NP-hard combinatorial problems dates back more than two decades, initially
introduced through quantum adiabatic eigenstate evolution [1]. This
foundational idea evolved into the Quantum Approximate Optimization Algorithm
(QAOA) [2] and Variational Quantum Eigensolver [3], which entails variational
optimization of quantum parameters [4]. With considerable interest in
harnessing quantum advantage for classical combinatorial problems, extensive
research has scrutinized the performance of QAOA [5, 6, 7]. These quantum
optimization techniques rely on establishing a bijective mapping between the
space of classical binary variables and logical basis states of a collection
of qubits, as originally outlined [2]. Within the QAOA framework, the cost
function optimized on a quantum computer typically features a classical
maximal eigenstate, which doesn’t strictly necessitate superposition and
entanglement for preparation. This contrasts with quantum many-body
Hamiltonians or quantum chemistry, where extremal eigenstates often exhibit
significant entanglement. In such cases, quantum computers benefit from a
natural memory advantage in storing the ground state.

While QAOA and VQE represent classical-quantum hybrid algorithms tailored for
near-term quantum devices capable of executing only shallow circuits, several
critical issues persist including the concerns of scalability. Given that QAOA
and VQE encode one classical bit into one qubit, the maximum number of qubits
for near-term quantum devices are limited. Consequently, the sizes of problem
instances that can be addressed are severely restricted. This limitation poses
a significant obstacle to the widespread applicability of these algorithms in
tackling larger-scale computational challenges.

QRAO [8] offers a solution to this challenge by encoding multiple classical
bits (typically three or fewer) into one qubit. By doing so, it facilitates
the generation of approximate solutions for combinatorial problems that seek
extremal eigenstates of local quantum Hamiltonians. These local quantum
Hamiltonians represent relaxations of the original combinatorial problems. For
each element in the image of a combinatorial cost function, it becomes
feasible to construct a quantum state with the same Hamiltonian expectation
value. This integration between classical combinatorial optimization and
quantum relaxation is a key feature of QRAO, making it a promising approach
for addressing complex optimization challenges using quantum-inspired
techniques [9]. Recent results of QRAO give hints of its robustness to quantum
noise [10], and its power to leverage quantum entanglement to obtain optimal
and better solutions [11]. However, the problems addressed by QRAO were all
unconstrained optimization.

In this study, our objective is to address a complex constrained supply chain
problem using QRAO. We will explore the effectiveness of QRAO in addressing
the inherent complexities of constrained supply chain problems, by solving a
Multiple Knapsack Problem (MKP) and comparing it with the well-studied QAOA
approach which is effective in solving unconstrained problems such as MaxCut
[13]. We will also be scaling up a real-world multiple knapsack-based Risk-
Aware Procurement Optimization problem involving $\geq$ $100$ variables and
demonstrating the prospect of combining QRAO with a classical method in
operations research, namely Linear Relaxation (LR)[14]. In this work, we aim
to merge quantum and classical computation to expand the utility of quantum
algorithms, enabling the solution of larger instances. Through this endeavor,
we demonstrate the scalability of QRAO and its efficacy in handling larger
problem sizes, where traditional methods like QAOA encounter limitations due
to the requirement of more qubits and memory.

The subsequent sections of this paper are structured as follows: In Section.
II we described the formulation for Multiple Knapsack Problem (MKP) and the
Risk-Aware Procurement Optimization problem, followed by Section. III where we
introduced the details of Quantum Random Access Encoding. In Sec. IV we
explain our approach on using Linear Relaxation and in Section. V we present
the results of the comparison of QAOA and QRAO on MKP problem and the
performance of QRAO with Linear Relaxation on Risk-Aware Procurement
Optimization problem. Finally in Section.VI we provide the concluding remarks
and the future outlook of the work.

This research will contribute valuable insights into the practical
applicability of quantum and classical hybrid optimization methods for complex
optimization challenges in finance and supply chain management.

##  II  Problem Settings

We consider two problem settings. First, the Multiple Knapsack Problem, which
is a strongly NP-hard problem with no fully polynomial-time approximation
scheme (FPTAS) (unlike the standard Knapsack Problem). On this problem, we
compare the QAOA and QRAO performance on multiple randomly generated test
instances. Next, we consider a real-world supply chain problem akin to an MKP
but with an added risk dimension. This is a significantly larger problem,
which cannot be solved via QAOA due to the current limit of hardware and
memory. The two problems are described as follows:

###  II.1 Multiple Knapsack Problem (MKP)

The Multiple Knapsack Problem(MKP) [15] is a generalization of the standard
knapsack problem (KP) from a single knapsack to $m$ knapsacks with (possibly)
different capacities. MKP involves allocating a subset of $n$ items to $m$
different knapsacks, aiming to maximize the total profit of the selected items
while ensuring that the capacity of each knapsack is not exceeded. This
problem finds applications in various fields such as naval and financial
management, where resources need to be efficiently allocated while considering
capacity constraints.

We are given $n$ items that need to be distributed among $m$ knapsacks, each
with a distinct capacity $c_{i}$ for $i=1,\ldots,m$. Each item $j$ has an
associated profit $p_{j}$ and weight $w_{j}$. The objective is to select $m$
disjoint subsets of items, ensuring that the items in subset $i$ fit within
the capacity $c_{i}$ of knapsack $i$ while maximizing the total profit of the
selected items. Formally, the MKP can be formulated as an Integer Linear
Programming (ILP) problem as follows:

Maximize: $\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n}p_{j}x_{ij}$ (1) Subject
to: $\displaystyle\sum_{j=1}^{n}w_{j}x_{ij}\leq c_{i},\quad i=1,\ldots,m$
$\displaystyle\sum_{i=1}^{m}x_{ij}\leq 1\quad j=1,\ldots,n,$ $\displaystyle
x_{ij}\in\\{0,1\\},\quad i=1,\ldots,m,\quad j=1,\ldots,n$

where $x_{ij}=1$ if item $j$ is assigned to knapsack $i$ , and $x_{ij}=0$
otherwise. It is usual to assume that the coefficients $p_{j},w_{j}$, and
$c_{i}$ are positive integers, and to avoid trivial cases we demand that:

$\displaystyle\max_{j=1,\ldots,n}w_{j}$
$\displaystyle\leq\max_{i=1,\ldots,m}c_{i}$ (2)
$\displaystyle\max_{i=1,\ldots,m}c_{i}$
$\displaystyle\leq\max_{j=1,\ldots,n}w_{j}$ $\displaystyle\sum_{j=1}^{n}w_{j}$
$\displaystyle\leq\max_{i=1,\ldots,m}c_{i}$

Note that we assume every item $j$ can fit into at least one knapsack;
otherwise, the item should be disregarded. Furthermore, if the second
inequality is breached, we can disregard the smallest knapsack, as it will not
accommodate any item. Lastly, the last inequality prevents a trivial solution
where all items can fit into the largest knapsack.

###  II.2 Risk-Aware Procurement Optimization

Optimization techniques have found wide application in addressing various
challenges within supply chain and logistics management, particularly in
mitigating risks and managing uncertainties. For instance, the classic
Newsvendor Problem [16] tackles the dilemma of making purchasing decisions
amidst uncertain demand, while disruptions in the supply chain can be managed
through portfolio approaches that assess the impact of delays across multiple
periods [17]. In scenarios where the ramifications of disruptions can be
precisely quantified, stochastic optimization techniques are typically
employed, solving deterministically across numerous generated scenarios [18].
However, when data limitations hinder the accurate realization of scenarios
for optimization, methods that directly incorporate risk into the optimization
process become essential. This can involve integrating risk minimization as a
joint objective alongside cost minimization or constraining cost minimization
problems with risk considerations [19].

Supply chain disruptions, whether stemming from unforeseen events like the
COVID-19 pandemic or more routine challenges such as labor disputes and
adverse weather conditions, pose significant risks to global companies. These
disruptions can lead to delays in deliveries, missed orders, and financial
losses. Addressing these challenges requires a comprehensive approach that
combines accurate risk quantification with cost-effective decision-making.
Following the methodology outlined in [20], we first establish a supplier risk
score metric by analyzing various data sources and identifying key risk
factors through factor analysis. With these risk scores in hand, we develop a
risk-constrained optimization model to formulate strategic procurement plans
for multinational computer manufacturing firms. We construct the following
simplified model for a typical procurement setting, with multiple parts to
procure from multiple suppliers.

We assign a risk score $r_{i}\in[0,9]$, for each supplier, $i$, derived from
Supplier Risk Analysis [20]. The per part cost for procuring part $j$ from
supplier $i$ is known in advance and denoted as $c_{i,j}$. For simplicity we
assume every supplier can produce all parts, in the case where a supplier
doesn’t produce certain parts, the respective costs will be set to a large
value. For each part $j$, there is a demand $d_{j}$ to be fulfilled by
sourcing from multiple suppliers and a risk tolerance level $\psi_{j}$. The
objective is to choose suppliers to fulfill the demands for each part at
minimized costs while managing the risk of suppliers within a given tolerance.
(4) represents the demand constraint and (5) ensures the weighted average
risks for each part are within the given thresholds.

Table 1: Notations used in the model Symbol |  Description
---|---
$i$ |  Supplier index from set $\mathcal{I}$
$j$ |  Part index from set $\mathcal{J}$
$y_{i,j}$ |  Number of part $j$ obtained from supplier $i$
$r_{i}$ |  Risk score for supplier $i$
$\psi_{j}$ |  Risk tolerance level for part $j$
$c_{i,j}$ |  Per part cost of procuring part $j$ from supplier $i$
$d_{j}$ |  Demand for part $j$

Following the notations given in Table 1, the following is the MILP
formulation:

$\text{Minimize:}\quad\sum_{i\in\mathcal{I}}\sum_{j\in\mathcal{J}}c_{i,j}y_{i,j}$
(3)

$\displaystyle\text{Subject to:}\quad\sum_{i\in\mathcal{I}}y_{i,j}$
$\displaystyle\geq d_{j}$ $\displaystyle\forall j\in\mathcal{J}$ (4)
$\displaystyle\sum_{i\in\mathcal{I}}r_{i}y_{i,j}$
$\displaystyle\leq\psi_{j}d_{j}$ $\displaystyle\forall j\in\mathcal{J}$ (5)

##  III Quantum Random Access Codes

The representation of $n$ qubits as a vector in $\mathbb{C}^{2n}$ may
initially suggest a higher information capacity compared to classical $n$
bits. However, it is worth noting that according to the Holevo bound [21],
transferring $n$-bit classical information without error requires $n$ qubits.
Nevertheless, if some errors are permissible, it becomes possible to encode
multiple classical bits into a single qubit using $(n,1,p)$-QRAC codes [22].
In this context, $(n,m,p)$-QRAC refers to quantum random access codes that
encode $n$ classical bits into $m$ qubits.

Definition 1: An $(n,1,p)$-QRA coding is a function that maps $n$-bit strings
$x\in\\{0,1\\}^{n}$ to $1$-qubit states $\rho_{x}$ satisfying the following
condition that for every $i\in\\{1,2,...,n\\}$ there exists a POVM

$E^{i}=\\{E_{0}^{i},E_{1}^{i}\\}$

such that

$\text{Tr}(E^{i}_{x_{i}}\rho_{x})\geq p$

The POVM $E^{i}$ is integral to the decoding process, enabling the extraction
of the $i$-th encoded bit $x_{i}$ from the measured encoded state $\rho_{x}$
with probability $p$. It’s important to note that $(n,1,p)$-QRA codes lack
significance when $p\leq\frac{1}{2}$, as $p=\frac{1}{2}$ implies random
selection of binary bits. Additionally, $(n,m,p)$-QRA coding, where $m\geq 2$,
follows a similar definition. Notably, specific instances include
$(2,1,0.85)$\- and $(3,1,0.78)$-QRA coding employed in QRAO [8]. However,
further extension to $(n,1,p)$ coding with $n\geq 4$ and $p>\frac{1}{2}$ is
impractical. This limitation arises from the geometric constraint where a
three-dimensional ball cannot be partitioned into sixteen non-empty regions
using only four planes [23].

Example 1: $(2,1,0.85)$-QRA Encoding

This encoding maps $x_{1},x_{2}\in\\{0,1\\}^{2}$ to a pure state
$\rho_{x_{1}x_{2}}=|\psi(x_{1}x_{2})\rangle\langle\psi(x_{1}x_{2})|$ ,
considering the map:

$(x_{1},x_{2})\mapsto\rho_{x_{1},x_{2}}:=\frac{1}{2}\bigg{(}I+\frac{1}{\sqrt{2}}\Big{(}(-1)^{x_{1}}X+(-1)^{x_{2}}Z\Big{)}\bigg{)}$
(6)

where

$\displaystyle|\psi(0,0)\rangle$
$\displaystyle=\cos\frac{\pi}{8}|0\rangle+\sin\frac{\pi}{8}|1\rangle$
$\displaystyle|\psi(0,1)\rangle$
$\displaystyle=\cos\frac{3\pi}{8}|0\rangle+\sin\frac{3\pi}{8}|1\rangle$
$\displaystyle|\psi(1,0)\rangle$
$\displaystyle=\cos\frac{5\pi}{8}|0\rangle+\sin\frac{5\pi}{8}|1\rangle$
$\displaystyle|\psi(1,1)\rangle$
$\displaystyle=\cos\frac{7\pi}{8}|0\rangle+\sin\frac{7\pi}{8}|1\rangle$

Then, this map is a $(2,1,0.85)$-QRA coding with the POVMs

$E^{1}=\\{|+\rangle\langle+|,|-\rangle\langle-|\\},\ E^{2}=\\{|0\rangle\langle
0|,|1\rangle\langle 1|\\},$

The measurements described above are conducted in both the $X$ and
computational bases. The $X$ basis measurement is specifically aimed at
decoding the first classical bit, whereas the computational basis measurement
is employed to decode the second classical bit. This dual measurement approach
facilitates the extraction of both classical bits encoded within the quantum
state.

Example 2: $(3,1,0.78)$-QRA Encoding Considering the map:

$\displaystyle(x_{1},x_{2},x_{3})\mapsto\rho_{x_{1},x_{2},x_{3}}$
$\displaystyle:=\frac{1}{2}\bigg{(}I+\frac{1}{\sqrt{3}}\Big{(}(-1)^{x_{1}}X+(-1)^{x_{2}}Y+(-1)^{x_{3}}Z\Big{)}\bigg{)}$
(7)

For every pair of $(x_{1},x_{2},x_{3}),\rho_{x_{1},x_{2},x_{3}}$ is a pure
state and can be written in the form
$\rho_{x_{1},x_{2},x_{3}}=|\psi(x_{1},x_{2},x_{3})\rangle\langle\psi(x_{1},x_{2},x_{3})|$,
where:

$\displaystyle|\psi(0,0,0)\rangle$
$\displaystyle=\cos\tilde{\theta}|0\rangle+e^{\frac{\pi\iota}{4}}\sin\tilde{\theta}|1\rangle$
(8) $\displaystyle|\psi(0,0,1)\rangle$
$\displaystyle=\sin\tilde{\theta}|0\rangle+e^{\frac{\pi\iota}{4}}\cos\tilde{\theta}|1\rangle$
$\displaystyle|\psi(0,1,0)\rangle$
$\displaystyle=\cos\tilde{\theta}|0\rangle+e^{\frac{-\pi\iota}{4}}\sin\tilde{\theta}|1\rangle$
$\displaystyle|\psi(0,1,1)\rangle$
$\displaystyle=\sin\tilde{\theta}|0\rangle+e^{\frac{-\pi\iota}{4}}\cos\tilde{\theta}|1\rangle$
$\displaystyle|\psi(1,0,0)\rangle$
$\displaystyle=\cos\tilde{\theta}|0\rangle+e^{\frac{3\pi\iota}{4}}\sin\tilde{\theta}|1\rangle$
$\displaystyle|\psi(1,0,1)\rangle$
$\displaystyle=\sin\tilde{\theta}|0\rangle+e^{\frac{3\pi\iota}{4}}\cos\tilde{\theta}|1\rangle$
$\displaystyle|\psi(1,1,0)\rangle$
$\displaystyle=\cos\tilde{\theta}|0\rangle+e^{\frac{-3\pi\iota}{4}}\sin\tilde{\theta}|1\rangle$
$\displaystyle|\psi(1,1,1)\rangle$
$\displaystyle=\sin\tilde{\theta}|0\rangle+e^{\frac{-3\pi\iota}{4}}\cos\tilde{\theta}|1\rangle$

where $\tilde{\theta}$ satisfies the condition
$(\cos(\tilde{\theta})^{2}=\frac{1}{2}+\frac{1}{2\sqrt{3}}>0.79$. Then this
map is a $(3,1,0.79)$-QRA codings with the POVMs

$\displaystyle E^{1}=\\{|+\rangle\langle+|,|-\rangle\langle-|\\},$
$\displaystyle\
E^{2}=\\{|+\iota\rangle\langle+\iota|,|-\iota\rangle\langle-\iota|\\}$
$\displaystyle E^{3}=$ $\displaystyle\\{|0\rangle\langle 0|,|1\rangle\langle
1|\\}$ (9)

The measurements described above are conducted in the $X$, $Y$, and
computational bases. Each measurement is specifically performed to decode the
corresponding classical bit encoded within the quantum state. By employing
these multiple bases, the decoding process enables the extraction of classical
information encoded within the quantum system.

Utilizing QRAO [8], multiple classical bits are compactly encoded into a
reduced number of qubits using Quantum Random Access Codes (QRACs), as
explained earlier. For instance, employing a $(3,1)$-QRAC, three classical
binary variables $x_{1}$, $x_{2}$, and $x_{3}$ are mapped to a single qubit
through the application of the Pauli $X$, $Y$, and $Z$ operators,
respectively. In comparison to methods like QAOA or VQE, QRAO boasts a
constant-factor space complexity advantage. Consequently, our focus in this
study lies on leveraging QRAO with a (3, 1)-QRAC approach.

The objective is to simplify the optimization problem by directing it towards
the exploration of the maximum eigenstate of the relaxed Hamiltonian
$H_{\text{relax}}$. To achieve this, we first map classical binary variables
into qubits through the construction of a relaxed Hamiltonian. This process
involves performing a graph coloring of the instance graph $G$, (made from the
objective problem) using the Large Degree First (LDF) method [24], with time
complexity of $O(|V(G)|\log|V(G)|+\text{deg}(G)|V(G)|)$, where $\text{deg}(G)$
represents the maximum degree of the graph $G$. Upon completion of the LDF
algorithm, the vertices are partitioned into the set $V_{c}$ associated with
the color $c\in C$. Here, the color of the $i$-th vertex $v_{i}$ is denoted as
color($i$). This partitioning satisfies the following condition:

$e_{i,j}\in E(G)\Rightarrow\text{color}(i)\neq\text{color}(j)$

Next, we allocate $\Big{\lceil}\frac{|V_{C}|}{3}\Big{\rceil}$ qubits for each
color $c\in C$, enabling up to three vertices to be assigned to a single
qubit. These vertices are ordered, and the Pauli operators $X$, $Y$, and $Z$
are assigned accordingly. Subsequently, we employ variational methods like VQE
to explore the maximum eigenstate of $H_{\text{relax}}$. Unlike the diagonal
structure of the original Hamiltonian, $H_{\text{relax}}$ comprises non-
classical states, characterized by superposition and entanglement, as its
maximal eigenstates. Consequently, the eigenstate obtained for
$H_{\text{relax}}$ cannot be directly linked to the classical solution due to
its quantum nature. Instead, it represents a quantum state corresponding to
the relaxed solution of the optimization problem, where the constraint that
the solution must be a binary vector is lifted. To recover the classical
solution, we employ quantum state rounding algorithms, as proposed in [8].

The first rounding algorithm, Pauli rounding, deciphers the encoded three
classical bits in each qubit using the POVM outlined in Eq. 9. Essentially,
this procedure involves measuring the $j$-th qubit with sufficient
repetitions, determining the majority measurement outcome, and assigning it as
the rounded value of the corresponding classical bit. However, Pauli rounding
may encounter limitations when the relaxed state exhibits significant
entanglement, preventing its representation in the form of
$\rho_{1}\otimes\rho_{2}\otimes\ldots\otimes\rho_{n}$. In such cases, the
algorithm’s effectiveness may be compromised due to the oversight of
correlations among the qubits.

In contrast to Pauli rounding, the second rounding algorithm, known as Magic
Rounding, mitigates the aforementioned issue. This method aims to decode three
classical variables simultaneously from a single qubit. For a comprehensive
understanding of Magic Rounding, further details can be found in [8] and [12].

##  IV Proposed Approach

An integer linear program (ILP) consists of a linear program requiring
variables to be integers. ILPs serve as expressive tools for formulating
combinatorial optimization problems. Nonetheless, solving ILPs optimally is
NP-hard.

One standard method to find an approximate solution for a combinatorial
optimization problem is via Linear Relaxation:

  * •

Formulate the optimization problem as an ILP.

  * •

Derive a linear program (LP) from the ILP by relaxing the integrality
constraints on variables. This resulting LP termed a relaxation of the
original problem, retains the same objective function but operates over a
broader solution set, leading to $\textit{opt}(LP)\leq\textit{opt}(ILP)$ for
minimization problem.

  * •

Solve the LP optimally using an efficient linear programming algorithm and
rounding variables to integers by some rounding techniques.

In the current NISQ era, quantum algorithms still suffer from scaling to
large-size problems. In our approach, we apply linear relaxation as a method
to reduce the problem size. Given the LP relaxed solution, the binary decision
variables that are solved to extreme values, i.e. very close to 0 or 1, will
be rounded accordingly and fixed, leaving a reduced-size problem for QRAO to
tackle.

##  V Results

We conducted initial investigations to ascertain the optimal ansatz and
associated parameters for leveraging $(3,1,p)-$QRAO by solving a simpler
version of our problem. All experiments are conducted with Qiskit’s [25]
AerSimulator.

Notably, our findings consistently favored the EfficientSU2 ansatz employing
full entanglement over alternatives such as PauliTwoDesign and RealAmplitudes.
This preference stems from the intrinsic characteristics described in Eq. 8,
where we see that $(3,1,p)-$QRAC has complex amplitudes. In contrast, the
RealAmplitudes ansatz exclusively addresses real-valued parameters. The
superiority of EfficientSU2, denoted by its designation, lies in its design
tailored for hardware efficiency within SU(2) 2-local circuits. These circuits
comprise layers of single-qubit operations interconnected by SU(2) and CX
entanglements, where SU(2) denotes the special unitary group of degree $2$.
Such circuits are characterized by $2\times 2$ unitary matrices with
determinant $1$, exemplified by the Pauli rotation gates.

| EfficientSU2 | PauliTwoDesign | RealAmplitudes
---|---|---|---
Reps. | Circ. | Full | Linear | Circ. | Full | Linear | Circ. | Full | Linear
0 | 27 | 30 | 33 | 20 | 19 | 18 | 0 | 0 | 0
1 | 18 | 5 | 2 | 4 | 9 | 9 | 0 | 0 | 0
2 | 21 | 27 | 12 | 26 | 24 | 14 | 0 | 0 | 0
3 | 32 | 20 | 10 | 3 | 4 | 2 | 0 | 0 | 0
4 | 23 | 31 | 12 | 1 | 7 | 7 | 0 | 0 | 0
5 | 30 | 38 | 24 | 12 | 5 | 18 | 0 | 0 | 0
Table 2: Number of solved instances for various ansätze, employing different
types of entanglement, with increasing repetitions.

As observed in Table 2, for the $(3,1,p)$-QRAO scenario, the EfficientSU2
ansatz demonstrates superior performance with five repetitions and full
entanglement. Conversely, as previously discussed, the RealAmplitudes ansatz
exhibits notably poor performance in this context.

###  V.1 QAOA vs QRAO on Multiple Knapsack Problem

Subsequently, we conducted a comparative analysis between QAOA and
$(3,1,p)-$QRAO, evaluating their performances on $20$ randomly generated, non-
trivial (guaranteed by Eq. (2)) instances of the Multiple Knapsack Problem
(MKP). The problem sizes comprised a maximum of $20$ binary variables. In
QAOA, each variable necessitated one qubit, while QRAO utilized fewer qubits
due to compression as shown in Tab. (3) and Tab. (4) respectively.

Instance | # vars | # qubits | Optimal | QAOA Obj. | Opt. gap
---|---|---|---|---|---
1 | 13 | 13 | 20 | 20 | 0%
2 | 18 | 18 | 25 | 25 | 0%
3 | 17 | 17 | 15 | 15 | 0%
4 | 20 | 20 | 15 | 12 | 20%
5 | 15 | 15 | 20 | 20 | 0%
6 | 15 | 15 | 19 | 19 | 0%
7 | 16 | 16 | 17 | 17 | 0%
8 | 20 | 20 | 19 | 16 | 15.79%
9 | 14 | 14 | 19 | 19 | 0%
10 | 18 | 18 | 15 | 13 | 13.33%
11 | 16 | 16 | 9 | 8 | 11.11%
12 | 18 | 18 | 32 | 32 | 0%
13 | 19 | 19 | 14 | infeasible | N.A.
14 | 14 | 14 | 15 | 15 | 0%
15 | 17 | 17 | 15 | 15 | 0%
16 | 13 | 13 | 18 | 18 | 0%
17 | 16 | 16 | 14 | 11 | 21.43%
18 | 15 | 15 | 12 | 12 | 0%
19 | 14 | 14 | 12 | 12 | 0%
20 | 15 | 15 | 19 | 19 | 0%
Table 3: Multiple Knapsack Problem QAOA Results Instance | # vars | # qubits | Optimal | QRAO Obj. | Opt. gap
---|---|---|---|---|---
1 | 13 | 5 | 20 | 20 | 0%
2 | 18 | 6 | 25 | 25 | 0%
3 | 17 | 6 | 15 | 15 | 0%
4 | 20 | 7 | 15 | 13 | 13.33%
5 | 15 | 5 | 20 | 20 | 0%
6 | 15 | 5 | 19 | 19 | 0%
7 | 16 | 6 | 17 | 17 | 0%
8 | 20 | 7 | 19 | 19 | 0%
9 | 14 | 5 | 19 | 16 | 15.79%
10 | 18 | 6 | 15 | infeasible | N.A.
11 | 16 | 6 | 9 | 5 | 44.44%
12 | 18 | 6 | 32 | 32 | 0%
13 | 19 | 7 | 14 | 14 | 0%
14 | 14 | 5 | 15 | 15 | 0%
15 | 17 | 6 | 15 | 15 | 0%
16 | 13 | 5 | 18 | 18 | 0%
17 | 16 | 6 | 14 | 14 | 0%
18 | 15 | 5 | 12 | 12 | 0%
19 | 14 | 5 | 12 | 12 | 0%
20 | 15 | 5 | 19 | 9 | 52.63%
Table 4: Multiple Knapsack Problem QRAO Results

In QAOA, we employed the default QAOAAnsatz, while in $(3,1,p)-$QRAO, we used
the EfficientSU2 ansatz with full entanglement, based on the findings
presented in Tab. 2. In both the cases, we used COBYLA as the classical
optimizer. The rounding scheme employed for QRAO adhered to the Magic Rounding
method.

The optimal solutions’ objective values, obtained by CPLEX, is used to compare
with the solutions obtained from QAOA/QRAO. The optimality gap is the absolute
difference between the solved objective value and the optimal objective value,
over the optimal objective value in percentage.

The results in Tab. 5 is an overall summary for Tab. 3 and Tab. 4, which
showed a slightly better performance for QRAO.

Method |  Feasible |  Optimal
---|---|---
QAOA |  $95\%$ |  $70\%$
QRAO |  $95\%$ |  $75\%$
Table 5: Multiple Knapsack Problem performance comparison of QAOA vs QRAO
results

###  V.2 QRAO with Linear Relaxation on Risk-Aware Procurement Optimization
Problem

We generated multiple random instances of the Risk-Aware Procurement
Optimization problem, each featuring approximately $100$ binary variables. The
sheer scale of these problems surpasses the current hardware limitations of
QAOA, rendering them challenging to tackle. Moreover, as the size of the
problems expands, the efficiency of QRAO is similarly impacted. To mitigate
these hurdles, we employed the Linear Relaxation technique as a strategic
response. We first tried with a random number of variables being fixed, and
compared it to $90\%$ of the variables being fixed. This approach aids in
navigating the complexities posed by the increasing dimensions of the problems
at hand, offering a viable pathway forward.

Method |  Feasible |  Optimal
---|---|---
QRAO-LR |  100% |  80%
QRAO-LR $90\%$ |  70% |  50%
Table 6: QRAOs’ (with Linear Relaxation) performance comparison

##  VI Conclusion & Future Outlook

This paper introduces a hybrid methodology aimed at addressing constraint
optimization problems prevalent in business contexts. It focuses on two
knapsack problem variants: the Multiple Knapsack Problem (MKP) and MKP
incorporating an additional risk dimension. Our analysis reveals that, despite
utilizing fewer qubits, QRAO achieves performance comparable to QAOA. Notably,
QRAO demonstrates an added advantage by enabling problem-solving for problems
ranging $\geq 100$ binary variables. This scalability advantage is
particularly significant as QAOA encounters challenges with errors stemming
from its high qubit and memory demands at such scales.

Moreover, our study demonstrates that by integrating the classical technique
of Linear Relaxation, we can achieve a further reduction in qubit demand. This
integration not only minimizes the resources needed but also enhances the
quality of the obtained results. By leveraging Linear Relaxation alongside
quantum approaches, our method offers a comprehensive solution framework that
optimizes both resource utilization and solution efficacy. This combination
underscores the versatility and effectiveness of our hybrid approach in
tackling complex optimization challenges across diverse business domains.

Expanding on this study, we aim to enhance our approach by integrating
stochastic elements into the problem formulation. This entails addressing
uncertainty surrounding both demand and supply variables [28]. Additionally,
we intend to explore alternative encoding schemes such as multi-basis encoding
(MBE) [26] and leverage polynomial space compression techniques [27].
Furthermore, we will investigate the potential of employing various classical
methods to streamline the problem-solving process. These adaptations are
anticipated to broaden the scope of our methodology and enhance its
effectiveness across diverse problem landscapes.

##  VII Acknowledgement

This research is supported by the National Research Foundation, Singapore
under its Quantum Engineering Programme 2.0 (NRF2021-QEP2-02-P01).

## References

  * [1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser. “Quantum Computation by Adiabatic Evolution.” (2000). arXiv:quant-ph/0001106.
  * [2] Edward Farhi, Jeffrey Goldstone, Sam Gutmann. “A Quantum Approximate Optimization Algorithm.” (2014). arXiv:1411.4028 [quant-ph].
  * [3] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, Jeremy L. O’Brien. “A variational eigenvalue solver on a photonic quantum processor.” Nature Communications, vol. 5, no. 1, July 2014. http://dx.doi.org/10.1038/ncomms5213
  * [4] Edward Farhi, Jeffrey Goldstone, Sam Gutmann. “A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem.” (2015). arXiv:1412.6062 [quant-ph].
  * [5] Daniel J. Egger, Jakub Mareček, Stefan Woerner. “Warm-starting quantum optimization.” Quantum, vol. 5, p. 479, June 2021. http://dx.doi.org/10.22331/q-2021-06-17-479
  * [6] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, Mikhail D. Lukin. “Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices.” Physical Review X, vol. 10, no. 2, June 2020. http://dx.doi.org/10.1103/PhysRevX.10.021067
  * [7] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler, Swati Gupta. “Bridging Classical and Quantum with SDP initialized warm-starts for QAOA.” (2022). arXiv:2010.14021 [quant-ph].
  * [8] Bryce Fuller, Charles Hadfield, Jennifer R. Glick, Takashi Imamichi, Toshinari Itoko, Richard J. Thompson, Yang Jiao, Marna M. Kagele, Adriana W. Blom-Schieber, Rudy Raymond, Antonio Mezzacapo. “Approximate Solutions of Combinatorial Problems via Quantum Relaxations.” (2021). arXiv:2111.03167 [quant-ph].
  * [9] Ruho Kondo and Yuki Sato and Rudy Raymond and Naoki Yamamoto, Recursive Quantum Relaxation for Combinatorial Optimization Problems, arXiv:2403.02045 [quant-ph] (2024).
  * [10] Kentaro Tamura and Yohichi Suzuki and Rudy Raymond and Hiroshi C. Watanabe and Yuki Sato and Ruho Kondo and Michihiko Sugawara and Naoki Yamamoto, Noise Robustness of Quantum Relaxation for Combinatorial Optimization, arXiv: 2403.05153 [quant-ph] (2024).
  * [11] K. Teramoto and R. Raymond and H. Imai, The Role of Entanglement in Quantum-Relaxation Based Optimization Algorithms, IEEE International Conference on Quantum Computing and Engineering (QCE), (2023).
  * [12] Kosei Teramoto and Rudy Raymond and Eyuri Wakakuwa and Hiroshi Imai, Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions, arXiv:2302.09481 [quant-ph] (2023).
  * [13] Zhou, Leo and Wang, Sheng-Tao and Choi, Soonwon and Pichler, Hannes and Lukin, Mikhail D, Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices Physical Review X 10.2 (2020): 021067.
  * [14] G. B. Dantzig, “Discrete-Variable Extremum Problems,” Operations Research, vol. 5, no. 2, pp. 266-288, 1957. https://doi.org/10.1287/opre.5.2.266
  * [15] Hans Kellerer, Ulrich Pferschy, and David Pisinger. Multiple Knapsack Problems. In: Knapsack Problems. Springer Berlin Heidelberg, 2004, pp. 285–316. doi: 10.1007/978-3-540-24777-7_10
  * [16] Roshanak Mohammadivojdan, Yasemin Merzifonluoglu, Joseph Geunes. “Procurement portfolio planning for a newsvendor with supplier delivery uncertainty.” European Journal of Operational Research, vol. 297, no. 3, pp. 917-929, 2022. ISSN: 0377-2217. https://doi.org/10.1016/j.ejor.2021.05.026
  * [17] Tadeusz Sawik. “A portfolio approach to supply chain disruption management.” International Journal of Production Research, vol. 55, no. 7, pp. 1970-1991, 2017. Publisher: Taylor & Francis. https://doi.org/10.1080/00207543.2016.1249432
  * [18] Shabbir Ahmed, Alexander Shapiro. “The sample average approximation method for stochastic programs with integer recourse. Submitted for publication.” Science, vol. 12, Jan. 2002.
  * [19] A.T. Beck, W.J.S. Gomes, R.H. Lopez, et al. “A comparison between robust and risk-based optimization under uncertainty.” Structural and Multidisciplinary Optimization, vol. 52, pp. 479-492, 2015. https://doi.org/10.1007/s00158-015-1253-9
  * [20] Jonathan Chase, Jingfeng Yang, Hoong Chuin Lau. “Risk-Aware Procurement Optimization in a Global Technology Supply Chain.” In: Proceedings of the International Conf. on Computational Logistics, Year 2022, Springer-Verlag. https://doi.org/10.1007/978-3-031-16579-5_26
  * [21] A. S. Holevo. “The Capacity of quantum channel with general signal states.” IEEE Transactions on Information Theory, vol. 44, pp. 269–273, 1998. https://doi.org/10.1109/18.651037
  * [22] Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh Vazirani. “Dense Quantum Coding and Quantum Finite Automata.” Journal of the ACM, vol. 49, pp. 496-511, Jul. 2002. https://doi.org/10.1145/581771.581773
  * [23] M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, S. Yamashita. “(4,1)-Quantum random access coding does not exist—one qubit is not enough to recover one of four bits.” New Journal of Physics, vol. 8, no. 8, p. 129, Aug. 2006. https://dx.doi.org/10.1088/1367-2630/8/8/129
  * [24] Dominic J. A. Welsh, M. B. Powell. “An upper bound for the chromatic number of a graph and its application to timetabling problems.” Computational Journal, vol. 10, pp. 85-86, 1967. https://api.semanticscholar.org/CorpusID:123441383
  * [25] Qiskit contributors, Qiskit: An Open-source Framework for Quantum Computing 2023 https://dx.doi.org/10.5281/zenodo.2573505
  * [26] T. L. Patti, J. Kossaifi, A. Anandkumar, and S. F. Yelin, Variational Quantum Optimization with Multi-Basis Encodings, arXiv:2106.13304 [quant-ph] (2022).
  * [27] M. Sciorilli, L. Borges, T. L. Patti, D. García-Martín, G. Camilo, A. Anandkumar, and L. Aolita, Towards large-scale quantum optimization solvers with few qubits, arXiv:2401.09421 [quant-ph] (2024).
  * [28] Monit Sharma, Hoong Chuin Lau, Rudy Raymond. Quantum-Enhanced Simulation-Based Optimization for Newsvendor Problems. arXiv:2403.17389 [quant-ph] (2024).


# Duration-aware pause insertion using pre-trained language model for multi-
speaker text-to-speech

###### Abstract

Pause insertion, also known as phrase break prediction and phrasing, is an
essential part of TTS systems because proper pauses with natural duration
significantly enhance the rhythm and intelligibility of synthetic speech.
However, conventional phrasing models ignore various speakers’ different
styles of inserting silent pauses, which can degrade the performance of the
model trained on a multi-speaker speech corpus. To this end, we propose more
powerful pause insertion frameworks based on a pre-trained language model. Our
approach uses bidirectional encoder representations from transformers (BERT)
pre-trained on a large-scale text corpus, injecting speaker embeddings to
capture various speaker characteristics. We also leverage duration-aware pause
insertion for more natural multi-speaker TTS. We develop and evaluate two
types of models. The first improves conventional phrasing models on the
position prediction of respiratory pauses (RPs), i.e., silent pauses at word
transitions without punctuation. It performs speaker-conditioned RP prediction
considering contextual information and is used to demonstrate the effect of
speaker information on the prediction. The second model is further designed
for phoneme-based TTS models and performs duration-aware pause insertion,
predicting both RPs and punctuation-indicated pauses (PIPs) that are
categorized by duration. The evaluation results show that our models improve
the precision and recall of pause insertion and the rhythm of synthetic
speech.

Index Terms—  multi-speaker TTS, pause insertion, phrase break prediction,
phrasing, categorized pause insertion, BERT

##  1 Introduction

Human speakers usually insert silent pauses into speech to take a breath or
show better expression. There are two main types of silent pause: respiratory
pauses (RPs) [1, 2] and punctuation-indicated pauses (PIPs). The former is
inserted at word transitions without punctuation to utter long sentences
fluently, and the latter is inserted at punctuation marks following text
descriptions. Pause insertion in text-to-speech (TTS) systems, also known as
phrase break prediction and phrasing, is an essential part of making computers
and robots speak as fluently as human speakers.

Since people always insert PIPs at punctuation marks, most previous works on
phrasing have focused on the position prediction of RPs. Conventionally,
linguistic information including lexical features (e.g., part-of-speech tags)
and syntax features (e.g., distance from punctuation) is used for this task.
Machine learning methods are used in phrasing models, such as decision tree
algorithms [2, 3, 4, 5, 6, 7, 8], hidden Markov models [9, 10, 11], and
conditional random fields [3, 12]. Due to the development of natural language
processing (NLP) and deep learning technologies, word representations have
become the key linguistic feature. Moreover, recurrent neural networks (RNNs),
especially bidirectional long short-term memory (BiLSTM) [13], have become the
mainstream models [2, 14, 15, 16]. Bidirectional encoder representations from
transformers (BERT) [17], one of the well-known pre-trained language models
currently, also shows potential for this task. For example, Futamata et al.
have introduced features from pre-trained BERT in Japanese phrase break
prediction [16], and Abbas et al. have taken word-level BERT embeddings as the
input of a conventional phrasing model [18].

However, the related works have not considered that various speakers have
different styles of inserting RPs. Although some latent grammar and rules are
shared among speakers, such differences can significantly reduce the accuracy
of an RP insertion model when we train it using a multi-speaker corpus without
speaker information. In fact, we always have to train the model with a multi-
speaker corpus due to the sparse distribution of RPs. Furthermore, the speaker
difference can also affect the insertion of PIPs, as well as the duration of
the inserted pauses. For example, speakers do not always add a pause at every
punctuation mark when reading text, depending on context and their habits.

Besides, in practice, most mainstream TTS models (e.g., FastSpeech 2 [19] and
Glow-TTS [20]) mainly use phonemes as input. They treat all silent pauses as
one phoneme, which leads to the duration of all silent pauses in synthetic
speech following the same distribution and not being sufficiently
differentiated. From our observation in preliminary experiments, the longer
the synthetic speech, the worse the rhythm due to the lack of well-
differentiated pauses. Therefore, we expect the input of silent pause phonemes
with duration information to enable phoneme-based TTS models to predict more
accurate silent pauses.

This paper proposes two multi-speaker pause insertion models: the respiratory
pause insertion (RPI) model and the categorized pause insertion (CPI) model.
The architecture is based on BERT and BiLSTM. The RPI model is a phrasing
model that considers the speaker difference by adding a speaker embedding to
the hidden sequence output by BERT. It is used to show the improvement of pre-
trained BERT and speaker information on RP prediction. With this RPI model as
a basis, we further propose the CPI model for phoneme-based TTS models, in
which both RPs and PIPs are categorized by duration, and their position and
category are predicted. We present objective evaluations of phrasing accuracy
and subjective evaluations of synthetic speech from text with automatically
inserted RPs and PIPs. The results show that our models perform better than
the baseline [2] and bring better rhythm to synthetic speech. Speech samples
are available online111https://ydqmkkx.github.io/pause-insertion/.

##  2 Dataset

We constructed the dataset from LibriTTS [21], a multi-speaker English corpus
derived from the audiobooks on the LibriVox website222https://librivox.org.
LibriTTS includes plenty of long-form sentences containing multiple silent
pauses uttered by more than 2,000 speakers, and thus fits our purpose of
evaluating the performance of multi-speaker pause prediction.

First, we pre-processed the text. We converted all words to lowercase
subwords. In the case of multiple consecutive punctuation marks, we kept only
the first one for better cleaning and alignment. We used the Montreal Forced
Aligner (MFA) [22] to align text and speech and obtain pause durations.
Because MFA recognizes the silence at word transitions over 30 ms as silent
pauses, we regarded silent pauses over 30 ms at punctuation marks as PIPs and
those over 50 ms at word transitions without punctuation as RPs. We also kept
the sentences that did not contain RPs in our dataset.

Second, we categorized the silent pauses by duration through the Gaussian
mixture model-based method in [23]. The distribution of pause duration was
fitted with several Gaussian distributions, after which the cut-off points of
every two adjacent Gaussian distribution curves were found. For convenience,
the whole hundred numbers nearest to the value on the horizontal axis of each
cut-off point were used as the thresholds for categorization. We specified the
pauses as brief ($<$ 300 ms), medium (300–700 ms), or long ($>$ 700 ms).

Statistics of the dataset are shown in Table 1, in which tokens consist of
subwords and punctuation. Each token was annotated with the four types of
labels shown in Fig. 1. Labels with the format P-x (x is the type of pauses)
include information about the position of pauses. In P-RPs, the label “1”
means an RP appears after its corresponding subword. We only labeled the last
subword of a word as “1”. The labels of C-x represent the categories of
pauses. Category “0” means “no pause”, and categories “1”, “2”, and “3”
correspond to the brief, medium, and long pauses, respectively.

Fig. 1: An example of text pre-processing and label setting. ##: identifier of continuing subwords, P-x: position of x, C-x: category of x. Table 1: Statistics of the dataset. | Training | Validation | Test
---|---|---|---
Sentences | 404,307 | 10,000 | 10,000
Tokens | 9,098,772 | 225,700 | 225,638
Punctuation | 1,047,561 | 26,046 | 26,001
Speakers | 2,305 | 2,154 | 2,162
RPs (total) | 170,168 | 4,083 | 4,297
RPs (category 1) | 136,306 | 3,287 | 3,450
RPs (category 2) | 32,367 | 768 | 813
RPs (category 3) | 1,495 | 28 | 34
PIPs (total) | 861,544 | 21,329 | 21,354
PIPs (category 1) | 399,559 | 9,898 | 9,979
PIPs (category 2) | 325,327 | 8,060 | 7,953
PIPs (category 3) | 136,658 | 3,371 | 3,422
Fig. 2: Architectures of the baseline and proposed models.

##  3 Baseline Method

Klimkov et al. [2] provided the mainstream framework of a phrasing model based
on English audiobooks, which focused on long-form reading TTS and was
implemented as our baseline. The architecture of the baseline model is shown
in Fig. 2(a). The input word2vec embeddings are processed by BiLSTM projection
with peephole connection (BiLSTMP) [24] layers and splicing windows. The
splicing window stacks together seven frames before and after and feeds them
to the next layer. The model outputs the probability of the occurrence of a
pause after each token.

In our implementation, we used subword embeddings as the input (with the same
dimension as the word embeddings in the original paper) and replaced the
softmax function with the sigmoid function for consistency with our proposed
models.

##  4 Proposed Method

###  4.1 RPI model

The proposed RPI model (Fig. 2(b)) is inspired by [16]. As with the baseline
model, it predicts the position of RPs. BERT has demonstrated its unparalleled
ability to extract textual features in various NLP tasks, and our task is well
suited as its downstream task. However, it cannot receive and utilize speaker
information very well by itself. Hence, we use the encoder-decoder structure
and take BERT as the encoder. Two BiLSTM layers are then used to decode the
information from BERT and speaker embeddings, which are initialized randomly
and trained with the RPI model. The hidden sequence is the output of the last
layer in BERT.

The main purpose of the RPI model is to quantify the improvements brought by
the pre-trained BERT and speaker embeddings on phrasing.

###  4.2 CPI model

As presented in Fig. 1 and stated in Section 2, we categorized the silent
pauses into three categories according to their duration. Then when training
the TTS model, silent pauses in the dataset were represented as three marks.
For example, “sp”, which usually represents silent pauses in phonemes, was
divided into “sp1”, “sp2”, and “sp3”, corresponding to the three categories.

When converting a text sequence into a phoneme sequence during the inference
of TTS models to insert PIPs, a common approach is to convert several specific
types of punctuation into pause marks and ignore the other punctuation. This
approach is a little crude because punctuation pauses also need to be
predicted. To overcome this limitation, our CPI model (Fig. 2(c)) predicts
both RPs and PIPs (including their position and category) by using a multi-
task learning framework. The CPI model utilizes two sets of BiLSTM layers to
decode the hidden sequence from BERT and speaker embeddings that correspond to
the predictions of RPs and PIPs, as the two pauses are different in the
distributions of position and category. In our preliminary experiment, we used
the same decoder to make both predictions. In that case, the prediction
distribution of RPs was significantly influenced by that of PIPs, which led to
poor results because there are many more PIPs than RPs.

As shown in Fig. 2(c), in addition to the Category, the CPI model also outputs
the Probability of pause occurrence, because taking the predictive probability
of category 0 as that of pause occurrence is not very effective. Specifically,
the model first predicts Probability that represents the occurrence of pauses
and then outputs Category with the highest probability among categories 1–3.

##  5 Experimental Evaluations

###  5.1 Experimental configurations

Fig. 3: Precision-recall curves on RP position prediction. Table 2: Results of RP position prediction. | Precision | Recall | $\mathrm{F}_{0.5}$
---|---|---|---
RPI: bert-lstm (FT+spk) | 0.569 | 0.272 | 0.467
bert-lstm (spk) | 0.490 | 0.253 | 0.413
bert (FT) | 0.487 | 0.233 | 0.400
bert-lstm (FT) | 0.467 | 0.246 | 0.396
bert-lstm | 0.475 | 0.213 | 0.381
baseline (spk) | 0.446 | 0.209 | 0.364
baseline | 0.393 | 0.187 | 0.322

For the baseline model, the hidden size and projection size for each BiLSTMP
layer were 512 and 128, respectively. The dimension of subword embeddings was
300. For the proposed models, we configured the BERT as
BERTBASE333https://huggingface.co/bert-base-uncased and set the hidden size of
each BiLSTM layer to 512. The dimensions of the hidden sequence and speaker
embeddings were 768. The BERTBASE was pre-trained on BookCorpus [25], which
consists of unpublished books and English Wikipedia entries. We also used this
corpus to pre-train the subword embeddings by a Continuous Bag-of-Words (CBOW)
model [26]. When training the baseline and RPI models, we used the P-RPs label
shown in Fig. 1. Four labels, namely, P-RPs, C-RPs, P-PIPs, and C-PIPs, were
the targets of the four outputs of the CPI model. In labels C-RPs and C-PIPs,
category 0 represents no pause after the token, which can be viewed as a
placeholder for the convenience of training. The loss function was binary
cross-entropy (BCE) loss for Probability and weighted cross-entropy (WCE) loss
for Category. The weights of categories 1–3 in WCE loss function equaled the
total number of category 0 divided by their total number in the training set.
As an exception, we set the weight of category 3 of RPs to 1.0 due to its
sparseness.

During training, each mini-batch had 32 sentences. We used the Adam optimizer
[27] and set the initial value of the dynamic learning rate to $5\times
10^{-5}$. The learning rate dropped by 0.2 times when the model’s performance
on the validation set did not improve within 5000 iterations. We took 200,000
as the maximum iterations (about 16 epochs). The models that performed best on
the validation set during these iterations were saved to make comparisons. We
utilized the unbalanced F-score described in [2] for threshold selection:

$\displaystyle\mathrm{F}_{\beta}$
$\displaystyle=\left(1+\beta^{2}\right)\frac{\mathrm{Precision}\times\mathrm{Recall}}{\beta^{2}\times\mathrm{Precision}+\mathrm{Recall}}$
(1)

The maximal value of $\mathrm{F}_{\beta}$ that the model could achieve was
taken as a criterion for evaluation. It is preferable to skip RPs rather than
to insert them in inappropriate places [2], so we took 0.5 as the value of
$\beta$. For PIPs, we focused more on the recall and used $\mathrm{F}_{2}$.
From our point of view, the absence of some critical PIPs makes for long
utterances with bad rhythm.

###  5.2 Objective evaluations

####  5.2.1 RPI model

This objective evaluation was designed to explore and quantify the
improvements of the pre-trained BERT, fine-tuning of BERT, and introducing
speaker information on phrasing models. We made comparisons on the position
prediction of RPs. To examine the effect of adding speaker embeddings, we also
added the speaker embedding after the first splicing window layer of the
baseline model to take it as an encoder-decoder model, which we denote as
“baseline (spk)”. The whole structure of the proposed RPI model is denoted as
“bert-lstm (FT+spk)”. To determine the performance of the models under
different thresholds, we used precision-recall curves to show the results and
only kept the points in the curves whose both precision and recall values were
above 0.1. When calculating the precision and recall values for the multiple
subwords from one word, we counted only the last subword with the same rules
as setting labels. From the results shown in Fig. 3 and Table 2, we can find:

  * •

The BERT-based models performed better than the baseline models, which
suggests that the pre-trained BERT can provide more efficient textual features
than conventional word2vec models.

  * •

There were only slight differences between bert-lstm (FT) and bert (FT), which
means that without speaker embedding, BERT alone is capable of predicting the
position of RPs after fine-tuning.

  * •

When adding speaker embeddings, the curve of baseline (spk) was close to that
of bert-lstm, and the performance of bert-lstm (spk) even exceeded bert-lstm
(FT). These enhancements demonstrate the validity and generalizability of
using speaker embeddings and show that different speakers have different
styles for inserting RPs. For a large multi-speaker dataset, such differences
deserve attention and can significantly affect the accuracy of RP prediction
models.

  * •

bert-lstm (FT) obtained a bit higher precisions than bert-lstm for the same
recalls, which means that the fine-tuning of BERT leads to better performance
but not by much without speaker embedding. However, the BERT-based model with
speaker embeddings got a big boost from fine-tuning, which shows the need to
apply them together.

####  5.2.2 CPI model

Table 3 and Table 4 show the results of the proposed CPI model for position
prediction and category prediction of both pauses, respectively. It is clear
that the model retained the ability to predict the position of RPs, and
achieved a recall value over 0.99 for the relatively simple task of position
prediction of PIPs. In category prediction, the accuracy of category 2 was
lower than that of the other two categories, which suggests that there is
still some room for improvement in the choice of thresholds for
categorization.

Table 3: Results of position prediction of CPI. | Precision | Recall | $\mathrm{F}_{\beta}$
---|---|---|---
RPs | 0.575 | 0.261 | $\mathrm{F}_{0.5}=0.463$
PIPs | 0.848 | 0.996 | $\mathrm{F}_{2}=0.962$
Table 4: Confusion matrix of category prediction of RPs and PIPs.

| Prediction
---|---
Label | 1 | 2 | 3
1 | 2,565 | 885 | 0
2 | 300 | 513 | 0
3 | 14 | 20 | 0
(a) Prediction of RPs

| Prediction
---|---
Label | 1 | 2 | 3
1 | 6,155 | 1,766 | 2,058
2 | 2,258 | 3,186 | 2,509
3 | 335 | 352 | 2,735
(b) Prediction of PIPs

Table 5: Subjective performance of pause insertion models. *: the model takes unmatched speaker embedding as input. Method A | Score | Method B | p-value
---|---|---|---
RPI | 0.560 vs. 0.440 | FastSpeech2 | $<0.005$
RPI | 0.537 vs. 0.463 | Baseline | $<0.1$
CPI | 0.557 vs. 0.443 | Baseline | $<0.01$
RPI | 0.488 vs. 0.512 | CPI (Position) | 0.60
RPI | 0.460 vs. 0.540 | CPI | $<0.05$
RPI | 0.510 vs. 0.490 | RPI* | 0.62
CPI | 0.550 vs. 0.450 | CPI* | $<0.05$

###  5.3 Subjective evaluations

To explore the performance of our proposed models in multi-speaker TTS,
especially to show the improvement of inputting categorized pause phonemes, we
performed AB preference tests using FastSpeech 2 as our TTS model with HiFi-
GAN [28] as the vocoder. For RPI and CPI models, the thresholds of position
predictions were as stated in Section 5.1. We used “clean” subsets in the
LibriTTS corpus to train two TTS models with silent pause phonemes, one with
non-categorized pauses (“sp”), and one with categorized pauses (“sp1”, “sp2”,
and “sp3”). In total, we selected 16 speakers (eight men, eight women) with
good synthetic sound quality as the test speaker set in our evaluations.

To ensure the synthetic speech in our test contained sufficient RPs and PIPs,
we first selected long-form sentences with a total number of words and
punctuation marks between 50 and 60 from the test set. After this, 123
sentences were left, each of them including more than one RPs. These sentences
were then used in TTS synthesis, where one sentence corresponds to several
speakers. To prevent the sound quality from affecting the tests, we removed
any synthetic speech with bad quality and kept 277 text-speaker pairs.

To explore whether the listener could perceive if a pause insertion style did
not match the speaker, for each text-speaker pair, we utilized another speaker
embedding from the test speaker set to do the pause insertion and made the gap
as large as possible (denoted by * in Table 5). In addition, to show that the
improvement in CPI relative to RPI came more from inputting categorized pause
phonemes rather than from the extra position prediction of PIPs, we made CPI
only predict uncategorized pauses and denoted it as “CPI (Position)”. We asked
native listeners from Amazon Mechanical Turk to participate in the tests.
Every test was completed by 30 listeners, each of whom listened to ten pairs
of synthetic speech and was asked to choose the one with better rhythm.

We set seven tests. As shown in Table 5, we can find:

  * •

Listeners perceived the difference between RPI and Baseline to be
insignificant and were insensitive to the position variance of RPs between RPI
and RPI*. We believe this is due to the sparse distribution and short duration
of RPs. People only became aware of the absence of RP when listening to a long
sentence without a pause, where the position of RPs could not attract enough
attention.

  * •

The slight lead of RPI over Baseline could also be due to the fact that RPI
inserts more RPs with the same requirement of $\mathrm{F}_{\beta}$ value.

  * •

Listeners were more likely to recognize that CPI performed better than
Baseline and RPI. Coupled with the inability of the listeners to distinguish
significantly between RPI and CPI (Position), we can conclude that inputting
categorized pause phonemes to phoneme-based TTS models makes the rhythm of
synthetic speech better.

  * •

According to the CPI and CPI* pair, listeners were sensitive to the difference
arising from inserting different categories of pauses. Since the duration
variation of pauses is present in both RPs and PIPs, using other speaker
embeddings brings clear differences.

##  6 Conclusion

In this paper, we proposed a respiratory pause insertion model and a
categorized pause insertion model. The results of objective evaluations
demonstrated that the speaker information can bring a large improvement to
phrasing models trained with a multi-speaker dataset. The results of
subjective evaluations showed that by inserting categorized pauses, the
synthetic speech had better rhythm and was more consistent with the features
of the speaker. In future work, we plan to explore the effectiveness of
incorporating speaker embedding into the text-processing model of the TTS
system for other similar tasks.

## References

  * [1] G. Bailly and C. Gouvernayre, “Pauses and respiratory markers of the structure of book reading,” in _Proc. INTERSPEECH_ , Portland and U.S.A., 2012.
  * [2] V. Klimkov, A. Nadolski, A. Moinet, B. Putrycz, R. Barra-Chicote, T. Merritt, and T. Drugman, “Phrase break prediction for long-form reading TTS: Exploiting text structure information,” in _Proc. INTERSPEECH_ , Stockholm, Sweden, 2017, pp. 1064–1068.
  * [3] V. Keri, S. C. Pammi, and K. Prahallad, “Pause prediction from lexical and syntax information,” in _Proc. ICON_ , Hyderabad, India, 2007.
  * [4] A. Parlikar and A. W. Black, “A grammar based approach to style specific phrase prediction,” in _Proc. INTERSPEECH_ , Florence, Italy, 2011, pp. 2149–2152.
  * [5] O. Watts, J. Yamagishi, and S. King, “Unsupervised continuous-valued word features for phrase-break prediction without a part-of-speech tagger,” in _Proc. INTERSPEECH_ , Florence, Italy, 2011, pp. 2157–2160.
  * [6] N. Braunschweiler and R. Maia, “Pause prediction from text for speech synthesis with user-definable pause insertion likelihood threshold,” in _Proc. INTERSPEECH_ , San Francisco, U.S.A., 2016, pp. 3191–3195.
  * [7] Q. Shi, J. DanNing, M. FanPing, and Q. Yong, “Combining length distribution model with decision tree in prosodic phrase prediction,” in _Proc. INTERSPEECH_ , Antwerp, Belgium, 2007, pp. 454–457.
  * [8] Z. Zhang, F. Wu, C. Yang, M. Dong, , and F. Zhou, “Mandarin prosodic phrase prediction based on syntactic trees,” in _Proc. SSW_ , Sunnyvale, U.S.A., 2016, pp. 175–180.
  * [9] P. Bell, T. Burrows, and P. Taylor, “Adaptation of prosodic phrasing models,” in _Proc. Speech Prosody_ , Dresden, Germany, 2006.
  * [10] I. Read and S. Cox, “Stochastic and syntactic techniques for predicting phrase breaks,” _Computer Speech and Language_ , vol. 21, no. 3, pp. 519–542, 2007\.
  * [11] Q. Chen, Z.-H. Ling, C.-Y. Yang, and L.-R. Dai, “Automatic phrase boundary labeling of speech synthesis database using context-dependent HMMs and n-gram prior distributions,” in _Proc. INTERSPEECH_ , Dresden, Germany, 2015, pp. 1581–1585.
  * [12] Y. Qian, Z. Wu, X. Ma, and F. Soong, “Automatic prosody prediction and detection with conditional random field models,” in _Proc. ISCSLP_ , Tainan, Taiwan, 2010, pp. 135–138.
  * [13] A. Graves and J. Schmidhuber, “Framewise phoneme classification with bidirectional lstm and other neural network architectures,” in _Proc. IJCNN_ , Montreal, Canada, 2005.
  * [14] A. Vadapalli and S. V. Gangashetty, “An investigation of recurrent neural network architectures using word embeddings for phrase break prediction,” in _Proc. INTERSPEECH_ , San Francisco, U.S.A., 2016, pp. 2308–2312.
  * [15] C. Ding, L. Xie, J. Yan, W. Zhang, and Y. Liu, “Automatic prosody prediction for chinese speech synthesis using BLSTM-RNN and embedding features,” in _Proc. ASRU_ , Scottsdale, U.S.A., 2015, pp. 98–102.
  * [16] K. Futamata, B. Park, R. Yamamoto, and K. Tachibana, “Phrase break prediction with bidirectional encoder representations in Japanese text-to-speech synthesis,” in _Proc. INTERSPEECH_ , Brno, Czech Republic, 2021, pp. 3126–3120.
  * [17] J. Devlin, M. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of deep bidirectional transformers for language understanding,” in _Proc. NAACL-HLT_ , Minneapolis, U.S.A., 2019, pp. 4171–4186.
  * [18] A. Abbas, T. Merritt, A. Moinet, S. Karlapati, E. Muszynska, S. Slangen, E. Gatti, and T. Drugman, “Expressive, variable, and controllable duration modelling in tts,” in _Proc. INTERSPEECH_ , Incheon, Korea, 2022, pp. 4546–4550.
  * [19] Y. Ren, C. Hu, X. Tan, T. Qin, S. Zhao, Z. Zhao, and T.-Y. Liu, “FastSpeech 2: Fast and high-quality end-to-end text to speech,” in _Proc. ICLR_ , Vienna, Austria, 2021.
  * [20] J. Kim, S. Kim, and S. Y. J. Kong, “Glow-TTS: A generative flow for text-to-speech via monotonic alignment search,” in _Proc. NeurIPS_ , Vancouver, Canada, 2020.
  * [21] H. Zen, V. Dang, R. Clark, Y. Zhang, R. J. Weiss, Y. Jia, Z. Chen, and Y. Wu, “LibriTTS: A corpus derived from LibriSpeech for text-to-speech,” in _Proc. INTERSPEECH_ , Graz, Austria, 2019, pp. 1526–1530.
  * [22] M. McAuliffe, M. Socolof, S. Mihuc, M. Wagner, and M. Sonderegger, “Montreal Forced Aligner: Trainable text-speech alignment using Kaldi,” in _Proc. INTERSPEECH_ , Stockholm, Sweden, 2017, pp. 498–502.
  * [23] E. Campione and J. Véronis, “A large-scale multilingual study of silent pause duration,” in _Proc. Speech Prosody_ , Aix-en-Provence, France, 2002, pp. 199–202.
  * [24] H. Sak, A. W. Senior, and F. Beaufays, “Long short-term memory recurrent neural network architectures for large scale acoustic modeling,” in _Proc. INTERSPEECH_ , Singapore, 2014, pp. 338–342.
  * [25] Y. Zhu, R. Kiros, R. Zemel, R. Salakhutdinov, R. Urtasun, A. Torralba, and S. Fidler, “Aligning books and movies: Towards story-like visual explanations by watching movies and reading books,” in _Proc. ICCV_ , Santiago, Chile, 2015, pp. 19–27.
  * [26] T. Mikolov, K. Chen, G. Corrad, and J. Dean, “Efficient estimation of word representations in vector space,” in _Proc. ICLR Workshop_ , Scottsdale, U.S.A., 2013.
  * [27] D. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _Proc. ICLR_ , San Diego, U.S.A., 2015.
  * [28] J. Kong, J. Kim, and J. Bae, “HiFi-GAN: Generative adversarial networks for efficient and high fidelity speech synthesis,” in _Proc. NeurIPS_ , Vancouver, Canada, 2020.