# Hafnian of two-parameter matrices

Dmitry Efimov
Institute of Physics and Mathematics,
Komi Science Centre UrD RAS,
Syktyvkar, Russia e-mail<EMAIL_ADDRESS>
###### Abstract

The concept of the hafnian first appeared in the works on quantum field theory
by E. R. Caianiello. However, it also has an important combinatorial property:
the hafnian of the adjacency matrix of an undirected weighted graph is equal
to the total sum of the weights of perfect matchings in this graph. In
general, the use of the hafnian is limited by the complexity of its
computation. In this paper, we present an efficient method for the exact
calculation of the hafnian of two-parameter matrices. In terms of graphs, we
count the total sum of the weights of perfect matchings in graphs whose edge
weights take only two values. This method is based on the formula expressing
the hafnian of a sum of two matrices through the product of the hafnians of
their submatrices. The necessary condition for the application of this method
is the possibility to count the number of $k$-edge matchings in some graphs.
We consider two special cases in detail using a Toeplitz matrix as the two-
parameter matrix. As an example, we propose a new interpretation of some of
the sequences from the On-Line Encyclopedia of Integer Sequences and then
provide new analytical formulas to count the number of certain linear chord
diagrams.

## Introduction

Let $A=(a_{ij})$ be a symmetric matrix of even order $n$ over a commutative
associative ring. The hafnian of $A$ is defined as

$\textrm{Hf}(A)=\sum_{(i_{1}i_{2}|\dots|i_{n-1}i_{n})}a_{i_{1}i_{2}}\cdots
a_{i_{n-1}i_{n}},$

where the sum ranges over all unordered partitions of the set
$\\{1,2,\dots,n\\}$ into unordered pairs $(i_{1}i_{2})$, $\dots$,
$(i_{n-1}i_{n})$. Therefore, if $n=4$, then
$\textrm{Hf}(A)=a_{12}a_{34}+a_{13}a_{24}+a_{14}a_{23}$. The hafnian of the
empty matrix is considered as $1$. Note that the elements of the main diagonal
are not included in the definition of the hafnian. For the sake of
convenience, we assume that all matrices under consideration have a zero main
diagonal.

A $k$-edge matching in a graph is a set of its $k$ pairwise nonadjacent edges.
An $m$-edge matching in a graph with $2m$ vertices is called perfect matching.
If a graph is weighted, then the weight of the matching is a product of the
weights of the edges included in this matching. The hafnian has a useful
combinatorial property related to an important problem in graph theory and its
applications: if $M$ is the adjacency matrix of an undirected weighted graph
with an even number of vertices, then $\textrm{Hf}(M)$ equals the total sum of
the weights of the perfect matchings in the graph. Unfortunately, the
widespread use of the hafnian is limited due to the complexity of its
computations in general. For example, one of the fastest exact algorithms to
compute the hafnian of an arbitrary complex $n\times n$ matrix runs in
$O(n^{3}2^{n/2})$ time, and, as the authors show, it seems to be close to an
optimal one [1].

Because the calculation of the hafnian has a high computational complexity in
general, the actual problem is the discovery of efficient analytical formulas
expressing the hafnian for special classes of matrices. Let $T_{n}$ be a
symmetric $(0,1)$-matrix of order $n$, and let $a$ and $b$ be elements of a
ring $R$. We denote a symmetric matrix of order $n$ by $T_{n}(a,b)$, which is
obtained from $T_{n}$ by replacing all instances of $1$ by $a$ and all zero
elements outside the main diagonal by $b$. For example (dots denote zeros),

$T_{4}=\left(\begin{array}[]{cccc}\cdot&1&\cdot&1\\\ 1&\cdot&1&\cdot\\\
\cdot&1&\cdot&1\\\ 1&\cdot&1&\cdot\end{array}\right)\ \ \Longrightarrow\ \
T_{4}(a,b)=\left(\begin{array}[]{cccc}\cdot&a&b&a\\\ a&\cdot&a&b\\\
b&a&\cdot&a\\\ a&b&a&\cdot\end{array}\right).$

We can say that $T_{n}(a,b)$ is a two-parameter matrix, and $T_{n}$ is the
template for $T_{n}(a,b)$. Note that $T_{n}(1,0)=T_{n}$. In our work, we
present an effective method for the exact computation of the hafnian of
matrices $T_{n}(a,b)$. In terms of graphs, we count the total sum of weights
of perfect matchings in two-parameter weighted graphs (i.e., weights of the
edges are only $a$ and $b$). This method is based on the formula expressing
the hafnian of a sum of two matrices through the sum of the product of the
hafnians of matrices and is also closely linked to the combinatorial problem
of counting the number of $k$-edge matchings in graphs. In theoretical
physics, this problem is known as the monomer-dimer problem [2].

ABCDEFABCDEF Figure 1: A binary tree and its corresponding arc diagram

Recall that an arc diagram is a graph presentation method in which all the
vertices are located along a line in the plane, whereas all edges are drawn as
arcs (Figure 1). In this work, it will be convenient for us to represent
graphs in the form of arc diagrams. Perfect matchings of arc diagrams are
often called linear chord diagrams [3, 4].

##  1 Hafnian of two-parameter matrices

To begin with, consider two properties of the hafnian. The first one is quite
obvious.

######  Proposition 1.

Let $A$ be a symmetric matrix of even order $n$ over a commutative associative
ring $R$, and $c\in R$. Then

$\mathrm{Hf}(cA)=c^{n/2}\mathrm{Hf}(A).$ (1)

Let $Q_{k,n}$ denote the set of all unordered $k$-element subsets of
$\\{1,2,\dots,n\\}$. Let $A$ be a matrix of order $n$ and $\alpha\in Q_{k,n}$.
Moreover, $A[\alpha]$ denotes the submatrix of $A$ formed by the rows and
columns of $A$ with numbers in $\alpha$, and $A\\{\alpha\\}$ denotes the
submatrix of $A$ formed from $A$ by removing the rows and columns with numbers
in $\alpha$. The following property was proved in [5]:

######  Proposition 2.

Let $A$ and $B$ be symmetric matrices of even order $n$. Then

$\mathrm{Hf}(A+B)=\sum_{k=0}^{n/2}\sum_{\alpha\in
Q_{2k,n}}\mathrm{Hf}(A[\alpha])\mathrm{Hf}(B\\{\alpha\\}).$ (2)

$J_{n}(b)$ denotes a matrix of order $n$ whose elements outside the main
diagonal are equal to $b$. From the definition of the hafnian, it follows that

$\mathrm{Hf}(J_{2m}(b))=b^{m}\frac{(2m)!}{m!2^{m}}.$ (3)

Since $T_{2m}(a,b)=J_{2m}(b)+T_{2m}(a-b,0)$, using formulas (1), (2), and (3),
we can write the following:

$\begin{split}&\mathrm{Hf}(T_{2m}(a,b))=\mathrm{Hf}(J_{2m}(b)+T_{2m}(a-b,0))=\\\
&=\sum_{k=0}^{m}\sum_{\alpha\in
Q_{2k,2m}}\mathrm{Hf}(J_{2m}(b)[\alpha])\mathrm{Hf}(T_{2m}(a-b,0)\\{\alpha\\})=\\\
&=\sum_{k=0}^{m}(a-b)^{m-k}b^{k}\frac{(2k)!}{k!2^{k}}\sum_{\alpha\in
Q_{2k,2m}}\mathrm{Hf}(T_{2m}\\{\alpha\\}).\end{split}$ (4)

Here, we use the fact that the matrix $J_{2m}(b)[\alpha]$ has the same form as
the initial matrix $J_{2m}(b)$, that is, $J_{2m}(b)[\alpha]$ is a matrix of
order $2k$ whose elements outside the main diagonal are equal to $b$. If $M$
is a symmetric nonnegative integer matrix, then $\Gamma(M)$ denotes a
multigraph with the adjacency matrix $M$. If $\alpha\in Q_{2k,2m}$, then the
hafnian $\mathrm{Hf}(T_{2m}\\{\alpha\\})$ equals the cardinality of a set of
$(m-k)$-edge matchings in the graph $\Gamma(T_{2m})$; moreover, such sets do
not intersect for different $\alpha$, and their union is the set of all
$(m-k)$-edge matchings of the graph $\Gamma(T_{2m})$. Given a graph $\Gamma$,
let $\mu_{k}(\Gamma)$ denote the number of all its $k$-edge matchings. By
definition, we set $\mu_{0}(\Gamma)=1$. Thus,

$\sum_{\alpha\in
Q_{2k,2m}}\mathrm{Hf}(T_{2m}\\{\alpha\\})=\mu_{m-k}(\Gamma(T_{2m})),$

and therefore,

$\mathrm{Hf}(T_{2m}(a,b))=\sum_{k=0}^{m}(a-b)^{m-k}b^{k}\frac{(2k)!}{k!2^{k}}\mu_{m-k}(\Gamma(T_{2m})).$
(5)

Note that (5) is the special case of Theorems 1W and 3W given in [6] in terms
of matching vectors of weighted graphs and their complements. The special case
of (5) when $a=0$ and $b=1$ is also given in [7] (Theorem $4$).

Thus, to calculate the hafnian of a two-parameter matrix by using formula (5),
one needs to determine the number of $k$-edge matchings of graphs
corresponding to the matrix, which is a nontrivial task in general. One of the
simplest special cases was considered in [8]. In the following section, we
consider a few more complicated special cases.

##  2 Hafnian of Toeplitz matrices of the first type

Recall that a matrix is called Toeplitz if all its diagonals parallel to the
main diagonal consist of the same elements. It is obvious that a symmetric
Toeplitz matrix is uniquely determined by its first row. As the template
matrix $T_{n}$, consider a symmetric Toeplitz matrix of order $n$ with the
first row

$\left(\begin{array}[]{cccccc}0&0&1&0&\dots&0\end{array}\right).$

We denote it by $C_{n}$. This matrix is the adjacency matrix of the arc
diagram shown in Figure 2.

1234$n-2$$n-1$$n$ Figure 2: The arc diagram $\Gamma(C_{n})$

######  Proposition 3.

Let $k$ and $n$ be a pair of nonnegative integers. Suppose $n\not=2k$ when $k$
is odd. Then, the inequality

$\left\lceil\frac{3k-n}{2}\right\rceil\leq\left\lfloor\frac{k}{2}\right\rfloor$
(6)

is equivalent to

$k\leq\left\lfloor\frac{n}{2}\right\rfloor.$ (7)

###### Proof.

Suppose (7) is wrong, which means that $n=2k-c$, where $c\geq 1$. On
substituting this expression for $n$ into the inequality (6), we can see that
the result is wrong as well. Now suppose (7) is true. Then, $n=2k+c$ and
$\left\lceil\frac{3k-n}{2}\right\rceil=\left\lceil\frac{k-c}{2}\right\rceil$ ,
where $c\geq 0$. If $k$ is even, then $\left\lceil\frac{k-c}{2}\right\rceil$
does not exceed $\left\lfloor\frac{k}{2}\right\rfloor$. If $k$ is odd, then,
by the assumption, $n\not=2k$. Therefore, $c\geq 1$, and
$\left\lceil\frac{k-c}{2}\right\rceil$ also does not exceed
$\left\lfloor\frac{k}{2}\right\rfloor$. Thus, the inequality (6) also holds. ∎

######  Proposition 4.

Let $k$ and $n$ be a pair of nonnegative integers. If
$k\leq\left\lfloor\frac{n}{2}\right\rfloor$, but $n\not=2k$ when $k$ is odd,
then the number of $k$-edge matchings in the arc diagram $\Gamma(C_{n})$ is

$\mu_{k}(\Gamma(C_{n}))=\sum\limits_{i=\max{\left(0,\left\lceil\frac{3k-n}{2}\right\rceil\right)}}^{\left\lfloor\frac{k}{2}\right\rfloor}{n-2k+i\choose
k-i}{k-i\choose i}.$ (8)

Otherwise, $\mu_{k}(\Gamma(C_{n}))=0$.

###### Proof.

For the sake of convenience, we use the abbreviated notation $v_{n,k}$ for
$\mu_{k}(\Gamma(C_{n}))$. Consider a $k$-edge matching in $\Gamma(C_{n})$. It
is obvious that if $k>\left\lfloor\frac{n}{2}\right\rfloor$, then $v_{n,k}$=0.
If $n\geq 4$, then the following three cases are possible: the first vertex of
the diagram is not incident to the edge of the matching (Figure 3(a)); the
first vertex is incident to an edge of the matching, but the second vertex is
not (Figure 3(b)); the first and second vertices are incident to the edges of
the matching (Figure 3(c)).

1(a)123(b)1234(c) Figure 3: Possible cases of matchings in the arc diagram
$\Gamma(C_{n})$

It follows from the above that $v_{n,k}$ satisfies the recurrence relation

$v_{n+4,k+2}=v_{n+3,k+2}+v_{n+1,k+1}+v_{n,k}$ (9)

with the initial conditions $v_{n,k}=0$ for
$k>\left\lfloor\frac{n}{2}\right\rfloor$; $v_{n,0}=1$ for all $n$;
$v_{n,1}=n-2$ for $n\geq 2$. Consider the two-parameter generating function
$v(x,t)$ for the sequence $v_{n,k}$:

$v(x,t)=\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}v_{n,k}x^{k}t^{n}.$

By multiplying (9) by $x^{k+3}t^{n+3}$ and summing over all possible $k$ and
$n$, we obtain the following equation:

$\begin{split}\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}v_{n+4,k+2}x^{k+3}t^{n+3}=\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}v_{n+3,k+2}x^{k+3}t^{n+3}+\\\
+\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}v_{n+1,k+1}x^{k+3}t^{n+3}+\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}v_{n,k}x^{k+3}t^{n+3}.\end{split}$
(10)

Consider separately the formal power series on the left side of this equation.

$\begin{split}\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}v_{n+4,k+2}x^{k+3}t^{n+3}=\frac{x}{t}\left(\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}v_{n+4,k+2}x^{k+2}t^{n+4}\right)=\\\
=\frac{x}{t}\left(v(x,t)-\sum_{n=0}^{+\infty}v_{n,0}t^{n}-\sum_{n=1}^{+\infty}v_{n,1}xt^{n}\right)=\\\
=\frac{x}{t}\left(v(x,t)-\sum_{n=0}^{+\infty}t^{n}-x\sum_{n=3}^{+\infty}(n-2)t^{n}\right)=\\\
=\frac{x}{t}\left(v(x,t)-\frac{1}{1-t}-xt^{3}\left(\sum_{n=1}^{+\infty}t^{n}\right)^{\prime}\right)=\\\
=\frac{x}{t}\left(v(x,t)-\frac{1}{1-t}-\frac{xt^{3}}{(1-t)^{2}}\right).\end{split}$

In the same way, we get

$\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}v_{n+3,k+2}x^{k+3}t^{n+3}=x\left(v(x,t)-\frac{1}{1-t}-\frac{xt^{3}}{(1-t)^{2}}\right).$

In addition,

$\begin{split}\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}v_{n+1,k+1}x^{k+3}t^{n+3}=x^{2}t^{2}\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}v_{n+1,k+1}x^{k+1}t^{n+1}=\\\
x^{2}t^{2}\left(v(x,t)-\sum_{n=0}^{+\infty}v_{n,0}t^{n}\right)=x^{2}t^{2}\left(v(x,t)-\frac{1}{1-t}\right).\end{split}$

Finally,

$\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}v_{n,k}x^{k+3}t^{n+3}=x^{3}t^{3}v(x,t).$

On substituting all of the above into (10), we get

$\displaystyle\frac{x}{t}\left(v(x,t)-\frac{1}{1-t}-\frac{xt^{3}}{(1-t)^{2}}\right)=x\left(v(x,t)-\frac{1}{1-t}-\frac{xt^{3}}{(1-t)^{2}}\right)+$
$\displaystyle+x^{2}t^{2}\left(v(x,t)-\frac{1}{1-t}\right)+x^{3}t^{3}v(x,t).$

On solving this equation, we obtain:

$\begin{split}v(x,t)=\frac{1}{1-t(1+xt^{2}+x^{2}t^{3})}=\sum_{m=0}^{+\infty}t^{m}(1+xt^{2}+x^{2}t^{3})^{m}=\\\
\sum_{m=0}^{+\infty}t^{m}\sum_{j=0}^{m}{m\choose
j}(xt^{2}+x^{2}t^{3})^{j}=\sum_{m=0}^{+\infty}\sum_{j=0}^{m}{m\choose
j}x^{j}t^{m+2j}(1+xt)^{j}=\\\ \sum_{m=0}^{+\infty}\sum_{j=0}^{m}{m\choose
j}x^{j}t^{m+2j}\sum_{i=0}^{j}{j\choose
i}(xt)^{i}=\sum_{m=0}^{+\infty}\sum_{j=0}^{m}\sum_{i=0}^{j}{m\choose
j}{j\choose i}x^{j+i}t^{m+2j+i}.\end{split}$ (11)

Fix nonnegative integers $k,n$, $k\leq\left\lfloor\frac{n}{2}\right\rfloor$.
From (11), we see that the coefficient at $x^{k}t^{n}$ is equal to
$\sum\limits_{i}C_{n-2k+i}^{k-i}C_{k-i}^{i}$ over all $i$, for which the
inequalities $i\geq 0$, $k-i\geq i$, $n-2k+i\geq k-i$ hold. The last two
inequalities can be rewritten as $i\leq\left\lfloor\frac{k}{2}\right\rfloor$,
$i\geq\left\lceil\frac{3k-n}{2}\right\rceil$. Thus, for the set of acceptable
values of $i$ to be nonempty, it is necessary that
$\left\lceil\frac{3k-n}{2}\right\rceil\leq\left\lfloor\frac{k}{2}\right\rfloor$.
However, according to Proposition 3, this condition is equivalent to
$k\leq\left\lfloor\frac{n}{2}\right\rfloor$, except for the case when $k$ is
odd and $n=2k$. In the last case, it is clear that the inequality
$\left\lceil\frac{3k-n}{2}\right\rceil\leq\left\lfloor\frac{k}{2}\right\rfloor$
does not hold, and therefore, the coefficient at $x^{k}t^{n}$ is equal to
zero. This completes the proof. ∎

######  Remark 1.

Several initial values $\mu_{k}(\Gamma(C_{n}))$ are presented in Table 1. The
empty cells correspond to zero. Table 1 coincides with Table $A220074$ in [9]
up to the sign.

$k$ $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$
---|---|---|---|---|---|---|---|---|---|---|---|---|---
|  |  |  |  |  |  |  |  |  |  |  |  |
$0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$
$1$ |  |  |  | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$
$2$ |  |  |  |  | $1$ | $2$ | $4$ | $7$ | $11$ | $16$ | $22$ | $29$ | $37$
$3$ |  |  |  |  |  |  |  | $2$ | $6$ | $13$ | $24$ | $40$ | $62$
$4$ |  |  |  |  |  |  |  |  | $1$ | $3$ | $9$ | $22$ | $46$
$5$ |  |  |  |  |  |  |  |  |  |  |  | $3$ | $12$
$6$ |  |  |  |  |  |  |  |  |  |  |  |  | $1$
Table 1: Number of $k$-edge matchings in the graph $\Gamma(C_{n})$

Let $R$ be a commutative associative ring with $1$ and $a,b\in R$. Consider a
symmetric two-parameter Toeplitz matrix $C_{2m}(a,b)$ having the first row of
the form

$\left(\begin{array}[]{cccccc}0&b&a&b&\dots&b\end{array}\right).$

On substituting the value $\mu_{m-k}(\Gamma(C_{2m}))$ in (5), we obtain the
following theorem:

######  Theorem 1.

If we assume that $0^{0}=1$, then the hafnian of the matrix $C_{2m}(a,b)$ can
be calculated using the following formula:

$\begin{split}&\mathrm{Hf}(C_{2m}(a,b))=\\\
&\sum_{k=p}^{m}(a-b)^{m-k}b^{k}\frac{(2k)!}{k!2^{k}}\sum\limits_{i=\max{\left(0,\left\lceil\frac{m-3k}{2}\right\rceil\right)}}^{\left\lfloor\frac{m-k}{2}\right\rfloor}{2k+i\choose
m-k-i}{m-k-i\choose i}\ ,\end{split}$ (12)

where $p=0$ when $m$ is even and $p=1$ when $m$ is odd.

######  Remark 2.

Equality (12) allows us to calculate $\mathrm{Hf}(C_{2m}(a,b))$ in time
$O(m^{3})$.

######  Example 1.

Consider the matrix $C_{2m}(0,1)$. By calculating its hafnian using formula
(12) for consecutive $m$’s, we obtain the sequence:

$\begin{array}[]{c|c|c|c|c|c|c|c|c|c|c|c}m&1&2&3&4&5&6&7&8&9&10&\dots\\\
\hline\cr\mathrm{Hf}&1&2&7&43&372&4027&51871&773186&13083385&247698481&\dots\end{array}$

In terms of graph theory, its $m$-th member equals the number of perfect
matchings in the arc diagram $\Gamma(C_{2m}(0,1))$ (Figure 4). In other words,
this is the number of linear chord diagrams with $m$ chords such that the
length of each chord does not equal $2$ (see [4]). This sequence has the
number $A265229$ in [9], but its description does not contain the
interpretation given here.

123456123456123456123456123456123456123456123456 Figure 4: The arc diagram
$\Gamma(C_{6}(0,1))$ and all its perfect matchings

##  3 Hafnian of Toeplitz matrices of the second type

As the template matrix $T_{n}$, now consider a symmetric Toeplitz matrix of
order $n$ with the first row

$\left(\begin{array}[]{cccccc}0&1&1&0&\dots&0\end{array}\right).$

We denote it by $D_{n}$. This matrix is the adjacency matrix of the arc
diagram shown in Figure 5.

1234$n-2$$n-1$$n$ Figure 5: The arc diagram $\Gamma(D_{n})$

######  Theorem 2.

Let $k$ and $n$ be nonnegative integers such that
$k\leq\left\lfloor\frac{n}{2}\right\rfloor$. Then, the number of $k$-edge
matchings in the arc diagram $\Gamma(D_{n})$ is equal to the following:

$\mu_{k}(\Gamma(D_{n}))=\sum_{i=0}^{\min(k,\left\lfloor\frac{n-k}{2}\right\rfloor)}\sum\limits_{p=\max(0,i+2k-n)}^{\min(i,k-i)}{n-k-i\choose
k-p}{k-p\choose i}{i\choose p}.$ (13)

###### Proof.

For convenience, we use the abbreviated notation $w_{n,k}$ for
$\mu_{k}(\Gamma(D_{n}))$. Consider a $k$-edge matching in $\Gamma(D_{n})$. If
$n\geq 4$, then the following four cases are possible: the first vertex of the
diagram is not incident to the edge of the matching (Figure 6(a)); the first
and second vertices are connected by an edge of the matching (Figure 6(b));
the first vertex is incident to an edge of the matching, but the second vertex
is not (Figure 6(c)); the first and second vertices are incident to different
edges of the matching (Figure 6(d)).

1(a)12(b)123(c)1234(d) Figure 6: Possible cases of matchings in the arc
diagram $\Gamma(D_{n})$

It follows from the above that $w_{n,k}$ satisfies the recurrence relation

$w_{n+4,k+2}=w_{n+3,k+2}+w_{n+2,k+1}+w_{n+1,k+1}+w_{n,k}$ (14)

with the initial conditions $w_{n,k}=0$ for
$k>\left\lfloor\frac{n}{2}\right\rfloor$; $w_{n,0}=1$ for all $n$;
$w_{n,1}=2n-3$ for $n\geq 2$. Consider the two-parameter generating function
for the sequence $w_{n,k}$:

$w(x,t)=\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}w_{n,k}x^{k}t^{n}.$

On multiplying (14) by $x^{k+3}t^{n+3}$ and summing over all possible $k$ and
$n$, we get the following equation:

$\begin{split}\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}w_{n+4,k+2}x^{k+3}t^{n+3}=\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}w_{n+3,k+2}x^{k+3}t^{n+3}+\\\
\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}w_{n+2,k+1}x^{k+3}t^{n+3}+\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}w_{n+1,k+1}x^{k+3}t^{n+3}+\\\
\sum_{n=0}^{+\infty}\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}w_{n,k}x^{k+3}t^{n+3}.\end{split}$
(15)

On solving this equation, we obtain:

$\begin{split}w(x,t)=&\frac{1}{1-t(1+xt+xt^{2}+x^{2}t^{3})}=\\\
&\sum_{m=0}^{+\infty}\sum_{j=0}^{m}\sum_{i=0}^{j}\sum_{p=0}^{i}{m\choose
j}{j\choose i}{i\choose p}x^{j+p}t^{m+j+i+p}.\end{split}$ (16)

Fix nonnegative integers $k$ and $n\geq 2k$. From (16), we see that the
coefficient at $x^{k}t^{n}$ is equal to the sum
$\sum\limits_{i}\sum\limits_{p}{n-k-i\choose k-p}{k-p\choose i}{i\choose p}$,
over all $i,p$ for which the inequalities $i\geq p\geq 0$, $k-p\geq i$,
$n-k-i\geq k-p$ hold. It can be shown that this system of inequalities is
equivalent to the following system of inequalities: $0\leq
i\leq\min(k,\left\lfloor\frac{n-k}{2}\right\rfloor)$, $\max(0,i+2k-n)\leq
p\leq\min(i,k-i)$. This completes the proof. ∎

######  Remark 3.

Note that the arc diagram $\Gamma(D_{n})$ is isomorphic to the triangular
lattice shown in Figure 7. Thus, formula (13) also allows us to calculate the
number of $k$-edge matchings in such lattices.

214365$n-2$$n-3$$n$$n-1$(a)214365$n-1$$n-2$$n$(b) Figure 7: The triangular
lattice $\Gamma(D_{n})$: (a) $n$ is even; (b) $n$ is odd

######  Remark 4.

Several initial values $\mu_{k}(\Gamma(D_{n}))$ are presented in Table 2. The
empty cells correspond to zero. Note that the sequence of the first nonzero
elements in the rows is the Fibonacci sequence, the sequence of the second
nonzero elements in the rows has the number $A023610$ in [9], and nonzero
elements of the third row coincide with the sequence $A130883$, excluding the
starting element.

$k$ $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$
---|---|---|---|---|---|---|---|---|---|---|---|---|---
|  |  |  |  |  |  |  |  |  |  |  |  |
$0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$
$1$ |  |  | $1$ | $3$ | $5$ | $7$ | $9$ | $11$ | $13$ | $15$ | $17$ | $19$ | $21$
$2$ |  |  |  |  | $2$ | $7$ | $16$ | $29$ | $46$ | $67$ | $92$ | $121$ | $154$
$3$ |  |  |  |  |  |  | $3$ | $15$ | $43$ | $95$ | $179$ | $303$ | $475$
$4$ |  |  |  |  |  |  |  |  | $5$ | $30$ | $104$ | $271$ | $591$
$5$ |  |  |  |  |  |  |  |  |  |  | $8$ | $58$ | $235$
$6$ |  |  |  |  |  |  |  |  |  |  |  |  | $13$
Table 2: Number of $k$-edge matchings in the graph $\Gamma(D_{n})$

Let $R$ be a commutative associative ring with $1$ and $a,b\in R$. Consider a
symmetric two-parameter Toeplitz matrix $D_{2m}(a,b)$ having the first row in
the form

$\left(\begin{array}[]{cccccc}0&a&a&b&\dots&b\end{array}\right).$

On substituting the value $\mu_{m-k}(\Gamma(D_{2m}))$ in (5), we obtain the
following theorem:

######  Theorem 3.

If we assume that $0^{0}=1$, then the hafnian of the matrix $D_{2m}(a,b)$ is
expressed using the following formula:

$\mathrm{Hf}(D_{2m}(a,b))=\sum_{k=0}^{m}(a-b)^{m-k}b^{k}\frac{(2k)!}{k!2^{k}}\mu_{m-k}(\Gamma(D_{2m}))\
,$ (17)

where

$\begin{split}&\mu_{m-k}(\Gamma(D_{2m}))=\\\
&\sum_{i=0}^{\min(m-k,\left\lfloor\frac{m+k}{2}\right\rfloor)}\sum\limits_{p=\max(0,i-2k)}^{\min(i,m-k-i)}{m+k-i\choose
m-k-p}{m-k-p\choose i}{i\choose p}.\end{split}$

######  Remark 5.

Equality (17) allows us to calculate $\mathrm{Hf}(D_{2m}(a,b))$ in time
$O(m^{4})$.

######  Example 2.

Consider the matrix $D_{2m}(0,1)$. By calculating its hafnian using formula
(17) for consecutive $m$s, we obtain the sequence:

$\begin{array}[]{c|c|c|c|c|c|c|c|c|c|c|c|}m&1&2&3&4&5&6&7&8&9&10&\dots\\\
\hline\cr\mathrm{Hf}&0&0&1&10&99&1146&15422&237135&4106680&79154927&\dots\end{array}$

In terms of graphs, the $m$-th member is equal to the number of perfect
matchings in the arc diagram $\Gamma(D_{2m}(0,1))$ (Figure 8). In other words,
this is the number of linear chord diagrams with $m$ chords such that the
length of every chord is at least $3$ (see also [4], [10]). This sequence has
the number $A190823$ in [9].

123456123456 Figure 8: The arc diagram $\Gamma(D_{6}(0,1))$ and its only
perfect matching

## References

  * [1] Björklund A., Gupt B., Quesada N. A faster hafnian formula for complex matrices and its benchmarking on a supercomputer // ACM Journal of Experimental Algorithmics. 2019. V. 24. 1.11.
  * [2] Grimson R.C. Enumeration of Dimer (Domino) Configurations // Discrete Mathematics. 1977. V. 18. pp. 167–178.
  * [3] Krasko E., Omelchenko A. Enumeration of chord diagrams without loops and parallel chords // The Electronic Journal of Combinatorics. 2017. 24(3). #3.43.
  * [4] Sullivan E. Linear chord diagrams with long chords // The Electronic Journal of Combinatorics. 2017. V. 24(4). pp. 1–8.
  * [5] Efimov D.B. The hafnian and a commutative analogue of the Grassmann algebra // Electronic Journal of Linear Algebra. 2018. V. 34. pp. 54-60.
  * [6] Zaslavsky T. Complementary Matching Vectors and the Uniform Matching Extension Property // European Journal of Combinatorics. 1981. V. 2. pp. 91–103.
  * [7] Young D. The Number of Domino Matchings in the Game of Memory // Journal of Integer Sequences. 2018. V. 21(8). pp. 1–14.
  * [8] Efimov D.B. The hafnian of Toeplitz matrices of special type, perfect matchings and Bessel polynomials // Bulletin of Syktyvkar University. Series 1: Mathematics. Mechanics. Informatics. 2018. V. 3(28). pp. 56–64. (in Russian).
  * [9] N.J.A. Sloane, editor The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org.
  * [10] Cameron N.T., Killpatrick K. Statistics on Linear Chord Diagrams // Discrete Mathematics and Theoretical Computer Science. 2019. V. 21(2). pp. 1–10.


# Adapting Coreference Resolution for Processing Violent Death Narratives

Ankith Uppunda, Susan D. Cochran, Jacob G. Foster
Alina Arseniev-Koehler, Vickie M. Mays, Kai-Wei Chang
University of California, Los Angeles<EMAIL_ADDRESS>
###### Abstract

Coreference resolution is an important component in analyzing narrative text
from administrative data (e.g., clinical or police sources). However, existing
coreference models trained on general language corpora suffer from poor
transferability due to domain gaps, especially when they are applied to
gender-inclusive data with lesbian, gay, bisexual, and transgender (LGBT)
individuals. In this paper, we analyzed the challenges of coreference
resolution in an exemplary form of administrative text written in English:
violent death narratives from the USA’s Centers for Disease Control’s (CDC)
National Violent Death Reporting System. We developed a set of data
augmentation rules to improve model performance using a probabilistic data
programming framework. Experiments on narratives from an administrative
database, as well as existing gender-inclusive coreference datasets,
demonstrate the effectiveness of data augmentation in training coreference
models that can better handle text data about LGBT individuals.

##  1 Introduction

Coreference resolution Soon et al. (2001); Ng and Cardie (2002) is the task of
identifying denotative phrases in text that refer to the same entity. It is an
essential component in Natural Language Processing (NLP). In real world
applications of NLP, coreference resolution is crucial for analysts to extract
structured information from text data. Like all components of NLP, it is
important that coreference resolution is robust and accurate, as applications
of NLP may inform policy-making and other decisions. This is especially true
when coreference systems are applied to administrative data, since results may
inform policy-making decisions.

In this paper, we describe an approach to adapting a coreference model to
process narrative text from an important administrative database written in
English: the National Violent Death Reporting System (NVDRS), maintained by
the Centers for Disease Control (CDC) in the USA. Violent death narratives
document murders, suicides, murder-suicides, and other violent deaths. These
narratives are complex, containing information on one or more persons; some
individuals are victims, others are partners (heterosexual or same-sex),
family members, witnesses and law enforcement. Specifically, we apply the End-
to-End Coreference Resolution (E2E-Coref) system Lee et al. (2017, 2018),
which has achieved high performance on the OntoNotes 5.0 Hovy et al. (2006)
corpus. We observe that when a model trained on OntoNotes is applied to
violent death narratives, the performance drops significantly for the
following reasons.

First, despite the fact that OntoNotes contains multiple genres111OntoNotes
contains news sources, broadcasts, talk shows, bible and others. It consists
of mostly news-related documents., it does not include administrative data.
Administrative text data is terse and contains an abundance of domain-specific
jargon. Because of the gap between training and administrative data, models
trained on OntoNotes are poorly equipped to handle administrative data that
are heavily skewed in vocabulary, structure, and style, such as violent death
narratives.

Second, approximately 5% of the victims in the NVDRS are lesbian, gay,
bisexual, or transgender (LGBT). This is a vulnerable population; for example,
existing data show LGB youth are 5 times more likely to attempt suicide than
heterosexual youth Clark et al. (2020) and are more likely to be bullied prior
to suicide222https://www.thetrevorproject.org/resources/preventing-
suicide/facts-about-suicide/. It is essential that data-analytic models work
well with these hard to identify but highly vulnerable populations; indeed
correctly processing text data is an important step in revealing the true
level of elevated risk for LGBT populations. This remains challenging because
of limitations of existing coreference systems. Close relationship partners
provide a marker of sexual orientations and can be used Lira et al. (2019);
Ream (2020) by social scientists to identify relevant information in LGBT
deaths. However, OntoNotes is heavily skewed towards male entities Zhao et al.
(2018) and E2E-Coref relies heavily on gender when deciphering context Cao and
Daumé III (2020). Consequently, E2E-Coref has a trouble dealing with
narratives involving LGBT individuals where gender referents do not follow the
modal pattern.

primary_victim is a 50 year old male. … primary_victim’s partner states that
he  and primary_victim had been living together for three years. …

Figure 1: A snippet of a violent death narrative. Highlighted is what the
e2e-coref model clusters, and the colored text shows what the e2e-coref model
misses.

Figure 1 illustrates a scenario where coreference systems struggle. The model
mislabels the pronoun “he” and this error will propagate to downstream
analysis. Specifically, the model takes the context and resolves the
coreference based on gender; it makes a mistake partially due to an incorrect
presumption of the sexual orientation of the 50 year old male victim.

To study coreference resolution on violent death narratives (VDN), we created
a new corpus that draws on a subset of cases from NVDRS where CDC has reported
the sex of both victims and their partners. We assigned ground truth labels
using experienced annotators trained by social scientists in public
health.333All annotators have signed the release form for accessing the NVDRS
data.

To bridge the domain gap, we further adapted E2E-coref by using a weakly
supervised data creation method empowered by the Snorkel toolkit Ratner et al.
(2017). This toolkit is often used to apply a set of rules to augment data by
probabilistic programming. Inspired by Snorkel, we designed a set of rules to
1) bridge the vocabulary difference between the source and target domains and
2) to mitigate data bias by augmenting data with samples from a more diverse
population. Because labeling public health data requires arduous human labor,
data augmentation provide a promising method to enlarge datasets while
covering a broader range of scenarios.

We verified our adaptation approach on both the in-house VDN dataset as well
as two publicly available English datasets, GICoref Cao and Daumé III (2020)
and MAP Cao and Daumé III (2020). We then measured the performance of our
approach on documents heavily skewed toward LGBT individuals and on documents
in which gendered terms were swapped with non-gendered ones (pronouns, names,
etc.). On all datasets, we achieved an improvement. For LGBT specific
datasets, we see much larger improvements, highlighting how poor the OntoNotes
model performed on these underrepresented populations before. Models trained
on the new data prove more applicable in that domain. _Our experiments
underscore the need for a modifiable tool to train specialized coreference
resolution models across a variety of specific domains and use-cases._

##  2 Related Work

Researchers have shown coreference systems exhibit gender bias and resolve
pronouns by relying heavily on gender information Cao and Daumé III (2020);
Zhao et al. (2018); Rudinger et al. (2018); Webster et al. (2018); Zhao et al.
(2019). In particular, Cao and Daumé III (2020) collected a gender-inclusive
coreference dataset and evaluated how state of the art coreference models
performed against them.

As NLP systems are deployed in social science, policy making, government, and
industry, it is imperative to keep inclusivity in mind when working with
models that perform downstream tasks with text data. For example, Named Entity
Recognition (NER) was used in processing Portuguese police reports to extract
people, location, organization, and time from the set of documents Carnaz et
al. (2019). These authors noted the need for a better training corpus with
more NER entities. Other NLP models face challenges in domain-adaptation like
the one demonstrated in this paper. One example from the biomedical field is
BioBERT Lee et al. (2019), in which the authors achieved better results on
biomedical text mining tasks by pretraining BERT on a set of biomedical
documents. Likewise, even when evaluating a model on a general set,
Babaeianjelodar et al. (2020) showed that many general-domain datasets include
as much bias as datasets designed to be toxic and biased. All these cases
required re-evaluation of the corpus used to train the model. This underscores
the need for methodology that can evaluate, debias, and increase the amount of
data used.

##  3 Annotating Violent Death Narratives

We first applied for and were given access to the CDC’s National Violent Death
Reporting-system’s (NVDRS) Restricted Access Database. From this, we sampled a
total 115 of violent death cases444Homicides and Suicides each over 200 words
in length. In these 115 cases, we had a total of 6,134 coreference links and
44,074 tokens, with a vocabulary size of 3,653. Each case had information
about the victim, the victim’s partner, and the type of death. We randomly
sampled 30 cases from three strata: 1) the victim is male and the partner is
female, 2) the victim is female and the partner is male, and 3) it was an LGBT
case. We also included 25 cases that were particularly challenging for the
general E2E model. The cases used were spell-checked and cleaned thoroughly.

John Smith → J. Smith went to the store. He→Zie wanted to buy apples, bananas,
and strawberries. His→Zir girlfriend came with him→him, and she wanted to buy
peaches and oranges.

Figure 2: The proposed rules for GI data applied to a sample paragraph.

To obtain gold-standard labels, we tasked a team of three annotators555All
annotators signed the release form for accessing the NVDRS data. to label the
coreference ground truth, under the guidance of senior experts in suicide and
public health. Annotators were told that every expression referring to a
specific person or group was to be placed into that person’s or group’s
cluster. From there, we resolved the three label sets into one by a majority
voting method – if two out of three annotators put the phrase in a cluster, we
assigned it to that cluster. Two of the annotators had previous experience
with coding the NVDRS narratives for other tasks, while one was inexperienced.
Agreement was typically unanimous.

#### Reproducibility

To get access to the NVDRS, Users must apply for access and follow a data
management agreement executed directly with CDC. We cannot release VDN or the
annotations but we will provide the augmentation code and instructions on how
reproducing the experiments. To allow reproduction of our approaches on data
without access-restriction, we perform evaluations on MAP and GICoref which
are readily available.

##  4 Weakly-Supervised Data Augmentation for Domain Adaption

Our next step was to build a pipeline for adapting E2E-Coref to resolve
coreference on VDN. The key component of this pipeline is the Snorkel toolkit
and its capacity to design rules that programmatically label, augment, and
slice data. We looked to adapt E2E-Coref to process domain-specific data by
creating a set of augmentation rules that would improve training data
performance. Our rules can generate augmented data with diverse genders and
then challenged our model to predict the coreference clusters.

#### Data Augmentation by Rules

With Snorkel, we assessed the weakness of the current coreference model
systems. These experiments helped us to develop effective augmentation rules
to create training data that mimics challenging data to guide the model going
forward. Specifically, we split data into groups and evaluated our model on
split data. In the case of VDN, we split a larger set of data into two groups
(LGBT and non-LGBT) and gauged model performance on both groups. We then
isolated specific groups of data that posed a problem and came up with sets of
augmentation rules that can be used to generate difficult training data from
easier training cases. For example, in our case, we sought to augment
documents that contained more precisely defined gender into cases with vaguer
language regarding gender often seen in gender-inclusive documents and LGBT
violent death narratives. This was seen in each rule’s effort to strip gender
from key phrases, leaving it more ambiguous to the model. For example, our
model struggles when terms like ‘partner’ are used to describe relationships.
To address this, we introduced a rule where gendered relationship terms like
’girlfriend’ in one cluster were replaced by non-gendered terms like
’partner’. In this manner, our model was forced to train against these
examples. Often, the model performance improved when training against these
augmented examples.

##  5 Experiments and Results

We conducted experiments to analyze E2E-Coref on VDN and verified the
effectiveness of the data augmentation method. We used the following
corpora666VDN must be obtained directly from CDC. We also conducted
experiments on publicly available datasets..

  * •

OntoNotes We used the English portion of version 5.0. It contains roughly 1.6M
words.

  * •

VDN The annotated violent death narratives described in Sec. 3. The corpus is
annotated by domain experts and used as the test set for measuring model
performance. We split VDN into train/dev/test with a 20/5/90 document split.
We are interested in the setting where only a small set of training data is
available, to emulate use-cases in which annotating a large amount of data is
impractical. We reserve more articles in the test set to ensure the evaluation
is reliable.

  * •

GICoref Cao and Daumé III (2020) consists of 95 documents from sources that
include articles about non-binary people, fan-fiction from Archive of Our Own,
and LGBTQ periodicals with a plethora of neopronouns (e.g., zie).

  * •

MAP Cao and Daumé III (2020) consists of snippets of Wikipedia articles with
two or more people and at least one pronoun.

We followed Cao and Daumé III (2020) to use LEA Moosavi and Strube (2016) as
the evaluation metric for coreference clusters.

###  5.1 Results on Violent Death Narratives

We created 3 rules based on the approach described in Sec. 4: (R1) Replace
gendered terms with another gender. (R2) Replace gendered relationship terms
with non-gendered terms. (R3) Replace terms describing gender with non-
gendered terms. Examples of the generated data are in Fig. 2.777See appendix
for violent death narrative rules. When applying the augmented rules to the
current 20/5 document split of the train/development (dev), we ended up with
100/25 train/dev documents enlarging both sets by 5 times.

We compared the following models.

  * •

E2E888For all the models, the number of epochs of training is tuned on the
development set. The E2E-Coref Lee et al. (2018) model trained on the
OntoNotes 5.0 corpus. We used the implementation provided in the AllenNLP
library Gardner et al. (2017).

  * •

E2E-FT E2E-FT is a variant of E2E-Coref. It was trained on OntoNotes first and
then fine-tuned on the 20 target training documents.

  * •

E2E-Aug E2E-Aug trained on OntoNotes first and then fine-tuned on the
augmented target training documents.

| Precision | Recall | F1
---|---|---|---
E2E | 26.6 | 18.2 | 21.8
E2E-FT | 69.9 | 54.8 | 61.4
E2E-Aug | 68.7 | 57.9 | 62.8
Table 1: Performance in LEA of each model on the Violent Death Narratives set.
The E2E model trained on OntoNotes performs terribly on the VDN corpus due to
the domain shift. With data augmentation, E2E-Aug significantly improves on
the performance of E2E.

Results are shown in Table 1. By fine-tuning with a modest amount of in-domain
data, E2E-FT significantly improved E2E in LEA F1. We saw E2E-Aug further
improved E2E-FT by 5% on LEA F1 with the 30 LGBT narratives in VDN’s test
set999Not found in tables. Our results meaningfully improved the
classification of LGBT-related data, and show the need for a more careful
approach with data from underrepresented groups. Further, this improvement
extended beyond our domain-specific data: E2E-Aug further improved the E2E F1
score by 1.4% in LEA F1 on the overall set. Overall, we saw a significant
improvement when training coreference models with our augmented data, on both
the overall and gender-neutral LGBT set.

###  5.2 Results on GICoref and MAP

We then evaluated the data augmentation approach on two publicly available
datasets – GICoref and MAP. We experimented with the following 3 rules. (R4)
Randomly pick a person-cluster in the document and replace all pronouns in the
cluster with a gender neutral pronoun (e.g., his $\leftarrow$ zir). (R5)
Truncate the first name of each person. (R6) Same as the R4 but replacing only
one pronoun in the cluster to the corresponding gender neutral pronoun.

We followed Zhao et al. (2018) and used GICoref and MAP only as the test data.
We compared E2E with its variant E2E-Aug. The latter was trained on the union
of the original dataset and variants of OntoNotes augmented using the above
rules. We also compared our results with those from a E2E-Coref model trained
on the union of the original and augmented data with the gender swapping rules
described in Zhao et al. (2018).

| Precision | Recall |  F1
---|---|---|---
E2E | 39.9 | 34.0 |  36.7
Zhao et al. (2018) | 38.8 | 38.0 |  38.4
E2E-Aug-R4 | 40.5 | 43.8 |  42.1
E2E-Aug-R5 | 41.2 | 41.1 |  41.2
E2E-Aug-R6 | 40.55 | 41.5 |  41.0
E2E-Aug-R456 | 40.7 | 41.9 |  41.3
Table 2: Evaluation on GICoref. Results are in LEA.  | Binary-Pronouns | Neopronouns
---|---|---
E2E | 36.6 | 24.3
E2E-Aug-R4 | 40.7 | 37.5
Table 3: Performance in LEA recall on binary-pronouns (male/female) and
neopronouns clusters.  Figure 3: Performance in accuracy on the ablations of
MAP. Error bar shows 95% significance intervals.

#### Results on GICoref

Results on GICoref are shown Table 2. Few documents (0.3%) in Ontonotes
contained neopronouns. Therefore, E2E struggled with resolving pronouns
refering to LGBT individuals. Zhao et al. (2018) had proposed to apply gender-
swapping and entity anonymization to mitigate bias towards binary genders.
However, their approach does not handle neopronouns and performs poorly
compared to our models. In contrast, E2E-Aug improved E2E from a range of 4%
to 6% in F1 with various data augmentation rules. When all the rules were
applied, the performance was not superior to using only R4.

We further investigated the performance improvement of E2E-Aug-R4 on clusters
containing binary pronouns and neopronouns. As shown in Table 3, E2E-Aug-R4
yielded a 4% increase in recall among binary-gender pronouns and 12% among
neopronouns as compared with E2E. This reduced the performance gap between
binary-gender pronouns and neopronouns from 12% to 3%. Our results show that
R4 is highly effective, despite its simplicity.

#### Results on MAP

The core of MAP is constructed through different ablation mechanisms Cao and
Daumé III (2020). Each ablation is a method for hiding various aspects of
gender and then investigating the performance change of a model. Performance
was evaluated based on the accuracy of pronoun resolution over the four label
classes: person A, B, both, or neither. We considered four ablation mechanisms
as described in the Appendix. With these four possible ablations, each
document was ablated a total nine times with each possible combination of
ablations, producing a separate document.

We compared E2E with E2E-R4 and showed the results in Figure 3. E2E-R4 was
better than or competitive with E2E in all the ablation scenarios. E2E-R4
especially outperformed E2E on the original set and the +Pro. set, where the
performance was improved by 30%.

##  6 Conclusion

With policy decisions increasingly informed by computational analysis, it is
imperative that methods used in these analyses be robust and accurate
especially for marginalized groups. Our contributions improved coreference
resolution for LGBT individuals, a historically underrepresented and
marginalized population at high risk for suicide; they may improve the
identification of LGBT individuals in NVDRS and hence inform better policy
aimed to reduce LGBT deaths. More generally, we show how to use augmentation
rules to adapt NLP models to real-world application domains where it is not
feasible to obtain annotated data from crowdworkers. Finally, we introduced a
novel dataset, VDN, which provide a challenging and consequential corpus for
coreference resolution models. Our studies demonstrate the challenges of
applying NLP techniques to real-world data involving diverse individuals
(including LGBT individuals and their families) and suggest ways to make these
methods more accurate and robust—thus contributing to algorithmic equity.

## Discussion of Ethics

Our research was exempted from human subjects review by the UCLA IRB. We
applied for and were given access to the CDC’s National Violent Death
Reporting-System’s Restricted Access Database. As the data contain private
information, we strictly follow their guidelines in our use of the dataset.

Despite our goal to improve gender inclusion in the coreference resolution
system, we admit that our augmentation rules and data analyses may not fully
address the diversities of sexual orientation in the population. Although our
approach improves the performance of coreference systems, the final system is
still not perfect and may exhibit some bias in its predictions.

## Acknowledgements

We thank all anonymous reviewers for their valuable feedback. We want to thank
our three annotators Mika Baumgardner, Vivian Nguyen, and Mikaela Gareeb for
their contributions to our paper. It is thanks to the amount of time they
spent on annotations that we were able to produce this work. Our work for this
study was partially funded by NIH( MH115344, MD006923). JGF was supported by
an Infosys Membership in the School of Social Science at the Institute for
Advanced Study.

## References

  * Babaeianjelodar et al. (2020) Marzieh Babaeianjelodar, Stephen Lorenz, Josh Gordon, Jeanna Matthews, and Evan Freitag. 2020.  Quantifying gender bias in different corpora.  In _Companion Proceedings of the Web Conference 2020_ , WWW ’20, page 752–759, New York, NY, USA. Association for Computing Machinery.
  * Cao and Daumé III (2020) Yang Trista Cao and Hal Daumé III. 2020.  Toward gender-inclusive coreference resolution.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4568–4595.
  * Carnaz et al. (2019) Gonçalo Carnaz, Paulo Quaresma, Vitor Beires Nogueira, Mário Antunes, and Nuno NM Fonseca Ferreira. 2019.  A review on relations extraction in police reports.  In _World Conference on Information Systems and Technologies_ , pages 494–503. Springer.
  * Clark et al. (2020) K. A. Clark, S. D. Cochran, A. J. Maiolatesi, and J. E. Pachankis. 2020.  Prevalence of Bullying Among Youth Classified as LGBTQ Who Died by Suicide as Reported in the National Violent Death Reporting System, 2003-2017.  _JAMA Pediatr_.
  * Gardner et al. (2017) Matt Gardner, Joel Grus, Mark Neumann, Oyvind Tafjord, Pradeep Dasigi, Nelson F. Liu, Matthew Peters, Michael Schmitz, and Luke S. Zettlemoyer. 2017\.  Allennlp: A deep semantic natural language processing platform.
  * Hovy et al. (2006) Eduard Hovy, Mitchell Marcus, Martha Palmer, Lance Ramshaw, and Ralph Weischedel. 2006.  OntoNotes: The 90% solution.  In _Proceedings of the Human Language Technology Conference of the NAACL, Companion Volume: Short Papers_ , pages 57–60.
  * Lee et al. (2019) Jinhyuk Lee, Wonjin Yoon, Sungdong Kim, Donghyeon Kim, Sunkyu Kim, Chan Ho So, and Jaewoo Kang. 2019.  Biobert: a pre-trained biomedical language representation model for biomedical text mining.  _Bioinformatics_.
  * Lee et al. (2017) Kenton Lee, Luheng He, Mike Lewis, and Luke Zettlemoyer. 2017.  End-to-end neural coreference resolution.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 188–197.
  * Lee et al. (2018) Kenton Lee, Luheng He, and Luke Zettlemoyer. 2018.  Higher-order coreference resolution with coarse-to-fine inference.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 687–692.
  * Lira et al. (2019) Marlene C. Lira, Ziming Xuan, Sharon M. Coleman, Monica H. Swahn, Timothy C. Heeren, and Timothy S. Naimi. 2019.  Alcohol policies and alcohol involvement in intimate partner homicide in the u.s. _American Journal of Preventive Medicine_ , 57(2):172 – 179.
  * Moosavi and Strube (2016) Nafise Sadat Moosavi and Michael Strube. 2016.  Which coreference evaluation metric do you trust? a proposal for a link-based entity aware metric.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 632–642.
  * Ng and Cardie (2002) Vincent Ng and Claire Cardie. 2002.  Improving machine learning approaches to coreference resolution.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 104–111.
  * Ratner et al. (2017) Alexander Ratner, Stephen H Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. 2017.  Snorkel: Rapid training data creation with weak supervision.  In _Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases_ , volume 11, page 269. NIH Public Access.
  * Ream (2020) Geoffrey L. Ream. 2020.  An investigation of the lgbtq+ youth suicide disparity using national violent death reporting system narrative data.  _Journal of Adolescent Health_ , 66(4):470 – 477.
  * Rudinger et al. (2018) Rachel Rudinger, Jason Naradowsky, Brian Leonard, and Benjamin Van Durme. 2018.  Gender bias in coreference resolution.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 8–14.
  * Soon et al. (2001) Wee Meng Soon, Hwee Tou Ng, and Daniel Chung Yong Lim. 2001.  A machine learning approach to coreference resolution of noun phrases.  _Computational Linguistics_ , 27(4):521–544.
  * Webster et al. (2018) Kellie Webster, Marta Recasens, Vera Axelrod, and Jason Baldridge. 2018.  Mind the GAP: A balanced corpus of gendered ambiguous pronouns.  _Transactions of the Association for Computational Linguistics_ , 6:605–617.
  * Zhao et al. (2019) Jieyu Zhao, Tianlu Wang, Mark Yatskar, Ryan Cotterell, Vicente Ordonez, and Kai-Wei Chang. 2019.  Gender bias in contextualized word embeddings.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 629–634.
  * Zhao et al. (2018) Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. 2018\.  Gender bias in coreference resolution: Evaluation and debiasing methods.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 15–20.

##  Appendix A Example Case for VDN with Augmenting Rules

An example snippet of a case would be as follows:

… recently primary_victim’s boyfriend $\rightarrow$ girlfriend caught the
primary_victim cheating. primary_victim’s boyfriend $\rightarrow$ partner
states that he $\rightarrow$ she and primary_victim had a fight which got
violent . primary_victim is a 50 year old black male $\rightarrow$ female. …

We see rule 1, rule 2, and rule 3 correlate to yellow, green, and red
highlights. We applied each rule to the entire narrative.

##  Appendix B MAP ablations

The core of MAP is constructed through different ablation mechanisms Cao and
Daumé III (2020). Each ablation is a method to hiding various aspects of
gender and investigate the performance change of a model.

  1. 1.

Replace third person pronouns with gender neutral variants (+Pro)

  2. 2.

Truncate the first name of each person in the document (+Name)

  3. 3.

Replace gendered nouns with the gender-neutral variant (+Sem)

  4. 4.

Remove terms of address (i.e. Mr., Mrs, etc.) (+Addr)

In Figure 3, the ablations are applied individually and together, with zero
containing all ablations. We see this yield 9 permutations, with the only
ablation not being applied with others being +pro (except for zero).