OpenRaiser/Intern-Atlas huggingface dataset:
Argumentation for Explainable Scheduling (Full Paper with Proofs)
Venue: arXiv cs.AI 2019
Year: 2019

Mathematical optimization offers highly-effective tools for finding solutions for problems with well-defined goals, notably scheduling. However, optimization solvers are often unexplainable black boxes whose solutions are inaccessible to users and which users cannot interact with. We define a novel paradigm using argumentation to empower the interaction between optimization solvers and users, supported by tractable explanations which certify or refute solutions. A solution can be from a solver or of interest to a user (in the context of 'what-if' scenarios). Specifically, we define argumentative and natural language explanations for why a schedule is (not) feasible, (not) efficient or (not) satisfying fixed user decisions, based on models of the fundamental makespan scheduling problem in terms of abstract argumentation frameworks (AFs). We define three types of AFs, whose stable extensions are in one-to-one correspondence with schedules that are feasible, efficient and satisfying fixed decisions, respectively. We extract the argumentative explanations from these AFs and the natural language explanations from the argumentative ones.
Grid-less Variational Bayesian Inference of Line Spectral from Quantized Samples
Venue: arXiv cs.IT 2019
Year: 2019

Efficient estimation of line spectral from quantized samples is of significant importance in information theory and signal processing, e.g., channel estimation in energy efficient massive MIMO systems and direction of arrival estimation. The goal of this paper is to recover the line spectral as well as its corresponding parameters including the model order, frequencies and amplitudes from heavily quantized samples. To this end, we propose an efficient grid-less Bayesian algorithm named VALSE-EP, which is a combination of the variational line spectral estimation (VALSE) and expectation propagation (EP). The basic idea of VALSE-EP is to iteratively approximate the challenging quantized model of line spectral estimation as a sequence of simple pseudo unquantized models so that the VALSE can be applied. Note that the noise in the pseudo linear model is heteroscedastic, i.e., different components having different variances, and a variant of the VALSE is re-derived to obtain the final VALSE-EP. Moreover, to obtain a benchmark performance of the proposed algorithm, the Cramér Rao bound (CRB) is derived. Finally, numerical experiments on both synthetic and real data are performed, demonstrating the near CRB performance of the proposed VALSE-EP for line spectral estimation from quantized samples.
The Remarkable Role of Similarity in Redundancy-based Program Repair
Venue: arXiv cs.SE 2019
Year: 2019

Recently, there have been original attempts to use the concept of "code similarity" in program repair, suggesting that similarity analysis has an important role in the repair process. However, there is no dedicated work to characterize and quantify the role of similarity in redundancy-based program repair, where the patch is composed from source code taken from somewhere else. This is where our paper makes a major contribution: we perform a deep and systematic analysis of the role of code similarity during the exploration of the repair search space. We define and set up a large-scale experiment based on four code similarity metrics that capture different similarities: character, token, semantic and structure similarity. Overall, we have computed 56 million similarity score over 15 million source code components. We show that with similarity analysis, at least 90% of search space can be ignored to find the correct patch. Code similarity is capable of ranking the correct repair ingredient first in 4 - 33 % of the considered cases.
Robustness of spectral methods for community detection
Venue: arXiv cs.DS 2019
Year: 2019

The present work is concerned with community detection. Specifically, we consider a random graph drawn according to the stochastic block model~: its vertex set is partitioned into blocks, or communities, and edges are placed randomly and independently of each other with probability depending only on the communities of their two endpoints. In this context, our aim is to recover the community labels better than by random guess, based only on the observation of the graph. In the sparse case, where edge probabilities are in $O(1/n)$, we introduce a new spectral method based on the distance matrix $D^{(l)}$, where $D^{(l)}_{ij} = 1$ iff the graph distance between $i$ and $j$, noted $d(i, j)$ is equal to $\ell$. We show that when $\ell \sim c\log(n)$ for carefully chosen $c$, the eigenvectors associated to the largest eigenvalues of $D^{(l)}$ provide enough information to perform non-trivial community recovery with high probability, provided we are above the so-called Kesten-Stigum threshold. This yields an efficient algorithm for community detection, since computation of the matrix $D^{(l)}$ can be done in $O(n^{1+κ})$ operations for a small constant $κ$. We then study the sensitivity of the eigendecomposition of $D^{(l)}$ when we allow an adversarial perturbation of the edges of $G$. We show that when the considered perturbation does not affect more than $O(n^\varepsilon)$ vertices for some small $\varepsilon > 0$, the highest eigenvalues and their corresponding eigenvectors incur negligible perturbations, which allows us to still perform efficient recovery.
Pitfalls of Graph Neural Network Evaluation
Venue: arXiv cs.LG 2019
Year: 2019

Semi-supervised node classification in graphs is a fundamental problem in graph mining, and the recently proposed graph neural networks (GNNs) have achieved unparalleled results on this task. Due to their massive success, GNNs have attracted a lot of attention, and many novel architectures have been put forward. In this paper we show that existing evaluation strategies for GNN models have serious shortcomings. We show that using the same train/validation/test splits of the same datasets, as well as making significant changes to the training procedure (e.g. early stopping criteria) precludes a fair comparison of different architectures. We perform a thorough empirical evaluation of four prominent GNN models and show that considering different splits of the data leads to dramatically different rankings of models. Even more importantly, our findings suggest that simpler GNN architectures are able to outperform the more sophisticated ones if the hyperparameters and the training procedure are tuned fairly for all models.
Evolving intrinsic motivations for altruistic behavior
Venue: arXiv cs.MA 2019
Year: 2019

Multi-agent cooperation is an important feature of the natural world. Many tasks involve individual incentives that are misaligned with the common good, yet a wide range of organisms from bacteria to insects and humans are able to overcome their differences and collaborate. Therefore, the emergence of cooperative behavior amongst self-interested individuals is an important question for the fields of multi-agent reinforcement learning (MARL) and evolutionary theory. Here, we study a particular class of multi-agent problems called intertemporal social dilemmas (ISDs), where the conflict between the individual and the group is particularly sharp. By combining MARL with appropriately structured natural selection, we demonstrate that individual inductive biases for cooperation can be learned in a model-free way. To achieve this, we introduce an innovative modular architecture for deep reinforcement learning agents which supports multi-level selection. We present results in two challenging environments, and interpret these in the context of cultural and ecological evolution.
A Performance Vocabulary for Affine Loop Transformations
Venue: arXiv cs.DC 2019
Year: 2019

Modern polyhedral compilers excel at aggressively optimizing codes with static control parts, but the state-of-practice to find high-performance polyhedral transformations especially for different hardware targets still largely involves auto-tuning. In this work we propose a novel polyhedral scheduling technique, with the aim to reduce the need for auto-tuning while allowing to build customizable and specific transformation strategies. We design constraints and objectives that model several crucial aspects of performance such as stride optimization or the trade-off between parallelism and reuse, while taking into account important architectural features of the target machine. The developed set of objectives embody a Performance Vocabulary for loop transformations. The goal is to use this vocabulary, consisting of performance idioms, to construct transformation recipes adapted to a number of program classes. We evaluate our work using the PolyBench/C benchmark suite and experimentally validate it against large optimization spaces generated with the Pluto compiler on a 10-core Intel Core-i9 (Skylake-X). Our results show that we can achieve comparable or superior performance to Pluto on the majority of benchmarks, without implementing tiling in the source code nor using experimental autotuning.
Efficient Edge Rewiring Strategies for Enhancement in Network Capacity
Venue: arXiv cs.NI 2019
Year: 2019

The structure of the network has great impact on its traffic dynamics. Most of the real world networks follow the heterogeneous structure and exhibit scale-free feature. In scale-free network, a new node prefers to connect with hub nodes and the network capacity is curtailed by smaller degree nodes. Therefore, we propose rewiring a fraction of links in the network, to improve the network transport efficiency. In this paper, we discuss some efficient link rewiring strategies and perform simulations on scale-free networks, confirming the effectiveness of these strategies. The rewiring strategies actually reduce the centrality of the nodes having higher betweenness centrality. After the link rewiring process, the degree distribution of the network remains the same. This work will be beneficial for the enhancement of network performance.
Minimizing the Age of Information from Sensors with Common Observations
Venue: arXiv cs.IT 2019
Year: 2019

We study the average Age of Information (AoI) in a system where physical sources produce independent discrete-time updates that are each observed by several sensors. We devise a model that is simple, but still capable to capture the main tradeoffs. Two sensor scheduling policies are proposed to minimize the AoI of the sources; one in which the system parameters are assumed known, and one in which they are learned. Both policies are able to exploit the common sensor information to reduce the AoI, resulting in large reductions in AoI compared to common schedules.
CAN: Composite Appearance Network for Person Tracking and How to Model Errors in a Tracking System
Venue: arXiv cs.CV 2019
Year: 2019

Tracking multiple people across multiple cameras is an open problem. It is typically divided into two tasks: (i) single-camera tracking (SCT) - identify trajectories in the same scene, and (ii) inter-camera tracking (ICT) - identify trajectories across cameras for real surveillance scenes. Many methods cater to SCT, while ICT still remains a challenge. In this paper, we propose a tracking method which uses motion cues and a feature aggregation network for template-based person re-identification by incorporating metadata such as person bounding box and camera information. We present a feature aggregation architecture called Composite Appearance Network (CAN) to address the above problem. The key structure of this architecture is called EvalNet that pays attention to each feature vector and learns to weight them based on gradients it receives for the overall template for optimal re-identification performance. We demonstrate the efficiency of our approach with experiments on the challenging multi-camera tracking dataset, DukeMTMC. We also survey existing tracking measures and present an online error metric called "Inference Error" (IE) that provides a better estimate of tracking/re-identification error, by treating SCT and ICT errors uniformly.
Importance of the window function choice for the predictive modelling of memristors
Venue: arXiv cs.ET 2019
Year: 2019

Window functions are widely employed in memristor models to restrict the changes of the internal state variables to specified intervals. Here we show that the actual choice of window function is of significant importance for the predictive modelling of memristors. Using a recently formulated theory of memristor attractors, we demonstrate that whether stable fixed points exist depends on the type of window function used in the model. Our main findings are formulated in terms of two memristor attractor theorems, which apply to broad classes of memristor models. As an example of our findings, we predict the existence of stable fixed points in Biolek window function memristors and their absence in memristors described by the Joglekar window function, when such memristors are driven by periodic alternating polarity pulses. It is anticipated that the results of this study will contribute toward the development of more sophisticated models of memristive devices and systems.
Machine Decisions and Human Consequences
Venue: arXiv cs.CY 2019
Year: 2019

As we increasingly delegate decision-making to algorithms, whether directly or indirectly, important questions emerge in circumstances where those decisions have direct consequences for individual rights and personal opportunities, as well as for the collective good. A key problem for policymakers is that the social implications of these new methods can only be grasped if there is an adequate comprehension of their general technical underpinnings. The discussion here focuses primarily on the case of enforcement decisions in the criminal justice system, but draws on similar situations emerging from other algorithms utilised in controlling access to opportunities, to explain how machine learning works and, as a result, how decisions are made by modern intelligent algorithms or 'classifiers'. It examines the key aspects of the performance of classifiers, including how classifiers learn, the fact that they operate on the basis of correlation rather than causation, and that the term 'bias' in machine learning has a different meaning to common usage. An example of a real world 'classifier', the Harm Assessment Risk Tool (HART), is examined, through identification of its technical features: the classification method, the training data and the test data, the features and the labels, validation and performance measures. Four normative benchmarks are then considered by reference to HART: (a) prediction accuracy (b) fairness and equality before the law (c) transparency and accountability (d) informational privacy and freedom of expression, in order to demonstrate how its technical features have important normative dimensions that bear directly on the extent to which the system can be regarded as a viable and legitimate support for, or even alternative to, existing human decision-makers.
A Constructive Arboricity Approximation Scheme
Venue: arXiv cs.DS 2019
Year: 2019

The arboricity $Γ$ of a graph is the minimum number of forests its edge set can be partitioned into. Previous approximation schemes were nonconstructive, i.e., they only approximated the arboricity as a value without computing a corresponding forest partition. This is because they operate on the related pseudoforest partitions or the dual problem of finding dense subgraphs. We propose an algorithm for converting a partition of $k$ pseudoforests into a partition of $k+1$ forests in $O(mk\log k + m \log n)$ time with a data structure by Brodal and Fagerberg that stores graphs of arboricity $k$. A slightly better bound can be given when perfect hashing is used. When applied to a pseudoforest partition obtained from Kowalik's approximation scheme, our conversion implies a constructive $(1+ε)$-approximation algorithm with runtime $O(m \log n \log Γ\, ε^{-1})$ for every $ε> 0$. For fixed $ε$, the runtime can be reduced to $O(m \log n)$. Our conversion also implies a near-exact algorithm that computes a partition into at most $Γ+2$ forests in $O(m\log n \,Γ\log^* Γ)$ time. It might also pave the way to faster exact arboricity algorithms. We also make several remarks on approximation algorithms for the pseudoarboricity and the equivalent graph orientations with smallest maximum indegree, and correct some mistakes made in the literature.
Projected BNNs: Avoiding weight-space pathologies by learning latent representations of neural network weights
Venue: arXiv cs.LG 2019
Year: 2019

As machine learning systems get widely adopted for high-stake decisions, quantifying uncertainty over predictions becomes crucial. While modern neural networks are making remarkable gains in terms of predictive accuracy, characterizing uncertainty over the parameters of these models is challenging because of the high dimensionality and complex correlations of the network parameter space. This paper introduces a novel variational inference framework for Bayesian neural networks that (1) encodes complex distributions in high-dimensional parameter space with representations in a low-dimensional latent space, and (2) performs inference efficiently on the low-dimensional representations. Across a large array of synthetic and real-world datasets, we show that our method improves uncertainty characterization and model generalization when compared with methods that work directly in the parameter space.
Robust Website Fingerprinting Through the Cache Occupancy Channel
Venue: arXiv cs.CR 2019
Year: 2019

Website fingerprinting attacks, which use statistical analysis on network traffic to compromise user privacy, have been shown to be effective even if the traffic is sent over anonymity-preserving networks such as Tor. The classical attack model used to evaluate website fingerprinting attacks assumes an on-path adversary, who can observe all traffic traveling between the user's computer and the Tor network. In this work we investigate these attacks under a different attack model, in which the adversary is capable of running a small amount of unprivileged code on the target user's computer. Under this model, the attacker can mount cache side-channel attacks, which exploit the effects of contention on the CPU's cache, to identify the website being browsed. In an important special case of this attack model, a JavaScript attack is launched when the target user visits a website controlled by the attacker. The effectiveness of this attack scenario has never been systematically analyzed, especially in the open-world model which assumes that the user is visiting a mix of both sensitive and non-sensitive sites. In this work we show that cache website fingerprinting attacks in JavaScript are highly feasible, even when they are run from highly restrictive environments, such as the Tor Browser. Specifically, we use machine learning techniques to classify traces of cache activity. Unlike prior works, which try to identify cache conflicts, our work measures the overall occupancy of the last-level cache. We show that our approach achieves high classification accuracy in both the open-world and the closed-world models. We further show that our techniques are resilient both to network-based defenses and to side-channel countermeasures introduced to modern browsers as a response to the Spectre attack.
Stacking-Based Deep Neural Network: Deep Analytic Network for Pattern Classification
Venue: arXiv cs.CV 2019
Year: 2019

Stacking-based deep neural network (S-DNN) is aggregated with pluralities of basic learning modules, one after another, to synthesize a deep neural network (DNN) alternative for pattern classification. Contrary to the DNNs trained end to end by backpropagation (BP), each S-DNN layer, i.e., a self-learnable module, is to be trained decisively and independently without BP intervention. In this paper, a ridge regression-based S-DNN, dubbed deep analytic network (DAN), along with its kernelization (K-DAN), are devised for multilayer feature re-learning from the pre-extracted baseline features and the structured features. Our theoretical formulation demonstrates that DAN/K-DAN re-learn by perturbing the intra/inter-class variations, apart from diminishing the prediction errors. We scrutinize the DAN/K-DAN performance for pattern classification on datasets of varying domains - faces, handwritten digits, generic objects, to name a few. Unlike the typical BP-optimized DNNs to be trained from gigantic datasets by GPU, we disclose that DAN/K-DAN are trainable using only CPU even for small-scale training sets. Our experimental results disclose that DAN/K-DAN outperform the present S-DNNs and also the BP-trained DNNs, including multiplayer perceptron, deep belief network, etc., without data augmentation applied.
Dynamic Social Interaction Mechanics CrossAnt
Venue: arXiv cs.HC 2019
Year: 2019

Nowadays, big effort is being put to study gamification and how game elements can be used to engage players. In this scope, we believe there is a growing need to explore the impact game mechanics have on the players' interactions and perception. This work focuses on the application of game mechanics to lead players to achieve certain types of social interaction (we named this type of mechanics social interaction mechanics). A word matching game called CrossAnt was modified so that it could dynamically generate different social interaction mechanics. These mechanics consisted in different key combinations needed to play the game and were aimed to promote what we think are three important types of social interactions: cooperation, competition and individual exploration. Our evaluation consisted on the execution of several sessions where two players interacted with the game for several levels and had to find for themselves how to perform the actions needed to succeed. While some of the levels required the input from both players in order to be completed, others could be completed by each player independently. Our results show that cooperation was perceived when both players had to intervene to perform the game actions. However, longer interactions may still be needed so that the other types of interactions are promoted.
Bayesian Modeling of Intersectional Fairness: The Variance of Bias
Venue: arXiv cs.LG 2019
Year: 2019

Intersectionality is a framework that analyzes how interlocking systems of power and oppression affect individuals along overlapping dimensions including race, gender, sexual orientation, class, and disability. Intersectionality theory therefore implies it is important that fairness in artificial intelligence systems be protected with regard to multi-dimensional protected attributes. However, the measurement of fairness becomes statistically challenging in the multi-dimensional setting due to data sparsity, which increases rapidly in the number of dimensions, and in the values per dimension. We present a Bayesian probabilistic modeling approach for the reliable, data-efficient estimation of fairness with multi-dimensional protected attributes, which we apply to two existing intersectional fairness metrics. Experimental results on census data and the COMPAS criminal justice recidivism dataset demonstrate the utility of our methodology, and show that Bayesian methods are valuable for the modeling and measurement of fairness in an intersectional context.