pwc-archive/papers-with-abstracts huggingface dataset:
Asymptotic normality and optimalities in estimation of large Gaussian graphical models
Authors: Zhao Ren, Tingni Sun, Cun-Hui Zhang, Harrison H. Zhou
Date: 2013-09-24 00:00:00
Tasks: LEMMA

The Gaussian graphical model, a popular paradigm for studying relationship
among variables in a wide range of applications, has attracted great attention
in recent years. This paper considers a fundamental question: When is it
possible to estimate low-dimensional parameters at parametric square-root rate
in a large Gaussian graphical model? A novel regression approach is proposed to
obtain asymptotically efficient estimation of each entry of a precision matrix
under a sparseness condition relative to the sample size. When the precision
matrix is not sufficiently sparse, or equivalently the sample size is not
sufficiently large, a lower bound is established to show that it is no longer
possible to achieve the parametric rate in the estimation of each entry. This
lower bound result, which provides an answer to the delicate sample size
question, is established with a novel construction of a subset of sparse
precision matrices in an application of Le Cam's lemma. Moreover, the proposed
estimator is proven to have optimal convergence rate when the parametric rate
cannot be achieved, under a minimal sample requirement. The proposed estimator
is applied to test the presence of an edge in the Gaussian graphical model or
to recover the support of the entire model, to obtain adaptive rate-optimal
estimation of the entire precision matrix as measured by the matrix $\ell_q$
operator norm and to make inference in latent variables in the graphical model.
All of this is achieved under a sparsity condition on the precision matrix and
a side condition on the range of its spectrum. This significantly relaxes the
commonly imposed uniform signal strength condition on the precision matrix,
irrepresentability condition on the Hessian tensor operator of the covariance
matrix or the $\ell_1$ constraint on the precision matrix. Numerical results
confirm our theoretical findings. The ROC curve of the proposed algorithm,
Asymptotic Normal Thresholding (ANT), for support recovery significantly
outperforms that of the popular GLasso algorithm.
Compound Rank-k Projections for Bilinear Analysis
Authors: Xiaojun Chang, Feiping Nie, Sen Wang, Yi Yang, Xiaofang Zhou, Chengqi Zhang
Date: 2014-11-23 00:00:00

In many real-world applications, data are represented by matrices or
high-order tensors. Despite the promising performance, the existing
two-dimensional discriminant analysis algorithms employ a single projection
model to exploit the discriminant information for projection, making the model
less flexible. In this paper, we propose a novel Compound Rank-k Projection
(CRP) algorithm for bilinear analysis. CRP deals with matrices directly without
transforming them into vectors, and it therefore preserves the correlations
within the matrix and decreases the computation complexity. Different from the
existing two dimensional discriminant analysis algorithms, objective function
values of CRP increase monotonically.In addition, CRP utilizes multiple rank-k
projection models to enable a larger search space in which the optimal solution
can be found. In this way, the discriminant ability is enhanced.
Hyperspectral Image Classification and Clutter Detection via Multiple Structural Embeddings and Dimension Reductions
Authors: Alexandros-Stavros Iliopoulos, Tiancheng Liu, Xiaobai Sun
Date: 2015-06-03 00:00:00
Tasks: Attribute, General Classification, Hyperspectral Image Classification, image-classification, Image Classification

We present a new and effective approach for Hyperspectral Image (HSI)
classification and clutter detection, overcoming a few long-standing challenges
presented by HSI data characteristics. Residing in a high-dimensional spectral
attribute space, HSI data samples are known to be strongly correlated in their
spectral signatures, exhibit nonlinear structure due to several physical laws,
and contain uncertainty and noise from multiple sources. In the presented
approach, we generate an adaptive, structurally enriched representation
environment, and employ the locally linear embedding (LLE) in it. There are two
structure layers external to LLE. One is feature space embedding: the HSI data
attributes are embedded into a discriminatory feature space where
spatio-spectral coherence and distinctive structures are distilled and
exploited to mitigate various difficulties encountered in the native
hyperspectral attribute space. The other structure layer encloses the ranges of
algorithmic parameters for LLE and feature embedding, and supports a
multiplexing and integrating scheme for contending with multi-source
uncertainty. Experiments on two commonly used HSI datasets with a small number
of learning samples have rendered remarkably high-accuracy classification
results, as well as distinctive maps of detected clutter regions.
Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
Authors: Wesley Cowan, Junya Honda, Michael N. Katehakis
Date: 2015-04-22 00:00:00

Consider the problem of sampling sequentially from a finite number of $N \geq
2$ populations, specified by random variables $X^i_k$, $ i = 1,\ldots , N,$ and
$k = 1, 2, \ldots$; where $X^i_k$ denotes the outcome from population $i$ the
$k^{th}$ time it is sampled. It is assumed that for each fixed $i$,
  $\{ X^i_k \}_{k \geq 1}$ is a sequence of i.i.d. normal random variables,
with unknown mean $\mu_i$ and unknown variance $\sigma_i^2$.
  The objective is to have a policy $\pi$ for deciding from which of the $N$
populations to sample form at any time $n=1,2,\ldots$ so as to maximize the
expected sum of outcomes of $n$ samples or equivalently to minimize the regret
due to lack on information of the parameters $\mu_i$ and $\sigma_i^2$. In this
paper, we present a simple inflated sample mean (ISM) index policy that is
asymptotically optimal in the sense of Theorem 4 below. This resolves a
standing open problem from Burnetas and Katehakis (1996). Additionally, finite
horizon regret bounds are given.
CIDEr: Consensus-based Image Description Evaluation
Authors: Ramakrishna Vedantam, C. Lawrence Zitnick, Devi Parikh
Date: 2014-11-20 00:00:00
Proceeding: CVPR 2015 6
Tasks: Action Recognition, Attribute, Benchmarking, Image Captioning, Image Description, Sentence, Triplet

Automatically describing an image with a sentence is a long-standing
challenge in computer vision and natural language processing. Due to recent
progress in object detection, attribute classification, action recognition,
etc., there is renewed interest in this area. However, evaluating the quality
of descriptions has proven to be challenging. We propose a novel paradigm for
evaluating image descriptions that uses human consensus. This paradigm consists
of three main parts: a new triplet-based method of collecting human annotations
to measure consensus, a new automated metric (CIDEr) that captures consensus,
and two new datasets: PASCAL-50S and ABSTRACT-50S that contain 50 sentences
describing each image. Our simple metric captures human judgment of consensus
better than existing metrics across sentences generated by various sources. We
also evaluate five state-of-the-art image description approaches using this new
protocol and provide a benchmark for future comparisons. A version of CIDEr
named CIDEr-D is available as a part of MS COCO evaluation server to enable
systematic evaluation and benchmarking.
Bayesian Hierarchical Clustering with Exponential Family: Small-Variance Asymptotics and Reducibility
Authors: Juho Lee, Seungjin Choi
Date: 2015-01-29 00:00:00
Tasks: Clustering

Bayesian hierarchical clustering (BHC) is an agglomerative clustering method,
where a probabilistic model is defined and its marginal likelihoods are
evaluated to decide which clusters to merge. While BHC provides a few
advantages over traditional distance-based agglomerative clustering algorithms,
successive evaluation of marginal likelihoods and careful hyperparameter tuning
are cumbersome and limit the scalability. In this paper we relax BHC into a
non-probabilistic formulation, exploring small-variance asymptotics in
conjugate-exponential models. We develop a novel clustering algorithm, referred
to as relaxed BHC (RBHC), from the asymptotic limit of the BHC model that
exhibits the scalability of distance-based agglomerative clustering algorithms
as well as the flexibility of Bayesian nonparametric models. We also
investigate the reducibility of the dissimilarity measure emerged from the
asymptotic limit of the BHC model, allowing us to use scalable algorithms such
as the nearest neighbor chain algorithm. Numerical experiments on both
synthetic and real-world datasets demonstrate the validity and high performance
of our method.
Bilinear Random Projections for Locality-Sensitive Binary Codes
Authors: Saehoon Kim, Seungjin Choi
Date: 2015-06-03 00:00:00
Proceeding: CVPR 2015 6
Tasks: Quantization

Locality-sensitive hashing (LSH) is a popular data-independent indexing
method for approximate similarity search, where random projections followed by
quantization hash the points from the database so as to ensure that the
probability of collision is much higher for objects that are close to each
other than for those that are far apart. Most of high-dimensional visual
descriptors for images exhibit a natural matrix structure. When visual
descriptors are represented by high-dimensional feature vectors and long binary
codes are assigned, a random projection matrix requires expensive complexities
in both space and time. In this paper we analyze a bilinear random projection
method where feature matrices are transformed to binary codes by two smaller
random projection matrices. We base our theoretical analysis on extending
Raginsky and Lazebnik's result where random Fourier features are composed with
random binary quantizers to form locality sensitive binary codes. To this end,
we answer the following two questions: (1) whether a bilinear random projection
also yields similarity-preserving binary codes; (2) whether a bilinear random
projection yields performance gain or loss, compared to a large linear
projection. Regarding the first question, we present upper and lower bounds on
the expected Hamming distance between binary codes produced by bilinear random
projections. In regards to the second question, we analyze the upper and lower
bounds on covariance between two bits of binary codes, showing that the
correlation between two bits is small. Numerical experiments on MNIST and
Flickr45K datasets confirm the validity of our method.
Probabilistic Network Metrics: Variational Bayesian Network Centrality
Authors: Harold Soh
Date: 2014-09-15 00:00:00
Tasks: Gaussian Processes

Network metrics form a fundamental part of the network analysis toolbox. Used
to quantitatively measure different aspects of the network, these metrics can
give insights into the underlying network structure and function. In this work,
we connect network metrics to modern probabilistic machine learning. We focus
on the centrality metric, which is used a wide variety of applications from web
search to gene-analysis. First, we formulate an eigenvector-based Bayesian
centrality model for determining node importance. Compared to existing methods,
our probabilistic model allows for the assimilation of multiple edge weight
observations, the inclusion of priors and the extraction of uncertainties. To
enable tractable inference, we develop a variational lower bound (VBC) that is
demonstrated to be effective on a variety of networks (two synthetic and five
real-world graphs). We then bridge this model to sparse Gaussian processes. The
sparse variational Bayesian centrality Gaussian process (VBC-GP) learns a
mapping between node attributes to latent centrality and hence, is capable of
predicting centralities from node features and can potentially represent a
large number of nodes using only a limited number of inducing inputs.
Experiments show that the VBC-GP learns high-quality mappings and compares
favorably to a two-step baseline, i.e., a full GP trained on the node
attributes and pre-computed centralities. Finally, we present two case-studies
using the VBC-GP: first, to ascertain relevant features in a taxi transport
network and second, to distribute a limited number of vaccines to mitigate the
severity of a viral outbreak.
On bicluster aggregation and its benefits for enumerative solutions
Authors: Saullo Haniell Galvão de Oliveira, Rosana Veroneze, Fernando José Von Zuben
Date: 2015-06-02 00:00:00
Tasks: Clustering

Biclustering involves the simultaneous clustering of objects and their
attributes, thus defining local two-way clustering models. Recently, efficient
algorithms were conceived to enumerate all biclusters in real-valued datasets.
In this case, the solution composes a complete set of maximal and non-redundant
biclusters. However, the ability to enumerate biclusters revealed a challenging
scenario: in noisy datasets, each true bicluster may become highly fragmented
and with a high degree of overlapping. It prevents a direct analysis of the
obtained results. To revert the fragmentation, we propose here two approaches
for properly aggregating the whole set of enumerated biclusters: one based on
single linkage and the other directly exploring the rate of overlapping. Both
proposals were compared with each other and with the actual state-of-the-art in
several experiments, and they not only significantly reduced the number of
biclusters but also consistently increased the quality of the solution.
Quizz: Targeted crowdsourcing with a billion (potential) users
Authors: Panagiotis G. Ipeirotis, Evgeniy Gabrilovich
Date: 2015-06-02 00:00:00

We describe Quizz, a gamified crowdsourcing system that simultaneously
assesses the knowledge of users and acquires new knowledge from them. Quizz
operates by asking users to complete short quizzes on specific topics; as a
user answers the quiz questions, Quizz estimates the user's competence. To
acquire new knowledge, Quizz also incorporates questions for which we do not
have a known answer; the answers given by competent users provide useful
signals for selecting the correct answers for these questions. Quizz actively
tries to identify knowledgeable users on the Internet by running advertising
campaigns, effectively leveraging the targeting capabilities of existing,
publicly available, ad placement services. Quizz quantifies the contributions
of the users using information theory and sends feedback to the
advertisingsystem about each user. The feedback allows the ad targeting
mechanism to further optimize ad placement.
  Our experiments, which involve over ten thousand users, confirm that we can
crowdsource knowledge curation for niche and specialized topics, as the
advertising network can automatically identify users with the desired expertise
and interest in the given topic. We present controlled experiments that examine
the effect of various incentive mechanisms, highlighting the need for having
short-term rewards as goals, which incentivize the users to contribute.
Finally, our cost-quality analysis indicates that the cost of our approach is
below that of hiring workers through paid-crowdsourcing platforms, while
offering the additional advantage of giving access to billions of potential
users all over the planet, and being able to reach users with specialized
expertise that is not typically available through existing labor marketplaces.
Performing Bayesian Risk Aggregation using Discrete Approximation Algorithms with Graph Factorization
Authors: Peng Lin
Date: 2015-06-02 00:00:00

Risk aggregation is a popular method used to estimate the sum of a collection
of financial assets or events, where each asset or event is modelled as a
random variable. Applications, in the financial services industry, include
insurance, operational risk, stress testing, and sensitivity analysis, but the
problem is widely encountered in many other application domains. This thesis
has contributed two algorithms to perform Bayesian risk aggregation when model
exhibit hybrid dependency and high dimensional inter-dependency. The first
algorithm operates on a subset of the general problem, with an emphasis on
convolution problems, in the presence of continuous and discrete variables (so
called hybrid models) and the second algorithm offer a universal method for
general purpose inference over much wider classes of Bayesian Network models.
Multi-stage Multi-task feature learning via adaptive threshold
Authors: Yaru Fan, Yi-Lun Wang
Date: 2014-06-16 00:00:00
Tasks: feature selection

Multi-task feature learning aims to identity the shared features among tasks
to improve generalization. It has been shown that by minimizing non-convex
learning models, a better solution than the convex alternatives can be
obtained. Therefore, a non-convex model based on the capped-$\ell_{1},\ell_{1}$
regularization was proposed in \cite{Gong2013}, and a corresponding efficient
multi-stage multi-task feature learning algorithm (MSMTFL) was presented.
However, this algorithm harnesses a prescribed fixed threshold in the
definition of the capped-$\ell_{1},\ell_{1}$ regularization and the lack of
adaptivity might result in suboptimal performance. In this paper we propose to
employ an adaptive threshold in the capped-$\ell_{1},\ell_{1}$ regularized
formulation, where the corresponding variant of MSMTFL will incorporate an
additional component to adaptively determine the threshold value. This variant
is expected to achieve a better feature selection performance over the original
MSMTFL algorithm. In particular, the embedded adaptive threshold component
comes from our previously proposed iterative support detection (ISD) method
\cite{Wang2010}. Empirical studies on both synthetic and real-world data sets
demonstrate the effectiveness of this new variant over the original MSMTFL.
Combining Two And Three-Way Embeddings Models for Link Prediction in Knowledge Bases
Authors: Alberto Garcia-Duran, Antoine Bordes, Nicolas Usunier, Yves GRANDVALET
Date: 2015-06-02 00:00:00
Tasks: Knowledge Base Completion, Link Prediction

This paper tackles the problem of endogenous link prediction for Knowledge
Base completion. Knowledge Bases can be represented as directed graphs whose
nodes correspond to entities and edges to relationships. Previous attempts
either consist of powerful systems with high capacity to model complex
connectivity patterns, which unfortunately usually end up overfitting on rare
relationships, or in approaches that trade capacity for simplicity in order to
fairly model all relationships, frequent or not. In this paper, we propose
Tatec a happy medium obtained by complementing a high-capacity model with a
simpler one, both pre-trained separately and then combined. We present several
variants of this model with different kinds of regularization and combination
strategies and show that this approach outperforms existing methods on
different types of relationships by achieving state-of-the-art results on four
benchmarks of the literature.
Two step recovery of jointly sparse and low-rank matrices: theoretical guarantees
Authors: Sampurna Biswas, Sunrita Poddar, Soura Dasgupta, Raghuraman Mudumbai, Mathews Jacob
Date: 2014-12-05 00:00:00

We introduce a two step algorithm with theoretical guarantees to recover a
jointly sparse and low-rank matrix from undersampled measurements of its
columns. The algorithm first estimates the row subspace of the matrix using a
set of common measurements of the columns. In the second step, the subspace
aware recovery of the matrix is solved using a simple least square algorithm.
The results are verified in the context of recovering CINE data from
undersampled measurements; we obtain good recovery when the sampling conditions
are satisfied.
Subspace based low rank and joint sparse matrix recovery
Authors: Sampurna Biswas, Sunrita Poddar, Soura Dasgupta, Raghuraman Mudumbai, Mathews Jacob
Date: 2014-12-05 00:00:00
Tasks: Time Series, Time Series Analysis

We consider the recovery of a low rank and jointly sparse matrix from under
sampled measurements of its columns. This problem is highly relevant in the
recovery of dynamic MRI data with high spatio-temporal resolution, where each
column of the matrix corresponds to a frame in the image time series; the
matrix is highly low-rank since the frames are highly correlated. Similarly the
non-zero locations of the matrix in appropriate transform/frame domains (e.g.
wavelet, gradient) are roughly the same in different frame. The superset of the
support can be safely assumed to be jointly sparse. Unlike the classical
multiple measurement vector (MMV) setup that measures all the snapshots using
the same matrix, we consider each snapshot to be measured using a different
measurement matrix. We show that this approach reduces the total number of
measurements, especially when the rank of the matrix is much smaller than than
its sparsity. Our experiments in the context of dynamic imaging shows that this
approach is very useful in realizing free breathing cardiac MRI.
Discovering Valuable Items from Massive Data
Authors: Hastagiri P. Vanchinathan, Andreas Marfurt, Charles-Antoine Robelin, Donald Kossmann, Andreas Krause
Date: 2015-06-02 00:00:00
Tasks: Recommendation Systems

Suppose there is a large collection of items, each with an associated cost
and an inherent utility that is revealed only once we commit to selecting it.
Given a budget on the cumulative cost of the selected items, how can we pick a
subset of maximal value? This task generalizes several important problems such
as multi-arm bandits, active search and the knapsack problem. We present an
algorithm, GP-Select, which utilizes prior knowledge about similarity be- tween
items, expressed as a kernel function. GP-Select uses Gaussian process
prediction to balance exploration (estimating the unknown value of items) and
exploitation (selecting items of high value). We extend GP-Select to be able to
discover sets that simultaneously have high utility and are diverse. Our
preference for diversity can be specified as an arbitrary monotone submodular
function that quantifies the diminishing returns obtained when selecting
similar items. Furthermore, we exploit the structure of the model updates to
achieve an order of magnitude (up to 40X) speedup in our experiments without
resorting to approximations. We provide strong guarantees on the performance of
GP-Select and apply it to three real-world case studies of industrial
relevance: (1) Refreshing a repository of prices in a Global Distribution
System for the travel industry, (2) Identifying diverse, binding-affine
peptides in a vaccine de- sign task and (3) Maximizing clicks in a web-scale
recommender system by recommending items to users.