pwc-archive/papers-with-abstracts huggingface dataset:
New similarity index based on entropy and group theory
Authors: Yasel Garcés, Esley Torres, Osvaldo Pereira, Roberto Rodríguez
Date: 2014-10-28 00:00:00

In this work, we propose a new similarity index for images considering the
entropy function and group theory. This index considers an algebraic group of
images, it is defined by an inner law that provides a novel approach for the
subtraction of images. Through an equivalence relationship in the field of
images, we prove the existence of the quotient group, on which the new
similarity index is defined. We also present the main properties of the new
index, and the immediate application thereof as a stopping criterion of the
"Mean Shift Iterative Algorithm".
Finite Element Based Tracking of Deforming Surfaces
Authors: Stefanie Wuhrer, Jochen Lang, Motahareh Tekieh, Chang Shu
Date: 2013-06-19 00:00:00
Tasks: Object

We present an approach to robustly track the geometry of an object that
deforms over time from a set of input point clouds captured from a single
viewpoint. The deformations we consider are caused by applying forces to known
locations on the object's surface. Our method combines the use of prior
information on the geometry of the object modeled by a smooth template and the
use of a linear finite element method to predict the deformation. This allows
the accurate reconstruction of both the observed and the unobserved sides of
the object. We present tracking results for noisy low-quality point clouds
acquired by either a stereo camera or a depth camera, and simulations with
point clouds corrupted by different error terms. We show that our method is
also applicable to large non-linear deformations.
Anomaly Detection Framework Using Rule Extraction for Efficient Intrusion Detection
Authors: Antti Juvonen, Tuomo Sipola
Date: 2014-10-28 00:00:00
Tasks: Anomaly Detection, BIG-bench Machine Learning, Dimensionality Reduction, Intrusion Detection, Traffic Classification, Unsupervised Anomaly Detection

Huge datasets in cyber security, such as network traffic logs, can be
analyzed using machine learning and data mining methods. However, the amount of
collected data is increasing, which makes analysis more difficult. Many machine
learning methods have not been designed for big datasets, and consequently are
slow and difficult to understand. We address the issue of efficient network
traffic classification by creating an intrusion detection framework that
applies dimensionality reduction and conjunctive rule extraction. The system
can perform unsupervised anomaly detection and use this information to create
conjunctive rules that classify huge amounts of traffic in real time. We test
the implemented system with the widely used KDD Cup 99 dataset and real-world
network logs to confirm that the performance is satisfactory. This system is
transparent and does not work like a black box, making it intuitive for domain
experts, such as network administrators.
Non-convex Robust PCA
Authors: Praneeth Netrapalli, U. N. Niranjan, Sujay Sanghavi, Animashree Anandkumar, Prateek Jain
Date: 2014-10-28 00:00:00
Proceeding: NeurIPS 2014 12

We propose a new method for robust PCA -- the task of recovering a low-rank
matrix from sparse corruptions that are of unknown value and support. Our
method involves alternating between projecting appropriate residuals onto the
set of low-rank matrices, and the set of sparse matrices; each projection is
{\em non-convex} but easy to compute. In spite of this non-convexity, we
establish exact recovery of the low-rank matrix, under the same conditions that
are required by existing methods (which are based on convex optimization). For
an $m \times n$ input matrix ($m \leq n)$, our method has a running time of
$O(r^2mn)$ per iteration, and needs $O(\log(1/\epsilon))$ iterations to reach
an accuracy of $\epsilon$. This is close to the running time of simple PCA via
the power method, which requires $O(rmn)$ per iteration, and
$O(\log(1/\epsilon))$ iterations. In contrast, existing methods for robust PCA,
which are based on convex optimization, have $O(m^2n)$ complexity per
iteration, and take $O(1/\epsilon)$ iterations, i.e., exponentially more
iterations for the same accuracy.
  Experiments on both synthetic and real data establishes the improved speed
and accuracy of our method over existing convex implementations.
A Short Image Series Based Scheme for Time Series Digital Image Correlation
Authors: Xian Wang, Shaopeng Ma
Date: 2014-10-28 00:00:00
Tasks: STS, Time Series, Time Series Analysis

A new scheme for digital image correlation, i.e., short time series DIC
(STS-DIC) is proposed. Instead of processing the original deformed speckle
images individually, STS-DIC combines several adjacent deformed speckle images
from a short time series and then processes the averaged image, for which
deformation continuity over time is introduced. The deformation of several
adjacent images is assumed to be linear in time and a new spatial-temporal
displacement representation method with eight unknowns is presented based on
the subset-based representation method. Then, the model of STS-DIC is created
and a solving scheme is developed based on the Newton-Raphson iteration. The
proposed method is verified for numerical and experimental cases. The results
show that the proposed STS-DIC greatly improves the accuracy of traditional
DIC, both under simple and complicated deformation conditions, while retaining
acceptable actual computational cost.
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
Authors: Ohad Shamir
Date: 2013-11-14 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Multi-Armed Bandits, Stochastic Optimization

Many machine learning approaches are characterized by information constraints
on how they interact with the training data. These include memory and
sequential access constraints (e.g. fast first-order methods to solve
stochastic optimization problems); communication constraints (e.g. distributed
learning); partial access to the underlying data (e.g. missing features and
multi-armed bandits) and more. However, currently we have little understanding
how such information constraints fundamentally affect our performance,
independent of the learning problem semantics. For example, are there learning
problems where any algorithm which has small memory footprint (or can use any
bounded number of bits from each example, or has certain communication
constraints) will perform worse than what is possible without such constraints?
In this paper, we describe how a single set of results implies positive answers
to the above, for several different settings.
Interactive Debugging of ASP Programs
Authors: Kostyantyn Shchekotykhin
Date: 2014-03-20 00:00:00

Broad application of answer set programming (ASP) for declarative problem
solving requires the development of tools supporting the coding process.
Program debugging is one of the crucial activities within this process.
Recently suggested ASP debugging approaches allow efficient computation of
possible explanations of a fault. However, even for a small program a debugger
might return a large number of possible explanations and selection of the
correct one must be done manually. In this paper we present an interactive
query-based ASP debugging method which extends previous approaches and finds a
preferred explanation by means of observations. The system queries a programmer
whether a set of ground atoms must be true in all (cautiously) or some
(bravely) answer sets of the program. Since some queries can be more
informative than the others, we discuss query selection strategies which, given
user's preferences for an explanation, can find the best query. That is, the
query an answer of which reduces the overall number of queries required for the
identification of a preferred explanation.
Fast Algorithms for Online Stochastic Convex Programming
Authors: Shipra Agrawal, Nikhil R. Devanur
Date: 2014-10-28 00:00:00

We introduce the online stochastic Convex Programming (CP) problem, a very
general version of stochastic online problems which allows arbitrary concave
objectives and convex feasibility constraints. Many well-studied problems like
online stochastic packing and covering, online stochastic matching with concave
returns, etc. form a special case of online stochastic CP. We present fast
algorithms for these problems, which achieve near-optimal regret guarantees for
both the i.i.d. and the random permutation models of stochastic inputs. When
applied to the special case online packing, our ideas yield a simpler and
faster primal-dual algorithm for this well studied problem, which achieves the
optimal competitive ratio. Our techniques make explicit the connection of
primal-dual paradigm and online learning to online stochastic CP.
Learning deep dynamical models from image pixels
Authors: Niklas Wahlström, Thomas B. Schön, Marc Peter Deisenroth
Date: 2014-10-28 00:00:00

Modeling dynamical systems is important in many disciplines, e.g., control,
robotics, or neurotechnology. Commonly the state of these systems is not
directly observed, but only available through noisy and potentially
high-dimensional observations. In these cases, system identification, i.e.,
finding the measurement mapping and the transition mapping (system dynamics) in
latent space can be challenging. For linear system dynamics and measurement
mappings efficient solutions for system identification are available. However,
in practical applications, the linearity assumptions does not hold, requiring
non-linear system identification techniques. If additionally the observations
are high-dimensional (e.g., images), non-linear system identification is
inherently hard. To address the problem of non-linear system identification
from high-dimensional observations, we combine recent advances in deep learning
and system identification. In particular, we jointly learn a low-dimensional
embedding of the observation by means of deep auto-encoders and a predictive
transition model in this low-dimensional space. We demonstrate that our model
enables learning good predictive models of dynamical systems from pixel
information only.
Practical Matrix Completion and Corruption Recovery using Proximal Alternating Robust Subspace Minimization
Authors: Yu-Xiang Wang, Choon Meng Lee, Loong-Fah Cheong, Kim-Chuan Toh
Date: 2013-09-06 00:00:00
Tasks: Low-Rank Matrix Completion, Matrix Completion

Low-rank matrix completion is a problem of immense practical importance.
Recent works on the subject often use nuclear norm as a convex surrogate of the
rank function. Despite its solid theoretical foundation, the convex version of
the problem often fails to work satisfactorily in real-life applications. Real
data often suffer from very few observations, with support not meeting the
random requirements, ubiquitous presence of noise and potentially gross
corruptions, sometimes with these simultaneously occurring.
  This paper proposes a Proximal Alternating Robust Subspace Minimization
(PARSuMi) method to tackle the three problems. The proximal alternating scheme
explicitly exploits the rank constraint on the completed matrix and uses the
$\ell_0$ pseudo-norm directly in the corruption recovery step. We show that the
proposed method for the non-convex and non-smooth model converges to a
stationary point. Although it is not guaranteed to find the global optimal
solution, in practice we find that our algorithm can typically arrive at a good
local minimizer when it is supplied with a reasonably good starting point based
on convex optimization. Extensive experiments with challenging synthetic and
real data demonstrate that our algorithm succeeds in a much larger range of
practical problems where convex optimization fails, and it also outperforms
various state-of-the-art algorithms.
The Price of Privacy in Untrusted Recommendation Engines
Authors: Siddhartha Banerjee, Nidhi Hegde, Laurent Massoulié
Date: 2012-07-13 00:00:00
Tasks: Clustering, Recommendation Systems

Recent increase in online privacy concerns prompts the following question:
can a recommender system be accurate if users do not entrust it with their
private data? To answer this, we study the problem of learning item-clusters
under local differential privacy, a powerful, formal notion of data privacy. We
develop bounds on the sample-complexity of learning item-clusters from
privatized user inputs. Significantly, our results identify a sample-complexity
separation between learning in an information-rich and an information-scarce
regime, thereby highlighting the interaction between privacy and the amount of
information (ratings) available to each user.
  In the information-rich regime, where each user rates at least a constant
fraction of items, a spectral clustering approach is shown to achieve a
sample-complexity lower bound derived from a simple information-theoretic
argument based on Fano's inequality. However, the information-scarce regime,
where each user rates only a vanishing fraction of items, is found to require a
fundamentally different approach both for lower bounds and algorithms. To this
end, we develop new techniques for bounding mutual information under a notion
of channel-mismatch, and also propose a new algorithm, MaxSense, and show that
it achieves optimal sample-complexity in this setting.
  The techniques we develop for bounding mutual information may be of broader
interest. To illustrate this, we show their applicability to $(i)$ learning
based on 1-bit sketches, and $(ii)$ adaptive learning, where queries can be
adapted based on answers to past queries.
The Falling Factorial Basis and Its Statistical Applications
Authors: Yu-Xiang Wang, Alex Smola, Ryan J. Tibshirani
Date: 2014-05-03 00:00:00

We study a novel spline-like basis, which we name the "falling factorial
basis", bearing many similarities to the classic truncated power basis. The
advantage of the falling factorial basis is that it enables rapid, linear-time
computations in basis matrix multiplication and basis matrix inversion. The
falling factorial functions are not actually splines, but are close enough to
splines that they provably retain some of the favorable properties of the
latter functions. We examine their application in two problems: trend filtering
over arbitrary input points, and a higher-order variant of the two-sample
Kolmogorov-Smirnov test.
Fast Function to Function Regression
Authors: Junier Oliva, Willie Neiswanger, Barnabas Poczos, Eric Xing, Jeff Schneider
Date: 2014-10-27 00:00:00
Tasks: regression, Time Series, Time Series Analysis, Time Series Prediction

We analyze the problem of regression when both input covariates and output
responses are functions from a nonparametric function class. Function to
function regression (FFR) covers a large range of interesting applications
including time-series prediction problems, and also more general tasks like
studying a mapping between two separate types of distributions. However,
previous nonparametric estimators for FFR type problems scale badly
computationally with the number of input/output pairs in a data-set. Given the
complexity of a mapping between general functions it may be necessary to
consider large data-sets in order to achieve a low estimation risk. To address
this issue, we develop a novel scalable nonparametric estimator, the
Triple-Basis Estimator (3BE), which is capable of operating over datasets with
many instances. To the best of our knowledge, the 3BE is the first
nonparametric FFR estimator that can scale to massive datasets. We analyze the
3BE's risk and derive an upperbound rate. Furthermore, we show an improvement
of several orders of magnitude in terms of prediction speed and a reduction in
error over previous estimators in various real-world data-sets.
Feature Selection through Minimization of the VC dimension
Authors: Jayadeva, Sanjit S. Batra, Siddharth Sabharwal
Date: 2014-10-27 00:00:00
Tasks: Drug Discovery, feature selection, Variable Selection

Feature selection involes identifying the most relevant subset of input
features, with a view to improving generalization of predictive models by
reducing overfitting. Directly searching for the most relevant combination of
attributes is NP-hard. Variable selection is of critical importance in many
applications, such as micro-array data analysis, where selecting a small number
of discriminative features is crucial to developing useful models of disease
mechanisms, as well as for prioritizing targets for drug discovery. The
recently proposed Minimal Complexity Machine (MCM) provides a way to learn a
hyperplane classifier by minimizing an exact (\boldmath{$\Theta$}) bound on its
VC dimension. It is well known that a lower VC dimension contributes to good
generalization. For a linear hyperplane classifier in the input space, the VC
dimension is upper bounded by the number of features; hence, a linear
classifier with a small VC dimension is parsimonious in the set of features it
employs. In this paper, we use the linear MCM to learn a classifier in which a
large number of weights are zero; features with non-zero weights are the ones
that are chosen. Selected features are used to learn a kernel SVM classifier.
On a number of benchmark datasets, the features chosen by the linear MCM yield
comparable or better test set accuracy than when methods such as ReliefF and
FCBF are used for the task. The linear MCM typically chooses one-tenth the
number of attributes chosen by the other methods; on some very high dimensional
datasets, the MCM chooses about $0.6\%$ of the features; in comparison, ReliefF
and FCBF choose 70 to 140 times more features, thus demonstrating that
minimizing the VC dimension may provide a new, and very effective route for
feature selection and for learning sparse representations.
A General Statistic Framework for Genome-based Disease Risk Prediction
Authors: L. Ma, N. Lin, C. I. Amos, M. M. Xiong
Date: 2014-10-27 00:00:00

Advances of modern sensing and sequencing technologies generate a deluge of
high dimensional space-temporal physiological and next-generation sequencing
(NGS) data. Physiological traits are observed either as continuous random
functions, or on a dense grid and referred to as function-valued traits. Both
physiological and NGS data are highly correlated data with their inherent
order, spacing, and functional nature which are ignored by traditional
summary-based univariate and multivariate regression methods designed for
quantitative genetic analysis of scalar trait and common variants. To capture
morphological and dynamic features of the data and utilize their dependent
structure, we propose a functional linear model (FLM) in which a trait curve is
modeled as a response function, the genetic variation in a genomic region or
gene is modeled as a functional predictor, and the genetic effects are modeled
as a function of both time and genomic position (FLMF) for genetic analysis of
function-valued trait with both GWAS and NGS data. By extensive simulations, we
demonstrate that the FLMF has the correct type 1 error rates and much higher
power to detect association than the existing methods. The FLMF is applied to
sleep data from Starr County health studies where oxygen saturation were
measured in 22,670 seconds on average for 833 individuals. We found 65 genes
that were significantly associated with oxygen saturation functional trait with
P-values ranging from 2.40E-06 to 2.53E-21. The results clearly demonstrate
that the FLMF substantially outperforms the traditional genetic models with
scalar trait.
Topology Adaptive Graph Estimation in High Dimensions
Authors: Johannes Lederer, Christian Müller
Date: 2014-10-27 00:00:00
Tasks: Vocal Bursts Intensity Prediction

We introduce Graphical TREX (GTREX), a novel method for graph estimation in
high-dimensional Gaussian graphical models. By conducting neighborhood
selection with TREX, GTREX avoids tuning parameters and is adaptive to the
graph topology. We compare GTREX with standard methods on a new simulation
set-up that is designed to assess accurately the strengths and shortcomings of
different methods. These simulations show that a neighborhood selection scheme
based on Lasso and an optimal (in practice unknown) tuning parameter
outperforms other standard methods over a large spectrum of scenarios.
Moreover, we show that GTREX can rival this scheme and, therefore, can provide
competitive graph estimation without the need for tuning parameter calibration.
An Unsupervised Ensemble-based Markov Random Field Approach to Microscope Cell Image Segmentation
Authors: Balint Antal, Bence Remenyik, Andras Hajdu
Date: 2014-10-27 00:00:00
Tasks: Image Segmentation, Segmentation, Semantic Segmentation

In this paper, we propose an approach to the unsupervised segmentation of
images using Markov Random Field. The proposed approach is based on the idea of
Bit Plane Slicing. We use the planes as initial labellings for an ensemble of
segmentations. With pixelwise voting, a robust segmentation approach can be
achieved, which we demonstrate on microscope cell images. We tested our
approach on a publicly available database, where it proven to be competitive
with other methods and manual segmentation.
Iris Biometric System using a hybrid approach
Authors: Abhimanyu Sarin, Dr. Jagadish Nayak
Date: 2014-10-27 00:00:00
Tasks: Image Enhancement, Iris Recognition

Iris Recognition Systems are ocular- based biometric devices used primarily
for security reasons. The complexity and the randomness of the Iris, amongst
various other factors, ensure that this biometric system is inarguably an exact
and reliable method of identification. The algorithm is responsible for
automatic localization and segmentation of boundaries using circular Hough
Transform, noise reductions, image enhancement and feature extraction across
numerous distinct images present in the database. This paper delves into the
various kinds of techniques required to approximate the pupillary and limbic
boundaries of the enrolled iris image, captured using a suitable image
acquisition device and perform feature extraction on the normalized iris image
with the help of Haar Wavelets to encode the input data into a binary string
format. These techniques were validated using images from the CASIA database,
and various other procedures were also tried and tested.
A Greedy Homotopy Method for Regression with Nonconvex Constraints
Authors: Fabian L. Wauthier, Peter Donnelly
Date: 2014-10-27 00:00:00
Tasks: regression

Constrained least squares regression is an essential tool for
high-dimensional data analysis. Given a partition $\mathcal{G}$ of input
variables, this paper considers a particular class of nonconvex constraint
functions that encourage the linear model to select a small number of variables
from a small number of groups in $\mathcal{G}$. Such constraints are relevant
in many practical applications, such as Genome-Wide Association Studies (GWAS).
Motivated by the efficiency of the Lasso homotopy method, we present RepLasso,
a greedy homotopy algorithm that tries to solve the induced sequence of
nonconvex problems by solving a sequence of suitably adapted convex surrogate
problems. We prove that in some situations RepLasso recovers the global minima
of the nonconvex problem. Moreover, even if it does not recover global minima,
we prove that in relevant cases it will still do no worse than the Lasso in
terms of support and signed support recovery, while in practice outperforming
it. We show empirically that the strategy can also be used to improve over
other Lasso-style algorithms. Finally, a GWAS of ankylosing spondylitis
highlights our method's practical utility.