pwc-archive/papers-with-abstracts huggingface dataset:
Feature Selection for Linear SVM with Provable Guarantees
Authors: Saurabh Paul, Malik Magdon-Ismail, Petros Drineas
Date: 2014-06-01 00:00:00
Tasks: feature selection

We give two provably accurate feature-selection techniques for the linear
SVM. The algorithms run in deterministic and randomized time respectively. Our
algorithms can be used in an unsupervised or supervised setting. The supervised
approach is based on sampling features from support vectors. We prove that the
margin in the feature space is preserved to within $\epsilon$-relative error of
the margin in the full feature space in the worst-case. In the unsupervised
setting, we also provide worst-case guarantees of the radius of the minimum
enclosing ball, thereby ensuring comparable generalization as in the full
feature space and resolving an open problem posed in Dasgupta et al. We present
extensive experiments on real-world datasets to support our theory and to
demonstrate that our method is competitive and often better than prior
state-of-the-art, for which there are no known provable guarantees.
On the Incommensurability Phenomenon
Authors: Donniell E. Fishkind, Cencheng Shen, Youngser Park, Carey E. Priebe
Date: 2013-01-09 00:00:00

Suppose that two large, multi-dimensional data sets are each noisy
measurements of the same underlying random process, and principle components
analysis is performed separately on the data sets to reduce their
dimensionality. In some circumstances it may happen that the two
lower-dimensional data sets have an inordinately large Procrustean
fitting-error between them. The purpose of this manuscript is to quantify this
"incommensurability phenomenon." In particular, under specified conditions, the
square Procrustean fitting-error of the two normalized lower-dimensional data
sets is (asymptotically) a convex combination (via a correlation parameter) of
the Hausdorff distance between the projection subspaces and the maximum
possible value of the square Procrustean fitting-error for normalized data. We
show how this gives rise to the incommensurability phenomenon, and we employ
illustrative simulations as well as a real data experiment to explore how the
incommensurability phenomenon may have an appreciable impact.
A Fingerprint-based Access Control using Principal Component Analysis and Edge Detection
Authors: E. F. Melo, H. M. de Oliveira
Date: 2015-02-06 00:00:00
Tasks: Decision Making, Edge Detection

This paper presents a novel approach for deciding on the appropriateness or
not of an acquired fingerprint image into a given database. The process begins
with the assembly of a training base in an image space constructed by combining
Principal Component Analysis (PCA) and edge detection. Then, the parameter H, a
new feature that helps in the decision making about the relevance of a
fingerprint image in databases, is derived from a relationship between
Euclidean and Mahalanobian distances. This procedure ends with the lifting of
the curve of the Receiver Operating Characteristic (ROC), where the thresholds
defined on the parameter H are chosen according to the acceptable rates of
false positives and false negatives.
Generalized Inpainting Method for Hyperspectral Image Acquisition
Authors: K. Degraux, V. Cambareri, L. Jacques, B. Geelen, C. Blanch, G. Lafruit
Date: 2015-02-06 00:00:00
Tasks: compressed sensing, Demosaicking

A recently designed hyperspectral imaging device enables multiplexed
acquisition of an entire data volume in a single snapshot thanks to
monolithically-integrated spectral filters. Such an agile imaging technique
comes at the cost of a reduced spatial resolution and the need for a
demosaicing procedure on its interleaved data. In this work, we address both
issues and propose an approach inspired by recent developments in compressed
sensing and analysis sparse models. We formulate our superresolution and
demosaicing task as a 3-D generalized inpainting problem. Interestingly, the
target spatial resolution can be adjusted for mitigating the compression level
of our sensing. The reconstruction procedure uses a fast greedy method called
Pseudo-inverse IHT. We also show on simulations that a random arrangement of
the spectral filters on the sensor is preferable to regular mosaic layout as it
improves the quality of the reconstruction. The efficiency of our technique is
demonstrated through numerical experiments on both synthetic and real data as
acquired by the snapshot imager.
Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification
Authors: Kaiming He, Xiangyu Zhang, Shaoqing Ren, Jian Sun
Date: 2015-02-06 00:00:00
Proceeding: ICCV 2015 12
Tasks: General Classification, image-classification, Image Classification

Rectified activation units (rectifiers) are essential for state-of-the-art
neural networks. In this work, we study rectifier neural networks for image
classification from two aspects. First, we propose a Parametric Rectified
Linear Unit (PReLU) that generalizes the traditional rectified unit. PReLU
improves model fitting with nearly zero extra computational cost and little
overfitting risk. Second, we derive a robust initialization method that
particularly considers the rectifier nonlinearities. This method enables us to
train extremely deep rectified models directly from scratch and to investigate
deeper or wider network architectures. Based on our PReLU networks
(PReLU-nets), we achieve 4.94% top-5 test error on the ImageNet 2012
classification dataset. This is a 26% relative improvement over the ILSVRC 2014
winner (GoogLeNet, 6.66%). To our knowledge, our result is the first to surpass
human-level performance (5.1%, Russakovsky et al.) on this visual recognition
challenge.
Hierarchical Maximum-Margin Clustering
Authors: Guang-Tong Zhou, Sung Ju Hwang, Mark Schmidt, Leonid Sigal, Greg Mori
Date: 2015-02-06 00:00:00
Tasks: Clustering

We present a hierarchical maximum-margin clustering method for unsupervised
data analysis. Our method extends beyond flat maximum-margin clustering, and
performs clustering recursively in a top-down manner. We propose an effective
greedy splitting criteria for selecting which cluster to split next, and employ
regularizers that enforce feature sharing/competition for capturing data
semantics. Experimental results obtained on four standard datasets show that
our method outperforms flat and hierarchical clustering baselines, while
forming clean and semantically meaningful cluster hierarchies.
Unsupervised Fusion Weight Learning in Multiple Classifier Systems
Authors: Anurag Kumar, Bhiksha Raj
Date: 2015-02-06 00:00:00

In this paper we present an unsupervised method to learn the weights with
which the scores of multiple classifiers must be combined in classifier fusion
settings. We also introduce a novel metric for ranking instances based on an
index which depends upon the rank of weighted scores of test points among the
weighted scores of training points. We show that the optimized index can be
used for computing measures such as average precision. Unlike most classifier
fusion methods where a single weight is learned to weigh all examples our
method learns instance-specific weights. The problem is formulated as learning
the weight which maximizes a clarity index; subsequently the index itself and
the learned weights both are used separately to rank all the test points. Our
method gives an unsupervised method of optimizing performance on actual test
data, unlike the well known stacking-based methods where optimization is done
over a labeled training set. Moreover, we show that our method is tolerant to
noisy classifiers and can be used for selecting N-best classifiers.
Crowded Scene Analysis: A Survey
Authors: Teng Li, Huan Chang, Meng Wang, Bingbing Ni, Richang Hong, Shuicheng Yan
Date: 2015-02-06 00:00:00
Tasks: Anomaly Detection, Survey

Automated scene analysis has been a topic of great interest in computer
vision and cognitive science. Recently, with the growth of crowd phenomena in
the real world, crowded scene analysis has attracted much attention. However,
the visual occlusions and ambiguities in crowded scenes, as well as the complex
behaviors and scene semantics, make the analysis a challenging task. In the
past few years, an increasing number of works on crowded scene analysis have
been reported, covering different aspects including crowd motion pattern
learning, crowd behavior and activity analysis, and anomaly detection in
crowds. This paper surveys the state-of-the-art techniques on this topic. We
first provide the background knowledge and the available features related to
crowded scenes. Then, existing models, popular algorithms, evaluation
protocols, as well as system performance are provided corresponding to
different aspects of crowded scene analysis. We also outline the available
datasets for performance evaluation. Finally, some research problems and
promising future directions are presented with discussions.
Learning Efficient Anomaly Detectors from $K$-NN Graphs
Authors: Jing Qian, Jonathan Root, Venkatesh Saligrama
Date: 2015-02-06 00:00:00
Tasks: Anomaly Detection, Computational Efficiency, Learning-To-Rank

We propose a non-parametric anomaly detection algorithm for high dimensional
data. We score each datapoint by its average $K$-NN distance, and rank them
accordingly. We then train limited complexity models to imitate these scores
based on the max-margin learning-to-rank framework. A test-point is declared as
an anomaly at $\alpha$-false alarm level if the predicted score is in the
$\alpha$-percentile. The resulting anomaly detector is shown to be
asymptotically optimal in that for any false alarm rate $\alpha$, its decision
region converges to the $\alpha$-percentile minimum volume level set of the
unknown underlying density. In addition, we test both the statistical
performance and computational efficiency of our algorithm on a number of
synthetic and real-data experiments. Our results demonstrate the superiority of
our algorithm over existing $K$-NN based anomaly detection algorithms, with
significant computational savings.
Multi-Action Recognition via Stochastic Modelling of Optical Flow and Gradients
Authors: Johanna Carvajal, Conrad Sanderson, Chris McCool, Brian C. Lovell
Date: 2015-02-06 00:00:00
Tasks: Action Recognition, Classification, General Classification, Optical Flow Estimation, Segmentation, Temporal Action Localization

In this paper we propose a novel approach to multi-action recognition that
performs joint segmentation and classification. This approach models each
action using a Gaussian mixture using robust low-dimensional action features.
Segmentation is achieved by performing classification on overlapping temporal
windows, which are then merged to produce the final result. This approach is
considerably less complicated than previous methods which use dynamic
programming or computationally expensive hidden Markov models (HMMs). Initial
experiments on a stitched version of the KTH dataset show that the proposed
approach achieves an accuracy of 78.3%, outperforming a recent HMM-based
approach which obtained 71.2%.
Multiscale Event Detection in Social Media
Authors: Xiaowen Dong, Dimitrios Mavroeidis, Francesco Calabrese, Pascal Frossard
Date: 2014-04-25 00:00:00
Tasks: Clustering, Event Detection

Event detection has been one of the most important research topics in social
media analysis. Most of the traditional approaches detect events based on fixed
temporal and spatial resolutions, while in reality events of different scales
usually occur simultaneously, namely, they span different intervals in time and
space. In this paper, we propose a novel approach towards multiscale event
detection using social media data, which takes into account different temporal
and spatial scales of events in the data. Specifically, we explore the
properties of the wavelet transform, which is a well-developed multiscale
transform in signal processing, to enable automatic handling of the interaction
between temporal and spatial scales. We then propose a novel algorithm to
compute a data similarity graph at appropriate scales and detect events of
different scales simultaneously by a single graph-based clustering process.
Furthermore, we present spatiotemporal statistical analysis of the noisy
information present in the data stream, which allows us to define a novel
term-filtering procedure for the proposed event detection algorithm and helps
us study its behavior using simulated noisy data. Experimental results on both
synthetically generated data and real world data collected from Twitter
demonstrate the meaningfulness and effectiveness of the proposed approach. Our
framework further extends to numerous application domains that involve
multiscale and multiresolution data analysis.
A Framework for Symmetric Part Detection in Cluttered Scenes
Authors: Tom Lee, Sanja Fidler, Alex Levinshtein, Cristian Sminchisescu, Sven Dickinson
Date: 2015-02-05 00:00:00

The role of symmetry in computer vision has waxed and waned in importance
during the evolution of the field from its earliest days. At first figuring
prominently in support of bottom-up indexing, it fell out of favor as shape
gave way to appearance and recognition gave way to detection. With a strong
prior in the form of a target object, the role of the weaker priors offered by
perceptual grouping was greatly diminished. However, as the field returns to
the problem of recognition from a large database, the bottom-up recovery of the
parts that make up the objects in a cluttered scene is critical for their
recognition. The medial axis community has long exploited the ubiquitous
regularity of symmetry as a basis for the decomposition of a closed contour
into medial parts. However, today's recognition systems are faced with
cluttered scenes, and the assumption that a closed contour exists, i.e. that
figure-ground segmentation has been solved, renders much of the medial axis
community's work inapplicable. In this article, we review a computational
framework, previously reported in Lee et al. (2013), Levinshtein et al. (2009,
2013), that bridges the representation power of the medial axis and the need to
recover and group an object's parts in a cluttered scene. Our framework is
rooted in the idea that a maximally inscribed disc, the building block of a
medial axis, can be modeled as a compact superpixel in the image. We evaluate
the method on images of cluttered scenes.
Monitoring Term Drift Based on Semantic Consistency in an Evolving Vector Field
Authors: Peter Wittek, Sándor Darányi, Efstratios Kontopoulos, Theodoros Moysiadis, Ioannis Kompatsiaris
Date: 2015-02-05 00:00:00
Tasks: Lexical Analysis, Philosophy

Based on the Aristotelian concept of potentiality vs. actuality allowing for
the study of energy and dynamics in language, we propose a field approach to
lexical analysis. Falling back on the distributional hypothesis to
statistically model word meaning, we used evolving fields as a metaphor to
express time-dependent changes in a vector space model by a combination of
random indexing and evolving self-organizing maps (ESOM). To monitor semantic
drifts within the observation period, an experiment was carried out on the term
space of a collection of 12.8 million Amazon book reviews. For evaluation, the
semantic consistency of ESOM term clusters was compared with their respective
neighbourhoods in WordNet, and contrasted with distances among term vectors by
random indexing. We found that at 0.05 level of significance, the terms in the
clusters showed a high level of semantic consistency. Tracking the drift of
distributional patterns in the term space across time periods, we found that
consistency decreased, but not at a statistically significant level. Our method
is highly scalable, with interpretations in philosophy.
Mesh Learning for Classifying Cognitive Processes
Authors: Mete Ozay, Ilke Öztekin, Uygar Öztekin, Fatos T. Yarman Vural
Date: 2012-05-10 00:00:00
Tasks: ARC

A relatively recent advance in cognitive neuroscience has been multi-voxel
pattern analysis (MVPA), which enables researchers to decode brain states
and/or the type of information represented in the brain during a cognitive
operation. MVPA methods utilize machine learning algorithms to distinguish
among types of information or cognitive states represented in the brain, based
on distributed patterns of neural activity. In the current investigation, we
propose a new approach for representation of neural data for pattern analysis,
namely a Mesh Learning Model. In this approach, at each time instant, a star
mesh is formed around each voxel, such that the voxel corresponding to the
center node is surrounded by its p-nearest neighbors. The arc weights of each
mesh are estimated from the voxel intensity values by least squares method. The
estimated arc weights of all the meshes, called Mesh Arc Descriptors (MADs),
are then used to train a classifier, such as Neural Networks, k-Nearest
Neighbor, Na\"ive Bayes and Support Vector Machines. The proposed Mesh Model
was tested on neuroimaging data acquired via functional magnetic resonance
imaging (fMRI) during a recognition memory experiment using categorized word
lists, employing a previously established experimental paradigm (\"Oztekin &
Badre, 2011). Results suggest that the proposed Mesh Learning approach can
provide an effective algorithm for pattern analysis of brain activity during
cognitive processing.
Arrhythmia Detection using Mutual Information-Based Integration Method
Authors: Othman Soufan, Samer Arafat
Date: 2015-02-05 00:00:00
Tasks: Arrhythmia Detection, General Classification, Majority Voting Classifier

The aim of this paper is to propose an application of mutual
information-based ensemble methods to the analysis and classification of heart
beats associated with different types of Arrhythmia. Models of multilayer
perceptrons, support vector machines, and radial basis function neural networks
were trained and tested using the MIT-BIH arrhythmia database. This research
brings a focus to an ensemble method that, to our knowledge, is a novel
application in the area of ECG Arrhythmia detection. The proposed classifier
ensemble method showed improved performance, relative to either majority voting
classifier integration or to individual classifier performance. The overall
ensemble accuracy was 98.25%.
Differentially- and non-differentially-private random decision trees
Authors: Mariusz Bojarski, Anna Choromanska, Krzysztof Choromanski, Yann Lecun
Date: 2014-10-26 00:00:00

We consider supervised learning with random decision trees, where the tree
construction is completely random. The method is popularly used and works well
in practice despite the simplicity of the setting, but its statistical
mechanism is not yet well-understood. In this paper we provide strong
theoretical guarantees regarding learning with random decision trees. We
analyze and compare three different variants of the algorithm that have minimal
memory requirements: majority voting, threshold averaging and probabilistic
averaging. The random structure of the tree enables us to adapt these methods
to a differentially-private setting thus we also propose differentially-private
versions of all three schemes. We give upper-bounds on the generalization error
and mathematically explain how the accuracy depends on the number of random
decision trees. Furthermore, we prove that only logarithmic (in the size of the
dataset) number of independently selected random decision trees suffice to
correctly classify most of the data, even when differential-privacy guarantees
must be maintained. We empirically show that majority voting and threshold
averaging give the best accuracy, also for conservative users requiring high
privacy guarantees. Furthermore, we demonstrate that a simple majority voting
rule is an especially good candidate for the differentially-private classifier
since it is much less sensitive to the choice of forest parameters than other
methods.
A Confident Information First Principle for Parametric Reduction and Model Selection of Boltzmann Machines
Authors: Xiaozhao Zhao, Yuexian Hou, Dawei Song, Wenjie Li
Date: 2015-02-05 00:00:00
Tasks: Density Estimation, Dimensionality Reduction, Model Selection

Typical dimensionality reduction (DR) methods are often data-oriented,
focusing on directly reducing the number of random variables (features) while
retaining the maximal variations in the high-dimensional data. In unsupervised
situations, one of the main limitations of these methods lies in their
dependency on the scale of data features. This paper aims to address the
problem from a new perspective and considers model-oriented dimensionality
reduction in parameter spaces of binary multivariate distributions.
  Specifically, we propose a general parameter reduction criterion, called
Confident-Information-First (CIF) principle, to maximally preserve confident
parameters and rule out less confident parameters. Formally, the confidence of
each parameter can be assessed by its contribution to the expected Fisher
information distance within the geometric manifold over the neighbourhood of
the underlying real distribution.
  We then revisit Boltzmann machines (BM) from a model selection perspective
and theoretically show that both the fully visible BM (VBM) and the BM with
hidden units can be derived from the general binary multivariate distribution
using the CIF principle. This can help us uncover and formalize the essential
parts of the target density that BM aims to capture and the non-essential parts
that BM should discard. Guided by the theoretical analysis, we develop a
sample-specific CIF for model selection of BM that is adaptive to the observed
samples. The method is studied in a series of density estimation experiments
and has been shown effective in terms of the estimate accuracy.
Graph Partitioning for Independent Sets
Authors: Sebastian Lamm, Peter Sanders, Christian Schulz
Date: 2015-02-05 00:00:00
Tasks: graph partitioning

Computing maximum independent sets in graphs is an important problem in
computer science. In this paper, we develop an evolutionary algorithm to tackle
the problem. The core innovations of the algorithm are very natural combine
operations based on graph partitioning and local search algorithms. More
precisely, we employ a state-of-the-art graph partitioner to derive operations
that enable us to quickly exchange whole blocks of given independent sets. To
enhance newly computed offsprings we combine our operators with a local search
algorithm. Our experimental evaluation indicates that we are able to outperform
state-of-the-art algorithms on a variety of instances.
On Anomaly Ranking and Excess-Mass Curves
Authors: Nicolas Goix, Anne Sabourin, Stéphan Clémençon
Date: 2015-02-05 00:00:00
Tasks: Anomaly Detection

Learning how to rank multivariate unlabeled observations depending on their
degree of abnormality/novelty is a crucial problem in a wide range of
applications. In practice, it generally consists in building a real valued
"scoring" function on the feature space so as to quantify to which extent
observations should be considered as abnormal. In the 1-d situation,
measurements are generally considered as "abnormal" when they are remote from
central measures such as the mean or the median. Anomaly detection then relies
on tail analysis of the variable of interest. Extensions to the multivariate
setting are far from straightforward and it is precisely the main purpose of
this paper to introduce a novel and convenient (functional) criterion for
measuring the performance of a scoring function regarding the anomaly ranking
task, referred to as the Excess-Mass curve (EM curve). In addition, an adaptive
algorithm for building a scoring function based on unlabeled data X1 , . . . ,
Xn with a nearly optimal EM is proposed and is analyzed from a statistical
perspective.