pwc-archive/papers-with-abstracts huggingface dataset:
Learning with Square Loss: Localization through Offset Rademacher Complexity
Authors: Tengyuan Liang, Alexander Rakhlin, Karthik Sridharan
Date: 2015-02-21 00:00:00
Tasks: regression

We consider regression with square loss and general classes of functions
without the boundedness assumption. We introduce a notion of offset Rademacher
complexity that provides a transparent way to study localization both in
expectation and in high probability. For any (possibly non-convex) class, the
excess loss of a two-step estimator is shown to be upper bounded by this offset
complexity through a novel geometric inequality. In the convex case, the
estimator reduces to an empirical risk minimizer. The method recovers the
results of \citep{RakSriTsy15} for the bounded case while also providing
guarantees without the boundedness assumption.
Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
Authors: Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, Alexander Rakhlin
Date: 2015-01-28 00:00:00

We consider the problem of optimizing an approximately convex function over a
bounded convex set in $\mathbb{R}^n$ using only function evaluations. The
problem is reduced to sampling from an \emph{approximately} log-concave
distribution using the Hit-and-Run method, which is shown to have the same
$\mathcal{O}^*$ complexity as sampling from log-concave distributions. In
addition to extend the analysis for log-concave distributions to approximate
log-concave distributions, the implementation of the 1-dimensional sampler of
the Hit-and-Run walk requires new methods and analysis. The algorithm then is
based on simulated annealing which does not relies on first order conditions
which makes it essentially immune to local minima.
  We then apply the method to different motivating problems. In the context of
zeroth order stochastic convex optimization, the proposed method produces an
$\epsilon$-minimizer after $\mathcal{O}^*(n^{7.5}\epsilon^{-2})$ noisy function
evaluations by inducing a $\mathcal{O}(\epsilon/n)$-approximately log concave
distribution. We also consider in detail the case when the "amount of
non-convexity" decays towards the optimum of the function. Other applications
of the method discussed in this work include private computation of empirical
risk minimizers, two-stage stochastic programming, and approximate dynamic
programming for online learning.
Transfer Learning for Video Recognition with Scarce Training Data for Deep Convolutional Neural Network
Authors: Yu-Chuan Su, Tzu-Hsuan Chiu, Chun-Yen Yeh, Hsin-Fu Huang, Winston H. Hsu
Date: 2014-09-15 00:00:00
Tasks: 4k, Transfer Learning, Video Recognition

Unconstrained video recognition and Deep Convolution Network (DCN) are two
active topics in computer vision recently. In this work, we apply DCNs as
frame-based recognizers for video recognition. Our preliminary studies,
however, show that video corpora with complete ground truth are usually not
large and diverse enough to learn a robust model. The networks trained directly
on the video data set suffer from significant overfitting and have poor
recognition rate on the test set. The same lack-of-training-sample problem
limits the usage of deep models on a wide range of computer vision problems
where obtaining training data are difficult. To overcome the problem, we
perform transfer learning from images to videos to utilize the knowledge in the
weakly labeled image corpus for video recognition. The image corpus help to
learn important visual patterns for natural images, while these patterns are
ignored by models trained only on the video corpus. Therefore, the resultant
networks have better generalizability and better recognition rate. We show that
by means of transfer learning from image to video, we can learn a frame-based
recognizer with only 4k videos. Because the image corpus is weakly labeled, the
entire learning process requires only 4k annotated instances, which is far less
than the million scale image data sets required by previous works. The same
approach may be applied to other visual recognition tasks where only scarce
training data is available, and it improves the applicability of DCNs in
various computer vision problems. Our experiments also reveal the correlation
between meta-parameters and the performance of DCNs, given the properties of
the target problem and data. These results lead to a heuristic for
meta-parameter selection for future researches, which does not rely on the time
consuming meta-parameter search.
Flow Segmentation in Dense Crowds
Authors: Javairia Nazir, Mehreen Sirshar
Date: 2015-06-15 00:00:00
Tasks: Numerical Integration, Position, Segmentation

A framework is proposed in this paper that is used to segment flow of dense
crowds. The flow field that is generated by the movement in the crowd is
treated just like an aperiodic dynamic system. On this flow field a grid of
particles is put over for particle advection by the use of a numerical
integration scheme. Then flow maps are generated which associates the initial
position of the particles with final position. The gradient of the flow maps
gives the amount of divergence of the neighboring particles. For forward
integration and analysis forward Finite time Lyapunov Exponent is calculated
and backward Finite time Lyapunov Exponent is also calculated it gives the
Lagrangian coherent structures of the flow in crowd. Lagrangian Coherent
Structures basically divides the flow in crowd into regions and these regions
have different dynamics. These regions are then used to get the boundary in the
different flow segments by using water shed algorithm. The experiment is
conducted on the crowd dataset of UCF (University of central Florida).
Learning with incremental iterative regularization
Authors: Lorenzo Rosasco, Silvia Villa
Date: 2014-04-30 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: BIG-bench Machine Learning

Within a statistical learning setting, we propose and study an iterative
regularization algorithm for least squares defined by an incremental gradient
method. In particular, we show that, if all other parameters are fixed a
priori, the number of passes over the data (epochs) acts as a regularization
parameter, and prove strong universal consistency, i.e. almost sure convergence
of the risk, as well as sharp finite sample bounds for the iterates. Our
results are a step towards understanding the effect of multiple epochs in
stochastic gradient techniques in machine learning and rely on integrating
statistical and optimization results.
Re-scale AdaBoost for Attack Detection in Collaborative Filtering Recommender Systems
Authors: Zhihai Yang, Lin Xu, Zhongmin Cai
Date: 2015-06-15 00:00:00
Tasks: Collaborative Filtering, General Classification, imbalanced classification, Recommendation Systems

Collaborative filtering recommender systems (CFRSs) are the key components of
successful e-commerce systems. Actually, CFRSs are highly vulnerable to attacks
since its openness. However, since attack size is far smaller than that of
genuine users, conventional supervised learning based detection methods could
be too "dull" to handle such imbalanced classification. In this paper, we
improve detection performance from following two aspects. First, we extract
well-designed features from user profiles based on the statistical properties
of the diverse attack models, making hard classification task becomes easier to
perform. Then, refer to the general idea of re-scale Boosting (RBoosting) and
AdaBoost, we apply a variant of AdaBoost, called the re-scale AdaBoost
(RAdaBoost) as our detection method based on extracted features. RAdaBoost is
comparable to the optimal Boosting-type algorithm and can effectively improve
the performance in some hard scenarios. Finally, a series of experiments on the
MovieLens-100K data set are conducted to demonstrate the outperformance of
RAdaBoost comparing with some classical techniques such as SVM, kNN and
AdaBoost.
Variational Recurrent Auto-Encoders
Authors: Otto Fabius, Joost R. van Amersfoort
Date: 2014-12-20 00:00:00
Tasks: Time Series, Time Series Analysis

In this paper we propose a model that combines the strengths of RNNs and
SGVB: the Variational Recurrent Auto-Encoder (VRAE). Such a model can be used
for efficient, large scale unsupervised learning on time series data, mapping
the time series data to a latent vector representation. The model is
generative, such that data can be generated from samples of the latent space.
An important contribution of this work is that the model can make use of
unlabeled data in order to facilitate supervised training of RNNs by
initialising the weights and network state.
Optimising Spatial and Tonal Data for PDE-based Inpainting
Authors: Laurent Hoeltgen, Markus Mainberger, Sebastian Hoffmann, Joachim Weickert, Ching Hoo Tang, Simon Setzer, Daniel Johannsen, Frank Neumann, Benjamin Doerr
Date: 2015-06-15 00:00:00
Tasks: Image Compression

Some recent methods for lossy signal and image compression store only a few
selected pixels and fill in the missing structures by inpainting with a partial
differential equation (PDE). Suitable operators include the Laplacian, the
biharmonic operator, and edge-enhancing anisotropic diffusion (EED). The
quality of such approaches depends substantially on the selection of the data
that is kept. Optimising this data in the domain and codomain gives rise to
challenging mathematical problems that shall be addressed in our work.
  In the 1D case, we prove results that provide insights into the difficulty of
this problem, and we give evidence that a splitting into spatial and tonal
(i.e. function value) optimisation does hardly deteriorate the results. In the
2D setting, we present generic algorithms that achieve a high reconstruction
quality even if the specified data is very sparse. To optimise the spatial
data, we use a probabilistic sparsification, followed by a nonlocal pixel
exchange that avoids getting trapped in bad local optima. After this spatial
optimisation we perform a tonal optimisation that modifies the function values
in order to reduce the global reconstruction error. For homogeneous diffusion
inpainting, this comes down to a least squares problem for which we prove that
it has a unique solution. We demonstrate that it can be found efficiently with
a gradient descent approach that is accelerated with fast explicit diffusion
(FED) cycles. Our framework allows to specify the desired density of the
inpainting mask a priori. Moreover, is more generic than other data
optimisation approaches for the sparse inpainting problem, since it can also be
extended to nonlinear inpainting operators such as EED. This is exploited to
achieve reconstructions with state-of-the-art quality.
  We also give an extensive literature survey on PDE-based image compression
methods.
Big Data Analytics in Bioinformatics: A Machine Learning Perspective
Authors: Hirak Kashyap, Hasin Afzal Ahmed, Nazrul Hoque, Swarup Roy, Dhruba Kumar Bhattacharyya
Date: 2015-06-15 00:00:00
Tasks: BIG-bench Machine Learning

Bioinformatics research is characterized by voluminous and incremental
datasets and complex data analytics methods. The machine learning methods used
in bioinformatics are iterative and parallel. These methods can be scaled to
handle big data using the distributed and parallel computing technologies.
  Usually big data tools perform computation in batch-mode and are not
optimized for iterative processing and high data dependency among operations.
In the recent years, parallel, incremental, and multi-view machine learning
algorithms have been proposed. Similarly, graph-based architectures and
in-memory big data tools have been developed to minimize I/O cost and optimize
iterative processing.
  However, there lack standard big data architectures and tools for many
important bioinformatics problems, such as fast construction of co-expression
and regulatory networks and salient module identification, detection of
complexes over growing protein-protein interaction data, fast analysis of
massive DNA, RNA, and protein sequence data, and fast querying on incremental
and heterogeneous disease networks. This paper addresses the issues and
challenges posed by several big data problems in bioinformatics, and gives an
overview of the state of the art and the future research opportunities.
On the Generalization of the C-Bound to Structured Output Ensemble Methods
Authors: François Laviolette, Emilie Morvant, Liva Ralaivola, Jean-Francis Roy
Date: 2014-08-06 00:00:00
Tasks: Binary Classification, General Classification

This paper generalizes an important result from the PAC-Bayesian literature
for binary classification to the case of ensemble methods for structured
outputs. We prove a generic version of the \Cbound, an upper bound over the
risk of models expressed as a weighted majority vote that is based on the first
and second statistical moments of the vote's margin. This bound may
advantageously $(i)$ be applied on more complex outputs such as multiclass
labels and multilabel, and $(ii)$ allow to consider margin relaxations. These
results open the way to develop new ensemble methods for structured output
prediction with PAC-Bayesian guarantees.
Convex Risk Minimization and Conditional Probability Estimation
Authors: Matus Telgarsky, Miroslav Dudík, Robert Schapire
Date: 2015-06-15 00:00:00
Tasks: General Classification

This paper proves, in very general settings, that convex risk minimization is
a procedure to select a unique conditional probability model determined by the
classification problem. Unlike most previous work, we give results that are
general enough to include cases in which no minimum exists, as occurs
typically, for instance, with standard boosting algorithms. Concretely, we
first show that any sequence of predictors minimizing convex risk over the
source distribution will converge to this unique model when the class of
predictors is linear (but potentially of infinite dimension). Secondly, we show
the same result holds for \emph{empirical} risk minimization whenever this
class of predictors is finite dimensional, where the essential technical
contribution is a norm-free generalization bound.
Training Restricted Boltzmann Machines via the Thouless-Anderson-Palmer Free Energy
Authors: Marylou Gabrié, Eric W. Tramel, Florent Krzakala
Date: 2015-06-09 00:00:00

Restricted Boltzmann machines are undirected neural networks which have been
shown to be effective in many applications, including serving as
initializations for training deep multi-layer neural networks. One of the main
reasons for their success is the existence of efficient and practical
stochastic algorithms, such as contrastive divergence, for unsupervised
training. We propose an alternative deterministic iterative procedure based on
an improved mean field method from statistical physics known as the
Thouless-Anderson-Palmer approach. We demonstrate that our algorithm provides
performance equal to, and sometimes superior to, persistent contrastive
divergence, while also providing a clear and easy to evaluate objective
function. We believe that this strategy can be easily generalized to other
models as well as to more accurate higher-order approximations, paving the way
for systematic improvements in training Boltzmann machines with hidden units.
On the properties of variational approximations of Gibbs posteriors
Authors: Pierre Alquier, James Ridgway, Nicolas Chopin
Date: 2015-06-12 00:00:00
Tasks: General Classification, Matrix Completion

The PAC-Bayesian approach is a powerful set of techniques to derive non-
asymptotic risk bounds for random estimators. The corresponding optimal
distribution of estimators, usually called the Gibbs posterior, is
unfortunately intractable. One may sample from it using Markov chain Monte
Carlo, but this is often too slow for big datasets. We consider instead
variational approximations of the Gibbs posterior, which are fast to compute.
We undertake a general study of the properties of such approximations. Our main
finding is that such a variational approximation has often the same rate of
convergence as the original PAC-Bayesian procedure it approximates. We
specialise our results to several learning tasks (classification, ranking,
matrix completion),discuss how to implement a variational approximation in each
case, and illustrate the good properties of said approximation on real
datasets.
Dual Memory Architectures for Fast Deep Learning of Stream Data via an Online-Incremental-Transfer Strategy
Authors: Sang-Woo Lee, Min-Oh Heo, Jiwon Kim, Jeonghee Kim, Byoung-Tak Zhang
Date: 2015-06-15 00:00:00
Tasks: Lifelong learning, Transfer Learning

The online learning of deep neural networks is an interesting problem of
machine learning because, for example, major IT companies want to manage the
information of the massive data uploaded on the web daily, and this technology
can contribute to the next generation of lifelong learning. We aim to train
deep models from new data that consists of new classes, distributions, and
tasks at minimal computational cost, which we call online deep learning.
Unfortunately, deep neural network learning through classical online and
incremental methods does not work well in both theory and practice. In this
paper, we introduce dual memory architectures for online incremental deep
learning. The proposed architecture consists of deep representation learners
and fast learnable shallow kernel networks, both of which synergize to track
the information of new data. During the training phase, we use various online,
incremental ensemble, and transfer learning techniques in order to achieve
lower error of the architecture. On the MNIST, CIFAR-10, and ImageNet image
recognition tasks, the proposed dual memory architectures performs much better
than the classical online and incremental ensemble algorithm, and their
accuracies are similar to that of the batch learner.
Leading Tree in DPCLUS and Its Impact on Building Hierarchies
Authors: Ji Xu, Guoyin Wang
Date: 2015-06-12 00:00:00
Tasks: Clustering

This paper reveals the tree structure as an intermediate result of clustering
by fast search and find of density peaks (DPCLUS), and explores the power of
using this tree to perform hierarchical clustering. The array used to hold the
index of the nearest higher-densitied object for each object can be transformed
into a Leading Tree (LT), in which each parent node P leads its child nodes to
join the same cluster as P itself, and the child nodes are sorted by their
gamma values in descendant order to accelerate the disconnecting of root in
each subtree. There are two major advantages with the LT: One is dramatically
reducing the running time of assigning noncenter data points to their cluster
ID, because the assigning process is turned into just disconnecting the links
from each center to its parent. The other is that the tree model for
representing clusters is more informative. Because we can check which objects
are more likely to be selected as centers in finer grained clustering, or which
objects reach to its center via less jumps. Experiment results and analysis
show the effectiveness and efficiency of the assigning process with an LT.
Scoring and Classifying with Gated Auto-encoders
Authors: Daniel Jiwoong Im, Graham W. Taylor
Date: 2014-12-20 00:00:00
Tasks: General Classification, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION, Representation Learning

Auto-encoders are perhaps the best-known non-probabilistic methods for
representation learning. They are conceptually simple and easy to train. Recent
theoretical work has shed light on their ability to capture manifold structure,
and drawn connections to density modelling. This has motivated researchers to
seek ways of auto-encoder scoring, which has furthered their use in
classification. Gated auto-encoders (GAEs) are an interesting and flexible
extension of auto-encoders which can learn transformations among different
images or pixel covariances within images. However, they have been much less
studied, theoretically or empirically. In this work, we apply a dynamical
systems view to GAEs, deriving a scoring function, and drawing connections to
Restricted Boltzmann Machines. On a set of deep learning benchmarks, we also
demonstrate their effectiveness for single and multi-label classification.
Compressing Convolutional Neural Networks
Authors: Wenlin Chen, James T. Wilson, Stephen Tyree, Kilian Q. Weinberger, Yixin Chen
Date: 2015-06-14 00:00:00

Convolutional neural networks (CNN) are increasingly used in many areas of
computer vision. They are particularly attractive because of their ability to
"absorb" great quantities of labeled data through millions of parameters.
However, as model sizes increase, so do the storage and memory requirements of
the classifiers. We present a novel network architecture, Frequency-Sensitive
Hashed Nets (FreshNets), which exploits inherent redundancy in both
convolutional layers and fully-connected layers of a deep learning model,
leading to dramatic savings in memory and storage consumption. Based on the key
observation that the weights of learned convolutional filters are typically
smooth and low-frequency, we first convert filter weights to the frequency
domain with a discrete cosine transform (DCT) and use a low-cost hash function
to randomly group frequency parameters into hash buckets. All parameters
assigned the same hash bucket share a single value learned with standard
back-propagation. To further reduce model size we allocate fewer hash buckets
to high-frequency components, which are generally less important. We evaluate
FreshNets on eight data sets, and show that it leads to drastically better
compressed performance than several relevant baselines.
A Real-time Cargo Damage Management System via a Sorting Array Triangulation Technique
Authors: Philip B. Alipour, Matteus Magnusson, Martin W. Olsson, Nooshin H. Ghasemi, Lawrence Henesey
Date: 2015-06-05 00:00:00
Tasks: Management

This report covers an intelligent decision support system (IDSS), which
handles an efficient and effective way to rapidly inspect containerized cargos
for defection. Defection is either cargo exposure to radiation, physical
damages such as holes, punctured surfaces, iron surface oxidation, etc. The
system uses a sorting array triangulation technique (SAT) and surface damage
detection (SDD) to conduct the inspection. This new technique saves time and
money on finding damaged goods during transportation such that, instead of
running $n$ inspections on $n$ containers, only 3 inspections per triangulation
or a ratio of $3:n$ is required, assuming $n > 3$ containers. The damaged stack
in the array is virtually detected contiguous to an actually-damaged cargo by
calculating nearby distances of such cargos, delivering reliable estimates for
the whole local stack population. The estimated values on damaged, somewhat
damaged and undamaged cargo stacks, are listed and profiled after being sorted
by the program, thereby submitted to the manager for a final decision. The
report describes the problem domain and the implementation of the simulator
prototype, showing how the system operates via software, hardware with/without
human agents, conducting real-time inspections and management per se.