OpenRaiser/Intern-Atlas huggingface dataset:
Personalizing a Dialogue System with Transfer Reinforcement Learning
Venue: arXiv cs.AI 2017
Year: 2017

It is difficult to train a personalized task-oriented dialogue system because the data collected from each individual is often insufficient. Personalized dialogue systems trained on a small dataset can overfit and make it difficult to adapt to different user needs. One way to solve this problem is to consider a collection of multiple users' data as a source domain and an individual user's data as a target domain, and to perform a transfer learning from the source to the target domain. By following this idea, we propose "PETAL"(PErsonalized Task-oriented diALogue), a transfer-learning framework based on POMDP to learn a personalized dialogue system. The system first learns common dialogue knowledge from the source domain and then adapts this knowledge to the target user. This framework can avoid the negative transfer problem by considering differences between source and target users. The policy in the personalized POMDP can learn to choose different actions appropriately for different users. Experimental results on a real-world coffee-shopping data and simulation data show that our personalized dialogue system can choose different optimal actions for different users, and thus effectively improve the dialogue quality under the personalized setting.
Achievable Rate and Energy Efficiency of Hybrid and Digital Beamforming Receivers with Low Resolution ADC
Venue: arXiv cs.IT 2017
Year: 2017

For 5G it will be important to leverage the available millimeter wave spectrum. To achieve an approximately omni- directional coverage with a similar effective antenna aperture compared to state of the art cellular systems, an antenna array is required at both the mobile and basestation. Due to the large bandwidth and inefficient amplifiers available in CMOS for mmWave, the analog front-end of the receiver with a large number of antennas becomes especially power hungry. Two main solutions exist to reduce the power consumption: Hybrid BeamForming (HBF) and Digital BeamForming (DBF) with low resolution ADC. Hybrid beamforming can also be combined with low resolution ADCs. This paper compares the spectral and energy efficiency based on the chosen RF-frontend configuration. A channel with multipath propagation is used. In contrast to previous publication, we take the spatial correlation of the quantization noise into account. We show that the low resolution ADC are robust to small Automatic Gain Control (AGC) imperfections. We showed that in the low SNR regime the performance of DBF even with 1-2 bit resolution outperforms HBF. If we consider the relationship of spectral and energy efficiency then DBF with 3-5 bits resolution achieves the best ratio of spectral efficiency per power consumption of the RF receiver frontend over a very wide SNR region. The power consumption model is based on components reported in literature.
Incrementally Closing Octagons
Venue: arXiv cs.PL 2017
Year: 2017

The octagon abstract domain is a widely used numeric abstract domain expressing relational information between variables whilst being both computationally efficient and simple to implement. Each element of the domain is a system of constraints where each constraint takes the restricted form $\pm x_i \pm x_j \leq d$. A key family of operations for the octagon domain are closure algorithms, which check satisfiability and provide a normal form for octagonal constraint systems. We present new quadratic incremental algorithms for closure, strong closure and integer closure and proofs of their correctness. We highlight the benefits and measure the performance of these new algorithms.
Skeletal Program Enumeration for Rigorous Compiler Testing
Venue: arXiv cs.PL 2017
Year: 2017

A program can be viewed as a syntactic structure P (syntactic skeleton) parameterized by a collection of the identifiers V (variable names). This paper introduces the skeletal program enumeration (SPE) problem: Given a fixed syntactic skeleton P and a set of variables V , enumerate a set of programs P exhibiting all possible variable usage patterns within P. It proposes an effective realization of SPE for systematic, rigorous compiler testing by leveraging three important observations: (1) Programs with different variable usage patterns exhibit diverse control- and data-dependence information, and help exploit different compiler optimizations and stress-test compilers; (2) most real compiler bugs were revealed by small tests (i.e., small-sized P) --- this "small-scope" observation opens up SPE for practical compiler validation; and (3) SPE is exhaustive w.r.t. a given syntactic skeleton and variable set, and thus can offer a level of guarantee that is absent from all existing compiler testing techniques. The key challenge of SPE is how to eliminate the enormous amount of equivalent programs w.r.t. $α$-conversion. Our main technical contribution is a novel algorithm for computing the canonical (and smallest) set of all non-$α$-equivalent programs. We have realized our SPE technique and evaluated it using syntactic skeletons derived from GCC's testsuite. Our evaluation results on testing GCC and Clang are extremely promising. In less than six months, our approach has led to 217 confirmed bug reports, 104 of which have already been fixed, and the majority are long latent bugs despite the extensive prior efforts of automatically testing both compilers (e.g., Csmith and EMI). The results also show that our algorithm for enumerating non-$α$-equivalent programs provides six orders of magnitude reduction, enabling processing the GCC test-suite in under a month.
QCMA hardness of ground space connectivity for commuting Hamiltonians
Venue: arXiv cs.CC 2017
Year: 2017

In this work we consider the ground space connectivity problem for commuting local Hamiltonians. The ground space connectivity problem asks whether it is possible to go from one (efficiently preparable) state to another by applying a polynomial length sequence of 2-qubit unitaries while remaining at all times in a state with low energy for a given Hamiltonian $H$. It was shown in [Gharibian and Sikora, ICALP'15] that this problem is QCMA-complete for general local Hamiltonians, where QCMA is defined as QMA with a classical witness and BQP verifier. Here we show that the commuting version of the problem is also QCMA-complete. This provides one of the first examples where commuting local Hamiltonians exhibit complexity theoretic hardness equivalent to general local Hamiltonians.
Light Field Compression with Disparity Guided Sparse Coding based on Structural Key Views
Venue: arXiv cs.CV 2017
Year: 2017

Recent imaging technologies are rapidly evolving for sampling richer and more immersive representations of the 3D world. And one of the emerging technologies are light field (LF) cameras based on micro-lens arrays. To record the directional information of the light rays, a much larger storage space and transmission bandwidth are required by a LF image as compared with a conventional 2D image of similar spatial dimension, and the compression of LF data becomes a vital part of its application. In this paper, we propose a LF codec that fully exploits the intrinsic geometry between the LF sub-views by first approximating the LF with disparity guided sparse coding over a perspective shifted light field dictionary. The sparse coding is only based on several optimized Structural Key Views (SKV); however the entire LF can be recovered from the coding coefficients. By keeping the approximation identical between encoder and decoder, only the residuals of the non-key views, disparity map and the SKVs need to be compressed into the bit stream. An optimized SKV selection method is proposed such that most LF spatial information could be preserved. And to achieve optimum dictionary efficiency, the LF is divided into several Coding Regions (CR), over which the reconstruction works individually. Experiments and comparisons have been carried out over benchmark LF dataset, which show that the proposed SC-SKV codec produces convincing compression results in terms of both rate-distortion performance and visual quality compared with High Efficiency Video Coding (HEVC): with 47.87% BD-rate reduction and 1.59 dB BD-PSNR improvement achieved on average, especially with up to 4 dB improvement for low bit rate scenarios.
The Curvature-Augmented Closest Point Method with Vesicle Inextensibility Application
Venue: arXiv cs.CE 2017
Year: 2017

The Closest Point method, initially developed by Ruuth and Merriman, allows for the numerical solution of surface partial differential equations without the need for a parameterization of the surface itself. Surface quantities are embedded into the surrounding domain by assigning each value at a given spatial location to the corresponding value at the closest point on the surface. This embedding allows for surface derivatives to be replaced by their Cartesian counterparts (e.g. $\nabla_s = \nabla$). This equivalence is only valid on the surface, and thus, interpolation is used to enforce what is known as the side condition away from the surface. To improve upon the method, this work derives an operator embedding that incorporates curvature information, making it valid in a neighborhood of the surface. With this, direct enforcement of the side condition is no longer needed. Comparisons in $\mathbb{R}^2$ and $\mathbb{R}^3$ show that the resulting Curvature-Augmented Closest Point method has better accuracy and requires less memory, through increased matrix sparsity, than the Closest Point method, while maintaining similar matrix condition numbers. To demonstrate the utility of the method in a physical application, simulations of inextensible, bi-lipid vesicles evolving toward equilibrium shapes are also included.
Reset-free Trial-and-Error Learning for Robot Damage Recovery
Venue: arXiv cs.RO 2017
Year: 2017

The high probability of hardware failures prevents many advanced robots (e.g., legged robots) from being confidently deployed in real-world situations (e.g., post-disaster rescue). Instead of attempting to diagnose the failures, robots could adapt by trial-and-error in order to be able to complete their tasks. In this situation, damage recovery can be seen as a Reinforcement Learning (RL) problem. However, the best RL algorithms for robotics require the robot and the environment to be reset to an initial state after each episode, that is, the robot is not learning autonomously. In addition, most of the RL methods for robotics do not scale well with complex robots (e.g., walking robots) and either cannot be used at all or take too long to converge to a solution (e.g., hours of learning). In this paper, we introduce a novel learning algorithm called "Reset-free Trial-and-Error" (RTE) that (1) breaks the complexity by pre-generating hundreds of possible behaviors with a dynamics simulator of the intact robot, and (2) allows complex robots to quickly recover from damage while completing their tasks and taking the environment into account. We evaluate our algorithm on a simulated wheeled robot, a simulated six-legged robot, and a real six-legged walking robot that are damaged in several ways (e.g., a missing leg, a shortened leg, faulty motor, etc.) and whose objective is to reach a sequence of targets in an arena. Our experiments show that the robots can recover most of their locomotion abilities in an environment with obstacles, and without any human intervention.
A Geometrical-Statistical approach to outlier removal for TDOA measuments
Venue: arXiv cs.IT 2017
Year: 2017

The curse of outlier measurements in estimation problems is a well known issue in a variety of fields. Therefore, outlier removal procedures, which enables the identification of spurious measurements within a set, have been developed for many different scenarios and applications. In this paper, we propose a statistically motivated outlier removal algorithm for time differences of arrival (TDOAs), or equivalently range differences (RD), acquired at sensor arrays. The method exploits the TDOA-space formalism and works by only knowing relative sensor positions. As the proposed method is completely independent from the application for which measurements are used, it can be reliably used to identify outliers within a set of TDOA/RD measurements in different fields (e.g. acoustic source localization, sensor synchronization, radar, remote sensing, etc.). The proposed outlier removal algorithm is validated by means of synthetic simulations and real experiments.
Tonal consonance parameters link microscopic and macroscopic properties of music exposing a hidden order in melody
Venue: arXiv cs.SD 2017
Year: 2017

Consonance is related to the perception of pleasantness arising from a combination of sounds and has been approached quantitatively using mathematical relations, physics, information theory, and psychoacoustics. Tonal consonance is present in timbre, musical tuning, harmony, and melody, and it is used for conveying sensations, perceptions, and emotions in music. It involves the physical properties of sound waves and is used to study melody and harmony through musical intervals and chords. From the perspective of complexity, the macroscopic properties of a system with many parts frequently rely on the statistical properties of its constituent elements. Here we show how the tonal consonance parameters for complex tones can be used to study complexity in music. We apply this formalism to melody, showing that melodic lines in musical pieces can be described in terms of the physical properties of melodic intervals and the existence of an entropy extremalization principle subject to psychoacoustic macroscopic constraints with musical meaning. This result connects the human perception of consonance with the complexity of human creativity in music through the physical properties of the musical stimulus.
Gibbard-Satterthwaite Success Stories and Obvious Strategyproofness
Venue: arXiv cs.GT 2017
Year: 2017

The Gibbard-Satterthwaite Impossibility Theorem holds that dictatorship is the only Pareto optimal and strategyproof social choice function on the full domain of preferences. Much of the work in mechanism design aims at getting around this impossibility theorem. Three grand success stories stand out. On the domains of single peaked preferences, of house matching, and of quasilinear preferences, there are appealing Pareto optimal and strategyproof social choice functions. We investigate whether these success stories are robust to strengthening strategyproofness to obvious strategyproofness (OSP), recently introduced by Li (2015). For single peaked preferences, we characterize the class of OSP-implementable and unanimous social choice functions as dictatorships with safeguards against extremism - mechanisms (which turn out to also be Pareto optimal) in which the dictator can choose the outcome, but other agents may prevent the dictator from choosing an outcome that is too extreme. Median voting is consequently not OSP-implementable. Indeed, the only OSP-implementable quantile rules choose either the minimal or the maximal ideal point. For house matching, we characterize the class of OSP-implementable and Pareto optimal matching rules as sequential barter with lurkers - a significant generalization over bossy variants of bipolar serially dictatorial rules. While Li (2015) shows that second-price auctions are OSP-implementable when only one good is sold, we show that this positive result does not extend to the case of multiple goods. Even when all agents' preferences over goods are quasilinear and additive, no welfare-maximizing auction where losers pay nothing is OSP-implementable when more than one good is sold. Our analysis makes use of a gradual revelation principle, an analog of the (direct) revelation principle for OSP mechanisms that we present and prove.
Logarithmic price of buffer downscaling on line metrics
Venue: arXiv cs.DS 2017
Year: 2017

We consider the reordering buffer problem on a line consisting of n equidistant points. We show that, for any constant delta, an (offline) algorithm that has a buffer (1-delta) k performs worse by a factor of Omega(log n) than an offline algorithm with buffer k. In particular, this demonstrates that the O(log n)-competitive online algorithm MovingPartition by Gamzu and Segev (ACM Trans. on Algorithms, 6(1), 2009) is essentially optimal against any offline algorithm with a slightly larger buffer.
Using Centroidal Voronoi Tessellations to Scale Up the Multi-dimensional Archive of Phenotypic Elites Algorithm
Venue: arXiv cs.NE 2017
Year: 2017

The recently introduced Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) is an evolutionary algorithm capable of producing a large archive of diverse, high-performing solutions in a single run. It works by discretizing a continuous feature space into unique regions according to the desired discretization per dimension. While simple, this algorithm has a main drawback: it cannot scale to high-dimensional feature spaces since the number of regions increase exponentially with the number of dimensions. In this paper, we address this limitation by introducing a simple extension of MAP-Elites that has a constant, pre-defined number of regions irrespective of the dimensionality of the feature space. Our main insight is that methods from computational geometry could partition a high-dimensional space into well-spread geometric regions. In particular, our algorithm uses a centroidal Voronoi tessellation (CVT) to divide the feature space into a desired number of regions; it then places every generated individual in its closest region, replacing a less fit one if the region is already occupied. We demonstrate the effectiveness of the new "CVT-MAP-Elites" algorithm in high-dimensional feature spaces through comparisons against MAP-Elites in maze navigation and hexapod locomotion tasks.
Membership Inference Attacks against Machine Learning Models
Venue: arXiv cs.CR 2017
Year: 2017

We quantitatively investigate how machine learning models leak information about the individual data records on which they were trained. We focus on the basic membership inference attack: given a data record and black-box access to a model, determine if the record was in the model's training dataset. To perform membership inference against a target model, we make adversarial use of machine learning and train our own inference model to recognize differences in the target model's predictions on the inputs that it trained on versus the inputs that it did not train on. We empirically evaluate our inference techniques on classification models trained by commercial "machine learning as a service" providers such as Google and Amazon. Using realistic datasets and classification tasks, including a hospital discharge dataset whose membership is sensitive from the privacy perspective, we show that these models can be vulnerable to membership inference attacks. We then investigate the factors that influence this leakage and evaluate mitigation strategies.
Cross-Lingual Syntactic Transfer with Limited Resources
Venue: arXiv cs.CL 2017
Year: 2017

We describe a simple but effective method for cross-lingual syntactic transfer of dependency parsers, in the scenario where a large amount of translation data is not available. The method makes use of three steps: 1) a method for deriving cross-lingual word clusters, which can then be used in a multilingual parser; 2) a method for transferring lexical information from a target language to source language treebanks; 3) a method for integrating these steps with the density-driven annotation projection method of Rasooli and Collins (2015). Experiments show improvements over the state-of-the-art in several languages used in previous work, in a setting where the only source of translation data is the Bible, a considerably smaller corpus than the Europarl corpus used in previous work. Results using the Europarl corpus as a source of translation data show additional improvements over the results of Rasooli and Collins (2015). We conclude with results on 38 datasets from the Universal Dependencies corpora.
ORB-SLAM2: an Open-Source SLAM System for Monocular, Stereo and RGB-D Cameras
Venue: arXiv cs.RO 2017
Year: 2017

We present ORB-SLAM2 a complete SLAM system for monocular, stereo and RGB-D cameras, including map reuse, loop closing and relocalization capabilities. The system works in real-time on standard CPUs in a wide variety of environments from small hand-held indoors sequences, to drones flying in industrial environments and cars driving around a city. Our back-end based on bundle adjustment with monocular and stereo observations allows for accurate trajectory estimation with metric scale. Our system includes a lightweight localization mode that leverages visual odometry tracks for unmapped regions and matches to map points that allow for zero-drift localization. The evaluation on 29 popular public sequences shows that our method achieves state-of-the-art accuracy, being in most cases the most accurate SLAM solution. We publish the source code, not only for the benefit of the SLAM community, but with the aim of being an out-of-the-box SLAM solution for researchers in other fields.
Reactive Turing Machines with Infinite Alphabets
Venue: arXiv cs.LO 2017
Year: 2017

The notion of Reactive Turing machine (RTM) was proposed as an orthogonal extension of Turing machines with interaction. RTMs are used to define the notion of executable transition system in the same way as Turing machines are used to define the notion of computable function on natural numbers. RTMs inherited finiteness of all sets involved from Turing machines, and as a consequence, in a single step, an RTM can only communicate elements from a finite set of data. Some process calculi, such as the pi-calculus, essentially depend on an infinite alphabet of actions, and hence it immediately follows that transition systems specified in these calculi are not executable. On closer inspection, however, the pi-calculus does not appear to use the infinite data in a non-computable manner. In this paper, we investigate several ways to relax the finiteness requirement. We start by considering a variant of RTMs in which all sets are allowed to be countable, and we get a notion of infinitary RTM. Infinitary RTMs are extremely expressive such that we can hardly use them as a expressiveness criterion. Then, we refine the model by adding extra restrictions. As a result, we define a notion of RTM with atoms. It is a more restricted variant of RTMs in which the sets of actions and data symbols are still allowed to be infinite. We propose a notion of of nominal executability based on RTMs with atoms, and show that every effective transition system with atoms is nominally executable. It will follow that processes definable in the pi-calculus are nominally executable. In contrast, in the process specification language mCRL2 it is possible to specify processes that are not nominally executable. Thus, nominal executability provides a new expressiveness criterion for process calculi.
Error estimates with explicit constants for the Sinc approximation over infinite intervals
Venue: arXiv cs.NA 2017
Year: 2017

The Sinc approximation is a function approximation formula that attains exponential convergence for rapidly decaying functions defined on the whole real axis. Even for other functions, the Sinc approximation works accurately when combined with a proper variable transformation. The convergence rate has been analyzed for typical cases including finite, semi-infinite, and infinite intervals. Recently, for verified numerical computations, a more explicit, "computable" error bound has been given in the case of a finite interval. In this paper, such explicit error bounds are derived for other cases.