July 28, 2019

3184 words 15 mins read

Paper Group ANR 379

Budget-Constrained Multi-Armed Bandits with Multiple Plays. Unsupervised Learning of Long-Term Motion Dynamics for Videos. Learning an Executable Neural Semantic Parser. Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problem. Introduction to Formal Concept Analysis and Its Applications in Information Retrieva …

Budget-Constrained Multi-Armed Bandits with Multiple Plays


Title	Budget-Constrained Multi-Armed Bandits with Multiple Plays
Authors	Datong P. Zhou, Claire J. Tomlin
Abstract	We study the multi-armed bandit problem with multiple plays and a budget constraint for both the stochastic and the adversarial setting. At each round, exactly $K$ out of $N$ possible arms have to be played (with $1\leq K \leq N$). In addition to observing the individual rewards for each arm played, the player also learns a vector of costs which has to be covered with an a-priori defined budget $B$. The game ends when the sum of current costs associated with the played arms exceeds the remaining budget. Firstly, we analyze this setting for the stochastic case, for which we assume each arm to have an underlying cost and reward distribution with support $[c_{\min}, 1]$ and $[0, 1]$, respectively. We derive an Upper Confidence Bound (UCB) algorithm which achieves $O(NK^4 \log B)$ regret. Secondly, for the adversarial case in which the entire sequence of rewards and costs is fixed in advance, we derive an upper bound on the regret of order $O(\sqrt{NB\log(N/K)})$ utilizing an extension of the well-known $\texttt{Exp3}$ algorithm. We also provide upper bounds that hold with high probability and a lower bound of order $\Omega((1 - K/N)^2 \sqrt{NB/K})$.
Tasks	Multi-Armed Bandits
Published	2017-11-16
URL	http://arxiv.org/abs/1711.05928v1
PDF	http://arxiv.org/pdf/1711.05928v1.pdf
PWC	https://paperswithcode.com/paper/budget-constrained-multi-armed-bandits-with
Repo
Framework

Unsupervised Learning of Long-Term Motion Dynamics for Videos


Title	Unsupervised Learning of Long-Term Motion Dynamics for Videos
Authors	Zelun Luo, Boya Peng, De-An Huang, Alexandre Alahi, Li Fei-Fei
Abstract	We present an unsupervised representation learning approach that compactly encodes the motion dependencies in videos. Given a pair of images from a video clip, our framework learns to predict the long-term 3D motions. To reduce the complexity of the learning framework, we propose to describe the motion as a sequence of atomic 3D flows computed with RGB-D modality. We use a Recurrent Neural Network based Encoder-Decoder framework to predict these sequences of flows. We argue that in order for the decoder to reconstruct these sequences, the encoder must learn a robust video representation that captures long-term motion dependencies and spatial-temporal relations. We demonstrate the effectiveness of our learned temporal representations on activity classification across multiple modalities and datasets such as NTU RGB+D and MSR Daily Activity 3D. Our framework is generic to any input modality, i.e., RGB, Depth, and RGB-D videos.
Tasks	Representation Learning, Unsupervised Representation Learning
Published	2017-01-07
URL	http://arxiv.org/abs/1701.01821v3
PDF	http://arxiv.org/pdf/1701.01821v3.pdf
PWC	https://paperswithcode.com/paper/unsupervised-learning-of-long-term-motion
Repo
Framework

Learning an Executable Neural Semantic Parser


Title	Learning an Executable Neural Semantic Parser
Authors	Jianpeng Cheng, Siva Reddy, Vijay Saraswat, Mirella Lapata
Abstract	This paper describes a neural semantic parser that maps natural language utterances onto logical forms which can be executed against a task-specific environment, such as a knowledge base or a database, to produce a response. The parser generates tree-structured logical forms with a transition-based approach which combines a generic tree-generation algorithm with domain-general operations defined by the logical language. The generation process is modeled by structured recurrent neural networks, which provide a rich encoding of the sentential context and generation history for making predictions. To tackle mismatches between natural language and logical form tokens, various attention mechanisms are explored. Finally, we consider different training settings for the neural semantic parser, including a fully supervised training where annotated logical forms are given, weakly-supervised training where denotations are provided, and distant supervision where only unlabeled sentences and a knowledge base are available. Experiments across a wide range of datasets demonstrate the effectiveness of our parser.
Tasks
Published	2017-11-14
URL	http://arxiv.org/abs/1711.05066v2
PDF	http://arxiv.org/pdf/1711.05066v2.pdf
PWC	https://paperswithcode.com/paper/learning-an-executable-neural-semantic-parser
Repo
Framework

Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problem


Title	Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problem
Authors	Jie Zhong, Yijun Huang, Ji Liu
Abstract	This paper considers the multi-armed thresholding bandit problem – identifying all arms whose expected rewards are above a predefined threshold via as few pulls (or rounds) as possible – proposed by Locatelli et al. [2016] recently. Although the proposed algorithm in Locatelli et al. [2016] achieves the optimal round complexity in a certain sense, there still remain unsolved issues. This paper proposes an asynchronous parallel thresholding algorithm and its parameter-free version to improve the efficiency and the applicability. On one hand, the proposed two algorithms use the empirical variance to guide the pull decision at each round, and significantly improve the round complexity of the “optimal” algorithm when all arms have bounded high order moments. The proposed algorithms can be proven to be optimal. On the other hand, most bandit algorithms assume that the reward can be observed immediately after the pull or the next decision would not be made before all rewards are observed. Our proposed asynchronous parallel algorithms allow making the choice of the next pull with unobserved rewards from earlier pulls, which avoids such an unrealistic assumption and significantly improves the identification process. Our theoretical analysis justifies the effectiveness and the efficiency of proposed asynchronous parallel algorithms.
Tasks
Published	2017-04-15
URL	http://arxiv.org/abs/1704.04567v2
PDF	http://arxiv.org/pdf/1704.04567v2.pdf
PWC	https://paperswithcode.com/paper/asynchronous-parallel-empirical-variance
Repo
Framework


Title	Introduction to Formal Concept Analysis and Its Applications in Information Retrieval and Related Fields
Authors	Dmitry I. Ignatov
Abstract	This paper is a tutorial on Formal Concept Analysis (FCA) and its applications. FCA is an applied branch of Lattice Theory, a mathematical discipline which enables formalisation of concepts as basic units of human thinking and analysing data in the object-attribute form. Originated in early 80s, during the last three decades, it became a popular human-centred tool for knowledge representation and data analysis with numerous applications. Since the tutorial was specially prepared for RuSSIR 2014, the covered FCA topics include Information Retrieval with a focus on visualisation aspects, Machine Learning, Data Mining and Knowledge Discovery, Text Mining and several others.
Tasks	Information Retrieval
Published	2017-03-08
URL	http://arxiv.org/abs/1703.02819v1
PDF	http://arxiv.org/pdf/1703.02819v1.pdf
PWC	https://paperswithcode.com/paper/introduction-to-formal-concept-analysis-and
Repo
Framework

Using Deep Learning and Google Street View to Estimate the Demographic Makeup of the US


Title	Using Deep Learning and Google Street View to Estimate the Demographic Makeup of the US
Authors	Timnit Gebru, Jonathan Krause, Yilun Wang, Duyun Chen, Jia Deng, Erez Lieberman Aiden, Li Fei-Fei
Abstract	The United States spends more than $1B each year on initiatives such as the American Community Survey (ACS), a labor-intensive door-to-door study that measures statistics relating to race, gender, education, occupation, unemployment, and other demographic factors. Although a comprehensive source of data, the lag between demographic changes and their appearance in the ACS can exceed half a decade. As digital imagery becomes ubiquitous and machine vision techniques improve, automated data analysis may provide a cheaper and faster alternative. Here, we present a method that determines socioeconomic trends from 50 million images of street scenes, gathered in 200 American cities by Google Street View cars. Using deep learning-based computer vision techniques, we determined the make, model, and year of all motor vehicles encountered in particular neighborhoods. Data from this census of motor vehicles, which enumerated 22M automobiles in total (8% of all automobiles in the US), was used to accurately estimate income, race, education, and voting patterns, with single-precinct resolution. (The average US precinct contains approximately 1000 people.) The resulting associations are surprisingly simple and powerful. For instance, if the number of sedans encountered during a 15-minute drive through a city is higher than the number of pickup trucks, the city is likely to vote for a Democrat during the next Presidential election (88% chance); otherwise, it is likely to vote Republican (82%). Our results suggest that automated systems for monitoring demographic trends may effectively complement labor-intensive approaches, with the potential to detect trends with fine spatial resolution, in close to real time.
Tasks
Published	2017-02-22
URL	http://arxiv.org/abs/1702.06683v2
PDF	http://arxiv.org/pdf/1702.06683v2.pdf
PWC	https://paperswithcode.com/paper/using-deep-learning-and-google-street-view-to
Repo
Framework

Robust Matrix Elastic Net based Canonical Correlation Analysis: An Effective Algorithm for Multi-View Unsupervised Learning


Title	Robust Matrix Elastic Net based Canonical Correlation Analysis: An Effective Algorithm for Multi-View Unsupervised Learning
Authors	Peng-Bo Zhang, Zhi-Xin Yang
Abstract	This paper presents a robust matrix elastic net based canonical correlation analysis (RMEN-CCA) for multiple view unsupervised learning problems, which emphasizes the combination of CCA and the robust matrix elastic net (RMEN) used as coupled feature selection. The RMEN-CCA leverages the strength of the RMEN to distill naturally meaningful features without any prior assumption and to measure effectively correlations between different ‘views’. We can further employ directly the kernel trick to extend the RMEN-CCA to the kernel scenario with theoretical guarantees, which takes advantage of the kernel trick for highly complicated nonlinear feature learning. Rather than simply incorporating existing regularization minimization terms into CCA, this paper provides a new learning paradigm for CCA and is the first to derive a coupled feature selection based CCA algorithm that guarantees convergence. More significantly, for CCA, the newly-derived RMEN-CCA bridges the gap between measurement of relevance and coupled feature selection. Moreover, it is nontrivial to tackle directly the RMEN-CCA by previous optimization approaches derived from its sophisticated model architecture. Therefore, this paper further offers a bridge between a new optimization problem and an existing efficient iterative approach. As a consequence, the RMEN-CCA can overcome the limitation of CCA and address large-scale and streaming data problems. Experimental results on four popular competing datasets illustrate that the RMEN-CCA performs more effectively and efficiently than do state-of-the-art approaches.
Tasks	Feature Selection
Published	2017-11-14
URL	http://arxiv.org/abs/1711.05068v2
PDF	http://arxiv.org/pdf/1711.05068v2.pdf
PWC	https://paperswithcode.com/paper/robust-matrix-elastic-net-based-canonical
Repo
Framework

D numbers theory based game-theoretic framework in adversarial decision making under fuzzy environment


Title	D numbers theory based game-theoretic framework in adversarial decision making under fuzzy environment
Authors	Xinyang Deng, Wen Jiang
Abstract	Adversarial decision making is a particular type of decision making problem where the gain a decision maker obtains as a result of his decisions is affected by the actions taken by others. Representation of alternatives’ evaluations and methods to find the optimal alternative are two important aspects in the adversarial decision making. The aim of this study is to develop a general framework for solving the adversarial decision making issue under uncertain environment. By combining fuzzy set theory, game theory and D numbers theory (DNT), a DNT based game-theoretic framework for adversarial decision making under fuzzy environment is presented. Within the proposed framework or model, fuzzy set theory is used to model the uncertain evaluations of decision makers to alternatives, the non-exclusiveness among fuzzy evaluations are taken into consideration by using DNT, and the conflict of interests among decision makers is considered in a two-person non-constant sum game theory perspective. An illustrative application is given to demonstrate the effectiveness of the proposed model. This work, on one hand, has developed an effective framework for adversarial decision making under fuzzy environment; One the other hand, it has further improved the basis of DNT as a generalization of Dempster-Shafer theory for uncertainty reasoning.
Tasks	Decision Making, Skeleton Based Action Recognition
Published	2017-11-25
URL	http://arxiv.org/abs/1711.09186v1
PDF	http://arxiv.org/pdf/1711.09186v1.pdf
PWC	https://paperswithcode.com/paper/d-numbers-theory-based-game-theoretic
Repo
Framework

Deep Texture and Structure Aware Filtering Network for Image Smoothing


Title	Deep Texture and Structure Aware Filtering Network for Image Smoothing
Authors	Kaiyue Lu, Shaodi You, Nick Barnes
Abstract	Image smoothing is a fundamental task in computer vision, that aims to retain salient structures and remove insignificant textures. In this paper, we aim to address the fundamental shortcomings of existing image smoothing methods, which cannot properly distinguish textures and structures with similar low-level appearance. While deep learning approaches have started to explore the preservation of structure through image smoothing, existing work does not yet properly address textures. To this end, we generate a large dataset by blending natural textures with clean structure-only images, and then build a texture prediction network (TPN) that predicts the location and magnitude of textures. We then combine the TPN with a semantic structure prediction network (SPN) so that the final texture and structure aware filtering network (TSAFN) is able to identify the textures to remove (“texture-awareness”) and the structures to preserve (“structure-awareness”). The proposed model is easy to understand and implement, and shows excellent performance on real images in the wild as well as our generated dataset.
Tasks
Published	2017-12-07
URL	http://arxiv.org/abs/1712.02893v2
PDF	http://arxiv.org/pdf/1712.02893v2.pdf
PWC	https://paperswithcode.com/paper/deep-texture-and-structure-aware-filtering
Repo
Framework

Arabian Horse Identification Benchmark Dataset


Title	Arabian Horse Identification Benchmark Dataset
Authors	Ayat Taha, Ashraf Darwish, Aboul Ella Hassanien
Abstract	The lack of a standard muzzle print database is a challenge for conducting researches in Arabian horse identification systems. Therefore, collecting a muzzle print images database is a crucial decision. The dataset presented in this paper is an option for the studies that need a dataset for testing and comparing the algorithms under development for Arabian horse identification. Our collected dataset consists of 300 color images that were collected from 50 Arabian horse muzzle species. This dataset has been collected from 50 Arabian horses with 6 muzzle print images each. A special care has been given to the quality of the collected images. The collected images cover different quality levels and degradation factors such as image rotation and image partiality for simulating real time identification operations. This dataset can be used to test the identification of Arabian horse system including the extracted features and the selected classifier.
Tasks
Published	2017-06-15
URL	http://arxiv.org/abs/1706.04870v1
PDF	http://arxiv.org/pdf/1706.04870v1.pdf
PWC	https://paperswithcode.com/paper/arabian-horse-identification-benchmark
Repo
Framework

Multi-Layer Generalized Linear Estimation


Title	Multi-Layer Generalized Linear Estimation
Authors	Andre Manoel, Florent Krzakala, Marc Mézard, Lenka Zdeborová
Abstract	We consider the problem of reconstructing a signal from multi-layered (possibly) non-linear measurements. Using non-rigorous but standard methods from statistical physics we present the Multi-Layer Approximate Message Passing (ML-AMP) algorithm for computing marginal probabilities of the corresponding estimation problem and derive the associated state evolution equations to analyze its performance. We also give the expression of the asymptotic free energy and the minimal information-theoretically achievable reconstruction error. Finally, we present some applications of this measurement model for compressed sensing and perceptron learning with structured matrices/patterns, and for a simple model of estimation of latent variables in an auto-encoder.
Tasks
Published	2017-01-24
URL	http://arxiv.org/abs/1701.06981v1
PDF	http://arxiv.org/pdf/1701.06981v1.pdf
PWC	https://paperswithcode.com/paper/multi-layer-generalized-linear-estimation
Repo
Framework

What the Language You Tweet Says About Your Occupation


Title	What the Language You Tweet Says About Your Occupation
Authors	Tianran Hu, Haoyuan Xiao, Thuy-vy Thi Nguyen, Jiebo Luo
Abstract	Many aspects of people’s lives are proven to be deeply connected to their jobs. In this paper, we first investigate the distinct characteristics of major occupation categories based on tweets. From multiple social media platforms, we gather several types of user information. From users’ LinkedIn webpages, we learn their proficiencies. To overcome the ambiguity of self-reported information, a soft clustering approach is applied to extract occupations from crowd-sourced data. Eight job categories are extracted, including Marketing, Administrator, Start-up, Editor, Software Engineer, Public Relation, Office Clerk, and Designer. Meanwhile, users’ posts on Twitter provide cues for understanding their linguistic styles, interests, and personalities. Our results suggest that people of different jobs have unique tendencies in certain language styles and interests. Our results also clearly reveal distinctive levels in terms of Big Five Traits for different jobs. Finally, a classifier is built to predict job types based on the features extracted from tweets. A high accuracy indicates a strong discrimination power of language features for job prediction task.
Tasks
Published	2017-01-22
URL	http://arxiv.org/abs/1701.06233v1
PDF	http://arxiv.org/pdf/1701.06233v1.pdf
PWC	https://paperswithcode.com/paper/what-the-language-you-tweet-says-about-your
Repo
Framework

Lifting high-dimensional nonlinear models with Gaussian regressors


Title	Lifting high-dimensional nonlinear models with Gaussian regressors
Authors	Christos Thrampoulidis, Ankit Singh Rawat
Abstract	We study the problem of recovering a structured signal $\mathbf{x}_0$ from high-dimensional data $\mathbf{y}_i=f(\mathbf{a}_i^T\mathbf{x}_0)$ for some nonlinear (and potentially unknown) link function $f$, when the regressors $\mathbf{a}_i$ are iid Gaussian. Brillinger (1982) showed that ordinary least-squares estimates $\mathbf{x}0$ up to a constant of proportionality $\mu\ell$, which depends on $f$. Recently, Plan & Vershynin (2015) extended this result to the high-dimensional setting deriving sharp error bounds for the generalized Lasso. Unfortunately, both least-squares and the Lasso fail to recover $\mathbf{x}0$ when $\mu\ell=0$. For example, this includes all even link functions. We resolve this issue by proposing and analyzing an alternative convex recovery method. In a nutshell, our method treats such link functions as if they were linear in a lifted space of higher-dimension. Interestingly, our error analysis captures the effect of both the nonlinearity and the problem’s geometry in a few simple summary parameters.
Tasks
Published	2017-12-11
URL	http://arxiv.org/abs/1712.03638v2
PDF	http://arxiv.org/pdf/1712.03638v2.pdf
PWC	https://paperswithcode.com/paper/lifting-high-dimensional-nonlinear-models
Repo
Framework

Accurate Bayesian Data Classification without Hyperparameter Cross-validation


Title	Accurate Bayesian Data Classification without Hyperparameter Cross-validation
Authors	M Sheikh, A C C Coolen
Abstract	We extend the standard Bayesian multivariate Gaussian generative data classifier by considering a generalization of the conjugate, normal-Wishart prior distribution and by deriving the hyperparameters analytically via evidence maximization. The behaviour of the optimal hyperparameters is explored in the high-dimensional data regime. The classification accuracy of the resulting generalized model is competitive with state-of-the art Bayesian discriminant analysis methods, but without the usual computational burden of cross-validation.
Tasks
Published	2017-12-28
URL	http://arxiv.org/abs/1712.09813v1
PDF	http://arxiv.org/pdf/1712.09813v1.pdf
PWC	https://paperswithcode.com/paper/accurate-bayesian-data-classification-without
Repo
Framework

Git Blame Who?: Stylistic Authorship Attribution of Small, Incomplete Source Code Fragments


Title	Git Blame Who?: Stylistic Authorship Attribution of Small, Incomplete Source Code Fragments
Authors	Edwin Dauber, Aylin Caliskan, Richard Harang, Gregory Shearer, Michael Weisman, Frederica Nelson, Rachel Greenstadt
Abstract	Program authorship attribution has implications for the privacy of programmers who wish to contribute code anonymously. While previous work has shown that complete files that are individually authored can be attributed, we show here for the first time that accounts belonging to open source contributors containing short, incomplete, and typically uncompilable fragments can also be effectively attributed. We propose a technique for authorship attribution of contributor accounts containing small source code samples, such as those that can be obtained from version control systems or other direct comparison of sequential versions. We show that while application of previous methods to individual small source code samples yields an accuracy of about 73% for 106 programmers as a baseline, by ensembling and averaging the classification probabilities of a sufficiently large set of samples belonging to the same author we achieve 99% accuracy for assigning the set of samples to the correct author. Through these results, we demonstrate that attribution is an important threat to privacy for programmers even in real-world collaborative environments such as GitHub. Additionally, we propose the use of calibration curves to identify samples by unknown and previously unencountered authors in the open world setting. We show that we can also use these calibration curves in the case that we do not have linking information and thus are forced to classify individual samples directly. This is because the calibration curves allow us to identify which samples are more likely to have been correctly attributed. Using such a curve can help an analyst choose a cut-off point which will prevent most misclassifications, at the cost of causing the rejection of some of the more dubious correct attributions.
Tasks	Calibration
Published	2017-01-20
URL	https://arxiv.org/abs/1701.05681v3
PDF	https://arxiv.org/pdf/1701.05681v3.pdf
PWC	https://paperswithcode.com/paper/git-blame-who-stylistic-authorship
Repo
Framework