pwc-archive/papers-with-abstracts huggingface dataset:
Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees
Authors: Tianbao Yang, Lijun Zhang, Qihang Lin, Rong Jin
Date: 2015-07-18 00:00:00
Tasks: regression

In this paper, we study a fast approximation method for {\it large-scale
high-dimensional} sparse least-squares regression problem by exploiting the
Johnson-Lindenstrauss (JL) transforms, which embed a set of high-dimensional
vectors into a low-dimensional space. In particular, we propose to apply the JL
transforms to the data matrix and the target vector and then to solve a sparse
least-squares problem on the compressed data with a {\it slightly larger
regularization parameter}. Theoretically, we establish the optimization error
bound of the learned model for two different sparsity-inducing regularizers,
i.e., the elastic net and the $\ell_1$ norm. Compared with previous relevant
work, our analysis is {\it non-asymptotic and exhibits more insights} on the
bound, the sample complexity and the regularization. As an illustration, we
also provide an error bound of the {\it Dantzig selector} under JL transforms.
The Mondrian Process for Machine Learning
Authors: Matej Balog, Yee Whye Teh
Date: 2015-07-18 00:00:00
Tasks: BIG-bench Machine Learning, regression

This report is concerned with the Mondrian process and its applications in
machine learning. The Mondrian process is a guillotine-partition-valued
stochastic process that possesses an elegant self-consistency property. The
first part of the report uses simple concepts from applied probability to
define the Mondrian process and explore its properties.
  The Mondrian process has been used as the main building block of a clever
online random forest classification algorithm that turns out to be equivalent
to its batch counterpart. We outline a slight adaptation of this algorithm to
regression, as the remainder of the report uses regression as a case study of
how Mondrian processes can be utilized in machine learning. In particular, the
Mondrian process will be used to construct a fast approximation to the
computationally expensive kernel ridge regression problem with a Laplace
kernel.
  The complexity of random guillotine partitions generated by a Mondrian
process and hence the complexity of the resulting regression models is
controlled by a lifetime hyperparameter. It turns out that these models can be
efficiently trained and evaluated for all lifetimes in a given range at once,
without needing to retrain them from scratch for each lifetime value. This
leads to an efficient procedure for determining the right model complexity for
a dataset at hand.
  The limitation of having a single lifetime hyperparameter will motivate the
final Mondrian grid model, in which each input dimension is endowed with its
own lifetime parameter. In this model we preserve the property that its
hyperparameters can be tweaked without needing to retrain the modified model
from scratch.
Face Alignment Assisted by Head Pose Estimation
Authors: Heng Yang, Wenxuan Mou, Yichi Zhang, Ioannis Patras, Hatice Gunes, Peter Robinson
Date: 2015-07-11 00:00:00
Tasks: Face Alignment, Head Pose Estimation, Pose Estimation

In this paper we propose a supervised initialization scheme for cascaded face
alignment based on explicit head pose estimation. We first investigate the
failure cases of most state of the art face alignment approaches and observe
that these failures often share one common global property, i.e. the head pose
variation is usually large. Inspired by this, we propose a deep convolutional
network model for reliable and accurate head pose estimation. Instead of using
a mean face shape, or randomly selected shapes for cascaded face alignment
initialisation, we propose two schemes for generating initialisation: the first
one relies on projecting a mean 3D face shape (represented by 3D facial
landmarks) onto 2D image under the estimated head pose; the second one searches
nearest neighbour shapes from the training set according to head pose distance.
By doing so, the initialisation gets closer to the actual shape, which enhances
the possibility of convergence and in turn improves the face alignment
performance. We demonstrate the proposed method on the benchmark 300W dataset
and show very competitive performance in both head pose estimation and face
alignment.
A Survey of League Championship Algorithm: Prospects and Challenges
Authors: Shafii Muhammad Abdulhamid, Muhammad Shafie Abd Latiff, Syed Hamid Hussain Madni, Osho Oluwafemi
Date: 2015-07-18 00:00:00
Tasks: Articles, Survey

The League Championship Algorithm (LCA) is sport-inspired optimization
algorithm that was introduced by Ali Husseinzadeh Kashan in the year 2009. It
has since drawn enormous interest among the researchers because of its
potential efficiency in solving many optimization problems and real-world
applications. The LCA has also shown great potentials in solving
non-deterministic polynomial time (NP-complete) problems. This survey presents
a brief synopsis of the LCA literatures in peer-reviewed journals, conferences
and book chapters. These research articles are then categorized according to
indexing in the major academic databases (Web of Science, Scopus, IEEE Xplore
and the Google Scholar). The analysis was also done to explore the prospects
and the challenges of the algorithm and its acceptability among researchers.
This systematic categorization can be used as a basis for future studies.
Classification with Noisy Labels by Importance Reweighting
Authors: Tongliang Liu, DaCheng Tao
Date: 2014-11-27 00:00:00
Tasks: Classification, General Classification

In this paper, we study a classification problem in which sample labels are
randomly corrupted. In this scenario, there is an unobservable sample with
noise-free labels. However, before being observed, the true labels are
independently flipped with a probability $\rho\in[0,0.5)$, and the random label
noise can be class-conditional. Here, we address two fundamental problems
raised by this scenario. The first is how to best use the abundant surrogate
loss functions designed for the traditional classification problem when there
is label noise. We prove that any surrogate loss function can be used for
classification with noisy labels by using importance reweighting, with
consistency assurance that the label noise does not ultimately hinder the
search for the optimal classifier of the noise-free sample. The other is the
open problem of how to obtain the noise rate $\rho$. We show that the rate is
upper bounded by the conditional probability $P(y|x)$ of the noisy sample.
Consequently, the rate can be estimated, because the upper bound can be easily
reached in classification problems. Experimental results on synthetic and real
datasets confirm the efficiency of our methods.
Persistent Topology of Syntax
Authors: Alexander Port, Iulia Gheorghita, Daniel Guth, John M. Clark, Crystal Liang, Shival Dasu, Matilde Marcolli
Date: 2015-07-18 00:00:00
Tasks: Position

We study the persistent homology of the data set of syntactic parameters of
the world languages. We show that, while homology generators behave erratically
over the whole data set, non-trivial persistent homology appears when one
restricts to specific language families. Different families exhibit different
persistent homology. We focus on the cases of the Indo-European and the
Niger-Congo families, for which we compare persistent homology over different
cluster filtering values. We investigate the possible significance, in
historical linguistic terms, of the presence of persistent generators of the
first homology. In particular, we show that the persistent first homology
generator we find in the Indo-European family is not due (as one might guess)
to the Anglo-Norman bridge in the Indo-European phylogenetic network, but is
related to the position of Ancient Greek and the Hellenic branch within the
network.
Fast Approximate Bayesian Computation for Estimating Parameters in Differential Equations
Authors: Sanmitra Ghosh, Srinandan Dasmahapatra, Koushik Maharatna
Date: 2015-07-17 00:00:00
Tasks: Gaussian Processes, Model Selection, Numerical Integration, parameter estimation

Approximate Bayesian computation (ABC) using a sequential Monte Carlo method
provides a comprehensive platform for parameter estimation, model selection and
sensitivity analysis in differential equations. However, this method, like
other Monte Carlo methods, incurs a significant computational cost as it
requires explicit numerical integration of differential equations to carry out
inference. In this paper we propose a novel method for circumventing the
requirement of explicit integration by using derivatives of Gaussian processes
to smooth the observations from which parameters are estimated. We evaluate our
methods using synthetic data generated from model biological systems described
by ordinary and delay differential equations. Upon comparing the performance of
our method to existing ABC techniques, we demonstrate that it produces
comparably reliable parameter estimates at a significantly reduced execution
time.
Deep Fried Convnets
Authors: Zichao Yang, Marcin Moczulski, Misha Denil, Nando de Freitas, Alex Smola, Le Song, Ziyu Wang
Date: 2014-12-22 00:00:00
Proceeding: ICCV 2015 12
Tasks: Image Classification

The fully connected layers of a deep convolutional neural network typically
contain over 90% of the network parameters, and consume the majority of the
memory required to store the network parameters. Reducing the number of
parameters while preserving essentially the same predictive performance is
critically important for operating deep neural networks in memory constrained
environments such as GPUs or embedded devices.
  In this paper we show how kernel methods, in particular a single Fastfood
layer, can be used to replace all fully connected layers in a deep
convolutional neural network. This novel Fastfood layer is also end-to-end
trainable in conjunction with convolutional layers, allowing us to combine them
into a new architecture, named deep fried convolutional networks, which
substantially reduces the memory footprint of convolutional networks trained on
MNIST and ImageNet with no drop in predictive performance.
Type I and Type II Bayesian Methods for Sparse Signal Recovery using Scale Mixtures
Authors: Ritwik Giri, Bhaskar D. Rao
Date: 2015-07-17 00:00:00
Tasks: Vocal Bursts Type Prediction

In this paper, we propose a generalized scale mixture family of
distributions, namely the Power Exponential Scale Mixture (PESM) family, to
model the sparsity inducing priors currently in use for sparse signal recovery
(SSR). We show that the successful and popular methods such as LASSO,
Reweighted $\ell_1$ and Reweighted $\ell_2$ methods can be formulated in an
unified manner in a maximum a posteriori (MAP) or Type I Bayesian framework
using an appropriate member of the PESM family as the sparsity inducing prior.
In addition, exploiting the natural hierarchical framework induced by the PESM
family, we utilize these priors in a Type II framework and develop the
corresponding EM based estimation algorithms. Some insight into the differences
between Type I and Type II methods is provided and of particular interest in
the algorithmic development is the Type II variant of the popular and
successful reweighted $\ell_1$ method. Extensive empirical results are provided
and they show that the Type II methods exhibit better support recovery than the
corresponding Type I methods.
Massively Deep Artificial Neural Networks for Handwritten Digit Recognition
Authors: Keiron O'Shea
Date: 2015-07-17 00:00:00
Tasks: Handwritten Digit Recognition

Greedy Restrictive Boltzmann Machines yield an fairly low 0.72% error rate on
the famous MNIST database of handwritten digits. All that was required to
achieve this result was a high number of hidden layers consisting of many
neurons, and a graphics card to greatly speed up the rate of learning.
Fast Rates by Transferring from Auxiliary Hypotheses
Authors: Ilja Kuzborskij, Francesco Orabona
Date: 2014-12-04 00:00:00

In this work we consider the learning setting where, in addition to the
training set, the learner receives a collection of auxiliary hypotheses
originating from other tasks. We focus on a broad class of ERM-based linear
algorithms that can be instantiated with any non-negative smooth loss function
and any strongly convex regularizer. We establish generalization and excess
risk bounds, showing that, if the algorithm is fed with a good combination of
source hypotheses, generalization happens at the fast rate $\mathcal{O}(1/m)$
instead of the usual $\mathcal{O}(1/\sqrt{m})$. On the other hand, if the
source hypotheses combination is a misfit for the target task, we recover the
usual learning rate. As a byproduct of our study, we also prove a new bound on
the Rademacher complexity of the smooth loss class under weaker assumptions
compared to previous works.
Classification of Complex Wishart Matrices with a Diffusion-Reaction System guided by Stochastic Distances
Authors: Luis Gomez, Luis Alvarez, Luis Mazorra, Alejandro C. Frery
Date: 2015-07-17 00:00:00
Tasks: General Classification

We propose a new method for PolSAR (Polarimetric Synthetic Aperture Radar)
imagery classification based on stochastic distances in the space of random
matrices obeying complex Wishart distributions. Given a collection of
prototypes $\{Z_m\}_{m=1}^M$ and a stochastic distance $d(.,.)$, we classify
any random matrix $X$ using two criteria in an iterative setup. Firstly, we
associate $X$ to the class which minimizes the weighted stochastic distance
$w_md(X,Z_m)$, where the positive weights $w_m$ are computed to maximize the
class discrimination power. Secondly, we improve the result by embedding the
classification problem into a diffusion-reaction partial differential system
where the diffusion term smooths the patches within the image, and the reaction
term tends to move the pixel values towards the closest class prototype. In
particular, the method inherits the benefits of speckle reduction by
diffusion-like methods. Results on synthetic and real PolSAR data show the
performance of the method.
Support Vector Machine in Prediction of Building Energy Demand Using Pseudo Dynamic Approach
Authors: Subodh Paudel, Phuong H. Nguyen, Wil L. Kling, Mohamed Elmitri, Bruno Lacarrière, Olivier Le Corre
Date: 2015-07-17 00:00:00
Tasks: Dynamic Time Warping, energy management, Management

Building's energy consumption prediction is a major concern in the recent
years and many efforts have been achieved in order to improve the energy
management of buildings. In particular, the prediction of energy consumption in
building is essential for the energy operator to build an optimal operating
strategy, which could be integrated to building's energy management system
(BEMS). This paper proposes a prediction model for building energy consumption
using support vector machine (SVM). Data-driven model, for instance, SVM is
very sensitive to the selection of training data. Thus the relevant days data
selection method based on Dynamic Time Warping is used to train SVM model. In
addition, to encompass thermal inertia of building, pseudo dynamic model is
applied since it takes into account information of transition of energy
consumption effects and occupancy profile. Relevant days data selection and
whole training data model is applied to the case studies of Ecole des Mines de
Nantes, France Office building. The results showed that support vector machine
based on relevant data selection method is able to predict the energy
consumption of building with a high accuracy in compare to whole data training.
In addition, relevant data selection method is computationally cheaper (around
8 minute training time) in contrast to whole data training (around 31 hour for
weekend and 116 hour for working days) and reveals realistic control
implementation for online system as well.
Dynamic Consistency of Conditional Simple Temporal Networks via Mean Payoff Games: a Singly-Exponential Time DC-Checking
Authors: Carlo Comin, Romeo Rizzi
Date: 2015-05-04 00:00:00

Conditional Simple Temporal Network (CSTN) is a constraint-based
graph-formalism for conditional temporal planning. It offers a more flexible
formalism than the equivalent CSTP model of Tsamardinos, Vidal and Pollack,
from which it was derived mainly as a sound formalization. Three notions of
consistency arise for CSTNs and CSTPs: weak, strong, and dynamic. Dynamic
consistency is the most interesting notion, but it is also the most challenging
and it was conjectured to be hard to assess. Tsamardinos, Vidal and Pollack
gave a doubly-exponential time algorithm for deciding whether a CSTN is
dynamically-consistent and to produce, in the positive case, a dynamic
execution strategy of exponential size. In the present work we offer a proof
that deciding whether a CSTN is dynamically-consistent is coNP-hard and provide
the first singly-exponential time algorithm for this problem, also producing a
dynamic execution strategy whenever the input CSTN is dynamically-consistent.
The algorithm is based on a novel connection with Mean Payoff Games, a family
of two-player combinatorial games on graphs well known for having applications
in model-checking and formal verification. The presentation of such connection
is mediated by the Hyper Temporal Network model, a tractable generalization of
Simple Temporal Networks whose consistency checking is equivalent to
determining Mean Payoff Games. In order to analyze the algorithm we introduce a
refined notion of dynamic-consistency, named \epsilon-dynamic-consistency, and
present a sharp lower bounding analysis on the critical value of the reaction
time \hat{\varepsilon} where the CSTN transits from being, to not being,
dynamically-consistent. The proof technique introduced in this analysis of
\hat{\varepsilon} is applicable more in general when dealing with linear
difference constraints which include strict inequalities.
FRULER: Fuzzy Rule Learning through Evolution for Regression
Authors: I. Rodríguez-Fdez, M. Mucientes, A. Bugarín
Date: 2015-07-17 00:00:00
Tasks: regression

In regression problems, the use of TSK fuzzy systems is widely extended due
to the precision of the obtained models. Moreover, the use of simple linear TSK
models is a good choice in many real problems due to the easy understanding of
the relationship between the output and input variables. In this paper we
present FRULER, a new genetic fuzzy system for automatically learning accurate
and simple linguistic TSK fuzzy rule bases for regression problems. In order to
reduce the complexity of the learned models while keeping a high accuracy, the
algorithm consists of three stages: instance selection, multi-granularity fuzzy
discretization of the input variables, and the evolutionary learning of the
rule base that uses the Elastic Net regularization to obtain the consequents of
the rules. Each stage was validated using 28 real-world datasets and FRULER was
compared with three state of the art enetic fuzzy systems. Experimental results
show that FRULER achieves the most accurate and simple models compared even
with approximative approaches.
Modular Action Language ALM
Authors: Daniela Inclezan, Michael Gelfond
Date: 2015-05-19 00:00:00

The paper introduces a new modular action language, ALM, and illustrates the
methodology of its use. It is based on the approach of Gelfond and Lifschitz
(1993; 1998) in which a high-level action language is used as a front end for a
logic programming system description. The resulting logic programming
representation is used to perform various computational tasks. The methodology
based on existing action languages works well for small and even medium size
systems, but is not meant to deal with larger systems that require structuring
of knowledge. ALM is meant to remedy this problem. Structuring of knowledge in
ALM is supported by the concepts of module (a formal description of a specific
piece of knowledge packaged as a unit), module hierarchy, and library, and by
the division of a system description of ALM into two parts: theory and
structure. A theory consists of one or more modules with a common theme,
possibly organized into a module hierarchy based on a dependency relation. It
contains declarations of sorts, attributes, and properties of the domain
together with axioms describing them. Structures are used to describe the
domain's objects. These features, together with the means for defining classes
of a domain as special cases of previously defined ones, facilitate the
stepwise development, testing, and readability of a knowledge base, as well as
the creation of knowledge representation libraries. To appear in Theory and
Practice of Logic Programming (TPLP).
Tree-based Visualization and Optimization for Image Collection
Authors: Xintong Han, Chongyang Zhang, Weiyao Lin, Mingliang Xu, Bin Sheng, Tao Mei
Date: 2015-07-17 00:00:00

The visualization of an image collection is the process of displaying a
collection of images on a screen under some specific layout requirements. This
paper focuses on an important problem that is not well addressed by the
previous methods: visualizing image collections into arbitrary layout shapes
while arranging images according to user-defined semantic or visual
correlations (e.g., color or object category). To this end, we first propose a
property-based tree construction scheme to organize images of a collection into
a tree structure according to user-defined properties. In this way, images can
be adaptively placed with the desired semantic or visual correlations in the
final visualization layout. Then, we design a two-step visualization
optimization scheme to further optimize image layouts. As a result, multiple
layout effects including layout shape and image overlap ratio can be
effectively controlled to guarantee a satisfactory visualization. Finally, we
also propose a tree-transfer scheme such that visualization layouts can be
adaptively changed when users select different "images of interest". We
demonstrate the effectiveness of our proposed approach through the comparisons
with state-of-the-art visualization techniques.
Lower Bounds for Multi-armed Bandit with Non-equivalent Multiple Plays
Authors: Aleksandr Vorobev, Gleb Gusev
Date: 2015-07-17 00:00:00

We study the stochastic multi-armed bandit problem with non-equivalent
multiple plays where, at each step, an agent chooses not only a set of arms,
but also their order, which influences reward distribution. In several problem
formulations with different assumptions, we provide lower bounds for regret
with standard asymptotics $O(\log{t})$ but novel coefficients and provide
optimal algorithms, thus proving that these bounds cannot be improved.
Analysis of the South Slavic Scripts by Run-Length Features of the Image Texture
Authors: Darko Brodic, Zoran N. Milivojevic, Alessia Amelio
Date: 2015-07-17 00:00:00
Tasks: Position

The paper proposes an algorithm for the script recognition based on the
texture characteristics. The image texture is achieved by coding each letter
with the equivalent script type (number code) according to its position in the
text line. Each code is transformed into equivalent gray level pixel creating
an 1-D image. Then, the image texture is subjected to the run-length analysis.
This analysis extracts the run-length features, which are classified to make a
distinction between the scripts under consideration. In the experiment, a
custom oriented database is subject to the proposed algorithm. The database
consists of some text documents written in Cyrillic, Latin and Glagolitic
scripts. Furthermore, it is divided into training and test parts. The results
of the experiment show that 3 out of 5 run-length features can be used for
effective differentiation between the analyzed South Slavic scripts.