pwc-archive/papers-with-abstracts huggingface dataset:
Informative Data Projections: A Framework and Two Examples
Authors: Tijl De Bie, Jefrey Lijffijt, Raul Santos-Rodriguez, Bo Kang
Date: 2015-11-27 00:00:00
Tasks: Vocal Bursts Valence Prediction

Methods for Projection Pursuit aim to facilitate the visual exploration of
high-dimensional data by identifying interesting low-dimensional projections. A
major challenge is the design of a suitable quality metric of projections,
commonly referred to as the projection index, to be maximized by the Projection
Pursuit algorithm. In this paper, we introduce a new information-theoretic
strategy for tackling this problem, based on quantifying the amount of
information the projection conveys to a user given their prior beliefs about
the data. The resulting projection index is a subjective quantity, explicitly
dependent on the intended user. As a useful illustration, we developed this
idea for two particular kinds of prior beliefs. The first kind leads to PCA
(Principal Component Analysis), shining new light on when PCA is (not)
appropriate. The second kind leads to a novel projection index, the
maximization of which can be regarded as a robust variant of PCA. We show how
this projection index, though non-convex, can be effectively maximized using a
modified power method as well as using a semidefinite programming relaxation.
The usefulness of this new projection index is demonstrated in comparative
empirical experiments against PCA and a popular Projection Pursuit method.
Algorithms for Differentially Private Multi-Armed Bandits
Authors: Aristide Tossou, Christos Dimitrakakis
Date: 2015-11-27 00:00:00
Tasks: Multi-Armed Bandits

We present differentially private algorithms for the stochastic Multi-Armed
Bandit (MAB) problem. This is a problem for applications such as adaptive
clinical trials, experiment design, and user-targeted advertising where private
information is connected to individual rewards. Our major contribution is to
show that there exist $(\epsilon, \delta)$ differentially private variants of
Upper Confidence Bound algorithms which have optimal regret, $O(\epsilon^{-1} +
\log T)$. This is a significant improvement over previous results, which only
achieve poly-log regret $O(\epsilon^{-2} \log^{2} T)$, because of our use of a
novel interval-based mechanism. We also substantially improve the bounds of
previous family of algorithms which use a continual release mechanism.
Experiments clearly validate our theoretical bounds.
Visual Learning of Arithmetic Operations
Authors: Yedid Hoshen, Shmuel Peleg
Date: 2015-06-07 00:00:00

A simple Neural Network model is presented for end-to-end visual learning of
arithmetic operations from pictures of numbers. The input consists of two
pictures, each showing a 7-digit number. The output, also a picture, displays
the number showing the result of an arithmetic operation (e.g., addition or
subtraction) on the two input numbers. The concepts of a number, or of an
operator, are not explicitly introduced. This indicates that addition is a
simple cognitive task, which can be learned visually using a very small number
of neurons.
  Other operations, e.g., multiplication, were not learnable using this
architecture. Some tasks were not learnable end-to-end (e.g., addition with
Roman numerals), but were easily learnable once broken into two separate
sub-tasks: a perceptual \textit{Character Recognition} and cognitive
\textit{Arithmetic} sub-tasks. This indicates that while some tasks may be
easily learnable end-to-end, other may need to be broken into sub-tasks.
Shaping Proto-Value Functions via Rewards
Authors: Chandrashekar Lakshmi Narayanan, Raj Kumar Maity, Shalabh Bhatnagar
Date: 2015-11-27 00:00:00

In this paper, we combine task-dependent reward shaping and task-independent
proto-value functions to obtain reward dependent proto-value functions (RPVFs).
In constructing the RPVFs we are making use of the immediate rewards which are
available during the sampling phase but are not used in the PVF construction.
We show via experiments that learning with an RPVF based representation is
better than learning with just reward shaping or PVFs. In particular, when the
state space is symmetrical and the rewards are asymmetrical, the RPVF capture
the asymmetry better than the PVFs.
A Stochastic Process Model of Classical Search
Authors: Dimitri Klimenko, Hanna Kurniawati, Marcus Gallagher
Date: 2015-11-27 00:00:00
Tasks: model

Among classical search algorithms with the same heuristic information, with
sufficient memory A* is essentially as fast as possible in finding a proven
optimal solution. However, in many situations optimal solutions are simply
infeasible, and thus search algorithms that trade solution quality for speed
are desirable. In this paper, we formalize the process of classical search as a
metalevel decision problem, the Abstract Search MDP. For any given optimization
criterion, this establishes a well-defined notion of the best possible
behaviour for a search algorithm and offers a theoretical approach to the
design of algorithms for that criterion. We proceed to approximately solve a
version of the Abstract Search MDP for anytime algorithms and thus derive a
novel search algorithm, Search by Maximizing the Incremental Rate of
Improvement (SMIRI). SMIRI is shown to outperform current state-of-the-art
anytime search algorithms on a parametrized stochastic tree model for most of
the tested parameter values.
Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis
Authors: Assaf Hallak, Aviv Tamar, Remi Munos, Shie Mannor
Date: 2015-09-17 00:00:00
Tasks: Off-policy evaluation

We consider the off-policy evaluation problem in Markov decision processes
with function approximation. We propose a generalization of the recently
introduced \emph{emphatic temporal differences} (ETD) algorithm
\citep{SuttonMW15}, which encompasses the original ETD($\lambda$), as well as
several other off-policy evaluation algorithms as special cases. We call this
framework \ETD, where our introduced parameter $\beta$ controls the decay rate
of an importance-sampling term. We study conditions under which the projected
fixed-point equation underlying \ETD\ involves a contraction operator, allowing
us to present the first asymptotic error bounds (bias) for \ETD. Our results
show that the original ETD algorithm always involves a contraction operator,
and its bias is bounded. Moreover, by controlling $\beta$, our proposed
generalization allows trading-off bias for variance reduction, thereby
achieving a lower total error.
Empirical Evaluation of Rectified Activations in Convolutional Network
Authors: Bing Xu, Naiyan Wang, Tianqi Chen, Mu Li
Date: 2015-05-05 00:00:00
Tasks: General Classification, image-classification, Image Classification

In this paper we investigate the performance of different types of rectified
activation functions in convolutional neural network: standard rectified linear
unit (ReLU), leaky rectified linear unit (Leaky ReLU), parametric rectified
linear unit (PReLU) and a new randomized leaky rectified linear units (RReLU).
We evaluate these activation function on standard image classification task.
Our experiments suggest that incorporating a non-zero slope for negative part
in rectified activation units could consistently improve the results. Thus our
findings are negative on the common belief that sparsity is the key of good
performance in ReLU. Moreover, on small scale dataset, using deterministic
negative slope or learning it are both prone to overfitting. They are not as
effective as using their randomized counterpart. By using RReLU, we achieved
75.68\% accuracy on CIFAR-100 test set without multiple test or ensemble.
Simultaneous Private Learning of Multiple Concepts
Authors: Mark Bun, Kobbi Nissim, Uri Stemmer
Date: 2015-11-27 00:00:00
Tasks: PAC learning

We investigate the direct-sum problem in the context of differentially
private PAC learning: What is the sample complexity of solving $k$ learning
tasks simultaneously under differential privacy, and how does this cost compare
to that of solving $k$ learning tasks without privacy? In our setting, an
individual example consists of a domain element $x$ labeled by $k$ unknown
concepts $(c_1,\ldots,c_k)$. The goal of a multi-learner is to output $k$
hypotheses $(h_1,\ldots,h_k)$ that generalize the input examples.
  Without concern for privacy, the sample complexity needed to simultaneously
learn $k$ concepts is essentially the same as needed for learning a single
concept. Under differential privacy, the basic strategy of learning each
hypothesis independently yields sample complexity that grows polynomially with
$k$. For some concept classes, we give multi-learners that require fewer
samples than the basic strategy. Unfortunately, however, we also give lower
bounds showing that even for very simple concept classes, the sample cost of
private multi-learning must grow polynomially in $k$.
Quantitative Analysis of Particles Segregation
Authors: Ting Peng, Aiping Qu, Xiaoling Wang
Date: 2015-11-19 00:00:00

Segregation is a popular phenomenon. It has considerable effects on material
performance. To the author's knowledge, there is still no automated objective
quantitative indicator for segregation. In order to full fill this task,
segregation of particles is analyzed. Edges of the particles are extracted from
the digital picture. Then, the whole picture of particles is splintered to
small rectangles with the same shape. Statistical index of the edges in each
rectangle is calculated. Accordingly, segregation between the indexes
corresponding to the rectangles is evaluated. The results show coincident with
subjective evaluated results. Further more, it can be implemented as an
automated system, which would facilitate the materials quality control
mechanism during production process.
TennisVid2Text: Fine-grained Descriptions for Domain Specific Videos
Authors: Mohak Sukhwani, C. V. Jawahar
Date: 2015-11-26 00:00:00

Automatically describing videos has ever been fascinating. In this work, we
attempt to describe videos from a specific domain - broadcast videos of lawn
tennis matches. Given a video shot from a tennis match, we intend to generate a
textual commentary similar to what a human expert would write on a sports
website. Unlike many recent works that focus on generating short captions, we
are interested in generating semantically richer descriptions. This demands a
detailed low-level analysis of the video content, specially the actions and
interactions among subjects. We address this by limiting our domain to the game
of lawn tennis. Rich descriptions are generated by leveraging a large corpus of
human created descriptions harvested from Internet. We evaluate our method on a
newly created tennis video data set. Extensive analysis demonstrate that our
approach addresses both semantic correctness as well as readability aspects
involved in the task.
SceneNet: Understanding Real World Indoor Scenes With Synthetic Data
Authors: Ankur Handa, Viorica Patraucean, Vijay Badrinarayanan, Simon Stent, Roberto Cipolla
Date: 2015-11-22 00:00:00
Tasks: Scene Understanding

Scene understanding is a prerequisite to many high level tasks for any
automated intelligent machine operating in real world environments. Recent
attempts with supervised learning have shown promise in this direction but also
highlighted the need for enormous quantity of supervised data --- performance
increases in proportion to the amount of data used. However, this quickly
becomes prohibitive when considering the manual labour needed to collect such
data. In this work, we focus our attention on depth based semantic per-pixel
labelling as a scene understanding problem and show the potential of computer
graphics to generate virtually unlimited labelled data from synthetic 3D
scenes. By carefully synthesizing training data with appropriate noise models
we show comparable performance to state-of-the-art RGBD systems on NYUv2
dataset despite using only depth data as input and set a benchmark on
depth-based segmentation on SUN RGB-D dataset. Additionally, we offer a route
to generating synthesized frame or video data, and understanding of different
factors influencing performance gains.
Some Epistemological Problems with the Knowledge Level in Cognitive Architectures
Authors: Antonio Lieto
Date: 2015-11-26 00:00:00
Tasks: General Knowledge

This article addresses an open problem in the area of cognitive systems and
architectures: namely the problem of handling (in terms of processing and
reasoning capabilities) complex knowledge structures that can be at least
plausibly comparable, both in terms of size and of typology of the encoded
information, to the knowledge that humans process daily for executing everyday
activities. Handling a huge amount of knowledge, and selectively retrieve it
ac- cording to the needs emerging in different situational scenarios, is an
important aspect of human intelligence. For this task, in fact, humans adopt a
wide range of heuristics (Gigerenzer and Todd) due to their bounded rationality
(Simon, 1957). In this perspective, one of the re- quirements that should be
considered for the design, the realization and the evaluation of intelligent
cognitively inspired systems should be represented by their ability of
heuristically identify and retrieve, from the general knowledge stored in their
artificial Long Term Memory (LTM), that one which is synthetically and
contextually relevant. This require- ment, however, is often neglected.
Currently, artificial cognitive systems and architectures are not able, de
facto, to deal with complex knowledge structures that can be even slightly
comparable to the knowledge heuris- tically managed by humans. In this paper I
will argue that this is not only a technological problem but also an
epistemological one and I will briefly sketch a proposal for a possible
solution.
Bayesian Network Models for Adaptive Testing
Authors: Martin Plajner, Jiří Vomlel
Date: 2015-11-26 00:00:00
Tasks: Model Selection

Computerized adaptive testing (CAT) is an interesting and promising approach
to testing human abilities. In our research we use Bayesian networks to create
a model of tested humans. We collected data from paper tests performed with
grammar school students. In this article we first provide the summary of data
used for our experiments. We propose several different Bayesian networks, which
we tested and compared by cross-validation. Interesting results were obtained
and are discussed in the paper. The analysis has brought a clearer view on the
model selection problem. Future research is outlined in the concluding part of
the paper.
Distributed Machine Learning via Sufficient Factor Broadcasting
Authors: Pengtao Xie, Jin Kyu Kim, Yi Zhou, Qirong Ho, Abhimanu Kumar, Yao-Liang Yu, Eric Xing
Date: 2015-11-26 00:00:00
Tasks: BIG-bench Machine Learning

Matrix-parametrized models, including multiclass logistic regression and
sparse coding, are used in machine learning (ML) applications ranging from
computer vision to computational biology. When these models are applied to
large-scale ML problems starting at millions of samples and tens of thousands
of classes, their parameter matrix can grow at an unexpected rate, resulting in
high parameter synchronization costs that greatly slow down distributed
learning. To address this issue, we propose a Sufficient Factor Broadcasting
(SFB) computation model for efficient distributed learning of a large family of
matrix-parameterized models, which share the following property: the parameter
update computed on each data sample is a rank-1 matrix, i.e., the outer product
of two "sufficient factors" (SFs). By broadcasting the SFs among worker
machines and reconstructing the update matrices locally at each worker, SFB
improves communication efficiency --- communication costs are linear in the
parameter matrix's dimensions, rather than quadratic --- without affecting
computational correctness. We present a theoretical convergence analysis of
SFB, and empirically corroborate its efficiency on four different
matrix-parametrized ML models.
An analysis of the factors affecting keypoint stability in scale-space
Authors: Ives Rey-Otero, Jean-Michel Morel, Mauricio Delbracio
Date: 2015-11-26 00:00:00
Tasks: Keypoint Detection

The most popular image matching algorithm SIFT, introduced by D. Lowe a
decade ago, has proven to be sufficiently scale invariant to be used in
numerous applications. In practice, however, scale invariance may be weakened
by various sources of error inherent to the SIFT implementation affecting the
stability and accuracy of keypoint detection. The density of the sampling of
the Gaussian scale-space and the level of blur in the input image are two of
these sources. This article presents a numerical analysis of their impact on
the extracted keypoints stability. Such an analysis has both methodological and
practical implications, on how to compare feature detectors and on how to
improve SIFT. We show that even with a significantly oversampled scale-space
numerical errors prevent from achieving perfect stability. Usual strategies to
filter out unstable detections are shown to be inefficient. We also prove that
the effect of the error in the assumption on the initial blur is asymmetric and
that the method is strongly degraded in presence of aliasing or without a
correct assumption on the camera blur.
A Symbolic SAT-based Algorithm for Almost-sure Reachability with Small Strategies in POMDPs
Authors: Krishnendu Chatterjee, Martin Chmelik, Jessica Davies
Date: 2015-11-26 00:00:00

POMDPs are standard models for probabilistic planning problems, where an
agent interacts with an uncertain environment. We study the problem of
almost-sure reachability, where given a set of target states, the question is
to decide whether there is a policy to ensure that the target set is reached
with probability 1 (almost-surely). While in general the problem is
EXPTIME-complete, in many practical cases policies with a small amount of
memory suffice. Moreover, the existing solution to the problem is explicit,
which first requires to construct explicitly an exponential reduction to a
belief-support MDP. In this work, we first study the existence of
observation-stationary strategies, which is NP-complete, and then small-memory
strategies. We present a symbolic algorithm by an efficient encoding to SAT and
using a SAT solver for the problem. We report experimental results
demonstrating the scalability of our symbolic (SAT-based) approach.
Towards Automatic Image Editing: Learning to See another You
Authors: Amir Ghodrati, Xu Jia, Marco Pedersoli, Tinne Tuytelaars
Date: 2015-11-26 00:00:00
Tasks: Attribute, Image Generation, Retrieval

Learning the distribution of images in order to generate new samples is a
challenging task due to the high dimensionality of the data and the highly
non-linear relations that are involved. Nevertheless, some promising results
have been reported in the literature recently,building on deep network
architectures. In this work, we zoom in on a specific type of image generation:
given an image and knowing the category of objects it belongs to (e.g. faces),
our goal is to generate a similar and plausible image, but with some altered
attributes. This is particularly challenging, as the model needs to learn to
disentangle the effect of each attribute and to apply a desired attribute
change to a given input image, while keeping the other attributes and overall
object appearance intact. To this end, we learn a convolutional network, where
the desired attribute information is encoded then merged with the encoded image
at feature map level. We show promising results, both qualitatively as well as
quantitatively, in the context of a retrieval experiment, on two face datasets
(MultiPie and CAS-PEAL-R1).
TGSum: Build Tweet Guided Multi-Document Summarization Dataset
Authors: Ziqiang Cao, Chengyao Chen, Wenjie Li, Sujian Li, Furu Wei, Ming Zhou
Date: 2015-11-26 00:00:00
Tasks: Document Summarization, Informativeness, Multi-Document Summarization, Sentence

The development of summarization research has been significantly hampered by
the costly acquisition of reference summaries. This paper proposes an effective
way to automatically collect large scales of news-related multi-document
summaries with reference to social media's reactions. We utilize two types of
social labels in tweets, i.e., hashtags and hyper-links. Hashtags are used to
cluster documents into different topic sets. Also, a tweet with a hyper-link
often highlights certain key points of the corresponding document. We
synthesize a linked document cluster to form a reference summary which can
cover most key points. To this aim, we adopt the ROUGE metrics to measure the
coverage ratio, and develop an Integer Linear Programming solution to discover
the sentence set reaching the upper bound of ROUGE. Since we allow summary
sentences to be selected from both documents and high-quality tweets, the
generated reference summaries could be abstractive. Both informativeness and
readability of the collected summaries are verified by manual judgment. In
addition, we train a Support Vector Regression summarizer on DUC generic
multi-document summarization benchmarks. With the collected data as extra
training resource, the performance of the summarizer improves a lot on all the
test sets. We release this dataset for further research.
OntoSeg: a Novel Approach to Text Segmentation using Ontological Similarity
Authors: Mostafa Bayomi, Killian Levacher, M. Rami Ghorab, Séamus Lawless
Date: 2015-11-26 00:00:00
Tasks: Clustering, Information Retrieval, Retrieval, Segmentation, Text Segmentation

Text segmentation (TS) aims at dividing long text into coherent segments
which reflect the subtopic structure of the text. It is beneficial to many
natural language processing tasks, such as Information Retrieval (IR) and
document summarisation. Current approaches to text segmentation are similar in
that they all use word-frequency metrics to measure the similarity between two
regions of text, so that a document is segmented based on the lexical cohesion
between its words. Various NLP tasks are now moving towards the semantic web
and ontologies, such as ontology-based IR systems, to capture the
conceptualizations associated with user needs and contents. Text segmentation
based on lexical cohesion between words is hence not sufficient anymore for
such tasks. This paper proposes OntoSeg, a novel approach to text segmentation
based on the ontological similarity between text blocks. The proposed method
uses ontological similarity to explore conceptual relations between text
segments and a Hierarchical Agglomerative Clustering (HAC) algorithm to
represent the text as a tree-like hierarchy that is conceptually structured.
The rich structure of the created tree further allows the segmentation of text
in a linear fashion at various levels of granularity. The proposed method was
evaluated on a wellknown dataset, and the results show that using ontological
similarity in text segmentation is very promising. Also we enhance the proposed
method by combining ontological similarity with lexical similarity and the
results show an enhancement of the segmentation quality.
Gains and Losses are Fundamentally Different in Regret Minimization: The Sparse Case
Authors: Joon Kwon, Vianney Perchet
Date: 2015-11-26 00:00:00

We demonstrate that, in the classical non-stochastic regret minimization
problem with $d$ decisions, gains and losses to be respectively maximized or
minimized are fundamentally different. Indeed, by considering the additional
sparsity assumption (at each stage, at most $s$ decisions incur a nonzero
outcome), we derive optimal regret bounds of different orders. Specifically,
with gains, we obtain an optimal regret guarantee after $T$ stages of order
$\sqrt{T\log s}$, so the classical dependency in the dimension is replaced by
the sparsity size. With losses, we provide matching upper and lower bounds of
order $\sqrt{Ts\log(d)/d}$, which is decreasing in $d$. Eventually, we also
study the bandit setting, and obtain an upper bound of order $\sqrt{Ts\log
(d/s)}$ when outcomes are losses. This bound is proven to be optimal up to the
logarithmic factor $\sqrt{\log(d/s)}$.