%
% File acl08.tex
%
% Contact: nasmith@cs.cmu.edu

\documentclass[11pt]{article}
\usepackage{acl08}
\usepackage{times}
\usepackage{latexsym}

\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{xspace}
\usepackage{url}
\usepackage{multirow}
\urlstyle{same}

\usepackage{orange}

\setlength\titlebox{6.5cm}    % Expanding the titlebox

\newcommand{\Astar}{\mbox{A$^*$}\xspace}
\newcommand{\Sstar}{\mbox{S$^*$}\xspace}
\newcommand{\argmax}{\mathrm{arg}\,\max}
\newcommand{\argmin}{\mathrm{arg}\,\min}
\newcommand{\rembow}{\mathrm{Rem.~BOW}}
\newcommand{\bow}{\mathrm{BOW}}
\newcommand{\perm}{\mathrm{perm}}
\newcommand{\vocab}{\mathrm{vocab}}
\newcommand{\stopwords}{\mathrm{stopwords}}
\newcommand{\Sbeg}{\mathtt{<}\mathrm{S}\mathtt{>}}
\newcommand{\Send}{\mathtt{<}\mathtt{/}\mathrm{S}\mathtt{>}}
\newcommand{\Dbeg}{\mathtt{<}\mathrm{D}\mathtt{>}}
\newcommand{\Dend}{\mathtt{<}\mathtt{/}\mathrm{D}\mathtt{>}}
\newcommand{\true}{\mathrm{true}}
\newcommand{\dvec}{\mathbf{d}}
\newcommand{\xvec}{\mathbf{x}}
\newcommand{\hvec}{\mathbf{h}}
\newcommand{\cvec}{\mathbf{c}}
\newcommand{\rvec}{\mathbf{r}}
\newcommand{\ivec}{\mathbf{i}}
\newcommand{\svec}{\mathbf{s}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\z}{\mathbf{z}}
\newcommand{\hadm}{h^{\mathrm{adm}}}
\newcommand{\hemp}{h^{\mathrm{emp}}}

\title{Document Recovery from Bag-of-Word Indices}

%\author{Joakim Nivre \\
%  School of Mathematics and Systems Engineering \\
%  V\"{a}xj\"{o} University \\
%  SE-35195, V\"{a}xj\"{o}, Sweden \\
%  {\tt nivre@msi.vxu.se} \And
%  Noah A. Smith \\
%  Language Technologies Institute \\
%  Carnegie Mellon University \\
%  Pittsburgh, PA 15213, USA\\
%  {\tt nasmith@cs.cmu.edu}}

\date{}

\begin{document}
\maketitle
\begin{abstract}
Motivated by computer privacy issues, we present the novel problem of document recovery from an index: given only a
document's bag-of-words (BOW) vector or other types of index, reconstruct the original
\emph{ordered} document. 
We investigate a variety of index
types, including count-based BOW vectors, stopwords-removed count BOW vectors,
indicator BOW vectors, and bigram count vectors. 
We formulate the problem as hypothesis rescoring
with \Astar search and using the Google Web 1T 5-gram corpus.  
Our experiments on five domains
indicate that if original documents are short, 
the documents can be recovered with high accuracy.
\end{abstract}

\section{Introduction}

With the proliferation of text processing software such as desktop search
engines, database systems, and spam filters, computer users' personal files are
increasingly being indexed to enable fast searches and processing.  With
great popularity comes greater risk, though: few users know where the index
files are maintained and what security measures are used to protect them.  In
this paper, we seek to answer the following question: if an adversary obtains a
document's index, what can it learn about the original document?

We define the problem of \emph{document recovery from an index} as follows:
given only a document's bag-of-words (BOW) vector or other index, reconstruct
the original \emph{ordered} document. Our goal is to understand the extent to
which recovery is possible under standard computational means using large-scale
language resources (i.e., the Google Web 1T 5-gram corpus). 

The risk to privacy is real. 
An adversary may hack into a machine and gain access to the indices.
\footnote{Throughout this paper, we
assume that encryption has been compromised by the
adversary.} Software with such indices include
desktop search engines such as Apache Lucene (\protect\url{lucene.apache.org}),
some e-mail clients such as \emph{sup} (\protect\url{sup.rubyforge.org}) and \emph{cone}
(\protect\url{www.courier-mta.org/cone}),
and database management systems
like MySQL and PostgreSQL. 
Even more alarmingly, certain types of text classifiers
(e.g., nearest neighbor and kernel machines)
willingly distribute indices with the trained model to end users (and potentially the adversary).
In this case, the model consists of the prototype training examples or the support vectors -- documents in index form.
The concern is that the training documents might be
confidential or private in nature, and people should not assume the model is
secure.  
In fact, the model files produced by both SVM$^{light}$
(\protect\url{svmlight.joachims.org}) and LIBSVM
(\protect\url{www.csie.ntu.edu.tw/~cjlin/libsvm}) contain the support vectors
in a readable ASCII format (even in the case of linear SVMs).  Thus, anyone
provided with a model file has access to a set of index files.  

The approach adopted in this paper is similar to hypothesis rescoring, which has a long history in NLP.  Nonetheless, this work provides several
novel contributions:
(1) A formulation of the problem of document recovery, which we believe is an
important area for future NLP research.
(2) A benchmark dataset that simulates domains where document recovery could
be particularly detrimental (e.g., personal e-mail, government documents,
medical records).
(3) A comprehensive empirical study using the Google Web 1T 5-gram corpus and
the resulting ``stupid backoff'' language model~\cite{Brants07}.
(4) A specialized \Astar decoder using novel search heuristics for document
recovery from several types of indices.


\section{Related work}
\label{sec:related}
In the NLP domain, there has been a great deal of research on hypothesis rescoring.
In statistical machine translation (SMT), various decoding strategies have been explored~\cite{Knight1999Decoding,Germann2003Greedy}, 
including
traveling salesman formulation~\cite{Germann2001Fast},
beam search~\cite{Hoang08,Crego2005Ngram}, and 
\Astar search~\cite{och2001}.
Automatic speech recognition (ASR) systems also employ rescoring mechanisms, such as the ROVER system~\cite{rover}.
Athanaselis et al.~\shortcite{athanaselis06} use language model to search for reorderings of words in the context of automatic grammar checking.
Our work differs from all of the above in that we already know (at least some of) the words that must appear in the recovered document. While this may appear to simplify the problem, our problem may in fact be harder. 
In SMT, the set of possible permutations of target words is constrained based on the \emph{ordered} source language document~\cite{kanthak05novel,bangalore07}.
We lack such constraints in our task. We also consider decoding indicator vectors and vectors with stopwords removed, where we must decide how many additional words to introduce without the guide of a source document.

The current work shares commonality with data mining and security research that attempts to recover hidden knowledge from published sources.
Staddon et al.~\shortcite{Staddon07} study what inferences can be made when newly published data is combined with existing information on the Web.
David Naccache and Claire Whelan demoed software at Eurocrypt 2004 that predicted redacted words in a White House briefing regarding September 11.
Although different than our notion of document recovery, these work also address questions of privacy leakage from obscured or modified text.

Perhaps the closest work is Zhu et al.~\shortcite{Zhu2008Learning}, which showed that using only a large set of BOW vectors, an adversary can learn a simple bigram model and recover simple documents.  In that paper, no external language resources were used.  Instead, we use the state-of-the-art Google Web 1T 5-gram collection to provide a rich source of background knowledge for decoding BOW documents. 

\section{Problem formulation}
\label{sec:problem}

Let $\dvec = w_1^n$ be a document with $n$ words. We are interested in
four types of indices: 

1. \textit{Count BOW}. The index is a vector $\xvec = (x_1,...,x_V) \in
\mathbb{Z}_+^V$, where $x_v$ is the number of times word $v \in \vocab$ occurs
in $\dvec$ and $V$ is the size of vocabulary $\vocab$.

2. \textit{Stopwords-removed count BOW}. The index $\xvec =
(x_1,...,x_V) \in \mathbb{Z}_+^V$, where $x_v$ is $0$ if $v\in
\mathrm{stopwords}$, and the number of times $v$ occurs in
$\dvec$ otherwise.

3. \textit{Indicator BOW}. The index $\xvec = (x_1,...,x_V) \in \{0,1\}^V$,
where $x_v$ is $1$ if $v$ occurs in $\dvec$, and $0$ otherwise. 

4. \textit{Bigram count vector}. The index $\xvec = (x_{11},...,x_{VV}) \in
\mathbb{Z}_+^{V^2}$, where $x_{ij}$ is the number of times the ordered pair
$v_i, v_j$ occurs in $\dvec$.

For any index $\xvec$, the \textit{feasible set} $F(\xvec)$ is defined as the
set of documents that are consistent with $\xvec$, that is, the set of
documents each having index $\xvec$:
$F(\xvec) = \{\dvec : \xvec(\dvec) = \xvec\}$.
The \textit{document recovery problem} is to find the best document in the
feasible set given an index:
$\dvec^* = \argmax_{\dvec\in F(\x)} \mathrm{score}(\dvec)$
for some score function. For large $F(\xvec)$, $\dvec^*$ may be impractical to
compute exactly. In what
follows, we define the feasible sets, score functions, and methods of
approximating $\dvec^*$ for each index type.

\section{Recovery from count BOWs}
\label{sec:countbow}

\subsection{\Astar search}

For count BOWs, the feasible set $F(\xvec)$ is the set of permutations on 
words in $\xvec$.  This set will be large for indices of even
moderate size, so it is impractical to enumerate documents $\dvec \in
F(\xvec)$.  Instead, we approximately find the best document using memory-bounded
\Astar search \cite{RussellNorvig02}.  \Astar search finds the minimal-cost
path between a start and goal in a search space. It requires a measure $g$ of
the cost from the start state to a particular state, and a heuristic estimate
$h$ of the cost from the state to the goal state. If the estimate $h$ always
underestimates the true cost to the goal, $h$ is called an admissible heuristic,
and \Astar search is guaranteed to find the minimal-cost path from start to
goal.

To find $\dvec^*$ using \Astar search, let each state in the search space
represent a partial path $w_1^l$, where $l$ is the length of the partial path.
The start state consists of the start-of-sentence symbol $\Sbeg$. The ``real''
goal state is the original document, but since this original document is
unknown, the first complete path of length $n$ that is found is accepted as the
goal.  In the absence of search error, this will be the most likely length-$n$
path.

For our $g$ and $h$, it is convenient to use \textit{score} instead of
\textit{cost}; \Astar search then maximizes path score instead minimizing path
cost. The partial path score $g$ of a partial document is the log probability
of the partial document under a language model:
$g(w_1^l) \equiv \log p(w_1^l) = \sum_{i=1}^l \log p(w_i|w_1^{i-1})$.
We use the Google Web 1T 5-gram corpus and a 5-gram language model with stupid
backoff \cite{Brants07} to approximate the probabilities:
%
\begin{align*}
p(w_i|w_{i-k+1}^{i-1}) 
  = %\approx
  \begin{cases}
    \frac{c(w_{i-k+1}^i)}{c(w_{i-k+1}^{i-1})} & \mathrm{if}\, c(w_{i-k+1}^i) > 0 \\
    \alpha p(w_i|w_{i-k+2}^{i-1})             & \mathrm{otherwise}
  \end{cases}
\end{align*}
%
if $k > 1$, and $p(w_i) = c(w_i)/\sum_{v\in \vocab} c(v)$ if $k = 1$, where
$c(\cdot)$ is the n-gram count in the corpus.

We present two heuristics for $h$ below: one that is admissible (i.e., always
overestimates the score of the future path from the current state to the goal),
and one that is not admissible but empirically performs better.

\subsection{An admissible heuristic}

We exploit properties of the stupid-backoff language model to construct an
efficient admissible heuristic. Let
$s(w_i|w_{i-k+1}^{i-1})=$ 
%
\begin{align*}
%&s(w_i|w_{i-k+1}^{i-1}) \\
& \max{}_{j=1}^k \alpha^{k-j} 
  \begin{cases}
    \frac{c(w_{i-j+1}^i)}{c(w_{i-j+1}^{i-1})} & \mathrm{if}\, j > 1 \\
    c(w_i)/\sum_{v\in \vocab} c(v) & \mathrm{if}\, j = 1
  \end{cases}
\end{align*}
%
One can show that
$s(w_i|w_{i-k+1}^{i-1}) \geq p(w_i|w_{i-k+1}^{i-1})$.
Let
$s^*(w) = \max_{v_1^4 \in \vocab} s(w|v_1^4) 
\geq \max_{v_1^4 \in \vocab} p(w|v_1^4)$
be an upper bound on the probability of the word $w \in \vocab$ under all
possible 5-gram histories. Then the following is an admissible heuristic:
\begin{equation}
\hadm(w_1^l) = \sum_{w \in \xvec \backslash w_1^l} \log s^*(w),
\label{eqn:hadm}
\end{equation}
where $\xvec \backslash w_1^l$ denotes the ``remaining BOW'', in which the
count $x_v$ is decremented for each occurrence of $v$ in $w_1^l$. 

The heuristic $\hadm$ can be computed efficiently for each state, since the
quantity $s^*$ can be computed once, before \Astar search begins. While
computing $s^*$, although there are $V^4$ possible permutations $v_1^4 \in
\vocab$, we need only consider permutations for which n-gram counts exist; that
is, $s^*$ can be computed by scanning the list of n-grams used to construct our
language model.


\subsection{An empirical heuristic}

Our second heuristic, $\hemp$, was originally proposed by Och et al. \shortcite{och2001}
in the context of machine translation.
To construct the heuristic $\hemp$,
we first run \Astar search using $\hadm$. For each state $w_1^l$ that is
evaluated by this first search, we update the best-encountered probability for
$v=w_l$:
$p^*(v) \leftarrow \max\left(p^*(v), p(w_l|w_{l-4}^{l-1})\right)$,
where $p^*(v)$ is initialized to $-\infty$. The second time we run \Astar
search, we use these probabilities in the heuristic:
$\hemp(w_1^l) = \sum_{v \in \xvec \backslash w_1^l} \log p^*(v)$.
The heuristic $\hemp$ is not admissible, but it is intended to give a more
realistic estimate of future path cost than $\hadm$ does, and thus reduce the
fraction of search space that needs to be explored.

\subsection{Pruning strategies}

Using \Astar search with $\hadm$ or $\hemp$, the search space that needs to be
explored is still huge and memory is frequently exhausted before a solution is
found. In \Astar search, we store states 
in a priority queue.  Memory-bounded \Astar limits the size
of this queue by removing states that look unpromising.  We present three such
pruning strategies.

The first strategy is to prune the state
$w_1^l =
\argmin_{w_1^l \in \mathrm{queue}} g(w_1^l) + h(w_1^l)$
when the priority queue's size exceeds a threshold. However, as $l$ increases
$g(w_1^l) + h(w_1^l)$ tends to increase as well, so this pruning strategy tends
to prune long partial paths before shorter ones. This introduces a bias towards
short partial paths, and can be undesirable. We call this first strategy
$g+h$.

The second strategy is to prune based on the normalized score
$\argmin_{w_1^l \in \mathrm{queue}} \left(g(w_1^l) + h(w_1^l)\right)/l$
when the threshold is exceeded. This corrects the bias caused by differences in
length among the states. We call this strategy $(g+h)/l$.

A third strategy is to prune short states first; that is, prune
$\argmin_{w_1^l \in \mathrm{queue}} \lambda\,l + g(w_1^l) + h(w_1^l)$,
where $\lambda$ is large enough that all states of length $l-1$ are pruned
before states of length $l$. This strategy directly exploits the earlier
insight that short partial paths are most likely to be safe to prune.  Note
that using strategy $\lambda\,l+g+h$, after the memory limit has been reached,
our \Astar search is similar to beam search. 

\subsection{Baseline}

We compare our \Astar search procedure with a greedy baseline. The baseline
constructs a document by repeatedly drawing a word, without replacement, from a
count BOW and appending it to the partial document. At each iteration, the most
likely word given the current partial document is drawn.  Formally, each word
$w_i$ in the recovered document $\dvec$ is drawn such that
$w_i = \argmax_{v \in \xvec \backslash w_1^{i-1}} \log p(v|w_{i-4}^{i-1})$,
where $w_1^{i-1}$ is the current partial document.

\section{Recovery from stopwords-removed count BOWs}

In order for a document $\dvec$ to be in the feasible set $F(\xvec)$ of a
stopwords-removed count BOW $\xvec$, each word $v$ in the vocabulary must occur
$\xvec_v$ times in $\dvec$, unless $v$ is a stopword. If $v$ is a stopword, it
can occur any number of times in the document. As a result, we also do not know
$n$, the document length. This makes \Astar search difficult.
For example, a short document that only uses words in $\xvec$ may have a
higher language model score than a longer document that also uses stopwords.
Conversely, a long document that repeats a high-probability phrase of stopwords
like ``and in the'' may have a higher per-word score than a moderate-length
document that uses fewer stopwords. In fact, per-word score can increase
monotonically with partial document length. To simplify the problem and reduce
the size of the feasible set, we infer document length from $\xvec$ and limit
the feasible set to documents of that length.

To construct an estimator for document length $n$, given a stopwords-removed
count BOW, we calculate the average ratio of document length (including
stopwords) to BOW length (excluding stopwords)
$\beta = \frac{1}{|D|} \sum_{\dvec_i \in D} \frac{n_i}{\mathbf{1}^\top \xvec_i}$
on a separate training set $D$ of documents, where each document $\dvec_i$ has
length $n_i$ and a stopwords-removed BOW $\xvec_i$, and $\mathbf{1}$ is the
all-one vector. Our document-length estimator, given a BOW $\xvec$ with unknown
$n$ and $\dvec$, simply scales BOW length by $\beta$:
$\hat{n}(\xvec) = \beta \mathbf{1}^\top \xvec$.

To find the best document $\dvec^* \in F(\xvec)$, we perform \Astar search as
before, with one difference: successor states are generated by appending words
drawn from the remaining BOW (without replacement), as before, but also from
the stopwords list (with replacement). The heuristic $\hadm$ is still
admissible, although it is farther from the true future path score than before,
since $\hadm$ does not sum over stopwords' $s^*$ scores.

\section{Recovery from indicator BOWs}

In order for a document $\dvec$ to be in the feasible set $F(\xvec)$ of an
indicator BOW $\xvec$, each word $v$ in the vocabulary where $x_v = 1$ must
occur at least once in $\dvec$, and each word $v$ where $x_v = 0$ must not
occur in $\dvec$.  As before, document length $n$ is unknown, so we infer it
instead.

We use support vector machine regression to infer document length $\hat n$ from
our indicator BOW $\xvec$. We will train a function $f(\xvec)=n$ on a training
set $D$ of documents, where each document $\dvec$ has length $n$ and an
indicator BOW $\xvec$. However, $\xvec$ itself is unsuitable as a feature
vector: it has too many dimensions, so our estimator will suffer from data
sparseness if it uses $\xvec$ directly. Instead we create a ``count-count''
histogram $\hvec \in \mathbb{Z}_+^{11}$, where $h_j$ is the number of words
types $v \in \xvec$ such that $c_{\mathrm{google}}(v)$, the Google 1T 5-gram
corpus count of $v$, has $j$ digits ($10^{j-1} \leq c_{\mathrm{google}}(v) <
10^j$). The histogram $\hvec$ has 11 dimensions because no count in the
Google corpus has more than 11 digits. For example, let $\xvec = (1 0 1 1 0 1 0
...)$, where the four nonzero word types are ``aardvark'', ``an'', ``apple'',
and ``ate'', with Google counts of 93030, 1369286818, 6878789, and 4763100
respectively.  Then $\hvec=(0 0 0 0 1 0 2 0 0 1 0)$, since the count of
``aardvark'' has five digits, the counts of ``apple'' and ``ate'' have seven
digits, and the count of ``an'' has ten digits. We use $\hvec$ along with BOW
length $\mathbf{1}^\top\xvec$ as our feature vector. We use SVM$^{light}$
\cite{joachims98making} to train a support vector machine regression model
$\hat f(\hvec, \mathbf{1}^\top\xvec)$ with a linear kernel.
%\footnote{We also tried using a polynomial kernel, but using a linear kernel yields better results. \orange{I tried other ones, but I think only when I was incorrectly in classification mode. should I try more or is this enough?}} 
To predict document length given a new indicator BOW $\xvec$, we take the maximum of the prediction and the BOW length:
\[
\hat n = \max(\mathrm{round}(\hat f(\hvec, \mathbf{1}^\top \xvec)), \mathbf{1}^\top \xvec).
\]

To find the best document $\dvec^* \in F(\xvec)$, we perform \Astar search as
for count BOWs, but when generating successor states, we append words drawn
from the remaining BOW with replacement rather than without replacement.
Additionally, we require that each word type in the BOW be used at least once
in the complete document. The heuristic $\hadm$ must be changed slightly, since
our BOW now contains $1$s and $0$s, not counts: we require the summation in
equation \ref{eqn:hadm} to range over a remaining BOW $\xvec \backslash w_1^l$
in which each entry is $1$ if $x_v=1$ and $v \not \in w_1^l$, and $0$
otherwise.  Since word types that will be reused in the future partial path are
not accounted for in this version of $\hadm$, this version is farther from the
true future path score than $\hadm$ in the case of a count BOW. Nevertheless,
this $\hadm$ is still admissible, since repeated word types will only decrease
the future path score.

\section{Recovery from bigram count vectors}
\label{sec:bigram}

The feasible set of a bigram count vector is highly constrained. Document
length $n$ can be recovered exactly: $n = \mathbf{1}^\top \xvec + 1$, since
each word token in the original document except the last token is counted in
the first position of one bigram. Additionally, the bigram $w_1, w_2$ must
occur $x_{w_1,w_2}$ times in $\dvec$ for all $\dvec \in F(\xvec)$.

We use these constraints to make the problem easier to solve. To motivate our
discussion, suppose that a bigram count vector $\xvec$ has count 1 for each of
``the dog'', ``dog runs'', ``runs quickly'', and ``runs slowly''. 
There is ambiguity: we do not know whether ``the dog runs
quickly'' or ``the dog runs slowly'' occurred in the original document. We do
still know that ``the dog runs'' occurred.

We call document fragments that are unambiguously determined by the bigram
count vector \textit{sticks}. Before we start our search procedure proper, we
construct a stick $t_i$ for each bigram $w_{i_1},w_{i_2}$ such that
$x_{w_{i_1},w_{i_2}} > 0$. We start with $t_i = w_{i_1},w_{i_2}$. If we can
extend leftward without ambiguity, that is, if there exists a $w_{i_3}$ such
that (a) $x_{w_{i_3},w_{i_1}} > 0$, (b) the bigram $w_{i_3},w_{i_1}$ will occur
no more than $x_{w_{i_3},w_{i_1}}$ times in the new stick, and (c)
$x_{w_{i_4},w_{i_1}} = 0$ for all $w_{i_4} \in \vocab$, $w_{i_4} \neq w_{i_3}$,
then we extend $t_i = w_{i_3},w_{i_1},w_{i_2}$.  Similarly, if we can extend
rightward without ambiguity, we extend $t_i = w_{i_1},w_{i_2},w_{i_3}$. A
single stick can be extended both leftward and rightward. We repeatedly extend
each stick until an ambiguity is reached. We extend rightward as far as
possible before extending leftward.

Once we have our sticks, we search for the best document $\dvec^* \in F(\xvec)$
using \Astar search without heuristic. We extend each partial path by
appending an unused stick to the partial path, and ignoring the beginning of
the stick if it overlaps with the end of the partial path.


\section{Experiments}
\label{sec:experiments}

\begin{small}
\begin{table*}[htbp]
\centering
\begin{tabular}{|lccl|}
\hline
Domain  & s/d & w/d & Example \\
\hline
Medical &   8 &  153 & 
    She also had some breathlessness . \\ %o1
&&& She  also  had  some  breathlessness  . \\ %r1
&&& She  also  had  some  breathlessness  . \\ %ind
&&& \text{We}  \text{have}  had  some  breathlessness  . \\ %stop
\hline

&&& He was not wearing a helmet and was seen unconscious when paramedics arrived . \\ % orig
&&& He  was  unconscious  when  paramedics  arrived  and  was  seen  not  wearing  a  helmet  . \\ % count 15
&&& He  was  not  wearing  a  helmet  and  was  unconscious  when  paramedics  arrived  .   seen  .  \\ % ind
&&& He  was  seen  wearing  a  helmet  was  not  unconscious  when  paramedics  arrived  . \\ % stop
\hline

CIA     &  22 &  487 & These regiments are under a divisional headquarters called the 324 B Division . \\ %o12
&&      & These  are  called  the  B  324  Division  regiments  under  a  divisional  headquarters  .  \\%r12
&&      & B  Division  324  These  are  called  the  regiments  under  a  divisional  headquarters  .  \\ %ind
&&      & 324  regiments  under  Division  B  \text{of  A}  are  called  \text{the}  divisional  headquarters  . \\ %stop
\hline

&&& The President had his breakfast during the meeting is [\textit{sic}] the Situation \\
&&&   Room Conference Room . \\ %o16
&&& The  Situation  Room  is  the  President  had  his  breakfast  meeting  during  the  \\
&&&  Conference  Room  . \\ % r16
&&& The  President  had  his  breakfast  .  The  Situation  Room  is  the  meeting  \\
&&& during  the  Conference  . \\ % ind
&&& It  is  during  this  meeting  that  the  President  had  breakfast  Situation  Room  \\
&&& Conference  Room  . \\ % stop
\hline

Email   &  11 &  228 & I sincerely wish all of you the best in your future endeavors . \\ %o14
&&      & I  sincerely  wish  all  of  you  the  best  in  your  future  endeavors  .  \\ %r14
&&      & I  sincerely  wish  \text{all  of}  you  \text{the  best  of  the  best}  in  \text{all}  your  future  endeavors  . \\ %ind
&&      & sincerely  wish  all  \text{the}  best  \text{in}  future  endeavors  .  \\ %stop
\hline

&&& PIRA is coming in May to do their semi - annual energy outlook . \\ %o9
&&& May  PIRA  is  coming  in  to  do  their  semi  -  annual  energy  outlook  . \\ %r9
&&& May  .  PIRA  is  coming  in  to  do  their  semi  -  annual  energy  outlook  . \\ %ind
&&& PIRA  is  a  semi  -  annual  energy  outlook  for  this  coming  May  . \\ %stop

\hline

Stock   &  13 &  400 & Our quality systems are ISO/TS16949 ( 2002 version ) certified . \\ %o14
&&      & Our  quality  systems  are  certified  ISO/TS16949  (  2002  version  )  .  \\ %r14
&&      & ISO/TS16949  Our  quality  systems  are  certified  version  \text{ ) }  (  2002  \text{ ) }  . \\ %ind
&&      & ISO/TS16949  quality  systems  are  certified  to  the  2002  and  version  (  )  . \\ %stop
\hline

&&& This department operates under the name of Stock Yards Trust Company . \\
&&& This  department  operates  under  the  name  of  Trust  Stock  Yards  Company  .\\ %17r
&&& This  department  operates  under  the  name  of  the  Trust  .  Stock  Yards  Company  . \\ % indicator
&&& Trust  in  the  Stock  Yards  Company  operates  under  the  name  department  . \\ % stop

\hline

SW      & 111 & 1771 & B : uh - huh um - hum  \\ %o1
&&      & B  :  huh  uh  -  um  -  hum  . \\ %r1
&&      & B  :  uh  huh  um  -  hum  .  \\ %ind
&&      & \text{Go}  \text{to}  :  \text{A}  -  B  -  um  uh  huh  hum  . \\ %stop
\hline
&&& A : halfway there so that 's good . \\
&&& A  halfway  there  :  so  that  's  good  . \\
&&&  A  :  halfway  there  so  that  's  good  . \\
&&& so  good  :  it  's  halfway  there  .  \\
\hline
\end{tabular}
\caption{Statistics and example sentences from each domain. s/d = sentences per
document; w/d = word tokens per document. The fourth column lists (1) the
original document, (2) the document recovered from a count BOW, (3) the
document recovered from an indicator BOW, and
(4) the document recovered from a stopwords-removed count BOW.}
\label{table:domains}
\end{table*}
\end{small}

\subsection{Datasets}

We collected a benchmark dataset consisting of 5 domains, each with 20
documents. The dataset simulates a collection of sensitive documents that an
adversary might be interested in. The domains are:

1. Medical records: anatomy case studies from the University of Michigan's
medical school at
\protect\url{http://medical.med.umich.edu/courseinfo/clinical_index.html}.

2. CIA: declassified CIA documents from Gale's Declassified Documents
Reference System at \protect\url{http://galenet.galegroup.com/servlet/DDRS}. 

3. Email: messages from the Enron email corpus at
\protect\url{http://www.cs.cmu.edu/~enron/}.

4. Stock: annual reports aggregated by InvestorCalendar at
\protect\url{http://investorcalendar.ar.wilink.com}.

5. Switchboard (SW): telephone conversation transcripts from LDC online's
free section of Switchboard. 

Table \ref{table:domains} presents statistics and examples of each domain.

\subsection{Experimental procedure}

Document recovery is a difficult problem, and results are sensitive to the
length of the documents. In order to compare our methods more effectively, we
created synthetic documents of varying lengths $N$ from each original document
and tested on these synthetic documents. Each synthetic document is comprised
of $N$ contiguous real sentences from one original document, starting at a
random sentence in the original. If the original document had fewer than $N$
sentences, we took the entire document; for $N=20$, this occurred 65 out of 100
times.
%in 65 out of the 100
%synthetic documents, the synthetic document consists of the entire original
%document.)

To evaluate the results of document recovery on each set of synthetic
documents, we use BLEU 4 \cite{Papineni01}, comparing the recovered documents
to the synthetic documents. All reported BLEU scores are averages within a set
of synthetic documents for a single $N$ and domain.
In all our experiments, we set $\alpha=0.4$ and $\lambda=1000$. We use the
small stopword list in \cite{manning99foundations}, which has 114 word types,
57 uppercase and 57 lowercase.

\subsection{Results}

Examples of a few recovered $N=1$ documents are shown in Table \ref{table:domains}.
Tables \ref{table:20} and  \ref{table:16} show the results of our experiments on
different combinations of index types, heuristics, pruning strategies, domains,
and document lengths, in terms of the BLEU scores. 
We make the following observations:

1. The results show two conditions under which we can recover documents with good
success: (i) if the original document is short (Table~\ref{table:20}, ``$N=1$'' row), or (ii) if the index is a bigram
count vector (Table~\ref{table:20}, ``bigram'' column). Long documents, given a unigram BOW, are much more difficult to
recover. This makes intuitive sense: when the original document is short or the index
preserves ordering constraints, the feasible set is small, which makes recovery
easier. 

2. Among unigram BOWs, the index type affects the recovery rate. It is
easiest to recover documents from count BOWs, somewhat harder to recover from
indicator BOWs, and hardest of all from stopwords-removed count BOWS (Table~\ref{table:20}, ``counts, stopwords, indicator'' columns). The fact
that we must infer the document length from the BOW contributes to the
difficulty of the latter two index types; when we artificially substitute the
true original document length for our estimated document length, recovery
improves, especially for short documents where each word is relatively more
important (Table~\ref{table:20}, ``$n$'' vs. ``$\hat{n}$'' columns).

3. The domains vary in difficulty of recovery. The medical and stock domains seem
the easiest (rows in Table~\ref{table:20}). This may be because they are both more similar to general Web text
than, for example, Switchboard, and our language model is trained on Web text.

4. Finally, Table~\ref{table:16} shows that our choice of heuristic and pruning strategy affects recovery. The
empirical heuristic performs consistently better than the admissible heuristic.
As for pruning strategies, $g+h$ is substantially the worst, but the other
two strategies, $\lambda\,l+g+h$ and $(g+h)/l$, yield more or less equally good
results. However, it is worth noting that \Astar search is much faster using
$\lambda\,l+g+h$ than it is using $(g+h)/l$. For example, producing the third
column of Table \ref{table:16} took about an hour, while the second column took
over a day.
% Using strategy (b) and $\hadm$, decoding the medical domain for
% $N =$ 1, 2, 4, and 16 takes over a day; using strategy (c), decoding takes
% about an hour. 


\begin{small}
\begin{table*}[htbp]
\centering
\begin{tabular}{|c|c|ccccccc|}
\hline
$N$ & domain & counts & baseline & stopwords, $n$ & stopwords, $\hat n$ & indicator, $n$     & indicator, $\hat n$ & bigram \\
\hline
           % count  % baseline % stop,n % stop,n^ % ind,n  % ind,n^ % bigram %
\multirow{5}{*}{1}                      
 & medical & 0.5774 & 0.0821   & 0.3998 & 0.3427  & 0.5590 & 0.3971 & 0.9294 \\
 & CIA     & 0.3704 & 0.1338   & 0.2525 & 0.2178  & 0.3541 & 0.2584 & 0.8515 \\
 & email   & 0.4845 & 0.1340   & 0.3639 & 0.2575  & 0.4242 & 0.3393 & 0.8122 \\
 & stock   & 0.5329 & 0.1023   & 0.4279 & 0.4282  & 0.4099 & 0.3329 & 0.8247 \\
 & SW      & 0.4793 & 0.1280   & 0.2866 & 0.2314  & 0.4341 & 0.3534 & 0.8522 \\
\hline                                   
\multirow{5}{*}{2}                      
 & medical & 0.4389 & 0.0972   & 0.2957 & 0.2521  & 0.3683 & 0.2885 & 0.7336 \\
 & CIA     & 0.3348 & 0.0867   & 0.2334 & 0.2148  & 0.2689 & 0.2187 & 0.7438 \\
 & email   & 0.4366 & 0.1949   & 0.3595 & 0.3304  & 0.3634 & 0.3216 & 0.7566 \\
 & stock   & 0.4768 & 0.1125   & 0.3522 & 0.3240  & 0.3671 & 0.3313 & 0.7415 \\
 & SW      & 0.3882 & 0.0700   & 0.2163 & 0.1923  & 0.2900 & 0.2751 & 0.6570 \\
\hline                                   
\multirow{5}{*}{5}                      
 & medical & 0.3363 & 0.0876   & 0.2413 & 0.2254  & 0.1997 & 0.2001 & 0.6902 \\
 & CIA     & 0.2381 & 0.0630   & 0.1803 & 0.1845  & 0.1631 & 0.1644 & 0.6710 \\
 & email   & 0.2822 & 0.0934   & 0.1894 & 0.1742  & 0.1982 & 0.2021 & 0.6519 \\
 & stock   & 0.3570 & 0.0787   & 0.2826 & 0.2624  & 0.2002 & 0.1896 & 0.6782 \\
 & SW      & 0.1904 & 0.0815   & 0.1293 & 0.1135  & 0.0983 & 0.0965 & 0.6018 \\
\hline                                   
\multirow{5}{*}{10}                     
 & medical & 0.2852 & 0.0835   & 0.2216 & 0.2038  & 0.1514 & 0.1543 & 0.6739 \\
 & CIA     & 0.1835 & 0.0682   & 0.1570 & 0.1427  & 0.1048 & 0.1050 & 0.6027 \\
 & email   & 0.2239 & 0.1104   & 0.1738 & 0.1621  & 0.1501 & 0.1513 & 0.6254 \\
 & stock   & 0.2713 & 0.0891   & 0.2190 & 0.2129  & 0.1291 & 0.1192 & 0.6331 \\
 & SW      & 0.1352 & 0.0617   & 0.1075 & 0.0997  & 0.0493 & 0.0449 & 0.4910 \\
\hline                                   
\multirow{5}{*}{20}                     
 & medical & 0.2823 & 0.0839   & 0.2200 & 0.2003  & 0.1531 & 0.1479 & 0.6687 \\
 & CIA     & 0.1737 & 0.0771   & 0.1515 & 0.1355  & 0.0866 & 0.0736 & 0.5513 \\
 & email   & 0.1928 & 0.1005   & 0.1556 & 0.1458  & 0.1155 & 0.1181 & 0.5697 \\
 & stock   & 0.2533 & 0.0878   & 0.2015 & 0.2090  & 0.1024 & 0.1148 & 0.6126 \\
 & SW      & 0.1239 & 0.0602   & 0.0989 & 0.0937  & 0.0285 & 0.0189 & 0.4365 \\
\hline
\end{tabular}
\caption{BLEU 4 scores for synthetic subsets of the all domains and for each
index type. In all cases, heuristic $\hemp$ and pruning strategy
$\lambda\,l+g+h$ are used.}
\label{table:20}
\end{table*}
\end{small}

\begin{small}
\begin{table*}[htbp]
\centering
\begin{tabular}{|c|ccc|ccc|}
\hline
$N$ & \multicolumn{3}{c|}{Admissible $h$} & \multicolumn{3}{c|}{Empirical $h$} \\
       & $g+h$  & $(g+h)/l$ & $\lambda\,l+g+h$ & $g+h$ & $(g+h)/l$ & $\lambda\,l+g+h$ \\
\hline
1      & 0.3302 & 0.5714    & 0.5971     & 0.4120     & 0.5975    & 0.5936 \\
2      & 0.2149 & 0.4267    & 0.3861     & 0.2708     & 0.4673    & 0.4804 \\
4      & 0.2099 & 0.2575    & 0.2264     & 0.2099     & 0.3586    & 0.3369 \\
16     & 0.1510 & 0.1934    & 0.1858     & 0.1847     & 0.2729    & 0.2970 \\







\hline
\end{tabular}
\caption{BLEU 4 scores for synthetic subsets of the medical domain, with count BOW, for each
heuristic and pruning strategy presented in Section~\ref{sec:countbow}.
These synthetic subsets are a different random sample than those in Table~\ref{table:20}.
}
\label{table:16}
\end{table*}
\end{small}


\section{Conclusion and Discussions}
\label{sec:discussions}

We have formulated the document recovery problem, constructed several initial
attempts to solve it, and produced a benchmark test dataset which we plan to share with the research community after review. Our results for all
conditions improve on the greedy baseline. Most importantly, we have shown that
if original documents are short or the index is a bigram count vector,
documents can be recovered from indices with high BLEU4 scores.
This has important implications in security and privacy.

In future research, we would like to explore syntactic constraints to limit
the feasible set and to improve our score function. We would also like to treat
other types of indices, such as TF-IDF vectors or BOWs with stemming.


\bibliographystyle{acl}
\bibliography{docrecovery}

\end{document}





% \begin{table}[H]
% \centering
% \begin{tabular}{c|ccccc}
% $N$ & medical & cia & email & stock & SW \\
% \hline
%  1     & 0.5774 & 0.3704 & 0.4845 & 0.5329 & 0.4793 \\
%  2     & 0.4389 & 0.3348 & 0.4366 & 0.4768 & 0.3882 \\
%  5     & 0.3363 & 0.2381 & 0.2822 & 0.3570 & 0.1904 \\
% 10     & 0.2852 & 0.1835 & 0.2239 & 0.2713 & 0.1352 \\
% 20     & 0.2823 & 0.1737 & 0.1928 & 0.2533 & 0.1239 \\
% \end{tabular}
% \caption{R2: counts bow, using h2pass, 1000-prune, true doclen}
% \label{table:R2}
% \end{table}


% \begin{table}[H]
% \centering
% \begin{tabular}{c|ccccc}
% $N$ & medical & cia & email & stock & SW \\
% \hline
%  1     & 0.5590 & 0.3541 & 0.4242 & 0.4099 & 0.4341 \\  
%  2     & 0.3683 & 0.2689 & 0.3634 & 0.3671 & 0.2900 \\ 
%  5     & 0.1997 & 0.1631 & 0.1982 & 0.2002 & 0.0983 \\ 
% 10     & 0.1514 & 0.1048 & 0.1501 & 0.1291 & 0.0493 \\ 
% 20     & 0.1531 & 0.0866 & 0.1155 & 0.1024 & 0.0285 \\ 
% \end{tabular}
% \caption{R4: indicator bow, using h2pass, 1000-prune, true doclen}
% \label{table:R4}
% \end{table}

% \begin{table}[H]
% \centering
% \begin{tabular}{c|ccccc}
% $N$ & medical & cia & email & stock & SW \\
% \hline
%  1     &  0.3971 & 0.2584 & 0.3393 & 0.3329 & 0.3534 \\
%  2     &  0.2885 & 0.2187 & 0.3216 & 0.3313 & 0.2751 \\ 
%  5     &  0.2001 & 0.1644 & 0.2021 & 0.1896 & 0.0965 \\ 
% 10     &  0.1543 & 0.1050 & 0.1513 & 0.1192 & 0.0449 \\ 
% 20     &  0.1479 & 0.0736 & 0.1181 & 0.1148 & 0.0189 \\ 
% \end{tabular}
% \caption{R5: indicator bow, using h2pass, 1000-prune, doclen estimate}
% \label{table:R5}
% \end{table}

% \begin{table}[H]
% \centering
% \begin{tabular}{c|ccccc}
% $N$ & medical & cia & email & stock & SW \\
% \hline
%  1     &  0.3998 & 0.2525 & 0.3639 & 0.4279 & 0.2866 \\
%  2     &  0.2957 & 0.2334 & 0.3595 & 0.3522 & 0.2163 \\
%  5     &  0.2413 & 0.1803 & 0.1894 & 0.2826 & 0.1293 \\
% 10     &  0.2216 & 0.1570 & 0.1738 & 0.2190 & 0.1075 \\
% 20     &  0.2200 & 0.1515 & 0.1556 & 0.2028 & 0.0989 \\
% \end{tabular}
% \caption{R6: stopwords bow, using h2pass, 1000-prune, true doclen}
% \label{table:R6}
% \end{table}

% \begin{table}[H]
% \centering
% \begin{tabular}{c|ccccc}
% $N$ & medical & cia & email & stock & SW \\
% \hline
%  1     &  0.3427 & 0.2178 & 0.2575 & 0.4282 & 0.2314 \\ 
%  2     &  0.2521 & 0.2148 & 0.3304 & 0.3240 & 0.1923 \\
%  5     &  0.2254 & 0.1845 & 0.1742 & 0.2624 & 0.1135 \\
% 10     &  0.2038 & 0.1427 & 0.1621 & 0.2129 & 0.0997 \\
% 20     &  0.2003 & 0.1355 & 0.1458 & 0.2023 & 0.0937 \\
% \end{tabular}
% \caption{R7: stopwords bow, using h2pass, 1000-prune, doclen estimate}
% \label{table:R7}
% \end{table}

% \begin{table}[H]
% \centering
% \begin{tabular}{c|ccccc}
% $N$ & medical & cia & email & stock & SW \\
% \hline
%  1     & 0.9294 & ? & ? & ? & ? \\ 
%  2     & 0.7352 & ? & ? & ? & ? \\
%  5     & 0.6962 & ? & ? & ? & ? \\
% 10     & 0.6747 & ? & ? & ? & ? \\
% 20     & 0.6711 & ? & ? & ? & ? \\
% \end{tabular}
% \caption{R8: bigram sticks, using no h, 1000-prune, true doclen}
% \label{table:R8}
% \end{table}

% \begin{table}[H]
% \centering
% \begin{tabular}{c|ccccc}
% $N$ & medical & cia & email & stock & SW \\
% \hline
%  1     & 0.0821 & 0.1338 & 0.1340 & 0.1023 & 0.1280 \\
%  2     & 0.0972 & 0.0867 & 0.1949 & 0.1125 & 0.0700 \\
%  5     & 0.0876 & 0.0630 & 0.0934 & 0.0787 & 0.0815 \\
% 10     & 0.0835 & 0.0682 & 0.1104 & 0.0891 & 0.0617 \\
% 20     & 0.0839 & 0.0771 & 0.1005 & 0.0878 & 0.0602 \\
% \end{tabular}
% \caption{R3: counts bow, using greedy baseline, true doclen}
% \label{table:R3}
% \end{table}





% \begin{figure}[ht]
% \centering
% \includegraphics[width=0.4\textwidth]{stopwords_doclen.eps}
% \caption{cia dataset, stopwords BOW, true vs predicted document length}
% \label{fig:stopwords_doclen}
% % # following two vectors generated by doclen_stopwords/test.py
% % #anatomy
% %  doclens=[8 11 17 15 26 28 21 31 40 28 32 36 45 23 16 15 32 33 12 28 31 23 49 39 40 89 38 22 60 19 61 60 74 47 46 33 50 54 22 57 76 119 104 100 115 153 105 94 157 70 94 89 135 103 103 93 106 97 61 96 130 146 104 167 115 153 180 178 234 160 225 89 211 233 125 93 186 184 131 96 130 146 104 167 115 153 180 178 234 289 257 89 211 233 125 93 186 184 199 96]
% % estimates=[10 14 22 18 29 32 24 33 41 34 31 38 51 28 19 18 37 36 15 31 33 26 49 37 41 75 40 24 55 20 56 54 65 49 46 32 43 49 24 54 65 97 88 72 94 115 83 79 112 55 72 80 109 88 80 83 75 84 50 77 97 115 88 121 94 115 124 140 151 120 151 80 158 166 96 83 126 132 98 77 97 115 88 121 94 115 124 140 151 188 161 80 158 166 96 83 126 132 140 77]
% % #enron
% % doclens=[16 4 3 4 29 24 37 42 16 8 16 25 5 15 10 17 128 30 18 34 12 21 18 20 69 88 16 23 67 15 48 41 15 46 23 38 39 26 32 45 56 48 106 51 100 166 79 78 67 15 94 75 41 339 238 74 194 103 67 82 56 48 154 169 196 320 175 78 67 15 247 172 41 412 195 74 217 327 110 82 56 48 154 297 221 453 427 78 67 15 346 172 41 425 758 74 217 407 110 82]
% % estimates=[14 5 4 5 27 23 36 45 15 6 15 26 6 11 10 18 120 37 18 28 11 20 19 20 82 72 20 23 80 14 42 43 15 42 29 37 40 24 27 40 54 50 123 59 110 166 73 80 80 14 89 84 42 392 278 70 183 87 59 72 54 50 172 185 221 295 190 80 80 14 234 190 42 463 197 70 204 332 106 72 54 50 172 336 252 415 455 80 80 14 333 190 42 476 852 70 204 410 106 72]
% % #cia
% % doclens=[ 4 28 37 27 32 43 52 5 29 19 11 15 27 40 4 17 54 4 25 18 45 80 52 56 52 66 71 47 78 22 47 26 74 68 50 43 105 48 66 40 153 118 109 185 131 144 88 90 148 66 139 94 112 140 98 92 147 113 162 96 288 342 241 354 268 293 262 172 301 148 279 257 193 276 231 201 330 338 316 157 325 601 417 555 545 374 451 346 642 275 525 432 374 339 403 267 732 560 407 303 ]
% % estimates=[ 5 26 32 27 26 38 43 6 26 20 13 15 24 33 5 17 41 5 24 20 45 72 46 51 38 60 61 40 73 26 45 27 65 57 42 38 82 49 60 45 138 103 98 174 109 128 87 86 137 73 137 86 105 128 94 91 121 107 146 110 262 290 221 336 226 241 229 162 268 162 276 231 179 252 212 198 285 332 285 186 296 538 374 532 458 318 414 318 559 300 517 393 345 309 377 254 618 545 370 349 ]
% % plot(doclens,estimates,'o')
% % hold on                             
% % plot([1:300],[1:300])  
% % xlabel('true D')
% % ylabel('{}_{^{\fontsize{10}D}}^{\^}')
% % saveas(1,'~/svn/recover/docs/paper/stopwords_doclen.eps')
% \end{figure}


% \begin{figure}[ht]
% \centering
% \includegraphics[width=0.4\textwidth]{indicator_doclen.eps}
% \caption{cia dataset, indicator BOW, true vs predicted document length}
% \label{fig:indicator_doclen}
% % # following two vectors generated by doclen_indicator/test.py
% %#anatomy
% %  doclens=[8 11 17 15 26 28 21 31 40 28 32 36 45 23 16 15 32 33 12 28 31 23 49 39 40 89 38 22 60 19 61 60 74 47 46 33 50 54 22 57 76 119 104 100 115 153 105 94 157 70 94 89 135 103 103 93 106 97 61 96 130 146 104 167 115 153 180 178 234 160 225 89 211 233 125 93 186 184 131 96 130 146 104 167 115 153 180 178 234 289 257 89 211 233 125 93 186 184 199 96]
% % estimates=[8 13 22 18 31 35 25 37 47 39 33 44 59 30 19 18 43 40 13 34 36 28 58 41 45 94 45 26 64 21 69 64 78 56 54 36 50 57 27 62 79 122 110 85 116 146 102 98 142 65 88 99 135 107 99 101 91 103 57 92 120 145 110 151 116 146 155 178 191 151 194 99 200 210 120 101 160 166 121 92 120 145 110 151 116 146 155 178 191 241 208 99 200 210 120 101 160 166 176 92]
% % #cia
% % doclens=[ 4 28 37 27 32 43 52 5 29 19 11 15 27 40 4 17 54 4 25 18 45 80 52 56 52 66 71 47 78 22 47 26 74 68 50 43 105 48 66 40 153 118 109 185 131 144 88 90 148 66 139 94 112 140 98 92 147 113 162 96 288 342 241 354 268 293 262 172 301 148 279 257 193 276 231 201 330 338 316 157 325 601 417 555 545 374 451 346 642 275 525 432 374 339 403 267 732 560 407 303 ]
% % estimates=[ 4 37 48 34 37 53 63 5 36 26 13 19 37 54 4 20 60 4 36 19 64 90 65 73 54 75 92 54 102 26 61 33 71 79 65 48 106 64 71 52 150 129 129 185 121 136 95 94 153 75 138 98 115 149 105 100 142 107 152 85 243 297 209 299 244 251 259 158 279 148 218 204 177 253 221 182 267 251 276 113 272 447 332 411 406 308 380 251 531 235 389 300 324 292 360 223 452 361 333 199 ]
% % plot(doclens,estimates,'o')
% % hold on                             
% % plot([1:300],[1:300])  
% % xlabel('true D')
% % ylabel('{}_{^{\fontsize{10}D}}^{\^}')
% % saveas(1,'~/svn/recover/docs/paper/indicator_doclen.eps')
% \end{figure}


% \begin{table*}[ht]
% \centering
% \begin{tabular}{c|c|ccccc}
% N & type               & medical & CIA   & email  & stock  & SW     \\
% \hline
% \multirow{7}{*}{1} 
%  & counts              & 0.5774 & 0.3704 & 0.4845 & 0.5329 & 0.4793 \\
%  & baseline            & 0.0821 & 0.1338 & 0.1340 & 0.1023 & 0.1280 \\
%  & stopwords, $n$      &                                     \\
%  & stopwords, $\hat n$ &                                     \\
%  & indicator, $n$      &                                     \\
%  & indicator, $\hat n$ &                                     \\
%  & bigram              &\\
% \hline
% \multirow{7}{*}{2} 
%  & counts              & 0.4389 & 0.3348 & 0.4366 & 0.4768 & 0.3882 \\
%  & baseline            & 0.0972 & 0.0867 & 0.1949 & 0.1125 & 0.0700 \\
%  & stopwords, $n$      &                                     \\
%  & stopwords, $\hat n$ &                                     \\
%  & indicator, $n$      &                                     \\
%  & indicator, $\hat n$ &\\
%  & bigram              &\\
% \hline
% \multirow{7}{*}{5} 
%  & counts              & 0.3363 & 0.2381 & 0.2822 & 0.3570 & 0.1904 \\
%  & baseline            & 0.0876 & 0.0630 & 0.0934 & 0.0787 & 0.0815 \\
%  & stopwords, $n$      &                                     \\
%  & stopwords, $\hat n$ &                                     \\
%  & indicator, $n$      &\\
%  & indicator, $\hat n$ &\\
%  & bigram              &\\
% \hline
% \multirow{7}{*}{10} 
%  & counts              & 0.2852 & 0.1835 & 0.2239 & 0.2713 & 0.1352 \\
%  & baseline            & 0.0835 & 0.0682 & 0.1104 & 0.0891 & 0.0617 \\
%  & stopwords, $n$      &                                     \\
%  & stopwords, $\hat n$ &\\
%  & indicator, $n$      &\\
%  & indicator, $\hat n$ &\\
%  & bigram              &\\
% \hline
% \multirow{7}{*}{20} 
%  & counts              & 0.2823 & 0.1737 & 0.1928 & 0.2533 & 0.1239 \\
%  & baseline            & 0.0839 & 0.0771 & 0.1005 & 0.0878 & 0.0602 \\
%  & stopwords, $n$      &\\
%  & stopwords, $\hat n$ &\\
%  & indicator, $n$      &\\
%  & indicator, $\hat n$ &\\
%  & bigram              &\\
% \end{tabular}
% \caption{Results of different heuristic-pruning strategy combinations on the
% medical dataset.}
% \label{table:20}
% \end{table*}

% \begin{table*}[ht]
% \centering
% \begin{tabular}{|lrrl|}
% \hline
% Domain  & s/d   & w/d   & Example \\
% \hline
% Medical &   8 &  153 & Pneumatic otoscopy confirms the presence of fluid in the middle ear. \\
% CIA     &  22 &  487 & The 324th has provided three regiments to South Vietnam. \\
% Email   &  11 &  228 & Please let me know when you have time to do another trial. \\
% Stock   &  13 &  400 & The Bank is wholly owned and is a state chartered bank. \\
% SW      & 111 & 1771 & B: boy uh it's a lot of work it seems. \\
% \hline
% \end{tabular}
% \caption{Statistics and example sentences from each domain. s/d = sentences per document; w/d = word tokens per document.}
% \label{table:domains}
% \end{table*}








% This makes sense: 

% Short documents can be recovered with reasonable success
% across 

% As the tables show, we can recover short documents with
% reasonable success. We can also recover documents, even long ones, from bigram
% count vectors with good success. Long documents, on the other hand, prove quite
% difficult to recover from unigram BOWs. This all makes sense: when the original
% document is short or the index preserves ordering constraints, the feasible set
% is small; this makes recovery easier. When the original document is long and
% the index discards ordering constraints, the feasible set is large and recovery
% is more difficult.  
% %Although document length appears to be the variable most strongly correlated with the recovery rate for unigram BOWs, other factors also have an effect.

% Even among unigram BOWs, the index type affects  Index For the case of index type, it is easiest to recover from count BOWs; indicator BOWs are harder, and stopwords-removed count BOWs are hardest of all. The 

% As one might expect, it is easier to recover documents from a
% count BOW than from a stopwords-removed count BOW or from an indicator BOW.

% One surprise: as a test, we performed \Astar search for stopwords-removed count
% BOWs and indicator BOWs where, instead of inferring document length, we used
% the true original document length. In this experiment, recovery under 

% But---a bit of a surprise---it is not that much easier. In particular, recovery from 

% It
% may be a bit of a surprise that indicator BOWs perform somewhat better than
% count BOWs.

% Still, other 

% the primary correlate
% with recovery score.

% the original document length is one of the most important 
% regardless of heuristic, pruning strategy, 

% As these tables show, regardless of heuristic, pruning
% strategy, or domain, the most important 

% We can recover documents with reasonable success under two conditions:
% if the original document is short or if the index is a bigram count vector.

% In table \ref{table:R1} we compare combinations of each of our heuristics,
% $\hadm$ and $\hemp$, with each of our pruning strategies (a)--(c) on the
% medical dataset. As the table shows, the empirical heuristic performs almost
% uniformly better than the admissible heuristic, at least on this dataset,
% although never by more than $0.1$. Is the improvement because $\hemp$ results
% in fewer search errors than $\hadm$--- due to pruning, these are possible even
% with $\hadm$---or because $\hemp$ ``randomly'' directs the search toward the
% original document better than $\hadm$ does? Table XXX, which shows the average
% score of each heuristic-prune strategy combination on the medical dataset,
% seems to indicate it is the former (\textit{hopefully, I think}).

% On the other hand, table \ref{table:R1} shows that pruning strategies (b),
% $\lambda\,l+g+h$, and (c), $(g+h)/l$, have about equal success. Both are
% substantially better than strategy (a), $g+h$. Table XXX shows that strategies
% (b) and (c) also result in much higher scores than strategy (a)
% (\textit{hopefully, I think}). This confirms our intuition that pruning causes
% much search error, so a better pruning strategy can result in a marked
% improvement. One important difference between strategies (b) and (c) is speed
% of decoding. Using strategy (b) and $\hadm$, decoding the medical dataset for
% $N =$ 1, 2, 4, and 16 takes over a day; using strategy (c), decoding takes
% about an hour. This difference seems to be because, as hypothesized in section
% \ref{sec:prunebacktracking}, strategy (c) is less prone to backtracking than
% strategy (b).

% Tables \ref{table:R2}--\ref{table:R7} compare results from decoding different
% index types from each of our datasets. For all these tests, we used heuristic
% $\hemp$ and prune strategy (c), since that combination seems to perform best in
% terms of results and speed. In table \ref{table:R2} we show results from
% decoding count BOWs, just as in the last column of table \ref{table:R1}, but on
% all datasets.\footnote{Results for the medical dataset with $N =$ 1 and 2 are
% slightly different between tables \ref{table:R1} and \ref{table:R2} because
% different samples were used.} In tables \ref{table:R4} and \ref{table:R6} we
% show results from decoding stopwords-removed count BOWs and indicator BOWs on
% all datasets, where we assume that we know the true document length $n$ for
% each document. As expected, recovery from stopwords-removed count BOWs and
% indicator BOWs is worse than recovery from simple count BOWs. Indeed, it is
% rather surprising that for short documents from some domains (medical, cia),
% recovery from stopwords-removed BOWs is nearly as good as recovery from simple
% count BOWs.

% Of course, it is unrealistic to assume that we know the true document length
% $n$ for stopwords-removed count BOWs and indicator BOWs. In tables
% \ref{table:R5} and \ref{table:R7} we show results when we use an estimate $\hat
% n$ of the document length. Results are somewhat worse, especially for short
% documents. On long documents, results are similar whether we use the true
% document length or the estimate.  Unfortunately, this similarity seems due to
% the fact that long documents decoded from stopword-removed BOWs tend to have
% long, nonsensical string of high-probability stopwords. When we know the true
% document length, this nonsense takes up more of the recovered document and the
% precision drops; when we use the estimate, the precision improves but the
% brevity penalty increases. The same phenomenon occurs with indicator BOWs; it
% is less pronounced because there are fewer high-probability stopwords to choose
% from.

% The above discussion assumes that our document-length estimates skew low. In
% fact, this is true, for both stopword-removed BOWs and indicator BOWs, as
% figures \ref{fig:stopwords_doclen} and \ref{fig:indicator_doclen} show.

% Table \ref{table:R8} is quite different than the others: results are quite
% good. This reflects the fact that a bigram count vector provides information
% about word order. When the bigram count vector's ordering information is
% combined with the language model's ordering information, we can exactly recover
% most documents with high accuracy.

% On the other hand, our results decoding unigram BOWs appear less than stellar.
% In fact, as table \ref{table:R2} shows, our results are a substantial
% improvement over results using our greedy baseline.  

% the best combination is an empiheuristic $\hemp$
% with pruning strategies (b), $\lambda\,l+g+h$, and (c), $(g+h)/l$, 

% To test our techniques, we sampled shorter documents of varying lengths from
% each original document. Each sample consists of $N$ contiguous sentences from
% an original document (or the whole document if it has fewer than $N$
% sentences). We then run experiments to see which heuristic-pruning strategy
% combination gives the best results. These are shown in table \ref{table:R1}.
% We ran other experiments to compare different reduced document conditions,
% shown in tables \ref{table:R2}--\ref{table:R8}.


% \subsubsection{Document length}

% We predicted document length for indicator BOWs using SVM$^{light}$ and a
% training corpus of documents similar to our test set. Predictions on our
% actual test set are in figure \ref{fig:indicator_doclen}. Predictions made by
% our stopwords estimator are in  figure\ref{fig:stopwords_doclen}. (This one
% isn't very good, actually ... .)

% \subsubsection{\Astar}

% To test our techniques, we sampled shorter documents of varying lengths from
% each original document. Each sample consists of $N$ contiguous sentences from
% an original document (or the whole document if the document has fewer than
% $N$ sentences). We then run experiments to see which heuristic-pruning
% strategy combination gives the best results. These are shown in table
% \ref{table:R1}. We ran other experiments to compare different reduced
% document conditions, shown in tables \ref{table:R3}--\ref{table:R8}.



% For example, suppose we have a bigram count vector $\xvec$ where
% $x_{\mathrm{a~rose}} = 2$ and $x_{\mathrm{is~a}} = x_{\mathrm{rose~is}} =
% x_{\mathrm{rose~.}} = x_{\mathrm{Sometimes~a}} = 1$. To create a stick starting
% with $t = \mathrm{rose~is}$, we extend rightward to $\mathrm{rose~is~a}$,
% $\mathrm{rose~is~a~rose}$, and $\mathrm{rose~is~a~rose~.}$, then leftward to
% $\mathrm{a~rose~is~a~rose~.}$.  We cannot extend leftward again to
% $\mathrm{is~a~rose~is~a~rose~.}$, since $\mathrm{is~a}$ has already been used.
% Hence we can extend leftward again to the only remaining choice,
% $\mathrm{Sometimes~a~rose~is~a~rose~.}$ \textit{This is a lousy example; change
% it.}

% ``is a rose is a''; each bigram token can be used only once per stick. (In
% practice, each sentence is wrapped in a $\Sbeg$ and $\Send$, and we add without
% loss of generality ``$\Dbeg$ $\Sbeg$'' and ``$\Send$ $\Dend$'' to every bigram
% BOW to avoid problems in certain cases.)

% $w_k,w_i,w_j$. On the other hand, if there exists a $w_k$ such that $x_{w_j,w_k}
% = 1$ exactly, we extend $t_i = w_i,w_j,w_k$. We repeat this procedure
% Then we try to extend $t_i$ to the right and to the left until there are no

% $\in \xvec$, we try t
% extend it to the right and to the left until there is more than one choice how
% to extend it. For example, starting from ``rose is'' we can extend rightward to
% ``rose is a'', then ``rose is a rose'' and leftward to ``a rose is a''. We
% cannot extend leftward again to ``is a rose is a''; each bigram token can be
% used only once per stick. (In practice, each sentence is wrapped in a $\Sbeg$
% and $\Send$, and we add without loss of generality ``$\Dbeg$ $\Sbeg$'' and
% ``$\Send$ $\Dend$'' to every bigram BOW to avoid problems in certain cases.)

% A bigram BOW is a set of bigrams tokens; for example $\bow($Sometimes a rose is
% a rose .$)$ = $\{$ a rose, a rose, is a, rose is, rose ., Sometimes a$\}$.
% Document length $D$ can be recovered exactly: $D = \mathrm{1}^\top \xvec+1$.

% Some of these bigrams overlap unambiguously. We can create ``sticks'',
% unambiguous phrases, as follows: for each bigram $v_1^2 \in \bow$, try to
% extend it to the right and to the left until there is more than one choice how
% to extend it. For example, starting from ``rose is'' we can extend rightward to
% ``rose is a'', then ``rose is a rose'' and leftward to ``a rose is a''. We
% cannot extend leftward again to ``is a rose is a''; each bigram token can be
% used only once per stick. (In practice, each sentence is wrapped in a $\Sbeg$
% and $\Send$, and we add without loss of generality ``$\Dbeg$ $\Sbeg$'' and
% ``$\Send$ $\Dend$'' to every bigram BOW to avoid problems in certain cases.)

% As the example above illustrates, the feasible set of a bigram count vector is
% in general much smaller than that of a unigram count vector. In fact, we can
% find the best document $\dvec^* \in F(\xvec)$ using best-first search, which is
% equivalent to \Astar search where $h = 1$ uniformly. Each partial path is
% scored using $g(w_1^l)$ as defined for unigram count BOWs. In the case of
% unigram BOWs, we extend a partial path by adding one word from the remaining
% BOW to the partial path; now, we extend a partial path by appending words from
% each stick drawn from the remaining BOW.  If the end of the partial path
% overlaps with the beginning of the stick, the overlap is discarded. (This may
% cause search error, if there are repeated words or phrases in the original
% document, as in, ``He said that that dog runs,'' and the overlap is not
% captured inside any stick; however this event is rare, and the other way to
% extend partial paths, by appending all words from each stick including overlap,
% causes much more search error.) 
% As a baseline, we recover a document by greedily appending the best unused
% word from the BOW at every position, starting at $w_1=\Sbeg$, the beginning
% of a sentence, and ending at $w_1^D=\Sbeg,w_2,...,w_{D-1},\Send$, where
% \[
% w_i = \argmax_{v:r_v>0} \log p(v|w_{i-4}^{i-1})
% %w_i = \argmin_{v \in V \backslash w_1^{i-1}} -\log p(v|w_{i-4}^{i-1})
% \]
% %for $i=1\dots D$,
% and $\rvec = \cvec(t_1^D)-\cvec(w_1^{i-1})$.
% %\footnote{We adopt the conventions $w_5|w_4^4=w_5|w_4$,
  %$w_5|w_5^4=w_5$, $w_1|w_{-4}^0=w_1$, $w_2|w_{-3}^1=w_2|w_1$, etc.}








% %
% \begin{align*}
% & s(w_i|w_{i-k+1}^{i-1}) \\
% &= \max{}_{j=1}^k \log \alpha^{j-1} p(w_i|w_{i-j+1}^{i-1}) \\
% &= \max{}_{j=1}^k \log \alpha^{j-1} 
%   \begin{cases}
%     \frac{c(w_{i-k+1}^i)}{c(w_{i-k+1}^{i-1})} & \mathrm{if}\, j > 1 \\
%     c(w_i)/\sum_{v\in V} c(v) & \mathrm{if}\, j = 1
%   \end{cases} \\
% &\geq p(w_i|w_{i-k+1}^{i-1}),
% %s(v_5|v_i^4) = \max{}_{j=1}^5 \log \alpha^{j-1} p(v_5|v_j^4) \geq p(v_5|v_j^4),
% \end{align*}
% %
% where $\alpha$ is the parameter used in stupid-backoff. In fact, $s(v_5|v_i^4)
% = p(v_5|v_i^4)$ unless $f(v_5|v_j)$ $f(v_5|v_j^4)$


% % In order to carry out the search efficiently we need a heuristic that is fast
% % but still gives reasonably good results. Several heuristics we tried were
% % either too slow to calculate or too far from the true cost to the goal.
% % \orange{need better transition}

% A heuristic is \textit{admissible} in \Astar search if it underestimates the
% cost of the best path from the current position to the goal. In our case, we
% seek a lower bound on the cost of extending $w_1^l$ to length $D$, that is, on 
% \[
% %\min_{w_{l+1}^D \in \perm(\bow \backslash w_1^l)} -\log p(w_{l+1}^D)
% -\max_{w_{l+1}^D \in \sigma(\rvec)} \log p(w_{l+1}^D),
% \]
% where $\rvec = \cvec(t_1^D)-\cvec(w_1^l)$. (This quantity is far too expensive
% to compute directly.) One possibility,
% \[
% %-\sum_{v_5 \in \bow \backslash w_1^l} 
% %min_{v_1^4 \in \perm(\bow \backslash w_1^{l-4})} \log p(v_5|v_1^4),
% -\sum_{v_5:r_{v_5}>0} \max_{v_1^4 \in \sigma(\cvec(t_1^D); 4)} \log p(v_5|v_1^4),
% \]
% is admissible, and much cheaper, but still impractical, since
% $\sigma(\cvec(t_1^D); 4)$ is of size $O(V^4)$.

% % compute the $\min$s for
% % every candidate $w_1^l$, and (b) $\perm(\bow \backslash w_1^{l-4})$ is a huge
% % set for small $l$. Problem (a) is avoided by
% % \[
% % h_2(w_1^l) = \sum_{v_5 \in \bow \backslash w_1^l} 
% %   \min_{v_1^4 \in \perm(\bow)} -\log p(v_5|v_1^4),
% % \]
% % since we can precompute the $\min$ for all $v_5 \in V$. Problem (b) is solved
% % by

% We avoid this computation by considering only histories that have nonzero
% $n$-gram counts. Let
% %
% \begin{align*}
% S(w_i|w_{i-k+1}^{i-1}) &= \max{}_{j=1}^k \log \alpha^{j-1} p(w_i|w_{i-j+1}^{i-1}) \\
% &\geq S(w_i|w_{i-k+1}^{i-1}),
% %S(v_5|v_i^4) = \max{}_{j=1}^5 \log \alpha^{j-1} p(v_5|v_j^4) \geq p(v_5|v_j^4),
% \end{align*}
% %
% where $\alpha$ is the parameter used in stupid-backoff. In fact, $S(v_5|v_i^4)
% = p(v_5|v_i^4)$ unless $f(v_5|v_j)$ $f(v_5|v_j^4)$

% \[
% S(v_5|v_i^4) = \min(-\log p(v_5|v_i^4), \alpha S(v_5|v_{i+1}^4)),
% \]

% \[
% h_3(w_1^l) = -\sum_{v_5 \in \bow \backslash w_1^l} \Sstar(v_5),
% \]
% where
% \[
%   \Sstar(v_5) = \min_{v_1^4 \in \perm(\bow)} S(v_5|v_1^4),
% \]
% and
% \[
% S(v_5|v_i^4) = \min(-\log p(v_5|v_i^4), \alpha S(v_5|v_{i+1}^4)),
% \]
% for $i = 1,\dots,4$, $S(v_5) = -\log p(v_5)$.  Heuristic $h_3$ is admissible,
% since $S(v_5|v_1^4) \geq -\log p(v_5|v_1^4)$ for all $v_1^5$ \orange{(should I
% give further proof?)}, and efficient, since $\Sstar$ can be computed for all
% $v_5 \in V$ in two passes through a list of n-gram counts. On the first pass,
% build a map from n-grams to counts. (5-grams can be ignored.) On the second
% pass, for every n-gram $v_1^n$ in the list, compute
% \[
% S' = \alpha^{5-n} \frac{c(v_1^n)}{c(v_1^{n-1})}.
% \]
% Compare $S'$ to $S^*(v_n)$, the best score for $v_n$ seen so far. If $S' >
% S^*(v_N)$, set $S^*(v_N) = S'$. (Initially set $S^*(v_N) = 0$.)



% In section \ref{sec:score},
% we define a score function. In sections
% \ref{sec:countbow}--\ref{sec:bigrambow}, we define a feasible set and a method
% for approximating $\dvec^*$ for each type of index.

% In what follows, we (a)
% construct $F(\xvec)$, define a $\mathrm{score}$ function,  $\argmax$ may be
% impractical
% to compute, even if $F(x)$ is  and $$ In what follows
% This $\argmax$ may be impossible to compute. In the sequel, we define a score
% and feasible for each 

% In the first and fourth cases, the document length $n$ is known. For a count
% BOW $\xvec$, $n = \mathbf{1}^\top \xvec$, the total number of times all word types
% occur (or: the total number of word tokens in the BOW). For a bigram count
% vector, $n = \mathbf{1}^\top \xvec + 1$, the total number of times all word types
% occur as the first member of a bigram, plus 1, since the last word in the
% document is not the first member of any bigram. In the second and third cases,
% the document length $n$ is unknown; in section ? we estimate it from the BOW.

% Once we know (or estimate) $n$, we can define a feasible set $F(\xvec)$, the
% set of documents that are consistent with $\xvec$. Specifics vary by index
% type, and are presented in each section. 

% The \textit{document recovery problem} is to find the best feasible document
% given an index:
% \[
%   \dvec^* = \argmax_{\dvec\in F(\x)} \mathrm{score}(\dvec)
% \]


% \[
% F(\xvec) = \{\dvec : |\dvec| = n, |\{w_i \in \dvec: w_i=v\}|=x_v\}
% \]
% \textit{this is just for count bow}.


% BONSW BO2G

%  The document
% length is known: $n = \mathbf{1}^\top \xvec$.

% In the case of a count BOW (without stopword removal), $n = \mathbf{1}^\top \xvec$.

% Let document $t_1^D=t_1,...,t_D$ be a sequence of length $D$, where each $t_i
% \in \{1,...,V\}$, and $V$ is the vocabulary size.  Then $\cvec(t_1^D) =
% (c_1,...,c_V) \in \mathbb{N}^V$ is a \textit{bag of words (BOW) count vector},
% where $c_v$ is the number of times that word $v$ occurs in $t_1^D$.


% Let $t_1^D=t_1,...,t_D$, an original document, be an ordered sequence of
% length $D$. A \textit{bag of words} (BOW) $B$ is a set of word tokens in
% $t_1^D$, i.e.  a multiset of word types.\footnote{The more frequent
% representation of a BOW as a count vector is inconvenient for us.}

% An \textit{indicator bag of words} is a set of word tokens, with no repeats.
% A \{stopwords-removed bag of words\} is one where stopwords have been
% removed.

% \section{Notation (temporary)}
% $v \in \{1,\dots,V\}$ -- a word in the vocabulary\\
% $\x = (x_1,\dots,x_V)$ -- a bag of words\\
% $\z$ -- an ordering of $\x$\\
% $\sigma(\x; l)$ -- set of unique orderings of sets $l$

% \[
% \sigma(\bow; l) = \cup_{l=1}^{|\bow|} \{\perm(x_1^l) : x_1^l \subseteq \bow\}
% \]

% $\sigma_l(\bow)$ -- a set of permutations of length $l$

% a length-$l$ permutation of BOW $x$\\

% Our problem is as follows: we seek 
% \[
% {w^*}_1^D = \argmax_{w_1^D\in \perm(\bow)} p(w_1^D),
% \]
% where $D$ is the document length.  \orange{(Actually
% this is not true. Should we formulate the problem in terms of BLEU? or edit
% distance to the true doc, etc.)}

% Our problem is as follows: we seek 
% \[
% {w^*}_1^D = \argmax_{w_1^D\in \perm(\bow)} \mathrm{distance}(w_1^D, \mathrm{true}_1^D),
% \]
% where $D$ is the document length, and $\mathrm{true}_1^D$ is the unknown
% original document.









% \subsection{Feasible set}

% In order for a document $\dvec$ to be in the feasible set $F(\xvec)$ of a count
% BOW $\xvec$, $\dvec$ must satisfy the following two conditions: (a) $|\dvec| =
% \mathbf{1}^\top \xvec = n$, the original document's length, and (b) each word $v$
% in the vocabulary must occur $\xvec_v$ times in $\dvec$. (In fact, (b) implies
% (a), but (a) will be useful later.) These conditions reflect the fact that
% given a count BOW we know precisely how many times each word type occurs in the
% original document.
% % condition: each word $v$ in the vocabulary must occur $\xvec_v$ times in
% % $\dvec$. This condition reflects the fact that we know precisely how many
% % times each word occurs in the original document. The condition implies 

