pwc-archive/papers-with-abstracts huggingface dataset:
StruClus: Structural Clustering of Large-Scale Graph Databases
Authors: Till Schäfer, Petra Mutzel
Date: 2016-09-28 00:00:00
Tasks: Clustering

We present a structural clustering algorithm for large-scale datasets of
small labeled graphs, utilizing a frequent subgraph sampling strategy. A set of
representatives provides an intuitive description of each cluster, supports the
clustering process, and helps to interpret the clustering results. The
projection-based nature of the clustering approach allows us to bypass
dimensionality and feature extraction problems that arise in the context of
graph datasets reduced to pairwise distances or feature vectors. While
achieving high quality and (human) interpretable clusterings, the runtime of
the algorithm only grows linearly with the number of graphs. Furthermore, the
approach is easy to parallelize and therefore suitable for very large datasets.
Our extensive experimental evaluation on synthetic and real world datasets
demonstrates the superiority of our approach over existing structural and
subspace clustering algorithms, both, from a runtime and quality point of view.
Variational Autoencoder for Deep Learning of Images, Labels and Captions
Authors: Yunchen Pu, Zhe Gan, Ricardo Henao, Xin Yuan, Chunyuan Li, Andrew Stevens, Lawrence Carin
Date: 2016-09-28 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Decoder, Deep Learning

A novel variational autoencoder is developed to model images, as well as
associated labels or captions. The Deep Generative Deconvolutional Network
(DGDN) is used as a decoder of the latent image features, and a deep
Convolutional Neural Network (CNN) is used as an image encoder; the CNN is used
to approximate a distribution for the latent DGDN features/code. The latent
code is also linked to generative models for labels (Bayesian support vector
machine) or captions (recurrent neural network). When predicting a
label/caption for a new image at test, averaging is performed across the
distribution of latent codes; this is computationally efficient as a
consequence of the learned CNN-based encoder. Since the framework is capable of
modeling the image in the presence/absence of associated labels/captions, a new
semi-supervised setting is manifested for CNN learning with images; the
framework even allows unsupervised CNN learning, based on images alone.
Graph Based Convolutional Neural Network
Authors: Michael Edwards, Xianghua Xie
Date: 2016-09-28 00:00:00
Tasks: BIG-bench Machine Learning, General Classification, image-classification, Image Classification

The benefit of localized features within the regular domain has given rise to
the use of Convolutional Neural Networks (CNNs) in machine learning, with great
proficiency in the image classification. The use of CNNs becomes problematic
within the irregular spatial domain due to design and convolution of a kernel
filter being non-trivial. One solution to this problem is to utilize graph
signal processing techniques and the convolution theorem to perform
convolutions on the graph of the irregular domain to obtain feature map
responses to learnt filters. We propose graph convolution and pooling operators
analogous to those in the regular domain. We also provide gradient calculations
on the input data and spectral filters, which allow for the deep learning of an
irregular spatial domain problem. Signal filters take the form of spectral
multipliers, applying convolution in the graph spectral domain. Applying smooth
multipliers results in localized convolutions in the spatial domain, with
smoother multipliers providing sharper feature maps. Algebraic Multigrid is
presented as a graph pooling method, reducing the resolution of the graph
through agglomeration of nodes between layers of the network. Evaluation of
performance on the MNIST digit classification problem in both the regular and
irregular domain is presented, with comparison drawn to standard CNN. The
proposed graph CNN provides a deep learning method for the irregular domains
present in the machine learning community, obtaining 94.23% on the regular
grid, and 94.96% on a spatially irregular subsampled MNIST.
Asymptotic and finite-sample properties of estimators based on stochastic gradients
Authors: Panos Toulis, Edoardo M. Airoldi
Date: 2014-08-13 00:00:00
Tasks: parameter estimation

Stochastic gradient descent procedures have gained popularity for parameter
estimation from large data sets. However, their statistical properties are not
well understood, in theory. And in practice, avoiding numerical instability
requires careful tuning of key parameters. Here, we introduce implicit
stochastic gradient descent procedures, which involve parameter updates that
are implicitly defined. Intuitively, implicit updates shrink standard
stochastic gradient descent updates. The amount of shrinkage depends on the
observed Fisher information matrix, which does not need to be explicitly
computed; thus, implicit procedures increase stability without increasing the
computational burden. Our theoretical analysis provides the first full
characterization of the asymptotic behavior of both standard and implicit
stochastic gradient descent-based estimators, including finite-sample error
bounds. Importantly, analytical expressions for the variances of these
stochastic gradient-based estimators reveal their exact loss of efficiency. We
also develop new algorithms to compute implicit stochastic gradient
descent-based estimators for generalized linear models, Cox proportional
hazards, M-estimators, in practice, and perform extensive experiments. Our
results suggest that implicit stochastic gradient descent procedures are poised
to become a workhorse for approximate inference from large data sets
Whole-brain substitute CT generation using Markov random field mixture models
Authors: Anders Hildeman, David Bolin, Jonas Wallin, Adam Johansson, Tufve Nyholm, Thomas Asklund, Jun Yu
Date: 2016-07-07 00:00:00
Tasks: Computational Efficiency, Computed Tomography (CT), parameter estimation

Computed tomography (CT) equivalent information is needed for attenuation
correction in PET imaging and for dose planning in radiotherapy. Prior work has
shown that Gaussian mixture models can be used to generate a substitute CT
(s-CT) image from a specific set of MRI modalities. This work introduces a more
flexible class of mixture models for s-CT generation, that incorporates spatial
dependency in the data through a Markov random field prior on the latent field
of class memberships associated with a mixture model. Furthermore, the mixture
distributions are extended from Gaussian to normal inverse Gaussian (NIG),
allowing heavier tails and skewness. The amount of data needed to train a model
for s-CT generation is of the order of 100 million voxels. The computational
efficiency of the parameter estimation and prediction methods are hence
paramount, especially when spatial dependency is included in the models. A
stochastic Expectation Maximization (EM) gradient algorithm is proposed in
order to tackle this challenge. The advantages of the spatial model and NIG
distributions are evaluated with a cross-validation study based on data from 14
patients. The study show that the proposed model enhances the predictive
quality of the s-CT images by reducing the mean absolute error with 17.9%.
Also, the distribution of CT values conditioned on the MR images are better
explained by the proposed model as evaluated using continuous ranked
probability scores.
A Discriminative Framework for Anomaly Detection in Large Videos
Authors: Allison Del Giorno, J. Andrew Bagnell, Martial Hebert
Date: 2016-09-28 00:00:00
Tasks: Anomaly Detection, Density Estimation

We address an anomaly detection setting in which training sequences are
unavailable and anomalies are scored independently of temporal ordering.
Current algorithms in anomaly detection are based on the classical density
estimation approach of learning high-dimensional models and finding
low-probability events. These algorithms are sensitive to the order in which
anomalies appear and require either training data or early context assumptions
that do not hold for longer, more complex videos. By defining anomalies as
examples that can be distinguished from other examples in the same video, our
definition inspires a shift in approaches from classical density estimation to
simple discriminative learning. Our contributions include a novel framework for
anomaly detection that is (1) independent of temporal ordering of anomalies,
and (2) unsupervised, requiring no separate training sequences. We show that
our algorithm can achieve state-of-the-art results even when we adjust the
setting by removing training sequences from standard datasets.
Multiplicative weights, equalizers, and P=PPAD
Authors: Ioannis Avramopoulos
Date: 2016-09-28 00:00:00

We show that, by using multiplicative weights in a game-theoretic thought experiment (and an important convexity result on the composition of multiplicative weights with the relative entropy function), a symmetric bimatrix game (that is, a bimatrix matrix wherein the payoff matrix of each player is the transpose of the payoff matrix of the other) either has an interior symmetric equilibrium or there is a pure strategy that is weakly dominated by some mixed strategy. Weakly dominated pure strategies can be detected and eliminated in polynomial time by solving a linear program. Furthermore, interior symmetric equilibria are a special case of a more general notion, namely, that of an "equalizer," which can also be computed efficiently in polynomial time by solving a linear program. An elegant "symmetrization method" of bimatrix games [Jurg et al., 1992] and the well-known PPAD-completeness results on equilibrium computation in bimatrix games [Daskalakis et al., 2009, Chen et al., 2009] imply then the compelling P = PPAD.
SemanticFusion: Dense 3D Semantic Mapping with Convolutional Neural Networks
Authors: John McCormac, Ankur Handa, Andrew Davison, Stefan Leutenegger
Date: 2016-09-16 00:00:00

Ever more robust, accurate and detailed mapping using visual sensing has
proven to be an enabling factor for mobile robots across a wide variety of
applications. For the next level of robot intelligence and intuitive user
interaction, maps need extend beyond geometry and appearence - they need to
contain semantics. We address this challenge by combining Convolutional Neural
Networks (CNNs) and a state of the art dense Simultaneous Localisation and
Mapping (SLAM) system, ElasticFusion, which provides long-term dense
correspondence between frames of indoor RGB-D video even during loopy scanning
trajectories. These correspondences allow the CNN's semantic predictions from
multiple view points to be probabilistically fused into a map. This not only
produces a useful semantic 3D map, but we also show on the NYUv2 dataset that
fusing multiple predictions leads to an improvement even in the 2D semantic
labelling over baseline single frame predictions. We also show that for a
smaller reconstruction dataset with larger variation in prediction viewpoint,
the improvement over single frame segmentation increases. Our system is
efficient enough to allow real-time interactive use at frame-rates of
approximately 25Hz.
Statistical and computational trade-offs in estimation of sparse principal components
Authors: Tengyao Wang, Quentin Berthet, Richard J. Samworth
Date: 2014-08-22 00:00:00
Tasks: Computational Efficiency, Dimensionality Reduction

In recent years, sparse principal component analysis has emerged as an
extremely popular dimension reduction technique for high-dimensional data. The
theoretical challenge, in the simplest case, is to estimate the leading
eigenvector of a population covariance matrix under the assumption that this
eigenvector is sparse. An impressive range of estimators have been proposed;
some of these are fast to compute, while others are known to achieve the
minimax optimal rate over certain Gaussian or sub-Gaussian classes. In this
paper, we show that, under a widely-believed assumption from computational
complexity theory, there is a fundamental trade-off between statistical and
computational performance in this problem. More precisely, working with new,
larger classes satisfying a restricted covariance concentration condition, we
show that there is an effective sample size regime in which no randomised
polynomial time algorithm can achieve the minimax optimal rate. We also study
the theoretical performance of a (polynomial time) variant of the well-known
semidefinite relaxation estimator, revealing a subtle interplay between
statistical and computational efficiency.
Learning zeroth class dictionary for human action recognition
Authors: Jia-xin Cai, Xin Tang, Lifang Zhang, Guocan Feng
Date: 2016-03-13 00:00:00
Tasks: Action Recognition, Dictionary Learning, Temporal Action Localization

In this paper, a discriminative two-phase dictionary learning framework is
proposed for classifying human action by sparse shape representations, in which
the first-phase dictionary is learned on the selected discriminative frames and
the second-phase dictionary is built for recognition using reconstruction
errors of the first-phase dictionary as input features. We propose a "zeroth
class" trick for detecting undiscriminating frames of the test video and
eliminating them before voting on the action categories. Experimental results
on benchmarks demonstrate the effectiveness of our method.
Statistical analysis of latent generalized correlation matrix estimation in transelliptical distribution
Authors: Fang Han, Han Liu
Date: 2013-05-29 00:00:00

Correlation matrices play a key role in many multivariate methods (e.g.,
graphical model estimation and factor analysis). The current state-of-the-art
in estimating large correlation matrices focuses on the use of Pearson's sample
correlation matrix. Although Pearson's sample correlation matrix enjoys various
good properties under Gaussian models, it is not an effective estimator when
facing heavy-tailed distributions. As a robust alternative, Han and Liu [J. Am.
Stat. Assoc. 109 (2015) 275-287] advocated the use of a transformed version of
the Kendall's tau sample correlation matrix in estimating high dimensional
latent generalized correlation matrix under the transelliptical distribution
family (or elliptical copula). The transelliptical family assumes that after
unspecified marginal monotone transformations, the data follow an elliptical
distribution. In this paper, we study the theoretical properties of the
Kendall's tau sample correlation matrix and its transformed version proposed in
Han and Liu [J. Am. Stat. Assoc. 109 (2015) 275-287] for estimating the
population Kendall's tau correlation matrix and the latent Pearson's
correlation matrix under both spectral and restricted spectral norms. With
regard to the spectral norm, we highlight the role of "effective rank" in
quantifying the rate of convergence. With regard to the restricted spectral
norm, we for the first time present a "sign sub-Gaussian condition" which is
sufficient to guarantee that the rank-based correlation matrix estimator
attains the fast rate of convergence. In both cases, we do not need any moment
condition.
Approachability of convex sets in generalized quitting games
Authors: János Flesch, Rida Laraki, Vianney Perchet
Date: 2016-09-28 00:00:00

We consider Blackwell approachability, a very powerful and geometric tool in
game theory, used for example to design strategies of the uninformed player in
repeated games with incomplete information. We extend this theory to
"generalized quitting games" , a class of repeated stochastic games in which
each player may have quitting actions, such as the Big-Match. We provide three
simple geometric and strongly related conditions for the weak approachability
of a convex target set. The first is sufficient: it guarantees that, for any
fixed horizon, a player has a strategy ensuring that the expected time-average
payoff vector converges to the target set as horizon goes to infinity. The
third is necessary: if it is not satisfied, the opponent can weakly exclude the
target set. In the special case where only the approaching player can quit the
game (Big-Match of type I), the three conditions are equivalent and coincide
with Blackwell's condition. Consequently, we obtain a full characterization and
prove that the game is weakly determined-every convex set is either weakly
approachable or weakly excludable. In games where only the opponent can quit
(Big-Match of type II), none of our conditions is both sufficient and necessary
for weak approachability. We provide a continuous time sufficient condition
using techniques coming from differential games, and show its usefulness in
practice, in the spirit of Vieille's seminal work for weak
approachability.Finally, we study uniform approachability where the strategy
should not depend on the horizon and demonstrate that, in contrast with
classical Blackwell approacha-bility for convex sets, weak approachability does
not imply uniform approachability.
Towards the effectiveness of Deep Convolutional Neural Network based Fast Random Forest Classifier
Authors: Mrutyunjaya Panda
Date: 2016-09-28 00:00:00
Tasks: BIG-bench Machine Learning, feature selection, Image Segmentation, Semantic Segmentation

Deep Learning is considered to be a quite young in the area of machine
learning research, found its effectiveness in dealing complex yet high
dimensional dataset that includes but limited to images, text and speech etc.
with multiple levels of representation and abstraction. As there are a plethora
of research on these datasets by various researchers , a win over them needs
lots of attention. Careful setting of Deep learning parameters is of paramount
importance in order to avoid the overfitting unlike conventional methods with
limited parameter settings. Deep Convolutional neural network (DCNN) with
multiple layers of compositions and appropriate settings might be is an
efficient machine learning method that can outperform the conventional methods
in a great way. However, due to its slow adoption in learning, there are also
always a chance of overfitting during feature selection process, which can be
addressed by employing a regularization method called dropout. Fast Random
Forest (FRF) is a powerful ensemble classifier especially when the datasets are
noisy and when the number of attributes is large in comparison to the number of
instances, as is the case of Bioinformatics datasets. Several publicly
available Bioinformatics dataset, Handwritten digits recognition and Image
segmentation dataset are considered for evaluation of the proposed approach.
The excellent performance obtained by the proposed DCNN based feature selection
with FRF classifier on high dimensional datasets makes it a fast and accurate
classifier in comparison the state-of-the-art.
Hierarchical Memory Networks for Answer Selection on Unknown Words
Authors: Jiaming Xu, Jing Shi, Yiqun Yao, Suncong Zheng, Bo Xu
Date: 2016-09-28 00:00:00
Proceeding: COLING 2016 12
Tasks: Answer Selection, Question Answering, Sentence

Recently, end-to-end memory networks have shown promising results on Question
Answering task, which encode the past facts into an explicit memory and perform
reasoning ability by making multiple computational steps on the memory.
However, memory networks conduct the reasoning on sentence-level memory to
output coarse semantic vectors and do not further take any attention mechanism
to focus on words, which may lead to the model lose some detail information,
especially when the answers are rare or unknown words. In this paper, we
propose a novel Hierarchical Memory Networks, dubbed HMN. First, we encode the
past facts into sentence-level memory and word-level memory respectively. Then,
(k)-max pooling is exploited following reasoning module on the sentence-level
memory to sample the (k) most relevant sentences to a question and feed these
sentences into attention mechanism on the word-level memory to focus the words
in the selected sentences. Finally, the prediction is jointly learned over the
outputs of the sentence-level reasoning module and the word-level attention
mechanism. The experimental results demonstrate that our approach successfully
conducts answer selection on unknown words and achieves a better performance
than memory networks.
Learning Latent Local Conversation Modes for Predicting Community Endorsement in Online Discussions
Authors: Hao Fang, Hao Cheng, Mari Ostendorf
Date: 2016-08-16 00:00:00

Many social media platforms offer a mechanism for readers to react to
comments, both positively and negatively, which in aggregate can be thought of
as community endorsement. This paper addresses the problem of predicting
community endorsement in online discussions, leveraging both the participant
response structure and the text of the comment. The different types of features
are integrated in a neural network that uses a novel architecture to learn
latent modes of discussion structure that perform as well as deep neural
networks but are more interpretable. In addition, the latent modes can be used
to weight text features thereby improving prediction accuracy.
Predictive Coarse-Graining
Authors: Markus Schöberl, Nicholas Zabaras, Phaedon-Stelios Koutsourelakis
Date: 2016-05-26 00:00:00
Tasks: Model Selection

We propose a data-driven, coarse-graining formulation in the context of
equilibrium statistical mechanics. In contrast to existing techniques which are
based on a fine-to-coarse map, we adopt the opposite strategy by prescribing a
probabilistic coarse-to-fine map. This corresponds to a directed probabilistic
model where the coarse variables play the role of latent generators of the fine
scale (all-atom) data. From an information-theoretic perspective, the framework
proposed provides an improvement upon the relative entropy method and is
capable of quantifying the uncertainty due to the information loss that
unavoidably takes place during the CG process. Furthermore, it can be readily
extended to a fully Bayesian model where various sources of uncertainties are
reflected in the posterior of the model parameters. The latter can be used to
produce not only point estimates of fine-scale reconstructions or macroscopic
observables, but more importantly, predictive posterior distributions on these
quantities. Predictive posterior distributions reflect the confidence of the
model as a function of the amount of data and the level of coarse-graining. The
issues of model complexity and model selection are seamlessly addressed by
employing a hierarchical prior that favors the discovery of sparse solutions,
revealing the most prominent features in the coarse-grained model. A flexible
and parallelizable Monte Carlo - Expectation-Maximization (MC-EM) scheme is
proposed for carrying out inference and learning tasks. A comparative
assessment of the proposed methodology is presented for a lattice spin system
and the SPC/E water model.
Equation Parsing: Mapping Sentences to Grounded Equations
Authors: Subhro Roy, Shyam Upadhyay, Dan Roth
Date: 2016-09-28 00:00:00
Tasks: Sentence

Identifying mathematical relations expressed in text is essential to
understanding a broad range of natural language text from election reports, to
financial news, to sport commentaries to mathematical word problems. This paper
focuses on identifying and understanding mathematical relations described
within a single sentence. We introduce the problem of Equation Parsing -- given
a sentence, identify noun phrases which represent variables, and generate the
mathematical equation expressing the relation described in the sentence. We
introduce the notion of projective equation parsing and provide an efficient
algorithm to parse text to projective equations. Our system makes use of a high
precision lexicon of mathematical expressions and a pipeline of structured
predictors, and generates correct equations in $70\%$ of the cases. In $60\%$
of the time, it also identifies the correct noun phrase $\rightarrow$ variables
mapping, significantly outperforming baselines. We also release a new annotated
dataset for task evaluation.