OpenRaiser/Intern-Atlas huggingface dataset:
Tone-index Multisine Modulation for SWIPT
Venue: arXiv cs.IT 2019
Year: 2019

We propose a new simultaneous wireless information and power transfer (SWIPT) technique that embeds information bits in the tone-index of multisine waveforms. By varying the number of subcarriers of the transmitted bandwidth-constrained multisine signal, the proposed scheme enables efficient radio-frequency energy harvesting and low-complexity information transmission. The receiver does not require channel estimation and employs a non-coherent maximum-likelihood detection at the envelope of the received signal. The performance of the proposed tone-index modulation is evaluated in terms of average error probability for a flat-fading channel, and we show that it outperforms its peak-to-average-power-ratio counterpart.
Graph-Based Offline Signature Verification
Venue: arXiv cs.CV 2019
Year: 2019

Graphs provide a powerful representation formalism that offers great promise to benefit tasks like handwritten signature verification. While most state-of-the-art approaches to signature verification rely on fixed-size representations, graphs are flexible in size and allow modeling local features as well as the global structure of the handwriting. In this article, we present two recent graph-based approaches to offline signature verification: keypoint graphs with approximated graph edit distance and inkball models. We provide a comprehensive description of the methods, propose improvements both in terms of computational time and accuracy, and report experimental results for four benchmark datasets. The proposed methods achieve top results for several benchmarks, highlighting the potential of graph-based signature verification.
New Pumping Technique for 2-dimensional VASS
Venue: arXiv cs.FL 2019
Year: 2019

We propose a new pumping technique for 2-dimensional vector addition systems with states (2-VASS) building on natural geometric properties of runs. We illustrate its applicability by reproving an exponential bound on the length of the shortest accepting run, and by proving a new pumping lemma for languages of 2-VASS. The technique is expected to be useful for settling questions concerning languages of 2-VASS, e.g., for establishing decidability status of the regular separability problem.
3D Surface Reconstruction from Voxel-based Lidar Data
Venue: arXiv cs.CV 2019
Year: 2019

To achieve fully autonomous navigation, vehicles need to compute an accurate model of their direct surrounding. In this paper, a 3D surface reconstruction algorithm from heterogeneous density 3D data is presented. The proposed method is based on a TSDF voxel-based representation, where an adaptive neighborhood kernel sourced on a Gaussian confidence evaluation is introduced. This enables to keep a good trade-off between the density of the reconstructed mesh and its accuracy. Experimental evaluations carried on both synthetic (CARLA) and real (KITTI) 3D data show a good performance compared to a state of the art method used for surface reconstruction.
A Convolutional Approach to Melody Line Identification in Symbolic Scores
Venue: arXiv cs.SD 2019
Year: 2019

In many musical traditions, the melody line is of primary significance in a piece. Human listeners can readily distinguish melodies from accompaniment; however, making this distinction given only the written score -- i.e. without listening to the music performed -- can be a difficult task. Solving this task is of great importance for both Music Information Retrieval and musicological applications. In this paper, we propose an automated approach to identifying the most salient melody line in a symbolic score. The backbone of the method consists of a convolutional neural network (CNN) estimating the probability that each note in the score (more precisely: each pixel in a piano roll encoding of the score) belongs to the melody line. We train and evaluate the method on various datasets, using manual annotations where available and solo instrument parts where not. We also propose a method to inspect the CNN and to analyze the influence exerted by notes on the prediction of other notes; this method can be applied whenever the output of a neural network has the same size as the input.
Awareness of Voter Passion Greatly Improves the Distortion of Metric Social Choice
Venue: arXiv cs.AI 2019
Year: 2019

We develop new voting mechanisms for the case when voters and candidates are located in an arbitrary unknown metric space, and the goal is to choose a candidate minimizing social cost: the total distance from the voters to this candidate. Previous work has often assumed that only ordinal preferences of the voters are known (instead of their true costs), and focused on minimizing distortion: the quality of the chosen candidate as compared with the best possible candidate. In this paper, we instead assume that a (very small) amount of information is known about the voter preference strengths, not just about their ordinal preferences. We provide mechanisms with much better distortion when this extra information is known as compared to mechanisms which use only ordinal information. We quantify tradeoffs between the amount of information known about preference strengths and the achievable distortion. We further provide advice about which type of information about preference strengths seems to be the most useful. Finally, we conclude by quantifying the ideal candidate distortion, which compares the quality of the chosen outcome with the best possible candidate that could ever exist, instead of only the best candidate that is actually in the running.
Isometry-Dual Flags of AG Codes
Venue: arXiv cs.IT 2019
Year: 2019

Consider a complete flag $\{0\} = C_0 < C_1 < \cdots < C_n = \mathbb{F}^n$ of one-point AG codes of length $n$ over the finite field $\mathbb{F}$. The codes are defined by evaluating functions with poles at a given point $Q$ in points $P_1,\dots,P_n$ distinct from $Q$. A flag has the isometry-dual property if the given flag and the corresponding dual flag are the same up to isometry. For several curves, including the projective line, Hermitian curves, Suzuki curves, Ree curves, and the Klein curve over the field of eight elements, the maximal flag, obtained by evaluation in all rational points different from the point $Q$, is self-dual. More generally, we ask whether a flag obtained by evaluation in a proper subset of rational points is isometry-dual. In [3] it is shown, for a curve of genus $g$, that a flag of one-point AG codes defined with a subset of $n > 2g+2$ rational points is isometry-dual if and only if the last code $C_n$ in the flag is defined with functions of pole order at most $n+2g-1$. Using a different approach, we extend this characterization to all subsets of size $n \geq 2g+2$. Moreover we show that this is best possible by giving examples of isometry-dual flags with $n=2g+1$ such that $C_n$ is generated by functions of pole order at most $n+2g-2$. We also prove a necessary condition, formulated in terms of maximum sparse ideals of the Weierstrass semigroup of $Q$, under which a flag of punctured one-point AG codes inherits the isometry-dual property from the original unpunctured flag.
Emotion Recognition Using Fusion of Audio and Video Features
Venue: arXiv cs.LG 2019
Year: 2019

In this paper we propose a fusion approach to continuous emotion recognition that combines visual and auditory modalities in their representation spaces to predict the arousal and valence levels. The proposed approach employs a pre-trained convolution neural network and transfer learning to extract features from video frames that capture the emotional content. For the auditory content, a minimalistic set of parameters such as prosodic, excitation, vocal tract, and spectral descriptors are used as features. The fusion of these two modalities is carried out at a feature level, before training a single support vector regressor (SVR) or at a prediction level, after training one SVR for each modality. The proposed approach also includes preprocessing and post-processing techniques which contribute favorably to improving the concordance correlation coefficient (CCC). Experimental results for predicting spontaneous and natural emotions on the RECOLA dataset have shown that the proposed approach takes advantage of the complementary information of visual and auditory modalities and provides CCCs of 0.749 and 0.565 for arousal and valence, respectively.
Wise Data: A Novel Approach in Data Science from a Network Science Perspective
Venue: arXiv cs.OH 2019
Year: 2019

Human beings have been generating data since very long times ago. We ask the following common-sense and wise questions (WizQuestions): 1. Why do we refer to some pieces of data more often than referring to other pieces? 2. What does make those commonly-referred pieces of data so unique and different? 3. What are the characteristics of data that sometimes make the data so unique and different? In this article, we introduce a novel approach (model) that helps us answer these questions from data science and network science perspectives. WizWordily speaking, our proposed approach enables us to model the data (as a network), measure the quality of data, and study the network of data deeply and thoroughly.
Uncertainty-aware Model-based Policy Optimization
Venue: arXiv cs.LG 2019
Year: 2019

Model-based reinforcement learning has the potential to be more sample efficient than model-free approaches. However, existing model-based methods are vulnerable to model bias, which leads to poor generalization and asymptotic performance compared to model-free counterparts. In addition, they are typically based on the model predictive control (MPC) framework, which not only is computationally inefficient at decision time but also does not enable policy transfer due to the lack of an explicit policy representation. In this paper, we propose a novel uncertainty-aware model-based policy optimization framework which solves those issues. In this framework, the agent simultaneously learns an uncertainty-aware dynamics model and optimizes the policy according to these learned models. In the optimization step, the policy gradient is computed by automatic differentiation through the models. With respect to sample efficiency alone, our approach shows promising results on challenging continuous control benchmarks with competitive asymptotic performance and significantly lower sample complexity than state-of-the-art baselines.
Anti-Latinx Computational Propaganda in the United States
Venue: arXiv cs.SI 2019
Year: 2019

Given that the Latino community is the second largest ethnic group in the US, an understanding of how Latinos are discussed and targeted on social media during US elections is crucial. This paper explores these questions through a data analysis on Reddit, one of the most prominent and popular social media platforms for political discussion. We collected Reddit posts mentioning Latinos and the US midterm elections from September 24, 2017 to September 24, 2018. We analyzed people's posting patterns over time, and the digital traces of the individuals posting the majority of content and the most popular content. Our research highlights data voids that existed in online discussions surrounding Latinos prior to the US midterm elections. We observe a lack of neutral actors engaging Latinos in political topics. It appears that it is the more extremist voices (i.e. individuals operating within subreddits who identify themselves as political trolls) who are creating the most political content about Latinos. We conclude our report with a discussion of the possible dangers of data voids (especially with regard to their ties to mis- and disinformation) and recommendations to increase the involvement of the Latino community in future US elections.
Large-Scale Analysis of Pop-Up Scam on Typosquatting URLs
Venue: arXiv cs.CR 2019
Year: 2019

Today, many different types of scams can be found on the internet. Online criminals are always finding new creative ways to trick internet users, be it in the form of lottery scams, downloading scam apps for smartphones or fake gambling websites. This paper presents a large-scale study on one particular delivery method of online scam: pop-up scam on typosquatting domains. Typosquatting describes the concept of registering domains which are very similar to existing ones while deliberately containing common typing errors; these domains are then used to trick online users while under the belief of browsing the intended website. Pop-up scam uses JavaScript alert boxes to present a message which attracts the user's attention very effectively, as they are a blocking user interface element. Our study among typosquatting domains derived from the Alexa Top 1 Million list revealed on 8255 distinct typosquatting URLs a total of 9857 pop-up messages, out of which 8828 were malicious. The vast majority of those distinct URLs (7176) were targeted and displayed pop-up messages to one specific HTTP user agent only. Based on our scans, we present an in-depth analysis as well as a detailed classification of different targeting parameters (user agent and language) which triggered varying kinds of pop-up scams.
Asymptotic growth rate of square grids dominating sets: a symbolic dynamics approach
Venue: arXiv cs.DM 2019
Year: 2019

In this text, we prove the existence of an asymptotic growth rate of the number of dominating sets (and variants) on finite rectangular grids, when the dimensions of the grid grow to infinity. Moreover, we provide, for each of the variants, an algorithm which computes the growth rate. We also give bounds on these rates provided by a computer program.
OLAE-ICP: Robust and fast alignment of geometric features with the optimal linear attitude estimator
Venue: arXiv cs.RO 2019
Year: 2019

The problems of point-cloud registration and attitude estimation from vector observations (Wahba's problem) have widespread applications in computer vision and mobile robotics. This work introduces a simple approach for integrating sets of geometric feature observations (points, lines, and planes) in such a way that any solution to either point-cloud registration or to Wahba's problem can be used to find the SE(3) transformation between the two sets that minimizes the corresponding cost function. We compare the performance of three solutions: classic Horn's optimal quaternion method, Optimal Linear Attitude Estimator (OLAE) that efficiently recovers the optimal Gibbs-Rodrigues vector solving a small linear system, and an iterative non-linear Gauss-Newton solver. Special care is given to explain how to overcome the Gibbs vector singularity for OLAE by using the method of sequential rotations. Gross outliers in point-to-point correspondences can be discarded by means of detecting transformation scale mismatches. The approach also allows the introduction of per-primitive relative weights, including an optional robust loss function that is applicable only if an initial guess for the solution is known in advance. Experiments are presented to evaluate how the three solutions tolerate noise in the input data for different kinds of geometric primitives. Finally, experiments with real datasets validate the suitability of the optimal alignment algorithm as the core of an Iterative Closest Point/Primitive (ICP) algorithm. An open-source implementation of all the described algorithms is provided in https://github.com/MOLAorg/mp2p_icp
Upper and Lower Bounds on Approximating Weighted Mixed Domination
Venue: arXiv cs.DS 2019
Year: 2019

A mixed dominating set of a graph $G = (V, E)$ is a mixed set $D$ of vertices and edges, such that for every edge or vertex, if it is not in $D$, then it is adjacent or incident to at least one vertex or edge in $D$. The mixed domination problem is to find a mixed dominating set with a minimum cardinality. It has applications in system control and some other scenarios and it is $NP$-hard to compute an optimal solution. This paper studies approximation algorithms and hardness of the weighted mixed dominating set problem. The weighted version is a generalization of the unweighted version, where all vertices are assigned the same nonnegative weight $w_v$ and all edges are assigned the same nonnegative weight $w_e$, and the question is to find a mixed dominating set with a minimum total weight. Although the mixed dominating set problem has a simple 2-approximation algorithm, few approximation results for the weighted version are known. The main contributions of this paper include: [1.] for $w_e\geq w_v$, a 2-approximation algorithm; [2.] for $w_e\geq 2w_v$, inapproximability within ratio 1.3606 unless $P=NP$ and within ratio 2 under UGC; [3.] for $2w_v > w_e\geq w_v$, inapproximability within ratio 1.1803 unless $P=NP$ and within ratio 1.5 under UGC; [4.] for $w_e< w_v$, inapproximability within ratio $(1-ε)\ln |V|$ unless $P=NP$ for any $ε>0$.
Coded State Machine -- Scaling State Machine Execution under Byzantine Faults
Venue: arXiv cs.IT 2019
Year: 2019

We introduce an information-theoretic framework, named Coded State Machine (CSM), to securely and efficiently execute multiple state machines on untrusted network nodes, some of which are Byzantine. The standard method of solving this problem is using State Machine Replication, which achieves high security at the cost of low efficiency. We propose CSM, which achieves the optimal linear scaling in storage efficiency, throughput, and security simultaneously with the size of the network. The storage efficiency is scaled via the design of Lagrange coded states and coded input commands that require the same storage size as their origins. The computational efficiency is scaled using a novel delegation algorithm, called INTERMIX, which is an information-theoretically verifiable matrix-vector multiplication algorithm of independent interest. Using INTERMIX, the network nodes securely delegate their coding operations to a single worker node, and a small group of randomly selected auditor nodes verify its correctness, so that computational efficiency can scale almost linearly with the network size, without compromising on security.
Essence Knowledge Distillation for Speech Recognition
Venue: arXiv cs.CL 2019
Year: 2019

It is well known that a speech recognition system that combines multiple acoustic models trained on the same data significantly outperforms a single-model system. Unfortunately, real time speech recognition using a whole ensemble of models is too computationally expensive. In this paper, we propose to distill the knowledge of essence in an ensemble of models (i.e. the teacher model) to a single model (i.e. the student model) that needs much less computation to deploy. Previously, all the soften outputs of the teacher model are used to optimize the student model. We argue that not all the outputs of the ensemble are necessary to be distilled. Some of the outputs may even contain noisy information that is useless or even harmful to the training of the student model. In addition, we propose to train the student model with a multitask learning approach by utilizing both the soften outputs of the teacher model and the correct hard labels. The proposed method achieves some surprising results on the Switchboard data set. When the student model is trained together with the correct labels and the essence knowledge from the teacher model, it not only significantly outperforms another single model with the same architecture that is trained only with the correct labels, but also consistently outperforms the teacher model that is used to generate the soft labels.
Making Smartphone Application Permissions Meaningful for the Average User
Venue: arXiv cs.CR 2019
Year: 2019

Smartphones hold important private information, yet users routinely expose this information to questionable applications written by developers they know nothing about. Users may be tempted to think of smartphones as old-style dumb phones, not as powerful network-connected computers, and this opens a gap between the permissions-based security paradigm (offered by platforms like Android) and what users expect. This makes it easy to fool users into installing applications that steal their information. Not surprisingly, Android is now a more favored target for hackers than Windows. We propose an approach for closing this gap, based on the observation that the current permissions system--rooted in good ol' UNIX-style thinking--is both too coarse and too fine grained, because it uses the wrong axes for defining the permissions space. We argue for replacing the paradigm in which "an app accesses device resources" (which is foreign to most non-geeks) with a paradigm in which "an app accesses user-tangible services." By using a simple piece of middleware, we can wrap this view of application control around today's permission system, and, by doing so, no conceptual refactoring of applications is required.
Towards Empathic Deep Q-Learning
Venue: arXiv cs.LG 2019
Year: 2019

As reinforcement learning (RL) scales to solve increasingly complex tasks, interest continues to grow in the fields of AI safety and machine ethics. As a contribution to these fields, this paper introduces an extension to Deep Q-Networks (DQNs), called Empathic DQN, that is loosely inspired both by empathy and the golden rule ("Do unto others as you would have them do unto you"). Empathic DQN aims to help mitigate negative side effects to other agents resulting from myopic goal-directed behavior. We assume a setting where a learning agent coexists with other independent agents (who receive unknown rewards), where some types of reward (e.g. negative rewards from physical harm) may generalize across agents. Empathic DQN combines the typical (self-centered) value with the estimated value of other agents, by imagining (by its own standards) the value of it being in the other's situation (by considering constructed states where both agents are swapped). Proof-of-concept results in two gridworld environments highlight the approach's potential to decrease collateral harms. While extending Empathic DQN to complex environments is non-trivial, we believe that this first step highlights the potential of bridge-work between machine ethics and RL to contribute useful priors for norm-abiding RL agents.
A wrinkle in time: A case study in DNS poisoning
Venue: arXiv cs.CR 2019
Year: 2019

The Domain Name System (DNS) provides a translation between readable domain names and IP addresses. The DNS is a key infrastructure component of the Internet and a prime target for a variety of attacks. One of the most significant threat to the DNS's wellbeing is a DNS poisoning attack, in which the DNS responses are maliciously replaced, or poisoned, by an attacker. To identify this kind of attack, we start by an analysis of different kinds of response times. We present an analysis of typical and atypical response times, while differentiating between the different levels of DNS servers' response times, from root servers down to internal caching servers. We successfully identify empirical DNS poisoning attacks based on a novel method for DNS response timing analysis. We then present a system we developed to validate our technique that does not require any changes to the DNS protocol or any existing network equipment. Our validation system tested data from different architectures including LAN and cloud environments and real data from an Internet Service Provider (ISP). Our method and system differ from most other DNS poisoning detection methods and achieved high detection rates exceeding 99%. These findings suggest that when used in conjunction with other methods, they can considerably enhance the accuracy of these methods.