Paper Group ANR 480
Bayesian Optimization with Exponential Convergence. Diversity Promoting Online Sampling for Streaming Video Summarization. Stream Clipper: Scalable Submodular Maximization on Stream. Faster Principal Component Regression and Stable Matrix Chebyshev Approximation. Scaling Submodular Maximization via Pruned Submodularity Graphs. Reinforcement Learnin …
Bayesian Optimization with Exponential Convergence
| Title | Bayesian Optimization with Exponential Convergence |
| Authors | Kenji Kawaguchi, Leslie Pack Kaelbling, Tomás Lozano-Pérez |
| Abstract | This paper presents a Bayesian optimization method with exponential convergence without the need of auxiliary optimization and without the delta-cover sampling. Most Bayesian optimization methods require auxiliary optimization: an additional non-convex global optimization problem, which can be time-consuming and hard to implement in practice. Also, the existing Bayesian optimization method with exponential convergence requires access to the delta-cover sampling, which was considered to be impractical. Our approach eliminates both requirements and achieves an exponential convergence rate. |
| Tasks | |
| Published | 2016-04-05 |
| URL | http://arxiv.org/abs/1604.01348v1 |
| http://arxiv.org/pdf/1604.01348v1.pdf | |
| PWC | https://paperswithcode.com/paper/bayesian-optimization-with-exponential |
| Repo | |
| Framework | |
Diversity Promoting Online Sampling for Streaming Video Summarization
| Title | Diversity Promoting Online Sampling for Streaming Video Summarization |
| Authors | Rushil Anirudh, Ahnaf Masroor, Pavan Turaga |
| Abstract | Many applications benefit from sampling algorithms where a small number of well chosen samples are used to generalize different properties of a large dataset. In this paper, we use diverse sampling for streaming video summarization. Several emerging applications support streaming video, but existing summarization algorithms need access to the entire video which requires a lot of memory and computational power. We propose a memory efficient and computationally fast, online algorithm that uses competitive learning for diverse sampling. Our algorithm is a generalization of online K-means such that the cost function reduces clustering error, while also ensuring a diverse set of samples. The diversity is measured as the volume of a convex hull around the samples. Finally, the performance of the proposed algorithm is measured against human users for 50 videos in the VSUMM dataset. The algorithm performs better than batch mode summarization, while requiring significantly lower memory and computational requirements. |
| Tasks | Video Summarization |
| Published | 2016-10-29 |
| URL | http://arxiv.org/abs/1610.09582v1 |
| http://arxiv.org/pdf/1610.09582v1.pdf | |
| PWC | https://paperswithcode.com/paper/diversity-promoting-online-sampling-for |
| Repo | |
| Framework | |
Stream Clipper: Scalable Submodular Maximization on Stream
| Title | Stream Clipper: Scalable Submodular Maximization on Stream |
| Authors | Tianyi Zhou, Jeff Bilmes |
| Abstract | We propose a streaming submodular maximization algorithm “stream clipper” that performs as well as the offline greedy algorithm on document/video summarization in practice. It adds elements from a stream either to a solution set $S$ or to an extra buffer $B$ based on two adaptive thresholds, and improves $S$ by a final greedy step that starts from $S$ adding elements from $B$. During this process, swapping elements out of $S$ can occur if doing so yields improvements. The thresholds adapt based on if current memory utilization exceeds a budget, e.g., it increases the lower threshold, and removes from the buffer $B$ elements below the new lower threshold. We show that, while our approximation factor in the worst case is $1/2$ (like in previous work, and corresponding to the tight bound), we show that there are data-dependent conditions where our bound falls within the range $[1/2, 1-1/e]$. In news and video summarization experiments, the algorithm consistently outperforms other streaming methods, and, while using significantly less computation and memory, performs similarly to the offline greedy algorithm. |
| Tasks | Video Summarization |
| Published | 2016-06-01 |
| URL | http://arxiv.org/abs/1606.00389v3 |
| http://arxiv.org/pdf/1606.00389v3.pdf | |
| PWC | https://paperswithcode.com/paper/stream-clipper-scalable-submodular |
| Repo | |
| Framework | |
Faster Principal Component Regression and Stable Matrix Chebyshev Approximation
| Title | Faster Principal Component Regression and Stable Matrix Chebyshev Approximation |
| Authors | Zeyuan Allen-Zhu, Yuanzhi Li |
| Abstract | We solve principal component regression (PCR), up to a multiplicative accuracy $1+\gamma$, by reducing the problem to $\tilde{O}(\gamma^{-1})$ black-box calls of ridge regression. Therefore, our algorithm does not require any explicit construction of the top principal components, and is suitable for large-scale PCR instances. In contrast, previous result requires $\tilde{O}(\gamma^{-2})$ such black-box calls. We obtain this result by developing a general stable recurrence formula for matrix Chebyshev polynomials, and a degree-optimal polynomial approximation to the matrix sign function. Our techniques may be of independent interests, especially when designing iterative methods. |
| Tasks | |
| Published | 2016-08-16 |
| URL | http://arxiv.org/abs/1608.04773v2 |
| http://arxiv.org/pdf/1608.04773v2.pdf | |
| PWC | https://paperswithcode.com/paper/faster-principal-component-regression-and |
| Repo | |
| Framework | |
Scaling Submodular Maximization via Pruned Submodularity Graphs
| Title | Scaling Submodular Maximization via Pruned Submodularity Graphs |
| Authors | Tianyi Zhou, Hua Ouyang, Yi Chang, Jeff Bilmes, Carlos Guestrin |
| Abstract | We propose a new random pruning method (called “submodular sparsification (SS)") to reduce the cost of submodular maximization. The pruning is applied via a “submodularity graph” over the $n$ ground elements, where each directed edge is associated with a pairwise dependency defined by the submodular function. In each step, SS prunes a $1-1/\sqrt{c}$ (for $c>1$) fraction of the nodes using weights on edges computed based on only a small number ($O(\log n)$) of randomly sampled nodes. The algorithm requires $\log_{\sqrt{c}}n$ steps with a small and highly parallelizable per-step computation. An accuracy-speed tradeoff parameter $c$, set as $c = 8$, leads to a fast shrink rate $\sqrt{2}/4$ and small iteration complexity $\log_{2\sqrt{2}}n$. Analysis shows that w.h.p., the greedy algorithm on the pruned set of size $O(\log^2 n)$ can achieve a guarantee similar to that of processing the original dataset. In news and video summarization tasks, SS is able to substantially reduce both computational costs and memory usage, while maintaining (or even slightly exceeding) the quality of the original (and much more costly) greedy algorithm. |
| Tasks | Video Summarization |
| Published | 2016-06-01 |
| URL | http://arxiv.org/abs/1606.00399v1 |
| http://arxiv.org/pdf/1606.00399v1.pdf | |
| PWC | https://paperswithcode.com/paper/scaling-submodular-maximization-via-pruned |
| Repo | |
| Framework | |
Reinforcement Learning in Rich-Observation MDPs using Spectral Methods
| Title | Reinforcement Learning in Rich-Observation MDPs using Spectral Methods |
| Authors | Kamyar Azizzadenesheli, Alessandro Lazaric, Animashree Anandkumar |
| Abstract | Reinforcement learning (RL) in Markov decision processes (MDPs) with large state spaces is a challenging problem. The performance of standard RL algorithms degrades drastically with the dimensionality of state space. However, in practice, these large MDPs typically incorporate a latent or hidden low-dimensional structure. In this paper, we study the setting of rich-observation Markov decision processes (ROMDP), where there are a small number of hidden states which possess an injective mapping to the observation states. In other words, every observation state is generated through a single hidden state, and this mapping is unknown a priori. We introduce a spectral decomposition method that consistently learns this mapping, and more importantly, achieves it with low regret. The estimated mapping is integrated into an optimistic RL algorithm (UCRL), which operates on the estimated hidden space. We derive finite-time regret bounds for our algorithm with a weak dependence on the dimensionality of the observed space. In fact, our algorithm asymptotically achieves the same average regret as the oracle UCRL algorithm, which has the knowledge of the mapping from hidden to observed spaces. Thus, we derive an efficient spectral RL algorithm for ROMDPs. |
| Tasks | |
| Published | 2016-11-11 |
| URL | http://arxiv.org/abs/1611.03907v4 |
| http://arxiv.org/pdf/1611.03907v4.pdf | |
| PWC | https://paperswithcode.com/paper/reinforcement-learning-in-rich-observation |
| Repo | |
| Framework | |
Crowdsourcing On-street Parking Space Detection
| Title | Crowdsourcing On-street Parking Space Detection |
| Authors | Ruizhi Liao, Cristian Roman, Peter Ball, Shumao Ou, Liping Chen |
| Abstract | As the number of vehicles continues to grow, parking spaces are at a premium in city streets. Additionally, due to the lack of knowledge about street parking spaces, heuristic circling the blocks not only costs drivers’ time and fuel, but also increases city congestion. In the wake of recent trend to build convenient, green and energy-efficient smart cities, we rethink common techniques adopted by high-profile smart parking systems, and present a user-engaged (crowdsourcing) and sonar-based prototype to identify urban on-street parking spaces. The prototype includes an ultrasonic sensor, a GPS receiver and associated Arduino micro-controllers. It is mounted on the passenger side of a car to measure the distance from the vehicle to the nearest roadside obstacle. Multiple road tests are conducted around Wheatley, Oxford to gather results and emulate the crowdsourcing approach. By extracting parked vehicles’ features from the collected trace, a supervised learning algorithm is developed to estimate roadside parking occupancy and spot illegal parking vehicles. A quantity estimation model is derived to calculate the required number of sensing units to cover urban streets. The estimation is quantitatively compared to a fixed sensing solution. The results show that the crowdsourcing way would need substantially fewer sensors compared to the fixed sensing system. |
| Tasks | |
| Published | 2016-03-01 |
| URL | http://arxiv.org/abs/1603.00441v1 |
| http://arxiv.org/pdf/1603.00441v1.pdf | |
| PWC | https://paperswithcode.com/paper/crowdsourcing-on-street-parking-space |
| Repo | |
| Framework | |
Memory Lens: How Much Memory Does an Agent Use?
| Title | Memory Lens: How Much Memory Does an Agent Use? |
| Authors | Christoph Dann, Katja Hofmann, Sebastian Nowozin |
| Abstract | We propose a new method to study the internal memory used by reinforcement learning policies. We estimate the amount of relevant past information by estimating mutual information between behavior histories and the current action of an agent. We perform this estimation in the passive setting, that is, we do not intervene but merely observe the natural behavior of the agent. Moreover, we provide a theoretical justification for our approach by showing that it yields an implementation-independent lower bound on the minimal memory capacity of any agent that implement the observed policy. We demonstrate our approach by estimating the use of memory of DQN policies on concatenated Atari frames, demonstrating sharply different use of memory across 49 games. The study of memory as information that flows from the past to the current action opens avenues to understand and improve successful reinforcement learning algorithms. |
| Tasks | |
| Published | 2016-11-21 |
| URL | http://arxiv.org/abs/1611.06928v1 |
| http://arxiv.org/pdf/1611.06928v1.pdf | |
| PWC | https://paperswithcode.com/paper/memory-lens-how-much-memory-does-an-agent-use |
| Repo | |
| Framework | |
Long-Term Identity-Aware Multi-Person Tracking for Surveillance Video Summarization
| Title | Long-Term Identity-Aware Multi-Person Tracking for Surveillance Video Summarization |
| Authors | Shoou-I Yu, Yi Yang, Xuanchong Li, Alexander G. Hauptmann |
| Abstract | Multi-person tracking plays a critical role in the analysis of surveillance video. However, most existing work focus on shorter-term (e.g. minute-long or hour-long) video sequences. Therefore, we propose a multi-person tracking algorithm for very long-term (e.g. month-long) multi-camera surveillance scenarios. Long-term tracking is challenging because 1) the apparel/appearance of the same person will vary greatly over multiple days and 2) a person will leave and re-enter the scene numerous times. To tackle these challenges, we leverage face recognition information, which is robust to apparel change, to automatically reinitialize our tracker over multiple days of recordings. Unfortunately, recognized faces are unavailable oftentimes. Therefore, our tracker propagates identity information to frames without recognized faces by uncovering the appearance and spatial manifold formed by person detections. We tested our algorithm on a 23-day 15-camera data set (4,935 hours total), and we were able to localize a person 53.2% of the time with 69.8% precision. We further performed video summarization experiments based on our tracking output. Results on 116.25 hours of video showed that we were able to generate a reasonable visual diary (i.e. a summary of what a person did) for different people, thus potentially opening the door to automatic summarization of the vast amount of surveillance video generated every day. |
| Tasks | Face Recognition, Video Summarization |
| Published | 2016-04-25 |
| URL | http://arxiv.org/abs/1604.07468v2 |
| http://arxiv.org/pdf/1604.07468v2.pdf | |
| PWC | https://paperswithcode.com/paper/long-term-identity-aware-multi-person |
| Repo | |
| Framework | |
Learning to Learn without Gradient Descent by Gradient Descent
| Title | Learning to Learn without Gradient Descent by Gradient Descent |
| Authors | Yutian Chen, Matthew W. Hoffman, Sergio Gomez Colmenarejo, Misha Denil, Timothy P. Lillicrap, Matt Botvinick, Nando de Freitas |
| Abstract | We learn recurrent neural network optimizers trained on simple synthetic functions by gradient descent. We show that these learned optimizers exhibit a remarkable degree of transfer in that they can be used to efficiently optimize a broad range of derivative-free black-box functions, including Gaussian process bandits, simple control objectives, global optimization benchmarks and hyper-parameter tuning tasks. Up to the training horizon, the learned optimizers learn to trade-off exploration and exploitation, and compare favourably with heavily engineered Bayesian optimization packages for hyper-parameter tuning. |
| Tasks | |
| Published | 2016-11-11 |
| URL | http://arxiv.org/abs/1611.03824v6 |
| http://arxiv.org/pdf/1611.03824v6.pdf | |
| PWC | https://paperswithcode.com/paper/learning-to-learn-without-gradient-descent-by |
| Repo | |
| Framework | |
Prototypical Recurrent Unit
| Title | Prototypical Recurrent Unit |
| Authors | Dingkun Long, Richong Zhang, Yongyi Mao |
| Abstract | Despite the great successes of deep learning, the effectiveness of deep neural networks has not been understood at any theoretical depth. This work is motivated by the thrust of developing a deeper understanding of recurrent neural networks, particularly LSTM/GRU-like networks. As the highly complex structure of the recurrent unit in LSTM and GRU networks makes them difficult to analyze, our methodology in this research theme is to construct an alternative recurrent unit that is as simple as possible and yet also captures the key components of LSTM/GRU recurrent units. Such a unit can then be used for the study of recurrent networks and its structural simplicity may allow easier analysis. Towards that goal, we take a system-theoretic perspective to design a new recurrent unit, which we call the prototypical recurrent unit (PRU). Not only having minimal complexity, PRU is demonstrated experimentally to have comparable performance to GRU and LSTM unit. This establishes PRU networks as a prototype for future study of LSTM/GRU-like recurrent networks. This paper also studies the memorization abilities of LSTM, GRU and PRU networks, motivated by the folk belief that such networks possess long-term memory. For this purpose, we design a simple and controllable task, called memorization problem'', where the networks are trained to memorize certain targeted information. We show that the memorization performance of all three networks depends on the amount of targeted information, the amount of interfering” information, and the state space dimension of the recurrent unit. Experiments are also performed for another controllable task, the adding problem, and similar conclusions are obtained. |
| Tasks | |
| Published | 2016-11-20 |
| URL | http://arxiv.org/abs/1611.06530v2 |
| http://arxiv.org/pdf/1611.06530v2.pdf | |
| PWC | https://paperswithcode.com/paper/prototypical-recurrent-unit |
| Repo | |
| Framework | |
Structure Learning in Graphical Modeling
| Title | Structure Learning in Graphical Modeling |
| Authors | Mathias Drton, Marloes H. Maathuis |
| Abstract | A graphical model is a statistical model that is associated to a graph whose nodes correspond to variables of interest. The edges of the graph reflect allowed conditional dependencies among the variables. Graphical models admit computationally convenient factorization properties and have long been a valuable tool for tractable modeling of multivariate distributions. More recently, applications such as reconstructing gene regulatory networks from gene expression data have driven major advances in structure learning, that is, estimating the graph underlying a model. We review some of these advances and discuss methods such as the graphical lasso and neighborhood selection for undirected graphical models (or Markov random fields), and the PC algorithm and score-based search methods for directed graphical models (or Bayesian networks). We further review extensions that account for effects of latent variables and heterogeneous data sources. |
| Tasks | |
| Published | 2016-06-07 |
| URL | http://arxiv.org/abs/1606.02359v1 |
| http://arxiv.org/pdf/1606.02359v1.pdf | |
| PWC | https://paperswithcode.com/paper/structure-learning-in-graphical-modeling |
| Repo | |
| Framework | |
The NOESIS Network-Oriented Exploration, Simulation, and Induction System
| Title | The NOESIS Network-Oriented Exploration, Simulation, and Induction System |
| Authors | Víctor Martínez, Fernando Berzal, Juan-Carlos Cubero |
| Abstract | Network data mining has become an important area of study due to the large number of problems it can be applied to. This paper presents NOESIS, an open source framework for network data mining that provides a large collection of network analysis techniques, including the analysis of network structural properties, community detection methods, link scoring, and link prediction, as well as network visualization algorithms. It also features a complete stand-alone graphical user interface that facilitates the use of all these techniques. The NOESIS framework has been designed using solid object-oriented design principles and structured parallel programming. As a lightweight library with minimal external dependencies and a permissive software license, NOESIS can be incorporated into other software projects. Released under a BSD license, it is available from http://noesis.ikor.org. |
| Tasks | Community Detection, Link Prediction |
| Published | 2016-11-15 |
| URL | http://arxiv.org/abs/1611.04810v2 |
| http://arxiv.org/pdf/1611.04810v2.pdf | |
| PWC | https://paperswithcode.com/paper/the-noesis-network-oriented-exploration |
| Repo | |
| Framework | |
Difference of Convex Functions Programming Applied to Control with Expert Data
| Title | Difference of Convex Functions Programming Applied to Control with Expert Data |
| Authors | Bilal Piot, Matthieu Geist, Olivier Pietquin |
| Abstract | This paper reports applications of Difference of Convex functions (DC) programming to Learning from Demonstrations (LfD) and Reinforcement Learning (RL) with expert data. This is made possible because the norm of the Optimal Bellman Residual (OBR), which is at the heart of many RL and LfD algorithms, is DC. Improvement in performance is demonstrated on two specific algorithms, namely Reward-regularized Classification for Apprenticeship Learning (RCAL) and Reinforcement Learning with Expert Demonstrations (RLED), through experiments on generic Markov Decision Processes (MDP), called Garnets. |
| Tasks | |
| Published | 2016-06-03 |
| URL | http://arxiv.org/abs/1606.01128v2 |
| http://arxiv.org/pdf/1606.01128v2.pdf | |
| PWC | https://paperswithcode.com/paper/difference-of-convex-functions-programming |
| Repo | |
| Framework | |
Discriminative Regularization for Generative Models
| Title | Discriminative Regularization for Generative Models |
| Authors | Alex Lamb, Vincent Dumoulin, Aaron Courville |
| Abstract | We explore the question of whether the representations learned by classifiers can be used to enhance the quality of generative models. Our conjecture is that labels correspond to characteristics of natural data which are most salient to humans: identity in faces, objects in images, and utterances in speech. We propose to take advantage of this by using the representations from discriminative classifiers to augment the objective function corresponding to a generative model. In particular we enhance the objective function of the variational autoencoder, a popular generative model, with a discriminative regularization term. We show that enhancing the objective function in this way leads to samples that are clearer and have higher visual quality than the samples from the standard variational autoencoders. |
| Tasks | |
| Published | 2016-02-09 |
| URL | http://arxiv.org/abs/1602.03220v4 |
| http://arxiv.org/pdf/1602.03220v4.pdf | |
| PWC | https://paperswithcode.com/paper/discriminative-regularization-for-generative |
| Repo | |
| Framework | |
