# Structural Controllability of Polysystems via Directed Hypergraph
Representation

Joshua Pickard Joshua Pickard is with the Department of Computational Medicine
and Bioinformatics, Medical School, University of Michigan, Ann Arbor, MI
48109 USA (e-mail: jpic@umich.edu). This work is supported by the National
Institute of General Medical Sciences under award number GM150581.

###### Abstract

This document explores structural controllability of polynomial dynamical
systems or polysystems. We extend Lin’s concept of structural controllability
for linear systems, offering hypergraph-theoretic methods to rapidly assess
strong controllability. Our main result establishes that a polysytem is
structurally controllable when its hypergraph representation contains no
hyperedge dilation and no inaccessible vertices. We propose two efficient,
scalable algorithms to validate these conditions.

##  1 Introduction

In this document we study the controllability of the system

$\dot{\mathbf{x}}=\mathbf{f}(\mathbf{x})+\mathbf{B}\mathbf{u}$ (1)

where $\mathbf{x}\in\mathbb{R}^{n}$ is the system state, $\mathbf{f}$ is an
odd, homogeneous polynomial of $\mathbf{x}$, $\mathbf{B}\in\mathbb{R}^{n\times
m}$ is the control matrix, and $\mathbf{u}\in\mathbb{R}^{m}$ is the system
input. Limitations in the precision to which the entries of $\mathbf{f}$ and
$\mathbf{B}$ are known motivate structural controllability, initially
introduced for linear dynamical systems.

######  Definition 1 (Structurally Controllable, Lin (1974)).

Consider the linear dynamical system
$\dot{\mathbf{x}}=\mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{u}$ where
$\mathbf{A}\in\mathbb{R}^{n\times n}.$ The pair $(\mathbf{A},\mathbf{B})$ is
structurally controllable if and only if there exist a completely controllable
pair $(\hat{\mathbf{A}},\hat{\mathbf{B}})$, where $\hat{\mathbf{A}}$ is any
matrix with the same sparsity structure as $\mathbf{A}.$

There are several advantages of strutructural – over complete or strong –
controllability. Graph theoretic tests to verify structural controllability
are faster than PHB or Kalman-based tests required for complete or strong
controllability (Liu et al. (2011)); system identification is rarely performed
to infinite precision, which limits the claims we may make about the
complete/strong controllability of engineered or biological systems (Lee and
Markus (1967)); while dynamics of many real systems can’t be described
perfectly as linear or polynomial systems, the connectedness of the network
can be precisely identified. This motivated initial tests for structural
controllability of a linear system with a single input where
$\mathbf{b}\in\mathbb{R}^{n}$ takes the place of $\mathbf{B}.$

######  Theorem 1 (Lin (1974)).

The following properties are equivalent to structural controllability of a
linear system defined by the pair $(\mathbf{A},\mathbf{b}):$

  * •

There is no permutation of the cooridinates to bring the pair
$(\mathbf{A},\mathbf{b})$ to the form

$\begin{bmatrix}\mathbf{A}_{11}&0\\\
\mathbf{A}_{21}&\mathbf{A}_{22}\end{bmatrix}\text{ and }\begin{bmatrix}0\\\
\mathbf{b}_{2}\end{bmatrix}\text{ or
}rank\big{(}\begin{bmatrix}\mathbf{A}&\mathbf{b}\end{bmatrix}\big{)}<n$

  * •

The graph of $(\mathbf{A},\mathbf{b})$ is span by a cactus

  * •

The graph of $(\mathbf{A},\mathbf{b})$ contains no inaccessable node and no
dilation

Several extensions were made immediately after the work of Lin (1974) to
consider multiinput control systems (Shields and Pearson (1976)), strong
structural controllability (Mayeda and Yamada (1979)), and other similar
varieties of the problem. Inspired by Liu et al. (2011), there has been a
recent resurgence in the study and utilization of structural controllability
(Mousavi et al. (2018); Gao et al. (2014)). While there are limitations to the
structural controllability (Cowan et al. (2012)), this avenue of work presents
several advantages.

In this document, we define and propose conditions for the structural
controllability of odd, homogeneous polynomial systems with linear inputs
defined by a pair $(\mathbf{f},\mathbf{B})$ or $(\textsf{A},\mathbf{B})$ where
A is the tensor representation of $\mathbf{f}.$

######  Theorem 2.

A pair $(\textsf{A},\mathbf{B})$ is structurally controllable if there exist a
strongly controllable pair $(\hat{\textsf{A}},\hat{\mathbf{B}}),$ which occurs
if and only if the hypergraph of $(\textsf{A},\mathbf{B})$ contains no
hyperedge dialation and no inaccessable vertices.

We will prove Theorem 2 and develop a pair of algorithms that verify this
condition in quadratic time throughout this document, which is organized as
follows. Section 2 provides preliminary results on polynomial control systems
and their relationship to uniform, undirected hypergraphs, and then Section 3
provides several definitions for directed hypergraph structures. In Section 4,
Theorem 2 is proven using a directed hypergraph representation of polynomial
systems. Finally, in Section 5, fast hypergraph algorithms are proposed to
test for structural controllability.

##  2 Polynomial Systems

Jurdjevic and Kupka (1985) derived conditions for the strong controllability
of odd homogeneous polynomials with linear inputs.111A polynomial
$p(\mathbf{x})$ is homogeneous if
$p(\lambda\mathbf{x})=\lambda^{d}p(\mathbf{x}).$ $d$ is the degree of the
polynomial $p$ and the parity of $p$ is that of $d.$

######  Theorem 3 (Jurdjevic and Kupka (1985)).

Suppose that f is a homogeneous polynomial system of odd degree. Consider the
following system

$\dot{\textbf{x}}=\textbf{f}(\textbf{x})+\sum_{j=1}^{m}\textbf{b}_{j}u_{j}.$
(2)

Then system 2 is strongly controllable if and only if the rank of the Lie
algebra spanned by the set of vector fields
$\\{\textbf{f},\textbf{b}_{1},\textbf{b}_{2},\dots,\textbf{b}_{m}\\}$ is $n$
at all points of $\mathbb{R}^{n}$. Moreover, the Lie algebra is of full rank
at all points of $\mathbb{R}^{n}$ if and only if it is of full rank at the
origin.

The rank of the Lie algebra can be found by evaluating the recursive Lie
brackets of $\\{\textbf{f},\mathbf{B}_{:1},\dots,\mathbf{B}_{m:}\\}$ at the
origin. The Lie bracket of two vector fields f and g at a point x is defined
as

$[\textbf{f},\textbf{g}]_{\textbf{x}}=\nabla\textbf{g}(\textbf{x})\textbf{f}(\textbf{x})-\nabla\textbf{f}(\textbf{x})\textbf{g}(\textbf{x}),$

where $\nabla$ is the gradient operator. Directly evaluating the Lie algebra
generated by a polynomial vector field and set of linear inputs that act as
constant vector fields is computationally intractable for large systems;
however, the tensor representation of a polynomial allows for the utilization
of the Singular Value Decomposition (SVD) to accelerate construction of the
Lie algebra.

###  2.1 Tensor Representation of Polynomials

Any homogeneous polynomial can be represented through repeated tensor
contractions.

######  Definition 2 (Tensor Representation of Polynomials).

Given a $k$-mode, $n$-dimensional tensor A and a vector
$\mathbf{x}\in\mathbb{R}^{n},$ the repeated tensor-vector multiplication or
contraction

$\textsf{A}\times_{1}\mathbf{x}\times_{2}\dots\times_{k-1}\mathbf{x}=\textsf{A}\mathbf{x}^{k-1}$
(3)

is referred to as the homogeneous polynomial of $\textsf{A}.$222We use
$\times_{i}$ to denote the Tucker product or contraction of $\mathbf{x}$ with
the $i$th mode of $\textsf{A}.$ Throughout the remainder of the article, we
adopt the conventions of multilinear algebra presented in Kolda and Bader
(2009)

We are able to represent any homogeneous polynomial in the form of eq. 3, and
when A has $k$-modes or indices, the expression $\textsf{A}\mathbf{x}^{k-1}$
is a $k-1$th degree, homogeneous polynomial. Then, when $k$ has even parity,
$\textsf{A}\mathbf{x}^{k-1}$ is an odd homogeneous polynomial and we are able
to apply Theorem 3. In the remainder of this document, pairs
$(\mathbf{f},\mathbf{B})$ and $(\textsf{A},\mathbf{B})$ refer to odd
homogeneous polynomials and are used interchangeably, and we may rewrite our
equation of interest eq. 1 as

$\dot{\mathbf{x}}=\mathbf{f}(\mathbf{x})+\mathbf{B}\mathbf{u}\Longleftrightarrow\dot{\mathbf{x}}=\textsf{A}\mathbf{x}^{k-1}+\mathbf{B}\mathbf{u}.$
(4)

The homogeneous polynomial of $\textsf{A}\mathbf{x}^{k-1}$ can be expressed
equivalently through tensor matricization and Kronecker exponentiation as

$\textsf{A}\mathbf{x}^{[k-1]}=\textsf{A}_{(k)}\times(\overbrace{\mathbf{x}\otimes\dots\otimes\mathbf{x}}^{\text{$k-1$
times}})=\textsf{A}_{(k)}\mathbf{x}^{[k-1]},$ (5)

where $\textsf{A}_{(k)}$ denotes the $k$th mode unfolding of A (Kolda and
Bader (2009); Ragnarsson and Van Loan (2012)) and $\mathbf{x}^{[i]}$ denotes
Kronecker exponentiation (Pickard et al. (2023a)). The polynomial
representation provided in eq. 5 allows for the construction of a nonlinear
controllability matrix.

###  2.2 A Test for Polynomial Controllability

A Kalman-rank-like test for controllability is developed in Chen et al. (2021)
where eq. 4 is strongly controllable if and only if
$rank(\mathbf{C}(\textsf{A},\mathbf{B}))=n$ where
$\mathbf{C}(\textsf{A},\mathbf{B})$ is the nonlinear controllability matrix
defined

$\mathbf{C}(\textsf{A},\mathbf{B})=\begin{bmatrix}\mathbf{B}&\textsf{A}_{(k)}\mathbf{B}^{k-1}&\dots&\textsf{A}_{(k)}(\textsf{A}_{(k)}(\dots\textsf{A}_{(k)}\mathbf{B}^{[k-1]})^{[k-1]}\dots)^{[k-1]}\end{bmatrix}.$
(6)

In practice, the authors of Chen et al. (2021) do not explicitly construct
$\mathbf{C}(\mathbf{A},\mathbf{B})$ but rather developed a fast SVD based
algorithm to construct a reduced controllability matrix
$\mathbf{C}_{r}(\textsf{A},\mathbf{B})$ that will have the same rank; see
algorithm 1 for details.

Initially proposed for undirected (or really omnidirectional333Undirected
hypergraphs in Chen et al. (2021) have dynamics defined so that if there are
$k$ vertices in a hyperedge, then information propagates from all sets of
$k-1$ vertices to the remaining $k$th vertex. Similar to how an undirected
graph has a symmetric adjacency matrix and can be thought of as bidirectional,
the dynamics of undirected hypergraphs flow not in bi- or two directions, but
in all possible directions indicated by the vertices in the hyperedge. In this
sense, undirected hyperedges are omnidirectional.) hypergraphs, the adjacency
tensor A is supersymmetric. As a result, the published version of algorithm 1
proposed that all unfoldings of A are equivalent; however, to consider a
generic homogeneous polynomial where directionality is encoded in $\mathbf{f}$
and asymmetries of $\textsf{A},$ we must enforce that the unfolding
$\textsf{A}_{(k)}$ is utilized in line with eq. 5.

Algorithm 1 Chen et al. (2021)

0: $(\textsf{A},\mathbf{B})$

1: $\mathbf{A}=\textsf{A}_{(k)}$

2: Set $\textbf{C}_{r}=\textbf{B}$ and $j=0$

3: while $j<n$ do

4: Compute
$\textbf{L}=\textbf{A}(\textbf{C}_{r}\otimes\textbf{C}_{r}\otimes\stackrel{{\scriptstyle
k-1}}{{\cdots}}\otimes\textbf{C}_{r})$

5: Set $\textbf{C}_{r}=\begin{bmatrix}\textbf{C}_{r}&\textbf{L}\end{bmatrix}$

6: Compute the economy-size SVD of $\textbf{C}_{r}$, and remove the zero
singular values, i.e., $\textbf{C}_{r}=\textbf{U}\textbf{S}\textbf{V}^{\top}$
where $\textbf{S}\in\mathbb{R}^{s\times s}$, and $s$ is the rank of
$\textbf{C}_{r}$

7: Set $\textbf{C}_{r}=\textbf{U}$, and $j=j+1$

8: end while

9: return The reduced controllability matrix $\textbf{C}_{r}$.

###  2.3 Limitations of Strong Controllability

As it was argued by Lin (1974), even for linear systems
$(\mathbf{A},\mathbf{B}),$ the system identification problem of identifying
the parameter entries of $\mathbf{A}$ and $\mathbf{B}$ can be determined up to
numerical or more often experimental precision, which is problematic when
considering that the set of all completely controllable pairs
$(\mathbf{A},\mathbf{B})$ is open and dense.

######  Theorem 4 (Lee and Markus (1967)).

For any pair $(\mathbf{A},\mathbf{B})$ that is not completely controllable and
any $\varepsilon\in\mathbb{R},$ there exist a completely controllable pair
$(\mathbf{A}^{\prime},\mathbf{B}^{\prime})$ where
$\|\mathbf{A}-\mathbf{A}^{\prime}\|<\varepsilon$ and
$\|\mathbf{B}-\mathbf{B}^{\prime}\|<\varepsilon.$

When we consider our limitations in determining the parameters of
$(\mathbf{A},\mathbf{B})$ in the context of Theorem 4, there will always be a
completely controllable pair arbitrarily close to the system
$(\mathbf{A},\mathbf{B})$ that is identified. This problem exist equivalently
for pairs $(\textsf{A},\mathbf{B}).$

######  Proposition 1.

The set of odd homogeneous polynomial controllable systems defined by the
pairs $(\textsf{A},\mathbf{B})$ is open and dense: For any pair
$(\textsf{A},\mathbf{B})$ that is not strongly controllable and any
$\varepsilon\in\mathbb{R},$ there exist a strongly controllable pair
$(\textsf{A}^{\prime},\mathbf{B}^{\prime})$ such that
$\|\textsf{A}-\textsf{A}^{\prime}\|<\varepsilon$ and
$\|\mathbf{B}-\mathbf{B}^{\prime}\|<\varepsilon$.

###### Proof.

This proof follows a similar structure to the original proof that
$(\mathbf{A},\mathbf{B})$ is open and dense presented on page 100 in Theorem
11 of Lee and Markus (1967) with the notable exception that we exchange the
linear controllability matrix for the nonlinear controllability matrix
$\mathbf{C}(\mathbf{A},\mathbf{B}).$ ∎

The limitation of Proposition 1 motivates the definition of structural
controllability for odd homogeneous polynomial systems.

######  Definition 3.

An odd homogenenous polynomial represented by the pairs
$(\mathbf{f},\mathbf{B})$ or $(\textsf{A},\mathbf{B})$ is structurally
controllable if and only if there exist a strongly controllable pair
$(\hat{\textsf{A}},\hat{\mathbf{B}}).$

###  2.4 Hypergraph Preliminaries

Hypergraphs provide a convienient framework for representing the sparsity
structure $(\textsf{A},\mathbf{B})$ and were the initial motivation of
algorithm 1. A hypergraph $\mathcal{H}=\\{\mathcal{V},\mathcal{E}\\}$ is a
finite set of vertices $\mathcal{V}$ together with a set of hyperedges where
each hyperedge $\mathcal{E}\in\mathcal{E}$ is a subset of vertices i.e.
$e\subseteq\mathcal{P}(\mathcal{V})\backslash\\{\emptyset\\},$ where
$\mathcal{P}(\mathcal{V})$ denotes the power set of $\mathcal{V}$ and
$\backslash$ is the set difference. A hypergraph is $k$-uniform if all
hyperedges $e$ contain $k$ vertices. The adjacency tensor is the higher order
analogue of an adjacency matrix which represents the structure of a
hypergraph.

######  Definition 4 (Cooper and Dutle (2012)).

Let $\mathcal{H}=\\{\mathcal{V},\mathcal{E}\\}$ be a $k$-uniform hypergraph
with $n$ nodes. The adjacency tensor $\textsf{A}\in\mathbb{R}^{n\times
n\times\dots\times n}$ of $\mathcal{H}$, which is a $k$-th order
$n$-dimensional supersymmetric tensor, is defined as

$\textsf{A}_{j_{1}j_{2}\dots j_{k}}=\begin{cases}\frac{1}{(k-1)!}&\text{if
$\\{j_{1},j_{2},\dots,j_{k}\\}\in\mathcal{E}$}\\\
0&\text{otherwise}\end{cases}.$ (7)

The homogeneous polynomial of the adjacency tensor can be fit to any
homogeneous polynomial $\mathbf{f}(\mathbf{x})$ by modifying the values of the
coefficients or tensor entries in eq. 7, and conditions and fast algorithms
have been developed for the observability and controllability of hypergraph
dynamics with linear inputs and outputs.

######  Definition 5 (Chen et al. (2021); Pickard et al. (2023b)).

Given a $k$-uniform hypergraph $\mathcal{H}$ with $n$ nodes, the dynamics of
$\mathcal{H}$ with control inputs can be represented by

$\begin{cases}\dot{\mathbf{x}}&=\textsf{A}\mathbf{x}^{k-1}+\sum_{j=1}^{m}\textbf{b}_{j}u_{j}\\\
\mathbf{y}&=\mathbf{C}\mathbf{x}\end{cases}$ (8)

where, $\textsf{A}\in\mathbb{R}^{n\times n\times\dots\times n}$ is the
adjacency tensor of G, and
$\textbf{B}=\begin{bmatrix}\textbf{b}_{1}&\textbf{b}_{2}&\dots&\textbf{b}_{m}\end{bmatrix}\in\mathbb{R}^{n\times
m}$ is the control matrix.

We will utilize this hypergraph framework to develop conditions for structural
control in section 4. In the following section, we relax some of the above
requirements and develop new structures to discuss directed hypergraphs.

##  3 Directed Hypergraphs

In this section, we describe one method through which the hypergraph
representation of an odd, homogeneous polynomial $\mathbf{f}$ can be
constructed. In order to apply Theorem 3 or algorithm 1 to determine strong
controllability of eq. 4, we require odd, homogeneous polynomial dynamics.
This means that each term appearing in the right hand side of
$\dot{\mathbf{x}}=\mathbf{f}(\mathbf{x})$ must be the product of an odd number
of entries in $\mathbf{x}$ (these will be the tail edges), and to accommodate
tensor representation the number of entries from $\mathbf{x}$ must be uniform
accross all terms in $\mathbf{f}(\mathbf{x})$; however, there is no
restriction from Theorem 3 as to how many entries of $\dot{\mathbf{x}}$ that a
given hypertail can appear in (entries of $\dot{\mathbf{x}}$ with identical
tails will be the heads).

###  3.1 Definition and Tensor Representation

To develop a condition for structural control, we assign a directed hypergraph
structure to the pair $(\textsf{A},\mathbf{B})$. Given a polynomial
$\dot{\mathbf{x}}=\mathbf{f}(\mathbf{x}),$ the dynamics of each term
$\dot{\mathbf{x}}_{i}$ can be written as

$\dot{\mathbf{x}}_{i}=\sum_{XX\text{ given }\mathbf{x}_{i}}\ \prod_{YY\text{
given }XX}\mathbf{x}_{j},$

where $XX$ and $YY$ are conditional expressions. In an
undirected/omnidirectional hypergraph, the conditions $XX$ and $YY$ are

$\dot{\mathbf{x}}=\textsf{A}\mathbf{x}^{k-1}+\mathbf{B}\mathbf{u}\Longrightarrow\text{
}\dot{\mathbf{x}}_{i}=\sum_{e\in\mathcal{E}|v_{i}\in e}\prod_{j|v_{j}\in
e,i\neq j}\mathbf{x}_{j},$ (9)

or when the control inputs are treated separately, the system is written

$\dot{\mathbf{x}}_{i}=\overbrace{\sum_{e\in\mathcal{E}|v_{i}\in
e}\prod_{j|v_{j}\in e,i\neq
j}\mathbf{x}_{j}}^{\textsf{A}\mathbf{x}^{k-1}}+\mathbf{B}_{i:}\mathbf{u}.$
(10)

Already, there is a notion of directionality where “information” or “forcing”
propagates from $\mathbf{x}_{j}$ to $\mathbf{x}_{i}.$

In a directed graph, we would say that $\mathbf{x}_{i}$ is in the edge head
and $\mathbf{x}_{j}$ is in the edge tail. The condition that $\mathbf{x}_{i}$
reside in the head, modifies which hyperedges are summed over or which
hyperedges influence $\mathbf{x}_{i}$ with the $XX$ conditional, and the
condition that $\mathbf{x}_{j}$ is in the tail modifies which vertices are
considered in the product via the $YY$ conditional. This can be extended to a
directed hypergraph as

$\dot{\mathbf{x}}=\textsf{A}\mathbf{x}^{k-1}+\mathbf{B}\mathbf{u}\Longleftrightarrow\dot{\mathbf{x}}_{i}=\overbrace{\sum_{e\in\mathcal{E}|v_{i}\in
e_{h}}\prod_{j|v_{j}\in
e_{t}}\mathbf{x}_{j}}^{\textsf{A}\mathbf{x}^{k-1}}+\mathbf{B}_{i:}\mathbf{u},$
(11)

where $e^{t}$ and $e^{h}$ denote hyperedge tails and heads respectively. From
eq. 11, we can explicitly define the hyperedge heads $e^{h}$ and tails $e^{t}$
to construct a directed hypergraph representation of
$(\textsf{A},\mathbf{B}).$

######  Definition 6.

Given a polysystem $(\textsf{A},\mathbf{B}),$ there the directed hypergraph
$\mathcal{H}(\textsf{A},\mathbf{B})=\\{\mathcal{V},\mathcal{E}\\}$ is defined:

  * •

$\mathcal{V}=\\{\overbrace{v_{1},\dots,v_{n}}^{\text{system
vertices}},\overbrace{v_{n+1},\dots,v_{n+m}}^{\text{control vertices}}\\}$

  * •

$\mathcal{E}=\\{(e^{t}_{1},e^{h}_{1}),\dots,(e^{t}_{l},e^{h}_{l})\\}$ where
each $e^{t}_{i}\subseteq\mathcal{V}$ and each $e^{h}_{i}\subset\mathcal{V}$

  * •

Each hypertail is unique (i.e. if $e^{t}_{i}=e^{t}_{j}$ then $i=j$)

  * •

Control vertices are not in the hyperedge heads (i.e.
$e^{h}\cap\\{v_{n+1},\dots,v_{n+m}\\}=\emptyset$)

Several modifications are made between directed and undirected/omnidirectional
hypergraphs:

  * •

Direction: each hyperedge can be explicitly split into hypertails and
hyperheads indicating how a walk, flow, or control input will propagate along
the hypergraph.

  * •

Nonuniformity: to apply Theorem 3, only the hypertails are fixed sizes. The
heads can vary in size and therefore so can the size of any hyperedge.

Rather than constructing a new adjacency tensor for
$\mathcal{H}(\textsf{A},\mathbf{B}),$ the set of all tensors with the sparsity
$\hat{\textsf{A}}$ will be the only objects required to verify if the system
is structurally controllable.

###  3.2 Hypergraph Structures

To extend Theorem 1, we define accessible vertices and dilations on
hypergraphs, which a few definitions; the following definitions will be
utilized in section 4.

In a graph, a set of vertices $S\subset\mathcal{V}$ is dilated if the in-
neighborhood of $S,$ denoted $\Gamma(S)$ is smaller than $S$ i.e. if
$|S|>\Gamma(S),$ then $S$ is dilated (Lin (1974)). For hypergraphs, we define
a dilation not by the size of the neighborhood of $S$ but by the number of
hyperedges directed into $S$.

######  Definition 7 (Hyperedge Dialation444I have not seen definitions of
hypergraph dilations in the literature yet.).

Given a directed hypergraph $\mathcal{H}=\\{\mathcal{V},\mathcal{E}\\}$ where
each directed hyperedge is denoted $(e^{t},e^{h})\in\mathcal{E}$, a set of
vertices $\\{v_{1},\dots,v_{s}\\}$ is dilated if the set of heads directed at
at least one vertex in $\\{v_{1},\dots,v_{s}\\}$ is smaller than $s$.

This definition is convenient because the existince of such a dilation can be
verified as a maximum matching problem in the star expansion of a directed
hypergraph; see section 5.

For a traditional graph or 2-uniform hypergraph, a walk is a sequence of edges
$e_{1},\dots,e_{l}$ where the edges are aligned $e_{i}^{h}=e_{i+1}^{t}.$ Graph
walks have two distinct properties:

  * •

Immediately before $e_{i}$ is added to the walk, the vertices in $e_{i}^{t}$
are visited.

  * •

All vertices in the tail $e^{t}_{i+1}$ are visited before $e_{i}$ is included
in the walk.

Typically, hypergraph walks focus on the first condition, requiring that
nearby vertices and hyperedges are visited sequentially. Several varieties of
hypergraph walks exist (Gallo et al. (1993); Ausiello and Laura (2017); Aksoy
et al. (2020)).

Following the second condition, we take an alternative perspective on
hypergraph walks: we impose the strict requirement that all vertices in the
tail $e^{t}_{i}$ are visited at some point in the walk prior to hyperedge
$e_{i}$ being visited. This relaxes the condition of visiting vertices in a
consecutive order.

######  Definition 8 (Walk 555There are many definitions of hypergraph walks
in the literature; however, I have not found a definition equivalent to this
one yet.).

A hypergraph walk beginning with the sets of visited vertices
$\\{\\{v_{1}\\},\dots,\\{v_{a}\\}\\}$ is a sequence of hyperedges
$w=(e_{1},\dots,e_{l})$ that obeys the following conditions:

  * •

A set of visited sets of vertices is maintained throughout the walk, beginning
with $V_{0}=\\{\\{v_{1}\\},\dots,\\{v_{a}\\}\\}$

  * •

Prior to $e_{i}$ appearing in the walk sequence, all vertices in the tail
$e_{i}^{t}$ are found in sets of visited vertices that contain no vertices
that are not in the tail of $e_{i}$, i.e. $\exists\ h_{1},\dots,h_{l}\in
V_{i-1}$ such that $h_{1}\cup\dots\cup h_{l}=e^{t}_{i}$ and $h_{j}\backslash
e^{t}_{i}=\emptyset\ \forall j,$ where $\backslash$ denotes the set
difference.

  * •

When a new hyperedge $e_{i}$ is added to the walk sequence $w$, vertices in
the head $e_{i}^{h}$ are counted as visited and added as a new set to the list
of sets of vertices that may be used to walk on new hyperedges i.e.
$V_{i}=V_{i-1}\cup e_{i}^{h}.$

For a walk $w$ of length $l,$ the vertices $e^{h}_{l}$ are the final vertices
of $w.$

This definition is convenient because it is simple and fast to perform a
breadth first search of a directed hypergraph using this type of walk.
Furthermore, it allows us to determine the set of hyperheads accessible from a
given set of visited vertices $V_{i}$ as the span of

$\hat{\textsf{A}}\times_{1}v_{1}\times_{2}\ldots\times_{k-1}v_{k-1}$

where $v_{i}\in V_{i}$. Notably, this expression bears a helpful resemblance
to eq. 4.

The notion of an accessible vertex for hypergraph walks parallels that of a
walk on a graph.

######  Definition 9 (Accessible Vertices).

Given a set of vertices $V_{0}=\\{\\{v_{1}\\},\dots,\\{v_{a}\\}\\},$ a vertex
$v$ is accessible if there exist a walk beginning at $V_{0}$ that visits $v.$

Unique to hypergraph walks, some vertices are accessible only in groups. For
instance, if $v_{1}$ and $v_{2}$ are each only in the head of one hyperedge
and $v_{1}$ and $v_{2}$ are in the same hyperedge, then all walks must visit
$v_{1}$ and $v_{2}$ together. We refer to a vertex $v$ as individually
accessible if there exist a set of walks that will isolate $v.$

######  Definition 10 (Individually Accessible Vertex).

A vertex $v$ is individually accessible if there exist a set of walks
$w_{1},\dots,w_{k}$ such that $\\{v\\}$ is the result of a series of set
unions and differences between the final vertices of walks
$w_{1},\dots,w_{k}$.

With these definitions, we are equipped to determine what sparsity structure
of $(\textsf{A},\mathbf{B})$ will render $\mathbf{C}(\textsf{A},\mathbf{B})$
full rank and to verify Theorem 2.

##  4 Structural Controllability for Polysystems

In this section we return to and prove our main result of Theorem 2. We show
that the presence of an inaccessible vertex or a hyperedge dilation is both
sufficient and necessary for the pair $(\textsf{A},\mathbf{B})$ to be
structurally uncontrollable. Our argument is based upon the rank of the
nonlinear controllability matrix $\mathbf{C}(\textsf{A},\mathbf{B})$ where a
pair $(\textsf{A},\mathbf{B})$ is structurally uncontrollable if there exist
no pair $(\hat{\textsf{A}},\hat{\mathbf{B}})$ with a full rank controllability
matrix.

###  4.1 Sufficient

Here we show that if $\mathcal{H}(\textsf{A},\mathbf{B})$ contain either a
inaccessible vertex or a hyperedge dilation then there exist no pair
$(\hat{\textsf{A}},\hat{\mathbf{B}})$ with a full rank controllability matrix.

######  Proposition 2.

In the hypergraph $\mathcal{H}(\textsf{A},\mathbf{B}),$ if there exist a
vertex in $\\{1,\dots,n\\}$ that is not accessible from a walk beginning at
$\\{\\{n+1\\},\dots,\\{n+m\\}\\},$ then the pair $(\textsf{A},\mathbf{B})$ is
not structurally controllable.

###### Proof.

If there exist a inaccessible vertex $v$, from the control vertices, then
there is no walk beginning at the control vertices which will ever visit $v.$
Denote by $\mathscr{W}_{1}$ the set of vertices that are accessible from the
control vertices such that $\mathscr{W}_{1}$ spans the column vectors of
$\mathbf{B}.$ The set of vertices accessible after the $i$th step in the walk
is the span of $\mathscr{W}_{i}$ where

$\mathscr{W}_{i}=\mathscr{W}_{i-1}\cup\\{\hat{\textsf{A}}\times_{2}\mathbf{e}_{i_{1}}\times\dots\times_{k}\mathbf{e}_{i_{k-1}}\text{
where }\mathbf{e}_{i}\in\mathscr{W}_{i-1}\\}.$ (12)

If $v$ is inaccessible, then there exist no $i$ such that $\mathscr{W}_{i}$
contains a vector whose $i$th entry is nonzero. In the context of the
controllability matrix, we observe that $\mathbf{C}(\textsf{A},\mathbf{B})$ is
the matrix whose columns are generated following a similar procedure as
$\mathscr{W}_{i}$ for $i\geq n,$ so if there exist a inaccessible vertex $v$
such that the $v$th entry of all vectors in $\mathscr{W}$ is always 0,
similarally, the $v$th row of $\mathbf{C}(\textsf{A},\mathbf{B})$ will be all
zeros and $rank(\mathbf{C}(\textsf{A},\mathbf{B}))<n.$ ∎

######  Proposition 3.

In the hypergraph $\mathcal{H}(\textsf{A},\mathbf{B})$, if there exist a
vertex $v_{i}$ that is not individually accessible, then the pair $\mathbf{C}$
is not structurally controllable.

###### Proof.

Suppose $v_{i}$ is accessible but not individually accessible, and let $v_{j}$
be the vertex that is always visited in conjunction with $v_{i}$ such that
$\\{v_{i},v_{j}\\}$ is accessible by neither $\\{v_{i}\\}$ nor $\\{v_{j}\\}$
are individually accessible. Then, it follows that the span of $\mathscr{W}$
contains vectors with nonzero entries that are linearly dependent in the $i$th
and $j$th position. Then, since $\mathbf{C}(\textsf{A},\mathbf{B})$ is
constructed such that its columns span a similar set of vectors at
$\mathscr{W},$ there exist a linear dependence between the $i$th and $j$th
rows of $\mathbf{C}(\textsf{A},\mathbf{B})$, so
$rank(\mathbf{C}(\textsf{A},\mathbf{B}))<n,$ and $(\textsf{A},\mathbf{B})$ is
not structurally controllable. ∎

######  Proposition 4.

There exist a pair of accessible vertices $\\{v_{1},v_{2}\\}$ where $v_{1}$
and $v_{2}$ are not individually accessible if and only if a hyperedge
dilation occurs.

###### Proof.

($\Longrightarrow$) Suppose $\\{v_{1},v_{2}\dots,v_{k}\\}$ are accessible from
walk $w_{1},$ and assume there is no dilation containing vertices $v_{1}$ and
$v_{2}.$ Then there must exist at least two hyperedges $e_{1}$ and $e_{2}$
that contain vertices $v_{1}$ and $v_{2}$ in the hyperedge heads. Since
$e_{1}$ and $e_{2}$ have distinct heads from one another with respect to
$v_{1}$ and $v_{2}$, their heads must contain two of the three:
$\\{v_{1}\\},\\{v_{2}\\},$ or $\\{v_{1},v_{2}\\}.$ However, if $\\{v_{1}\\}$
and $\\{v_{2}\\}$ are the heads than both $v_{1}$ and $v_{2}$ are immediately
individually accessible (a contradiction), and if $\\{v_{1},v_{2}\\}$ and
$\\{v_{1}\\}$ or $\\{v_{2}\\}$ are the heads, then $v_{1}$ and $v_{2}$ are
accessible through the set difference of these heads (another contradiction).
These contradictions violate our assumption, so the assumption that no
dilation occurs is false, and we may conclude that when vertices are
accessible but not individually accessible, a hyperedge dilation exist.

($\Longleftarrow$) If there exist a dilation, then there must exist
individually inaccessible vertices. ∎

######  Lemma 1.

In the hypergraph $\mathcal{H}(\textsf{A},\mathbf{B})$, the presence of either
a nonaccessable vertex or a hyperedge dilation are a sufficient condition for
the pair $(\textsf{A},\mathbf{B})$ to be structurally uncontrollable.

###### Proof.

This follows as an immediate consequence of the previous propositions. If
there is a inaccessible vertex, then Proposition 2 says
$(\textsf{A},\mathbf{B})$ is not structurally controllable. If there is a
dilation, then Proposition 4 says there exist individually inaccessible
vertices, which Proposition 3 says implies the system is not structurally
controllable. ∎

###  4.2 Necessary

The next step is to show that the presence of a hyperedge dilation or
inaccessible vertex is a necessary condition for $(\textsf{A},\mathbf{B})$ to
be structurally uncontrollable.

######  Proposition 5.

Suppose $(\textsf{A},\mathbf{B})$ is not structurally controllable. Then
$\mathcal{H}(\textsf{A},\mathbf{B})$ contains either a hyperedge dilation or
inaccessible vertex.

###### Proof.

If $(\textsf{A},\mathbf{B})$ is not structurally controllable, then
$rank(\mathbf{C}(\textsf{A},\mathbf{B}))<n$ for all entries in the set
$(\hat{\textsf{A}},\hat{\mathbf{B}}).$ This can occur either if
$rank(\begin{bmatrix}\hat{\textsf{A}}_{(k)}&\hat{\mathbf{B}}\end{bmatrix})<n$
or if
$rank(\begin{bmatrix}\hat{\textsf{A}}_{(k)}&\hat{\mathbf{B}}\end{bmatrix})=n,$
where
$\begin{bmatrix}\hat{\textsf{A}}_{(k)}&\hat{\mathbf{B}}\end{bmatrix}\in\mathbb{R}^{n\times
n(k-1)+m}.$ Beginning with the case
$rank(\begin{bmatrix}\hat{\textsf{A}}_{(k)}&\hat{\mathbf{B}}\end{bmatrix})<n,$
if this matrix is generally rank deficient, then there exist at least one row
containing all zeros – corresponding to an inaccessible vertex – or if there
are at least $n(k-2)+m+1$ columns containing all zeros – corresponding to a
dilation.

Consider the alternative case where
$rank(\begin{bmatrix}\hat{\textsf{A}}_{(k)}&\hat{\mathbf{B}}\end{bmatrix})=n.$
Then $dim(Im(\hat{\textsf{A}}_{(k)})\cup Im(\mathbf{B}))=n$ and
$rank(\mathbf{C}(\textsf{A},\mathbf{B}))<n.$ Since $rank(\mathbf{C})<n,$ it
follows that the dimension of $Im(\hat{\textsf{A}}_{(k)})$ shrinks when
restricted to the domain of the image of $\mathbf{B}.$ This indicates that
part of the image of $\hat{\textsf{A}}_{(k)}$ is inaccessible from the image
of $\mathbf{B},$ which is equivalent to their being a vertex that is not
individually accessible from walks originating at the vertices of
$\mathbf{B}.$ Since there is a vertex that is not individually accessible,
there must exist either a inaccessible vertex or a hyperedge dilation. ∎

We can now conclude that presence of inaccessible vertices or a hyperedge
dilations is both neccessary and sufficient for a pair
$(\textsf{A},\mathbf{B})$ to be structurally uncontrollable, and we have
proved Theorem 2.

##  5 A Test for Structural Controllability

This section presents 2 algorithms to verify the separate conditions of
Theorem 2, namely the existence of inaccessible nodes and hyperedge dilations.
Checking for dilations is equivalent to solving a maximum matching problem,
which can be accomplished in $\mathcal{O}(|\mathcal{V}|\sum_{i}|e_{i}^{h}|),$
and verifying the existence of inaccessible nodes can by performing a walk
beginning at the control vertices over all hyperedges, which occurs in
$\mathcal{O}(|\mathcal{E}|).$ The complexity to run both algorithms and verify
Theorem 2 is $\mathcal{O}(|\mathcal{V}|\sum_{i}|e_{i}^{h}|+|\mathcal{E}|).$

###  5.1 Maximum Matching to Detect Dilations

Maximum matching was utilized by Liu et al. (2011) to determine structural
controllability of graphs/linear systems. We can map the problem of detecting
hypergraph dilations to solving a maximum matching problem in a directed star
expansion.

######  Definition 11 (Directed Star Expansion).

The star expansion of $\mathcal{H}=\\{\mathcal{V},\mathcal{E}_{h}\\}$
constructs a directed bipartite graph
$\mathcal{S}=\\{\mathcal{V}_{s},\mathcal{E}_{s}\\}$ by introducing a new set
of vertices $\mathcal{V}_{s}=\mathcal{V}\cup\mathcal{E}_{h}$ where some
vertices represent hyperedges. There exists a directed edge between each
vertex $v,e\in\mathcal{V}_{s}$ when $v\in\mathcal{V}$, $e\in\mathcal{E}_{h},$
and $v\in e$. The edge is oriented $v\xrightarrow{}e$ when $v\in e^{t}$ and
oriented $e\xrightarrow{}v$ when $v\in e^{h}.$

We denote by $\mathcal{S}(\textsf{A},\mathbf{B})$ the star expansion of
$\mathcal{H}(\textsf{A},\mathbf{B}).$

######  Proposition 6.

A hypergraph dilation in $\mathcal{H}(\textsf{A},\mathbf{B})$ exist if and
only if there exist a dilation in $\mathcal{S}(\textsf{A},\mathbf{B})$ where
the star graph dilation is directed from hyperedge representing vertices of
$\mathcal{S}(\textsf{A},\mathbf{B})$ to vertices representing the nodes of
$\mathcal{H}(\textsf{A},\mathbf{B})$

From Proposition 6, we can use classic algorithms to detect the presence of a
dilation in $\mathcal{H}(\textsf{A},\mathbf{B})$ and verify the structural
controllability of $(\textsf{A},\mathbf{B}).$ In graphs, dilations can be
detected as a maximum matching problem, and Ford-Fulkerson is a fast, classic
algorithm to solve network flow problems that has been utilized to find
maximum matchings and detect dilations. We can apply Ford-Fulkerson to detect
dilations in our hypergraph.

Algorithm 2 Dilation Detector with Maximum Matching

0: $(\textsf{A},\mathbf{B})$

1: Construct
$\mathcal{H}(\textsf{A},\mathbf{B})=\\{\mathcal{V},\mathcal{E}\\}$

2: $\mathcal{S}=$star expansion of $\mathcal{H}(\textsf{A},\mathbf{B})$

3: Maximum Matching = Ford-Fulkerson($\mathcal{S}$)

4: Dilation = $(|$Maximum Matching$|=|\mathcal{V}|)$

5: return Dilation

The complexity of algorithm 2 is bounded by the complexity of Ford-Fulkerson,
which is $\mathcal{O}(nm)$ where $n$ is the number of vertices and $m$ is the
number of edges. In our specific case, algorithm 2 is
$\mathcal{O}(|\mathcal{V}|\sum_{i}|e_{i}^{h}|)$ where $|e_{i}^{h}|$ is the
size of the $i$th hyperhead.

###  5.2 BFS for Accessibility

Verification that all vertices are accessible can be performed in
$\mathcal{O}(|\mathcal{E}|)$ by performing a walk beginning at control
vertices that will step over each hyperedge in
$\mathcal{H}(\textsf{A},\mathbf{B}).$

Algorithm 3 Hypergraph BFS $\mathcal{O}(r|\mathcal{E}|)$

0: $(\textsf{A},\mathbf{B})$

Construct $\mathcal{H}(\textsf{A},\mathbf{B})=\\{\mathcal{V},\mathcal{E}\\}$

$A=\\{n+1,\dots,n+m\\}$

$Q=$set of hyperedges containing hypertails formed from $A$

$i=0$

while $Q$ is not empty and $i<|\mathcal{E}|$ do

$e=Q.pop()$

$A=A\cup e^{h}$

$N=$new accessible hyperedges from $A$

$Q.put(N)$

$i=i+1$

end while

return $A$

Algorithm 3 returns the set of all vertices visited of a walk beginning at the
control vertices. If $|A|=|\mathcal{V}|,$ then all vertices are accessible. It
requires at most $\mathcal{O}(|\mathcal{E}|)$ iterations of the loop beginning
on line 5 to verify this condition.

## References

  * Aksoy et al. (2020) Sinan G Aksoy, Cliff Joslyn, Carlos Ortiz Marrero, Brenda Praggastis, and Emilie Purvine.  Hypernetwork science via high-order hypergraph walks.  _EPJ Data Science_ , 9(1):16, 2020.
  * Ausiello and Laura (2017) Giorgio Ausiello and Luigi Laura.  Directed hypergraphs: Introduction and fundamental algorithms—a survey.  _Theoretical Computer Science_ , 658:293–306, 2017.
  * Chen et al. (2021) Can Chen, Amit Surana, Anthony Bloch, and Indika Rajapakse.  Controllability of hypergraphs.  _IEEE Transactions on Network Science and Engineering_ , 8(2):1646–1657, 2021.
  * Cooper and Dutle (2012) Joshua Cooper and Aaron Dutle.  Spectra of uniform hypergraphs.  _Linear Algebra and its Applications_ , 436(9):3268–3292, 2012.  ISSN 0024-3795.  doi: https://doi.org/10.1016/j.laa.2011.11.018.  URL http://www.sciencedirect.com/science/article/pii/S0024379511007610.
  * Cowan et al. (2012) Noah J Cowan, Erick J Chastain, Daril A Vilhena, James S Freudenberg, and Carl T Bergstrom.  Nodal dynamics, not degree distributions, determine the structural controllability of complex networks.  _PloS one_ , 7(6):e38398, 2012.
  * Gallo et al. (1993) Giorgio Gallo, Giustino Longo, Stefano Pallottino, and Sang Nguyen.  Directed hypergraphs and applications.  _Discrete applied mathematics_ , 42(2-3):177–201, 1993.
  * Gao et al. (2014) Jianxi Gao, Yang-Yu Liu, Raissa M D’souza, and Albert-László Barabási.  Target control of complex networks.  _Nature communications_ , 5(1):5415, 2014.
  * Jurdjevic and Kupka (1985) Velimir Jurdjevic and I7996670554 Kupka.  Polynomial control systems.  _Mathematische Annalen_ , 272(3):361–368, 1985.
  * Kolda and Bader (2009) T. Kolda and B. Bader.  Tensor decompositions and applications.  _SIAM Review_ , 51(3):455–500, 2009.  doi: 10.1137/07070111X.  URL https://doi.org/10.1137/07070111X.
  * Lee and Markus (1967) Ernest Bruce Lee and Lawrence Markus.  _Foundations of optimal control theory_ , volume 87.  Wiley New York, 1967.
  * Lin (1974) Ching-Tai Lin.  Structural controllability.  _IEEE Transactions on Automatic Control_ , 19(3):201–208, 1974.
  * Liu et al. (2011) Yang-Yu Liu, Jean-Jacques Slotine, and Albert-László Barabási.  Controllability of complex networks.  _nature_ , 473(7346):167–173, 2011.
  * Mayeda and Yamada (1979) Hirokazu Mayeda and Takashi Yamada.  Strong structural controllability.  _SIAM Journal on Control and Optimization_ , 17(1):123–138, 1979.
  * Mousavi et al. (2018) Shima Sadat Mousavi, Airlie Chapman, Mohammad Haeri, and Mehran Mesbahi.  Null space strong structural controllability via skew zero forcing sets.  In _2018 European Control Conference (ECC)_ , pages 1845–1850. IEEE, 2018.
  * Pickard et al. (2023a) Joshua Pickard, Can Chen, Cooper Stansbury, Amit Surana, Anthony Bloch, and Indika Rajapakse.  Kronecker products for tensors and hypergraphs: Structure and dynamics.  _arXiv preprint_ , 2023a.
  * Pickard et al. (2023b) Joshua Pickard, Amit Surana, Anthony Bloch, and Indika Rajapakse.  Observability of hypergraphs.  _arXiv preprint arXiv:2304.04883, Accepted for IEEE CDC_ , 2023b.
  * Ragnarsson and Van Loan (2012) Stefan Ragnarsson and Charles F Van Loan.  Block tensor unfoldings.  _SIAM Journal on Matrix Analysis and Applications_ , 33(1):149–169, 2012.
  * Shields and Pearson (1976) Robert Shields and J Pearson.  Structural controllability of multiinput linear systems.  _IEEE Transactions on Automatic control_ , 21(2):203–212, 1976.


RobertFlynn AntonRagni

# Self-Train Before You Transcribe

###### Abstract

When there is a mismatch between the training and test domains, current speech
recognition systems show significant performance degradation. Self-training
methods, such as noisy student teacher training, can help address this and
enable the adaptation of models under such domain shifts. However, self-
training typically requires a collection of unlabelled target domain data. For
settings where this is not practical, we investigate the benefit of performing
noisy student teacher training on recordings in the test set as a test-time
adaptation approach. Similarly to the dynamic evaluation approach in language
modelling, this enables the transfer of information across utterance
boundaries and functions as a method of domain adaptation. A range of in-
domain and out-of-domain datasets are used for experiments demonstrating large
relative gains of up to 32.2%. Interestingly, our method showed larger gains
than the typical self-training setup that utilises separate adaptation data.

###### keywords:

speech recognition, long-context, self-attention

##  1 Introduction

Speech recognition models are usually trained on a collection of speech and
text data, then remain fixed at inference/test time when they are used to
transcribe new speech. As a consequence, the model holds a fixed prior, formed
from the training data, on the distribution of words and speech for every new
utterance that is processed. This fixed prior becomes problematic as the
change in distribution between the training data and the inference data
becomes larger, resulting in reduced performance [1].

Prior work [2, 3, 4, 5] has shown that self-training methods, such as pseudo-
labelling, [6] can be used to adapt models under domain shifts. This typically
involves training an initial teacher model on a source domain, which is then
used to produce the target labels for a student model on the target domain.
While these methods do not require labelled data, they usually assume that a
collection of unlabelled data from the target domain is available. Recent work
on test time adaptation [7] (TTA) proposes to instead adapt the model solely
at test time, without the need for a separate adaptation set. This is
advantageous when the target domain is not known in advance, or unlabelled
data is either not available or cannot be shared due to privacy concerns.
Additionally, target domain data collection can be expensive, and may need to
be repeated over time due to domain drift.

Pseudo-labelling can also be used as a TTA method for automatic speech
recognition (ASR) [8]. For this, the pseudo-labelling-based adaptation is
performed solely on the current recording, prior to transcribing it. This
process also allows for the transfer of information across utterance
boundaries via gradient descent, relaxing the independence assumption that is
usually made when segmenting a recording into separate utterances. We draw
parallels to the dynamic evaluation approach [9, 10] that has proved effective
in language modelling, where training models on the previous history enables
them to better exploit recurring patterns, that occur outside the effective
context window. Extensions to pseudo-labelling such as noisy student teacher
(NST) training [11, 12, 3], where noise/augmentation is added to the inputs of
the student model to make prediction more challenging, have proven effective
for self-training approaches. Hence, in this work, we investigate the use of
NST at test time as a method of TTA. A breakdown of our main contributions is
given as follows:

  1. 1.

We propose ($\S$ 2) a method that substantially improves over prior work,
demonstrating that NST is more effective than standard pseudo-labelling for
TTA. We find ($\S$ 5.4) that the use of augmentation is particularly crucial
when the domain mismatch is large.

  2. 2.

We show ($\S$ 5.3) that our method leads to better performance, while using
$100\times$ less data, than a more standard self-training approach that uses
separate adaptation data.

  3. 3.

We show ($\S$ 5.5) that the method improves with longer recordings and that
the local context is most useful for the adaptation.

The model checkpoint and code to reproduce our results are made available
here111www.github.com/robflynnyh/Self-Train-Before-You-Transcribe.

##  2 Method

The following section presents our method of TTA, which we refer to as Noisy
Student Teacher at Inference (NSTI). This is depicted in figure 1, with
algorithm 1 covering the process that is used to transcribe recordings with
NSTI. For this work CTC [13] based acoustic models are used.

For NSTI 2 spectrograms $X$ and $X^{{}^{\prime}}$, where
$X^{{}^{\prime}}=\mathrm{Transformation}(X)$, are used as inputs to a teacher
model $M$ and a student model $M^{{}^{\prime}}$ which are identical and always
share the same parameters. The Transformation used to produce
$X^{{}^{\prime}}$ can be an augmentation strategy such as SpecAugment [14].
Output probabilities $P=M(X)$ and
$P^{{}^{\prime}}=M^{{}^{\prime}}(X^{{}^{\prime}})$ are obtained from the
models. The models are then updated based on the loss between
$P^{{}^{\prime}}$ and a decoded label sequence $Y^{*}$ that is produced from
decoding $P$. Practically, as the student and teacher models are identical,
this method only requires one forward and backwards pass per step through a
single model.

Figure 1:  Depiction of the NSTI method Algorithm 1 Noisy Student Teacher at
Inference (NSTI)

1:Recording $R$, model $M$, number of epochs $n$

2:Segment $R$ into $S_{1},S_{2},\dots,S_{m}$

3:Shuffle the segments $S_{1},S_{2},\dots,S_{m}$

4:for $i=1$ to $n$ do

5: for each segment $S_{j}$ do

6: $X=S_{j}$

7: Apply Transfomation: $X^{{}^{\prime}}=\mathrm{Transformation}(X)$

8: Compute probabilities: $P=M(X)$,
$P^{{}^{\prime}}=M^{{}^{\prime}}(X^{{}^{\prime}})$

9: Decode $P$ to obtain target labels: $Y^{*}=\mathrm{Decode}(P)$

10: Obtain gradients using the loss between $P^{{}^{\prime}}$ and $Y^{*}$

11: Update $M$ and $M^{{}^{\prime}}$ using the gradients

12: end for

13:end for

14:Obtain predictions for recording $R$ using the updated model $M$

For transcribing recordings using our method, the following process is used:
first, the recording is segmented. Self-training is then performed on each
segment in the recording in a random order, and repeated for $n$ epochs. A
final pass is then performed over the recording to obtain the model's
predictions. Note that the method is performed over individual recordings and
not the Dev/Test set as a whole.

###  2.1 Transformations

For the transformation function, the frequency masking component of
SpecAugment [14] is used for our primary experiments. The use of time masking
was not found to be beneficial. In $\S$ 5.4 we also experiment with a range of
other transformations, which are as follows: Identity transform, where no
change is applied; Random noise, where Gaussian noise is added to the
spectrogram; CutOut [15], where $n$ rectangles are masked out from the
spectrogram.

##  3 Prior Work

Self-training methods can be used for the purpose of adaptation [2, 3, 4, 5],
these methods typically use a separate training set to adapt a model to a
target domain. In contrast, TTA methods use only the data available at
test/inference time, such as the current recording or utterance. Entropy
minimisation (EM), originally presented as a semi-supervised learning approach
[16], has proven effective as a method of TTA for computer vision [7] and ASR
[17]. The Single-Utterance Test-time Adaptation (SUTA) [17] is an example of a
TTA approach for ASR that uses an EM-based technique. This method adapts
models on a single utterance and then discards the adapted model for the
following utterance. While SUTA is appropriate in an $i.i.d$ scenario,
recordings containing multiple utterances with highly correlated features are
present at test time in most scenarios. Therefore, to improve performance our
work leverages the entire recording, rather than a single utterance.

To benefit from updates from preceding utterances, AWMC [8], adopts a psuedo-
labelling approach towards TTA. This method focuses on an online scenario
where utterances are trained on and transcribed in their natural order. Due to
problems with model collapse, AWMC uses 2 models to serve as the teacher
model, with weights that are an exponential moving average (EMA) of the
students. While [8] investigates TTA for an online setting where only prior
utterances are available, our work focuses on an offline approach that also
uses future utterances for improved performance. Additionally, the use of
augmentation is not explored in [8]. In our work, we find that the use of an
EMA teacher is not needed to prevent model collapse. This may be due to a more
stable base model and the use of augmentation. Attempts to include an EMA
teacher also resulted in reduced performance due to the teacher adapting at a
slower rate, however in scenarios where model collapse does occur this would
be beneficial.

Other work in natural language processing, also investigates a form of TTA
[18] where pseudo-labelling is used at test-time to adapt the model via
gradient descent. In this work, low-quality pseudo-labels are filtered based
on confidence, and the model is trained to predict the pseudo-labels while
maintaining similarity to the pre-trained weights. Other work, in language
modelling presents a technique referred to as dynamic evaluation [9, 10],
where gradient descent is used to update the model based on the prior text
history. This enables the model to exploit recurring patterns in the sequence,
which occur outside the effective context window. However, it generally relies
on the availability of a ground truth text history.

##  4 Experimental Setup

###  4.1 Datasets

For training the initial pre-adapted baseline model, the collection of Spotify
podcasts totalling 58K hours provided in [19] is used. For the experiments in
this work, a range of in-domain and out-of-domain datasets are included in
order to properly evaluate our method, which are as follows: Earnings-22 [20],
which consists of earnings report meetings with a diverse range of accents.
The train/dev/test splits from [21] are used in this work. Each meeting lasts
up to 2 hours in length, with 5.5/5.6 in the dev and test sets respectively.
Rev16, which is a collection of 30 podcast episodes, we use the 16 episodes
reported on in [22]. Rev16 can be viewed as our in-domain test set due to its
similarity to our training data. Tedlium [23], which is a collection of 10-20
minute TED talks, typically involving a single speaker. Chime6 [24], which is
used as a highly out-of-domain test set, we use only the first distant
microphone array from this data, resulting in large amounts of background
noise. Channels of the first array are combined by averaging the spectrograms
prior to normalisation.

###  4.2 Model Configuration

The model uses a Conformer [25] based architecture, with the Fast Conformer
subsampling configuration [26]. For our method, we find it essential to
replace batch normalisation [27] with batch renormalization [28] in the
conformer convolution modules, and do not update the batch statistics during
the self-training process. A similar approach is taken in [5], where group
normalisation is used, however, we find this to be unstable during the initial
training stage. The model consists of 6 layers with roughly 90 million
parameters. Training and adaptation is performed with a context window/segment
length of 162 seconds.

###  4.3 Hyperparameters

All hyperparameters (i.e. augmentation, epochs, learning rate) are tuned using
a random search on the development set of Tedlium for our primary
experiements. Dataset-specific tuning is also explored in $\S$ 5.2. All
experiments use a batch size of 2, composed of $2$ copies of a single
segment/utterance. Madgrad [29] is used as the optimizer. For our primary
results that use SpecAugment the following hyperparameters are used: $6$
frequency masks with a maximum size of $34$, $5$ epochs and a learning rate of
$9e-5$.

For segmenting recordings the sliding window scheme described in [30] is used.
Specifically, the recording is chunked into segments/windows equal to the
model's context window using a moving window with a stride of $12.5\%$ of the
segment length. When transcribing the recording, probabilities from segments
that overlap are averaged to obtain the final prediction. However, this
process is not essential to the method, and standard utterance boundaries can
also be used.

##  5 Experimental Results

All evaluations reported in the tables are repeated 3 times, with mean
statistics reported. We find the variation between repeats to be low, with a
standard deviation of around $0.01-0.1$. The following subsections will break
down and discuss our findings.

###  5.1 How effective is the method?

Table 1: WERs (Dev/Test) when using various training settings. *Method from prior work [8]. Setting | Aug | TED | E-22 | Chime6 | Rev16
---|---|---|---|---|---
Shuffled | ✓ | 6.6/5.8 | 18.9/14.9 | 56.6/59.4 | 14.2
Ordered | ✓ |  6.6/5.9 | 19.5/15.4 | 57.3/61.8 | 14.2
Online | ✓ | 6.9/6.1 | 21.7/16.7 | 59.7/64.7 | 14.2
AWMC* | ✗ | 7.0/6.2 | 23.4/18.1 |  88.9/85.3 | 15.2
AWMC | ✓ | 6.8/6.0 | 20.7/15.7 | 70.7/75.9 | 14.2
Unadapted model | N/A | 7.1/6.2 | 23.9/18.3 | 83.5/86.5 | 14.5
Table 2: Real time factor of each setting Setting | Aug | 1 Epoch | Total
---|---|---|---
Shuffled | ✓ | 0.027 | 0.115
Ordered | ✓ | 0.027 | 0.115
Online | ✓ | 0.023 | 0.023
AWMC | ✗ | 0.026 | 0.026
AWMC | ✓ | 0.026 | 0.097
Unadapted model | N/A | N/A | 0.004

Table 1 presents the results for our method using various settings. Settings
with augmentation (Aug), use the frequency masking component of SpecAugment
[14] The real-time factors (RTF) for each setting are provided in table 2.
Bold text denotes the best results, red text denotes that the model performs
worse after test-time adaptation.

The primary method described in algorithm 1 is referred to as the Shuffled
setting. The results for this setting demonstrate substantial gains over the
unadapted model with word error reductions (WERRs) of 6.5%, 18.6%, 31.3% and
2.0% for Tedlium, Earnings-22 (E-22), Chime6 and Rev16 respectively. Note that
our un-adapted baseline already shows competitive performance [23, 21, 1, 22]
due to the large and diverse training dataset. Whereas prior TTA work in ASR
[8, 17] uses a baseline trained on Librispeech [31], which consequently shows
unrealistic gains from adaptation due to the narrow training domain.

In general, the datasets that are the most different from the training domain
see the largest gains. Recordings in Tedlium are also shorter which results in
less data for adaptation and therefore lower gains (see $\S$ 5.5). Results for
Chime6 show that the method remains effective and stable even when the domain
mismatch is very large and transcription quality is extremely poor. Rev16, our
in-domain test set shows the smallest gains. We hypothesise that this is due
to the similarity of this data to our large training dataset.

Figure 2: Error rates after each epoch of NSTI on Earnings-22

Word error rate (WERs), substitution, insertions and deletion statistics after
each epoch of NSTI on Earnings-22 (test) are provided in figure 2. We find
that the majority of the benefit from the method is attained after the first
epoch, with a WERR of 14.8%. Therefore, adaptation can be stopped here if RTF
is an issue. The method benefits from a reduction in the number of
substitutions and deletions. Insertions see a small increase of 4.4% by epoch
5, with deletions showing the largest reduction of 30.3%. On the Chime6
dataset, the model is initially unconfident, with a very high deletion rate of
83.8%, therefore the method is very beneficial for this data, with the
deletion rate reducing to 37.2% after NSTI.

While shuffling the data during NSTI is helpful, results from the Ordered
setting demonstrate that it is not necessary for good performance. We also
present an online setting where utterances are processed in their natural
order, and the final predictions are taken from the teacher model at each
time-step. This shows worse performance as it can not leverage future
utterances, and only runs for one epoch. The AWMC method [8] shows a small
WERR of 2.1%/1.1% on Earning-22, with the model degrading on Chime6 and Rev16.
This is primarily due to not incorporating augmentation, as including
augmentation causes the results to improve. As AWMC is an online method the
use of this approach with augmentation may be preferable to the online
variation of NSTI. However, the WER is higher than other settings on Chime6,
which may be due to the EMA teacher model updating at a slower rate.

###  5.2 Dependency on hyperparameters

The hyperparameters used in the results are tuned on the Tedlium development
split. We also experiment with dataset-specific tuning. On Earnings-22 there
was no change in results when tuning was performed on the datasets Dev set.
For Chime6 there was a small further WERR of 2.3%/4.0%. This demonstrates that
the method is not overly sensitive to hyperparameter choice, and does not
require repeated re-tuning when the test domain changes. Which is important
for scenarios where NSTI is likely to be useful.

Figure 3: Comparison between NST and NSTI on Earnings-22

###  5.3 Comparison to self-training on a separate training set

We provide comparisons to an NST self-training approach that uses the 105-hour
Earnings-22 training set to adapt the model in figure 3. For the NST training
we use the method described in [3]. Results show that our method (NSTI)
improves over NST by 4% when selecting the best checkpoint on the validation
data. During NSTI only the current recording with a duration of around 1 hour
is used, hence our method required $100\times$ less data. Performing NSTI
after adapting the model on the training set did not result in any further
gains. We believe this is due to the sharpening of the model's class
distribution after NST training.

Self-training on separate adaptation data may still be preferred in scenarios
where the RTF is an issue and the target domain is known and constant. This is
because NSTI needs to be performed on every recording. For example, adapting
on a recording from Earnings-22 and then evaluating on other recordings from
the same test set led to a WERR of -3.9% after the first epoch, and -17.4%
after the fifth.

###  5.4 Comparison of transformation functions

Table 3: WERs when using various transformation functions. Transform | TED | E-22 | Chime6 | Rev16
---|---|---|---|---
SpecAugment |  6.6/5.8 |  18.9/14.9 | 56.6/59.4 | 14.2
Identity | 7.0/6.1 | 22.6/17.4 | 100.0/100.0 | 15.0
Noise | 6.6/5.9 | 24.2/19.2 | 99.6/97.3 | 18.5
CutOut |  6.4/5.8 |  18.9/14.5 |  54.9/56.9 | 37.9
Unadapted model | 7.1/6.2 | 23.9/18.3 | 83.5/86.5 | 14.5

A comparison of the different transformation functions described in $\S$ 2.1
is provided in table 3. The identity transform (no transformation) shows the
worst performance, with small improvements on Tedlium/Earnings-22 and worse
performance than the unadapted model on Chime6/Rev16. This explains the poor
performance of AWMC [8], which uses this transformation. We find that the use
of augmentation is especially crucial for datasets, such as Chime6, where the
deletion rate is high, otherwise, the model learns to only output blank
tokens.

Using random noise as the transformation function resulted in degradation on
all datasets other than Tedlium. Cutout [15] showed the best performance on
all datasets other than Rev16, where the model performed much worse than the
unadapted model. The degradation seen on various datasets for the Identity,
Noise, and Cutout transforms is because these methods were more sensitive to
hyperparameter choices (which were tuned on Tedlium). Overall, the frequency
masking component of SpecAugment showed the most consistent performance and
outperformed the unadapted model by a large margin on all datasets.

###  5.5 Impact of recording duration

Figure 4: WER as the recording duration for NSTI is increased

Figure 4 presents results analysing the effect of recording duration on WERR.
For this experiment, all recordings from Earnings-22 Dev/Test that are 1 hour
or greater in duration are used. Each recording is partitioned into segments
of 2.7, 5.5, 10.9, 21.8 and 43.7 minutes using the moving window scheme
discussed in $\S$ 4.3. NSTI is then performed separately on each of these
partitions. Results when using the entire recording, which range from 61-76
minutes ($\mu=66.2$), are also provided.

When the recording duration is equal to the context window of the model (2.7
minutes) we see very small gains of less than 1%. As the model is already
attending over this data it is likely that some form of adaptation is already
being performed. As expected the local context beyond the model's context
window is more valuable, for example performing two epochs with a recording
duration of 10.9 minutes is more beneficial than 1 epoch at 21.8 minutes. This
helps explain the discrepancy in performance we see in $\S$ 5.3 between NSTI
and NST. Self-training on separate adaptation data requires much more data
because this data is much less representative of any recording at test time.

##  6 Conclusion

ASR models often degrade considerably in performance when the domain mismatch
between training and testing/inference is large. In this work, to help address
these challenges, we propose a self-training approach, which applies the noisy
student teacher training framework on recordings at test time before
transcribing them. Our proposed method improves considerably over prior test
time adapatation methods for ASR. Additionally, the results demonstrate that
this work leads to better performance than a more typical approach which uses
a separate 105 hour training set for adaptation. We find that this is due to
the high corellation between a current utterance and surrounding utterances in
a recording. While, the method is very effective, it does not take into
account the sequential nature of utterances in a recording, we plan to
investigate this, alongside other augmentation strategies in our future work.

##  7 Acknowledgements

This work was supported by the CDT in Speech and Language Technologies (SLT)
and their Applications funded by UKRI [grant number EP/S023062/1].

## References

  * [1] T. Likhomanenko, Q. Xu, V. Pratap, P. Tomasello, J. Kahn, G. Avidov, R. Collobert, and G. Synnaeve, ``Rethinking evaluation in asr: Are our models robust enough?'' _arXiv preprint arXiv:2010.11745_ , 2020.
  * [2] S. Khurana, N. Moritz, T. Hori, and J. Le Roux, ``Unsupervised domain adaptation for speech recognition via uncertainty driven self-training,'' in _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2021, pp. 6553–6557.
  * [3] Y. Higuchi, N. Moritz, J. L. Roux, and T. Hori, ``Momentum pseudo-labeling for semi-supervised speech recognition,'' _arXiv preprint arXiv:2106.08922_ , 2021.
  * [4] Z. Meng, J. Li, Y. Gaur, and Y. Gong, ``Domain adaptation via teacher-student learning for end-to-end speech recognition,'' in _2019 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU)_. IEEE, 2019, pp. 268–275.
  * [5] Y. Higuchi, N. Moritz, J. Le Roux, and T. Hori, ``Advancing momentum pseudo-labeling with conformer and initialization strategy,'' in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 7672–7676.
  * [6] D.-H. Lee _et al._ , ``Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks,'' in _Workshop on challenges in representation learning, ICML_ , vol. 3, no. 2. Atlanta, 2013, p. 896.
  * [7] D. Wang, E. Shelhamer, S. Liu, B. Olshausen, and T. Darrell, ``Tent: Fully test-time adaptation by entropy minimization,'' _arXiv preprint arXiv:2006.10726_ , 2020.
  * [8] J.-H. Lee, D.-H. Kim, and J.-H. Chang, ``Awmc: Online test-time adaptation without mode collapse for continual adaptation,'' in _2023 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU)_. IEEE, 2023, pp. 1–8.
  * [9] T. Mikolov, M. Karafiát, L. Burget, J. Cernockỳ, and S. Khudanpur, ``Recurrent neural network based language model.'' in _Interspeech_ , vol. 2, no. 3. Makuhari, 2010, pp. 1045–1048.
  * [10] B. Krause, E. Kahembwe, I. Murray, and S. Renals, ``Dynamic evaluation of neural sequence models,'' in _International Conference on Machine Learning_. PMLR, 2018, pp. 2766–2775.
  * [11] Q. Xie, M.-T. Luong, E. Hovy, and Q. V. Le, ``Self-training with noisy student improves imagenet classification,'' in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2020, pp. 10 687–10 698.
  * [12] D. S. Park, Y. Zhang, Y. Jia, W. Han, C.-C. Chiu, B. Li, Y. Wu, and Q. V. Le, ``Improved noisy student training for automatic speech recognition,'' _arXiv preprint arXiv:2005.09629_ , 2020.
  * [13] 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.
  * [14] D. S. Park, W. Chan, Y. Zhang, C.-C. Chiu, B. Zoph, E. D. Cubuk, and Q. V. Le, ``Specaugment: A simple data augmentation method for automatic speech recognition,'' _arXiv preprint arXiv:1904.08779_ , 2019.
  * [15] T. DeVries and G. W. Taylor, ``Improved regularization of convolutional neural networks with cutout,'' _arXiv preprint arXiv:1708.04552_ , 2017.
  * [16] Y. Grandvalet and Y. Bengio, ``Semi-supervised learning by entropy minimization,'' _Advances in neural information processing systems_ , vol. 17, 2004.
  * [17] G.-T. Lin, S.-W. Li, and H.-y. Lee, ``Listen, adapt, better wer: Source-free single-utterance test-time adaptation for automatic speech recognition,'' _arXiv preprint arXiv:2203.14222_ , 2022.
  * [18] A. Kedia and S. C. Chinthakindi, ``Keep learning: Self-supervised meta-learning for learning from inference,'' in _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , 2021, pp. 63–77.
  * [19] A. Clifton, A. Pappu, S. Reddy, Y. Yu, J. Karlgren, B. Carterette, and R. Jones, ``The spotify podcast dataset,'' _arXiv preprint arXiv:2004.04270_ , 2020.
  * [20] M. Del Rio, P. Ha, Q. McNamara, C. Miller, and S. Chandra, ``Earnings-22: A practical benchmark for accents in the wild,'' _arXiv preprint arXiv:2203.15591_ , 2022.
  * [21] S. Gandhi, P. Von Platen, and A. M. Rush, ``Esb: A benchmark for multi-domain end-to-end speech recognition,'' _arXiv preprint arXiv:2210.13352_ , 2022.
  * [22] A. Radford, J. W. Kim, T. Xu, G. Brockman, C. McLeavey, and I. Sutskever, ``Robust speech recognition via large-scale weak supervision,'' in _International Conference on Machine Learning_. PMLR, 2023, pp. 28 492–28 518.
  * [23] F. Hernandez, V. Nguyen, S. Ghannay, N. Tomashenko, and Y. Esteve, ``Ted-lium 3: Twice as much data and corpus repartition for experiments on speaker adaptation,'' in _Speech and Computer: 20th International Conference, SPECOM 2018, Leipzig, Germany, September 18–22, 2018, Proceedings 20_. Springer, 2018, pp. 198–208.
  * [24] S. Watanabe, M. Mandel, J. Barker, E. Vincent, A. Arora, X. Chang, S. Khudanpur, V. Manohar, D. Povey, D. Raj _et al._ , ``Chime-6 challenge: Tackling multispeaker speech recognition for unsegmented recordings,'' _arXiv preprint arXiv:2004.09249_ , 2020.
  * [25] 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,'' _arXiv preprint arXiv:2005.08100_ , 2020.
  * [26] D. Rekesh, S. Kriman, S. Majumdar, V. Noroozi, H. Juang, O. Hrinchuk, A. Kumar, and B. Ginsburg, ``Fast conformer with linearly scalable attention for efficient speech recognition,'' _arXiv preprint arXiv:2305.05084_ , 2023.
  * [27] S. Ioffe and C. Szegedy, ``Batch normalization: Accelerating deep network training by reducing internal covariate shift,'' in _International conference on machine learning_. pmlr, 2015, pp. 448–456.
  * [28] S. Ioffe, ``Batch renormalization: Towards reducing minibatch dependence in batch-normalized models,'' _Advances in neural information processing systems_ , vol. 30, 2017.
  * [29] A. Defazio and S. Jelassi, ``Adaptivity without compromise: a momentumized, adaptive, dual averaged gradient method for stochastic optimization,'' _J Mach Learn Res_ , vol. 23, pp. 1–34, 2022.
  * [30] R. Flynn and A. Ragni, ``How much context does my attention-based asr system need?'' _arXiv preprint arXiv:2310.15672_ , 2023.
  * [31] V. Panayotov, G. Chen, D. Povey, and S. Khudanpur, ``Librispeech: an asr corpus based on public domain audio books,'' in _2015 IEEE international conference on acoustics, speech and signal processing (ICASSP)_. IEEE, 2015, pp. 5206–5210.