pwc-archive/papers-with-abstracts huggingface dataset:
Finding Linear Structure in Large Datasets with Scalable Canonical Correlation Analysis
Authors: Zhuang Ma, Yichao Lu, Dean Foster
Date: 2015-06-26 00:00:00
Tasks: Stochastic Optimization

Canonical Correlation Analysis (CCA) is a widely used spectral technique for
finding correlation structures in multi-view datasets. In this paper, we tackle
the problem of large scale CCA, where classical algorithms, usually requiring
computing the product of two huge matrices and huge matrix decomposition, are
computationally and storage expensive. We recast CCA from a novel perspective
and propose a scalable and memory efficient Augmented Approximate Gradient
(AppGrad) scheme for finding top $k$ dimensional canonical subspace which only
involves large matrix multiplying a thin matrix of width $k$ and small matrix
decomposition of dimension $k\times k$. Further, AppGrad achieves optimal
storage complexity $O(k(p_1+p_2))$, compared with classical algorithms which
usually require $O(p_1^2+p_2^2)$ space to store two dense whitening matrices.
The proposed scheme naturally generalizes to stochastic optimization regime,
especially efficient for huge datasets where batch algorithms are prohibitive.
The online property of stochastic AppGrad is also well suited to the streaming
scenario, where data comes sequentially. To the best of our knowledge, it is
the first stochastic algorithm for CCA. Experiments on four real data sets are
provided to show the effectiveness of the proposed methods.
An $O(n\log(n))$ Algorithm for Projecting Onto the Ordered Weighted $\ell_1$ Norm Ball
Authors: Damek Davis
Date: 2015-05-05 00:00:00
Tasks: Clustering, regression

The ordered weighted $\ell_1$ (OWL) norm is a newly developed generalization
of the Octogonal Shrinkage and Clustering Algorithm for Regression (OSCAR)
norm. This norm has desirable statistical properties and can be used to perform
simultaneous clustering and regression. In this paper, we show how to compute
the projection of an $n$-dimensional vector onto the OWL norm ball in
$O(n\log(n))$ operations. In addition, we illustrate the performance of our
algorithm on a synthetic regression test.
Humor in Collective Discourse: Unsupervised Funniness Detection in the New Yorker Cartoon Caption Contest
Authors: Dragomir Radev, Amanda Stent, Joel Tetreault, Aasish Pappu, Aikaterini Iliakopoulou, Agustin Chanfreau, Paloma de Juan, Jordi Vallmitjana, Alejandro Jaimes, Rahul Jha, Bob Mankoff
Date: 2015-06-26 00:00:00
Proceeding: LREC 2016 5

The New Yorker publishes a weekly captionless cartoon. More than 5,000
readers submit captions for it. The editors select three of them and ask the
readers to pick the funniest one. We describe an experiment that compares a
dozen automatic methods for selecting the funniest caption. We show that
negative sentiment, human-centeredness, and lexical centrality most strongly
match the funniest captions, followed by positive sentiment. These results are
useful for understanding humor and also in the design of more engaging
conversational agents in text and multimodal (vision+text) systems. As part of
this work, a large set of cartoons and captions is being made available to the
community.
Modelling of directional data using Kent distributions
Authors: Parthan Kasarapu
Date: 2015-06-26 00:00:00

The modelling of data on a spherical surface requires the consideration of
directional probability distributions. To model asymmetrically distributed data
on a three-dimensional sphere, Kent distributions are often used. The moment
estimates of the parameters are typically used in modelling tasks involving
Kent distributions. However, these lack a rigorous statistical treatment. The
focus of the paper is to introduce a Bayesian estimation of the parameters of
the Kent distribution which has not been carried out in the literature, partly
because of its complex mathematical form. We employ the Bayesian
information-theoretic paradigm of Minimum Message Length (MML) to bridge this
gap and derive reliable estimators. The inferred parameters are subsequently
used in mixture modelling of Kent distributions. The problem of inferring the
suitable number of mixture components is also addressed using the MML
criterion. We demonstrate the superior performance of the derived MML-based
parameter estimates against the traditional estimators. We apply the MML
principle to infer mixtures of Kent distributions to model empirical data
corresponding to protein conformations. We demonstrate the effectiveness of
Kent models to act as improved descriptors of protein structural data as
compared to commonly used von Mises-Fisher distributions.
Dynamic Bayesian Ontology Languages
Authors: İsmail İlkan Ceylan, Rafael Peñaloza
Date: 2015-06-26 00:00:00

Many formalisms combining ontology languages with uncertainty, usually in the
form of probabilities, have been studied over the years. Most of these
formalisms, however, assume that the probabilistic structure of the knowledge
remains static over time. We present a general approach for extending ontology
languages to handle time-evolving uncertainty represented by a dynamic Bayesian
network. We show how reasoning in the original language and dynamic Bayesian
inferences can be exploited for effective reasoning in our framework.
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
Authors: Shiri Chechik, Edith Cohen, Haim Kaplan
Date: 2015-03-30 00:00:00

The average distance from a node to all other nodes in a graph, or from a
query point in a metric space to a set of points, is a fundamental quantity in
data analysis. The inverse of the average distance, known as the (classic)
closeness centrality of a node, is a popular importance measure in the study of
social networks. We develop novel structural insights on the sparsifiability of
the distance relation via weighted sampling. Based on that, we present highly
practical algorithms with strong statistical guarantees for fundamental
problems. We show that the average distance (and hence the centrality) for all
nodes in a graph can be estimated using $O(\epsilon^{-2})$ single-source
distance computations. For a set $V$ of $n$ points in a metric space, we show
that after preprocessing which uses $O(n)$ distance computations we can compute
a weighted sample $S\subset V$ of size $O(\epsilon^{-2})$ such that the average
distance from any query point $v$ to $V$ can be estimated from the distances
from $v$ to $S$. Finally, we show that for a set of points $V$ in a metric
space, we can estimate the average pairwise distance using $O(n+\epsilon^{-2})$
distance computations. The estimate is based on a weighted sample of
$O(\epsilon^{-2})$ pairs of points, which is computed using $O(n)$ distance
computations. Our estimates are unbiased with normalized mean square error
(NRMSE) of at most $\epsilon$. Increasing the sample size by a $O(\log n)$
factor ensures that the probability that the relative error exceeds $\epsilon$
is polynomially small.
Spectral Collaborative Representation based Classification for Hand Gestures recognition on Electromyography Signals
Authors: Ali Boyali
Date: 2015-06-26 00:00:00
Tasks: Classification, General Classification

In this study, we introduce a novel variant and application of the
Collaborative Representation based Classification in spectral domain for
recognition of the hand gestures using the raw surface Electromyography
signals. The intuitive use of spectral features are explained via circulant
matrices. The proposed Spectral Collaborative Representation based
Classification (SCRC) is able to recognize gestures with higher levels of
accuracy for a fairly rich gesture set. The worst recognition result which is
the best in the literature is obtained as 97.3\% among the four sets of the
experiments for each hand gestures. The recognition results are reported with a
substantial number of experiments and labeling computation.
ASOC: An Adaptive Parameter-free Stochastic Optimization Techinique for Continuous Variables
Authors: Jayanta Basak
Date: 2015-06-26 00:00:00
Tasks: Evolutionary Algorithms, Stochastic Optimization

Stochastic optimization is an important task in many optimization problems
where the tasks are not expressible as convex optimization problems. In the
case of non-convex optimization problems, various different stochastic
algorithms like simulated annealing, evolutionary algorithms, and tabu search
are available. Most of these algorithms require user-defined parameters
specific to the problem in order to find out the optimal solution. Moreover, in
many situations, iterative fine-tunings are required for the user-defined
parameters, and therefore these algorithms cannot adapt if the search space and
the optima changes over time. In this paper we propose an \underline{a}daptive
parameter-free \underline{s}tochastic \underline{o}ptimization technique for
\underline{c}ontinuous random variables called ASOC.
Safe Feature Pruning for Sparse High-Order Interaction Models
Authors: Kazuya Nakagawa, Shinya Suzumura, Masayuki Karasuyama, Koji Tsuda, Ichiro Takeuchi
Date: 2015-06-26 00:00:00
Tasks: Sparse Learning, Vocal Bursts Intensity Prediction

Taking into account high-order interactions among covariates is valuable in
many practical regression problems. This is, however, computationally
challenging task because the number of high-order interaction features to be
considered would be extremely large unless the number of covariates is
sufficiently small. In this paper, we propose a novel efficient algorithm for
LASSO-based sparse learning of such high-order interaction models. Our basic
strategy for reducing the number of features is to employ the idea of recently
proposed safe feature screening (SFS) rule. An SFS rule has a property that, if
a feature satisfies the rule, then the feature is guaranteed to be non-active
in the LASSO solution, meaning that it can be safely screened-out prior to the
LASSO training process. If a large number of features can be screened-out
before training the LASSO, the computational cost and the memory requirment can
be dramatically reduced. However, applying such an SFS rule to each of the
extremely large number of high-order interaction features would be
computationally infeasible. Our key idea for solving this computational issue
is to exploit the underlying tree structure among high-order interaction
features. Specifically, we introduce a pruning condition called safe feature
pruning (SFP) rule which has a property that, if the rule is satisfied in a
certain node of the tree, then all the high-order interaction features
corresponding to its descendant nodes can be guaranteed to be non-active at the
optimal solution. Our algorithm is extremely efficient, making it possible to
work, e.g., with 3rd order interactions of 10,000 original covariates, where
the number of possible high-order interaction features is greater than 10^{12}.
An Efficient Post-Selection Inference on High-Order Interaction Models
Authors: S. Suzumura, K. Nakagawa, K. Tsuda, I. Takeuchi
Date: 2015-06-26 00:00:00
Tasks: Vocal Bursts Intensity Prediction

Finding statistically significant high-order interaction features in
predictive modeling is important but challenging task. The difficulty lies in
the fact that, for a recent applications with high-dimensional covariates, the
number of possible high-order interaction features would be extremely large.
Identifying statistically significant features from such a huge pool of
candidates would be highly challenging both in computational and statistical
senses. To work with this problem, we consider a two stage algorithm where we
first select a set of high-order interaction features by marginal screening,
and then make statistical inferences on the regression model fitted only with
the selected features. Such statistical inferences are called post-selection
inference (PSI), and receiving an increasing attention in the literature. One
of the seminal recent advancements in PSI literature is the works by Lee et al.
where the authors presented an algorithmic framework for computing exact
sampling distributions in PSI. A main challenge when applying their approach to
our high-order interaction models is to cope with the fact that PSI in general
depends not only on the selected features but also on the unselected features,
making it hard to apply to our extremely high-dimensional high-order
interaction models. The goal of this paper is to overcome this difficulty by
introducing a novel efficient method for PSI. Our key idea is to exploit the
underlying tree structure among high-order interaction features, and to develop
a pruning method of the tree which enables us to quickly identify a group of
unselected features that are guaranteed to have no influence on PSI. The
experimental results indicate that the proposed method allows us to reliably
identify statistically significant high-order interaction features with
reasonable computational cost.
Java Implementation of a Parameter-less Evolutionary Portfolio
Authors: José C. Pereira, Fernando G. Lobo
Date: 2015-06-26 00:00:00
Tasks: Bayesian Optimization, Evolutionary Algorithms

The Java implementation of a portfolio of parameter-less evolutionary
algorithms is presented. The Parameter-less Evolutionary Portfolio implements a
heuristic that performs adaptive selection of parameter-less evolutionary
algorithms in accordance with performance criteria that are measured during
running time. At present time, the portfolio includes three parameter-less
evolutionary algorithms: Parameter-less Univariate Marginal Distribution
Algorithm, Parameter-less Extended Compact Genetic Algorithm, and
Parameter-less Hierarchical Bayesian Optimization Algorithm. Initial
experiments showed that the parameter-less portfolio can solve various classes
of problems without the need for any prior parameter setting technique and with
an increase in computational effort that can be considered acceptable.
A Java Implementation of Parameter-less Evolutionary Algorithms
Authors: José C. Pereira, Fernando G. Lobo
Date: 2015-06-26 00:00:00
Tasks: Bayesian Optimization, Evolutionary Algorithms

The Parameter-less Genetic Algorithm was first presented by Harik and Lobo in
1999 as an alternative to the usual trial-and-error method of finding, for each
given problem, an acceptable set-up of the parameter values of the genetic
algorithm. Since then, the same strategy has been successfully applied to
create parameter-less versions of other population-based search algorithms such
as the Extended Compact Genetic Algorithm and the Hierarchical Bayesian
Optimization Algorithm. This report describes a Java implementation,
Parameter-less Evolutionary Algorithm (P-EAJava), that integrates several
parameter-less evolutionary algorithms into a single platform. Along with a
brief description of P-EAJava, we also provide detailed instructions on how to
use it, how to implement new problems, and how to generate new parameter-less
versions of evolutionary algorithms.
  At present time, P-EAJava already includes parameter-less versions of the
Simple Genetic Algorithm, the Extended Compact Genetic Algorithm, the
Univariate Marginal Distribution Algorithm, and the Hierarchical Bayesian
Optimization Algorithm. The source and binary files of the Java implementation
of P-EAJava are available for free download at
https://github.com/JoseCPereira/2015ParameterlessEvolutionaryAlgorithmsJava.
A Java Implementation of the SGA, UMDA, ECGA, and HBOA
Authors: José C. Pereira, Fernando G. Lobo
Date: 2015-06-26 00:00:00
Tasks: Bayesian Optimization, Evolutionary Algorithms

The Simple Genetic Algorithm, the Univariate Marginal Distribution Algorithm,
the Extended Compact Genetic Algorithm, and the Hierarchical Bayesian
Optimization Algorithm are all well known Evolutionary Algorithms.
  In this report we present a Java implementation of these four algorithms with
detailed instructions on how to use each of them to solve a given set of
optimization problems. Additionally, it is explained how to implement and
integrate new problems within the provided set. The source and binary files of
the Java implementations are available for free download at
https://github.com/JoseCPereira/2015EvolutionaryAlgorithmsJava.
Online Matrix Factorization via Broyden Updates
Authors: Ömer Deniz Akyildiz
Date: 2015-06-14 00:00:00

In this paper, we propose an online algorithm to compute matrix
factorizations. Proposed algorithm updates the dictionary matrix and associated
coefficients using a single observation at each time. The algorithm performs
low-rank updates to dictionary matrix. We derive the algorithm by defining a
simple objective function to minimize whenever an observation is arrived. We
extend the algorithm further for handling missing data. We also provide a
mini-batch extension which enables to compute the matrix factorization on big
datasets. We demonstrate the efficiency of our algorithm on a real dataset and
give comparisons with well-known algorithms such as stochastic gradient matrix
factorization and nonnegative matrix factorization (NMF).
Factorized Asymptotic Bayesian Inference for Factorial Hidden Markov Models
Authors: Shaohua Li, Ryohei Fujimaki, Chunyan Miao
Date: 2015-06-26 00:00:00
Tasks: Bayesian Inference, Model Selection

Factorial hidden Markov models (FHMMs) are powerful tools of modeling
sequential data. Learning FHMMs yields a challenging simultaneous model
selection issue, i.e., selecting the number of multiple Markov chains and the
dimensionality of each chain. Our main contribution is to address this model
selection issue by extending Factorized Asymptotic Bayesian (FAB) inference to
FHMMs. First, we offer a better approximation of marginal log-likelihood than
the previous FAB inference. Our key idea is to integrate out transition
probabilities, yet still apply the Laplace approximation to emission
probabilities. Second, we prove that if there are two very similar hidden
states in an FHMM, i.e. one is redundant, then FAB will almost surely shrink
and eliminate one of them, making the model parsimonious. Experimental results
show that FAB for FHMMs significantly outperforms state-of-the-art
nonparametric Bayesian iFHMM and Variational FHMM in model selection accuracy,
with competitive held-out perplexity.
Bag-of-Features Image Indexing and Classification in Microsoft SQL Server Relational Database
Authors: Marcin Korytkowski, Rafal Scherer, Pawel Staszewski, Piotr Woldan
Date: 2015-06-26 00:00:00
Tasks: Classification, General Classification, Retrieval

This paper presents a novel relational database architecture aimed to visual
objects classification and retrieval. The framework is based on the
bag-of-features image representation model combined with the Support Vector
Machine classification and is integrated in a Microsoft SQL Server database.
Collaboratively Learning Preferences from Ordinal Data
Authors: Sewoong Oh, Kiran K. Thekumparampil, Jiaming Xu
Date: 2015-06-26 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Collaborative Ranking, Management, Recommendation Systems

In applications such as recommendation systems and revenue management, it is
important to predict preferences on items that have not been seen by a user or
predict outcomes of comparisons among those that have never been compared. A
popular discrete choice model of multinomial logit model captures the structure
of the hidden preferences with a low-rank matrix. In order to predict the
preferences, we want to learn the underlying model from noisy observations of
the low-rank matrix, collected as revealed preferences in various forms of
ordinal data. A natural approach to learn such a model is to solve a convex
relaxation of nuclear norm minimization. We present the convex relaxation
approach in two contexts of interest: collaborative ranking and bundled choice
modeling. In both cases, we show that the convex relaxation is minimax optimal.
We prove an upper bound on the resulting error with finite samples, and provide
a matching information-theoretic lower bound.
Clustering categorical data via ensembling dissimilarity matrices
Authors: Saeid Amiri, Bertrand Clarke, Jennifer Clarke
Date: 2015-06-26 00:00:00
Tasks: Clustering

We present a technique for clustering categorical data by generating many
dissimilarity matrices and averaging over them. We begin by demonstrating our
technique on low dimensional categorical data and comparing it to several other
techniques that have been proposed. Then we give conditions under which our
method should yield good results in general. Our method extends to high
dimensional categorical data of equal lengths by ensembling over many choices
of explanatory variables. In this context we compare our method with two other
methods. Finally, we extend our method to high dimensional categorical data
vectors of unequal length by using alignment techniques to equalize the
lengths. We give examples to show that our method continues to provide good
results, in particular, better in the context of genome sequences than
clusterings suggested by phylogenetic trees.
Analyzing statistical and computational tradeoffs of estimation procedures
Authors: Daniel L. Sussman, Alexander Volfovsky, Edoardo M. Airoldi
Date: 2015-06-25 00:00:00

The recent explosion in the amount and dimensionality of data has exacerbated
the need of trading off computational and statistical efficiency carefully, so
that inference is both tractable and meaningful. We propose a framework that
provides an explicit opportunity for practitioners to specify how much
statistical risk they are willing to accept for a given computational cost, and
leads to a theoretical risk-computation frontier for any given inference
problem. We illustrate the tradeoff between risk and computation and illustrate
the frontier in three distinct settings. First, we derive analytic forms for
the risk of estimating parameters in the classical setting of estimating the
mean and variance for normally distributed data and for the more general
setting of parameters of an exponential family. The second example concentrates
on computationally constrained Hodges-Lehmann estimators. We conclude with an
evaluation of risk associated with early termination of iterative matrix
inversion algorithms in the context of linear regression.
Diffusion Nets
Authors: Gal Mishne, Uri Shaham, Alexander Cloninger, Israel Cohen
Date: 2015-06-25 00:00:00
Tasks: Decoder, Outlier Detection

Non-linear manifold learning enables high-dimensional data analysis, but
requires out-of-sample-extension methods to process new data points. In this
paper, we propose a manifold learning algorithm based on deep learning to
create an encoder, which maps a high-dimensional dataset and its
low-dimensional embedding, and a decoder, which takes the embedded data back to
the high-dimensional space. Stacking the encoder and decoder together
constructs an autoencoder, which we term a diffusion net, that performs
out-of-sample-extension as well as outlier detection. We introduce new neural
net constraints for the encoder, which preserves the local geometry of the
points, and we prove rates of convergence for the encoder. Also, our approach
is efficient in both computational complexity and memory requirements, as
opposed to previous methods that require storage of all training points in both
the high-dimensional and the low-dimensional spaces to calculate the
out-of-sample-extension and the pre-image.
Deep Learning by Scattering
Authors: Stéphane Mallat, Irène Waldspurger
Date: 2013-06-24 00:00:00
Tasks: Deep Learning, General Classification

We introduce general scattering transforms as mathematical models of deep
neural networks with l2 pooling. Scattering networks iteratively apply complex
valued unitary operators, and the pooling is performed by a complex modulus. An
expected scattering defines a contractive representation of a high-dimensional
probability distribution, which preserves its mean-square norm. We show that
unsupervised learning can be casted as an optimization of the space contraction
to preserve the volume occupied by unlabeled examples, at each layer of the
network. Supervised learning and classification are performed with an averaged
scattering, which provides scattering estimations for multiple classes.