OpenRaiser/Intern-Atlas huggingface dataset:
Automated Pruning for Deep Neural Network Compression
Venue: arXiv cs.CV 2019
Year: 2019

In this work we present a method to improve the pruning step of the current state-of-the-art methodology to compress neural networks. The novelty of the proposed pruning technique is in its differentiability, which allows pruning to be performed during the backpropagation phase of the network training. This enables an end-to-end learning and strongly reduces the training time. The technique is based on a family of differentiable pruning functions and a new regularizer specifically designed to enforce pruning. The experimental results show that the joint optimization of both the thresholds and the network weights permits to reach a higher compression rate, reducing the number of weights of the pruned network by a further 14% to 33% compared to the current state-of-the-art. Furthermore, we believe that this is the first study where the generalization capabilities in transfer learning tasks of the features extracted by a pruned network are analyzed. To achieve this goal, we show that the representations learned using the proposed pruning methodology maintain the same effectiveness and generality of those learned by the corresponding non-compressed network on a set of different recognition tasks.
Perspectival Knowledge in PSOA RuleML: Representation, Model Theory, and Translation
Venue: arXiv cs.AI 2019
Year: 2019

In Positional-Slotted Object-Applicative (PSOA) RuleML, a predicate application (atom) can have an Object IDentifier (OID) and descriptors that may be positional arguments (tuples) or attribute-value pairs (slots). PSOA RuleML explicitly specifies for each descriptor whether it is to be interpreted under the perspective of the predicate in whose scope it occurs. This predicate-dependency dimension refines the space between oidless, positional atoms (relationships) and oidful, slotted atoms (framepoints): While relationships use only a predicate-scope-sensitive (predicate-dependent) tuple and framepoints use only predicate-scope-insensitive (predicate-independent) slots, PSOA uses a systematics of orthogonal constructs also permitting atoms with (predicate-)independent tuples and atoms with (predicate-)dependent slots. This supports data and knowledge representation where a slot attribute can have different values depending on the predicate. PSOA thus extends object-oriented multi-membership and multiple inheritance. Based on objectification, PSOA laws are given: Besides unscoping and centralization, the semantic restriction and transformation of describution permits rescoping of one atom's independent descriptors to another atom with the same OID but a different predicate. For inheritance, default descriptors are realized by rules. On top of a metamodel and a Grailog visualization, PSOA's atom systematics for facts, queries, and rules is explained. The presentation and (XML-)serialization syntaxes of PSOA RuleML are introduced. Its model-theoretic semantics is formalized by extending the interpretation functions for dependent descriptors. The open-source PSOATransRun system realizes PSOA RuleML by a translator to runtime predicates, including for dependent tuples (prdtupterm) and slots (prdsloterm). Our tests show efficiency advantages of dependent and tupled modeling.
Journey to the Center of the Point Set
Venue: arXiv cs.CG 2019
Year: 2019

$\renewcommand{\Re}{\mathbb{R}} \newcommand{\eps}{\varepsilon} \newcommand{\Net}{S} \newcommand{\tldO}{\widetilde{O}} \newcommand{\body}{C} $ We revisit an algorithm of Clarkson etal [CEMST96], that computes (roughly) a $1/(4d^2)$-centerpoint in $\tldO(d^9)$ time, for a point set in $\Re^d$, where $\tldO$ hides polylogarithmic terms. We present an improved algorithm that computes (roughly) a $1/d^2$-centerpoint with running time $\tldO(d^7)$. While the improvements are (arguably) mild, it is the first progress on this well known problem in over twenty years. The new algorithm is simpler, and the running time bound follows by a simple random walk argument, which we believe to be of independent interest. We also present several new applications of the improved centerpoint algorithm.
Compact Hash Code Learning with Binary Deep Neural Network
Venue: arXiv cs.CV 2019
Year: 2019

Learning compact binary codes for image retrieval problem using deep neural networks has recently attracted increasing attention. However, training deep hashing networks is challenging due to the binary constraints on the hash codes. In this paper, we propose deep network models and learning algorithms for learning binary hash codes given image representations under both unsupervised and supervised manners. The novelty of our network design is that we constrain one hidden layer to directly output the binary codes. This design has overcome a challenging problem in some previous works: optimizing non-smooth objective functions because of binarization. In addition, we propose to incorporate independence and balance properties in the direct and strict forms into the learning schemes. We also include a similarity preserving property in our objective functions. The resulting optimizations involving these binary, independence, and balance constraints are difficult to solve. To tackle this difficulty, we propose to learn the networks with alternating optimization and careful relaxation. Furthermore, by leveraging the powerful capacity of convolutional neural networks, we propose an end-to-end architecture that jointly learns to extract visual features and produce binary hash codes. Experimental results for the benchmark datasets show that the proposed methods compare favorably or outperform the state of the art.
Energy Efficient and Throughput Optimal CSMA Scheme
Venue: arXiv cs.IT 2019
Year: 2019

Carrier Sense Multiple Access (CSMA) is widely used as a Medium Access Control (MAC) in wireless networks due to its simplicity and distributed nature. This motivated researchers to find CSMA schemes that achieve throughput optimality. In 2008, it has been shown that a simple CSMA-type algorithm is able to achieve optimality in terms of throughput and has been given the name "adaptive" CSMA. Lately, new technologies emerged where prolonged battery life is crucial such as environment and industrial monitoring. This inspired the foundation of new CSMA based MAC schemes where links are allowed to transition into sleep mode to reduce the power consumption. However, throughput optimality of these schemes was not established. This paper therefore aims to find a new CSMA scheme that combines both throughput optimality and energy efficiency by adapting to the throughput and power consumption needs of each link. This is done by controlling operational parameters such as back-off and sleeping timers with the aim of optimizing a certain objective function. The resulting CSMA scheme is characterized by being asynchronous, completely distributed and being able to adapt to different power consumption profiles required by each link while still ensuring throughput optimality. The performance gain in terms of energy efficiency compared to the conventional adaptive CSMA scheme is demonstrated through computer simulations.
The Insecurity of Home Digital Voice Assistants -- Amazon Alexa as a Case Study
Venue: arXiv cs.CR 2019
Year: 2019

Home Digital Voice Assistants (HDVAs) are getting popular in recent years. Users can control smart devices and get living assistance through those HDVAs (e.g., Amazon Alexa, Google Home) using voice. In this work, we study the insecurity of HDVA service by using Amazon Alexa as a case study. We disclose three security vulnerabilities which root in the insecure access control of Alexa services. We then exploit them to devise two proof-of-concept attacks, home burglary and fake order, where the adversary can remotely command the victim's Alexa device to open a door or place an order from Amazon.com. The insecure access control is that the Alexa device not only relies on a single-factor authentication but also takes voice commands even if no people are around. We thus argue that HDVAs should have another authentication factor, a physical presence based access control; that is, they can accept voice commands only when any person is detected nearby. To this end, we devise a Virtual Security Button (VSButton), which leverages the WiFi technology to detect indoor human motions. Once any indoor human motion is detected, the Alexa device is enabled to accept voice commands. Our evaluation results show that it can effectively differentiate indoor motions from the cases of no motion and outdoor motions in both the laboratory and real world settings.
Efficient enumeration of solutions produced by closure operations
Venue: arXiv cs.CC 2019
Year: 2019

In this paper we address the problem of generating all elements obtained by the saturation of an initial set by some operations. More precisely, we prove that we can generate the closure of a boolean relation (a set of boolean vectors) by polymorphisms with a polynomial delay. Therefore we can compute with polynomial delay the closure of a family of sets by any set of "set operations": union, intersection, symmetric difference, subsets, supersets $\dots$). To do so, we study the $Membership_{\mathcal{F}}$ problem: for a set of operations $\mathcal{F}$, decide whether an element belongs to the closure by $\mathcal{F}$ of a family of elements. In the boolean case, we prove that $Membership_{\mathcal{F}}$ is in P for any set of boolean operations $\mathcal{F}$. When the input vectors are over a domain larger than two elements, we prove that the generic enumeration method fails, since $Membership_{\mathcal{F}}$ is NP-hard for some $\mathcal{F}$. We also study the problem of generating minimal or maximal elements of closures and prove that some of them are related to well known enumeration problems such as the enumeration of the circuits of a matroid or the enumeration of maximal independent sets of a hypergraph. This article improves on previous works of the same authors.
Krylov Subspace Approximation for Local Community Detection in Large Networks
Venue: arXiv cs.SI 2019
Year: 2019

Community detection is an important information mining task to uncover modular structures in large networks. For increasingly common large network data sets, global community detection is prohibitively expensive, and attention has shifted to methods that mine local communities, i.e. identifying all latent members of a particular community from a few labeled seed members. To address such semi-supervised mining task, we systematically develop a local spectral subspace-based community detection method, called LOSP. We define a family of local spectral subspaces based on Krylov subspaces, and seek a sparse indicator for the target community via an $\ell_1$ norm minimization over the Krylov subspace. Variants of LOSP depend on type of random walks with different diffusion speeds, type of random walks, dimension of the local spectral subspace and step of diffusions. The effectiveness of the proposed LOSP approach is theoretically analyzed based on Rayleigh quotients, and it is experimentally verified on a wide variety of real-world networks across social, production and biological domains, as well as on an extensive set of synthetic LFR benchmark datasets.
Closing the gap for pseudo-polynomial strip packing
Venue: arXiv cs.DM 2019
Year: 2019

The set of 2-dimensional packing problems builds an important class of optimization problems and Strip Packing together with 2-dimensional Bin Packing and 2-dimensional Knapsack is one of the most famous of these problems. Given a set of rectangular axis parallel items and a strip with bounded width and infinite height the objective is to find a packing of the items into the strip which minimizes the packing height. We speak of pseudo-polynomial Strip Packing if we consider algorithms with pseudo-polynomial running time with respect to the width of the strip. It is known that there is no pseudo-polynomial algorithm for Strip Packing with a ratio better than $5/4$ unless $\mathrm{P} = \mathrm{NP}$. The best algorithm so far has a ratio of $(4/3 + \varepsilon)$. In this paper, we close this gap between inapproximability result and best known algorithm by presenting an algorithm with approximation ratio $(5/4 + \varepsilon)$ and thus categorize the problem accurately. The algorithm uses a structural result which states that each optimal solution can be transformed such that it has one of a polynomial number of different forms. The strength of this structural result is that it applies to other problem settings as well for example to Strip Packing with rotations (90 degrees) and Contiguous Moldable Task Scheduling. This fact enabled us to present algorithms with approximation ratio $(5/4 + \varepsilon)$ for these problems as well.
Achievability Performance Bounds for Integer-Forcing Source Coding
Venue: arXiv cs.IT 2019
Year: 2019

Integer-forcing source coding has been proposed as a low-complexity method for compression of distributed correlated Gaussian sources. In this scheme, each encoder quantizes its observation using the same fine lattice and reduces the result modulo a coarse lattice. Rather than directly recovering the individual quantized signals, the decoder first recovers a full-rank set of judiciously chosen integer linear combinations of the quantized signals, and then inverts it. It has been observed that the method works very well for "most" but not all source covariance matrices. The present work quantifies the measure of bad covariance matrices by studying the probability that integer-forcing source coding fails as a function of the allocated rate, %in excess of the %Berger-Tung benchmark, where the probability is with respect to a random orthonormal transformation that is applied to the sources prior to quantization. For the important case where the signals to be compressed correspond to the antenna inputs of relays in an i.i.d. Rayleigh fading environment, this orthonormal transformation can be viewed as being performed by nature. Hence, the results provide performance guarantees for distributed source coding via integer forcing in this scenario.
Occam's razor is insufficient to infer the preferences of irrational agents
Venue: arXiv cs.AI 2019
Year: 2019

Inverse reinforcement learning (IRL) attempts to infer human rewards or preferences from observed behavior. Since human planning systematically deviates from rationality, several approaches have been tried to account for specific human shortcomings. However, the general problem of inferring the reward function of an agent of unknown rationality has received little attention. Unlike the well-known ambiguity problems in IRL, this one is practically relevant but cannot be resolved by observing the agent's policy in enough environments. This paper shows (1) that a No Free Lunch result implies it is impossible to uniquely decompose a policy into a planning algorithm and reward function, and (2) that even with a reasonable simplicity prior/Occam's razor on the set of decompositions, we cannot distinguish between the true decomposition and others that lead to high regret. To address this, we need simple `normative' assumptions, which cannot be deduced exclusively from observations.
Graph Transform Optimization with Application to Image Compression
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we propose a new graph-based transform and illustrate its potential application to signal compression. Our approach relies on the careful design of a graph that optimizes the overall rate-distortion performance through an effective graph-based transform. We introduce a novel graph estimation algorithm, which uncovers the connectivities between the graph signal values by taking into consideration the coding of both the signal and the graph topology in rate-distortion terms. In particular, we introduce a novel coding solution for the graph by treating the edge weights as another graph signal that lies on the dual graph. Then, the cost of the graph description is introduced in the optimization problem by minimizing the sparsity of the coefficients of its graph Fourier transform (GFT) on the dual graph. In this way, we obtain a convex optimization problem whose solution defines an efficient transform coding strategy. The proposed technique is a general framework that can be applied to different types of signals, and we show two possible application fields, namely natural image coding and piecewise smooth image coding. The experimental results show that the proposed graph-based transform outperforms classical fixed transforms such as DCT for both natural and piecewise smooth images. In the case of depth map coding, the obtained results are even comparable to the state-of-the-art graph-based coding method, that are specifically designed for depth map images.
Uniform Diagonalization Theorem for Complexity Classes of Promise Problems including Randomized and Quantum Classes
Venue: arXiv cs.CC 2019
Year: 2019

Diagonalization in the spirit of Cantor's diagonal arguments is a widely used tool in theoretical computer sciences to obtain structural results about computational problems and complexity classes by indirect proofs. The Uniform Diagonalization Theorem allows the construction of problems outside complexity classes while still being reducible to a specific decision problem. This paper provides a generalization of the Uniform Diagonalization Theorem by extending it to promise problems and the complexity classes they form, e.g. randomized and quantum complexity classes. The theorem requires from the underlying computing model not only the decidability of its acceptance and rejection behaviour but also of its promise-contradicting indifferent behaviour - a property that we will introduce as "total decidability" of promise problems. Implications of the Uniform Diagonalization Theorem are mainly of two kinds: 1. Existence of intermediate problems (e.g. between BQP and QMA) - also known as Ladner's Theorem - and 2. Undecidability if a problem of a complexity class is contained in a subclass (e.g. membership of a QMA-problem in BQP). Like the original Uniform Diagonalization Theorem the extension applies besides BQP and QMA to a large variety of complexity class pairs, including combinations from deterministic, randomized and quantum classes.
Companions, Causality and Codensity
Venue: arXiv cs.LO 2019
Year: 2019

In the context of abstract coinduction in complete lattices, the notion of compatible function makes it possible to introduce enhancements of the coinduction proof principle. The largest compatible function, called the companion, subsumes most enhancements and has been proved to enjoy many good properties. Here we move to universal coalgebra, where the corresponding notion is that of a final distributive law. We show that when it exists, the final distributive law is a monad, and that it coincides with the codensity monad of the final sequence of the given functor. On sets, we moreover characterise this codensity monad using a new abstract notion of causality. In particular, we recover the fact that on streams, the functions definable by a distributive law or GSOS specification are precisely the causal functions. Going back to enhancements of the coinductive proof principle, we finally obtain that any causal function gives rise to a valid up-to-context technique.
The Robust Manifold Defense: Adversarial Training using Generative Models
Venue: arXiv cs.CV 2019
Year: 2019

We propose a new type of attack for finding adversarial examples for image classifiers. Our method exploits spanners, i.e. deep neural networks whose input space is low-dimensional and whose output range approximates the set of images of interest. Spanners may be generators of GANs or decoders of VAEs. The key idea in our attack is to search over latent code pairs to find ones that generate nearby images with different classifier outputs. We argue that our attack is stronger than searching over perturbations of real images. Moreover, we show that our stronger attack can be used to reduce the accuracy of Defense-GAN to 3\%, resolving an open problem from the well-known paper by Athalye et al. We combine our attack with normal adversarial training to obtain the most robust known MNIST classifier, significantly improving the state of the art against PGD attacks. Our formulation involves solving a min-max problem, where the min player sets the parameters of the classifier and the max player is running our attack, and is thus searching for adversarial examples in the {\em low-dimensional} input space of the spanner. All code and models are available at \url{https://github.com/ajiljalal/manifold-defense.git}
Generalized Compression Strategy for the Downlink Cloud Radio Access Network
Venue: arXiv cs.IT 2019
Year: 2019

This paper studies the downlink of a cloud radio access network (C-RAN) in which a centralized processor (CP) communicates with mobile users through base stations (BSs) that are connected to the CP via finite-capacity fronthaul links. Information theoretically, the downlink of a C-RAN is modeled as a two-hop broadcast-relay network. Among the various transmission and relaying strategies for such model, this paper focuses on the compression strategy, in which the CP centrally encodes the signals to be broadcasted jointly by the BSs, then compresses and sends these signals to the BSs through the fronthaul links. This paper characterizes an achievable rate region for a generalized compression strategy with Marton's multicoding for broadcasting and multivariate compression for fronthaul transmission. We then compare this rate region with the distributed decode-forward (DDF) scheme, which achieves the capacity of the general relay networks to within a constant gap, and show that the difference lies in that DDF performs Marton's multicoding and multivariate compression jointly as opposed to successively as in the compression strategy. A main result of this paper is that under the assumption that the fronthaul links are subject to a \emph{sum} capacity constraint this difference is immaterial, so the successive encoding based compression strategy can already achieve the capacity region of the C-RAN to within a constant gap, where the gap is independent of the channel parameters and the power constraints at the BSs. For the special case of the Gaussian network, we further establish that under individual fronthaul constraints, the compression strategy achieves to within a constant gap to the \emph{sum} capacity of the C-RAN.
Restricted Deformable Convolution based Road Scene Semantic Segmentation Using Surround View Cameras
Venue: arXiv cs.CV 2019
Year: 2019

Understanding the surrounding environment of the vehicle is still one of the challenges for autonomous driving. This paper addresses 360-degree road scene semantic segmentation using surround view cameras, which are widely equipped in existing production cars. First, in order to address large distortion problem in the fisheye images, Restricted Deformable Convolution (RDC) is proposed for semantic segmentation, which can effectively model geometric transformations by learning the shapes of convolutional filters conditioned on the input feature map. Second, in order to obtain a large-scale training set of surround view images, a novel method called zoom augmentation is proposed to transform conventional images to fisheye images. Finally, an RDC based semantic segmentation model is built; the model is trained for real-world surround view images through a multi-task learning architecture by combining real-world images with transformed images. Experiments demonstrate the effectiveness of the RDC to handle images with large distortions, and that the proposed approach shows a good performance using surround view cameras with the help of the transformed images.