Rich experimental evidences show that one can better estimate users’ unknown ratings with the aid of graph side information such as social graphs. However, the gain is not theoretically quantified. In this work, we study the binary rating estimation problem to understand the fundamental value of graph side information. Considering a simple correlation model between a rating matrix and a graph, we characterize the sharp threshold on the number of observed entries required to recover the rating matrix (called the optimal sample complexity) as a function of the quality of graph side information (to be detailed). To the best of our knowledge, we are the first to reveal how much the graph side information reduces sample complexity. Further, we propose a computationally efficient algorithm that achieves the limit. Our experimental results demonstrate that the algorithm performs well even with real-world graphs.
안광준 (KATUSA), 이강욱(KAIST), 차현승 (카카오브레인), 서창호 (KAIST)
Recommender Systems, Information Theory
In this paper, we propose a novel maximum causal Tsallis entropy (MCTE) framework for imitation learning which can efficiently learn a sparse multi-modal policy distribution from demonstrations. We provide the full mathematical analysis of the proposed framework. First, the optimal solution of an MCTE problem is shown to be a sparsemax distribution, whose supporting set can be adjusted. The proposed method has advantages over a softmax distribution in that it can exclude unnecessary actions by assigning zero probability. Second, we prove that an MCTE problem is equivalent to robust Bayes estimation in the sense of the Brier score. Third, we propose a maximum causal Tsallis entropy imitation learning (MCTEIL) algorithm with a sparse mixture density network (sparse MDN) by modeling mixture weights using a sparse max distribution. In particular, we show that the causal Tsallis entropy of an MDN encourages exploration and efficient mixture utilization while Boltzmann Gibbs entropy is less effective. We validate the proposed method in two simulation studies and MCTEIL outperforms existing imitation learning methods in terms of average returns and learning multi-modal policies.
이경재 (서울대학교), 최성준 (카카오브레인/디즈니), 오송회 (서울대학교)
RL, Core ML/DL
Due to the inherent model uncertainty, learning to infer Bayesian posterior from a few-shot dataset is an important step towards robust meta-learning. In this paper, we propose a novel Bayesian model-agnostic meta-learning method. The proposed method combines efficient gradient-based meta-learning with nonparametric variational inference in a principled probabilistic framework. Unlike previous methods, during fast adaptation, the method is capable of learning complex uncertainty structure beyond a simple Gaussian approximation, and during meta-update, a novel Bayesian mechanism prevents meta-level overfitting. Remaining a gradient- based method, it is also the first Bayesian model-agnostic meta-learning method applicable to various tasks including reinforcement learning. Experiment results show the accuracy and robustness of the proposed method in sinusoidal regression, image classification, active learning, and reinforcement learning.
김태섭 (MILA), 윤재식 (SAP Korea), 김성웅 (카카오브레인), 안성진 (ElementAI)
Learning complex spatiotemporal patterns is a key to predict future taxi demand volumes. We propose temporal guided networks (TGNet), which is an efficient model architecture with fully convolutional networks and temporal guided embedding, to capture spatiotemporal patterns. Existing approaches use complex architectures, historical demands (day/week/month ago) to capture the recurring patterns, and external data sources such as meteorological, traffic flow, or texture data. However, TGNet only uses fully convolutional networks and temporal guided embedding without those external data sources. In this study, only pick-up and drop-off volumes of NYC-taxi dataset are used to utilize the full potential of the hidden patterns in the historical data points. We show that TGNet provides notable performance gains on a real-world benchmark, NYC-taxi dataset, over previous state-of-the-art models. Finally we explain how to extend our architecture to incorporate external data sources.
NIPS Workshop Presentation
이도엽, 정수헌, 천영재 (카카오브레인), 유승일, 김동일 (카카오모빌리티)
traffic modeling, forecasting, taxi demand, spatiotemporal modeling