From Word Embeddings To Document Distances
MattJ.Kusner
MKUSNER
@
WUSTL
.
EDU
Yu Sun
YUSUN
@
WUSTL
.
EDU
Nicholas I. Kolkin
N
.
KOLKIN
@
WUSTL
.
EDU
Kilian Q.Weinberger
KILIAN
@
WUSTL
.
EDU
WashingtonUniversityinSt. Louis,1Brookings Dr.,St. Louis, MO63130
Abstract
WepresenttheWordMover’sDistance(WMD),
a novel distance function between text docu-
ments. Our work is based on recent results in
word embeddings that learn semantically mean-
ingful representations for words from local co-
occurrences in sentences. The WMD distance
measuresthe dissimilaritybetweentwotextdoc-
uments as the minimum amountofdistancethat
the embedded words of one document need to
“travel” toreach theembeddedwords ofanother
document. Weshowthatthisdistancemetriccan
be cast as aninstance of the Earth Mover’s Dis-
tance, a well studied transportation problem for
which severalhighly efficient solvers have been
developed. Our metric has no hyperparameters
andisstraight-forwardtoimplement. Further,we
demonstrateoneightrealworlddocumentclassi-
ficationdatasets,incomparisonwithsevenstate-
of-the-art baselines, that the WMD metric leads
to unprecedented low k-nearest neighbor docu-
mentclassificationerrorrates.
1. Introduction
Accurately representing the distance between two docu-
ments has far-reaching applications in document retrieval
(Salton&Buckley,1988),newscategorizationandcluster-
ing(Ontrup&Ritter,2001;Greene&Cunningham,2006),
song identification (Brochu&Freitas2002), and multi-
lingualdocumentmatching(Quadriantoetal.,2009).
The two most common ways documents are represented
is via a bag of words (BOW) or by their term frequency-
inversedocumentfrequency(TF-IDF). However,thesefea-
tures are often not suitable for document distances due to
Proceedings of the 32
nd
International Conference on Machine
Learning,Lille,France,2015. JMLR:W&CPvolume 37. Copy-
right2015bytheauthor(s).
‘Obama’
word2vec embedding
‘President’
‘speaks’
‘Illinois’
‘media’
‘greets’
‘press’
‘Chicago’
document 2
document 1
Obama
speaks
to
the
media
in
Illinois
The
President
greets
the
press
in
Chicago
Figure1.An illustration of the word mover’s distance. All
non-stop words (bold) of both documents are embedded into a
word2vecspace. The distancebetween the two documentsisthe
minimum cumulative distancethatall wordsin document 1need
totraveltoexactlymatchdocument2. (Bestviewedincolor.)
their frequent near-orthogonality (Sch¨olkopfetal.2002;
Greene & Cunningham, 2006). Anothersignificantdraw-
back of these representations are that they do not capture
the distance between individual words. Take for example
the two sentences in different documents: Obama speaks
tothemediainIllinoisand: ThePresidentgreets thepress
inChicago. While these sentences have no words in com-
mon, they conveynearlythe same information, a fact that
cannotberepresentedbytheBOWmodel. Inthiscase, the
closeness ofthe wordpairs: (Obama, President); (speaks,
greets); (media, press); and(Illinois, Chicago) is not fac-
toredintotheBOW-baseddistance.
Therehavebeennumerousmethodsthatattempttocircum-
ventthisproblembylearningalatentlow-dimensionalrep-
resentationofdocuments. LatentSemanticIndexing(LSI)
(Deerwesteretal.,1990)eigendecomposes the BOWfea-
ture space, and Latent Dirichlet Allocation (LDA) (Blei
etal.,2003)probabilisticallygroupssimilarwordsintotop-
icsandrepresentsdocumentsasdistributionoverthesetop-
ics. At the same time, there are many competing vari-
ants of BOW/TF-IDF (Salton& Buckley1988;Robert-
son & Walker, 1994). Whiletheseapproachesproducea
more coherent document representation than BOW, they
often do not improve the empirical performance ofBOW
ondistance-based tasks (e.g., nearest-neighbor classifiers)
(Pettersonetal.,2010;Mikolovetal.,2013c).
How to convert pdf file to html - software SDK dll:C# PDF Convert to HTML SDK: Convert PDF to html files in C#.net, ASP.NET MVC, WinForms, WPF application
How to Convert PDF to HTML Webpage with C# PDF Conversion SDK
www.rasteredge.com
How to convert pdf file to html - software SDK dll:VB.NET PDF Convert to HTML SDK: Convert PDF to html files in vb.net, ASP.NET MVC, WinForms, WPF application
PDF to HTML Webpage Converter SDK for VB.NET PDF to HTML Conversion
www.rasteredge.com
FromWordEmbeddingsToDocumentDistances
Inthispaperweintroduceanewmetricforthedistancebe-
tween text documents. Our approach leverages recent re-
sultsbyMikolovetal.(2013b)whosecelebratedword2vec
model generateswordembeddings ofunprecedented qual-
ityandscalesnaturallytovery largedatasets(e.g., weuse
afreely-available modeltrainedonapproximately100bil-
lion words). The authors demonstrate that semantic rela-
tionships are often preserved invector operations on word
vectors, e.g., vec(Berlin) - vec(Germany) + vec(France)
is close to vec(Paris). This suggests that distances and
between embedded word vectors are to some degree se-
mantically meaningful. Our metric, which we call the
Word Mover’s Distance (WMD), utilizes this property of
word2vec embeddings. We represent text documents as a
weightedpointcloudofembeddedwords. Thedistancebe-
tweentwotext documents AandB is the minimum cumu-
lative distance that words from document Aneedtotravel
tomatch exactly the point cloud of document B. Figure1
showsaschematicillustrationofournewmetric.
The optimization problem underlying WMD reduces to
a special case of the well-studied Earth Mover’s Dis-
tance (Rubner et al.1998) transportation problem and
we can leverage existing literature on fast specialized
solvers (Pele&Werman,2009). We alsocompare several
lower bounds and showthatthesecan be usedas approxi-
mations ortopruneaway documents that are provablynot
amongstthek-nearest neighborsofaquery.
The WMD distance has several intriguing properties: 1.
itis hyper-parameterfree andstraight-forwardto under-
stand and use; 2. it is highly interpretable as the dis-
tance between two documents can be broken down and
explained as the sparse distances between few individual
words; 3. itnaturallyincorporates the knowledge encoded
in the word2vec space and leads to high retrieval accu-
racy—it outperforms all 7state-of-the-art alternativedoc-
umentdistancesin6of8realworldclassificationtasks.
2. Related Work
Constructinga distance betweendocuments is closelytied
with learning new document representations. One of the
first works to systematically study different combinations
ofterm frequency-based weightings, normalization terms,
and corpus-based statistics is Salton& Buckley (1988).
Anothervariationis the Okapi BM25 function (Robertson
&Walker, 1994)whichdescribesascoreforeach(word,
document) pair and is designed for ranking applications.
Aslam &Frost(2003)deriveaninformation-theoreticsim-
ilarityscore betweentwodocuments, based on probability
ofwordoccurrenceinadocumentcorpus.Croft&Lafferty
(2003)usealanguagemodel to describetheprobabilityof
generating a word from a document, similar to LDA(Blei
et al., 2003). Mostsimilartoourmethodisthatof Wan
(2007)whichfirstdecomposeseachdocumentintoasetof
subtopicunitsviaTextTiling(Hearst,1994),andthenmea-
sures the effort required to transform a subtopic set into
anothervia theEMD(Monge,1781;Rubneretal.,1998).
New approaches for learning document representations
include Stacked Denoising Autoencoders (SDA) (Glorot
et al., 2011), and the e fastermSDA(Chen et al., 2012),
whichlearnwordcorrelations viadropoutnoiseinstacked
neural networks. Recently, the Componential Counting
Grid (Perinaetal.,2013) merges LDA (Bleietal.,2003)
and Counting Grid (Jojic&Perina,2011) models, allow-
ing ‘topics’tobe mixtures ofword distributions. As well,
Le& Mikolov(2014)learnadenserepresentationfordoc-
uments usinga simplified neurallanguage model, inspired
bytheword2vecmodel(Mikolovetal.,2013a).
TheuseoftheEMDhasbeenpioneeredinthecomputervi-
sion literature(Rubneretal.,1998;Renetal.,2011). Sev-
eral publications investigate approximations of the EMD
forimageretrievalapplications (Grauman&Darrell,2004;
Shirdhonkar& Jacobs, 2008; Levina & Bickel, 2001). As
word embeddings improve in quality, document retrieval
enters an analogous setup, where each word is associated
withahighlyinformativefeaturevector. Toourknowledge,
our work is the first to make the connection betweenhigh
qualitywordembeddingsandEMDretrievalalgorithms.
Cuturi(2013)introducesanentropypenaltytotheEMD
objective, which allows the resulting approximation to be
solvedwithveryefficientiterativematrixupdates. Further,
thevectorizationenablesparallelcomputationviaGPGPUs
However, their approach assumes that the number of di-
mensions per document is not too high, which in our set-
ting is extremelylarge(allpossible words). This removes
the main benefit (parallelization on GPGPUs) oftheir ap-
proach and sowedevelop anew EMDapproximationthat
appears tobeveryeffectiveforourproblemdomain.
3. Word2Vec Embedding
RecentlyMikolovetal.(2013a;b) introducedword2vec, a
novel word-embedding procedure. Their model learns a
vector representationforeachwordusinga (shallow)neu-
ral network language model. Specifically, they propose a
neuralnetworkarchitecture(theskip-grammodel)thatcon-
sists of an input layer, a projection layer, and an output
layertopredict nearbywords. Eachwordvectoris trained
tomaximizethelogprobabilityofneighboring words ina
corpus, i.e., givenasequenceofwordsw
1
;:::;w
T
,
1
T
XT
t=1
X
j2nb(t)
logp(w
j
jw
t
)
wherenb(t)isthesetofneighboringwordsofwordw
t
and
p(w
j
jw
t
)isthehierarchicalsoftmaxoftheassociatedword
software SDK dll:Online Convert PDF to HTML5 files. Best free online PDF html
Download Free Trial. Convert a PDF file to HTML. Just upload your file by clicking on the blue button or drag-and-drop your pdf file into the drop area.
www.rasteredge.com
software SDK dll:VB.NET PDF File Compress Library: Compress reduce PDF size in vb.
Convert smooth lines to curves. Detect and merge image fragments. Flatten visible layers. VB.NET Demo Code to Optimize An Exist PDF File in Visual C#.NET Project
www.rasteredge.com
FromWordEmbeddingsToDocumentDistances
vectors v
w
j
andv
w
t
(seeMikolovetal.(2013a)for more
details). Duetoits surprisinglysimplearchitectureandthe
use of the hierarchical softmax, the skip-gram model can
be trained on a single machine on billions of words per
hour using a conventional desktop computer. The ability
to train on very large data sets allows the model to learn
complexwordrelationshipssuchasvec(Japan)-vec(sushi)
+ vec(Germany)  vec(bratwurst) and vec(Einstein) -
vec(scientist) + vec(Picasso)  vec(painter) (Mikolov
et al., 2013a;b). Learningthewordembeddingisentirely
unsupervised anditcan be computed on thetext corpus of
interest orbe pre-computed inadvance. Although we use
word2vec as our preferred embedding throughout, other
embeddings arealsoplausible (Collobert&Weston,2008;
Mnih& Hinton,2009;Turianetal.,2010).
4. Word Mover’s Distance
Assumewe are provided with a word2vecembeddingma-
trixX2R
dn
forafinitesizevocabularyofnwords. The
i
th
column, x
i
2R
d
,represents the embedding ofthe i
th
word in d-dimensional space. We assume textdocuments
are representedas normalized bag-of-words (nBOW)vec-
tors, d2Rn. Tobe precise, ifwordi appears c
i
times in
the document, wedenote d
i
=
c
i
P
n
j=1
c
j
. An nBOW vector
disnaturallyverysparseas mostwords willnotappearin
any given document. (We remove stop words, which are
generallycategoryindependent.)
nBOW representation. We can think of the vector d as
apointonthen 1 dimensionalsimplex ofworddistribu-
tions. Twodocuments withdifferent uniquewords will lie
in different regions of this simplex. However, these doc-
uments may still be semantically close. Recall the earlier
exampleoftwosimilar, butword-differentsentencesinone
document: “Obamaspeaks tothe mediainIllinois” and in
another:“ThePresidentgreetsthepressinChicago”. After
stop-word removal, the twocorresponding nBOW vectors
dandd
0
have nocommonnon-zerodimensionsandthere-
fore have close to maximum simplex distance, although
theirtrue distanceis small.
Word travel cost. Our goal is to incorporate the seman-
tic similarity between individual word pairs (e.g. Presi-
dent andObama) intothe document distancemetric. One
suchmeasureofworddissimilarityisnaturallyprovidedby
theirEuclideandistanceintheword2vecembeddingspace.
Moreprecisely,thedistancebetweenwordiandwordjbe-
comes c(i;j) = kx
i
x
j
k
2
. To avoidconfusion between
wordanddocumentdistances, wewillrefertoc(i;j)asthe
costassociatedwith“traveling” from onewordtoanother.
Documentdistance. The “travelcost”betweentwowords
isanaturalbuildingblocktocreateadistancebetweentwo
documents. Let d and d
0
be the nBOW representation of
The President greets the press in Chicago.
Obama speaks in Illinois.
1.30
D
1
D
2
D
3
D
0
D
0
The President greets the press in Chicago.
Obama speaks to the media in Illinois.
The band gave a concert in Japan.
0.49
0.42
0.44
0.20
0.24
0.45
1.07
1.63
+
+
=
=
+
+
+
0.28
0.18
+
Figure2.(Top:) Thecomponents ofthe WMDmetric between a
queryD
0
andtwosentencesD
1
;D
2
(withequalBOWdistance).
The arrows represent flow between two words and are labeled
withtheirdistancecontribution. (Bottom:) The flowbetweentwo
sentencesD
3
andD
0
withdifferentnumbersofwords. Thismis-
matchcausestheWMDtomovewordstomultiplesimilarwords.
two text documents in the (n   1)-simplex. First, we al-
low each word i in d to be transformed into any word in
d
0
in total or in parts. Let T2 R
nn
be a (sparse) flow
matrix where T
ij
0 denotes how much of word i in d
travelstowordj ind
0
.Totransform dentirelyinto d
0
we
ensurethattheentire outgoingflowfromwordiequalsd
i
,
i.e.
P
j
T
ij
=d
i
. Further, the amount of incoming flow
to word j must match d0
j
,i.e.
P
i
T
ij
=d0
j
. Finally, we
candefine the distance between the two documents as the
minimum (weighted) cumulative cost required to move all
words from dtod
0
,i.e.
P
i;j
T
ij
c(i;j).
Transportation problem. Formally, the minimum cumu-
lative cost of moving d tod
0
given the constraints is pro-
videdbythesolutiontothefollowinglinearprogram,
min
T0
Xn
i;j=1
T
ij
c(i;j)
subjectto:
Xn
j=1
T
ij
=d
i
8i2 f1;:::;ng
(1)
Xn
i=1
T
ij
=d
0
j
8j 2 f1;:::;ng:
The above optimization is a special case of the earth
mover’s distance metric (EMD) (Monge1781Rubner
et al., 1998; Nemhauser & Wolsey, 1988),awellstudied
transportation problem for which specialized solvers have
been developed (Ling& Okada2007;Pele& Werman,
2009).Tohighlightthisconnectionwerefertotheresulting
metric as the word mover’s distance (WMD). As the cost
c(i;j)isametric, itcanreadilybeshownthattheWMDis
alsoametric(Rubneretal.,1998).
Visualization. Figure2 illustrates the WMD metric on
twosentencesD
1
andD
2
whichwewouldliketocompare
software SDK dll:VB.NET PDF File Merge Library: Merge, append PDF files in vb.net
Professional VB.NET PDF file merging SDK support Visual Studio .NET. Merge PDF without size limitation. Append one PDF file to the end of another one in VB.NET.
www.rasteredge.com
software SDK dll:C# PDF File Split Library: Split, seperate PDF into multiple files
Application. Best and professional adobe PDF file splitting SDK for Visual Studio .NET. outputOps); Divide PDF File into Two Using C#.
www.rasteredge.com
FromWordEmbeddingsToDocumentDistances
to the query sentence D
0
. First, stop-words are removed,
leaving President, greets, press, Chicagoin D
0
eachwith
d
i
=0:25. The arrows from each word i in sentences D
1
and D
2
towordj inD
0
are labeledwiththeircontribution
to the distance T
ij
c(i;j). We note that the WMD agrees
withourintuition, and“moves”wordstosemanticallysim-
ilar words. Transforming Illinois into Chicago is much
cheaper than is Japan into Chicago. This is because the
word2vec embedding places the vector vec(Illinois)closer
to vec(Chicago) than vec(Japan). Consequently, the dis-
tancefrom D
0
toD
1
(1:07)is significantlysmallerthan to
D
2
(1:63). Importantly however, both sentences D
1
and
D
2
havethesamebag-of-words/TF-IDFdistancefrom D
0
,
asneithersharesanywords incommonwithD
0
.Anaddi-
tional example D
3
highlights theflowwhenthenumberof
words does notmatch. D
3
hasterm weights d
j
=0:33and
excess flow is sent to othersimilar words. This increases
thedistance,althoughtheeffectmightbeartificiallymagni-
fiedduetotheshortdocumentlengthsaslongerdocuments
maycontainseveralsimilarwords.
4.1.FastDistance Computation
ThebestaveragetimecomplexityofsolvingtheWMDop-
timizationproblemscalesO(p
3
logp),wherepdenotesthe
number of unique words in the documents (Pele&Wer-
man, 2009). Fordatasetswithmanyuniquewords(i.e.,
high-dimensional) and/or a large number of documents,
solving the WMD optimal transport problem can become
prohibitive. Wecanhoweverintroduceseveralcheaplower
bounds oftheWMDtransportationproblem thatallows us
toprune away the majority of the documents without ever
computingthe exactWMDdistance.
Word centroid distance. Following the work ofRubner
etal.(1998)itisstraight-forwardtoshow(viathetriangle
inequality)thatthe‘centroid’distancekXd Xd
0
k
2
must
lowerboundtheWMDbetweendocuments d;d
0
,
Xn
i;j=1
T
ij
c(i;j) =
Xn
i;j=1
T
ij
kx
i
x
0
j
k
2
=
Xn
i;j=1
kT
ij
(x
i
x
0
j
)k
2
Xn
i;j=1
T
ij
(x
i
x
0
j
)
2
=
Xn
i=1
Xn
j=1
T
ij
x
i
Xn
j=1
Xn
i=1
T
ij
x
0
j
2
=
Xn
i=1
d
i
x
i
Xn
j=1
d
0
j
x
0
j
2
=kXd Xd
0
k
2
:
We refer to this distance as the Word Centroid Distance
(WCD) as each document is represented by its weighted
average word vector. It is very fast to compute via a few
matrix operations and scales O(dp). For nearest-neighbor
applications we can use this centroid-distance to inform
our nearest neighbor search about promising candidates,
which allows us to speed up the exact WMD search sig-
nificantly. We can also use WCD to limit our k-nearest
neighborsearchtoasmallsubsetofmostpromisingcandi-
dates, resultinginanevenfasterapproximatesolution.
Relaxed word moving distance. Although the WCD is
fast to compute, it is not very tight (see section5). We
canobtainmuchtighterboundsbyrelaxingtheWMDopti-
mizationproblem andremovingoneofthetwoconstraints
respectively (removing bothconstraints results in the triv-
ial lower bound T = 0.) If just the second constraint is
removed, theoptimizationbecomes,
min
T0
Xn
i;j=1
T
ij
c(i;j)
subjectto:
Xn
j=1
T
ij
=d
i
8i2f1;:::;ng:
This relaxed problem must yield a lower-bound to the
WMD distance, which is evident from the fact that every
WMDsolution(satisfyingboth constraints)must remaina
feasible solutionifone constraintis removed.
The optimal solution is foreach word ind to move allits
probabilitymass tothe mostsimilarwordind
0
.Precisely,
anoptimalT
matrixis definedas
T
ij
=
(
d
i
ifj = argmin
j
c(i;j)
0otherwise:
(2)
Theoptimalityofthis solutionisstraight-forwardtoshow.
Let T be anyfeasible matrix forthe relaxed problem, the
contribution to the objective value for any word i, with
closestwordj = argmin
j
c(i;j), cannotbesmaller:
X
j
T
ij
c(i;j)
X
j
T
ij
c(i;j
)= c(i;j
)
X
j
T
ij
=c(i;j
)d
i
=
X
j
T
ij
c(i;j):
Therefore, T
must yield a minimum objective value.
Computingthissolutionrequires onlythe identification of
j
= argmin
i
c(i;j), which is a nearest neighbor search
in the Euclidean word2vec space. For each word vec-
tor x
i
in document D we need to find the most simi-
lar word vector x
j
in document D
0
. The second setting,
when the first constraint is removed, is almost identical
except that the nearest neighbor search is reversed. Both
lower bounds ultimately relyonpairwise distancecompu-
tations betweenword vectors. These computations canbe
combined and reused to obtain both bounds jointly at lit-
tle additional overhead. Let the two relaxed solutions be
1
(d;d0) and ‘
2
(d;d0) respectively. We can obtain an
software SDK dll:VB.NET PDF Convert to Jpeg SDK: Convert PDF to JPEG images in vb.
Convert PDF to Tiff; C#: Convert PDF to HTML; C#: Convert PDF to Jpeg; C# File: Compress PDF; C# File: Merge PDF; C# File: Split PDF;
www.rasteredge.com
software SDK dll:VB.NET PDF File Split Library: Split, seperate PDF into multiple
Professional VB.NET PDF file splitting SDK for Visual Studio and .NET framework 2.0. Split PDF file into two or multiple files in ASP.NET webpage online.
www.rasteredge.com
FromWordEmbeddingsToDocumentDistances
even tighter bound by taking the maximum of the two,
r
(d;d
0
)= max(‘
1
(d;d
0
);‘
2
(d;d
0
)), which we refer to
astheRelaxedWMD(RWMD).Thisboundissignificantly
tighterthanWCD. Thenearest neighbor searchhas atime
complexityofO(p2), anditcanbespedupfurtherbylever-
aging out-of-the-box tools for fast (approximate or exact)
nearest neighbor retrieval (Garcia etal.2008;Yianilos,
1993; Andoni&Indyk, 2006).
Prefetch and prune. Wecan use the twolowerbounds to
drasticallyreducetheamount ofWMDdistance computa-
tionsweneedtomake inordertofindthek nearestneigh-
borsofaquerydocument. Wefirstsortalldocumentsinin-
creasingorderoftheir(extremelycheap)WCDdistance to
thequerydocumentandcomputetheexactWMDdistance
to the first k of these documents. Subsequently, we tra-
versetheremainingdocuments. Foreachwe firstcheck if
theRWMDlowerboundexceedsthedistanceofthecurrent
k
th
closestdocument, ifsowecanpruneit. Ifnot,wecom-
putetheWMDdistanceandupdatetheknearestneighbors
if necessary. As the RWMD approximation is very tight,
itallows us topruneup to 95% ofalldocuments on some
data sets. Iftheexact knearestneighborsarenotrequired,
an additional speedup can be obtained if this traversal is
limitedtom<n documents. We referto this algorithm as
prefetchandprune. Ifm=k, thisisequivalenttoreturning
thek nearestneighborsoftheWCDdistance. Ifm=n itis
exactasonlyprovablynon-neighborsarepruned.
5. Results
We evaluate the word mover’s distance in the context
of kNN classification on eight benchmark document cat-
egorization tasks. We first describe each dataset and
a set of classic and state-of-the-art document represen-
tations and distances. We then compare the nearest-
neighborperformance ofWMD and the competing meth-
ods on these datasets. Finally, we examine how the fast
lower bounddistances canspeedupnearest neighbor com-
putation by prefetching and pruning neighbors. Mat-
lab code for the WMD metric is available athttp://
matthewkusner.com
5.1.DatasetDescriptionand Setup
We evaluate all approaches on 8 supervised document
datasets:
BBCSPORT
: BBC sports articles between 2004-
2005,
TWITTER
: a set of tweets labeled with sentiments
‘positive’, ‘negative’, or ‘neutral’ (Sanders2011) (the
set is reduced due to the unavailability of some tweets),
RECIPE
: a set of recipe procedure descriptions labeled by
their region of origin,
OHSUMED
: a collection of medi-
cal abstracts categorized by different cardiovascular dis-
ease groups (for computational efficiency we subsample
thedataset,usingthefirst10classes),
CLASSIC
:setsofsen-
Table 1. Dataset characteristics,usedinevaluation.
BOW
UNIQUE
NAME
n
DIM
.
WORDS
(
AVG
) jYj
BBCSPORT
517
13243
117
5
TWITTER
2176
6344
9:9
3
RECIPE
3059
5708
48:5
15
OHSUMED
3999
31789
59:2
10
CLASSIC
4965
24277
38:6
4
REUTERS
5485
22425
37:1
8
AMAZON
5600
42063
45:0
4
20
NEWS
11293
29671
72
20
tences from academic papers, labeled by publisher name,
REUTERS
: a classic news dataset labeled by news topics
(weusethe8-classversionwithtrain/testsplitasdescribed
inCardoso-Cachopo(2007)),
AMAZON
:a set of Amazon
reviews whichare labeledby category productin fbooks,
dvd, electronics, kitcheng (as opposed to by sentiment),
and 20
NEWS
: news articles classified into 20 different
categories (we use the “bydate” train/test splitCardoso-
Cachopo(2007)). Wepreprocessalldatasetsbyremoving
allwordsintheSMART stopwordlist(Salton&Buckley,
1971).For20
NEWS
,weadditionallyremoveallwordsthat
appear less than 5 times across alldocuments. Finally, to
speedup thecomputationofWMD(and its lowerbounds)
welimitall 20
NEWS
documents tothe most common500
words (ineachdocument)forWMD-basedmethods.
Wespliteachdatasetintotrainingandtestingsubsets(ifnot
alreadydone so). Table1showsrelevantstatistics foreach
of these training datasets including the number of inputs
n, the bag-of-words dimensionality, the average number
ofunique words perdocument, andthenumberofclasses
jYj. The word embedding used in our WMD implemen-
tation is the freely-available word2vec word embedding
2
whichhasanembeddingfor3millionwords/phrases(from
GoogleNews), trainedusingtheapproachinMikolovetal.
(2013b). Words that are not present in the pre-computed
word2vecmodelare droppedfortheWMDmetric(andits
lower bounds), but kept for all baselines (thus giving the
baselines aslightcompetitive advantage).
We compare against7documentrepresentationbaselines:
bag-of-words (BOW). Avectorofwordcounts ofdimen-
sionalityd, thesizeofthedictionary.
TFIDF term frequency-inverse document frequency
(Salton&Buckley,1988): the bag-of-words representa-
tiondividedbyeachword’sdocumentfrequency.
BM25Okapi:(Robertsonetal.,1995)arankingfunction
thatextends TF-IDF foreachwordw ina documentD:
BM25(w;D) =
IDF(w)TF(w;D)(k
1
+1)
TF(w;D)+k
1
(1 b+b
jDj
D
avg
)
whereIDF(w)istheinversedocumentfrequencyofword
1
http://qwone.com/
˜
jason/20Newsgroups/
2
https://code.google.com/p/word2vec/
software SDK dll:C# PDF File Compress Library: Compress reduce PDF size in C#.net
All object data. File attachment. Hidden layer content. Convert smooth lines to curves. Flatten visible layers. C#.NET DLLs: Compress PDF Document.
www.rasteredge.com
software SDK dll:C# PDF File Merge Library: Merge, append PDF files in C#.net, ASP.
Professional C#.NET PDF SDK for merging PDF file merging in Visual Studio .NET. Append one PDF file to the end of another and save to a single PDF file.
www.rasteredge.com
FromWordEmbeddingsToDocumentDistances
1
2
3
4
5
6
7
8
0
10
20
30
40
50
60
70
recipe
ohsumed
classic
reuters
amazon
test error %
43
33
44
33
32
32
29
66
63
61
49
51
44
36
8.0
9.7
62
44
41
35
6.9
5.0
6.7
2.8
33
29
14
8.1
6.9
6.3
3.5
59
42
28
14
17
12
9.3
7.4
34
17
22
21
8.4
6.4
4.3
21
4.6
53
53
59
54
48
45
43
51
56
54
58
36
40
31
29
27
20news
bbcsport
k-nearest neighbor error
BOW [Frakes & Baeza-Yates, 1992] 
TF-IDF [Jones, 1972]
Okapi BM25 [Robertson & Walker, 1994]
LSI [Deerwester et al., 1990]
LDA [Blei et al., 2003]
mSDA [Chen et al., 2012]
Componential Counting Grid [Perina et al., 2013]
Word Mover's Distance
Figure3.ThekNNtesterrorresultson8documentclassificationdatasets,comparedtocanonicalandstate-of-the-artbaselinesmethods.
1
2
3
4
5
6
7
8
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
average error w.r.t. BOW
1.6
1.4
1.2
1.0
0.8
0.6
0.4
0.2
0
1.29
1.15
1.0
0.72
0.60
0.55
0.49
0.42
BOW 
TF-IDF 
Okapi BM25
LSI 
LDA 
mSDA 
CCG
WMD
Figure4.The kNNtest errorsofvariousdocumentmetricsaver-
agedoveralleightdatasets,relativetokNNwithBOW.
w, TF(w;D) is its term frequency indocumentD, jDjis
the numberofwords inthe document, D
avg
istheaverage
sizeofa document, andk
1
andbarefreeparameters.
LSILatentSemanticIndexing(Deerwesteretal.,1990):
usessingularvaluedecompositionontheBOWrepresenta-
tiontoarriveatasemanticfeaturespace.
LDA Latent Dirichlet Allocation (Bleietal.,2003): a
celebratedgenerativemodelfortext documents thatlearns
representations for documents as distributions over word
topics. We use the Matlab Topic Modeling Toolbox
Steyvers & Griffiths(2007)andallow100iterationsfor
burn-in and run the chain for 1000 iterations afterwards.
Importantly, foreachdatasetwetrainLDA transductively,
i.e. wetrainonthe unionofthetrainingandholdoutsets.
mSDA Marginalized Stacked Denoising Autoencoder
(Chenetal.,2012): a representationlearnedfrom stacked
denotingautoencoders(SDAs), marginalizedforfasttrain-
ing. In general, SDAs have been shown to have state-of-
the-artperformance fordocumentsentimentanalysistasks
(Glorotetal.,2011). For high-dimensional datasets (i.e.,
all except
BBCSPORT
,
TWITTER
,and
RECIPE
)we use ei-
ther the high-dimensional version of mSDA (Chenetal.,
2012)orlimitthefeaturestothetop20%ofthewords(or-
deredbyoccurence),whicheverperforms better.
CCG Componential Counting Grid (Perina et t al.,
Table2.Testerrorpercentageandstandarddeviationfordifferent
text embeddings. NIPS,AMZ,Newsareword2vec(w2v)models
trainedondifferentdatasetswhereasHLBLand Collowere also
obtainedwithotherembeddingalgorithms.
D
OCUMENT
k-
NEARESTNEIGHBOR RESULTS
DATASET
HLBL
CW
NIPS
AMZ
N
EWS
(
W
2
V
) (
W
2
V
) (
W
2
V
)
BBCSPORT
4:5
8:2
9:5
4:1
5:0
TWITTER
33:3
33:7
29:3
28:1
28:3
RECIPE
47:0
51:6
52:7
47:4
45:1
OHSUMED
52:0
56:2
55:6
50:4
44:5
CLASSIC
5:3
5:5
4:0
3:8
3:0
REUTERS
4:2
4:6
7:1
9:1
3:5
AMAZON
12:3
13:3
13:9
7:8
7:2
2013): a a generative model that directly generalizes s the
CountingGrid (Jojic&Perina,2011), which models doc-
uments as a mixture ofworddistributions, and LDA(Blei
etal., 2003).Weusethegridlocationadmixtureprobabil-
ityofeachdocumentasthenewrepresentation.
Foreach baseline we use the Euclidean distance forkNN
classification. All free hyperparameters were set with
Bayesian optimization for all algorithms (Snoek et t al.,
2012). WeusetheopensourceMATLABimplementation
“bayesopt.m”fromGardneretal.(2014).
3
5.2.Documentclassification
Documentsimilarities areparticularlyusefulforclassifica-
tion given a supervised training dataset, via the kNN de-
cision rule (Cover& Hart1967). Different from other
classification techniques, kNN provides an interpretable
certificate (i.e., in the form of nearest neighbors) that al-
lowpractitioners the ability to verifythepredictionresult.
Moreover, such similarities can be used for ranking and
recommendation. To assess the performance of our met-
ric on classification, we compare the kNN results of the
WMD with each of the aforementioned document repre-
sentations/distances. For all algorithms we split the train-
3
http://tinyurl.com/bayesopt
FromWordEmbeddingsToDocumentDistances
1
0
0.2
0.4
0.6
0.8
1
1.2
0
0.2
0.4
0.6
0.8
1
1.2
1.2
1.0
0.8
0.6
0.4
0.2
RWMD
WMD
WCD
RWMD
RWMD
0.93
0.56 0.54
0.45
0.42
0
average kNN error w.r.t. BOW
c1
c2
1.2
1.0
0.8
0.6
0.4
0.2
RWMD
WMD
WCD
RWMD
RWMD
0.92 0.92
0.30
0.96
1.0
0
average distance w.r.t. WMD
c1
c2
Figure5.(Left:)Theaverage distancesoflowerboundsasaratio
w.r.t WMD. (Right:) kNNtest error resultson 8 datasets, com-
paredtocanonical andstate-of-the-artbaselinemethods.
ing set into a 80/20 train/validation for hyper-parameter
tuning. It is worthemphasizingthat BOW, TF-IDF, BM25
and WMD have nohyperparametersand thus we onlyop-
timizetheneighborhoodsize(k 2f1;:::;19g)ofkNN.
Figure3showsthe kNNtesterrorofthe 8aforementioned
algorithms on the 8 document classification datasets. For
datasets without predefined train/test splits (
BBCSPORT
,
TWITTER
,
RECIPE
,
CLASSIC
,
AMAZON
)we averagedover
5train/testsplits and we reportmeansandstandard errors.
We orderthe methods by theiraverage performance. Per-
haps surprisingly, LSI and LDA outperform the more re-
cent approaches CCG and mSDA. For LDA this is likely
because it is trained transductively. One explanation for
why LSI performs so wellmay be the power ofBayesian
Optimization to tune the single LSI hyperparameter: the
numberofbasis vectors touseintherepresentation. Fine-
tuningthenumberoflatentvectors mayallowLSItocreate
averyaccuraterepresentation. Onall datasets except two
(
BBCSPORT
,
OHSUMED
), WMD achieves the lowest test
error. Notably, WMDachieves almost a10% reduction in
(relative) error over the second best method on
TWITTER
(LSI). It evenreaches error levels as lowas 2:8% error on
classic and 3:5% error on
REUTERS
, even outperforming
transductive LDA, which has direct access to the features
ofthetestset. Onepossibleexplanationforthe WMDper-
formance on
OHSUMED
is that many of these documents
containtechnicalmedicaltermswhichmaynothaveaword
embedding in ourmodel. These words mustbe discarded,
possiblyharmingthe accuracyofthemetric.
Figure4shows the average improvementofeach method,
relative to BOW, across all datasets. On average, WMD
results inonly0:42oftheBOWtest-errorandoutperforms
allothermetrics thatwe comparedagainst.
5.3.Word embeddings.
As our technique is naturally dependent on a word em-
bedding, we examine how different word embeddings af-
fect the quality of k-nearest neighbor classification with
theWMD. Apartfrom theaforementionedfreely-available
Google News word2vec model, we trained two other
word2vecmodelsonapaperscorpus(NIPS)andaproduct
reviewcorpus (AMZ). Specifically, we extracted textfrom
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.0
0.8
0.6
0.4
0.2
1.4
0
500
1500
2500
1000
2000
0
amazon
WMD
RWMD
WCD
training input index
distance
1.6
1.4
1.2
1.0
0.8
0.6
0.4
1.6
0.2
twitter
200
400
800
1000
600
0
training input index
0
Figure6.The WCD, RWMD, and WMD distances (sorted by
WMD)fora randomtest querydocument.
allNIPS conferencepaperswithintheyears2004-2013and
trained a Skip-gram model on the dataset as perMikolov
et al. (2013b). We e alsousedthe 340;000Amazonre-
viewdatasetofBlitzeretal.(2006)(asupersetofthe ama-
zon classification dataset used above) to train the review-
basedword2vec model. Priortotraining we removed stop
words forboth models, resulting in 36,425,259 words for
the NIPS dataset (50-dimensional) and 90,005,609 words
for the Reviews dataset (100-dimensional) (compared to
the100billionworddatasetofGoogleNews(NEWS)).
Additionally, we experimented with the pre-trained em-
beddings of the hierarchical log-bilinear model (HLBL)
(Mnih&Hinton,2009)andthemodelofCollobert&We-
ston(2008)(CW)
4
.The HLBL model contains 246;122
unique50-dimensionalwordembeddingsandtheCollobert
model has 268;810 unique word embeddings (also 50-
dimensional). Table2 shows classification results on all
data sets except 20
NEWS
(which we dropped due to run-
ning time constraints). On the five larger data sets, the 3
million word Google NEWS model performs superior to
the smaller models. This result is in line with those of
Mikolov et al.(2013a), thatingeneralmoredata(asop-
posed to simply relevant data) creates betterembeddings.
Additionally, thethreeword2vec(w2v)modelsoutperform
the HLBL andCollobertmodelsonall datasets. The clas-
sification error deteriorates when the underlying model is
trained onvery different vocabulary(e.g. NIPS papers vs
cooking recipes), althoughthe performance of the Google
NEWS corpus is surprisinglycompetitivethroughout.
5.4.LowerBoundsand Pruning
Although WMDyields byfarthe mostaccurate classifica-
tion results, itis fair to say that itis also the slowest met-
ric to compute. We can therefore use the lower bounds
from section4tospeedupthe distance computations. Fig-
ure6shows theWMDdistanceofalltraininginputstotwo
randomlychosentestqueriesfrom
TWITTER
and
AMAZON
inincreasing order. The graph alsodepicts the WCD and
RWMD lowerbounds. The RWMDis typically very close
to the exact WMD distance, whereas the cheaper WCD
4
Both available at http://metaoptimize.com/
projects/wordreprs/
FromWordEmbeddingsToDocumentDistances
1
2
3
4
5
6
7
8
0
10
20
30
40
50
est error %
twitter
recipe
ohsumed
classic
reuters
amazon
bbcsport
20news
prefetch and prune
109x
29x
20x
14x
3.1x
2.9x
2.7x
2.6x
18x
13x
12x
10x
28x
20x
16x
12x
13x
12x
12x
11x
14x
12x
12x
11x
22x
13x
11x
8.5x
66x
62x
60x
58x
speedup w.r.t. 
exhaustive 
WMD
4.1x
16x
1.0x
1.1x
2.7x
4.0x
2.2x
5.5x
2.7x
3.2x
2.8x
3.3x
3.0x
4.9x
5.5x
12x
(WCD)
(WMD)
RWMD
m=k
m=2k
m=4k
m=8k
m=n
2.1 s
0.1 s
1.2 s
2.5 s
1.3 s
1.4 s
2.5 s
8.8 s
time per test 
input with the 
exhaustive           
WMD
Figure7.Test errors(in%) and speedups of the prefetch and prune algorithm asthe document cutoff, m, changes. All speedupsare
relativetotheexhaustive k-NNsearchwiththeWMD(shownontheverytop). The errorbarsindicatestandarderror(ifapplicable).
approximation is rather loose. The tightness of RWMD
makesitvaluabletoprunedocuments thatareprovablynot
amongst the k nearest neighbors. Although the WCD is
too loose forpruning, its distances increase withthe exact
WMD distance, whichmakes ita useful heuristic to iden-
tifypromisingnearestneighborcandidates.
The tightness of each lower bound can be seen in the
left image in Figure 5 (averaged across all test points).
RWMD
C1
;RWMD
C2
correspondtoWMDwithonlycon-
straints #1and#2respectively,whichresultincomparable
tightness. WCDisbyfartheloosestandRWMDthetight-
est bound. Interestingly, this tightness does not directly
translate into retrieval accuracy. The right image shows
the average kNN errors (relative to the BOW kNN error)
ifthe lower bounds are useddirectly for nearest neighbor
retrieval. The two mostleft columns representthe twoin-
dividual lowerbounds ofthe RWMDapproximation. Both
perform poorly (worse than WCD), however their maxi-
mum(RWMD)issurprisinglyaccurate andyields kNNer-
rors that are only a little bit less accurate than the exact
WMD. In fact, we would like to emphasize that the aver-
age kNN error with RWMD (0:45 relative to BOW) still
outperformsallotherbaselines(seeFigure4).
Finally, we evaluate thespeedup andaccuracyoftheexact
and approximate versions of the prefetch and prune algo-
rithm from Section4undervariousvaluesofm(Figure7).
When m = k we use the WCD metric for classification
(anddropallWMDcomputations whichareunnecessary).
ForallotherresultsweprefetchminstancesviaWCD,use
RWMD to check if a document can be pruned and only
ifnotcompute the exact WMD distance. The last barfor
eachdatasetshows thetesterrorobtainedwiththeRWMD
metric (omitting all WMD computations). All speedups
arereportedrelative tothetimerequiredfortheexhaustive
WMD metric (verytopofthe figure)andwere run in par-
alell on 4 cores (8 cores for 20
NEWS
)of an Intel L5520
CPUwith2.27Ghz clockfrequency.
First, we notice in all cases the increase in error through
prefetchingis relativelyminorwhereasthe speedupcanbe
substantial. The exact method(m=n)typicallyresults in
aspeedup between 2 and5 whichappears pronounced
with increasing document lengths (e.g. 20
NEWS
). It is
interesting to observe, that the error drops most between
m= k and m = 2k, which might yield a sweet spot be-
tweenaccuracyandretrieval time fortime-sensitive appli-
cations. As noted before, using RWMD directly leads to
impressivelylowerrorratesandaverageretrievaltimesbe-
low1sonalldata sets. We believethe actualtimingcould
be improved substantially with more sophisticated imple-
mentations (ourcodeis inMATLAB)andparallelization.
6. Discussion and Conclusion
ItisworthwhileconsideringwhytheWMDmetricleads to
suchlow errorrates across all data sets. We attribute this
toitsabilitytoutilize thehighqualityoftheword2vecem-
bedding. Trained on billions of words, the word2vec em-
bedding captures knowledge about text documents in the
Englishlanguagethatmaynotbeobtainablefromthetrain-
ing set alone. As pointed out byMikolovetal.(2013a),
other algorithms (such as LDA or LSI) do not scale nat-
urally to data sets of such scale without special approxi-
mations which often counteract the benefit of large-scale
data (although it is a worthy area of future work). Sur-
prisingly, this “latent” supervision benefits tasks that are
differentfrom thedatausedtolearnthe wordembedding.
One attractive feature of the WMD, that we would like
to explore in the future, is its interpretability. Document
distances can be dissected into sparse distances between
words, which can be visualized and explained to humans.
Another interesting direction will be to incorporate docu-
mentstructure intothe distances betweenwords byadding
penalty terms if two words occur in different sections of
similarlystructured documents. If for example the WMD
metric is used to measure the distance between academic
papers, it might make sense to penalize word movements
between the introduction and method section more than
wordmovements from oneintroductiontoanother.
FromWordEmbeddingsToDocumentDistances
Acknowledgments
KQWandMJKaresupportedbyNSFgrantsIIA-1355406,
IIS-1149882, EFRI-1137211. Wethanktheanonymousre-
viewersforinsightfulfeedback.
References
Andoni,A. andIndyk, P. Near-optimalhashingalgorithms
forapproximatenearestneighborinhighdimensions. In
FOCS, pp. 459–468. IEEE, 2006.
Aslam, J. A. andFrost, M. Aninformation-theoreticmea-
sure for document similarity. In SIGIR, volume 3, pp.
449–450.Citeseer, 2003.
Blei, D. M., Ng, A. Y., andJordan, M. I. Latent dirichlet
allocation. Journal of Machine Learning Research, 3:
993–1022, 2003.
Blitzer, J., McDonald, R., andPereira, F. Domain adapta-
tionwithstructuralcorrespondencelearning.InEMNLP,
pp. 120–128.ACL, 2006.
Brochu, E. andFreitas, N. D. Name that song! In NIPS,
pp. 1505–1512, 2002.
Cardoso-Cachopo,A. ImprovingMethodsforSingle-label
TextCategorization. PdDThesis,InstitutoSuperiorTec-
nico, UniversidadeTecnicade Lisboa,2007.
Chen,M., Xu,Z., Weinberger,K.Q., andSha,F. Marginal-
ized denoising autoencoders for domain adaptation. In
ICML, 2012.
Collobert, R. and Weston, J. A unified architecture for
naturallanguageprocessing: Deepneuralnetworkswith
multitasklearning. InICML,pp.160–167.ACM, 2008.
Cover, T. andHart, P. Nearest neighborpattern classifica-
tion. InformationTheory, IEEE Transactions on, 13(1):
21–27, 1967.
Croft, W. B.andLafferty, J. Languagemodelingfor infor-
mationretrieval, volume13. Springer,2003.
Cuturi, Marco. Sinkhorn distances: Lightspeed computa-
tion ofoptimal transport. In Advances inNeural Infor-
mationProcessingSystems, pp. 2292–2300,2013.
Deerwester, S. C., Dumais, S. T., Landauer, T. K., Furnas,
G.W.,andHarshman,R. A. Indexingbylatentsemantic
analysis. JournaloftheAmericanSocietyofInformation
Science,41(6):391–407, 1990.
Garcia, Vincent,Debreuve, Eric,andBarlaud,Michel. Fast
knearestneighborsearchusinggpu. InCVPRWorkshop,
pp. 1–6. IEEE, 2008.
Gardner, J., Kusner, M. J., Xu, E., Weinberger, K. Q., and
Cunningham, J. Bayesian optimization with inequality
constraints. InICML, pp. 937–945, 2014.
Glorot,X., Bordes, A., andBengio, Y. Domain adaptation
forlarge-scalesentiment classification: A deeplearning
approach. InICML, pp. 513–520, 2011.
Grauman, K. and Darrell, T. Fast contour matchingusing
approximateearthmover’sdistance. InCVPR,volume1,
pp. I–220. IEEE,2004.
Greene, D. and Cunningham, P. Practical solutions to the
problemofdiagonaldominanceinkerneldocumentclus-
tering. InICML, pp. 377–384. ACM,2006.
Hearst,M. A. Multi-paragraphsegmentationofexpository
text. In ACL, pp. 9–16. Association for Computational
Linguistics, 1994.
Jojic, N. andPerina, A. Multidimensionalcounting grids:
Inferringwordorderfrom disorderedbags ofwords. In
UAI.2011.
Le, Quoc V andMikolov, Tomas. Distributed representa-
tionsofsentences anddocuments. InICML, 2014.
Levina, E. and Bickel, P. The earth mover’s distance is
themallows distance: Some insights from statistics. In
ICCV, volume2,pp.251–256.IEEE, 2001.
Ling, Haibin and Okada, Kazunori. An efficient earth
mover’sdistancealgorithmforrobusthistogramcompar-
ison. PatternAnalysis and Machine Intelligence, 29(5):
840–853,2007.
Mikolov, T., Chen, K., Corrado, G., andDean, J. Efficient
estimation of word representations in vector space. In
ProceedsingsofWorkshopatICLR,2013a.
Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S.,
and Dean, J. Distributed representations of words and
phrases andtheir compositionality. In NIPS, pp. 3111–
3119,2013b.
Mikolov, T., Yih, W., andZweig, G. Linguisticregularities
in continuous space word representations. In NAACL,
pp. 746–751.Citeseer, 2013c.
Mnih, A. and Hinton, G. E. A scalable hierarchical dis-
tributedlanguagemodel. InNIPS,pp.1081–1088,2009.
Monge,G. M´emoiresur lath´eorie des d´eblais etdesrem-
blais. Del’ImprimerieRoyale,1781.
Nemhauser, G. L.andWolsey, L. A. Integer andcombina-
torialoptimization, volume18. WileyNewYork, 1988.
FromWordEmbeddingsToDocumentDistances
Ontrup, J. andRitter, H. Hyperbolic self-organizing maps
forsemanticnavigation. InNIPS, volume14, pp. 2001,
2001.
Pele, O. and Werman, M. Fast and robust earth mover’s
distances. InICCV,pp.460–467.IEEE, 2009.
Perina,A.,Jojic,N.,Bicego,M.,andTruski,A.Documents
asmultipleoverlappingwindowsintogrids ofcounts. In
NIPS, pp. 10–18. 2013.
Petterson, J., Buntine, W., Narayanamurthy, S. M., Cae-
tano, T. S., and Smola, A. J. Word features for latent
dirichletallocation. InNIPS,pp.1921–1929, 2010.
Quadrianto,N.,Song, L.,andSmola, A.J. Kernelizedsort-
ing. InNIPS,pp.1289–1296, 2009.
Ren, Z., Yuan, J., and Zhang, Z. Robust hand gesture
recognition based on finger-earth mover’s distancewith
acommoditydepthcamera. InProceedings ofACM in-
ternational conference on multimedia, pp. 1093–1096.
ACM, 2011.
Robertson, S. E. and Walker, S. Some simple effective
approximations to the 2-poisson model for probabilis-
ticweighted retrieval. InProceedings ACMSIGIR con-
ferenceonResearchanddevelopmentininformationre-
trieval, pp. 232–241. Springer-Verlag New York, Inc.,
1994.
Robertson,S. E., Walker, S., Jones, S., Hancock-Beaulieu,
M. M., Gatford, M., et al. Okapi attrec-3. NIST SPE-
CIALPUBLICATIONSP,pp.109–109,1995.
Rubner, Y., Tomasi, C., and Guibas, L. J. A metric for
distributions with applications to image databases. In
ICCV, pp. 59–66. IEEE,1998.
Salton, G. and Buckley, C. The smart retrieval systemex-
periments inautomaticdocumentprocessing. 1971.
Salton, G. andBuckley, C. Term-weightingapproaches in
automatictextretrieval. Informationprocessing& man-
agement, 24(5):513–523,1988.
Sanders, N. J. Sanders-twittersentimentcorpus, 2011.
Sch¨olkopf, B., Weston, J., Eskin, E., Leslie, C., and No-
ble, W. S. A kernel approach for learning from almost
orthogonal patterns. In ECML, pp. 511–528. Springer,
2002.
Shirdhonkar, S. and Jacobs, D. W. Approximate earth
moversdistanceinlineartime. InCVPR, pp.1–8. IEEE,
2008.
Snoek, J., Larochelle, H., and Adams, R. P. Practical
bayesian optimization of machine learning algorithms.
InNIPS,pp.2951–2959, 2012.
Steyvers, M. and Griffiths, T. Probabilistic topic models.
Handbookof latent semantic analysis, 427(7):424–440,
2007.
Turian, J., Ratinov, L., and Bengio, Y. Word representa-
tions: a simple and general methodfor semi-supervised
learning. In ACL, pp. 384–394.Association forCompu-
tationalLinguistics, 2010.
Wan, X. A novel document similarity measure based on
earth movers distance. Information Sciences, 177(18):
3718–3730, 2007.
Yianilos, PeterN. Datastructuresandalgorithms fornear-
estneighborsearchingeneralmetricspaces. InProceed-
ings ofACM-SIAM SymposiumonDiscrete Algorithms,
pp. 311–321. SocietyforIndustrialandApplied Mathe-
matics, 1993.
Documents you may be interested
Documents you may be interested