pwc-archive/papers-with-abstracts huggingface dataset:
Convex relaxations of structured matrix factorizations
Authors: Francis Bach
Date: 2013-09-12 00:00:00

We consider the factorization of a rectangular matrix $X $ into a positive
linear combination of rank-one factors of the form $u v^\top$, where $u$ and
$v$ belongs to certain sets $\mathcal{U}$ and $\mathcal{V}$, that may encode
specific structures regarding the factors, such as positivity or sparsity. In
this paper, we show that computing the optimal decomposition is equivalent to
computing a certain gauge function of $X$ and we provide a detailed analysis of
these gauge functions and their polars. Since these gauge functions are
typically hard to compute, we present semi-definite relaxations and several
algorithms that may recover approximate decompositions with approximation
guarantees. We illustrate our results with simulations on finding
decompositions with elements in $\{0,1\}$. As side contributions, we present a
detailed analysis of variational quadratic representations of norms as well as
a new iterative basis pursuit algorithm that can deal with inexact first-order
oracles.
Temporal Autoencoding Improves Generative Models of Time Series
Authors: Chris Häusler, Alex Susemihl, Martin P Nawrot, Manfred Opper
Date: 2013-09-12 00:00:00
Tasks: Denoising, Time Series, Time Series Analysis, Unsupervised Pre-training

Restricted Boltzmann Machines (RBMs) are generative models which can learn
useful representations from samples of a dataset in an unsupervised fashion.
They have been widely employed as an unsupervised pre-training method in
machine learning. RBMs have been modified to model time series in two main
ways: The Temporal RBM stacks a number of RBMs laterally and introduces
temporal dependencies between the hidden layer units; The Conditional RBM, on
the other hand, considers past samples of the dataset as a conditional bias and
learns a representation which takes these into account. Here we propose a new
training method for both the TRBM and the CRBM, which enforces the dynamic
structure of temporal datasets. We do so by treating the temporal models as
denoising autoencoders, considering past frames of the dataset as corrupted
versions of the present frame and minimizing the reconstruction error of the
present data by the model. We call this approach Temporal Autoencoding. This
leads to a significant improvement in the performance of both models in a
filling-in-frames task across a number of datasets. The error reduction for
motion capture data is 56\% for the CRBM and 80\% for the TRBM. Taking the
posterior mean prediction instead of single samples further improves the
model's estimates, decreasing the error by as much as 91\% for the CRBM on
motion capture data. We also trained the model to perform forecasting on a
large number of datasets and have found TA pretraining to consistently improve
the performance of the forecasts. Furthermore, by looking at the prediction
error across time, we can see that this improvement reflects a better
representation of the dynamics of the data as opposed to a bias towards
reconstructing the observed data on a short time scale.
Distributed Adaptive Networks: A Graphical Evolutionary Game-Theoretic View
Authors: Chunxiao Jiang, Yan Chen, K. J. Ray Liu
Date: 2012-12-06 00:00:00

Distributed adaptive filtering has been considered as an effective approach
for data processing and estimation over distributed networks. Most existing
distributed adaptive filtering algorithms focus on designing different
information diffusion rules, regardless of the nature evolutionary
characteristic of a distributed network. In this paper, we study the adaptive
network from the game theoretic perspective and formulate the distributed
adaptive filtering problem as a graphical evolutionary game. With the proposed
formulation, the nodes in the network are regarded as players and the local
combiner of estimation information from different neighbors is regarded as
different strategies selection. We show that this graphical evolutionary game
framework is very general and can unify the existing adaptive network
algorithms. Based on this framework, as examples, we further propose two
error-aware adaptive filtering algorithms. Moreover, we use graphical
evolutionary game theory to analyze the information diffusion process over the
adaptive networks and evolutionarily stable strategy of the system. Finally,
simulation results are shown to verify the effectiveness of our analysis and
proposed methods.
Sparse and Functional Principal Components Analysis
Authors: Genevera I. Allen, Michael Weylandt
Date: 2013-09-11 00:00:00
Tasks: Dimensionality Reduction, EEG, Electroencephalogram (EEG), feature selection

Regularized variants of Principal Components Analysis, especially Sparse PCA and Functional PCA, are among the most useful tools for the analysis of complex high-dimensional data. Many examples of massive data, have both sparse and functional (smooth) aspects and may benefit from a regularization scheme that can capture both forms of structure. For example, in neuro-imaging data, the brain's response to a stimulus may be restricted to a discrete region of activation (spatial sparsity), while exhibiting a smooth response within that region. We propose a unified approach to regularized PCA which can induce both sparsity and smoothness in both the row and column principal components. Our framework generalizes much of the previous literature, with sparse, functional, two-way sparse, and two-way functional PCA all being special cases of our approach. Our method permits flexible combinations of sparsity and smoothness that lead to improvements in feature selection and signal recovery, as well as more interpretable PCA factors. We demonstrate the efficacy of our method on simulated data and a neuroimaging example on EEG data.
Concentration in unbounded metric spaces and algorithmic stability
Authors: Aryeh Kontorovich
Date: 2013-09-04 00:00:00

We prove an extension of McDiarmid's inequality for metric spaces with
unbounded diameter. To this end, we introduce the notion of the {\em
subgaussian diameter}, which is a distribution-dependent refinement of the
metric diameter. Our technique provides an alternative approach to that of
Kutin and Niyogi's method of weakly difference-bounded functions, and yields
nontrivial, dimension-free results in some interesting cases where the former
does not. As an application, we give apparently the first generalization bound
in the algorithmic stability setting that holds for unbounded loss functions.
We furthermore extend our concentration inequality to strongly mixing
processes.
General Purpose Textual Sentiment Analysis and Emotion Detection Tools
Authors: Alexandre Denis, Samuel Cruz-Lara, Nadia Bellalem
Date: 2013-09-11 00:00:00
Tasks: Emotion Recognition, Opinion Mining, Sentiment Analysis

Textual sentiment analysis and emotion detection consists in retrieving the
sentiment or emotion carried by a text or document. This task can be useful in
many domains: opinion mining, prediction, feedbacks, etc. However, building a
general purpose tool for doing sentiment analysis and emotion detection raises
a number of issues, theoretical issues like the dependence to the domain or to
the language but also pratical issues like the emotion representation for
interoperability. In this paper we present our sentiment/emotion analysis
tools, the way we propose to circumvent the di culties and the applications
they are used for.
High-dimensional cluster analysis with the Masked EM Algorithm
Authors: Shabnam N. Kadir, Dan F. M. Goodman, Kenneth D. Harris
Date: 2013-09-11 00:00:00
Tasks: Spike Sorting, Vocal Bursts Intensity Prediction

Cluster analysis faces two problems in high dimensions: first, the `curse of
dimensionality' that can lead to overfitting and poor generalization
performance; and second, the sheer time taken for conventional algorithms to
process large amounts of high-dimensional data. In many applications, only a
small subset of features provide information about the cluster membership of
any one data point, however this informative feature subset may not be the same
for all data points. Here we introduce a `Masked EM' algorithm for fitting
mixture of Gaussians models in such cases. We show that the algorithm performs
close to optimally on simulated Gaussian data, and in an application of `spike
sorting' of high channel-count neuronal recordings.
Efficient Transductive Online Learning via Randomized Rounding
Authors: Nicolò Cesa-Bianchi, Ohad Shamir
Date: 2011-06-13 00:00:00
Tasks: Collaborative Filtering, Open-Ended Question Answering

Most traditional online learning algorithms are based on variants of mirror
descent or follow-the-leader. In this paper, we present an online algorithm
based on a completely different approach, tailored for transductive settings,
which combines "random playout" and randomized rounding of loss subgradients.
As an application of our approach, we present the first computationally
efficient online algorithm for collaborative filtering with trace-norm
constrained matrices. As a second application, we solve an open question
linking batch learning and transductive online learning
Enhancements of Multi-class Support Vector Machine Construction from Binary Learners using Generalization Performance
Authors: Patoomsiri Songsiri, Thimaporn Phetkaew, Boonserm Kijsirikul
Date: 2013-09-11 00:00:00

We propose several novel methods for enhancing the multi-class SVMs by
applying the generalization performance of binary classifiers as the core idea.
This concept will be applied on the existing algorithms, i.e., the Decision
Directed Acyclic Graph (DDAG), the Adaptive Directed Acyclic Graphs (ADAG), and
Max Wins. Although in the previous approaches there have been many attempts to
use some information such as the margin size and the number of support vectors
as performance estimators for binary SVMs, they may not accurately reflect the
actual performance of the binary SVMs. We show that the generalization ability
evaluated via a cross-validation mechanism is more suitable to directly extract
the actual performance of binary SVMs. Our methods are built around this
performance measure, and each of them is crafted to overcome the weakness of
the previous algorithm. The proposed methods include the Reordering Adaptive
Directed Acyclic Graph (RADAG), Strong Elimination of the classifiers (SE),
Weak Elimination of the classifiers (WE), and Voting based Candidate Filtering
(VCF). Experimental results demonstrate that our methods give significantly
higher accuracy than all of the traditional ones. Especially, WE provides
significantly superior results compared to Max Wins which is recognized as the
state of the art algorithm in terms of both accuracy and classification speed
with two times faster in average.
Robust Periocular Recognition By Fusing Sparse Representations of Color and Geometry Information
Authors: Juan C. Moreno, V. B. S. Prasath, Gil Santos, Hugo Proenca
Date: 2013-09-11 00:00:00

In this paper, we propose a re-weighted elastic net (REN) model for biometric
recognition. The new model is applied to data separated into geometric and
color spatial components. The geometric information is extracted using a fast
cartoon - texture decomposition model based on a dual formulation of the total
variation norm allowing us to carry information about the overall geometry of
images. Color components are defined using linear and nonlinear color spaces,
namely the red-green-blue (RGB), chromaticity-brightness (CB) and
hue-saturation-value (HSV). Next, according to a Bayesian fusion-scheme, sparse
representations for classification purposes are obtained. The scheme is
numerically solved using a gradient projection (GP) algorithm. In the empirical
validation of the proposed model, we have chosen the periocular region, which
is an emerging trait known for its robustness against low quality data. Our
results were obtained in the publicly available UBIRIS.v2 data set and show
consistent improvements in recognition effectiveness when compared to related
state-of-the-art techniques.
Approximate Counting CSP Solutions Using Partition Function
Authors: Junping Zhou, Weihua Su, Minghao Yin
Date: 2013-09-11 00:00:00

We propose a new approximate method for counting the number of the solutions
for constraint satisfaction problem (CSP). The method derives from the
partition function based on introducing the free energy and capturing the
relationship of probabilities of variables and constraints, which requires the
marginal probabilities. It firstly obtains the marginal probabilities using the
belief propagation, and then computes the number of solutions according to the
partition function. This allows us to directly plug the marginal probabilities
into the partition function and efficiently count the number of solutions for
CSP. The experimental results show that our method can solve both random
problems and structural problems efficiently.
A Conflict-Based Path-Generation Heuristic for Evacuation Planning
Authors: Victor Pillac, Pascal Van Henetenryck, Caroline Even
Date: 2013-09-10 00:00:00
Tasks: Management, Scheduling

Evacuation planning and scheduling is a critical aspect of disaster
management and national security applications. This paper proposes a
conflict-based path-generation approach for evacuation planning. Its key idea
is to generate evacuation routes lazily for evacuated areas and to optimize the
evacuation over these routes in a master problem. Each new path is generated to
remedy conflicts in the evacuation and adds new columns and a new row in the
master problem. The algorithm is applied to massive flood scenarios in the
Hawkesbury-Nepean river (West Sydney, Australia) which require evacuating in
the order of 70,000 persons. The proposed approach reduces the number of
variables from 4,500,000 in a Mixed Integer Programming (MIP) formulation to
30,000 in the case study. With this approach, realistic evacuations scenarios
can be solved near-optimally in real time, supporting both evacuation planning
in strategic, tactical, and operational environments.
Maximizing submodular functions using probabilistic graphical models
Authors: K. S. Sesh Kumar, Francis Bach
Date: 2013-09-10 00:00:00
Tasks: Variational Inference

We consider the problem of maximizing submodular functions; while this
problem is known to be NP-hard, several numerically efficient local search
techniques with approximation guarantees are available. In this paper, we
propose a novel convex relaxation which is based on the relationship between
submodular functions, entropies and probabilistic graphical models. In a
graphical model, the entropy of the joint distribution decomposes as a sum of
marginal entropies of subsets of variables; moreover, for any distribution, the
entropy of the closest distribution factorizing in the graphical model provides
an bound on the entropy. For directed graphical models, this last property
turns out to be a direct consequence of the submodularity of the entropy
function, and allows the generalization of graphical-model-based upper bounds
to any submodular functions. These upper bounds may then be jointly maximized
with respect to a set, while minimized with respect to the graph, leading to a
convex variational inference scheme for maximizing submodular functions, based
on outer approximations of the marginal polytope and maximum likelihood bounded
treewidth structures. By considering graphs of increasing treewidths, we may
then explore the trade-off between computational complexity and tightness of
the relaxation. We also present extensions to constrained problems and
maximizing the difference of submodular functions, which include all possible
set functions.
Preparing Korean Data for the Shared Task on Parsing Morphologically Rich Languages
Authors: Jinho D. Choi
Date: 2013-09-06 00:00:00
Tasks: Morphological Analysis

This document gives a brief description of Korean data prepared for the SPMRL
2013 shared task. A total of 27,363 sentences with 350,090 tokens are used for
the shared task. All constituent trees are collected from the KAIST Treebank
and transformed to the Penn Treebank style. All dependency trees are converted
from the transformed constituent trees using heuristics and labeling rules de-
signed specifically for the KAIST Treebank. In addition to the gold-standard
morphological analysis provided by the KAIST Treebank, two sets of automatic
morphological analysis are provided for the shared task, one is generated by
the HanNanum morphological analyzer, and the other is generated by the Sejong
morphological analyzer.
A multi-stream hmm approach to offline handwritten arabic word recognition
Authors: Ahlam Maqqor, Akram Halli, Khaled Satori
Date: 2013-09-10 00:00:00

In This paper we presented new approach for cursive Arabic text recognition
system. The objective is to propose methodology analytical offline recognition
of handwritten Arabic for rapid implementation. The first part in the writing
recognition system is the preprocessing phase is the preprocessing phase to
prepare the data was introduces and extracts a set of simple statistical
features by two methods : from a window which is sliding long that text line
the right to left and the approach VH2D (consists in projecting every character
on the abscissa, on the ordinate and the diagonals 45{\deg} and 135{\deg}) . It
then injects the resulting feature vectors to Hidden Markov Model (HMM) and
combined the two HMM by multi-stream approach.
Compressed Sensing for Block-Sparse Smooth Signals
Authors: Shahzad Gishkori, Geert Leus
Date: 2013-09-10 00:00:00
Tasks: compressed sensing

We present reconstruction algorithms for smooth signals with block sparsity
from their compressed measurements. We tackle the issue of varying group size
via group-sparse least absolute shrinkage selection operator (LASSO) as well as
via latent group LASSO regularizations. We achieve smoothness in the signal via
fusion. We develop low-complexity solvers for our proposed formulations through
the alternating direction method of multipliers.
Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
Authors: Julien Mairal
Date: 2013-06-19 00:00:00
Proceeding: NeurIPS 2013 12

Majorization-minimization algorithms consist of iteratively minimizing a
majorizing surrogate of an objective function. Because of its simplicity and
its wide applicability, this principle has been very popular in statistics and
in signal processing. In this paper, we intend to make this principle scalable.
We introduce a stochastic majorization-minimization scheme which is able to
deal with large-scale or possibly infinite data sets. When applied to convex
optimization problems under suitable assumptions, we show that it achieves an
expected convergence rate of $O(1/\sqrt{n})$ after $n$ iterations, and of
$O(1/n)$ for strongly convex functions. Equally important, our scheme almost
surely converges to stationary points for a large class of non-convex problems.
We develop several efficient algorithms based on our framework. First, we
propose a new stochastic proximal gradient method, which experimentally matches
state-of-the-art solvers for large-scale $\ell_1$-logistic regression. Second,
we develop an online DC programming algorithm for non-convex sparse estimation.
Finally, we demonstrate the effectiveness of our approach for solving
large-scale structured matrix factorization problems.
Implementation of nlization framework for verbs, pronouns and determiners with eugene
Authors: Harinder Singh, Parteek Kumar
Date: 2013-09-10 00:00:00
Tasks: Machine Translation, Translation

UNL system is designed and implemented by a nonprofit organization, UNDL
Foundation at Geneva in 1999. UNL applications are application softwares that
allow end users to accomplish natural language tasks, such as translating,
summarizing, retrieving or extracting information, etc. Two major web based
application softwares are Interactive ANalyzer (IAN), which is a natural
language analysis system. It represents natural language sentences as semantic
networks in the UNL format. Other application software is dEep-to-sUrface
GENErator (EUGENE), which is an open-source interactive NLizer. It generates
natural language sentences out of semantic networks represented in the UNL
format. In this paper, NLization framework with EUGENE is focused, while using
UNL system for accomplishing the task of machine translation. In whole
NLization process, EUGENE takes a UNL input and delivers an output in natural
language without any human intervention. It is language-independent and has to
be parametrized to the natural language input through a dictionary and a
grammar, provided as separate interpretable files. In this paper, it is
explained that how UNL input is syntactically and semantically analyzed with
the UNL-NL T-Grammar for NLization of UNL sentences involving verbs, pronouns
and determiners for Punjabi natural language.
The Linearized Bregman Method via Split Feasibility Problems: Analysis and Generalizations
Authors: Dirk A. Lorenz, Frank Schöpfer, Stephan Wenger
Date: 2013-09-09 00:00:00

The linearized Bregman method is a method to calculate sparse solutions to
systems of linear equations. We formulate this problem as a split feasibility
problem, propose an algorithmic framework based on Bregman projections and
prove a general convergence result for this framework. Convergence of the
linearized Bregman method will be obtained as a special case. Our approach also
allows for several generalizations such as other objective functions,
incremental iterations, incorporation of non-gaussian noise models or box
constraints.
Elementos de ingeniería de explotación de la información aplicados a la investigación tributaria fiscal
Authors: Rodrigo Lopez-Pablos
Date: 2013-09-10 00:00:00

By introducing elements of information mining to tax analysis, by means of
data mining software and advanced computational concepts of artificial
intelligence, the problem of tax evader's crime against public property has
been addressed. Through an empirical approach from a hypothetical case of use,
induction algorithms, neural networks and bayesian networks are applied to
determine the feasibility of its heuristic application by the tax public
administrator. Different strategies are explored to facilitate the work of
local and regional federal tax inspectors, considering their limited
computational capabilities, but equally effective for those social scientist
committed to handcrafting tax research.
  -----
  Apresentando a introdu\c{c}\~ao de elementos de explora\c{c}\~ao de
informa\c{c}\~oes para an\'alise fiscal, por meio de software de
minera\c{c}\~ao de dados e conceitos avan\c{c}ados computacionais de
intelig\^encia artificial, foi abordado o problema do crime de sonegador fiscal
contra o patrim\^onio p\'ublico. Atrav\'es de uma abordagem emp\'irica a partir
de um caso hipot\'etico de uso, os algoritmos de indu\c{c}\~ao, redes neurais e
redes bayesianas s\~ao aplicados para determinar a viabilidade de sua
aplica\c{c}\~ao heur\'istica pelo administrador p\'ublico tribut\'ario.
Diferentes estrat\'egias s\~ao exploradas para facilitar o trabalho dos
inspectores tribut\'arios federais locais e regionais, tendo em conta as suas
capacidades computacionais limitados, mas igualmente eficaz para aqueles
cientista social comprometido com a investiga\c{c}\~ao fiscal.