OpenRaiser/Intern-Atlas huggingface dataset:
A lightweight optimization selection method for Sparse Matrix-Vector Multiplication
Venue: arXiv cs.PF 2016
Year: 2016

In this paper, we propose an optimization selection methodology for the ubiquitous sparse matrix-vector multiplication (SpMV) kernel. We propose two models that attempt to identify the major performance bottleneck of the kernel for every instance of the problem and then select an appropriate optimization to tackle it. Our first model requires online profiling of the input matrix in order to detect its most prevailing performance issue, while our second model only uses comprehensive structural features of the sparse matrix. Our method delivers high performance stability for SpMV across different platforms and sparse matrices, due to its application and architecture awareness. Our experimental results demonstrate that a) our approach is able to distinguish and appropriately optimize special matrices in multicore platforms that fall out of the standard class of memory bandwidth bound matrices, and b) lead to a significant performance gain of 29% in a manycore platform compared to an architecture-centric optimization, as a result of the successful selection of the appropriate optimization for the great majority of the matrices. With a runtime overhead equivalent to a couple dozen SpMV operations, our approach is practical for use in iterative numerical solvers of real-life applications.
Modelling influence and opinion evolution in online collective behaviour
Venue: arXiv cs.SI 2016
Year: 2016

Opinion evolution and judgment revision are mediated through social influence. Based on a large crowdsourced in vitro experiment (n=861), it is shown how a consensus model can be used to predict opinion evolution in online collective behaviour. It is the first time the predictive power of a quantitative model of opinion dynamics is tested against a real dataset. Unlike previous research on the topic, the model was validated on data which did not serve to calibrate it. This avoids to favor more complex models over more simple ones and prevents overfitting. The model is parametrized by the influenceability of each individual, a factor representing to what extent individuals incorporate external judgments. The prediction accuracy depends on prior knowledge on the participants' past behaviour. Several situations reflecting data availability are compared. When the data is scarce, the data from previous participants is used to predict how a new participant will behave. Judgment revision includes unpredictable variations which limit the potential for prediction. A first measure of unpredictability is proposed. The measure is based on a specific control experiment. More than two thirds of the prediction errors are found to occur due to unpredictability of the human judgment revision process rather than to model imperfection.
Totally Unimodular Congestion Games
Venue: arXiv cs.GT 2016
Year: 2016

We investigate a new class of congestion games, called Totally Unimodular (TU) Congestion Games, where the players' strategies are binary vectors inside polyhedra defined by totally unimodular constraint matrices. Network congestion games belong to this class. In the symmetric case, when all players have the same strategy set, we design an algorithm that finds an optimal aggregated strategy and then decomposes it into the single players' strategies. This approach yields strongly polynomial-time algorithms to (i) find a pure Nash equilibrium, and (ii) compute a socially optimal state, if the delay functions are weakly convex. We also show how this technique can be extended to matroid congestion games. We introduce some combinatorial TU congestion games, where the players' strategies are matchings, vertex covers, edge covers, and stable sets of a given bipartite graph. In the asymmetric case, we show that for these games (i) it is PLS-complete to find a pure Nash equilibrium even in case of linear delay functions, and (ii) it is NP-hard to compute a socially optimal state, even in case of weakly convex delay functions.
Learning with a Strong Adversary
Venue: arXiv cs.LG 2016
Year: 2016

The robustness of neural networks to intended perturbations has recently attracted significant attention. In this paper, we propose a new method, \emph{learning with a strong adversary}, that learns robust classifiers from supervised data. The proposed method takes finding adversarial examples as an intermediate step. A new and simple way of finding adversarial examples is presented and experimentally shown to be efficient. Experimental results demonstrate that resulting learning method greatly improves the robustness of the classification models produced.
God(s) Know(s): Developmental and Cross-Cultural Patterns in Children Drawings
Venue: arXiv cs.CV 2016
Year: 2016

This paper introduces a novel approach to data analysis designed for the needs of specialists in psychology of religion. We detect developmental and cross-cultural patterns in children's drawings of God(s) and other supernatural agents. We develop methods to objectively evaluate our empirical observations of the drawings with respect to: (1) the gravity center, (2) the average intensities of the colors \emph{green} and \emph{yellow}, (3) the use of different colors (palette) and (4) the visual complexity of the drawings. We find statistically significant differences across ages and countries in the gravity centers and in the average intensities of colors. These findings support the hypotheses of the experts and raise new questions for further investigation.
Constraint-Tightening and Stability in Stochastic Model Predictive Control
Venue: arXiv cs.SY 2016
Year: 2016

Constraint tightening to non-conservatively guarantee recursive feasibility and stability in Stochastic Model Predictive Control is addressed. Stability and feasibility requirements are considered separately, highlighting the difference between existence of a solution and feasibility of a suitable, a priori known candidate solution. Subsequently, a Stochastic Model Predictive Control algorithm which unifies previous results is derived, leaving the designer the option to balance an increased feasible region against guaranteed bounds on the asymptotic average performance and convergence time. Besides typical performance bounds, under mild assumptions, we prove asymptotic stability in probability of the minimal robust positively invariant set obtained by the unconstrained LQ-optimal controller. A numerical example, demonstrating the efficacy of the proposed approach in comparison with classical, recursively feasible Stochastic MPC and Robust MPC, is provided.
Direct Polarization for q-ary Source and Channel Coding
Venue: arXiv cs.IT 2016
Year: 2016

It has been shown that an extension of the basic binary polar transformation also polarizes over finite fields. With it the direct encoding of q-ary sources and channels is a process that can be implemented with simple and efficient algorithms. However, direct polar decoding of q-ary sources and channels is more involved. In this paper we obtain a recursive equation for the likelihood ratio expressed as a LR vector. With it successive cancellation (SC) decoding is applied in a straightforward way. The complexity is quadratic in the order of the field, but the use of the LR vector introduces factors that soften that complexity. We also show that operations can be parallelized in the decoder. The Bhattacharyya parameters are expressed as a function of the LR vectors, as in the binary case, simplifying the construction of the codes. We have applied direct polar coding to several sources and channels and we have compared it with other multilevel strategies. The direct q-ary polar coding is closer to the theoretical limit than other techniques when the alphabet size is large. Our results suggest that direct q-ary polar coding could be used in real scenarios.
Find Your Place: Simple Distributed Algorithms for Community Detection
Venue: arXiv cs.DC 2016
Year: 2016

Given an underlying graph, we consider the following \emph{dynamics}: Initially, each node locally chooses a value in $\{-1,1\}$, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to address a computational problem that is non-trivial even in a centralized setting.
Fundamental Limits of Cache-Aided Wireless BC: Interplay of Coded-Caching and CSIT Feedback
Venue: arXiv cs.IT 2016
Year: 2016

Building on the recent coded-caching breakthrough by Maddah-Ali and Niesen, the work here considers the $K$-user cache-aided wireless multi-antenna (MISO) symmetric broadcast channel (BC) with random fading and imperfect feedback, and analyzes the throughput performance as a function of feedback statistics and cache size. In this setting, our work identifies the optimal cache-aided degrees-of-freedom (DoF) within a factor of 4, by identifying near-optimal schemes that exploit the new synergy between coded caching and delayed CSIT, as well as by exploiting the unexplored interplay between caching and feedback-quality. The derived limits interestingly reveal that --- the combination of imperfect quality current CSIT, delayed CSIT, and coded caching, guarantees that --- the DoF gains have an initial offset defined by the quality of current CSIT, and then that the additional gains attributed to coded caching are exponential, in the sense that any linear decrease in the required DoF performance, allows for an exponential reduction in the required cache size.
LLNet: A Deep Autoencoder Approach to Natural Low-light Image Enhancement
Venue: arXiv cs.CV 2016
Year: 2016

In surveillance, monitoring and tactical reconnaissance, gathering the right visual information from a dynamic environment and accurately processing such data are essential ingredients to making informed decisions which determines the success of an operation. Camera sensors are often cost-limited in ability to clearly capture objects without defects from images or videos taken in a poorly-lit environment. The goal in many applications is to enhance the brightness, contrast and reduce noise content of such images in an on-board real-time manner. We propose a deep autoencoder-based approach to identify signal features from low-light images handcrafting and adaptively brighten images without over-amplifying the lighter parts in images (i.e., without saturation of image pixels) in high dynamic range. We show that a variant of the recently proposed stacked-sparse denoising autoencoder can learn to adaptively enhance and denoise from synthetically darkened and noisy training examples. The network can then be successfully applied to naturally low-light environment and/or hardware degraded images. Results show significant credibility of deep learning based approaches both visually and by quantitative comparison with various popular enhancing, state-of-the-art denoising and hybrid enhancing-denoising techniques.
LSTM-based Deep Learning Models for Non-factoid Answer Selection
Venue: arXiv cs.CL 2016
Year: 2016

In this paper, we apply a general deep learning (DL) framework for the answer selection task, which does not depend on manually defined features or linguistic tools. The basic framework is to build the embeddings of questions and answers based on bidirectional long short-term memory (biLSTM) models, and measure their closeness by cosine similarity. We further extend this basic model in two directions. One direction is to define a more composite representation for questions and answers by combining convolutional neural network with the basic framework. The other direction is to utilize a simple but efficient attention mechanism in order to generate the answer representation according to the question context. Several variations of models are provided. The models are examined by two datasets, including TREC-QA and InsuranceQA. Experimental results demonstrate that the proposed models substantially outperform several strong baselines.
Action Recognition using Visual Attention
Venue: arXiv cs.LG 2016
Year: 2016

We propose a soft attention based model for the task of action recognition in videos. We use multi-layered Recurrent Neural Networks (RNNs) with Long Short-Term Memory (LSTM) units which are deep both spatially and temporally. Our model learns to focus selectively on parts of the video frames and classifies videos after taking a few glimpses. The model essentially learns which parts in the frames are relevant for the task at hand and attaches higher importance to them. We evaluate the model on UCF-11 (YouTube Action), HMDB-51 and Hollywood2 datasets and analyze how the model focuses its attention depending on the scene and the action being performed.
On the Monotone Measure of Correlation
Venue: arXiv cs.IT 2016
Year: 2016

Based on the notion of maximal correlation, Kimeldorf, May and Sampson (1980) introduce a measure of correlation between two random variables, called the "concordant monotone correlation" (CMC). We revisit, generalize and prove new properties of this measure of correlation. It is shown that CMC captures various types of correlation detected in measures of rank correlation like the Kendall tau correlation. We show that the CMC satisfies the data processing and tensorization properties (that make ordinary maximal correlation applicable to problems in information theory). Furthermore, CMC is shown to be intimately related to the FKG inequality. Furthermore, a combinatorical application of CMC is given for which we do not know of another method to derive its result. Finally, we study the problem of the complexity of the computation of the CMC, which is a non-convex optimization problem with local maximas. We give a simple but exponential-time algorithm that is guaranteed to output the exact value of the generalized CMC.
Canonicity and Relativized Canonicity via Pseudo-Correspondence: an Application of ALBA
Venue: arXiv cs.LO 2016
Year: 2016

We generalize Venema's result on the canonicity of the additivity of positive terms, from classical modal logic to a vast class of logics the algebraic semantics of which is given by varieties of normal distributive lattice expansions (normal DLEs), aka `distributive lattices with operators'. We provide two contrasting proofs for this result: the first is along the lines of Venema's pseudo-correspondence argument but using the insights and tools of unified correspondence theory, and in particular the algorithm ALBA; the second closer to the style of Jónsson. Using insights gleaned from the second proof, we define a suitable enhancement of the algorithm ALBA, which we use prove the canonicity of certain syntactically defined classes of DLE-inequalities (called the meta-inductive inequalities), relative to the structures in which the formulas asserting the additivity of some given terms are valid.
Software Defined Optical Networks (SDONs): A Comprehensive Survey
Venue: arXiv cs.NI 2016
Year: 2016

The emerging Software Defined Networking (SDN) paradigm separates the data plane from the control plane and centralizes network control in an SDN controller. Applications interact with controllers to implement network services, such as network transport with Quality of Service (QoS). SDN facilitates the virtualization of network functions so that multiple virtual networks can operate over a given installed physical network infrastructure. Due to the specific characteristics of optical (photonic) communication components and the high optical transmission capacities, SDN based optical networking poses particular challenges, but holds also great potential. In this article, we comprehensively survey studies that examine the SDN paradigm in optical networks; in brief, we survey the area of Software Defined Optical Networks (SDONs). We mainly organize the SDON studies into studies focused on the infrastructure layer, the control layer, and the application layer. Moreover, we cover SDON studies focused on network virtualization, as well as SDON studies focused on the orchestration of multilayer and multidomain networking. Based on the survey, we identify open challenges for SDONs and outline future directions.
Oracle performance for visual captioning
Venue: arXiv cs.CV 2016
Year: 2016

The task of associating images and videos with a natural language description has attracted a great amount of attention recently. Rapid progress has been made in terms of both developing novel algorithms and releasing new datasets. Indeed, the state-of-the-art results on some of the standard datasets have been pushed into the regime where it has become more and more difficult to make significant improvements. Instead of proposing new models, this work investigates the possibility of empirically establishing performance upper bounds on various visual captioning datasets without extra data labelling effort or human evaluation. In particular, it is assumed that visual captioning is decomposed into two steps: from visual inputs to visual concepts, and from visual concepts to natural language descriptions. One would be able to obtain an upper bound when assuming the first step is perfect and only requiring training a conditional language model for the second step. We demonstrate the construction of such bounds on MS-COCO, YouTube2Text and LSMDC (a combination of M-VAD and MPII-MD). Surprisingly, despite of the imperfect process we used for visual concept extraction in the first step and the simplicity of the language model for the second step, we show that current state-of-the-art models fall short when being compared with the learned upper bounds. Furthermore, with such a bound, we quantify several important factors concerning image and video captioning: the number of visual concepts captured by different models, the trade-off between the amount of visual elements captured and their accuracy, and the intrinsic difficulty and blessing of different datasets.
Shortest Paths and Distances with Differential Privacy
Venue: arXiv cs.CR 2016
Year: 2016

We introduce a model for differentially private analysis of weighted graphs in which the graph topology $(V,E)$ is assumed to be public and the private information consists only of the edge weights $w:E\to\mathbb{R}^+$. This can express hiding congestion patterns in a known system of roads. Differential privacy requires that the output of an algorithm provides little advantage, measured by privacy parameters $ε$ and $δ$, for distinguishing between neighboring inputs, which are thought of as inputs that differ on the contribution of one individual. In our model, two weight functions $w,w'$ are considered to be neighboring if they have $\ell_1$ distance at most one. We study the problems of privately releasing a short path between a pair of vertices and of privately releasing approximate distances between all pairs of vertices. We are concerned with the approximation error, the difference between the length of the released path or released distance and the length of the shortest path or actual distance. For privately releasing a short path between a pair of vertices, we prove a lower bound of $Ω(|V|)$ on the additive approximation error for fixed $ε,δ$. We provide a differentially private algorithm that matches this error bound up to a logarithmic factor and releases paths between all pairs of vertices. The approximation error of our algorithm can be bounded by the number of edges on the shortest path, so we achieve better accuracy than the worst-case bound for vertex pairs that are connected by a low-weight path with $o(|V|)$ vertices. For privately releasing all-pairs distances, we show that for trees we can release all distances with approximation error $O(\log^{2.5}|V|)$ for fixed privacy parameters. For arbitrary bounded-weight graphs with edge weights in $[0,M]$ we can release all distances with approximation error $\tilde{O}(\sqrt{|V|M})$.
Context-Free Commutative Grammars with Integer Counters and Resets
Venue: arXiv cs.FL 2016
Year: 2016

We study the computational complexity of reachability, coverability and inclusion for extensions of context-free commutative grammars with integer counters and reset operations on them. Those grammars can alternatively be viewed as an extension of communication-free Petri nets. Our main results are that reachability and coverability are inter-reducible and both NP-complete. In particular, this class of commutative grammars enjoys semi-linear reachability sets. We also show that the inclusion problem is, in general, coNEXP-complete and already $Π_2^\text{P}$-complete for grammars with only one non-terminal symbol. Showing the lower bound for the latter result requires us to develop a novel $Π_2^\text{P}$-complete variant of the classic subset sum problem.
Proposal Flow
Venue: arXiv cs.CV 2016
Year: 2016

Finding image correspondences remains a challenging problem in the presence of intra-class variations and large changes in scene layout.~Semantic flow methods are designed to handle images depicting different instances of the same object or scene category. We introduce a novel approach to semantic flow, dubbed proposal flow, that establishes reliable correspondences using object proposals. Unlike prevailing semantic flow approaches that operate on pixels or regularly sampled local regions, proposal flow benefits from the characteristics of modern object proposals, that exhibit high repeatability at multiple scales, and can take advantage of both local and geometric consistency constraints among proposals. We also show that proposal flow can effectively be transformed into a conventional dense flow field. We introduce a new dataset that can be used to evaluate both general semantic flow techniques and region-based approaches such as proposal flow. We use this benchmark to compare different matching algorithms, object proposals, and region features within proposal flow, to the state of the art in semantic flow. This comparison, along with experiments on standard datasets, demonstrates that proposal flow significantly outperforms existing semantic flow methods in various settings.
Random sampling of bandlimited signals on graphs
Venue: arXiv cs.SI 2016
Year: 2016

We study the problem of sampling k-bandlimited signals on graphs. We propose two sampling strategies that consist in selecting a small subset of nodes at random. The first strategy is non-adaptive, i.e., independent of the graph structure, and its performance depends on a parameter called the graph coherence. On the contrary, the second strategy is adaptive but yields optimal results. Indeed, no more than O(k log(k)) measurements are sufficient to ensure an accurate and stable recovery of all k-bandlimited signals. This second strategy is based on a careful choice of the sampling distribution, which can be estimated quickly. Then, we propose a computationally efficient decoder to reconstruct k-bandlimited signals from their samples. We prove that it yields accurate reconstructions and that it is also stable to noise. Finally, we conduct several experiments to test these techniques.