OpenRaiser/Intern-Atlas huggingface dataset:
Neural Relation Prediction for Simple Question Answering over Knowledge Graph
Venue: arXiv cs.CL 2020
Year: 2020

Knowledge graphs are widely used as a typical resource to provide answers to factoid questions. In simple question answering over knowledge graphs, relation extraction aims to predict the relation of a factoid question from a set of predefined relation types. Most recent methods take advantage of neural networks to match a question with all predefined relations. In this paper, we propose an instance-based method to capture the underlying relation of question and to this aim, we detect matching paraphrases of a new question which share the same relation, and their corresponding relation is selected as our prediction. The idea of our model roots in the fact that a relation can be expressed with various forms of questions while these forms share lexically or semantically similar terms and concepts. Our experiments on the SimpleQuestions dataset show that the proposed model achieves better accuracy compared to the state-of-the-art relation extraction models.
Artificial Intelligent Ethics in the Digital Era: an Engineering Ethical Framework Proposal
Venue: arXiv cs.CY 2020
Year: 2020

Nowadays technology is being adopted on every aspect of our lives and it is one of most important transformation driver in industry. Moreover, many of the systems and digital services that we use daily rely on artificial intelligent technology capable of modeling social or individual behaviors that in turns also modify personal decisions and actions. In this paper, we briefly discuss, from a technological perspective, a number of critical issues including the purpose of promoting trust and ensure social benefit by the proper use of Artificial Intelligent Systems. To achieve this goal we propose a generic ethical technological framework as a first attempt to define a common context towards developing real engineering ethical by design. We hope that this initial proposal to be useful for early adopters and especially for standardization teams.
Traffic Prediction and Random Access Control Optimization: Learning and Non-learning based Approaches
Venue: arXiv cs.NI 2020
Year: 2020

Random access schemes in modern wireless communications are generally based on the framed-ALOHA (f-ALOHA), which can be optimized by flexibly organizing devices' transmission and re-transmission. However, this optimization is generally intractable due to the lack of information about complex traffic generation statistics and the occurrence of the random collision. In this article, we first summarize the general structure of access control optimization for different random access schemes, and then review the existing access control optimization based on Machine Learning (ML) and non-ML techniques. We demonstrate that the ML-based methods can better optimize the access control problem compared with non-ML based methods, due to their capability in solving high complexity long-term optimization problem and learning experiential knowledge from reality. To further improve the random access performance, we propose two-step learning optimizers for access control optimization, which individually execute the traffic prediction and the access control configuration. In detail, our traffic prediction method relies on online supervised learning adopting Recurrent Neural Networks (RNNs) that can accurately capture traffic statistics over consecutive frames, and the access control configuration can use either a non-ML based controller or a cooperatively trained Deep Reinforcement Learning (DRL) based controller depending on the complexity of different random access schemes. Numerical results show that the proposed two-step cooperative learning optimizer considerably outperforms the conventional Deep Q-Network (DQN) in terms of higher training efficiency and better access performance.
Computer classification of linear codes
Venue: arXiv cs.IT 2020
Year: 2020

We present algorithms for classification of linear codes over finite fields, based on canonical augmentation and on lattice point enumeration. We apply these algorithms to obtain classification results over fields with 2, 3 and 4 elements. We validate a correct implementation of the algorithms with known classification results from the literature, which we partially extend to larger ranges of parameters.
Cyberattack Action-Intent-Framework for Mapping Intrusion Observables
Venue: arXiv cs.CR 2020
Year: 2020

The techniques and tactics used by cyber adversaries are becoming more sophisticated, ironically, as defense getting stronger and the cost of a breach continuing to rise. Understanding the thought processes and behaviors of adversaries is extremely challenging as high profile or even amateur attackers have no incentive to share the trades associated with their illegal activities. One opportunity to observe the actions the adversaries perform is through the use of Intrusion Detection Systems (IDS) which generate alerts in the event that suspicious behavior was detected. The alerts raised by these systems typically describe the suspicious actions via the form of attack 'signature', which do not necessarily reveal the true intent of the attacker performing the action. Meanwhile, several high level frameworks exist to describe the sequence or chain of action types an adversary might perform. These frameworks, however, do not connect the action types to observables of standard intrusion detection systems, nor describing the plausible intents of the adversarial actions. To address these gaps, this work proposes the Action-Intent Framework (AIF) to complement existing Cyber Attack Kill Chains and Attack Taxonomies. The AIF defines a set of Action-Intent States (AIS) at two levels of description: the Macro-AIS describes 'what' the attacker is trying to achieve and the Micro-AIS describes "how" the intended goal is achieved. A full description of both the Macro is provided along with a set of guiding principals of how the AIS is derived and added to the framework.
Performance of a reconciliation method operating on a discreet quantum key distribution system
Venue: arXiv cs.CR 2020
Year: 2020

Reconciliation is a mechanism allowing to weed out the discrepancies between two correlated variables. It has great role in every Quantum Key Distribution protocol where the key has to be transmitted through a noisy channel or as in our case of study in presence of an eavesdropping. In this paper, we show that for discrete-variable QKD protocols, this problem can be advantageously solved with Turbo codes. In particular, we demonstrate that our method leads to a significant improvement of Bit Error Rate, may divide it by three in presence of a eavesdropper even with great eavesdropping capability.
Online Parameter Estimation for Safety-Critical Systems with Gaussian Processes
Venue: arXiv cs.RO 2020
Year: 2020

Parameter estimation is crucial for modeling, tracking, and control of complex dynamical systems. However, parameter uncertainties can compromise system performance under a controller relying on nominal parameter values. Typically, parameters are estimated using numerical regression approaches framed as inverse problems. However, they suffer from non-uniqueness due to existence of multiple local optima, reliance on gradients, numerous experimental data, or stability issues. Addressing these drawbacks, we present a Bayesian optimization framework based on Gaussian processes (GPs) for online parameter estimation. It uses an efficient search strategy over a response surface in the parameter space for finding the global optima with minimal function evaluations. The response surface is modeled as correlated surrogates using GPs on noisy data. The GP posterior predictive variance is exploited for smart adaptive sampling. This balances the exploration versus exploitation trade-off which is key in reaching the global optima under limited budget. We demonstrate our technique on an actuated planar pendulum and safety-critical quadrotor in simulation with changing parameters. We also benchmark our results against solvers using interior point method and sequential quadratic program. By reconfiguring the controller with new optimized parameters iteratively, we drastically improve trajectory tracking of the system versus the nominal case and other solvers.
Informative Path Planning for Mobile Sensing with Reinforcement Learning
Venue: arXiv cs.RO 2020
Year: 2020

Large-scale spatial data such as air quality, thermal conditions and location signatures play a vital role in a variety of applications. Collecting such data manually can be tedious and labour intensive. With the advancement of robotic technologies, it is feasible to automate such tasks using mobile robots with sensing and navigation capabilities. However, due to limited battery lifetime and scarcity of charging stations, it is important to plan paths for the robots that maximize the utility of data collection, also known as the informative path planning (IPP) problem. In this paper, we propose a novel IPP algorithm using reinforcement learning (RL). A constrained exploration and exploitation strategy is designed to address the unique challenges of IPP, and is shown to have fast convergence and better optimality than a classical reinforcement learning approach. Extensive experiments using real-world measurement data demonstrate that the proposed algorithm outperforms state-of-the-art algorithms in most test cases. Interestingly, unlike existing solutions that have to be re-executed when any input parameter changes, our RL-based solution allows a degree of transferability across different problem instances.
Block Switching: A Stochastic Approach for Deep Learning Security
Venue: arXiv cs.LG 2020
Year: 2020

Recent study of adversarial attacks has revealed the vulnerability of modern deep learning models. That is, subtly crafted perturbations of the input can make a trained network with high accuracy produce arbitrary incorrect predictions, while maintain imperceptible to human vision system. In this paper, we introduce Block Switching (BS), a defense strategy against adversarial attacks based on stochasticity. BS replaces a block of model layers with multiple parallel channels, and the active channel is randomly assigned in the run time hence unpredictable to the adversary. We show empirically that BS leads to a more dispersed input gradient distribution and superior defense effectiveness compared with other stochastic defenses such as stochastic activation pruning (SAP). Compared to other defenses, BS is also characterized by the following features: (i) BS causes less test accuracy drop; (ii) BS is attack-independent and (iii) BS is compatible with other defenses and can be used jointly with others.
Studying the Effects of Cognitive Biases in Evaluation of Conversational Agents
Venue: arXiv cs.CL 2020
Year: 2020

Humans quite frequently interact with conversational agents. The rapid advancement in generative language modeling through neural networks has helped advance the creation of intelligent conversational agents. Researchers typically evaluate the output of their models through crowdsourced judgments, but there are no established best practices for conducting such studies. Moreover, it is unclear if cognitive biases in decision-making are affecting crowdsourced workers' judgments when they undertake these tasks. To investigate, we conducted a between-subjects study with 77 crowdsourced workers to understand the role of cognitive biases, specifically anchoring bias, when humans are asked to evaluate the output of conversational agents. Our results provide insight into how best to evaluate conversational agents. We find increased consistency in ratings across two experimental conditions may be a result of anchoring bias. We also determine that external factors such as time and prior experience in similar tasks have effects on inter-rater consistency.
On the Planar Two-Center Problem and Circular Hulls
Venue: arXiv cs.CG 2020
Year: 2020

Given a set $S$ of $n$ points in the Euclidean plane, the two-center problem is to find two congruent disks of smallest radius whose union covers all points of $S$. Previously, Eppstein [SODA'97] gave a randomized algorithm of $O(n\log^2n)$ expected time and Chan [CGTA'99] presented a deterministic algorithm of $O(n\log^2 n\log^2\log n)$ time. In this paper, we propose an $O(n\log^2 n)$ time deterministic algorithm, which improves Chan's deterministic algorithm and matches the randomized bound of Eppstein. If $S$ is in convex position, then we solve the problem in $O(n\log n\log\log n)$ deterministic time. Our results rely on new techniques for dynamically maintaining circular hulls under point insertions and deletions, which are of independent interest.
SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra
Venue: arXiv cs.DB 2020
Year: 2020

Machine learning algorithms are commonly specified in linear algebra (LA). LA expressions can be rewritten into more efficient forms, by taking advantage of input properties such as sparsity, as well as program properties such as common subexpressions and fusible operators. The complex interaction among these properties' impact on the execution cost poses a challenge to optimizing compilers. Existing compilers resort to intricate heuristics that complicate the codebase and add maintenance cost but fail to search through the large space of equivalent LA expressions to find the cheapest one. We introduce a general optimization technique for LA expressions, by converting the LA expressions into Relational Algebra (RA) expressions, optimizing the latter, then converting the result back to (optimized) LA expressions. One major advantage of this method is that it is complete, meaning that any equivalent LA expression can be found using the equivalence rules in RA. The challenge is the major size of the search space, and we address this by adopting and extending a technique used in compilers, called equality saturation. We integrate the optimizer into SystemML and validate it empirically across a spectrum of machine learning tasks; we show that we can derive all existing hand-coded optimizations in SystemML, and perform new optimizations that lead to speedups from 1.2X to 5X.
Gradient Boosting Neural Networks: GrowNet
Venue: arXiv cs.LG 2020
Year: 2020

A novel gradient boosting framework is proposed where shallow neural networks are employed as ``weak learners''. General loss functions are considered under this unified framework with specific examples presented for classification, regression, and learning to rank. A fully corrective step is incorporated to remedy the pitfall of greedy function approximation of classic gradient boosting decision tree. The proposed model rendered outperforming results against state-of-the-art boosting methods in all three tasks on multiple datasets. An ablation study is performed to shed light on the effect of each model components and model hyperparameters.
The Microsoft Toolkit of Multi-Task Deep Neural Networks for Natural Language Understanding
Venue: arXiv cs.CL 2020
Year: 2020

We present MT-DNN, an open-source natural language understanding (NLU) toolkit that makes it easy for researchers and developers to train customized deep learning models. Built upon PyTorch and Transformers, MT-DNN is designed to facilitate rapid customization for a broad spectrum of NLU tasks, using a variety of objectives (classification, regression, structured prediction) and text encoders (e.g., RNNs, BERT, RoBERTa, UniLM). A unique feature of MT-DNN is its built-in support for robust and transferable learning using the adversarial multi-task learning paradigm. To enable efficient production deployment, MT-DNN supports multi-task knowledge distillation, which can substantially compress a deep neural model without significant performance drop. We demonstrate the effectiveness of MT-DNN on a wide range of NLU applications across general and biomedical domains. The software and pre-trained models will be publicly available at https://github.com/namisan/mt-dnn.
Best-item Learning in Random Utility Models with Subset Choices
Venue: arXiv cs.LG 2020
Year: 2020

We consider the problem of PAC learning the most valuable item from a pool of $n$ items using sequential, adaptively chosen plays of subsets of $k$ items, when, upon playing a subset, the learner receives relative feedback sampled according to a general Random Utility Model (RUM) with independent noise perturbations to the latent item utilities. We identify a new property of such a RUM, termed the minimum advantage, that helps in characterizing the complexity of separating pairs of items based on their relative win/loss empirical counts, and can be bounded as a function of the noise distribution alone. We give a learning algorithm for general RUMs, based on pairwise relative counts of items and hierarchical elimination, along with a new PAC sample complexity guarantee of $O(\frac{n}{c^2ε^2} \log \frac{k}δ)$ rounds to identify an $ε$-optimal item with confidence $1-δ$, when the worst case pairwise advantage in the RUM has sensitivity at least $c$ to the parameter gaps of items. Fundamental lower bounds on PAC sample complexity show that this is near-optimal in terms of its dependence on $n,k$ and $c$.
Fast and linear-time string matching algorithms based on the distances of $q$-gram occurrences
Venue: arXiv cs.DS 2020
Year: 2020

Given a text $T$ of length $n$ and a pattern $P$ of length $m$, the string matching problem is a task to find all occurrences of $P$ in $T$. In this study, we propose an algorithm that solves this problem in $O((n + m)q)$ time considering the distance between two adjacent occurrences of the same $q$-gram contained in $P$. We also propose a theoretical improvement of it which runs in $O(n + m)$ time, though it is not necessarily faster in practice. We compare the execution times of our and existing algorithms on various kinds of real and artificial datasets such as an English text, a genome sequence and a Fibonacci string. The experimental results show that our algorithm is as fast as the state-of-the-art algorithms in many cases, particularly when a pattern frequently appears in a text.
A Case for Humans-in-the-Loop: Decisions in the Presence of Erroneous Algorithmic Scores
Venue: arXiv cs.CY 2020
Year: 2020

The increased use of algorithmic predictions in sensitive domains has been accompanied by both enthusiasm and concern. To understand the opportunities and risks of these technologies, it is key to study how experts alter their decisions when using such tools. In this paper, we study the adoption of an algorithmic tool used to assist child maltreatment hotline screening decisions. We focus on the question: Are humans capable of identifying cases in which the machine is wrong, and of overriding those recommendations? We first show that humans do alter their behavior when the tool is deployed. Then, we show that humans are less likely to adhere to the machine's recommendation when the score displayed is an incorrect estimate of risk, even when overriding the recommendation requires supervisory approval. These results highlight the risks of full automation and the importance of designing decision pipelines that provide humans with autonomy.
Feasibility of Video-based Sub-meter Localization on Resource-constrained Platforms
Venue: arXiv cs.CV 2020
Year: 2020

While the satellite-based Global Positioning System (GPS) is adequate for some outdoor applications, many other applications are held back by its multi-meter positioning errors and poor indoor coverage. In this paper, we study the feasibility of real-time video-based localization on resource-constrained platforms. Before commencing a localization task, a video-based localization system downloads an offline model of a restricted target environment, such as a set of city streets, or an indoor shopping mall. The system is then able to localize the user within the model, using only video as input. To enable such a system to run on resource-constrained embedded systems or smartphones, we (a) propose techniques for efficiently building a 3D model of a surveyed path, through frame selection and efficient feature matching, (b) substantially reduce model size by multiple compression techniques, without sacrificing localization accuracy, (c) propose efficient and concurrent techniques for feature extraction and matching to enable online localization, (d) propose a method with interleaved feature matching and optical flow based tracking to reduce the feature extraction and matching time in online localization. Based on an extensive set of both indoor and outdoor videos, manually annotated with location ground truth, we demonstrate that sub-meter accuracy, at real-time rates, is achievable on smart-phone type platforms, despite challenging video conditions.
Translating Between Wavelet Tree and Wavelet Matrix Construction
Venue: arXiv cs.DS 2020
Year: 2020

The wavelet tree (Grossi et al. [SODA, 2003]) and wavelet matrix (Claude et al. [Inf. Syst., 2015]) are compact data structures with many applications such as text indexing or computational geometry. By continuing the recent research of Fischer et al. [ALENEX, 2018], we explore the similarities and differences of these heavily related data structures with focus on their construction. We develop a data structure to modify construction algorithms for either the wavelet tree or matrix to construct instead the other. This modification is efficient, in that it does not worsen the asymptotic time and space requirements of any known wavelet tree or wavelet matrix construction algorithm.
Performance Analysis of Single-Cell Adaptive Data Rate-Enabled LoRaWAN
Venue: arXiv cs.NI 2020
Year: 2020

LoRaWAN enables massive connectivity for Internet-of-Things applications. Many published works employ stochastic geometry to derive outage models of LoRaWAN over fading channels assuming fixed transmit power and distance-based spreading factor (SF) allocation. However, in practice, LoRaWAN employs the Adaptive Data Rate (ADR) mechanism, which dynamically adjusts SF and transmit power of nodes based on channel state. The community addressed the performance of ADR using simulations, but analytical models have not been introduced. In this letter, we seek to close this gap. We build over an analytical LoRaWAN model to consider the performance of steady-state ADR-enabled LoRaWAN. We derive outage expressions and an optimization procedure to maximize the number of users under reliability constraints. Results show that power allocation reduces interference and improves network capacity while reducing average power.
BB_Evac: Fast Location-Sensitive Behavior-Based Building Evacuation
Venue: arXiv cs.DM 2020
Year: 2020

Past work on evacuation planning assumes that evacuees will follow instructions -- however, there is ample evidence that this is not the case. While some people will follow instructions, others will follow their own desires. In this paper, we present a formal definition of a behavior-based evacuation problem (BBEP) in which a human behavior model is taken into account when planning an evacuation. We show that a specific form of constraints can be used to express such behaviors. We show that BBEPs can be solved exactly via an integer program called BB_IP, and inexactly by a much faster algorithm that we call BB_Evac. We conducted a detailed experimental evaluation of both algorithms applied to buildings (though in principle the algorithms can be applied to any graphs) and show that the latter is an order of magnitude faster than BB_IP while producing results that are almost as good on one real-world building graph and as well as on several synthetically generated graphs.