  We develop a novel bi-directional attention model for dependency parsing,
which learns to agree on headword predictions from the forward and backward
parsing directions. The parsing procedure for each direction is formulated as
sequentially querying the memory component that stores continuous headword
embeddings. The proposed parser makes use of {\it soft} headword embeddings,
allowing the model to implicitly capture high-order parsing history without
dramatically increasing the computational complexity. We conduct experiments on
English, Chinese, and 12 other languages from the CoNLL 2006 shared task,
showing that the proposed model achieves state-of-the-art unlabeled attachment
scores on 6 languages.
