OpenRaiser/Intern-Atlas huggingface dataset:
An Extended Treatment of Uncertainty Constrained robotic Exploration: An Integrated Exploration Planner
Venue: arXiv cs.RO 2017
Year: 2017

Efficient robotic exploration of unknown, sensor limited, global-information-deficient environments poses unique challenges to path planning algorithms. In these difficult environments, no deterministic guarantees on path completion and mission success can be made in general. Integrated Exploration (IE), which strives to combine localization and exploration, must be solved in order to create an autonomous robotic system capable of long term operation in new and challenging environments. This paper formulates a probabilistic framework which allows the creation of exploration algorithms providing probabilistic guarantees of success. A novel connection is made between the Hamiltonian Path Problem and exploration. The Guaranteed Probabilistic Information Explorer (G-PIE) is developed for the IE problem, providing a probabilistic guarantee on path completion, and asymptotic optimality of exploration. A receding horizon formulation, dubbed RH-PIE, is presented which addresses the exponential complexity present in G-PIE. Finally, RH-PIE planner is verified via autonomous, hardware-in-the-loop experiments.
Generalized RBF kernel for incomplete data
Venue: arXiv cs.LG 2017
Year: 2017

We construct $\bf genRBF$ kernel, which generalizes the classical Gaussian RBF kernel to the case of incomplete data. We model the uncertainty contained in missing attributes making use of data distribution and associate every point with a conditional probability density function. This allows to embed incomplete data into the function space and to define a kernel between two missing data points based on scalar product in $L_2$. Experiments show that introduced kernel applied to SVM classifier gives better results than other state-of-the-art methods, especially in the case when large number of features is missing. Moreover, it is easy to implement and can be used together with any kernel approaches with no additional modifications.
Plane Gossip: Approximating rumor spread in planar graphs
Venue: arXiv cs.DS 2017
Year: 2017

We study the design of schedules for multi-commodity multicast; we are given an undirected graph $G$ and a collection of source destination pairs, and the goal is to schedule a minimum-length sequence of matchings that connects every source with its respective destination. Multi-commodity multicast models a classic information dissemination problem in networks where the primary communication constraint is the number of connections that a node can make, not link bandwidth. Multi-commodity multicast is closely related to the problem of finding a subgraph, $H$, of optimal poise, where the poise is defined as the sum of the maximum degree of $H$ and the maximum distance between any source-destination pair in $H$. We first show that the minimum poise subgraph for single-commodity multicast can be approximated to within a factor of $O(\log k)$ with respect to the value of a natural LP relaxation in an instance with $k$ terminals. This is the first upper bound on the integrality gap of the natural LP. Using this poise result and shortest-path separators in planar graphs, we obtain a $O(\log^3 k\log n/(\log\log n))$-approximation for multi-commodity multicast for planar graphs. We also study the minimum-time radio gossip problem in planar graphs where a message from each node must be transmitted to all other nodes under a model where nodes can broadcast to all neighbors in a single step but only nodes with a single broadcasting neighbor get a message. We give an $O(\log^2 n)$-approximation for radio gossip in planar graphs breaking previous barriers. This is the first bound for radio gossip that does not rely on the maximum degree of the graph. Finally, we show that our techniques for planar graphs extend to graphs with excluded minors. We establish polylogarithmic-approximation algorithms for both multi-commodity multicast and radio gossip problems in minor-free graphs.
Logic and Topology for Knowledge, Knowability, and Belief
Venue: arXiv cs.LO 2017
Year: 2017

In recent work, Stalnaker proposes a logical framework in which belief is realized as a weakened form of knowledge. Building on Stalnaker's core insights, and using frameworks developed in previous work by Bjorndahl and Baltag et al., we employ topological tools to refine and, we argue, improve on this analysis. The structure of topological subset spaces allows for a natural distinction between what is known and (roughly speaking) what is knowable; we argue that the foundational axioms of Stalnaker's system rely intuitively on both of these notions. More precisely, we argue that the plausibility of the principles Stalnaker proposes relating knowledge and belief relies on a subtle equivocation between an "evidence-in-hand" conception of knowledge and a weaker "evidence-out-there" notion of what could come to be known. Our analysis leads to a trimodal logic of knowledge, knowability, and belief interpreted in topological subset spaces in which belief is definable in terms of knowledge and knowability. We provide a sound and complete axiomatization for this logic as well as its uni-modal belief fragment. We then consider weaker logics that preserve suitable translations of Stalnaker's postulates, yet do not allow for any reduction of belief. We propose novel topological semantics for these irreducible notions of belief, generalizing our previous semantics, and provide sound and complete axiomatizations for the corresponding logics.
A Functional Regression approach to Facial Landmark Tracking
Venue: arXiv cs.CV 2017
Year: 2017

Linear regression is a fundamental building block in many face detection and tracking algorithms, typically used to predict shape displacements from image features through a linear mapping. This paper presents a Functional Regression solution to the least squares problem, which we coin Continuous Regression, resulting in the first real-time incremental face tracker. Contrary to prior work in Functional Regression, in which B-splines or Fourier series were used, we propose to approximate the input space by its first-order Taylor expansion, yielding a closed-form solution for the continuous domain of displacements. We then extend the continuous least squares problem to correlated variables, and demonstrate the generalisation of our approach. We incorporate Continuous Regression into the cascaded regression framework, and show its computational benefits for both training and testing. We then present a fast approach for incremental learning within Cascaded Continuous Regression, coined iCCR, and show that its complexity allows real-time face tracking, being 20 times faster than the state of the art. To the best of our knowledge, this is the first incremental face tracker that is shown to operate in real-time. We show that iCCR achieves state-of-the-art performance on the 300-VW dataset, the most recent, large-scale benchmark for face tracking.
Sparse Geometric Representation Through Local Shape Probing
Venue: arXiv cs.CG 2017
Year: 2017

We propose a new shape analysis approach based on the non-local analysis of local shape variations. Our method relies on a novel description of shape variations, called Local Probing Field (LPF), which describes how a local probing operator transforms a pattern onto the shape. By carefully optimizing the position and orientation of each descriptor, we are able to capture shape similarities and gather them into a geometrically relevant dictionary over which the shape decomposes sparsely. This new representation permits to handle shapes with mixed intrinsic dimensionality (e.g. shapes containing both surfaces and curves) and to encode various shape features such as boundaries. Our shape representation has several potential applications; here we demonstrate its efficiency for shape resampling and point set denoising for both synthetic and real data.
Quotient inductive-inductive types
Venue: arXiv cs.LO 2017
Year: 2017

Higher inductive types (HITs) in Homotopy Type Theory (HoTT) allow the definition of datatypes which have constructors for equalities over the defined type. HITs generalise quotient types and allow to define types which are not sets in the sense of HoTT (i.e. do not satisfy uniqueness of equality proofs) such as spheres, suspensions and the torus. However, there are also interesting uses of HITs to define sets, such as the Cauchy reals, the partiality monad, and the internal, total syntax of type theory. In each of these examples we define several types that depend on each other mutually, i.e. they are inductive-inductive definitions. We call those HITs quotient inductive-inductive types (QIITs). Although there has been recent progress on the general theory of HITs, there isn't yet a theoretical foundation of the combination of equality constructors and induction-induction, despite having many interesting applications. In the present paper we present a first step towards a semantic definition of QIITs. In particular, we give an initial-algebra semantics and show that this is equivalent to the section induction principle, which justifies the intuitively expected elimination rules.
Scene Flow Estimation: A Survey
Venue: arXiv cs.CV 2017
Year: 2017

This paper is the first to review the scene flow estimation field, which analyzes and compares methods, technical challenges, evaluation methodologies and performance of scene flow estimation. Existing algorithms are categorized in terms of scene representation, data source, and calculation scheme, and the pros and cons in each category are compared briefly. The datasets and evaluation protocols are enumerated, and the performance of the most representative methods is presented. A future vision is illustrated with few questions arisen for discussion. This survey presents a general introduction and analysis of scene flow estimation.
Learning in the Machine: Random Backpropagation and the Deep Learning Channel
Venue: arXiv cs.LG 2017
Year: 2017

Random backpropagation (RBP) is a variant of the backpropagation algorithm for training neural networks, where the transpose of the forward matrices are replaced by fixed random matrices in the calculation of the weight updates. It is remarkable both because of its effectiveness, in spite of using random matrices to communicate error information, and because it completely removes the taxing requirement of maintaining symmetric weights in a physical neural system. To better understand random backpropagation, we first connect it to the notions of local learning and learning channels. Through this connection, we derive several alternatives to RBP, including skipped RBP (SRPB), adaptive RBP (ARBP), sparse RBP, and their combinations (e.g. ASRBP) and analyze their computational complexity. We then study their behavior through simulations using the MNIST and CIFAR-10 bechnmark datasets. These simulations show that most of these variants work robustly, almost as well as backpropagation, and that multiplication by the derivatives of the activation functions is important. As a follow-up, we study also the low-end of the number of bits required to communicate error information over the learning channel. We then provide partial intuitive explanations for some of the remarkable properties of RBP and its variations. Finally, we prove several mathematical results, including the convergence to fixed points of linear chains of arbitrary length, the convergence to fixed points of linear autoencoders with decorrelated data, the long-term existence of solutions for linear systems with a single hidden layer and convergence in special cases, and the convergence to fixed points of non-linear chains, when the derivative of the activation functions is included.
Optimal Design of Energy and Spectral Efficiency Tradeoff in One-Bit Massive MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers a single-cell massive multiple-input multiple-output (MIMO) system equipped with a base station (BS) that uses one-bit quantization and investigates the energy efficiency (EE) and spectral efficiency (SE) trade-off. We first propose a new precoding scheme and downlink power allocation strategy that results in uplink-downlink SINR duality for one-bit MIMO systems. Taking into account the effect of the imperfect channel state information, we obtain approximate closed-form expressions for the uplink and downlink achievable rates under duality with maximum ratio combining/matched-filter and zero-forcing processing. We then focus on joint optimization of the competing SE and EE objectives over the number of users, pilot training duration and operating power, using the weighted product method to obtain the EE/SE Pareto boundary. Numerical results are presented to verify our analytical resultsand demonstrate the fundamental tradeoff between EE and SE for different parameter settings.
An Attention-Driven Approach of No-Reference Image Quality Assessment
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we present a novel method of no-reference image quality assessment (NR-IQA), which is to predict the perceptual quality score of a given image without using any reference image. The proposed method harnesses three functions (i) the visual attention mechanism, which affects many aspects of visual perception including image quality assessment, however, is overlooked in the NR-IQA literature. The method assumes that the fixation areas on an image contain key information to the process of IQA. (ii) the robust averaging strategy, which is a means \--- supported by psychology studies \--- to integrating multiple/step-wise evidence to make a final perceptual judgment. (iii) the multi-task learning, which is believed to be an effectual means to shape representation learning and could result in a more generalized model. To exploit the synergy of the three, we consider the NR-IQA as a dynamic perception process, in which the model samples a sequence of "informative" areas and aggregates the information to learn a representation for the tasks of jointly predicting the image quality score and the distortion type. The model learning is implemented by a reinforcement strategy, in which the rewards of both tasks guide the learning of the optimal sampling policy to acquire the "task-informative" image regions so that the predictions can be made accurately and efficiently (in terms of the sampling steps). The reinforcement learning is realized by a deep network with the policy gradient method and trained through back-propagation. In experiments, the model is tested on the TID2008 dataset and it outperforms several state-of-the-art methods. Furthermore, the model is very efficient in the sense that a small number of fixations are used in NR-IQA.
Learning to Drive using Inverse Reinforcement Learning and Deep Q-Networks
Venue: arXiv cs.AI 2017
Year: 2017

We propose an inverse reinforcement learning (IRL) approach using Deep Q-Networks to extract the rewards in problems with large state spaces. We evaluate the performance of this approach in a simulation-based autonomous driving scenario. Our results resemble the intuitive relation between the reward function and readings of distance sensors mounted at different poses on the car. We also show that, after a few learning rounds, our simulated agent generates collision-free motions and performs human-like lane change behaviour.
Neurogenesis Deep Learning
Venue: arXiv cs.NE 2017
Year: 2017

Neural machine learning methods, such as deep neural networks (DNN), have achieved remarkable success in a number of complex data processing tasks. These methods have arguably had their strongest impact on tasks such as image and audio processing - data processing domains in which humans have long held clear advantages over conventional algorithms. In contrast to biological neural systems, which are capable of learning continuously, deep artificial networks have a limited ability for incorporating new information in an already trained network. As a result, methods for continuous learning are potentially highly impactful in enabling the application of deep networks to dynamic data sets. Here, inspired by the process of adult neurogenesis in the hippocampus, we explore the potential for adding new neurons to deep layers of artificial neural networks in order to facilitate their acquisition of novel information while preserving previously trained data representations. Our results on the MNIST handwritten digit dataset and the NIST SD 19 dataset, which includes lower and upper case letters and digits, demonstrate that neurogenesis is well suited for addressing the stability-plasticity dilemma that has long challenged adaptive machine learning algorithms.
Neural Machine Translation by Minimising the Bayes-risk with Respect to Syntactic Translation Lattices
Venue: arXiv cs.CL 2017
Year: 2017

We present a novel scheme to combine neural machine translation (NMT) with traditional statistical machine translation (SMT). Our approach borrows ideas from linearised lattice minimum Bayes-risk decoding for SMT. The NMT score is combined with the Bayes-risk of the translation according the SMT lattice. This makes our approach much more flexible than $n$-best list or lattice rescoring as the neural decoder is not restricted to the SMT search space. We show an efficient and simple way to integrate risk estimation into the NMT decoder which is suitable for word-level as well as subword-unit-level NMT. We test our method on English-German and Japanese-English and report significant gains over lattice rescoring on several data sets for both single and ensembled NMT. The MBR decoder produces entirely new hypotheses far beyond simply rescoring the SMT search space or fixing UNKs in the NMT output.
Models of retrieval in sentence comprehension: A computational evaluation using Bayesian hierarchical modeling
Venue: arXiv cs.CL 2017
Year: 2017

Research on interference has provided evidence that the formation of dependencies between non-adjacent words relies on a cue-based retrieval mechanism. Two different models can account for one of the main predictions of interference, i.e., a slowdown at a retrieval site, when several items share a feature associated with a retrieval cue: Lewis and Vasishth's (2005) activation-based model and McElree's (2000) direct access model. Even though these two models have been used almost interchangeably, they are based on different assumptions and predict differences in the relationship between reading times and response accuracy. The activation-based model follows the assumptions of ACT-R, and its retrieval process behaves as a lognormal race between accumulators of evidence with a single variance. Under this model, accuracy of the retrieval is determined by the winner of the race and retrieval time by its rate of accumulation. In contrast, the direct access model assumes a model of memory where only the probability of retrieval varies between items; in this model, differences in latencies are a by-product of the possibility and repairing incorrect retrievals. We implemented both models in a Bayesian hierarchical framework in order to evaluate them and compare them. We show that some aspects of the data are better fit under the direct access model than under the activation-based model. We suggest that this finding does not rule out the possibility that retrieval may be behaving as a race model with assumptions that follow less closely the ones from the ACT-R framework. We show that by introducing a modification of the activation model, i.e, by assuming that the accumulation of evidence for retrieval of incorrect items is not only slower but noisier (i.e., different variances for the correct and incorrect items), the model can provide a fit as good as the one of the direct access model.
Compressive Image Recovery Using Recurrent Generative Model
Venue: arXiv cs.CV 2017
Year: 2017

Reconstruction of signals from compressively sensed measurements is an ill-posed problem. In this paper, we leverage the recurrent generative model, RIDE, as an image prior for compressive image reconstruction. Recurrent networks can model long-range dependencies in images and hence are suitable to handle global multiplexing in reconstruction from compressive imaging. We perform MAP inference with RIDE using back-propagation to the inputs and projected gradient method. We propose an entropy thresholding based approach for preserving texture in images well. Our approach shows superior reconstructions compared to recent global reconstruction approaches like D-AMP and TVAL3 on both simulated and real data.
Memcomputing Numerical Inversion with Self-Organizing Logic Gates
Venue: arXiv cs.ET 2017
Year: 2017

We propose to use Digital Memcomputing Machines (DMMs), implemented with self-organizing logic gates (SOLGs), to solve the problem of numerical inversion. Starting from fixed-point scalar inversion we describe the generalization to solving linear systems and matrix inversion. This method, when realized in hardware, will output the result in only one computational step. As an example, we perform simulations of the scalar case using a 5-bit logic circuit made of SOLGs, and show that the circuit successfully performs the inversion. Our method can be extended efficiently to any level of precision, since we prove that producing n-bit precision in the output requires extending the circuit by at most n bits. This type of numerical inversion can be implemented by DMM units in hardware, it is scalable, and thus of great benefit to any real-time computing application.
Your Processor Leaks Information - and There's Nothing You Can Do About It
Venue: arXiv cs.CR 2017
Year: 2017

Timing channels are information flows, encoded in the relative timing of events, that bypass the system's protection mechanisms. Any microarchitectural state that depends on execution history and affects the rate of progress of later executions potentially establishes a timing channel, unless explicit steps are taken to close it. Such state includes CPU caches, TLBs, branch predictors and prefetchers; removing the channels requires that the OS can partition such state or flush it on a switch of security domains. We measure the capacities of channels based on these microarchitectural features on several generations of processors across the two mainstream ISAs, x86 and ARM, and investigate the effectiveness of the flushing mechanisms provided by the respective ISA.We find that in all processors we studied, at least one significant channel remains. This implies that closing all timing channels seems impossible on contemporary mainstream processors.
Operating Massive MIMO in Unlicensed Bands for Enhanced Coexistence and Spatial Reuse
Venue: arXiv cs.IT 2017
Year: 2017

We propose to operate massive multiple-input multiple output (MIMO) cellular base stations (BSs) in unlicensed bands. We denote such system as massive MIMO unlicensed (mMIMO-U). We design the key procedures required at a cellular BS to guarantee coexistence with nearby Wi-Fi devices operating in the same band. In particular, spatial reuse is enhanced by actively suppressing interference towards neighboring Wi-Fi devices. Wi-Fi interference rejection is also performed during an enhanced listen-before-talk (LBT) phase. These operations enable Wi-Fi devices to access the channel as though no cellular BSs were transmitting, and vice versa. Under concurrent Wi-Fi and BS transmissions, the downlink rates attainable by cellular user equipment (UEs) are degraded by the Wi-Fi-generated interference. To mitigate this effect, we select a suitable set of UEs to be served in the unlicensed band accounting for a measure of the Wi-Fi/UE proximity. Our results show that the so-designed mMIMO-U allows simultaneous cellular and Wi-Fi transmissions by keeping their mutual interference below the regulatory threshold. Compared to a system without interference suppression, Wi-Fi devices enjoy a median interference power reduction of between 3 dB with 16 antennas and 18 dB with 128 antennas. With mMIMO-U, cellular BSs can also achieve large data rates without significantly degrading the performance of Wi-Fi networks deployed within their coverage area.