pwc-archive/papers-with-abstracts huggingface dataset:
Generalized Conditional Gradient for Sparse Estimation
Authors: Yao-Liang Yu, Xinhua Zhang, Dale Schuurmans
Date: 2014-10-17 00:00:00
Tasks: Dictionary Learning, Matrix Completion, Multi-class Classification

Structured sparsity is an important modeling tool that expands the
applicability of convex formulations for data analysis, however it also creates
significant challenges for efficient algorithm design. In this paper we
investigate the generalized conditional gradient (GCG) algorithm for solving
structured sparse optimization problems---demonstrating that, with some
enhancements, it can provide a more efficient alternative to current state of
the art approaches. After providing a comprehensive overview of the convergence
properties of GCG, we develop efficient methods for evaluating polar operators,
a subroutine that is required in each GCG iteration. In particular, we show how
the polar operator can be efficiently evaluated in two important scenarios:
dictionary learning and structured sparse estimation. A further improvement is
achieved by interleaving GCG with fixed-rank local subspace optimization. A
series of experiments on matrix completion, multi-class classification,
multi-view dictionary learning and overlapping group lasso shows that the
proposed method can significantly reduce the training cost of current
alternatives.
Convex Optimization in Julia
Authors: Madeleine Udell, Karanveer Mohan, David Zeng, Jenny Hong, Steven Diamond, Stephen Boyd
Date: 2014-10-17 00:00:00
Tasks: Form

This paper describes Convex, a convex optimization modeling framework in
Julia. Convex translates problems from a user-friendly functional language into
an abstract syntax tree describing the problem. This concise representation of
the global structure of the problem allows Convex to infer whether the problem
complies with the rules of disciplined convex programming (DCP), and to pass
the problem to a suitable solver. These operations are carried out in Julia
using multiple dispatch, which dramatically reduces the time required to verify
DCP compliance and to parse a problem into conic form. Convex then
automatically chooses an appropriate backend solver to solve the conic form
problem.
Variational Bayes for Merging Noisy Databases
Authors: Tamara Broderick, Rebecca C. Steorts
Date: 2014-10-17 00:00:00
Tasks: Bayesian Inference, Entity Resolution

Bayesian entity resolution merges together multiple, noisy databases and
returns the minimal collection of unique individuals represented, together with
their true, latent record values. Bayesian methods allow flexible generative
models that share power across databases as well as principled quantification
of uncertainty for queries of the final, resolved database. However, existing
Bayesian methods for entity resolution use Markov monte Carlo method (MCMC)
approximations and are too slow to run on modern databases containing millions
or billions of records. Instead, we propose applying variational approximations
to allow scalable Bayesian inference in these models. We derive a
coordinate-ascent approximation for mean-field variational Bayes, qualitatively
compare our algorithm to existing methods, note unique challenges for inference
that arise from the expected distribution of cluster sizes in entity
resolution, and discuss directions for future work in this domain.
A Hierarchical Multi-Output Nearest Neighbor Model for Multi-Output Dependence Learning
Authors: Richard G. Morris, Tony Martinez, Michael R. Smith
Date: 2014-10-17 00:00:00
Tasks: General Classification

Multi-Output Dependence (MOD) learning is a generalization of standard
classification problems that allows for multiple outputs that are dependent on
each other. A primary issue that arises in the context of MOD learning is that
for any given input pattern there can be multiple correct output patterns. This
changes the learning task from function approximation to relation
approximation. Previous algorithms do not consider this problem, and thus
cannot be readily applied to MOD problems. To perform MOD learning, we
introduce the Hierarchical Multi-Output Nearest Neighbor model (HMONN) that
employs a basic learning model for each output and a modified nearest neighbor
approach to refine the initial results.
mS2GD: Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
Authors: Jakub Konečný, Jie Liu, Peter Richtárik, Martin Takáč
Date: 2014-10-17 00:00:00

We propose a mini-batching scheme for improving the theoretical complexity
and practical performance of semi-stochastic gradient descent applied to the
problem of minimizing a strongly convex composite function represented as the
sum of an average of a large number of smooth convex functions, and simple
nonsmooth convex function. Our method first performs a deterministic step
(computation of the gradient of the objective function at the starting point),
followed by a large number of stochastic steps. The process is repeated a few
times with the last iterate becoming the new starting point. The novelty of our
method is in introduction of mini-batching into the computation of stochastic
steps. In each step, instead of choosing a single function, we sample $b$
functions, compute their gradients, and compute the direction based on this. We
analyze the complexity of the method and show that the method benefits from two
speedup effects. First, we prove that as long as $b$ is below a certain
threshold, we can reach predefined accuracy with less overall work than without
mini-batching. Second, our mini-batching scheme admits a simple parallel
implementation, and hence is suitable for further acceleration by
parallelization.
Heuristic algorithm for 1D and 2D unfolding
Authors: Yordan Karadzhov
Date: 2014-10-17 00:00:00

A very simple heuristic approach to the unfolding problem will be described.
An iterative algorithm starts with an empty histogram and every iteration aims
to add one entry to this histogram. The entry to be added is selected according
to a criteria which includes a $\chi^2$ test and a regularization. After a
relatively small number of iterations (500 - 1000) the growing reconstructed
distribution converges to the true distribution.
Learning Soft Linear Constraints with Application to Citation Field Extraction
Authors: Sam Anzaroot, Alexandre Passos, David Belanger, Andrew McCallum
Date: 2014-03-06 00:00:00
Proceeding: ACL 2014 6

Accurately segmenting a citation string into fields for authors, titles, etc.
is a challenging task because the output typically obeys various global
constraints. Previous work has shown that modeling soft constraints, where the
model is encouraged, but not require to obey the constraints, can substantially
improve segmentation performance. On the other hand, for imposing hard
constraints, dual decomposition is a popular technique for efficient prediction
given existing algorithms for unconstrained inference. We extend the technique
to perform prediction subject to soft constraints. Moreover, with a technique
for performing inference given soft constraints, it is easy to automatically
generate large families of constraints and learn their costs with a simple
convex optimization problem during training. This allows us to obtain
substantial gains in accuracy on a new, challenging citation extraction
dataset.
Realizing RCC8 networks using convex regions
Authors: Steven Schockaert, Sanjiang Li
Date: 2014-10-09 00:00:00

RCC8 is a popular fragment of the region connection calculus, in which
qualitative spatial relations between regions, such as adjacency, overlap and
parthood, can be expressed. While RCC8 is essentially dimensionless, most
current applications are confined to reasoning about two-dimensional or
three-dimensional physical space. In this paper, however, we are mainly
interested in conceptual spaces, which typically are high-dimensional Euclidean
spaces in which the meaning of natural language concepts can be represented
using convex regions. The aim of this paper is to analyze how the restriction
to convex regions constrains the realizability of networks of RCC8 relations.
First, we identify all ways in which the set of RCC8 base relations can be
restricted to guarantee that consistent networks can be convexly realized in
respectively 1D, 2D, 3D, and 4D. Most surprisingly, we find that if the
relation 'partially overlaps' is disallowed, all consistent atomic RCC8
networks can be convexly realized in 4D. If instead refinements of the relation
'part of' are disallowed, all consistent atomic RCC8 relations can be convexly
realized in 3D. We furthermore show, among others, that any consistent RCC8
network with 2n+1 variables can be realized using convex regions in the
n-dimensional Euclidean space.
KCRC-LCD: Discriminative Kernel Collaborative Representation with Locality Constrained Dictionary for Visual Categorization
Authors: Weiyang Liu, Zhiding Yu, Lijia Lu, Yandong Wen, Hui Li, Yuexian Zou
Date: 2014-10-17 00:00:00
Tasks: Classification, General Classification, image-classification, Image Classification

We consider the image classification problem via kernel collaborative
representation classification with locality constrained dictionary (KCRC-LCD).
Specifically, we propose a kernel collaborative representation classification
(KCRC) approach in which kernel method is used to improve the discrimination
ability of collaborative representation classification (CRC). We then measure
the similarities between the query and atoms in the global dictionary in order
to construct a locality constrained dictionary (LCD) for KCRC. In addition, we
discuss several similarity measure approaches in LCD and further present a
simple yet effective unified similarity measure whose superiority is validated
in experiments. There are several appealing aspects associated with LCD. First,
LCD can be nicely incorporated under the framework of KCRC. The LCD similarity
measure can be kernelized under KCRC, which theoretically links CRC and LCD
under the kernel method. Second, KCRC-LCD becomes more scalable to both the
training set size and the feature dimension. Example shows that KCRC is able to
perfectly classify data with certain distribution, while conventional CRC fails
completely. Comprehensive experiments on many public datasets also show that
KCRC-LCD is a robust discriminative classifier with both excellent performance
and good scalability, being comparable or outperforming many other
state-of-the-art approaches.
MKL-RT: Multiple Kernel Learning for Ratio-trace Problems via Convex Optimization
Authors: Raviteja Vemulapalli, Vinay Praneeth Boda, Rama Chellappa
Date: 2014-10-16 00:00:00
Tasks: Cross-Modal Retrieval, Dimensionality Reduction, Retrieval

In the recent past, automatic selection or combination of kernels (or
features) based on multiple kernel learning (MKL) approaches has been receiving
significant attention from various research communities. Though MKL has been
extensively studied in the context of support vector machines (SVM), it is
relatively less explored for ratio-trace problems. In this paper, we show that
MKL can be formulated as a convex optimization problem for a general class of
ratio-trace problems that encompasses many popular algorithms used in various
computer vision applications. We also provide an optimization procedure that is
guaranteed to converge to the global optimum of the proposed optimization
problem. We experimentally demonstrate that the proposed MKL approach, which we
refer to as MKL-RT, can be successfully used to select features for
discriminative dimensionality reduction and cross-modal retrieval. We also show
that the proposed convex MKL-RT approach performs better than the recently
proposed non-convex MKL-DR approach.
Robust Topological Feature Extraction for Mapping of Environments using Bio-Inspired Sensor Networks
Authors: Alireza Dirafzoon, Edgar Lobaton
Date: 2014-10-17 00:00:00
Tasks: General Classification, Topological Data Analysis

In this paper, we exploit minimal sensing information gathered from
biologically inspired sensor networks to perform exploration and mapping in an
unknown environment. A probabilistic motion model of mobile sensing nodes,
inspired by motion characteristics of cockroaches, is utilized to extract weak
encounter information in order to build a topological representation of the
environment.
  Neighbor to neighbor interactions among the nodes are exploited to build
point clouds representing spatial features of the manifold characterizing the
environment based on the sampled data.
  To extract dominant features from sampled data, topological data analysis is
used to produce persistence intervals for features, to be used for topological
mapping. In order to improve robustness characteristics of the sampled data
with respect to outliers, density based subsampling algorithms are employed.
Moreover, a robust scale-invariant classification algorithm for persistence
diagrams is proposed to provide a quantitative representation of desired
features in the data. Furthermore, various strategies for defining encounter
metrics with different degrees of information regarding agents' motion are
suggested to enhance the precision of the estimation and classification
performance of the topological method.
Volumes of logistic regression models with applications to model selection
Authors: James G. Dowty
Date: 2014-08-05 00:00:00
Tasks: Model Selection, regression

Logistic regression models with $n$ observations and $q$ linearly-independent
covariates are shown to have Fisher information volumes which are bounded below
by $\pi^q$ and above by ${n \choose q} \pi^q$. This is proved with a novel
generalization of the classical theorems of Pythagoras and de Gua, which is of
independent interest. The finding that the volume is always finite is new, and
it implies that the volume can be directly interpreted as a measure of model
complexity. The volume is shown to be a continuous function of the design
matrix $X$ at generic $X$, but to be discontinuous in general. This means that
models with sparse design matrices can be significantly less complex than
nearby models, so the resulting model-selection criterion prefers sparse
models. This is analogous to the way that $\ell^1$-regularisation tends to
prefer sparse model fits, though in our case this behaviour arises
spontaneously from general principles. Lastly, an unusual topological duality
is shown to exist between the ideal boundaries of the natural and expectation
parameter spaces of logistic regression models.
An Overview of General Performance Metrics of Binary Classifier Systems
Authors: Sebastian Raschka
Date: 2014-10-17 00:00:00
Tasks: Binary Classification, Classification, General Classification

This document provides a brief overview of different metrics and terminology
that is used to measure the performance of binary classification systems.
Domain-Independent Optimistic Initialization for Reinforcement Learning
Authors: Marlos C. Machado, Sriram Srinivasan, Michael Bowling
Date: 2014-10-16 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

In Reinforcement Learning (RL), it is common to use optimistic initialization
of value functions to encourage exploration. However, such an approach
generally depends on the domain, viz., the scale of the rewards must be known,
and the feature representation must have a constant norm. We present a simple
approach that performs optimistic initialization with less dependence on the
domain.
Learning a hyperplane regressor by minimizing an exact bound on the VC dimension
Authors: Jayadeva, Suresh Chandra, Siddarth Sabharwal, Sanjit S. Batra
Date: 2014-10-16 00:00:00

The capacity of a learning machine is measured by its Vapnik-Chervonenkis
dimension, and learning machines with a low VC dimension generalize better. It
is well known that the VC dimension of SVMs can be very large or unbounded,
even though they generally yield state-of-the-art learning performance. In this
paper, we show how to learn a hyperplane regressor by minimizing an exact, or
\boldmath{$\Theta$} bound on its VC dimension. The proposed approach, termed as
the Minimal Complexity Machine (MCM) Regressor, involves solving a simple
linear programming problem. Experimental results show, that on a number of
benchmark datasets, the proposed approach yields regressors with error rates
much less than those obtained with conventional SVM regresssors, while often
using fewer support vectors. On some benchmark datasets, the number of support
vectors is less than one tenth the number used by SVMs, indicating that the MCM
does indeed learn simpler representations.
Linearized and Single-Pass Belief Propagation
Authors: Wolfgang Gatterbauer, Stephan Günnemann, Danai Koutra, Christos Faloutsos
Date: 2014-06-27 00:00:00

How can we tell when accounts are fake or real in a social network? And how
can we tell which accounts belong to liberal, conservative or centrist users?
Often, we can answer such questions and label nodes in a network based on the
labels of their neighbors and appropriate assumptions of homophily ("birds of a
feather flock together") or heterophily ("opposites attract"). One of the most
widely used methods for this kind of inference is Belief Propagation (BP) which
iteratively propagates the information from a few nodes with explicit labels
throughout a network until convergence. One main problem with BP, however, is
that there are no known exact guarantees of convergence in graphs with loops.
  This paper introduces Linearized Belief Propagation (LinBP), a linearization
of BP that allows a closed-form solution via intuitive matrix equations and,
thus, comes with convergence guarantees. It handles homophily, heterophily, and
more general cases that arise in multi-class settings. Plus, it allows a
compact implementation in SQL. The paper also introduces Single-pass Belief
Propagation (SBP), a "localized" version of LinBP that propagates information
across every edge at most once and for which the final class assignments depend
only on the nearest labeled neighbors. In addition, SBP allows fast incremental
updates in dynamic networks. Our runtime experiments show that LinBP and SBP
are orders of magnitude faster than standard
Reconstructive Sparse Code Transfer for Contour Detection and Semantic Labeling
Authors: Michael Maire, Stella X. Yu, Pietro Perona
Date: 2014-10-16 00:00:00
Tasks: Contour Detection, Dictionary Learning

We frame the task of predicting a semantic labeling as a sparse
reconstruction procedure that applies a target-specific learned transfer
function to a generic deep sparse code representation of an image. This
strategy partitions training into two distinct stages. First, in an
unsupervised manner, we learn a set of generic dictionaries optimized for
sparse coding of image patches. We train a multilayer representation via
recursive sparse dictionary learning on pooled codes output by earlier layers.
Second, we encode all training images with the generic dictionaries and learn a
transfer function that optimizes reconstruction of patches extracted from
annotated ground-truth given the sparse codes of their corresponding image
patches. At test time, we encode a novel image using the generic dictionaries
and then reconstruct using the transfer function. The output reconstruction is
a semantic labeling of the test image.
  Applying this strategy to the task of contour detection, we demonstrate
performance competitive with state-of-the-art systems. Unlike almost all prior
work, our approach obviates the need for any form of hand-designed features or
filters. To illustrate general applicability, we also show initial results on
semantic part labeling of human faces.
  The effectiveness of our approach opens new avenues for research on deep
sparse representations. Our classifiers utilize this representation in a novel
manner. Rather than acting on nodes in the deepest layer, they attach to nodes
along a slice through multiple layers of the network in order to make
predictions about local patches. Our flexible combination of a generatively
learned sparse representation with discriminatively trained transfer
classifiers extends the notion of sparse reconstruction to encompass arbitrary
semantic labeling tasks.
Improve CAPTCHA's Security Using Gaussian Blur Filter
Authors: Ariyan Zarei
Date: 2014-10-16 00:00:00
Tasks: Optical Character Recognition (OCR)

Providing security for webservers against unwanted and automated
registrations has become a big concern. To prevent these kinds of false
registrations many websites use CAPTCHAs. Among all kinds of CAPTCHAs OCR-Based
or visual CAPTCHAs are very common. Actually visual CAPTCHA is an image
containing a sequence of characters. So far most of visual CAPTCHAs, in order
to resist against OCR programs, use some common implementations such as
wrapping the characters, random placement and rotations of characters, etc. In
this paper we applied Gaussian Blur filter, which is an image transformation,
to visual CAPTCHAs to reduce their readability by OCR programs. We concluded
that this technique made CAPTCHAs almost unreadable for OCR programs but, their
readability by human users still remained high.
Unbiased Black-Box Complexities of Jump Functions
Authors: Benjamin Doerr, Carola Doerr, Timo Kötzing
Date: 2014-03-30 00:00:00

We analyze the unbiased black-box complexity of jump functions with small,
medium, and large sizes of the fitness plateau surrounding the optimal
solution.
  Among other results, we show that when the jump size is $(1/2 -
\varepsilon)n$, that is, only a small constant fraction of the fitness values
is visible, then the unbiased black-box complexities for arities $3$ and higher
are of the same order as those for the simple \textsc{OneMax} function. Even
for the extreme jump function, in which all but the two fitness values $n/2$
and $n$ are blanked out, polynomial-time mutation-based (i.e., unary unbiased)
black-box optimization algorithms exist. This is quite surprising given that
for the extreme jump function almost the whole search space (all but a
$\Theta(n^{-1/2})$ fraction) is a plateau of constant fitness.
  To prove these results, we introduce new tools for the analysis of unbiased
black-box complexities, for example, selecting the new parent individual not by
comparing the fitnesses of the competing search points, but also by taking into
account the (empirical) expected fitnesses of their offspring.
Multi-Agent Shape Formation and Tracking Inspired from a Social Foraging Dynamics
Authors: Debdipta Goswami, Chiranjib Saha, Kunal Pal, Swagatam Das
Date: 2014-10-14 00:00:00

Principle of Swarm Intelligence has recently found widespread application in
formation control and automated tracking by the automated multi-agent system.
This article proposes an elegant and effective method inspired by foraging
dynamics to produce geometric-patterns by the search agents. Starting from a
random initial orientation, it is investigated how the foraging dynamics can be
modified to achieve convergence of the agents on the desired pattern with
almost uniform density. Guided through the proposed dynamics, the agents can
also track a moving point by continuously circulating around the point. An
analytical treatment supported with computer simulation results is provided to
better understand the convergence behaviour of the system.