OpenRaiser/Intern-Atlas huggingface dataset:
High Performance Evaluation of Helmholtz Potentials using the Multi-Level Fast Multipole Algorithm
Venue: arXiv cs.DC 2020
Year: 2020

Evaluation of pair potentials is critical in a number of areas of physics. The classicalN-body problem has its root in evaluating the Laplace potential, and has spawned tree-algorithms, the fast multipole method (FMM), as well as kernel independent approaches. Over the years, FMM for Laplace potential has had a profound impact on a number of disciplines as it has been possible to develop highly scalable parallel algorithm for these potential evaluators. This is in stark contrast to parallel algorithms for the Helmholtz (oscillatory) potentials. The principal bottleneck to scalable parallelism are operations necessary to traverse up, across and down the tree, affecting both computation and communication. In this paper, we describe techniques to overcome bottlenecks and achieve high performance evaluation of the Helmholtz potential for a wide spectrum of geometries. We demonstrate that the resulting implementation has a load balancing effect that significantly reduces the time-to-solution and enhances the scale of problems that can be treated using full wave physics.
The Generalized Independent and Dominating Set Problems on Unit Disk Graphs
Venue: arXiv cs.DS 2020
Year: 2020

In this article, we study a generalized version of the maximum independent set and minimum dominating set problems, namely, the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem on unit disk graphs for a positive integer $d>0$. We first show that the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem belongs to NP-hard class. Next, we propose a simple polynomial-time constant-factor approximation algorithms and PTAS for both the problems.
Beneath (or beyond) the surface: Discovering voice-leading patterns with skip-grams
Venue: arXiv cs.SD 2020
Year: 2020

Recurrent voice-leading patterns like the Mi-Re-Do compound cadence (MRDCC) rarely appear on the musical surface in complex polyphonic textures, so finding these patterns using computational methods remains a tremendous challenge. The present study extends the canonical n-gram approach by using skip-grams, which include sub-sequences in an n-gram list if their constituent members occur within a certain number of skips. We compiled four data sets of Western tonal music consisting of symbolic encodings of the notated score and a recorded performance, created a model pipeline for defining, counting, filtering, and ranking skip-grams, and ranked the position of the MRDCC in every possible model configuration. We found that the MRDCC receives a higher rank in the list when the pipeline employs 5 skips, filters the list by excluding n-gram types that do not reflect a genuine harmonic change between adjacent members, and ranks the remaining types using a statistical association measure.
String-based methods for tonal harmony: A corpus study of Haydn's string quartets
Venue: arXiv cs.CL 2020
Year: 2020

This chapter considers how string-based methods might be adapted to address music-analytic questions related to the discovery of musical organization, with particular attention devoted to the analysis of tonal harmony. I begin by applying the taxonomy of mental organization proposed by Mandler (1979) to the concept of musical organization. Using this taxonomy as a guide, I then present evidence for three principles of tonal harmony -- recurrence, syntax, and recursion -- using a corpus of Haydn string quartets.
Mind The Facts: Knowledge-Boosted Coherent Abstractive Text Summarization
Venue: arXiv cs.CL 2020
Year: 2020

Neural models have become successful at producing abstractive summaries that are human-readable and fluent. However, these models have two critical shortcomings: they often don't respect the facts that are either included in the source article or are known to humans as commonsense knowledge, and they don't produce coherent summaries when the source article is long. In this work, we propose a novel architecture that extends Transformer encoder-decoder architecture in order to improve on these shortcomings. First, we incorporate entity-level knowledge from the Wikidata knowledge graph into the encoder-decoder architecture. Injecting structural world knowledge from Wikidata helps our abstractive summarization model to be more fact-aware. Second, we utilize the ideas used in Transformer-XL language model in our proposed encoder-decoder architecture. This helps our model with producing coherent summaries even when the source article is long. We test our model on CNN/Daily Mail summarization dataset and show improvements on ROUGE scores over the baseline Transformer model. We also include model predictions for which our model accurately conveys the facts, while the baseline Transformer model doesn't.
RepBERT: Contextualized Text Embeddings for First-Stage Retrieval
Venue: arXiv cs.IR 2020
Year: 2020

Although exact term match between queries and documents is the dominant method to perform first-stage retrieval, we propose a different approach, called RepBERT, to represent documents and queries with fixed-length contextualized embeddings. The inner products of query and document embeddings are regarded as relevance scores. On MS MARCO Passage Ranking task, RepBERT achieves state-of-the-art results among all initial retrieval techniques. And its efficiency is comparable to bag-of-words methods.
Task-driven Perception and Manipulation for Constrained Placement of Unknown Objects
Venue: arXiv cs.RO 2020
Year: 2020

Recent progress in robotic manipulation has dealt with the case of previously unknown objects in the context of relatively simple tasks, such as bin-picking. Existing methods for more constrained problems, however, such as deliberate placement in a tight region, depend more critically on shape information to achieve safe execution. This work deals with pick-and-constrained placement of objects without access to geometric models. The objective is to pick an object and place it safely inside a desired goal region without any collisions, while minimizing the time and the sensing operations required to complete the task. An algorithmic framework is proposed for this purpose, which performs manipulation planning simultaneously over a conservative and an optimistic estimate of the object's volume. The conservative estimate ensures that the manipulation is safe while the optimistic estimate guides the sensor-based manipulation process when no solution can be found for the conservative estimate. To maintain these estimates and dynamically update them during manipulation, objects are represented by a simple volumetric representation, which stores sets of occupied and unseen voxels. The effectiveness of the proposed approach is demonstrated by developing a robotic system that picks a previously unseen object from a table-top and places it in a constrained space. The system comprises of a dual-arm manipulator with heterogeneous end-effectors and leverages hand-offs as a re-grasping strategy. Real-world experiments show that straightforward pick-sense-and-place alternatives frequently fail to solve pick-and-constrained placement problems. The proposed pipeline, however, achieves more than 95% success rate and faster execution times as evaluated over multiple physical experiments.
A Multilevel Approach to Training
Venue: arXiv cs.LG 2020
Year: 2020

We propose a novel training method based on nonlinear multilevel minimization techniques, commonly used for solving discretized large scale partial differential equations. Our multilevel training method constructs a multilevel hierarchy by reducing the number of samples. The training of the original model is then enhanced by internally training surrogate models constructed with fewer samples. We construct the surrogate models using first-order consistency approach. This gives rise to surrogate models, whose gradients are stochastic estimators of the full gradient, but with reduced variance compared to standard stochastic gradient estimators. We illustrate the convergence behavior of the proposed multilevel method to machine learning applications based on logistic regression. A comparison with subsampled Newton's and variance reduction methods demonstrate the efficiency of our multilevel method.
Analogical Image Translation for Fog Generation
Venue: arXiv cs.CV 2020
Year: 2020

Image-to-image translation is to map images from a given \emph{style} to another given \emph{style}. While exceptionally successful, current methods assume the availability of training images in both source and target domains, which does not always hold in practice. Inspired by humans' reasoning capability of analogy, we propose analogical image translation (AIT). Given images of two styles in the source domain: $\mathcal{A}$ and $\mathcal{A}^\prime$, along with images $\mathcal{B}$ of the first style in the target domain, learn a model to translate $\mathcal{B}$ to $\mathcal{B}^\prime$ in the target domain, such that $\mathcal{A}:\mathcal{A}^\prime ::\mathcal{B}:\mathcal{B}^\prime$. AIT is especially useful for translation scenarios in which training data of one style is hard to obtain but training data of the same two styles in another domain is available. For instance, in the case from normal conditions to extreme, rare conditions, obtaining real training images for the latter case is challenging but obtaining synthetic data for both cases is relatively easy. In this work, we are interested in adding adverse weather effects, more specifically fog effects, to images taken in clear weather. To circumvent the challenge of collecting real foggy images, AIT learns with synthetic clear-weather images, synthetic foggy images and real clear-weather images to add fog effects onto real clear-weather images without seeing any real foggy images during training. AIT achieves this zero-shot image translation capability by coupling a supervised training scheme in the synthetic domain, a cycle consistency strategy in the real domain, an adversarial training scheme between the two domains, and a novel network design. Experiments show the effectiveness of our method for zero-short image translation and its benefit for downstream tasks such as semantic foggy scene understanding.
Deep Bayesian Quadrature Policy Optimization
Venue: arXiv cs.LG 2020
Year: 2020

We study the problem of obtaining accurate policy gradient estimates using a finite number of samples. Monte-Carlo methods have been the default choice for policy gradient estimation, despite suffering from high variance in the gradient estimates. On the other hand, more sample efficient alternatives like Bayesian quadrature methods have received little attention due to their high computational complexity. In this work, we propose deep Bayesian quadrature policy gradient (DBQPG), a computationally efficient high-dimensional generalization of Bayesian quadrature, for policy gradient estimation. We show that DBQPG can substitute Monte-Carlo estimation in policy gradient methods, and demonstrate its effectiveness on a set of continuous control benchmarks. In comparison to Monte-Carlo estimation, DBQPG provides (i) more accurate gradient estimates with a significantly lower variance, (ii) a consistent improvement in the sample complexity and average return for several deep policy gradient algorithms, and, (iii) the uncertainty in gradient estimation that can be incorporated to further improve the performance.
Optimal and Quantized Mechanism Design for Fresh Data Acquisition
Venue: arXiv cs.NI 2020
Year: 2020

The proliferation of real-time applications has spurred much interest in data freshness, captured by the {\it age-of-information} (AoI) metric. When strategic data sources have private market information, a fundamental economic challenge is how to incentivize them to acquire fresh data and optimize the age-related performance. In this work, we consider an information update system in which a destination acquires, and pays for, fresh data updates from multiple sources. The destination incurs an age-related cost, modeled as a general increasing function of the AoI. Each source is strategic and incurs a sampling cost, which is its private information and may not be truthfully reported to the destination. The destination decides on the price of updates, when to get them, and who should generate them, based on the sources' reported sampling costs. We show that a benchmark that naively trusts the sources' reports can lead to an arbitrarily bad outcome compared to the case where sources truthfully report. To tackle this issue, we design an optimal (economic) mechanism for timely information acquisition following Myerson's seminal work. To this end, our proposed optimal mechanism minimizes the sum of the destination's age-related cost and its payment to the sources, while ensuring that the sources truthfully report their private information and will voluntarily participate in the mechanism. However, finding the optimal mechanisms may suffer from \textit{prohibitively expensive computational overheads} as it involves solving a nonlinear infinite-dimensional optimization problem. We further propose a quantized version of the optimal mechanism that achieves asymptotic optimality, maintains the other economic properties, and enables one to tradeoff between optimality and computational overheads.
Empirically Verifying Hypotheses Using Reinforcement Learning
Venue: arXiv cs.AI 2020
Year: 2020

This paper formulates hypothesis verification as an RL problem. Specifically, we aim to build an agent that, given a hypothesis about the dynamics of the world, can take actions to generate observations which can help predict whether the hypothesis is true or false. Existing RL algorithms fail to solve this task, even for simple environments. In order to train the agents, we exploit the underlying structure of many hypotheses, factorizing them as {pre-condition, action sequence, post-condition} triplets. By leveraging this structure we show that RL agents are able to succeed at the task. Furthermore, subsequent fine-tuning of the policies allows the agent to correctly verify hypotheses not amenable to the above factorization.
Towards Learning-automation IoT Attack Detection through Reinforcement Learning
Venue: arXiv cs.CR 2020
Year: 2020

As a massive number of the Internet of Things (IoT) devices are deployed, the security and privacy issues in IoT arouse more and more attention. The IoT attacks are causing tremendous loss to the IoT networks and even threatening human safety. Compared to traditional networks, IoT networks have unique characteristics, which make the attack detection more challenging. First, the heterogeneity of platforms, protocols, software, and hardware exposes various vulnerabilities. Second, in addition to the traditional high-rate attacks, the low-rate attacks are also extensively used by IoT attackers to obfuscate the legitimate and malicious traffic. These low-rate attacks are challenging to detect and can persist in the networks. Last, the attackers are evolving to be more intelligent and can dynamically change their attack strategies based on the environment feedback to avoid being detected, making it more challenging for the defender to discover a consistent pattern to identify the attack. In order to adapt to the new characteristics in IoT attacks, we propose a reinforcement learning-based attack detection model that can automatically learn and recognize the transformation of the attack pattern. Therefore, we can continuously detect IoT attacks with less human intervention. In this paper, we explore the crucial features of IoT traffics and utilize the entropy-based metrics to detect both the high-rate and low-rate IoT attacks. Afterward, we leverage the reinforcement learning technique to continuously adjust the attack detection threshold based on the detection feedback, which optimizes the detection and the false alarm rate. We conduct extensive experiments over a real IoT attack dataset and demonstrate the effectiveness of our IoT attack detection framework.
Resilience Bounds of Network Clock Synchronization with Fault Correction
Venue: arXiv cs.NI 2020
Year: 2020

The Internet of Things (IoT) will be a main data generation infrastructure for achieving better system intelligence. This paper considers the design and implementation of a practical privacy-preserving collaborative learning scheme, in which a curious learning coordinator trains a better machine learning model based on the data samples contributed by a number of IoT objects, while the confidentiality of the raw forms of the training data is protected against the coordinator. Existing distributed machine learning and data encryption approaches incur significant computation and communication overhead, rendering them ill-suited for resource-constrained IoT objects. We study an approach that applies independent random projection at each IoT object to obfuscate data and trains a deep neural network at the coordinator based on the projected data from the IoT objects. This approach introduces light computation overhead to the IoT objects and moves most workload to the coordinator that can have sufficient computing resources. Although the independent projections performed by the IoT objects address the potential collusion between the curious coordinator and some compromised IoT objects, they significantly increase the complexity of the projected data. In this paper, we leverage the superior learning capability of deep learning in capturing sophisticated patterns to maintain good learning performance. Extensive comparative evaluation shows that this approach outperforms other lightweight approaches that apply additive noisification for differential privacy and/or support vector machines for learning in the applications with light to moderate data pattern complexities.
A Framework for Pre-processing of Social Media Feeds based on Integrated Local Knowledge Base
Venue: arXiv cs.CL 2020
Year: 2020

Most of the previous studies on the semantic analysis of social media feeds have not considered the issue of ambiguity that is associated with slangs, abbreviations, and acronyms that are embedded in social media posts. These noisy terms have implicit meanings and form part of the rich semantic context that must be analysed to gain complete insights from social media feeds. This paper proposes an improved framework for pre-processing of social media feeds for better performance. To do this, the use of an integrated knowledge base (ikb) which comprises a local knowledge source (Naijalingo), urban dictionary and internet slang was combined with the adapted Lesk algorithm to facilitate semantic analysis of social media feeds. Experimental results showed that the proposed approach performed better than existing methods when it was tested on three machine learning models, which are support vector machines, multilayer perceptron, and convolutional neural networks. The framework had an accuracy of 94.07% on a standardized dataset, and 99.78% on localised dataset when used to extract sentiments from tweets. The improved performance on the localised dataset reveals the advantage of integrating the use of local knowledge sources into the process of analysing social media feeds particularly in interpreting slangs/acronyms/abbreviations that have contextually rooted meanings.
Multi-armed bandit approach to password guessing
Venue: arXiv cs.CR 2020
Year: 2020

The multi-armed bandit is a mathematical interpretation of the problem a gambler faces when confronted with a number of different machines (bandits). The gambler wants to explore different machines to discover which machine offers the best rewards, but simultaneously wants to exploit the most profitable machine. A password guesser is faced with a similar dilemma. They have lists of leaked password sets, dictionaries of words, and demographic information about the users, but they don't know which dictionary will reap the best rewards. In this paper we provide a framework for using the multi-armed bandit problem in the context of the password guesser and use some examples to show that it can be effective.
Most Competitive Mechanisms in Online Fair Division
Venue: arXiv cs.GT 2020
Year: 2020

This paper combines two key ingredients for online algorithms - competitive analysis (e.g. the competitive ratio) and advice complexity (e.g. the number of advice bits needed to improve online decisions) - in the context of a simple online fair division model where items arrive one by one and are allocated to agents via some mechanism. We consider four such online mechanisms: the popular Ranking matching mechanism adapted from online bipartite matching and the Like, Balanced Like and Maximum Like allocation mechanisms firstly introduced for online fair division problems. Our first contribution is that we perform a competitive analysis of these mechanisms with respect to the expected size of the matching, the utilitarian welfare, and the egalitarian welfare. We also suppose that an oracle can give a number of advice bits to the mechanisms. Our second contribution is to give several impossibility results; e.g. no mechanism can achieve the egalitarian outcome of the optimal offline mechanism supposing they receive partial advice from the oracle. Our third contribution is that we quantify the competitive performance of these four mechanisms w.r.t. the number of oracle requests they can make. We thus present a most-competitive mechanism for each objective.
Is Japanese gendered language used on Twitter ? A large scale study
Venue: arXiv cs.CL 2020
Year: 2020

This study analyzes the usage of Japanese gendered language on Twitter. Starting from a collection of 408 million Japanese tweets from 2015 till 2019 and an additional sample of 2355 manually classified Twitter accounts timelines into gender and categories (politicians, musicians, etc). A large scale textual analysis is performed on this corpus to identify and examine sentence-final particles (SFPs) and first-person pronouns appearing in the texts. It turns out that gendered language is in fact used also on Twitter, in about 6% of the tweets, and that the prescriptive classification into "male" and "female" language does not always meet the expectations, with remarkable exceptions. Further, SFPs and pronouns show increasing or decreasing trends, indicating an evolution of the language used on Twitter.
Robots and COVID-19: Challenges in integrating robots for collaborative automation
Venue: arXiv cs.RO 2020
Year: 2020

Objective: The status of human-robot collaboration for assembly applications is reviewed and key current challenges for the research community and practitioners are presented. Background: As the pandemic of COVID-19 started to surface the manufacturers went under pressure to address demand challenges. Social distancing measures made fewer people available to work. In such situations, robots were pointed at to support humans to address a shortage in supply. An important activity where humans are needed in a manufacturing value chain is assembly. HRC assembly systems are supposed to safeguard coexisting humans, perform a range of actions, and often need to be reconfigured to handle product variety. This requires them to be resilient and adaptable to various configurations during their operational life. Besides the potential advantages of using robots the challenges of using them in an industrial assembly are enormous. Methods: This mini-review summarizes the challenges of industrial deployment of collaborative robots for assembly applications. Applications: The documented challenges highlight the future research directions in human-robot interaction for industrial applications.