# Probability Mass Functions for which Sources have the Maximum Minimum
Expected Length

Shivkumar K. Manickam  Dept. of Electrical Communication Engineering
Indian Institute of Science, Bangalore, India
Email<EMAIL_ADDRESS>
###### Abstract

Let $\mathcal{P}_{n}$ be the set of all probability mass functions (PMFs)
$(p_{1},p_{2},\ldots,p_{n})$ that satisfy $p_{i}>0$ for $1\leq i\leq n$.
Define the minimum expected length function
$\mathcal{L}_{D}:\mathcal{P}_{n}\rightarrow\mathbb{R}$ such that
$\mathcal{L}_{D}(P)$ is the minimum expected length of a prefix code, formed
out of an alphabet of size $D$, for the discrete memoryless source having $P$
as its source distribution. It is well-known that the function
$\mathcal{L}_{D}$ attains its maximum value at the uniform distribution.
Further, when $n$ is of the form $D^{m}$, with $m$ being a positive integer,
PMFs other than the uniform distribution at which $\mathcal{L}_{D}$ attains
its maximum value are known. However, a complete characterization of all such
PMFs at which the minimum expected length function attains its maximum value
has not been done so far. This is done in this paper.

##  I Introduction to the Problem

One of the earliest problems considered in information theory is that of
finding a prefix code with the minimum expected length for a given discrete
memoryless source. This paper addresses a question related to this problem.

Let us begin by establishing the basic terminology and notation used in this
paper. A set of finite length strings of letters coming from a given finite
alphabet is said to be a _prefix code_ if no string is a prefix of another.
Let us use $\mathcal{A}$ to denote the finite alphabet and $D$ to denote its
size. The members of a prefix code are called _codewords_.

Consider a discrete source with $n$ symbols where the $i$th symbol occurs with
a probability $p_{i}$ ($\sum_{i}p_{i}=1$). The collection of probabilities
$P=(p_{1},p_{2},\ldots,p_{n})$ is a _probability mass function_ (PMF). Let $X$
be a prefix code assigned to this source (from now onwards, we will simply say
$X$ is a prefix code for the PMF $P$, leaving out any mention of the source)
and let the $i$th source symbol be associated with a codeword of length
$l_{i}$. The _expected length_ of the prefix code $X$ is $\sum_{i}p_{i}l_{i}$.
A minimum expected length prefix code can be effectively obtained using the
Huffman algorithm [1]. Henceforth, we will refer to a minimum expected length
prefix code as an _optimal code_.

Let $\mathcal{P}_{n}$ be the set of all PMFs $(p_{1},p_{2},\ldots,p_{n})$ that
satisfy $p_{i}>0$ for $1\leq i\leq n$. Define the function
$\mathcal{L}_{D}:\mathcal{P}_{n}\rightarrow\mathbb{R}$ such that
$\mathcal{L}_{D}(P)$ is the expected length of an optimal code for the PMF
$P$. Let us call this function the _minimum expected length function_.

Now, for a PMF $P\in\mathcal{P}_{n}$, the only known general way to determine
$\mathcal{L}_{D}(P)$ is by first determining an optimal code using the Huffman
algorithm and then finding its expected length. There is neither any known
analytical formula for $\mathcal{L}_{D}(P)$ in terms of the probabilities of
$P$ nor an alternate characterization of the function $\mathcal{L}_{D}$, from
which its values can be readily evaluated. However, some properties of this
function are known. Let us call a PMF at which $\mathcal{L}_{D}$ attains its
maximum value to be a _point of maximum_. A result of Hwang [2] shows that the
minimum expected length function is Schur-concave, and so attains its maximum
value at the uniform distribution: $U_{n}=(1/n,1/n,\ldots,1/n)$. Further, when
$n$ is of the form $D^{m}$, a result of [3] gives other points of maximum: all
$P\in\mathcal{P}_{n}$ in which the sum of the lowest $D$ probabilities is
greater than or equal to the highest probability (we will see more about
this). However, to the author’s knowledge, a complete characterization of all
the points of maximum has not been done so far. This is carried out in this
paper.

We will be making use of a characterization of Huffman trees given by Gallager
[4]. This is presented in the next section.

##  II Huffman Trees

It is useful to visualize prefix codes in the form of trees [5, Chapter 5]
(see Fig. 1). For our purpose, we will find it convenient to give directions
to the edges of a tree. When we will refer to a directed graph as a tree, we
will do so in the sense that the undirected graph obtained by replacing each
directed edge by an undirected one is a tree. Consider an infinite rooted
directed tree in which all the edges are directed away from the root. Let each
node of the tree have $D$ outgoing edges. Let us denote this tree as
$T_{\infty}$. Throughout this paper, whenever we talk of a tree we will mean a
subtree of $T_{\infty}$. In a tree, if there is an edge from a node $v$ to
node $v_{1}$, then $v$ is said to be the _parent_ of $v_{1}$ and $v_{1}$ is
said to be a _child_ of $v$. A node $d$ is said to be a _descendant_ of a node
$v$ if there is a path from $v$ to $d$. Nodes having the same parent are
called _siblings_. A _sibling set_ is the set of the children of an internal
node of a tree. The _level_ of a node $v$ is the length of the path from the
root to $v$.

$0$$1$$0$$1$$1$$0$$1$$0$$1$$0$$00$$01$$100$$101$$110$$111$

Figure 1: Code tree for the prefix-free code $\\{00,01,100,101,110,111\\}$.

For every node of $T_{\infty}$, label each of the outgoing edges with a letter
from $\mathcal{A}$ such that no two edges is associated with the same letter.
Associate each node with the string formed by reading out the labels in the
path from the root to that particular node. To get the tree representation of
a prefix code, mark all the nodes of the labeled tree $T_{\infty}$ that
correspond to the codewords. Retain all the nodes in the paths from the root
to the marked nodes (including the root and the marked nodes) and delete the
remaining nodes. The resulting tree is called a _code tree_. Conversely, any
tree $T$ can be considered to represent a class of prefix codes. To get this
class, consider all the possible ways the edges of the tree $T$ can be labeled
using the letters of $\mathcal{A}$ (with no two outgoing edges from a node
getting the same label). From each assignment of labels on the edges, we can
get a prefix code by collecting all the strings along the leaves of $T$. Let
us consider $T$ to represent the class of all such prefix codes obtained from
all the different assignments of labels.

Let $T$ be a tree with $n$ leaves and let $P\in\mathcal{P}_{n}$. If there is a
1-1 mapping between the probabilities of $P$ and the leaves of $T$, we say
that $T$ is a tree associated with the PMF $P$. Using our relation between a
tree and a class of prefix codes, we can see that a tree $T$ associated with a
PMF $P$ defines a class of prefix codes for $P$. Observe that the expected
length of all these prefix codes is the same, and we take this value as the
_expected length_ of the tree $T$. An _optimal tree_ is that having the
minimum expected length. The Huffman algorithm can be viewed as a one that
constructs an optimal tree. It is briefly described below as we will refer to
it to establish the Huffman tree characterization.

###  II-A The Huffman Algorithm

Let $P=(p_{1},p_{2},\ldots,p_{n})$ be the given PMF for which we need an
optimal code. Consider a forest $F_{1}$ containing $n$ isolated vertices. View
each of the vertices as a tree and associate the probability $p_{i}$ with the
$i$th vertex. Identify the integer $m$ such that $2\leq m\leq D$ and $D-1$
divides $n-m$. Choose any $m$ vertices $v_{1},v_{2},\ldots,v_{m}$ from $F_{1}$
having the lowest $m$ probabilities. Add a new vertex $r$ to $F_{1}$ and make
it the parent of the vertices $v_{1},v_{2},\ldots,v_{m}$. Associate with the
vertex $r$ the probability equaling the sum of the probabilities of its
children. Finally, make the vertex $r$ the root of the tree to which it
belongs.

Now suppose that the forests $F_{1},F_{2},\ldots,F_{i}$ are defined, with
$F_{i}$ not being a tree. Define the forest $F_{i+1}$ as follows: choose any
$D$ roots of the trees in $F_{i}$ with lowest $D$ probabilities. As in the
previous case assign a parent to them, making the parent the root of the tree
to which it belongs and assigning it the probability equaling the sum of the
probabilities of its children. This is the forest $F_{i+1}$. From the way the
first step of the algorithm was carried out, we will end with a forest that is
in fact a tree associated with $P$; let us call it a _Huffman tree_ for the
PMF $P$.

###  II-B Huffman Tree Characterization

Let $T$ be a tree for a PMF $P$. As done during the Huffman algorithm, let us
associate each node of $T$ with a probability in the following way: a node
gets the probability equal to the sum of the probabilities of its children.
This assignment will result in the root node getting the probability 1. It can
be shown that the expected length of $T$ is the sum of the probabilities of
all its internal nodes (including the root node).

Gallager [4] has given a necessary and sufficient condition for a tree
associated with a PMF to be a _Huffman tree_ , i.e. a tree which can be
generated by the application of Huffman algorithm on $P$. For our purpose, we
will need a more descriptive version of this condition which is stated in the
following theorem. A part of its proof follows the arguments presented in [4].

######  Theorem 1.

Let $T$ be a tree associated with a PMF $P\in\mathcal{P}_{n}$. It is a Huffman
tree for $P$ iff the following conditions hold:
(P1) The probability of a lower level node is greater than or equal to that of
a higher level node.
(P2) Let $m$ be such that $D-1$ divides $n-m$ with $2\leq m\leq D$. The tree
$T$ contains a sibling set with $m$ nodes at its maximum level which has the
lowest $m$ probabilities of $P$. All the other sibling sets of $T$ have
exactly $D$ nodes.
(P3) The nodes at any level of $T$ can be listed in such a way that their
probabilities are in a non-decreasing order, and the siblings come next to
each other in the listing.

###### Proof.

Let us first take $T$ to be a Huffman tree for $P$. Now suppose that the
condition (P1) is not satisfied for two nodes $v_{1}$ and $v_{2}$ at levels
$l_{1}$ and $l_{2}$ respectively, with $l_{1}<l_{2}$. Let $v_{1}$ have the
probability $p_{1}$ and $v_{2}$ have the probability $p_{2}$. Let $ST(v_{1})$
($ST(v_{2})$) be the subtree of $T$ that has $v_{1}$ ($v_{2}$) as its root and
contains all the descendants of $v_{1}$ ($v_{2}$). Let
$l_{11},l_{12},\ldots,l_{1i}$ be the levels of the leaves of $ST(v_{1})$, with
levels calculated from the node $v_{1}$, and $p_{11},p_{12},\ldots,p_{1i}$ be
their respective probabilities (with $\sum_{k}p_{1k}=p_{1}$). Similarly, let
$l_{21},l_{22},\ldots,l_{2j}$ be the levels of the leaves of $ST(v_{2})$, with
levels calculated from the node $v_{2}$, and $p_{21},p_{22},\ldots,p_{2j}$ be
their respective probabilities (with $\sum_{k}p_{2k}=p_{2}$). Since
$p_{2}>p_{1}$, $v_{2}$ cannot be a descendant of $v_{1}$. Create a new tree
associated with $P$ as follows without changing the association between the
probabilities of $P$ and the leaves of $T$: Let $u_{1}$ and $u_{2}$ be the
parents of $v_{1}$ and $v_{2}$ respectively. Delete the edges between $u_{1}$
and $v_{1}$, and $u_{2}$ and $v_{2}$. Construct new edges from $u_{1}$ to
$v_{2}$, and $u_{2}$ to $v_{1}$. In other words, we are interchanging the
parents of $v_{1}$ and $v_{2}$. It is clear that the resulting graph is a
tree. Let us call this tree $T^{\prime}$. Let $L(T)$ and $L(T^{\prime})$
denote the expected lengths of $T$ and $T^{\prime}$ respectively. Now, there
exists a $\lambda\in\mathbb{R}$ such that

$\displaystyle L(T)$
$\displaystyle=\lambda+\sum_{k=1}^{i}(l_{1}+l_{1k})p_{1k}+\sum_{k=1}^{j}(l_{2}+l_{2k})p_{2k}$
$\displaystyle=\lambda+l_{1}p_{1}+l_{2}p_{2}+\sum_{k=1}^{i}l_{1k}p_{1k}+\sum_{k=1}^{j}l_{2k}p_{2k},$
(1)

and

$\displaystyle L(T^{\prime})$
$\displaystyle=\lambda+\sum_{k=1}^{i}(l_{1}+l_{2k})p_{2k}+\sum_{k=1}^{j}(l_{2}+l_{1k})p_{1k}$
$\displaystyle=\lambda+l_{1}p_{2}+l_{2}p_{1}+\sum_{k=1}^{i}l_{1k}p_{1k}+\sum_{k=1}^{j}l_{2k}p_{2k}.$
(2)

Notice that $L(T^{\prime})<L(T)$ which contradicts the optimality of $T$. Thus
the condition (P1) is true.

The condition (P2) follows from the way the Huffman algorithm is carried out
and the condition (P1).

Let us now prove condition (P3). Let $F_{1},F_{2},\ldots,F_{N}$ be the forests
obtained during the execution of the Huffman algorithm on PMF $P$ that yields
the tree $T$ (see Section II-A). Let $S_{i}$ ($1\leq i\leq N$) be the chosen
root nodes in $F_{i}$ having the lowest $D$ probabilities (lowest $m$
probabilities when $i=1$). It can be seen that the $S_{i}$’s are precisely the
sibling sets in $T$. Further, each of the probabilities in $S_{i}$ is less
than or equal to each of that in $S_{i+1}$. Thus, it is possible to list all
the nodes of $T$ in such a way that their probabilities are in a non-
decreasing order, and the siblings come next to each other in the listing. As
a result, (P3) also holds.

Let us prove that these conditions are sufficient for $T$ to be a Huffman tree
for $P$. We will do so by showing that a tree isomorphic to $T$ can be
obtained by the application of the Huffman algorithm on $P$.

Let $V$ and $V_{L}$ denote the nodes and leaf nodes of $T$ respectively. Let
$U$ be a set with $|U|=|V|$. Define a bijection $\psi:V\rightarrow U$. For any
$V^{\prime}\subseteq V$, let the $\psi$-image of $V^{\prime}$ be the set
$\\{\psi(v^{\prime})\mid v^{\prime}\in V^{\prime}\\}$. Construct a forest $F$
exactly containing all the elements of the $\psi$-image of $V_{L}$ as isolated
vertices (with each of them viewed as a tree with that vertex itself serving
as its root). For each node of $V_{L}$, assign its probability to its
$\psi$-image in the forest. Let $S$ be the sibling set in $T$ having the $m$
lowest probabilities of $P$, and let $r$ be its parent. Derive a new forest
$F^{\prime}$ from $F$ by introducing $\psi(r)$ as a new vertex to $F$, and
making it the parent of the vertices occurring in the $\psi$-image of $S$.
Assign the probability of the node $r$ to $\psi(r)$. Derive a new tree
$T^{\prime}$ from $T$ by deleting all the nodes of $S$ from $T$. It can be
seen that the roots of the trees in $F^{\prime}$ are precisely the leaf nodes
of $T^{\prime}$.

If $F^{\prime}$ is not a tree, then perform the above mentioned step for
$T^{\prime}$ and $F^{\prime}$ by taking $S$ to be a sibling set in
$T^{\prime}$ containing the lowest $D$ probabilities of $T^{\prime}$. Such a
choice is possible as $T^{\prime}$ also satisfies conditions (P1) and (P3).
Note that all the nodes of $S$ are leaf nodes of $T^{\prime}$. The execution
of the step will leave us with a tree and a graph both of which are derived in
two steps from $T$ and $F$ respectively. The graph derived from $F$ will be a
forest as the $\psi$-image of $S$ are root nodes in $F^{\prime}$. Keep
repeating the above step and it can be seen that each execution of the step
will yield a tree derived from $T$ and a forest derived from $F$ with the
$\psi$-image of the leaves of the tree being exactly the root nodes of the
trees of the forest. Continue doing so till the forest derived from $F$
becomes a tree, say $T^{*}$. It can be seen that these steps constitute the
Huffman algorithm and so $T^{*}$ is a Huffman tree for $P$. By way of
construction of $T^{*}$, it is clear that it is isomorphic to $T$ under the
bijection $\psi$. Thus, $T$ is a Huffman tree for $P$. ∎

######  Remark 1.

Equations (1) and (2) can be used to show that if a tree $T$ is optimal, then
it should at least satisfy the condition (P1).

Let us call the conditions (P1)–(P3) as Huffman tree properties. We will be
referring to each of them as follows: the condition (P1) will be called the
_level property_ , condition (P2) will be called the _maximum-level sibling
property_ and condition (P3) will be called the _sibling property_. These
properties serve as a potent tool to approach questions related to Huffman
trees.

##  III Points of Maximum

Let the sequence of the codeword lengths of a prefix code $X$ arranged in a
non-decreasing order be called the _length sequence_ of $X$. Let an _optimal
length sequence_ for a PMF $P$ be the length sequence of an optimal code for
$P$. Let us follow the convention of always writing out the probabilities of a
PMF $P=(p_{1},p_{2},\ldots,p_{n})$ in a non-increasing order, i.e., $p_{1}\geq
p_{2}\geq\ldots\geq p_{n}$.

Let us now take up the following problem: what is an optimal length sequence
for a point of maximum? The length sequence of the Huffman code for the
uniform distribution — which is a point of maximum — is known (see, for e.g.,
[3]). To emphasize the point that problems related to Huffman trees can be
effectively handled using the Huffman tree properties, we will now use these
to determine the length sequence of the Huffman code for $U_{n}$.

Consider the tree having $D^{m}$ leaves at level $m$, for some
$m\in\mathbb{N}$. Let us denote it as $T_{U}(m)$. We have the following result
which has appeared in [3].

######  Lemma 1.

Let $n=D^{m}$, for some $m\in\mathbb{N}$. A PMF $P\in\mathcal{P}_{n}$ with
$P=(p_{1},p_{2},\ldots,p_{n})$ has $T_{U}(m)$ as a Huffman tree iff the sum of
the lowest $D$ probabilities of $P$ is greater than or equal to its highest
probability, i.e., iff

$\sum_{i=n-D+1}^{n}p_{i}\geq p_{1}.$

###### Proof.

First suppose that $T_{U}(m)$ is a Huffman tree for $P$. The minimum
probability of the nodes at level $m-1$ is $\sum_{i=n-D+1}^{n}p_{i}$ (maximum-
level sibling property (P2)). From the level property (P1), we have that
$\sum_{i=n-D+1}^{n}p_{i}\geq p_{1}$.

Now suppose that $\sum_{i=n-D+1}^{n}p_{i}\geq p_{1}$. Assign the probabilities
of $P$ to the leaves of $T_{U}(m)$ in such a way that the probabilities of the
leaves from left to right are in a non-decreasing order. We will now show
$T_{U}(m)$ with this assignment of probabilities satisfies the Huffman tree
properties. We will do it by induction on $m$. The statement is clearly true
for $m=1$. Let us assume that for some positive integer $k$, the statement is
true for $m=k$. Let us now take $m=k+1$. Let us denote the PMF formed out of
the probabilities at level $k$ of $T_{U}(k+1)$ to be $Q$. Observe that the
probabilities of $Q$ are arranged in a non-decreasing order from left to right
at the $k$th level. Let $q_{1},q_{2},\ldots,q_{D}$ be the lowest $D$
probabilities of $Q$ taken in a non-decreasing order. The highest probability
of $Q$, say $q_{h}$, is given by $p_{1}+p_{2}+\cdots+p_{D}$. Since
$q_{1}=\sum_{i=n-D+1}^{n}p_{i}$, we have the following inequalities:

$q_{D}\geq q_{D-1}\geq\ldots\geq q_{1}\geq p_{1}\geq p_{2}\geq\ldots\geq
p_{D}.$

Thus, we have that $\sum_{i=1}^{D}q_{i}\geq q_{h}$. By the induction
hypothesis, we have that the tree $T_{U}(k)$, with its nodes retaining its
probabilities as in $T_{U}(k+1)$, satisfies the Huffman tree properties. Now
take a node at level $k$ in the tree $T_{U}(k+1)$ with probability $q_{i}$ and
a node at level $k+1$ with probability $p_{j}$. We have that $q_{i}\geq
q_{1}\geq p_{1}\geq p_{j}$. Thus, the level property (P1) is satisfied in
$T_{U}(k+1)$. Finally, by the way the probabilities were assigned to the
leaves of $T_{U}(k+1)$, the maximum-level sibling property (P2) and the
sibling property (P3) are also satisfied at level $k+1$ of $T_{U}(k+1)$. Thus,
from Theorem 1, the tree $T_{U}(k+1)$ is a Huffman tree for $P$. Hence the
lemma is proved. ∎

######  Remark 2.

For the case $n=D^{m}$ ($m\in\mathbb{N}$), Lemma 1 describes points of
maximum, other than the uniform distribution $U_{n}$, for the minimum expected
length function $\mathcal{L}_{D}$. For a PMF $P\in\mathcal{P}_{n}$, satisfying
the condition of Lemma 1, i.e., $\sum_{i=n-D+1}^{n}p_{i}\geq p_{1}$, we have
from this lemma that $\mathcal{L}_{D}(P)=m$. Since $U_{n}$ also satisfies this
condition of the lemma, and since it is a point of maximum, we have that $P$
is also a point of maximum. Thus, all the PMFs satisfying the condition of
Lemma 1 are points of maximum.

Now, let $T_{U}$ represent the tree $T_{U}(m)$ when $n=D^{m}$ (a power of $D$)
and when $D^{m}<n<D^{m+1}$ ($n$ is not a power of $D$) let $T_{U}$ denote the
tree (see Fig. 2) in which

  * i)

all the leaves are at levels $m$ and $m+1$,

  * ii)

at level $m$, each of the internal nodes is to the right of any of the leaf
nodes and

  * iii)

all the internal nodes, except possibly the leftmost internal node at level
$m$, have $D$ children each. The leftmost internal node at level $m$ has at
least 2 children.

\begin{picture}(16487.0,8565.0)(-1335.0,-8146.0)\end{picture}

Figure 2: An example for $T_{U}$ when $D=3$ and $n$ is not a power of $D$.

It can be seen that these conditions uniquely define the tree $T_{U}$ when $n$
is not a power of $D$. When $D-1$ divides $n-1$, then all the internal nodes
of $T_{U}$ will have $D$ children; and the number of internal nodes at level
$m$ is $(n-D^{m})/(D-1)$. When $D-1$ doesn’t divide $n-1$, only one internal
node will have $m$ children where $m$ is such that $2\leq m\leq D$ and $D-1$
divides $n-m$; and the number of internal nodes at level $m$ is
$\lceil(n-D^{m})/(D-1)\rceil$.

Now we have the following result.

######  Theorem 2.

The tree $T_{U}$ is a Huffman tree for the uniform distribution $U_{n}$.

###### Proof.

Lemma 1 tells us that the theorem is true when $n$ is a power of $D$. Let us
take that $n$ satisfies $D^{m}<n<D^{m+1}$. Consider $T_{U}$ and assign the
probabilities of $U_{n}$ to its leaves. Consider the tree $T_{U}(m)$ obtained
by removing all the leaves from $T_{U}$ at level $m+1$. Let the nodes of
$T_{U}(m)$ retain their probabilities as they were in $T_{U}$. Now look at the
probabilities of the nodes of $T_{U}(m)$ at level $m$. The lowest probability
is at least $1/n$ and the highest probability is at most $D/n$. Thus, by Lemma
1 and Theorem 1, we have that $T_{U}(m)$ satisfies the Huffman tree
properties. This, along with the way the tree $T_{U}$ is defined shows us that
$T_{U}$ also satisfies the Huffman tree properties. Thus, $T_{U}$ is a Huffman
tree for $U_{n}$. ∎

Thus, we have that when $n=D^{m}$, an optimal length sequence for $U_{n}$ is
$(m,m,\ldots,m)$ and when $D^{m}<n<D^{m+1}$ an optimal length sequence for
$U_{n}$ is $(m,m,\ldots,m,m+1,m+1,\ldots,m+1)$ with
$D^{m}-\lceil(n-D^{m})/(D-1)\rceil$ occurrences of $m$. Let us denote this
optimal length sequence for $U_{n}$ by $\mathsf{L}_{U}$.

It turns out that Hwang’s argument, as in [2], can now be used to determine an
optimal length sequence for any point of maximum. Let
$P=(p_{1},p_{2},\ldots,p_{n})$ and $Q=(q_{1},q_{2},\ldots,q_{n})$ be two PMFs
from $\mathcal{P}_{n}$. If the sum of the highest $k$ probabilities of $P$ is
greater than or equal to the sum of the highest $k$ probabilities of $Q$, i.e.
if $\sum_{i=1}^{k}p_{i}\geq\sum_{i=1}^{k}q_{i}$, for all $k$ satisfying $1\leq
k\leq n$, then $P$ is said to _majorize_ $Q$ and is denoted as $P\succ Q$.
Note that this relation is a partial order. It is well-known that every
$P\in\mathcal{P}_{n}$ majorizes the uniform distribution $U_{n}$.

######  Lemma 2.

If $P$ is a point of maximum, then the following hold:
i) $\mathsf{L}_{U}$ is an optimal length sequence for $P$.
ii) When $n$ is not a power of $D$, the PMF $P$ is the uniform distribution
$U_{n}$, or, in other words, $U_{n}$ is the unique point of maximum.

###### Proof.

Let $P=(p_{1},p_{2},\ldots,p_{n})$ and let
$\mathsf{L}_{P}=(l^{(p)}_{1},l^{(p)}_{2},\ldots,l^{(p)}_{n})$ be an optimal
length sequence for $P$. From our ordering convention, we have that
$l^{(p)}_{i}$ is the length of the codeword associated with $p_{i}$. Let us
also consider the optimal length sequence $\mathsf{L}_{U}$ for $U_{n}$ and
write it out as $(l^{(u)}_{1},l^{(u)}_{2},\ldots,l^{(u)}_{n})$. Take
$l^{(u)}_{0}=l^{(p)}_{0}=0$. Making use of Hwang’s technique, we get the
following chain of inequalities:

$\displaystyle\mathcal{L}_{D}(U_{n})$
$\displaystyle=\sum_{i=1}^{n}l^{(u)}_{i}/n,$
$\displaystyle=\sum_{i=1}^{n}(l^{(u)}_{i}-l^{(u)}_{i-1})\sum_{j=i}^{n}\frac{1}{n},$
(3)
$\displaystyle\geq\sum_{i=1}^{n}(l^{(u)}_{i}-l^{(u)}_{i-1})\sum_{j=i}^{n}p_{j},$
(4) $\displaystyle=\sum_{i=1}^{n}l^{(u)}_{i}p_{i},$
$\displaystyle\geq\sum_{i=1}^{n}l^{(p)}_{i}p_{i},$ (5)
$\displaystyle=\mathcal{L}_{D}(P),$

where (4) follows from the relation $P\succ U_{n}$, and (5) follows from the
fact that $\mathsf{L}_{P}$ is an optimal length sequence for $P$. Since
$\mathcal{L}_{D}(U_{n})=\mathcal{L}_{D}(P)$, we have that the inequalities in
(4) and in (5) are equalities. Let us see what they imply.

i) Since the inequality in (5) is actually an equality, we have that
$\mathsf{L}_{U}$ is an optimal length sequence for $P$.

ii) Let $n$ be such that $D^{m}<n<D^{m+1}$. Since the entries in the sequence
$\mathsf{L}_{U}$ are either $m$ and $m+1$, the expression in (3) boils down to
$m\sum_{j=1}^{n}1/n+\sum_{j=k+1}^{n}1/n$, for $k$ such that $l^{(u)}_{k}=m$
and $l^{(u)}_{k+1}=m+1$. Similarly, the expression in (4) is
$m\sum_{j=1}^{n}p_{j}+\sum_{j=k+1}^{n}p_{j}$. Since the inequality in (4) is
an equality, we have that

$\frac{n-k}{n}=\sum_{j=k+1}^{n}p_{j}.$ (6)

Let $I_{1}=\\{1,2,\ldots,k\\}$ and $I_{2}=\\{k+1,k+2,\ldots,n\\}$. We have
that $p_{k+1}$ is greater than or equal to the average of $\\{p_{j}\\}_{j\in
I_{2}}$, which equals $1/n$ (from 6). Thus, $p_{k+1}\geq 1/n$. From (6), we
also have that

$\sum_{j\in I_{1}}p_{j}=k/n.$ (7)

For $j\in I_{1}$, since $p_{j}\geq p_{k+1}\geq 1/n$, (7) can occur iff

$p_{j}=1/n,\text{ for all }j\in I_{1}.$ (8)

Now, if there exists a $j\in I_{2}$ such that $p_{j}<1/n$, then (6) implies
that $p_{k+1}>1/n$. But this contradicts (8). Thus, $P$ is the uniform
distribution. Hence, when $n$ is not a power of $D$, uniform distribution
$U_{n}$ is the unique point of maximum. ∎

Lemma 2 tells that when $n$ is not a power of $D$, the uniform distribution is
the unique point of maximum. It also tells that when $n$ is a power of $D$,
the set of all the points of maximum is precisely the collection of all the
PMFs that have $\mathsf{L}_{U}$ as their optimal length sequence. Is this set
the same as the set of all PMFs whose Huffman code’s length sequence is
$\mathsf{L}_{U}$? The answer to this question is not clear at this stage
because the Huffman algorithm does not generate all the optimal codes. The
following result will come to our aid:

######  Lemma 3.

If $\mathsf{L}$ is an optimal length sequence for a $P\in\mathcal{P}_{n}$,
then there exists a Huffman tree for $P$ with $\mathsf{L}$ as its length
sequence.

###### Proof.

Let $T$ be an optimal tree for $P$ with $\mathsf{L}$ as its length sequence.
It should at least satisfy the level property (P1) (Remark 1).

Let $l_{\max}$ be the maximum level of a node of $T$. Change, if necessary,
the assignment of children at level $l_{\max}$ to the internal nodes at level
$l_{\max}-1$ so that the resulting tree is still a subtree of $T_{\infty}$,
but now the maximum-level sibling property (P2) and the sibling property (P3)
are satisfied by the nodes at level $l_{\max}$. This will not create any new
leaf nodes at level $l_{\max}-1$ of the resulting tree, call it $T^{\prime}$,
for otherwise one of the leaves at level $l_{\max}$ can be deleted and its
probability can be assigned to one of the newly created leaves at level
$l_{\max}-1$. If we now throw away the other leaves, if present, without any
assignment of probabilities, then the expected length of this new tree is
strictly less than that of $T$ which is not possible. Further, we have that
$T^{\prime}$ is optimal.

Assume that we now have a tree

  * i)

which is optimal, and

  * ii)

in which the sibling property (P3) is true for the nodes at levels
$l_{\max}-k$ to $l_{\max}$, for some $k$ satisfying $0\leq k<l_{\max}-1$.

Change, if necessary, the assignment of children at level $l_{\max}-k-1$ to
the internal nodes at level $l_{\max}-k-2$ so that the resulting tree is still
$D$-ary, but now the sibling property (P3) is satisfied by the nodes at level
$l_{\max}-k-1$. A tree obtained after this re-assignment is clearly optimal.
Moreover, the nodes at levels $l_{\max}-k$ to $l_{\max}$ still satisfy the
sibling property (P3) as the nodes at these levels which were siblings before
the rearrangement remain so after it. This process can be continued till we
get a tree which is optimal and satisfies (P2) and (P3). This tree is a
Huffman tree for $P$ (Remark 1 and Theorem 1) and has $\mathsf{L}$ as its
length sequence. ∎

Even though the Huffman algorithm is restrictive in the range of optimal trees
it constructs, Lemma 3 assures us that the algorithm can yield an optimal tree
corresponding to any optimal length sequence.

Thus, for the case of $n=D^{m}$, any point of maximum has a Huffman tree with
$\mathsf{L}_{U}$ as its length sequence. From Lemmas 1 and 2, the following
theorem follows:

######  Theorem 3.

i) When $n$ is a power of $D$, the points of maximum for the minimum expected
length function $\mathcal{L}_{D}$ are those $P=(p_{1},p_{2},\ldots,p_{n})$
from the set $\mathcal{P}_{n}$ for which the sum of the lowest $D$
probabilities is greater than or equal to its maximum probability, i.e.

$\sum_{i=n-D+1}^{n}p_{i}\geq p_{1}.$

ii) When $n$ is not a power of $D$, the uniform distribution $U_{n}$ is the
unique point of maximum for $\mathcal{L}_{D}$.

##  IV Concluding Remarks

The points of maximum of the minimum expected length function have been
completely characterized using a characterization of Huffman trees, and a
chain of inequalities that Hwang used to show the Schur-concavity of the
minimum expected length function. This result shows that the points of maximum
known in the literature are all that exist.

## References

  * [1] D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes,” _Proceedings of the IRE_ , vol. 40, no. 9, pp. 1098–1101, 1952.
  * [2] F. Hwang, “Generalized Huffman Trees,” _SIAM J. Appl. Math._ , vol. 37, no. 1, pp. 124–127, 1979.
  * [3] N. Geckinli, “Two Corollaries to the Huffman Coding Procedure,” _IEEE Trans. Inf. Th._ , vol. 21, no. 3, pp. 342–344, 1975.
  * [4] R. Gallager, “Variations on a Theme by Huffman,” _IEEE Trans. Inf. Th._ , vol. 24, no. 6, pp. 668–674, 1978.
  * [5] T. M. Cover and J. A. Thomas, _Elements of Information Theory_. John Wiley & Sons, 2012.


# i-Code V2: An Autoregressive Generation Framework
over Vision, Language, and Speech Data

Ziyi Yang, Mahmoud Khademi, Yichong Xu, Reid Pryzant, Yuwei Fang, Chenguang
Zhu,
Dongdong Chen, Yao Qian, Mei Gao, Yi-Ling Chen, Robert Gmyr, Naoyuki Kanda,
Noel Codella, Bin Xiao, Yu Shi, Lu Yuan, Takuya Yoshioka, Michael Zeng,
Xuedong Huang
Microsoft Azure Cognitive Services Research
<EMAIL_ADDRESS>
###### Abstract

The convergence of text, visual, and audio data is a key step towards human-
like artificial intelligence, however the current Vision-Language-Speech
landscape is dominated by encoder-only models which lack generative abilities.
We propose closing this gap with i-Code V2, the first model capable of
generating natural language from any combination of Vision, Language, and
Speech data. i-Code V2 is an integrative system that leverages state-of-the-
art single-modality encoders, combining their outputs with a new modality-
fusing encoder in order to flexibly project combinations of modalities into a
shared representational space. Next, language tokens are generated from these
representations via an autoregressive decoder. The whole framework is
pretrained end-to-end on a large collection of dual- and single-modality
datasets using a novel text completion objective that can be generalized
across arbitrary combinations of modalities. i-Code V2 matches or outperforms
state-of-the-art single- and dual-modality baselines on 7 multimodal tasks,
demonstrating the power of generative multimodal pretraining across a
diversity of tasks and signals.

##  1 Introduction

Pretrained Large language models (LLMs) have experienced massive success as
general-purpose solutions for multiple tasks Brown et al. (2020). However, a
large gap persists between the capabilities of LLMs and true humanlike
intelligence. This is partially because humans perceive a variety of sensory
inputs while LLMs are typically restricted to Language (L) data and unable to
understand or generalize to other modalities such as Vision (V) and Speech
audio (S).

Recently, the field of multimodal AI, which aims to develop AI systems capable
of modeling multiple kinds of signals, has witnessed significant progress
including new learning techniques (Radford et al., 2021; Bao et al., 2022;
Alayrac et al., 2022), training data (Schuhmann et al., 2022; Zellers et al.,
2022a; Yang et al., 2023), and model architectures (Su et al., 2020; Li et
al., 2019; Xu et al., 2022).

Despite this progress in multimodal AI, most research has focused on
understanding pairs of modalities, such as speech-language and vision-
language, and the fast-growing subfield of triple-modality AI (Language,
Vision, Speech) remains limited to encoder-only models (Akbari et al., 2021;
Zellers et al., 2022b; Yang et al., 2023).

This paper proposes i-Code V2, the first encoder-decoder generative model for
the triple-modality setting. i-Code V2 can flexibly generate text from
arbitrary combinations of Language, Vision, and Speech data. This model
addresses three ongoing challenges within multimodal research.

First, at the time of writing, all existing triple-modality models are
encoder-only, i.e. they can conduct discriminative tasks such as multimodal
classification but not generative ones like visual question answering or
automatic speech recognition. i-Code V2 enables the model to generate content
from multimodal signals, unlocking more diverse applications and improved
discriminative performance He et al. (2022).

Second, most existing triple-modality research leverages triple-modality data
(i.e. video with subtitles and audio track). However, the three modalities in
video data can be noisily aligned (Miech et al., 2019) which degrades
downstream pretraining. Furthermore, the available high quality video data is
several orders of magnitudes smaller in size than single- or dual-modality
datasets. For example, the largest publicly available image-caption dataset
LAION (Schuhmann et al., 2022) has 5 billion pairs (335 billion text tokens)
while the largest video dataset MERLOT has 180M videos (Akbari et al., 2021;
Zellers et al., 2022a) and only 5 billion text tokens. i-Code V2 proposes a
novel method for efficiently leveraging these larger and higher-quality dual-
and single- modality datasets within a triple-modality pretraining framework.
We accomplish this with a new, generalized sequence-to-sequence pretraining
objective which converts multiple secondary objectives into simple text
completion problems.

Third, multimodal tasks are diverse in settings and data formats, e.g.
Automatic Speech Recognition (ASR), vision QA, sentiment analysis, etc.
Existing techniques apply separate inference strategies to each problem type,
adding complexity and overhead for practitioners. i-Code V2 unifies all tasks
under its text completion framework, rendering multimodal inference and cross-
task transfer easier for practitioners.

i-Code V2 is built on top of state-of-the-art single-modality models: the
vision and speech modalities are encoded with single-modality encoder
respectively. Next, these encoded features and text token embeddings are
inputted to a joint vision-language-speech encoder, which merges the different
modalities into a shared representational space. Last, a language decoder,
conditioned on the joint encoder via a cross-attention mechanism, is trained
to generate language tokens autoregressively.

We evaluate i-Code V2 thoroughly on 7 datasets, including multimodal
summarization, multimodal dialogue generation, multimodal sentiment analysis,
vision QA, vision captioning, and ASR. Notably, i-Code V2 outperforms previous
SOTA models on MSMO (multimodal summarization), Image Chat (multimodal
dialogue generation), UR-FUNNY (multimodal sentiment analysis). Additionally,
i-Code V2 exhibits highly competitive performance compared to specialized
dual-modality models on vision QA, vision captioning, and ASR, suggesting the
power of integrative multimodal pretraining.

In summary, our key contributions are threefold:

  1. 1.

We propose i-Code V2, the first vision-language-speech generative model that
can generate natural language from one-, two- or three-modality inputs of
image, video, language and speech.

  2. 2.

We propose to pretrain i-Code V2 on a large-scale uni- and dual-modality
datasets with a novel cross-modality text completion framework. The
pretraining data resource is of higher quality and of larger scale, compared
with video data previously used in three-modality learning. Using a sequence-
to-sequence training objective, as opposed to the modality-specific objectives
and task heads common in the multimodal AI space, can be flexibly applied to
arbitrary combinations of modalities while simplifying the training and
inference process.

  3. 3.

i-Code V2 shows state-of-the-art or competitive performance across several
multimodal tasks and domains, including multimodal natural language
generation, vision QA, vision captioning, ASR, video sentiment analysis,
multimodal summarization and dialogue generation.

##  2 Related Work

Multimodal Learning. This field studies extracting and incorporating
information from vision, language, and speech modalities. A recent advance is
unifying models of different modalities to the transformer. For example,
representing vision and language with one multimodal transformer model has
shown great performance in image caption (Wang et al., 2022a; Alayrac et al.,
2022), vision classification (Yu et al., 2022), vision question answering (Yu
et al., 2022; Li et al., 2022), etc. In these models, extracted image features
(Chen et al., 2020) or projections of image patches (Wang et al., 2022e; Yu et
al., 2022) are fused together with text token embeddings, then input to a
multimodal encoder to obtain unified representations for vision and language.
Lately, there has been significant progress in unifying representations for
vision, language, and speech modalities. Three-modality encoder are pretrained
on video data (Zellers et al., 2022a; Yang et al., 2023) or dual-modality data
pairs (Yang et al., 2023). Multimodal representations can be integrated by a
late-stage multimodal fusion network (Yang et al., 2023), or integrated early
at the input stage (Zellers et al., 2022a).

Natural Language Generation (NLG). Language generation has achieved
significant process in many fronts in the era of deep learning, including text
summarization (Liu and Lapata, 2019; Yang et al., 2020; Lewis et al., 2020;
Zhang et al., 2020; He et al., 2022), dialogue generation (Bao et al., 2020;
Zhao et al., 2020; OpenAI, 2022), question answering (Rajpurkar et al., 2016;
Yang et al., 2018), machine translation (Wu et al., 2016), etc. The
transformer encoder-decoder model (Vaswani et al., 2017) is a powerful
sequence-to-sequence generation architecture, due to its ability to
efficiently model global dependencies in input text sequence. The Generative
Pretrained Transformer (GPT) model families, which is transformer decoder
only, have shown exceptional abilities in multi-task learning (Radford et al.,
2019), few-shot in context learning (Brown et al., 2020), following human
instructions (Ouyang et al., 2022), etc. The recently released large language
model (LLM) ChatGPT, trained with Reinforcement Learning from Human Feedback
(RLHF), can generate human-like text responses in fields like programming,
tutoring, and professional writing.

Generative Multimodal Model. Generating one modality from another modality or
a combination of input modalities has been an active field of multimodal
learning. For example, image captioning (Johnson et al., 2016; Wang et al.,
2022a), automatic speech recognition (Yu and Deng, 2016; Radford et al.,
2022), text-to-image generation (Ramesh et al., 2021, 2022; Saharia et al.,
2022; Rombach et al., 2022), etc. Inspired by the success of unified sequence-
to-sequence multitask learning on NLP (Raffel et al., 2020; Lewis et al.,
2020), several recent works propose to unify vision-language tasks with one
homogeneous model architectures and schemes. For example, Wang et al. (2022c);
Lu et al. (2022); Tang et al. (2022) unite vision and vision-language tasks,
such as image classification, object detection, semantic segmentation, visual
QA, document understanding, image generation, etc. Huang et al. (2023)
recently proposed the Kosmos-1 model to generate text based on vision and text
input.

Different from previous works, i-Code V2 can not only encode and merge inputs
from vision, language, and speech modalities, but also generate natural
language. Such an integrative framework unifies various tasks across
multimodal summarization, multimodal sentiment analysis, speech recognition,
visual QA and vision captioning.

##  3 An Integrative Multimodal Generative Model

In this section, first we will introduce the design and model architecture of
i-Code V2. Then we present how we pretrain i-Code V2 on diverse large-scale
multimodal datasets.

###  3.1 Model Architecture

i-Code V2 model consists of multimodal encoders and a language decoder.
Following the spirit of integrative AI (Yang et al., 2023), the language,
vision and speech modalities are encoded by their corresponding encoder or
converted to numerical representations respectively, before fused with each
other. Leveraging pretrained models enables us to utilize state-of-the-art
model architecture for each modality. It is also computationally efficient
since these models have already been extensively trained on single-modality
data. This also gives us the flexibility of choosing preferred encoders. For
example, we can use a medical-domain specific language encoder-decoder; or
choose smaller speech/vision encoder on devices with low computation resource,
without having to re-design the framework.

In detail, we leverage the following state-of-the-art single-modality
encoders:

##### Vision Encoder.

In different multimodal scenarios, the vision modality can be either a single
image or a video (especially when the input contains speech). To flexibly
encode and represent the vision modality input, we opt to use OmniVL, a
foundation model for both image-language and video-language (Wang et al.,
2022b). It uses independent 2D/3D convolution-based patch tokenizer to first
process image/video and a unified vision transformer to generate vision
representations. It has 122 million parameters.

##### Speech Encoder.

We use WavLM large (Chen et al., 2022), a speech encoder pretrained on
94k-hour data in a self-supervised manner. Pretraining objectives include
masked speech denoising and predicting. The model architecture is a
transformer encoder with Gated Relative Position Bias on top of a temporal
CNN-based featurizer. The parameter size is 315 million.

##### Joint Vision-Language-Speech Encoder.

We use a 24-layer transformer encoder to jointly encode vision, language and
speech modalities. After the vision and speech modality inputs are encoded by
their respective encoder, a 1-layer projection (one for each modality)
transforms the features into the same dimension as the text vocabulary
embedding. Transformed features are concatenated with the text tokens
embeddings and then input into the transformer layers for both inter- and
intra-modality attention.

We initialize the transformer layers of the joint encoder using the encoder
part of the recently developed Z-Code++ summarization model, which has 485
million parameters and was pretrained using generative training objectives on
160G of English text data (He et al., 2022).

##### Language Decoder with Multimodal Cross-Attention.

i-Code V2 then uses a decoder to generate textual sequences from the
multimodal encoder output. The 24-layer decoder cross-attends with the
multimodal representation from the joint Vision-Language-Speech encoder. We
use the pretrained transformer _decoder_ from the Z-Code++ model (485 million
parameters) to initialize these parameters.

Figure 1: i-Code V2 Model Architecture. Parameters of vision and speech
encoders are frozen during pretraining and are updated in finetuning.

###  3.2 Large-Scale Multimodal Generative Pretraining

We leverage a collection of large-scale dual modality datasets to conduct
speech-language generative pretraining, vision-language generative
pretraining, and language-language generative pretraining. In particular, our
pretraining objectives adopt a simple sequence-to-sequence strategy, which
poses each modality-specific and cross-modality objective as a text
completion.

####  3.2.1 Vision-Language Generative Pretraining

##### Image Captioning.

Given an image, the model predicts the corresponding textual caption. We use
the 72.8 million subset of Florence image-text pair dataset (Yuan et al.,
2021). The task prompt is “Generate the caption for this image: ”.

##### Video Captioning.

The pretraining task is to generate the caption of a video clip. We use the
largest-scale publicly available video captioning dataset WebVid-10M (Bain et
al., 2021), which contains 10.7M video-caption pairs. The task prompt is
“Generate the caption for this video: ”.

##### Vision Question & Answering.

For this task, we use VQA v2 training set, an open-ended vision question
answering dataset (Antol et al., 2015), which has 443,757 question-answer
pairs. The task prompt is “Answer the following question based on the image:
”.

##### Vision-Augmented Text Reconstruction.

This pretraining task aims to improve the model’s ability on cross-modal
understanding. We mask spans of the textual image caption and replace them
with sentinel tokens, similar to T5 pretraining (Raffel et al., 2020). The
model needs to predict masked out text spans, given the masked textual input
and the image. The data resource is the same as in “Image Captioning”. The
task prompt is “Reconstruct the following text based on the image: ”.

####  3.2.2 Speech-Language Generative Pretraining

We leverage three sources of labeled data for generative speech-language
learning:

##### Speech transcription.

This dataset contains 75k-hour human-transcribed speech utterances (Yang et
al., 2023), collected from scenarios such as call center and AI voice
assistant. The input is the speech utterance, and the target output is the
transcription. The pretraining loss is the cross entropy between the target
and prediction. The task prompt is “Transcribe the speech utterance to text:
”.

##### Speech Sentiment Analysis.

The goal of this task is to predict the sentiment of a speech utterance, e.g.,
from “highly negative” to “highly positive”. We gather data from CMU
Multimodal Opinion Sentiment and Emotion Intensity (CMU-MOSEI) (Zadeh et al.,
2018) and Spoken Language Understanding Evaluation (SLUE) (Shon et al., 2022).
The task prompt is “Predict the sentiment of this segment: ”. The output
target is the textual sequence of the “sentiment”.

##### Speech Emotion Recognition.

The task is to predict the emotion category of a speech utterance, including
{happiness, sadness, anger, fear, disgust, surprise}. The dataset is from the
emotion intensity subtask of CMU-MOSEI. The target generation sequence is the
emotion category name. The task prompt is “Predict the emotion of this
segment: ”.

##### Speech-Augmented Text Reconstruction.

Similar to “Vision-Augmented Text Reconstruction”, we mask spans of the speech
transcription and ask the model to predict masked-out text spans, given the
speech input as well. The task prompt is “Reconstruct the following text based
on the speech: ”.

####  3.2.3 Language-only Generative Pretraining.

We include high-quality text-only corpus, i.e. English Wikipedia and
BookCorpus (Zhu et al., 2015), in pretraining as a supplement to the language-
modality data of vision-language and speech-language datasets. This language-
only pretraining task follows T5 where the input is span-masked text, and the
output is the original masked span. The task prompt is “Reconstruct masked
spans in the following text: ”.

The multimodal pretraining process, task, and textual instructions are
illustrated in Figure 2.

Figure 2: i-Code V2 multimodal pretraining. It unifies tasks across vision,
language and speech domains to text completion/generation training objectives.
Pretraining tasks include both unimodal, e.g. TR, and dual-modal ones, e.g.,
ASR, SA, ER, SR, VC, VQA, and VR (full names of task initials are provided in
the figure).

####  3.2.4 Pretraining Details

To expedite the pretraining process, we freeze the speech and vision encoders
during pretraining, only updating the parameters of the Vision-Language-Speech
encoder and the language decoder. For each optimization step, we select the
pretraining dataset from the candidate pool using “Exponentially Smoothed
Weighting (ESW)” sampling. ESW is widely used in multilingual pretraining
(Devlin et al., 2019) where multilingual corpus sizes can be different with
several magnitudes. Assume the size ratio of the dataset $A$ in the overall
training datasets is $P(A)$. We exponentiate the ratio by the factor $S<1$
then we sample datasets according the re-normalized exponential ratio
$\frac{p(A)^{S}}{\sum_{A}{p(A)^{s}}}$. We use $S=0.5$ in our setting.

We pretrain the i-Code V2 model on datasets introduced above for 1 epoch on 24
A100 GPUs, with batch size 8 (per-GPU) and gradient accumulation steps 3.
Having accumulation steps > 1 also makes the effective optimization batch
contain data from different resources.

##  4 Experiments

We test i-Code v2 on 7 datasets from assorted categories, including multimodal
summarization, multimodal dialogue generation, video multimodal sentiment
analysis, ASR, vision QA, and vision captioning. In downstream tasks, we
update parameters of Vision-Language-Speech encoder, language decoder, and
single-modality encoders. Finetuning hyperparameters can be found in Section
4.7.

Overall, i-Code V2 sets a new state-of-the-art in 3 tasks (MSMO, Image Chat,
and UR-FUNNY) and remains highly competitive in the rest, suggesting the
promise of integrative and generative multimodal pretraining.

###  4.1 Multimodal Summarization

We first evaluate on multimodal summarization task. Well studied in the field
of natural language processing, in traditional summarization, input only
contains language. However, in many real-world scenarios, such as multimedia
coverage and online news article, key information is also included other
modalities, e.g., pictures. We test i-Code V2 on the multimodal news
summarization dataset MSMO (Zhu et al., 2018). Given a news article with
image(s), the task is to generate a few-sentence summarization. Its
training/validation/test split contains 293,965/10,355/10,261 news articles
with images from Daily Mail website. The ground-truth “golden” summary is the
highlight written by the news editor. The evaluation metrics are ROUGE scores
(Lin, 2004). Baseline models include:

##### Text-only summarization model.

BertSum (Liu and Lapata, 2019) model variants BertAbs and BertExtAbs, BART
(Lewis et al., 2020), ZCode++ (He et al., 2022).

##### UniMS (Zhang et al., 2022)

An encoder-decoder multimodal summarization model that can process multimodal
inputs and select images.

##### MOF (Zhu et al., 2020)

A multimodal generation model with the guidance of multimodal reference.

##### ATG/ATL/HAN

These are baselines from the original MSMO dataset paper, that Point Generator
Network (See et al., 2017) attending with global vision features(ATG),
attending with local vision features (ATL), and hierarchical attention with
local features.

The task prompt used in i-Code V2 is “Summarize this article with the images:
”. As shown in Table 1, compared with baseline models, i-Code V2 has shown
competitive performance on ROUGE-1 and ROUGE-L. Compared with the language
encoder-decoder ZCode++, that i-Code V2 encoder-decoder is initialize from,
i-Code V2 shows considerable improvement, which demonstrates the effectiveness
of the proposed multimodal pretraining.

Model | R1 | R2 | RL
---|---|---|---
BertAbs | 39.02 | 18.17 | 33.20
BertExtAbs | 39.88 | 18.77 | 38.36
BART | 41.83 | 19.83 | 39.74
ZCode++ | 42.19 | 20.03 | 37.2
UniMS | 42.94 | 20.50 | 40.96
MOF (enc) | 41.05 | 18.29 | 37.74
MOF (dec) | 41.20 | 18.33 | 37.80
HAN | 40.82 | 18.30 | 37.70
ATL | 40.86 | 18.27 | 37.75
ATG | 40.63 | 18.12 | 37.53
i-Code V2 | 44.7 | 21.0 | 37.7
Table 1: Results on the multimodal news summarization MSMO test set.

###  4.2 Multimodal Dialogue Generation

Our model also has the ability perceive contextual multimodal signals to
generate textual response. A type of datasets to measure such ability is
multimodal-based conversation. For example, for the multimodal open-domain
dialogue dataset Image-Chat (Shuster et al., 2020), each data example includes
an image; the dialogue history between two speakers A and B; speaker style
traits. The task objective is to generate the next-round dialogue. Baselines
include:

##### BlenderBot (Roller et al., 2020)

A sequence-to-sequence ChatBot model of 2.7 Billion parameters pretrained on
1.5B Reddit comment conversations.

##### Multi-Modal BlenderBot(Shuster et al., 2021)

The multimodal version of BlenderBot that fuses vision features from
ResNet/Faster-RCNN in the multimodal text generation.

##### 2AMMC (Ju et al., 2019)

A multimodal generative model that combines ResNet and text transformer.

##### DialoGPT (Zhang et al., 2019)

A GPT model trained on 147 million social media dialogues.

With the task prompt, we can conveniently guide the model to generate dialogue
in the speaker style, the prompt is “Generate the response for the dialogue in
{style type} style: ”. For fair comparison, we do not include baseline model
that co-trains on multiple multimodal dialogue datasets e.g., (Shuster et al.
(2020)). The evaluation metric includes F1 and ROUGE-L. Results in Table 2
show that i-Code V2 has significantly outperformed previous baselines on both
F1 and R-L metrics.

Model | F1 | RL
---|---|---
DialoGPT | 6.2 | 5.2
2AMMC | 9.3 | 11.0
BlenderBot | 9.2 | 12.3
Multi-Modal BlenderBot | 13.1 | 18.0
i-Code V2 | 15.5 | 18.6
Table 2: Results on the multimodal dialogue generation dataset Image Chat.

###  4.3 Video Multimodal Sentiment Analysis

We further evaluate on multimodal sentiment analysis datasets. E.g., in UR-
FUNNY (Hasan et al., 2019), a humor detection dataset, the input is a video,
the audio of the video, and the text transcript. The task is to predict
whether the immediate laughter will follow the clip. The dataset contains
5306/1313/1638 humor instances for train/validation/test split, and
5292/1313/1652 for the not humor instances. Although previous models
approached this problem as binary classification, we finetune i-Code V2 to
directly predict the target sequence “funny”/“unfunny”, with task prompt
“Predict the sentiment of this clip: ”. We compare i-Code V2 with baselines
that use all three-modality inputs. i-Code V2 outperforms previous models by
large margins. This shows that the multimodal encoder in i-Code V2 can
effectively fuse signals of vision, language and speech modalities, and the
decoder can successfully attend with the multimodal encoder outputs.

Model | Accuracy
---|---
ZCode++ | 75.4
MulT (Tsai et al., 2019) | 70.55
MISA (Hazarika et al., 2020) | 70.61
MultiBench (Liang et al., 2021) | 66.7
BBFN (Han et al., 2021) | 71.68
LMF (Liu et al., 2018) | 67.53
TFN (Zadeh et al., 2017) | 68.57
i-Code V2 | 79.59
Table 3: Prediction accuracy on UR-FUNNY dataset.

###  4.4 Automatic Speech Recognition

Automatic Speech Recognition (ASR) transfers human-spoken language into text.
As a multimodal generative model, i-Code is able to process speech signals and
generate the text transcript in a sequence-to-sequence manner. We evaluate on
the classical ASR dataset LibriSpeech (Panayotov et al., 2015). We finetune
i-Code V2 on LibriSpeech 960h training data and test on the test-clean split.
We compare i-Code V2 with the following models:

##### WavLM (Chen et al., 2022)

Transformer-based speech encoder that is pretrained on audio data with self-
supervised learning

##### wav2vec 2.0 (Baevski et al., 2020)

A speech representation model with CNN-Transformer architecture, pretrained
with a contrastive self-supervised task on quantized speech representations.

##### S2T Transformer (Wang et al., 2021)

A transformer-based text-to-speech model provided in the Fairseq (Ott et al.,
2019) sequence modeling toolkit.

##### Whisper (Radford et al., 2022)

A recently developed speech recognition system that is pretrained on 680K
hours labeled speech-text transcript with multitask-supervision.

Model | WER(%)$\downarrow$
---|---
wav2vec 2.0 | 2.0
WavLM Large | 2.1
Whisper Large | 2.7
Whisper Medium | 4.12
S2T Transformer Large | 3.2
i-Code V2 | 3.86
Table 4: Word Error Rate (WER) on LibriSpeech dataset test-clean split.

The task prompt is “transcribe the speech utterance to text: ”. Results are
presented in Table 4. i-Code V2 exhibits competitive performance on this task
compared with ASR models specifically designed for this task, showing it is
capable of decoding speech signals to language. Note that WavLM Large result
presented in Table 4 is using Connectionist temporal classification (CTC)
decoding on top of the speech encoder, which is superficially designed for ASR
task. While the language decoding in i-Code V2 is for general purpose.

###  4.5 Vision QA

An important domain in vision-language learning is vision question & answering
(QA). The task is given an image and a question about the image, the model
needs to predict the answer. The evaluation benchmark we test on is the Visual
Question Answering (VQA) 2.0 (Antol et al., 2015). The train/validation/test
data split has 443,757/214,354/447,793 questions respectively. Previous
vision-language works, including those with language-generation functionality,
almost all convert this task into a classification task: the models are
trained to the answer from 3129 most frequent candidates (e.g. (Wang et al.,
2022d)). Unlike this closed-vocabulary setup, we adopt an open-vocabulary
setting that i-Code V2 is trained to generate the answer. The task prompt is
“Answer the following question based on the image:”. Note that we don’t
provide candidate answer choices to i-Code V2 during testing. Table 5 contains
baselines for both settings. i-Code V2’s performance is competitive compared
with vision-language models such as VisualBERT, LXMERT and VL-BERT. It is
worth noting that Flamingo is pretrained on 2.1B vision-language data examples
and has 80B parameters. In comparison i-Code V2 is pretrained on < 80M vision-
language data and only has 1.4% parameters of Flamingo (1.1B parameters,
vision encoder, multimodal encoder, and the language decoder).

Model | Accuracy
---|---
Closed-Vocabulary
VisualBERT (Li et al., 2020) | 71.0
LXMERT (Tan and Bansal, 2019) | 72.5
FLAVA | 72.8
OSCAR | 73.16
VL-BERT (Su et al., 2020) | 72.2
BLIP (Li et al., 2022) | 78.32
CoCa (Yu et al., 2022) | 82.3
Open-Vocabulary
Flamingo*(Alayrac et al., 2022) | 82.1
i-Code V2 | 75.10
Table 5: Comparison with baselines on VQA 2.0 test set.

We further test i-Code V2 on the VizWiz-VQA dataset (Gurari et al., 2019),
which is designed to answer visual questions from visually impaired people. It
has 20,000/3,173/8000 image-question-answer triplet for the
train/validation/test data split. Baselines include VisWiz Challenge Winner
(Liu et al., 2021), BAN (Kim et al., 2018), B-Ultra & B-FRCNN (Changpinyo et
al., 2019). Our performance is obtained from submitting to VizWiz challenge
server. Again, we adopt the open-vocabulary evaluation setting. i-Code V2
shows better performance than the previous VizWiz challenge winner and
provides a strong baseline for models of intermediate size. As will be
discussed in Section 4.7, i-Code V2 also shows impressive zero-shot
performance on VizWiz-VQA dataset, given that it is an open-vocabulary
generative model.

Model | Accuracy
---|---
BAN | 51.6
B-FRCNN | 51.9
B-Ultra | 53.7
LXMERT | 55.4
VisWiz Challenge Winner | 60.6
Flamingo* | 65.4
i-Code V2 | 61.3
Table 6: Performance on VisWiz-VQA test-std set.

###  4.6 Image Captioning

Image captioning is an important field of multimodal understanding and
generation. We evaluate i-Code V2 on the MS-COCO dataset (Chen et al., 2015)
with the Karpathy test split (Karpathy and Fei-Fei, 2015), with results
presented in Table 7. Evaluations metrics include BLEU@4, METEOR, CIDEr, and
SPICE. The task prompt is “Generate the caption for this image: ”. Baseline
methods include image captioning models BUTD (Anderson et al., 2018) and
AoANet (Huang et al., 2019); vision-language generative models, e.g., VL-BART,
VL-T5 (Cho et al., 2021), XGPT(Xia et al., 2021); models using additional
auxiliary input such as UNITAB (Yang et al., 2022) with object detection
information. i-Code v2 outperforms vision-language baselines on METEOR, CIDEr,
and SPICE.

Model | BLEU@4 | METEOR | CIDEr | SPICE
---|---|---|---|---
VL-T5 | 34.5 | 28.7 | 116.5 | 21.9
VL-BART | - | - | 116.6 | -
BUTD | 36.2 | 27.0 | 113.5 | 20.3
AoANet | 37.2 | 28.4 | 119.8 | 21.3
UNITAB | 35.8 | 28.4 | 119.1 | 21.5
XGPT | 37.2 | 28.6 | 120.1 | 21.8
i-Code V2 | 36.8 | 28.9 | 124.3 | 22.3

Table 7: Experimental results (with cross-entropy optimization) on MS-COCO
image captioning dataset (Karpathy test split).

###  4.7 Analysis & Explorations

##### Ablation study on pretraining effectiveness.

We investigate the pretraining effectiveness by comparing performance of
i-Code V2 with and without the multimodal pretraining (Section 3.2). As shown
in Table 8, the multimodal pretraining further improves the performance on
downstream tasks. The improvement is more significant on tasks where cross-
modality understanding is more crucial, such as video sentiment analysis.

variant | UR-FUNNY | Image Chat | LibriSpeech
---|---|---|---
i-Code V2 | Accuracy | F1 | R-L | WER(%)$\downarrow$
w/ pretraining | 79.59 | 15.5 | 18.6 | 3.86
w/o pretraining | 62.85 | 15.0 | 18.2 | 12.1

Table 8: Ablation study of the proposed multimodal pretraining.

##### Ablation study on pretraining objectives.

We explore how pretraining objectives affect the model performance. For
example, as shown in Table 9, removing “Language-only Generative Pretraining”
(LGP) is adversarial for the performance on multimodal summarization dataset
MSMO, while it has negligible effect on ASR.

Dataset | MSMO | ASR
---|---|---
Metric | R1 | R2 | RL | WER ($\downarrow$)
w/o LGP | 42.23 | 20.12 | 37.1 | 3.88
Full Pretraining | 44.7 | 21.0 | 37.7 | 3.86

Table 9: Ablation study on pretraining objectives. LGP stands for “Language-
only Generative Pretraining”.

##### Zero-shot Learning.

We further explore i-Code V2 transfer learning ability. We test pretrained
i-Code V2 directly on VizWiz-VQA without finetuning. As a open-vocabulary
generative model, the zero-shot performance of i-Code V2 is respectful, with
overall accuracy 22.53%, and 73.6% for “Yes/No” answers, 8.47% for “Number”
answers, 24.46% for “Other” answers, 10.49% for “Unanswerable” answers
respectively (for reference, Flamingo-9B zero-shot accuracy is 28.8%). Note
that VizWiz-VQA questions are from visually impaired population and images are
also distinct from those in VQA 2.0 that is in the pretraining data. With the
significant difference in dataset distribution between VizWiz-VQA and VQA 2.0,
this performance indicates that i-Code V2 can closely follow the task
instruction to answer the question (e.g., other than generating the caption).
It also shows that i-Code V2 learns to answer visually grounded questions from
pretraining, even though there are assorted pretraining tasks and datasets.

##### Training Hyperparameters for Downstream Tasks.

In Table 10, we list the learning rate, batch size (per GPU), and epochs for
each finetuning dataset. We choose the finetuning checkpoint with the best
performance on the validation test for the final evaluation. All finetuning
jobs are conducted on eight A100 GPUs.

Task | lr | Batch Size | Epochs
---|---|---|---
MSMO | $2.5\times 10^{-5}$ | 8 | 12
Image Chat | $2\times 10^{-5}$ | 8 | 5
UR-FUNNY | $1\times 10^{-5}$ | 8 | 12
LibriSpeech | $2\times 10^{-5}$ | 2 | 10
VQA | $2\times 10^{-6}$ | 2 | 4
VisWiz-VQA | $2\times 10^{-6}$ | 2 | 4
MS-COCO | $2\times 10^{-6}$ | 2 | 4

Table 10: Training hyperparameters on downstream tasks.

##  5 Conclusion

In this paper, we propose i-Code V2, a multimodal generative model that
jointly encodes language, vision and speech modalities and decodes the
corresponding natural language sequence. i-Code V2 is pretrained on assorted
high-quality single- and dual-modality datasets, where different tasks are
unified as a multimodal sequence-to-sequence generation paradigm. i-Code V2
exhibits impressive performance in various multimodal generation domains,
including multimodal nature language generation, ASR, vision QA, vision
captioning and video sentiment analysis.

## References

  * Akbari et al. (2021) Hassan Akbari, Liangzhe Yuan, Rui Qian, Wei-Hong Chuang, Shih-Fu Chang, Yin Cui, and Boqing Gong. 2021.  Vatt: Transformers for multimodal self-supervised learning from raw video, audio and text.  _Advances in Neural Information Processing Systems_ , 34.
  * Alayrac et al. (2022) Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katherine Millican, Malcolm Reynolds, et al. 2022.  Flamingo: a visual language model for few-shot learning.  In _Advances in Neural Information Processing Systems_.
  * Anderson et al. (2018) Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang. 2018.  Bottom-up and top-down attention for image captioning and visual question answering.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 6077–6086.
  * Antol et al. (2015) Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh. 2015.  Vqa: Visual question answering.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2425–2433.
  * Baevski et al. (2020) Alexei Baevski, Yuhao Zhou, Abdelrahman Mohamed, and Michael Auli. 2020.  wav2vec 2.0: A framework for self-supervised learning of speech representations.  _Advances in neural information processing systems_ , 33:12449–12460.
  * Bain et al. (2021) Max Bain, Arsha Nagrani, Gül Varol, and Andrew Zisserman. 2021.  Frozen in time: A joint video and image encoder for end-to-end retrieval.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 1728–1738.
  * Bao et al. (2022) Hangbo Bao, Li Dong, Songhao Piao, and Furu Wei. 2022.  BEit: BERT pre-training of image transformers.  In _International Conference on Learning Representations_.
  * Bao et al. (2020) Siqi Bao, Huang He, Fan Wang, Hua Wu, and Haifeng Wang. 2020.  Plato: Pre-trained dialogue generation model with discrete latent variable.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 85–96.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Changpinyo et al. (2019) Soravit Changpinyo, Bo Pang, Piyush Sharma, and Radu Soricut. 2019.  Decoupled box proposal and featurization with ultrafine-grained semantic labels improve image captioning and visual question answering.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 1468–1474.
  * Chen et al. (2022) Sanyuan Chen, Chengyi Wang, Zhengyang Chen, Yu Wu, Shujie Liu, Zhuo Chen, Jinyu Li, Naoyuki Kanda, Takuya Yoshioka, Xiong Xiao, et al. 2022.  Wavlm: Large-scale self-supervised pre-training for full stack speech processing.  _IEEE Journal of Selected Topics in Signal Processing_ , 16(6):1505–1518.
  * Chen et al. (2015) Xinlei Chen, Hao Fang, Tsung-Yi Lin, Ramakrishna Vedantam, Saurabh Gupta, Piotr Dollár, and C Lawrence Zitnick. 2015.  Microsoft coco captions: Data collection and evaluation server.  _arXiv preprint arXiv:1504.00325_.
  * Chen et al. (2020) Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu. 2020.  Uniter: Universal image-text representation learning.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XXX_ , pages 104–120. Springer.
  * Cho et al. (2021) Jaemin Cho, Jie Lei, Hao Tan, and Mohit Bansal. 2021.  Unifying vision-and-language tasks via text generation.  In _International Conference on Machine Learning_ , pages 1931–1942. PMLR.
  * 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.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186.
  * Gurari et al. (2019) Danna Gurari, Qing Li, Chi Lin, Yinan Zhao, Anhong Guo, Abigale Stangl, and Jeffrey P Bigham. 2019.  Vizwiz-priv: A dataset for recognizing the presence and purpose of private visual information in images taken by blind people.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 939–948.
  * Han et al. (2021) Wei Han, Hui Chen, Alexander Gelbukh, Amir Zadeh, Louis-philippe Morency, and Soujanya Poria. 2021.  Bi-bimodal modality fusion for correlation-controlled multimodal sentiment analysis.  In _Proceedings of the 2021 International Conference on Multimodal Interaction_ , pages 6–15.
  * Hasan et al. (2019) Md Kamrul Hasan, Wasifur Rahman, AmirAli Bagher Zadeh, Jianyuan Zhong, Md Iftekhar Tanveer, Louis-Philippe Morency, and Mohammed Ehsan Hoque. 2019.  Ur-funny: A multimodal language dataset for understanding humor.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 2046–2056.
  * Hazarika et al. (2020) Devamanyu Hazarika, Roger Zimmermann, and Soujanya Poria. 2020.  Misa: Modality-invariant and-specific representations for multimodal sentiment analysis.  In _Proceedings of the 28th ACM International Conference on Multimedia_ , pages 1122–1131.
  * He et al. (2022) Pengcheng He, Baolin Peng, Liyang Lu, Song Wang, Jie Mei, Yang Liu, Ruochen Xu, Hany Hassan Awadalla, Yu Shi, Chenguang Zhu, et al. 2022.  Z-code++: A pre-trained language model optimized for abstractive summarization.  _arXiv preprint arXiv:2208.09770_.
  * Huang et al. (2019) Lun Huang, Wenmin Wang, Jie Chen, and Xiao-Yong Wei. 2019.  Attention on attention for image captioning.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 4634–4643.
  * Huang et al. (2023) Shaohan Huang, Li Dong, Wenhui Wang, Yaru Hao, Saksham Singhal, Shuming Ma, Tengchao Lv, Lei Cui, Owais Khan Mohammed, Qiang Liu, et al. 2023.  Language is not all you need: Aligning perception with language models.  _arXiv preprint arXiv:2302.14045_.
  * Johnson et al. (2016) Justin Johnson, Andrej Karpathy, and Li Fei-Fei. 2016.  Densecap: Fully convolutional localization networks for dense captioning.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4565–4574.
  * Ju et al. (2019) Da Ju, Kurt Shuster, Y-Lan Boureau, and Jason Weston. 2019.  All-in-one image-grounded conversational agents.  _arXiv preprint arXiv:1912.12394_.
  * Karpathy and Fei-Fei (2015) Andrej Karpathy and Li Fei-Fei. 2015.  Deep visual-semantic alignments for generating image descriptions.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3128–3137.
  * Kim et al. (2018) Jin-Hwa Kim, Yongseok Choi, Sungeun Hong, Jaehyun Jun, and Byoung-Tak Zhang. 2018\.  Bilinear attention networks for vizwiz challenge.  In _Proceedings of the ECCV Workshop on VizWiz Grand challenge_.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880.
  * Li et al. (2022) Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi. 2022.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  In _International Conference on Machine Learning_ , pages 12888–12900. PMLR.
  * Li et al. (2019) Liunian Harold Li, Mark Yatskar, Da Yin, Cho-Jui Hsieh, and Kai-Wei Chang. 2019\.  Visualbert: A simple and performant baseline for vision and language.  _arXiv preprint arXiv:1908.03557_.
  * Li et al. (2020) Liunian Harold Li, Mark Yatskar, Da Yin, Cho-Jui Hsieh, and Kai-Wei Chang. 2020\.  What does bert with vision look at?  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 5265–5275.
  * Liang et al. (2021) Paul Pu Liang, Yiwei Lyu, Xiang Fan, Zetian Wu, Yun Cheng, Jason Wu, Leslie Yufan Chen, Peter Wu, Michelle A Lee, Yuke Zhu, et al. 2021.  Multibench: Multiscale benchmarks for multimodal representation learning.  In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1)_.
  * Lin (2004) Chin-Yew Lin. 2004.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , pages 74–81.
  * Liu and Lapata (2019) Yang Liu and Mirella Lapata. 2019.  Text summarization with pretrained encoders.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3730–3740.
  * Liu et al. (2021) Yu Liu, Lianghua Huang, Liuyihang Song, Bin Wang, Yingya Zhang, and Pan Pan. 2021\.  Enhancing textual cues in multi-modal transformers for vqa.  In _2021 VizWiz Grand Challenge Workshop_.
  * Liu et al. (2018) Zhun Liu, Ying Shen, Varun Bharadhwaj Lakshminarasimhan, Paul Pu Liang, AmirAli Bagher Zadeh, and Louis-Philippe Morency. 2018.  Efficient low-rank multimodal fusion with modality-specific factors.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2247–2256.
  * Lu et al. (2022) Jiasen Lu, Christopher Clark, Rowan Zellers, Roozbeh Mottaghi, and Aniruddha Kembhavi. 2022.  Unified-io: A unified model for vision, language, and multi-modal tasks.  _arXiv preprint arXiv:2206.08916_.
  * Miech et al. (2019) Antoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makarand Tapaswi, Ivan Laptev, and Josef Sivic. 2019.  Howto100m: Learning a text-video embedding by watching hundred million narrated video clips.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 2630–2640.
  * OpenAI (2022) OpenAI. 2022.  Chatgpt: Optimizing language models for dialogue.  https://openai.com/blog/chatgpt/.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A fast, extensible toolkit for sequence modeling.  In _Proceedings of NAACL-HLT 2019: Demonstrations_.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Gray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. 2022.  Training language models to follow instructions with human feedback.  In _Advances in Neural Information Processing Systems_.
  * Panayotov et al. (2015) Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. 2015.  Librispeech: an asr corpus based on public domain audio books.  In _2015 IEEE international conference on acoustics, speech and signal processing (ICASSP)_ , pages 5206–5210. IEEE.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021.  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ , pages 8748–8763. PMLR.
  * Radford et al. (2022) Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. 2022.  Robust speech recognition via large-scale weak supervision.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Raffel et al. (2020) Colin Raffel, Noam 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.  _Journal of Machine Learning Research_ , 21(140):1–67.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  Squad: 100,000+ questions for machine comprehension of text.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 2383–2392.
  * Ramesh et al. (2022) Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. 2022.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_.
  * Ramesh et al. (2021) Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. 2021.  Zero-shot text-to-image generation.  In _International Conference on Machine Learning_ , pages 8821–8831. PMLR.
  * Roller et al. (2020) Stephen Roller, Emily Dinan, Naman Goyal, Da Ju, Mary Williamson, Yinhan Liu, Jing Xu, Myle Ott, Kurt Shuster, Eric M Smith, et al. 2020.  Recipes for building an open-domain chatbot.  _arXiv preprint arXiv:2004.13637_.
  * Rombach et al. (2022) Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. 2022.  High-resolution image synthesis with latent diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10684–10695.
  * Saharia et al. (2022) Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Raphael Gontijo-Lopes, Burcu Karagol Ayan, Tim Salimans, Jonathan Ho, David J. Fleet, and Mohammad Norouzi. 2022.  Photorealistic text-to-image diffusion models with deep language understanding.  In _Advances in Neural Information Processing Systems_.
  * Schuhmann et al. (2022) Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade W Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, Patrick Schramowski, Srivatsa R Kundurthy, Katherine Crowson, Ludwig Schmidt, Robert Kaczmarczyk, and Jenia Jitsev. 2022.  LAION-5b: An open large-scale dataset for training next generation image-text models.  In _Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track_.
  * See et al. (2017) Abigail See, Peter J. Liu, and Christopher D. Manning. 2017.  Get to the point: Summarization with pointer-generator networks.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1073–1083, Vancouver, Canada. Association for Computational Linguistics.
  * Shon et al. (2022) Suwon Shon, Ankita Pasad, Felix Wu, Pablo Brusco, Yoav Artzi, Karen Livescu, and Kyu J Han. 2022.  Slue: New benchmark tasks for spoken language understanding evaluation on natural speech.  In _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 7927–7931. IEEE.
  * Shuster et al. (2020) Kurt Shuster, Samuel Humeau, Antoine Bordes, and Jason Weston. 2020.  Image-chat: Engaging grounded conversations.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2414–2429.
  * Shuster et al. (2021) Kurt Shuster, Eric Michael Smith, Da Ju, and Jason Weston. 2021.  Multi-modal open-domain dialogue.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 4863–4883.
  * Su et al. (2020) Weijie Su, Xizhou Zhu, Yue Cao, Bin Li, Lewei Lu, Furu Wei, and Jifeng Dai. 2020\.  Vl-bert: Pre-training of generic visual-linguistic representations.  In _International Conference on Learning Representations_.
  * Tan and Bansal (2019) Hao Tan and Mohit Bansal. 2019.  Lxmert: Learning cross-modality encoder representations from transformers.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 5100–5111.
  * Tang et al. (2022) Zineng Tang, Ziyi Yang, Guoxin Wang, Yuwei Fang, Yang Liu, Chenguang Zhu, Michael Zeng, Cha Zhang, and Mohit Bansal. 2022.  Unifying vision, text, and layout for universal document processing.  _arXiv preprint arXiv:2212.02623_.
  * Tsai et al. (2019) Yao-Hung Hubert Tsai, Shaojie Bai, Paul Pu Liang, J Zico Kolter, Louis-Philippe Morency, and Ruslan Salakhutdinov. 2019.  Multimodal transformer for unaligned multimodal language sequences.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 6558–6569.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * Wang et al. (2021) Changhan Wang, Wei-Ning Hsu, Yossi Adi, Adam Polyak, Ann Lee, Peng-Jen Chen, Jiatao Gu, and Juan Pino. 2021.  fairseq sˆ2: A scalable and integrable speech synthesis toolkit.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 143–152.
  * Wang et al. (2022a) Jianfeng Wang, Zhengyuan Yang, Xiaowei Hu, Linjie Li, Kevin Lin, Zhe Gan, Zicheng Liu, Ce Liu, and Lijuan Wang. 2022a.  GIT: A generative image-to-text transformer for vision and language.  _Transactions on Machine Learning Research_.
  * Wang et al. (2022b) Junke Wang, Dongdong Chen, Zuxuan Wu, Chong Luo, Luowei Zhou, Yucheng Zhao, Yujia Xie, Ce Liu, Yu-Gang Jiang, and Lu Yuan. 2022b.  OmniVL: One foundation model for image-language and video-language tasks.  In _Advances in Neural Information Processing Systems_.
  * Wang et al. (2022c) Peng Wang, An Yang, Rui Men, Junyang Lin, Shuai Bai, Zhikang Li, Jianxin Ma, Chang Zhou, Jingren Zhou, and Hongxia Yang. 2022c.  Ofa: Unifying architectures, tasks, and modalities through a simple sequence-to-sequence learning framework.  In _International Conference on Machine Learning_ , pages 23318–23340. PMLR.
  * Wang et al. (2022d) Wenhui Wang, Hangbo Bao, Li Dong, Johan Bjorck, Zhiliang Peng, Qiang Liu, Kriti Aggarwal, Owais Khan Mohammed, Saksham Singhal, Subhojit Som, et al. 2022d.  Image as a foreign language: Beit pretraining for all vision and vision-language tasks.  _arXiv preprint arXiv:2208.10442_.
  * Wang et al. (2022e) Zirui Wang, Jiahui Yu, Adams Wei Yu, Zihang Dai, Yulia Tsvetkov, and Yuan Cao. 2022e.  SimVLM: Simple visual language model pretraining with weak supervision.  In _International Conference on Learning Representations_.
  * Wu et al. (2016) Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. 2016.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _arXiv preprint arXiv:1609.08144_.
  * Xia et al. (2021) Qiaolin Xia, Haoyang Huang, Nan Duan, Dongdong Zhang, Lei Ji, Zhifang Sui, Edward Cui, Taroon Bharti, and Ming Zhou. 2021.  Xgpt: Cross-modal generative pre-training for image captioning.  In _Natural Language Processing and Chinese Computing: 10th CCF International Conference, NLPCC 2021, Qingdao, China, October 13–17, 2021, Proceedings, Part I 10_ , pages 786–797. Springer.
  * Xu et al. (2022) Xiao Xu, Chenfei Wu, Shachar Rosenman, Vasudev Lal, and Nan Duan. 2022.  Bridge-tower: Building bridges between encoders in vision-language representation learning.  _arXiv preprint arXiv:2206.08657_.
  * Yang et al. (2022) Zhengyuan Yang, Zhe Gan, Jianfeng Wang, Xiaowei Hu, Faisal Ahmed, Zicheng Liu, Yumao Lu, and Lijuan Wang. 2022.  Unitab: Unifying text and box outputs for grounded vision-language modeling.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXXVI_ , pages 521–539. Springer.
  * Yang et al. (2018) Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D Manning. 2018.  Hotpotqa: A dataset for diverse, explainable multi-hop question answering.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2369–2380.
  * Yang et al. (2023) Ziyi Yang, Yuwei Fang, Chenguang Zhu, Reid Pryzant, Dongdong Chen, Yu Shi, Yichong Xu, Yao Qian, Mei Gao, Yi-Ling Chen, et al. 2023.  i-code: An integrative and composable multimodal learning framework.  _Proceedings of the AAAI Conference on Artificial Intelligence_.
  * Yang et al. (2020) Ziyi Yang, Chenguang Zhu, Robert Gmyr, Michael Zeng, Xuedong Huang, and Eric Darve. 2020.  Ted: A pretrained unsupervised summarization model with theme modeling and denoising.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1865–1874.
  * Yu and Deng (2016) Dong Yu and Li Deng. 2016.  _Automatic speech recognition_ , volume 1.  Springer.
  * Yu et al. (2022) Jiahui Yu, Zirui Wang, Vijay Vasudevan, Legg Yeung, Mojtaba Seyedhosseini, and Yonghui Wu. 2022.  Coca: Contrastive captioners are image-text foundation models.  _Transactions on Machine Learning Research_ , Aug 2022.
  * Yuan et al. (2021) Lu Yuan, Dongdong Chen, Yi-Ling Chen, Noel Codella, Xiyang Dai, Jianfeng Gao, Houdong Hu, Xuedong Huang, Boxin Li, Chunyuan Li, et al. 2021.  Florence: A new foundation model for computer vision.  _arXiv preprint arXiv:2111.11432_.
  * Zadeh et al. (2017) Amir Zadeh, Minghai Chen, Soujanya Poria, Erik Cambria, and Louis-Philippe Morency. 2017.  Tensor fusion network for multimodal sentiment analysis.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 1103–1114.
  * Zadeh et al. (2018) AmirAli Bagher Zadeh, Paul Pu Liang, Soujanya Poria, Erik Cambria, and Louis-Philippe Morency. 2018.  Multimodal language analysis in the wild: Cmu-mosei dataset and interpretable dynamic fusion graph.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2236–2246.
  * Zellers et al. (2022a) Rowan Zellers, Jiasen Lu, Ximing Lu, Youngjae Yu, Yanpeng Zhao, Mohammadreza Salehi, Aditya Kusupati, Jack Hessel, Ali Farhadi, and Yejin Choi. 2022a.  Merlot reserve: Neural script knowledge through vision and language and sound.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 16375–16387.
  * Zellers et al. (2022b) Rowan Zellers, Jiasen Lu, Ximing Lu, Youngjae Yu, Yanpeng Zhao, Mohammadreza Salehi, Aditya Kusupati, Jack Hessel, Ali Farhadi, and Yejin Choi. 2022b.  Merlot reserve: Neural script knowledge through vision and language and sound.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 16375–16387.
  * Zhang et al. (2020) Jingqing Zhang, Yao Zhao, Mohammad Saleh, and Peter Liu. 2020.  Pegasus: Pre-training with extracted gap-sentences for abstractive summarization.  In _International Conference on Machine Learning_ , pages 11328–11339. PMLR.
  * Zhang et al. (2019) Yizhe Zhang, Siqi Sun, Michel Galley, Yen-Chun Chen, Chris Brockett, Xiang Gao, Jianfeng Gao, Jingjing Liu, and Bill Dolan. 2019.  Dialogpt: Large-scale generative pre-training for conversational response generation.  _arXiv preprint arXiv:1911.00536_.
  * Zhang et al. (2022) Zhengkun Zhang, Xiaojun Meng, Yasheng Wang, Xin Jiang, Qun Liu, and Zhenglu Yang. 2022.  Unims: A unified framework for multimodal summarization with knowledge distillation.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 36(10):11757–11764.
  * Zhao et al. (2020) Xueliang Zhao, Wei Wu, Can Xu, Chongyang Tao, Dongyan Zhao, and Rui Yan. 2020.  Knowledge-grounded dialogue generation with pre-trained language models.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 3377–3390.
  * Zhu et al. (2018) Junnan Zhu, Haoran Li, Tianshang Liu, Yu Zhou, Jiajun Zhang, and Chengqing Zong. 2018.  Msmo: Multimodal summarization with multimodal output.  In _Proceedings of the 2018 conference on empirical methods in natural language processing_ , pages 4154–4164.
  * Zhu et al. (2020) Junnan Zhu, Yu Zhou, Jiajun Zhang, Haoran Li, Chengqing Zong, and Changliang Li. 2020.  Multimodal summarization with guidance of multimodal reference.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 9749–9756.
  * Zhu et al. (2015) Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. 2015.  Aligning books and movies: Towards story-like visual explanations by watching movies and reading books.  In _Proceedings of the IEEE international conference on computer vision_ , pages 19–27.