July 28, 2019

2800 words 14 mins read

Paper Group ANR 392

Multiresolution Match Kernels for Gesture Video Classification. Private Learning on Networks: Part II. Robust Shape Registration using Fuzzy Correspondences. Approximating Partition Functions in Constant Time. A Unified Neural Network Approach for Estimating Travel Time and Distance for a Taxi Trip. Expressive power of recurrent neural networks. Co …

Multiresolution Match Kernels for Gesture Video Classification


Title	Multiresolution Match Kernels for Gesture Video Classification
Authors	Hemanth Venkateswara, Vineeth N. Balasubramanian, Prasanth Lade, Sethuraman Panchanathan
Abstract	The emergence of depth imaging technologies like the Microsoft Kinect has renewed interest in computational methods for gesture classification based on videos. For several years now, researchers have used the Bag-of-Features (BoF) as a primary method for generation of feature vectors from video data for recognition of gestures. However, the BoF method is a coarse representation of the information in a video, which often leads to poor similarity measures between videos. Besides, when features extracted from different spatio-temporal locations in the video are pooled to create histogram vectors in the BoF method, there is an intrinsic loss of their original locations in space and time. In this paper, we propose a new Multiresolution Match Kernel (MMK) for video classification, which can be considered as a generalization of the BoF method. We apply this procedure to hand gesture classification based on RGB-D videos of the American Sign Language(ASL) hand gestures and our results show promise and usefulness of this new method.
Tasks	Video Classification
Published	2017-06-23
URL	http://arxiv.org/abs/1706.07530v1
PDF	http://arxiv.org/pdf/1706.07530v1.pdf
PWC	https://paperswithcode.com/paper/multiresolution-match-kernels-for-gesture
Repo
Framework

Private Learning on Networks: Part II


Title	Private Learning on Networks: Part II
Authors	Shripad Gade, Nitin H. Vaidya
Abstract	This paper considers a distributed multi-agent optimization problem, with the global objective consisting of the sum of local objective functions of the agents. The agents solve the optimization problem using local computation and communication between adjacent agents in the network. We present two randomized iterative algorithms for distributed optimization. To improve privacy, our algorithms add “structured” randomization to the information exchanged between the agents. We prove deterministic correctness (in every execution) of the proposed algorithms despite the information being perturbed by noise with non-zero mean. We prove that a special case of a proposed algorithm (called function sharing) preserves privacy of individual polynomial objective functions under a suitable connectivity condition on the network topology.
Tasks	Distributed Optimization
Published	2017-03-27
URL	http://arxiv.org/abs/1703.09185v2
PDF	http://arxiv.org/pdf/1703.09185v2.pdf
PWC	https://paperswithcode.com/paper/private-learning-on-networks-part-ii
Repo
Framework

Robust Shape Registration using Fuzzy Correspondences


Title	Robust Shape Registration using Fuzzy Correspondences
Authors	Abhishek Kolagunda, Scott Sorensen, Philip Saponaro, Wayne Treible, Chandra Kambhamettu
Abstract	Shape registration is the process of aligning one 3D model to another. Most previous methods to align shapes with no known correspondences attempt to solve for both the transformation and correspondences iteratively. We present a shape registration approach that solves for the transformation using fuzzy correspondences to maximize the overlap between the given shape and the target shape. A coarse to fine approach with Levenberg-Marquardt method is used for optimization. Real and synthetic experiments show our approach is robust and outperforms other state of the art methods when point clouds are noisy, sparse, and have non-uniform density. Experiments show our method is more robust to initialization and can handle larger scale changes and rotation than other methods. We also show that the approach can be used for 2D-3D alignment via ray-point alignment.
Tasks
Published	2017-02-18
URL	http://arxiv.org/abs/1702.05664v1
PDF	http://arxiv.org/pdf/1702.05664v1.pdf
PWC	https://paperswithcode.com/paper/robust-shape-registration-using-fuzzy
Repo
Framework

Approximating Partition Functions in Constant Time


Title	Approximating Partition Functions in Constant Time
Authors	Vishesh Jain, Frederic Koehler, Elchanan Mossel
Abstract	We study approximations of the partition function of dense graphical models. Partition functions of graphical models play a fundamental role is statistical physics, in statistics and in machine learning. Two of the main methods for approximating the partition function are Markov Chain Monte Carlo and Variational Methods. An impressive body of work in mathematics, physics and theoretical computer science provides conditions under which Markov Chain Monte Carlo methods converge in polynomial time. These methods often lead to polynomial time approximation algorithms for the partition function in cases where the underlying model exhibits correlation decay. There are very few theoretical guarantees for the performance of variational methods. One exception is recent results by Risteski (2016) who considered dense graphical models and showed that using variational methods, it is possible to find an $O(\epsilon n)$ additive approximation to the log partition function in time $n^{O(1/\epsilon^2)}$ even in a regime where correlation decay does not hold. We show that under essentially the same conditions, an $O(\epsilon n)$ additive approximation of the log partition function can be found in constant time, independent of $n$. In particular, our results cover dense Ising and Potts models as well as dense graphical models with $k$-wise interaction. They also apply for low threshold rank models.
Tasks
Published	2017-11-05
URL	http://arxiv.org/abs/1711.01655v2
PDF	http://arxiv.org/pdf/1711.01655v2.pdf
PWC	https://paperswithcode.com/paper/approximating-partition-functions-in-constant
Repo
Framework

A Unified Neural Network Approach for Estimating Travel Time and Distance for a Taxi Trip


Title	A Unified Neural Network Approach for Estimating Travel Time and Distance for a Taxi Trip
Authors	Ishan Jindal, Tony, Qin, Xuewen Chen, Matthew Nokleby, Jieping Ye
Abstract	In building intelligent transportation systems such as taxi or rideshare services, accurate prediction of travel time and distance is crucial for customer experience and resource management. Using the NYC taxi dataset, which contains taxi trips data collected from GPS-enabled taxis [23], this paper investigates the use of deep neural networks to jointly predict taxi trip time and distance. We propose a model, called ST-NN (Spatio-Temporal Neural Network), which first predicts the travel distance between an origin and a destination GPS coordinate, then combines this prediction with the time of day to predict the travel time. The beauty of ST-NN is that it uses only the raw trips data without requiring further feature engineering and provides a joint estimate of travel time and distance. We compare the performance of ST-NN to that of state-of-the-art travel time estimation methods, and we observe that the proposed approach generalizes better than state-of-the-art methods. We show that ST-NN approach significantly reduces the mean absolute error for both predicted travel time and distance, about 17% for travel time prediction. We also observe that the proposed approach is more robust to outliers present in the dataset by testing the performance of ST-NN on the datasets with and without outliers.
Tasks	Feature Engineering
Published	2017-10-12
URL	http://arxiv.org/abs/1710.04350v1
PDF	http://arxiv.org/pdf/1710.04350v1.pdf
PWC	https://paperswithcode.com/paper/a-unified-neural-network-approach-for
Repo
Framework

Expressive power of recurrent neural networks


Title	Expressive power of recurrent neural networks
Authors	Valentin Khrulkov, Alexander Novikov, Ivan Oseledets
Abstract	Deep neural networks are surprisingly efficient at solving practical tasks, but the theory behind this phenomenon is only starting to catch up with the practice. Numerous works show that depth is the key to this efficiency. A certain class of deep convolutional networks – namely those that correspond to the Hierarchical Tucker (HT) tensor decomposition – has been proven to have exponentially higher expressive power than shallow networks. I.e. a shallow network of exponential width is required to realize the same score function as computed by the deep architecture. In this paper, we prove the expressive power theorem (an exponential lower bound on the width of the equivalent shallow network) for a class of recurrent neural networks – ones that correspond to the Tensor Train (TT) decomposition. This means that even processing an image patch by patch with an RNN can be exponentially more efficient than a (shallow) convolutional network with one hidden layer. Using theoretical results on the relation between the tensor decompositions we compare expressive powers of the HT- and TT-Networks. We also implement the recurrent TT-Networks and provide numerical evidence of their expressivity.
Tasks
Published	2017-11-02
URL	http://arxiv.org/abs/1711.00811v2
PDF	http://arxiv.org/pdf/1711.00811v2.pdf
PWC	https://paperswithcode.com/paper/expressive-power-of-recurrent-neural-networks
Repo
Framework

Concept Drift Learning with Alternating Learners


Title	Concept Drift Learning with Alternating Learners
Authors	Yunwen Xu, Rui Xu, Weizhong Yan, Paul Ardis
Abstract	Data-driven predictive analytics are in use today across a number of industrial applications, but further integration is hindered by the requirement of similarity among model training and test data distributions. This paper addresses the need of learning from possibly nonstationary data streams, or under concept drift, a commonly seen phenomenon in practical applications. A simple dual-learner ensemble strategy, alternating learners framework, is proposed. A long-memory model learns stable concepts from a long relevant time window, while a short-memory model learns transient concepts from a small recent window. The difference in prediction performance of these two models is monitored and induces an alternating policy to select, update and reset the two models. The method features an online updating mechanism to maintain the ensemble accuracy, and a concept-dependent trigger to focus on relevant data. Through empirical studies the method demonstrates effective tracking and prediction when the steaming data carry abrupt and/or gradual changes.
Tasks
Published	2017-10-18
URL	http://arxiv.org/abs/1710.06940v1
PDF	http://arxiv.org/pdf/1710.06940v1.pdf
PWC	https://paperswithcode.com/paper/concept-drift-learning-with-alternating
Repo
Framework

Quantile Markov Decision Process


Title	Quantile Markov Decision Process
Authors	Xiaocheng Li, Huaiyang Zhong, Margaret L. Brandeau
Abstract	In this paper, we consider the problem of optimizing the quantiles of the cumulative rewards of Markov Decision Processes (MDP), to which we refers as Quantile Markov Decision Processes (QMDP). Traditionally, the goal of a Markov Decision Process (MDP) is to maximize expected cumulative reward over a defined horizon (possibly to be infinite). In many applications, however, a decision maker may be interested in optimizing a specific quantile of the cumulative reward instead of its expectation. Our framework of QMDP provides analytical results characterizing the optimal QMDP solution and presents the algorithm for solving the QMDP. We provide analytical results characterizing the optimal QMDP solution and present the algorithms for solving the QMDP. We illustrate the model with two experiments: a grid game and a HIV optimal treatment experiment.
Tasks
Published	2017-11-15
URL	https://arxiv.org/abs/1711.05788v3
PDF	https://arxiv.org/pdf/1711.05788v3.pdf
PWC	https://paperswithcode.com/paper/quantile-markov-decision-process
Repo
Framework

An Unsupervised Approach for Mapping between Vector Spaces


Title	An Unsupervised Approach for Mapping between Vector Spaces
Authors	Syed Sarfaraz Akhtar, Arihant Gupta, Avijit Vajpayee, Arjit Srivastava, Madan Gopal Jhawar, Manish Shrivastava
Abstract	We present a language independent, unsupervised approach for transforming word embeddings from source language to target language using a transformation matrix. Our model handles the problem of data scarcity which is faced by many languages in the world and yields improved word embeddings for words in the target language by relying on transformed embeddings of words of the source language. We initially evaluate our approach via word similarity tasks on a similar language pair - Hindi as source and Urdu as the target language, while we also evaluate our method on French and German as target languages and English as source language. Our approach improves the current state of the art results - by 13% for French and 19% for German. For Urdu, we saw an increment of 16% over our initial baseline score. We further explore the prospects of our approach by applying it on multiple models of the same language and transferring words between the two models, thus solving the problem of missing words in a model. We evaluate this on word similarity and word analogy tasks.
Tasks	Word Embeddings
Published	2017-11-15
URL	http://arxiv.org/abs/1711.05680v2
PDF	http://arxiv.org/pdf/1711.05680v2.pdf
PWC	https://paperswithcode.com/paper/an-unsupervised-approach-for-mapping-between
Repo
Framework

Tight Semi-Nonnegative Matrix Factorization


Title	Tight Semi-Nonnegative Matrix Factorization
Authors	David W Dreisigmeyer
Abstract	The nonnegative matrix factorization is a widely used, flexible matrix decomposition, finding applications in biology, image and signal processing and information retrieval, among other areas. Here we present a related matrix factorization. A multi-objective optimization problem finds conical combinations of templates that approximate a given data matrix. The templates are chosen so that as far as possible only the initial data set can be represented this way. However, the templates are not required to be nonnegative nor convex combinations of the original data.
Tasks	Information Retrieval
Published	2017-09-13
URL	http://arxiv.org/abs/1709.04395v3
PDF	http://arxiv.org/pdf/1709.04395v3.pdf
PWC	https://paperswithcode.com/paper/tight-semi-nonnegative-matrix-factorization
Repo
Framework

CNN-Based Prediction of Frame-Level Shot Importance for Video Summarization


Title	CNN-Based Prediction of Frame-Level Shot Importance for Video Summarization
Authors	Mohaiminul Al Nahian, A. S. M. Iftekhar, Mohammad Tariqul Islam, S. M. Mahbubur Rahman, Dimitrios Hatzinakos
Abstract	In the Internet, ubiquitous presence of redundant, unedited, raw videos has made video summarization an important problem. Traditional methods of video summarization employ a heuristic set of hand-crafted features, which in many cases fail to capture subtle abstraction of a scene. This paper presents a deep learning method that maps the context of a video to the importance of a scene similar to that is perceived by humans. In particular, a convolutional neural network (CNN)-based architecture is proposed to mimic the frame-level shot importance for user-oriented video summarization. The weights and biases of the CNN are trained extensively through off-line processing, so that it can provide the importance of a frame of an unseen video almost instantaneously. Experiments on estimating the shot importance is carried out using the publicly available database TVSum50. It is shown that the performance of the proposed network is substantially better than that of commonly referred feature-based methods for estimating the shot importance in terms of mean absolute error, absolute error variance, and relative F-measure.
Tasks	Video Summarization
Published	2017-08-23
URL	http://arxiv.org/abs/1708.07023v1
PDF	http://arxiv.org/pdf/1708.07023v1.pdf
PWC	https://paperswithcode.com/paper/cnn-based-prediction-of-frame-level-shot
Repo
Framework

Robust Sparse Estimation Tasks in High Dimensions


Title	Robust Sparse Estimation Tasks in High Dimensions
Authors	Jerry Li
Abstract	In this paper we initiate the study of whether or not sparse estimation tasks can be performed efficiently in high dimensions, in the robust setting where an $\eps$-fraction of samples are corrupted adversarially. We study the natural robust version of two classical sparse estimation problems, namely, sparse mean estimation and sparse PCA in the spiked covariance model. For both of these problems, we provide the first efficient algorithms that provide non-trivial error guarantees in the presence of noise, using only a number of samples which is similar to the number required for these problems without noise. In particular, our sample complexities are sublinear in the ambient dimension $d$. Our work also suggests evidence for new computational-vs-statistical gaps for these problems (similar to those for sparse PCA without noise) which only arise in the presence of noise.
Tasks
Published	2017-02-20
URL	http://arxiv.org/abs/1702.05860v2
PDF	http://arxiv.org/pdf/1702.05860v2.pdf
PWC	https://paperswithcode.com/paper/robust-sparse-estimation-tasks-in-high
Repo
Framework


Title	The Merits of Sharing a Ride
Authors	Pooyan Ehsani, Jia Yuan Yu
Abstract	The culture of sharing instead of ownership is sharply increasing in individuals behaviors. Particularly in transportation, concepts of sharing a ride in either carpooling or ridesharing have been recently adopted. An efficient optimization approach to match passengers in real-time is the core of any ridesharing system. In this paper, we model ridesharing as an online matching problem on general graphs such that passengers do not drive private cars and use shared taxis. We propose an optimization algorithm to solve it. The outlined algorithm calculates the optimal waiting time when a passenger arrives. This leads to a matching with minimal overall overheads while maximizing the number of partnerships. To evaluate the behavior of our algorithm, we used NYC taxi real-life data set. Results represent a substantial reduction in overall overheads.
Tasks
Published	2017-12-19
URL	http://arxiv.org/abs/1712.10011v1
PDF	http://arxiv.org/pdf/1712.10011v1.pdf
PWC	https://paperswithcode.com/paper/the-merits-of-sharing-a-ride
Repo
Framework

Unsupervised Sequence Classification using Sequential Output Statistics


Title	Unsupervised Sequence Classification using Sequential Output Statistics
Authors	Yu Liu, Jianshu Chen, Li Deng
Abstract	We consider learning a sequence classifier without labeled data by using sequential output statistics. The problem is highly valuable since obtaining labels in training data is often costly, while the sequential output statistics (e.g., language models) could be obtained independently of input data and thus with low or no cost. To address the problem, we propose an unsupervised learning cost function and study its properties. We show that, compared to earlier works, it is less inclined to be stuck in trivial solutions and avoids the need for a strong generative model. Although it is harder to optimize in its functional form, a stochastic primal-dual gradient method is developed to effectively solve the problem. Experiment results on real-world datasets demonstrate that the new unsupervised learning method gives drastically lower errors than other baseline methods. Specifically, it reaches test errors about twice of those obtained by fully supervised learning.
Tasks
Published	2017-02-25
URL	http://arxiv.org/abs/1702.07817v2
PDF	http://arxiv.org/pdf/1702.07817v2.pdf
PWC	https://paperswithcode.com/paper/unsupervised-sequence-classification-using
Repo
Framework

Bayesian Learning of Clique Tree Structure


Title	Bayesian Learning of Clique Tree Structure
Authors	Cetin Savkli, J. Ryan Carr, Philip Graff, Lauren Kennell
Abstract	The problem of categorical data analysis in high dimensions is considered. A discussion of the fundamental difficulties of probability modeling is provided, and a solution to the derivation of high dimensional probability distributions based on Bayesian learning of clique tree decomposition is presented. The main contributions of this paper are an automated determination of the optimal clique tree structure for probability modeling, the resulting derived probability distribution, and a corresponding unified approach to clustering and anomaly detection based on the probability distribution.
Tasks	Anomaly Detection
Published	2017-08-23
URL	http://arxiv.org/abs/1708.07025v1
PDF	http://arxiv.org/pdf/1708.07025v1.pdf
PWC	https://paperswithcode.com/paper/bayesian-learning-of-clique-tree-structure
Repo
Framework