pwc-archive/papers-with-abstracts huggingface dataset:
How to partition diversity
Authors: Richard Reeve, Tom Leinster, Christina A. Cobbold, Jill Thompson, Neil Brummitt, Sonia N. Mitchell, Louise Matthews
Date: 2014-04-25 00:00:00
Tasks: Diversity

Diversity measurement underpins the study of biological systems, but measures
used vary across disciplines. Despite their common use and broad utility, no
unified framework has emerged for measuring, comparing and partitioning
diversity. The introduction of information theory into diversity measurement
has laid the foundations, but the framework is incomplete without the ability
to partition diversity, which is central to fundamental questions across the
life sciences: How do we prioritise communities for conservation? How do we
identify reservoirs and sources of pathogenic organisms? How do we measure
ecological disturbance arising from climate change?
  The lack of a common framework means that diversity measures from different
fields have conflicting fundamental properties, allowing conclusions reached to
depend on the measure chosen. This conflict is unnecessary and unhelpful. A
mathematically consistent framework would transform disparate fields by
delivering scientific insights in a common language. It would also allow the
transfer of theoretical and practical developments between fields.
  We meet this need, providing a versatile unified framework for partitioning
biological diversity. It encompasses any kind of similarity between
individuals, from functional to genetic, allowing comparisons between
qualitatively different kinds of diversity. Where existing partitioning
measures aggregate information across the whole population, our approach
permits the direct comparison of subcommunities, allowing us to pinpoint
distinct, diverse or representative subcommunities and investigate population
substructure. The framework is provided as a ready-to-use R package to easily
test our approach.
Athena: A New Code for Astrophysical MHD
Authors: James M. Stone, Thomas A. Gardiner, Peter Teuben, John F. Hawley, Jacob B. Simon
Date: 2008-04-02 00:00:00

A new code for astrophysical magnetohydrodynamics (MHD) is described. The
code has been designed to be easily extensible for use with static and adaptive
mesh refinement. It combines higher-order Godunov methods with the constrained
transport (CT) technique to enforce the divergence-free constraint on the
magnetic field. Discretization is based on cell-centered volume-averages for
mass, momentum, and energy, and face-centered area-averages for the magnetic
field. Novel features of the algorithm include (1) a consistent framework for
computing the time- and edge-averaged electric fields used by CT to evolve the
magnetic field from the time- and area-averaged Godunov fluxes, (2) the
extension to MHD of spatial reconstruction schemes that involve a
dimensionally-split time advance, and (3) the extension to MHD of two different
dimensionally-unsplit integration methods. Implementation of the algorithm in
both C and Fortran95 is detailed, including strategies for parallelization
using domain decomposition. Results from a test suite which includes problems
in one-, two-, and three-dimensions for both hydrodynamics and MHD are given,
not only to demonstrate the fidelity of the algorithms, but also to enable
comparisons to other methods. The source code is freely available for download
on the web.
Component response rate variation underlies the stability of highly complex finite systems
Authors: A. Bradley Duthie
Date: 2018-06-04 00:00:00

The stability of a complex system generally decreases with increasing system size and interconnectivity, a counterintuitive result of widespread importance across the physical, life, and social sciences. Despite recent interest in the relationship between system properties and stability, the effect of variation in response rate across system components remains unconsidered. Here I vary the component response rates ($\boldsymbol{\gamma}$) of randomly generated complex systems. I use numerical simulations to show that when component response rates vary, the potential for system stability increases. These results are robust to common network structures, including small-world and scale-free networks, and cascade food webs. Variation in $\boldsymbol{\gamma}$ is especially important for stability in highly complex systems, in which the probability of stability would otherwise be negligible. At such extremes of simulated system complexity, the largest stable complex systems would be unstable if not for variation in $\boldsymbol{\gamma}$. My results therefore reveal a previously unconsidered aspect of system stability that is likely to be pervasive across all realistic complex systems.
Efficient algorithms to discover alterations with complementary functional association in cancer
Authors: Rebecca Sarto Basso, Dorit S. Hochbaum, Fabio Vandin
Date: 2018-03-26 00:00:00

Recent large cancer studies have measured somatic alterations in an
unprecedented number of tumours. These large datasets allow the identification
of cancer-related sets of genetic alterations by identifying relevant
combinatorial patterns. Among such patterns, mutual exclusivity has been
employed by several recent methods that have shown its effectivenes in
characterizing gene sets associated to cancer. Mutual exclusivity arises
because of the complementarity, at the functional level, of alterations in
genes which are part of a group (e.g., a pathway) performing a given function.
The availability of quantitative target profiles, from genetic perturbations or
from clinical phenotypes, provides additional information that can be leveraged
to improve the identification of cancer related gene sets by discovering groups
with complementary functional associations with such targets.
  In this work we study the problem of finding groups of mutually exclusive
alterations associated with a quantitative (functional) target. We propose a
combinatorial formulation for the problem, and prove that the associated
computation problem is computationally hard. We design two algorithms to solve
the problem and implement them in our tool UNCOVER. We provide analytic
evidence of the effectiveness of UNCOVER in finding high-quality solutions and
show experimentally that UNCOVER finds sets of alterations significantly
associated with functional targets in a variety of scenarios. In addition, our
algorithms are much faster than the state-of-the-art, allowing the analysis of
large datasets of thousands of target profiles from cancer cell lines. We show
that on one such dataset from project Achilles our methods identify several
significant gene sets with complementary functional associations with targets.
Hilbert space embeddings and metrics on probability measures
Authors: Bharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, Gert R. G. Lanckriet
Date: 2009-07-30 00:00:00
Tasks: Dimensionality Reduction

A Hilbert space embedding for probability measures has recently been
proposed, with applications including dimensionality reduction, homogeneity
testing, and independence testing. This embedding represents any probability
measure as a mean element in a reproducing kernel Hilbert space (RKHS). A
pseudometric on the space of probability measures can be defined as the
distance between distribution embeddings: we denote this as $\gamma_k$, indexed
by the kernel function $k$ that defines the inner product in the RKHS.
  We present three theoretical properties of $\gamma_k$. First, we consider the
question of determining the conditions on the kernel $k$ for which $\gamma_k$
is a metric: such $k$ are denoted {\em characteristic kernels}. Unlike
pseudometrics, a metric is zero only when two distributions coincide, thus
ensuring the RKHS embedding maps all distributions uniquely (i.e., the
embedding is injective). While previously published conditions may apply only
in restricted circumstances (e.g. on compact domains), and are difficult to
check, our conditions are straightforward and intuitive: bounded continuous
strictly positive definite kernels are characteristic. Alternatively, if a
bounded continuous kernel is translation-invariant on $\bb{R}^d$, then it is
characteristic if and only if the support of its Fourier transform is the
entire $\bb{R}^d$. Second, we show that there exist distinct distributions that
are arbitrarily close in $\gamma_k$. Third, to understand the nature of the
topology induced by $\gamma_k$, we relate $\gamma_k$ to other popular metrics
on probability measures, and present conditions on the kernel $k$ under which
$\gamma_k$ metrizes the weak topology.
Determinantal point processes for machine learning
Authors: Alex Kulesza, Ben Taskar
Date: 2012-07-25 00:00:00
Tasks: BIG-bench Machine Learning, Point Processes

Determinantal point processes (DPPs) are elegant probabilistic models of
repulsion that arise in quantum physics and random matrix theory. In contrast
to traditional structured models like Markov random fields, which become
intractable and hard to approximate in the presence of negative correlations,
DPPs offer efficient and exact algorithms for sampling, marginalization,
conditioning, and other inference tasks. We provide a gentle introduction to
DPPs, focusing on the intuitions, algorithms, and extensions that are most
relevant to the machine learning community, and show how DPPs can be applied to
real-world applications like finding diverse sets of high-quality search
results, building informative summaries by selecting diverse sentences from
documents, modeling non-overlapping human poses in images or video, and
automatically building timelines of important news stories.
Reduced-Rank Hidden Markov Models
Authors: Sajid M. Siddiqi, Byron Boots, Geoffrey J. Gordon
Date: 2009-10-06 00:00:00

We introduce the Reduced-Rank Hidden Markov Model (RR-HMM), a generalization
of HMMs that can model smooth state evolution as in Linear Dynamical Systems
(LDSs) as well as non-log-concave predictive distributions as in
continuous-observation HMMs. RR-HMMs assume an m-dimensional latent state and n
discrete observations, with a transition matrix of rank k <= m. This implies
the dynamics evolve in a k-dimensional subspace, while the shape of the set of
predictive distributions is determined by m. Latent state belief is represented
with a k-dimensional state vector and inference is carried out entirely in R^k,
making RR-HMMs as computationally efficient as k-state HMMs yet more
expressive. To learn RR-HMMs, we relax the assumptions of a recently proposed
spectral learning algorithm for HMMs (Hsu, Kakade and Zhang 2009) and apply it
to learn k-dimensional observable representations of rank-k RR-HMMs. The
algorithm is consistent and free of local optima, and we extend its performance
guarantees to cover the RR-HMM case. We show how this algorithm can be used in
conjunction with a kernel density estimator to efficiently model
high-dimensional multivariate continuous data. We also relax the assumption
that single observations are sufficient to disambiguate state, and extend the
algorithm accordingly. Experiments on synthetic data and a toy video, as well
as on a difficult robot vision modeling problem, yield accurate models that
compare favorably with standard alternatives in simulation quality and
prediction capability.
Structured Sparse Principal Component Analysis
Authors: Rodolphe Jenatton, Guillaume Obozinski, Francis Bach
Date: 2009-09-08 00:00:00
Tasks: Dictionary Learning, Face Recognition

We present an extension of sparse PCA, or sparse dictionary learning, where
the sparsity patterns of all dictionary elements are structured and constrained
to belong to a prespecified set of shapes. This \emph{structured sparse PCA} is
based on a structured regularization recently introduced by [1]. While
classical sparse priors only deal with \textit{cardinality}, the regularization
we use encodes higher-order information about the data. We propose an efficient
and simple optimization procedure to solve this problem. Experiments with two
practical tasks, face recognition and the study of the dynamics of a protein
complex, demonstrate the benefits of the proposed structured approach over
unstructured approaches.
No More Pesky Learning Rates
Authors: Tom Schaul, Sixin Zhang, Yann Lecun
Date: 2012-06-06 00:00:00

The performance of stochastic gradient descent (SGD) depends critically on
how learning rates are tuned and decreased over time. We propose a method to
automatically adjust multiple learning rates so as to minimize the expected
error at any one time. The method relies on local gradient variations across
samples. In our approach, learning rates can increase as well as decrease,
making it suitable for non-stationary problems. Using a number of convex and
non-convex learning tasks, we show that the resulting algorithm matches the
performance of SGD or other adaptive approaches with their best settings
obtained through systematic search, and effectively removes the need for
learning rate tuning.
Uncovering the Temporal Dynamics of Diffusion Networks
Authors: Manuel Gomez Rodriguez, David Balduzzi, Bernhard Schölkopf
Date: 2011-05-03 00:00:00

Time plays an essential role in the diffusion of information, influence and
disease over networks. In many cases we only observe when a node copies
information, makes a decision or becomes infected -- but the connectivity,
transmission rates between nodes and transmission sources are unknown.
Inferring the underlying dynamics is of outstanding interest since it enables
forecasting, influencing and retarding infections, broadly construed. To this
end, we model diffusion processes as discrete networks of continuous temporal
processes occurring at different rates. Given cascade data -- observed
infection times of nodes -- we infer the edges of the global diffusion network
and estimate the transmission rates of each edge that best explain the observed
data. The optimization problem is convex. The model naturally (without
heuristics) imposes sparse solutions and requires no parameter tuning. The
problem decouples into a collection of independent smaller problems, thus
scaling easily to networks on the order of hundreds of thousands of nodes.
Experiments on real and synthetic data show that our algorithm both recovers
the edges of diffusion networks and accurately estimates their transmission
rates from cascade data.
Elliptical slice sampling
Authors: Iain Murray, Ryan Prescott Adams, David J. C. MacKay
Date: 2009-12-31 00:00:00

Many probabilistic models introduce strong dependencies between variables
using a latent multivariate Gaussian distribution or a Gaussian process. We
present a new Markov chain Monte Carlo algorithm for performing inference in
models with multivariate Gaussian priors. Its key properties are: 1) it has
simple, generic code applicable to many models, 2) it has no free parameters,
3) it works well for a variety of Gaussian process based models. These
properties make our method ideal for use while model building, removing the
need to spend time deriving and tuning updates for more complex algorithms.
The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo
Authors: Matthew D. Hoffman, Andrew Gelman
Date: 2011-11-18 00:00:00

Hamiltonian Monte Carlo (HMC) is a Markov chain Monte Carlo (MCMC) algorithm
that avoids the random walk behavior and sensitivity to correlated parameters
that plague many MCMC methods by taking a series of steps informed by
first-order gradient information. These features allow it to converge to
high-dimensional target distributions much more quickly than simpler methods
such as random walk Metropolis or Gibbs sampling. However, HMC's performance is
highly sensitive to two user-specified parameters: a step size {\epsilon} and a
desired number of steps L. In particular, if L is too small then the algorithm
exhibits undesirable random walk behavior, while if L is too large the
algorithm wastes computation. We introduce the No-U-Turn Sampler (NUTS), an
extension to HMC that eliminates the need to set a number of steps L. NUTS uses
a recursive algorithm to build a set of likely candidate points that spans a
wide swath of the target distribution, stopping automatically when it starts to
double back and retrace its steps. Empirically, NUTS perform at least as
efficiently as and sometimes more efficiently than a well tuned standard HMC
method, without requiring user intervention or costly tuning runs. We also
derive a method for adapting the step size parameter {\epsilon} on the fly
based on primal-dual averaging. NUTS can thus be used with no hand-tuning at
all. NUTS is also suitable for applications such as BUGS-style automatic
inference engines that require efficient "turnkey" sampling algorithms.
From Machine Learning to Machine Reasoning
Authors: Leon Bottou
Date: 2011-02-09 00:00:00
Tasks: BIG-bench Machine Learning, Language Modeling, Language Modelling, Optical Character Recognition, Optical Character Recognition (OCR)

A plausible definition of "reasoning" could be "algebraically manipulating
previously acquired knowledge in order to answer a new question". This
definition covers first-order logical inference or probabilistic inference. It
also includes much simpler manipulations commonly used to build large learning
systems. For instance, we can build an optical character recognition system by
first training a character segmenter, an isolated character recognizer, and a
language model, using appropriate labeled training sets. Adequately
concatenating these modules and fine tuning the resulting system can be viewed
as an algebraic operation in a space of models. The resulting model answers a
new question, that is, converting the image of a text page into a computer
readable text.
  This observation suggests a conceptual continuity between algebraically rich
inference systems, such as logical or probabilistic inference, and simple
manipulations, such as the mere concatenation of trainable learning systems.
Therefore, instead of trying to bridge the gap between machine learning systems
and sophisticated "all-purpose" inference mechanisms, we can instead
algebraically enrich the set of manipulations applicable to training systems,
and build reasoning capabilities from the ground up.
Hybrid Bayesian Eigenobjects: Combining Linear Subspace and Deep Network Methods for 3D Robot Vision
Authors: Benjamin Burchfiel, George Konidaris
Date: 2018-06-20 00:00:00
Tasks: 3D geometry, Object, subspace methods

We introduce Hybrid Bayesian Eigenobjects (HBEOs), a novel representation for
3D objects designed to allow a robot to jointly estimate the pose, class, and
full 3D geometry of a novel object observed from a single viewpoint in a single
practical framework. By combining both linear subspace methods and deep
convolutional prediction, HBEOs efficiently learn nonlinear object
representations without directly regressing into high-dimensional space. HBEOs
also remove the onerous and generally impractical necessity of input data
voxelization prior to inference. We experimentally evaluate the suitability of
HBEOs to the challenging task of joint pose, class, and shape inference on
novel objects and show that, compared to preceding work, HBEOs offer
dramatically improved performance in all three tasks along with several orders
of magnitude faster runtime performance.
Sequential change-point detection in high-dimensional Gaussian graphical models
Authors: Hossein Keshavarz, George Michailidis, Yves Atchade
Date: 2018-06-20 00:00:00
Tasks: Change Point Detection, Vocal Bursts Intensity Prediction

High dimensional piecewise stationary graphical models represent a versatile
class for modelling time varying networks arising in diverse application areas,
including biology, economics, and social sciences. There has been recent work
in offline detection and estimation of regime changes in the topology of sparse
graphical models. However, the online setting remains largely unexplored,
despite its high relevance to applications in sensor networks and other
engineering monitoring systems, as well as financial markets. To that end, this
work introduces a novel scalable online algorithm for detecting an unknown
number of abrupt changes in the inverse covariance matrix of sparse Gaussian
graphical models with small delay. The proposed algorithm is based upon
monitoring the conditional log-likelihood of all nodes in the network and can
be extended to a large class of continuous and discrete graphical models. We
also investigate asymptotic properties of our procedure under certain mild
regularity conditions on the graph size, sparsity level, number of samples, and
pre- and post-changes in the topology of the network. Numerical works on both
synthetic and real data illustrate the good performance of the proposed
methodology both in terms of computational and statistical efficiency across
numerous experimental settings.
Learning ReLU Networks via Alternating Minimization
Authors: Gauri Jagatap, Chinmay Hegde
Date: 2018-06-20 00:00:00

We propose and analyze a new family of algorithms for training neural
networks with ReLU activations. Our algorithms are based on the technique of
alternating minimization: estimating the activation patterns of each ReLU for
all given samples, interleaved with weight updates via a least-squares step.
The main focus of our paper are 1-hidden layer networks with $k$ hidden neurons
and ReLU activation. We show that under standard distributional assumptions on
the $d-$dimensional input data, our algorithm provably recovers the true
`ground truth' parameters in a linearly convergent fashion. This holds as long
as the weights are sufficiently well initialized; furthermore, our method
requires only $n=\widetilde{O}(dk^2)$ samples. We also analyze the special case
of 1-hidden layer networks with skipped connections, commonly used in
ResNet-type architectures, and propose a novel initialization strategy for the
same. For ReLU based ResNet type networks, we provide the first linear
convergence guarantee with an end-to-end algorithm. We also extend this
framework to deeper networks and empirically demonstrate its convergence to a
global minimum.
RUDDER: Return Decomposition for Delayed Rewards
Authors: Jose A. Arjona-Medina, Michael Gillhofer, Michael Widrich, Thomas Unterthiner, Johannes Brandstetter, Sepp Hochreiter
Date: 2018-06-20 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Atari Games, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We propose RUDDER, a novel reinforcement learning approach for delayed rewards in finite Markov decision processes (MDPs). In MDPs the Q-values are equal to the expected immediate reward plus the expected future rewards. The latter are related to bias problems in temporal difference (TD) learning and to high variance problems in Monte Carlo (MC) learning. Both problems are even more severe when rewards are delayed. RUDDER aims at making the expected future rewards zero, which simplifies Q-value estimation to computing the mean of the immediate reward. We propose the following two new concepts to push the expected future rewards toward zero. (i) Reward redistribution that leads to return-equivalent decision processes with the same optimal policies and, when optimal, zero expected future rewards. (ii) Return decomposition via contribution analysis which transforms the reinforcement learning task into a regression task at which deep learning excels. On artificial tasks with delayed rewards, RUDDER is significantly faster than MC and exponentially faster than Monte Carlo Tree Search (MCTS), TD({\lambda}), and reward shaping approaches. At Atari games, RUDDER on top of a Proximal Policy Optimization (PPO) baseline improves the scores, which is most prominent at games with delayed rewards. Source code is available at \url{https://github.com/ml-jku/rudder} and demonstration videos at \url{https://goo.gl/EQerZV}.