pwc-archive/papers-with-abstracts huggingface dataset:
Local and global asymptotic inference in smoothing spline models
Authors: Zuofeng Shang, Guang Cheng
Date: 2012-12-30 00:00:00
Tasks: Math, valid

This article studies local and global inference for smoothing spline
estimation in a unified asymptotic framework. We first introduce a new
technical tool called functional Bahadur representation, which significantly
generalizes the traditional Bahadur representation in parametric models, that
is, Bahadur [Ann. Inst. Statist. Math. 37 (1966) 577-580]. Equipped with this
tool, we develop four interconnected procedures for inference: (i) pointwise
confidence interval; (ii) local likelihood ratio testing; (iii) simultaneous
confidence band; (iv) global likelihood ratio testing. In particular, our
confidence intervals are proved to be asymptotically valid at any point in the
support, and they are shorter on average than the Bayesian confidence intervals
proposed by Wahba [J. R. Stat. Soc. Ser. B Stat. Methodol. 45 (1983) 133-150]
and Nychka [J. Amer. Statist. Assoc. 83 (1988) 1134-1143]. We also discuss a
version of the Wilks phenomenon arising from local/global likelihood ratio
testing. It is also worth noting that our simultaneous confidence bands are the
first ones applicable to general quasi-likelihood models. Furthermore, issues
relating to optimality and efficiency are carefully addressed. As a by-product,
we discover a surprising relationship between periodic and nonperiodic
smoothing splines in terms of inference.
A Novel Family of Adaptive Filtering Algorithms Based on The Logarithmic Cost
Authors: Muhammed O. Sayin, N. Denizcan Vanli, Suleyman S. Kozat
Date: 2013-11-26 00:00:00

We introduce a novel family of adaptive filtering algorithms based on a
relative logarithmic cost. The new family intrinsically combines the higher and
lower order measures of the error into a single continuous update based on the
error amount. We introduce important members of this family of algorithms such
as the least mean logarithmic square (LMLS) and least logarithmic absolute
difference (LLAD) algorithms that improve the convergence performance of the
conventional algorithms. However, our approach and analysis are generic such
that they cover other well-known cost functions as described in the paper. The
LMLS algorithm achieves comparable convergence performance with the least mean
fourth (LMF) algorithm and extends the stability bound on the step size. The
LLAD and least mean square (LMS) algorithms demonstrate similar convergence
performance in impulse-free noise environments while the LLAD algorithm is
robust against impulsive interferences and outperforms the sign algorithm (SA).
We analyze the transient, steady state and tracking performance of the
introduced algorithms and demonstrate the match of the theoretical analyzes and
simulation results. We show the extended stability bound of the LMLS algorithm
and analyze the robustness of the LLAD algorithm against impulsive
interferences. Finally, we demonstrate the performance of our algorithms in
different scenarios through numerical examples.
The asymptotics of ranking algorithms
Authors: John C. Duchi, Lester Mackey, Michael. I. Jordan
Date: 2012-04-07 00:00:00

We consider the predictive problem of supervised ranking, where the task is
to rank sets of candidate items returned in response to queries. Although there
exist statistical procedures that come with guarantees of consistency in this
setting, these procedures require that individuals provide a complete ranking
of all items, which is rarely feasible in practice. Instead, individuals
routinely provide partial preference information, such as pairwise comparisons
of items, and more practical approaches to ranking have aimed at modeling this
partial preference data directly. As we show, however, such an approach raises
serious theoretical challenges. Indeed, we demonstrate that many commonly used
surrogate losses for pairwise comparison data do not yield consistency;
surprisingly, we show inconsistency even in low-noise settings. With these
negative results as motivation, we present a new approach to supervised ranking
based on aggregation of partial preferences, and we develop $U$-statistic-based
empirical risk minimization procedures. We present an asymptotic analysis of
these new procedures, showing that they yield consistency results that parallel
those available for classification. We complement our theoretical results with
an experiment studying the new procedures in a large-scale web-ranking task.
On the Complexity and Approximation of Binary Evidence in Lifted Inference
Authors: Guy Van den Broeck, Adnan Darwiche
Date: 2013-11-26 00:00:00
Proceeding: NeurIPS 2013 12

Lifted inference algorithms exploit symmetries in probabilistic models to
speed up inference. They show impressive performance when calculating
unconditional probabilities in relational models, but often resort to
non-lifted inference when computing conditional probabilities. The reason is
that conditioning on evidence breaks many of the model's symmetries, which can
preempt standard lifting techniques. Recent theoretical results show, for
example, that conditioning on evidence which corresponds to binary relations is
#P-hard, suggesting that no lifting is to be expected in the worst case. In
this paper, we balance this negative result by identifying the Boolean rank of
the evidence as a key parameter for characterizing the complexity of
conditioning in lifted inference. In particular, we show that conditioning on
binary evidence with bounded Boolean rank is efficient. This opens up the
possibility of approximating evidence by a low-rank Boolean matrix
factorization, which we investigate both theoretically and empirically.
Gradient Magnitude Similarity Deviation: A Highly Efficient Perceptual Image Quality Index
Authors: Wufeng Xue, Lei Zhang, Xuanqin Mou, Alan C. Bovik
Date: 2013-08-14 00:00:00
Tasks: Full reference image quality assessment, Image Compression, Image Quality Assessment, Image Restoration, Prediction

It is an important task to faithfully evaluate the perceptual quality of
output images in many applications such as image compression, image restoration
and multimedia streaming. A good image quality assessment (IQA) model should
not only deliver high quality prediction accuracy but also be computationally
efficient. The efficiency of IQA metrics is becoming particularly important due
to the increasing proliferation of high-volume visual data in high-speed
networks. We present a new effective and efficient IQA model, called gradient
magnitude similarity deviation (GMSD). The image gradients are sensitive to
image distortions, while different local structures in a distorted image suffer
different degrees of degradations. This motivates us to explore the use of
global variation of gradient based local quality map for overall image quality
prediction. We find that the pixel-wise gradient magnitude similarity (GMS)
between the reference and distorted images combined with a novel pooling
strategy the standard deviation of the GMS map can predict accurately
perceptual image quality. The resulting GMSD algorithm is much faster than most
state-of-the-art IQA methods, and delivers highly competitive prediction
accuracy.
Discriminative Density-ratio Estimation
Authors: Yun-Qian Miao, Ahmed K. Farahat, Mohamed S. Kamel
Date: 2013-11-18 00:00:00
Tasks: Density Ratio Estimation, General Classification, regression

The covariate shift is a challenging problem in supervised learning that
results from the discrepancy between the training and test distributions. An
effective approach which recently drew a considerable attention in the research
community is to reweight the training samples to minimize that discrepancy. In
specific, many methods are based on developing Density-ratio (DR) estimation
techniques that apply to both regression and classification problems. Although
these methods work well for regression problems, their performance on
classification problems is not satisfactory. This is due to a key observation
that these methods focus on matching the sample marginal distributions without
paying attention to preserving the separation between classes in the reweighted
space. In this paper, we propose a novel method for Discriminative
Density-ratio (DDR) estimation that addresses the aforementioned problem and
aims at estimating the density-ratio of joint distributions in a class-wise
manner. The proposed algorithm is an iterative procedure that alternates
between estimating the class information for the test data and estimating new
density ratio for each class. To incorporate the estimated class information of
the test data, a soft matching technique is proposed. In addition, we employ an
effective criterion which adopts mutual information as an indicator to stop the
iterative procedure while resulting in a decision boundary that lies in a
sparse region. Experiments on synthetic and benchmark datasets demonstrate the
superiority of the proposed method in terms of both accuracy and robustness.
Universal Codes from Switching Strategies
Authors: Wouter M. Koolen, Steven de Rooij
Date: 2013-11-26 00:00:00
Tasks: LEMMA, Prediction, Time Series, Time Series Analysis

We discuss algorithms for combining sequential prediction strategies, a task
which can be viewed as a natural generalisation of the concept of universal
coding. We describe a graphical language based on Hidden Markov Models for
defining prediction strategies, and we provide both existing and new models as
examples. The models include efficient, parameterless models for switching
between the input strategies over time, including a model for the case where
switches tend to occur in clusters, and finally a new model for the scenario
where the prediction strategies have a known relationship, and where jumps are
typically between strongly related ones. This last model is relevant for coding
time series data where parameter drift is expected. As theoretical ontributions
we introduce an interpolation construction that is useful in the development
and analysis of new algorithms, and we establish a new sophisticated lemma for
analysing the individual sequence regret of parameterised models.
A Blockwise Descent Algorithm for Group-penalized Multiresponse and Multinomial Regression
Authors: Noah Simon, Jerome Friedman, Trevor Hastie
Date: 2013-11-26 00:00:00
Tasks: regression

In this paper we purpose a blockwise descent algorithm for group-penalized
multiresponse regression. Using a quasi-newton framework we extend this to
group-penalized multinomial regression. We give a publicly available
implementation for these in R, and compare the speed of this algorithm to a
competing algorithm --- we show that our implementation is an order of
magnitude faster than its competitor, and can solve gene-expression-sized
problems in real time.
Are all training examples equally valuable?
Authors: Agata Lapedriza, Hamed Pirsiavash, Zoya Bylinskii, Antonio Torralba
Date: 2013-11-25 00:00:00
Tasks: All

When learning a new concept, not all training examples may prove equally
useful for training: some may have higher or lower training value than others.
The goal of this paper is to bring to the attention of the vision community the
following considerations: (1) some examples are better than others for training
detectors or classifiers, and (2) in the presence of better examples, some
examples may negatively impact performance and removing them may be beneficial.
In this paper, we propose an approach for measuring the training value of an
example, and use it for ranking and greedily sorting examples. We test our
methods on different vision tasks, models, datasets and classifiers. Our
experiments show that the performance of current state-of-the-art detectors and
classifiers can be improved when training on a subset, rather than the whole
training set.
Parallel Coordinate Descent Methods for Big Data Optimization
Authors: Peter Richtárik, Martin Takáč
Date: 2012-12-04 00:00:00

In this work we show that randomized (block) coordinate descent methods can
be accelerated by parallelization when applied to the problem of minimizing the
sum of a partially separable smooth convex function and a simple separable
convex function. The theoretical speedup, as compared to the serial method, and
referring to the number of iterations needed to approximately solve the problem
with high probability, is a simple expression depending on the number of
parallel processors and a natural and easily computable measure of separability
of the smooth component of the objective function. In the worst case, when no
degree of separability is present, there may be no speedup; in the best case,
when the problem is separable, the speedup is equal to the number of
processors. Our analysis also works in the mode when the number of blocks being
updated at each iteration is random, which allows for modeling situations with
busy or unreliable processors. We show that our algorithm is able to solve a
LASSO problem involving a matrix with 20 billion nonzeros in 2 hours on a large
memory node with 24 cores.
On Recursive Edit Distance Kernels with Application to Time Series Classification
Authors: Pierre-François Marteau, Sylvie Gibet
Date: 2010-05-27 00:00:00
Tasks: General Classification, Time Series, Time Series Analysis, Time Series Classification

This paper proposes some extensions to the work on kernels dedicated to
string or time series global alignment based on the aggregation of scores
obtained by local alignments. The extensions we propose allow to construct,
from classical recursive definition of elastic distances, recursive edit
distance (or time-warp) kernels that are positive definite if some sufficient
conditions are satisfied. The sufficient conditions we end-up with are original
and weaker than those proposed in earlier works, although a recursive
regularizing term is required to get the proof of the positive definiteness as
a direct consequence of the Haussler's convolution theorem. The classification
experiment we conducted on three classical time warp distances (two of which
being metrics), using Support Vector Machine classifier, leads to conclude
that, when the pairwise distance matrix obtained from the training data is
\textit{far} from definiteness, the positive definite recursive elastic kernels
outperform in general the distance substituting kernels for the classical
elastic distances we have tested.
Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching
Authors: Marcelo Fiori, Pablo Sprechmann, Joshua Vogelstein, Pablo Musé, Guillermo Sapiro
Date: 2013-11-25 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Collaborative Inference, Graph Matching

Graph matching is a challenging problem with very important applications in a
wide range of fields, from image and video analysis to biological and
biomedical problems. We propose a robust graph matching algorithm inspired in
sparsity-related techniques. We cast the problem, resembling group or
collaborative sparsity formulations, as a non-smooth convex optimization
problem that can be efficiently solved using augmented Lagrangian techniques.
The method can deal with weighted or unweighted graphs, as well as multimodal
data, where different graphs represent different types of data. The proposed
approach is also naturally integrated with collaborative graph inference
techniques, solving general network inference problems where the observed
variables, possibly coming from different modalities, are not in
correspondence. The algorithm is tested and compared with state-of-the-art
graph matching techniques in both synthetic and real graphs. We also present
results on multimodal graphs and applications to collaborative inference of
brain connectivity from alignment-free functional magnetic resonance imaging
(fMRI) data. The code is publicly available.
Synchronous Context-Free Grammars and Optimal Linear Parsing Strategies
Authors: Pierluigi Crescenzi, Daniel Gildea, Andrea Marino, Gianluca Rossi, Giorgio Satta
Date: 2013-11-25 00:00:00
Tasks: Translation

Synchronous Context-Free Grammars (SCFGs), also known as syntax-directed
translation schemata, are unlike context-free grammars in that they do not have
a binary normal form. In general, parsing with SCFGs takes space and time
polynomial in the length of the input strings, but with the degree of the
polynomial depending on the permutations of the SCFG rules. We consider linear
parsing strategies, which add one nonterminal at a time. We show that for a
given input permutation, the problems of finding the linear parsing strategy
with the minimum space and time complexity are both NP-hard.
Large-scale Multi-label Learning with Missing Labels
Authors: Hsiang-Fu Yu, Prateek Jain, Purushottam Kar, Inderjit S. Dhillon
Date: 2013-07-18 00:00:00
Tasks: Missing Labels, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION, Multi-Label Learning

The multi-label classification problem has generated significant interest in
recent years. However, existing approaches do not adequately address two key
challenges: (a) the ability to tackle problems with a large number (say
millions) of labels, and (b) the ability to handle data with missing labels. In
this paper, we directly address both these problems by studying the multi-label
problem in a generic empirical risk minimization (ERM) framework. Our
framework, despite being simple, is surprisingly able to encompass several
recent label-compression based methods which can be derived as special cases of
our method. To optimize the ERM problem, we develop techniques that exploit the
structure of specific loss functions - such as the squared loss function - to
offer efficient algorithms. We further show that our learning framework admits
formal excess risk bounds even in the presence of missing labels. Our risk
bounds are tight and demonstrate better generalization performance for low-rank
promoting trace-norm regularization when compared to (rank insensitive)
Frobenius norm regularization. Finally, we present extensive empirical results
on a variety of benchmark datasets and show that our methods perform
significantly better than existing label compression based methods and can
scale up to very large datasets such as the Wikipedia dataset.
Learning Reputation in an Authorship Network
Authors: Charanpal Dhanjal, Stéphan Clémençon
Date: 2013-11-25 00:00:00
Tasks: Topic Models

The problem of searching for experts in a given academic field is hugely
important in both industry and academia. We study exactly this issue with
respect to a database of authors and their publications. The idea is to use
Latent Semantic Indexing (LSI) and Latent Dirichlet Allocation (LDA) to perform
topic modelling in order to find authors who have worked in a query field. We
then construct a coauthorship graph and motivate the use of influence
maximisation and a variety of graph centrality measures to obtain a ranked list
of experts. The ranked lists are further improved using a Markov Chain-based
rank aggregation approach. The complete method is readily scalable to large
datasets. To demonstrate the efficacy of the approach we report on an extensive
set of computational simulations using the Arnetminer dataset. An improvement
in mean average precision is demonstrated over the baseline case of simply
using the order of authors found by the topic models.
Summary Statistics for Partitionings and Feature Allocations
Authors: Işık Barış Fidaner, Ali Taylan Cemgil
Date: 2013-10-01 00:00:00
Proceeding: NeurIPS 2013
Tasks: Clustering

Infinite mixture models are commonly used for clustering. One can sample from
the posterior of mixture assignments by Monte Carlo methods or find its maximum
a posteriori solution by optimization. However, in some problems the posterior
is diffuse and it is hard to interpret the sampled partitionings. In this
paper, we introduce novel statistics based on block sizes for representing
sample sets of partitionings and feature allocations. We develop an
element-based definition of entropy to quantify segmentation among their
elements. Then we propose a simple algorithm called entropy agglomeration (EA)
to summarize and visualize this information. Experiments on various infinite
mixture posteriors as well as a feature allocation dataset demonstrate that the
proposed statistics are useful in practice.
Novelty Detection Under Multi-Instance Multi-Label Framework
Authors: Qi Lou, Raviv Raich, Forrest Briggs, Xiaoli Z. Fern
Date: 2013-11-25 00:00:00
Tasks: Novelty Detection, Object, TAG

Novelty detection plays an important role in machine learning and signal
processing. This paper studies novelty detection in a new setting where the
data object is represented as a bag of instances and associated with multiple
class labels, referred to as multi-instance multi-label (MIML) learning.
Contrary to the common assumption in MIML that each instance in a bag belongs
to one of the known classes, in novelty detection, we focus on the scenario
where bags may contain novel-class instances. The goal is to determine, for any
given instance in a new bag, whether it belongs to a known class or a novel
class. Detecting novelty in the MIML setting captures many real-world phenomena
and has many potential applications. For example, in a collection of tagged
images, the tag may only cover a subset of objects existing in the images.
Discovering an object whose class has not been previously tagged can be useful
for the purpose of soliciting a label for the new object class. To address this
novel problem, we present a discriminative framework for detecting new class
instances. Experiments demonstrate the effectiveness of our proposed method,
and reveal that the presence of unlabeled novel instances in training bags is
helpful to the detection of such instances in testing stage.
A Complete Characterization of Statistical Query Learning with Applications to Evolvability
Authors: Vitaly Feldman
Date: 2010-02-16 00:00:00
Tasks: Evolutionary Algorithms, PAC learning

Statistical query (SQ) learning model of Kearns (1993) is a natural
restriction of the PAC learning model in which a learning algorithm is allowed
to obtain estimates of statistical properties of the examples but cannot see
the examples themselves. We describe a new and simple characterization of the
query complexity of learning in the SQ learning model. Unlike the previously
known bounds on SQ learning our characterization preserves the accuracy and the
efficiency of learning. The preservation of accuracy implies that that our
characterization gives the first characterization of SQ learning in the
agnostic learning framework. The preservation of efficiency is achieved using a
new boosting technique and allows us to derive a new approach to the design of
evolutionary algorithms in Valiant's (2006) model of evolvability. We use this
approach to demonstrate the existence of a large class of monotone evolutionary
learning algorithms based on square loss performance estimation. These results
differ significantly from the few known evolutionary algorithms and give
evidence that evolvability in Valiant's model is a more versatile phenomenon
than there had been previous reason to suspect.
Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
Authors: Xiao-Tong Yuan, Ping Li, Tong Zhang
Date: 2013-11-22 00:00:00
Tasks: Compressive Sensing, parameter estimation, regression

Hard Thresholding Pursuit (HTP) is an iterative greedy selection procedure
for finding sparse solutions of underdetermined linear systems. This method has
been shown to have strong theoretical guarantee and impressive numerical
performance. In this paper, we generalize HTP from compressive sensing to a
generic problem setup of sparsity-constrained convex optimization. The proposed
algorithm iterates between a standard gradient descent step and a hard
thresholding step with or without debiasing. We prove that our method enjoys
the strong guarantees analogous to HTP in terms of rate of convergence and
parameter estimation accuracy. Numerical evidences show that our method is
superior to the state-of-the-art greedy selection methods in sparse logistic
regression and sparse precision matrix estimation tasks.