OpenRaiser/Intern-Atlas huggingface dataset:
Target-driven Visual Navigation in Indoor Scenes using Deep Reinforcement Learning
Venue: arXiv cs.CV 2016
Year: 2016

Two less addressed issues of deep reinforcement learning are (1) lack of generalization capability to new target goals, and (2) data inefficiency i.e., the model requires several (and often costly) episodes of trial and error to converge, which makes it impractical to be applied to real-world scenarios. In this paper, we address these two issues and apply our model to the task of target-driven visual navigation. To address the first issue, we propose an actor-critic model whose policy is a function of the goal as well as the current state, which allows to better generalize. To address the second issue, we propose AI2-THOR framework, which provides an environment with high-quality 3D scenes and physics engine. Our framework enables agents to take actions and interact with objects. Hence, we can collect a huge number of training samples efficiently. We show that our proposed method (1) converges faster than the state-of-the-art deep reinforcement learning methods, (2) generalizes across targets and across scenes, (3) generalizes to a real robot scenario with a small amount of fine-tuning (although the model is trained in simulation), (4) is end-to-end trainable and does not need feature engineering, feature matching between frames or 3D reconstruction of the environment. The supplementary video can be accessed at the following link: https://youtu.be/SmBxMDiOrvs.
Prioritised Default Logic as Argumentation with Partial Order Default Priorities
Venue: arXiv cs.AI 2016
Year: 2016

We express Brewka's prioritised default logic (PDL) as argumentation using ASPIC+. By representing PDL as argumentation and designing an argument preference relation that takes the argument structure into account, we prove that the conclusions of the justified arguments correspond to the PDL extensions. We will first assume that the default priority is total, and then generalise to the case where it is a partial order. This provides a characterisation of non-monotonic inference in PDL as an exchange of argument and counter-argument, providing a basis for distributed non-monotonic reasoning in the form of dialogue.
RFM-SLAM: Exploiting Relative Feature Measurements to Separate Orientation and Position Estimation in SLAM
Venue: arXiv cs.RO 2016
Year: 2016

The SLAM problem is known to have a special property that when robot orientation is known, estimating the history of robot poses and feature locations can be posed as a standard linear least squares problem. In this work, we develop a SLAM framework that uses relative feature-to-feature measurements to exploit this structural property of SLAM. Relative feature measurements are used to pose a linear estimation problem for pose-to-pose orientation constraints. This is followed by solving an iterative non-linear on-manifold optimization problem to compute the maximum likelihood estimate for robot orientation given relative rotation constraints. Once the robot orientation is computed, we solve a linear problem for robot position and map estimation. Our approach reduces the computational burden of non-linear optimization by posing a smaller optimization problem as compared to standard graph-based methods for feature-based SLAM. Further, empirical results show our method avoids catastrophic failures that arise in existing methods due to using odometery as an initial guess for non-linear optimization, while its accuracy degrades gracefully as sensor noise is increased. We demonstrate our method through extensive simulations and comparisons with an existing state-of-the-art solver.
Capacity of the Two-Hop Relay Channel with Wireless Energy Transfer from Relay to Source and Energy Transmission Cost
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we investigate a communication system comprised of an energy harvesting (EH) source which harvests radio frequency (RF) energy from an out-of-band full-duplex relay node and exploits this energy to transmit data to a destination node via the relay node. We assume two scenarios for the battery of the EH source. In the first scenario, we assume that the EH source is not equipped with a battery and thereby cannot store energy. As a result, the RF energy harvested during one symbol interval can only be used in the following symbol interval. In the second scenario, we assume that the EH source is equipped with a battery having unlimited storage capacity in which it can store the harvested RF energy. As a result, the RF energy harvested during one symbol interval can be used in any of the following symbol intervals. For both system models, we derive the channel capacity subject to an average power constraint at the relay and an additional energy transmission cost at the EH source. We compare the derived capacities to the achievable rates of several benchmark schemes. Our results show that using the optimal input distributions at both the EH source and the relay is essential for high performance. Moreover, we demonstrate that neglecting the energy transmission cost at the source can result in a severe overestimation of the achievable performance.
Detection of Biasing Attacks on Distributed Estimation Networks
Venue: arXiv cs.SY 2016
Year: 2016

The paper addresses the problem of detecting attacks on distributed estimator networks that aim to intentionally bias process estimates produced by the network. It provides a sufficient condition, in terms of the feasibility of certain linear matrix inequalities, which guarantees distributed input attack detection using an $H_\infty$ approach.
On protocol and physical interference models in Poisson wireless networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper analyzes the connection between the protocol and physical interference models in the setting of Poisson wireless networks. A transmission is successful under the protocol model if there are no interferers within a parameterized guard zone around the receiver, while a transmission is successful under the physical model if the signal to interference plus noise ratio (SINR) at the receiver is above a threshold. The parameterized protocol model forms a family of decision rules for predicting the success or failure of the same transmission attempt under the physical model. For Poisson wireless networks, we employ stochastic geometry to determine the prior, evidence, and posterior distributions associated with this estimation problem. With this in hand, we proceed to develop five sets of results: i) the maximum correlation of protocol and physical model success indicators, ii) the minimum Bayes risk in estimating physical success from a protocol observation, iii) the receiver operating characteristic (ROC) of false rejection (Type I) and false acceptance (Type II) probabilities, iv) the impact of Rayleigh fading vs. no fading on the correlation and ROC, and v) the impact of multiple prior protocol model observations in the setting of a wireless network with a fixed set of nodes in which the nodes employ the slotted Aloha protocol in each time slot.
Fast and Effective Algorithms for Symmetric Nonnegative Matrix Factorization
Venue: arXiv cs.CV 2016
Year: 2016

Symmetric Nonnegative Matrix Factorization (SNMF) models arise naturally as simple reformulations of many standard clustering algorithms including the popular spectral clustering method. Recent work has demonstrated that an elementary instance of SNMF provides superior clustering quality compared to many classic clustering algorithms on a variety of synthetic and real world data sets. In this work, we present novel reformulations of this instance of SNMF based on the notion of variable splitting and produce two fast and effective algorithms for its optimization using i) the provably convergent Accelerated Proximal Gradient (APG) procedure and ii) a heuristic version of the Alternating Direction Method of Multipliers (ADMM) framework. Our two algorithms present an interesting tradeoff between computational speed and mathematical convergence guarantee: while the former method is provably convergent it is considerably slower than the latter approach, for which we also provide significant but less stringent mathematical proof regarding its convergence. Through extensive experiments we show not only that the efficacy of these approaches is equal to that of the state of the art SNMF algorithm, but also that the latter of our algorithms is extremely fast being one to two orders of magnitude faster in terms of total computation time than the state of the art approach, outperforming even spectral clustering in terms of computation time on large data sets.
Optimisations for Real-Time Volumetric Cloudscapes
Venue: arXiv cs.GR 2016
Year: 2016

Volumetric cloudscapes are prohibitively expensive to render in real time without extensive optimisations. Previous approaches render the clouds to an offscreen buffer at one quarter resolution and update a fraction of the pixels per frame, drawing the remaining pixels by temporal reprojection. We present an alternative approach, reducing the number of raymarching steps and adding a randomly jittered offset to the raymarch. We use an analytical integration technique to make results consistent with a lower number of raymarching steps. To remove noise from the resulting image we apply a temporal anti-aliasing implementation. The result is a technique producing visually similar results with 1/16 the number of steps.
Taming Context-Sensitive Languages with Principled Stateful Parsing
Venue: arXiv cs.PL 2016
Year: 2016

Historically, true context-sensitive parsing has seldom been applied to programming languages, due to its inherent complexity. However, many mainstream programming and markup languages (C, Haskell, Python, XML, and more) possess context-sensitive features. These features are traditionally handled with ad-hoc code (e.g., custom lexers), outside of the scope of parsing theory. Current grammar formalisms struggle to express context-sensitive features. Most solutions lack context transparency: they make grammars hard to write, maintain and compose by hardwiring context through the entire grammar. Instead, we approach context-sensitive parsing through the idea that parsers may recall previously matched input (or data derived therefrom) in order to make parsing decisions. We make use of mutable parse state to enable this form of recall. We introduce principled stateful parsing as a new transactional discipline that makes state changes transparent to parsing mechanisms such as backtracking and memoization. To enforce this discipline, users specify parsers using formally specified primitive state manipulation operations. Our solution is available as a parsing library named Autumn. We illustrate our solution by implementing some practical context-sensitive grammar features such as significant whitespace handling and namespace classification.
Consistent Discretization and Minimization of the L1 Norm on Manifolds
Venue: arXiv cs.NA 2016
Year: 2016

The L1 norm has been tremendously popular in signal and image processing in the past two decades due to its sparsity-promoting properties. More recently, its generalization to non-Euclidean domains has been found useful in shape analysis applications. For example, in conjunction with the minimization of the Dirichlet energy, it was shown to produce a compactly supported quasi-harmonic orthonormal basis, dubbed as compressed manifold modes. The continuous L1 norm on the manifold is often replaced by the vector l1 norm applied to sampled functions. We show that such an approach is incorrect in the sense that it does not consistently discretize the continuous norm and warn against its sensitivity to the specific sampling. We propose two alternative discretizations resulting in an iteratively-reweighed l2 norm. We demonstrate the proposed strategy on the compressed modes problem, which reduces to a sequence of simple eigendecomposition problems not requiring non-convex optimization on Stiefel manifolds and producing more stable and accurate results.
Genetic Algorithm-based Mapper to Support Multiple Concurrent Users on Wireless Testbeds
Venue: arXiv cs.NI 2016
Year: 2016

Communication and networking research introduces new protocols and standards with an increasing number of researchers relying on real experiments rather than simulations to evaluate the performance of their new protocols. A number of testbeds are currently available for this purpose and a growing number of users are requesting access to those testbeds. This motivates the need for better utilization of the testbeds by allowing concurrent experimentations. In this work, we introduce a novel mapping algorithm that aims to maximize wireless testbed utilization using frequency slicing of the spectrum resources. The mapper employs genetic algorithm to find the best combination of requests that can be served concurrently, after getting all possible mappings of each request via an induced sub-graph isomorphism stage. The proposed mapper is tested on grid testbeds and randomly generated topologies. The solution of our mapper is compared to the optimal one, obtained through a brute-force search, and was able to serve the same number of requests in 82.96% of testing scenarios. Furthermore, we show the effect of the careful design of testbed topology on enhancing the testbed utilization by applying our mapper on a carefully positioned 8-nodes testbed. In addition, our proposed approach for testbed slicing and requests mapping has shown an improved performance in terms of total served requests, about five folds, compared to the simple allocation policy with no slicing.
Learning camera viewpoint using CNN to improve 3D body pose estimation
Venue: arXiv cs.CV 2016
Year: 2016

The objective of this work is to estimate 3D human pose from a single RGB image. Extracting image representations which incorporate both spatial relation of body parts and their relative depth plays an essential role in accurate3D pose reconstruction. In this paper, for the first time, we show that camera viewpoint in combination to 2D joint lo-cations significantly improves 3D pose accuracy without the explicit use of perspective geometry mathematical models.To this end, we train a deep Convolutional Neural Net-work (CNN) to learn categorical camera viewpoint. To make the network robust against clothing and body shape of the subject in the image, we utilized 3D computer rendering to synthesize additional training images. We test our framework on the largest 3D pose estimation bench-mark, Human3.6m, and achieve up to 20% error reduction compared to the state-of-the-art approaches that do not use body part segmentation.
Learning Personalized Optimal Control for Repeatedly Operated Systems
Venue: arXiv cs.LG 2016
Year: 2016

We consider the problem of online learning of optimal control for repeatedly operated systems in the presence of parametric uncertainty. During each round of operation, environment selects system parameters according to a fixed but unknown probability distribution. These parameters govern the dynamics of a plant. An agent chooses a control input to the plant and is then revealed the cost of the choice. In this setting, we design an agent that personalizes the control input to this plant taking into account the stochasticity involved. We demonstrate the effectiveness of our approach on a simulated system.
Label-Free Supervision of Neural Networks with Physics and Domain Knowledge
Venue: arXiv cs.AI 2016
Year: 2016

In many machine learning applications, labeled data is scarce and obtaining more labels is expensive. We introduce a new approach to supervising neural networks by specifying constraints that should hold over the output space, rather than direct examples of input-output pairs. These constraints are derived from prior domain knowledge, e.g., from known laws of physics. We demonstrate the effectiveness of this approach on real world and simulated computer vision tasks. We are able to train a convolutional neural network to detect and track objects without any labeled examples. Our approach can significantly reduce the need for labeled training data, but introduces new challenges for encoding prior knowledge into appropriate loss functions.
A GRASP approach for solving the 2-connected m-dominating set problem
Venue: arXiv cs.DM 2016
Year: 2016

In this paper, we present a constructive heuristic algorithm for the $2$-connected $m$-dominating set problem. It is based on a greedy heuristic in which a 2-connected subgraph is iteratively extended with suitable open ears. The growth procedure is an adaptation of the breadth-first-search which efficiently manages to find open ears. Further, a heuristic function is defined for selecting the best ear out of a list of candidates. The performance of the basic approach is improved by adding a correction procedure which removes unnecessary nodes from a generated solution. Finally, randomization is included and the method is extended towards the GRASP metaheuristic. In our computational experiments, we compare the performance of the proposed algorithm to recently published results and show that the method is highly competitive and especially suitable for dense graphs.
The Undecidability of Arbitrary Arrow Update Logic
Venue: arXiv cs.LO 2016
Year: 2016

Arbitrary Arrow Update Logic is a dynamic modal logic that uses an arbitrary arrow update modality to quantify over all arrow updates. Some properties of this logic have already been established, but until now it remained an open question whether the logic's satisfiability problem is decidable. Here, we show that the satisfiability problem of Arbitrary Arrow Update Logic is co-RE hard, and therefore undecidable, by a reduction of the tiling problem.
Mixing Oscillators for Phase Noise Reduction
Venue: arXiv cs.IT 2016
Year: 2016

The output of oscillators is usually not stable over time. In particular, phase variations---or \emph{phase noise}---corrupts the oscillations. In this letter, we describe a circuit that designed to average the phase noise processes and frequency offsets in frequency-matched oscillators. The basic circuit uses the independence of 2 phase noise processes to provide a cleaner oscillating output with lower phase noise variance. We describe extensions of the circuit designed to average out more than 2 oscillators, as well as a single one through delay elements. In all the examples covered, we provide a theoretical analysis of the resulting phase noise process when the input phase noise processes follow a Wiener model.
SpectroMeter: Amortized Sublinear Spectral Approximation of Distance on Graphs
Venue: arXiv cs.DS 2016
Year: 2016

We present a method to approximate pairwise distance on a graph, having an amortized sub-linear complexity in its size. The proposed method follows the so called heat method due to Crane et al. The only additional input are the values of the eigenfunctions of the graph Laplacian at a subset of the vertices. Using these values we estimate a random walk from the source points, and normalize the result into a unit gradient function. The eigenfunctions are then used to synthesize distance values abiding by these constraints at desired locations. We show that this method works in practice on different types of inputs ranging from triangular meshes to general graphs. We also demonstrate that the resulting approximate distance is accurate enough to be used as the input to a recent method for intrinsic shape correspondence computation.
Integrating citizen science with online learning to ask better questions
Venue: arXiv cs.HC 2016
Year: 2016

Online learners spend millions of hours per year testing their new skills on assignments with known answers. This paper explores whether framing research questions as assignments with unknown answers helps learners generate novel, useful, and difficult-to-find knowledge while increasing their motivation by contributing to a larger goal. Collaborating with the American Gut Project, the world's largest crowdfunded citizen science project, we deploy Gut Instinct to allow novices to generate hypotheses about the constitution of the human gut microbiome. The tool enables online learners to explore learning material about the microbiome and create their own theories around causal variances for microbiome. Building on crowdsourcing or serious games that use people as replaceable units, this work-in-progress lays our plans for how people (a) use their personal knowledge (b) towards solving a larger real-world goal (c) that can provide potential benefits to them. We hope to demonstrate that Gut Instinct citizen scientists generate useful hypotheses, perform better on learning tasks than traditional MOOC learners, and are better engaged with the learning material.
Context-aware Sequential Recommendation
Venue: arXiv cs.IR 2016
Year: 2016

Since sequential information plays an important role in modeling user behaviors, various sequential recommendation methods have been proposed. Methods based on Markov assumption are widely-used, but independently combine several most recent components. Recently, Recurrent Neural Networks (RNN) based methods have been successfully applied in several sequential modeling tasks. However, for real-world applications, these methods have difficulty in modeling the contextual information, which has been proved to be very important for behavior modeling. In this paper, we propose a novel model, named Context-Aware Recurrent Neural Networks (CA-RNN). Instead of using the constant input matrix and transition matrix in conventional RNN models, CA-RNN employs adaptive context-specific input matrices and adaptive context-specific transition matrices. The adaptive context-specific input matrices capture external situations where user behaviors happen, such as time, location, weather and so on. And the adaptive context-specific transition matrices capture how lengths of time intervals between adjacent behaviors in historical sequences affect the transition of global sequential features. Experimental results show that the proposed CA-RNN model yields significant improvements over state-of-the-art sequential recommendation methods and context-aware recommendation methods on two public datasets, i.e., the Taobao dataset and the Movielens-1M dataset.
Active Integrity Constraints for Multi-Context Systems
Venue: arXiv cs.DB 2016
Year: 2016

We introduce a formalism to couple integrity constraints over general-purpose knowledge bases with actions that can be executed to restore consistency. This formalism generalizes active integrity constraints over databases. In the more general setting of multi-context systems, adding repair suggestions to integrity constraints allows defining simple iterative algorithms to find all possible grounded repairs - repairs for the global system that follow the suggestions given by the actions in the individual rules. We apply our methodology to ontologies, and show that it can express most relevant types of integrity constraints in this domain.
Automatic Quality Assessment for Speech Translation Using Joint ASR and MT Features
Venue: arXiv cs.CL 2016
Year: 2016

This paper addresses automatic quality assessment of spoken language translation (SLT). This relatively new task is defined and formalized as a sequence labeling problem where each word in the SLT hypothesis is tagged as good or bad according to a large feature set. We propose several word confidence estimators (WCE) based on our automatic evaluation of transcription (ASR) quality, translation (MT) quality, or both (combined ASR+MT). This research work is possible because we built a specific corpus which contains 6.7k utterances for which a quintuplet containing: ASR output, verbatim transcript, text translation, speech translation and post-edition of translation is built. The conclusion of our multiple experiments using joint ASR and MT features for WCE is that MT features remain the most influent while ASR feature can bring interesting complementary information. Our robust quality estimators for SLT can be used for re-scoring speech translation graphs or for providing feedback to the user in interactive speech translation or computer-assisted speech-to-text scenarios.