OpenRaiser/Intern-Atlas huggingface dataset:
Superimposed Pilots are Superior for Mitigating Pilot Contamination in Massive MIMO
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, superimposed pilots are introduced as an alternative to time-multiplexed pilot and data symbols for mitigating pilot contamination in massive multiple-input multiple-output (MIMO) systems. We propose a non-iterative scheme for uplink channel estimation based on superimposed pilots and derive an expression for the uplink signal-to-interference-plus-noise ratio (SINR) at the output of a matched filter employing this channel estimate. Based on this expression, we observe that power control is essential when superimposed pilots are employed. Moreover, the quality of the channel estimate can be improved by reducing the interference that results from transmitting data alongside the pilots, and an intuitive iterative data-aided scheme that reduces this component of interference is also proposed. Approximate expressions for the uplink SINR are provided for the iterative data-aided method as well. In addition, we show that a hybrid system with users utilizing both time-multiplexed and superimposed pilots is superior to an optimally designed system that employs only time-multiplexed pilots, even when the non-iterative channel estimate is used to build the detector and precoder. We also describe a simple approach to implement this hybrid system by minimizing the overall inter and intra-cell interference. Numerical simulations demonstrating the performance of the proposed channel estimation schemes and the superiority of the hybrid system are also provided.
Object Manipulation Learning by Imitation
Venue: arXiv cs.RO 2017
Year: 2017

We aim to enable robot to learn object manipulation by imitation. Given external observations of demonstrations on object manipulations, we believe that two underlying problems to address in learning by imitation is 1) segment a given demonstration into skills that can be individually learned and reused, and 2) formulate the correct RL (Reinforcement Learning) problem that only considers the relevant aspects of each skill so that the policy for each skill can be effectively learned. Previous works made certain progress in this direction, but none has taken private information into account. The public information is the information that is available in the external observations of demonstration, and the private information is the information that are only available to the agent that executes the actions, such as tactile sensations. Our contribution is that we provide a method for the robot to automatically segment the demonstration of object manipulations into multiple skills, and formulate the correct RL problem for each skill, and automatically decide whether the private information is an important aspect of each skill based on interaction with the world. Our experiment shows that our robot learns to pick up a block, and stack it onto another block by imitating an observed demonstration. The evaluation is based on 1) whether the demonstration is reasonably segmented, 2) whether the correct RL problems are formulated, 3) and whether a good policy is learned.
HyperFace: A Deep Multi-task Learning Framework for Face Detection, Landmark Localization, Pose Estimation, and Gender Recognition
Venue: arXiv cs.CV 2017
Year: 2017

We present an algorithm for simultaneous face detection, landmarks localization, pose estimation and gender recognition using deep convolutional neural networks (CNN). The proposed method called, HyperFace, fuses the intermediate layers of a deep CNN using a separate CNN followed by a multi-task learning algorithm that operates on the fused features. It exploits the synergy among the tasks which boosts up their individual performances. Additionally, we propose two variants of HyperFace: (1) HyperFace-ResNet that builds on the ResNet-101 model and achieves significant improvement in performance, and (2) Fast-HyperFace that uses a high recall fast face detector for generating region proposals to improve the speed of the algorithm. Extensive experiments show that the proposed models are able to capture both global and local information in faces and performs significantly better than many competitive algorithms for each of these four tasks.
A New Method to Visualize Deep Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

We present a method for visualising the response of a deep neural network to a specific input. For image data for instance our method will highlight areas that provide evidence in favor of, and against choosing a certain class. The method overcomes several shortcomings of previous methods and provides great additional insight into the decision making process of convolutional networks, which is important both to improve models and to accelerate the adoption of such methods in e.g. medicine. In experiments on ImageNet data, we illustrate how the method works and can be applied in different ways to understand deep neural nets.
Computational complexity of exterior products and multi-particle amplitudes of non-interacting fermions in entangled states
Venue: arXiv cs.CC 2017
Year: 2017

Noninteracting bosons were proposed to be used for a demonstration of quantum-computing supremacy in a boson-sampling setup. A similar demonstration with fermions would require that the fermions are initially prepared in an entangled state. I suggest that pairwise entanglement of fermions would be sufficient for this purpose. Namely, it is shown that computing multi-particle scattering amplitudes for fermions entangled pairwise in groups of four single-particle states is #P hard. In linear algebra, such amplitudes are expressed as exterior products of two-forms of rank two. In particular, a permanent of a NxN matrix may be expressed as an exterior product of N^2 two-forms of rank two in dimension 2N^2, which establishes the #P-hardness of the latter.
Optimal Estimation via Nonanticipative Rate Distortion Function and Applications to Time-Varying Gauss-Markov Processes
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we develop {finite-time horizon} causal filters using the nonanticipative rate distortion theory. We apply the {developed} theory to {design optimal filters for} time-varying multidimensional Gauss-Markov processes, subject to a mean square error fidelity constraint. We show that such filters are equivalent to the design of an optimal \texttt{\{encoder, channel, decoder\}}, which ensures that the error satisfies {a} fidelity constraint. Moreover, we derive a universal lower bound on the mean square error of any estimator of time-varying multidimensional Gauss-Markov processes in terms of conditional mutual information. Unlike classical Kalman filters, the filter developed is characterized by a reverse-waterfilling algorithm, which ensures {that} the fidelity constraint is satisfied. The theoretical results are demonstrated via illustrative examples.
Universal probability-free prediction
Venue: arXiv cs.LG 2017
Year: 2017

We construct universal prediction systems in the spirit of Popper's falsifiability and Kolmogorov complexity and randomness. These prediction systems do not depend on any statistical assumptions (but under the IID assumption they dominate, to within the usual accuracy, conformal prediction). Our constructions give rise to a theory of algorithmic complexity and randomness of time containing analogues of several notions and results of the classical theory of Kolmogorov complexity and randomness.
Learning Domain-Invariant Subspace using Domain Features and Independence Maximization
Venue: arXiv cs.CV 2017
Year: 2017

Domain adaptation algorithms are useful when the distributions of the training and the test data are different. In this paper, we focus on the problem of instrumental variation and time-varying drift in the field of sensors and measurement, which can be viewed as discrete and continuous distributional change in the feature space. We propose maximum independence domain adaptation (MIDA) and semi-supervised MIDA (SMIDA) to address this problem. Domain features are first defined to describe the background information of a sample, such as the device label and acquisition time. Then, MIDA learns a subspace which has maximum independence with the domain features, so as to reduce the inter-domain discrepancy in distributions. A feature augmentation strategy is also designed to project samples according to their backgrounds so as to improve the adaptation. The proposed algorithms are flexible and fast. Their effectiveness is verified by experiments on synthetic datasets and four real-world ones on sensors, measurement, and computer vision. They can greatly enhance the practicability of sensor systems, as well as extend the application scope of existing domain adaptation algorithms by uniformly handling different kinds of distributional change.
Deep Fully-Connected Networks for Video Compressive Sensing
Venue: arXiv cs.CV 2017
Year: 2017

In this work we present a deep learning framework for video compressive sensing. The proposed formulation enables recovery of video frames in a few seconds at significantly improved reconstruction quality compared to previous approaches. Our investigation starts by learning a linear mapping between video sequences and corresponding measured frames which turns out to provide promising results. We then extend the linear formulation to deep fully-connected networks and explore the performance gains using deeper architectures. Our analysis is always driven by the applicability of the proposed framework on existing compressive video architectures. Extensive simulations on several video sequences document the superiority of our approach both quantitatively and qualitatively. Finally, our analysis offers insights into understanding how dataset sizes and number of layers affect reconstruction performance while raising a few points for future investigation. Code is available at Github: https://github.com/miliadis/DeepVideoCS
On Hamiltonian alternating cycles and paths
Venue: arXiv cs.CG 2017
Year: 2017

We undertake a study on computing Hamiltonian alternating cycles and paths on bicolored point sets. This has been an intensively studied problem, not always with a solution, when the paths and cycles are also required to be plane. In this paper, we relax the constraint on the cycles and paths from being plane to being 1-plane, and deal with the same type of questions as those for the plane case, obtaining a remarkable variety of results. Among them, we prove that a 1-plane Hamiltonian alternating cycle on a bicolored point set in general position can always be obtained, and that when the point set is in convex position, every Hamiltonian alternating cycle with minimum number of crossings is 1-plane. Further, for point sets in convex position, we provide $O(n)$ and $O(n^2)$ time algorithms for computing, respectively, Hamiltonian alternating cycles and paths with minimum number of crossings.
Evaluating semantic models with word-sentence relatedness
Venue: arXiv cs.CL 2017
Year: 2017

Semantic textual similarity (STS) systems are designed to encode and evaluate the semantic similarity between words, phrases, sentences, and documents. One method for assessing the quality or authenticity of semantic information encoded in these systems is by comparison with human judgments. A data set for evaluating semantic models was developed consisting of 775 English word-sentence pairs, each annotated for semantic relatedness by human raters engaged in a Maximum Difference Scaling (MDS) task, as well as a faster alternative task. As a sample application of this relatedness data, behavior-based relatedness was compared to the relatedness computed via four off-the-shelf STS models: n-gram, Latent Semantic Analysis (LSA), Word2Vec, and UMBC Ebiquity. Some STS models captured much of the variance in the human judgments collected, but they were not sensitive to the implicatures and entailments that were processed and considered by the participants. All text stimuli and judgment data have been made freely available.
Energy Scaling of Targeted Optimal Control of Complex Networks
Venue: arXiv cs.SY 2017
Year: 2017

Recently it has been shown that the control energy required to control a dynamical complex network is prohibitively large when there are only a few control inputs. Most methods to reduce the control energy have focused on where, in the network, to place additional control inputs. Here, in contrast, we show that by controlling the states of a subset of the nodes of a network, rather than the state of every node, while holding the number of control signals constant, the required energy to control a portion of the network can be reduced substantially. The energy requirements exponentially decay with the number of target nodes, suggesting that large networks can be controlled by a relatively small number of inputs as long as the target set is appropriately sized. We validate our conclusions in model and real networks to arrive at an energy scaling law to better design control objectives regardless of system size, energy restrictions, state restrictions, input node choices and target node choices.
Encoding Arguments
Venue: arXiv cs.IT 2017
Year: 2017

Many proofs in discrete mathematics and theoretical computer science are based on the probabilistic method. To prove the existence of a good object, we pick a random object and show that it is bad with low probability. This method is effective, but the underlying probabilistic machinery can be daunting. "Encoding arguments" provide an alternative presentation in which probabilistic reasoning is encapsulated in a "uniform encoding lemma". This lemma provides an upper bound on the probability of an event using the fact that a uniformly random choice from a set of size $n$ cannot be encoded with fewer than $\log_2 n$ bits on average. With the lemma, the argument reduces to devising an encoding where bad objects have short codewords. In this expository article, we describe the basic method and provide a simple tutorial on how to use it. After that, we survey many applications to classic problems from discrete mathematics and computer science. We also give a generalization for the case of non-uniform distributions, as well as a rigorous justification for the use of non-integer codeword lengths in encoding arguments. These latter two results allow encoding arguments to be applied more widely and to produce tighter results.
Towards Understanding Sparse Filtering: A Theoretical Perspective
Venue: arXiv cs.LG 2017
Year: 2017

In this paper we present a theoretical analysis to understand sparse filtering, a recent and effective algorithm for unsupervised learning. The aim of this research is not to show whether or how well sparse filtering works, but to understand why and when sparse filtering does work. We provide a thorough theoretical analysis of sparse filtering and its properties, and further offer an experimental validation of the main outcomes of our theoretical analysis. We show that sparse filtering works by explicitly maximizing the entropy of the learned representation through the maximization of the proxy of sparsity, and by implicitly preserving mutual information between original and learned representations through the constraint of preserving a structure of the data, specifically the structure defined by relations of neighborhoodness under the cosine distance. Furthermore, we empirically validate our theoretical results with artificial and real data sets, and we apply our theoretical understanding to explain the success of sparse filtering on real-world problems. Our work provides a strong theoretical basis for understanding sparse filtering: it highlights assumptions and conditions for success behind this feature distribution learning algorithm, and provides insights for developing new feature distribution learning algorithms.
FAST: A Framework to Accelerate Super-Resolution Processing on Compressed Videos
Venue: arXiv cs.CV 2017
Year: 2017

State-of-the-art super-resolution (SR) algorithms require significant computational resources to achieve real-time throughput (e.g., 60Mpixels/s for HD video). This paper introduces FAST (Free Adaptive Super-resolution via Transfer), a framework to accelerate any SR algorithm applied to compressed videos. FAST exploits the temporal correlation between adjacent frames such that SR is only applied to a subset of frames; SR pixels are then transferred to the other frames. The transferring process has negligible computation cost as it uses information already embedded in the compressed video (e.g., motion vectors and residual). Adaptive processing is used to retain accuracy when the temporal correlation is not present (e.g., occlusions). FAST accelerates state-of-the-art SR algorithms by up to 15x with a visual quality loss of 0.2dB. FAST is an important step towards real-time SR algorithms for ultra-HD displays and energy constrained devices (e.g., phones and tablets).
Adaptive Computation Time for Recurrent Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

This paper introduces Adaptive Computation Time (ACT), an algorithm that allows recurrent neural networks to learn how many computational steps to take between receiving an input and emitting an output. ACT requires minimal changes to the network architecture, is deterministic and differentiable, and does not add any noise to the parameter gradients. Experimental results are provided for four synthetic problems: determining the parity of binary vectors, applying binary logic operations, adding integers, and sorting real numbers. Overall, performance is dramatically improved by the use of ACT, which successfully adapts the number of computational steps to the requirements of the problem. We also present character-level language modelling results on the Hutter prize Wikipedia dataset. In this case ACT does not yield large gains in performance; however it does provide intriguing insight into the structure of the data, with more computation allocated to harder-to-predict transitions, such as spaces between words and ends of sentences. This suggests that ACT or other adaptive computation methods could provide a generic method for inferring segment boundaries in sequence data.
Adaptive Maximization of Pointwise Submodular Functions With Budget Constraint
Venue: arXiv cs.AI 2017
Year: 2017

We study the worst-case adaptive optimization problem with budget constraint that is useful for modeling various practical applications in artificial intelligence and machine learning. We investigate the near-optimality of greedy algorithms for this problem with both modular and non-modular cost functions. In both cases, we prove that two simple greedy algorithms are not near-optimal but the best between them is near-optimal if the utility function satisfies pointwise submodularity and pointwise cost-sensitive submodularity respectively. This implies a combined algorithm that is near-optimal with respect to the optimal algorithm that uses half of the budget. We discuss applications of our theoretical results and also report experiments comparing the greedy algorithms on the active learning problem.
Cost-Sensitive Label Embedding for Multi-Label Classification
Venue: arXiv cs.LG 2017
Year: 2017

Label embedding (LE) is an important family of multi-label classification algorithms that digest the label information jointly for better performance. Different real-world applications evaluate performance by different cost functions of interest. Current LE algorithms often aim to optimize one specific cost function, but they can suffer from bad performance with respect to other cost functions. In this paper, we resolve the performance issue by proposing a novel cost-sensitive LE algorithm that takes the cost function of interest into account. The proposed algorithm, cost-sensitive label embedding with multidimensional scaling (CLEMS), approximates the cost information with the distances of the embedded vectors by using the classic multidimensional scaling approach for manifold learning. CLEMS is able to deal with both symmetric and asymmetric cost functions, and effectively makes cost-sensitive decisions by nearest-neighbor decoding within the embedded vectors. We derive theoretical results that justify how CLEMS achieves the desired cost-sensitivity. Furthermore, extensive experimental results demonstrate that CLEMS is significantly better than a wide spectrum of existing LE algorithms and state-of-the-art cost-sensitive algorithms across different cost functions.
Analysis of gradient descent methods with non-diminishing, bounded errors
Venue: arXiv cs.SY 2017
Year: 2017

The main aim of this paper is to provide an analysis of gradient descent (GD) algorithms with gradient errors that do not necessarily vanish, asymptotically. In particular, sufficient conditions are presented for both stability (almost sure boundedness of the iterates) and convergence of GD with bounded, (possibly) non-diminishing gradient errors. In addition to ensuring stability, such an algorithm is shown to converge to a small neighborhood of the minimum set, which depends on the gradient errors. It is worth noting that the main result of this paper can be used to show that GD with asymptotically vanishing errors indeed converges to the minimum set. The results presented herein are not only more general when compared to previous results, but our analysis of GD with errors is new to the literature to the best of our knowledge. Our work extends the contributions of Mangasarian & Solodov, Bertsekas & Tsitsiklis and Tadic & Doucet. Using our framework, a simple yet effective implementation of GD using simultaneous perturbation stochastic approximations (SP SA), with constant sensitivity parameters, is presented. Another important improvement over many previous results is that there are no `additional' restrictions imposed on the step-sizes. In machine learning applications where step-sizes are related to learning rates, our assumptions, unlike those of other papers, do not affect these learning rates. Finally, we present experimental results to validate our theory.
PHOCNet: A Deep Convolutional Neural Network for Word Spotting in Handwritten Documents
Venue: arXiv cs.CV 2017
Year: 2017

In recent years, deep convolutional neural networks have achieved state of the art performance in various computer vision task such as classification, detection or segmentation. Due to their outstanding performance, CNNs are more and more used in the field of document image analysis as well. In this work, we present a CNN architecture that is trained with the recently proposed PHOC representation. We show empirically that our CNN architecture is able to outperform state of the art results for various word spotting benchmarks while exhibiting short training and test times.
Half-Duplex or Full-Duplex Communications: Degrees of Freedom Analysis under Self-Interference
Venue: arXiv cs.IT 2017
Year: 2017

In-band full-duplex (FD) communication provides a promising alternative to half-duplex (HD) for wireless systems, due to increased spectral efficiency and capacity. In this paper, HD and FD radio implementations of two way, two hop and two way two hop communication are compared in terms of degrees of freedom (DoF) under a realistic residual self-interference (SI) model. DoF analysis is carried out for each communication scenario for HD, antenna conserved (AC) and RF chain conserved (RC) FD radio implementations. The DoF analysis indicates that for the two way channel, the achievable AC FD with imperfect SI cancellation performs strictly below HD, and RC FD DoF trade-off is superior when the SI can be sufficiently cancelled. For the two hop channel, FD is better when the relay has large number of antennas and enough SI cancellation. For the two way two hop channel, when both nodes require similar throughput, the achievable DoF pairs for FD do not outperform HD. FD still can achieve better DoF pairs than HD, provided the relay has sufficient number of antennas and SI suppression.