The Derivative Degree Sequences of Finite Simple Connected Graphs are Parking
Functions

(Johan Kok)111Affiliation of author(s):
Johan Kok (Tshwane Metropolitan Police Department), City of Tshwane, Republic
of South Africa
e-mail<EMAIL_ADDRESS>
###### Abstract

Parking functions are well researched and interesting results are found in the
listed references and more. Some introductory results stemming from
application to degree sequences of simple connected graphs are provided in
this paper. Amongst others, the result namely, that a derivative degree
sequence,

$d_{d}(G)\in\mathbb{D}_{d}(G)=\\{(\lceil\frac{d(v_{1})}{\ell}\rceil,\lceil\frac{d(v_{2})}{\ell}\rceil,\lceil\frac{d(v_{3})}{\ell}\rceil,...,\lceil\frac{d(v_{n})}{\ell}\rceil)|\ell=d(v_{i}),\forall
i,$ with $d(v_{i})\geq 2\\},$

of a simple connected graph $G$ is a parking function, is presented. We also
introduce the concept of _looping degree sequences_ and the _looping number_ ,
$\xi(G)$. Four open problems are proposed as well.

Keywords: Parking functions, Derivative degree sequence, Looping degree
sequences, Looping number $\xi(G)$,
Recursive parking function.

AMS Classification Numbers: 05C07, 05C38, 05C75, 05C85

##  1 Introduction

Let the simple connected graph $G=(V,E)$ have vertices
$V=\\{v_{1},v_{2},v_{3},...,v_{n}\\}.$ Allow each vertex $v_{i}$ to associate
itself with a singular value $d(v_{i})=j\in\\{0,1,2,3,...,n-1\\},$ as its
preferred value. Allow for $n$ parking spaces $p_{1},p_{2},p_{3},..,p_{n}$ and
allow the the vertices to stream in randomly under the rule that a vertex
$v_{i}$ only occupies a _parking space_ if its preferred value $j$ has _a
vacant parking space_ $p_{j}$ or has $p_{k,(j+1)\leq k\leq n}$ vacant, else
vertex $v_{i}$ _cliffs_. It is known that if
$\alpha=(a_{1},a_{2},a_{3},...,a_{n})\in\mathbb{P}^{n}$ and $b_{1}\leq
b_{2}\leq...\leq b_{n}$ is the increasing representation of $\alpha$ then
$\alpha$ is a parking function if and only if $b_{i}\leq i.$ It is also known
that every permutation of the entries of a parking function is a parking
function. So the converse holds namely, if a sequense of integers say,
$(a_{1},a_{2},a_{3},...,a_{n})$ is not a parking function then no permutation
thereof is a parking function. In addition the strict definition it will be
relaxed so that the _default_ preferred value _zero_ is allowed. So we allow
for cases $\alpha^{*}=(0,a_{1},a_{2},a_{3},...,a_{n})$ to be considered.

For ease of reference let us state a corollary done similarly by Stanley, R.P.
in $[11]$.

######  Corollary 1.1.

Let $\alpha=(a_{1},a_{2},a_{3},...,a_{n})\in\mathbb{P}^{n}$ and $b_{1}\leq
b_{2}\leq...\leq b_{n}$ be the increasing representation of $\alpha$ then
$\alpha$ is a parking function if and only if $b_{i}\leq i,$ and every
permutation of the entries of a parking function is also a parking function.

It is obvious that if $\alpha=(a_{1},a_{2},a_{3},...,a_{n})$ is a parking
function on $n$ _parking spaces_ then
$\alpha^{*}=(0,a_{1},a_{2},a_{3},...,a_{n})$ is a parking function on $(n+1)$
_parking spaces._

##  2 Parking functions in respect of the degree sequences of simple connected
graphs

It is easy to see that if the vertices of a path $P_{n},n\in\mathbb{N}$ are
labelled from _left to right_ consecutively as $v_{1},v_{2},v_{3},...,v_{n}$,
the degree sequence of the path $P_{n},$ namely
$(1,\underbrace{2,2,...2,}_{(n-2)-entries}1)$ is a parking function.
Similarly, easy to see that the degree sequence of the cycle $C_{n},$ namely
$(\underbrace{2,2,2,...,2}_{n-entries})$ is not a parking function since
exactly one vertex $v_{i},i\in\\{1,2,3,...,n\\}$ will _cliff_.

This leads to the observation that if the degree sequence of a spanning
subgraph say, graph $H$ (or at least a spanning tree thereof, [3] and Theorem
2.6) of a simple connected graph $G$ is a parking graph, the degree sequence
of $G$ might not be. However, the converse holds.

######  Theorem 2.1.

If the degree sequence of a simple connected graph $G$ is a parking function
then the degree sequence of any spanning subgraph $H$ of $G$ is a parking
function.

###### Proof.

Let a spanning subgraph of $G$ be graph $H$. Label the vertices of $G$ as
$v_{1},v_{2},v_{3},...,v_{n},$ and assume the degree sequence of $G$ is a
parking function. Then from the definition of a spanning subgrah $H$ we have
that the degree sequence is given by $(d_{H}(v_{1})\leq
d_{G}(v_{1}),d_{H}(v_{2})\leq d_{G}(v_{2}),d_{H}(v_{3})\leq
d_{G}(v_{3}),...,d_{H}(v_{n})\leq d_{G}(v_{n})).$ This implies that the degree
sequence is merely a permutation of the increasing representation of the
sequence $(d_{H}(v_{i})\leq d_{G}(v_{i})\leq d_{H}(v_{i+1})\leq
d_{G}(v_{i+1}),i=1,2,...,n-1).$

Since, $d_{G}(v_{i})\leq i$ it follows that $d_{H}(v_{i})\leq i$ and therefore
a parking function. ∎

From our earlier observation that $\alpha^{*}=(0,a_{1},a_{2},a_{3},...,a_{n})$
is a parking function on $(n+1)$ parking spaces if and only if
$\alpha=(a_{1},a_{2},a_{3},...,a_{n})$ is a parking function on $n$ parking
spaces, it follows that if the degree sequence of a simple connected graph $G$
is a parking function on $n$ parking spaces , then the degree sequence of
$G\cup mK_{1,_{m\rightarrow\infty}}$ is a parking function on
$(n+m),_{m\rightarrow\infty}$ parking spaces.

######  Proposition 2.2.

For a simple connected graph $G$ on n vertices the degree sequence $d(G)$ is a
parking function if $\Delta(G)\leq\lceil\frac{n}{2}\rceil.$

###### Proof.

Consider the graph on _one_ vertex $v_{1}.$ Hence,
$d(v_{1})=0\leq\lceil\frac{1}{2}\rceil.$ With one _parking space_ available
vertex $v_{1}$ can by default, park. So the result holds for $n=1.$ Assume it
holds for any simple connected graph on $n=k$ vertices. Now consider any
simple connected graph $G^{*}=G+{v_{i}v_{k+1}},$ for possibly multiple
$i=1,2,3,...,k.$ such that $d(v_{k+1})\leq\lceil\frac{k+1}{2}\rceil.$ So now,
we provide $k+1$ _parking spaces._

If the $n$ vertices of $G$ stream in at random as before they can occupy
parking spaces as before or a permutation thereof and any one vertex may
occupy the parking space $k+1$ as a result of a change in preferred value as
well. At all times one parking space $p_{i},i\geq\lceil\frac{k+1}{2}\rceil$ is
available. Hence, vertex $v_{k+1}$ with
$d(v_{k+1})\leq\Delta(G)\leq\lceil\frac{n}{2}\rceil\leq\lceil\frac{n+1}{2}\rceil$
always has a _parking space_ to occupy. Through mathematical induction it
follows that for all graphs for which, $\Delta(G)\leq\lceil\frac{n}{2}\rceil,$
the degree sequence $d(G)$ is a parking function.

∎

######  Corollary 2.3.

If the degree sequence of a simple connected graph $G$ is a parking function
then $G$ has at least one pendant vertex.

###### Proof.

Since a vertex parked in _parking space_ $p_{1}$ the result follows from the
definition of connectivity and that of a parking function.

∎

######  Lemma 2.4.

For the Jaco Graph $J_{n}(1)$ we have that
$\Delta(J_{n}(1))\leq\lceil\frac{n}{2}\rceil.$

###### Proof.

Because $\lceil\frac{n}{2}\rceil\leq\lceil\frac{n+1}{2}\rceil$, the result
follows from Lemma 1.2 and Corollary 1.3 in $[10].$ ∎

######  Corollary 2.5.

The degree sequence of a Jaco Graph $J_{n}(1)$ is a parking function.

###### Proof.

Follows immediately from the definition of a Jaco Graph $J_{n}(1)$ in [10] and
Proposition 2.2 above. ∎

######  Theorem 2.6.

The degree sequence of any tree is a parking function.

###### Proof.

Consider the tree on _one_ vertex $v_{1}.$ Hence, $d(v_{1})=0.$ With one
_parking space_ available vertex $v_{1}$ can be default, occupy. So the result
holds for $n=1.$ Assume it holds for any tree on $n=k$ vertices. Now consider
any tree $T^{*}=T+{v_{i}v_{k+1}},i\in\\{1,2,3,...,k\\}.$ So we provide $k+1$
_parking spaces_. If the $n$ vertices of $T$ stream in at random as before
they can occupy parking spaces as before or a permutation therefore. Any
vertex may even occupy parking space $k+1$ as a result of change of preferred
value as well. At all times one parking space $p_{i},i\geq 1$ is available.
Since $d(v_{k+1})=1$ it can occupy any vacant parking space $p_{i},i\geq 1.$
Hence the result follows for any tree on $n=k+1$ vertices and therefore,
through mathematical induction it follows to hold for all trees on
$n\in\mathbb{N}$ vertices. ∎

######  Proposition 2.7.

Consider any tree $T$ on $n\geq 4$ vertices and construct the tree $T^{*}$ by
linking any two vertices $v_{i},v_{j}$ of $T$ such that at least one pendant
vertex remains. Then the degree sequence of $T^{*}$ is a parking function.

###### Proof.

Construct any $T^{*}$ as defined in the proposition. Label the cycle $C$ and
assume it is isomorphic to $C_{m}$. So $T^{*}-C_{m}$ is a forest of $\ell$
trees, $F=\cup_{i}^{\ell}T_{i}$. Consider any tree $T_{j}\in F$ which was
linked to $v_{i}$ in $C_{m}$. Link one pendant $v_{k_{1}}$ to $v_{i}$. Because
all degrees of all vertices in $C_{m}$ equals 2 only one vertex cliffs because
all vertices have to skip parking $p_{1}$. But with the added pendant vertex
an additional parking space $p_{m+1}$ is allowed so all vertices of $C_{m}$
_park_ and the pendant vertex occupies $p_{1}$. Hence the degree sequence of
$C_{m}+v_{k_{1}}$ is a parking function.

By linking another pendant $v_{k_{2}}$ to $v_{i}$ or $v_{k_{1}}$ a similar
result follows because now we provide $m+2$ parking spaces. By smartly linking
pendants recursively, the tree $T_{j}$ can be reconstructed as linked before
to $v_{i}$. So it follows that the degree sequence of $C_{m}+T_{j}$ is a
parking function. Label $C_{m}+T_{j}$ as $G^{*}_{m+1}$. So we proved the
result for $G^{*}_{m+1}$.

Assume the result holds for $G^{*}_{m+x},x\leq\ell$. Also assume that
$G^{*}_{m+x}=C_{m}+(T_{1}+T_{2}+,...,+T_{x})$ has $(m+t)$ vertices. This means
that the $(m+t)$ vertices all park in $(m+t)$ parking spaces. Consider any
other tree $T_{x+1}\in F$ which was linked to $v^{*}_{i}$. By the same
reasoning as before the degree sequence of $G^{*}_{m+x}+v^{*}_{i}$ is a
parking function. So through finite mathematical induction the result follows.
∎

######  Corollary 2.8.

The degree sequence of an unicyclic graph is a parking function.

###### Proof.

Follows directly from Proposition 2.7. ∎

Although we mainly consider simple connected graphs it is useful to note that:

######  Lemma 2.9.

If the respective degree sequences of simple connected graphs
$G_{1},G_{2},G_{3},...,G_{s}$ are all parking functions the _the degree
sequence_ of the graph $H=G_{i}\cup_{\forall j\neq i}^{s}G_{j},$ is a parking
function.

###### Proof.

Let $|V_{1}|=\nu_{1},|V_{2}|=\nu_{2},...,|V_{s}|=\nu_{s}.$ Since $G_{\ell}\cup
G_{q}=G_{q}\cup G_{\ell}$ we have that $H=G_{i}\cup_{\forall j\neq
i}^{s}G_{j}\simeq G_{1}\cup G_{2}\cup...\cup G_{s}.$ Without loss of
generality consider graphs $G_{1}$ and $G_{2}$ and the degree sequence of
$G_{1}$ stream in first. Note that $\nu_{1}+\nu_{2}$ parking spaces are
available. Because the degree sequence of $G_{1}$ is a parking function all
the vertices of $G_{1}$ will park within the first $\nu_{1}$ parking spaces.
Now $\nu_{2}$ parking spaces remain and numbered
$(\nu_{1}+1),(\nu_{1}+2),(\nu_{1}+3),...,(\nu_{1}+\nu_{2}).$

Since the degree sequence of $G_{2}$ is a parking function a vertex $v_{i}$ of
$G_{2}$ initially occupied a parking space $p_{j},1\leq p_{j}\leq\nu_{2}.$ The
equivalent parking space in $H_{2}=G_{1}\cup G_{2}$ that is available is
numbered, $p_{j}+\nu_{1}\leq\nu_{1}+\nu_{2}.$ Hence all vertices of $G_{2}$
will find parking space. So the result holds for $H_{2}=G_{1}\cup G_{2}.$

Assume it holds for $H_{t}=G_{1}\cup G_{2}\cup...\cup G_{t}.$ Now consider the
graph $H_{t+1}=G_{1}\cup G_{2}\cup...\cup G_{t}\cup G_{t+1}.$ Since,
$H_{t+1}=G_{1}\cup G_{2}\cup...\cup G_{t}\cup G_{t+1}=(G_{1}\cup
G_{2}\cup...\cup G_{t})\cup G_{t+1},$ the results holds for the graph
$H_{t+1}$ and it follows immediately to hold in general. ∎

######  Definition 2.1.

For a simple connected graph $G$, define the set of derivative degree
sequences,

$\mathbb{D}_{d}(G)=\\{(\lceil\frac{d(v_{1})}{\ell}\rceil,\lceil\frac{d(v_{2})}{\ell}\rceil,\lceil\frac{d(v_{3})}{\ell}\rceil,...,\lceil\frac{d(v_{n})}{\ell}\rceil),\ell=d(v_{i}),\forall
i,$ with $d(v_{i})\geq 2\\}.$

The next theorem is of importance.

######  Theorem 2.10.

(Daneel’s theorem)222In memory of my young friend who so untimely (11
Spetember 2013, age 25), parked his soul somewhere in space. A derivative
degree sequence $d_{d}(G)\in\mathbb{D}_{d}(G)$ is a parking function.

###### Proof.

The derivative degree sequence with _largest_ entries is certainly,
$(\lceil\frac{d(v_{i})}{min(d(v_{i}))_{d(v_{i})\geq 2}}\rceil,i=\\\ \\\
1,2,3,...,n).$ This implies that if
$(\lceil\frac{d(v_{i})}{min(d(v_{i}))_{d(v_{i})\geq 2}}\rceil,i=1,2,3,...,n),$
can be shown to be

a parking function then all others derivative degree sequences are as well
since, $\lceil\frac{d(v_{i})}{\ell}\rceil\leq\\\ \\\
\lceil\frac{d(v_{i})}{min(d(v_{i}))_{d(v_{i})\geq 2}}\rceil,\ell=d(v_{i})\geq
2,\forall i.$ (See Corollary 1.1).

For any simple connected graph we have that if
$\lceil\frac{d(v_{i})}{min(d(v_{i}))_{d(v_{i})\geq 2}}\rceil$ for exactly one
vertex

then $\Delta(G)\leq(n-2).$ So in general $\Delta(G)\leq(n-2)$ for all simple
connected graphs with

$\lceil\frac{d(v_{i})}{min(d(v_{i}))_{d(v_{i})\geq 2}}\rceil\geq 2.$

The above implies that if $n$ is even then $(n+2)$ _parking spaces_ are
available beyond the largest _preferred value,_ $\lceil\frac{n-2}{2}\rceil.$
So in all cases we have that
$\lceil\frac{d(v_{i})}{min(d(v_{i}))_{d(v_{i})\geq 2}}\rceil\leq
i,i=1,2,3,...,n,$ which implies the derivative degree sequence to be a parking
function.

It also implies that if $n$ is uneven then $(n+1)$ _parking spaces_ are
available beyond the largest _preferred value,_ $\lceil\frac{n-2}{2}\rceil.$

So in all cases we have that
$\lceil\frac{d(v_{i})}{min(d(v_{i}))_{d(v_{i})\geq 2}}\rceil\leq
i,i=1,2,3,...,n,$ which implies the derivative degree sequence to be a parking
function.

Finally then, since $(\lceil\frac{d(v_{i})}{min(d(v_{i}))_{d(v_{i})\geq
2}}\rceil,i=1,2,3,...,n)$ is a parking function for both _n even or uneven,_
the result that a derivative degree sequence $d_{d}(G)\in\mathbb{D}_{d}(G)$ of
a simple connected graph $G$ is a parking function, follows. ∎

###  2.1 Looping degree sequences of
$G-\\{v_{1},v_{2},v_{3},...,v_{r}\\},r\leq n-1$

_Looping degree sequences_ are found by allowing the degree sequence of a
simple connected graph $G$ to stream in and when the maximum set of vertices
$T=\\{v_{t}|v_{t}$ _parks_ $\\}$ parks, the degree sequence reduces to the
degree sequence of $G-T.$ Recursively then, when on the first stream vertex
$v_{r}$ parks, the degree sequence reduces to the degree sequence of
$G-\\{v_{1},v_{2},v_{3},...,v_{r}\\},r\leq n-1.$ Now the first _loop_ streams
with the degree sequence of $G-T.$ After all vertices find parking we refer to
the set $\mathbb{R}_{d}$ of recursive degree sequences as a _recursive parking
function_.

Example: For the complete graph $K_{n},n$ even the _recursive parking
function_ is given by the set
$\mathbb{R}_{d}=\\{\underbrace{(n-1,n-1,n-1,...,n-1)}_{n-entries},\underbrace{(n-3,n-3,n-3,...,n-3)}_{(n-2)-entries},...,(1,1)\\}.$
Also see Lemma 2.12 (Case 1).

######  Theorem 2.11.

For any simple connected graph $G$ on $n$ vertices the recursive parking
function is a finite set.

###### Proof.

It is obvious that if the degree sequence of a simple connected graph $G$ is a
parking function, the result holds since such a degree sequence is a recursive
degree sequence in itself.

Furthermore, it is obvious that we only have to consider the extermal case
where it is found that on the first stream and subsequent looping streams,
only one vertex at a time finds parking. All other cases show an improvement
in that the number of loops required decreases. It is also known that if the
degree sequence of a simple connected graph $G$ is not a parking function
then, neither the permutations thereof are parking functions. However, any
first vertex of the degree sequence stream or of a permutation thereof, will
park since $n$ parking spaces are available and $\Delta(G)\leq n-1,$ and
therefore any $d(v_{i})\leq n-1,\forall i.$

Therefore, on the next round of streaming (_looping_), $n-1$ parking spaces
are available whilst $\Delta(G-v_{1})\leq n-2.$ This means that any second
vertex of the _recursive degree sequence_ or of a permutation thereof, can
park. After $n-1$ recursions a single _(last)_ vertex remains say, $v_{k}$
with $d(v_{k})=0,$ and exactly _one_ parking space is left. It means that by
the default preferred value convention and the parking rule, vertex $v_{k}$
may park at any available _parking space_ , $p_{i},1\leq i\leq n$ which is not
occupied. It also means that for any simple connected graph $G$ the set of
recursive degree sequences or any permutation thereof (_implicitly all_
$(n+1)^{n-1}$ _cases covered_), are a finite recursive parking function
because all vertices necessary find parking. ∎

###  2.2 Looping number $\xi(G)$ of a simple connected graph, $G$

The _looping number_ $\xi(G)$ of a simple connected graph $G$ is the _maximum_
number of loops required for all vertices to park. Clearly, $\xi(G)=0$ if and
only if the degree sequence of $G$ is a parking function.

######  Lemma 2.12.

For a simple connected graph $G$ on n vertices we have,
$0\leq\xi(G)\leq\lfloor\frac{n-1}{2}\rfloor.$

###### Proof.

If the degree sequence of a simple connected graph $G$ is a parking function,
then $\xi(G)=0.$

So we consider the cases where the degree sequences of $G$ are not parking
functions. Since, the degree sequence of $G-v_{i}$ equals the degree sequence
of $(G+v_{i}v_{j})_{j\neq i,v_{j}\in V(G)}-v_{i},$ it follows that
$\xi(G)\leq\xi(K_{n}).$ Hence $\xi(K_{n})$ provides the _upper bound_.

Case 1: Let $n$ be even. It follows that in $K_{n}$ we have
$d(v_{i})=n-1,\forall i.$ Hence, on first streaming exactly two vertices can
park in $p_{n-1}$ and $p_{n}$ whilst the $n-2$ vertices of $K_{n-2}$ loops
(_first loop_). Thereafter, exactly two more vertives (_degree_ = $(n-2)-1)$
can park in $p_{n-3}$ and $p_{n-2}$ whilst the $n-4$ vertices of $K_{n-4}$
loops (_second loop_). Recursively after exactly $\frac{n}{2}-2$ _loops_ only
$K_{2}$, with exactly two parking spaces $p_{1},p_{2}$ remain. Hence, after
one more loop or, after $(\frac{n}{2}-2)+1=\lfloor\frac{n-1}{2}\rfloor$
_loops_ all vertices park.

Case 2: Let $n$ be uneven. The proof follows similar to Case 1 except that
recursively after exactly $\frac{n}{2}-2$ _loops_ , only $K_{1}$, with exactly
one parking space $p_{1}$ remain. Hence, after one more loop or, after
$(\frac{n}{2}-2)+1=\lfloor\frac{n-1}{2}\rfloor$ _loops_ all vertices park. ∎

Note that if the respective degree sequences of graphs $G_{1}$ and $G_{2}$ are
parking functions the degree sequence of $G_{1}+G_{2}$ is not necessarily a
parking function. It remains an open problem for which graphs the result will
hold.

######  Corollary 2.13.

We have that
$\xi(\cup_{i\in\mathbb{N}}P_{i})=\xi(P_{\sum\limits_{i\in\mathbb{N}}}).$

###### Proof.

Consider $P_{n}$ and $P_{m}$, $(n\geq 1)\in\mathbb{N},(m\geq 1)\in\mathbb{N}.$
The vertices of path $P_{n}$ can park in the first $n$ parking spaces and so
can the vertices of $P_{m}$ park in the following $n+1$ to $n+m$ parking
spaces or vice versa. Equally so can the vertices of $P_{n+m}$ park in $(n+m)$
parking spaces because we have in $P_{n+m}$ that, $d(v_{n})=2$ and
$d(v_{n+1})=2.$ Hence, these two vertices can still park in parking spaces,
$n$ and $n+1.$ So the result follows for $P_{n}$ and $P_{m}$. Through
induction it follows that
$\xi(\cup_{i\in\mathbb{N}}P_{i})=\xi(P_{\sum\limits_{i\in\mathbb{N}}}).$ ∎

Now the next theorem can be settled.

######  Theorem 2.14.

For the respective degree sequences of two simple connected graphs $G_{1}$ and
$G_{2}$ we have that:

(a) if both degree sequences are parking functions, the looping number
$\xi(G_{1}+G_{2})\leq 1$,
(b) if at least one degree sequence is not a parking function, the looping
number $\xi(G_{1}+G_{2})\leq\xi(G_{1})+\xi(G_{2})+1.$

###### Proof.

(a) Consider the simple connected graphs $G_{1}$ and $G_{2}$ on $n$ and $m$
vertices, respectively. Assume both degree sequences of $G_{1}$ and $G_{2}$
are parking functions. Because $G_{1}+G_{2}=G_{2}+G_{1}$ we only have to
consider the case $G_{1}+G_{2}.$ Without loss of generality assume $n\leq m.$

Case a(1). Assume that all the vertices of graph $G_{1}$ stream in randomly,
first. Then as before these vertices will park in the consecutively labelled
parking spaces $p_{1+m},p_{2+m},...,p_{n+m}.$ Now the vertices of $G_{2}$
stream in randomly and since the remaining parking spaces are labelled
$p_{1},p_{2},...,p_{n},p_{(n+1)},p_{(n+2)},...,p_{n+(m-n)}$ some vertices of
$G_{2}$ can park by definition, and some (or all) may _cliff_ to enter loop
one. On the first loop the graph $G_{1}+G_{2}$ reduces to at most $G_{2}$ or a
subgraph of $G_{2}$ and since the number vacant parking spaces equals the
number of vertices $v_{i}\in V(G_{2})$ that cliffed, those vertices can all
park by definition. It implies that $\xi(G_{1}+G_{2})=1.$ Since no cliffing
occurs for $K_{1}+K_{1}$ the result suggests that if both the respective
degree sequences of two simple connected graphs $G_{1}$ and $G_{2}$ are
parking functions, then $\xi(G_{1}+G_{2})\leq 1.$

Case a(ii) Assume that all the vertices of graph $G_{2}$ stream in randomly,
first. Then as before these vertices will park in the consecutively labelled
parking spaces $p_{1+n},p_{2+n},...,p_{m+n}.$ Since exactly $n$ parking spaces
labelled, $p_{1},p_{2},...,p_{n}$ remain vacant and only the vertices of
$G_{1}$ with the reduces degree sequence of $G_{1}$ streams in on loop 1, all
vertices can park. As before we have that for $K_{1}+K_{1}$ no cliffing occurs
so the result suggests that if both the respective degree sequences of two
simple connected graphs $G_{1}$ and $G_{2}$ are parking functions, then
$\xi(G_{1}+G_{2})\leq 1.$

Case a(iii) Also let any vertex say, $v_{k}\in V(G_{1})$ stream in first. As
an extremal case assume vertex $v_{k}$ parked in the space $p_{n}$ initially.
Now the degree of $v_{k}$ increased by $m$ so it can park in, at most, the
parking space $p_{n+m}$ in $G_{1}+G_{2}.$ Now as the next extremal case assume
without loss of generality that any vertex say, $v_{\ell}\in V(G_{2})$ streams
in. Certainly then, since the degree of vertex $v_{\ell}\in V(G_{2})$ has
increased by $n$ it can park in, at most, the vacant parking space numbered
$(m-n)$. So this is possible for all vertices of the graph $G_{1}+G_{2}$
streaming in randomly, allowing for some vertices of both $V(G_{1})$ and
$V(G_{2})$ to cliff. However, on streaming loop 1, all vertices park because
the degree values decrease by either $n$ or $m.$ As before we have that for
$K_{1}+K_{1}$ no cliffing occurs so the result suggests that if both the
respective degree sequences of two simple connected graphs $G_{1}$ and $G_{2}$
are parking functions, then $\xi(G_{1}+G_{2})\leq 1.$

Since all cases have been argued and all the suggestions are assertive, the
partial result that for some graphs $\xi(G_{1}+G_{2})<\xi(G_{1})+\xi(G_{2}),$
follows conclusively.

(b) We know that $\xi(K_{n})=1,\forall n\in\mathbb{N}.$ Since
$K_{n+m}=K_{n}+K_{m}$ we have that $\xi(K_{n+m})=1<\xi(K_{n})+\xi(K_{m})$ so
the inequality holds. We also know that $\xi(C_{n})=1,\forall n\in\mathbb{N}.$
For $C_{n}+C_{m}$ we have that $d_{C_{n}}(v)=2+m,$ $\forall v\in V(C_{n})$ and
$d_{C_{m}}(u)=2+n,$ $\forall u\in V(C_{m}).$ Also assume without loss of
generality that $n\geq m.$

Case (b)(i). Let the vertices of $C_{n}$ stream in first. It implies that
exactly $n-1$ vertices of $C_{n}$ can park in _parking spaces_
$p_{(2+m)},p_{(2+m)+1},...,p_{(n+m)}$. On loop one we have the graph
$K_{1}+C_{m}$ looping. Since the graph has no pendant vertex a further loop
will be required, leaving exactly $P_{2}$ looping into parking. Hence
$\xi(C_{n}+C_{m})=2.$ It suggests that for some graphs equality
$\xi(G_{1}+G_{2})=\xi(G_{1})+\xi(G_{2})$, holds.

Case (b)(ii). Let the vertices of $C_{m}$ stream in first. It implies that
exactly $m-1$ vertices of $C_{m}$ can park with exactly one vertex of $C_{n}$
parking as well. On loop one we have the graph $K_{1}+P_{n-1}$ looping. Since
the graph has no pendant vertex a further loop will be required. Considering
all random streaming we are left with either $K_{1}$ and one vacant parking
space, or $K_{1}\cup K_{1}$ and two vacant parking spaces or $P_{2}$ and two
vacant parking spaces. It suggests that for some graphs, equality
$\xi(G_{1}+G_{2})=\xi(G_{1})+\xi(G_{2})$, holds.

Since all cases have been argued and all the suggestions are assertive, the
partial result that for some graphs $\xi(G_{1}+G_{2})=\xi(G_{1})+\xi(G_{2})$,
follows conclusively.

(c) Consider the _tetrahedron_ , $G_{1},$ [3] and the path $P_{n}$. We have
that $d_{G_{1}}(v)=3+n,$ $\forall v\in V(G_{1})$ and $d_{P_{n}}(u)=5$ (pendant
vertices) or $6$. Any random streaming of vertices allows exactly $n$ vertices
to park and on stream one, a _tetrahedron_ loops. Hence loop two is required
because the tetrahedron has no pendant vertices. It follows that for some
graphs, $\xi(G_{1}+P_{n})=2=(0+1)+1=\xi(G_{1})+\xi(P_{n})+1.$

So we could show for specific cases that
$\xi(G_{1}+G_{2})\leq\xi(G_{1})+\xi(G_{2})+1.$

To settle the theorem we need to show that
$\xi(G_{1}+G_{2})>\xi(G_{1})+\xi(G_{2})+1,$ is false in general. In terms of
the definition of $\xi(G)$ we know that $K_{n},n\in\mathbb{N}$ is the most
complex graph and we know that $G_{1}+G_{2}$ is always a subgraph of
$K_{(n+m)}$. It easily follows that
$\xi(K_{s})=\xi(K_{(n+m)})=\xi(K_{n}+K_{m})=\xi(K_{n})+\xi(K_{m}).$ In fact
the $"+1"$ only follows if the degree sequence of only one graph is a parking
function. Hence, $\xi(G_{1}+G_{2})>\xi(G_{1})+\xi(G_{2})+1$ is false in
general.

So the result of the theorem follows. ∎

###  2.3 Appendix III of Bondy and Murty $[3]$

As stated in Bondy and Murty $[3]$, there are a number of graphs which are
interesting. We will present the looping number of some of those mentioned.

2.3.1 Frucht graph ([8], 1949)

For the _Frucht graph,_ $F_{1}$ on first stream, any 10 of the 12 vertices
streaming at random will park and always leave two isolated (disjoint)
vertices say, $v_{i}$ and $v_{j}$. Since $d(v_{i})=d(v_{j})=0$ they may both
occupy any of the two remaining vacant parking spaces on loop one. Hence,
$\xi(F_{1})=1.$

2.3.2 Folkman graph ([6], 1967)

Folkman proved that every edge, but not vertex-transitive regular graph, has
at least twenty vertices. The Folkman graph $F_{2}$ has exactly twenty
vertices, the best possible result. Each vertex $v_{i}$ has $d(v_{i})=4.$ So a
set of $|T|=17$ vertices streaming randomly on the first stream will park
leaving three vertices in $F_{2}-T$ of which at most, only one vertex say,
$v_{i}$ will have $d(v_{i})=2$ and the other two with degree 0. Hence, on loop
one all vertices will park. So, $\xi(F_{2})=1.$

2.3.3 The platonic octahedron graph ([7], 1967)

The graph is 4-regular on six vertices. Hence any three vertices can park on
the first stream leaving either $C_{3}$ or $P_{3}$ to loop. Since parking
spaces $p_{1},p_{2}$ and $p_{3}$ are available only two vertices can park on
loop one in the case $C_{3},$ loops. So, $\xi=2.$

We further observe that
$\mathbb{R}_{d}=\underbrace{\\{(4,4,4,4,4,4),(2,2,2),(0)\\}}_{C_{3}-loops}$ or
$\underbrace{\\{(4,4,4,4,4,4),(1,2,1)\\}}_{P_{3}-loops}.$ It shows that the
_looping number_ is dependent on the permutations of vertex streaming per
loop.

[Open problem: For which graphs will we have that, if the respective degree
sequences of graphs $G_{1}$ and $G_{2}$ are parking functions then the degree
sequence of $H=G_{1}+G_{2}$ is a parking function as well? $K_{1}+K_{1}=P_{2}$
is an example.]

[Open problem: Consider the simple connected graphs
$G_{1},G_{2},G_{3},...,G_{n}.$ What can be said about $\xi(\cup_{(1\leq i\leq
n)}G_{i})?$]

[Open problem: If for the simple connected graphs $G$ and
$H_{i},i=1,2,3,...,k$ at least one degree sequence is not a parking function,
it is expected that the looping number, $\xi(G+H_{i,\forall
i})\leq\xi(G)+\sum\limits_{\forall i}\xi(H_{i})+1.$ Is the conjecture true?]

[Open problem: Define the first line graph of a simple connected graph $G$ the
graph $G^{\ell=1}$. We know that the degree sequence of $P_{n}$ is a parking
function. We also know that $P^{\ell\rightarrow\infty}_{n}\rightarrow P_{1}$
of which the degree function is a parking function. We also know that
$C^{\ell\rightarrow\infty}_{n}\rightarrow C_{n}$ of which the degree sequence
is not a parking function.

(a) If it is true that the degree sequence of a simple connected graph $G$ is
a parking function, is it consequently true that the degree sequence of the
line graph $G^{\ell\rightarrow\infty}$ is a parking function as well ?

(b) If it is true that the degree sequence of a simple connected graph $G$ is
not a parking function, is it consequently true that the degree sequence of
the line graph $G^{\ell\rightarrow\infty}$ is not a parking function as well
?]

_Open access: 333To be submitted to the _Pioneer Journal of Mathematics and
Mathematical Sciences.__ This paper is distributed under the terms of the
Creative Commons Attribution License which permits any use, distribution and
reproduction in any medium, provided the original author(s) and the source are
credited.

References (Limited)

$[1]$ Aker, K., Can, M.B., _From parking functions to Gelfand pairs_ ,
Proceedings of the American Mathematical Society, Vol 140 (2012), no. 4, pp
1113-1124.
$[2]$ Armstrong, D., Garsia, A., Haglund, J., Rhoades, B., Sagan, B.,
_Combinatorics of Tesler matrices in the theory of parking functions and
diagonal harmonics,_ Journal of Combinatorics, Vol 3 (2012), no.3, pp 451-494.
$[3]$ Bondy, J.A., Murty, U.S.R., _Graph Theory with Applications,_ Macmillan
Press, London, (1976).
$[4]$ Chebikin, D., Postnikov, A., _Generalised parking functions, descent
numbers, and chain polytopes of ribbon posets_ , Advances in Applied
Mathematics, Vol 44 (2010), no. 2, pp 145-154.
$[5]$ Dotsenko, V., _Parking functions and vertex operators_ , Selecta
Mathematica, Vol 14 (2009), no. 2, pp 229-245.
$[6]$ Folkman, J., _Regular line-symmetric graphs,_ Journal of Combinatorial
Theory, Vol 3 (1967), pp 215-232.
$[7]$ Frechet, M., Fan, K., _Initiation to Combinatorial Topology,_ Prindle,
Weber and Schmidt, Boston, (1967).
$[8]$ Frucht, R., _Graphs of degree three with a given abstract group,_
Canadian Journal of Mathematics, Vol 1 (1949), pp 365-378.
$[9]$ Hopkins, S., Perkinson, D., _Bigraphical arrangements_ , arXiv:
1212.4398v2 [math.CO], 2012.
$[10]$ Kok, J., Fisher, P., Wilkens, B., Mabula, M., Mukungunugwa, V.,
_Characteristics of Finite Jaco Graphs, $J_{n}(1),n\in\mathbb{N}$_, arXiv:
1404.0484v1 [math.CO], 2 April 2014.
$[11]$ Shin, H., _A New Bijection Between Forests and Parking Functions_ ,
arXiv: 0810.0427v2 [math.CO], 2010.
$[12]$ Stanley, R.P., _Parking Functions_. Department of Mathematics, M.I.T.,
Cambridge, MA 02139.


# LinkNER: Linking Local Named Entity Recognition Models to
Large Language Models using Uncertainty

Zhen Zhang  0000-0001-5134-8566 College of SoftwareNankai
UniversityTianjinChina300350<EMAIL_ADDRESS>,  Yuhua Zhao
0009-0001-5160-2859 College of SoftwareNankai UniversityTianjinChina300350
<EMAIL_ADDRESS>,  Hang Gao  0000-0003-4797-3072 College of
Artificial IntelligenceTianjin University of Science and
TechnologyTianjinChina300222<EMAIL_ADDRESS>and  Mengting Hu
0000-0003-1536-5400 College of SoftwareNankai UniversityTianjinChina300350
<EMAIL_ADDRESS>
(2024)

###### Abstract.

Named Entity Recognition (NER) serves as a fundamental task in natural
language understanding, bearing direct implications for web content analysis,
search engines, and information retrieval systems. Fine-tuned NER models
exhibit satisfactory performance on standard NER benchmarks. However, due to
limited fine-tuning data and lack of knowledge, it performs poorly on unseen
entity recognition. As a result, the usability and reliability of NER models
in web-related applications are compromised. Instead, Large Language Models
(LLMs) like GPT-4 possess extensive external knowledge, but research indicates
that they lack specialty for NER tasks. Furthermore, non-public and large-
scale weights make tuning LLMs difficult. To address these challenges, we
propose a framework that combines small fine-tuned models with LLMs (LinkNER)
and an uncertainty-based linking strategy called RDC that enables fine-tuned
models to complement black-box LLMs, achieving better performance. We
experiment with both standard NER test sets and noisy social media datasets.
LinkNER enhances NER task performance, notably surpassing SOTA models in
robustness tests. We also quantitatively analyze the influence of key
components like uncertainty estimation methods, LLMs, and in-context learning
on diverse NER tasks, offering specific web-related recommendations.

Information extraction; uncertainty estimation; robustness; large language
models

††copyright: acmlicensed††journalyear: 2024††doi:
10.1145/3589334.3645414††conference: Proceedings of the ACM Web Conference
2024; May 13–17, 2024; Singapore, Singapore.††booktitle: Proceedings of the
ACM Web Conference 2024 (WWW ’24), May 13–17, 2024, Singapore,
Singapore††price: 15.00††isbn: 979-8-4007-0171-9/24/05††submissionid:
563††ccs: Computing methodologies Information extraction

##  1\. Introduction

Named entity recognition (NER) is a core information extraction task in
natural language processing (NLP), where named entities (NEs) are human-
defined words or phrases whose entity types are associated with contextual
semantics. For instance, in the sentence ”New York never sleeps, a city
teeming with diversity”, the phrase ”New York” is defined as the ”Location”
entity. NER models require accurate entity boundary detection and entity type
classification for correct recognition. NER extracts structured information
from unstructured data, enabling more effective information retrieval and
analysis. Therefore, it plays a crucial role in various domains such as web
search (Guo et al., 2009a), relation extraction (Shen et al., 2021), and
conversational agents (Zhou et al., 2016). With the emergence of pre-trained
models (PLMs, e.g. BERT (Devlin et al., 2019)), fine-tuning models based on
PLMs are suitable for various NLP tasks, which also promotes significant
progress in NER tasks.

Recent studies show that NER models face challenges in predicting entities
that are not encountered during training (Fu et al., 2020; Lin et al., 2020;
Wang et al., 2022), encompassing both Out-of-Vocabulary (OOV) and Out-of-
Domain (OOD) entities. These challenges frequently arise in web social media
and the medical domain (Derczynski et al., 2017; Jin et al., 2014).
Consequently, NER models’ ability to detect and classify decreases when they
encounter these entities, which we attribute to the ”lack of knowledge” of
fine-tuned small models. An effective technique, as proposed by Zhang and Yang
(2018), involves addressing OOV/OOD issues by integrating entity vocabulary
through the incorporation of external knowledge. However, it is worth noting
that external knowledge may not always be readily accessible or at hand.
Strategies for addressing this challenge also involve methods that consider
data distributions (Wang et al., 2022; Zhang et al., 2023), but these methods
still suffer from drastic performance gaps on various disturbing unseen
entities (even the SOTA method achieves only a 54.86% F1 score on the social
media dataset WNUT’17 (Derczynski et al., 2017) with unseen entities).
Therefore, current NER models obviously fail to meet the requirements for
system availability and reliability in an open environment.

The advent of large language models (LLMs), such as GPT-3 (Brown et al.,
2020), Bloom (Scao et al., 2022) and Llama 2 (Touvron et al., 2023), has
brought about a turning point for worldwide artificial intelligence, and led
to significant progress in a wide range of NLP tasks. With their vast search
space and extensive training data, LLMs possess a huge amount of knowledge and
have the potential to address OOV/OOD entities. However, while they excel at
understanding context and conversational language generation, LLMs are less
performed in NER. Recent evaluation indicates that there is a significant
performance gap between LLMs and SOTA NER methods (shown in Table 1), though
LLMs adopt a few in-context samples as prompts (Han et al., 2023). This may be
caused by a lack of specific learning and explicit understanding of the NER
task. We attribute this limitation to the LLM’s ”lack of specialty”.
Furthermore, LLMs have a substantial number of parameters, some of which
remain undisclosed. This presents significant challenges when fine-tuning them
to achieve the ”specialty” of NER. Thus, directly tackling NER tasks using NER
models or LLMs alone remains a challenging endeavor.

Table 1. Performance comparison of GPT-3.5 and SOTA methods on NER dataset. The evaluation metric is the F1 score (%), and Ratio@SOTA$\in[0\%,100\%]$ refers to the extent of GPT-3.5 reaching the SOTA score. Setting | CoNLL’03 | Onto. 5.0 | JNLPBA
---|---|---|---
GPT-3.5 | 67.08 | 51.15 | 41.25
Ratio@SOTA | 70.95% | 56.52% | 52.57%

To address these challenges, we propose LinkNER, shown in Figure 1, a novel
approach that enables a local NER model to link synergistically with a black-
box large language model (GPT-3.5 and Llama 2-Chat are used in this study),
thus making the recognition of various entities more robust. Specifically, we
first fine-tune a local NER model. Generally, when equipped with an
uncertainty estimation method, the local model can assume any architecture. In
this study, we select the commonly used SpanNER framework to equip four
uncertainty estimation techniques (based on Confidence, Entropy, Monte-Carlo
Dropout (Gal and Ghahramani, 2016), and Evidential-based learning (Zhang et
al., 2023)) for experiments and analysis. As a result, the local model can
recognize simple entities, and detect difficult and unseen entities by
assigning them higher uncertainty.

Then, during the inference phase, LLM is employed to further classify the
difficult entities. Uncertainty serves as the catalyst for LLM to undergo a
paradigm shift in NER tasks, transitioning from entity recognition to entity
classification. The final prediction combines the results of the local model
and LLM. Consequently, the remarkable generalization ability of LLM overcomes
the challenge of lack of knowledge in local models. At the same time, the
distribution learned by local models addresses the lack of specialty challenge
faced by LLM, making the two models mutually complementary. To evaluate the
effectiveness of LinkNER, we conduct extensive experiments on various datasets
and achieve impressive results, and gave recommendations for different LinkNER
components on web-related scenarios.

Our contributions are summarized as follows:

  * •

To the best of our knowledge, LinkNER is the first work exploring how to fine-
tune models synergistically with LLMs for NER tasks.

  * •

We propose a linking strategy RDC based on uncertainty estimation, which
guarantees that two models can complement each other, so as to solve the
challenges of ”lack of knowledge” in local models, and ”lack of specialty” in
LLMs.

  * •

We conduct extensive experiments on LinkNER’s benchmarks and robustness tests,
and it is notably superior to the current SOTA in robustness tests such as web
social media and medical. Moreover, we study the impact of uncertainty
estimation methods, LLMs, and in-context learning on LinkNER, while also
providing application suggestions.

Figure 1. Illustration of LinkNER processing the NER task. If the local NER
model is uncertain about its output (see the second case), the linked LLM
undergoes further classification to determine the final result.

##  2\. Related Work

Named Entity Recognition. In web search, where NEs can be used to filter or
re-rank to the top. For example, Guo et al. (2009b) use query log data and
latent dirichlet allocation to adopt a probabilistic method to complete the
NER query task. Fetahu et al. (2021) enhance existing multilingual
Transformers based on external dictionary knowledge so that they can
simultaneously distinguish and process entity and non-entity query terms in
multiple languages.

Recently, NER systems are undergoing a paradigm shift (Fu et al., 2021; Wang
et al., 2022; Li et al., 2022a), in which the span-based performs better on
sentences with OOV words and entities with medium length (Fu et al., 2021). In
the traditional sequence labeling paradigm, Li et al. (2021) propose a
boundary-aware bidirectional neural network to solve problems such as boundary
label sparsity. Recent studies (Lin et al., 2020; Agarwal et al., 2021; Wang
et al., 2022) indicate that test entities present in the training set
consistently perform better, while unseen entities lead to lower performance.
The current strategy incorporates external knowledge to reduce reliance on
word embeddings (Li et al., 2018; Zhang and Yang, 2018), enabling models to
make more semantic-based decisions. Meanwhile, some works focus on
distribution-based strategies to solve unseen entity recognition. For example,
MINER (Wang et al., 2022) utilizes mutual information to handle OOV NER tasks
and achieve high performance. Additionally, several studies focus on
uncertainty-based unseen entity detection (Lei et al., 2022; Zhang et al.,
2023). For example, Lei et al. (2022) utilize deep learning combined with
evidence theory (Jøsang, 2016) to achieve entity uncertainty estimation. Zhang
et al. (2023) combine uncertainty-guided reweighting and regularization
techniques with evidence theory to improve the NER system’s ability to detect
unseen entities.

Language Model Plug-ins. LLMs currently demonstrate the ability to learn
contextually, and external tools also enhance their capabilities (Brown et
al., 2020). One example is HuggingGPT (Shen et al., 2023) utilizes ChatGPT for
task planning and selects a model based on the available feature description
in Hugging Face. It executes each subtask using the selected AI model and
aggregates responses based on the execution results. Toolformer (Schick et
al., 2023) introduces special symbols that allow LLMs to call external APIs
and accomplish tasks. In the NER tasks, Han et al. (2023) observe that GPT-3.5
lacks sensitivity to entity order and struggles to accurately understand the
subject-object relationship of entities. Xu et al. (2023) use small models as
plug-ins for LLMs to improve model performance on supervised tasks, as well as
improve model multilingualism and interpretability.

##  3\. Preliminary

In this section, we present the problem formulation for NER. Additionally, we
introduce uncertain probabilistic modeling methods (Sensoy et al., 2018) and
optimization functions (Zhang et al., 2023) to construct local models.

###  3.1. Local Model and Problem Definition

Local Model. In this study, we choose SpanNER (Fu et al., 2021) as the local
model for the following reasons:

  1. (1)

Web content is noisy and diverse, including variations in writing style,
spelling errors, and inconsistent formatting. Span-based models tend to be
more robust to such changes because they focus on extracting coherent spans of
text rather than labeling individual tokens (Zhang et al., 2023).

  2. (2)

Downstream programs such as web retrieval, dialogue, relationship extraction,
etc., have high requirements on entity boundaries. Compared with other NER
paradigms, SpanNER reduces the ambiguity of boundary expressions (Wang et al.,
2022).

Problem Definition. Specifically, Given a sentence of length $n$, denoted as
$\mathbf{x}=\\{x^{1},x^{2},...,x^{n}\\}$. For the commonly used span-based NER
modeling method, SpanNER (Fu et al., 2021) enumerates all candidate spans
$S=\\{s^{1},s^{2},...,s^{m}\\}$, where $m$ represents the set size.
$s=\\{x^{e},x^{e+1},...,x^{d}\\}$ represents the entity span between the start
$x^{e}$ and the end $x^{d}$, and the maximum length of the span within the
predetermined range is $l$. Each span is assigned an entity label $c$, where
$c$ belongs to the label set $c\in[1,C]$. Among these test entities, if the
data distribution is the same as that of the training set, it is called in-
domain (ID). Conversely, if the data distribution differs from that of the
training set, it is termed OOD. Entities not present in the model’s vocabulary
are referred to as OOV entities. In general, OOD and OOV entities represent
unseen test entities for the model, and the performance reflects the
robustness of the model in an open environment.

###  3.2. Uncertainty Estimation Methods

Uncertainty estimation techniques play a key role in deploying machine
learning in the field of NLP. Commonly used estimation methods include
confidence-based, sampling-based, and distribution-based methods (Hu et al.,
2023). Recall that SpanNER divides the input into spans, and logits are
obtained after feeding each span into the neural network. Based on this, we
use the following four uncertainty estimation methods in our study:

Least Confidence (LC). For a $C-$class classification problem, given an span
input ${s}$ and the class prediction $y\in\\{1,...,C\\}$, the uncertainty
describe as:

(1) $u_{LC}({s})=1-{\mathop{\mathrm{max}}_{c\in C}\;p(y=c|{s})},$

where $p(y=c|{s})$ is the Softmax scores on $C$ categories.

Prediction Entropy (PE) serves as a straightforward and efficient method for
estimating uncertainty. Maximum entropy occurs when all outcomes share the
same probability. The uncertainty $u_{PE}({s})$ of point ${s}$ can be
quantified as its predicted entropy:

(2) $u_{PE}({s})=\sum_{c\in C}-p(y=c|{s})\,{\mathrm{log}}\,p(y=c|{s}).$

Monte Carlo Dropout (MCD) is the typical sampling method. Specifically, the
MCD method performs $M$ stochastic forward passes with activated dropout:

(3)
$u_{MCD}(s)=\frac{1}{M}\sum_{c,m}^{C,M}-p(y^{m}=c|s){\mathrm{log}}\,p(y^{m}=c|{s}).$

In this study, MCD is used to perform Monte Carlo integration on the entropy
value.

Figure 2. Link’s overall framework. A fine-tuned NER model is used for
recognizing entities and detecting uncertain entities, and the LLM
reclassifies the detected uncertain entities.

Evidential Neural Network (ENN) is one of the distribution based uncertainty
estimation methods implemented through a Dirichlet distribution parameterized
neural network. Specifically, each $s$ is fed into the evidential neural
network to obtain $logits$ and convert them into evidence $\mathbf{e}$ using a
non-negative function: $\mathbf{e}=\mathbf{func}(logits)$. For example,
$\mathbf{func}$ can be an exponential function or Softplus. Finally, the
predicted probability $\mathbf{p}$ and the corresponding uncertainty $u_{ENN}$
of the span entity are as follows:

(4)
$\mathbf{p}=\frac{\mathbf{e}+\mathbf{s}^{\mathrm{prior}}}{\sum_{C}(\mathbf{e}+\mathbf{s}^{\mathrm{prior}})},\quad
u_{ENN}(s)=\frac{\sum_{C}\mathbf{s}^{\mathrm{prior}}}{\sum_{C}(\mathbf{e}+\mathbf{s}^{\mathrm{prior}})},$

where $\mathbf{s}^{\mathrm{prior}}$ represents a uniform distribution with a
value of $\mathbf{1}$ as the prior.

Figure 3. Illustration of the LinkNER framework and components.

Model Learning Optimization. In addition to the uncertainty quantification
method of ENN, other methods use the original loss function of SpanNER, which
is the cross-entropy loss function. For ENN, to improve the detection of
unseen entities, the training scheme of E-NER (Zhang et al., 2023) is used for
network optimization. Overall, the E-NER loss function of this scheme consists
of two components: classification loss function $\mathcal{L}_{\mathrm{cls}}$
and the penalty loss function $\mathcal{L}_{\mathrm{penalty}}$. The detailed
optimization function is in Appendix B.

(5) $\displaystyle\mathcal{L}_{E}=$
$\displaystyle\mathcal{L}_{\mathrm{cls}}+\mathcal{L}_{\mathrm{penalty}},$

where $\mathcal{L}_{\mathrm{cls}}$ allows the evidence to gather on the
correct category, and $\mathcal{L}_{\mathrm{penalty}}$ aims to reduce the
evidence of the incorrect category, thereby increasing the uncertainty of the
unknown entity.

Finally, the tuple $y$ representing each entity prediction is denoted as
$y=[(x^{e},x^{d},\mathrm{label}),u]$.

##  4\. LinkNER Framework

As shown in Figure 2, we describe the LinkNER overall framework. In the
subsequent subsection, we offer a comprehensive explanation of the showcased
concept.

###  4.1. LinkNER Workflow

The entity recognition of each text contains three steps, and the workflow of
LinkNER is shown in Figure 3. At step \small{1}⃝, the test sentence is fed
into the local model, which outputs the entity recognition result and the
corresponding uncertainty probability, denoted as
$y=[(\mathrm{x}^{e},\mathrm{x}^{d},\mathrm{label}),u]$. At step \small{2}⃝,
the uncertainty of the local model output is compared with a predefined
threshold $\tau$. Entities that are greater than the threshold $\tau$ are
detected as uncertain, and sent to the LLM for further classification.
Entities that are less than the threshold $\tau$ do not need to undergo
refinement. Finally, at step \small{3}⃝, the outputs of the local model and
LLM are integrated into the final result. Then, we explain in detail how the
local model performs entity recognition and detection, and how the LLM refines
the results from the local model.

###  4.2. Local NER Model

As mentioned in §3, the local NER model is SpanNER, which is commonly used for
NER tasks and comes equipped with four uncertainty estimation methods. These
four uncertainty estimation methods are chosen because they cover common
uncertainty quantification methods in NLP (Hu et al., 2023) (based on
confidence, sampling, and distribution), as well as targeted quantification
methods in NER (E-NER). Here a research question raises: _why the uncertainty
needs to be reliable?_ The reason relies on that uncertainty needs to
accurately characterize the output reliability of the model. For example,
using only the output confidence of Softmax often leads to overconfidence (Guo
et al., 2017). It fails to clearly distinguish between seen and unseen
uncertain entities (Zhang et al., 2023). Sampling-based uncertainty estimation
methods consume more time, computing resources, and distribution-based methods
typically necessitate model retraining. There is no certainty that a single
uncertainty estimation method exhibits the best overall performance across
multiple datasets. Therefore, we need to assess the performance of uncertainty
methods on various datasets.

After fine-tuning the local model, we can get the relationship between the
output uncertainty and model performance. As shown in Figure 4(a), we obtain
the performance and entity density of local model (E-NER as example) under
different uncertainty intervals during the CoNLL’03 test. We observe that as
uncertainty increases, the performance of the local model and the entity
density exhibit a downward trend within each uncertainty interval. This trend
indicates that different uncertainty intervals reflect the difficulty of
entities. Furthermore, in the OOV test illustrated in Figure 4(b), compared to
Figure 4(a), the overall performance experiences a downward shift, and the
entity density exhibits a bias towards high uncertainty. These findings
demonstrate that the local model, although challenging in OOV testing, still
offers opportunities to detect unseen entities through uncertainty.

(a) CoNLL’03

(b) CoNLL’03-OOV

Figure 4. Illustration of local model (E-NER as an example) performance under
different uncertainties. The polyline and histogram represent the changes in
F1 score and entity density under different uncertainty intervals,
respectively.

###  4.3. Linking Local Model to LLM

Entity naming is related to the data sources and annotators involved, which
requires the model to carefully capture the data distribution of the current
NER task. However, recall our investigation in §1, and previous studies (Han
et al., 2023) showing that LLM lack of specialty (Extract unmentioned
entities, undefined categories, etc.) in NER tasks, hindering LLM from
directly extracting entities from a given text. Therefore, we propose an
uncertainty-based interaction strategy between two models: Recognition-
Detection-Classification (RDC) to address this challenge.

Specifically, a fine-tuned local model is used for entity recognition, and its
output uncertainty probabilities can be used for uncertain entity detection,
and then sends uncertain entities to LLM for entity type classification, i.e.,
a multiple-choice question. By doing so, the local model provides LLM with
entity span and category constraints, and simultaneously, makes the task
paradigm simpler. For clarity, Figure 3 illustrates the process. The uncertain
entity Sandor Tolonics undergoes filtration using the uncertainty output from
the local model. Subsequently, the filtered entity is forwarded to LLM for
reclassification. Finally, the output from LLM is combined with the local
model’s output to obtain the final prediction.

###  4.4. In-Context Learning for LLM

The large and undisclosed parameters of LLM make it difficult to achieve fine-
tuning, but its powerful contextual understanding ability makes it possible to
perform in-context learning. In order to provide LLM with task-specific
information, we design two kinds of context hinting for LinkNER as its
components.

Label Description. Several datasets already encompass descriptions for
different entity types. We argue that integrating these interpretations into
LLM augments its semantic comprehension. For instance, the OntoNotes 5.0
(Weischedel et al., 2013) dataset offers an explanation for the ”FACILITY”
entity class: ”FACILITY: buildings, airports, highways, bridges, etc.” . In
the Appendix C Table 8, we furnish label descriptions extracted from the
original paper for the dataset.

Few-Shot Learning. Examples of each entity category serve as valuable
references in this context. We construct an example set by combining the
training and validation sets, which comprise ¡Question-Answer¿ pairs. Each
pair consists of context, instructions for entity classification, and answers.
To clarify, the sample Question and Answer format are the same as the question
shown in Figure 3 ¡Prompt¿. The question is presented in a multiple-choice
format, such as ”select the entity type of Sandor Tolonics”, while the answer
is provided by selecting one of the entity type options, such as ”Person”.
Then, we select a total of $N$ classes ($N$-way), and each class has $K$
($K$-shot) examples from the example set, thus $N\times{K}$ shots in total.
Furthermore, more specific examples can be found in Appendix C. In the N-way-
K-shot setting, we always set K to 1 due to the limitation of LLM input token
length, and N depends on the number of entity types in the dataset. By
employing this approach, the few-shot setting equips LLM with a collection of
examples for entity classification, allowing the LLM to efficiently classify
similar entity types.

##  5\. Experiments

In this section, we first introduce the benchmark and uncertainty threshold
selection, and then conduct extensive experiments to verify the effectiveness
of LinkNER.

Table 2. Statistics of entities in the test sets. Dataset | Entities | Types | Domain | OOV Rate
---|---|---|---|---
CoNLL’03 | 35.1k | 4 | Newswire | -
OntoNotes 5.0 | 161.8k | 18 | General | -
WikiGold | 1.6k | 4 | General | -
1-5 CoNLL’03-Typos | 4.1k | 4 | Newswire | 0.71
CoNLL’03-OOV | 5.6k | 4 | Newswire | 0.96
JNLPBA | 4.3k | 5 | Medical | 0.77
WNUT’17 | 0.9k | 6 | SocialMedia | 1.00
TweetNER | 4.0k | 4 | SocialMedia | 0.62

###  5.1. Experimental Research Questions

In this section, we design extensive experiments to verify the effectiveness
of the LinkNER method and the applicable scenarios of the components. We
evaluate LinkNER in the following research questions (RQ):
RQ1: When should the LLM make decisions in LinkNER?
RQ2: What is the impact of RDC on LinkNER performance?
RQ3: How many decisions are made by LLM in LinkNER?
RQ4: When is it effective to employ in-context learning in LinkNER?

###  5.2. Experimental Settings

Dataset. For testing on standard data, as shown in Table 2, we choose three
commonly used datasets, including two In-Domain (ID) datasets and one Out-of-
Domain (OOD) dataset: ID: CoNLL’03 Dataset (Tjong Kim Sang and De Meulder,
2003). We only consider the English (EN) dataset collected from the Reuters
Corpus. ID: OntoNotes 5.0 Dataset (Onto. 5.0) (Weischedel et al., 2013) has
multiple entity types in the fields of telephone conversations, web data, news
agencies, etc. OOD: WikiGold Dataset (Balasuriya et al., 2009) is a test set
from Wikipedia with the same entity types as CoNLL’03 but with different
domains. Furthermore, as shown in Table 2, we use five commonly used OOV
datasets to test on unseen entities: Typos Dataset (Wang et al., 2021)
replaces entities in the CoNLL’03 test set by typos version (character modify,
insert, and delete operation); OOV Dataset (Wang et al., 2021) replaces
entities in the CoNLL’03 test set for other OOV entities; TweetNER Dataset
(Zhang et al., 2018) is a NER dataset derived from English tweets; WNUT’17
Dataset (Derczynski et al., 2017), a focus on the noisy and unseen different
distribution entities in the social domain. JNLPBA Dataset (Collier et al.,
2004) focuses on the field of biology and contains relevant technical terms
and symbols.

To address RQ1, we employ the CoNLL’03 dataset as an example to establish the
uncertainty threshold for LLM decision-making. For RQ2 and RQ3, we utilize all
datasets (Table 2). For RQ4 scenario, we select CoNLL’03 and its variants,
OntoNotes 5.0, and WNUT’17 datasets for ablation experiments and analysis.
Furthermore, for RQ1 and RQ4, we use E-NER as the local model uncertainty
estimation method, and GPT-3.5 as LLM as an example for analysis. The local
model in other scenarios is equipped with all uncertainty estimation methods.
Llama 2-Chat (13B) and GPT-3.5 as LLM.

Benchmark. To evaluate the effectiveness of LinkNER, we compare it with the
following baselines: SpanNER (Fu et al., 2021), which enumerates all possible
entities in a sentence, is trained with an unconstrained classification
framework. MINER (Wang et al., 2022), which uses variational information
bottleneck to solve the OOV problem and demonstrates SOTA performance across
various datasets. DataAug (Dai and Adel, 2020), which trains the architecture
using the SpanNER model, and uses the original training set and the entity
replacement training set for data augmentation. VaniIB (Alemi et al., 2017),
which applies the information bottleneck constraint to SpanNER and directly
compresses all information in the input.

Metrics. Entity-level micro average F1 score is used for test set evaluation,
and only predictions with correct entity boundaries and classifications are
considered correct.

Figure 5. Uncertainty threshold $\tau$ selection on the CoNLL’03 validation
set. Align the fully linked LinkNER ($\tau=0.0$) prediction results with the
results of the local model, and the intersection point is used as the
threshold point.

###  5.3. Determining Threshold for LLM in LinkNER

LLM’s classification decision depends on the uncertainty estimate score of the
local model’s output for the entity. The crucial step in LinkNER is the
selection of an appropriate uncertainty threshold $\tau$, which determines
when LLM makes classification decisions. As mentioned earlier, the performance
of the local model deteriorates in the high uncertainty range. Therefore, we
aim to leverage LLM for improved entity classification within this range
compared to local model. To illustrate this, let us consider CoNLL’03 as an
example, as depicted in Figure 5. Initially, we set the LinkNER threshold
$\tau=0.0$ (see full linked LinkNER ($\tau=0.0$)), as a result, the local
model is responsible for entity detection in LinkNER, while LLM (GPT-3.5 is
used for this example) provides all entity classification results.
Simultaneously, we record the recognition results of the local model across
various intervals (see E-NER). The threshold $\tau$ is determined by
identifying the intersection point where the fully linked LinkNER aligns with
these results (see the star-shaped intersection). In other words, the LLM
outperforms the local model in classifying uncertain entities when the
uncertainty surpasses the threshold $\tau$. At this moment, integrating the
local model with the LLM can lead to performance enhancement. By selecting an
appropriate threshold $\tau$, we achieve a favorable balance between
performance and efficiency.

(a) CoNLL’03

(b) CoNLL’03-OOV

Figure 6. Illustrations (a) and (b) present the variations in LinkNER’s
performance at different threshold points.

Then, we assess the appropriateness of the uncertainty threshold selection.
Figures 6(a) and 6(b) present the results, where we employ 10 threshold points
with a step size of 0.1. We evaluate the performance of LinkNER at each
threshold point individually. The figure displays the outcomes, indicating
that both the CoNLL’03 and OOV test sets exhibit the highest F1 scores when
the threshold is set to 0.4. Notably, this aligns with the threshold selected
in §5.4, based on the CoNLL’03 validation set, which also confirms the
rationality of our threshold selection method. This approach allows the local
model and the LLM to complement each other. The more serious the phenomenon of
unseen entities in the test set, the more serious the ”lack of knowledge”
phenomenon of the local model, so the uncertainty threshold $\tau$ used will
be smaller, and the classification of entities is more inclined to LLM
decision-making. In this way, we can select the threshold and obtain the
performance of the local model and LLM under different uncertainty intervals
in more detail. The thresholds for all datasets in the experiments are given
in Appendix C Table 7.

Table 3. Comparison of performance and robustness tests between LinkNER and SOTA methods, in terms of F1 (%). | Setting | Onto. 5.0 | CoNLL’03 | WNUT’17 | TweetNER | JNLPBA
---|---|---|---|---|---|---
| ID | ID | Typos | OOV | OOD | OOV | OOV | OOV
| SOTA |  90.50(Li et al., 2022b) |  94.54(Li et al., 2021) |  87.57(Wang et al., 2022) |  79.15(Wang et al., 2022) |  82.21(Zhang et al., 2023) |  54.86(Wang et al., 2022) |  76.71(Zhang et al., 2023) |  78.47(Zhang et al., 2023)
Baseline | GPT-3.5 | 51.15 | 67.08 | 62.24 | 62.74 | 71.28 | 42.53 | 55.59 | 41.25
naïve Llama 2(13B) | 8.17 | 17.85 | 13.81 | 11.26 | 15.52 | 9.33 | 13.40 | 11.06
VaniIB | - | - | 83.49 | 70.12 | - | 51.60 | 71.19 | 73.41
DataAug | - | - | 81.73 | 69.60 | - | 52.29 | 73.69 | 75.85
SpanNER (BERT_large) | 87.82 | 92.37 | 81.83 | 64.43 | 80.54 | 51.83 | 74.93 | 75.07
SpanNER-MCD (BERT_large) | 88.42 | 92.67 | 83.58 | 69.49 | 78.30 | 49.07 | 75.25 | 76.39
MINER (RoBERTa_large) | 88.99 | 90.19 | 87.57 | 79.15 | 77.01 | 54.86 | 75.38 | 76.43
E-NER (BERT_base) | 88.70 | 92.00 | 82.69 | 68.61 | 81.09 | 51.74 | 75.64 | 76.44
E-NER (BERT_large) | 90.59 | 93.12 | 84.62 | 70.41 | 82.21 | 51.28 | 76.71 | 78.47
Link-Llama2 (13B) | Link-SpanNER (Confidence) | 89.14 | 93.04 | 83.83 | 70.21 | 82.40 | 62.11 | 77.51 | 78.09
Link-SpanNER (Entropy) | 89.24 | 93.28 | 83.87 | 70.56 | 82.65 | 62.81 | 77.20 | 82.89
Link-SpanNER (MCD) | 90.06 | 93.99 | 85.16 | 71.41 | 82.42 | 63.38 | 77.77 | 79.85
Link-ENER (BERT_large) | 90.64 | 93.17 | 85.03 | 73.12 | 82.72 | 68.30 | 77.05 | 80.41
2-10 |  Min $\Delta$ LinkNER vs. LocalNER | 0.05↑ | 0.05↑ | 0.41↑ | 1.92↑ | 0.51↑ | 10.28↑ | 0.34↑ | 1.94↑
|  Max $\Delta$ LinkNER vs. LocalNER | 1.64↑ | 1.32↑ | 2.04↑ | 6.13↑ | 4.12↑ | 17.02↑ | 2.58↑ | 7.82↑
| Link SOTA (Confidence) to Llama 2 | 90.62 | 93.78 | 88.41 | 79.19 | 82.72 | 63.37 | 77.05 | 80.41
Link-GPT3.5 | Link-SpanNER (Confidence) | 89.20 | 92.99 | 83.85 | 69.63 | 82.51 | 65.12 | 79.18 | 82.22
Link-SpanNER (Entropy) | 88.72 | 93.32 | 84.41 | 71.24 | 83.79 | 65.45 | 79.20 | 82.89
Link-SpanNER (MCD) | 90.45 | 94.18 | 85.48 | 71.95 | 82.49 | 66.67 | 80.12 | 81.93
Link-ENER (BERT_base) | 89.71 | 93.05 | 85.73 | 72.91 | 85.08 | 73.04 | 77.02 | 84.60
Link-ENER (BERT_large) | 90.82 | 93.36 | 86.52 | 73.74 | 84.16 | 72.12 | 79.43 | 86.81
2-10 |  Min $\Delta$ LinkNER vs. GPT-3.5 | 37.57↑ | 25.91↑ | 21.61↑ | 6.89↑ | 11.21↑ | 22.59↑ | 21.43↑ | 40.68↑
|  Max $\Delta$ LinkNER vs. GPT-3.5 | 39.67↑ | 27.10↑ | 24.28↑ | 11.00↑ | 13.80↑ | 30.51↑ | 24.53↑ | 45.56↑
2-10 |  Min $\Delta$ LinkNER vs. LocalNER | 0.18↑ | 0.24↑ | 1.90↑ | 2.46↑ | 1.95↑ | 13.29↑ | 1.38↑ | 5.54↑
|  Max $\Delta$ LinkNER vs. LocalNER | 2.03↑ | 1.51↑ | 3.04↑ | 6.81↑ | 4.19↑ | 21.30↑ | 4.87↑ | 8.34↑
| Link SOTA (Confidence) to GPT 3.5 | 90.74 | 93.85 | 89.72 | 79.88 | 84.16 | 67.61 | 79.43 | 86.81

###  5.4. Assessing RDC’s Influence on LinkNER Performance

Standard Performance Evaluation. After the optimal threshold is chosen, we
first investigate how LinkNER performs on the standard evaluation. After
selecting the optimal threshold, we first study the performance of LinkNER on
the ID dataset. The experimental results are displayed in the first two
columns of Table 3. We confirm that LinkNER generally improves task
performance on ID data, demonstrating that local models and LLM can complement
each other through the RDC model bridge. Among these models, the minimum and
maximum improvements of different local models are relatively close. MCD and
E-NER serve as better methods for estimating local model uncertainty. Whether
it’s Llama 2-Chat (13B) or GPT-3.5 for classification decisions, after
linking, the performance of LinkNER closely matches that of the SOTA method.
However, MINER, which excels in OOV scenarios, exhibits weaker performance in
ID tests. Since the local model acquires relevant knowledge from the LLM, most
simple entities are accurately recognized in regular tests, while only a few
challenging entities with higher uncertainty are identified and classified by
the LLM.

OOV/OOD Robustness Test Evaluation. Then, it is wondered whether LinkNER can
achieve better results in the robustness test. As shown in the results in
columns 3-8 in Table 3. The local model captures the original data
distribution, allowing the RDC model to exhibit more powerful uncertain entity
recognition capabilities while maintaining high efficiency. Especially in the
OOD test set, LinkNER equipped with E-NER and GPT-3.5 exceeds the SOTA method
by a 2.87% F1 score. In the two OOV variant test sets of CoNLL’03, LinkNER
equipped with different uncertainty estimation methods shows improved
performance in terms of F1 scores. The overall performance of MCD and E-NER is
better, but it is still far from SOTA. The gap, we analyze, is related to the
choice of the local model. The experiments we conduct only in the original
framework of SpanNER do not include any information enhancement. It is worth
noting that in OOV/OOD scenarios, different uncertainty estimation methods
have a greater impact on the final performance of LinkNER, which is manifested
in the floating gap between the minimum and maximum performance improvements.
These findings further validate the usability and robustness of the LinkNER
model equipped with RDC strategy.

(a) CoNLL’03

(b) CoNLL’03-OOV

Figure 7. Illustrations (a) and (b) depict the performance comparison between
LinkNER and E-NER across various uncertainty intervals.

Furthermore, LinkNER outperforms SOTA in F1 scores on social media datasets,
including TweetNER and WNUT’17 datasets. These datasets contain a lot of noise
and unseen entities, especially LinkNER’s performance improvement of 18.18% on
the WNUT’17 dataset relative to SOTA, which proves the reliability of LinkNER
even on unstructured social media noisy data. Finally, in the medical dataset
JNLPBA, the entity test contains OOV entities with a large number of
biological terms. LinkNER still surpass the SOTA with an 8.34% F1 score,
proving the effectiveness of LinkNER in NER tasks in the medical professional
field. Finally, we are currently just trying the simplest uncertainty strategy
(confidence-based) and using the LinkNER to improve the SOTA score.

Table 4. The proportion of LLM making classification decisions in different LinkNERs. Setting | Onto. 5.0 | CoNLL’03 | WNUT’17 | TweetNER | JNLPBA
---|---|---|---|---|---
ID | ID | Typos | OOV | OOD | OOV | OOV | OOV
Link-SpanNER (Confidence) | 0.47% | 0.08% | 0.27% | 1.18% | 0.49% | 59.70% | 1.74% | 21.58%
Link-SpanNER (Entropy) | 4.59% | 2.23% | 4.09% | 6.88% | 8.13% | 60.18% | 10.41% | 45.31%
Link-SpanNER (MCD) | 0.16% | 0.44% | 0.95% | 0.35% | 0.66% | 13.82% | 0.36% | 6.33%
Link-ENER (BERT_base) | 1.56% | 2.81% | 12.90% | 21.17% | 19.79% | 85.13% | 72.65% | 50.35%
Link-ENER (BERT_large) | 0.94% | 2.38% | 9.29% | 13.78% | 14.33% | 55.66% | 9.45% | 52.58%

###  5.5. Analyzing the Uncertainty Interval of LLM Decision-making

To further investigate the contribution of LLM in LinkNER, we analyze the
entity recognition performance across various uncertainty intervals. As
illustrated in Figure 7, LinkNER can improve performance in high uncertainty
intervals. Recall that Section §3 mentions that entities with high uncertainty
are more likely to be incorrect, and a reasonable threshold link LLM can
compensate for the test performance in the high uncertainty interval.
Consequently, LinkNER can improve the overall performance by refining high-
uncertainty entities, whether it is regular data testing 7(a) or testing with
unseen entities 7(b). This further verifies the rationality of LinkNER to
achieve more robust performance, ensuring that the system is still available
under noise data.

Furthermore, we analyze the proportion of LLM making classification decisions.
The results are shown in Table 4, from the perspective of the dataset, the
four uncertainty methods screen out a relatively small number of uncertain
entities on the ID dataset, which aligns with our hypothesis. There are only a
small proportion of challenging entities in these ID datasets. However, it
filters out more uncertain entities in the WNUT’17 dataset. We find that this
is caused by too little data available in the training set and underfitting of
the model. Although the uncertainty estimation method based on entropy value
filters out more uncertain entities, the improvement is subtle and consumes
too much LLM reasoning resources. Table 3 shows that the final performance
improvement is very limited. Conversely, the method based on MCD screens out
fewer uncertain entities, but Table 3 shows that the final performance is
greatly improved. While MCD multiple forward sampling consumes some local
model reasoning resources, high-quality uncertainty estimation yields more
effective results for LLM. E-NER detects more uncertain entities (as
demonstrated by BERT_base), and performance improves noticeably in OOV/OOD
scenarios. However, overly ”cautious” uncertainty scores also consume more LLM
reasoning resources.

###  5.6. Identifying Effective Scenarios for In-Context Learning in LinkNER

We conduct ablation experiments to assess the effect of model components and
in-context learning in LinkNER. The model components considered are as
follows: (I) Local model E-NER, which focuses on entity recognition and
detection in the first stage; (II) The GPT-3.5 plugin, responsible for making
decisions regarding uncertain entities. Furthermore, we perform a study on the
in-context learning component of LinkNER, exploring the following aspects: (a)
The multiple-choice-style few-shot setting. (b) The information of entity type
label description. The experimental results are shown in Table 5. When
compared to the local model alone (E-NER), LinkNER improves the F1 score of
the ID datasets by 1.05%↑ and 1.01%↑, respectively. For the Typos and OOV
variant datasets of ConLL’03 and the WNUT’17 dataset, LinkNER’s F1 scores
improve by 3.04%↑, 4.30%↑, and 21.30%↑, respectively. Additionally, when
compared to GPT-3.5, the F1 scores of LinkNER on ID data are 25.97%↑ and
38.56%↑, respectively. LinkNER achieves improvements of 23.49%↑, 10.17%↑, and
30.51%↑ on the Typos, OOV variant dataset, and WNUT’17 dataset, respectively.

Table 5. Ablation study evaluation results F1(%) . (a) Few-shot setting (FS). (b) Entity type label description (LD). | Components | CoNLL’03 | Onto. | WNUT.
---|---|---|---|---
|  (a) FS. |  (b) LD. | ID | Typos | OOV | ID | OOV
(I) E-NER (BERT_base) | 92.00 | 82.69 | 68.61 | 88.70 | 51.74
(II) GPT-3.5 | 67.08 | 62.24 | 62.74 | 51.15 | 42.53
(1) | ✗ | ✗ | 92.50 | 83.60 | 71.25 | 89.16 | 77.96
(2) | ✗ | ✓ | 92.85 | 85.51 | 70.68 | 89.59 | 77.54
(3) | ✓ | ✗ | 92.94 | 84.79 | 71.60 | 89.37 | 64.51
| ✓ | ✓ | 93.05 | 85.73 | 72.91 | 89.71 | 73.04

For each component, we analyze CoNLL’03 and its variants, as well as the Onto.
5.0 dataset, this can simulate normal text and a small amount of noise text on
the web. For setting (1), when all examples containing context are removed,
both models work seamlessly together without any adverse impact. However,
relative to LinkNER’s performance, there is a sharp decline. RDC’s interaction
model fully leverages the respective benefits of both models. For the setup of
the LD (2), we attempt to remove the FS setting from LinkNER, resulting in
performance degradation. This degradation can be attributed to the lack of
examples for each entity type, making it difficult for GPT-3.5 to capture the
data distribution. (3) When the LD is removed, performance also decreases.
This demonstrates that accurate entity LD provides a classification basis for
GPT-3.5. However, for the WNUT’17 dataset, which is often noisy data in web
social media, we observe that contextual examples and LD hinder performance
improvement. We attribute this to the limited size of the training data and
resulting in a significant distribution gap between the training and test
sets. Consequently, when the training data distribution matches that of the
web test text, we can use context learning to enhance the effectiveness of LLM
in making classification decisions, and vice versa.

##  6\. Conclusion

In this work, we combine LLM to design a more robust NER system by utilizing
the local fine-tuned model, SpanNER. To address the issue of ”lack of
knowledge” in the fine-tuning model for unseen entities, as well as the ”lack
of specialty” problem of LLM entity recognition, we propose the LinkNER
framework, which we refer to as the RDC linking strategy based on uncertainty
estimation, to link these two models. Extensive experimental results
demonstrate that the proposed method can be effectively applied to benchmarks
and robustness tests, particularly outperforming the SOTA models by 3.04% to
21.30% F1 scores in the challenging robustness tests. These results validate
the superiority of LinkNER in open environments.

## Acknowledgements

This work is supported by the youth program of National Science Fund of
Tianjin, China (Grant No. 22JCQNJC01340), the Fundamental Research Funds for
the Central University, Nankai University (Grant No. 63221028), and the key
program of National Science Fund of Tianjin, China (Grant No. 21JCZDJC00130).

## References

  * (1)
  * Agarwal et al. (2021) Oshin Agarwal, Yinfei Yang, Byron C. Wallace, and Ani Nenkova. 2021.  Interpretability Analysis for Named Entity Recognition to Understand System Predictions and How They Can Improve.  _Computational Linguistics_ (2021), 117–140.
  * Alemi et al. (2017) Alexander A. Alemi, Ian Fischer, Joshua V. Dillon, and Kevin Murphy. 2017.  Deep Variational Information Bottleneck. In _International Conference on Learning Representations (ICLR)_. 1–19.
  * Balasuriya et al. (2009) Dominic Balasuriya, Nicky Ringland, Joel Nothman, Tara Murphy, and James R. Curran. 2009.  Named Entity Recognition in Wikipedia. In _Proceedings of the 2009 Workshop on The People’s Web Meets NLP: Collaboratively Constructed Semantic Resources (People’s Web)_. 10–18.
  * 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 (NeurIPS)_ (2020), 1877–1901.
  * Collier et al. (2004) Nigel Collier, Tomoko Ohta, Yoshimasa Tsuruoka, Yuka Tateisi, and Jin-Dong Kim. 2004.  Introduction to the Bio-entity Recognition Task at JNLPBA. In _Proceedings of the International Joint Workshop on Natural Language Processing in Biomedicine and its Applications (NLPBA/BioNLP)_. 73–78.
  * Dai and Adel (2020) Xiang Dai and Heike Adel. 2020.  An Analysis of Simple Data Augmentation for Named Entity Recognition. In _Proceedings of the 28th International Conference on Computational Linguistics (COLING)_. 3861–3867.
  * Derczynski et al. (2017) Leon Derczynski, Eric Nichols, Marieke van Erp, and Nut Limsopatham. 2017.  Results of the WNUT2017 Shared Task on Novel and Emerging Entity Recognition. In _Proceedings of the 3rd Workshop on Noisy User-generated Text_. 140–147.  https://doi.org/10.18653/v1/W17-4418
  * 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)_. 4171–4186.  https://doi.org/10.18653/v1/N19-1423
  * Fetahu et al. (2021) Besnik Fetahu, Anjie Fang, Oleg Rokhlenko, and Shervin Malmasi. 2021.  Gazetteer Enhanced Named Entity Recognition for Code-Mixed Web Queries. In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Virtual Event, Canada) _(SIGIR ’21)_. Association for Computing Machinery, 1677–1681.
  * Fu et al. (2021) Jinlan Fu, Xuanjing Huang, and Pengfei Liu. 2021.  SpanNER: Named Entity Re-/Recognition as Span Prediction. In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (ACL: Long Papers)_. 7183–7195.
  * Fu et al. (2020) Jinlan Fu, Pengfei Liu, and Qi Zhang. 2020.  Rethinking generalization of neural models: A named entity recognition case study. In _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , Vol. 34. 7732–7739.
  * Gal and Ghahramani (2016) Yarin Gal and Zoubin Ghahramani. 2016.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In _international conference on machine learning_. PMLR, 1050–1059.
  * Guo et al. (2017) Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. 2017.  On Calibration of Modern Neural Networks. In _Proceedings of the 34th International Conference on Machine Learning (ICML)_. 1321–1330.
  * Guo et al. (2009a) Jiafeng Guo, Gu Xu, Xueqi Cheng, and Hang Li. 2009a.  Named entity recognition in query. In _Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval_. 267–274.
  * Guo et al. (2009b) Jiafeng Guo, Gu Xu, Xueqi Cheng, and Hang Li. 2009b.  Named entity recognition in query. In _Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval_. 267–274.
  * Han et al. (2023) Ridong Han, Tao Peng, Chaohao Yang, Benyou Wang, Lu Liu, and Xiang Wan. 2023.  Is Information Extraction Solved by ChatGPT? An Analysis of Performance, Evaluation Criteria, Robustness and Errors.  _arXiv preprint arXiv:2305.14450_ (2023).
  * Hu et al. (2023) Mengting Hu, Zhen Zhang, Shiwan Zhao, Minlie Huang, and Bingzhe Wu. 2023.  Uncertainty in Natural Language Processing: Sources, Quantification, and Applications.  _arXiv preprint arXiv:2306.04459_ (2023).
  * Jin et al. (2014) Yuzhe Jin, Emre Kıcıman, Kuansan Wang, and Ricky Loynd. 2014.  Entity linking at the tail: sparse signals, unknown entities, and phrase models. In _Proceedings of the 7th ACM international conference on Web search and data mining_. 453–462.
  * Jøsang (2016) Audun Jøsang. 2016.  _Subjective logic_. Vol. 3.  Springer.
  * Lei et al. (2022) Shuo Lei, Xuchao Zhang, Jianfeng He, Fanglan Chen, and Chang-Tien Lu. 2022.  Uncertainty-Aware Cross-Lingual Transfer with Pseudo Partial Labels. In _Findings of the Association for Computational Linguistics: NAACL 2022 (NAACL Findings)_. 1987–1997.  https://doi.org/10.18653/v1/2022.findings-naacl.153
  * Li et al. (2018) Changliang Li, Liang Li, and Ji Qi. 2018.  A Self-Attentive Model with Gate Mechanism for Spoken Language Understanding. In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. 3824–3833.  https://doi.org/10.18653/v1/D18-1417
  * Li et al. (2021) Fei Li, Zheng Wang, Siu Cheung Hui, Lejian Liao, Dandan Song, and Jing Xu. 2021.  Effective named entity recognition with boundary-aware bidirectional neural networks. In _Proceedings of the Web Conference 2021_. 1695–1703.
  * Li et al. (2022a) Jingye Li, Hao Fei, Jiang Liu, Shengqiong Wu, Meishan Zhang, Chong Teng, Donghong Ji, and Fei Li. 2022a.  Unified named entity recognition as word-word relation classification. In _Proceedings of the AAAI Conference on Artificial Intelligence(AAAI)_. 10965–10973.
  * Li et al. (2022b) Jingye Li, Hao Fei, Jiang Liu, Shengqiong Wu, Meishan Zhang, Chong Teng, Donghong Ji, and Fei Li. 2022b.  Unified named entity recognition as word-word relation classification. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 36. 10965–10973.
  * Lin et al. (2020) Hongyu Lin, Yaojie Lu, Jialong Tang, Xianpei Han, Le Sun, Zhicheng Wei, and Nicholas Jing Yuan. 2020.  A Rigorous Study on Named Entity Recognition: Can Fine-tuning Pretrained Model Lead to the Promised Land?. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. 7291–7300.  https://doi.org/10.18653/v1/2020.emnlp-main.592
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled Weight Decay Regularization. In _International Conference on Learning Representations (ICLR)_. 1–18.
  * Scao et al. (2022) Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilić, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al. 2022\.  Bloom: A 176b-parameter open-access multilingual language model.  _arXiv preprint arXiv:2211.05100_ (2022).
  * Schick et al. (2023) Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023.  Toolformer: Language models can teach themselves to use tools.  _arXiv preprint arXiv:2302.04761_ (2023).
  * Sensoy et al. (2018) Murat Sensoy, Lance M. Kaplan, and Melih Kandemir. 2018.  Evidential Deep Learning to Quantify Classification Uncertainty. In _Advances in Neural Information Processing Systems (NeurIPS)_. 3183–3193.
  * Shen et al. (2021) Yongliang Shen, Xinyin Ma, Yechun Tang, and Weiming Lu. 2021.  A trigger-sense memory flow framework for joint entity and relation extraction. In _Proceedings of the web conference 2021_. 1704–1715.
  * Shen et al. (2023) Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. 2023.  Hugginggpt: Solving ai tasks with chatgpt and its friends in huggingface.  _arXiv preprint arXiv:2303.17580_ (2023).
  * Tjong Kim Sang and De 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 at HLT-NAACL 2003 (HLT-NAACL)_. 142–147.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023\.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ (2023).
  * Wang et al. (2022) Xiao Wang, Shihan Dou, Limao Xiong, Yicheng Zou, Qi Zhang, Tao Gui, Liang Qiao, Zhanzhan Cheng, and Xuanjing Huang. 2022.  MINER: Improving Out-of-Vocabulary Named Entity Recognition from an Information Theoretic Perspective. In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (ACL: Long Papers)_. 5590–5600.  https://doi.org/10.18653/v1/2022.acl-long.383
  * Wang et al. (2021) Xiao Wang, Qin Liu, Tao Gui, Qi Zhang, Yicheng Zou, Xin Zhou, Jiacheng Ye, Yongxin Zhang, Rui Zheng, and Zexiong and Pang. 2021.  TextFlint: Unified Multilingual Robustness Evaluation Toolkit for Natural Language Processing. In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing: System Demonstrations (ACL-IJCNLP)_. 347–355.  https://doi.org/10.18653/v1/2021.acl-demo.41
  * Weischedel et al. (2013) Ralph Weischedel, Martha Palmer, Mitchell Marcus, Eduard Hovy, Sameer Pradhan, Lance Ramshaw, Nianwen Xue, Ann Taylor, Jeff Kaufman, Michelle Franchini, Mohammed El-Bachouti, Robert Belvin, and Ann Houston. 2013.  OntoNotes Release 5.0. In _3_. Abacus Data Network.  https://doi.org/11272.1/AB2/MKJJ2R
  * Xu et al. (2023) Canwen Xu, Yichong Xu, Shuohang Wang, Yang Liu, Chenguang Zhu, and Julian McAuley. 2023.  Small models are valuable plug-ins for large language models.  _arXiv preprint arXiv:2305.08848_ (2023).
  * Zhang et al. (2018) Qi Zhang, Jinlan Fu, Xiaoyu Liu, and Xuanjing Huang. 2018.  Adaptive co-attention network for named entity recognition in tweets. In _Thirty-Second AAAI Conference on Artificial Intelligence (AAAI)_. 5674–5681.
  * Zhang and Yang (2018) Yue Zhang and Jie Yang. 2018.  Chinese NER Using Lattice LSTM. In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL: Long Papers)_. 1554–1564.
  * Zhang et al. (2023) Zhen Zhang, Mengting Hu, Shiwan Zhao, Minlie Huang, Haotian Wang, Lemao Liu, Zhirui Zhang, Zhe Liu, and Bingzhe Wu. 2023.  E-NER: Evidential Deep Learning for Trustworthy Named Entity Recognition. In _Findings of the Association for Computational Linguistics: ACL 2023_. Association for Computational Linguistics, Toronto, Canada, 1619–1634.  https://doi.org/10.18653/v1/2023.findings-acl.103
  * Zhou et al. (2016) Xiangyang Zhou, Daxiang Dong, Hua Wu, Shiqi Zhao, Dianhai Yu, Hao Tian, Xuan Liu, and Rui Yan. 2016.  Multi-view Response Selection for Human-Computer Conversation. In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Austin, Texas, 372–381.  https://doi.org/10.18653/v1/D16-1036

Table 6. A comprehensive case study of LinkNER on NER tasks in real-world scenarios. It includes two parts, one is the example construction of LLM in-context learning, and the other is the LinkNER workflow. in-context Learning |  ¡Label Description¿
---|---
Here is all entity class information: Person: Names of people (e.g. Virginia
Wade)……
¡Few-Shot (6-way, 1-shot) examples¿
Example 1: ”¡Context¿:Pxleyes Top 50 Photography Contest Pictures of August
2010 … http://bit.ly/bgCyZ0 #photography Select the entity type of Pxleyes in
this context, and only need to output the entity type.”
Answer: corporation
…
Example 6: ”¡Context¿:@SnoopDogg hey snoop my wife Cath is 30 today , any
chance of a shout out to her , Select the entity type of snoop in this
context, and only need to output the entity type.”
Answer: person
LinkNER’s Work Case |  ¡Context¿
1. ”¡Context¿: 9 Resources For Crafting The Perfect Outreach Email by @ stephenjeske via @ quora https://t.co/c66x410IUr # emailmarketing # startup”
2. ”¡Context¿: You do realize this was published by CBC Manitoba .”
3. ”¡Context¿: That seems like something someone who supposedly works in Sandringham ”
¡Local Model¿
1. ${\mathrm{stephenjeske}}_{\\{10,10,{\color[rgb]{1,0,0}O|u=0.8}\\}}$✗
2. ${\mathrm{CBC\;Manitoba}}_{\\{7,8,{\color[rgb]{1,0,0}location|u=0.9}\\}}$✗
3. ${\mathrm{Sandringham}}_{\\{10,10,{\color[rgb]{0.1,0.81,0.21}location|u=0.0}\\}}$✓
¡Prompt and Respond¿
Question 1. Label description + Few-Shot examples + ”¡Context¿: 9 Resources
For Crafting The Perfect Outreach Email by @ stephenjeske via @ quora
https://t.co/c66x410IUr # emailmarketing # startup”. Select the entity type of
stephenjeske in this context, and only need to output the entity type:
location; group; corporation; person; creative-work; product; Non-entity.
Answer: person
Question 2. Label description + Few-Shot examples + ”¡Context¿: You do realize
this was published by CBC Manitoba .” Select the entity type of CBC Manitoba
in this context, and only need to output the entity type: location; group;
corporation; person; creative-work; product; Non-entity.
Answer: corporation
¡Final Results¿
1. ${\mathrm{stephenjeske}}_{\\{10,10,{\color[rgb]{0.1,0.81,0.21}person}\\}}$✓
2. ${\mathrm{CBC\;Manitoba}}_{\\{7,8,{\color[rgb]{0.1,0.81,0.21}corporation}\\}}$✓
3. ${\mathrm{Sandringham}}_{\\{10,10,{\color[rgb]{0.1,0.81,0.21}location}\\}}$✓
Table 7. Threshold settings for each uncertainty method on different datasets. Setting | CoNLL’03 | WNUT’17 | TweetNER | JNLPBA | OntoNotes 5.0
---|---|---|---|---|---
ID | Typos | OOV | OOD | OOV | OOV | OOV | ID
Link-SpanNER (Confidence) | 0.4 | 0.4 | 0.4 | 0.4 | 0.1 | 0.3 | 0.4 | 0.8
Link-SpanNER (Entropy) | 0.7 | 0.7 | 0.7 | 0.7 | 0.3 | 0.8 | 0.7 | 0.9
Link-SpanNER (MCD) | 0.8 | 0.8 | 0.8 | 0.8 | 0.1 | 0.6 | 0.4 | 0.7
Link-ENER (BERT_base) | 0.4 | 0.4 | 0.4 | 0.4 | 0.1 | 0.2 | 0.2 | 0.5
Link-ENER (BERT_large) | 0.8 | 0.8 | 0.8 | 0.8 | 0.1 | 0.4 | 0.3 | 0.9

##  Appendix A Case Study

We conduct a case study to better demonstrate the working behavior of LinkNER.
Examples are given in Table 6. In the social media data examples, the local
model encounters difficulty in recognizing the entities ”stephenjeske” and
”CBC Manitoba”. However, through the RDC strategy, the LinkNER can correctly
classify these two entity categories. We find that the effectiveness of
GPT-3.5 also depends on the recognition and detection results of the local
model. Therefore, the uncertainty-based RDC strategy takes advantage of the
two models in LinkNER and makes them complement each other.

##  Appendix B E-NER Optimization Function

In this section, we give the detailed formulation of the E-NER optimization
function. E-NER mainly includes two components, namely the classification loss
function $\mathcal{L}_{\mathrm{cls}}$ and the penalty loss function
$\mathcal{L}_{\mathrm{penalty}}$, as follows:

(6) $\displaystyle\mathcal{L}_{E}\\!=$
$\displaystyle\mathcal{L}_{\mathrm{cls}}+\mathcal{L}_{\mathrm{penalty}}.$

Specifically, given a sample $(x^{i},\mathbf{y}^{i})$, the two components are
as follows:

(a) training utilizes cross-entropy loss to learn evidence for the correct
class:

(7)
$\displaystyle\mathcal{L}^{i}_{\mathrm{cls}}={\sum_{c=1}^{C}W^{i}_{c}\left(\psi(S^{i})-\psi(\alpha^{i}_{c})\right)},$

where $W^{i}=(\mathbf{1}-\mathbf{e}^{i}/\alpha_{0})\odot\mathbf{y}^{i}$ is
reweighed one-hot $C$-dimensional label for sample $x^{i}$ to reduce
overfitting, $\psi(\cdot)$ is the digamma function.

(b) Penalty terms include KL divergence and uncertainty optimization terms. KL
divergence serves as a distribution penalty for other classes, and uncertainty
optimization focuses on wrong entities:

(8) $\displaystyle\mathcal{L}^{i}_{\mathrm{penalty}}=$
$\displaystyle{\lambda_{1}KL[{\rm{Dir}}(\mathbf{p}^{i}|{\widetilde{\boldsymbol{\alpha}}^{i})}||{\rm{Dir}}(\mathbf{p}^{i}|\mathbf{1})]}-$
$\displaystyle{\lambda_{2}\sum_{i\in\\{\hat{y}^{i}\neq
y^{i}\\}}{\rm{log}}(u^{i})},$

where $\lambda_{1}$ and $\lambda_{2}$ are the balance factor,
${\rm{Dir}}(\mathbf{p}^{i}|\mathbf{1})$ is a special case which is equivalent
to the uniform distribution, and
$\widetilde{\boldsymbol{\alpha}}^{i}=\mathbf{y}^{i}+(1-\mathbf{y}^{i})\odot\boldsymbol{\alpha}^{i}$
denotes the masked parameters while $\odot$ refers to the Hadamard (element-
wise) product, which removes the non-misleading evidence from predicted
parameters $\boldsymbol{\alpha}^{i}$.

##  Appendix C Implementation Details

For local models, we use E-NER with BERT-base-uncased as the base encoder
(Devlin et al., 2019). The dropout rate is set to 0.2 and the BERT dropout
rate is set to 0.15. The AdamW optimizer (Loshchilov and Hutter, 2019) is used
for training the CoNLL’03 dataset with a learning rate of 1e-5 and a training
batch size of 10. To improve training efficiency, sentences are truncated to a
maximum length of 128, and the maximum length of the span enumeration is set
to 4. The initial value of $\lambda_{0}$ is set to 1e-02. We use heuristic
decoding and retain the highest probability span for flattened entity
recognition in span-based methods. In this study, the large language model
chose gpt-3.5-turbo and Llama 2-Chat as the linked LLM. As shown in Table 7,
we decide the uncertainty threshold $\tau$ by the method in §5.4. It is worth
noting that CoNLL’03-Typos, CoNLL’03-OOV and WikiGold all use CoNLL’03 as the
source dataset, so the label description and threshold $\tau$ also use the
corresponding information of the CoNLL’03 validation set. Moreover, we
summarize the label descriptions in Table 8.

Table 8. The label description information in each dataset involved in the experiment, and the selected threshold. Dataset |  Label description
---|---
CoNLL’03 CoNLL’03-Typos CoNLL’03-OOV WikiGold |  ”Here is the entity class information: Person: This category includes names of persons, such as individual people or groups of people with personal names. Organization: The organization category consists of names of companies, institutions, or any other group or entity formed for a specific purpose. Location: The location category represents names of geographical places or landmarks, such as cities, countries, rivers, or mountains. Miscellaneous: The miscellaneous category encompasses entities that do not fall into the above three categories. This includes adjectives, like Italian, and events, like 1000 Lakes Rally, making it a very diverse category.”
1-2  OntoNotes 5.0 |  ”Here is the entity class information: PERSON: People, including fictional; ORGANIZATION: Companies, agencies, institutions, etc. GPE: Countries, cities, states; DATE: Absolute or relative dates or periods; NORP: Nationalities or religious or political groups; CARDINAL: Numerals that do not fall under another type; TIME: Times smaller than a day; LOC: Non-GPE locations, mountain ranges, bodies of water; FACILITY:Buildings, airports, highways, bridges, etc; PRODUCT: Vehicles, weapons, foods, etc. (Not services); WORK_OF_ART: Titles of books, songs, etc; MONEY: Monetary values, including unit; ORDINAL: “first”, “second”, etc; QUANTITY: Measurements, as of weight or distance, etc; EVENT: Named hurricanes, battles, wars, sports events, etc; PERCENT: Percentage (including “%”), etc; LAW: Named documents made into laws, etc; LANGUAGE: Any named language, etc.”
1-2  Wnut’17 |  ”Here is all entity class information: Person: Names of people (e.g. Virginia Wade). Don’t mark people that don’t have their own name. Include punctuation in the middle of names. Fictional people can be included, as long as they’re referred to by name (e.g. Harry Potter). Location: Names that are locations (e.g. France). Don’t mark locations that don’t have their own name. Include punctuation in the middle of names. Fictional locations can be included, as long as they’re referred to by name (e.g. Hogwarts). Corporation: Names of corporations (e.g. Google). Don’t mark locations that don’t have their own name. Include punctuation in the middle of names. Product: Name of products (e.g. iPhone). Don’t mark products that don’t have their own name. Include punctuation in the middle of names. Fictional products can be included, as long as they’re referred to by name (e.g. Everlasting Gobstopper). It’s got to be something you can touch, and it’s got to be the official name. Creative-work: Names of creative works (e.g. Bohemian Rhapsody). Include punctuation in the middle of names. The work should be created by a human, and referred to by its specific name. Group: Names of groups (e.g. Nirvana, San Diego Padres). Don’t mark groups that don’t have a specific, unique name, or companies (which should be marked corporation).”
1-2  TweetNER |  ”Here is the entity class information: For polysemous entities, our guidelines instructed annotators to assign the entity class that corresponds to the correct entity class in the given context. For example, in “We’re driving to Manchester”, Manchester is a Location, but in “Manchester are in the final tonight”, it is a sports club – an Organization. Special attention is given to username mentions. Where other corpora have blocked these out or classified them universally as Person, our approach is to treat these as named entities of any potential class. For example, the account belonging to the M̈anchester United football clubẅould be labeled as an Organization. Other: The Other category encompasses entities that do not fall into the above three categories. This includes adjectives, like Italian, and events, like 1000 Lakes Rally, making it a very diverse category.”
1-2  JNLPBA |  ”Here is the entity class information: The composition of the Protein category includes protein molecules, complexes, etc. The DNA is Deoxyribonucleic Acid. The RNA is Ribonucleic Acid. The Cell_type category refers to the Cell type in nature. The Cell_line category refers to the Cell line in artificial.”