October 18, 2019

3273 words 16 mins read

Paper Group ANR 573

Parallelized Interactive Machine Learning on Autonomous Vehicles. Multi-hop Inference for Sentence-level TextGraphs: How Challenging is Meaningfully Combining Information for Science Question Answering?. Smooth Structured Prediction Using Quantum and Classical Gibbs Samplers. Nonconvex Matrix Factorization from Rank-One Measurements. Physics-inform …

Parallelized Interactive Machine Learning on Autonomous Vehicles


Title	Parallelized Interactive Machine Learning on Autonomous Vehicles
Authors	Xi Chen, Caylin Hickey
Abstract	Deep reinforcement learning (deep RL) has achieved superior performance in complex sequential tasks by learning directly from image input. A deep neural network is used as a function approximator and requires no specific state information. However, one drawback of using only images as input is that this approach requires a prohibitively large amount of training time and data for the model to learn the state feature representation and approach reasonable performance. This is not feasible in real-world applications, especially when the data are expansive and training phase could introduce disasters that affect human safety. In this work, we use a human demonstration approach to speed up training for learning features and use the resulting pre-trained model to replace the neural network in the deep RL Deep Q-Network (DQN), followed by human interaction to further refine the model. We empirically evaluate our approach by using only a human demonstration model and modified DQN with human demonstration model included in the Microsoft AirSim car simulator. Our results show that (1) pre-training with human demonstration in a supervised learning approach is better and much faster at discovering features than DQN alone, (2) initializing the DQN with a pre-trained model provides a significant improvement in training time and performance even with limited human demonstration, and (3) providing the ability for humans to supply suggestions during DQN training can speed up the network’s convergence on an optimal policy, as well as allow it to learn more complex policies that are harder to discover by random exploration.
Tasks	Autonomous Vehicles
Published	2018-12-23
URL	http://arxiv.org/abs/1812.09724v1
PDF	http://arxiv.org/pdf/1812.09724v1.pdf
PWC	https://paperswithcode.com/paper/parallelized-interactive-machine-learning-on
Repo
Framework

Multi-hop Inference for Sentence-level TextGraphs: How Challenging is Meaningfully Combining Information for Science Question Answering?


Title	Multi-hop Inference for Sentence-level TextGraphs: How Challenging is Meaningfully Combining Information for Science Question Answering?
Authors	Peter Jansen
Abstract	Question Answering for complex questions is often modeled as a graph construction or traversal task, where a solver must build or traverse a graph of facts that answer and explain a given question. This “multi-hop” inference has been shown to be extremely challenging, with few models able to aggregate more than two facts before being overwhelmed by “semantic drift”, or the tendency for long chains of facts to quickly drift off topic. This is a major barrier to current inference models, as even elementary science questions require an average of 4 to 6 facts to answer and explain. In this work we empirically characterize the difficulty of building or traversing a graph of sentences connected by lexical overlap, by evaluating chance sentence aggregation quality through 9,784 manually-annotated judgments across knowledge graphs built from three free-text corpora (including study guides and Simple Wikipedia). We demonstrate semantic drift tends to be high and aggregation quality low, at between 0.04% and 3%, and highlight scenarios that maximize the likelihood of meaningfully combining information.
Tasks	graph construction, Knowledge Graphs, Question Answering
Published	2018-05-29
URL	http://arxiv.org/abs/1805.11267v1
PDF	http://arxiv.org/pdf/1805.11267v1.pdf
PWC	https://paperswithcode.com/paper/multi-hop-inference-for-sentence-level
Repo
Framework

Smooth Structured Prediction Using Quantum and Classical Gibbs Samplers


Title	Smooth Structured Prediction Using Quantum and Classical Gibbs Samplers
Authors	Behrooz Sepehry, Ehsan Iranmanesh, Michael P. Friedlander, Pooya Ronagh
Abstract	We introduce two quantum algorithms for solving structured prediction problems. We show that a stochastic subgradient descent method that uses the quantum minimum finding algorithm and takes its probabilistic failure into account solves the structured prediction problem with a runtime that scales with the square root of the size of the label space, and in $\widetilde O\left(1/\epsilon\right)$ with respect to the precision, $\epsilon$, of the solution. Motivated by robust inference techniques in machine learning, we introduce another quantum algorithm that solves a smooth approximation of the structured prediction problem with a similar quantum speedup in the size of the label space and a similar scaling in the precision parameter. In doing so, we analyze a stochastic gradient algorithm for convex optimization in the presence of an additive error in the calculation of the gradients, and show that its convergence rate does not deteriorate if the additive errors are of the order $O(\sqrt\epsilon)$. This algorithm uses quantum Gibbs sampling at temperature $\Omega (\epsilon)$ as a subroutine. Based on these theoretical observations, we propose a method for using quantum Gibbs samplers to combine feedforward neural networks with probabilistic graphical models for quantum machine learning. Our numerical results using Monte Carlo simulations on an image tagging task demonstrate the benefit of the approach.
Tasks	Quantum Machine Learning, Structured Prediction
Published	2018-09-11
URL	http://arxiv.org/abs/1809.04091v4
PDF	http://arxiv.org/pdf/1809.04091v4.pdf
PWC	https://paperswithcode.com/paper/smooth-structured-prediction-using-quantum
Repo
Framework

Nonconvex Matrix Factorization from Rank-One Measurements


Title	Nonconvex Matrix Factorization from Rank-One Measurements
Authors	Yuanxin Li, Cong Ma, Yuxin Chen, Yuejie Chi
Abstract	We consider the problem of recovering low-rank matrices from random rank-one measurements, which spans numerous applications including covariance sketching, phase retrieval, quantum state tomography, and learning shallow polynomial neural networks, among others. Our approach is to directly estimate the low-rank factor by minimizing a nonconvex quadratic loss function via vanilla gradient descent, following a tailored spectral initialization. When the true rank is small, this algorithm is guaranteed to converge to the ground truth (up to global ambiguity) with near-optimal sample complexity and computational complexity. To the best of our knowledge, this is the first guarantee that achieves near-optimality in both metrics. In particular, the key enabler of near-optimal computational guarantees is an implicit regularization phenomenon: without explicit regularization, both spectral initialization and the gradient descent iterates automatically stay within a region incoherent with the measurement vectors. This feature allows one to employ much more aggressive step sizes compared with the ones suggested in prior literature, without the need of sample splitting.
Tasks	Quantum State Tomography
Published	2018-02-17
URL	http://arxiv.org/abs/1802.06286v2
PDF	http://arxiv.org/pdf/1802.06286v2.pdf
PWC	https://paperswithcode.com/paper/nonconvex-matrix-factorization-from-rank-one
Repo
Framework

Physics-informed deep generative models


Title	Physics-informed deep generative models
Authors	Yibo Yang, Paris Perdikaris
Abstract	We consider the application of deep generative models in propagating uncertainty through complex physical systems. Specifically, we put forth an implicit variational inference formulation that constrains the generative model output to satisfy given physical laws expressed by partial differential equations. Such physics-informed constraints provide a regularization mechanism for effectively training deep probabilistic models for modeling physical systems in which the cost of data acquisition is high and training data-sets are typically small. This provides a scalable framework for characterizing uncertainty in the outputs of physical systems due to randomness in their inputs or noise in their observations. We demonstrate the effectiveness of our approach through a canonical example in transport dynamics.
Tasks
Published	2018-12-09
URL	http://arxiv.org/abs/1812.03511v1
PDF	http://arxiv.org/pdf/1812.03511v1.pdf
PWC	https://paperswithcode.com/paper/physics-informed-deep-generative-models
Repo
Framework

Explicit Bias Discovery in Visual Question Answering Models


Title	Explicit Bias Discovery in Visual Question Answering Models
Authors	Varun Manjunatha, Nirat Saini, Larry S. Davis
Abstract	Researchers have observed that Visual Question Answering (VQA) models tend to answer questions by learning statistical biases in the data. For example, their answer to the question “What is the color of the grass?” is usually “Green”, whereas a question like “What is the title of the book?” cannot be answered by inferring statistical biases. It is of interest to the community to explicitly discover such biases, both for understanding the behavior of such models, and towards debugging them. Our work address this problem. In a database, we store the words of the question, answer and visual words corresponding to regions of interest in attention maps. By running simple rule mining algorithms on this database, we discover human-interpretable rules which give us unique insight into the behavior of such models. Our results also show examples of unusual behaviors learned by models in attempting VQA tasks.
Tasks	Question Answering, Visual Question Answering
Published	2018-11-19
URL	http://arxiv.org/abs/1811.07789v1
PDF	http://arxiv.org/pdf/1811.07789v1.pdf
PWC	https://paperswithcode.com/paper/explicit-bias-discovery-in-visual-question
Repo
Framework

Learning Correlation Space for Time Series


Title	Learning Correlation Space for Time Series
Authors	Han Qiu, Hoang Thanh Lam, Francesco Fusco, Mathieu Sinn
Abstract	We propose an approximation algorithm for efficient correlation search in time series data. In our method, we use Fourier transform and neural network to embed time series into a low-dimensional Euclidean space. The given space is learned such that time series correlation can be effectively approximated from Euclidean distance between corresponding embedded vectors. Therefore, search for correlated time series can be done using an index in the embedding space for efficient nearest neighbor search. Our theoretical analysis illustrates that our method’s accuracy can be guaranteed under certain regularity conditions. We further conduct experiments on real-world datasets and the results show that our method indeed outperforms the baseline solution. In particular, for approximation of correlation, our method reduces the approximation loss by a half in most test cases compared to the baseline solution. For top-$k$ highest correlation search, our method improves the precision from 5% to 20% while the query time is similar to the baseline approach query time.
Tasks	Time Series
Published	2018-02-10
URL	http://arxiv.org/abs/1802.03628v3
PDF	http://arxiv.org/pdf/1802.03628v3.pdf
PWC	https://paperswithcode.com/paper/learning-correlation-space-for-time-series
Repo
Framework

Multi-view Reconstructive Preserving Embedding for Dimension Reduction


Title	Multi-view Reconstructive Preserving Embedding for Dimension Reduction
Authors	Huibing Wang, Lin Feng, Adong Kong, Bo Jin
Abstract	With the development of feature extraction technique, one sample always can be represented by multiple features which locate in high-dimensional space. Multiple features can re ect various perspectives of one same sample, so there must be compatible and complementary information among the multiple views. Therefore, it’s natural to integrate multiple features together to obtain better performance. However, most multi-view dimension reduction methods cannot handle multiple features from nonlinear space with high dimensions. To address this problem, we propose a novel multi-view dimension reduction method named Multi-view Reconstructive Preserving Embedding (MRPE) in this paper. MRPE reconstructs each sample by utilizing its k nearest neighbors. The similarities between each sample and its neighbors are primely mapped into lower-dimensional space in order to preserve the underlying neighborhood structure of the original manifold. MRPE fully exploits correlations between each sample and its neighbors from multiple views by linear reconstruction. Furthermore, MRPE constructs an optimization problem and derives an iterative procedure to obtain the low-dimensional embedding. Various evaluations based on the applications of document classification, face recognition and image retrieval demonstrate the effectiveness of our proposed approach on multi-view dimension reduction.
Tasks	Dimensionality Reduction, Document Classification, Face Recognition, Image Retrieval
Published	2018-07-25
URL	http://arxiv.org/abs/1807.10614v1
PDF	http://arxiv.org/pdf/1807.10614v1.pdf
PWC	https://paperswithcode.com/paper/multi-view-reconstructive-preserving
Repo
Framework

Thompson Sampling Algorithms for Cascading Bandits


Title	Thompson Sampling Algorithms for Cascading Bandits
Authors	Wang Chi Cheung, Vincent Y. F. Tan, Zixin Zhong
Abstract	Motivated by efficient optimization for online recommender systems, we revisit the cascading bandit model proposed by Kveton et al.(2015). While Thompson sampling (TS) algorithms have been shown to be empirically superior to Upper Confidence Bound (UCB) algorithms for cascading bandits, theoretical guarantees are only known for the latter, not the former. In this paper, we close the gap by designing and analyzing a TS algorithm, TS-Cascade, that achieves the state-of-the-art regret bound for cascading bandits. In complement, we derive a nearly matching regret lower bound, with information-theoretic techniques and judiciously constructed cascading bandit instances. Finally, we consider a linear generalization of the cascading bandit model, which allows efficient learning in large cascading bandit problem instances. We introduce a TS algorithm, which enjoys a regret bound that depends on the dimension of the linear model but not the number of items. Our paper establishes the first theoretical guarantees on TS algorithms for stochastic combinatorial bandit problem model with partial feedback. Numerical experiments demonstrate the superiority of our TS algorithms compared to existing UCB alogrithms.
Tasks	Efficient Exploration, Recommendation Systems
Published	2018-10-02
URL	https://arxiv.org/abs/1810.01187v2
PDF	https://arxiv.org/pdf/1810.01187v2.pdf
PWC	https://paperswithcode.com/paper/thompson-sampling-for-cascading-bandits
Repo
Framework

Multi-label Learning with Missing Labels using Mixed Dependency Graphs


Title	Multi-label Learning with Missing Labels using Mixed Dependency Graphs
Authors	Baoyuan Wu, Fan Jia, Wei Liu, Bernard Ghanem, Siwei Lyu
Abstract	This work focuses on the problem of multi-label learning with missing labels (MLML), which aims to label each test instance with multiple class labels given training instances that have an incomplete/partial set of these labels. The key point to handle missing labels is propagating the label information from provided labels to missing labels, through a dependency graph that each label of each instance is treated as a node. We build this graph by utilizing different types of label dependencies. Specifically, the instance-level similarity is served as undirected edges to connect the label nodes across different instances and the semantic label hierarchy is used as directed edges to connect different classes. This base graph is referred to as the mixed dependency graph, as it includes both undirected and directed edges. Furthermore, we present another two types of label dependencies to connect the label nodes across different classes. One is the class co-occurrence, which is also encoded as undirected edges. Combining with the base graph, we obtain a new mixed graph, called MG-CO (mixed graph with co-occurrence). The other is the sparse and low rank decomposition of the whole label matrix, to embed high-order dependencies over all labels. Combining with the base graph, the new mixed graph is called as MG-SL (mixed graph with sparse and low rank decomposition). Based on MG-CO and MG-SL, we propose two convex transductive formulations of the MLML problem, denoted as MLMG-CO and MLMG-SL, respectively. Two important applications, including image annotation and tag based image retrieval, can be jointly handled using our proposed methods. Experiments on benchmark datasets show that our methods give significant improvements in performance and robustness to missing labels over the state-of-the-art methods.
Tasks	Image Retrieval, Multi-Label Learning
Published	2018-03-31
URL	http://arxiv.org/abs/1804.00117v1
PDF	http://arxiv.org/pdf/1804.00117v1.pdf
PWC	https://paperswithcode.com/paper/multi-label-learning-with-missing-labels
Repo
Framework

Coordinated Exploration in Concurrent Reinforcement Learning


Title	Coordinated Exploration in Concurrent Reinforcement Learning
Authors	Maria Dimakopoulou, Benjamin Van Roy
Abstract	We consider a team of reinforcement learning agents that concurrently learn to operate in a common environment. We identify three properties - adaptivity, commitment, and diversity - which are necessary for efficient coordinated exploration and demonstrate that straightforward extensions to single-agent optimistic and posterior sampling approaches fail to satisfy them. As an alternative, we propose seed sampling, which extends posterior sampling in a manner that meets these requirements. Simulation results investigate how per-agent regret decreases as the number of agents grows, establishing substantial advantages of seed sampling over alternative exploration schemes.
Tasks
Published	2018-02-05
URL	http://arxiv.org/abs/1802.01282v1
PDF	http://arxiv.org/pdf/1802.01282v1.pdf
PWC	https://paperswithcode.com/paper/coordinated-exploration-in-concurrent
Repo
Framework

Variational Autoencoders Pursue PCA Directions (by Accident)


Title	Variational Autoencoders Pursue PCA Directions (by Accident)
Authors	Michal Rolinek, Dominik Zietlow, Georg Martius
Abstract	The Variational Autoencoder (VAE) is a powerful architecture capable of representation learning and generative modeling. When it comes to learning interpretable (disentangled) representations, VAE and its variants show unparalleled performance. However, the reasons for this are unclear, since a very particular alignment of the latent embedding is needed but the design of the VAE does not encourage it in any explicit way. We address this matter and offer the following explanation: the diagonal approximation in the encoder together with the inherent stochasticity force local orthogonality of the decoder. The local behavior of promoting both reconstruction and orthogonality matches closely how the PCA embedding is chosen. Alongside providing an intuitive understanding, we justify the statement with full theoretical analysis as well as with experiments.
Tasks	Representation Learning
Published	2018-12-17
URL	http://arxiv.org/abs/1812.06775v2
PDF	http://arxiv.org/pdf/1812.06775v2.pdf
PWC	https://paperswithcode.com/paper/variational-autoencoders-pursue-pca
Repo
Framework

A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs


Title	A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs
Authors	Rohit Kannan, James Luedtke
Abstract	We propose a stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs. Our approach is based on a bi-objective viewpoint of chance-constrained programs that seeks solutions on the efficient frontier of optimal objective value versus risk of constraint violation. To this end, we construct a reformulated problem whose objective is to minimize the probability of constraints violation subject to deterministic convex constraints (which includes a bound on the objective function value). We adapt existing smoothing-based approaches for chance-constrained problems to derive a convergent sequence of smooth approximations of our reformulated problem, and apply a projected stochastic subgradient algorithm to solve it. In contrast with exterior sampling-based approaches (such as sample average approximation) that approximate the original chance-constrained program with one having finite support, our proposal converges to stationary solutions of a smooth approximation of the original problem, thereby avoiding poor local solutions that may be an artefact of a fixed sample. Our proposal also includes a tailored implementation of the smoothing-based approach that chooses key algorithmic parameters based on problem data. Computational results on three test problems from the literature indicate that our proposed approach can efficiently determine good approximations of the efficient frontier.
Tasks
Published	2018-12-17
URL	https://arxiv.org/abs/1812.07066v2
PDF	https://arxiv.org/pdf/1812.07066v2.pdf
PWC	https://paperswithcode.com/paper/a-stochastic-approximation-method-for-chance
Repo
Framework

Minima distribution for global optimization


Title	Minima distribution for global optimization
Authors	Xiaopeng Luo
Abstract	This paper establishes a strict mathematical relationship between an arbitrary continuous function on a compact set and its global minima, like the well-known first order optimality condition for convex and differentiable functions. By introducing a class of nascent minima distribution functions that is only related to the target function and the given compact set, we construct a sequence that monotonically converges to the global minima on that given compact set. Then, we further consider some various sequences of sets where each sequence monotonically shrinks from the original compact set to the set of all global minimizers, and the shrink rate can be determined for continuously differentiable functions. Finally, we provide a different way of constructing the nascent minima distribution functions.
Tasks
Published	2018-12-09
URL	https://arxiv.org/abs/1812.03457v4
PDF	https://arxiv.org/pdf/1812.03457v4.pdf
PWC	https://paperswithcode.com/paper/minima-distribution-for-global-optimization
Repo
Framework

Latent Dirichlet Allocation for Internet Price War


Title	Latent Dirichlet Allocation for Internet Price War
Authors	Chenchen Li, Xiang Yan, Xiaotie Deng, Yuan Qi, Wei Chu, Le Song, Junlong Qiao, Jianshan He, Junwu Xiong
Abstract	Internet market makers are always facing intense competitive environment, where personalized price reductions or discounted coupons are provided for attracting more customers. Participants in such a price war scenario have to invest a lot to catch up with other competitors. However, such a huge cost of money may not always lead to an improvement of market share. This is mainly due to a lack of information about others’ strategies or customers’ willingness when participants develop their strategies. In order to obtain this hidden information through observable data, we study the relationship between companies and customers in the Internet price war. Theoretically, we provide a formalization of the problem as a stochastic game with imperfect and incomplete information. Then we develop a variant of Latent Dirichlet Allocation (LDA) to infer latent variables under the current market environment, which represents the preferences of customers and strategies of competitors. To our best knowledge, it is the first time that LDA is applied to game scenario. We conduct simulated experiments where our LDA model exhibits a significant improvement on finding strategies in the Internet price war by including all available market information of the market maker’s competitors. And the model is applied to an open dataset for real business. Through comparisons on the likelihood of prediction for users’ behavior and distribution distance between inferred opponent’s strategy and the real one, our model is shown to be able to provide a better understanding for the market environment. Our work marks a successful learning method to infer latent information in the environment of price war by the LDA modeling, and sets an example for related competitive applications to follow.
Tasks
Published	2018-08-23
URL	http://arxiv.org/abs/1808.07621v1
PDF	http://arxiv.org/pdf/1808.07621v1.pdf
PWC	https://paperswithcode.com/paper/latent-dirichlet-allocation-for-internet
Repo
Framework