OpenRaiser/Intern-Atlas huggingface dataset:
Quantitative Overfitting Management for Human-in-the-loop ML Application Development with ease.ml/meter
Venue: arXiv cs.LG 2019
Year: 2019

Simplifying machine learning (ML) application development, including distributed computation, programming interface, resource management, model selection, etc, has attracted intensive interests recently. These research efforts have significantly improved the efficiency and the degree of automation of developing ML models. In this paper, we take a first step in an orthogonal direction towards automated quality management for human-in-the-loop ML application development. We build ease. ml/meter, a system that can automatically detect and measure the degree of overfitting during the whole lifecycle of ML application development. ease. ml/meter returns overfitting signals with strong probabilistic guarantees, based on which developers can take appropriate actions. In particular, ease. ml/meter provides principled guidelines to simple yet nontrivial questions regarding desired validation and test data sizes, which are among commonest questions raised by developers. The fact that ML application development is typically a continuous procedure further worsens the situation: The validation and test data sets can lose their statistical power quickly due to multiple accesses, especially in the presence of adaptive analysis. ease. ml/meter addresses these challenges by leveraging a collection of novel techniques and optimizations, resulting in practically tractable data sizes without compromising the probabilistic guarantees. We present the design and implementation details of ease. ml/meter, as well as detailed theoretical analysis and empirical evaluation of its effectiveness.
Automated Video Game Testing Using Synthetic and Human-Like Agents
Venue: arXiv cs.AI 2019
Year: 2019

In this paper, we present a new methodology that employs tester agents to automate video game testing. We introduce two types of agents -synthetic and human-like- and two distinct approaches to create them. Our agents are derived from Reinforcement Learning (RL) and Monte Carlo Tree Search (MCTS) agents, but focus on finding defects. The synthetic agent uses test goals generated from game scenarios, and these goals are further modified to examine the effects of unintended game transitions. The human-like agent uses test goals extracted by our proposed multiple greedy-policy inverse reinforcement learning (MGP-IRL) algorithm from tester trajectories. MGPIRL captures multiple policies executed by human testers. These testers' aims are finding defects while interacting with the game to break it, which is considerably different from game playing. We present interaction states to model such interactions. We use our agents to produce test sequences, run the game with these sequences, and check the game for each run with an automated test oracle. We analyze the proposed method in two parts: we compare the success of human-like and synthetic agents in bug finding, and we evaluate the similarity between humanlike agents and human testers. We collected 427 trajectories from human testers using the General Video Game Artificial Intelligence (GVG-AI) framework and created three games with 12 levels that contain 45 bugs. Our experiments reveal that human-like and synthetic agents compete with human testers' bug finding performances. Moreover, we show that MGP-IRL increases the human-likeness of agents while improving the bug finding performance.
Approximate degree, secret sharing, and concentration phenomena
Venue: arXiv cs.CC 2019
Year: 2019

The $ε$-approximate degree $deg_ε(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $ε$. The approximate degree of $f$ is at least $k$ iff there exists a pair of probability distributions, also known as a dual polynomial, that are perfectly $k$-wise indistinguishable, but are distinguishable by $f$ with advantage $1 - ε$. Our contributions are: We give a simple new construction of a dual polynomial for the AND function, certifying that $deg_ε(f) \geq Ω(\sqrt{n \log 1/ε})$. This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the $1/3$-approximate degree of any read-once DNF is $Ω(\sqrt{n})$. We show that any pair of symmetric distributions on $n$-bit strings that are perfectly $k$-wise indistinguishable are also statistically $K$-wise indistinguishable with error at most $K^{3/2} \cdot \exp(-Ω(k^2/K))$ for all $k < K < n/64$. This implies that any symmetric function $f$ is a reconstruction function with constant advantage for a ramp secret sharing scheme that is secure against size-$K$ coalitions with statistical error $K^{3/2} \exp(-Ω(deg_{1/3}(f)^2/K))$ for all values of $K$ up to $n/64$ simultaneously. Previous secret sharing schemes required that $K$ be determined in advance, and only worked for $f=$ AND. Our analyses draw new connections between approximate degree and concentration phenomena. As a corollary, we show that for any $d < n/64$, any degree $d$ polynomial approximating a symmetric function $f$ to error $1/3$ must have $\ell_1$-norm at least $K^{-3/2} \exp({Ω(deg_{1/3}(f)^2/d)})$, which we also show to be tight for any $d > deg_{1/3}(f)$. These upper and lower bounds were also previously only known in the case $f=$ AND.
Sparse Matrix to Matrix Multiplication: A Representation and Architecture for Acceleration (long version)
Venue: arXiv cs.AR 2019
Year: 2019

Accelerators for sparse matrix multiplication are important components in emerging systems. In this paper, we study the main challenges of accelerating Sparse Matrix Multiplication (SpMM). For the situations that data is not stored in the desired order (row/column order), we propose a compact high performance sparse format, which allows for random access to a dataset with low memory access overhead. We show that using this format results in a 14-49 times speedup for SpMM. Next, we propose a high performance systolic architecture for SpMM, which uses a mesh of comparators to locate the useful (non-zero) computation. This design maximizes data reuse by sharing the input data among a row/column of the mesh. We also show that, with similar memory access assumptions, the proposed architecture results in a 9-30 times speedup in comparison with the state of the art.
Adversarial Examples for Edge Detection: They Exist, and They Transfer
Venue: arXiv cs.CV 2019
Year: 2019

Convolutional neural networks have recently advanced the state of the art in many tasks including edge and object boundary detection. However, in this paper, we demonstrate that these edge detectors inherit a troubling property of neural networks: they can be fooled by adversarial examples. We show that adding small perturbations to an image causes HED, a CNN-based edge detection model, to fail to locate edges, to detect nonexistent edges, and even to hallucinate arbitrary configurations of edges. More surprisingly, we find that these adversarial examples transfer to other CNN-based vision models. In particular, attacks on edge detection result in significant drops in accuracy in models trained to perform unrelated, high-level tasks like image classification and semantic segmentation. Our code will be made public.
Efficient Algorithms for Densest Subgraph Discovery
Venue: arXiv cs.DB 2019
Year: 2019

Densest subgraph discovery (DSD) is a fundamental problem in graph mining. It has been studied for decades, and is widely used in various areas, including network science, biological analysis, and graph databases. Given a graph G, DSD aims to find a subgraph D of G with the highest density (e.g., the number of edges over the number of vertices in D). Because DSD is difficult to solve, we propose a new solution paradigm in this paper. Our main observation is that a densest subgraph can be accurately found through a k-core (a kind of dense subgraph of G), with theoretical guarantees. Based on this intuition, we develop efficient exact and approximation solutions for DSD. Moreover, our solutions are able to find the densest subgraphs for a wide range of graph density definitions, including clique-based and general pattern-based density. We have performed extensive experimental evaluation on eleven real datasets. Our results show that our algorithms are up to four orders of magnitude faster than existing approaches.
Linear Model-Predictive Controller (LMPC) for Building's Heating Ventilation and Air Conditioning (HVAC) System
Venue: arXiv cs.SY 2019
Year: 2019

Model predictive control (MPC) is a widely used technique for temperature set-point tracking and energy optimization of Heating Ventilation and Air Conditioning (HVAC) systems in buildings. Unfortunately, a nonlinear thermal building model leads to a computationally expensive nonlinear MPC problem that is not suitable for real-time control and optimization. This paper presents a novel approximate linearized model for building's thermal dynamics and the HVAC system power consumption that leads to a computationally efficient linear model predictive controller (LMPC) for the buildings' HVAC systems. We employ feedback linearization technique to obtain an equivalent linearized model for the nonlinear thermal building dynamics and use constraint mapping approach to obtain a linearized formulation for new control variables. Next, using piecewise linearization, we obtain a linearized analytical model for the HVAC system power consumption. The proposed LMPC technique is validated using multiple simulation case studies. We demonstrate that the proposed LMPC technique is not only computationally efficient but also accurately approximates the nonlinear optimal control decisions.
Plain English Summarization of Contracts
Venue: arXiv cs.CL 2019
Year: 2019

Unilateral contracts, such as terms of service, play a substantial role in modern digital life. However, few users read these documents before accepting the terms within, as they are too long and the language too complicated. We propose the task of summarizing such legal documents in plain English, which would enable users to have a better understanding of the terms they are accepting. We propose an initial dataset of legal text snippets paired with summaries written in plain English. We verify the quality of these summaries manually and show that they involve heavy abstraction, compression, and simplification. Initial experiments show that unsupervised extractive summarization methods do not perform well on this task due to the level of abstraction and style differences. We conclude with a call for resource and technique development for simplification and style transfer for legal language.
An Empirical Study on Hyperparameters and their Interdependence for RL Generalization
Venue: arXiv cs.LG 2019
Year: 2019

Recent results in Reinforcement Learning (RL) have shown that agents with limited training environments are susceptible to a large amount of overfitting across many domains. A key challenge for RL generalization is to quantitatively explain the effects of changing parameters on testing performance. Such parameters include architecture, regularization, and RL-dependent variables such as discount factor and action stochasticity. We provide empirical results that show complex and interdependent relationships between hyperparameters and generalization. We further show that several empirical metrics such as gradient cosine similarity and trajectory-dependent metrics serve to provide intuition towards these results.
Dimensionality compression and expansion in Deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Datasets such as images, text, or movies are embedded in high-dimensional spaces. However, in important cases such as images of objects, the statistical structure in the data constrains samples to a manifold of dramatically lower dimensionality. Learning to identify and extract task-relevant variables from this embedded manifold is crucial when dealing with high-dimensional problems. We find that neural networks are often very effective at solving this task and investigate why. To this end, we apply state-of-the-art techniques for intrinsic dimensionality estimation to show that neural networks learn low-dimensional manifolds in two phases: first, dimensionality expansion driven by feature generation in initial layers, and second, dimensionality compression driven by the selection of task-relevant features in later layers. We model noise generated by Stochastic Gradient Descent and show how this noise balances the dimensionality of neural representations by inducing an effective regularization term in the loss. We highlight the important relationship between low-dimensional compressed representations and generalization properties of the network. Our work contributes by shedding light on the success of deep neural networks in disentangling data in high-dimensional space while achieving good generalization. Furthermore, it invites new learning strategies focused on optimizing measurable geometric properties of learned representations, beginning with their intrinsic dimensionality.
Minimax bounds for structured prediction
Venue: arXiv cs.LG 2019
Year: 2019

Structured prediction can be considered as a generalization of many standard supervised learning tasks, and is usually thought as a simultaneous prediction of multiple labels. One standard approach is to maximize a score function on the space of labels, which decomposes as a sum of unary and pairwise potentials, each depending on one or two specific labels, respectively. For this approach, several learning and inference algorithms have been proposed over the years, ranging from exact to approximate methods while balancing the computational complexity. However, in contrast to binary and multiclass classification, results on the necessary number of samples for achieving learning is still limited, even for a specific family of predictors such as factor graphs. In this work, we provide minimax bounds for a class of factor-graph inference models for structured prediction. That is, we characterize the necessary sample complexity for any conceivable algorithm to achieve learning of factor-graph predictors.
Classification of Crop Tolerance to Heat and Drought: A Deep Convolutional Neural Networks Approach
Venue: arXiv cs.LG 2019
Year: 2019

Environmental stresses such as drought and heat can cause substantial yield loss in agriculture. As such, hybrid crops that are tolerant to drought and heat stress would produce more consistent yields compared to the hybrids that are not tolerant to these stresses. In the 2019 Syngenta Crop Challenge, Syngenta released several large datasets that recorded the yield performances of 2,452 corn hybrids planted in 1,560 locations between 2008 and 2017 and asked participants to classify the corn hybrids as either tolerant or susceptible to drought stress, heat stress, and combined drought and heat stress. However, no data was provided that classified any set of hybrids as tolerant or susceptible to any type of stress. In this paper, we present an unsupervised approach to solving this problem, which was recognized as one of the winners in the 2019 Syngenta Crop Challenge. Our results labeled 121 hybrids as drought tolerant, 193 as heat tolerant, and 29 as tolerant to both stresses.
On the Use of Randomness in Local Distributed Graph Algorithms
Venue: arXiv cs.DS 2019
Year: 2019

We attempt to better understand randomization in local distributed graph algorithms by exploring how randomness is used and what we can gain from it: - We first ask the question of how much randomness is needed to obtain efficient randomized algorithms. We show that for all locally checkable problems for which polylog $n$-time randomized algorithms exist, there are such algorithms even if either (I) there is a only a single (private) independent random bit in each polylog $n$-neighborhood of the graph, (II) the (private) bits of randomness of different nodes are only polylog $n$-wise independent, or (III) there are only polylog $n$ bits of global shared randomness (and no private randomness). - Second, we study how much we can improve the error probability of randomized algorithms. For all locally checkable problems for which polylog $n$-time randomized algorithms exist, we show that there are such algorithms that succeed with probability $1-n^{-2^{\varepsilon(\log\log n)^2}}$ and more generally $T$-round algorithms, for $T\geq$ polylog $n$, that succeed with probability $1-n^{-2^{\varepsilon\log^2T}}$. We also show that polylog $n$-time randomized algorithms with success probability $1-2^{-2^{\log^\varepsilon n}}$ for some $\varepsilon>0$ can be derandomized to polylog $n$-time deterministic algorithms. Both of the directions mentioned above, reducing the amount of randomness and improving the success probability, can be seen as partial derandomization of existing randomized algorithms. In all the above cases, we also show that any significant improvement of our results would lead to a major breakthrough, as it would imply significantly more efficient deterministic distributed algorithms for a wide class of problems.
Efficient 8-Bit Quantization of Transformer Neural Machine Language Translation Model
Venue: arXiv cs.LG 2019
Year: 2019

In this work, we quantize a trained Transformer machine language translation model leveraging INT8/VNNI instructions in the latest Intel$^\circledR$ Xeon$^\circledR$ Cascade Lake processors to improve inference performance while maintaining less than 0.5$\%$ drop in accuracy. To the best of our knowledge, this is the first attempt in the industry to quantize the Transformer model. This has high impact as it clearly demonstrates the various complexities of quantizing the language translation model. We present novel quantization techniques directly in TensorFlow to opportunistically replace 32-bit floating point (FP32) computations with 8-bit integers (INT8) and transform the FP32 computational graph. We also present a bin-packing parallel batching technique to maximize CPU utilization. Overall, our optimizations with INT8/VNNI deliver 1.5X improvement over the best FP32 performance. Furthermore, it reveals the opportunities and challenges to boost performance of quantized deep learning inference and establishes best practices to run inference with high efficiency on Intel CPUs.
Information-Theoretic Privacy through Chaos Synchronization and Optimal Additive Noise
Venue: arXiv cs.SY 2019
Year: 2019

We study the problem of maximizing privacy of data sets by adding random vectors generated via synchronized chaotic oscillators. In particular, we consider the setup where information about data sets, queries, is sent through public (unsecured) communication channels to a remote station. To hide private features (specific entries) within the data set, we corrupt the response to queries by adding random vectors. We send the distorted query (the sum of the requested query and the random vector) through the public channel. The distribution of the additive random vector is designed to minimize the mutual information (our privacy metric) between private entries of the data set and the distorted query. We cast the synthesis of this distribution as a convex program in the probabilities of the additive random vector. Once we have the optimal distribution, we propose an algorithm to generate pseudo-random realizations from this distribution using trajectories of a chaotic oscillator. At the other end of the channel, we have a second chaotic oscillator, which we use to generate realizations from the same distribution. Note that if we obtain the same realizations on both sides of the channel, we can simply subtract the realization from the distorted query to recover the requested query. To generate equal realizations, we need the two chaotic oscillators to be synchronized, i.e., we need them to generate exactly the same trajectories on both sides of the channel synchronously in time. We force the two chaotic oscillators into exponential synchronization using a driving signal. Simulations are presented to illustrate our results.
Sponsored data with ISP competition
Venue: arXiv cs.NI 2019
Year: 2019

We analyze the effect of sponsored data platforms when Internet service providers (ISPs) compete for subscribers and content providers (CPs) compete for a share of the bandwidth usage by the customers. Our analytical model is of a full information, leader-follower game. ISPs lead and set prices for sponsorship. CPs then make the binary decision of sponsoring or not sponsoring their content on the ISPs. Lastly, based on both of these, users make a two-part decision of choosing the ISP to which they subscribe, and the amount of data to consume from each of the CPs through the chosen ISP. User consumption is determined by a utility maximization framework, the sponsorship decision is determined by a non-cooperative game between the CPs, and the ISPs set their prices to maximize their profit in response to the prices set by the competing ISP. We analyze the pricing dynamics of the prices set by the ISPs, the sponsorship decisions that the CPs make and the market structure therein, and the surpluses of the ISPs, CPs, and users. This is the first analysis of the effect sponsored data platforms in the presence of ISP competition. We show that inter-ISP competition does not inhibit ISPs from extracting a significant fraction of the CP surplus. Moreover, the ISPs often have an incentive to significantly skew the CP marketplace in favor of the most profitable CP.
Apprentissage de la pensée informatique : de la formation des enseignant$\cdot$e$\cdot$s à la formation de tou$\cdot$te$\cdot$s les citoyen$\cdot$ne$\cdot$s
Venue: arXiv cs.CY 2019
Year: 2019

In recent years, in France, computer learning (under the term of code) has entered the school curriculum, in primary and high school. This learning is also aimed at developing computer thinking to enable students, girls and boys, to start master all aspects of the digital world (science, technology, industry, culture). However, neither teachers, nor parents are trained to teach or educate on these topics. Furthermore, if the educational system progresses progressively towards these objectives, in everyday life and in professional context there is also a need for lifelong training in computer thinking. Large-scale projects on coding initiation are now quite successful in supporting the training of professionals in education on these topics. However, they require an infrastructure of people and important resources to maintain their level of efficiency. In order to further develop the objectives ofhelping people to demystify IT thinking, we aim to question here the way by which it is possible to conceive a concrete and operational initiative that addresses this issue. A huge challenge: Let's share a proposal here and discuss it.