  Continuous vector representations of words and objects appear to carry
surprisingly rich semantic content. In this paper, we advance both the
conceptual and theoretical understanding of word embeddings in three ways.
First, we ground embeddings in semantic spaces studied in
cognitive-psychometric literature and introduce new evaluation tasks. Second,
in contrast to prior work, we take metric recovery as the key object of study,
unify existing algorithms as consistent metric recovery methods based on
co-occurrence counts from simple Markov random walks, and propose a new
recovery algorithm. Third, we generalize metric recovery to graphs and
manifolds, relating co-occurence counts on random walks in graphs and random
processes on manifolds to the underlying metric to be recovered, thereby
reconciling manifold estimation and embedding algorithms. We compare embedding
algorithms across a range of tasks, from nonlinear dimensionality reduction to
three semantic language tasks, including analogies, sequence completion, and
classification.
