# Novel Tour Construction Heuristic for Pick-Up and Delivery Routing Problems

Mithun Goutham1 and Stephanie Stockar1 Manuscript submitted on 22 April 2024
to the 4th Modeling, Estimation, and Control Conference (MECC 2024);1 Mithun
Goutham and Stephanie Stockar are with the Department of Mechanical and
Aerospace Engineering, Ohio State University, Columbus, OH 43210 USA (e-mail:
<EMAIL_ADDRESS>stockar.1@osu.edu).

###### Abstract

In logistic applications that require the pickup and delivery of items, route
optimization problems can be modeled as precedence constrained traveling
salesperson problems. The combinatorial nature of this problem restricts the
application of exact algorithms to small instances, and heuristics are largely
preferred for tractability. However, due to precedence constraints that
restrict the order in which locations can be visited, heuristics outside of
the nearest neighbor algorithm have been neglected in literature. While the
convex hull cheapest insertion heuristic is known to produce good solutions in
the absence of precedence constraints, i.e., when locations can be visited in
any order, it has not been adapted for pick-up and delivery considerations.
This paper presents an adapted convex hull cheapest insertion heuristic that
accounts for precedence constraints and compares its solutions with the
nearest neighbor heuristic using the TSPLIB benchmark data set. The proposed
algorithm is particularly suited to cases where pickups are located in the
periphery and deliveries are centrally located, outperforming the Nearest
Neighbor algorithm in every examined instance.

###### Index Terms:

Traveling salesman problems, Vehicle routing and navigation, Intelligent
Transportation Systems, Algorithms, Autonomous robot, Autonomous vehicles

##  I Introduction

Given a set of locations, the Precedence Constrained Traveling Salesperson
Problem (TSP-PC) finds the shortest possible tour that respects precedence
relations between locations, visiting each location exactly once and returning
to the starting location [1]. These problems arise in a variety of real-world
applications such as crane scheduling in ports, job scheduling, automotive
paint shops, helicopter scheduling and flexible manufacturing systems [2, 3,
4, 5], where commodities have to be efficiently transported between locations
to delivery locations, and a tour is only feasible when pick up locations are
visited before their respective deliveries.

Exact methods to solve TSP-PCs are limited to problems with a relatively small
number of locations, typically below 100, due to their $\mathcal{NP}$-hard
nature [6, 7, 8]. Conversely, heuristics follow tour construction rules to
iteratively select locations, defining their order of visitation. While tour
construction heuristics generate feasible solutions quickly, they do not
guarantee optimality and are generally sensitive to problem parameters. For
this reason, heuristics are typically used when solutions have to be found
instantaneously [9, 10, 11], or to initialize exact methods for faster
convergence to the optimal solution [12].

Due to the presence of precedence constraints, sophisticated heuristics
tailored for the TSP-PC have been neglected in literature [13, 14], and
instead, the simple Nearest Neighbor (NN) greedy heuristic is commonly used
[15, 16]. When precedence constraints do not exist, the Convex Hull Cheapest
Insertion (CHCI) heuristic has been shown to produce superior solutions when
compared to the NN heuristic [17, 18]. The CHCI heuristic is initiated by a
subtour created from the convex hull of points, and its interior points are
then progressively added to the subtour in increasing order of insertion cost
ratios until the complete tour is obtained. However, the CHCI heuristic has
not been adapted to the TSP-PC because of the challenges in accounting for
precedence constraints when inserting points to a subtour.

The main contribution of this paper is the extension of the CHCI algorithm to
the TSP-PC by initiating a subtour using the convex hull boundary points of
only the non-delivery locations. After reordering the subtour to originate at
the depot, the subtour is then explored in both clockwise and counterclockwise
directions because precedence constraints introduce a sense of direction of
travel. For every ensuing insertion, the adapted CHCI (ACHCI) heuristic
maintains precedence constraints by only permitting insertions into feasible
subtour segments. This implies that pickup locations can be added anywhere in
the subtour, while delivery locations can only be added in the subtour segment
that has already visited its corresponding pickup location. Test cases that
replicate real-world pickup and delivery considerations are created by adding
precedence constraints to the TSPLIB benchmark instances [19]. After comparing
the performance of the ACHCI and NN heuristics, their solutions are used to
warm start an exact solver to study convergence.

##  II Precedence Constrained TSP

Figure 1: TSP-PC as applied to a delivery truck

Consider $n$ material handling tasks to be completed by an agent, with the
different commodities represented by the set
$\mathcal{H}:=\\{h_{1},h_{2},...,h_{n}\\}$. The set of paired parent and child
locations are defined by $\mathcal{V}^{P}:=\\{1,2,...,n\\}$ and
$\mathcal{V}^{D}:=\\{n+1,n+2,...,2n\\}$, respectively. A commodity
$m\in\mathcal{H}$ picked up at $i\in\mathcal{V}^{P}$ is associated with
payload $q_{im}$ and is paired with a delivery location
$i+n\in\mathcal{V}^{D}$, such that $q_{im}+q_{i+n,m}=0$. The start and end
locations of the agent are at the depot, defined by the identically located
nodes $\\{0,2n+1\\}$. Define
$\mathcal{V}:=\mathcal{V}^{P}\cup\mathcal{V}^{D}$, and
$\overline{\mathcal{V}}:=\mathcal{V}\cup\\{0,2n+1\\}$ to define the graph
representation as $\mathcal{G}:=(\overline{\mathcal{V}},\mathcal{E})$, where
$\mathcal{E}:=\\{(i,j)\in\overline{\mathcal{V}}\times\overline{\mathcal{V}}:i\neq
j\\}$ denotes the set of edges. The TSP-PC is formulated in Eq. (1) below:

$\displaystyle J=\min_{\begin{subarray}{c}x_{ij}\\\
\end{subarray}}~{}\sum_{(ij)\in\mathcal{E}}C_{ij}x_{ij}$ (1a) s.t.
$\displaystyle x_{ij}\in\\{0,1\\}\quad\forall(i,j)\in\mathcal{E}$ (1b)
$\displaystyle\sum_{j\in\mathcal{V}^{p}}x_{0j}=1$ (1c)
$\displaystyle\sum_{i\in\mathcal{V}^{D}}x_{i,2n+1}=1$ (1d)
$\displaystyle\sum_{(ij)\in\mathcal{E}}x_{ij}=1$ (1e)
$\displaystyle\sum_{i\in\mathcal{V}}x_{ij}=\sum_{k\in\mathcal{V}}x_{jk}\quad\forall
j\in\mathcal{V}$ (1f)
$\displaystyle\sum_{i,j\in\mathcal{S}}x_{ij}\leq|\mathcal{S}|-1~{}~{}\forall\mathcal{S}\subset\overline{\mathcal{V}}:2\leq|\mathcal{S}|\leq|\overline{\mathcal{V}}|-1$
(1g) $\displaystyle y_{0m}=0\quad\forall m\in\mathcal{H}$ (1h)
$\displaystyle\sum_{j\in\mathcal{V}}x_{ij}y_{jm}=y_{im}+\sum_{j\in\mathcal{V}}x_{ij}q_{jm}~{}\forall
m\in\mathcal{H},j\in\mathcal{V}$ (1i) $\displaystyle y_{im}\geq 0\quad\forall
m\in\mathcal{H},i\in\mathcal{V}$ (1j)

The cost to travel between each node pair $(i,j)\in\overline{\mathcal{V}}$ is
defined as parameter $C_{ij}\in\mathbb{R}^{+}$ which is to be minimized over
the tour, as captured by Eq. (1a). Binary variables $x_{ij}$ are used to
indicate whether the agent uses edge $(i,j)\in\mathcal{E}$ in the tour. The
agent must start and end at the depot, as specified by Eq. (1c) and (1d)
respectively. Additionally, the agent is permitted to visit each location only
once, as enforced by Eq. (1e), and must leave the location after completing
the visit, as defined by Eq. (1f). The subtour elimination constraint of Eq.
(1g) ensures that the resulting tour visits every location in
$\overline{\mathcal{V}}$.

Payload variables $y_{im}$ define the mass of commodity $m\in\mathcal{H}$
being carried by the agent as it leaves node $i\in\overline{\mathcal{V}}$. The
agent starts its tour with no payload at the depot, as specified by Eq. (1h)
and the evolution of payload as the agent visits pickup and delivery locations
is defined by Eq. (1i) Precedence constraints for each commodity are enforced
by Eq. (1j) which prevents the visit of a delivery location before the
corresponding item has been picked up.

Figure 2: Generalized TSP-PC using the TSPLIB ‘eil51’ instance with added
precedence constraints

The problem of optimally visiting package pickup and delivery locations is
shown in Fig. 1, where, depending on the application, $C_{ij}$ may capture
distance, operational, fuel or any expense to be minimized between two
locations $i,j\in\mathcal{V}$. For an intracity problem, if $C_{ij}$ denotes
distance, the tour cost of a truck that starts at the depot, picks up and
delivers all the packages and returns to the depot typically amounts to tens
of miles. When applied to helicopter scheduling, this may rise to hundreds of
miles [2], while in the context of flexible manufacturing systems, it is often
measured in feet [4].

To generalize the analysis of the proposed ACHCI heuristic for any TSP-PC
application, the popular TSPLIB benchmark instances [19] are used with added
precedence constraints, and the total Euclidean distance is minimized in this
paper. TSPLIB instance ‘eil51’ is shown in Fig. 2, where precedence
constraints are illustrated using grey line segments that relate parent pickup
positions, shown in red, with the respective children drop-off positions,
marked in green. The agent starts and ends its tour at the depot, marked in
blue.

##  III Adapted CHCI Heuristic

The ACHCI heuristic is initiated as the ordered boundary nodes of the convex
hull of non-child locations, that is, the set
$\bar{V}_{0}:=\mathcal{V}^{P}\cup\\{0,2n+1\\}$. This ordered set of points
defines a node sequence $T_{0}:=[v_{1},v_{2},...,v_{1}]$. For any node $v_{k}$
not in $T_{0}$, and any two consecutive nodes $v_{i},v_{j}$ in $T_{0}$, the
insertion cost ratio of $v_{k}$ with respect to $v_{i},v_{j}$ is:

$(C_{ik}+C_{kj})/C_{ij}$ (2)

If the identically located depot node $\\{0,2n+1\\}\notin T_{0}$, consecutive
nodes $v_{i}^{*},v_{j}^{*}$ with the lowest insertion cost ratio is first
found in $T_{0}$, and the depot node is inserted between them. To start and
end the subtour at the depot, the updated subtour $T_{0}$ is reordered to
$[0,v_{j}^{*},...,v_{i}^{*},2n+1]$. Because a sense of direction exists due to
the precedence constraints, denote the resulting subtour as
$\overleftarrow{T}$. The subsequent steps will be repeated in the other
direction $\overrightarrow{T}$ as well, and the lower cost tour is selected.

(a) Initial convex hull subtour

(b) Child node insertion onto the valid segment of the counterclockwise tour

(c) Completed counterclockwise tour

Figure 3: Illustrative example tour of the ACHCI algorithm

For a node $v_{p}\in\overleftarrow{T}$, let the segment of $\overleftarrow{T}$
that has already visited $v_{p}$ be denoted by
$\overleftarrow{T}_{p^{+}}:=[v_{p},v_{p+1},...,2n+1]$. For a candidate
insertion node $v_{k}\notin\overleftarrow{T}$, the feasible partition of
$\overleftarrow{T}$ where $v_{k}$ can be inserted is the subtour segment that
contains every parent of this candidate. If the set of all parents of $v_{k}$,
denoted by $\mathcal{V}_{k}^{-}$ is empty, then the candidate node $v_{k}$ can
be inserted anywhere in the subtour. Contrarily, if $|\mathcal{V}_{k}^{-}|>0$,
then the insertion of $v_{k}\notin\overleftarrow{T}$ is only permitted in
segment
$\overleftarrow{T}^{k}=\bigcap_{p\in\mathcal{V}_{k}^{-}}\overleftarrow{T}_{p^{+}}$.

For every node $v_{i}\notin\overleftarrow{T}$ that is yet to be inserted to
the subtour, the insertion arc given by consecutive nodes
$(v_{q},v_{r})\in\overleftarrow{T}^{i}$ is found that minimizes insertion cost
ratio given by Eq. (2). To ensure feasibility, child nodes whose parents have
not yet been visited in $\overleftarrow{T}$ are assigned an infinite insertion
cost. Next, the node $v^{*}\notin\overleftarrow{T}$ with the lowest insertion
cost ratio is inserted at its associated insertion arc. This increments
$\overleftarrow{T}$ by one node, and these steps are repeated until every node
has been inserted.

Considering the initial subtour $T_{0}$ was assigned some arbitrary direction
that resulted in $\overleftarrow{T}$, all of the tour constructing steps are
also repeated after initializing subtour $T_{0}$ in the opposite direction,
forming another subtour $\overrightarrow{T}$. Thus, two complete tours
$\overleftarrow{T}$ and $\overrightarrow{T}$ are obtained for the TSP-PC, and
the minimum cost tour is selected.

For the convex hull points shown in Fig. 3a, the tour with the
counterclockwise direction is shown in Fig. 3b at an instance when a child
node, marked by a green star, is inserted. Its associated parent is marked by
the red star, and the valid partition of the tour is highlighted, being the
tour segment that has already visited the parent. Notice also that at this
instance, the sub-tour $\overrightarrow{T}$ has already been incremented by
other parent nodes, but not all parent nodes have been inserted. After
inserting all the remaining nodes, the completed Hamiltonian tour with some
cost $\overrightarrow{J}$ is shown in Fig. 3c. These steps are also repeated
after initiating $T_{0}$ in the clockwise direction, to obtain a tour of some
cost $\overleftarrow{J}$. The tour with lower cost between
$\overrightarrow{J}$ & $\overleftarrow{J}$ is selected as the ACHCI heuristic
tour.

(a) Instance ‘eil76’ with central children  (b)  Instance ‘eil76’ with central
parents

(c) Cost ratios for central children  (d) Cost ratios for central parents

Figure 4: Performance comparison of the ACHCI and NN algorithm

##  IV Nearest Neighbor Heuristic

The benchmark for the ACHCI algorithm is the NN which is known to produce
feasible tours in real time for problems with a large number of locations
[20]. The NN heuristic uses a fast greedy selection rule and is commonly seen
in constrained TSP literature because it can easily be modified to account for
constraints in the problem formulation [21, 15]. Starting from the depot, the
NN heuristic assigns the nearest unvisited node as the next node until all
nodes are contained in the tour. By modifying this to only consider unvisited
feasible nodes as the next node, it can be adapted for the TSP-PC:

  1. 1.

Initiate the subtour as the depot

  2. 2.

Add the closest feasible node to the end of the subtour

  3. 3.

Repeat step 2 until all the nodes are included

  4. 4.

Return to the depot

##  V Computational Experiments

To compare the effectiveness of the ACHCI heuristic with the NN heuristic,
sufficiently diverse benchmark instances are not readily available for the
TSP-PC. For this reason, the popular TSPLIB benchmark instances [19] are
modified in a reproducible manner to create cases precedence constraints.

The following steps are used to create TSP-PC instances:

  1. 1.

Load a TSPLIB point cloud that has 2D Cartesian coordinates defined for every
point. Let $n$ be the number of points.

  2. 2.

Find the centroid of the point cloud. Sort and assign indices to the points in
order of increasing distance from the centroid. Let the indices be $1,2,...,n$
for the sorted points.

  3. 3.

Designate the point with index 1 as the depot.

  4. 4.

Define precedence constraints between points with pairs of indices as $(n\prec
2),(n-1\prec 3),(n-2\prec 4)$ and so on. If three nodes remain to be assigned
precedence constraints, the node with the smallest index is assigned to be the
child node while the other two are its parents. The generated point cloud has
child nodes that are clustered closer to the centroid, with parent nodes at
the periphery.

  5. 5.

Assign payload $q_{im}=1$ at all parent locations $i\in\mathcal{V}^{P}$ and
$q_{im}=-1$ for child nodes with only one parent, and $q_{im}=-2$ when a child
node has two parents.

  6. 6.

Repeat (5) after changing direction of the precedence constraints to create
the complementary case where parent nodes are closer to the centroid.

The resulting spatial characteristic of the precedence constraints are
illustrated using the modified TSPLIB ‘eil76’ instance in Fig. 4a and 4b.

###  V-A Comparison of Heuristic Solutions

The ACHCI and NN tours are compared for 60 TSPLIB instances with precedence
constraints, with the number of points varying from 51 to 1,577. The result of
these experiments is summarized in Table II and Table II for ten instances.
The first column lists the name of each TSPLIB instance, formatted with a
prefix followed by a numeric value that indicates the number of points in the
respective instance. The second and third columns provide the solution costs
of the NN and ACHCI heuristics along with the percentage reduction in NN cost
by using the ACHCI solution. The histogram in Fig. 4c shows that the ACHCI
tour cost is lower than the NN cost in all cases with centrally located
children. However, the ACHCI heuritic does not perform as well when parent
nodes are closer to the centroid, as seen in Fig. 4d.

TABLE I: Centrally Located Children

TSPLIB | Heuristic | Exact
---|---|---
instance | NN | ACHCI | Standalone | NN warm start | ACHCI warm start
eil51 | 5.83e+02 | 4.80e+02 (-17.7%) | 4.73e+02 | 4.54e+02 (- 4.0%) | 4.64e+02 (- 2.0%)
erlin52 | 1.12e+04 | 8.25e+03 (-26.1%) | 8.54e+03 | 9.39e+03 (+10.1%) | 8.14e+03 (- 4.6%)
t70 | 9.10e+02 | 7.89e+02 (-13.3%) | 2.20e+03 | 8.29e+02 (-62.3%) | 7.63e+02 (-65.3%)
eil76 | 7.93e+02 | 6.32e+02 (-20.4%) | 2.41e+03 | 7.22e+02 (-70.0%) | 6.28e+02 (-73.9%)
pr76 | 1.96e+05 | 1.27e+05 (-35.0%) | 4.80e+05 | 1.66e+05 (-65.4%) | 1.27e+05 (-73.5%)
rat99 | 1.79e+03 | 1.48e+03 (-17.4%) | - | 1.74e+03 ( - ) | 1.46e+03 ( - )
roC100 | 3.52e+04 | 2.45e+04 (-30.4%) | - | 3.45e+04 ( - ) | 2.44e+04 ( - )
roD100 | 3.50e+04 | 2.75e+04 (-21.2%) | - | 3.34e+04 ( - ) | 2.74e+04 ( - )
roE100 | 3.34e+04 | 2.77e+04 (-17.2%) | - | 3.09e+04 ( - ) | 2.77e+04 ( - )
roA100 | 3.01e+04 | 2.70e+04 (-10.2%) | - | 2.86e+04 ( - ) | 2.68e+04 ( - )

TABLE II: Centrally Located Parents

TSPLIB | Heuristic | Exact
---|---|---
instance | NN | ACHCI | Standalone | NN warm start | ACHCI warm start
eil51 | 5.82e+02 | 6.18e+02 (+ 6.3%) | 1.09e+03 | 5.20e+02 (-52.4%) | 4.74e+02 (-56.6%)
erlin52 | 1.11e+04 | 1.17e+04 (+ 5.5%) | 9.34e+03 | 9.96e+03 (+ 6.6%) | 8.21e+03 (-12.2%)
t70 | 1.08e+03 | 1.20e+03 (+10.6%) | 2.57e+03 | 1.03e+03 (-60.0%) | 1.10e+03 (-57.0%)
eil76 | 7.31e+02 | 8.29e+02 (+13.3%) | 2.08e+03 | 7.24e+02 (-65.1%) | 7.12e+02 (-65.7%)
pr76 | 1.54e+05 | 1.71e+05 (+11.1%) | 4.34e+05 | 1.50e+05 (-65.4%) | 1.63e+05 (-62.4%)
rat99 | 1.80e+03 | 1.94e+03 (+ 7.7%) | - | 1.79e+03 ( - ) | 1.92e+03 ( - )
roC100 | 2.88e+04 | 3.66e+04 (+27.1%) | - | 2.88e+04 ( - ) | 3.52e+04 ( - )
roD100 | 2.80e+04 | 3.55e+04 (+26.6%) | - | 2.78e+04 ( - ) | 3.02e+04 ( - )
roE100 | 3.17e+04 | 3.56e+04 (+12.3%) | - | 3.01e+04 ( - ) | 3.23e+04 ( - )
roA100 | 3.44e+04 | 3.32e+04 (- 3.5%) | - | 3.32e+04 ( - ) | 3.29e+04 ( - )

###  V-B Heuristic Initialization of an Exact Algorithm

The TSP-PC problem formulation defined by Eq. (1) is associated with binary
variables $x_{ij}$ that defines which edges $(i,j)\in\mathcal{E}$ to
constitute the tour, and continuous variables $y_{im}$ related to payload
evolution. The quadratic term $x_{ij}y_{jm}$ in Eq. (1i) sets up a Mixed
Integer Nonlinear Programming (MINLP) formulation which is challenging to
solve, especially considering the $\mathcal{NP}$-hard nature of the TSP-PC. To
address this, each $x_{ij}y_{im}$ is linearized to reduce problem complexity
using the big $M$ method by introducing auxiliary variables
$\lambda_{ijm}=x_{ij}y_{im}$ and four additional constraints:

$\displaystyle\lambda_{ijm}$ $\displaystyle\leq y_{im}+M(1-x_{ij})$
$\displaystyle\forall~{}i,j\in\overline{\mathcal{V}},m\in\mathcal{H}$ (3a)
$\displaystyle\lambda_{ijm}$ $\displaystyle\geq y_{im}-M(1-x_{ij})$
$\displaystyle\forall~{}i,j\in\overline{\mathcal{V}},m\in\mathcal{H}$ (3b)
$\displaystyle\lambda_{ijm}$ $\displaystyle\leq Mx_{ij}$
$\displaystyle\forall~{}i,j\in\overline{\mathcal{V}},m\in\mathcal{H}$ (3c)
$\displaystyle\lambda_{ijm}$ $\displaystyle\geq-Mx_{ij}$
$\displaystyle\forall~{}i,j\in\overline{\mathcal{V}},m\in\mathcal{H}$ (3d)

The value of $M$ in Eq. (3) must be chosen to be a sufficiently large positive
number so that the auxiliary variable and additional constraints linearize
$x_{ij}y_{im}$. This is satisfied for $M>2$ since the maximum payload of
$m\in\mathcal{H}$ is at most 2 in the problem being studied. By replacing
$x_{ij}y_{im}$ in Eq. (1) with $\lambda_{ijm}$ and adding the constraints of
Eq. (3), the MINLP is converted to a Mixed Integer Linear Programming problem
(MILP) which can be solved effectively using commercially available solvers.

The MILP reformulation of Eq. (1) is modeled in a Matlab R2023b environment
and the intlinprog solver of Gurobi 9.5.2 [22] is utilized on an AMD Ryzen
5600X CPU clocked at 3.7 GHz, paired with 128GB RAM. The time limit of the
exact solver is set to 5 minutes and the results are tabulated in Tables II
and II. The fourth column provides the solution found when running the exact
algorithm standalone without any heuristic initialization, where it is seen
that for instances with 99 or more points, no feasible solution is found
within the allocated computation time. The fifth and sixth columns show the
solution found when the exact solver uses the NN solution and ACHCI solution
respectively for a warm start, along with the percentage reduction in solution
cost compared with the standalone solution.

###  V-C Discussion

The spatial characteristics of precedence constraints significantly affect the
performance of the ACHCI algorithm since child nodes can only be inserted in
feasible segments of the tour. When parent nodes are located closer to the
periphery of the point cloud, insertions onto the resulting convex hull are
restricted to the region enclosed by the tour. This avoids large cost
increments when building the tour, and produces tours with low solution costs.
However, when parent nodes are centrally located, the insertions of child
nodes from the periphery can result in large excursions from the tour,
depending on the distance of the child node from its feasible insertion
segment of the subtour. When only a few child nodes remain to be inserted but
their insertable segments happen to be far from them, the ACHCI solution cost
is significantly affected. In these cases, the NN heuristic performs better
than the ACHCI.

Figure 5: Computation time for the two heuristics

A worst case complexity of $O(n^{3})$ characterizes the ACHCI heuristic, as
seen in Fig. 5 where the x axis is the number of TSP-PC locations cubed.
Because of the greedy nature of the NN heuristic, it almost instantaneously
provides tours regardless of the number of points. Considering the negligible
computation time, it is worthwhile to compute the NN tour in addition to the
ACHCI tour, and simply choose the tour with minimum cost between the two.

When the ACHCI heuristic is used to initialize an exact solver, it
consistently improves convergence of the exact solver in all of the cases
studied. The initiation of the candidate subtour with the convex hull of the
points is advantageous when precedence constraints do not exist, because
points on the boundary of the convex hull are visited in the same cyclic order
as their order in the optimal tour [23]. The ACHCI heuristic makes use of this
property and therefore, the resulting solution acts as a good initialization
point for the exact solver. In most NN warm start cases as well, the
convergence of the exact solver was improved.

##  VI Conclusion

In this paper, the popular CHCI algorithm has been adapted for the TSP-PC, a
route optimization problem commonly seen in logistic applications where items
have to be picked up from and delivered to various locations. The proposed
ACHCI algorithm is a tour construction heuristic that accounts for precedence
constraints by first drawing the initiating convex hull over non-delivery
locations and permitting subsequent insertions only in feasible segments that
respect precedence constraints.

Given the diverse problem parameters and cost considerations in real-world
TSP-PC instances, the TSPLIB benchmark dataset was used to generalize the
performance analysis of the ACHCI heuristic. Using the ACHCI heuristic
solution to initialize an exact solver improved convergence in all cases,
while the NN heuristic solutions did not always improve convergence.

The ACHCI heuristic solution outperforms the NN heuristic in all cases where
delivery locations are centrally located, though it did not perform as well
otherwise. It is therefore highly applicable to spatial configurations of
logistics operations where pickup locations are situated around the periphery
to facilitate efficient collection and delivery locations are centrally
situated for sorting, processing, or distribution. Examples include layouts
seen in flexible manufacturing systems or warehousing facilities where
inventory shelves are at the perimeters of the facility, or in online retail
or digital commerce settings where sorting facilities are located on the
outskirts of a city and customers are within city premises.

## References

  * [1] A. Mingozzi, L. Bianco, and S. Ricciardelli, “Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints,” _Operations research_ , vol. 45, no. 3, pp. 365–377, 1997.
  * [2] M. T. Fiala Timlin and W. R. Pulleyblank, “Precedence constrained routing and helicopter scheduling: heuristic design,” _Interfaces_ , vol. 22, no. 3, pp. 100–111, 1992.
  * [3] L. F. Escudero, M. Guignard, and K. Malik, “A lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships,” _Annals of Operations Research_ , vol. 50, no. 1, pp. 219–237, 1994.
  * [4] N. Ascheuer, L. F. Escudero, M. Grötschel, and M. Stoer, “A cutting plane approach to the sequential ordering problem (with applications to job scheduling in manufacturing),” _SIAM Journal on Optimization_ , vol. 3, no. 1, pp. 25–42, 1993.
  * [5] S. Spieckermann, K. Gutenschwager, and S. Voß, “A sequential ordering problem in automotive paint shops,” _International journal of production research_ , vol. 42, no. 9, pp. 1865–1878, 2004.
  * [6] J. Jamal, G. Shobaki, V. Papapanagiotou, L. M. Gambardella, and R. Montemanni, “Solving the sequential ordering problem using branch and bound,” in _2017 IEEE Symposium Series on Computational Intelligence (SSCI)_. IEEE, 2017, pp. 1–9.
  * [7] G. Shobaki and J. Jamal, “An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers,” _Computational Optimization and Applications_ , vol. 61, no. 2, pp. 343–372, 2015.
  * [8] Y. Salii, “Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization,” _European Journal of Operational Research_ , vol. 272, no. 1, pp. 32–42, 2019.
  * [9] Z. Xiang, C. Chu, and H. Chen, “The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments,” _European Journal of Operational Research_ , vol. 185, no. 2, pp. 534–551, 2008.
  * [10] K.-I. Wong, A. Han, and C. Yuen, “On dynamic demand responsive transport services with degree of dynamism,” _Transportmetrica A: Transport Science_ , vol. 10, no. 1, pp. 55–73, 2014.
  * [11] N. Marković, R. Nair, P. Schonfeld, E. Miller-Hooks, and M. Mohebbi, “Optimizing dial-a-ride services in maryland: benefits of computerized routing and scheduling,” _Transportation Research Part C: Emerging Technologies_ , vol. 55, pp. 156–165, 2015.
  * [12] K. Braekers, A. Caris, and G. K. Janssens, “Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots,” _Transportation Research Part B: Methodological_ , vol. 67, pp. 166–186, 2014.
  * [13] F. Glover, G. Gutin, A. Yeo, and A. Zverovich, “Construction heuristics for the asymmetric tsp,” _European Journal of Operational Research_ , vol. 129, no. 3, pp. 555–568, 2001.
  * [14] É. D. Taillard, “A linearithmic heuristic for the travelling salesman problem,” _European Journal of Operational Research_ , vol. 297, no. 2, pp. 442–450, 2022.
  * [15] X. Bai, M. Cao, W. Yan, S. S. Ge, and X. Zhang, “Efficient heuristic algorithms for single-vehicle task planning with precedence constraints,” _IEEE Transactions on Cybernetics_ , vol. 51, no. 12, pp. 6274–6283, 2020.
  * [16] S. Edelkamp, M. Lahijanian, D. Magazzeni, and E. Plaku, “Integrating temporal reasoning and sampling-based motion planning for multigoal problems with dynamics and time windows,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 4, pp. 3473–3480, 2018.
  * [17] L. Ivanova, A. Kurkin, and S. Ivanov, “Methods for optimizing routes in digital logistics,” in _E3S Web of Conferences_ , vol. 258. EDP Sciences, 2021, p. 02015.
  * [18] A. Warburton, “Worst-case analysis of some convex hull heuristics for the euclidean travelling salesman problem,” _Operations research letters_ , vol. 13, no. 1, pp. 37–42, 1993.
  * [19] G. Reinhelt, “$\\{$TSPLIB$\\}$: a library of sample instances for the tsp (and related problems) from various sources and of various types,” _URL: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/_ , 2014.
  * [20] M. Charikar, R. Motwani, P. Raghavan, and C. Silverstein, “Constrained tsp and low-power computing,” in _Workshop on Algorithms and Data Structures_. Springer, 1997, pp. 104–115.
  * [21] A. Grigoryev and O. Tashlykov, “Solving a routing optimization of works in radiation fields with using a supercomputer,” in _AIP Conference Proceedings_ , vol. 2015. AIP Publishing LLC, 2018, p. 020028.
  * [22] Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,” 2023. [Online]. Available: https://www.gurobi.com
  * [23] V. G. Deineko, R. Van Dal, and G. Rote, “The convex-hull-and-line traveling salesman problem: A solvable case,” _Information Processing Letters_ , vol. 51, no. 3, pp. 141–148, 1994.


# Combining Spectral and Self-Supervised Features for Low Resource Speech
Recognition and Translation

###### Abstract

Self-Supervised Learning (SSL) models have been successfully applied in
various deep learning-based speech tasks, particularly those with a limited
amount of data. However, the quality of SSL representations depends highly on
the relatedness between the SSL training domain(s) and the target data domain.
On the contrary, spectral feature (SF) extractors such as log Mel-filterbanks
are hand-crafted non-learnable components, and could be more robust to domain
shifts. The present work examines the assumption that combining non-learnable
SF extractors to SSL models is an effective approach to low resource speech
tasks. We propose a learnable and interpretable framework to combine SF and
SSL representations. The proposed framework outperforms significantly both
baseline and SSL models on Automatic Speech Recognition (ASR) and Speech
Translation (ST) tasks on three low resource datasets. We additionally design
a mixture of experts based combination model. This last model reveals that the
relative contribution of SSL models over conventional SF extractors is very
small in case of domain mismatch between SSL training set and the target
language data.

Index Terms: Low Resource, Self-Supervised Learning, Spectral Features, co-
Attention, Mixture of Experts.

##  1 Introduction

End-to-end models based on deep learning have demonstrated their superiority
over conventional hidden Markov-based models on speech tasks for some corpora
[1, 2, 3, 4]. End-to-end models could be beneficial to low resource speech
tasks because these models: (1) alleviate the need of language specific
resources such as lexicons [5, 6, 7]. (2) can be trained multilingually to
facilitate cross-lingual transfers between high resource and low resource
languages through shared architecture and weights [8]. On the other hand, end-
to-end models can perform poorly when the training data is limited [9] and low
resource scenarios often introduce a language-mismatch with the data used to
train powerful self-supervised learning (SSL) representations [10].

One direction towards mitigating these low-resource issues is to incorporate
knowledge from several languages into multilingual end-to-end models [11, 12,
13]. When there is no training data available for the target languages, these
systems can be even applied in a zero-shot manner [14, 15, 16]. Fortunately,
many languages have small amounts of data which can be used to fine-tune
large-scale multilingual models towards target languages, resulting in further
improvements [17, 18, 19, 20].

Another direction is to use self-supervised learning models trained on large
untranscribed corpora as front-end feature extractors, replacing conventional
spectral features (SF) such as log Mel-filterbanks coefficients (FBANK) [21,
22, 23, 24, 25, 26]. During their unsupervised training, SSL models [27, 28,
29, 30] learn their own feature extraction modules and are totally free of SF
at fine-tuning time. As these models achieve state of the art on numerous
speech tasks and significantly outperform models with more supervision, the
effectiveness of SF on low resource tasks is increasingly questioned.

The majority of SSL models are trained exclusively using English speech.
Although these approaches have shown improvements, even when domain mismatches
occur (such as language or audio conditions [31]), performance depends on the
relatedness between the SSL training domain and the target language one [32].
SSL first layers output representations tend to be quite similar to SF
according to a canonical correlation analysis [33] of Wav2vec2 [29] from Pasad
et al. [34]. In contrast, the last layers are likely to be more corpus or
domain-specific, which should be randomly initialized at fine-tuning time
[34]. Therefore, we assume that SSL representations are potentially more
hurted by domain shifts than SF-based systems are. SF are domain and language
agnostic and their use in multilingual models has demonstrated that they
enable strong cross-lingual transfers [8]. It is then legitimate to assume
that a model leveraging both SF and SSL representations would lead to strong
performances on low resource speech scenarios.

In the present work, we examine this assumption by building a framework that
enables combining SF and SSL representations through learnable fusions. We
propose linear, convolutional and co-attention based combinations. Those
methods obtain a relative diminution of $19.3\%$ Character Error Rate (CER),
averaged on two ASR datasets, and a gain of 1.0 BLEU, on an ST dataset, over
the SSL baseline model, while having less than 0.01% additional parameters. We
further propose a mixture of experts [35] based technique in order to better
interpret the roles and complementarities of SF and SSL components.111Our code
is released on ESPnet [36] Finally the proposed framework is evaluated on
Totonac, a Mexican endangered language, and we release the first publicly
available annotated speech corpus of this
language.222http://www.openslr.org/107/

##  2 Speech Representations

Spectral Features: Machine learning based speech analytics require the
extraction of feature vectors from raw analog waveforms. Log Mel-filterbanks
features (FBANK), conventionally used for supervised speech processing tasks,
are perceptually inspired by human hearing. These features sample and quantize
the analog waveform, apply pre-emphasis to boost high frequency energies,
undergo a discrete Fourier transform (DFT), and finally passed through Mel
filter banks. It is worth noting that the DFT operation is linear and could be
learned during model training but the system may fail to learn it due to its
high complexity, especially if only small amounts of data are available.

Self-Supervised Learning features : While FBANK are hand-crafted features
inspired by the human perception of speech, SSL features learn latent
representations derived from large amounts of unlabeled data. After training
the SSL model, often referred to as pre-training, a fine-tuning phase is
conducted with a task-specific labeled data set. The key idea is that
unlabeled data contains valuable information and is far more abundant than
labeled data in any domain. This paradigm leads to general-purpose speech
representation, suitable for speech processing tasks [10].

##  3 Proposed Approaches

###  3.1 Feature extraction

Let $S$ be a sampled and quantized raw waveform of one utterance. We note
$f_{\text{SF}}(S)$ and $f_{\text{SSL}}(S)$ the features extracted from $S$ by
spectral feature extractors and SSL models (respectively SF and SSL in
formulas). We note $T_{\text{SF}}$ and $T_{\text{SSL}}$ the number of frames
of the utterance, while $D_{\text{SF}}$ and $D_{\text{SSL}}$ denote dimensions
of the features extracted by $f_{\text{SF}}$ and $f_{\text{SSL}}$. We obtain,

$f_{\text{i}}(S)=(f^{t}_{\text{i}}(S)\in\mathbb{R}^{D_{\text{i}}}|t=1,\cdots,T_{\text{i}}),\>i\in\\{\text{SF,
SSL}\\}$ (1)

Additional linear projection and reshaping is applied over SF and SSL features
to allow a same feature dimension $D=D_{\text{SF}}$ and number of frames
$T=T_{\text{SSL}}$. For the dimension, we choose to project SSL features into
SF space and not the inverse in order to decrease the number of parameters (as
$D_{\text{SF}}<D_{\text{SSL}}$) for efficiency purposes. For the number of
frames, as we use a frame-shift two times longer for SSL than for SF, we
downsample (through linear projection and reshaping) the SF features to get a
common number of frames $T=T_{\text{SSL}}$. We now have
$f_{\text{SF}}(S)\in\mathbb{R}^{T\times D}$ and
$f_{\text{SSL}}(S)\in\mathbb{R}^{T\times D}$. Our goal is to combine
$f_{\text{SF}}(S)$ and $f_{\text{SSL}}(S)$ in order to get the best model for
low resource tasks.

###  3.2 Learnable combinations

We first propose a general framework of using learnable transformations
(concatenation, convolutional, and co-attention [37] mechanisms) for combining
those features. Such learnable fusions have previously been employed in
various multisource/multimodal applications[38, 39]. The framework is
formulated as follows, where $f_{\text{FUSE}}(S)$ is the resultant features:

$\vspace{-2pt}f_{\text{FUSE}}(S)=\textsc{Linear(Transform}(f_{\text{SF}}(S),f_{\text{SSL}}(S))$
(2)

With Transform being a concatenation, a convolution or a co-attention based
fusion. We will dive into more details about Eq. (2) for the proposed co-
attention fusion method, which is illustrated in Fig. 1.

Let $W_{\text{SF}}^{\text{Q}}$, $W_{\text{SF}}^{\text{K}}$,
$W_{\text{SF}}^{\text{V}}$, $W_{\text{SSL}}^{\text{Q}}$,
$W_{\text{SSL}}^{\text{K}}$ and $W_{\text{SSL}}^{\text{V}}$ be six learnable
matrices of $\mathbb{R}^{D\times D}$. We use classical attention notation [40]
in Eq. (3). For i$\in${SF, SSL}, we note,

$\vspace{-3pt}Q_{\text{i}}=f_{\text{i}}(S)W_{\text{i}}^{\text{Q}},\quad
K_{\text{i}}=f_{\text{i}}(S)W_{\text{i}}^{\text{K}},\quad
V_{\text{i}}=f_{\text{i}}(S)W_{\text{i}}^{\text{V}}\vspace{-1pt}$ (3)

Figure 1: Architecture of our proposed co-attention based fusion. Raw signal S
is passed through SF and SSL feature extractors. The extracted features,
$f_{\text{SF}}(S)$ and $f_{\text{SSL}}(S)$, attend to each other through two
distinct attention mechanisms. Output features are then concatenated,
projected and passed to the speech model.

Then, we apply two cross-attention blocks in parallel, each made of a one head
scaled dot-product attention operation, with residual connection. We obtain
the SF context vector $h_{\text{SF}}$ by using the SF feature vector as a
query and the SSL feature vector as key and value, and vice versa to obatain
$h_{\text{SSL}}$, the SSL context vector. Eq. (4) and Eq. (5) describe those
symetric attention mechanisms, where $\cdot$ is the dot-product operator.

$h_{\text{SF}}=\textsc{SoftMax}(\frac{Q_{\text{SF}}\cdot
K_{\text{SSL}}}{\sqrt{D}})V_{\text{SSL}}+f_{\text{SF}}(S)$ (4)
$h_{\text{SSL}}=\textsc{SoftMax}(\frac{Q_{\text{SSL}}\cdot
K_{\text{SF}}}{\sqrt{D}})V_{\text{SF}}+f_{\text{SSL}}(S)$ (5)

Our final feature is a projection on $\mathbb{R}^{D}$ of the concatenation of
$h_{\text{SF}}$ and $h_{\text{SSL}}$, as descibed in Eq. (6), where
$\mathbin{\|}$ design the vector concatenation operation.

$f_{\text{FUSE}}(S)=\textsc{Linear}(h_{\text{SF}}\mathbin{\|}h_{\text{SSL}})\vspace{-2pt}$
(6)

We also designed an attention-based fusion, however performance on preliminary
experiments were weak compared to the co-attention model. We assume that the
parallel computations on SF and SSL enable more sophisticated combinations of
the two feature extractors than only one attention block would do.

###  3.3 Mixture of Experts

To get a broader understanding of the potential complementarity of SF and SSL
features, we propose an adaptation of the mixture of experts [35] gating
paradigm, illustrated in Fig. 2. We consider the two feature extractors,
$f_{\text{SF}}$ and $f_{\text{SSL}}$, as our experts. This model requires a
same number of frames for the two experts (see the processing step in Sec.
3.1). We use $f_{\text{SF}}(S)$ as input feature to the gate.333Both
$f_{\text{SF}}(S)$ or $f_{\text{SSL}}(S)$ could be used as input for the gate
layer. We discuss this designing choice in Sec 4.2. Weights are calculated
following Eq. (7), where $w(S)\in\mathbb{R}^{T\times 2}$ is the obtained
weight matrix.

$w(S)=\Theta(f_{\text{SF}}(S)W_{\text{MoE}}),$ (7)

with $W_{\text{MoE}}\in\mathbb{R}^{D\times 2}$ a learnable matrix, and
$\Theta(\cdot)$ a gating-type function such as SoftMax. For clarity, we
introduce $w_{\text{SF}}(S),\>w_{\text{SSL}}(S)\in\mathbb{R}^{T}$, the column
vectors of $w(S)$.

Figure 2: Architecture of the model combining SF and SSL through a gating
mechanism. For a given utterance, the features are extracted by the two models
($a_{i}$ for SF and $b_{i}$ for SSL, $i\in\\{1,...,T\\}$). Each model gets
confidence scores and features are then summed. The $c_{i}$ variables
indicates the weighted sum. Colors of $c_{i}$ frames are used to show how each
frame gets a specific combination of SF (green) and SSL (red) features.

The final combined feature is computed following Eq. (8), where
$[x]^{\text{tr}}$ denotes the transpose vector of $x$.

$\vspace{-2pt}f_{\text{FUSE}}(S)=\sum_{i\in\\{\text{SF},\text{SSL}\\}}[w_{\text{i}}(S)]^{\text{tr}}f_{\text{i}}(S)\vspace{-2pt}$
(8)

The mixture of experts model outputs a weighted sum of feature extractors for
each frame of the utterance. The weights can be interpreted as confidence
scores of SF and SSL for each frame. This model makes the fusion process more
interpretable by enabling to compare relative usage of SF and SSL.

##  4 Experiments

###  4.1 Datasets

Totonac is an endangered language spoken in the northern sierras of the state
of Puebla and adjacent areas of Veracruz, Mexico. To increase the coverage
over endangered languages, we evaluate our proposed methods on Totonac and
release a publicly available version of Totonac ASR
data.444http://www.openslr.org/107/ The corpus comprises 10 hours of speech
(86 long recordings) with fine-grained transcriptions. We randomly selected 70
recordings for the training set, 8 for validation, and 8 for testing.555Those
splits are officially released at https://github.com/ftshijt/Totonac_Split.git
In addition to Totonac, we perform experiments on Arabic corpora of 20 hours
from Commonvoice 5.1 [41], still in the low-resource scenario. Finally, we
extend our study to low resource ST using the Mboshi-French dataset [42],
consisting of 4 hours of speech, to show that our framework is effective in
other speech tasks as well. We chose Arabic (Semitic language) and Mboshi
(Bantu language) as they belong to different language groups than English
(Germanic). Thus, we will compare the robustness of the SSL representations to
the ones of our proposed models over a set of diverse language families, all
different from the one of the SSL self-training data.

###  4.2 Experimental setup

Baseline : Our ASR baseline (Base in the experiments) adopts a transformer-
based encoder-decoder architecture with CTC/Attention hybrid training [43].
The front-end extracts FBANK spectral features with a frame length of 25ms and
a frame-shift of 10ms. The extracted FBANK features are subsampled with a
convolutional block and then fed into the encoder-decoder. The encoder
consists of 12 self-attention blocks with 4-head attention and 256-dimensional
hidden sizes while the decoder has 6 cross-attention transformer blocks. For
ST, we add 2 extra decoders of 2 layers each to this architecture. SpecAugment
[44] and speed perturbation are employed for data augmentation.
Hyperparameters used for training can be found on ESPnet. The ASR model is
trained to recognize 250 byte-pair-encoding (BPE) units. The same architecture
and training configuration are used for the following experiments.

Self-supervised representations : In our experiments, we employ HuBERT [27] ,
which shows promising results over the SUPERB benchmark [10].666We also
performed preliminary experiments over Wav2vec2 XLSR model [45], but it did
not improve the results over HuBERT model so we continued the study only for
HuBERT model. To fully explore the potential of HuBERT, we select the HuBERT-
large model pre-trained over 60k hours of LibriLight [46, 47]. The SSL wrapper
provided in Yang et al.[48] is applied to extract high-dimensional features
with a 20ms frame-shift. In experiment SSL, the FBANK feature extractor (used
in Base) is replaced by the pretained HuBERT model, which is fine-tuned during
training.777SSL based front-ends could be freezed, but the best performances
were obtained when fine-tuning the models.

Learnable combinations : Experiments Linear, Conv. and co-Att. are the
Transform operations introduced in Eq. (2) of Sec 3.2 respectively for
concatenation, convolutional, and co-attention based fusions. For Linear
experiment, we concatenate $f_{\text{SF}}(S)$ and $f_{\text{SSL}}(S)$ and then
project the concatenation into a 80-dimensional space. In Conv. experiment, we
apply a 1-dimensionnal convolutional layer with kernel size 5 and stride of 1
over $f_{\text{SF}}(S)$ and $f_{\text{SSL}}(S)$ before concatenating and
projecting them. The co-attention model is described through Eq. (3) to Eq.
(6), and the model is illustrated in Fig. 1.

Mixture of experts : Our mixture of experts model (MoE in the experiments)
follows Eq. (7) and Eq. (8) described in Sec. 3.3. For the main experiments,
we use SF (here FBANK) as input features and $\Theta(\cdot)=\textsc{Log-
SoftMax}(\cdot)$ for the gating function. We performed a comparative study of
inputs to the gating function. Using both SF or SSL features led to better
scores than the baselines but SF as input performed best. Our interpretation
is that it is easier for the model to learn gating weights when computed over
non-learnable features (SF, here FBANK) than over complex features which are
continuously fine-tuned. We also compared results with
$\Theta(\cdot)=\textsc{Log-SoftMax}(\cdot)$ and
$\Theta(\cdot)=\textsc{SoftMax}(\cdot)$. Performances are similar,
$\Theta(\cdot)=\textsc{Log-SoftMax}(\cdot)$ being slightly better. A more
detailed analysis of the gating weights intra-utterance revealed a more peaky
behavior for $\Theta(\cdot)=\textsc{SoftMax}(\cdot)$, which in our opinion led
to the small performance degradation.

Evaluation metrics : We use Character Error Rate (CER) for evaluation of our
ASR models and BLEU score to measure performances of our ST systems.

##  5 Results and Analysis

###  5.1 Main results

Table 1 provides results for the experiments listed in Sec. 4.2.

Table 1: ASR and ST results over models described in Sec. 4.2. The two first experiments are our FBANK and SSL baselines. The following lines are the proposed Linear, Convolutional, co-Attention, and Mixture of Experts models. |  CER $\downarrow$ |  BLEU $\uparrow$
---|---|---
Exp | Totonac | Arabic | Mboshi-French
Base | 17.2 | 15.4 | 10.9
SSL | 14.2 | 8.1 | 10.6
Linear | 14.0 | 6.6 | 11.6
Conv. | 13.9 | 7.2 | 11.3
co-Att. | 13.4 | 5.4 | 10.9
MoE | 13.7 | 6.2 | 11.2

####  5.1.1 Speech Recognition results

First we remark that using HuBERT as a feature extractor (SSL experiment)
instead of FBANK (Base experiment) is very effective on the Totonac and Arabic
ASR corpora, leading to respective diminutions of $3.0$ and $7.3$ of CER.

Then, we note that all of the combination methods we introduced in Sec. 3.2
led to improvements on the two datasets over the Base and SSL models. We get a
diminution of $2.7$ CER ($33\%$) on Arabic and $0.8$ CER ($5.6\%$) on Totonac
when using the co-attention model. The co-attention model performs better than
the linear and convolution based methods, in particular for Arabic. A possible
explanation is that this model: (1) has a larger modeling capacity (leading to
better results), and (2) induces a more balanced use of the two front-ends,
through the symmetric architecture and the residual connections. This second
point could explain the greater CER reduction over Arabic than Totonac, as an
equal contribution of front-ends seems to lead to a robust model for Arabic
(see Sec. 5.2).

Finally, the mixture of experts model that we introduced for gaining
interpretability is also getting strong performances.

####  5.1.2 Speech Translation results

As it is straightforward to use our front-end fusion framework for different
speech tasks, we applied it to ST. Table 1 shows that all of our proposed
methods outperforms both FBANK and SSL baselines. We note that using HuBERT
representations as front-end degraded the performance in that scenario (see
experiments Base and SSL). Even in that case, all the proposed systems
performed better than both baselines. The linear fusion method reaches a BLEU
score of $11.6$, gaining $1.0$ BLEU over the SSL baseline and $0.7$ BLEU over
the FBANK one. Contrary to the ASR scenario, here the linear and convolutional
methods outperform the co-attention one. As Mboshi is only made of only 4
hours of speech, we assume that the co-attention model may be too complex to
be well trained contrary to the linear model.

###  5.2 Mixture of Experts : Weights and Analysis

In this section, we examine the weights $w_{\text{SF}}(S)$ and
$w_{\text{SSL}}(S)$ (introduced in Sec. 3.3) obtained by the mixture of
experts model for the two ASR datasets. For more interpretability, we
normalized them so that $w_{\text{SSL}}(S)+w_{\text{SF}}(S)=1$. First we can
note that our robust MoE model is indeed using both FBANK and HuBERT
components as the two weights are non negligible. Then, we remark that the
weights across frames of a same utterance are quite similar. The two front-
ends are used consistently over the frames, which we would expect as a
utterance content may be quite consistent. We note that the weights across
different utterances are also similar within languages. However they are very
different from one language to another.

Table 2: Two views on HuBERT representations quality over Totonac and Arabic data. The first column presents $\overline{w_{\text{SSL}}(S)}$, the mean MoE weights for HuBERT front-end. The second column is the character error reduction rate reduction (CERR8) between the FBANK baseline and the HuBERT baseline. Language | $\overline{w_{\text{SSL}}(S)}$ |  CERR(Base $\rightarrow$ SSL)
---|---|---
Totonac | 0.17 | 17%
Arabic | 0.51 | 47%

The first column of Table 2 presents the mean $w_{\text{SSL}}(S)$ weight for
each language. Contrary to the Arabic model, which uses HuBERT and FBANK with
similar weights, the Totonac model seems to be using HuBERT representations as
an adjustment component, relying on average at more than $80\%$ on spectral
features. Our interpretation is that the Commonvoice Arabic data is closer in
domain (read speech) to the English LibriLight than Totonac data is
(spontaneous speech/conversation). For that reason, HuBERT model may extract
relatively better speech representations (compared to FBANK representations)
for Arabic than it does for Totonac. This would explain that the mixture of
experts model grants HuBERT with a larger weight for the Arabic data. Another
way of quantifying HuBERT representations quality over the languages could be
to calculate the character error reduction rate (CERR888CERR is defined as
follows : CERR = $\frac{\text{CER(Base) - CER(SSL)}}{\text{CER(Base)}}\times
100$.) between FBANK and HuBERT baselines (experiments Base and SSL in Table
1). The second column in Table 2 confirms our intuition : the mixture of
experts model weights the components according to their relative strength over
the language. As Arabic benefits more from HuBERT representations than Totonac
does, the mixture of experts model assigned a higher weight to the HuBERT
front-end in the Arabic model than in the Totonac one.

##  6 Conclusions

SSL models performance depends highly on the relatedness between the self-
supervised training domain(s) and the target data domain. As spectral features
are not subject to those variations, we proposed a framework to combine
spectral features to SSL representations. This framework can be applied to
many speech tasks with no further work. We obtained strong improvements over
ASR and ST datasets compared with the SSL baseline. We further proposed a
weight analysis showing that: (1) our models performances are strong for both
in-domain and out-of-domain scenarios. (2) our mixture of experts framework
enables quantifying the domain shift between the SSL training data and the
target language resources.

Future work could involve fusions at the encoder level. As SSL models also
perform strongly when used as encoders, fusing SSL features with SF passed
through a pre-trained encoder could be an even more robust technique.

##  7 Acknowledgements

This work used the Extreme Science and Engineering Discovery Environment
(XSEDE) [49], which is supported by National Science Foundation grant number
ACI-1548562. Specifically, it used the Bridges system [50], as part of project
cis210027p, which is supported by NSF award number ACI-1445606, at the
Pittsburgh Supercomputing Center (PSC). Recording (Amith) and transcription
(López) of Zongozotla Totonac was carried out with support from the National
Science Foundation, Documenting Endangered Languages Program (Award
#BCS-1401178), the National Endowment for the Humanities, Preservation and
Access (Award #PD-50031-14), and the Jacobs Research Fund (awards in 2019 and
2020). Amith was PI on all three.

## References

  * [1] C.-C. Chiu, T. N. Sainath, Y. Wu _et al._ , “State-of-the-art speech recognition with sequence-to-sequence models,” in _ICASSP_ , 2018.
  * [2] S. Karita, Chen _et al._ , “A comparative study on transformer vs RNN† in speech applications,” in _ASRU_ , 2019.
  * [3] N.-Q. Pham, T.-S. Nguyen _et al._ , “Very deep self-attention networks for end-to-end speech recognition,” _Interspeech_ , 2019.
  * [4] P. Guo, F. Boyer _et al._ , “Recent developments on ESPnet toolkit boosted by conformer,” in _ICASSP_ , 2021.
  * [5] L. A. Grenoble, P. K. Austin, and J. Sallabank, “The Cambridge handbook of endangered languages,” _Cambridge University Press_ , 2011.
  * [6] A. Zahrer, A. Zgank, and B. Schuppler, “Towards building an automatic transcription system for language documentation: Experiences from muyu,” in _LREC_ , 2020.
  * [7] J. Shi, J. D. Amith, R. Castillo García _et al._ , “Leveraging end-to-end ASR for endangered language documentation: An empirical study on yolóxochitl Mixtec,” in _EACL_ , 2020.
  * [8] J. Cho, M. K. Baskar _et al._ , “Multilingual sequence-to-sequence speech recognition: Architecture, transfer learning, and language modeling,” in _SLT_ , 2018.
  * [9] C. Lüscher, E. Beck, K. Irie _et al._ , “RWTH ASR systems for Librispeech: Hybrid vs attention - w/o data augmentation,” in _Interspeech_ , 2019.
  * [10] H.-S. Tsai, H.-J. Chang, W.-C. Huang _et al._ , “SUPERB-SG: Enhanced speech processing universal performance benchmark for semantic and generative capabilities,” _arXiv preprint arXiv:2203.06849_ , 2022.
  * [11] S. Watanabe, T. Hori, and J. R. Hershey, “Language independent end-to-end architecture for joint language identification and speech recognition,” in _ASRU_ , 2017.
  * [12] S. Toshniwal, T. N. Sainath _et al._ , “Multilingual speech recognition with a single end-to-end model,” in _ICASSP_ , 2018.
  * [13] A. Kannan, A. Datta, T. N. Sainath _et al._ , “Large-Scale Multilingual Speech Recognition with a Streaming End-to-End Model,” in _Interspeech_ , 2019.
  * [14] X. Li, S. Dalmia, J. Li _et al._ , “Universal phone recognition with a multilingual allophone system,” in _ICASSP_ , 2020.
  * [15] B. Yan, S. Dalmia _et al._ , “Differentiable allophone graphs for language-universal speech recognition,” _Interspeech_ , 2021.
  * [16] Q. Xu, A. Baevski, and M. Auli, “Simple and effective zero-shot cross-lingual phoneme recognition,” _arXiv preprint arXiv:2109.11680_ , 2021.
  * [17] W. Hou, Y. Dong, B. Zhuang _et al._ , “Large-Scale End-to-End Multilingual Speech Recognition and Language Identification with Multi-Task Learning,” in _Interspeech_ , 2020.
  * [18] V. Pratap, A. Sriram, P. Tomasello _et al._ , “Massively Multilingual ASR: 50 Languages, 1 Model, 1 Billion Parameters,” in _Interspeech_ , 2020\.
  * [19] O. Adams, M. Wiesner _et al._ , “Massively multilingual adversarial speech recognition,” in _ACL_ , 2019.
  * [20] B. Li, R. Pang, T. N. Sainath _et al._ , “Scaling end-to-end models for large-scale multilingual ASR,” _ASRU_ , 2021.
  * [21] C. Yi, J. Wang, N. Cheng _et al._ , “Applying wav2vec2.0 to speech recognition in various low-resource languages,” _arXiv preprint arXiv:2012.12121_ , 2020.
  * [22] A. Wu, C. Wang, J. Pino, and J. Gu, “Self-Supervised Representations Improve End-to-End Speech Translation,” in _Interspeech_ , 2020.
  * [23] A. Baevski, Y. Zhou, A. Mohamed, and M. Auli, “wav2vec 2.0: A framework for self-supervised learning of speech representations,” _NeurIPS_ , 2020.
  * [24] K. D. N, P. Wang, and B. Bozza, “Using Large Self-Supervised Models for Low-Resource Speech Recognition,” in _Interspeech_ , 2021.
  * [25] X. Chang, T. Maekaku, P. Guo _et al._ , “An exploration of self-supervised pretrained representations for end-to-end speech recognition,” _ASRU_ , 2021\.
  * [26] A. T. Liu, S.-W. Li, and H.-y. Lee, “Tera: Self-supervised learning of transformer encoder representation for speech,” _TASLP_ , 2021.
  * [27] W. Hsu, B. Bolte, Y. H. Tsai _et al._ , “Hubert: Self-supervised speech representation learning by masked prediction of hidden units,” _TASLP_ , 2021\.
  * [28] S. Schneider, A. Baevski, R. Collobert, and M. Auli, “wav2vec: Unsupervised pre-training for speech recognition,” _Interspeech_ , 2019.
  * [29] A. Baevski, H. Zhou, A. Mohamed, and M. Auli, “wav2vec 2.0: A framework for self-supervised learning of speech representations,” _NeurIPS_ , 2020.
  * [30] S. Chen, C. Wang, Z. Chen _et al._ , “Wavlm: Large-scale self-supervised pre-training for full stack speech processing,” _arXiv preprint arXiv:2110.13900_ , 2021.
  * [31] R. Sanabria, W.-N. Hsu, A. Baevski, and M. Auli, “Measuring the impact of individual domain factors in self-supervised pre-training,” _arXiv preprint arXiv:2203.00648_ , 2022.
  * [32] A. Conneau, K. Khandelwal, N. Goyal _et al._ , “Unsupervised cross-lingual representation learning at scale,” _Interspeech_ , 2019.
  * [33] G. Andrew, R. Arora, J. Bilmes, and K. Livescu, “Deep canonical correlation analysis,” in _ICML_ , 2013.
  * [34] A. Pasad, J.-C. Chou, and K. Livescu, “Layer-wise analysis of a self-supervised speech representation model,” in _ASRU_ , 2021.
  * [35] R. A. Jacobs, M. I. Jordan, S. J. Nowlan, and G. E. Hinton, “Adaptive Mixtures of Local Experts,” _Neural Computation_ , 1991.
  * [36] S. Watanabe, T. Hori, S. Karita _et al._ , “ESPnet: End-to-end speech processing toolkit,” in _Interspeech_ , 2018.
  * [37] J. Lu, J. Yang, D. Batra, and D. Parikh, “Hierarchical question-image co-attention for visual question answering,” in _NIPS_ , 2016.
  * [38] J. Libovický and J. Helcl, “Attention strategies for multi-source sequence-to-sequence learning,” in _ACL_ , 2017.
  * [39] C. Hori, T. Hori, T.-Y. Lee _et al._ , “Attention-based multimodal fusion for video description,” in _EECV_ , 2017.
  * [40] A. Vaswani, N. Shazeer, N. Parmar _et al._ , “Attention is all you need,” in _NeurIPS_ , 2017.
  * [41] R. Ardila, M. Branson _et al._ , “Common voice: A massively-multilingual speech corpus,” in _LREC_ , 2020.
  * [42] P. Godard, G. Adda, M. Adda-Decker _et al._ , “A very low resource language speech corpus for computational language documentation experiments,” in _LREC_ , 2018.
  * [43] S. Kim, T. Hori, and S. Watanabe, “Joint ctc-attention based end-to-end speech recognition using multi-task learning,” in _ICASSP_ , 2017.
  * [44] D. S. Park, W. Chan, Y. Zhang _et al._ , “SpecAugment: A Simple Data Augmentation Method for Automatic Speech Recognition,” in _Interspeech_ , 2019.
  * [45] A. Conneau, A. Baevski, R. Collobert _et al._ , “Unsupervised cross-lingual representation learning for speech recognition,” in _Interspeech_ , 2021.
  * [46] J. Kahn, M. Rivière _et al._ , “Libri-light: A benchmark for asr with limited or no supervision,” in _ICASSP_ , 2020.
  * [47] M. Ott, S. Edunov, A. Baevski _et al._ , “fairseq: A fast, extensible toolkit for sequence modeling,” in _NAACL_ , 2019.
  * [48] S. Yang, P.-H. Chi, Y.-S. Chuang _et al._ , “SUPERB: Speech Processing Universal PERformance Benchmark,” in _Interspeech_ , 2021.
  * [49] J. Towns, T. Cockerill _et al._ , “XSEDE: Accelerating scientific discovery,” _Computing in Science & Engineering_, 2014.
  * [50] N. A. Nystrom, M. J. Levine _et al._ , “Bridges: a uniquely flexible HPC resource for new communities and data analytics,” in _XSEDE_ , 2015.


# Slice-level Detection of Intracranial Hemorrhage on CT Using Deep
Descriptors of Adjacent Slices

Dat T. Ngo  Vingroup Big Data Institute
10000, Hanoi, Vietnam Thao T.B. Nguyen  Vingroup Big Data Institute
10000, Hanoi, Vietnam Hieu T. Nguyen  Vingroup Big Data Institute
10000, Hanoi, Vietnam Dung B. Nguyen  Vingroup Big Data Institute
10000, Hanoi, Vietnam Ha Q. Nguyen  Vingroup Big Data Institute
VinBigData JSC,
10000, Hanoi, Vietnam Hieu H. Pham  VinUni-Illinois Smart Health Center,
College of Engineering & Computer Science,
10000, Hanoi, Vietnam
Correspondence<EMAIL_ADDRESS>
###### Abstract

The rapid development in representation learning techniques such as deep
neural networks and the availability of large-scale, well annotated medical
imaging datasets have to a rapid increase in the use of supervised machine
learning in the 3D medical image analysis and diagnosis. In particular, deep
convolutional neural networks (D-CNNs) have been key players and were adopted
by the medical imaging community to assist clinicians and medical experts in
disease diagnosis and treatment. However, training and inferencing deep neural
networks such as D-CNN on high-resolution 3D volumes of Computed Tomography
(CT) scans for diagnostic tasks poses formidable computational challenges.
This challenge raises the need of developing deep learning-based approaches
that are robust in learning representations in 2D images, instead 3D scans. In
this work, we propose for the first time a new strategy to train _slice-level_
classifiers on CT scans based on the descriptors of the adjacent slices along
the axis. In particular, each of which is extracted through a convolutional
neural network (CNN). This method is applicable to CT datasets with per-slice
labels such as the RSNA Intracranial Hemorrhage (ICH) dataset, which aims to
predict the presence of ICH and classify it into 5 different sub-types. We
obtain a single model in the top 4% best-performing solutions of the RSNA ICH
challenge, where model ensembles are allowed. Experiments also show that the
proposed method significantly outperforms the baseline model on CQ500. The
proposed method is general and can be applied for other 3D medical diagnosis
tasks such as MRI imaging. To encourage new advances in the field, we will
make our codes and pre-trained model available upon acceptance of the paper.

###### Index Terms:

component, formatting, style, styling, insert

##  I Introduction

Deep neural networks, in particular deep convolutional neural networks (CNNs)
[24, 1, 4] became a key tool in medical imaging analysis [20, 22, 26, 6]. In
particular, deep neural networks have showed excellent performance in 2D
medical imaging data such as the interpretation of X-ray scans [18, 21, 16,
17, 14, 13, 23, 12]. However, training very deep networks on high-resolution
3D volumes of Computed Tomography (CT) scans requires a huge computing
resource. For examples, each typical 3D CT scans study may contain from
hundreds to thousands slices, which makes training deep neural networks on
this modality challenging in terms of computing requirements (see Figure 1).
In this study, we aim to develop an efficient 2D deep learning-based approach
for 3D medical imaging analysis that is able to provide the same level of
performance compared to 3D-based learning approaches. To tackle this
challenge, we consider each 3D CT scan as a set of 2D images and propose a new
strategy to train _slice-level_ classifiers on CT based on the descriptors of
the adjacent slices along the axis, each of which is extracted through a
convolutional neural network (CNN). Extracted features are then concatenated
to produce better representations for classification tasks. This method is
applicable to CT datasets with per-slice labels such as the RSNA Intracranial
Hemorrhage (ICH) dataset [19], which aims to predict the presence of ICH and
classify it into 5 different sub-types.

Figure 1: Examples of head computed tomography scans. Each study may contain
from hundreds to thousands slices, which makes training deep neural networks
on this modality challenging in terms of computing requirements.

The proposed method exploits a two-stage training scheme. In the first stage,
we treat a CT scan simply as a set of 2D images and train a state-of-the-art
CNN classifier [7] that was pretrained on ImageNet [10]. During the training
process, each slice is sampled _together_ with the 3 slices before and the 3
slices after it. By this way, each CNN model takes a batch size a multiple of
7 slices as input. In the second stage, the output _descriptors_ of each block
of 7 consecutive slices obtained from the first stage are stacked into an
image and fed to another CNN model for final prediction of the middle slice.
Then, we leverage the assemble learning to boost classification performance.
To evaluate the effectiveness of the proposed approach, we train our deep
learning framework on the RSNA dataset and additionally evaluated on the CQ500
dataset [2], which adopts the same a set of labels but only on study level. We
obtain a single model111Model weights and codes are available upon acceptance
of the paper. in the top 4% best-performing solutions of the RSNA ICH
challenge, where model ensembles are allowed. Experiments also show that the
proposed method significantly outperforms the baseline model on CQ500 [2]. To
summarize, our key contribution is to introduce a simple 2D-based technique
that allows to train a very deep neural network on 3D imaging data and
providing better results compared to 3D-based approaches. The proposed method
is simple, general can can be applied for many other 3D medical imaging
analysis tasks such as MRI imaging analysis. The rest of the paper is
organized as follows. The proposed approach is presented in Section II.
Section III describe the experiments and discusses the experimental results.
Finally, section IV concludes the work as well as presents its perspectives.

##  II Proposed approach

Non-contrast head CT scans are the current standard imaging propotcol for
initial imaging of patients with stroke symptoms, including intracranial
haemorrhag [3]. We aim in this study to develop and validate a 2D-based deep
learning algorithms for automated detection of the key findings from head CT
scan scans called intracranial haemorrhage. The proposed approach is validated
on the RSNA Intracranial Hemorrhage (ICH) dataset. It is difficult to exploit
high-performing deep neural networks for the ICH classification while keeping
the full 3D resolution of the input CT. On the other hand, using slices as
independent 2D images and ignoring the axial information of data causes
detrimental effects to the algorithm’s performance. Our method gets the best
of both worlds: we apply transfer learning [15] on 2D images to perform
classification per slice and then assemble the results of local slices to
refine the prediction of the middle one. The proposed scheme, illustrated in
Figure 2, consists of two stages: descriptor extraction and axial fusion.
Below we describe these element in details.

Figure 2: Illustration of the proposed two-stage training procedure.

###  II-A Descriptor extraction

In this stage, we train a 2D CNN to classify individual slices of the CT
scans, which are converted into 3-channel images using 3 different windows:
brain ($l=40,w=80$), subdural ($l=75,w=215$), and bone ($l=600,w=2800$). The
output of the network is a descriptor of size 6$\times$1 that includes the
probabilities of the 5 ICH sub-types and an additional class for any of them.
During training, each slice is always sampled in a block of 7 that includes
itself in the center and 6 neighboring slices. With this approach, we can take
advantage of pre-trained models on ImageNet [5] to initialize the network.
Specifically, a ResNet-50 [7] was used in our experiments. We followed the
procedure in [8] and trained the network for 20 epochs with a batch size of
$16\times 7$ using Adam optimizer [9]. An initial learning rate of $5e-4$ and
the cosine annealing learning rate scheduler [11] were used. Several
augmentation techniques such as cropping, resizing, flips, rotations,
distortions, gaussian noise, and CutMix [25] were applied to prevent the
network from overfitting.

###  II-B Axial fusion

This stage combines the descriptors of each 7 consecutive slices generated in
stage 1 to exploit the axial information and to refine the prediction of the
centered slice. In particular, we concatenate the 7 descriptors into a
7$\times$6$\times$1 tensor and train a 3-layer CNN to output the final
classification result for the representative slice in the middle of the block.
This network contains only 2 convolution layers and 1 fully connected layer.
The 2D convolution kernels help the model learn both the relationship between
ICH predictions across local slices and the relationship between probabilities
for the sub-types. The output of the fusion network can therefore be seen as a
re-calibrated prediction of a single slice.

##  III Experiments and results

###  III-A Datasets and evaluation protocols

The RSNA and CQ500 datasets were used to verify the effectiveness of the
proposed approach. Both of them contain non-contrast CT scans that are labeled
with 5 sub-types of ICH: intraparenchymal, intraventricular, subdural,
extradural, and subarachnoid. The only difference between the two datasets is
that the labels of RSNA are per slice, while the those of CQ500 are per CT
scan. The whole RSNA dataset was split into 3 parts: a public training set
(19,530 studies), a public testing set (2,214 studies), and a private testing
set (3,518 studies). Each study is a CT scan of 20 to 60 slices of
512$\times$512 pixels. The weighted log loss was used as the evaluation metric
for this dataset, in which a weight of $2/7$ was used for the ICH label and a
weight of $1/7$ was used for each of the 5 sub-types.

Meanwhile, CQ500 consists of 500 studies, from which 490 were selected for
experiments while the rest 10 of them are noisy and were excluded from the
dataset. We used CQ500 as another test set to validate the efficiency and
robustness of the proposed algorithm, which was merely trained on the public
training set of RSNA. On this test, the performance of our method is measured
by area under the ROC curve (AUC). Note that the study-level probability of
any class was taken as the maximum probability amongst all slices.

###  III-B Experimental results

We report a weighted log loss of 0.05341 on the private testing set of RSNA,
which ranks in top 4$\%$ over 1345 teams on the Kaggle leaderboard. Note that
our result is provided by a single ResNet-50 model, while many other solutions
in this competition exploit ensemble techniques. On CQ500, the proposed method
achieves a mean AUC of 0.971. This is an improvement of around $2\%$ compared
to the baseline model [2]. Especially, our method provides better AUC scores
over all disease labels as shown in Table I. These results strongly
demonstrate the generalization capacity of our model, which was trained on a
different dataset with a different labeling protocol.

Findings | [2] |  | Ours
---|---|---|---
ICH (any subtypes) | 0.9419 |  | 0.9612
Intraparenchymal | 0.9544 |  | 0.9691
Intraventricular | 0.9310 |  | 0.9832
Subarachnoid | 0.9574 |  | 0.9596
Subdural | 0.9521 |  | 0.9694
Extradural | 0.9731 |  | 0.9814
Mean | 0.9520 |  | 0.9710
TABLE I: Experimental results measured by AUC score on CQ500 dataset.

##  IV Conclusion

Training very deep neural networks such as D-CNN model on 3D medical scans
like CT or MRI is a challenging task. Three-dimensional computed tomography
(3DCT) is a type of CT scanning which records multiple images over time, that
requires huge computational requirements when D-CNNs are explored. We
presented in this paper a novel two-stage training strategy for the task of
slice-level classification on CT scans. The key idea is to sample each slice
together with its neighbors and to refine the classification of it using the
coarse descriptors of the whole group. This method was experimentally
demonstrated to work well on ICH datasets like RSNA and CQ500. We believe that
it can be easily extended to other 3D datasets of CT or MRI scans.

Acknowledgements. This study was supported by VinBigData JSC.

## References

  * [1] W. Alakwaa, M. Nassef, and A. Badr.  Lung cancer detection and classification with 3d convolutional neural network (3d-cnn).  International Journal of Advanced Computer Science and Applications, 8(8), 2017.
  * [2] S. Chilamkurthy, R. Ghosh, S. Tanamala, M. Biviji, N. Campeau, V. Venugopal, V. Mahajan, P. Rao, and P. Warier.  Development and validation of deep learning algorithms for detection of critical findings in head CT scans.  Lancet, 392:2388–2396, 2018.
  * [3] S. Chilamkurthy, R. Ghosh, S. Tanamala, M. Biviji, N. G. Campeau, V. K. Venugopal, V. Mahajan, P. Rao, and P. Warier.  Deep learning algorithms for detection of critical findings in head ct scans: a retrospective study.  The Lancet, 392(10162):2388–2396, 2018.
  * [4] B. T. Dao, T. V. Nguyen, H. H. Pham, and H. Q. Nguyen.  Phase recognition in contrast-enhanced ct scans based on deep learning and random sampling.  Medical Physics, 2022.
  * [5] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In Proc. CVPR, pages 248–255, 2009.
  * [6] R. Gruetzemacher, A. Gupta, and D. Paradice.  3d deep learning for detecting pulmonary nodules in ct scans.  Journal of the American Medical Informatics Association, 25(10):1301–1310, 2018.
  * [7] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In Proc. CVPR, pages 770–778, 2016.
  * [8] T. He, Z. Zhang, H. Zhang, Z. Zhang, J. Xie, and M. Li.  Bag of tricks for image classification with convolutional neural networks.  In Proc. CVPR, pages 558–567, 2019.
  * [9] D. Kingma and J. Ba.  Adam: A method for stochastic optimization.  In Proceedings of the 3rd International Conference on Learning Representations (ICLR), pages 1–15, 2015.
  * [10] A. Krizhevsky, , I. Sutskever, and G. Hinton.  Imagenet classification with deep convolutional neural networks.  In Proc. NeurIPS, pages 1097–1105, 2012.
  * [11] I. Loshchilov and F. Hutter.  SGDR: Stochastic gradient descent with warm restarts.  In Proc. ICLR, pages 1–16, 2017.
  * [12] H. T. Nguyen, H. H. Pham, N. T. Nguyen, H. Q. Nguyen, T. Q. Huynh, M. Dao, and V. Vu.  Vindr-spinexr: A deep learning framework for spinal lesions detection and classification from radiographs.  In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 291–301. Springer, 2021.
  * [13] H. T. Nguyen, S. B. Tran, D. B. Nguyen, H. H. Pham, and H. Q. Nguyen.  A novel multi-view deep learning approach for bi-rads and density assessment of mammograms.  arXiv preprint arXiv:2112.04490, 2021.
  * [14] N. H. Nguyen, H. Q. Nguyen, N. T. Nguyen, T. V. Nguyen, H. H. Pham, and T. N.-M. Nguyen.  A clinical validation of vindr-cxr, an ai system for detecting abnormal chest radiographs.  arXiv preprint arXiv:2104.02256, 2021.
  * [15] S. Pan and Q. Yang.  A survey on transfer learning.  IEEE Transactions on Knowledge and Data Engineering, 22(10):1345–1359, 2009.
  * [16] H. H. Pham, T. T. Le, D. Q. Tran, D. T. Ngo, and H. Q. Nguyen.  Interpreting chest x-rays via cnns that exploit hierarchical disease dependencies and uncertainty labels.  Neurocomputing, 437:186–194, 2021.
  * [17] H. H. Pham, H. Q. Nguyen, K. Lam, L. T. Le, D. B. Nguyen, H. T. Nguyen, T. T. Le, T. V. Nguyen, M. Dao, and V. Vu.  An accurate and explainable deep learning system improves interobserver agreement in the interpretation of chest radiograph.  medRxiv, 2021.
  * [18] P. Rajpurkar, J. Irvin, K. Zhu, B. Yang, H. Mehta, T. Duan, D. Ding, A. Bagul, C. Langlotz, K. Shpanskaya, et al.  Chexnet: Radiologist-level pneumonia detection on chest x-rays with deep learning.  arXiv preprint arXiv:1711.05225, 2017.
  * [19] RSNA.  RSNA Intracranial Hemorrhage Detection.  https://www.kaggle.com/c/rsna-intracranial-hemorrhage-detection/overview, 2019\.  [Online].
  * [20] S. Serte and H. Demirel.  Deep learning for diagnosis of covid-19 using 3d ct scans.  Computers in biology and medicine, 132:104306, 2021.
  * [21] L. Shen, L. R. Margolies, J. H. Rothstein, E. Fluder, R. McBride, and W. Sieh.  Deep learning to improve breast cancer detection on screening mammography.  Scientific reports, 9(1):1–12, 2019.
  * [22] S. P. Singh, L. Wang, S. Gupta, H. Goli, P. Padmanabhan, and B. Gulyás.  3d deep learning on medical images: a review.  Sensors, 20(18):5097, 2020.
  * [23] T. T. Tran, H. H. Pham, T. V. Nguyen, T. T. Le, H. T. Nguyen, and H. Q. Nguyen.  Learning to automatically diagnose multiple diseases in pediatric chest radiographs using deep convolutional neural networks.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3314–3323, 2021.
  * [24] R. Yamashita, M. Nishio, R. K. G. Do, and K. Togashi.  Convolutional neural networks: an overview and application in radiology.  Insights into imaging, 9(4):611–629, 2018.
  * [25] S. Yun, D. Han, S. Oh, S. Chun, J. Choe, and Y. Yoo.  CutMix: Regularization strategy to train strong classifiers with localizable features.  In Proc. ICCV, pages 6023–6032, 2019.
  * [26] C. Zheng, X. Deng, Q. Fu, Q. Zhou, J. Feng, H. Ma, W. Liu, and X. Wang.  Deep learning-based detection for covid-19 from chest ct using weak label.  MedRxiv, 2020.