pwc-archive/papers-with-abstracts huggingface dataset:
Image Compressive Sensing Recovery Using Adaptively Learned Sparsifying Basis via L0 Minimization
Authors: Jian Zhang, Chen Zhao, Debin Zhao, Wen Gao
Date: 2014-04-30 00:00:00
Tasks: Blocking, Compressive Sensing

From many fewer acquired measurements than suggested by the Nyquist sampling
theory, compressive sensing (CS) theory demonstrates that, a signal can be
reconstructed with high probability when it exhibits sparsity in some domain.
Most of the conventional CS recovery approaches, however, exploited a set of
fixed bases (e.g. DCT, wavelet and gradient domain) for the entirety of a
signal, which are irrespective of the non-stationarity of natural signals and
cannot achieve high enough degree of sparsity, thus resulting in poor CS
recovery performance. In this paper, we propose a new framework for image
compressive sensing recovery using adaptively learned sparsifying basis via L0
minimization. The intrinsic sparsity of natural images is enforced
substantially by sparsely representing overlapped image patches using the
adaptively learned sparsifying basis in the form of L0 norm, greatly reducing
blocking artifacts and confining the CS solution space. To make our proposed
scheme tractable and robust, a split Bregman iteration based technique is
developed to solve the non-convex L0 minimization problem efficiently.
Experimental results on a wide range of natural images for CS recovery have
shown that our proposed algorithm achieves significant performance improvements
over many current state-of-the-art schemes and exhibits good convergence
property.
Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
Authors: Yuchen Zhang, John C. Duchi, Martin J. Wainwright
Date: 2013-05-22 00:00:00
Tasks: regression

We establish optimal convergence rates for a decomposition-based scalable
approach to kernel ridge regression. The method is simple to describe: it
randomly partitions a dataset of size N into m subsets of equal size, computes
an independent kernel ridge regression estimator for each subset, then averages
the local solutions into a global predictor. This partitioning leads to a
substantial reduction in computation time versus the standard approach of
performing kernel ridge regression on all N samples. Our two main theorems
establish that despite the computational speed-up, statistical optimality is
retained: as long as m is not too large, the partition-based estimator achieves
the statistical minimax rate over all estimators using the set of N samples. As
concrete examples, our theory guarantees that the number of processors m may
grow nearly linearly for finite-rank kernels and Gaussian kernels and
polynomially in N for Sobolev spaces, which in turn allows for substantial
reductions in computational cost. We conclude with experiments on both
simulated data and a music-prediction task that complement our theoretical
results, exhibiting the computational and statistical benefits of our approach.
An Approach to Forgetting in Disjunctive Logic Programs that Preserves Strong Equivalence
Authors: James P. Delgrande, Kewen Wang
Date: 2014-04-29 00:00:00

In this paper we investigate forgetting in disjunctive logic programs, where
forgetting an atom from a program amounts to a reduction in the signature of
that program. The goal is to provide an approach that is syntax-independent, in
that if two programs are strongly equivalent, then the results of forgetting an
atom in each program should also be strongly equivalent. Our central definition
of forgetting is impractical but satisfies this goal: Forgetting an atom is
characterised by the set of SE consequences of the program that do not mention
the atom to be forgotten. We then provide an equivalent, practical definition,
wherein forgetting an atom $p$ is given by those rules in the program that
don't mention $p$, together with rules obtained by a single inference step from
rules that do mention $p$. Forgetting is shown to have appropriate properties;
as well, the finite characterisation results in a modest (at worst quadratic)
blowup. Finally we have also obtained a prototype implementation of this
approach to forgetting.
The Information Geometry of Mirror Descent
Authors: Garvesh Raskutti, Sayan Mukherjee
Date: 2013-10-29 00:00:00
Tasks: parameter estimation

Information geometry applies concepts in differential geometry to probability
and statistics and is especially useful for parameter estimation in exponential
families where parameters are known to lie on a Riemannian manifold.
Connections between the geometric properties of the induced manifold and
statistical properties of the estimation problem are well-established. However
developing first-order methods that scale to larger problems has been less of a
focus in the information geometry community. The best known algorithm that
incorporates manifold structure is the second-order natural gradient descent
algorithm introduced by Amari. On the other hand, stochastic approximation
methods have led to the development of first-order methods for optimizing noisy
objective functions. A recent generalization of the Robbins-Monro algorithm
known as mirror descent, developed by Nemirovski and Yudin is a first order
method that induces non-Euclidean geometries. However current analysis of
mirror descent does not precisely characterize the induced non-Euclidean
geometry nor does it consider performance in terms of statistical relative
efficiency. In this paper, we prove that mirror descent induced by Bregman
divergences is equivalent to the natural gradient descent algorithm on the dual
Riemannian manifold. Using this equivalence, it follows that (1) mirror descent
is the steepest descent direction along the Riemannian manifold of the
exponential family; (2) mirror descent with log-likelihood loss applied to
parameter estimation in exponential families asymptotically achieves the
classical Cram\'er-Rao lower bound and (3) natural gradient descent for
manifolds corresponding to exponential families can be implemented as a
first-order method through mirror descent.
Implementing spectral methods for hidden Markov models with real-valued emissions
Authors: Carl Mattfeld
Date: 2014-04-29 00:00:00
Tasks: parameter estimation, Time Series, Time Series Analysis

Hidden Markov models (HMMs) are widely used statistical models for modeling
sequential data. The parameter estimation for HMMs from time series data is an
important learning problem. The predominant methods for parameter estimation
are based on local search heuristics, most notably the expectation-maximization
(EM) algorithm. These methods are prone to local optima and oftentimes suffer
from high computational and sample complexity. Recent years saw the emergence
of spectral methods for the parameter estimation of HMMs, based on a method of
moments approach. Two spectral learning algorithms as proposed by Hsu, Kakade
and Zhang 2012 (arXiv:0811.4413) and Anandkumar, Hsu and Kakade 2012
(arXiv:1203.0683) are assessed in this work. Using experiments with synthetic
data, the algorithms are compared with each other. Furthermore, the spectral
methods are compared to the Baum-Welch algorithm, a well-established method
applying the EM algorithm to HMMs. The spectral algorithms are found to have a
much more favorable computational and sample complexity. Even though the
algorithms readily handle high dimensional observation spaces, instability
issues are encountered in this regime. In view of learning from real-world
experimental data, the representation of real-valued observations for the use
in spectral methods is discussed, presenting possible methods to represent data
for the use in the learning algorithms.
Information-Theoretic Bounds for Adaptive Sparse Recovery
Authors: Cem Aksoylar, Venkatesh Saligrama
Date: 2014-02-24 00:00:00
Tasks: Compressive Sensing

We derive an information-theoretic lower bound for sample complexity in
sparse recovery problems where inputs can be chosen sequentially and
adaptively. This lower bound is in terms of a simple mutual information
expression and unifies many different linear and nonlinear observation models.
Using this formula we derive bounds for adaptive compressive sensing (CS),
group testing and 1-bit CS problems. We show that adaptivity cannot decrease
sample complexity in group testing, 1-bit CS and CS with linear sparsity. In
contrast, we show there might be mild performance gains for CS in the sublinear
regime. Our unified analysis also allows characterization of gains due to
adaptivity from a wider perspective on sparse problems.
Identification of structural features in chemicals associated with cancer drug response: A systematic data-driven analysis
Authors: Suleiman A. Khan, Seppo Virtanen, Olli P Kallioniemi, Krister Wennerberg, Antti Poso, Samuel Kaski
Date: 2013-12-30 00:00:00

Motivation: Analysis of relationships of drug structure to biological
response is key to understanding off-target and unexpected drug effects, and
for developing hypotheses on how to tailor drug thera-pies. New methods are
required for integrated analyses of a large number of chemical features of
drugs against the corresponding genome-wide responses of multiple cell models.
Results: In this paper, we present the first comprehensive multi-set analysis
on how the chemical structure of drugs impacts on ge-nome-wide gene expression
across several cancer cell lines (CMap database). The task is formulated as
searching for drug response components across multiple cancers to reveal shared
effects of drugs and the chemical features that may be responsible. The
com-ponents can be computed with an extension of a very recent ap-proach called
Group Factor Analysis (GFA). We identify 11 compo-nents that link the
structural descriptors of drugs with specific gene expression responses
observed in the three cell lines, and identify structural groups that may be
responsible for the responses. Our method quantitatively outperforms the
limited earlier studies on CMap and identifies both the previously reported
associations and several interesting novel findings, by taking into account
multiple cell lines and advanced 3D structural descriptors. The novel
observations include: previously unknown similarities in the effects induced by
15-delta prostaglandin J2 and HSP90 inhibitors, which are linked to the 3D
descriptors of the drugs; and the induction by simvastatin of leukemia-specific
anti-inflammatory response, resem-bling the effects of corticosteroids.
Analysis of Dialogical Argumentation via Finite State Machines
Authors: Anthony Hunter
Date: 2014-04-29 00:00:00

Dialogical argumentation is an important cognitive activity by which agents
exchange arguments and counterarguments as part of some process such as
discussion, debate, persuasion and negotiation. Whilst numerous formal systems
have been proposed, there is a lack of frameworks for implementing and
evaluating these proposals. First-order executable logic has been proposed as a
general framework for specifying and analysing dialogical argumentation. In
this paper, we investigate how we can implement systems for dialogical
argumentation using propositional executable logic. Our approach is to present
and evaluate an algorithm that generates a finite state machine that reflects a
propositional executable logic specification for a dialogical argumentation
together with an initial state. We also consider how the finite state machines
can be analysed, with the minimax strategy being used as an illustration of the
kinds of empirical analysis that can be undertaken.
Near-Optimal Adaptive Compressed Sensing
Authors: Matthew L. Malloy, Robert D. Nowak
Date: 2013-06-26 00:00:00
Tasks: compressed sensing

This paper proposes a simple adaptive sensing and group testing algorithm for
sparse signal recovery. The algorithm, termed Compressive Adaptive Sense and
Search (CASS), is shown to be near-optimal in that it succeeds at the lowest
possible signal-to-noise-ratio (SNR) levels, improving on previous work in
adaptive compressed sensing. Like traditional compressed sensing based on
random non-adaptive design matrices, the CASS algorithm requires only k log n
measurements to recover a k-sparse signal of dimension n. However, CASS
succeeds at SNR levels that are a factor log n less than required by standard
compressed sensing. From the point of view of constructing and implementing the
sensing operation as well as computing the reconstruction, the proposed
algorithm is substantially less computationally intensive than standard
compressed sensing. CASS is also demonstrated to perform considerably better in
practice through simulation. To the best of our knowledge, this is the first
demonstration of an adaptive compressed sensing algorithm with near-optimal
theoretical guarantees and excellent practical performance. This paper also
shows that methods like compressed sensing, group testing, and pooling have an
advantage beyond simply reducing the number of measurements or tests --
adaptive versions of such methods can also improve detection and estimation
performance when compared to non-adaptive direct (uncompressed) sensing.
Concise comparative summaries (CCS) of large text corpora with a human experiment
Authors: Jinzhu Jia, Luke Miratrix, Bin Yu, Brian Gawalt, Laurent El Ghaoui, Luke Barnesmoore, Sophie Clavier
Date: 2014-04-29 00:00:00
Tasks: Articles, General Classification

In this paper we propose a general framework for topic-specific summarization
of large text corpora and illustrate how it can be used for the analysis of
news databases. Our framework, concise comparative summarization (CCS), is
built on sparse classification methods. CCS is a lightweight and flexible tool
that offers a compromise between simple word frequency based methods currently
in wide use and more heavyweight, model-intensive methods such as latent
Dirichlet allocation (LDA). We argue that sparse methods have much to offer for
text analysis and hope CCS opens the door for a new branch of research in this
important field. For a particular topic of interest (e.g., China or energy),
CSS automatically labels documents as being either on- or off-topic (usually
via keyword search), and then uses sparse classification methods to predict
these labels with the high-dimensional counts of all the other words and
phrases in the documents. The resulting small set of phrases found as
predictive are then harvested as the summary. To validate our tool, we, using
news articles from the New York Times international section, designed and
conducted a human survey to compare the different summarizers with human
understanding. We demonstrate our approach with two case studies, a media
analysis of the framing of "Egypt" in the New York Times throughout the Arab
Spring and an informal comparison of the New York Times' and Wall Street
Journal's coverage of "energy." Overall, we find that the Lasso with $L^2$
normalization can be effectively and usefully used to summarize large corpora,
regardless of document size.
Generalized Nonconvex Nonsmooth Low-Rank Minimization
Authors: Canyi Lu, Jinhui Tang, Shuicheng Yan, Zhouchen Lin
Date: 2014-04-29 00:00:00
Proceeding: CVPR 2014 6

As surrogate functions of $L_0$-norm, many nonconvex penalty functions have
been proposed to enhance the sparse vector recovery. It is easy to extend these
nonconvex penalty functions on singular values of a matrix to enhance low-rank
matrix recovery. However, different from convex optimization, solving the
nonconvex low-rank minimization problem is much more challenging than the
nonconvex sparse minimization problem. We observe that all the existing
nonconvex penalty functions are concave and monotonically increasing on
$[0,\infty)$. Thus their gradients are decreasing functions. Based on this
property, we propose an Iteratively Reweighted Nuclear Norm (IRNN) algorithm to
solve the nonconvex nonsmooth low-rank minimization problem. IRNN iteratively
solves a Weighted Singular Value Thresholding (WSVT) problem. By setting the
weight vector as the gradient of the concave penalty function, the WSVT problem
has a closed form solution. In theory, we prove that IRNN decreases the
objective function value monotonically, and any limit point is a stationary
point. Extensive experiments on both synthetic data and real images demonstrate
that IRNN enhances the low-rank matrix recovery compared with state-of-the-art
convex algorithms.
Arguments for Nested Patterns in Neural Ensembles
Authors: Kieran Greer
Date: 2014-03-25 00:00:00

This paper describes a relatively simple way of allowing a brain model to
self-organise its concept patterns through nested structures. Time is a key
element and a simulator would be able to show how patterns may form and then
fire in sequence, as part of a search or thought process. It uses a very simple
equation to show how the inhibitors in particular, can switch off certain
areas, to allow other areas to become the prominent ones and thereby define the
current brain state. This allows for a small amount of control over what
appears to be a chaotic structure inside of the brain. It is attractive because
it is still mostly mechanical and therefore can be added as an automatic
process, or the modelling of that. The paper also describes how the nested
pattern structure can be used as a basic counting mechanism.
Code Minimization for Fringe Projection Based 3D Stereo Sensors by Calibration Improvement
Authors: Christian Bräuer-Burchardt, Peter Kühmstedt, Gunther Notni
Date: 2014-04-29 00:00:00

Code minimization provides a speed-up of the processing time of fringe
projection based stereo sensors and possibly makes them real-time applicable.
This paper reports a methodology which enables such sensors to completely omit
Gray code or other additional code. Only a sequence of sinusoidal images is
necessary. The code reduction is achieved by involvement of the projection unit
into the measurement, double triangulation, and a precise projector calibration
or significant projector calibration improvement, respectively.
A Deep Architecture for Semantic Parsing
Authors: Edward Grefenstette, Phil Blunsom, Nando de Freitas, Karl Moritz Hermann
Date: 2014-04-29 00:00:00
Proceeding: WS 2014 6
Tasks: Semantic Parsing

Many successful approaches to semantic parsing build on top of the syntactic
analysis of text, and make use of distributional representations or statistical
models to match parses to ontology-specific queries. This paper presents a
novel deep learning architecture which provides a semantic parsing system
through the union of two neural models of language semantics. It allows for the
generation of ontology-specific queries from natural language statements and
questions without the need for parsing, which makes it especially suitable to
grammatically malformed or syntactically atypical text, such as tweets, as well
as permitting the development of semantic parsers for resource-poor languages.
A Complete Solver for Constraint Games
Authors: Thi-Van-Anh Nguyen, Arnaud Lallouet
Date: 2014-04-17 00:00:00

Game Theory studies situations in which multiple agents having conflicting
objectives have to reach a collective decision. The question of a compact
representation language for agents utility function is of crucial importance
since the classical representation of a $n$-players game is given by a
$n$-dimensional matrix of exponential size for each player. In this paper we
use the framework of Constraint Games in which CSP are used to represent
utilities. Constraint Programming --including global constraints-- allows to
easily give a compact and elegant model to many useful games. Constraint Games
come in two flavors: Constraint Satisfaction Games and Constraint Optimization
Games, the first one using satisfaction to define boolean utilities. In
addition to multimatrix games, it is also possible to model more complex games
where hard constraints forbid certain situations. In this paper we study
complete search techniques and show that our solver using the compact
representation of Constraint Games is faster than the classical game solver
Gambit by one to two orders of magnitude.
Assessing the players'performance in the game of bridge: A fuzzy logic approach
Authors: Michael Gr. Voskoglou
Date: 2014-04-29 00:00:00

Contract bridge occupies nowadays a position of great prestige being,
together with chess, the only mind games officially recognized by the
International Olympic Committee. In the present paper an innovative method for
assessing the total performance of bridge- players' belonging to groups of
special interest(e.g. different bridge clubs during a tournament, men and
women, new and old players, etc) is introduced, which is based on principles of
fuzzy logic. For this, the cohorts under assessment are represented as fuzzy
subsets of a set of linguistic labels characterizing their performance and the
centroid defuzzification method is used to convert the fuzzy data collected
from the game to a crisp number. This new method of assessment could be used
informally as a complement of the official bridge-scoring methods for
statistical and other obvious reasons. Two real applications related to
simultaneous tournaments with pre-dealt boards, organized by the Hellenic
Bridge Federation, are also presented, illustrating the importance of our
results in practice.
Do we need Asimov's Laws?
Authors: Ulrike Barthelmess, Ulrich Furbach
Date: 2014-04-29 00:00:00
Tasks: Cultural Vocal Bursts Intensity Prediction

In this essay the stance on robots is discussed. The attitude against robots
in history, starting in Ancient Greek culture until the industrial revolution
is described. The uncanny valley and some possible explanations are given. Some
differences in Western and Asian understanding of robots are listed and finally
we answer the question raised with the title.
Stereo on a budget
Authors: Dana Menaker, Shai Avidan
Date: 2014-04-28 00:00:00
Tasks: Decoder, Image Compression, Stereo Matching, Stereo Matching Hand

We propose an algorithm for recovering depth using less than two images.
Instead of having both cameras send their entire image to the host computer,
the left camera sends its image to the host while the right camera sends only a
fraction $\epsilon$ of its image. The key aspect is that the cameras send the
information without communicating at all. Hence, the required communication
bandwidth is significantly reduced.
  While standard image compression techniques can reduce the communication
bandwidth, this requires additional computational resources on the part of the
encoder (camera). We aim at designing a light weight encoder that only touches
a fraction of the pixels. The burden of decoding is placed on the decoder
(host).
  We show that it is enough for the encoder to transmit a sparse set of pixels.
Using only $1+\epsilon$ images, with $\epsilon$ as little as 2% of the image,
the decoder can compute a depth map. The depth map's accuracy is comparable to
traditional stereo matching algorithms that require both images as input. Using
the depth map and the left image, the right image can be synthesized. No
computations are required at the encoder, and the decoder's runtime is linear
in the images' size.
Robust Logistic Regression using Shift Parameters (Long Version)
Authors: Julie Tibshirani, Christopher D. Manning
Date: 2013-05-21 00:00:00
Tasks: named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER), regression

Annotation errors can significantly hurt classifier performance, yet datasets
are only growing noisier with the increased use of Amazon Mechanical Turk and
techniques like distant supervision that automatically generate labels. In this
paper, we present a robust extension of logistic regression that incorporates
the possibility of mislabelling directly into the objective. Our model can be
trained through nearly the same means as logistic regression, and retains its
efficiency on high-dimensional datasets. Through named entity recognition
experiments, we demonstrate that our approach can provide a significant
improvement over the standard model when annotation errors are present.