pwc-archive/papers-with-abstracts huggingface dataset:
Data-Driven Threshold Machine: Scan Statistics, Change-Point Detection, and Extreme Bandits
Authors: Shuang Li, Yao Xie, Le Song
Date: 2016-10-14 00:00:00
Tasks: Change Point Detection, Computational Efficiency

We present a novel distribution-free approach, the data-driven threshold
machine (DTM), for a fundamental problem at the core of many learning tasks:
choose a threshold for a given pre-specified level that bounds the tail
probability of the maximum of a (possibly dependent but stationary) random
sequence. We do not assume data distribution, but rather relying on the
asymptotic distribution of extremal values, and reduce the problem to estimate
three parameters of the extreme value distributions and the extremal index. We
specially take care of data dependence via estimating extremal index since in
many settings, such as scan statistics, change-point detection, and extreme
bandits, where dependence in the sequence of statistics can be significant. Key
features of our DTM also include robustness and the computational efficiency,
and it only requires one sample path to form a reliable estimate of the
threshold, in contrast to the Monte Carlo sampling approach which requires
drawing a large number of sample paths. We demonstrate the good performance of
DTM via numerical examples in various dependent settings.
Message-passing algorithms for synchronization problems over compact groups
Authors: Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, Ankur Moitra
Date: 2016-10-14 00:00:00
Tasks: Community Detection, compressed sensing

Various alignment problems arising in cryo-electron microscopy, community
detection, time synchronization, computer vision, and other fields fall into a
common framework of synchronization problems over compact groups such as Z/L,
U(1), or SO(3). The goal of such problems is to estimate an unknown vector of
group elements given noisy relative observations. We present an efficient
iterative algorithm to solve a large class of these problems, allowing for any
compact group, with measurements on multiple 'frequency channels' (Fourier
modes, or more generally, irreducible representations of the group). Our
algorithm is a highly efficient iterative method following the blueprint of
approximate message passing (AMP), which has recently arisen as a central
technique for inference problems such as structured low-rank estimation and
compressed sensing. We augment the standard ideas of AMP with ideas from
representation theory so that the algorithm can work with distributions over
compact groups. Using standard but non-rigorous methods from statistical
physics we analyze the behavior of our algorithm on a Gaussian noise model,
identifying phases where the problem is easy, (computationally) hard, and
(statistically) impossible. In particular, such evidence predicts that our
algorithm is information-theoretically optimal in many cases, and that the
remaining cases show evidence of statistical-to-computational gaps.
Two-sample testing in non-sparse high-dimensional linear models
Authors: Yinchu Zhu, Jelena Bradic
Date: 2016-10-14 00:00:00
Tasks: regression, Two-sample testing, Vocal Bursts Intensity Prediction, Vocal Bursts Valence Prediction

In analyzing high-dimensional models, sparsity of the model parameter is a
common but often undesirable assumption. In this paper, we study the following
two-sample testing problem: given two samples generated by two high-dimensional
linear models, we aim to test whether the regression coefficients of the two
linear models are identical. We propose a framework named TIERS (short for
TestIng Equality of Regression Slopes), which solves the two-sample testing
problem without making any assumptions on the sparsity of the regression
parameters. TIERS builds a new model by convolving the two samples in such a
way that the original hypothesis translates into a new moment condition. A
self-normalization construction is then developed to form a moment test. We
provide rigorous theory for the developed framework. Under very weak conditions
of the feature covariance, we show that the accuracy of the proposed test in
controlling Type I errors is robust both to the lack of sparsity in the
features and to the heavy tails in the error distribution, even when the sample
size is much smaller than the feature dimension. Moreover, we discuss minimax
optimality and efficiency properties of the proposed test. Simulation analysis
demonstrates excellent finite-sample performance of our test. In deriving the
test, we also develop tools that are of independent interest. The test is built
upon a novel estimator, called Auto-aDaptive Dantzig Selector (ADDS), which not
only automatically chooses an appropriate scale of the error term but also
incorporates prior information. To effectively approximate the critical value
of the test statistic, we develop a novel high-dimensional plug-in approach
that complements the recent advances in Gaussian approximation theory.
Automatically tracking neurons in a moving and deforming brain
Authors: Jeffrey P. Nguyen, Ashley N. Linder, George S. Plummer, Joshua W. Shaevitz, Andrew M. Leifer
Date: 2016-10-14 00:00:00

Advances in optical neuroimaging techniques now allow neural activity to be
recorded with cellular resolution in awake and behaving animals. Brain motion
in these recordings pose a unique challenge. The location of individual neurons
must be tracked in 3D over time to accurately extract single neuron activity
traces. Recordings from small invertebrates like C. elegans are especially
challenging because they undergo very large brain motion and deformation during
animal movement. Here we present an automated computer vision pipeline to
reliably track populations of neurons with single neuron resolution in the
brain of a freely moving C. elegans undergoing large motion and deformation. 3D
volumetric fluorescent images of the animal's brain are straightened, aligned
and registered, and the locations of neurons in the images are found via
segmentation. Each neuron is then assigned an identity using a new
time-independent machine-learning approach we call Neuron Registration Vector
Encoding. In this approach, non-rigid point-set registration is used to match
each segmented neuron in each volume with a set of reference volumes taken from
throughout the recording. The way each neuron matches with the references
defines a feature vector which is clustered to assign an identity to each
neuron in each volume. Finally, thin-plate spline interpolation is used to
correct errors in segmentation and check consistency of assigned identities.
The Neuron Registration Vector Encoding approach proposed here is uniquely well
suited for tracking neurons in brains undergoing large deformations. When
applied to whole-brain calcium imaging recordings in freely moving C. elegans,
this analysis pipeline located 150 neurons for the duration of an 8 minute
recording and consistently found more neurons more quickly than manual or
semi-automated approaches.
Kernel Alignment Inspired Linear Discriminant Analysis
Authors: Shuai Zheng, Chris Ding
Date: 2016-10-14 00:00:00

Kernel alignment measures the degree of similarity between two kernels. In
this paper, inspired from kernel alignment, we propose a new Linear
Discriminant Analysis (LDA) formulation, kernel alignment LDA (kaLDA). We first
define two kernels, data kernel and class indicator kernel. The problem is to
find a subspace to maximize the alignment between subspace-transformed data
kernel and class indicator kernel. Surprisingly, the kernel alignment induced
kaLDA objective function is very similar to classical LDA and can be expressed
using between-class and total scatter matrices. This can be extended to
multi-label data. We use a Stiefel-manifold gradient descent algorithm to solve
this problem. We perform experiments on 8 single-label and 6 multi-label data
sets. Results show that kaLDA has very good performance on many single-label
and multi-label problems.
Understanding intermediate layers using linear classifier probes
Authors: Guillaume Alain, Yoshua Bengio
Date: 2016-10-05 00:00:00
Tasks: General Classification

Neural network models have a reputation for being black boxes. We propose to
monitor the features at every layer of a model and measure how suitable they
are for classification. We use linear classifiers, which we refer to as
"probes", trained entirely independently of the model itself.
  This helps us better understand the roles and dynamics of the intermediate
layers. We demonstrate how this can be used to develop a better intuition about
models and to diagnose potential problems.
  We apply this technique to the popular models Inception v3 and Resnet-50.
Among other things, we observe experimentally that the linear separability of
features increase monotonically along the depth of the model.
On Duality Of Multiple Target Tracking and Segmentation
Authors: Yicong Tian, Mubarak Shah
Date: 2016-10-14 00:00:00
Tasks: Object, Object Tracking, Occlusion Handling, Segmentation, Semantic Segmentation

Traditionally, object tracking and segmentation are treated as two separate
problems and solved independently. However, in this paper, we argue that
tracking and segmentation are actually closely related and solving one should
help the other. On one hand, the object track, which is a set of bounding boxes
with one bounding box in every frame, would provide strong high-level guidance
for the target/background segmentation task. On the other hand, the object
segmentation would separate object from other objects and background, which
will be useful for determining track locations in every frame. We propose a
novel framework which combines online multiple target tracking and segmentation
in a video. In our approach, the tracking and segmentation problems are coupled
by Lagrange dual decomposition, which leads to more accurate segmentation
results and also \emph{helps resolve typical difficulties in multiple target
tracking, such as occlusion handling, ID-switch and track drifting}. To track
targets, an individual appearance model is learned for each target via
structured learning and network flow is employed to generate tracks from
densely sampled candidates. For segmentation, multi-label Conditional Random
Field (CRF) is applied to a superpixel based spatio-temporal graph in a segment
of video to assign background or target labels to every superpixel. The
experiments on diverse sequences show that our method outperforms
state-of-the-art approaches for multiple target tracking as well as
segmentation.
Numerical Inversion of SRNF Maps for Elastic Shape Analysis of Genus-Zero Surfaces
Authors: Hamid Laga, Qian Xie, Ian H. Jermyn, Anuj Srivastava
Date: 2016-10-14 00:00:00
Tasks: Computational Efficiency

Recent developments in elastic shape analysis (ESA) are motivated by the fact
that it provides comprehensive frameworks for simultaneous registration,
deformation, and comparison of shapes. These methods achieve computational
efficiency using certain square-root representations that transform invariant
elastic metrics into Euclidean metrics, allowing for applications of standard
algorithms and statistical tools. For analyzing shapes of embeddings of
$\mathbb{S}^2$ in $\mathbb{R}^3$, Jermyn et al. introduced square-root normal
fields (SRNFs) that transformed an elastic metric, with desirable invariant
properties, into the $\mathbb{L}^2$ metric. These SRNFs are essentially surface
normals scaled by square-roots of infinitesimal area elements. A critical need
in shape analysis is to invert solutions (deformations, averages, modes of
variations, etc) computed in the SRNF space, back to the original surface space
for visualizations and inferences. Due to the lack of theory for understanding
SRNFs maps and their inverses, we take a numerical approach and derive an
efficient multiresolution algorithm, based on solving an optimization problem
in the surface space, that estimates surfaces corresponding to given SRNFs.
This solution is found effective, even for complex shapes, e.g. human bodies
and animals, that undergo significant deformations including bending and
stretching. Specifically, we use this inversion for computing elastic shape
deformations, transferring deformations, summarizing shapes, and for finding
modes of variability in a given collection, while simultaneously registering
the surfaces. We demonstrate the proposed algorithms using a statistical
analysis of human body shapes, classification of generic surfaces and analysis
of brain structures.
Fast rates with high probability in exp-concave statistical learning
Authors: Nishant A. Mehta
Date: 2016-05-04 00:00:00
Tasks: Model Selection, Vocal Bursts Intensity Prediction

We present an algorithm for the statistical learning setting with a bounded
exp-concave loss in $d$ dimensions that obtains excess risk $O(d
\log(1/\delta)/n)$ with probability at least $1 - \delta$. The core technique
is to boost the confidence of recent in-expectation $O(d/n)$ excess risk bounds
for empirical risk minimization (ERM), without sacrificing the rate, by
leveraging a Bernstein condition which holds due to exp-concavity. We also show
that with probability $1 - \delta$ the standard ERM method obtains excess risk
$O(d (\log(n) + \log(1/\delta))/n)$. We further show that a regret bound for
any online learner in this setting translates to a high probability excess risk
bound for the corresponding online-to-batch conversion of the online learner.
Lastly, we present two high probability bounds for the exp-concave model
selection aggregation problem that are quantile-adaptive in a certain sense.
The first bound is a purely exponential weights type algorithm, obtains a
nearly optimal rate, and has no explicit dependence on the Lipschitz continuity
of the loss. The second bound requires Lipschitz continuity but obtains the
optimal rate.
The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
Authors: Tor Lattimore, Csaba Szepesvari
Date: 2016-10-14 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Thompson Sampling

Stochastic linear bandits are a natural and simple generalisation of
finite-armed bandits with numerous practical applications. Current approaches
focus on generalising existing techniques for finite-armed bandits, notably the
optimism principle and Thompson sampling. While prior work has mostly been in
the worst-case setting, we analyse the asymptotic instance-dependent regret and
show matching upper and lower bounds on what is achievable. Surprisingly, our
results show that no algorithm based on optimism or Thompson sampling will ever
achieve the optimal rate, and indeed, can be arbitrarily far from optimal, even
in very simple cases. This is a disturbing result because these techniques are
standard tools that are widely used for sequential optimisation. For example,
for generalised linear bandits and reinforcement learning.
Distributional Inclusion Hypothesis for Tensor-based Composition
Authors: Dimitri Kartsaklis, Mehrnoosh Sadrzadeh
Date: 2016-10-14 00:00:00
Proceeding: COLING 2016 12
Tasks: Sentence

According to the distributional inclusion hypothesis, entailment between
words can be measured via the feature inclusions of their distributional
vectors. In recent work, we showed how this hypothesis can be extended from
words to phrases and sentences in the setting of compositional distributional
semantics. This paper focuses on inclusion properties of tensors; its main
contribution is a theoretical and experimental analysis of how feature
inclusion works in different concrete models of verb tensors. We present
results for relational, Frobenius, projective, and holistic methods and compare
them to the simple vector addition, multiplication, min, and max models. The
degrees of entailment thus obtained are evaluated via a variety of existing
word-based measures, such as Weed's and Clarke's, KL-divergence, APinc,
balAPinc, and two of our previously proposed metrics at the phrase/sentence
level. We perform experiments on three entailment datasets, investigating which
version of tensor-based composition achieves the highest performance when
combined with the sentence-level measures.
Cohesion and Coalition Formation in the European Parliament: Roll-Call Votes and Twitter Activities
Authors: Darko Cherepnalkoski, Andreas Karpf, Igor Mozetic, Miha Grcar
Date: 2016-08-17 00:00:00

We study the cohesion within and the coalitions between political groups in
the Eighth European Parliament (2014--2019) by analyzing two entirely different
aspects of the behavior of the Members of the European Parliament (MEPs) in the
policy-making processes. On one hand, we analyze their co-voting patterns and,
on the other, their retweeting behavior. We make use of two diverse datasets in
the analysis. The first one is the roll-call vote dataset, where cohesion is
regarded as the tendency to co-vote within a group, and a coalition is formed
when the members of several groups exhibit a high degree of co-voting agreement
on a subject. The second dataset comes from Twitter; it captures the retweeting
(i.e., endorsing) behavior of the MEPs and implies cohesion (retweets within
the same group) and coalitions (retweets between groups) from a completely
different perspective.
  We employ two different methodologies to analyze the cohesion and coalitions.
The first one is based on Krippendorff's Alpha reliability, used to measure the
agreement between raters in data-analysis scenarios, and the second one is
based on Exponential Random Graph Models, often used in social-network
analysis. We give general insights into the cohesion of political groups in the
European Parliament, explore whether coalitions are formed in the same way for
different policy areas, and examine to what degree the retweeting behavior of
MEPs corresponds to their co-voting patterns. A novel and interesting aspect of
our work is the relationship between the co-voting and retweeting patterns.
Semi-Supervised Active Learning for Support Vector Machines: A Novel Approach that Exploits Structure Information in Data
Authors: Tobias Reitmaier, Adrian Calma, Bernhard Sick
Date: 2016-10-13 00:00:00
Tasks: Active Learning, General Classification

In our today's information society more and more data emerges, e.g.~in social
networks, technical applications, or business applications. Companies try to
commercialize these data using data mining or machine learning methods. For
this purpose, the data are categorized or classified, but often at high
(monetary or temporal) costs. An effective approach to reduce these costs is to
apply any kind of active learning (AL) methods, as AL controls the training
process of a classifier by specific querying individual data points (samples),
which are then labeled (e.g., provided with class memberships) by a domain
expert. However, an analysis of current AL research shows that AL still has
some shortcomings. In particular, the structure information given by the
spatial pattern of the (un)labeled data in the input space of a classification
model (e.g.,~cluster information), is used in an insufficient way. In addition,
many existing AL techniques pay too little attention to their practical
applicability. To meet these challenges, this article presents several
techniques that together build a new approach for combining AL and
semi-supervised learning (SSL) for support vector machines (SVM) in
classification tasks. Structure information is captured by means of
probabilistic models that are iteratively improved at runtime when label
information becomes available. The probabilistic models are considered in a
selection strategy based on distance, density, diversity, and distribution (4DS
strategy) information for AL and in a kernel function (Responsibility Weighted
Mahalanobis kernel) for SVM. The approach fuses generative and discriminative
modeling techniques. With 20 benchmark data sets and with the MNIST data set it
is shown that our new solution yields significantly better results than
state-of-the-art methods.
Civique: Using Social Media to Detect Urban Emergencies
Authors: Diptesh Kanojia, Vishwajeet Kumar, Krithi Ramamritham
Date: 2016-10-14 00:00:00

We present the Civique system for emergency detection in urban areas by
monitoring micro blogs like Tweets. The system detects emergency related
events, and classifies them into appropriate categories like "fire",
"accident", "earthquake", etc. We demonstrate our ideas by classifying Twitter
posts in real time, visualizing the ongoing event on a map interface and
alerting users with options to contact relevant authorities, both online and
offline. We evaluate our classifiers for both the steps, i.e., emergency
detection and categorization, and obtain F-scores exceeding 70% and 90%,
respectively. We demonstrate Civique using a web interface and on an Android
application, in realtime, and show its use for both tweet detection and
visualization.
Aboveground biomass mapping in French Guiana by combining remote sensing, forest inventories and environmental data
Authors: Ibrahim Fayad, Nicolas Baghdadi, Stéphane Guitet, Jean-Stéphane Bailly, Bruno Hérault, Valéry Gond, Mahmoud Hajj, Dinh Ho Tong Minh
Date: 2016-10-14 00:00:00
Tasks: regression

Mapping forest aboveground biomass (AGB) has become an important task,
particularly for the reporting of carbon stocks and changes. AGB can be mapped
using synthetic aperture radar data (SAR) or passive optical data. However,
these data are insensitive to high AGB levels (\textgreater{}150 Mg/ha, and
\textgreater{}300 Mg/ha for P-band), which are commonly found in tropical
forests. Studies have mapped the rough variations in AGB by combining optical
and environmental data at regional and global scales. Nevertheless, these maps
cannot represent local variations in AGB in tropical forests. In this paper, we
hypothesize that the problem of misrepresenting local variations in AGB and AGB
estimation with good precision occurs because of both methodological limits
(signal saturation or dilution bias) and a lack of adequate calibration data in
this range of AGB values. We test this hypothesis by developing a calibrated
regression model to predict variations in high AGB values (mean
\textgreater{}300 Mg/ha) in French Guiana by a methodological approach for
spatial extrapolation with data from the optical geoscience laser altimeter
system (GLAS), forest inventories, radar, optics, and environmental variables
for spatial inter-and extrapolation. Given their higher point count, GLAS data
allow a wider coverage of AGB values. We find that the metrics from GLAS
footprints are correlated with field AGB estimations (R 2 =0.54, RMSE=48.3
Mg/ha) with no bias for high values. First, predictive models, including
remote-sensing, environmental variables and spatial correlation functions,
allow us to obtain "wall-to-wall" AGB maps over French Guiana with an RMSE for
the in situ AGB estimates of ~51 Mg/ha and R${}^2$=0.48 at a 1-km grid size. We
conclude that a calibrated regression model based on GLAS with dependent
environmental data can produce good AGB predictions even for high AGB values if
the calibration data fit the AGB range. We also demonstrate that small temporal
and spatial mismatches between field data and GLAS footprints are not a problem
for regional and global calibrated regression models because field data aim to
predict large and deep tendencies in AGB variations from environmental
gradients and do not aim to represent high but stochastic and temporally
limited variations from forest dynamics. Thus, we advocate including a greater
variety of data, even if less precise and shifted, to better represent high AGB
values in global models and to improve the fitting of these models for high
values.