January 29, 2020

2889 words 14 mins read

Paper Group ANR 651

Stochastic Implicit Natural Gradient for Black-box Optimization. Musical Tempo and Key Estimation using Convolutional Neural Networks with Directional Filters. Theory and Evaluation Metrics for Learning Disentangled Representations. Measuring Similarity of Interactive Driving Behaviors Using Matrix Profile. Uniform-in-Time Weak Error Analysis for S …

Stochastic Implicit Natural Gradient for Black-box Optimization


Title	Stochastic Implicit Natural Gradient for Black-box Optimization
Authors	Yueming Lyu, Ivor W. Tsang
Abstract	Black-box optimization is primarily important for many compute-intensive applications, including reinforcement learning (RL), robot control, etc. This paper presents a novel theoretical framework for black-box optimization, in which our method performs stochastic update within a trust region defined with KL-divergence. We show that this update is equivalent to a natural gradient step w.r.t. natural parameters of an exponential-family distribution. Theoretically, we prove the convergence rate of our framework for convex functions. Our theoretical results also hold for non-differentiable black-box functions. Empirically, our method achieves superior performance compared with the state-of-the-art method CMA-ES on separable benchmark test problems.
Tasks
Published	2019-10-09
URL	https://arxiv.org/abs/1910.04301v2
PDF	https://arxiv.org/pdf/1910.04301v2.pdf
PWC	https://paperswithcode.com/paper/stochastic-implicit-natural-gradient-for
Repo
Framework

Musical Tempo and Key Estimation using Convolutional Neural Networks with Directional Filters


Title	Musical Tempo and Key Estimation using Convolutional Neural Networks with Directional Filters
Authors	Hendrik Schreiber, Meinard Müller
Abstract	In this article we explore how the different semantics of spectrograms’ time and frequency axes can be exploited for musical tempo and key estimation using Convolutional Neural Networks (CNN). By addressing both tasks with the same network architectures ranging from shallow, domain-specific approaches to deep variants with directional filters, we show that axis-aligned architectures perform similarly well as common VGG-style networks developed for computer vision, while being less vulnerable to confounding factors and requiring fewer model parameters.
Tasks
Published	2019-03-26
URL	http://arxiv.org/abs/1903.10839v1
PDF	http://arxiv.org/pdf/1903.10839v1.pdf
PWC	https://paperswithcode.com/paper/musical-tempo-and-key-estimation-using
Repo
Framework

Theory and Evaluation Metrics for Learning Disentangled Representations


Title	Theory and Evaluation Metrics for Learning Disentangled Representations
Authors	Kien Do, Truyen Tran
Abstract	We make two theoretical contributions to disentanglement learning by (a) defining precise semantics of disentangled representations, and (b) establishing robust metrics for evaluation. First, we characterize the concept “disentangled representations” used in supervised and unsupervised methods along three dimensions-informativeness, separability and interpretability - which can be expressed and quantified explicitly using information-theoretic constructs. This helps explain the behaviors of several well-known disentanglement learning models. We then propose robust metrics for measuring informativeness, separability and interpretability. Through a comprehensive suite of experiments, we show that our metrics correctly characterize the representations learned by different methods and are consistent with qualitative (visual) results. Thus, the metrics allow disentanglement learning methods to be compared on a fair ground. We also empirically uncovered new interesting properties of VAE-based methods and interpreted them with our formulation. These findings are promising and hopefully will encourage the design of more theoretically driven models for learning disentangled representations.
Tasks
Published	2019-08-26
URL	https://arxiv.org/abs/1908.09961v2
PDF	https://arxiv.org/pdf/1908.09961v2.pdf
PWC	https://paperswithcode.com/paper/theory-and-evaluation-metrics-for-learning
Repo
Framework

Measuring Similarity of Interactive Driving Behaviors Using Matrix Profile


Title	Measuring Similarity of Interactive Driving Behaviors Using Matrix Profile
Authors	Qin Lin, Wenshuo Wang, Yihuan Zhang, John Dolan
Abstract	Understanding multi-vehicle interactive behaviors with temporal sequential observations is crucial for autonomous vehicles to make appropriate decisions in an uncertain traffic environment. On-demand similarity measures are significant for autonomous vehicles to deal with massive interactive driving behaviors by clustering and classifying diverse scenarios. This paper proposes a general approach for measuring spatiotemporal similarity of interactive behaviors using a multivariate matrix profile technique. The key attractive features of the approach are its superior space and time complexity, real-time online computing for streaming traffic data, and possible capability of leveraging hardware for parallel computation. The proposed approach is validated through automatically discovering similar interactive driving behaviors at intersections from sequential data.
Tasks	Autonomous Vehicles
Published	2019-10-28
URL	https://arxiv.org/abs/1910.12969v3
PDF	https://arxiv.org/pdf/1910.12969v3.pdf
PWC	https://paperswithcode.com/paper/measuring-similarity-of-interactive-driving
Repo
Framework

Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation


Title	Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
Authors	Yuanyuan Feng, Tingran Gao, Lei Li, Jian-Guo Liu, Yulong Lu
Abstract	Diffusion approximation provides weak approximation for stochastic gradient descent algorithms in a finite time horizon. In this paper, we introduce new tools motivated by the backward error analysis of numerical stochastic differential equations into the theoretical framework of diffusion approximation, extending the validity of the weak approximation from finite to infinite time horizon. The new techniques developed in this paper enable us to characterize the asymptotic behavior of constant-step-size SGD algorithms for strongly convex objective functions, a goal previously unreachable within the diffusion approximation framework. Our analysis builds upon a truncated formal power expansion of the solution of a stochastic modified equation arising from diffusion approximation, where the main technical ingredient is a uniform-in-time weak error bound controlling the long-term behavior of the expansion coefficient functions near the global minimum. We expect these new techniques to greatly expand the range of applicability of diffusion approximation to cover wider and deeper aspects of stochastic optimization algorithms in data science.
Tasks	Stochastic Optimization
Published	2019-02-02
URL	https://arxiv.org/abs/1902.00635v2
PDF	https://arxiv.org/pdf/1902.00635v2.pdf
PWC	https://paperswithcode.com/paper/uniform-in-time-weak-error-analysis-for
Repo
Framework

Joint Image and Depth Estimation with Mask-Based Lensless Cameras


Title	Joint Image and Depth Estimation with Mask-Based Lensless Cameras
Authors	Yucheng Zheng, M. Salman Asif
Abstract	Mask-based lensless cameras replace the lens of a conventional camera with a customized mask. These cameras can potentially be very thin and even flexible. Recently, it has been demonstrated that such mask-based cameras can recover light intensity and depth information of a scene. Existing depth recovery algorithms either assume that the scene consists of a small number of depth planes or solve a sparse recovery problem over a large 3D volume. Both these approaches fail to recover scene with large depth variations. In this paper, we propose a new approach for depth estimation based on alternating gradient descent algorithm that jointly estimates a continuous depth map and light distribution of the unknown scene from its lensless measurements. The computational complexity of the algorithm scales linearly with the spatial dimension of the imaging system. We present simulation results on image and depth reconstruction for a variety of 3D test scenes. A comparison between the proposed algorithm and other method shows that our algorithm is faster and more robust for natural scenes with a large range of depths.
Tasks	Depth Estimation
Published	2019-10-06
URL	https://arxiv.org/abs/1910.02526v1
PDF	https://arxiv.org/pdf/1910.02526v1.pdf
PWC	https://paperswithcode.com/paper/joint-image-and-depth-estimation-with-mask
Repo
Framework

Predicting customer’s gender and age depending on mobile phone data


Title	Predicting customer’s gender and age depending on mobile phone data
Authors	Ibrahim Mousa AlZuabi, Assef Jafar, Kadan Aljoumaa
Abstract	In the age of data driven solution, the customer demographic attributes, such as gender and age, play a core role that may enable companies to enhance the offers of their services and target the right customer in the right time and place. In the marketing campaign, the companies want to target the real user of the GSM (global system for mobile communications), not the line owner. Where sometimes they may not be the same. This work proposes a method that predicts users’ gender and age based on their behavior, services and contract information. We used call detail records (CDRs), customer relationship management (CRM) and billing information as a data source to analyze telecom customer behavior, and applied different types of machine learning algorithms to provide marketing campaigns with more accurate information about customer demographic attributes. This model is built using reliable data set of 18,000 users provided by SyriaTel Telecom Company, for training and testing. The model applied by using big data technology and achieved 85.6% accuracy in terms of user gender prediction and 65.5% of user age prediction. The main contribution of this work is the improvement in the accuracy in terms of user gender prediction and user age prediction based on mobile phone data and end-to-end solution that approaches customer data from multiple aspects in the telecom domain.
Tasks	Gender Prediction
Published	2019-02-20
URL	http://arxiv.org/abs/1903.06756v1
PDF	http://arxiv.org/pdf/1903.06756v1.pdf
PWC	https://paperswithcode.com/paper/predicting-customers-gender-and-age-depending
Repo
Framework

Stochastic Frank-Wolfe for Composite Convex Minimization


Title	Stochastic Frank-Wolfe for Composite Convex Minimization
Authors	Francesco Locatello, Alp Yurtsever, Olivier Fercoq, Volkan Cevher
Abstract	A broad class of convex optimization problems can be formulated as a semidefinite program (SDP), minimization of a convex function over the positive-semidefinite cone subject to some affine constraints. The majority of classical SDP solvers are designed for the deterministic setting where problem data is readily available. In this setting, generalized conditional gradient methods (aka Frank-Wolfe-type methods) provide scalable solutions by leveraging the so-called linear minimization oracle instead of the projection onto the semidefinite cone. Most problems in machine learning and modern engineering applications, however, contain some degree of stochasticity. In this work, we propose the first conditional-gradient-type method for solving stochastic optimization problems under affine constraints. Our method guarantees $\mathcal{O}(k^{-1/3})$ convergence rate in expectation on the objective residual and $\mathcal{O}(k^{-5/12})$ on the feasibility gap.
Tasks	Stochastic Optimization
Published	2019-01-29
URL	https://arxiv.org/abs/1901.10348v3
PDF	https://arxiv.org/pdf/1901.10348v3.pdf
PWC	https://paperswithcode.com/paper/stochastic-conditional-gradient-method-for
Repo
Framework

Bilevel Integrative Optimization for Ill-posed Inverse Problems


Title	Bilevel Integrative Optimization for Ill-posed Inverse Problems
Authors	Risheng Liu, Long Ma, Xiaoming Yuan, Shangzhi Zeng, Jin Zhang
Abstract	Classical optimization techniques often formulate the feasibility of the problems as set, equality or inequality constraints. However, explicitly designing these constraints is indeed challenging for complex real-world applications and too strict constraints may even lead to intractable optimization problems. On the other hand, it is still hard to incorporate data-dependent information into conventional numerical iterations. To partially address the above limits and inspired by the leader-follower gaming perspective, this work first introduces a bilevel-type formulation to jointly investigate the feasibility and optimality of nonconvex and nonsmooth optimization problems. Then we develop an algorithmic framework to couple forward-backward proximal computations to optimize our established bilevel leader-follower model. We prove its convergence and estimate the convergence rate. Furthermore, a learning-based extension is developed, in which we establish an unrolling strategy to incorporate data-dependent network architectures into our iterations. Fortunately, it can be proved that by introducing some mild checking conditions, all our original convergence results can still be preserved for this learnable extension. As a nontrivial byproduct, we demonstrate how to apply this ensemble-like methodology to address different low-level vision tasks. Extensive experiments verify the theoretical results and show the advantages of our method against existing state-of-the-art approaches.
Tasks
Published	2019-07-06
URL	https://arxiv.org/abs/1907.03083v1
PDF	https://arxiv.org/pdf/1907.03083v1.pdf
PWC	https://paperswithcode.com/paper/bilevel-integrative-optimization-for-ill
Repo
Framework

Knowledge-driven Encode, Retrieve, Paraphrase for Medical Image Report Generation


Title	Knowledge-driven Encode, Retrieve, Paraphrase for Medical Image Report Generation
Authors	Christy Y. Li, Xiaodan Liang, Zhiting Hu, Eric P. Xing
Abstract	Generating long and semantic-coherent reports to describe medical images poses great challenges towards bridging visual and linguistic modalities, incorporating medical domain knowledge, and generating realistic and accurate descriptions. We propose a novel Knowledge-driven Encode, Retrieve, Paraphrase (KERP) approach which reconciles traditional knowledge- and retrieval-based methods with modern learning-based methods for accurate and robust medical report generation. Specifically, KERP decomposes medical report generation into explicit medical abnormality graph learning and subsequent natural language modeling. KERP first employs an Encode module that transforms visual features into a structured abnormality graph by incorporating prior medical knowledge; then a Retrieve module that retrieves text templates based on the detected abnormalities; and lastly, a Paraphrase module that rewrites the templates according to specific cases. The core of KERP is a proposed generic implementation unit—Graph Transformer (GTR) that dynamically transforms high-level semantics between graph-structured data of multiple domains such as knowledge graphs, images and sequences. Experiments show that the proposed approach generates structured and robust reports supported with accurate abnormality description and explainable attentive regions, achieving the state-of-the-art results on two medical report benchmarks, with the best medical abnormality and disease classification accuracy and improved human evaluation performance.
Tasks	Knowledge Graphs, Language Modelling, Medical Report Generation
Published	2019-03-25
URL	http://arxiv.org/abs/1903.10122v1
PDF	http://arxiv.org/pdf/1903.10122v1.pdf
PWC	https://paperswithcode.com/paper/knowledge-driven-encode-retrieve-paraphrase
Repo
Framework

Graph-Based Decoding Model for Functional Alignment of Unaligned fMRI Data


Title	Graph-Based Decoding Model for Functional Alignment of Unaligned fMRI Data
Authors	Weida Li, Mingxia Liu, Fang Chen, Daoqiang Zhang
Abstract	Aggregating multi-subject functional magnetic resonance imaging (fMRI) data is indispensable for generating valid and general inferences from patterns distributed across human brains. The disparities in anatomical structures and functional topographies of human brains warrant aligning fMRI data across subjects. However, the existing functional alignment methods cannot handle well various kinds of fMRI datasets today, especially when they are not temporally-aligned, i.e., some of the subjects probably lack the responses to some stimuli, or different subjects might follow different sequences of stimuli. In this paper, a cross-subject graph that depicts the (dis)similarities between samples across subjects is used as a priori for developing a more flexible framework that suits an assortment of fMRI datasets. However, the high dimension of fMRI data and the use of multiple subjects makes the crude framework time-consuming or unpractical. To address this issue, we further regularize the framework, so that a novel feasible kernel-based optimization, which permits nonlinear feature extraction, could be theoretically developed. Specifically, a low-dimension assumption is imposed on each new feature space to avoid overfitting caused by the highspatial-low-temporal resolution of fMRI data. Experimental results on five datasets suggest that the proposed method is not only superior to several state-of-the-art methods on temporally-aligned fMRI data, but also suitable for dealing `with temporally-unaligned fMRI data. \|
Tasks
Published	2019-05-14
URL	https://arxiv.org/abs/1905.05468v8
PDF	https://arxiv.org/pdf/1905.05468v8.pdf
PWC	https://paperswithcode.com/paper/a-graph-based-decoding-model-for-incomplete
Repo
Framework

Measuring the Algorithmic Convergence of Randomized Ensembles: The Regression Setting


Title	Measuring the Algorithmic Convergence of Randomized Ensembles: The Regression Setting
Authors	Miles E. Lopes, Suofei Wu, Thomas C. M. Lee
Abstract	When randomized ensemble methods such as bagging and random forests are implemented, a basic question arises: Is the ensemble large enough? In particular, the practitioner desires a rigorous guarantee that a given ensemble will perform nearly as well as an ideal infinite ensemble (trained on the same data). The purpose of the current paper is to develop a bootstrap method for solving this problem in the context of regression — which complements our companion paper in the context of classification (Lopes 2019). In contrast to the classification setting, the current paper shows that theoretical guarantees for the proposed bootstrap can be established under much weaker assumptions. In addition, we illustrate the flexibility of the method by showing how it can be adapted to measure algorithmic convergence for variable selection. Lastly, we provide numerical results demonstrating that the method works well in a range of situations.
Tasks
Published	2019-08-04
URL	https://arxiv.org/abs/1908.01251v1
PDF	https://arxiv.org/pdf/1908.01251v1.pdf
PWC	https://paperswithcode.com/paper/measuring-the-algorithmic-convergence-of
Repo
Framework

A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms


Title	A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms
Authors	Donghwan Lee, Niao He
Abstract	In this paper, we introduce a unified framework for analyzing a large family of Q-learning algorithms, based on switching system perspectives and ODE-based stochastic approximation. We show that the nonlinear ODE models associated with these Q-learning algorithms can be formulated as switched linear systems, and analyze their asymptotic stability by leveraging existing switching system theories. Our approach provides the first O.D.E. analysis of the asymptotic convergence of various Q-learning algorithms, including asynchronous Q-learning and averaging Q-learning. We also extend the approach to analyze Q-learning with linear function approximation and derive a new sufficient condition for its convergence.
Tasks	Q-Learning
Published	2019-12-04
URL	https://arxiv.org/abs/1912.02270v2
PDF	https://arxiv.org/pdf/1912.02270v2.pdf
PWC	https://paperswithcode.com/paper/a-unified-switching-system-perspective-and
Repo
Framework

When Your Robot Breaks: Active Learning During Plant Failure


Title	When Your Robot Breaks: Active Learning During Plant Failure
Authors	Mariah Schrum, Matthew Gombolay
Abstract	Detecting and adapting to catastrophic failures in robotic systems requires a robot to learn its new dynamics quickly and safely to best accomplish its goals. To address this challenging problem, we propose probabilistically-safe, online learning techniques to infer the altered dynamics of a robot at the moment a failure (e.g., physical damage) occurs. We combine model predictive control and active learning within a chance-constrained optimization framework to safely and efficiently learn the new plant model of the robot. We leverage a neural network for function approximation in learning the latent dynamics of the robot under failure conditions. Our framework generalizes to various damage conditions while being computationally light-weight to advance real-time deployment. We empirically validate within a virtual environment that we can regain control of a severely damaged aircraft in seconds and require only 0.1 seconds to find safe, information-rich trajectories, outperforming state-of-the-art approaches.
Tasks	Active Learning
Published	2019-12-17
URL	https://arxiv.org/abs/1912.08116v1
PDF	https://arxiv.org/pdf/1912.08116v1.pdf
PWC	https://paperswithcode.com/paper/when-your-robot-breaks-active-learning-during
Repo
Framework

Analysis of Lower Bounds for Simple Policy Iteration


Title	Analysis of Lower Bounds for Simple Policy Iteration
Authors	Sarthak Consul, Bhishma Dedhia, Kumar Ashutosh, Parthasarathi Khirwadkar
Abstract	Policy iteration is a family of algorithms that are used to find an optimal policy for a given Markov Decision Problem (MDP). Simple Policy iteration (SPI) is a type of policy iteration where the strategy is to change the policy at exactly one improvable state at every step. Melekopoglou and Condon [1990] showed an exponential lower bound on the number of iterations taken by SPI for a 2 action MDP. The results have not been generalized to $k-$action MDP since. In this paper, we revisit the algorithm and the analysis done by Melekopoglou and Condon. We generalize the previous result and prove a novel exponential lower bound on the number of iterations taken by policy iteration for $N-$state, $k-$action MDPs. We construct a family of MDPs and give an index-based switching rule that yields a strong lower bound of $\mathcal{O}\big((3+k)2^{N/2-3}\big)$.
Tasks
Published	2019-11-28
URL	https://arxiv.org/abs/1911.12842v1
PDF	https://arxiv.org/pdf/1911.12842v1.pdf
PWC	https://paperswithcode.com/paper/analysis-of-lower-bounds-for-simple-policy
Repo
Framework