OpenRaiser/Intern-Atlas huggingface dataset:
On the Differential Linear Connectivity Table of Vectorial Boolean Functions
Venue: arXiv cs.IT 2019
Year: 2019

Vectorial Boolean functions are crucial building blocks in symmetric ciphers. Different known attacks on block ciphers have resulted in diverse cryptographic criteria of vectorial Boolean functions,such as differential distribution table and nonlinearity. Very recently, Bar-On et al. introduced at Eurocrypt'19 a new tool, called the Differential-Linear Connectivity Table (DLCT).This paper is a follow-up work, which presents further theoretical characterization of the DLCT of vectorial Boolean functions and also investigates this new criterion of functions with certain forms. In this paper we introduce a generalized concept of the additive autocorrelation, which is extended from Boolean functions to the vectorial Boolean functions, and use it as a main tool to investigate the DLCT property of vectorial Boolean functions. Firstly, by establishing a connection between the DLCT and the additive autocorrelation, we characterize properties of DLCT by means of the Walsh transform and the differential distribution table, and present generic lower bounds on the differential-linear uniformity (DLU) of vectorial Boolean functions. Furthermore, we investigate the DLCT property of monomials, APN, plateaued and AB functions. Our study reveals that the DLCT of these special functions are closely related to other cryptographic criteria. Next, we prove that the DLU of vectorial Boolean functions is invariant underthe EA equivalence but not invariant under the CCZ equivalence, and that the DLCT spectrum is only invariant under affine equivalence. In addition, under affine equivalence, we exhaust the DLCT spectra and DLU of optimal S-boxes with $4$ bit by Magma. Finally, we investigate the DLCT spectra and DLU of some polynomials over $F_{2^n}$, including the inverse, Gold, Bracken-Leander power functions and all quadratic polynomials.
The Two-Sided Game of Googol and Sample-Based Prophet Inequalities
Venue: arXiv cs.DS 2019
Year: 2019

The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. We consider a variant of the problem and explore its connections to data-driven online selection. Specifically, we are given $n$ cards with arbitrary non-negative numbers written on both sides. The cards are randomly placed on $n$ consecutive positions on a table, and for each card, the visible side is also selected at random. The player sees the visible side of all cards and wants to select the card with the maximum hidden value. To this end, the player flips the first card, sees its hidden value and decides whether to pick it or drop it and continue with the next card. We study algorithms for two natural objectives. In the first one, as in the secretary problem, the player wants to maximize the probability of selecting the maximum hidden value. We show that this can be done with probability at least $0.45292$. In the second one, similar to the prophet inequality, the player maximizes the expectation of the selected hidden value. We show a guarantee of at least $0.63518$ with respect to the expected maximum hidden value. Our algorithms result from combining three basic strategies. One is to stop whenever we see a value larger than the initial $n$ visible numbers. The second one is to stop the first time the last flipped card's value is the largest of the currently $n$ visible numbers in the table. And the third one is similar to the latter but it additionally requires that the last flipped value is larger than the value on the other side of its card. We apply our results to the prophet secretary problem with unknown distributions, but with access to a single sample from each distribution. Our guarantee improves upon $1-1/e$ for this problem, which is the currently best known guarantee and only works for the i.i.d. case.
On linear regression in three-dimensional Euclidean space
Venue: arXiv cs.CG 2019
Year: 2019

The three-dimensional linear regression problem is a problem of finding a spacial straight line best fitting a group of points in three-dimensional Euclidean space. This problem is considered in the present paper and a solution to it is given in a coordinate-free form.
The Futility of Bias-Free Learning and Search
Venue: arXiv cs.LG 2019
Year: 2019

Building on the view of machine learning as search, we demonstrate the necessity of bias in learning, quantifying the role of bias (measured relative to a collection of possible datasets, or more generally, information resources) in increasing the probability of success. For a given degree of bias towards a fixed target, we show that the proportion of favorable information resources is strictly bounded from above. Furthermore, we demonstrate that bias is a conserved quantity, such that no algorithm can be favorably biased towards many distinct targets simultaneously. Thus bias encodes trade-offs. The probability of success for a task can also be measured geometrically, as the angle of agreement between what holds for the actual task and what is assumed by the algorithm, represented in its bias. Lastly, finding a favorably biasing distribution over a fixed set of information resources is provably difficult, unless the set of resources itself is already favorable with respect to the given task and algorithm.
Energy-Efficient Radio Resource Allocation for Federated Edge Learning
Venue: arXiv cs.IT 2019
Year: 2019

Edge machine learning involves the development of learning algorithms at the network edge to leverage massive distributed data and computation resources. Among others, the framework of federated edge learning (FEEL) is particularly promising for its data-privacy preservation. FEEL coordinates global model training at a server and local model training at edge devices over wireless links. In this work, we explore the new direction of energy-efficient radio resource management (RRM) for FEEL. To reduce devices' energy consumption, we propose energy-efficient strategies for bandwidth allocation and scheduling. They adapt to devices' channel states and computation capacities so as to reduce their sum energy consumption while warranting learning performance. In contrast with the traditional rate-maximization designs, the derived optimal policies allocate more bandwidth to those scheduled devices with weaker channels or poorer computation capacities, which are the bottlenecks of synchronized model updates in FEEL. On the other hand, the scheduling priority function derived in closed form gives preferences to devices with better channels and computation capacities. Substantial energy reduction contributed by the proposed strategies is demonstrated in learning experiments.
Multi-Element Long Distance Dependencies: Using SPk Languages to Explore the Characteristics of Long-Distance Dependencies
Venue: arXiv cs.LG 2019
Year: 2019

In order to successfully model Long Distance Dependencies (LDDs) it is necessary to understand the full-range of the characteristics of the LDDs exhibited in a target dataset. In this paper, we use Strictly k-Piecewise languages to generate datasets with various properties. We then compute the characteristics of the LDDs in these datasets using mutual information and analyze the impact of factors such as (i) k, (ii) length of LDDs, (iii) vocabulary size, (iv) forbidden subsequences, and (v) dataset size. This analysis reveal that the number of interacting elements in a dependency is an important characteristic of LDDs. This leads us to the challenge of modelling multi-element long-distance dependencies. Our results suggest that attention mechanisms in neural networks may aide in modeling datasets with multi-element long-distance dependencies. However, we conclude that there is a need to develop more efficient attention mechanisms to address this issue.
Learning better generative models for dexterous, single-view grasping of novel objects
Venue: arXiv cs.RO 2019
Year: 2019

This paper concerns the problem of how to learn to grasp dexterously, so as to be able to then grasp novel objects seen only from a single view-point. Recently, progress has been made in data-efficient learning of generative grasp models which transfer well to novel objects. These generative grasp models are learned from demonstration (LfD). One weakness is that, as this paper shall show, grasp transfer under challenging single view conditions is unreliable. Second, the number of generative model elements rises linearly in the number of training examples. This, in turn, limits the potential of these generative models for generalisation and continual improvement. In this paper, it is shown how to address these problems. Several technical contributions are made: (i) a view-based model of a grasp; (ii) a method for combining and compressing multiple grasp models; (iii) a new way of evaluating contacts that is used both to generate and to score grasps. These, together, improve both grasp performance and reduce the number of models learned for grasp transfer. These advances, in turn, also allow the introduction of autonomous training, in which the robot learns from self-generated grasps. Evaluation on a challenging test set shows that, with innovations (i)-(iii) deployed, grasp transfer success rises from 55.1% to 81.6%. By adding autonomous training this rises to 87.8%. These differences are statistically significant. In total, across all experiments, 539 test grasps were executed on real objects.
Automated Gaming Pommerman: FFA
Venue: arXiv cs.AI 2019
Year: 2019

Our game Pommerman is based on the console game Bommerman. The game starts on an 11 by 11 platform. Pommerman is a multi-agent environment and is made up of a set of different situations and contains four agents.
Supporting Security Sensitive Tenants in a Bare-Metal Cloud
Venue: arXiv cs.DC 2019
Year: 2019

Bolted is a new architecture for bare-metal clouds that enables tenants to control tradeoffs between security, price, and performance. Security-sensitive tenants can minimize their trust in the public cloud provider and achieve similar levels of security and control that they can obtain in their own private data centers. At the same time, Bolted neither imposes overhead on tenants that are security insensitive nor compromises the flexibility or operational efficiency of the provider. Our prototype exploits a novel provisioning system and specialized firmware to enable elasticity similar to virtualized clouds. Experimentally we quantify the cost of different levels of security for a variety of workloads and demonstrate the value of giving control to the tenant.
A Versatile Software Systolic Execution Model for GPU Memory-Bound Kernels
Venue: arXiv cs.DC 2019
Year: 2019

This paper proposes a versatile high-performance execution model, inspired by systolic arrays, for memory-bound regular kernels running on CUDA-enabled GPUs. We formulate a systolic model that shifts partial sums by CUDA warp primitives for the computation. We also employ register files as a cache resource in order to operate the entire model efficiently. We demonstrate the effectiveness and versatility of the proposed model for a wide variety of stencil kernels that appear commonly in HPC, and also convolution kernels (increasingly important in deep learning workloads). Our algorithm outperforms the top reported state-of-the-art stencil implementations, including implementations with sophisticated temporal and spatial blocking techniques, on the two latest Nvidia architectures: Tesla V100 and P100. For 2D convolution of general filter sizes and shapes, our algorithm is on average 2.5x faster than Nvidia's NPP on V100 and P100 GPUs.
Zeros of ferromagnetic 2-spin systems
Venue: arXiv cs.DS 2019
Year: 2019

We study zeros of the partition functions of ferromagnetic 2-state spin systems in terms of the external field, and obtain new zero-free regions of these systems via a refinement of Asano's and Ruelle's contraction method. The strength of our results is that they do not depend on the maximum degree of the underlying graph. Via Barvinok's method, we also obtain new efficient and deterministic approximate counting algorithms. In certain regimes, our algorithm outperforms all other methods such as Markov chain Monte Carlo and correlation decay.
Modeling the Uncertainty in Electronic Health Records: a Bayesian Deep Learning Approach
Venue: arXiv cs.LG 2019
Year: 2019

Deep learning models have exhibited superior performance in predictive tasks with the explosively increasing Electronic Health Records (EHR). However, due to the lack of transparency, behaviors of deep learning models are difficult to interpret. Without trustworthiness, deep learning models will not be able to assist in the real-world decision-making process of healthcare issues. We propose a deep learning model based on Bayesian Neural Networks (BNN) to predict uncertainty induced by data noise. The uncertainty is introduced to provide model predictions with an extra level of confidence. Our experiments verify that instances with high uncertainty are harmful to model performance. Moreover, by investigating the distributions of model prediction and uncertainty, we show that it is possible to identify a group of patients for timely intervention, such that decreasing data noise will benefit more on the prediction accuracy for these patients.
Compressed Subspace Learning Based on Canonical Angle Preserving Property
Venue: arXiv cs.LG 2019
Year: 2019

Union of Subspaces (UoS) is a popular model to describe the underlying low-dimensional structure of data. The fine details of UoS structure can be described in terms of canonical angles (also known as principal angles) between subspaces, which is a well-known characterization for relative subspace positions. In this paper, we prove that random projection with the so-called Johnson-Lindenstrauss (JL) property approximately preserves canonical angles between subspaces with overwhelming probability. This result indicates that random projection approximately preserves the UoS structure. Inspired by this result, we propose a framework of Compressed Subspace Learning (CSL), which enables to extract useful information from the UoS structure of data in a greatly reduced dimension. We demonstrate the effectiveness of CSL in various subspace-related tasks such as subspace visualization, active subspace detection, and subspace clustering.
The FAST Algorithm for Submodular Maximization
Venue: arXiv cs.LG 2019
Year: 2019

In this paper we describe a new algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint $k$ whose approximation ratio is arbitrarily close to $1-1/e$, is $O(\log(n) \log^2(\log k))$ adaptive, and uses a total of $O(n \log\log(k))$ queries. Recent algorithms have comparable guarantees in terms of asymptotic worst case analysis, but their actual number of rounds and query complexity depend on very large constants and polynomials in terms of precision and confidence, making them impractical for large data sets. Our main contribution is a design that is extremely efficient both in terms of its non-asymptotic worst case query complexity and number of rounds, and in terms of its practical runtime. We show that this algorithm outperforms any algorithm for submodular maximization we are aware of, including hyper-optimized parallel versions of state-of-the-art serial algorithms, by running experiments on large data sets. These experiments show FAST is orders of magnitude faster than the state-of-the-art.
An Approach Based on Bayesian Networks for Query Selectivity Estimation
Venue: arXiv cs.DB 2019
Year: 2019

The efficiency of a query execution plan depends on the accuracy of the selectivity estimates given to the query optimiser by the cost model. The cost model makes simplifying assumptions in order to produce said estimates in a timely manner. These assumptions lead to selectivity estimation errors that have dramatic effects on the quality of the resulting query execution plans. A convenient assumption that is ubiquitous among current cost models is to assume that attributes are independent with each other. However, it ignores potential correlations which can have a huge negative impact on the accuracy of the cost model. In this paper we attempt to relax the attribute value independence assumption without unreasonably deteriorating the accuracy of the cost model. We propose a novel approach based on a particular type of Bayesian networks called Chow-Liu trees to approximate the distribution of attribute values inside each relation of a database. Our results on the TPC-DS benchmark show that our method is an order of magnitude more precise than other approaches whilst remaining reasonably efficient in terms of time and space.
Myers-Briggs Personality Classification and Personality-Specific Language Generation Using Pre-trained Language Models
Venue: arXiv cs.LG 2019
Year: 2019

The Myers-Briggs Type Indicator (MBTI) is a popular personality metric that uses four dichotomies as indicators of personality traits. This paper examines the use of pre-trained language models to predict MBTI personality types based on scraped labeled texts. The proposed model reaches an accuracy of $0.47$ for correctly predicting all 4 types and $0.86$ for correctly predicting at least 2 types. Furthermore, we investigate the possible uses of a fine-tuned BERT model for personality-specific language generation. This is a task essential for both modern psychology and for intelligent empathetic systems.
Entanglement-assisted Quantum Codes from Algebraic Geometry Codes
Venue: arXiv cs.IT 2019
Year: 2019

Quantum error correcting codes play the role of suppressing noise and decoherence in quantum systems by introducing redundancy. Some strategies can be used to improve the parameters of these codes. For example, entanglement can provide a way for quantum error correcting codes to achieve higher rates than the one obtained via the traditional stabilizer formalism. Such codes are called entanglement-assisted quantum (QUENTA) codes. In this paper, we use algebraic geometry codes to construct several families of QUENTA codes via the Euclidean and the Hermitian construction. Two of the families created have maximal entanglement and have quantum Singleton defect equal to zero or one. Comparing the other families with the codes with the respective quantum Gilbert-Varshamov bound, we show that our codes have a rate that surpasses that bound. At the end, asymptotically good towers of linear complementary dual codes are used to obtain asymptotically good families of maximal entanglement QUENTA codes. Furthermore, a simple comparison with the quantum Gilbert-Varshamov bound demonstrates that using our construction it is possible to create an asymptotically family of QUENTA codes that exceeds this bound.
What does it mean to understand a neural network?
Venue: arXiv cs.LG 2019
Year: 2019

We can define a neural network that can learn to recognize objects in less than 100 lines of code. However, after training, it is characterized by millions of weights that contain the knowledge about many object types across visual scenes. Such networks are thus dramatically easier to understand in terms of the code that makes them than the resulting properties, such as tuning or connections. In analogy, we conjecture that rules for development and learning in brains may be far easier to understand than their resulting properties. The analogy suggests that neuroscience would benefit from a focus on learning and development.
A Comparison of Visualizations for Identifying Correlation over Space and Time
Venue: arXiv cs.HC 2019
Year: 2019

Observing the relationship between two or more variables over space and time is essential in many domains. For instance, looking, for different countries, at the evolution of both the life expectancy at birth and the fertility rate will give an overview of their demographics. The choice of visual representation for such multivariate data is key to enabling analysts to extract patterns and trends. Prior work has compared geo-temporal visualization techniques for a single thematic variable that evolves over space and time, or for two variables at a specific point in time. But how effective visualization techniques are at communicating correlation between two variables that evolve over space and time remains to be investigated. We report on a study comparing three techniques that are representative of different strategies to visualize geo-temporal multivariate data: either juxtaposing all locations for a given time step, or juxtaposing all time steps for a given location; and encoding thematic attributes either using symbols overlaid on top of map features, or using visual channels of the map features themselves. Participants performed a series of tasks that required them to identify if two variables were correlated over time and if there was a pattern in their evolution. Tasks varied in granularity for both dimensions: time (all time steps, a subrange of steps, one step only) and space (all locations, locations in a subregion, one location only). Our results show that a visualization's effectiveness depends strongly on the task to be carried out. Based on these findings we present a set of design guidelines about geo-temporal visualization techniques for communicating correlation.
Naver Labs Europe's Systems for the WMT19 Machine Translation Robustness Task
Venue: arXiv cs.CL 2019
Year: 2019

This paper describes the systems that we submitted to the WMT19 Machine Translation robustness task. This task aims to improve MT's robustness to noise found on social media, like informal language, spelling mistakes and other orthographic variations. The organizers provide parallel data extracted from a social media website in two language pairs: French-English and Japanese-English (in both translation directions). The goal is to obtain the best scores on unseen test sets from the same source, according to automatic metrics (BLEU) and human evaluation. We proposed one single and one ensemble system for each translation direction. Our ensemble models ranked first in all language pairs, according to BLEU evaluation. We discuss the pre-processing choices that we made, and present our solutions for robustness to noise and domain adaptation.
General Board Game Playing for Education and Research in Generic AI Game Learning
Venue: arXiv cs.AI 2019
Year: 2019

We present a new general board game (GBG) playing and learning framework. GBG defines the common interfaces for board games, game states and their AI agents. It allows one to run competitions of different agents on different games. It standardizes those parts of board game playing and learning that otherwise would be tedious and repetitive parts in coding. GBG is suitable for arbitrary 1-, 2-, ..., N-player board games. It makes a generic TD($λ$)-n-tuple agent for the first time available to arbitrary games. On various games, TD($λ$)-n-tuple is found to be superior to other generic agents like MCTS. GBG aims at the educational perspective, where it helps students to start faster in the area of game learning. GBG aims as well at the research perspective by collecting a growing set of games and AI agents to assess their strengths and generalization capabilities in meaningful competitions. Initial successful educational and research results are reported.