author

# Extremal Fitting CQs do not Generalize

Balder ten Cate  ILLC, University of Amsterdam  Maurice Funk  Leipzig
University and ScaDS.AI  Jean Christoph Jung  TU Dortmund University  Carsten
Lutz  Leipzig University and ScaDS.AI

###### Abstract

A fitting algorithm for conjunctive queries (CQs) produces, given a set of
positively and negatively labeled data examples, a CQ that fits these
examples. In general, there may be many non-equivalent fitting CQs and thus
the algorithm has some freedom in producing its output. Additional desirable
properties of the produced CQ are that it generalizes well to unseen examples
in the sense of PAC learning and that it is most general or most specific in
the set of all fitting CQs. In this research note, we show that these
desiderata are incompatible when we require PAC-style generalization from a
_polynomial_ sample: we prove that any fitting algorithm that produces a most-
specific fitting CQ cannot be a sample-efficient PAC learning algorithm, and
the same is true for fitting algorithms that produce a most-general fitting CQ
(when it exists). Our proofs rely on a polynomial construction of relativized
homomorphism dualities for path-shaped structures.

##  1 Introduction

The classic _query-by-example_ paradigm [13], also known as _query reverse
engineering_ , aims to assist users in query formation. At its heart lies the
_fitting problem_ , which is the task to compute a query that fits a given set
of (positively and negatively) labeled data examples. The fitting problem has
been intensively studied for the class of conjunctive queries, see for example
(CQs) [11, 10, 2].

An algorithm that solves this task, that is, takes as input a set of labeled
data examples and returns a CQ that fits the examples, is called a fitting
algorithm. As most sets of examples have multiple fitting CQs, the returned CQ
depends on the chosen fitting algorithm. If one desires the fitting CQ to have
additional desirable properties, one might thus choose a fitting algorithm
that is tailored towards this purpose. See [6] for an overview.

In many query reverse engineering scenarios, one wants a fitting algorithm
that produces a CQ that correctly labels future examples, provided that they
are drawn from the same distribution as the examples given as an input. This
property is formalized by Valiant’s framework of probably approximately
correct (PAC) learning [12]. Given sufficiently many examples sampled from an
unknown distribution, a PAC learning algorithm is required to return with high
probability $1-\delta$ a CQ that has small classification error $\epsilon$,
for $\delta,\epsilon\in(0,1)$. Additionally, it is desirable that the number
of required examples only grows polynomially with the parameters
$\delta,\epsilon$. If this is the case, we say that the PAC learning algorithm
is _sample-efficient_.

From a logical perspective, extremal fitting CQs are of particular interest.
These are fitting CQs that are most general or most specific in the class of
all fitting CQs. When they exist, extremal fitting CQs describe the entire
(potentially infinite) set of fitting CQs and thus they provide a useful basis
to understand this set. Extremal fitting CQs have recently been studied in
detail in [5].

A natural question is how the desiderata of PAC learning and of extremality
relate. In particular, one may ask whether there is a fitting algorithm that
is both a sample efficient PAC learning algorithm and produces a most-specific
or most-general fitting CQ, when it exists. This question was answered to the
negative in [7] for a class of tree-shaped CQs, there called $\mathcal{EL}$
queries, both for most-specific and for most-general fittings.111We remark
that this is not always the case. In the case of monomials (conjunctions of
propositional literals), for instance, fitting algorithms that produce the
shortest fitting monomial are sample-efficient PAC learning algorithms [1] and
shortest fitting monomials are also most general fittings. The aim of this
note is to extend these results to unrestricted CQs and to present them in a
self-contained way. More specifically, we prove the following:

  1. 1.

Any fitting algorithm for CQs that always produces a most-general fitting CQ,
when it exists, is not a sample-efficient PAC learning algorithm.

  2. 2.

Any fitting algorithm for CQs that always produces a most-specific fitting CQ
is not a sample-efficient PAC learning algorithm.

##  2 Preliminaries

A schema $\mathcal{S}$ is a set of relation symbols, each with associated
arity. A _database instance_ over $\mathcal{S}$ is a finite set $I$ of _facts_
of the form $R(a_{1},\dots,a_{n})$ where $R\in\mathcal{S}$ is a relation
symbol of arity $n$ and $a_{1},\dots,a_{n}$ are _values_. We use
$\mathsf{adom}(I)$ to denote the set of all values used in $I$.

A $k$-ary _conjunctive query_ (CQ) over a schema $\mathcal{S}$ for $k\geq 0$,
is an expression of the form

$q(\textbf{x})\text{ :- }\alpha_{1},\ldots,\alpha_{n}$

where $\textbf{x}=x_{1},\ldots,x_{k}$ is a sequence of variables and each
$\alpha_{i}$ is a relational atom that uses a relation symbol from
$\mathcal{S}$ and no constants. The variables in x are called _answer
variables_ and the other variables used in the atoms $\alpha_{i}$ are the
_existential variables_. We denote by $q(I)$ the set of all $k$-tuples
$\mathbf{a}\in\mathsf{adom}(I)^{k}$ such that $I\models q(\mathbf{a})$. With
the _size_ $||q||$ of a CQ $q$, we mean the number of atoms in it. For CQs
$q_{1}$ and $q_{2}$ of the same arity and over the same schema $\mathcal{S}$,
we write $q_{1}\subseteq q_{2}$ and say that $q_{1}$ is _contained_ in $q_{2}$
if $q_{1}(I)\subseteq q_{2}(I)$ for all database instances $I$ over
$\mathcal{S}$. If $q_{1}\subseteq q_{2}$ and $q_{2}\subseteq q_{1}$, then we
call $q_{1}$ and $q_{2}$ _equivalent_ and write $q_{1}\equiv q_{2}$.

A _data example_ $(I,\mathbf{a})$ for a $k$-ary CQ $q$ consists of a database
instance $I$ together with a tuple $\mathbf{a}\in\mathsf{adom}(I)^{k}$. A data
example is

  * •

a _positive example_ for $q$ if $\textbf{a}\in q(I)$;

  * •

a _negative example_ for $q$ if $\textbf{a}\notin q(I)$.

A collection of labeled examples is a pair $E=(E^{+},E^{-})$ where $E^{+}$ and
$E^{-}$ are sets of examples. We say that a CQ _fits_ $E$ if each element of
$E^{+}$ is a positive example for $q$ and each element of $E^{-}$ is a
negative example for $q$. A _fitting algorithm_ takes as input a collection of
labeled examples $E$ for which a fitting CQ is promised to exist, and returns
such a CQ.

A _homomorphism_ $h$ from an instance $I$ to an instance $J$ (over the same
schema) is a function $h\colon\mathsf{adom}(I)\to\mathsf{adom}(J)$ such that
the $h$-image of every fact of $I$ is a fact of $J$. We write $I\to J$ to
indicate the existence of a homomorphism from $I$ to $J$. For two data
examples $(I,\mathbf{a})$ and $(J,\mathbf{b})$ we write
$(I,\mathbf{a})\to(J,\mathbf{b})$ if there is a homomorphism $h$ from $I$ to
$J$ with $h(\mathbf{a})=\mathbf{b}$.

The _canonical database instance_ of a CQ $q$ is the instance $I_{q}$ (over
the same schema as $q$) whose active domain consists of the variables that
occur in $q$ and whose facts are the atomic formulas in $q$. The _canonical
example_ $e_{q}$ of a CQ $q(\mathbf{x})$ is the example $(I_{q},\mathbf{x})$.
The _canonical CQ_ $q_{I}(\mathbf{a})$ of an example $(I,\mathbf{a})$ is the
CQ whose atoms are the facts of $I$ and whose variables are the values in
$\mathsf{adom}(I)$.

It is well known that for all CQs $q(\mathbf{x})$ and instances $I$ over the
same schema, $\mathbf{a}\in q(I)$ if and only if
$(I_{q},\mathbf{x})\to(I,\mathbf{a})$. Furthermore, for all CQs
$q_{1}(\mathbf{x})$ and $q_{2}(\mathbf{y})$ of the same arity and over the
same schema, $q_{1}\subseteq q_{2}$ if and only if
$(I_{q_{2}},\mathbf{y})\to(I_{q_{1}},\mathbf{x})$. We will use these facts
freely.

###  2.1 PAC Learning

For CQs $q$, $q_{T}$ of the same arity $n$ and a probability distribution over
examples $P$ of arity $n$, we define

$\mathsf{error}_{P,q_{T}}(q)=\mathop{\textrm{Pr}}_{(I,\mathbf{a})\in
P}(\mathbf{a}\in q(I)\mathop{\triangle}q_{T}(I))$

to be the expected error of $q$ relative to $q_{T}$ and $P$ where $\triangle$
denotes symmetry difference. In other words, $\mathsf{error}_{P,q_{T}}(q)$ is
the probability that $q$ disagrees with $q_{T}$ on an example drawn at random
from $P$.

######  Definition 1.

A _PAC learning algorithm_ is a (potentially randomized) algorithm
$\mathbf{A}$ associated with a function
$m\colon\mathbb{R}^{2}\times\mathbb{N}^{3}\rightarrow\mathbb{N}$ such that

  * •

$\mathbf{A}$ takes as input a collection of labeled data examples $E$;

  * •

for all $\epsilon,\delta\in(0,1)$, all finite schemas $\mathcal{S}$, all
$s_{Q},s_{E}\geq 0$, all probability distributions $P$ over examples
$(I,\mathbf{a})$ over $\mathcal{S}$ with $|I|\leq s_{E}$, and all CQs $q_{T}$
with $||q_{T}||\leq s_{Q}$, the following holds: when running $\mathbf{A}$ on
a collection $E$ of at least
$m(\frac{1}{\delta},\frac{1}{\epsilon},|\mathcal{S}|,s_{Q},s_{E})$ data
examples drawn from $P$ and labeled by $q_{T}$, $\mathbf{A}$ returns a CQ
$q_{H}$ such that with probability at least $1-\delta$ (over the choice of
$E$), we have $\mathsf{error}_{P,q_{T}}(q_{H})\leq\epsilon$.

We say that $\mathbf{A}$ _has sample size_ $m$ and call $\mathbf{A}$ _sample-
efficient_ if $m$ is a polynomial.

Some stricter definitions of PAC learning algorithms let $m$ only depend on
$\frac{1}{\delta}$ and $\frac{1}{\epsilon}$. By including $|\mathcal{S}|$,
$s_{E}$ and $s_{Q}$ as parameters of $m$, our definition is more liberal and
we obtain stronger lower bounds. Note that we do not impose any requirements
on the running time of a PAC learning algorithm, and that sample efficiency
only requires the number of examples needed to achieve generalization to be
bounded polynomially, but not the running time. This is because it is known
that there are no polynomial time PAC learning algorithms for CQs unless
RP$=$NP [8, 9].

We remark that sample-efficient PAC learning algorithms exist. In fact, using
a well known connection between PAC learning algorithms and Occam algorithms
[3], one can obtain the following.

######  Theorem 1 ([8]).

Let $\mathbf{A}$ be a fitting algorithm that always produces the smallest
fitting CQ. Then $\mathbf{A}$ is a sample-efficient PAC learning algorithm.

An algorithm of this kind can easily be obtained: enumerate all CQs over
$\mathcal{S}$ in order of increasing size and check for each candidate $q$,
whether it fits the input examples. For some classes of queries, such
algorithms can even be efficiently implemented [7].

###  2.2 Extremal Fittings

Besides minimal size, there are other interesting properties that a fitting CQ
might have. From a logical perspective, fitting CQs stick out that are
_extremal_ in the sense of being most general or most specific among all
fitting CQs. For example, extremal fittings are interesting because the set of
all fitting CQs is convex, meaning that if $q_{1}$ and $q_{2}$ are fitting CQs
and $q_{1}\subseteq q\subseteq q_{2}$, then $q$ is also a fitting CQ. When
they exist, extremal fitting CQs thus characterize the space of all fitting
CQs. They have recently been studied in detail in [5].

Let $E$ be a collection of labeled examples. A CQ $q$ is a

  * •

_most-specific fitting_ CQ for $E$ if $q$ fits $E$ and for every CQ
$q^{\prime}$ that fits $E$, $q\subseteq q$;

  * •

_strongly most-general fitting_ CQ for $E$ if $q$ fits $E$ and for every CQ
$q^{\prime}$ that fits $E$, $q^{\prime}\subseteq q$;

  * •

_weakly most-general fitting_ CQ for $E$ if $q$ fits $E$ and for every CQ
$q^{\prime}$ that fits $E$, $q\subseteq q^{\prime}$ implies $q\equiv
q^{\prime}$.

There is also a more general notion than strongly most-general fitting:

  * •

a finite set of CQs $\\{q_{1},\ldots,q_{n}\\}$ is a _basis of most-general
fitting CQs_ for $E$ if each $q_{i}$ fits $E$ and for all CQs $q^{\prime}$
that fit $E$, we have $q^{\prime}\subseteq q_{i}$ for some $i\leq n$.

Note that the definition of most-specific fitting CQs parallels that of
strongly most-general fitting CQs. One may also define a weak version of most-
specific fitting CQs, but it turns out to be equivalent [5]. The different
notions of most-general fitting CQ are connected as follows. If $q$ is a
strongly most-general fitting CQ, then $\\{q\\}$ is a basis of most-general
fitting CQs. If a basis of most-general fitting CQs is subset minimal, then it
contains only weakly most-general fitting CQs. Furthermore, if a strongly
most-general fitting CQ exists, then it is the only weakly most-general
fitting CQ.

A most-specific fitting CQ $q$ and a basis of most-general fitting CQs
$\\{q_{1},\dots,q_{n}\\}$ completely describe the space of all fitting CQs:
For all CQs $q^{\prime}$, $q\subseteq q^{\prime}$ and $q^{\prime}\subseteq
q_{i}$ for some $i$, if and only if $q^{\prime}$ fits $E$.

Most-specific fitting CQs are closely related to direct products of examples.
The _direct product_ $I\times J$ of two instances $I$ and $J$ is the instance
that consists of all facts $R(\langle a_{1},b_{1}\rangle,\ldots,\langle
a_{n},b_{n}\rangle)$, where $R(a_{1},\ldots,a_{n})$ is a fact in $I$ and
$R(b_{1},\ldots,b_{n})$ is a fact in $J$. The direct product
$(I,\textbf{a})\times(J,\textbf{b})$ of two $k$-ary examples, where
$\textbf{a}=a_{1},\ldots,a_{k}$ and $\textbf{b}=b_{1},\ldots b_{k}$, is
$(I\times J,(\langle a_{1},b_{1}\rangle,\ldots,\langle a_{k},b_{k}\rangle))$.

######  Theorem 2 ([5]).

For all CQs $q$ and collections of labeled examples $E=(E^{+},E^{-})$, the
following are equivalent:

  1. 1.

$q$ is a most-specific fitting CQ for $E$,

  2. 2.

$q$ fits $E$ and is equivalent to the canonical CQ of $\Pi_{e\in E^{+}}(e)$.

Strongly most-general fitting CQs and, more generally, finite bases of most-
general fitting CQs are closely related to _homomorphism dualities_ , a
fundamental concept that originates from combinatorial graph theory and that
has found diverse applications in different areas, including the study of
constraint satisfaction problems, database theory and knowledge
representation. Here, we use a relativized version of homomorphism dualities
introduced in [5].

######  Definition 2.

Let $(J,\mathbf{b})$ be an example. A _homomorphism duality relative to_
$(J,\mathbf{b})$ is a pair of finite sets of examples
$(\mathcal{F},\mathcal{D})$ such that for all examples
$(J^{\prime},\mathbf{b}^{\prime})$ with
$(J^{\prime},\mathbf{b}^{\prime})\to(J,\mathbf{b})$, it holds that
$(I_{f},\mathbf{a}_{f})\to(J^{\prime},\mathbf{b}^{\prime})$ for some
$(I_{f},\mathbf{a}_{f})\in\mathcal{F}$ if and only if
$(J^{\prime},\mathbf{b}^{\prime})\not\to(I_{d},\mathbf{a}_{d})$ for all
$(I_{d},\mathbf{a}_{d})\in\mathcal{D}$.

######  Theorem 3 ([5]).

For all CQs $q_{1},\ldots,q_{n}$ and collections of labeled examples $E$, the
following are equivalent:

  1. 1.

$\\{q_{1},\ldots,q_{n}\\}$ is a basis of most-general fitting CQs for $E$

  2. 2.

each $q_{i}$ fits $E$, and $(\\{e_{q_{1}},\ldots,e_{q_{n}}\\},E^{-})$ is a
homomorphism duality relative to $\Pi_{e\in E^{+}}(e)$.

Or, formulated for strongly most-general fitting CQs: $q$ is a strongly most-
general fitting CQ if and only if $q$ fits $E$ and $(\\{e_{q}\\},E^{-})$ is a
homomorphism duality relative to $\Pi_{e\in E^{+}}(e)$.

##  3 Most-General Fittings Preclude Sample-Efficient PAC Learning

We show that fitting algorithms that always produce a most-general fitting CQ,
if it exists, cannot be sample-efficient PAC learning algorithms. We focus on
strongly most-general fitting CQs since fitting algorithms that always produce
a weakly most-general fitting CQ or the elements of a base of most-general
fitting CQs must also produce a strongly most-general fitting CQ, if it
exists. Consequently, our result also applies to the latter kinds of
algorithms.

The existing similar results in [7] that pertain to tree-shaped CQs rely
heavily on _simulation dualities_ , defined like homomorphism dualities but
using the weaker simulation relation instead of homomorphisms. In fact, [5]
gives a characterization of bases of most-general fitting tree CQs in terms of
simulation dualities instead of homomorphism dualities. Guided by Theorem 3,
we aim to base our proofs on homomorphism dualities instead.

Known constructions of a duality $(\mathcal{F},\mathcal{D})$ from
$\mathcal{F}$ relative to some example $(J,\mathbf{b})$ result in examples
$\mathcal{D}$ that have size exponential in $||\mathcal{F}||$ and $|J|$ [4].
This makes them unsuitable to show non-sample-efficiency as it would force us
to use negative data examples that are exponentially larger than the positive
examples. Since Definition 1 allows the sample size $m$ to depend on the size
of the examples, this would effectively allow a sample-efficient PAC learning
algorithm to use an exponential number of examples. In order to avoid this
effect, we begin by showing that for a certain restricted class of examples
$\mathcal{F}$, a homomorphism duality $(\mathcal{F},\mathcal{D})$ exists such
that $\mathcal{D}$ is of polynomial size (and can be computed in polynomial
time).

A _path instance_ is a database instance $I$ such that the facts in $I$ are of
the form

$R_{1}(a_{0},a_{1}),\dots,R_{n}(a_{n-1},a_{n}),P_{1}(a_{j_{1}}),\dots,P_{m}(a_{j_{m}})$

where all $R_{i}$ are binary relation symbols, all $P_{i}$ are unary relation
symbols and for all $j_{i}$, $j_{i}>0$. A _path example_ $(I,a)$ is a unary
data example where $I$ is a path instance and $a=a_{0}$.

######  Lemma 1.

Let $(I,a_{0})$ and $(J,b_{0})$ be path examples. There exists a data example
$(D,d)$ that can be computed in time polynomial in $|I|$ and $|J|$ such that
$(\\{(I,a_{0})\\},\\{(D,d)\\})$ is a homomorphism duality relative to
$(J,b_{0})$.

###### Proof.

Since $I$ and $J$ are path instances, assume that
$\mathsf{adom}(I)=\\{a_{0},\dots,a_{n}\\}$ and
$\mathsf{adom}(J)=\\{b_{0},\dots b_{m}\\}$. We can check in polynomial time
whether $(I,a_{0})\to(J,b_{0})$. We distinguish cases.

If $(I,a_{0})\not\to(J,b_{0})$, then it follows that
$(I,a_{0})\not\to(J^{\prime},b^{\prime})$ for all data examples
$(J^{\prime},b^{\prime})$ with $(J^{\prime},b^{\prime})\to(J,b_{0})$. Hence,
$(\\{(I,a_{0})\\},\\{(J,b_{0})\\})$ is a homomorphism duality relative to
$(J,b_{0})$.

If $(I,a_{0})\to(J,b_{0})$, we construct a data example $(D,d)$ such that
$(\\{(I,a_{0})\\},\\{(D,d)\\})$ is the desired homomorphism duality relative
to $(J,b_{0})$ as follows. Since $(I,a_{0})\to(J,b_{0})$, it must be that
$n\leq m$ and the binary relation symbol $R_{i}$ is the same in $I$ and $J$
for all $i$ with $1\leq i\leq n$. The values used in $D$ will be pairs
$\langle b_{i},f\rangle$ where $b_{i}\in\mathsf{adom}(J)$ and $f$ is a fact
from $I$ that mentions $a_{i}$ or the dummy fact $\circ$. More specifically,
$\mathsf{adom}(D)$ will be the following set of values:

$\displaystyle\\{\langle b_{i},\circ\rangle\mid i=0\text{ or }n<i\leq
m\\}\cup{}$ $\displaystyle\\{\langle b_{i},R_{i}(a_{i-1},a_{i})\rangle\mid
1\leq i\leq n\\}\cup{}$ $\displaystyle\\{\langle
b_{i},R_{i+1}(a_{i},a_{i+1})\rangle\mid 0\leq i\leq n-1\\}\cup{}$
$\displaystyle\\{\langle b_{i},P(a_{i})\rangle\mid 1\leq i\leq n\text{ and
}P(a_{i})\in I\\}.$

For all values $\langle b_{i},f\rangle,\langle b_{i+1},f^{\prime}\rangle$ in
the above set we add to $D$ the fact

  * •

$R_{i+1}(\langle b_{i},f\rangle,\langle b_{i+1},f^{\prime}\rangle)$ if $f\neq
R_{i+1}(a_{i},a_{i+1})$ or $f^{\prime}\neq R_{i+1}(a_{i},a_{i+1})$,

  * •

$P(\langle b_{i+1},f^{\prime}\rangle)$ if $P(b_{i+1})\in J$ and
$f^{\prime}\neq P(a_{i+1})$.

Then set $d$ to be the value $\langle b_{0},R_{1}(a_{0},a_{1})\rangle$. This
completes the construction of $(D,d)$. Note that every binary fact
$R_{i+1}(\langle b_{i},f\rangle,\langle b_{i+1},f^{\prime}\rangle)$ in $D$ is
a copy of a binary fact $R_{i+1}(b_{i},b_{i+1})$ in $J$. Since
$f,f^{\prime}\in I\cup\\{\circ\\}$, there are at most $(|I|+1)^{2}$ copies of
every binary fact of $J$ in $D$. The same is true for unary facts. Therefore
$|D|\leq|J|\cdot(|I|+1)^{2}$. It is easy to see that $D$ can be computed in
polynomial time using the above construction.

It remains to show that $(\\{(I,a_{0})\\},\\{(D,d)\\})$ is a homomorphism
duality relative to $(J,b_{0})$. First, we show that
$(I,a_{0})\to(J^{\prime},b^{\prime})$ implies
$(J^{\prime},b^{\prime})\not\to(D,d)$ for all examples
$(J^{\prime},b^{\prime})$ with $(J^{\prime},b^{\prime})\to(J,b_{0})$. For
this, it suffices to show that $(I,a_{0})\not\to(D,d)$. Let $I_{k}$ be the
restriction of $I$ to facts that contain only values $a_{i}$ with $i\geq k$.
We show that for all $i$ with $1\leq i\leq n$ and all $\langle
b_{i},f\rangle\in\mathsf{adom}(D)$,

$(I_{i},a_{i})\to(D,\langle b_{i},f\rangle)\quad\text{implies}\quad
f=R_{i}(a_{i-1},a_{i}).$

We show this by induction on $n-i$. In the induction start, let $i=n$. By
construction of $D$, $f\in\\{R_{n}(a_{n-1},a_{n})\\}\cup\\{P(a_{n})\mid
P(a_{n})\in I\\}$. Assume that $(I,a_{n})\to(D,\langle b_{n},f\rangle)$. Then
it follows that $P(\langle b_{n},f\rangle)\in D$ for all $P(a_{n})\in I$,
hence $f\neq P(a_{n})$ for any $P(a_{n})\in I$. Therefore, the only
possibility that remains is that $f=R_{n}(a_{n-1},a_{n})$.

In the induction step, assume that the implication holds for $i+1$ and that
$(I_{i},a_{i})\to(D,\langle b_{i},f\rangle)$. Again, this implies that
$P(\langle b_{i},f\rangle)\in D$ for all $P(a_{i})\in I$, hence
$f\notin\\{P(a_{i})\mid P(a_{i})\in I\\}$. Additionally, from
$(I_{i},a_{i})\to(D,\langle b_{i},f\rangle)$ and $i<n$ it follows that there
must be a fact $R_{i+1}(\langle b_{i},f\rangle,\langle
b_{i+1},f^{\prime}\rangle)\in D$ such that $(I_{i+1},a_{i+1})\to(D,\langle
b_{i+1},f^{\prime}\rangle)$. By the induction hypothesis,
$f^{\prime}=R_{i+1}(a_{i},a_{i+1})$. It follows from $R_{i+1}(\langle
b_{i},f\rangle,\langle b_{i+1},f^{\prime}\rangle)\in D$, that $f\neq
R_{i+1}(a_{i},a_{i+1})$. Therefore, the only possibility that remains is that
$f=R_{i}(a_{i-1},a_{i})$.

From ($*$) and $R_{1}(a_{0},a_{1})\in I$ it now follows that
$(I,a_{0})\not\to(D,\langle b_{0},R_{1}(a_{0},a_{1})\rangle)=(D,d)$, since by
construction of $D$, $R_{1}(\langle b_{0},R_{1}(a_{0},a_{1})\rangle,\langle
b_{1},R_{1}(a_{0},a_{1})\rangle)\notin D$.

Second, we show that $(I,a_{0})\not\to(J^{\prime},b^{\prime})$ implies
$(J^{\prime},b^{\prime})\to(D,d)$ for all examples $(J^{\prime},b^{\prime})$
with $(J^{\prime},b^{\prime})\to(J,b_{0})$. Let $(J^{\prime},b^{\prime})$ be
an example such that $(I,a_{0})\not\to(J^{\prime},b^{\prime})$ and
$(J^{\prime},b^{\prime})\to(J,b_{0})$. Let $h$ be a homomorphism from
$J^{\prime}$ to $J$ with $h(b^{\prime})=b_{0}$. We construct a homomorphism
$g$ from $J^{\prime}$ to $(D,d)$ with $g(b^{\prime})=d$ as follows. For all
$a\in\mathsf{adom}(J^{\prime})$, there is an $i$ such that $0\leq i\leq m$ and
$h(e)=b_{i}$. Define $g(a)$ depending on this $i$ as follows. For $i=0$,

  * •

if $(I_{i},a_{i})\to(J^{\prime},a)$, set $g(a)=\langle b_{0},\circ\rangle$;

  * •

otherwise, that is, if $(I_{i},a_{i})\not\to(J^{\prime},a)$, set $g(a)=\langle
b_{0},R_{1}(a_{0},a_{1})\rangle$.

For $1\leq i\leq n$,

  * •

if $(I_{i},a_{i})\to(J^{\prime},a)$, set $g(a)=\langle
b_{i},R_{i}(a_{i-1},a_{i})\rangle$;

  * •

otherwise, that is, if $(I_{i},a_{i})\not\to(J^{\prime},a)$, we distinguish
cases:

    * –

if there is a $P(a_{i})\in I_{i}$ such that $P(a)\notin J^{\prime}$, set
$g(a)=\langle b_{i},P(a_{i})\rangle$;

    * –

otherwise, set $g(a)=\langle b_{i},R_{i+1}(a_{i},a_{i+1})\rangle$ (note that
in this case $i<n$ and $(I_{i+1},a_{i+1})\not\to(J^{\prime},a^{\prime})$ for
all $R_{i+1}(a,a^{\prime})\in J^{\prime}$).

For $i>n$, set $g(a)=\langle b_{i},\circ\rangle$.

It remains to verify that $g$ is a homomorphism. Let $P(a)$ be a unary fact in
$J^{\prime}$. Since $h$ is a homomorphism, there is a fact $P(b_{i})\in J$
with $h(a)=b_{i}$. By definition of $g$, $g(a)=\langle b_{i},f\rangle$ for
some fact
$f\in\\{\circ,R_{i}(a_{i-1},a_{i}),R_{i+1}(a_{i},a_{i+1})\\}\cup\\{P^{\prime}(a_{i})\in
I\mid P^{\prime}\neq P\\}$. From the construction of $D$ it follows that
$P(g(a))\in D$ for all these cases of $f$.

Let $R(a,a^{\prime})$ be a binary fact in $J^{\prime}$. Since $h$ is a
homomorphism, there is a fact $R(b_{i},b_{i+1})\in J$ with $h(a)=b_{i}$ and
$h(a^{\prime})=b_{i+1}$. The mapping $g$ then maps $a$ to $\langle
b_{i},f\rangle$ and $a^{\prime}$ to $\langle b_{i+1},f^{\prime}\rangle$, for
some facts $f,f^{\prime}\in I\cup\\{\circ\\}$. It follows from the
construction of $D$ that there is an atom $R(\langle b_{i},f\rangle,\langle
b_{i+1},f^{\prime}\rangle)\in D$ for all $f,f^{\prime}$, except for
$f=f^{\prime}=R(a_{i},a_{i+1})\in I$ (and $i+1\leq n$). Assume for
contradiction that there is an atom $R(a_{i},a_{i+1})\in I$ and
$f=f^{\prime}=R(a_{i},a_{i+1})$. By definition of $g$ and $f=R(a_{i},a_{i+1})$
it follows that there is no fact $R(a,a^{\prime\prime})\in J^{\prime}$ with
$(I_{i+1},a_{i+1})\to(J^{\prime},a^{\prime\prime})$, and it follows from
definition of $g$ and $f^{\prime}=R(a_{i},a_{i+1})$ that
$(I_{i+1},a_{i+1})\to(J^{\prime},a^{\prime})$. A contradiction, since
$R(a,a^{\prime})\in J^{\prime}$. ∎

${I_{q}}$${D_{q}}$${I_{q_{T}}}$${{y_{0}}}$ ${{\langle
x_{0},R(y_{0},y_{1})\rangle}}$${{\langle x_{0},\circ\rangle}}$
${{x_{0}}}$${{y_{1}}}$${A}$${{\langle
x_{1},R(y_{1},y_{2})\rangle}}$${A,B}$${{\langle
x_{1},A(y_{1})\rangle}}$${B}$${{\langle
x_{1},R(y_{0},y_{1})\rangle}}$${A,B}$${{x_{1}}}$${A,B}$${{y_{2}}}$${B}$${{\langle
x_{2},B(y_{2})\rangle}}$${A}$${{\langle
x_{2},R(y_{1},y_{2})\rangle}}$${A,B}$${{x_{2}}}$${A,B}$ Figure 1: The examples
$(I_{q},y_{0})$ and $(I_{q_{T}},x_{0})$ are path examples. The instance
$D_{q}$ is the result of the construction in the proof of Lemma 1. The pair
$(\\{(I_{q},y_{0})\\},\\{(D_{q},\langle x_{0},R(y_{0},y_{1})\rangle)\\})$ is a
homomorphism duality relative to the example $(I_{q_{T}},x_{0})$.

Figure 1 shows an example of the construction employed in the proof of Lemma
1. Note that the result of this construction $D_{q}$ is not itself a path
instance, and not even a tree. In what follows, we use $p$ to refer to a
polynomial function $p\colon\mathbb{N}^{2}\to\mathbb{N}$ that bounds the size
of the data example $(D,d)$, depending on the size of the examples $(I,a_{0})$
and $(J,b_{0})$, constructed according to Lemma 1. We now build on Lemma 1 to
show that algorithms that produce strongly most-general fittings are not
sample-efficient PAC learning algorithms.

######  Theorem 4.

Let $\mathbf{A}$ be a fitting algorithm for CQs that always produces a
strongly most-general fitting, if it exists. Then $\mathbf{A}$ is not a
sample-efficient PAC learning algorithm.

###### Proof.

Assume to the contrary of what we aim to show that there is a sample-efficient
PAC learning algorithm that produces a strongly most-general fitting CQ, if it
exists, with associated polynomial function
$m\colon\mathbb{R}^{2}\times\mathbb{N}^{3}\rightarrow\mathbb{N}$ as in
Definition 1. We assume that the value of $m$ is at least 2, for any input.

Choose a signature $\mathcal{S}$ that contains the unary relation symbols $A$,
$B$ and a binary relation symbol $R$, $\delta=0.5$, $\epsilon=0.25$, and
$n\in\mathbb{N}$ large enough so that
$2^{n-1}>m(\frac{1}{\delta},\frac{1}{\epsilon},|\mathcal{S}|,3n,p(3n,2n))$.
Without loss of generality we assume that $p(3n,2n)\geq 3n$.

As target CQ, we use

$q_{T}(x_{0})\text{ :-
}R(x_{0},x_{1}),A(x_{1}),B(x_{1}),\dots,R(x_{n-1},x_{n}),A(x_{n}),B(x_{n}).$

Thus, $q_{T}$ is an $r$-path of length $n$ in which every non-root node is
labeled with $A$ and $B$. We will use $(I_{q_{T}},x_{0})$ as a positive
example for $q_{T}$. Note that $I_{q_{T}}$ is a path instance with
$|I_{q_{T}}|=3n\leq p(3n,2n)$.

Next, we construct instances that we use as negative examples. Define a set of
CQs

$S=\\{q(y_{0})\text{ :-
}R(y_{0},y_{1}),\alpha_{1}(y_{1}),\dots,R(y_{n-1},y_{n}),\alpha_{n}(y_{n})\mid\alpha_{i}\in\\{A,B\\}\\}.$

The CQs in $S$ resemble $q_{T}$, except that every node is labeled with only
one of the unary relation symbols $A$ and $B$. For all elements $q$ of $S$ it
holds that $q_{T}\subseteq q$ and $I_{q}$ is a path instance with
$|I_{q}|=2n$. In order to obtain the negative examples, we construct for each
$q\in S$, the example $(D_{q},a_{q})$ such that
$(\\{(I_{q},y_{0})\\},\\{(D_{q},a_{q})\\})$ is a homomorphism duality relative
to $(I_{q_{T}},x_{0})$. By definition of $p$, $|D_{q}|\leq p(3n,2n)$. Since
$(I_{q},y_{0})\to(I_{q_{T}},x_{0})$ for all $q\in S$, it follows from the
definition of relativized homomorphism duality that
$(I_{q_{T}},x_{0})\not\to(D_{q},a_{q})$. Hence all $(D_{q},a_{q})$ are
negative examples for $q_{T}$. Figure 1 shows examples of these instances for
$n=2$.

The central properties of the chosen data examples are the following. For
$q_{1},q_{2}\in S$, let $q_{1}\land q_{2}$ denote the unary CQ that joins
$q_{1}$ and $q_{2}$ at the answer variable $y_{0}$, but keeps all existential
variables distinct. For $S^{\prime}\subseteq S$, let
$q_{S^{\prime}}=\bigwedge_{q\in S}q$.

Claim. For every $S^{\prime}\subseteq S$,
$(\\{(I_{q_{S^{\prime}}},y_{0})\\},\\{(D_{q},a_{q})\mid q\in S^{\prime}\\})$
is a homomorphism duality relative to $(I_{q_{T}},x_{0})$.

Proof of claim. Let $S^{\prime}$ be a subset of $S$. Using the definition of
homomorphism duality, we have to show that for all data examples $(I,a)$ with
$(I,a)\to(I_{q_{T}},x_{0})$, it holds that
$(I_{q_{S^{\prime}}},y_{0})\to(I,a)$ if and only if
$(I,a)\not\to(D_{q},a_{q})$ for all $q\in S^{\prime}$.

Let $(I,a)$ be an example such that $(I,a)\to(I_{q_{T}},x_{0})$. First, we
show that $(I_{q_{S}^{\prime}},y_{0})\to(I,a)$ implies that
$(I,a)\not\to(D_{q},a_{q})$ for all $q\in S^{\prime}$. So assume that
$(I_{q_{S}^{\prime}},y_{0})\to(I,a)$. It suffices to show that
$(I_{q_{S^{\prime}}},y_{0})\not\to(D_{q},a_{q})$ for all $q\in S^{\prime}$.
Take any $q\in S^{\prime}$. Since $(\\{(I_{q},y_{0})\\},\\{(D_{q},a_{q})\\})$
is a homomorphism duality relative to $(I_{q_{T}},x_{0})$ and
$(I_{q},y_{0})\to(I_{q_{T}},x_{0})$, we have
$(I_{q},y_{0})\not\to(D_{q},a_{q})$. By construction of $q_{S^{\prime}}$, this
implies $(I_{q_{S^{\prime}}},y_{0})\not\to(D_{q},a_{q})$.

Next, we show that $(I_{q_{S}^{\prime}},y_{0})\not\to(I,a)$ implies that there
is a $q\in S^{\prime}$ such that $(I,a)\to(D_{q},a_{1})$. Since
$I_{q_{S^{\prime}}}$ is the join of all $I_{q}$ with $q\in S^{\prime}$ as the
answer variable, there must be a $q\in S^{\prime}$ such that
$(I_{q},y_{0})\not\to(I,a)$. By definition of homomorphism dualities therefore
$(I,a)\to(D_{q},a_{q})$, as required. This completes the proof of the claim.

Let the probability distribution $P$ assign probability $\frac{1}{2}$ to the
positive example $(I_{q_{T}},x_{0})$, probability $\frac{1}{2^{n+1}}$ to all
negative examples $(D_{q},a_{q})$, $q\in S$, and probability $0$ to all other
data examples. Now assume that the algorithm is started on a collection of
$m(\frac{1}{\delta},\frac{1}{\epsilon},|\mathcal{S}|,3n,p(3n,2n))$ data
examples $E=(E^{+},E^{-})$ drawn according to $P$ and labeled according to
$q_{T}$. Let $S^{\prime}=\\{q\in S\mid(D_{q},a_{q})\in E^{-}\\}\subseteq S$.
We argue that $q_{S^{\prime}}$ fits $E$. Since
$(I_{q},y_{0})\to(I_{q_{T}},x_{0})$ for all $q\in S$, it follows that
$q_{S^{\prime}}$ fits the positive examples in $E$ which are all of the form
$(I_{q_{T}},x_{0})$. Now let $(D_{q},a_{q})$ be a negative example in $E$. We
have $(I_{q},y_{0})\not\to(D_{q},a_{q})$ by the properties of homomorphism
dualities and by construction of $q_{S^{\prime}}$ it follows that
$q_{S^{\prime}}\not\to(D_{q},a_{q})$, as required.

We next observe that if $(I_{q_{T}},x_{0})\in E^{+}$, then it follows from
Theorem 3 and the claim that $q_{S^{\prime}}$ is a strongly most-general
fitting of $E$. Hence, with probability $1-\frac{1}{2^{|E|}}>1-\delta$ (since
the value of $m$ and thus $|E|$ is at least 2), the algorithm $\mathbf{A}$
returns a CQ equivalent to $q_{S^{\prime}}$.

We argue that $q_{S^{\prime}}$ classifies all negative examples
$(D_{q},a_{q})$ with $q\in S\setminus S^{\prime}$ incorrectly. To see this,
let $q$ be a CQ from $S\setminus S^{\prime}$. Note that
$(I_{q},y_{0})\not\to(I_{q_{S^{\prime}}},y_{0})$ by construction of
$q_{S^{\prime}}$. Then, it follows from
$(\\{(I_{q},y_{0})\\},\\{D_{q},a_{q}\\})$ being a homomorphism duality
relative to $(I_{q_{T}},x_{0})$ and
$(I_{q_{S^{\prime}}},y_{0})\to(I_{q_{T}},a_{q_{T}})$ that
$(I_{q_{S^{\prime}}},y_{0})\to(D_{q},a_{q})$. Therefore all $(D_{q},a_{q})$
with $q\in S\setminus S^{\prime}$ are positive examples for $q_{S^{\prime}}$.

Since $|S\setminus S^{\prime}|=2^{n}-|S^{\prime}|>2^{n}-2^{n-1}$ by choice of
$n$ and each of the negative examples $(D_{q},a_{q})$ with $q\in S\setminus
S^{\prime}$ has probability $\frac{1}{2^{n+1}}$ to be drawn from $P$, we have
$\mathsf{error}_{P,q_{T}}(q_{S^{\prime}})>\frac{2^{n}-2^{n-1}}{2^{n+1}}=1/4=\epsilon$,
a contradiction. ∎

##  4 Most-Specific Fittings Preclude Sample-Efficient PAC Learning

We show that fitting algorithms that always produce a most-specific fitting CQ
cannot be sample-efficient PAC learning algorithms. Note that a most-specific
fitting CQ is always guaranteed to exist provided that a fitting CQ exists at
all [5]. The proof of the following result is a refinement of a similar proof
given in [7] for tree-shaped CQs.

######  Theorem 5.

Let $\mathbf{A}$ be a fitting algorithm for CQs that always produces a most-
specific fitting CQ. Then $\mathbf{A}$ is not a sample-efficient PAC learning
algorithm.

###### Proof.

Assume to the contrary of what we aim to show that $\mathbf{A}$ is a sample-
efficient PAC learning algorithm with associated polynomial function
$m\colon\mathbb{R}^{2}\times\mathbb{N}^{3}\rightarrow\mathbb{N}$ as in
Definition 1. Choose a schema $\mathcal{S}$ that contains a unary relation
symbol $A$ and a binary relation symbol $R$, set $q_{T}(x_{0})\text{ :-
}A(x_{0})$, $\delta=\epsilon=0.5$, and $n$ even and large enough such that

$\frac{1}{2}\binom{n}{n/2}>m\left(\frac{1}{\epsilon},\frac{1}{\delta},|\mathcal{S}|,1,p(2n,2n)+1\right).$

We next construct positive examples for $q_{T}$; negative examples are not
used. Let $N$ denote the set of subsets of $\\{1,\dots,n\\}$ and let
$N^{\frac{1}{2}}$ be defined likewise, but include only sets of cardinality
exactly $n/2$. With every $S\in N$, we associate the path instance

$I_{S}=\\{R(b_{0},b_{1}),\dots,R(b_{n-1},b_{n})\\}\cup\\{A(b_{i})\mid i\in
S\\}.$

as well as the example $(I^{\prime}_{S},a_{0})$ that can be obtained by
constructing an example $(J_{S},a_{0})$ such that
$(\\{(I_{S},b_{0})\\},\\{(J_{S},a_{0})\\})$ is a homomorphism duality relative
to $(I_{\\{1,\dots,n\\}},b_{0})$ via the construction in the proof of Lemma 1
and then adding the fact $A(a_{0})$. Due to this additional fact, every
$(I^{\prime}_{S},a_{0})$ is a positive data example for $q_{T}$ with
$|I^{\prime}_{S}|\leq p(2n,2n)+1$.

Let $P$ be the probability distribution that assigns probability
$1/|N^{\frac{1}{2}}|$ to every $(I^{\prime}_{S},a_{0})$ with $S\in
N^{\frac{1}{2}}$, and probability $0$ to all other examples. Now assume that
$\mathbf{A}$ is started on a collection of
$m(\frac{1}{\epsilon},\frac{1}{\delta},|\mathcal{S}|,1,p(2n,2n)+1)$ data
examples $E$ drawn from $P$ and labeled according to $q_{T}$, and let $q_{H}$
be the CQ that is output by $\mathbf{A}$. Since $E$ contains no negative
examples, Theorem 2 implies that a most-specific fitting CQ exists. By the
properties of $\mathbf{A}$, $q_{H}$ must therefore be be a most-specific CQ
that fits $E$.

We argue that $q_{H}$ labels all data examples $(I^{\prime}_{S},a_{0})$ with
$S\in N^{\frac{1}{2}}$ that are not in the sample $E$ incorrectly. Let $S$ be
any element of $N^{\frac{1}{2}}$ with $(I^{\prime}_{S},a_{0})\notin E$. We aim
to show that $(I_{q_{H}},a_{q_{H}})\not\to(I^{\prime}_{S},a_{0})$. Let $q_{S}$
be the canonical CQ of $(I_{S},b_{0})$. Since
$(\\{(I_{S},b_{0})\\},\\{(J,a_{0})\\})$ is a homomorphism duality relative to
$(I_{1,\dots,n},b_{0})$, and $I^{\prime}_{S}=J\cup\\{A(a_{0})\\}$,
$(I_{S},b_{0})\not\to(I^{\prime}_{S},a_{0})$. Hence, it suffices to show that
$(I_{S},b_{0})\to(I_{q_{H}},a_{q_{H}})$ or equivalently that $q_{H}\subseteq
q_{S}$.

Recall that $q_{H}$ is a most-specific fitting for $E$. Hence, it suffices to
show that $q_{S}$ is a fitting for $E$. Let $S^{\prime}$ be any element of
$N^{\frac{1}{2}}$ with $(I^{\prime}_{S^{\prime}},a_{0})\in E$. Then $S\neq
S^{\prime}$ and thus $(I_{S^{\prime}},b_{0})\not\to(I_{S},b_{0})$ by
construction. Since $(I_{S},b_{0})\to(I_{\\{1,\dots,n\\}},b_{0})$ and
$(\\{(I_{S^{\prime}},b_{0})\\},\\{(J_{S^{\prime}},a_{0})\\})$ is a
homomorphism duality relative to $(I_{\\{1,\dots n\\}},b_{0})$, it follows
that $(I_{S},b_{0})\to(J_{S^{\prime}},a_{0})$ and hence
$(I_{S},b_{0})\to(I^{\prime}_{S^{\prime}},a_{0})$. Therefore
$(I^{\prime}_{S^{\prime}},a_{0})$ is a positive example for $q_{S}$ and we are
done.

The definition of $P$ and the choice of $n$ now yield that with probability
$1>1-\delta$,

$\mathsf{error}_{P,q_{T}}(q_{H})=\frac{|N^{\frac{1}{2}}|-|E|}{|N^{\frac{1}{2}}|}>0.5,$

a contradiction. ∎

## References

  * [1] Martin Anthony and Norman Biggs.  Computational Learning Theory.  Cambridge University Press, 1992.
  * [2] Pablo Barceló and Miguel Romero.  The complexity of reverse engineering problems for conjunctive queries.  In Proc. of ICDT, pages 7:1–7:17, 2017.
  * [3] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth.  Learnability and the Vapnik-Chervonenkis dimension.  J. ACM, 36(4):929–965, 1989.
  * [4] Balder  ten Cate and Victor Dalmau.  Conjunctive queries: Unique characterizations and exact learnability.  ACM Trans. Database Syst., 47(4):14:1–14:41, 2022.
  * [5] Balder  ten Cate, Victor Dalmau, Maurice Funk, and Carsten Lutz.  Extremal fitting problems for conjunctive queries.  In Proc. of PODS, 2023.
  * [6] Balder  ten Cate, Maurice Funk, Jean Christoph Jung, and Carsten Lutz.  Fitting algorithms for conjunctive queries.  SIGMOD Rec. to appear.
  * [7] Balder  ten Cate, Maurice Funk, Jean Christoph Jung, and Carsten Lutz.  SAT-based PAC learning of description logic concepts.  In Proc. IJCAI, pages 3347–3355, 2023.
  * [8] Balder  ten Cate, Maurice Funk, Jean Christoph Jung, and Carsten Lutz.  On the non-efficient PAC learnability of conjunctive queries.  Inf. Process. Lett., 183:106431, 2024.
  * [9] Jörg-Uwe Kietz.  Some lower bounds for the computational complexity of inductive logic programming.  In Proc. of ECML, pages 115–123. Springer, 1993.
  * [10] Hao Li, Chee-Yong Chan, and David Maier.  Query from examples: An iterative, data-driven approach to query construction.  Proc. VLDB Endow., 8(13):2158–2169, 2015.
  * [11] Quoc Trung Tran, Chee-Yong Chan, and Srinivasan Parthasarathy.  Query reverse engineering.  The VLDB Journal, 23(5):721–746, 2014.
  * [12] Leslie G. Valiant.  A theory of the learnable.  Commun. ACM, 27:1134–1142, 1984.
  * [13] Moshé M. Zloof.  Query by example.  In Proc. of AFIPS NCC, pages 431–438. AFIPS Press, May 1975.


# Word Embeddings as Statistical Estimators

Neil Dey<EMAIL_ADDRESS>
Department of Statistics
North Carolina State University Matthew Singer<EMAIL_ADDRESS>
Department of Statistics
North Carolina State University Jonathan P. Williams<EMAIL_ADDRESS>
Department of Statistics, North Carolina State University
Centre for Advanced Study, Norwegian Academy of Science and Letters Srijan
Sengupta<EMAIL_ADDRESS>
Department of Statistics
North Carolina State University

###### Abstract

Word embeddings are a fundamental tool in natural language processing.
Currently, word embedding methods are evaluated on the basis of empirical
performance on benchmark data sets, and there is a lack of rigorous
understanding of their theoretical properties. This paper studies word
embeddings from a statistical theoretical perspective, which is essential for
formal inference and uncertainty quantification. We propose a copula-based
statistical model for text data and show that under this model, the now-
classical Word2Vec method can be interpreted as a statistical estimation
method for estimating the theoretical pointwise mutual information (PMI).
Next, by building on the work of Levy & Goldberg (2014), we develop a missing
value-based estimator as a statistically tractable and interpretable
alternative to the Word2Vec approach. The estimation error of this estimator
is comparable to Word2Vec and improves upon the truncation-based method
proposed by Levy & Goldberg (2014). The proposed estimator also performs
comparably to Word2Vec in a benchmark sentiment analysis task on the IMDb
Movie Reviews data set.

##  1 Introduction

In natural language processing (NLP), the notion and construction of an
embedding (i.e., a mapping of a linguistic object such as a word, phrase,
sentence, or an entire document to a vector in Euclidean space) is the
essential link for making precise the features of language that we hope to
learn or understand with statistical or machine learning tools. Word
embeddings, arguably introduced in Deerwester et al. (1990), have grown
greatly in popularity since their utility in downstream tasks was demonstrated
by Collobert & Weston (2008). Specifically, the Word2Vec algorithm (Mikolov et
al., 2013) greatly influenced the use of word embeddings by providing a fast
and effective unsupervised approach to constructing word embeddings. This was
quickly followed by the GloVe algorithm (Pennington et al., 2014), which had
performance comparable to Word2Vec. More modern deep learning word embedding
algorithms, such as ELMo (Peters et al., 2018), BERT (Devlin et al., 2019),
and GPT-3 (Brown et al., 2020), have further pushed the performance of word
embeddings to state-of-the-art levels on a variety of downstream tasks such as
masked language modeling, part-of-speech tagging, analogy completion, and text
generation. Though these powerful techniques have already demonstrated far-
reaching societal impacts, it remains important to understand the nature of
the embeddings that underlie their success.

All the aforementioned embedding techniques employ some strategy to generate
word embeddings from a corpus based on some intuited feature of natural
language, theoretically giving the word embeddings relational meaning. Some
examples of such strategies include the order of words in a sentence, how
often pairs of words appear near one another, and the number of times certain
words occur in various documents. However, embeddings are not ultimately
evaluated on how well they represent the intuited features of natural language
that they are designed to learn—NLP algorithms are typically only judged by
their success on downstream tasks. In fact, due to a lack of any precise
mathematical formulation of theoretical features that govern the meaning of
natural language, it is not clear that embeddings have any significance beyond
auxiliary data features that are useful for training NLP models on downstream
tasks (such as those tested by the GLUE benchmark of Wang et al., 2019,
evaluating on sentiment classification, semantic equivalence evaluation, text
similarity evaluation, and recognition of textual entailment, among others).

We argue that to begin to understand the natural language features that
embeddings represent, we must first mathematically formalize the precise
features of natural language that we conjecture to make inferences on. Second,
we must be able to generate synthetic natural language data that exhibit the
precise features that have been formulated (i.e., there must exist a
generative model). And third, we must be able to demonstrate theoretical
and/or empirical statistical consistency of estimation procedures designed to
learn the features. Without any understanding of how natural language can be
generated, attempting to gain insight into learned features—much less gain
statistical guarantees on estimation properties for “true" underlying
linguistic features—is hopeless.

The contributions of our paper are as follows:

  * •

We consider a theoretical formulation of the skip-gram algorithm used for
training unsupervised word embeddings, as in Word2Vec. It is established in
Levy & Goldberg (2014) that the skip-gram algorithm minimizes its loss
function at the pointwise mutual information (PMI), but the statistical
properties of the estimated embedding features are not investigated. We
investigate the statistical properties via simulation studies by proposing a
copula-based statistical model for natural language data that truly has a
given PMI matrix as a feature of the generative model.

  * •

We provide a solution to the problem of constructing a singular value
decomposition (SVD) of the PMI matrix from real natural language text data,
which exhibits many infinite-valued components. Levy & Goldberg (2014) propose
ad hoc truncation rules, but we adapt recent developments in missing values
SVD (MVSVD) algorithms that rely on expectation-maximization (EM) based
imputation and estimation for matrices with missing components. Moreover, the
right and left singular vectors resulting from the SVD of a PMI matrix can be
used as embedding vectors with comparable meaning to the embedding vectors
trained from the skip-gram algorithm and with similar performance in training
on downstream tasks but with improved interpretability. This is implicit in
the fact that matrix decompositions such as SVD are relatively well-understood
mathematically, unlike unsupervised learning algorithms.

  * •

The copula-based statistical model that we propose is motivated by linguistic
literature on theoretical distributional features of data from natural
language, namely that ordered word frequencies in text corpora are often
Zipfian distributed. We illustrate that it is possible to build generative
models for natural language data that can be used to study theoretical
features not limited to the PMI matrix.

  * •

While the construction of embedding vectors in NLP contexts is almost
exclusively driven by training models for optimized performance on downstream
tasks, our work forces the question of whether embedding vectors have inherent
meaningfulness for representing features of natural language.

The organization of our paper is as follows. An overview of existing language
modeling approaches is given in Section 2. This is followed by a brief
discussion of the theoretical properties of the Word2Vec algorithm and our
proposed model for natural language in Section 3. In Section 4, we discuss
various estimators that can act as alternatives to skip-gram embeddings,
examining previously used proposals as well as our new algorithm. Section 5
provides simulation studies to analyze Word2Vec and its alternatives in terms
of their abilities as statistical estimators. Finally, Section 6 presents the
performance of these algorithms on a standard sentiment analysis task to
illustrate that similar behavior as statistical estimators yields similar
performance in downstream tasks. The code to reproduce the results of this
paper can be found at https://github.com/neil-dey/word-embeddings-as-
estimators.

##  2 Existing Studies

The analysis of text data and word embeddings are largely an unexplored avenue
of research in the statistics literature. There do, however, exist papers in
the statistics literature on the related topics of sentiment analysis (Taddy,
2013; Wang et al., 2016), topic modeling (Airoldi & Bischof, 2016; Li et al.,
2021; Chen et al., 2022; Wu et al., 2022), and text classification (Zhou et
al., 2016; Xia et al., 2021).

Previous studies in the statistics and linguistics literature more closely
related to our work include the following. In (Dai et al., 2022b), an approach
is proposed for sentence generation in next-word prediction, and it is shown
that the generation error can be sufficiently well estimated. Recently, Dai et
al. developed and proposed a concept of U-minimal sufficient embeddings, a
class of embeddings that minimizes a predefined U-embedding loss. They then
provide a theory determining when U-minimal sufficient embeddings can be
recovered from text Dai et al. (2022a). Related to our direct application,
work by Yan & Bien (2021) demonstrates how the sparsity of a co-occurrence
matrix can be reduced by grouping rare words together in aggregate features.
However, their technique assumes additional side information which encodes
word similarity, namely a hierarchical clustering of GloVe embeddings. If our
generative models were to reduce their complexity using such a technique, we
would most likely require the side information used in comparing semantic
similarity not to be generated from an arbitrary embedding. Finally, word
embeddings were recently extended in Feng et al. (2022) to include information
regarding grammar patterns. They additionally argued that multi-word patterns
follow a Zipfian distribution, and pattern lengths are inversely related to
their frequency. The commonality of both text and language patterns following
Zipfian distributions allows for an easy extension of our copula text
generation procedure to include identified multi-word phrases.

A great deal more work has been done beyond the scope of the statistics and
linguistics literature in the area of natural language generation and language
modeling. A standard model for text generation is the $n$-gram model, in which
words are generated using an $n$th order Markov chain. These $n$-gram models
are popular due to their simple nature allowing for ease of statistical
analysis; however, a naive $n$-gram model, creating transition probabilities
by using observed frequencies from a training corpus, often fails to capture
desirable linguistic features. To remedy this limitation, a variety of methods
have been proposed. A common approach to creating more sophisticated $n$-gram
models is smoothing—adjusting maximum likelihood estimates for probabilities
by making the distribution of word occurrence probabilities more uniform (Chen
& Goodman, 1999). Examples include Good-Turing estimation (Good, 1953),
Jelinek-Mercer smoothing (Jelinek & Mercer, 1980; Brown et al., 1992a), and
Bayesian smoothing (Nádas, 1984; MacKay & Bauman Peto, 1995), among others.
However, most attempts at smoothing still fail to take into account how
similar words occur in similar contexts; class-based $n$-gram models (Brown et
al., 1992b) address this by separating words into distinct classes based on
the frequency of co-occurrence with other words. The primary limitation of
such an approach is in the difficulties encountered when words can have
disparate meanings and appear in wildly different contexts.

Other approaches more sophisticated than the $n$-gram model also exist. Neural
network approaches to language modeling, such as those inspired by Bengio et
al. (2003), address many of these issues and perform admirably in generating
reasonably likely text (as measured in Bengio et al. (2003) by the perplexity
metric). However, jumping to neural networks again decreases the
interpretability of the model and makes proving theoretical results difficult.
Another approach is found in the log-linear models of Mnih & Hinton (2008) and
Arora et al. (2016). These models do provide sophisticated statistical models
for language that yield interesting theoretical results but are tailored to
capturing specific linguistic features and do not generalize easily to
multiple features.

##  3 Statistical Framework

###  3.1 Word2Vec and Pointwise Mutual Information

Given a training corpus, Levy & Goldberg (2014) proved that the Word2Vec
algorithm, using a skip-gram algorithm with one negative sample, implicitly
factors the empirical PMI matrix, given by

$\operatorname{PMI}(w,c)=\log\frac{\Pr(w,c)}{\Pr(w)\Pr(c)}$

where $w$ and $c$ together form a word-context pair, $\Pr(w,c)$ is the
probability of drawing $(w,c)$ as a word-context pair from the corpus, and
$\Pr(w)$ and $\Pr(c)$ are the probabilities of drawing $w$ and $c$
respectively from the corpus. That is, Word2Vec generates a matrix $W$ of word
embeddings and a matrix $C$ of context embeddings, and its objective function
attains a global maximum when $W$ and $C$ are such that
$WC^{\top}=\text{PMI}$. More generally, Word2Vec with $k$ negative samples
factors the empirical Shifted PMI (SPMI) matrix

$\operatorname{SPMI}=\operatorname{PMI}-\log(k)\cdot{\bf\it J}$

where ${\bf\it J}$ is the all-ones matrix. Note that neither the empirical PMI
nor SPMI matrix is guaranteed to have only finite entries. In a finite corpus,
most words do not co-occur with each other, leading to $\Pr(w,c)=0$ for any
such non-co-occurring pair and hence $\log\Pr(w,c)=-\infty$. The presence of
many $-\infty$ entries in the empirical PMI matrix limits the mathematical and
statistical techniques that can be used to interpret the matrix directly, as
most linear algebra techniques require the entries of a matrix to come from a
ring or field, but $\mathbb{R}\cup\\{\pm\infty\\}$ fails to even form a
semigroup. Thus, a mathematical analysis of the PMI matrix and Word2Vec will
require a deeper understanding of these infinite entries.

###  3.2 Two Settings for Natural Language Modeling

We identify two mutually exclusive possibilities for the nature of a language
that produces infinite entries for an empirical PMI matrix: a sparse setting
and a dense setting. In both settings, we interpret the observed corpus as a
sample which is obtained from a hypothetical, infinite population of text
data. This population-sample framework is a fundamental building block of
statistical reasoning. In any statistical inference problem, the goal is to
learn something about the population, e.g., the population mean. However, it
is impossible to actually observe the entire population, so we use the
statistical sample as a representative and finite subset of the population on
which calculations can be carried out in a feasible manner, e.g., computing
the sample mean. We then use the sample metric as an estimate of the unknown
population metric of interest.

We now carry this intuition to text data and, more specifically, co-occurrence
and PMI, under sparse and dense settings. In practice, the sample co-
occurrence matrix, i.e., the co-occurrence matrix computed from the observed
corpus, is almost always sparse, with most of its entries being zero. This
implies that the corresponding terms of the PMI matrix are $-\infty$. However,
this does not necessarily mean that the population version of the co-
occurrence matrix and the PMI matrix suffers from the same issues.

In the sparse setting, there do indeed occur words (say $w$ and $c$) that
never appear in the same context in the population itself; therefore, any
corpus will have an infinite entry for $(w,c)$ in its corresponding empirical
PMI matrix. On the other hand, the dense setting allows for any two words to
appear with each other in some context in the population (though this context
may be very rarely seen); thus, for any two words, there is a positive
probability of their co-occurrence. In other words, there is a corpus that
contains a finite entry in the empirical PMI matrix for the word-context pair.
Note that even under the dense setting, we are likely to observe many zero
entries in the observed co-occurrence matrix since the sample might not be
large enough for observed frequencies to be non-zero even though the
underlying probabilities are.

Both of these settings have an underlying notion of the “truth" of the
language that Word2Vec intends to train on. However, discussing “truth" in a
statistical sense is hard, if not impossible, without any understanding of how
the data itself is generated. Indeed, the lack of a data-generating model for
NLP data contributes to the need for the use of performance on downstream
tasks for various NLP methods. To draw an analogy, suppose that a new method
for regression was proposed. Rather than measuring the efficacy of this new
method using downstream tasks, the designers could either directly prove
results or at least test the method using simulated data
$(X_{i},Y_{i})_{i=1}^{n}$ from $Y_{i}=f(X_{i})+\varepsilon_{i}$ for some
function $f$, covariates $X$, and random errors $\varepsilon_{i}$ from some
distribution. With a data-generating model for natural language, we can
proceed similarly with NLP methods.

Thus, choose some data-generating model for natural language. Then in the
dense setting, the sparsity (in the sense of having many infinite entries) of
the empirical PMI is an artifact of sampling from the model rather than a
consequence of theoretical sparsity. On the other hand, in the sparse setting,
sparsity is an inherent attribute of language (i.e. the data-generating model)
itself. A mathematically rigorous definition of these two settings is provided
in Section 3.3.

Under a sparse model, many traditional mathematical approaches to interpreting
the PMI are fruitless, since infinite entries are inherent to the data itself:
There necessarily exists a pair $(w,c)$ such that $\Pr(w,c)=0$, and thus
$\log\Pr(w,c)=-\infty$ in both the population and empirical PMI matrix.
Indeed, the objective function of Word2Vec itself (without normalization of
word and context vectors) would require these words to have infinitely large
dot products with each other, so even direct analysis of the algorithm proves
difficult. It is due to these complications that the remainder of this paper
primarily focuses on a dense model for language.

###  3.3 A Text Generation Framework

In light of the need for a data-generating model for natural language, we
provide the following theoretical framework: Let $\mathscr{C}$ be an infinite
sequence of tokens given by $(t_{i})_{i=-\infty}^{\infty}$. We assume that
$\mathscr{C}$ is “stationary" in the sense that any corpus (i.e. a finite
substring from $\mathscr{C}$) we draw would form a representative
sample—compare this to a non-stationary $\mathscr{C}$ that adjoins a fantasy
textbook with a medical textbook, where which section of $\mathscr{C}$ we draw
from to sample a corpus would matter. This is inspired by the statistical
framework of time series analysis, where the observed data is assumed to be a
finite, continuous subset of an infinite temporal sequence. Every finite
sequence of tokens can be assigned some probability of occurrence based on
their frequency in $\mathscr{C}$; the $n$-gram model assigns the probability
of the sequence of tokens $(w_{i})_{i=1}^{m}$ to be

$\Pr(w_{1},\ldots,w_{m})=\prod_{i=1}^{m}\Pr(w_{i}\mid,w_{i-(n-1)},\ldots,w_{i-1}).$

Hence, an $n$th order Markov chain can be used to generate data if the
transition probabilities are specified (e.g. via a transition probability
matrix or tensor); for simplicity, we restrict ourselves in this paper to a
unigram (first order) model. We can thus formally define the notions of dense
and sparse models for language, as discussed in Section 3.2: If the associated
Markov chain is strongly connected, then the language model is dense;
otherwise, it is sparse.

It then still remains to answer the question of how the transition
probabilities should be specified to match the distributional properties of
natural language. A natural distributional property that the model’s
transition probabilities should match is the marginal distribution for word
frequencies (i.e. the probability of occurrence for individual words). It is
well-established that words in the English language tend to follow a Zipfian
distribution with Zipf parameter approximately $1$ (Moreno-Sánchez et al.,
2016). To illustrate this phenomenon, we display the empirical frequencies of
words from the Brown Corpus (Francis & Kucera, 1979) and overlay the expected
frequencies from a Zipfian distribution in Figure 1.

Figure 1: The empirical word frequencies from the Brown Corpus and expected
word frequencies from a $\operatorname{Zipf}(1,V)$ distribution, where
$V\approx 10^{4}$. Infrequent words (with $<10$ occurrences) have been
omitted.

Thus, in a fixed vocabulary of $V$ unique words, the distribution of the word
probabilities should follow a $\operatorname{Zipf}(1,V)$ distribution (though
our methodology can be extended to any distribution). This thus gives us the
marginal distributions for a $V\times V$ word co-occurrence matrix; however,
this does not give all the information necessary to construct the co-
occurrence matrix in its entirety.

The problem of constructing a bivariate distribution when only the marginals
are known is solved using copula distributions. A function
${C:[0,1]^{d}\rightarrow[0,1]}$ is a copula function if it is a joint
cumulative distribution function of a $d$-dimensional random vector on the
unit cube $[0,1]^{d}$ with uniform marginals. With this definition, copulas
are often used in the study of multivariate data. For example, the Fréchet-
Hoeffding Theorem (Schweiser & Sklar, 1983) gives sharp bounds the behavior of
the joint random variables, with the upper bound attained by co-monotone
random variables. Another use of copulas can be found in approximating the
expected value of a response function $g$ applied to a random vector
$(X_{1},\ldots,X_{d})$ (McNeil et al., 2005); one can simulate draws of
$(X_{1},\ldots,X_{d})$ (whose joint distribution may be unknown) by instead
drawing samples $(U_{1},\ldots,U_{d})$ from the (known) copula and then simply
applying the inverse marginal distribution functions to each component,
resulting in i.i.d. samples with the correct joint distribution. Because of
the utility of copulas in studying multivariate data, they have been applied
to a variety of areas, including quantitative finance (Li, 2000; Ibragimov &
Prokhorov, 2017), engineering (Thompson & Kilgore, 2011; Zhang & Singh, 2019),
and medicine (Lapuyade-Lahorgue et al., 2017; Kon & Nikolaev, 2011), among
others.

For our purpose of completing the co-occurrence matrix, the relevant result
from the literature on copulas is Sklar’s Theorem (Sklar, 1959), which states
that every continuous multivariate cumulative distribution function
$F_{{\bf\it X}}(x_{1},\ldots,x_{d})$ can be expressed in terms of its marginal
cdfs $F_{i}(x_{i})$ and a unique copula function $C$:

$F_{{\bf\it X}}(x_{1},\ldots,x_{d})=C(F_{1}(x_{1}),\ldots,F_{d}(x_{d})).$

Though Sklar’s Theorem only holds for continuous distributions, many discrete
multivariate distributions can still be closely approximated using copula
functions. In particular, given Zipfian marginals with a Zipf parameter near
$1$, a Gaussian copula with correlation matrix $R$,

$C_{R}({\bf\it u})=\Phi_{R}(\Phi^{-1}(u_{1}),\Phi^{-1}(u_{2})),$

where $\Phi$ denotes a normal cumulative distribution function, does well
empirically in generating a bivariate Zipfian distribution with the desired
marginal distributions. This thus allows us to construct a dense co-occurrence
matrix, and hence (by normalizing rows to sum to unity) a transition
probability matrix to generate a corpus.

Note that though this data-generating model is limited as-is, it easily
extends to other, more complex situations. The current model simply generates
words via a first-order Markov chain; a straightforward extension would be to
use a higher-order chain. This of course comes at a cost of having to work
with tensors rather than matrices and greatly increases the computational cost
of computing copulas. Another extension would be to use more sophisticated
copulas than the Gaussian copula, allowing for more complex structures in a
language to be replicated in the model; see Ibragimov & Prokhorov (2017) for
an in-depth treatment of appropriate copulas for heavy-tailed distributions
such as the Zipfian distribution. Different copulas also allow for a choice
between the dense and sparse settings referenced in Section 3.2.

##  4 Embedding Algorithms to Estimate the SPMI Matrix

In our theoretical framework introduced in Section 3.3, a corpus is an
observed finite sample from a population of infinite length. In light of this,
the empirical SPMI matrix from a corpus is simply a point estimate for the
SPMI matrix associated to the population. The only reason Word2Vec factors an
empirical SPMI matrix rather than the population SPMI matrix is due to the
limitation of having to train on a finite corpus. Though impossible in
practice, Word2Vec would ideally factor the population SPMI matrix, as this
would allow for the most generally applicable word embeddings. Thus, in order
to theoretically understand Word2Vec, we need methods that are easier to
analyze mathematically but still approximate Word2Vec in its ability to
implicitly factor the population SPMI matrix as well as in its performance on
downstream tasks.

###  4.1 Truncating the SPMI

As stated in section 3.1, the objective function of Word2Vec with $k$ negative
samples aims to find matrices $W$ and $C$ such that $WC^{\top}=\text{SPMI}$.
Hence, one can bypass the need to perform the Word2Vec algorithm by directly
factorizing the empirical SPMI matrix; the simplest way to do so would be to
use singular value decomposition (SVD) on the matrix

$\operatorname{SPMI}=U\Sigma V^{\top}$

and use $U\Sigma^{1/2}$ and $V\Sigma^{1/2}$ as our word and context embeddings
respectively. However, the infinite entries of the empirical PMI matrix
prevent SVD from being used directly.

To circumvent the problem of the infinite entries of the empirical SPMI
matrix, Levy & Goldberg (2014) instead perform SVD on the empirical positive
SPMI (SPPMI) matrix

$\operatorname{SPPMI}(w,c)=\max(\operatorname{SPMI}(w,c),0)$

which truncates all negative entries to $0$. Though the SPPMI metric is shown
to perform well empirically on semantic similarity tasks, it has the
significant downside of “throwing away" a large amount of data regarding
negative associations. Indeed, Table 2 of Levy & Goldberg (2014) illustrates
that as the number of negative entries increases (e.g. via an increase in
negative sampling for the Word2Vec procedure), performance of SVD on the SPPMI
generally decreases. Similarly, Table 1 of Levy & Goldberg (2014) demonstrates
that as the number of negative entries increases, SVD of the SPPMI matrix
continues to deviate further from the empirical PMI. Thus, a better approach
to dealing with missing co-occurrence frequencies is necessary.

###  4.2 Missing Values SVD

In the dense setting, it makes sense to look into MVSVD algorithms in order to
work around the sparsity of the empirical PMI matrix. Several such algorithms
are presented in Kurucz et al. (2007). One particular algorithm, yielding an
EM approach to MVSVD, is shown in Algorithm 1. This algorithm essentially
imputes missing values by minimizing the Frobenius norm between the imputed
matrix and the given matrix with missing values on the non-missing values.

Algorithm 1 EM-MVSVD Algorithm from Kurucz et al. (2007)

$W$, a matrix with missing values

$d$, the number of singular values to keep

$R\leftarrow\\{(i,j)\mid W_{ij}\text{ is missing}\\}$

for $(i,j)\in R$ do

$W_{ij}\leftarrow$ initial guess

end for

$U,\Sigma,V^{\top}\leftarrow\operatorname{SVD}(W,d)$

$\widehat{W}^{(0)}\leftarrow U\Sigma V^{\top}$

for $(i,j)\in R$ do

$W_{ij}\leftarrow\widehat{W}^{(0)}_{ij}$

end for

for $t=1,2,3,\ldots$ do

if converged then

return $U$, $\Sigma$, $V^{\top}$

end if

$U,\Sigma,V^{\top}\leftarrow\operatorname{SVD}(W,d)$

$\widehat{W}\leftarrow U\Sigma V^{\top}$

$\lambda\leftarrow\arg\,\min\sum\limits_{(i,j)\not\in
R}\quantity[W_{ij}-(\lambda\cdot\widehat{W}_{ij}+(1-\lambda)\cdot\widehat{W}^{(t-1)}_{ij})]^{2}$

$\widehat{W}^{(t)}\leftarrow\lambda\cdot\widehat{W}+(1-\lambda)\cdot\widehat{W}^{(t-1)}$

for $(i,j)\in R$ do

$W_{ij}\leftarrow W^{(t)}_{ij}$

end for

end for

Algorithm 2 DD-MVSVD Algorithm

$W$, a matrix with missing values

$\widetilde{W}$, a matrix approximating the “true" matrix from a distribution

$d$, the number of singular values to keep

$R\leftarrow\\{(i,j)\mid W_{ij}\text{ is missing}\\}$

for $(i,j)\in R$ do

$W_{ij}\leftarrow$ initial guess

end for

$U,\Sigma,V^{\top}\leftarrow\operatorname{SVD}(W,d)$

$\widehat{W}^{(0)}\leftarrow U\Sigma V^{\top}$

for $(i,j)\in R$ do

$W_{ij}\leftarrow\widehat{W}^{(0)}_{ij}$

end for

for $t=1,2,3,\ldots$ do

if converged then

return $U$, $\Sigma$, $V^{\top}$

end if

$U,\Sigma,V^{\top}\leftarrow\operatorname{SVD}(W,d)$

$\widehat{W}\leftarrow U\Sigma V^{\top}$

$\lambda\leftarrow\arg\,\min\sum\limits_{(i,j)\not\in
R}\frac{\quantity[\widetilde{W}_{ij}-(\lambda\cdot\widehat{W}+(1-\lambda)\cdot\widehat{W}^{(t-1)})_{ij}]^{2}}{\vphantom{\widetilde{\widetilde{W}}}\widetilde{W}_{ij}}$

$\widehat{W}^{(t)}\leftarrow\lambda\cdot\widehat{W}+(1-\lambda)\cdot\widehat{W}^{(t-1)}$

for $(i,j)\in R$ do

$W_{ij}\leftarrow W^{(t)}_{ij}$

end for

end for

These methods typically excel in the case of data that is missing completely
at random; this is not the case for the empirical PMI matrix, where the
smallest values are the entries most likely to be missing. Indeed, this
limitation is a special case of the primary downside of the EM-MVSVD
algorithm: It only aims to minimize the error on the known, non-missing
values, so no information regarding the missing values is incorporated. As a
result, if the matrix entries come from a known distribution, the EM-MVSVD
algorithm may yield a factorization that is incompatible with the generating
distribution on the missing values. This thus motivates the need to
incorporate distributional information into the EM-MVSVD algorithm in certain
problems.

Thus, our proposed methodology to factorize the population SPMI matrix is thus
as follows: Given a corpus of finite length with $V$ unique words, compute the
empirical co-occurrence matrix; sort the rows and columns by marginal
frequencies and then normalize the matrix to form a bivariate probability
distribution. Now identify each word with its rank ($1$ through $V$, with $1$
being most frequent and $V$ being least frequent); this allows us to compute
the correlation terms to use in the Gaussian copula. The copula then gives us
a dense estimate for the “true" co-occurrence probabilities, which can then be
transformed into an estimate for the population SPMI matrix with no missing
values. We then use this estimate as the input $\widetilde{W}$ to Algorithm 2,
a distribution-dependent MVSVD algorithm. This modifies EM-MVSVD (Algorithm 1)
by minimizing a Chi-Square Goodness-of-Fit statistic with the estimated
population SPMI as opposed to merely trying to match the empirical SPMI on
non-missing entries.

##  5 Simulation Study

To study the effectiveness of these methods in estimating the population SPMI
matrix, we generated text and compared the matrices generated by Word2Vec, SVD
of the SPPMI, EM-MVSVD (Algorithm 1), and DD-MVSVD (Algorithm 2) to the
population SPMI matrix.

To do so, we read in words from the Brown Corpus and sampled 500 words
uniformly from the set of unique words; analogously to our proposed
methodology from Section 4.2, we then created a positive transition
probability matrix to generate text as well as the associated dense SPMI
matrix for this set of words via a Gaussian copula. We then ran Word2Vec, EM-
MVSVD, DD-MVSVD, and SVD on the empirical SPPMI matrix; each algorithm was
asked to create 100-dimensional word embeddings based on a shift of $10$
negative samples. The factorizations produced were then multiplied back
together to form an estimate of the population SPMI matrix; the root mean
square errors (RMSE) of these algorithms compared to the population SPMI
matrix are shown in Figure 2.

Evidently, the SVD of the empirical SPPMI matrix is an increasingly worse
approximation to the population PMI as the corpus size increases, and it
yields approximations far worse than any of the other algorithms. On the other
hand, the two MVSVD algorithms perform essentially identically to Word2Vec in
terms of RMSE from the population SPMI matrix. This thus demonstrates, without
the need to check performance on downstream tasks, that MVSVD algorithms will
yield word embeddings much more similar to Word2Vec (and thus perform
similarly to Word2Vec) than SVD on the empirical SPPMI matrix does.

Figure 2: The RMSE of Word2Vec, the MVSVD algorithms, and SVD on the SPPMI
matrix with respect to the population SPMI matrix. The RMSEs plotted are the
average over 20 independent trials. Error bars are not clearly visible, as all
standard errors are $<0.5$.

##  6 Real Data Analysis

To provide more evidence of our claim from the end of Section 5, we now
compare the performance of Word2Vec, the MVSVD algorithms, and SVD on the
SPPMI matrix on a sentiment analysis task. We trained a simple sentiment
analysis classifier on the IMDB movie review data set (Maas et al., 2011),
which is comprised of 50,000 anonymized movie reviews split evenly between bad
reviews (1-4 star ratings) and good reviews (7-10 star ratings). The goal of
the task is to train a model to predict how a review rated any given movie
when given that review’s text. We randomly split the data set into test-train
partitions, trained each embedding technique using the training partition,
then trained Bidirectional Long Short-Term Memory Networks (BiLSTMs) on movie
sentiment analysis. This experiment was repeated twenty times. The input to
each two-layer BiLSTM (with 100 units) was a sequence of embeddings
corresponding to the words contained in the review. Each model’s output was a
binary classification layer using a binary-cross entropy loss function and a
sigmoid activation function. To keep computations feasible, we removed
stopwords as well as words with fewer than 300 occurrences, reducing the
corpus to 3104 distinct words. Additionally, we zero-padded or truncated all
reviews to 500 words. The use of truncation avoided the problem of vanishing
or exploding gradients in long BiLSTM chains without severely compromising the
data, as 95% of reviews required no truncation.

|  | One-Hot | Word2Vec | SPPMI | EM-MVSVD | DD-MVSVD
---|---|---|---|---|---|---
|  | Acc. | S.E. | Acc. | S.E. | Acc. | S.E. | Acc. | S.E. | Acc. | S.E.
Negative Samples | 1 | 0.86 | 0.0047 | 0.79 | 0.0072 | 0.82 | 0.0087 | 0.82 | 0.0070 | 0.82 | 0.0146
2 | 0.86 | 0.0065 | 0.80 | 0.0138 | 0.78 | 0.0103 | 0.81 | 0.0096 | 0.84 | 0.0034
5 | 0.86 | 0.0028 | 0.79 | 0.0173 | 0.70 | 0.0133 | 0.80 | 0.0109 | 0.82 | 0.0114
Table 1: Model accuracies in positive/negative sentiment analysis on the IMDB
data ste across multiple levels of negative sampling.

Table 1 shows the performance of each model across five distinct embedding
algorithms and negative sampling levels of one, two, and five. In addition to
the previously discussed algorithms, we included a one-hot encoding of the
input words followed by a dense layer with 100 nodes, which serves the purpose
of acting as a benchmark for roughly how well the “perfect" embedding overfits
to the data can do in this task. All algorithms produced 100-dimensional
embeddings.

As expected, the one-hot embedding performed the best, achieving 86% accuracy
regardless of the amount of negative sampling. We see that the MVSVD
algorithms perform comparably to Word2Vec across all levels of negative
sampling, with DD-MVSVD performing the best among the three. We see that these
algorithms still perform decently in comparison to the one-hot embeddings,
achieving accuracies of roughly 80%. This is in stark contrast to the
performance of SVD on the SPPMI, which matches the MVSVD algorithms at one
negative sample, but quickly decreases in accuracy to 70% as the number of
negative samples increases. This phenomenon occurs because the sparsity of the
SPPMI matrix increases rapidly as the number of negative samples increases, so
the embeddings contain less and less information to allow the BiLSTM to make a
well-tuned classifier.

##  7 Conclusions

Through the use of our data-generating model for natural language, we find
that the MVSVD algorithms perform similarly to Word2Vec in estimating the
population PMI matrix, whereas SVD on the SPPMI matrix does not. This is also
reflected in the algorithms’ performance on the downstream task of sentiment
analysis, and perhaps to others as well. As such, the MVSVD algorithms can be
seen to be quite reasonable approximations to Word2Vec that still remain
tractable to analyze mathematically.

In the future, we hope to develop a theory for our proposed DD-MVSVD
algorithm, such as proving the convergence properties of the algorithm. A
similar EM-type algorithm for matrix completion is studied in Mazumder et al.
(2010), and theoretical convergence results are provided; we believe that
following a similar path as in Mazumder et al. (2010)—though extending their
proofs to our DD-MVSVD algorithm—is likely nontrivial due to the additional
SVD steps in our algorithm.

We also hope to be able to determine what other population parameters of
natural language, if any, are correlated with performance on various
downstream tasks of interest. For example, word embeddings generated by GloVe
(Pennington et al., 2014) target a log-count matrix in a similar way that
Word2Vec targets a PMI matrix; thus, this log-count matrix may also be
considered as a population parameter for a natural language. There are, of
course, other parameters derived from languages that are not based on
frequencies of words: capturing grammatical structures such as adjective
ordering or dominant word order, as well as measures based on semantic
similarity, would also be of great interest. As part of this investigation, we
believe that examining constructed languages prior to natural languages would
be a reasonable course of action; whereas structures that may yield
interesting population parameters in natural language are difficult both to
identify and to control for, it is easier to account for such problems in
simpler, constructed languages. Even exceedingly simple languages with less
than a dozen words and simple grammatical structures may be able to offer
insight into such parameters. More complex constructed languages exist, such
as Toki Pona (Lang, 2017, with only 14 phenomes and 120 words, but a well-
developed grammatical structure allowing for full communication), which may
act as a bridge between the study of completely artificial constructed
languages and natural languages.

We also plan to investigate other more complex NLP methods and build upon our
generating model to allow for more expressive modeling of language. For
example, a simple extension of our basic model would be to use a more general
$n$-gram model for some $n>1$ rather than limiting ourselves to the unigram
Markov chain. Additionally, we would like to investigate how other choices of
copulas other than the Gaussian copula impact the estimation of various
population parameters. We are also interested in studying more modern, non-
static embedding techniques, such as ELMo (Peters et al., 2018) and BERT
(Devlin et al., 2019), and investigating whether or not these can be
interpreted as statistical estimators.

#### Acknowledgements

Jonathan Williams’s and Neil Dey’s work in this publication was partially
supported by the National Heart, Lung, And Blood Institute of the National
Institutes of Health under Award Number R56HL155373. Srijan Sengupta’s work
was partially supported by an NIH R01 grant 1R01LM013309. Matthew Singer’s
work was partially supported by a grant from the Pacific Northwest National
Laboratory Distinguished Graduate Research Program. The content is solely the
responsibility of the authors and does not necessarily represent the official
views of the National Institutes of Health or the Pacific Northwest National
Laboratory.

## References

  * Airoldi & Bischof (2016) Edoardo M Airoldi and Jonathan M Bischof.  Improving and evaluating topic models and other models of text.  _Journal of the American Statistical Association_ , 111(516):1381–1403, 2016.
  * Arora et al. (2016) Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski.  A latent variable model approach to PMI-based word embeddings.  _Transactions of the Association for Computational Linguistics_ , 4:385–299, 2016.  doi: https://doi.org/10.1162/tacl_a_00106.
  * Bengio et al. (2003) Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Janvin.  A neural probabilistic language model.  _Journal of Machine Learning Research_ , 3:1137–1155, 2003\.
  * Brown et al. (1992a) Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, Jennifer C. Lai, and Robert L. Mercer.  An estimate of an upper bound for the entropy of English.  _Computational Linguistics_ , 18(1):31–40, 1992a.
  * Brown et al. (1992b) Peter F. Brown, Vincent J. Della Pietra, Peter V. deSouza, Jennifer C. Lai, and Robert L. Mercer.  Class-based $n$-gram models of natural language.  _Computational Linguistics_ , 18(4):467–479, 1992b.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  In _34th Conference on Neural Information Processing System_ , volume 33, pp. 1877–1901. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf.
  * Chen & Goodman (1999) Stanley F. Chen and Joshua Goodman.  An empirical study of smoothing techniques for language modeling.  _Computer Speech & Language_, 13(4):359–394, 1999.  ISSN 0885-2308.  doi: https://doi.org/10.1006/csla.1999.0128.  URL https://www.sciencedirect.com/science/article/pii/S0885230899901286.
  * Chen et al. (2022) Yinyin Chen, Shishuang He, Yun Yang, and Feng Liang.  Learning topic models: Identifiability and finite-sample analysis.  _Journal of the American Statistical Association_ , pp. 1–16, 2022\.
  * Collobert & Weston (2008) Ronan Collobert and Jason Weston.  A unified architecture for natural language processing: Deep neural networks with multitask learning.  In _Proceedings of the 25th International Conference on Machine Learning_ , pp. 160–167, 2008.  doi: https://doi.org/10.1145/1390156.1390177.
  * Dai et al. (2022a) Ben Dai, Xiaotong Shen, and Junhui Wang.  Embedding learning.  _Journal of the American Statistical Association_ , 117(537):307–319, 2022a.
  * Dai et al. (2022b) Ben Dai, Xiaotong Shen, and Wing Wong.  Coupled generation.  _Journal of the American Statistical Association_ , 117(539):1243–1253, 2022b.
  * Deerwester et al. (1990) Scott Deerwester, Susan T Dumais, George W Furnas, Thomas K Landauer, and Richard Harshman.  Indexing by latent semantic analysis.  _Journal of the American society for information science_ , 41(6):391–407, 1990.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  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_ , pp. 4171–4186, 2019.  doi: https://doi.org/10.18653/v1/N19-1423.
  * Feng et al. (2022) Rui Feng, Congcong Yang, and Yunhua Qu.  A word embedding model for analyzing patterns and their distributional semantics.  _Journal of Quantitative Linguistics_ , 29(1):80–105, 2022.
  * Francis & Kucera (1979) W. N. Francis and H. Kucera.  Brown corpus manual.  Technical report, Department of Linguistics, Brown University, Providence, Rhode Island, US, 1979.  URL http://icame.uib.no/brown/bcm.html.
  * Good (1953) I. J. Good.  The population frequencies of species and the estimation of population parameters.  _Biometrika_ , 40(3/4):237–264, 1953.  ISSN 00063444.  URL http://www.jstor.org/stable/2333344.
  * Ibragimov & Prokhorov (2017) Rustam Ibragimov and Artem Prokhorov.  _Heavy Tails and Copulas: Topics in Dependence Modelling in Economics and Finance_.  World Scientific Publishing Co. Pte. Ltd., 2017.
  * Jelinek & Mercer (1980) Frederick Jelinek and Robert L. Mercer.  Interpolated estimation of Markov source parameters from sparse data.  In _Proceedings of the Workshop on Pattern Recognition in Practice_ , 1980.
  * Kon & Nikolaev (2011) Mark A. Kon and Nikolay Nikolaev.  Empirical normalization for quadratic discriminant analysis and classifying cancer subtypes.  In _10th International Conference on Machine Learning and Applications and Workshops_ , 2011.  doi: https://doi.org/10.1109/ICMLA.2011.160.
  * Kurucz et al. (2007) Miklós Kurucz, András A Benczúr, and Károly Csalogány.  Methods for large scale SVD with missing values.  In _Proceedings of KDD cup and workshop_ , volume 12, pp. 31–38. Citeseer, 2007.
  * Lang (2017) Sonja Lang.  _Toki Pona: The Language of Good_.  Tawhid, 2017.  ISBN 0978292308.
  * Lapuyade-Lahorgue et al. (2017) Jérôme Lapuyade-Lahorgue, Jing-Hao Xue, and Su Ruan.  Segmenting multi-source images using hidden markov fields with copula-based multivariate statistical distributions.  _IEEE Transactions on Image Processing_ , 26(7):3187–3195, 2017.
  * Levy & Goldberg (2014) Omer Levy and Yoav Goldberg.  Neural word embedding as implicit matrix factorization.  _Advances in neural information processing systems_ , 27:2177–2185, 2014.
  * Li (2000) David X. Li.  On default correlation: A copula function approach.  _Journal of Fixed Income_ , 9(4):43–54, 2000\.  doi: https://doi.org/10.3905/jfi.2000.319253.
  * Li et al. (2021) Yutong Li, Ruoqing Zhu, Annie Qu, Han Ye, and Zhankun Sun.  Topic modeling on triage notes with semiorthogonal nonnegative matrix factorization.  _Journal of the American Statistical Association_ , 116(536):1609–1624, 2021.
  * Maas et al. (2011) Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts.  Learning word vectors for sentiment analysis.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pp. 142–150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/P11-1015.
  * MacKay & Bauman Peto (1995) David J. C. MacKay and Linda C. Bauman Peto.  A hierarchical Dirichlet language model.  _Natural Language Engineering_ , 1(3):289–308, 1995.  doi: https://doi.org/10.1017/S1351324900000218.
  * Mazumder et al. (2010) Rahul Mazumder, Trevor Hastie, and Robert Tibshirani.  Spectral regularization algorithms for learning large incomplete matrices.  _Journal of Machine Learning Research_ , 11:2287–2322, 2010\.
  * McNeil et al. (2005) Alexander J. McNeil, Rüdiger Frey, and Paul Embrechts.  _Quantitative Risk Management - Concepts, Techniques and Tools_.  Princeton University Press, 2005.  ISBN 0691122555.
  * Mikolov et al. (2013) Tomas Mikolov, Kai Chen, Gregory S. Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  In _International Conference on Learning Representations_ , 2013.
  * Mnih & Hinton (2008) Andriy Mnih and Geoffrey Hinton.  A scalable hierarchical distributed language model.  In _Advances in Neural Information Processing Systems 21_ , 2008.
  * Moreno-Sánchez et al. (2016) Isabel Moreno-Sánchez, Francesc Font-Clos, and Álvaro Corral.  Large-scale analysis of Zipf’s law in English texts.  _PLOS ONE_ , 11(1), 2016.
  * Nádas (1984) Arthur Nádas.  Estimation of probabilities in the language model of the IBM speech recognition system.  _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , ASSP-32(4):859–861, 1984.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning.  GloVe: Global vectors for word representation.  In _Empirical Methods in Natural Language Processing_ , pp. 1532–1543, 2014.  URL http://www.aclweb.org/anthology/D14-1162.
  * Peters et al. (2018) Matthew E. Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer.  Deep contextualized word representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pp. 2227–2237. Association for Computational Linguistics, 2018\.  doi: https://doi.org/10.18653/v1/N18-1202.
  * Schweiser & Sklar (1983) B. Schweiser and Abe Sklar.  _Probabilistic Metric Spaces_.  Dover Publications, Inc., Mineola, New York, 1983.
  * Sklar (1959) Abe Sklar.  Fonctions de répartition à n dimensions et leurs marges.  _Publications de l’Institut Statistique de l’Université de Paris_ , pp. 229–231, 1959.
  * Taddy (2013) Matt Taddy.  Multinomial inverse regression for text analysis.  _Journal of the American Statistical Association_ , 108(503):755–770, 2013.
  * Thompson & Kilgore (2011) David Thompson and Roger Kilgore.  Estimating joint flow probabilities at stream confluences using copulas.  _Transportation Research Record_ , 2262:200–206, 2011.  doi: https://doi.org/10.3141/2262-20.
  * Wang et al. (2019) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _Seventh International Conference on Learning Representations_ , 2019.
  * Wang et al. (2016) Junhui Wang, Xiaotong Shen, Yiwen Sun, and Annie Qu.  Classification with unstructured predictors and an application to sentiment analysis.  _Journal of the American Statistical Association_ , 111(515):1242–1253, 2016.
  * Wu et al. (2022) Ruijia Wu, Linjun Zhang, and T Tony Cai.  Sparse topic modeling: Computational efficiency, near-optimal algorithms, and statistical inference.  _Journal of the American Statistical Association_ , pp. 1–13, 2022\.
  * Xia et al. (2021) Lucy Xia, Richard Zhao, Yanhui Wu, and Xin Tong.  Intentional control of type i error over unconscious data distortion: A neyman–pearson approach to text classification.  _Journal of the American Statistical Association_ , 116(533):68–81, 2021.
  * Yan & Bien (2021) Xiaohan Yan and Jacob Bien.  Rare feature selection in high dimensions.  _Journal of the American Statistical Association_ , 116(534):887–900, 2021.
  * Zhang & Singh (2019) Lan Zhang and V. P. Singh.  _Copulas and their Applications in Water Resources Engineering_.  Cambridge University Press, 2019.  doi: https://doi.org/10.1017/9781108565103.
  * Zhou et al. (2016) Mingyuan Zhou, Oscar Hernan Madrid Padilla, and James G Scott.  Priors for random count matrices derived from a family of negative binomial processes.  _Journal of the American Statistical Association_ , 111(515):1144–1156, 2016.