# Independence Properties of Generalized Submodular Information Measures

Himanshu Asnani  School of Technology and Computer Science
TIFR, Mumbai
Email<EMAIL_ADDRESS>Jeff Bilmes  Department of ECE
University of Washington, Seattle
Email<EMAIL_ADDRESS>Rishabh Iyer  Department of Computer Science
University of Texas, Dallas
Email<EMAIL_ADDRESS>
###### Abstract

Recently a class of generalized information measures was defined on sets of
items parametrized by submodular functions [7]. In this paper, we propose and
study various notions of independence between sets with respect to such
information measures, and connections thereof. Since entropy can also be used
to parametrize such measures, we derive interesting independence properties
for the entropy of sets of random variables. We also study the notion of
multi-set independence and its properties. Finally, we present optimization
algorithms for obtaining a set that is independent of another given set, and
also discuss the implications and applications of combinatorial independence.

##  I Introduction

In this paper, we consider the recently proposed class of submodular
information measures [7], and study general combinatorial independence
characterizations admitted by them. A set function
$f:2^{V}\rightarrow\mathbf{R}$ over a finite set $V=\\{1,2,\ldots,n\\}$ is
_submodular_ [3] if for all subsets $S,T\subseteq V$, it holds that
$f(S)+f(T)\geq f(S\cup T)+f(S\cap T)$. Given a set $S\subseteq V$, we define
the _gain_ of an element $j\notin S$ in the context $S$ as $f(j|S)=f(S\cup
j)-f(S)$. A perhaps more intuitive characterization of submodularity is as
follows: a function $f$ is submodular if it satisfies _diminishing marginal
returns_ , namely $f(j|S)\geq f(j|T)$ for all $S\subseteq T,j\notin T$, and is
_monotone_ if $f(j|S)\geq 0$ for all $j\notin S,S\subseteq V$. Submodular
functions are a rich and expressive class of models which capture a number of
important aspects like coverage (e.g. set cover function), representation
(e.g. facility location function), diversity (e.g. log-determinants), and
information (e.g. joint entropy of a set of random variables). Submodular
functions have been shown to be closely connected with convexity [14, 2], and
concavity [5].

Given a submodular function $f$, we can define the submodular (conditional)
mutual information $I_{f}(A;B|C)$ as:

$\displaystyle I_{f}(A;B|C)=f(A|C)+f(B|C)-f(A\cup B|C)$ (1)

where the conditional information $f(A|C)=f(A\cup C)-f(C)$. Recently, [7, 4]
studied several important and interesting properties of $I_{f}$ such as non-
negativity, monotonicity, conditions for submodularity, and upper/lower
bounds. Furthermore, [7] also studied multi-set extensions of the submodular
mutual information to capture joint information between $k$ sets. As argued by
[7, 4], the submodular mutual information (or multi-set mutual information)
effectively captures the _shared_ information between two sets (or multiple
sets), from the lens of the submodular function $f$. [7] also study a number
of examples of $I_{f}$, and the modeling capabilities of these in various
machine learning applications such as query focused and privacy preserving
summarization, clustering and disparate partitioning.

In this work, we extend the paradigm of combinatorial information measures to
study the concept of independence among sets. In particular, we first
introduce six notions of (conditional) independence between subsets in Section
II. Next, in Section III, we study the relationship between the independence
types for general submodular functions, and then study these connections for a
few special cases, including set cover functions, modular functions, and
Entropy. We then study independence between multiple sets (Section IV), and
then present optimization algorithms for obtaining a set $A$ which is
independent of a given set $B$ (Section V), and also discuss the implications
and applications of this study. While the main focus of this work is
combinatorial independence, we note that our results in the special case of
Entropy function (specifically Lemma 3.3), is one of the first (to our
knowledge) which studies the different possible types of independence between
sets of random variables. We provide proofs of our results in Section VI, and
conclude this paper in Section VII.

##  II Submodular (Conditional) Independence:

Two random variables $X$ and $Y$ are statistically independent iff the mutual
information $I(X;Y)=0$. Since we are studying sets of variables (rather than
two random variables), the notion of independence becomes a little more
intricate. Consequently, we define six types of combinatorial (or submodular)
independence relations between two sets $A,B\subseteq\Omega$ with respect to a
submodular function $f$. These relations also hold in the entropic case, in
which case it is exactly the statistical independence between two sets of
random variables. Before going into defining the different independence types,
we provide some definitions.

A function $f$ is said to satisfy the condition $\mathcal{M}(S_{1},S_{2})$
(for any $S_{1},S_{2}\subseteq\Omega$), if $f(\\{j\\}|X)=f(\\{j\\})$, $\forall
j\in S_{1}\backslash X$ and $X\subseteq S_{2}$. This condition implies that
the function $f$ is modular with respect to the addition of any element from
$S_{1}$ to any subset of $S_{2}$ not containing the specific element. This
notation is introduced to draw attention towards implications of the
difference amongst the definitions of the independence types. Below, we define
the six types of independence conditions.

  1. 1.

Joint Independence ($JI$): We say set $A$ is jointly independent of another
set $B$, or $A\perp_{J}B$ with respect to $f$ if $I_{f}(A;B)=0$ or
equivalently: $f(A|B)=f(A)$ (or $f(B|A)=f(B)$).

  2. 2.

Marginal Independence ($MI$): We say set $A$ is marginally independent with
another set $B$, or $A\perp_{M}B$ with respect to $f$ if
$f(\\{a\\}|B)=f(\\{a\\})\;\forall a\in A$ and
$f(\\{b\\}|A)=f(\\{b\\})\;\forall b\in B$. In other words, $A\perp_{M}B$ if
$a\perp_{J}B,\forall a\in A$ and $b\perp_{J}A,\forall b\in B$

  3. 3.

Pairwise Independence ($PI$): Set $A$ is pairwise independent of another set
$B$, or $A\perp_{P}B$ with respect to $f$ if $\forall a\in A,b\in
B,\;f(\\{a\\}|\\{b\\})=f(\\{a\\})$ and $f(\\{b\\}|\\{a\\})=f(\\{b\\})$. In
other words, $A\perp_{P}B$ if $a\perp_{J}b,\forall a\in A,b\in B$.

  4. 4.

Subset Marginal Independence ($SMI$): We say set $A$ holds subset marginal
independence with another set $B$, or $A\perp_{SM}B$ with respect to $f$ if
$f(\\{a\\}|X)=f(\\{a\\})$, $\forall a\in A,X\subseteq B$ and
$f(\\{b\\}|X)=f(\\{b\\})$, $\forall b\in B,X\subseteq A$. In other words,
$A\perp_{SM}B$ if $a\perp_{J}X,\forall a\in A,X\subseteq B$ and
$b\perp_{J}X,\forall b\in B,X\subseteq A$. Observe that SMI generalizes MI and
PI.

  5. 5.

Modular Independence ($ModI$): Set $A$ holds modular independence with another
set $B$, or $A\perp_{Mod}B$ with respect to $f$ if
$f(\\{j\\}|X)=f(\\{j\\})\;\forall j\in A\cup B\setminus X$ where $X\subseteq
A\cup B$. Thus, $f$ satisfies the condition $\mathcal{M}(A\cup B,A\cup B)$.

  6. 6.

Subset Modular Independence ($SModI$): Set $A$ is said to be subset modular
independent of $B$ or $A\perp_{S-Mod}B$ with respect to $f$ if
$f(\\{j\\}|X)=f(\\{j\\})\;\forall j\in A\cup B\setminus X$ where $X\subseteq
A$ or $X\subseteq B$. Thus, $f$ satisfies both the conditions
$\mathcal{M}(A,A\cup B)$ and $\mathcal{M}(B,A\cup B)$

Unless specified, we will use joint independence as the default notion of
independence. We also assume that $A$ and $B$ are disjoint without a loss of
generality – since joint independence implies $f(A\cap B)=0$ and since $f$ is
assumed to be monotone, this essentially means that we can remove the elements
in $A\cap B$ from the ground set $\Omega$ without letting them affect the
functional values.

Similar to independence, we also define conditional combinatorial independence
between two sets $A$ and $C$ given a third set $B$. We say that $A,C$ are
conditionally independent of each other given $B$, in the context of $f$, and
denoted by $A\perp_{f}C\;|\;B$ iff $I_{f}(A;C|B)=0$. An equivalent way of
viewing this is in terms of the submodular mutual information:
$A\perp_{f}C\;|\;B$ iff $I_{f}(A;B\cup C)=I_{f}(A;B)$ and $I_{f}(C;A\cup
B)=I_{f}(C;B)$. In terms of the conditional gains, it implies that
$f(C|B)=f(C|A\cup B)$ and $f(A|B)=f(A|B\cup C)$. Similar to independence, we
can also define the six types of conditional independence.

##  III Connections between Independence Types

We start this section by providing a relationship between the different types
of (conditional) independences. Figure 1 illustrates the containment
relationship between the different types of (conditional) independence.

Figure 1: An illustration of the independence relation classes

Also, note that we prove the relationships only for the independence case and
note that since conditional independence $I_{f}(A;B|C)$ with $f$ is equivalent
to independence with $g(A)=f(A|C)$ for fixed given C, the conditions below
also hold for the six types of conditional independence.

######  Theorem III.1.

The following relations hold between the different types of independence
defined in the previous section. We use $JI,MI,\dots,SModI$ to denote the
different types compactly.

$\displaystyle ModI\implies JI\implies MI\iff SMI\implies PI\;$ (2)
$\displaystyle\text{and}\;ModI\implies SModI\implies MI$ (3)

Moreover, there exists submodular functions where $JI\centernot\implies ModI$,
$SModI\centernot\implies ModI$, $JI\centernot\implies SModI$,
$SModI\centernot\implies JI$, $MI\centernot\implies SModI$,
$MI\centernot\implies JI$, $PI\centernot\implies MI$.

Thus we can see that there is a certain hierarchy attached to the independence
types in general which is illustrated in Fig. 1.

###  III-A Relationship between the Independence Types for the Modular and Set
Cover Function

For the special case when $f$ is a modular function, all the six independence
types are equivalent i.e reverse implications also hold and in fact, this
follows from the very definition of a modular function. Next we show that for
the Set Cover function the first four types are indeed equivalent.

######  Lemma III.2.

When $f$ is a Set Cover function the relation shown in Theorem III.1 is not
tight. In fact we have that the reverse implications also hold among the first
four types, which makes them in essence equivalent to one another:
$ModI\implies JI\iff MI\iff SMI\iff PI$. However, $JI\centernot\implies ModI$.

###  III-B Relationship between the Independence Types for the Entropy
Function

As we have noted earlier, Entropy function is generalized by our framework.
This is done via defining the universal set of random variables
$\Omega=\\{X_{1},X_{2},\cdots,X_{k}\\}$ with the corresponding joint
probability distribution $\mathcal{P}_{\Omega}$ on the random variables. Thus
for $A\subseteq\Omega$ we have well defined submodular function, entropy
$H(A)=H(X_{A})$, where $X_{A}=\\{X_{a},a\in A\\}$. The usual celebrated notion
of independence is that of $H(A|B)=H(A)\iff
P_{X_{A},X_{B}}=P_{X_{A}}P_{X_{B}}$, or the set of random variables $X_{A}$
are independent of the set of random variables $X_{B}$. This is the $JI$
notion of independence as per our exposition on the different types of
independence. However with the above definitions of six types of independence
in the context of generalized submodular information, we have a richer set of
notions of independence and hierarchies thereof for the entropy function. The
lemma below further elaborates on the relations of different types of
independence for the entropy function.

######  Lemma III.3.

For the entropy function:

$\displaystyle ModI\implies JI\implies MI\iff SMI\implies PI\;$ (4)
$\displaystyle\text{and}\;ModI\implies SModI\implies MI$ (5)

Moreover, there exists tuple, $(\Omega,\mathcal{P}_{\Omega})$ where
$JI\centernot\implies ModI,\;SModI\centernot\implies
ModI,\;JI\centernot\implies SModI,\;SModI\centernot\implies
JI,\;MI\centernot\implies SModI,\;MI\centernot\implies
JI,\;PI\centernot\implies MI$,

###  III-C Miscellaneous Results

Next, we provide sufficient but not necessary conditions for submodular
(conditional) independence to hold.

######  Lemma III.4.

For a submodular $f$, $A\perp_{f}\emptyset$. Also, $A\perp_{f}C\;|\;B$ if
$A\subseteq B$ (and $C$ is any set) or $C\subseteq B$ (and $A$ is any set).
Moreover, $A\perp_{f}C\;|\;B\implies I_{f}(A;C)\leq I_{f}(A;B),I_{f}(A;C)\leq
I_{f}(C;B)$.

###### Proof.

We first prove that $A\perp_{f}\emptyset$. This follows from definition since
$I_{f}(A;\emptyset)=f(A)+f(\emptyset)-f(A)=0$ if $f$ is normalized. Next, if
$A\subseteq B$, $A\cup B=B$ and hence $f(C|B)=f(C|A\cup B)$. Similarly,
$f(A|B)=F(A|B\cup C)=0$ and hence $I_{f}(A;B|C)=0$. The same proof holds for
thye case if $C\subseteq B$.

Finally, we show that $I_{f}(A;C)\leq I_{f}(A;B)$ (the case of $I_{f}(A;C)\leq
I_{f}(C;B)$ follows from a symmetric argument). Recall that $I_{f}(A;C|B)=0$
implies that $I_{f}(A;B\cup C)=I_{f}(A;B)$. This implies that $I_{f}(A;C)\leq
I_{f}(A;B\cup C)=I_{f}(A;B)$. The first inequality follows from the
monotonicity of $I_{f}$ in one argument given the other. Hence proved. ∎

The last result in Lemma III.4 is similar to the classical data processing
inequality, but defined on sets of variables. Given that the sets $A\to B\to
C$ form a Markov chain111This is in the usual sense of Markovicity, that
knowing $B$, $A$ is fully determined irrespective of $C$ and so forth, it
implies that the conditional mutual information $I_{f}(A;C|B)=0$. Furthermore,
let $C=P(B)$ be a processing operator ($P:2^{\Omega}\to 2^{\Omega}$). If the
processing involves taking subsets $C\subseteq B$, this implies that
$I_{f}(A;C|B)=0$ (from Lemma III.4). For specific sub-classes of functions,
the processing can be more interesting. For example, in the case of set cover,
let $\gamma^{-1}$ be the inverse operator such that given a concept $u\in
U,\gamma^{-1}(u)\subseteq\Omega$ gives the subset of $\Omega$ such that
$\forall c\in\gamma^{-1}(u),u\in\gamma(c)$. Similarly, given a subset
$C_{U}\subseteq U$, we can define $\gamma^{-1}(C_{U})$. Then given sets
$A,B\subseteq\Omega$, let $B_{U}\subseteq\gamma(B)\subseteq U$ be any subset.
Then the sets $A\to B\to\gamma^{-1}(B_{U})$ form a Markov chain with the
property that $I_{f}(A;\gamma^{-1}(B_{U})|B)=0$.

Finally, we give some examples of properties which do not hold for
combinatorial independence.

######  Lemma III.5.

Suppose $A,B,C$ are subsets such that $A\perp_{f}B$ and $A\perp_{f}C$. This
does not however, imply that $A\perp_{f}B\cup C$.

###### Proof.

To see this, again, define $f(A)=\min(|A|,k)$ and let $|A|=|B|=|C|=k/2$ with
$A,B,C$ being mutually disjoint. Note that $A\perp_{f}B$ and $A\perp_{f}C$.
Lets study $I_{f}(A;B\cup C)=f(A)+f(B\cup C)-f(A\cup B\cup C)=3k/2-k=k/2>0$.
This means that $A$ is not jointly independent of $B\cup C$. This is a good
segway to the next subsection, which studies independence among $k$-sets. ∎

##  IV Multi-Set Submodular Independence

In this section, we first introduce multi-set submodular independence. In
particular, we introduce two concepts of independence among $k$ sets.

  * •

Sets $A_{1},\cdots,A_{k}$ are mutually independent iff
$f(\cup_{i}A_{i})=\sum_{i}f(A_{i})$.

  * •

Sets $A_{1},\cdots,A_{k}$ are pairwise independent iff
$A_{i}\perp_{J}A_{j},\forall i,j$.

Next, we study the connection between mutual and pairwise independence of sets
$A_{1},\cdots,A_{k}$. We first define the multi-set total correlation $C_{f}$
as [7]:

$\displaystyle
C_{f}(A_{1};\cdots;A_{k})=\sum_{i=1}^{k}f(A_{i})-f(\cup_{i=1}^{k}A_{i})$ (6)

Next, note that the mutual submodular independence between sets
$A_{1},\cdots,A_{k}$ means that $C_{f}(A_{1};\cdots;A_{k})=0$. On the other
hand, pairwise independendence implies that for all pairs,
$A_{i}\perp_{J}A_{j}$. Both types of independence are again, w.l.o.g. defined
on disjoint sets of items. The following result connects the two types of
independences.

######  Lemma IV.1.

Given a monotone, non-negative and normalized submodular function $f$, mutual
independence implies pairwise independence. However, pairwise independence
does not imply mutual independence.

###### Proof.

Lets prove that mutual independence implies pairwise independence. To prove
this, lets assume that sets $A_{1},\cdots,A_{k}$ are mutually independent, but
not pairwise independent. That is, there exist two sets which are not joint
independent. W.l.o.g, lets assume they are $A_{1},A_{2}$. In other words,
$f(A_{1}\cup A_{2})<f(A_{1})+f(A_{2})$. This implies (following from
submodularity):

$\displaystyle f(\cup_{i}A_{i})\leq f(A_{1}\cup
A_{2})+\sum_{i=3}^{k}f(\cup_{i}A_{i})$ (7)

Now invoking the assumption that $f(A_{1}\cup A_{2})<f(A_{1})+f(A_{2})$, this
means that:

$\displaystyle
f(\cup_{i}A_{i})<f(A_{1})+f(A_{2})+\sum_{i=3}^{k}f(\cup_{i}A_{i})$ (8)

which means that $f(\cup_{i}A_{i})<\sum_{i=1}^{k}f(\cup_{i}A_{i})$ which
contradicts mutual independence. Hence, given mutual independence, this must
imply pairwise independence. However, pairwise independence does not imply
mutual independence. We prove this with an example. Again, define
$f(A)=\min(|A|,c)$ and let $|A_{1}|=|A_{2}|=\cdots=|A_{k}|=c/2$ be mutually
disjoint sets. Note that all pairs $A_{i},A_{j}$ are pairwise independent.
However, they are not mutually independent since
$f(\cup_{i}A_{i})=c<\sum_{i}f(A_{i})=kc/2$ for $k>2$. ∎

Finally, we consider an alternative to mutual independence, which is
$I_{f}(A_{1};\cdots;A_{k})=0$ instead of $C_{f}(A_{1};\cdots;A_{k})=0$. Recall
that the multi-set mutual information $I_{f}$ is defined as:

$\displaystyle
I_{f}(A_{1};A_{2};\dots;A_{k})=-\sum_{T\subseteq[k]}(-1)^{|T|}f(\cup_{i\in
T}A_{i}).$ (9)

Note that $I_{f}$ and $C_{f}$ are _different_ quantities and they will in
general provide different conditions for the mutual independence between sets
$A_{1},\cdots,A_{k}$. However, the condition that the multi-set submodular
mutual information is zero is unfortunately not very interesting. To
understand this, we look at it via the example of the set cover function.

######  Example IV.1.

If $f(A)=\gamma(A)$, the multi-set submodular mutual information being zero is
equivalent to $\cap_{i=1}^{k}\gamma(A_{i})=\emptyset$. This is, however, not
very interesting since even if any two sets $A_{1}$ and $A_{2}$ are jointly
independent, they will satisfy $\gamma(A_{1})\cap\gamma(A_{2})=\emptyset$ and
hence it will hold that $\cap_{i=1}^{k}\gamma(A_{i})=\emptyset$. This means
that even if only two sets are mutually independent, but the rest of the sets
are completely dependent (or even identical), the multi-set submodular mutual
information will still be zero.

##  V The Utility of Independence Characterizations

Here, we present some discussion on the applications and utility of our
formulations. In several data subset selection applications (e.g. video/image
collection summarization [10, 11, 16], data selection for efficient training
[17, 13, 12], and active learning [1, 13, 17], submodular functions have been
shown to be a natural fit. In particular, many of these problems involve
optimizing a submodular function under constraints, such as cardinality,
knapsack, and matroid constraints [9, 15].

Submodular Independence discussed in this work, can be viewed as a new class
of combinatorial constraints, and we will refer to this constraint as
$A\perp_{f}P$. In particular, we can then consider optimization problem as:

$\displaystyle\max_{A\subseteq V}g(A),\mbox{s.t. }A\perp_{f}P$ (10)

for a given set $P$. This has several natural applications. The first is
privacy preserving summarization [10, 11] where we want to select a subset $A$
which is as different as possible from set $P$ (and this difference is
measured with respect to the submodular function). For instance this private
set could be of one’s personal picture collection or medical data, or could be
images of one’s family. The independence equates to lack of discernment of any
information contained in $P$ by knowing $A$. If the independence considered
here is JI, then this is equivalent to $I_{f}(A;P)=0$, which we can
equivalently relax to $I_{f}(A;P)\leq\epsilon$ for a very small $\epsilon$. We
can also consider the different types of independence here since the
constraint $I_{f}(A;P)\leq\epsilon$ may not be amenable to tractable
optimization algorithms when $I_{f}(A;P)$ is not submodular in A for a fixed
$P$ (which is true for several important classes of submodular functions). In
such cases, we can relax this to SMI or MI instead of JI, which requires that
$I_{f}(a;P)=0,\forall a\in A$ and $I_{f}(A;p)=0.\forall p\in P.$

If $f$ is second-order supermodular [7], then the problem of maximizing $g(A)$
subject to a constraint that $I_{f}(A;P)\leq\epsilon$ is an instance of SCSK
[8, 6] which admits bounded approximation guarantees. For general $f$ though,
achieving such a set could be NP hard. On the other hand, the independence
characterizations for MI (equivalently SMI) and PI are much easier. In
particular, for MI, we just need to find elements $a\in A$ such that
$f(a|B)=0$. Similarly, for PI, we find elements $a\in A$ such that
$f(a|b)=0,\forall b\in B$.

##  VI Proofs of Results in Section III

Proof of Theorem III.1.

###### Proof.

We start with $JI\implies MI$. $JI$ implies that $f(A|B)=f(A)$. Let
$A=\\{a_{1},\cdots,a_{k}\\}$ be the elements in $A$, and define a chain of
sets corresponding to the above ordering as $A=C_{0}\subseteq
C_{1}\subseteq\cdots\subseteq C_{k}=A\cup B$. The set
$C_{i}=A\cup\\{a_{1},\cdots,a_{i}\\}$. Similarly, consider the chain of sets
$\emptyset=D_{0}\subseteq D_{1}\subseteq\cdots\subseteq D_{k}=A$ with
$D_{i}=\\{a_{1},\cdots,a_{i}\\}$. Then note that
$f(A|B)=\sum_{i=1}^{k}f(a_{i}|C_{i-1})$ and
$f(A)=\sum_{i=1}^{k}f(a_{i}|D_{i-1})$. Since $f(A|B)=f(A)$, this implies that
$\sum_{i=1}^{k}f(a_{i}|C_{i-1})=\sum_{i=1}^{k}f(a_{i}|D_{i-1})$ . Note that
$\sum_{i=1}^{k}f(a_{i}|C_{i-1})\leq\sum_{i=1}^{k}f(a_{i}|D_{i-1}),\forall i$
and hence this implies that for each $i$, $f(a_{i}|C_{i-1})=f(a_{i}|D_{i-1})$.
Setting $i=1$, we have $f(a_{i}|B)=f(a_{i})$. Note that since the order
$a_{1},\cdots,a_{k}$ can be arbitrary, we have $f(a|B)=f(a),\forall a\in A$.

Next, we show that $MI\iff SMI$. For this, first observe that $MI\implies SMI$
by submodularity. From $MI$ we have, $f(\\{a\\}|B)=f(\\{a\\})\;\forall a\in A$
and $f(\\{b\\}|A)=f(\\{b\\})\;\forall b\in B$. Also with submodularity we
have: $f(\\{a\\}|B)\leq f(\\{a\\}|X)\leq f(\\{a\\})\;\forall X\subseteq B,a\in
A$. But $f(\\{a\\}|B)=f(\\{a\\})\implies f(\\{a\\}|X)=f(\\{a\\})$. Similar
proof works for showing the other case with $B$. For $SMI\implies MI$, we can
just use $X=B$ (since we trivially have $B\subseteq B$). Similarly for the
other case, use $X=A$.

We have $SMI\implies PI$ by just substituting in the singleton set as:
$X=\\{b\\},\;(b\in B)$ in $PI$ and it follows through trivially since
$\\{b\\}\subseteq B\;\forall b\in B$. Similarly we can also substitute
$X=\\{a\\},\;(a\in A)$ for showing the other case.

For $ModI\implies JI$, recall that $ModI$ implies that $f(j|X)=f(j),\forall
X\subseteq A\cup B$ and$j\notin A\cup B\backslash X$. Let
$A=\\{a_{1},a_{2},...,a_{k}\\}$ and $B=\\{b_{1},b_{2},...,b_{k}\\}$.
Furthermore, define $A_{l}=\\{a_{1},\cdots,a_{l}\\},l\leq k$ and
$B_{l}=\\{b_{1},\cdots,b_{l}\\},l\leq k$. Then,
$f(A)=\sum_{i=1}^{k}f(a_{i}|A_{i-1})=\sum_{i=1}^{k}f(a_{i})=\sum_{j\in
A}f(A)$. Similarly we obtain $f(B)=\sum_{j\in B}f(j),f(A\cup B)=\sum_{j\in
A\cup B}f(i)$ and clearly, this satisfies $f(A)+f(B)=f(A\cup B)$ when $A$ and
$B$ are disjoint. This shows that $ModI\implies JI\implies MI\iff SMI\implies
PI$.

We then show $SModI\implies MI$. $SModI$ implies $f(j|X)=f(j),\forall j\in
A\cup B\backslash X$ and $X\subseteq A$ or $X\subseteq B$. Setting $X=A$ and
$X=B$, we get $T2$. Also, $ModI\implies SModI$ since $SModI$ only requires
$X\subseteq A$ and $X\subseteq B$ while $ModI$ requires $X\subseteq A\cup B$.
Finally, we show the reverse implications do not hold with examples. We start
with $JI\centernot\implies ModI$. Let $f(A)=|\gamma(A)|$ and $A,B$ be sets
such that $\gamma(A)\cap\gamma(B)=\emptyset$. Concretely, let
$\Omega=\\{1,2,3\\}$,
$\gamma(1)=\\{c_{1},c_{2}\\},\gamma(2)=\\{c_{1}\\},\gamma(3)=\\{c_{3}\\}$, and
$A=\\{1,2\\},B=\\{3\\}$. Note that sets $A$ and $B$ are $JI$ independent since
$f(A\cup B)=3=f(A)+f(B)$. However, it is not $ModI$ independent since let
$X=\\{1\\}$, then $f(\\{2\\}|X)=0\neq f(\\{2\\})=1$.

Next, we show that $SModI\centernot\implies ModI$. Let $f(A)=\min(|A|,k)$ with
$A$ and $B$ being disjoint sets of size $k-1$. Then, $A$ and $B$ are
$SModI$-independent since for all $X\subseteq A$ or $B$, $f(j|X)=f(j)$ (the
function is modular if we only add a single element). However, they are not
$ModI$ independent since we can set $X=A\cup\\{b_{1}\\}$ for a specific
$\\{b_{1}\\}\in B$, and then selecting a $j\neq b_{1}\in B$, we have that
$f(j|X)=0\neq f(j)$. We then show that $JI\centernot\implies SModI$ and
$SModI\centernot\implies JI$. To show $JI\centernot\implies SModI$, we use the
set-cover function used earlier. The specific sets $A$ and $B$ are $JI$
independent however they are not $SModI$ independent since let
$X=\\{1\\}\subseteq A$ and $j=\\{2\\}$. Then $f(\\{2\\}|\\{1\\})=0\neq
f(\\{2\\}=1$. To show that $SModI\centernot\implies JI$, again use the matroid
rank function $f(A)=\min(|A|,k)$ with $A$ and $B$ being disjoint sets of size
$k-1$. Notice that $A$ and $B$ are $SModI$ independent. However, $f(A\cup
B)=k\neq f(A)+f(B)=2(k-2)$ and hence they are $JI$ independent.

Next, we show that $MI\centernot\implies SModI$ and $MI\centernot\implies JI$.
$MI\centernot\implies SModI$ follows since $JI\implies MI$ and
$JI\centernot\implies SModI$. Hence there exists a $f$, and sets $A,B$ which
are $JI$ independent (and hence $MI$ independent) but not $SModI$ independent.
Similarly, $MI\centernot\implies JI$ follows since $SModI\implies MI$ and
$SModI\centernot\implies JI$. Finally, we show that $PI\centernot\implies MI$.
Again, let $f(A)=\min\\{|A|,2\\}$ with $|A|=|B|=4$ and $A\cap B=\emptyset$.
Note that every pair of elements $i\in A,j\in B$ satisfy
$f(\\{1,j\\})=2=f(\\{i\\}+f(\\{j\\})$. However, $f(j|A)=0\neq f(j)=1,\forall
j\in B$. Hence $A$ and $B$ are not $MI$ independent. ∎

Proof of Lemma III.2.

###### Proof.

To prove this, we show that $JI\iff PI$. We know that $A\perp_{f}B$ (when
$f(A)=w(\gamma(A))$) iff $\gamma(A)\cap\gamma(B)=\emptyset$. Similarly,
$A\perp_{f}B$ with $PI$ if for every $a\in A,b\in
B,\gamma(a)\cap\gamma(b)=\emptyset$. Note that this condition then also
implies $\gamma(A)\cap\gamma(B)=\emptyset$ and hence $PI\implies JI$ which
proves the equivalence. Since $JI\iff PI$, this means that all the four types
are equivalent. Finally, $JI\centernot\implies ModI$ since the proof of
Theorem III.1 uses an instance of set cover to show that $JI\centernot\implies
ModI$. ∎

Proof of Lemma III.3.

###### Proof.

Since entropy is a submodular function, the following holds from the proof of
Lemma III.1.

$\displaystyle ModI\implies JI\implies MI\iff SMI\implies PI\;$ (11)
$\displaystyle\text{and}\;ModI\implies SModI\implies MI$ (12)

Next, we show that reverse implications do not hold. We start with
$JI\centernot\implies ModI$. Consider $\Omega={X_{1},X_{2},X_{3}}$ with the
joint distribution satisfying
$P_{X_{1},X_{2},X_{3}}=P_{X_{1},X_{2}}P_{X_{3}}$. For an example, let
$X_{1},X_{2},X_{3}$ be three binary random variables (taking values in
$\\{0,1\\}$) such that $X_{1},X_{2}$ are jointly distributed as
$P_{X_{1},X_{2}}(1,0)=P_{X_{1},X_{2}}(0,1)=\frac{1}{8},\;P_{X_{1},X_{2}}(0,0)=\frac{1}{4},\;P_{X_{1},X_{2}}(1,1)=\frac{1}{2}$,
and we have $X_{3}\sim\text{Bern}(\frac{1}{2})$. Take $A=\\{1,2\\},\
B=\\{3\\},\ X=\\{2\\},j=\\{1\\}$. Since the pair $X_{1},X_{2}$ are independent
of $X_{3}$, we have $H(A|B)=H(A)$ and $H(B|A)=H(A)$, i.e., they are $JI$
independent but we have $H(j|X)\neq H(j)$, implying A and B are not $ModI$
independent.

For showing $JI\centernot\implies SModI$ we consider the same example as above
with $P_{X_{1},X_{2},X_{3}}=P_{X_{1},X_{2}}P_{X_{3}}$ and let $A=\\{1,2\\},\
B=\\{3\\},\ X=\\{2\\},j=\\{1\\}$. $A$ and $B$ are $JI$ independent as shown
above. However, this would not imply necessarily $SModI$ independence
criterion which needs here pairwise independence between all the variables and
that $H(X_{3}|X_{1},X_{2})=H(X_{2})$.

Next, we show $SModI\centernot\implies ModI$ and $SModI\centernot\implies JI$.
To prove them both, we consider the example with $\Omega=\\{1,2,3,4\\}$ with
$X_{i}\in\\{0,1\\}$, $\forall\ i=1,2,3,4$ and
$P_{X_{1},X_{2},X_{3},X_{4}}(x_{1},x_{2},x_{3},x_{4})=\frac{1}{8}$ for
$(x_{1},x_{2},x_{3},x_{4})\in\\{(0,0,0,0),(0,0,1,1),(0,1,0,1),(0,1,1,0),(1,0,0,1),\\\
(1,0,1,0),(1,1,0,0),(1,1,1,1)\\}$. Note here we have $X_{4}=X_{1}\oplus
X_{2}\oplus X_{3}\oplus X_{4}$. Let us have $A=\\{1,2\\}$ and $B=\\{3,4\\}$.
Thus, with the chosen joint distribution we have $SModI$ to be true which
needs pairwise independence and the mutual independence between any set of
three random variables. Since $H(X_{4}|X_{1},X_{2},X_{3})=0\neq
H(X_{4})=\frac{1}{2}$, $ModI$ is not true. Also as
$P_{X_{1},X_{2},X_{3},X_{4}}(0,0,0,0)=\frac{1}{8}\neq
P_{X_{1},X_{2}}(0,0)P_{X_{3},X_{4}}(0,0)=\frac{1}{16}$, $ModI$ is not true.
Therefore, $SModI\centernot\implies ModI$ and $SModI\centernot\implies JI$.

$MI\centernot\implies SModI$ follows since $JI\implies MI$ and
$JI\centernot\implies SModI$. Similarly, $MI\centernot\implies JI$ follows
since $SModI\implies MI$ and $SModI\centernot\implies JI$.

In the end, we show $PI\centernot\implies MI$. Here consider an example, where
the assumed probability distribution on $X_{1},X_{2},X_{3}$ which take values
in $\\{0,1\\}$, is as follows:
$P_{X_{1},X_{2},X_{3}}(0,0,0)=P_{X_{1},X_{2},X_{3}}(0,1,1)=P_{X_{1},X_{2},X_{3}}(1,0,1)=P_{X_{1},X_{2},X_{3}}(1,1,0)=\frac{1}{4}$.
It is easy to check here that there is pairwise independence, as,
$X_{i}\sim\text{Bern}(\frac{1}{2})$ and that
$P_{X_{i},X_{j}}(0,0)=P_{X_{i},X_{j}}(1,0)=P_{X_{i},X_{j}}(0,1)=P_{X_{i},X_{j}}(1,1)=\frac{1}{4}$,
$\forall i\neq j\in\\{1,2,3\\}$. Thus there is pairwise independence which
implies $PI$ independence for sets $A=\\{1,2\\}$ and $B=\\{3\\}$. However
there is no mutual independence here as we can see that
$P_{X_{1},X_{2},X_{3}}(0,0,0)=\frac{1}{4}\neq\frac{1}{8}=P_{X_{1}}(0)P_{X_{2}}(0)P_{X_{3}}(0)$.
In fact, by the way of construction of the example, knowing $X_{1}$ and
$X_{2}$ one knows $X_{3}$ with certainty, which implies
$H(X_{3}|X_{1},X_{2})=0\neq H(X_{3})=1$. This implies $MI$ independence does
not hold for the sets as it requires at least $H(X_{3}|X_{1},X_{2})=H(X_{3})$,
which is not true in this example. ∎

##  VII Conclusions

To conclude, in this paper, we study different independence classes of
combinatorial independence, and their relationships. We then discuss the
implications of these results in the entropic case, and provide algorithms for
obtaining the independent sets for different independence classes. Finally, we
discuss some implications of the results for applications like summarization
and clustering.

## References

  * [1] Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal.  Deep batch active learning by diverse, uncertain gradient lower bounds.  arXiv preprint arXiv:1906.03671, 2019.
  * [2] Francis Bach.  Learning with submodular functions: A convex optimization perspective.  arXiv preprint arXiv:1111.6453, 2011.
  * [3] S. Fujishige.  Submodular functions and optimization, volume 58.  Elsevier Science, 2005.
  * [4] Anupam Gupta and Roie Levin.  The online submodular cover problem.  In ACM-SIAM Symposium on Discrete Algorithms, 2020.
  * [5] Rishabh Iyer and Jeff Bilmes.  Concave aspects of submodular functions.  In Proc. ISIT, 2020.
  * [6] Rishabh Iyer, Stefanie Jegelka, and Jeff Bilmes.  Fast semidifferential-based submodular function optimization: Extended version.  In ICML, 2013.
  * [7] Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, and Himanshu Asanani.  Submodular combinatorial information measures with applications in machine learning.  In Algorithmic Learning Theory, 2021.
  * [8] Rishabh K Iyer and Jeff A Bilmes.  Submodular optimization with submodular cover and submodular knapsack constraints.  In Advances in Neural Information Processing Systems, pages 2436–2444, 2013.
  * [9] Rishabh Krishnan Iyer.  Submodular optimization and machine learning: Theoretical results, unifying and scalable algorithms, and applications.  PhD thesis, 2015.
  * [10] Vishal Kaushal, Suraj Kothawade, Ganesh Ramakrishnan, Jeff Bilmes, Himanshu Asnani, and Rishabh Iyer.  A unified framework for generic, query-focused, privacy preserving and update summarization using submodular information measures.  arXiv preprint arXiv:2010.05631, 2020.
  * [11] Vishal Kaushal, Suraj Kothawade, Ganesh Ramakrishnan, Jeff Bilmes, and Rishabh Iyer.  Prism: A unified framework of parameterized submodular information measures for targeted data subset selection and summarization.  arXiv preprint arXiv:2103.00128, 2021.
  * [12] Krishnateja Killamsetty, Durga Sivasubramanian, Baharan Mirzasoleiman, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer.  Grad-match: A gradient matching based data subset selection for efficient learning.  In Proc. ICML, 2021.
  * [13] Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer.  Glister: Generalization based data subset selection for efficient and robust learning.  arXiv preprint arXiv:2012.10630, 2020.
  * [14] László Lovász.  Submodular functions and convexity.  In Mathematical Programming The State of the Art, pages 235–257. Springer, 1983.
  * [15] Ehsan Tohidi, Rouhollah Amiri, Mario Coutino, David Gesbert, Geert Leus, and Amin Karbasi.  Submodularity in action: From machine learning to signal processing applications.  IEEE Signal Processing Magazine, 37(5):120–133, 2020.
  * [16] Sebastian Tschiatschek, Rishabh K Iyer, Haochen Wei, and Jeff A Bilmes.  Learning Mixtures of Submodular Functions for Image Collection Summarization.  In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27. 2014.
  * [17] Kai Wei, Rishabh Iyer, and Jeff Bilmes.  Submodularity in data subset selection and active learning.  In International Conference on Machine Learning, pages 1954–1963. PMLR, 2015.


# Formulating Few-shot Fine-tuning Towards Language Model Pre-training:
A Pilot Study on Named Entity Recognition

Zihan Wang Kewen Zhao Zilong Wang Jingbo Shang
University of California, San Diego
{ziw224, k4zhao, zlwang<EMAIL_ADDRESS>Corresponding Author.

###### Abstract

Fine-tuning pre-trained language models is a common practice in building NLP
models for various tasks, including the case with less supervision. We argue
that under the few-shot setting, formulating fine-tuning closer to the pre-
training objective shall be able to unleash more benefits from the pre-trained
language models. In this work, we take few-shot named entity recognition (NER)
for a pilot study, where existing fine-tuning strategies are much different
from pre-training. We propose a novel few-shot fine-tuning framework for NER,
FFF-NER. Specifically, we introduce three new types of tokens, “ _is-entity_
”, “ _which-type_ ” and _bracket_ , so we can formulate the NER fine-tuning as
(masked) token prediction or generation, depending on the choice of the pre-
training objective. In our experiments, we apply FFF-NER to fine-tune both
BERT and BART for few-shot NER on several benchmark datasets and observe
significant improvements over existing fine-tuning strategies, including
sequence labeling, prototype meta-learning, and prompt-based approaches. We
further perform a series of ablation studies, showing few-shot NER performance
is strongly correlated with the similarity between fine-tuning and pre-
training.

##  1 Introduction

Figure 1: Two pre-training strategies (masked language modeling and sequence
to sequence denoising) and different few-shot fine-tuning frameworks based on
them. Our FFF-NER has different designs for different pre-trained models, but
share the same principle of simulating the pre-training task.

Pre-trained language models Peters et al. (2018); Devlin et al. (2019); Liu et
al. (2019); Lewis et al. (2020) have the ability to capture extensive semantic
and syntactic information in text. Such prior understanding of language offers
a solid foundation to downstream tasks, therefore, fine-tuning language models
have been widely applied in various NLP applications, especially when the
task-specific annotations are limited (a.k.a. few-shot setting) Radford et al.
(2019); Brown et al. (2020).

While many few-shot strategies have been explored, there is no established
systematic principle on designing these strategies. Intuitively, given the
same amount of task-specific annotations, a pre-training aligned fine-tuning
strategy should more easily extract beneficial knowledge encoded during pre-
training. Therefore, we hypothesize that the performance of few-shot fine-
tuning is tied to the similarity between the fine-tuning strategy and the pre-
training objective.

To verify this hypothesis, we take the Named Entity Recognition (NER) task for
a pilot study, since the common fine-tuning strategies for NER are much
different from popular pre-training tasks. Specifically, the most common fine-
tuning paradigm for NER is to train a sequence labeling model on top of a pre-
trained language model — for each token in a sentence, simultaneously decide
whether it belongs to an entity and the type of the entity among given entity
types. As an example showing the difference, the commonly used pre-trained
language model BERT has a pre-training goal to disambiguate some masked tokens
by predicting the correct token (masked language modeling). While in sequence
labeling, each token (representation) is to decide two different pieces of
information (span & type).

Following our hypothesis, we propose a few-shot fine-tuning framework for NER,
FFF-NER as shown in Figure 1. At the core is decoupling span detection and
type prediction, since they are essentially two quite different tasks, which
is not easy to learn altogether in few-shot fine-tuning. We introduce two new
types of tokens that we dub as “ _is-entity_ ” and “ _which-type_ ” to perform
the two tasks individually. With the help of these two types of tokens, we
consider each instance not a single sentence but a sentence-span pair and ask
the model to predict whether the span is an entity and, if it is, the type of
the entity. The two tokens are placed around the span. By introducing another
type of token, _bracket_ , around the span and the two special tokens, the
sentence highlights the span in consideration and treats the special tokens as
meta-data-like information. The goal of the fine-tuning task is then to
classify the corresponding “ _is-entity_ ” and “ _which-type_ ” representation
for each span.

Our FFF-NER is formulated in a pre-training agnostic way, and here we
elaborate how it can be adapted to two popular pre-training tasks, (masked)
token prediction and generation. For BERT trained with masked language
modeling, we use the masked tokens as the two special tokens and ask the model
to perform a binary classification on “ _is-entity_ ” and a multi-class
classification on “ _which-type_ ”. For BART trained with sequence to sequence
denoising that is able to generate text, the two tokens are virtual — we treat
the formulated sentence with _brackets_ indicating spans and type-decoded
special tokens as the target clean sentence, and the original sentence as a
noised one without entity information. The model is to decode the target
sentence with entity information.

We conduct experiments on the recently proposed few-shot NER benchmark Huang
et al. (2021) and show that FFF-NER can achieve significant improvements over
the state-of-the-art methods, including sequence labeling, prototype meta-
learning models, and prompt-based approaches. It is worth mentioning that
several recent NER methods Cui et al. (2021); Yang and Katiyar (2020); Wang et
al. (2021); Ma et al. (2021) have different experimental settings and
dataset/data-split selections (even though the dataset names may be the same).
Therefore, for a fair comparison, we have carefully re-evaluated them under
the same setting.

Our extensive ablation studies have further verified the correlation between
the performance of NER and the similarity between fine-tuning and pre-
training. Focusing on the masked language modeling pre-training task, the key
efforts that we made in FFF-NER to close the gap between pre-training and
fine-tuning (i.e., the usage of _mask_ , _brackets_ , “ _is-entity_ ”, and “
_which-type_ ” tokens) are all crucial to the NER performance.

All these empirical results are in favor of our hypothesis, shedding insights
on design principles for fine-tuning strategies. Remarkably, there are
existing models GENRE Cao et al. (2021) and TANL Paolini et al. (2021) sharing
the same design principle as FFF-NER by formulating BART fine-tuning as a
token generation task. They can be viewed as siblings of FFF-NER, serving as
another strong evidence in favor of our hypothesis. Our contributions are
summarized as follows.

  * •

We hypothesize for better performance, (few-shot) fine-tuning should be
designed similarly to the pre-training as much as possible. We further conduct
an ablation study to verify this insight.

  * •

Our pilot study on few-shot NER shows favorable results for our hypothesis.
Specifically, we propose a fine-tuning framework for few-shot NER FFF-NER,
which outperforms sequence labeling, protocol methods, and prompt-based
learning models on the five benchmark datasets for few-shot NER.

  * •

We enrich the standard few-shot NER benchmark by including more state-of-the-
art methods.

Reproducibility. We will release our code on
GitHub111https://github.com/ZihanWangKi/fffner.

##  2 Related Works

###  2.1 Named Entity Recognition

It has been shown that traditional fine-tuning methods that work in full
supervision might not work well in few-shot learning scenarios Wang et al.
(2021), as is the case in widely used BIO sequence labeling and near state of
the art fully supervised NER models Li et al. (2020). Some works have been
proposed based on templates or prototypical networks targeting low resource
NER Cui et al. (2021); Yang and Katiyar (2020); Wang et al. (2021). However,
there lacks a general principle for few-shot NER. In this work, we claim that
the similarity between the fine-tuning task and pre-training task can help
few-shot learning and prove empirically with our pre-training tailored few-
shot fine-tuning design and several ablations.

###  2.2 Prompt Learning

Recently, a resource-less way of solving downstream tasks, prompt learning Liu
et al. (2021) has gained interest. By stirring knowledge from pre-trained
language models with manually designed templates, the GPT model Radford et al.
(2019); Brown et al. (2020) can achieve decent performance on downstream tasks
without training. For NER, since the labeling task is unseen in natural text,
prompt-based methods are often combined with further fine-tuning Cui et al.
(2021). Our idea goes along the same line, where we argue that the similarity
to the pre-training task can help the model better transfer knowledge from
pre-training to the fine-tuning task. We show that some templates Cui et al.
(2021) might not work well for sequence-to-sequence denoising trained models,
as they are still much different from the pre-training task.

##  3 Preliminaries

###  3.1 Problem Definition

The task of Named Entity Recognition is to extract the n-grams in the text
that are named entities and label them with a set of pre-defined entity types.
Formally, given a sequence of words $w_{1},w_{2},\ldots,w_{n}$ of length $n$,
the goal is to identify the spans $w_{l},w_{l+1},\ldots,w_{r}$ where $l\leq r$
that is an entity, and assign it an entity type $c$ from a set of pre-defined
entity types $C$ (e.g., $C=\\{\text{Person, Location, etc}\\}$). In this work,
we sometimes use $l\ldots r$ to denote the span for simplicity.

#### Metric.

The most widely used metric for NER is the (span-based, micro) F1 score. It
considers all typed spans in the ground truth and from the model’s prediction
and calculates its F1 score on retrieving the whole entities.

#### Few-shot.

There are different definitions of Few-shot learning for NER. In this work, we
focus on the N-way K-shot setting Huang et al. (2021), where we consider all
$N=|C|$ entity types and for each entity type, randomly pick $K$ sentences
with supervision that contains the particular entity type. This is to make a
fair comparison with the traditional sequence labeling methods since full
supervision of sentences is crucial. Undoubtedly, while we select $N*K$
sentences as supervision, the total number of entity spans in the sentences
can be greater than $N*K$. Therefore, it is important to evaluate all models
on the same randomly selected sets of sentences. And one major reason for us
choosing this setting is the established benchmark over ten NER datasets Huang
et al. (2021).

###  3.2 Pre-trained Language Model

The use of a pre-trained language model has become ubiquitous in NLP. By
training with self-supervision, often through disambiguating corrupted
sentences, pre-trained language models can obtain a general understanding of
the text. Studies have shown that the pre-training task is more a major factor
for downstream task performance, rather than the architecture Tay et al.
(2022).

BERT Devlin et al. (2019) is a transformer Vaswani et al. (2017) encoder model
trained with masked language modeling. After replacing some tokens with a
special mask token, the model attempts to recover the original tokens. Thus,
BERT can leverage the nearby context of the mask token to predict its origin.

BART Lewis et al. (2020) is a transformer encoder-decoder model trained with
sequence to sequence denoising. The whole sentence is corrupted by replacing
segments with masks, and the model is to recover the original uncorrupted
sentence. A BART can predict the complete, clean sentence given a partial
sentence.

##  4 Our Framework FFF-NER

In this section, we introduce our framework FFF-NER, and specifically talk
about how to adapt it for a masked language modeling and sequence to sequence
pre-trained model.

###  4.1 Task Formation

The goal is to design a fine-tuning task equivalent to NER and similar to pre-
training, where the goal is to disambiguate sentences. We consider each
possible span in a sentence and predict whether it is an entity and, if it is,
the type of it. The major difference from our task to a traditional sequence
labeling task is that we decouple the span detection and entity prediction
problems.

We introduce two tokens, “is-entity” and “which-type” for span detection and
type prediction. For a particular sentence and a span specified, we insert the
two tokens around the span and then brackets around the two tokens and the
span. As an illustration, suppose the sentence in consideration is

Tom lives in Los Angeles

and the span is “Los Angeles”, then our task translates (by inserting 6
brackets and 2 special tokens) the sentence into

Tom lives in [ is-entity ] [ Los Angeles ] [ which-type ]

The brackets “highlight” the two special tokens and the span in the sentence,
which are important for understanding whether the span is an entity and the
type of it. The brackets may also hint that the special tokens should be
treated as meta-data, instead of normal text.

Different pre-trained language models will have slightly different training
objectives and prediction strategies based on such a task formation. We will
focus on the two popular pre-trained language models, BERT and BART, and talk
about integrating them with the framework.

###  4.2 Instantiation of FFF-NER using BERT

We first talk about BERT, an encoder model pre-trained with masked language
modeling.

#### Model Architecture.

We use the BERT model to encode the translated sentence. Then, the last layer
representations for the two special tokens are extracted, and each is fed
through a classification head to retrieve the class logits for both span
detection and type prediction. The pre-trained model is also tuned (i.e., the
parameters are not frozen), as in many fine-tuning approaches. We use the mask
token for both “is-entity” and “which-type”.

#### Training.

We train the model to detect whether the span is an entity and predict the
entity type for each span sentence pair. We consider a negative sampling
approach to treat the given entities as positive instances and all the other
spans as potential negative ones. Specifically, for each sentence
$W=w_{1},w_{2},\ldots,w_{n}$ with typed entity spans
$\mathcal{E}_{W}=\\{(l_{1},r_{1},t_{1}),(l_{2},r_{2},t_{2}),\ldots,(s_{e},r_{e},t_{e})\\}$
that are given as supervision, we consider a “positive” loss for the sentence
and a certain entity span

$\mathcal{L}^{\text{pos}}=\mathcal{L}(\text{is-
entity})+\mathcal{L}(\text{which-type}),$

where $\mathcal{L}(\text{is-entity})$ is the cross-entropy loss for the binary
prediction problem of classifying the “is-entity” token, and
$\mathcal{L}(\text{which-type})$ is the cross-entropy loss for the multi-class
prediction problem of classifying the exact type. The “negative” loss is
learned on spans that are not entities. For the sentence $W$, there are
$|W|+\binom{|W|}{2}-|\mathcal{E}_{W}|$ spans that are not entities. We
consider sampling a subset $\mathcal{D}_{W}$ of negative spans for each
sentence every epoch. The sample can change every epoch, which gives high
coverage over all the negative spans. Then, for each negative span, the loss
is

$\mathcal{L}^{\text{neg}}=\mathcal{L}(\text{is-entity}).$

Here, we only consider the is-entity loss since there is no entity type for
the sampled negative span.

During training in each epoch, we first sample all the negative samples along
with the positive ones, treat it as the dataset to train on in the epoch, and
perform regular (mini-)batch gradient descent on the dataset with the loss.

$\mathcal{L}=\mathcal{L}^{\text{pos}}+\mathcal{L}^{\text{neg}}.$

#### Negative Sampling for Training.

Here, we detail how we sample the negatives during training. There are two
things to consider, the number of negative samples to pick and the probability
of each span being sampled as a negative.

Directly training on all negative samples is very hard, since there are much
more negatives than positives, resulting in an imbalanced training set. We
describe how we determine the number of negatives to pick: the number of
negative samples depends on the length of the sentence and the number of
entities given as supervision in it. Intuitively, the longer the sentence is,
the more negative spans we need to pick to cover every token that appears in
it. And the more entities in the sentence, the more negative spans we need to
pick to cover overlapping non-entities with the entities. We consider these
two measurements separately.

For sentence length, we consider $\alpha*|W|$ negative samples where $\alpha$
is a small constant. This is based on a statistical result where
$O(|W|\log|W|)$ randomly sampled spans can cover each word with high
probability, and an empirical reasoning that since sentences are short, even
after removing the log factor, the sampled spans still can cover almost all
words in expectation.

We then take a simple approach where we project entities as virtual words that
increases the length of the sequence; then, we fall back to the formula
proposed for the sentence lengths. Based on statistics in the CoNLL Sang and
Meulder (2003) training set, the ratio of tokens to the number of entities is
about $10:1$. We count each entity as $10$ words and select
$\alpha*10*|\mathcal{E}_{W}|$ negative samples.

Finally, we sum up these two numbers as the negative samples for each
sentence. We empirically show that this choice works well, and through
sensitivity studies, the choice of $\alpha$ is not significant to performance
changes.

We also note that since we only sample a portion of negatives, we should
consider a weighted sampling since there are important negatives: those that
have high overlap with a true entity (e.g., “Chicago is” and “York”). The
model learns spurious features without explicitly treating them as negatives.

To solve this, for each sentence, we define a sampling probability based on
the overlap between the non-positive spans and entities. If the span contains
words $w_{l},w_{l+1},\ldots,w_{r}$, and among these $r-l+1$ words, $c$ of them
are within an entity in the sentence, the probability for the span being
sampled is proportional to $exp(\frac{c}{r-l+1})$. The probability of each
sample is determined based on the intuition that the hard instances to predict
are those that look like an entity. Therefore, we calculate the overlap
between the span and the entities, normalized by the length of the span to
assign a priority score for each span. Simply treating this score (after
normalizing to a distribution) as the probabilities to sample will cause the
sampling process never to pick spans that have no intersection with entities
since their priority score is 0. So, we transform the percentage into an
exponential scale and normalize thereafter to form a probability distribution.

#### Predicting.

During prediction, we enumerate through all spans in the sentence and extract
the probability of it being classified as an entity $p_{l,r}$ (from the “is-
entity” token), along with the type (the class that has the maximum
probability on which-type token). Ideally, all the spans with $p_{l,r}\geq
0.5$ should be disjoint since all our positive instance training is performed
on non-overlapping spans from a non-nested NER dataset. However, training is
hard to be perfect, especially in few-shot scenarios. Therefore, we need a
strategy to resolve the overlapping predicted spans.

We consider the most straightforward way to resolve overlaps: greedily assign
spans based on their probability and ignore overlapping ones with lower
probability. Formally, we consider all spans $(l,r)$ with $p_{l,r}\geq 0.5$
and sort them with the largest probability one first. Then, we pick the spans
one by one and add them to the final predicted entity list, given that the
span does not overlap with an already picked span, in which case we ignore it
and move on to the next span.

###  4.3 Instantiation of FFF-NER using BART

MLM pre-training is not the only type of model that can be tuned under our
setting. We talk about instantiating our framework with an encoder-decoder
model pre-trained with sequence to sequence denoising, BART.

#### Setup

The sequence denoising task is to recover the original sentence given a
partially corrupted version. As a direct simulation of the MLM-based setting
for FFF-NER, we can consider the original sentence as partially corrupted, and
ask the model to generate the full sentence that contains the decoded “is-
entity” and “which-type” tokens indicating the span and type. However, in
sequence decoding, the “is-entity” part is unnecessary since the brackets are
generated to predict the span. We illustrate the sentence denoising setup with
an example. Consider an input sentence

Tom lives in Los Angeles

then, a correctly decoded sentence is

[ Tom ] [ Person ] lives in [ Los Angeles ] [ Location ]

We introduce two similar designs in literature. GENRE.  GENRE Cao et al.
(2021) was originally proposed for entity linking. The setup is almost
equivalent to our setup above except for the use of different type of
brackets.

TANL.  TANL Paolini et al. (2021) has a slightly different design that joints
the adjacent brackets between the entity and the type with a “|”. For the same
input sentence example in the setup section, the correctly decoded sentence is

[ Tom | Person ] lives in [ Los Angeles | Location ]

Because of the existence of such work, our experiments will focus on the MLM-
based models and we leave discussion of such sequence-to-sequence models in
the Appendix.

##  5 Experiments

Dataset | LC | P | FFF-NER
---|---|---|---
CoNLL | 53.5 | 58.4 |  67.90 ($\pm 3.95$)
Onto | 57.7 | 53.3 |  66.40 ($\pm 1.62$)
WikiGold | 47.0 | 51.1 |  61.42 ($\pm 8.82$)
WNUT17 | 25.7 | 29.5 | 30.48 ($\pm 3.69$)
MIT Movie | 51.3 | 38.0 |  60.32 ($\pm 1.12$)
MIT Restaurant | 48.7 | 44.1 |  51.99 ($\pm 2.33$)
SNIPS | 79.2 | 75.0 |  83.43 ($\pm 1.44$)
ATIS | 90.8 | 84.2 |  92.75 ($\pm 0.99$)
Multiwoz | 12.3 | 21.9 |  47.56 ($\pm 8.46$)
I2B2 | 36.0 | 32.0 |  49.37 ($\pm 5.08$)
Average | 50.2 | 48.8 | 61.15
Table 1: Experiments on N-way 5 shot NER on all datasets in Huang et al.
(2021) for our model. LC stands for a sequence labeling method, P stands for
prototypical network, and FFF-NER is a BERT-base-uncased model trained with
our framework. We bold the best scores that are statistically significant when
compared with others at a 0.05 significance level.

Framework | Language Model | CoNLL | Onto | WNUT17 | MIT Movie | MIT Restaurant
---|---|---|---|---|---|---
Seq Labeling | Roberta-base† | 53.5 | 57.7 | 25.7 | 51.3 | 48.7
BERT-base-uncased | 52.92 ($\pm 4.55$) | 56.66 ($\pm 0.85$) | 21.53 ($\pm 4.81$) | 47.29 ($\pm 1.32$) | 45.64 ($\pm 2.30$)
BERT-base-cased | 51.04 ($\pm 3.94$) | 60.71 ($\pm 1.11$) | 20.18 ($\pm 5.43$) | 44.98 ($\pm 1.48$) | 39.07 ($\pm 2.73$)
BERT-large-uncased | 53.50 ($\pm 4.40$) | 59.65 ($\pm 1.87$) | 28.03 ($\pm 5.08$) | 52.84 ($\pm 2.00$) | 47.33 ($\pm 1.91$)
BERT-large-cased | 52.23 ($\pm 3.90$) | 64.03 ($\pm 1.28$) | 26.76 ($\pm 4.30$) | 48.31 ($\pm 2.93$) | 43.08 ($\pm 1.98$)
Prototype | Roberta-base† | 58.4 | 53.3 | 29.5 | 38.0 | 44.1
TemplateNER | BART-large | 61.46 ($\pm 6.46$) | N/A | 11.20 ($\pm 1.09$) | 41.80 ($\pm 1.36$) | N/A
StructShot | BERT-large-cased | 50.55 ($\pm 7.75$) | 69.80 ($\pm 1.19$) | 27.32 ($\pm 3.01$) | 56.58 ($\pm 2.01$) | 45.62 ($\pm 3.39$)
EntLM‡ | BERT-base-cased | 61.67 ($\pm 2.72$) | 67.97 ($\pm 1.24$) | 23.70 ($\pm 4.03$) | 43.95 ($\pm 0.79$) | 51.29 ($\pm 2.12$)
BERT-large-cased | 59.44 ($\pm 2.85$) | 68.92 ($\pm 1.58$) | 17.82 ($\pm 3.06$) | 45.31 ($\pm 6.09$) | 53.13 ($\pm 1.56$)
SpanNER‡ | BERT-base-uncased | 58.95 ($\pm 4.15$) | 67.89 ($\pm 1.33$) | 22.18 ($\pm 4.63$) | 55.79 ($\pm 1.22$) | 52.08 ($\pm 2.46$)
BERT-large-uncased | 57.93 ($\pm 3.99$) | 68.40 ($\pm 1.39$) | 20.72 ($\pm 6.58$) | 57.81 ($\pm 2.29$) | 50.10 ($\pm 1.06$)
FFF-NER | BERT-base-uncased | 67.90 ($\pm 3.95$) | 66.40 ($\pm 1.62$) | 30.48 ($\pm 3.69$) | 60.32 ($\pm 1.12$) | 51.99 ($\pm 2.33$)
BERT-large-uncased | 69.23 ($\pm 3.90$) | 69.43 ($\pm 1.30$) | 34.96 ($\pm 5.07$) | 61.31 ($\pm 2.12$) | 55.01 ($\pm 2.71$)

Table 2: Experiments on N-way 5 shot NER on 5 datasets. The average
performance over ten different folds of seed shots are given, and the standard
deviation is given in parentheses. † indicates results borrowed from Huang et
al. (2021), and they did not report standard deviations. N/A indicates the
performance is far behind other methods, and we suspect that extensive
dataset-specific template/hyperparameter tuning is necessary. For the backbone
language model, we show the better one among the cased and uncased versions.
We discuss the reproduction details and number differences from reported
numbers of EntLM and SpanNER in the Appendix.

###  5.1 Compared Methods

We compare with several publicly available low-resource NER models.

Roberta-base is a sequence labeling model build on the official roberta-base
Liu et al. (2019). It is a baseline result reported in Huang et al. (2021). We
also use BERT models and experiment with BERT-{base, large}-{uncased, cased}.

Nearest Neighbor is a baseline prototype method reported in Huang et al.
(2021) that assigns each token representation to the nearest label
representation, learned by the examples in the training set in a prototypical
network Snell et al. (2017).

StructShot Yang and Katiyar (2020) extends Nearest Neighbor to consider label
transitions as in a Conditional Random Field Lafferty et al. (2001).

TemplateNER Cui et al. (2021) considers templates that are human selected
formatted like “X is a Y entity .” and “X is not a named entity .” where X is
the span to consider and Y is the ground truth entity during training. It uses
BART to decode the template for each sentence span pair.

EntLM Ma et al. (2021) also has the idea of minimizing the gap between pre-
training and fine-tuning. They asked a MLM-pretrained language model to
predict every token in the input sentence. The prediction should either be
within list of special tokens specifying each type if it is an entity or the
original token itself otherwise. This setting draws the pre-training and fine-
tuning closer by making token predictions, but poses another difference in
that the target predicted word might not suit the context well. In fact, they
need to specially curate a list of entity names. More discussions on this are
in the Appendix.

SpanNER Wang et al. (2021) is a method that also breaks span detection and
type prediction into two tasks. For each token, they simultaneously predict
whether it is a start of span and an end, similar to question answering. Then,
they utilize class descriptions from annotation guidelines or Wikipedia to
construct a class representation to match the detected spans. In some sense,
their ideology follows our framework, as an important step in our framework is
also decoupling span detection and type prediction. However, many of their
model designs still differ from the backbone pre-trained model BERT (e.g.,
asking each token to perform span predictions and averaging span
representations to find the closest class representation).

###  5.2 Experimental Settings

For the four BERT sequence labeling models, we use the implementation of
sequence labeling in Huggingface Wolf et al. (2020); Huggingface (2022), and
tune the number of epochs to use.

We reproduce the other compared methods as their performance is not reported
on the standard few-shot setting/standard datasets or splits in Huang et al.
(2021). When reproducing, we follow the original hyper-parameters except (1)
Increasing the sequence length when necessary, (2) Decreasing the batch size
if the GPU memory does not fit, and (3) Tuning the number of training epochs
and learning rate if performance is not desirable.

Our masked language modeling based FFF-NER is built with Pytorch Lightning
PyTorchLightning (2022). We try to follow all hyper-parameter settings
(optimizer, learning rate, etc.) as close as Huggingface’s sequence labeling.

All experiments are conducted on RTX A6000 and RTX 8000 GPUs, both having 48
GB GPU RAM. For exact hyperparameter settings, please refer to the Appendix.

###  5.3 Datasets

We mainly experiment on five of the ten datasets in Huang et al. (2021). The
reasons of choosing these five datasets are: (1) SpanNER Wang et al. (2021)
require descriptions that were not gathered for the other five datasets (2)
These five datasets are commonly used and cover various domains (news,
general, social media, reviews). We do include a study of our framework on all
of the ten datasets. For each dataset, we run on the standard ten splits from
Huang et al. (2021) whenever possible and report both the average and standard
deviation.

###  5.4 Performance of FFF-NER

In Table 1 we show the performance of our framework on a BERT-based-uncased
model on all ten datasets in Huang et al. (2021) and compare with the two
baselines that do not require extra data: sequence labeling and prototype. We
see that our model performs statistically significantly better than the
compared methods on every dataset except WNUT17. We also note that our overall
performance on the ten datasets exceeds the best method reported in Huang et
al. (2021) (LC + NSP + ST) that has an average performance of 58.5. Notably,
we do not require a large-scale noisy fine-grained entity recognition dataset
to adapt the pre-trained language model or self-training on the unlabeled in-
domain dataset.

In Table 2 we show the full table containing our method and all the compared
methods on the five datasets performing 5-shot NER, differentiating by the
underlying pre-trained language model. Each baseline performed pretty well on
some of the datasets, especially EntLM and SpanNER, which we attribute to
their unanimous design of bridging pre-training and fine-tuning. However, none
of them showed consistent improvement across all datasets like ours. When
looking at the absolute scores, our large methods are statistically
significantly better than the compared methods on all datasets except Onto.

###  5.5 Ablations of FFF-NER

Framework | CoNLL | MIT Restaurant
---|---|---
Sequence Labeling | 52.92 ($\pm 4.55$) | 45.64 ($\pm 2.30$)
FFF-NER | 67.90 ($\pm 3.95$) | 51.99 ($\pm 2.33$)
Not mask | 64.08 ($\pm 3.62$) | 52.71 ($\pm 3.47$)
No brackets | 60.18 ($\pm 3.42$) | 42.73 ($\pm 4.21$)
Span & type together | 53.20 ($\pm 7.96$) | 33.79 ($\pm 6.87$)
Table 3: Ablations of FFF-NER that distance the fine-tuning task from pre-
training. We use a BERT-base-uncased model.

We strengthen our claim that the improvement of our method comes from the
fine-tuning design being similar to the pre-training task. We consider three
variants of our framework design for masked language modeling and show the
results in Table 3.

Not mask replaces the mask token used for the two special tokens with the
actual tokens “span” and “type”. We can see that the performance drops
significantly on CoNLL, while no significant changes can be observed from
Restaurant. We attribute this to the fact that there is less difference from a
mask token to an actual token for pre-trained language models since MLM is
also trained on non-mask tokens for $20\%$ of the training time Devlin et al.
(2019). However, the slight decrease in performance still indicates that using
the mask token is better.

No brackets removes all six brackets when formulating the input sentence.
Since we have the two mask tokens around the span, the input sentence is still
distinct for different spans. However, the performance drops by a large
margin. At first, this may sound intriguing since the sentence without
brackets looks more like natural text. However, we note that with the original
setting with brackets, the sentence is like annotating a span with meta-data,
while without brackets, the model is to complete the sentence with missing
words.

Span & type together removes the “is-entity” token and integrates the span
detection and type prediction task. The “which-type” token now needs to
perform two tasks simultaneously, much like in sequence labeling. The
performance on the two datasets drops drastically: on CoNLL, the performance
is similar to that of sequence labeling, and on MIT Restaurant, the
performance is even lower.

###  5.6 A Mismatched Scenario of FFF-NER

Backbone | BERT | BART
---|---|---
Sequence Labeling | 52.92 ($\pm 4.55$) | 59.66 ($\pm 2.92$)
FFF-NER for MLM | 67.90 ($\pm 3.95$) | 59.65 ($\pm 2.61$)
Table 4: An experiment where FFF-NER for Masked Language Modeling trained
models (e.g., BERT) are applied to Sequence Denoising trained models (e.g.,
BART).

Given our hypothesis that pre-training fine-tuning gap should be minimized,
one would expect that a framework designed to reduce the gap between MLM pre-
training shouldn’t work well for Sequence Denoising pre-training. We show that
this is indeed the case with an experiment in Table 4. Even though FFF-NER
outperforms Sequence Labeling on an MLM model, as expected, it does not show a
difference on a model with a different pre-training objective. This
observation can be even strengthened if we can check the other way – whether
Sequence Denoising tailored methods fall short on MLM pre-trained models.
However, we note that all such methods we tested in this work require the
ability to generate text, which MLM models can not.

###  5.7 Sensitivity Study of FFF-NER

Figure 2: Sensitivity study using on CoNLL and MIT Restaurant using BERT-base-
uncased. Average performance and standard deviation are shown.

We study the choice of the number of negative spans to sample in Figure 2. In
our framework, we sample $\alpha*(|W|+|\mathcal{E}_{W}|*10)$ negative spans
for each sentence, and $\alpha$ is chosen to be 3 across all datasets. While
we fix the use of $10$, we analyze how the performance varies with different
choices of $\alpha$. We can see that overall, the performance is pretty steady
even when we use two times smaller number of samples ($\alpha=1$) or almost
one time more number of samples $(\alpha=5)$. Therefore, we believe that one
does not need extensive hyper-parameter selection on $\alpha$.

###  5.8 Performance vs Shots

Figure 3: Analysis of our FFF-NER when the number of shots vary on the CoNLL
dataset using BERT-base-uncased. Average performance and standard deviation
are shown. A sequence labeling model is also shown for comparison.

We also study how our framework works with more supervision. In Figure 3 we
increase the number of shots $K$ from the default $5$ shots to as many as
$100$ shots. A clear trend is that the advantages of our framework vanish as
the number of shots increases. We also train FFF-NER with BERT-base-uncased on
the full CoNLL dataset, achieving a performance of 95.57 on the dev set and
92.06 on the test set. This result is slightly less but close to a sequence
labeling based BERT model. The vanishing performance in high-resource
scenarios aligns with our common sense — the gap between pre-training and
fine-tuning can be overcome when there is large amounts of supervision.
Overall, our framework is still capable of handling large amounts of
supervision, albeit designed for a few-shot scenario.

##  6 Conclusions

In this work, we draw attention to an intuitive principle for few-shot fine-
tuning designs: the closer the fine-tuning task is to the pre-training task,
the better the performance. We empirically prove this by designing a few-shot
fine-tuning framework for NER, FFF-NER. Our framework is not constrained to a
specific architecture of language models and can be easily extended to
distinct pre-trained models (e.g., BERT and BART in our experiments). Our
model outperforms existing fine-tuning strategies including sequence labeling,
prototype meta-learning, and prompt-based approaches on the standard benchmark
for few-shot NER. Through a series of ablations, we also show that if we
manually remove ingredients in our framework that make the fine-tuning task
similar to pre-training, the performance drops.

We see future works in two directions. One is to incorporate label semantics
into the BERT based FFF-NER, so that even less supervision can suffice. The
other is to verify our principle of few-shot fine-tuning on other downstream
tasks.

## Ethical Considerations

The work presented in this paper deals with design principles in the few-shot
scenario. We present experiments on Named Entity Recognition, which do not
pose ethical concerns. Further, we will also open source our code. Our
framework makes it possible for training NER models with small amounts of
supervision, which makes NER tools more accessible to every ordinary people,
so we are on the positive side on ethical consideration.

## Limitations

#### Time Complexity.

One drawback of our FFF-NER design for MLM models is the increased time
complexity. Compared to a sequence labeling method which needs one forward
pass to predict entities of the whole sentence, our requires potentially
$n+\binom{n}{2}$ passes. However, a few things to note is:

  * •

If one has prior knowledge on how long the entity could be, they can only
consider spans with at most that length and avoid the quadratic dependency on
the sequence length.

  * •

In few-shot learning, the training set is small, so the increase in training
time is insignificant.

Yet, even with these considerations, our work is less efficient than
approaches that require a single pass for each sentence, like the traditional
sequence labeling method.

#### Special Treatment for Large Training Sets.

Shown in the Appendix, our method needs a smaller learning rate when we
experiment with more data (e.g., 100 shot scenario). Otherwise, there will be
cases when the model training fails due to gradient vanishing We also observed
this behavior for EntLM Ma et al. (2021) and tuned the learning rate for it as
well. We do not think that this problem is severe since (1) they are
noticeable without a development set as one can check the gradients and the
training accuracy/loss to detect such problems and (2) decreasing learning
rate or restarting with different initializations can resolve this problem in
our experiments.

## Acknowledgement

We thank all anonymous reviewers and program chairs for their helpful
feedback. Zihan Wang is supported by the UCSD Jacob School of Engineering
Fellowship and the UCSD Halıcıoğlu Data Science Fellowship. This work is
sponsored in part by National Science Foundation Convergence Accelerator under
award OIA-2040727 as well as generous gifts from Google, Adobe, and Teradata.
Any opinions, findings, and conclusions or recommendations expressed herein
are those of the authors and should not be interpreted as necessarily
representing the views, either expressed or implied, of the U.S. Government.
The U.S. Government is authorized to reproduce and distribute reprints for
government purposes not withstanding any copyright annotation hereon.

## References

  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Cao et al. (2021) Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni. 2021.  Autoregressive entity retrieval.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Cui et al. (2021) Leyang Cui, Yu Wu, Jian Liu, Sen Yang, and Yue Zhang. 2021.  Template-based named entity recognition using BART.  In _Findings of the Association for Computational Linguistics: ACL/IJCNLP 2021, Online Event, August 1-6, 2021_ , volume ACL/IJCNLP 2021 of _Findings of ACL_ , pages 1835–1845. Association for Computational Linguistics.
  * 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, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , pages 4171–4186. Association for Computational Linguistics.
  * Huang et al. (2021) Jiaxin Huang, Chunyuan Li, Krishan Subudhi, Damien Jose, Shobana Balakrishnan, Weizhu Chen, Baolin Peng, Jianfeng Gao, and Jiawei Han. 2021.  Few-shot named entity recognition: An empirical baseline study.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021_ , pages 10408–10423. Association for Computational Linguistics.
  * Huggingface (2022) Huggingface. 2022.  https://github.com/huggingface/transformers/tree/master/examples/pytorch.
  * Lafferty et al. (2001) John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001.  Conditional random fields: Probabilistic models for segmenting and labeling sequence data.  In _Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), Williams College, Williamstown, MA, USA, June 28 - July 1, 2001_ , pages 282–289. Morgan Kaufmann.
  * 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, ACL 2020, Online, July 5-10, 2020_ , pages 7871–7880. Association for Computational Linguistics.
  * Li et al. (2020) Xiaoya Li, Jingrong Feng, Yuxian Meng, Qinghong Han, Fei Wu, and Jiwei Li. 2020\.  A unified MRC framework for named entity recognition.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , pages 5849–5859. Association for Computational Linguistics.
  * Liang et al. (2020) Chen Liang, Yue Yu, Haoming Jiang, Siawpeng Er, Ruijia Wang, Tuo Zhao, and Chao Zhang. 2020.  BOND: bert-assisted open-domain named entity recognition with distant supervision.  In _KDD ’20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020_ , pages 1054–1064. ACM.
  * Liu et al. (2021) Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. 2021.  Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing.  _CoRR_ , abs/2107.13586.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized BERT pretraining approach.  _CoRR_ , abs/1907.11692.
  * Ma et al. (2021) Ruotian Ma, Xin Zhou, Tao Gui, Yiding Tan, Qi Zhang, and Xuanjing Huang. 2021.  Template-free prompt tuning for few-shot NER.  _CoRR_ , abs/2109.13532.
  * Paolini et al. (2021) Giovanni Paolini, Ben Athiwaratkun, Jason Krone, Jie Ma, Alessandro Achille, Rishita Anubhai, Cícero Nogueira dos Santos, Bing Xiang, and Stefano Soatto. 2021.  Structured prediction as translation between augmented natural languages.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Peters et al. (2018) Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018.  Deep contextualized word representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2018, New Orleans, Louisiana, USA, June 1-6, 2018, Volume 1 (Long Papers)_ , pages 2227–2237. Association for Computational Linguistics.
  * PyTorchLightning (2022) PyTorchLightning. 2022.  https://github.com/PyTorchLightning/pytorch-lightning.
  * 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.
  * Sang and Meulder (2003) Erik F. Tjong Kim Sang and Fien De Meulder. 2003.  Introduction to the conll-2003 shared task: Language-independent named entity recognition.  In _Proceedings of the Seventh Conference on Natural Language Learning, CoNLL 2003, Held in cooperation with HLT-NAACL 2003, Edmonton, Canada, May 31 - June 1, 2003_ , pages 142–147. ACL.
  * Snell et al. (2017) Jake Snell, Kevin Swersky, and Richard S. Zemel. 2017.  Prototypical networks for few-shot learning.  In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 4077–4087.
  * Tay et al. (2022) Yi Tay, Mostafa Dehghani, Vinh Q. Tran, Xavier Garcia, Dara Bahri, Tal Schuster, Huaixiu Steven Zheng, Neil Houlsby, and Donald Metzler. 2022.  Unifying language learning paradigms.  _CoRR_ , abs/2205.05131.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 5998–6008.
  * Wang et al. (2021) Yaqing Wang, Haoda Chu, Chao Zhang, and Jing Gao. 2021.  Learning from language description: Low-shot named entity recognition via decomposed framework.  In _Findings of the Association for Computational Linguistics: EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 16-20 November, 2021_ , pages 1618–1630. Association for Computational Linguistics.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, EMNLP 2020 - Demos, Online, November 16-20, 2020_ , pages 38–45. Association for Computational Linguistics.
  * Yang and Katiyar (2020) Yi Yang and Arzoo Katiyar. 2020.  Simple and effective few-shot named entity recognition with structured nearest neighbor learning.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020_ , pages 6365–6375. Association for Computational Linguistics.

##  Appendix A FFF-NER for MLM

We include some pseudo code pieces to help understand the whole framework when
applied to masked language modeling based pre-training language model.

Input: Sentence $W$ and entities $\mathcal{E_{W}}$.

$\overline{\mathcal{E_{W}}}=$ all spans not in $\mathcal{E_{W}}$.

if  _is predicting_ then

Return Formulated Input for $(W,e),\forall
e\in\mathcal{E_{W}}\cup\overline{\mathcal{E_{W}}}$.

else

$S(\overline{\mathcal{E_{W}}})=$ sampled $\overline{\mathcal{E_{W}}}$.

Return Formulated Input for $(W,e),\forall e\in\mathcal{E_{W}}\cup
S(\overline{\mathcal{E_{W}}})$.

Algorithm 1 Create

Input: Few-shot Training Dataset $D_{train}$, Model $\mathcal{M}$.

for  _each epoch_ do

$\overline{D_{train}}=\emptyset$

for  _each ( $W,\mathcal{E_{W}}$) in $D_{train}$_ do

$\overline{D_{train}}=\overline{D_{train}}\cup Create(W,\mathcal{E_{W}})$

Train $\mathcal{M}$ on $\overline{D_{train}}$.

Return $\mathcal{M}$

Algorithm 2 Training

Input: Evaluation Dataset $D_{eval}$, Model $\mathcal{M}$.

Final predictions $\mathcal{P}=\emptyset$

for  _each ( $W,\mathcal{E_{W}}$) in $D_{eval}$_ do

$preds=$ $\mathcal{M}(Create(W,\mathcal{E_{W}}))$.

$\mathcal{P}=\mathcal{P}\cup$ Resolve predictions $preds$.

Return $\mathcal{P}$

Algorithm 3 Predicting

##  Appendix B Dataset Statistics and License

We refer the readers to the benchmark paper that standardized the datasets
Huang et al. (2021).

##  Appendix C Hyperparameters

We show the hyper-parameters we use for training the sequence labeling model
and FFF-NER based on BERT in Table 5 for both base and large models. We note
that there are some exceptions on learning rates for our framework. For the
base models when experimenting with $100$ shots, we set the learning rate to
$0.00001$; for the fully supervised training, we set the learning rate to
$0.000002$. For the large models on the Onto dataset, we set the learning rate
to $0.00001$.

| Sequence Labeling | FFF-NER-BERT
---|---|---
Epochs | 100/300 (base/large) | 30
Optimizer | AdamW
Learning Rate | 0.00002 †
Scheduler | Linear, no warmup
Batch Size | 32
Dropout | 0.1
$\alpha$ | N/A | 3
Table 5: Hyper-parameters for sequence labeling and FFF-NER-BERT, for all
experiments in the paper. † there is some exceptions for the learning rate,
explained in text in Section C.

##  Appendix D EntLM

Result Source | Model | Label Source | CoNLL
---|---|---|---
reported | RoBERTa-base | Knowledge Base | 68.6
reproduced | RoBERTa-base | Knowledge Base | 68.40 ($\pm 3.00$)
reproduced | RoBERTa-base | Ground Truth | 65.20 ($\pm 3.03$)
reproduced | BERT-base-cased | Ground Truth | 61.67 ($\pm 2.72$)
Table 6: Reported and Reproduced numbers of EntLM with different model and
label sources.

EntLM needs to identify representative tokens for each class. In their paper,
they follow BOND Liang et al. (2020) that labels the training set based on
distant supervision from external knowledge bases. However, BOND was not
developed for all the datasets in the benchmark, so we take an alternative
approach where we give EntLM ground truth full training set to find
representative tokens.

Arguably, this should be an upper bound for EntLM since we replaced a noisy
source to a clean source. However, we note that there is a performance
difference of our reproduced EntLM from their paper. We ruled out the
differences between theirs and ours in Table 6. We can see that while there is
a difference emerging from the backbone model choice to our surprise, there is
a performance drop when the source of labels comes from ground truth instead
of a noisy distant supervision-based approach. We show the representative
words in Table 7 and note that the actual tokens selected are rather similar
for the two approaches. We argue that EntLM might suffer from instability
issues where a few small changes on the representative tokens (in our case,
even trying to improve it with the ground truth source) can hurt the
performance quite hard.

Source |  Person |  Organization |  Location |  Miscellaneous
---|---|---|---|---
Distant Supervision |  "Michael", "John", "David", "Thomas", "Martin", "Paul" |  "Corp", "Inc", "Commission", "Union", "Bank", "Party" |  "England", "Germany", "Australia", "France", "Russia", "Italy" |  "Palestinians", "Russian", "Chinese", "Dutch", "Russians", "English"
Ground Truth |  "John", "Michael", "David", "Paul", "Thomas", "Mark" |  "Corp", "National", "Inc", "Commission", "St", "Co" |  "Australia", "France", "Germany", "England", "Italy", "Russia" |  "German", "Australian", "British", "American", "European", "Israeli"
Table 7: Representative tokens for classes in EntLM

##  Appendix E SpanNER

Our reproduction of SpanNER on CoNLL2003 and MitMovie with 5-shot supervision
is quite different from their original numbers. There are a few reasons behind
this:

  * •

The dataset, particularly the labeling schema, of MiTMovie is different, while
they used the same dataset names.

  * •

The choice of 5-shot supervision is likely different due to randomness. We
followed the exact same splits in Huang et al. (2021).

  * •

We reported average and std performance across 10 different random 5-shot
supervision, while SpanNER reported average and std performance across 5
different model random initializations. The high variance we reported
indicates that different choice of splits can lead to drastically different
performance.

We believe that our choice of the following Huang et al. (2021) has two
advantages. First, this setting (datasets and data split) is open-sourced and
can be compared with future work more easily. Second, the averaging across
random splits make the result more stable since it accounts for the larger
portion of the variance.

##  Appendix F Sequence Denoising Pre-training

Framework | Language Model | CoNLL | Onto | WNUT17 | MIT Movie | MIT Restaurant
---|---|---|---|---|---|---
Seq Labeling | Roberta-base† | 53.5 | 57.7 | 25.7 | 51.3 | 48.7
Prototype | Roberta-base† | 58.4 | 53.3 | 29.5 | 38.0 | 44.1
FFF-NER | BERT-base-uncased | 67.90 ($\pm 3.95$) | 66.40 ($\pm 1.62$) | 30.48 ($\pm 3.69$) | 60.32 ($\pm 1.12$) | 51.99 ($\pm 2.33$)
BERT-large-uncased | 69.23 ($\pm 3.90$) | 69.43 ($\pm 1.30$) | 34.96 ($\pm 5.07$) | 61.31 ($\pm 2.12$) | 55.01 ($\pm 2.71$)
TemplateNER | BART-large | 61.46 ($\pm 6.46$) | N/A | 11.20 ($\pm 1.09$) | 41.80 ($\pm 1.36$) | N/A
FFF-NER (GENRE) | BART-base | 58.86 ($\pm 1.78$) | 56.12 ($\pm 0.87$) | 26.98 ($\pm 1.64$) | 52.45 ($\pm 2.01$) | 43.34 ($\pm 1.41$)
BART-large | 71.00 ($\pm 2.67$) | 64.40 ($\pm 2.88$) | 41.48 ($\pm 1.58$) | 53.25 ($\pm 1.99$) | 51.00 ($\pm 1.52$)
FFF-NER (TANL) | BART-base | 59.05 ($\pm 1.65$) | 62.13 ($\pm 0.97$) | 34.24 ($\pm 3.13$) | 55.61 ($\pm 1.42$) | 56.76 ($\pm 2.47$)
BART-large | 60.32 ($\pm 2.47$) | 63.17 ($\pm 1.26$) | 36.98 ($\pm 1.37$) | 58.23 ($\pm 1.37$) | 59.84 ($\pm 2.27$)
T5-base | 62.33 ($\pm 2.76$) | 69.27 ($\pm 1.40$) | 33.80 ($\pm 2.91$) | 56.46 ($\pm 1.49$) | 58.85 ($\pm 1.33$)

Table 8: Experiments on N-way 5 shot NER on 5 datasets. The average
performance over ten different folds of seed shots are given, and the standard
deviation is given in parentheses.

We show the performance for models based on sequence denoising pre-trained
models in Table 8. We use GENRE and TANL to illustrate how FFF-NER works with
BART since they are similar by design. We note that it is quite hard to
compare across different pre-training models, but both GENRE and TANL have
established a strong performance improvement against the TemplateNER baseline
and the sequence labeling and prototype baselines in Huang et al. (2021).