# iRNN: Integer-only Recurrent Neural Network

Eyyüb Sari, Vanessa Courville, Vahid Partovi Nia
Huawei Noah’s Ark Lab, Montreal Research Centre, 7101 Park Avenue, H3N1X9
Quebec, Canada
<EMAIL_ADDRESS>
Corresponding author

###### Abstract

Recurrent neural networks (RNN) are used in many real-world text and speech
applications. They include complex modules such as recurrence, exponential-
based activation, gate interaction, unfoldable normalization, bi-directional
dependence, and attention. The interaction between these elements prevents
running them on integer-only operations without a significant performance
drop. Deploying RNNs that include layer normalization and attention on
integer-only arithmetic is still an open problem. We present a quantization-
aware training method for obtaining a highly accurate integer-only recurrent
neural network (iRNN). Our approach supports layer normalization, attention,
and an adaptive piecewise linear approximation of activations (PWL), to serve
a wide range of RNNs on various applications. The proposed method is proven to
work on RNN-based language models and challenging automatic speech
recognition, enabling AI applications on the edge. Our iRNN maintains similar
performance as its full-precision counterpart, their deployment on smartphones
improves the runtime performance by $2\times$, and reduces the model size by
$4\times$.

##  1 Introduction

RNN (Rumelhart, Hinton, and Williams, 1986) architectures such as LSTM
Hochreiter and Schmidhuber (1997) or GRU Cho et al. (2014) are the backbones
of many downstream applications. RNNs now are part of large-scale systems such
as neural machine translation Chen et al. (2018); Wang, Wu, and Liu (2019) and
on-device systems such as Automatic Speech Recognition (ASR) He et al. (2019).
RNNs are still highly used architectures in academia and industry, and their
efficient inference requires more elaborated studies.

In many edge devices, the number of computing cores is limited to a handful of
computing units, in which parallel-friendly transformer-based models lose
their advantage. There have been several studies in quantizing transformers to
adapt them for edge devices but RNNs are largely ignored. Deploying RNN-based
chatbot, conversational agent, and ASR on edge devices with limited memory and
energy requires further computational improvements. The 8-bit integer neural
networks quantization (Jacob et al., 2017) for convolutional architectures
(CNNs) is shown to be an almost free lunch to tackle the memory, energy, and
latency costs, with a negligible accuracy drop (Krishnamoorthi, 2018).

Figure 1: Example of an integer-only LSTM cell (iLSTM). Layer normalization
change to quantized integer friendly MadNorm (QMadNorm), full-precision matrix
multiplications change to integer matrix multiplication (QMatmul), sigmoid and
tanh activations are replaced with their corresponding piecewise linear (PWL)
approximations.

Intuitively, quantizing RNNs is more challenging because the errors introduced
by quantization will propagate in two directions, i) to the next layers, like
feedforward networks ii) across timesteps. Furthermore, RNN cells are
computationally more complex; they include several element-wise additions and
multiplications. They also have different activation functions that rely on
the exponential function, such as sigmoid and hyperbolic tangent (tanh).

Accurate fully-integer RNNs calls for a new cell that is built using integer
friendly operations. Our main motivation is to enable integer-only inference
of RNNs on specialized edge AI computing hardware with no floating-point
units, so we constrained the new LSTM cell to include only integer operations.

First we build a fully integer LSTM cell in which its inference require
integer-only computation units, see Figure 1. Our method can be applied to any
RNN architecture, but here we focus on LSTM networks which are the most
commonly used RNNs.

Our contributions can be summarized as

  * •

providing a quantization-aware piecewise linear approximation algorithm to
replace exponential-based activation functions (e.g. sigmoid and tanh) with
integer-friendly activation,

  * •

introducing an integer-friendly normalization layer based on mean absolute
deviation,

  * •

proposing integer-only attention,

  * •

wrapping up these new modules into an LSTM cell towards an integer-only LSTM
cell.

We also implement our method on an anonymous smartphone, effectively showing
$2\times$ speedup and $4\times$ memory compression. It is the proof that our
method enables more RNN-based applications (e.g. ASR) on edge devices.

##  2 Related Work

With ever-expanding deep models, designing efficient neural networks enable
wider adoption of deep learning in industry. Researchers recently started
working on developing various quantization methods (Jacob et al., 2017; Hubara
et al., 2018; Darabi et al., 2018; Esser et al., 2020). Ott et al. (2016)
explores low-bit quantization of weights for RNNs. They show binarizing
weights lead to a massive accuracy drop, but ternarizing them keeps the model
performance. Hubara et al. (2018) demonstrate quantizing RNNs to extremely low
bits is challenging; they quantize weights and matrix product to 4-bit, but
other operations such as element-wise pairwise and activations are computed in
full-precision. Hou et al. (2019) quantize LSTM weights to 1-bit and 2-bit and
show empirically that low-bit quantized LSTMs suffer from exploding gradients.
Gradient explosion can be alleviated using normalization layers and leads to
successful training of low bit weights Ardakani et al. (2018). Sari and
Partovi Nia (2020) studied the effect of normalization in low bit networks
theoretically, and proved that low-bit training without normalization
operation is mathematically impossible; their work demonstrates the
fundamental importance of involving normalization layers in quantized
networks. He et al. (2016) introduce Bit-RNN and improve 1-bit and 2-bit RNNs
quantization by constraining values within fixed range carefully; they keep
activation computation and element-wise pairwise operations in full-precision.
Kapur, Mishra, and Marr (2017) build upon Bit-RNN and propose a low-bit RNN
with minimal performance drop, but they increase the number of neurons to
compensate for performance drop; they run activation and pair-wise operations
on full-precision as well.

Wu et al. (2016) is a pioneering work in LSTM quantization, which demonstrated
speed-up inference of large-scale LSTM models with limited performance drop by
partially quantizing RNN cells. Their proposed method is tailored towards
specific hardware. They use 8-bit integer for matrix multiplications and
16-bit integer for tanh, sigmoid, and element-wise operations but do no
quantize attention Bluche, Primet, and Gisselbrecht (2020) propose an
effective 8-bit integer-only LSTM cell for Keyword Spotting application on
microcontrollers. They enforce weights and activations to be symmetric on
fixed ranges $[-4,4]$ and $[-1,1]$. This prior assumption about the network’s
behaviour restrict generalizing their approach for wide range of RNN models.
They propose a look-up table of 256 slots to represent the quantized tanh and
sigmoid activations. However, the look-up table memory requirement explodes
for bigger bitwidth. Their solution does not serve complex tasks such as
automatic speech recognition due to large look up table memory consumption.
While demonstrating strong results on Keyword Spotting task, their assumptions
on quantization range and bitwidth make their method task-specific.

##  3 Background

We use the common linear algebra notation and use plain symbols to denote
scalar values, e.g. $x\in\mathbb{R}$, bold lower-case letters to denote
vectors, e.g. $\textbf{x}\in\mathbb{R}^{n}$, and bold upper-case letters to
denote matrices, e.g. $\textbf{X}\in\mathbb{R}^{m\times n}$. The element-wise
multiplication is represented by $\odot$.

###  3.1 LSTM

We define an LSTM cell as

$\displaystyle\begin{pmatrix}\mathbf{i}_{t}\\\ \mathbf{f}_{t}\\\
\mathbf{j}_{t}\\\ \mathbf{o}_{t}\end{pmatrix}$
$\displaystyle=\mathbf{W}_{x}\mathbf{x}_{t}+\mathbf{W}_{h}\mathbf{h}_{t-1},$
(1) $\displaystyle\mathbf{c}_{t}$
$\displaystyle=\sigma(\mathbf{f}_{t})\odot\mathbf{c}_{t-1}+\sigma(\mathbf{i}_{t})\odot\text{tanh}(\mathbf{j}_{t}),$
(2) $\displaystyle\mathbf{h}_{t}$
$\displaystyle=\sigma(\mathbf{o}_{t})\odot\text{tanh}(\mathbf{c}_{t}),$ (3)

where $\sigma(\cdot)$ is the sigmoid function; $n$ is the input hidden units
dimension, and $m$ is the state hidden units dimension;
$\mathbf{x}_{t}\in\mathbb{R}^{n}$ is the input for the current timestep
$t\in\\{1,...,T\\}$; $\mathbf{h}_{t-1}\in\mathbb{R}^{m}$ is the hidden state
from the previous timestep and $\mathbf{h}_{0}$ is initialized with zeros;
$\mathbf{W}_{x}\in\mathbb{R}^{4m\times n}$ is the input to state weight
matrix; $\mathbf{W}_{h}\in\mathbb{R}^{4m\times m}$ is the state to state
weight matrix;
$\\{\mathbf{i}_{t},\mathbf{f}_{t},\mathbf{o}_{t}\\}\in\mathbb{R}^{m}$ are the
pre-activations to the {input, forget, output} gates;
$\mathbf{j}_{t}\in\mathbb{R}^{m}$ is the pre-activation to the cell candidate;
$\\{\mathbf{c}_{t},\mathbf{h}_{t}\\}\in\mathbb{R}^{m}$ are the cell state and
the hidden state for the current timestep, respectively. We omit the biases
for the sake of notation simplicity. For a bidirectional LSTM (BiLSTM) the
output hidden state at timestep $t$ is the concatenation of the forward hidden
state $\overrightarrow{\mathbf{h}}_{t}$ and the backward hidden state
$\overleftarrow{\mathbf{h}}_{t}$,
$[\overrightarrow{\mathbf{h}}_{t};\overleftarrow{\mathbf{h}}_{t}]$.

###  3.2 LayerNorm

Layer normalization Ba, Kiros, and Hinton (2016) standardizes inputs across
the hidden units dimension with zero location and unit scale. Given hidden
units $\mathbf{x}\in\mathbb{R}^{H}$, LayerNorm is defined as

$\displaystyle\mu$ $\displaystyle=\frac{1}{H}\sum_{i=1}^{H}x_{i},$
$\displaystyle\hat{x}_{i}=x_{i}-\mu$ (4)
$\displaystyle\sigma_{\mathrm{std}}^{2}$
$\displaystyle=\frac{1}{H}\sum_{i=1}^{H}\hat{x}_{i}^{2},$
$\displaystyle\sigma_{\mathrm{std}}=\sqrt{\sigma_{\mathrm{std}}^{2}}$ (5)
$\displaystyle\mathrm{LN}(\mathbf{x})_{i}$
$\displaystyle=y_{i}=\frac{\hat{x_{i}}}{\sigma_{\mathrm{std}}}$ (6)

where $\mu$ (4) is the hidden unit mean, $\hat{x}_{i}$ (4) is the centered
hidden unit $x_{i}$, $\sigma_{\mathrm{std}}^{2}$ (5) is the hidden unit
variance, and $y_{i}$ (6) is the normalized hidden unit. In practice, one can
scale $y_{i}$ by a learnable parameter $\gamma$ or shift by a learnable
parameter $\beta$. The LayerNormLSTM cell is defined as in Ba, Kiros, and
Hinton (2016).

###  3.3 Attention

Attention is often used in encoder-decoder RNN architectures (Bahdanau, Cho,
and Bengio, 2015; Chorowski et al., 2015; Wu et al., 2016). We employ Bahdanau
attention, also called additive attention (Bahdanau, Cho, and Bengio, 2015).
The attention mechanism allows the decoder network to attend to the variable-
length output states from the encoder based on their relevance to the current
decoder timestep. At each of its timesteps, the decoder extracts information
from the encoder’s states and summarizes it as a context vector,

$\displaystyle\mathbf{s}_{t}$
$\displaystyle=\sum_{i=1}^{T_{\mathrm{enc}}}\alpha_{ti}\odot\mathbf{h}_{\mathrm{enc}_{i}}$
(7) $\displaystyle\alpha_{ti}$
$\displaystyle=\frac{\text{exp}(e_{ti})}{\sum_{j=1}^{T_{\mathrm{enc}}}\text{exp}(e_{tj})}$
(8) $\displaystyle e_{ti}$
$\displaystyle=\mathbf{v}^{\top}\text{tanh}(\mathbf{W}_{q}\mathbf{h}_{t-1}+\mathbf{W}_{k}\mathbf{h}_{enc_{i}})$
(9)

where $\mathbf{s}_{t}$ is the context at decoder timestep $t$ which is a
weighted sum of the encoder hidden states outputs
$\mathbf{h}_{\mathrm{enc}_{i}}\in\mathbb{R}^{m_{\mathrm{enc}}}$ along encoder
timesteps $i\in\\{1,...,T_{\mathrm{enc}}\\}$ ; $0<\alpha_{ti}<1$ are the
attention weights attributed to each encoder hidden states based on the
alignments $e_{ti}\in\mathbb{R}$; $m_{\mathrm{dec}}$ and $m_{\mathrm{enc}}$
are respectively the decoder and encoder hidden state dimension;
$\\{\mathbf{W}_{q}\in\mathbb{R}^{m_{\mathrm{att}}\times
m_{\mathrm{dec}}},\mathbf{W}_{k}\in\mathbb{R}^{m_{\mathrm{att}}\times
m_{\mathrm{enc}}}\\}$ are the weights matrices of output dimension
$m_{\mathrm{att}}$ respectively applied to the query $\mathbf{h}_{t-1}$ and
the keys $\mathbf{h}_{\mathrm{enc}_{i}}$;
$\mathbf{v}\in\mathbb{R}^{m_{\mathrm{att}}}$ is a learned weight vector. The
context vector is incorporated into the LSTM cell by modifying (1) to

$\displaystyle\begin{pmatrix}\mathbf{i}\\\ \mathbf{f}\\\ \mathbf{j}\\\
\mathbf{o}\end{pmatrix}=\mathbf{W}_{x}\mathbf{x}_{t}+\mathbf{W}_{h}\mathbf{h}_{t-1}+\mathbf{W}_{s}\mathbf{s}_{t}$
(10)

where $\mathbf{W}_{s}\in\mathbb{R}^{4m_{\mathrm{dec}}\times
m_{\mathrm{enc}}}$.

###  3.4 Quantization

Quantization is a process whereby an input set is mapped to a lower resolution
discrete set, called the quantization set $\mathcal{Q}$. The mapping is either
performed from floating-points to integers (e.g. float32 to int8) or from a
dense integer to another integer set with lower cardinality, e.g. int32 to
int8. We follow the Quantization-Aware Training (QAT) scheme described in
Jacob et al. (2017).

Given $x\in[x_{\min},x_{\max}]$, we define the quantization process as

$\displaystyle q_{x}=\mathrm{q}(x)$
$\displaystyle=\Big{\lfloor}\frac{x}{S_{x}}\Big{\rceil}+Z_{x}$ (11)
$\displaystyle r_{x}=\mathrm{r}(x)$ $\displaystyle=S_{x}(q_{x}-Z_{x})$ (12)
$\displaystyle S_{x}=\frac{x_{\max}-x_{\min}}{2^{b}-1},~{}~{}$ $\displaystyle
Z_{x}=\Big{\lfloor}\frac{-x_{\min}}{S_{x}}\Big{\rceil}$ (13)

where the input is clipped between $x_{\min}$ and $x_{\max}$ beforehand;
$\lfloor.\rceil$ is the round-to-nearest function; $S_{x}$ is the scaling
factor (also known as the step-size); $b$ is the bitwidth, e.g. $b=8$ for
8-bit quantization, $b=16$ for 16-bit quantization; $Z_{x}$ is the zero-point
corresponding to the quantized value of 0 (note that zero should always be
included in $[x_{\min},x_{\max}]$); $\mathrm{q}(x)$ quantize $x$ to an integer
number and $\mathrm{r}(x)$ gives the floating-point value $\mathrm{q}(x)$
represents, i.e. $\mathrm{r}(x)\approx x$. We refer to
$\\{x_{\min},x_{\max},b,S_{x},Z_{x}\\}$ as quantization parameters of $x$.
Note that for inference, $S_{x}$ is expressed as a fixed-point integer number
rather than a floating-point number, allowing for integer-only arithmetic
computations (Jacob et al., 2017).

##  4 Methodology

In this section, we describe our task-agnostic quantization-aware training
method to enable integer-only RNN (iRNN).

###  4.1 Integer-only activation

First, we need to compute activation functions without relying on floating-
point operations to take the early step towards an integer-only RNN. At
inference, the non-linear activation is applied to the quantized input
$q_{x}$, performs operations using integer-only arithmetic and outputs the
quantized result $q_{y}$. Clearly, given the activation function $f$,
$q_{y}=q(f(q_{x}))$; as the input and the activation output are both
quantized, we obtain a discrete mapping from $q_{x}$ to $q_{y}$. There are
several ways to formalize this operation. The first solution is a Look-Up
Table (LUT), where $q_{x}$ is the index and $q_{y}=\text{LUT}[q_{x}]$. Thus,
the number of slots in the LUT is $2^{b}$ (e.g. 256 bytes for $b=8$ bits input
$q_{x}$). This method does not scale to large indexing bitwidths, e.g. 65536
slots need to be stored in memory for 16-bit activation quantization. LUT is
not cache-friendly for large numbers of slots. The second solution is
approximating the full-precision activation function using a fixed-point
integer Taylor approximation, but the amount of computations grows as the
approximation order grows. We propose to use a Quantization-Aware PWL that
selects PWL knots during the training process to produce the linear pieces.
Therefore the precision of approximation adapts to the required range of data
flow automatically and provides highly accurate data-dependent activation
approximation with fewer pieces.

Figure 2:  Tanh approximations using quantization-aware PWLs with 4 knots
(left panel), 16 pieces (right panel) using (14). The dashed cyan curves are
the true tanh functions, while the solid orange curves are its approximation
from Algorithm 1. Red dots are the knots. The more we add pieces, the better
the approximation is. Our algorithm is able to prioritize sections of the
function with more curvatures.

A PWL is defined as follows,

$\displaystyle
g(x)=\sum_{i=1}^{N}\mathbbm{1}_{[k_{i},k_{i+1})}\Big{(}a_{i}(x-k_{i})+b_{i}\Big{)},$
(14)

where $N$ is the number of linear pieces defined by $N+1$ knots (also known as
cutpoints or breakpoints); $\\{a_{i},k_{i},b_{i}=f(k_{i})\\}$ are the slope,
the knot, and the intercept of the $i^{\text{th}}$ piece respectively;
$\mathbbm{1}_{A}(x)=1$ is the indicator function on $A$. The more the linear
pieces, the better the activation approximation is (see Figure 2). A PWL is
suitable for simple fixed-point integer operations. It only relies on basic
arithmetic operations and is easy to parallelize because the computation of
each piece is independent. Therefore, the challenge is to select the knot
locations that provide the best PWL approximation to the original function
$f$. Note in this regime, we only approximate the activation function on the
subset corresponding quantized inputs and not the whole full-precision range.
In our proposed method if $x=k_{i}$ then $g(x)=g(k_{i})=b_{i}$, i.e. recovers
the exact output $f(k_{i})$. Hence, if the PWL has $2^{b}$ knots (i.e.
$2^{b}-1$ pieces), it is equivalent to a look-up table representing the
quantized activation function. Thus, we constraint the knots to be a subset of
the quantized inputs of the function we are approximating (i.e.
$\\{k_{i}\\}_{i=1}^{N+1}\subseteq\mathcal{Q}$).

We propose a recursive greedy algorithm to locate the knots during the
quantization-aware PWL. The algorithm starts with $2^{b}-1$ pieces and
recursively removes one knot at a time until it reaches the specified number
of pieces. The absolute differences between adjacents slopes are computed, and
the shared knot from the pair of slopes that minimizes the absolute difference
is removed; see Appendix Figure 3. The algorithm is simple to implement and
applied only once at a given training step; see Appendix Algorithm 1. This
algorithm is linear in time and space complexity with respect to the number of
starting pieces and is generic, allowing it to cover various nonlinear
functions. Note that the PWL is specific to a given set of quantization
parameters, i.e. the quantization parameters are kept frozen after its
creation.

At inference, the quantization-aware PWL is computed as follows

$\displaystyle
q_{y}=\Big{\lfloor}\sum_{i=1}^{N}\mathbbm{1}_{[q_{k_{i}},q_{k_{i+1}})}\Big{(}\frac{S_{x}a_{i}}{S_{y}}(q_{x}-q_{k_{i}})+\frac{b_{i}}{S_{y}}\Big{)}\Big{\rceil}+Z_{y},$

where the constants are expressed as fixed-point integers.

###  4.2 Integer-only normalization

Normalization greatly helps the convergence of quantized networks (Hou et al.,
2019; Sari and Partovi Nia, 2020). There is a plurality of measures of
location and scale to define normalization operation. The commonly used
measure of dispersion is the standard deviation to define normalization, which
is imprecise and costly to compute on integer-only hardware. However, the mean
absolute deviation (MAD) is integer-friendly and defined as

$d=\frac{1}{H}\sum_{i=1}^{H}|x_{i}-\mu|=\frac{1}{H}\sum_{i=1}^{H}|\hat{x}_{i}|.$
(15)

While the mean minimizes the standard deviation, the median minimizes MAD. We
suggest measuring deviation with respect to mean for two reasons: i) the
median is computationally more expensive ii) the absolute deviation from the
mean is closer to the standard deviation. For Gaussian data, the MAD is
$\approx 0.8\sigma_{\mathrm{std}}$ so that it might be exchanged with standard
deviation. We propose to LayerNorm in LSTM with MAD instead of standard
deviation and refer to it as MadNorm., where (6) is replaced by

$y_{i}=\frac{\hat{x}_{i}}{d}.$ (16)

MadNorm involves simpler operations, as there is no need to square and no need
to take the square root while taking absolute value instead of these two
operations is much cheaper. The values $\\{\mu,\hat{x}_{i},d,y_{i}\\}$ are
8-bit quantized and computed as follows

$\displaystyle q_{\mu}$
$\displaystyle=\Big{\lfloor}\frac{S_{x}}{S_{\mu}N}\Big{(}\sum_{i=1}^{N}q_{x_{i}}-NZ_{x}\Big{)}\Big{\rceil}+Z_{\mu},$
(17) $\displaystyle q_{\hat{x}_{i}}$
$\displaystyle=\Big{\lfloor}\frac{S_{x}}{S_{\hat{x}}}(q_{x_{i}}-Z_{x})-\frac{S_{\mu}}{S_{\hat{x}}}(q_{\mu}-Z_{\mu})\Big{\rceil}+Z_{\hat{x}},$
(18) $\displaystyle q_{d}$
$\displaystyle=\Big{\lfloor}\frac{S_{\hat{x}}}{S_{d}N}\sum_{i=1}^{N}|q_{\hat{x}_{i}}-Z_{\hat{x}}|\Big{\rceil}+Z_{d},$
(19) $\displaystyle q_{y_{i}}$
$\displaystyle=\Big{\lfloor}\frac{\frac{S_{\hat{x}}}{S_{y}S_{d}}(q_{\hat{x_{i}}}-Z_{\hat{x}})}{\mathrm{\max}(q_{d},1)}\Big{\rceil}+Z_{y},$
(20)

where all floating-point constants can be expressed as fixed-point integer
numbers, allowing for integer-only arithmetic computations. Note that (17-20)
are only examples of ways to perform integer-only arithmetic for MadNorm, and
may change depending on the software implementation and the target hardware.
We propose to quantize $\\{\mathbf{v},\mathbf{W}_{q},\mathbf{W}_{k}\\}$ to
8-bit. The vectors $\mathbf{h}_{t-1}$ and $\mathbf{h}_{\mathrm{enc}_{i}}$ are
quantized thank to the previous timestep and/or layer. The matrix
multiplications in (9) are performed in 8-bit and their results are quantized
to 8-bit, each with their own quantization parameters. Since those matrix
multiplications do not share the same quantization parameters, the sum (9)
require proper rescaling and the result is quantized to 16-bit. We found 8-bit
quantization adds too much noise, thus preventing the encoder-decoder model to
work correctly. The tanh function in (9) is computed using quantization-aware
PWL and its outputs are quantized to 8-bit. The alignments $e_{ti}$ are
quantized to 16-bit (9). The exponential function in $\alpha_{ti}$ is computed
using a quantization-aware PWL, with its outputs quantized to 8-bit. We found
that quantizing the softmax denominator (8) to 8-bit introduces too much noise
and destroys attention. 8-bit attention does not offer enough flexibility and
prevents fine grained decoder attention to the encoder. We left the
denominator in 32-bit integer value and defer quantization to 8-bit in the
division. The context vector $\mathbf{s}_{t}$ is quantized to 8-bit. Note that
in practice we shift the inputs to softmax for numerical stability reasons
(i.e. $e_{ti}-\max\limits_{j}e_{tj}$).

######  Theorem 1 (Scale convergence).

Suppose $X_{i}$ pairwise independent samples from the same probability space
$(\Omega,\mathcal{F},\Pr)$ with $\mu=\mathrm{I\\!E}(X_{i})$ and are absolutely
integrable, then $D_{n}={1\over n}\sum_{i=1}^{n}|X_{i}-\mu|$ converges almost
surely to $\tilde{\sigma}=\mathrm{I\\!E}(|X-\mu|).$

Proof: Absolutely integrable condition assures the existence of
$\mu=\mathrm{I\\!E}(X_{i})<\mathrm{I\\!E}(|X_{i}|)<\infty$ and hence the
existence of $\mathrm{I\\!E}|X_{i}-\mu|<\mathrm{I\\!E}|X_{i}|+\mu<\infty$. The
proof is straightforward by applying the standard strong law of large numbers
to $Y_{i}=|X_{i}-\mu|.\blacksquare$

One may prove the central limit theorem by replacing absolute integrability
with square integrability, and exchanging pairwise independence with mutual
independence. Convergence to the population scale $\tilde{\sigma}$ in Theorem
1 paves the way to show that our MadNorm enjoys a concentration inequality
similar to LayerNorm.

######  Theorem 2 (Concentration inequality).

Suppose the random variable $X$ with mean $\mu$ is absolutely integrable with
respect to the probability measure $P$. Then for a positive $k$, A vanilla
LSTM cell comprises matrix multiplications, element-wise additions, element-
wise multiplications, tanh, and sigmoid activations (1 \- 3). We quantize the
weights matrices $\mathbf{W}_{x}$ and $\mathbf{W}_{h}$ to 8-bit. The inputs
$\mathbf{x}_{t}$ and hidden states $\mathbf{h}_{t-1}$ are already 8-bit
quantized from the previous layer and from the previous timestep. The cell
states $\mathbf{c}_{t}$ are theoretically unbounded (2); therefore the amount
of quantization noise potentially destroys the information carried by
$\mathbf{c}_{t}$, if it spans a large range. When performing QAT on some pre-
trained models, it is advised to quantize $\mathbf{c}_{t}$ to 16-bit.
Therefore, $\mathbf{c}_{t}$ is 8-bit quantized unless stated otherwise but can
be quantized to 16-bit if necessary. Matrix multiplications in (1) are
performed with 8-bit arithmetic, and their outputs are quantized to 8-bit
based on their respective quantization parameters. The sum between the two
matrix multiplications outputs in (1) requires proper rescaling, because they
do not share the same quantization parameters.

$\Pr\left(\lvert{X-\mu\over\tilde{\sigma}}\rvert<k\right)\geq 1-{1\over k}$

Proof: Take $Y=\lvert{X-\mu\over\tilde{\sigma}}\rvert$. The random variable
$X$ is absolutely integrable, and so is $Y$.

$\displaystyle\mathrm{I\\!E}(Y)$ $\displaystyle=$
$\displaystyle\int_{0}^{\infty}YdP=\int_{0}^{k}YdP+\int_{k}^{\infty}YdP$
$\displaystyle\geq$ $\displaystyle 0+k\int_{k}^{\infty}YdP=k\Pr(Y>k),$

it follows immediately that
$\Pr\left(\lvert{X-\mu\over\tilde{\sigma}}\rvert>k\right)\leq{1\over
k}.\blacksquare$
Theorem 2 assures that independent of distribution of data, this MadNorm
brings the mass of the distribution around the origin. This is somehow
expected from any normalization method. It is not surprising to see that
LayerNorm also has a similar property, and therefore in this sense LayerNorm
and MadNorm assures the tail probability far from the origin is negligible.

There is a slight difference between the concentration inequality of LayerNorm
and MadNorm. The LayerNorm provides a tighter bound, i.e. the bound in Theorem
2 changes from $1-{1\over k}$ to $1-{1\over k^{2}}$ but it also requires more
assumptions like the square integrability of $X$.

###  4.3 Integer-only attention

Attention plays a crucial role in modern encoder-decoder architectures. The
decoder relies on attention to extract information from the encoder and
provide predictions. Attention is the bridge between the encoder and the
decoder. Careless quantization of attention breaks apart the decoder due to
quantization noise.

###  4.4 Integer-only LSTM network

The results of the sum are quantized to 8-bit; however, 16-bit quantization
might be necessary for complex tasks. The sigmoid and tanh activations in (2)
and (3) are replaced with their own quantization-aware PWL, and their output
is always quantized to 8-bit. The element-wise multiplications operations are
distributive, and sharing quantization parameters is not required. In (2), the
element-wise multiplications are quantized to 8-bit, but can be quantized to
16-bit if $\mathbf{c}_{t}$ is quantized to 16-bit as well; the element-wise
additions are quantized based on $\mathbf{c}_{t}$’s bitwidth (i.e. 8-bit or
16-bit).

The element-wise multiplications between sigmoid and tanh in (3) is always
quantized to 8-bit, because $\mathbf{h}_{t}$ are always quantized to 8-bit.
Following this recipe, we obtain an integer-only arithmetic LSTM cell, see
Figure. 1. For LSTM cells with LayerNorm quantized MadNorm layers are used
instead of LayerNorm. Appendix 7.1 provides details about quantization of
other types of layers in an LSTM model.

##  5 Experiments

We evaluate our proposed method, iRNN, on language modeling and automatic
speech recognition. We also implemented our approach on a smartphone to
benchmark inference speedup, see 5.4.

###  5.1 Language modeling on PTB

LayerNorm LSTM | val | test
---|---|---
Full-precision | $98.58\pm 0.35$ | $94.84\pm 0.21$
PWL4 | $101.40\pm 0.70$ | $98.11\pm 0.75$
PWL8 | $98.14\pm 0.11$ | $95.03\pm 0.16$
PWL16 | $98.09\pm 0.06$ | $94.92\pm 0.05$
PWL32 | $\mathbf{97.97}\pm 0.01$ | $\mathbf{94.81}\pm 0.02$
Table 1: Word-level perplexities on PTB with a LayerNorm LSTM and quantized
models with a different number of PWL pieces. LayerNorm is replaced with
MadNorm for the quantized models (iRNN). Best results are averaged across 3
runs $\pm$ standard deviation.

As a proof of concept, we perform several experiments on full-precision and
fully 8-bit quantized models on the Penn TreeBank (PTB) dataset (Marcus,
Santorini, and Marcinkiewicz, 1993). We report perplexity per word as a
performance metric.

For the quantized models, the LayerNorm is replaced with MadNorm. We do not
train full-precision models with MadNorm to make our method comparable with
common full-precision architectures. We can draw two conclusions from the
results presented in Table 1, i) replacing LayerNorm by MadNorm does not
destroy model performance, ii) using eight linear pieces is enough to retain
the performance of the model, but adding more linear pieces improves the
performance. We could obtain even superior results in the quantized model
compared to the full-precision model because of the regularization introduced
by quantization errors.

###  5.2 Language modeling on WikiText2

Mogrifier LSTM | val | test
---|---|---
Full-precision | $60.27\pm 0.34$ | $58.02\pm 0.34$
PWL8 | $60.91\pm 0.04$ |  $58.54\pm$ 0.07
PWL16 | $60.65\pm 0.09$ | $58.21\pm 0.08$
PWL32 | $\mathbf{60.37}\pm 0.03$ | $\mathbf{57.93}\pm 0.07$
Table 2: Word-level perplexities on WikiText2 with Mogrifier LSTM and
quantized models with different number of PWL pieces. Best results are
averaged across 3 runs $\pm$ standard deviations.

We evaluated our proposed method on the WikiText2 dataset (Merity et al.,
2016) with a state-of-the-art RNN, Mogrifier LSTM (Melis, Kočiský, and
Blunsom, 2020). The original code111https://github.com/deepmind/lamb was
written in TensorFlow, we reimplemented our own version in PyTorch by staying
as close as possible to the TensorFlow version. We follow the experimental
setup from the
authors222https://github.com/deepmind/lamb/blob/254a0b0e330c44e00cf535f98e9538d6e735750b/lamb/experiment/mogrifier/config/c51c838b33a5+˙tune˙wikitext-2˙35m˙lstm˙mos2˙fm˙d2˙arms/trial˙747/config
as we found it critical to get similar results. We use a two layer Mogrifier
LSTM. The setup and hyper-parameters for the experiments can be found in
Appendix 7.2.2 to save some space. We present our results averaged over 3 runs
in Table 2. We use the best full-precision model, which scores $59.95$
perplexity to initialize the quantized models. Our method is able to produce
8-bit quantized integer-only Mogrifier LSTM with similar performance to the
full-precision model with only about $0.3$ perplexity increase for the
quantized model with a PWL of 32 pieces and a maximum of about $0.9$
perplexity increase with a number of pieces as low as 8. Interestingly, a
pattern emerged by doubling the number of pieces, as we get a decrease in
perplexity by about $0.3$. We also perform a thorough ablation study of our
method in Appendix Table 5. Surprisingly, we found that stochastic weight
averaging for quantized models exhibits the same behavior as for full-
precision models and improved performance thanks to regularization. While
experiments on the PTB dataset were a demonstration of the potential of our
method, these experiments on WikiText2 show that our proposed method is able
to stay on par with state-of-the-art RNN models.

###  5.3 ASR on LibriSpeech

ESPRESSO LSTM | set | clean | other
---|---|---|---
Full-precision | dev | 2.99 | 8.77
iRNN PWL96* | dev | 3.73 | 10.02
Full-precision | test | 3.37 | 9.49
iRNN PWL96* | test | 4.11 | 10.71
Table 3: WER% on LibriSpeech with ESPRESSO LSTM (Encoder-Decoder LSTM with
Attention) with LM shallow fusion. *(160 pieces were used for the exponential
function)

ASR is a critical edge AI application, but also challenging due to the nature
of the task. Voice is diverse in nature as human voice may vary in pitch,
accent, pronunciation style, voice volume, etc. While we showed our method is
working for competitive language modeling task, one can argue ASR is a more
practical and at the same time more difficult task for edge and IoT
applications. Thefore, we experiment on an ASR task based on the setup of Wang
et al. (2019) and their ESPRESSO
framework333https://github.com/freewym/espresso. We used an LSTM-based
Attention Encoder-Decoder (ESPRESSO LSTM) trained on the strong ASR
LibriSpeech dataset (Panayotov et al., 2015). Experiments setup and hyper-
parameters are provided in Appendix 7.2.3 We initialize the quantized model
from the pre-trained full-precision ESPRESSO LSTM. In our early experiments,
we found that quantizing the model to 8-bit would not give comparable results.
After investigation, we noticed it was mainly due to two reasons, i) the cell
states $\mathbf{c}_{t}$ had large ranges (e.g. $[-17,15]$), ii) the attention
mechanism was not letting the decoder attend the encoder outputs accurately.
Therefore, we quantize the pre-activation gates (1), the element-wise
multiplications in (2) and cell states $\mathbf{c}_{t}$ to 16-bit. The
attention is quantized following our described integer-only attention method.
Everything else is quantized to 8-bit following our described method. The
quantized model has a similar performance to the full-precision model, with a
maximum of $1.25$ WER% drop (Table 3). We believe allowing the model to train
longer would reduce the gap.

###  5.4 Inference measurements

LSTM | ms | iter/s | speedup
---|---|---|---
Full-precision | 130 | 7.6 | $1.00\times$
iRNN PWL32 | 84 | 11.8 | $1.54\times$
iRNN PWL8 | 61 | 14.9 | $\mathbf{1.95\times}$
iRNN without QAct | 127 | 7.8 | $1.02\times$
Table 4: Inference measurements on an anonymous smartphone based on a custom
fork from PyTorch 1.7.1. The model is a one LSTM cell with a state size of
400.

We implemented an 8-bit quantized integer-only LSTM with PWL model based on a
custom PyTorch (Paszke et al., 2019) fork from 1.7.1. We implemented an
integer-only PWL kernel using NEON intrinsics. We benchmark the models on an
anonymous smartphone using the $\mathrm{speed\\_benchmark\\_torch}$
tool444https://github.com/pytorch/pytorch/blob/1.7/binaries/speed˙benchmark˙torch.cc.
We warm up each model for 5 runs and then measure the inference time a hundred
times and report an average. The sequence length used is 128, and the batch
size is one. We benchmark our iRNN LSTM model using PWLs with 32 pieces, and 8
pieces which achieve up to $2\times$ speedup. We also evaluate our iRNN with
full-precision computations (iRNN w/o QAct) for the activation where no
speedup was observed for this state size. We believe it is due to round-trip
conversions between floating-points and integers (Table 4). There is a lot of
room for improvements to achieve even greater speedup, such as writing a C++
integer-only LSTM cell, fusing operations, and better PWL kernel
implementation.

##  6 Conclusion

We propose a task-agnostic and flexible methodology to enable integer-only
RNNs. To the best of our knowledge, we are the first to offer an approach to
quantize all existing operations in modern RNNs, supporting normalization and
attention. We evaluated our approach on high-performance LSTM-based models on
language modeling and ASR, which have distinct architectures and variable
computation requirements. We show that RNN can be fully quantized while
achieving similar performance as their full-precision counterpart. We
benchmark our method on an anonymous smartphone, where we obtain $2\times$
inference speedup and $4\times$ memory reduction. This allows to deploy a wide
range of RNN-based applications on edge and on specialized AI hardware and
microcontrollers that lack floating point operation.

## REFERENCES

  * Ardakani et al. (2018) Ardakani, A.; Ji, Z.; Smithson, S. C.; Meyer, B. H.; and Gross, W. J. 2018.  Learning recurrent binary/ternary weights.  _arXiv preprint arXiv:1809.11086_.
  * Ba, Kiros, and Hinton (2016) Ba, J.; Kiros, J. R.; and Hinton, G. E. 2016.  Layer Normalization.  _ArXiv_ , abs/1607.06450.
  * Bahdanau, Cho, and Bengio (2015) Bahdanau, D.; Cho, K.; and Bengio, Y. 2015.  Neural Machine Translation by Jointly Learning to Align and Translate.  In Bengio, Y.; and LeCun, Y., eds., _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Bluche, Primet, and Gisselbrecht (2020) Bluche, T.; Primet, M.; and Gisselbrecht, T. 2020.  Small-Footprint Open-Vocabulary Keyword Spotting with Quantized LSTM Networks.  _arXiv preprint arXiv:2002.10851_.
  * Chen et al. (2018) Chen, M. X.; Firat, O.; Bapna, A.; Johnson, M.; Macherey, W.; Foster, G.; Jones, L.; Schuster, M.; Shazeer, N.; Parmar, N.; Vaswani, A.; Uszkoreit, J.; Kaiser, L.; Chen, Z.; Wu, Y.; and Hughes, M. 2018.  The Best of Both Worlds: Combining Recent Advances in Neural Machine Translation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 76–86. Melbourne, Australia: Association for Computational Linguistics.
  * Cho et al. (2014) Cho, K.; Van Merriënboer, B.; Bahdanau, D.; and Bengio, Y. 2014.  On the properties of neural machine translation: Encoder-decoder approaches.  _arXiv preprint arXiv:1409.1259_.
  * Chorowski et al. (2015) Chorowski, J.; Bahdanau, D.; Serdyuk, D.; Cho, K.; and Bengio, Y. 2015.  Attention-based models for speech recognition.  _arXiv preprint arXiv:1506.07503_.
  * Darabi et al. (2018) Darabi, S.; Belbahri, M.; Courbariaux, M.; and Nia, V. P. 2018.  BNN+: Improved Binary Network Training.  _CoRR_ , abs/1812.11800.
  * Esser et al. (2020) Esser, S. K.; McKinstry, J. L.; Bablani, D.; Appuswamy, R.; and Modha, D. S. 2020\.  Learned Step Size quantization.  In _ICLR_. OpenReview.net.
  * He et al. (2016) He, Q.; Wen, H.; Zhou, S.; Wu, Y.; Yao, C.; Zhou, X.; and Zou, Y. 2016.  Effective quantization methods for recurrent neural networks.  _arXiv preprint arXiv:1611.10176_.
  * He et al. (2019) He, Y.; Sainath, T. N.; Prabhavalkar, R.; McGraw, I.; Alvarez, R.; Zhao, D.; Rybach, D.; Kannan, A.; Wu, Y.; Pang, R.; et al. 2019.  Streaming end-to-end speech recognition for mobile devices.  In _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 6381–6385. IEEE.
  * Hochreiter and Schmidhuber (1997) Hochreiter, S.; and Schmidhuber, J. 1997.  Long Short-Term Memory.  _Neural Comput._ , 9(8): 1735–1780.
  * Hou et al. (2019) Hou, L.; Zhu, J.; Kwok, J. T.-Y.; Gao, F.; Qin, T.; and Liu, T.-y. 2019.  Normalization helps training of quantized lstm.
  * Hubara et al. (2018) Hubara, I.; Courbariaux, M.; Soudry, D.; El-Yaniv, R.; and Bengio, Y. 2018.  Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations.  _Journal of Machine Learning Research_ , 18(187): 1–30.
  * Jacob et al. (2017) Jacob, B.; Kligys, S.; Chen, B.; Zhu, M.; Tang, M.; Howard, A. G.; Adam, H.; and Kalenichenko, D. 2017.  Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference.  _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2704–2713.
  * Kapur, Mishra, and Marr (2017) Kapur, S.; Mishra, A.; and Marr, D. 2017.  Low precision rnns: Quantizing rnns without losing accuracy.  _arXiv preprint arXiv:1710.07706_.
  * Krishnamoorthi (2018) Krishnamoorthi, R. 2018.  Quantizing deep convolutional networks for efficient inference: A whitepaper.  _arXiv preprint arXiv:1806.08342_.
  * Marcus, Santorini, and Marcinkiewicz (1993) Marcus, M. P.; Santorini, B.; and Marcinkiewicz, M. A. 1993.  Building a Large Annotated Corpus of English: The Penn Treebank.  _Computational Linguistics_ , 19(2): 313–330.
  * Melis, Kočiský, and Blunsom (2020) Melis, G.; Kočiský, T.; and Blunsom, P. 2020.  Mogrifier LSTM.  In _International Conference on Learning Representations_.
  * Merity et al. (2016) Merity, S.; Xiong, C.; Bradbury, J.; and Socher, R. 2016.  Pointer Sentinel Mixture Models.  _CoRR_ , abs/1609.07843.
  * Ott et al. (2016) Ott, J.; Lin, Z.; Zhang, Y.; Liu, S.-C.; and Bengio, Y. 2016.  Recurrent neural networks with limited numerical precision.  _arXiv preprint arXiv:1608.06902_.
  * Panayotov et al. (2015) Panayotov, V.; Chen, G.; Povey, D.; and Khudanpur, S. 2015.  Librispeech: an ASR corpus based on public domain audio books.  In _Acoustics, Speech and Signal Processing (ICASSP), 2015 IEEE International Conference on_ , 5206–5210. IEEE.
  * Paszke et al. (2019) Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; Desmaison, A.; Kopf, A.; Yang, E.; DeVito, Z.; Raison, M.; Tejani, A.; Chilamkurthy, S.; Steiner, B.; Fang, L.; Bai, J.; and Chintala, S. 2019.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In Wallach, H.; Larochelle, H.; Beygelzimer, A.; d'Alché-Buc, F.; Fox, E.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc.
  * Rumelhart, Hinton, and Williams (1986) Rumelhart, D.; Hinton, G. E.; and Williams, R. J. 1986.  Learning internal representations by error propagation.
  * Sari, Courville, and Partovi Nia (2021) Sari, E.; Courville, V.; and Partovi Nia, V. 2021.  Appendix for iRNN: Integer-only Recurrent Neural Network.  Available at https://github.com/eyyub/irnn-appendix/blob/main/iRNN˙Appendix.pdf.
  * Sari and Partovi Nia (2020) Sari, E.; and Partovi Nia, V. 2020.  Batch normalization in quantized networks.  In _Proceedings of the Edge Intelligence Workshop_ , 6–9.
  * Wang, Wu, and Liu (2019) Wang, C.; Wu, S.; and Liu, S. 2019.  Accelerating Transformer Decoding via a Hybrid of Self-attention and Recurrent Neural Network.  _arXiv preprint arXiv:1909.02279_.
  * Wang et al. (2019) Wang, Y.; Chen, T.; Xu, H.; Ding, S.; Lv, H.; Shao, Y.; Peng, N.; Xie, L.; Watanabe, S.; and Khudanpur, S. 2019.  Espresso: A Fast End-to-End Neural Speech Recognition Toolkit.  In _2019 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU)_ , 136–143.
  * Wu et al. (2016) Wu, Y.; Schuster, M.; Chen, Z.; Le, Q. V.; Norouzi, M.; Macherey, W.; Krikun, M.; Cao, Y.; Gao, Q.; Macherey, K.; et al. 2016.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _arXiv preprint arXiv:1609.08144_.

##  7 Appendix

###  7.1 Specific details on LSTM-based models

For BiLSTM cells, nothing stated in section Integer-only LSTM network is
changed except that we enforce the forward LSTM hidden state
$\overrightarrow{\mathbf{h}}_{t}$ and the backward LSTM hidden state
$\overleftarrow{\mathbf{h}}_{t}$ to share the same quantization parameters so
that they can be concatenated as a vector. If the model has embedding layers,
they are quantized to 8-bit as we found they were not sensitive to
quantization. If the model has residual connections (e.g. between LSTM cells),
they are quantized to 8-bit integers. In encoder-decoder models the attention
layers would be quantized following section Integer-only attention. The
model’s last fully-connected layer’s weights are 8-bit quantized to allow for
8-bit matrix multiplication. However, we do not quantize the outputs and let
them remain 32-bit integers as often this is where it is considered that the
model has done its job and that some postprocessing is performed (e.g. beam
search).

###  7.2 Experimental details

iRNN Mogrifier LSTM | val | test
---|---|---
w/o PWL | $60.40\pm 0.05$ | $57.90\pm 0.01$
w/o Quantized Activations | $60.40\pm 0.03$ | $57.95\pm 0.003$
w/o Quantized Element-wise ops | $60.08\pm 0.10$ | $57.61\pm 0.23$
w/o Quantized Matmul | $60.10\pm 0.05$ | $57.64\pm 0.10$
w/o Quantized Weights (Full-precision) | $60.27\pm 0.34$ | $58.02\pm 0.34$
Table 5: Ablation study on quantized Mogrifier LSTM training on WikiText2.
iRNN w/o PWL is the quantized model using LUT instead of PWL to compute the
activation function. Best results are averaged across 3 runs, and standard
deviations are reported.

We provide a detailed explanation of our experimental setups.

####  7.2.1 LayerNorm LSTM on PTB

We provide detailed information about how the language modeling on PTB
experiments are performed. The vocabulary size is 10k, and we follow dataset
preprocessing as done in mikolov2012subword. We report the best _perplexity_
per word on the validation set and test set for a language model of embedding
size 200 with one LayerNormLSTM cell of state size 200. The lower the
perplexity, the better the model performs. In these experiments, we are
focusing on the relative increase of perplexity between the full-precision
models and their 8-bit quantized counterpart. We did not aim to reproduce
state-of-the-art performance on PTB and went with a naive set of hyper-
parameters. The full-precision network is trained on for 100 epochs with batch
size 20 and BPTT (werbos1990bptt) window size of 35. We used the SGD optimizer
with weight decay of $10^{-5}$ and learning rate 20, which is divided by 4
when the loss plateaus for more than 2 epochs without a relative decrease of
$10^{-4}$ in perplexity. We use gradient clipping of 0.25. We initialize the
quantized models from the best full-precision checkpoint and train from
another 100 epochs. For the first 5 epochs we do not enable quantization to
gather range statistics to compute the quantization parameters.

####  7.2.2 Mogrifier LSTM on WikiText2

We describe the experimental setup for Mogrifier LSTM on WikiText2. Note that
we follow the setup of Melis, Kočiský, and Blunsom (2020) where they do not
use dynamic evaluation (krause2018dyneval) nor Monte Carlo dropout
(gal2016mcdropout). The vocabulary size is 33279. We use a 2 layer Mogrifier
LSTM with embedding dimension 272, state dimension 1366, and capped input
gates. We use 6 modulation rounds per Mogrifier layer with low-rank dimension
48. We use 2 Mixture-of-Softmax layers (yang2018mos). The input and output
embedding are tied. We use a batch size of 64 and a BPTT window size of 70. We
train the full-precision Mogrifier LSTM for 340 epochs, after which we enable
Stochastic Weight Averaging (SWA) (izmailov2018swa) for 70 epochs. For the
optimizer we used Adam (kingma2014adam) with a learning rate of $\approx
3\times 10^{-3}$, $\beta_{1}=0$, $\beta_{2}=0.999$ and weight decay $\approx
1.8\times 10^{-4}$. We clip gradients’ norm to 10. We use the same hyper-
parameters for the quantized models from which we initialize with a pre-
trained full-precision and continue to train for 200 epochs. During the first
2 epochs, we do not perform QAT, but we gather min and max statistics in the
network to have a correct starting estimate of the quantization parameters.
After that, we enable 8-bit QAT on every component of the Mogrifier LSTM:
weights, matrix multiplications, element-wise operations, activations. Then we
replace activation functions in the model with quantization-aware PWLs and
continue training for 100 epochs.

We perform thorough ablation on our method to study the effect of each
component. Quantizing the weights or the weights and matrix multiplications
covers about $0.1$ of the perplexity increase. There is a clear performance
drop after adding quantization of element-wise operations with an increase in
perplexity of about $0.3$. This is both due to the presence of element-wise
operations in the cell and hidden states computations affecting the flow of
information across timesteps and to the residual connections across layers. On
top of that, adding quantization of the activation does not impact the
performance of the network.

####  7.2.3 ESPRESSO LSTM on LibriSpeech

The encoder is composed of 4 CNN-BatchNorm-ReLU blocks followed by 4 BiLSTM
layers with 1024 units. The decoder consists of 3 LSTM layers of units 1024
with Bahdanau attention on the encoder’s hidden states and residual
connections between each layer. The dataset preprocessing is exactly the same
as in Wang et al. (2019). We train the model for 30 epochs on one V100 GPU,
which takes approximately 6 days to complete. We use a batch size of 24 while
limiting the maximum number of tokens in a mini-batch to 26000. Adam is used
with a starting learning rate of $0.001$, which is divided by 2 when the
validation set metric plateaus without a relative decrease of $10^{-4}$ in
performance. Cross-entropy with uniform label smoothing $\alpha=0.1$
(szegedy2016inceptionv3) is used as a loss function. At evaluation time, the
model predictions are weighted using a pre-trained full-precision 4-layer LSTM
language model (shallow fusion). Note that we consider this language model an
external component to the ESPRESSO LSTM; we do not quantize it due to the lack
of resources. However, we already show in our language modeling experiments
that quantized language models retain their performance. We refer the reader
to Wang et al. (2019) and training
script555https://github.com/freewym/espresso/blob/master/examples/asr˙librispeech/run.sh
for a complete description of the experimental setup. We initialize the
quantized model from the pre-trained full-precision ESPRESSO LSTM. We train
the quantized model for only 4 epochs due to the lack of resources. The
quantized model is trained on 6 V100 GPUs where each epoch takes 2 days, so a
total of 48 GPU days. The batch size is set to 8 mini-batch per GPU with
maximum 8600 tokens. We made these changes because otherwise, the GPU would
run out of VRAM due to the added fake quantization operations. For the first
half of the first epoch, we gather statistics for quantization parameters then
we enable QAT. The activation functions are swapped with quantization-aware
PWL in the last epoch. The number of pieces for the quantization-aware PWLs is
96, except for the exponential function in the attention, which is 160 as we
found out it was necessary to have more pieces because of its curvature. The
number of pieces used is higher than in the language modeling experiments we
did. However, the difference is that the inputs to the activation functions
are 16-bit rather than 8-bit although the outputs are still quantized to
8-bit. It means we need more pieces to capture the inputs resolution better.
Note that it would not be feasible to use a 16-bit Look-Up Table to compute
the activation functions due to the size and cache misses, whereas using 96
pieces allows for a 170x reduction in memory consumption compared to LUT.

Full-precision model | val | test
---|---|---
LayerNorm LSTM | $98.58\pm 0.35$ | $94.84\pm 0.21$
MadNorm LSTM | $\mathbf{97.20}\pm 0.47$ | $\mathbf{93.63}\pm 0.74$
Table 6: Word-level perplexities on PTB for a full-precision LSTM with
LayerNorm and a full-precision model with MadNorm. Best results are averaged
across 3 runs, and standard deviations are reported. Figure 3: Example of an
iteration from our proposed quantization-aware PWL Algorithm 1. The algorithm
proceeds to reduce the number of pieces by merging two similar adjacents
pieces. In this figure, the slopes $S_{12}$ and $S_{23}$ are the most similar
pieces; therefore, the knot $k_{2}$ is removed.

def  _select_knots(_knots, intercepts, pwl_nb_)_:

dknots $\leftarrow$ knots$[1$:$]$ $-$ knots$[$:$-1]$

dintercepts $\leftarrow$ intercepts$[1$:$]$ $-$ intercepts$[$:$-1]$

slopes $\leftarrow$ $\text{dintercepts}/\text{dknots}$

if _len (slopes) $==$ pwl_nb_:

return _knots, slopes, intercepts_

else:

diff_adj_slopes $\leftarrow\Big{|}$slopes$[$:$-1]-$ slopes$[1$:$]\Big{|}$

knot_index_to_remove $\leftarrow\mathbf{argmin}$ diff_adj_slopes

remaining_knots $\leftarrow$ knots.remove(knot_index_to_remove)

remaining_intercepts $\leftarrow$ intercepts.remove(knot_index_to_remove)

return _select_knots(_remaining_knots, remaining_intercepts, pwl _nb _) _

def  _create_quantization_aware_pwl(_f, input_scale, input_zero_point, b,
pwl_nb_)_:

quantized_knots $\leftarrow[0,...,2^{b}-1]$ // Generate every $q_{x}$

knots
$\leftarrow\text{input\\_scale}\odot(\text{quantized\\_knots}-\text{input\\_zero\\_point})$
// Generate every $r_{x}$

intercepts $\leftarrow f(\text{knots})$

{knots, slopes, intercepts} $\leftarrow$ select_knots(_knots, intercepts, pwl
_nb_)

return _knots, slopes, intercepts_

Algorithm 1 The algorithm recursively reduced the number of pieces until the
wanted number of pieces is achieved. The algorithm needs to be provided the
function to approximate $f$, the input scaling factor $S_{x}$ and zero-point
$Z_{x}$, the quantization bitwidth $b$ and the number of linear pieces wanted.
One iteration of select_knots can be viewed in Figure 3.


######  Corollary 12.3.

If the nonempty connected components of
$\Sigma\setminus\cup_{j=0}^{k-1}\\{d_{2j+1}\\}$ are $K_{1},\dots,K_{m}$, then
$B_{k}(p/q,\nu)$ consists of exactly $m$ distinct periodic orbits
$P_{1},\dots,P_{m}$ with $\zeta(x)\in P_{j}$ if and only if $x\in o(K_{j},R)$.
Further, $\lambda_{k}(p/q,\nu)=\sum N|K_{j}|\delta_{j}$ with $\delta_{j}$ the
unique invariant probability measure supported in $P_{j}$ and
$N=qk/\gcd(p,k)$.

###### Proof.

As noted above, $J$ is a fundamental domain for the action of $R$ on $S_{k}$
and so it it suffices to study $\zeta(x)$ for $x\in J$.

Combining Lemma 12.2(a) and (b) we have that for $x\in\Sigma$,
$\zeta(x)=\zeta(x^{\prime})$ if and only if $x$ and $x^{\prime}$ are in the
same component $K_{j}$. Further, using Lemma 12.2(c), $\zeta(x)$ and
$\zeta(x^{\prime})$ can be on the same $\sigma$-orbit if and only if they are
in the same component $K_{j}$, proving the first sentence of the theorem. The
second sentence follows from the definition of $\lambda_{k}$, the fact that
$S_{k}=\cup_{i=1}^{N}R^{i}(J)$, and $R$ preserves Lebesgue measure. ∎

###  12.3. The pure lattice and the structure of $\operatorname{HM}_{kp/q}$

We now describe the pure affine lattice in more detail with an eye towards
counting the number of $p/q$-periodic kfsm sets. For this a new method of
specifying the address system in $S_{k}$ will be useful. We fix a $k$ and an
$\omega=p/q$ and sometimes suppress dependence on them

Recall that a pair $(p/q,\vec{\nu})$ specifies an address system
$\\{X_{j}(p/q,\vec{\nu})\\}$ with each
$X_{j}(p/q,\vec{\nu})=[\ell_{j},r_{j}]$. For each $i=1,\dots,k-1$ let
$\delta_{i}$ be the signed displacement of the address system from its totally
symmetric position given by $(\omega,\vec{\nu}_{s}(\omega))$. Thus

$\delta_{i}(\vec{\nu})=(\nu_{1}+\dots\nu_{i})-i(1-\omega).$ (12.1)

Since in the HM-construction $X_{2k}$ is fixed for all $\vec{\nu}$, the vector
$\vec{\delta}(\omega)$ is $(k-1)$-dimensional and so
$\vec{\delta}:{\mathcal{D}}_{k,p/q}\rightarrow\vec{\delta}({\mathcal{D}}_{k,p/q})$
is an affine map from the simplex $\sum\nu_{i}=k(1-p/q)$ to a subset of
${\mathbb{R}}^{k-1}$. Note that $\vec{\delta}(\vec{\nu}_{s})=\vec{0}$.

######  Lemma 12.4.

Given $k$ and $p/q$ there exists a $\vec{\eta}$ with
$\|\vec{\eta}\|_{\infty}\leq\gcd(p,k)/(2q)$ so that
$\vec{\nu}\in{\mathcal{D}}_{k,p/q}$ is a pure parameter for $p/q$ if and only
if $\vec{\delta}(p/q,\vec{\nu})\in\vec{\eta}+(\gcd(p,k)/q){\mathbb{Z}}^{k-1}$
in $\vec{\delta}({\mathcal{D}}_{k,p/q})$.

###### Proof.

The structure theorem Theorem 12.3 implies that $B_{k}(p/q,\vec{\nu})$ is a
single periodic orbit if and only if no $d_{2j-1}$ is in the interior of $J$.
This happens if and only if all $\ell_{2j-1}$ are contained in $o(0,R_{p/q})$.
Now $o(0,R_{p/q})$ divides $S_{k}$ evenly into subintervals of length
$\gcd(p,k)/q$. For each $j=1,\dots,k-1$ let $m_{j}$ be such that
$R^{m_{j}}_{p/q}(0)$ is the point on $o(0,R_{p/q})$ that is closest to
$\ell_{2j-1}$ and define $\eta_{j}=\ell_{2j-1}-R^{m_{j}}_{p/q}(0)$. Thus
$\|\vec{\eta}\|_{\infty}\leq\gcd(p,k)/(2q)$ and $\vec{\nu}$ is pure if and
only if $\phi(\vec{\nu})\in\vec{\eta}+(\gcd(p,k)/q){\mathbb{Z}}^{k-1}$. ∎

######  Definition 12.5.

The set
$L=\vec{\eta}+(\gcd(p,k)/q){\mathbb{Z}}^{k-1}\cap\vec{\delta}({\mathcal{D}}_{k,p/q})$
is called the $p/q$-pure affine lattice as is its pre-image
$\vec{\delta}^{-1}(L)\subset{\mathbb{R}}^{n-1}$

###  12.4. Sub-resonance and the size of clusters

######  Definition 12.6.

When $\omega=p/q$, the pair $(p/q,\nu)$ is called sub-resonant if for some
$qk/\gcd(p,k)>n>1$ and $j\not=j^{\prime}$,
$R_{\omega}^{n}(\ell_{j})=\ell_{j^{\prime}}$.

It follows from Theorem 12.3 that the number of sub-resonances in a
$(p/q,\vec{\nu})\in{\mathcal{D}}_{k,p/q}$ controls the number of distinct
periodic orbits in a cluster $B_{k}(p/q,\vec{\nu})$ with no sub-resonance
corresponding to $k$ distinct periodic orbits and all the $\ell_{j}$ on a
single $R_{p/q}$ orbit corresponding to $B_{k}(p/q,\vec{\nu})$ being a single
periodic orbit so $(p/q,\vec{\nu})$ is a pure parameter

The set sub-resonance parameters is a finite collection of codimension one
affine subspaces in ${\mathcal{D}}_{k,p/q}$ and thus the no sub-resonance case
is open, dense and full measure in ${\mathcal{D}}_{k,p/q}$. Thus in
$\operatorname{HM}_{k,p/q}$ the typical parameter corresponds to a cluster of
$k$ periodic orbits. It also follows that the assignment $\vec{\nu}\mapsto
B_{k}(p/q,\vec{\nu})$ restricted to $\operatorname{HM}_{k,p/q}$ is constant
and thus continuous on connected components of the no sub-resonance parameters
and is discontinuous at the sub-resonance parameters.

###  12.5. Estimating the number of $p/q$ kfsm sets

For a given $g\in{\mathcal{G}}$ the number of points from the pure
$p/q$-lattice $\operatorname{Pure}_{k,p/q}$ contained in
$\operatorname{HM}_{k,p/q}(g)$ tells us how many distinct periodic orbits
there are in ${\hat{{\mathcal{B}}}}_{k}(g)$. So by Lemma 10.7 it yields how
many distinct periodic $p/q$-kfsm sets $g$ has. We get an estimate for this
number using the continuity properties of $B_{k}$ from Theorem 9.5 and the
relationship of kfsm sets in $S_{k}$ to those in $S^{1}$. The next result
proves Theorem 1.2(b).

######  Theorem 12.7.

If $\alpha\in\operatorname{Int}(\rho(g))$, $\alpha\not\in{\mathbb{Q}}$, $k>0$
and $p_{n}/q_{n}$ is a sequence of rationals in lowest terms with
$p_{n}/q_{n}\rightarrow\alpha$, then there exists a $C>0$ so that for
sufficiently large $n$ the number of distinct periodic $p_{n}/q_{n}$ kfsm sets
in $\Lambda_{1}(g)$ is greater than or equal to $Cq_{n}^{k-1}$.

###### Proof.

By Theorem 9.5(b) there is an $\epsilon_{1}>0$ so that
$N_{\epsilon_{1}}(\vec{\nu}_{s}(\alpha))\subset\operatorname{HM}_{k}(g)$ where
recall that $\vec{\nu}_{s}(\alpha)$ is the Sturmian $\vec{\nu}$ for $\alpha$
on the diagonal of ${\mathcal{D}}_{k}$. Since $\vec{\delta}$ is a
homeomorphism there is an $\epsilon$-ball $H$ in the max norm with
$\epsilon>0$ about $\vec{0}$ in $\vec{\delta}({\mathcal{D}}_{k})$ with
$\vec{\delta}^{-1}(H)\subset\operatorname{HM}_{k}(g)$. Thus if
$|p_{n}/q_{n}-\alpha|<\epsilon$ there is a $\epsilon$-ball in the max norm,
i.e., a $(k-1)$-dimensional hypercube $H_{1}$, about $(p_{n}/q_{n},\vec{0})$
in $\vec{\delta}({\mathcal{D}}_{k,p_{n}/q_{n}})$ with
$\vec{\delta}^{-1}(H_{1})\subset\operatorname{HM}_{k,p_{n}/q_{n}}(g)$.

We next estimate the number of pure resonance $\vec{\nu}$ in $H_{1}$. By Lemma
12.4, the pure $\vec{\nu}$ form an affine lattice with linear separation
$\gcd(p_{n},k)/q_{n}$. Thus for $p_{n}/q_{n}$ close enough to $\alpha$, the
number of lattice points in $H_{1}$ is larger than

$\left(\frac{\epsilon
q_{n}}{\gcd(p_{n},k)}\right)^{k-1}\geq\left(\frac{\epsilon
q_{n}}{k}\right)^{k-1}.$

since $\gcd(p_{n},k)\leq k$. Thus since $\vec{\delta}$ is a homeomorphism the
same estimate holds for the number of pure lattice points in
$\vec{\delta}^{-1}(H_{1})\subset\operatorname{HM}_{k,p_{n}/q_{n}}(g)$. By
Theorem 9.5 this tells us how many distinct periodic $p_{n}/q_{n}$ are in
${\hat{{\mathcal{B}}}}_{k}(g)$ and thus in ${\mathcal{B}}_{k}(g)$ by Theorem
7.6.

To project this estimate to kfsm sets in $S^{1}$, recall from Theorem 10.10
that
$\theta_{k}:\overline{\operatorname{HM}}_{k,p_{n}/q_{n}}(g)\rightarrow{\mathcal{C}}_{k,p_{n}/q_{n}}(g)$
is injective on the pure lattice. The projection
$\operatorname{Pure}(k,p_{n}/q_{n})\rightarrow\overline{\operatorname{Pure}}(k,p_{n}/q_{n})$
is at most $k$ to $1$ and so the number of distinct $p_{n}/q_{n}$ periodic
orbits in ${\mathcal{C}}(g)$ is greater than or equal to

$\frac{1}{k}\left(\frac{\epsilon}{k}\right)^{k-1}q_{n}^{k-1}.$

∎

######  Remark 12.8.

For a pure $\vec{\nu}$ for $p/q$ when $\tau^{j}(\vec{\nu})=\vec{\nu}$ for some
$0<j<k$ the period of the $C_{k}(p/q,\vec{\nu})$ counted in the theorem is
$jq/\gcd(j,p)$ (Lemma 12.1). In the typical case of no such symmetry the
period is $kq/\gcd(k,p)$. So, for example, when $p$ and $k$ are relatively
prime, the counted periodic orbit has rotation type $(pk,qk)$ and when $k$
divides $p$ the rotation type is $(p,q)$. By making judicious choices of the
sequence $p_{n}/q_{n}\rightarrow\alpha$, one can control the rotation types of
the counted periodic orbits.

##  13\. Parameterization via the interpolated family of maps

We return now to the heuristic description in the introduction of kfsm sets
via a family of interpolated semi-monotone maps and prove a few results and
connections to the HM-parameterization. Since we are mainly developing a
heuristic, some details are left to the reader. In many ways this point of
view is better for studying kfsm sets while the HM construction is better for
measures. Initially the parameterization depends on the map
$\tilde{g}\in{\mathcal{G}}$ but using the model map we will get a uniform
parameterization.

###  13.1. The family of k-fold interpolated maps for $g\in{\mathcal{G}}$

Fix $g\in{\mathcal{G}}$ with preferred lift $\tilde{g}$. For
$y\in[g(x_{min}+n),g(x_{max}+n)]$ there is a unique
$x\in[x_{min}+n,x_{max}+n]$ with $\tilde{g}(x)=y$. Denote this $x$ as
$b_{n}(y)$ ($b$ for branch). Let $L_{g}=\tilde{g}(\min(\Lambda_{\infty}(g)\cap
I_{0}))$ and $U_{g}=\tilde{g}(\max(\Lambda_{\infty}(g)\cap I_{-1}))$ with the
$I_{i}$ as defined in Section 5.1. Note from the definition of the class
${\mathcal{G}}$, $0\leq L_{g}<U_{g}\leq 1$ and by equivariance,
$L_{g}+j=\tilde{g}(\min(\Lambda_{\infty}(g)\cap I_{2j}))$ and
$U_{g}+j=\tilde{g}(\max(\Lambda_{\infty}(g)\cap I_{2j-1}))$.

######  Definition 13.1.

For $\vec{c}\in{\mathbb{R}}^{k}$ define $\tilde{c}\in{\mathbb{R}}^{k}$ via
$\tilde{c}_{j}=c_{j}+j-1$ for $j=1,\dots,k$.

Fix $k>0$. For $\vec{c}\in[L_{g},U_{g}]^{k}$ and for $j=1,2,\dots,k$ define
$\tilde{H}_{k\vec{c}}(x)$ on $[b_{-1}(0),b_{-1}(0)+k]$ as

$\tilde{H}_{k\vec{c}}(x)=\begin{cases}\tilde{c}_{j}&\text{when}\
x\in[b_{j-2}(c_{j}),b_{j-1}(c_{j})]\\\
\tilde{g}(x)&\text{otherwise}\end{cases}$

and extend to $\tilde{H}_{k\vec{c}}:{\mathbb{R}}\rightarrow{\mathbb{R}}$ so
that $\tilde{H}_{k\vec{c}}(x+k)=\tilde{H}_{k\vec{c}}(x)+k$. See Figure 1. Next
define $H_{k\vec{c}}:S_{k}\rightarrow S_{k}$ as the descent of $H_{k,\vec{c}}$
to $S_{k}$.

Example: The model map For the model map $f_{m}$,
$x_{min}=0,x_{max}=1/2,L=0,U=1/2$ and $b_{j}(y)=(y+2j)/3$.

Given a compact $Z\subset\Lambda_{k}(g)$, for $j=0,\dots,k$ let

$\ell_{j}^{\prime}(Z)=\tilde{g}_{k}(\max\\{Z\cap I_{2j-1}\\})-(j-1)\
\text{and}\ r_{j}^{\prime}(Z)=\tilde{g}_{k}(\min\\{Z\cap I_{2j}\\})-(j-1).$

If for some $j$ we have $\ell_{j}^{\prime}<L_{g}$ let $\ell_{j}=L_{g}$
otherwise let $\ell_{j}=\ell_{j}^{\prime}$. Similarly, and if for some $j$, we
have $r_{j}^{\prime}>R_{g}$ let $r_{j}=R_{g}$ otherwise let
$r_{j}=r_{j}^{\prime}$. Not that these $r$’s and $\ell$’s are unrelated to
those in Section 9.1.

######  Theorem 13.2.

Assume $Z\subset\Lambda_{k}(g)$ is compact and invariant. The following are
equivalent

  1. (a)

$Z$ is a kfsm set

  2. (b)

For $j=1,\dots,k$, $\ell_{j}(Z)\leq r_{j}(Z)$.

  3. (c)

$Z\subset P(H_{k\vec{c}})$ for

$\vec{c}\in\prod_{j=1}^{k}[\ell_{j}(Z),r_{j}(Z)]$ (13.1)

thus $(\tilde{g}_{k})_{|Z}=(H_{k\vec{c}})_{|Z}$.

###### Proof.

If for some $j$, $\ell_{j}(Z)>r_{j}(Z)$ then $g$ restricted to $Z$ doesn’t
preserve the cyclic order, and so (a) implies (b). (c) implies (a) since
invariant sets in nondecreasing maps are always kfsm. Finally, (b) says that
$Z\subset P(H_{k\vec{c}})$ for $\vec{c}$ in the given range. ∎

######  Definition 13.3.

For $Z\in{\mathcal{B}}_{k}(g)$, let

$\operatorname{Box}_{g}(Z)=\prod_{j=1}^{k}[\ell_{j}(Z),r_{j}(Z)]$

and so $\operatorname{Box}_{g}(Z)\subset[L_{g},U_{g}]^{k}$.

######  Remark 13.4.

  1. (a)

Nothing in the theorem requires $Z$ to be recurrent. If it is, so
$Z\in{\mathcal{B}}_{k}(g)$, from Theorem 8.5,
$\iota_{k}(Z)=B_{k}(\omega,\vec{\nu})$ where $\omega=\rho_{k}(Z)$ and
$\vec{\nu}\in{\mathcal{D}}_{k\omega}$.

  2. (b)

When $Z$ is a periodic orbit or cluster, $\operatorname{Box}_{g}(Z)$ is
$k$-dimensional. When $Z$ is a periodic orbit cluster its box is equal to the
intersections of the boxes of its constituent single periodic orbits.

  3. (c)

When $Z$ is a semi-Denjoy minimal set contained in $P(H_{k\vec{c}})$ recall
that a tight flat spot of $Z$ is one for which both endpoints of a flat spot
of $H_{k\vec{c}}$ are in $Z$. The dimension of $\operatorname{Box}_{g}(Z)$ is
the same as the number of loose flat spots in $Z$. Since by Lemma 3.5(b), $Z$
cannot have $k$ tight flat spots, the dimension of $\operatorname{Box}_{g}(Z)$
is between $0$ and $k-1$.

  4. (d)

Note that in contrast, in the HM parameterization, each single periodic orbit
or semi-Denjoy minimal corresponds to just one point.

  5. (e)

When $\alpha\not\in{\mathbb{Q}}$, if
$Z=\iota_{k}^{-1}(B_{k}(\alpha,\vec{\nu}))$ from the HM construction then the
number of loose flat spots of $Z$ is the same as the number of resonances of
$(\alpha,\vec{\nu})$ i.e., $j\not=j^{\prime}$ with
$R_{\alpha}^{N}(\ell_{j})=\ell_{j^{\prime}}$ for some $n>1$ which is then the
same as the dimension of $\operatorname{Box}_{g}(Z)$.

###  13.2. Nonrecurrence and kfsm sets that hit the negative slope region

Throughout this paper we have assumed that the kfsm sets were recurrent and
avoided the negative slope region. In this section we use the interpolated
maps to motivate these assumptions.

Assume now that $Z$ is a kfsm set for some $g\in{\mathcal{G}}$ and $Z$
contains points in the negative slope region of $g$. It still follows that $Z$
is an invariant set of some $H_{k\vec{c}}$. Let $Z^{\prime}$ be the maximal
recurrent set in $P(H_{k\vec{c}})$. A gap of $Z^{\prime}$ is a component of
the complement of $Z^{\prime}$ that contains a flat spot of $H_{k\vec{c}}$. In
formulas, a gap is an interval $(\max\\{Z^{\prime}\cap
I_{2j-1}\\},\min\\{Z^{\prime}\cap I_{2j}\\})$ for some $j$. Since $g_{k}$
acting on $Z$ is semi-monotone, $Z$ can contain at most one point $p_{j}$ in
the negative slope region within each gap.

There are two cases. In the first, which may happen for both rational and
irrational rotation number, for all $j^{\prime}$ there is some $n$ so that
$f^{i}(p_{j^{\prime}})\not\in\\{p_{j}\\}$ for all $i\geq n$. This implies that
$H_{k\vec{c}}^{i}(p_{j})\in P(H_{k\vec{c}})$ for all $i\geq n$ and so by Lemma
3.5(c), there is an $n^{\prime}$ so that $H_{k\vec{c}}^{i}(p_{j})\in
Z^{\prime}$ for all $i\geq n^{\prime}$. Thus in this case negative slope
orbits add no additional recurrent dynamics. In Figure 4 the disks give part
of a periodic kfsm set and the squares show additional homoclinic points to
this kfsm set in the negative and positive slope region.

Figure 4. A semi-monotone set with homoclinic points

The second case holds for just rational rotation number and is when some
$p_{j}$ is a periodic point; this does add new recurrent kfsm sets. Since the
periodic points on the endpoint of a gap always return, there is, in fact, a
periodic point in the negative slope region of each gap of $Z^{\prime}$. By
adjusting $\vec{c}$ we can assume that all these gap periodic orbits are also
superstable periodic orbits of $H_{k\vec{c}}$. Since the periodic points in
$Z^{\prime}$ are all unstable the periodic points of $Z^{\prime}$ must
alternate with these gap periodic points. In particular, the number of gap
periodic orbits equals the number of periodic orbits in $Z^{\prime}$. Thus the
addition of the negative slope periodic orbits just adds a factor of two to
the basic estimates of Section 12.5.

We again use Figure 4 but this time to discuss the holes in the space of
recurrent kfsm sets. Let $H_{c_{0}}$ be an interploted map whose flat spot
contains the homoclinic points indicated by squares. Assume we are in the
$k=1$ case and so each interpolated map $H_{c}$ contains exactly one recurrent
semi-monotone set $Z_{c}$ in its positive slope region. As $c_{n}$ increases
to $c_{0}$ the sets $Z_{c_{n}}$ converge in the Hausdorff topology to not just
$Z_{c_{0}}$ but to that set union the boxed point in the positive slope
region. A similar phenomenon happens as $c_{n}$ decreases to $c_{0}$. This
phenomenon also clearly happens for loose gaps of semi-Denjoy minimal sets and
happens for all $k$. This is the geometric explanation of the holes in
${\mathcal{B}}_{k}(g)$ and the discontinuity of $B_{k}$ discussed in Section
9.1.

###  13.3. The rotation number diagram

Fix $g\in{\mathcal{G}}$. Since $H_{k\vec{c}}:S_{k}\rightarrow S_{k}$ we define
$R_{k}(\vec{c})=k\rho(D_{k}\circ H_{k\vec{c}}\circ D_{k}^{-1})$. Thus if
$Z\subset P(H_{k\vec{c}})$ is compact invariant then
$\rho_{k}(Z)=R_{k}(\vec{c})$. We treat $R_{k}$ as a function
$R_{k}:[L_{g},U_{g}]^{k}\rightarrow{\mathbb{R}}$.

Let ${\mathbb{R}}_{+}^{k}=\\{\vec{u}\in{\mathbb{R}}_{K}\colon\ \text{all}\
u_{i}>0\\}$. The open projective positive cone in ${\mathbb{R}}^{k}$ is
$Q_{k}=\\{\vec{u}\in{\mathbb{R}}^{k}_{+}\colon\|\vec{u}\|_{2}=1\\}$. For a
given $k,\omega$ define
$\varphi_{-,\omega},\varphi_{+,\omega}:Q_{k}\rightarrow{\mathbb{R}}^{+}$ as

$\displaystyle\varphi_{-,\omega}(\vec{u})$
$\displaystyle=\min\\{t\in{\mathbb{R}}^{+}\colon
R_{k}(t\vec{u}+\vec{L})=\omega\\}$
$\displaystyle\varphi_{+,\omega}(\vec{u})=\max\\{t\in{\mathbb{R}}^{+}\colon
R_{k}(t\vec{u}+\vec{L})=\omega\\}$

where $\vec{L}=(L_{g},L_{g},\dots,L_{g})$. So $\varphi_{-,\omega}$ and
$\varphi_{+,\omega}$ give the top and bottom edges of the level set
$R_{k}^{-1}(\omega)$ when view from the origin.

######  Theorem 13.5.

Assume $g\in{\mathcal{G}}$ and construct $R_{k}$ as above

  1. (a)

$R_{k}$ is continuous function and is nondecreasing in $t$ along any line
$\vec{c}=t\vec{u}+\vec{v}$ with all $v_{i}\geq 0$.

  2. (b)

For all $\omega$ the functions $\varphi_{-,\omega}$ and $\varphi_{+,\omega}$
are continuous.

  3. (c)

For rational $\omega$, $\varphi_{-,p/q}<\varphi_{+,p/q}$ while for
$\alpha\not\in{\mathbb{Q}}$ then $\varphi_{-,\alpha}=\varphi_{+,\alpha}$. Thus
each level set $R_{k}^{-1}(p/q)$ is homeomorphic to a $(k-1)$-dimensional open
disk product a nontrivial closed interval while each $R_{k}^{-1}(\alpha)$ is
homeomorphic to a $(k-1)$-dimensional open disk.

  4. (d)

$\rho(g)=[\rho(H_{L_{g}}),\rho(H_{U_{g}})]=\rho(\Lambda_{1}(g),g)$

###### Proof.

Part (a) follows directly from Lemma 3.1(b) and (c). For (b) assume to the
contrary that $\varphi_{-}$ is not continuous. Then there is a sequence
$\vec{u}_{n}\rightarrow\vec{u}_{0}$ with
$\varphi_{-}(\vec{u}_{n})\not\rightarrow\varphi_{-}(\vec{u}_{0})$. Passing to
a subsequence if necessary, there is some $t_{0}$ with
$\varphi_{-}(\vec{u}_{n})\vec{u}_{n}+\vec{L}\rightarrow
t_{0}\vec{u}_{0}+\vec{L}$. By the continuity of $R_{k}$,
$R_{k}(t_{0}\vec{u}_{0}+\vec{L})=\omega$ and by the nonconvergence assumption,
there is some $t^{\prime}<t_{0}$ with
$R_{k}(t^{\prime}\vec{u}_{0}+\vec{L})=\omega$. Thus again by the continuity of
$R_{k}$ for $n$ large enough there is some
$t^{\prime\prime}_{n}<\varphi_{-}(\vec{u}_{n})$ with
$R_{k}(t^{\prime\prime}_{n}\vec{u}_{n}+\vec{L})=\omega$, a contradiction.
Therefore, $\varphi_{-}$ is continuous: the continuity of $\varphi_{+}$ is
similar.

For (c), pick any $t_{0}$ and $\vec{u}_{0}$ with
$R_{k}(t_{0}\vec{u}_{0}+\vec{L})=p/q$ and let
$\vec{c}=t_{0}\vec{u}_{0}+\vec{L}$. Then by Lemma 3.5, $H_{\vec{c}}$ has a
periodic orbit $Z\subset P(H_{\vec{c}})$. Since $Z$ is a finite set there is a
nontrivial interval $I$ so that $t\in I$ implies
$R_{k}(t\vec{u}_{0}+\vec{L})=p/q$ and so $\varphi_{-,p/q}<\varphi_{+,p/q}$.

To complete (c), assume to the contrary that for some $\vec{u}_{0}$,
$\varphi_{-,\alpha}(\vec{u}_{0})<\varphi_{+,\alpha}(\vec{u}_{0})$. Thus by the
continuity of $R_{k}$ there is an open ball $N\subset R_{k}^{-1}(\alpha)$.
Pick $\vec{c}\in N$ and let $Z$ be the semi-Denjoy minimal set in
$P(H_{\vec{c}})$ guaranteed by Lemma 3.5 which has at least one tight gap, say
the gap associated with $c_{1}$ the first coordinate of $\vec{c}$. Let $y$ be
the $x$-coordinate of the right hand endpoint of this gap and so
$\tilde{g}_{k}(y)=c_{1}$. Since $Z$ is minimal under $H_{\vec{c}}$ there are
points $z\in Z$ with $z>y$ and arbitrarily close to $y$ which have a $n>0$
with $y<H_{\vec{c}}^{n}(z)<z$. Now let $c_{1}^{\prime}=\tilde{g}_{k}(z)$ and
$\vec{c}^{\prime}=(c_{1}^{\prime},c_{2},\dots,c_{k})$ and we have that
$H^{n}_{\vec{c}^{\prime}}(z)<z$ which says that the $n^{th}$ iterate of the
first coordinate flat spot of $H_{\vec{c}^{\prime}}$ is in that flat spot.
Thus $H_{\vec{c}^{\prime}}$ has a periodic orbit and so
$R_{k}(\vec{c}^{\prime})\not=\alpha$ for some $\vec{c}^{\prime}$ arbitrarily
close to $\vec{c}$, a contradiction.

For (d), assume $k=1$ and $\rho(g)=[\rho_{1},\rho_{2}]$. Let $H_{T}$ be the
semi-monotone map constructed from $g$ to have a single flat spot of height
$\tilde{g}(x_{max})$ and $H_{B}$ similarly constructed having a single flat
spot of height $\tilde{g}(x_{min})$. Since $H_{T}\geq\tilde{g}$, we have
$\rho(H_{T})\geq\rho_{1}$. Now by Lemma 3.5, there is a compact invariant
$Z\subset P(H_{T})$ and so $g_{|Z}=(H_{T})_{|Z}$ and so
$\rho(H_{T})=\rho(Z,g)\in\rho(g)$ and so $\rho(H_{T})=\rho_{1}$. Similarly,
$\rho(H_{B})=\rho_{2}$. Note that by definition of $H_{U}$, the compact
invariant $Z\subset P(H_{T})$ also satisfies $Z\subset P(H_{U})$ and so
$\rho(H_{T})=\rho(H_{U})$. Similarly, $\rho(H_{B})=\rho(H_{L})$. Thus
$\rho(g)=[\rho(H_{L}),\rho(H_{U})]$. Finally, consider the entire family
$H_{c}$ for $c\in[L,U]$. Since $\rho(H_{c})$ is continuous in $c$, for each
$\omega\in[\rho(H_{L}),\rho(H_{U})]$ there is a $c$ with $\rho(H_{c})=\omega$.
Further, for each $c$ there is a compact invariant $Z_{c}\subset P(H_{c})$ and
$Z_{c}\subset\Lambda_{1}(g)$ and thus
$\omega\in\rho(\Lambda_{1}(g))\subset\rho(g)$

∎

######  Remark 13.6.

  1. (a)

Note that $H_{T}(x)\leq x+1$ and $H_{B}(x)\geq x$ and thus $g\in{\mathcal{G}}$
implies $\rho(g)\subset[0,1]$. Further, it follows from (d) that the image of
each $R_{k}$ is $\rho(g)$.

  2. (b)

Part (b) deals only with the part of the level sets of $R_{k}$ in the open set
$(L_{g},U_{g})^{k}$. The extension to all of $[L_{g},U_{g}]^{k}$ is technical
and not very illuminating so we leave it to the interested reader.

  3. (c)

Let $\tau$ act on $\vec{c}$ as the left cyclic shift. It easily follows that
$R_{k}(\tau(\vec{c}))=R_{k}(\vec{c})$.

  4. (d)

When $k=1$ there is a one-dimensional family $H_{c}$ for $c\in[L_{g},U_{g}]$.
The rotation number $R_{1}(c)$ is nondecreasing in $c$ and assumes each
irrational value at a point and each rational value on an interval by (a) and
(c). For each $c$ there is a unique recurrent $Z_{c}\subset P(H_{c})$ and
$\iota_{1}(Z_{c})$ is the Sturmian with the given rotation number. This along
with the geometry of the family $H_{c}$ give the proof of Lemma 10.15.

###  13.4. Comparing $g\in{\mathcal{G}}$ to the model map

In this section we use the interpolation parameter $\vec{c}$ to parameterize
the $Z\in{\mathcal{B}}_{k}(g)$ for a general $g\in{\mathcal{G}}$. Notice that
for the model map, $\Lambda_{k}(f_{m})$ is all of $\Omega_{k}$. Thus
${\hat{{\mathcal{B}}}}_{k}(g)\subset{\hat{{\mathcal{B}}}}_{k}(f_{m})$ and so
we can pass back to ${\mathcal{B}}(g)$ using the inverse of the itinerary map.
Thus we can use a subset of the interpolation parameters of the model map to
parameterize ${\mathcal{B}}(g)$ using the symbolic representation of a kfsm
set as the link. This subset turns out to be a square of the form
$[L^{\prime},U^{\prime}]^{k}$. In this section we often add an additional
subscript of $f$ or $g$ to indicate which map $f_{m}$ or $g$ is involved

Since
$\iota_{k,g}(\Lambda_{k}(g))={\hat{\Lambda}}_{k}(g)\subset\Omega_{k}={\hat{\Lambda}}_{k}(f)$
we may define $\psi^{\prime}:\Lambda_{k}(g)\rightarrow\Lambda_{k}(f)$ by
$\psi^{\prime}=\iota_{kf}\circ\iota_{kg}^{-1}$. By Theorem 6.1 $\psi^{\prime}$
is an orientation preserving homeomorphism onto its image as well as a
conjugacy. It thus induces a map
$\overline{\psi}:{\mathcal{B}}_{k}(g)\rightarrow{\mathcal{B}}_{k}(f)$.

Recall that the parameters for the model map are
$[L_{f},U_{f}]^{k}=[0,1/2]^{k}$. For a map $\phi:[a,b]\rightarrow[a,b]$ extend
it to the Cartesian product as $\phi^{(k)}=(\phi,\phi,\dots,\phi)$.

######  Theorem 13.7.

Given $g\in{\mathcal{G}}$ and $k>0$ construct the interpolation parameters
$[L_{g},U_{g}]$. There exists an interval
$[L^{\prime},U^{\prime}]\subset[0,1/2]$ and an orientation preserving
homeomorphism $\phi:[U_{g},L_{g}]\rightarrow[L^{\prime},U^{\prime}]$ so that
for all $Z\in{\mathcal{B}}_{k}(g)$,
$\phi^{(k)}(\operatorname{Box}_{g}(Z)))=\operatorname{Box}_{f}(\overline{\psi}(Z))$
and for all $\omega\in\rho(g)$,
$\phi^{(k)}\rho_{k,g}^{-1}(\omega)=\rho_{k,f}^{-1}(\omega)$. Where

###### Proof.

Construct $\psi^{\prime}$ as above. Its properties imply that

$\psi^{\prime}(\ell_{j}(Z))=\ell_{j}(\overline{\psi}(Z))\ \text{and}\
\psi^{\prime}(r_{j}(Z))=r_{j}(\overline{\psi}(Z))$ (13.2)

for all $Z\subset{\mathcal{B}}_{k}(g)$ and $j=1,\dots,k$. Let
$L^{\prime}=\psi^{\prime}(L_{g})$ and $U^{\prime}=\psi^{\prime}(U_{g})$. Then
$\psi^{\prime}$ restricts to
$\psi:\Lambda_{k}(g)\cap[L_{g},U_{g}]^{k}\rightarrow\Lambda_{k}(f)\cap[L^{\prime},U^{\prime}]^{k}$.
Since $\psi T_{k}=T_{k}\psi$ and $\Lambda_{k}(g)\cap[L_{g},U_{g}]^{k}$ is
compact we can extend $\psi$ equivariantly to a homeomorphism
$\Psi:[L_{g},U_{g}]^{k}\rightarrow[L^{\prime},U^{\prime}]^{k}$ which using
(13.2) satisfies
$\Psi\circ\operatorname{Box}_{g}=\operatorname{Box}_{f}\circ\overline{\psi}$.
Finally, since $\Psi\circ\tau=\tau\circ\Psi$ (recall $\tau$ is the left cyclic
shift) there is a $\phi:[U_{g},L_{g}]\rightarrow[L^{\prime},U^{\prime}]$ with
$\Psi=\phi^{(k)}$. ∎

Thi result implies that the $\rho_{k}$-diagram for $g$ looks like
$k$-dimensional cube cut from inside the $\rho_{k}$-diagram of the model map
and perhaps rescaled.

###  13.5. The case $k=2$: numerics

Figure 5 shows the $k=2$ rotation number diagram for the model map $f_{m}$.
Each connected union of rectangles is the level set of some rational. The
rationals with denominator less than $6$ are shown. Only the center rectangle
is labeled for each rational. In the figure each rectangle corresponds to a
different $2$-fold semi-monotone periodic orbit. The intersections of these
rectangles correspond to $H_{\vec{c}}$ which have a cluster of two periodic
orbits

Figure 5. The rotation number diagram for the model map with $k=2$. Figure has
been reparameterized for clarity.

The computation of this diagram used a discrete version of the HM
construction. The construction depends on integers $p,q,\mu$ with $0<p/q<1$,
$p$ and $q$ relatively prime, and $0\leq\mu\leq 2(q-p)$. The discrete circle
is the finite cyclic group ${\mathbb{Z}}/2q{\mathbb{Z}}={\mathbb{Z}}_{2q}$ and
it is acted on by $R_{p}:n\mapsto n+p$. The address intervals are
$X_{0}^{\prime}=[1,\mu],X_{1}^{\prime}=[\mu+1,\mu+p],X_{2}^{\prime}=[\mu+p+1,2q-p]$,
and $I_{3}=[2q-p+1,2(q-p)]$. Let $B^{\prime}(p,q,\mu)$ be the itinerary of the
point $1$ under $R_{p}$.

Using Theorem 8.5(b), when $p$ is odd, $R_{p}$ has a single period $2q$ orbit
in ${\mathbb{Z}}_{2q}$. Expanding the points in ${\mathbb{Z}}_{2q}$ to
intervals in the circle as in the proof of Theorem 8.5(c), we see that by
varying $\mu$ the construction generates all the symbolic $p/q$-periodic
$2$-fold semi-monotone sets in $\Omega_{2}$.

Now when $p$ is even, $R_{p}$ has a pair of period $q$ orbits. When $\mu$ is
odd, these generate different periodic orbits $B^{\prime}(p,q,\mu)$. However,
$\mu$ even corresponds to a pure parameter and so varying $\mu$ through the
even $\mu$ generates all the symbolic $p/q$-periodic $2$-fold semi-monotone
sets in $\Omega_{2}$.

The next step is to use $B^{\prime}(p,q,\mu)$ to compute its symbolic box as
in Corollary 14.1 below. Finally, we take the inverse of the itinerary map for
the model map to get a box in the $\vec{c}$ parameter. Because the map $f_{m}$
has uniform slope of three in its positive slope region the formula for this
inverse is ${\underline{s}}\in\Sigma_{2}^{+}$,

$\iota_{1}^{-1}({\underline{s}})=\sum_{j=0}^{\infty}\frac{s_{j}}{3^{j+1}}.$
(13.3)

##  14\. Symbolic kfsm sets and the map $z\mapsto z^{n}$

Using the model map Theorem 13.2 characterising “physical” kfsm sets can be
directly transformed into a characterization of symbolic kfsm sets. For
compact ${\hat{Z}}\subset\Omega_{k}$ for $j=1,\dots,k$ define

${\hat{\ell}}_{j}(Z)=\sigma_{k}(\max\\{{\hat{Z}}\cap[2j-1]\\})\ \text{and}\
{\hat{r}}_{j}(Z)=\sigma_{k}(\min\\{{\hat{Z}}\cap[2j]\\})$

Since $\iota_{k}$ is order preserving and onto for the model map we have

######  Corollary 14.1.

Assume ${\hat{Z}}\subset\Omega_{k}$ is compact and shift invariant. The
following are equivalent

  1. (1)

${\hat{Z}}$ is kfsm

  2. (2)

For $j=1,\dots,k$, ${\hat{\ell}}_{j}({\hat{Z}})\leq{\hat{r}}_{j}({\hat{Z}})$
with indices reduced mod $2k$

If $Z$ is recurrent we know that each $Z\in{\mathcal{B}}_{k}(f)$ has
$\iota_{k}({\hat{Z}})=B_{k}(\omega,\vec{\nu})$ for some allowable
$(\omega,\vec{\nu})$ which yields an indirect connection between the
interpolated semi-monotone maps and HM parameterization.

There is a well known connection between the dynamics of $d_{n}:z\mapsto
z^{n}$ and the full shift on $n$ symbols. This yields a connection of the
symbolic kfsm sets as described by this corollary to invariant sets of the
circle on which the action of $d_{n}$ is semi-monotone, sometimes call
circular orbits.

Figure 6. The semi-monotone map corresponding to a symbolic $3$-fold semi-
monotone set interpolated into $z\mapsto z^{6}$

In Figure 6 we show the conditions forced by Corollary 14.1 as flat spots in
the graph of $d_{n}$ for $k=3$ and $n=6$. There are two classes of flat spots.
Those in class A are forced by the condition that ${\hat{Z}}\subset\Omega_{k}$
and thus satisfies (5.2). These are the intervals of width $1/6$,
$[1/18,2/9],[7/18,5/9]$ and $[13/18,8/9]$. These conditions are satisfied by
all symbolic kfsm sets in the corollary. The other three flat spots in class B
are determined by the conditions in part (b) of the corollary and vary with
the symbolic kfsm set. Note that the result of addding all the flat spots is a
degree one semi-monotone circle map as expected. See figures in [20] and [33].

The figure also illustrates a clear difference between the kfsm sets for
bimodal circle maps and circular orbits for $d_{n}$-one. Specifically, the
kfsm sets correspond to a specific subclass of circular orbits for $d_{2k}$.
On the other hand, there is clearly a tight relationship between the theories
which needs to be investigated. Perhaps the degree reduction process described
in [7, 33] would be a good place to start.

## References

  * [1] Lluís Alsedà, Jaume Llibre, and MichałMisiurewicz, _Combinatorial dynamics and entropy in dimension one_ , second ed., Advanced Series in Nonlinear Dynamics, vol. 5, World Scientific Publishing Co., Inc., River Edge, NJ, 2000. MR 1807264
  * [2] P. Arnoux, _Sturmian sequences_ , Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Math., vol. 1794, Springer, Berlin, 2002, pp. 143–198. MR 1970391
  * [3] Joseph Auslander, _Minimal flows and their extensions_ , North-Holland Mathematics Studies, vol. 153, North-Holland Publishing Co., Amsterdam, 1988, Notas de Matemática [Mathematical Notes], 122. MR 956049
  * [4] Marcy Barge and Joe Martin, _The construction of global attractors_ , Proc. Amer. Math. Soc. 110 (1990), no. 2, 523–525. MR 1023342
  * [5] C. Bernhardt, _Rotation intervals of a class of endomorphisms of the circle_ , Proc. London Math. Soc. (3) 45 (1982), no. 2, 258–280. MR 670037
  * [6] Patrick Billingsley, _Convergence of probability measures_ , second ed., Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, 1999, A Wiley-Interscience Publication. MR 1700749
  * [7] Alexander Blokh, James M. Malaugh, John C. Mayer, Lex G. Oversteegen, and Daniel K. Parris, _Rotational subsets of the circle under $z^{d}$_, Topology Appl. 153 (2006), no. 10, 1540–1570. MR 2216120
  * [8] David Bowman, Ross Flek, and Greg Markowsky, _Rotation numbers and symbolic dynamics_ , Ann. Acad. Sci. Fenn. Math. 40 (2015), no. 1, 227–234. MR 3310081
  * [9] Philip Boyland, _Rotation sets and monotone periodic orbits for annulus homeomorphisms_ , Comment. Math. Helv. 67 (1992), no. 2, 203–213. MR 1161281
  * [10] by same author, _Weak disks of Denjoy minimal sets_ , Ergodic Theory Dynam. Systems 13 (1993), no. 4, 597–614. MR 1257024
  * [11] by same author, _Topological methods in surface dynamics_ , Topology Appl. 58 (1994), no. 3, 223–298. MR 1288300
  * [12] Philip Boyland, André de Carvalho, and Toby Hall, _Inverse limits as attractors in parameterized families_ , Bull. Lond. Math. Soc. 45 (2013), no. 5, 1075–1085. MR 3104999
  * [13] Philip L. Boyland, _Bifurcations of circle maps: Arnol’d tongues, bistability and rotation intervals_ , Comm. Math. Phys. 106 (1986), no. 3, 353–381. MR 859816
  * [14] M. Brown, _Some applications of an approximation theorem for inverse limits_ , Proc. Amer. Math. Soc. 11 (1960), 478–483. MR 0115157 (22 #5959)
  * [15] Karen M. Brucks and Henk Bruin, _Topics from one-dimensional dynamics_ , London Mathematical Society Student Texts, vol. 62, Cambridge University Press, Cambridge, 2004. MR 2080037
  * [16] Shaun Bullett and Pierrette Sentenac, _Ordered orbits of the shift, square roots, and the devil’s staircase_ , Math. Proc. Cambridge Philos. Soc. 115 (1994), no. 3, 451–481. MR 1269932
  * [17] Alain Chenciner, Jean-Marc Gambaudo, and Charles Tresser, _Une remarque sur la structure des endomorphismes de degré $1$ du cercle_, C. R. Acad. Sci. Paris Sér. I Math. 299 (1984), no. 5, 145–148. MR 756312
  * [18] Gustave Choquet, _Lectures on analysis. Vol. II: Representation theory_ , W. A. Benjamin, Inc., New York-Amsterdam, 1969, Edited by J. Marsden, T. Lance and S. Gelbart. MR 0250012
  * [19] Bráulio A. Garcia and Valentín Mendoza, _Non-monotone periodic orbits of a rotational horseshoe_ , Ergodic Theory Dynam. Systems 39 (2019), no. 7, 1870–1903. MR 3961679
  * [20] Lisa Goldberg and Charles Tresser, _Rotation orbits and the Farey tree_ , Ergodic Theory Dynam. Systems 16 (1996), no. 5, 1011–1029. MR 1417771
  * [21] Lisa R. Goldberg, _Fixed points of polynomial maps. I. Rotation subsets of the circles_ , Ann. Sci. École Norm. Sup. (4) 25 (1992), no. 6, 679–685. MR 1198093
  * [22] Christophe Golé, _Symplectic twist maps_ , Advanced Series in Nonlinear Dynamics, vol. 18, World Scientific Publishing Co., Inc., River Edge, NJ, 2001, Global variational techniques. MR 1992005
  * [23] Walter Helbig Gottschalk and Gustav Arnold Hedlund, _Topological dynamics_ , American Mathematical Society Colloquium Publications, Vol. 36, American Mathematical Society, Providence, R.I., 1955. MR 0074810
  * [24] Kevin Hockett and Philip Holmes, _Josephson’s junction, annulus maps, Birkhoff attractors, horseshoes and rotation sets_ , Ergodic Theory Dynam. Systems 6 (1986), no. 2, 205–239. MR 857198
  * [25] by same author, _Bifurcation to badly ordered orbits in one-parameter families of circle maps, or angels fallen from the devil’s staircase_ , Proc. Amer. Math. Soc. 102 (1988), no. 4, 1031–1051. MR 934888
  * [26] by same author, _Bifurcation to rotating Cantor sets in maps of the circle_ , Nonlinearity 1 (1988), no. 4, 603–616. MR 967473
  * [27] Ryuichi Ito, _Rotation sets are closed_ , Math. Proc. Cambridge Philos. Soc. 89 (1981), no. 1, 107–111. MR 591976
  * [28] Leo P. Kadanoff, _Supercritical behavior of an ordered trajectory_ , J. Statist. Phys. 31 (1983), no. 1, 1–27. MR 711468
  * [29] Anatole Katok and Boris Hasselblatt, _Introduction to the modern theory of dynamical systems_ , Encyclopedia of Mathematics and its Applications, vol. 54, Cambridge University Press, Cambridge, 1995, With a supplementary chapter by Katok and Leonardo Mendoza. MR 1326374
  * [30] Patrice Le Calvez, _Propriétés dynamiques des difféomorphismes de l’anneau et du tore_ , Astérisque (1991), no. 204, 131. MR 1183304
  * [31] Mark Levi, _Qualitative analysis of the periodically forced relaxation oscillations_ , Mem. Amer. Math. Soc. 32 (1981), no. 244, vi+147. MR 617687
  * [32] Robert MacKay and Jaroslav Stark, _Lectures on orbits of minimal action for area-preserving maps_ , Warwick Maths Institute preprint (1985 (corrected 1989)).
  * [33] James Martin Malaugh, _Rotational sets of the circle under z(d)_ , ProQuest LLC, Ann Arbor, MI, 2003, Thesis (Ph.D.)–The University of Alabama at Birmingham. MR 2705028
  * [34] Nelson G. Markley and Michael E. Paul, _Almost automorphic symbolic minimal sets without unique ergodicity_ , Israel J. Math. 34 (1979), no. 3, 259–272 (1980). MR 570885
  * [35] John N. Mather, _More Denjoy minimal sets for area preserving diffeomorphisms_ , Comment. Math. Helv. 60 (1985), no. 4, 508–557. MR 826870
  * [36] MichałMisiurewicz, _Rotation intervals for a class of maps of the real line into itself_ , Ergodic Theory Dynam. Systems 6 (1986), no. 1, 117–132. MR 837979
  * [37] Marston Morse and Gustav A. Hedlund, _Symbolic dynamics II. Sturmian trajectories_ , Amer. J. Math. 62 (1940), 1–42. MR 745
  * [38] S. Newhouse, J. Palis, and F. Takens, _Bifurcations and stability of families of diffeomorphisms_ , Inst. Hautes Études Sci. Publ. Math. (1983), no. 57, 5–71. MR 699057
  * [39] S. Ostlund, DA Rand, E Siggia, and J Sethna, _Supercritical behavior of an ordered trajectory_ , Physica D 8 (1983), no. 3, 303–342.
  * [40] Kamlesh Parwani, _Monotone periodic orbits for torus homeomorphisms_ , Proc. Amer. Math. Soc. 133 (2005), no. 6, 1677–1683. MR 2120254
  * [41] J. J. P. Veerman, _Irrational rotation numbers_ , Nonlinearity 2 (1989), no. 3, 419–428. MR 1005057
  * [42] Peter Veerman, _Symbolic dynamics and rotation numbers_ , Phys. A 134 (1986), no. 3, 543–576. MR 861742
  * [43] by same author, _Symbolic dynamics of order-preserving orbits_ , Phys. D 29 (1987), no. 1-2, 191–201. MR 923891
  * [44] Ya-Nan Wang and Wen-Xin Qin, _Many Denjoy minimal sets for monotone recurrence relations_ , Nonlinearity 27 (2014), no. 9, 2393–2408. MR 3266859