HyperQuaternionE: A hyperbolic embedding model for qualitative spatial and temporal reasoning
Tóm tắt
Qualitative spatial/temporal reasoning (QSR/QTR) plays a key role in research on human cognition, e.g., as it relates to navigation, as well as in work on robotics and artificial intelligence. Although previous work has mainly focused on various spatial and temporal calculi, more recently representation learning techniques such as embedding have been applied to reasoning and inference tasks such as query answering and knowledge base completion. These subsymbolic and learnable representations are well suited for handling noise and efficiency problems that plagued prior work. However, applying embedding techniques to spatial and temporal reasoning has received little attention to date. In this paper, we explore two research questions: (1) How do embedding-based methods perform empirically compared to traditional reasoning methods on QSR/QTR problems? (2) If the embedding-based methods are better, what causes this superiority? In order to answer these questions, we first propose a hyperbolic embedding model, called HyperQuaternionE, to capture varying properties of relations (such as symmetry and anti-symmetry), to learn inversion relations and relation compositions (i.e., composition tables), and to model hierarchical structures over entities induced by transitive relations. We conduct various experiments on two synthetic datasets to demonstrate the advantages of our proposed embedding-based method against existing embedding models as well as traditional reasoners with respect to entity inference and relation inference. Additionally, our qualitative analysis reveals that our method is able to learn conceptual neighborhoods implicitly. We conclude that the success of our method is attributed to its ability to model composition tables and learn conceptual neighbors, which are among the core building blocks of QSR/QTR.
Tài liệu tham khảo
Dylla F, Lee JH, Mossakowski T, Schneider T, Delden AV, Ven JVD, Wolter D (2017) A survey of qualitative spatial and temporal calculi: algebraic and computational properties. ACM Comput Surv (CSUR) 50(1):1–39
Suchan J, Bhatt M, Varadarajan S (2019) Out of sight but not out of mind: An answer set programming based online abduction framework for visual sensemaking in autonomous driving. In: 28th International joint conference on artificial intelligence (IJCAI 2019), Macao, China, August 10-16, 2019, pp 1879–1885. ijcai. org
Suchan J, Bhatt M (2016) Semantic question-answering with video and eye-tracking data: Ai foundations for human visual perception driven cognitive film studies. In: Proceedings of the twenty-fifth international joint conference on artificial intelligence, pp 2633–2639
Kostakis O, Tatti N, Gionis A (2017) Discovering recurring activity in temporal networks. Data Min Knowl Discov 31(6):1840–1871
Billen R, Van de Weghe N (2009) Qualitative spatial reasoning. International Encyclopaedia of Human Geography, 12–18
Renz J, Nebel B (2007) Qualitative spatial reasoning using constraint calculi. In: Handbook of spatial logics, pp 161–215. Springer
Allen JF (1983) Maintaining knowledge about temporal intervals. Communications of the ACM 26(11):832–843
Randell DA, Cui Z, Cohn AG (1992) A spatial logic based on regions and connection. KR 92, 165–176
Egenhofer MJ, Al-Taha KK (1992) Reasoning about gradual changes of topological relationships. In: Theories and methods of spatio-temporal reasoning in geographic space, pp. 196–219. Springer
Freksa, C. (1992) Using orientation information for qualitative spatial reasoning. In: Theories and methods of spatio-temporal reasoning in geographic space, pp. 162–178. Springer
Zimmermann K (1993) Enhancing qualitative spatial reasoning-combining orientation and distance. In: European Conference on Spatial Information Theory, pp. 69–76. Springer
Frank AU (1992) Qualitative spatial reasoning about distances and directions in geographic space. J Vis Lang Comput 3(4):343–371
Frank AU, Campari I, Formentini U (1992) Theories and Methods of Spatio-temporal Reasoning in Geographic Space. Springer
Clementini E, Di Felice P, Hernández D (1997) Qualitative representation of positional information. Artif Intell 95(2):317–356
Worboys MF (2001) Nearness relations in environmental space. Int J Geogr Inf Syst 15(7):633–651
Hernandez D, Clementini E, Di Felice P (1995) Qualitative distances. In: International conference on spatial information theory, pp. 45–57. Springer
Pratt I, Schoop D (1998) A complete axiom system for polygonal mereotopology of the real plane. J Philos Log 27(6):621–658
Egenhofer MJ, Franzosa RD (1991) Point-set topological spatial relations. Int J Geogr Inf Syst 5(2):161–174
Freksa C (1991) Qualitative spatial reasoning. In: Cognitive and linguistic aspects of geographic space, pp 361–372. Springer
Freksa C (1992) Temporal reasoning based on semi-intervals. Artif Intell 54(1–2):199–227
Renz J, Nebel B (1999) On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus. Artif Intell 108(1–2):69–123
Renz J, Nebel B (2001) Efficient methods for qualitative spatial reasoning. J Artif Intell Res 15:289–318
Cohn AG, Hazarika SM (2001) Qualitative spatial representation and reasoning: An overview. Fundam Inform 46(1–2):1–29
Mikolov T, Sutskever I, Chen K, Corrado GS, Dean J (2013) Distributed representations of words and phrases and their compositionality. In: Advances in neural information processing systems, pp 3111–3119
Peters ME, Neumann M, Iyyer M, Gardner M, Clark C, Lee K, Zettlemoyer L (2018) Deep contextualized word representations. In: Proc. of NAACL
Devlin J, Chang M-W, Lee K, Toutanova K (2018) Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv:1810.04805
Cui Y, Chen Z, Wei S, Wang S, Liu T, Hu G (2016) Attention-over-attention neural networks for reading comprehension. arXiv:1607.04423
Hamilton WL, Bajaj P, Zitnik M, Jurafsky D, Leskovec J (2018) Embedding logical queries on knowledge graphs. In: Proceedings of the 32nd international conference on neural information processing systems, pp 2030–2041
Mai G, Janowicz K, Yan B, Zhu R, Cai L, Lao N (2019) Contextual graph attention for answering logical queries over incomplete knowledge graphs. In: Proceedings of the 10th international conference on knowledge capture, pp 171–178
Ren H, Leskovec J (2020) Beta embeddings for multi-hop logical reasoning in knowledge graphs. Advances in Neural Information Processing Systems, 33
Kipf T, Fetaya E, Wang K-C, Welling M, Zemel R (2018) Neural relational inference for interacting systems. In: International conference on machine learning, pp 2688–2697. PMLR
Xiong W, Hoang T, Wang WY (2017) Deeppath: A reinforcement learning method for knowledge graph reasoning. In: Proceedings of the 2017 conference on empirical methods in natural language processing, pp 564–573
Guo L, Sun Z, Hu W (2019) Learning to exploit long-term relational dependencies in knowledge graphs. In: International conference on machine learning, pp 2505–2514. PMLR
Lin Y, Liu Z, Luan H, Sun M, Rao S, Liu S (2015) Modeling relation paths for representation learning of knowledge bases. In: Proceedings of the 2015 conference on empirical methods in natural language processing, pp 705–714
Schlichtkrull M, Kipf TN, Bloem P, Van Den Berg R, Titov I, Welling M (2018) Modeling relational data with graph convolutional networks. In: European semantic web conference, pp 593–607. Springer
Rolnick D, Veit A, Belongie S, Shavit N (2017) Deep learning is robust to massive label noise. arXiv:1705.10694
Jiang L, Huang D, Liu M, Yang W (2020) Beyond synthetic noise: Deep learning on controlled noisy labels. In: International conference on machine learning, pp. 4804–4815. PMLR
Sala F, De Sa C, Gu A, Ré C (2018) Representation tradeoffs for hyperbolic embeddings. In: International conference on machine learning, pp 4460–4469. PMLR
Sarkar R (2011) Low distortion delaunay embedding of trees in hyperbolic plane. In: International symposium on graph drawing, pp 355–366. Springer
Nickel M, Kiela D (2018) Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In: International conference on machine learning, pp 3779–3788. PMLR
Nickel M, Kiela D (2017) Poincaré embeddings for learning hierarchical representations. Adv Neural Inf Process Syst 30:6338–6347
Sun Z, Deng Z-H, Nie J-Y, Tang, J (2019) Rotate: Knowledge graph embedding by relational rotation in complex space. arXiv:1902.10197
Bordes A, Usunier N, Garcia-Duran A, Weston J, Yakhnenko O (2013) Translating embeddings for modeling multi-relational data. In: Neural information processing systems (NIPS), pp. 1–9
Wang Z, Zhang J, Feng J, Chen Z (2014) Knowledge graph embedding by translating on hyperplanes. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pp. 1112–1119
Ji G, Liu K, He S, Zhao J (2016) Knowledge graph completion with adaptive sparse transfer matrix. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pp. 985–991
Gao C, Sun C, Shan L, Lin L, Wang M (2020) Rotate3d: Representing relations as rotations in three-dimensional space for knowledge graph embedding. In: Proceedings of the 29th ACM international conference on information & knowledge management, pp 385–394
Cao Z, Xu Q, Yang Z, Cao X, Huang Q (2021) Dual quaternion knowledge graph embeddings. Proceedings of the AAAI conference on artificial intelligence 35:6894–6902
Yang B, Yih W-T, He X, Gao J, Deng L (2014) Embedding entities and relations for learning and inference in knowledge bases. In: Proceedings of the 3rd International Conference on Learning Representation.
Nickel M, Tresp V, Kriegel H-P (2011) A three-way model for collective learning on multi-relational data. In: Proceedings of the 28th International Conference on International Conference on Machine Learning, pp. 809–816
Trouillon T, Dance CR, Welbl J, Riedel S, Gaussier É, Bouchard G (2017) Knowledge graph completion via complex tensor factorization. Journal of Machine Learning Research, 18: pp.1–38
Lacroix T, Obozinski G, Usunier N (2020) Tensor decompositions for temporal knowledge base completion. In: Proceedings of the Seventh International Conference on Learning Representations
Ganea O-E, Bécigneul G, Hofmann T (2018) Hyperbolic neural networks. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 5350–5360
Gu A, Sala F, Gunel B, Ré C (2018) Learning mixed-curvature representations in product spaces. In: Proceedings of the sixth International conference on learning representations.
Balazevic I, Allen C, Hospedales T (2019) Multi-relational poincaré graph embeddings. In: Proceedings of the 33rd International Conference on Neural Inf Process Syst 32:4463–4473
Kolyvakis P, Kalousis A, Kiritsis D (2020) Hyperbolic knowledge graph embeddings for knowledge base completion. In: Harth A, Kirrane S, Ngonga Ngomo A-C, Paulheim H, Rula A, Gentile AL, Haase P, Cochez M (eds) The Semantic Web. Springer, Cham, pp 199–214
Chami I, Wolf A, Juan D-C, Sala F, Ravi S, Ré C (2020) Low-dimensional hyperbolic knowledge graph embeddings. In: Proceedings of the 58th annual meeting of the association for computational linguistics, pp 6901–6914
Pletinckx D (1989) Quaternion calculus as a basic tool in computer graphics. The Visual Computer 5(1):2–13
Shoemake K (1985) Animating rotation with quaternion curves. In: Proceedings of the 12th annual conference on computer graphics and interactive techniques, pp 245–254
Hamilton WR (1866) Elements of Quaternions. (Cambridge Library Collection - Mathematics) (W. Hamilton, Ed.). Cambridge: Cambridge University Press. https://doi.org/10.1017/CBO9780511707162
Vicci L (2001) Quaternions and rotations in 3-space: The algebra and its geometric interpretation. Chapel Hill, NC, USA, Tech. Rep.
Bisi C, Gentili G (2009) Möbius transformations and the poincaré distance in the quaternionic setting. Indiana University Mathematics Journal, 2729–2764
Vilain MB, Kautz HA (1986) Constraint propagation algorithms for temporal reasoning. Aaai 86:377–382
Lin Y, Liu Z, Sun M, Liu Y, Zhu X (2015) Learning entity and relation embeddings for knowledge graph completion. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pp. 2181–2187
Freksa C (1991) Conceptual neighborhood and its role in temporal and spatial reasoning. In: Proc. of the IMACS workshop on decision support systems and qualitative reasoning, pp 181–187