OpenRaiser/Intern-Atlas huggingface dataset:
Explicit construction of optimal locally recoverable codes of distance 5 and 6 via binary constant weight codes
Venue: arXiv cs.IT 2020
Year: 2020

It was shown in \cite{GXY18} that the length $n$ of a $q$-ary linear locally recoverable code with distance $d\ge 5$ is upper bounded by $O(dq^3)$. Thus, it is a challenging problem to construct $q$-ary locally recoverable codes with distance $d\ge 5$ and length approaching the upper bound. The paper \cite{GXY18} also gave an algorithmic construction of $q$-ary locally recoverable codes with locality $r$ and length $n=Ω_r(q^2)$ for $d=5$ and $6$, where $Ω_r$ means that the implicit constant depends on locality $r$. In the present paper, we present an explicit construction of $q$-ary locally recoverable codes of distance $d= 5$ and $6$ via binary constant weight codes. It turns out that (i) our construction is simpler and more explicit; and (ii) lengths of our codes are larger than those given in \cite{GXY18}.
An operational interpretation of coinductive types
Venue: arXiv cs.LO 2020
Year: 2020

We introduce an operational rewriting-based semantics for strictly positive nested higher-order (co)inductive types. The semantics takes into account the "limits" of infinite reduction sequences. This may be seen as a refinement and generalization of the notion of productivity in term rewriting to a setting with higher-order functions and with data specified by nested higher-order inductive and coinductive definitions. Intuitively, we interpret lazy data structures in a higher-order functional language by potentially infinite terms corresponding to their complete unfoldings. We prove an approximation theorem which essentially states that if a term reduces to an arbitrarily large finite approximation of an infinite object in the interpretation of a coinductive type, then it infinitarily (i.e. in the "limit") reduces to an infinite object in the interpretation of this type. We introduce a sufficient syntactic correctness criterion, in the form of a type system, for finite terms decorated with type information. Using the approximation theorem, we show that each well-typed term has a well-defined interpretation in our semantics.
Using SWISH to realise interactive web based tutorials for logic based languages
Venue: arXiv cs.PL 2020
Year: 2020

Programming environments have evolved from purely text based to using graphical user interfaces, and now we see a move towards web based interfaces, such as Jupyter. Web based interfaces allow for the creation of interactive documents that consist of text and programs, as well as their output. The output can be rendered using web technology as, e.g., text, tables, charts or graphs. This approach is particularly suitable for capturing data analysis workflows and creating interactive educational material. This article describes SWISH, a web front-end for Prolog that consists of a web server implemented in SWI-Prolog and a client web application written in JavaScript. SWISH provides a web server where multiple users can manipulate and run the same material, and it can be adapted to support Prolog extensions. In this paper we describe the architecture of SWISH, and describe two case studies of extensions of Prolog, namely Probabilistic Logic Programming (PLP) and Logic Production System (LPS), which have used SWISH to provide tutorial sites.
Automatic Foreground Extraction from Imperfect Backgrounds using Multi-Agent Consensus Equilibrium
Venue: arXiv cs.CV 2020
Year: 2020

Extracting accurate foreground objects from a scene is an essential step for many video applications. Traditional background subtraction algorithms can generate coarse estimates, but generating high quality masks requires professional softwares with significant human interventions, e.g., providing trimaps or labeling key frames. We propose an automatic foreground extraction method in applications where a static but imperfect background is available. Examples include filming and surveillance where the background can be captured before the objects enter the scene or after they leave the scene. Our proposed method is very robust and produces significantly better estimates than state-of-the-art background subtraction, video segmentation and alpha matting methods. The key innovation of our method is a novel information fusion technique. The fusion framework allows us to integrate the individual strengths of alpha matting, background subtraction and image denoising to produce an overall better estimate. Such integration is particularly important when handling complex scenes with imperfect background. We show how the framework is developed, and how the individual components are built. Extensive experiments and ablation studies are conducted to evaluate the proposed method.
A new Taxonomy of Continuous Global Optimization Algorithms
Venue: arXiv cs.NE 2020
Year: 2020

Surrogate-based optimization, nature-inspired metaheuristics, and hybrid combinations have become state of the art in algorithm design for solving real-world optimization problems. Still, it is difficult for practitioners to get an overview that explains their advantages in comparison to a large number of available methods in the scope of optimization. Available taxonomies lack the embedding of current approaches in the larger context of this broad field. This article presents a taxonomy of the field, which explores and matches algorithm strategies by extracting similarities and differences in their search strategies. A particular focus lies on algorithms using surrogates, nature-inspired designs, and those created by design optimization. The extracted features of components or operators allow us to create a set of classification indicators to distinguish between a small number of classes. The features allow a deeper understanding of components of the search strategies and further indicate the close connections between the different algorithm designs. We present intuitive analogies to explain the basic principles of the search algorithms, particularly useful for novices in this research field. Furthermore, this taxonomy allows recommendations for the applicability of the corresponding algorithms.
Context Mover's Distance & Barycenters: Optimal Transport of Contexts for Building Representations
Venue: arXiv cs.CL 2020
Year: 2020

We present a framework for building unsupervised representations of entities and their compositions, where each entity is viewed as a probability distribution rather than a vector embedding. In particular, this distribution is supported over the contexts which co-occur with the entity and are embedded in a suitable low-dimensional space. This enables us to consider representation learning from the perspective of Optimal Transport and take advantage of its tools such as Wasserstein distance and barycenters. We elaborate how the method can be applied for obtaining unsupervised representations of text and illustrate the performance (quantitatively as well as qualitatively) on tasks such as measuring sentence similarity, word entailment and similarity, where we empirically observe significant gains (e.g., 4.1% relative improvement over Sent2vec, GenSen). The key benefits of the proposed approach include: (a) capturing uncertainty and polysemy via modeling the entities as distributions, (b) utilizing the underlying geometry of the particular task (with the ground cost), (c) simultaneously providing interpretability with the notion of optimal transport between contexts and (d) easy applicability on top of existing point embedding methods. The code, as well as prebuilt histograms, are available under https://github.com/context-mover/.
Generalized weak rigidity: Theory, and local and global convergence of formations
Venue: arXiv cs.SY 2020
Year: 2020

This paper discusses generalized weak rigidity theory, and aims to apply the theory to formation control problems with a gradient flow law. The generalized weak rigidity theory is utilized in order that desired formations are characterized by a general set of pure inter-agent distances and angles. As the first result of its applications, the paper provides analysis of locally exponential stability for formation systems with pure distance/angle constraints in the $2$- and $3$-dimensional spaces. Then, as the second result, if there are three agents in the $2$-dimensional space, almost globally exponential stability for formation systems is ensured. Through numerical simulations, the validity of analyses is illustrated.
A Continuous Information Gain Measure to Find the Most Discriminatory Problems for AI Benchmarking
Venue: arXiv cs.AI 2020
Year: 2020

This paper introduces an information-theoretic method for selecting a subset of problems which gives the most information about a group of problem-solving algorithms. This method was tested on the games in the General Video Game AI (GVGAI) framework, allowing us to identify a smaller set of games that still gives a large amount of information about the abilities of different game-playing agents. This approach can be used to make agent testing more efficient. We can achieve almost as good discriminatory accuracy when testing on only a handful of games as when testing on more than a hundred games, something which is often computationally infeasible. Furthermore, this method can be extended to study the dimensions of the effective variance in game design between these games, allowing us to identify which games differentiate between agents in the most complementary ways.
Accurate Tracking of Aggressive Quadrotor Trajectories using Incremental Nonlinear Dynamic Inversion and Differential Flatness
Venue: arXiv cs.RO 2020
Year: 2020

Autonomous unmanned aerial vehicles (UAVs) that can execute aggressive (i.e., high-speed and high-acceleration) maneuvers have attracted significant attention in the past few years. This paper focuses on accurate tracking of aggressive quadcopter trajectories. We propose a novel control law for tracking of position and yaw angle and their derivatives of up to fourth order, specifically, velocity, acceleration, jerk, and snap along with yaw rate and yaw acceleration. Jerk and snap are tracked using feedforward inputs for angular rate and angular acceleration based on the differential flatness of the quadcopter dynamics. Snap tracking requires direct control of body torque, which we achieve using closed-loop motor speed control based on measurements from optical encoders attached to the motors. The controller utilizes incremental nonlinear dynamic inversion (INDI) for robust tracking of linear and angular accelerations despite external disturbances, such as aerodynamic drag forces. Hence, prior modeling of aerodynamic effects is not required. We rigorously analyze the proposed control law through response analysis, and we demonstrate it in experiments. The controller enables a quadcopter UAV to track complex 3D trajectories, reaching speeds up to 12.9 m/s and accelerations up to 2.1g, while keeping the root-mean-square tracking error down to 6.6 cm, in a flight volume that is roughly 18 m by 7 m and 3 m tall. We also demonstrate the robustness of the controller by attaching a drag plate to the UAV in flight tests and by pulling on the UAV with a rope during hover.
Interstellar: Using Halide's Scheduling Language to Analyze DNN Accelerators
Venue: arXiv cs.DC 2020
Year: 2020

We show that DNN accelerator micro-architectures and their program mappings represent specific choices of loop order and hardware parallelism for computing the seven nested loops of DNNs, which enables us to create a formal taxonomy of all existing dense DNN accelerators. Surprisingly, the loop transformations needed to create these hardware variants can be precisely and concisely represented by Halide's scheduling language. By modifying the Halide compiler to generate hardware, we create a system that can fairly compare these prior accelerators. As long as proper loop blocking schemes are used, and the hardware can support mapping replicated loops, many different hardware dataflows yield similar energy efficiency with good performance. This is because the loop blocking can ensure that most data references stay on-chip with good locality and the processing units have high resource utilization. How resources are allocated, especially in the memory system, has a large impact on energy and performance. By optimizing hardware resource allocation while keeping throughput constant, we achieve up to 4.2X energy improvement for Convolutional Neural Networks (CNNs), 1.6X and 1.8X improvement for Long Short-Term Memories (LSTMs) and multi-layer perceptrons (MLPs), respectively.
MotherNets: Rapid Deep Ensemble Learning
Venue: arXiv cs.LG 2020
Year: 2020

Ensembles of deep neural networks significantly improve generalization accuracy. However, training neural network ensembles requires a large amount of computational resources and time. State-of-the-art approaches either train all networks from scratch leading to prohibitive training cost that allows only very small ensemble sizes in practice, or generate ensembles by training a monolithic architecture, which results in lower model diversity and decreased prediction accuracy. We propose MotherNets to enable higher accuracy and practical training cost for large and diverse neural network ensembles: A MotherNet captures the structural similarity across some or all members of a deep neural network ensemble which allows us to share data movement and computation costs across these networks. We first train a single or a small set of MotherNets and, subsequently, we generate the target ensemble networks by transferring the function from the trained MotherNet(s). Then, we continue to train these ensemble networks, which now converge drastically faster compared to training from scratch. MotherNets handle ensembles with diverse architectures by clustering ensemble networks of similar architecture and training a separate MotherNet for every cluster. MotherNets also use clustering to control the accuracy vs. training cost tradeoff. We show that compared to state-of-the-art approaches such as Snapshot Ensembles, Knowledge Distillation, and TreeNets, MotherNets provide a new Pareto frontier for the accuracy-training cost tradeoff. Crucially, training cost and accuracy improvements continue to scale as we increase the ensemble size (2 to 3 percent reduced absolute test error rate and up to 35 percent faster training compared to Snapshot Ensembles). We verify these benefits over numerous neural network architectures and large data sets.
Graph Pattern Mining and Learning through User-defined Relations (Extended Version)
Venue: arXiv cs.LG 2020
Year: 2020

In this work we propose R-GPM, a parallel computing framework for graph pattern mining (GPM) through a user-defined subgraph relation. More specifically, we enable the computation of statistics of patterns through their subgraph classes, generalizing traditional GPM methods. R-GPM provides efficient estimators for these statistics by employing a MCMC sampling algorithm combined with several optimizations. We provide both theoretical guarantees and empirical evaluations of our estimators in application scenarios such as stochastic optimization of deep high-order graph neural network models and pattern (motif) counting. We also propose and evaluate optimizations that enable improvements of our estimators accuracy, while reducing their computational costs in up to 3-orders-of-magnitude. Finally,we show that R-GPM is scalable, providing near-linear speedups on 44 cores in all of our tests.
Meta-Embedding as Auxiliary Task Regularization
Venue: arXiv cs.CL 2020
Year: 2020

Word embeddings have been shown to benefit from ensambling several word embedding sources, often carried out using straightforward mathematical operations over the set of word vectors. More recently, self-supervised learning has been used to find a lower-dimensional representation, similar in size to the individual word embeddings within the ensemble. However, these methods do not use the available manually labeled datasets that are often used solely for the purpose of evaluation. We propose to reconstruct an ensemble of word embeddings as an auxiliary task that regularises a main task while both tasks share the learned meta-embedding layer. We carry out intrinsic evaluation (6 word similarity datasets and 3 analogy datasets) and extrinsic evaluation (4 downstream tasks). For intrinsic task evaluation, supervision comes from various labeled word similarity datasets. Our experimental results show that the performance is improved for all word similarity datasets when compared to self-supervised learning methods with a mean increase of $11.33$ in Spearman correlation. Specifically, the proposed method shows the best performance in 4 out of 6 of word similarity datasets when using a cosine reconstruction loss and Brier's word similarity loss. Moreover, improvements are also made when performing word meta-embedding reconstruction in sequence tagging and sentence meta-embedding for sentence classification.
Observation and Distinction. Representing Information in Infinite Games
Venue: arXiv cs.GT 2020
Year: 2020

We compare two approaches for modelling imperfect information in infinite games by using finite-state automata. The first, more standard approach views information as the result of an observation process driven by a sequential Mealy machine. In contrast, the second approach features indistinguishability relations described by synchronous two-tape automata. The indistinguishability-relation model turns out to be strictly more expressive than the one based on observations. We present a characterisation of the indistinguishability relations that admit a representation as a finite-state observation function. We show that the characterisation is decidable, and give a procedure to construct a corresponding Mealy machine whenever one exists.
AppAngio: Revealing Contextual Information of Android App Behaviors by API-Level Audit Logs
Venue: arXiv cs.SE 2020
Year: 2020

Android users are now suffering severe threats from unwanted behaviors of various apps. The analysis of apps' audit logs is one of the essential methods for some device manufacturers to unveil the underlying malice within apps. We propose and implement AppAngio, a novel system that reveals contextual information in Android app behaviors by API-level audit logs. Our goal is to help analysts of device manufactures understand what has happened on users' devices and facilitate the identification of the malice within apps. The key module of AppAngio is identifying the path matched with the logs on the app's control-flow graph (CFG). The challenge, however, is that the limited-quantity logs may incur high computational complexity in the log matching, where there are a large number of candidates caused by the coupling relation of successive logs. To address the challenge, we propose a divide and conquer strategy that precisely positions the nodes matched with log records on the corresponding CFGs and connects the nodes with as few backtracks as possible. Our experiments show that AppAngio reveals the contextual information of behaviors in real-world apps. Moreover, the revealed results assist the analysts in identifying malice of app behaviors and complement existing analysis schemes. Meanwhile, AppAngio incurs negligible performance overhead on the Android device.
Fully distributed cooperation for networked uncertain mobile manipulators
Venue: arXiv cs.RO 2020
Year: 2020

This paper investigates a fully distributed cooperation scheme for networked mobile manipulators. To achieve cooperative task allocation in a distributed way, an adaptation-based estimation law is established for each robotic agent to estimate the desired local trajectory. In addition, wrench synthesis is analyzed in detail to lay a solid foundation for tight cooperation tasks. Together with the estimated task, a set of distributed adaptive controllers is proposed to achieve motion synchronization of the mobile manipulator ensemble over a directed graph with a spanning tree irrespective of the kinematic and dynamic uncertainties in both the mobile manipulators and the tightly grasped object. The controlled synchronization alleviates the performance degradation caused by the estimation/tracking discrepancy during the transient phase. The proposed scheme requires no persistent excitation condition and avoids the use of noisy Cartesian-space velocities. Furthermore, it is independent from the object's center of mass by employing formation-based task allocation and a task-oriented strategy. These attractive attributes facilitate the practical application of the scheme. It is theoretically proven that convergence of the cooperative task tracking error is guaranteed. Simulation results validate the efficacy and demonstrate the expected performance of the proposed scheme.
LSTM-based Whisper Detection
Venue: arXiv cs.CL 2020
Year: 2020

This article presents a whisper speech detector in the far-field domain. The proposed system consists of a long-short term memory (LSTM) neural network trained on log-filterbank energy (LFBE) acoustic features. This model is trained and evaluated on recordings of human interactions with voice-controlled, far-field devices in whisper and normal phonation modes. We compare multiple inference approaches for utterance-level classification by examining trajectories of the LSTM posteriors. In addition, we engineer a set of features based on the signal characteristics inherent to whisper speech, and evaluate their effectiveness in further separating whisper from normal speech. A benchmarking of these features using multilayer perceptrons (MLP) and LSTMs suggests that the proposed features, in combination with LFBE features, can help us further improve our classifiers. We prove that, with enough data, the LSTM model is indeed as capable of learning whisper characteristics from LFBE features alone compared to a simpler MLP model that uses both LFBE and features engineered for separating whisper and normal speech. In addition, we prove that the LSTM classifiers accuracy can be further improved with the incorporation of the proposed engineered features.
A Prospect Theoretic Approach for Trust Management in IoT Networks under Manipulation Attacks
Venue: arXiv cs.NI 2020
Year: 2020

As Internet of Things (IoT) and Cyber-Physical systems become more ubiquitous and an integral part of our daily lives, it is important that we are able to trust the data aggregate from such systems. However, the interpretation of trustworthiness is contextual and varies according to the risk tolerance attitude of the concerned application and varying levels of uncertainty associated with the evidence upon which trust models act. Hence, the data integrity scoring mechanisms should have provisions to adapt to varying risk attitudes and uncertainties. In this paper, we propose a Bayesian inference model and a prospect theoretic framework for data integrity scoring that quantify the trustworthiness of data collected from IoT devices in the presence of an adversaries who manipulate the data. We consider an imperfect anomaly monitoring mechanism that monitors the data being sent from each device and classifies the outcome as not compromised, compromised, and cannot be inferred. These outcomes are conceptualized as a multinomial hypothesis of a Bayesian inference model with three parameters which are then used for calculating a utility value on how reliable the aggregate data is. We use a prospect theory inspired approach to quantify this data integrity score and evaluate the trustworthiness of the aggregate data from the IoT framework. Furthermore, we also model the system using the traditionally used expected utility theory and compare the results with that obtained using prospect theory. As decisions are based on how the data is fused, we propose two measuring models: one optimistic and another conservative. The proposed framework is validated using extensive simulation experiments. We show how data integrity scores vary under a variety of system factors like attack intensity and inaccurate detection.