# Optimal polymer slugs injection profiles

F. Bakharev, A. Enin, K. Kalinin, Yu. Petrova111Corresponding author. E-mail:
<EMAIL_ADDRESS>St. Petersburg State University, 7/9 Universitetskaya
Emb., St Petersburg 199034, Russia., N. Rastegaev, S. Tikhomirov

###### Abstract

The graded viscosity banks technology (tapering) for polymer flooding is
studied for several different models of mixing zones behavior. Depending on
the viscosity function the limiting polymer injection profile is rigorously
derived in case of transverse flow equilibrium assumption, for the Koval model
and for the Todd-Longstaff model. The possible gain of the polymer in
comparison to finite number of slugs is numerically estimated.

Keywords.  Koval model, transverse flow equilibrium, Todd-Longstaff model,
graded viscosity banks, tapering, polymer flooding. 2000 Mathematics Subject
Classification.  Primary 76D55; secondary 35L65, 49Q10.

##  1 Introduction

Chemical flooding, i.e. injection of aqueous solutions of several chemical
components, is one of the most widely studied and used enhanced oil recovery
methods. Polymer flooding consists of adding polymer to the injected water to
decrease its mobility and usually used for several purposes. Firstly, to
stabilize displacements if the oil-water shock front mobility ratio is greater
than one and so to prevent the degree of viscous fingering (see e.g. [1, 2, 3,
4]). Secondly, in combination with other chemicals to increase shock front
saturation in comparison with ordinary waterflooding and so to reduce the
watercut until the polymer appears on the production well. Thirdly, to improve
the sweep efficiency in heterogeneous reservoirs. Main disadvantage of
chemical flooding is the high cost of chemical ingredients. To reduce the
costs one desires to inject a fixed and rather small volume of chemical
solutions (slugs). In such a case the main chemical slug is commonly driven by
polymer slug and water postflush.

However, some factors may potentially spoil or destroy the polymer slug. If
the transition to drive water is made abruptly, miscible viscous fingering
occurs at the trailing edge of the polymer slug, thereby forming a so-called
mixing zone (see Fig. 1). If these fingers (the leading edge of the mixing
zone) reach the leading edge of the slug they will affect the main chemical
solution and reduce its benefits. Note that viscous fingering in this case
usually occurs despite the stabilizing effect of diffusion (see e.g. [5, 6, 7,
8, 9]). We mention here that another crucial factor which negatively affects
the polymer slug is adsorption, but in the current work we are not going to
discuss it.

Figure 1: Example of an injection scheme in chemical flooding. On the trailing
edge of the polymer slug instabilities occur, forming a so-called mixing zone
of viscous fingering. In this paper we assume constant velocity rates of
leading and trailing edges of the mixing zone, $v^{f}$ and $v^{b}$
respectively.

Many numerical simulations and laboratory experiments (e.g. [10, 11] and
references therein) show that under conditions of high Péclet number the
mixing zone spreads linearly in time and its leading and trailing edges travel
asymptotically with constant velocities $v^{f}$ and $v^{b}$ respectively.
There are several empirical models describing the behavior of the averaged
concentration across the fingers, and as a consequence giving the empirical
estimates for the velocities $v^{f}$ and $v^{b}$ (Koval model [12], naive
Koval model [13], Todd-Longstaff model [14] etc). Another approach consists in
writing pessimistic theoretical bounds for the velocities under some
additional assumptions (e.g. transverse flow equilibrium (TFE) model for
gravity-driven fingers [15, 16] and for linear flood [17], see [11] for
numerical elaboration). The main idea of these approaches is the transition
from a two-dimensional problem to a one-dimensional one, which greatly
simplifies the analysis of corresponding equations.

In this paper we focus on the graded viscosity bank (GVB) technology firstly
suggested in [9]. It consists in sequential injection of several polymer slugs
with a gradual decrease in viscosity (concentration), which helps reducing the
viscous fingering instabilities and allows to save polymer mass in comparison
to one polymer slug. In this case several mixing zones appear and it is
important to prevent their overlapping. The main aim of the present paper is
to calculate optimal injection schemes based on various one-dimensional
approximate models. We deduce conditions for finite number of slugs and
optimal injection profile corresponding to infinite number of slugs. The
choice of the model is out of the scope of the present paper, see [11] for the
discussion. While due to engineering and organizational reasons in practice a
small number of slugs is usually used, it is important to note what is the
maximum theoretically possible gain by GVB-method in order to make a decision
how many slugs should be used.

One notable conclusion of our analysis is that the limiting optimal injection
scheme in all considered models has the same very simple structure. After some
natural rescaling it starts with the maximal polymer concentration $c_{\max}$
at the beginning of the polymer injection and decays as the inverse to the
function (see Section 2 for formal definition)

$\mathcal{T}(c)=1-\left(\frac{\mu(c)}{\mu(c_{\max})}\right)^{\beta}$

with some parameter $\beta$ (different for different models). Note that
$\beta=0.44$ in case of Koval model was heuristically predicted by Claridge in
[9] but was not rigorously proved. In our paper we get this result as a
consequence of general scheme.

The paper has the following structure. In Section 2 we formulate the
mathematical description of the graded viscosity banks technology for a finite
number of slugs and the main result of the article (Theorem 1), that describes
the limiting optimal injection profile in GVB technology as number of slugs
tends to infinity. Section 3 contains the proof of the Theorem 1. Section 4
describes the numerical results for a finite number of slugs and some
qualitative information about the convergence to limiting profiles.

##  2 Problem statement and formulation of the main theorem

We assume the flow to be single-phase, which is the case, for example, for a
post flush polymer slug in surfactant-polymer flooding. One-phase miscible
flow in porous media can be described by a system of equations called Peaceman
model [18], which couples an equation for the transport of solvent with
incompressibility condition and Darcy’s law for fluid velocity:

$\displaystyle\phi\frac{\partial c}{\partial t}+\mathrm{div}(q\cdot c)=D\Delta
c,$ (1) $\displaystyle q=-\frac{k}{\mu(c)}\nabla p=-m(c)\nabla
p,\qquad\mathrm{div}(q)=0,$ (2)

where $c$ is concentration of polymer, $\phi$ is porosity, $q$ is velocity,
$\mu=\mu(c)$ is viscosity function which is assumed to be positive and
strictly increasing, $p$ is pressure, $D$ is diffusion coefficient and $k$ is
permeability. Also $m=k/\mu$ is a mobility function.

Figure 2: An example of boundary condition $\mathcal{C}(t)$ in GVB (left) and
corresponding injection profile $\mathcal{T}(c)$ (right)

We consider the system (1)-(2) in rectangular domain with the length $L$ and
width $W$, and assume that $Q$ is a linear injection velocity at the injection
well, i.e. $q(0,y,t)=(Q,0)$. Under proper scaling of variables we can assume
$L=1$, $Q=1$. We put $c=0$ as initial condition which means that there is no
polymer before we start the injection. The boundary condition at the injection
well for a GVB technology is described by a piecewise constant function
$\mathcal{C}=\mathcal{C}(t)=c(0,y,t)$ (see Fig. 2). The values of the injected
concentrations are described by a partition ${\bf c}=(c_{1},\ldots,c_{n+1})$
of the interval $[c_{\min},c_{\max}]=[c_{n+1},c_{1}]$, i.e.
$c_{\max}=c_{1}>c_{2}>\ldots>c_{n}>c_{n+1}=c_{\min}$. The corresponding
injection times are defined by the vector ${\bf t}=(t_{1},\ldots,t_{n+1})$
with non-negative coordinates and $t_{1}>0$. Usually, $c_{\min}=c_{n+1}=0$ and
we inject water as the last slug. Thus, the function $\mathcal{C}$ can be
written as a linear combination of the indicator functions

$\mathcal{C}(t):=\sum_{j=1}^{n+1}c_{j}\mathds{1}_{[T_{j-1},T_{j}]}(t),$

where $T_{0}=0$ and $T_{j}=t_{1}+\ldots+t_{j}$ is the starting time for the
injection of the concentration $c_{j+1}$, $T_{n+1}=L/Q=1$. It will be very
convenient to consider an inverse function $\mathcal{T}=\mathcal{T}(c)$
defined by the formula

$\mathcal{T}(c):=\sum_{j=1}^{n}T_{j}\cdot\mathds{1}_{[c_{j+1},c_{j}]}(c),$ (3)

which we will call an injection profile (see Fig. 2).

The total amount $V$ of injected polymer can be calculated as

$V({\bf c},{\bf
t}):=\sum\limits_{k=1}^{n+1}c_{k}t_{k}=\sum\limits_{j=1}^{n}(c_{j}-c_{j+1})T_{j}+c_{n+1}T_{n+1}=\int\limits_{0}^{c_{1}}\mathcal{T}(c)\,dc.$
(4)

As we mention above the mixing zones appear at the common boundary of each two
slugs (see Fig. 3). We say that there has been a breakthrough if two mixing
zones overlap each other. Let $v^{f}_{j}$ and $v^{b}_{j}$ be a leading and
trailing edge velocities of the $j$-th mixing zone. We are interested in
configurations in which a breakthrough occurs not sooner than the polymer
reaches the production well. Thus, the no-breakthrough conditions are

$\displaystyle v_{j}^{b}\cdot(1-T_{j})$ $\displaystyle\geqslant
v_{j+1}^{f}\cdot(1-T_{j+1}),$ (5)

for $j\in\\{0,\ldots,n-1\\}$ and $v_{0}^{b}=1$.

######  Remark 1.

Conditions (5) provide a non-breakthrough between each two consecutive slugs,
although from practical point of view it is important to have a non-
breakthrough condition only of the first slug. Rigorous formulation of such a
problem faces the lack of numerical and experimental investigation on what
happens when two mixing zones overlap. Is it not clear whether it is correct
that the dynamics of the leading and trailing edges of new mining zones
remains linear. Preliminary numerical experiments show that this dynamics
obeys different laws. This is out of the scope of the present paper.

Figure 3: Two-dimensional picture of the viscous fingers growth in Peaceman
model

######  Definition 1.

A pair $({\bf c},{\bf t})$ is called an $n$-configuration if ${\bf c}$ is the
partition of $[c_{1},c_{n+1}]$ and ${\bf t}$ satisfies the non-breakthrough
conditions (5).

######  Definition 2.

An $n$-configuration $({\bf c},{\bf t})$ is called an optimal
$n$-configuration if it minimizes the volume function $V$ among all
$n$-configurations.

######  Remark 2.

It is easy to see that for an optimal $n$-configuration the inequalities in
(5) could be replaced by the equalities. Then the no-breakthrough conditions
become a linear system of $n$ equations with $n$ variables and can be solved
explicitly:

$\displaystyle T_{j}=1-\prod\limits_{k=1}^{j}\frac{v_{k-1}^{b}}{v_{k}^{f}},$
(6)

for $j\in\\{1,\ldots,n\\}$. Note that the velocity functions $v^{f}_{j}$ and
$v^{b}_{j}$ generally depend on the partition ${\bf c}$. Concrete form of
these dependencies is determined by the choice of the mixing zone growth
model. So for an optimal $n$-configuration the volume function $V=V({\bf
c},{\bf t}({\bf c}))$ is a function of ${\bf c}$ only. For simplicity we
denote it with the same letter $V({\bf c})$.

######  Definition 3.

Let $({\bf c},{\bf t})$ be an optimal $n$-configuration. Then $\mathcal{T}$,
defined in (3), is called an optimal injection profile.

######  Definition 4.

Let $\mathcal{T}^{n}$ be an optimal injection profile for $n$ slugs. If there
exists the pointwise limit $\mathcal{T}^{\infty}$ of $\mathcal{T}^{n}$ as
$n\to\infty$ it is called an optimal limiting injection profile.

Let us now consider specific models used to estimate the growth of the mixing
zone.

### TFE model

[16, 17]. Rigorous pessimistic estimates for the velocities of the mixing zone
ends were made under the assumption of transverse flow equilibrium condition
(TFE). According to this model, the velocities of front end and the back end
of the $j$-th mixing zone can be estimated by:

$\displaystyle
v^{f}_{j}\leqslant\frac{\mathop{\overline{m}}(c_{j},c_{j+1})}{m(c_{j})},\qquad
v^{b}_{j}\geqslant\frac{\mathop{\overline{m}}(c_{j},c_{j+1})}{m(c_{j+1})},$
(7)

where

$\displaystyle\mathop{\overline{m}}(a,b)=\frac{1}{b-a}\int\limits_{a}^{b}m(c)\,dc$

is the mean value of the function $m$ on the interval $(a,b)$. In what follows
for TFE model we will consider the velocities $v_{j}^{f}$ and $v_{j}^{b}$ to
be equal to their pessimistic estimates (equalities in (7)).

### Generalized Koval model

It is natural to conjecture that velocities of the leading and the trailing
edge of $j$-mixing zone depend on the ratio of viscosities of the
corresponding concentrations $c_{j}$ and $c_{j+1}$, that is for any partition
${\bf c}=(c_{1},\ldots,c_{n+1})$ we have

$\displaystyle v_{j}^{f}=\frac{1}{f\left(\frac{m(c_{j+1})}{m(c_{j})}\right)},$
$\displaystyle v_{j}^{b}=f\left(\frac{m(c_{j+1})}{m(c_{j})}\right),$
$\displaystyle j=1,\ldots,n.$ (8)

We will assume the following properties of $f$ and $m$:

  1. (A)

$f\in C^{1}[1,M]$, where $M=\frac{m(c_{\min})}{m(c_{\max})}$, $m\in
C^{1}[c_{\min},c_{\max}]$;

  2. (B)

$f(1)=1$, $f>0$ and $f$ is decreasing;

  3. (C)

$f(ab)\leqslant f(a)f(b)$ for any $a,b\in[1,M]$ such that $ab\leqslant M$;

  4. (D)

$f\left(\frac{m(c^{\prime})}{m(c)}\right)$ is a convex function of $c$ for any
$c^{\prime}\in[c_{\min},c_{\max}]$, $c<c^{\prime}$.

The famous empirical models (Koval [12], Todd-Longstaff [14]) are of type (8)
with $f$:

$\displaystyle f_{K}(x)=(\alpha\cdot x^{1/4}+(1-\alpha))^{-4},$ $\displaystyle
f_{TL}(x)=x^{-\omega}.$

Here and later on “K” stands for Koval and “TL” for Todd-Longstaff. In
applications usually parameter $\alpha\in(0,1)$ is taken to be equal to
$0.22$; the miscibility parameter $\omega\in(0,1]$ usually selected according
to the data and sometimes is taken to be equal to $2/3$. In [13] there was an
attempt to rigorously derive Koval model, which gave rise to naive Koval
model, corresponding to TL model with $\omega=1$. It is easy to see that both
Koval and TL models satisfy conditions (A)–(C). Notice that condition (D) is a
restriction on mobility functions $m$ that we consider.

The main purpose of this article is to find the shape of the optimal limiting
polymer injection profile. For TFE and generalized Koval models we give the
answer in Theorem 1.

######  Theorem 1.

Under the assumptions described above, the optimal limiting injection profile
$\mathcal{T}^{\infty}$ exists and has the form

$\mathcal{T}^{\infty}(c)=1-\left(\frac{m(c_{1})}{m(c)}\right)^{\beta}=1-\left(\frac{\mu(c)}{\mu(c_{1})}\right)^{\beta}\,$

with $\beta=1$ in case of TFE and $\beta=-2f^{\prime}(1)$ in case of
generalized Koval model.

######  Remark 3.

In particular, for Koval model we have $\beta=2\alpha$, which is in agreement
with [9] for $\alpha=0.22$. For TL model we obtain $\beta=2\omega$.

##  3 Proof of the main result

Let ${\bf c}$ be a partition of $[c_{\min},c_{\max}]$. In what follows we will
need the notion of a rank of the partition ${\bf c}$:

$\displaystyle\delta({\bf c}):=\max\limits_{1\leq j\leq n}|c_{j}-c_{j+1}|.$

The proof of Theorem 1 consists of two parts: the existence of the optimal
limiting injection profile and finding it’s exact form. Using Lemmas 1–2 we
show the existence of the limiting profile and this is the most technical part
of the proof.

Lemma 1 shows that for any optimal $n$-configuration there exists an
$(n+1)$-configuration with less amount of polymer mass, so under the
assumptions above it is always profitable to increase number of slugs. Note
that it is not always the case (see Rem. 4).

######  Lemma 1.

Let $({\bf c},{\bf t})$ be an optimal $n$-configuration with volume $V_{n}$.
Then there exists an $(n+1)$-configuration $(\widetilde{\bf c},\widetilde{\bf
t})$ with volume $V_{n+1}$ and a function $\varphi$ such that

$\displaystyle V_{n}({\bf c})-\varphi(\delta({\bf c}))>V_{n+1}(\widetilde{\bf
c},\widetilde{\bf t}).$

Here function $\varphi:(0,c_{\max}-c_{\min}]\to\mathbb{R}_{+}$ is continuous,
non-decreasing and strictly positive.

###### Proof.

Fix an index $k\in\\{1,\ldots,n\\}$ such that
$k:=\mathrm{argmax}|c_{k}-c_{k+1}|$ and consider a new vector of
concentrations $\widetilde{{\bf c}}$:

$\displaystyle{\bf c}$
$\displaystyle=(c_{1},\ldots,c_{k},c_{k+1},\ldots,c_{n+1}),$
$\displaystyle\widetilde{\bf c}:$
$\displaystyle=(c_{1},\ldots,c_{k},\tilde{c},c_{k+1},\ldots,c_{n+1}),$

for some $\widetilde{c}\in[c_{k+1},c_{k}]$, which we will define later. Define
$\widetilde{\bf t}$ such that the relation (6) holds. For a configuration
$(\widetilde{\bf c},\widetilde{\bf t})$ we will use the same system of
notations from formulas (4), (7), (8) by equipping the corresponding symbols
with a tilde. Then

$\displaystyle V({\bf c})-V(\widetilde{\bf c})$
$\displaystyle=\sum\limits_{i=1}^{k-1}(c_{i}-c_{i+1})(T_{i}-\widetilde{T}_{i})+\sum\limits_{i=k+1}^{n+1}(c_{i}-c_{i+1})(T_{i}-\widetilde{T}_{i+1})+$
(9)
$\displaystyle+(c_{k}-c_{k+1})T_{k}-((c_{k}-\widetilde{c})\widetilde{T}_{k}+(\widetilde{c}-c_{k+1})\widetilde{T}_{k+1}).$

We claim that for both TFE and generalized Koval models the following holds:

  1. (i)

$T_{i}=\widetilde{T}_{i}$ for $i\leqslant k-1$;

  2. (ii)

$T_{i}\geqslant\widetilde{T}_{i+1}$ for $i\geqslant k+1$;

  3. (iii)

there exists $\tilde{c}$ and a continuous strictly positive function $\varphi$
such that

$\displaystyle\Delta_{k}(\widetilde{\bf
c}):=(c_{k}-c_{k+1})T_{k}-((c_{k}-\widetilde{c})\widetilde{T}_{k}+(\widetilde{c}-c_{k+1})\widetilde{T}_{k+1})\geqslant\varphi(\delta({\bf
c})).$

It is easy to see that Lemma 1 follows from (i)–(iii) and relation (9).

Consider TFE model. Formula (6) for $T_{j}$ (for any $j=2,\ldots,n$)
simplifies significantly due to telescopic cancellations

$\displaystyle T_{j}=1-\frac{m(c_{1})}{\mathop{\overline{m}}(c_{j},c_{j+1})}.$
(10)

Using formula (10), we get that $T_{i}=\widetilde{T}_{i}$ for $i\leqslant
k-1$, $i\geqslant k+1$ and (i)–(ii) are true.

Let us prove (iii). Notice that for TFE model $\Delta_{k}(\widetilde{\bf
c})=\Delta_{k}(c_{k},\widetilde{c},c_{k+1})$. Introducing
$\lambda=(c_{k}-\widetilde{c})/(c_{k}-c_{k+1})\in[0,1]$ and rewriting
$\Delta_{k}$, we get

$\displaystyle\Delta_{k}(c_{k},\widetilde{c},c_{k+1})=(c_{k}-c_{k+1})(T_{k}-\lambda\widetilde{T}_{k}-(1-\lambda)\widetilde{T}_{k+1}).$

First, let us show that $\Delta_{k}>0$ for any
$\widetilde{c}\in(c_{k+1},c_{k})$, or equivalently for $\lambda\in(0,1)$. By
formula (10) the inequality $\Delta_{k}>0$ is equivalent to

$\lambda\frac{1}{\mathop{\overline{m}}(c_{k},\widetilde{c})}+(1-\lambda)\frac{1}{\mathop{\overline{m}}(\widetilde{c},c_{k+1})}>\frac{1}{\mathop{\overline{m}}(c_{k},c_{k+1})},$

and can be rewritten as

$\frac{\lambda}{A}+\frac{1-\lambda}{B}>\frac{1}{\lambda A+(1-\lambda)B}$

with $A=\mathop{\overline{m}}(c_{k},\widetilde{c})$ and
$B=\mathop{\overline{m}}(\widetilde{c},c_{k+1})$ and obviously follows from
the convexity of $1/x$ for $x>0$. Note that $\Delta_{k}=0$ when
$\widetilde{c}=c_{k}$ or $\widetilde{c}=c_{k+1}$, or equivalently $\lambda=0$
or $\lambda=1$.

Secondly, the existence of function $\varphi$ follows from the compactness
argument. Define

$\displaystyle\varphi(d):=\min\limits_{|c_{k}-c_{k+1}|\geqslant
d}\left(\max\limits_{\widetilde{c}\in[c_{k+1},c_{k}]}\Delta_{k}(c_{k},\widetilde{c},c_{k+1})\right).$
(11)

Since $\Delta_{k}$ is a continuous function defined on a compact set, we
obtain $\varphi$ to be continuous and strictly positive. By definition,
$\varphi$ is non-decreasing. Taking
$\widetilde{c}:=\mathrm{argmax}\,\Delta_{k}(c_{k},\widetilde{c},c_{k+1})$ for
fixed values of $c_{k},c_{k+1}\in[c_{\min},c_{\max}]$, and $\varphi$ from
formula (11), we get

$\displaystyle\Delta_{k}\geqslant\varphi(c_{k}-c_{k+1})=\varphi(\delta({\bf
c})),$

where the last inequality is true by the choice of $k$. This completes the
proof of Lemma 1 for TFE model.

Consider generalized Koval model. From formula (6) we obtain

$\displaystyle T_{j}$
$\displaystyle=1-f\left(\frac{m(c_{j+1})}{m(c_{j})}\right)\cdot g_{j}({\bf
c});$ $\displaystyle g_{j}({\bf
c})=\prod\limits_{i=1}^{j-1}f^{2}\left(\frac{m(c_{i+1})}{m(c_{i})}\right).$
(12)

Using formula (12), we obtain $T_{i}=\widetilde{T}_{i}$ for $i\leqslant k-1$.
The inequality (ii) for any $i\geqslant k+1$ is equivalent to

$\displaystyle f^{2}\left(\frac{m(c_{k+1})}{m(c_{k})}\right)\leqslant
f^{2}\left(\frac{m(\widetilde{c})}{m(c_{k})}\right)\cdot
f^{2}\left(\frac{m(c_{k+1})}{m(\widetilde{c})}\right),$

and is true due to assumption (C) on function $f$.

Let us prove (iii). Introducing
$\lambda=(c_{k}-\widetilde{c})/(c_{k}-c_{k+1})\in[0,1]$ and using formulas
(12), we can rewrite $\Delta_{k}$ in the following form

$\displaystyle\Delta_{k}(\widetilde{\bf c})=g_{k}({\bf
c})\cdot(c_{k}-c_{k+1})\cdot\widetilde{\Delta}_{k}(c_{k},\widetilde{c},c_{k+1}),$

where $\widetilde{\Delta}_{k}$ is defined as

$\displaystyle\widetilde{\Delta}_{k}:=\lambda
f\left(\frac{m(\widetilde{c})}{m(c_{k})}\right)+(1-\lambda)f^{2}\left(\frac{m(\widetilde{c})}{m(c_{k})}\right)f\left(\frac{m(c_{k+1})}{m(\widetilde{c})}\right)-f\left(\frac{m(c_{k+1})}{m(c_{k})}\right).$

First, let us show that $\Delta_{k}>0$ for any
$\widetilde{c}\in(c_{k+1},c_{k})$, or equivalently for $\lambda\in(0,1)$. It
is clear that $g_{k}>0$ and $(c_{k}-c_{k+1})>0$. The inequality
$\widetilde{\Delta}_{k}>0$ is true due to assumptions (B)–(D) on $f$ and $m$.
Indeed,

$\displaystyle\cfrac{f\left(\frac{m(c_{k+1})}{m(c_{k})}\right)}{f\left(\frac{m(\widetilde{c})}{m(c_{k})}\right)}$
$\displaystyle\stackrel{{\scriptstyle\text{(C)}}}{{\leqslant}}f\left(\frac{m(c_{k+1})}{m(\widetilde{c})}\right)\stackrel{{\scriptstyle\text{(D)}}}{{<}}\lambda
f\left(\frac{m(c_{k+1})}{m(c_{k+1})}\right)+(1-\lambda)f\left(\frac{m(c_{k+1})}{m(c_{k})}\right)\stackrel{{\scriptstyle\text{(B)}}}{{=}}$
$\displaystyle\stackrel{{\scriptstyle\text{(B)}}}{{=}}\lambda+(1-\lambda)f\left(\frac{m(c_{k+1})}{m(c_{k})}\right)\stackrel{{\scriptstyle\text{(C)}}}{{\leqslant}}\lambda+(1-\lambda)f\left(\frac{m(\widetilde{c})}{m(c_{k})}\right)f\left(\frac{m(c_{k+1})}{m(\widetilde{c})}\right).$

Secondly, by the same compactness argument as for TFE model, we can show that
there exists $\tilde{c}\in(c_{k+1},c_{k})$ and a function
$\widetilde{\varphi}:\,(0,c_{\max}-c_{\min}]\to\mathbb{R}_{+}$ such that

$\displaystyle\widetilde{\Delta}_{k}\geqslant\widetilde{\varphi}(c_{k}-c_{k+1}).$

Note that $\widetilde{\varphi}$ is continuous, non-decreasing and strictly
positive.

Thirdly, let us prove that $g_{k}({\bf c})$ is separated from zero. Consider a
function $z(x,y)=\ln\left(f\left(\frac{m(x)}{m(y)}\right)\right)$ for
$x,y\in[c_{\min},c_{\max}]$ and $x\leqslant y$. By condition (A), we see that
$z$ is a Lipschitz function. Thus there exists a positive constant $K>0$ such
that

$\displaystyle|z(x,y)-z(x,x)|=|z(x,y)|\leqslant K|x-y|.$

This implies $g_{k}\geqslant e^{-2K}$ due to inequalities

$\displaystyle|\ln\left(g_{k}({\bf c})\right)|\leqslant
2\sum\limits_{i=1}^{k-1}\left|\ln\left(f\left(\frac{m(c_{i+1})}{m(c_{i})}\right)\right)\right|\leqslant
2\sum\limits_{i=1}^{k-1}|c_{j+1}-c_{j}|K\leqslant 2K.$

Finally, we obtain

$\displaystyle\Delta_{k}(\widetilde{\bf c})\geqslant
e^{-2K}(c_{k}-c_{k+1})\widetilde{\varphi}(c_{k}-c_{k+1})=:\varphi(c_{k}-c_{k+1})=\varphi(\delta({\bf
c})),$

where the last inequality is true by the choice of $k$. This completes the
proof of Lemma 1 for generalized Koval model. ∎

######  Remark 4.

For TL model in condition (C) the equality holds $f(ab)=f(a)f(b)$. So
$m^{\omega}$ is convex if and only if for any 1-configuration ${\bf
c}=(c_{1},c_{2})$ no matter what intermediate concentration
$\widetilde{c}\in(c_{1},c_{2})$ you add, there will be gain in polymer mass.
So the convexity condition (D) provides the possibility of passing from
$n$-configuration to $(n+1)$-configuration and as we will see guarantees the
existence of a continuous limiting injection profile.

Consider an example where condition (D) on $m^{\omega}$ is not satisfied. Take
$m^{\omega}(c)=1/(1+c^{3})$, which corresponds to $\mu(c)=(1+c^{3})^{3/2}$ and
$\omega=2/3$. Note that the graph of $m^{\omega}$ lies above the segment,
connecting points $(c_{1},m^{\omega}(c_{1}))$ and $(c_{2},m^{\omega}(c_{2}))$,
so following the proof of Lemma 1 we get that any $2$-configuration is less
optimal than $1$-configuration. Dependence of the volume function on
$\widetilde{c}$ is given in Fig. 4. In this case we won’t get any limiting
profile as we can’t even replace a 1-configuration with a better
2-configuration.

Figure 4: An example where GVB technology doesn’t give positive results
according to TL model. Left: graph of $m^{\omega}$; right: dependence of the
volume of the polymer on the concentration of the second slug for the non-
convex $m^{\omega}$, Todd-Longstaff model

######  Lemma 2.

Let $({\bf c}^{n},{\bf t}^{n})$ be a sequence of optimal $n$-configurations.
Then
$\delta({\bf c}^{n})\to 0$ as $n\to+\infty$.

###### Proof.

Proof by contradiction. Fix $\varepsilon$ and consider a subsequence
$\\{n_{k}\\}$ such that

$\displaystyle|c_{j_{n_{k}}}^{n_{k}}-c_{j_{n_{k}}+1}^{n_{k}}|\geq\varepsilon.$

Using Lemma 1, we obtain that there exists a function
$\varphi=\varphi(\delta({\bf c}^{n_{k}}))$, such that for any configuration
${\bf c}^{n_{k}}$ there exists a configuration ${\bf c}^{n_{k}+1}$ with gain
in polymer mass at least $\varphi(\delta({\bf c}^{n_{k}}))$, that is:

$\displaystyle V({\bf c}^{n_{k}},{\bf t}^{n_{k}})>V({\bf c}^{n_{k}+1},{\bf
t}^{n_{k}+1})+\varphi(\delta({\bf c}^{n_{k}}))\geqslant V({\bf
c}^{n_{k}+1},{\bf t}^{n_{k}+1})+\varphi(\varepsilon),$ (13)

where the last inequality is true by monotonocity of $\varphi$. Note that the
sequence of $V({\bf c}^{n_{k}},{\bf t}^{n_{k}})$, $k\to\infty$, has a limit
$V^{\infty}$ as non-increasing and non-negative. So starting from some $N_{0}$
for all $n_{k}>N_{0}$ we have

$\displaystyle V^{\infty}+\frac{\varphi(\varepsilon)}{2}>V({\bf
c}^{n_{k}},{\bf t}^{n_{k}})>V^{\infty}.$ (14)

Combining (13) and (14) we arrive at a contradiction, since

$\displaystyle V^{\infty}+\frac{\varphi(\varepsilon)}{2}>V({\bf
c}^{n_{k}},{\bf t}^{n_{k}})$ $\displaystyle>V({\bf c}^{n_{k}+1},{\bf
t}^{n_{k}+1})+\varphi(\varepsilon)\geqslant$ $\displaystyle\geqslant V({\bf
c}^{n_{k+1}},{\bf
t}^{n_{k+1}})+\varphi(\varepsilon)>V^{\infty}+\varphi(\varepsilon).$

∎

Now we can prove the main Theorem 1.

###### Proof.

Fix $c\in[c_{\min},c_{\max}]$. For every $n$ choose $j_{n}$, such that
$c_{j_{n}+1}^{n}\leq c<c_{j_{n}}^{n}$. Since $\delta({\bf c}^{n})\to 0$ by
Lemma 2, we obtain

$c_{j_{n}}^{n},c_{j_{n}+1}^{n}\to c,\qquad n\to\infty.$

Consider TFE model. Using (10) we get

$\displaystyle
1-\frac{m(c_{1})}{m(c_{j_{n}}^{n})}\leqslant\mathcal{T}^{n}(c)\leqslant
1-\frac{m(c_{1})}{m(c_{j_{n}+1}^{n})},$

thus $\mathcal{T}^{n}\to\mathcal{T}^{\infty}$ by the squeeze theorem.

Consider generalized Koval model. Using formula (12), we get

$\displaystyle
1-\mathcal{T}^{n}(c)=f\left(\frac{m(c_{j_{n}+1}^{n})}{m(c_{j_{n}}^{n})}\right)\cdot\prod\limits_{k=1}^{j_{n}-1}f^{2}\left(\frac{m(c_{k+1}^{n})}{m(c_{k}^{n})}\right).$
(15)

The key idea is the following relation:

$\displaystyle
f\left(\frac{m(x)}{m(y)}\right)=\left(\frac{m(x)}{m(y)}\right)^{f^{\prime}(1)}(1+h(x,y)).$
(16)

Due to Taylor formula and conditions (A) and (B) on $f$ and $m$ the following
estimate for the residue function $h$ holds:

$\widetilde{h}(d):=\max_{|x-y|\leq d}\dfrac{|h(x,y)|}{|x-y|}\to
0\qquad\text{as }d\to 0.$

Substituting (16) into (15), we obtain

$1-\mathcal{T}^{n}(c)=\left(\frac{m(c_{j_{n}+1}^{n})}{m(c_{j_{n}}^{n})}\right)^{f^{\prime}(1)}\prod\limits_{k=1}^{j_{n}-1}\left(\frac{m(c_{k+1}^{n})}{m(c_{k}^{n})}\right)^{2f^{\prime}(1)}\cdot
H^{n}_{j_{n}},$ (17)
$H_{j_{n}}^{n}:=(1+h(c_{j_{n}+1}^{n},c_{j_{n}}^{n}))\prod_{k=1}^{j_{n}-1}(1+h(c_{k+1}^{n},c_{k}^{n}))^{2}.$

Consider $n\geq N$, such that $\widetilde{h}(\delta({\bf
c}^{n}))(c_{\max}-c_{\min})<\frac{1}{2}$. By the definition of the function
$\widetilde{h}$ we have

$\forall k=1,\ldots,j_{n},\qquad
h(c_{k+1}^{n},c_{k}^{n})\leq\widetilde{h}(\delta({\bf
c}^{n}))(c_{k}^{n}-c_{k+1}^{n}).$

Thus, from the standard inequality for the logarithm

$\dfrac{x}{x+1}\leq\ln(1+x)\leq x$

we obtain an estimate

$-4\widetilde{h}(\delta({\bf c}^{n}))(c_{\max}-c_{\min})\leq\ln
H_{j_{n}}^{n}\leq 2\widetilde{h}(\delta({\bf
c}^{n}))(c_{\max}-c_{\min}),\qquad n\geq N.$ (18)

Combining (17) and (18) for $n\geq N$ we arrive at

$\left(\frac{m(c^{n}_{j_{n}})m(c^{n}_{j_{n}+1})}{m(c^{n}_{1})^{2}}\right)^{f^{\prime}(1)}\gamma^{-4\widetilde{h}(\delta({\bf
c}^{n}))}\leq
1-\mathcal{T}^{n}(c)\leq\left(\frac{m(c^{n}_{j})m(c^{n}_{j_{n}+1})}{m(c^{n}_{1})^{2}}\right)^{f^{\prime}(1)}\gamma^{2\widetilde{h}(\delta({\bf
c}^{n}))},$

where $\gamma=\exp(c_{\max}-c_{\min})$. Thus as $n\to\infty$ the statement
follows immediately. ∎

##  4 Numerical solution for several slugs

For a finite number of slugs, the optimization problem can be solved using
numerical algorithms, for example, the conjugate gradient method. The results
for $n$ slugs ($n=2,5,10,50$) and optimal limiting injection profiles are
shown in Fig. 5 and 6.

Theorem 1 for the TFE and generalized Koval models answer the question of how
much polymer maximum can be saved. Define the polymer mass in comparison to
one slug gain as

$\displaystyle\eta_{n}:=\frac{V_{1}-V_{n}}{V_{1}},$

where $V_{1}$ is the value of the volume function (4) for the optimal
1-configuration and $V_{n}$ is the value of the volume function (4) for the
optimal $n$-configuration. $V_{1}$ and $V_{n}$ can be found as

$\displaystyle V_{1}=1-\frac{1}{v^{f}_{1}},$ $\displaystyle
V_{n}=\int_{c_{\min}}^{c_{\max}}\mathcal{T}^{n}(c)\;dc.$

The dependence of the polymer mass gain in comparison to one slug on the
number of slugs for the TFE, Todd-Longstaff, naive Koval and Koval models are
given in the Tables 1 and 2.

As follows from the Tables 1 and 2, after about 5 slugs, the polymer gain
remains practically unchanged and is almost equal to its limit value. Hence,
in practice it makes no sense to inject more than 5 slugs.

Figure 5: Optimal injection profiles for $n$ slugs, $n=2,5,10,50$, and
limiting optimal injection profiles for the TFE, Todd-Longstaff, naive Koval
and Koval models, $\mu(c)=1+9c$.

Figure 6: Optimal injection profiles for $n$ slugs, $n=2,5,10,50$, and limiting optimal injection profiles for the TFE, Todd-Longstaff, naive Koval and Koval models, $\mu(c)=\exp(c\ln 10)$. | n = 2 | n = 3 | n = 4 | n = 5 | n = 10 | Limit
---|---|---|---|---|---|---
TFE | 19,83% | 23,35% | 24,57% | 25,13% | 25,88% | 26,12%
Todd-Longstaff | 24,84% | 29,36% | 30,93% | 31,66% | 32,63% | 32,95%
naive Koval | 22,50% | 26,67% | 28,12% | 28,80% | 29,70% | 30,00%
Koval | 33,21% | 39,24% | 41,46% | 42,55% | 44,24% | 45,28%
Table 1: The dependence of the polymer mass gain in comparison to one slug on the number of slugs, $\mu(c)=1+9c$ | n = 2 | n = 3 | n = 4 | n = 5 | n = 10 | Limit
---|---|---|---|---|---|---
TFE | 13,24% | 15,93% | 16,89% | 17,34% | 17,94% | 18,14%
Todd-Longstaff | 9,07% | 10,77% | 11,36% | 11,64% | 12,01% | 12,13%
naive Koval | 9,52% | 11,32% | 11,96% | 12,25% | 12,64% | 12,78%
Koval | 13,06% | 16,14% | 17,47% | 18,22% | 19,57% | 20,75%
Table 2: The dependence of the polymer mass gain in comparison to one slug on
the number of slugs, $\mu(c)=\exp(c\ln 10)$

##  5 Acknowledgement

Theorem 1 and its proof in Section 3 was supported by the Russian Science
Foundation grant 19-71-30002. The rest of the paper was supported by President
Grant 075-15-2019-204, August Moebius Contest, and Ministery of Science and
Education of Russian Federation, grant 075-15-2019-1619.

## References

  * [1] S. Berg and H. Ott.  Stability of CO2–brine immiscible displacement.  International Journal of Greenhouse Gas Control, 11:188–203, November 2012.
  * [2] J. Hagoort.  Displacement Stability of Water Drives in Water-Wet Connate-Water-Bearing Reservoirs.  Society of Petroleum Engineers Journal, 14(01):63–74, February 1974\.
  * [3] M.J. Blunt, J.W. Barker, B. Rubin, M. Mansfield, I.D. Culverwell, and M.A. Christie.  Predictive Theory for Viscous Fingering in Compositional Displacement.  SPE Reservoir Engineering, 9(01):73–80, February 1994.
  * [4] F. Bakharev, L. Campoli, A. Enin, S. Matveenko, Y. Petrova, S. Tikhomirov, and A. Yakovlev.  Numerical Investigation of Viscous Fingering Phenomenon for Raw Field Data.  Transport in Porous Media, 132(2):443–464, March 2020.
  * [5] R.L. Chuoke, P. Van Meurs, and C. van der Poel.  The instability of slow, immiscible, viscous liquid-liquid displacements in permeable media.  Transactions of the AIME, 216(01):188–194, 1959.
  * [6] H.D. Outmans.  Nonlinear Theory for Frontal Stability and Viscous Fingering in Porous Media.  Society of Petroleum Engineers Journal, 2(02):165–176, June 1962\.
  * [7] R.L. Perrine.  Stability Theory and Its Use to Optimize Solvent Recovery of Oil.  Society of Petroleum Engineers Journal, 1(01):9–16, March 1961\.
  * [8] R.L. Perrine.  The Development of Stability Theory for Miscible Liquid-Liquid Displacement.  Society of Petroleum Engineers Journal, 1(01):17–25, March 1961\.
  * [9] E.L. Claridge.  A Method for Designing Graded Viscosity Banks.  Society of Petroleum Engineers Journal, 18(05):315–324, October 1978.
  * [10] J.S. Nijjer, D.R. Hewitt, and J.A. Neufeld.  The dynamics of miscible viscous fingering from onset to shutdown.  Journal of Fluid Mechanics, 837:520–545, February 2018.
  * [11] F. Bakharev, A. Enin, A. Groman, A. Kalyuzhnuk, S. Matveenko, Yu Petrova, I. Starkov, and S. Tikhomirov.  Velocity of viscous fingers in miscible displacement.  arXiv:2012.02849, December 2020.
  * [12] E.J. Koval.  A Method for Predicting the Performance of Unstable Miscible Displacement in Heterogeneous Media.  Society of Petroleum Engineers Journal, 3(02):145–154, June 1963\.
  * [13] R.J.S. Booth.  On the growth of the mixing zone in miscible viscous fingering.  Journal of Fluid Mechanics, 655:527–539, July 2010.
  * [14] M.R. Todd and W.J. Longstaff.  The Development, Testing, and Application Of a Numerical Simulator for Predicting Miscible Flood Performance.  Journal of Petroleum Technology, 24(07):874–882, July 1972.
  * [15] G. Menon and F. Otto.  Dynamic Scaling in Miscible Viscous Fingering.  Communications in Mathematical Physics, 257(2):303–317, July 2005\.
  * [16] G. Menon and F. Otto.  Diffusive slowdown in miscible viscous fingering.  Communications in Mathematical Sciences, 4(1):267–273, 2006.
  * [17] Y.C. Yortsos and D. Salin.  On the selection principle for viscous fingering in porous media.  Journal of Fluid Mechanics, 557:225, June 2006.
  * [18] D.W. Peaceman and H.H. Rachford.  Numerical Calculation of Multidimensional Miscible Displacement.  Society of Petroleum Engineers Journal, 2(04):327–339, December 1962.


# Optimal and Efficient Binary Questioning for Human-in-the-Loop Annotation

Franco Marchesoni-Acland
SLB, Centre Borelli
<EMAIL_ADDRESS>
&Jean-Michel Morel
Centre Borelli
Université Paris-Saclay
Josselin Kherroubi
SLB
<EMAIL_ADDRESS>&Gabriele Facciolo
Centre Borelli
Université Paris-Saclay

###### Abstract

Even though data annotation is extremely important for interpretability,
research and development of artificial intelligence solutions, most research
efforts such as active learning or few-shot learning focus on the sample
efficiency problem. This paper studies the neglected complementary problem of
getting annotated data given a predictor. For the simple binary classification
setting, we present the spectrum ranging from optimal general solutions to
practical efficient methods. The problem is framed as the full annotation of a
binary classification dataset with the minimal number of yes/no questions when
a predictor is available. For the case of general binary questions the
solution is found in coding theory, where the optimal questioning strategy is
given by the Huffman encoding of the possible labelings. However, this
approach is computationally intractable even for small dataset sizes. We
propose an alternative practical solution based on several heuristics and
lookahead minimization of proxy cost functions. The proposed solution is
analysed, compared with optimal solutions and evaluated on several synthetic
and real-world datasets. On these datasets, the method allows a significant
improvement ($23-86\%$) in annotation efficiency.

##  1 Introduction

Deep supervised learning has been key to advancing artificial intelligence
(AI) and solving practical problems. Even now, with the advent of more
powerful self-supervised methods, human feedback is essential to ensure proper
deployment and correct downstream performance [2, 25]. Annotated datasets help
researchers evaluate performances on tasks that can be as subjective as image
enhancement [9] and allow engineers to fine-tune self-supervised predictors on
downstream tasks. Although rarely perfect, datasets are fundamental for AI
research and development, yet the quick annotation of datasets is still an
open problem.

There is a strong relation between data and (trained) predictors. A large
portion of the last decade of research focused on supervised learning, i.e. on
obtaining better predictors given some annotated data. More recently the
research evolved and refocused into sampling efficiency considerations, as
seen in active learning (AL), few-shot learning (FSL) or semi-supervised
learning. Alternatively, data availability was considered by the self-
supervised learning or weakly-supervised learning fields. Virtually all these
fields study the path from data to predictors. In contrast, there have been
very few works (e.g. [15]) studying the path from predictors to data. This
opposite direction lies in the core of quick or intelligent annotation (IA)
solutions, i.e. methods that allow a human to quickly annotate a dataset. Most
of these methods have a predictor of some sort or could benefit from one.

From a higher level, human-in-the-loop learning (HILL) comprises methods that
involve the interaction between a human and a machine with a teaching/learning
aim. The most basic way for a human to teach a machine a task is not HILL but
is still widely used: the human simply annotates a dataset and a predictor is
trained on it. More sophisticated methods involve annotating the dataset by
leveraging a fixed generalistic predictor, as it is done in interactive image
segmentation [18, 23]. In the case where the stopping criteria for annotation
is a performance threshold the HILL solution of active learning allows
reducing the annotation effort by stopping the annotation earlier. What has
been largely missing from these solutions is using the predictor to reduce the
annotation cost. Leveraging a predictor has been shown to increase annotation
efficacy in practice [15] and in theory [21, 33].

The importance of data annotation follows from the importance of annotated
data. Even though there are some problems that are truly self-supervised in
the sense of not requiring any human supervision (e.g. generative text models
[32]), many of those solutions require some supervision for finetuning [25,
23] or alignment [2]. Of course, annotated data is not only used for
development but also for testing and comparing predictors.

The present work analyses the quick annotation problem for the binary
classification setting. The quick annotation problem involves finding the
method that annotates more samples with the least number of yes/no answers.
The direction goes from predictor to data, opposite to the usual data-to-
predictor direction. Most of the paper considers the oracle case in which a
reasonably good predictor is available. As discussed in Section 6, the very
best solutions will likely combine quick model training (AL) with quick
annotation (IA). We study the latter and only explore the combination naively
by the end of the paper.

The rest of the paper is organized as follows: Section 2 presents the related
work on semi- and self-supervised learning, active learning, and a few key
papers related to ours. Section 3 introduces the general binary questioning
case, its relation with information theory, and the solutions given by Huffman
encoding and tree search. The proposed method based on rollout is introduced
in Section 4, along with the heuristics that make it computationally feasible.
Section 5 presents the experimental results on synthetic and real datasets for
the oracular and the more realistic HILL case. Lastly, we revise the
limitations of our method, explore its implementation into a tool and conclude
our work in Section 6.

The contributions of this work are the following:

  1. 1.

We theoretically link IA to Huffmann encoding and explain why it cannot be a
feasible solution.

  2. 2.

We propose the first intelligent annotation (IA) method for binary
classification that reduces annotation cost by $\approx 20\%\text{ to }88\%$
in the oracle case and by $\approx 70\%$ in the harder from-scratch setting.

##  2 Related work

###  2.1 Active Learning

AL methods are commonly evaluated by looking at the test performance vs.
number of annotations curve [27]. Most research explores methods to select the
observations to annotate next to optimally help model training. The methods
can be understood through the lenses of Bayesian estimation and information
theory [19]. The number of observations to be selected is called budget and it
is usually big, e.g. 5000 labels [34]. Batch AL is especially relevant because
neural networks are trained using batches and more importantly, because in
practice it is more convenient to ask the annotator to annotate many
observations at once.

One underlying assumption in many AL works [1, 11] is that the annotation cost
of an observation is constant, irrespective of the type of problem, e.g.
regression or classification, and irrespective of the complexity of the
annotation, e.g. multi-class with 4 vs. 1000 classes. Although the annotation
cost of an observation is not constant in most of the cases, it is useful to
assume so to keep the focus on the sample efficiency problem.

As will be seen in Section 6, AL is an important component of a full solution
to the HILL problem. What AL has been missing and this work studies is the
annotation advantage one can get by using the predictor being trained. Both AL
and IA can be studied simultaneously in the binary classification problem,
where the number of annotations equals the number of yes/no answers in the AL
case. In fact, we integrate the most traditional AL methods, namely entropy,
least confidence sampling and margin sampling, into our IA solution. Note that
in the binary classification case all these are reduced to selecting the
samples whose assigned probabilities are closer to $0.5$. We note that even
though many other methods exist [34, 19], simple entropy-based AL is still
extremely competitive [4].

Our work complements active learning in that it can be used to fullfil each
one of the batched requests AL yields. However, we deviate from AL with an
assumption that is not true in general and is opposite and incompatible with
the assumption made in AL: to study intelligent annotation we assume that the
annotation cost is given by the number of yes/no answers the annotator needs
to provide. For instance, if the annotator is asked “are these 3 observations
positive?” it could suffice with one “yes” to get 3 annotations and the
annotation cost of that set of 3 observations would be 1. To answer that
question the annotator should look at all annotations at once, and the actual
time it takes to get the answer is most likely somewhere between the cost as
in AL ($=3$) and the cost as in IA ($=1$).

###  2.2 Semi and self-supervised learning

Semi-supervised learning can improve model training via the use of the
unlabeled data[35, 29]. One important strategy in semi-supervised learning is
self-training or pseudo-labeling. Although we regard these as ways to further
improve model training, pseudo-labeling is interesting from the data
annotation point of view. For instance, the recently released SAM dataset [18]
is fully composed of automatic annotations.

Lastly, self-supervised learning [3] can be roughly divided into noisy
autoencoding and contrastive learning. Contrastive learning is indirectly
supervised [10] via the definition of the invariance and equivariance
conditions the predictor should satisfy. We do not consider data augmentation
nor contrastive learning to limit the amount of supervision but we note that
prior knowledge is still present for instance in architectural choices or
weight-initialization strategies. Of course, if such supervision is available
in practice its use is recommended. Similarly, we consider the self-supervised
techniques of noisy autoencoding as smart weight-initialization procedures.
Semi-supervised learning and self-supervised learning are still very active
fields that aim to improve weight initialization and model training. For
simplicity, this work ignores most of those advances and builds upon
traditional blocks, namely a ResNet18 [14], the Adam optimizer [17] and the
binary cross-entropy loss, but a good product should integrate everything.

###  2.3 Intelligent annotation

There are two notable theoretical analysis of this problem. The first [21]
formalizes the problem in a way that inspires the one presented in Section 3.
A key piece of the formalization is the introduction of a concept $c$. A way
to see it is to let the concept $c$ be the subset of the samples $X$ composed
by the samples with positive label. Then there is a one-to-one mapping between
$c$ and binary vectors $y\in[0,1]^{|X|}$, where $y$ is the vector of labels
$(y_{1},\dots,y_{|X|})$ for the full dataset. This is the bridge between the
formalization in [21] and ours. Learnability conditions are derived in [21]
for the fixed distribution case and for the free distribution case. The proof
for the fixed distribution case involves a key assumption: the learner wants
to minimize the length of the longest codeword rather than the mean codeword
length. In other words, [21] considers the worst case number of questions. Our
work considers the expected number of questions (or mean codeword length)
instead. Furthermore, in our framework the minimum number of binary questions
is $1$ (the case of automatic annotation with a perfect predictor). The second
theoretical work [33] also deals with (active) learning bounds. The authors
correctly point out the equivalence between the problem and coding theory, but
choose to consider lossy coding algorithms. The biggest (theoretical)
difference between our work and [21, 33] is the change of focus from quick
learning to quick annotation and the use of a lossless compression method.

The second class of works are ad-hoc methods such as [31, 15] that introduce
yes/no answers as supervision. Notably [15] uses binary questioning to reduce
the annotation cost of multiclass classification instances. Similarly, [31]
aims to reduce the cost of annotating an observation but for the image
segmentation case.

###  2.4 Dynamic Programming

Dynamic Programming (DP) is an optimization algorithm widely used to solve
optimal control / reinforcement learning problems. The closest to our work is
the recent Wordle resolution [8] based on the rollout method popularized by
Bertsekas [5, 6]. Rollout is a reinforcement-learning method that yields an
improved policy based on an initial policy [7]. For some control problems
there is an heuristic policy based on a proxy cost function that serves as
initial policy. The main idea of rollout is that, for these cases, one can use
lookahead minimization of the same proxy cost function by going down the tree
of actions/states and obtain a new policy that is guaranteed to be an
improvement over the original heuristic.

##  3 General setting

Given a dataset of size $N$ we (re-)define the set of observations
$X=(x_{1},\dots,x_{N})$ and the associated ground truth labeling
$y=(y_{1},\dots,y_{N})\in[0,1]^{N}$. As shown in [21] a general binary
question is of the sort “is $y\in q$?” where $q$ is a subset of the set of
possible labelings, i.e. $q\subset[0,1]^{N}$. In particular the annotation of
a single sample can be phrased as “is $y\in q_{y_{i}=1}$?” where
$q_{y_{i}=1}=\\{z\in[0,1]^{N}|z_{i}=1\\}$. The problem of annotating the full
dataset with the minimum number of questions is exactly the problem of
encoding $y$ with the minimum expected length. The sequence of Q&A is given by
the corresponding decoding process. The source coding theorem establishes that
the minimum expected length achievable by a lossless compressor is given by
$H(Y)$ [28], where $Y$ is the random variable associated to the labeling $y$.
This is a lower bound on the number of questions $Q$ that we can compute if we
know the distribution $P(Y=y)$. For our purposes we assume that (i) $P(Y=y|X)$
is known and that (ii) the entries of $y$ are independent, i.e.
$P(Y=y|X)=\prod_{i}P(Y_{i}=y_{i}|x_{i})$. These assumptions fit the familiar
case where a predictor $f_{\theta}$ can estimate the probabilities
$f_{\theta}(x_{i})=\hat{P}(Y_{i}=1|x_{i})$. We will now use $f_{\theta}$ in
place of $P$ but this is only valid in the oracle case. The entropy of the
distribution is

$H(Y)=-\sum_{y\in Y}P(Y=y)\log(P(Y=y))\\\ =-\sum_{1\leq i\leq
N}\left[f(x_{i})\log(f(x_{i}))+(1-f(x_{i}))\log(1-f(x_{i}))\right].$ (1)

###  3.1 Huffman encoding

Huffman encoding [16] is a lossless encoding method that is optimal for the
case of single-symbol encoding. Optimally encoding a sequence of symbols is a
different problem often solved with arithmetic codes. Huffman encoding
achieves the entropy bound when the probabilities assigned to every symbol are
dyadic, i.e. of the form $1/2^{k}$. The algorithm works as follows: (i) set
the initial list of nodes without a parent to be all symbols. The symbols in
our case are all possible dataset labelings, i.e. the $2^{N}$ binary vectors
of length $N$. Then (ii) the two nodes without a parent with the smallest
probability are assigned a new node as parent whose probability is the sum of
the probabilities of the children. Step (ii) is repeated until only one node
is left without parents. This last node is an ancestor for all symbols. Once
the tree is built, each node represents a state given by all labelings that
have not been discarded, which are the descendant symbols of that node.

The decoding process is conducted as follows: starting from the root node we
ask the question “is $y\in q$?” where $q$ is the right branch coming out of
the node. Repeating this step takes us down the tree until only one symbol is
left. We are guaranteed that, given the probabilities $P(Y=y)$, we will arrive
at the ground truth labeling $y$ in the minimum expected number of questions Q
(this is proven via an exchangeability argument and induction) [26].
Furthermore, one can prove that $H(Y)\leq Q_{\text{huffman}}\leq H(Y)+1$ [12].
The computational complexity for building the tree is $m\log m$ where $m$ is
the number of symbols in the alphabet. In our case $m=2^{N}$. This is
exponential complexity and becomes unmanageable for values of $N$ as small as
$N=20$.

Figure 1: Computed expected cost on Huffman tree vs. entropy for the synthetic
problem (a).

Given the Huffman tree and the probabilities we can compute the expected
number of questions from a given node. In Figure 1 we show the comparison
between this exact computation and the entropy, finding that indeed the
expected cost on the Huffman tree gets very close to the entropy bound.
Lastly, note that because Huffman encoding falls into the general questioning
case, the questions are of the sort is the correct labeling of the whole
dataset $y$ among those labelings in $q$?. The user experience when answering
this question is not great, and this will be fixed with an heuristic in
Section 4.

###  3.2 Exhaustive tree search and DP

If we take the dyadic case where Huffman encoding reaches the entropy bound we
have that, simultaneously, there is a policy or questioning strategy (Huffman)
for which $E[Q]=H(Y)$ and also we have that $E[Q]\geq H(Y)$. It follows that
the optimal value or cost function, i.e. the evaluator function that returns
the expected cost incurred by the optimal policy from a given state, is the
entropy $H(Y)$. Given such an optimal value function the derivation of the
optimal policy is simple: we choose the action (a subset $q$ of binary
vectors) that minimizes the expected entropy on the next state. In other
words, given a state $s_{t}$ we consider all possible questions $q$ and choose
$\text{argmin}_{q}J^{\star}(s_{t},q)=\text{argmin}_{q}J^{\star}({s_{t+1}}_{1}|a=1)P(a=1)+J^{\star}({s_{t+1}}_{0}|a=0)P(a=0)$
where $J^{\star}=H(s)$. Note that to compute $H(s)$ we need to update the
probabilities $P(Y=y)$ using Bayes rule to restrict them to $s$, which simply
accounts for a renormalization. This method gives us a procedure that is
optimal and is top-down (greedy) instead of bottom-up (Huffman). The
computational complexity is given by that of the entropy computation times the
number of possible questions. The number of possible questions in the first
step is the cardinality of the set of all possible subsets of binary vectors
of length $N$, this is, the cardinality of the power set
$2^{([0,1]^{N})}=2^{2^{N}}$. This exponential-exponential computational cost
is way higher than the exponential of Huffman and also unfeasible.

##  4 Practical setting

The optimal solutions described above have two issues that make them not
useful in practice. The first is the computational complexity, which is (at
least) exponential on the dataset size. The second is the type of binary
questions, which are general and over all the dataset, and make the user
experience of any product unacceptably bad. Our proposed IA method solves
these two issues.

The proposed method is based on two key observations, namely that lookeahead
minimization guarantees improvement over the base heuristic and that the
branching factor of the tree (originally $2^{2^{N}}$ should be drastically
reduced. Another quantity of interest that will be used in what follows is the
size $|s|$ of the state $s$, which represents the number of labelings that
were not yet discarded.

###  4.1 Reducing the computational cost

To reduce the branching factor of $2^{2^{N}}$ to something reasonable we use a
handful of heuristics, each one taking us further away from optimality but
closer to an efficient method. We note that all possible questions can be
counted considering the cardinality of the questions $n=|q|$ as $\sum_{1\leq
n\leq 2^{N}}\binom{2^{N}}{n}=2^{2^{N}}$. These are:

  1. 1.

Early stopping: We will assume that the cost of the best question of size $n$
as a function of $n$ has a global minimum. We look for questions starting from
$n=1$ and increase $n$ but stop once we find that the cost of the best
question of size $n$ is higher than the cost of the best question of size
$n-1$. This reduces the branching factor to $\sum_{1\leq n\leq
E}\binom{2^{N}}{n}$ where $E\ll N$.

  2. 2.

Select most likely: Not true in general, we consider that the best question of
size $n$ is given by the $n$ most likely labelings of those that remain
available in $s$. This criterion is optimal when the cost function is $|s|$,
but it is not optimal in general for the case of the entropy as a cost
function. This heuristic reduces the branching factor to $\sum_{1\leq n\leq
E}1=E$, if the $2^{N}$ possible labelings are sorted and to
$2^{N}\log(2^{N})E$ if not.

We now introduce two more heuristics that are not only motivated by the
computational complexity problem but also by user experience considerations
and algorithmic simplicity:

  1. 3.

Question as single guess: This heuristic targets user experience: the space of
questions is now given by the (most likely) guesses over $n$ observations
(abusing notation of $n$). This means that the method will choose some set of
$n$ observations, pseudo-label them, and ask the annotator if the pseudo-
labeling is correct. We maintain the early stopping and most likely heuristics
that now cause our search to be of complexity $N\log(N)E$, caused by sorting
the probabilities for each observation and evaluating guess sizes $n$ from $1$
up to $E$ (we early stop when the cost function increases).

  2. 4.

Don’t give up: Until the introduction of the single guess heuristic, the
incorrect guesses were simple to handle: we simply removed them from the
state. In contrast, when using guesses the state can be summarized as the
current unlabeled indices and the incorrect guesses made so far. Updating the
state given a new correct or incorrect guess is possible but the
simplification of a state (without redundancy) is somewhat contrived. Although
we successfully implemented general state updates we prefer to introduce the
don’t give up heuristic for simplicity. The don’t give up heuristic
establishes that when an incorrect guess of size $n$ has been made, the next
guess should be the incorrect guess with the most uncertain prediction
removed. When the second guess is correct, we can deduce the labels for all
the indices of the first guess. In contrast, when the second guess is
incorrect, we apply the heuristic again. This reduces the branching factor to
$N\log(N)$ when an incorrect guess has been made. Note that the sorting can be
made only once if the predictor $f$ stays the same.

#### Lookahead minimization

The heuristics introduced above can successfully reduce the number of possible
questions to be considered at each step. However, choosing the one that
minimizes the expected entropy or the expected size on the next state is not
an optimal method anymore. Optimality was lost when reducing the question
space. However, using lookahead minimization, i.e. simulating a few steps
ahead and only then evaluating the states using the chosen proxy cost
function, is guaranteed to improve over the heuristic generated by the proxy
cost function [6]. In the limit of maximum lookahead the terminal states are
reached and the exact expected number of questions is computed, thereby
achieving the optimal method respecting the heuristics above.

#### Summary and parameters

In a nutshell, our method (IA) is lookahead minimization over the tree of
state and actions. Some parameters control the algorithm, in italics in this
section. The tree search involves selecting a node, expanding the selected
node, updating the parents of the expanded node, and after a number of
expansions taking the action that has the best expected cost. When expanding a
node, guesses with different sizes $n$ are considered as actions, with a
special treatment for $n=1$. In fact, for $n=1$, we allow to choose between
random sampling or entropy sampling, but any active learning algorithm could
be used. To allow for more control on the branching factor and the user
experience a parameter that sets the maximum allowed guess size $n$ is added.
Another parameter of our method is the maximum node expansions to be made at
each step that roughly controls the computational cost of the tree search.

The selection of the node to be expanded is done according to the priority,
where the priority is the product of the probabilities of the edges. Even
though we always use a greedy approach for action selection, to set priorities
we consider the probability of an action to be the result of the softmax over
the cost of the different actions with some temperature. Lastly, a proxy cost
function is used, and we allow the choice between the entropy $H(s)$ and the
log state size $\log_{2}(|s|)$ (roughly the number of points left to
annotate). Both functions are adapted for the case in which an incorrect guess
is part of the state by using conditional entropy and counting concepts.

After each node expansion the parents are updated, which means that we
propagate the new estimate of the state cost up the tree and continue
expanding nodes if needed. Of course, if the probabilities given by $f$ do not
change, after each step the relevant branch of the tree is kept in memory,
thereby allowing the max expansions to further expand the tree. We refer the
reader to the supplementary material for full code and algorithm description.

#### Fitting to incorrect examples

In the online learning case where the predictor $f$ is continuously being
learned, the predictor can and should be updated if an incorrect guess has
been made. The simple method used to do this is now described. Consider
$\bar{x}=(x_{1},\dots,x_{n})\in X$ without loss of generality when selecting
the indices and the associated predicted labeling
$\hat{y}=(\hat{y}_{1},\dots,\hat{y}_{n})$. The estimated probability of
$\hat{y}$ being correct is given by $\hat{P}(\hat{y}\text{
ok})=f_{J}(\hat{y}\text{ ok})=\prod_{1\leq i\leq
n}f(x_{i})^{\hat{y}_{i}}(1-f(x_{i}))^{1-\hat{y}_{i}}$, where $f_{J}$ assigns a
probability to each answer. It follows that given an incorrect guess the
binary cross entropy between $f(\hat{y}\text{ ok})$ and the actual answer $0$
can be used as a loss that can be minimized via gradient descent. This loss is
added to the loss computed over the labeled examples for each epoch and in
this way the knowledge of the guess being incorrect is integrated into $f$.

##  5 Experiments

Here we summarize our main results. The Appendix includes full numerical
results, experimental details and extra figures.

#### Synthetic

(a) Two Gaussians. The predictor $f=P(Y|X)$ follows Bayes’ rule.

(b) Two Gaussians. The predictor $f(X)=P(Y|X)$ is independent of $P(X)$.

(c) Data following [13]. The predictor $f$ is a logistic regressor trained on
the data and $f(X)\neq P(Y|X)$.

Figure 2: Example sample of three two-dimensional synthetic binary
classification problems. The background color corresponds to the probabilities
predicted by $f$. The color of the points correspond to the ground truth
labeling.

We generate three two-dimensional toy problem variations with dataset size
$N=10$ for $1000$ different seeds. The variations are depicted in Figure 2. In
Figure 3 one observes that the proposed method is very close to the optimal
given by Huffman ((a),(b) and (c)), that is in turn close to the entropy lower
bound ((a) and (b)). For the last problem (c) we observe that the entropy
computed by the predictor that is fit to the data but does not capture the
underlying distribution $P(Y|X)$ does not act as a lower bound. This means
that pretrained predictors can incorrectly estimate the complexity of the data
they were fitted to.

(a)

(b)

(c)

Figure 3: Number of questions for the synthetic problems (ref. Figure 2) for
each method (IA, Huffman) and the entropy of the data as estimated by the
predictor.

#### Real with pretraining

The IA method is evaluated over the first 6000 samples of the CIFAR10 [20] and
SVHN [24] datasets, where all labels with indices greater than 4 are
considered positive. These datasets are too hard to run from scratch and a
fixed predictor trained on different samples of the training set is provided
to the IA. The oracles have accuracies of $0.67$ and $0.93$ respectively.
Figure 4 shows the number of annotated samples vs. the number of binary
questions posed. The maximum annotation gain (number of answers required to
annotate $2500$ points) for CIFAR10 is $20\%$, which is expected considering
that the predictor is not very good. In contrast, for SVHN all methods manage
to annotate the full $6000$ samples with less than $2500$ questions, showing
how effective the method can be when the predictor is good. We note that the
number of incorrect guesses is permanently increasing in most cases,
indicating that the size of the guesses is larger than one. Furthermore, when
using the entropy of the state $H(s)$ as a proxy cost function and offering
the most uncertain sample as the potential guess with unit size, the IA method
sticks to point-by-point annotation for more than $1000$ examples. This
variant then switches to annotating the most obvious datapoints at a high
annotation rate.

(a) CIFAR10 [20]

(b) SVHN [24]

Figure 4: Number of annotations vs. number of questions for four IA variants
on the first 6000 examples of each dataset and leveraging a fixed pretrained
model.

#### Real from scratch

Then we turn our attention to the more realistic case of intelligent
annotation when a trained predictor is not available. In this case the
predictor is trained from scratch with the available annotations so far. This
is the case (dubbed ALIA) that combines the related tasks of active learning
(quickly training a predictor) and intelligent annotation (using that
predictor to annotate more efficiently) and yields both annotated data and a
trained predictor. For this experiment we run the ALIA over MNIST [22] and
Fashion MNIST [30]. An annotation gain of $70\%$ is observed for both
datasets. As expected, after most easy samples are annotated, the annotation
slows down. This change is very abrupt for MNIST and we hypothetize that this
is due to an uncalibrated predictor.

(a) MNIST [22]

(b) FMNIST [30]

Figure 5: Number of annotations vs. number of questions for four ALIA variants
on the first 6000 examples of each dataset starting from a randomly-
initialized predictor.

##  6 Product, Limitations, Conclusion

Our method naturally suggests a software for the annotation of binary
classification. The annotator is presented with a classification of at most
max_n samples and they answer correct or incorrect. The classification is the
pseudo-labeling of a predictor $f$ that is continuously trained in the
background using all the annotated data so far and checkpoints are frequently
saved. The last checkpoint is loaded by the tree search that uses its
predicted probabilities to select the number $n$ of samples presented to the
annotator as described in Section 4.

Our work is arguably the first attempt to solve the intelligent annotation
problem, with some limitations. One of them is that, similarly to most AL
work, the present work mostly ignores the interplay between quick annotation
and quick learning, where quick refers to the number of binary answers. It is
natural to expect that for both problems a sweet spot will be found in
between, i.e. the best solution will involve quickly annotating data that
makes the predictor training quicker. Furthermore, all our experiments have
dealt with balanced datasets, while in many real scenarios only imbalanced
data is available. Another limitation is that we have not considered in-depth
the impact on our method of imperfect predictors, in particular uncalibrated
predictors. Even though the method works in practice, the whole tree search is
dependent on probabilities that might not correspond to true frequencies.
Lastly, even though the computational complexity has been greatly reduced, the
method becomes slower for large $N$ (freezing the predictor and reducing the
number of node expansions makes the method fast in practice).

Motivated by the need of tools for quick annotation, this paper studies how a
predictor can be leveraged to quickly annotate data and measures quickness as
the number of yes/no answers provided by the user. We show that the optimal
binary questioning strategy given a perfect predictor is found in Huffman
encoding, but this strategy is too computationally expensive to be applied in
practice. We manage to develop a practical intelligent annotation (IA)
solution by introducing heuristics and relying on the dynamic programming
principle of lookahead minimization. We show that our strategy works
comparably to the optimal one on toy problems and that it provides significant
annotation efficiency gains over more realistic data.

## References

  * [1] Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy and Sham Kakade  “Gone Fishing: Neural Active Learning with Fisher Embeddings”, 2021  arXiv:2106.09675 [cs.LG]
  * [2] Yuntao Bai et al.  “Training a helpful and harmless assistant with reinforcement learning from human feedback”  In _arXiv preprint arXiv:2204.05862_ , 2022
  * [3] Randall Balestriero et al.  “A Cookbook of Self-Supervised Learning”, 2023  arXiv:2304.12210 [cs.LG]
  * [4] Nathan Beck et al.  “Effective Evaluation of Deep Active Learning on Image Classification Tasks”, 2021  arXiv:2106.15324 [cs.CV]
  * [5] Dimitri Bertsekas  “Dynamic programming and optimal control: Volume I”  Athena scientific, 2012
  * [6] Dimitri Bertsekas  “Rollout Algorithms and Approximate Dynamic Programming for Bayesian Optimization and Sequential Estimation”  In _arXiv preprint arXiv:2212.07998_ , 2022
  * [7] Dimitri Bertsekas  “Rollout, policy iteration, and distributed reinforcement learning”  Athena Scientific, 2021
  * [8] Siddhant Bhambri, Amrita Bhattacharjee and Dimitri Bertsekas  “Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach”  In _arXiv preprint arXiv:2211.10298_ , 2022
  * [9] Vladimir Bychkovsky, Sylvain Paris, Eric Chan and Frédo Durand  “Learning Photographic Global Tonal Adjustment with a Database of Input / Output Image Pairs”  In _The Twenty-Fourth IEEE Conference on Computer Vision and Pattern Recognition_ , 2011
  * [10] Vivien Cabannes, Leon Bottou, Yann Lecun and Randall Balestriero  “Active Self-Supervised Learning: A Few Low-Cost Relationships Are All You Need”, 2023  arXiv:2303.15256 [cs.LG]
  * [11] Juan Elenter, Navid Naderializadeh and Alejandro Ribeiro  “A Lagrangian Duality Approach to Active Learning”  In _Advances in Neural Information Processing Systems_ 35 Curran Associates, Inc., 2022, pp. 37575–37589  URL: https://proceedings.neurips.cc/paper_files/paper/2022/file/f475bdd151d8b5fa01215aeda925e75c-Paper-Conference.pdf
  * [12] Michel Goemans  “Huffman Codes”  In _MIT 18.310 lecture notes_ URL: https://math.mit.edu/~goemans/18310S15/huffman-notes.pdf
  * [13] Isabelle Guyon, Steve Gunn, Asa Ben Hur and Gideon Dror  “Design and analysis of the NIPS2003 challenge”  In _Feature extraction: foundations and applications_ Springer, 2006, pp. 237–263
  * [14] Kaiming He, Xiangyu Zhang, Shaoqing Ren and Jian Sun  “Deep residual learning for image recognition”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778
  * [15] Hengtong Hu et al.  “One-bit Supervision for Image Classification”  In _Advances in Neural Information Processing Systems_ 33 Curran Associates, Inc., 2020, pp. 501–511  URL: https://proceedings.neurips.cc/paper_files/paper/2020/file/05f971b5ec196b8c65b75d2ef8267331-Paper.pdf
  * [16] David A Huffman  “A method for the construction of minimum-redundancy codes”  In _Proceedings of the IRE_ 40.9 IEEE, 1952, pp. 1098–1101
  * [17] Diederik P Kingma and Jimmy Ba  “Adam: A method for stochastic optimization”  In _arXiv preprint arXiv:1412.6980_ , 2014
  * [18] Alexander Kirillov et al.  “Segment anything”  In _arXiv preprint arXiv:2304.02643_ , 2023
  * [19] Andreas Kirsch and Yarin Gal  “Unifying Approaches in Active Learning and Active Sampling via Fisher Information and Information-Theoretic Quantities”  In _Transactions on Machine Learning Research_ , 2022  URL: https://openreview.net/forum?id=UVDAKQANOW
  * [20] Alex Krizhevsky and Geoffrey Hinton  “Learning multiple layers of features from tiny images”  Toronto, ON, Canada, 2009
  * [21] Sanjeev R Kulkarni, Sanjoy K Mitter and John N Tsitsiklis  “Active learning using arbitrary binary valued queries”  In _Machine Learning_ 11 Springer, 1993, pp. 23–35
  * [22] Yann LeCun, Léon Bottou, Yoshua Bengio and Patrick Haffner  “Gradient-based learning applied to document recognition”  In _Proceedings of the IEEE_ 86.11 Ieee, 1998, pp. 2278–2324
  * [23] Qin Liu, Zhenlin Xu, Gedas Bertasius and Marc Niethammer  “SimpleClick: Interactive Image Segmentation with Simple Vision Transformers”, 2023  arXiv:2210.11006 [cs.CV]
  * [24] Yuval Netzer et al.  “Reading digits in natural images with unsupervised feature learning”, 2011
  * [25] Maxime Oquab et al.  “DINOv2: Learning Robust Visual Features without Supervision”, 2023  arXiv:2304.07193 [cs.CV]
  * [26] “Proof of Optimality of Huffman Coding”  In _California Berkeley cs170 notes_ URL: https://inst.eecs.berkeley.edu/~cs170/fa20/assets/notes/huffman.pdf
  * [27] Burr Settles  “Active learning literature survey”  University of Wisconsin-Madison Department of Computer Sciences, 2009
  * [28] Claude Elwood Shannon  “A mathematical theory of communication”  In _ACM SIGMOBILE mobile computing and communications review_ 5.1 ACM New York, NY, USA, 2001, pp. 3–55
  * [29] Jesper E Van Engelen and Holger H Hoos  “A survey on semi-supervised learning”  In _Machine learning_ 109.2 Springer, 2020, pp. 373–440
  * [30] Han Xiao, Kashif Rasul and Roland Vollgraf  “Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms”, 2017  arXiv:cs.LG/1708.07747 [cs.LG]
  * [31] Binhui Xie et al.  “Towards fewer annotations: Active learning via region impurity and prediction uncertainty for domain adaptive semantic segmentation”  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 8068–8078
  * [32] Jingfeng Yang et al.  “Harnessing the Power of LLMs in Practice: A Survey on ChatGPT and Beyond”  In _arXiv preprint arXiv:2304.13712_ , 2023
  * [33] Liu Yang, Steve Hanneke and Jaime G Carbonell  “Bayesian Active Learning Using Arbitrary Binary Valued Queries.”  In _ALT_ , 2010, pp. 50–58  Springer
  * [34] Xueying Zhan et al.  “A comparative survey of deep active learning”  In _arXiv preprint arXiv:2203.13450_ , 2022
  * [35] Xiaojin Jerry Zhu  “Semi-supervised learning literature survey”  University of Wisconsin-Madison Department of Computer Sciences, 2005

##  Appendix A Code

Code is available at https://anonymous.4open.science/r/optimalbinaryhill/.

##  Appendix B Proposed method

Even though the exact code is provided, here we provide Python-styled pseudo-
code for the proposed method to ease understanding. The following function is
the one that chooses the best guess, question or action from a state node.

def tree_search(root_node): print("Expanding tree…") for i in
range(self.max_expansions): node = select_node(root_node) # highest priority
leaf node if node == "all nodes expanded": break # get the predictions
relevant to the current node expand_node( node, max_n, node_predictions,
al_method, approx_cost_function ) update_parents(node) # here

best_action_node = get_best_action(root_node) return best_action_node

Here root_node| is a state node, described by a list of indices corresponding
to the unlabeled datapoints and optionally an incorrect guess. As described in
the manuscript,

The algorithm is fully described by the definition of the functions

  * •
  * •

Then, if the last guess is correct it means that the extra label from the
incorrect previous guess was wrongly guessed and we can deduce the actual
label is the opposite.

The second step is to increment $n$ and select the subset of the $n$

After a new action node is added then its value is computed as a probability-
weighted average of the values of its children states. These values are
computed using the We repeat the second step of incrementing $n$ until the
cost of the new action node is greater than the cost of the previous action
node. The cost of the action with minimum cost is assigned to the state node
being expanded.

  * •
  * •

The content above explains how to choose the best action given a state. The
complete loop involves finding the best action, getting the answer for that
question, updating the state, and optionally retraining the predictor. For the
oracular case there is no predictor retraining. For the HILL or ALIA case
there is retraining ideally after each annotation step. To keep the
computational cost low we retrain after every state update if we have made
less than $100$ questions, else if we have made less than $200$ questions we
retrain every two state updates, and so on. Full experimental parameters are
given in Section C.

Lastly, we note that when

##  Appendix C Experimental details for synthetic datasets

###  C.1 Datasets

The three synthetic datasets generated are two-dimensional.

  1. (a)

Two blobs: 5 points are sampled from each one of two gaussians. Both have
identity covariance matrices and they are cenetered at $(0,0)$ and $(2,2)$
respectively. The likelihood is given by
$P(X=x|y)=\frac{1}{2\pi}\exp{\left(-\frac{1}{2}((x_{1}-c_{y})^{2}+(x_{2}-c_{y})^{2})\right)}$
where $c_{y}$ is the center of one of the gaussians (we set $c_{0}=0$). Then
the probability of an observation $x$ being positive is

$P(y=1|x)=\frac{P(x|y=1)P(y=1)}{P(x,y=1)+P(x,y=0)}\\\
=\frac{P(x|y=1)P(y=1)}{P(x|y=1)P(y=1)+P(x|y=0)P(y=0)}\\\
=\frac{P(x|y=1)}{P(x|y=1)+P(x|y=0)}$ (2)

where $P(y=1)=P(y=0)$ because we create a balanced dataset. The function
$P(y=1|x)$ is used as the predictor.

  2. (b)

Two blobs with linear predictor: To show that our method does not rely on
clustering properties (unlike some semi-supervised methods [35]) we again
create datapoints from two blobs but now assign the labels according to a
probability given by a pre-defined predictor. In this case $P(X)$ corresponds
to a balanced gaussian mixture with centers $(0,0)$ and $(3,3)$ and
covarianecs given by $Id/2$. The $P(y=1|x)$ is given by

$P(y=1|x)=\frac{1}{1+\exp{\left(-\frac{x_{2}-x_{1}}{2}/0.3\right)}}$ (3)

and each label $y_{i}$ is set to $1$ with probability $P(y_{i}=1|x_{i})$.

  3. (c)

The last case is generating points using the

###  C.2 Parameters

IA parameters for our experiments on synthetic datasets include: TEMPERATURE =
10 MAX_DEPTH = 20 al_method = "uncertainty" max_n = 8 max_expansions = 8
cost_fn = "entropy" reduce_certainty_factor=0.01 reset_tree=False

The Huffman questioning method has no parameters.

###  C.3 Experiment details

We run the same experiment for $1000$ different seeds $(0,\dots,999)$. There
is no initial labeling provided as the predictors are fixed for each seed.
Note that because the tree is not reset it (most likely) grows after every
question.

##  Appendix D Experimental details for real datasets

###  D.1 Datasets

The datasets used for the experiments are CIFAR10 [20], MNIST [22], FMNIST
[30], SVHN [24]. The first three are balanced, while SVHN has some bias
towards smaller digits. The datasets are binarized by setting a positive label
if the original label is greater than $4$. This binarization mantains the
(un)balanced character of the datasets. The datasets are downloaded using For
our experiments we use the first $6000$ examples from the training set of each
dataset.

The color datasets are normalized using ImageNet mean and standard deviation
and the single-channel datasets are normalized using MNIST mean and standard
deviation.

###  D.2 Model parameters

Below are the model parameters of our IA solution. All these were created to
provide flexibility to the user and set to (roughly) arbitrary values.
Preliminary experiments suggested that the temperature set at the order of 10
provided a good balance between breath and depth expansion of the tree. The
maximum depth was set to $20$ because planning $20$ steps ahead was already
considered too much. For the case in which the tree is not reset, i.e. when
the predictions do not change, the tree grows at each iteration and the
maximum depth parameter is a way to avoid unlimited growth and potentially
high memory consumption. We do not expect this limit to be reached. The last
parameter is the factor that reduces the certainty of the predictor via a
weighted average with $0.5$. This parameter was introduced because the
predictions can be sometimes too confident. A factor of $0.01$ should not
significantly modify the behavior of the model, while a parameter of $0.05$ is
already enough to make the length cost function somewhat less aggressive. We
did not run ablation studies on this factor for any of the two losses.

TEMPERATURE = 10 MAX_DEPTH = 20 reduce_certainty_factor=0.05 if
cost_fn==’length’ else 0.01 max_n = 8 max_expansions = 8

The

###  D.3 Architecture and pretrained predictor

The architecture used is a ResNet18 [14] from

For CIFAR10 and SVHN we pretrain the predictor on all the training datapoints
but the first $6000$. The pretraining uses a batch size of $6000$ and Adam
optimizer with initial learning rate set to $0.01$. The pretraining comprises
$24$ epochs.

###  D.4 Experiment and training

Each experiment was run for four seeds (0, 1, 2, 3) on GeForce, V100 or Titan
Nvidia GPUs as available. The runtimes vary for each experiment but it is
always less than $30$ minutes. The speed of the tree search is below $0.5$
seconds per search.

A first annotated example, selected randomly, is provided. This is one source
of stochasticity, albeit minor. For the case with fixed predictions the
deviations between runs is negligible and the error intervals can barely be
noticed (e.g. see Figure 4a). We can thus conclude that the stochasticity
coming from what is the first annotated example is very low. Most of the
stochasticity visualized for the experiments over MNIST and FMNIST comes from
the initialization of the predictor weights.

For these later cases of HILL or ALIA, we retrain the predictor after each
question for the first $100$ examples, every two questions for the next $100$
examples, and so on. Each time the predictor is retrained starting from the
latest set of weights. The predictor is retrained using the current labeled
examples and the current incorrect example if any for $4$ epochs. The
optimizer is Adam with initial learning rate $0.01$ and it is reinitialized at
each new retraining. The fitting to the incorrect example is done as described
in Section 4. This is done without any particular weighting. The incorrect
example counts to the loss the same as any labeled sample. We avoid using
batches and thus our gradient descent is non-stochastic. For all experiments,
the maximum number of questions considered was $2500$.

##  Appendix E Questioning as encoding

The manuscript reads: “The problem of annotating the full dataset with the
minimum number of questions is exactly the problem of encoding $y$ with the
minimum expected length.”. However, this might not be obvious for the reader.
The problem as it was formulated involves, with some knowledge of the
probability $P(Y)$ where $Y$ is the random variable representing the labeling
of the full dataset, to find through binary questions what specific value $y$
the random variable takes for our realization. This is, we want to recover a
full dataset labeling $y$ with the least number of binary questions. The
encoding problem in communication theory tackled by Huffman involves assigning
to each possible symbol $y$ a binary code. This binary code is, on average
over many samples of symbols, the one that has the least number of bits. The
Huffman decoding process can be seen as a sequential question game where we
ask “is the next bit of the symbol representation a $1$?”. The answer of each
question is a bit that is communicated to the receiver. With the least number
of bits (on average) the Huffman method can reconstruct the symbol $y$.
Another way of phrasing the question is “is the symbol being transmitted on
the branch to the right of the current node in the Huffman tree?”, which is
one case of a general binary question (“is $y\in q$?”). The equivalence
between annotation and communication theory can be drawn also when trying to
find the minimum possible expected number of questions needed to annotate a
dataset provided with the probabilities of the labels. This is given by the
entropy and the reasoning is similar. The key to the reasoning is considering
not each individual label $y_{i}$ but the full labeling $y$ as a symbol.

Table 1: Results over synthetic datasets. All entries are mean values over the quantities in the column titles. $Q$ represents the number of questions and $H$ represents the entropy for a given sample of $N=10$ synthetic datapoints. | Synthetic (a) | Synthetic (b) | Synthetic (c)
---|---|---|---
| $\overline{Q}$ | $\overline{Q-H}$ | $\overline{Q/H}$ | $\overline{Q}$ | $\overline{Q-H}$ | $\overline{Q/H}$ | $\overline{Q}$ | $\overline{Q-H}$ | $\overline{Q/H}$
Entropy | 2.77 | - | - | 6.03 | - | - | 7.33 | - | -
Huffman | 2.80 | 0.03 | 1.05 | 6.11 | 0.08 | 1.01 | 5.08 | -2.25 | 0.67
IA | 3.46 | 0.69 | 1.42 | 6.31 | 0.28 | 1.05 | 5.20 | -2.13 | 0.69
Table 2: Performance of methods over CIFAR10 dataset using a pretrained predictor. |  | CIFAR10
---|---|---
AL method | Cost function | $Q_{L=2500}\downarrow$ | $\max{Q}\downarrow$ | $L_{\max Q}\uparrow$ | $\text{\\#Inc}_{\max Q}\downarrow$ | $\frac{Q_{L=2500}}{2500}\downarrow$
Random | $H(s)$ | $2143\pm 14.3$ | $2500$ | $2880\pm 13.8$ | $1464\pm 4.5$ | $85.72\%$
Random | $\log_{2}(|s|)$ | $1932\pm 3.7$ | $2500$ | $\bm{3050\pm 1.3}$ | $1360\pm 2.6$ | $\bm{77.28\%}$
Uncertainty | $H(s)$ | $2500\pm 0.0$ | $2500$ | $2500\pm 0.0$ | $\bm{0\pm 0.0}$ | $100\%$
Uncertainty | $\log_{2}(|s|)$ | $\bm{1952\pm 1.0}$ | $2500$ | $3032\pm 1.0$ | $1372\pm 1.0$ | $78.08\%$
Table 3: Performance of methods over SVHN dataset using a pretrained predictor. |  | SVHN
---|---|---
AL method | Cost function | $Q_{L=2500}\downarrow$ | $\max{Q}\downarrow$ | $L_{\max Q}\uparrow$ | $\text{\\#Inc}_{\max Q}\downarrow$ | $\frac{Q_{L=2500}}{2500}\downarrow$
Random | $H(s)$ | $438\pm 13.1$ | $2208\pm 9.0$ | $6000\pm 0.4$ | $895\pm 11.4$ | $17.50\%$
Random | $\log_{2}(|s|)$ | $\bm{348\pm 0.0}$ | $2188\pm 1.6$ | $6000\pm 0.0$ | $1029\pm 1.1$ | $\bm{13.92\%}$
Uncertainty | $H(s)$ | $1262\pm 0.0$ | $2199\pm 0.0$ | $6000\pm 0.0$ | $\bm{470\pm 0.0}$ | $50.48\%$
Uncertainty | $\log_{2}(|s|)$ | $\bm{348\pm 0.0}$ | $\bm{2185\pm 0.5}$ | $6000\pm 0.0$ | $1029\pm 0.5$ | $\bm{13.92\%}$
Table 4: Performance of methods over MNIST dataset starting from scratch. |  | MNIST
---|---|---
AL method | Cost function | $Q_{L=2500}\downarrow$ | $\max{Q}\downarrow$ | $L_{\max Q}\uparrow$ | $\text{\\#Inc}_{\max Q}\downarrow$ | $\frac{Q_{L=2500}}{2500}\downarrow$
Random | $H(s)$ | $740\pm 46.7$ | $2500$ | $5234\pm 52.6$ | $1559\pm 21.8$ | $29.63\%$
Random | $\log_{2}(|s|)$ | $704\pm 53.5$ | $2500$ | $4971\pm 15.9$ | $1683\pm 2.8$ | $28.17\%$
Uncertainty | $H(s)$ | $1198\pm 26.8$ | $2500$ | $\bm{5716\pm 348}$ | $\bm{611\pm 246}$ | $47.92\%$
Uncertainty | $\log_{2}(|s|)$ | $\bm{699\pm 46.0}$ | $2500$ | $4978\pm 13.7$ | $1683\pm 1.9$ | $\bm{27.94\%}$
Table 5: Performance of methods over FMNIST dataset starting from scratch. |  | FMNIST
---|---|---
AL method | Cost function | $Q_{L=2500}\downarrow$ | $\max{Q}\downarrow$ | $L_{\max Q}\uparrow$ | $\text{\\#Inc}_{\max Q}\downarrow$ | $\frac{Q_{L=2500}}{2500}\downarrow$
Random | $H(s)$ | $818\pm 17.6$ | $2500$ | $\bm{5039\pm 31.8}$ | $1452\pm 19.8$ | $32.73\%$
Random | $\log_{2}(|s|)$ | $\bm{626\pm 66.6}$ | $2500$ | $4733\pm 161$ | $1719\pm 17.2$ | $\bm{25.05\%}$
Uncertainty | $H(s)$ | $1668\pm 23.8$ | $2500$ | $5006\pm 107$ | $\bm{248\pm 84.7}$ | $66.7\%$
Uncertainty | $\log_{2}(|s|)$ | $630\pm 71.1$ | $2500$ | $4755\pm 175$ |  $1718\pm 19.4$$ | $25.2\%$

##  Appendix F Full results

###  F.1 Synthetic

The numerical results for the synthetic experiments with the three synthetic
datasets described in Section C are presented in Table 1.

###  F.2 Real

The numerical results for the experiments over real datasets as described in
Section D are presented in Tables 2, 3, 4 and 5.