Paper Group ANR 258
Combating Reinforcement Learning’s Sisyphean Curse with Intrinsic Fear. Proceedings of the 2016 ICML Workshop on Human Interpretability in Machine Learning (WHI 2016). A New Approach to Laplacian Solvers and Flow Problems. Fast robustness quantification with variational Bayes. Reconciling Lambek’s restriction, cut-elimination, and substitution in t …
Combating Reinforcement Learning’s Sisyphean Curse with Intrinsic Fear
| Title | Combating Reinforcement Learning’s Sisyphean Curse with Intrinsic Fear |
| Authors | Zachary C. Lipton, Kamyar Azizzadenesheli, Abhishek Kumar, Lihong Li, Jianfeng Gao, Li Deng |
| Abstract | Many practical environments contain catastrophic states that an optimal agent would visit infrequently or never. Even on toy problems, Deep Reinforcement Learning (DRL) agents tend to periodically revisit these states upon forgetting their existence under a new policy. We introduce intrinsic fear (IF), a learned reward shaping that guards DRL agents against periodic catastrophes. IF agents possess a fear model trained to predict the probability of imminent catastrophe. This score is then used to penalize the Q-learning objective. Our theoretical analysis bounds the reduction in average return due to learning on the perturbed objective. We also prove robustness to classification errors. As a bonus, IF models tend to learn faster, owing to reward shaping. Experiments demonstrate that intrinsic-fear DQNs solve otherwise pathological environments and improve on several Atari games. |
| Tasks | Atari Games, Q-Learning |
| Published | 2016-11-03 |
| URL | http://arxiv.org/abs/1611.01211v8 |
| http://arxiv.org/pdf/1611.01211v8.pdf | |
| PWC | https://paperswithcode.com/paper/combating-reinforcement-learnings-sisyphean |
| Repo | |
| Framework | |
Proceedings of the 2016 ICML Workshop on Human Interpretability in Machine Learning (WHI 2016)
| Title | Proceedings of the 2016 ICML Workshop on Human Interpretability in Machine Learning (WHI 2016) |
| Authors | Been Kim, Dmitry M. Malioutov, Kush R. Varshney |
| Abstract | This is the Proceedings of the 2016 ICML Workshop on Human Interpretability in Machine Learning (WHI 2016), which was held in New York, NY, June 23, 2016. Invited speakers were Susan Athey, Rich Caruana, Jacob Feldman, Percy Liang, and Hanna Wallach. |
| Tasks | |
| Published | 2016-07-08 |
| URL | http://arxiv.org/abs/1607.02531v2 |
| http://arxiv.org/pdf/1607.02531v2.pdf | |
| PWC | https://paperswithcode.com/paper/proceedings-of-the-2016-icml-workshop-on |
| Repo | |
| Framework | |
A New Approach to Laplacian Solvers and Flow Problems
| Title | A New Approach to Laplacian Solvers and Flow Problems |
| Authors | Patrick Rebeschini, Sekhar Tatikonda |
| Abstract | This paper investigates the behavior of the Min-Sum message passing scheme to solve systems of linear equations in the Laplacian matrices of graphs and to compute electric flows. Voltage and flow problems involve the minimization of quadratic functions and are fundamental primitives that arise in several domains. Algorithms that have been proposed are typically centralized and involve multiple graph-theoretic constructions or sampling mechanisms that make them difficult to implement and analyze. On the other hand, message passing routines are distributed, simple, and easy to implement. In this paper we establish a framework to analyze Min-Sum to solve voltage and flow problems. We characterize the error committed by the algorithm on general weighted graphs in terms of hitting times of random walks defined on the computation trees that support the operations of the algorithms with time. For $d$-regular graphs with equal weights, we show that the convergence of the algorithms is controlled by the total variation distance between the distributions of non-backtracking random walks defined on the original graph that start from neighboring nodes. The framework that we introduce extends the analysis of Min-Sum to settings where the contraction arguments previously considered in the literature (based on the assumption of walk summability or scaled diagonal dominance) can not be used, possibly in the presence of constraints. |
| Tasks | |
| Published | 2016-11-22 |
| URL | http://arxiv.org/abs/1611.07138v2 |
| http://arxiv.org/pdf/1611.07138v2.pdf | |
| PWC | https://paperswithcode.com/paper/a-new-approach-to-laplacian-solvers-and-flow |
| Repo | |
| Framework | |
Fast robustness quantification with variational Bayes
| Title | Fast robustness quantification with variational Bayes |
| Authors | Ryan Giordano, Tamara Broderick, Rachael Meager, Jonathan Huggins, Michael Jordan |
| Abstract | Bayesian hierarchical models are increasing popular in economics. When using hierarchical models, it is useful not only to calculate posterior expectations, but also to measure the robustness of these expectations to reasonable alternative prior choices. We use variational Bayes and linear response methods to provide fast, accurate posterior means and robustness measures with an application to measuring the effectiveness of microcredit in the developing world. |
| Tasks | |
| Published | 2016-06-23 |
| URL | http://arxiv.org/abs/1606.07153v1 |
| http://arxiv.org/pdf/1606.07153v1.pdf | |
| PWC | https://paperswithcode.com/paper/fast-robustness-quantification-with |
| Repo | |
| Framework | |
Reconciling Lambek’s restriction, cut-elimination, and substitution in the presence of exponential modalities
| Title | Reconciling Lambek’s restriction, cut-elimination, and substitution in the presence of exponential modalities |
| Authors | Max Kanovich, Stepan Kuznetsov, Andre Scedrov |
| Abstract | The Lambek calculus can be considered as a version of non-commutative intuitionistic linear logic. One of the interesting features of the Lambek calculus is the so-called “Lambek’s restriction,” that is, the antecedent of any provable sequent should be non-empty. In this paper we discuss ways of extending the Lambek calculus with the linear logic exponential modality while keeping Lambek’s restriction. Interestingly enough, we show that for any system equipped with a reasonable exponential modality the following holds: if the system enjoys cut elimination and substitution to the full extent, then the system necessarily violates Lambek’s restriction. Nevertheless, we show that two of the three conditions can be implemented. Namely, we design a system with Lambek’s restriction and cut elimination and another system with Lambek’s restriction and substitution. For both calculi we prove that they are undecidable, even if we take only one of the two divisions provided by the Lambek calculus. The system with cut elimination and substitution and without Lambek’s restriction is folklore and known to be undecidable. |
| Tasks | |
| Published | 2016-08-07 |
| URL | https://arxiv.org/abs/1608.02254v2 |
| https://arxiv.org/pdf/1608.02254v2.pdf | |
| PWC | https://paperswithcode.com/paper/reconciling-lambeks-restriction-cut |
| Repo | |
| Framework | |
Extracting Predictive Information from Heterogeneous Data Streams using Gaussian Processes
| Title | Extracting Predictive Information from Heterogeneous Data Streams using Gaussian Processes |
| Authors | Sid Ghoshal, Stephen Roberts |
| Abstract | Financial markets are notoriously complex environments, presenting vast amounts of noisy, yet potentially informative data. We consider the problem of forecasting financial time series from a wide range of information sources using online Gaussian Processes with Automatic Relevance Determination (ARD) kernels. We measure the performance gain, quantified in terms of Normalised Root Mean Square Error (NRMSE), Median Absolute Deviation (MAD) and Pearson correlation, from fusing each of four separate data domains: time series technicals, sentiment analysis, options market data and broker recommendations. We show evidence that ARD kernels produce meaningful feature rankings that help retain salient inputs and reduce input dimensionality, providing a framework for sifting through financial complexity. We measure the performance gain from fusing each domain’s heterogeneous data streams into a single probabilistic model. In particular our findings highlight the critical value of options data in mapping out the curvature of price space and inspire an intuitive, novel direction for research in financial prediction. |
| Tasks | Gaussian Processes, Sentiment Analysis, Time Series |
| Published | 2016-03-20 |
| URL | http://arxiv.org/abs/1603.06202v2 |
| http://arxiv.org/pdf/1603.06202v2.pdf | |
| PWC | https://paperswithcode.com/paper/extracting-predictive-information-from |
| Repo | |
| Framework | |
Stance and Sentiment in Tweets
| Title | Stance and Sentiment in Tweets |
| Authors | Saif M. Mohammad, Parinaz Sobhani, Svetlana Kiritchenko |
| Abstract | We can often detect from a person’s utterances whether he/she is in favor of or against a given target entity – their stance towards the target. However, a person may express the same stance towards a target by using negative or positive language. Here for the first time we present a dataset of tweet–target pairs annotated for both stance and sentiment. The targets may or may not be referred to in the tweets, and they may or may not be the target of opinion in the tweets. Partitions of this dataset were used as training and test sets in a SemEval-2016 shared task competition. We propose a simple stance detection system that outperforms submissions from all 19 teams that participated in the shared task. Additionally, access to both stance and sentiment annotations allows us to explore several research questions. We show that while knowing the sentiment expressed by a tweet is beneficial for stance classification, it alone is not sufficient. Finally, we use additional unlabeled data through distant supervision techniques and word embeddings to further improve stance classification. |
| Tasks | Stance Detection, Word Embeddings |
| Published | 2016-05-05 |
| URL | http://arxiv.org/abs/1605.01655v1 |
| http://arxiv.org/pdf/1605.01655v1.pdf | |
| PWC | https://paperswithcode.com/paper/stance-and-sentiment-in-tweets |
| Repo | |
| Framework | |
Distributed stochastic optimization via matrix exponential learning
| Title | Distributed stochastic optimization via matrix exponential learning |
| Authors | Panayotis Mertikopoulos, E. Veronica Belmega, Romain Negrel, Luca Sanguinetti |
| Abstract | In this paper, we investigate a distributed learning scheme for a broad class of stochastic optimization problems and games that arise in signal processing and wireless communications. The proposed algorithm relies on the method of matrix exponential learning (MXL) and only requires locally computable gradient observations that are possibly imperfect and/or obsolete. To analyze it, we introduce the notion of a stable Nash equilibrium and we show that the algorithm is globally convergent to such equilibria - or locally convergent when an equilibrium is only locally stable. We also derive an explicit linear bound for the algorithm’s convergence speed, which remains valid under measurement errors and uncertainty of arbitrarily high variance. To validate our theoretical analysis, we test the algorithm in realistic multi-carrier/multiple-antenna wireless scenarios where several users seek to maximize their energy efficiency. Our results show that learning allows users to attain a net increase between 100% and 500% in energy efficiency, even under very high uncertainty. |
| Tasks | Stochastic Optimization |
| Published | 2016-06-03 |
| URL | http://arxiv.org/abs/1606.01190v1 |
| http://arxiv.org/pdf/1606.01190v1.pdf | |
| PWC | https://paperswithcode.com/paper/distributed-stochastic-optimization-via |
| Repo | |
| Framework | |
Modeling Rich Contexts for Sentiment Classification with LSTM
| Title | Modeling Rich Contexts for Sentiment Classification with LSTM |
| Authors | Minlie Huang, Yujie Cao, Chao Dong |
| Abstract | Sentiment analysis on social media data such as tweets and weibo has become a very important and challenging task. Due to the intrinsic properties of such data, tweets are short, noisy, and of divergent topics, and sentiment classification on these data requires to modeling various contexts such as the retweet/reply history of a tweet, and the social context about authors and relationships. While few prior study has approached the issue of modeling contexts in tweet, this paper proposes to use a hierarchical LSTM to model rich contexts in tweet, particularly long-range context. Experimental results show that contexts can help us to perform sentiment classification remarkably better. |
| Tasks | Sentiment Analysis |
| Published | 2016-05-05 |
| URL | http://arxiv.org/abs/1605.01478v1 |
| http://arxiv.org/pdf/1605.01478v1.pdf | |
| PWC | https://paperswithcode.com/paper/modeling-rich-contexts-for-sentiment |
| Repo | |
| Framework | |
Geometric Dirichlet Means algorithm for topic inference
| Title | Geometric Dirichlet Means algorithm for topic inference |
| Authors | Mikhail Yurochkin, XuanLong Nguyen |
| Abstract | We propose a geometric algorithm for topic learning and inference that is built on the convex geometry of topics arising from the Latent Dirichlet Allocation (LDA) model and its nonparametric extensions. To this end we study the optimization of a geometric loss function, which is a surrogate to the LDA’s likelihood. Our method involves a fast optimization based weighted clustering procedure augmented with geometric corrections, which overcomes the computational and statistical inefficiencies encountered by other techniques based on Gibbs sampling and variational inference, while achieving the accuracy comparable to that of a Gibbs sampler. The topic estimates produced by our method are shown to be statistically consistent under some conditions. The algorithm is evaluated with extensive experiments on simulated and real data. |
| Tasks | |
| Published | 2016-10-27 |
| URL | http://arxiv.org/abs/1610.09034v1 |
| http://arxiv.org/pdf/1610.09034v1.pdf | |
| PWC | https://paperswithcode.com/paper/geometric-dirichlet-means-algorithm-for-topic |
| Repo | |
| Framework | |
Hierarchical Piecewise-Constant Super-regions
| Title | Hierarchical Piecewise-Constant Super-regions |
| Authors | Imanol Luengo, Mark Basham, Andrew P. French |
| Abstract | Recent applications in computer vision have come to heavily rely on superpixel over-segmentation as a pre-processing step for higher level vision tasks, such as object recognition, image labelling or image segmentation. Here we present a new superpixel algorithm called Hierarchical Piecewise-Constant Super-regions (HPCS), which not only obtains superpixels comparable to the state-of-the-art, but can also be applied hierarchically to form what we call n-th order super-regions. In essence, a Markov Random Field (MRF)-based anisotropic denoising formulation over the quantized feature space is adopted to form piecewise-constant image regions, which are then combined with a graph-based split & merge post-processing step to form superpixels. The graph and quantized feature based formulation of the problem allows us to generalize it hierarchically to preserve boundary adherence with fewer superpixels. Experimental results show that, despite the simplicity of our framework, it is able to provide high quality superpixels, and to hierarchically apply them to form layers of over-segmentation, each with a decreasing number of superpixels, while maintaining the same desired properties (such as adherence to strong image edges). The algorithm is also memory efficient and has a low computational cost. |
| Tasks | Denoising, Object Recognition, Semantic Segmentation |
| Published | 2016-05-19 |
| URL | http://arxiv.org/abs/1605.05937v1 |
| http://arxiv.org/pdf/1605.05937v1.pdf | |
| PWC | https://paperswithcode.com/paper/hierarchical-piecewise-constant-super-regions |
| Repo | |
| Framework | |
Predicting and Understanding Law-Making with Word Vectors and an Ensemble Model
| Title | Predicting and Understanding Law-Making with Word Vectors and an Ensemble Model |
| Authors | John J. Nay |
| Abstract | Out of nearly 70,000 bills introduced in the U.S. Congress from 2001 to 2015, only 2,513 were enacted. We developed a machine learning approach to forecasting the probability that any bill will become law. Starting in 2001 with the 107th Congress, we trained models on data from previous Congresses, predicted all bills in the current Congress, and repeated until the 113th Congress served as the test. For prediction we scored each sentence of a bill with a language model that embeds legislative vocabulary into a high-dimensional, semantic-laden vector space. This language representation enables our investigation into which words increase the probability of enactment for any topic. To test the relative importance of text and context, we compared the text model to a context-only model that uses variables such as whether the bill’s sponsor is in the majority party. To test the effect of changes to bills after their introduction on our ability to predict their final outcome, we compared using the bill text and meta-data available at the time of introduction with using the most recent data. At the time of introduction context-only predictions outperform text-only, and with the newest data text-only outperforms context-only. Combining text and context always performs best. We conducted a global sensitivity analysis on the combined model to determine important variables predicting enactment. |
| Tasks | Language Modelling |
| Published | 2016-07-07 |
| URL | http://arxiv.org/abs/1607.02109v2 |
| http://arxiv.org/pdf/1607.02109v2.pdf | |
| PWC | https://paperswithcode.com/paper/predicting-and-understanding-law-making-with |
| Repo | |
| Framework | |
Incorporating Pass-Phrase Dependent Background Models for Text-Dependent Speaker Verification
| Title | Incorporating Pass-Phrase Dependent Background Models for Text-Dependent Speaker Verification |
| Authors | A. K. Sarkar, Zheng-Hua Tan |
| Abstract | In this paper, we propose pass-phrase dependent background models (PBMs) for text-dependent (TD) speaker verification (SV) to integrate the pass-phrase identification process into the conventional TD-SV system, where a PBM is derived from a text-independent background model through adaptation using the utterances of a particular pass-phrase. During training, pass-phrase specific target speaker models are derived from the particular PBM using the training data for the respective target model. While testing, the best PBM is first selected for the test utterance in the maximum likelihood (ML) sense and the selected PBM is then used for the log likelihood ratio (LLR) calculation with respect to the claimant model. The proposed method incorporates the pass-phrase identification step in the LLR calculation, which is not considered in conventional standalone TD-SV systems. The performance of the proposed method is compared to conventional text-independent background model based TD-SV systems using either Gaussian mixture model (GMM)-universal background model (UBM) or Hidden Markov model (HMM)-UBM or i-vector paradigms. In addition, we consider two approaches to build PBMs: speaker-independent and speaker-dependent. We show that the proposed method significantly reduces the error rates of text-dependent speaker verification for the non-target types: target-wrong and imposter-wrong while it maintains comparable TD-SV performance when imposters speak a correct utterance with respect to the conventional system. Experiments are conducted on the RedDots challenge and the RSR2015 databases that consist of short utterances. |
| Tasks | Speaker Verification, Text-Dependent Speaker Verification |
| Published | 2016-11-19 |
| URL | http://arxiv.org/abs/1611.06423v2 |
| http://arxiv.org/pdf/1611.06423v2.pdf | |
| PWC | https://paperswithcode.com/paper/incorporating-pass-phrase-dependent |
| Repo | |
| Framework | |
Parallel SGD: When does averaging help?
| Title | Parallel SGD: When does averaging help? |
| Authors | Jian Zhang, Christopher De Sa, Ioannis Mitliagkas, Christopher Ré |
| Abstract | Consider a number of workers running SGD independently on the same pool of data and averaging the models every once in a while – a common but not well understood practice. We study model averaging as a variance-reducing mechanism and describe two ways in which the frequency of averaging affects convergence. For convex objectives, we show the benefit of frequent averaging depends on the gradient variance envelope. For non-convex objectives, we illustrate that this benefit depends on the presence of multiple globally optimal points. We complement our findings with multicore experiments on both synthetic and real data. |
| Tasks | |
| Published | 2016-06-23 |
| URL | http://arxiv.org/abs/1606.07365v1 |
| http://arxiv.org/pdf/1606.07365v1.pdf | |
| PWC | https://paperswithcode.com/paper/parallel-sgd-when-does-averaging-help |
| Repo | |
| Framework | |
Detecting Unusual Input-Output Associations in Multivariate Conditional Data
| Title | Detecting Unusual Input-Output Associations in Multivariate Conditional Data |
| Authors | Charmgil Hong, Milos Hauskrecht |
| Abstract | Despite tremendous progress in outlier detection research in recent years, the majority of existing methods are designed only to detect unconditional outliers that correspond to unusual data patterns expressed in the joint space of all data attributes. Such methods are not applicable when we seek to detect conditional outliers that reflect unusual responses associated with a given context or condition. This work focuses on multivariate conditional outlier detection, a special type of the conditional outlier detection problem, where data instances consist of multi-dimensional input (context) and output (responses) pairs. We present a novel outlier detection framework that identifies abnormal input-output associations in data with the help of a decomposable conditional probabilistic model that is learned from all data instances. Since components of this model can vary in their quality, we combine them with the help of weights reflecting their reliability in assessment of outliers. We study two ways of calculating the component weights: global that relies on all data, and local that relies only on instances similar to the target instance. Experimental results on data from various domains demonstrate the ability of our framework to successfully identify multivariate conditional outliers. |
| Tasks | Outlier Detection |
| Published | 2016-12-21 |
| URL | http://arxiv.org/abs/1612.07374v1 |
| http://arxiv.org/pdf/1612.07374v1.pdf | |
| PWC | https://paperswithcode.com/paper/detecting-unusual-input-output-associations |
| Repo | |
| Framework | |
