OpenRaiser/Intern-Atlas huggingface dataset:
Divide-and-Conquer Large Scale Capacitated Arc Routing Problems with Route Cutting Off Decomposition
Venue: arXiv cs.NE 2020
Year: 2020

The capacitated arc routing problem is a very important problem with many practical applications. This paper focuses on the large scale capacitated arc routing problem. Traditional solution optimization approaches usually fail because of their poor scalability. The divide-and-conquer strategy has achieved great success in solving large scale optimization problems by decomposing the original large problem into smaller sub-problems and solving them separately. For arc routing, a commonly used divide-and-conquer strategy is to divide the tasks into subsets, and then solve the sub-problems induced by the task subsets separately. However, the success of a divide-and-conquer strategy relies on a proper task division, which is non-trivial due to the complex interactions between the tasks. This paper proposes a novel problem decomposition operator, named the route cutting off operator, which considers the interactions between the tasks in a sophisticated way. To examine the effectiveness of the route cutting off operator, we integrate it with two state-of-the-art divide-and-conquer algorithms, and compared with the original counterparts on a wide range of benchmark instances. The results show that the route cutting off operator can improve the effectiveness of the decomposition, and lead to significantly better results especially when the problem size is very large and the time budget is very tight.
A Gentle Introduction to Deep Learning for Graphs
Venue: arXiv cs.LG 2020
Year: 2020

The adaptive processing of graph data is a long-standing research topic which has been lately consolidated as a theme of major interest in the deep learning community. The snap increase in the amount and breadth of related research has come at the price of little systematization of knowledge and attention to earlier literature. This work is designed as a tutorial introduction to the field of deep learning for graphs. It favours a consistent and progressive introduction of the main concepts and architectural aspects over an exposition of the most recent literature, for which the reader is referred to available surveys. The paper takes a top-down view to the problem, introducing a generalized formulation of graph representation learning based on a local and iterative approach to structured information processing. It introduces the basic building blocks that can be combined to design novel and effective neural models for graphs. The methodological exposition is complemented by a discussion of interesting research challenges and applications in the field.
On Bi-Modal Constrained Coding
Venue: arXiv cs.IT 2020
Year: 2020

Bi-modal (respectively, multi-modal) constrained coding refers to an encoding model whereby a user input block can be mapped to two (respectively, multiple) codewords. In current storage applications, such as optical disks, multi-modal coding allows to achieve DC control, in addition to satisfying the runlength limited (RLL) constraint specified by the recording channel. In this work, a study is initiated on bi-modal fixed-length constrained encoders. Necessary and sufficient conditions are presented for the existence of such encoders for a given constraint. It is also shown that under somewhat stronger conditions, one can guarantee a bi-modal encoder with finite decoding delay.
Animals in Virtual Environments
Venue: arXiv cs.GR 2020
Year: 2020

The core idea in an XR (VR/MR/AR) application is to digitally stimulate one or more sensory systems (e.g. visual, auditory, olfactory) of the human user in an interactive way to achieve an immersive experience. Since the early 2000s biologists have been using Virtual Environments (VE) to investigate the mechanisms of behavior in non-human animals including insect, fish, and mammals. VEs have become reliable tools for studying vision, cognition, and sensory-motor control in animals. In turn, the knowledge gained from studying such behaviors can be harnessed by researchers designing biologically inspired robots, smart sensors, and multi-agent artificial intelligence. VE for animals is becoming a widely used application of XR technology but such applications have not previously been reported in the technical literature related to XR. Biologists and computer scientists can benefit greatly from deepening interdisciplinary research in this emerging field and together we can develop new methods for conducting fundamental research in behavioral sciences and engineering. To support our argument we present this review which provides an overview of animal behavior experiments conducted in virtual environments.
Globally Optimal Selection of Ground Stations in Satellite Systems with Site Diversity
Venue: arXiv cs.NI 2020
Year: 2020

The availability of satellite communication systems is extremely limited by atmospheric impairments, such as rain (for radio frequencies) and cloud coverage (for optical frequencies). A solution to this problem is the site diversity technique, where a network of geographically distributed ground stations (GSs) can ensure, with high probability, that at least one GS is available for connection to the satellite at each time period. However, the installation of redundant GSs induces unnecessary additional costs for the network operator. In this context, we study an optimization problem that minimizes the number of required GSs, subject to availability constraints. First, the problem is transformed into a binary-integer-linear-programming (BILP) problem, which is proven to be NP-hard. Subsequently, we design a branch-and-bound (B&B) algorithm, with global-optimization guarantee, based on the linear-programming (LP) relaxation and a greedy method as well. Finally, numerical results show that the proposed algorithm significantly outperforms state-of-the-art methods, and has low complexity in the average case.
AutoDiscern: Rating the Quality of Online Health Information with Hierarchical Encoder Attention-based Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Patients increasingly turn to search engines and online content before, or in place of, talking with a health professional. Low quality health information, which is common on the internet, presents risks to the patient in the form of misinformation and a possibly poorer relationship with their physician. To address this, the DISCERN criteria (developed at University of Oxford) are used to evaluate the quality of online health information. However, patients are unlikely to take the time to apply these criteria to the health websites they visit. We built an automated implementation of the DISCERN instrument (Brief version) using machine learning models. We compared the performance of a traditional model (Random Forest) with that of a hierarchical encoder attention-based neural network (HEA) model using two language embeddings, BERT and BioBERT. The HEA BERT and BioBERT models achieved average F1-macro scores across all criteria of 0.75 and 0.74, respectively, outperforming the Random Forest model (average F1-macro = 0.69). Overall, the neural network based models achieved 81% and 86% average accuracy at 100% and 80% coverage, respectively, compared to 94% manual rating accuracy. The attention mechanism implemented in the HEA architectures not only provided 'model explainability' by identifying reasonable supporting sentences for the documents fulfilling the Brief DISCERN criteria, but also boosted F1 performance by 0.05 compared to the same architecture without an attention mechanism. Our research suggests that it is feasible to automate online health information quality assessment, which is an important step towards empowering patients to become informed partners in the healthcare process.
The Shmoop Corpus: A Dataset of Stories with Loosely Aligned Summaries
Venue: arXiv cs.CL 2020
Year: 2020

Understanding stories is a challenging reading comprehension problem for machines as it requires reading a large volume of text and following long-range dependencies. In this paper, we introduce the Shmoop Corpus: a dataset of 231 stories that are paired with detailed multi-paragraph summaries for each individual chapter (7,234 chapters), where the summary is chronologically aligned with respect to the story chapter. From the corpus, we construct a set of common NLP tasks, including Cloze-form question answering and a simplified form of abstractive summarization, as benchmarks for reading comprehension on stories. We then show that the chronological alignment provides a strong supervisory signal that learning-based methods can exploit leading to significant improvements on these tasks. We believe that the unique structure of this corpus provides an important foothold towards making machine story comprehension more approachable.
Off-Policy Estimation of Long-Term Average Outcomes with Applications to Mobile Health
Venue: arXiv cs.LG 2020
Year: 2020

Due to the recent advancements in wearables and sensing technology, health scientists are increasingly developing mobile health (mHealth) interventions. In mHealth interventions, mobile devices are used to deliver treatment to individuals as they go about their daily lives. These treatments are generally designed to impact a near time, proximal outcome such as stress or physical activity. The mHealth intervention policies, often called just-in-time adaptive interventions, are decision rules that map an individual's current state (e.g., individual's past behaviors as well as current observations of time, location, social activity, stress and urges to smoke) to a particular treatment at each of many time points. The vast majority of current mHealth interventions deploy expert-derived policies. In this paper, we provide an approach for conducting inference about the performance of one or more such policies using historical data collected under a possibly different policy. Our measure of performance is the average of proximal outcomes over a long time period should the particular mHealth policy be followed. We provide an estimator as well as confidence intervals. This work is motivated by HeartSteps, an mHealth physical activity intervention.
Investigating Wave Energy Potential in Southern Coasts of the Caspian Sea Using Grey Wolf Optimizer Algorithm
Venue: arXiv cs.NE 2020
Year: 2020

There is a significantly accelerating trend in the application of the marine wave energy converters in recent years. As a result, it is imperative to adopt a suitable point for implementing these systems. Besides, the Caspian Sea, as one of the most important marine renewable energy sources in Asia, is capable of supplying the coastal areas with a large amount of energy. Therefore, areas around nine ports in the southern coasts of the Caspian Sea were selected to measure their wave energy potential. Initially, the amount of energy on these points was measured using the irregular energy theory. It was observed that the wave power was higher in the southwestern areas (within the Kiashahr coast and Anzali port) than the southeastern areas. A new approach was developed to compare these points and measure their fitnesses in supplying the maximum energy using the Grey Wolf optimizer (GWO) algorithm and time history analysis. In this method, the optimal parameters were first extracted from the algorithm for assessing the points within the southern areas of the Caspian Sea. These values were regarded as the assessment indices. Then, the fitness of each point was obtained using the correlation function and the norm vector to present the most optimal position with maximum wave energy exploitation potential. This new approach was validated with analytical data, and its accuracy in predicting and comparing the wave power on different points was approved. Finally, by a side-by-side comparison of the parameters affecting the wave energy, the optimum range of significant wave height and wave energy period was achieved.
Generalized Rental Harmony
Venue: arXiv cs.GT 2020
Year: 2020

Rental Harmony is the problem of assigning rooms in a rented house to tenants with different preferences, and simultaneously splitting the rent among them, such that no tenant envies the bundle (room+price) given to another tenant. Different papers have studied this problem under two incompatible assumptions: the miserly tenants assumption is that each tenant prefers a free room to a non-free room; the quasilinear tenants assumption is that each tenant attributes a monetary value to each room, and prefers a room of which the difference between value and price is maximum. This note shows how to adapt the main technique used for rental harmony with miserly tenants, using Sperner's lemma, to a much more general class of preferences, that contains both miserly and quasilinear tenants as special cases. This implies that some recent results derived for miserly tenants apply to this more general preference class too.
oLMpics -- On what Language Model Pre-training Captures
Venue: arXiv cs.CL 2020
Year: 2020

Recent success of pre-trained language models (LMs) has spurred widespread interest in the language capabilities that they possess. However, efforts to understand whether LM representations are useful for symbolic reasoning tasks have been limited and scattered. In this work, we propose eight reasoning tasks, which conceptually require operations such as comparison, conjunction, and composition. A fundamental challenge is to understand whether the performance of a LM on a task should be attributed to the pre-trained representations or to the process of fine-tuning on the task data. To address this, we propose an evaluation protocol that includes both zero-shot evaluation (no fine-tuning), as well as comparing the learning curve of a fine-tuned LM to the learning curve of multiple controls, which paints a rich picture of the LM capabilities. Our main findings are that: (a) different LMs exhibit qualitatively different reasoning abilities, e.g., RoBERTa succeeds in reasoning tasks where BERT fails completely; (b) LMs do not reason in an abstract manner and are context-dependent, e.g., while RoBERTa can compare ages, it can do so only when the ages are in the typical range of human ages; (c) On half of our reasoning tasks all models fail completely. Our findings and infrastructure can help future work on designing new datasets, models and objective functions for pre-training.
Patterns and Interactions in Network Security
Venue: arXiv cs.NI 2020
Year: 2020

Networks play a central role in cyber-security: networks deliver security attacks, suffer from them, defend against them, and sometimes even cause them. This article is a concise tutorial on the large subject of networks and security, written for all those interested in networking, whether their specialty is security or not. To achieve this goal, we derive our focus and organization from two perspectives. The first perspective is that, although mechanisms for network security are extremely diverse, they are all instances of a few patterns. Consequently, after a pragmatic classification of security attacks, the main sections of the tutorial cover the four patterns for providing network security, of which the familiar three are cryptographic protocols, packet filtering, and dynamic resource allocation. Although cryptographic protocols hide the data contents of packets, they cannot hide packet headers. When users need to hide packet headers from adversaries, which may include the network from which they are receiving service, they must resort to the pattern of compound sessions and overlays. The second perspective comes from the observation that security mechanisms interact in important ways, with each other and with other aspects of networking, so each pattern includes a discussion of its interactions.
AEGR: A simple approach to gradient reversal in autoencoders for network anomaly detection
Venue: arXiv cs.LG 2020
Year: 2020

Anomaly detection is referred to as a process in which the aim is to detect data points that follow a different pattern from the majority of data points. Anomaly detection methods suffer from several well-known challenges that hinder their performance such as high dimensionality. Autoencoders are unsupervised neural networks that have been used for the purpose of reducing dimensionality and also detecting network anomalies in large datasets. The performance of autoencoders debilitates when the training set contains noise and anomalies. In this paper, a new gradient-reversal method is proposed to overcome the influence of anomalies on the training phase for the purpose of detecting network anomalies. The method is different from other approaches as it does not require an anomaly-free training set and is based on reconstruction error. Once latent variables are extracted from the network, Local Outlier Factor is used to separate normal data points from anomalies. A simple pruning approach and data augmentation is also added to further improve performance. The experimental results show that the proposed model can outperform other well-know approaches.
BIRL: Benchmark on Image Registration methods with Landmark validation
Venue: arXiv cs.CV 2020
Year: 2020

This report presents a generic image registration benchmark with automatic evaluation using landmark annotations. The key features of the BIRL framework are: easily extendable, performance evaluation, parallel experimentation, simple visualisations, experiment's time-out limit, resuming unfinished experiments. From the research practice, we identified and focused on these two main use-cases: (a) comparison of user's (newly developed) method with some State-of-the-Art (SOTA) methods on a common dataset and (b) experimenting SOTA methods on user's custom dataset (which should contain landmark annotation). Moreover, we present an integration of several standard image registration methods aiming at biomedical imaging into the BIRL framework. This report also contains experimental results of these SOTA methods on the CIMA dataset, which is a dataset of Whole Slice Imaging (WSI) from histology/pathology containing several multi-stain tissue samples from three tissue kinds. Source and results: https://borda.github.io/BIRL
Nested Column Generation decomposition for solving the Routing and Spectrum Allocation problem in Elastic Optical Networks
Venue: arXiv cs.NI 2020
Year: 2020

With the continued growth of Internet traffic, and the scarcity of the optical spectrum, there is a continuous need to optimize the usage of this resource. In the process of provisioning elastic optical networks using the flexible frequency grid paradigm, telecommunication operators must deal with a combinatorial optimization problem that is NP-complete namely the Routing and Spectrum Allocation(RSA) problem. Following on our previous study, where we used Integer Linear Programming, and proposed a Column Generation algorithm based on a Lightpath decomposition, which proved to be the most efficient so far, we now consider the traditional Configuration decomposition that has been studied in other works in the past. In the process, we created an new mathematical model using two variable sets instead of a single variable set. Equally important,we independently rediscovered the Nested Column Generation technique, and we used it to propose an algorithm that led to a considerable improvement on the previous algorithms that use the same Configuration decomposition. When compared to the latest such existing study, our algorithm achieved an accuracy gap of 1% as opposed to 14.3% for the previous study, and a running time two orders of magnitude faster on average.
PatDNN: Achieving Real-Time DNN Execution on Mobile Devices with Pattern-based Weight Pruning
Venue: arXiv cs.LG 2020
Year: 2020

With the emergence of a spectrum of high-end mobile devices, many applications that formerly required desktop-level computation capability are being transferred to these devices. However, executing the inference of Deep Neural Networks (DNNs) is still challenging considering high computation and storage demands, specifically, if real-time performance with high accuracy is needed. Weight pruning of DNNs is proposed, but existing schemes represent two extremes in the design space: non-structured pruning is fine-grained, accurate, but not hardware friendly; structured pruning is coarse-grained, hardware-efficient, but with higher accuracy loss. In this paper, we introduce a new dimension, fine-grained pruning patterns inside the coarse-grained structures, revealing a previously unknown point in design space. With the higher accuracy enabled by fine-grained pruning patterns, the unique insight is to use the compiler to re-gain and guarantee high hardware efficiency. In other words, our method achieves the best of both worlds, and is desirable across theory/algorithm, compiler, and hardware levels. The proposed PatDNN is an end-to-end framework to efficiently execute DNN on mobile devices with the help of a novel model compression technique (pattern-based pruning based on extended ADMM solution framework) and a set of thorough architecture-aware compiler- and code generation-based optimizations (filter kernel reordering, compressed weight storage, register load redundancy elimination, and parameter auto-tuning). Evaluation results demonstrate that PatDNN outperforms three state-of-the-art end-to-end DNN frameworks, TensorFlow Lite, TVM, and Alibaba Mobile Neural Network with speedup up to 44.5x, 11.4x, and 7.1x, respectively, with no accuracy compromise. Real-time inference of representative large-scale DNNs (e.g., VGG-16, ResNet-50) can be achieved using mobile devices.
AIR: A Light-Weight Yet High-Performance Dataflow Engine based on Asynchronous Iterative Routing
Venue: arXiv cs.DC 2020
Year: 2020

Distributed Stream Processing Systems (DSPSs) are among the currently most emerging topics in data management, with applications ranging from real-time event monitoring to processing complex dataflow programs and big data analytics. The major market players in this domain are clearly represented by Apache Spark and Flink, which provide a variety of frontend APIs for SQL, statistical inference, machine learning, stream processing, and many others. Yet rather few details are reported on the integration of these engines into the underlying High-Performance Computing (HPC) infrastructure and the communication protocols they use. Spark and Flink, for example, are implemented in Java and still rely on a dedicated master node for managing their control flow among the worker nodes in a compute cluster. In this paper, we describe the architecture of our AIR engine, which is designed from scratch in C++ using the Message Passing Interface (MPI), pthreads for multithreading, and is directly deployed on top of a common HPC workload manager such as SLURM. AIR implements a light-weight, dynamic sharding protocol (referred to as "Asynchronous Iterative Routing"), which facilitates a direct and asynchronous communication among all client nodes and thereby completely avoids the overhead induced by the control flow with a master node that may otherwise form a performance bottleneck. Our experiments over a variety of benchmark settings confirm that AIR outperforms Spark and Flink in terms of latency and throughput by a factor of up to 15; moreover, we demonstrate that AIR scales out much better than existing DSPSs to clusters consisting of up to 8 nodes and 224 cores.