Automatically Discovering Conceptual Neighborhoods Using Machine Learning Methods

Authors Ling Cai , Krzysztof Janowicz, Rui Zhu



PDF
Thumbnail PDF

File

LIPIcs.COSIT.2022.3.pdf
  • Filesize: 0.89 MB
  • 14 pages

Document Identifiers

Author Details

Ling Cai
  • Center for Spatial Studies, University of California, Santa Barbara, CA, USA
  • STKO Lab, Department Geography, University of California, Santa Barbara, CA, USA
Krzysztof Janowicz
  • Universität Wien, Austria
  • Center for Spatial Studies, University of California, Santa Barbara, CA, USA
Rui Zhu
  • Center for Spatial Studies, University of California, Santa Barbara, CA, USA
  • School of Geographical Sciences, University of Bristol, Bristol, UK

Acknowledgements

We want to thank Yutao Zhou for discussion on experiment design/ visualization.

Cite AsGet BibTex

Ling Cai, Krzysztof Janowicz, and Rui Zhu. Automatically Discovering Conceptual Neighborhoods Using Machine Learning Methods. In 15th International Conference on Spatial Information Theory (COSIT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 240, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.COSIT.2022.3

Abstract

Qualitative spatio-temporal reasoning (QSTR) plays a key role in spatial cognition and artificial intelligence (AI) research. In the past, research and applications of QSTR have often taken place in the context of declarative forms of knowledge representation. For instance, conceptual neighborhoods (CN) and composition tables (CT) of relations are introduced explicitly and utilized for spatial/temporal reasoning. Orthogonal to this line of study, we focus on bottom-up machine learning (ML) approaches to investigate QSTR. More specifically, we are interested in questions of whether similarities between qualitative relations can be learned from data purely based on ML models, and, if so, how these models differ from the ones studied by traditional approaches. To achieve this, we propose a graph-based approach to examine the similarity of relations by analyzing trained ML models. Using various experiments on synthetic data, we demonstrate that the relationships discovered by ML models are well-aligned with CN structures introduced in the (theoretical) literature, for both spatial and temporal reasoning. Noticeably, even with significantly limited qualitative information for training, ML models are still able to automatically construct neighborhood structures. Moreover, patterns of asymmetric similarities between relations are disclosed using such a data-driven approach. To the best of our knowledge, our work is the first to automatically discover CNs without any domain knowledge. Our results can be applied to discovering CNs of any set of jointly exhaustive and pairwise disjoint (JEPD) relations.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Machine learning
  • Computing methodologies → Knowledge representation and reasoning
  • Computing methodologies → Temporal reasoning
  • Computing methodologies → Spatial and physical reasoning
Keywords
  • Qualitative Spatial Reasoning
  • Qualitative Temporal Reasoning
  • Conceptual Neighborhood
  • Machine Learning
  • Knowledge Discovery

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. James F Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11):832-843, 1983. Google Scholar
  2. Roland Billen and Nico Van de Weghe. Qualitative spatial reasoning. International Encyclopaedia of Human Geography, pages 12-18, 2009. Google Scholar
  3. Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, pages 1-9, 2013. Google Scholar
  4. Lejdel Brahim, Kazar Okba, and Laurini Robert. Mathematical framework for topological relationships between ribbons and regions. Journal of Visual Languages & Computing, 2015. Google Scholar
  5. Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low-dimensional hyperbolic knowledge graph embeddings. In Proceedings of the 58th Annual Meeting of ACL, pages 6901-6914, 2020. Google Scholar
  6. Anthony G Cohn and Jochen Renz. Qualitative spatial representation and reasoning. Foundations of Artificial Intelligence, 3:551-596, 2008. Google Scholar
  7. Matthew P Dube and Max J Egenhofer. An ordering of convex topological relations. In GIScience, pages 72-86. Springer, 2012. Google Scholar
  8. Max J Egenhofer. Deriving the composition of binary topological relations. Journal of Visual Languages & Computing, 5(2):133-149, 1994. Google Scholar
  9. Max J Egenhofer. The family of conceptual neighborhood graphs for region-region relations. In GIScience, pages 42-55. Springer, 2010. Google Scholar
  10. Max J Egenhofer and Khaled K Al-Taha. Reasoning about gradual changes of topological relationships. In TMSTRGS, pages 196-219. Springer, 1992. Google Scholar
  11. Max J Egenhofer and Robert D Franzosa. Point-set topological spatial relations. IJGIS, 5(2):161-174, 1991. Google Scholar
  12. Max J Egenhofer and John Herring. Categorizing binary topological relations between regions, lines, and points in geographic databases. The, 9(94-1):76, 1990. Google Scholar
  13. Andrew U Frank. Qualitative spatial reasoning about distances and directions in geographic space. Journal of Visual Languages & Computing, 3(4):343-371, 1992. Google Scholar
  14. Christian Freksa. Qualitative spatial reasoning. In Cognitive and linguistic aspects of geographic space, pages 361-372. Springer, 1991. Google Scholar
  15. Christian Freksa. Temporal reasoning based on semi-intervals. AI, 54(1-2):199-227, 1992. Google Scholar
  16. Christian Freksa. Using orientation information for qualitative spatial reasoning. In TMSTRGS, pages 162-178. Springer, 1992. Google Scholar
  17. Alexander Klippel. Spatial information theory meets spatial thinking: is topology the rosetta stone of spatio-temporal cognition? Annals of AAG, 102(6):1310-1328, 2012. Google Scholar
  18. Alexander Klippel and Rui Li. The endpoint hypothesis: A topological-cognitive assessment of geographic scale movement patterns. In COSIT, pages 177-194. Springer, 2009. Google Scholar
  19. Alexander Klippel, Jinlong Yang, Jan Oliver Wallgrün, Frank Dylla, and Rui Li. Assessing similarities of qualitative spatio-temporal relations. In ICSC, pages 242-261. Springer, 2012. Google Scholar
  20. Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation embeddings for knowledge graph completion. In AAAI, volume 29, 2015. Google Scholar
  21. David M Mark and Max J Egenhofer. Calibrating the meanings of spatial predicates from natural language: Line-region relations. In Proceedings, SDH 1994, volume 1, pages 538-553, 1994. Google Scholar
  22. David A Randell, Zhan Cui, and Anthony G Cohn. A spatial logic based on regions and connection. KR, 92:165-176, 1992. Google Scholar
  23. Jochen Renz, Debasis Mitra, et al. Qualitative direction calculi with arbitrary granularity. Google Scholar
  24. Jochen Renz and Bernhard Nebel. Qualitative spatial reasoning using constraint calculi. In Handbook of spatial logics, pages 161-215. Springer, 2007. Google Scholar
  25. Carl Schultz, Mehul Bhatt, Jakob Suchan, and Przemysław Andrzej Wałęga. Answer set programming modulo ‘space-time’. In IJCRR, pages 318-326. Springer, 2018. Google Scholar
  26. Jan Oliver Wallgrün, Diedrich Wolter, and Kai-Florian Richter. Qualitative matching of spatial information. In the 18th SIGSPATIAL, pages 300-309, 2010. Google Scholar
  27. Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. IEEE TKDE, 29(12):2724-2743, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail