OpenRaiser/Intern-Atlas huggingface dataset:
Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding
Venue: arXiv cs.CV 2016
Year: 2016

Neural networks are both computationally intensive and memory intensive, making them difficult to deploy on embedded systems with limited hardware resources. To address this limitation, we introduce "deep compression", a three stage pipeline: pruning, trained quantization and Huffman coding, that work together to reduce the storage requirement of neural networks by 35x to 49x without affecting their accuracy. Our method first prunes the network by learning only the important connections. Next, we quantize the weights to enforce weight sharing, finally, we apply Huffman coding. After the first two steps we retrain the network to fine tune the remaining connections and the quantized centroids. Pruning, reduces the number of connections by 9x to 13x; Quantization then reduces the number of bits that represent each connection from 32 to 5. On the ImageNet dataset, our method reduced the storage required by AlexNet by 35x, from 240MB to 6.9MB, without loss of accuracy. Our method reduced the size of VGG-16 by 49x from 552MB to 11.3MB, again with no loss of accuracy. This allows fitting the model into on-chip SRAM cache rather than off-chip DRAM memory. Our compression method also facilitates the use of complex neural networks in mobile applications where application size and download bandwidth are constrained. Benchmarked on CPU, GPU and mobile GPU, compressed network has 3x to 4x layerwise speedup and 3x to 7x better energy efficiency.
Semidefinite relaxations in optimal experiment design with application to substrate injection for hyperpolarized MRI
Venue: arXiv cs.SY 2016
Year: 2016

We consider the problem of optimal input design for estimating uncertain parameters in a discrete-time linear state space model, subject to simultaneous amplitude and l1/l2-norm constraints on the admissible inputs. We formulate this problem as the maximization of a (non-concave) quadratic function over the space of inputs, and use semidefinite relaxation techniques to efficiently find the global solution or to provide an upper bound. This investigation is motivated by a problem in medical imaging, specifically designing a substrate injection profile for in vivo metabolic parameter mapping using magnetic resonance imaging (MRI) with hyperpolarized carbon-13 pyruvate. In the l2-norm-constrained case, we show that the relaxation is tight, allowing us to efficiently compute a globally optimal injection profile. In the l1-norm-constrained case the relaxation is no longer tight, but can be used to prove that the boxcar injection currently used in practice achieves at least 98.7% of the global optimum.
Information-Theoretic Approach to Strategic Communication as a Hierarchical Game
Venue: arXiv cs.IT 2016
Year: 2016

This paper analyzes the information disclosure problems originated in economics through the lens of information theory. Such problems are radically different from the conventional communication paradigms in information theory since they involve different objectives for the encoder and the decoder, which are aware of this mismatch and act accordingly. This leads, in our setting, to a hierarchical communication game, where the transmitter announces an encoding strategy with full commitment, and its distortion measure depends on a private information sequence whose realization is available at the transmitter. The receiver decides on its decoding strategy that minimizes its own distortion based on the announced encoding map and the statistics. Three problem settings are considered, focusing on the quadratic distortion measures, and jointly Gaussian source and private information: compression, communication, and the simple equilibrium conditions without any compression or communication. The equilibrium strategies and associated costs are characterized. The analysis is then extended to the receiver side information setting and the major changes in the structure of optimal strategies are identified. Finally, an extension of the results to the broader context of decentralized stochastic control is presented.
Existence of k-ary Trees: Subtree Sizes, Heights and Depths
Venue: arXiv cs.DS 2016
Year: 2016

The rooted tree is an important data structure, and the subtree size, height, and depth are naturally defined attributes of every node. We consider the problem of the existence of a k-ary tree given a list of attribute sequences. We give polynomial time (O(nlog(n))) algorithms for the existence of a k-ary tree given depth and/or height sequences. Our most significant results are the Strong NP-Completeness of the decision problems of existence of k-ary trees given subtree sizes sequences. We prove this by multi-stage reductions from NUMERICAL MATCHING WITH TARGET SUMS. In the process, we also prove a generalized version of the 3-PARTITION problem to be Strongly NP-Complete. By looking at problems where a combination of attribute sequences are given, we are able to draw the boundary between easy and hard problems related to existence of trees given attribute sequences and enhance our understanding of where the difficulty lies in such problems.
Tight lower bounds on the number of bicliques in false-twin-free graphs
Venue: arXiv cs.DM 2016
Year: 2016

A \emph{biclique} is a maximal bipartite complete induced subgraph of $G$. Bicliques have been studied in the last years motivated by the large number of applications. In particular, enumeration of the maximal bicliques has been of interest in data analysis. Associated with this issue, bounds on the maximum number of bicliques were given. In this paper we study bounds on the minimun number of bicliques of a graph. Since adding false-twin vertices to $G$ does not change the number of bicliques, we restrict to false-twin-free graphs. We give a tight lower bound on the minimum number bicliques for a subclass of $\{C_4$,false-twin$\}$-free graphs and for the class of $\{K_3$,false-twin$\}$-free graphs. Finally we discuss the problem for general graphs.
Haystack: A Multi-Purpose Mobile Vantage Point in User Space
Venue: arXiv cs.NI 2016
Year: 2016

Despite our growing reliance on mobile phones for a wide range of daily tasks, their operation remains largely opaque. A number of previous studies have addressed elements of this problem in a partial fashion, trading off analytic comprehensiveness and deployment scale. We overcome the barriers to large-scale deployment (e.g., requiring rooted devices) and comprehensiveness of previous efforts by taking a novel approach that leverages the VPN API on mobile devices to design Haystack, an in-situ mobile measurement platform that operates exclusively on the device, providing full access to the device's network traffic and local context without requiring root access. We present the design of Haystack and its implementation in an Android app that we deploy via standard distribution channels. Using data collected from 450 users of the app, we exemplify the advantages of Haystack over the state of the art and demonstrate its seamless experience even under demanding conditions. We also demonstrate its utility to users and researchers in characterizing mobile traffic and privacy risks.
A Framework for Estimating Stream Expression Cardinalities
Venue: arXiv cs.DS 2016
Year: 2016

Given $m$ distributed data streams $A_1, \dots, A_m$, we consider the problem of estimating the number of unique identifiers in streams defined by set expressions over $A_1, \dots, A_m$. We identify a broad class of algorithms for solving this problem, and show that the estimators output by any algorithm in this class are perfectly unbiased and satisfy strong variance bounds. Our analysis unifies and generalizes a variety of earlier results in the literature. To demonstrate its generality, we describe several novel sampling algorithms in our class, and show that they achieve a novel tradeoff between accuracy, space usage, update speed, and applicability.
Classical and Quantum Algorithms for the Boolean Satisfiability Problem
Venue: arXiv cs.CC 2016
Year: 2016

This paper presents a complete algorithmic study of the decision Boolean Satisfiability Problem under the classical computation and quantum computation theories. The paper depicts deterministic and probabilistic algorithms, propositions of their properties and the main result is that the problem has not an efficient algorithm (NP is not P). Novel quantum algorithms and propositions depict that the complexity by quantum computation approach for solving the Boolean Satisfiability Problem or any NP problem is lineal time.
A survey of discrete methods in (algebraic) statistics for networks
Venue: arXiv cs.DM 2016
Year: 2016

Sampling algorithms, hypergraph degree sequences, and polytopes play a crucial role in statistical analysis of network data. This article offers a brief overview of open problems in this area of discrete mathematics from the point of view of a particular family of statistical models for networks called exponential random graph models. The problems and underlying constructions are also related to well-known concepts in commutative algebra and graph-theoretic concepts in computer science. We outline a few lines of recent work that highlight the natural connection between these fields and unify them into some open problems. While these problems are often relevant in discrete mathematics in their own right, the emphasis here is on statistical relevance with the hope that these lines of research do not remain disjoint. Suggested specific open problems and general research questions should advance algebraic statistics theory as well as applied statistical tools for rigorous statistical analysis of networks.
Device-to-Device Communication Underlaying a Finite Cellular Network Region
Venue: arXiv cs.IT 2016
Year: 2016

Underlay in-band device-to-device (D2D) communication can improve the spectrum efficiency of cellular networks. However, the coexistence of D2D and cellular users causes inter-cell and intra-cell interference. The former can be effectively managed through inter-cell interference coordination and, therefore, is not considered in this work. Instead, we focus on the intra-cell interference and propose a D2D mode selection scheme to manage it inside a finite cellular network region. The potential D2D users are controlled by the base station (BS) to operate in D2D mode based on the average interference generated to the BS. Using stochastic geometry, we study the outage probability experienced at the BS and a D2D receiver, and spectrum reuse ratio, which quantifies the average fraction of successfully transmitting D2D users. The analysis shows that the outage probability at the D2D receiver varies for different locations. Additionally, without impairing the performance at the BS, if the path-loss exponent on the cellular link is slightly lower than that on the D2D link, the spectrum reuse ratio can have negligible decrease while the D2D users' average number of successful transmissions increases with increasing D2D node density. This indicates that an increasing level of D2D communication can be beneficial in future networks..
Text-Attentional Convolutional Neural Networks for Scene Text Detection
Venue: arXiv cs.CV 2016
Year: 2016

Recent deep learning models have demonstrated strong capabilities for classifying text and non-text components in natural images. They extract a high-level feature computed globally from a whole image component (patch), where the cluttered background information may dominate true text features in the deep representation. This leads to less discriminative power and poorer robustness. In this work, we present a new system for scene text detection by proposing a novel Text-Attentional Convolutional Neural Network (Text-CNN) that particularly focuses on extracting text-related regions and features from the image components. We develop a new learning mechanism to train the Text-CNN with multi-level and rich supervised information, including text region mask, character label, and binary text/nontext information. The rich supervision information enables the Text-CNN with a strong capability for discriminating ambiguous texts, and also increases its robustness against complicated background components. The training process is formulated as a multi-task learning problem, where low-level supervised information greatly facilitates main task of text/non-text classification. In addition, a powerful low-level detector called Contrast- Enhancement Maximally Stable Extremal Regions (CE-MSERs) is developed, which extends the widely-used MSERs by enhancing intensity contrast between text patterns and background. This allows it to detect highly challenging text patterns, resulting in a higher recall. Our approach achieved promising results on the ICDAR 2013 dataset, with a F-measure of 0.82, improving the state-of-the-art results substantially.
Towards Meaningful Maps of Polish Case Law
Venue: arXiv cs.CL 2016
Year: 2016

In this work, we analyze the utility of two dimensional document maps for exploratory analysis of Polish case law. We start by comparing two methods of generating such visualizations. First is based on linear principal component analysis (PCA). Second makes use of the modern nonlinear t-Distributed Stochastic Neighbor Embedding method (t-SNE). We apply both PCA and t-SNE to a corpus of judgments from different courts in Poland. It emerges that t-SNE provides better, more interpretable results than PCA. As a next test, we apply t-SNE to randomly selected sample of common court judgments corresponding to different keywords. We show that t-SNE, in this case, reveals hidden topical structure of the documents related to keyword,,pension". In conclusion, we find that the t-SNE method could be a promising tool to facilitate the exploitative analysis of legal texts, e.g., by complementing search or browse functionality in legal databases.
A Sensitivity Analysis of (and Practitioners' Guide to) Convolutional Neural Networks for Sentence Classification
Venue: arXiv cs.CL 2016
Year: 2016

Convolutional Neural Networks (CNNs) have recently achieved remarkably strong performance on the practically important task of sentence classification (kim 2014, kalchbrenner 2014, johnson 2014). However, these models require practitioners to specify an exact model architecture and set accompanying hyperparameters, including the filter region size, regularization parameters, and so on. It is currently unknown how sensitive model performance is to changes in these configurations for the task of sentence classification. We thus conduct a sensitivity analysis of one-layer CNNs to explore the effect of architecture components on model performance; our aim is to distinguish between important and comparatively inconsequential design decisions for sentence classification. We focus on one-layer CNNs (to the exclusion of more complex models) due to their comparative simplicity and strong empirical performance, which makes it a modern standard baseline method akin to Support Vector Machine (SVMs) and logistic regression. We derive practical advice from our extensive empirical results for those interested in getting the most out of CNNs for sentence classification in real world settings.
Type-Based Analysis for Session Inference
Venue: arXiv cs.PL 2016
Year: 2016

We propose a type-based analysis to infer the session protocols of channels in an ML-like concurrent functional language. Combining and extending well-known techniques, we develop a type-checking system that separates the underlying ML type system from the typing of sessions. Without using linearity, our system guarantees communication safety and partial lock freedom. It also supports provably complete session inference for finite sessions with no programmer annotations. We exhibit the usefulness of our system with interesting examples, including one which is not typable in substructural type systems.
Experimental Analysis of Popular Smartphone Apps Offering Anonymity, Ephemerality, and End-to-End Encryption
Venue: arXiv cs.CR 2016
Year: 2016

As social networking takes to the mobile world, smartphone apps provide users with ever-changing ways to interact with each other. Over the past couple of years, an increasing number of apps have entered the market offering end-to-end encryption, self-destructing messages, or some degree of anonymity. However, little work thus far has examined the properties they offer. To this end, this paper presents a taxonomy of 18 of these apps: we first look at the features they promise in their appeal to broaden their reach and focus on 8 of the more popular ones. We present a technical evaluation, based on static and dynamic analysis, and identify a number of gaps between the claims and reality of their promises.
Scatter Component Analysis: A Unified Framework for Domain Adaptation and Domain Generalization
Venue: arXiv cs.CV 2016
Year: 2016

This paper addresses classification tasks on a particular target domain in which labeled training data are only available from source domains different from (but related to) the target. Two closely related frameworks, domain adaptation and domain generalization, are concerned with such tasks, where the only difference between those frameworks is the availability of the unlabeled target data: domain adaptation can leverage unlabeled target information, while domain generalization cannot. We propose Scatter Component Analyis (SCA), a fast representation learning algorithm that can be applied to both domain adaptation and domain generalization. SCA is based on a simple geometrical measure, i.e., scatter, which operates on reproducing kernel Hilbert space. SCA finds a representation that trades between maximizing the separability of classes, minimizing the mismatch between domains, and maximizing the separability of data; each of which is quantified through scatter. The optimization problem of SCA can be reduced to a generalized eigenvalue problem, which results in a fast and exact solution. Comprehensive experiments on benchmark cross-domain object recognition datasets verify that SCA performs much faster than several state-of-the-art algorithms and also provides state-of-the-art classification accuracy in both domain adaptation and domain generalization. We also show that scatter can be used to establish a theoretical generalization bound in the case of domain adaptation.
Outage Bound for Max-Based Downlink Scheduling With Imperfect CSIT and Delay Constraint
Venue: arXiv cs.IT 2016
Year: 2016

We consider downlink max-based scheduling in which the base station and each user are equipped with a single antenna. In each time slot, the base station obtains channel gains of all users and selects the user with the largest squared channel gain. Assuming that channel state information at the transmitter (CSIT), i.e., squared channel gain, can be inaccurate, we derive lower bounds for probability of outage, which occurs when a required data rate is not satisfied under a delay constraint. The bounds are tight for Rayleigh fading and show how required rate and CSIT error affect outage performance.
Spectral Partitioning with Blends of Eigenvectors
Venue: arXiv cs.NA 2016
Year: 2016

Many common methods for data analysis rely on linear algebra. We provide new results connecting data analysis error to numerical accuracy, which leads to the first meaningful stopping criterion for two way spectral partitioning. More generally, we provide pointwise convergence guarantees so that blends (linear combinations) of eigenvectors can be employed to solve data analysis problems with confidence in their accuracy. We demonstrate this theory on an accessible model problem, the Ring of Cliques, by deriving the relevant eigenpairs and comparing the predicted results to numerical solutions. These results bridge the gap between linear algebra based data analysis methods and the convergence theory of iterative approximation methods.
A categorical approach to open and interconnected dynamical systems
Venue: arXiv cs.SY 2016
Year: 2016

We develop a sound and complete graphical theory for discrete linear time-invariant dynamical systems. The graphical syntax, as in previous work, is closely related to the classical notion of signal flow diagrams, differently from previous work, these are understood as multi-input multi-output transducers that process streams with an \emph{infinite past} as well as an infinite future. This extended semantics features non-controllable systems, and we develop a novel, structural characterisation of controllability. Our approach is formalised through the theory of props, extending the work of Bonchi, Zanasi and the third author.
A Local Perspective on Community Structure in Multilayer Networks
Venue: arXiv cs.SI 2016
Year: 2016

The analysis of multilayer networks is among the most active areas of network science, and there are now several methods to detect dense "communities" of nodes in multilayer networks. One way to define a community is as a set of nodes that trap a diffusion-like dynamical process (usually a random walk) for a long time. In this view, communities are sets of nodes that create bottlenecks to the spreading of a dynamical process on a network. We analyze the local behavior of different random walks on multiplex networks (which are multilayer networks in which different layers correspond to different types of edges) and show that they have very different bottlenecks that hence correspond to rather different notions of what it means for a set of nodes to be a good community. This has direct implications for the behavior of community-detection methods that are based on these random walks.
A First Practical Fully Homomorphic Crypto-Processor Design: The Secret Computer is Nearly Here
Venue: arXiv cs.CR 2016
Year: 2016

Following a sequence of hardware designs for a fully homomorphic crypto-processor - a general purpose processor that natively runs encrypted machine code on encrypted data in registers and memory, resulting in encrypted machine states - proposed by the authors in 2014, we discuss a working prototype of the first of those, a so-called `pseudo-homomorphic' design. This processor is in principle safe against physical or software-based attacks by the owner/operator of the processor on user processes running in it. The processor is intended as a more secure option for those emerging computing paradigms that require trust to be placed in computations carried out in remote locations or overseen by untrusted operators. The prototype has a single-pipeline superscalar architecture that runs OpenRISC standard machine code in two distinct modes. The processor runs in the encrypted mode (the unprivileged, `user' mode, with a long pipeline) at 60-70% of the speed in the unencrypted mode (the privileged, `supervisor' mode, with a short pipeline), emitting a completed encrypted instruction every 1.67-1.8 cycles on average in real trials.