May 5, 2019

2770 words 14 mins read

Paper Group ANR 464

Decision Theory in an Algebraic Setting. Stochastic Quasi-Newton Langevin Monte Carlo. Crowdsourced Outcome Determination in Prediction Markets. A Structured Variational Auto-encoder for Learning Deep Hierarchies of Sparse Features. Heter-LP: A heterogeneous label propagation algorithm and its application in drug repositioning. Ontology-Mediated Qu …

Decision Theory in an Algebraic Setting


Title	Decision Theory in an Algebraic Setting
Authors	Maurizio Negri
Abstract	In decision theory an act is a function from a set of conditions to the set of real numbers. The set of conditions is a partition in some algebra of events. The expected value of an act can be calculated when a probability measure is given. We adopt an algebraic point of view by substituting the algebra of events with a finite distributive lattice and the probability measure with a lattice valuation. We introduce a partial order on acts that generalizes the dominance relation and show that the set of acts is a lattice with respect to this order. Finally we analyze some different kinds of comparison between acts, without supposing a common set of conditions for the acts to be compared.
Tasks
Published	2016-12-02
URL	http://arxiv.org/abs/1612.02660v1
PDF	http://arxiv.org/pdf/1612.02660v1.pdf
PWC	https://paperswithcode.com/paper/decision-theory-in-an-algebraic-setting
Repo
Framework

Stochastic Quasi-Newton Langevin Monte Carlo


Title	Stochastic Quasi-Newton Langevin Monte Carlo
Authors	Umut Şimşekli, Roland Badeau, A. Taylan Cemgil, Gaël Richard
Abstract	Recently, Stochastic Gradient Markov Chain Monte Carlo (SG-MCMC) methods have been proposed for scaling up Monte Carlo computations to large data problems. Whilst these approaches have proven useful in many applications, vanilla SG-MCMC might suffer from poor mixing rates when random variables exhibit strong couplings under the target densities or big scale differences. In this study, we propose a novel SG-MCMC method that takes the local geometry into account by using ideas from Quasi-Newton optimization methods. These second order methods directly approximate the inverse Hessian by using a limited history of samples and their gradients. Our method uses dense approximations of the inverse Hessian while keeping the time and memory complexities linear with the dimension of the problem. We provide a formal theoretical analysis where we show that the proposed method is asymptotically unbiased and consistent with the posterior expectations. We illustrate the effectiveness of the approach on both synthetic and real datasets. Our experiments on two challenging applications show that our method achieves fast convergence rates similar to Riemannian approaches while at the same time having low computational requirements similar to diagonal preconditioning approaches.
Tasks
Published	2016-02-10
URL	http://arxiv.org/abs/1602.03442v2
PDF	http://arxiv.org/pdf/1602.03442v2.pdf
PWC	https://paperswithcode.com/paper/stochastic-quasi-newton-langevin-monte-carlo
Repo
Framework

Crowdsourced Outcome Determination in Prediction Markets


Title	Crowdsourced Outcome Determination in Prediction Markets
Authors	Rupert Freeman, Sebastien Lahaie, David M. Pennock
Abstract	A prediction market is a useful means of aggregating information about a future event. To function, the market needs a trusted entity who will verify the true outcome in the end. Motivated by the recent introduction of decentralized prediction markets, we introduce a mechanism that allows for the outcome to be determined by the votes of a group of arbiters who may themselves hold stakes in the market. Despite the potential conflict of interest, we derive conditions under which we can incentivize arbiters to vote truthfully by using funds raised from market fees to implement a peer prediction mechanism. Finally, we investigate what parameter values could be used in a real-world implementation of our mechanism.
Tasks
Published	2016-12-14
URL	http://arxiv.org/abs/1612.04885v1
PDF	http://arxiv.org/pdf/1612.04885v1.pdf
PWC	https://paperswithcode.com/paper/crowdsourced-outcome-determination-in
Repo
Framework

A Structured Variational Auto-encoder for Learning Deep Hierarchies of Sparse Features


Title	A Structured Variational Auto-encoder for Learning Deep Hierarchies of Sparse Features
Authors	Tim Salimans
Abstract	In this note we present a generative model of natural images consisting of a deep hierarchy of layers of latent random variables, each of which follows a new type of distribution that we call rectified Gaussian. These rectified Gaussian units allow spike-and-slab type sparsity, while retaining the differentiability necessary for efficient stochastic gradient variational inference. To learn the parameters of the new model, we approximate the posterior of the latent variables with a variational auto-encoder. Rather than making the usual mean-field assumption however, the encoder parameterizes a new type of structured variational approximation that retains the prior dependencies of the generative model. Using this structured posterior approximation, we are able to perform joint training of deep models with many layers of latent random variables, without having to resort to stacking or other layerwise training procedures.
Tasks
Published	2016-02-28
URL	http://arxiv.org/abs/1602.08734v1
PDF	http://arxiv.org/pdf/1602.08734v1.pdf
PWC	https://paperswithcode.com/paper/a-structured-variational-auto-encoder-for
Repo
Framework

Heter-LP: A heterogeneous label propagation algorithm and its application in drug repositioning


Title	Heter-LP: A heterogeneous label propagation algorithm and its application in drug repositioning
Authors	Maryam Lotfi Shahreza, Nasser Ghadiri, Seyed Rasul Mossavi, Jaleh Varshosaz, James Green
Abstract	Drug repositioning offers an effective solution to drug discovery, saving both time and resources by finding new indications for existing drugs. Typically, a drug takes effect via its protein targets in the cell. As a result, it is necessary for drug development studies to conduct an investigation into the interrelationships of drugs, protein targets, and diseases. Although previous studies have made a strong case for the effectiveness of integrative network-based methods for predicting these interrelationships, little progress has been achieved in this regard within drug repositioning research. Moreover, the interactions of new drugs and targets (lacking any known targets and drugs, respectively) cannot be accurately predicted by most established methods. In this paper, we propose a novel semi-supervised heterogeneous label propagation algorithm named Heter-LP, which applies both local as well as global network features for data integration. To predict drug-target, disease-target, and drug-disease associations, we use information about drugs, diseases, and targets as collected from multiple sources at different levels. Our algorithm integrates these various types of data into a heterogeneous network and implements a label propagation algorithm to find new interactions. Statistical analyses of 10-fold cross-validation results and experimental analysis support the effectiveness of the proposed algorithm.
Tasks	Drug Discovery
Published	2016-11-08
URL	http://arxiv.org/abs/1611.02945v1
PDF	http://arxiv.org/pdf/1611.02945v1.pdf
PWC	https://paperswithcode.com/paper/heter-lp-a-heterogeneous-label-propagation
Repo
Framework

Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity


Title	Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity
Authors	Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii, Michael Zakharyaschev
Abstract	We give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL: the succinctness problem for first-order rewritings of ontology-mediated queries (OMQs), and the complexity problem for OMQ answering. We classify OMQs according to the shape of their conjunctive queries (treewidth, the number of leaves) and the existential depth of their ontologies. For each of these classes, we determine the combined complexity of OMQ answering, and whether all OMQs in the class have polynomial-size first-order, positive existential, and nonrecursive datalog rewritings. We obtain the succinctness results using hypergraph programs, a new computational model for Boolean functions, which makes it possible to connect the size of OMQ rewritings and circuit complexity.
Tasks
Published	2016-05-04
URL	http://arxiv.org/abs/1605.01207v1
PDF	http://arxiv.org/pdf/1605.01207v1.pdf
PWC	https://paperswithcode.com/paper/ontology-mediated-queries-combined-complexity
Repo
Framework

An All-In-One Convolutional Neural Network for Face Analysis


Title	An All-In-One Convolutional Neural Network for Face Analysis
Authors	Rajeev Ranjan, Swami Sankaranarayanan, Carlos D. Castillo, Rama Chellappa
Abstract	We present a multi-purpose algorithm for simultaneous face detection, face alignment, pose estimation, gender recognition, smile detection, age estimation and face recognition using a single deep convolutional neural network (CNN). The proposed method employs a multi-task learning framework that regularizes the shared parameters of CNN and builds a synergy among different domains and tasks. Extensive experiments show that the network has a better understanding of face and achieves state-of-the-art result for most of these tasks.
Tasks	Age Estimation, Face Alignment, Face Detection, Face Recognition, Face Verification, Multi-Task Learning, Pose Estimation
Published	2016-11-03
URL	http://arxiv.org/abs/1611.00851v1
PDF	http://arxiv.org/pdf/1611.00851v1.pdf
PWC	https://paperswithcode.com/paper/an-all-in-one-convolutional-neural-network
Repo
Framework

Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation


Title	Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation
Authors	Jian Du, Shaodan Ma, Yik-Chung Wu, Soummya Kar, José M. F. Moura
Abstract	This paper considers inference over distributed linear Gaussian models using factor graphs and Gaussian belief propagation (BP). The distributed inference algorithm involves only local computation of the information matrix and of the mean vector, and message passing between neighbors. Under broad conditions, it is shown that the message information matrix converges to a unique positive definite limit matrix for arbitrary positive semidefinite initialization, and it approaches an arbitrarily small neighborhood of this limit matrix at a doubly exponential rate. A necessary and sufficient convergence condition for the belief mean vector to converge to the optimal centralized estimator is provided under the assumption that the message information matrix is initialized as a positive semidefinite matrix. Further, it is shown that Gaussian BP always converges when the underlying factor graph is given by the union of a forest and a single loop. The proposed convergence condition in the setup of distributed linear Gaussian models is shown to be strictly weaker than other existing convergence conditions and requirements, including the Gaussian Markov random field based walk-summability condition, and applicable to a large class of scenarios.
Tasks
Published	2016-11-07
URL	http://arxiv.org/abs/1611.02010v3
PDF	http://arxiv.org/pdf/1611.02010v3.pdf
PWC	https://paperswithcode.com/paper/convergence-analysis-of-distributed-inference
Repo
Framework

Multidimensional Dynamic Pricing for Welfare Maximization


Title	Multidimensional Dynamic Pricing for Welfare Maximization
Authors	Aaron Roth, Aleksandrs Slivkins, Jonathan Ullman, Zhiwei Steven Wu
Abstract	We study the problem of a seller dynamically pricing $d$ distinct types of indivisible goods, when faced with the online arrival of unit-demand buyers drawn independently from an unknown distribution. The goods are not in limited supply, but can only be produced at a limited rate and are costly to produce. The seller observes only the bundle of goods purchased at each day, but nothing else about the buyer’s valuation function. Our main result is a dynamic pricing algorithm for optimizing welfare (including the seller’s cost of production) that runs in time and a number of rounds that are polynomial in $d$ and the approximation parameter. We are able to do this despite the fact that (i) the price-response function is not continuous, and even its fractional relaxation is a non-concave function of the prices, and (ii) the welfare is not observable to the seller. We derive this result as an application of a general technique for optimizing welfare over \emph{divisible} goods, which is of independent interest. When buyers have strongly concave, H"older continuous valuation functions over $d$ divisible goods, we give a general polynomial time dynamic pricing technique. We are able to apply this technique to the setting of unit demand buyers despite the fact that in that setting the goods are not divisible, and the natural fractional relaxation of a unit demand valuation is not strongly concave. In order to apply our general technique, we introduce a novel price randomization procedure which has the effect of implicitly inducing buyers to “regularize” their valuations with a strongly concave function. Finally, we also extend our results to a limited-supply setting in which the number of copies of each good cannot be replenished.
Tasks
Published	2016-07-19
URL	http://arxiv.org/abs/1607.05397v3
PDF	http://arxiv.org/pdf/1607.05397v3.pdf
PWC	https://paperswithcode.com/paper/multidimensional-dynamic-pricing-for-welfare
Repo
Framework

Stationary signal processing on graphs


Title	Stationary signal processing on graphs
Authors	Nathanaël Perraudin, Pierre Vandergheynst
Abstract	Graphs are a central tool in machine learning and information processing as they allow to conveniently capture the structure of complex datasets. In this context, it is of high importance to develop flexible models of signals defined over graphs or networks. In this paper, we generalize the traditional concept of wide sense stationarity to signals defined over the vertices of arbitrary weighted undirected graphs. We show that stationarity is expressed through the graph localization operator reminiscent of translation. We prove that stationary graph signals are characterized by a well-defined Power Spectral Density that can be efficiently estimated even for large graphs. We leverage this new concept to derive Wiener-type estimation procedures of noisy and partially observed signals and illustrate the performance of this new model for denoising and regression.
Tasks	Denoising
Published	2016-01-11
URL	http://arxiv.org/abs/1601.02522v5
PDF	http://arxiv.org/pdf/1601.02522v5.pdf
PWC	https://paperswithcode.com/paper/stationary-signal-processing-on-graphs
Repo
Framework

Spectral Echolocation via the Wave Embedding


Title	Spectral Echolocation via the Wave Embedding
Authors	Alexander Cloninger, Stefan Steinerberger
Abstract	Spectral embedding uses eigenfunctions of the discrete Laplacian on a weighted graph to obtain coordinates for an embedding of an abstract data set into Euclidean space. We propose a new pre-processing step of first using the eigenfunctions to simulate a low-frequency wave moving over the data and using both position as well as change in time of the wave to obtain a refined metric to which classical methods of dimensionality reduction can then applied. This is motivated by the behavior of waves, symmetries of the wave equation and the hunting technique of bats. It is shown to be effective in practice and also works for other partial differential equations – the method yields improved results even for the classical heat equation.
Tasks	Dimensionality Reduction
Published	2016-07-15
URL	http://arxiv.org/abs/1607.04566v1
PDF	http://arxiv.org/pdf/1607.04566v1.pdf
PWC	https://paperswithcode.com/paper/spectral-echolocation-via-the-wave-embedding
Repo
Framework

A Sentence Compression Based Framework to Query-Focused Multi-Document Summarization


Title	A Sentence Compression Based Framework to Query-Focused Multi-Document Summarization
Authors	Lu Wang, Hema Raghavan, Vittorio Castelli, Radu Florian, Claire Cardie
Abstract	We consider the problem of using sentence compression techniques to facilitate query-focused multi-document summarization. We present a sentence-compression-based framework for the task, and design a series of learning-based compression models built on parse trees. An innovative beam search decoder is proposed to efficiently find highly probable compressions. Under this framework, we show how to integrate various indicative metrics such as linguistic motivation and query relevance into the compression process by deriving a novel formulation of a compression scoring function. Our best model achieves statistically significant improvement over the state-of-the-art systems on several metrics (e.g. 8.0% and 5.4% improvements in ROUGE-2 respectively) for the DUC 2006 and 2007 summarization task.
Tasks	Document Summarization, Multi-Document Summarization, Sentence Compression
Published	2016-06-24
URL	http://arxiv.org/abs/1606.07548v1
PDF	http://arxiv.org/pdf/1606.07548v1.pdf
PWC	https://paperswithcode.com/paper/a-sentence-compression-based-framework-to
Repo
Framework

Document Neural Autoregressive Distribution Estimation


Title	Document Neural Autoregressive Distribution Estimation
Authors	Stanislas Lauly, Yin Zheng, Alexandre Allauzen, Hugo Larochelle
Abstract	We present an approach based on feed-forward neural networks for learning the distribution of textual documents. This approach is inspired by the Neural Autoregressive Distribution Estimator(NADE) model, which has been shown to be a good estimator of the distribution of discrete-valued igh-dimensional vectors. In this paper, we present how NADE can successfully be adapted to the case of textual data, retaining from NADE the property that sampling or computing the probability of observations can be done exactly and efficiently. The approach can also be used to learn deep representations of documents that are competitive to those learned by the alternative topic modeling approaches. Finally, we describe how the approach can be combined with a regular neural network N-gram model and substantially improve its performance, by making its learned representation sensitive to the larger, document-specific context.
Tasks
Published	2016-03-18
URL	http://arxiv.org/abs/1603.05962v1
PDF	http://arxiv.org/pdf/1603.05962v1.pdf
PWC	https://paperswithcode.com/paper/document-neural-autoregressive-distribution
Repo
Framework

Spatio-temporal Dynamics of Intrinsic Networks in Functional Magnetic Imaging Data Using Recurrent Neural Networks


Title	Spatio-temporal Dynamics of Intrinsic Networks in Functional Magnetic Imaging Data Using Recurrent Neural Networks
Authors	R Devon Hjelm, Eswar Damaraju, Kyunghyun Cho, Helmut Laufs, Sergey M. Plis, Vince Calhoun
Abstract	We introduce a novel recurrent neural network (RNN) approach to account for temporal dynamics and dependencies in brain networks observed via functional magnetic resonance imaging (fMRI). Our approach directly parameterizes temporal dynamics through recurrent connections, which can be used to formulate blind source separation with a conditional (rather than marginal) independence assumption, which we call RNN-ICA. This formulation enables us to visualize the temporal dynamics of both first order (activity) and second order (directed connectivity) information in brain networks that are widely studied in a static sense, but not well-characterized dynamically. RNN-ICA predicts dynamics directly from the recurrent states of the RNN in both task and resting state fMRI. Our results show both task-related and group-differentiating directed connectivity.
Tasks
Published	2016-11-03
URL	http://arxiv.org/abs/1611.00864v2
PDF	http://arxiv.org/pdf/1611.00864v2.pdf
PWC	https://paperswithcode.com/paper/spatio-temporal-dynamics-of-intrinsic
Repo
Framework

Recommender Engine for Continuous Time Quantum Monte Carlo Methods


Title	Recommender Engine for Continuous Time Quantum Monte Carlo Methods
Authors	Li Huang, Yi-feng Yang, Lei Wang
Abstract	Recommender systems play an essential role in the modern business world. They recommend favorable items like books, movies, and search queries to users based on their past preferences. Applying similar ideas and techniques to Monte Carlo simulations of physical systems boosts their efficiency without sacrificing accuracy. Exploiting the quantum to classical mapping inherent in the continuous-time quantum Monte Carlo methods, we construct a classical molecular gas model to reproduce the quantum distributions. We then utilize powerful molecular simulation techniques to propose efficient quantum Monte Carlo updates. The recommender engine approach provides a general way to speed up the quantum impurity solvers.
Tasks	Recommendation Systems
Published	2016-12-06
URL	http://arxiv.org/abs/1612.01871v1
PDF	http://arxiv.org/pdf/1612.01871v1.pdf
PWC	https://paperswithcode.com/paper/recommender-engine-for-continuous-time
Repo
Framework