pwc-archive/papers-with-abstracts huggingface dataset:
Learning Sparse Causal Models is not NP-hard
Authors: Tom Claassen, Joris Mooij, Tom Heskes
Date: 2013-09-26 00:00:00
Tasks: Causal Discovery, Model Discovery, Selection bias

This paper shows that causal model discovery is not an NP-hard problem, in
the sense that for sparse graphs bounded by node degree k the sound and
complete causal model can be obtained in worst case order N^{2(k+2)}
independence tests, even when latent variables and selection bias may be
present. We present a modification of the well-known FCI algorithm that
implements the method for an independence oracle, and suggest improvements for
sample/real-world data versions. It does not contradict any known hardness
results, and does not solve an NP-hard problem: it just proves that sparse
causal discovery is perhaps more complicated, but not as hard as learning
minimal Bayesian networks.
Convex Relaxations of Bregman Divergence Clustering
Authors: Hao Cheng, Xinhua Zhang, Dale Schuurmans
Date: 2013-09-26 00:00:00
Tasks: Clustering

Although many convex relaxations of clustering have been proposed in the past
decade, current formulations remain restricted to spherical Gaussian or
discriminative models and are susceptible to imbalanced clusters. To address
these shortcomings, we propose a new class of convex relaxations that can be
flexibly applied to more general forms of Bregman divergence clustering. By
basing these new formulations on normalized equivalence relations we retain
additional control on relaxation quality, which allows improvement in
clustering quality. We furthermore develop optimization methods that improve
scalability by exploiting recent implicit matrix norm methods. In practice, we
find that the new formulations are able to efficiently produce tighter
clusterings that improve the accuracy of state of the art methods.
Automorphism Groups of Graphical Models and Lifted Variational Inference
Authors: Hung Bui, Tuyen Huynh, Sebastian Riedel
Date: 2013-09-26 00:00:00
Tasks: Variational Inference

Using the theory of group action, we first introduce the concept of the
automorphism group of an exponential family or a graphical model, thus
formalizing the general notion of symmetry of a probabilistic model. This
automorphism group provides a precise mathematical framework for lifted
inference in the general exponential family. Its group action partitions the
set of random variables and feature functions into equivalent classes (called
orbits) having identical marginals and expectations. Then the inference problem
is effectively reduced to that of computing marginals or expectations for each
class, thus avoiding the need to deal with each individual variable or feature.
We demonstrate the usefulness of this general framework in lifting two classes
of variational approximation for maximum a posteriori (MAP) inference: local
linear programming (LP) relaxation and local LP relaxation with cycle
constraints; the latter yields the first lifted variational inference algorithm
that operates on a bound tighter than the local constraints.
Sample Complexity of Multi-task Reinforcement Learning
Authors: Emma Brunskill, Lihong Li
Date: 2013-09-26 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Transferring knowledge across a sequence of reinforcement-learning tasks is
challenging, and has a number of important applications. Though there is
encouraging empirical evidence that transfer can improve performance in
subsequent reinforcement-learning tasks, there has been very little theoretical
analysis. In this paper, we introduce a new multi-task algorithm for a sequence
of reinforcement-learning tasks when each task is sampled independently from
(an unknown) distribution over a finite set of Markov decision processes whose
parameters are initially unknown. For this setting, we prove under certain
assumptions that the per-task sample complexity of exploration is reduced
significantly due to transfer compared to standard single-task algorithms. Our
multi-task algorithm also has the desired characteristic that it is guaranteed
not to exhibit negative transfer: in the worst case its per-task sample
complexity is comparable to the corresponding single-task algorithm.
SparsityBoost: A New Scoring Function for Learning Bayesian Network Structure
Authors: Eliot Brenner, David Sontag
Date: 2013-09-26 00:00:00

We give a new consistent scoring function for structure learning of Bayesian
networks. In contrast to traditional approaches to scorebased structure
learning, such as BDeu or MDL, the complexity penalty that we propose is
data-dependent and is given by the probability that a conditional independence
test correctly shows that an edge cannot exist. What really distinguishes this
new scoring function from earlier work is that it has the property of becoming
computationally easier to maximize as the amount of data increases. We prove a
polynomial sample complexity result, showing that maximizing this score is
guaranteed to correctly learn a structure with no false edges and a
distribution close to the generating distribution, whenever there exists a
Bayesian network which is a perfect map for the data generating distribution.
Although the new score can be used with any search algorithm, we give empirical
results showing that it is particularly effective when used together with a
linear programming relaxation approach to Bayesian network structure learning.
Hilbert Space Embeddings of Predictive State Representations
Authors: Byron Boots, Geoffrey Gordon, Arthur Gretton
Date: 2013-09-26 00:00:00

Predictive State Representations (PSRs) are an expressive class of models for
controlled stochastic processes. PSRs represent state as a set of predictions
of future observable events. Because PSRs are defined entirely in terms of
observable data, statistically consistent estimates of PSR parameters can be
learned efficiently by manipulating moments of observed training data. Most
learning algorithms for PSRs have assumed that actions and observations are
finite with low cardinality. In this paper, we generalize PSRs to infinite sets
of observations and actions, using the recent concept of Hilbert space
embeddings of distributions. The essence is to represent the state as a
nonparametric conditional embedding operator in a Reproducing Kernel Hilbert
Space (RKHS) and leverage recent work in kernel methods to estimate, predict,
and update the representation. We show that these Hilbert space embeddings of
PSRs are able to gracefully handle continuous actions and observations, and
that our learned models outperform competing system identification algorithms
on several prediction benchmarks.
Boosting in the presence of label noise
Authors: Jakramate Bootkrajang, Ata Kaban
Date: 2013-09-26 00:00:00

Boosting is known to be sensitive to label noise. We studied two approaches
to improve AdaBoost's robustness against labelling errors. One is to employ a
label-noise robust classifier as a base learner, while the other is to modify
the AdaBoost algorithm to be more robust. Empirical evaluation shows that a
committee of robust classifiers, although converges faster than non label-noise
aware AdaBoost, is still susceptible to label noise. However, pairing it with
the new robust Boosting algorithm we propose here results in a more resilient
algorithm under mislabelling.
Probabilistic Conditional Preference Networks
Authors: Damien Bigot, Bruno Zanuttini, Helene Fargier, Jerome Mengin
Date: 2013-09-26 00:00:00

In order to represent the preferences of a group of individuals, we introduce
Probabilistic CP-nets (PCP-nets). PCP-nets provide a compact language for
representing probability distributions over preference orderings. We argue that
they are useful for aggregating preferences or modelling noisy preferences.
Then we give efficient algorithms for the main reasoning problems, namely for
computing the probability that a given outcome is preferred to another one, and
the probability that a given outcome is optimal. As a by-product, we obtain an
unexpected linear-time algorithm for checking dominance in a standard,
tree-structured CP-net.
Reasoning about Probabilities in Dynamic Systems using Goal Regression
Authors: Vaishak Belle, Hector Levesque
Date: 2013-09-26 00:00:00
Tasks: Gaussian Processes, regression

Reasoning about degrees of belief in uncertain dynamic worlds is fundamental
to many applications, such as robotics and planning, where actions modify state
properties and sensors provide measurements, both of which are prone to noise.
With the exception of limited cases such as Gaussian processes over linear
phenomena, belief state evolution can be complex and hard to reason with in a
general way. This paper proposes a framework with new results that allows the
reduction of subjective probabilities after sensing and acting to questions
about the initial state only. We build on an expressive probabilistic
first-order logical account by Bacchus, Halpern and Levesque, resulting in a
methodology that, in principle, can be coupled with a variety of existing
inference solutions.
Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases
Authors: Paul Beame, Jerry Li, Sudeepa Roy, Dan Suciu
Date: 2013-09-26 00:00:00
Tasks: Negation

The best current methods for exactly computing the number of satisfying
assignments, or the satisfying probability, of Boolean formulas can be seen,
either directly or indirectly, as building 'decision-DNNF' (decision
decomposable negation normal form) representations of the input Boolean
formulas. Decision-DNNFs are a special case of 'd-DNNF's where 'd' stands for
'deterministic'. We show that any decision-DNNF can be converted into an
equivalent 'FBDD' (free binary decision diagram) -- also known as a 'read-once
branching program' (ROBP or 1-BP) -- with only a quasipolynomial increase in
representation size in general, and with only a polynomial increase in size in
the special case of monotone k-DNF formulas. Leveraging known exponential lower
bounds for FBDDs, we then obtain similar exponential lower bounds for
decision-DNNFs which provide lower bounds for the recent algorithms. We also
separate the power of decision-DNNFs from d-DNNFs and a generalization of
decision-DNNFs known as AND-FBDDs. Finally we show how these imply exponential
lower bounds for natural problems associated with probabilistic databases.
High-dimensional Joint Sparsity Random Effects Model for Multi-task Learning
Authors: Krishnakumar Balasubramanian, Kai Yu, Tong Zhang
Date: 2013-09-26 00:00:00
Tasks: Multi-Task Learning, Vocal Bursts Intensity Prediction

Joint sparsity regularization in multi-task learning has attracted much
attention in recent years. The traditional convex formulation employs the group
Lasso relaxation to achieve joint sparsity across tasks. Although this approach
leads to a simple convex formulation, it suffers from several issues due to the
looseness of the relaxation. To remedy this problem, we view jointly sparse
multi-task learning as a specialized random effects model, and derive a convex
relaxation approach that involves two steps. The first step learns the
covariance matrix of the coefficients using a convex formulation which we refer
to as sparse covariance coding; the second step solves a ridge regression
problem with a sparse quadratic regularizer based on the covariance matrix
obtained in the first step. It is shown that this approach produces an
asymptotically optimal quadratic regularizer in the multitask learning setting
when the number of tasks approaches infinity. Experimental results demonstrate
that the convex formulation obtained via the proposed model significantly
outperforms group Lasso (and related multi-stage formulations
Hinge-loss Markov Random Fields: Convex Inference for Structured Prediction
Authors: Stephen Bach, Bert Huang, Ben London, Lise Getoor
Date: 2013-09-26 00:00:00
Tasks: Structured Prediction

Graphical models for structured domains are powerful tools, but the
computational complexities of combinatorial prediction spaces can force
restrictions on models, or require approximate inference in order to be
tractable. Instead of working in a combinatorial space, we use hinge-loss
Markov random fields (HL-MRFs), an expressive class of graphical models with
log-concave density functions over continuous variables, which can represent
confidences in discrete predictions. This paper demonstrates that HL-MRFs are
general tools for fast and accurate structured prediction. We introduce the
first inference algorithm that is both scalable and applicable to the full
class of HL-MRFs, and show how to train HL-MRFs with several learning
algorithms. Our experiments show that HL-MRFs match or surpass the predictive
performance of state-of-the-art methods, including discrete models, in four
application domains.
The Bregman Variational Dual-Tree Framework
Authors: Saeed Amizadeh, Bo Thiesson, Milos Hauskrecht
Date: 2013-09-26 00:00:00
Tasks: Text Categorization

Graph-based methods provide a powerful tool set for many non-parametric
frameworks in Machine Learning. In general, the memory and computational
complexity of these methods is quadratic in the number of examples in the data
which makes them quickly infeasible for moderate to large scale datasets. A
significant effort to find more efficient solutions to the problem has been
made in the literature. One of the state-of-the-art methods that has been
recently introduced is the Variational Dual-Tree (VDT) framework. Despite some
of its unique features, VDT is currently restricted only to Euclidean spaces
where the Euclidean distance quantifies the similarity. In this paper, we
extend the VDT framework beyond the Euclidean distance to more general Bregman
divergences that include the Euclidean distance as a special case. By
exploiting the properties of the general Bregman divergence, we show how the
new framework can maintain all the pivotal features of the VDT framework and
yet significantly improve its performance in non-Euclidean domains. We apply
the proposed framework to different text categorization problems and
demonstrate its benefits over the original VDT.
Generative Multiple-Instance Learning Models For Quantitative Electromyography
Authors: Tameem Adel, Benn Smith, Ruth Urner, Daniel Stashuk, Daniel J. Lizotte
Date: 2013-09-26 00:00:00
Tasks: Multiple Instance Learning

We present a comprehensive study of the use of generative modeling approaches
for Multiple-Instance Learning (MIL) problems. In MIL a learner receives
training instances grouped together into bags with labels for the bags only
(which might not be correct for the comprised instances). Our work was
motivated by the task of facilitating the diagnosis of neuromuscular disorders
using sets of motor unit potential trains (MUPTs) detected within a muscle
which can be cast as a MIL problem. Our approach leads to a state-of-the-art
solution to the problem of muscle classification. By introducing and analyzing
generative models for MIL in a general framework and examining a variety of
model structures and components, our work also serves as a methodological guide
to modelling MIL tasks. We evaluate our proposed methods both on MUPT datasets
and on the MUSK1 dataset, one of the most widely used benchmarks for MIL.
Adopting level set theory based algorithms to segment human ear
Authors: Bijeesh T. V, Nimmi I. P
Date: 2013-09-26 00:00:00

Human identification has always been a topic that interested researchers
around the world. Biometric methods are found to be more effective and much
easier for the users than the traditional identification methods like keys,
smart cards and passwords. Unlike with the traditional methods, with biometric
methods the data acquisition is most of the times passive, which means the
users do not take active part in data acquisition. Data acquisition can be
performed using cameras, scanners or sensors. Human physiological biometrics
such as face, eye and ear are good candidates for uniquely identifying an
individual. However, human ear scores over face and eye because of certain
advantages it has over face. The most challenging phase in human identification
based on ear biometric is the segmentation of the ear image from the captured
image which may contain many unwanted details. In this work, PDE based image
processing techniques are used to segment out the ear image. Level Set Theory
based image processing is employed to obtain the contour of the ear image. A
few Level set algorithms are compared for their efficiency in segmenting test
ear images.
Domain-Specific Sentiment Word Extraction by Seed Expansion and Pattern Generation
Authors: Tang Duyu, Qin Bing, Zhou LanJun, Wong KamFai, Zhao Yanyan, Liu Ting
Date: 2013-09-26 00:00:00
Tasks: Sentiment Analysis

This paper focuses on the automatic extraction of domain-specific sentiment
word (DSSW), which is a fundamental subtask of sentiment analysis. Most
previous work utilizes manual patterns for this task. However, the performance
of those methods highly relies on the labelled patterns or selected seeds. In
order to overcome the above problem, this paper presents an automatic framework
to detect large-scale domain-specific patterns for DSSW extraction. To this
end, sentiment seeds are extracted from massive dataset of user comments.
Subsequently, these sentiment seeds are expanded by synonyms using a
bootstrapping mechanism. Simultaneously, a synonymy graph is built and the
graph propagation algorithm is applied on the built synonymy graph. Afterwards,
syntactic and sequential relations between target words and high-ranked
sentiment words are extracted automatically to construct large-scale patterns,
which are further used to extracte DSSWs. The experimental results in three
domains reveal the effectiveness of our method.
Decision Making for Inconsistent Expert Judgments Using Negative Probabilities
Authors: J. Acacio de Barros
Date: 2013-07-15 00:00:00
Tasks: Decision Making

In this paper we provide a simple random-variable example of inconsistent
information, and analyze it using three different approaches: Bayesian,
quantum-like, and negative probabilities. We then show that, at least for this
particular example, both the Bayesian and the quantum-like approaches have less
normative power than the negative probabilities one.
Characterness: An Indicator of Text in the Wild
Authors: Yao Li, Wenjing Jia, Chunhua Shen, Anton Van Den Hengel
Date: 2013-09-25 00:00:00
Tasks: Saliency Detection, Scene Text Detection, Text Detection

Text in an image provides vital information for interpreting its contents,
and text in a scene can aide with a variety of tasks from navigation, to
obstacle avoidance, and odometry. Despite its value, however, identifying
general text in images remains a challenging research problem. Motivated by the
need to consider the widely varying forms of natural text, we propose a
bottom-up approach to the problem which reflects the `characterness' of an
image region. In this sense our approach mirrors the move from saliency
detection methods to measures of `objectness'. In order to measure the
characterness we develop three novel cues that are tailored for character
detection, and a Bayesian method for their integration. Because text is made up
of sets of characters, we then design a Markov random field (MRF) model so as
to exploit the inherent dependencies between characters.
  We experimentally demonstrate the effectiveness of our characterness cues as
well as the advantage of Bayesian multi-cue integration. The proposed text
detector outperforms state-of-the-art methods on a few benchmark scene text
detection datasets. We also show that our measurement of `characterness' is
superior than state-of-the-art saliency detection models when applied to the
same task.
The Classification Accuracy of Multiple-Metric Learning Algorithm on Multi-Sensor Fusion
Authors: Firouz Abdullah Al-Wassai, N. V. Kalyankar
Date: 2013-09-11 00:00:00
Tasks: General Classification, Metric Learning, Sensor Fusion

This paper focuses on two main issues; first one is the impact of Similarity
Search to learning the training sample in metric space, and searching based on
supervised learning classi-fication. In particular, four metrics space
searching are based on spatial information that are introduced as the
following; Cheby-shev Distance (CD); Bray Curtis Distance (BCD); Manhattan
Distance (MD) and Euclidean Distance(ED) classifiers. The second issue
investigates the performance of combination of mul-ti-sensor images on the
supervised learning classification accura-cy. QuickBird multispectral data (MS)
and panchromatic data (PAN) have been used in this study to demonstrate the
enhance-ment and accuracy assessment of fused image over the original images.
The supervised classification results of fusion image generated better than the
MS did. QuickBird and the best results with ED classifier than the other did.
An Inter-lingual Reference Approach For Multi-Lingual Ontology Matching
Authors: Haytham Al-Feel, Ralph Schafermeier, Adrian Paschke
Date: 2013-09-25 00:00:00
Tasks: Ontology Matching

Ontologies are considered as the backbone of the Semantic Web. With the
rising success of the Semantic Web, the number of participating communities
from different countries is constantly increasing. The growing number of
ontologies available in different natural languages leads to an
interoperability problem. In this paper, we discuss several approaches for
ontology matching; examine similarities and differences, identify weaknesses,
and compare the existing automated approaches with the manual approaches for
integrating multilingual ontologies. In addition to that, we propose a new
architecture for a multilingual ontology matching service. As a case study we
used an example of two multilingual enterprise ontologies - the university
ontology of Freie Universitaet Berlin and the ontology for Fayoum University in
Egypt.
Learning Stable Multilevel Dictionaries for Sparse Representations
Authors: Jayaraman J. Thiagarajan, Karthikeyan Natesan Ramamurthy, Andreas Spanias
Date: 2013-03-03 00:00:00
Tasks: Clustering, Dictionary Learning

Sparse representations using learned dictionaries are being increasingly used
with success in several data processing and machine learning applications. The
availability of abundant training data necessitates the development of
efficient, robust and provably good dictionary learning algorithms. Algorithmic
stability and generalization are desirable characteristics for dictionary
learning algorithms that aim to build global dictionaries which can efficiently
model any test data similar to the training samples. In this paper, we propose
an algorithm to learn dictionaries for sparse representations from large scale
data, and prove that the proposed learning algorithm is stable and
generalizable asymptotically. The algorithm employs a 1-D subspace clustering
procedure, the K-hyperline clustering, in order to learn a hierarchical
dictionary with multiple levels. We also propose an information-theoretic
scheme to estimate the number of atoms needed in each level of learning and
develop an ensemble approach to learn robust dictionaries. Using the proposed
dictionaries, the sparse code for novel test data can be computed using a
low-complexity pursuit procedure. We demonstrate the stability and
generalization characteristics of the proposed algorithm using simulations. We
also evaluate the utility of the multilevel dictionaries in compressed recovery
and subspace learning applications.