OpenRaiser/Intern-Atlas huggingface dataset:
Training Sparse Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

Deep neural networks with lots of parameters are typically used for large-scale computer vision tasks such as image classification. This is a result of using dense matrix multiplications and convolutions. However, sparse computations are known to be much more efficient. In this work, we train and build neural networks which implicitly use sparse computations. We introduce additional gate variables to perform parameter selection and show that this is equivalent to using a spike-and-slab prior. We experimentally validate our method on both small and large networks and achieve state-of-the-art compression results for sparse neural network models.
Bidiagonalization with Parallel Tiled Algorithms
Venue: arXiv cs.MS 2016
Year: 2016

We consider algorithms for going from a "full" matrix to a condensed "band bidiagonal" form using orthogonal transformations. We use the framework of "algorithms by tiles". Within this framework, we study: (i) the tiled bidiagonalization algorithm BiDiag, which is a tiled version of the standard scalar bidiagonalization algorithm; and (ii) the R-bidiagonalization algorithm R-BiDiag, which is a tiled version of the algorithm which consists in first performing the QR factorization of the initial matrix, then performing the band-bidiagonalization of the R-factor. For both bidiagonalization algorithms BiDiag and R-BiDiag, we use four main types of reduction trees, namely FlatTS, FlatTT, Greedy, and a newly introduced auto-adaptive tree, Auto. We provide a study of critical path lengths for these tiled algorithms, which shows that (i) R-BiDiag has a shorter critical path length than BiDiag for tall and skinny matrices, and (ii) Greedy based schemes are much better than earlier proposed variants with unbounded resources. We provide experiments on a single multicore node, and on a few multicore nodes of a parallel distributed shared-memory system, to show the superiority of the new algorithms on a variety of matrix sizes, matrix shapes and core counts.
Isolario: a Do-ut-des Approach to Improve the Appeal of BGP Route Collecting
Venue: arXiv cs.NI 2016
Year: 2016

The incompleteness of data collected from BGP route collecting projects is a well-known issue which potentially affects every research activity carried out on the analysis of the Internet inter-domain routing. Recent works explained that one of the possible solutions is to increase the number of ASes feeding these projects from the Internet periphery, in order to reveal the hidden portion of peering connectivity of their upstream providers. The main problem is that these projects are currently not appealing enough for the network administrators of these ASes, which are typically not aware of their existence or not interested enough to share their data. Our contribution is Isolario, a project based on the do-ut-des principle which aims at persuading network administrators to share their routing information by offering services in return, ranging from real-time analyses of the incoming BGP session(s) to historic analyses of routing reachability. To the best of our knowledge, Isolario is the only route collecting project publicly available which offers a set of services to its users to encourage their participation, aiming at increasing the amount of BGP data publicly available for research purposes.
A Metaprogramming and Autotuning Framework for Deploying Deep Learning Applications
Venue: arXiv cs.NE 2016
Year: 2016

In recent years, deep neural networks (DNNs), have yielded strong results on a wide range of applications. Graphics Processing Units (GPUs) have been one key enabling factor leading to the current popularity of DNNs. However, despite increasing hardware flexibility and software programming toolchain maturity, high efficiency GPU programming remains difficult: it suffers from high complexity, low productivity, and low portability. GPU vendors such as NVIDIA have spent enormous effort to write special-purpose DNN libraries. However, on other hardware targets, especially mobile GPUs, such vendor libraries are not generally available. Thus, the development of portable, open, high-performance, energy-efficient GPU code for DNN operations would enable broader deployment of DNN-based algorithms. Toward this end, this work presents a framework to enable productive, high-efficiency GPU programming for DNN computations across hardware platforms and programming models. In particular, the framework provides specific support for metaprogramming, autotuning, and DNN-tailored data types. Using our framework, we explore implementing DNN operations on three different hardware targets: NVIDIA, AMD, and Qualcomm GPUs. On NVIDIA GPUs, we show both portability between OpenCL and CUDA as well competitive performance compared to the vendor library. On Qualcomm GPUs, we show that our framework enables productive development of target-specific optimizations, and achieves reasonable absolute performance. Finally, On AMD GPUs, we show initial results that indicate our framework can yield reasonable performance on a new platform with minimal effort.
Statistical Learning for OCR Text Correction
Venue: arXiv cs.CV 2016
Year: 2016

The accuracy of Optical Character Recognition (OCR) is crucial to the success of subsequent applications used in text analyzing pipeline. Recent models of OCR post-processing significantly improve the quality of OCR-generated text, but are still prone to suggest correction candidates from limited observations while insufficiently accounting for the characteristics of OCR errors. In this paper, we show how to enlarge candidate suggestion space by using external corpus and integrating OCR-specific features in a regression approach to correct OCR-generated errors. The evaluation results show that our model can correct 61.5% of the OCR-errors (considering the top 1 suggestion) and 71.5% of the OCR-errors (considering the top 3 suggestions), for cases where the theoretical correction upper-bound is 78%.
Robust end-to-end deep audiovisual speech recognition
Venue: arXiv cs.CL 2016
Year: 2016

Speech is one of the most effective ways of communication among humans. Even though audio is the most common way of transmitting speech, very important information can be found in other modalities, such as vision. Vision is particularly useful when the acoustic signal is corrupted. Multi-modal speech recognition however has not yet found wide-spread use, mostly because the temporal alignment and fusion of the different information sources is challenging. This paper presents an end-to-end audiovisual speech recognizer (AVSR), based on recurrent neural networks (RNN) with a connectionist temporal classification (CTC) loss function. CTC creates sparse "peaky" output activations, and we analyze the differences in the alignments of output targets (phonemes or visemes) between audio-only, video-only, and audio-visual feature representations. We present the first such experiments on the large vocabulary IBM ViaVoice database, which outperform previously published approaches on phone accuracy in clean and noisy conditions.
Coherent Dialogue with Attention-based Language Models
Venue: arXiv cs.CL 2016
Year: 2016

We model coherent conversation continuation via RNN-based dialogue models equipped with a dynamic attention mechanism. Our attention-RNN language model dynamically increases the scope of attention on the history as the conversation continues, as opposed to standard attention (or alignment) models with a fixed input scope in a sequence-to-sequence model. This allows each generated word to be associated with the most relevant words in its corresponding conversation history. We evaluate the model on two popular dialogue datasets, the open-domain MovieTriples dataset and the closed-domain Ubuntu Troubleshoot dataset, and achieve significant improvements over the state-of-the-art and baselines on several metrics, including complementary diversity-based metrics, human evaluation, and qualitative visualizations. We also show that a vanilla RNN with dynamic attention outperforms more complex memory models (e.g., LSTM and GRU) by allowing for flexible, long-distance memory. We promote further coherence via topic modeling-based reranking.
Manipulability of consular election rules
Venue: arXiv cs.GT 2016
Year: 2016

The Gibbard-Satterthwaite theorem is a cornerstone of social choice theory, stating that an onto social choice function cannot be both strategy-proof and non-dictatorial if the number of alternatives is at least three. The Duggan-Schwartz theorem proves an analogue in the case of set-valued elections: if the function is onto with respect to singletons, and can be manipulated by neither an optimist nor a pessimist, it must have a weak dictator. However, the assumption that the function is onto with respect to singletons makes the Duggan-Schwartz theorem inapplicable to elections which necessarily select a committee with multiple members. In this paper we make a start on this problem by considering elections which elect a committee of size two (such as the consulship of ancient Rome). We establish that if such a consular election rule cannot be expressed as the union of two disjoint social choice functions, then strategy-proofness implies the existence of a dictator. Although we suspect that a similar result holds for larger sized committees, there appear to be many obstacles to proving it, which we discuss in detail.
Max-Margin Deep Generative Models for (Semi-)Supervised Learning
Venue: arXiv cs.CV 2016
Year: 2016

Deep generative models (DGMs) are effective on learning multilayered representations of complex data and performing inference of input data by exploring the generative ability. However, it is relatively insufficient to empower the discriminative ability of DGMs on making accurate predictions. This paper presents max-margin deep generative models (mmDGMs) and a class-conditional variant (mmDCGMs), which explore the strongly discriminative principle of max-margin learning to improve the predictive performance of DGMs in both supervised and semi-supervised learning, while retaining the generative capability. In semi-supervised learning, we use the predictions of a max-margin classifier as the missing labels instead of performing full posterior inference for efficiency; we also introduce additional max-margin and label-balance regularization terms of unlabeled data for effectiveness. We develop an efficient doubly stochastic subgradient algorithm for the piecewise linear objectives in different settings. Empirical results on various datasets demonstrate that: (1) max-margin learning can significantly improve the prediction performance of DGMs and meanwhile retain the generative ability; (2) in supervised learning, mmDGMs are competitive to the best fully discriminative networks when employing convolutional neural networks as the generative and recognition models; and (3) in semi-supervised learning, mmDCGMs can perform efficient inference and achieve state-of-the-art classification results on several benchmarks.
Outage Effective Capacity of Buffer-Aided Diamond Relay Systems Using HARQ with Incremental Redundancy
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, transmission over buffer-aided diamond relay systems under statistical quality of service (QoS) constraints is studied. The statistical QoS constraints are imposed as limitations on delay violation probabilities. In the absence of channel state information (CSI) at the transmitter, truncated hybrid automatic repeat request-incremental redundancy (HARQ-IR) is incorporated to make better use of the wireless channel and the resources for each communication link. The packets that cannot be successfully received upon the maximum number of transmissions will be removed from buffer, i.e., outage occurs. The \emph{outage effective capacity} of a communication link is defined as the maximum constant arrival rate to the source that can be supported by the \emph{goodput} departure processes, i.e., the departure that can be successfully received by the receiver. Then, the outage effective capacity for the buffer-aided diamond relay system is obtained for HARQ-IR incorporated transmission strategy under the \emph{end-to-end} delay constraints. In comparison with the DF protocol with perfect CSI at the transmitters, it is shown that HARQ-IR can achieve superior performance when the SNR levels at the relay are not so large or when the delay constraints are stringent.
PVR: Patch-to-Volume Reconstruction for Large Area Motion Correction of Fetal MRI
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we present a novel method for the correction of motion artifacts that are present in fetal Magnetic Resonance Imaging (MRI) scans of the whole uterus. Contrary to current slice-to-volume registration (SVR) methods, requiring an inflexible anatomical enclosure of a single investigated organ, the proposed patch-to-volume reconstruction (PVR) approach is able to reconstruct a large field of view of non-rigidly deforming structures. It relaxes rigid motion assumptions by introducing a specific amount of redundant information that is exploited with parallelized patch-wise optimization, super-resolution, and automatic outlier rejection. We further describe and provide an efficient parallel implementation of PVR allowing its execution within reasonable time on commercially available graphics processing units (GPU), enabling its use in the clinical practice. We evaluate PVR's computational overhead compared to standard methods and observe improved reconstruction accuracy in presence of affine motion artifacts of approximately 30% compared to conventional SVR in synthetic experiments. Furthermore, we have evaluated our method qualitatively and quantitatively on real fetal MRI data subject to maternal breathing and sudden fetal movements. We evaluate peak-signal-to-noise ratio (PSNR), structural similarity index (SSIM), and cross correlation (CC) with respect to the originally acquired data and provide a method for visual inspection of reconstruction uncertainty. With these experiments we demonstrate successful application of PVR motion compensation to the whole uterus, the human fetus, and the human placenta.
Geodesic Distance Descriptors
Venue: arXiv cs.CG 2016
Year: 2016

The Gromov-Hausdorff (GH) distance is traditionally used for measuring distances between metric spaces. It is defined as the minimal distortion of embedding one surface into the other, while the optimal correspondence can be described as the map that minimizes this distortion. Solving such a minimization is a hard combinatorial problem that requires pre-computation and storing of all pairwise geodesic distances for the matched surfaces. A popular way for compact representation of functions on surfaces is by projecting them into the leading eigenfunctions of the Laplace-Beltrami Operator (LBO). When truncated, The basis of the LBO is known to be the optimal for representing functions with bounded gradient in a min-max sense. Methods such as Spectral-GMDS exploit this idea to simplify and efficiently approximate a minimization related to the GH distance by operating in the truncated spectral domain, and obtain state of the art results for matching of nearly isometric shapes. However, when considering only a specific set of functions on the surface, such as geodesic distances, an optimized basis could be considered as an even better alternative. Here, we define the geodesic distance basis, which is optimal for compact approximation of geodesic distances, in terms of Frobenius norm. We use the suggested basis to extract the Geodesic Distance Descriptor (GDD), which encodes the geodesic distances information as a linear combination of the basis functions. We then show how these ideas can be used to efficiently and accurately approximate the metric spaces matching problem with almost no loss of information. These observations are used to construct a very simple and efficient procedure for shape correspondence. Experimental results show that the GDD improves both accuracy and efficiency of state of the art shape matching procedures.
Smart Library: Identifying Books in a Library using Richly Supervised Deep Scene Text Reading
Venue: arXiv cs.CV 2016
Year: 2016

Physical library collections are valuable and long standing resources for knowledge and learning. However, managing books in a large bookshelf and finding books on it often leads to tedious manual work, especially for large book collections where books might be missing or misplaced. Recently, deep neural models, such as Convolutional Neural Networks (CNN) and Recurrent Neural Networks (RNN) have achieved great success for scene text detection and recognition. Motivated by these recent successes, we aim to investigate their viability in facilitating book management, a task that introduces further challenges including large amounts of cluttered scene text, distortion, and varied lighting conditions. In this paper, we present a library inventory building and retrieval system based on scene text reading methods. We specifically design our scene text recognition model using rich supervision to accelerate training and achieve state-of-the-art performance on several benchmark datasets. Our proposed system has the potential to greatly reduce the amount of human labor required in managing book inventories as well as the space needed to store book information.
Reduction-Based Creative Telescoping for Fuchsian D-finite Functions
Venue: arXiv cs.SC 2016
Year: 2016

Continuing a series of articles in the past few years on creative telescoping using reductions, we adapt Trager's Hermite reduction for algebraic functions to fuchsian D-finite functions and develop a reduction-based creative telescoping algorithm for this class of functions, thereby generalizing our recent reduction-based algorithm for algebraic functions, presented at ISSAC 2016.
Assessing the Performance of a 60-GHz Dense Small-Cell Network Deployment from Ray-Based Simulations
Venue: arXiv cs.NI 2016
Year: 2016

Future dense small-cell networks are one key 5G candidates to offer outdoor high access data rates, especially in millimeter wave (mmWave) frequency bands. At those frequencies, the free space propagation loss and shadowing (from buildings, vegetation or any kind of obstacles) are far stronger than in the traditional radio cellular spectrum. Therefore, the cell range is expected to be limited to 50 - 100 meters, and directive high gain antennas are required at least for the base stations. This paper investigates the kind of topology that is required to serve a suburban area with a small-cell network operating at 60 GHz and equipped with beam-steering antennas. A real environment is considered to introduce practical deployment and propagation constraints. The analysis relies on Monte-Carlo system simulations with non-full buffer, and ray-based predictions. The ray-tracing techniques are today identified as a relevant solution to capture the main channel properties impacting the beam-steering performance (angular dispersion, inter-link correlation); and the one involved in the present study was specifically enhanced to deal with detailed vegetation modeling. In addition to the user outage, the paper evaluates the evolution of the inter-cell interference along with the user density, and investigates the network behavior in case of local strong obstructions.
Variational Intrinsic Control
Venue: arXiv cs.LG 2016
Year: 2016

In this paper we introduce a new unsupervised reinforcement learning method for discovering the set of intrinsic options available to an agent. This set is learned by maximizing the number of different states an agent can reliably reach, as measured by the mutual information between the set of options and option termination states. To this end, we instantiate two policy gradient based algorithms, one that creates an explicit embedding space of options and one that represents options implicitly. The algorithms also provide an explicit measure of empowerment in a given state that can be used by an empowerment maximizing agent. The algorithm scales well with function approximation and we demonstrate the applicability of the algorithm on a range of tasks.
Can Broken Multicore Hardware be Mended?
Venue: arXiv cs.DC 2016
Year: 2016

A suggestion is made for mending multicore hardware, which has been diagnosed as broken.
A Truthful $(1-ε)$-Optimal Mechanism for On-demand Cloud Resource Provisioning
Venue: arXiv cs.GT 2016
Year: 2016

On-demand resource provisioning in cloud computing provides tailor-made resource packages (typically in the form of VMs) to meet users' demands. Public clouds nowadays provide more and more elaborated types of VMs, but have yet to offer the most flexible dynamic VM assembly, which is partly due to the lack of a mature mechanism for pricing tailor-made VMs on the spot. This work proposes an efficient randomized auction mechanism based on a novel application of smoothed analysis and randomized reduction, for dynamic VM provisioning and pricing in geo-distributed cloud data centers. This auction, to the best of our knowledge, is the first one in literature that achieves (i) truthfulness in expectation, (ii) polynomial running time in expectation, and (iii) $(1-ε)$-optimal social welfare in expectation for resource allocation, where $ε$ can be arbitrarily close to 0. Our mechanism consists of three modules: (1) an exact algorithm to solve the NP-hard social welfare maximization problem, which runs in polynomial time in expectation, (2) a perturbation-based randomized resource allocation scheme which produces a VM provisioning solution that is $(1-ε)$-optimal, and (3) an auction mechanism that applies the perturbation-based scheme for dynamic VM provisioning and prices the customized VMs using a randomized VCG payment, with a guarantee in truthfulness in expectation. We validate the efficacy of the mechanism through careful theoretical analysis and trace-driven simulations.
Using SyGuS to Synthesize Reactive Motion Plans
Venue: arXiv cs.PL 2016
Year: 2016

We present an approach for synthesizing reactive robot motion plans, based on compilation to Syntax-Guided Synthesis (SyGuS) specifications. Our method reduces the motion planning problem to the problem of synthesizing a function that can choose the next robot action in response to the current state of the system. This technique offers reactivity not by generating new motion plans throughout deployment, but by synthesizing a single program that causes the robot to reach its target from any system state that is consistent with the system model. This approach allows our tool to handle environments with adversarial obstacles. This work represents the first use of the SyGuS formalism to solve robot motion planning problems. We investigate whether using SyGuS for a bounded two-player reachability game is practical at this point in time.
Knapsack Problems: A Parameterized Point of View
Venue: arXiv cs.CC 2016
Year: 2016

The knapsack problem (KP) is a very famous NP-hard problem in combinatorial optimization. Also its generalization to multiple dimensions named d-dimensional knapsack problem (d-KP) and to multiple knapsacks named multiple knapsack problem (MKP) are well known problems. Since KP, d-KP, and MKP are integer-valued problems defined on inputs of various informations, we study the fixed-parameter tractability of these problems. The idea behind fixed-parameter tractability is to split the complexity into two parts - one part that depends purely on the size of the input, and one part that depends on some parameter of the problem that tends to be small in practice. Further we consider the closely related question, whether the sizes and the values can be reduced, such that their bit-length is bounded polynomially or even constantly in a given parameter, i.e. the existence of kernelizations is studied. We discuss the following parameters: the number of items, the threshold value for the profit, the sizes, the profits, the number d of dimensions, and the number m of knapsacks. We also consider the connection of parameterized knapsack problems to linear programming, approximation, and pseudo-polynomial algorithms.