# Beyond the Frontier: Predicting Unseen Walls from Occupancy Grids by
Learning from Floor Plans

Ludvig Ericson, Patric Jensfelt This work was supported by the Swedish
Research Council. All authors are with the Division of Robotics, Perception
and Learning at KTH Royal Institute of Technology, Stockholm, SE-10044,
Sweden. For e-mail correspondence, contact<EMAIL_ADDRESS>
###### Abstract

In this paper, we tackle the challenge of predicting the unseen walls of a
partially observed environment as a set of 2D line segments, conditioned on
occupancy grids integrated along the trajectory of a $None$ LIDAR sensor. A
dataset of such occupancy grids and their corresponding target wall segments
is collected by navigating a virtual robot between a set of randomly sampled
waypoints in a collection of office-scale floor plans from a university
campus. The line segment prediction task is formulated as an autoregressive
sequence prediction task, and an attention-based deep network is trained on
the dataset. The sequence-based autoregressive formulation is evaluated
through predicted information gain, as in frontier-based autonomous
exploration, demonstrating significant improvements over both non-predictive
estimation and convolution-based image prediction found in the literature.
Ablations on key components are evaluated, as well as sensor range and the
occupancy grid’s metric area. Finally, model generality is validated by
predicting walls in a novel floor plan reconstructed on-the-fly in a real-
world office environment.

###### Index Terms:

Deep Learning Methods, Planning under Uncertainty, Autonomous Agents, Learning
from Experience, Map-Predictive Exploration

##  I Introduction

Human and robotic problem-solving approaches differ in dealing with the
unknown and predicting the near future. Classical robotic approaches seek
exactness at the cost of intuition and foresight, and on the contrary, humans
do not meticulously maintain metric maps of their worlds. Even schematics and
blueprints, documents explicitly intended to specify technical details, leave
room for interpretation. Abstraction seems necessary for our ability to move
between the specifics of reality and the generality of ideas and ideals.
Replicating this ability to reason abstractly with explicit algorithms has
historically proven difficult, but recent advances in learning-based
approaches have opened up new avenues and great strides have been made across
many subfields of robotics.

In this work, floor plans are used as the medium through which abstract
reasoning is made possible. Floor plans are the architectural blueprints of
our built environment, a distillate of the real world as a tidy set of shapes
and symbols encoding the layouts and purposes of rooms, positions of walls,
doorways, and windows. Floor plans obey rules, symmetries, and regularities
that are impossible to state explicitly, often driven by aesthetic
considerations rather than logic. We have previously shown that recent
advances in autoregressive language models can be leveraged to produce a
generative model over floor plans as sequences of vector graphic instructions
[1]. By contrast to single-shot approaches such as [2, 3], an autoregressive
approach casts the floor plan generation task as a series of decisions and
their consequences, enabling the model to reason in steps, analogous to the
chain-of-thought paradigm in large language models [4].

Autonomous exploration planning is an obvious example of a classical robotics
problem where such a prediction model should be immediately applicable;
however, we have previously shown that traditional non-predictive exploration
planners are not well-suited to using predictions, and predictions can
actually have a negative impact on exploration performance [5]. In this
article, we have limited the scope to evaluating predictions by the primary
variable that they affect in the exploration context: _predicted information
gain_.

This paper is structured as follows. In Section IV, an model for predicting
floor plans from sensor history, dubbed _Floorist_ , is defined. Data modality
is the main difference from our previous model [1], which dealt solely with
abstract floor plans. Floorist is instead grounded in the real world by taking
a partially observed environment as input in the form of 2D occupancy grids
from a $None$ LIDAR sensor and predicting the unobserved walls of that
environment as line segments. In Section V, a dataset generation method is
outlined wherein a virtual robot navigates between randomly sampled waypoints
in a collection of annotated floor plans, generating input occupancy grids and
their target wall segments. In Section VI, cluster-based predicted information
gain is defined as in [6, 7], it is the evaluation metric used in this work,
suitable for occupancy grid-based prediction models. In Sections VII and VIII,
three prediction models are evaluated: Floorist, a baseline convolution-based
architecture as in [7, 3, 8, 9, 2], and a non-predictive approach as in [10].
Floorist performance under ablation of key components is also reported, as
well as its sensitivity to sensor range and occupancy grid area. Finally, in
Section VIII-D, Floorist is applied to an on-the-fly floor plan reconstruction
of a real-world office environment to validate its generality.

Figure 1: Three consecutive occupancy grids with  Unknown,  Free,  Occupied,
and  Window cells;  Predicted walls from a Floorist model;  Target walls; and
Trajectory. Initially (left), few lines match up exactly, apart from the
northern exterior wall which is visible, and the predicted rooms do exist
though not in the exact locations predicted. In the next step (middle), more
information about the corridor is observed, and the predicted segments are
also improved, though the adjoining rooms are still misaligned and their
doorways misplaced. Finally (right), the adjacent rooms are partially
observed, and the predicted doorway alignment is now correct, and both room’s
widths are correctly adjusted. The images have been cropped for legibility.

The dataset generation software along with training and inference code for
Floorist is published in tandem with this work under an open-source license at
lericson.se/floorist.

##  II Related Work

The approach of predicting the unknown from occupancy grids is perhaps most
common in the autonomous exploration literature. Autonomous exploration is the
task of reconstructing a map of an environment, typically with no prior
information about that particular environment, e.g., [6, 11, 12], though not
always [13]. In _frontier-based_ exploration planners, the planner considers
_frontiers_ by spatial clustering of the boundary between free and unknown
space. A score is assigned to each frontier, and the planner navigates to the
highest-scoring frontier. The score is typically a function of the travel
distance and the predicted information gain, an estimate of how many bits of
new information will be obtained by visiting that frontier. A popular
predictive approach, e.g., [2, 7, 3, 8, 9], is to derive training data
directly from autonomous exploration planning and then train some neural
network to predict a 2D occupancy grid, computing the predicted information
gain from the occupancy grid prediction. In sampling-based exploration
planners such as [10, 14, 15], path and exploration planning are performed
simultaneously with some variant of RRT [16]. Some sampling-based works
predict information gain directly by a regression formulation, with a deep
network [15] or a Gaussian process [14]. In [8], a reinforcement learning-
based approach is proposed paired with a convolutional network for occupancy
grid prediction; [9] extends the approach to a real-world exploration system
in the form of a micro-aerial vehicle.

Another line of inquiry is the explicit reconstruction of floor plans from
sensor data for architectural purposes, typically in an offline setting. In
[17, 18, 19] use an attention-based network to approach the task of predicting
a cohesive floor plan given a set of point clouds covering the entire
environment. [20] solve a similar task, though using sparse multi-views
instead of point clouds. Their approach is to model the environment
topologically before generating a floor plan suitable to those topological
constraints. In [21], the aim is somewhere between offline and online
prediction, posing the problem of inferring what is behind closed doors given
an occupancy grid of the observable parts of the environment, i.e., after
exploration is completed. The authors demonstrate favorable performance in
path planning tasks into unknown space, behind closed doors.

Some works concerning autonomous driving take a similar approach to ours in
representing and predicting the environment as a set of line segments with a
neural network [22, 23]. Emphasis is placed on reconstruction of the visible
environment as opposed to reasoning about the unknown, though many of the
technical challenges are similar. In the category of learning-based approaches
on vector graphics, the approach is typically to embed an entire graphic to
enable downstream tasks on that embedding, such as animation and interpolation
[24, 25].

In [26], a topological approach to modeling and reasoning about indoor
environnments is taken. It also introduces the _KTH floor plan dataset_ ,
which is used for synthesizing training data in the present work. It is a
collection of floor plans from a university campus, annotated with positions
of walls, doors, and windows.

##  III Notation

$\left\langle\cdot\right\rangle$ denotes expectation under some probability
distribution. $\left[\cdot\right]$ denotes the Iverson bracket, sometimes
called the indicator function. It maps the truth value of a proposition to one
or zero. $\left\langle\left[x=1\right]\right\rangle$ thus denotes the
probability that $x=1$. $\lfloor{x}\rfloor$ denotes the floor function, i.e.,
the greatest integer less than or equal to $x$.

##  IV Probabilistic Model

The problem of predicting floor plans is formulated as an autoregressive
prediction task on sequences of line segment vertices. The perspective is an
in-situ robot located at the origin having observed some part of its
surroundings, and the task is to predict the walls of the floor plan beyond
what has already been observed, as illustrated in Fig. 1. The floor plan is
represented as a matrix $\bm{S}\in\mathbb{R}^{N{\times}{}4}$ of the $N$ target
line segments from $(x{},y{})$ to $(x^{\prime}{},y^{\prime}{})$, i.e.,

$\bm{S}=\begin{pmatrix}x_{1}&y_{1}&x^{\prime}_{1}&y^{\prime}_{1}\\\
x_{2}&y_{2}&x^{\prime}_{2}&y^{\prime}_{2}\\\ \vdots&\vdots&\vdots&\vdots\\\
x_{\mathrm{N}}&y_{\mathrm{N}}&x^{\prime}_{\mathrm{N}}&y^{\prime}_{\mathrm{N}}\end{pmatrix}$
(1)

The vector graphic produced by $\bm{S}$ is invariant to row-wise permutations,
and vertex order reversal. However, in an autoregressive regime, order does
matter and must be chosen carefully for two reasons. First, any function that
models an ordered sequence must by necessity subsume the ordering algorithm.
Secondly, autoregression implies that later positions in the sequence are
informed by earlier positions. We use a proximity heuristic where the rows are
ordered by the distance from the robot to the nearest point on each line
segment, as in [1]. The intuition is that segments near the robot are often
partially observed, and can be predicted using the occupancy grid as
grounding. Later segments that are far away and ungrounded can then be chosen
to fit with the nearby grounded segments. For vertex order, a simple strategy
suffices. The vertices of each segment are ordered lexicographically, i.e.,

$(x{}<x^{\prime}{})\lor((x{}=x^{\prime}{})\land(y{}\leq y^{\prime}{}))$ (2)

###  IV-A Sequence Tokenization and Factorization

The line segment prediction problem is cast as a sequence prediction problem
on the _token sequence_ $\bm{t}$ where the joint distribution is conditioned
on some contextual input $C$, that is

$p(\bm{S}\mid C)=p(\bm{t}\mid C)$ (3)

The sequence $\bm{t}$ is initialized and terminated by a ‘start’ and ‘end’
token respectively, and otherwise consists of vertex pairs, each vertex is
quantized by $q:\mathbb{R}{\times}\mathbb{R}\to\mathcal{V}$ with the index set
$\mathcal{V}=\\{1,2,\ldots,HW\\}$ and

$q(x,y)=\lfloor{W(\tfrac{1}{2}H-s_{y}y)+(\tfrac{1}{2}W+s_{x}x)}\rfloor$ (4)

for some $H{\times}{}W$ grid at scale $s_{x},s_{y}$ in /. The function from
segments $\bm{S}$ to tokens $\bm{t}(\bm{S}){}\in\mathcal{T}^{2N+2}$ with the
token vocabulary
$\mathcal{T}=\\{\text{`{start}'}{},\text{`{end}'}{}\\}\cup\mathcal{V}$ is then
defined

$\displaystyle\bm{t}(\bm{S}){}=(\text{`{start}'}{},{}$ $\displaystyle
q(x_{1},y_{1}),q(x^{\prime}_{1},y^{\prime}_{1}),$ (5) $\displaystyle
q(x_{2},y_{2}),q(x^{\prime}_{2},y^{\prime}_{2}),\,\ldots$ $\displaystyle
q(x_{\mathrm{N}},y_{\mathrm{N}}),q(x^{\prime}_{\mathrm{N}},y^{\prime}_{\mathrm{N}}),\text{`{end}'}{})$

The joint probability is factorized autoregressively as in the recursion

$\displaystyle p(\bm{t}_{\left[j\leq{}i\right]}\mid C)$
$\displaystyle=p(t_{i}\mid\bm{t}_{\left[j<i\right]},C)\,p(\bm{t}_{\left[j<i\right]}\mid
C)$ (6) $\displaystyle p(\bm{t}_{\left[j\leq{}1\right]}\mid C)$
$\displaystyle=\left[t_{1}=\text{`{start}'}{}\right]$

where $t_{i}$ denotes the $i$th token, $\bm{t}_{\left[j<i\right]}$ and
$\bm{t}_{\left[j\leq{}i\right]}$ denote the subsequence of $\bm{t}$ up to but
excluding (or including) $i$. The next-token distribution is parameterized by
logits from a deep network $\bm{f}_{\theta}$, i.e.,

$p(t_{i}\mid\bm{t}_{\left[j<i\right]},C)=\sigma(\bm{f}_{\theta}(\bm{t}_{\left[j<i\right]},C))_{i}$
(7)

where $\sigma(\cdot)_{i}$ is the $i$th element of the normalized logistic
function. The function $\bm{f}_{\theta}$ assigns probability mass to the true
token sequence ${\hat{\bm{t}}}$ by gradient descent on $\left\langle
L\right\rangle$, the expected negative log likelihood under the data
distribution, with

$L_{\theta}({\hat{\bm{t}}},C)=-\sum_{{\hat{t}}_{i}\in{\hat{\bm{t}}}}\log\sigma(\bm{f}_{\theta}(\bm{{\hat{t}}}_{\left[j<i\right]},C))_{{\hat{t}}_{i}}$
(8)

###  IV-B Contextual Inputs

The contextual input $C$ consists of two parts: a partial occupancy grid
$\bm{M}\in\mathcal{C}^{H{\times}{}W}$, and the _visible line segments_
$\bm{S}(\bm{M})\in\mathbb{R}^{N{\times}{}4}$ recovered from the occupancy
grid. The cell labels are

$\mathcal{C}{}=\\{\text{`{unknown}'}{},\text{`{free}'}{},\text{`{occupied}'}{},\text{`{window}'}{}\\}$
(9)

The label ‘window’ indicates that a cell contains an _exterior window_ , i.e.,
a window facing outside the building, and hints the floor plan’s perimeter.
Marching squares [27] is used to find the visible line segments
$\bm{S}(\bm{M})$. In regions where at least one cell is marked ‘unknown’, no
line segment is produced.

###  IV-C Network Architecture

Occupancy Grid $\bm{M}$ $\mathcal{C}^{H{\times}{}W}$ ViT Image Encoder
$P{\times}{}E$ embeddings Segment Recovery $\mathcal{T}{}^{R}$ tokens Vertex
Embedding ${R}{\times}{E}$ embeddings Concat Rows Full $h$-way MHA Causal
$h$-way MHA Linear Layer ${\times}{}L$ Next-Token Distr.
$\sigma(\bm{f}_{\theta}(\cdot))$ Vertex Embedding Source Tokens
$\bm{t}_{\left[i<T\right]}$ Token Sequence $\bm{t}$ Synthesized
Dataset$K,V$$Q,K,V$$Q$Generation: sample next token and append to input Target
Tokens $\bm{t}_{\left[1<i\right]}$ Cross-Entropy Loss (Eq. 8) Training: target
and source tokens sampled from dataset

Figure 2: The Floorist network architecture with training and generation
pathways. In training, source and target token sequences are samples from the
dataset, where  Encoder blocks and  Decoder blocks are evaluated in one pass.
In generation, the source sequence starts as ‘start’ and the encoder side is
only evaluated once. The decoder is then evaluated to obtain the next-token
distribution, and a token is sampled from it and appended to the source
sequence before the process repeats again. $R=|\bm{t}(\bm{S}(\bm{M})){}|$ is
the number of tokens in the line segments visible in $\bm{M}$,
$T=|\bm{{\hat{t}}}|$ is the number of target tokens. $P$ is the number of
patches from ViT, $E$ is the embedding dimension, $Q,K,V$ are the query, key,
and value matrices for a multi-head attention (MHA) layer.
$\bm{t}_{\left[i<T\right]}$ denotes removal of the last token (i.e., ‘end’),
and $\bm{t}_{\left[1<i\right]}$ denotes removal of the first token (i.e.,
‘start’). This shifts the two sequences so that the target is always the next
token. Note that each attention block is a gated residual connection as in
[28].

Following success in the language modeling domain, the choice of $f_{\theta}$
in Eq. 7 is a transformer encoder-decoder with multi-head attention (MHA) as
in [29], illustrated in Fig. 2. The encoder is computed once per sequence to
encode the contextual input, while the decoder is iteratively re-evaluated
step-by-step during sampling as the generated sequence is constructed. Unlike
[29], each transformer layer is a residual layer with a gated residual as in
[28]. The two modalities of the contextual input are tokenized separately. The
occupancy grid $\bm{M}$ is encoded using a ViT network [30], and the tokenized
visible line segments $\bm{t}(\bm{S}(\bm{M}))$ are encoded with a discrete
embedding with absolute position encoding. The context tokens are concatenated
along the sequence dimension and cross-attended to.

####  IV-C1 Chromatization

Cell labels are mapped to 3-channel pseudo-colors by
$k{}:\mathcal{C}{}\to\mathbb{R}{}^{3}$ with

$\displaystyle k{}(\text{`{unknown}'}{})$
$\displaystyle={\left[{-}1;{-}1;{-}1\right]}$ $\displaystyle
k{}(\text{`{free}'}{})$ $\displaystyle={\left[{-}1;{+}1;{-}1\right]}$
$\displaystyle k{}(\text{`{occupied}'}{})$
$\displaystyle={\left[{-}1;{-}1;{+}1\right]}$ $\displaystyle
k{}(\text{`{window}'}{})$ $\displaystyle={\left[{+}1;{-}1;{+}1\right]}$

The exact choice of pseudo-colors is inconsequential as long as they are
unique.

####  IV-C2 Image Encoding

The chromatized image is fed through a ViT network that produces a set of
image tokens by considering the image as a set of non-overlapping patches
which are linearly projected to the embedding dimension $E$, and then fed
through a stack of self-attention layers. The ViT network is not pretrained.

####  IV-C3 Sequence Embedding

Each token value $t_{i}\in\mathcal{T}{}$ is mapped to a learnable embedding
vector, along with a learned absolute position embedding for each $i$. The two
embeddings are summed to form the final token embedding.

###  IV-D Image-Based Formulation

Our baseline is an image-based formulation as in [2, 3], where a chromatized
occupancy grid $\bm{k{}}(\bm{M})$ is the input and the target is a rasterized
image of the target line segments. The outputs are per-cell occupancy logits
$Y_{ij}{}$. At inference time, the occupancy state $O_{ij}{}$ is the maximum
likelihood estimate

$O_{ij}{}=\left[Y_{ij}{}({\bm{k{}}(\bm{M})})<0\right]$ (10)

Marching squares is used to recover the predicted line segments. The loss
function is per-pixel binary cross-entropy.

##  V Data Synthesis

Similar to our previous work, we derive training and test data from the KTH
floor plan dataset [26]. Each floor plan is represented as a set of rooms,
each room being a polygon of line segments categorized as walls, doors or
windows. For our purposes, only two boolean properties of the segment
categories are considered: _transparent_ and _passable_. Doors are assumed to
be open and so are both transparent and passable; windows are transparent but
impassable; and, walls are non-transparent and impassable. The segments are
collected into two sets, one with impassable segments used to generate paths
in the floor plan, and one with non-transparent segments used for simulating
sensor occlusions. Note that windows are not only exterior windows, but also
glass walls which are common in office environments such as the KTH floor plan
dataset.

Waypoints are first sampled by farthest point sampling [31] inside each floor
plan. Paths are then generated by Dijkstra’s algorithm [32] between every pair
of waypoints with a cost based on the truncated distance to the nearest wall,
so that some minimum wall clearance is maintained where possible. A virtual
sensor is then simulated along each path at a predefined step length, yielding
a partial occupancy grid at each step of the path built from the scans up to
that step by ray marching. Incident cells are first marked ‘free’, and the
terminal cells are then marked ‘occupied’ or ‘window’ if the ray is a _hit_ ,
i.e., terminated before the sensor’s maximum range. Each occupancy grid is
accompanied by its target line segments from the floor plan. The target
segments are filtered by removing subsegments that lie inside ‘occupied’
cells.

###  V-A Axis Alignment

The occupancy grid axes are automatically rotated to coincide with the visible
line segments, which adds invariance in the world-to-robot rotation up to an
integer multiple of $None$. Alignment also improves fidelity, as straight
lines in the environment are rotated to coincide with either the row or column
axis of the occupancy grid which minimizes discretization error, which is
important for recovering the visible line segments. Following [33], a
histogram is computed over the angle of the line passing through each pair of
neighboring LIDAR points, modulo $None$. The robot-to-surroundings rotation
$\alpha$ is then computed by an average of the histogram’s mode and the two
adjacent bins, weighted by frequency. Finally, the LIDAR scans and target line
segments are rotated by $-\alpha$ to align them to the occupancy grid axes
before the occupancy grid is rendered.

###  V-B Subdividing Segments

Subdividing segments serves to simplify the prediction problem by allowing
long segments to be predicted piece by piece. The subdivision algorithm must
be reproduced by the model function $f_{\theta}$, so it should be simple and
_predictable_. Furthermore, increasing the sequence by padding tokens improves
model performance [34, 35], suggesting that shorter segments should improve
performance, ceteris paribus. In practice, it becomes a compromise between
model performance versus inference speed and memory usage.

Our solution is to subdivide the segments by superimposing a 21x21 regular
grid and cutting the segments where they intersect this grid. The effect is
that from the model’s perspective, the segments are always subdivided at the
same predefined coordinates.

##  VI Predicted Information Gain

$\displaystyle{-2.5}$$\displaystyle{0.0}$$\displaystyle{2.5}$$\displaystyle{5.0}$$\displaystyle{-2}$$\displaystyle{0}$$\displaystyle{2}$$\displaystyle{4}$$\displaystyle{6}$(a)
Occupancy
Grid$\displaystyle{-2.5}$$\displaystyle{0.0}$$\displaystyle{2.5}$$\displaystyle{5.0}$(b)
Naive
[10]$\displaystyle\tilde{I}_{n}=\qty{2900}{}$$\displaystyle{-2.5}$$\displaystyle{0.0}$$\displaystyle{2.5}$$\displaystyle{5.0}$(c)
U-Net [2,
3]$\displaystyle\tilde{I}_{d}=\qty{2077}{}$$\displaystyle{-2.5}$$\displaystyle{0.0}$$\displaystyle{2.5}$$\displaystyle{5.0}$(d)
Floorist$\displaystyle\tilde{I}_{f}=\qty{1402}{}$$\displaystyle{-2.5}$$\displaystyle{0.0}$$\displaystyle{2.5}$$\displaystyle{5.0}$(e)
Ground Truth$\displaystyle\hat{I}=\qty{1307}{}$

Figure 3: Illustration of how information gain is computed for a  Frontier
location found along  Trajectory. The initial occupancy grid $\bm{M}$ is shown
in (a), while (b) to (e) show the occupancy grid $\bm{M}^{\prime}$ after a
simulated sensor scan in the predicted environment has been integrated into
$\bm{M}$, with  Information gain cells,  Sensor scan, and  Walls. Occupancy
grid colors as in Fig. 1. In (b), walls are extracted from (a), corresponding
to the typical way information gain is estimated for a frontier in non-
predictive autonomous exploration [10]. In (c), walls are predicted by a model
using (a) as input to a U-Net predictor as in [2, 3], and in (d) with the
method proposed in this paper. In (e), the ground truth walls are used. In
this example, the naive $\tilde{I}_{n}$, convolutional $\tilde{I}_{d}$, and
our approach $\tilde{I}_{f}$ differ from the ground truth ${\hat{I}}$ by
1593;770;95 (relative difference [list-units = repeat]122;58.9;7.26)
respectively.

Evaluating generative models is notoriously difficult as there is typically no
way to quantify the quality of novel generations, and the measure of quality
is often subjective. A common approach to this issue is to evaluate the
generation quality by measuring feature statistics from a different neural
network [36, 37]. As argued by [38], generative models are best evaluated by
an intended application, which in our case is to predict information gain in
frontier-based autonomous exploration. To define information gain, a
probabilistic interpretation must be made of the occupancy grid $\bm{M}$. For
this definition, independence between cells is assumed, and a categorical
probability distribution is defined for the label of each cell by

$p(M_{ij}{}=k)=\begin{cases}{{|\mathcal{C}|}{}}^{-1}&\text{if
}M_{ij}{}=\text{`{unknown}'}\\\
\left[M_{ij}{}=k\right]&\text{otherwise}\end{cases}$ (11)

If a cell is unknown, its label distribution is uniform, otherwise, the
distribution is an indicator function of the label, with
$M_{ij}{}\in\mathcal{C}$ as defined in Eq. 9. Let $\bm{M}^{\prime}{}$ denote
the occupancy grid $\bm{M}{}$ after sensor data integration at some frontier.
Information gained in $\bm{M}^{\prime}$ given $\bm{M}$ is then defined as

${I(\bm{M}^{\prime}{}\mid\bm{M}{})}=\sum_{ij,k}p(M^{\prime}_{ij}{}=k)\log\frac{p(M^{\prime}_{ij}{}=k)}{p(M_{ij}{}=k)}$
(12)

Notice that terms where $M_{ij}{}=M^{\prime}_{ij}{}$, or
$M^{\prime}_{ij}{}=\text{`{unknown}'}{}$, become zero. Assuming known cells in
$\bm{M}{}$ remain the same label, then the only non-zero terms will be those
where $M_{ij}{}$ is unknown and $M^{\prime}_{ij}{}$ is known. In other words,
Equation 12 is proportional to the number of unknown-turned-known cells, which
is the definition of information gain used in this and other works, e.g., [7].

Each occupancy grid cell is classified as either a frontier or non-frontier
based on its 4-connected neighbors. Specifically, a cell is deemed a frontier
cell if it is free, and amongst its four neighboring cells there exists both
free and unknown cells. Following this classification, the DBSCAN algorithm
[39] is used to group these frontier cells into frontier clusters. The
frontier location is the location of the cell closest to the average cell
location.

##  VII Experimental Setup

Since the KTH floor plan dataset represents rooms as closed polygons, there
are no connecting line segments where rooms connect, e.g., doorways, making it
possible to traverse and see inside the walls at these doorways. A heuristic
is used to insert wall segments in such situations: find a bijection from each
door segment $uv$ to its nearest door segment $u^{\prime}v^{\prime}$ and
insert two wall segments $uu^{\prime}$ and $vv^{\prime}$ so that a
quadrilateral is formed, if $\|uu^{\prime}\|+\|vv^{\prime}\|<\qty{2}{}$. After
this, each set of segments is canonicalized by first merging nearly identical
vertices (within 1), then joining overlapping line segments, and finally
removing vertices that are not corners; i.e., vertices $v$ with exactly two
neighbors $u,w$ that form a straight line $uw$ through $v$.

The generated paths are filtered by length and number of turns, only keeping
paths between [range-units = repeat]5100 long and having at least 3 turns. The
virtual sensor returns 720 points per scan, and a scan is obtained every 80 c
along the path. A cell is ‘window’ if a hit inside it is within 10 from the
nearest exterior window segment. A window segment is classified as exterior if
both its vertices are within some threshold distance (100) from the building
perimeter.

Frontier clusters with less than 3 are excluded from evaluation, as are those
whose center lies within 5 of the edge of the occupancy grid. Cluster larger
than 30 are divided into subclusters by k-means [40].

There are on average $75$ context line segments and $165$ target line segments
per sample in $6\,392\,919$ samples from $164$ floor plans. Each occupancy
grid represents a 15x15 area in 121x121. The vertex quantization function Eq.
4 is identical in scale and size to the occupancy grid, i.e.,
$\frac{H}{s_{y}}=\frac{W}{s_{x}}=\qty{15}{}$ and $H=W=121$. The maximum sensor
range is $r=\qty{4.5}{}$ unless otherwise stated.

###  VII-A KTH Dataset Considerations

It is important to note that the KTH floor plan dataset contains duplicated
floor plans, and that there are strong similarities between floors of a single
building. It would therefore be an error to simply shuffle the entire dataset,
as this would contaminate the training set with test data. As in [1], we
deduplicate the KTH floor plan dataset and split it into training and test
_before_ shuffling, and adjust the splitting point such that a single
building’s floor plans are all exclusively training or test data, preventing
any cross contamination.

###  VII-B Model Hyperparameters

In all experiments, the embedding dimension $E=$512$$. AdamW [41] is used with
weight decay ${10}^{-2}$, learning rate ${10}^{-4}$, and batch size 6. A 10
dropout is also applied. Since the dataset is large compared to the model
size, the network can be trained indefinitely without overfitting; training
was stopped when the validation loss stopped decreasing. The occupancy grids,
visible line segments, and target line segments are jittered by one of the
eight symmetries of the square, i.e., a random combination of mirroring and
rotating. Performance was not improved by relaxed regularization.

Top-$p$ sampling [42] is used for all generation, with $p=\qty{80}{}$. Other
choices of $p$ were evaluated but yielded worse results. No temperature
scaling or repetition penalty is applied.

##  VIII Experimental Results

In Fig. 4, examples of the generated wall segments are shown for six
continuous steps of randomly sampled trajectories in the test set. Frontier
locations used when evaluating predicted information gain are also shown.
Results from a model with larger area but same network size is also shown,
showing less coherent output, as the prediction task is harder; e.g., there
are segments passing through free space, a mistake that the smaller model does
not tend to make. Finally, results from the image-based predictor are also
presented, illustrating the difficulty in a pixel-wise approach to occupancy
regression.

###  VIII-A Predicted Information Gain

Predicted information gain is evaluated using the following different sets of
wall segments, illustrated in Fig. 3:

####  VIII-A1 Naive

Assume that only what has been observed to be occupied is occupied, i.e., no
segments are predicted and only the walls visible in the occupancy grid
occlude the sensor. This is a common approach in non-predictive exploration
planning [10], and is equivalent to assuming that unknown space can be
considered sensor transparent.

####  VIII-A2 U-Net

U-Net [43] is a fully-convolutional image segmentation network, chosen as a
baseline as it has been used in previous work on occupancy grid prediction for
autonomous exploration [2, 3]. The network was not pretrained. Several network
architectures were evaluated for image-based prediction [43, 44, 30, 45, 46,
8]. All architectures reached convergence at the same loss value, suggesting
that convergence is caused by the intrinsic difficulty of image-based
prediction.

####  VIII-A3 Floorist

A 121x121 vertex grid with $L=6$ attention layers, 8-way MHA, $4096$ GeLU
units, and $E=$512$$ embedding dimensions. The image encoder is a three-layer
ViT [30] with patch size 6 (i.e., $P=400$), 8-way MHA, and $4096$ hidden
units.

####  VIII-A4 Ground Truth

Using the actual walls of building, i.e., true information gain.

(a) Floorist 15x15

(b) U-Net [2, 3]

(c) Floorist 30x30

Figure 4: Examples of predictions on random samples from the test set. Each
row is a section of a single trajectory, in sequence from left to right.
Frontier locations used in the information gain evaluation are also shown.
Other conventions as in Fig. 3. Note that in (b), the predicted occupancy grid
is shown with  Occupied cells. It is advisable to use a digital document
viewer to zoom the vector graphics.

$\displaystyle{0}$$\displaystyle{500}$$\displaystyle{1000}$$\displaystyle{1500}$$\displaystyle{2000}$$\displaystyle{2500}$Error
$\displaystyle|d|$ in predicted information gain
(cells)0%25%50%75%100%$\displaystyle F(|d|)$

Figure 5: Cumulative distribution function $F$ of absolute error
$|d|=|\tilde{I}-{\hat{I}}|$ in predicted information gain $\tilde{I}$ from the
true information gain ${\hat{I}}$ using line segments from  Naive,  U-Net, and
Floorist. $N=$1\,464\,140$$.

In Fig. 5, the cumulative distribution function of absolute errors in
predicted information gain is presented for the three evaluation targets on
test data. Image-based prediction provides substantial improvements over naive
non-predictive estimation, and our sequence-based approach in turn provides
substantial improvements over image-based prediction. 95 confidence intervals
for the median absolute error (MAE) are $1195(2)452(1)236(1)$ cells. The
intervals are computed by bootstrapping with $1000$ trials. A _two-sample
Kolmogorov-Smirnoff test_ (KS) indicates whether a pair of CDFs differ
significantly by measuring the largest vertical gap. Image-based predictions
are significantly more accurate than naive estimation ($\Delta$MAE 745, KS
34.5), and Floorist predictions are in turn significantly more accurate than
image-based prediction ($\Delta$MAE 217, KS 16.2).

###  VIII-B Scale and Sensor Range

To assess the impact of scale, the information gain evaluation is performed on
a model with twice the area, 30x30. The occupancy grid size is limited by GPU
memory, and remains 121x121 cells. The resolution is therefore four times
lower (16.27/□ vs 65.07/□). The larger area resulted in 75 longer token
sequences, requiring significantly more GPU memory; batch size was therefore
reduced to 2. Information gain is evaluated as in Section VI, with two sensor
range settings: $r=\qty{4.5}{}$ and $r=\qty{9}{}$. To ensure the results are
comparable, information gain is computed at the base resolution. The MAE of
each model at each setting is reported in Table I, with the frequency of
overestimating and underestimating of the information gain. The first three
rows are the results reported in Section VIII-A. The performance of the
larger-scale model is slightly worse than the base model in the shorter range
setting ($\Delta$MAE 40). The large-scale model is significantly better than
the base model in the 9-meter case ($\Delta$MAE 679), because the longer
sensor range often reaches outside the 15x15 prediction area of the base
model, giving an overestimating effect similar to naive estimation. This is
reflected in the sharp increase in frequency of overestimation.

Table I: Evaluation of Scale and Sensor Range Range () | Area | Median () | Under (%) | Over (%)
---|---|---|---|---
$r$ | (^ 2 ) | $|\tilde{I}-{\hat{I}}|$ | $\langle[\tilde{I}<{\hat{I}}]\rangle$ | $\langle[\tilde{I}>{\hat{I}}]\rangle$
$4.5$ | Naive |  1195  1195 |  0.00  0.00 |  00.0  98.0
| U-Net |  1195  452 |  0.00  11.3 |  00.0  85.9
|  15x15 |  1195  236 |  0.00  28.5 |  00.0  66.5
|  30x30 |  1195  276 |  0.00  34.0 |  00.0  58.7
$9.0$ |  15x15 |  1195  1475 |  0.00  19.0 |  00.0  80.1
|  30x30 |  1195  796 |  0.00  31.5 |  00.0  66.0

###  VIII-C Model Ablations

Table II: Evaluation of Model Ablations on Test Set

Ablation | Loss (bits) | Accuracy (%)
---|---|---
| $\left\langle L\right\rangle$ | $\langle[{\hat{t}}={t^{*}}]\rangle$
Floorist 15x15 |  1.13  1.23 (+0.123) |  81.7  12.3 (-1.23)
No Window Labels |  1.17 (+0.043)  1.23 (+0.123) |  81.3 (-0.38)  12.3 (-1.23)
Shared Vertex Embedding |  1.20 (+0.065)  1.23 (+0.123) |  80.8 (-0.87)  12.3 (-1.23)
No Context Segments |  1.23 (+0.103)  1.23 (+0.123) |  80.1 (-1.55)  12.3 (-1.23)
No Image Encoder |  1.40 (+0.267)  1.23 (+0.123) |  78.1 (-3.54)  12.3 (-1.23)

Values in parentheses are relative to the first row. $L$ is defined as in Eq.
8, and ${t^{*}}$ is the maximum likelihood estimate.

We ablate some key components of our model and evaluate the impact on its
performance on the test set in terms of the loss and the accuracy of the
maximum likelihood estimate. The following ablations are reported in Table II:
‘window’ labels replaced by ‘occupied’ in training and test occupancy grids;
embedding weights of visible segments is shared with embedding weights of the
target segments; without visible segments as cross-attended tokens, i.e., only
using the occupancy grid as context; and, without the image encoder, i.e.,
only using visible segments as context. We see that each ablation degrades
performance, and that the occupancy grid context is most important. This may
be because the occupancy grid is the only volumetric representation of the
environment, and indicates where free versus unknown space is.

Window labels have the smallest impact on the reported metrics since windows
are relatively uncommon in the dataset. Window labels were included as a cue
for the building exterior, so the effect of those labels should be evaluated
by evaluating if they prevent the model from predicting walls outside the
building exterior. We specifically look at instances where at least one
occupancy grid cell has the ‘window’ label, and compute the length of
predicted line segments that fall outside the building perimeter as a
proportion of the total predicted segment length. Window labels reduced the
length of segments outside the building perimeter by 22.4, from 10.93 to 8.48,
indicating that the model does respond to the window cues.

###  VIII-D Reconstructed Floor Plans

The software library _RoomPlan_ [47] enables online reconstruction of floor
plans from real-world sensor data in cluttered environments. As a test of the
generality of our approach, we show that our method can use such
reconstructions. RoomPlan runs on a modern smartphone using an image sensor
and a solid-state LIDAR sensor, and produces a parametric 3D model of the
environment as a set of objects of some predefined types: walls, doors,
windows, and miscellaneous furniture. From this model, 2D line segments are
derived by the orthogonal projection of the walls and windows onto the ground
plane. A LIDAR sensor is simulated along the trajectory, and the floor plan is
predicted from the resulting occupancy grid. The reconstructed 2D floor plan,
the trajectory, and a wall prediction is shown Fig. 6. The model correctly
infers that there is a corridor outside, and that there is an adjoining room;
however, it predicts the room to be in the middle of the corridor, not the
end, as is the actual case.

$\displaystyle{-2}$$\displaystyle{0}$$\displaystyle{2}$$\displaystyle{-4}$$\displaystyle{-2}$$\displaystyle{0}$$\displaystyle{2}$$\displaystyle{4}$

$\displaystyle{-7.5}$$\displaystyle{-5.0}$$\displaystyle{-2.5}$$\displaystyle{0.0}$$\displaystyle{2.5}$$\displaystyle{5.0}$$\displaystyle{7.5}$$\displaystyle{-7.5}$$\displaystyle{-5.0}$$\displaystyle{-2.5}$$\displaystyle{0.0}$$\displaystyle{2.5}$$\displaystyle{5.0}$$\displaystyle{7.5}$Estimated
$\displaystyle\theta$: -35.95°

(a) (b) (c)

Figure 6: Illustration of (a) a reconstructed floor plan from [47], with
walls, a window, and furniture; (b) simulated  Trajectory inside the floor
plan derived from (a) with sensor scans; and (c) the axis-aligned occupancy
grid, and an example of  Predicted walls from Floorist.

##  IX Conclusion

In this work, we have presented an attention-based generative model for floor
plans conditioned on realistic sensor data. We have shown that our model can
cope with the high dimensionality of a time-dependent occupancy grid
representation with a realistic sensor model and make competent predictions as
quantified by evaluating the predicted information gain. The approach offers
advantages over traditional image-based predictions at the cost of longer
inference time, though autoregressive sampling performance is an active area
of research. We have also shown that the approach is robust enough to be used
in real-world environments, demonstrated by using an off-the-shelf floor plan
mapping solution as the source of floor plan data. In the future, we aim to
extend our real-world demonstration to create a real-time floor plan
prediction system from sensor data. Another interesting direction is
adversarial multi-agent contexts where intuiting the surrounding is important,
such as pursuit-evasion and other search games.

## References

  * [1] L. Ericson and P. Jensfelt, “FloorGenT: Generative vector graphic model of floor plans for robotics,” in _International Conference on Intelligent Robots and Systems_. IEEE, 2022.
  * [2] Y. Tao, Y. Wu, _et al._ , “SEER: Safe efficient exploration for aerial robots using learning to predict information gain,” in _International Conference on Robotics and Automation_. IEEE, 2023.
  * [3] K. Katyal, K. Popek, C. Paxton, P. Burlina, and G. D. Hager, “Uncertainty-aware occupancy map prediction using generative networks for robot navigation,” in _International Conference on Robotics and Automation_. IEEE, 2019.
  * [4] J. Wei, X. Wang, _et al._ , “Chain-of-Thought prompting elicits reasoning in large language models,” _Advances in Neural Information Processing Systems_ , vol. 35, 2022.
  * [5] L. Ericson, D. Duberg, and P. Jensfelt, “Understanding greediness in map-predictive exploration planning,” in _European Conference on Mobile Robots_. IEEE, 2021.
  * [6] B. Zhou, Y. Zhang, X. Chen, and S. Shen, “FUEL: Fast UAV exploration using incremental frontier structure and hierarchical planning,” _Robotics and Automation Letters_ , 2021.
  * [7] R. Shrestha, F.-P. Tian, W. Feng, P. Tan, and R. Vaughan, “Learned map prediction for enhanced mobile robot exploration,” in _International Conference on Robotics and Automation_. IEEE, 2019.
  * [8] E. Zwecher, E. Iceland, _et al._ , “Integrating deep reinforcement and supervised learning to expedite indoor mapping,” in _International Conference on Robotics and Automation_. IEEE, 2022.
  * [9] Y. Tao, E. Iceland, _et al._ , “Learning to explore indoor environments using autonomous micro aerial vehicles,” _arXiv 2309.06986_ , 2023.
  * [10] A. Bircher, M. Kamel, K. Alexis, H. Oleynikova, and R. Siegwart, “Receding horizon ”next-best-view” planner for 3D exploration,” in _International Conference on Robotics and Automation_. IEEE, 2016.
  * [11] D. Duberg and P. Jensfelt, “UFOExplorer: Fast and scalable sampling-based exploration with a graph-based planning structure,” _Robotics and Automation Letters_ , 2022.
  * [12] J. Yu, H. Shen, J. Xu, and T. Zhang, “ECHO: An efficient heuristic viewpoint determination method on frontier-based autonomous exploration for quadrotors,” _Robotics and Automation Letters_ , 2023.
  * [13] M. Luperto, M. Antonazzi, F. Amigoni, and N. A. Borghese, “Robot exploration of indoor environments using incomplete and inaccurate prior knowledge,” _Robotics and Autonomous Systems_ , 2020.
  * [14] M. Selin, M. Tiger, D. Duberg, F. Heintz, and P. Jensfelt, “Efficient autonomous exploration planning of large-scale 3D environments,” _Robotics and Automation Letters_ , 2019.
  * [15] L. Schmid, C. Ni, Y. Zhong, R. Siegwart, and O. Andersson, “Fast and compute-efficient sampling-based local exploration planning via distribution learning,” _Robotics and Automation Letters_ , 2022.
  * [16] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” _International Journal of Robotics Research_ , vol. 30, no. 7, 2011.
  * [17] Y. Yue, T. Kontogianni, K. Schindler, and F. Engelmann, “Connecting the dots: Floorplan reconstruction using two-level queries,” in _Conference on Computer Vision and Pattern Recognition_ , 2023.
  * [18] J.-W. Su, K.-Y. Tung, _et al._ , “SLIBO-Net: Floorplan reconstruction via slicing box representation with local geometry regularization,” in _Conference on Neural Information Processing Systems_ , 2023.
  * [19] J. Chen, Y. Qian, and Y. Furukawa, “HEAT: Holistic edge attention transformer for structured reconstruction,” in _Conference on Computer Vision and Pattern Recognition_. IEEE/CVF, 2022.
  * [20] A. Gueze, M. Ospici, D. Rohmer, and M.-P. Cani, “Floor plan reconstruction from sparse views: Combining graph neural network with constrained diffusion,” in _International Conference on Computer Vision_. IEEE/CVF, 2023.
  * [21] M. Luperto, F. Amadelli, M. Di Berardino, and F. Amigoni, “Mapping beyond what you can see: Predicting the layout of rooms behind closed doors,” _Robotics and Autonomous Systems_ , 2023.
  * [22] B. Liao, S. Chen, _et al._ , “MapTR: Structured modeling and learning for online vectorized HD map construction,” in _International Conference on Learning Representations_ , 2023.
  * [23] Q. Li, Y. Wang, _et al._ , “HDMapNet: An online hd map construction and evaluation framework,” _arXiv 2107.06307_ , 2021.
  * [24] A. Carlier, M. Danelljan, A. Alahi, and R. Timofte, “Deepsvg: A hierarchical generative network for vector graphics animation,” _Advances in Neural Information Processing Systems_ , 2020.
  * [25] P. Reddy, M. Gharbi, M. Lukac, and N. J. Mitra, “Im2Vec: Synthesizing vector graphics without vector supervision,” in _Conference on Computer Vision and Pattern Recognition_. IEEE, 2021.
  * [26] A. Aydemir, P. Jensfelt, and J. Folkesson, “What can we learn from $38\,000$ rooms? Reasoning about unexplored space in indoor environments,” in _Conference on Intelligent Robots and Systems_. IEEE, 2012.
  * [27] C. Maple, “Geometric design and space planning using the marching squares and marching cube algorithms,” in _International Conference on Geometric Modeling and Graphics_. IEEE, 2003.
  * [28] T. Bachlechner, B. P. Majumder, H. Mao, G. Cottrell, and J. McAuley, “ReZero is all you need: Fast convergence at large depth,” in _Uncertainty in Artificial Intelligence_. PMLR, 2021.
  * [29] A. Vaswani, N. Shazeer, _et al._ , “Attention is all you need,” in _Advances in Neural Information Processing Systems_. Curran Associates, Inc., 2017.
  * [30] A. Dosovitskiy, L. Beyer, _et al._ , “An image is worth 16x16 words: Transformers for image recognition at scale,” _arXiv 2010.11929_ , 2020.
  * [31] C. R. Qi, L. Yi, H. Su, and L. J. Guibas, “PointNet++: Deep hierarchical feature learning on point sets in a metric space,” _Advances in neural information processing systems_ , 2017.
  * [32] E. Dijkstra, “A note on two problems in connexion with graphs,” _Numerische Mathematik_ , 1959.
  * [33] G. Weiß, C. Wetzler, and E. Von Puttkamer, “Keeping track of position and orientation of moving indoor systems by correlation of range-finder scans,” in _International Conference on Intelligent Robots and Systems_ , vol. 1. IEEE, 1994.
  * [34] G. Weiss, Y. Goldberg, and E. Yahav, “Thinking like transformers,” in _International Conference on Machine Learning_. PMLR, 2021.
  * [35] S. Goyal, Z. Ji, _et al._ , “Think before you speak: Training language models with pause tokens,” _arXiv 2310.02226_ , 2023.
  * [36] T. Salimans, I. Goodfellow, _et al._ , “Improved techniques for training GANs,” _Advances in Neural Information Processing Systems_ , vol. 29, 2016\.
  * [37] K. Pillutla, S. Swayamdipta, R. Zellers, _et al._ , “Mauve: Measuring the gap between neural text and human text using divergence frontiers,” _Advances in Neural Information Processing Systems_ , 2021.
  * [38] S. Barratt and R. Sharma, “A note on the inception score,” _arXiv 1801.01973_ , 2018.
  * [39] M. Ester, H.-P. Kriegel, J. Sander, X. Xu, _et al._ , “A density-based algorithm for discovering clusters in large spatial databases with noise,” in _International Conference on Knowledge Discovery and Data Mining_ , vol. 96, no. 34. AAAI Press, 1996.
  * [40] J. MacQueen, “Some methods for classification and analysis of multivariate observations,” in _Symposium on Mathematical Statistics and Probability_ , vol. 1, no. 14. University of California Press, 1967.
  * [41] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _International Conference on Learning Representations_ , 2015.
  * [42] A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi, “The curious case of neural text degeneration,” in _International Conference on Learning Representations_. Curran Associates, Inc., 2019.
  * [43] O. Ronneberger, P. Fischer, and T. Brox, “U-Net: Convolutional networks for biomedical image segmentation,” in _International Conference on Medical Image Computing and Computer-Assisted Intervention_. Springer, 2015.
  * [44] Z. Liu, H. Mao, _et al._ , “A convnet for the 2020s,” in _Conference on Computer Vision and Pattern Recognition_. IEEE/CVF, 2022.
  * [45] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Conference on Computer Vision and Pattern Recognition_. IEEE/CVF, 2016.
  * [46] L.-C. Chen, G. Papandreou, F. Schroff, and H. Adam, “Rethinking atrous convolution for semantic image segmentation,” _arXiv 1706.05587_ , 2017.
  * [47] Apple Inc., “3D parametric room representation with RoomPlan,” 2022. [Online]. Available: https://machinelearning.apple.com/research/roomplan


# Posterior Probability Matters: Doubly-Adaptive Calibration for Neural
Predictions in Online Advertising

Penghui Wei  Alibaba GroupBeijingChina<EMAIL_ADDRESS>,  Weimin
Zhang  Alibaba GroupBeijingChina<EMAIL_ADDRESS>,  Ruijie Hou
Alibaba GroupBeijingChina<EMAIL_ADDRESS>,  Jinquan Liu  Alibaba
GroupBeijingChina<EMAIL_ADDRESS>,  Shaoguo Liu  Alibaba
GroupBeijingChina<EMAIL_ADDRESS>,  Liang Wang  Alibaba
GroupBeijingChina<EMAIL_ADDRESS>and  Bo Zheng  Alibaba
GroupBeijingChina<EMAIL_ADDRESS>
(2022)

###### Abstract.

Predicting user response probabilities is vital for ad ranking and bidding. We
hope that predictive models can produce accurate probabilistic predictions
that reflect true likelihoods. Calibration techniques aims to post-process
model predictions to posterior probabilities. Field-level calibration – which
performs calibration w.r.t. to a specific field value – is fine-grained and
more practical. In this paper we propose a doubly-adaptive approach AdaCalib.
It learns an isotonic function family to calibrate model predictions with the
guidance of posterior statistics, and field-adaptive mechanisms are designed
to ensure that the posterior is appropriate for the field value to be
calibrated. Experiments verify that AdaCalib achieves significant improvement
on calibration performance. It has been deployed online and beats previous
approach. 00footnotetext: Correspondence to: S. Liu. The first two authors
contributed equally.

response prediction, field-level calibration, adaptive mechanisms

††journalyear: 2022††copyright: acmcopyright††conference: Proceedings of the
45th International ACM SIGIR Conference on Research and Development in
Information Retrieval; July 11–15, 2022; Madrid, Spain.††booktitle:
Proceedings of the 45th International ACM SIGIR Conference on Research and
Development in Information Retrieval (SIGIR ’22), July 11–15, 2022, Madrid,
Spain††price: 15.00††isbn: 978-1-4503-8732-3/22/07††doi:
10.1145/3477495.3531911††ccs: Information systems Computational advertising

##  1\. Introduction

In online advertising systems, predicting user response probabilities, such as
click-through rate (CTR) and conversion rate (CVR), is the key for ranking
candidate ads and bidding strategies. Take cost-per-conversion (CPA) system as
an example, an ad’s expected revenue per thousand impressions (eCPM) is
computed by
$\mathrm{eCPM}=1000\cdot\hat{p}_{\mathrm{CTR}}\cdot\hat{p}_{\mathrm{CVR}}\cdot\mathrm{Bid}_{\mathrm{CPA}}$,
where $\mathrm{Bid}_{\mathrm{CPA}}$ denotes the bid price the advertiser is
willing to pay for one conversion.
$\hat{p}_{\mathrm{CTR}}$/$\hat{p}_{\mathrm{CVR}}$ denotes the predicted
CTR/CVR of the ad, produced by predictive models like logistic regression (He
et al., 2014) and deep neural networks (Covington et al., 2016; Cheng et al.,
2016).

In terms of bidding and charging, we expect that predicted probabilities
reflect true likelihoods: if the ad is displayed sufficiently many times and
its CTR is 0.02, the ideal situation is that the predicted value is near 0.02.
Inaccurate predictions (i.e., over- and under-estimation) will hurt user
experiences, prevent advertisers from achieving their marketing goals, and
affect the revenue of advertising platforms. Predictive models are typically
trained with binary labels, because for each displayed ad we can only observe
whether a response happens while we do not know the likelihood. Thus there is
a discrepancy between model predictions and true likelihoods. Existing studies
of predictive models focus more on ranking ability (Zhou et al., 2018; Ma et
al., 2018; Wei et al., 2021; Xu et al., 2022) and pay less attention to this.

To alleviate such discrepancy, calibration aims to post-process model
predictions to posterior probabilities (McMahan et al., 2013; Borisov et al.,
2018). Performing fine-grained calibration is more practical in real world
systems. By analyzing user response logs from our advertising system, we have
found that if we group the data to several subsets according to a specific
field (e.g., for a field “user activity”, each user belongs to one of values
{‘high’, ‘moderate’, ‘low’}, and we can group the data to three subsets), the
averaged response probability of each subset may be quite different. If the
calibration omits field information, this may result in underestimation for
one field value but overestimation for another one. Thus we focus on field-
level calibration, which learns a specific calibration function to each field
value (Pan et al., 2020).

In this paper we propose a doubly-adaptive approach AdaCalib for field-level
calibration. It learns a field-adaptive isotonic function family based on
binning, where each field value is associated with a specific function with
the guidance of posterior statistics. Besides, consider that different field
values’ frequencies (i.e., data sizes) may be distinct, while the reliability
of posterior statistics depends on data size, a field-adaptive binning
mechanism is proposed to dynamically determine the number of bins based on a
field value’s frequency information. AdaCalib can be integrated seamlessly
into neural predictive models for online serving, compared to traditional two-
stage (prediction then calibration) solution. The main contributions of this
paper are:

  * •

We propose AdaCalib for field-level calibration. It learns an isotonic
function family with the guidance of posterior statistics, and can be
integrated to neural predictive models.

  * •

Field-adaptive mechanisms (for function learning and binning strategy) are
designed to ensure that the learned calibration function is appropriate for
the specific field value.

  * •

Experiments on billion-size datasets verify that AdaCalib brings significant
improvement on calibration performance. It has been deployed online and beats
previous approach on core metrics.

##  2\. Prerequisites

Calibration is usually regarded as a post-process technique. Given predictive
models that produces un-calibrated scores, calibration aims at transforming
them to approximate posterior probabilities. We introduce representative
techniques, and describe their limitations for field-level calibration.

Binning-based approaches (Zadrozny and Elkan, 2001, 2002; Naeini et al., 2015)
rank all samples based on un-calibrated scores and partition them to bins.
Histogram Binning (Zadrozny and Elkan, 2001) takes the posterior probability
of a bin as the calibrated score to each sample in the bin. Isotonic
Regression (Zadrozny and Elkan, 2002) adjusts bin’s number and width to ensure
monotonicity, that is, if one sample’s un-calibrated score is higher than
another one, its calibrated score should be also higher. This is reasonable
for modern neural models (Covington et al., 2016) because their ranking
ability is usually impressive. These non-parametric approaches are effective
but lack of expressiveness.

Scaling-based approaches (Platt et al., 1999; Guo et al., 2017; Kull et al.,
2017; Kweon et al., 2022) learn parametric functions that map un-calibrated
scores to calibrated ones. They assume that probabilities are approximately
specific distributed, such as Gaussian distribution with same variance to
positive/negative class for Platt Scaling (Platt et al., 1999) and Gamma
distribution for Gamma Calibration (Kweon et al., 2022). The scaling function
is defined based on the assumption and is trained with the pairs of {un-
calibrated score, binary label}.

Hybrid approaches (Kumar et al., 2019; Pan et al., 2020; Deng et al., 2020;
Huang et al., 2022) borrow ideas from binning and scaling. For example,
Smoothed Isotonic Regression (Deng et al., 2020) integrates isotonic
regression and linear interpolation to a unified solution.

Most approaches only consider un-calibrated predictions as unique input for
calibration, which is unaware of field information. Neural Calibration (Pan et
al., 2020) puts forward the problem of field-level calibration by taking
sample’s features as the input. In this work, the field information (carried
by sample’s features) is used as an auxiliary module’s input to interpose the
final output, thus it is not directly involved in the computation of
calibration function.

##  3\. Problem Definition

Consider that we have trained a neural predictive model
$f_{\mathrm{uncalib}}(\cdot)$ on a training dataset
$\mathcal{D}_{\mathrm{train}}=\\{(x,y)\\}$, here $x$ denotes a sample’s
feature information (including user/item/context fields) and $y\in\\{0,1\\}$
denotes a sample’s binary response label:

(1) $\hat{p}=f_{\mathrm{uncalib}}(x)$

where $\hat{p}\in(0,1)$ is the prediction produced by a logistic function
$\sigma(\cdot)$. The model is un-calibrated: its output may not reflects true
likelihood because we cannot observe sample-wise likelihood.

For a field $\mathcal{Z}$ having multiple possible values
$\\{z_{1},z_{2},\ldots\\}$, field-level calibration is to learn a function
family $\mathcal{F}_{\mathrm{calib}}(\cdot;z)$, which post-processes the
prediction $\hat{p}$ to calibrated probability $\hat{p}_{\mathrm{calib}}$:

(2)
$\hat{p}_{\mathrm{calib}}=\mathcal{F}_{\mathrm{calib}}\left(\hat{p};z\right)\,,\text{where
the field $\mathcal{Z}$'s value of sample $x$ is $z$}\,.$

The goal is that $\hat{p}_{\mathrm{calib}}$ is close to the posterior
probability of samples having field value $z$.

The metric for evaluating calibration approaches is field-level relative
calibration error (Field-RCE):

(3) $\small\text{Field-
RCE}=\frac{1}{|\mathcal{D}|}\sum_{z\in\mathcal{Z}}\frac{\left|\
\sum_{(x^{(i)},y^{(i)})\in\mathcal{D}^{z}}\left(y^{(i)}-\hat{p}^{(i)}_{\mathrm{calib}}\right)\
\right|}{\frac{1}{|\mathcal{D}^{z}|}\sum_{(x^{(i)},y^{(i)})\in\mathcal{D}^{z}}y^{(i)}}$

where $\mathcal{D}=\left\\{(x^{(i)},y^{(i)})\right\\}_{i=1}^{|\mathcal{D}|}$
is the test dataset. The samples having field value $z$ construct a subset
$\mathcal{D}^{z}=\left\\{(x^{(i)},y^{(i)})\mid\ z^{(i)}=z\right\\}$. For the
dataset $\mathcal{D}^{z}$, Field-RCE evaluates the deviation level of each
sample’s calibrated probability $\hat{p}^{(i)}_{\mathrm{calib}}$. We can see
that the key of well-calibration at field-level is that, for a specific field
value $z\in\mathcal{Z}$, the calibration function should be adaptive to $z$
for producing an appropriate calibrated probability.

##  4\. Proposed Approach

We propose a doubly-adaptive approach AdaCalib that learns field-adaptive
calibration function for each field value with the guidance of posterior
statistics. AdaCalib is a hybrid approach, which takes the advantages of
monotonicity and posterior integration in binning-based solutions, as well as
the rich expressiveness in scaling-based solutions.

AdaCalib learns a field-adaptive isotonic (monotonical) function family via
binning-based posterior guidance, and each field value is associated with a
specific function for calibration. Moreover, consider that the reliability of
each bin’s posterior depends on the size of samples in the bin, a field-
adaptive binning mechanism is further proposed to dynamically determine the
number of bins.

###  4.1. Field-Adaptive Isotonic Function Family

####  4.1.1. Binning of Samples with Un-calibrated Predictions

Consider that we have trained a predictive model $f_{\mathrm{uncalib}}(\cdot)$
that produces prediction score $\hat{p}\in(0,1)$ for each sample. For the
dataset $\mathcal{D}_{\mathrm{dev}}=\\{(x^{(i)},y^{(i)})\\}$ that is used for
training calibration function, we employ the model
$f_{\mathrm{uncalib}}(\cdot)$ to produce un-calibrated predictions on each
sample, which is denoted as $\hat{p}^{(i)}$ for the $i$-th sample.

Given a field value $z$ of field $\mathcal{Z}$, to obtain the corresponding
posterior statistics based on
$\mathcal{D}_{\mathrm{dev}}\cup\mathcal{D}_{\mathrm{train}}$, we take all
samples whose field $\mathcal{Z}$’s value is equal to $z$, that is,
$\left\\{(x^{(i)},y^{(i)})\mid z^{(i)}=z\right\\}$. Based on these samples’
un-calibrated scores, we rank them in ascending order, and partition these
samples to $K$ equi-frequency bins: we compute $K+1$ bound values
$\left(b_{1}(z),b_{2}(z),\ldots,b_{K+1}(z)\right)$ where each bin contains
same size of samples. For a sample $x^{(i)}$ which has field value $z$, if its
un-calibrated score $\hat{p}^{(i)}$ meets the condition of
$b_{k}(z)\leq\hat{p}^{(i)}<b_{k+1}(z)$, we place it to the $k$-th bin.

To guide the calibration function learning, we compute posterior statistics of
each bin based on the constructed bins.111To ensure that the averaged response
rate of each bin is monotonically increasing, we can employ isotonic
regression to process the original binning. However in practice we find that
the final performance is not sensitive to this. Then for the $k$-th bin’s
samples, posterior statistics include the averaged response rate and the sum
of responses. We denote the posterior statistics of the $k$-th bin’s samples
as $\bm{p}_{k}(z)$.

####  4.1.2. Posterior-Guided Calibration Function Learning

Our AdaCalib learns an isotonic (monotonical) function family to map un-
calibrated predictions to calibrated scores. For each field value $z$,
AdaCalib has a function specific to it for calibration.

To preserve the ranking ability of the un-calibrated model and focus more on
approximating the posterior probabilities, the formulation of the calibration
function is a continuous piecewise linear mapping with monotone increasing
nature, where each bin has a linear mapping (Deng et al., 2020; Pan et al.,
2020). Specifically, for each bin’s samples, we adopt linear mapping to
transform the un-calibrated predictions $\hat{p}$ to calibrated scores
$\hat{p}_{\mathrm{calib}}$, and the key for learning calibration function is
to represent the slope of each bin.

Formally, the calibration function for $z$ is represented as:

(4) $\displaystyle\hat{p}_{\mathrm{calib}}$
$\displaystyle=\mathcal{F}_{\mathrm{calib}}(\hat{p};z)$
$\displaystyle=\frac{\mathsf{MLP}\bigl{(}\bm{p}_{k+1}(z)\bigr{)}-\mathsf{MLP}\bigl{(}\bm{p}_{k}(z)\bigr{)}}{b_{k+1}(z)-b_{k}(z)}\bigl{(}\hat{p}-b_{k}(z)\bigr{)}+\mathsf{MLP}\bigl{(}\bm{p}_{k}(z)\bigr{)}\,,$
$\displaystyle\quad\mathrm{\ if\ }b_{k}(z)\leq\hat{p}<b_{k+1}(z)$

where $\mathsf{MLP}(\cdot)$ denotes a fully-connected layer that enables rich
expressiveness. In this parameterized formulation, for samples in the $k$-th
bin, the calibration function has a slope
$\frac{\mathsf{MLP}\bigl{(}\bm{p}_{k+1}(z)\bigr{)}-\mathsf{MLP}\bigl{(}\bm{p}_{k}(z)\bigr{)}}{b_{k+1}-b_{k}}$
that is determined by the posterior statistics $\bm{p}_{k}(z)$.222We transform
posterior statistics $\bm{p}_{k}(z)$ to embeddings (by discretizing continuous
values to IDs) as the input of $\mathsf{MLP}(\cdot)$.

The posterior statistics guide the learning of calibration functions by
imposing on the slope of each bin. Because the posterior statistics are
computed on specific field values’ bins, learned functions are adaptive to
field values and perform field-level calibration.

In practice, we perform calibration on the logit $\sigma^{-1}(\hat{p})$ other
than the score $\hat{p}$. This enables the improvement of expressiveness via
adding an auxiliary term $\mathsf{MLP}_{\mathrm{aux}}(x)$ to calibrated logit
(Pan et al., 2020), and it is possible to improve ranking ability. Then a
logistic function is used to output the final calibrated score.

####  4.1.3. Optimization

The calibration function is optimized with:

(5)
$\small\mathcal{L}(\hat{p}_{\mathrm{calib}})=\ell\left(\hat{p}_{\mathrm{calib}},y\right)+\sum_{k=1}^{K}\max\bigl{\\{}\mathsf{MLP}\bigl{(}\bm{p}_{k}(z)\bigr{)}-\mathsf{MLP}\bigl{(}\bm{p}_{k+1}(z)\bigr{)},0\bigr{\\}}$

where $\ell$ is cross-entropy. The second term plays the role of a constraint,
which ensures that for each bin $k$ its slope is non-negative.

###  4.2. Field-Adaptive Binning

In the above we have implemented field-adaptive calibration function, where
the binning number is fixed to $K$ for all field values.

The reliability of posterior probability depends on the size of samples in a
bin. Different field values’ frequencies may be distinct. We expect that the
high-frequency field values (i.e., having sufficient samples) can be
partitioned to more bins to compute posterior statistics in a fine-grained
manner, while low-frequency field values is assigned with few bins to avoid
inaccurate posteriors.

We propose a field-adaptive binning mechanism to dynamically determine the
number of bins. Specifically, we pre-define $n$ candidates of bin number
$\\{K_{1},K_{2},\ldots,K_{n}\\}$, and maintain $n$ calibration function
families
$\left\\{\mathcal{F}^{1}_{\mathrm{calib}}(\cdot;z),\mathcal{F}^{2}_{\mathrm{calib}}(\cdot;z),\ldots,\mathcal{F}^{n}_{\mathrm{calib}}(\cdot;z)\right\\}$.

After obtaining the calibrated scores
$\left\\{\hat{p}^{1}_{\mathrm{calib}},\hat{p}^{2}_{\mathrm{calib}},\ldots,\hat{p}^{n}_{\mathrm{calib}}\right\\}$
produced by all calibration functions, AdaCalib employs hard attention to
select one of them as the final calibrated probability. Formally, the
attention scores $\\{\alpha_{1},\ldots,\alpha_{n}\\}$ is computed by a fully-
connected layer $\mathsf{MLP}_{\mathrm{bin}}(\cdot)$ that takes the field
value $z$’s frequency statistics as input, where a gumbel-softmax operation
(Jang et al., 2017) is used to approximate hard selection and keep the model
differentiable:

(6)
$\displaystyle\\{\hat{\alpha}_{i}\\}_{i=1}^{n}=\mathsf{MLP}_{\mathrm{bin}}(\bm{s}_{z})$
$\displaystyle\alpha_{i}=\frac{\exp\left(({\log\left(\hat{\alpha}_{i}\right)+g_{i}})/{\tau}\right)}{\sum_{j=1}^{n}\exp\left(({\log\left(\hat{\alpha}_{j}\right)+g_{j}})/{\tau}\right)},\text{
where }g_{i}=-\log\left(-\log u_{i}\right),u_{i}\sim U(0,1)$
$\displaystyle\hat{p}_{\mathrm{calib}}=\sum_{i=1}^{n}\alpha_{i}\cdot\hat{p}^{i}_{\mathrm{calib}}$

where $\bm{s}_{z}$ denotes $z$’s frequency information including the total
number of samples having value $z$ and the ID embedding of $z$.

The optimization objective of our AdaCalib is:

(7)
$\small\mathcal{L}_{\mathsf{AdaCalib}}=\sum_{i=1}^{n}\mathcal{L}\left(\hat{p}^{i}_{\mathrm{calib}}\right)\,.$

Figure 1. Training and serving of AdaCalib.

###  4.3. Online Deployment

For a sample $x$ having field value $z$, AdaCalib takes its un-calibrated
score $\hat{p}$, bound values of binning $\\{b_{k}(z)\\}$, posterior
statistics $\bm{p}_{k}(z)$ and frequency information $\bm{s}_{z}$ as inputs,
and the forward process is a light neural network. Given a neural predictive
model that produces un-calibrated scores, we integrate AdaCalib to the
predictive model via combining their checkpoints, and export a unified
checkpoint for online serving. Figure 1 illustrates the overall procedure, and
we can see that during online serving there is no need to maintain an
independent calibration module for AdaCalib.

##  5\. Experiments

Datasets We conduct experiments on both public and industrial datasets. We
collect click and conversion logs from our advertising system to construct two
industrial datasets, performing calibration on CTR and CVR prediction tasks.
The dataset for calibrating CTR prediction contains 1.2 billion impressions,
and we choose the field “item ID” that has 969 unique values. We split the log
by timestamp, where the first 5 days for $\mathcal{D}_{\mathrm{train}}$, the
6th day for $\mathcal{D}_{\mathrm{dev}}$ and the 7th day for
$\mathcal{D}_{\mathrm{test}}$. The dataset for calibrating CVR prediction
contains 0.2 billion clicks, and we choose the field “item ID” that has 542
unique values, where the first 60 days for $\mathcal{D}_{\mathrm{train}}$, the
next 7 days for $\mathcal{D}_{\mathrm{dev}}$ and the last 7 days for
$\mathcal{D}_{\mathrm{test}}$. For public dataset, we use the click logs (Ma
et al., 2018) to calibrate CTR prediction, which contains 80 million
impressions. We choose the field “user group ID” that has 13 unique values.
Because the provided training/test datasets do not contain timestamp
information, we split the training set with the proportion 1:1 to
$\mathcal{D}_{\mathrm{train}}$ and $\mathcal{D}_{\mathrm{dev}}$.

Table 1. Results of competitors for calibrating CTR and CVR predictive models on public and industrial datasets. $\ddagger$ denotes that the performance outperforms the second-best approach at the significant level of $p<0.05$ (paired t-test). Type | Approach |  CVR Task (industrial data) |  CTR Task (industrial data) |  CTR Task (public data)
---|---|---|---|---
Field-RCE | LogLoss | Field-AUC | AUC | Field-RCE | LogLoss | Field-AUC | AUC | Field-RCE | LogLoss | Field-AUC | AUC
No Calib. | N/A | 0.3311 | 0.1460 | 0.7833 | 0.8039 | 0.2592 | 0.0819 | 0.5879 | 0.6513 | 0.3258 | 0.1681 | 0.5760 | 0.5765
Binning | HistoBin | 0.3060 | 0.1460 | 0.7833 | 0.8039 | 0.2537 | 0.0819 | 0.5878 | 0.6513 | 0.0452 | 0.1657 | 0.5760 | 0.5765
IsoReg | 0.2329 | 0.1455 | 0.7833 | 0.8039 | 0.2538 | 0.0819 | 0.5877 | 0.6513 | 0.0430 | 0.1645 | 0.5760 | 0.5765
Scaling | GammaCalib | 0.2095 | 0.1451 | 0.7833 | 0.8039 | 0.2540 | 0.0819 | 0.5878 | 0.6513 | 0.0394 | 0.1630 | 0.5760 | 0.5765
Hybrid | SIR | 0.2579 | 0.1461 | 0.7833 | 0.8039 | 0.2532 | 0.0819 | 0.5878 | 0.6513 | 0.0428 | 0.1644 | 0.5760 | 0.5765
NeuCalib | 0.1920 | 0.1448 | 0.7833 | 0.8056 | 0.1815 | 0.0814 | 0.5888 | 0.6666 | 0.0485 | 0.1646 | 0.5897 | 0.5903
AdaCalib | 0.1666‡ | 0.1445 | 0.7843 | 0.8054 | 0.1626‡ | 0.0814 | 0.5899 | 0.6680 | 0.0147‡ | 0.1653 | 0.5897 | 0.5905

Comparative Approaches We choose representative calibration approaches as
competitors. Binning-based competitors are Histogram Binning (HistoBin)
(Zadrozny and Elkan, 2001) and Isotonic Regression (IsoReg) (Zadrozny and
Elkan, 2002). Scaling-based competitor is Gamma Calibration (GammaCalib)
(Kweon et al., 2022). Hybrid approaches are Smoothed Isotonic Regression (SIR)
(Deng et al., 2020) and Neural Calibration (NeuCalib) (Pan et al., 2020).

We conduct CTR calibration on both datasets as well as CVR calibration on
industrial datasets. Thus we trained three un-calibrated models, and model
architecture is composed of four-layered fully-connected layers (Covington et
al., 2016). For comparative approaches that need binning, we set the number of
bins to 10 empirically. The candidate set of bin numbers in AdaCalib is set to
{5, 10, 20} for CVR task and {2, 4, 8} for CTR task. All calibration
approaches are trained using
$\mathcal{D}_{\mathrm{dev}}\cup\mathcal{D}_{\mathrm{train}}$ because in
practice we found that the calibration performance is better in this way.

Evaluation Metrics We evaluate all comparative approaches from two
perspectives: 1) field-level calibration performance, evaluated by the metric
Field-RCE in Equation 3. 2) field-level ranking ability, evaluated by Field-
AUC (a.k.a. weighted AUC in previous work (He and McAuley, 2016)), which
represents whether the calibration approach hurts the ranking of the un-
calibrated model. Besides, we also report the overall (i.e., field-agnostic)
calibration and ranking performances for reference, which are evaluated by
LogLoss and AUC respectively. We do not consider expected calibration error
(ECE) as an overall metric because if a model simply predicts the averaged
response rate for all samples, its ECE is well but such model is non-useful.

Table 2. Ablation study for AdaCalib. Variants of AdaCalib | Metric
---|---
Posterior | Adaptive | Adaptive | Auxiliary | Field-RCE | Field-AUC
Guidance | Function | Binning | $\mathsf{MLP}_{\mathrm{aux}}(x)$
✓ | ✓ | ✓ | ✓ | 0.1666 | 0.7843
✓ | ✓ | ✓ | $\times$ | 0.1778 | 0.7828
✓ | ✓ | $\times$ | $\times$ | 0.1946 | 0.7827
✓ | $\times$ | $\times$ | $\times$ | 0.2120 | 0.7828
$\times$ | $\times$ | $\times$ | $\times$ | 0.2348 | 0.7833

###  5.1. Results and Discussion

####  5.1.1. Main Results

Table 1 shows the results for calibrating CTR and CVR predictive models, where
the first line lists the metrics of un-calibrated models. In terms of ranking
ability, we observe that calibration usually do not hurt AUC and Field-AUC of
un-calibrated models. NeuCalib and AdaCalib slightly improve AUC and Field-AUC
because they employ auxiliary $\textsf{MLP}_{\mathrm{aux}}(x)$ that improves
the expressiveness of calibration models.

In terms of the calibration performance, we can see that traditional binning-
and scaling-based approaches cannot achieve large improvement on the metric
Field-RCE. Thus, the approaches that do not consider field information during
calibration are less effective to field-level calibration. The field-level
competitor NeuCalib outperforms most approaches on Field-RCE and LogLoss,
demonstrating that taking field value into account is indeed effective for
calibrating model predictions at field-level. Our AdaCalib takes the
advantages of binning’s posterior statistics and parametric function’s
expressiveness to learn field-adaptive calibration function family, and
achieves the state-of-the-art calibration performance for all three predictive
models.

####  5.1.2. Ablation Study

Table 2 shows several variants of AdaCalib on calibrating CVR models.
Specifically, the variant without posterior guidance means that the two slope
parameters of each bin are directly set as two learnable parameters and do not
consider posterior statistics $\bm{p}_{k}(z)$. The variant without adaptive
function means that binning is performed on global dataset other than the
subset specific to field value $z$. The variant without adaptive binning means
that we employ a fixed binning number for all field values. As the results
shown in Table 2 (note that the last two lines’ variants do not perform field-
level calibration), we can see that all components contribute to the
calibration performance, which verifies the effectiveness of each component in
AdaCalib.

Figure 2. Calibration functions of AdaCalib and NeuCalib.

Figure 3. The number of field values selecting 5 or 20 bins.

###  5.2. Further Analysis

####  5.2.1. Comparison of Learned Functions

Figure 2 shows the learned calibration functions (i.e., piece-wise linear
mapping for all bins) of AdaCalib and NeuCalib for two distinct field values.
Recall that we perform calibration on logits, thus for visualization we employ
logistic function to transform the slope parameter
$\mathsf{MLP}\bigl{(}\bm{p}_{k}(z)\bigr{)}$ to probability space (y-axis).
Because the two approaches employ different binning strategies, to ensure that
their calibration functions are comparable, the x-axis represents bin ID other
than boundary value. Compared to NeuCalib, AdaCalib learns more appropriate
functions that approximate field-level posterior probabilities, verifying the
effect of field-adaptive mechanisms.

####  5.2.2. Effect of Field-Adaptive Binning

We rank all field values’ subsets $\\{\mathcal{D}^{z}\\}$ based on their
positive response numbers (which reflects the reliability of posterior
statistics), and then merge all $|\mathcal{Z}|$ subsets to 10 groups. Let the
1st group has fewest positive responses and the 10th group has most ones.
Figure 3 shows that in each group, the number of field values that select 5 or
20 bins via adaptive binning mechanism. We can see that with the increasing of
response numbers, more field values in the group tends to select the large
binning number (i.e., 20 bins) other than the small numbers. This verifies
that the field-adaptive binning mechanism can choose appropriate binning
numbers for specific field values.

###  5.3. Online A/B Test

We conduct online experiments using our advertising system’s CVR prediction
module for one week. Compared to SIR, it brings +5.05% lift on CVR and +5.47%
lift on Gross Merchandise Volume (GMV).

##  6\. Conclusion

We propose a doubly-adaptive calibration approach AdaCalib. Field-adaptive
mechanisms for function learning and binning strategy ensure that the learned
calibration function is appropriate for specific field value. Both offline and
online experiments verify that AdaCalib achieves significant improvement. In
future work, we shall explore how to improve AdaCalib under data sparsity.

## Acknowledgments

We thank all the anonymous reviewers to their insightful comments.

## References

  * (1)
  * Borisov et al. (2018) Alexey Borisov, Julia Kiseleva, Ilya Markov, and Maarten de Rijke. 2018.  Calibration: A simple way to improve click models. In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_. 1503–1506.
  * Cheng et al. (2016) Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al. 2016\.  Wide & deep learning for recommender systems. In _Proceedings of the 1st workshop on deep learning for recommender systems_. 7–10.
  * Covington et al. (2016) Paul Covington, Jay Adams, and Emre Sargin. 2016\.  Deep neural networks for YouTube recommendations. In _Proceedings of the 10th ACM conference on recommender systems_. 191–198.
  * Deng et al. (2020) Chao Deng, Hao Wang, Qing Tan, Jian Xu, and Kun Gai. 2020.  Calibrating user response predictions in online advertising. In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. 208–223.
  * Guo et al. (2017) Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. 2017\.  On calibration of modern neural networks. In _International Conference on Machine Learning_. 1321–1330.
  * He and McAuley (2016) Ruining He and Julian McAuley. 2016.  Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In _proceedings of the 25th international conference on world wide web_. 507–517.
  * He et al. (2014) Xinran He, Junfeng Pan, Ou Jin, Tianbing Xu, Bo Liu, Tao Xu, Yanxin Shi, Antoine Atallah, Ralf Herbrich, Stuart Bowers, et al. 2014\.  Practical lessons from predicting clicks on ads at facebook. In _Proceedings of the eighth international workshop on data mining for online advertising_. 1–9.
  * Huang et al. (2022) Siguang Huang, Yunli Wang, Lili Mou, Huayue Zhang, Han Zhu, Chuan Yu, and Bo Zheng. 2022.  MBCT: Tree-Based Feature-Aware Binning for Individual Uncertainty Calibration. In _Proceedings of The Web Conference 2022_.
  * Jang et al. (2017) Eric Jang, Shixiang Gu, and Ben Poole. 2017.  Categorical Reparameterization with Gumbel-Softmax. In _International Conference on Learning Representations_.
  * Kull et al. (2017) Meelis Kull, Telmo Silva Filho, and Peter Flach. 2017\.  Beta calibration: A well-founded and easily implemented improvement on logistic calibration for binary classifiers. In _Artificial Intelligence and Statistics_. 623–631.
  * Kumar et al. (2019) Ananya Kumar, Percy S Liang, and Tengyu Ma. 2019.  Verified uncertainty calibration.  _Advances in Neural Information Processing Systems_ 32 (2019).
  * Kweon et al. (2022) Wonbin Kweon, SeongKu Kang, and Hwanjo Yu. 2022.  Obtaining Calibrated Probabilities with Personalized Ranking Models. In _Proceedings of the 36th AAAI Conference on Artificial Intelligence_.
  * Ma et al. (2018) Xiao Ma, Liqin Zhao, Guan Huang, Zhi Wang, Zelin Hu, Xiaoqiang Zhu, and Kun Gai. 2018.  Entire space multi-task model: An effective approach for estimating post-click conversion rate. In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_. 1137–1140.
  * McMahan et al. (2013) H Brendan McMahan, Gary Holt, David Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, et al. 2013\.  Ad click prediction: A view from the trenches. In _Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining_. 1222–1230.
  * Naeini et al. (2015) Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. 2015\.  Obtaining well calibrated probabilities using Bayesian binning. In _Twenty-Ninth AAAI Conference on Artificial Intelligence_.
  * Pan et al. (2020) Feiyang Pan, Xiang Ao, Pingzhong Tang, Min Lu, Dapeng Liu, Lei Xiao, and Qing He. 2020.  Field-aware calibration: A simple and empirically strong method for reliable probabilistic predictions. In _Proceedings of The Web Conference 2020_. 729–739.
  * Platt et al. (1999) John Platt et al. 1999\.  Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods.  _Advances in large margin classifiers_ 10, 3 (1999), 61–74.
  * Wei et al. (2021) Penghui Wei, Weimin Zhang, Zixuan Xu, Shaoguo Liu, Kuang-chih Lee, and Bo Zheng. 2021\.  AutoHERI: Automated Hierarchical Representation Integration for Post-Click Conversion Rate Estimation. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. 3528–3532.
  * Xu et al. (2022) Zixuan Xu, Penghui Wei, Weimin Zhang, Shaoguo Liu, Liang Wang, and Bo Zheng. 2022\.  UKD: Debiasing Conversion Rate Estimation via Uncertainty-regularized Knowledge Distillation. In _Proceedings of The Web Conference 2022_.
  * Zadrozny and Elkan (2001) Bianca Zadrozny and Charles Elkan. 2001.  Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers. In _Proceedings of the Eighteenth International Conference on Machine Learning_. 609–616.
  * Zadrozny and Elkan (2002) Bianca Zadrozny and Charles Elkan. 2002.  Transforming classifier scores into accurate multiclass probability estimates. In _Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining_. 694–699.
  * Zhou et al. (2018) Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. 2018\.  Deep interest network for click-through rate prediction. In _Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining_. 1059–1068.


$\mathbf{\Pi}^{1}_{3}\mbox{-}\omega\mathsf{RFN}$ are equivalent [Sim09,
Theorem VIII.5.12].

######  Lemma 6.6 ($\mathsf{ACA}_{0}$).

$\mathbf{\Pi}^{1}_{2}\mbox{-}\mathbf{R}^{\alpha}\big{(}\mathsf{ACA}_{0}+\mathbf{\Pi}^{1}_{3}\mbox{-}\omega\mathsf{RFN}(\mathsf{ACA}_{0})\big{)}\equiv^{\mathbf{\Sigma}^{1}_{1}}_{\mathbf{\Pi}^{1}_{2}}\mathbf{\Pi}^{1}_{2}\mbox{-}\omega\mathbf{R}^{\omega\alpha}(\mathsf{ACA}_{0})$

###### Proof.

We prove the lemma using Löb’s Theorem. We reason in $\mathsf{ACA}_{0}$. We
assume that the lemma is provable in $\mathsf{ACA}_{0}$ and claim that the
lemma holds. We consider some particular linear order $\alpha$ and need to
show that

$U=\mathbf{\Pi}^{1}_{2}\mbox{-}\mathbf{R}^{\alpha}\big{(}\mathsf{ACA}_{0}+\mathbf{\Pi}^{1}_{3}\mbox{-}\omega\mathsf{RFN}(\mathsf{ACA}_{0})\big{)}\equiv^{\mathbf{\Sigma}^{1}_{1}}_{\mathbf{\Pi}^{1}_{2}}\mathbf{\Pi}^{1}_{2}\mbox{-}\omega\mathbf{R}^{\omega\alpha}(\mathsf{ACA}_{0})=V.$

We start with proving
$U\supseteq^{\mathbf{\Sigma}^{1}_{1}}_{\mathbf{\Pi}^{1}_{2}}V$. It is enough
to show that for any $\beta\prec\alpha$ and $n<\omega$, the sentence
$\mathbf{\Pi}^{1}_{2}\textrm{-}\mathsf{RFN}(\mathbf{\Pi}^{1}_{2}\mbox{-}\mathbf{R}^{\omega\beta+n}\big{(}\mathsf{ACA}_{0})\big{)}$
is provable in $U$. By the provability of the present lemma we have the
provability of the equivalence

$\mathbf{\Pi}^{1}_{2}\textrm{-}\mathsf{RFN}\Big{(}\mathbf{\Pi}^{1}_{2}\mbox{-}\mathbf{R}^{\beta}\big{(}\mathsf{ACA}_{0}+\mathbf{\Pi}^{1}_{3}\mbox{-}\omega\mathsf{RFN}(\mathsf{ACA}_{0})\big{)}\Big{)}\mathrel{\leftrightarrow}\mathbf{\Pi}^{1}_{2}\textrm{-}\mathsf{RFN}\big{(}\mathbf{\Pi}^{1}_{2}\mbox{-}\mathbf{R}^{\omega\beta}(\mathsf{ACA}_{0})\big{)}.$

Thus $U$ proves
$\mathbf{\Pi}^{1}_{2}\textrm{-}\mathsf{RFN}(\mathbf{\Pi}^{1}_{2}\mbox{-}\mathbf{R}^{\omega\beta}\big{(}\mathsf{ACA}_{0})\big{)}$.
Next by induction (using closure of $V$ under
$\mathbf{\Pi}^{1}_{2}\textrm{-}\mathsf{RFN}$ rule) we establish that $U$
proves
$\mathbf{\Pi}^{1}_{2}\textrm{-}\mathsf{RFN}(\mathbf{\Pi}^{1}_{2}\mbox{-}\mathbf{R}^{\omega\beta+m}\big{(}\mathsf{ACA}_{0})\big{)}$,
for all natural $m$.

Now let us prove that
$U\subseteq^{\mathbf{\Sigma}^{1}_{1}}_{\mathbf{\Pi}^{1}_{2}}V$. We need to
show that for any $\beta<\alpha$ we have

$U^{\prime}=\mathsf{ACA}_{0}+\mathbf{\Pi}^{1}_{3}\mbox{-}\omega\mathsf{RFN}(\mathsf{ACA}_{0})+\mathbf{\Pi}^{1}_{2}\mbox{-}\omega\mathsf{RFN}\Big{(}\mathbf{\Pi}^{1}_{2}\mbox{-}\mathbf{R}^{\beta}\big{(}\mathsf{ACA}_{0}+\mathbf{\Pi}^{1}_{3}\mbox{-}\omega\mathsf{RFN}(\mathsf{ACA}_{0})\big{)}\Big{)}\supseteq^{\mathbf{\Sigma}^{1}_{1}}_{\mathbf{\Pi}^{1}_{2}}V.$

Indeed, the provability of the lemma implies that $V$ proves

$\mathbf{\Pi}^{1}_{2}\mbox{-}\omega\mathsf{RFN}\Big{(}\mathbf{\Pi}^{1}_{2}\mbox{-}\mathbf{R}^{\beta}\big{(}\mathsf{ACA}_{0}+\mathbf{\Pi}^{1}_{3}\mbox{-}\omega\mathsf{RFN}(\mathsf{ACA}_{0})\big{)}\Big{)}.$

Using the closure of $V$ under the
$\mathbf{\Pi}^{1}_{2}\textrm{-}\mathsf{RFN}$ rule and Lemma 2.9 we get the
desired inclusion
$U^{\prime}\subseteq^{\mathbf{\Sigma}^{1}_{1}}_{\mathbf{\Pi}^{1}_{2}}V$.∎

######  Theorem 6.7.

$\mathsf{ATR}_{0}\equiv\mathsf{ACA}_{0}+\mathbf{\Pi}^{1}_{2}\mbox{-}\omega\mathsf{RFN}(\mathsf{ACA}_{0}+\mathbf{\Pi}^{1}_{3}\mbox{-}\omega\mathsf{RFN}\big{(}\mathsf{ACA}_{0})\big{)}$

###### Proof.

The following sequence of pairwise equivalent sentences establishes the
equivalence:

$\displaystyle\mathsf{ATR}_{0}$
$\displaystyle\equiv\forall\alpha\Big{(}\mathsf{WO}(\alpha)\to\mathbf{\Pi}^{1}_{2}\mbox{-}\omega\mathsf{RFN}\big{(}\mathbf{\Pi}^{1}_{2}\mbox{-}\omega\mathbf{R}^{\alpha}(\mathsf{ACA}_{0})\big{)}\Big{)}\text{
by Corollary \ref{reflection_ATR_0} }$
$\displaystyle\equiv\forall\alpha\Big{(}\mathsf{WO}(\alpha)\to\mathbf{\Pi}^{1}_{2}\mbox{-}\mathsf{RFN}\big{(}\mathbf{\Pi}^{1}_{2}\mbox{-}\omega\mathbf{R}^{\omega\alpha}(\mathsf{ACA}_{0})\big{)}\Big{)}\text{
trivially}$
$\displaystyle\equiv\forall\alpha\Big{(}\mathsf{WO}(\alpha)\to\mathbf{\Pi}^{1}_{2}\mbox{-}\mathsf{RFN}\big{(}\mathbf{\Pi}^{1}_{2}\mbox{-}\mathbf{R}^{\alpha}(\mathsf{ACA}_{0}+\mathbf{\Pi}^{1}_{3}\mbox{-}\omega\mathsf{RFN}(\mathsf{ACA}_{0}))\big{)}\Big{)}\text{
by Lemma \ref{DC_iter}}$
$\displaystyle\equiv\mathbf{\Pi}^{1}_{2}\mbox{-}\omega\mathsf{RFN}\big{(}\mathsf{ACA}_{0}+\mathbf{\Pi}^{1}_{3}\mbox{-}\omega\mathsf{RFN}(\mathsf{ACA}_{0})\big{)}\text{
by Theorem \ref{omega_to_iter}}$

This completes the proof of the theorem. ∎

##  7\. Proof-theoretic ordinals and well-ordering principles

In this section we deliver proof-theoretic applications of the results from
the previous sections. In particular, we use the systematic connection between
$\omega$-model reflection and dilators to provide uniform proof-theoretic
analyses of theories in the interval $[\mathsf{ACA}_{0},\mathsf{ATR}]$. Note
that these techniques are useful not only for calculating proof-theoretic
ordinals but also for proving reverse-mathematical characterizations of well-
ordering principles.

The following is a variant of the usual Schmerl’s formula that could be proved
in a standard manner [Bek03, Sch79] using Lemma 2.9:

######  Theorem 7.1.

For any $\mathbf{\Pi}^{1}_{n+1}$-axiomatizable theory $T$ we have

$T+\mathbf{\Pi}^{1}_{\infty}\text{-}\mathsf{RFN}(T)\equiv^{\mathbf{\Sigma}^{1}_{1}}_{\mathbf{\Pi}^{1}_{n}}\mathbf{\Pi}^{1}_{n}\text{-}\mathbf{R}^{\varepsilon_{0}}(T).$

######  Corollary 7.2.

  1. (1)

$|\mathsf{ACA}_{0}^{+}|_{\mathbf{\Pi}^{1}_{1}}=\phi_{2}(0)$;

  2. (2)

$|\Sigma^{1}_{1}$-$\mathsf{AC}|_{\mathbf{\Pi}^{1}_{1}}=|\Pi^{1}_{2}$-$\mathsf{RFN}^{\varepsilon_{0}}(\Sigma^{1}_{1}$-$\mathsf{AC}_{0})|_{\mathbf{\Pi}^{1}_{1}}=\phi_{\varepsilon_{0}}(0)$;

  3. (3)

$|\mathsf{ATR}_{0}|_{\mathbf{\Pi}^{1}_{1}}=\Gamma_{0}$;

  4. (4)

$|\mathsf{ATR}|_{\mathbf{\Pi}^{1}_{1}}=\Gamma_{\varepsilon_{0}}$.

###### Proof.

(1) is a straightforward combination of Theorems 5.8 and 5.10. (3) follows
immediately from 5.6.

For (2) we reason as follows:

$\displaystyle\Sigma^{1}_{1}\text{-}\mathsf{AC}$
$\displaystyle\equiv\mathsf{\Sigma}^{1}_{1}\text{-}\mathsf{AC}_{0}+\mathbf{\Pi}^{1}_{\infty}\text{-}\mathsf{RFN}(\mathsf{\Sigma}^{1}_{1}\text{-}\mathsf{AC}_{0})$
$\displaystyle\equiv^{\mathbf{\Sigma}^{1}_{1}}_{\mathbf{\Pi}^{1}_{2}}\mathbf{\Pi}^{1}_{2}\text{-}\mathbf{R}^{\varepsilon_{0}}(\Sigma^{1}_{1}\text{-}\mathsf{AC}_{0})\text{
by Theorem \ref{Schmerl-variant}}$
$\displaystyle\equiv\mathbf{\Pi}^{1}_{2}\text{-}\mathbf{R}^{\varepsilon_{0}}(\mathsf{ACA}_{0}+\Sigma^{1}_{1}\text{-}\mathsf{AC}_{0})$
$\displaystyle\equiv_{\mathbf{\Pi}^{1}_{2}}\mathbf{\Pi}^{1}_{2}\text{-}\omega\mathbf{R}^{\varepsilon_{0}}(\mathsf{ACA}_{0})\text{
by Lemma \ref{AC_cons_iter}}$

The conclusion follows since, by Theorem 5.11,
$|\mathbf{\Pi}^{1}_{2}\text{-}\omega\mathbf{R}^{\varepsilon_{0}}(\mathsf{ACA}_{0})|_{\mathbf{\Pi}^{1}_{1}}=\phi^{+}_{\varepsilon_{0}}(0)$.

For (4), we first note that:

$\displaystyle\mathsf{ATR}$
$\displaystyle\equiv\mathsf{ATR}_{0}+\mathbf{\Pi}^{1}_{\infty}\text{-}\mathsf{RFN}(\mathsf{ATR}_{0})$
$\displaystyle\equiv^{\mathbf{\Sigma}^{1}_{1}}_{\mathbf{\Pi}^{1}_{1}}\mathbf{\Pi}^{1}_{1}\text{-}\mathbf{R}^{\varepsilon_{0}}(\mathsf{ATR}_{0})\text{
by Theorem \ref{Schmerl-variant}}$

We proceed to show that for any linear order $\alpha$ we have

(16)
$|\mathbf{\Pi}^{1}_{1}\textrm{-}\mathbf{R}^{\alpha}(\mathsf{ATR}_{0})|_{\mathbf{\Pi}^{1}_{1}}=\Gamma_{\alpha}.$

We prove it using Löb’s theorem.

We reason in $\mathsf{ACA_{0}}$ under the assumption $\mathsf{ACA}_{0}$-proves
that for all for all linear orders $\alpha$ we have (16). We need to show that
(16) holds. Indeed, for any linear order $\beta$ we have
$\mathbf{\Pi}^{1}_{1}\textrm{-}\mathbf{R}^{\alpha}(\mathsf{ATR}_{0})\vdash\mathsf{WO}(\beta)$
iff for some $x\in\alpha$ we have

$\mathsf{ATR}_{0}+\mathbf{\Pi}^{1}_{1}\textrm{-}\mathsf{RFN}(\mathbf{\Pi}^{1}_{1}\textrm{-}\mathbf{R}^{\mathsf{cone}(\alpha,x)}(\mathsf{ATR}_{0}))\vdash\mathsf{WO}(\beta).$

But using our assumption about provability of (16) we see that

$\mathsf{ACA}_{0}\vdash\mathbf{\Pi}^{1}_{1}\textrm{-}\mathsf{RFN}(\mathbf{\Pi}^{1}_{1}\textrm{-}\mathbf{R}^{\gamma}(\mathsf{ATR}_{0}))\mathrel{\leftrightarrow}\mathsf{WO}(\Gamma_{\gamma}).$

Thus
$\mathbf{\Pi}^{1}_{1}\textrm{-}\mathbf{R}^{\alpha}(\mathsf{ATR}_{0})\vdash\mathsf{WO}(\beta)$
iff for some $x\in\alpha$ we have

$\mathsf{ATR}_{0}+\mathsf{WO}(\Gamma_{\mathsf{cone}(\alpha,x)})\vdash\mathsf{WO}(\beta).$

And since $|\mathsf{ATR}_{0}|_{\mathbf{\Pi}^{1}_{2}}=\Gamma^{+}$ the latter
condition is equivalent to:

$\beta<\Gamma^{+}(\Gamma_{\mathsf{cone}(\alpha,x)})=\Gamma_{\mathsf{cone}(\alpha,x)+1}.$

Thus (16) holds. ∎

Note that our technique actually delivers not just $\Pi^{1}_{1}$-ordinals but
also reverse-mathematical well-ordering theorems.

######  Corollary 7.3.

Over $\mathsf{ACA}_{0}$ we have the following equivalences:

  1. (1)

$\mathsf{ACA}_{0}^{+}$ is equivalent to the well-ordering principle

$\forall\alpha\Big{(}\mathsf{WO}(\alpha)\to\mathsf{WO}\big{(}\phi_{1}(\alpha)\big{)}\Big{)}.$

  2. (2)

$\mathsf{ATR}_{0}$ is equivalent to the well-ordering principle

$\forall\alpha\Big{(}\mathsf{WO}(\alpha)\to\mathsf{WO}\big{(}\phi_{\alpha}(0)\big{)}\Big{)}.$

###### Proof.

We reason in $\mathsf{ACA}_{0}$. By Theorem 4.3 $\mathsf{ACA}_{0}^{+}$ is
equivalent to

$\forall\alpha\Big{(}\mathsf{WO}(\alpha)\rightarrow\mathbf{\Pi}^{1}_{1}\mbox{-}\mathsf{RFN}\big{(}\mathbf{\Pi}^{1}_{1}\mbox{-}\mathbf{R}^{\alpha}(\mathsf{ACA}_{0})\big{)}\Big{)}.$

And by Theorem 5.9
$\mathbf{\Pi}^{1}_{1}\mbox{-}\mathsf{RFN}(\mathbf{\Pi}^{1}_{1}\mbox{-}\mathbf{R}^{\alpha}(\mathsf{ACA}_{0}))$
is equivalent to $\mathsf{WO}(\varphi_{1}^{+\alpha})$. This yields 1.

We again reason in $\mathsf{ACA}_{0}$. By Theorem 4.3 $\mathsf{ATR}_{0}$ is
equivalent to

$\forall\alpha\Big{(}\mathsf{WO}(\alpha)\rightarrow\mathbf{\Pi}^{1}_{1}\mbox{-}\mathsf{RFN}\big{(}\mathbf{\Pi}^{1}_{2}\mbox{-}\omega\mathbf{R}^{\alpha}(\mathsf{ACA}_{0})\big{)}\Big{)}.$

The formula
$\mathbf{\Pi}^{1}_{1}\mbox{-}\mathsf{RFN}\big{(}\mathbf{\Pi}^{1}_{2}\mbox{-}\omega\mathbf{R}^{\alpha}(\mathsf{ACA}_{0})\big{)}$
by Theorem 5.11 is equivalent to $\mathsf{WO}(\phi_{1+\alpha}(0))$. This
yields 2. ∎

## References

  * [AR09] Bahareh Afshari and Michael Rathjen.  Reverse mathematics and well-ordering principles: A pilot study.  Annals of Pure and Applied Logic, 160(3):231–237, 2009.
  * [AS99] Jeremy Avigad and Richard Sommer.  The model-theoretic ordinal analysis of theories of predicative strength.  The Journal of Symbolic Logic, 64(1):327–349, 1999.
  * [Avi02] Jeremy Avigad.  Saturated models of universal theories.  Annals of Pure and Applied Logic, 118(3):219–234, 2002.
  * [Bek03] Lev D Beklemishev.  Proof-theoretic analysis by iterated reflection.  Archive for Mathematical Logic, 42(6):515–552, 2003.
  * [FD15] David Fernández-Duque.  Impredicative consistency and reflection, 2015.
  * [Fef62] Solomon Feferman.  Transfinite recursive progressions of axiomatic theories.  The Journal of Symbolic Logic, 27(3):259–316, 1962.
  * [Fri75] Harvey Friedman.  Some systems of second order arithmetic and their use.  In in Proceedings of the International Congress of Mathematicians, Vancouver 1974, pages 235–242, 1975.
  * [Gir81] Jean-Yves Girard.  $\Pi^{1}_{2}$-logic, Part 1: Dilators.  Annals of Mathematical Logic, 21(2-3):75–219, 1981.
  * [Gir87] J.-Y. Girard.  Proof Theory and Logical Complexity.  Bibliopolis, 1987.
  * [JS99] Gerhard Jäger and Thomas Strahm.  Bar induction and $\omega$ model reflection.  Annals of Pure and Applied Logic, 97(1):221 – 230, 1999.
  * [KL68] Georg Kreisel and Azriel Lévy.  Reflection principles and their use for establishing the complexity of axiomatic systems.  Mathematical Logic Quarterly, 14(7-12):97–142, 1968.
  * [MM11] Alberto Marcone and Antonio Montalbán.  The Veblen functions for computability theorists.  The Journal of Symbolic Logic, 76(2):575–602, 2011.
  * [Poh08] Wolfram Pohlers.  Proof theory: The first step into impredicativity.  Springer Science & Business Media, 2008.
  * [PW18] Fedor Pakhomov and James Walsh.  Reflection ranks and ordinal analysis.  arXiv preprint arXiv:1805.02095, 2018.
  * [Sch79] Ulf R Schmerl.  A fine structure generated by reflection formulas over primitive recursive arithmetic.  In Studies in Logic and the Foundations of Mathematics, volume 97, pages 335–350. Elsevier, 1979.
  * [Sch82] Ulf R Schmerl.  Iterated reflection principles and the $\omega$-rule.  The Journal of Symbolic Logic, 47(4):721–733, 1982.
  * [Sho69] Joseph R Shoenfield.  On a restricted $\omega$-rule.  The Journal of Symbolic Logic, 34(1):130–131, 1969.
  * [Sim09] Stephen G Simpson.  Subsystems of Second Order Arithmetic, volume 1.  Cambridge University Press, 2009.