Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Deep Siamese Metric Learning: A Highly Scalable Approach to Searching Unordered Sets of Trajectories

Published: 29 November 2021 Publication History

Abstract

This work proposes metric learning for fast similarity-based scene retrieval of unstructured ensembles of trajectory data from large databases. We present a novel representation learning approach using Siamese Metric Learning that approximates a distance preserving low-dimensional representation and that learns to estimate reasonable solutions to the assignment problem. To this end, we employ a Temporal Convolutional Network architecture that we extend with a gating mechanism to enable learning from sparse data, leading to solutions to the assignment problem exhibiting varying degrees of sparsity.
Our experimental results on professional soccer tracking data provides insights on learned features and embeddings, as well as on generalization, sensitivity, and network architectural considerations. Our low approximation errors for learned representations and the interactive performance with retrieval times several magnitudes smaller shows that we outperform previous state of the art.

References

[1]
Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. 2018. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv:1803.01271 (2018).
[2]
Alina Bialkowski, Patrick Lucey, Peter Carr, Yisong Yue, Sridha Sridharan, and Iain Matthews. 2014. Identifying team style in soccer using formations learned from spatiotemporal tracking data. In International Conference on Data Mining Workshop. IEEE, 9–14.
[3]
Alina Bialkowski, Patrick Lucey, Peter Carr, Yisong Yue, Sridha Sridharan, and Iain Matthews. 2014. Large-scale analysis of soccer matches using spatiotemporal tracking data. In International Conference on Data Mining. IEEE, IEEE Computer Society, Los Alamitos, CA, USA, 725–730.
[4]
Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. 1994. Signature verification using a “siamese” time delay neural network. In Advances in neural information processing systems. 737–744.
[5]
Nicolas Carion, F. Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. 2020. End-to-end object detection with transformers. In European Conference on Computer Vision.
[6]
Christopher Mutschler. 2010. Online Data-Mining of Interactive Trajectories in Realtime Location Systems. Master’s thesis. Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU).
[7]
Christopher Mutschler, Gabriella Kókai, and Thorsten Edelhäußer. 2011. Online data Sstream mining on interactive trajectories in soccer games. In Proceedings of the 2nd International Conference on Positioning and Context-Awareness (Brussels). 15–22.
[8]
Ian R. Cleasby, Ewan D. Wakefield, Barbara J. Morrissey, Thomas W. Bodey, Steven C. Votier, Stuart Bearhop, and Keith C. Hamer. 2019. Using time-series similarity measures to compare animal movement trajectories in ecology. Behavioral Ecology and Sociobiology 73, 11 (2019), 151.
[9]
Tom Decroos, Jan Van Haaren, and Jesse Davis. 2018. Automatic discovery of tactics in spatio-temporal soccer match data. In Proceedings of the International Conference on Knowledge Discovery & Data Mining. 223–232.
[10]
Mingyang Di, Diego Klabjan, Long Sha, and Patrick Lucey. 2018. Large-Scale adversarial sports play retrieval with learning to rank. ACM Transactions on Knowledge Discovery from Data (TKDD) 12, 6 (2018), 1–18.
[11]
Esther Calvo Fernández, José Manuel Cordero, George Vouros, Nikos Pelekis, Theocharis Kravaris, Harris Georgiou, Georg Fuchs, Natalya Andrienko, Gennady Andrienko, Enrique Casado, et al. 2017. DART: A machine-learning approach to trajectory prediction and demand-capacity balancing. SESAR Innovation Days, Belgrade (2017), 28–30.
[12]
X. Gao, X. Liu, T. Yang, G. Deng, H. Peng, Q. Zhang, H. Li, and J. Liu. 2020. Automatic key moment extraction and highlights generation based on comprehensive soccer video understanding. In International Conference on Multimedia Expo Workshops (ICMEW). IEEE, 1–6.
[13]
Andreas Grunz, Daniel Memmert, and Jürgen Perl. 2012. Tactical pattern recognition in soccer games by means of special self-organizing maps. Human Movement Science 31, 2 (2012), 334–343.
[14]
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In Proceedings of the Conference on Computer Vision and Pattern Recognition. 770–778.
[15]
Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural Computation 9, 8 (1997), 1735–1780.
[16]
Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, San Diego, CA, USA.
[17]
Georg Kohl, Kiwon Um, and Nils Thuerey. 2020. Learning similarity metrics for numerical simulations. In International Conference on Machine Learning. PMLR, 5349–5360.
[18]
Harold W. Kuhn. 1955. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, 1–2 (1955), 83–97.
[19]
Mengyuan Lee, Yuanhao Xiong, Guanding Yu, and Geoffrey Ye Li. 2018. Deep neural networks for linear sum assignment problems. IEEE Wireless Communications Letters 7, 6 (2018), 962–965.
[20]
D. Link. 2014. A toolset for beach volleyball game analysis based on object tracking. International Journal of Computer Science in Sport 13 (01 2014), 24–35.
[21]
Yingchi Mao, Haishi Zhong, Xianjian Xiao, and Xiaofang Li. 2017. A segment-based trajectory similarity measure in the urban transportation systems. Sensors 17, 3 (2017), 524.
[22]
Leland McInnes, John Healy, Nathaniel Saul, and Lukas Großberger. 2018. UMAP: Uniform manifold approximation and projection. Journal of Open Source Software 3, 29 (2018), 861.
[23]
Vinod Nair and Geoffrey E. Hinton. 2010. Rectified linear units improve restricted Boltzmann machines. In Proceedings of the 27th International Conference on Machine Learning (Haifa, Israel) (ICML’10). 807–814.
[24]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32. Montré al, Canada, 8024–8035.
[25]
Jürgen Perl. 2018. Formation-based modelling and simulation of success in soccer. International Journal of Computer Science in Sport 17, 2 (2018), 204–215.
[26]
Jürgen Perl and Daniel Memmert. 2011. Net-Based game analysis by means of the software tool SOCCER. International Journal of Computer Science in Sport (01 2011).
[27]
Nils Reimers and Iryna Gurevych. 2019. Sentence-BERT: Sentence embeddings using siamese BERT-Networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 3973–3983.
[28]
Keven Richly. 2018. Leveraging spatio-temporal soccer data to define a graphical query language for game recordings. In 2018 IEEE International Conference on Big Data (Big Data). IEEE, 3456–3463.
[29]
Pavel Senin. 2008. Dynamic time warping algorithm review. Information and Computer Science Department University of Hawaii at Manoa Honolulu, HI, USA 855, 1–23 (2008), 40.
[30]
B. Serrien, M. Goossens, and J-P. Baeyens. 2017. Issues in using self-organizing maps in human movement and sport science. International Journal of Computer Science in Sport 16, 1 (2017), 1–17.
[31]
Long Sha, Patrick Lucey, Yisong Yue, Peter Carr, Charlie Rohlf, and Iain Matthews. 2016. Chalkboarding: A new spatiotemporal query paradigm for sports play retrieval. In Proceedings of the 21st International Conference on Intelligent User Interfaces. 336–347.
[32]
Long Sha, Patrick Lucey, Stephan Zheng, Taehwan Kim, Yisong Yue, and Sridha Sridharan. 2017. Fine-grained retrieval of sports plays using tree-based alignment of trajectories. arXiv preprint arXiv:1710.02255 (2017).
[33]
Zhi-Hao Shen, W. Du, X. Zhao, and Jianhua Zou. 2019. Retrieving similar trajectories from cellular data at city scale. ArXiv abs/1907.12371 (2019).
[34]
Huong Yong Ting, Kok-Swee Sim, and Fazly Salleh Abas. 2015. Kinect-based badminton movement recognition and analysis system. International Journal of Computer Science in Sport 14, 2 (2015), 25–41.
[35]
Aäron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. 2016. WaveNet: A generative model for raw audio. In 9th ISCA Speech Synthesis Workshop. 125–125.
[36]
Aäron Van Den Oord, Nal Kalchbrenner, and Koray Kavukcuoglu. 2016. Pixel recurrent neural networks. In Proceedings of the 33rd International Conference on Machine Learning-Volume 48. 1747–1756.
[37]
Michail Vlachos, George Kollios, and Dimitrios Gunopulos. 2002. Discovering similar multidimensional trajectories. In Proceedings 18th International Conference on Data Engineering. IEEE, 673–684.
[38]
Zheng Wang, Cheng Long, Gao Cong, and Ce Ju. 2019. Effective and efficient sports play retrieval with deep representation learning. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 499–509.
[39]
Sebastian Wenninger, Daniel Link, and Martin Lames. 2020. Performance of machine learning models in application to beach volleyball data.International Journal of Computer Science in Sport 19, 1 (2020), 24–36.
[40]
Han Xiao. 2020. Hungarian layer: A novel interpretable neural layer for paraphrase identification. Neural Networks 131 (2020), 172–184.
[41]
Munkh-Erdene Yadamjav, Zhifeng Bao, Baihua Zheng, Farhana M. Choudhury, and Hanan Samet. 2020. Querying recurrent convoys over trajectory data. ACM Trans. Intell. Syst. Technol. 11, 5, Article 59 (Aug. 2020), 24 pages.
[42]
Jiahui Yu, Zhe Lin, Jimei Yang, Xiaohui Shen, Xin Lu, and Thomas S. Huang. 2019. Free-form image inpainting with gated convolution. In Proceedings of the IEEE International Conference on Computer Vision. 4471–4480.
[43]
Yu Zhao, Quan Chen, Wengang Cao, Jie Yang, Jian Xiong, and Guan Gui. 2019. Deep learning for risk detection and trajectory tracking at construction sites. IEEE Access 7 (2019), 30905–30912.
[44]
Yu Zheng. 2015. Trajectory data mining: An overview. ACM Transactions on Intelligent Systems and Technology (TIST) 6, 3 (2015), 1–41.

Cited By

View all
  • (2024)Memristive neural network circuit design based on locally competitive algorithm for sparse coding applicationNeurocomputing10.1016/j.neucom.2024.127369578:COnline publication date: 2-Jul-2024
  • (2022)Knowledge transfer based hierarchical few-shot learning via tree-structured knowledge graphInternational Journal of Machine Learning and Cybernetics10.1007/s13042-022-01640-514:1(281-294)Online publication date: 9-Sep-2022

Index Terms

  1. Deep Siamese Metric Learning: A Highly Scalable Approach to Searching Unordered Sets of Trajectories

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Transactions on Intelligent Systems and Technology
      ACM Transactions on Intelligent Systems and Technology  Volume 13, Issue 1
      February 2022
      349 pages
      ISSN:2157-6904
      EISSN:2157-6912
      DOI:10.1145/3502429
      • Editor:
      • Huan Liu
      Issue’s Table of Contents

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 29 November 2021
      Accepted: 01 May 2021
      Revised: 01 March 2021
      Received: 01 December 2020
      Published in TIST Volume 13, Issue 1

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. Siamese neural networks
      2. assignment problem
      3. metric learning

      Qualifiers

      • Research-article
      • Refereed

      Funding Sources

      • Bavarian Ministry of Economic Affairs, Infrastructure, Energy and Technology as part of the Bavarian project Leistungszentrum Elektroniksysteme (LZE)
      • Center for Analytics-Data-Applications (ADA-Center) within the framework of “BAYERN DIGITAL II”

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)121
      • Downloads (Last 6 weeks)7
      Reflects downloads up to 19 Nov 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Memristive neural network circuit design based on locally competitive algorithm for sparse coding applicationNeurocomputing10.1016/j.neucom.2024.127369578:COnline publication date: 2-Jul-2024
      • (2022)Knowledge transfer based hierarchical few-shot learning via tree-structured knowledge graphInternational Journal of Machine Learning and Cybernetics10.1007/s13042-022-01640-514:1(281-294)Online publication date: 9-Sep-2022

      View Options

      Login options

      Full Access

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Full Text

      View this article in Full Text.

      Full Text

      HTML Format

      View this article in HTML Format.

      HTML Format

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media