pwc-archive/papers-with-abstracts huggingface dataset:
Generic construction of scale-invariantly coarse grained memory
Authors: Karthik H. Shankar
Date: 2014-06-12 00:00:00
Tasks: Future prediction

Encoding temporal information from the recent past as spatially distributed
activations is essential in order for the entire recent past to be
simultaneously accessible. Any biological or synthetic agent that relies on the
past to predict/plan the future, would be endowed with such a spatially
distributed temporal memory. Simplistically, we would expect that resource
limitations would demand the memory system to store only the most useful
information for future prediction. For natural signals in real world which show
scale free temporal fluctuations, the predictive information encoded in memory
is maximal if the past information is scale invariantly coarse grained. Here we
examine the general mechanism to construct a scale invariantly coarse grained
memory system. Remarkably, the generic construction is equivalent to encoding
the linear combinations of Laplace transform of the past information and their
approximated inverses. This reveals a fundamental construction constraint on
memory networks that attempt to maximize predictive information storage
relevant to the natural world.
An Experimental Analysis of the Echo State Network Initialization Using the Particle Swarm Optimization
Authors: Sebastián Basterrech, Enrique Alba, Václav Snášel
Date: 2015-01-02 00:00:00

This article introduces a robust hybrid method for solving supervised
learning tasks, which uses the Echo State Network (ESN) model and the Particle
Swarm Optimization (PSO) algorithm. An ESN is a Recurrent Neural Network with
the hidden-hidden weights fixed in the learning process. The recurrent part of
the network stores the input information in internal states of the network.
Another structure forms a free-memory method used as supervised learning tool.
The setting procedure for initializing the recurrent structure of the ESN model
can impact on the model performance. On the other hand, the PSO has been shown
to be a successful technique for finding optimal points in complex spaces.
Here, we present an approach to use the PSO for finding some initial
hidden-hidden weights of the ESN model. We present empirical results that
compare the canonical ESN model with this hybrid method on a wide range of
benchmark problems.
Efficiently Discovering Frequent Motifs in Large-scale Sensor Data
Authors: Puneet Agarwal, Gautam Shroff, Sarmimala Saikia, Zaigham Khan
Date: 2015-01-02 00:00:00
Tasks: Anomaly Detection, Clustering, Time Series, Time Series Analysis

While analyzing vehicular sensor data, we found that frequently occurring
waveforms could serve as features for further analysis, such as rule mining,
classification, and anomaly detection. The discovery of waveform patterns, also
known as time-series motifs, has been studied extensively; however, available
techniques for discovering frequently occurring time-series motifs were found
lacking in either efficiency or quality: Standard subsequence clustering
results in poor quality, to the extent that it has even been termed
'meaningless'. Variants of hierarchical clustering using techniques for
efficient discovery of 'exact pair motifs' find high-quality frequent motifs,
but at the cost of high computational complexity, making such techniques
unusable for our voluminous vehicular sensor data. We show that good quality
frequent motifs can be discovered using bounded spherical clustering of
time-series subsequences, which we refer to as COIN clustering, with near
linear complexity in time-series size. COIN clustering addresses many of the
challenges that previously led to subsequence clustering being viewed as
meaningless. We describe an end-to-end motif-discovery procedure using a
sequence of pre and post-processing techniques that remove trivial-matches and
shifted-motifs, which also plagued previous subsequence-clustering approaches.
We demonstrate that our technique efficiently discovers frequent motifs in
voluminous vehicular sensor data as well as in publicly available data sets.
Passing Expectation Propagation Messages with Kernel Methods
Authors: Wittawat Jitkrittum, Arthur Gretton, Nicolas Heess
Date: 2015-01-02 00:00:00

We propose to learn a kernel-based message operator which takes as input all
expectation propagation (EP) incoming messages to a factor node and produces an
outgoing message. In ordinary EP, computing an outgoing message involves
estimating a multivariate integral which may not have an analytic expression.
Learning such an operator allows one to bypass the expensive computation of the
integral during inference by directly mapping all incoming messages into an
outgoing message. The operator can be learned from training data (examples of
input and output messages) which allows automated inference to be made on any
kind of factor that can be sampled.
Stochastic Optimization with Importance Sampling
Authors: Peilin Zhao, Tong Zhang
Date: 2014-01-13 00:00:00
Tasks: Stochastic Optimization

Uniform sampling of training data has been commonly used in traditional
stochastic optimization algorithms such as Proximal Stochastic Gradient Descent
(prox-SGD) and Proximal Stochastic Dual Coordinate Ascent (prox-SDCA). Although
uniform sampling can guarantee that the sampled stochastic quantity is an
unbiased estimate of the corresponding true quantity, the resulting estimator
may have a rather high variance, which negatively affects the convergence of
the underlying optimization procedure. In this paper we study stochastic
optimization with importance sampling, which improves the convergence rate by
reducing the stochastic variance. Specifically, we study prox-SGD (actually,
stochastic mirror descent) with importance sampling and prox-SDCA with
importance sampling. For prox-SGD, instead of adopting uniform sampling
throughout the training process, the proposed algorithm employs importance
sampling to minimize the variance of the stochastic gradient. For prox-SDCA,
the proposed importance sampling scheme aims to achieve higher expected dual
value at each dual coordinate ascent step. We provide extensive theoretical
analysis to show that the convergence rates with the proposed importance
sampling methods can be significantly improved under suitable conditions both
for prox-SGD and for prox-SDCA. Experiments are provided to verify the
theoretical analysis.
Comprehend DeepWalk as Matrix Factorization
Authors: Cheng Yang, Zhiyuan Liu
Date: 2015-01-02 00:00:00

Word2vec, as an efficient tool for learning vector representation of words
has shown its effectiveness in many natural language processing tasks. Mikolov
et al. issued Skip-Gram and Negative Sampling model for developing this
toolbox. Perozzi et al. introduced the Skip-Gram model into the study of social
network for the first time, and designed an algorithm named DeepWalk for
learning node embedding on a graph. We prove that the DeepWalk algorithm is
actually factoring a matrix M where each entry M_{ij} is logarithm of the
average probability that node i randomly walks to node j in fix steps.
Multi-Access Communications with Energy Harvesting: A Multi-Armed Bandit Model and the Optimality of the Myopic Policy
Authors: Pol Blasco, Deniz Gunduz
Date: 2015-01-01 00:00:00
Tasks: Scheduling

A multi-access wireless network with N transmitting nodes, each equipped with
an energy harvesting (EH) device and a rechargeable battery of finite capacity,
is studied. At each time slot (TS) a node is operative with a certain
probability, which may depend on the availability of data, or the state of its
channel. The energy arrival process at each node is modelled as an independent
two-state Markov process, such that, at each TS, a node either harvests one
unit of energy, or none. At each TS a subset of the nodes is scheduled by the
access point (AP). The scheduling policy that maximises the total throughput is
studied assuming that the AP does not know the states of either the EH
processes or the batteries. The problem is identified as a restless multiarmed
bandit (RMAB) problem, and an upper bound on the optimal scheduling policy is
found. Under certain assumptions regarding the EH processes and the battery
sizes, the optimality of the myopic policy (MP) is proven. For the general
case, the performance of MP is compared numerically to the upper bound.
SIRF: Simultaneous Image Registration and Fusion in A Unified Framework
Authors: Chen Chen, Yeqing Li, Wei Liu, Junzhou Huang
Date: 2014-11-18 00:00:00
Tasks: Image Registration

In this paper, we propose a novel method for image fusion with a
high-resolution panchromatic image and a low-resolution multispectral image at
the same geographical location. The fusion is formulated as a convex
optimization problem which minimizes a linear combination of a least-squares
fitting term and a dynamic gradient sparsity regularizer. The former is to
preserve accurate spectral information of the multispectral image, while the
latter is to keep sharp edges of the high-resolution panchromatic image. We
further propose to simultaneously register the two images during the fusing
process, which is naturally achieved by virtue of the dynamic gradient sparsity
property. An efficient algorithm is then devised to solve the optimization
problem, accomplishing a linear computational complexity in the size of the
output image in each iteration. We compare our method against seven
state-of-the-art image fusion methods on multispectral image datasets from four
satellites. Extensive experimental results demonstrate that the proposed method
substantially outperforms the others in terms of both spatial and spectral
qualities. We also show that our method can provide high-quality products from
coarsely registered real-world datasets. Finally, a MATLAB implementation is
provided to facilitate future research.
A robust sub-linear time R-FFAST algorithm for computing a sparse DFT
Authors: Sameer Pawar, Kannan Ramchandran
Date: 2015-01-01 00:00:00

The Fast Fourier Transform (FFT) is the most efficiently known way to compute
the Discrete Fourier Transform (DFT) of an arbitrary n-length signal, and has a
computational complexity of O(n log n). If the DFT X of the signal x has only k
non-zero coefficients (where k < n), can we do better? In [1], we addressed
this question and presented a novel FFAST (Fast Fourier Aliasing-based Sparse
Transform) algorithm that cleverly induces sparse graph alias codes in the DFT
domain, via a Chinese-Remainder-Theorem (CRT)-guided sub-sampling operation of
the time-domain samples. The resulting sparse graph alias codes are then
exploited to devise a fast and iterative onion-peeling style decoder that
computes an n length DFT of a signal using only O(k) time-domain samples and
O(klog k) computations. The FFAST algorithm is applicable whenever k is
sub-linear in n (i.e. k = o(n)), but is obviously most attractive when k is
much smaller than n.
  In this paper, we adapt the FFAST framework of [1] to the case where the
time-domain samples are corrupted by a white Gaussian noise. In particular, we
show that the extended noise robust algorithm R-FFAST computes an n-length
k-sparse DFT X using O(klog ^3 n) noise-corrupted time-domain samples, in
O(klog^4n) computations, i.e., sub-linear time complexity. While our
theoretical results are for signals with a uniformly random support of the
non-zero DFT coefficients and additive white Gaussian noise, we provide
simulation results which demonstrates that the R-FFAST algorithm performs well
even for signals like MR images, that have an approximately sparse Fourier
spectrum with a non-uniform support for the dominant DFT coefficients.
Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
Authors: Po-Ling Loh, Martin J. Wainwright
Date: 2013-05-10 00:00:00
Proceeding: NeurIPS 2013 12

We provide novel theoretical results regarding local optima of regularized
$M$-estimators, allowing for nonconvexity in both loss and penalty functions.
Under restricted strong convexity on the loss and suitable regularity
conditions on the penalty, we prove that \emph{any stationary point} of the
composite objective function will lie within statistical precision of the
underlying parameter vector. Our theory covers many nonconvex objective
functions of interest, including the corrected Lasso for errors-in-variables
linear models; regression for generalized linear models with nonconvex
penalties such as SCAD, MCP, and capped-$\ell_1$; and high-dimensional
graphical model estimation. We quantify statistical accuracy by providing
bounds on the $\ell_1$-, $\ell_2$-, and prediction error between stationary
points and the population-level optimum. We also propose a simple modification
of composite gradient descent that may be used to obtain a near-global optimum
within statistical precision $\epsilon$ in $\log(1/\epsilon)$ steps, which is
the fastest possible rate of any first-order method. We provide simulation
studies illustrating the sharpness of our theoretical results.
Statistical consistency and asymptotic normality for high-dimensional robust M-estimators
Authors: Po-Ling Loh
Date: 2015-01-01 00:00:00
Tasks: regression, Vocal Bursts Intensity Prediction

We study theoretical properties of regularized robust M-estimators,
applicable when data are drawn from a sparse high-dimensional linear model and
contaminated by heavy-tailed distributions and/or outliers in the additive
errors and covariates. We first establish a form of local statistical
consistency for the penalized regression estimators under fairly mild
conditions on the error distribution: When the derivative of the loss function
is bounded and satisfies a local restricted curvature condition, all stationary
points within a constant radius of the true regression vector converge at the
minimax rate enjoyed by the Lasso with sub-Gaussian errors. When an appropriate
nonconvex regularizer is used in place of an l_1-penalty, we show that such
stationary points are in fact unique and equal to the local oracle solution
with the correct support---hence, results on asymptotic normality in the
low-dimensional case carry over immediately to the high-dimensional setting.
This has important implications for the efficiency of regularized nonconvex
M-estimators when the errors are heavy-tailed. Our analysis of the local
curvature of the loss function also has useful consequences for optimization
when the robust regression function and/or regularizer is nonconvex and the
objective function possesses stationary points outside the local region. We
show that as long as a composite gradient descent algorithm is initialized
within a constant radius of the true regression vector, successive iterates
will converge at a linear rate to a stationary point within the local region.
Furthermore, the global optimum of a convex regularized robust regression
function may be used to obtain a suitable initialization. The result is a novel
two-step procedure that uses a convex M-estimator to achieve consistency and a
nonconvex M-estimator to increase efficiency.
QANUS: An Open-source Question-Answering Platform
Authors: Jun-Ping Ng, Min-Yen Kan
Date: 2015-01-01 00:00:00
Tasks: Question Answering

In this paper, we motivate the need for a publicly available, generic
software framework for question-answering (QA) systems. We present an
open-source QA framework QANUS which researchers can leverage on to build new
QA systems easily and rapidly. The framework implements much of the code that
will otherwise have been repeated across different QA systems. To demonstrate
the utility and practicality of the framework, we further present a fully
functioning factoid QA system QA-SYS built on top of QANUS.
Sequence Modeling using Gated Recurrent Neural Networks
Authors: Mohammad Pezeshki
Date: 2015-01-01 00:00:00
Tasks: Machine Translation, Speech Synthesis, Translation

In this paper, we have used Recurrent Neural Networks to capture and model
human motion data and generate motions by prediction of the next immediate data
point at each time-step. Our RNN is armed with recently proposed Gated
Recurrent Units which has shown promising results in some sequence modeling
problems such as Machine Translation and Speech Synthesis. We demonstrate that
this model is able to capture long-term dependencies in data and generate
realistic motions.
Consistent Classification Algorithms for Multi-class Non-Decomposable Performance Metrics
Authors: Harish G. Ramaswamy, Harikrishna Narasimhan, Shivani Agarwal
Date: 2015-01-01 00:00:00
Tasks: Classification, General Classification, Information Retrieval, Retrieval

We study consistency of learning algorithms for a multi-class performance
metric that is a non-decomposable function of the confusion matrix of a
classifier and cannot be expressed as a sum of losses on individual data
points; examples of such performance metrics include the macro F-measure
popular in information retrieval and the G-mean metric used in class-imbalanced
problems. While there has been much work in recent years in understanding the
consistency properties of learning algorithms for `binary' non-decomposable
metrics, little is known either about the form of the optimal classifier for a
general multi-class non-decomposable metric, or about how these learning
algorithms generalize to the multi-class case. In this paper, we provide a
unified framework for analysing a multi-class non-decomposable performance
metric, where the problem of finding the optimal classifier for the performance
metric is viewed as an optimization problem over the space of all confusion
matrices achievable under the given distribution. Using this framework, we show
that (under a continuous distribution) the optimal classifier for a multi-class
performance metric can be obtained as the solution of a cost-sensitive
classification problem, thus generalizing several previous results on specific
binary non-decomposable metrics. We then design a consistent learning algorithm
for concave multi-class performance metrics that proceeds via a sequence of
cost-sensitive classification problems, and can be seen as applying the
conditional gradient (CG) optimization method over the space of feasible
confusion matrices. To our knowledge, this is the first efficient learning
algorithm (whose running time is polynomial in the number of classes) that is
consistent for a large family of multi-class non-decomposable metrics. Our
consistency proof uses a novel technique based on the convergence analysis of
the CG method.
Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss
Authors: Yuchen Zhang, Lin Xiao
Date: 2015-01-01 00:00:00
Tasks: Binary Classification, Distributed Computing, Distributed Optimization, regression, Stochastic Optimization

We consider distributed convex optimization problems originated from sample
average approximation of stochastic optimization, or empirical risk
minimization in machine learning. We assume that each machine in the
distributed computing system has access to a local empirical loss function,
constructed with i.i.d. data sampled from a common distribution. We propose a
communication-efficient distributed algorithm to minimize the overall empirical
loss, which is the average of the local empirical losses. The algorithm is
based on an inexact damped Newton method, where the inexact Newton steps are
computed by a distributed preconditioned conjugate gradient method. We analyze
its iteration complexity and communication efficiency for minimizing
self-concordant empirical loss functions, and discuss the results for
distributed ridge regression, logistic regression and binary classification
with a smoothed hinge loss. In a standard setting for supervised learning, the
required number of communication rounds of the algorithm does not increase with
the sample size, and only grows slowly with the number of machines.
Solving Games with Functional Regret Estimation
Authors: Kevin Waugh, Dustin Morrill, J. Andrew Bagnell, Michael Bowling
Date: 2014-11-28 00:00:00

We propose a novel online learning method for minimizing regret in large
extensive-form games. The approach learns a function approximator online to
estimate the regret for choosing a particular action. A no-regret algorithm
uses these estimates in place of the true regrets to define a sequence of
policies.
  We prove the approach sound by providing a bound relating the quality of the
function approximation and regret of the algorithm. A corollary being that the
method is guaranteed to converge to a Nash equilibrium in self-play so long as
the regrets are ultimately realizable by the function approximator. Our
technique can be understood as a principled generalization of existing work on
abstraction in large games; in our work, both the abstraction as well as the
equilibrium are learned during self-play. We demonstrate empirically the method
achieves higher quality strategies than state-of-the-art abstraction techniques
given the same resources.
Beta-Negative Binomial Process and Exchangeable Random Partitions for Mixed-Membership Modeling
Authors: Mingyuan Zhou
Date: 2014-10-28 00:00:00

The beta-negative binomial process (BNBP), an integer-valued stochastic
process, is employed to partition a count vector into a latent random count
matrix. As the marginal probability distribution of the BNBP that governs the
exchangeable random partitions of grouped data has not yet been developed,
current inference for the BNBP has to truncate the number of atoms of the beta
process. This paper introduces an exchangeable partition probability function
to explicitly describe how the BNBP clusters the data points of each group into
a random number of exchangeable partitions, which are shared across all the
groups. A fully collapsed Gibbs sampler is developed for the BNBP, leading to a
novel nonparametric Bayesian topic model that is distinct from existing ones,
with simple implementation, fast convergence, good mixing, and state-of-the-art
predictive performance.
The continuum-of-urns scheme, generalized beta and Indian buffet processes, and hierarchies thereof
Authors: Daniel M. Roy
Date: 2014-12-31 00:00:00

We describe the combinatorial stochastic process underlying a sequence of
conditionally independent Bernoulli processes with a shared beta process hazard
measure. As shown by Thibaux and Jordan [TJ07], in the special case when the
underlying beta process has a constant concentration function and a finite and
nonatomic mean, the combinatorial structure is that of the Indian buffet
process (IBP) introduced by Griffiths and Ghahramani [GG05]. By reinterpreting
the beta process introduced by Hjort [Hjo90] as a measurable family of
Dirichlet processes, we obtain a simple predictive rule for the general case,
which can be thought of as a continuum of Blackwell-MacQueen urn schemes (or
equivalently, one-parameter Hoppe urn schemes). The corresponding measurable
family of Perman-Pitman-Yor processes leads to a continuum of two-parameter
Hoppe urn schemes, whose ordinary component is the three-parameter IBP
introduced by Teh and G\"or\"ur [TG09], which exhibits power-law behavior, as
further studied by Broderick, Jordan, and Pitman [BJP12]. The idea extends to
arbitrary measurable families of exchangeable partition probability functions
and gives rise to generalizations of the beta process with matching buffet
processes. Finally, in the same way that hierarchies of Dirichlet processes
were given Chinese restaurant franchise representations by Teh, Jordan, Beal,
and Blei [Teh+06], one can construct representations of sequences of Bernoulli
processes directed by hierarchies of beta processes (and their generalizations)
using the stochastic process we uncover.