pwc-archive/papers-with-abstracts huggingface dataset:
More data speeds up training time in learning halfspaces over sparse vectors
Authors: Amit Daniely, Nati Linial, Shai Shalev Shwartz
Date: 2013-11-10 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: PAC learning

The increased availability of data in recent years has led several authors to
ask whether it is possible to use data as a {\em computational} resource. That
is, if more data is available, beyond the sample complexity limit, is it
possible to use the extra examples to speed up the computation time required to
perform the learning task?
  We give the first positive answer to this question for a {\em natural
supervised learning problem} --- we consider agnostic PAC learning of
halfspaces over $3$-sparse vectors in $\{-1,1,0\}^n$. This class is
inefficiently learnable using $O\left(n/\epsilon^2\right)$ examples. Our main
contribution is a novel, non-cryptographic, methodology for establishing
computational-statistical gaps, which allows us to show that, under a widely
believed assumption that refuting random $\mathrm{3CNF}$ formulas is hard, it
is impossible to efficiently learn this class using only
$O\left(n/\epsilon^2\right)$ examples. We further show that under stronger
hardness assumptions, even $O\left(n^{1.499}/\epsilon^2\right)$ examples do not
suffice. On the other hand, we show a new algorithm that learns this class
efficiently using $\tilde{\Omega}\left(n^2/\epsilon^2\right)$ examples. This
formally establishes the tradeoff between sample and computational complexity
for a natural supervised learning problem.
Semantic Sort: A Supervised Approach to Personalized Semantic Relatedness
Authors: Ran El-Yaniv, David Yanay
Date: 2013-11-10 00:00:00

We propose and study a novel supervised approach to learning statistical
semantic relatedness models from subjectively annotated training examples. The
proposed semantic model consists of parameterized co-occurrence statistics
associated with textual units of a large background knowledge corpus. We
present an efficient algorithm for learning such semantic models from a
training sample of relatedness preferences. Our method is corpus independent
and can essentially rely on any sufficiently large (unstructured) collection of
coherent texts. Moreover, the approach facilitates the fitting of semantic
models for specific users or groups of users. We present the results of
extensive range of experiments from small to large scale, indicating that the
proposed method is effective and competitive with the state-of-the-art.
Learning Gaussian Graphical Models with Observed or Latent FVSs
Authors: Ying Liu, Alan S. Willsky
Date: 2013-11-10 00:00:00
Proceeding: NeurIPS 2013 12

Gaussian Graphical Models (GGMs) or Gauss Markov random fields are widely
used in many applications, and the trade-off between the modeling capacity and
the efficiency of learning and inference has been an important research
problem. In this paper, we study the family of GGMs with small feedback vertex
sets (FVSs), where an FVS is a set of nodes whose removal breaks all the
cycles. Exact inference such as computing the marginal distributions and the
partition function has complexity $O(k^{2}n)$ using message-passing algorithms,
where k is the size of the FVS, and n is the total number of nodes. We propose
efficient structure learning algorithms for two cases: 1) All nodes are
observed, which is useful in modeling social or flight networks where the FVS
nodes often correspond to a small number of high-degree nodes, or hubs, while
the rest of the networks is modeled by a tree. Regardless of the maximum
degree, without knowing the full graph structure, we can exactly compute the
maximum likelihood estimate in $O(kn^2+n^2\log n)$ if the FVS is known or in
polynomial time if the FVS is unknown but has bounded size. 2) The FVS nodes
are latent variables, where structure learning is equivalent to decomposing a
inverse covariance matrix (exactly or approximately) into the sum of a
tree-structured matrix and a low-rank matrix. By incorporating efficient
inference into the learning steps, we can obtain a learning algorithm using
alternating low-rank correction with complexity $O(kn^{2}+n^{2}\log n)$ per
iteration. We also perform experiments using both synthetic data as well as
real data of flight delays to demonstrate the modeling capacity with FVSs of
various sizes.
Pattern-Coupled Sparse Bayesian Learning for Recovery of Block-Sparse Signals
Authors: Jun Fang, Yanning Shen, Hongbin Li, Pu Wang
Date: 2013-11-09 00:00:00

We consider the problem of recovering block-sparse signals whose structures
are unknown \emph{a priori}. Block-sparse signals with nonzero coefficients
occurring in clusters arise naturally in many practical scenarios. However, the
knowledge of the block structure is usually unavailable in practice. In this
paper, we develop a new sparse Bayesian learning method for recovery of
block-sparse signals with unknown cluster patterns. Specifically, a
pattern-coupled hierarchical Gaussian prior model is introduced to characterize
the statistical dependencies among coefficients, in which a set of
hyperparameters are employed to control the sparsity of signal coefficients.
Unlike the conventional sparse Bayesian learning framework in which each
individual hyperparameter is associated independently with each coefficient, in
this paper, the prior for each coefficient not only involves its own
hyperparameter, but also the hyperparameters of its immediate neighbors. In
doing this way, the sparsity patterns of neighboring coefficients are related
to each other and the hierarchical model has the potential to encourage
structured-sparse solutions. The hyperparameters, along with the sparse signal,
are learned by maximizing their posterior probability via an
expectation-maximization (EM) algorithm. Numerical results show that the
proposed algorithm presents uniform superiority over other existing methods in
a series of experiments.
Large Margin Semi-supervised Structured Output Learning
Authors: P. Balamurugan, Shirish Shevade, Sundararajan Sellamanickam
Date: 2013-11-09 00:00:00
Tasks: Structured Prediction

In structured output learning, obtaining labelled data for real-world
applications is usually costly, while unlabelled examples are available in
abundance. Semi-supervised structured classification has been developed to
handle large amounts of unlabelled structured data. In this work, we consider
semi-supervised structural SVMs with domain constraints. The optimization
problem, which in general is not convex, contains the loss terms associated
with the labelled and unlabelled examples along with the domain constraints. We
propose a simple optimization approach, which alternates between solving a
supervised learning problem and a constraint matching problem. Solving the
constraint matching problem is difficult for structured prediction, and we
propose an efficient and effective hill-climbing method to solve it. The
alternating optimization is carried out within a deterministic annealing
framework, which helps in effective constraint matching, and avoiding local
minima which are not very useful. The algorithm is simple to implement and
achieves comparable generalization performance on benchmark datasets.
A Structured Prediction Approach for Missing Value Imputation
Authors: Rahul Kidambi, Vinod Nair, Sundararajan Sellamanickam, S. Sathiya Keerthi
Date: 2013-11-09 00:00:00
Tasks: Imputation, Prediction, Structured Prediction

Missing value imputation is an important practical problem. There is a large
body of work on it, but there does not exist any work that formulates the
problem in a structured output setting. Also, most applications have
constraints on the imputed data, for example on the distribution associated
with each variable. None of the existing imputation methods use these
constraints. In this paper we propose a structured output approach for missing
value imputation that also incorporates domain constraints. We focus on large
margin models, but it is easy to extend the ideas to probabilistic models. We
deal with the intractable inference step in learning via a piecewise training
technique that is simple, efficient, and effective. Comparison with existing
state-of-the-art and baseline imputation methods shows that our method gives
significantly improved performance on the Hamming loss measure.
Low-Rank Matrix and Tensor Completion via Adaptive Sampling
Authors: Akshay Krishnamurthy, Aarti Singh
Date: 2013-04-17 00:00:00
Proceeding: NeurIPS 2013 12

We study low rank matrix and tensor completion and propose novel algorithms
that employ adaptive sampling schemes to obtain strong performance guarantees.
Our algorithms exploit adaptivity to identify entries that are highly
informative for learning the column space of the matrix (tensor) and
consequently, our results hold even when the row space is highly coherent, in
contrast with previous analyses. In the absence of noise, we show that one can
exactly recover a $n \times n$ matrix of rank $r$ from merely $\Omega(n
r^{3/2}\log(r))$ matrix entries. We also show that one can recover an order $T$
tensor using $\Omega(n r^{T-1/2}T^2 \log(r))$ entries. For noisy recovery, our
algorithm consistently estimates a low rank matrix corrupted with noise using
$\Omega(n r^{3/2} \textrm{polylog}(n))$ entries. We complement our study with
simulations that verify our theory and demonstrate the scalability of our
algorithms.
Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
Authors: Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes
Date: 2013-11-08 00:00:00
Proceeding: NeurIPS 2013 12

We investigate three related and important problems connected to machine
learning: approximating a submodular function everywhere, learning a submodular
function (in a PAC-like setting [53]), and constrained minimization of
submodular functions. We show that the complexity of all three problems depends
on the 'curvature' of the submodular function, and provide lower and upper
bounds that refine and improve previous results [3, 16, 18, 52]. Our proof
techniques are fairly generic. We either use a black-box transformation of the
function (for approximation and learning), or a transformation of algorithms to
use an appropriate surrogate function (for minimization). Curiously, curvature
has been known to influence approximations for submodular maximization [7, 55],
but its effect on minimization, approximation and learning has hitherto been
open. We complete this picture, and also support our theoretical claims by
empirical results.
Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
Authors: Rishabh Iyer, Jeff Bilmes
Date: 2013-11-08 00:00:00
Proceeding: NeurIPS 2013
Tasks: Diversity

We investigate two new optimization problems -- minimizing a submodular
function subject to a submodular lower bound constraint (submodular cover) and
maximizing a submodular function subject to a submodular upper bound constraint
(submodular knapsack). We are motivated by a number of real-world applications
in machine learning including sensor placement and data subset selection, which
require maximizing a certain submodular function (like coverage or diversity)
while simultaneously minimizing another (like cooperative cost). These problems
are often posed as minimizing the difference between submodular functions [14,
35] which is in the worst case inapproximable. We show, however, that by
phrasing these problems as constrained optimization, which is more natural for
many applications, we achieve a number of bounded approximation guarantees. We
also show that both these problems are closely related and an approximation
algorithm solving one can be used to obtain an approximation guarantee for the
other. We provide hardness results for both problems thus showing that our
approximation factors are tight up to log-factors. Finally, we empirically
demonstrate the performance and good scalability properties of our algorithms.
An Experimental Comparison of Trust Region and Level Sets
Authors: Lena Gorelick, Ismail BenAyed, Frank R. Schmidt, Yuri Boykov
Date: 2013-11-08 00:00:00

High-order (non-linear) functionals have become very popular in segmentation,
stereo and other computer vision problems. Level sets is a well established
general gradient descent framework, which is directly applicable to
optimization of such functionals and widely used in practice. Recently, another
general optimization approach based on trust region methodology was proposed
for regional non-linear functionals. Our goal is a comprehensive experimental
comparison of these two frameworks in regard to practical efficiency,
robustness to parameters, and optimality. We experiment on a wide range of
problems with non-linear constraints on segment volume, appearance and shape.
Nonparametric Multi-group Membership Model for Dynamic Networks
Authors: Myunghwan Kim, Jure Leskovec
Date: 2013-11-08 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Link Prediction

Relational data-like graphs, networks, and matrices-is often dynamic, where
the relational structure evolves over time. A fundamental problem in the
analysis of time-varying network data is to extract a summary of the common
structure and the dynamics of the underlying relations between the entities.
Here we build on the intuition that changes in the network structure are driven
by the dynamics at the level of groups of nodes. We propose a nonparametric
multi-group membership model for dynamic networks. Our model contains three
main components: We model the birth and death of individual groups with respect
to the dynamics of the network structure via a distance dependent Indian Buffet
Process. We capture the evolution of individual node group memberships via a
Factorial Hidden Markov model. And, we explain the dynamics of the network
structure by explicitly modeling the connectivity structure of groups. We
demonstrate our model's capability of identifying the dynamics of latent groups
in a number of different types of network data. Experimental results show that
our model provides improved predictive performance over existing dynamic
network models on future network forecasting and missing link prediction.
A new stopping criterion for the mean shift iterative algorithm
Authors: Roberto Rodríguez, Esley Torres, Yasel Garcés, Osvaldo Pereira, Humberto Sossa
Date: 2013-11-08 00:00:00
Tasks: Segmentation

The mean shift iterative algorithm was proposed in 2006, for using the
entropy as a stopping criterion. From then on, a theoretical base has been
developed and a group of applications has been carried out using this
algorithm. This paper proposes a new stopping criterion for the mean shift
iterative algorithm, where stopping threshold via entropy is used now, but in
another way. Many segmentation experiments were carried out by utilizing
standard images and it was verified that a better segmentation was reached, and
that the algorithm had better stability. An analysis on the convergence,
through a theorem, with the new stopping criterion was carried out. The goal of
this paper is to compare the new stopping criterion with the old criterion. For
this reason, the obtained results were not compared with other segmentation
approaches, since with the old stopping criterion were previously carried out.
Models and algorithms for skip-free Markov decision processes on trees
Authors: E. J. Collins
Date: 2013-09-17 00:00:00

We introduce a class of models for multidimensional control problems which we
call skip-free Markov decision processes on trees. We describe and analyse an
algorithm applicable to Markov decision processes of this type that are
skip-free in the negative direction. Starting with the finite average cost
case, we show that the algorithm combines the advantages of both value
iteration and policy iteration -- it is guaranteed to converge to an optimal
policy and optimal value function after a finite number of iterations but the
computational effort required for each iteration step is comparable with that
for value iteration. We show that the algorithm can also be used to solve
discounted cost models and continuous time models, and that a suitably modified
algorithm can be used to solve communicating models.
Fast Tracking via Spatio-Temporal Context Learning
Authors: Kaihua Zhang, Lei Zhang, Ming-Hsuan Yang, David Zhang
Date: 2013-11-08 00:00:00
Tasks: Position, Visual Tracking

In this paper, we present a simple yet fast and robust algorithm which
exploits the spatio-temporal context for visual tracking. Our approach
formulates the spatio-temporal relationships between the object of interest and
its local context based on a Bayesian framework, which models the statistical
correlation between the low-level features (i.e., image intensity and position)
from the target and its surrounding regions. The tracking problem is posed by
computing a confidence map, and obtaining the best target location by
maximizing an object location likelihood function. The Fast Fourier Transform
is adopted for fast learning and detection in this work. Implemented in MATLAB
without code optimization, the proposed tracker runs at 350 frames per second
on an i7 machine. Extensive experimental results show that the proposed
algorithm performs favorably against state-of-the-art methods in terms of
efficiency, accuracy and robustness.
Unsupervised learning human's activities by overexpressed recognized non-speech sounds
Authors: Serge Smidtas, Magalie Peyrot
Date: 2013-11-08 00:00:00
Tasks: TAG

Human activity and environment produces sounds such as, at home, the noise
produced by water, cough, or television. These sounds can be used to determine
the activity in the environment. The objective is to monitor a person's
activity or determine his environment using a single low cost microphone by
sound analysis. The purpose is to adapt programs to the activity or environment
or detect abnormal situations. Some patterns of over expressed repeatedly in
the sequences of recognized sounds inter and intra environment allow to
characterize activities such as the entrance of a person in the house, or a tv
program watched. We first manually annotated 1500 sounds of daily life activity
of old persons living at home recognized sounds. Then we inferred an ontology
and enriched the database of annotation with a crowed sourced manual annotation
of 7500 sounds to help with the annotation of the most frequent sounds. Using
learning sound algorithms, we defined 50 types of the most frequent sounds. We
used this set of recognizable sounds as a base to tag sounds and put tags on
them. By using over expressed number of motifs of sequences of the tags, we
were able to categorize using only a single low-cost microphone, complex
activities of daily life of a persona at home as watching TV, entrance in the
apartment of a person, or phone conversation including detecting unknown
activities as repeated tasks performed by users.
Moment-based Uniform Deviation Bounds for $k$-means and Friends
Authors: Matus Telgarsky, Sanjoy Dasgupta
Date: 2013-11-08 00:00:00
Tasks: Clustering

Suppose $k$ centers are fit to $m$ points by heuristically minimizing the
$k$-means cost; what is the corresponding fit over the source distribution?
This question is resolved here for distributions with $p\geq 4$ bounded
moments; in particular, the difference between the sample cost and distribution
cost decays with $m$ and $p$ as $m^{\min\{-1/4, -1/2+2/p\}}$. The essential
technical contribution is a mechanism to uniformly control deviations in the
face of unbounded parameter sets, cost functions, and source distributions. To
further demonstrate this mechanism, a soft clustering variant of $k$-means cost
is also considered, namely the log likelihood of a Gaussian mixture, subject to
the constraint that all covariance matrices have bounded spectrum. Lastly, a
rate with refined constants is provided for $k$-means instances possessing some
cluster structure.
Logique mathématique et linguistique formelle
Authors: Christian Retoré
Date: 2013-11-08 00:00:00
Tasks: Sentence

As the etymology of the word shows, logic is intimately related to language,
as exemplified by the work of philosophers from Antiquity and from the
Middle-Age. At the beginning of the XX century, the crisis of the foundations
of mathematics invented mathematical logic and imposed logic as a
language-based foundation for mathematics. How did the relations between logic
and language evolved in this newly defined mathematical framework? After a
survey of the history of the relation between logic and linguistics,
traditionally focused on semantics, we focus on some present issues: 1) grammar
as a deductive system 2) the transformation of the syntactic structure of a
sentence to a logical formula representing its meaning 3) taking into account
the context when interpreting words. This lecture shows that type theory
provides a convenient framework both for natural language syntax and for the
interpretation of any of tis level (words, sentences, discourse).
Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
Authors: Edoardo M. Airoldi, Thiago B. Costa, Stanley H. Chan
Date: 2013-11-07 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Stochastic Block Model

Non-parametric approaches for analyzing network data based on exchangeable
graph models (ExGM) have recently gained interest. The key object that defines
an ExGM is often referred to as a graphon. This non-parametric perspective on
network modeling poses challenging questions on how to make inference on the
graphon underlying observed network data. In this paper, we propose a
computationally efficient procedure to estimate a graphon from a set of
observed networks generated from it. This procedure is based on a stochastic
blockmodel approximation (SBA) of the graphon. We show that, by approximating
the graphon with a stochastic block model, the graphon can be consistently
estimated, that is, the estimation error vanishes as the size of the graph
approaches infinity.
Optimization, Learning, and Games with Predictable Sequences
Authors: Alexander Rakhlin, Karthik Sridharan
Date: 2013-11-08 00:00:00
Proceeding: NeurIPS 2013 12

We provide several applications of Optimistic Mirror Descent, an online
learning algorithm based on the idea of predictable sequences. First, we
recover the Mirror Prox algorithm for offline optimization, prove an extension
to Holder-smooth functions, and apply the results to saddle-point type
problems. Next, we prove that a version of Optimistic Mirror Descent (which has
a close relation to the Exponential Weights algorithm) can be used by two
strongly-uncoupled players in a finite zero-sum matrix game to converge to the
minimax equilibrium at the rate of O((log T)/T). This addresses a question of
Daskalakis et al 2011. Further, we consider a partial information version of
the problem. We then apply the results to convex programming and exhibit a
simple algorithm for the approximate Max Flow problem.