OpenRaiser/Intern-Atlas huggingface dataset:
SurFree: a fast surrogate-free black-box attack
Venue: arXiv cs.CR 2020
Year: 2020

Machine learning classifiers are critically prone to evasion attacks. Adversarial examples are slightly modified inputs that are then misclassified, while remaining perceptively close to their originals. Last couple of years have witnessed a striking decrease in the amount of queries a black box attack submits to the target classifier, in order to forge adversarials. This particularly concerns the black-box score-based setup, where the attacker has access to top predicted probabilites: the amount of queries went from to millions of to less than a thousand. This paper presents SurFree, a geometrical approach that achieves a similar drastic reduction in the amount of queries in the hardest setup: black box decision-based attacks (only the top-1 label is available). We first highlight that the most recent attacks in that setup, HSJA, QEBA and GeoDA all perform costly gradient surrogate estimations. SurFree proposes to bypass these, by instead focusing on careful trials along diverse directions, guided by precise indications of geometrical properties of the classifier decision boundaries. We motivate this geometric approach before performing a head-to-head comparison with previous attacks with the amount of queries as a first class citizen. We exhibit a faster distortion decay under low query amounts (few hundreds to a thousand), while remaining competitive at higher query budgets.
Bounds for Algorithmic Mutual Information and a Unifilar Order Estimator
Venue: arXiv cs.IT 2020
Year: 2020

Inspired by Hilberg's hypothesis, which states that mutual information between blocks for natural language grows like a power law, we seek for links between power-law growth rate of algorithmic mutual information and of some estimator of the unifilar order, i.e., the number of hidden states in the generating stationary ergodic source in its minimal unifilar hidden Markov representation. We consider an order estimator which returns the smallest order for which the maximum likelihood is larger than a weakly penalized universal probability. This order estimator is intractable and follows the ideas by Merhav, Gutman, and Ziv (1989) and by Ziv and Merhav (1992) but in its exact form seems overlooked despite some nice theoretical properties. In particular, we can prove both strong consistency of this order estimator and an upper bound of algorithmic mutual information in terms of it. Using both results, we show that all (also uncomputable) sources of a finite unifilar order exhibit sub-power-law growth of algorithmic mutual information and of the unifilar order estimator. In contrast, we also exhibit an example of unifilar processes of a countably infinite order, with a deterministic pushdown automaton and an algorithmically random oracle, for which the mentioned two quantities grow as a power law with the same exponent. We also relate our results to natural language research.
Capacity Region of Two-users Weak Gaussian Interference Channel
Venue: arXiv cs.IT 2020
Year: 2020

Computing capacity of Gaussian Interference Channel (GIC) is complex since knowledge of input distributions is needed to find the mutual information terms in closed forms, which should be optimized over input distributions and associated resource allocation. The optimum solution may require dividing the available resources among several GIC (each called a "constituent region", hereafter) and apply time-sharing among them. The current article focuses on a single constituent region (meaning the constraints on resources are all satisfied with equality) for a 2-users weak GIC. It is shown that, by relying on a different, intuitively straightforward, interpretation of the underlying optimization problem, one can determine the encoding/decoding strategies in the process of computing the optimum solution. This is based on gradually moving along the boundary of the capacity region in infinitesimal steps, where the solution for the end point in each step is optimized relying on the solution at the step's starting point. This approach enables proving Gaussian distribution is optimum over the entire boundary, and also allows finding simple closed form solutions describing different parts of the capacity region. The solution for each constituent 2-users GIC coincides with the optimum solution to the Han Kobayashi (HK) system of constraints with i.i.d. (scalar) Gaussian inputs. Although the article is focused on 2-users weak GIC, the proof for optimality of Gaussian distribution is independent of the values of cross gains, and thereby is universally applicable to strong, mixed and Z interference channels, as well as to GIC with more than two users. In addition, the procedure for the construction of boundary is applicable for arbitrary cross gain values, by re-deriving various conditions that have been established assuming cross gains being less than one.
Learning to dance: A graph convolutional adversarial network to generate realistic dance motions from audio
Venue: arXiv cs.GR 2020
Year: 2020

Synthesizing human motion through learning techniques is becoming an increasingly popular approach to alleviating the requirement of new data capture to produce animations. Learning to move naturally from music, i.e., to dance, is one of the more complex motions humans often perform effortlessly. Each dance movement is unique, yet such movements maintain the core characteristics of the dance style. Most approaches addressing this problem with classical convolutional and recursive neural models undergo training and variability issues due to the non-Euclidean geometry of the motion manifold structure.In this paper, we design a novel method based on graph convolutional networks to tackle the problem of automatic dance generation from audio information. Our method uses an adversarial learning scheme conditioned on the input music audios to create natural motions preserving the key movements of different music styles. We evaluate our method with three quantitative metrics of generative methods and a user study. The results suggest that the proposed GCN model outperforms the state-of-the-art dance generation method conditioned on music in different experiments. Moreover, our graph-convolutional approach is simpler, easier to be trained, and capable of generating more realistic motion styles regarding qualitative and different quantitative metrics. It also presented a visual movement perceptual quality comparable to real motion data.
A Comparison of Inquiry-Based Conceptual Feedback vs. Traditional Detailed Feedback Mechanisms in Software Testing Education: An Empirical Investigation
Venue: arXiv cs.SE 2020
Year: 2020

The feedback provided by current testing education tools about the deficiencies in a student's test suite either mimics industry code coverage tools or lists specific instructor test cases that are missing from the student's test suite. While useful in some sense, these types of feedback are akin to revealing the solution to the problem, which can inadvertently encourage students to pursue a trial-and-error approach to testing, rather than using a more systematic approach that encourages learning. In addition to not teaching students why their test suite is inadequate, this type of feedback may motivate students to become dependent on the feedback rather than thinking for themselves. To address this deficiency, there is an opportunity to investigate alternative feedback mechanisms that include a positive reinforcement of testing concepts. We argue that using an inquiry-based learning approach is better than simply providing the answers. To facilitate this type of learning, we present Testing Tutor, a web-based assignment submission platform that supports different levels of testing pedagogy via a customizable feedback engine. We evaluated the impact of the different types of feedback through an empirical study in two sophomore-level courses. We use Testing Tutor to provide students with different types of feedback, either traditional detailed code coverage feedback or inquiry-based learning conceptual feedback, and compare the effects. The results show that students that receive conceptual feedback had higher code coverage (by different measures), fewer redundant test cases, and higher programming grades than the students who receive traditional code coverage feedback.
Augmentation-Interpolative AutoEncoders for Unsupervised Few-Shot Image Generation
Venue: arXiv cs.CV 2020
Year: 2020

We aim to build image generation models that generalize to new domains from few examples. To this end, we first investigate the generalization properties of classic image generators, and discover that autoencoders generalize extremely well to new domains, even when trained on highly constrained data. We leverage this insight to produce a robust, unsupervised few-shot image generation algorithm, and introduce a novel training procedure based on recovering an image from data augmentations. Our Augmentation-Interpolative AutoEncoders synthesize realistic images of novel objects from only a few reference images, and outperform both prior interpolative models and supervised few-shot image generators. Our procedure is simple and lightweight, generalizes broadly, and requires no category labels or other supervision during training.
Non-Rigid Puzzles
Venue: arXiv cs.CV 2020
Year: 2020

Shape correspondence is a fundamental problem in computer graphics and vision, with applications in various problems including animation, texture mapping, robotic vision, medical imaging, archaeology and many more. In settings where the shapes are allowed to undergo non-rigid deformations and only partial views are available, the problem becomes very challenging. To this end, we present a non-rigid multi-part shape matching algorithm. We assume to be given a reference shape and its multiple parts undergoing a non-rigid deformation. Each of these query parts can be additionally contaminated by clutter, may overlap with other parts, and there might be missing parts or redundant ones. Our method simultaneously solves for the segmentation of the reference model, and for a dense correspondence to (subsets of) the parts. Experimental results on synthetic as well as real scans demonstrate the effectiveness of our method in dealing with this challenging matching scenario.
Regret Bounds for Adaptive Nonlinear Control
Venue: arXiv cs.LG 2020
Year: 2020

We study the problem of adaptively controlling a known discrete-time nonlinear system subject to unmodeled disturbances. We prove the first finite-time regret bounds for adaptive nonlinear control with matched uncertainty in the stochastic setting, showing that the regret suffered by certainty equivalence adaptive control, compared to an oracle controller with perfect knowledge of the unmodeled disturbances, is upper bounded by $\widetilde{O}(\sqrt{T})$ in expectation. Furthermore, we show that when the input is subject to a $k$ timestep delay, the regret degrades to $\widetilde{O}(k \sqrt{T})$. Our analysis draws connections between classical stability notions in nonlinear control theory (Lyapunov stability and contraction theory) and modern regret analysis from online convex optimization. The use of stability theory allows us to analyze the challenging infinite-horizon single trajectory setting.
Nearly Complete Characterization of 2-Agent Deterministic Strategyproof Mechanisms for Single Facility Location in $L_p$ Space
Venue: arXiv cs.GT 2020
Year: 2020

We consider the problem of locating a single facility for 2 agents in $L_p$ space ($1<p<\infty$) and give a nearly complete characterization of such deterministic strategyproof mechanisms. We use the distance between an agent and the facility in $L_p$ space to denote the cost of the agent. A mechanism is strategyproof iff no agent can reduce her cost from misreporting her private location. We show that in $L_p$ space ($1<p<\infty$) with 2 agents, any location output of a deterministic, unanimous, translation-invariant strategyproof mechanism must satisfy a set of equations and mechanisms are continuous, scalable. In one-dimensional space, the output must be one agent's location, which is easy to prove in any $n$ agents. However, in $m$-dimensional space ($m\ge 2$), the situation will be much more complex, with only 2-agent case finished. We show that the output of such a mechanism must satisfy a set of equations, and when $p=2$ the output must locate at a sphere with the segment between the two agents as the diameter. Further more, for $n$-agent situations, we find that the simple extension of this the 2-agent situation cannot hold when dimension $m>2$ and prove that the well-known general median mechanism will give an counter-example. Particularly, in $L_2$ (i.e., Euclidean) space with 2 agents, such a mechanism is rotation-invariant iff it is dictatorial; and such a mechanism is anonymous iff it is one of the three mechanisms in Section 4. And our tool implies that any such a mechanism has a tight lower bound of 2-approximation for maximum cost in any multi-dimensional space.
Explainable Tensorized Neural Ordinary Differential Equations forArbitrary-step Time Series Prediction
Venue: arXiv cs.LG 2020
Year: 2020

We propose a continuous neural network architecture, termed Explainable Tensorized Neural Ordinary Differential Equations (ETN-ODE), for multi-step time series prediction at arbitrary time points. Unlike the existing approaches, which mainly handle univariate time series for multi-step prediction or multivariate time series for single-step prediction, ETN-ODE could model multivariate time series for arbitrary-step prediction. In addition, it enjoys a tandem attention, w.r.t. temporal attention and variable attention, being able to provide explainable insights into the data. Specifically, ETN-ODE combines an explainable Tensorized Gated Recurrent Unit (Tensorized GRU or TGRU) with Ordinary Differential Equations (ODE). The derivative of the latent states is parameterized with a neural network. This continuous-time ODE network enables a multi-step prediction at arbitrary time points. We quantitatively and qualitatively demonstrate the effectiveness and the interpretability of ETN-ODE on five different multi-step prediction tasks and one arbitrary-step prediction task. Extensive experiments show that ETN-ODE can lead to accurate predictions at arbitrary time points while attaining best performance against the baseline methods in standard multi-step time series prediction.
Towards Interpretable Multilingual Detection of Hate Speech against Immigrants and Women in Twitter at SemEval-2019 Task 5
Venue: arXiv cs.CL 2020
Year: 2020

his paper describes our techniques to detect hate speech against women and immigrants on Twitter in multilingual contexts, particularly in English and Spanish. The challenge was designed by SemEval-2019 Task 5, where the participants need to design algorithms to detect hate speech in English and Spanish language with a given target (e.g., women or immigrants). Here, we have developed two deep neural networks (Bidirectional Gated Recurrent Unit (GRU), Character-level Convolutional Neural Network (CNN)), and one machine learning model by exploiting the linguistic features. Our proposed model obtained 57 and 75 F1 scores for Task A in English and Spanish language respectively. For Task B, the F1 scores are 67 for English and 75.33 for Spanish. In the case of task A (Spanish) and task B (both English and Spanish), the F1 scores are improved by 2, 10, and 5 points respectively. Besides, we present visually interpretable models that can address the generalizability issues of the custom-designed machine learning architecture by investigating the annotated dataset.
Automatic Optimizations for Stream-based Monitoring Languages
Venue: arXiv cs.FL 2020
Year: 2020

Runtime monitors that are specified in a stream-based monitoring language tend to be easier to understand, maintain, and reuse than those written in a standard programming language. Because of their formal semantics, such specification languages are also a natural choice for safety-critical applications. Unlike for standard programming languages, there is, however, so far very little support for automatic code optimization. In this paper, we present the first collection of code transformations for the stream-based monitoring language RTLola. We show that classic compiler optimizations, such as Sparse Conditional Constant Propagation and Common Subexpression Elimination, can be adapted to monitoring specifications. We also develop new transformations -- Pacing Type Refinement and Filter Refinement -- which exploit the specific modular structure of RTLola as well as the implementation freedom afforded by a declarative specification language. We demonstrate the significant impact of the code transformations on benchmarks from the monitoring of unmanned aircraft systems (UAS).
Prediction in ungauged regions with sparse flow duration curves and input-selection ensemble modeling
Venue: arXiv cs.LG 2020
Year: 2020

While long short-term memory (LSTM) models have demonstrated stellar performance with streamflow predictions, there are major risks in applying these models in contiguous regions with no gauges, or predictions in ungauged regions (PUR) problems. However, softer data such as the flow duration curve (FDC) may be already available from nearby stations, or may become available. Here we demonstrate that sparse FDC data can be migrated and assimilated by an LSTM-based network, via an encoder. A stringent region-based holdout test showed a median Kling-Gupta efficiency (KGE) of 0.62 for a US dataset, substantially higher than previous state-of-the-art global-scale ungauged basin tests. The baseline model without FDC was already competitive (median KGE 0.56), but integrating FDCs had substantial value. Because of the inaccurate representation of inputs, the baseline models might sometimes produce catastrophic results. However, model generalizability was further meaningfully improved by compiling an ensemble based on models with different input selections.
Automatic coding of students' writing via Contrastive Representation Learning in the Wasserstein space
Venue: arXiv cs.LG 2020
Year: 2020

Qualitative analysis of verbal data is of central importance in the learning sciences. It is labor-intensive and time-consuming, however, which limits the amount of data researchers can include in studies. This work is a step towards building a statistical machine learning (ML) method for achieving an automated support for qualitative analyses of students' writing, here specifically in score laboratory reports in introductory biology for sophistication of argumentation and reasoning. We start with a set of lab reports from an undergraduate biology course, scored by a four-level scheme that considers the complexity of argument structure, the scope of evidence, and the care and nuance of conclusions. Using this set of labeled data, we show that a popular natural language modeling processing pipeline, namely vector representation of words, a.k.a word embeddings, followed by Long Short Term Memory (LSTM) model for capturing language generation as a state-space model, is able to quantitatively capture the scoring, with a high Quadratic Weighted Kappa (QWK) prediction score, when trained in via a novel contrastive learning set-up. We show that the ML algorithm approached the inter-rater reliability of human analysis. Ultimately, we conclude, that machine learning (ML) for natural language processing (NLP) holds promise for assisting learning sciences researchers in conducting qualitative studies at much larger scales than is currently possible.
Outcome Indistinguishability
Venue: arXiv cs.LG 2020
Year: 2020

Prediction algorithms assign numbers to individuals that are popularly understood as individual "probabilities" -- what is the probability of 5-year survival after cancer diagnosis? -- and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are Outcome Indistinguishable yield a generative model for outcomes that cannot be efficiently refuted on the basis of the real-life observations produced by Nature. We investigate a hierarchy of Outcome Indistinguishability definitions, whose stringency increases with the degree to which distinguishers may access the predictor in question. Our findings reveal that Outcome Indistinguishability behaves qualitatively differently than previously studied notions of indistinguishability. First, we provide constructions at all levels of the hierarchy. Then, leveraging recently-developed machinery for proving average-case fine-grained hardness, we obtain lower bounds on the complexity of the more stringent forms of Outcome Indistinguishability. This hardness result provides the first scientific grounds for the political argument that, when inspecting algorithmic risk prediction instruments, auditors should be granted oracle access to the algorithm, not simply historical predictions.
Multi-view Human Pose and Shape Estimation Using Learnable Volumetric Aggregation
Venue: arXiv cs.CV 2020
Year: 2020

Human pose and shape estimation from RGB images is a highly sought after alternative to marker-based motion capture, which is laborious, requires expensive equipment, and constrains capture to laboratory environments. Monocular vision-based algorithms, however, still suffer from rotational ambiguities and are not ready for translation in healthcare applications, where high accuracy is paramount. While fusion of data from multiple viewpoints could overcome these challenges, current algorithms require further improvement to obtain clinically acceptable accuracies. In this paper, we propose a learnable volumetric aggregation approach to reconstruct 3D human body pose and shape from calibrated multi-view images. We use a parametric representation of the human body, which makes our approach directly applicable to medical applications. Compared to previous approaches, our framework shows higher accuracy and greater promise for real-time prediction, given its cost efficiency.
ShapeFlow: Dynamic Shape Interpreter for TensorFlow
Venue: arXiv cs.LG 2020
Year: 2020

We present ShapeFlow, a dynamic abstract interpreter for TensorFlow which quickly catches tensor shape incompatibility errors, one of the most common bugs in deep learning code. ShapeFlow shares the same APIs as TensorFlow but only captures and emits tensor shapes, its abstract domain. ShapeFlow constructs a custom shape computational graph, similar to the computational graph used by TensorFlow. ShapeFlow requires no code annotation or code modification by the programmer, and therefore is convenient to use. We evaluate ShapeFlow on 52 programs collected by prior empirical studies to show how fast and accurately it can catch shape incompatibility errors compared to TensorFlow. We use two baselines: a worst-case training dataset size and a more realistic dataset size. ShapeFlow detects shape incompatibility errors highly accurately -- with no false positives and a single false negative -- and highly efficiently -- with an average speed-up of 499X and 24X for the first and second baseline, respectively. We believe ShapeFlow is a practical tool that benefits machine learning developers. We will open-source ShapeFlow on GitHub to make it publicly available to both the developer and research communities.
Towards Movement Generation with Audio Features
Venue: arXiv cs.SD 2020
Year: 2020

Sound and movement are closely coupled, particularly in dance. Certain audio features have been found to affect the way we move to music. Is this relationship between sound and movement something which can be modelled using machine learning? This work presents initial experiments wherein high-level audio features calculated from a set of music pieces are included in a movement generation model trained on motion capture recordings of improvised dance. Our results indicate that the model learns to generate realistic dance movements which vary depending on the audio features.