# When ChatGPT for Computer Vision Will Come? From 2D to 3D

Chenghao Li  KAISTSouth Korea<EMAIL_ADDRESS>and  Chaoning Zhang
Kyung Hee UniversitySouth Korea<EMAIL_ADDRESS>
(2022)

###### Abstract.

ChatGPT and its improved variant GPT4 have revolutionized the NLP field with a
single model solving almost all text related tasks. However, such a model for
computer vision does not exist, especially for 3D vision. This article first
provides a brief view on the progress of deep learning in text, image and 3D
fields from the model perspective. Moreover, this work further discusses how
AIGC evolves from the data perspective. On top of that, this work presents an
outlook on the development of AIGC in 3D from the data perspective.

text-to-3D, generative AI, AIGC, 3D generation, metaverse

††copyright: acmcopyright††journalyear: 2022††doi: XXXXXXX.XXXXXXX††ccs:
Computing methodologies Reconstruction††ccs: Computing methodologies Shape
modeling

###### Contents

  1. 1 Introduction
  2. 2 Model perspective
  3. 3 Data perspective
  4. 4 Outlook
    1. 4.1 Data explosion since 2010
    2. 4.2 The 3D field awaits its own ’iPhone4’
  5. 5 Conclusion

##  1\. Introduction

Generative AI (AIGC) (Zhang et al., 2023c) has made remarkable progress in the
past few years, for which ChatGPT (Zhang et al., 2023b) is a phenomenal
product, attracting significant attention. The advent of ChatGPT is largely
attributed to large-scale pre-trained models such as BERT (Devlin et al.,
2018) and GPTs (Radford et al., 2018, 2019; Brown et al., 2020; OpenAI, 2023).
These models have not only performed well on natural language processing tasks
(Daniel et al., 2007), but also provided strong support for computer vision
(Szeliski, 2022) and other fields.

In the text field, large-scale deep learning models (Han et al., 2021)
represented by ChatGPT have made revolutionary achievements in natural
language processing (NLP) tasks. They use a large amount of text data for pre-
training, thereby achieving a high level of understanding and generation of
natural language. These models have been widely used in tasks such as machine
translation (Koehn, 2009), text summarization (Allahyari et al., 2017), Q&A
systems (Adamopoulou and Moussiades, 2020), and have shown performance beyond
human in various evaluations. These successful applications provide new ideas
for researchers, further driving the development of generative AI (Zhang et
al., 2023c) in the text field. Meanwhile, in the image field, large-scale deep
learning models have also made important breakthroughs. These models use a
large amount of image data for training, providing strong support for computer
vision tasks. They have achieved excellent results in image recognition (Wu
and Chen, 2015), object detection (Zou et al., 2019), semantic segmentation
(Long et al., 2015) and other tasks, leading the research direction of
computer vision field. Generative AI has also made remarkable breakthroughs in
the image field, laying a solid foundation for the application of artificial
intelligence in image processing and analysis. Compared with 2D images, the
progress in 3D domain is relatively lagging (Shi et al., 2022). 3D models have
great potential in simulating the real world, digital media, and virtual
reality. While text-to-image can generate high-resolution, exquisite images,
text-to-3D models are not yet able to achieve the same results. With the help
of NeRF, the 3D domain can take another route, using the powerful priors from
text-to-image to assist in training text-to-3D models. Moreover, some deep
learning based 3D model reconstruction and generation algorithms have made
great progress (Mildenhall et al., 2021; Poole et al., 2022; Nichol et al.,
2022), laying the foundation for future large-scale pre-trained models in the
3D field. Overall, compared with the text and image fields, the 3D field faces
more challenges in terms of data scale, computational complexity, and model
representation.

The rest of this article is orgenized as follows. Section 2 discusses the
development of deep learning from the model perspective. Moreover, Section 3
further covers the develpment of AIGC from the data perspective. On top of
that, Section 4 presents an outlook on the development of AIGC in 3D from the
data perspective.

##  2\. Model perspective

Three stages of deep learning. Since the success of AlexNet in 2012
(Krizhevsky et al., 2017), deep learning has developed rapidly, which can be
regarded as a paragon of data-driven AI. Three important factors influencing
the development of deep learning are data, computing power and model. During
the evolution of these three factors, deep learning can be roughly divided
into three stages: task-specific stage, fine-tuning stage and general-task
stage by their performance, as shown in Figure 1.

Figure 1. Three stages of deep learning in the fields of text, image and 3D,
and their representative works.

Firstly, in the task-specific stage, due to the limited amount of data, models
with strong inductive bias, such as convolutional neural networks (CNNs) (He
et al., 2016; Szegedy et al., 2015; Tan and Le, 2019) and recurrent neural
networks (RNNs) (Cho et al., 2014), as well as supervised learning, were
adopted. These models can achieve good results on a small amount of data.

Then, in the large model pre-training and fine-tuning stage, the training data
became more complex and extensive, and a small number of model parameters and
network layers could no longer learn the complex and extensive data
distribution. The mainstream model structure also became globally dependent
transformer (Vaswani et al., 2017), using self-supervised learning, first
learning complex features, and then fine-tuning to solve downstream tasks.

At present, text has entered the general task stage. With more data and super-
large models, the distribution of data closer to reality can be learned with
only specific prompts to complete free content generation. Representative
works at this stage include the GPT series (Radford et al., 2018, 2019; Brown
et al., 2020; OpenAI, 2023) in the text domain. In the image field, there is
no unified CV field tasks for the large model yet, but Dalle (Ramesh et al.,
2022, 2021) has shown strong text-prompted 2d image generation capabilities,
and SAM (Segment Anything) (Kirillov et al., 2023) has demonstrated a dominant
ability in the single segmentation task.

Text. With the development of deep learning, the Natural Language Processing
(NLP) field has entered the era of super-large models. The transformer
(Vaswani et al., 2017) model introduced by Google is the underlying network
architecture of the current large model, and ChatGPT released by OpenAI in
November 2022 is a dialog-type super-large language model that uses the
generative pre-trained transformer (GPT) to process sequence data, with
language understanding and text generation capabilities. It can train models
through massive corpus to achieve almost indistinguishable chat scenarios from
real humans. ChatGPT can not only be used as a chatbot, but also for tasks
such as writing emails, video scripts, copywriting, translation, and coding.
The NLP field is in the forefront in the era of super-large models.

Image. On top of GPT-3, OpenAI released the large-scale image generation model
DALL-E, which can generate digital images from natural language descriptions,
referred to as “prompts”. Later, OpenAI released DALL-E 2, a successor
designed to generate more realistic images and higher resolution, with 3.5B
parameters. It can combine concepts, attributes and styles. This model has
achieved considerable results in the field of computer vision, and has made
significant improvements in the quality of generation. More recently, Meta has
released a project termed “Segment Anything” (Kirillov et al., 2023), which
introduces a new task called promptable segmentation together with a new large
segmentation dataset. The resulting model termed segment anything model (SAM)
mimics the GPT-3 in the NLP to adopt prompt engineering for adapting it to
various downstream taks, which demonstrates impressive zero-shot transfer
performance. Numerous works have either evaluated its capability of
generalization (Tang et al., 2023; Han et al., 2023) or robustness (Zhang et
al., 2023a). Moreover, some works have combined SAM with other models to
realize image editing and inpainting (IDEA-Research, 2023; Kevmo, 2023; Feizc,
2023), which shows that SAM can also help generative tasks.

The exploration of pre-training stage is currently underway in 3D field (He et
al., 2021; Shi et al., 2022; Yu et al., 2022). The research in the field of 3D
deep learning is limited by computation power and data access, lagging behind
image and text. This is because 3D data is more complex, scarce and
diversified than images and texts. Existing 3D content creation approaches
usually require a lot of professional knowledge and manpower, which can be
very time-consuming and expensive. There have been numerous pioneering
attempts to study how to automatically generate 3D data(Mildenhall et al.,
2021; Poole et al., 2022; Nichol et al., 2022). However, the quality and
generalization of the generated samples are far inferior to those of large
models in text and image.

Figure 2. From the perspective of training data volume and model parameter
volume, the development process of NLP large model from 2018 to 2021. The
picture is derived from (Han et al., 2021).

The development of large models (including training methods and model
structures) is determined by two main factors: Computational power and Data
volume. This also indirectly affects the development of large models, which
can be referenced by the development history of large models in the NLP field,
as shown in the figure 2. The number of model parameters and the amount of
training data are limited by computing power. By referring to Moore’s Law (as
shown in Figure 3), we can assume and predict the development of computing
power. So how to solve the data problem, in other words, when will the
explosion of three-dimensional data come?

Figure 3. A logarithmic graph showing the timeline of how transistor counts in
microchips are almost doubling every two years from 1970 to 2020; Moore’s Law.
The picture is derived from (Roser and Ritchie, 2020).

##  3\. Data perspective

Before we discuss the issue of data explosion in the 3D field, let us first
look into how PGC and UGC promote AIGC. PGC (Professionally Generated Content)
refers to content that is produced and published by professionals,
institutions, or companies. Such content usually has a high quality,
reliability, and authority, such as news reports, films, television programs,
etc. UGC (User Generated Content) is content created and shared by ordinary
users or community members. Compared with PGC, the quality of UGC is uneven,
but it provides a platform for ordinary users to express their opinions and
ideas. Typical UGC platforms include social media, blogs, forums, etc. AIGC
(AI Generated Content) refers to content created by artificial intelligence
algorithms and systems. AIGC covers a variety of content types, such as text,
images, music, etc., and its quality is gradually improving with the progress
of technology, gradually approaching or even surpassing the level of human
creation.

The relationship between PGC, UGC and AIGC is complementary. Each of PGC, UGC
and AIGC has its own unique advantages and limitations. PGC has authority and
reliability, but the cost of creation is relatively high and the speed of
updating is relatively slow. UGC has wide range and diversity, but the quality
is uneven. The development of AIGC needs time, but after the generative AI is
mature, it can generate unexpected high-quality content in a short time.

Figure 4. Three data generation methods, PGC and UGC promote AIGC by providing
training data.

The emergence order of these three in text and image fields is PGC, UGC and
AIGC. At the beginning of the development of the Internet, content was mainly
created by professionals and institutions, i.e. PGC. With the development of
Internet technology and platforms, users began to participate in content
creation, forming UGC. In recent years, with the rapid development of
artificial intelligence technology, AI has gradually entered content creation,
forming AIGC.

The emergence of AIGC in both text and image domains is largely dependent on
PGC and UGC. From a technical perspective, the development of AIGC is indeed
benefited from the large amount of data from PGC and UGC. In the process of AI
generating content, PGC and UGC provide AI with rich samples and knowledge,
helping AI to learn different types of content and styles. In this sense, the
development of AIGC depends on the existence of PGC and UGC. However, from
another perspective, even without PGC and UGC, AIGC still may be developed. In
theory, as long as there is enough technical progress and innovation, AI can
learn and generate content independently. But in practical applications, the
existence of PGC and UGC provides AI with a more rich and diverse learning
environment, which accelerates the development of AI in the field of content
creation.

Overall, there is a close relationship between PGC, UGC and AIGC. The
development of AIGC has benefited a lot from the existence of PGC and UGC,
which provides AI with abundant learning resources. However, theoretically
speaking, the development of AIGC does not entirely depend on the existence of
PGC and UGC. In the future, with the continuous progress of AI technology, we
believe that AIGC will play an even more important role in content creation.

##  4\. Outlook

###  4.1. Data explosion since 2010

Figure 5. Amount of data created consumed and stored from 2010 to 2020 with
forecasts to 2025. The picture is derived from (IDC and Statista, 2021).

The emergence of IoT devices especially smart phone greatly increased the
demand for network text and image data in several aspects. The amount of data
created consumed and stored change since 2010 is visually shown in the figure
5. The rise of social media was one of the main factors. At the time of the
release of iPhone 4, social media such as Facebook, Twitter and Instagram were
becoming increasingly popular and the portability and features of smart phones
made them ideal devices for users to communicate and share content on these
platforms, resulting in a rapid growth in the demand for text and image data
on social media platforms. The continuously upgraded camera technology has
enabled mobile phone users to easily take high-quality photos and videos,
allowing users to upload and share more image data on social media, photo
sharing platforms, and other online services.

The expansion of the App Store was also an important factor. With the
development of the smartphone, the ecosystem of the App Store was further
developed, with more developers creating applications for mobile, including
social media applications, photo editing applications, games, news readers,
etc., making it easier for users to access and share text and image data and
further increasing the demand for such data. Finally, with the increasing
demand for high-quality text and image data, content creators and companies
began to invest more energy and resources into creating and publishing such
content, leading to a rapid increase in the amount of text and image data.
Overall, the emergence of smartphones, with their innovations and
improvements, has greatly increased the demand for text and image data, which
has to some extent contributed to the development of foundation models in
those fields.

###  4.2. The 3D field awaits its own ’iPhone4’

In the field of technology, the iPhone 4 is not only a mobile phone, but also
an important milestone. Its emergence made the global audience amazed and
changed the pattern of the smartphone industry. Today, the 3D field is also in
need of a product with the same influence to promote the development and
popularization of the industry. We are looking forward to the birth of a 3D
product that can lead the trend and make people rethink the value of this
technology. In the past few years, 3D technology has made great progress,
however, there is still a certain distance from the mainstream market
acceptance and wide applications. We can think from the following aspects how
the 3D field can welcome its ”iPhone 4”.

First of all, 3D products need to have stronger usability. Just as the iPhone
4 improved the touchscreen, operating system and user interface, making the
phone more intuitive and easy to use, 3D technology also needs to make
breakthroughs in this area. Both hardware and software need to provide users
with an intuitive operating experience, reduce the learning cost, and make it
easier for more people to get started. Secondly, innovative business models
and application scenarios are crucial. The iPhone 4 created a huge application
market for developers, attracting the birth of countless wonderful
applications. The 3D field also needs to find a similar breakthrough, so that
3D technology is no longer limited to certain specific scenarios, but become
an indispensable part of our daily life. Finally, the 3D field needs a leading
enterprise to lead innovation. Apple has become the leader of the smartphone
market with the success of the iPhone 4. The 3D field also needs an enterprise
with vision and strength to drive technological progress and market
competition. Such an enterprise can not only lead the market trend, but also
drive the technological innovation and application expansion of the entire
industry. Overall, in the 3D field, a popular consumer-level product is
expected to promote the demand for 3D data, thus further promoting the
development of deep learning in the 3D field.

##  5\. Conclusion

Given that ChatGPT dominates the NLP field for solving almost all text tasks
with a single model, this work provides a brief view on when such a model
might come to the computer vision field, that ranges from 2D vision to 3D
vision.

## References

  * (1)
  * Adamopoulou and Moussiades (2020) Eleni Adamopoulou and Lefteris Moussiades. 2020.  An overview of chatbot technology. In _Artificial Intelligence Applications and Innovations: 16th IFIP WG 12.5 International Conference, AIAI 2020, Neos Marmaras, Greece, June 5–7, 2020, Proceedings, Part II 16_. Springer, 373–383.
  * Allahyari et al. (2017) Mehdi Allahyari, Seyedamin Pouriyeh, Mehdi Assefi, Saeid Safaei, Elizabeth D Trippe, Juan B Gutierrez, and Krys Kochut. 2017.  Text summarization techniques: a brief survey.  _arXiv preprint arXiv:1707.02268_ (2017).
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020\.  Language models are few-shot learners.  _Advances in neural information processing systems_ 33 (2020), 1877–1901.
  * Cho et al. (2014) Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014\.  Learning phrase representations using RNN encoder-decoder for statistical machine translation.  _arXiv preprint arXiv:1406.1078_ (2014).
  * Daniel et al. (2007) Jurafsky Daniel, Martin James H, et al. 2007\.  _Speech and language processing: An introduction to natural language processing, computational linguistics, and speech recognition_.  prentice hall.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ (2018).
  * Feizc (2023) Feizc. 2023.  IEA.  https://github.com/feizc/IEA GitHub repository.
  * Han et al. (2023) Dongsheng Han, Chaoning Zhang, Yu Qiao, Maryam Qamar, Yuna Jung, SeungKyu Lee, Sung-Ho Bae, and Choong Seon Hong. 2023\.  Segment Anything Model (SAM) Meets Glass: Mirror and Transparent Objects Cannot Be Easily Detected.  _arXiv preprint_ (2023).
  * Han et al. (2021) Xu Han, Zhengyan Zhang, Ning Ding, Yuxian Gu, Xiao Liu, Yuqi Huo, Jiezhong Qiu, Yuan Yao, Ao Zhang, Liang Zhang, et al. 2021\.  Pre-trained models: Past, present and future.  _AI Open_ 2 (2021), 225–250.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 770–778.
  * He et al. (2021) Yong He, Hongshan Yu, Xiaoyan Liu, Zhengeng Yang, Wei Sun, Yaonan Wang, Qiang Fu, Yanmei Zou, and Ajmal Mian. 2021.  Deep learning based 3D segmentation: A survey.  _arXiv preprint arXiv:2103.05423_ (2021).
  * IDC and Statista (2021) IDC and Statista. 2021\.  Total data volume worldwide 2010-2025.  https://www.statista.com/statistics/871513/worldwide-data-created/.
  * IDEA-Research (2023) IDEA-Research. 2023\.  Grounded Segment Anything.  https://github.com/IDEA-Research/Grounded-Segment-Anything GitHub repository.
  * Kevmo (2023) Kevmo. 2023.  magic-copy.  https://github.com/kevmo314/magic-copy GitHub repository.
  * Kirillov et al. (2023) Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al. 2023\.  Segment anything.  _arXiv preprint arXiv:2304.02643_ (2023).
  * Koehn (2009) Philipp Koehn. 2009\.  _Statistical machine translation_.  Cambridge University Press.
  * Krizhevsky et al. (2017) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2017\.  Imagenet classification with deep convolutional neural networks.  _Commun. ACM_ 60, 6 (2017), 84–90.
  * Long et al. (2015) Jonathan Long, Evan Shelhamer, and Trevor Darrell. 2015\.  Fully convolutional networks for semantic segmentation. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 3431–3440.
  * Mildenhall et al. (2021) Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng. 2021\.  Nerf: Representing scenes as neural radiance fields for view synthesis.  _Commun. ACM_ 65, 1 (2021), 99–106.
  * Nichol et al. (2022) Alex Nichol, Heewoo Jun, Prafulla Dhariwal, Pamela Mishkin, and Mark Chen. 2022.  Point-E: A System for Generating 3D Point Clouds from Complex Prompts.  _arXiv preprint arXiv:2212.08751_ (2022).
  * OpenAI (2023) OpenAI. 2023.  GPT-4 Technical Report.  arXiv:2303.08774 [cs.CL]
  * Poole et al. (2022) Ben Poole, Ajay Jain, Jonathan T Barron, and Ben Mildenhall. 2022\.  Dreamfusion: Text-to-3d using 2d diffusion.  _arXiv preprint arXiv:2209.14988_ (2022).
  * Radford et al. (2018) Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. 2018\.  Improving language understanding by generative pre-training.  (2018).
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019\.  Language models are unsupervised multitask learners.  _OpenAI blog_ 1, 8 (2019), 9.
  * Ramesh et al. (2022) Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. 2022.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_ (2022).
  * Ramesh et al. (2021) Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. 2021\.  Zero-shot text-to-image generation. In _International Conference on Machine Learning_. PMLR, 8821–8831.
  * Roser and Ritchie (2020) Max Roser and Hannah Ritchie. 2020.  Moore’s law.  https://en.wikipedia.org/wiki/Moore%27s_law#/media/File:Moore’s_Law_Transistor_Count_1970-2020.png.
  * Shi et al. (2022) Zifan Shi, Sida Peng, Yinghao Xu, Yiyi Liao, and Yujun Shen. 2022.  Deep generative models on 3d representations: A survey.  _arXiv preprint arXiv:2210.15663_ (2022).
  * Szegedy et al. (2015) Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. 2015.  Going deeper with convolutions. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 1–9.
  * Szeliski (2022) Richard Szeliski. 2022\.  _Computer vision: algorithms and applications_.  Springer Nature.
  * Tan and Le (2019) Mingxing Tan and Quoc Le. 2019.  Efficientnet: Rethinking model scaling for convolutional neural networks. In _International conference on machine learning_. PMLR, 6105–6114.
  * Tang et al. (2023) Lv Tang, Haoke Xiao, and Bo Li. 2023.  Can sam segment anything? when sam meets camouflaged object detection.  _arXiv preprint arXiv:2304.04709_ (2023).
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ 30 (2017).
  * Wu and Chen (2015) Meiyin Wu and Li Chen. 2015\.  Image recognition based on deep learning. In _2015 Chinese automation congress (CAC)_. IEEE, 542–546.
  * Yu et al. (2022) Xumin Yu, Lulu Tang, Yongming Rao, Tiejun Huang, Jie Zhou, and Jiwen Lu. 2022\.  Point-bert: Pre-training 3d point cloud transformers with masked point modeling. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 19313–19322.
  * Zhang et al. (2023a) Chenshuang Zhang, Chaoning Zhang, Taegoo Kang, Donghun Kim, Sung-Ho Bae, and In So Kweon. 2023a.  Attack-SAM: Towards Evaluating Adversarial Robustness of Segment Anything Model.  _arXiv preprint_ (2023).
  * Zhang et al. (2023b) Chaoning Zhang, Chenshuang Zhang, Chenghao Li, Yu Qiao, Sheng Zheng, Sumit Kumar Dam, Mengchun Zhang, Jung Uk Kim, Seong Tae Kim, Jinwoo Choi, et al. 2023b.  One small step for generative ai, one giant leap for agi: A complete survey on chatgpt in aigc era.  _arXiv preprint arXiv:2304.06488_ (2023).
  * Zhang et al. (2023c) Chaoning Zhang, Chenshuang Zhang, Sheng Zheng, Yu Qiao, Chenghao Li, Mengchun Zhang, Sumit Kumar Dam, Chu Myaet Thwal, Ye Lin Tun, Le Luang Huy, et al. 2023c.  A Complete Survey on Generative AI (AIGC): Is ChatGPT from GPT-4 to GPT-5 All You Need?  _arXiv preprint arXiv:2303.11717_ (2023).
  * Zou et al. (2019) Zhengxia Zou, Zhenwei Shi, Yuhong Guo, and Jieping Ye. 2019\.  Object detection in 20 years: A survey.  _arXiv preprint arXiv:1905.05055_ (2019).


# Termination of linear loops under commutative updates

Ruiwen Dong<EMAIL_ADDRESS>University of OxfordDepartment of
Computer Science, 7 Parks RoadOxfordUnited KingdomOX1 3QG

###### Abstract.

We consider the following problem: given $d\times d$ rational matrices
$A_{1},\ldots,A_{k}$ and a polyhedral cone $\mathcal{C}\subset\mathbb{R}^{d}$,
decide whether there exists a non-zero vector whose orbit under multiplication
by $A_{1},\ldots,A_{k}$ is contained in $\mathcal{C}$. This problem can be
interpreted as verifying the termination of multi-path while loops with linear
updates and linear guard conditions. We show that this problem is decidable
for _commuting_ invertible matrices $A_{1},\ldots,A_{k}$. The key to our
decision procedure is to reinterpret this problem in a purely algebraic
manner. Namely, we discover its connection with modules over the polynomial
ring $\mathbb{R}[X_{1},\ldots,X_{k}]$ as well as the polynomial semiring
$\mathbb{R}_{\geq 0}[X_{1},\ldots,X_{k}]$. The loop termination problem is
then reduced to deciding whether a submodule of
$\left(\mathbb{R}[X_{1},\ldots,X_{k}]\right)^{n}$ contains a “positive”
element.

loop termination, commuting matrices, positive polynomials, module over
polynomial ring

###### Acknowledgements.

The author acknowledges support from UKRI Frontier Research Grant
EP/X033813/1.

##  1\. Introduction

We consider the termination problem for multipath (or branching) linear loops
over the real numbers. We are concerned with problems of the following form:
given $d\times d$ matrices $A_{1},\ldots,A_{k}$ and a subset $\mathcal{C}$ of
$\mathbb{R}^{d}$, decide whether there exists a vector
$\boldsymbol{v}\in\mathcal{C}$ whose orbit under multiplication by
$A_{1},\ldots,A_{k}$ is contained in $\mathcal{C}$. In other words, denote by
$\langle A_{1},\ldots,A_{k}\rangle$ the monoid generated by
$A_{1},\ldots,A_{k}$, we want to decide whether there exists
$\boldsymbol{v}\in\mathcal{C}$ such that $A\boldsymbol{v}\in\mathcal{C}$ for
all $A\in\langle A_{1},\ldots,A_{k}\rangle$. Such a problem can be interpreted
as the non-termination of the following linear loop:

(1) $\textit{while }\boldsymbol{x}\in\mathcal{C}\textit{ do
}(\boldsymbol{x}\coloneqq A_{1}\boldsymbol{x}\textit{ or }\cdots\textit{ or
}\boldsymbol{x}\coloneqq A_{k}\boldsymbol{x}).$

The problem is whether there exists an initial value $\boldsymbol{v}$ such
that the loop never terminates. Analysis of loops of this form is an important
part of analysing more complex programs (jeannet2014abstract, ;
kincaid2019closed, ). Various tools such as computing polynomial invariants
(hrushovski2018polynomial, ), porous invariants (lefaucheux2021porous, ),
ranking functions (ben2014ranking, ; ben2019multiphase, ) have been developed
to analyse properties of such multipath loops.

Termination of linear loops with a _single_ update ($k=1$) has been intensely
studied for the last twenty years. Tiwari (tiwari2004termination, ) first
showed its decidability in the case where the guard condition $\mathcal{C}$ is
a convex polyhedron. Subsequently, Braverman (braverman2006termination, )
extended the decidability result to the case where $\mathcal{C}$ is the set of
rational points in a convex polyhedron; and Hosseini, Ouaknine, Worrell
(HosseiniO019, ) further extended the result to integer points.111The original
results all concern single _affine_ updates. However, they are equivalent to
the case of _linear_ updates by increasing the dimension by one and
homogenizing the coordinates.

In the above results, the decidability relies on the freedom of choosing the
initial value $\boldsymbol{v}$ to circumvent the difficulties inherent in
deciding termination on a single initial value. In fact, when $\mathcal{C}$ is
a closed halfspace, termination of single-path linear loops for a _fixed_
initial value, that is,

(2) $\boldsymbol{x}\coloneqq\boldsymbol{v};\textit{ while
}\boldsymbol{x}\in\mathcal{C}\textit{ do }(\boldsymbol{x}\coloneqq
A\boldsymbol{x}),$

subsumes the _Positivity Problem_ (ouaknine2014positivity, ). The Positivity
Problem at dimension greater than five has been shown to be intrinsically
hard; and its decidability would entail major breakthroughs in open problems
in Diophantine approximation (ouaknine2014positivity, ). Therefore, the
freedom of choice for the initial value is crucial in proving decidability
results.

In this paper we consider termination of the multipath loop (1) under
_commutative_ updates, that is, when $A_{1},\ldots,A_{k}$ are commuting
matrices. In (babai1996multiplicative, ), Babai, Beals, Cai, Ivanyos and Luks
proved various results on reachability problems of multipath linear loops
under commutative updates. A continuous analogue of the reachability problem
has been studied in (ouaknine2019decidability, ). For the termination problem,
we restrict to the case where $\mathcal{C}$ is a _polyhedral cone_ , that is,

$\mathcal{C}\coloneqq\left\\{\boldsymbol{x}\in\mathbb{R}^{d}\;\middle|\;\boldsymbol{c}_{i}^{\top}\boldsymbol{x}\geq
0,i=1,\ldots,n\right\\}$

for some $\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{n}\in\mathbb{R}^{d}$. We
will also exclude the initial value $(0,\ldots,0)$ since it is trivially
invariant under linear updates. For the sake of simplicity, we will suppose
$A_{1},\ldots,A_{k}$ to have rational entries and are invertible, and that
$\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{n}\in\mathbb{Q}^{d}$. Our main
result (see Theorem 5) is that termination of such multipath linear loops is
decidable.

If one tries to adapt the proofs for the single update case to multiple
updates, natural attempts will start by simultaneously diagonalizing the
update matrices and analysing their actions on the cone geometrically.
Unfortunately such analysis depends on classifying the complex eigenvalues of
all the update matrices. Besides the unavoidable tedious case analysis, it is
also not clear how to circumvent certain problems related to Diophantine
approximation, as such circumvention appears ad hoc in the single update case.
Our main contribution is a completely algebraic approach that overcomes this
difficulty. In particular, using the duality of linear programming, we reduce
the problem to deciding whether an orbit cone is _salient_. We show that
deciding whether an orbit is salient is equivalent to deciding whether a
submodule of $\left(\mathbb{R}[X_{1},\ldots,X_{k}]\right)^{n}$ contains an
element with only positive coefficients. We then use a result of Einsiedler,
Mouat, and Tuncel (einsiedler2003does, ) and the decidability of first order
theory of the reals to deduce the desired result.

##  2\. Preliminaries

###  2.1. Convex geometry

A _convex cone_ in $\mathbb{R}^{d}$ is a subset
$\mathcal{C}\subset\mathbb{R}^{d}$ that satisfies $r\in\mathbb{R}_{\geq
0},\boldsymbol{v}\in\mathcal{C}\implies r\cdot\boldsymbol{v}\in\mathcal{C}$
and
$\boldsymbol{v},\boldsymbol{w}\in\mathcal{C}\implies\boldsymbol{v}+\boldsymbol{w}\in\mathcal{C}$.
In this article, we will use the word _cone_ to imply convex cones. A
_polyhedral_ cone is a cone of the form

$\mathcal{C}\coloneqq\left\\{\boldsymbol{x}\in\mathbb{R}^{d}\;\middle|\;\boldsymbol{c}_{i}^{\top}\boldsymbol{x}\geq
0,i=1,\ldots,n\right\\}.$

for finitely many given non-zero vectors
$\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{n}\in\mathbb{R}^{d}$.

Given mutually commuting matrices $A_{1},\ldots,A_{k}\in\mathbb{R}^{d\times
d}$, and a vector $\boldsymbol{v}\in\mathbb{R}^{d}$, denote by

$\langle
A_{1},\ldots,A_{k}\rangle\cdot\boldsymbol{v}\coloneqq\left\\{A_{1}^{n_{1}}\cdots
A_{k}^{n_{k}}\boldsymbol{v}\;\middle|\;n_{1},\ldots,n_{k}\in\mathbb{N}\right\\}$

the orbit of $\boldsymbol{v}$ under multiplication by $A_{1},\ldots,A_{k}$.
Similarly, given a cone $\mathcal{C}\subset\mathbb{R}^{d}$, denote by

$\langle
A_{1},\ldots,A_{k}\rangle\cdot\mathcal{C}\coloneqq\left\\{A_{1}^{n_{1}}\cdots
A_{k}^{n_{k}}\boldsymbol{v}\;\middle|\;n_{1},\ldots,n_{k}\in\mathbb{N},\boldsymbol{v}\in\mathcal{C}\right\\}$

the orbit of $\mathcal{C}$ under multiplication by $A_{1},\ldots,A_{k}$.

Given an arbitrary subset $\mathcal{S}\subset\mathbb{R}^{d}$, denote by
$\boldsymbol{cone}(\mathcal{S})$ the smallest cone in $\mathbb{R}^{d}$
containing $\mathcal{S}$. Similarly, denote by $\boldsymbol{lin}(\mathcal{S})$
the smallest linear space in $\mathbb{R}^{d}$ containing $\mathcal{S}$.

A _closed halfspace_ of a $\mathbb{R}^{d}$ is a subset $\mathcal{H}$ defined
by
$\mathcal{H}\coloneqq\\{\boldsymbol{x}\mid\boldsymbol{v}^{\top}\boldsymbol{x}\geq
0\\}$ for some $\boldsymbol{v}\in\mathbb{R}^{d}\setminus\\{0^{d}\\}$. Here,
$0^{d}$ denotes the zero vector of $\mathbb{R}^{d}$. By the Supporting
Hyperplane Theorem (boyd2004convex, , Chapter 2.5.2) (applied at the point
$0^{d}$), every cone $\mathcal{C}\subset\mathbb{R}^{d}$ is either contained in
some closed halfspace or it is $\mathbb{R}^{d}$ itself.

A cone $\mathcal{C}$ is called _salient_ if
$\mathcal{C}\cap-\mathcal{C}=\\{0^{d}\\}$, where
$-\mathcal{C}\coloneqq\\{-\boldsymbol{v}\mid\boldsymbol{v}\in\mathcal{C}\\}$.
An arbitrary set $\mathcal{S}\subset\mathbb{R}^{d}$ is called salient if
$\boldsymbol{cone}(\mathcal{S})$ is salient. Obviously every salient cone (and
hence every salient set) is contained in a closed halfspace because a salient
cone cannot be $\mathbb{R}^{d}$.

###  2.2. Modules over polynomial rings

Fix an integer $k\geq 1$. In this paper we consider the polynomial ring
$\mathbb{A}\coloneqq\mathbb{R}[X_{1},\ldots,X_{k}]$ and its sub-semiring

$\mathbb{A}^{+}=\mathbb{R}_{\geq 0}[X_{1},\ldots,X_{k}]\\\
\coloneqq\Bigg{\\{}\sum_{n_{1},\ldots,n_{k}\in\mathbb{N}}r_{n_{1},\ldots,n_{k}}X_{1}^{n_{1}}\cdots
X_{k}^{n_{k}}\;\Bigg{|}\;r_{n_{1},\ldots,n_{k}}\in\mathbb{R}_{\geq 0},\\\
r_{n_{1},\ldots,n_{k}}=0\text{ for all but finitely many
}r_{n_{1},\ldots,n_{k}}\Bigg{\\}}.$

That is, $\mathbb{A}^{+}\subset\mathbb{A}$ is the sub-semiring of polynomials
with non-negative coefficients. Define additionally
$\mathbb{A}^{++}\coloneqq\mathbb{A}^{+}\setminus\\{0\\}$.

Let $\mathbb{A}^{n}\coloneqq\\{(f_{1},\ldots,f_{n})\mid
f_{1},\ldots,f_{n}\in\mathbb{A}\\}$. An $\mathbb{A}$-_submodule_ of
$\mathbb{A}^{n}$ is a subset $\mathcal{M}\subset\mathbb{A}^{n}$ such that
$\boldsymbol{v},\boldsymbol{w}\in\mathcal{M}\implies\boldsymbol{v}+\boldsymbol{w}\in\mathcal{M}$
and $f\in\mathbb{A},\boldsymbol{v}\in\mathcal{M}\implies
f\cdot\boldsymbol{v}\in\mathcal{M}$. Here
$f\cdot(f_{1},\ldots,f_{n})\coloneqq(ff_{1},\ldots,ff_{n})$.

For example, given
$\boldsymbol{g}_{1},\ldots,\boldsymbol{g}_{m}\in\mathbb{A}^{n}$, the set

$\mathcal{M}=\boldsymbol{g}_{1}\mathbb{A}+\cdots+\boldsymbol{g}_{m}\mathbb{A}\\\
\coloneqq\\{f_{1}\cdot\boldsymbol{g}_{1}+\cdots+f_{m}\cdot\boldsymbol{g}_{m}\mid
f_{1},\ldots,f_{m}\in\mathbb{A}\\}$

is an $\mathbb{A}$-submodule of $\mathbb{A}^{n}$. In this case we will say
that $\boldsymbol{g}_{1},\ldots,\boldsymbol{g}_{m}$ form a _basis_ of
$\mathcal{M}$. The above definition still works when one replaces $\mathbb{A}$
by any commutative ring.

Naturally, we define the following subset of $\mathbb{A}^{n}$:

$\left(\mathbb{A}^{+}\right)^{n}\coloneqq\\{(f_{1},\ldots,f_{n})\mid
f_{1},\ldots,f_{n}\in\mathbb{A}^{+}\\}.$

The key ingredient of our paper is a deep result by Einsiedler, Mouat, and
Tuncel (einsiedler2003does, ) that characterizes when an
$\mathbb{A}$-submodule of $\mathbb{A}^{n}$ contains an element of
$\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}$. We will state this
result in Section 6.

##  3\. Overview of the decision procedure

In this section we give an overview of the procedure that decides
(non-)termination of the multipath loops under commutative updates. In
rigorous terms, given commuting matrices $A_{1},\ldots,A_{k}$ and a polyhedral
cone $\mathcal{C}$, we want to decide whether there exists a vector
$\boldsymbol{v}\in\mathbb{R}^{d}\setminus\\{0^{d}\\}$, such that $\langle
A_{1},\ldots,A_{k}\rangle\cdot\boldsymbol{v}\subset\mathcal{C}$.

Let the cone $\mathcal{C}$ be given by

(3)
$\mathcal{C}\coloneqq\left\\{\boldsymbol{x}\in\mathbb{R}^{d}\;\middle|\;\boldsymbol{c}_{i}^{\top}\boldsymbol{x}\geq
0,i=1,\ldots,n\right\\}.$

We define its _dual cone_ $\mathcal{C}^{*}$ as

(4)
$\mathcal{C}^{*}\coloneqq\left\\{\boldsymbol{x}\in\mathbb{R}^{d}\;\middle|\;\boldsymbol{x}=r_{1}\boldsymbol{c}_{1}+\cdots+r_{n}\boldsymbol{c}_{n},r_{1},\ldots,r_{n}\in\mathbb{R}_{\geq
0}\right\\}.$

Our first lemma is a duality type argument that reduces the termination
problem to deciding whether an orbit is contained in some halfspace.

###### Lemma 1.

The following two conditions are equivalent:

  1. (i)

There exists $\boldsymbol{v}\in\mathbb{R}^{d}\setminus\\{0^{d}\\}$, such that
$\langle A_{1},\ldots,A_{k}\rangle\cdot\boldsymbol{v}\subset\mathcal{C}$.

  2. (ii)

The orbit $\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}$ is contained in a
closed halfspace.

The proof of Lemma 1 is given in Section 4. Deciding whether an orbit has the
property of being contained in a closed halfspace is challenging. In
particular, the smallest cone containing the orbit might not be finitely
generated. It is very unlikely that one can compute any precise description of
this cone, otherwise one would be able to decide whether it is contained in a
_given_ halfspace, and hence solve the Positivity Problem, entailing
breakthroughs in number theory (ouaknine2014positivity, ). Therefore, we will
first devise a procedure that decides a similar property for the orbit, namely
whether it is salient. We will later use it as a sub-procedure to decide
whether the orbit is contained in a closed halfspace. The next lemma reduces
deciding salient-ness to finding certain tuples of polynomials in
$\mathbb{A}^{+}$.

###### Lemma 2.

The following two conditions are equivalent:

  1. (i)

The orbit $\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}$ is not salient.

  2. (ii)

There exists a tuple of polynomials
$(f_{1},\ldots,f_{n})\in\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}$,
not all zero, such that
$\sum_{i=1}^{n}f_{i}(A_{1}^{\top},\ldots,A_{k}^{\top})\cdot\boldsymbol{c}_{i}=0^{d}$.

The proof of Lemma 2 is given in Section 4.

Define the following $\mathbb{A}$-submodule of $\mathbb{A}^{n}$.

(5)
$\mathcal{M}\coloneqq\left\\{(f_{1},\ldots,f_{n})\in\mathbb{A}^{n}\;\middle|\;\sum_{i=1}^{n}f_{i}(A_{1}^{\top},\ldots,A_{k}^{\top})\cdot\boldsymbol{c}_{i}=\boldsymbol{0}\right\\}.$

One easily verifies that
$\boldsymbol{g},\boldsymbol{h}\in\mathcal{M}\implies\boldsymbol{g}+\boldsymbol{h}\in\mathcal{M}$,
as well as $f\in\mathbb{A},\boldsymbol{g}\in\mathcal{M}\implies
f\cdot\boldsymbol{g}\in\mathcal{M}$; so $\mathcal{M}$ is indeed an
$\mathbb{A}$-module. Observe that condition (ii) of Lemma 2 can be expressed
as “$\mathcal{M}$ contains an element of
$\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{d}\\}^{n}$”. The next
proposition shows that a basis of $\mathcal{M}$ is computable.

###### Proposition 3.

Given as input $A_{1},\ldots,A_{k}$ and
$\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{n}$, one can compute a basis
$\boldsymbol{g}_{1},\ldots,\boldsymbol{g}_{m}\in\mathbb{A}^{n}$ such that
$\mathcal{M}=\boldsymbol{g}_{1}\mathbb{A}+\cdots+\boldsymbol{g}_{m}\mathbb{A}$.

The proof of Proposition 3 is given in Section 5. The next proposition shows
that it is decidable whether the module $\mathcal{M}$ contains an element of
$\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}$. Hence condition (ii) of
Lemma 2 is decidable.

###### Proposition 4.

There is a procedure that, given as input a basis
$\boldsymbol{g}_{1},\ldots,\boldsymbol{g}_{m}\in\mathbb{A}^{n}$ with rational
coefficients such that
$\mathcal{M}=\boldsymbol{g}_{1}\mathbb{A}+\cdots+\boldsymbol{g}_{m}\mathbb{A}$,
decides whether $\mathcal{M}$ contains an element of
$\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}$, and outputs this
element $\boldsymbol{f}$ in case it exists.

The proof of Proposition 4 is given in Section 6. Combining Lemma 2,
Proposition 3 and 4, we conclude that it is decidable whether the orbit
$\langle A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}$ is
salient. We now use this to show that it is decidable whether $\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}$ is contained in a
closed halfspace. This together with Lemma 1 will give us the main result:

###### Theorem 5.

Given commuting invertible matrices $A_{1},\ldots,A_{k}\in\mathbb{Q}^{d\times
d}$ and vectors
$\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{n}\in\mathbb{Q}^{d}$ defining a
polyhedral cone $\mathcal{C}$ as in Equation (3), it is decidable whether
there exists $\boldsymbol{v}\in\mathbb{R}^{d}\setminus\\{0^{d}\\}$ such that
$\langle A_{1},\ldots,A_{k}\rangle\cdot\boldsymbol{v}\subset\mathcal{C}$.

###### Proof.

By Lemma 1, it suffices to construct a procedure that decides whether the
orbit $\langle A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}$ is
contained in a closed halfspace. We use induction on $d$. When $d=1$, the
decision procedure is easy: $\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}$ is contained in a
closed halfspace if and only if $\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{n}$
all have the same sign and $A_{1},\ldots,A_{k}$ are all positive rationals.

Suppose we have a decision procedure for all dimensions smaller than $d$, we
now construct a procedure for dimension $d$. By Lemma 2, Proposition 3 and 4,
it is decidable whether the orbit $\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}$ is salient.

If the orbit is salient, then it is contained in some closed halfspace. If the
orbit is not salient, then $\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)$ contains
the vectors $\boldsymbol{w}$ and $-\boldsymbol{w}$ for some
$\boldsymbol{w}\in\mathbb{R}^{d}\setminus\\{0^{d}\\}$. Such a $\boldsymbol{w}$
can be effectively computed in the following way: by Proposition 4, one can
compute an element
$\boldsymbol{f}\in\mathcal{M}\cap\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}$.
Then, as in the proof of Lemma 2 (see Section 4), one can obtain from
$\boldsymbol{f}$ a non-zero vector $\boldsymbol{w}\in\mathbb{Q}^{d}$ such that
$\pm\boldsymbol{w}\in\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)$.

We then compute (a basis of) the linear space

$W\coloneqq\boldsymbol{lin}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\boldsymbol{w}\right).$

This can be done by starting with $W\coloneqq\mathbb{R}\boldsymbol{w}$ and
repeatedly replacing $W$ by $W+A_{1}W+\cdots+A_{k}W$ until
$W=W+A_{1}W+\cdots+A_{k}W$. This process must terminate since the dimension of
$W$ is always growing. The resulting $W=\boldsymbol{lin}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\boldsymbol{w}\right)$ is invariant
under the linear maps $A_{1}^{\top},\ldots,A_{k}^{\top}$. Since
$\mathbb{R}\boldsymbol{w}\subset\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)$ we have
$W\subset\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)$.

The quotient $\mathbb{R}^{d}/W$ is isomorphic to $\mathbb{R}^{d-\dim(W)}$
after fixing a basis. We can suppose this basis admits only rational entries.
Composing with the canonical map $\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}/W$
we have an (effectively computable) map

$\pi\colon\mathbb{R}^{d}\longrightarrow\mathbb{R}^{d-\dim(W)}$

with $\ker(\pi)=W$. Since multiplication by the matrices
$A_{1}^{\top},\ldots,A_{k}^{\top}$ leaves $W$ invariant, these matrices act on
$\mathbb{R}^{d}/W\cong\mathbb{R}^{d-\dim(W)}$ linearly. We denote these
actions by

$B_{1},\ldots,B_{k}\in\mathbb{Q}^{(d-\dim(W))\times(d-\dim(W))}.$

These matrices are obviously invertible, commuting and effectively computable.

Using the induction hypothesis on the dimension $d$, we can decide whether the
image

$\pi\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)=\langle
B_{1},\ldots,B_{k}\rangle\cdot\pi(\mathcal{C}^{*})$

is contained in some closed halfspace (of
$\mathbb{R}^{d}/W\cong\mathbb{R}^{d-\dim(W)}$). If the image $\pi\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)$ is
contained in a closed halfspace $\mathcal{H}\subset\mathbb{R}^{d-\dim(W)}$
then $\langle A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}$ is
contained in the closed halfspace
$\pi^{-1}(\mathcal{H})\subset\mathbb{R}^{d}$. Otherwise,

$\boldsymbol{cone}\left(\pi\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)\right)=\mathbb{R}^{d-\dim(W)}.$

Since
$\pi(\boldsymbol{v}+\boldsymbol{w})=\pi(\boldsymbol{v})+\pi(\boldsymbol{w})$
for all $\boldsymbol{v},\boldsymbol{w}\in\mathbb{R}^{d}$, the above equation
yields

$\pi\left(\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)\right)=\mathbb{R}^{d-\dim(W)}.$

Thus, any $\boldsymbol{v}\in\mathbb{R}^{d}$ can be written as
$\boldsymbol{v}^{\prime}+\boldsymbol{v}^{\prime\prime}$ where

$\boldsymbol{v}^{\prime}\in\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right),$

and $\boldsymbol{v}^{\prime\prime}\in W$. Recall that
$W\subset\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)$.
Therefore,
$\boldsymbol{v}=\boldsymbol{v}^{\prime}+\boldsymbol{v}^{\prime\prime}\in\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)$ for all
$\boldsymbol{v}\in\mathbb{R}^{d}$. So

$\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)=\mathbb{R}^{d}$

is not contained in any closed halfspace. ∎

##  4\. From linear loops to positive polynomials

In this section we give the proofs of Lemma 1 and 2.

See 1

###### Proof.

(i) $\implies$ (ii). Suppose
$\boldsymbol{v}\in\mathbb{R}^{d}\setminus\\{0^{d}\\}$, such that $\langle
A_{1},\ldots,A_{k}\rangle\cdot\boldsymbol{v}\subset\mathcal{C}$. Then by the
definition of $\mathcal{C}$, for all $n_{1},\ldots,n_{k}\in\mathbb{N}$ and
$i=1,\ldots,n$, we have $\boldsymbol{c}_{i}^{\top}A_{1}^{n_{1}}\cdots
A_{k}^{n_{k}}\boldsymbol{v}\geq 0$. Taking the transpose yields

(6)
$\boldsymbol{v}^{\top}\left(A_{k}^{\top}\right)^{n_{k}}\cdots\left(A_{1}^{\top}\right)^{n_{1}}\boldsymbol{c}_{i}\geq
0,\quad i=1,\ldots,n;n_{1},\ldots,n_{k}\in\mathbb{N}.$

Let $\mathcal{H}$ be the closed halfspace defined by
$\mathcal{H}\coloneqq\\{\boldsymbol{x}\in\mathbb{R}^{d}\mid\boldsymbol{v}^{\top}\boldsymbol{x}\geq
0\\}$. Then Equation (6) shows that $\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\boldsymbol{c}_{i}\subset\mathcal{H}$
for all $i$. Since the cone $\mathcal{C}^{*}$ is generated by
$\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{n}$, we have $\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\subset\mathcal{H}$.

(ii) $\implies$ (i). Suppose $\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}$ is contained in
the halfspace $\mathcal{H}$ defined by
$\mathcal{H}\coloneqq\\{\boldsymbol{x}\in\mathbb{R}^{d}\mid\boldsymbol{v}^{\top}\boldsymbol{x}\geq
0\\}$, where $\boldsymbol{v}\neq 0^{d}$. Then Equation (6) holds for all $i$
and all $n_{1},\ldots,n_{k}\in\mathbb{N}$. Taking the transpose yields
$\boldsymbol{c}_{i}^{\top}A_{1}^{n_{1}}\cdots A_{k}^{n_{k}}\boldsymbol{v}\geq
0$ and hence $\langle
A_{1},\ldots,A_{k}\rangle\cdot\boldsymbol{v}\subset\mathcal{C}$. ∎

See 2

###### Proof.

(i) $\implies$ (ii). If $\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}$ is not salient,
then there exists $\boldsymbol{v}\neq 0^{d}$ with
$\boldsymbol{v},-\boldsymbol{v}\in\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)$.
Therefore, there exist finitely many positive reals
$r_{i,n_{1},\ldots,n_{k}}$, such that

$\sum_{i=1}^{n}\sum_{n_{1},\ldots,n_{k}\in\mathbb{N}}r_{i,n_{1},\ldots,n_{k}}\left(A_{1}^{\top}\right)^{n_{1}}\cdots\left(A_{k}^{\top}\right)^{n_{k}}\cdot\boldsymbol{c}_{i}=\boldsymbol{v}.$

In order words, there exist polynomials with non-negative coefficients
$(g_{1},\ldots,g_{n})\in\left(\mathbb{A}^{+}\right)^{n}$, such that
$\sum_{i=1}^{n}g_{i}(A_{1}^{\top},\ldots,A_{k}^{\top})\cdot\boldsymbol{c}_{i}=\boldsymbol{v}$.
Similarly, there exist polynomials
$(h_{1},\ldots,h_{n})\in\left(\mathbb{A}^{+}\right)^{n}$, such that
$\sum_{i=1}^{n}h_{i}(A_{1}^{\top},\ldots,A_{k}^{\top})\cdot\boldsymbol{c}_{i}=-\boldsymbol{v}$.
Since $\boldsymbol{v}\neq 0^{d}$, we know that $g_{1},\ldots,g_{n}$ are not
all zero. Let $f_{i}\coloneqq g_{i}+h_{i},i=1,\ldots,n$, then
$\sum_{i=1}^{n}f_{i}(A_{1}^{\top},\ldots,A_{k}^{\top})\cdot\boldsymbol{c}_{i}=0^{d}$;
and
$(f_{1},\ldots,f_{n})\in\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}$.

(ii) $\implies$ (i). Suppose
$\sum_{i=1}^{n}f_{i}(A_{1}^{\top},\ldots,A_{k}^{\top})\cdot\boldsymbol{c}_{i}=0^{d}$
for some
$(f_{1},\ldots,f_{n})\in\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}$.
Without loss of generality suppose $f_{1}\neq 0$. Let $g$ be a monomial of
$f_{1}$ and write $f_{1}=g+f^{\prime}_{1}$. Since $f_{1}\in\mathbb{A}^{+}$, we
have also $g,f^{\prime}_{1}\in\mathbb{A}^{+}$. We have
$\boldsymbol{v}\coloneqq
g(A_{1}^{\top},\ldots,A_{k}^{\top})\cdot\boldsymbol{c}_{1}\neq 0^{d}$ because
$A_{1}^{\top},\ldots,A_{k}^{\top}$ are invertible, $\boldsymbol{c}_{1}\neq
0^{d}$ and because $g$ is a monomial. Then
$\boldsymbol{v}=g(A_{1}^{\top},\ldots,A_{k}^{\top})\cdot\boldsymbol{c}_{1}\in\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}$ and

$-\boldsymbol{v}=f^{\prime}_{1}(A_{1}^{\top},\ldots,A_{k}^{\top})\cdot\boldsymbol{c}_{1}+\sum_{i=2}^{n}f_{i}(A_{1}^{\top},\ldots,A_{k}^{\top})\cdot\boldsymbol{c}_{i}\\\
\in\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right).$

Thus, $\boldsymbol{cone}\left(\langle
A_{1}^{\top},\ldots,A_{k}^{\top}\rangle\cdot\mathcal{C}^{*}\right)$ contains
both $\boldsymbol{v}$ and $-\boldsymbol{v}$ and is therefore not salient. ∎

##  5\. Computing the module $\mathcal{M}$

In this section we prove Proposition 3. Let
$\boldsymbol{e}_{1},\ldots,\boldsymbol{e}_{n}$ be the standard basis of
$\mathbb{A}^{n}$, that is,

$\boldsymbol{e}_{i}=(0,\cdots,0,1,0,\cdots,0),$

where the $i$-th coordinate is one.

The vector space $\mathbb{R}^{d}$ can be considered as an $\mathbb{A}$-module
by $f\cdot\boldsymbol{v}\coloneqq
f(A_{1}^{\top},\ldots,A_{k}^{\top})\boldsymbol{v}$ for all
$f\in\mathbb{A},\boldsymbol{v}\in\mathbb{R}^{d}$. Define the following map of
$\mathbb{A}$-modules:

(7) $\displaystyle\varphi:\mathbb{A}^{n}$
$\displaystyle\longrightarrow\mathbb{R}^{d},$ (8)
$\displaystyle\sum_{i=1}^{n}f_{i}\boldsymbol{e}_{i}$
$\displaystyle\mapsto\sum_{i=1}^{n}f_{i}(A_{1}^{\top},\ldots,A_{k}^{\top})\boldsymbol{c}_{i}.$

Then the $\mathbb{A}$-module $\mathcal{M}$ defined in (5) is exactly
$\ker(\varphi)$.

See 3

###### Proof.

Let $F_{1}\in\mathbb{R}[X_{1}],\ldots,F_{k}\in\mathbb{R}[X_{k}]$ be the
(monic) characteristic polynomials of $A_{1}^{\top},\ldots,A_{k}^{\top}$,
respectively. Then $F_{j}(A_{j}^{\top})=0^{d\times d}$, so obviously
$F_{j}\boldsymbol{e}_{i}\in\mathcal{M}$ for all $1\leq j\leq k,1\leq i\leq n$.
Define the (finite) set of monomials

$S\coloneqq\\{X_{1}^{n_{1}}\cdots X_{k}^{n_{k}}\boldsymbol{e}_{i}\mid
n_{1}<\deg F_{1},\ldots,n_{k}<\deg F_{k},1\leq i\leq n\\}.$

Consider the map

(9) $\displaystyle\lambda:\mathbb{R}^{\operatorname{card}(S)}$
$\displaystyle\longrightarrow\mathbb{R}^{d},$ (10) $\displaystyle(r_{s})_{s\in
S}$ $\displaystyle\mapsto\sum_{s\in S}r_{s}\varphi(s).$

One can effectively compute a basis $(r_{1s})_{s\in S},\ldots,(r_{ps})_{s\in
S}$ of $\ker(\lambda)$. Define the set

$\mathcal{R}\coloneqq\left\\{\sum_{s\in S}r_{js}\cdot
s\;\middle|\;j=1,\ldots,p\right\\}$

of elements in $\mathbb{A}^{n}$. Clearly
$\mathcal{R}\subset\ker(\varphi)=\mathcal{M}$. Define additionally the
following subset of $\mathcal{M}$:

$\mathcal{F}\coloneqq\left\\{F_{j}\boldsymbol{e}_{i}\;\middle|\;1\leq j\leq
k,1\leq i\leq n\right\\}.$

We claim that $\mathcal{R}\cup\mathcal{F}$ is a basis for $\mathcal{M}$.

To prove this claim, let $L$ be the $\mathbb{A}$-module generated by
$\mathcal{R}\cup\mathcal{F}$. It is a submodule of $\mathcal{M}$. We will show
$L=\mathcal{M}$. Let $\boldsymbol{f}=\sum_{i=1}^{n}f_{i}\boldsymbol{e}_{i}$ be
an element of $\mathcal{M}$.

Every monomial $m\coloneqq X_{1}^{n_{1}}\cdots X_{k}^{n_{k}}$ of every
polynomial $f_{i},i=1,\ldots,n,$ can be written as two polynomials
$m=p^{\prime}+p^{\prime\prime}$ such that
$p^{\prime\prime}\boldsymbol{e}_{i}\in L$ and every monomial of
$p^{\prime}\boldsymbol{e}_{i}$ is in the set $S$. Indeed, denote
$J\coloneqq\\{1\leq j\leq k\mid n_{j}>\deg F_{j}\\}$. We write
$J=\\{i_{1},\ldots,i_{d}\\}$ for some $d\leq k$, and where
$i_{1},\ldots,i_{d},i_{d+1},\ldots,i_{k}$ is some permutation of
$(1,\ldots,k)$. We divide $X_{j}^{n_{j}}$ by $F_{j}$ for every $j\in J$ and
obtain

$X_{j}^{n_{j}}=P_{j}F_{j}+R_{j}$

with $\deg R_{j}<\deg F_{j}$. Then

$m-(P_{i_{1}}F_{i_{1}})X_{i_{2}}^{n_{i_{2}}}\cdots
X_{i_{k}}^{n_{i_{k}}}=R_{i_{1}}X_{i_{2}}^{n_{i_{2}}}\cdots
X_{i_{k}}^{n_{i_{k}}},$

with $(P_{i_{1}}F_{i_{1}})X_{i_{2}}^{n_{i_{2}}}\cdots
X_{i_{k}}^{n_{i_{k}}}\boldsymbol{e}_{i}\in L$, and

$R_{i_{1}}X_{i_{2}}^{n_{i_{2}}}\cdots\,X_{i_{k}}^{n_{i_{k}}}-R_{i_{1}}(P_{i_{2}}F_{i_{2}})X_{i_{3}}^{n_{i_{3}}}\cdots\,X_{i_{k}}^{n_{i_{k}}}=R_{i_{1}}R_{i_{2}}X_{i_{3}}^{n_{i_{3}}}\cdots
X_{i_{k}}^{n_{i_{k}}},$

with
$R_{i_{1}}(P_{i_{2}}F_{i_{2}})X_{i_{3}}^{n_{i_{3}}}\cdots\,X_{i_{k}}^{n_{i_{k}}}\boldsymbol{e}_{i}\in
L$. Continue this process until $i_{d}$, we obtain
$m=p^{\prime}+p^{\prime\prime}$ where

$p^{\prime}=R_{i_{1}}\cdots R_{i_{d}}X_{i_{d+1}}^{n_{i_{d+1}}}\cdots
X_{i_{k}}^{n_{i_{k}}},$

and

$p^{\prime\prime}=(P_{i_{1}}F_{i_{1}})X_{i_{2}}^{n_{i_{2}}}\cdots
X_{i_{k}}^{n_{i_{k}}}+R_{i_{1}}(P_{i_{2}}F_{i_{2}})X_{i_{3}}^{n_{i_{3}}}\cdots\,X_{i_{k}}^{n_{i_{k}}}+\\\
\cdots+R_{i_{1}}\cdots
R_{i_{d-1}}(P_{i_{d}}F_{i_{d}})X_{i_{d+1}}^{n_{i_{d+1}}}\cdots
X_{i_{k}}^{n_{i_{k}}}.$

Clearly, every monomials of $p^{\prime}$ is in the set $\mathcal{S}$, and
$p^{\prime\prime}\boldsymbol{e}_{i}\in L$.

Decompose every monomial of every $f_{i},i=1,\ldots,n$. In this way,
$\boldsymbol{f}$ can be written as
$\boldsymbol{f}=\boldsymbol{f}^{\prime}+\boldsymbol{f}^{\prime\prime}$ with
$\boldsymbol{f}^{\prime\prime}\in L$ and $\boldsymbol{f}^{\prime}$ generated
by the set $\mathcal{R}$ (note that every monomial of
$\boldsymbol{f}^{\prime}$ is in the set $\mathcal{S}$ and
$\boldsymbol{f}^{\prime}\in\mathcal{M}$).

We have thus found the finite basis $\mathcal{R}\cup\mathcal{F}$ for
$\mathcal{M}$ as a $\mathbb{A}$-module. Note that the procedure described in
the proof is effective: the computation of the characteristic polynomials
$F_{1},\ldots,F_{k}$ can be done by computing the determinants
$\det(A_{i}-XI),i=1,\ldots,k$, and the computation of $\ker(\lambda)$ is
simply linear algebra.

∎

Note that since the entries of the matrices $A_{1},\ldots,A_{k}$ and the
vectors $\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{n}$ are all rationals, the
computation given in Proposition 3 can be done over the rational. Hence, we
can suppose the computed basis of $\mathcal{M}$ has rational coefficients.

##  6\. Positive polynomial membership

In this section we prove Proposition 4. Recall
$\mathbb{A}^{++}\coloneqq\mathbb{A}^{+}\setminus\\{0\\}$. Let
$\mathbb{B}\coloneqq\mathbb{R}[X_{1}^{\pm 1},\ldots,X_{k}^{\pm 1}]$ be the
Laurent polynomial ring over $k$ variables, and
$\mathbb{B}^{+}\coloneqq\mathbb{R}_{\geq 0}[X_{1}^{\pm 1},\ldots,X_{k}^{\pm
1}]$ be the sub-semiring of Laurent polynomials with non-negative
coefficients. Define $\mathbb{B}^{++}\coloneqq\mathbb{B}^{+}\setminus\\{0\\}$.

The first step to proving Proposition 4 is a quick reduction from
$\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}$ to
$\left(\mathbb{A}^{++}\right)^{n}$.

###### Lemma 6.

Given an $\mathbb{A}$-submodule $\mathcal{M}$ of $\mathbb{A}^{n}$ and a non-
empty subset $I\subset\\{1,\ldots,n\\}$, define the following
$\mathbb{A}$-submodule of $\mathbb{A}^{I}$:

$\mathcal{M}_{I}\coloneqq\left\\{(f_{i})_{i\in I}\;\middle|\;\sum_{i\in
I}f_{i}\boldsymbol{e}_{i}\in\mathcal{M}\right\\}\subset\mathbb{A}^{I}.$

Then $\mathcal{M}$ contains an element in
$\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}$ if and only if there
exists some non-empty set $I\subset\\{1,\ldots,n\\}$ such that
$\mathcal{M}_{I}\cap\left(\mathbb{A}^{++}\right)^{I}\neq\emptyset$.

###### Proof.

If $\mathcal{M}$ contains an element
$\boldsymbol{f}=\sum_{i=1}^{n}f_{i}\boldsymbol{e}_{i}\in\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}$.
Let $I$ be the set $\\{i\mid f_{i}\neq 0\\}$. Then $(f_{i})_{i\in
I}\in\mathcal{M}_{I}\cap\left(\mathbb{A}^{++}\right)^{I}\neq\emptyset$.

If there exists non-empty $I\subset\\{1,\ldots,n\\}$ such that
$\mathcal{M}_{I}\cap\left(\mathbb{A}^{++}\right)^{I}\neq\emptyset$. Let
$(f_{i})_{i\in I}\in\mathcal{M}_{I}\cap\left(\mathbb{A}^{++}\right)^{I}$, then
$\sum_{i=1}^{n}f_{i}\boldsymbol{e}_{i}\in\mathcal{M}\cap\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}\neq\emptyset$.
∎

Given a finite basis for the $\mathbb{A}$-submodule $\mathcal{M}$ of
$\mathbb{A}^{n}$, it is easy to compute $\mathcal{M}_{I}$ for any
$I\subset\\{1,\ldots,n\\}$ using linear algebra over $\mathbb{A}$
(bareiss1968sylvester, ). Therefore it suffices to devise a procedure that
decide whether $\mathcal{M}\cap\left(\mathbb{A}^{++}\right)^{n}\neq\emptyset$
for a given $\mathcal{M}$. This procedure can then be used to decide whether
$\mathcal{M}\cap\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}\neq\emptyset$
by verifying whether there exists non-empty $I\subset\\{1,\ldots,n\\}$ such
that $\mathcal{M}_{I}\cap\left(\mathbb{A}^{++}\right)^{I}\neq\emptyset$.

###### Lemma 7.

Let
$\mathcal{M}=\boldsymbol{g}_{1}\mathbb{A}+\cdots+\boldsymbol{g}_{m}\mathbb{A}$
be an $\mathbb{A}$-submodule of $\mathbb{A}^{n}$. Define
$\mathcal{M}_{\mathbb{B}}\coloneqq\boldsymbol{g}_{1}\mathbb{B}+\cdots+\boldsymbol{g}_{m}\mathbb{B}$;
it is a $\mathbb{B}$-submodule of $\mathbb{B}^{n}$. Then
$\mathcal{M}\cap\left(\mathbb{A}^{++}\right)^{n}\neq\emptyset$ if and only if
$\mathcal{M}_{\mathbb{B}}\cap\left(\mathbb{B}^{++}\right)^{n}\neq\emptyset$.

###### Proof.

Obviously $\mathcal{M}\subset\mathcal{M}_{\mathbb{B}}$ and
$\mathbb{A}^{++}\subset\mathbb{B}^{++}$, so
$\mathcal{M}\cap\left(\mathbb{A}^{++}\right)^{n}\neq\emptyset\implies\mathcal{M}_{\mathbb{B}}\cap\left(\mathbb{B}^{++}\right)^{n}\neq\emptyset$.

For the other direction, suppose
$\mathcal{M}_{\mathbb{B}}\cap\left(\mathbb{B}^{++}\right)^{n}\neq\emptyset$.
Let
$\boldsymbol{f}=\sum_{i=1}^{m}h_{i}\boldsymbol{g}_{i}\in\left(\mathbb{B}^{++}\right)^{n}$.
Then there exists $n_{1},\ldots,n_{k}\in\mathbb{N}$ such that
$X_{1}^{n_{1}}\cdots X_{k}^{n_{k}}h_{i}\in\mathbb{A}$ for all $1\leq i\leq m$.
So

$X_{1}^{n_{1}}\cdots
X_{k}^{n_{k}}\boldsymbol{f}=\sum_{i=1}^{m}X_{1}^{n_{1}}\cdots
X_{k}^{n_{k}}h_{i}\boldsymbol{g}_{i}\in\mathcal{M}\cap\left(\mathbb{A}^{++}\right)^{n}.$

∎

By Lemma 7, it suffices to consider finitely generated $\mathbb{B}$-submodules
of $\mathbb{B}^{n}$. The key ingredient of our proof is the following
consequence of a deep result by Einsiedler, Mouat, and Tuncel
(einsiedler2003does, ).

###### Lemma 8 (Corollary of (einsiedler2003does, , Procedure 6.3)).

Suppose a finite basis of a submodule $\mathcal{M}_{\mathbb{B}}$ of
$\mathbb{B}^{n}$ is given. One can decide whether
$\mathcal{M}_{\mathbb{B}}\cap\left(\mathbb{B}^{++}\right)^{n}\neq\emptyset$,
provided an effective procedure for the following problem:

  * •

(ExistPos): Given a rectangular set
$K\coloneqq[p,q]^{d}\subset\mathbb{R}_{>0}^{d}$, decide if for all
$\boldsymbol{a}\in K$ there exists
$\boldsymbol{f}=(f_{1},\dots,f_{n})\in\mathcal{M}_{\mathbb{B}}$ such that
$\boldsymbol{f}(\boldsymbol{a})\coloneqq\left(f_{1}(\boldsymbol{a}),\ldots,f_{n}(\boldsymbol{a})\right)\in\mathbb{R}_{>0}^{n}$.

Furthermore, we can find an element of
$\mathcal{M}_{\mathbb{B}}\cap\left(\mathbb{B}^{++}\right)^{n}$ with rational
coefficients if the set is non-empty.

###### Proof.

Consider the result of Einsiedler, Mouat, and Tuncel (einsiedler2003does, ,
Procedure 6.3). By the remark following Procedure 6.3, this procedure becomes
effective if (einsiedler2003does, , Condition 1.3(a)) can be checked
algorithmically for the compact set $K$ defined in (einsiedler2003does, ,
Lemma 5.3).222The second question mentioned in the remark (whether there is a
computable bound on $\ell$ in the procedure?) does not hinder decidability
since the existence of $\ell$ is guaranteed, according to the remark.
Therefore, it suffices to provide an effective procedure that checks
(einsiedler2003does, , Condition 1.3(a)) for the compact set $K$. By the proof
of (einsiedler2003does, , Lemma 5.3), one can even suppose $K$ to be of the
form $[p,q]^{d}\subset\mathbb{R}_{>0}^{d}$. Then (einsiedler2003does, ,
Condition 1.3(a)) is equivalent to the problem ExistPos. ∎

###### Lemma 9.

Fix an $\boldsymbol{a}\in\mathbb{R}_{>0}^{k}$ and let
$\mathcal{M}_{\mathbb{B}}=\boldsymbol{g}_{1}\mathbb{B}+\cdots+\boldsymbol{g}_{m}\mathbb{B}$.
Then the two following conditions are equivalent:

  1. (i)

There exists $\boldsymbol{f}=(f_{1},\dots,f_{n})\in\mathcal{M}_{\mathbb{B}}$
such that $\boldsymbol{f}(\boldsymbol{a})\in\mathbb{R}_{>0}^{n}$.

  2. (ii)

There exists reals $r_{1},\ldots,r_{m}\in\mathbb{R}$ such that
$\sum_{i=1}^{m}r_{i}\boldsymbol{g}_{i}(\boldsymbol{a})\in\mathbb{R}_{>0}^{n}$.

###### Proof.

(i) $\implies$ (ii). Let $\boldsymbol{f}\in\mathcal{M}_{\mathbb{B}}$ such that
$\boldsymbol{f}(\boldsymbol{a})\in\mathbb{R}_{>0}^{n}$. Suppose
$\boldsymbol{f}=\sum_{j=1}^{m}h_{j}\boldsymbol{g}_{j}$ for some
$h_{1},\ldots,h_{m}\in\mathbb{B}$, then we have
$\boldsymbol{f}(\boldsymbol{a})=\sum_{j=1}^{m}h_{j}(\boldsymbol{a})\boldsymbol{g}_{j}(\boldsymbol{a})$.
Taking $r_{1}\coloneqq h_{1}(\boldsymbol{a}),\ldots,r_{m}\coloneqq
h_{m}(\boldsymbol{a})$ yields (ii).

(ii) $\implies$ (i). Let $r_{1},\ldots,r_{m}\in\mathbb{R}$ be reals such that
$\sum_{i=1}^{m}r_{i}\boldsymbol{g}_{i}(\boldsymbol{a})\in\mathbb{R}_{>0}^{n}$.
Taking
$\boldsymbol{f}\coloneqq\sum_{i=1}^{m}r_{i}\boldsymbol{g}_{i}\in\mathcal{M}$
yields (i). ∎

###### Proposition 10.

Suppose a finite basis of a submodule $\mathcal{M}$ of $\mathbb{A}^{n}$ is
given. One can decide whether
$\mathcal{M}\cap\left(\mathbb{A}^{++}\right)^{n}\neq\emptyset$.

###### Proof.

By Lemma 7, it suffices to decide whether
$\mathcal{M}_{\mathbb{B}}\cap\left(\mathbb{B}^{++}\right)^{n}\neq\emptyset$.
By Lemma 8, it suffices to give a decision procedure for the problem ExistPos.
By Lemma 9, ExistPos has a positive answer if and only if the following
statement in the first order theory of reals is true:

$\displaystyle\forall a_{1}\cdots\forall a_{d}\exists r_{1}\cdots\exists
r_{m},$ (11) $\displaystyle\bigg{(}a_{1}\in[p,q]\land\cdots\land
a_{d}\in[p,q]\bigg{)}\implies\sum_{i=1}^{m}r_{i}\boldsymbol{g}_{i}(a_{1},\ldots,a_{d})\in\mathbb{R}_{>0}^{n}.$

The truth of such statements is decidable by Tarski’s theorem (Tarski1949, ).
∎

Combining Lemma 6 and Proposition 10 immediately yields Proposition 4.

See 4

###### Proof.

By Lemma 6, $\mathcal{M}$ contains an element of
$\left(\mathbb{A}^{+}\right)^{n}\setminus\\{0^{n}\\}$ if and only if there
exists a non-empty set $I\subset\\{1,\ldots,n\\}$ such that
$\mathcal{M}_{I}\cap\left(\mathbb{A}^{++}\right)^{I}\neq\emptyset$. Therefore,
it suffices to enumerate all non-empty sets $I\subset\\{1,\ldots,n\\}$,
compute a basis for $\mathcal{M}_{I}$, and use Proposition 10 (with
$n\coloneqq\operatorname{card}(I)$) to check whether
$\mathcal{M}_{I}\cap\left(\mathbb{A}^{++}\right)^{I}\neq\emptyset$. ∎

##  7\. Conclusion and future work

In this paper we proved decidability of termination of linear loops under
commutative updates, where the guard condition is a polyhedral cone. A natural
continuation of our work would be to generalize Theorem 5 to the case where
$\mathcal{C}$ is a polyhedron (instead of a polyhedral cone). Unfortunately,
the duality argument that is crucial in our proof stops working when we remove
the homogeneity of the guard conditions. New techniques, possibly combining
geometric and algebraic arguments, might be needed to overcome this
difficulty. Another possible generalization is the removal of the
commutativity assumption on the update matrices. For this, one would need a
generalization of Einsiedler, Mouat, and Tuncel’s result to left-modules over
non-commutative polynomials rings, which would have deep consequences in the
field of real algebra.

## References

  * (1) László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, and Eugene M. Luks.  Multiplicative equations over commuting matrices.  In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 498–507, 1996.
  * (2) Erwin H. Bareiss.  Sylvester’s identity and multistep integer-preserving gaussian elimination.  Mathematics of computation, 22(103):565–578, 1968.
  * (3) Amir M Ben-Amram, Jesús J Doménech, and Samir Genaim.  Multiphase-linear ranking functions and their relation to recurrent sets.  In International Static Analysis Symposium, pages 459–480. Springer, 2019.
  * (4) Amir M. Ben-Amram and Samir Genaim.  Ranking functions for linear-constraint loops.  Journal of the ACM (JACM), 61(4):1–55, 2014.
  * (5) Stephen Boyd and Lieven Vandenberghe.  Convex Optimization.  Cambridge University Press, 2004.
  * (6) Mark Braverman.  Termination of integer linear programs.  In International conference on computer aided verification, pages 372–385. Springer, 2006.
  * (7) Manfred Einsiedler, Robert Mouat, and Selim Tuncel.  When does a submodule of $\left(\mathbb{R}[x_{1},\ldots,x_{k}]\right)^{n}$ contain a positive element?  Monatshefte für Mathematik, 140(4):267–283, 2003.
  * (8) Mehran Hosseini, Joël Ouaknine, and James Worrell.  Termination of linear loops over the integers.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 118:1–118:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ICALP.2019.118.
  * (9) Ehud Hrushovski, Joël Ouaknine, Amaury Pouly, and James Worrell.  Polynomial invariants for affine programs.  In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 530–539, 2018.
  * (10) Bertrand Jeannet, Peter Schrammel, and Sriram Sankaranarayanan.  Abstract acceleration of general linear loops.  In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 529–540, 2014.
  * (11) Zachary Kincaid, Jason Breck, John Cyphert, and Thomas Reps.  Closed forms for numerical loops.  Proceedings of the ACM on Programming Languages, 3(POPL):1–29, 2019\.
  * (12) Engel Lefaucheux, Joël Ouaknine, David Purser, and James Worrell.  Porous invariants.  In International Conference on Computer Aided Verification, pages 172–194. Springer, 2021.
  * (13) Joël Ouaknine, Amaury Pouly, João Sousa-Pinto, and James Worrell.  On the decidability of membership in matrix-exponential semigroups.  Journal of the ACM (JACM), 66(3):1–24, 2019.
  * (14) Joël Ouaknine and James Worrell.  Positivity problems for low-order linear recurrence sequences.  In Proceedings of the twenty-fifth annual ACM-SIAM Symposium on Discrete Algorithms, pages 366–379. SIAM, 2014.
  * (15) Alfred Tarski.  A Decision Method for Elementary Algebra and Geometry.  second ed., rev., Univ. of California Press, Berkeley, 1951.
  * (16) Ashish Tiwari.  Termination of linear programs.  In International Conference on Computer Aided Verification, pages 70–82. Springer, 2004.


# Linking ImageNet WordNet Synsets with Wikidata

Finn Årup Nielsen  Technical University of DenmarkDTU ComputeRichard Petersens
Plads2800Kongens LyngbyDenmark<EMAIL_ADDRESS>
###### Abstract.

The linkage of ImageNet WordNet synsets to Wikidata items will leverage deep
learning algorithm with access to a rich multilingual knowledge graph. Here I
will describe our on-going efforts in linking the two resources and issues
faced in matching the Wikidata and WordNet knowledge graphs. I show an example
on how the linkage can be used in a deep learning setting with real-time image
classification and labeling in a non-English language and discuss what
opportunities lies ahead.

Wikidata; ImageNet; WordNet; ontology alignment; machine learning

I would like to thank Laura Rieger and Lars Kai Hansen for discussions. This
research was supported by Innovation Fund Denmark through the DABAI project.

††copyright: iw3c2w3††conference: The 2018 Web Conference Companion; April
23–27, 2018; Lyon, France††journalyear: 2018††price: ††doi:
10.1145/XXXXXX.XXXXXX††isbn: 978-1-4503-5640-4/18/04.

##  1\. Introduction

Machine learning with deep neural networks has in recent years yielded
interesting advances with a range of tasks. Particularly image classification
models have seen advances with the first system claiming “superhuman visual
pattern recognition” in a restricted and controlled setting back in 2011
(Q34451415, ). More recent trends have explored how knowledge bases can be
utilized together with machine learning. For instance, a combined word
embedding of the ConceptNet knowledge graph and the two popular word
embeddings, word2vec and GloVe, could produce state-of-the-art results on word
similarity tests (Q31895639, ), while the Wembedder system uses an embedding
of the Wikidata knowledge graph in a web application with recommender system
features (Q41799598, ).

To take advantage of knowledge graphs in machine learning we should deep-link
systems, and preferably not just on the word-level but on a semantic level
where the different senses of polysemic words are distinguished. One
opportunity is a linkage between ImageNet through Wordnet to Wikidata. Below I
will describe these three resources and follow with a detailed account of
issues around on-going work on matching the items across these resources. I
will show statistics and describe a small machine learning application that
uses the linkage between ImageNet and Wikidata, and lastly discuss issues
concerning the matching and the opportunities for extending Wikidata.

##  2\. WordNet, ImageNet and Wikidata

###  2.1. WordNet

WordNet is a machine readable lexical resource that describe words. Words that
are synonyms are grouped into items called _synsets_ (Q36655252, ). Each
WordNet synset is associated with an Semantic Web Linked Open Data (LOD) URI.
URIs for WordNet for version 3.0 has been prefixed with http://wordnet-
rdf.princeton.edu/wn30/ while URIs for version 3.1 synsets are prefixed with
http://wordnet-rdf.princeton.edu/wn31/. The canonical prefix has been change
recently, so the part `wn30` has been changed to `pwn30`.111See the discussion
on the WN-USER mailing list at https://lists.princeton.edu/cgi-
bin/wa?A2=ind1801&L=wn-users&F=&S=&P=1719. The old URIs are redirected.

###  2.2. ImageNet

ImageNet (Q37043902, ) is a large collection of images, labeled against
WordNet 3.0 and described at http://image-net.org/. According to January
statistics, ImageNet contains 14,197,122 images and 21,841 indexed synsets.
There are various labeling schemes. The object attributes scheme labels 400
synsets across 25 attributes. The attributes are with respect to color,
pattern, shape and texture.222http://image-net.org/download-attributes
ImageNet Large Scale Visual Recognition Challenge ILSVRC (Q47451393, ) is an
image recognition challenge that started in 2010 and has been repeated for
several years. It has had several tasks: image classification, single-object
locatization or object detection. For the image classification task a subset
with 1,000 object categories from ImageNet was selected corresponding to 1,000
WordNet synsets. ILSVRC synsets have changed through the years so only 639
have been used in all the years.

Inspired by the demonstration of the so-called AlexNet (Q30077834, ) where
state-of-the-art image classification results were reported on the ILSVRC
dataset, many publications describe the usage of the ILSVRC data for training
deep learning image classification models. Researchers distribute pre-trained
deep learning models based on the ILSVRC data. One such model is Resnet-50
described by (Q35464016, ). High-level deep learning Python frameworks, Keras
and Caffe, are able to read this model in a few lines of code. For instance,
with Keras the pre-trained Resnet-50 model is set up with `model =
ResNet50()`.333https://keras.io/applications/#resnet50 The Keras
implementation will also convert the output of the trained model from its
index-based value to the WordNet synset identifier.

In ImageNet the synset identifier is represented with the word class as a
prefix, e.g., the synset identifier for banana is n07753592. So a (trivial)
conversion is necessary to match the LOD URIs which in the banana case would
be http://wordnet-rdf.princeton.edu/wn30/07753592-n, while a preview of
corresponding ImageNet images is available as http://image-
net.org/explore.php?wnid=n07753592.

###  2.3. Wikidata

The collaborative knowledge graph, Wikidata, at https://www.wikidata.org
(Q18507561, ) has over 40 million items (with the identifier prefixed with
“Q”), that each may be described by several thousand properties (prefixed with
“P”). Wikidata properties with the data type “External identifier” is often
suggested as a means to deep linking external databases. Such a method could
also be applied for WordNet synset identifiers. This requires a property
suggestion and some deliberation among the Wikidata editor before the external
identifier property is made available for use.444I suggested such a property,
see
https://www.wikidata.org/wiki/Wikidata:Property_proposal/Wordnet_synset_ID.
There is another way to link Wikidata with WordNet. Wikidata has a property to
link to LOD URIs: the “exact match” property (P2888), corresponding to
skos:exactMatch. This method can be used to link a Wikidata item to its
associated WordNet synset, e.g., _mashed potato_ (Q322787) is linked via the
P2888 property to http://wordnet-rdf.princeton.edu/wn30/07711569-n.

Wikidata links to another lexical resource: The multilingual
BabelNet555http://babelnet.org/. is linked via its own external identifier
property, the P2581666https://www.wikidata.org/wiki/Property:P2581. which
currently is used 59.105 times.777Wikidata Query Service can be queried with
“SELECT (COUNT(*) AS ?count) WHERE { [] wdt:P2581 [] }”, see
http://tinyurl.com/y8pk2cqa.  While WordNet is one of the resources that uses
BabelNet (Q47485515, ), the identifier is different. For instance, “quill pen”
is 00065709n in BabelNet and 04033901-n in WordNet 3.0.

Once WordNet 3.0 URIs have been entered into Wikidata, we can obtain the
inverse mapping from the WordNet URI to the Wikidata item with the Wikidata
Query Service (WDQS) SPARQL engine, e.g., the SPARQL query “SELECT * WHERE {
?item wdt:P2888
<http://wordnet-rdf.princeton.edu/wn30/04033901-n> }” will identify Q4063215
as the Wikidata item corresponding to the WordNet concept “quill”.

One advantage with Wikidata is its multilingual nature: Once we have linked a
WordNet synset to a Wikidata item we can record labels in multiple languages,
and in many cases the labels are already present. For instance, “quill pen” is
currently labeled for 33 languages. The corresponding number for BabelNet is
12. It is important to note though that the multilinguality in Wikidata is
certainly not complete and biased towards the major European languages
(Q37859976, ).

Wikidata and WordNet have been defined mostly independent of each other. There
are other linked semantic resources where this is also the case. Examples are
some of the wordnets inspired by the original English (Princeton) WordNet
(Q37052366, ).

ImageNet |  WordNet |  Wikidata
---|---|---
n07930864: Mostly (coffee) cups, i.e., “a small open container usually used for drinking; usually has a handle”, but also a few champagne glasses. |  _Cup_ ; “A punch served in a pitcher instead of a punch bowl”, — the 6th sense of _cup_. |  ? Q1121224 is an item for the parent synset (punch). There seems to be none for the punch cup synset.
n07565083: Printed cards with information about dishes served. |  _Menu_ : “The dishes making up a meal”. |  ? ImageNet-consistency could link to Q658274. There does not seem to be an item corresponding to the WordNet sense.
n03742115: Image of bathroom cabinets. |  _Medicine chest_ , medicine cabinet; “Cabinet that holds medicines and toiletries” |  Rather than medicine chest, the WordNet synset corresponds to bathroom cabinet (Q4869069)
n03832673: Images linked directly to n03832673 show computer notebooks, but the _planner_ child synset shows paper notebooks. |  _Notebook_ is a notebook computer, but the WordNet hierarchy displayed on the ImageNet homepage shows _planner_ n03956785 as a hyponym and this synset is described as “A notebook for recording appointments and things to be done, etc.” There is a separate item for _laptop_. |  ? The closest Wikidata item may be Q3962 with _laptop_ as the current English label. There does not seem to be an individual item for computer notebook.
n04152593: Cathode-ray tube (CRT) screens as well as some flatscreens. Often the full apparatus, — not just the display. Mostly computer screens. |  _Screen_ , CRT screen: “The display that is electronically created on the surface of the large end of a cathode-ray tube”. |  ? Q5290 is computer monitor or screen, and not necessarily CRT-based. Q1736293 is cathode ray tube screen fitting WordNet but less so ImageNet.
n04355933: Mostly (all?) protective eyewear. |  _Sunglass_ ; “A convex lens that focuses the rays of the sun; used to start a fire” |  ? Q368027 is “burning glass” corresponding to the WordNet sense, but quite different from the examples in ImageNet.
n03944341: Toy pinwheels |  _Pinwheel_ ; “A wheel that has numerous pins that are set at right angles to its rim”. There is another WordNet synset for the toy: n03944138 also called “pinwheel wind collector”. |  ? Pinwheel is a disambiguation page in English Wikipedia, while “Pinwheel (toy)” corresponds to ImageNet usage and n03944138.
Table 1. Matching between ImageNet, WordNet and Wikidata. Some examples of the
difficulties with aligning the resources.

##  3\. Matching Wikidata with ImageNet

For matching Wikidata with ImageNet, I focused on the ILSVRC-part of ImageNet
synsets linking them up with the P2888 property and the `http://wordnet-
rdf.princeton.edu/wn30/` prefix by examining Wikidata definitions, WordNet
synsets descriptions, ImageNet images linked to the WordNet synsets and
sometimes the description in Wikipedia articles associated with Wikidata
items. Matching Wikidata with ImageNet is for some concepts straightforward.
For instance, many taxons can readily be matched. At other times the matching
requires some thought. Table 1 shows examples where a match is particular
difficult. Below I attempt a classification of various matching problems faced
during manual linking of Wikidata items to WordNet synsets.

An ILSVRC synset is missing from Wikidata. In most of these cases, it is easy
to create new Wikidata items and link them to WordNet. Examples where I could
not find matching items and created new items are _soup bowl_ and _bath
towel_.

The matching Wikidata item is a Wikipedia disambiguation page: An example is
car mirror where the English Wikipedia page “Car mirror” currently is a
disambiguation page linking to two real articles “Rear-view mirror” and “Wing
mirror”. A solution to such a problem would be to either create a new Wikidata
item for car mirror or change the definition of “Car mirror” in both Wikidata
and the English Wikipedia. “Armchair is a disambiguation page in the English
Wikipedia, but another item link armchair in Wikidata (Q25503439). _Mixing
bowl_ is another example where the Wikidata item is describing a
disambiguation page.

There is a discrepancy between ImageNet and WordNet: For instance, _sunglass_
(http://wordnet-rdf.princeton.edu/wn30/04355933-n) is described as a “a convex
lens that focuses the rays of the sun; used to start a fire”. However, the
associated ImageNet images are better described with the http://wordnet-
rdf.princeton.edu/wn31/104296228-n synset (dark glasses, shades, sunglasses)
described with “spectacles that are darkened or polarized to protect the eyes
from the glare of the sun”. This issue was previously noted by Tom White on
Twitter in September 2017.888Tom White (@dribnet). aha: “sunglass” is “burning
glass”, …https://twitter.com/dribnet/status/904133638257655808 (3 September
2017). In the same context he also reported differences between the _sunglass_
and the _sunglasses_ images. A similar confusion occurs for _maillot_ , where
Wordnet has two synsets: “a woman’s one-piece bathing suit” and “tights for
dancers or gymnasts”. For the latter synset, ImageNet displays images for one-
piece bathing suits. Another example is _monitor_ described as “Electronic
equipment that is used to check the quality or content of electronic
transmissions”. At ImageNet’s n03782006, the images shown are broader with
many displaying computer monitors, — in Wikidata it would correspond to
approximately the more general concept Q6021804 (“electronic visual display”).
Related to the _monitor_ issue is _screen_ with the alias _CRT screen_ and
description “The display that is electronically created on the surface of the
large end of a cathode-ray tube”. The associated ImageNet images show many
screens that are not CRT-based, but flat panel displays. One interesting
discrepancy is for _spider web_ : WordNet has two synsets for that word: “a
web spun by spiders to trap insect prey” and “a web resembling the webs spun
by spiders” where the latter is regarded as an artifact and the former is not
found in ImageNet. ImageNet images labeled with the latter sense (n04275548)
show real natural spider webs. It is obvious that webs spun by spiders
resemble webs spun by spiders, but in this case the webs spun by spiders
should probably not be assigned to the WordNet synset. Table 1 shows other
examples of this problem, e.g., for _cup_ (coffee cup or punch), _menu_
(printed list or a set of servings), _notebook_ (computer or paper book for
notes) and _pinwheel_. Not shown in the table is _picture rail_ (“rail fixed
to a wall for hanging pictures”) and its parent _rail_ (“a horizontal bar
(usually of wood or metal)”). For both these synsets ImageNet associates
images of railways and trains. These cases may involve concepts with a large
semantic difference. There are likely more discrepancies.

There are some difference between the WordNet and the Wikidata concepts with
similar names. For instance, WordNet defines _street sign_ as “a sign visible
from the street” while Wikidata describes the same English word as a “type of
traffic sign used to identify named roads” (Q1969455). The Wikidata item for
traffic sign (Q170285) is described as a “symbol for people out in traffic”
corresponding better to the _street sign_ of WordNet. Another example is “tea
chest” that in the English Wikipedia (the only Wikipedia describing the
concept) is explained as a case “approximate size 500x500x750 millimeters”
with metal edges. Wikidata links this concept to the identifier 300039143 of
the _Art & Architecture Thesaurus_ where it is explained as “Square wooden
cases usually fixed with sheet lead or tin and used for exporting tea.” The
English Wikipedia further extends the concept with “The term is now used more
widely to indicate similarly-sized cases, including cardboard cases, produced
for various home and commercial uses.” In ImageNet _tea chest_ (n04397168) are
cases with tea of varying sizes corresponding well to the WordNet’s general
description: “Chest for storing or transporting tea”. Here we have an example
of the English Wikipedia describing two concepts in the same article, a
specific and a general, where the general topic correspond to WordNet and
ImageNet concepts.

There are a number of other cases where the matching requires an effort to
resolve. These may involve multiple semantically similar items in WordNet and
Wikidata: For instance, there are multiple synsets for _radiator_. The
_radiator_ synsets in ILSVRC (n04040759) is described as “A mechanism
consisting of a metal honeycomb through which hot fluids circulate; heat is
transferred from the fluid through the honeycomb to the airstream that is
created either by the motion of the vehicle or by a fan”. Most of the ImageNet
images associated with this synset fit the description of another synset
described as a “heater consisting of a series of pipes for circulating steam
or hot water to heat rooms or buildings”. In Wikidata there are 3 or 4 items
close in semantics to _radiator_. WordNet distinguishes between _tape player_
, (n04392985) and _tape recorder_ (n04393095). In Wikidata there is only one
item. Wikidata has multiple items for infant bed (infant bed, bassinet), the
media archive Wikimedia Commons distinguishes between baby beds, bassinets,
cradles and cribs among others. ImageNet WordNet has two bassinet synsets, one
cradle, one _carrycot_ and one _crib_ , with four of them grouped under _baby
bed_. ImageNet WordNet has two main _mask_ synsets and Wikidata has also two
items with the main label “mask”. They differ slightly in semantics and for
the n03725035 synset described as “A protective covering worn over the face”,
ImageNet associates images that are not necessarily protective coverings.
ImageNet Wordnet has _cassette_ and _cassette tape_ synsets that are difficult
to dissociate from their description (“a container that holds a magnetic tape
used for recording or playing sound or video” vs. “a cassette that contains
magnetic tape”). One is grouped under _container_ and the other under _memory
device_. Wikidata’s cassette corresponds more to the _audiocassette_ of
ImageNet WordNet.

##  4\. Statistics

With a SPARQL query in WDQS, we can count the number of WordNet 3.0 synsets
linked from Wikidata:

⬇

SELECT

(COUNT(*) AS ?count)

WHERE {

?item wdt:P2888 ?uri .

FILTER STRSTARTS(STR(?uri),

"http://wordnet-rdf.princeton.edu/wn30/")

}

The response currently yields 324, i.e., approximately a third of the total
number of ILSVRC synsets. A query for items that links to both WordNet 3.0 and
BabelNet (with the P2581 property) yields 105 Wikidata items.

Wikidata items with links to WordNet synsets may have quite few properties
describing the items. For instance, the only properties describing _oxygen
mask_ (Q1890958) is currently the exact match (P2888), the Wikimedia Commons
category property (P373) and 3 external identifiers for Freebase, Quora and
JSTOR. For _loupe_ (Q4165197) there is only one property beyond the exact
match property.

We can count the number of statements (i.e., the number of property values)
for each Wikidata item with the follow WDSQ SPARQL query:

⬇

SELECT

?item

(COUNT(?property) AS ?count)

WHERE {

?item wdt:P2888 ?uri .

FILTER STRSTARTS(STR(?uri),

"http://wordnet-rdf.princeton.edu/wn30/")

?item ?property [] .

FILTER STRSTARTS(STR(?property),

"http://www.wikidata.org/prop/direct/")

}

GROUP BY ?item

ORDER BY ?count

The sorted list shows that the WordNet 3.0-linked Wikidata items with the most
statements are typically various taxons: _Dog_ , _bald eagle_ and _goldfish_
each has over 100 statements. On the other hand, inanimate objects like
_bathroom cabinet_ , _loupe_ , _cradle_ and _cathode ray tube screen_ as well
as newly created _pill bottle_ and _bath towel_ have three or less statements,
— including the statement(s) linking to WordNet.

Figure 1. Plot from the Wikidata Query Service displaying the frequency of the
number statements in each Wikidata item that is linked to WordNet 3.0.

We can get an overview of the counts by plotting the statement counts with the
following SPARQL, producing a histogram-like plot:

⬇

SELECT

?count (COUNT(?item) AS ?frequency)

WHERE {

SELECT

?item

(COUNT(?property) AS ?count)

WHERE {

?item wdt:P2888 ?uri .

FILTER STRSTARTS(STR(?uri),

"http://wordnet-rdf.princeton.edu/wn30/")

?item ?property [] .

FILTER STRSTARTS(STR(?property),

"http://www.wikidata.org/prop/direct/")

}

GROUP BY ?item

}

GROUP BY ?count

Figure 1 shows the scatter plot output from WDQS. The most frequent number of
statements are 9. Examples on Wikidata items with this number of statements
are _filing cabinet_ , _Miniature Pinscher_ (a dog bred), _table lamp_ and
_cowboy hat_

##  5\. Example application

(a) “Coffee mug”

(b) “Washing machine”

Figure 2. Two screenshots of an application using the Keras Resnet-50 model
for image classification of camera images with labels translated to Danish via
Wikidata. A coffee mug is in front of a tape recorder on a desk. In one case
the label reads “kaffekrus” (coffee mug), in the other case—a less successful
classification—it reads “vaskemaskine” (washing machine).

I created an example application that would use Wikidata in an image
classification setting. The application was implemented in Python using the
Keras deep learning framework with a TensorFlow backend. Images were captured
real-time from a USB camera with OpenCV. For ImageNet-based image
classification, I used the Resnet-50 pre-trained neural network in the form of
the `ResNet50` Keras implementation. Before the camera images were feed to the
neural model, they were cropped and preprocessed with the `ResNet50`
preprocessing method following the example code provided by François Chollet
at https://github.com/fchollet/deep-learning-models. The index-based output of
the neural network was converted to the associated WordNet synset identifier
with the decoder provided by Keras. Only the index associated with the highest
probability in prediction was used. This identifier was used for a least-
recently-used cached lookup in WDQS to identify the corresponding Wikidata
item. The Danish label from Wikidata was overlayed on the camera image and the
resulting image displayed on the computer screen via an OpenCV function. The
font size was dynamically adjusted to indicate the probability of the
classification. Figure 2 shows screenshots of the running application.

Running on a desktop computer with an NVIDIA Quadro K620, the update rate with
camera capture, preprocessing, neural computation and display would take
around 80 milliseconds for TensorFlow running on the GPU, while around 180
milliseconds if only the CPU was used. If the query returning the label was
not cached, then the update would take a few hundred milliseconds extra while
querying WDQS.

##  6\. Discussion

I have pointed to several cases of discrepancies between WordNet and
associated ImageNet images. This is a problem if the hierarchy of WordNet or
Wikidata is used for semantic background knowledge in an image classification
setting. Given that ImageNet is used for benchmarking it may be less
optimistic to think that the annotation will be changed in ImageNet. How can
Wikidata record that certain WordNet synsets are not well represented in
ImageNet? One way would be to make a dedicated property for ImageNet synset
identifiers in Wikidata, — independently of WordNet. These would enable
Wikidata to record ImageNet’s discrepancies, e.g., with the “deprecated”
feature or by a suitable qualifier attached to the property. A dedicated
property may also make certain SPARQL query faster as it would not require the
use of the FILTER SPARQL keyword to distinguish between different LOD URI
prefixes.

The low number of statements for Wikidata items linked to ILSVRC classes via
WordNet synsets poses a problem if we want to utilize these statements to give
contexts to the categories identified with ImageNet-trained image classifiers.
Even for _dog_ —the Wikidata items with the most statements among those items
linked to WordNet currently—the number of relevant statements to support a
semantic characterization is low: Many of the statements are for the property
_taxon common name_ (which is just a label) and the number of statements which
links to other statements and characterizes the concept of _dog_ well may be
argued to be less than 10: It is a subclass of domesticated animal and pet; it
can be used as a pet, for hunting and guarding and as a service animal; and it
can produce a sound that is a _bark_. We may contrast that to ConceptNet where
there are more statements (assertions), but they are also less formal:
According to ConceptNet a dog has a big heart, brains, fleas, four legs, fur,
nose, one mouth, paws, penis, teeth, two ears; a dog can be located in the
backyard, in bed, on a couch or desk, in a doghouse, etc.; and it is capable
of barking, biting and fighting a cat among lots of other activities.999These
statements come from conceptnet-assertions-5.5.0.csv.gz which can be
downloaded from https://s3.amazonaws.com/conceptnet/precomputed-
data/2016/assertions/conceptnet-assertions-5.5.0.csv.gz, see
https://github.com/commonsense/conceptnet5/wiki/Downloads. There are
opportunities to extend Wikidata with statements that better characterize its
items, though it is not readily clear how this can be done. For instance, how
should we represent that a dog typically has fur and four legs? Or that in
some contexts it forms an antonym with cat? One property that could be used
more extensively is _has quality_ (P1552) for non-material characteristics.
Physical objects may be characterized by, e.g., height and weight, but how
should we describe the size of, say, a coffee mug: By an average height and
weight over a set of coffee mugs? If yes, then where would we get that data
from? Wikidata items may be used to characterize other items, e.g., visual
works may be described by what they depict and written works what they are
about. For instance, Wikidata can describe that _washing machine_ is the main
topic of a set of scientific articles. Yet the examples we have in Wikidata
now are mostly medical articles describing accidents with washine machines. It
not obvious how such annotations can be used with benefit in ImageNet-based
machine learning system.

Regardless of the issues around matching ImageNet synsets with Wikidata item
and the questions raised here in the discussion, I see interesting
opportunities in the combination of machine learning and a collaborative
knowledge base such as Wikidata.

## References

  * (1) Bond, F., Vossen, P., McCrae, J. P., and Fellbaum, C. CILI: the Collaborative Interlingual Index.  Proceedings of the Eighth Global WordNet Conference (January 2016), 50–57.
  * (2) Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Li, F.-F. ImageNet: A large-scale hierarchical image database.  2009 IEEE Conference on Computer Vision and Pattern Recognition (June 2009).
  * (3) He, K., Zhang, X., Ren, S., and Sun, J. Deep Residual Learning for Image Recognition.  2016 IEEE Conference on Computer Vision and Pattern Recognition (December 2015), 770–778.
  * (4) Kaffee, L.-A., Piscopo, A., Vougiouklis, P., Simperl, E., Carr, L., and Pintscher, L. A Glimpse into Babel: An Analysis of Multilinguality in Wikidata.  Proceedings of the 13th International Symposium on Open Collaboration (August 2017).
  * (5) Krizhevsky, A., Sutskever, I., and Hinton, G. Imagenet classification with deep convolutional neural networks.  Advances in Neural Information Processing Systems 25 (December 2012), 1097–1105.
  * (6) Miller, G. A. WordNet: a lexical database for English.  Communications of the ACM 38 (November 1995), 39–41.
  * (7) Navigli, R., and Ponzetto, S. P. BabelNet: building a very large multilingual semantic network.  Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (July 2010), 216–225.
  * (8) Nielsen, F. Å. Wembedder: Wikidata entity embedding web service.
  * (9) Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A. C., and Li, F.-F. ImageNet Large Scale Visual Recognition Challenge.
  * (10) Schmidhuber, J. Deep learning in neural networks: an overview.  Neural Networks 61 (October 2014), 85–117.
  * (11) Speer, R., Chin, J., and Havasi, C. ConceptNet 5.5: An Open Multilingual Graph of General Knowledge.  Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (December 2016), 4444–4451.
  * (12) Vrandečić, D., and Krötzsch, M. Wikidata: a free collaborative knowledgebase.  Communications of the ACM 57 (October 2014), 78–85.