# Unsupervised MKL in Multi-layer Kernel Machines

Akhil Meethal1, Asharaf S2, Sumitra S1

1 Department of Mathematics, Indian Institute of Space Science and Technology,
Trivandrum  2 School of CS & IT, Indian Institute of Information Technology
and Management - Kerala

###### Abstract

Kernel based Deep Learning using multi-layer kernel machines(MKMs) was
proposed by Y.Cho and L.K. Saul in [1]. In MKMs they used only one kernel(arc-
cosine kernel) at a layer for the kernel PCA based feature extraction. We
propose to use multiple kernels in each layer by taking a convex combination
of many kernels following unsupervised learning strategy. Empirical study is
conducted on mnist-back-rand, mnist-back-image and mnist-rot-back-image
datasets generated by adding random noise in the image background of MNIST
dataset. Experimental results indicates that using MKL in MKMs earns better
representation of the raw data and improves the classifier performance.

###### Index Terms:

Deep Learning, Multiple Kernel Learning, Deep Kernel Learning

##  I Introduction

Representation Learning is one of the key area in machine learning, where
intense research works are being done spanning over decades. The choice of the
representation has a considerable influence in the performance of learning
algorithms[3]. Representation Learning is also considered as an effective
mechanism for transferring the prior knowledge of humans to the machine
learning system. The architecture of the Representation Learning system is
broadly classified into deep and shallow architectures[2]. Shallow
architectures often produces strong task specific priors, whereas deep
architectures can support broad priors which can favour a wide range of
functions.

Deep Learning is a rapidly developing area among Representation Learning
algorithms, which makes use of depth as a key criteria for producing good
representations(hence they belong to deep architectures). In general, Deep
Learning is a set of algorithms in machine learning that attempts to model
high-level abstractions in data by using model architectures composed of
multiple non-linear transformations[4][3]. Deep Learning methods are preferred
over shallow ones in many complex learning tasks(such as computer vision,
speech recognition etc.) due to: the wide range of functions that can be
parameterized by composing weakly nonlinear transformations, the broad range
of prior knowledge they can transfer to the learning system, the invariance
being modelled by such systems against local changes in the input and their
ability to learn more abstract concepts in an hierarchical fashion[1][2].

Though the idea of using such deep architectures for learning representations
is known to machine learning researchers, two main factors deterred the wide
use of Deep Learning algorithms: the gradient-based methods often gets trapped
in local minima which results in poor generalization capacity, training the
networks with more than 2 or 3 layers was a big computational challenge. The
greedy layerwise unsupervised pre-training proposed by Hinton et.al in [10] is
a breakthrough in machine learning research tackling the difficulty in
training such deep models. This method proposes to learn a hierarchy of
features one level at a time, following an unsupervised strategy[3]. This
greedy layerwise unsupervised pre-training is used to initialize the weights
of the network(unsupervised pre-training stage) and then the weights are fine-
tuned with the given label information(supervised fine-tuning stage).

The recent rise in computing power alleviated the second problem upto a
considerable level. Efficient training methods are devised for learning
networks with millions of parameters both on multi-core CPUs and GPUs[12][13].
Scalable deep learning models are also developed in distributed cloud based
enviornments[14].

Armed with these tools Deep Learning witnessed a sudden boost since 2006,
producing state-of-the-art results in several complex machine learning tasks
like speech recognition[7], visual object recognition[8][5][6], natural
language processing[9] etc. However, most of the Deep Learning algorithms are
developed on top of neural network based models[11][10] which shows a
declining trend in the popularity of kernel machines in advanced learning
tasks. Many researchers have been extensively studied the limitations kernel
machines in such problems. The analysis shown in [2] claims that the number of
training examples required for a kernel machine with Gaussian kernel may grow
linearly with the number of variations of the target function.

In [1] Cho et.al explored the concept of kernel methods based Deep Learning by
proposing Multi-layer Kernel Machines(MKMs). The architecture of MKMs consists
multiple layers with each layer performing unsupervised feature extraction
using kernel PCA[15] followed by supervised feature selection by ranking
features based on their mutual information with class labels. We tried to
extend this architecture by taking combination of multiple kernels at each
layer. In particular, instead of using a single kernel for the kernel PCA
based feature extraction we used a convex combination of multiple
kernels(Multiple Kernel Learning following unsupervised paradigm) at each
layer.

The organization of this paper is as follows. In section II we reviews the
existing MKMs proposed by Cho et.al along with the kernel function introduced
by them(arc-cosine kernels which can mimic the computations in large
multilayer threshold networks). Section III describes the proposed Multi-layer
Multiple Kernel Learning(ML-MKL) framework for representation learning.
Section IV describes the experimental results and some analysis done on this
ML-MKL framework. Section V concludes this paper.

##  II Multi-layer Kernel Machines

In MKMs the non-linear transformations are induced by kernel functions stacked
in a layerwise fashion. The architecture of MKMs are similar to that of neural
network based deep learning machines, with unsupervised feature
extraction(using Kernel PCA[15]) followed by supervised feature selection in
each layer. The figure 1 shows the architecture of an MKM consisting of L
layers of non-linear transformations.

Figure 1: An MKM with L layers of transformations. Each layer consists of
unsupervised feature extraction(using kernel PCA) followed by supervised
feature selection.

The supervised feature selection allows us to retain only those set of
features that are most informative for the pattern recognition task. The
number of features to be passed to the next layer(width of that layer) are
found out using cross validation techniques. This procedure determines the
architecture of the network in a greedy, layer-by-layer fashion. In their
implementation[1] Cho et. al used exhaustive search in a particular range to
determine the optimal set of features. The output from the final layer can be
passed to any classifier. Though any kernel can be used for the kernel PCA
based feature extraction, in [1] they emphasized on using arc-cosine kernels
due to: their similarity with computation in large neural networks, the
multiple layers of kernel composition does meaningful computation only in case
of arc-cosine kernels.

###  II-A Arc-cosine Kernels

Let x, y be two inputs in $\mathbb{R}^{d}$. Define $\theta$ as the angle
between them.

$\theta=cos^{-1}\left(\frac{x\cdot
y}{\left\|x\right\|\left\|y\right\|}\right)$

Then the kernel function computed by the arc-cosine kernel is

$k_{n}(x,y)=\frac{1}{\pi}\left\|x\right\|^{n}\left\|y\right\|^{n}J_{n}(\theta)$
(1)

where n is called the degree of the kernel and

$J_{n}(\theta)=(-1)^{n}(sin\theta)^{2n+1}\left(\frac{1}{sin\theta}\frac{\partial}{\partial\theta}\right)^{n}\left(\frac{\pi-\theta}{sin\theta}\right)$

$J_{n}(\theta)$ for n=0, 1, 2 is computed as shown below.

$J_{0}(\theta)=\pi-\theta$ $J_{1}(\theta)=sin\theta+(\pi-\theta)cos\theta$
$J_{2}(\theta)=3sin\theta cos\theta+(\pi-\theta)(1+2cos^{2}\theta)$

for n=0, it takes the simple form

$k_{0}(x,y)=1-\frac{1}{\pi}cos^{-1}\left(\frac{x\cdot
y}{\left\|x\right\|\left\|y\right\|}\right)$

hence the name arc-cosine kernel is given. Since arc-cosine kernels do not
have any continuous tuning parameters, cross-validation for finding the
optimal degree value is not a tiresome job.

A kernel function is implicitly inducing a non-linear mapping from input $x$
to feature vector $\phi(x)$(except the linear kernel). In effect, the kernel
function computes the inner product of two input datapoints $x\textrm{ and }y$
in this induced feature space:

$k(x,y)=\phi(x)\cdot\phi(y)$

Iteratively applying the mapping $\phi(\cdot)$ on the inputs $x\textrm{ and
}y$ and then taking their inner product, we can obtain an L-layer kernel
function as

$k^{(L)}(x,y)=\underbrace{\phi(\phi(\ldots\phi(x)))}_{\textrm{L
times}}\textrm{ }\cdot\textrm{
}\underbrace{\phi(\phi(\ldots\phi(y)))}_{\textrm{L times}}$

The intuition behind this in case of arc-cosine kernels is, if the base kernel
$k(x,y)=\phi(x)\cdot\phi(y)$ can mimic the computation of a single-layer
network, then the iterated mapping in $k^{(L)}(x,y)$ can mimic the computation
of multi-layer network[1]. The L layer kernel function for arc-cosine kernels
can be recursively computed as

$k^{(L+1)}_{n}(x,y)=\frac{1}{\Pi}\Bigg{[}k^{(L)}(x,x)\textrm{
}k^{(L)}(y,y)\Bigg{]}^{\frac{n}{2}}J_{n}(\theta_{n}^{(L)})$

where $\theta_{n}^{(L)}$ is the angle between images of $x\textrm{ and }y$ in
the feature space after L layer composition

$\theta_{n}^{(L)}=\textrm{cos}^{-1}\Bigg{(}k^{(L)}(x,y)\Bigg{[}k^{(L)}(x,x)\textrm{
}k^{(L)}(y,y)\Bigg{]}^{\frac{-1}{2}}\Bigg{)}$

for simplicity we have assumed that the arc-cosine kernels have the same
degree $n$ at every layers of recursion. We can also use kernels of different
degree at different layers.

##  III Multi-layer Multiple Kernel Machines

Multiple Kernel Learning(MKL)[17] aims at learning a convex combination of a
set of predefined base kernles inorder to get a good kernel. The primary aim
of MKL algorithm is to reduce the burden of choosing the optimal kernel(and
hence automate the kernel parameter tuning) for the learning task. Also in
practical scenarios instead of using a single kernel, a combination of
multiple kernels give better results for pattern recognition, regression etc.

The concept of Multi-layer Multiple Kernel Learning has been explored by many
authors[20][21] in supervised learning settings. In particular the authors in
[20] and [21] embedded the ML-MKL framework inside the SVM cost function,
where instead of a single flat kernel a multi-layer kernel with many kernels
in each layer is used. The authors used a combination of Convex Quadratic
Programming(for finding coefficients of decision function, $\alpha$) and
gradient descent(for getting the kernel weights $\mu$) in an alternating
fashion to solve the resulting optimization task. Though the results are
encouraging, the framework is not tested in large datasets studied extensively
in Deep Learning literatures. Another limitation of the above approach is, the
feature learning process is specific to a classifier.

In the KPCA based feature extraction stages, we were using only one kernel for
the task. With the intuition that by using multiple kernels at each layer we
will get more similarity information, we computed a convex combination of
multiple kernels following the work in [16]. Since we are using kernels for
unsupervised feature extraction, traditional MKLs following supervised
paradigm cannot be used here.

The goal of an unsupervised multiple kernel learning task is to find an
optimal linear combination of the $m$ kernel functions as, i.e,
$k^{*}(\cdot\textrm{ , }\cdot)\in K_{conv}$, where $K_{conv}$ is defined as
follows:

$K_{conv}=\Bigg{\\{}k(\cdot\textrm{ ,
}\cdot)=\sum_{t=1}^{m}\mu_{t}k_{t}(\cdot\textrm{ , }\cdot)\textrm{ :
}\sum_{t=1}^{m}\mu_{t}=1,\mu_{t}\geq 0\Bigg{\\}}$

where $k_{t}$’s are the base kernels. Inorder to determine the optimality of a
linear combination of kernels, we used the following quality criteria:

  * •

A good kernel should enable each training instances to be well reconstructed
from the localized bases weighted by the kernel values. Formulating this
requirment mathematically, for each $x_{i}$ we expect the optimal kernel
should minimize the approximation error $\left\lVert
x_{i}-\sum_{j}k_{ij}x_{j}\right\rVert^{2}$.

  * •

A good kernel should induce kernel values that are coincided with the local
geometry of the training data. This is equivalent to finding the optimal
kernel that minimizes the distortion over all trainig data, computed as
$\sum_{i,j}k_{ij}\left\lVert x_{i}-x_{j}\right\rVert^{2}$, where
$k_{ij}=k(x_{i},x_{j})$.

In addition to this, the locality preserving principle is also exploited here
by using a set of local bases for each $x_{i}\in X$ denoted as $B_{i}$.
Instead of using the entire training data, we used these local bases to
reconstruct the sample $x_{i}$ and compute the distortion as well. By fixing
the size of the local bases to some constant $N_{B}$, we formulate the
optimization problem of unsupervised MKL as follows.

$\min_{k\in K_{conv}}\frac{1}{2}\sum_{i=1}^{n}\left\lVert x_{i}-\sum_{x_{j}\in
B_{i}}k_{ij}x_{j}\right\rVert^{2}+\gamma*\sum_{i=1}^{n}\sum_{x_{j}\in
B_{i}}k_{ij}\left\lVert x_{i}-x_{j}\right\rVert^{2}$

where $\gamma$ is a tuning parameter, which controls the tradeoff between the
coding error and the locality distortion. Converting to matrix notations we
will get the following optimization problem

$\min_{\mu\in\Delta,D}\frac{1}{2}\left\lVert X(I-K\circ
D)\right\rVert_{F}^{2}+\gamma*\textrm{ tr }K\circ D\circ M(11^{T})$ (2)
$\textrm{subject to }D\in\\{0,1\\}^{n\times n}$ $\left\lVert
d_{i}\right\rVert_{1}=N_{B},i=1,2,\ldots,n$
$\Delta=\Big{\\{}\mu:\mu^{T}\textbf{1}=1,\mu\geq 0\Big{\\}}\textrm{ and }$
$[K]_{i,j}=\sum_{t=1}^{m}\mu_{t}k^{t}(x_{i},x_{j}),1\leq i,j\leq n$

The matrix $D\in\\{0,1\\}^{n\times n}$ contains information about local bases
of each $x_{i}$ as a column vector. In particular, each column vector
$d_{i}\in\\{0,1\\}^{n}$ in $D$ has a 1 at those points $j$ where, $x_{j}\in
B_{i}$ and zero elsewhere(or $B_{i}=\\{x_{j}:d_{j}\neq 0\\}$). The matrix M is
defined as

$[M]_{ij}=x_{i}^{T}x_{i}+x_{j}^{T}x_{j}-2x_{i}^{T}x_{j}$

In equation 2 the notation ‘$\circ$’ denotes elementwise multiplication of two
matrices, $\left\lVert\cdot\right\rVert_{F}^{2}$ denotes the Frobenius norm of
a matrix and ‘tr’ denotes the trace of a matrix.

In their implementation([16]) Zhuang et.al solved the optimization problem in
two stages in an alternating fashion, first by solving for $\mu$ with a fixed
$D$(using convex optimization) and then solving for $D$ by fixing $\mu$(using
a greedy mixed integer programming formulation). Since we are using a many
layer architecture, the alternating optimization strategy is too costly for
us; so we choose to do the optimization across $\mu$ only by choosing $D$
beforehand. Specifically, the matrix $D$ is computed beforehand by taking $k$
nearest neighbours of $x_{i}$ from the training set and putting a one in those
positions for $d_{i}$. Rest of the positions are filled with zeros. The
resulting optimization problem will be

$\displaystyle\min_{\mu\in\Delta}\frac{1}{2}\left\lVert X(I-K\circ
D)\right\rVert_{F}^{2}+\gamma*\textrm{ tr }K\circ D\circ M(11^{T})$ (3)
$\textrm{subject to }D\in\\{0,1\\}^{n\times n},\left\lVert
d_{i}\right\rVert_{1}=N_{B},i=1,2,\ldots,n$
$\Delta=\Big{\\{}\mu:\mu^{T}\textbf{1}=1,\mu\geq 0\Big{\\}}$

The objective function can be formulated as a Convex Qudratic Programming
problem w.r.t to kernel weights $\mu$ as shown below(derivation of the
objective function $J(\mu)$ is shown in Appendix A).

$J(\mu)=\mu^{T}\Bigg{(}\sum_{t=1}^{m}\sum_{i=1}^{n}k_{t,i}k_{t,i}^{T}\circ
d_{i}d_{i}^{T}\circ P\Bigg{)}^{T}\mu+z^{T}\mu$ (4)

where $[z]_{t}=\sum_{i=1}^{n}(2\gamma v_{i}\circ d_{i}-2p_{i}\circ
d_{i})^{T}\mathit{k}_{t,i}$, $P=X^{T}X$, and
$\mathit{k}_{t,i}=\Big{[}k^{t}(x_{i},x_{1}),\ldots,k^{t}(x_{i},x_{n})\Big{]}^{T}$
is the $i^{th}$ column of the $t^{th}$ kernel matrix. $p$ and $v$ are columns
of $P$ and $M$ corresponding to $x_{i}$ respectively.

###  III-A ML-MKL Algorithm

The architectue of the proposed ML-MKL framework is shown in figure 2. It
consists of many layers and in each layer the kernel PCA based feature
extraction is performed using the combination of a set of predefined kernels.
The dimensionality of the features thus obtained are reduced by using
supervised feature selection techniques. The final output can be given to any
classifier. Algorithm 1 summarizes the proposed ML-MKL algorithm.

Input: data X, true labels y, no. of layers L, base kernels for each layer
$K_{base}^{(l)}=\\{k_{1}^{(l)},k_{2}^{(l)},k_{m}^{(l)}\\}$, $N_{B}$, $\gamma$;

Output: kernel weights $\mu^{l}$ for each layer, predicted labels;

1.Initialize $[M]_{ij}=x_{i}^{T}x_{i}+x_{j}^{T}x_{j}-2x_{i}^{T}x_{j}$,
$\bm{D}=d_{1},d_{2},\ldots,d_{n}$ as row vectors, where $d_{i}=\\{1\textrm{ if
}x_{j}\in B_{i}\textrm{ else }0\forall x_{j}\in X\\}$, $\mu=\frac{1}{m}$,
$\bm{P}=X^{T}X$;

2.for  _each layer l_ do

a. $\bm{W}=\sum_{t=1}^{m}\sum_{i=1}^{n}k_{t,i}^{(l)}k_{t,i}^{(l)^{T}}\circ
d_{i}d_{i}^{T}\circ P$

b. $\bm{[z]}_{t}^{l}=\sum_{i=1}^{n}(2\gamma v_{i}\circ d_{i}-2p_{i}\circ
d_{i})^{T}\mathit{k}_{t,i}^{(l)}$

c. $\bm{\mu}^{*^{l}}=\mu^{l^{T}}W\mu^{l}+z^{l^{T}}\mu^{l}$

d. $\bm{K}_{new}=\sum_{t=1}^{m}\mu_{t}^{l}*K_{t}^{(l)}$

e. extract principal components with $\bm{K}_{new}$

f. select most informative features for layer $l$($X_{new}$)

g. $\bm{P}=X_{new}^{T}X_{new}$

end for

3.Give the final set of features to any classifier;

Algorithm 1 ML-MKL Algorithm Figure 2: An ML-MKL with L layers of
transformations. Each layer consists of many kernels for feature extraction
using kernel PCA and a supervised feature selection module.

##  IV Experiments

Empirical study is conducted on three datasets, created from MNIST dataset[19]
of handwritten digits by adding noise in the background(and by performing some
transformations also). The mnist-back-rand dataset was created by filling the
image background with random pixel values, mnist-back-image dataset by filling
the image background with random image patches, and mnist-rot-back-image is a
rotated variant of mnist-back-image where the rotation angle is generated
uniformly between $0$ and $2\pi$. Each image is of size 28$\times$28 and each
dataset contains 12000 training images and 50000 testing images. Figure 3
contains some samples from these the datasets.

Figure 3: sample images from mnist-back-rand(first row), mnist-back-
image(second row) and mnist-rot-back-image(third row) datasets.

In the training phase, for each layer we set apart 10000 datapoints for
training the model and 2000 datapoints for cross validating kernel parameters
and the tuning parameter $\gamma$. For the kernel PCA we choose 3000
datapoints from the training set randomly and repeated the test 5 times to get
a mean value of the performance. The feature selection is done by performing a
univariate statistical test and then ranking the features based on the test
score, followed by selection of most informative features sorted according to
the rank. For performing the univariate statistical test feature selection
module available in the scikit-learn[18] library is used.

In the final classification stage SVMs with arc-cosine kernels are used. For a
fair comparison with MKMs the same feature selection techique(univariate
feature selection) and classifier(SVM with arc-cosine kernel) is used in our
implementation of MKMs. Table I summarizes the results of our empirical study.

Table I also contains best results obtained from other models[10] like SVM
with RBF kernel(SVM RBF), SVM with polynomial kenel(SVM Poly), single hidden
layer feed-forward neural network(NNet), DBN with 1 hidden layer(DBN-1), DBN
with 3 hidden layer(DBN-3) and 3 hidden layer Stacked Autoassociator
Network(SAA-3). The first three models comes under shallow architectures and
the remaining are deep architectures. From the table, it can be observed that
ML-MKL outperforms all the remaining models except Deep Belif Networks(DBN).
Compared to DBN the architecture, parameter tuning and optimization etc. are
fairly simple in ML-MKL models. The performance gap is very much considerable
with shallow architectures(SVM RBF, SVM Poly, NNet) in case of mnist-back-rand
dataset.

Dataset | Loss in Percentage
---|---
SVM RBF | SVM Poly | NNet | DBN-3 | SAA-3 | DBN-1 | MKM | ML-MKL
mnist-back-rand | 14.58 | 16.62 | 20.04 | 6.73 | 11.28 | 9.80 | 10.55 | 8.43$\pm 0.088$
mnist-back-image | 22.61 | 24.01 | 27.41 | 16.31 | 23.00 | 16.15 | 21.39 | 20.92$\pm 0.092$
mnist-rot-back-image | 55.18 | 56.41 | 62.16 | 47.39 | 51.93 | 52.21 | 51.61 | 51.21$\pm 0.811$
TABLE I: Experimental Results of ML-MKL

For the mnist-back-rand dataset the best result is obtained with a model
consists of 4 layers and in each layer 7 kernels are used. In particular, each
layer consists of a mixture of one arc-cosine kernel and 6 gaussian kernels.
For the mnist-back-image dataset the best ML-MKL model obtained has 2 layers
and 5 kernels in each layer. In each layer a mixture of one arc-cosine kernel
and 4 polynomial kernels are used. In the case of mnist-rot-back-image dataset
the best result is fetched by a model having only one layer with 4 arc-cosine
kernels in it. For all datasets the layer width is set to 150 features in each
layer after cross validation.

Figures 4 and 5 illustrates the variation in classifier performance on mnist-
back-rand and mnist-back-image datasets respectively when layers are added
iteratively to the ML-MKL model. The value shown for each layer is the best
error rate obtained after tuning the kernel parameters. The parameters are
choosen greedily for each layer(with the expectation that subsequent layers
will learn more valuable features from the current one) and no fine-tuning is
performed with respect to the entire architecture.

Figure 4: Change in classifier performance on mnist-back-rand dataset when
adding layers iteratively. Figure 5: Change in classifier performance on
mnist-back-image dataset when adding layers iteratively.

Tables II and III shows the kernel weights of each kernel in the mixture at
every layer for mnist-back-rand and mnist-back-image datasets respectively. In
both cases $k_{1}$ is an acr-cosine kernel, and the remaining are Gaussian
kernels for mnist-back-rand dataset and Polynomial kernel for textitmnist-
back-image dataset. The results in the table indicates that, in a multi-layer
architecture the contribution of individual kernels is highly varying in each
layer(no single kernel has complete dominance over all layers in the feature
learning process). However the exact reason why some kernels are weighted more
in a particular layer than the other kernels is not very clear.

layers | Kernel Weights
---|---
$k_{1}$ | $k_{2}$ | $k_{3}$ | $k_{4}$ | $k_{5}$ | $k_{6}$ | $k_{7}$
Layer 1 | 0.2007 | 0.1331 | 0.1331 | 0.1332 | 0.1332 | 0.1333 | 0.1333
Layer 2 | 0.2711 | 0.1160 | 0.1181 | 0.1203 | 0.1225 | 0.1248 | 0.1271
Layer 3 | 0.1764 | 0.0999 | 0.1125 | 0.1266 | 0.1426 | 0.1607 | 0.1811
Layer 4 | 0.0598 | 0.0524 | 0.0747 | 0.1071 | 0.1547 | 0.2245 | 0.3269
Layer 5 | 0.0514 | 0.0493 | 0.0726 | 0.1069 | 0.1569 | 0.2295 | 0.3334
TABLE II: Kernel weights in each layer for the mnist-back-rand dataset layers | Kernel Weights
---|---
$k_{1}$ | $k_{2}$ | $k_{3}$ | $k_{4}$ | $k_{5}$
Layer 1 | 0.2445 | 0.1887 | 0.1888 | 0.1889 | 0.1891
Layer 2 | 0.3421 | 0.1603 | 0.1630 | 0.1659 | 0.1688
Layer 3 | 0.2035 | 0.1615 | 0.1843 | 0.2104 | 0.2403
Layer 4 | 0.0843 | 0.1409 | 0.1877 | 0.2508 | 0.3362
TABLE III: Kernel weights in each layer for the mnist-back-image dataset

##  V Conclusion

In this paper we explored the concept of Multiple Kernel Learning in MKMs. A
linear combination of multiple kernels formulated purely from unlabelled data
is used in each layer of MKMs. The learning process of the proposed ML-MKL
algorithm employs a greedy layerwise training for each layer. Empirical
results indicates that using (unsupervised)MKL in in MKMs improves the
classifier performance. The classification accuracy is better than learning
machines with shallow architectures and is comparable with existing deep
architectures.

The proposed ML-MKL algorithm can be extended in many ways. One immediate
future direction to explore is to devise fine-tuning mechanism with respect to
the entire architecture after kernel weights in each layer is obtained.
Exploratory analysis on the features obtained is a second possible direction
for further studies.

##  Appendix A Derivation of the objective function $J(\mu)$

The objective function to be minimized is given by

$\min_{k\in K_{conv}}\frac{1}{2}\sum_{i=1}^{n}\left\lVert x_{i}-\sum_{x_{j}\in
B_{i}}k_{ij}x_{j}\right\rVert^{2}+\gamma*\sum_{i=1}^{n}\sum_{x_{j}\in
B_{i}}k_{ij}\left\lVert x_{i}-x_{j}\right\rVert^{2}$

Expanding the norm on the first part of the sum

$\begin{split}\min_{k\in K_{conv}}\frac{1}{2}\sum_{i=1}^{n}\bigg{(}\left\lVert
x_{i}\right\rVert^{2}-2*\sum_{x_{j}\in B_{i}}k_{ij}\langle
x_{i},x_{j}\rangle+\\\ k_{i}k_{i}^{T}\circ d_{i}d_{i}^{T}\circ
X^{T}X\bigg{)}+\gamma*\sum_{i=1}^{n}\sum_{x_{j}\in B_{i}}k_{ij}\left\lVert
x_{i}-x_{j}\right\rVert^{2}\end{split}$ (5)

The notation ‘$\circ$’ denotes elementwise multiplication of two vectors. Here
the summation $\sum_{i=1}^{n}\left\lVert x_{i}\right\rVert^{2}$ can be
discarded, since it is independent of the optimization parameters.
Substituting $X^{T}X=P$,

$\sum_{x_{j}\in B_{i}}k_{ij}\langle x_{i},x_{j}\rangle=k_{i}\circ d_{i}\circ
p_{i}$

and

$\sum_{x_{j}\in B_{i}}k_{ij}\left\lVert x_{i}-x_{j}\right\rVert^{2}=k_{i}\circ
d_{i}\circ v_{i}$

in 5 we will get the simplified objective function

$\begin{split}\min_{k\in K_{conv}}\sum_{i=1}^{n}\bigg{(}k_{i}k_{i}^{T}\circ
d_{i}d_{i}^{T}\circ P+\\\ 2\big{(}\gamma*k_{i}\circ v_{i}\circ
d_{i}-k_{i}\circ p_{i}\circ d_{i}\big{)}\bigg{)}\end{split}$ (6)

Here $p_{i}$ and $v_{i}$ are columns of $P$ and $M$ corresponding to $x_{i}$
respectively. Substituting $k_{i}=\sum_{t=1}^{m}\mu_{t}k_{t,i}$ in 6 we will
get

$\min_{\mu\in\Delta}\mu^{T}\Bigg{(}\sum_{t=1}^{m}\sum_{i=1}^{n}k_{t,i}k_{t,i}^{T}\circ
d_{i}d_{i}^{T}\circ P\Bigg{)}^{T}\mu+z^{T}\mu$

which is the objective function $J(\mu)$.

## References

  * [1] Y. Cho, L.K. Saul, Kernel Methods for Deep Learning  _Advances in Neural Information Processing Systems(NIPS)_ Volume 22, 342 – 350, 2009.
  * [2] Yoshua Bengio and Yann LeCun, Scaling learning algorithms towards AI, in Bottou, L. and Chapelle, O. and DeCoste, D. and Weston, J. (Eds)  _Large-Scale Kernel Machines_ , MIT Press, 2007.
  * [3] Yoshua Bengio, Aaron Courville and Pascal Vincent, Representation Learning: A Review and New Perspectives  _IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI)_ Volume 35, 1798–1828, August 2013.
  * [4] Yoshua Bengio, Learning Deep Architectures for AI  _Foundations and Trends in Machine Learning_ Volume 2, 1 – 127, January 2009.
  * [5] Benjamin Graham, Fractional Max-pooling,  _arxiv:cs/arXiv:1412.6071_ , 2014.
  * [6] Li Wan, Matthew Zeiler, Sixin Zhang, Yann LeCun and Rob Fergus, Regularization of Neural Networks using DropConnect,  _JMLR Proceedings_ Volume 28, 1058 – 1066, 2013.
  * [7] Geoffrey Hinton, Li Deng, Dong Yu, George Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara Sainath and Brian Kingsbury, Deep Neural Networks for Acoustic Modeling in Speech Recognition  _IEEE Signal Processing Magazine_ Volume 29, 82 – 97, 2012.
  * [8] Alex Krizhevsky, Ilya Sutskever and Geoffrey E. Hinton, ImageNet Classification with Deep Convolutional Neural Networks,  _Neural Information Processing Systems(NIPS)_ , 1106 – 1114, 2012.
  * [9] R. Collobert and J. Weston. A unified architecture for natural language processing: Deep neural networks with multitask learning  _International Conference on Machine Learning(ICML)_ , 2008.
  * [10] Geoffrey E. Hinton, Simon Osindero, and Yee Whye Teh, A fast learning algorithm for deep belief nets,  _Neural Computation_ , 2006.
  * [11] Yann LeCun, Léon Bottou, Yoshua Bengio and Patrick Haffner, Gradient based learning applied to document recognition,  _Proceedings of the IEEE_ , 2278–2324, November 1998.
  * [12] Rajat Raina, Anand Madhavan and Andrew Y. Ng, Large-scale Deep Unsupervised Learning using Graphics Processors,  _International Conference on Machine Learning_ , 2009.
  * [13] Jeffrey Dean, Greg S. Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V. Le, Mark Z. Mao, Marc’Aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang and Andrew Y. Ng, Large Scale Distributed Deep Networks,  _Advances in Neural Information Processing Systems_ , 1223 – 1231, 2012.
  * [14] Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin and J. Hellerstein, GraphLab: A New Framework For Parallel Machine Learning  _26th Conference on Uncertainty in Artificial Intelligence (UAI)_ , 2010.
  * [15] Bernhard Schölkopf, Alexander Smola and Klaus-Robert Müller, Nonlinear Component Analysis As a Kernel Eigenvalue Problem  _journel of Neural Computation_ Volume 10, 1299 – 1319, 1998.
  * [16] J. Zhuang, Jialei Wang, Steven C.H Hoi, Xiangyang Lan, Unsupervised Multiple Kernel Learning  _Journal of Machine Learning Research(JMLR)_ Volume 20, 129 – 144, 2011.
  * [17] Gert R. G. Lanckriet, Nello Cristianini, Peter L. Bartlett, Laurent El Ghaoui, and Michael I. Jordan, Learning the kernel matrix with semidefinite programming  _Journal of Machine Learning Research_ , Volume 5, 27–72, 2004.
  * [18] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M.Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, Scikit-learn: Machine Learning in Python  _Journal of Machine Learning Research(JMLR)_ Volume 12, 2825 – 2830, 2011.
  * [19] Y. LeCun and C. Cortes, The MNIST database of handwritten digits  http://yann.lecun.com/exdb/mnist/.
  * [20] Jinfeng Zhuang, Ivor W. Tsang and Steven C.H. Hoi, Two-layer Multiple Kernel Learning.  _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , pp 909–917, 2011.
  * [21] Ilyes Rebai, Yassine BenAyed and Walid Mahdi, Deep Multilayer Multiple Kernel Learning  _Journal of Neural Computing and Applications_ , pp 1–10, 2015.


Michael Levit, Sarangarajan Parthasarathy, Cem Aksoylar, Mohammad Sadegh
Rasooli, Shuangyu Chang

# External Language Model Integration for Factorized Neural Transducers

###### Abstract

We propose an adaptation method for factorized neural transducers (FNT) with
external language models. We demonstrate that both neural and n-gram external
LMs add significantly more value when linearly interpolated with predictor
output compared to shallow fusion, thus confirming that FNT forces the
predictor to act like regular language models. Further, we propose a method to
integrate class-based n-gram language models into FNT framework resulting in
accuracy gains similar to a hybrid setup. We show average gains of 18% WERR
with lexical adaptation across various scenarios and additive gains of up to
60% WERR in one entity-rich scenario through a combination of class-based
n-gram and neural LMs.

Index Terms: Factorized neural transducer, RNN-T adaptation with text

##  1 Introduction

With large amounts of paired speech and text data available for ASR training,
end-to-end (E2E) automatic speech recognition (ASR) systems have become
competitive with hybrid ASR systems [1, 2, 3]. E2E alternatives have the
advantage of architectural simplicity compared to hybrid ASR systems in which
acoustic models, language models, and pronunciation models are independently
trained. However, a consequence of joint modeling is that effective adaptation
to target scenarios using text-only tuning data becomes challenging. There are
generally four ways to perform text-only adaptation:

  * •

Rescoring and reranking: after decoding, use a powerful external LM to update
scores and rerank n-best results or recognition lattice [4, 5, 6];

  * •

Audio generation: generate audio for training texts via TTS [7, 8], data
splicing [9] or learn to emulate encoder output from texts on the fly [10];

  * •

Fusion and biasing: during decoding interpolate posterior word probabilities
with text priors from external LMs [11, 12, 13, 14, 15];

  * •

Explicit separation of internal LMs: force the E2E decoder/predictor to behave
more like a language model [16, 17, 18, 19, 20].

In this paper, we focus on the last approach using factorized neural
transducers (FNT) [20] which is an extension of RNN-T [21] that makes the
predictor network act like a proper language model. We investigate linear/log-
linear interpolation approaches for augmenting FNT predictor activations with
probabilities from external in-domain n-gram and neural models, and
demonstrate that these methods are superior to the shallow fusion baseline. We
also show how the n-gram approach can be extended to handle class-based n-gram
LMs via linear interpolation, resulting in adaptation improvements comparable
to those achievable with a hybrid recognizer. A number of important
adjustments necessary for an effective application of the interpolated class-
based setup is also discussed.

The remainder of this paper is organized as follows. In §2 we explain the
basic principles of FNTs and how various types of external LMs can be
integrated with them. An experimental section follows, and the paper is
concluded with a summary of presented results.

##  2 LM Adaptation via Interpolation

In this section, we describe our approach for LM adaptation via interpolation.
The FNT model is an extension of the RNN-T model in which the predictor
network is factored into two different predictors, one for the blank
($\mathop{\phi}$) likelihood and the other for non-blank words in vocabulary
${\cal V}$. We follow the model from [20] which is depicted in Fig. 1. The
following equations show the full pipeline of an FNT model (for the sake of
brevity we omit biases):

$\displaystyle\boldsymbol{f}_{t}$ $\displaystyle=$
$\displaystyle\mathrm{encoder}(x_{1}^{t})$
$\displaystyle\boldsymbol{g}_{u}^{\mathop{\phi}}$ $\displaystyle=$
$\displaystyle\mathrm{predictor}_{\mathop{\phi}}(y_{1}^{u})$
$\displaystyle\boldsymbol{z}^{\mathop{\phi}}_{t,u}$ $\displaystyle=$
$\displaystyle
W_{j}\cdot\mathrm{relu}(W_{\mathrm{e}}\cdot\boldsymbol{f}_{t}+W_{\mathrm{d}}\cdot\boldsymbol{g}_{u}^{\phi})$
$\displaystyle\boldsymbol{z}^{v}_{t}$ $\displaystyle=$
$\displaystyle\mathop{\rm
log~{}\sigma}(\boldsymbol{W}_{\mathrm{enc}}^{v}\cdot\boldsymbol{f}_{t})$ (1)
$\displaystyle\boldsymbol{g}_{u}^{v}$ $\displaystyle=$
$\displaystyle\mathrm{predictor}_{\cal V}(y_{1}^{u})$
$\displaystyle\boldsymbol{z}^{v}_{u}$ $\displaystyle=$
$\displaystyle\mathop{\rm
log~{}\sigma}(\boldsymbol{W}_{\mathrm{pred}}^{v}\cdot\boldsymbol{g}_{u}^{v})$
(2) $\displaystyle\boldsymbol{z}^{v}_{t,u}$ $\displaystyle=$
$\displaystyle\boldsymbol{z}^{v}_{t}+\boldsymbol{z}^{v}_{u}$ (3)
$\displaystyle P({\hat{y}}_{t+1}|x_{1}^{t},y_{1}^{u})$ $\displaystyle=$
$\displaystyle\mathop{\rm\sigma}([\boldsymbol{z}^{v}_{t,u};\boldsymbol{z}^{\mathop{\phi}}_{t,u}])$
(4)

where $\sigma$ is the softmax function. The values
$P(\hat{y}_{t+1}|x_{1}^{t},y_{1}^{u})$ and $\boldsymbol{z}^{v}_{u}$ are used
for RNN-T and cross-entropy losses respectively during training and in some
cases, $\boldsymbol{z}^{v}_{t}$ can also be used for an additional CTC loss
[22].

Since the predictor in FNT behaves like an LM [20], it can be adapted to the
target domain by interpolating with an external LM [23]. This approach has
several advantages over other approaches for E2E adaptation. For instance, an
in-domain LM can be built on large text corpora and interpolated with the
predictor in near-real time. Furthermore, unlike rescoring which takes place
at the end of recognition, interpolation can directly influence the beam
search during decoding and preserve paths that could otherwise be dismissed in
the beam. Finally, interpolation has leverage compared to shallow fusion in
terms of explainability since the interpolation happens entirely within the
space of prior probabilities.

Figure 1: Schematic diagram of the factorized neural transducer model  _[20]_.
$\phi$ represents the _blank_ symbol.

Language model fusion techniques [11, 12, 13] remain popular because they are
simple to implement, reasonably effective, and generally robust. We use
shallow fusion (SF) [11] in our experiments as a baseline. Using notations
above, Eqs. (2,3) can be updated to account for SF, linear (LI) and log-linear
(LLI) interpolation respectively:

$\displaystyle\bar{\boldsymbol{z}}^{v}_{t,u}$ $\displaystyle=$
$\displaystyle\mathop{\rm
SF}(\boldsymbol{z}^{v}_{t,u},\boldsymbol{p}_{u})=\alpha\log\boldsymbol{p}_{u}+(1-\alpha)\boldsymbol{z}^{v}_{t,u}$
(5) $\displaystyle\bar{\boldsymbol{z}}^{v}_{u}$ $\displaystyle=$
$\displaystyle\mathop{\rm
LI}(\boldsymbol{z}^{v}_{u},\boldsymbol{p}_{u})=\log(\alpha\boldsymbol{p}_{u}+(1-\alpha)\exp(\boldsymbol{z}^{v}_{u}))$
(6) $\displaystyle\bar{\boldsymbol{z}}^{v}_{u}$ $\displaystyle=$
$\displaystyle\mathop{\rm
LLI}(\boldsymbol{z}^{v}_{u},\boldsymbol{p}_{u})=\alpha\log\boldsymbol{p}_{u}+(1-\alpha)\boldsymbol{z}^{v}_{u}$
(7)

where $\boldsymbol{p}_{u}$ is a tensor of word111For clarity, we will refer to
basic modeling units as words and not subwords that they actually are, unless
explicitly stated otherwise. probabilities given history according to the
external LM and $\alpha$ is interpolation weight assigned to the external
model. If interpolation is applied to a subset of words rather than all of
them, we can call it biasing [24].

Combining predictor output with external neural LMs (NNLMs) is intuitive and
simple. Assuming that the external model operates with the same lexicon (e.g.
word-pieces) as the E2E network, $\boldsymbol{p}_{u}$ is just a vector of
normalized projections from the external NNLM. While used for RNN-T adaptation
in several studies [25, 17], external NNLMs are difficult to estimate when
only a small amount of text adaptation material is available. Instead, in such
cases a large pretrained NNLM needs to be tuned on the in-domain data, which
complicates personalization and plug-and-play abilities due to added time and
memory requirements. With this caveat, we found that in some cases, and in
particular for less-structured scenarios with a lot of conversational
language, external NNLMs can offer superior adaptation results w.r.t. their
n-gram counterparts.

Integration of external NNLMs into FNT framework in both SF and interpolation
settings is relatively straightforward and, for the most part, realized
through augmentation of search states in sets $B$ (final states at each time
step) and $A$ (expanded states) of the beam search decoder [21] with hidden
states and outputs of the external NNLM.

###  2.1 Adaptation with N-gram Language Models

For n-gram models, LM states $s$ are short sequences (histories) of previous
tokens. Therefore, definitions for RNN-T states in sets $A$ and $B$ have to be
adjusted to contain these histories. However, querying n-gram language model
probabilities is a one-by-one look-up process that breaks highly
parallelizable tensor operations on neural networks. Additional optimization
techniques such as one-step acceleration [26, 27] also lose their
attractiveness for n-gram adaptation for the same reason.

To that end, we employ several optimization techniques to speed up
interactions with n-grams LMs. In addition to extensive caching, we do not
consult external n-gram LMs for all words in a given context but just for the
ones with reasonably high probabilities (e.g. up to a certain _rank_ $r$ in a
sorted list). Thus, for finite history $h$, external probability
$\boldsymbol{p}_{u}$ turns into a sparse vector of probabilities
$P_{\mathop{\rm\scriptsize ng}}(w|h)$ that is defined only for some words $w$.
This makes our approach similar to the biasing scheme used in [28] except the
decision which word to bias depends on its probability in the external LM and
not on the word itself. The conditional linear interpolation formula (C-LI)
for individual words of the $\bar{\boldsymbol{z}}^{v}_{u}$ tensor can be
written as:

$\displaystyle\bar{z}^{v}_{u}(w)$ $\displaystyle=$ $\displaystyle\mathop{\rm
C{\text{-}}LI}(z^{v}_{u}(w),P_{\mathop{\rm\scriptsize ng}}(w|h))$
$\displaystyle=$ $\displaystyle\left\\{\begin{array}[]{ll}\mathop{\rm
LI}(z^{v}_{u}(w),P_{\mathop{\rm\scriptsize ng}}(w|h)),&\mbox{if }\mathop{\rm
rank}\limits_{P_{\mathop{\rm\scriptsize ng}}(w|h)}(w)<r\\\
z^{v}_{u}(w)&\mbox{otherwise}.\end{array}\right.$

An efficient approximation for such conditional interpolation can be achieved
by representing n-gram trie as a collection of sorted arrays [29] such that
for each history-node, identities and probabilities of all word-arcs can be
found in constant time, low-probability words dismissed and iterative fall-
backs to shorter histories performed until the requested number of high-
probability words is collected. With this approximation and $r=200$, we
observe only $\approx 20\%$ slow-down during inference due to interpolation
with medium-sized n-grams models.

###  2.2 Interpolating with Class-based LMs

Class-based language models (CLMs) are much more difficult to work with in the
context of neural E2E solutions. For simplicity, only the case of linear
interpolation is considered here. In [30], SF biasing is done with a weighted
FST representing one class embedded in characteristic carrier phrases. In
contrast, we choose not to expand the class-based model into a single WFST,
but preserve class definitions as prefix trees at the expense of more
elaborate bookkeeping for CLM states $s$. With CLM trained on sentences tagged
in terms of classes, its states $s$ now include not just previous token
history $h$ (with tokens being words or classes), but also current position
(node) $p$ in the prefix tree of the active class $c$. For example, in a phone
assistant application with classes $\langle$name$\rangle$ (e.g. _``john
smith''_) and $\langle$type$\rangle$ (e.g. _``his mobile''_), a partial word
hypothesis _`` $<$s$>$ call john smith on his…''_ could end up in the
following state $s$ of a 4-gram CLM:

$s=\\{h:\text{\emph{$\langle$s$\rangle$ call $\langle${name}$\rangle$
on}},c:\text{$\langle${type}$\rangle$ },p:\text{\emph{his}}\\}$

The benefits of this representation include small memory footprint as well as
absent need to redistribute FSM weights [31, 30], thanks to readily available
cumulative posteriors in each node of the prefix tree. On the flip side,
without deterministic WFST, we now face the ambiguity of having the same
lexical history corresponding to potentially more than one state in the
external CLM. For instance, the above lexical hypothesis could also be
explained via state:

$s=\\{h:\text{\emph{call $\langle${name}$\rangle$ on
his}},c:\varnothing,p:\varnothing\\}$

In [32] a special decider network was trained to predict the next class given
token history. Our CLM integration, on the other hand, relies entirely on beam
search to find the most probable extension and does not require pretraining.

From the CLM point of view, RNN-T beam search expansions are mapped to three
types of transitions between CLM states:

  1. CAT1: n-gram part of the CLM emits word $w$;

  2. CAT2: prefix tree for class $c^{\prime}$ is entered with word $w$;

  3. CAT3: word $w$ advances within the current class $c$.

Let $P_{\mathop{\rm\scriptsize pt}}(*|c,p)$ be the exit probability from the
current state $s=\\{h,c,p\\}$ inside the class $c$ (set to $1.0$ if
$c=\varnothing$), and $s^{\prime}=\\{h^{\prime},\varnothing,\varnothing\\}$
the resulting new state. Then the CAT1/2/3 transition probabilities $P(w|s)$
are computed as:

$\displaystyle P^{1}(w|s)$ $\displaystyle=$ $\displaystyle
P_{\mathop{\rm\scriptsize pt}}(*|c,p)P_{\mathop{\rm\scriptsize
ng}}(w|h^{\prime})$ (11) $\displaystyle P^{2}(w|s)$ $\displaystyle=$
$\displaystyle P_{\mathop{\rm\scriptsize pt}}(*|c,p)P_{\mathop{\rm\scriptsize
ng}}(c^{\prime}|h^{\prime})P_{\mathop{\rm\scriptsize
pt}}(w|c^{\prime},\varnothing)$ (12) $\displaystyle P^{3}(w|s)$
$\displaystyle=$ $\displaystyle P_{\mathop{\rm\scriptsize pt}}(w|c,p)$ (13)

where $P_{\mathop{\rm\scriptsize ng}}(\cdot)$ values come from the CLM n-gram
statistics, and $P_{\mathop{\rm\scriptsize pt}}(\cdot)$ from class prefix
trees. Fig. 2 shows an example of such transitions. A single word can trigger
several CLM transition types but not all transitions types will be available
for each word. To start, CAT2/3 transitions are only possible for words
accepted in given class positions and also, to save computation, we will only
consider CAT2/3 transitions for words $w$ with high encoder scores:
$\mathop{\rm rank}\limits_{\boldsymbol{z}^{v}_{t}(w)}(w)<r^{\prime}$. Given
current LM state $s$, if $\mathcal{S}^{1}$, $\mathcal{S}^{2}$ and
$\mathcal{S}^{3}$ are lists of words for which CAT1/2/3 transitions are
possible (potentially with repetitions due to one-to-many mapping between word
sequences and CLM states explained above), then we can construct an augmented
version of $\boldsymbol{z}^{v}_{u}$ as a concatenation of three parts:

$\displaystyle\bar{\boldsymbol{z}}^{v}_{u}$ $\displaystyle=$
$\displaystyle\Bigr{[}\left\\{\mathop{\rm
C{\text{-}}LI}(z^{v}_{u}(w),P^{1}(w|s))\ \ \forall
w\in\mathcal{S}^{1}\right\\},$ $\displaystyle~{}\ \left\\{\mathop{\rm
LI}(z^{v}_{u}(w),P^{2}(w|s))\ \ \forall w\in\mathcal{S}^{2}\right\\},$
$\displaystyle~{}\ \left\\{\log(P^{3}(w|s))\ \ \forall
w\in\mathcal{S}^{3}\right\\}\Bigr{]}$

Note that the within-class transition probabilities in CAT3 are accepted
without interpolation with the predictor. The corresponding tensor of encoder
probabilities is then constructed as:

$\displaystyle\bar{\boldsymbol{z}}^{v}_{t}$ $\displaystyle=$
$\displaystyle\Bigr{[}\left\\{z^{v}_{t}(w)\ \ \forall
w\in\mathcal{S}^{1}\right\\},$ $\displaystyle\ \ \ \left\\{z^{v}_{t}(w)\ \
\forall w\in\mathcal{S}^{2}\right\\},\left\\{z^{v}_{t}(w)\ \ \forall
w\in\mathcal{S}^{3}\right\\}\Bigr{]}$

The order of words in $\mathcal{S}^{2}$ and $\mathcal{S}^{3}$ needs to be
observed in the same way in both Eqs. (2.2,2.2) and preserved throughout beam
search iterations at each time step to select the best states for expansion.
Typically, their sizes are much smaller than that of $\mathcal{S}^{1}$ and
therefore the respective two components do not add a prohibitive amount of
additional complexity to search. As a result, the average dimension of the
augmented
$\bar{\boldsymbol{z}}^{v}_{t,u}=\bar{\boldsymbol{z}}^{v}_{t}+\bar{\boldsymbol{z}}^{v}_{u}$
increases only slightly, as does the search space for the next $y^{*}$ in
terms of original notation in [21].

MaryJohnBrownSmithPrefix tree of class $\mathrm{\langle NAME\rangle}$…$P_{\rm
pt}(*|\phi,\phi)P_{\rm ng}(\mathrm{\langle NAME\rangle|\langle s\rangle}\
call)\ P_{\rm pt}(John|\mathrm{\langle
NAME\rangle},\phi)$CAT2CAT1callat$P_{\rm pt}(*|\phi,\phi)P_{\rm
ng}(call|\mathrm{\langle s\rangle})$$\begin{array}[]{l}P_{\rm
pt}(*|\mathrm{\langle NAME\rangle},John\ Smith)\\\ \times\ P_{\rm ng}(at\ |\
call\mathrm{\langle NAME\rangle})\end{array}$CAT1$P_{\rm
pt}(Smith|\mathrm{\langle NAME\rangle},\ John)$CAT3

Figure 2: Illustration of how three different transition types are applied to
partial sentence ``call John Smith at…''.

As for $\mathcal{S}^{1}$, it usually accounts for all words in ${\cal V}$ in
the natural order, so that the first components in Eqs. (2.2,2.2) are simply
$\boldsymbol{z}^{v}_{u}$ and $\boldsymbol{z}^{v}_{t}$. However, if $s$ is
within a class $c$ and $P_{\mathop{\rm\scriptsize pt}}(*|c,p)=0$, then no CAT1
transitions are possible and $\mathcal{S}^{1}=\varnothing$. In this case,
$\mathcal{S}^{1}$ is removed from the augmented definitions
$\bar{\boldsymbol{z}}^{v}_{u}$ and $\bar{\boldsymbol{z}}^{v}_{t}$, leading to
a speed-up in decoding. A further important refinement to this case concerns
the situation where all three sets $\mathcal{S}^{1,2,3}$ are empty resulting
in empty tensors in Eqs. (2.2,2.2). In absence of lexical competitors,
emitting blank token $\phi$ would incur no costs. To alleviate this problem,
we then compute the probability of $\phi$ by applying the final softmax Eq.
(4) to a tensor of original values $\boldsymbol{z}^{v}_{t,u}$ (before
interpolation). Another potential way of addressing this situation is to
properly separate blank probabilities in advance as suggested in [16, 17].

Finally, to reduce the chance of having all search states in the beam
traversing CLM entities only to discover a dead end, we modify the loop exit
condition of the beam search algorithm to require at least some states in $B$
with available CAT1 options, effectively increasing average beam width by
about 20%.

##  3 Experiments and Results

###  3.1 Scenarios and Recognition Setup

We evaluate our models on five English language setups covering a wide range
of scenarios, with some setups containing multiple splits that we separately
train and evaluate over: human-human instructions in spontaneous language
(HI), human-human telephone conversations (HTC and L-HTC), strongly structured
product ordering (PO) and human-machine interactive-voice-response systems
(HMIVR). Each setup has a test set of about 1K utterances per split over which
we report average WER, and training set sizes per split varying from
$\sim$1.2K utterances for PO to $\sim$15K each for HTC and $\sim$24M for L-HTC
as a notable exception. All data is anonymized.

Our baseline FNT system was trained on a large (though not production
scale222We are not allowed to disclose exact size of the training material.)
anonymized corpus of paired audio and text data, compiled from a variety of
Microsoft services. The encoder consists of 18 transformer layers and the
predictor is a two-layer LSTM initialized by an LM trained on the text portion
of the paired data. The word-piece [33] vocabulary of 4.5K units was also
trained on the same corpus as the pretrained LM. For more information on the
training process please see [34].

###  3.2 Lexical Adaptation

Table 1: Baseline word error rate (WER) and word error rate reduction (WERR) due to different lexical adaptation methods Corpus | Baseline | NNLM WERR ($\alpha^{*}$) | N-gram WERR ($\alpha^{*}$) | NNLM WERR ($\alpha^{0}$) | N-gram WERR ($\alpha^{0}$)
---|---|---|---|---|---
| WER | SF | LI | LLI | SF | LI | LLI | SF ($0.05$) | LI ($0.5$) | LLI ($0.5$) | SF ($0.25$) | LI ($0.5$) | LLI ($0.5$)
HI | 31.5% | 18% | 31% | 28% | 11% | 25% | 21% | 13% | 29% | 25% | 9% | 25% | 19%
HTC | 9.6% | 2% | 8% | 6% | 1% | 5% | 3% | 2% | 8% | 6% | -4% | 3% | 2%
L-HTC | 15.6% | 4% | 11% | 9% | 1% | 7% | 5% | 4% | 11% | 9% | 0% | 7% | 5%
PO | 21.2% | 7% | 24% | 23% | 23% | 33% | 29% | 4% | 23% | 21% | 18% | 31% | 25%
HMIVR | 10.6% | 1% | 8% | 14% | 5% | 29% | 41% | -18% | -8% | 9% | -11% | 14% | 41%
Average | 16.3% | 7.7% | 17.8% | 16.0% | 8.7% | 17.6% | 15.2% | 4.5% | 16.0% | 14.3% | 4.0% | 15.7% | 13.2%

In this section, we evaluate adapted setups utilizing neural and n-gram LMs
trained as described in §2 using lexical form adaptation training data for
each scenario, comparing shallow fusion (SF, c.f. Eq. (5)) and interpolation
(LI/LLI, Eqs. (6,7)) approaches described in §2.

Neural LMs adapted to the target scenario were trained as follows: we
initialized the adapted LM by pretraining on a curated conversational corpus
of about 10 billion words, froze the embedding parameters, and fine-tuned the
parameters of the LSTM layers using CE loss for two passes over the adaptation
data. For adaptation using n-gram LMs, we trained a 5-gram model with Kneser-
Ney smoothing for each scenario, without utilizing any n-gram cutoffs or
pruning. The adaptation data was represented using the same 4.5K word-piece
units as the FNT model. The resulting model sizes ranged from $\sim$17K
n-grams for PO scenarios to $\sim$600K for HTC scenarios, with the exception
of $\sim$100M n-grams for L-HTC scenario.

For both n-gram and neural models, we evaluate with a fixed set of
interpolation weights $\alpha\in\\{0.01,0.05,0.1,$ $0.25,0.5,0.9\\}$ where we
omit the last two sets of weights for SF due to worsening performance. We
present WERR performance for all three methods across all scenarios in Table 1
for two weighting schemas: $\alpha^{*}$ where we choose the best-performing
weight for each corpus-method combination and $\alpha^{0}$ where we choose a
fixed weight for each method that performs best when averaged across all
corpora. The best-performing weights for each method are denoted next to the
method name. The bold items are the best-performing methods for each corpus
and weighting scheme. The final averages are computed as a weighted average
over the five setups.

From the results, we first observe that shallow fusion SF performs
significantly worse than the other methods LI/LLI, whereas the two result in
similar accuracy, with LI edging out LLI for all scenarios except HMIVR.
Another observation is that while NNLM-based adaptation gives slightly higher
WERR than n-gram adaptation on average, there are certain scenarios where
n-gram models significantly outperform, namely product ordering (PO) and
human-machine IVR (HMIVR). We note that these two scenarios are very
structured human-machine interactions, whereas the rest are more free-form and
conversational. In particular, telephone conversations corpus (HTC) contains
longer utterances that are less structured and consequently we see a larger
gap between NNLM and n-gram adaptation, and lesser gains due to adaptation
overall. Given the ease of training n-gram models on smaller amounts of data
and the small observed performance gaps, n-gram adaptation is competitive with
NNLM-based adaptation. Finally, we note that the WERR performance over the
space of $\alpha$'s is relatively smooth for non-SF methods, which can also be
observed from the small WERR gap between two weight selection regimes
$\alpha^{*}$ and $\alpha^{0}$. This is promising for practical applications
since extensive tuning of weights does not seem to be necessary for good
adaptation performance.

###  3.3 Class-based Adaptation

To test linear interpolation with external CLMs we chose one split of the
product ordering scenarios PO1 as well as two additional setups: one
engineered data set of home entertainment command-and-control queries (HE) and
another collection of personal assistant interactions mostly about calendar
operations (PA). Tagged training sentences and class definitions for CLM have
all been converted to word-pieces using the same model used to prepare FNT
data. Table 2 offers more information regarding these corpora. All test sets
contain $\sim$1200 utterances.

Table 2: Setups used for FNT+CLM evaluation Corpus | Train sent | Class sizes | Entity coverage
---|---|---|---
PO1 | 35 | 1212, 121, 8, 8, 7, 4 |  50-80%
HE | 731 | 827 | 100%
PA | 15 | 990 |  80%

The effect of incorporating CLM via linear interpolation with FNT predictor is
summarized in Table 3. A very significant WER improvement of up to 55% is
observed on all domains. At this point, the optimal interpolation weights
$\alpha^{*}$ have been found via parameter sweep. However, here too, the
weight space appears to be smooth and one should be able to optimize a single
weight parameter with a small validation set. In addition to FNT numbers, we
also present results for respective hybrid ASR setups where word-level CLM was
interpolated with the large n-gram LM with $\alpha$ optimized similarly. It
can be seen that FNT and hybrid WER improvements are in the same ballpark,
providing yet another confirmation of a proper LM separation in FNT. Note that
comparison of absolute WER numbers does not make sense in context of these
setups, because FNT and hybrid ASR were trained on different training data.

Table 3: Effect of linear interpolation with CLM Corpus | FNT | Hybrid
---|---|---
| Baseline | $\alpha^{*}_{\mbox{\scriptsize FNT}}$ | WERR | $\alpha^{*}_{\mbox{\scriptsize hyb}}$ | WERR
PO1 | 21.1% | 0.9 | 54% | 0.2 | 31%
HE | 5.3 % | 0.6 | 55% | 0.9 | 73%
PA | 20.6% | 0.9 | 36% | 0.9 | 60%

Since for PO1 we also had a separate lexical training corpus as described in
§3.1, a three-way interpolation between predictor, external adapted NNLM and
CLM was possible. We applied it in consecutive manner, first linearly
interpolating with NNLM, and then with the CLM using previously found optimal
interpolation weights. The outcome was further reduced WER on this set with
overall WERR reaching 60%.

##  4 Conclusions

We showed how external language models can be integrated into FNT framework.
Our experiments proved that in-domain n-gram and neural LMs can be linearly
interpolated with the predictor model and improve WER far beyond what is
possible with shallow fusion. In addition, we suggested an extension of the
integration algorithm that also allows using class-based n-gram models for
linear interpolation, achieving WERR of over 50% on our internal sets. A
combination of neural and class-based n-gram LMs produced the best overall
results.

## References

  * [1] T. N. Sainath, Y. He, B. Li, A. Narayanan, R. Pang, A. Bruguier, S.-y. Chang, W. Li, R. Alvarez, Z. Chen _et al._ , ``A streaming on-device end-to-end model surpassing server-side conventional model quality and latency,'' in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 6059–6063.
  * [2] J. Li, R. Zhao, Z. Meng, Y. Liu, W. Wei, S. Parthasarathy, V. Mazalov, Z. Wang, L. He, S. Zhao _et al._ , ``Developing RNN-T models surpassing high-performance hybrid models with customization capability,'' _arXiv preprint arXiv:2007.15188_ , 2020.
  * [3] A. Radford, J. W. Kim, T. Xu, G. Brockman, C. McLeavey, and I. Sutskever, ``Robust speech recognition via large-scale weak supervision,'' _arXiv preprint arXiv:2212.04356_ , 2022.
  * [4] L. Xu, Y. Gu, J. Kolehmainen, H. Khan, A. Gandhe, A. Rastrow, A. Stolcke, and I. Bulyko, ``Rescorebert: Discriminative speech recognition rescoring with BERT,'' in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 6117–6121.
  * [5] S.-H. Chiu and B. Chen, ``Innovative BERT-based reranking language models for speech recognition,'' in _2021 IEEE Spoken Language Technology Workshop (SLT)_. IEEE, 2021, pp. 266–271.
  * [6] E. Beck, R. Schlüter, and H. Ney, ``LVCSR with transformer language models.'' in _INTERSPEECH_ , 2020, pp. 1798–1802.
  * [7] Y. Deng, R. Zhao, Z. Meng, X. Chen, B. Liu, J. Li, Y. Gong, and L. He, ``Improving RNN-T for domain scaling using semi-supervised training with neural TTS.'' in _Interspeech_ , 2021, pp. 751–755.
  * [8] A. Fazel, W. Yang, Y. Liu, R. Barra-Chicote, Y. Meng, R. Maas, and J. Droppo, ``Synthasr: Unlocking synthetic data for speech recognition,'' _arXiv preprint arXiv:2106.07803_ , 2021.
  * [9] R. Zhao, J. Xue, J. Li, W. Wei, L. He, and Y. Gong, ``On addressing practical challenges for RNN-Transducer,'' in _2021 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU)_. IEEE, 2021, pp. 526–533.
  * [10] A. Mittal, S. Sarawagi, and P. Jyothi, ``In-situ text-only adaptation of speech models with low-overhead speech imputations,'' in _to appear in ICLR workshop_ , 2023.
  * [11] J. Chorowski and N. Jaitly, ``Towards better decoding and language model integration in sequence to sequence models,'' in _Interspeech_ , 2016.
  * [12] C. Gulcehre, O. Firat, K. Xu, K. Cho, L. Barrault, H.-C. Lin, F. Bougares, H. Schwenk, and Y. Bengio, ``On using monolingual corpora in neural machine translation,'' _arXiv preprint arXiv:1503.03535_ , 2015.
  * [13] A. Sriram, H. Jun, S. Satheesh, and A. Coates, ``Cold fusion: Training seq2seq models together with language models,'' in _Interspeech_ , 2018.
  * [14] S. Toshniwal, A. Kannan, C.-C. Chiu, Y. Wu, T. N. Sainath, and K. Livescu, ``A comparison of techniques for language model integration in encoder-decoder speech recognition,'' in _2018 IEEE spoken language technology workshop (SLT)_. IEEE, 2018, pp. 369–375.
  * [15] E. McDermott, H. Sak, and E. Variani, ``A density ratio approach to language model fusion in end-to-end automatic speech recognition,'' in _2019 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU)_. IEEE, 2019, pp. 434–441.
  * [16] E. Variani, D. Rybach, C. Allauzen, and M. Riley, ``Hybrid autoregressive transducer (HAT),'' in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 6139–6143.
  * [17] Z. Meng, T. Chen, R. Prabhavalkar, Y. Zhang, G. Wang, K. Audhkhasi, J. Emond, T. Strohman, B. Ramabhadran, W. R. Huang _et al._ , ``Modular hybrid autoregressive transducer,'' in _2022 IEEE Spoken Language Technology Workshop (SLT)_. IEEE, 2023, pp. 197–204.
  * [18] Z. Meng, S. Parthasarathy, E. Sun, Y. Gaur, N. Kanda, L. Lu, X. Chen, R. Zhao, J. Li, and Y. Gong, ``Internal language model estimation for domain-adaptive end-to-end speech recognition,'' in _2021 IEEE Spoken Language Technology Workshop (SLT)_. IEEE, 2021, pp. 243–250.
  * [19] W. Zhou, Z. Zheng, R. Schlüter, and H. Ney, ``On language model integration for RNN transducer based speech recognition,'' in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 8407–8411.
  * [20] X. Chen, Z. Meng, S. Parthasarathy, and J. Li, ``Factorized neural transducer for efficient language model adaptation,'' in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 8132–8136.
  * [21] A. Graves, ``Sequence transduction with recurrent neural networks,'' _arXiv preprint arXiv:1211.3711_ , 2012.
  * [22] A. Graves, S. Fernández, F. Gomez, and J. Schmidhuber, ``Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks,'' in _Proceedings of the 23rd international conference on Machine learning_ , 2006, pp. 369–376.
  * [23] R. Zhao, J. Xue, P. Parthasarathy, V. Miljanic, and J. Li, ``Fast and accurate factorized neural transducer for text adaption of end-to-end speech recognition models,'' in _ICASSP_ , 2023.
  * [24] P. Aleksic, M. Ghodsi, A. Michaely, C. Allauzen, K. Hall, B. Roark, D. Rybach, and P. Moreno, ``Bringing contextual information to google speech recognition,'' in _Interspeech_ , 2015.
  * [25] R. Cabrera, X. Liu, M. Ghodsi, Z. Matteson, E. Weinstein, and A. Kannan, ``Language model fusion for streaming end to end speech recognition,'' _arXiv preprint arXiv:2104.04487_ , 2021.
  * [26] J. Kim and Y. Lee, ``Accelerating rnn transducer inference via one-step constrained beam search,'' _arXiv preprint arXiv:2002.03577_ , 2020.
  * [27] J. Kim, Y. Lee, and E. Kim, ``Accelerating rnn transducer inference via adaptive expansion search,'' _IEEE Signal Processing Letters_ , vol. 27, pp. 2019–2023, 01 2020.
  * [28] D. Zhao, T. Sainath, D. Rybach, P. Rondon, D. Bhatia, B. Li, and R. Pang, ``Shallow-fusion end-to-end contextual biasing,'' in _Interspeech_ , 09 2019, pp. 1418–1422.
  * [29] K. Heafield, ``KenLM: Faster and smaller language model queries,'' in _Proceedings of the sixth workshop on statistical machine translation_ , 2011, pp. 187–197.
  * [30] D. Le, G. Keren, J. Chan, J. Mahadeokar, C. Fuegen, and M. L. Seltzer, ``Deep shallow fusion for RNN-T personalization,'' in _2021 IEEE Spoken Language Technology Workshop (SLT)_. IEEE, 2021, pp. 251–257.
  * [31] G. Pundak, T. N. Sainath, R. Prabhavalkar, A. Kannan, and D. Zhao, ``Deep context: end-to-end contextual speech recognition,'' in _2018 IEEE spoken language technology workshop (SLT)_. IEEE, 2018, pp. 418–425.
  * [32] A. Bruguier, D. Le, R. Prabhavalkar, D. Li, Z. Liu, B. Wang, E. Chang, F. Peng, O. Kalinli, and M. L. Seltzer, ``Neural-FST class language model for end-to-end speech recognition,'' in _ICASSP_ , 2022, pp. 6107–6111.
  * [33] T. Kudo and J. Richardson, ``SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing,'' _EMNLP 2018_ , p. 66, 2018.
  * [34] J. Li, R. Zhao, E. Sun, J. H. M. Wong, A. Das, Z. Meng, and Y. Gong, ``High-accuracy and low-latency speech recognition with two-head contextual layer trajectory LSTM model,'' in _ICASSP_ , 2020, pp. 7699–7703.