pwc-archive/papers-with-abstracts huggingface dataset:
K-Plane Regression
Authors: Naresh Manwani, P. S. Sastry
Date: 2012-11-07 00:00:00
Tasks: Clustering, regression

In this paper, we present a novel algorithm for piecewise linear regression
which can learn continuous as well as discontinuous piecewise linear functions.
The main idea is to repeatedly partition the data and learn a liner model in in
each partition. While a simple algorithm incorporating this idea does not work
well, an interesting modification results in a good algorithm. The proposed
algorithm is similar in spirit to $k$-means clustering algorithm. We show that
our algorithm can also be viewed as an EM algorithm for maximum likelihood
estimation of parameters under a reasonable probability model. We empirically
demonstrate the effectiveness of our approach by comparing its performance with
the state of art regression learning algorithms on some real world datasets.
Sequential testing over multiple stages and performance analysis of data fusion
Authors: Gaurav Thakur
Date: 2013-03-27 00:00:00

We describe a methodology for modeling the performance of decision-level data
fusion between different sensor configurations, implemented as part of the
JIEDDO Analytic Decision Engine (JADE). We first discuss a Bayesian network
formulation of classical probabilistic data fusion, which allows elementary
fusion structures to be stacked and analyzed efficiently. We then present an
extension of the Wald sequential test for combining the outputs of the Bayesian
network over time. We discuss an algorithm to compute its performance
statistics and illustrate the approach on some examples. This variant of the
sequential test involves multiple, distinct stages, where the evidence
accumulated from each stage is carried over into the next one, and is motivated
by a need to keep certain sensors in the network inactive unless triggered by
other sensors.
An intelligent approach towards automatic shape modeling and object extraction from satellite images using cellular automata based algorithm
Authors: P. V. Arun, S. K. Katiyar
Date: 2013-03-27 00:00:00

Automatic feature extraction domain has witnessed the application of many
intelligent methodologies over past decade; however detection accuracy of these
approaches were limited as object geometry and contextual knowledge were not
given enough consideration. In this paper, we propose a frame work for accurate
detection of features along with automatic interpolation, and interpretation by
modeling feature shape as well as contextual knowledge using advanced
techniques such as SVRF, Cellular Neural Network, Core set, and MACA. Developed
methodology has been compared with contemporary methods using different
statistical measures. Investigations over various satellite images revealed
that considerable success was achieved with the CNN approach. CNN has been
effective in modeling different complex features effectively and complexity of
the approach has been considerably reduced using corset optimization. The
system has dynamically used spectral and spatial information for representing
contextual knowledge using CNN-prolog approach. System has been also proved to
be effective in providing intelligent interpolation and interpretation of
random features.
An N-dimensional approach towards object based classification of remotely sensed imagery
Authors: Arun P. V, S. K. Katiyar
Date: 2013-03-26 00:00:00
Tasks: Classification, General Classification, Land Cover Classification

Remote sensing techniques are widely used for land cover classification and
urban analysis. The availability of high resolution remote sensing imagery
limits the level of classification accuracy attainable from pixel-based
approach. In this paper object-based classification scheme based on a
hierarchical support vector machine is introduced. By combining spatial and
spectral information, the amount of overlap between classes can be decreased;
thereby yielding higher classification accuracy and more accurate land cover
maps. We have adopted certain automatic approaches based on the advanced
techniques as Cellular automata and Genetic Algorithm for kernel and tuning
parameter selection. Performance evaluation of the proposed methodology in
comparison with the existing approaches is performed with reference to the
Bhopal city study area.
Performance Evaluation of Edge-Directed Interpolation Methods for Images
Authors: Shaode Yu, Qingsong Zhu, Shibin Wu, Yaoqin Xie
Date: 2013-03-26 00:00:00

Many interpolation methods have been developed for high visual quality, but
fail for inability to preserve image structures. Edges carry heavy structural
information for detection, determination and classification. Edge-adaptive
interpolation approaches become a center of focus. In this paper, performance
of four edge-directed interpolation methods comparing with two traditional
methods is evaluated on two groups of images. These methods include new
edge-directed interpolation (NEDI), edge-guided image interpolation (EGII),
iterative curvature-based interpolation (ICBI), directional cubic convolution
interpolation (DCCI) and two traditional approaches, bi-linear and bi-cubic.
Meanwhile, no parameters are mentioned to measure edge-preserving ability of
edge-adaptive interpolation approaches and we proposed two. One evaluates
accuracy and the other measures robustness of edge-preservation ability.
Performance evaluation is based on six parameters. Objective assessment and
visual analysis are illustrated and conclusions are drawn from theoretical
backgrounds and practical results.
Analysis Operator Learning and Its Application to Image Reconstruction
Authors: Simon Hawe, Martin Kleinsteuber, Klaus Diepold
Date: 2012-04-24 00:00:00
Tasks: Denoising, Image Denoising, Image Reconstruction, Image Super-Resolution, Operator learning, Super-Resolution

Exploiting a priori known structural information lies at the core of many
image reconstruction methods that can be stated as inverse problems. The
synthesis model, which assumes that images can be decomposed into a linear
combination of very few atoms of some dictionary, is now a well established
tool for the design of image reconstruction algorithms. An interesting
alternative is the analysis model, where the signal is multiplied by an
analysis operator and the outcome is assumed to be the sparse. This approach
has only recently gained increasing interest. The quality of reconstruction
methods based on an analysis model severely depends on the right choice of the
suitable operator.
  In this work, we present an algorithm for learning an analysis operator from
training images. Our method is based on an $\ell_p$-norm minimization on the
set of full rank matrices with normalized columns. We carefully introduce the
employed conjugate gradient method on manifolds, and explain the underlying
geometry of the constraints. Moreover, we compare our approach to
state-of-the-art methods for image denoising, inpainting, and single image
super-resolution. Our numerical results show competitive performance of our
general approach in all presented applications compared to the specialized
state-of-the-art techniques.
Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems
Authors: David R. Karger, Sewoong Oh, Devavrat Shah
Date: 2011-10-17 00:00:00
Tasks: image-classification, Image Classification, Optical Character Recognition, Optical Character Recognition (OCR)

Crowdsourcing systems, in which numerous tasks are electronically distributed
to numerous "information piece-workers", have emerged as an effective paradigm
for human-powered solving of large scale problems in domains such as image
classification, data entry, optical character recognition, recommendation, and
proofreading. Because these low-paid workers can be unreliable, nearly all such
systems must devise schemes to increase confidence in their answers, typically
by assigning each task multiple times and combining the answers in an
appropriate manner, e.g. majority voting.
  In this paper, we consider a general model of such crowdsourcing tasks and
pose the problem of minimizing the total price (i.e., number of task
assignments) that must be paid to achieve a target overall reliability. We give
a new algorithm for deciding which tasks to assign to which workers and for
inferring correct answers from the workers' answers. We show that our
algorithm, inspired by belief propagation and low-rank matrix approximation,
significantly outperforms majority voting and, in fact, is optimal through
comparison to an oracle that knows the reliability of every worker. Further, we
compare our approach with a more general class of algorithms which can
dynamically assign tasks. By adaptively deciding which questions to ask to the
next arriving worker, one might hope to reduce uncertainty more efficiently. We
show that, perhaps surprisingly, the minimum price necessary to achieve a
target reliability scales in the same manner under both adaptive and
non-adaptive scenarios. Hence, our non-adaptive approach is order-optimal under
both scenarios. This strongly relies on the fact that workers are fleeting and
can not be exploited. Therefore, architecturally, our results suggest that
building a reliable worker-reputation system is essential to fully harnessing
the potential of adaptive designs.
Simulation of Fractional Brownian Surfaces via Spectral Synthesis on Manifolds
Authors: Zachary Gelbaum, Mathew Titus
Date: 2013-03-26 00:00:00

Using the spectral decomposition of the Laplace-Beltrami operator we simulate
fractal surfaces as random series of eigenfunctions. This approach allows us to
generate random fields over smooth manifolds of arbitrary dimension,
generalizing previous work with fractional Brownian motion with
multi-dimensional parameter. We give examples of surfaces with and without
boundary and discuss implementation.
Convex Tensor Decomposition via Structured Schatten Norm Regularization
Authors: Ryota Tomioka, Taiji Suzuki
Date: 2013-03-26 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Tensor Decomposition

We discuss structured Schatten norms for tensor decomposition that includes
two recently proposed norms ("overlapped" and "latent") for
convex-optimization-based tensor decomposition, and connect tensor
decomposition with wider literature on structured sparsity. Based on the
properties of the structured Schatten norms, we mathematically analyze the
performance of "latent" approach for tensor decomposition, which was
empirically found to perform better than the "overlapped" approach in some
settings. We show theoretically that this is indeed the case. In particular,
when the unknown true tensor is low-rank in a specific mode, this approach
performs as good as knowing the mode with the smallest rank. Along the way, we
show a novel duality result for structures Schatten norms, establish the
consistency, and discuss the identifiability of this approach. We confirm
through numerical simulations that our theoretical prediction can precisely
predict the scaling behavior of the mean squared error.
Video Face Matching using Subset Selection and Clustering of Probabilistic Multi-Region Histograms
Authors: Sandra Mau, Shaokang Chen, Conrad Sanderson, Brian C. Lovell
Date: 2013-03-26 00:00:00
Tasks: All, Clustering, Computational Efficiency, Face Detection, Face Recognition, Face Selection

Balancing computational efficiency with recognition accuracy is one of the major challenges in real-world video-based face recognition. A significant design decision for any such system is whether to process and use all possible faces detected over the video frames, or whether to select only a few "best" faces. This paper presents a video face recognition system based on probabilistic Multi-Region Histograms to characterise performance trade-offs in: (i) selecting a subset of faces compared to using all faces, and (ii) combining information from all faces via clustering. Three face selection metrics are evaluated for choosing a subset: face detection confidence, random subset, and sequential selection. Experiments on the recently introduced MOBIO dataset indicate that the usage of all faces through clustering always outperformed selecting only a subset of faces. The experiments also show that the face selection metric based on face detection confidence generally provides better recognition performance than random or sequential sampling. Moreover, the optimal number of faces varies drastically across selection metric and subsets of MOBIO. Given the trade-offs between computational effort, recognition accuracy and robustness, it is recommended that face feature clustering would be most advantageous in batch processing (particularly for video-based watchlists), whereas face selection methods should be limited to applications with significant computational restrictions.
Hypothesis Testing in Feedforward Networks with Broadcast Failures
Authors: Zhenliang Zhang, Edwin K. P. Chong, Ali Pezeshki, William Moran
Date: 2012-11-19 00:00:00
Tasks: Two-sample testing

Consider a countably infinite set of nodes, which sequentially make decisions
between two given hypotheses. Each node takes a measurement of the underlying
truth, observes the decisions from some immediate predecessors, and makes a
decision between the given hypotheses. We consider two classes of broadcast
failures: 1) each node broadcasts a decision to the other nodes, subject to
random erasure in the form of a binary erasure channel; 2) each node broadcasts
a randomly flipped decision to the other nodes in the form of a binary
symmetric channel. We are interested in whether there exists a decision
strategy consisting of a sequence of likelihood ratio tests such that the node
decisions converge in probability to the underlying truth. In both cases, we
show that if each node only learns from a bounded number of immediate
predecessors, then there does not exist a decision strategy such that the
decisions converge in probability to the underlying truth. However, in case 1,
we show that if each node learns from an unboundedly growing number of
predecessors, then the decisions converge in probability to the underlying
truth, even when the erasure probabilities converge to 1. We also derive the
convergence rate of the error probability. In case 2, we show that if each node
learns from all of its previous predecessors, then the decisions converge in
probability to the underlying truth when the flipping probabilities of the
binary symmetric channels are bounded away from 1/2. In the case where the
flipping probabilities converge to 1/2, we derive a necessary condition on the
convergence rate of the flipping probabilities such that the decisions still
converge to the underlying truth. We also explicitly characterize the
relationship between the convergence rate of the error probability and the
convergence rate of the flipping probabilities.
Random Intersection Trees
Authors: Rajen Dinesh Shah, Nicolai Meinshausen
Date: 2013-03-25 00:00:00

Finding interactions between variables in large and high-dimensional datasets
is often a serious computational challenge. Most approaches build up
interaction sets incrementally, adding variables in a greedy fashion. The
drawback is that potentially informative high-order interactions may be
overlooked. Here, we propose at an alternative approach for classification
problems with binary predictor variables, called Random Intersection Trees. It
works by starting with a maximal interaction that includes all variables, and
then gradually removing variables if they fail to appear in randomly chosen
observations of a class of interest. We show that informative interactions are
retained with high probability, and the computational complexity of our
procedure is of order $p^\kappa$ for a value of $\kappa$ that can reach values
as low as 1 for very sparse data; in many more general settings, it will still
beat the exponent $s$ obtained when using a brute force search constrained to
order $s$ interactions. In addition, by using some new ideas based on min-wise
hash schemes, we are able to further reduce the computational cost.
Interactions found by our algorithm can be used for predictive modelling in
various forms, but they are also often of interest in their own right as useful
characterisations of what distinguishes a certain class from others.
Regression for sets of polynomial equations
Authors: Franz Johannes Király, Paul von Bünau, Jan Saputra Müller, Duncan Blythe, Frank Meinecke, Klaus-Robert Müller
Date: 2011-10-20 00:00:00
Tasks: regression

We propose a method called ideal regression for approximating an arbitrary
system of polynomial equations by a system of a particular type. Using
techniques from approximate computational algebraic geometry, we show how we
can solve ideal regression directly without resorting to numerical
optimization. Ideal regression is useful whenever the solution to a learning
problem can be described by a system of polynomial equations. As an example, we
demonstrate how to formulate Stationary Subspace Analysis (SSA), a source
separation problem, in terms of ideal regression, which also yields a
consistent estimator for SSA. We then compare this estimator in simulations
with previous optimization-based approaches for SSA.
Compression as a universal principle of animal behavior
Authors: R. Ferrer-i-Cancho, A. Hernández-Fernández, D. Lusseau, G. Agoramoorthy, M. J. Hsu, S. Semple
Date: 2013-03-25 00:00:00

A key aim in biology and psychology is to identify fundamental principles
underpinning the behavior of animals, including humans. Analyses of human
language and the behavior of a range of non-human animal species have provided
evidence for a common pattern underlying diverse behavioral phenomena: words
follow Zipf's law of brevity (the tendency of more frequently used words to be
shorter), and conformity to this general pattern has been seen in the behavior
of a number of other animals. It has been argued that the presence of this law
is a sign of efficient coding in the information theoretic sense. However, no
strong direct connection has been demonstrated between the law and compression,
the information theoretic principle of minimizing the expected length of a
code. Here we show that minimizing the expected code length implies that the
length of a word cannot increase as its frequency increases. Furthermore, we
show that the mean code length or duration is significantly small in human
language, and also in the behavior of other species in all cases where
agreement with the law of brevity has been found. We argue that compression is
a general principle of animal behavior, that reflects selection for efficiency
of coding.
On Sparsity Inducing Regularization Methods for Machine Learning
Authors: Andreas Argyriou, Luca Baldassarre, Charles A. Micchelli, Massimiliano Pontil
Date: 2013-03-25 00:00:00
Tasks: BIG-bench Machine Learning, Multi-Task Learning

During the past years there has been an explosion of interest in learning
methods based on sparsity regularization. In this paper, we discuss a general
class of such methods, in which the regularizer can be expressed as the
composition of a convex function $\omega$ with a linear function. This setting
includes several methods such the group Lasso, the Fused Lasso, multi-task
learning and many more. We present a general approach for solving
regularization problems of this kind, under the assumption that the proximity
operator of the function $\omega$ is available. Furthermore, we comment on the
application of this approach to support vector machines, a technique pioneered
by the groundbreaking work of Vladimir Vapnik.
Poisoning Attacks against Support Vector Machines
Authors: Battista Biggio, Blaine Nelson, Pavel Laskov
Date: 2012-06-27 00:00:00

We investigate a family of poisoning attacks against Support Vector Machines
(SVM). Such attacks inject specially crafted training data that increases the
SVM's test error. Central to the motivation for these attacks is the fact that
most learning algorithms assume that their training data comes from a natural
or well-behaved distribution. However, this assumption does not generally hold
in security-sensitive settings. As we demonstrate, an intelligent adversary
can, to some extent, predict the change of the SVM's decision function due to
malicious input and use this ability to construct malicious data. The proposed
attack uses a gradient ascent strategy in which the gradient is computed based
on properties of the SVM's optimal solution. This method can be kernelized and
enables the attack to be constructed in the input space even for non-linear
kernels. We experimentally demonstrate that our gradient ascent procedure
reliably identifies good local maxima of the non-convex validation error
surface, which significantly increases the classifier's test error.
Spatio-Temporal Covariance Descriptors for Action and Gesture Recognition
Authors: Andres Sanin, Conrad Sanderson, Mehrtash T. Harandi, Brian C. Lovell
Date: 2013-03-25 00:00:00
Tasks: General Classification, Gesture Recognition, Interest Point Detection

We propose a new action and gesture recognition method based on spatio-temporal covariance descriptors and a weighted Riemannian locality preserving projection approach that takes into account the curved space formed by the descriptors. The weighted projection is then exploited during boosting to create a final multiclass classification algorithm that employs the most useful spatio-temporal regions. We also show how the descriptors can be computed quickly through the use of integral video representations. Experiments on the UCF sport, CK+ facial expression and Cambridge hand gesture datasets indicate superior performance of the proposed method compared to several recent state-of-the-art techniques. The proposed method is robust and does not require additional processing of the videos, such as foreground detection, interest-point detection or tracking.
Generalizing k-means for an arbitrary distance matrix
Authors: Balázs Szalkai
Date: 2013-03-24 00:00:00
Tasks: Clustering

The original k-means clustering method works only if the exact vectors
representing the data points are known. Therefore calculating the distances
from the centroids needs vector operations, since the average of abstract data
points is undefined. Existing algorithms can be extended for those cases when
the sole input is the distance matrix, and the exact representing vectors are
unknown. This extension may be named relational k-means after a notation for a
similar algorithm invented for fuzzy clustering. A method is then proposed for
generalizing k-means for scenarios when the data points have absolutely no
connection with a Euclidean space.
Efficient Reinforcement Learning for High Dimensional Linear Quadratic Systems
Authors: Morteza Ibrahimi, Adel Javanmard, Benjamin Van Roy
Date: 2013-03-24 00:00:00
Proceeding: NeurIPS 2012 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Vocal Bursts Intensity Prediction

We study the problem of adaptive control of a high dimensional linear
quadratic (LQ) system. Previous work established the asymptotic convergence to
an optimal controller for various adaptive control schemes. More recently, for
the average cost LQ problem, a regret bound of ${O}(\sqrt{T})$ was shown, apart
form logarithmic factors. However, this bound scales exponentially with $p$,
the dimension of the state space. In this work we consider the case where the
matrices describing the dynamic of the LQ system are sparse and their
dimensions are large. We present an adaptive control scheme that achieves a
regret bound of ${O}(p \sqrt{T})$, apart from logarithmic factors. In
particular, our algorithm has an average cost of $(1+\eps)$ times the optimum
cost after $T = \polylog(p) O(1/\eps^2)$. This is in comparison to previous
work on the dense dynamics where the algorithm requires time that scales
exponentially with dimension in order to achieve regret of $\eps$ times the
optimal cost.
  We believe that our result has prominent applications in the emerging area of
computational advertising, in particular targeted online advertising and
advertising in social networks.