# An Alternative Practice of Tropical Convolution to Traditional Convolutional
Neural Networks

Shiqing Fan
School of Informatics
Xiamen University
Xiamen, Fujian 361005, China
<EMAIL_ADDRESS>
Liying Liu
School of Informatics
Xiamen University
Xiamen, Fujian 361005, China
<EMAIL_ADDRESS>Ye Luo111Corresponding Author.
This work is supported by National Natural Science Foundation of China (Grant
No. 61875169).
School of Informatics
Xiamen University
Xiamen, Fujian 361005, China
<EMAIL_ADDRESS>

###### Abstract

Convolutional neural networks (CNNs) have been used in many machine learning
fields. In practical applications, the computational cost of convolutional
neural networks is often high with the deepening of the network and the growth
of data volume, mostly due to a large amount of multiplication operations of
floating-point numbers in convolution operations. To reduce the amount of
multiplications, we propose a new type of CNNs called Tropical Convolutional
Neural Networks (TCNNs) which are built on tropical convolutions in which the
multiplications and additions in conventional convolutional layers are
replaced by additions and min/max operations respectively. In addition, since
tropical convolution operators are essentially nonlinear operators, we expect
TCNNs to have higher nonlinear fitting ability than conventional CNNs. In the
experiments, we test and analyze several different architectures of TCNNs for
image classification tasks in comparison with similar-sized conventional CNNs.
The results show that TCNN can achieve higher expressive power than ordinary
convolutional layers on the MNIST and CIFAR10 image data set. In different
noise environments, there are wins and losses in the robustness of TCNN and
ordinary CNNs.

CCS CONCEPTS · Computing methodologies · Machine learning · Machine learning
approaches · Neural networks
Keywords— Convolutional neural network, Tropical convolution, Minplus
convolution

##  1 Introduction

In recent years, convolutional neural networks (CNNs) have been widely used in
computer vision field of machine learning [1] tasks related to images and
videos, such as image classification [2, 3], face verification [4, 5], object
detection [6], image Segmentation [7, 8] and so on. But with the deepening of
the CNN layers, sometimes there will be billions of floating point
multiplications that make the computational cost of the convolutional neural
network extremely high. Although the emergence of graphics processing unit
(GPU) has increased the speed of deep convolutional networks, high-end GPU
cards require many other hardware support, which prevents them from being
easily installed on smart watches, mobile phones and other mobile devices.
Therefore, research on efficient forward reasoning deep neural network is very
necessary.

To speed up CNNs and cut down energy consumption, researchers have proposed
many approaches, such as changing the weight value to make the multiplication
into a bool operation [9, 10], or changing the traditional convolution
operation to reduce the large number of multiplications in the network [11,
12]. Among these attempts, the application of binary network can reduce
computational cost, but it will also cause the network to fail to maintain the
original recognition accuracy and converge slowly during training. Moreover,
in directly changing the direction of the convolution operation, some papers
use different methods to reduce or eliminate the multiplication in the
convolution, such as changing the metric operation between the input image and
the convolutional kernel to a metric where the multiplication is not dominant.
Our work continues this direction, trying to find a structure as a replacement
of the traditional convolution operation which can greatly reduce the number
of multiplications from an algebra that has been proven to have global
expression capabilities.

In network calculation [13], a convolution operation using minplus algebra is
commonly used to estimate the performance of communication network, which
replaces the nonlinear system with a linear system with the lower limit of the
nonlinear system to calculate the worst-case performance index. In such a
minplus convolution, the multiplication and addition operations in a
conventional convolution are replaced by addition and minimum operations
respectively. The arithmetic behind this convolution structure is directly
related to the mathematical theory of tropical semi-rings, which is fast
developing area in pure and applied mathematics [14].

It is well-known that executing additions is usually faster than executing
multiplications with less energy consumption. Therefore, the min-plus
convolution is a theoretically feasible solution to be applied to CNNs as a
replacement of conventional convolutions to reduce the overall computation
cost.

In this article, we propose a new type of CNNs called Tropical Convolutional
Neural Networks (TCNNs) in which the tropical convolution operators (including
both minplus and maxplus operators) are used in the convolution layer. When
applied to computer vision, a TCNN maximizes the use of addition to replace
the floating point multiplication between the convolutional kernel and the
pixels of input images when performing convolution computations, and takes the
minimum value or maximum value across the entire sliding window as output.
Throughout the process of feature extraction of the entire convolutional
network, the use of addition also has the capability to measure the similarity
of convolutional kernel and input image as in traditional CNNs. On multiple
benchmark classification datasets such as MNIST and CIFAR10, experimental
results show that TCNNs can reduce the proportion of deep neural network
multiplication while achieving higher accuracy compared with traditional CNNs.

The organization of this article is as follows. In Section 2, we study related
work on network calculus and multiplication substitution. In Section 3, we
present the tropical convolution operations and the basic structure of TCNNs.
In Section 4, we show several different network structure designs, and
evaluate the performance of various benchmark data sets on the TCNNs, and
makes a statistical comparison with traditional CNNs. Section 5 is a summary
of the paper.

##  2 Related Work

###  2.1 Min-plus Convolution

A lot of work has found that the superiority of an application of minplus
algebra to convolution calculation. Because of the features of this kind of
convolution, it has been widely used in different fields. One of the major
applications is network calculation [15] which provides a theoretical
framework for analyzing the performance guarantee of computer networks.
Specifically, it can calculate the worst-case limits of delay and buffer
requirements in the network. For example, Zubaydy et al. [16] proposed a
network calculus that can incorporate common statistical models of fading
channels and obtain statistical boundaries for delays and backlogs across
multiple nodes. And Tabatabaee et al. [17] used a network calculus approach
and found a strict service curve for Interleaved Weighted Round-Robin.

###  2.2 Network Demultiplication

Recently, many researchers have worked with efforts to reduce the cost of the
underlying circuit by cutting down the multiplication in deep neural networks.
One of the more typical methods to decrease multiplication is to improve
network parameters. For example, Courbariaux et al. [9] wrote a seminal paper
introducing BinaryConnect to train the deep learning network with binary
weights, in which multiply-accumulate operations are replaced by simple
accumulations. Similarly, Hubara et al. [10] proposed BNNs, which also used
binary activation besides binary weights to improve power-efficiency. On the
other hand, there are some other works that directly replace the
multiplication in the network calculation to lower the computational cost: Kim
et al. [11] analyzed and justified that multiplications can be approximated
while additions need to be exact in CNN Multiply Accumulate operations; XNOR-
nets [18] used the approximate binary value in the fully connected layer to
replace convolution with binary calculations; AdderNet [12] calculated the
1-norm distance between filters and input functions to take place of
multiplication. In a previous work, we proposed Min-Max-Plus Neural Networks
[19] as a new model of neural networks whose fitting ability can be more
concentrated in the nonlinear part which is composed of minplus layers and
maxplus layers with no multiplications performed.

##  3 Methods

###  3.1 Tropical Algebra and Tropical Convolution Operators

Here we start with the traditional convolution, a particular kind of integral
transform, usually defined as the integral of the product of the two functions
($f$ and $g$) after one is reversed and shifted as in Definition 3.1, where
$t$ can be any domain and does not necessarily represent the time domain.

######  Definition 3.1.

The _convolution_ of two functions $f$ and $g$ is

$(f*g)(t)=\int_{0}^{t}f(\tau)g(t-\tau)d\tau$

In tropical arithmetic over tropical semiring, the multiplication and addition
are replace by addition and minimum (or maximum) respectively. More precisely,
we have the following definition of tropical semiring.

######  Definition 3.2.

The _tropical semiring_ may refer to either the minplus algebra or the maxplus
algebra (we need to use both of them in this paper).

  1. (i)

The _minplus algebra_ is defined as

$\mathbb{R}_{\min}:=(\mathbb{R}\bigcup\\{\infty\\},\oplus,\odot)$

where the _tropical (lower) addition_ $\oplus$ and the _tropical
multiplication_ $\odot$ are defined respectively as $x\oplus y:=\min(x,y)$ and
$x\odot y:=x+y$ for all $x,y\in\mathbb{R}_{\min}$.

  2. (ii)

As a dual, the _maxplus algebra_ is defined as

$\mathbb{R}_{\max}:=(\mathbb{R}\bigcup\\{-\infty\\},\boxplus,\odot)$

where the _tropical (upper) addition_ $\boxplus$ is defined as $x\boxplus
y:=\max(x,y)$ for all $x,y\in\mathbb{R}_{\max}$.

Note that $\infty$ and $-\infty$ are the identities for tropical lower and
upper additions respectively. In practice, all computations are performed
within $\mathbb{R}$.

As widely used in network calculus, the minplus convolution is a notion
similar to traditional convolution (Definition 3.1) where operations are
performed in minplus algebra where multiplication and addition are replaced by
tropical multiplication (addition) and tropical lower addition (minimum)
respectively.

While min-plus convolution, which is widely used in network calculus, uses
plus and min operators to replace multiplication and sum operators in
respectively, and obtains the following Definition 3.3. Similarly, we also
have Max-Plus Convolution described as Definition 3.5.

######  Definition 3.3.

The _min-plus convolution_ of two functions $f$ and $g$ is defined as

$(f\otimes g)(t)=\inf_{0\geq\tau\geq t}(f(\tau)+g(t-\tau)).$

In addition, there is also a notion of minplus deconvolution as the inverse
operator of the convolution operation can be expressed as Definition 3.4.

######  Definition 3.4.

The minplus deconvolution of two functions $f$ and $g$ is defined as

$(f\oslash g)(t)=\sup{\tau\geq 0}(f(t+\tau)-g(\tau))$

As a dual to minplus convolution, we may define maxplus convolution
analogously.

######  Definition 3.5.

The maxplus convolution of two functions $f$ and $g$ is defined as

$(f\boxplus g)(t)=\sup_{0\geq\tau\geq t}(f(\tau)+g(t-\tau))$

Both minplus and maxplus convolution operators can be used either individually
or collaboratively in varied types of our proposed TCNNs.

###  3.2 Operators and Building Blocks

In a typical CNN (e.g., applied to a computer vision task), the convolutional
layer commonly refers to the operation of Definition 3.1 where the domain can
be higher dimensional. In particular, consider a convolutional kernel
$K\in\mathbb{R}^{k\times k\times C_{in}\times C_{out}}$ in an intermediate
layer of the neural network, where $C_{out}$ is the output channel size,
$C_{in}$ is the input channel size and k is kernel size. The input feature is
defined as $X\in\mathbb{R}^{H_{in}\times W_{in}\times C_{in}}$, where $H$ and
$W$ are the height and width of the feature, respectively. And the output
feature $Y\in\mathbb{R}^{H_{out}\times W_{out}\times C_{out}}$ can be computed
as the convolution of $X$ and $K$ by the following equation.

$Y(h,w,p)=\sum_{d=0}^{C_{in}}\sum_{i,j=0}^{k}(X(h+i,w+j,d)\times
K(i,j,d,p))+bias$ (1)

where $h$, $w$, $p$ are the indices of a pixel, and $bias$ is the bias of the
convolutional neural kernel. Currently, there are many ways to change
operations in convolution, but most of them contain some or many
multiplication operations, which makes the computational cost in the
convolutional layer high.

Figure 1: MinPlus and MaxPlus operators.

To minimize the beep of multiplication in the convolution calculation, we use
the idea of minplus convolution for reference, that is, simply change the
$(x\times y)$ in Equation 1 to $(x+y)$, which means all multiplication
operations will be replaced by addition. And we also change the original
process of calculating the sum in a sliding window to taking the
minimum/maximum value.

The calculation process of MinPlus and MaxPlus convolution operators are shown
in Figure 1. Since the two processes are very similar, we take MinPlus as an
example. (For MaxPlus convolution operator, simply change the minimum to
maximum.) Suppose there is an input image of size $7\times 7$, and we set the
size of the convolutional kernel to $3\times 3$ (that is, the size of the
sliding window is $3\times 3$) and the sliding step to 1. Then the calculation
process of the convolution operation in a sliding window can be divided into
two steps.

  1. Step 1:

Add the $3\times 3$ sliding window by the corresponding elements of the
convolutional kernel to obtain a new $3\times 3$ matrix, and use the minimum
of the new matrix as the extracted value of this sliding window.

  2. Step 2:

Slide the window with a stride of 1, and after computing all the values as
same as step 1, we can get the final output image of the size $5\times 5$.

###  3.3 The Tropical Convolution Layers

Now suppose we have a multi-channel input image. Based on the operators in
Figure 1, we can get the first step of the example in Figure 2, that is, the
$7\times 7\times 3$ input image ($3$ is $C_{in}$, the number of input
channels) passes through two $3\times 3$ convolutional kernels separately to
obtain a $5\times 5\times 3$ intermediate result each. After that, we can
either sum up or take the maximum value of the corresponding positions of each
channel of the intermediate result to obtain the output result in one single
channel. In this example, we finally get the feature map of size $5\times
5\times 2$, thus completing a forward process of Min(Max)Plus-Sum(Max)-Conv
layer. The whole operations above can be described as the following 6 types of
tropical convolutional layers:

Figure 2: An example of tropical convolutional layer.

######  Definition 3.6.

We define 6 types of tropical convolutional layers.

  1. (i)

MinPlus-Sum-Conv Layer (MinP-S)

$Y(h,w,p)=\sum_{d=0}^{C_{in}}\min_{i,j=0}^{k}(X(h+i,w+j,d)+K(i,j,d,p))$

  2. (ii)

MaxPlus-Sum-Conv Layer (MaxP-S)

$Y(h,w,p)=\sum_{d=0}^{C_{in}}\max_{i,j=0}^{k}(X(h+i,w+j,d)+K(i,j,d,p))$

  3. (iii)

MinPlus-Max-Conv Layer (MinP-Max)

$Y(h,w,p)=\max_{d=0}^{C_{in}}\min_{i,j=0}^{k}(X(h+i,w+j,d)+K(i,j,d,p))$

  4. (iv)

MaxPlus-Max-Conv Layer (MaxP-Max)

$Y(h,w,p)=\max_{d=0}^{C_{in}}\max_{i,j=0}^{k}(X(h+i,w+j,d)+K(i,j,d,p))$

  5. (v)

MinPlus-Min-Conv Layer (MinP-Min)

$Y(h,w,p)=\min_{d=0}^{C_{in}}\min_{i,j=0}^{k}(X(h+i,w+j,d)+K(i,j,d,p))$

  6. (vi)

MaxPlus-Max-Conv Layer (MaxP-Min)

$Y(h,w,p)=\min_{d=0}^{C_{in}}\max_{i,j=0}^{k}(X(h+i,w+j,d)+K(i,j,d,p))$

We note that these tropical convolution layers do not use multiplication at
all. Moreover, since min/max operations are performed, unlike conventional
convolution layers which are linear, tropical convolution layers are
essentially nonlinear layers, and incorporating them in the network can
increase the overall non-linear expression capabilities of the network.

Figure 3: The effect of color pictures after going through the MinP-S and
MaxP-S layers.

We use a classic processing image ”Lena” as an example to show the result of
this color picture passing through the MinP-S and MaxP-S layers, and the
results are shown in Figure 3. All the sizes of convolutional kernels in
MinP-S and MaxP-S are set to $16\times 16$, and the entry values of the
kernels in four output channels are random chosen from the interval $[-1,1]$
multiplied by $1$, $0.5$, $0.2$, $0.1$ respectively. It can be seen that the
result of MinP-S, shown in Figure 3.(a), and the result of MaxP-S, shown in
Figure 3.(b), can extract features at different levels of the image without
using multiplication. Furthermore, we observe that the darker parts of the
image are displayed more prominently when the values in the convolution
kernels become smaller through MinP-S, while MaxP-S shows the opposite effect
that the lighter parts are prominently displayed.

##  4 SOME EXPERIMENTS

###  4.1 TCNNs

In Section 3.2, we’ve defined several types of tropical convolution layers
with different calculation methods not involving multiplication. In practice,
we can make a variety of combinations of these convolution layers together
with some linear layers and choose from them an optimized one for a specific
application. Here are some of our solutions.

Figure 4: TCNNs.

Figure 4 shows four different network structures, which are composed of
tropical convolution operators, linear layers, common convolution layers and
so on. We use these structures to conduct preliminary experiments on
handwritten digit dataset MNIST. We compare a number of different
convolutional kernel size and sliding step size combinations using
visualization of the hidden layer’s feature map. We observe that in the
structure of Figure 4(a) and Figure 4(b), the first layer of MinP-S or MaxP-S
provides images like different contrasts and different styles on the premise
of retaining the main information of the original data. We think that this can
be regarded as a data feature extraction with data enhancement function. The
structure of tropical convolution makes the convolution layers have good
nonlinear expression ability without activation function. We also combine
tropical convolution layer with ordinary convolution layer, expecting to take
advantage of the features of both tropical convolution which can provide data
enhancement for the network at the first layer and ordinary convolution which
has the powerful information extraction ability for feature extraction. This
structure is shown in Figure 4(d). We will make statistics on the specific
task implementation effect in the next session.

###  4.2 Classification

In the final image classification results, we’ve also tested TCNNs with an
comparison to ordinary CNN. We uniformly use a 4-layer network, the latter two
layers are fixed as flatten layer and Dense layer, the first two layers use
different tropical convolutional modules, the output of the first layer is
unified to 15x15 4-channel feature map, and the output of the second layer is
unified to $7\times 7$. The four-channel feature map ensures that the
parameters of the four networks are consistent. Among them, the Conv-Conv
network only contains ordinary convolution layers and both layers have a large
number of multiplications; the first two layers of (MinP-S)+(MaxP-S) and
(MinP-Max)+(MaxP-Min) networks do not contain any multiplications; in
(MinP-S)+(Conv) network, a tropical convolution layer is followed by a layer
of ordinary convolution, and thus there is no multiplication in the first
layer.

Table 1: Classification accuracy of several TCNNs on image classification
tasks.

Network Structure MNIST CIFAR10 Conv+Conv+Flatten+Dense 92.18$\%$ 39.34$\%$
(MinP-S)+(MaxP-S)+Flatten+Dense 96.38$\%$ 46.53$\%$ (MinP-Max)+(MaxP-
Min)+Flatten+Dense 95.2$\%$ 52.77$\%$ (MinP-S)+Conv+Flatten+Dense 95.85$\%$
55.73$\%$

From the results of Table 1, we conclude that the networks containing the
tropical convolutional structure have much stronger information extraction and
expression capabilities than those containing only the ordinary convolution.
In particular, on color images, the network that uses both tropical
convolution and ordinary convolution achieves the highest accuracy, which also
reminds us that the combination of tropical convolution and ordinary
convolution on a specific data set can exert their respective advantages.

###  4.3 Noise Resistance

The classification model’s resistance to image noise is also an important part
of the model’s capabilities. Therefore, we have carried out several noise
processing strategies on the CIFAR10 color image data set, namely:

Noise1: Noise with standard normal distribution $*0.01$ added to all points.

Noise2: Noise with standard normal distribution $*0.1$ added to all points.

Noise3: Add noise to a random $5\%$ complete block of the picture.

Noise4: Add noise to random $5\%$ of pixels in the picture.

Table 2: Changes in accuracy of TCNNs under different noise strategies on
CIFAR10

Network structure Noise1 Noise2 Noise3 Noise4 Conv+Conv+Flatten+Dense
-0.61$\%$ -10.17$\%$ -15.02$\%$ -10.07$\%$ (MinP-S)+(MaxP-S)+Flatten+Dense
-0.21$\%$ -27.79$\%$ -8.30$\%$ -10.23$\%$ (MinP-Max)+(MaxP-Min)+Flatten+Dense
-0.87$\%$ -23.27$\%$ -10.10$\%$ -8.19$\%$ (MinP-S)+Conv+Flatten+Dense
-0.50$\%$ -28.17$\%$ -9.74$\%$ -6.80$\%$

These noise strategies have been applied to all the test-set images and tested
again using pre-trained models of various networks. From the results, we
observe that no model can achieve the best robustness on all noise strategies,
while those networks adopting tropical convolution modules have better test
results than those using only ordinary convolution on Noise3 and Noise4
strategies.

##  5 Conclusion

In this paper, we make a new attempt to remove multiplication in the image
convolution operation commonly used in computer vision. We’ve got inspirations
from tropical mathematics and min-plus convolution, and proposed TCNNs based
on tropical convolution structures for image convolution, including several
different similarity measurement operations between images and convolution
kernels, and the basic blocks of tropical convolution layers. Moreover, we
conduct experiments with real data on these TCNNs, in which we analyze the
feature map extracted by the hidden layers in the structure, and evaluate the
actual performance of TCNNs on image classification and its robustness to
different noises. From the results, compared to the traditional CNNs, TCNNs
have stronger non-linear expression ability in general, and its resistance to
different noises has its own advantages and disadvantages. From a practical
point of view, this proposal of TCNNs provides richer possibilities for us to
build deep neural networks. In the future, we can select suitable tropical
convolution modules for actual tasks and build networks for specific needs.
Regarding future work, we hope to apply the tropical convolution modules to
more types of deep neural networks to conduct a more in-depth analysis of this
emerging convolution design.

## References

  * [1] Li Deng and Dong Yu.  Deep learning: Methods and applications.  Found. Trends Signal Process., 7(3–4):197–387, June 2014.
  * [2] D. Ciregan, U. Meier, and J. Schmidhuber.  Multi-column deep neural networks for image classification.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 3642–3649, 2012.
  * [3] Dongmei Han, Qigang Liu, and Weiguo Fan.  A new image classification method using cnn transfer learning and web data augmentation.  Expert Systems with Applications, 95:43 – 56, 2018.
  * [4] Yi Sun, Yuheng Chen, Xiaogang Wang, and Xiaoou Tang.  Deep learning face representation by joint identification-verification.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, pages 1988–1996. Curran Associates, Inc., 2014.
  * [5] Nate Crosswhite, Jeffrey Byrne, Chris Stauffer, Omkar Parkhi, Qiong Cao, and Andrew Zisserman.  Template adaptation for face verification and identification.  Image and Vision Computing, 79:35 – 48, 2018.
  * [6] Zhaowei Cai and Nuno Vasconcelos.  Cascade r-cnn: Delving into high quality object detection.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [7] Liang-Chieh Chen, Jonathan T. Barron, George Papandreou, Kevin Murphy, and Alan L. Yuille.  Semantic image segmentation with task-specific edge detection using cnns and a discriminatively trained domain transform.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
  * [8] G. Wang, W. Li, M. A. Zuluaga, R. Pratt, P. A. Patel, M. Aertsen, T. Doel, A. L. David, J. Deprest, S. Ourselin, and T. Vercauteren.  Interactive medical image segmentation using deep learning with image-specific fine tuning.  IEEE Transactions on Medical Imaging, 37(7):1562–1573, 2018.
  * [9] Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David.  Binaryconnect: Training deep neural networks with binary weights during propagations.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28, pages 3123–3131. Curran Associates, Inc., 2015.
  * [10] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio.  Binarized neural networks.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, pages 4107–4115. Curran Associates, Inc., 2016.
  * [11] Min Soo Kim, Alberto Antonio Del Barrio Garcia, Hyunjin Kim, and Nader Bagherzadeh.  The effects of approximate multiplication on convolutional neural networks.  IEEE Transactions on Emerging Topics in Computing, 2021.
  * [12] Hanting Chen, Yunhe Wang, Chunjing Xu, Boxin Shi, Chao Xu, Qi Tian, and Chang Xu.  Addernet: Do we really need multiplications in deep learning?  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [13] J. . Le Boudec and P. Thiran.  A short tutorial on network calculus. i. fundamental bounds in communication networks.  In 2000 IEEE International Symposium on Circuits and Systems (ISCAS), volume 4, pages 93–96 vol.4, 2000.
  * [14] Lazarevich Litvinov, Grigori and Sergej Nikolaevi Sergeev.  Tropical and Idempotent Mathematics: International Workshop Tropical-07, Tropical and Idempotent Mathematics, August 25-30, 2007, Independent University of Moscow and Laboratory J.-V. Poncelet, volume 495.  American Mathematical Soc., 2009.
  * [15] J. . Le Boudec.  Application of network calculus to guaranteed service networks.  IEEE Transactions on Information Theory, 44(3):1087–1096, 1998\.
  * [16] H. Al-Zubaidy, J. Liebeherr, and A. Burchard.  A (min, $\times$) network calculus for multi-hop fading channels.  In 2013 Proceedings IEEE INFOCOM, pages 1833–1841, 2013.
  * [17] Seyed Mohammadhossein Tabatabaee, Jean-Yves Le Boudec, and Marc Boyer.  Interleaved weighted round-robin: A network calculus analysis.  arXiv e-prints, page arXiv:2003.08372, March 2020.
  * [18] Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi.  Xnor-net: Imagenet classification using binary convolutional neural networks.  In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling, editors, Computer Vision – ECCV 2016, pages 525–542, Cham, 2016. Springer International Publishing.
  * [19] Ye Luo and Shiqing Fan.  Min-max-plus neural networks.  arXiv preprint arXiv:2102.06358, 2021.


Igor Gitman1, Vitaly Lavrukhin1, Aleksandr Laptev1,2, Boris Ginsburg1

# Confidence-based Ensembles of End-to-End Speech Recognition Models

###### Abstract

The number of end-to-end speech recognition models grows every year. These
models are often adapted to new domains or languages resulting in a
proliferation of expert systems that achieve great results on target data,
while generally showing inferior performance outside of their domain of
expertise. We explore combination of such experts via confidence-based
ensembles: ensembles of models where only the output of the most-confident
model is used. We assume that models' target data is not available except for
a small validation set. We demonstrate effectiveness of our approach with two
applications. First, we show that a confidence-based ensemble of 5 monolingual
models outperforms a system where model selection is performed via a dedicated
language identification block. Second, we demonstrate that it is possible to
combine base and adapted models to achieve strong results on both original and
target data. We validate all our results on multiple datasets and model
architectures.

Index Terms: ensembles, confidence, end-to-end, speech recognition, language
identification, accent adaptation

100(20,290) To appear in _Proc. INTERSPEECH 2023, August 20-24, 2023, Dublin,
Ireland_

##  1 Introduction

Deep neural network (DNN) models are commonly combined in an ensemble to
improve predictions' accuracy. Most widely used types of ensembles include
bagging [1], boosting [2] and stacking [3]. A less popular ensembling approach
is to only use an output of a single model that is deemed best for the current
input. A typical way to pick the ``best'' output is to select a model with the
highest confidence score, which provides an estimate of how likely the output
is to be correct. We refer to such systems as _confidence-based ensembles_
(see Figure 1).

Figure 1: An illustration of a confidence-based ensemble applied to ASR. The
same input audio is passed to all models. They run in parallel to produce an
output text as well as an estimation of the output's correctness (confidence).
A confidence of each model can generally consist of multiple values (e.g.,
acoustic and language model scores). Model selection block can be implemented
as any mapping from confidence values to the index of the ``most confident''
model.

There exists a number of applications of confidence-based ensembles to
automatic speech recognition (ASR) and classification. Metze et al. [4] used
confidence scores of multiple monolingual Hidden Markov Model (HMM)-based ASR
models to improve language identification (LID) performance. This idea has
been later applied to build a hybrid DNN-HMM multilingual ASR model where a
combination of a dedicated LID block and a confidence-based model selection
was used [5, 6]. Wang et al. [7] extended this further to include additional
acoustic and language model scores and trained a neural network to make the
final model selection. Confidence-based ensembles have also been applied to
dialectal and accented speech recognition. Soto et al. [8] showed that a
confidence-based hypothesis selection improves recognition results on Arabic
dialects. Kukk and Alumäe [9] improved accented speech LID by directly
building text classification models on top of the ASR output.

While there are many applications of confidence-based ensembles of HMM-based
ASR systems, there is no study on using confidence to combine multiple _end-
to-end_ neural ASR models. We fill this gap by building ensembles of
connectionist temporal classification (CTC) [10] and recurrent neural network
transducer (RNNT) [11] models (using Conformer [12] as an encoder). There are
different ways how to define confidence measure for such models. A traditional
approach is to use a maximum probability of the output tokens [13]. Laptev et
al. [14] observed that using entropy-based measures helps to reduce networks'
overconfidence. It is possible to train separate models for confidence
estimation [15, 16], but such methods are not directly applicable to
pretrained models, so we do not consider them in this paper. Instead, we focus
on the collection of entropy-based measures proposed in [14] and
systematically study their effect on the quality of confidence-based
ensembles.

Table 1: Comparison of different confidence estimation methods for ensembles of Conformer models. All the numbers in the table represent an average per-dataset accuracy on the validation subsets. ``LID 5 languages'' is a combination of MCV, MLS and VoxPopuli data. For the ``LID 5 languages'' and ``SLR83'' columns we report mean ± standard deviation of results across all datasets. ``untuned max-prob'' confidence is defined as a product of probabilities of emitted tokens (including blanks). ``default confidence'' corresponds to Rényi entropy with linear normalization, mean aggregation (excluding blanks), $T=1.0,\alpha=0.25$. ``tuned confidence'' is the best confidence measure, which is generally different for each dataset. | Conformer-Transducer | Conformer-CTC
---|---|---
Confidence | LID 5 languages | CORAAL | SLR83 | LID 5 languages | CORAAL | SLR83
untuned max-prob | 98.18 ± 0.77 | 88.00 | 75.32 ± 4.35 | 98.76 ± 0.82 | 84.89 | 57.84 ± 4.53
default confidence | 99.13 ± 0.44 | 94.13 | 81.85 ± 4.73 | 99.37 ± 0.39 | 91.39 | 77.08 ± 5.23
tuned confidence | 99.39 ± 0.32 | 95.31 | 93.60 ± 1.88 | 99.48 ± 0.37 | 93.31 | 90.37 ± 4.35

We use two applications to evaluate the effectiveness of our approach. First,
we consider a task of multilingual ASR. The current trend in building
multilingual end-to-end ASR models is to train a single network that can
recognize multiple languages [17, 18, 19]. Another popular line of work is to
build mixture-of-expert systems that use separate sub-networks specializing in
different languages [20, 21]. However, such techniques require significant
computational resources for training and might produce worse recognition than
monolingual predictors [18]. An alternative approach is to combine monolingual
models into a multilingual system using a dedicated language identification
(LID) block [6]. We show that confidence-based ensembles outperform dedicated
LID models on long audio segments ($>5$ seconds) and can be combined with LID
model's scores to improve predictions on short segments.

We then show that it is possible to use confidence-based ensembles for the
models sharing the same input language. We consider a task of accent and
dialect adaptation. A typical solution to this problem is to finetune an ASR
model on the target data. A common issue of this approach is that model's
performance on the original domain might significantly degrade, which is known
as catastrophic forgetting [22]. While many techniques have been proposed to
address this issue [23, 24], they often require access to the original
training data, which might not be available. Majumdar et al. [25] proposes
using limited training strategy and regularized adapter modules to reduce the
degradation on the source domain without access to the original training data.
In this paper we show that a simple confidence-based combination of original
and finetuned models achieves significantly better results. Additionally, we
demonstrate that the proposed ensemble can interpolate between better
performance on source or target domain via a _runtime_ change in the weights
of the confidence scores.

A clear limitation of most ensemble systems is that required computation grows
linearly with each added model. To address this problem, we show that it is
possible to use an output of intermediate layers for confidence estimation. We
demonstrate this technique through an ensemble of models finetuned with
intermediate CTC loss [26] and show that using only 4 out of 18 layers is
enough for accurate model selection. We apply this technique to both CTC and
Transducer models and find that it generally improves the base models'
accuracy.

Summing up, our findings are as follows:

  * •

Confidence-based ensembles of end-to-end ASR models have better recognition
accuracy than a system with a dedicated LID block on long audio segments. Our
method provides approximately $10\%$ relative word-error-rate reduction (WERR)
compared to the state-of-the-art LID systems on 3 public multilingual
datasets.

  * •

Our method can be used to significantly limit catastrophic forgetting during
model adaptation. Compared to the constraint adaptation of [25], confidence-
based ensembles show $10$–$50\%$ WERR on the target data, while being $2\%$
relatively better on the source domain.

  * •

Confidence can be reliably estimated from the output of early layers (4 out of
18) if the model was trained with intermediate CTC loss [26]. This reduces the
runtime cost of adding a new model to the ensemble by $4.5$ times.

##  2 Method

An illustration of confidence-based ensembles is presented in Figure 1. This
general structure allows for any vector of confidence values to be produced by
each model and any non-linear mapping of the confidence vectors to the model
indices to be used as a ``model selection block''. In our experiments we adopt
a simpler pipeline. We only use a single confidence score for each model and
train a logistic regression (LR) on a few audio samples to predict matching
model index from the generated confidence values.

###  2.1 Model selection

Formally, our model selection block is defined as follows. Let's denote the
set of models in the ensemble as $\mathcal{M}=\\{m_{k}\\}_{k=1}^{M}$ and the
set of evaluation datasets as $\mathcal{D}=\\{d_{i}\\}_{i=1}^{D}$. We assume
that there is a surjective mapping $L:\mathcal{D}\rightarrow\mathcal{M}$ that
defines which model is considered ``correct'' for which dataset. We select a
small set of $N$ utterances111We use $N=100$ in our experiments, but for
datasets with a lot of variability it might be better to use larger training
data. of the _training_ subset of each dataset $d_{i}$ denoted as
$\\{t_{i}^{j}\\}_{j=1}^{N}$. Finally, let's define $c_{k}(t_{i}^{j})$ as the
confidence score of the model $k$ computed on the sample $j$ from the dataset
$i$. Then we train $\text{LR}:\mathcal{R}^{M}\rightarrow\mathcal{M}$ to map
$x_{i}^{j}=[c_{1}(t_{i}^{j}),c_{2}(t_{i}^{j}),...,c_{M}(t_{i}^{j})]\rightarrow
y_{i}^{j}=L(d_{i})$.

Recall that logistic regression is a linear classifier that only needs to
train $n+1$ coefficients for $n$ models. E.g., in the case of a 2-model
ensemble, LR produces the following model selection rule: $ac_{1}+bc_{2}>c$.
While a more powerful non-linear functions might achieve better results, using
a simple LR allows us to train model selection block with only a few audio
samples and helps to avoid overfitting.

###  2.2 Evaluation metrics

To evaluate the accuracy of the ASR models we use a traditional word-error-
rate (WER) metric. To evaluate the accuracy of the model selection within
ensemble we use the _average per-dataset accuracy ( $A_{\text{avg}}$)_ metric:

$A_{\text{avg}}=\frac{1}{D}\sum_{i=1}^{D}\frac{1}{D_{i}}\sum_{j=1}^{D_{i}}\left[\text{LR}\left(c_{1}(v_{i}^{j}),...,c_{m}(v_{i}^{j})\right)=L\left(d_{i}\right)\right]$

where $v_{i}^{j},j=1..D_{i}$ are the _validation/test_ utterances from dataset
$d_{i}$ and $D_{i}$ is the size of the validation/test set. $[X=Y]$ is an
indicator function that equals $1$ if $X=Y$ and $0$ otherwise. Put simply, an
average per-dataset accuracy is a mean of the model prediction accuracies
across all datasets. We use this metric instead of a regular multi-class
prediction accuracy in order to account for label imbalances present in some
dataset combinations. E.g., multilingual datasets can be very imbalanced, but
we assume that the performance on each language is of equal importance.

##  3 Experiments

For all experiments we followed the same evaluation setup. We fit LR on 100
training utterances and tuned LR's hyperparameters (regularization strength
and class weights in case of imbalanced datasets) maximizing the
$A_{\text{avg}}$ metric on the validation subsets of all datasets. In the
following tables we report the results on the test subsets unless noted
otherwise. All experiments were performed using NeMo
toolkit222https://github.com/NVIDIA/NeMo [27].

###  3.1 Datasets

####  3.1.1 Multilingual ASR.

To evaluate the performance of our method we used 3 public multilingual ASR
datasets: Mozilla Common Voice (MCV) [28], Multilingual LibriSpeech (MLS) [29]
and VoxPopuli [30]. For all datasets we used standard train, validation and
test splits. We refer the reader to the original papers for additional
information about the used datasets. We built ensembles that supports five
languages: English, Italian, Spanish, German and French. For all languages we
used ``Conformer Large'' models from NVIDIA NGC catalog.

####  3.1.2 Accent and dialect adaptation.

We tested our method on 2 public datasets: Corpus of Regional African American
Language (CORAAL) [31] and Open-source Multi-speaker Corpora of the English
Accents in the British Isles (SLR83) [32]. We manually split CORAAL into
train, validation and test splits containing 18, 3 and 22 hours respectively.
The training, validation and test sets contained audio from different
speakers. For SLR83 we re-used data splits from [25]. To be able to have
direct comparison with [25] we used Conformer Large models trained on
LibriSpeech dataset [33] as the base for model adaptation on SLR83 datasets.
For CORAAL, we started finetuning from Conformer Large trained on 24325 hours
of English speech from NVIDIA NGC catalog.

###  3.2 Impact of the confidence measure

In this section we study the effect of choosing a confidence estimation method
on the ensemble's quality. We evaluated Gibbs, Tsallis [34] and Rényi [35]
entropies (with both linear and exponential normalization) proposed in [14] as
well as the maximum probability as confidence measures. To aggregate
confidence information across time steps we tested minimum, maximum, mean and
product aggregation functions. Both RNNT and CTC models use a special blank
symbol to align input to the output. We test both including and ignoring
blanks in the confidence aggregation. For all measures we tuned the softmax's
temperature $T\in[0.01,0.05,0.1,0.25,0.5,0.75,1.0,2.0,5.0,10.0]$. For the
entropy-based measures we also ran a grid-search over the parameter
$\alpha\in[0.1,0.2,0.25,0.33,0.5,1.0]$. Overall, the search space spans 2960
combinations of confidence measures.

While the best performing measure for each dataset is typically different, we
found that using _Rényi entropy with linear normalization, mean aggregation,
$T=1.0,\alpha=0.25$ and blank symbols excluded_ tends to perform well across
all evaluated tasks333This measure might not be well-calibrated as it is tuned
to optimize the model-selection accuracy.. Table 1 shows the comparison of
using the product of probabilities of the output tokens (untuned max-prob),
Rényi entropy with the aforementioned parameters (default confidence) and the
best confidence measure for each dataset (tuned confidence). The proposed
default confidence always outperforms maximum probability and can be further
improved if confidence hyperparameters are tuned for each dataset.

Due to the space constraints all subsequent results are reported with default
confidence and only for Transducer models.

Table 2: LID accuracy and WER on VoxPopuli, MLS and MCV datasets. All numbers show an average of the results across all 5 languages. Confidence-based ensembles outperform all baseline LID systems. LID model | VoxPopuli | MLS | MCV
---|---|---|---
_LID accuracy_
ECAPA-TDNN-CE [36] | 96.29 | 98.41 | 94.42
XLS-R [37] | 97.63 | 98.69 | 97.47
confidence-based | 98.76 | 99.69 | 98.82
_WER_
oracle | 9.44 | 5.89 | 6.05
ECAPA-TDNN-CE [36] | 11.26 | 6.90 | 9.44
XLS-R [37] | 10.53 | 6.78 | 7.23
confidence-based | 9.57 | 6.04 | 6.24
Table 3: Model selection accuracy with different audio duration on VoxPopuli dataset. Only utterances with more than 15 seconds of audio were used to have the same evaluation set for all durations. ``Combination'' column shows that using a combination of confidence and LID scores can improve the results for short segments. Audio duration | Confidence | XLS-R | Combination
---|---|---|---
3 sec | 90.63 | 93.45 | 96.00
5 sec | 95.50 | 95.45 | 97.56
10 sec | 98.05 | 97.07 | 98.86
15 sec | 99.02 | 97.56 | 99.46
full audio | 99.57 | 97.67 | 99.57
Table 4: Comparison of the WER for different model adaptation techniques on the SLR83 dataset. The LibriSpeech test-other WER is averaged across all speakers. We abbreviate each speaker id using the first two letters of speaker's dialect and the first letter of gender (e.g., ``Ir-M'' stands for ``Irish-English Male''). Our ``base'' model is the same as in [25], but the ``finetuned'' model is generally better on the target data as we do not constraint training. Model | LS other | Ir-M | Mi-F | Mi-M | No-F | No-M | Sc-F | Sc-M | So-F | So-M | We-F | We-M
---|---|---|---|---|---|---|---|---|---|---|---|---
base | 5.12 | 20.69 | 9.61 | 11.25 | 11.11 | 10.18 | 12.26 | 11.94 | 9.70 | 10.22 | 8.51 | 11.46
finetuned | 7.85 ± 2.28 | 9.17 | 7.51 | 8.36 | 7.60 | 6.87 | 8.32 | 6.35 | 4.14 | 3.59 | 4.67 | 6.49
constrained [25] | 5.40 ± 0.05 | 15.86 | 8.40 | 9.43 | 9.33 | 8.54 | 10.00 | 8.68 | 7.73 | 7.90 | 6.64 | 9.70
ensemble | 5.26 ± 0.11 | 9.17 | 7.51 | 8.36 | 7.63 | 6.78 | 8.40 | 6.82 | 4.64 | 3.98 | 4.79 | 6.70
Table 5: WER after model adaptation on CORAAL dataset. We trained ensemble to select ``base'' model for both LibriSpeech and VoxPopuli datasets and ``finetuned'' model for CORAAL dataset. The last two rows demonstrate capability of ensemble to prioritize original vs target domain via a runtime adjustment of logistic regression probability threshold. Model | LS other | VoxPopuli | CORAAL
---|---|---|---
base | 3.73 | 6.37 | 31.23
finetuned | 5.25 | 10.51 | 8.29
ensemble default | 3.82 | 6.57 | 8.72
tuned for base | 3.76 | 6.39 | 9.77
tuned for target | 4.31 | 8.85 | 8.33

###  3.3 Multilingual ASR

In this section we evaluate the performance of the confidence-based ensembles
for the multilingual ASR task. We compared our method with several state-of-
the-art LID models [36, 37]. Since these models were trained to recognize much
larger set of languages, we constrained them to only select the highest
probability index out of the 5 evaluated languages. Table 2 shows LID accuracy
and WER of the resulting systems on VoxPopuli, MLS and MCV datasets. Table 3
shows how the LID accuracy changes for different audio duration. Our
experiments demonstrate that while confidence-based ensembles outperform
dedicated LID models on the long audio segments ($>5$ seconds), they
underperform the best baseline for shorter durations. Last column of Table 3
shows that using a combination of confidence and LID scores as an input to
logistic regression obtains significantly better predictions for the short
segments.

###  3.4 Accent and dialect adaptation

For all finetuning experiments in this section we ran training for 100 epochs
on a single 16GB NVIDIA V100 GPU re-using training configuration of the base
model, except for the batch size and learning rate parameters. Batch size was
selected to fully utilize GPU memory and learning rate was tuned over 8 log-
uniform grid points in $[10^{-7},10^{-3}]$. Table 4 shows the comparison of
the confidence-based ensembles with the constraint adaptation approach of [25]
on the SLR83 dataset. Our method achieves significantly better accuracy on
both original and target domains. Note that for one dialect confidence-based
ensemble outperforms the finetuned model. This is possible because the base
model can be ``incorrectly'' selected on utterances where it has lower WER
than the finetuned model.

Table 5 shows the results of the confidence-based ensemble after adaptation on
the CORAAL dataset. The last two rows of the table demonstrate an ability of
the ensemble to trade-off between performance on the target and the original
domain via a runtime change of the logistic regression threshold. Based on the
specific requirements users can adjust the performance of the model with a
simple configuration change.

###  3.5 Decreasing runtime cost

A clear limitation of model ensembles is that runtime cost increases linearly
with ensemble size. To partially overcome this, we propose to use outputs of
the intermediate layers for model selection444This approach requires
finetuning models and thus can only be used if the training data is
available.. Table 6 shows that it is possible to get a high-quality confidence
estimate using intermediate encoder layers. We finetuned all models for 100
epochs on the combination of MCV, MLS and VoxPopuli datasets using
intermediate CTC loss [26] applied to different layers and used the output of
those layers to compute confidence scores. Following the original paper, we
added the new loss with coefficient of $0.3$. We re-used training
configuration of the base models except the learning rate which was 10 times
smaller. Unlike the original paper we applied this technique to both CTC and
Transducer models and it generally increased models' accuracy because of the
extra regularization. Surprisingly, even though WER of intermediate layers is
significantly worse, using intermediate confidence has only a minor reduction
in the model-selection accuracy.

Table 6: Model selection accuracy using confidence estimation from different layers. All models have been finetuned with intermediate CTC loss [26]. Confidence from | CORAAL | VoxPopuli | MLS
---|---|---|---
Layer 4 | 91.58 | 98.67 | 99.80
Layer 9 | 93.32 | 98.08 | 99.75
Layer 18 (final) | 94.13 | 98.76 | 99.69

##  4 Conclusion

In this paper we showed that confidence-based ensembles of end-to-end ASR
models can improve state-of-the-art results for several speech recognition
problems. Our method achieves close to $10\%$ WERR on 3 multilingual ASR
datasets compared to systems using a dedicated LID block. It also improves
results on accent and dialect adaptation tasks by $10$–$50\%$ WERR.

However, there are several limitations that need to be acknowledged.
Confidence-based ensembles are not well suited for latency-critical
applications as they require a few seconds of audio to select the most
confident model. The runtime cost grows linearly with each added model, which
limits the practically useful ensemble size. Finally, given enough compute and
data, it is likely possible to build specialized models that would outperform
confidence-based ensembles on most tasks.

Taking these limitations into account, we think that confidence-based
ensembles can be useful in a wide range of applications beyond what is covered
in our experiments. We consider building confidence-based ensembles as a
general technique to combine multiple black-box expert models into a single
system that achieves competitive results on all target domains. The models can
be combined with almost no additional training and without the need to share
either data or model weights. We think that these properties can enable new
applications of speech technology for users who don't have access to large
compute clusters or big training datasets.

## References

  * [1] D. W. Opitz and R. F. Maclin, ``An empirical evaluation of bagging and boosting for artificial neural networks,'' in _Proceedings of International Conference on Neural Networks (ICNN'97)_ , vol. 3. IEEE, 1997, pp. 1401–1405.
  * [2] H. Schwenk and Y. Bengio, ``Boosting neural networks,'' _Neural computation_ , vol. 12, no. 8, pp. 1869–1887, 2000.
  * [3] L. Deng, D. Yu, and J. Platt, ``Scalable stacking and learning for building deep architectures,'' in _2012 IEEE International conference on Acoustics, speech and signal processing (ICASSP)_. IEEE, 2012, pp. 2133–2136.
  * [4] F. Metze, T. Kemp, T. Schaaf, T. Schultz, and H. Soltau, ``Confidence measure based language identification,'' in _ICASSP_ , 2000.
  * [5] H. Lin, J.-t. Huang, F. Beaufays, B. Strope, and Y.-h. Sung, ``Recognition of multilingual speech in mobile applications,'' in _ICASSP_ , 2012.
  * [6] J. Gonzalez-Dominguez, D. Eustis, I. Lopez-Moreno, A. Senior, F. Beaufays, and P. J. Moreno, ``A real-time end-to-end multilingual speech recognition architecture,'' _IEEE Journal of selected topics in signal processing_ , vol. 9, no. 4, pp. 749–759, 2014.
  * [7] S. Wang, L. Wan, Y. Yu, and I. L. Moreno, ``Signal combination for language identification,'' _arXiv:1910.09687_ , 2019.
  * [8] V. Soto, O. Siohan, M. Elfeky, and P. Moreno, ``Selection and combination of hypotheses for dialectal speech recognition,'' in _ICASSP_ , 2016.
  * [9] K. Kukk and T. Alumäe, ``Improving language identification of accented speech,'' in _Interspeech_ , 2022.
  * [10] A. Graves, S. Fernández, F. Gomez, and J. Schmidhuber, ``Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks,'' in _ICML_ , 2006.
  * [11] A. Graves, ``Sequence transduction with recurrent neural networks,'' in _ICML_ , 2012.
  * [12] A. Gulati, J. Qin, C.-C. Chiu, N. Parmar, Y. Zhang, J. Yu, W. Han, S. Wang, Z. Zhang, Y. Wu _et al._ , ``Conformer: Convolution-augmented transformer for speech recognition,'' in _Interspeech_ , 2020.
  * [13] D. Hendrycks and K. Gimpel, ``A baseline for detecting misclassified and out-of-distribution examples in neural networks,'' in _ICLR_ , 2017.
  * [14] A. Laptev and B. Ginsburg, ``Fast entropy-based methods of word-level confidence estimation for end-to-end automatic speech recognition,'' in _Spoken Language Technology Workshop (SLT)_ , 2023.
  * [15] A. Woodward, C. Bonnín, I. Masuda, D. Varas, E. Bou-Balust, and J. C. Riveiro, ``Confidence measures in encoder-decoder models for speech recognition.'' in _Interspeech_ , 2020, pp. 611–615.
  * [16] Q. Li, D. Qiu, Y. Zhang, B. Li, Y. He, P. C. Woodland, L. Cao, and T. Strohman, ``Confidence estimation for attention-based sequence-to-sequence models for speech recognition,'' in _ICASSP_ , 2021.
  * [17] S. Punjabi, H. Arsikere, Z. Raeesy, C. Chandak, N. Bhave, A. Bansal, M. Müller, S. Murillo, A. Rastrow, A. Stolcke _et al._ , ``Joint ASR and language identification using RNN-T: An efficient approach to dynamic language switching,'' in _ICASSP_ , 2021.
  * [18] B. Li, T. N. Sainath, R. Pang, S.-y. Chang, Q. Xu, T. Strohman, V. Chen, Q. Liang, H. Liu, Y. He _et al._ , ``A language agnostic multilingual streaming on-device asr system,'' in _Interspeech_ , 2022.
  * [19] L. Zhou, J. Li, E. Sun, and S. Liu, ``A configurable multilingual model is all you need to recognize all languages,'' in _ICASSP_ , 2022.
  * [20] N. Gaur, B. Farris, P. Haghani, I. Leal, P. J. Moreno, M. Prasad, B. Ramabhadran, and Y. Zhu, ``Mixture of informed experts for multilingual speech recognition,'' in _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2021, pp. 6234–6238.
  * [21] Y. Kwon and S.-W. Chung, ``MoLE : Mixture of language experts for multi-lingual automatic speech recognition,'' in _ICASSP_ , 2023.
  * [22] R. M. French, ``Catastrophic forgetting in connectionist networks,'' _Trends in cognitive sciences_ , vol. 3, no. 4, pp. 128–135, 1999.
  * [23] Y. Zhao, C. Ni, C.-C. Leung, S. Joty, E. S. Chng, and B. Ma, ``A unified speaker adaptation approach for ASR,'' in _EMNLP_ , 2021.
  * [24] D. Hwang, A. Misra, Z. Huo, N. Siddhartha, S. Garg, D. Qiu, K. C. Sim, T. Strohman, F. Beaufays, and Y. He, ``Large-scale ASR domain adaptation using self-and semi-supervised learning,'' in _ICASSP_ , 2022.
  * [25] S. Majumdar, S. Acharya, V. Lavrukhin, and B. Ginsburg, ``Damage control during domain adaptation for transducer based automatic speech recognition,'' in _Spoken Language Technology Workshop (SLT)_. IEEE, 2023, pp. 130–135.
  * [26] J. Lee and S. Watanabe, ``Intermediate loss regularization for ctc-based speech recognition,'' in _ICASSP_ , 2021.
  * [27] O. Kuchaiev, J. Li, H. Nguyen, O. Hrinchuk, R. Leary, B. Ginsburg, S. Kriman, S. Beliaev, V. Lavrukhin, J. Cook _et al._ , ``NeMo: a toolkit for building AI applications using neural modules,'' in _Systems for ML Workshop, NeurIPS_ , 2019.
  * [28] R. Ardila, M. Branson, K. Davis, M. Kohler, J. Meyer, M. Henretty, R. Morais, L. Saunders, F. Tyers, and G. Weber, ``Common voice: A massively-multilingual speech corpus,'' in _Proceedings of the 12th Language Resources and Evaluation Conference_ , 2020, pp. 4218–4222.
  * [29] V. Pratap, Q. Xu, A. Sriram, G. Synnaeve, and R. Collobert, ``MLS: A large-scale multilingual dataset for speech research,'' in _Interspeech_ , 2020.
  * [30] C. Wang, M. Riviere, A. Lee, A. Wu, C. Talnikar, D. Haziza, M. Williamson, J. Pino, and E. Dupoux, ``Voxpopuli: A large-scale multilingual speech corpus for representation learning, semi-supervised learning and interpretation,'' in _Proc, of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , 2021, pp. 993–1003.
  * [31] T. Kendall and C. Farrington, ``The corpus of regional African American language. The Corpus of Regional African American Language. Version 2021.07. Eugene, OR,'' _The Online Resources for African American Language Project_ , 2021.
  * [32] I. Demirsahin, O. Kjartansson, A. Gutkin, and C. Rivera, ``Open-source multi-speaker corpora of the English accents in the British Isles,'' in _Proc. of the Twelfth Language Resources and Evaluation Conference_ , 2020, pp. 6532–6541.
  * [33] V. Panayotov, G. Chen, D. Povey, and S. Khudanpur, ``Librispeech: an ASR corpus based on public domain audio books,'' in _ICASSP_. IEEE, 2015.
  * [34] C. Tsallis, ``Possible generalization of Boltzmann-Gibbs statistics,'' _Journal of statistical physics_ , 1988.
  * [35] A. Rényi _et al._ , ``On measures of entropy and information,'' in _Proceedings of the fourth Berkeley symposium on mathematical statistics and probability_ , 1961.
  * [36] B. Desplanques, J. Thienpondt, and K. Demuynck, ``ECAPA-TDNN: Emphasized Channel Attention, Propagation and Aggregation in TDNN Based Speaker Verification,'' in _Interspeech_ , 2020.
  * [37] A. Babu, C. Wang, A. Tjandra, K. Lakhotia, Q. Xu, N. Goyal, K. Singh, P. von Platen, Y. Saraf, J. Pino, A. Baevski, A. Conneau, and M. Auli, ``XLS-R: self-supervised cross-lingual speech representation learning at scale,'' in _Interspeech_ , 2022.


# Wait, That Feels Familiar: Learning to Extrapolate Human Preferences for
Preference-Aligned Path Planning

Haresh Karnan1∗, Elvin Yang2∗†, Garrett Warnell3,4, Joydeep Biswas3, Peter
Stone3,5 1Walker Department of Mechanical Engineering, The University of Texas
at Austin<EMAIL_ADDRESS>of Michigan, Ann Arbor,
<EMAIL_ADDRESS>of Computer Science, The University of Texas at
Austin, {joydeepb<EMAIL_ADDRESS>Research Laboratory,
<EMAIL_ADDRESS>AI, North America*Equal Contribution,
sorted alphabetically by last name$\dagger$ Work done while at UT Austin

###### Abstract

Autonomous mobility tasks such as last-mile delivery require reasoning about
operator-indicated preferences over terrains on which the robot should
navigate to ensure both robot safety and mission success. However, coping with
_out of distribution_ data from novel terrains or appearance changes due to
lighting variations remains a fundamental problem in visual terrain-adaptive
navigation. Existing solutions either require labor-intensive manual data re-
collection and labeling or use hand-coded reward functions that may not align
with operator preferences. In this work, we posit that operator preferences
for visually novel terrains, which the robot should adhere to, can often be
extrapolated from established terrain preferences within the _inertial-
proprioceptive-tactile_ domain. Leveraging this insight, we introduce
Preference extrApolation for Terrain-awarE Robot Navigation (patern), a novel
framework for extrapolating operator terrain preferences for visual
navigation. patern learns to map inertial-proprioceptive-tactile measurements
from the robot’s observations to a representation space and performs nearest-
neighbor search in this space to estimate operator preferences over novel
terrains. Through physical robot experiments in outdoor environments, we
assess patern’s capability to extrapolate preferences and generalize to novel
terrains and challenging lighting conditions. Compared to baseline approaches,
our findings indicate that patern robustly generalizes to diverse terrains and
varied lighting conditions, while navigating in a preference-aligned manner.

##  I INTRODUCTION

To ensure the safety, mission success, and efficiency of autonomous mobile
robots in outdoor settings, the ability to visually discern distinct terrain
features is paramount. This necessity stems not only from direct implications
for robot functionality but also from the operator-indicated terrain
preferences that the robot must adhere to. Often, these preferences are
motivated by the desire the protect delicate landscapes, such as flower beds,
or to mitigate potential wear and tear on the robot by avoiding hazardous
surfaces. However, during autonomous operations, ground robots frequently face
unfamiliar terrains [1, 2] and dynamic real-world conditions such as varied
lighting, that lie outside the distribution of visually recognized terrains
where operator preferences have been pre-defined. This mismatch presents
significant challenges for vision-based outdoor navigation [3].

Figure 1: An illustration of the intuition behind preference extrapolation in
patern. Operator preferences of the three known terrains are marked
numerically, with 1 being the most preferred and 3 being the least preferred.
In the pre-adaptation stage, a novel terrain (pebble pavement) is encountered
and the preference order of its nearest neighbor (concrete) inferred from
proprioceptive representations is transferred (extrapolated) to the
corresponding samples in the visual representation space. The extrapolated
preference order is used to update both the visual representations and the
visual preference function. The post-adaptation stage shows extrapolated
preferences in the updated visual representation space for the novel terrain.

Equipping robots with the capability to handle novel terrain conditions for
preference-aligned path planning is a challenging problem in visual
navigation. Prior approaches to address this problem include collecting more
expert demonstrations [4, 5, 6], labeling additional data [7, 8, 9], and
utilizing hand-coded reward functions to assign traversability costs [10, 11,
12]. While these approaches have been successful at visual navigation,
collecting more expert demonstration data and labeling may be labor-intensive
and expensive, and utilizing hand-coded reward functions may not always align
with operator preferences. We posit that in certain cases, while the terrain
may look visually distinct in comparison to prior experience, similarities in
the inertial-proprioceptive-tactile space may be leveraged to extrapolate
operator preferences over such terrains, that the robot must adhere to. For
instance, assuming a robot has experienced concrete pavement and marble rocks,
and prefers the former over the latter (as expressed by the operator), when
the robot experiences a visually novel terrain such as pebble pavement which
feels inertially similar to traversing over concrete pavement, it is more
likely that the operator might also prefer pebble pavement over marble rocks.
While it is not possible to know the operator’s true preferences without
querying them, we submit that in cases where the operator is unavailable,
hypothesizing preferences through extrapolation from the inertial-
proprioceptive-tactile space is a plausible way to estimate traversability
preferences for novel terrains.

Leveraging the intuition of extrapolating operator preferences for visually
distinct terrains that are familiar in the inertial-proprioceptive-tactile
space (collectively known as proprioceptive for brevity), we introduce
Preference extrApolation for Terrain-awarE Robot Navigation (patern) 111A
preliminary version of this work was presented at the PT4R workshop at ICRA
2023 [13], a novel framework for extrapolating operator terrain preferences
for visual navigation. patern learns a proprioceptive latent representation
space from the robot’s prior experience and uses nearest-neighbor search in
this space to estimate operator preferences for visually novel terrains. Fig.
1 provides an illustration of the intuition behind preference extrapolation in
patern. We conduct extensive physical robot experiments on the task of
preference-aligned off-road navigation, evaluating patern against state-of-
the-art approaches, and find that patern is empirically successful with
respect to preference alignment and in adapting to novel terrains and lighting
conditions seen in the real world.

##  II RELATED WORK

In this section, we review related work in visual off-road navigation, with a
focus on preference-aligned path planning.

###  II-A Supervised Methods

To learn terrain-aware navigation behaviors, several prior methods have been
proposed that used supervised learning from large curated datasets [8, 9] as
supervision to pixel-wise segment terrains [7]. Guan et al. [7] propose a
transformer-based architecture (ganav) to segment terrains, and manually
assign traversability costs for planning. While successful at preference-
aligned navigation, fully-supervised methods suffer from domain shift on novel
terrains and may require additional labeling.

###  II-B Self-Supervised Methods

To alleviate the need for large-scale datasets for visual navigation, several
self-supervised learning methods have been proposed that learn from data
collected on the robot [14]. Specifically, prior methods in this category have
explored using inertial Fourier features [10], contact vibrations [15],
proprioceptive feedback [16], odometry errors [12], future predictive models
[11], acoustic features [17], and trajectory features [18] to learn
traversability costs for visual navigation. While successful in several visual
navigation tasks such as comfort-aware navigation [10], such methods use a
hand-coded reward/cost model to solve a specific task and do not reason about
operator preferences over terrains. In contrast with prior methods, patern
utilizes the prior experience of the robot and extrapolates operator
preferences to novel terrains.

Sikand et al. propose vrl-pap [6] in which both a visual representation and a
visual preference cost are learned for preference-aligned navigation.
Similarly, sterling[19] introduces a self-supervised representation learning
approach for visual representation learning. However, a limitation for both
vrl-pap and sterling is their dependence on additional human feedback when
dealing with novel terrains — feedback that might not consistently be
available during deployment. Distinct from vrl-pap and sterling, patern
focuses on extrapolating operator preferences from known terrains to visually
novel terrains.

##  III PRELIMINARIES

We formulate preference-aligned planning as a local path-planning problem in a
state space $\mathcal{S}$, with an associated action space $\mathcal{A}$. The
forward kino-dynamic transition function is denoted as
$\mathcal{T}:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}$ and we assume
that the robot has a reasonable model of $\mathcal{T}$ (e.g., using parametric
system identification [20] or a learned kino-dynamic model [21, 1, 22]), and
that the robot can execute actions in $\mathcal{A}$ with reasonable precision.
For ground vehicles, a common choice for $\mathcal{S}$ is $\mathrm{SE}(2)$,
which represents the robot’s x and y position on the ground plane, as well as
its orientation $\theta$.

The objective of the path-planning problem can be expressed as finding the
optimal trajectory $\Gamma^{*}=\underset{\Gamma}{\arg\min}\ J(\Gamma,G)$ to
the goal $G$, using any planner (e.g. a sampling-based motion planner like dwa
[23]) while minimizing an objective function $J(\Gamma,G)$,
$J:(\mathcal{S}^{N},\mathcal{S})\rightarrow\mathbb{R}^{+}$. Here,
$\Gamma=\\{s_{1},s_{2},\dots,s_{N}\\}$ denotes a sequence of states. The
sequence of states in the optimal trajectory $\Gamma^{*}$ is then translated
into a sequence of actions, using a 1-D time-optimal controller, to be played
on the robot. For operator preference-aligned planning, the objective function
$J$ is articulated as,

$J(\Gamma,G)=J_{G}(\Gamma(N),G)+J_{P}(\Gamma),$ (1)

Here, $J_{G}$ denotes cost based on proximity of the robot’s state to the goal
$G$, while $J_{P}$ imparts a cost based on terrain preference. Crucially,
$J_{P}$ is designed to capture operator preferences over different terrains;
less preferred terrains incur a higher cost. Though earlier studies leverage
human feedback to ascertain $J_{P}$ for unfamiliar terrains [6, 19], in this
work, we hypothesize that in certain situations, operator preferences for
novel terrains can be extrapolated from known terrains, obviating operator
dependency during real-world deployment. Thus, our novel contribution is a
self-supervised framework for extrapolating $J_{P}$ from known terrains to
visually novel terrains by leveraging inertial-proprioceptive-tactile
observations of a robot, without inquiring additional human feedback.

##  IV APPROACH

In this section, we present Preference extrApolation for Terrain-awarE Robot
Navigation (patern), a novel framework for extrapolating operator preferences
for preference-aligned navigation. We first detail an existing framework for
terrain-preference-aligned visual navigation. We then introduce patern for
self-supervised extrapolation of operator preferences from known terrains to
visually novel terrains by leveraging proprioceptive feedback.

###  IV-A A Two-Step Framework for Preference-Aligned Planning

For real-time preference-aligned planning, inspired from earlier studies [6,
19], we postulate that $J_{P}(\Gamma)$ can be estimated in a two-step approach
from visual observations of patches of terrain at $s\in\mathcal{S}$ along
$\Gamma$. Let $O\in\mathcal{O}$ represent these observations. We denote $\Pi$
as a projection operator that extracts visual observation $O$ of terrain at
$s$ by yielding image patches from homography-transformed bird’s eye view
images [6, 19]. First, a visual encoder, denoted as $f_{vis}$, maps $O$ from
the RGB space to a latent vector $\phi_{vis}\in\Phi_{vis}$ such that
observations from identical terrains cluster closely in $\Phi_{vis}$ and are
distinct from those of differing terrains. Next, a real-valued preference
utility is estimated from $\phi_{vis}$ using a learned preference utility
function $u_{vis}:\Phi_{vis}\rightarrow\mathbb{R}^{+}$ trained with ranked
preferences of terrains, derived either from demonstrations [6], or by active
querying [19]. Adopting the popular formulation of Zucker et al. [24], we
train the utility function with the margin-based ranking loss [25]. To
estimate $J_{P}(\Gamma)$ during planning, we employ an exponential cost
formulation given by,
$J_{P}(\Gamma)=\sum_{s\in\Gamma}e^{-u_{vis}[f_{vis}(\Pi(s))]}$, which we find
works well in practice. This two-step framework for estimating $J_{P}(\Gamma)$
has been utilized successfully in recent works [6, 19] for operator
preference-aligned off-road navigation. Training details of the visual encoder
and the utility function are provided in Section V.

While the above two-step framework effectively handles known terrains with
pre-defined preferences, it faces challenges when the robot encounters
visually novel terrains that lie beyond the training distribution of $f_{vis}$
and $u_{vis}$. Towards addressing this problem, the primary contribution of
our work is a self-supervised framework to extrapolate operator preferences to
novel terrains and adapting $f_{vis}$ and $u_{vis}$ to ensure successful
preference alignment.

###  IV-B Extrapolating Preferences for Visually Novel Terrains

Leveraging the intuition that in addition to visual appearance, operator
preferences over terrains are likely also based on the “feel” of the
underlying terrain such as bumpiness, stability, or traction, we posit that in
many situations, operator preferences for novel terrains can be deduced by
relating the proprioceptive modality to known terrains. Utilizing these rich,
alternate data sources offers deeper insight into terrain properties, enabling
us to extrapolate terrain preferences when direct operator feedback is
unavailable. Upon initially encountering a novel terrain, before undergoing
any adaptation, we designate this stage as the pre-adaptation phase. During
this phase, the visual encoder and utility function operate based on
previously known operator preferences. However, once preferences are
extrapolated and the visual encoder and utility functions are subsequently
retrained to adapt, the system progresses to the post-adaptation phase, as
shown in Fig. 1.

Inertial-Proprioceptive-Tactile Encoder and Utility Function: In patern, in
addition to the visual encoder, we introduce a non-visual encoder that
independently processes the inertial, proprioceptive (joint angles and
velocities), and tactile feet data—collectively referred to as proprioception
for brevity—observed by the robot as it traverses a terrain. This encoder maps
proprioception observations into a proprioceptive representation space
$\Phi_{pro}$, such that representations $\phi_{pro}\in\Phi_{pro}$ of the same
terrain are closely clustered whereas those of distinct terrains are farther
apart. Additionally, a utility function
$u_{pro}:\Phi_{pro}\rightarrow\mathbb{R}^{+}$ maps the proprioceptive
representation vector $\phi_{pro}\in\Phi_{pro}$ to a real-valued preference
utility, similar to the visual utility function. Note that, to estimate
$J_{P}(\Gamma)$ during deployment, we only use $u_{vis}$ and not $u_{pro}$
since we cannot observe the proprioceptive components of a future state
without traversing the terrain first.

Pre-Adaptation Phase: While traversing known terrains that are in-
distribution, the visual and proprioceptive utility values tend to align
closely. However, for visually novel terrains, discrepancies often emerge
between the utility values predicted from the visual and proprioceptive
modalities. In patern, we utilize the mean-squared error between the predicted
utilities as a signal to detect visually novel, out-of-distribution terrains.
Although any novelty detection mechanism can be integrated within patern, such
as the uni-modal approach by Burda et al. [26], our primary focus is on a
framework that extrapolates operator preferences for novel terrains. Moreover,
any foundational approach employing the two-step framework for preference cost
estimation [6, 19, 27], as elaborated in Subsection IV-A, can be utilized in
the pre-adaptation phase. For clarity, we use the notation
$\textsc{patern}{}^{-}$ to represent the baseline algorithm in its unadapted
state and $\textsc{patern}{}^{+}$ to indicate the updated model in the post-
adaptation phase.

Extrapolating Operator Preferences: Given a novel terrain segment for which
operator preferences are unknown, we propose to self-supervise preference
assignment by first clustering its proprioceptive representations $\phi_{pro}$
and then associating it with the closest known existing cluster in
$\Phi_{pro}$, assigning the same operator preference as the known-cluster, as
illustrated in Fig. 1. Following this self-supervised preference assignment,
the visual encoder and visual utility function for novel terrain segments are
finetuned by aggregating newly gathered experience with existing data.

Figure 2: An illustration of the training setup for preference extrapolation
proposed in patern. We utilize two encoders to map visual and inertial-
proprioceptive-tactile samples to $\Phi_{vis}$ and $\Phi_{pro}$ respectively.
For a visually novel terrain, a preference is hypothesized and extrapolated
from $\Phi_{pro}$, following which the visual encoder and utility function are
retrained.

##  V Implementation Details

In this section, we describe the implementation details of patern. We first
describe data pre-processing, followed by training details in the pre-
adaptation phase. Finally, we describe adapting the visual encoder and utility
function using the extrapolated preference in patern.

###  V-A Data Pre-Processing

In tandem with the visual patch extraction process used in the projection
operator $\Pi$ as in prior methods [6, 19], for every state $s_{t}$, we also
extract a 2-second history of time-series inertial (angular velocities along
the x and y-axes and linear acceleration in the z-axis), proprioceptive (joint
angles and velocities), and tactile (feet depth penetration estimates) data.
To ensure the resulting input data representation for training is independent
of the length and phase of the signals, we compute statistical measures of
center and spread as well as the power spectral density, and maintain that as
the input. All the visual patches extracted with the projection operator $\Pi$
and the non-visual data for each state $s$ are then tagged with their
corresponding terrain name, given that each trajectory uniquely contains a
particular terrain type. In addition to processing the recorded data in the
pre-adaptation phase, a human operator is queried for a full-order ranking of
terrain preference labels.

###  V-B Pre-Adaptation Training

We use a supervised contrastive learning formulation inspired by Sikand et al.
[6] to train the baseline functions $f_{vis}$ and $u_{vis}$, represented as
neural networks.

Training the Encoders: Given labeled visual patches and proprioception data,
we generate triplets for contrastive learning such that for any anchor, the
positive pair is chosen from the same label and the negative pair is sourced
from another label. Given such triplets, we use triplet loss [28] with a
margin of $1.0$ to independently train the visual and proprioception encoders
through mini-batch gradient descent using the AdamW optimizer. For the visual
encoder, we use a 3-layer CNN of $5\times 5$ kernels, each followed by ReLU
activations. This model, containing approximately 250k parameters, transforms
$64\times 64$ size RGB image patches into an 8-dimensional vector
representation $\phi_{vis}$. Similarly, our inertial encoder is comprised of a
3-layer MLP with ReLU activations, encompassing around 4k parameters, and maps
proprioceptive inputs to an 8-dimensional vector $\phi_{pro}$. To mitigate the
risk of overfitting, data is partitioned in a 75-25 split for training and
validation, respectively.

Training the Utility Functions: In our setup, the utility function is
represented as a two-layer MLP with ReLU non-linearity and output activation
that maps an 8-dimensional vector into a singular non-negative real value.
Given ranked operator preferences of the terrains, we follow Zucker et al.
[24] and train the visual utility function $u_{vis}$ using a margin-based
ranking loss [25]. Furthermore, to ensure consistent predictions from
$u_{vis}$ and $u_{pro}$ for both visual and non-visual observations at
identical locations, we update parameters of $u_{pro}$ using the loss
$\mathcal{L}_{\text{MSE}}(u_{\text{pro}})=\frac{1}{N}\sum_{i=1}^{N}\left(sg(u_{\text{vis}}(\phi_{vis}))-u_{\text{pro}}(\phi_{pro})\right)^{2}$.
Here, $sg(\cdot)$ denotes the stop-gradient operation, and $\phi_{vis}$ and
$\phi_{pro}$ are the terrain representations from paired visual and non-visual
data, respectively, at the same location.

The functions $f_{vis}$ and $u_{vis}$ prior to adaptation are collectively
termed as $\textsc{patern}{}^{-}$, signifying their non-adapted state with
respect to visually novel terrains. In our implementation, although we use
supervised contrastive learning, in instances where explicit terrain labels
might be absent, one can resort to self-supervised representation learning
techniques, such as sterling [19], to derive $f_{vis}$ and $u_{vis}$. patern
can be applied regardless of the specific representation learning approach
used.

###  V-C Preference Extrapolation Training

During deployment, if the robot encounters a visually novel terrain, both
visual and inertial-proprioceptive-tactile data is recorded to be used in the
adaptation phase in patern, aiding in preference extrapolation and subsequent
model adaptation. We refer to this collected data as the adaptation-set. We
extract paired visual and non-visual observations at identical locations from
the adaptation-set and use $f_{pro}$ to extract proprioceptive representations
$\phi_{pro}$. We cluster samples of $\phi_{pro}$ and perform a nearest-
neighbor search against existing terrain clusters from the pre-adaptation
dataset that is within a threshold $\mu$. We set this threshold to be the same
as the triplet margin value of 1.0 which we find to work well in practice.
This procedure seeks a known terrain that “feels” similar to the novel terrain
which then inherits the preference of its closest match. Following this self-
supervised preference extrapolation framework, the adaptation-set is
aggregated with the pre-adaptation training set, and the visual encoder
$f_{vis}$ is retrained using the procedure described in V-B. Additionally, the
visual utility function $u_{vis}$ is retrained with the extrapolated
preference for the novel terrain. The updated functions $f_{vis}$ and
$u_{vis}$ are collectively referred to as $\textsc{patern}{}^{+}$. Figure 2
illustrates retraining and preference extrapolation as described above.

##  VI EXPERIMENTS

In this section, we describe the physical robot experiments conducted to
evaluate patern against other state-of-the-art visual off-road navigation
algorithms. Specifically, our experiments are designed to explore the
following questions:

  1. ($Q_{1}$)

Is patern capable of extrapolating operator preferences accurately to novel
terrains?

  2. ($Q_{2}$)

How effectively does patern navigate under challenging lighting scenarios such
as nighttime conditions?

  3. ($Q_{3}$)

How well does patern perform in large-scale real-world off-road conditions?

Figure 3: Trajectories traced by patern and baseline approaches across three
different environments and varied lighting conditions within the UT Austin
campus. Note the drastic changes in the appearance of the terrain between day
and night, which pose a significant challenge for visual navigation. In
environments where $\textsc{patern}{}^{-}$ fails to generalize,
$\textsc{patern}{}^{+}$ successfully extrapolates and reaches the goal in a
preference-aligned manner.

To study $Q_{1}$ and $Q_{2}$, we execute a series of experiments consisting of
short-scale outdoor navigation tasks. We then conduct a large-scale autonomous
robot deployment along a 3-mile outdoor trail to qualitatively evaluate
$Q_{3}$. We use the legged Boston Dynamics Spot robot for all experiments,
equipped with a VectorNav VN100 IMU, front-facing Kinect RGB camera, Velodyne
VLP-16 LiDAR for geometric obstacle detection, and a GeForce RTX 3060 mobile
GPU. For local planning, we use an open-source sampling-based motion planner
called graphnav [29] and augment its sample evaluation function with the
inferred preference cost $L_{P}(\Gamma)$. For real-time planning, we run
$f_{vis}$ and $u_{vis}$ on the onboard GPU.

TABLE I: Mean Hausdorff distance relative to a human reference trajectory. Approach | Environment
---|---
1 | 2-D | 2-N | 3-D | 3-N
Geometric-Only | 2.87 | 2.34 | 2.34 | 3.44 | 3.69
rca[10] | 0.84 | 0.91 | 6.061 | 2.57 | 7.37
ganav[7] | 1.47 | 2.98 | 3.07 | 0.898 | 1.42
Fully-Supervised | 0.58 | 0.44 | 2.735 | 0.763 | 6.747
$\textsc{patern}{}^{-}$ | 0.54 | 2.31 | 2.29 | 2.305 | 5.76
$\textsc{patern}{}^{+}$ | - | 0.56 | 1.097 | 0.86 | 0.763
TABLE II: Mean trajectory percentage aligned with operator preferences. Approach | Environment
---|---
1 | 2-D | 2-N | 3-D | 3-N
Geometric-Only | 44.0% | 68.8% | 68.8% | 43.6% | 43.6%
rca[10] | 100% | 97.3% | 67.4% | 100% | 99.4%
ganav[7] | 93.9% | 71.6% | 71.4% | 100% | 100%
Fully-Supervised | 100% | 100% | 71.7% | 100% | 93.6%
$\textsc{patern}{}^{-}$ | 100% | 94.1% | 71.6% | 81.3% | 100%
$\textsc{patern}{}^{+}$ | - | 100% | 98.2% | 100% | 100%

###  VI-A Data Collection

To collect labeled data for training $\textsc{patern}{}^{-}$, we manually
teleoperated the robot across the UT Austin campus, gathering 8 distinct
trajectories each across 3 terrains: concrete, grass, and marble rocks. Each
trajectory, five minutes long, is exclusive to a single terrain type for ease
of labeling and evaluation. The pre-adaptation training data was collected in
the daytime under sunny conditions. Our evaluations then centered on two
preference extrapolation scenarios: one, extending to new terrains such as
pebble-pavement, concrete-with-shadows, and bushes, all experienced under
varying daylight conditions ranging from bright sunlight to overcast skies,
and two, adapting to nighttime illumination for familiar terrains that appear
visually different. In our experiments, we use the preference order
$\texttt{concrete}\succ\texttt{grass}\succ\texttt{marble rocks}$.

###  VI-B Quantitative Short-Scale Experiments

We evaluate patern in three environments with a variety of terrains within the
UT Austin campus. We also test under two different lighting conditions, as
shown in Fig. 3. The primary task for evaluation is preference-aligned visual
off-road navigation, in which the robot is tasked with reaching a goal, while
adhering to operator preferences over terrains.

To evaluate the effectiveness of patern, we compare it against five state-of-
the-art baseline and reference approaches: Geometric-Only [29], a purely
geometric obstacle-avoidant planner; RCA [10], a self-supervised
traversability estimation algorithm based on ride-comfort; GANav, a semantic
segmentation method 222https://github.com/rayguan97/GANav-
offroadhttps://github.com/rayguan97/GANav-offroad trained on RUGD dataset [8];
Fully-Supervised, an approach that utilizes a visual terrain cost function
comprehensively learned using supervised costs drawn from operator
preferences; and lastly, Human Reference, which offers a preference-aligned
reference trajectory where the robot is teleoperated by a human expert. To
train the rca and Fully-Supervised baselines, in addition to the entirety of
the pre-adaptation dataset on the 3 known terrains, we additionally collect 8
trajectories each on the novel terrains during daytime.

In each environment, we perform five trials of each method to ensure
consistency in our evaluation. For each trial, the robot is relocalized in the
environment, and the same goal location $G$ is fed to the robot. In the
environments where $\textsc{patern}{}^{-}$ fails to navigate in a preference-
aligned manner, we run five trials of the self-supervised
$\textsc{patern}{}^{+}$ instance that uses experience gathered in these
environments to extrapolate preferences to the novel terrains or novel
lighting conditions. Fig. 3 shows the qualitative results of trajectories
traced by each method in the outdoor experiments. Only one trajectory is shown
for each method unless there is significant variation between trials. Table I
shows quantitative results using the mean Hausdorff distance between a human
reference trajectory and evaluation trajectories of each method. Table II
shows quantitative results for the mean percentage of preference-aligned
distance traversed in each trajectory. Note that both the reported metrics may
be high if a method does not reach the goal but stays on operator-preferred
terrain.

From the quantitative results, we see that, as expected, the
$\textsc{patern}{}^{-}$ approach is able to successfully navigate in an
operator-preference-aligned manner in Env. 1, which did not contain any novel
terrain types. However, $\textsc{patern}{}^{-}$ fails to consistently reach
the goal and/or navigate in alignment with operator preferences in the
remaining environments. In the daytime experiments, Env. 2 contains a novel
terrain (pebble pavement) absent from training data for
$\textsc{patern}{}^{-}$, while Env. 3 contains both a novel terrain type
(bush) and novel visual terrain appearances caused by tree shadows. In the
nighttime experiments, all terrains contain novel visual appearances.
Following deployments in Envs. 2 and 3, patern extrapolates terrain
preferences for new visual data using the corresponding proprioceptive data to
retrain environment-specific $\textsc{patern}{}^{+}$ instances. In each
environment that the $\textsc{patern}{}^{-}$ model fails, the self-supervised
$\textsc{patern}{}^{+}$ model is able to successfully navigate to the
respective goal in a preference-aligned manner, without requiring any
additional operator feedback during deployment, addressing $Q_{1}$ and
$Q_{2}$. While the fully-supervised baseline more closely resembles the human
reference trajectory compared to $\textsc{patern}{}^{+}$ during the day in
Envs. 2 and 3, unlike the fully-supervised approach, $\textsc{patern}{}^{+}$
does not require operator preferences over all terrains and is capable of
extrapolating to visually novel terrains.

###  VI-C Qualitative Large-Scale Experiment

Figure 4:  Trajectory trace of a large-scale qualitative deployment of
$\textsc{patern}{}^{+}$ along a 3-mile segment of the Ann and Roy Butler trail
located in Austin, Texas. With only five minutes of supplementary data, patern
required only one manual intervention to stay on the trail and successfully
completes the hike, demonstrating robustness and adaptability to real-world
off-road conditions.

To investigate $Q_{3}$, we execute a large-scale autonomous deployment of
patern along a challenging 3-mile off-road trail 333Ann and Roy Butler trail,
Austin, TX, USA. The robot’s objective is to navigate in a terrain-aware
manner on the trail by preferring dirt, gravel and concrete over bush, mulch,
and rocks. Failure to navigate in a preference-aligned manner may cause
catastrophic effects such as falling into the river next to the trail. An
operator is allowed to temporarily take manual control of the robot only to
prevent such catastrophic effects, adjust the robot’s heading for forks in the
trail, or yield to pedestrians and cyclists. The $\textsc{patern}{}^{-}$ model
used for short-scale experiments is augmented with approximately five minutes
of combined additional data for dirt, bush, and mulch terrains commonly seen
in the trail. Following this preference extrapolation, the
$\textsc{patern}{}^{+}$ model is able to successfully navigate the 3-mile
trail, while only requiring one human intervention. Fig. 4 shows the
trajectory of the robot and a number of settings along the trail, including
the single unexpected terrain-related intervention in the lower right corner,
for the hour-long deployment. Additionally, we attach a video recording of the
robot deployment444https://youtu.be/j7159pE0u6spatern deployed in the trail:
https://youtu.be/j7159pE0u6s. This large-scale study addresses $Q_{3}$ by
qualitatively demonstrating the effectiveness of patern in scaling to real-
world off-road conditions.

##  VII LIMITATIONS AND FUTURE WORK

patern uses similarities between novel and known terrains in its learned
proprioception representation space to extrapolate preferences. Thus, patern
needs to have had experiences with terrains bearing close inertial-
proprioceptive-tactile resemblances for successful extrapolation. A noticeable
limitation is that if a terrain evoking similar proprioceptive features has
not been encountered before, patern might not be able to extrapolate
preferences. Additionally, patern utilizes non-visual observations that
require a robot to physically drive over terrains, which may be unsafe or
infeasible in certain cases. Extending patern with depth sensors to handle
non-flat terrains is a promising direction for future work.

##  VIII CONCLUSION

In this work, we present Preference extrApolation for Terrain-awarE Robot
Navigation (patern), a novel approach to extrapolate human preferences for
novel terrains in visual off-road navigation. patern learns an inertial-
proprioceptive-tactile representation space to detect similarities between
visually novel terrains and the set of known terrains. Through this self-
supervision, patern successfully extrapolates operator preferences for
visually novel terrain segments, without requiring additional human feedback.
Through extensive physical robot experiments in challenging outdoor
environments in varied lighting conditions, we find that patern successfully
extrapolates preferences for visually novel terrains and is scalable to real-
world off-road conditions.

## References

  * [1] H. Karnan, K. S. Sikand, P. Atreya, S. Rabiee, X. Xiao, G. Warnell, P. Stone, and J. Biswas, “Vi-ikd: High-speed accurate off-road navigation using learned visual-inertial inverse kinodynamics,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2022, pp. 3294–3301.
  * [2] T. Miki, J. Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter, “Learning robust perceptive locomotion for quadrupedal robots in the wild,” _Science Robotics_ , vol. 7, no. 62, p. eabk2822, 2022.
  * [3] X. Xiao, B. Liu, G. Warnell, and P. Stone, “Motion planning and control for mobile robot navigation using machine learning: a survey,” 2020.
  * [4] M. Bojarski, D. Del Testa, D. Dworakowski, B. Firner, B. Flepp, P. Goyal, L. D. Jackel, M. Monfort, U. Muller, J. Zhang, X. Zhang, J. Zhao, and K. Zieba, “End to end learning for self-driving cars,” 2016.
  * [5] Y. LeCun, U. Muller, J. Ben, E. Cosatto, and B. Flepp, “Off-road obstacle avoidance through end-to-end learning,” in _Proceedings of the 18th International Conference on Neural Information Processing Systems_ , ser. NIPS’05. Cambridge, MA, USA: MIT Press, 2005, p. 739–746.
  * [6] K. S. Sikand, S. Rabiee, A. Uccello, X. Xiao, G. Warnell, and J. Biswas, “Visual representation learning for preference-aware path planning,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 11 303–11 309.
  * [7] T. Guan, D. Kothandaraman, R. Chandra, A. J. Sathyamoorthy, K. Weerakoon, and D. Manocha, “Ga-nav: Efficient terrain segmentation for robot navigation in unstructured outdoor environments,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 3, pp. 8138–8145, 2022.
  * [8] M. Wigness, S. Eum, J. G. Rogers, D. Han, and H. Kwon, “A rugd dataset for autonomous navigation and visual perception in unstructured outdoor environments,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2019, pp. 5000–5007.
  * [9] P. Jiang, P. Osteen, M. Wigness, and S. Saripalli, “Rellis-3d dataset: Data, benchmarks and analysis,” 2020.
  * [10] X. Yao, J. Zhang, and J. Oh, “Rca: Ride comfort-aware visual navigation via self-supervised learning,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2022, pp. 7847–7852.
  * [11] G. Kahn, P. Abbeel, and S. Levine, “Badgr: An autonomous self-supervised learning-based navigation system,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 1312–1319, 2021.
  * [12] A. J. Sathyamoorthy, K. Weerakoon, T. Guan, J. Liang, and D. Manocha, “Terrapn: Unstructured terrain navigation using online self-supervised learning,” 2022.
  * [13] E. Yang, H. Karnan, G. Warnell, P. Stone, and J. Biswas, “Wait, that feels familiar: Learning to extrapolate human preferences for preference-aligned path planning,” in _ICRA2023 Workshop on Pretraining for Robotics (PT4R)_ , 2023.
  * [14] J. Frey, M. Mattamala, N. Chebrolu, C. Cadena, M. Fallon, and M. Hutter, “Fast traversability estimation for wild visual navigation,” 2023.
  * [15] C. A. Brooks and K. D. Iagnemma, “Self-supervised classification for planetary rover terrain sensing,” in _2007 IEEE aerospace conference_. IEEE, 2007, pp. 1–9.
  * [16] A. Loquercio, A. Kumar, and J. Malik, “Learning visual locomotion with cross-modal supervision,” 2022.
  * [17] J. Zürn, W. Burgard, and A. Valada, “Self-supervised visual terrain classification from unsupervised acoustic feature learning,” _IEEE Transactions on Robotics_ , vol. 37, no. 2, pp. 466–481, 2020.
  * [18] L. Wellhausen, A. Dosovitskiy, R. Ranftl, K. Walas, C. Cadena, and M. Hutter, “Where should i walk? predicting terrain properties from images via self-supervised learning,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 1509–1516, 2019.
  * [19] H. Karnan, E. Yang, D. Farkash, G. Warnell, J. Biswas, and P. Stone, “Self-supervised terrain representation learning from unconstrained robot experience,” in _ICRA2023 Workshop on Pretraining for Robotics (PT4R)_ , 2023\.
  * [20] N. Seegmiller, F. Rogers-Marcovitz, G. Miller, and A. Kelly, “Vehicle model identification by integrated prediction error minimization,” _The International Journal of Robotics Research_ , vol. 32, no. 8, pp. 912–931, 2013\.
  * [21] X. Xiao, J. Biswas, and P. Stone, “Learning Inverse Kinodynamics for Accurate High-Speed Off-Road Navigation on Unstructured Terrain,” _arXiv e-prints_ , p. arXiv:2102.12667, Feb. 2021.
  * [22] P. Atreya, H. Karnan, K. S. Sikand, X. Xiao, S. Rabiee, and J. Biswas, “High-speed accurate robot control using learned forward kinodynamics and non-linear least squares optimization,” in _Intelligent Robots and Systems (IROS), IEEE/RSJ International Conference on_. IEEE, 2022, pp. 11 789–11 795.
  * [23] D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” _IEEE Robotics & Automation Magazine_, vol. 4, no. 1, pp. 23–33, 1997.
  * [24] M. Zucker, N. Ratliff, M. Stolle, J. Chestnutt, J. A. Bagnell, C. G. Atkeson, and J. Kuffner, “Optimization and learning for rough terrain legged locomotion,” _The International Journal of Robotics Research_ , vol. 30, no. 2, pp. 175–191, 2011.
  * [25] D. P. Vassileios Balntas, Edgar Riba and K. Mikolajczyk, “Learning local feature descriptors with triplets and shallow convolutional neural networks,” in _Proceedings of the British Machine Vision Conference (BMVC)_ , E. R. H. Richard C. Wilson and W. A. P. Smith, Eds. BMVA Press, September 2016, pp. 119.1–119.11. [Online]. Available: https://dx.doi.org/10.5244/C.30.119
  * [26] Y. Burda, H. Edwards, A. Storkey, and O. Klimov, “Exploration by random network distillation,” 2018.
  * [27] D. S. Brown, W. Goo, and S. Niekum, “Better-than-demonstrator imitation learning via automatically-ranked demonstrations,” in _Conference on robot learning_. PMLR, 2020, pp. 330–359.
  * [28] F. Schroff, D. Kalenichenko, and J. Philbin, “Facenet: A unified embedding for face recognition and clustering,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 815–823.
  * [29] J. Biswas, “Amrl autonomy stack,” https://github.com/ut-amrl/graph_navigation, 2013.