May 7, 2019

2640 words 13 mins read

Paper Group AWR 74

A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems. Deep Reinforcement Learning from Self-Play in Imperfect-Information Games. Feature Importance Measure for Non-linear Learning Algorithms. Learning to Act by Predicting the Future. On a Topic Model for Sentences. Segmentation from Natural Language Expressions. Gradients …

A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems


Title	A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems
Authors	Paul Swoboda, Jan Kuske, Bogdan Savchynskyy
Abstract	We propose a general dual ascent framework for Lagrangean decomposition of combinatorial problems. Although methods of this type have shown their efficiency for a number of problems, so far there was no general algorithm applicable to multiple problem types. In his work, we propose such a general algorithm. It depends on several parameters, which can be used to optimize its performance in each particular setting. We demonstrate efficacy of our method on graph matching and multicut problems, where it outperforms state-of-the-art solvers including those based on subgradient optimization and off-the-shelf linear programming solvers.
Tasks	Graph Matching
Published	2016-12-16
URL	http://arxiv.org/abs/1612.05460v2
PDF	http://arxiv.org/pdf/1612.05460v2.pdf
PWC	https://paperswithcode.com/paper/a-dual-ascent-framework-for-lagrangean
Repo	https://github.com/pawelswoboda/LP_MP
Framework	none

Deep Reinforcement Learning from Self-Play in Imperfect-Information Games


Title	Deep Reinforcement Learning from Self-Play in Imperfect-Information Games
Authors	Johannes Heinrich, David Silver
Abstract	Many real-world applications can be described as large-scale games of imperfect information. To deal with these challenging domains, prior work has focused on computing Nash equilibria in a handcrafted abstraction of the domain. In this paper we introduce the first scalable end-to-end approach to learning approximate Nash equilibria without prior domain knowledge. Our method combines fictitious self-play with deep reinforcement learning. When applied to Leduc poker, Neural Fictitious Self-Play (NFSP) approached a Nash equilibrium, whereas common reinforcement learning methods diverged. In Limit Texas Holdem, a poker game of real-world scale, NFSP learnt a strategy that approached the performance of state-of-the-art, superhuman algorithms based on significant domain expertise.
Tasks	Card Games, Game of Poker
Published	2016-03-03
URL	http://arxiv.org/abs/1603.01121v2
PDF	http://arxiv.org/pdf/1603.01121v2.pdf
PWC	https://paperswithcode.com/paper/deep-reinforcement-learning-from-self-play-in
Repo	https://github.com/IAARhub/TrucoAnalytics
Framework	none

Feature Importance Measure for Non-linear Learning Algorithms


Title	Feature Importance Measure for Non-linear Learning Algorithms
Authors	Marina M. -C. Vidovic, Nico Görnitz, Klaus-Robert Müller, Marius Kloft
Abstract	Complex problems may require sophisticated, non-linear learning methods such as kernel machines or deep neural networks to achieve state of the art prediction accuracies. However, high prediction accuracies are not the only objective to consider when solving problems using machine learning. Instead, particular scientific applications require some explanation of the learned prediction function. Unfortunately, most methods do not come with out of the box straight forward interpretation. Even linear prediction functions are not straight forward to explain if features exhibit complex correlation structure. In this paper, we propose the Measure of Feature Importance (MFI). MFI is general and can be applied to any arbitrary learning machine (including kernel machines and deep learning). MFI is intrinsically non-linear and can detect features that by itself are inconspicuous and only impact the prediction function through their interaction with other features. Lastly, MFI can be used for both — model-based feature importance and instance-based feature importance (i.e, measuring the importance of a feature for a particular data point).
Tasks	Feature Importance
Published	2016-11-22
URL	http://arxiv.org/abs/1611.07567v1
PDF	http://arxiv.org/pdf/1611.07567v1.pdf
PWC	https://paperswithcode.com/paper/feature-importance-measure-for-non-linear
Repo	https://github.com/mcvidomi/MFI
Framework	none

Learning to Act by Predicting the Future


Title	Learning to Act by Predicting the Future
Authors	Alexey Dosovitskiy, Vladlen Koltun
Abstract	We present an approach to sensorimotor control in immersive environments. Our approach utilizes a high-dimensional sensory stream and a lower-dimensional measurement stream. The cotemporal structure of these streams provides a rich supervisory signal, which enables training a sensorimotor control model by interacting with the environment. The model is trained using supervised learning techniques, but without extraneous supervision. It learns to act based on raw sensory input from a complex three-dimensional environment. The presented formulation enables learning without a fixed goal at training time, and pursuing dynamically changing goals at test time. We conduct extensive experiments in three-dimensional simulations based on the classical first-person game Doom. The results demonstrate that the presented approach outperforms sophisticated prior formulations, particularly on challenging tasks. The results also show that trained models successfully generalize across environments and goals. A model trained using the presented approach won the Full Deathmatch track of the Visual Doom AI Competition, which was held in previously unseen environments.
Tasks
Published	2016-11-06
URL	http://arxiv.org/abs/1611.01779v2
PDF	http://arxiv.org/pdf/1611.01779v2.pdf
PWC	https://paperswithcode.com/paper/learning-to-act-by-predicting-the-future
Repo	https://github.com/a-mcego/DirectFuturePred_tf2
Framework	tf

On a Topic Model for Sentences


Title	On a Topic Model for Sentences
Authors	Georgios Balikas, Massih-Reza Amini, Marianne Clausel
Abstract	Probabilistic topic models are generative models that describe the content of documents by discovering the latent topics underlying them. However, the structure of the textual input, and for instance the grouping of words in coherent text spans such as sentences, contains much information which is generally lost with these models. In this paper, we propose sentenceLDA, an extension of LDA whose goal is to overcome this limitation by incorporating the structure of the text in the generative and inference processes. We illustrate the advantages of sentenceLDA by comparing it with LDA using both intrinsic (perplexity) and extrinsic (text classification) evaluation tasks on different text collections.
Tasks	Text Classification, Topic Models
Published	2016-06-01
URL	http://arxiv.org/abs/1606.00253v1
PDF	http://arxiv.org/pdf/1606.00253v1.pdf
PWC	https://paperswithcode.com/paper/on-a-topic-model-for-sentences
Repo	https://github.com/balikasg/topicModelling
Framework	none

Segmentation from Natural Language Expressions


Title	Segmentation from Natural Language Expressions
Authors	Ronghang Hu, Marcus Rohrbach, Trevor Darrell
Abstract	In this paper we approach the novel problem of segmenting an image based on a natural language expression. This is different from traditional semantic segmentation over a predefined set of semantic classes, as e.g., the phrase “two men sitting on the right bench” requires segmenting only the two people on the right bench and no one standing or sitting on another bench. Previous approaches suitable for this task were limited to a fixed set of categories and/or rectangular regions. To produce pixelwise segmentation for the language expression, we propose an end-to-end trainable recurrent and convolutional network model that jointly learns to process visual and linguistic information. In our model, a recurrent LSTM network is used to encode the referential expression into a vector representation, and a fully convolutional network is used to a extract a spatial feature map from the image and output a spatial response map for the target object. We demonstrate on a benchmark dataset that our model can produce quality segmentation output from the natural language expression, and outperforms baseline methods by a large margin.
Tasks	Semantic Segmentation
Published	2016-03-20
URL	http://arxiv.org/abs/1603.06180v1
PDF	http://arxiv.org/pdf/1603.06180v1.pdf
PWC	https://paperswithcode.com/paper/segmentation-from-natural-language
Repo	https://github.com/ssharpe42/VNLQAC
Framework	tf

Gradients of Counterfactuals


Title	Gradients of Counterfactuals
Authors	Mukund Sundararajan, Ankur Taly, Qiqi Yan
Abstract	Gradients have been used to quantify feature importance in machine learning models. Unfortunately, in nonlinear deep networks, not only individual neurons but also the whole network can saturate, and as a result an important input feature can have a tiny gradient. We study various networks, and observe that this phenomena is indeed widespread, across many inputs. We propose to examine interior gradients, which are gradients of counterfactual inputs constructed by scaling down the original input. We apply our method to the GoogleNet architecture for object recognition in images, as well as a ligand-based virtual screening network with categorical features and an LSTM based language model for the Penn Treebank dataset. We visualize how interior gradients better capture feature importance. Furthermore, interior gradients are applicable to a wide variety of deep networks, and have the attribution property that the feature importance scores sum to the the prediction score. Best of all, interior gradients can be computed just as easily as gradients. In contrast, previous methods are complex to implement, which hinders practical adoption.
Tasks	Feature Importance, Language Modelling, Object Recognition
Published	2016-11-08
URL	http://arxiv.org/abs/1611.02639v2
PDF	http://arxiv.org/pdf/1611.02639v2.pdf
PWC	https://paperswithcode.com/paper/gradients-of-counterfactuals
Repo	https://github.com/kundajelab/deeplift
Framework	tf

Sequential Neural Models with Stochastic Layers


Title	Sequential Neural Models with Stochastic Layers
Authors	Marco Fraccaro, Søren Kaae Sønderby, Ulrich Paquet, Ole Winther
Abstract	How can we efficiently propagate uncertainty in a latent state representation with recurrent neural networks? This paper introduces stochastic recurrent neural networks which glue a deterministic recurrent neural network and a state space model together to form a stochastic and sequential neural generative model. The clear separation of deterministic and stochastic layers allows a structured variational inference network to track the factorization of the model’s posterior distribution. By retaining both the nonlinear recursive structure of a recurrent neural network and averaging over the uncertainty in a latent path, like a state space model, we improve the state of the art results on the Blizzard and TIMIT speech modeling data sets by a large margin, while achieving comparable performances to competing methods on polyphonic music modeling.
Tasks	Music Modeling
Published	2016-05-24
URL	http://arxiv.org/abs/1605.07571v2
PDF	http://arxiv.org/pdf/1605.07571v2.pdf
PWC	https://paperswithcode.com/paper/sequential-neural-models-with-stochastic
Repo	https://github.com/marcofraccaro/srnn
Framework	none

SGDR: Stochastic Gradient Descent with Warm Restarts


Title	SGDR: Stochastic Gradient Descent with Warm Restarts
Authors	Ilya Loshchilov, Frank Hutter
Abstract	Restart techniques are common in gradient-free optimization to deal with multimodal functions. Partial warm restarts are also gaining popularity in gradient-based optimization to improve the rate of convergence in accelerated gradient schemes to deal with ill-conditioned functions. In this paper, we propose a simple warm restart technique for stochastic gradient descent to improve its anytime performance when training deep neural networks. We empirically study its performance on the CIFAR-10 and CIFAR-100 datasets, where we demonstrate new state-of-the-art results at 3.14% and 16.21%, respectively. We also demonstrate its advantages on a dataset of EEG recordings and on a downsampled version of the ImageNet dataset. Our source code is available at https://github.com/loshchil/SGDR
Tasks	EEG, Stochastic Optimization
Published	2016-08-13
URL	http://arxiv.org/abs/1608.03983v5
PDF	http://arxiv.org/pdf/1608.03983v5.pdf
PWC	https://paperswithcode.com/paper/sgdr-stochastic-gradient-descent-with-warm
Repo	https://github.com/Harshvardhan1/cyclic-learning-schedulers-pytorch
Framework	pytorch

Fifty Shades of Ratings: How to Benefit from a Negative Feedback in Top-N Recommendations Tasks


Title	Fifty Shades of Ratings: How to Benefit from a Negative Feedback in Top-N Recommendations Tasks
Authors	Evgeny Frolov, Ivan Oseledets
Abstract	Conventional collaborative filtering techniques treat a top-n recommendations problem as a task of generating a list of the most relevant items. This formulation, however, disregards an opposite - avoiding recommendations with completely irrelevant items. Due to that bias, standard algorithms, as well as commonly used evaluation metrics, become insensitive to negative feedback. In order to resolve this problem we propose to treat user feedback as a categorical variable and model it with users and items in a ternary way. We employ a third-order tensor factorization technique and implement a higher order folding-in method to support online recommendations. The method is equally sensitive to entire spectrum of user ratings and is able to accurately predict relevant items even from a negative only feedback. Our method may partially eliminate the need for complicated rating elicitation process as it provides means for personalized recommendations from the very beginning of an interaction with a recommender system. We also propose a modification of standard metrics which helps to reveal unwanted biases and account for sensitivity to a negative feedback. Our model achieves state-of-the-art quality in standard recommendation tasks while significantly outperforming other methods in the cold-start “no-positive-feedback” scenarios.
Tasks	Recommendation Systems
Published	2016-07-14
URL	http://arxiv.org/abs/1607.04228v1
PDF	http://arxiv.org/pdf/1607.04228v1.pdf
PWC	https://paperswithcode.com/paper/fifty-shades-of-ratings-how-to-benefit-from-a
Repo	https://github.com/Evfro/fifty-shades
Framework	none

Semi-Supervised Learning with Generative Adversarial Networks


Title	Semi-Supervised Learning with Generative Adversarial Networks
Authors	Augustus Odena
Abstract	We extend Generative Adversarial Networks (GANs) to the semi-supervised context by forcing the discriminator network to output class labels. We train a generative model G and a discriminator D on a dataset with inputs belonging to one of N classes. At training time, D is made to predict which of N+1 classes the input belongs to, where an extra class is added to correspond to the outputs of G. We show that this method can be used to create a more data-efficient classifier and that it allows for generating higher quality samples than a regular GAN.
Tasks
Published	2016-06-05
URL	http://arxiv.org/abs/1606.01583v2
PDF	http://arxiv.org/pdf/1606.01583v2.pdf
PWC	https://paperswithcode.com/paper/semi-supervised-learning-with-generative
Repo	https://github.com/eriklindernoren/PyTorch-GAN
Framework	pytorch

Learning Language Games through Interaction


Title	Learning Language Games through Interaction
Authors	Sida I. Wang, Percy Liang, Christopher D. Manning
Abstract	We introduce a new language learning setting relevant to building adaptive natural language interfaces. It is inspired by Wittgenstein’s language games: a human wishes to accomplish some task (e.g., achieving a certain configuration of blocks), but can only communicate with a computer, who performs the actual actions (e.g., removing all red blocks). The computer initially knows nothing about language and therefore must learn it from scratch through interaction, while the human adapts to the computer’s capabilities. We created a game in a blocks world and collected interactions from 100 people playing it. First, we analyze the humans’ strategies, showing that using compositionality and avoiding synonyms correlates positively with task performance. Second, we compare computer strategies, showing how to quickly learn a semantic parsing model from scratch, and that modeling pragmatics further accelerates learning for successful players.
Tasks	Semantic Parsing
Published	2016-06-08
URL	http://arxiv.org/abs/1606.02447v1
PDF	http://arxiv.org/pdf/1606.02447v1.pdf
PWC	https://paperswithcode.com/paper/learning-language-games-through-interaction
Repo	https://github.com/sidaw/shrdlurn
Framework	none

Improving Hypernymy Detection with an Integrated Path-based and Distributional Method


Title	Improving Hypernymy Detection with an Integrated Path-based and Distributional Method
Authors	Vered Shwartz, Yoav Goldberg, Ido Dagan
Abstract	Detecting hypernymy relations is a key task in NLP, which is addressed in the literature using two complementary approaches. Distributional methods, whose supervised variants are the current best performers, and path-based methods, which received less research attention. We suggest an improved path-based algorithm, in which the dependency paths are encoded using a recurrent neural network, that achieves results comparable to distributional methods. We then extend the approach to integrate both path-based and distributional signals, significantly improving upon the state-of-the-art on this task.
Tasks
Published	2016-03-19
URL	http://arxiv.org/abs/1603.06076v3
PDF	http://arxiv.org/pdf/1603.06076v3.pdf
PWC	https://paperswithcode.com/paper/improving-hypernymy-detection-with-an
Repo	https://github.com/vered1986/HypeNET
Framework	none

A hybrid approach to supervised machine learning for algorithmic melody composition


Title	A hybrid approach to supervised machine learning for algorithmic melody composition
Authors	Rouven Bauer
Abstract	In this work we present an algorithm for composing monophonic melodies similar in style to those of a given, phrase annotated, sample of melodies. For implementation, a hybrid approach incorporating parametric Markov models of higher order and a contour concept of phrases is used. This work is based on the master thesis of Thayabaran Kathiresan (2015). An online listening test conducted shows that enhancing a pure Markov model with musically relevant context, like count and planed melody contour, improves the result significantly.
Tasks
Published	2016-12-29
URL	http://arxiv.org/abs/1612.09212v1
PDF	http://arxiv.org/pdf/1612.09212v1.pdf
PWC	https://paperswithcode.com/paper/a-hybrid-approach-to-supervised-machine
Repo	https://github.com/roba91/melody-composer
Framework	none

Multi-view Self-supervised Deep Learning for 6D Pose Estimation in the Amazon Picking Challenge


Title	Multi-view Self-supervised Deep Learning for 6D Pose Estimation in the Amazon Picking Challenge
Authors	Andy Zeng, Kuan-Ting Yu, Shuran Song, Daniel Suo, Ed Walker Jr., Alberto Rodriguez, Jianxiong Xiao
Abstract	Robot warehouse automation has attracted significant interest in recent years, perhaps most visibly in the Amazon Picking Challenge (APC). A fully autonomous warehouse pick-and-place system requires robust vision that reliably recognizes and locates objects amid cluttered environments, self-occlusions, sensor noise, and a large variety of objects. In this paper we present an approach that leverages multi-view RGB-D data and self-supervised, data-driven learning to overcome those difficulties. The approach was part of the MIT-Princeton Team system that took 3rd- and 4th- place in the stowing and picking tasks, respectively at APC 2016. In the proposed approach, we segment and label multiple views of a scene with a fully convolutional neural network, and then fit pre-scanned 3D object models to the resulting segmentation to get the 6D object pose. Training a deep neural network for segmentation typically requires a large amount of training data. We propose a self-supervised method to generate a large labeled dataset without tedious manual segmentation. We demonstrate that our system can reliably estimate the 6D pose of objects under a variety of scenarios. All code, data, and benchmarks are available at http://apc.cs.princeton.edu/
Tasks	6D Pose Estimation, 6D Pose Estimation using RGBD, Pose Estimation
Published	2016-09-29
URL	http://arxiv.org/abs/1609.09475v3
PDF	http://arxiv.org/pdf/1609.09475v3.pdf
PWC	https://paperswithcode.com/paper/multi-view-self-supervised-deep-learning-for
Repo	https://github.com/andyzeng/apc-vision-toolbox
Framework	none