pwc-archive/papers-with-abstracts huggingface dataset:
Matrices of forests, analysis of networks, and ranking problems
Authors: Pavel Chebotarev, Rafig Agaev
Date: 2013-05-28 00:00:00

The matrices of spanning rooted forests are studied as a tool for analysing
the structure of networks and measuring their properties. The problems of
revealing the basic bicomponents, measuring vertex proximity, and ranking from
preference relations / sports competitions are considered. It is shown that the
vertex accessibility measure based on spanning forests has a number of
desirable properties. An interpretation for the stochastic matrix of
out-forests in terms of information dissemination is given.
Joint and individual variation explained (JIVE) for integrated analysis of multiple data types
Authors: Eric F. Lock, Katherine A. Hoadley, J. S. Marron, Andrew B. Nobel
Date: 2011-02-20 00:00:00

Research in several fields now requires the analysis of data sets in which
multiple high-dimensional types of data are available for a common set of
objects. In particular, The Cancer Genome Atlas (TCGA) includes data from
several diverse genomic technologies on the same cancerous tumor samples. In
this paper we introduce Joint and Individual Variation Explained (JIVE), a
general decomposition of variation for the integrated analysis of such data
sets. The decomposition consists of three terms: a low-rank approximation
capturing joint variation across data types, low-rank approximations for
structured variation individual to each data type, and residual noise. JIVE
quantifies the amount of joint variation between data types, reduces the
dimensionality of the data and provides new directions for the visual
exploration of joint and individual structures. The proposed method represents
an extension of Principal Component Analysis and has clear advantages over
popular two-block methods such as Canonical Correlation Analysis and Partial
Least Squares. A JIVE analysis of gene expression and miRNA data on
Glioblastoma Multiforme tumor samples reveals gene-miRNA associations and
provides better characterization of tumor types. Data and software are
available at https://genome.unc.edu/jive/
Proceedings of the 37th Annual Workshop of the Austrian Association for Pattern Recognition (ÖAGM/AAPR), 2013
Authors: Justus Piater, Antonio Rodríguez-Sánchez
Date: 2013-04-06 00:00:00

This volume represents the proceedings of the 37th Annual Workshop of the
Austrian Association for Pattern Recognition (\"OAGM/AAPR), held May 23-24,
2013, in Innsbruck, Austria.
Optimal rates of convergence for persistence diagrams in Topological Data Analysis
Authors: Frédéric Chazal, Marc Glisse, Catherine Labruère, Bertrand Michel
Date: 2013-05-27 00:00:00
Tasks: Topological Data Analysis

Computational topology has recently known an important development toward
data analysis, giving birth to the field of topological data analysis.
Topological persistence, or persistent homology, appears as a fundamental tool
in this field. In this paper, we study topological persistence in general
metric spaces, with a statistical approach. We show that the use of persistent
homology can be naturally considered in general statistical frameworks and
persistence diagrams can be used as statistics with interesting convergence
properties. Some numerical experiments are performed in various contexts to
illustrate our results.
Extended Lambek calculi and first-order linear logic
Authors: Richard Moot
Date: 2013-05-27 00:00:00

First-order multiplicative intuitionistic linear logic (MILL1) can be seen as
an extension of the Lambek calculus. In addition to the fragment of MILL1 which
corresponds to the Lambek calculus (of Moot & Piazza 2001), I will show
fragments of MILL1 which generate the multiple context-free languages and which
correspond to the Displacement calculus of Morrilll e.a.
Integrating Prior Knowledge Into Prognostic Biomarker Discovery based on Network Structure
Authors: Yupeng Cun, Holger Fröhlich
Date: 2012-12-13 00:00:00

Background: Predictive, stable and interpretable gene signatures are
generally seen as an important step towards a better personalized medicine.
During the last decade various methods have been proposed for that purpose.
However, one important obstacle for making gene signatures a standard tool in
clinics is the typical low reproducibility of these signatures combined with
the difficulty to achieve a clear biological interpretation. For that purpose
in the last years there has been a growing interest in approaches that try to
integrate information from molecular interaction networks. Results: We propose
a novel algorithm, called FrSVM, which integrates protein-protein interaction
network information into gene selection for prognostic biomarker discovery. Our
method is a simple filter based approach, which focuses on central genes with
large differences in their expression. Compared to several other competing
methods our algorithm reveals a significantly better prediction performance and
higher signature stability. More- over, obtained gene lists are highly enriched
with known disease genes and drug targets. We extendd our approach further by
integrating information on candidate disease genes and targets of disease
associated Transcript Factors (TFs).
On some interrelations of generalized $q$-entropies and a generalized Fisher information, including a Cramér-Rao inequality
Authors: Jean-François Bercher
Date: 2013-05-27 00:00:00

In this communication, we describe some interrelations between generalized
$q$-entropies and a generalized version of Fisher information. In information
theory, the de Bruijn identity links the Fisher information and the derivative
of the entropy. We show that this identity can be extended to generalized
versions of entropy and Fisher information. More precisely, a generalized
Fisher information naturally pops up in the expression of the derivative of the
Tsallis entropy. This generalized Fisher information also appears as a special
case of a generalized Fisher information for estimation problems. Indeed, we
derive here a new Cram\'er-Rao inequality for the estimation of a parameter,
which involves a generalized form of Fisher information. This generalized
Fisher information reduces to the standard Fisher information as a particular
case. In the case of a translation parameter, the general Cram\'er-Rao
inequality leads to an inequality for distributions which is saturated by
generalized $q$-Gaussian distributions. These generalized $q$-Gaussians are
important in several areas of physics and mathematics. They are known to
maximize the $q$-entropies subject to a moment constraint. The Cram\'er-Rao
inequality shows that the generalized $q$-Gaussians also minimize the
generalized Fisher information among distributions with a fixed moment.
Similarly, the generalized $q$-Gaussians also minimize the generalized Fisher
information among distributions with a given $q$-entropy.
Some results on a $χ$-divergence, an~extended~Fisher information and~generalized~Cramér-Rao inequalities
Authors: Jean-François Bercher
Date: 2013-05-27 00:00:00

We propose a modified $\chi^{\beta}$-divergence, give some of its properties,
and show that this leads to the definition of a generalized Fisher information.
We give generalized Cram\'er-Rao inequalities, involving this Fisher
information, an extension of the Fisher information matrix, and arbitrary norms
and power of the estimation error. In the case of a location parameter, we
obtain new characterizations of the generalized $q$-Gaussians, for instance as
the distribution with a given moment that minimizes the generalized Fisher
information. Finally we indicate how the generalized Fisher information can
lead to new uncertainty relations.
Information-Theoretic Approach to Efficient Adaptive Path Planning for Mobile Robotic Environmental Sensing
Authors: Kian Hsiang Low, John M. Dolan, Pradeep Khosla
Date: 2013-05-27 00:00:00

Recent research in robot exploration and mapping has focused on sampling
environmental hotspot fields. This exploration task is formalized by Low,
Dolan, and Khosla (2008) in a sequential decision-theoretic planning under
uncertainty framework called MASP. The time complexity of solving MASP
approximately depends on the map resolution, which limits its use in
large-scale, high-resolution exploration and mapping. To alleviate this
computational difficulty, this paper presents an information-theoretic approach
to MASP (iMASP) for efficient adaptive path planning; by reformulating the
cost-minimizing iMASP as a reward-maximizing problem, its time complexity
becomes independent of map resolution and is less sensitive to increasing robot
team size as demonstrated both theoretically and empirically. Using the
reward-maximizing dual, we derive a novel adaptive variant of maximum entropy
sampling, thus improving the induced exploration policy performance. It also
allows us to establish theoretical bounds quantifying the performance advantage
of optimal adaptive over non-adaptive policies and the performance quality of
approximately optimal vs. optimal adaptive policies. We show analytically and
empirically the superior performance of iMASP-based policies for sampling the
log-Gaussian process to that of policies for the widely-used Gaussian process
in mapping the hotspot field. Lastly, we provide sufficient conditions that,
when met, guarantee adaptivity has no benefit under an assumed environment
model.
Regression trees for longitudinal and multiresponse data
Authors: Wei-Yin Loh, Wei Zheng
Date: 2012-09-21 00:00:00
Tasks: Missing Values, regression

Previous algorithms for constructing regression tree models for longitudinal
and multiresponse data have mostly followed the CART approach. Consequently,
they inherit the same selection biases and computational difficulties as CART.
We propose an alternative, based on the GUIDE approach, that treats each
longitudinal data series as a curve and uses chi-squared tests of the residual
curve patterns to select a variable to split each node of the tree. Besides
being unbiased, the method is applicable to data with fixed and random time
points and with missing values in the response or predictor variables.
Simulation results comparing its mean squared prediction error with that of
MVPART are given, as well as examples comparing it with standard linear mixed
effects and generalized estimating equation models. Conditions for asymptotic
consistency of regression tree function estimates are also given.
Supervised Feature Selection for Diagnosis of Coronary Artery Disease Based on Genetic Algorithm
Authors: Sidahmed Mokeddem, Baghdad Atmani, Mostefa Mokaddem
Date: 2013-05-26 00:00:00
Tasks: Attribute, feature selection, General Classification

Feature Selection (FS) has become the focus of much research on decision
support systems areas for which data sets with tremendous number of variables
are analyzed. In this paper we present a new method for the diagnosis of
Coronary Artery Diseases (CAD) founded on Genetic Algorithm (GA) wrapped Bayes
Naive (BN) based FS. Basically, CAD dataset contains two classes defined with
13 features. In GA BN algorithm, GA generates in each iteration a subset of
attributes that will be evaluated using the BN in the second step of the
selection procedure. The final set of attribute contains the most relevant
feature model that increases the accuracy. The algorithm in this case produces
85.50% classification accuracy in the diagnosis of CAD. Thus, the asset of the
Algorithm is then compared with the use of Support Vector Machine (SVM),
MultiLayer Perceptron (MLP) and C4.5 decision tree Algorithm. The result of
classification accuracy for those algorithms are respectively 83.5%, 83.16% and
80.85%. Consequently, the GA wrapped BN Algorithm is correspondingly compared
with other FS algorithms. The Obtained results have shown very promising
outcomes for the diagnosis of CAD.
Semi-bounded Rationality: A model for decision making
Authors: Tshilidzi Marwala
Date: 2013-05-26 00:00:00
Tasks: Decision Making, Missing Values, model

In this paper the theory of semi-bounded rationality is proposed as an
extension of the theory of bounded rationality. In particular, it is proposed
that a decision making process involves two components and these are the
correlation machine, which estimates missing values, and the causal machine,
which relates the cause to the effect. Rational decision making involves using
information which is almost always imperfect and incomplete as well as some
intelligent machine which if it is a human being is inconsistent to make
decisions. In the theory of bounded rationality this decision is made
irrespective of the fact that the information to be used is incomplete and
imperfect and the human brain is inconsistent and thus this decision that is to
be made is taken within the bounds of these limitations. In the theory of
semi-bounded rationality, signal processing is used to filter noise and
outliers in the information and the correlation machine is applied to complete
the missing information and artificial intelligence is used to make more
consistent decisions.
Efficient Active Learning of Halfspaces: an Aggressive Approach
Authors: Alon Gonen, Sivan Sabato, Shai Shalev-Shwartz
Date: 2012-08-17 00:00:00
Tasks: Active Learning

We study pool-based active learning of half-spaces. We revisit the aggressive
approach for active learning in the realizable case, and show that it can be
made efficient and practical, while also having theoretical guarantees under
reasonable assumptions. We further show, both theoretically and experimentally,
that it can be preferable to mellow approaches. Our efficient aggressive active
learner of half-spaces has formal approximation guarantees that hold when the
pool is separable with a margin. While our analysis is focused on the
realizable setting, we show that a simple heuristic allows using the same
algorithm successfully for pools with low error as well. We further compare the
aggressive approach to the mellow approach, and prove that there are cases in
which the aggressive approach results in significantly better label complexity
compared to the mellow approach. We demonstrate experimentally that substantial
improvements in label complexity can be achieved using the aggressive approach,
for both realizable and low-error settings.
Reduce Meaningless Words for Joint Chinese Word Segmentation and Part-of-speech Tagging
Authors: Kaixu Zhang, Maosong Sun
Date: 2013-05-25 00:00:00
Tasks: Chinese Word Segmentation, Part-Of-Speech Tagging, Segmentation

Conventional statistics-based methods for joint Chinese word segmentation and
part-of-speech tagging (S&T) have generalization ability to recognize new words
that do not appear in the training data. An undesirable side effect is that a
number of meaningless words will be incorrectly created. We propose an
effective and efficient framework for S&T that introduces features to
significantly reduce meaningless words generation. A general lexicon, Wikepedia
and a large-scale raw corpus of 200 billion characters are used to generate
word-based features for the wordhood. The word-lattice based framework consists
of a character-based model and a word-based model in order to employ our
word-based features. Experiments on Penn Chinese treebank 5 show that this
method has a 62.9% reduction of meaningless word generation in comparison with
the baseline. As a result, the F1 measure for segmentation is increased to
0.984.
ÖAGM/AAPR 2013 - The 37th Annual Workshop of the Austrian Association for Pattern Recognition
Authors: Justus Piater, Antonio J. Rodríguez Sánchez
Date: 2013-05-25 00:00:00

In this editorial, the organizers summarize facts and background about the
event.
A Symmetric Rank-one Quasi Newton Method for Non-negative Matrix Factorization
Authors: Shu-Zhen Lai, Hou-Biao Li, Zu-Tao Zhang
Date: 2013-05-24 00:00:00
Tasks: Clustering, Dimensionality Reduction, Text Clustering

As we all known, the nonnegative matrix factorization (NMF) is a dimension
reduction method that has been widely used in image processing, text
compressing and signal processing etc. In this paper, an algorithm for
nonnegative matrix approximation is proposed. This method mainly bases on the
active set and the quasi-Newton type algorithm, by using the symmetric rank-one
and negative curvature direction technologies to approximate the Hessian
matrix. Our method improves the recent results of those methods in [Pattern
Recognition, 45(2012)3557-3565; SIAM J. Sci. Comput., 33(6)(2011)3261-3281;
Neural Computation, 19(10)(2007)2756-2779, etc.]. Moreover, the object function
decreases faster than many other NMF methods. In addition, some numerical
experiments are presented in the synthetic data, imaging processing and text
clustering. By comparing with the other six nonnegative matrix approximation
methods, our experiments confirm to our analysis.
Semantic Web Search based on Ontology Modeling using Protege Reasoner
Authors: Monica Shekhar, Saravanaguru RA. K
Date: 2013-05-24 00:00:00

The Semantic Web works on the existing Web which presents the meaning of
information as well-defined vocabularies understood by the people. Semantic
Search, at the same time, works on improving the accuracy if a search by
understanding the intent of the search and providing contextually relevant
results. This paper describes a semantic approach toward web search through a
PHP application. The goal was to parse through a user's browsing history and
return semantically relevant web pages for the search query provided.
Parallel Gaussian Process Regression with Low-Rank Covariance Matrix Approximations
Authors: Jie Chen, Nannan Cao, Kian Hsiang Low, Ruofei Ouyang, Colin Keng-Yan Tan, Patrick Jaillet
Date: 2013-05-24 00:00:00
Tasks: Gaussian Processes, regression

Gaussian processes (GP) are Bayesian non-parametric models that are widely
used for probabilistic regression. Unfortunately, it cannot scale well with
large data nor perform real-time predictions due to its cubic time cost in the
data size. This paper presents two parallel GP regression methods that exploit
low-rank covariance matrix approximations for distributing the computational
load among parallel machines to achieve time efficiency and scalability. We
theoretically guarantee the predictive performances of our proposed parallel
GPs to be equivalent to that of some centralized approximate GP regression
methods: The computation of their centralized counterparts can be distributed
among parallel machines, hence achieving greater time efficiency and
scalability. We analytically compare the properties of our parallel GPs such as
time, space, and communication complexity. Empirical evaluation on two
real-world datasets in a cluster of 20 computing nodes shows that our parallel
GPs are significantly more time-efficient and scalable than their centralized
counterparts and exact/full GP while achieving predictive performances
comparable to full GP.
Learning Topic Models and Latent Bayesian Networks Under Expansion Constraints
Authors: Animashree Anandkumar, Daniel Hsu, Adel Javanmard, Sham M. Kakade
Date: 2012-09-24 00:00:00
Tasks: Topic Models

Unsupervised estimation of latent variable models is a fundamental problem
central to numerous applications of machine learning and statistics. This work
presents a principled approach for estimating broad classes of such models,
including probabilistic topic models and latent linear Bayesian networks, using
only second-order observed moments. The sufficient conditions for
identifiability of these models are primarily based on weak expansion
constraints on the topic-word matrix, for topic models, and on the directed
acyclic graph, for Bayesian networks. Because no assumptions are made on the
distribution among the latent variables, the approach can handle arbitrary
correlations among the topics or latent factors. In addition, a tractable
learning method via $\ell_1$ optimization is proposed and studied in numerical
experiments.
An Inventory of Preposition Relations
Authors: Vivek Srikumar, Dan Roth
Date: 2013-05-24 00:00:00
Tasks: Relation, Word Sense Disambiguation

We describe an inventory of semantic relations that are expressed by
prepositions. We define these relations by building on the word sense
disambiguation task for prepositions and propose a mapping from preposition
senses to the relation labels by collapsing semantically related senses across
prepositions.
Adapting the Stochastic Block Model to Edge-Weighted Networks
Authors: Christopher Aicher, Abigail Z. Jacobs, Aaron Clauset
Date: 2013-05-24 00:00:00
Tasks: Stochastic Block Model

We generalize the stochastic block model to the important case in which edges
are annotated with weights drawn from an exponential family distribution. This
generalization introduces several technical difficulties for model estimation,
which we solve using a Bayesian approach. We introduce a variational algorithm
that efficiently approximates the model's posterior distribution for dense
graphs. In specific numerical experiments on edge-weighted networks, this
weighted stochastic block model outperforms the common approach of first
applying a single threshold to all weights and then applying the classic
stochastic block model, which can obscure latent block structure in networks.
This model will enable the recovery of latent structure in a broader range of
network data than was previously possible.
Flooding edge or node weighted graphs
Authors: Fernand Meyer
Date: 2013-05-24 00:00:00
Tasks: RAG

Reconstruction closings have all properties of a physical flooding of a
topographic surface. They are precious for simplifying gradient images or,
filling unwanted catchment basins, on which a subsequent watershed transform
extracts the targeted objects. Flooding a topographic surface may be modeled as
flooding a node weighted graph (TG), with unweighted edges, the node weights
representing the ground level. The progression of a flooding may also be
modeled on the region adjacency graph (RAG) of a topographic surface. On a RAG
each node represents a catchment basin and edges connect neighboring nodes. The
edges are weighted by the altitude of the pass point between both adjacent
regions. The graph is flooded from sources placed at the marker positions and
each node is assigned to the source by which it has been flooded. The level of
the flood is represented on the nodes on each type of graphs. The same flooding
may thus be modeled on a TG or on a RAG. We characterize all valid floodings on
both types of graphs, as they should verify the laws of hydrostatics. We then
show that each flooding of a node weighted graph also is a flooding of an edge
weighted graph with appropriate edge weights. The highest flooding under a
ceiling function may be interpreted as the shortest distance to the root for
the ultrametric flooding distance in an augmented graph. The ultrametric
distance between two nodes is the minimal altitude of a flooding for which both
nodes are flooded. This remark permits to flood edge or node weighted graphs by
using shortest path algorithms. It appears that the collection of all lakes of
a RAG has the structure of a dendrogram, on which the highest flooding under a
ceiling function may be rapidly found.