OpenRaiser/Intern-Atlas huggingface dataset:
Bundled References: An Abstraction for Highly-Concurrent Linearizable Range Queries
Venue: arXiv cs.DS 2020
Year: 2020

We present bundled references, a new building block to provide linearizable range query operations for highly concurrent linked data structures. Bundled references allow range queries to traverse a path through the data structure that is consistent with the target atomic snapshot and is made of the minimal amount of nodes that should be accessed to preserve linearizability. We implement our technique into a skip list, a binary search tree, and a linked list data structure. Our evaluation reveals that in mixed workloads, our design improves upon the state-of-the-art techniques by 3.9x for a skip list and 2.1x for a binary search tree. We also integrate our bundled data structure into the DBx1000 in-memory database, yielding up to 20% gain over the same competitors.
CADA: Communication-Adaptive Distributed Adam
Venue: arXiv cs.LG 2020
Year: 2020

Stochastic gradient descent (SGD) has taken the stage as the primary workhorse for large-scale machine learning. It is often used with its adaptive variants such as AdaGrad, Adam, and AMSGrad. This paper proposes an adaptive stochastic gradient descent method for distributed machine learning, which can be viewed as the communication-adaptive counterpart of the celebrated Adam method - justifying its name CADA. The key components of CADA are a set of new rules tailored for adaptive stochastic gradients that can be implemented to save communication upload. The new algorithms adaptively reuse the stale Adam gradients, thus saving communication, and still have convergence rates comparable to original Adam. In numerical experiments, CADA achieves impressive empirical performance in terms of total communication round reduction.
Multi-Agent Reinforcement Learning for Unmanned Aerial Vehicle Coordination by Multi-Critic Policy Gradient Optimization
Venue: arXiv cs.RO 2020
Year: 2020

Recent technological progress in the development of Unmanned Aerial Vehicles (UAVs) together with decreasing acquisition costs make the application of drone fleets attractive for a wide variety of tasks. In agriculture, disaster management, search and rescue operations, commercial and military applications, the advantage of applying a fleet of drones originates from their ability to cooperate autonomously. Multi-Agent Reinforcement Learning approaches that aim to optimize a neural network based control policy, such as the best performing actor-critic policy gradient algorithms, struggle to effectively back-propagate errors of distinct rewards signal sources and tend to favor lucrative signals while neglecting coordination and exploitation of previously learned similarities. We propose a Multi-Critic Policy Optimization architecture with multiple value estimating networks and a novel advantage function that optimizes a stochastic actor policy network to achieve optimal coordination of agents. Consequently, we apply the algorithm to several tasks that require the collaboration of multiple drones in a physics-based reinforcement learning environment. Our approach achieves a stable policy network update and similarity in reward signal development for an increasing number of agents. The resulting policy achieves optimal coordination and compliance with constraints such as collision avoidance.
FiD-Ex: Improving Sequence-to-Sequence Models for Extractive Rationale Generation
Venue: arXiv cs.CL 2020
Year: 2020

Natural language (NL) explanations of model predictions are gaining popularity as a means to understand and verify decisions made by large black-box pre-trained models, for NLP tasks such as Question Answering (QA) and Fact Verification. Recently, pre-trained sequence to sequence (seq2seq) models have proven to be very effective in jointly making predictions, as well as generating NL explanations. However, these models have many shortcomings; they can fabricate explanations even for incorrect predictions, they are difficult to adapt to long input documents, and their training requires a large amount of labeled data. In this paper, we develop FiD-Ex, which addresses these shortcomings for seq2seq models by: 1) introducing sentence markers to eliminate explanation fabrication by encouraging extractive generation, 2) using the fusion-in-decoder architecture to handle long input contexts, and 3) intermediate fine-tuning on re-structured open domain QA datasets to improve few-shot performance. FiD-Ex significantly improves over prior work in terms of explanation metrics and task accuracy, on multiple tasks from the ERASER explainability benchmark, both in the fully supervised and in the few-shot settings.
XLM-T: Scaling up Multilingual Machine Translation with Pretrained Cross-lingual Transformer Encoders
Venue: arXiv cs.CL 2020
Year: 2020

Multilingual machine translation enables a single model to translate between different languages. Most existing multilingual machine translation systems adopt a randomly initialized Transformer backbone. In this work, inspired by the recent success of language model pre-training, we present XLM-T, which initializes the model with an off-the-shelf pretrained cross-lingual Transformer encoder and fine-tunes it with multilingual parallel data. This simple method achieves significant improvements on a WMT dataset with 10 language pairs and the OPUS-100 corpus with 94 pairs. Surprisingly, the method is also effective even upon the strong baseline with back-translation. Moreover, extensive analysis of XLM-T on unsupervised syntactic parsing, word alignment, and multilingual classification explains its effectiveness for machine translation. The code will be at https://aka.ms/xlm-t.
Autonomous Maintenance in IoT Networks via AoI-driven Deep Reinforcement Learning
Venue: arXiv cs.NI 2020
Year: 2020

Internet of Things (IoT) with its growing number of deployed devices and applications raises significant challenges for network maintenance procedures. In this work, we formulate a problem of autonomous maintenance in IoT networks as a Partially Observable Markov Decision Process. Subsequently, we utilize Deep Reinforcement Learning algorithms (DRL) to train agents that decide if a maintenance procedure is in order or not and, in the former case, the proper type of maintenance needed. To avoid wasting the scarce resources of IoT networks we utilize the Age of Information (AoI) metric as a reward signal for the training of the smart agents. AoI captures the freshness of the sensory data which are transmitted by the IoT sensors as part of their normal service provision. Numerical results indicate that AoI integrates enough information about the past and present states of the system to be successfully used in the training of smart agents for the autonomous maintenance of the network.
Refined Nonlinear Rectenna Modeling and Optimal Waveform Design for Multi-User Multi-Antenna Wireless Power Transfer
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we study the optimal waveform design for wireless power transfer (WPT) from a multi-antenna energy transmitter (ET) to multiple single-antenna energy receivers (ERs) simultaneously in multi-path frequency-selective channels. First, we propose a refined nonlinear current-voltage model of the diode in the ER rectifier, and accordingly derive new expressions for the output direct current (DC) voltage and corresponding harvested power at the ER. Leveraging this new rectenna model, we first consider the single-ER case and study the multisine-based power waveform design based on the wireless channel to maximize the harvested power at the ER. We propose two efficient algorithms for finding high-quality suboptimal solutions to this non-convex optimization problem. Next, we extend our formulated waveform design problem to the general multi-ER case for maximizing the weighted sum of the harvested powers by all ERs, and propose an efficient difference-of-convex functions programming (DCP)-based algorithm for solving this problem. Finally, we demonstrate the superior performance of our proposed waveform designs based on the new rectenna model over existing schemes/models via simulations.
FILO: FIx-LOcus Localization for Backward Incompatibilities Caused by Android Framework Upgrades
Venue: arXiv cs.SE 2020
Year: 2020

Mobile operating systems evolve quickly, frequently updating the APIs that app developers use to build their apps. Unfortunately, API updates do not always guarantee backward compatibility, causing apps to not longer work properly or even crash when running with an updated system. This paper presents FILO, a tool that assists Android developers in resolving backward compatibility issues introduced by API upgrades. FILO both suggests the method that needs to be modified in the app in order to adapt the app to an upgraded API, and reports key symptoms observed in the failed execution to facilitate the fixing activity. Results obtained with the analysis of 12 actual upgrade problems and the feedback produced by early tool adopters show that FILO can practically support Android developers.FILO can be downloaded from https://gitlab.com/learnERC/filo, and its video demonstration is available at https://youtu.be/WDvkKj-wnlQ.
Leveraging Audio Gestalt to Predict Media Memorability
Venue: arXiv cs.MM 2020
Year: 2020

Memorability determines what evanesces into emptiness, and what worms its way into the deepest furrows of our minds. It is the key to curating more meaningful media content as we wade through daily digital torrents. The Predicting Media Memorability task in MediaEval 2020 aims to address the question of media memorability by setting the task of automatically predicting video memorability. Our approach is a multimodal deep learning-based late fusion that combines visual, semantic, and auditory features. We used audio gestalt to estimate the influence of the audio modality on overall video memorability, and accordingly inform which combination of features would best predict a given video's memorability scores.
Exploiting Transitivity for Top-k Selection with Score-Based Dueling Bandits
Venue: arXiv cs.LG 2020
Year: 2020

We consider the problem of top-k subset selection in Dueling Bandit problems with score information. Real-world pairwise ranking problems often exhibit a high degree of transitivity and prior work has suggested sampling methods that exploit such transitivity through the use of parametric preference models like the Bradley-Terry-Luce (BTL) and Thurstone models. To date, this work has focused on cases where sample outcomes are win/loss binary responses. We extend this to selection problems where sampling results contain quantitative information by proposing a Thurstonian style model and adapting the Pairwise Optimal Computing Budget Allocation for subset selection (POCBAm) sampling method to exploit this model for efficient sample selection. We compare the empirical performance against standard POCBAm and other competing algorithms.
NeuralMagicEye: Learning to See and Understand the Scene Behind an Autostereogram
Venue: arXiv cs.CV 2020
Year: 2020

An autostereogram, a.k.a. magic eye image, is a single-image stereogram that can create visual illusions of 3D scenes from 2D textures. This paper studies an interesting question that whether a deep CNN can be trained to recover the depth behind an autostereogram and understand its content. The key to the autostereogram magic lies in the stereopsis - to solve such a problem, a model has to learn to discover and estimate disparity from the quasi-periodic textures. We show that deep CNNs embedded with disparity convolution, a novel convolutional layer proposed in this paper that simulates stereopsis and encodes disparity, can nicely solve such a problem after being sufficiently trained on a large 3D object dataset in a self-supervised fashion. We refer to our method as ``NeuralMagicEye''. Experiments show that our method can accurately recover the depth behind autostereograms with rich details and gradient smoothness. Experiments also show the completely different working mechanisms for autostereogram perception between neural networks and human eyes. We hope this research can help people with visual impairments and those who have trouble viewing autostereograms. Our code is available at \url{https://jiupinjia.github.io/neuralmagiceye/}.
Real-time Webcam Heart-Rate and Variability Estimation with Clean Ground Truth for Evaluation
Venue: arXiv cs.CV 2020
Year: 2020

Remote photo-plethysmography (rPPG) uses a camera to estimate a person's heart rate (HR). Similar to how heart rate can provide useful information about a person's vital signs, insights about the underlying physio/psychological conditions can be obtained from heart rate variability (HRV). HRV is a measure of the fine fluctuations in the intervals between heart beats. However, this measure requires temporally locating heart beats with a high degree of precision. We introduce a refined and efficient real-time rPPG pipeline with novel filtering and motion suppression that not only estimates heart rates, but also extracts the pulse waveform to time heart beats and measure heart rate variability. This unsupervised method requires no rPPG specific training and is able to operate in real-time. We also introduce a new multi-modal video dataset, VicarPPG 2, specifically designed to evaluate rPPG algorithms on HR and HRV estimation. We validate and study our method under various conditions on a comprehensive range of public and self-recorded datasets, showing state-of-the-art results and providing useful insights into some unique aspects. Lastly, we make available CleanerPPG, a collection of human-verified ground truth peak/heart-beat annotations for existing rPPG datasets. These verified annotations should make future evaluations and benchmarking of rPPG algorithms more accurate, standardized and fair.
Exploration of Voice User Interfaces for Older Adults - A Pilot Study to Address Progressive Vision Loss
Venue: arXiv cs.HC 2020
Year: 2020

Voice User Interfaces (VUIs) owing to recent developments in Artificial Intelligence (AI) and Natural Language Processing (NLP), are becoming increasingly intuitive and functional. They are especially promising for older adults, also with special needs, as VUIs remove some barriers related to access to Information and Communications Technology (ICT) solutions. In this pilot study we examine interdisciplinary opportunities in the area of VUIs as assistive technologies, based on an exploratory study with older adults, and a follow-up in-depth pilot study with two participants regarding the needs of people who are gradually losing their sight at a later age.
Encoding sinusoidal functions in hybrid automata formalism
Venue: arXiv cs.FL 2020
Year: 2020

Hybrid systems can express a plethora of physical phenomena and systems as they can combine continuous and discrete dynamics. There exist several tools that enable the reachability analysis of hybrid systems modeled as hybrid automata. However, these tools exhibit certain limitations in the type of mathematical operations that they natively support. For example, SpaceEx, a well-established tool in the hybrid verification community, supports the use of linear ODEs in the flow of each discrete location. Mathematical functions like algebraic equations or trigonometric functions have to be encoded as the solutions of a set of ODEs. In this article, we provide a mechanism to define sinusoidal functions that are supported by SpaceEx. We also show how certain Simulink blocks can be translated into hybrid automata.
Consensus with Bounded Space and Minimal Communication
Venue: arXiv cs.DC 2020
Year: 2020

Population protocols are a fundamental model in distributed computing, where many nodes with bounded memory and computational power have random pairwise interactions over time. This model has been studied in a rich body of literature aiming to understand the tradeoffs between the memory and time needed to perform computational tasks. We study the population protocol model focusing on the communication complexity needed to achieve consensus with high probability. When the number of memory states is $s = O(\log \log{n})$, the best upper bound known was given by a protocol with $O(n \log{n})$ communication, while the best lower bound was $Ω(n \log(n)/s)$ communication. We design a protocol that shows the lower bound is sharp. When each agent has $s=O(\log{n}^θ)$ states of memory, with $θ\in (0,1/2)$, consensus can be reached in time $O(\log(n))$ with $O(n \log{(n)}/s)$ communications with high probability.
Data Criticality in Multi-Threaded Applications: An Insight for Many-Core Systems
Venue: arXiv cs.AR 2020
Year: 2020

Multi-threaded applications are capable of exploiting the full potential of many-core systems. However, Network-on-Chip (NoC) based inter-core communication in many-core systems is responsible for 60-75% of the miss latency experienced by multi-threaded applications. Delay in the arrival of critical data at the requesting core severely hampers performance. This brief presents some interesting insights about how critical data is requested from the memory by multi-threaded applications. Then it investigates the cause of delay in NoC and how it affects the performance. Finally, this brief shows how NoC-aware memory access optimisations can significantly improve performance. Our experimental evaluation considers early restart memory access optimisation and demonstrates that by exploiting NoC resources, critical data can be prioritised to reduce miss penalty by 10-12% and improve system performance by 7-11%.
calculus: High Dimensional Numerical and Symbolic Calculus in R
Venue: arXiv cs.MS 2020
Year: 2020

The R package calculus implements C++ optimized functions for numerical and symbolic calculus, such as the Einstein summing convention, fast computation of the Levi-Civita symbol and generalized Kronecker delta, Taylor series expansion, multivariate Hermite polynomials, high-order derivatives, ordinary differential equations, differential operators and numerical integration in arbitrary orthogonal coordinate systems. The library applies numerical methods when working with R functions or symbolic programming when working with characters or expressions. The package handles multivariate numerical calculus in arbitrary dimensions and coordinates and implements the symbolic counterpart of the numerical methods whenever possible, without depending on external computer algebra systems. Except for Rcpp, the package has no strict dependencies in order to provide a stable self-contained toolbox that invites re-use.
OralViewer: 3D Demonstration of Dental Surgeries for Patient Education with Oral Cavity Reconstruction from a 2D Panoramic X-ray
Venue: arXiv cs.HC 2020
Year: 2020

Patient's understanding on forthcoming dental surgeries is required by patient-centered care and helps reduce fear and anxiety. Due to the gap of expertise between patients and dentists, conventional techniques of patient education are usually not effective for explaining surgical steps. In this paper, we present \textit{OralViewer} -- the first interactive application that enables dentist's demonstration of dental surgeries in 3D to promote patients' understanding. \textit{OralViewer} takes a single 2D panoramic dental X-ray to reconstruct patient-specific 3D teeth structures, which are then assembled with registered gum and jaw bone models for complete oral cavity modeling. During the demonstration, \textit{OralViewer} enables dentists to show surgery steps with virtual dental instruments that can animate effects on a 3D model in real-time. A technical evaluation shows our deep learning based model achieves a mean Intersection over Union (IoU) of 0.771 for 3D teeth reconstruction. A patient study with 12 participants shows \textit{OralViewer} can improve patients' understanding of surgeries. An expert study with 3 board-certified dentists further verifies the clinical validity of our system.
Scalable Online Conformance Checking Using Incremental Prefix-Alignment Computation
Venue: arXiv cs.LO 2020
Year: 2020

Conformance checking techniques aim to collate observed process behavior with normative/modeled process models. The majority of existing approaches focuses on completed process executions, i.e., offline conformance checking. Recently, novel approaches have been designed to monitor ongoing processes, i.e., online conformance checking. Such techniques detect deviations of an ongoing process execution from a normative process model at the moment they occur. Thereby, countermeasures can be taken immediately to prevent a process deviation from causing further, undesired consequences. Most online approaches only allow to detect approximations of deviations. This causes the problem of falsely detected deviations, i.e., detected deviations that are actually no deviations. We have, therefore, recently introduced a novel approach to compute exact conformance checking results in an online environment. In this paper, we focus on the practical application and present a scalable, distributed implementation of the proposed online conformance checking approach. Moreover, we present two extensions to said approach to reduce its computational effort and its practical applicability. We evaluate our implementation using data sets capturing the execution of real processes.
Understanding Power Consumption and Reliability of High-Bandwidth Memory with Voltage Underscaling
Venue: arXiv cs.AR 2020
Year: 2020

Modern computing devices employ High-Bandwidth Memory (HBM) to meet their memory bandwidth requirements. An HBM-enabled device consists of multiple DRAM layers stacked on top of one another next to a compute chip (e.g. CPU, GPU, and FPGA) in the same package. Although such HBM structures provide high bandwidth at a small form factor, the stacked memory layers consume a substantial portion of the package's power budget. Therefore, power-saving techniques that preserve the performance of HBM are desirable. Undervolting is one such technique: it reduces the supply voltage to decrease power consumption without reducing the device's operating frequency to avoid performance loss. Undervolting takes advantage of voltage guardbands put in place by manufacturers to ensure correct operation under all environmental conditions. However, reducing voltage without changing frequency can lead to reliability issues manifested as unwanted bit flips. In this paper, we provide the first experimental study of real HBM chips under reduced-voltage conditions. We show that the guardband regions for our HBM chips constitute 19% of the nominal voltage. Pushing the supply voltage down within the guardband region reduces power consumption by a factor of 1.5X for all bandwidth utilization rates. Pushing the voltage down further by 11% leads to a total of2.3X power savings at the cost of unwanted bit flips. We explore and characterize the rate and types of these reduced-voltage-induced bit flips and present a fault map that enables the possibility of a three-factor trade-off among power, memory capacity, and fault rate.
Additive Link Metrics Identification: Proof of Selected Lemmas and Propositions
Venue: arXiv cs.NI 2020
Year: 2020

This is a technical report, containing all the lemma and proposition proofs in paper "Topological Constraints on Identifying Additive Link Metrics via End-to-end Paths Measurements" by Liang Ma, Ting He, Kin K. Leung, Don Towsley, and Ananthram Swami, published in Annual Conference of The International Technology Alliance (ACITA), 2012.