OpenRaiser/Intern-Atlas huggingface dataset:
On the (parameterized) complexity of recognizing well-covered (r,l)-graphs
Venue: arXiv cs.DS 2018
Year: 2018

An $(r, \ell)$-partition of a graph $G$ is a partition of its vertex set into $r$ independent sets and $\ell$ cliques. A graph is $(r, \ell)$ if it admits an $(r, \ell)$-partition. A graph is well-covered if every maximal independent set is also maximum. A graph is $(r,\ell)$-well-covered if it is both $(r,\ell)$ and well-covered. In this paper we consider two different decision problems. In the $(r,\ell)$-Well-Covered Graph problem ($(r,\ell)$WCG for short), we are given a graph $G$, and the question is whether $G$ is an $(r,\ell)$-well-covered graph. In the Well-Covered $(r,\ell)$-Graph problem (WC$(r,\ell)$G for short), we are given an $(r,\ell)$-graph $G$ together with an $(r,\ell)$-partition of $V(G)$ into $r$ independent sets and $\ell$ cliques, and the question is whether $G$ is well-covered. We classify most of these problems into P, coNP-complete, NP-complete, NP-hard, or coNP-hard. Only the cases WC$(r,0)$G for $r\geq 3$ remain open. In addition, we consider the parameterized complexity of these problems for several choices of parameters, such as the size $α$ of a maximum independent set of the input graph, its neighborhood diversity, its clique-width, or the number $\ell$ of cliques in an $(r, \ell)$-partition. In particular, we show that the parameterized problem of deciding whether a general graph is well-covered parameterized by $α$ can be reduced to the WC$(0,\ell)$G problem parameterized by $\ell$. In addition, we prove that both problems are coW[2]-hard but can be solved in XP-time.
GXNOR-Net: Training deep neural networks with ternary weights and activations without full-precision memory under a unified discretization framework
Venue: arXiv cs.LG 2018
Year: 2018

There is a pressing need to build an architecture that could subsume these networks under a unified framework that achieves both higher performance and less overhead. To this end, two fundamental issues are yet to be addressed. The first one is how to implement the back propagation when neuronal activations are discrete. The second one is how to remove the full-precision hidden weights in the training phase to break the bottlenecks of memory/computation consumption. To address the first issue, we present a multi-step neuronal activation discretization method and a derivative approximation technique that enable the implementing the back propagation algorithm on discrete DNNs. While for the second issue, we propose a discrete state transition (DST) methodology to constrain the weights in a discrete space without saving the hidden weights. Through this way, we build a unified framework that subsumes the binary or ternary networks as its special cases, and under which a heuristic algorithm is provided at the website https://github.com/AcrossV/Gated-XNOR. More particularly, we find that when both the weights and activations become ternary values, the DNNs can be reduced to sparse binary networks, termed as gated XNOR networks (GXNOR-Nets) since only the event of non-zero weight and non-zero activation enables the control gate to start the XNOR logic operations in the original binary networks. This promises the event-driven hardware design for efficient mobile intelligence. We achieve advanced performance compared with state-of-the-art algorithms. Furthermore, the computational sparsity and the number of states in the discrete space can be flexibly modified to make it suitable for various hardware platforms.
SpinArt: A Spin-based Verifier for Artifact Systems
Venue: arXiv cs.DB 2018
Year: 2018

Data-driven workflows, of which IBM's Business Artifacts are a prime exponent, have been successfully deployed in practice, adopted in industrial standards, and have spawned a rich body of research in academia, focused primarily on static analysis. In previous work, we obtained theoretical results on the verification of a rich model incorporating core elements of IBM's successful Guard-Stage-Milestone (GSM) artifact model. The results showed decidability of verification of temporal properties of a large class of GSM workflows and established its complexity. Following up on these results, the present paper reports on the implementation of SpinArt, a practical verifier based on the classical model-checking tool Spin. The implementation includes nontrivial optimizations and achieves good performance on real-world business process examples. Our results shed light on the capabilities and limitations of off-the-shelf verifiers in the context of data-driven workflows.
Reliability of Broadcast Communications Under Sparse Random Linear Network Coding
Venue: arXiv cs.IT 2018
Year: 2018

Ultra-reliable Point-to-Multipoint (PtM) communications are expected to become pivotal in networks offering future dependable services for smart cities. In this regard, sparse Random Linear Network Coding (RLNC) techniques have been widely employed to provide an efficient way to improve the reliability of broadcast and multicast data streams. This paper addresses the pressing concern of providing a tight approximation to the probability of a user recovering a data stream protected by this kind of coding technique. In particular, by exploiting the Stein--Chen method, we provide a novel and general performance framework applicable to any combination of system and service parameters, such as finite field sizes, lengths of the data stream and level of sparsity. The deviation of the proposed approximation from Monte Carlo simulations is negligible, improving significantly on the state of the art performance bounds.
Guess & Check Codes for Deletions, Insertions, and Synchronization
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of constructing codes that can correct $δ$ deletions occurring in an arbitrary binary string of length $n$ bits. Varshamov-Tenengolts (VT) codes, dating back to 1965, are zero-error single deletion $(δ=1)$ correcting codes, and have an asymptotically optimal redundancy. Finding similar codes for $δ\geq 2$ deletions remains an open problem. In this work, we relax the standard zero-error (i.e., worst-case) decoding requirement by assuming that the positions of the $δ$ deletions (or insertions) are independent of the codeword. Our contribution is a new family of explicit codes, that we call Guess & Check (GC) codes, that can correct with high probability up to a constant number of $δ$ deletions (or insertions). GC codes are systematic; and have deterministic polynomial time encoding and decoding algorithms. We also describe the application of GC codes to file synchronization.
End-to-end Global to Local CNN Learning for Hand Pose Recovery in Depth Data
Venue: arXiv cs.CV 2018
Year: 2018

Despite recent advances in 3D pose estimation of human hands, especially thanks to the advent of CNNs and depth cameras, this task is still far from being solved. This is mainly due to the highly non-linear dynamics of fingers, which make hand model training a challenging task. In this paper, we exploit a novel hierarchical tree-like structured CNN, in which branches are trained to become specialized in predefined subsets of hand joints, called local poses. We further fuse local pose features, extracted from hierarchical CNN branches, to learn higher order dependencies among joints in the final pose by end-to-end training. Lastly, the loss function used is also defined to incorporate appearance and physical constraints about doable hand motion and deformation. Finally, we introduce a non-rigid data augmentation approach to increase the amount of training depth data. Experimental results suggest that feeding a tree-shaped CNN, specialized in local poses, into a fusion network for modeling joints correlations and dependencies, helps to increase the precision of final estimations, outperforming state-of-the-art results on NYU and SyntheticHand datasets.
Deep Metric Learning and Image Classification with Nearest Neighbour Gaussian Kernels
Venue: arXiv cs.CV 2018
Year: 2018

We present a Gaussian kernel loss function and training algorithm for convolutional neural networks that can be directly applied to both distance metric learning and image classification problems. Our method treats all training features from a deep neural network as Gaussian kernel centres and computes loss by summing the influence of a feature's nearby centres in the feature embedding space. Our approach is made scalable by treating it as an approximate nearest neighbour search problem. We show how to make end-to-end learning feasible, resulting in a well formed embedding space, in which semantically related instances are likely to be located near one another, regardless of whether or not the network was trained on those classes. Our approach outperforms state-of-the-art deep metric learning approaches on embedding learning challenges, as well as conventional softmax classification on several datasets.
Multi-channel Weighted Nuclear Norm Minimization for Real Color Image Denoising
Venue: arXiv cs.CV 2018
Year: 2018

Most of the existing denoising algorithms are developed for grayscale images, while it is not a trivial work to extend them for color image denoising because the noise statistics in R, G, B channels can be very different for real noisy images. In this paper, we propose a multi-channel (MC) optimization model for real color image denoising under the weighted nuclear norm minimization (WNNM) framework. We concatenate the RGB patches to make use of the channel redundancy, and introduce a weight matrix to balance the data fidelity of the three channels in consideration of their different noise statistics. The proposed MC-WNNM model does not have an analytical solution. We reformulate it into a linear equality-constrained problem and solve it with the alternating direction method of multipliers. Each alternative updating step has closed-form solution and the convergence can be guaranteed. Extensive experiments on both synthetic and real noisy image datasets demonstrate the superiority of the proposed MC-WNNM over state-of-the-art denoising methods.
DICOD: Distributed Convolutional Sparse Coding
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we introduce DICOD, a convolutional sparse coding algorithm which builds shift invariant representations for long signals. This algorithm is designed to run in a distributed setting, with local message passing, making it communication efficient. It is based on coordinate descent and uses locally greedy updates which accelerate the resolution compared to greedy coordinate selection. We prove the convergence of this algorithm and highlight its computational speed-up which is super-linear in the number of cores used. We also provide empirical evidence for the acceleration properties of our algorithm compared to state-of-the-art methods.
Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
Venue: arXiv cs.IT 2018
Year: 2018

We consider a large-scale matrix multiplication problem where the computation is carried out using a distributed system with a master node and multiple worker nodes, where each worker can store parts of the input matrices. We propose a computation strategy that leverages ideas from coding theory to design intermediate computations at the worker nodes, in order to efficiently deal with straggling workers. The proposed strategy, named as \emph{polynomial codes}, achieves the optimum recovery threshold, defined as the minimum number of workers that the master needs to wait for in order to compute the output. Furthermore, by leveraging the algebraic structure of polynomial codes, we can map the reconstruction problem of the final output to a polynomial interpolation problem, which can be solved efficiently. Polynomial codes provide order-wise improvement over the state of the art in terms of recovery threshold, and are also optimal in terms of several other metrics. Furthermore, we extend this code to distributed convolution and show its order-wise optimality.
IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models
Venue: arXiv cs.IR 2018
Year: 2018

This paper provides a unified account of two schools of thinking in information retrieval modelling: the generative retrieval focusing on predicting relevant documents given a query, and the discriminative retrieval focusing on predicting relevancy given a query-document pair. We propose a game theoretical minimax game to iteratively optimise both models. On one hand, the discriminative model, aiming to mine signals from labelled and unlabelled data, provides guidance to train the generative model towards fitting the underlying relevance distribution over documents given the query. On the other hand, the generative model, acting as an attacker to the current discriminative model, generates difficult examples for the discriminative model in an adversarial way by minimising its discrimination objective. With the competition between these two models, we show that the unified framework takes advantage of both schools of thinking: (i) the generative model learns to fit the relevance distribution over documents via the signals from the discriminative model, and (ii) the discriminative model is able to exploit the unlabelled data selected by the generative model to achieve a better estimation for document ranking. Our experimental results have demonstrated significant performance gains as much as 23.96% on Precision@5 and 15.50% on MAP over strong baselines in a variety of applications including web search, item recommendation, and question answering.
Adversarial Ranking for Language Generation
Venue: arXiv cs.CL 2018
Year: 2018

Generative adversarial networks (GANs) have great successes on synthesizing data. However, the existing GANs restrict the discriminator to be a binary classifier, and thus limit their learning capacity for tasks that need to synthesize output with rich structures such as natural language descriptions. In this paper, we propose a novel generative adversarial network, RankGAN, for generating high-quality language descriptions. Rather than training the discriminator to learn and assign absolute binary predicate for individual data sample, the proposed RankGAN is able to analyze and rank a collection of human-written and machine-written sentences by giving a reference group. By viewing a set of data samples collectively and evaluating their quality through relative ranking scores, the discriminator is able to make better assessment which in turn helps to learn a better generator. The proposed RankGAN is optimized through the policy gradient technique. Experimental results on multiple public datasets clearly demonstrate the effectiveness of the proposed approach.
Models and information-theoretic bounds for nanopore sequencing
Venue: arXiv cs.IT 2018
Year: 2018

Nanopore sequencing is an emerging new technology for sequencing DNA, which can read long fragments of DNA (~50,000 bases) in contrast to most current short-read sequencing technologies which can only read hundreds of bases. While nanopore sequencers can acquire long reads, the high error rates (20%-30%) pose a technical challenge. In a nanopore sequencer, a DNA is migrated through a nanopore and current variations are measured. The DNA sequence is inferred from this observed current pattern using an algorithm called a base-caller. In this paper, we propose a mathematical model for the "channel" from the input DNA sequence to the observed current, and calculate bounds on the information extraction capacity of the nanopore sequencer. This model incorporates impairments like (non-linear) inter-symbol interference, deletions, as well as random response. These information bounds have two-fold application: (1) The decoding rate with a uniform input distribution can be used to calculate the average size of the plausible list of DNA sequences given an observed current trace. This bound can be used to benchmark existing base-calling algorithms, as well as serving a performance objective to design better nanopores. (2) When the nanopore sequencer is used as a reader in a DNA storage system, the storage capacity is quantified by our bounds.
Bayesian fairness
Venue: arXiv cs.LG 2018
Year: 2018

We consider the problem of how decision making can be fair when the underlying probabilistic model of the world is not known with certainty. We argue that recent notions of fairness in machine learning need to explicitly incorporate parameter uncertainty, hence we introduce the notion of {\em Bayesian fairness} as a suitable candidate for fair decision rules. Using balance, a definition of fairness introduced by Kleinberg et al (2016), we show how a Bayesian perspective can lead to well-performing, fair decision rules even under high uncertainty.
Benchmark problems for phase retrieval
Venue: arXiv cs.IT 2018
Year: 2018

In recent years, the mathematical and algorithmic aspects of the phase retrieval problem have received considerable attention. Many papers in this area mention crystallography as a principal application. In crystallography, the signal to be recovered is periodic and comprised of atomic distributions arranged homogeneously in the unit cell of the crystal. The crystallographic problem is both the leading application and one of the hardest forms of phase retrieval. We have constructed a graded set of benchmark problems for evaluating algorithms that perform this type of phase retrieval. The data, publicly available online, is provided in an easily interpretable format. We also propose a simple and unambiguous success/failure criterion based on the actual needs in crystallography. Baseline runtimes were obtained with an iterative algorithm that is similar but more transparent than those used in crystallography. Empirically, the runtimes grow exponentially with respect to a new hardness parameter: the sparsity of the signal autocorrelation. We also review the algorithms used by the leading software packages. This set of benchmark problems, we hope, will encourage the development of new algorithms for the phase retrieval problem in general, and crystallography in particular.
A Comparison of Spatial-based Targeted Disease Containment Strategies using Mobile Phone Data
Venue: arXiv cs.SI 2018
Year: 2018

Epidemic outbreaks are an important healthcare challenge, especially in developing countries where they represent one of the major causes of mortality. Approaches that can rapidly target subpopulations for surveillance and control are critical for enhancing containment processes during epidemics. Using a real-world dataset from Ivory Coast, this work presents an attempt to unveil the socio-geographical heterogeneity of disease transmission dynamics. By employing a spatially explicit meta-population epidemic model derived from mobile phone Call Detail Records (CDRs), we investigate how the differences in mobility patterns may affect the course of a realistic infectious disease outbreak. We consider different existing measures of the spatial dimension of human mobility and interactions, and we analyse their relevance in identifying the highest risk sub-population of individuals, as the best candidates for isolation countermeasures. The approaches presented in this paper provide further evidence that mobile phone data can be effectively exploited to facilitate our understanding of individuals' spatial behaviour and its relationship with the risk of infectious diseases' contagion. In particular, we show that CDRs-based indicators of individuals' spatial activities and interactions hold promise for gaining insight of contagion heterogeneity and thus for developing containment strategies to support decision-making during country-level pandemics.
IDK Cascades: Fast Deep Learning by Learning not to Overthink
Venue: arXiv cs.CV 2018
Year: 2018

Advances in deep learning have led to substantial increases in prediction accuracy but have been accompanied by increases in the cost of rendering predictions. We conjecture that fora majority of real-world inputs, the recent advances in deep learning have created models that effectively "overthink" on simple inputs. In this paper, we revisit the classic question of building model cascades that primarily leverage class asymmetry to reduce cost. We introduce the "I Don't Know"(IDK) prediction cascades framework, a general framework to systematically compose a set of pre-trained models to accelerate inference without a loss in prediction accuracy. We propose two search based methods for constructing cascades as well as a new cost-aware objective within this framework. The proposed IDK cascade framework can be easily adopted in the existing model serving systems without additional model re-training. We evaluate the proposed techniques on a range of benchmarks to demonstrate the effectiveness of the proposed framework.
Optimal controller/observer gains of discounted-cost LQG systems
Venue: arXiv cs.SY 2018
Year: 2018

The linear-quadratic-Gaussian (LQG) control paradigm is well-known in literature. The strategy of minimizing the cost function is available, both for the case where the state is known and where it is estimated through an observer. The situation is different when the cost function has an exponential discount factor, also known as a prescribed degree of stability. In this case, the optimal control strategy is only available when the state is known. This paper builds on from that result, deriving an optimal control strategy when working with an estimated state. Expressions for the resulting optimal expected cost are also given.
Signal Amplitude Estimation and Detection from Unlabeled Binary Quantized Samples
Venue: arXiv cs.IT 2018
Year: 2018

Signal amplitude estimation and detection from unlabeled quantized binary samples are studied, assuming that the order of the time indexes is completely unknown. First, maximum likelihood (ML) estimators are utilized to estimate both the permutation matrix and unknown signal amplitude under arbitrary, but known signal shape and quantizer thresholds. Sufficient conditions are provided under which an ML estimator can be found in polynomial time and an alternating maximization algorithm is proposed to solve the general problem via good initial estimates. In addition, the statistical identifiability of the model is studied. Furthermore, the generalized likelihood ratio test (GLRT) detector is adopted to detect the presence of signal. In addition, an accurate approximation to the probability of successful permutation matrix recovery is derived, and explicit expressions are provided to reveal the relationship between the number of signal samples and the number of quantizers. Finally, numerical simulations are performed to verify the theoretical results.
Deep learning evaluation using deep linguistic processing
Venue: arXiv cs.CL 2018
Year: 2018

We discuss problems with the standard approaches to evaluation for tasks like visual question answering, and argue that artificial data can be used to address these as a complement to current practice. We demonstrate that with the help of existing 'deep' linguistic processing technology we are able to create challenging abstract datasets, which enable us to investigate the language understanding abilities of multimodal deep learning models in detail, as compared to a single performance value on a static and monolithic dataset.