Paper Group ANR 143
The Complexity of Bayesian Networks Specified by Propositional and Relational Languages. Engineering Safety in Machine Learning. Accelerated Gradient Temporal Difference Learning. Poisson Random Fields for Dynamic Feature Models. Hitting times of local and global optima in genetic algorithms with very high selection pressure. Recovering Multiple No …
The Complexity of Bayesian Networks Specified by Propositional and Relational Languages
| Title | The Complexity of Bayesian Networks Specified by Propositional and Relational Languages |
| Authors | Fabio Gagliardi Cozman, Denis Deratani Mauá |
| Abstract | We examine the complexity of inference in Bayesian networks specified by logical languages. We consider representations that range from fragments of propositional logic to function-free first-order logic with equality; in doing so we cover a variety of plate models and of probabilistic relational models. We study the complexity of inferences when network, query and domain are the input (the inferential and the combined complexity), when the network is fixed and query and domain are the input (the query/data complexity), and when the network and query are fixed and the domain is the input (the domain complexity). We draw connections with probabilistic databases and liftability results, and obtain complexity classes that range from polynomial to exponential levels. |
| Tasks | |
| Published | 2016-12-04 |
| URL | http://arxiv.org/abs/1612.01120v3 |
| http://arxiv.org/pdf/1612.01120v3.pdf | |
| PWC | https://paperswithcode.com/paper/the-complexity-of-bayesian-networks-specified |
| Repo | |
| Framework | |
Engineering Safety in Machine Learning
| Title | Engineering Safety in Machine Learning |
| Authors | Kush R. Varshney |
| Abstract | Machine learning algorithms are increasingly influencing our decisions and interacting with us in all parts of our daily lives. Therefore, just like for power plants, highways, and myriad other engineered sociotechnical systems, we must consider the safety of systems involving machine learning. In this paper, we first discuss the definition of safety in terms of risk, epistemic uncertainty, and the harm incurred by unwanted outcomes. Then we examine dimensions, such as the choice of cost function and the appropriateness of minimizing the empirical average training cost, along which certain real-world applications may not be completely amenable to the foundational principle of modern statistical machine learning: empirical risk minimization. In particular, we note an emerging dichotomy of applications: ones in which safety is important and risk minimization is not the complete story (we name these Type A applications), and ones in which safety is not so critical and risk minimization is sufficient (we name these Type B applications). Finally, we discuss how four different strategies for achieving safety in engineering (inherently safe design, safety reserves, safe fail, and procedural safeguards) can be mapped to the machine learning context through interpretability and causality of predictive models, objectives beyond expected prediction accuracy, human involvement for labeling difficult or rare examples, and user experience design of software. |
| Tasks | |
| Published | 2016-01-16 |
| URL | http://arxiv.org/abs/1601.04126v1 |
| http://arxiv.org/pdf/1601.04126v1.pdf | |
| PWC | https://paperswithcode.com/paper/engineering-safety-in-machine-learning |
| Repo | |
| Framework | |
Accelerated Gradient Temporal Difference Learning
| Title | Accelerated Gradient Temporal Difference Learning |
| Authors | Yangchen Pan, Adam White, Martha White |
| Abstract | The family of temporal difference (TD) methods span a spectrum from computationally frugal linear methods like TD({\lambda}) to data efficient least squares methods. Least square methods make the best use of available data directly computing the TD solution and thus do not require tuning a typically highly sensitive learning rate parameter, but require quadratic computation and storage. Recent algorithmic developments have yielded several sub-quadratic methods that use an approximation to the least squares TD solution, but incur bias. In this paper, we propose a new family of accelerated gradient TD (ATD) methods that (1) provide similar data efficiency benefits to least-squares methods, at a fraction of the computation and storage (2) significantly reduce parameter sensitivity compared to linear TD methods, and (3) are asymptotically unbiased. We illustrate these claims with a proof of convergence in expectation and experiments on several benchmark domains and a large-scale industrial energy allocation domain. |
| Tasks | |
| Published | 2016-11-28 |
| URL | http://arxiv.org/abs/1611.09328v2 |
| http://arxiv.org/pdf/1611.09328v2.pdf | |
| PWC | https://paperswithcode.com/paper/accelerated-gradient-temporal-difference |
| Repo | |
| Framework | |
Poisson Random Fields for Dynamic Feature Models
| Title | Poisson Random Fields for Dynamic Feature Models |
| Authors | Valerio Perrone, Paul A. Jenkins, Dario Spano, Yee Whye Teh |
| Abstract | We present the Wright-Fisher Indian buffet process (WF-IBP), a probabilistic model for time-dependent data assumed to have been generated by an unknown number of latent features. This model is suitable as a prior in Bayesian nonparametric feature allocation models in which the features underlying the observed data exhibit a dependency structure over time. More specifically, we establish a new framework for generating dependent Indian buffet processes, where the Poisson random field model from population genetics is used as a way of constructing dependent beta processes. Inference in the model is complex, and we describe a sophisticated Markov Chain Monte Carlo algorithm for exact posterior simulation. We apply our construction to develop a nonparametric focused topic model for collections of time-stamped text documents and test it on the full corpus of NIPS papers published from 1987 to 2015. |
| Tasks | |
| Published | 2016-11-22 |
| URL | http://arxiv.org/abs/1611.07460v1 |
| http://arxiv.org/pdf/1611.07460v1.pdf | |
| PWC | https://paperswithcode.com/paper/poisson-random-fields-for-dynamic-feature |
| Repo | |
| Framework | |
Hitting times of local and global optima in genetic algorithms with very high selection pressure
| Title | Hitting times of local and global optima in genetic algorithms with very high selection pressure |
| Authors | Anton Eremeev |
| Abstract | The paper is devoted to upper bounds on the expected first hitting times of the sets of local or global optima for non-elitist genetic algorithms with very high selection pressure. The results of this paper extend the range of situations where the upper bounds on the expected runtime are known for genetic algorithms and apply, in particular, to the Canonical Genetic Algorithm. The obtained bounds do not require the probability of fitness-decreasing mutation to be bounded by a constant less than one. |
| Tasks | |
| Published | 2016-06-18 |
| URL | http://arxiv.org/abs/1606.05784v2 |
| http://arxiv.org/pdf/1606.05784v2.pdf | |
| PWC | https://paperswithcode.com/paper/hitting-times-of-local-and-global-optima-in |
| Repo | |
| Framework | |
Recovering Multiple Nonnegative Time Series From a Few Temporal Aggregates
| Title | Recovering Multiple Nonnegative Time Series From a Few Temporal Aggregates |
| Authors | Jiali Mei, Yohann De Castro, Yannig Goude, Georges Hébrail |
| Abstract | Motivated by electricity consumption metering, we extend existing nonnegative matrix factorization (NMF) algorithms to use linear measurements as observations, instead of matrix entries. The objective is to estimate multiple time series at a fine temporal scale from temporal aggregates measured on each individual series. Furthermore, our algorithm is extended to take into account individual autocorrelation to provide better estimation, using a recent convex relaxation of quadratically constrained quadratic program. Extensive experiments on synthetic and real-world electricity consumption datasets illustrate the effectiveness of our matrix recovery algorithms. |
| Tasks | Time Series |
| Published | 2016-10-05 |
| URL | http://arxiv.org/abs/1610.01492v1 |
| http://arxiv.org/pdf/1610.01492v1.pdf | |
| PWC | https://paperswithcode.com/paper/recovering-multiple-nonnegative-time-series |
| Repo | |
| Framework | |
Scene Parsing with Integration of Parametric and Non-parametric Models
| Title | Scene Parsing with Integration of Parametric and Non-parametric Models |
| Authors | Bing Shuai, Zhen Zuo, Gang Wang, Bing Wang |
| Abstract | We adopt Convolutional Neural Networks (CNNs) to be our parametric model to learn discriminative features and classifiers for local patch classification. Based on the occurrence frequency distribution of classes, an ensemble of CNNs (CNN-Ensemble) are learned, in which each CNN component focuses on learning different and complementary visual patterns. The local beliefs of pixels are output by CNN-Ensemble. Considering that visually similar pixels are indistinguishable under local context, we leverage the global scene semantics to alleviate the local ambiguity. The global scene constraint is mathematically achieved by adding a global energy term to the labeling energy function, and it is practically estimated in a non-parametric framework. A large margin based CNN metric learning method is also proposed for better global belief estimation. In the end, the integration of local and global beliefs gives rise to the class likelihood of pixels, based on which maximum marginal inference is performed to generate the label prediction maps. Even without any post-processing, we achieve state-of-the-art results on the challenging SiftFlow and Barcelona benchmarks. |
| Tasks | Metric Learning, Scene Parsing |
| Published | 2016-04-20 |
| URL | http://arxiv.org/abs/1604.05848v1 |
| http://arxiv.org/pdf/1604.05848v1.pdf | |
| PWC | https://paperswithcode.com/paper/scene-parsing-with-integration-of-parametric |
| Repo | |
| Framework | |
Temporal Topic Modeling to Assess Associations between News Trends and Infectious Disease Outbreaks
| Title | Temporal Topic Modeling to Assess Associations between News Trends and Infectious Disease Outbreaks |
| Authors | Saurav Ghosh, Prithwish Chakraborty, Elaine O. Nsoesie, Emily Cohn, Sumiko R. Mekaru, John S. Brownstein, Naren Ramakrishnan |
| Abstract | In retrospective assessments, internet news reports have been shown to capture early reports of unknown infectious disease transmission prior to official laboratory confirmation. In general, media interest and reporting peaks and wanes during the course of an outbreak. In this study, we quantify the extent to which media interest during infectious disease outbreaks is indicative of trends of reported incidence. We introduce an approach that uses supervised temporal topic models to transform large corpora of news articles into temporal topic trends. The key advantages of this approach include, applicability to a wide range of diseases, and ability to capture disease dynamics - including seasonality, abrupt peaks and troughs. We evaluated the method using data from multiple infectious disease outbreaks reported in the United States of America (U.S.), China and India. We noted that temporal topic trends extracted from disease-related news reports successfully captured the dynamics of multiple outbreaks such as whooping cough in U.S. (2012), dengue outbreaks in India (2013) and China (2014). Our observations also suggest that efficient modeling of temporal topic trends using time-series regression techniques can estimate disease case counts with increased precision before official reports by health organizations. |
| Tasks | Time Series, Topic Models |
| Published | 2016-06-01 |
| URL | http://arxiv.org/abs/1606.00411v1 |
| http://arxiv.org/pdf/1606.00411v1.pdf | |
| PWC | https://paperswithcode.com/paper/temporal-topic-modeling-to-assess |
| Repo | |
| Framework | |
Automatic Knowledge Base Evolution by Learning Instances
| Title | Automatic Knowledge Base Evolution by Learning Instances |
| Authors | Sundong Kim |
| Abstract | Knowledge base is the way to store structured and unstructured data throughout the web. Since the size of the web is increasing rapidly, there are huge needs to structure the knowledge in a fully automated way. However fully-automated knowledge-base evolution on the Semantic Web is a major challenges, although there are many ontology evolution techniques available. Therefore learning ontology automatically can contribute to the semantic web society significantly. In this paper, we propose full-automated ontology learning algorithm to generate refined knowledge base from incomplete knowledge base and rdf-triples. Our algorithm is data-driven approach which is based on the property of each instance. Ontology class is being elaborated by generalizing frequent property of its instances. By using that developed class information, each instance can find its most relatively matching class. By repeating these two steps, we achieve fully-automated ontology evolution from incomplete basic knowledge base. |
| Tasks | |
| Published | 2016-04-04 |
| URL | http://arxiv.org/abs/1604.00869v1 |
| http://arxiv.org/pdf/1604.00869v1.pdf | |
| PWC | https://paperswithcode.com/paper/automatic-knowledge-base-evolution-by |
| Repo | |
| Framework | |
Generalized minimum dominating set and application in automatic text summarization
| Title | Generalized minimum dominating set and application in automatic text summarization |
| Authors | Yi-Zhi Xu, Hai-Jun Zhou |
| Abstract | For a graph formed by vertices and weighted edges, a generalized minimum dominating set (MDS) is a vertex set of smallest cardinality such that the summed weight of edges from each outside vertex to vertices in this set is equal to or larger than certain threshold value. This generalized MDS problem reduces to the conventional MDS problem in the limiting case of all the edge weights being equal to the threshold value. We treat the generalized MDS problem in the present paper by a replica-symmetric spin glass theory and derive a set of belief-propagation equations. As a practical application we consider the problem of extracting a set of sentences that best summarize a given input text document. We carry out a preliminary test of the statistical physics-inspired method to this automatic text summarization problem. |
| Tasks | Text Summarization |
| Published | 2016-02-16 |
| URL | http://arxiv.org/abs/1602.04930v1 |
| http://arxiv.org/pdf/1602.04930v1.pdf | |
| PWC | https://paperswithcode.com/paper/generalized-minimum-dominating-set-and |
| Repo | |
| Framework | |
Semi-Supervised Active Learning for Support Vector Machines: A Novel Approach that Exploits Structure Information in Data
| Title | Semi-Supervised Active Learning for Support Vector Machines: A Novel Approach that Exploits Structure Information in Data |
| Authors | Tobias Reitmaier, Adrian Calma, Bernhard Sick |
| Abstract | In our today’s information society more and more data emerges, e.g.~in social networks, technical applications, or business applications. Companies try to commercialize these data using data mining or machine learning methods. For this purpose, the data are categorized or classified, but often at high (monetary or temporal) costs. An effective approach to reduce these costs is to apply any kind of active learning (AL) methods, as AL controls the training process of a classifier by specific querying individual data points (samples), which are then labeled (e.g., provided with class memberships) by a domain expert. However, an analysis of current AL research shows that AL still has some shortcomings. In particular, the structure information given by the spatial pattern of the (un)labeled data in the input space of a classification model (e.g.,~cluster information), is used in an insufficient way. In addition, many existing AL techniques pay too little attention to their practical applicability. To meet these challenges, this article presents several techniques that together build a new approach for combining AL and semi-supervised learning (SSL) for support vector machines (SVM) in classification tasks. Structure information is captured by means of probabilistic models that are iteratively improved at runtime when label information becomes available. The probabilistic models are considered in a selection strategy based on distance, density, diversity, and distribution (4DS strategy) information for AL and in a kernel function (Responsibility Weighted Mahalanobis kernel) for SVM. The approach fuses generative and discriminative modeling techniques. With 20 benchmark data sets and with the MNIST data set it is shown that our new solution yields significantly better results than state-of-the-art methods. |
| Tasks | Active Learning |
| Published | 2016-10-13 |
| URL | http://arxiv.org/abs/1610.03995v2 |
| http://arxiv.org/pdf/1610.03995v2.pdf | |
| PWC | https://paperswithcode.com/paper/semi-supervised-active-learning-for-support |
| Repo | |
| Framework | |
Rotation-Invariant Restricted Boltzmann Machine Using Shared Gradient Filters
| Title | Rotation-Invariant Restricted Boltzmann Machine Using Shared Gradient Filters |
| Authors | Mario Valerio Giuffrida, Sotirios A. Tsaftaris |
| Abstract | Finding suitable features has been an essential problem in computer vision. We focus on Restricted Boltzmann Machines (RBMs), which, despite their versatility, cannot accommodate transformations that may occur in the scene. As a result, several approaches have been proposed that consider a set of transformations, which are used to either augment the training set or transform the actual learned filters. In this paper, we propose the Explicit Rotation-Invariant Restricted Boltzmann Machine, which exploits prior information coming from the dominant orientation of images. Our model extends the standard RBM, by adding a suitable number of weight matrices, associated with each dominant gradient. We show that our approach is able to learn rotation-invariant features, comparing it with the classic formulation of RBM on the MNIST benchmark dataset. Overall, requiring less hidden units, our method learns compact features, which are robust to rotations. |
| Tasks | |
| Published | 2016-04-24 |
| URL | http://arxiv.org/abs/1604.07045v2 |
| http://arxiv.org/pdf/1604.07045v2.pdf | |
| PWC | https://paperswithcode.com/paper/rotation-invariant-restricted-boltzmann |
| Repo | |
| Framework | |
Expressibility of norms in temporal logic
| Title | Expressibility of norms in temporal logic |
| Authors | Natasha Alechina, Mehdi Dastani, Brian Logan |
| Abstract | In this short note we address the issue of expressing norms (such as obligations and prohibitions) in temporal logic. In particular, we address the argument from [Governatori 2015] that norms cannot be expressed in Linear Time Temporal Logic (LTL). |
| Tasks | |
| Published | 2016-08-24 |
| URL | http://arxiv.org/abs/1608.06787v1 |
| http://arxiv.org/pdf/1608.06787v1.pdf | |
| PWC | https://paperswithcode.com/paper/expressibility-of-norms-in-temporal-logic |
| Repo | |
| Framework | |
Stochastic Process Bandits: Upper Confidence Bounds Algorithms via Generic Chaining
| Title | Stochastic Process Bandits: Upper Confidence Bounds Algorithms via Generic Chaining |
| Authors | Emile Contal, Nicolas Vayatis |
| Abstract | The paper considers the problem of global optimization in the setup of stochastic process bandits. We introduce an UCB algorithm which builds a cascade of discretization trees based on generic chaining in order to render possible his operability over a continuous domain. The theoretical framework applies to functions under weak probabilistic smoothness assumptions and also extends significantly the spectrum of application of UCB strategies. Moreover generic regret bounds are derived which are then specialized to Gaussian processes indexed on infinite-dimensional spaces as well as to quadratic forms of Gaussian processes. Lower bounds are also proved in the case of Gaussian processes to assess the optimality of the proposed algorithm. |
| Tasks | Gaussian Processes |
| Published | 2016-02-16 |
| URL | http://arxiv.org/abs/1602.04976v1 |
| http://arxiv.org/pdf/1602.04976v1.pdf | |
| PWC | https://paperswithcode.com/paper/stochastic-process-bandits-upper-confidence |
| Repo | |
| Framework | |
Online Maximum Likelihood Estimation of the Parameters of Partially Observed Diffusion Processes
| Title | Online Maximum Likelihood Estimation of the Parameters of Partially Observed Diffusion Processes |
| Authors | Simone Carlo Surace, Jean-Pascal Pfister |
| Abstract | We revisit the problem of estimating the parameters of a partially observed diffusion process, consisting of a hidden state process and an observed process, with a continuous time parameter. The estimation is to be done online, i.e. the parameter estimate should be updated recursively based on the observation filtration. We provide a theoretical analysis of the stochastic gradient ascent algorithm on the incomplete-data log-likelihood. The convergence of the algorithm is proved under suitable conditions regarding the ergodicity of the process consisting of state, filter, and tangent filter. Additionally, our parameter estimation is shown numerically to have the potential of improving suboptimal filters, and can be applied even when the system is not identifiable due to parameter redundancies. Online parameter estimation is a challenging problem that is ubiquitous in fields such as robotics, neuroscience, or finance in order to design adaptive filters and optimal controllers for unknown or changing systems. Despite this, theoretical analysis of convergence is currently lacking for most of these algorithms. This article sheds new light on the theory of convergence in continuous time. |
| Tasks | |
| Published | 2016-11-01 |
| URL | http://arxiv.org/abs/1611.00170v4 |
| http://arxiv.org/pdf/1611.00170v4.pdf | |
| PWC | https://paperswithcode.com/paper/online-maximum-likelihood-estimation-of-the |
| Repo | |
| Framework | |
