pwc-archive/papers-with-abstracts huggingface dataset:
Efficient Classification for Metric Data
Authors: Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer
Date: 2013-06-11 00:00:00
Tasks: Classification, Computational Efficiency, General Classification

Recent advances in large-margin classification of data residing in general
metric spaces (rather than Hilbert spaces) enable classification under various
natural metrics, such as string edit and earthmover distance. A general
framework developed for this purpose by von Luxburg and Bousquet [JMLR, 2004]
left open the questions of computational efficiency and of providing direct
bounds on generalization error.
  We design a new algorithm for classification in general metric spaces, whose
runtime and accuracy depend on the doubling dimension of the data points, and
can thus achieve superior classification performance in many common scenarios.
The algorithmic core of our approach is an approximate (rather than exact)
solution to the classical problems of Lipschitz extension and of Nearest
Neighbor Search. The algorithm's generalization performance is guaranteed via
the fat-shattering dimension of Lipschitz classifiers, and we present
experimental evidence of its superiority to some common kernel methods. As a
by-product, we offer a new perspective on the nearest neighbor classifier,
which yields significantly sharper risk asymptotics than the classic analysis
of Cover and Hart [IEEE Trans. Info. Theory, 1967].
Real-Time Impulse Noise Suppression from Images Using an Efficient Weighted-Average Filtering
Authors: Hossein Hosseini, Farzad Hessar, Farokh Marvasti
Date: 2014-07-10 00:00:00

In this paper, we propose a method for real-time high density impulse noise
suppression from images. In our method, we first apply an impulse detector to
identify the corrupted pixels and then employ an innovative weighted-average
filter to restore them. The filter takes the nearest neighboring interpolated
image as the initial image and computes the weights according to the relative
positions of the corrupted and uncorrupted pixels. Experimental results show
that the proposed method outperforms the best existing methods in both PSNR
measure and visual quality and is quite suitable for real-time applications.
On the Convergence of the Mean Shift Algorithm in the One-Dimensional Space
Authors: Youness Aliyari Ghassabeh
Date: 2014-07-10 00:00:00

The mean shift algorithm is a non-parametric and iterative technique that has
been used for finding modes of an estimated probability density function. It
has been successfully employed in many applications in specific areas of
machine vision, pattern recognition, and image processing. Although the mean
shift algorithm has been used in many applications, a rigorous proof of its
convergence is still missing in the literature. In this paper we address the
convergence of the mean shift algorithm in the one-dimensional space and prove
that the sequence generated by the mean shift algorithm is a monotone and
convergent sequence.
An eigenanalysis of data centering in machine learning
Authors: Paul Honeine
Date: 2014-07-10 00:00:00
Tasks: BIG-bench Machine Learning

Many pattern recognition methods rely on statistical information from
centered data, with the eigenanalysis of an empirical central moment, such as
the covariance matrix in principal component analysis (PCA), as well as partial
least squares regression, canonical-correlation analysis and Fisher
discriminant analysis. Recently, many researchers advocate working on
non-centered data. This is the case for instance with the singular value
decomposition approach, with the (kernel) entropy component analysis, with the
information-theoretic learning framework, and even with nonnegative matrix
factorization. Moreover, one can also consider a non-centered PCA by using the
second-order non-central moment.
  The main purpose of this paper is to bridge the gap between these two
viewpoints in designing machine learning methods. To provide a study at the
cornerstone of kernel-based machines, we conduct an eigenanalysis of the inner
product matrices from centered and non-centered data. We derive several results
connecting their eigenvalues and their eigenvectors. Furthermore, we explore
the outer product matrices, by providing several results connecting the largest
eigenvectors of the covariance matrix and its non-centered counterpart. These
results lay the groundwork to several extensions beyond conventional centering,
with the weighted mean shift, the rank-one update, and the multidimensional
scaling. Experiments conducted on simulated and real data illustrate the
relevance of this work.
A Compilation Target for Probabilistic Programming Languages
Authors: Brooks Paige, Frank Wood
Date: 2014-03-03 00:00:00
Tasks: Probabilistic Programming

Forward inference techniques such as sequential Monte Carlo and particle
Markov chain Monte Carlo for probabilistic programming can be implemented in
any programming language by creative use of standardized operating system
functionality including processes, forking, mutexes, and shared memory.
Exploiting this we have defined, developed, and tested a probabilistic
programming language intermediate representation language we call probabilistic
C, which itself can be compiled to machine code by standard compilers and
linked to operating system libraries yielding an efficient, scalable, portable
probabilistic programming compilation target. This opens up a new hardware and
systems research path for optimizing probabilistic programming systems.
Possibilities of technologization of philosophical knowledge
Authors: Sergey Kulikov
Date: 2014-07-10 00:00:00
Tasks: Philosophy

Article purpose is the analysis of a question of possibility of
technologization of philosophical knowledge. We understand the organization of
cognitive activity which is guided by the set of methods guaranteed bringing to
successful (i.e. to precisely corresponding set parameters) to applied results
as technologization. Transformation of sense of philosophy allows revealing
possibilities of its technologization. The leading role in this process is
played by philosophy of science which creates conditions for such
transformation. At the same time there is justified an appeal to branch
combination theory of the directions of scientific knowledge and partial
refusal of understanding of philosophy as synthetic knowledge in which the main
task is permission, instead of generation of paradoxes.
Asynchronous Anytime Sequential Monte Carlo
Authors: Brooks Paige, Frank Wood, Arnaud Doucet, Yee Whye Teh
Date: 2014-07-10 00:00:00
Proceeding: NeurIPS 2014 12

We introduce a new sequential Monte Carlo algorithm we call the particle
cascade. The particle cascade is an asynchronous, anytime alternative to
traditional particle filtering algorithms. It uses no barrier synchronizations
which leads to improved particle throughput and memory efficiency. It is an
anytime algorithm in the sense that it can be run forever to emit an unbounded
number of particles while keeping within a fixed memory budget. We prove that
the particle cascade is an unbiased marginal likelihood estimator which means
that it can be straightforwardly plugged into existing pseudomarginal methods.
XML Matchers: approaches and challenges
Authors: Santa Agreste, Pasquale De Meo, Emilio Ferrara, Domenico Ursino
Date: 2014-07-10 00:00:00
Tasks: Clustering, Management

Schema Matching, i.e. the process of discovering semantic correspondences
between concepts adopted in different data source schemas, has been a key topic
in Database and Artificial Intelligence research areas for many years. In the
past, it was largely investigated especially for classical database models
(e.g., E/R schemas, relational databases, etc.). However, in the latest years,
the widespread adoption of XML in the most disparate application fields pushed
a growing number of researchers to design XML-specific Schema Matching
approaches, called XML Matchers, aiming at finding semantic matchings between
concepts defined in DTDs and XSDs. XML Matchers do not just take well-known
techniques originally designed for other data models and apply them on
DTDs/XSDs, but they exploit specific XML features (e.g., the hierarchical
structure of a DTD/XSD) to improve the performance of the Schema Matching
process. The design of XML Matchers is currently a well-established research
area. The main goal of this paper is to provide a detailed description and
classification of XML Matchers. We first describe to what extent the
specificities of DTDs/XSDs impact on the Schema Matching task. Then we
introduce a template, called XML Matcher Template, that describes the main
components of an XML Matcher, their role and behavior. We illustrate how each
of these components has been implemented in some popular XML Matchers. We
consider our XML Matcher Template as the baseline for objectively comparing
approaches that, at first glance, might appear as unrelated. The introduction
of this template can be useful in the design of future XML Matchers. Finally,
we analyze commercial tools implementing XML Matchers and introduce two
challenging issues strictly related to this topic, namely XML source clustering
and uncertainty management in XML Matchers.
Rate-Optimal Detection of Very Short Signal Segments
Authors: T. Tony Cai, Ming Yuan
Date: 2014-07-10 00:00:00

Motivated by a range of applications in engineering and genomics, we consider
in this paper detection of very short signal segments in three settings:
signals with known shape, arbitrary signals, and smooth signals. Optimal rates
of detection are established for the three cases and rate-optimal detectors are
constructed. The detectors are easily implementable and are based on scanning
with linear and quadratic statistics. Our analysis reveals both similarities
and differences in the strategy and fundamental difficulty of detection among
these three settings.
Bandits Warm-up Cold Recommender Systems
Authors: Jérémie Mary, Romaric Gaudel, Preux Philippe
Date: 2014-07-10 00:00:00
Tasks: Multi-Armed Bandits, Recommendation Systems

We address the cold start problem in recommendation systems assuming no
contextual information is available neither about users, nor items. We consider
the case in which we only have access to a set of ratings of items by users.
Most of the existing works consider a batch setting, and use cross-validation
to tune parameters. The classical method consists in minimizing the root mean
square error over a training subset of the ratings which provides a
factorization of the matrix of ratings, interpreted as a latent representation
of items and users. Our contribution in this paper is 5-fold. First, we
explicit the issues raised by this kind of batch setting for users or items
with very few ratings. Then, we propose an online setting closer to the actual
use of recommender systems; this setting is inspired by the bandit framework.
The proposed methodology can be used to turn any recommender system dataset
(such as Netflix, MovieLens,...) into a sequential dataset. Then, we explicit a
strong and insightful link between contextual bandit algorithms and matrix
factorization; this leads us to a new algorithm that tackles the
exploration/exploitation dilemma associated to the cold start problem in a
strikingly new perspective. Finally, experimental evidence confirm that our
algorithm is effective in dealing with the cold start problem on publicly
available datasets. Overall, the goal of this paper is to bridge the gap
between recommender systems based on matrix factorizations and those based on
contextual bandits.
What you need to know about the state-of-the-art computational models of object-vision: A tour through the models
Authors: Seyed-Mahdi Khaligh-Razavi
Date: 2014-07-10 00:00:00
Tasks: Object Recognition

Models of object vision have been of great interest in computer vision and
visual neuroscience. During the last decades, several models have been
developed to extract visual features from images for object recognition tasks.
Some of these were inspired by the hierarchical structure of primate visual
system, and some others were engineered models. The models are varied in
several aspects: models that are trained by supervision, models trained without
supervision, and models (e.g. feature extractors) that are fully hard-wired and
do not need training. Some of the models come with a deep hierarchical
structure consisting of several layers, and some others are shallow and come
with only one or two layers of processing. More recently, new models have been
developed that are not hand-tuned but trained using millions of images, through
which they learn how to extract informative task-related features. Here I will
survey all these different models and provide the reader with an intuitive, as
well as a more detailed, understanding of the underlying computations in each
of the models.
A multi-instance learning algorithm based on a stacked ensemble of lazy learners
Authors: Ramasubramanian Sundararajan, Hima Patel, Manisha Srivastava
Date: 2014-07-10 00:00:00
Tasks: Diversity

This document describes a novel learning algorithm that classifies "bags" of
instances rather than individual instances. A bag is labeled positive if it
contains at least one positive instance (which may or may not be specifically
identified), and negative otherwise. This class of problems is known as
multi-instance learning problems, and is useful in situations where the class
label at an instance level may be unavailable or imprecise or difficult to
obtain, or in situations where the problem is naturally posed as one of
classifying instance groups. The algorithm described here is an ensemble-based
method, wherein the members of the ensemble are lazy learning classifiers
learnt using the Citation Nearest Neighbour method. Diversity among the
ensemble members is achieved by optimizing their parameters using a
multi-objective optimization method, with the objectives being to maximize
Class 1 accuracy and minimize false positive rate. The method has been found to
be effective on the Musk1 benchmark dataset.
Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
Authors: Aaron J. Defazio, Tibério S. Caetano, Justin Domke
Date: 2014-07-10 00:00:00

Recent advances in optimization theory have shown that smooth strongly convex
finite sums can be minimized faster than by treating them as a black box
"batch" problem. In this work we introduce a new method in this class with a
theoretical convergence rate four times faster than existing methods, for sums
with sufficiently many terms. This method is also amendable to a sampling
without replacement scheme that in practice gives further speed-ups. We give
empirical results showing state of the art performance.
Offline handwritten signature identification using adaptive window positioning techniques
Authors: Ghazali Sulong, Anwar Yahy Ebrahim, Muhammad Jehanzeb
Date: 2014-07-10 00:00:00

The paper presents to address this challenge, we have proposed the use of
Adaptive Window Positioning technique which focuses on not just the meaning of
the handwritten signature but also on the individuality of the writer. This
innovative technique divides the handwritten signature into 13 small windows of
size nxn(13x13).This size should be large enough to contain ample information
about the style of the author and small enough to ensure a good identification
performance.The process was tested with a GPDS data set containing 4870
signature samples from 90 different writers by comparing the robust features of
the test signature with that of the user signature using an appropriate
classifier. Experimental results reveal that adaptive window positioning
technique proved to be the efficient and reliable method for accurate signature
feature extraction for the identification of offline handwritten signatures.The
contribution of this technique can be used to detect signatures signed under
emotional duress.
A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation
Authors: Aaron J. Defazio, Tiberio S. Caetano
Date: 2014-07-10 00:00:00
Proceeding: NeurIPS 2012

A key problem in statistics and machine learning is the determination of
network structure from data. We consider the case where the structure of the
graph to be reconstructed is known to be scale-free. We show that in such cases
it is natural to formulate structured sparsity inducing priors using submodular
functions, and we use their Lov\'asz extension to obtain a convex relaxation.
For tractable classes such as Gaussian graphical models, this leads to a convex
optimization problem that can be efficiently solved. We show that our method
results in an improvement in the accuracy of reconstructed networks for
synthetic data. We also show how our prior encourages scale-free
reconstructions on a bioinfomatics dataset.
Quality Estimation Of Machine Translation Outputs Through Stemming
Authors: Pooja Gupta, Nisheeth Joshi, Iti Mathur
Date: 2014-07-10 00:00:00
Tasks: BIG-bench Machine Learning, Machine Translation, Sentence, Translation

Machine Translation is the challenging problem for Indian languages. Every
day we can see some machine translators being developed, but getting a high
quality automatic translation is still a very distant dream . The correct
translated sentence for Hindi language is rarely found. In this paper, we are
emphasizing on English-Hindi language pair, so in order to preserve the correct
MT output we present a ranking system, which employs some machine learning
techniques and morphological features. In ranking no human intervention is
required. We have also validated our results by comparing it with human
ranking.
Quantum support vector machine for big data classification
Authors: Patrick Rebentrost, Masoud Mohseni, Seth Lloyd
Date: 2013-07-01 00:00:00
Tasks: BIG-bench Machine Learning, Classification, General Classification

Supervised machine learning is the classification of new data based on
already classified training examples. In this work, we show that the support
vector machine, an optimized binary classifier, can be implemented on a quantum
computer, with complexity logarithmic in the size of the vectors and the number
of training examples. In cases when classical sampling algorithms require
polynomial time, an exponential speed-up is obtained. At the core of this
quantum big data algorithm is a non-sparse matrix exponentiation technique for
efficiently performing a matrix inversion of the training data inner-product
(kernel) matrix.
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
Authors: Amos Beimel, Kobbi Nissim, Uri Stemmer
Date: 2014-07-10 00:00:00

We compare the sample complexity of private learning [Kasiviswanathan et al.
2008] and sanitization~[Blum et al. 2008] under pure $\epsilon$-differential
privacy [Dwork et al. TCC 2006] and approximate
$(\epsilon,\delta)$-differential privacy [Dwork et al. Eurocrypt 2006]. We show
that the sample complexity of these tasks under approximate differential
privacy can be significantly lower than that under pure differential privacy.
  We define a family of optimization problems, which we call Quasi-Concave
Promise Problems, that generalizes some of our considered tasks. We observe
that a quasi-concave promise problem can be privately approximated using a
solution to a smaller instance of a quasi-concave promise problem. This allows
us to construct an efficient recursive algorithm solving such problems
privately. Specifically, we construct private learners for point functions,
threshold functions, and axis-aligned rectangles in high dimension. Similarly,
we construct sanitizers for point functions and threshold functions.
  We also examine the sample complexity of label-private learners, a relaxation
of private learning where the learner is required to only protect the privacy
of the labels in the sample. We show that the VC dimension completely
characterizes the sample complexity of such learners, that is, the sample
complexity of learning with label privacy is equal (up to constants) to
learning without privacy.
Possibility neutrosophic soft sets with applications in decision making and similarity measure
Authors: Faruk Karaaslan
Date: 2014-07-09 00:00:00
Tasks: Decision Making, Position

In this paper, concept of possibility neutrosophic soft set and its
operations are defined, and their properties are studied. An application of
this theory in decision making is investigated. Also a similarity measure of
two possibility neutrosophic soft sets is introduced and discussed. Finally an
application of this similarity measure is given to select suitable person for
position in a firm.
Classifying Fonts and Calligraphy Styles Using Complex Wavelet Transform
Authors: Alican Bozkurt, Pinar Duygulu, A. Enis Cetin
Date: 2014-07-09 00:00:00
Tasks: Font Recognition

Recognizing fonts has become an important task in document analysis, due to
the increasing number of available digital documents in different fonts and
emphases. A generic font-recognition system independent of language, script and
content is desirable for processing various types of documents. At the same
time, categorizing calligraphy styles in handwritten manuscripts is important
for palaeographic analysis, but has not been studied sufficiently in the
literature. We address the font-recognition problem as analysis and
categorization of textures. We extract features using complex wavelet transform
and use support vector machines for classification. Extensive experimental
evaluations on different datasets in four languages and comparisons with
state-of-the-art studies show that our proposed method achieves higher
recognition accuracy while being computationally simpler. Furthermore, on a new
dataset generated from Ottoman manuscripts, we show that the proposed method
can also be used for categorizing Ottoman calligraphy with high accuracy.
Learning Probabilistic Programs
Authors: Yura N. Perov, Frank D. Wood
Date: 2014-07-09 00:00:00
Tasks: Probabilistic Programming

We develop a technique for generalising from data in which models are
samplers represented as program text. We establish encouraging empirical
results that suggest that Markov chain Monte Carlo probabilistic programming
inference techniques coupled with higher-order probabilistic programming
languages are now sufficiently powerful to enable successful inference of this
kind in nontrivial domains. We also introduce a new notion of probabilistic
program compilation and show how the same machinery might be used in the future
to compile probabilistic programs for efficient reusable predictive inference.