# Solution to the isoperimetric $n$-bubble problem on $\mathbb{R}^{1}$ with
log-concave density

John Ross

##  1 Introduction

The isoperimetric problem is a classic problem in mathematics that dates back
to antiquity. The original problem, as well as its (equivalent) dual problem,
are as follows:

######  Problem 1.1 (The Classic Isoperimetric Problem).

Out of all simple closed curves $\gamma\subset\mathbb{R}^{2}$ with a fixed
length of perimeter, find the curve that maximizes its enclosed area.

######  Problem 1.2 (The Dual Isoperimetric Problem).

Out of all simple closed curves $\gamma\subset\mathbb{R}^{2}$ which enclose a
fixed area, find the curve that minimizes its length of perimeter.

That the circle is the solution to the isoperimetric problem has been assumed
knowledge for centuries. A modern approach to this problem was first developed
by Steiner in the 1830’s [10], [11]. For a brief history and overview of the
classic problem, we refer to [2].

There are innumerable directions in which the isoperimetric problem has been
generalized, and we introduce several below. Perhaps the most immediate
generalization is to higher dimensional spaces, where we
$\gamma^{n}\subset\mathbb{R}^{n+1}$ or $\gamma^{n}\subset\Omega^{n+1}$ (with
$\Omega^{n+1}\subseteq\mathbb{R}^{n+1}$ a subset of Euclidean space, and with
boundary $\partial\Omega$ that might intersect $\gamma$. Here, solutions take
on the familiar name of “bubbles” because soap bubbles and soap film naturally
model the isoperimetric problem in $\mathbb{R}^{3}$.

The next immediate direction in which to generalize the problem is in working
with two (or more) regions. In this problem (which we formulate here for
area), we can look to (unions of pieces of) hypersurfaces that enclose two
fixed volume measurements $M_{1}$, $M_{2}$, and seek to minimize total surface
area. A (modern classic) result in this direction is the solution to the
double bubble conjecture. This conjecture was believed solved until more
modern times, then reverted to conjecture, and then eventually solved by
Hutchings, Morgan, Ritore, and Ros [6]. Anecdotally, the problem becomes more
challenging as more regions are introduced. The triple bubble problem has been
proven only in the case of the plane by Wichiramala [12]. A standard 3-bubble
has been suggested for higher dimensions, although it has not been proven to
be uniquely area minimizing.

Our third method of generalizing the problem is to introduce a density
function on the background space. In this problem, we introduce a background
density function $f$ on our ambient space ($\mathbb{R}^{n}$ or $\Omega$) that
affects how “enclosed volume” and “surface area” are measured. Specifically,
for an ambient space $\Omega^{n}\subseteq\mathbb{R}^{n}$, we introduce a
density function $f:\Omega\rightarrow[0,\infty)$. Then, for a hypersurface
$\gamma^{n-1}$ enclosing an $n$-dimensional solid $\Gamma$ (so
$\partial\Gamma=\gamma$), we define the (density-weighted) volume and surface
area to be

Weighted Volume $\displaystyle=\int_{\Gamma}f\,d\mathcal{H}^{n}$ Weighted
Surface Area $\displaystyle=\int_{\gamma}f\,d\mathcal{H}^{n-1}$

where the integrals are taken with respect to the usual Hausdorff measure.

This work will focus on multi-bubble isoperimetric problems with a density,
and with the ambient space being the real number line $\mathbb{R}^{1}$. Such
problems have been studied under a variety of densities. By an argument in
[7], it is known that a perimeter-minimizing $n$-bubble solution will exist on
$\mathbb{R}^{m}$ when using a density function that radially increases to
infinity. On $\mathbb{R}^{1}$, some early results for a single bubble under a
large class of density functions were first identified in [8].

Two families of density functions that have been studied recently are the
$|x|^{p}$ functions and the log-convex functions. An initial exploration on
density functions of the form $|x|^{p}$ was done by a research team under the
mentorship of Frank Morgan [5]. This team identified solutions for the single
and double bubble on these densities. Work was expanded to the 3-bubble and
the 4-bubble in the case of $p=1$ in [1]. Of note in these results is that any
isoperimetric solution maintains a regular structure, regardless of the
relative size of the bubble regions.

A radically different family of density functions on $\mathbb{R}^{1}$ was
studied by Bongiovanni et al. [3], who looked at single and double-bubble
solutions under log-convex density functions. This approach was motivated by
Gregory Chamber’s proof [4] of the single-bubble isoperimetric solution in
general $\mathbb{R}^{n}$ with log-convex density. In [3], it was found that a
double-bubble solution under a log-convex density function did not have a
standard structure. Instead, the solution could either be made up of two
intervals (one per region) or three intervals (with one region sandwiched
between two components of the other region), and the isoperimetric structure
depended on the sizes of the two masses in questions. In recent work, [9]
extended these results to identify possible triple-bubbles.

In both Huang et al. and Bongiovanni et al.’s work, radially symmetric,
increasing density functions were studied. This paper looks at symmetric,
radially increasing density functions $f$ that satisfy an additional property
of log-concavity. This property stipulates that $\left[\log
f\right]^{\prime\prime}\leq 0$. This study extends the work of [5] and [1], as
$|x|^{p}$ is a log-concave function. Specifically, our work address the
following problem:

######  Problem 1.3 (Our Isoperimetric Problem).

Consider the real number line $\mathbb{R}^{1}$, imbued with a density function
$f$ that satisfies the following:

  * •

$f$ is radially symmetric ($f(x)=f(-x)$)

  * •

$f$ has a point of zero density at the origin ($f(0)=0$)

  * •

$f$ is radially increasing ($f^{\prime}(x)\geq 0$ if $x>0$)

  * •

$f$ is log-concave ($\left[\log(f(x))\right]^{\prime\prime}<0$ for $x\neq 0$)

Then, given a set of $n$ masses $M_{1}\leq\dots\leq M_{n}$, find a
configuration of $n$ regions with these weighted masses and with minimal
weighted perimeter.

We will formally state the solution to this problem in Theorem 1 below. Unlike
Bongiovanni et al.’s work with log-convex functions, we will find that a
general structure is upheld for all $n$ and for all $n$-bubbles. Furthermore,
our isoperimetric solution is unique up to reflective symmetry across the
origin, and our proof gives the solution for an arbitrary number of regions.
We will call this $n$-bubble structure the “standard position” for $n$ masses,
and formally define/introduce it in Section 3.3.

Of special note is that the density functions we study have a point of 0
density at the origin. This is not inherent in the definition of “log-
concave”, but it is necessary for our arguments. The point will serve as an
“anchor” for endpoints of intervals, and will keep our entire configuration
from “sliding” as we tweak the size of certain masses. More specifically, we
will use a first-variation argument to show that moving interval endpoints at
speed $1/f$ will naturally preserve enclosed area while moving perimeter. This
first variation argument breaks down when $f=0$, making the origin a natural
interval endpoint. Our log-concave requirement will also play a role in our
first variation analysis.

###  1.1 Overview of the argument

Our argument follows a proof by induction on the number of regions. The first
several cases are already known in the case of $|x|^{p}$ (see [5] [1]), and
for a general log-concave density function the base case is given as an
immediate offshoot of Corollary 3.8. For the inductive case, we assume that
the standard position is the only isoperimetric solution for bubbles of $n$ or
fewer regions. For contradiction, we assume there exist a specific set of
$n+1$ masses for which an isoperimetric solution _other_ than standard
position exists. We spend several sections drawing conclusions about what any
isoperimetric configuration (standard or nonstandard) must look like. An
important result here is Corollary 3.8, in which we use the first variation
formula to show that an $n$-bubble must have exactly $n$ intervals. (Note that
this immediately distinguishes our log-concave situation from the log-convex
case studied in [3].) Because of this, we can differentiate the standard and
nonstandard solutions by identifying the “outermost interval that breaks the
standard pattern.” We then use this interval as the foundation for our
contradiction, swapping two intervals to get less total perimeter. In order to
make the comparison work, we first carefully adjust the size of certain masses
to develop a new set of masses with two isoperimetric solutions (one standard,
one nonstandard). that can be easily compared, and from which the
contradiction more readily appears. The mass-adjustments are described in
Section 4, and a fundamental result that allows us to adjust these masses is
Proposition 3.9.

Our paper is organized as follows. Section 2 includes definitions and other
preliminary work. Section 3 explores the first variation formulas for mass and
perimeter, and then uses these tools to show any isoperimetric $n$-bubble must
have exactly $n$ intervals. Section 4 explores how tweaking our region sizes
(by inflating or deflating certain masses) will change our isoperimetric
configurations. Finally, Section 5 shows our induction proof of the $n$-bubble
problem.

###  1.2 A quick remark on images in this paper

Throughout this paper, we inlude images of the real number line with a density
function. The images almost exclusively show the density function $f(x)=|x|$.
However, this is simply done to standardize the images: the function shown
should be viewed as a stand-in for any radially symmetric, log-concave density
function with a point of 0 density at the origin. The exception is Figure 1,
which gives a basic example specifically for $f(x)=|x|$.

##  2 Preliminaries

In this section we include some basic definitions and early results.

######  Definition 2.1.

A density function on $\mathbb{R}$ is simply a nonnegative function $f$.

######  Definition 2.2.

Given an interval $[a,b]$ and a density $f$, the weighted mass of the interval
with respect to the density is $\int_{a}^{b}f$. The weighted perimeter with
respect to the density is defined to be $f(a)+f(b)$. Note that, in this paper,
weighted mass is sometimes simply called mass, area, or volume, and that
weighted perimeter is sometimes called perimeter.

######  Definition 2.3.

A region on $\mathbb{R}$ is a collection of disjoint intervals $[a_{i},b_{i}]$
with total mass $M$ and perimeter $P$

$\displaystyle M$ $\displaystyle=\displaystyle\sum_{i}\int_{a_{i}}^{b_{i}}f$
$\displaystyle P$ $\displaystyle=\displaystyle\sum_{i}f(a_{i})+f(b_{i})$

We remark that, under many natural density functions (in particular: density
functions that have a positive lower bound), regions with finite mass or
finite perimeter must necessarily be made up of only finitely many intervals.
With a point of zero density, it is possible to have a region of finite mass
consisting of infinitely many interval that are accumulating at the point of
zero density.

######  Definition 2.4.

A region $R$ with mass $M$ and perimeter $P$ is said to be isoperimetric (and
is also referred to as a bubble or a 1-bubble) if, out of all possible regions
with mass $M$, $R$ has the least perimeter.

$4$$-2$

$\sqrt{20}$

Figure 1: Above, we see an example with density function $f(x)=|x|$, and
regions of weighted mass 10 arranged in two different configurations. The
first configuration, defined on the interval $[-2,4]$, has weighted perimeter
of 6. The second configuration, defined on the interval $[0,\sqrt{20}]$, has
weighted perimeter of $\sqrt{20}\approx 4.47$. This second configuration is
the isoperimetric 1-bubble, as shown in [5]. Note that in each picture, the
“region” is an interval, while the weighted volume is calculated as (and
displayed as) area under the density function.

We can also consider multiple regions on the same number line. In such a
situation, each region consists of (possibly multiple, disjoint) intervals.
Two intervals, each from a different region, are either completely disjoint or
meet at a single endpoint. In addition to measuring the mass and perimeter of
each region, we can measure the total (weighted) perimeter by summing the
perimeter of each of the regions. In doing so, any point where two intervals
meet is only counted once.

######  Definition 2.5.

A configuration of n regions $R_{1},\dots,R_{n}$ with masses
$M_{1},\dots,M_{n}$ is said to be isoperimetric (and is referred to as an
$n$-bubble) if, out of all possible configurations of regions with the same
masses, this configuration has the least total perimeter.

To begin exploring isoperimetry in earnest, we can start by looking at one
side of the number line (say, without loss of generality, the positive side
$x\geq 0$). Our first result says that we can benefit (resulting in lower
perimeter) by consolidating our regions into adjacent intervals near the
origin.

######  Proposition 2.6.

On the positive real number line $(x\geq 0)$ with an increasing density
function $f$, suppose we have a number of regions $R_{1}...R_{n}$ with masses
$M_{1},\dots,M_{n}$. Note that each region could consist of one or more
intervals, and that there might be “empty” intervals that do not correspond to
any particular region. Nevertheless, we can create a new configuration of
regions which simultaneously preserve mass and decrease perimeter. In this new
configuration, each region consists of a single interval, and there are no
empty intervals.

###### Proof.

Suppose we have an arbitrary configuration on $n$ regions, each consisting of
(possibly multiple) intervals on the non-negative axis $x\geq 0$. WLOG, we
identify $R_{1}$ to have a maximum value (and rightmost endpoint) of $b_{1}$,
$R_{2}$ to have a maximum value of $b_{2}$, and so on, named so that
$b_{1}<b_{2}<\dots<b_{n}$. As seen in Figure 2, we can create a new
configuration in which regions consist of a single interval, each of which are
adjacent and ordered so that region $R_{i}$ sits to the left of region $R_{j}$
if $i<j$. Furthermore, this can clearly be done in such a manner that the mass
of each region is preserved.

$b_{1}$$b_{2}$$b_{3}$

$b_{1}^{\prime}$$b_{2}^{\prime}$$b_{3}^{\prime}$

Figure 2: We see how an arbirtrary arrangement (on the left) can be
consolidated (shown the right) in a manner that lowers perimeter.

Because of how we have constructed these regions, it is clear that the new
rightmost endpoint $b_{j}^{\prime}$ of the region $R_{j}$ satisfies
$0<b_{j}^{\prime}\leq b_{j}$. Since $f$ is assumed to be increasing, we know
$f(b_{j}^{\prime})\leq f(b_{j})$. This gives us the following inequalities for
the new and original perimeter:

$P_{new}=\displaystyle\sum_{j=1}^{n}f(b_{j}^{\prime})\leq\displaystyle\sum_{j=1}^{n}f(b_{j})\leq
P_{orig}$

completing the proof. ∎

######  Corollary 2.7.

If a configuration of $n$ regions is isoperimetric, then the configuration
consists of at most $2n$ adjacent intervals, with the origin contained in at
least one of the intervals (either at an interior or an endpoint).

###### Proof.

Our previous proposition says that we can reconfigure our regions so that
there are at most $n$ intervals on the positive side, and at most $n$
intervals on the negative side. (i.e., each region will have at most one
interval on each side of the origin.) Furthermore, as the consolidation from
before occurs at the origin, it is clear that the origin will either be
between two different regions (in which case it’s an endpoint of each), or in
a single region (with some mass to be found on both the positive and negative
side). ∎

Beyond simply knowing that our regions accumulate near the origin, we also
learn that we can reorder them so that they “grow” from smallest to largest
mass as we move further out from the origin. This follows immediately from
iterating the transposition lemma, which we state below.

######  Proposition 2.8 (Transposition Lemma).

Consider a configuration of regions $R_{i}$ ($i=1,2$) such that the regions
are individual intervals adjacent to each other on the positive $x$-axis.
Suppose each $R_{i}$ has mass $M_{i}$, and suppose $M_{1}<M_{2}$. Then
weighted perimeter is minimized when the interval for $R_{1}$ lies to the left
of the interval for $R_{2}$.

###### Proof.

This is seen immediately in Figure 3. Keeping the leftmost and rightmost
endpoints fixed, and transposing the two intervals if necessary, we see that
the perimeter is lowered when the interval with less mass is placed to the
left (as it moves the internal endpoint to the left). ∎

Figure 3: Transposition of adjacent intervals: If we transpose $R_{1}$ and
$R_{2}$ without changing their global location, the lower perimeter results
from placing the smaller interval closer to the origin (as the only endpoint
to move is the internal endpoint). Iterating the transposition lemma
guarantees that, on one side of the interval, regions will be ordered
(according to weighted area) from smallest to largest as we move away from the
origin.

######  Definition 2.9.

A configuration of $n$ regions is said to be in a condensed configuration if
it satisfies the following conditions:

  * •

the configuration consists of at most $2n$ adjacent intervals, with each
region contributing at most one interval on each side of the origin.

  * •

the origin is contained in at least one of the intervals, possibly as an
endpoint.

  * •

The intervals are all adjacent, and – working from the origin outward – they
increase in size.

######  Remark 2.10.

Due to Proposition 2.6, we know a necessary condition for a configuration to
be isoperimetric is for it to be condensed.

We conclude this section with an important comparison lemma that allows us to
compare intervals of appropriate masses. Although it is stated for the
positive real number line, it is clear (due to the symmetry of $f$) that there
is a corresponding statement on the negative real number line.

######  Proposition 2.11.

On the positive real number line with a symmetric, radially incresaing density
$f$: Consider two intervals $R_{1}=[a_{1},b_{1}]$, $R_{2}=[a_{2},b_{2}]$.
Suppose that each of these intervals contains the same mass ($M_{1}=M_{2}$),
and suppose the innermost endpoint of the first region is closer to the origin
than the second $(a_{1}<a_{2})$. Then the following two inequalities hold
true:

$b_{1}<b_{2}\qquad\text{and}\qquad b_{1}-a_{1}>b_{2}-a_{2}.$

###### Proof.

The first inequality is an immediate consequence of the two intervals
enclosing the same mass. For the final inequality, note that since
$[a_{2},b_{2}]$ is further away from the origin. Since our density function is
radially increasing as we move away from the origin, the average density of
$[a_{2},b_{2}]$ will be larger than that of $[a_{1},b_{1}]$, and since they
each contain the same amount of mass, this means the interval $[a_{2},b_{2}]$
will be smaller. ∎

######  Corollary 2.12.

The first inequality above continues to hold true in the cases where
$M_{2}\geq M_{1}$. The second inequality also holds true in the cases where
$M_{2}\leq M_{1}$.

##  3 The First Variation of Mass and Perimeter

In this section, we briefly introduce the concept of continuously varying
configurations and the first variation formula. We will introduce this for an
arbitrary density function $f$ over the real number line.

###  3.1 The First Variation Formulas

Consider an interval of $[a,x]$. We have already seen how the weighted mass
$M$ and perimeter $P$ are measured as $\int_{a}^{x}f$ and $f(a)+f(x)$,
respectively. An immediate consequence of this is that

$\displaystyle\frac{dM}{dx}$ $\displaystyle=f(x)$ (3.1)
$\displaystyle\frac{dP}{dx}$ $\displaystyle=f^{\prime}(x).$ (3.2)

Suppose that we let $x=x(t)$ vary as a function of time, and with a specified
velocity $x^{\prime}(t)$. This will allow us to calculate

$\displaystyle\frac{dM}{dt}$ $\displaystyle=f(x(t))x^{\prime}(t)$ (3.3)
$\displaystyle\frac{dP}{dt}$ $\displaystyle=f^{\prime}(x(t))x^{\prime}(t).$
(3.4)

If we choose our velocity to equal $1/f(x(t))$, these equations become

$\displaystyle\frac{dM}{dt}$ $\displaystyle=1$ (3.5)
$\displaystyle\frac{dP}{dt}$
$\displaystyle=f^{\prime}(x(t))/f(x(t))=\frac{d}{dx}\left[\log(f(x(t)))\right].$
(3.6)

$a$$x$ Figure 4: The interval $[a,x(t)]$ has one endpoint dragged to the right
at speed $x^{\prime}(t)=1/f(x)$.

An immediate consequence of this is as follows:

######  Proposition 3.1 (The first variation formula).

Suppose we take an interval $[a,b]$, and drag _both_ endpoints to the right at
speed $1/f(x)$. Then the weighted mass of the interval will not change, while
the perimeter’s instantaneous rate of change will be
$(\log(f))^{\prime}(a)+(\log(f))^{\prime}(b)$

######  Corollary 3.2.

Suppose we taken an isoperimetric $n$-bubble, comprised of a number of
intervals with all endpoints of all intervals listed as
$x_{1},x_{2},\dots,x_{m}$. Then

$\sum_{i=1}^{m}\log(f)^{\prime}(x_{i})=0.$

###### Proof.

If our region is isoperimetric, it has minimal perimeter out of all other
configurations that have regions with the same prescribed masses. This means,
as we vary our configuration by dragging every endpoint to the right at speed
$1/f$, our masses will stay the same and our perimeter must have been at a
local/global minimum. Thus, its instantaneous rate of change should be 0. ∎

######  Remark 3.3.

With our chosen density function $f(x)$, the first variation formula is not
defined when there is an endpoint at $x=0$. However, as long as we are not
dragging an endpoint across the origin, we can use the first variation formula
as usual. Indeed, we will see that the point of zero density at the origin
leads endpoints of regions to naturally “slide” towards the origin.

###  3.2 Consolidating regions using the first variation

We have already seen that an $n$-bubble will consist of at most $2n$
intervals. We use the first variation formula in a number of ways to reduce
the number of total intervals. We begin by identifying the different ways in
which multiple intervals can be relatively positioned.

######  Definition 3.4.

Suppose we have a condensed configuration of $n$ regions, and suppose that
there are two regions (call them $A$ and $B$) each with two intervals, one on
each side of the origin. Call these intervals $A^{-}$, $A^{+}$, $B^{-}$, and
$B^{+}$ depending on their position relative to the origin. Then the regions
$A$, $B$ are said to be alternating if their relative positions, ordered left
to right, are as $A^{-}$, $B^{-}$, $A^{+}$, $B^{+}$ or as $B^{-}$, $A^{-}$,
$B^{+}$, $A^{+}$.

If $A$ and $B$ are not in an alternating pattern, this means that the relative
positions are either as $A^{-}$, $B^{-}$, $B^{+}$, $A^{+}$ or as $B^{-}$,
$A^{-}$, $A^{+}$, $B^{+}$. In this case, we say that $A$, $B$ are nested.

Our next lemma will guarantee that alternating patterns cannot be
isoperimetric: if such a configuration exists, we can use the first variation
formula to create a continuous movement that preserves the masses of our $n$
regions while reducing total perimeter. The core idea present – simultaneous
siphoning of area from each of the inner intervals in the alternating pattern
– was used in [3] to reduce the number of possible intervals in a 2-bubble.

######  Proposition 3.5.

On the real number line with a radially increasing density function $f$:
Suppose there exists a condensed configuration of $n$ regions, with two
regions in an alternating pattern. Then we can create a new configuration the
same $n$ masses and lower total perimeter that eliminates at least one of the
inner intervals in the alternating pattern.

###### Proof.

Suppose we have a condensed configuration of $n$ regions such that two regions
(identified as $A$ and $B$) exist in an alternating pattern. WLOG, suppose
points in these intervals satisfy $A^{-}\leq B^{-}\leq 0\leq A^{+}\leq B^{+}$.

Take the right endpoint of $A^{-}$, the left endpoint of $B^{-}$, and all
interval endpoints between these two. We drag these endpoints to the right at
speed $1/f(x)$. Simultaneously, we take the right endpoint of $A^{+}$, the
left endpoint of $B^{+}$, and all interval endpoints between these two, and
drag these endpoints to the left at speed $1/f(x)$. This process is
illustrated in Figure 5. According to Proposition 3.1, this process does not
change the weighted masses of any region for which both endpoints are moving.
Additionally, the masses for $A$ and $B$ are not changing: the mass gained by
$A^{-}$ (and $B^{+}$) is identical to the mass lost by $A^{+}$ (and $B^{-}$).
Since $f$ is radially increasing and our endpoints are all moving towards the
origin, this variation reduces total weighted perimeter. Since no moving
endpoint is in danger of reaching the origin, this process can continue until
either $B^{-}$ or $A^{+}$ has shrunk entirely to size 0. We see that perimeter
was made to decrease throughout this process, and continued to decrease until
one of the central intervals in the alternating pattern completely disappears.
∎

$G$$G$$B$$B$

$B$$B$$G$$G$

$B$$G$$G$

Figure 5: In the first image, the blue region “B” and green region “G” consist
of alternating intervals. In the second image, we see which endpoints we slide
to reduce perimeter and maintain constant weighted volumes. In the final
image, the blue region closest to the origin was fully moved to the other blue
mass. At this point, the sliding is done and the alternating pattern has been
eliminated.

Note that the proposition above holds for all density functions that are
radially increasing, because every perimeter point that is moving is moving
towards the origin. Our next argument allows us to eliminate any 2-interval
region, combining it into a single interval on one side of the origin, in the
situation where our density function is log-concave.

######  Proposition 3.6.

Suppose we have $n$ regions in a condensed form on the number line, and
suppose that one region can be written as the union of two intervals, one non-
positive and one non-negative. Then there exists a configuration $n$ regions
with the same masses as before, but with lower perimeter than before, achieved
by combining the region identified above into a single interval on one side of
the origin.

###### Proof.

Suppose we have our condensed configuration of regions. Identify region
$R=R^{-}\cup R^{+}=[r_{1},r_{2}]\cup[r_{3},r_{4}]$ as split into intervals on
the negative and positive side of the origin, respectively. Then we proceed as
follows: first, take all endpoints less than $r_{2}$, as well as all endpoints
greater than $r_{3}$. (Note that this set of endpoints includes $r_{1}$ and
$r_{4}$.) Then, shift _only these endpoints_ to the right at speed $1/f$.
According to the first variation formula for enclosed mass, this results in
movement that keeps the weighted mass of each region constant (with $R$’s mass
staying constant because $[r_{1},r_{2}]$ is losing mass at the same rate
$[r_{3},r_{4}]$ is gaining mass). And by the first variation formula for
perimeter, we know the total perimeter changes at rates of

$\displaystyle\frac{dP}{dt}$ $\displaystyle=\sum f^{\prime}(x(t))/f(x(t))$
$\displaystyle\frac{d^{2}P}{dt^{2}}$
$\displaystyle=\sum\frac{f(x(t))f^{\prime\prime}(x(t))-\left[f^{\prime}(x(t))\right]^{2}}{\left[f(x(t))\right]^{3}}$

where the summation is taken over all perimeter points that are moving.
Notably, we can observe that the second derivative of perimeter is negative if
$f$ is log-concave. So the perimeter function $P$, when dragging every
perimeter point to the right, is concave down. There are therefore two
possibilities:

  1. 1.

If perimeter is decreasing (so $P^{\prime}<0$), it will continue to decrease.
We can therefore continue in this manner until the endpoint $r_{1}$ has been
dragged to collide with endpoint $r_{2}$.

  2. 2.

If perimeter is increasing, we instead drag every one of our targeted points
to the _left_ with speed $1/f(x)$. This will keep the masses the same, will
change the sign of $P^{\prime}$, and will leave $P^{\prime\prime}$ negative.
The result is that perimeter will decrease, and will continue to decrease
until the endpoint $r_{4}$ collides with the endpoint $r_{3}$.

Thus, we see that we can drag endpoints in a manner that decreases perimeter
until either $[r_{1},r_{2}]$ or $[r_{3},r_{4}]$ disappears. Either way, we are
left with the entirety of region $R$ on one side of the origin. ∎

######  Corollary 3.7.

If our density function $f$ is radially symmetric and log-concave: Suppose we
have $n$ regions in a condensed form on the number line, and suppose the
origin is contained in the interior of one region. Then our configuration is
not isoperimetric, and we can lower perimeter by moving this region entirely
to one side of the origin.

###### Proof.

The same argument as above applies, with the region in question being
interpreted as the union of two intervals, each directly adjacent to the
origin. In this interpretation, every endpoint (except the origin) will be
dragged to the right or the left in the variation. ∎

######  Corollary 3.8.

If our density function $f$ is radially symmetric and log-concave: An
isoperimetric configuration with $n$ regions consists of exactly $n$
intervals, with one interval per region. The origin will sit as an endpoint to
two distinct regions.

We conclude this section with an important inequality relating perimeter
points to intervals that contain the same mass. The result, due to the log-
concavity of the density function, should be viewed as similar to those of
Proposition 2.11.

######  Proposition 3.9.

On the positive real number line with a log-concave density function $f$:
Consider two intervals $R_{1}=[a_{1},b_{1}]$, $R_{2}=[a_{2},b_{2}]$. Suppose
that each of these intervals contains the same mass ($M_{1}=M_{2}$), and
suppose the innermost endpoint of the first region is closer to the origin
than the second $(a_{1}<a_{2})$. Then

$f(b_{1})-f(a_{1})\geq f(b_{2})-f(a_{2}).$

###### Proof.

Let $Q(t)=f(b(t))-f(a(t))$ with $a(0)=a_{1}$ and $b(0)=b_{1}$, and consider
what happens to $Q(t)$ as we drag points $a,b$ to the right at speed $1/f$.
The first variation formula tells us

$Q^{\prime}(t)=\frac{f^{\prime}(b(t))}{f(b(t))}-\frac{f^{\prime}(a(t))}{f(a(t))}.$

Since $f$ is log-concave, we know the quantity $f^{\prime}/f$ is _decreasing_
, meaning that (as long as $a<b$) we will have $Q^{\prime}(t)\leq 0$.
Therefore, $Q(t)$ is a monotone decreasing quantity, and will be smaller by
the time it gets to points $a_{2}$, $b_{2}$. This completes the proof.

∎

###  3.3 A standard $n$-bubble configuration

We are now in a position to identify our “standard” $n$-bubble configuration.
Corollary 3.8 has shown that every $n$-bubble must have exactly $n$ intervals
positioned along the real number line; that the intervals must be arranged in
a condensed manner (in the spirit of Definition 2.9); and that the origin will
appear as an endpoint for two distinct intervals/regions. The final question
is the appropriate order for the intervals, i.e. on which side of the origin
they will appear.

######  Definition 3.10.

Suppose we have a set of $n$ fixed masses $\\{M_{1},\dots,M_{n}\\}$ that
satisfy $0<M_{1}\leq M_{2}\leq\dots\leq M_{n}$. Then the standard
configuration of these masses will be an arrangement of $n$ regions (with
$R_{i}$ containing mass $M_{i}$), such that

  * •

The regions are condensed (in the spirit of Definition 2.9) and appear as
single intervals (in the spirit of Corollary 3.8).

  * •

The region $R_{i}$ is found on the positive side or the negative side of the
origin depending solely on the parity of its index, so odd-indexed regions
appear the opposite side of the even-indexed regions.

Because of the nature of condensed regions (following Definition 2.9 and the
transposition lemma), we know that smaller regions will appear closer to the
origin. This, along with the even/odd index split across the origin,
completely determines the positions of the intervals. Figure 6 shows a
standard 5-bubble.

$R_{1}$$R_{2}$$R_{3}$$R_{4}$$R_{5}$ Figure 6: A standard $5$-bubble,
consisting of regions $R_{i}$ of weighted mass $M_{i}$ satisfying $M_{1}\leq
M_{2}\leq M_{3}\leq M_{4}\leq M_{5}$. Note that the masses are weighted by the
function $f(x)=|x|$, so (e.g.) even though the interval associated with
$R_{2}$ appears larger than the interval associated with $R_{3}$, the weighted
masses satisfy $M_{3}>M_{2}$.

######  Theorem 1.

For any $n\in\mathbb{N}$, and any collection of $n$ masses, the standard
configuration is the only isoperimetric $n$-bubble with these masses.

##  4 Manipulating volumes of regions

In this section, we explore how changing the weighted volumes of the regions
will affect the isoperimetric configuration. These arguments will be used
later in our induction/contradiction argument by changing our (non-standard)
isoperimetric configuration to a related (non-standard) isoperimetric
configuration with different sized regions.

###  4.1 Adding a region of small size $\epsilon$

We want to imagine what happens if we take a set of $n$ regions in standard
position and “add in” an $(n+1)$th region. A priori, we want this new region
to be able to have any mass (so we are not simply creating a new region of
largest mass or of smallest mass). We could imagine doing this by injecting
the new region into the configuration (possibly as multiple intervals), and
shifting/rearranging the rest of the regions to accommodate this new addition.
A special case of adding a new region is identified here:

######  Definition 4.1.

Suppose we have $n$ regions arranged in standard position. Then we say a
newly-introduced $(n+1)$th region willmaintain standard position if the new
configuration with $n+1$ regions is also in standard position.

Of course, by simply inserting a new region (even as a single interval) we
might lose the “positive/negative parity” of the (reindexed) regions. To
maintain this parity, we either need our inserted region to be smaller than
all other regions (and inserted directly adjacent to the origin); larger than
all other regions (and inserted on the outside of the configuration); or, when
inserting it into the middle of the configuration, all regions with more mass
than the inserted region must be rearranged (by swapping sides across the
origin). In what follows below, we see that introducing a mass into a standard
configuration of $n$ regions is best done by maintaining standard position, if
the introduced mass is small.

######  Proposition 4.2.

Suppose that we have $n$ regions (of mass $M_{1}\leq\dots\leq M_{n}$) arranged
in a standard position. Then there exists an $\epsilon$, depending on $n$,
such that the following is true: when adding an $(n+1)$th region of size
$\leq\epsilon$ to the configuration, perimeter is minimized by adding the new
region a way that maintains standard position.

###### Proof.

We observe that our original $n$ regions have a total of $n$ endpoints other
than the origin, and each region can be identified by its endpoint furthest
from the origin. Call these endpoints $b_{i}$. Then the total perimeter is
$\sum_{i}f(b_{i})$. When adding an $(n+1)$th region, we see that adding it in
a manner that places it adjacent to the origin will result in each other
interval “shifting” a little to the right or left, slightly increasing the
value of each $b_{i}$ on that side of the origin. We can observe that a region
of mass $\epsilon$ inserted next to the origin (say, on the positive side)
will have an endpoint $b_{*}$ determined $\int_{0}^{b_{*}}f=\epsilon$, and a
new perimeter value of $f(b_{*})$. Furthermore, all endpoints on this side of
the origin will shift. Due to Proposition 3.9, each endpoint’s shift will
result in a perimeter increase less than $f(b_{*})$. So as a (very rough)
estimate, inserting our new mass adjacent to the origin will increase total
perimeter less than $(n+1)f(b_{*})$. Since our density has a point of 0
density at the origin, by making $\epsilon$ small we will make this quantity
less than any $f(b_{i})$, which is an underestimate for the perimeter added if
our new region is inserted adjacent to another $M_{i}$.

Therefore, our small $(n+1)$th region must be inserted adjacent to the origin
to minimize added perimeter. A quick check allows us to verify that it will be
better inserted into standard position (which will be across the origin from
$M_{1}$). ∎

The previous result is not surprising, as it can be viewed through a lens of
continuity. Indeed, we largely expect isoperimetric configurations to vary
continuously as the masses of the regiouns vary in a continuous manner. In
this way, we can imagine the standard configuration of $n+1$ regions varying
continuously as the smallest region (noted above as having volume $\epsilon$)
shrinks to 0.

One concern of ours is that there might exist a set of set of $n+1$ masses for
which there are two distinct isoperimetric configurations. One could imagine
that varying one (or more) of the masses in such a set could result in
diverging isoperimetric configurations.

######  Definition 4.3.

A set of masses $\\{M_{i}\\}$ for which two configurations of regions are
simultaneously isoperimetric will be called a bifurcating set of masses

Our result above shows that, when $n$ masses are fixed and one mass is small,
our set of masses will not be bifurcating.

######  Corollary 4.4.

Suppose that we know that the standard configuration for $n$ masses is the
isoperimetric configuration. Then given $n+1$ masses, where one of the masses
is suitably small, we can be guaranteed that the isoperimetric configuration
will be the standard position.

######  Corollary 4.5.

Suppose it is known that any configuration of $n$ regions has a standard
isoperimetric configuration. However, suppose there is a some set of $n+1$
masses whose isoperimetric configuration is non-standard. Then, by shrinking
the mass of the smallest region, we can find a bifurcating set of $n+1$
masses. Of the isoperimetric configurations, one will be in standard position.

###### Proof.

Assume there exists a set of $n+1$ regions (call the regions $R_{i}$, each of
mass $M_{i}$, with $M_{1}\leq\dots\leq M_{n+1}$) whose isoperimetric
configuration is non-standard. We know that $M_{1}$ cannot be too small (or
else the configuration would be standard). We will say a mass $x>0$ is below
the bifurcation threshold if the isoperimetric configuration for masses
$y,M_{2},\dots,M_{n+1}$ is standard for all $y\leq x$. Let $\epsilon$ be
defined as $\epsilon=\sup\\{x:x\;\text{is below the threshold}\\}$. Then by
continuity, we know that the $n+1$ masses $\\{\epsilon,M_{2},\dots,M_{n+1}\\}$
are bifurcating: there are at least two isoperimetric configurations, one of
which is standard. ∎

###  4.2 Inflating a large mass in a bifurcating set of masses

Here we explore in detail an argument that will be generalized later. Suppose
we have a collection of masses $M_{1}\leq M_{2}\leq\dots\leq M_{n+1}$ that can
be configured in two distinct isoperimetrc regions, one standard and one non-
standard. Our work in sections 2 and 3 guarantee that in both isoperimetric
configurations there are exactly $n+1$ intervals, whose masses increase as
they move away from the origin. This means that the region of largest mass
must be “external” to the configuration in both the standard and non-standard
solutions. WLOG, we assume the region of mass $M_{n+1}$ appears on the
positive side of the $x$-axis in both images. Let the $n+1$ endpoints (other
than the origin) in the standard configuration be denoted as $a_{i}$, and let
the endpoints in the non-standard configuration be denoted as $b_{i}$. Since
both configurations are isoperimetric, we have

$\sum_{i=1}^{n+1}f(a_{i})=\sum_{i=1}^{n+1}f(b_{i}).$

Let us assume for a moment that any configuration of $n$ regions is
isoperimetric if and only if it is in standard position. Then we know

$\sum_{i=1}^{n}f(a_{i})<\sum_{i=1}^{n}f(b_{i}).$

This tells us that $a_{n+1}>b_{n+1}$. An immediate consequence of this
follows:

######  Corollary 4.6.

Suppose we it is known that the sole isoperimetric solution with $n$ regions
is the standard one, and suppose we have a bifurcating set of masses
$\\{M_{i}\\}_{i=1}^{n+1}$. WLOG, assume the largest region appears on the
positive side in both configurations, and name the endpoints $a_{i}$ and
$b_{i}$ for the standard and nonstandard solutions respectively. Call the
leftmost endpoint of the leftmost region $a_{*}$ (for the standard
configuration) and $b_{*}$ (for the non-standard). Then $a_{*}>b_{*}$.

###### Proof.

From our work above, we know that $a_{n+1}>b_{n+1}$. These are the rightmost
endpoints of each of our isoperimetric solutions. Since both configurations
have the same total mass between the leftmost and rightmost endpoints (namely,
$\sum M_{i}$), we must have $a_{*}>b_{*}$ as well. ∎

######  Definition 4.7.

Suppose we have two isoperimetric solutions (one standard and one non-
standard) with masses $M_{1}\leq\dots\leq M_{n+1}$, with $a_{i}$ and $b_{i}$
defined as above (for the standard and non-standard solution, respectively).
If $b_{*}<a_{*}\leq 0<b_{n+1}<a_{n+1}$, we say the nonstandard solution is
shifted to the left of the standard solution.

Our main result of this section is as follows:

######  Proposition 4.8.

Suppose we have a bifurcating set of masses with two isoperimetric solutions
(one standard and one nonstandard). WLOG, assume the largest region is on the
positive side of the origin. Suppose the second-largest region, $M_{\star}$,
is on the negative side of the origin. Then, by increasing the value of
$M_{*}$ (and thus inflating the left-most region of each configuration), we
can create a new set of masses in which the standard configuration fails to be
isoperimetric.

###### Proof.

Referring to Figure 7, suppose we have two isoperimetric configurations, one
standard (with endpoints $a_{i}$) and one non-standard (with endpoints
$b_{i}$). Enlarging the second-largest mass, $M_{*}$ will shift $a_{*}$ and
$b_{*}$ to new values, $a^{\prime}_{*}$ and $b^{\prime}_{*}$. However, we know
the non-standard configuration is shifted to the left, and due to Proposition
3.9 we can conclude $f(a^{\prime}_{*})-f(a_{*})>f(b^{\prime}_{*})-f(b_{*})$.
Calculating the perimeter of our new configuration, we see that the $\sum
f(a_{i})>\sum f(b_{i})$, and that the nonstandard configuration now has less
perimeter than the standard. Therefore, the standard configuration with this
new set of masses cannot be isoperimetric. ∎

$a_{*}$

$b_{*}$

Figure 7: Our two images represent two different isoperimetric configurations
(whose details, except for the leftmost region $M_{*}$, are hidden in the blue
region of the $x$-axis). We note that the second picture is left-shifted, so
$b_{*}<a_{*}$. Inflating the mass $M_{*}$ will shift these points to the left,
but (due to the left-shifted nature) will increase the perimeter for the
standard configuration more than the nonstandard.

##  5 Proof of the $n$-bubble theorem

In this section, we prove Theorem 1’s claim that the only isoperimetric
solution is the standard one. We do this by induction. Suppose it is known
that every set of $n$ positive masses has the standard configuration as the
only isoperimetric solution. For contradiction, assume this is not true for
$n+1$. This means there exists at least one configuration of masses
$M_{1}\leq\dots\leq M_{n+1}$ for which there is a nonstandard isoperimetric
solution. Corollary 3.8 tells us that each region in this nonstandard
configuration consists of a single interval, that each interval is entirely on
one side of the origin, and that (on its respective side of the interval) the
intervals are ordered according to mass size, with the smaller masses closer
to the origin.

First, WLOG, we assume (shrinking $M_{1}$ if necessary) that our set of $n+1$
masses are bifurcating, with both a standard and nonstandard isoperimetric
solution. Identify the unique outer endpoints associated with mass $M_{i}$,
and name them $a_{i}$ (in the case of the standard solution) and $b_{i}$ (in
the case of the nonstandard solution). Assume our solutions are oriented so
that the largest region (associatd with $M_{n+1}$) appears on the positive
side of the origin in both configurations.

The standard solution will have regions (and endpoints $a_{i}$) that alternate
from the positive to the negative side as $i$ increases. The nonstandard
solution, by virtue of being nonstandard, will not – therefore it will need to
break this pattern at some point. There will need to be a largest pair of
consecutive indices $j$, $j+1$ for which $b_{j}$ and $b_{j+1}$ are both on the
same side of the origin. Our goal will be to use the intervals associated with
$M_{j}$ and $M_{j+1}$ to construct a contradiction.

An overview of our argument is as follows: We aim to perform a direct
comparison, but only after we carefully “inflate” the masses larger than
$M_{j+1}$ so that they each have a partner of equal mass on the opposite side
of the origin. We will inflate $M_{n}$ to be equal to $M_{n+1}$; inflate
$M_{n-2}$ to be equal to $M_{n-1}$; and so on, until we get to the offending
index. We will show that doing this carefully will allow us to keep both a
standard and nonstandard solution. Making the masses pairwise equal will
simplify the direct comparison of endpoints that we hope to do later.

Here, we include more details about “inflating” appropriate masses to reach
pairs of equal masses. We start with our largest indices. Assume $M_{n}$ is
strictly smaller than $M_{n+1}$. Additionally, assume that $b_{n}$ and
$b_{n+1}$ have opposite signs. (If they had the same sign, then we would
already have our consecutive indices with $j=n$.) Our previous work shows that
our nonstandard configuration is shifted to the left of the standard
configuration, so that $b_{n}<a_{n}<0$. In this case, $b_{n}$ is further away
from the origin than $a_{n}$. This means, as in Proposition 4.8, adding any
amount of mass to $M_{n}$ will shift $b_{n}$ and $a_{n}$ further to the left,
resulting in new points $b_{n}^{\prime}$ and $a_{n}^{\prime}$ that satisfy
$f(b_{n}^{\prime})-f(b_{n})<f(a_{n}^{\prime})-f(a_{n})$. We conclude that our
nonstandard configuration has less total perimeter than the standard
configuration. We have shown

Partial Result: If there exists a set of $n+1$ masses $M_{1}\leq\dots\leq
M_{n}+1$ for which a nonstandard framework is isoperimetric, and that
isoperimetric framework has $M_{n}$ and $M_{n+1}$ on opposite sides of the
origin, then there exists a (possibly new) set of $n+1$ masses, also with a
nonstandard isoperimetric configuration, in which the two largest masses are
of equal size.

######  Remark 5.1.

We can, if necessary, shrink our smallest mass until our set of masses is once
again a bifurcating set.

Next, we observe that when $M_{n}=M_{n+1}$, we can WLOG flip our nonstandard
configuration across the origin to put the third largest region ($M_{n-1}$) on
the side of the positive $x$-axis (this will already be true for the standard
configuration). By our assumption that $n$-bubbles are always standard, we
have that (newly flipped) nonstandard configuration is still shifted to the
left of the standard configuration.

We now perform a similar analysis on the third- and fourth-largest regions,
$M_{n-1}$ and $M_{n-2}$. Again, we assume that $b_{n-2}$ is on the negative
side of the axis (or else we would have our index $j$). We find that, as
before, we can “inflate” the size of $M_{n-2}$ until it reaches the same size
as $M_{n-1}$. This inflation would move the leftmost endpoints of each
configuration further to the left, in a manner that ultimately leads the
nonstandard configuration to have less perimeter than the standard
configuration. The details are shown in Figures 8 and 9. Notice that the four
intervals $[b_{n}^{\prime},b_{n}]$, $[b_{n-2}^{\prime},b_{n-2}]$,
$[a_{n}^{\prime},a_{n}]$, and $[a_{n-2}^{\prime},a_{n-2}]$ all have the same
weighted mass (which is exactly the difference between $M_{n-2}$ and
$M_{n-1}$). The left-shifted nature of our non-standard configuration, and
Proposition 3.9, implies that
$f(b_{n}^{\prime})-f(b_{n})<f(a_{n}^{\prime})-f(a_{n})$ and
$f(b_{n-2}^{\prime})-f(b_{n-2})<f(a_{n-2}^{\prime})-f(a_{n-2})$. This will
immediately imply that, after inflating $M_{n-2}$ and shifting our endpoints
appropriately, our new perimeter is lower in the nonstandard example. We have
shown

Partial Result: If there exists a set of $n+1$ masses $M_{1}\leq\dots\leq
M_{n}+1$ for which a nonstandard framework is isoperimetric, and that
isoperimetric framework has $M_{n-1}$ and $M_{n+1}$ on one side of the origin
opposite $M_{n}$ and $M_{n-2}$, then there exists a (possibly new) set of
$n+1$ masses, also with a nonstandard isoperimetric configuration, in which
$M_{n+1}=M_{n}$ and $M_{n-2}=M_{n-1}$.

$a_{n-2}$

$b_{n-2}$

Figure 8: Here we see two configurations with the same weighted perimeter. The
left picture is our standard configuration, while the right is a nonstandard
configuration. In each picture, the outermost (red) intervals contain the same
weighted area. In each picture, the yellow region contains mass that is
slightly bigger than the green region. To keep the picture clear, all smaller
intervals are omitted and shown as blue.
$b_{n-2}$$b_{n}$$b_{n}^{\prime}$$b_{n-2}^{\prime}$ Figure 9: Here, we see our
nonstandard configuration with $M_{n-2}$ inflated until the green interval has
the same weighted mass as the yellow interval. This has resulted in two of the
original endpoints ($b_{n}$ and $b_{n-2}$) shifting further to the left. (The
new endpoints are denoted $b_{n}^{\prime}$ and $b_{n-2}^{\prime}$.) A similar
shift occurs in the standard configuration, with new endpoints
$a_{n}^{\prime}$ and $a_{n-2}^{\prime}$.

We see that we can continue this process. At each step, we begin with a
bifurcation in which the outermost intervals, in pairs, have the same enclosed
mass. We then repeat the following actions:

  * •

Flip our nonstandard configuration (if necessary) to put the region with the
next-largest mass, $M_{k}$, on the positive side.

  * •

Observe that our nonstandard configuration is still shifted to the left of our
standard one.

  * •

If the interval with $M_{k-1}$ is on the negative side, we can “inflate”
$M_{k-1}$ until it is the same size as $M_{k}$. Due to the left shift and
Proposition 3.9, our nonstandard configuration will have total perimeter no
more than than our standard configuration, meaning that the standard
configuration is not solely isoperimetric.

  * •

Shrink $M_{1}$, if necessary, until our set of masses is once again
bifurcating (only now with $M_{k-1}$ set equal to $M_{k}$) as well.

We repeat as necessary until our we reach consecutive indices $j$, $j+1$ with
endpoints that are on the same (positive) side of the origin in our
nonstandard configuration. Note that the outer regions are grouped into pairs
of equal weighted volume. At this point, we have a nonstandard configuration
that looks like Figure 10

$c$$M_{2}$. . .$M_{\ell}$. . .
$M_{1}$$M_{3}$…$M_{j}$$d$$M_{j+1}$…$M_{n+1}$$M_{n}$ Figure 10: The $n+1$
regions are alternating for large indices, and these large indices are grouped
in consecutive pairs with equal volume ($M_{n+1}=M_{n}$, etc). The largest
index that fails this pattern in $j+1$, so that $M_{j}$ and $M_{j+1}$ are on
the same side of the origin. The largest index, smaller than $j$, that appears
on the other side of the origin is $\ell$.

Let $c$ be the outer endpoint of the interval associated with region
$M_{\ell}$, and let $d$ be the endpoint separating $M_{j}$ from $M_{j+1}$
(these endpoints have been identified in Figure 10). In short order, we will
show that $|d|<|c|$. We momentarily assume this, and additionally recognize
that $M_{\ell}<M_{j}$ (it is known that $M_{\ell}\leq M_{j}$, and if
$M_{\ell}=M_{j}$ we can simply change their index names so that $M_{j}$,
$M_{j+1}$ appear on opposite sides of the origin). Then, as seen in Figure 11,
transposing the regions associated with $M_{\ell}$ and $M_{j}$ will result in
lower total perimeter.

$c$$M_{2}$. . .$M_{\ell}$. . .
$M_{1}$$M_{3}$…$M_{j}$d$M_{j+1}$…$M_{N+1}$$M_{N}$ Figure 11: Transposing the
locations of the $j$th and $\ell$th regions will result in a decreasing of
perimeter. Endpoint $c$ and those to the left of $c$ will increase, but this
increase in perimeter will be offset by the decrease in perimeter by $d$ and
points to the left of $d$.

The decreased perimeter can be seen as follows. First, we recognie that
swapping the regions $M_{j}$ and $M_{\ell}$ will result in a shifting of a
certain number of endpoints. The endpoints that are less than or equal to $c$
will shift to the left, resulting in an increased contribution to perimeter.
Meanwhile, the endpoints that are greater than or equal to $d$ will also shift
to the left, but will result in a decrease in perimeter. (All endpoints are
known to shift to the left because $M_{\ell}<M_{j}$.) However, by counting
regions, we see that there is one more endpoint moving on the right than on
the left. This extra endpoint should be seen as $d$, because all other
shifting endpoints can be paired with a partner across the origin. Because
$|c|>|d|$, because we inflated masses to be paired and equal on opposite sides
of the origin, and using Proposition 3.9, we see that the decrease in
perimeter from each endpoint on the right outweights the increase in perimeter
from their partner on the left. Taken together, we see that the total
perimeter decreases after the transposition of $M_{j}$ and $M_{\ell}$. Thus,
the original nonstandard configuration could not have been isoperimetric,
giving us out contradiction.

Thus, to complete the argument, it remains to be seen that $|d|<|c|$. This is
shown in Figure 12 and uses the fact that our nonstandard configuration is
left-shifted when compared to our standard configuration.

$c$$M_{\ell}$. . . $M_{j}$$M_{j+1}$$d$…nonstandard$c^{\prime}$$M_{j}$. . .
$M_{j-1}$$M_{j+1}$$d^{\prime}$…standard Figure 12: A nonstandard and a
standard configuration lined up for comparison. The nonstandard configuration
is left-shifted.

Because the nonstandard configuration is left shifted, and because both
configurations have the same alternating pattern for the largest regions (i.e.
those greater than $j$), we can conclude that $d^{\prime}>d$ and that
$c^{\prime}>c$. Furthermore, because of the alternating nature of the standard
configuration, we know that $|c^{\prime}|>|d^{\prime}|$. Taken together, we
get $|c|>|c^{\prime}|>|d^{\prime}|>|d|$ as desired.

## References

  * [1] E. Alexander, E. Burns, J. Ross, J. Stovall, and Z. Whyte.  Isoperimetric 3- and 4-bubble results on $\mathbb{R}^{1}$ with density $|x|$.  Preprint, 2021.
  * [2] Viktor Blåsjö.  The isoperimetric problem.  The American Mathematical Monthly, 112(6):526–566, 2005.
  * [3] E. Bongiovanni, L. Di Giosia, A. Diaz, J. Habib, A. Kakkar, L. Kenigsberg, D. Pittman, N. Sothanaphan, and W. Zhu.  Double bubbles on the real line with log-convex density.  Analysis and Geometry in Metric Spaces, 6(1):64–88, 2018.
  * [4] G. Chambers.  Proof of the log-convex density conjeture.  J. Eur. Math. Soc., 21:2301–2332, 2019.
  * [5] J. Huang, X. Qian, Y. Pan, M. Xu, L. Yang, and J. Zhou.  Isoperimetric problems on the line with density $|x|^{p}$.  Rose-Hulman Undergraduate Mathematics Journal, 20(2), 2019.
  * [6] M. Hutchings, F. Morgan, M. Ritoré, and A. Ros.  Proof of the double bubble conjecture.  Annals of Mathematics, 155(2):459–489, 2002.
  * [7] F. Morgan and A. Pratelli.  Existence of isoperimetric regions in rn with density.  Ann. Glob. Anal. Geom., 43:331–365, 2013.
  * [8] Cesar Rosales, Antonio Cañete, Vincent Bayle, and Frank Morgan.  On the isoperimetric problem in euclidean space with density.  Calculus of Variations and Partial Differential Equations, 31, 03 2006.
  * [9] Nat Sothanaphan.  1d triple bubble problem with log-convex density.  11 2020.
  * [10] J. Steiner.  Einfacher beweis der isoperimetrischen hauptsatze.  J. reine angew Math., 18:281–296, 1838.
  * [11] Jakob Steiner.  Jacob Steiner’s Gesammelte Werke: Herausgegeben auf Veranlassung der königlich preussischen Akademie der Wissenschaften, volume 2 of Cambridge Library Collection - Mathematics.  Cambridge University Press, 2013.
  * [12] W. Wichiramala.  Proof of the planar triple bubble conjecture.  J. reine angew. Math., 2004(567):1–49, 2004.


# McQueen: a Benchmark for Multimodal Conversational Query Rewrite

Yifei Yuan1, Chen Shi2, Runze Wang2,
Liyi Chen3, Feijun Jiang2, Yuan You2, and Wai Lam1
1The Chinese University of Hong Kong
2Alibaba Group
3Nankai University
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>Work done when Yifei Yuan was an intern at
Alibaba. This work was supported by Alibaba Group through Alibaba Research
Intern Program, and a grant from the Research Grant Council of the Hong Kong
Special Administrative Region, China (Project Codes: 14200620).

###### Abstract

The task of query rewrite aims to convert an in-context query to its fully-
specified version where ellipsis and coreference are completed and referred-
back according to the history context. Although much progress has been made,
less efforts have been paid to real scenario conversations that involve
drawing information from more than one modalities. In this paper, we propose
the task of multimodal conversational query rewrite (McQR), which performs
query rewrite under the multimodal visual conversation setting. We collect a
large-scale dataset named McQueen based on manual annotation, which contains
15k visual conversations and over 80k queries where each one is associated
with a fully-specified rewrite version. In addition, for entities appearing in
the rewrite, we provide the corresponding image box annotation. We then use
the McQueen dataset to benchmark a state-of-the-art method for effectively
tackling the McQR task, which is based on a multimodal pre-trained model with
pointer generator. Extensive experiments are performed to demonstrate the
effectiveness of our model on this task111The dataset and code of this paper
are both available in https://github.com/yfyuan01/MQR.

McQueen: a Benchmark for Multimodal Conversational Query Rewrite

Yifei Yuan1††thanks:  Work done when Yifei Yuan was an intern at Alibaba. This
work was supported by Alibaba Group through Alibaba Research Intern Program,
and a grant from the Research Grant Council of the Hong Kong Special
Administrative Region, China (Project Codes: 14200620)., Chen Shi2, Runze
Wang2, Liyi Chen3, Feijun Jiang2, Yuan You2, and Wai Lam1 1The Chinese
University of Hong Kong 2Alibaba Group 3Nankai University
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

##  1 Introduction

Recent years have witnessed an increasing attention in conversational-related
tasks, such as conversational question answering Choi et al. (2018); Reddy et
al. (2019), visual conversation modeling Das et al. (2017), etc. One main
challenge in multi-turn conversation modeling is that information from context
history is easy to be abbreviated or omitted in the follow-up queries, causing
the so-called coreference and ellipsis. To address this concern, the task of
query rewrite Elgohary et al. (2019); Pan et al. (2019); Su et al. (2019) aims
to reconstruct the original query to a fully specified form based on its
history context. The rewrite eliminates the coreference and ellipsis in the
original query without changing its semantic information, thus helping turn
the more challenging multi-turn conversation modeling problem to a single-turn
version.

Figure 1: An example of the mulitmodal query rewrite task, where
$\mathcal{Q}$, $\mathcal{Q^{*}}$, and $\mathcal{A}$ denote the queries, their
corresponding rewrites and the answers. Red color denotes the coreference
rewrite part and blue denotes the ellipsis rewrite part. Image boxes are
utilized for representing the area of the entities in the rewrite.

Following this line, several attempts have been made in the query rewrite task
which achieve decent performance on the natural language level. Nevertheless,
conversations in real scenario tend to involve knowledge from more than one
modalities, such as vision, text, speech, etc. Information from different
modalities is not handled in isolation, but often integrated together to
improve the quality of perception and understanding. For example, as shown in
Figure 1, in the first turn of the visual conversation, with the lack of
context, the user directly uses the pronoun “it” to refer to the dog in the
image. In the third turn, for ellipsis that does not appear in the context
history, in order to perform ellipsis completion, one also needs to find clues
from the corresponding image. Rewriting the query under the circumstance where
grounding outside the text information is needed poses more challenges to
traditional query rewrite models that based only on textual features.

In this paper, we propose the task of multimodal conversational query rewrite
(McQR), which aims to perform query rewrite under the multimodal visual
conversation setting. To achieve this goal, we collect a large-scale dataset
called McQueen. Specifically, for each visual conversation consisting of an
image and the corresponding history question-answer context, we provide manual
rewrite for the query, where the coreference resolution and ellipsis
completion are performed respectively. Furthermore, in order to assist
downstream tasks such as coreference entity detection, for all the entities
appearing in the rewrite, we annotate the image boxes for representing their
corresponding image area.

We then use the McQueen dataset to benchmark a state-of-the-art method for
effectively tackling the McQR task. Inspired by the big success of pre-trained
models such as BERT Devlin et al. (2019), our model is based on a multimodal
pre-trained model where interactions between different modalities can be
better captured. Furthermore, we enhance the model with a pointer generator
specially designed for the multimodal Transformer blocks Vaswani et al.
(2017), so that the rewritten query is either generated from scratch or copied
from certain contextual parts with high attention weights. Extensive
experiments are conducted to compare our method with several state-of-the-art
methods. Our model outperforms all the methods in both the McQR task and two
subtasks. We further perform analysis to investigate the role of different
modalities in this task and demonstrate that the introduction of image
information provides extra guidance for the concerned query rewrite task.

In summary, the contribution of our paper lies in three folds:

  * •

We formally define the task of multimodal conversational query rewrite (McQR),
which aims to generate a fully-specified rewrite query based on both the
context history and the visual image.

  * •

We propose a large-scale dataset McQueen, containing 15k visual conversations
and over 80k rewrites. For the entities appearing in the rewrites, we also
annotate the image boxes for representing their corresponding image area.

  * •

We benchmark a multimodal Transformer-based model with pointer mechanism for
effectively tackling the McQR task. Extensive analysis shows the role of
different modalities in our model.

##  2 Related Work

###  2.1 Query Rewrite

The task of query rewrite provides reconstructed queries based on abbreviated
in-context queries without changing their semantic meaning. First introduced
by Elgohary et al. (2019); Su et al. (2019); Pan et al. (2019), most works
formulate it as a standard generation task, which can be solved via a
Sequence-to-Sequence model Quan et al. (2019); Vakulenko et al. (2021);
Anantha et al. (2021). Some attempts have been made to introduce a multi-task
learning setup in order to enhance the training process Rastogi et al. (2019);
Song et al. (2020); Zhang et al. (2020). Some works seek to focus on query
rewrite under the low-resource scenario Yu et al. (2020); Voskarides et al.
(2020); Yu et al. (2021). For modeling the linguistic knowledge in
conversational context more effectively, prior knowledge is leveraged such as
using semantic role labeling to provide extra guidance Xu et al. (2020), and
reducing the generation search space via sequence tagging Hao et al. (2021).
Although these works have achieved great performance on their corresponding
task, query rewrite under the multimodal setting has not been explored.

###  2.2 Visual Coreference Resolution

Visual dialog entails answering a set of questions grounded by an image Das et
al. (2017). Based on that, visual coreference resolution involves linking the
words in the text (usually nouns and pronouns) to a certain area in the image
Kong et al. (2014); Kottur et al. (2018). Following this line, Li et al.
(2021) restrict coreference resolution to pronouns and resolve coreferences in
visual dialog in an unsupervised way. Yu et al. (2019) define the task of
visual pronoun coreference resolution where a dataset called VisPro and a
model called VisCoref are benchmarked accordingly. Based on that, Yu et al.
(2022) resolve pronoun coreference and propose a novel framework to improve
visual dialog understanding. This task can be seen as a subtask of the McQR
task where coreference resolution and ellipsis completion are both taken into
account.

##  3 The McQueen Dataset

###  3.1 Dataset Overview

Our dataset is based on a visual dialog dataset called VisDial Das et al.
(2017). The original VisDial dataset consists of over 133k dialogs, each
associated with an image and 10 rounds of question-answer pairs. All question-
answer pairs are conducted in a conversational format and revolve around the
content of the picture.

Our dataset randomly selects 15k conversations from the VisDial dataset with
the total of over 80k rewrite utterances. For each query in a visual
conversation, we conduct manual annotation to resolve the information
omission. The query is reconstructed based on the image as well as the history
context so that the coreference and ellipsis are referred-back or completed.
For negative queries that do not contain any information omission, the rewrite
stays the same as the original query. In addition, for all the entities
appearing in the coreference and ellipsis, we annotate the image boxes for
representing their corresponding image areas.

###  3.2 Dataset Construction

####  3.2.1 Text Rewrite Annotation

For manual annotation, we hire 16 annotators in total. Before the annotation
starts, we provide 100 examples for all the annotators to refer to. We also
provide a guideline and some tutorials by listing some typical coreference and
ellipsis cases so that the bias and language style shift between individuals
are minimized as possible. After that, the annotators start working on a small
portion of data where query rewrite is performed. After all the results are
returned and the data quality is checked, the main annotation phase begins and
the rest of data is labeled. On average, each annotator is in charge with the
rewrite of 5059 queries. The rewrite annotation interface can be seen in
Appendix A.

####  3.2.2 Image Box Annotation

Besides the rewrite annotation, we also provide image annotation to assist
downstream or related tasks (e.g. coreference entity detection). The image box
annotation begins right after the rewrite annotation. The overall procedure
also follows the (1) tutorial (2) trial phase (3) main phase pipeline.
Specifically, the annotators have to extract the entities in the ellipsis and
coreference part and draw the bounding boxes of them in the image. Each
annotator is in charge of the image annotation of the rewrites written by
him/herself. The image annotation interface can be seen in Appendix B.

####  3.2.3 Quality Control

After the all the annotation is finished, we re-group and shuffle the
annotators to perform cross quality inspection. Each group is asked to check
the annotation results of other groups. In addition, two new annotators who do
not take part in the annotation phase are recruited to check the quality of
all the annotation results. The annotators have to answer three questions for
each query : (1) Is the rewrite result correct or not? (2) Are all the
coreference and ellipsis resolved in the rewrite? (3) Are the entities in the
coreference and ellipsis correctly annotated in the image? All the
conversation rewrites must get the all “yes” result from all the annotators
before official acceptance, otherwise they are collected to be revised and re-
checked (the questionnaire interface is shown in Appendix C). The whole check-
revise process lasts for three iterations. Considering chance agreement, we
measured the Inter-Annotator Agreement (IAA) in terms of Cohen’s $\kappa$
Cohen (1960). The final $\kappa$ score is 0.82, reaching the “almost perfect”
level222According to Landis and Koch (1977), if $\kappa>=0.81$. Besides, after
each quality check iteration, we randomly sample 100 conversations from the
dataset and manually evaluate the utterance-level precision and recall rate,
where precision denotes the rate of the retrieved rewrites being correct,
while the recall rate records the portion that the coreference and ellipsis
being handled. The precision and recall rate in the 1st/2nd/3rd iteration are
(89.0%, 87.1%)/(95.5%, 94.2%)/(98.3%, 98.2%), respectively.

####  3.2.4 Annotation Cost and Duration

The overall phase including the annotation and quality check spanned for 10
weeks (from March to May 2022), where the annotation guidance lasts for 2
weeks, data annotation lasts for 5 weeks, quality check lasts for 3 weeks. All
the annotators are English native speakers recruited from a professional data
management company Appen333https://appen.com/. The annotation costs $5942 US
dollars in total, with $0.31 per utterance rewrite, $0.03 per image box
annotation.

###  3.3 Dataset Statistics

| Task | Conv. Size | Utterance Size. | Modality | Coref. | Ellip. | Image Box
---|---|---|---|---|---|---|---
CANARD Elgohary et al. (2019) | Query Rewrite | 5644 | 40527 | t | ✓ | ✓ | ✗
REWRITE Su et al. (2019) | Query Rewrite | 2000 | 40000 | t | ✓ | ✓ | ✗
RESTORE Pan et al. (2019) | Query Rewrite | 203965 | 203965 | t | ✓ | ✓ | ✗
VisDial Das et al. (2017) | Visual Dialog | 133351 | 1333510 | t&v | ✗ | ✗ | ✗
VisPro Yu et al. (2019) | VCR | 5000 | 29722 | t&v | ✓ | ✓ | ✗
McQueen | McQR | 15000 | 80944 | t&v | ✓ | ✓ | ✓
Table 1: Comparison with existing datasets, where VCR denotes visual pronoun coreference resolution. Characteristic | % Ratio
---|---
Queries w/ Coreference | 57.2
Queries w/ Ellipsis | 30.4
Queries w/o both | 13.5
Table 2: Proportion of queries with coreference and ellipsis in our dataset. Avg. Num. of Turn per Conv.: |  5.40
---|---
Avg. Num. of Entity per Conv.: |  3.04
Avg. Num. of Image Box per Conv.: |  2.02
Avg. Length of Rewrites: |  6.65
Avg. Length of Contexts: |  42.13
Table 3: Statistics of the dataset. The length is calculated by the number of English words. 0-2 | 3-4 | 5-6 | 7-8 | 9+ | o/a
---|---|---|---|---|---
15143 | 17064 | 16431 | 16126 | 16180 | 80944
Table 4: Number of rewrites concerning different history turn lengths in
McQueen.

According to Table 2, 86.5% of our dataset covers positive rewrite cases that
coreference or ellipsis occurs in the query. Table 3 lists the statistics of
our dataset, where each visual conversation contains 5.40 Q-A turns with 2.02
image boxes on average. Table 4 lists the number of rewrites in our dataset
under different history context lengths, where most of the data contains
context from 3-4 turns, and over 16k data contains context over 9 turns.

Futhermore, we compare our dataset with existing datasets from related works.
According to Table 1, our dataset is: (1) _more complete_ \- we provide manual
annotation on both image and text levels, where the rewrite query and entity
boxes are both provided; (2) _more diverse_ \- since our dataset is designed
not only for all the coreference cases, but also performs ellipsis completion
in the rewrite; (3) _much larger_ \- compared with existing VCR dataset, the
dataset has a larger scale.

Figure 2: The overall architecture of our model.

##  4 McQR Task

###  4.1 Task Definition

We define the task of multimodal conversational query rewrite (McQR).
Concerning a multimodal visual conversation with an image $I$ and the
corresponding text conversation $D$, at time step $m$, given the conversation
history $H$ with $m-1$ turns, the $i$-th turn consists of a query $q_{i}$ and
an answer $a_{i}$. The goal of the task is to generate a rewrite query $r_{m}$
for the current query $q_{m}$ based on both image $I$ and textual history $H$,
which can be represented as

$r_{m}=Rewriter(H,I,q_{m})$ (1)

###  4.2 Methods

####  4.2.1 Model Overview

Figure 2 depicts the overall structure of our proposed model. Our model is
based on a multimodal pre-trained model VL-T5 Cho et al. (2021), where a
Transformer-based encoder and decoder are jointly trained to perform
generation. Besides, we add a pointer generator to the multimodal Transformer
decoder so that the rewrite is either generated from scratch or copied from
history context.

####  4.2.2 Image and Text Embeddings

Text Embedding The text input of our model includes two parts: the task prefix
and the history context. The task prefix is a short prompt which aims to
differentiate the concerned McQR task from other tasks in the pre-training
phase (e.g. visual grounding). Specifically, we use “query rewrite:” as the
task prefix. Following it, the history context contains all the utterances
including all the queries and answers in previous turns. The input text is
then tokenized and embedded before passed into the encoder. Following the
setting in T5 Raffel et al. (2020), we also add a relative position bias to
each self-attention layer. As a result, the text input is represented as
$e^{t}$.

Image Embedding To extract image features, we first detect several object
regions from the image, denoted as Region of Interest (ROI). Following
previous works Cho et al. (2021); Lu et al. (2019), we also use Faster R-CNN
Ren et al. (2015) pre-trained on the Visual Genome dataset Krishna et al.
(2016) to extract ROI features in our task. For each image $I$, we extract
$n=36$ ROIs from it. The final visual vector can be represented as $e^{v}$.

####  4.2.3 Encoder-Decoder Structure

Encoder. We use a multimodal Transformer encoder-decoder structure to encode
the image text features and generate the target rewrite. The multimodal
encoder is a stack of $L$ Transformers which take the image and text
representations as input

$h_{0}=[e^{t}_{1},..,e^{t}_{m},e^{v}_{1},...,e^{v}_{n}]$ (2)
$h_{i}=FNN(MultiHead(h_{i-1},h_{i-1},h_{i-1}))$ (3)

Decoder. Similarly, the decoder is also a stack of $L$ Transformers. Given the
decoder input $x_{t}$, the decoding step consists three phases, where the
first sub-layer is a self-attention layer which can be represented as

$d_{i}=MultiHead(d_{i-1},d_{i-1},d_{i-1})$ (4)

where $d_{0}=x_{t}$. After that, the second sub-layer calculates the cross
attention between the encoder outputs and the decoder self-attention result

$s_{i}=MultiHead(d_{i},h_{L},h_{L})$ (5)

The third sub-layer is a position-wise fully connected feed-forward neural
network, followed by a softmax layer to output the final probability

$P_{vocab}(y_{t})=\sum_{i:w_{i}\in V}\beta_{t,i}=Softmax(FNN(s_{i}))$ (6)

where $\beta$ is the softmax score over the whole vocabulary $V$.

| BLEU-2 | BLEU-4 | ROUGE-2 | ROUGE-L | METEOR | EM
---|---|---|---|---|---|---
Original | 57.27 | 48.44 | 54.86 | 73.45 | 38.28 | \- | -
AllenNLP Coref | 59.72 | 50.21 | 56.09 | 76.07 | 39.87 | 8.97 | 96.14
L-Gen | 77.14 | 66.31 | 74.44 | 84.68 | 46.09 | 41.84 | 57.77
T(E)-Gen | 78.03 | 65.40 | 75.53 | 86.80 | 47.32 | 41.37 | 56.58
T(L)-Gen | 79.30 | 67.16 | 76.28 | 88.14 | 49.23 | 42.06 | 58.25
L-Ptr | 77.46 | 69.46 | 76.07 | 86.65 | 48.63 | 47.87 | 66.72
T(E)-Ptr | 79.52 | 68.26 | 77.27 | 88.49 | 50.10 | 49.49 | 68.94
T(L)-Ptr | 80.12 | 68.41 | 78.40 | 89.54 | 50.56 | 48.15 | 69.53
VLBart | 90.01 | 84.28 | 88.67 | 93.80 | 58.87 | 64.28 | 86.89
VLT5 | 90.37 | 84.87 | 89.23 | 94.10 | 59.45 | 65.62 | 89.95
VLBart-Ptr | 90.16 | 84.52 | 88.87 | 93.89 | 59.26 | 64.87 | 87.22
VLT5-Ptr | 90.47 | 84.94 | 89.32 | 94.45 | 59.46 |  65.67 | 90.22
Table 5: The main experiment on our dataset, where T(E) denotes Transformer
with Early Fusion, T(L) denotes Transformer with Late Fusion. For EM rate, we
report both EM for positive and negative rewrite samples.

Multimodal Transformer with Pointer Generator. Additionally, following the
motivation that most part of the rewrite sentence can be related to certain
parts of the input context, we add a pointer generator See et al. (2017) to
the multimodal Transformer such that the rewrite is either generated from
scratch or directly copied from the input. Specifically, the cross attention
in the last decoder layer can be naturally taken as the context vector

$c_{i}=MultiHead(d_{i},h^{U}_{L},h^{U}_{L})$ (7)

where $h^{U}_{L}$ is the textual part of the encoding result, which is the
embedding of tokens before the “[SEP]” token.

$\alpha_{t,i}=softmax(\frac{{(W_{s}s_{t})}^{T}W_{h}h_{i}}{\sqrt{d}})$ (8)
$P_{copy}(y_{t})=\sum_{i:w_{i}\in H}\alpha_{t,i}$ (9)

where $\alpha$ is the copy distribution over the input $H$, $P_{copy}$
determines where to copy at time step $t$.

By incorporating the pointer generator, the final probability of generating
the target word $y_{t}$ at time step $t$ is represented as

$P(y_{t})=\lambda P_{vocab}(y_{t})+(1-\lambda)P_{copy}(y_{t})$ (10)
$\lambda=sigmoid(w_{d}^{T}c_{t}+w_{l}^{T}s_{t}+w_{a}^{T}x_{t})$ (11)

where $w_{d},w_{l},w_{a}$ are the weights to learn.

####  4.2.4 Training

We adopt the standard generation loss when fine-tuning the pre-trained model
parameterized $\theta$ on our McQR task. At each time step $t$, the decoder
output token is determined based on the generated rewrites of previous time
steps denoted as $y_{<t}$, the input image and text encoding vector $e^{v}$
and $e^{t}$. We minimize the negative log-likelihood of generating the target
rewrite $y$ given the image text input and previous generation results as

$min-
logP_{\theta}(y|e^{t},e^{v})=-\sum_{j=1}^{|y|}logP_{\theta}(y_{t}|e^{t},e^{v},y_{<t})$
(12)

##  5 Experiments

###  5.1 Compared Methods

We compare our methods with several baselines.

  * •

Original Elgohary et al. (2019) is the method where the rewrite is set to be
the same as the input query.

  * •

AllenNLP Coref Gardner et al. (2018) is a deep learning based NLP tool. We
utilize its coreference resolution model to generate the rewrite.

  * •

(L/T)-Gen Su et al. (2019) denotes the LSTM/Transformer based encoder-decoder
generation model. For Transformer-based models, we report the performance of
two variants: Early Fusion which utilizes the same encoder to encode image and
text features, and Late Fusion which first embeds image and text into vector
spaces separately and then performs fusion into a joint embedding.

  * •

(L/T)-Ptr See et al. (2017) adds a pointer generator to the (L/T)-Gen model.

  * •

VL-(Bart/T5) Cho et al. (2021) is the mulitimodal implementation of large pre-
trained language model Bart/T5.

  * •

VL-(Bart/T5)-Ptr is the model depicted in Section 4.2 that adds a pointer
generator to the pre-trained model.

###  5.2 Experimental Settings

Our code is implemented based on Pytorch and Huggingface Transformers Wolf et
al. (2019). We use the base version of the pre-trained VL-Bart/T5 in all our
experiments. Our dataset is split into the training, testing, and validation
dataset following the portion of 60%, 20%, 20%, resulting in 48566 queries for
the training set, 16189 queries for the testing and validation set. By
default, we set the batch size as 32 and the learning rate to be 5e-5, the
model is fine-tuned for 20 epochs with the random seed of 42. In the testing
stage, all models decode words by beam search with beam size set to 5.

We employ several evaluation metrics to evaluate the quality of the generated
rewrite. We first report the BLEU Papineni et al. (2002), ROUGE Lin (2004),
and METEOR Denkowski and Lavie (2014) rate. In addition, we report the Exact
Match (EM) of both positive samples that involves some changes in the rewrite
and negative samples that the rewrite is the same as the query. On two
subtasks, we report the precision, recall, and F1 score.

###  5.3 Experiment Results

We first report the overall performance on the query rewrite task. Then we
perform experiments on two subtasks including coreference resolution and
ellipsis completion, respectively.

Table 5 demonstrates the overall performance of different models on the McQR
task. We have the following observations: first of all, compared with LSTM
based models (e.g. L-Gen), Transformer based models have a stronger generation
ability (e.g. T-(E) Gen), where the BLEU-2 score increases from 77.14 to
78.03. In addition, with the help of the pointer generator, certain parts from
the original query and the history context are able to be preserved in the
rewrite, where the negative EM score increases from 86.89 to 87.22 in the
VLBart model. Furthermore, by leveraging the pre-trained model, a significant
performance improvement can be seen where the BLEU-2 increases from 80.12 in
T(L)-Ptr to 90.47 in VLT5-Ptr.

| Precision | Recall | F1
---|---|---|---
AllenNLP Coref | 15.76 | 14.48 | 15.10
L-Gen | 28.63 | 28.18 | 28.40
T-Gen | 42.12 | 41.45 | 41.78
L-Ptr | 38.07 | 37.47 | 37.77
T-Ptr | 43.88 | 43.19 | 43.53
MBERT | 72.42 | 65.03 | 68.53
VLT5 | 77.00 | 70.84 | 73.79
VLBart | 76.59 | 70.37 | 73.35
VLBart-Ptr | 77.28 | 71.00 | 74.00
VLT5-Ptr | 77.33 | 71.05 | 74.05
Table 6: Precision, recall, F1 score of visual coreference resolution. For Transformer based models, we record the late fusion version. All three metrics are evaluated on utterance level. | Precision | Recall | F1
---|---|---|---
L-Gen | 17.95 | 17.29 | 17.61
T-Gen | 29.02 | 30.12 | 29.56
L-Ptr | 24.49 | 23.59 | 24.03
T-Ptr | 32.60 | 31.41 | 32.00
VLBart | 51.93 | 50.04 | 50.97
VLT5 | 54.33 | 52.35 | 53.32
VLBart-Ptr | 52.45 | 50.54 | 51.47
VLT5-Ptr | 54.59 | 52.60 | 53.58
Table 7: Precision, recall, F1 score of visual ellipsis completion. For
Transformer based models, we also report the late fusion version.

Table 6 shows the results of different models on the visual coreference
resolution (VCR) subtask. We further utilize one state-of-the-art VCR method
named MBERT to compare Yu et al. (2022). According to the table, traditional
text-only coreference resolution methods such as AllenNLP Coref may not have a
good performance in the VCR task. The reason is that, in the conversations,
many pronouns refer to entities that never appear in the history context, but
can be found clues in the image. Furthermore, it can be concluded that pointer
network also has a positive influence on the results since many coreferred
entities can be directly copied from previous turns.

Besides VCR, we also perform tests on the visual ellipsis completion task, as
shown in Table 7. The overall condition is similar to results in Table 6,
while there encounters a performance degradation in this task. This may result
from the fact that recovering the omitted information may not be that apparent
(we will use some examples to illustrate in Section 6.3). In conclusion, our
model shows superior performance on both two tasks, demonstrating the
effectiveness of our model in resolving the information omission of the
conversations.

##  6 Extensive Analysis

###  6.1 Image Role Analysis

Figure 3: BLEU-2 performance under different length of turns, where (M)
denotes the multimodal version, (S) denotes the text-only version, o/a denotes
the overall performance over all turns. Figure 4: Example rewrites generated
by different methods, where the red part denotes the coreference part and the
blue part denotes the ellipsis part. The underline denotes the errors in the
rewrites. Figure 5: The heat map visualization of the self-attention weight in
the Transformer block of our model. The full visual conversation example is
shown in Appendix D.

In order to further investigate the role of image information in the query
rewrite task, we remove the image features and compare the performance with
the original model under different length of context respectively.
Specifically, we divide the overall 16189 testing data into five categories by
the history context length, ending up with 3136/3380/3180/3185/3308 data
records with the context turn length from 0-1/2-3/4-5/6-7/8+, as shown in
Figure 3. According to the figure, the performance gets improved with the help
of image information. Compared with Transformer generator, our model is less
sensitive to the turn length, where the model still has a decent performance
when the conversation goes deep. We can also observe that, in our model, when
there is no or short textual context that the information in conversation
history is limited, the gap between monomodal and multimodal performance
reaches to the largest, showing that the model is more dependant to the image
information in this case. While when the conversation is deep, the gap
decreases, showing that the model learns to copy information from the rich
history context when rewriting the query.

###  6.2 Multimodal Attention Visualization

We utilize the self-attention weight heat map in the Transformer block of our
model to visualize how the model learns the cross-modal relationship of the
conversation. In the example shown in Figure 5 (the full conversation
information can be found in Appendix D), the first three image segments
correspond to ROI “man”, “boy”, “shorts”, respectively. According to the map,
the pronoun “they” is correctly related to the “man” and “boy” ROI segments
and also has a high attention weight to the text “the man” in the history
context444The pronoun “they” in the query refers to “the man and the boy” in
the original conversation.. The learned relationship between visual and text
representations can serve as the reason that our model shows superior
performance concerning the multimodal feature incorporation in the McQR task.

###  6.3 Case Study

We provide several example rewrites generated by different methods to vividly
demonstrate the quality of rewrites, according to Figure 4. In the first case
where the query is the first utterance where no textual context is provided,
non pre-trained models (e.g. T(L)-Ptr) have difficulty resolving the pronoun
“he” in the query. The results imply that with the help of prior knowledge,
multimodal pre-trained models have a superior ability in incorporating image
and text features, mitigating the gap between representations of multimodal
heterogeneous space. The second case shows that traditional Transformer
pointer network tends to copy incorrect context segments whose rewrite results
may not make sense to human readers. For example, the abbreviated entity after
“except for” should apparently be “the bear” instead of “the people”, while
our model has a better ability of understanding the whole context and
outputing more accurate results. Furthermore, when it comes to complicated
cases where coreference and ellipsis are both observed, our model is both
capable of copying the entities from history to solve the coreference (e.g.
the red part in the third case) and generate parts that require reasoning
(e.g. the blue part in the third case) from scratch.

Figure 6: Common error cases of our method.

##  7 Error Case Analysis

As shown in Figure 6, we demonstrate the most common error cases of our model,
which can be classified into several cases including bad sentence structure,
wrong coreference result, inaccurate omission completion, etc. According to
the figure, we can see that pre-trained language models can generate sentences
that have a proper format, but still have some problems in understanding the
deep semantic correlation in the visual conversations. For example, in the top
two cases, although the coreference seems simple for human readers, it poses
challenges for machines other than directly making a copy from context.
Specifically, for complicated cases such as when coreference and ellipsis
appear at the same time, when the conversation is long, and when the omitted
information requires reasoning between history entities (e.g. the bottom
cases), there still remains much space to explore.

##  8 Conclusion and Future Work

We propose the task of multimodal conversational query rewrite (McQR), which
aims to perform query rewrite under a multi-turn visual conversation. To
facilitate the research, we benchmark a large-scale dataset with manual
annotation which covers 15k visual conversations with more than 80k rewrites.
We also provide image box annotation of entities appearing in the rewrites.
Accordingly, we propose a model based on an existing multimodal pre-trained
model and further enhance it with a pointer generator. Extensive experiments
are performed to show the effectiveness of our model.

##  9 Limitations

Although our model achieves over 90% BLEU-2 rate on our dataset, there is
still room for improvements in the future work, since the exact match for
positive rewrite queries can be further lifted. In addition, in the future
work, we will also continue to explore how the dataset and model can further
benefit downstream research under this scenario. Furthermore, fine-grained
image features such as the image box annotation can be leveraged for improving
the performance.

##  10 Ethics Statement

All data records of our dataset are originally from the Visual Dialog Das et
al. (2017) dataset, where all the images are collected from the COCO Lin et
al. (2014) dataset. When annotating the data, we make sure that the annotators
do not have any other rights except for the conversation information. Upon
data publication, we will strictly follow the user terms of the Visual Dialog
dataset.

## References

  * Anantha et al. (2021) R. Anantha, Svitlana Vakulenko, Zhucheng Tu, S. Longpre, Stephen G. Pulman, and Srinivas Chappidi. 2021.  Open-domain question answering goes conversational via question rewriting.  In _NAACL_.
  * Cho et al. (2021) Jaemin Cho, Jie Lei, Hao Tan, and Mohit Bansal. 2021.  Unifying vision-and-language tasks via text generation.  In _ICML_.
  * Choi et al. (2018) Eunsol Choi, He He, Mohit Iyyer, Mark Yatskar, Wen tau Yih, Yejin Choi, Percy Liang, and Luke Zettlemoyer. 2018.  Quac: Question answering in context.  In _EMNLP_.
  * Cohen (1960) Jacob Cohen. 1960.  A coefficient of agreement for nominal scales.  _Educational and Psychological Measurement_ , 20:37 – 46.
  * Das et al. (2017) Abhishek Das, Satwik Kottur, Khushi Gupta, Avi Singh, Deshraj Yadav, José M. F. Moura, Devi Parikh, and Dhruv Batra. 2017.  Visual dialog.  _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 1080–1089.
  * Denkowski and Lavie (2014) Michael J. Denkowski and Alon Lavie. 2014.  Meteor universal: Language specific translation evaluation for any target language.  In _WMT@ACL_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _ArXiv_ , abs/1810.04805.
  * Elgohary et al. (2019) Ahmed Elgohary, Denis Peskov, and Jordan L. Boyd-Graber. 2019.  Can you unpack that? learning to rewrite questions-in-context.  In _EMNLP_.
  * Gardner et al. (2018) Matt Gardner, Joel Grus, Mark Neumann, Oyvind Tafjord, Pradeep Dasigi, Nelson F. Liu, Matthew E. Peters, Michael Schmitz, and Luke Zettlemoyer. 2018\.  Allennlp: A deep semantic natural language processing platform.  _ArXiv_ , abs/1803.07640.
  * Hao et al. (2021) Jie Hao, Linfeng Song, Liwei Wang, Kun Xu, Zhaopeng Tu, and Dong Yu. 2021.  Rast: Domain-robust dialogue rewriting as sequence tagging.  In _EMNLP_.
  * Kong et al. (2014) Chen Kong, Dahua Lin, Mohit Bansal, Raquel Urtasun, and Sanja Fidler. 2014.  What are you talking about? text-to-image coreference.  _2014 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 3558–3565.
  * Kottur et al. (2018) Satwik Kottur, José M. F. Moura, Devi Parikh, Dhruv Batra, and Marcus Rohrbach. 2018.  Visual coreference resolution in visual dialog using neural module networks.  In _ECCV_.
  * Krishna et al. (2016) Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A. Shamma, Michael S. Bernstein, and Li Fei-Fei. 2016.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  _International Journal of Computer Vision_ , 123:32–73.
  * Landis and Koch (1977) J Richard Landis and Gary G. Koch. 1977.  The measurement of observer agreement for categorical data.  _Biometrics_ , 33 1:159–74.
  * Li et al. (2021) Mingxiao Li, K. U. Leuven, and Marie-Francine Moens. 2021.  Modeling coreference relations in visual dialog.  In _EACL_.
  * Lin (2004) Chin-Yew Lin. 2004.  Rouge: A package for automatic evaluation of summaries.  In _ACL 2004_.
  * Lin et al. (2014) Tsung-Yi Lin, Michael Maire, Serge J. Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. 2014.  Microsoft coco: Common objects in context.  In _ECCV_.
  * Lu et al. (2019) Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee. 2019.  Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks.  In _NeurIPS_.
  * Pan et al. (2019) Zhufeng Pan, Yan Wang, Kun Bai, Lianqiang Zhou, and Xiaojiang Liu. 2019.  Improving open-domain dialogue systems via multi-turn incomplete utterance restoration.  In _EMNLP_.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _ACL_.
  * Quan et al. (2019) Jun Quan, Deyi Xiong, Bonnie Lynn Webber, and Changjian Hu. 2019.  Gecor: An end-to-end generative ellipsis and co-reference resolution model for task-oriented dialogue.  _ArXiv_ , abs/1909.12086.
  * Raffel et al. (2020) Colin Raffel, Noam M. Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _ArXiv_ , abs/1910.10683.
  * Rastogi et al. (2019) Pushpendre Rastogi, Arpit Gupta, Tongfei Chen, and Lambert Mathias. 2019.  Scaling multi-domain dialogue state tracking via query reformulation.  In _NAACL_.
  * Reddy et al. (2019) Siva Reddy, Danqi Chen, and Christopher D. Manning. 2019.  Coqa: A conversational question answering challenge.  _Transactions of the Association for Computational Linguistics_ , 7:249–266.
  * Ren et al. (2015) Shaoqing Ren, Kaiming He, Ross B. Girshick, and Jian Sun. 2015.  Faster r-cnn: Towards real-time object detection with region proposal networks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 39:1137–1149.
  * See et al. (2017) A. See, Peter J. Liu, and Christopher D. Manning. 2017.  Get to the point: Summarization with pointer-generator networks.  In _ACL_.
  * Song et al. (2020) Shuangyong Song, Chao Wang, Qianqian Xie, Xinxing Zu, Huan Chen, and Haiqing Chen. 2020.  A two-stage conversational query rewriting model with multi-task learning.  _Companion Proceedings of the Web Conference 2020_.
  * Su et al. (2019) Hui Su, Xiaoyu Shen, Rongzhi Zhang, Fei Sun, Pengwei Hu, Cheng Niu, and Jie Zhou. 2019.  Improving multi-turn dialogue modelling with utterance rewriter.  In _ACL_.
  * Vakulenko et al. (2021) Svitlana Vakulenko, S. Longpre, Zhucheng Tu, and R. Anantha. 2021.  Question rewriting for conversational question answering.  _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _ArXiv_ , abs/1706.03762.
  * Voskarides et al. (2020) Nikos Voskarides, Dan Li, Pengjie Ren, E. Kanoulas, and M. de Rijke. 2020.  Query resolution for conversational search with limited supervision.  _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _ArXiv_ , abs/1910.03771.
  * Xu et al. (2020) Kun Xu, Haochen Tan, Linfeng Song, Han Wu, Haisong Zhang, Linqi Song, and Dong Yu. 2020.  Semantic role labeling guided multi-turn dialogue rewriter.  In _EMNLP_.
  * Yu et al. (2020) Shih Yuan Yu, Jiahua Liu, Jingqing Yang, Chenyan Xiong, Paul N. Bennett, Jianfeng Gao, and Zhiyuan Liu. 2020.  Few-shot generative conversational query rewriting.  _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_.
  * Yu et al. (2021) Shih Yuan Yu, Zhenghao Liu, Chenyan Xiong, Tao Feng, and Zhiyuan Liu. 2021.  Few-shot conversational dense retrieval.  _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_.
  * Yu et al. (2022) Xintong Yu, Hongming Zhang, Ruixin Hong, Yangqiu Song, and Changshui Zhang. 2022\.  Vd-pcr: Improving visual dialog with pronoun coreference resolution.  _Pattern Recognit._ , 125:108540.
  * Yu et al. (2019) Xintong Yu, Hongming Zhang, Yangqiu Song, Yan Song, and Changshui Zhang. 2019.  What you see is what you get: Visual pronoun coreference resolution in dialogues.  In _EMNLP_.
  * Zhang et al. (2020) Xiyuan Zhang, Chengxi Li, Dian Yu, Sam Davidson, and Zhou Yu. 2020.  Filling conversation ellipsis for better social dialog understanding.  In _AAAI_.

##  Appendix A Rewrite Annotation Interface

Figure 7 shows the annotation interface when preparing the rewrite. We assign
one text box for each query in the visual conversation so that the annotators
can rewrite the query according to the image and history context.

Figure 7: Rewrite annotation interface of our dataset.

##  Appendix B Image Box Annotation

Figure 8 shows the image box annotation interface, where the annotators
extract entities from the rewrites and mark them on the image in the format of
box.

Figure 8: Image box annotation interface of our dataset.

##  Appendix C Quality Control Questionnaire

We design the quality control questionnaire as shown in Figure 9. All quality
checkers have to click and answer the three questions.

Figure 9: The questionnaire interface in the quality control phase.

##  Appendix D Dataset Examples

We list some examples of our dataset to vividly demonstrate the characteristic
of the task. All the examples are listed in Figure 10.

Figure 10: Example cases of our dataset.