pwc-archive/papers-with-abstracts huggingface dataset:
The complexity of learning halfspaces using generalized linear methods
Authors: Amit Daniely, Nati Linial, Shai Shalev-Shwartz
Date: 2012-11-03 00:00:00
Tasks: regression

Many popular learning algorithms (E.g. Regression, Fourier-Transform based
algorithms, Kernel SVM and Kernel ridge regression) operate by reducing the
problem to a convex optimization problem over a vector space of functions.
These methods offer the currently best approach to several central problems
such as learning half spaces and learning DNF's. In addition they are widely
used in numerous application domains. Despite their importance, there are still
very few proof techniques to show limits on the power of these algorithms.
  We study the performance of this approach in the problem of (agnostically and
improperly) learning halfspaces with margin $\gamma$. Let $\mathcal{D}$ be a
distribution over labeled examples. The $\gamma$-margin error of a hyperplane
$h$ is the probability of an example to fall on the wrong side of $h$ or at a
distance $\le\gamma$ from it. The $\gamma$-margin error of the best $h$ is
denoted $\mathrm{Err}_\gamma(\mathcal{D})$. An $\alpha(\gamma)$-approximation
algorithm receives $\gamma,\epsilon$ as input and, using i.i.d. samples of
$\mathcal{D}$, outputs a classifier with error rate $\le
\alpha(\gamma)\mathrm{Err}_\gamma(\mathcal{D}) + \epsilon$. Such an algorithm
is efficient if it uses $\mathrm{poly}(\frac{1}{\gamma},\frac{1}{\epsilon})$
samples and runs in time polynomial in the sample size.
  The best approximation ratio achievable by an efficient algorithm is
$O\left(\frac{1/\gamma}{\sqrt{\log(1/\gamma)}}\right)$ and is achieved using an
algorithm from the above class. Our main result shows that the approximation
ratio of every efficient algorithm from this family must be $\ge
\Omega\left(\frac{1/\gamma}{\mathrm{poly}\left(\log\left(1/\gamma\right)\right)}\right)$,
essentially matching the best known upper bound.
A PAC-Bayesian bound for Lifelong Learning
Authors: Anastasia Pentina, Christoph H. Lampert
Date: 2013-11-12 00:00:00
Tasks: Lifelong learning, Transfer Learning

Transfer learning has received a lot of attention in the machine learning
community over the last years, and several effective algorithms have been
developed. However, relatively little is known about their theoretical
properties, especially in the setting of lifelong learning, where the goal is
to transfer information to tasks for which no data have been observed so far.
In this work we study lifelong learning from a theoretical perspective. Our
main result is a PAC-Bayesian generalization bound that offers a unified view
on existing paradigms for transfer learning, such as the transfer of parameters
or the transfer of low-dimensional representations. We also use the bound to
derive two principled lifelong learning algorithms, and we show that these
yield results comparable with existing methods.
Hyperspectral pan-sharpening: a variational convex constrained formulation to impose parallel level lines, solved with ADMM
Authors: Alexis Huck, François de Vieilleville, Pierre Weiss, Manuel Grizonnet
Date: 2014-05-10 00:00:00

In this paper, we address the issue of hyperspectral pan-sharpening, which
consists in fusing a (low spatial resolution) hyperspectral image HX and a
(high spatial resolution) panchromatic image P to obtain a high spatial
resolution hyperspectral image. The problem is addressed under a variational
convex constrained formulation. The objective favors high resolution spectral
bands with level lines parallel to those of the panchromatic image. This term
is balanced with a total variation term as regularizer. Fit-to-P data and
fit-to-HX data constraints are effectively considered as mathematical
constraints, which depend on the statistics of the data noise measurements. The
developed Alternating Direction Method of Multipliers (ADMM) optimization
scheme enables us to solve this problem efficiently despite the non
differentiabilities and the huge number of unknowns.
Predicting Central Topics in a Blog Corpus from a Networks Perspective
Authors: Srayan Datta
Date: 2014-05-10 00:00:00

In today's content-centric Internet, blogs are becoming increasingly popular
and important from a data analysis perspective. According to Wikipedia, there
were over 156 million public blogs on the Internet as of February 2011. Blogs
are a reflection of our contemporary society. The contents of different blog
posts are important from social, psychological, economical and political
perspectives. Discovery of important topics in the blogosphere is an area which
still needs much exploring. We try to come up with a procedure using
probabilistic topic modeling and network centrality measures which identifies
the central topics in a blog corpus.
A Hybrid Monte Carlo Architecture for Parameter Optimization
Authors: James Brofos
Date: 2014-05-10 00:00:00
Tasks: regression

Much recent research has been conducted in the area of Bayesian learning,
particularly with regard to the optimization of hyper-parameters via Gaussian
process regression. The methodologies rely chiefly on the method of maximizing
the expected improvement of a score function with respect to adjustments in the
hyper-parameters. In this work, we present a novel algorithm that exploits
notions of confidence intervals and uncertainties to enable the discovery of
the best optimal within a targeted region of the parameter space. We
demonstrate the efficacy of our algorithm with respect to machine learning
problems and show cases where our algorithm is competitive with the method of
maximizing expected improvement.
Bounding the Test Log-Likelihood of Generative Models
Authors: Yoshua Bengio, Li Yao, Kyunghyun Cho
Date: 2013-11-24 00:00:00

Several interesting generative learning algorithms involve a complex
probability distribution over many random variables, involving intractable
normalization constants or latent variable normalization. Some of them may even
not have an analytic expression for the unnormalized probability function and
no tractable approximation. This makes it difficult to estimate the quality of
these models, once they have been trained, or to monitor their quality (e.g.
for early stopping) while training. A previously proposed method is based on
constructing a non-parametric density estimator of the model's probability
function from samples generated by the model. We revisit this idea, propose a
more efficient estimator, and prove that it provides a lower bound on the true
test log-likelihood, and an unbiased estimator as the number of generated
samples goes to infinity, although one that incorporates the effect of poor
mixing. We further propose a biased variant of the estimator that can be used
reliably with a finite number of samples for the purpose of model comparison.
Image Segmentation Using Frequency Locking of Coupled Oscillators
Authors: Yan Fang, Matthew J. Cotter, Donald M. Chiarulli, Steven P. Levitan
Date: 2014-05-09 00:00:00
Tasks: Image Segmentation, Segmentation, Semantic Segmentation

Synchronization of coupled oscillators is observed at multiple levels of
neural systems, and has been shown to play an important function in visual
perception. We propose a computing system based on locally coupled oscillator
networks for image segmentation. The system can serve as the preprocessing
front-end of an image processing pipeline where the common frequencies of
clusters of oscillators reflect the segmentation results. To demonstrate the
feasibility of our design, the system is simulated and tested on a human face
image dataset and its performance is compared with traditional intensity
threshold based algorithms. Our system shows both better performance and higher
noise tolerance than traditional methods.
Better Feature Tracking Through Subspace Constraints
Authors: Bryan Poling, Gilad Lerman, Arthur Szlam
Date: 2014-05-09 00:00:00
Proceeding: CVPR 2014 6
Tasks: CPU

Feature tracking in video is a crucial task in computer vision. Usually, the
tracking problem is handled one feature at a time, using a single-feature
tracker like the Kanade-Lucas-Tomasi algorithm, or one of its derivatives.
While this approach works quite well when dealing with high-quality video and
"strong" features, it often falters when faced with dark and noisy video
containing low-quality features. We present a framework for jointly tracking a
set of features, which enables sharing information between the different
features in the scene. We show that our method can be employed to track
features for both rigid and nonrigid motions (possibly of few moving bodies)
even when some features are occluded. Furthermore, it can be used to
significantly improve tracking results in poorly-lit scenes (where there is a
mix of good and bad features). Our approach does not require direct modeling of
the structure or the motion of the scene, and runs in real time on a single CPU
core.
A bi-level view of inpainting - based image compression
Authors: Yunjin Chen, René Ranftl, Thomas Pock
Date: 2014-01-16 00:00:00
Tasks: Descriptive, Image Compression

Inpainting based image compression approaches, especially linear and
non-linear diffusion models, are an active research topic for lossy image
compression. The major challenge in these compression models is to find a small
set of descriptive supporting points, which allow for an accurate
reconstruction of the original image. It turns out in practice that this is a
challenging problem even for the simplest Laplacian interpolation model. In
this paper, we revisit the Laplacian interpolation compression model and
introduce two fast algorithms, namely successive preconditioning primal dual
algorithm and the recently proposed iPiano algorithm, to solve this problem
efficiently. Furthermore, we extend the Laplacian interpolation based
compression model to a more general form, which is based on principles from
bi-level optimization. We investigate two different variants of the Laplacian
model, namely biharmonic interpolation and smoothed Total Variation
regularization. Our numerical results show that significant improvements can be
obtained from the biharmonic interpolation model, and it can recover an image
with very high quality from only 5% pixels.
Hellinger Distance Trees for Imbalanced Streams
Authors: R. J. Lyon, J. M. Brooke, J. D. Knowles, B. W. Stappers
Date: 2014-05-09 00:00:00

Classifiers trained on data sets possessing an imbalanced class distribution
are known to exhibit poor generalisation performance. This is known as the
imbalanced learning problem. The problem becomes particularly acute when we
consider incremental classifiers operating on imbalanced data streams,
especially when the learning objective is rare class identification. As
accuracy may provide a misleading impression of performance on imbalanced data,
existing stream classifiers based on accuracy can suffer poor minority class
performance on imbalanced streams, with the result being low minority class
recall rates. In this paper we address this deficiency by proposing the use of
the Hellinger distance measure, as a very fast decision tree split criterion.
We demonstrate that by using Hellinger a statistically significant improvement
in recall rates on imbalanced data streams can be achieved, with an acceptable
increase in the false positive rate.
Training Deep Fourier Neural Networks To Fit Time-Series Data
Authors: Michael S. Gashler, Stephen C. Ashmore
Date: 2014-05-09 00:00:00
Tasks: Time Series, Time Series Analysis

We present a method for training a deep neural network containing sinusoidal
activation functions to fit to time-series data. Weights are initialized using
a fast Fourier transform, then trained with regularization to improve
generalization. A simple dynamic parameter tuning method is employed to adjust
both the learning rate and regularization term, such that stability and
efficient training are both achieved. We show how deeper layers can be utilized
to model the observed sequence using a sparser set of sinusoid units, and how
non-uniform regularization can improve generalization by promoting the shifting
of weight toward simpler units. The method is demonstrated with time-series
problems to show that it leads to effective extrapolation of nonlinear trends.
Graph Regularized Non-negative Matrix Factorization By Maximizing Correntropy
Authors: Le Li, Jianjun Yang, Kaili Zhao, Yang Xu, Honggang Zhang, Zhuoyi Fan
Date: 2014-05-09 00:00:00
Tasks: Clustering, Image Clustering

Non-negative matrix factorization (NMF) has proved effective in many
clustering and classification tasks. The classic ways to measure the errors
between the original and the reconstructed matrix are $l_2$ distance or
Kullback-Leibler (KL) divergence. However, nonlinear cases are not properly
handled when we use these error measures. As a consequence, alternative
measures based on nonlinear kernels, such as correntropy, are proposed.
However, the current correntropy-based NMF only targets on the low-level
features without considering the intrinsic geometrical distribution of data. In
this paper, we propose a new NMF algorithm that preserves local invariance by
adding graph regularization into the process of max-correntropy-based matrix
factorization. Meanwhile, each feature can learn corresponding kernel from the
data. The experiment results of Caltech101 and Caltech256 show the benefits of
such combination against other NMF algorithms for the unsupervised image
clustering.
An Overview of Face Liveness Detection
Authors: Saptarshi Chakraborty, Dhrubajyoti Das
Date: 2014-05-09 00:00:00
Tasks: Face Recognition

Face recognition is a widely used biometric approach. Face recognition technology has developed rapidly in recent years and it is more direct, user friendly and convenient compared to other methods. But face recognition systems are vulnerable to spoof attacks made by non-real faces. It is an easy way to spoof face recognition systems by facial pictures such as portrait photographs. A secure system needs Liveness detection in order to guard against such spoofing. In this work, face liveness detection approaches are categorized based on the various types techniques used for liveness detection. This categorization helps understanding different spoof attacks scenarios and their relation to the developed solutions. A review of the latest works regarding face liveness detection works is presented. The main aim is to provide a simple path for the future development of novel and more secured face liveness detection approach.
Gaussian-Chain Filters for Heavy-Tailed Noise with Application to Detecting Big Buyers and Big Sellers in Stock Market
Authors: Li-Xin Wang
Date: 2014-05-09 00:00:00

We propose a new heavy-tailed distribution --- Gaussian-Chain (GC)
distribution, which is inspirited by the hierarchical structures prevailing in
social organizations. We determine the mean, variance and kurtosis of the
Gaussian-Chain distribution to show its heavy-tailed property, and compute the
tail distribution table to give specific numbers showing how heavy is the
heavy-tails. To filter out the heavy-tailed noise, we construct two filters ---
2nd and 3rd-order GC filters --- based on the maximum likelihood principle.
Simulation results show that the GC filters perform much better than the
benchmark least-squares algorithm when the noise is heavy-tail distributed.
Using the GC filters, we propose a trading strategy, named Ride-the-Mood, to
follow the mood of the market by detecting the actions of the big buyers and
the big sellers in the market based on the noisy, heavy-tailed price data.
Application of the Ride-the-Mood strategy to five blue-chip Hong Kong stocks
over the recent two-year period from April 2, 2012 to March 31, 2014 shows that
their returns are higher than the returns of the benchmark Buy-and-Hold
strategy and the Hang Seng Index Fund.
FO(C): A Knowledge Representation Language of Causality
Authors: Bart Bogaerts, Joost Vennekens, Marc Denecker, Jan Van den Bussche
Date: 2014-05-08 00:00:00

Cause-effect relations are an important part of human knowledge. In real
life, humans often reason about complex causes linked to complex effects. By
comparison, existing formalisms for representing knowledge about causal
relations are quite limited in the kind of specifications of causes and effects
they allow. In this paper, we present the new language C-Log, which offers a
significantly more expressive representation of effects, including such
features as the creation of new objects. We show how C-Log integrates with
first-order logic, resulting in the language FO(C). We also compare FO(C) with
several related languages and paradigms, including inductive definitions,
disjunctive logic programming, business rules and extensions of Datalog.
Evaluation The Efficiency Of Cuckoo Optimization Algorithm
Authors: Elham Shadkam, Mehdi Bijari
Date: 2014-05-09 00:00:00

In this paper a new evolutionary algorithm, for continuous nonlinear
optimization problems, is surveyed. This method is inspired by the life of a
bird, called Cuckoo. The Cuckoo Optimization Algorithm (COA) is evaluated by
using the Rastrigin function. The problem is a non-linear continuous function
which is used for evaluating optimization algorithms. The efficiency of the COA
has been studied by obtaining optimal solution of various dimensions Rastrigin
function in this paper. The mentioned function also was solved by FA and ABC
algorithms. Comparing the results shows the COA has better performance than
other algorithms. Application of algorithm to test function has proven its
capability to deal with difficult optimization problems.
Cognitive-mapping and contextual pyramid based Digital Elevation Model Registration and its effective storage using fractal based compression
Authors: Suma Dawn, Vikas Saxena, Bhudev Sharma
Date: 2014-05-09 00:00:00
Tasks: Change Detection, Image Registration

Digital Elevation models (DEM) are images having terrain information embedded
into them. Using cognitive mapping concepts for DEM registration, has evolved
from this basic idea of using the mapping between the space to objects and
defining their relationships to form the basic landmarks that need to be
marked, stored and manipulated in and about the environment or other candidate
environments, namely, in our case, the DEMs. The progressive two-level
encapsulation of methods of geo-spatial cognition includes landmark knowledge
and layout knowledge and can be useful for DEM registration. Space-based
approach, that emphasizes on explicit extent of the environment under
consideration, and object-based approach, that emphasizes on the relationships
between objects in the local environment being the two paradigms of cognitive
mapping can be methodically integrated in this three-architecture for DEM
registration. Initially, P-model based segmentation is performed followed by
landmark formation for contextual mapping that uses contextual pyramid
formation. Apart from landmarks being used for registration key-point finding,
Euclidean distance based deformation calculation has been used for
transformation and change detection. Landmarks have been categorized to belong
to either being flat-plain areas without much variation in the land heights;
peaks that can be found when there is gradual increase in height as compared to
the flat areas; valleys, marked with gradual decrease in the height seen in
DEM; and finally, ripple areas with very shallow crests and nadirs. Fractal
based compression was used for storage of co-registered DEMs. This method may
further be extended for DEM-topographic map and DEM-to-remote sensed image
registration. Experimental results further cement the fact that DEM
registration may be effectively done using the proposed method.
New explicit thresholding/shrinkage formulas for one class of regularization problems with overlapping group sparsity and their applications
Authors: Gang Liu, Ting-Zhu Huang, Xiao-Guang Lv, Jun Liu
Date: 2013-12-24 00:00:00
Tasks: Compressive Sensing, Deblurring, Denoising, Translation

The least-square regression problems or inverse problems have been widely
studied in many fields such as compressive sensing, signal processing, and
image processing. To solve this kind of ill-posed problems, a regularization
term (i.e., regularizer) should be introduced, under the assumption that the
solutions have some specific properties, such as sparsity and group sparsity.
Widely used regularizers include the $\ell_1$ norm, total variation (TV)
semi-norm, and so on.
  Recently, a new regularization term with overlapping group sparsity has been
considered. Majorization minimization iteration method or variable duplication
methods are often applied to solve them. However, there have been no direct
methods for solve the relevant problems because of the difficulty of
overlapping. In this paper, we proposed new explicit shrinkage formulas for one
class of these relevant problems, whose regularization terms have translation
invariant overlapping groups. Moreover, we apply our results in TV deblurring
and denoising with overlapping group sparsity. We use alternating direction
method of multipliers to iterate solve it. Numerical results also verify the
validity and effectiveness of our new explicit shrinkage formulas.
On-line PCA with Optimal Regrets
Authors: Jiazhong Nie, Wojciech Kotlowski, Manfred K. Warmuth
Date: 2013-06-17 00:00:00

We carefully investigate the on-line version of PCA, where in each trial a
learning algorithm plays a k-dimensional subspace, and suffers the compression
loss on the next instance when projected into the chosen subspace. In this
setting, we analyze two popular on-line algorithms, Gradient Descent (GD) and
Exponentiated Gradient (EG). We show that both algorithms are essentially
optimal in the worst-case. This comes as a surprise, since EG is known to
perform sub-optimally when the instances are sparse. This different behavior of
EG for PCA is mainly related to the non-negativity of the loss in this case,
which makes the PCA setting qualitatively different from other settings studied
in the literature. Furthermore, we show that when considering regret bounds as
function of a loss budget, EG remains optimal and strictly outperforms GD.
Next, we study the extension of the PCA setting, in which the Nature is allowed
to play with dense instances, which are positive matrices with bounded largest
eigenvalue. Again we can show that EG is optimal and strictly better than GD in
this setting.
Kaggle LSHTC4 Winning Solution
Authors: Antti Puurula, Jesse Read, Albert Bifet
Date: 2014-05-03 00:00:00
Tasks: text-classification, Text Classification

Our winning submission to the 2014 Kaggle competition for Large Scale
Hierarchical Text Classification (LSHTC) consists mostly of an ensemble of
sparse generative models extending Multinomial Naive Bayes. The
base-classifiers consist of hierarchically smoothed models combining document,
label, and hierarchy level Multinomials, with feature pre-processing using
variants of TF-IDF and BM25. Additional diversification is introduced by
different types of folds and random search optimization for different measures.
The ensemble algorithm optimizes macroFscore by predicting the documents for
each label, instead of the usual prediction of labels per document. Scores for
documents are predicted by weighted voting of base-classifier outputs with a
variant of Feature-Weighted Linear Stacking. The number of documents per label
is chosen using label priors and thresholding of vote scores. This document
describes the models and software used to build our solution. Reproducing the
results for our solution can be done by running the scripts included in the
Kaggle package. A package omitting precomputed result files is also
distributed. All code is open source, released under GNU GPL 2.0, and GPL 3.0
for Weka and Meka dependencies.