May 5, 2019

2790 words 14 mins read

Paper Group ANR 486

Optimal Inference in Crowdsourced Classification via Belief Propagation. Analysis of opinionated text for opinion mining. Linear Thompson Sampling Revisited. Using Deep Q-Learning to Control Optimization Hyperparameters. Community Recovery in Graphs with Locality. Bridging Medical Data Inference to Achilles Tendon Rupture Rehabilitation. An Experim …

Optimal Inference in Crowdsourced Classification via Belief Propagation


Title	Optimal Inference in Crowdsourced Classification via Belief Propagation
Authors	Jungseul Ok, Sewoong Oh, Jinwoo Shin, Yung Yi
Abstract	Crowdsourcing systems are popular for solving large-scale labelling tasks with low-paid workers. We study the problem of recovering the true labels from the possibly erroneous crowdsourced labels under the popular Dawid-Skene model. To address this inference problem, several algorithms have recently been proposed, but the best known guarantee is still significantly larger than the fundamental limit. We close this gap by introducing a tighter lower bound on the fundamental limit and proving that Belief Propagation (BP) exactly matches this lower bound. The guaranteed optimality of BP is the strongest in the sense that it is information-theoretically impossible for any other algorithm to correctly label a larger fraction of the tasks. Experimental results suggest that BP is close to optimal for all regimes considered and improves upon competing state-of-the-art algorithms.
Tasks
Published	2016-02-11
URL	http://arxiv.org/abs/1602.03619v4
PDF	http://arxiv.org/pdf/1602.03619v4.pdf
PWC	https://paperswithcode.com/paper/optimal-inference-in-crowdsourced
Repo
Framework

Analysis of opinionated text for opinion mining


Title	Analysis of opinionated text for opinion mining
Authors	K Paramesha, K C Ravishankar
Abstract	In sentiment analysis, the polarities of the opinions expressed on an object/feature are determined to assess the sentiment of a sentence or document whether it is positive/negative/neutral. Naturally, the object/feature is a noun representation which refers to a product or a component of a product, let us say, the “lens” in a camera and opinions emanating on it are captured in adjectives, verbs, adverbs and noun words themselves. Apart from such words, other meta-information and diverse effective features are also going to play an important role in influencing the sentiment polarity and contribute significantly to the performance of the system. In this paper, some of the associated information/meta-data are explored and investigated in the sentiment text. Based on the analysis results presented here, there is scope for further assessment and utilization of the meta-information as features in text categorization, ranking text document, identification of spam documents and polarity classification problems.
Tasks	Opinion Mining, Sentiment Analysis, Text Categorization
Published	2016-07-09
URL	http://arxiv.org/abs/1607.02576v2
PDF	http://arxiv.org/pdf/1607.02576v2.pdf
PWC	https://paperswithcode.com/paper/analysis-of-opinionated-text-for-opinion
Repo
Framework

Linear Thompson Sampling Revisited


Title	Linear Thompson Sampling Revisited
Authors	Marc Abeille, Alessandro Lazaric
Abstract	We derive an alternative proof for the regret of Thompson sampling (\ts) in the stochastic linear bandit setting. While we obtain a regret bound of order $\widetilde{O}(d^{3/2}\sqrt{T})$ as in previous results, the proof sheds new light on the functioning of the \ts. We leverage on the structure of the problem to show how the regret is related to the sensitivity (i.e., the gradient) of the objective function and how selecting optimal arms associated to \textit{optimistic} parameters does control it. Thus we show that \ts can be seen as a generic randomized algorithm where the sampling distribution is designed to have a fixed probability of being optimistic, at the cost of an additional $\sqrt{d}$ regret factor compared to a UCB-like approach. Furthermore, we show that our proof can be readily applied to regularized linear optimization and generalized linear model problems.
Tasks
Published	2016-11-20
URL	https://arxiv.org/abs/1611.06534v3
PDF	https://arxiv.org/pdf/1611.06534v3.pdf
PWC	https://paperswithcode.com/paper/linear-thompson-sampling-revisited
Repo
Framework

Using Deep Q-Learning to Control Optimization Hyperparameters


Title	Using Deep Q-Learning to Control Optimization Hyperparameters
Authors	Samantha Hansen
Abstract	We present a novel definition of the reinforcement learning state, actions and reward function that allows a deep Q-network (DQN) to learn to control an optimization hyperparameter. Using Q-learning with experience replay, we train two DQNs to accept a state representation of an objective function as input and output the expected discounted return of rewards, or q-values, connected to the actions of either adjusting the learning rate or leaving it unchanged. The two DQNs learn a policy similar to a line search, but differ in the number of allowed actions. The trained DQNs in combination with a gradient-based update routine form the basis of the Q-gradient descent algorithms. To demonstrate the viability of this framework, we show that the DQN’s q-values associated with optimal action converge and that the Q-gradient descent algorithms outperform gradient descent with an Armijo or nonmonotone line search. Unlike traditional optimization methods, Q-gradient descent can incorporate any objective statistic and by varying the actions we gain insight into the type of learning rate adjustment strategies that are successful for neural network optimization.
Tasks	Q-Learning
Published	2016-02-12
URL	http://arxiv.org/abs/1602.04062v2
PDF	http://arxiv.org/pdf/1602.04062v2.pdf
PWC	https://paperswithcode.com/paper/using-deep-q-learning-to-control-optimization
Repo
Framework

Community Recovery in Graphs with Locality


Title	Community Recovery in Graphs with Locality
Authors	Yuxin Chen, Govinda Kamath, Changho Suh, David Tse
Abstract	Motivated by applications in domains such as social networks and computational biology, we study the problem of community recovery in graphs with locality. In this problem, pairwise noisy measurements of whether two nodes are in the same community or different communities come mainly or exclusively from nearby nodes rather than uniformly sampled between all nodes pairs, as in most existing models. We present an algorithm that runs nearly linearly in the number of measurements and which achieves the information theoretic limit for exact recovery.
Tasks
Published	2016-02-11
URL	http://arxiv.org/abs/1602.03828v3
PDF	http://arxiv.org/pdf/1602.03828v3.pdf
PWC	https://paperswithcode.com/paper/community-recovery-in-graphs-with-locality
Repo
Framework

Bridging Medical Data Inference to Achilles Tendon Rupture Rehabilitation


Title	Bridging Medical Data Inference to Achilles Tendon Rupture Rehabilitation
Authors	An Qu, Cheng Zhang, Paul Ackermann, Hedvig Kjellström
Abstract	Imputing incomplete medical tests and predicting patient outcomes are crucial for guiding the decision making for therapy, such as after an Achilles Tendon Rupture (ATR). We formulate the problem of data imputation and prediction for ATR relevant medical measurements into a recommender system framework. By applying MatchBox, which is a collaborative filtering approach, on a real dataset collected from 374 ATR patients, we aim at offering personalized medical data imputation and prediction. In this work, we show the feasibility of this approach and discuss potential research directions by conducting initial qualitative evaluations.
Tasks	Decision Making, Imputation, Predicting Patient Outcomes, Recommendation Systems
Published	2016-12-07
URL	http://arxiv.org/abs/1612.02490v1
PDF	http://arxiv.org/pdf/1612.02490v1.pdf
PWC	https://paperswithcode.com/paper/bridging-medical-data-inference-to-achilles
Repo
Framework

An Experimental Study of LSTM Encoder-Decoder Model for Text Simplification


Title	An Experimental Study of LSTM Encoder-Decoder Model for Text Simplification
Authors	Tong Wang, Ping Chen, Kevin Amaral, Jipeng Qiang
Abstract	Text simplification (TS) aims to reduce the lexical and structural complexity of a text, while still retaining the semantic meaning. Current automatic TS techniques are limited to either lexical-level applications or manually defining a large amount of rules. Since deep neural networks are powerful models that have achieved excellent performance over many difficult tasks, in this paper, we propose to use the Long Short-Term Memory (LSTM) Encoder-Decoder model for sentence level TS, which makes minimal assumptions about word sequence. We conduct preliminary experiments to find that the model is able to learn operation rules such as reversing, sorting and replacing from sequence pairs, which shows that the model may potentially discover and apply rules such as modifying sentence structure, substituting words, and removing words for TS.
Tasks	Text Simplification
Published	2016-09-13
URL	http://arxiv.org/abs/1609.03663v1
PDF	http://arxiv.org/pdf/1609.03663v1.pdf
PWC	https://paperswithcode.com/paper/an-experimental-study-of-lstm-encoder-decoder
Repo
Framework

Real-time eSports Match Result Prediction


Title	Real-time eSports Match Result Prediction
Authors	Yifan Yang, Tian Qin, Yu-Heng Lei
Abstract	In this paper, we try to predict the winning team of a match in the multiplayer eSports game Dota 2. To address the weaknesses of previous work, we consider more aspects of prior (pre-match) features from individual players’ match history, as well as real-time (during-match) features at each minute as the match progresses. We use logistic regression, the proposed Attribute Sequence Model, and their combinations as the prediction models. In a dataset of 78362 matches where 20631 matches contain replay data, our experiments show that adding more aspects of prior features improves accuracy from 58.69% to 71.49%, and introducing real-time features achieves up to 93.73% accuracy when predicting at the 40th minute.
Tasks	Dota 2
Published	2016-12-10
URL	http://arxiv.org/abs/1701.03162v1
PDF	http://arxiv.org/pdf/1701.03162v1.pdf
PWC	https://paperswithcode.com/paper/real-time-esports-match-result-prediction
Repo
Framework

Multi-Language Identification Using Convolutional Recurrent Neural Network


Title	Multi-Language Identification Using Convolutional Recurrent Neural Network
Authors	Vrishabh Ajay Lakhani, Rohan Mahadev
Abstract	Language Identification, being an important aspect of Automatic Speaker Recognition has had many changes and new approaches to ameliorate performance over the last decade. We compare the performance of using audio spectrum in the log scale and using Polyphonic sound sequences from raw audio samples to train the neural network and to classify speech as either English or Spanish. To achieve this, we use the novel approach of using a Convolutional Recurrent Neural Network using Long Short Term Memory (LSTM) or a Gated Recurrent Unit (GRU) for forward propagation of the neural network. Our hypothesis is that the performance of using polyphonic sound sequence as features and both LSTM and GRU as the gating mechanisms for the neural network outperform the traditional MFCC features using a unidirectional Deep Neural Network.
Tasks	Language Identification, Speaker Recognition
Published	2016-11-12
URL	http://arxiv.org/abs/1611.04010v2
PDF	http://arxiv.org/pdf/1611.04010v2.pdf
PWC	https://paperswithcode.com/paper/multi-language-identification-using
Repo
Framework

Multi-Label Image Classification with Regional Latent Semantic Dependencies


Title	Multi-Label Image Classification with Regional Latent Semantic Dependencies
Authors	Junjie Zhang, Qi Wu, Chunhua Shen, Jian Zhang, Jianfeng Lu
Abstract	Deep convolution neural networks (CNN) have demonstrated advanced performance on single-label image classification, and various progress also have been made to apply CNN methods on multi-label image classification, which requires to annotate objects, attributes, scene categories etc. in a single shot. Recent state-of-the-art approaches to multi-label image classification exploit the label dependencies in an image, at global level, largely improving the labeling capacity. However, predicting small objects and visual concepts is still challenging due to the limited discrimination of the global visual features. In this paper, we propose a Regional Latent Semantic Dependencies model (RLSD) to address this problem. The utilized model includes a fully convolutional localization architecture to localize the regions that may contain multiple highly-dependent labels. The localized regions are further sent to the recurrent neural networks (RNN) to characterize the latent semantic dependencies at the regional level. Experimental results on several benchmark datasets show that our proposed model achieves the best performance compared to the state-of-the-art models, especially for predicting small objects occurred in the images. In addition, we set up an upper bound model (RLSD+ft-RPN) using bounding box coordinates during training, the experimental results also show that our RLSD can approach the upper bound without using the bounding-box annotations, which is more realistic in the real world.
Tasks	Image Classification
Published	2016-12-04
URL	http://arxiv.org/abs/1612.01082v3
PDF	http://arxiv.org/pdf/1612.01082v3.pdf
PWC	https://paperswithcode.com/paper/multi-label-image-classification-with
Repo
Framework

Asymptotic behavior of $\ell_p$-based Laplacian regularization in semi-supervised learning


Title	Asymptotic behavior of $\ell_p$-based Laplacian regularization in semi-supervised learning
Authors	Ahmed El Alaoui, Xiang Cheng, Aaditya Ramdas, Martin J. Wainwright, Michael I. Jordan
Abstract	Given a weighted graph with $N$ vertices, consider a real-valued regression problem in a semi-supervised setting, where one observes $n$ labeled vertices, and the task is to label the remaining ones. We present a theoretical study of $\ell_p$-based Laplacian regularization under a $d$-dimensional geometric random graph model. We provide a variational characterization of the performance of this regularized learner as $N$ grows to infinity while $n$ stays constant, the associated optimality conditions lead to a partial differential equation that must be satisfied by the associated function estimate $\hat{f}$. From this formulation we derive several predictions on the limiting behavior the $d$-dimensional function $\hat{f}$, including (a) a phase transition in its smoothness at the threshold $p = d + 1$, and (b) a tradeoff between smoothness and sensitivity to the underlying unlabeled data distribution $P$. Thus, over the range $p \leq d$, the function estimate $\hat{f}$ is degenerate and “spiky,” whereas for $p\geq d+1$, the function estimate $\hat{f}$ is smooth. We show that the effect of the underlying density vanishes monotonically with $p$, such that in the limit $p = \infty$, corresponding to the so-called Absolutely Minimal Lipschitz Extension, the estimate $\hat{f}$ is independent of the distribution $P$. Under the assumption of semi-supervised smoothness, ignoring $P$ can lead to poor statistical performance, in particular, we construct a specific example for $d=1$ to demonstrate that $p=2$ has lower risk than $p=\infty$ due to the former penalty adapting to $P$ and the latter ignoring it. We also provide simulations that verify the accuracy of our predictions for finite sample sizes. Together, these properties show that $p = d+1$ is an optimal choice, yielding a function estimate $\hat{f}$ that is both smooth and non-degenerate, while remaining maximally sensitive to $P$.
Tasks
Published	2016-03-02
URL	http://arxiv.org/abs/1603.00564v1
PDF	http://arxiv.org/pdf/1603.00564v1.pdf
PWC	https://paperswithcode.com/paper/asymptotic-behavior-of-ell_p-based-laplacian
Repo
Framework

Towards an Indexical Model of Situated Language Comprehension for Cognitive Agents in Physical Worlds


Title	Towards an Indexical Model of Situated Language Comprehension for Cognitive Agents in Physical Worlds
Authors	Shiwali Mohan, Aaron Mininger, John Laird
Abstract	We propose a computational model of situated language comprehension based on the Indexical Hypothesis that generates meaning representations by translating amodal linguistic symbols to modal representations of beliefs, knowledge, and experience external to the linguistic system. This Indexical Model incorporates multiple information sources, including perceptions, domain knowledge, and short-term and long-term experiences during comprehension. We show that exploiting diverse information sources can alleviate ambiguities that arise from contextual use of underspecific referring expressions and unexpressed argument alternations of verbs. The model is being used to support linguistic interactions in Rosie, an agent implemented in Soar that learns from instruction.
Tasks
Published	2016-04-09
URL	http://arxiv.org/abs/1604.02509v1
PDF	http://arxiv.org/pdf/1604.02509v1.pdf
PWC	https://paperswithcode.com/paper/towards-an-indexical-model-of-situated
Repo
Framework

Symmetry-free SDP Relaxations for Affine Subspace Clustering


Title	Symmetry-free SDP Relaxations for Affine Subspace Clustering
Authors	Francesco Silvestri, Gerhard Reinelt, Christoph Schnörr
Abstract	We consider clustering problems where the goal is to determine an optimal partition of a given point set in Euclidean space in terms of a collection of affine subspaces. While there is vast literature on heuristics for this kind of problem, such approaches are known to be susceptible to poor initializations and getting trapped in bad local optima. We alleviate these issues by introducing a semidefinite relaxation based on Lasserre’s method of moments. While a similiar approach is known for classical Euclidean clustering problems, a generalization to our more general subspace scenario is not straightforward, due to the high symmetry of the objective function that weakens any convex relaxation. We therefore introduce a new mechanism for symmetry breaking based on covering the feasible region with polytopes. Additionally, we introduce and analyze a deterministic rounding heuristic.
Tasks
Published	2016-07-25
URL	http://arxiv.org/abs/1607.07387v1
PDF	http://arxiv.org/pdf/1607.07387v1.pdf
PWC	https://paperswithcode.com/paper/symmetry-free-sdp-relaxations-for-affine
Repo
Framework

Performance Analysis of the Gradient Comparator LMS Algorithm


Title	Performance Analysis of the Gradient Comparator LMS Algorithm
Authors	Bijit Kumar Das, Mrityunjoy Chakraborty
Abstract	The sparsity-aware zero attractor least mean square (ZA-LMS) algorithm manifests much lower misadjustment in strongly sparse environment than its sparsity-agnostic counterpart, the least mean square (LMS), but is shown to perform worse than the LMS when sparsity of the impulse response decreases. The reweighted variant of the ZA-LMS, namely RZA-LMS shows robustness against this variation in sparsity, but at the price of increased computational complexity. The other variants such as the l 0 -LMS and the improved proportionate normalized LMS (IPNLMS), though perform satisfactorily, are also computationally intensive. The gradient comparator LMS (GC-LMS) is a practical solution of this trade-off when hardware constraint is to be considered. In this paper, we analyse the mean and the mean square convergence performance of the GC-LMS algorithm in detail. The analyses satisfactorily match with the simulation results.
Tasks
Published	2016-05-10
URL	http://arxiv.org/abs/1605.02877v1
PDF	http://arxiv.org/pdf/1605.02877v1.pdf
PWC	https://paperswithcode.com/paper/performance-analysis-of-the-gradient
Repo
Framework

Long Short-Term Memory based Convolutional Recurrent Neural Networks for Large Vocabulary Speech Recognition


Title	Long Short-Term Memory based Convolutional Recurrent Neural Networks for Large Vocabulary Speech Recognition
Authors	Xiangang Li, Xihong Wu
Abstract	Long short-term memory (LSTM) recurrent neural networks (RNNs) have been shown to give state-of-the-art performance on many speech recognition tasks, as they are able to provide the learned dynamically changing contextual window of all sequence history. On the other hand, the convolutional neural networks (CNNs) have brought significant improvements to deep feed-forward neural networks (FFNNs), as they are able to better reduce spectral variation in the input signal. In this paper, a network architecture called as convolutional recurrent neural network (CRNN) is proposed by combining the CNN and LSTM RNN. In the proposed CRNNs, each speech frame, without adjacent context frames, is organized as a number of local feature patches along the frequency axis, and then a LSTM network is performed on each feature patch along the time axis. We train and compare FFNNs, LSTM RNNs and the proposed LSTM CRNNs at various number of configurations. Experimental results show that the LSTM CRNNs can exceed state-of-the-art speech recognition performance.
Tasks	Large Vocabulary Continuous Speech Recognition, Speech Recognition
Published	2016-10-11
URL	http://arxiv.org/abs/1610.03165v1
PDF	http://arxiv.org/pdf/1610.03165v1.pdf
PWC	https://paperswithcode.com/paper/long-short-term-memory-based-convolutional
Repo
Framework