pwc-archive/papers-with-abstracts huggingface dataset:
Tighter Low-rank Approximation via Sampling the Leveraged Element
Authors: Srinadh Bhojanapalli, Prateek Jain, Sujay Sanghavi
Date: 2014-10-14 00:00:00

In this work, we propose a new randomized algorithm for computing a low-rank
approximation to a given matrix. Taking an approach different from existing
literature, our method first involves a specific biased sampling, with an
element being chosen based on the leverage scores of its row and column, and
then involves weighted alternating minimization over the factored form of the
intended low-rank matrix, to minimize error only on these samples. Our method
can leverage input sparsity, yet produce approximations in {\em spectral} (as
opposed to the weaker Frobenius) norm; this combines the best aspects of
otherwise disparate current results, but with a dependence on the condition
number $\kappa = \sigma_1/\sigma_r$. In particular we require $O(nnz(M) +
\frac{n\kappa^2 r^5}{\epsilon^2})$ computations to generate a rank-$r$
approximation to $M$ in spectral norm. In contrast, the best existing method
requires $O(nnz(M)+ \frac{nr^2}{\epsilon^4})$ time to compute an approximation
in Frobenius norm. Besides the tightness in spectral norm, we have a better
dependence on the error $\epsilon$. Our method is naturally and highly
parallelizable.
  Our new approach enables two extensions that are interesting on their own.
The first is a new method to directly compute a low-rank approximation (in
efficient factored form) to the product of two given matrices; it computes a
small random set of entries of the product, and then executes weighted
alternating minimization (as before) on these. The sampling strategy is
different because now we cannot access leverage scores of the product matrix
(but instead have to work with input matrices). The second extension is an
improved algorithm with smaller communication complexity for the distributed
PCA setting (where each server has small set of rows of the matrix, and want to
compute low rank approximation with small amount of communication with other
servers).
Reducing the Effects of Detrimental Instances
Authors: Michael R. Smith, Tony Martinez
Date: 2014-06-09 00:00:00

Not all instances in a data set are equally beneficial for inducing a model
of the data. Some instances (such as outliers or noise) can be detrimental.
However, at least initially, the instances in a data set are generally
considered equally in machine learning algorithms. Many current approaches for
handling noisy and detrimental instances make a binary decision about whether
an instance is detrimental or not. In this paper, we 1) extend this paradigm by
weighting the instances on a continuous scale and 2) present a methodology for
measuring how detrimental an instance may be for inducing a model of the data.
We call our method of identifying and weighting detrimental instances reduced
detrimental instance learning (RDIL). We examine RIDL on a set of 54 data sets
and 5 learning algorithms and compare RIDL with other weighting and filtering
approaches. RDIL is especially useful for learning algorithms where every
instance can affect the classification boundary and the training instances are
considered individually, such as multilayer perceptrons trained with
backpropagation (MLPs). Our results also suggest that a more accurate estimate
of which instances are detrimental can have a significant positive impact for
handling them.
Presence-absence reasoning for evolutionary phenotypes
Authors: James P. Balhoff, T. Alexander Dececchi, Paula M. Mabee, Hilmar Lapp
Date: 2014-10-14 00:00:00

Nearly invariably, phenotypes are reported in the scientific literature in
meticulous detail, utilizing the full expressivity of natural language. Often
it is particularly these detailed observations (facts) that are of interest,
and thus specific to the research questions that motivated observing and
reporting them. However, research aiming to synthesize or integrate phenotype
data across many studies or even fields is often faced with the need to
abstract from detailed observations so as to construct phenotypic concepts that
are common across many datasets rather than specific to a few. Yet,
observations or facts that would fall under such abstracted concepts are
typically not directly asserted by the original authors, usually because they
are "obvious" according to common domain knowledge, and thus asserting them
would be deemed redundant by anyone with sufficient domain knowledge. For
example, a phenotype describing the length of a manual digit for an organism
implicitly means that the organism must have had a hand, and thus a forelimb;
the presence or absence of a forelimb may have supporting data across a far
wider range of taxa than the length of a particular manual digit. Here we
describe how within the Phenoscape project we use a pipeline of OWL axiom
generation and reasoning steps to infer taxon-specific presence/absence of
anatomical entities from anatomical phenotypes. Although presence/absence is
all but one, and a seemingly simple way to abstract phenotypes across data
sources, it can nonetheless be powerful for linking genotype to phenotype, and
it is particularly relevant for constructing synthetic morphological
supermatrices for comparative analysis; in fact presence/absence is one of the
prevailing character observation types in published character matrices.
A Non-Local Structure Tensor Based Approach for Multicomponent Image Recovery Problems
Authors: Giovanni Chierchia, Nelly Pustelnik, Beatrice Pesquet-Popescu, Jean-Christophe Pesquet
Date: 2014-03-21 00:00:00

Non-Local Total Variation (NLTV) has emerged as a useful tool in variational
methods for image recovery problems. In this paper, we extend the NLTV-based
regularization to multicomponent images by taking advantage of the Structure
Tensor (ST) resulting from the gradient of a multicomponent image. The proposed
approach allows us to penalize the non-local variations, jointly for the
different components, through various $\ell_{1,p}$ matrix norms with $p \ge 1$.
To facilitate the choice of the hyper-parameters, we adopt a constrained convex
optimization approach in which we minimize the data fidelity term subject to a
constraint involving the ST-NLTV regularization. The resulting convex
optimization problem is solved with a novel epigraphical projection method.
This formulation can be efficiently implemented thanks to the flexibility
offered by recent primal-dual proximal algorithms. Experiments are carried out
for multispectral and hyperspectral images. The results demonstrate the
interest of introducing a non-local structure tensor regularization and show
that the proposed approach leads to significant improvements in terms of
convergence speed over current state-of-the-art methods.
An exact mapping between the Variational Renormalization Group and Deep Learning
Authors: Pankaj Mehta, David J. Schwab
Date: 2014-10-14 00:00:00
Tasks: Deep Learning, speech-recognition, Speech Recognition

Deep learning is a broad set of techniques that uses multiple layers of
representation to automatically learn relevant features directly from
structured data. Recently, such techniques have yielded record-breaking results
on a diverse set of difficult machine learning tasks in computer vision, speech
recognition, and natural language processing. Despite the enormous success of
deep learning, relatively little is understood theoretically about why these
techniques are so successful at feature learning and compression. Here, we show
that deep learning is intimately related to one of the most important and
successful techniques in theoretical physics, the renormalization group (RG).
RG is an iterative coarse-graining scheme that allows for the extraction of
relevant features (i.e. operators) as a physical system is examined at
different length scales. We construct an exact mapping from the variational
renormalization group, first introduced by Kadanoff, and deep learning
architectures based on Restricted Boltzmann Machines (RBMs). We illustrate
these ideas using the nearest-neighbor Ising Model in one and two-dimensions.
Our results suggests that deep learning algorithms may be employing a
generalized RG-like scheme to learn relevant features from data.
POLYGLOT-NER: Massive Multilingual Named Entity Recognition
Authors: Rami Al-Rfou, Vivek Kulkarni, Bryan Perozzi, Steven Skiena
Date: 2014-10-14 00:00:00
Tasks: Diversity, Information Retrieval, Machine Translation, Multilingual Named Entity Recognition, named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER), NER, Retrieval, Translation, Word Embeddings

The increasing diversity of languages used on the web introduces a new level
of complexity to Information Retrieval (IR) systems. We can no longer assume
that textual content is written in one language or even the same language
family. In this paper, we demonstrate how to build massive multilingual
annotators with minimal human expertise and intervention. We describe a system
that builds Named Entity Recognition (NER) annotators for 40 major languages
using Wikipedia and Freebase. Our approach does not require NER human annotated
datasets or language specific resources like treebanks, parallel corpora, and
orthographic rules. The novelty of approach lies therein - using only language
agnostic techniques, while achieving competitive performance.
  Our method learns distributed word representations (word embeddings) which
encode semantic and syntactic features of words in each language. Then, we
automatically generate datasets from Wikipedia link structure and Freebase
attributes. Finally, we apply two preprocessing stages (oversampling and exact
surface form matching) which do not require any linguistic expertise.
  Our evaluation is two fold: First, we demonstrate the system performance on
human annotated datasets. Second, for languages where no gold-standard
benchmarks are available, we propose a new method, distant evaluation, based on
statistical machine translation.
Crowd Saliency Detection via Global Similarity Structure
Authors: Mei Kuan Lim, Ven Jyn Kok, Chen Change Loy, Chee Seng Chan
Date: 2014-10-14 00:00:00
Tasks: Saliency Detection

It is common for CCTV operators to overlook inter- esting events taking place
within the crowd due to large number of people in the crowded scene (i.e.
marathon, rally). Thus, there is a dire need to automate the detection of
salient crowd regions acquiring immediate attention for a more effective and
proactive surveillance. This paper proposes a novel framework to identify and
localize salient regions in a crowd scene, by transforming low-level features
extracted from crowd motion field into a global similarity structure. The
global similarity structure representation allows the discovery of the
intrinsic manifold of the motion dynamics, which could not be captured by the
low-level representation. Ranking is then performed on the global similarity
structure to identify a set of extrema. The proposed approach is unsupervised
so learning stage is eliminated. Experimental results on public datasets
demonstrates the effectiveness of exploiting such extrema in identifying
salient regions in various crowd scenarios that exhibit crowding, local
irregular motion, and unique motion areas such as sources and sinks.
Enhanced Random Forest with Image/Patch-Level Learning for Image Understanding
Authors: Wai Lam Hoo, Tae-Kyun Kim, Yuru Pei, Chee Seng Chan
Date: 2014-10-14 00:00:00

Image understanding is an important research domain in the computer vision
due to its wide real-world applications. For an image understanding framework
that uses the Bag-of-Words model representation, the visual codebook is an
essential part. Random forest (RF) as a tree-structure discriminative codebook
has been a popular choice. However, the performance of the RF can be degraded
if the local patch labels are poorly assigned. In this paper, we tackle this
problem by a novel way to update the RF codebook learning for a more
discriminative codebook with the introduction of the soft class labels,
estimated from the pLSA model based on a feedback scheme. The feedback scheme
is performed on both the image and patch levels respectively, which is in
contrast to the state- of-the-art RF codebook learning that focused on either
image or patch level only. Experiments on 15-Scene and C-Pascal datasets had
shown the effectiveness of the proposed method in image understanding task.
A Fusion Approach for Efficient Human Skin Detection
Authors: Wei Ren Tan, Chee Seng Chan, Pratheepan Yogarajah, Joan Condell
Date: 2014-10-14 00:00:00

A reliable human skin detection method that is adaptable to different human
skin colours and illu- mination conditions is essential for better human skin
segmentation. Even though different human skin colour detection solutions have
been successfully applied, they are prone to false skin detection and are not
able to cope with the variety of human skin colours across different ethnic.
Moreover, existing methods require high computational cost. In this paper, we
propose a novel human skin de- tection approach that combines a smoothed 2D
histogram and Gaussian model, for automatic human skin detection in colour
image(s). In our approach an eye detector is used to refine the skin model for
a specific person. The proposed approach reduces computational costs as no
training is required; and it improves the accuracy of skin detection despite
wide variation in ethnicity and illumination. To the best of our knowledge,
this is the first method to employ fusion strategy for this purpose.
Qualitative and quantitative results on three standard public datasets and a
comparison with state-of-the-art methods have shown the effectiveness and
robustness of the proposed approach.
Zero-Shot Object Recognition System based on Topic Model
Authors: Wai Lam Hoo, Chee Seng Chan
Date: 2014-10-14 00:00:00
Tasks: Attribute, General Classification, Object, Object Recognition, Zero-Shot Learning

Object recognition systems usually require fully complete manually labeled
training data to train the classifier. In this paper, we study the problem of
object recognition where the training samples are missing during the classifier
learning stage, a task also known as zero-shot learning. We propose a novel
zero-shot learning strategy that utilizes the topic model and hierarchical
class concept. Our proposed method advanced where cumbersome human annotation
stage (i.e. attribute-based classification) is eliminated. We achieve
comparable performance with state-of-the-art algorithms in four public
datasets: PubFig (67.09%), Cifar-100 (54.85%), Caltech-256 (52.14%), and
Animals with Attributes (49.65%) when unseen classes exist in the
classification task.
Refined Particle Swarm Intelligence Method for Abrupt Motion Tracking
Authors: Mei Kuan Lim, Chee Seng Chan, Dorothy Monekosso, Paolo Remagnino
Date: 2014-10-14 00:00:00

Conventional tracking solutions are not feasible in handling abrupt motion as
they are based on smooth motion assumption or an accurate motion model. Abrupt
motion is not subject to motion continuity and smoothness. To assuage this, we
deem tracking as an optimisation problem and propose a novel abrupt motion
tracker that based on swarm intelligence - the SwaTrack. Unlike existing
swarm-based filtering methods, we first of all introduce an optimised
swarm-based sampling strategy to tradeoff between the exploration and
exploitation of the search space in search for the optimal proposal
distribution. Secondly, we propose Dynamic Acceleration Parameters (DAP) allow
on the fly tuning of the best mean and variance of the distribution for
sampling. Such innovating idea of combining these strategies in an ingenious
way in the PSO framework to handle the abrupt motion, which so far no existing
works are found. Experimental results in both quantitative and qualitative had
shown the effectiveness of the proposed method in tracking abrupt motions.
Scene Image is Non-Mutually Exclusive - A Fuzzy Qualitative Scene Understanding
Authors: Chern Hong Lim, Anhar Risnumawan, Chee Seng Chan
Date: 2014-10-14 00:00:00
Tasks: Binary Classification, Decision Making, Scene Understanding

Ambiguity or uncertainty is a pervasive element of many real world decision
making processes. Variation in decisions is a norm in this situation when the
same problem is posed to different subjects. Psychological and metaphysical
research had proven that decision making by human is subjective. It is
influenced by many factors such as experience, age, background, etc. Scene
understanding is one of the computer vision problems that fall into this
category. Conventional methods relax this problem by assuming scene images are
mutually exclusive; and therefore, focus on developing different approaches to
perform the binary classification tasks. In this paper, we show that scene
images are non-mutually exclusive, and propose the Fuzzy Qualitative Rank
Classifier (FQRC) to tackle the aforementioned problems. The proposed FQRC
provides a ranking interpretation instead of binary decision. Evaluations in
term of qualitative and quantitative using large numbers and challenging public
scene datasets have shown the effectiveness of our proposed method in modeling
the non-mutually exclusive scene images.
A graph Laplacian regularization for hyperspectral data unmixing
Authors: Rita Ammanouil, André Ferrari, Cédric Richard
Date: 2014-10-14 00:00:00
Tasks: Hyperspectral Unmixing

This paper introduces a graph Laplacian regularization in the hyperspectral
unmixing formulation. The proposed regularization relies upon the construction
of a graph representation of the hyperspectral image. Each node in the graph
represents a pixel's spectrum, and edges connect spectrally and spatially
similar pixels. The proposed graph framework promotes smoothness in the
estimated abundance maps and collaborative estimation between homogeneous areas
of the image. The resulting convex optimization problem is solved using the
Alternating Direction Method of Multipliers (ADMM). A special attention is
given to the computational complexity of the algorithm, and Graph-cut methods
are proposed in order to reduce the computational burden. Finally, simulations
conducted on synthetic data illustrate the effectiveness of the graph Laplacian
regularization with respect to other classical regularizations for
hyperspectral unmixing.
Sparsity Based Poisson Denoising with Dictionary Learning
Authors: Raja Giryes, Michael Elad
Date: 2013-09-17 00:00:00
Tasks: Denoising, Dictionary Learning

The problem of Poisson denoising appears in various imaging applications,
such as low-light photography, medical imaging and microscopy. In cases of high
SNR, several transformations exist so as to convert the Poisson noise into an
additive i.i.d. Gaussian noise, for which many effective algorithms are
available. However, in a low SNR regime, these transformations are
significantly less accurate, and a strategy that relies directly on the true
noise statistics is required. A recent work by Salmon et al. took this route,
proposing a patch-based exponential image representation model based on GMM
(Gaussian mixture model), leading to state-of-the-art results. In this paper,
we propose to harness sparse-representation modeling to the image patches,
adopting the same exponential idea. Our scheme uses a greedy pursuit with
boot-strapping based stopping condition and dictionary learning within the
denoising process. The reconstruction performance of the proposed scheme is
competitive with leading methods in high SNR, and achieving state-of-the-art
results in cases of low SNR.
A stochastic behavior analysis of stochastic restricted-gradient descent algorithm in reproducing kernel Hilbert spaces
Authors: Masa-aki Takizawa, Masahiro Yukawa, Cedric Richard
Date: 2014-10-14 00:00:00

This paper presents a stochastic behavior analysis of a kernel-based
stochastic restricted-gradient descent method. The restricted gradient gives a
steepest ascent direction within the so-called dictionary subspace. The
analysis provides the transient and steady state performance in the mean
squared error criterion. It also includes stability conditions in the mean and
mean-square sense. The present study is based on the analysis of the kernel
normalized least mean square (KNLMS) algorithm initially proposed by Chen et
al. Simulation results validate the analysis.
Computational Understanding and Manipulation of Symmetries
Authors: Attila Egri-Nagy, Chrystopher L. Nehaniv
Date: 2009-08-21 00:00:00

For natural and artificial systems with some symmetry structure,
computational understanding and manipulation can be achieved without learning
by exploiting the algebraic structure. Here we describe this algebraic
coordinatization method and apply it to permutation puzzles. Coordinatization
yields a structural understanding, not just solutions for the puzzles.
Direct Processing of Document Images in Compressed Domain
Authors: Mohammed Javed, P. Nagabhushan, B. B. Chaudhuri
Date: 2014-10-11 00:00:00
Tasks: Segmentation

With the rapid increase in the volume of Big data of this digital era, fax
documents, invoices, receipts, etc are traditionally subjected to compression
for the efficiency of data storage and transfer. However, in order to process
these documents, they need to undergo the stage of decompression which indents
additional computing resources. This limitation induces the motivation to
research on the possibility of directly processing of compressed images. In
this research paper, we summarize the research work carried out to perform
different operations straight from run-length compressed documents without
going through the stage of decompression. The different operations demonstrated
are feature extraction; text-line, word and character segmentation; document
block segmentation; and font size detection, all carried out in the compressed
version of the document. Feature extraction methods demonstrate how to extract
the conventionally defined features such as projection profile, run-histogram
and entropy, directly from the compressed document data. Document segmentation
involves the extraction of compressed segments of text-lines, words and
characters using the vertical and horizontal projection profile features.
Further an attempt is made to segment randomly a block of interest from the
compressed document and subsequently facilitate absolute and relative
characterization of the segmented block which finds real time applications in
automatic processing of Bank Cheques, Challans, etc, in compressed domain.
Finally an application to detect font size at text line level is also
investigated. All the proposed algorithms are validated experimentally with
sufficient data set of compressed documents.
Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
Authors: Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, Robert E. Schapire
Date: 2014-02-04 00:00:00
Tasks: General Classification, Multi-Armed Bandits

We present a new algorithm for the contextual bandit learning problem, where
the learner repeatedly takes one of $K$ actions in response to the observed
context, and observes the reward only for that chosen action. Our method
assumes access to an oracle for solving fully supervised cost-sensitive
classification problems and achieves the statistically optimal regret guarantee
with only $\tilde{O}(\sqrt{KT/\log N})$ oracle calls across all $T$ rounds,
where $N$ is the number of policies in the policy class we compete against. By
doing so, we obtain the most practical contextual bandit learning algorithm
amongst approaches that work for general policy classes. We further conduct a
proof-of-concept experiment which demonstrates the excellent computational and
prediction performance of (an online variant of) our algorithm relative to
several baselines.