OpenRaiser/Intern-Atlas huggingface dataset:
The Dispersion of Mismatched Joint Source-Channel Coding for Arbitrary Sources and Additive Channels
Venue: arXiv cs.IT 2018
Year: 2018

We consider a joint source channel coding (JSCC) problem in which we desire to transmit an arbitrary memoryless source over an arbitrary additive channel. We propose a mismatched coding architecture that consists of Gaussian codebooks for both the source reproduction sequences and channel codewords. The natural nearest neighbor encoder and decoder, however, need to be judiciously modified to obtain the highest communication rates at finite blocklength. In particular, we consider a unequal error protection (UEP) scheme in which all sources are partitioned into disjoint power type classes. We also regularize the nearest neighbor decoder so that an appropriate measure of the size of each power type class is taken into account in the decoding strategy. For such an architecture, we derive ensemble-tight second-order and moderate deviations results. Our first-order (optimal bandwidth expansion ratio) result generalizes the seminal results by Lapidoth (1996, 1997). The dispersion of our JSCC scheme is a linear combination of the mismatched dispersions for the channel coding saddle-point problem by Scarlett, Tan and Durisi (2017) and the rate-distortion saddle-point problem by the present authors, thus also generalizing these results.
Assessing Information Transmission in Data Transformations with the Channel Multivariate Entropy Triangle
Venue: arXiv cs.IT 2018
Year: 2018

Data transformation, e.g. feature transformation and selection, is an integral part of any machine learning procedure. In this paper we introduce an information-theoretic model and tools to assess the quality of data transformations in machine learning tasks. In an unsupervised fashion, we analyze the transfer of information of the transformation of a discrete, multivariate source of information X into a discrete, multivariate sink of information Y related by a distribution PXY . The first contribution is a decomposition of the maximal potential entropy of (X, Y) that we call a balance equation, into its a) non-transferable, b) transferable but not transferred and c) transferred parts. Such balance equations can be represented in (de Finetti) entropy diagrams, our second set of contributions. The most important of these, the aggregate Channel Multivariate Entropy Triangle is a visual exploratory tool to assess the effectiveness of multivariate data transformations in transferring information from input to output variables. We also show how these decomposition and balance equation also apply to the entropies of X and Y respectively and generate entropy triangles for them. As an example, we present the application of these tools to the assessment of information transfer efficiency for PCA and ICA as unsupervised feature transformation and selection procedures in supervised classification tasks.
Comparing Deep Reinforcement Learning and Evolutionary Methods in Continuous Control
Venue: arXiv cs.LG 2018
Year: 2018

Reinforcement Learning and the Evolutionary Strategy are two major approaches in addressing complicated control problems. Both are strong contenders and have their own devotee communities. Both groups have been very active in developing new advances in their own domain and devising, in recent years, leading-edge techniques to address complex continuous control tasks. Here, in the context of Deep Reinforcement Learning, we formulate a parallelized version of the Proximal Policy Optimization method and a Deep Deterministic Policy Gradient method. Moreover, we conduct a thorough comparison between the state-of-the-art techniques in both camps fro continuous control; evolutionary methods and Deep Reinforcement Learning methods. The results show there is no consistent winner.
Resource Sharing of a Computing Access Point for Multi-user Mobile Cloud Offloading with Delay Constraints
Venue: arXiv cs.IT 2018
Year: 2018

We consider a mobile cloud computing system with multiple users, a remote cloud server, and a computing access point (CAP). The CAP serves both as the network access gateway and a computation service provider to the mobile users. It can either process the received tasks from mobile users or offload them to the cloud. We jointly optimize the offloading decisions of all users, together with the allocation of computation and communication resources, to minimize the overall cost of energy consumption, computation, and maximum delay among users. The joint optimization problem is formulated as a mixed-integer program. We show that the problem can be reformulated and transformed into a non-convex quadratically constrained quadratic program, which is NP-hard in general. We then propose an efficient solution to this problem by semidefinite relaxation and a novel randomization mapping method. Furthermore, when there is a strict delay constraint for processing each user's task, we further propose a three-step algorithm to guarantee the feasibility and local optimality of the obtained solution. Our simulation results show that the proposed solutions give nearly optimal performance under a wide range of parameter settings, and the addition of a CAP can significantly reduce the cost of multi-user task offloading compared with conventional mobile cloud computing where only the remote cloud server is available.
Fundamental Limits on Data Acquisition: Trade-offs between Sample Complexity and Query Difficulty
Venue: arXiv cs.IT 2018
Year: 2018

We consider query-based data acquisition and the corresponding information recovery problem, where the goal is to recover $k$ binary variables (information bits) from parity measurements of those variables. The queries and the corresponding parity measurements are designed using the encoding rule of Fountain codes. By using Fountain codes, we can design potentially limitless number of queries, and corresponding parity measurements, and guarantee that the original $k$ information bits can be recovered with high probability from any sufficiently large set of measurements of size $n$. In the query design, the average number of information bits that is associated with one parity measurement is called query difficulty ($\bar{d}$) and the minimum number of measurements required to recover the $k$ information bits for a fixed $\bar{d}$ is called sample complexity ($n$). We analyze the fundamental trade-offs between the query difficulty and the sample complexity, and show that the sample complexity of $n=c\max\{k,(k\log k)/\bar{d}\}$ for some constant $c>0$ is necessary and sufficient to recover $k$ information bits with high probability as $k\to\infty$.
On the Hardness of Deriving the Arithmetic Mean Component Competitive Ratio
Venue: arXiv cs.DS 2018
Year: 2018

For the multi-objective time series search problem, Hasegawa and Itoh [Theoretical Computer Science, Vo.718, pp.58-66, 2018] presented the best possible online algorithm balanced price policy (BPP for short) for any monotone function $f: R^k \to R$. Specifically, the competitive ratio with respect to the monotone function $f(c_{1},\ldots,c_{k})=(c_{1}+\cdots+c_{k})/k$ is referred to as the arithmetic mean component competitive ratio. Hasegawa and Itoh derived the closed formula of the arithmetic mean component competitive ratio for $k=2$, but it has not been known for any integer $k \geq 3$. In this paper, we show that it is NP-hard to derive closed formulas of the arithmetic mean component competitive ratio for general integer $k\geq 2$. On the the hand, we derive closed formulas of the arithmetic mean component competitive ratio for $k=3$ and $k=4$.
Flexible Installability of Android Apps with App-level Virtualization based Decomposition
Venue: arXiv cs.CY 2018
Year: 2018

With the popularity of smartphones, users are heavily dependent on mobile applications for daily work and entertainments. However, mobile apps are becoming more and more complicated with more features and increasing size, part of which may be redundant to users. Due to the limitation of current installation mechanism, users have to download full-size applications instead of enjoy only the wanted features. Such full-size apps may consume more resources, including CPU, memory, and energy, which may hurt users' enthusiasm for further installation. We first conduct an empirical study to characterize used features when users interact with mobile applications, and find that users only consume a small set features of target apps. To address this problem, we present AppStarscream, which offers to decompose and run Android apps with app-level virtualization. We have implemented a prototype system and evaluated it with real-world apps showing that AppStarscream is efficient and practical.
Spatial Modulation Aided Layered Division Multiplexing: A Spectral Efficiency Perspective
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, spatial modulation (SM) is introduced to layered division multiplexing (LDM) systems for enlarging the spectral efficiency over broadcasting transmission. Firstly, the SM aided LDM (SM-LDM) system is proposed, in which different layered services utilize SM for terrestrial broadcasting transmission with different power levels. Then a spectral efficiency (SE) analysis framework for SM-LDM systems is proposed, which is suitable for the SM-LDM systems with linear combining. Moreover, the closed-form SE lower bound of SM-LDM systems with maximum ratio combining (MRC) is derived, which is based on this framework. Since the theoretical SE analysis of single transmit antenna (TA) LDM systems with MRC and spatial multiplexing (SMX) aided LDM systems with MRC lacks a closed-form expression, the closed-form SE is also derived for these systems. Monte Carlo simulations are provided to verify the tightness of our proposed SE lower bound. Furthermore, it can be shown via simulations that our proposed SM-LDM systems always have a better SE performance than single-TA LDM systems, which can even outperform the SE of SMX aided LDM (SMX-LDM) systems.
Research assessment by percentile-based double rank analysis
Venue: arXiv cs.DL 2018
Year: 2018

In the double rank analysis of research publications, the local rank position of a country or institution publication is expressed as a function of the world rank position. Excluding some highly or lowly cited publications, the double rank plot fits well with a power law, which can be explained because citations for local and world publications follow lognormal distributions. We report here that the distribution of the number of country or institution publications in world percentiles is a double rank distribution that can be fitted to a power law. Only the data points in high percentiles deviate from it when the local and world $μ$ parameters of the lognormal distributions are very different. The likelihood of publishing very highly cited papers can be calculated from the power law that can be fitted either to the upper tail of the citation distribution or to the percentile-based double rank distribution. The great advantage of the latter method is that it has universal application, because it is based on all publications and not just on highly cited publications. Furthermore, this method extends the application of the well-established percentile approach to very low percentiles where breakthroughs are reported but paper counts cannot be performed.
Drinfeld Modules with Complex Multiplication, Hasse Invariants and Factoring Polynomials over Finite Fields
Venue: arXiv cs.CG 2018
Year: 2018

We present a novel randomized algorithm to factor polynomials over a finite field $\F_q$ of odd characteristic using rank $2$ Drinfeld modules with complex multiplication. The main idea is to compute a lift of the Hasse invariant (modulo the polynomial $f \in \F_q[x]$ to be factored) with respect to a random Drinfeld module $ϕ$ with complex multiplication. Factors of $f$ supported on prime ideals with supersingular reduction at $ϕ$ have vanishing Hasse invariant and can be separated from the rest. Incorporating a Drinfeld module analogue of Deligne's congruence, we devise an algorithm to compute the Hasse invariant lift, which turns out to be the crux of our algorithm. The resulting expected runtime of $n^{3/2+\varepsilon} (\log q)^{1+o(1)}+n^{1+\varepsilon} (\log q)^{2+o(1)}$ to factor polynomials of degree $n$ over $\F_q$ matches the fastest previously known algorithm, the Kedlaya-Umans implementation of the Kaltofen-Shoup algorithm.
Improving Network Robustness against Adversarial Attacks with Compact Convolution
Venue: arXiv cs.LG 2018
Year: 2018

Though Convolutional Neural Networks (CNNs) have surpassed human-level performance on tasks such as object classification and face verification, they can easily be fooled by adversarial attacks. These attacks add a small perturbation to the input image that causes the network to misclassify the sample. In this paper, we focus on neutralizing adversarial attacks by compact feature learning. In particular, we show that learning features in a closed and bounded space improves the robustness of the network. We explore the effect of L2-Softmax Loss, that enforces compactness in the learned features, thus resulting in enhanced robustness to adversarial perturbations. Additionally, we propose compact convolution, a novel method of convolution that when incorporated in conventional CNNs improves their robustness. Compact convolution ensures feature compactness at every layer such that they are bounded and close to each other. Extensive experiments show that Compact Convolutional Networks (CCNs) neutralize multiple types of attacks, and perform better than existing methods in defending adversarial attacks, without incurring any additional training overhead compared to CNNs.
Low-Rank Tensor Completion by Truncated Nuclear Norm Regularization
Venue: arXiv cs.CV 2018
Year: 2018

Currently, low-rank tensor completion has gained cumulative attention in recovering incomplete visual data whose partial elements are missing. By taking a color image or video as a three-dimensional (3D) tensor, previous studies have suggested several definitions of tensor nuclear norm. However, they have limitations and may not properly approximate the real rank of a tensor. Besides, they do not explicitly use the low-rank property in optimization. It is proved that the recently proposed truncated nuclear norm (TNN) can replace the traditional nuclear norm, as a better estimation to the rank of a matrix. Thus, this paper presents a new method called the tensor truncated nuclear norm (T-TNN), which proposes a new definition of tensor nuclear norm and extends the truncated nuclear norm from the matrix case to the tensor case. Beneficial from the low rankness of TNN, our approach improves the efficacy of tensor completion. We exploit the previously proposed tensor singular value decomposition and the alternating direction method of multipliers in optimization. Extensive experiments on real-world videos and images demonstrate that the performance of our approach is superior to those of existing methods.
SOAP: One Clean Analysis of All Age-Based Scheduling Policies
Venue: arXiv cs.PF 2018
Year: 2018

We consider an extremely broad class of M/G/1 scheduling policies called SOAP: Schedule Ordered by Age-based Priority. The SOAP policies include almost all scheduling policies in the literature as well as an infinite number of variants which have never been analyzed, or maybe not even conceived. SOAP policies range from classic policies, like first-come, first-serve (FCFS), foreground-background (FB), class-based priority, and shortest remaining processing time (SRPT); to much more complicated scheduling rules, such as the famously complex Gittins index policy and other policies in which a job's priority changes arbitrarily with its age. While the response time of policies in the former category is well understood, policies in the latter category have resisted response time analysis. We present a universal analysis of all SOAP policies, deriving the mean and Laplace-Stieltjes transform of response time.
Drift Analysis
Venue: arXiv cs.NE 2018
Year: 2018

Drift analysis is one of the major tools for analysing evolutionary algorithms and nature-inspired search heuristics. In this chapter we give an introduction to drift analysis and give some examples of how to use it for the analysis of evolutionary algorithms.
Layer by layer - Combining Monads
Venue: arXiv cs.LO 2018
Year: 2018

We develop a method to incrementally construct programming languages. Our approach is categorical: each layer of the language is described as a monad. Our method either (i) concretely builds a distributive law between two monads, i.e. layers of the language, which then provides a monad structure to the composition of layers, or (ii) identifies precisely the algebraic obstacles to the existence of a distributive law and gives a best approximant language. The running example will involve three layers: a basic imperative language enriched first by adding non-determinism and then probabilistic choice. The first extension works seamlessly, but the second encounters an obstacle, which results in a best approximant language structurally very similar to the probabilistic network specification language ProbNetKAT.
tHoops: A Multi-Aspect Analytical Framework Spatio-Temporal Basketball Data
Venue: arXiv cs.LG 2018
Year: 2018

During the past few years advancements in sports information systems and technology has allowed us to collect a number of detailed spatio-temporal data capturing various aspects of basketball. For example, shot charts, that is, maps capturing locations of (made or missed) shots, and spatio-temporal trajectories for all the players on the court can capture information about the offensive and defensive tendencies and schemes of a team. Characterization of these processes is important for player and team comparisons, pre-game scouting, game preparation etc. Playing tendencies among teams have traditionally been compared in a heuristic manner. Recently automated ways for similar comparisons have appeared in the sports analytics literature. However, these approaches are almost exclusively focused on the spatial distribution of the underlying actions (usually shots taken), ignoring a multitude of other parameters that can affect the action studied. In this work, we propose a framework based on tensor decomposition for obtaining a set of prototype spatio-temporal patterns based on the core spatiotemporal information and contextual meta-data. The core of our framework is a 3D tensor X, whose dimensions represent the entity under consideration (team, player, possession etc.), the location on the court and time. We make use of the PARAFAC decomposition and we decompose the tensor into several interpretable patterns, that can be thought of as prototype patterns of the process examined (e.g., shot selection, offensive schemes etc.). We also introduce an approach for choosing the number of components to be considered. Using the tensor components, we can then express every entity as a weighted combination of these components. The framework introduced in this paper can have further applications in the work-flow of the basketball operations of a franchise, which we also briefly discuss.
Deep linear neural networks with arbitrary loss: All local minima are global
Venue: arXiv cs.LG 2018
Year: 2018

We consider deep linear networks with arbitrary convex differentiable loss. We provide a short and elementary proof of the fact that all local minima are global minima if the hidden layers are either 1) at least as wide as the input layer, or 2) at least as wide as the output layer. This result is the strongest possible in the following sense: If the loss is convex and Lipschitz but not differentiable then deep linear networks can have sub-optimal local minima.
A new measure for community structures through indirect social connections
Venue: arXiv cs.SI 2018
Year: 2018

Based on an expert systems approach, the issue of community detection can be conceptualized as a clustering model for networks. Building upon this further, community structure can be measured through a clustering coefficient, which is generated from the number of existing triangles around the nodes over the number of triangles that can be hypothetically constructed. This paper provides a new definition of the clustering coefficient for weighted networks under a generalized definition of triangles. Specifically, a novel concept of triangles is introduced, based on the assumption that, should the aggregate weight of two arcs be strong enough, a link between the uncommon nodes can be induced. Beyond the intuitive meaning of such generalized triangles in the social context, we also explore the usefulness of them for gaining insights into the topological structure of the underlying network. Empirical experiments on the standard networks of 500 commercial US airports and on the nervous system of the Caenorhabditis elegans support the theoretical framework and allow a comparison between our proposal and the standard definition of clustering coefficient.
Fully Convolutional Measurement Network for Compressive Sensing Image Reconstruction
Venue: arXiv cs.CV 2018
Year: 2018

Recently, deep learning methods have made a significant improvement in compressive sensing image reconstruction task. In the existing methods, the scene is measured block by block due to the high computational complexity. This results in block-effect of the recovered images. In this paper, we propose a fully convolutional measurement network, where the scene is measured as a whole. The proposed method powerfully removes the block-effect since the structure information of scene images is preserved. To make the measure more flexible, the measurement and the recovery parts are jointly trained. From the experiments, it is shown that the results by the proposed method outperforms those by the existing methods in PSNR, SSIM, and visual effect.
iPose: Instance-Aware 6D Pose Estimation of Partly Occluded Objects
Venue: arXiv cs.CV 2018
Year: 2018

We address the task of 6D pose estimation of known rigid objects from single input images in scenarios where the objects are partly occluded. Recent RGB-D-based methods are robust to moderate degrees of occlusion. For RGB inputs, no previous method works well for partly occluded objects. Our main contribution is to present the first deep learning-based system that estimates accurate poses for partly occluded objects from RGB-D and RGB input. We achieve this with a new instance-aware pipeline that decomposes 6D object pose estimation into a sequence of simpler steps, where each step removes specific aspects of the problem. The first step localizes all known objects in the image using an instance segmentation network, and hence eliminates surrounding clutter and occluders. The second step densely maps pixels to 3D object surface positions, so called object coordinates, using an encoder-decoder network, and hence eliminates object appearance. The third, and final, step predicts the 6D pose using geometric optimization. We demonstrate that we significantly outperform the state-of-the-art for pose estimation of partly occluded objects for both RGB and RGB-D input.