OpenRaiser/Intern-Atlas huggingface dataset:
An Entropy-based Proof of Threshold Saturation for Nonbinary SC-LDPC Ensembles on the BEC
Venue: arXiv cs.IT 2020
Year: 2020

In this paper we are concerned with the asymptotic analysis of nonbinary spatially-coupled low-density parity-check (SC-LDPC) ensembles defined over GL$\left(2^{m}\right)$ (the general linear group of degree $m$ over GF$\left(2\right)$). Our purpose is to prove threshold saturation when the transmission takes place on the binary erasure channel (BEC). To this end, we establish the duality rule for entropy for nonbinary variable-node (VN) and check-node (CN) convolutional operators to accommodate the nonbinary density evolution (DE) analysis. Based on this, we construct the explicit forms of the potential functions for uncoupled and coupled DE recursions. In addition, we show that these functions exhibit similar monotonicity properties as those for binary LDPC and SC-LDPC ensembles over general binary memoryless symmetric (BMS) channels. This leads to the threshold saturation theorem and its converse for nonbinary SC-LDPC ensembles on the BEC, following the proof technique developed by S. Kumar et al.
Patch Based Classification of Remote Sensing Data: A Comparison of 2D-CNN, SVM and NN Classifiers
Venue: arXiv cs.CV 2020
Year: 2020

Pixel based algorithms including back propagation neural networks (NN) and support vector machines (SVM) have been widely used for remotely sensed image classifications. Within last few years, deep learning based image classifier like convolution neural networks (2D-CNN) are becoming popular alternatives to these classifiers. In this paper, we compare performance of patch based SVM and NN with that of a deep learning algorithms comprising of 2D-CNN and fully connected layers. Similar to CNN which utilise image patches to derive features for further classification, we propose to use patches as an input in place of individual pixel with both SVM and NN classifiers. Two datasets, one multispectral and other hyperspectral data was used to compare the performance of different classifiers. Results with both datasets suggest the effectiveness of patch based SVM and NN classifiers in comparison to state of art 2D-CNN classifier.
Network Moments: Extensions and Sparse-Smooth Attacks
Venue: arXiv cs.LG 2020
Year: 2020

The impressive performance of deep neural networks (DNNs) has immensely strengthened the line of research that aims at theoretically analyzing their effectiveness. This has incited research on the reaction of DNNs to noisy input, namely developing adversarial input attacks and strategies that lead to robust DNNs to these attacks. To that end, in this paper, we derive exact analytic expressions for the first and second moments (mean and variance) of a small piecewise linear (PL) network (Affine, ReLU, Affine) subject to Gaussian input. In particular, we generalize the second-moment expression of Bibi et al. to arbitrary input Gaussian distributions, dropping the zero-mean assumption. We show that the new variance expression can be efficiently approximated leading to much tighter variance estimates as compared to the preliminary results of Bibi et al. Moreover, we experimentally show that these expressions are tight under simple linearizations of deeper PL-DNNs, where we investigate the effect of the linearization sensitivity on the accuracy of the moment estimates. Lastly, we show that the derived expressions can be used to construct sparse and smooth Gaussian adversarial attacks (targeted and non-targeted) that tend to lead to perceptually feasible input attacks.
Internet of Threats Introspection in Dynamic Intelligent Virtual Sensing
Venue: arXiv cs.CR 2020
Year: 2020

Continued ubiquity of communication infrastructure across Internet of Things (IoT) ecosystems has seen persistent advances of dynamic, intelligent, virtualised sensing and actuation. This has led to effective interaction across the connected ecosystem of -things. Furthermore, this has enabled the creation of smart environments that has created the need for the development of different IoT protocols that support the relaying of information across billions of electronic devices over the Internet. That notwithstanding, the phenomenon of virtual sensors that are supported by IoT technologies like Wireless Sensor Networks (WSNs), RFID, WIFI, Bluetooth, ZigBee, IEEE 802.15.4, etc., emulates physical sensors, and enables more efficient resource management through the dynamic allocation of virtual sensor resources. A distinctive example of this has been the proposition of the Dynamic Intelligent Virtual Sensors (DIVS). This DIVS concept is a novel proposition that allows sensing to be done by the use of logical instances through the use of labeled data. This allows for making accurate predictions during data fusion. However, a potential security attack on DIVS may end up providing false labels during the User Feedback Process (UFP), which may interfere with the accuracy of DIVS. This paper investigates the threat landscape in DIVS when employed in IoT ecosystems, in order to identify the extent to which the severity of these threats may hinder accurate prediction of DIVS in IoT, based on labeled data.
Flood severity mapping from Volunteered Geographic Information by interpreting water level from images containing people: a case study of Hurricane Harvey
Venue: arXiv cs.CV 2020
Year: 2020

With increasing urbanization, in recent years there has been a growing interest and need in monitoring and analyzing urban flood events. Social media, as a new data source, can provide real-time information for flood monitoring. The social media posts with locations are often referred to as Volunteered Geographic Information (VGI), which can reveal the spatial pattern of such events. Since more images are shared on social media than ever before, recent research focused on the extraction of flood-related posts by analyzing images in addition to texts. Apart from merely classifying posts as flood relevant or not, more detailed information, e.g. the flood severity, can also be extracted based on image interpretation. However, it has been less tackled and has not yet been applied for flood severity mapping. In this paper, we propose a novel three-step process to extract and map flood severity information. First, flood relevant images are retrieved with the help of pre-trained convolutional neural networks as feature extractors. Second, the images containing people are further classified into four severity levels by observing the relationship between body parts and their partial inundation, i.e. images are classified according to the water level with respect to different body parts, namely ankle, knee, hip, and chest. Lastly, locations of the Tweets are used for generating a map of estimated flood extent and severity. This process was applied to an image dataset collected during Hurricane Harvey in 2017, as a proof of concept. The results show that VGI can be used as a supplement to remote sensing observations for flood extent mapping and is beneficial, especially for urban areas, where the infrastructure is often occluding water. Based on the extracted water level information, an integrated overview of flood severity can be provided for the early stages of emergency response.
Enriching Large-Scale Eventuality Knowledge Graph with Entailment Relations
Venue: arXiv cs.CL 2020
Year: 2020

Computational and cognitive studies suggest that the abstraction of eventualities (activities, states, and events) is crucial for humans to understand daily eventualities. In this paper, we propose a scalable approach to model the entailment relations between eventualities ("eat an apple'' entails ''eat fruit''). As a result, we construct a large-scale eventuality entailment graph (EEG), which has 10 million eventuality nodes and 103 million entailment edges. Detailed experiments and analysis demonstrate the effectiveness of the proposed approach and quality of the resulting knowledge graph. Our datasets and code are available at https://github.com/HKUST-KnowComp/ASER-EEG.
Hierarchical Decompositions of dihypergraphs
Venue: arXiv cs.DM 2020
Year: 2020

In this paper we are interested in decomposing a dihypergraph $\mathcal{H} = (V, \mathcal{E})$ into simpler dihypergraphs, that can be handled more efficiently. We study the properties of dihypergraphs that can be hierarchically decomposed into trivial dihypergraphs, \ie vertex hypergraph. The hierarchical decomposition is represented by a full labelled binary tree called $\mathcal{H}$-tree, in the fashion of hierarchical clustering. We present a polynomial time and space algorithm to achieve such a decomposition by producing its corresponding $\mathcal{H}$-tree. However, there are dihypergraphs that cannot be completely decomposed into trivial components. Therefore, we relax this requirement to more indecomposable dihypergraphs called H-factors, and discuss applications of this decomposition to closure systems and lattices.
Kolmogorov's legacy: Algorithmic Theory of Informatics and Kolmogorov Programmable Technology
Venue: arXiv cs.GL 2020
Year: 2020

In this survey, we explore Andrei Nikolayevich Kolmogorov's seminal work in just one of his many facets: its influence Computer Science especially his viewpoint of what herein we call 'Algorithmic Theory of Informatics.' Can a computer file 'reduce' its 'size' if we add to it new symbols? Do equations of state like second Newton law in Physics exist in Computer Science? Can Leibniz' principle of identification by indistinguishability be formalized? In the computer, there are no coordinates, no distances, and no dimensions; most of traditional mathematical approaches do not work. The computer processes finite binary sequences i.e. the sequences of 0 and 1. A natural question arises: Should we continue today, as we have done for many years, to approach Computer Science problems by using classical mathematical apparatus such as 'mathematical modeling'? The first who drew attention to this question and gave insightful answers to it was Kolmogorov in 1960s. Kolmogorov's empirical postulate about existence of a program that translates 'a natural number into its binary record and the record into the number' formulated in 1958 represents a hint of Kolmogorov's approach to Computer Science. Following his ideas, we interpret Kolmogorov algorithm, Kolmogorov machine, and Kolmogorov complexity in the context of modern information technologies showing that they essentially represent fundamental elements of Algorithmic Theory of Informatics, Kolmogorov Programmable Technology, and new Komputer Mathematics i.e. Mathematics of computers.
Automatic Query Optimization for Retrieving Traffic Tweets
Venue: arXiv cs.SI 2020
Year: 2020

Twitter, like many social media and data brokering companies, makes their data available through a search API (application programming interface). In addition to filtering results by date and location, researchers can search for tweets with specific content with a boolean text query, using {\it AND}, {\it OR}, and {\it NOT} operators to select the combinations of phrases which must, or must not, appear in matching tweets. This boolean text search system is not at all unique to Twitter and is found in many different contexts, including academic, legal, and medical databases, however it is stretched to its limits in Twitter's use case because of the relative volume and brevity of tweets. In addition, the semi-automated use of such systems was well studied under the topic of Information Retrieval during the 1980s and 1990s, however the study of such systems has greatly declined since that time. As such, we propose updated methods for automatically selecting and refining complex boolean search queries that can isolate relevant results with greater specificity and completeness. Furthermore, we present preliminary results of using an optimized query to collect a sample of traffic-incident-related tweets, along with the results of manually classifying and analyzing them.
QTRAN++: Improved Value Transformation for Cooperative Multi-Agent Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

QTRAN is a multi-agent reinforcement learning (MARL) algorithm capable of learning the largest class of joint-action value functions up to date. However, despite its strong theoretical guarantee, it has shown poor empirical performance in complex environments, such as Starcraft Multi-Agent Challenge (SMAC). In this paper, we identify the performance bottleneck of QTRAN and propose a substantially improved version, coined QTRAN++. Our gains come from (i) stabilizing the training objective of QTRAN, (ii) removing the strict role separation between the action-value estimators of QTRAN, and (iii) introducing a multi-head mixing network for value transformation. Through extensive evaluation, we confirm that our diagnosis is correct, and QTRAN++ successfully bridges the gap between empirical performance and theoretical guarantee. In particular, QTRAN++ newly achieves state-of-the-art performance in the SMAC environment. The code will be released.
Object Tracking through Residual and Dense LSTMs
Venue: arXiv cs.CV 2020
Year: 2020

Visual object tracking task is constantly gaining importance in several fields of application as traffic monitoring, robotics, and surveillance, to name a few. Dealing with changes in the appearance of the tracked object is paramount to achieve high tracking accuracy, and is usually achieved by continually learning features. Recently, deep learning-based trackers based on LSTMs (Long Short-Term Memory) recurrent neural networks have emerged as a powerful alternative, bypassing the need to retrain the feature extraction in an online fashion. Inspired by the success of residual and dense networks in image recognition, we propose here to enhance the capabilities of hybrid trackers using residual and/or dense LSTMs. By introducing skip connections, it is possible to increase the depth of the architecture while ensuring a fast convergence. Experimental results on the Re3 tracker show that DenseLSTMs outperform Residual and regular LSTM, and offer a higher resilience to nuisances such as occlusions and out-of-view objects. Our case study supports the adoption of residual-based RNNs for enhancing the robustness of other trackers.
MUMBO: MUlti-task Max-value Bayesian Optimization
Venue: arXiv cs.LG 2020
Year: 2020

We propose MUMBO, the first high-performing yet computationally efficient acquisition function for multi-task Bayesian optimization. Here, the challenge is to perform efficient optimization by evaluating low-cost functions somehow related to our true target function. This is a broad class of problems including the popular task of multi-fidelity optimization. However, while information-theoretic acquisition functions are known to provide state-of-the-art Bayesian optimization, existing implementations for multi-task scenarios have prohibitive computational requirements. Previous acquisition functions have therefore been suitable only for problems with both low-dimensional parameter spaces and function query costs sufficiently large to overshadow very significant optimization overheads. In this work, we derive a novel multi-task version of entropy search, delivering robust performance with low computational overheads across classic optimization challenges and multi-task hyper-parameter tuning. MUMBO is scalable and efficient, allowing multi-task Bayesian optimization to be deployed in problems with rich parameter and fidelity spaces.
Machine Learning Pipelines: Provenance, Reproducibility and FAIR Data Principles
Venue: arXiv cs.LG 2020
Year: 2020

Machine learning (ML) is an increasingly important scientific tool supporting decision making and knowledge generation in numerous fields. With this, it also becomes more and more important that the results of ML experiments are reproducible. Unfortunately, that often is not the case. Rather, ML, similar to many other disciplines, faces a reproducibility crisis. In this paper, we describe our goals and initial steps in supporting the end-to-end reproducibility of ML pipelines. We investigate which factors beyond the availability of source code and datasets influence reproducibility of ML experiments. We propose ways to apply FAIR data practices to ML workflows. We present our preliminary results on the role of our tool, ProvBook, in capturing and comparing provenance of ML experiments and their reproducibility using Jupyter Notebooks.
The color out of space: learning self-supervised representations for Earth Observation imagery
Venue: arXiv cs.CV 2020
Year: 2020

The recent growth in the number of satellite images fosters the development of effective deep-learning techniques for Remote Sensing (RS). However, their full potential is untapped due to the lack of large annotated datasets. Such a problem is usually countered by fine-tuning a feature extractor that is previously trained on the ImageNet dataset. Unfortunately, the domain of natural images differs from the RS one, which hinders the final performance. In this work, we propose to learn meaningful representations from satellite imagery, leveraging its high-dimensionality spectral bands to reconstruct the visible colors. We conduct experiments on land cover classification (BigEarthNet) and West Nile Virus detection, showing that colorization is a solid pretext task for training a feature extractor. Furthermore, we qualitatively observe that guesses based on natural images and colorization rely on different parts of the input. This paves the way to an ensemble model that eventually outperforms both the above-mentioned techniques.
Rapid Structural Pruning of Neural Networks with Set-based Task-Adaptive Meta-Pruning
Venue: arXiv cs.LG 2020
Year: 2020

As deep neural networks are growing in size and being increasingly deployed to more resource-limited devices, there has been a recent surge of interest in network pruning methods, which aim to remove less important weights or activations of a given network. A common limitation of most existing pruning techniques, is that they require pre-training of the network at least once before pruning, and thus we can benefit from reduction in memory and computation only at the inference time. However, reducing the training cost of neural networks with rapid structural pruning may be beneficial either to minimize monetary cost with cloud computing or to enable on-device learning on a resource-limited device. Recently introduced random-weight pruning approaches can eliminate the needs of pretraining, but they often obtain suboptimal performance over conventional pruning techniques and also does not allow for faster training since they perform unstructured pruning. To overcome their limitations, we propose Set-based Task-Adaptive Meta Pruning (STAMP), which task-adaptively prunes a network pretrained on a large reference dataset by generating a pruning mask on it as a function of the target dataset. To ensure maximum performance improvements on the target task, we meta-learn the mask generator over different subsets of the reference dataset, such that it can generalize well to any unseen datasets within a few gradient steps of training. We validate STAMP against recent advanced pruning methods on benchmark datasets, on which it not only obtains significantly improved compression rates over the baselines at similar accuracy, but also orders of magnitude faster training speed.
Scalable Range Locks for Scalable Address Spaces and Beyond
Venue: arXiv cs.OS 2020
Year: 2020

Range locks are a synchronization construct designed to provide concurrent access to multiple threads (or processes) to disjoint parts of a shared resource. Originally conceived in the file system context, range locks are gaining increasing interest in the Linux kernel community seeking to alleviate bottlenecks in the virtual memory management subsystem. The existing implementation of range locks in the kernel, however, uses an internal spin lock to protect the underlying tree structure that keeps track of acquired and requested ranges. This spin lock becomes a point of contention on its own when the range lock is frequently acquired. Furthermore, where and exactly how specific (refined) ranges can be locked remains an open question. In this paper, we make two independent, but related contributions. First, we propose an alternative approach for building range locks based on linked lists. The lists are easy to maintain in a lock-less fashion, and in fact, our range locks do not use any internal locks in the common case. Second, we show how the range of the lock can be refined in the mprotect operation through a speculative mechanism. This refinement, in turn, allows concurrent execution of mprotect operations on non-overlapping memory regions. We implement our new algorithms and demonstrate their effectiveness in user-space and kernel-space, achieving up to 9$\times$ speedup compared to the stock version of the Linux kernel. Beyond the virtual memory management subsystem, we discuss other applications of range locks in parallel software. As a concrete example, we show how range locks can be used to facilitate the design of scalable concurrent data structures, such as skip lists.
Neural networks adapting to datasets: learning network size and topology
Venue: arXiv cs.LG 2020
Year: 2020

We introduce a flexible setup allowing for a neural network to learn both its size and topology during the course of a standard gradient-based training. The resulting network has the structure of a graph tailored to the particular learning task and dataset. The obtained networks can also be trained from scratch and achieve virtually identical performance. We explore the properties of the network architectures for a number of datasets of varying difficulty observing systematic regularities. The obtained graphs can be therefore understood as encoding nontrivial characteristics of the particular classification tasks.
Risk Communication in Asian Countries: COVID-19 Discourse on Twitter
Venue: arXiv cs.SI 2020
Year: 2020

COVID-19 has become one of the most widely talked about topics on social media. This research characterizes risk communication patterns by analyzing the public discourse on the novel coronavirus from four Asian countries: South Korea, Iran, Vietnam, and India, which suffered the outbreak to different degrees. The temporal analysis shows that the official epidemic phases issued by governments do not match well with the online attention on COVID-19. This finding calls for a need to analyze the public discourse by new measures, such as topical dynamics. Here, we propose an automatic method to detect topical phase transitions and compare similarities in major topics across these countries over time. We examine the time lag difference between social media attention and confirmed patient counts. For dynamics, we find an inverse relationship between the tweet count and topical diversity.
Shared Task on Evaluating Accuracy in Natural Language Generation
Venue: arXiv cs.CL 2020
Year: 2020

We propose a shared task on methodologies and algorithms for evaluating the accuracy of generated texts. Participants will measure the accuracy of basketball game summaries produced by NLG systems from basketball box score data.