pwc-archive/papers-with-abstracts huggingface dataset:
Multilinear Principal Component Analysis Network for Tensor Object Classification
Authors: Rui Zeng, Jiasong Wu, Zhuhong Shao, Lotfi Senhadji, Huazhong Shu
Date: 2014-11-05 00:00:00
Tasks: Classification, General Classification, Object

The recently proposed principal component analysis network (PCANet) has been
proved high performance for visual content classification. In this letter, we
develop a tensorial extension of PCANet, namely, multilinear principal analysis
component network (MPCANet), for tensor object classification. Compared to
PCANet, the proposed MPCANet uses the spatial structure and the relationship
between each dimension of tensor objects much more efficiently. Experiments
were conducted on different visual content datasets including UCF sports action
video sequences database and UCF11 database. The experimental results have
revealed that the proposed MPCANet achieves higher classification accuracy than
PCANet for tensor object classification.
On the Convergence Rate of Decomposable Submodular Function Minimization
Authors: Robert Nishihara, Stefanie Jegelka, Michael. I. Jordan
Date: 2014-06-25 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: BIG-bench Machine Learning

Submodular functions describe a variety of discrete problems in machine
learning, signal processing, and computer vision. However, minimizing
submodular functions poses a number of algorithmic challenges. Recent work
introduced an easy-to-use, parallelizable algorithm for minimizing submodular
functions that decompose as the sum of "simple" submodular functions.
Empirically, this algorithm performs extremely well, but no theoretical
analysis was given. In this paper, we show that the algorithm converges
linearly, and we provide upper and lower bounds on the rate of convergence. Our
proof relies on the geometry of submodular polyhedra and draws on results from
spectral graph theory.
A Probabilistic Translation Method for Dictionary-based Cross-lingual Information Retrieval in Agglutinative Languages
Authors: Javid Dadashkarimi, Azadeh Shakery, Heshaam Faili
Date: 2014-11-04 00:00:00
Tasks: Cross-Lingual Information Retrieval, Information Retrieval, Retrieval, Translation

Translation ambiguity, out of vocabulary words and missing some translations
in bilingual dictionaries make dictionary-based Cross-language Information
Retrieval (CLIR) a challenging task. Moreover, in agglutinative languages which
do not have reliable stemmers, missing various lexical formations in bilingual
dictionaries degrades CLIR performance. This paper aims to introduce a
probabilistic translation model to solve the ambiguity problem, and also to
provide most likely formations of a dictionary candidate. We propose Minimum
Edit Support Candidates (MESC) method that exploits a monolingual corpus and a
bilingual dictionary to translate users' native language queries to documents'
language. Our experiments show that the proposed method outperforms
state-of-the-art dictionary-based English-Persian CLIR.
Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy
Authors: Maria Florina Balcan, Vitaly Feldman
Date: 2013-07-11 00:00:00
Tasks: Active Learning, General Classification

We describe a framework for designing efficient active learning algorithms
that are tolerant to random classification noise and are
differentially-private. The framework is based on active learning algorithms
that are statistical in the sense that they rely on estimates of expectations
of functions of filtered random examples. It builds on the powerful statistical
query framework of Kearns (1993).
  We show that any efficient active statistical learning algorithm can be
automatically converted to an efficient active learning algorithm which is
tolerant to random classification noise as well as other forms of
"uncorrelated" noise. The complexity of the resulting algorithms has
information-theoretically optimal quadratic dependence on $1/(1-2\eta)$, where
$\eta$ is the noise rate.
  We show that commonly studied concept classes including thresholds,
rectangles, and linear separators can be efficiently actively learned in our
framework. These results combined with our generic conversion lead to the first
computationally-efficient algorithms for actively learning some of these
concept classes in the presence of random classification noise that provide
exponential improvement in the dependence on the error $\epsilon$ over their
passive counterparts. In addition, we show that our algorithms can be
automatically converted to efficient active differentially-private algorithms.
This leads to the first differentially-private active learning algorithms with
exponential label savings over the passive case.
On the Complexity of Learning with Kernels
Authors: Nicolò Cesa-Bianchi, Yishay Mansour, Ohad Shamir
Date: 2014-11-05 00:00:00

A well-recognized limitation of kernel learning is the requirement to handle
a kernel matrix, whose size is quadratic in the number of training examples.
Many methods have been proposed to reduce this computational cost, mostly by
using a subset of the kernel matrix entries, or some form of low-rank matrix
approximation, or a random projection method. In this paper, we study lower
bounds on the error attainable by such methods as a function of the number of
entries observed in the kernel matrix or the rank of an approximate kernel
matrix. We show that there are kernel learning problems where no such method
will lead to non-trivial computational savings. Our results also quantify how
the problem difficulty depends on parameters such as the nature of the loss
function, the regularization parameter, the norm of the desired predictor, and
the kernel matrix rank. Our results also suggest cases where more efficient
kernel learning might be possible.
Classification with the nearest neighbor rule in general finite dimensional spaces: necessary and sufficient conditions
Authors: Sébastien Gadat, Thierry Klein, Clément Marteau
Date: 2014-11-04 00:00:00
Tasks: General Classification

Given an $n$-sample of random vectors $(X_i,Y_i)_{1 \leq i \leq n}$ whose
joint law is unknown, the long-standing problem of supervised classification
aims to \textit{optimally} predict the label $Y$ of a given a new observation
$X$. In this context, the nearest neighbor rule is a popular flexible and
intuitive method in non-parametric situations.
  Even if this algorithm is commonly used in the machine learning and
statistics communities, less is known about its prediction ability in general
finite dimensional spaces, especially when the support of the density of the
observations is $\mathbb{R}^d$. This paper is devoted to the study of the
statistical properties of the nearest neighbor rule in various situations. In
particular, attention is paid to the marginal law of $X$, as well as the
smoothness and margin properties of the \textit{regression function} $\eta(X) =
\mathbb{E}[Y | X]$. We identify two necessary and sufficient conditions to
obtain uniform consistency rates of classification and to derive sharp
estimates in the case of the nearest neighbor rule. Some numerical experiments
are proposed at the end of the paper to help illustrate the discussion.
Adaptive Learning in Cartesian Product of Reproducing Kernel Hilbert Spaces
Authors: Masahiro Yukawa
Date: 2014-08-05 00:00:00

We propose a novel adaptive learning algorithm based on iterative orthogonal
projections in the Cartesian product of multiple reproducing kernel Hilbert
spaces (RKHSs). The task is estimating/tracking nonlinear functions which are
supposed to contain multiple components such as (i) linear and nonlinear
components, (ii) high- and low- frequency components etc. In this case, the use
of multiple RKHSs permits a compact representation of multicomponent functions.
The proposed algorithm is where two different methods of the author meet:
multikernel adaptive filtering and the algorithm of hyperplane projection along
affine subspace (HYPASS). In a certain particular case, the sum space of the
RKHSs is isomorphic to the product space and hence the proposed algorithm can
also be regarded as an iterative projection method in the sum space. The
efficacy of the proposed algorithm is shown by numerical examples.
High-Speed Tracking with Kernelized Correlation Filters
Authors: João F. Henriques, Rui Caseiro, Pedro Martins, Jorge Batista
Date: 2014-04-30 00:00:00
Tasks: regression, Video Object Tracking, Vocal Bursts Intensity Prediction

The core component of most modern trackers is a discriminative classifier,
tasked with distinguishing between the target and the surrounding environment.
To cope with natural image changes, this classifier is typically trained with
translated and scaled sample patches. Such sets of samples are riddled with
redundancies -- any overlapping pixels are constrained to be the same. Based on
this simple observation, we propose an analytic model for datasets of thousands
of translated patches. By showing that the resulting data matrix is circulant,
we can diagonalize it with the Discrete Fourier Transform, reducing both
storage and computation by several orders of magnitude. Interestingly, for
linear regression our formulation is equivalent to a correlation filter, used
by some of the fastest competitive trackers. For kernel regression, however, we
derive a new Kernelized Correlation Filter (KCF), that unlike other kernel
algorithms has the exact same complexity as its linear counterpart. Building on
it, we also propose a fast multi-channel extension of linear correlation
filters, via a linear kernel, which we call Dual Correlation Filter (DCF). Both
KCF and DCF outperform top-ranking trackers such as Struck or TLD on a 50
videos benchmark, despite running at hundreds of frames-per-second, and being
implemented in a few lines of code (Algorithm 1). To encourage further
developments, our tracking framework was made open-source.
Distributed Low-Rank Estimation Based on Joint Iterative Optimization in Wireless Sensor Networks
Authors: S. Xu, R. C. de Lamare, H. V. Poor
Date: 2014-11-05 00:00:00
Tasks: Dimensionality Reduction

This paper proposes a novel distributed reduced--rank scheme and an adaptive
algorithm for distributed estimation in wireless sensor networks. The proposed
distributed scheme is based on a transformation that performs dimensionality
reduction at each agent of the network followed by a reduced-dimension
parameter vector. A distributed reduced-rank joint iterative estimation
algorithm is developed, which has the ability to achieve significantly reduced
communication overhead and improved performance when compared with existing
techniques. Simulation results illustrate the advantages of the proposed
strategy in terms of convergence rate and mean square error performance.
Learning of Agent Capability Models with Applications in Multi-agent Planning
Authors: Yu Zhang, Subbarao Kambhampati
Date: 2014-11-04 00:00:00

One important challenge for a set of agents to achieve more efficient
collaboration is for these agents to maintain proper models of each other. An
important aspect of these models of other agents is that they are often partial
and incomplete. Thus far, there are two common representations of agent models:
MDP based and action based, which are both based on action modeling. In many
applications, agent models may not have been given, and hence must be learnt.
While it may seem convenient to use either MDP based or action based models for
learning, in this paper, we introduce a new representation based on capability
models, which has several unique advantages. First, we show that learning
capability models can be performed efficiently online via Bayesian learning,
and the learning process is robust to high degrees of incompleteness in plan
execution traces (e.g., with only start and end states). While high degrees of
incompleteness in plan execution traces presents learning challenges for MDP
based and action based models, capability models can still learn to {\em
abstract} useful information out of these traces. As a result, capability
models are useful in applications in which such incompleteness is common, e.g.,
robot learning human model from observations and interactions. Furthermore,
when used in multi-agent planning (with each agent modeled separately),
capability models provide flexible abstraction of actions. The limitation,
however, is that the synthesized plan is incomplete and abstract.
Do Convnets Learn Correspondence?
Authors: Jonathan Long, Ning Zhang, Trevor Darrell
Date: 2014-11-04 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: General Classification, image-classification, Image Classification, Keypoint Detection, object-detection, Object Detection

Convolutional neural nets (convnets) trained from massive labeled datasets
have substantially improved the state-of-the-art in image classification and
object detection. However, visual understanding requires establishing
correspondence on a finer level than object category. Given their large pooling
regions and training from whole-image labels, it is not clear that convnets
derive their success from an accurate correspondence model which could be used
for precise localization. In this paper, we study the effectiveness of convnet
activation features for tasks requiring correspondence. We present evidence
that convnet features localize at a much finer scale than their receptive field
sizes, that they can be used to perform intraclass alignment as well as
conventional hand-engineered features, and that they outperform conventional
features in keypoint prediction on objects from PASCAL VOC 2011.
Expectation-Maximization for Learning Determinantal Point Processes
Authors: Jennifer Gillenwater, Alex Kulesza, Emily Fox, Ben Taskar
Date: 2014-11-04 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Diversity, Point Processes, Product Recommendation

A determinantal point process (DPP) is a probabilistic model of set diversity
compactly parameterized by a positive semi-definite kernel matrix. To fit a DPP
to a given task, we would like to learn the entries of its kernel matrix by
maximizing the log-likelihood of the available data. However, log-likelihood is
non-convex in the entries of the kernel matrix, and this learning problem is
conjectured to be NP-hard. Thus, previous work has instead focused on more
restricted convex learning settings: learning only a single weight for each row
of the kernel matrix, or learning weights for a linear combination of DPPs with
fixed kernel matrices. In this work we propose a novel algorithm for learning
the full kernel matrix. By changing the kernel parameterization from matrix
entries to eigenvalues and eigenvectors, and then lower-bounding the likelihood
in the manner of expectation-maximization algorithms, we obtain an effective
optimization procedure. We test our method on a real-world product
recommendation task, and achieve relative gains of up to 16.5% in test
log-likelihood compared to the naive approach of maximizing likelihood by
projected gradient ascent on the entries of the kernel matrix.
Fast Exact Matrix Completion with Finite Samples
Authors: Prateek Jain, Praneeth Netrapalli
Date: 2014-11-04 00:00:00
Tasks: Matrix Completion

Matrix completion is the problem of recovering a low rank matrix by observing
a small fraction of its entries. A series of recent works [KOM12,JNS13,HW14]
have proposed fast non-convex optimization based iterative algorithms to solve
this problem. However, the sample complexity in all these results is
sub-optimal in its dependence on the rank, condition number and the desired
accuracy.
  In this paper, we present a fast iterative algorithm that solves the matrix
completion problem by observing $O(nr^5 \log^3 n)$ entries, which is
independent of the condition number and the desired accuracy. The run time of
our algorithm is $O(nr^7\log^3 n\log 1/\epsilon)$ which is near linear in the
dimension of the matrix. To the best of our knowledge, this is the first near
linear time algorithm for exact matrix completion with finite sample complexity
(i.e. independent of $\epsilon$).
  Our algorithm is based on a well known projected gradient descent method,
where the projection is onto the (non-convex) set of low rank matrices. There
are two key ideas in our result: 1) our argument is based on a $\ell_{\infty}$
norm potential function (as opposed to the spectral norm) and provides a novel
way to obtain perturbation bounds for it. 2) we prove and use a natural
extension of the Davis-Kahan theorem to obtain perturbation bounds on the best
low rank approximation of matrices with good eigen-gap. Both of these ideas may
be of independent interest.
A statistical model for tensor PCA
Authors: Andrea Montanari, Emile Richard
Date: 2014-11-04 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: model

We consider the Principal Component Analysis problem for large tensors of
arbitrary order $k$ under a single-spike (or rank-one plus noise) model. On the
one hand, we use information theory, and recent results in probability theory,
to establish necessary and sufficient conditions under which the principal
component can be estimated using unbounded computational resources. It turns
out that this is possible as soon as the signal-to-noise ratio $\beta$ becomes
larger than $C\sqrt{k\log k}$ (and in particular $\beta$ can remain bounded as
the problem dimensions increase).
  On the other hand, we analyze several polynomial-time estimation algorithms,
based on tensor unfolding, power iteration and message passing ideas from
graphical models. We show that, unless the signal-to-noise ratio diverges in
the system dimensions, none of these approaches succeeds. This is possibly
related to a fundamental limitation of computationally tractable estimators for
this problem.
  We discuss various initializations for tensor power iteration, and show that
a tractable initialization based on the spectrum of the matricized tensor
outperforms significantly baseline methods, statistically and computationally.
Finally, we consider the case in which additional side information is available
about the unknown signal. We characterize the amount of side information that
allows the iterative algorithms to converge to a good estimate.
Randomized Dimensionality Reduction for k-means Clustering
Authors: Christos Boutsidis, Anastasios Zouzias, Michael W. Mahoney, Petros Drineas
Date: 2011-10-13 00:00:00
Tasks: Clustering, Dimensionality Reduction, feature selection

We study the topic of dimensionality reduction for $k$-means clustering.
Dimensionality reduction encompasses the union of two approaches: \emph{feature
selection} and \emph{feature extraction}. A feature selection based algorithm
for $k$-means clustering selects a small subset of the input features and then
applies $k$-means clustering on the selected features. A feature extraction
based algorithm for $k$-means clustering constructs a small set of new
artificial features and then applies $k$-means clustering on the constructed
features. Despite the significance of $k$-means clustering as well as the
wealth of heuristic methods addressing it, provably accurate feature selection
methods for $k$-means clustering are not known. On the other hand, two provably
accurate feature extraction methods for $k$-means clustering are known in the
literature; one is based on random projections and the other is based on the
singular value decomposition (SVD).
  This paper makes further progress towards a better understanding of
dimensionality reduction for $k$-means clustering. Namely, we present the first
provably accurate feature selection method for $k$-means clustering and, in
addition, we present two feature extraction methods. The first feature
extraction method is based on random projections and it improves upon the
existing results in terms of time complexity and number of features needed to
be extracted. The second feature extraction method is based on fast approximate
SVD factorizations and it also improves upon the existing results in terms of
time complexity. The proposed algorithms are randomized and provide
constant-factor approximation guarantees with respect to the optimal $k$-means
objective value.
Iterated geometric harmonics for data imputation and reconstruction of missing data
Authors: Chad Eckman, Jonathan A. Lindgren, Erin P. J. Pearse, David J. Sacco, Zachariah Zhang
Date: 2014-11-04 00:00:00
Tasks: Imputation

The method of geometric harmonics is adapted to the situation of incomplete
data by means of the iterated geometric harmonics (IGH) scheme. The method is
tested on natural and synthetic data sets with 50--500 data points and
dimensionality of 400--10,000. Experiments suggest that the algorithm converges
to a near optimal solution within 4--6 iterations, at runtimes of less than 30
minutes on a medium-grade desktop computer. The imputation of missing data
values is applied to collections of damaged images (suffering from data
annihilation rates of up to 70\%) which are reconstructed with a surprising
degree of accuracy.
Complexity theoretic limitations on learning DNF's
Authors: Amit Daniely, Shai Shalev-Shwatz
Date: 2014-04-13 00:00:00

Using the recently developed framework of [Daniely et al, 2014], we show that
under a natural assumption on the complexity of refuting random K-SAT formulas,
learning DNF formulas is hard. Furthermore, the same assumption implies the
hardness of learning intersections of $\omega(\log(n))$ halfspaces,
agnostically learning conjunctions, as well as virtually all (distribution
free) learning problems that were previously shown hard (under complexity
assumptions).
Articulated Pose Estimation by a Graphical Model with Image Dependent Pairwise Relations
Authors: Xianjie Chen, Alan Yuille
Date: 2014-07-12 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Pose Estimation

We present a method for estimating articulated human pose from a single
static image based on a graphical model with novel pairwise relations that make
adaptive use of local image measurements. More precisely, we specify a
graphical model for human pose which exploits the fact the local image
measurements can be used both to detect parts (or joints) and also to predict
the spatial relationships between them (Image Dependent Pairwise Relations).
These spatial relationships are represented by a mixture model. We use Deep
Convolutional Neural Networks (DCNNs) to learn conditional probabilities for
the presence of parts and their spatial relationships within image patches.
Hence our model combines the representational flexibility of graphical models
with the efficiency and statistical power of DCNNs. Our method significantly
outperforms the state of the art methods on the LSP and FLIC datasets and also
performs very well on the Buffy dataset without any training.
Convex Optimization for Big Data
Authors: Volkan Cevher, Stephen Becker, Mark Schmidt
Date: 2014-11-04 00:00:00
Tasks: Survey

This article reviews recent advances in convex optimization algorithms for
Big Data, which aim to reduce the computational, storage, and communications
bottlenecks. We provide an overview of this emerging field, describe
contemporary approximation techniques like first-order methods and
randomization for scalability, and survey the important role of parallel and
distributed computation. The new Big Data algorithms are based on surprisingly
simple principles and attain staggering accelerations even on classical
problems.