pwc-archive/papers-with-abstracts huggingface dataset:
Advancing Matrix Completion by Modeling Extra Structures beyond Low-Rankness
Authors: Guangcan Liu, Ping Li
Date: 2014-04-17 00:00:00
Tasks: Low-Rank Matrix Completion, Matrix Completion

A well-known method for completing low-rank matrices based on convex
optimization has been established by Cand{\`e}s and Recht. Although
theoretically complete, the method may not entirely solve the low-rank matrix
completion problem. This is because the method captures only the low-rankness
property which gives merely a rough constraint that the data points locate on
some low-dimensional subspace, but generally ignores the extra structures which
specify in more detail how the data points locate on the subspace. Whenever the
geometric distribution of the data points is not uniform, the coherence
parameters of data might be large and, accordingly, the method might fail even
if the latent matrix we want to recover is fairly low-rank. To better handle
non-uniform data, in this paper we propose a method termed Low-Rank Factor
Decomposition (LRFD), which imposes an additional restriction that the data
points must be represented as linear combinations of the bases in a dictionary
constructed or learnt in advance. We show that LRFD can well handle non-uniform
data, provided that the dictionary is configured properly: We mathematically
prove that if the dictionary itself is low-rank then LRFD is immune to the
coherence parameters which might be large on non-uniform data. This provides an
elementary principle for learning the dictionary in LRFD and, naturally, leads
to a practical algorithm for advancing matrix completion. Extensive experiments
on randomly generated matrices and motion datasets show encouraging results.
Recovery of Coherent Data via Low-Rank Dictionary Pursuit
Authors: Guangcan Liu, Ping Li
Date: 2014-04-15 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Clustering

The recently established RPCA method provides us a convenient way to restore
low-rank matrices from grossly corrupted observations. While elegant in theory
and powerful in reality, RPCA may be not an ultimate solution to the low-rank
matrix recovery problem. Indeed, its performance may not be perfect even when
data are strictly low-rank. This is because conventional RPCA ignores the
clustering structures of the data which are ubiquitous in modern applications.
As the number of cluster grows, the coherence of data keeps increasing, and
accordingly, the recovery performance of RPCA degrades. We show that the
challenges raised by coherent data (i.e., the data with high coherence) could
be alleviated by Low-Rank Representation (LRR), provided that the dictionary in
LRR is configured appropriately. More precisely, we mathematically prove that
if the dictionary itself is low-rank then LRR is immune to the coherence
parameter which increases with the underlying cluster number. This provides an
elementary principle for dealing with coherent data. Subsequently, we devise a
practical algorithm to obtain proper dictionaries in unsupervised environments.
Our extensive experiments on randomly generated matrices verify our claims.
Online Asynchronous Distributed Regression
Authors: Gérard Biau, Ryad Zenine
Date: 2014-07-16 00:00:00
Tasks: Distributed Computing, regression

Distributed computing offers a high degree of flexibility to accommodate
modern learning constraints and the ever increasing size of datasets involved
in massive data issues. Drawing inspiration from the theory of distributed
computation models developed in the context of gradient-type optimization
algorithms, we present a consensus-based asynchronous distributed approach for
nonparametric online regression and analyze some of its asymptotic properties.
Substantial numerical evidence involving up to 28 parallel processors is
provided on synthetic datasets to assess the excellent performance of our
method, both in terms of computation time and prediction accuracy.
One-Step or Two-Step Optimization and the Overfitting Phenomenon: A Case Study on Time Series Classification
Authors: Muhammad Marwan Muhammad Fuad
Date: 2014-07-16 00:00:00
Tasks: General Classification, Time Series, Time Series Analysis, Time Series Classification

For the last few decades, optimization has been developing at a fast rate.
Bio-inspired optimization algorithms are metaheuristics inspired by nature.
These algorithms have been applied to solve different problems in engineering,
economics, and other domains. Bio-inspired algorithms have also been applied in
different branches of information technology such as networking and software
engineering. Time series data mining is a field of information technology that
has its share of these applications too. In previous works we showed how
bio-inspired algorithms such as the genetic algorithms and differential
evolution can be used to find the locations of the breakpoints used in the
symbolic aggregate approximation of time series representation, and in another
work we showed how we can utilize the particle swarm optimization, one of the
famous bio-inspired algorithms, to set weights to the different segments in the
symbolic aggregate approximation representation. In this paper we present, in
two different approaches, a new meta optimization process that produces optimal
locations of the breakpoints in addition to optimal weights of the segments.
The experiments of time series classification task that we conducted show an
interesting example of how the overfitting phenomenon, a frequently encountered
problem in data mining which happens when the model overfits the training set,
can interfere in the optimization process and hide the superior performance of
an optimization algorithm.
Data Assimilation by Artificial Neural Networks for an Atmospheric General Circulation Model: Conventional Observation
Authors: Rosangela S. Cintra, Haroldo F. de Campos Velho
Date: 2014-07-16 00:00:00
Tasks: CPU

This paper presents an approach for employing artificial neural networks (NN)
to emulate an ensemble Kalman filter (EnKF) as a method of data assimilation.
The assimilation methods are tested in the Simplified Parameterizations
PrimitivE-Equation Dynamics (SPEEDY) model, an atmospheric general circulation
model (AGCM), using synthetic observational data simulating localization of
balloon soundings. For the data assimilation scheme, the supervised NN, the
multilayer perceptrons (MLP-NN), is applied. The MLP-NN are able to emulate the
analysis from the local ensemble transform Kalman filter (LETKF). After the
training process, the method using the MLP-NN is seen as a function of data
assimilation. The NN were trained with data from first three months of 1982,
1983, and 1984. A hind-casting experiment for the 1985 data assimilation cycle
using MLP-NN were performed with synthetic observations for January 1985. The
numerical results demonstrate the effectiveness of the NN technique for
atmospheric data assimilation. The results of the NN analyses are very close to
the results from the LETKF analyses, the differences of the monthly average of
absolute temperature analyses is of order 0.02. The simulations show that the
major advantage of using the MLP-NN is better computational performance, since
the analyses have similar quality. The CPU-time cycle assimilation with MLP-NN
is 90 times faster than cycle assimilation with LETKF for the numerical
experiment.
Finding sparse solutions of systems of polynomial equations via group-sparsity optimization
Authors: Fabien Lauer, Henrik Ohlsson
Date: 2013-11-22 00:00:00

The paper deals with the problem of finding sparse solutions to systems of
polynomial equations possibly perturbed by noise. In particular, we show how
these solutions can be recovered from group-sparse solutions of a derived
system of linear equations. Then, two approaches are considered to find these
group-sparse solutions. The first one is based on a convex relaxation resulting
in a second-order cone programming formulation which can benefit from efficient
reweighting techniques for sparsity enhancement. For this approach, sufficient
conditions for the exact recovery of the sparsest solution to the polynomial
system are derived in the noiseless setting, while stable recovery results are
obtained for the noisy case. Though lacking a similar analysis, the second
approach provides a more computationally efficient algorithm based on a greedy
strategy adding the groups one-by-one. With respect to previous work, the
proposed methods recover the sparsest solution in a very short computing time
while remaining at least as accurate in terms of the probability of success.
This probability is empirically analyzed to emphasize the relationship between
the ability of the methods to solve the polynomial system and the sparsity of
the solution.
Optimal CUR Matrix Decompositions
Authors: Christos Boutsidis, David P. Woodruff
Date: 2014-05-30 00:00:00

The CUR decomposition of an $m \times n$ matrix $A$ finds an $m \times c$
matrix $C$ with a subset of $c < n$ columns of $A,$ together with an $r \times
n$ matrix $R$ with a subset of $r < m$ rows of $A,$ as well as a $c \times r$
low-rank matrix $U$ such that the matrix $C U R$ approximates the matrix $A,$
that is, $ || A - CUR ||_F^2 \le (1+\epsilon) || A - A_k||_F^2$, where
$||.||_F$ denotes the Frobenius norm and $A_k$ is the best $m \times n$ matrix
of rank $k$ constructed via the SVD. We present input-sparsity-time and
deterministic algorithms for constructing such a CUR decomposition where
$c=O(k/\epsilon)$ and $r=O(k/\epsilon)$ and rank$(U) = k$. Up to constant
factors, our algorithms are simultaneously optimal in $c, r,$ and rank$(U)$.
Argument Ranking with Categoriser Function
Authors: Fuan Pu, Jian Luo, Yulai Zhang, Guiming Luo
Date: 2014-06-16 00:00:00

Recently, ranking-based semantics is proposed to rank-order arguments from
the most acceptable to the weakest one(s), which provides a graded assessment
to arguments. In general, the ranking on arguments is derived from the strength
values of the arguments. Categoriser function is a common approach that assigns
a strength value to a tree of arguments. When it encounters an argument system
with cycles, then the categoriser strength is the solution of the non-linear
equations. However, there is no detail about the existence and uniqueness of
the solution, and how to find the solution (if exists). In this paper, we will
cope with these issues via fixed point technique. In addition, we define the
categoriser-based ranking semantics in light of categoriser strength, and
investigate some general properties of it. Finally, the semantics is shown to
satisfy some of the axioms that a ranking-based semantics should satisfy.
Collaborative Filtering Ensemble for Personalized Name Recommendation
Authors: Bernat Coma-Puig, Ernesto Diaz-Aviles, Wolfgang Nejdl
Date: 2014-07-16 00:00:00
Tasks: Collaborative Filtering, Recommendation Systems

Out of thousands of names to choose from, picking the right one for your
child is a daunting task. In this work, our objective is to help parents making
an informed decision while choosing a name for their baby. We follow a
recommender system approach and combine, in an ensemble, the individual
rankings produced by simple collaborative filtering algorithms in order to
produce a personalized list of names that meets the individual parents' taste.
Our experiments were conducted using real-world data collected from the query
logs of 'nameling' (nameling.net), an online portal for searching and exploring
names, which corresponds to the dataset released in the context of the ECML
PKDD Discover Challenge 2013. Our approach is intuitive, easy to implement, and
features fast training and prediction steps.
A Plausibility Semantics for Abstract Argumentation Frameworks
Authors: Emil Weydert
Date: 2014-07-16 00:00:00
Tasks: Abstract Argumentation

We propose and investigate a simple ranking-measure-based extension semantics
for abstract argumentation frameworks based on their generic instantiation by
default knowledge bases and the ranking construction semantics for default
reasoning. In this context, we consider the path from structured to logical to
shallow semantic instantiations. The resulting well-justified JZ-extension
semantics diverges from more traditional approaches.
Mobile Camera Array Calibration for Light Field Acquisition
Authors: Yichao Xu, Kazuki Maeno, Hajime Nagahara, Rin-ichiro Taniguchi
Date: 2014-07-16 00:00:00
Tasks: Camera Calibration, global-optimization

The light field camera is useful for computer graphics and vision
applications. Calibration is an essential step for these applications. After
calibration, we can rectify the captured image by using the calibrated camera
parameters. However, the large camera array calibration method, which assumes
that all cameras are on the same plane, ignores the orientation and intrinsic
parameters. The multi-camera calibration technique usually assumes that the
working volume and viewpoints are fixed. In this paper, we describe a
calibration algorithm suitable for a mobile camera array based light field
acquisition system. The algorithm performs in Zhang's style by moving a
checkerboard, and computes the initial parameters in closed form. Global
optimization is then applied to refine all the parameters simultaneously. Our
implementation is rather flexible in that users can assign the number of
viewpoints and refinement of intrinsic parameters is optional. Experiments on
both simulated data and real data acquired by a commercial product show that
our method yields good results. Digital refocusing application shows the
calibrated light field can well focus to the target object we desired.
Allocation in Practice
Authors: Toby Walsh
Date: 2014-07-11 00:00:00

How do we allocate scarcere sources? How do we fairly allocate costs? These
are two pressing challenges facing society today. I discuss two recent projects
at NICTA concerning resource and cost allocation. In the first, we have been
working with FoodBank Local, a social startup working in collaboration with
food bank charities around the world to optimise the logistics of collecting
and distributing donated food. Before we can distribute this food, we must
decide how to allocate it to different charities and food kitchens. This gives
rise to a fair division problem with several new dimensions, rarely considered
in the literature. In the second, we have been looking at cost allocation
within the distribution network of a large multinational company. This also has
several new dimensions rarely considered in the literature.
Automatic discovery of cell types and microcircuitry from neural connectomics
Authors: Eric Jonas, Konrad Kording
Date: 2014-07-15 00:00:00

Neural connectomics has begun producing massive amounts of data,
necessitating new analysis methods to discover the biological and computational
structure. It has long been assumed that discovering neuron types and their
relation to microcircuitry is crucial to understanding neural function. Here we
developed a nonparametric Bayesian technique that identifies neuron types and
microcircuitry patterns in connectomics data. It combines the information
traditionally used by biologists, including connectivity, cell body location
and the spatial distribution of synapses, in a principled and
probabilistically-coherent manner. We show that the approach recovers known
neuron types in the retina and enables predictions of connectivity, better than
simpler algorithms. It also can reveal interesting structure in the nervous
system of C. elegans, and automatically discovers the structure of a
microprocessor. Our approach extracts structural meaning from connectomics,
enabling new approaches of automatically deriving anatomical insights from
these emerging datasets.
Fast matrix completion without the condition number
Authors: Moritz Hardt, Mary Wootters
Date: 2014-07-15 00:00:00
Tasks: Matrix Completion

We give the first algorithm for Matrix Completion whose running time and
sample complexity is polynomial in the rank of the unknown target matrix,
linear in the dimension of the matrix, and logarithmic in the condition number
of the matrix. To the best of our knowledge, all previous algorithms either
incurred a quadratic dependence on the condition number of the unknown matrix
or a quadratic dependence on the dimension of the matrix in the running time.
Our algorithm is based on a novel extension of Alternating Minimization which
we show has theoretical guarantees under standard assumptions even in the
presence of noise.
Global disease monitoring and forecasting with Wikipedia
Authors: Nicholas Generous, Geoffrey Fairchild, Alina Deshpande, Sara Y. Del Valle, Reid Priedhorsky
Date: 2014-05-14 00:00:00

Infectious disease is a leading threat to public health, economic stability,
and other key social structures. Efforts to mitigate these impacts depend on
accurate and timely monitoring to measure the risk and progress of disease.
Traditional, biologically-focused monitoring techniques are accurate but costly
and slow; in response, new techniques based on social internet data such as
social media and search queries are emerging. These efforts are promising, but
important challenges in the areas of scientific peer review, breadth of
diseases and countries, and forecasting hamper their operational usefulness.
  We examine a freely available, open data source for this use: access logs
from the online encyclopedia Wikipedia. Using linear models, language as a
proxy for location, and a systematic yet simple article selection procedure, we
tested 14 location-disease combinations and demonstrate that these data
feasibly support an approach that overcomes these challenges. Specifically, our
proof-of-concept yields models with $r^2$ up to 0.92, forecasting value up to
the 28 days tested, and several pairs of models similar enough to suggest that
transferring models from one location to another without re-training is
feasible.
  Based on these preliminary results, we close with a research agenda designed
to overcome these challenges and produce a disease monitoring and forecasting
system that is significantly more effective, robust, and globally comprehensive
than the current state of the art.
Identification of Probabilities of Languages
Authors: Paul M. B. Vitanyi, Nick Chater
Date: 2012-08-24 00:00:00

We consider the problem of inferring the probability distribution associated
with a language, given data consisting of an infinite sequence of elements of
the languge. We do this under two assumptions on the algorithms concerned: (i)
like a real-life algorothm it has round-off errors, and (ii) it has no
round-off errors. Assuming (i) we (a) consider a probability mass function of
the elements of the language if the data are drawn independent identically
distributed (i.i.d.), provided the probability mass function is computable and
has a finite expectation. We give an effective procedure to almost surely
identify in the limit the target probability mass function using the Strong Law
of Large Numbers. Second (b) we treat the case of possibly incomputable
probabilistic mass functions in the above setting. In this case we can only
pointswize converge to the target probability mass function almost surely.
Third (c) we consider the case where the data are dependent assuming they are
typical for at least one computable measure and the language is finite. There
is an effective procedure to identify by infinite recurrence a nonempty subset
of the computable measures according to which the data is typical. Here we use
the theory of Kolmogorov complexity. Assuming (ii) we obtain the weaker result
for (a) that the target distribution is identified by infinite recurrence
almost surely; (b) stays the same as under assumption (i). We consider the
associated predictions.
An iterative approach to Hough transform without re-voting
Authors: Giorgio Ricca, Mauro C. Beltrametti, Anna Maria Massone
Date: 2014-07-15 00:00:00

Many bone shapes in the human skeleton are characterized by profiles that can
be associated to equations of algebraic curves. Fixing the parameters in the
curve equation, by means of a classical pattern recognition procedure like the
Hough transform technique, it is then possible to associate an equation to a
specific bone profile. However, most skeleton districts are more accurately
described by piecewise defined curves. This paper utilizes an iterative
approach of the Hough transform without re-voting, to provide an efficient
procedure for describing the profile of a bone in the human skeleton as a
collection of different but continuously attached curves.
Analysis of purely random forests bias
Authors: Sylvain Arlot, Robin Genuer
Date: 2014-07-15 00:00:00
Tasks: regression

Random forests are a very effective and commonly used statistical method, but
their full theoretical analysis is still an open problem. As a first step,
simplified models such as purely random forests have been introduced, in order
to shed light on the good performance of random forests. In this paper, we
study the approximation error (the bias) of some purely random forest models in
a regression framework, focusing in particular on the influence of the number
of trees in the forest. Under some regularity assumptions on the regression
function, we show that the bias of an infinite forest decreases at a faster
rate (with respect to the size of each tree) than a single tree. As a
consequence, infinite forests attain a strictly better risk rate (with respect
to the sample size) than single trees. Furthermore, our results allow to derive
a minimum number of trees sufficient to reach the same rate as an infinite
forest. As a by-product of our analysis, we also show a link between the bias
of purely random forests and the bias of some kernel estimators.
Complex Support Vector Machines for Regression and Quaternary Classification
Authors: Pantelis Bouboulis, Sergios Theodoridis, Charalampos Mavroforakis, Leoni Dalla
Date: 2013-03-09 00:00:00
Tasks: Classification, General Classification, regression

The paper presents a new framework for complex Support Vector Regression as
well as Support Vector Machines for quaternary classification. The method
exploits the notion of widely linear estimation to model the input-out relation
for complex-valued data and considers two cases: a) the complex data are split
into their real and imaginary parts and a typical real kernel is employed to
map the complex data to a complexified feature space and b) a pure complex
kernel is used to directly map the data to the induced complex feature space.
The recently developed Wirtinger's calculus on complex reproducing kernel
Hilbert spaces (RKHS) is employed in order to compute the Lagrangian and derive
the dual optimization problem. As one of our major results, we prove that any
complex SVM/SVR task is equivalent with solving two real SVM/SVR tasks
exploiting a specific real kernel which is generated by the chosen complex
kernel. In particular, the case of pure complex kernels leads to the generation
of new kernels, which have not been considered before. In the classification
case, the proposed framework inherently splits the complex space into four
parts. This leads naturally in solving the four class-task (quaternary
classification), instead of the typical two classes of the real SVM. In turn,
this rationale can be used in a multiclass problem as a split-class scenario
based on four classes, as opposed to the one-versus-all method; this can lead
to significant computational savings. Experiments demonstrate the effectiveness
of the proposed framework for regression and classification tasks that involve
complex data.