# Neural-network quantum state tomography

Dominik Koutný  Department of Optics, Palacky University, 17. listopadu 12,
77146 Olomouc, Czech Republic  Libor Motka  Department of Optics, Palacky
University, 17. listopadu 12, 77146 Olomouc, Czech Republic  Zdeněk Hradil
Department of Optics, Palacky University, 17. listopadu 12, 77146 Olomouc,
Czech Republic  Jaroslav Řeháček  Department of Optics, Palacky University,
17. listopadu 12, 77146 Olomouc, Czech Republic  L. L. Sánchez-Soto
Departamento de Óptica, Facultad de Física, Universidad Complutense, 28040
Madrid, Spain  Max-Planck-Institut für die Physik des Lichts, 91058 Erlangen,
Germany

###### Abstract

We revisit the application of neural networks techniques to quantum state
tomography. We confirm that the positivity constraint can be successfully
implemented with trained networks that convert outputs from standard feed-
forward neural networks to valid descriptions of quantum states. Any standard
neural-network architecture can be adapted with our method. Our results open
possibilities to use state-of-the-art deep-learning methods for quantum state
reconstruction under various types of noise.

##  I Introduction

Modern quantum technologies exploit distinctive features of quantum systems to
achieve performances unattainable by classical strategies. This potential
advantage hinges on the capability to create, manipulate, and measure quantum
states. Any experimental procedure in this area requires a reliable
certification of these steps: this is precisely the province of quantum state
tomography (QST) [1].

The goal of QST is to estimate the unknown quantum state through measurements
performed on a finite set of identical copies of the system. If the state is
described by the density matrix $\varrho$, living in a $d$-dimensional Hilbert
space, $O(d/\varepsilon)$ copies are required to obtain an estimate of
$\varrho$ with an error (understood as total variation distance) less than
$\varepsilon$ [2]. This clearly illustrates the resource requirements of QST
for large-scale systems.

In a broad sense, QST is an inverse problem [3, 4, 5]. As such, the linear
inversion [6] is probably the most intuitive approach to the topic. Yet it has
some cons too: it might report a nonphysical state and the mean squared error
bound of the estimate cannot be determined analytically. To bypass these
drawbacks a variety of useful QST methods, such as Bayesian tomography [7, 8],
compressed sensing [9, 10], or matrix-product states [11, 12], are at hand,
although the maximum-likelihood estimation (MLE) is still the most common
approach [13, 14].

From a modern perspective, QST is fundamentally a data processing problem,
trying to extract information from as few noisy measurements as possible.
Therefore, the estimation algorithms used in QST can be easily translated into
tasks in machine learning (ML) [15, 16, 17]. Actually, neural networks (NNs)
have been used to address data-driven problems: examples in quantum
information include identifying phase transitions [18], detecting nonclassical
features [19, 20, 21], quantum error correction [22, 23, 24, 25], calibrating
quantum devices [26, 27], speeding up quantum optimal control [28], and
designing quantum experiments [29, 30, 31], to cite only but a few.

Recently, ML has been applied to QST with very promising results [32, 33, 34,
35, 36, 37, 38, 39, 40]. In particular, generative models [41, 42], usually
restricted Boltzmann machines, have been used to treat the measurement
outcomes on a quantum state [43]. These are NNs containing two layers, visible
and hidden, with all-to-all connections between the neurons in different
layers and none inside each layer. This technique, although powerful, suffers
from difficulties with sampling and a lack of straightforward training for
larger models.

The use of feed-forward architectures, including recurrent NNs, has been
recently advocated [44, 45] because these architectures are easier to train
without any need for sampling steps, using gradient-based optimization with
backpropagation. However, generative tasks in ML often use variational
autoencoders [46] and generative adversarial NNs [47]. These are now being
actively explored for learning quantum states [48, 49, 50, 51].

Our motivation in this paper is to address the benefits of NN-based
reconstruction over standard techniques. To fairly benchmark the performance
we pick three representative estimators, namely linear inversion, its
positivized version, and MLE, and compare them with a typical NN estimator,
obtained with a feed-forward architecture. As measurement, we choose the so-
called square root measurement, which was introduced as a “pretty good
measurement” [80] for distinguishing possibly nonorthogonal states. Using the
Hilbert-Schmidt distance between the true and the reported states as our main
indicator, our results suggest that NNs predict unknown quantum states about
three orders of magnitude faster compared to linear and MLE estimates.
Interestingly, the average errors are similar for all the estimators
considered in all dimensions. This confirms the power of deep-learning-based
tools for the quantum realm.

This paper is organized as follows. In Sec. II, we briefly discuss the basic
tools of QST we need for our purposes. In Sec. III we describe the details of
our NN architecture and training methods. Then, we present the performance of
the different estimators in Sec. IV, while our conclusions are summarized in
Sec. V.

##  II Background

We first set the stage for our model. We shall be considering a
$d$-dimensional quantum system, described by a $d\times d$ density matrix
$\varrho$, which requires $n\equiv d^{2}-1$ independent real numbers for its
specification.

The goal of QST is to estimate $\varrho$ from measurements performed on
identically prepared copies of the system. These measurements are, in general,
represented by positive operator-valued measures (POVMs) [52]: they are a set
of positive Hermitian operators $\\{\Pi_{\ell}\\}$, with the properties

$\Pi_{\ell}\geq
0\,,\qquad\Pi_{\ell}^{\dagger}=\Pi_{\ell}\,,\qquad\sum_{\ell}\Pi_{\ell}=\openone\,.$
(1)

Each POVM element represents a single output of the measuring apparatus. We
take every measurement as yielding $m$ distinct outcomes (which we assume to
be discrete). According to Born’s rule, the probability of detecting the
$\ell$th output is given by

$p_{\ell}=\mathop{\mathrm{Tr}}\nolimits(\varrho\Pi_{\ell})\,.$ (2)

To invert this equation, it is convenient to map both $\varrho$ and
$\\{\Pi_{\ell}\\}$ into a suitable vector form. To this end, we use a
traceless Hermitian operator basis $\\{\Gamma_{k}\\}$ ($k=0,\ldots,n$) and
$\Gamma_{0}=\openone$, satisfying
$\mathop{\mathrm{Tr}}\nolimits(\Gamma_{j})=0$ and
$\mathop{\mathrm{Tr}}\nolimits(\Gamma_{j}\Gamma_{k})=\delta_{jk}$. In this
way, we get the parametrization

$\varrho=r_{0}\,\Gamma_{0}+\sum_{k=1}^{n}r_{k}\,\Gamma_{k}\,\qquad\qquad\Pi_{\ell}=w_{\ell}+\sum_{k=1}^{n}\mathsf{C}_{\ell
k}\;\Gamma_{k}\,.$ (3)

Although the condition $\mathop{\mathrm{Tr}}\nolimits\varrho=1$ sets
$r_{0}=1/d$, we leave $r_{0}$ as a parameter to keep the same number of
unknowns as for the approach using Cholesky decomposition to be described
later. The important point is that the state is characterized by the Bloch
vector [53, 54, 55, 56]
$r_{k}=\mathop{\mathrm{Tr}}\nolimits(\varrho\Gamma_{k})$, whereas
$\mathsf{C}_{\ell k}=\mathop{\mathrm{Tr}}\nolimits(\Pi_{\ell}\Gamma_{k})$ is a
$m\times n$ real matrix describing the explicit relation between the
theoretical probabilities $\mathbf{p}$ and the state parameters $\mathbf{r}$.

In consequence, the inverse problem we have to solve turns out to be the
linear system

$\mathbf{p}=\mathsf{C}\,\mathbf{r}\,,$ (4)

where we have omitted an unessential constant term that can be incorporated
into the following discussion in a straightforward way.

In presence of noise and with a finite number of copies the collected data, we
will denote by $\mathbf{f}$, deviates from the expected values $\mathbf{p}$.
The ultimate goal of QST is to infer the signal parameters $\mathbf{r}$ from
the measured noisy data $\mathbf{f}$. A naive solution is to use the estimator

$\widehat{\mathbf{r}}_{\textsc{LI}}=\mathsf{C}^{-}\;\mathbf{f}\,,$ (5)

where the $\mathsf{C}^{-}$ stands for pseudoinverse [57, 58, 59] and the
subscript LI reminds us that this is a linear inversion approach.

This $\widehat{\mathbf{r}}_{\mathrm{LI}}$ is also known as the ordinary least
squares estimator [60]. As heralded before, the resulting
$\widehat{\mathbf{r}}_{\mathrm{LI}}$ is no longer guaranteed to represent a
positive semidefinite operator. One might ensure positivity by setting the
negative eigenvalues to zero, which has been called the “quick and dirty”
approach [61], although this performs poorly.

Another alternative is to use instead the generalized least-square estimator
[62], defined as
$\widehat{r}_{\mathrm{GLS}}=(\mathsf{X}^{-1}\mathsf{C})^{+}\mathsf{X}^{-1})\mathbf{f}$,
where $\mathsf{X}$ is such that $\mathsf{C}\mathsf{C}^{\dagger}$ is the data
covariance matrix. Under the Gauss-Markov assumptions [63] it is the best
linear unbiased estimator (usually known as blue) [64]. However, for small and
medium sized data sets, a reliable estimation of the data covariances is not
possible, and then $\widehat{\mathbf{r}}_{\mathrm{LI}}$ turns out to be a
handy estimator.

To circumvent these obstructions we might follow yet another route,
introducing instead a semidefinite program that solves (4), together with the
positivity constraint. The resulting estimator, denoted by
$\widehat{\mathbf{r}}_{\mathrm{SDP}}$, is thus a solution of

$\begin{array}[]{ll}\mathrm{minimize}&||\mathbf{f}-\mathsf{C}\mathbf{r}||\\\
&\\\ \mathrm{subject\ to}&\varrho\geq
0\quad\mathrm{and}\quad\mathop{\mathrm{Tr}}\nolimits\varrho=1.\end{array}$ (6)

Finally, to make our analysis complete and consider a nonlinear estimator, we
also incorporate the MLE, which guarantees positivity of the resulting quantum
state. Although there is a vast literature on the subject, the MLE estimate
$\widehat{\varrho}_{\mathrm{MLE}}$ can be seen as the fixed point of the
iterative map [65]

$\varrho_{k+1}\leftarrow{\lambda_{k}}R\varrho_{k}R,$ (7)

with

$R=\sum_{j}\frac{f_{j}}{p_{j}}\Pi_{j}$ (8)

and $\lambda_{k}$ is a normalization constant. The resulting Bloch-vector
$\widehat{\mathbf{r}}_{\mathrm{MLE}}$ estimate is asymptotically unbiased as
$f_{j}\rightarrow p_{j}$. Usually, a few thousands of iterations are needed to
observe the stationary point of the map (7).

From a numerical point of view, an efficient way to deal with the positivity
constraint is to directly decompose the density operator using the famous
Cholesky factorization [66]

$\varrho=\frac{\mathsf{A}\mathsf{A}^{\dagger}}{\mathop{\mathrm{Tr}}\nolimits(\mathsf{A}\mathsf{A}^{\dagger})}\,,$
(9)

where $\mathsf{A}$ is a complex lower triangular matrix and
$\mathsf{A}^{\dagger}$ its Hermitian conjugate. Born’s rule then turns to a
set of nonlinear equations, which are rather complicated to solve. For this
purpose, we adopt ML techniques.

##  III Neural-network estimators

Our goal is to built a NN that links the input observed frequencies
$\mathbf{f}$ to either an output true Bloch vector
$\widehat{\mathbf{r}}_{\mathrm{NN}}$ or a Cholesky matrix
$\mathsf{A}_{\mathrm{NN}}$. The sampled frequencies $\mathbf{f}$ serve as
input to the NN, which transforms them into an output Bloch vector or a
Cholesky matrix via a series of linear transformations, each followed by
evaluation of some nonlinear function. The structure of such transformations
is represented by neurons ordered into deep layers. More precisely, the values
$\mathbf{z}^{(k)}$ of the neurons in $k$th layer are

$\begin{array}[]{ll}\mathbf{z}^{(k)}&={f\left(\mathbf{y}^{(k)}\right)},\\\
&\\\ \mathbf{y}^{(k)}&=\mathsf{W}^{(k-1\rightarrow
k)}\mathbf{z}^{(k-1)}+\mathbf{b}^{(k-1)},\end{array}$ (10)

where $\mathsf{W}$ is a matrix of weights connecting neighboring layers that
together with the vector of biases $\mathbf{b}$ forms a set of trainable
parameters. The nonlinear activation scalar function $f$ can be chosen
arbitrarily, depending on the problem. In our case, the rectified linear unit
function $f_{\mathrm{ReLU}}(x):=\max(0,x)$ is used in every deep layer except
at the output layer, where we take $f(x)=\tanh(x)$. The hyperbolic tangent
function maps real numbers into the $(-1,1)$ interval which coincides with
restriction on elements of both Bloch vector and Cholesky matrix.
Symbolically, we can express the Bloch vector (and similarly the elements of
the Cholesky matrix) as

$\mathbf{r}_{\mathrm{NN}}=f_{\tanh}\circ\widetilde{\mathsf{W}}^{(n-1\rightarrow\mathrm{out})}\circ\cdots\circ
f_{\mathrm{ReLU}}\circ\widetilde{\mathsf{W}}^{(\mathrm{in}\rightarrow
1)}\circ\mathbf{f},$ (11)

where $\widetilde{\mathsf{W}}$ is a shortcut for
$\\{\mathsf{W},\mathbf{b}\\}$.

Figure 1: Sketch of a NN for estimating the Bloch parameters or the elements
of the Cholesky matrix from the sampled statistics $\mathbf{f}$. The filled
blue ovals represent neurons in deep layers, representing about $2\times
10^{5}$ trainable parameters. The output layer has a hyperbolic tangent as an
activation function since it has the same bounds as the Bloch parameters and
theelements of the Cholesky matrix. In the hidden layers, the rectified linear
unit is used as an activation function. The structure of the NN is the same,
independently of the dimension or specific parametric representation of
quantum states.

The NN learns by minimizing the loss function. We chose to work with mean
squared error, which takes the form

$\mathcal{L}=\left\langle\sum_{k=0}^{n}\left|r_{k}-z_{k}^{\mathrm{out}}(\widetilde{\mathsf{W}},f)\right|^{2}\right\rangle\,,$
(12)

where $\langle\cdot\rangle$ denotes the average value in the state $\varrho$.
Optimization in the NN is done by backpropagating the error. This is arguably
the workhorse of most ML algorithms and definitely the standard approach in
most situations, which is working with batches of data. The term and its
general use in NNs was coined in [67] and a modern overview is given in
textbook [68].

We minimize the value of the loss function $\mathcal{L}$ over all components
of a given dataset to update weights and biases $\widetilde{\mathsf{W}}$,
using a stochastic gradient-based optimization, which is of core practical
importance in many fields [69]. A widely accepted algorithm is Adam [70],
which is straightforward to implement, computationally efficient, and has
little memory requirements. We use an improved version that incorporates
Nesterov-accelerated adaptive momentum estimation (Nadam) [71], since recent
results indicate that it has better performance [72]. At the step $t$, the
Nadam procedure updates parameters in the form

$\displaystyle{\widetilde{\mathbf{W}}_{t}\leftarrow\widetilde{\mathbf{W}}_{t-1}-\eta\frac{\bar{\mathbf{m}}_{t}}{\sqrt{\hat{\mathbf{n}}_{t}}+\epsilon}\,,}$
(13)

with

$\displaystyle\mathbf{g}_{t}$ $\displaystyle\leftarrow$
$\displaystyle\nabla_{\widetilde{\mathbf{W}}_{t-1}}\mathcal{L}\left(\widetilde{\mathbf{W}}_{t-1}\right),$
$\displaystyle\mathbf{\hat{g}}$ $\displaystyle\leftarrow$
$\displaystyle\frac{\mathbf{g}_{t}}{1-\prod_{j=1}^{t}\mu_{j}},$
$\displaystyle\mathbf{m}_{t}$ $\displaystyle\leftarrow$
$\displaystyle\mu\mathbf{m}_{t-1}+(1-\mu)\mathbf{g}_{t},$
$\displaystyle\mathbf{\hat{m}}_{t}$ $\displaystyle\leftarrow$
$\displaystyle\frac{\mathbf{m}_{t}}{1-\prod_{j=1}^{t+1}\mu_{j}},$ (14)
$\displaystyle\mathbf{n}_{t}$ $\displaystyle\leftarrow$
$\displaystyle\nu\mathbf{n}_{t-1}+(1-\nu)\mathbf{g}_{t}^{2},$
$\displaystyle\mathbf{\hat{n}}_{t}$ $\displaystyle\leftarrow$
$\displaystyle\frac{\mathbf{n}_{t}}{1-\nu^{t}},$
$\displaystyle\mathbf{\bar{m}}_{t}$ $\displaystyle\leftarrow$
$\displaystyle(1-\mu_{t})\mathbf{\hat{g}}_{t}+\mu_{t+1}\mathbf{\hat{m}}_{t}.$

Here, $\eta$ represents the learning rate, $\mu$ the exponential decay rate
for the first moment estimates $\mathbf{\hat{m}}$, $\nu$ the exponential decay
rate for the weighted norm $\mathbf{g}_{t}^{2}$, and $\epsilon$ is a parameter
that ensures the numerical stability of the Nadam optimization procedure. We
set the numerical values $\\{\eta,\mu,\nu,\epsilon\\}$ to
$\\{0.001,0.9,0.999,10^{-7}\\}$.

All the above is implemented in Keras [73] and Tensorflow [74] libraries for
Python. The corresponding code can be found in Ref. [75]. In every epoch, the
training dataset is divided into $100$ batches. The number of epochs needed to
find a global minimum of the loss function varies across different deep NNs.
In general, the training stopped after $400-2000$ epochs, depending on the
dimension in which we estimate quantum states. We defined an early stopping
after not finding the better minimum of the loss function in the $200$
consecutive epochs. We stress that both $\widehat{\mathbf{r}}_{\mathrm{NN}}$
and $\widehat{\mathbf{r}}_{\mathrm{LI}}$ estimates and the ensuing quantum
states are Hermitian matrices but do not incorporate the positivity
constraint, in contradiction with $\widehat{\mathbf{r}}_{\mathrm{SDP}}$ and
$\widehat{\mathbf{r}}_{\mathrm{MLE}}$.

Figure 2: Average Hilbert-Schmidt distance for different estimating strategies
on the number of trials with which we sampled the true probability
distribution $\mathbf{p}$ in dimension 3 (upper left panel), 5 (upper rigt
panel), 7 (lower left panel), and 9 (upper right panel). The insets indicate
the corresponding estimators. The average errors for both NN in the
undersampled regime are of the same order for SDP and MLE in all dimensions.
When using highly sampled statistics, number of trials $>10^{5}$, MLE starts
to outperfonm both NN approaches. Confidence intervals of 80% are depicted in
respective colors. Figure 3: Average time per state estimation for different
tomographical methods, as indicated in the inset. The NN approach is about
three orders faster than SDP and about four order faster than MLE.

##  IV Results

Our deep NN is built as follows: The input layer is fed by observed
frequencies $\mathbf{f}$ for different quantum states, followed by eight
layers consisting of $(200,180^{\otimes 2},160^{\otimes 4},100)$ neurons with
the ReLU activation function. The output layer, with a hyperbolic tangent
activation function, serves as an estimate of Bloch vector or the elements of
Cholesky matrix.

The structure of the NN was adjusted heuristically, after having tried
multiple settings with differing number of free parameters and deep layers. In
terms of the distance between estimated and true quantum states, we got on
average the same accuracy for a NN with two layers. However, it was observed
that NNs are more likely to return parameters corresponding to positive
semidefinite matrices, compared to, e.g., the LI method.

The NN sketch is presented in Fig. 1. We trained in total eight NNs, each with
the same structure, for the inference of quantum states in dimensions
$d=3,5,7,$ and $9$. As our target states, we use random density matrices
$\varrho$ distributed according to [76]

${\varrho=\frac{\mathsf{X}\mathsf{X}^{\dagger}}{\mathop{\mathrm{Tr}}\nolimits(\mathsf{X}\mathsf{X}^{\dagger})},}$
(15)

with $\mathsf{X}$ pertaining to the Ginibre ensemble [77], that is, with real
and imaginary parts of each matrix entry being independent normal random
variables. These are implemented in Python using QuTiP [78].

As heralded in the Introduction, as our measurement scheme, we choose the
square root measurement, defined by the rank-one POVM

${\Pi_{\ell}=G^{-1/2}\;\ket{\phi_{\ell}}\bra{\phi_{\ell}}\,G^{-1/2}\,,\qquad
G=\sum_{\ell}\ket{\phi_{\ell}}\bra{\phi_{\ell}}\,,}$ (16)

where $|\phi_{\ell}\rangle$ are randomly generated Haar-distributed pure
states [79] $(\ell=0,\ldots,n)$. This POVM is known to be optimal, in the
sense that the measurement vectors are the closest in the squared norm to the
given states [81, 82].

Figure 4: Quality of estimators based on linear inversion and NN. In all the
panels, red diamonds, blue squares, green triangles, and yellow circles
represent the results for estimators in dimensions 3, 5, 7, and 9,
respectively. The upper plots show the dependence of the most negative
eigenvalue on the number of trials for those dimensions and for the LI
estimator (left) and the Bloch NN estimator (right). The bottom panels depict
the percentage of positive semidefinite states amongst all the reconstructed
states with LI (left) and Bloch NN (right). The results are obtained from
datasets containing $10^{4}$ statistics in each dimension.

For each dimension, the training (validation) dataset contains $8\times
10^{5}\,(2\times 10^{5})$ points. One quarter of the data in the training
dataset are probabilities
$p_{\ell}=\mathop{\mathrm{Tr}}\nolimits(\varrho\Pi_{\ell})$ sampled with a
random number of trials, ranging from $d^{2}$ up to $10^{5}$, the rest are
theoretical probabilities. Each input vector, containing either theoretical or
sampled statistics, corresponds to different randomly generated quantum states
(15), whereas the measurement (16) is fixed for all states in each dimension.

Ideally, all data points in the training dataset should consist of only
theoretical probabilities so that the NN can extract the appropriate
transformation. However, in the undersampled regime, it turns out to be
beneficial for the NN to see examples of the sampled statistics. In this case,
with a training dataset containing only theoretical probabilities, the NN
would lose the ability to predict positive matrices, while with only sampled
probabilities in the training dataset, the NN would have a hard time in
correctly learning the mapping from probabilities to the Bloch vector or the
Cholesky matrix.

The output layer consists of true values of the Bloch vector or elements of
the Cholesky matrix. All NNs are trained for at most 2000 epochs, which takes
about 12 hours for every NN when estimating density matrices in dimension 9.
After the training procedure, we compared estimates of quantum states based on
NNs with standard methods, namely LI, SPD, and MLE.

Results are shown in Fig. 2. For each dimension $d$, we generated $10^{3}$
random density matrices and, using the same measurement scheme as for the
training, we obtained a set of $10^{3}$ probability distributions, often
called a test set. After getting the test set, we sampled each probability
distribution with a number of trials depicted on the horizontal axis. Then, we
used trained NNs, LI, MLE and the SDP to reconstruct density matrices from the
sampled statistics. We plot the average Hilbert-Schmidt distance between true
and inferred quantum states as a function of the number of trials. As we can
see, NNs outperform the $\widehat{\mathbf{r}}_{\mathrm{LI}}$ estimator and are
better or give errors in the same order of magnitude as
$\widehat{\mathbf{r}}_{\mathrm{SPD}}$.

For a fixed number of trials, the NN-based Bloch vector has a better average
error compared to the Cholesky one, but tends to report Hermitian matrices
with nonpositive least eigenvalues. Moreover, NNs work relatively well in the
undersampled regime. Interestingly, NNs show the ability to extrapolate beyond
the number of samples on which they were trained. This can be appreciated in
the lower Hilbert-Schmidt distance for $10^{6}$ trials, when only up to
$10^{5}$ trials were used to sample the true statistics.

The combination of theoretical and sampled probabilities in the training set
was balanced in such a way that the NNs work well in the undersampled regime,
but also provide accurate estimates when the number of trials is high. Of
course, when the number of trials goes to infinity; i.e, when working with
theoretical probabilities, the $\widehat{\mathbf{r}}_{\mathrm{LI}}$ and
$\widehat{\mathbf{r}}_{\mathrm{MLE}}$ estimators converge to the true state of
the system.

Figure 3 shows an analysis of the performance of different estimators. We
depict the average time per single evaluation of
$\widehat{\mathbf{r}}_{\mathrm{LI}}$, $\widehat{\mathbf{r}}_{\mathrm{SDP}}$,
$\widehat{\mathbf{r}}_{\mathrm{MLE}}$, and both NNs. For the NNs, the times
shown are only those associated with the prediction phase, not the training
(which takes a lot longer). The semidefinite program infers the quantum state
from sampling statistics at around $10^{-1}$ seconds. MLE turns out to be the
most time-consuming procedure. Compared to linear inversion and both NN
approaches, MLE predicts quantum states about $10^{4}$ slower. Akin to linear
inversion, NN predicts unknown quantum state from the data about three orders
faster compared to SPD estimates and about four orders faster compared to the
MLE estimates.

Figure 4 summarizes our performance analysis. We compare the quality of
$\widehat{\mathbf{r}}_{\mathrm{LI}}$ and $\widehat{\mathbf{r}}_{\mathrm{NN}}$
in terms of the _quantumness_ of the inferred states. We show the mean of the
largest negative eigenvalues and ratio of positive semidefinite quantum states
among the set of estimated Hermitian matrices on the measured statistics
sampled with given number of trials. Note that we have excluded results from
MLE and SDP, for those estimators always reconstruct a positive matrix.

As one can see in Fig. 4, NNs can learn the positivity constraint. For
example, in dimension 9, considering $\widehat{\mathbf{r}}_{\mathrm{LI}}$,
only $1\%$ of all Hermitian matrices are positive semidefinite, compared to
$17\%$ using NN, estimated from statistics sampled with $10^{6}$ trials. In
the undersampled regime, where the number of trials is in the order of the
number of projectors, NNs in each dimension predict the higher number of
positive quantum states compared to the $\widehat{\mathbf{r}}_{\mathrm{LI}}$
estimator.

The issue with predicting quantum states with negative eigenvalues is that it
is more prevalent for states that are singular (i.e., with vanishing
determinant), as these are the states that sit on the boundary in the
generalized Bloch representation. As such, the results in Fig. 4 depend on the
purity of the states to be reported.

##  V Concluding remarks

In summary, we have shown how NN can assist in the reconstruction of quantum
states. The NN maps the input experimental data to a valid density matrix up
to three orders of magnitude faster than the standard QST. This presents a
significant advantage for data postprocessing during tomography. The NN learns
to represent the state in a way that is well suited for the problem.

Our results confirm how some of the latest ideas from deep learning can be
quite easily adapted and applied to quantum information tasks with just a few
tweaks to incorporate the rules of quantum physics. This opens up a wealth of
possible applications, which are the object of intense investigation.

## Ackowledgments

The authors thank Miroslav Ježek for useful discussions and two anonymous
reviewers for their constructive and detailed comments. This work was
supported by the European Union’s Horizon 2020 research and innovation
programme under the QuantERA programme through the project ApresSF and from
the EU Grant 899587 (Project Stormytune), the Palacký University Grant
IGA_PrF_2021_002 and the Spanish Ministerio de Ciencia e Innovacion (Grant
PGC2018-099183-B-I00).

## References

  * Paris and Řeháček [2004] M. G. A. Paris and J. Řeháček, eds.,  _Quantum State Estimation_ , Lect. Not. Phys., Vol. 649 (Springer, Berlin, 2004).
  * O’Donnell and Wright [2016] R. O’Donnell and J. Wright, Efficient quantum tomography, in  _Proc. forty-eighth annual ACM symposium on Theory of Computing_ (Association for Computing Machinery, Cambridge, MA, USA, 2016) pp. 899–912.
  * Artiles  _et al._ [2005] L. M. Artiles, R. D. Gill, and M. I. Gut¸ă, An invitation to quantum tomography, J. Roy. Stat. Soc. B 67, 109 (2005).
  * Tarantola [2005] A. Tarantola,  _Inverse Problem Theory and Methods for Model Parameter Estimation_ (SIAM, Philadelphia, 2005) p. 348.
  * Aster  _et al._ [2013] R. Aster, B. Borchers, and C. Thurber,  _Parameter Estimation and Inverse Problems_ , 2nd ed. (Academic, Boston, 2013).
  * Qi  _et al._ [2013] B. Qi, Z. Hou, L. Li, D. Dong, G. Xiang, and G. Guo, Quantum state tomography via linear regression estimation, Sci. Rep. 3, 3496 (2013).
  * Blume-Kohout [2010] R. Blume-Kohout, Optimal, reliable estimation of quantum states, New J. Phys. 12, 043034 (2010).
  * Granade  _et al._ [2016] C. Granade, J. Combes, and D. G. Cory, Practical bayesian tomography, New J. Phys. 18, 033024 (2016).
  * Gross  _et al._ [2010] D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, Quantum state tomography via compressed sensing, Phys. Rev. Lett. 105, 150401 (2010).
  * Ahn  _et al._ [2019] D. Ahn, Y. S. Teo, H. Jeong, F. Bouchard, F. Hufnagel, E. Karimi, D. Koutný, J. Řeháček, Z. Hradil, G. Leuchs, and L. L. Sánchez-Soto, Adaptive compressive tomography with no a priori information, Phys. Rev. Lett. 122, 100404 (2019).
  * Cramer  _et al._ [2010] M. Cramer, M. B. Plenio, S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin, and Y. K. Liu, Efficient quantum state tomography, Nat. Commun. 1, 149 EP (2010).
  * Lanyon  _et al._ [2017] B. P. Lanyon, C. Maier, M. Holzäpfel, T. Baumgratz, C. Hempel, P. Jurcevic, I. Dhand, A. S. Buyskikh, A. J. Daley, M. Cramer, M. B. Plenio, R. Blatt, and C. F. Roos, Efficient tomography of a quantum many-body system, Nat. Phys. 13, 1158 (2017).
  * Hradil [1997] Z. Hradil, Quantum-state estimation, Phys. Rev. A 55, R1561 (1997).
  * James  _et al._ [2001] D. F. V. James, P. G. Kwiat, W. J. Munro, and A. G. White, Measurement of qubits, Phys. Rev. A 64, 052312 (2001).
  * Murphy [2012] K. Murphy,  _Machine Learning: A Probabilistic Perspective_ (The MIT Press, Cambridge, 2012).
  * Nielsen [2018] M. A. Nielsen, Neural networks and deep learning (2018).
  * Mehta  _et al._ [2019] P. Mehta, M. Bukov, C.-H. Wang, A. G. R. Day, C. Richardson, C. K. Fisher, and D. J. Schwab, A high-bias, low-variance introduction to machine learning for physicists, Phys. Rep. 810, 1 (2019).
  * Rem  _et al._ [2019] B. S. Rem, N. Käming, M. Tarnowski, L. Asteria, N. Fläschner, C. Becker, K. Sengstock, and C. Weitenberg, Identifying quantum phase transitions using artificial neural networks on experimental data, Nat. Phys. 15, 917 (2019).
  * Gebhart and Bohmann [2020] V. Gebhart and M. Bohmann, Neural-network approach for identifying nonclassicality from click-counting data, Phys. Rev. Research 2, 023150 (2020).
  * You  _et al._ [2020] C. You, M. A. Quiroz-Juárez, A. Lambert, N. Bhusal, C. Dong, A. Perez-Leija, A. Javaid, R. J. León-Montiel, and O. S. Magaña-Loaiza, Identification of light sources using machine learning, Appl. Phys. Rev. 7, 021404 (2020).
  * Harney  _et al._ [2020] C. Harney, S. Pirandola, A. Ferraro, and M. Paternostro, Entanglement classification via neural network quantum states, New J. Phys. 22, 045001 (2020).
  * Torlai and Melko [2017] G. Torlai and R. G. Melko, Neural decoder for topological codes, Phys. Rev. Lett. 119, 030501 (2017).
  * Baireuther  _et al._ [2018] P. Baireuther, T. E. O’Brien, B. Tarasinski, and C. W. J. Beenakker, Machine-learning-assisted correction of correlated qubit errors in a topological code, Quantum 2, 48 (2018).
  * Krastanov and Jiang [2017] S. Krastanov and L. Jiang, Deep neural network probabilistic decoder for stabilizer codes, Sci. Rep. 7, 11003 (2017).
  * Fitzek  _et al._ [2020] D. Fitzek, M. Eliasson, A. F. Kockum, and M. Granath, Deep q-learning decoder for depolarizing noise on the toric code, Phys. Rev. Research 2, 023230 (2020).
  * Flurin  _et al._ [2020] E. Flurin, L. S. Martin, S. Hacohen-Gourgy, and I. Siddiqi, Using a recurrent neural network to reconstruct quantum dynamics of a superconducting qubit from physical observations, Phys. Rev. X 10, 011006 (2020).
  * Wittler  _et al._ [2021] N. Wittler, F. Roy, K. Pack, M. Werninghaus, A. S. Roy, D. J. Egger, S. Filipp, F. K. Wilhelm, and S. Machnes, Integrated tool set for control, calibration, and characterization of quantum devices applied to superconducting qubits, Phys. Rev. Applied 15, 034080 (2021).
  * Leung  _et al._ [2017] N. Leung, M. Abdelhafez, J. Koch, and D. Schuster, Speedup for quantum optimal control from automatic differentiation based on graphics processing units, Phys. Rev. A 95, 042318 (2017).
  * Krenn  _et al._ [2016] M. Krenn, M. Malik, R. Fickler, R. Lapkiewicz, and A. Zeilinger, Automated search for new quantum experiments, Phys. Rev. Lett. 116, 090405 (2016).
  * Melnikov  _et al._ [2018] A. A. Melnikov, H. Poulsen Nautrup, M. Krenn, V. Dunjko, M. Tiersch, A. Zeilinger, and H. J. Briegel, Active learning machine learns to create new quantum experiments, Proc. Natl. Acad. Sci. USA 115, 1221 (2018).
  * O’Driscoll  _et al._ [2019] L. O’Driscoll, R. Nichols, and P. A. Knott, A hybrid machine learning algorithm for designing quantum experiments, Quantum Machine Intelligence 1, 5 (2019).
  * Torlai  _et al._ [2018] G. Torlai, G. Mazzola, J. Carrasquilla, M. Troyer, R. Melko, and G. Carleo, Neural-network quantum state tomography, Nat. Phys. 14, 447 (2018).
  * Carleo  _et al._ [2018] G. Carleo, Y. Nomura, and M. Imada, Constructing exact representations of quantum many-body systems with deep neural networks, Nat. Commun. 9, 5322 (2018).
  * Xin  _et al._ [2019] T. Xin, S. Lu, N. Cao, G. Anikeeva, D. Lu, J. Li, G. Long, and B. Zeng, Local-measurement-based quantum state tomography via neural networks, npj Quantum Inf. 5, 109 (2019).
  * Palmieri  _et al._ [2020] A. M. Palmieri, E. Kovlakov, F. Bianchi, D. Yudin, S. Straupe, J. D. Biamonte, and S. Kulik, Experimental neural network enhanced quantum tomography, npj Quantum Inf. 6, 20 (2020).
  * Melkani  _et al._ [2020] A. Melkani, C. Gneiting, and F. Nori, Eigenstate extraction with neural-network tomography, Phys. Rev. A 102, 022412 (2020).
  * Lohani  _et al._ [2020] S. Lohani, B. T. Kirby, M. Brodsky, O. Danaci, and R. T. Glasser, Machine learning assisted quantum state estimation, Mach. Learn.: Sci. Technol. 1, 035007 (2020).
  * Liu  _et al._ [2020] Y. Liu, D. Wang, S. Xue, A. Huang, X. Fu, X. Qiang, P. Xu, H.-L. Huang, M. Deng, C. Guo, X. Yang, and J. Wu, Variational quantum circuits for quantum state tomography, Phys. Rev. A 101, 052316 (2020).
  * Quek  _et al._ [2021] Y. Quek, S. Fort, and H. K. Ng, Adaptive quantum state tomography with neural networks, npj Quantum Inf. 7, 105 (2021).
  * Carrasquilla and Torlai [2021] J. Carrasquilla and G. Torlai, How to use neural networks to investigate quantum many-body physics, PRX Quantum 2, 040201 (2021).
  * Carrasquilla  _et al._ [2019] J. Carrasquilla, G. Torlai, R. G. Melko, and L. Aolita, Reconstructing quantum states with generative models, Nat. Mach. Intell. 1, 155 (2019).
  * Lloyd and Weedbrook [2018] S. Lloyd and C. Weedbrook, Quantum generative adversarial learning, Phys. Rev. Lett. 121, 040502 (2018).
  * Tiunov  _et al._ [2020] E. S. Tiunov, V. V. Tiunova (Vyborova), A. E. Ulanov, A. I. Lvovsky, and A. K. Fedorov, Experimental quantum homodyne tomography via machine learning, Optica 7, 448 (2020).
  * Cai and Liu [2018] Z. Cai and J. Liu, Approximating quantum many-body wave functions using artificial neural networks, Phys. Rev. B 97, 035116 (2018).
  * Cha  _et al._ [2021] P. Cha, P. Ginsparg, F. Wu, J. Carrasquilla, P. L. McMahon, and E.-A. Kim, Attention-based quantum tomography, Mach. Learn.: Sci. Technol. 3, 01LT01 (2021).
  * Kingma and Welling [2019] D. Kingma and M. Welling, An introduction to variational autoencoders, Found. Trends Mach. Learn. 12, 307 (2019).
  * Goodfellow  _et al._ [2014] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, Generative adversarial nets, in  _Advances in Neural Information Processing Systems_ , Vol. 3 (Curran Associates, Montreal, 2014) pp. 2672–2680.
  * Rocchetto  _et al._ [2018] A. Rocchetto, E. Grant, S. Strelchuk, G. Carleo, and S. Severini, Learning hard quantum distributions with variational autoencoders, npj Quantum Inf. 4, 28 (2018).
  * Zoufal  _et al._ [2019] C. Zoufal, A. Lucchi, and S. Woerner, Quantum generative adversarial networks for learning and loading random distributions, npj Quantum Inf. 5, 103 (2019).
  * Ahmed  _et al._ [2021a] S. Ahmed, C. Sánchez Muñoz, F. Nori, and A. F. Kockum, Quantum state tomography with conditional generative adversarial networks, Phys. Rev. Lett. 127, 140502 (2021a).
  * Ahmed  _et al._ [2021b] S. Ahmed, C. Sánchez Muñoz, F. Nori, and A. F. Kockum, Classification and reconstruction of optical quantum states with deep neural networks, Phys. Rev. Research 3, 033278 (2021b).
  * Helstrom [1976] C. W. Helstrom,  _Quantum Detection and Estimation Theory_ (Academic, New York, 1976).
  * Kimura [2003] G. Kimura, The Bloch vector for $n$-level systems, Phys. Lett. A 314, 339 (2003).
  * Bertlmann and Krammer [2008] R. A. Bertlmann and P. Krammer, Bloch vectors for qudits, J. Phys. A: Math. Theo. 41, 235303 (2008).
  * Mendaš [2008] I. P. Mendaš, Classification and time evolution of density matrices for a $n$-state system, J. Math. Phys. 49, 092102 (2008).
  * Brüning  _et al._ [2012] E. Brüning, H. Mäkelä, A. Messina, and F. Petruccione, Parametrizations of density matrices, J. Mod. Opt. 59, 1 (2012).
  * Penrose [1955] R. Penrose, A generalized inverse for matrices, Proc. Cambridge Phil. Soc. 51, 406 (1955).
  * Ben-Israel and Greville [1977] A. Ben-Israel and T. N. E. Greville,  _Generalized Inverses: Theory and Applications_ (Wiley, New York, 1977).
  * Campbell and Meyer [1991] S. L. Campbell and C. D. J. Meyer,  _Generalized Inverses of Linear Transformations_ (Dover, New York, 1991).
  * Lawson and Hanson [1974] C. Lawson and R. Hanson,  _Solving Least Squares Problems_ (Prentice-Hall, Englewood Cliffs, 1974).
  * Kaznady and James [2009] M. S. Kaznady and D. F. V. James, Numerical strategies for quantum tomography: Alternatives to full optimization, Physical Review A 79, 022109 (2009).
  * Opatrný  _et al._ [1997] T. Opatrný, D. G. Welsch, and W. Vogel, Least-squares inversion for density-matrix reconstruction, Phys. Rev. A 56, 1788 (1997).
  * Hallin [2006] M. Hallin, Gauss–Markov theorem in statistics, in  _Encyclopedia of Environmetrics_ (John Wiley, 2006).
  * Kay [1993] S. M. Kay,  _Fundamentals of Statistical Signal Processing_ , Vol. 1 (Prentice Hall, Upper Saddle River, 1993).
  * Řeháček  _et al._ [2007] J. Řeháček, Z. Hradil, E. Knill, and A. I. Lvovsky, Diluted maximum-likelihood algorithm for quantum tomography, Phys. Rev. A 75, 042108 (2007).
  * Watkins [1991] D. Watkins,  _Fundamentals of Matrix Computations_ (Wiley, New York, 1991).
  * Rumelhart  _et al._ [1986] D. E. Rumelhart, G. E. Hinton, and R. J. Williams, Learning representations by back-propagating errors, Nature 323, 533 (1986).
  * Goodfellow  _et al._ [2016] I. Goodfellow, Y. Bengio, and A. Courville,  _Deep Learning_ (MIT Press, Cambridge, MA, 2016).
  * Ruder [2016] S. Ruder, An overview of gradient descent optimization algorithms, arXiv:1609.04747 (2016).
  * Kingma and Ba [2014] D. P. Kingma and J. Ba, Adam: A method for stochastic optimization (2014).
  * Dozat [2015] T. Dozat, Incorporating Nesterov momentum into Adam, (2015).
  * Dogo  _et al._ [2018] E. M. Dogo, O. J. Afolabi, N. I. Nwulu, B. Twala, and C. O. Aigbavboa, A comparative analysis of gradient descent-based optimization algorithms on convolutional neural networks, in  _2018 International Conference on Computational Techniques, Electronics and Mechanical Systems (CTEMS)_ (2018) pp. 92–99.
  * Chollet [2015] F. Chollet, Keras (2015).
  * _et al_ [2015] M. A.  _et al_ , TensorFlow: Large-scale machine learning on heterogeneous systems (2015), software available from tensorflow.org.
  * [75] https://github.com/dkoutny/ReconstructionOfQuantumStatesViaNNs.
  * Osipov  _et al._ [2010] V. . A. Osipov, H. Sommers, and K. Życzkowski, Random bures mixed states and the distribution of their purity, J. Phys. A: Math. Theo. 43, 055302 (2010).
  * Ginibre [1965] J. Ginibre, Statistical ensembles of complex, quaternion, and real matrices, J. Math. Phys. 6, 440 (1965).
  * Johansson  _et al._ [2012] J. R. Johansson, P. D. Nation, and F. Nori, QuTiP: An open-source Python framework for the dynamics of open quantum systems, Comp. Phys. Commun. 183, 1760 (2012).
  * Życzkowski  _et al._ [2011] K. Życzkowski, K. A. Penson, I. Nechita, and B. Collins, Generating random density matrices, J. Math. Phys. 52, 062201 (2011).
  * Hausladen and Wootters [1994] P. Hausladen and W. K. Wootters, A ‘pretty good’ measurement for distinguishing quantum states, J. Mod. Opt. 41, 2385 (1994).
  * Eldar and Forney [2001] Y. C. Eldar and G. D. Forney, On quantum detection and the square-root measurement, IEEE Trans. Inform. Theory 47, 858 (2001).
  * Dalla Pozza and Pierobon [2015] N. Dalla Pozza and G. Pierobon, Optimality of square-root measurements in quantum state discrimination, Phys. Rev. A 91, 042334 (2015).


# Improving Sign Recognition with Phonology

Lee Kezar
University of Southern California
<EMAIL_ADDRESS>
&Jesse Thomason
University of Southern California
<EMAIL_ADDRESS>
Zed Sevcikova Sehyr
San Diego State University
<EMAIL_ADDRESS>

###### Abstract

We use insights from research on American Sign Language (ASL) phonology to
train models for isolated sign language recognition (ISLR), a step towards
automatic sign language understanding. Our key insight is to explicitly
recognize the role of phonology in sign production to achieve more accurate
ISLR than existing work which does not consider sign language phonology. We
train ISLR models that take in pose estimations of a signer producing a single
sign to predict not only the sign but additionally its phonological
characteristics, such as the handshape. These auxiliary predictions lead to a
nearly 9% absolute gain in sign recognition accuracy on the WLASL benchmark,
with consistent improvements in ISLR regardless of the underlying prediction
model architecture. This work has the potential to accelerate linguistic
research in the domain of signed languages and reduce communication barriers
between deaf and hearing people.

##  1 Introduction

When learning to recognize sign language, there is evidence that people rely
on breaking signs down into their constituent parts, such as the configuration
and location of the hand (Klima and Bellugi, 1979). This process is also true
of spoken language recognition, where recognizing sound patterns plays a
crucial role in one’s ability to recognize a word. Sometimes, one of these
“parts” (phonemes) is the only distinguishing factor between two very
different terms, as seen in the signs for difference (palms up) and balance
(palms down) in Croatian Sign Language (Kuhn et al., 2006). Thus, the ability
to encode and recognize individual phonemes and the relationships among them
is essential for sign recognition. As a first step in exploring the
practicality of phoneme recognition, we ask: Can machine learning models for
isolated sign language recognition (ISLR) benefit from the phonological
structure of signs?

Figure 1: We demonstrate that sign language recognition models improve in
accuracy when also tasked with predicting component phonemes of the sign.

While some ISLR models explicitly focus on the signers’ hands (Hu et al.,
2021) or face (Albanie et al., 2020), none have leveraged sign language
phonology. Instead, ISLR has been treated similarly to gesture recognition,
where a “gesture” (such as swinging an imaginary bat or waving a hand) has no
underlying structure except for that of the human body itself. This lack of
structure might explain why state-of-the-art models like the Sign Language
Graph Convolution Network (SL-GCN, Jiang et al. 2021) sometimes predict labels
that are visually and phonologically unrelated to the ground truth, as shown
in Figure 1.

In contrast, we show that models trained to recognize both signs and their
phonemes will be more accurate at sign identification than those trained for
ISLR alone. Our main contributions are:

  * •

We join an ISLR benchmark with a dataset of phonologically-labeled signs
(§3.1) and describe a simple method for learning these labels alongside the
target gloss111A “gloss” is a label for a sign that corresponds to its
translation in the target language, such as apple. (§3.2).

  * •

We explore which and how many phoneme types are most beneficial as an
auxiliary task to sign recognition (§3.3, §4.1).

  * •

We demonstrate that adding auxiliary predictions for sign language phonology
targets yields nearly 9% absolute gain in accuracy for ISLR sign prediction
(§4.2), and that the resulting phoneme classification heads outperform prior
work (§4.3).

##  2 Background

Sign languages are complete and natural languages primarily used by deaf and
hard-of-hearing people. There are hundreds of sign languages in the world
today collectively used by tens of millions of people (Eberhard et al., 2022).
They rely on the hands, face, and body to communicate meaning according to
complex grammars which are independent of any spoken language.

Sign languages have been and continue to be largely overlooked in natural
language processing (NLP) research, necessitating explicit calls for more
inclusivity (e.g. Yin et al. 2021, Bragg et al. 2019). In this paper, we seek
to bridge robust techniques in NLP with insights from theories of sign
language phonology.

#### Sign language phonology

is an abstract system of rules that governs how the structural units of signs
(e.g., handshape, location, movement) are combined to create an infinite
number of utterances. These manual units play a significant role at the
phonological level similarly to place of articulation, manner, and voicing in
spoken language. Theories of sign language phonology attempt to enumerate the
meaningless units or “phonemes” found in a sign language and describe the
complex relationships among them. In ASL-LEX 2.0, Sehyr et al. (2021) describe
16 types of phonemes, largely guided by Brentari’s Prosodic Model (Brentari,
1998). We provide three examples of these phoneme types here:

  * •

Minor Location: one of 37 regions of the body where the sign is produced (e.g.
“chin”).

  * •

Handshape: one of 49 configurations of the hand (e.g. “2”).

  * •

Path Movement: one of 8 ways of moving the hand through space during the
production of a single sign (e.g. “circular”).

Brentari’s Prosodic Model contains $<200$ possible phonemes across its 16
phoneme types, each of which can be observed during the production of any
sign. In ASL-LEX 2.0, about 70% of signs can be uniquely identified by their
phonemes, making them an appealing conduit for learning to recognize signs. We
leverage these properties by using them as target labels alongside the target
gloss.

#### ISLR: Definition and Prior Work

In ISLR, a model is given a video of one sign being produced in isolation and
must predict the target gloss $S_{\textrm{gloss}}$. Many models have been
proposed to recognize isolated signs, varying with regard to input modality
(e.g. pose, RGB video), pretraining (e.g. frame prediction, hand modeling),
and encoding strategy (e.g. attention, convolution). Selvaraj et al. (2022)
provide a comprehensive framework for comparing models across multilingual
data, in particular LSTMs (Konstantinidis et al., 2018), Transformers (Devlin
et al., 2019), Spatio-Temporal Graph Convolution Network (ST-GCN, Cheng et al.
2020), and Sign Language Graph Convolutional Network (SL-GCN, Jiang et al.
2021).

We evaluate our method with SL-GCN and via a Transformer network. These models
are open-sourced,222https://openhands.readthedocs.io/ easily modifiable, and
take in pose information as input. These models perform well on the WLASL 2000
benchmark (Li et al., 2020). While the model from (Hu et al., 2021) obtains
higher accuracy on that benchmark, their code is not publicly available to
replicate those findings.

##  3 Method

We combine two datasets for the task of ISLR, ASL-LEX 2.0 (Sehyr et al., 2021)
and WLASL 2000 (Li et al., 2020), in order to learn ASL phonology (§3.1).
Then, we describe how to utilize these data by learning two ISLR models to
predict both the target gloss and the phonemes for any input (§3.2). Finally,
we address the questions of how many and which phoneme types are best for ISLR
(§3.3). The dataset and modified models are released for replication and
future
work.333https://github.com/leekezar/ImprovingSignRecognitionWithPhonology

###  3.1 Data

We combine the phonological annotations in ASL-LEX 2.0 (Sehyr et al., 2021)
with signs in the WLASL 2000 ISLR benchmark (Li et al., 2020). ASL-LEX
contains 2,723 videos, each demonstrating a unique sign and human-annotated
with phonemes across 16 categories. WLASL contains 21,083 videos, each
demonstrating one of 2,000 unique signs (an average of 10.5 videos per sign).

To combine these datasets, we edit the WLASL metadata file to add 16 new
properties (one for each phoneme type) to each video example. If the video’s
English gloss is also found in ASL-LEX, then we copy the phonemes directly
from ASL-LEX. If it is not found, then we set these new properties to -1 and
ignore them during training. After combining, 48% of videos in the aggregated
dataset have phonological labels, and all of the videos retain their original
split (train, validation, and test) and English gloss. Note that this dataset
is identical in structure to WLASL-LEX (Tavella et al., 2022), however, both
our sources are more recently updated and contain more samples. Table 1
provides a summary of the combined data.

|  | # Videos
---|---|---
$\mathcal{P}$ Labels | # Signs | Train | Val | Test | Total
✗ | 1246 | 7850 | 2221 | 1574 | 11645
✓ | 754 | 6439 | 1695 | 1304 | 9438
Total | 2000 | 14289 | 3916 | 2878 | 21083
Table 1: We match phonological data from ASL-LEX 2.0 with signs in the WLASL benchmark to create a subset of WLASL with phoneme type labels $\mathcal{P}$. | Pred | WLASL${}^{\text{test}}_{\text{all}}$ | WLASL${}^{\text{test}}_{\text{w}\mathcal{P}}$ | WLASL${}^{\text{test}}_{\text{w/o}\mathcal{P}}$
---|---|---|---|---
Model | $\mathcal{P}$ | %A@1 | %A@3 | MRR | %A@1 | %A@3 | MRR | %A@1 | %A@3 | MRR
| ✗ |  $29.4$$\pm 1.6$ |  $50.2$$\pm 2.3$ |  $.43$$\pm.02$ |  $35.0$$\pm 1.8$ |  $56.1$$\pm 1.7$ |  $.48$$\pm.02$ |  $24.8$$\pm 1.4$ |  $45.3$$\pm 3.0$ |  $.39$$\pm.02$
SL-GCN | ✓ |  $38.1$$\pm 0.5$ |  $61.0$$\pm 0.3$ |  $.52$$\pm.00$ |  $44.1$$\pm 1.1$ |  $64.1$$\pm 0.6$ |  $.56$$\pm.01$ |  $33.1$$\pm 0.3$ |  $58.4$$\pm 0.2$ |  $.49$$\pm.00$
_$\Delta$ Improvement_ |  ${}^{*}8.7$$\pm 0.0$ |  ${}^{*}10.8$$\pm 0.0$ |  ${}^{*}.09$$\pm.00$ |  $9.1$$\pm 0.0$ |  $8.1$$\pm 0.0$ |  $.08$$\pm.00$ |  $8.3$$\pm 0.0$ |  $13.1$$\pm 0.0$ |  $.10$$\pm.00$
| ✗ |  $20.5$$\pm 0.4$ |  $36.9$$\pm 1.0$ |  $.32$$\pm.01$ |  $24.5$$\pm 1.1$ |  $41.2$$\pm 1.7$ |  $.36$$\pm.01$ |  $17.2$$\pm 0.3$ |  $33.3$$\pm 0.7$ |  $.29$$\pm.00$
Transformer | ✓ |  $23.4$$\pm 0.4$ |  $41.7$$\pm 0.7$ |  $.36$$\pm.01$ |  $28.2$$\pm 0.4$ |  $46.5$$\pm 0.6$ |  $.40$$\pm.01$ |  $19.3$$\pm 1.0$ |  $37.8$$\pm 1.6$ |  $.32$$\pm.01$
_$\Delta$ Improvement_ |  ${}^{*}2.8$$\pm 0.0$ |  ${}^{*}4.8$$\pm 0.0$ |  ${}^{*}.04$$\pm.00$ |  $3.7$$\pm 0.0$ |  $5.3$$\pm 0.0$ |  $.04$$\pm.00$ |  $2.1$$\pm 0.0$ |  $4.5$$\pm 0.0$ |  $.03$$\pm.00$
Table 2: ISLR model performance with and without training with auxiliary
phoneme predictions averaged over four seeds. Models are trained on
WLASL${}^{\text{train}}_{\text{all}}$ and evaluated on
WLASL${}^{\text{test}}_{\text{all}}$. Models trained to predict phonemes
improve over their ISLR-only baselines on both signs seen at training time
with phonemes (WLASL${}^{\text{test}}_{\text{w}\mathcal{P}}$) and signs for
which no phonological data was available during training
(WLASL${}^{\text{test}}_{\text{w/o}\mathcal{P}}$). Differences on
WLASL${}^{\text{test}}_{\text{all}}$ are significant (∗) at $p<0.05$ under a
Welch’s two-sided $t$-test with a Bonferroni correction applied.

###  3.2 Models

We add phoneme value predictions to two ISLR model architectures: a graph
convolutional network, SL-GCN Jiang et al. (2021), and a Transformer-based
model. These models are implemented by the OpenHands project (Selvaraj et al.,
2022) and are largely left untouched; we refer the reader to the OpenHands
paper and code for implementation details. The SL-GCN model treats pose
estimations over time as a connected graph and learns 10 convolution layers
over this graph, using spatial and temporal attention. The Transformer model
treats pose estimations as a sequence of coordinates over time and learns 5
Transformer layers similarly to BERT Devlin et al. (2019). Importantly, both
of these models implement spatial and temporal attention, a feature which
enables phoneme recognition even when the phoneme exists for a short amount of
time.

For each model, we modify the decoder to classify not only the target gloss,
but also the selected phonemes. This is accomplished by adding $n$ fully-
connected layers to the decoder, each with shape (hidden size, # phoneme
values). During the forward pass, the video encoding is used as the input for
each fully connected layer (not chained together). The total loss is then
computed as:

$\mathcal{L}_{\textrm{total}}=\mathcal{L}_{\textrm{gloss}}+\sum_{\textrm{phoneme}\in\mathcal{P}}\mathcal{L}_{\textrm{phoneme}},$

where $\mathcal{L}_{\textrm{gloss}}$ is the cross entropy of the model’s gloss
predictions, while $\mathcal{L}_{\textrm{phoneme}}$ is the cross entropy of
the model’s phoneme predictions. The sum of these losses is then
backpropagated to the entire model, encouraging the encoder to learn a
representation which more explicitly captures the desired phonemes
$\mathcal{P}$ alongside the target gloss (Fig 2).

We train models until the validation accuracy has not improved in the last 30
epochs and use the top performing model for testing. For further details on
model implementation and training procedure, see Selvaraj et al. (2022).

Figure 2: The proposed decoder relies on fully-connected layers for each
classification head: one for the target gloss and one for each of the $n$
phoneme types.

###  3.3 Phoneme Type Selection

It is not immediately clear which, if any, of the 16 phoneme types in ASL-LEX
2.0 yield improvements on ISLR. Regarding how many phoneme types, one might
assume that more informative outputs would only improve a model’s ability to
recognize signs, and therefore all 16 phoneme types should be included.
However, these additions come at a cost to the encoder, which must now learn
to fit more information into the same encoding space without adding new
samples. Furthermore, it is unclear which types to maximize performance.

To address these questions, we define the utility $U$ of a set of phonemes
types $\mathcal{P}$ as the percentage of signs that are uniquely identified by
those types. Defined in this way, a set of phoneme types with high utility
ensures that when a model can accurately predict those types, it is guaranteed
to have sufficient information to recognize $U(\mathcal{P})$ percent of signs.
$U(\mathcal{P})$ is provided by:

$U(\mathcal{P})=\frac{\sum_{S,S^{\prime}\in
V}\mathbf{1}\left[p(S|\mathcal{P})>p(S^{\prime}|\mathcal{P})\right]}{|V|-1},$

where $V$ is the set of all target glosses and $P(S|\mathcal{P})$ is the
probability of a sign $S$ given the observed phoneme values in $\mathcal{P}$.
We implement $P(S|\mathcal{P})$ with a simple look-up table for all possible
combinations of the 16 phoneme types. With this utility function in hand, we
can define the optimal subset of $n$ phoneme types as:

$\mathcal{P}^{*}(n)=\left\\{\operatorname*{arg\,max}_{\mathcal{P}}U(\mathcal{P}):|\mathcal{P}|=n\right\\}.$

##  4 Results

We demonstrate across-the-board improvements on ISLR when predicting phonemes
alongside glosses. We measure model performance via ISLR accuracy, both top-1
and top-3, as well as mean reciprocal rank (MRR), which ranges from 1 (correct
sign given highest prediction score) to 1/2000 (correct sign given lowest
prediction score).

###  4.1 Not All Phonemes are Helpful.

First, we explore which subsets of the 16 labeled phonemes are most beneficial
for downstream ISLR. We train models with auxiliary losses for
$\mathcal{P}^{*}(n),n\in\left\\{2,5,9,16\right\\}$ and report their
performance in Table 3. With two classification heads—handshape and minor
location—we most improve ISLR on WLASL${}^{\text{val}}_{\text{w}\mathcal{P}}$.

$n$ | $\mathcal{P}^{*}(n)$ | %A@1 | %A@3 | MRR
---|---|---|---|---
0 | $\emptyset$ | 50.2 | 69.3 | .62
2 | Dominant Handshape, Minor Location | 55.7 | 74.7 | .67
5 |  $\mathcal{P}^{*}(2)$ \+ Nondominant HS, Path Movement, Repeated Movement | 51.5 | 69.3 | .62
9 |  $\mathcal{P}^{*}(5)$ \+ 2nd Minor Loc., 2nd Handshape, Wrist Twist, Contact | 52.5 | 69.3 | .64
16 |  $\mathcal{P}^{*}(9)$ \+ Remaining 7 phoneme types | 54.3 | 72.7 | .65
Table 3: SL-GCN sign recognition accuracy when trained on
WLASL${}^{\text{train}}_{\text{w}\mathcal{P}}$ with auxiliary predictions of
the top-$n$ phoneme types $\mathcal{P}$ and tested on
WLASL${}^{\text{val}}_{\text{w}\mathcal{P}}$. See §3.3 for the details of
$\mathcal{P}^{*}(n)$.

###  4.2 Predicting Phonemes Improves ISLR.

Table 2 demonstrates that adding classification heads for handshape and minor
location yield a 3–9% gain on top-1 accuracy, 5–11% gain on top-3 accuracy,
and .04–.09 gain on MRR. These gains are greater for signs trained with
phonological labels, but extend to signs that do not have phonological labels
as well!

###  4.3 SL-GCN Performs Accurate Phoneme Classification.

To lay the groundwork for modeling phonology in and of itself, we train SL-GCN
to predict all 16 phoneme types and examine its accuracy at phoneme prediction
(Figure 3). We compare to a frozen SL-GCN encoder pretrained for only ISLR, on
top of which we learn linear probes for each phoneme type, as well as a
majority class baseline. In all cases, training SL-GCN explicitly for phoneme
prediction leads to the highest phoneme prediction accuracy. Prior work
predicted phoneme values for Flexion, Major Location, Minor Location, Path
Movement, Selected Fingers, and Sign Type Tavella et al. (2022). Despite not
being the explicit goal of this work, SL-GCN with auxiliary phoneme prediction
outperforms that model, too.

Figure 3: Model phoneme prediction accuracy when trained on
WLASL${}^{\text{train}}_{\text{w}\mathcal{P}}$ and tested on
WLASL${}^{\text{test}}_{\text{w}\mathcal{P}}$.

##  5 Discussion

We find that adding auxiliary classification tasks for sign phonemes to ISLR
models statistically significantly improves sign recognition accuracy.
Representing phonemes during training may enable models to learn a more
holistic latent representation of sign videos compared to models that only
predict the target gloss. The success of this approach provides evidence that
handshape and minor location are not only useful in recognizing signs, but
also easy enough to learn with semi-supervision (recall that only 48% of the
dataset has handshape and minor location labels). Our findings show that both
models learn these new labels well (Fig 3) and as a result, the encodings for
all videos contain more relevant information for ISLR.

A secondary finding of this paper is that SL-GCN, when trained to recognize
all 16 phoneme types, outperforms prior work by anywhere from 1%-9%. Still,
there is room for improvement in phoneme recognition, especially for
handshape, minor location, and path movement.

##  6 Limitations

The WLASL benchmark has several notable limitations that must be taken into
account by those interested in using it. Dafnis et al. (2022) show that
incorrect labels are pervasive in WLASL, causing lower ISLR accuracy and, in
this work, incorrect phoneme labels. Additionally, existing sign language
datasets do not provide information about the signers’ fluency, dialect, age,
or race and therefore may not be representative of those who use ASL. Finally,
we caution those interested in collecting ASL data against scraping websites
without permission, and we encourage acknowledging the creators of those
sources.

As a first attempt to model sign language phonology in order to improve sign
recognition, we applied our approach to two models and used data for one
language pair (ASL/English). Although many phonemes are shared across signed
languages, more language pairs and models should be tested in order to verify
our claim that learning phonology improves sign recognition in general. In
particular, the Two-Stream Inflated 3D ConvNet (I3D; Carreira and Zisserman
2017) model, designed for gesture recognition, has also been shown to do well
on ISLR (e.g. Hosain et al. 2021, Albanie et al. 2020) and we look forward to
extending our method to this model as well.

## References

  * Albanie et al. (2020) Samuel Albanie, Gül Varol, Liliane Momeni, Triantafyllos Afouras, Joon Son Chung, Neil Fox, and Andrew Zisserman. 2020.  BSL-1K: Scaling up co-articulated sign language recognition using mouthing cues.  In _European Conference on Computer Vision_.
  * Bragg et al. (2019) Danielle Bragg, Oscar Koller, Mary Bellard, Larwan Berke, Patrick Boudreault, Annelies Braffort, Naomi K. Caselli, Matt Huenerfauth, Hernisa Kacorri, Tessa Verhoef, Christian Vogler, and Meredith Ringel Morris. 2019.  Sign language recognition, generation, and translation: An interdisciplinary perspective.  _The 21st International ACM SIGACCESS Conference on Computers and Accessibility_.
  * Brentari (1998) Diane Brentari. 1998.  _A Prosodic Model of Sign Language Phonology_.  The MIT Press.
  * Carreira and Zisserman (2017) João Carreira and Andrew Zisserman. 2017.  Quo vadis, action recognition? a new model and the kinetics dataset.  _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Cheng et al. (2020) Ke Cheng, Yifan Zhang, Congqi Cao, Lei Shi, Jian Cheng, and Hanqing Lu. 2020.  Decoupling gcn with dropgraph module for skeleton-based action recognition.  In _European Conference on Computer Vision (ECCV)_.
  * Dafnis et al. (2022) Konstantinos M. Dafnis, Evgenia Chroni, Carol Neidle, and Dimitri Metaxas. 2022\.  Bidirectional skeleton-based isolated sign recognition using graph convolutional networks.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 7328–7338. European Language Resources Association.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Eberhard et al. (2022) David M. Eberhard, Gary F. Simons, and Charles D. Fennig. 2022.  Ethnologue: Languages of the world.
  * Hosain et al. (2021) Al Amin Hosain, Panneer Selvam Santhalingam, Parth H. Pathak, Huzefa Rangwala, and Jana Kosecka. 2021.  Hand pose guided 3d pooling for word-level sign language recognition.  _2021 IEEE Winter Conference on Applications of Computer Vision (WACV)_.
  * Hu et al. (2021) Hezhen Hu, Wen gang Zhou, and Houqiang Li. 2021.  Hand-model-aware sign language recognition.  In _Association for the Advancement of Artificial Intelligence (AAAI)_.
  * Jiang et al. (2021) Songyao Jiang, Bin Sun, Lichen Wang, Yue Bai, Kunpeng Li, and Yun Raymond Fu. 2021\.  Skeleton aware multi-modal sign language recognition.  _IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_.
  * Klima and Bellugi (1979) E.S. Klima and U. Bellugi. 1979.  _The Signs of Language_.  Harvard University Press.
  * Konstantinidis et al. (2018) Dimitrios Konstantinidis, Kosmas Dimitropoulos, and Petros Daras. 2018.  Sign language recognition based on hand and body skeletal data.  _3DTV-Conference: The True Vision-Capture, Transmission and Display of 3D Video (3DTV-CON)_.
  * Kuhn et al. (2006) Ninoslava Kuhn, Tamara Ciciliani, and Ronnie Wilbur. 2006.  Phonological parameters in croatian sign language.  _Sign Language & Linguistics_.
  * Li et al. (2020) Dongxu Li, Cristian Rodriguez, Xin Yu, and Hongdong Li. 2020.  Word-level deep sign language recognition from video: A new large-scale dataset and methods comparison.  In _The IEEE Winter Conference on Applications of Computer Vision (WACV)_.
  * Sehyr et al. (2021) Zed Sevcikova Sehyr, Naomi K. Caselli, Ariel Cohen-Goldberg, and Karen Emmorey. 2021\.  The ASL-LEX 2.0 Project: A Database of Lexical and Phonological Properties for 2,723 Signs in American Sign Language.  _The Journal of Deaf Studies and Deaf Education_.
  * Selvaraj et al. (2022) Prem Selvaraj, C. GokulN., Pratyush Kumar, and Mitesh M. Khapra. 2022.  Openhands: Making sign language recognition accessible with pose-based pretrained models across languages.  In _Association for Computational Linguistics (ACL)_.
  * Tavella et al. (2022) Federico Tavella, Viktor Schlegel, Marta Romeo, Aphrodite Galata, and Angelo Cangelosi. 2022.  WLASL-LEX: a dataset for recognising phonological properties in American Sign Language.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_.
  * Yin et al. (2021) Kayo Yin, Amit Moryossef, Julie A. Hochgesang, Yoav Goldberg, and Malihe Alikhani. 2021.  Including signed languages in natural language processing.  In _Association for Computational Linguistics (ACL)_.


# Leveraging Large Language Models for Fuzzy String Matching in Political
Science

Yu Wang<EMAIL_ADDRESS>Institute for Advanced Study in Social
Sciences, Fudan University, Shanghai, 200433, China

###### Abstract

Fuzzy string matching remains a key issue when political scientists combine
data from different sources. Existing matching methods invariably rely on
string distances, such as Levenshtein distance and cosine similarity. As such,
they are inherently incapable of matching strings that refer to the same
entity with different names such as “JP Morgan” and “Chase Bank”, “DPRK” and
“North Korea”, “Chuck Fleischmann (R)” and “Charles Fleischmann (R)”. In this
letter, we propose to use large language models to entirely sidestep this
problem in an easy and intuitive manner. Extensive experiments show that our
proposed methods can improve the state of the art by as much as 39% in terms
of average precision while being substantially easier and more intuitive to
use by political scientists. Moreover, our results are robust against various
temperatures. We further note that enhanced prompting can lead to additional
performance improvements.

###### keywords:

Large language models, ChatGPT, prompt engineering, text as data

## Introduction

Political scientists frequently deal with many variables in their research
and, as part of the data preparation process, need to merge datasets from
different sources using a shared identifier. For example, North Korea is
represented as “Korea, Dem. People’s Rep.” in economic data from the World
Bank, as “Korea, Dem. People’s Rep. of” in trade data from the International
Monetary Fund, and as “Korea North” in polity scores from the Center for
Systemic Peace [1]. This is sometimes referred to as the fuzzy string matching
problem. Existing solutions to the fuzzy string matching problem invariably
operate at the string level. Such solutions include edit distance, longest
common substring, and bag-of-words similarities. Edit distance is good at
matching cases with minor typos, longest common substring is designed to be
sensitive to even the smallest letter differences, and bag-of-words
similarities are robust against word orders. More recently, researchers have
proposed a method that utilizes all these different distances as separate
features to build a random forest. The new method further involves human
annotation in the loop (HITL) to overcome predictive deficiencies [2]. Their
method shows improvement over using the single solutions above. Nevertheless,
given that all these individual features are ultimately based on matching raw
strings, the resulting random forest still cannot overcome the inherent
difficulty of matching entities expressed in totally different terms. For
example, the model performs poorly in such cases as “DPRK” and “North Korea”,
“JP Morgan” and “Chase Bank”, “Chuck Fleischmann (R)” and “Charles Fleischmann
(R)” At the same time, the involvement of human annotation in the loop
increases the cost and slows down the velocity of model development.

In this paper we propose a semantics-based solution that leverages large
language models to overcome the limitations noted above. Specifically, we use
ChatGPT as a zero-shot classifier for fuzzy string matching. ChatGPT is known
to contain world knowledge [3, 4, 5], so we expect them to see the semantic
similarity between “DPRK” and “North Korea” and between “JP Morgan” and “Chase
Bank.” As a sanity check, we did ask ChatGPT the following question: “Does
DPRK and North Korea refer to the same country? Yes or no?” and got the
correct answer. At the same time, ChatGPT uses byte-pair encoding (BPE), a
subword encoding mechanism [6], and consequently is relatively robust against
typos in individual words. Indeed, researchers have already identified several
areas where ChatGPT excels in zero-shot learning [7, 8], which motivates us to
experiment with using ChatGPT as a zero-shot classifier for fuzzy string
matching. Extensive experiments offer strong evidence that the zero-shot
ChatGPT outperforms the best performing string matching methods by a
substantial margin, while being substantially easier and more intuitive to
use. Our results are robust against the use of different temperatures. In
addition, we observe that improved prompting could lead to performance gains.

## Results

Figure 1: ChatGPT substantially outperforms character-based matching methods.
The zero-shot ChatGPTs, at temperatures 0.2 and 1, both outperform character-
based methods by a large margin.

We use two main datasets (n = 4,500) that cover both organizations and
politicians in the United States from [2]. The first dataset, Amicus and
Bonica, focuses on matching organizations and has 4,000 samples. The second
dataset, Incumbent Voting, has 500 samples and centers around matching
political candidates. The second dataset is built from a larger set of
mismatched named entities. That set is first sorted using a random forest-
based model from [2] and the top five hundred most likely matches come to form
the Incumbent Voting dataset.

In Figure 1, we report our result on the Amicus and Bonica dataset in terms of
average precision (AP) scores. we plot the results for N-Gram Overlap,
Jaccard, Cosine, Random Forest, HITL, Jaro-Winkler, ChatGPT-T10 and
ChatGPT-T02. HITL refers to the human-in-the-loop algorithm proposed by [2]
and is built on top of a random forest. HITL differs from the random forest
model in that it involves actual human annotation in the loop. The first fix
bars use the results from [2]. ChatGPT-T10 refers to ChatGPT with a
temperature of 1.0. ChatGPT-T02 refers to ChatGPT with a temperature of 0.2.

We observe that HITL [2] and Jaro-Winkler perform the best among the existing
models, with an average precision score of 0.57 and 0.66, respectively. n-Gram
Overlap performs the worst with an average precision of 0.2. Note that both
Jaccard similarity and cosine similarity are composition-based measures.
Jaccard similarity measures the ratio of in-common characters to total
characters. Cosine similarity measures the cosine of the angle between two
letter frequency vectors. N-Gram Overlap refers to the longest common
substring. Jaro-Winkler is one type of edit distance is calculated using the R
package RecordLinkage [2]. In comparison, the zero-shot ChatGPT attains an
average precision score of 0.91 at a temperature setting of 1.0 and improves
slightly to a score of 0.92 when the temperature is reduced to 0.2. This
represents a gain of 39% for ChatGPT over existing methods. This is
particularly noteworthy given that, unlike HITL, ChatGPT does not use any
training samples in the current setting.

Figure 2: ChatGPT again outperforms character-based matching methods. In
particular, when we provide more context in the prompt (p2), zero-shot
ChatGPTs, at temperatures 0.2 and 1.0, both outperform character-based methods
by a large margin and achieve 100% precision.

Figure 2 shows results for the Incumbent Voting dataset in terms of precision
at recall = 1.0, where our goal is to identify all the matching politicians
(100% recall) in the dataset with the highest precision. As our baselines, we
have results for Jaccard, Random Forest (trained on the Amicus and Bonica
dataset), and Cosine. The random forest model is the same model as used in
Figure 1. Here it is directly applied to Incumbent Voting, which is considered
out of domain [9]. Besides the baseline models, we report results from zero-
shot ChatGPT, with two different temperatures and different prompting schemes.

We observe that n-gram performs best among the character-based methods,
achieving a precision of 0.947. By comparison, ChatGPT achieves a precision of
0.951 with temperature at 1.0 and 0.966 with temperature at 0.2, both using
plain prompting. When we add additional information about the entity pairs,
including what ‘(R)’ and ‘(D)’ stand for as well as the fact that all those
entities are Congressional candidates, we observe that precision can reach 1.0
at both temperatures, which represents another 6% gain over the best
performing character-based method, n-gram.

## Discussion

#### Performance

Fuzzy string matching is a long-standing problem in political science. So far,
existing methods have exclusively focused on character-level calculations. In
this letter, we have proposed a semantics-based matching methods that leverage
the latest large language models. We have shown that zero-shot ChatGPT
outperforms the best existing methods by as much as 39% in the Amicus and
Bonica dataset. In the Incumbent Voting, where records represent the most
probable matching pairs as ranked by a base random forest model, ChatGPT was
able to reach a precision of 1.0 with detailed prompting.

#### Ease of use

In addition to its exceptional performance, we note that another advantage of
using zero-shot ChatGPT is its ease of use. Among the existing character-based
matching methods, some of them, such as random forest, HITL, and n-gram, can
get quite complicated. By contrast, ChatGPT and other similar LLMs only
require a simple and intuitive command in a natural language, which
drastically lowers the technical barriers.

#### Running Time

In terms of running time, we note that running zero-shot inference using
ChatGPT-4 for 4,000 samples takes about 3,545 seconds (max among our multiple
runs). While this is doable for small datasets of similar sizes, running time
for larger datasets could become a bottleneck. Potential solutions to speeding
up the process include (1) parallelizing the API calls, (2) making calls in
batches, and (3) using the ChatGPT-3, which is faster, instead of ChatGPT-4.
Alternatively, researchers could adopt a two-stage approach, where at the
first stage a fast but less accurate model, e.g. Cosine Similarity, is used to
sort the entity pairs in terms of matching probability and at the second stage
ChatGPT is applied to grading only the top ranked entity pairs. This is
similar to the experiment on Incumbent Voting in this study.

## Materials and methods

### Data

We use the main datasets from [2]: Amicus and Bonic and Incumbent Voting. In
Amicus and Bonic, strings representing campaign donors [10] are matched to
strings that represent amicus curiae cosigners [11]. The training set contains
71,043 string pairs in total. Please refer to Table 1 for an illustration of
the training data and see the replication package for more details. In terms
of the distribution of positive labels and negative labels, we note that only
357 string pairs refer to the same entity. Given that the positive samples
represent only 0.5% of the training set, the dataset is severely imbalanced.
For related studies on rare event classification (e.g., civil wars), readers
can refer to [12] and [13]. The test set contains 4,000 string pairs. In our
experiments, we use the test set exclusively.

In the Incumbent Voting dataset, strings representing names of the
Congressional candidates hand-typed by respondents are matched to strings that
represent the standard version of candidates’ names. The data points in
Incumbent Voting are part of the 5,356 mismatched pairs in total. [2] build
Incumbent Voting by first ranking all these mismatched pairs by the random
forest model trained on Amicus and Bonic, select the top 500 most likely
matches, and then label them.

Table 1: Sample data from Datasets Amicus and Bonica and Incumbent Voting. Capitalization is kept the same as in the original dataset. Left | Right | Label
---|---|---
JPMORGAN CHASE BANK NA | jp morgan chase | 1
roadway express inc | motion picture assn | 0
Chuck Fleischmann (R) | Charles Fleischmann (R) | 1
Brad Sherman (D) | Howard Berman (D) | 0

#### Methods

When calling the ChatGPT model, we do not use the training set. Instead, we
build zero-shot prompts and rely on ChatGPT to make inferences on the test set
directly [7]. Specifically, we use ChatGPT-4 version, gpt-4-0613, and use the
OpenAI API for chat completion.111For an introduction to the API, please see
https://platform.openai.com/docs/quickstart?context=python. GPT-4 was accessed
online on Oct 28, 2023. For coding details, please refer to our replication
package. For our first experiment, we provide the prompt in a standardized
format as follows, where entity_a and entity_b refer to the two entity
strings, respectively:

How confident are you that the following entities, entity_a and entity_b,
refer to the same entity, allowing for the possibility of minor typos?

Please return your confidence in the range of 0 and 1 only and no other words.

For our second experiment (Incumbent Voting), besides using the standard
prompt, we also enrich the prompt with more information about each entity
pair. For example, all the named entities are Congressional candidates. ‘R’
stands for Republican in ‘Walter B. Jones (R)’.

You are a helpful and knowledgeable assistant. You will be given two entities.
Both entities refer to Congressional candidates, where ‘R’ stands for
Republican and ‘D’ stands for ‘Democrat’.

How confident are you that the following entities, entity_a and entity_b,
refer to the same entity, allowing for the possibility of minor typos?

Please return your confidence in the range of 0 and 1 only and no other words.

We make an individual call for each entity pair and then parse the returned
response into a certainty score, which is a float number between 0 and 1. The
higher the score, the more likely that the two entity strings refer to the
same entity. We then use the ChatGPT score to sort and rank the likelihood of
two strings referring to the same entity.

## Data availability

All data generated or analysed during this study are included in this
published article and its supplementary information files.

## Ethical approval

This article does not contain any studies with human participants performed by
any of the authors.

## References

  *   * Stone et al. [2022] Stone, R., Wang, Y., Yu, S.: Chinese Power and the State-Owned Enterprise. International Organization 76(1), 229–50 (2022)
  * Kaufman and Klevs [2022] Kaufman, A.R., Klevs, A.: Adaptive fuzzy string matching: How to merge datasets with only one (messy) identifying field. Political Analysis (2022)
  * Longpre et al. [2020] Longpre, S., Wang, Y., DuBois, C.: How Effective is Task-Agnostic Data Augmentation for Pretrained Transformers? Findings of the Association for Computational Linguistics: EMNLP 2020 (2020)
  * Yu et al. [2024] Yu, J., Wang, X., Tu, S., Cao, S., Zhang-Li, D., Lv, X., Peng, H., Yao, Z., Zhang, X., Li, H., Li, C., Zhang, Z., Bai, Y., Liu, Y., Xin, A., Lin, N., Yun, K., Gong, L., Chen, J., Wu, Z., Qi, Y., Li, W., Guan, Y., Zeng, K., Qi, J., Jin, H., Liu, J., Gu, Y., Yao, Y., Ding, N., Hou, L., Liu, Z., Xu, B., Tang, J., Li, J.: Kola: Carefully benchmarking world knowledge of large language models. ICLR (2024)
  * Meo et al. [2023] Meo, S.A., Al-Masri, A.A., Alotaibi, M., Meo, M.Z.S., Meo, M.O.S.: Chatgpt knowledge evaluation in basic and clinical medical sciences: Multiple choice question examination-based performance. Healthcare (Basel). (2023)
  * Sennrich et al. [2016] Sennrich, R., Haddow, B., Birch, A.: Neural machine translation of rare words with subword units. Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (2016)
  * Gilardi et al. [2023] Gilardi, F., Alizadeh, M., Kubli, M.: Chatgpt outperforms crowd-workers for text-annotation tasks. Proceedings of the National Academy of Sciences (2023)
  * Sarkar et al. [2022] Sarkar, S., Feng, D., Santu1, S.K.K.: Zero-shot multi-label topic inference with sentence encoders & llms. EMNLP (2022)
  * Osnabrügge et al. [2021] Osnabrügge, M., Ash, E., Morelli, M.: Cross-Domain Topic Classification for Political Texts. Political Analysis (2021)
  * Bonica [2014] Bonica, A.: Mapping the ideological marketplace. American Journal of Political Science 58(2), 367–386 (2014)
  * Box-Steffensmeier et al. [2013] Box-Steffensmeier, J.M., Christenson, D.P., Hitt, M.P.: Quality over quantity: Amici influence and judicial decision making. American Political Science Review 107(3), 446–460 (2013)
  * Muchlinski et al. [2016] Muchlinski, D., Siroky, D., He, J., Kocher, M.: Comparing Random Forest with Logistic Regression for Predicting Class-Imbalanced Civil War Onset Data. Political Analysis 24(1), 87–103 (2016)
  * Wang [2019] Wang, Y.: Comparing Random Forest with Logistic Regression for Predicting Class-Imbalanced Civil War Onset Data: A Comment. Political Analysis 21(1), 107–110 (2019)