# Edit Probability for Scene Text Recognition

Fan Bai1 Zhanzhan Cheng2 Yi Niu2
Shiliang Pu2 Shuigeng Zhou1
1Shanghai Key Lab of Intelligent Information Processing, and School of
Computer Science, Fudan University, Shanghai 200433, China
2Hikvision Research Institute, China
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Fan Bai did most of this work
when he was an intern in Hikvision Research Institute.Corresponding author.

###### Abstract

We consider the scene text recognition problem under the attention-based
encoder-decoder framework, which is the state of the art. The existing methods
usually employ a frame-wise maximal likelihood loss to optimize the models.
When we train the model, the misalignment between the ground truth strings and
the attention’s output sequences of probability distribution, which is caused
by missing or superfluous characters, will confuse and mislead the training
process, and consequently make the training costly and degrade the recognition
accuracy. To handle this problem, we propose a novel method called edit
probability (EP) for scene text recognition. EP tries to effectively estimate
the probability of generating a string from the output sequence of probability
distribution conditioned on the input image, while considering the possible
occurrences of missing/superfluous characters. The advantage lies in that the
training process can focus on the missing, superfluous and unrecognized
characters, and thus the impact of the misalignment problem can be alleviated
or even overcome. We conduct extensive experiments on standard benchmarks,
including the IIIT-5K, Street View Text and ICDAR datasets. Experimental
results show that the EP can substantially boost scene text recognition
performance.

##  1 Introduction

Text recognition in natural scene images has recently attracted much research
interest of the computer vision community [18, 25, 31]. The sequence-learning-
based text recognition techniques, which have been advancing rapidly in recent
years [7, 25, 32], generally consist of an encoding module and a decoding
module. The encoding module usually encodes the input images to vectors of
fixed dimensionality with a certain encoding technique, such as convolution
neural network (CNN) [32], or recurrent neural network (RNN) including long
short-term memory (LSTM) [16, 31, 34] and gate recurrent neural network (GRU)
[4, 8, 32]. While the decoding module decodes the encoded feature vectors into
the target strings by exploiting RNN, connectionist temporal classification
(CTC) [12, 31] or attention mechanism [3, 5, 32] _etc_.

The state-of-the-art of scene text recognition is the attention-based encoder-
decoder framework [7, 25, 32]. It outputs a sequence of _probability
distribution_ (_pd_) that is expected to be aligned with the characters of the
text in the input image. In model training, the probability of the _ground-
truth text_ (_gt_ in short), calculated by the corresponding output _pd_
sequence in a frame-wise style, is utilized to estimate the likelihood of
model parameters. In this paper, we call this joint probability _frame-wise
probability_ (FP), and the existing frame-wise loss based methods _FP based
methods_ in the sequel.

However, in both the training and predicting processes of the attention-based
text recognition models, some characters may be missing or superfluous, which
results in misalignment between the _gt_ and the output sequence of _pd_. In a
recent work, Cheng _et al_. [7] considered this phenomenon as a result of
attention drift, and solved it by introducing the Focusing Attention Net
(FAN). This method achieved the state of the art performance. But the training
of FAN requires extra pixel-wise supervising information, which is expensive
to provide. And the training process is time-consuming due to the large amount
of pixel-wise calculation.

Fig. 1 provides examples to illustrate the phenomenon of missing and
superfluous characters in training an attention-based text recognition model
on the ground truth “DOVE#”. Here, ‘#’ represents the End-Of-Sequence (EOS)
symbol, which is commonly used in attention-based methods [7, 25, 32]. In Fig.
1 (a) and (b), the model may recognize the inputs as “DVE#” and “DOOVE#”
respectively, based on the output $pd$ sequences. Comparing against the $gt$
“DOVE#”, it is natural to say that the former misses an ‘O’ and the latter has
a superfluous ‘O’.

Figure 1: The illustration of misalignment between the output sequences of
_pd_ and the ground truth “DOVE#” due to (a) missing character and (b)
superfluous character. A cell with higher saturation corresponds to a
character with higher probability in the $pd$. The green _gt_ -characters at
the bottom of each subfigure have the highest probability in their _pd_ s
(linked by curves), while the red characters have lower probability in their
$pd$s. In subfigure (a), the left part shows that ‘O’, ‘V’ and ‘E’ have low
probability in their corresponding _pd_ s. The right part shows if an ‘O’ is
inserted, then ‘V’ and ‘E’ are alignable with the probabilities in their
$pd$s. Similarly, in subfigure (b), if an ’O’ is removed, then the remaining
‘O’, ‘V’, ‘E’ and ‘#’ have matched probabilities in their $pd$s.

By checking the training process of attention-based text recognition models,
we can see that the FP-based methods simply train the model by maximizing the
probability of each character in the _gt_ , based on the corresponding _pd_ of
the attention’s output sequence. However, the misalignments caused by missing
or superfluous characters may confuse and mislead the training process, and
consequently make the training costly and degrade the recognition accuracy.
Concretely, back to Fig. 1, except for ‘D’ and ‘#’, all the other three
characters ‘O’, ‘V’ and ‘E’ have low probability in the corresponding _pd_ s
(see the left diagrams), thus large error will be back-propagated to these
_pd_ s for further training. Instead, if the training algorithm realizes that
the character ‘O’ in Fig. 1 (a) is missing and one of the character ‘O’ in
Fig. 1 (b) is superfluous, it will align ‘V’ and ‘E’ in Fig. 1 (a), ‘V’, ‘E’,
and ‘#’ in Fig. 1 (b) to more appropriate _pd_ s (see the right diagrams), and
the characters will have higher probability under the new alignment, then it
needs only to focus on the missing/superfluous character ‘O’, which will make
the training simpler and less costly.

Motivated by the observation above and inspired by the concept of sequence
alignment where edit distance is used to measure the dissimilarity of two
sequences, in this paper we propose a new method for scene text recognition
under the attention-based encoder-decoder framework, which is called edit
probability (EP in short). By treating the misalignment between the $gt$ and
the output $pd$ sequence as the result of possible occurrences of
missing/superfluous characters, in the training process, EP tries to
effectively estimate the probability of a string conditioned on the output
sequence of _pd_ under certain model parameters while considering possible
occurrences of missing/superfluous characters. The merit lies in that the
training process can focus on the missing, superfluous and misclassified
characters, and the impact of misalignment can be reduced substantially. To
validate the proposed method, we conduct extensive experiments on several
benchmarks, which show that EP can significantly boost recognition
performance.

The rest of this paper is organized as follows: Section 2 reviews related
work, Section 3 presents the EP method in detail, Section 4 conducts empirical
evaluation, and Section 5 concludes the paper.

##  2 Related Work

In the past decade, many methods have been proposed for scene text
recognition, which roughly fall into three types: 1) traditional methods with
handcrafted features, 2) Naïve deep neural-network-based methods, and 3)
sequence-based methods.

In early years, traditional methods first extract handcrafted visual features
for individual character detection and recognition one by one, then integrate
these characters into words based on a set of heuristic rules or a language
model. Neumann and Matas [28] recognized characters by training a Support
Vector Machine (SVM) classifier with the defined handcrafted features such as
aspect ratio, hole area ratio etc. Wang _et al_. [35, 36] first trained a
character classifier with the extracted HOG descriptors [38], then recognized
characters of the cropped word image by a sliding window one by one. However,
due to the low representation capability of handcrafted features, these
methods cannot achieve satisfactory recognition performance.

Later, instead of handcrafted features, some deep neural-network-based methods
were developed for extracting robust visual features. Bissacco _et al_. [6]
adopted a fully connected network (FC) of 5 hidden layers for extracting
character features, then applied an n-gram language model to recognize
characters. Wang _et al_. [37] and Jaderberg _et al_. [19, 20] first developed
CNN-based framework for character feature representation, then applied some
heuristic rules for characters generation. These naïve deep neural-network-
based methods above usually recognized character sequence based on some
pre/post-processing, such as the segmentation of each character or a non-
maximum suppression, which may be very challenging because of the complicated
background and the inadequate distance between consecutive characters.

Recently, some researchers treated the text recognition task as a sequence
learning problem: first encoding a text image into a sequence of features with
deep neural network, then directly generating character sequence with sequence
recognition techniques. He _et al_. [15] and Shi  _et al_. [31] proposed the
end-to-end neural networks that first capture visual feature representation by
using CNN or RNN, then the CTC [12] loss was combined with the neural network
outputs for calculating the conditional probability between the predicted and
the target sequences. The state of the art for text recognition is the
attention-based methods [7, 25, 32]. These methods first combined CNN and RNN
for encoding text images into feature representations, then employed a frame-
wise loss to optimize the model. In the training process, the misalignment
between the $gt$ sequence and the output $pd$ sequence may mislead the
training algorithm and result in poor performance.

Note that the misalignment problem has also been observed in attention
training of speech recognition. Kim _et al_. tried to solve the problem by
using a joint CTC-attention model within the multi-task learning framework
[24]. However, as pointed in [7], the joint CTC-attention model does not work
well in scene text recognition. This paper also addresses the scene text
recognition problem under the attention-based framework. Different from the
existing methods, we propose a novel method EP that tries to estimate the
probability of a string conditioned on the input image, by treating the
misalignment between the $gt$ text and the output $pd$ sequence as the result
of possible occurrences of missing/superfluous characters. EP provides an
effective way to handle the misalignment problem, and empirically it
outperforms the existing methods.

##  3 The EP Method

In this section, we present the EP method in detail, including the EP-based
attention decoder, the formulation of EP, the EP training process, and EP
based prediction with/without a lexicon.

_Edit probability_ is proposed to effectively train attention-based models for
accurate scene text recognition. Conceptually, for an image $\mathcal{I}$ and
a text string $T$, $EP(T|\mathcal{I};\theta)$ measures the probability of $T$
conditioned on $\mathcal{I}$ under model parameters $\theta$. It is evaluated
by summing the probabilities of all possible edit paths that transform an
initially empty string to $T$ based on the _pd_ sequence $y$ generated by the
model. And each edit path consists of a sequence of edit operations that are
detailed in Sec. 3.2.

###  3.1 EP-based Attention Decoder

The original attention decoder is an RNN that generates the output _pd_
$y_{j}$ on the $j$-_th_ step [4]:

$\begin{array}[]{rcl}y_{j}&=&\operatorname{softmax}(v^{\top}s_{j}),\\\
s_{j}&=&\operatorname{LSTM}(y_{j-1},c_{j},s_{j-1}),\\\
c_{j}&=&\sum_{k^{\prime}=1}^{|h|}\alpha_{j,k}h_{k},\\\
\alpha_{j,k}&=&\dfrac{\exp(e_{j,k})}{\sum_{k^{\prime}=1}^{|h|}\exp(e_{j,k})},\\\
e_{j,k}&=&w^{\top}\tanh(Ws_{j-1}+Vh_{k}+b)\end{array}$ (1)

where $h$ is a sequence of encoded feature vectors, and $s_{j}$, $c_{j}$,
$\alpha_{j}$ and $e_{j}$ represent the LSTM [16] hidden state, the weighted
sum of $h$, the attention weights and the alignment model on the $j$-_th_
step, respectively. $w$, $W$, $V$, $b$ and $v$ are all trainable parameters.

In this work, for EP calculation, the attention decoder also generates $R_{j}$
and $I_{j}$ on the $j$-_th_ step:

$\begin{array}[]{rcl}R_{j}~{}~{}=~{}~{}(R_{j}^{C},R_{j}^{I},R_{j}^{D})^{\top}&=&\operatorname{softmax}(W_{R}^{\top}s_{j}),\\\
I_{j}&=&\operatorname{softmax}(W_{I}^{\top}s_{j})\end{array}$ (2)

where $W_{R}$ and $W_{I}$ are trainable parameters. $R_{j}^{C}$, $R_{j}^{I}$
and $R_{j}^{D}$ respectively represents the probability of $y_{j}$ being
correctly aligned, a character being missing before $y_{j}$ and $y_{j}$ being
superfluous. And $I_{j}$ is the _pd_ of characters being missing before
$y_{j}$ conditioned on $R_{j}^{I}$.

###  3.2 Edit Probability

Formally, with the alphabet (including the EOS) $\Sigma$, let
$T\in\mathbb{T}_{\Sigma}$ where $\mathbb{T}_{\Sigma}$ represents the set of
all valid strings (each of which contains one and only one EOS as its end
token) on $\Sigma$. We define the edit states as tuples $(T_{1:i},y_{1:j})$
for $0\leq i\leq|T|$ and $0\leq j\leq|y|$. And the state $(T_{1:i},y_{1:j})$
indicates generating $T_{1:i}$ from $y_{1:j}$. In particular, $T_{1:0}$ and
$y_{1:0}$ represent an empty string (also denoted by “”) and an empty _pd_
sequence respectively. The edit operations for state $(T_{1:i},y_{1:j})$ are
defined as follows:

  * •

_consumption_ : the consumption operation $\varepsilon^{C}_{i,j}$ transforms
state $(T_{1:i-1},y_{1:j-1})$ to state $(T_{1:i},y_{1:j})$ if $0<i\leq|T|$ and
$0<j\leq|y|$ by regarding the character $T_{i}$ and the _pd_ $A_{j}$ as being
correctly aligned, and appending $T_{i}$ to $T_{1:i-1}$ by consuming $y_{j}$.
Formally,

$\varepsilon^{C}_{i,j}(T_{1:i-1},y_{1:j-1})=(T_{1:i},y_{1:j})\text{.}$ (3)

The probability of this operation is the joint probability of doing
consumption and consuming $T_{i}$ of $y_{j}$. That is,

$p(\varepsilon^{C}_{i,j}|\mathcal{I};\theta)=R_{j}^{C}y_{j}(T_{i})\text{.}$
(4)

  * •

_deletion_ : the deletion operation $\varepsilon^{D}_{i,j}$ transforms state
$(T_{1:i},y_{1:j-1})$ to state $(T_{1:i},y_{1:j})$ if $0<j\leq|y|$ by
regarding the _pd_ $y_{j}$ as being superfluous, and deleting $y_{j}$
directly. Formally,

$\varepsilon^{D}_{i,j}(T_{1:i},y_{1:j-1})=(T_{1:i},y_{1:j})\text{,}$ (5)

For $T_{i}\neq\text{`\\#'}$, the probability of this operation is $R_{j}^{D}$.
And for $T_{i}=\text{`\\#'}$, _deletion_ is the only allowed operation on
state $(T_{1:i},y_{1:j-1})$ as any character after the EOS is ignored. So we
have

$p(\varepsilon^{D}_{i,j}|\mathcal{I};\theta)=\left\\{\begin{array}[]{ll}R_{j}^{D}{}{}{}&\operatorname{if}T_{i}\neq\text{`\\#'}\text{,}\\\
1{}{}{}&\operatorname{if}T_{i}=\text{`\\#'}\text{.}\end{array}\right.$ (6)

  * •

_insertion_ : the insertion operation $\varepsilon^{I}_{i,j}$ transforms state
$(T_{1:i-1},y_{1:j})$ to state $(T_{1:i},y_{1:j})$ if $0<i\leq|T|$ by
regarding $T_{i}$ as a missing character, and appending $T_{i}$ to $T_{1:i-1}$
directly. Formally,

$\varepsilon^{I}_{i,j}(T_{1:i-1},y_{1:j})=(T_{1:i},y_{1:j})\text{.}$ (7)

For $j<|y|$, the probability of this operation is the joint probability of a
character is missed from the position just before $y_{j+1}$ and the missing
character is $T_{i+1}$. And for $j=|y|$, _insertion_ is the only allowed
operation over state $(T_{1:i-1},y_{1:|y|})$ as there is no more _pd_ to
delete or consume. So we have

$p(\varepsilon^{I}_{i,j}|\mathcal{I};\theta)=\left\\{\begin{array}[]{ll}R_{j}^{I}I_{j}(T_{i})&\operatorname{if}j<|y|\text{,}\\\
I_{j}(T_{i})&\operatorname{if}j=|y|\text{.}\end{array}\right.$ (8)

By assuming that the edit operations over $T$ and $y$ are conditional
independent, the probability of an edit path $E$ is the joint probability of
all the edit operations in $E$. That is,

$p(E|\mathcal{I};\theta)=\prod_{t=1}^{|E|}p(E_{t}|\mathcal{I};\theta),$ (9)

where $E_{t}$ refers to the $t$-_th_ edit operation in $E$. In particular, the
probability of an empty path is $1$.

The edit probability of states $(T_{1:i},y_{1:j})$ is evaluated by the sum of
all the conditional probabilities of edit paths
$E_{1:|E|}\in\mathbb{E}_{\Sigma}^{*}$ that transform $(\text{``''},y_{1:0})$
to $(T_{1:i},y_{1:j})$ where “” and $y_{1:0}$ represent an empty string and an
empty _pd_ sequence respectively. Formally,

$\operatorname{ep}(T_{1:i},y_{1:j})=\sum_{\begin{subarray}{c}E\in\mathbb{E}_{\Sigma}^{*}\\\
E(\text{``''},y_{1:0})=(T_{1:i},y_{1:j})\end{subarray}}p(E|\mathcal{I};\theta)$
(10)

where and $\mathbb{E}_{\Sigma}$ is the set of all edit operations over $T$ and
$y$. That is,

$\mathbb{E}_{\Sigma}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\varepsilon^{C}_{i,j},\varepsilon^{D}_{i,j},\varepsilon^{I}_{i,j}|0<i\leq|T|,0<j\leq|y|\\}\text{.}$
(11)

Figure 2: The illustration of edit probability calculation. The red filled
circle on the $i$-th row $j$-th column (count from 0) indicates the state
$(T_{1:i},y_{1:j})$, in which $T_{1:i}$ is the string prefix (as shown with
the green words) and $y_{1:j}$ is the prefix of the _pd_ sequence (as shown in
Fig. 1 (a)). Given the state $(T_{1:i},y_{1:j})$: 1) the horizontal arrow
below the state indicates the deletion operation $\varepsilon^{D}_{i,j}$; 2)
The vertical arrow right to the state indicates the insertion operation
$\varepsilon^{I}_{i,j}$; 3) The diagonal arrow right below the state indicates
the consumption operation $\varepsilon^{C}_{i,j}$. And the higher saturation
of a red filled circle or an arrow refers to the higher probability of the
state or the corresponding edit operation, vice versa. The edit path with the
highest probability is emphasized with bold arrows, which consumes $y_{1}$,
$y_{2}$, $y_{3}$ and $y_{4}$ to generate ‘D’, ‘V’, ‘E’ and ‘#’ respectively,
inserts an ‘O’ before $y_{2}$, and deletes $y_{5}$ and $y_{6}$.

However, enumerating all the possible edit paths is prohibitively expensive
(if not impossible) as the search space is too large. Fortunately, this can be
solved by dynamic programming based on the following equation inferred from
Eq. 9:

$p(\varepsilon\circ
E|\mathcal{I};\theta)=p(\varepsilon|\mathcal{I};\theta)p(E|\mathcal{I};\theta)\text{,}$
(12)

for $\varepsilon\in\mathbb{E}_{\Sigma}$ and $E\in\mathbb{E}_{\Sigma}^{*}$. And
$\circ$ represents the concatenation operator for edit operations and edit
paths, which is defined as follows:

$(\varepsilon\circ
E)(T_{1:i},y_{1:j})=E(\varepsilon(T_{1:i},y_{1:j}))\text{.}$ (13)

With Eq. 12, we can rewrite Eq. 10 as follows:

$\begin{array}[]{rl}&\operatorname{ep}(T_{1:i},y_{1:j})\\\
=&\left\\{\begin{array}[]{lr}\lx@intercol 1\hskip
96.73936pt\operatorname{if}i=0,j=0\hfil\lx@intercol\\\
p(\varepsilon^{D}_{i,j}|\mathcal{I};\theta)\operatorname{ep}(T_{1:i},y_{1:j-1})\delta_{j>0}&\text{otherwise}\\\
\lx@intercol~{}~{}+p(\varepsilon^{I}_{i,j}|\mathcal{I};\theta)\operatorname{ep}(T_{1:i-1},y_{1:j})\delta_{i>0}\hfil\lx@intercol\\\
\lx<EMAIL_ADDRESS>(14)

where the value of $\delta_{condition}$ is $1$ if the condition is met,
otherwise $0$. By recursively applying Eq. 14,
$\operatorname{EP}(T|\mathcal{I};\theta)=\operatorname{ep}(T,y)$ can be
calculated in $\operatorname{O}(|T|\cdot|y|)$.

Fig. 2 shows the EP calculation process for generating “DOVE#” from the
sequence of _pd_ displayed in Fig. 1 (a). We can see that the insertion
operation, which inserts an ‘O’ is contained in the maximal probable edit
path. This is an expected result.

###  3.3 EP Training

With the training set $\mathcal{X}$ that consists of pairs of image and _gt_
string, the EP training is to find $\hat{\theta}$ that minimizes the negative
log-likelihood over $\mathcal{X}$:

$\hat{\theta}=\arg\min_{\theta}-\sum_{(\mathcal{I},T)\in\mathcal{X}}\ln(\operatorname{EP}(T|\mathcal{I};\theta))$
(15)

The model can be optimized with standard back-propagation algorithm [30].

###  3.4 EP Predicting

EP Predicting is to find the string $\hat{T}$ that maximizes
$\operatorname{EP}(\hat{T}|\mathcal{I};\hat{\theta})$:

$\hat{T}=\arg\max_{T\in{\mathbb{T}_{\Sigma}}}\operatorname{EP}(T|\mathcal{I};\hat{\theta})\text{.}$
(16)

However, looking for the whole answer set ${\mathbb{T}_{\Sigma}}$ with Eq. 16
is extremely costly. Therefore, we develop two efficient sequence generation
mechanisms for both lexicon-free and lexicon-based prediction.

Predicting without lexicon. By deeply analyzing the prediction problem, we
find that in general, the string $\hat{T}$ that maximizes
$\operatorname{EP}(\hat{T}|\mathcal{I};\hat{\theta})$ is mostly a prefix
(ended by an EOS ‘#’) of the string $\mathcal{T}$ with the most probable edit
path that transforms $(\text{``''},y_{1:0})$ to $(\mathcal{T},y)$ where
$\text{`\\#'}\not\in\mathcal{T}$.

Therefore, we firstly find the string $\mathcal{T}$:

$\mathcal{T}=\arg\max_{{T}\in(\Sigma\backslash\\{\text{`\\#'}\\})^{*}}\max_{\begin{subarray}{c}E\in\mathbb{E}_{\Sigma}^{*}\\\
E(\text{``''},y_{1:0})=({T},y)\end{subarray}}p(E|\mathcal{I};\theta)$ (17)

where $\Sigma\backslash\\{\text{`\\#'}\\}$ represents the alphabet without the
EOS, then use all the prefixes of $\mathcal{T}$ (each ended by an EOS) as the
candidate set $\mathcal{B}$:

$\mathcal{B}=\\{\mathcal{T}_{1:i}\oplus\text{`\\#'}|0\leq
i\leq|\mathcal{T}|\\}$ (18)

where $\oplus$ represents the concatenation operator for two strings, finally
select the best $\hat{T}\in\mathcal{B}$ that maximizes
$\operatorname{ep}(\hat{T},A)$:

$\hat{T}=\arg\max_{{T}\in\mathcal{B}}\operatorname{EP}({T}|\mathcal{I};\hat{\theta})\text{.}$
(19)

Note that the edit path with the highest probability should not include an
insertion edit operation that inserts a non-EOS character, because we can
remove such insertions and get a new edit path whose conditional probability
is greater than the previous one.

Therefore, we can generate $\mathcal{T}$ by beginning with the state
$(\text{``''},y_{1:0})$ and performing the most probable deletion or
consumption operation (not considering any operation generating the EOS) at
each step, till a state $(\mathcal{T},y)$ is reached. Since all strings in
$\mathcal{B}$ share the common prefixes, we can compute all the
$\operatorname{ep}({T},y)$ for ${T}\in\mathcal{B}$ in
$O(|\mathcal{T}|\cdot|y|)$ time with Eq. 14.

Figure 3: The illustration of edit probability trie. The trie contains a
lexicon with three strings: “DOVE#”, “DO#” and “DAY#”. Each node represents a
prefix of one or more strings in the lexicon. Upper right to each node with
the prefix (say $S$) is a probability vector where the color saturation of the
$j$-_th_ element represents $\operatorname{ep}(S,y_{1:j})$ and $y$ is the
output sequence of _pd_. Higher color saturation means higher probability, and
vice versa.

Predicting with a lexicon. In constrained cases, we can enumerate the strings
in a lexicon $\mathcal{D}$, and find the most probable one. A tunable
parameter $\lambda$ is used to indicate how much we trust the lexicon
$\mathcal{D}$ since some target strings may be not contained in the lexicon.
Therefore, we actually assess all the possible strings in
$\mathcal{B}\cup\mathcal{D}$ by

$\hat{T}=\arg\max_{{T}\in\mathcal{B}\cup\mathcal{D}}\left\\{\begin{array}[]{lr}\lambda\operatorname{EP}({T}|\mathcal{I};\hat{\theta})&\operatorname{if}{T}\in\mathcal{D}\\\
(1-\lambda)\operatorname{EP}({T}|\mathcal{I};\hat{\theta})&\operatorname{if}{T}\not\in\mathcal{D}\end{array}\right.$
(20)

where $0.5\leq\lambda\leq 1$. The larger $\lambda$ is, the more we trust the
lexicon, and vice versa. Specifically, $\lambda=0.5$ means that the lexicon
can provide only some additional candidates that are treated equally to those
in $\mathcal{B}$, while $\lambda=1$ means that the generated strings are
guaranteed to appear in the lexicon $\mathcal{D}$.

However, with the growing of lexicon size, the above enumeration-based method
is extremely time-consuming. To tackle this problem, Shi _et al_. used a
prefix tree (Trie) [9, 32] to accelerate the search process since many strings
in the lexicon share common prefixes. In this work we develop a data structure
called edit probability Trie (EP-Trie), which is a variant of Trie with nodes
containing not only a prefix $S$, but also a vector indicating
$\operatorname{ep}(S,y_{1:j})$ for $0\leq j\leq|y|$. The vector of a node can
be computed from the vector of its parent in O($|y|$) time with Eq. 14. We
will demonstrate the effectiveness of EP-Trie in Sec. 4.5. Fig. 3 illustrates
EP-Trie.

Method | IIIT5k | SVT | IC03 | IC13 | IC15
---|---|---|---|---|---
50 | 1k | None | 50 | None | 50 | Full | None | None | None
ABBYY [35] | 24.3 | $-$ | $-$ | 35.0 | $-$ | 56.0 | 55.0 | $-$ | $-$ | $-$
Wang _et al_. [35] | $-$ | $-$ | $-$ | 57.0 | $-$ | 76.0 | 62.0 | $-$ | $-$ | $-$
Mishra _et al_. [13] | 64.1 | 57.5 | $-$ | 73.2 | $-$ | 81.8 | 67.8 | $-$ | $-$ | $-$
Wang _et al_. [37] | $-$ | $-$ | $-$ | 70.0 | $-$ | 90.0 | 84.0 | $-$ | $-$ | $-$
Goel _et al_. [10] | $-$ | $-$ | $-$ | 77.3 | $-$ | 89.7 | $-$ | $-$ | $-$ | $-$
Bissacco _et al_. [6] | $-$ | $-$ | $-$ | 90.4 | 78.0 | $-$ | $-$ | $-$ | 87.6 | $-$
Alsharif and Pineau [2] | $-$ | $-$ | $-$ | 74.3 | $-$ | 93.1 | 88.6 | $-$ | $-$ | $-$
Almazán _et al_. [1] | 91.2 | 82.1 | $-$ | 89.2 | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Yao _et al_. [38] | 80.2 | 69.3 | $-$ | 75.9 | $-$ | 88.5 | 80.3 | $-$ | $-$ | $-$
Rodríguez-Serrano _et al_. [29] | 76.1 | 57.4 | $-$ | 70.0 | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Jaderberg _et al_. [19] | $-$ | $-$ | $-$ | 86.1 | $-$ | 96.2 | 91.5 | $-$ | $-$ | $-$
Su and Lu [33] | $-$ | $-$ | $-$ | 83.0 | $-$ | 92.0 | 82.0 | $-$ | $-$ | $-$
Gordo [11] | 93.3 | 86.6 | $-$ | 91.8 | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Jaderberg _et al_. [20] | 97.1 | 92.7 | $-$ | 95.4 | 80.7 | 98.7 | 98.6 | 93.1 | 90.8 | $-$
Jaderberg _et al_. [19] | 95.5 | 89.6 | $-$ | 93.2 | 71.7 | 97.8 | 97.0 | 89.6 | 81.8 | $-$
Shi _et al_. [31] | 97.6 | 94.4 | 78.2 | 96.4 | 80.8 | 98.7 | 97.6 | 89.4 | 86.7 | $-$
Shi _et al_. [32] | 96.2 | 93.8 | 81.9 | 95.5 | 81.9 | 98.3 | 96.2 | 90.1 | 88.6 | $-$
Lee _et al_. [25] | 96.8 | 94.4 | 78.4 | 96.3 | 80.7 | 97.9 | 97.0 | 88.7 | 90.0 | $-$
Cheng _et al_. [7] | 99.3 | 97.5 | 87.4 | 97.1 | 85.9 | 99.2 | 97.3 | 94.2 | 93.3 | 70.6
Shi _et al_. (baseline) [32] | 96.5 | 92.8 | 79.7 | 96.1 | 81.5 | 97.8 | 96.4 | 88.7 | 87.5 | $-$
Cheng _et al_. (baseline) [7] | 98.9 | 96.8 | 83.7 | 95.7 | 82.2 | 98.5 | 96.7 | 91.5 | 89.4 | 63.3
Shi’s + EP (ours) | 99.1 | 97.3 | 85.0 | 96.3 | 86.2 | 98.4 | 97.0 | 93.7 | 93.0 | 68.1
Cheng’s + EP (ours) | 99.5 | 97.9 | 88.3 | 96.6 | 87.5 | 98.7 | 97.9 | 94.6 | 94.4 | 73.9
Table 1: Results of recognition accuracy on general benchmarks. “50” and “1k”
are lexicon sizes, “Full” indicates the combined lexicon of all images in the
benchmarks, and “None” means lexicon-free. The results of the baseline methods
are directly referenced from the “SRN only” and the “Baseline” in [32] and [7]
respectively.

##  4 Performance Evaluation

We conduct extensive experiments to validate the EP method on several general
recognition benchmarks under the attention framework. For a fair and
comprehensive comparison, we directly employ the structures of the state-of-
the-art works and replace their loss layers with EP. We first evaluate the
performance of the EP-based methods, and compare them with the existing
methods. Then we demonstrate the advantage of EP training over frame-wise loss
based training on some real training data. Finally, we evaluate our method
with the Hunspell 50k lexicon [17], and compare EP predicting methods with and
without lexicon.

Figure 4: The visual comparison of EP and FP on real training data. In each
subfigure, the characters shown in the 3rd raw are those having the largest
probability in the corresponding _pd_. A vector of probability is shown in the
4th row, where the red saturation of the $j$-_th_ element (labeled from $0$)
of the vector indicates the FP value of the first $j$ characters in the _gt_ ,
calculated by the first $j$ _pd_ s in the output sequence. A matrix of
probability is given in the 6th row, where the red saturation of the ($i$,
$j$) element of the matrix indicates the EP value of generating the first $i$
characters in the _gt_ from the first $j$ _pd_ s in the output sequence. In
subfigure (a) and (b), no misalignment occurs. The maximal possible edit path
appears on the diagonal line of the EP matrix because no insertion/deletion
operation is likely to be performed. In subfigure (c) and (d), some
misalignments occur because some characters are missing. The maximal possible
edit path appears below the diagonal line of the EP matrix because some
insertions are likely to be performed near by the places of the missing
characters. In subfigure (e) and (f), some misalignments occur because some
characters are superfluous. The maximal possible edit path appears to the
right of the diagonal line of the EP matrix because some deletions are likely
to be performed near by the places of the superfluous characters.

###  4.1 Datasets

IIIT 5K-Words [27] (IIIT5K) is a dataset collected from the Internet with 3000
cropped word images in its test set. For each of its images, a 50-word lexicon
and a 1k-word lexicon are specified, both of which contain the ground truth
words as well as other randomly picked words.

Street View Text [35] (SVT) is collected from the Google Street View. Its test
set consists of 647 word images, each of which is specified with a 50-word
lexicon.

ICDAR 2003 [26] (IC03) contains 251 scene images with text bounding boxes.
Each image is associated with a 50-word lexicon defined by Wang _et al_. [35].
A full lexicon that combines all lexicon words is also provided. For fair
comparison, as in [35], we discard the images containing non-alphanumeric
characters or have less than three characters. The resulting dataset contains
867 cropped images.

ICDAR 2013 [23] (IC13) is the successor of IC03, so most of its data are
inherited from IC03. It contains 1015 cropped text images, but no lexicon is
associated.

ICDAR 2015 [22] (IC15) contains 2077 cropped images. For fair comparison, we
discard the images containing non-alphanumeric characters, and eventually
obtain 1811 images in total. No lexicon is associated.

###  4.2 Implementation Details

Network Structure: The attention-based encoder-decoder framework is the-state-
of-the-art technique for text recognition, which consists of two major steps:
1) Obtaining visual feature representation with a CNN-based feature extractor,
such as 7-Conv-based by Shi _et al_. [32] and ResNet-based by Cheng _et al_.
[7]; 2) Generating the output sequence of probability distribution with the
attention model. In this work, we evaluate the proposed method by replacing
the FP-based training/predicting in Shi’s and Cheng’s structures with the EP-
based training/predicting.

Model Training: Our model is trained on 8-million synthetic data released by
Jaderberg  _et al_. [18] and 4-million synthetic data (excluding the images
that contain non-alphanumeric characters) cropped from 800-thousand images
released by Gupta _et al_. [14] by the ADADELTA [39] optimization method.

Running Environment: Our method is implemented under the Caffe framework [21].
In our implementation, most modules in our model can be GPU accelerated as the
CUDA backend is extensively used. All experiments are conducted on a
workstation equipped with an Intel Xeon(R) E5-2650 2.30GHz CPU, an NVIDIA
Tesla P40 GPU and 128GB RAM.

###  4.3 Comparison with Existing Methods

Tab. 1 shows the performance results of two EP-based methods, two FP-based
(baseline) methods and previous methods. With Shi’s and Cheng’s structures,
the EP-based methods significantly outperform the baseline methods on all
benchmarks. In comparison with the existing methods, we consider both
constrained and unconstrained cases. In the unconstrained cases, the EP-based
method (Cheng’s + EP) outperforms all existing methods; While in the
constrained cases, our method (Cheng’s + EP) performs better than all existing
methods on IIIT5K, and achieves comparable results to that of the method
proposed by Cheng _et al_. (FAN) [7] on SVT and IC03 datasets. However, it
should be pointed out that FAN is trained with both word-level and character-
level bounding box annotations, which is expensive and time consuming. On the
contrary, our method is trained with only word-level ground truth. We also
note that the method proposed by Jaderberg _et al_. [18] achieves the best
result on IC03 with the full lexicon, but it cannot recognize out-of-training-
set words.

###  4.4 Performance of EP Training

To demonstrate the advantage of EP in training stage, we compare the
calculation of the FP and the proposed EP on some real training data. The
input images, the ground truths and the recognition results are displayed in
the 1st, 2nd and 3rd rows in the upper part of Fig. 4, respectively. As for
the recognition results, they are actually the _pd_ sequences. For
demonstration convenience, we just display the characters that dominate the
corresponding _pd_.

For the FP calculation, we show a vector of probability for each image on the
4th row and the FP value on the 5th row in Fig. 4. The value of the $j$-_th_
element in the vector represents the joint conditional probability of
generating the first $j$ characters in _gt_ from the first $j$ _pd_ s in the
output $pd$ sequence, and the probabilities after the EOS are ignored
(regarded as $1$). We have the following observations on FP: 1) when the
output _pd_ sequence is well aligned to the _gt_ (see Fig. 4 (a) and (b)), the
FP declines only at the place where the character is misclassified; 2) when
the output _pd_ sequence is misaligned to the _gt_ (see Fig. 4 (c), (d), (e)
and (f)), the FP continues to decline after any occurrence of
missing/superfluous character even some characters are correctly recognized.
As a result, in the cases of misalignment, the error will be back-propagated
to the correctly recognized _pd_ s following the missing/superfluous
character, which may confuse the model training.

For the EP calculation, we display a matrix of probability for each image on
the 6th row and the EP values on the 7th row. The value of the ($i$, $j$)
element represents $\operatorname{ep}(T_{1:i},y_{1:j})$ where $T$ is the _gt_
and $y$ is the output sequence of _pd_ conditioned on the input image
$\mathcal{I}$. We have the following observations on EP: 1) When the output
sequence of _pd_ is well aligned to the _gt_ (see Fig. 4 (a) and (b)), no
matter whether the classification result is correct, the EP value is almost
equal to the FP value and the most probable edit path appears on the matrix
diagonal line, that is, generating every character in _gt_ by consuming the
corresponding _pd_ ; 2) When some characters are missing/superfluous (see Fig.
4 (c) and (d) for missing character cases, (e) and (f) for superfluous
character cases), the EP value is much larger than the FP value, and the most
probable edit path appears under or to the right of the matrix diagonal line
after the occurrence of the missing/superfluous characters. Different from the
FP, the EP is indicative of inserting/deleting the missing/superfluous
character and generating others by consuming the aligned _pd_. As a result, in
the cases of misalignment, much error will be back-propagated only to the
place where the missing/superfluous character occurs, and little error back-
propagated to the correctly recognized _pd_ s before or after the occurrence
of the missing/superfluous characters, which makes the model training process
focus on the missing/superfluous characters, instead of the misaligned
characters.

As EP-based methods theoretically require more calculation than baselines, we
measure the time cost for training. The result shows that Shi’s/Cheng’s
baselines cost 170.5ms/536.0ms per iteration, and EP based methods cost only
6.8ms/7.0ms more (batch size is set to 75).

###  4.5 Performance of EP Prediction

Figure 5: The accuracy on general recognition datasets when predict with the
Hunspell 50k lexicon and $\lambda$ varies from 0.5 to 1. The left and right
figures are the results of the Shi’s+EP method and Cheng’s+EP method,
respectively.

Here, we evaluate the performance of EP prediction with/without lexicon. In
real world text recognition tasks, it is not easy to get the ground-truth-
related lexicons. Therefore, following previous works [2, 19, 20, 31, 32], we
also test our methods on a public ground-truth-unrelated lexicon Hunspell
[17], which contains more than 50k words. As mentioned in Sec. 3.4, $\lambda$
is a tunable super-parameter in the predicting stage. We conduct lexicon-based
prediction on all datasets by varying $\lambda$ from $0.5$ to $1$. The results
are shown in Fig. 5. We can see that 1) the accuracy increases when $\lambda$
varies from $0.5$ to $0.98$, but decreases rapidly when $\lambda$ approaches 1
due to over-correction; 2) When $\lambda$ is set to $0.5$, the accuracy of
lexicon-based prediction is exactly the same as that of lexicon-free
prediction, which demonstrates the effectiveness of the proposed lexicon-free
prediction method; 3) The ground-truth-unrelated lexicon is also helpful for
improving text recognition performance if $\lambda$ falls in a proper range
(from $0.9$ to $0.98$), which validates the effectiveness of the lexicon-based
prediction method.

Besides, we also test the enumeration-based and EP-Trie-based methods in terms
of recognition accuracy and time cost per image while using the 50k lexicon.
Our experiments show that 1) the EP-Trie-based method predicts the same result
as the enumeration-based method’s, and 2) the former costs 0.11 second per
image while the latter costs 2.566 seconds per image, which demonstrates the
excellent efficiency of EP-Trie.

##  5 Conclusion

In this work, we propose a new method called edit probability for accurate
scene text recognition. The new method can effectively handle the misalignment
problem between the training text and the output probability distribution
sequence caused by missing or superfluous characters. We conduct extensive
experiments over several benchmarks to validate the proposed method, and
experimental results show that EP can significantly improve recognition
performance. In the future, we plan to apply the EP idea to machine
translation, speech recognition, image/video caption and other related tasks.

##  6 Acknowledgment

Fan Bai and Shuigeng Zhou were partially supported by the Science and
Technology Innovation Action Program of Science and Technology Commission of
Shanghai Municipality (STCSM) under grant No. 17511105204.

## References

  * [1] J. Almazán, A. Gordo, A. Fornés, and E. Valveny.  Word Spotting and Recognition with Embedded Attributes.  TPAMI, 36(12):2552–2566, 2014.
  * [2] O. Alsharif and J. Pineau.  End-to-end text recognition with hybrid hmm maxout models.  In ICLR, 2014.
  * [3] D. Bahdanau, K. Cho, and Y. Bengio.  Neural Machine Translation by Jointly Learning to Align and Translate.  In ICLR, 2015.
  * [4] D. Bahdanau, J. Chorowski, D. Serdyuk, Y. Bengio, et al.  End-to-end attention-based large vocabulary speech recognition.  In ICASSP, pages 4945–4949, 2016.
  * [5] D. Bahdanau, J. Chorowski, D. Serdyuk, P. Brakel, and Y. Bengio.  End-to-end attention-based large vocabulary speech recognition.  In ICASSP, pages 4945–4949, 2016.
  * [6] A. Bissacco, M. Cummins, Y. Netzer, and H. Neven.  PhotoOCR: Reading Text in Uncontrolled Conditions.  In ICCV, pages 785–792, 2013.
  * [7] Z. Cheng, F. Bai, Y. Xu, G. Zheng, S. Pu, and S. Zhou.  Focusing attention: Towards accurate text recognition in natural images.  In ICCV, pages 5076–5084, 2017.
  * [8] K. Cho, B. van Merrienboer, D. Bahdanau, and Y. Bengio.  On the properties of neural machine translation: Encoder-decoder approaches.  CoRR, abs/1409.1259, 2014.
  * [9] R. De La Briandais.  File searching using variable length keys.  In Western Joint Computer Conference, pages 295–298, 1959.
  * [10] V. Goel, A. Mishra, K. Alahari, and C. V. Jawahar.  Whole is Greater than Sum of Parts: Recognizing Scene Text Words.  In ICDAR, pages 398–402, 2013.
  * [11] A. Gordo.  Supervised mid-level features for word image representation.  In CVPR, pages 2956–2964, 2015.
  * [12] A. Graves, S. Fernández, F. Gomez, and J. Schmidhuber.  Connectionist temporal classification: Labelling unsegmented sequence data with recurrent neural networks.  In ICML, pages 369–376, 2006.
  * [13] A. Graves, A. r. Mohamed, and G. Hinton.  Speech recognition with deep recurrent neural networks.  In ICASSP, pages 6645–6649, 2013.
  * [14] A. Gupta, A. Vedaldi, and A. Zisserman.  Synthetic Data for Text Localisation in Natural Images.  In CVPR, pages 2315–2324, 2016.
  * [15] K. He, X. Zhang, S. Ren, and J. Sun.  Deep Residual Learning for Image Recognition.  In CVPR, pages 770–778, 2016.
  * [16] S. Hochreiter and J. Schmidhuber.  Long short-term memory.  Neural Computation, 9(8):1735–1780, 1997.
  * [17] Hunspell.  http://hunspell.github.io.
  * [18] M. Jaderberg, K. Simonyan, A. Vedaldi, and A. Zisserman.  Synthetic Data and Artificial Neural Networks for Natural Scene Text Recognition.  arXiv preprint arXiv:1406.2227, 2014.
  * [19] M. Jaderberg, K. Simonyan, A. Vedaldi, and A. Zisserman.  Deep Structured Output Learning for Unconstrained Text Recognition.  In ICLR, 2015.
  * [20] M. Jaderberg, K. Simonyan, A. Vedaldi, and A. Zisserman.  Reading Text in the Wild with Convolutional Neural Networks.  IJCV, 116(1):1–20, 2016.
  * [21] Y. Jia, E. Shelhamer, J. Donahue, S. Karayev, J. Long, R. Girshick, S. Guadarrama, and T. Darrell.  Caffe: Convolutional Architecture for Fast Feature Embedding.  In ACM MM, pages 675–678, 2014.
  * [22] D. Karatzas, L. Gomez-Bigorda, A. Nicolaou, S. Ghosh, A. Bagdanov, M. Iwamura, J. Matas, L. Neumann, V. R. Chandrasekhar, S. Lu, F. Shafait, S. Uchida, and E. Valveny.  ICDAR 2015 Competition on Robust Reading.  In ICDAR, pages 1156–1160, 2015.
  * [23] D. Karatzas, F. Shafait, S. Uchida, M. Iwamura, L. G. i. Bigorda, S. R. Mestre, J. Mas, D. F. Mota, J. A. Almazàn, and L. P. de las Heras.  ICDAR 2013 Robust Reading Competition.  In ICDAR, pages 1484–1493, 2013.
  * [24] S. Kim, T. Hori, and S. Watanabe.  Joint CTC-Attention based End-to-End Speech Recognition using Multi-task Learning.  In ICASSP, pages 4835–4839, 2017.
  * [25] C. Y. Lee and S. Osindero.  Recursive Recurrent Nets with Attention Modeling for OCR in the Wild.  In CVPR, pages 2231–2239, 2016.
  * [26] S. M. Lucas, A. Panaretos, L. Sosa, A. Tang, S. Wong, and R. Young.  ICDAR 2003 robust reading competitions.  In ICDAR, pages 682–687, 2003.
  * [27] A. Mishra, K. Alahari, and C. V. Jawahar.  Scene Text Recognition using Higher Order Language Priors.  In BMVC, pages 1–11, 2012.
  * [28] L. Neumann and J. Matas.  Real-time scene text localization and recognition.  In CVPR, pages 3538–3545, 2012.
  * [29] J. A. Rodriguez-Serrano, A. Gordo, and F. Perronnin.  Label Embedding: A Frugal Baseline for Text Recognition.  IJCV, 113(3):193–207, 2015.
  * [30] D. E. Rumelhart, G. E. Hinton, and R. J. Williams.  Learning representations by back-propagating errors.  Cognitive Modeling, 5(3):1, 1988.
  * [31] B. Shi, X. Bai, and C. Yao.  An End-to-End Trainable Neural Network for Image-Based Sequence Recognition and Its Application to Scene Text Recognition.  IEEE TPAMI, 39(11):2298–2304, 2017.
  * [32] B. Shi, X. Wang, P. Lyu, C. Yao, and X. Bai.  Robust Scene Text Recognition with Automatic Rectification.  In CVPR, pages 4168–4176, 2016.
  * [33] B. Su and S. Lu.  Accurate Scene Text Recognition Based on Recurrent Neural Network.  In ACCV, pages 35–48, 2015.
  * [34] I. Sutskever, O. Vinyals, and Q. V. Le.  Sequence to sequence learning with neural networks.  In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, NIPS, pages 3104–3112, 2014.
  * [35] K. Wang, B. Babenko, and S. Belongie.  End-to-end scene text recognition.  In ICCV, pages 1457–1464, 2011.
  * [36] K. Wang and S. Belongie.  Word Spotting in the Wild.  In ECCV, pages 591–604. Springer, 2010.
  * [37] T. Wang, D. J. Wu, A. Coates, and A. Y. Ng.  End-to-end text recognition with convolutional neural networks.  In ICPR, pages 3304–3308, 2012.
  * [38] C. Yao, X. Bai, B. Shi, and W. Liu.  Strokelets: A Learned Multi-scale Representation for Scene Text Recognition.  In CVPR, pages 4042–4049, 2014.
  * [39] M. D. Zeiler.  ADADELTA: An Adaptive Learning Rate Method.  CoRR, abs/1212.5701, 2012.


We also define $\tau'$ as the same as (<ref>) except that we replace $T_{\dt_1}$ therein with $n/4$.
Then, by introducing the notation $\PP^{\cA}$ to indicate the dependency on the algorithm $\cA$,

\begin{align}\label{eq:thethirdterm}
\begin{aligned}
&\PP^{\cA} \del{T_{\dt_1}\le \fr n4, \tau \neq \infty}
\\&\le \PP^{\cA'}\del{\tau' \neq \infty}
\\&= \PP^{\cA'}\del{\tau' \neq \infty,~ \chi_{i(\th)} \le \tau'}
+ \PP^{\cA'}\del{\tau' \neq \infty,~ \chi_{i(\th)} > \tau'}
\\&\stackrel{(a)}{\le} \PP^{\cA'}\del{a_{\chi_{i(\th)}} = i(\th),~ \chi_{i(\th)} \neq \infty,~ R_{1:(\chi_{i(\th)}-1)} = 0}
+ \PP^{\cA'}\del{\tau'\neq\infty,~ a_{\tau'} \neq i(\th),~ R_{\tau'} = 1}
\end{aligned}
\end{align}

where $(a)$ introduces the notation $R_{1:t} = 0$ for $R_i=0, \forall i\in[t]$.

Hereafter, we omit the dependence on $\cA'$ for brevity.
Denote by $T_j^{(n/4)}$ the number of pulls of arm $j$ up to (and including) time $n/4$.
The first term above is equal to

\begin{align*}
&\fr1n \sum_\th \PP_\th\del{a_{\chi_{i(\th)}} = i(\th),~ \chi_{i(\th)} \neq \infty,~ R_{1:(\chi_{i(\th)}-1)} = 0}
\\&= \fr1n \sum_\th \PP\del{a_{\chi_{i(\th)}} = i(\th),~ \chi_{i(\th)} \neq \infty,~ R_{1:(\chi_{i(\th)}-1)} = 0}
\tag{independence}
\\&= \fr1n \sum_{j=1}^n \PP\del{a_{\chi_{j}} = j,~ \chi_{j} \neq \infty,~ R_{1:(\chi_{j}-1)} = 0}
\tag{reindexing}
\\&\le \fr1n \sum_{j=1}^n \PP\del{T_j^{(n/4)} \ge 1}
% \\&\le \fr1n \sum_{j=1}^n \EE\sbr{ \one\cbr{T_j^{(n/4)} \ge 1}\cd T_j^{(n/4)}}
\\&\le \fr1n \sum_{j=1}^n \EE\sbr{T_j^{(n/4)}} \tag{Markov's inequality}
\\&= \fr1n \cd \fr{n}{4} = \fr14
\end{align*}

where the reasoning is mostly the same as the display (<ref>).

The second term of the display (<ref>) is equal to

\begin{align*}
&\fr1n \sum_\th \PP_\th \del{\tau'\neq\infty,~ a_{\tau'} \neq i(\th),~ R_{\tau'} = 1}
\\&=\fr1n \sum_\th \PP_\th \del{\exists t \le n/4: a_t \neq i(\th), R_t = 1, a_{1:t-1} \neq i(\th), R_{1:t-1}=0}
\\&\le \fr1n \sum_\th \sum_{t=1}^{n/4} \PP_\th \del{R_t = 1\mid a_t \neq i(\th), a_{1:t-1} \neq i(\th), R_{1:t-1}=0} \cd \PP_\th\del{ a_t \neq i(\th), a_{1:t-1} \neq i(\th), R_{1:t-1}=0 }
\\&\le \fr1n \sum_\th \sum_{t=1}^{n/4}  \dt_2 \cd 1
% \\&= \fr1n \sum_{j=1}^n \sum_{t=1}^{n/4}  \dt_2 \cd \PP\del{ a_t \neq j, a_{1:t-1} \neq j, R_{1:t-1}=0 }
\\&\le \dt_2 \cd \fr n 4~.
\end{align*}

Step 3: Putting it all together

Using the results of the previous two steps, we have that

\begin{align*}
\fr1n \sum_\th \P_\th(\mc{A} \text{ returns } i(\mathsf{q}(\th)))
&\ge  \left(1-\delta_2\right)^{n/4} \PP\del{ \cE_{\th} }
\\&\ge \left(1-\delta_2\right)^{n/4}\left(1 - \del{\dt_1 + \fr14 + \fr14 + \delta_2\cd \fr n 4}\right)
\\&\ge \left(1-\fr1{2n}\right)^{n/4} \fr18 \tag{$\dt_1<\fr 1 {16} < \fr14,~  \dt_2 \le \fr{1}{2n}$}
\\&\ge \frac{1}{16} \tag{$n \ge 20$}
\\&> \dt_1 \tag{assumption}
\end{align*}

However, we have by design that $i(\mathsf{q}(\theta)) \neq i(\theta)$.
As we have assumed that $\cA$ is $\delta_1$-PAC, we have the following contradiction, which concludes the proof:

\begin{align*}
\fr1n \sum_\th \P_\th(\mc{A} \text{ returns } i(\mathsf{q}(\th))) \leq \fr1n \sum_\th \delta_1 = \delta_1~.
\end{align*}

§.§.§ Comparison to Theorem <ref> on the same instances

The family of $\theta$'s is important to the statement of Theorems <ref> and <ref>. It captures the complexity of exploration for logistic bandits and rules out pathological algorithms that have knowledge of $\theta^\ast$. Otherwise, if we restrict to finding the best arm and fix a set $\mc{Z}$ and a single $\theta^\ast \in \Theta$ as defined in in Theorems  <ref> and <ref>,
then an oracle that knows $i(\theta^\ast)$ can put all of its samples on it. Indeed, the constraint on $\mc{Z}$ and $\theta \in \Theta$ imposed by Theorem <ref>
implies that $\mu(i(\theta)^T\theta) \geq 1-\delta_2$ and $\mu(z_j^T\theta) \leq \delta_2$ for all $z_j \neq i(\theta)$ and all $\theta\in \Theta$. Hence, for $\theta^\ast \in \Theta$, the set of alternates to $\theta^\ast$ for the bound given in Theorem <ref>
is $\Theta \backslash \{\theta^\ast\}$. For every $\theta'\in \Theta \backslash\{\theta^\ast\}$, $KL(\mu(i(\theta^\ast)^T\theta^\ast) || \mu(i(\theta^\ast)^T\theta') \geq KL(1-\delta_2 || \delta_2)) = \Omega(1)$. Therefore, the allocation

\begin{align*}
\lambda_a = \begin{cases}
1 & \text{ if } a = i(\theta^\ast)\\
0 & \text{ otherwise}
\end{cases}
\end{align*}

which puts all of the samples on arm $i(\theta^\ast)$ is feasible for the optimization in Theorem <ref>. However, this would imply a lower bound of $KL(1-\delta_2 || \delta_2)^{-1} \log(1/2.4\delta) = O(\log(1/\delta))$ independent of both the dimension and the number of arms. Naturally, this is pathological since the allocation depends on knowledge of $\i(\theta)$. In order to rule out such pathological instances, we consider a family of $\theta$'s.

§ COMMENTS ON

A diagram showing the dependency of the variables in SupCB-GLM of Li et al., 2017. The troublesome dependency is colored orange with thick lines. Note that we did not show all the dependencies here to avoid clutter. For example, $X_{\tau+1}$ depends on $X_1,\ldots,X_{\tau}$.

Li et al., 2017 collects the burn-in samples in a different way from our SupLogistic.
They collect burn-in samples (denoted by $\Phi$ here) for the first $\tau=\sqrt{dT}$ rounds, and the buckets $\Psi_1, \ldots, \Psi_S$ are empty at the beginning of time step $\tau+1$.
Then, at time $t>\tau$, when they compute the estimate $\th^{(s)}_t$, they use both the samples from $\Psi_s$ and $\Phi$.
However, we claim that this scheme invalidates the concentration inequality.
We explain below how this happens with the help of Figure <ref>.

* At time $\tau+1$, we choose $X_{\tau+1}$ in $s=1$ with step (a).

* At time $\tau+2$, we pass $s=1$ and then choose $X_{\tau+2}$ in $s=2$ with step (a). Note that the set of arms that has survived $s=1$ and passed onto $s=2$ are dependent on $\th^{(1)}_{\tau+1}$ that is a function of $y_1,\ldots, y_\tau$; see the orange thick line in Figure <ref>.

* At time $\tau+3$, we pass $s=1$, arrive at $s=2$ step (c), and we perform the arm rejections using $\th^{(2)}_{\tau+2}$.
At this point, the fixed design assumption of our concentration inequality for $\th^{(2)}_{\tau+2}$ is violated as we describe below.

Let $\tau=1$ for convenience.
The estimator $\theta^{(2)}_{3}$ is computed based on $\{X_1, X_3, y_1, y_3\}$, but $X_3$ depends on $y_1$.
That is, $y_1\mid X_1$ is not conditionally independent from $X_3$.

\begin{align*}
p(y_1,y_3\mid X_1,X_3) = \frac{p(y_1,y_3,X_1,X_3)}{p(X_1,X_3)} = \fr{p(y_3\mid X_3) p(y_1\mid X_1,X_3)p(X_1,X_3)}{p(X_1,X_3)} = p(y_3\mid X_3) p(y_1\mid X_1,X_3)
\end{align*}

where we use $p$ to denote both the PDF and PMF.
Note that $p(y_1\mid X_1,X_3) \neq p(y_1\mid X_1)$ in general; the distribution of $y_1\mid X_1, X_3$ is algorithm-dependent and thus hard to control.
To be clear, note that $p(y_1\mid X_1,X_3)$ must follow a Bernoulli distribution. It is just that we cannot guarantee that it has the mean $\mu(X_1^\T \th^*)$.

Our algorithm SupLogistic circumvents this issue by collecting burn-in samples for each bucket $\Psi_1,\ldots,\Psi_S$, but there is another challenge in dealing with the confidence width that depends on $\th^{(s)}_{t}$ due to our novel variance-dependent concentration inequality.

§ PROOFS FOR SUPLOGISTIC

While SupLogistic is inspired by the standard SupLinRel-type algorithms [Auer, 2002, Li et al., 2017], its design and analysis are challenging due to the fact that the confidence width scales with the unkonwn $\th^*$ unlike the standard linear bandit setting.
To get around this issue, we design the algorithm so that the mean estimate and the variance estimate are computed from different buckets – $\Psi_s(t-1)$ and $\Phi$ respectively.
Such a design was necessary (as far as we stick to the SupLinRel type) because using the confidence widths based on $\th^{(s)}_t$ would introduce a dependency issue similar to what we described in Section <ref> and invalidate our confidence bound.

While our regret bound improves upon the dependence on $\|\th^*\|$ in the leading term, we believe it should also be possible to incorporate recent developments of SupLinRel-type algorithms by Li et al., 2019 to shave off the logarithmic factors from $\log^{3/2}(T)$ to $\log^{1/2}(T)$.
The focus our paper is, however, to show the impact of our novel confidence bounds.

We first define our notations for the proof.

* We define a shorthand ${X_t} := x_{t,a_t}$ for the arm chosen at time step $t$.

* Denote by $\blue{\Psi_s(t)}$ the set of time steps at which the pulled arm $a_t$ was
included to the bucket $s$ up to (and including) time $t$.
In other words, $\Psi_s(t)$ is the variable $\Psi_s$ in the pseudocode of SupLogistic at the end of time step $t$.

* Define ${H^{(s)}_{t}(\th)} = \sum_{u\in \Psi_s(t)} \dmu(X_u^\T \th) X_u X_u^\T,
\forall s\in[S],$ and ${H^\Phi_{t}(\th)} := \sum_{u\in \Phi(\tau)} \dmu(X_u^\T \th) X_u
We remark that this definition depends on three variables: bucket index,
time step, and the parameter $\th$ for computing the variance $\dmu(X_u^\T \th)$.
Note that the bucket $\Phi$ is never updated after the time step $\tau$ and, so
we often use the notation $\Phi$ to mean $\Phi(\tau)$.

We present the proof by a bottom-up approach:

* Lemma <ref> set up the basic lemma concerned with $T_0$, the smallest budget for which we can enjoy a regret guarantee, and the key stochastic events that hold with high probability.

* Lemma <ref> analyzes the instantaneous regret.

* Lemma <ref> analyzes the cumulative regret per bucket $\Psi_s(T)$.

* Theorem <ref> analyzes the final cumulative regret.

Note that the proof of the final regret bound becomes a matter of invoking the Cauchy-Schwarz inequality and the elliptical potential lemma (Lemma <ref> below), which is standard in linear bandit analysis.

We first begin with the condition under which the algorithm collects enough burn-in samples and guarantees concentration of measure after time step $\tau$.

Fix $\delta>0$.
Consider SupLogistic with $T\ge d$, $\tau=\sqrt{dT}$, and $\alpha=3.5 \sqrt{\ln(2(2+\tau) \cd \fr{2STK}{\dt})}$.
Let $H^{(S+1)}_{t}(\th^*) := H^{\Phi}_{t}(\th^*)$.
Define the following event:

\begin{align}    \label{eq:event}
\begin{aligned}
{\cE_{\mathsf{mean}}} &:=
\Bigg\{
\forall t\in\cbr{\tau+1, \ldots, T}, a\in[K], s\in[S],~~ | x_{t,a}^\T\th^{(s)}_{t-1}  - x_{t,a}^\T\th^*| \le \alpha \|x_{t,a}\|_{(H^{(s)}_{t-1}(\th^*))^{-1}},
\\ &\hspace{15em}
\fr{1}{\sqrt{2.2}}\|x\|_{(H_{t-1}^{(s)}(\th^*))^{-1}}
\le \|x\|_{(H_{t-1}^{(s)}(\th_\Phi))^{-1}}
\le \sqrt{2.2} \|x\|_{(H_{t-1}^{(s)}(\th^*))^{-1}}
\Bigg\}
%            \\ \cE_{\mathsf{var}} &:=
%            \cbr{\forall x: \|x\|\le 1: | x^\T(\th_\Phi  - \th^*)| \le 1}
\\
{\cE_{\mathsf{diversity}}} &:= \cbr{\forall s\in[S+1], \lammin(H^{(s)}_{\tau}(\th^*)) \ge d + \ln\del{6(2+\tau)\cd \fr{2STK}{\dt}}} ~.
\end{aligned}
\end{align}

Then, there exists

\begin{align}\label{eq:T0}
T_0 = \Theta(Z\ln^4(Z)) \text{~~ where ~~} Z =\fr{d^3}{\kappa^2} + \fr{\ln^2(K/\dt)}{d\kappa^2}\cd
\end{align}

such that $\forall T \ge T_0$, $\PP(\cE_{\mathsf{mean}}, \cE_{\msf{diversity}}) \ge 1-\dt$.

To avoid clutter, let us fix $s$ and drop the superscript from $H^{(s)}_\tau(\th^*)$ and use $H_\tau(\th^*)$.
Note that each bucket has at least $\lfl\fr{\tau}{S+1}\rfl$ samples.
Since $\lammin(H_\tau(\th^*)) \ge \kappa \lammin(V_\tau)$ where ${V_\tau} = \sum_{u=1}^\tau X_u X_u^\T$, to ensure $\cE_{\mathsf{diversity}}$, it suffices to show that $\lammin(V_\tau) \ge \kappa^{-1}\del{d + \ln\del{6(2+\tau)\cd \fr{2STK}{\dt}}} =: \blue{F}$.
Recall our stochastic assumption on the context vectors ${x_{t,a}}$, the definition of $\Sigma$, and our assumption $\lammin(\Sigma)\ge\sig_0^2$.
By <cit.>, there exists $C_1,C_2>0$ such that if

\begin{align*}
\lt\lfl\fr{\tau}{S+1}\rt\rfl
%        \ge \fr{\tau}{S+1} - 1
%        = \fr{\sqrt{dT}}{S+1}  - 1
&\ge \del{\fr{C_1\sqrt{d} + C_2 \sqrt{\ln(2STK/\dt)}}{\sig_0^2}}^2 + \fr{2}{\sig_0^2} \cd F~,
%        \\&\ge \del{\fr{C_1\sqrt{d} + C_2 \sqrt{\ln(2STK/\dt)}}{\lammin(\Sigma)}}^2 + \fr{2}{\lammin(\Sigma)} \cd F~,
\end{align*}

then $\PP(\lammin(V) \ge F) \ge 1-\fr{\dt}{2STK}$.
Since $\tau = \sqrt{dT}$, we have $T$ in both LHS and RHS.
It remains to find the smallest $T$ that satisfies the inequality above.
Omitting the dependence on $\sig_0^2$, one can show that it suffices to find a sufficient condition for $T$ such that

\begin{align}\label{eq:suffcond-div}
T \ge \underbrace{\del{C_3 \cd \fr{d}{\kappa^2} + C_4\cd\fr{1}{d\kappa^2}\cd \ln^2(K/\dt)}}_{=:\blue{Z}}\ln^4(T)
\end{align}

for some absolute constants $C_3$ and $C_4$.
One can show that $T < Z \ln^4(T)$ implies $T < \Theta( Z\ln^4(Z))$ whose contraposition implies that there exists $T_0 = \Theta(Z\ln^4(Z))$ such that if $ T\ge T_0$, then (<ref>) is true, which in turn implies that $\PP(\cE_{\mathsf{diversity}}) \ge 1- \fr{\dt}{2STK} \cd (S+1)$ via union bound over $s\in[S+1]$.

When $\cE_{\mathsf{diversity}}$ is true, it is easy to see that the condition on $\nu_t$ in Theorem <ref> is satisfied if we substitute $\dt \larrow \dt/(2STK)$.
Thus, by the union bound,

\begin{align*}
\PP(\cE_{\mathsf{mean}} \mid \cE_{\msf{diversity}}) \ge 1- \fr{\dt}{2STK}\cd STK~.
\end{align*}

Note that $\PP(A\cup B) = \PP((A\cap \bar B) \cup B) \le \PP(A\cap \bar B) + \PP(B) \le  \PP(A\mid \bar B) + \PP(B)$.
Setting $A = \bar\cE_{\msf{mean}}$ and $B = \bar\cE_{\msf{diversity}}$, we have

\begin{align*}
\PP(\bar\cE_{\msf{mean}} \cup \bar\cE_{\msf{diversity}} ) \le \fr{\dt}{2STK}\cd STK + \fr{\dt}{2STK}(S+1) \le \dt
\end{align*}

where the last inequality is by $K\ge2$.

Take $\tau$ and $\alpha$ from Lemma <ref>.
Recall that $M=1/4$.
Suppose $\cE_{\msf{mean}}$.
Consider the time step $t\ge \tau+1$.
Let $s_t$ be the while loop counter $s$ at which the arm $a_t$ is chosen.

Let $a_t^* = \arg \max_{a\in[K]} \mu(x_{t,a}^\T \th^*)$ be the best arm at time $t$.
Then, the best arm $a_t^*$ survives through $s_t$, i.e., $a_t^* \in A_s$ for all $s \le s_t$.
Furthermore, we have

\begin{align*}
&\mu(x_{t,*}^\T \th^*) - \mu(x_{t,a_t}^\T \th^*) \\
\begin{cases}
\dot\mu(x_{t,a_t}^\T\th^*)8\cd2^{-s_t} + M\cd 64\cd2^{-2s_t} & \text{if $a_t$ is selected in step \textbf{(a)}}
\\ \dot\mu(x_{t,a_t}^\T\th^*)2T^{-1/2} + M\cd 4\cd T^{-1} & \text{if $a_t$ is selected in step \textbf{(b)}}
\end{cases}~.
\end{align*}

This proof is adapted from <cit.> while keeping the dependence on the variance $\dot\mu(x_{t,a_t}^\T \th^*)$ to avoid introducing $\kappa^{-1}$ explicitly.
Fix $t$.
To avoid clutter, let us omit the subscript $t$ from $\cbr{x_{t,a},a_t^*}$ and use $\cbr{x_a, a^*}$ instead, respectively.
We also drop the subscript $t-1$ from $H^{(s)}_{t-1}(\th)$.
Let us refer to the iteration index of the while loop as level.
We use the notation $m^{(s)}_a$ to denote $m_{t,a}$ at level $s$.

We prove the first part of the lemma by induction.
For the base case, we trivially have $a^* \in A_1$.
Suppose that $a^*$ has survived through the beginning of the $s$-th level (i.e., $a^* \in A_s$) where $s \le s_t-1$.
We want to prove $a^* \in A_{s+1}$.
Since the algorithm proceeds to level $s+1$, we know from step (a) at $s$-th level that, $\forall a\in A_s$,

\begin{align}\label{eq:induction}
|m_{a}^{(s)} - x_{a}^\T \th^*|
\le \alpha \|x_a\|_{(H^{(s)}(\th^*))^{-1}}
\le \alpha \sqrt{2.2} \|x_a\|_{(H^{(s)}(\th_\Phi))^{-1}} \le 2^{-s}
\end{align}

where both inequalities are due to $\cE_{\mathsf{mean}}$.
Specifically, it holds for $a=a^*$ because $a^* \in A_{s}$ by our induction step.
Then, the optimality of $a^*$ implies that, $\forall a\in A_s$,

\begin{align*}
\sr{\eqref{eq:induction}}{\ge} x_{a^*}^\T\th^* - 2^{-s}
\ge x_{a}^\T\th^* - 2^{-s}
\sr{\eqref{eq:induction}}{\ge} m_{a}^{(s)} - 2\cdot2^{-s} ~.
\end{align*}

Thus we have $a^* \in A_{s+1}$ according to step (c).

For the second part of the lemma, suppose $a_t$ is selected at level $s_t$ in step (a).
If $s_t=1$, obviously the lemma holds because $\mu(z) \in (0,1), \forall z$.
If $s_t>1$, since we have proved $a^* \in A_{s_t}$,
Eq. (<ref>) implies that for $a \in \cbr{a_t, a^*}$,

\begin{align*}
|m_{a}^{(s_t-1)} - x_{a}^\T\th^*| \le 2^{-s_t+1}~.
\end{align*}

Step (c) at level $s_t-1$ implies

\begin{align*}
m_{a^*}^{(s_t-1)} -  m_{a_t}^{(s_t-1)} \le 2\cdot 2^{-s_t+1} ~.
\end{align*}

Combining the two inequalities above, we get

\begin{align*}
x_{a_t}^\T\th^* \ge m_{a_t}^{(s_t-1)} - 2^{-s_t+1}
\ge m_{a^*}^{(s_t-1)} - 3\cdot 2^{-s_t+1} \ge x_{a^*}^\T\th^*- 4\cdot 2^{-s_t+1} ~.
\end{align*}

Recall that $M=1/4$ is an upper bound on $\ddot{\mu}(z)$.
The inequality above implies that, using Taylor's theorem,

\begin{align}\label{eq:reasoning}
\begin{aligned}
\mu(x_{a^*}^\T\th^*) - \mu(x_{a_t},\th^*)
&= \alpha(x_{a^*}^\T\th^*,x_{a_t}^\T\th^*) \cd (x_{a^*}-x_{a_t})^\T\th^*
\\&\le \alpha(x_{a^*}^\T\th^*,x_{a_t}^\T\th^*) \cd 4 \cd 2^{-s_t + 1}
\\&\le \del{\dot\mu(x_{a_t}^\T\th^*) + M\cd (x_{a^*}-x_{a_t})^\T\th^*} \cd 4 \cd 2^{-s_t + 1}
\\&= \dot\mu(x_{a_t}^\T\th^*)4 \cd 2^{-s_t + 1} + M\cd (4 \cd 2^{-s_t + 1})^2
\\&\le \dot\mu(x_{a_t}^\T\th^*)8\cd2^{-s_t} + M\cd 64\cd2^{-2s_t}~.
\end{aligned}
\end{align}

When $a_t$ is selected in step (b), since $m_{a_t}^{(s_t)} \ge m_{a^*}^{(s_t)}$, we have

\begin{align*}
x_{a_t}^\T\th^* \ge m_{a_t}^{(s_t)} - 1/\sqrt{T}
\ge m_{a^*}^{(s_t)} - 1/\sqrt{T} \ge x_{a^*}^\T\th^*- 2/\sqrt{T} ~.
\end{align*}

We now apply a similar reasoning as (<ref>), we have

\begin{align*}
\mu(x_{a^*}^\T\th^*) - \mu(x_{a_t}^\T\th^*)
\le \dot\mu(x_{a^*}^\T\th^*)2T^{-1/2} + M\cd 4\cd T^{-1}~.
\end{align*}

Assume $\cE_{\mathsf{mean}}$ and take $\alpha$ from Lemma <ref>. Recall that $L=1/4$.

Then, $\forall s\in[S]$,

\begin{align*}
\sum_{t\in \Psi_s(T)\sm[\tau]} \mu(x_{t,*}^\T \th^*) - \mu(X_t^\T\th^*)
\le 18\sqrt{L} \cd \alpha \sqrt{|\Psi_s(T)| d \ln(LT/d)} + \fr{320 M\alpha^2}{\kappa}d \ln(LT/d)~.
\end{align*}

By Lemma <ref> and the fact that $\mu(z) \in (0,1), \forall z$, we have

\begin{align*}
\sum_{t\in \Psi_s(T)} \mu(x_{t,*}^\T \th^*) - \mu(X_t^\T\th^*)
&\le \sum_{t\in \Psi_s(T)} 1\wedge \del{\dot\mu(X_t^\T\th^*) \cd 8 \cd 2^{-s} + 64 M\cd 2^{-2s}}
\\&\le \del{\sum_{t\in \Psi_s(T)} 1\wedge  \dot\mu(X_t^\T\th^*) \cd 8 \cd 2^{-s}} + \del{ \sum_{t\in \Psi_s(T)} 1 \wedge  64 M\cd 2^{-2s}}
\end{align*}

where the last inequality is true by $1 \wedge (a+b) \le 1 \wedge a + 1 \wedge b$.
For the first summation, we use $w_{t,a_t}^{(s)} > 2^{-s}$ due to step (a) of the algorithm:

\begin{align*}
\del{\sum_{t\in \Psi_s(T)} 1\wedge  \dot\mu(X_t^\T\th^*) \cd 8 \cd 2^{-s}}
&\le \sum_{t\in \Psi_s(T)} 1\wedge \dot\mu(X_t^\T\th^*) \cd 8 \cd w_{t,a_t}^{(s)}
\\&= \sum_{t\in \Psi_s(T)} 1\wedge \dot\mu(X_t^\T\th^*) \cd 8 \cd \alpha \sqrt{2.2} \|X_t\|_{(H^{(s)}_{t-1}(\th_\Phi) )^{-1}} \tag*{(Def'n of $w^{(s)}_{t,a_t}$)}
\\&\le \sum_{t\in \Psi_s(T)} 1\wedge \dot\mu(X_t^\T\th^*) \cd 18 \cd \alpha \|X_t\|_{(H^{(s)}_{t-1}(\th^*))^{-1}} \tag{$\cE_{\mathsf{mean}}$}
\\&\le \sum_{t\in \Psi_s(T)}  1\wedge 18\alpha\sqrt{L} \|\sqrt{\dot\mu(X_t^\T\th^*)} X_t\|_{(H^{(s)}_{t-1}(\th^*))^{-1}}
\tag*{($\because \sqrt{\dmu(X_t^\T\th^*)} \le \sqrt{L}$)}
\\&\sr{(a)}{\le} \sqrt{ |\Psi_s(T)| \sum_{t\in \Psi_s(T)} 1\wedge (18\alpha\sqrt{L})^2 \|\sqrt{\dot\mu(X_t^\T\th^*)} X_t\|^2_{(H^{(s)}_{t-1}(\th^*))^{-1}}}
\\&\sr{(b)}{\le} 18\alpha\sqrt{L} \sqrt{|\Psi_s(T)| \cd d\ln\del{LT/d}}
%    \\&\le  \cd d\ln\del{\fr{LT}{d\lammin(....)}}
\end{align*}

where $(a)$ by the Cauchy-Schwarz inequality and $(b)$ by Lemma <ref>, with the fact that $(18\alpha\sqrt{L})^2 \ge \fr12$, and  $\lammin(H_{\tau}(\th^*)) \ge 1$ ($\because \cE_{\mathsf{diversity}}$).

The second summation follows a similar derivation:

\begin{align*}
\sum_{t\in \Psi_s(T)} 1 \wedge 64M\cd 2^{-2s}
&\le \sum_{t\in \Psi_s(T)} 1 \wedge 64M\cd \alpha^2\cd 2.2\|X_t \|^2_{(H_{t-1}(\th_\Phi))^{-1}}
\\&\le \sum_{t\in \Psi_s(T)} 1 \wedge 64M\cd \alpha^2 \fr{\dot\mu(X_t^\T\th^*)}{\dot\mu(X_t^\T\th^*)} 5\|X_t \|^2_{(H_{t-1}(\th^*))^{-1}}
%    \\&\le \fr{64M}{\kappa}\sum_{t\in \Psi_s(T)} \alpha^2 \dot\mu(X_t^\T\th^*) \|X_t \|^2_{(H_t^*)^{-1}}
\\&\le \sum_{t\in \Psi_s(T)} 1\wedge \fr{64M \alpha^2}{\kappa}  5\cd \lt\|\sqrt{\dot\mu(X_t^\T\th^*)} X_t \rt\|^2_{(H_{t-1}(\th^*))^{-1}}
\\&\le \fr{320M\alpha^2}{\kappa}d\ln(LT/d)
\end{align*}

where $(a)$ is by Lemma <ref> and $\fr{320M\alpha^2}{\kappa} \ge 320M^2\alpha^2/L \ge 1/2$, and  $\lammin(H_{\tau}(\th^*)) \ge 1$.

Finally, we prove the regret bound of SupLogistic below.
Note that the statement here is slightly different from that of the main paper because we state the regret bound for large enough $T$ only.
This is only an aesthetic difference.
Indeed, assume that we have a regret bound $\mathsf{Reg}_T \le A\sqrt{T} + B$ for $T \ge C$.
Then, using $\Reg_T \le T$, we have $\Reg_T \le C$ for $T < C$.
This implies that, for all $T$, we have $\Reg_T \le A\sqrt{T} + B + C$.

Consider SupLogistic with $\tau$, $\alpha$, and $T_0$ from Lemma <ref>.
Then, if $T \ge T_0$, then

\begin{align*}
\mathsf{Reg}_T
&\le 10 \alpha\sqrt{dT\ln(T/d)\log_2(T)} + O\del{\fr{\alpha^2}{\kappa} d\cd
(\ln(T/d))\cd\ln T } ~.
\end{align*}

Recall that $\Psi_0$ contains the time step indices at which the choice $a_t$ happened in
Recall that we set $\tau=\sqrt{dT}$.
Let $\blue{\Delta_t} := \mu(x_{t,*}^\T \th^*) - \mu(x_{t,a_t}^\T \th^*)$.

\begin{align*}
&= \sum_{t=1}^{\tau} \Delta_t
+ \sum_{t=\tau+1}^{T} \Delta_t \\
&\le  \sqrt{dT} + \sum_{t \in \Psi_0(T)}  \Delta_t
+ \sum_{s=1}^{S}  \sum_{t \in \Psi_s(T)\sm[\tau]} \Delta_t~.
\end{align*}

For the first term, using Lemma <ref>,

\begin{align*}
\sum_{t \in \Psi_0(T)}  \Delta_t
\le T \cd \del{\dmu(X_t^\T\th^*) \cd \fr{2}{\sqrt{T}} + \fr{4M}{T}}
\le 2L\sqrt{T} + 4M~.
\end{align*}

For the second term, using Lemma <ref>, using the Cauchy-Schwarz inequality,

\begin{align*}
\sum_{s=1}^{S}  \sum_{t \in \Psi_s(T)\sm[\tau]} \Delta_t
&\le \sum_{s=1}^S \del{18\alpha \sqrt{L|\Psi_s(T)| d \ln(LT/d)} + \fr{320
M\alpha^2}{\kappa}d \ln(LT/d)}
\\&\le 18\alpha \sqrt{L d \ln(LT/d)} \sqrt{S\sum_{s=1}^S |\Psi_s(T)|} + S\cd\fr{320
M\alpha^2}{\kappa}d \ln(LT/d)
\\&\le 18\alpha \sqrt{L d \ln(LT/d) }\cd \sqrt{T\log_2(T)} + \log_2(T)\cd\fr{320
M\alpha^2}{\kappa}d \ln(LT/d)~.
\end{align*}

Using $L = 1/4$ and $\alpha \ge 7$, the terms involving $\sqrt{T}$ is: $\sqrt{dT} + 2L\sqrt{T} + 18\alpha \sqrt{L d
T\ln(LT/d)\log_2(T)} \le 10 \alpha\sqrt{dT\ln(T/d)\log_2(T)}$.
This concludes the proof.

§.§ Auxiliary Results

Let $s \in [S]$ and $F>0$. Then,

\begin{align*}
\sum_{t \in \Psi_s(T)} \min\cbr{1, F \| \sqrt{\dot\mu(X_t^\T\th^*)} X_t\|^2_{(H^*(\Psi_s(t-1)))^{-1}} }
\le (2F \vee 1) \cd d\ln\del{\fr{L |\Psi_s(T)|}{d \lammin(H^*(\Psi_s(\tau)))}}~.
\end{align*}

Using Lemma 3 of Jun et al., 2017, we have that $\forall q,x>0, \min\{q,x\} \le \max\cbr{2,q}\ln(1+x)$.

\begin{align*}
\min\cbr{1,  F\| \sqrt{\dot\mu(X_t^\T\th^*)} X_t\|^2_{(H^*(\Psi_s(t)))^{-1}} }
&=F\min\cbr{\fr1{F},~ \| \sqrt{\dot\mu(X_t^\T\th^*)} X_t\|^2_{(H^*(\Psi_s(t)))^{-1}} }
\\&\le F \cd \max\cbr{2,\fr{1}{F}} \ln\del{1 + \| \sqrt{\dot\mu(X_t^\T\th^*)} X_t\|^2_{(H^*(\Psi_s(t)))^{-1}}  }
\end{align*}

where the last inequality is by $\max\{2, 1/F\} = 2$.

\begin{align*}
\sum_{t \in \Psi_s(T)} \min\cbr{1, F \| \sqrt{\dot\mu(X_t^\T\th^*)} X_t\|^2_{(H^*(\Psi_s(t)))^{-1}} }
&\le (2F\vee1) \sum_{t \in \Psi_s(T)} \ln\del{1 + \| \sqrt{\dot\mu(X_t^\T\th^*)} X_t\|^2_{(H^*(\Psi_s(t)))^{-1}}  }
\\&= (2F\vee1) \ln\del{\fr{|H^*(\Psi_s(T))|}{|H^*(\Psi_s(\tau))|}}
\\&\le (2F\vee1) \cd d\ln\del{\fr{L|\Psi_s(T)|}{d \cd \lammin(H^*(\Psi_s(\tau)))}}
\end{align*}

where the last inequality is by the arithmetic-geometric mean inequality.

§ SOME ADDITIONAL EMPIRICAL INSIGHTS

In this section we dive a bit more into what RAGE-GLM is doing in its process of sampling. We utilized the Zappos pairwise comparison dataset [Yu & Grauman, 2014], focusing on the most “pointy” setting. As in the main text, we used the collected pairwise comparisons to learn $\theta^*$. We then sampled 10,000 shoes randomly from the set of 50,000 to be our $\mc{Z}$ set, and an additional randomly chosen 3,000 pairs of pairs of shoes from $\mc{Z}$ to be our $\mc{X}$ set (after being PCA-ed down to 25 dimensions). Given a query from the $x\in \cX$ set we then hallucinate the response using $\P(y = 1) = \mu(x^{\top}\theta^{\ast})$ according to the logistic model.

RAGE-GLM required roughly $5\times 10^6$ samples to complete. In the following figure, the top row shows the allocation of RAGE-GLM over $\cX$ (where we have sorted the elements of $\cX$ by the number of times each element was pulled). As we can see only a few hundred items received any pulls.

The top row is the allocation of samples over the pairs in $\cX$, the bottom row is the cosine similarity of these items with the difference.

Within a few tens of thousands of samples RAGE-GLM was able to narrow down to the top two different pair of shoes and then spent it's sampling budget differentiating between them. The second row of Figure <ref> shows the absolute value of the cosine similarity between the elements of $\cX$ and the difference between the top two pairs of shoes (we show a windowed average over 50 items to mitigate some spikes). As we can see, the most sampled items have higher average cosine similarity with the difference between the last two items. This has an interpretation in terms of analogies - the algorithm focuses on two pairs of shoes in $\cX$ whose difference is most aligned with that of the best two pairs of shoes $\mc{Z}$.

Most queried pairs of pairs of shoes.

In Figure <ref> we show the top two pairs of shoes along with the 10 pairs that were most queried (corresponding to the allocations above). Even though the pairwise comparisons shown may not be similar to those of the pointed shoes, asking them still gives us information about the difference between the best two, illuminating the advantage of the transductive setting.