OpenRaiser/Intern-Atlas huggingface dataset:
Symblicit Exploration and Elimination for Probabilistic Model Checking
Venue: arXiv cs.LO 2020
Year: 2020

Binary decision diagrams can compactly represent vast sets of states, mitigating the state space explosion problem in model checking. Probabilistic systems, however, require multi-terminal diagrams storing rational numbers. They are inefficient for models with many distinct probabilities and for iterative numeric algorithms like value iteration. In this paper, we present a new "symblicit" approach to checking Markov chains and related probabilistic models: We first generate a decision diagram that symbolically collects all reachable states and their predecessors. We then concretise states one-by-one into an explicit partial state space representation. Whenever all predecessors of a state have been concretised, we eliminate it from the explicit state space in a way that preserves all relevant probabilities and rewards. We thus keep few explicit states in memory at any time. Experiments show that very large models can be model-checked in this way with very low memory consumption.
Granular Learning with Deep Generative Models using Highly Contaminated Data
Venue: arXiv cs.LG 2020
Year: 2020

An approach to utilize recent advances in deep generative models for anomaly detection in a granular (continuous) sense on a real-world image dataset with quality issues is detailed using recent normalizing flow models, with implications in many other applications/domains/data types. The approach is completely unsupervised (no annotations available) but qualitatively shown to provide accurate semantic labeling for images via heatmaps of the scaled log-likelihood overlaid on the images. When sorted based on the median values per image, clear trends in quality are observed. Furthermore, downstream classification is shown to be possible and effective via a weakly supervised approach using the log-likelihood output from a normalizing flow model as a training signal for a feature-extracting convolutional neural network. The pre-linear dense layer outputs on the CNN are shown to disentangle high level representations and efficiently cluster various quality issues. Thus, an entirely non-annotated (fully unsupervised) approach is shown possible for accurate estimation and classification of quality issues..
Hierarchical Modeling of Multidimensional Data in Regularly Decomposed Spaces: Synthesis and Perspective
Venue: arXiv cs.CV 2020
Year: 2020

This fourth and last tome is focusing on describing the envisioned works for a project that has been presented in the preceding tome. It is about a new approach dedicated to the coding of still and moving pictures, trying to bridge the MPEG-4 and MPEG-7 standard bodies. The aim of this project is to define the principles of self-descriptive video coding. In order to establish them, the document is composed in five chapters that describe the various envisioned techniques for developing such a new approach in visual coding: - image segmentation, - computation of visual descriptors, - computation of perceptual groupings, - building of visual dictionaries, - picture and video coding. Based on the techniques of multiresolution computing, it is proposed to develop an image segmentation made from piecewise regular components, to compute attributes on the frame and the rendering of so produced shapes, independently to the geometric transforms that can occur in the image plane, and to gather them into perceptual groupings so as to be able in performing recognition of partially hidden patterns. Due to vector quantization of shapes frame and rendering, it will appear that simple shapes may be compared to a visual alphabet and that complex shapes then become words written using this alphabet and be recorded into a dictionary. With the help of a nearest neighbour scanning applied on the picture shapes, the self-descriptive coding will then generate a sentence made from words written using the simple shape alphabet.
A Novel Inspection System For Variable Data Printing Using Deep Learning
Venue: arXiv cs.CV 2020
Year: 2020

We present a novel approach for inspecting variable data prints (VDP) with an ultra-low false alarm rate (0.005%) and potential applicability to other real-world problems. The system is based on a comparison between two images: a reference image and an image captured by low-cost scanners. The comparison task is challenging as low-cost imaging systems create artifacts that may erroneously be classified as true (genuine) defects. To address this challenge we introduce two new fusion methods, for change detection applications, which are both fast and efficient. The first is an early fusion method that combines the two input images into a single pseudo-color image. The second, called Change-Detection Single Shot Detector (CD-SSD) leverages the SSD by fusing features in the middle of the network. We demonstrate the effectiveness of the proposed deep learning-based approach with a large dataset from real-world printing scenarios. Finally, we evaluate our models on a different domain of aerial imagery change detection (AICD). Our best method clearly outperforms the state-of-the-art baseline on this dataset.
Merging of Ontologies Through Merging of Their Rules
Venue: arXiv cs.AI 2020
Year: 2020

Ontology merging is important, but not always effective. The main reason, why ontology merging is not effective, is that ontology merging is performed without considering goals. Goals define the way, in which ontologies to be merged more effectively. The paper illustrates ontology merging by means of rules, which are generated from these ontologies. This is necessary for further use in expert systems.
Reachability in fixed dimension vector addition systems with states
Venue: arXiv cs.FL 2020
Year: 2020

The reachability problem is a central decision problem for formal verification based on vector addition systems with states (VASS), which are equivalent to Petri nets and form one of the most studied and applied models of concurrency. Reachability for VASS is also inter-reducible with a plethora of problems from a number of areas of computer science. In spite of recent progress, the complexity of the reachability problem remains unsettled, and it is closely related to the lengths of shortest VASS runs that witness reachability. We consider VASS of fixed dimension, and obtain three main results. For the first two, we assume that the integers in the input are given in unary, and that the control graph of the given VASS is flat (i.e., without nested cycles). We obtain a family of VASS in dimension 3 whose shortest reachability witnessing runs are exponential, and we show that the reachability problem is NP-hard in dimension 7. These results resolve negatively questions that had been posed by the works of Blondin et al. in LICS 2015 and Englert et al. in LICS 2016, and contribute a first construction that distinguishes 3-dimensional flat VASS from 2-dimensional VASS. Our third result, by means of a novel family of products of integer fractions, shows that 4-dimensional VASS can have doubly exponentially long shortest reachability witnessing runs. The smallest dimension for which this was previously known is 14.
DoF Region of the Decentralized MIMO Broadcast Channel -- How many informed antennas do we need?
Venue: arXiv cs.IT 2020
Year: 2020

In this work, we study the impact of imperfect sharing of the Channel State Information (CSI) available at the transmitters on a Network MIMO setting in which a set of $M$ transmit antennas, possibly not co-located, jointly serve two multi-antenna users endowed with $N_1$ and $N_2$ antennas, respectively. We consider the case where only a subset of $k$ transmit antennas have access to perfect CSI, whereas the other $M-k$ transmit antennas have only access to finite precision CSI. The analysis of this configuration aims to answer the question of how much an extra informed antenna can help. We model this scenario as a Decentralized MIMO Broadcast Channel (BC) and characterize the Degrees-of-Freedom (DoF) region, showing that only $k=\max(N_1,N_2)$ antennas with perfect CSI are needed to achieve the DoF of the conventional BC with ubiquitous perfect CSI. Furthermore, we identify the increase of DoF obtained by providing CSI to an extra transmit antenna.
Domination in Signed Petri Net
Venue: arXiv cs.DM 2020
Year: 2020

In this paper, domination in Signed Petri net(SPN) has been introduced.We identify some of the Petri net structures where a dominating set can exist.Applications of producer consumer problem, searching of food by bees and finding similarity in research papers are given to understand the areas where the proposed theory can be used.
Evaluating the snappability of bar-joint frameworks
Venue: arXiv cs.CG 2020
Year: 2020

It is well-known that there exist bar-joint frameworks (without continuous flexions) whose physical models can snap between different realizations due to non-destructive elastic deformations of material. We present a method to measure these snapping capability -- shortly called snappability -- based on the total elastic strain energy of the framework by computing the deformation of all bars using Hook's law. The presented theoretical results give further connections between shakiness and snapping beside the well-known technique of averaging and deaveraging.
One-Clock Priced Timed Games are PSPACE-hard
Venue: arXiv cs.GT 2020
Year: 2020

The main result of this paper is that computing the value of a one-clock priced timed game (OCPTG) is PSPACE-hard. Along the way, we provide a family of OCPTGs that have an exponential number of event points. Both results hold even in very restricted classes of games such as DAGs with treewidth three. Finally, we provide a number of positive results, including polynomial-time algorithms for even more restricted classes of OCPTGs such as trees.
Fast Generation of Big Random Binary Trees
Venue: arXiv cs.DS 2020
Year: 2020

random_tree() is a linear time and space C++ implementation able to create trees of up to a billion nodes for genetic programming and genetic improvement experiments. A 3.60GHz CPU can generate more than 18 million random nodes for GP program trees per second.
Multi-Robot Formation Control Using Reinforcement Learning
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we present a machine learning approach to move a group of robots in a formation. We model the problem as a multi-agent reinforcement learning problem. Our aim is to design a control policy for maintaining a desired formation among a number of agents (robots) while moving towards a desired goal. This is achieved by training our agents to track two agents of the group and maintain the formation with respect to those agents. We consider all agents to be homogeneous and model them as unicycle [1]. In contrast to the leader-follower approach, where each agent has an independent goal, our approach aims to train the agents to be cooperative and work towards the common goal. Our motivation to use this method is to make a fully decentralized multi-agent formation system and scalable for a number of agents.
Understanding and mitigating gradient pathologies in physics-informed neural networks
Venue: arXiv cs.LG 2020
Year: 2020

The widespread use of neural networks across different scientific domains often involves constraining them to satisfy certain symmetries, conservation laws, or other domain knowledge. Such constraints are often imposed as soft penalties during model training and effectively act as domain-specific regularizers of the empirical risk loss. Physics-informed neural networks is an example of this philosophy in which the outputs of deep neural networks are constrained to approximately satisfy a given set of partial differential equations. In this work we review recent advances in scientific machine learning with a specific focus on the effectiveness of physics-informed neural networks in predicting outcomes of physical systems and discovering hidden physics from noisy data. We will also identify and analyze a fundamental mode of failure of such approaches that is related to numerical stiffness leading to unbalanced back-propagated gradients during model training. To address this limitation we present a learning rate annealing algorithm that utilizes gradient statistics during model training to balance the interplay between different terms in composite loss functions. We also propose a novel neural network architecture that is more resilient to such gradient pathologies. Taken together, our developments provide new insights into the training of constrained neural networks and consistently improve the predictive accuracy of physics-informed neural networks by a factor of 50-100x across a range of problems in computational physics. All code and data accompanying this manuscript are publicly available at \url{https://github.com/PredictiveIntelligenceLab/GradientPathologiesPINNs}.
Optimal Approximate Sampling from Discrete Probability Distributions
Venue: arXiv cs.DS 2020
Year: 2020

This paper addresses a fundamental problem in random variate generation: given access to a random source that emits a stream of independent fair bits, what is the most accurate and entropy-efficient algorithm for sampling from a discrete probability distribution $(p_1, \dots, p_n)$, where the probabilities of the output distribution $(\hat{p}_1, \dots, \hat{p}_n)$ of the sampling algorithm must be specified using at most $k$ bits of precision? We present a theoretical framework for formulating this problem and provide new techniques for finding sampling algorithms that are optimal both statistically (in the sense of sampling accuracy) and information-theoretically (in the sense of entropy consumption). We leverage these results to build a system that, for a broad family of measures of statistical accuracy, delivers a sampling algorithm whose expected entropy usage is minimal among those that induce the same distribution (i.e., is "entropy-optimal") and whose output distribution $(\hat{p}_1, \dots, \hat{p}_n)$ is a closest approximation to the target distribution $(p_1, \dots, p_n)$ among all entropy-optimal sampling algorithms that operate within the specified $k$-bit precision. This optimal approximate sampler is also a closer approximation than any (possibly entropy-suboptimal) sampler that consumes a bounded amount of entropy with the specified precision, a class which includes floating-point implementations of inversion sampling and related methods found in many software libraries. We evaluate the accuracy, entropy consumption, precision requirements, and wall-clock runtime of our optimal approximate sampling algorithms on a broad set of distributions, demonstrating the ways that they are superior to existing approximate samplers and establishing that they often consume significantly fewer resources than are needed by exact samplers.
Spatial-Spectral Residual Network for Hyperspectral Image Super-Resolution
Venue: arXiv cs.CV 2020
Year: 2020

Deep learning-based hyperspectral image super-resolution (SR) methods have achieved great success recently. However, most existing models can not effectively explore spatial information and spectral information between bands simultaneously, obtaining relatively low performance. To address this issue, in this paper, we propose a novel spectral-spatial residual network for hyperspectral image super-resolution (SSRNet). Our method can effectively explore spatial-spectral information by using 3D convolution instead of 2D convolution, which enables the network to better extract potential information. Furthermore, we design a spectral-spatial residual module (SSRM) to adaptively learn more effective features from all the hierarchical features in units through local feature fusion, significantly improving the performance of the algorithm. In each unit, we employ spatial and temporal separable 3D convolution to extract spatial and spectral information, which not only reduces unaffordable memory usage and high computational cost, but also makes the network easier to train. Extensive evaluations and comparisons on three benchmark datasets demonstrate that the proposed approach achieves superior performance in comparison to existing state-of-the-art methods.
Cross-dataset Training for Class Increasing Object Detection
Venue: arXiv cs.CV 2020
Year: 2020

We present a conceptually simple, flexible and general framework for cross-dataset training in object detection. Given two or more already labeled datasets that target for different object classes, cross-dataset training aims to detect the union of the different classes, so that we do not have to label all the classes for all the datasets. By cross-dataset training, existing datasets can be utilized to detect the merged object classes with a single model. Further more, in industrial applications, the object classes usually increase on demand. So when adding new classes, it is quite time-consuming if we label the new classes on all the existing datasets. While using cross-dataset training, we only need to label the new classes on the new dataset. We experiment on PASCAL VOC, COCO, WIDER FACE and WIDER Pedestrian with both solo and cross-dataset settings. Results show that our cross-dataset pipeline can achieve similar impressive performance simultaneously on these datasets compared with training independently.
Block-wise Dynamic Sparseness
Venue: arXiv cs.LG 2020
Year: 2020

Neural networks have achieved state of the art performance across a wide variety of machine learning tasks, often with large and computation-heavy models. Inducing sparseness as a way to reduce the memory and computation footprint of these models has seen significant research attention in recent years. In this paper, we present a new method for \emph{dynamic sparseness}, whereby part of the computations are omitted dynamically, based on the input. For efficiency, we combined the idea of dynamic sparseness with block-wise matrix-vector multiplications. In contrast to static sparseness, which permanently zeroes out selected positions in weight matrices, our method preserves the full network capabilities by potentially accessing any trained weights. Yet, matrix vector multiplications are accelerated by omitting a pre-defined fraction of weight blocks from the matrix, based on the input. Experimental results on the task of language modeling, using recurrent and quasi-recurrent models, show that the proposed method can outperform a magnitude-based static sparseness baseline. In addition, our method achieves similar language modeling perplexities as the dense baseline, at half the computational cost at inference time.
Funding information in Web of Science: An updated overview
Venue: arXiv cs.DL 2020
Year: 2020

Despite the limitations of funding acknowledgment (FA) data in Web of Science (WoS), studies using FA information have increased rapidly over the last several years. Considering this WoS'recent practice of updating funding data, this paper further investigates the characteristics and distribution of FA data in four WoS journal citation indexes. The research reveals that FA information coverage variances persist cross all four citation indexes by time coverage, language and document type. Our evidence suggests an improvement in FA information collection in humanity and social science research. Departing from previous studies, we argue that FA text (FT) alone no longer seems an appropriate field to retrieve and analyze funding information, since a substantial number of documents only report funding agency or grant number information in respective fields. Articles written in Chinese have a higher FA presence rate than other non-English WoS publications. This updated study concludes with a discussion of new findings and practical guidance for the future retrieval and analysis of funded research.
A (Simplified) Supreme Being Necessarily Exists, says the Computer: Computationally Explored Variants of Gödel's Ontological Argument
Venue: arXiv cs.LO 2020
Year: 2020

An approach to universal (meta-)logical reasoning in classical higher-order logic is employed to explore and study simplifications of Kurt Gödel's modal ontological argument. Some argument premises are modified, others are dropped, modal collapse is avoided and validity is shown already in weak modal logics K and T. Key to the gained simplifications of Gödel's original theory is the exploitation of a link to the notions of filter and ultrafilter from topology. The paper illustrates how modern knowledge representation and reasoning technology for quantified non-classical logics can contribute new knowledge to other disciplines. The contributed material is also well suited to support teaching of non-trivial logic formalisms in classroom.
Semi-automatic methods for adding words to the dictionary of VepKar corpus based on inflectional rules extracted from Wiktionary
Venue: arXiv cs.IR 2020
Year: 2020

The article describes a technique for using English Wiktionary inflection tables for generating word forms for Veps verbs and nominals in the Open corpus of Veps and Karelian languages. The information concerning Karelian and Veps Wiktionary entries with inflection tables is given. The operating principle of the Wiktionary static and dynamic templates is explained with the use of the jogi (river) dictionary entry as an example. The method of constructing the inflection table in the dictionary of the VepKar corpus according to the data of the dynamic template of the English Wiktionary is presented.
Age-of-Information Dependent Random Access for Massive IoT Networks
Venue: arXiv cs.IT 2020
Year: 2020

As the most well-known application of the Internet of Things (IoT), remote monitoring is now pervasive. In these monitoring applications, information usually has a higher value when it is fresher. A new metric, termed the age of information (AoI), has recently been proposed to quantify the information freshness in various IoT applications. This paper concentrates on the design and analysis of age-oriented random access for massive IoT networks. Specifically, we devise a new stationary threshold-based age-dependent random access (ADRA) protocol, in which each IoT device accesses the channel with a certain probability only when its instantaneous AoI exceeds a predetermined threshold. We manage to evaluate the average AoI of the proposed ADRA protocol mathematically by decoupling the tangled AoI evolution of multiple IoT devices and modeling the decoupled AoI evolution of each device as a Discrete-Time Markov Chain. Simulation results validate our theoretical analysis and affirm the superior age performance of the proposed ADRA protocol over the state-of-the-art age-oriented random access schemes.