pwc-archive/papers-with-abstracts huggingface dataset:
On Learnability, Complexity and Stability
Authors: Silvia Villa, Lorenzo Rosasco, Tomaso Poggio
Date: 2013-03-24 00:00:00
Tasks: Survey

We consider the fundamental question of learnability of a hypotheses class in
the supervised learning setting and in the general learning setting introduced
by Vladimir Vapnik. We survey classic results characterizing learnability in
term of suitable notions of complexity, as well as more recent results that
establish the connection between learnability and stability of a learning
algorithm.
DLOLIS-A: Description Logic based Text Ontology Learning
Authors: Sourish Dasgupta, Ankur Padia, Kushal Shah, Rupali KaPatel, Prasenjit Majumder
Date: 2013-03-24 00:00:00
Tasks: Formal Logic

Ontology Learning has been the subject of intensive study for the past
decade. Researchers in this field have been motivated by the possibility of
automatically building a knowledge base on top of text documents so as to
support reasoning based knowledge extraction. While most works in this field
have been primarily statistical (known as light-weight Ontology Learning) not
much attempt has been made in axiomatic Ontology Learning (called heavy-weight
Ontology Learning) from Natural Language text documents. Heavy-weight Ontology
Learning supports more precise formal logic-based reasoning when compared to
statistical ontology learning. In this paper we have proposed a sound Ontology
Learning tool DLOL_(IS-A) that maps English language IS-A sentences into their
equivalent Description Logic (DL) expressions in order to automatically
generate a consistent pair of T-box and A-box thereby forming both regular
(definitional form) and generalized (axiomatic form) DL ontology. The current
scope of the paper is strictly limited to IS-A sentences that exclude the
possible structures of: (i) implicative IS-A sentences, and (ii) "Wh" IS-A
questions. Other linguistic nuances that arise out of pragmatics and epistemic
of IS-A sentences are beyond the scope of this present work. We have adopted
Gold Standard based Ontology Learning evaluation on chosen IS-A rich Wikipedia
documents.
Heart Disease Prediction System using Associative Classification and Genetic Algorithm
Authors: M. Akhil Jabbar, B L Deekshatulu, Priti Chandra
Date: 2013-03-24 00:00:00
Tasks: Classification, Disease Prediction, General Classification, Prediction

Associative classification is a recent and rewarding technique which
integrates association rule mining and classification to a model for prediction
and achieves maximum accuracy. Associative classifiers are especially fit to
applications where maximum accuracy is desired to a model for prediction. There
are many domains such as medical where the maximum accuracy of the model is
desired. Heart disease is a single largest cause of death in developed
countries and one of the main contributors to disease burden in developing
countries. Mortality data from the registrar general of India shows that heart
disease are a major cause of death in India, and in Andhra Pradesh coronary
heart disease cause about 30%of deaths in rural areas. Hence there is a need to
develop a decision support system for predicting heart disease of a patient. In
this paper we propose efficient associative classification algorithm using
genetic approach for heart disease prediction. The main motivation for using
genetic algorithm in the discovery of high level prediction rules is that the
discovered rules are highly comprehensible, having high predictive accuracy and
of high interestingness values. Experimental Results show that most of the
classifier rules help in the best prediction of heart disease which even helps
doctors in their diagnosis decisions.
A Diffusion Process on Riemannian Manifold for Visual Tracking
Authors: Marcus Chen, Cham Tat Jen, Pang Sze Kim, Alvina Goh
Date: 2013-03-24 00:00:00
Tasks: Visual Tracking

Robust visual tracking for long video sequences is a research area that has
many important applications. The main challenges include how the target image
can be modeled and how this model can be updated. In this paper, we model the
target using a covariance descriptor, as this descriptor is robust to problems
such as pixel-pixel misalignment, pose and illumination changes, that commonly
occur in visual tracking. We model the changes in the template using a
generative process. We introduce a new dynamical model for the template update
using a random walk on the Riemannian manifold where the covariance descriptors
lie in. This is done using log-transformed space of the manifold to free the
constraints imposed inherently by positive semidefinite matrices. Modeling
template variations and poses kinetics together in the state space enables us
to jointly quantify the uncertainties relating to the kinematic states and the
template in a principled way. Finally, the sequential inference of the
posterior distribution of the kinematic states and the template is done using a
particle filter. Our results shows that this principled approach can be robust
to changes in illumination, poses and spatial affine transformation. In the
experiments, our method outperformed the current state-of-the-art algorithm -
the incremental Principal Component Analysis method, particularly when a target
underwent fast poses changes and also maintained a comparable performance in
stable target tracking cases.
Near-optimal compressed sensing guarantees for total variation minimization
Authors: Deanna Needell, Rachel Ward
Date: 2012-10-11 00:00:00
Tasks: compressed sensing

Consider the problem of reconstructing a multidimensional signal from an
underdetermined set of measurements, as in the setting of compressed sensing.
Without any additional assumptions, this problem is ill-posed. However, for
signals such as natural images or movies, the minimal total variation estimate
consistent with the measurements often produces a good approximation to the
underlying signal, even if the number of measurements is far smaller than the
ambient dimensionality. This paper extends recent reconstruction guarantees for
two-dimensional images to signals of arbitrary dimension d>1 and to isotropic
total variation problems. To be precise, we show that a multidimensional signal
x can be reconstructed from O(sd*log(N^d)) linear measurements using total
variation minimization to within a factor of the best s-term approximation of
its gradient. The reconstruction guarantees we provide are necessarily optimal
up to polynomial factors in the spatial dimension d.
Bipolar Fuzzy Soft sets and its applications in decision making problem
Authors: Muhammad Aslam, Saleem Abdullah, Kifayat ullah
Date: 2013-03-23 00:00:00
Tasks: Decision Making

In this article, we combine the concept of a bipolar fuzzy set and a soft
set. We introduce the notion of bipolar fuzzy soft set and study fundamental
properties. We study basic operations on bipolar fuzzy soft set. We define
exdended union, intersection of two bipolar fuzzy soft set. We also give an
application of bipolar fuzzy soft set into decision making problem. We give a
general algorithm to solve decision making problems by using bipolar fuzzy soft
set.
High quality topic extraction from business news explains abnormal financial market volatility
Authors: Ryohei Hisano, Didier Sornette, Takayuki Mizuno, Takaaki Ohnishi, Tsutomu Watanabe
Date: 2012-10-23 00:00:00

Understanding the mutual relationships between information flows and social
activity in society today is one of the cornerstones of the social sciences. In
financial economics, the key issue in this regard is understanding and
quantifying how news of all possible types (geopolitical, environmental,
social, financial, economic, etc.) affect trading and the pricing of firms in
organized stock markets. In this article, we seek to address this issue by
performing an analysis of more than 24 million news records provided by
Thompson Reuters and of their relationship with trading activity for 206 major
stocks in the S&P US stock index. We show that the whole landscape of news that
affect stock price movements can be automatically summarized via simple
regularized regressions between trading activity and news information pieces
decomposed, with the help of simple topic modeling techniques, into their
"thematic" features. Using these methods, we are able to estimate and quantify
the impacts of news on trading. We introduce network-based visualization
techniques to represent the whole landscape of news information associated with
a basket of stocks. The examination of the words that are representative of the
topic distributions confirms that our method is able to extract the significant
pieces of information influencing the stock market. Our results show that one
of the most puzzling stylized fact in financial economies, namely that at
certain times trading volumes appear to be "abnormally large," can be partially
explained by the flow of news. In this sense, our results prove that there is
no "excess trading," when restricting to times when news are genuinely novel
and provide relevant financial information.
Dialectics of Knowledge Representation in a Granular Rough Set Theory
Authors: A. Mani
Date: 2012-12-28 00:00:00

The concepts of rough and definite objects are relatively more determinate
than those of granules and granulation in general rough set theory (RST) [1].
Representation of rough objects can however depend on the dialectical relation
between granulation and definiteness. In this research, we make this exact in
the context of RST over proto-transitive approximation spaces. This approach
can be directly extended to many other types of RST. These are used for
formulating an extended concept of knowledge interpretation (KI)(relative the
situation for classical RST) and the problem of knowledge representation (KR)
is solved. These will be of direct interest in granular KR in RST as developed
by the present author [2] and of rough objects in general. In [3], these have
already been used for five different semantics by the present author. This is
an extended version of [4] with key examples and more results.
Deep Gaussian Processes
Authors: Andreas C. Damianou, Neil D. Lawrence
Date: 2012-11-02 00:00:00
Tasks: Gaussian Processes, Model Selection

In this paper we introduce deep Gaussian process (GP) models. Deep GPs are a
deep belief network based on Gaussian process mappings. The data is modeled as
the output of a multivariate GP. The inputs to that Gaussian process are then
governed by another GP. A single layer model is equivalent to a standard GP or
the GP latent variable model (GP-LVM). We perform inference in the model by
approximate variational marginalization. This results in a strict lower bound
on the marginal likelihood of the model which we use for model selection
(number of layers and nodes per layer). Deep belief networks are typically
applied to relatively large data sets using stochastic gradient descent for
optimization. Our fully Bayesian treatment allows for the application of deep
models even when data is scarce. Model selection by our variational bound shows
that a five layer hierarchy is justified even when modelling a digit data set
containing only 150 examples.
Speech Recognition with Deep Recurrent Neural Networks
Authors: Alex Graves, Abdel-rahman Mohamed, Geoffrey Hinton
Date: 2013-03-22 00:00:00
Tasks: Handwriting Recognition, Phoneme Recognition, Speech Recognition

Recurrent neural networks (RNNs) are a powerful model for sequential data.
End-to-end training methods such as Connectionist Temporal Classification make
it possible to train RNNs for sequence labelling problems where the
input-output alignment is unknown. The combination of these methods with the
Long Short-term Memory RNN architecture has proved particularly fruitful,
delivering state-of-the-art results in cursive handwriting recognition. However
RNN performance in speech recognition has so far been disappointing, with
better results returned by deep feedforward networks. This paper investigates
\emph{deep recurrent neural networks}, which combine the multiple levels of
representation that have proved so effective in deep networks with the flexible
use of long range context that empowers RNNs. When trained end-to-end with
suitable regularisation, we find that deep Long Short-term Memory RNNs achieve
a test set error of 17.7% on the TIMIT phoneme recognition benchmark, which to
our knowledge is the best recorded score.
Bayesian Compressed Regression
Authors: Rajarshi Guhaniyogi, David B. Dunson
Date: 2013-03-04 00:00:00
Tasks: Dimensionality Reduction, regression, Variable Selection

As an alternative to variable selection or shrinkage in high dimensional
regression, we propose to randomly compress the predictors prior to analysis.
This dramatically reduces storage and computational bottlenecks, performing
well when the predictors can be projected to a low dimensional linear subspace
with minimal loss of information about the response. As opposed to existing
Bayesian dimensionality reduction approaches, the exact posterior distribution
conditional on the compressed data is available analytically, speeding up
computation by many orders of magnitude while also bypassing robustness issues
due to convergence and mixing problems with MCMC. Model averaging is used to
reduce sensitivity to the random projection matrix, while accommodating
uncertainty in the subspace dimension. Strong theoretical support is provided
for the approach by showing near parametric convergence rates for the
predictive density in the large p small n asymptotic paradigm. Practical
performance relative to competitors is illustrated in simulations and real data
applications.
Cortical Surface Co-Registration based on MRI Images and Photos
Authors: Benjamin Berkels, Ivan Cabrilo, Sven Haller, Martin Rumpf, Carlo Schaller
Date: 2013-03-22 00:00:00
Tasks: General Classification, Robust classification

Brain shift, i.e. the change in configuration of the brain after opening the
dura mater, is a key problem in neuronavigation. We present an approach to
co-register intra-operative microscope images with pre-operative MRI to adapt
and optimize intra-operative neuronavigation. The tools are a robust
classification of sulci on MRI extracted cortical surfaces, guided user marking
of most prominent sulci on a microscope image, and the actual variational
registration method with a fidelity energy for 3D deformations of the cortical
surface combined with a higher order, linear elastica type prior energy.
Furthermore, the actual registration is validated on an artificial testbed with
known ground truth deformation and on real data of a neuro clinical patient.
Measuring the Complexity of Ultra-Large-Scale Adaptive Systems
Authors: Michele Amoretti, Carlos Gershenson
Date: 2012-07-27 00:00:00

Ultra-large scale (ULS) systems are becoming pervasive. They are inherently
complex, which makes their design and control a challenge for traditional
methods. Here we propose the design and analysis of ULS systems using measures
of complexity, emergence, self-organization, and homeostasis based on
information theory. These measures allow the evaluation of ULS systems and thus
can be used to guide their design. We evaluate the proposal with a ULS
computing system provided with adaptation mechanisms. We show the evolution of
the system with stable and also changing workload, using different fitness
functions. When the adaptive plan forces the system to converge to a predefined
performance level, the nodes may result in highly unstable configurations, that
correspond to a high variance in time of the measured complexity. Conversely,
if the adaptive plan is less "aggressive", the system may be more stable, but
the optimal performance may not be achieved.
Network Detection Theory and Performance
Authors: Steven T. Smith, Kenneth D. Senne, Scott Philips, Edward K. Kao, Garrett Bernstein
Date: 2013-03-22 00:00:00
Tasks: Community Detection, graph partitioning

Network detection is an important capability in many areas of applied
research in which data can be represented as a graph of entities and
relationships. Oftentimes the object of interest is a relatively small subgraph
in an enormous, potentially uninteresting background. This aspect characterizes
network detection as a "big data" problem. Graph partitioning and network
discovery have been major research areas over the last ten years, driven by
interest in internet search, cyber security, social networks, and criminal or
terrorist activities. The specific problem of network discovery is addressed as
a special case of graph partitioning in which membership in a small subgraph of
interest must be determined. Algebraic graph theory is used as the basis to
analyze and compare different network detection methods. A new Bayesian network
detection framework is introduced that partitions the graph based on prior
information and direct observations. The new approach, called space-time threat
propagation, is proved to maximize the probability of detection and is
therefore optimum in the Neyman-Pearson sense. This optimality criterion is
compared to spectral community detection approaches which divide the global
graph into subsets or communities with optimal connectivity properties. We also
explore a new generative stochastic model for covert networks and analyze using
receiver operating characteristics the detection performance of both classes of
optimal detection techniques.
A Block Lanczos with Warm Start Technique for Accelerating Nuclear Norm Minimization Algorithms
Authors: Zhouchen Lin, Siming Wei
Date: 2010-12-02 00:00:00
Tasks: Matrix Completion

Recent years have witnessed the popularity of using rank minimization as a
regularizer for various signal processing and machine learning problems. As
rank minimization problems are often converted to nuclear norm minimization
(NNM) problems, they have to be solved iteratively and each iteration requires
computing a singular value decomposition (SVD). Therefore, their solution
suffers from the high computation cost of multiple SVDs. To relieve this issue,
we propose using the block Lanczos method to compute the partial SVDs, where
the principal singular subspaces obtained in the previous iteration are used to
start the block Lanczos procedure. To avoid the expensive reorthogonalization
in the Lanczos procedure, the block Lanczos procedure is performed for only a
few steps. Our block Lanczos with warm start (BLWS) technique can be adopted by
different algorithms that solve NNM problems. We present numerical results on
applying BLWS to Robust PCA and Matrix Completion problems. Experimental
results show that our BLWS technique usually accelerates its host algorithm by
at least two to three times.
Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions
Authors: Donald Goldfarb, Shiqian Ma, Katya Scheinberg
Date: 2009-12-23 00:00:00

We present in this paper first-order alternating linearization algorithms
based on an alternating direction augmented Lagrangian approach for minimizing
the sum of two convex functions. Our basic methods require at most
$O(1/\epsilon)$ iterations to obtain an $\epsilon$-optimal solution, while our
accelerated (i.e., fast) versions of them require at most
$O(1/\sqrt{\epsilon})$ iterations, with little change in the computational
effort required at each iteration. For both types of methods, we present one
algorithm that requires both functions to be smooth with Lipschitz continuous
gradients and one algorithm that needs only one of the functions to be so.
Algorithms in this paper are Gauss-Seidel type methods, in contrast to the ones
proposed by Goldfarb and Ma in [21] where the algorithms are Jacobi type
methods. Numerical results are reported to support our theoretical conclusions
and demonstrate the practical potential of our algorithms.
Solving Principal Component Pursuit in Linear Time via $l_1$ Filtering
Authors: Risheng Liu, Zhouchen Lin, Siming Wei, Zhixun Su
Date: 2011-08-26 00:00:00

In the past decades, exactly recovering the intrinsic data structure from
corrupted observations, which is known as robust principal component analysis
(RPCA), has attracted tremendous interests and found many applications in
computer vision. Recently, this problem has been formulated as recovering a
low-rank component and a sparse component from the observed data matrix. It is
proved that under some suitable conditions, this problem can be exactly solved
by principal component pursuit (PCP), i.e., minimizing a combination of nuclear
norm and $l_1$ norm. Most of the existing methods for solving PCP require
singular value decompositions (SVD) of the data matrix, resulting in a high
computational complexity, hence preventing the applications of RPCA to very
large scale computer vision problems. In this paper, we propose a novel
algorithm, called $l_1$ filtering, for \emph{exactly} solving PCP with an
$O(r^2(m+n))$ complexity, where $m\times n$ is the size of data matrix and $r$
is the rank of the matrix to recover, which is supposed to be much smaller than
$m$ and $n$. Moreover, $l_1$ filtering is \emph{highly parallelizable}. It is
the first algorithm that can \emph{exactly} solve a nuclear norm minimization
problem in \emph{linear time} (with respect to the data size). Experiments on
both synthetic data and real applications testify to the great advantage of
$l_1$ filtering in speed over state-of-the-art algorithms.
Moving Object Detection by Detecting Contiguous Outliers in the Low-Rank Representation
Authors: Xiaowei Zhou, Can Yang, Weichuan Yu
Date: 2011-09-05 00:00:00
Tasks: Moving Object Detection, Object, object-detection, Object Detection

Object detection is a fundamental step for automated video analysis in many
vision applications. Object detection in a video is usually performed by object
detectors or background subtraction techniques. Often, an object detector
requires manually labeled examples to train a binary classifier, while
background subtraction needs a training sequence that contains no objects to
build a background model. To automate the analysis, object detection without a
separate training phase becomes a critical task. People have tried to tackle
this task by using motion information. But existing motion-based methods are
usually limited when coping with complex scenarios such as nonrigid motion and
dynamic background. In this paper, we show that above challenges can be
addressed in a unified framework named DEtecting Contiguous Outliers in the
LOw-rank Representation (DECOLOR). This formulation integrates object detection
and background learning into a single process of optimization, which can be
solved by an alternating algorithm efficiently. We explain the relations
between DECOLOR and other sparsity-based methods. Experiments on both simulated
data and real sequences demonstrate that DECOLOR outperforms the
state-of-the-art approaches and it can work effectively on a wide range of
complex scenarios.
Sparse Bayesian Methods for Low-Rank Matrix Estimation
Authors: S. Derin Babacan, Martin Luessi, Rafael Molina, Aggelos K. Katsaggelos
Date: 2011-02-25 00:00:00
Tasks: Matrix Completion

Recovery of low-rank matrices has recently seen significant activity in many
areas of science and engineering, motivated by recent theoretical results for
exact reconstruction guarantees and interesting practical applications. A
number of methods have been developed for this recovery problem. However, a
principled method for choosing the unknown target rank is generally not
provided. In this paper, we present novel recovery algorithms for estimating
low-rank matrices in matrix completion and robust principal component analysis
based on sparse Bayesian learning (SBL) principles. Starting from a matrix
factorization formulation and enforcing the low-rank constraint in the
estimates as a sparsity constraint, we develop an approach that is very
effective in determining the correct rank while providing high recovery
performance. We provide connections with existing methods in other similar
problems and empirical results and comparisons with current state-of-the-art
methods that illustrate the effectiveness of this approach.