pwc-archive/papers-with-abstracts huggingface dataset:
Adaptive Graph via Multiple Kernel Learning for Nonnegative Matrix Factorization
Authors: Jing-Yan Wang, Mustafa Abduljabbar
Date: 2012-08-19 00:00:00
Tasks: Clustering, Information Retrieval, Retrieval

Nonnegative Matrix Factorization (NMF) has been continuously evolving in
several areas like pattern recognition and information retrieval methods. It
factorizes a matrix into a product of 2 low-rank non-negative matrices that
will define parts-based, and linear representation of nonnegative data.
Recently, Graph regularized NMF (GrNMF) is proposed to find a compact
representation,which uncovers the hidden semantics and simultaneously respects
the intrinsic geometric structure. In GNMF, an affinity graph is constructed
from the original data space to encode the geometrical information. In this
paper, we propose a novel idea which engages a Multiple Kernel Learning
approach into refining the graph structure that reflects the factorization of
the matrix and the new data space. The GrNMF is improved by utilizing the graph
refined by the kernel learning, and then a novel kernel learning method is
introduced under the GrNMF framework. Our approach shows encouraging results of
the proposed algorithm in comparison to the state-of-the-art clustering
algorithms like NMF, GrNMF, SVD etc.
Discriminative Sparse Coding on Multi-Manifold for Data Representation and Classification
Authors: Jing-Yan Wang
Date: 2012-08-19 00:00:00
Tasks: General Classification

Sparse coding has been popularly used as an effective data representation
method in various applications, such as computer vision, medical imaging and
bioinformatics, etc. However, the conventional sparse coding algorithms and its
manifold regularized variants (graph sparse coding and Laplacian sparse
coding), learn the codebook and codes in a unsupervised manner and neglect the
class information available in the training set. To address this problem, in
this paper we propose a novel discriminative sparse coding method based on
multi-manifold, by learning discriminative class-conditional codebooks and
sparse codes from both data feature space and class labels. First, the entire
training set is partitioned into multiple manifolds according to the class
labels. Then, we formulate the sparse coding as a manifold-manifold matching
problem and learn class-conditional codebooks and codes to maximize the
manifold margins of different classes. Lastly, we present a data point-manifold
matching error based strategy to classify the unlabeled data point.
Experimental results on somatic mutations identification and breast tumors
classification in ultrasonic images tasks demonstrate the efficacy of the
proposed data representation-classification approach.
Predicting Network Attacks Using Ontology-Driven Inference
Authors: Ahmad Salahi, Morteza Ansarinia
Date: 2013-04-03 00:00:00
Tasks: Intrusion Detection, Management

Graph knowledge models and ontologies are very powerful modeling and re
asoning tools. We propose an effective approach to model network attacks and
attack prediction which plays important roles in security management. The goals
of this study are: First we model network attacks, their prerequisites and
consequences using knowledge representation methods in order to provide
description logic reasoning and inference over attack domain concepts. And
secondly, we propose an ontology-based system which predicts potential attacks
using inference and observing information which provided by sensory inputs. We
generate our ontology and evaluate corresponding methods using CAPEC, CWE, and
CVE hierarchical datasets. Results from experiments show significant capability
improvements comparing to traditional hierarchical and relational models.
Proposed method also reduces false alarms and improves intrusion detection
effectiveness.
Duality in STRIPS planning
Authors: Martin Suda
Date: 2013-04-03 00:00:00

We describe a duality mapping between STRIPS planning tasks. By exchanging
the initial and goal conditions, taking their respective complements, and
swapping for every action its precondition and delete list, one obtains for
every STRIPS task its dual version, which has a solution if and only if the
original does. This is proved by showing that the described transformation
essentially turns progression (forward search) into regression (backward
search) and vice versa.
  The duality sheds new light on STRIPS planning by allowing a transfer of
ideas from one search approach to the other. It can be used to construct new
algorithms from old ones, or (equivalently) to obtain new benchmarks from
existing ones. Experiments show that the dual versions of IPC benchmarks are in
general quite difficult for modern planners. This may be seen as a new
challenge. On the other hand, the cases where the dual versions are easier to
solve demonstrate that the duality can also be made useful in practice.
Improved Anomaly Detection in Crowded Scenes via Cell-based Analysis of Foreground Speed, Size and Texture
Authors: Vikas Reddy, Conrad Sanderson, Brian C. Lovell
Date: 2013-04-03 00:00:00
Tasks: Anomaly Detection, Density Estimation, Foreground Segmentation, Optical Flow Estimation

A robust and efficient anomaly detection technique is proposed, capable of
dealing with crowded scenes where traditional tracking based approaches tend to
fail. Initial foreground segmentation of the input frames confines the analysis
to foreground objects and effectively ignores irrelevant background dynamics.
Input frames are split into non-overlapping cells, followed by extracting
features based on motion, size and texture from each cell. Each feature type is
independently analysed for the presence of an anomaly. Unlike most methods, a
refined estimate of object motion is achieved by computing the optical flow of
only the foreground pixels. The motion and size features are modelled by an
approximated version of kernel density estimation, which is computationally
efficient even for large training datasets. Texture features are modelled by an
adaptively grown codebook, with the number of entries in the codebook selected
in an online fashion. Experiments on the recently published UCSD Anomaly
Detection dataset show that the proposed method obtains considerably better
results than three recent approaches: MPPCA, social force, and mixture of
dynamic textures (MDT). The proposed method is also several orders of magnitude
faster than MDT, the next best performing method.
Learning DNF Expressions from Fourier Spectrum
Authors: Vitaly Feldman
Date: 2012-03-03 00:00:00
Tasks: Learning Theory, PAC learning

Since its introduction by Valiant in 1984, PAC learning of DNF expressions
remains one of the central problems in learning theory. We consider this
problem in the setting where the underlying distribution is uniform, or more
generally, a product distribution. Kalai, Samorodnitsky and Teng (2009) showed
that in this setting a DNF expression can be efficiently approximated from its
"heavy" low-degree Fourier coefficients alone. This is in contrast to previous
approaches where boosting was used and thus Fourier coefficients of the target
function modified by various distributions were needed. This property is
crucial for learning of DNF expressions over smoothed product distributions, a
learning model introduced by Kalai et al. (2009) and inspired by the seminal
smoothed analysis model of Spielman and Teng (2001).
  We introduce a new approach to learning (or approximating) a polynomial
threshold functions which is based on creating a function with range [-1,1]
that approximately agrees with the unknown function on low-degree Fourier
coefficients. We then describe conditions under which this is sufficient for
learning polynomial threshold functions. Our approach yields a new, simple
algorithm for approximating any polynomial-size DNF expression from its "heavy"
low-degree Fourier coefficients alone. Our algorithm greatly simplifies the
proof of learnability of DNF expressions over smoothed product distributions.
We also describe an application of our algorithm to learning monotone DNF
expressions over product distributions. Building on the work of Servedio
(2001), we give an algorithm that runs in time $\poly((s \cdot
\log{(s/\eps)})^{\log{(s/\eps)}}, n)$, where $s$ is the size of the target DNF
expression and $\eps$ is the accuracy. This improves on $\poly((s \cdot
\log{(ns/\eps)})^{\log{(s/\eps)} \cdot \log{(1/\eps)}}, n)$ bound of Servedio
(2001).
Coalitional Manipulation for Schulze's Rule
Authors: Serge Gaspers, Thomas Kalinowski, Nina Narodytska, Toby Walsh
Date: 2013-04-03 00:00:00
Tasks: Open-Ended Question Answering

Schulze's rule is used in the elections of a large number of organizations
including Wikimedia and Debian. Part of the reason for its popularity is the
large number of axiomatic properties, like monotonicity and Condorcet
consistency, which it satisfies. We identify a potential shortcoming of
Schulze's rule: it is computationally vulnerable to manipulation. In
particular, we prove that computing an unweighted coalitional manipulation
(UCM) is polynomial for any number of manipulators. This result holds for both
the unique winner and the co-winner versions of UCM. This resolves an open
question stated by Parkes and Xia (2012). We also prove that computing a
weighted coalitional manipulation (WCM) is polynomial for a bounded number of
candidates. Finally, we discuss the relation between the unique winner UCM
problem and the co-winner UCM problem and argue that they have substantially
different necessary and sufficient conditions for the existence of a successful
manipulation.
A Fast Semidefinite Approach to Solving Binary Quadratic Problems
Authors: Peng Wang, Chunhua Shen, Anton Van Den Hengel
Date: 2013-04-03 00:00:00
Proceeding: CVPR 2013 6
Tasks: Clustering, Image Segmentation, Segmentation, Semantic Segmentation

Many computer vision problems can be formulated as binary quadratic programs
(BQPs). Two classic relaxation methods are widely used for solving BQPs,
namely, spectral methods and semidefinite programming (SDP), each with their
own advantages and disadvantages. Spectral relaxation is simple and easy to
implement, but its bound is loose. Semidefinite relaxation has a tighter bound,
but its computational complexity is high for large scale problems. We present a
new SDP formulation for BQPs, with two desirable properties. First, it has a
similar relaxation bound to conventional SDP formulations. Second, compared
with conventional SDP methods, the new SDP formulation leads to a significantly
more efficient and scalable dual optimization approach, which has the same
degree of complexity as spectral methods. Extensive experiments on various
applications including clustering, image segmentation, co-segmentation and
registration demonstrate the usefulness of our SDP formulation for solving
large-scale BQPs.
Multiscale Hybrid Non-local Means Filtering Using Modified Similarity Measure
Authors: Zahid Hussain Shamsi, Dai-Gyoung Kim
Date: 2013-04-03 00:00:00
Tasks: Denoising, Image Denoising

A new multiscale implementation of non-local means filtering for image
denoising is proposed. The proposed algorithm also introduces a modification of
similarity measure for patch comparison. The standard Euclidean norm is
replaced by weighted Euclidean norm for patch based comparison. Assuming the
patch as an oriented surface, notion of normal vector patch is being associated
with each patch. The inner product of these normal vector patches is then used
in weighted Euclidean distance of photometric patches as the weight factor. The
algorithm involves two steps: The first step is multiscale implementation of an
accelerated non-local means filtering in the stationary wavelet domain to
obtain a refined version of the noisy patches for later comparison. This step
is inspired by a preselection phase of finding similar patches in various
non-local means approaches. The next step is to apply the modified non-local
means filtering to the noisy image using the reference patches obtained in the
first step. These refined patches contain less noise, and consequently the
computation of normal vectors and partial derivatives is more accurate.
Experimental results indicate equivalent or better performance of proposed
algorithm as compared to various state of the art algorithms.
O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
Authors: Lijun Zhang, Tianbao Yang, Rong Jin, Xiaofei He
Date: 2013-04-02 00:00:00
Tasks: Stochastic Optimization

Traditional algorithms for stochastic optimization require projecting the
solution at each iteration into a given domain to ensure its feasibility. When
facing complex domains, such as positive semi-definite cones, the projection
operation can be expensive, leading to a high computational cost per iteration.
In this paper, we present a novel algorithm that aims to reduce the number of
projections for stochastic optimization. The proposed algorithm combines the
strength of several recent developments in stochastic optimization, including
mini-batch, extra-gradient, and epoch gradient descent, in order to effectively
explore the smoothness and strong convexity. We show, both in expectation and
with a high probability, that when the objective function is both smooth and
strongly convex, the proposed algorithm achieves the optimal $O(1/T)$ rate of
convergence with only $O(\log T)$ projections. Our empirical study verifies the
theoretical result.
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees
Authors: Vitaly Feldman, Pravesh Kothari, Jan Vondrak
Date: 2013-04-02 00:00:00
Tasks: Attribute, PAC learning

We study the complexity of approximate representation and learning of
submodular functions over the uniform distribution on the Boolean hypercube
$\{0,1\}^n$. Our main result is the following structural theorem: any
submodular function is $\epsilon$-close in $\ell_2$ to a real-valued decision
tree (DT) of depth $O(1/\epsilon^2)$. This immediately implies that any
submodular function is $\epsilon$-close to a function of at most
$2^{O(1/\epsilon^2)}$ variables and has a spectral $\ell_1$ norm of
$2^{O(1/\epsilon^2)}$. It also implies the closest previous result that states
that submodular functions can be approximated by polynomials of degree
$O(1/\epsilon^2)$ (Cheraghchi et al., 2012). Our result is proved by
constructing an approximation of a submodular function by a DT of rank
$4/\epsilon^2$ and a proof that any rank-$r$ DT can be $\epsilon$-approximated
by a DT of depth $\frac{5}{2}(r+\log(1/\epsilon))$.
  We show that these structural results can be exploited to give an
attribute-efficient PAC learning algorithm for submodular functions running in
time $\tilde{O}(n^2) \cdot 2^{O(1/\epsilon^{4})}$. The best previous algorithm
for the problem requires $n^{O(1/\epsilon^{2})}$ time and examples (Cheraghchi
et al., 2012) but works also in the agnostic setting. In addition, we give
improved learning algorithms for a number of related settings.
  We also prove that our PAC and agnostic learning algorithms are essentially
optimal via two lower bounds: (1) an information-theoretic lower bound of
$2^{\Omega(1/\epsilon^{2/3})}$ on the complexity of learning monotone
submodular functions in any reasonable model; (2) computational lower bound of
$n^{\Omega(1/\epsilon^{2/3})}$ based on a reduction to learning of sparse
parities with noise, widely-believed to be intractable. These are the first
lower bounds for learning of submodular functions over the uniform
distribution.
Pedestrian Detection with Unsupervised Multi-Stage Feature Learning
Authors: Pierre Sermanet, Koray Kavukcuoglu, Soumith Chintala, Yann Lecun
Date: 2012-12-01 00:00:00
Proceeding: CVPR 2013 6
Tasks: Pedestrian Detection

Pedestrian detection is a problem of considerable practical interest. Adding
to the list of successful applications of deep learning methods to vision, we
report state-of-the-art and competitive results on all major pedestrian
datasets with a convolutional network model. The model uses a few new twists,
such as multi-stage features, connections that skip layers to integrate global
shape information with local distinctive motif information, and an unsupervised
method based on convolutional sparse coding to pre-train the filters at each
stage.
Sparsistent Estimation of Time-Varying Discrete Markov Random Fields
Authors: Mladen Kolar, Eric P. Xing
Date: 2009-07-14 00:00:00
Tasks: regression, Time Series, Time Series Analysis

Network models have been popular for modeling and representing complex
relationships and dependencies between observed variables. When data comes from
a dynamic stochastic process, a single static network model cannot adequately
capture transient dependencies, such as, gene regulatory dependencies
throughout a developmental cycle of an organism. Kolar et al (2010b) proposed a
method based on kernel-smoothing l1-penalized logistic regression for
estimating time-varying networks from nodal observations collected from a
time-series of observational data. In this paper, we establish conditions under
which the proposed method consistently recovers the structure of a time-varying
network. This work complements previous empirical findings by providing sound
theoretical guarantees for the proposed estimation procedure. For completeness,
we include numerical simulations in the paper.
Event management for large scale event-driven digital hardware spiking neural networks
Authors: Louis-Charles Caron, \and Michiel D'Haene, \and Frédéric Mailhot, \and Benjamin Schrauwen, \and Jean Rouat
Date: 2013-04-02 00:00:00
Tasks: Image Segmentation, Management, Semantic Segmentation

The interest in brain-like computation has led to the design of a plethora of
innovative neuromorphic systems. Individually, spiking neural networks (SNNs),
event-driven simulation and digital hardware neuromorphic systems get a lot of
attention. Despite the popularity of event-driven SNNs in software, very few
digital hardware architectures are found. This is because existing hardware
solutions for event management scale badly with the number of events. This
paper introduces the structured heap queue, a pipelined digital hardware data
structure, and demonstrates its suitability for event management. The
structured heap queue scales gracefully with the number of events, allowing the
efficient implementation of large scale digital hardware event-driven SNNs. The
scaling is linear for memory, logarithmic for logic resources and constant for
processing time. The use of the structured heap queue is demonstrated on
field-programmable gate array (FPGA) with an image segmentation experiment and
a SNN of 65~536 neurons and 513~184 synapses. Events can be processed at the
rate of 1 every 7 clock cycles and a 406$\times$158 pixel image is segmented in
200 ms.
Disjunctive Logic Programs versus Normal Logic Programs
Authors: Heng Zhang, Yan Zhang
Date: 2013-04-02 00:00:00
Tasks: Translation

This paper focuses on the expressive power of disjunctive and normal logic
programs under the stable model semantics over finite, infinite, or arbitrary
structures. A translation from disjunctive logic programs into normal logic
programs is proposed and then proved to be sound over infinite structures. The
equivalence of expressive power of two kinds of logic programs over arbitrary
structures is shown to coincide with that over finite structures, and coincide
with whether or not NP is closed under complement. Over finite structures, the
intranslatability from disjunctive logic programs to normal logic programs is
also proved if arities of auxiliary predicates and functions are bounded in a
certain way.
A Semiparametric Bayesian Extreme Value Model Using a Dirichlet Process Mixture of Gamma Densities
Authors: Jairo Fuquene
Date: 2013-04-02 00:00:00
Tasks: Density Estimation

In this paper we propose a model with a Dirichlet process mixture of gamma
densities in the bulk part below threshold and a generalized Pareto density in
the tail for extreme value estimation. The proposed model is simple and
flexible allowing us posterior density estimation and posterior inference for
high quantiles. The model works well even for small sample sizes and in the
absence of prior information. We evaluate the performance of the proposed model
through a simulation study. Finally, the proposed model is applied to a real
environmental data.
On the definition of a confounder
Authors: Tyler J. VanderWeele, Ilya Shpitser
Date: 2013-04-02 00:00:00
Tasks: Causal Inference, counterfactual, Math

The causal inference literature has provided a clear formal definition of
confounding expressed in terms of counterfactual independence. The literature
has not, however, come to any consensus on a formal definition of a confounder,
as it has given priority to the concept of confounding over that of a
confounder. We consider a number of candidate definitions arising from various
more informal statements made in the literature. We consider the properties
satisfied by each candidate definition, principally focusing on (i) whether
under the candidate definition control for all "confounders" suffices to
control for "confounding" and (ii) whether each confounder in some context
helps eliminate or reduce confounding bias. Several of the candidate
definitions do not have these two properties. Only one candidate definition of
those considered satisfies both properties. We propose that a "confounder" be
defined as a pre-exposure covariate C for which there exists a set of other
covariates X such that effect of the exposure on the outcome is unconfounded
conditional on (X,C) but such that for no proper subset of (X,C) is the effect
of the exposure on the outcome unconfounded given the subset. We also provide a
conditional analogue of the above definition; and we propose a variable that
helps reduce bias but not eliminate bias be referred to as a "surrogate
confounder." These definitions are closely related to those given by Robins and
Morgenstern [Comput. Math. Appl. 14 (1987) 869-916]. The implications that hold
among the various candidate definitions are discussed.
Evolution and the structure of learning agents
Authors: Alok Raj
Date: 2012-09-18 00:00:00

This paper presents the thesis that all learning agents of finite information
size are limited by their informational structure in what goals they can
efficiently learn to achieve in a complex environment. Evolutionary change is
critical for creating the required structure for all learning agents in any
complex environment. The thesis implies that there is no efficient universal
learning algorithm. An agent can go past the learning limits imposed by its
structure only by slow evolutionary change or blind search which in a very
complex environment can only give an agent an inefficient universal learning
capability that can work only in evolutionary timescales or improbable luck.
Stroke-Based Cursive Character Recognition
Authors: K. C. Santosh, E. Iwata
Date: 2013-04-01 00:00:00
Tasks: Handwriting Recognition

Human eye can see and read what is written or displayed either in natural
handwriting or in printed format. The same work in case the machine does is
called handwriting recognition. Handwriting recognition can be broken down into
two categories: off-line and on-line. ...