May 5, 2019

3298 words 16 mins read

Paper Group ANR 563

Convolutional Random Walk Networks for Semantic Image Segmentation. Sub-Sampled Newton Methods I: Globally Convergent Algorithms. Informative Planning and Online Learning with Sparse Gaussian Processes. Leaving Some Stones Unturned: Dynamic Feature Prioritization for Activity Detection in Streaming Video. Context-Aware Online Learning for Course Re …

Convolutional Random Walk Networks for Semantic Image Segmentation


Title	Convolutional Random Walk Networks for Semantic Image Segmentation
Authors	Gedas Bertasius, Lorenzo Torresani, Stella X. Yu, Jianbo Shi
Abstract	Most current semantic segmentation methods rely on fully convolutional networks (FCNs). However, their use of large receptive fields and many pooling layers cause low spatial resolution inside the deep layers. This leads to predictions with poor localization around the boundaries. Prior work has attempted to address this issue by post-processing predictions with CRFs or MRFs. But such models often fail to capture semantic relationships between objects, which causes spatially disjoint predictions. To overcome these problems, recent methods integrated CRFs or MRFs into an FCN framework. The downside of these new models is that they have much higher complexity than traditional FCNs, which renders training and testing more challenging. In this work we introduce a simple, yet effective Convolutional Random Walk Network (RWN) that addresses the issues of poor boundary localization and spatially fragmented predictions with very little increase in model complexity. Our proposed RWN jointly optimizes the objectives of pixelwise affinity and semantic segmentation. It combines these two objectives via a novel random walk layer that enforces consistent spatial grouping in the deep layers of the network. Our RWN is implemented using standard convolution and matrix multiplication. This allows an easy integration into existing FCN frameworks and it enables end-to-end training of the whole network via standard back-propagation. Our implementation of RWN requires just $131$ additional parameters compared to the traditional FCNs, and yet it consistently produces an improvement over the FCNs on semantic segmentation and scene labeling.
Tasks	Scene Labeling, Semantic Segmentation
Published	2016-05-24
URL	http://arxiv.org/abs/1605.07681v3
PDF	http://arxiv.org/pdf/1605.07681v3.pdf
PWC	https://paperswithcode.com/paper/convolutional-random-walk-networks-for
Repo
Framework

Sub-Sampled Newton Methods I: Globally Convergent Algorithms


Title	Sub-Sampled Newton Methods I: Globally Convergent Algorithms
Authors	Farbod Roosta-Khorasani, Michael W. Mahoney
Abstract	Large scale optimization problems are ubiquitous in machine learning and data analysis and there is a plethora of algorithms for solving such problems. Many of these algorithms employ sub-sampling, as a way to either speed up the computations and/or to implicitly implement a form of statistical regularization. In this paper, we consider second-order iterative optimization algorithms and we provide bounds on the convergence of the variants of Newton’s method that incorporate uniform sub-sampling as a means to estimate the gradient and/or Hessian. Our bounds are non-asymptotic and quantitative. Our algorithms are global and are guaranteed to converge from any initial iterate. Using random matrix concentration inequalities, one can sub-sample the Hessian to preserve the curvature information. Our first algorithm incorporates Hessian sub-sampling while using the full gradient. We also give additional convergence results for when the sub-sampled Hessian is regularized by modifying its spectrum or ridge-type regularization. Next, in addition to Hessian sub-sampling, we also consider sub-sampling the gradient as a way to further reduce the computational complexity per iteration. We use approximate matrix multiplication results from randomized numerical linear algebra to obtain the proper sampling strategy. In all these algorithms, computing the update boils down to solving a large scale linear system, which can be computationally expensive. As a remedy, for all of our algorithms, we also give global convergence results for the case of inexact updates where such linear system is solved only approximately. This paper has a more advanced companion paper, [42], in which we demonstrate that, by doing a finer-grained analysis, we can get problem-independent bounds for local convergence of these algorithms and explore trade-offs to improve upon the basic results of the present paper.
Tasks
Published	2016-01-18
URL	http://arxiv.org/abs/1601.04737v3
PDF	http://arxiv.org/pdf/1601.04737v3.pdf
PWC	https://paperswithcode.com/paper/sub-sampled-newton-methods-i-globally
Repo
Framework

Informative Planning and Online Learning with Sparse Gaussian Processes


Title	Informative Planning and Online Learning with Sparse Gaussian Processes
Authors	Kai-Chieh Ma, Lantao Liu, Gaurav S. Sukhatme
Abstract	A big challenge in environmental monitoring is the spatiotemporal variation of the phenomena to be observed. To enable persistent sensing and estimation in such a setting, it is beneficial to have a time-varying underlying environmental model. Here we present a planning and learning method that enables an autonomous marine vehicle to perform persistent ocean monitoring tasks by learning and refining an environmental model. To alleviate the computational bottleneck caused by large-scale data accumulated, we propose a framework that iterates between a planning component aimed at collecting the most information-rich data, and a sparse Gaussian Process learning component where the environmental model and hyperparameters are learned online by taking advantage of only a subset of data that provides the greatest contribution. Our simulations with ground-truth ocean data shows that the proposed method is both accurate and efficient.
Tasks	Gaussian Processes
Published	2016-09-24
URL	http://arxiv.org/abs/1609.07560v1
PDF	http://arxiv.org/pdf/1609.07560v1.pdf
PWC	https://paperswithcode.com/paper/informative-planning-and-online-learning-with
Repo
Framework

Leaving Some Stones Unturned: Dynamic Feature Prioritization for Activity Detection in Streaming Video


Title	Leaving Some Stones Unturned: Dynamic Feature Prioritization for Activity Detection in Streaming Video
Authors	Yu-Chuan Su, Kristen Grauman
Abstract	Current approaches for activity recognition often ignore constraints on computational resources: 1) they rely on extensive feature computation to obtain rich descriptors on all frames, and 2) they assume batch-mode access to the entire test video at once. We propose a new active approach to activity recognition that prioritizes “what to compute when” in order to make timely predictions. The main idea is to learn a policy that dynamically schedules the sequence of features to compute on selected frames of a given test video. In contrast to traditional static feature selection, our approach continually re-prioritizes computation based on the accumulated history of observations and accounts for the transience of those observations in ongoing video. We develop variants to handle both the batch and streaming settings. On two challenging datasets, our method provides significantly better accuracy than alternative techniques for a wide range of computational budgets.
Tasks	Action Detection, Activity Detection, Activity Recognition, Feature Selection
Published	2016-04-01
URL	http://arxiv.org/abs/1604.00427v1
PDF	http://arxiv.org/pdf/1604.00427v1.pdf
PWC	https://paperswithcode.com/paper/leaving-some-stones-unturned-dynamic-feature
Repo
Framework

Context-Aware Online Learning for Course Recommendation of MOOC Big Data


Title	Context-Aware Online Learning for Course Recommendation of MOOC Big Data
Authors	Yifan Hou, Pan Zhou, Ting Wang, Li Yu, Yuchong Hu, Dapeng Wu
Abstract	The Massive Open Online Course (MOOC) has expanded significantly in recent years. With the widespread of MOOC, the opportunity to study the fascinating courses for free has attracted numerous people of diverse educational backgrounds all over the world. In the big data era, a key research topic for MOOC is how to mine the needed courses in the massive course databases in cloud for each individual student accurately and rapidly as the number of courses is increasing fleetly. In this respect, the key challenge is how to realize personalized course recommendation as well as to reduce the computing and storage costs for the tremendous course data. In this paper, we propose a big data-supported, context-aware online learning-based course recommender system that could handle the dynamic and infinitely massive datasets, which recommends courses by using personalized context information and historical statistics. The context-awareness takes the personal preferences into consideration, making the recommendation suitable for people with different backgrounds. Besides, the algorithm achieves the sublinear regret performance, which means it can gradually recommend the mostly preferred and matched courses to students. In addition, our storage module is expanded to the distributed-connected storage nodes, where the devised algorithm can handle massive course storage problems from heterogeneous sources of course datasets. Comparing to existing algorithms, our proposed algorithms achieve the linear time complexity and space complexity. Experiment results verify the superiority of our algorithms when comparing with existing ones in the MOOC big data setting.
Tasks	Recommendation Systems
Published	2016-10-11
URL	http://arxiv.org/abs/1610.03147v2
PDF	http://arxiv.org/pdf/1610.03147v2.pdf
PWC	https://paperswithcode.com/paper/context-aware-online-learning-for-course
Repo
Framework

Reinforcement Learning Approach for Parallelization in Filters Aggregation Based Feature Selection Algorithms


Title	Reinforcement Learning Approach for Parallelization in Filters Aggregation Based Feature Selection Algorithms
Authors	Ivan Smetannikov, Ilya Isaev, Andrey Filchenkov
Abstract	One of the classical problems in machine learning and data mining is feature selection. A feature selection algorithm is expected to be quick, and at the same time it should show high performance. MeLiF algorithm effectively solves this problem using ensembles of ranking filters. This article describes two different ways to improve MeLiF algorithm performance with parallelization. Experiments show that proposed schemes significantly improves algorithm performance and increase feature selection quality.
Tasks	Feature Selection
Published	2016-11-07
URL	http://arxiv.org/abs/1611.02047v1
PDF	http://arxiv.org/pdf/1611.02047v1.pdf
PWC	https://paperswithcode.com/paper/reinforcement-learning-approach-for
Repo
Framework

Web-based Semantic Similarity for Emotion Recognition in Web Objects


Title	Web-based Semantic Similarity for Emotion Recognition in Web Objects
Authors	Valentina Franzoni, Giulio Biondi, Alfredo Milani, Yuanxi Li
Abstract	In this project we propose a new approach for emotion recognition using web-based similarity (e.g. confidence, PMI and PMING). We aim to extract basic emotions from short sentences with emotional content (e.g. news titles, tweets, captions), performing a web-based quantitative evaluation of semantic proximity between each word of the analyzed sentence and each emotion of a psychological model (e.g. Plutchik, Ekman, Lovheim). The phases of the extraction include: text preprocessing (tokenization, stop words, filtering), search engine automated query, HTML parsing of results (i.e. scraping), estimation of semantic proximity, ranking of emotions according to proximity measures. The main idea is that, since it is possible to generalize semantic similarity under the assumption that similar concepts co-occur in documents indexed in search engines, therefore also emotions can be generalized in the same way, through tags or terms that express them in a particular language, ranking emotions. Training results are compared to human evaluation, then additional comparative tests on results are performed, both for the global ranking correlation (e.g. Kendall, Spearman, Pearson) both for the evaluation of the emotion linked to each single word. Different from sentiment analysis, our approach works at a deeper level of abstraction, aiming at recognizing specific emotions and not only the positive/negative sentiment, in order to predict emotions as semantic data.
Tasks	Emotion Recognition, Semantic Similarity, Semantic Textual Similarity, Sentiment Analysis, Tokenization
Published	2016-12-17
URL	http://arxiv.org/abs/1612.05734v1
PDF	http://arxiv.org/pdf/1612.05734v1.pdf
PWC	https://paperswithcode.com/paper/web-based-semantic-similarity-for-emotion
Repo
Framework

Unsupervised Learning of 3D Structure from Images


Title	Unsupervised Learning of 3D Structure from Images
Authors	Danilo Jimenez Rezende, S. M. Ali Eslami, Shakir Mohamed, Peter Battaglia, Max Jaderberg, Nicolas Heess
Abstract	A key goal of computer vision is to recover the underlying 3D structure from 2D observations of the world. In this paper we learn strong deep generative models of 3D structures, and recover these structures from 3D and 2D images via probabilistic inference. We demonstrate high-quality samples and report log-likelihoods on several datasets, including ShapeNet [2], and establish the first benchmarks in the literature. We also show how these models and their inference networks can be trained end-to-end from 2D images. This demonstrates for the first time the feasibility of learning to infer 3D representations of the world in a purely unsupervised manner.
Tasks
Published	2016-07-03
URL	http://arxiv.org/abs/1607.00662v2
PDF	http://arxiv.org/pdf/1607.00662v2.pdf
PWC	https://paperswithcode.com/paper/unsupervised-learning-of-3d-structure-from
Repo
Framework

Face valuing: Training user interfaces with facial expressions and reinforcement learning


Title	Face valuing: Training user interfaces with facial expressions and reinforcement learning
Authors	Vivek Veeriah, Patrick M. Pilarski, Richard S. Sutton
Abstract	An important application of interactive machine learning is extending or amplifying the cognitive and physical capabilities of a human. To accomplish this, machines need to learn about their human users’ intentions and adapt to their preferences. In most current research, a user has conveyed preferences to a machine using explicit corrective or instructive feedback; explicit feedback imposes a cognitive load on the user and is expensive in terms of human effort. The primary objective of the current work is to demonstrate that a learning agent can reduce the amount of explicit feedback required for adapting to the user’s preferences pertaining to a task by learning to perceive a value of its behavior from the human user, particularly from the user’s facial expressions—we call this face valuing. We empirically evaluate face valuing on a grip selection task. Our preliminary results suggest that an agent can quickly adapt to a user’s changing preferences with minimal explicit feedback by learning a value function that maps facial features extracted from a camera image to expected future reward. We believe that an agent learning to perceive a value from the body language of its human user is complementary to existing interactive machine learning approaches and will help in creating successful human-machine interactive applications.
Tasks
Published	2016-06-09
URL	http://arxiv.org/abs/1606.02807v1
PDF	http://arxiv.org/pdf/1606.02807v1.pdf
PWC	https://paperswithcode.com/paper/face-valuing-training-user-interfaces-with
Repo
Framework

Recurrent Regression for Face Recognition


Title	Recurrent Regression for Face Recognition
Authors	Yang Li, Wenming Zheng, Zhen Cui
Abstract	To address the sequential changes of images including poses, in this paper we propose a recurrent regression neural network(RRNN) framework to unify two classic tasks of cross-pose face recognition on still images and video-based face recognition. To imitate the changes of images, we explicitly construct the potential dependencies of sequential images so as to regularize the final learning model. By performing progressive transforms for sequentially adjacent images, RRNN can adaptively memorize and forget the information that benefits for the final classification. For face recognition of still images, given any one image with any one pose, we recurrently predict the images with its sequential poses to expect to capture some useful information of others poses. For video-based face recognition, the recurrent regression takes one entire sequence rather than one image as its input. We verify RRNN in static face dataset MultiPIE and face video dataset YouTube Celebrities(YTC). The comprehensive experimental results demonstrate the effectiveness of the proposed RRNN method.
Tasks	Face Recognition
Published	2016-07-24
URL	http://arxiv.org/abs/1607.06999v1
PDF	http://arxiv.org/pdf/1607.06999v1.pdf
PWC	https://paperswithcode.com/paper/recurrent-regression-for-face-recognition
Repo
Framework

Pure Exploration of Multi-armed Bandit Under Matroid Constraints


Title	Pure Exploration of Multi-armed Bandit Under Matroid Constraints
Authors	Lijie Chen, Anupam Gupta, Jian Li
Abstract	We study the pure exploration problem subject to a matroid constraint (Best-Basis) in a stochastic multi-armed bandit game. In a Best-Basis instance, we are given $n$ stochastic arms with unknown reward distributions, as well as a matroid $\mathcal{M}$ over the arms. Let the weight of an arm be the mean of its reward distribution. Our goal is to identify a basis of $\mathcal{M}$ with the maximum total weight, using as few samples as possible. The problem is a significant generalization of the best arm identification problem and the top-$k$ arm identification problem, which have attracted significant attentions in recent years. We study both the exact and PAC versions of Best-Basis, and provide algorithms with nearly-optimal sample complexities for these versions. Our results generalize and/or improve on several previous results for the top-$k$ arm identification problem and the combinatorial pure exploration problem when the combinatorial constraint is a matroid.
Tasks
Published	2016-05-23
URL	http://arxiv.org/abs/1605.07162v3
PDF	http://arxiv.org/pdf/1605.07162v3.pdf
PWC	https://paperswithcode.com/paper/pure-exploration-of-multi-armed-bandit-under
Repo
Framework

A Harmonic Extension Approach for Collaborative Ranking


Title	A Harmonic Extension Approach for Collaborative Ranking
Authors	Da Kuang, Zuoqiang Shi, Stanley Osher, Andrea Bertozzi
Abstract	We present a new perspective on graph-based methods for collaborative ranking for recommender systems. Unlike user-based or item-based methods that compute a weighted average of ratings given by the nearest neighbors, or low-rank approximation methods using convex optimization and the nuclear norm, we formulate matrix completion as a series of semi-supervised learning problems, and propagate the known ratings to the missing ones on the user-user or item-item graph globally. The semi-supervised learning problems are expressed as Laplace-Beltrami equations on a manifold, or namely, harmonic extension, and can be discretized by a point integral method. We show that our approach does not impose a low-rank Euclidean subspace on the data points, but instead minimizes the dimension of the underlying manifold. Our method, named LDM (low dimensional manifold), turns out to be particularly effective in generating rankings of items, showing decent computational efficiency and robust ranking quality compared to state-of-the-art methods.
Tasks	Collaborative Ranking, Matrix Completion, Recommendation Systems
Published	2016-02-16
URL	http://arxiv.org/abs/1602.05127v1
PDF	http://arxiv.org/pdf/1602.05127v1.pdf
PWC	https://paperswithcode.com/paper/a-harmonic-extension-approach-for
Repo
Framework

Distributed Convex Optimization with Many Convex Constraints


Title	Distributed Convex Optimization with Many Convex Constraints
Authors	Joachim Giesen, Sören Laue
Abstract	We address the problem of solving convex optimization problems with many convex constraints in a distributed setting. Our approach is based on an extension of the alternating direction method of multipliers (ADMM) that recently gained a lot of attention in the Big Data context. Although it has been invented decades ago, ADMM so far can be applied only to unconstrained problems and problems with linear equality or inequality constraints. Our extension can handle arbitrary inequality constraints directly. It combines the ability of ADMM to solve convex optimization problems in a distributed setting with the ability of the Augmented Lagrangian method to solve constrained optimization problems, and as we show, it inherits the convergence guarantees of ADMM and the Augmented Lagrangian method.
Tasks
Published	2016-10-07
URL	http://arxiv.org/abs/1610.02967v2
PDF	http://arxiv.org/pdf/1610.02967v2.pdf
PWC	https://paperswithcode.com/paper/distributed-convex-optimization-with-many
Repo
Framework

Spatio-Temporal Saliency Networks for Dynamic Saliency Prediction


Title	Spatio-Temporal Saliency Networks for Dynamic Saliency Prediction
Authors	Cagdas Bak, Aysun Kocak, Erkut Erdem, Aykut Erdem
Abstract	Computational saliency models for still images have gained significant popularity in recent years. Saliency prediction from videos, on the other hand, has received relatively little interest from the community. Motivated by this, in this work, we study the use of deep learning for dynamic saliency prediction and propose the so-called spatio-temporal saliency networks. The key to our models is the architecture of two-stream networks where we investigate different fusion mechanisms to integrate spatial and temporal information. We evaluate our models on the DIEM and UCF-Sports datasets and present highly competitive results against the existing state-of-the-art models. We also carry out some experiments on a number of still images from the MIT300 dataset by exploiting the optical flow maps predicted from these images. Our results show that considering inherent motion information in this way can be helpful for static saliency estimation.
Tasks	Optical Flow Estimation, Saliency Prediction
Published	2016-07-16
URL	http://arxiv.org/abs/1607.04730v2
PDF	http://arxiv.org/pdf/1607.04730v2.pdf
PWC	https://paperswithcode.com/paper/spatio-temporal-saliency-networks-for-dynamic
Repo
Framework

Estimating latent feature-feature interactions in large feature-rich graphs


Title	Estimating latent feature-feature interactions in large feature-rich graphs
Authors	Corrado Monti, Paolo Boldi
Abstract	Real-world complex networks describe connections between objects; in reality, those objects are often endowed with some kind of features. How does the presence or absence of such features interplay with the network link structure? Although the situation here described is truly ubiquitous, there is a limited body of research dealing with large graphs of this kind. Many previous works considered homophily as the only possible transmission mechanism translating node features into links. Other authors, instead, developed more sophisticated models, that are able to handle complex feature interactions, but are unfit to scale to very large networks. We expand on the MGJ model, where interactions between pairs of features can foster or discourage link formation. In this work, we will investigate how to estimate the latent feature-feature interactions in this model. We shall propose two solutions: the first one assumes feature independence and it is essentially based on Naive Bayes; the second one, which relaxes the independence assumption assumption, is based on perceptrons. In fact, we show it is possible to cast the model equation in order to see it as the prediction rule of a perceptron. We analyze how classical results for the perceptrons can be interpreted in this context; then, we define a fast and simple perceptron-like algorithm for this task, which can process $10^8$ links in minutes. We then compare these two techniques, first with synthetic datasets that follows our model, gaining evidence that the Naive independence assumptions are detrimental in practice. Secondly, we consider a real, large-scale citation network where each node (i.e., paper) can be described by different types of characteristics; there, our algorithm can assess how well each set of features can explain the links, and thus finding meaningful latent feature-feature interactions.
Tasks
Published	2016-12-03
URL	http://arxiv.org/abs/1612.00984v2
PDF	http://arxiv.org/pdf/1612.00984v2.pdf
PWC	https://paperswithcode.com/paper/estimating-latent-feature-feature
Repo
Framework