Elamur Research⌕
☰
home / papers / 2015 / Compositional Vector Space Models for Knowledge Base Completion

Compositional Vector Space Models for Knowledge Base Completion

Summary

The paper addresses knowledge base completion (KB completion), that is, automatically inferring missing triple facts from those already present in the graph. Earlier methods, notably the Path Ranking Algorithm (PRA), treated each multi-step path between two entities as a separate, atomic feature. As a result, the number of features grew sharply, and the model could not generalize to new paths. The authors propose a compositional approach. A recurrent neural network (RNN) combines the vector representations of the relations along a path step by step, and the resulting vector is compared with the vector of the target relation. For each entity pair, the model takes the highest-scoring path. It can therefore handle paths it did not see during training. Moreover, a single shared RNN can predict even entirely new relation types (zero-shot). For evaluation, the authors assembled a large dataset of more than 52 million triples based on Freebase and ClueWeb. Their model outperforms PRA by 11% and Cluster PRA by 7%. Combined with a new strong baseline classifier, the result is even better. The work shows that vector composition makes it possible to scale reasoning over large knowledge graphs.

Key points

  • Data: a new open dataset with more than 52 million triples. It was built from Freebase and Google entity linking in ClueWeb. It contains 46 relation types, more than 2 million paths per relation (Gardner had about 1000), and more than 10 thousand entity pairs (Gardner had about 200).
  • Method: paths between entities are found using PRA. An RNN then recursively computes the path vector from the relation vectors. In the main experiments, a separate composition matrix is trained for each target relation.
  • Results: the RNN surpasses PRA by 11%, and its margin over Cluster PRA (Gardner et al., 2013) is 7%. The new baseline PRA Classifier-b, which uses path bigram features, performs statistically on par with the RNN. Combining these two methods yields a 15% gain over Cluster PRA.
  • Zero-shot: the authors took 10 random relations out of the 46 and split them into two halves. A model trained on one half predicts the relations in the other. It is noticeably weaker than the fully supervised RNN but clearly better than a random ranking of facts.
  • Ensemble: individual RNNs with different random initializations score about 57 (57.09, 57.11 and 56.91). Their ensemble achieves 59.16, and the result stops improving after three models.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: AI & machine learning

Topics Knowledge graphs & ontologies

Cite

Cite as Arvind Neelakantan, Benjamin Roth and Andrew McCallum. 2015. Compositional Vector Space Models for Knowledge Base Completion. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/v1/p15-1016 · arXiv 1504.06662

@inproceedings{neelakantan2015compositional,
  title = {{Compositional Vector Space Models for Knowledge Base Completion}},
  author = {Arvind Neelakantan, Benjamin Roth and Andrew McCallum},
  booktitle = {Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)},
  year = {2015},
  doi = {10.3115/v1/p15-1016},
  eprint = {1504.06662},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.3115/v1/p15-1016}
}

References

48 references, 8 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014. Neural machine translation by jointly learning to align and translate. In ArXiv. our card
  2. Michele Banko, Michael J Cafarella, Stephen Soderland, Matt Broadhead, and Oren Etzioni. 2007. Open information extraction from the web. In International Joint Conference on Artificial Intelligence. our card
  3. Marco Baroni and Roberto Zamparelli. 2010. Nouns are vectors, adjectives are matrices: Representing adjective-noun constructions in semantic space. In Empirical Methods in Natural Language Processing. find
  4. Jonathan Berant, Ido Dagan, and Jacob Goldberger. 2011. Global learning of typed entailment rules. In Association for Computational Linguistics. find
  5. Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the ACM SIG-MOD International Conference on Management of Data. find
  6. Antoine Bordes, Nicolas Usunier, Alberto Garcı́a-Durán, Jason Weston, and Oksana Yakhnenko. 2013. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems. find
  7. Samuel R. Bowman, Christopher Potts, and Christopher D Manning. 2014. Recursive neural networks for learning logical semantics. In CoRR. find
  8. Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R. Hruschka, and A. 2010. Toward an architecture for never-ending language learning. In In AAAI. find
  9. Cheng, Jianpeng Kartsaklis, and Edward Grefenstette. 2014. Investigating the role of prior disambiguation in deep-learning compositional models of meaning. In In Learning Semantics workshop NIPS. find
  10. Kyunghyun Cho, Bart van Merrienboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014. On the properties of neural machine translation: Encoder–decoder approaches. In Workshop on Syntax, Semantics and Structure in Statistical Translation. our card
  11. John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. In Journal of Machine Learning Research. find
  12. Andrea Frome, Gregory S. Corrado, Jonathon Shlens, Samy Bengio, Jeffrey Dean, Marc’Aurelio Ranzato, and Tomas Mikolov. 2013. Devise: A deep visual-semantic embedding model. In Neural Information Processing Systems. find
  13. Matt Gardner, Partha Pratim Talukdar, Bryan Kisiel, and Tom M. Mitchell. 2013. Improving learning and inference in a large knowledge-base using latent syntactic cues. In Empirical Methods in Natural Language Processing. find
  14. Matt Gardner, Partha Talukdar, Jayant Krishnamurthy, and Tom Mitchell. 2014. Incorporating vector space similarity in random walk inference over knowledge bases. In Empirical Methods in Natural Language Processing. find
  15. Christoph Goller and Andreas Küchler. 1996. Learning task-dependent distributed representations by backpropagation through structure. In IEEE Transactions on Neural Networks. find
  16. Alex Graves. 2013. Generating sequences with recurrent neural networks. In ArXiv. find
  17. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. In Neural Computation. find
  18. Ozan Irsoy and Claire Cardie. 2014. Deep recursive neural networks for compositionality in language. In Neural Information Processing Systems. find
  19. Mohit Iyyer, Jordan Boyd-Graber, Leonardo Claudino, Richard Socher, and Hal Daumé III. 2014. A neural network for factoid question answering over paragraphs. In Empirical Methods in Natural Language Processing. find
  20. Ni Lao, Tom Mitchell, and William W. Cohen. 2011. Random walk inference and learning in a large scale knowledge base. In Conference on Empirical Methods in Natural Language Processing. find
  21. Ni Lao, Amarnag Subramanya, Fernando Pereira, and William W. Cohen. 2012. Reading the web with learned syntactic-semantic inference rules. In Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. find
  22. Hugo Larochelle, Dumitru Erhan, and Yoshua Bengio. 2008. Zero-data learning of new tasks. In National Conference on Artificial Intelligence. find
  23. Dekang Lin and Patrick Pantel. 2001. Dirt - discovery of inference rules from text. In International Conference on Knowledge Discovery and Data Mining. find
  24. Tomas Mikolov, Martin Karafiát, Lukas Burget, Jan Cernocký, and Sanjeev Khudanpur. 2010. Recurrent neural network based language model. In Annual Conference of the International Speech Communication Association. find
  25. Tomas Mikolov, Armand Joulin, Sumit Chopra, Michaël Mathieu, and Marc’Aurelio Ranzato. 2014. Learning longer memory in recurrent neural networks. In CoRR. find
  26. Bonan Min, Ralph Grishman, Li Wan, Chang Wang, and David Gondek. 2013. Distant supervision for relation extraction with an incomplete knowledge base. In HLT-NAACL, pages 777–782. our card
  27. Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky. 2009. Distant supervision for relation extraction without labeled data. In Association for Computational Linguistics and International Joint Conference on Natural Language Processing. find
  28. Jeff Mitchell and Mirella Lapata. 2008. Vector-based models of semantic composition. In Association for Computational Linguistics. find
  29. Arvind Neelakantan, Jeevan Shankar, Alexandre Passos, and Andrew McCallum. 2014. Efficient non-parametric estimation of multiple embeddings per word in vector space. In Empirical Methods in Natural Language Processing. our card
  30. Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. 2011. A three-way model for collective learning on multi-relational data. In International Conference on Machine Learning. find
  31. Mohammad Norouzi, Tomas Mikolov, Samy Bengio, Yoram Singer, Jonathon Shlens, Andrea Frome, Greg Corrado, and Jeffrey Dean. 2014. Zero-shot learning by convex combination of semantic embeddings. In International Conference on Learning Representations. find
  32. Dave Orr, Amarnag Subramanya, Evgeniy Gabrilovich, and Michael Ringgaard. 2013. 11 billion clues in 800 million documents: A web research corpus annotated with freebase concepts. http://googleresearch.blogspot.com/2013/07/11-billion-clues-in-800-million.html. ↗
  33. Mark Palatucci, Dean Pomerleau, Geoffrey Hinton, and Tom Mitchell. 2009. Zero-shot learning with semantic output codes. In Neural Information Processing Systems. find
  34. Sebastian Riedel, Limin Yao, Andrew McCallum, and Benjamin M. Marlin. 2013. Relation extraction with matrix factorization and universal schemas. In HLT-NAACL. find
  35. Stefan Schoenmackers, Oren Etzioni, Daniel S. Weld, and Jesse Davis. 2010. Learning first-order horn clauses from web text. In Empirical Methods in Natural Language Processing. find
  36. Richard Socher, Cliff Chiung-Yu Lin, Christopher D. Manning, and Andrew Y. Ng. 2011. Parsing natural scenes and natural language with recursive neural networks. In Proceedings of the 26th International Conference on Machine Learning (ICML). find
  37. Richard Socher, Brody Huval, Christopher D. Manning, and Andrew Y. Ng. 2012. Semantic compositionality through recursive matrix-vector spaces. In Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. our card
  38. Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Ng. 2013a. Reasoning with neural tensor networks for knowledge base completion. In Advances in Neural Information Processing Systems. our card
  39. Richard Socher, Milind Ganjoo, Christopher D Manning, and Andrew Ng. 2013b. Zero-shot learning through cross-modal transfer. In Neural Information Processing Systems. find
  40. Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Y. Ng, and Christopher Potts. 2013c. Recursive deep models for semantic compositionality over a sentiment treebank. In Conference on Empirical Methods in Natural Language Processing. find
  41. Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007. Yago: A core of semantic knowledge. In Proceedings of the 16th International Conference on World Wide Web. find
  42. Ilya Sutskever, Oriol Vinyals, and Quoc V. V Le. 2014. Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems. find
  43. Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2014. Grammar as a foreign language. In CoRR. find
  44. Paul Werbos. 1990. Backpropagation through time: what it does and how to do it. In IEEE. find
  45. Jason Weston, Ron Weiss, and Hector Yee. 2013. Nonlinear latent factorization by embedding multiple user interests. In ACM International Conference on Recommender Systems. find
  46. Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2014. Embedding entities and relations for learning and inference in knowledge bases. In CoRR. our card
  47. Alexander Yates and Oren Etzioni. 2007. Unsupervised resolution of objects and relations on the web. In North American Chapter of the Association for Computational Linguistics. find
  48. Ainur Yessenalina and Claire Cardie. 2011. Compositional matrix-space models for sentiment analysis. In Empirical Methods in Natural Language Processing. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/neelakantan-2015-compositional-vector-space-models-knowledge/