pwc-archive/papers-with-abstracts huggingface dataset:
The Relationship Between Agnostic Selective Classification Active Learning and the Disagreement Coefficient
Authors: Roei Gelbhart, Ran El-Yaniv
Date: 2017-03-19 00:00:00
Tasks: Active Learning, General Classification

A selective classifier (f,g) comprises a classification function f and a
binary selection function g, which determines if the classifier abstains from
prediction, or uses f to predict. The classifier is called
pointwise-competitive if it classifies each point identically to the best
classifier in hindsight (from the same class), whenever it does not abstain.
The quality of such a classifier is quantified by its rejection mass, defined
to be the probability mass of the points it rejects. A "fast" rejection rate is
achieved if the rejection mass is bounded from above by O(1/m) where m is the
number of labeled examples used to train the classifier (and O hides
logarithmic factors). Pointwise-competitive selective (PCS) classifiers are
intimately related to disagreement-based active learning and it is known that
in the realizable case, a fast rejection rate of a known PCS algorithm (called
Consistent Selective Strategy) is equivalent to an exponential speedup of the
well-known CAL active algorithm.
  We focus on the agnostic setting, for which there is a known algorithm called
LESS that learns a PCS classifier and achieves a fast rejection rate (depending
on Hanneke's disagreement coefficient) under strong assumptions. We present an
improved PCS learning algorithm called ILESS for which we show a fast rate
(depending on Hanneke's disagreement coefficient) without any assumptions. Our
rejection bound smoothly interpolates the realizable and agnostic settings. The
main result of this paper is an equivalence between the following three
entities: (i) the existence of a fast rejection rate for any PCS learning
algorithm (such as ILESS); (ii) a poly-logarithmic bound for Hanneke's
disagreement coefficient; and (iii) an exponential speedup for a new
disagreement-based active learner called ActiveiLESS.
From Deep to Shallow: Transformations of Deep Rectifier Networks
Authors: Senjian An, Farid Boussaid, Mohammed Bennamoun, Jiankun Hu
Date: 2017-03-30 00:00:00

In this paper, we introduce transformations of deep rectifier networks,
enabling the conversion of deep rectifier networks into shallow rectifier
networks. We subsequently prove that any rectifier net of any depth can be
represented by a maximum of a number of functions that can be realized by a
shallow network with a single hidden layer. The transformations of both deep
rectifier nets and deep residual nets are conducted to demonstrate the
advantages of the residual nets over the conventional neural nets and the
advantages of the deep neural nets over the shallow neural nets. In summary,
for two rectifier nets with different depths but with same total number of
hidden units, the corresponding single hidden layer representation of the
deeper net is much more complex than the corresponding single hidden
representation of the shallower net. Similarly, for a residual net and a
conventional rectifier net with the same structure except for the skip
connections in the residual net, the corresponding single hidden layer
representation of the residual net is much more complex than the corresponding
single hidden layer representation of the conventional net.
Automated News Suggestions for Populating Wikipedia Entity Pages
Authors: Besnik Fetahu, Katja Markert, Avishek Anand
Date: 2017-03-30 00:00:00
Tasks: Articles, Knowledge Base Construction

Wikipedia entity pages are a valuable source of information for direct
consumption and for knowledge-base construction, update and maintenance. Facts
in these entity pages are typically supported by references. Recent studies
show that as much as 20\% of the references are from online news sources.
However, many entity pages are incomplete even if relevant information is
already available in existing news articles. Even for the already present
references, there is often a delay between the news article publication time
and the reference time. In this work, we therefore look at Wikipedia through
the lens of news and propose a novel news-article suggestion task to improve
news coverage in Wikipedia, and reduce the lag of newsworthy references. Our
work finds direct application, as a precursor, to Wikipedia page generation and
knowledge-base acceleration tasks that rely on relevant and high quality input
sources.
  We propose a two-stage supervised approach for suggesting news articles to
entity pages for a given state of Wikipedia. First, we suggest news articles to
Wikipedia entities (article-entity placement) relying on a rich set of features
which take into account the \emph{salience} and \emph{relative authority} of
entities, and the \emph{novelty} of news articles to entity pages. Second, we
determine the exact section in the entity page for the input article
(article-section placement) guided by class-based section templates. We perform
an extensive evaluation of our approach based on ground-truth data that is
extracted from external references in Wikipedia. We achieve a high precision
value of up to 93\% in the \emph{article-entity} suggestion stage and upto 84\%
for the \emph{article-section placement}. Finally, we compare our approach
against competitive baselines and show significant improvements.
Person Search with Natural Language Description
Authors: Shuang Li, Tong Xiao, Hongsheng Li, Bolei Zhou, Dayu Yue, Xiaogang Wang
Date: 2017-02-19 00:00:00
Proceeding: CVPR 2017 7
Tasks: Attribute, Person Search, Text based Person Retrieval

Searching persons in large-scale image databases with the query of natural
language description has important applications in video surveillance. Existing
methods mainly focused on searching persons with image-based or attribute-based
queries, which have major limitations for a practical usage. In this paper, we
study the problem of person search with natural language description. Given the
textual description of a person, the algorithm of the person search is required
to rank all the samples in the person database then retrieve the most relevant
sample corresponding to the queried description. Since there is no person
dataset or benchmark with textual description available, we collect a
large-scale person description dataset with detailed natural language
annotations and person samples from various sources, termed as CUHK Person
Description Dataset (CUHK-PEDES). A wide range of possible models and baselines
have been evaluated and compared on the person search benchmark. An Recurrent
Neural Network with Gated Neural Attention mechanism (GNA-RNN) is proposed to
establish the state-of-the art performance on person search.
Efficient Benchmarking of Algorithm Configuration Procedures via Model-Based Surrogates
Authors: Katharina Eggensperger, Marius Lindauer, Holger H. Hoos, Frank Hutter, Kevin Leyton-Brown
Date: 2017-03-30 00:00:00
Tasks: Benchmarking, Hyperparameter Optimization

The optimization of algorithm (hyper-)parameters is crucial for achieving
peak performance across a wide range of domains, ranging from deep neural
networks to solvers for hard combinatorial problems. The resulting algorithm
configuration (AC) problem has attracted much attention from the machine
learning community. However, the proper evaluation of new AC procedures is
hindered by two key hurdles. First, AC benchmarks are hard to set up. Second
and even more significantly, they are computationally expensive: a single run
of an AC procedure involves many costly runs of the target algorithm whose
performance is to be optimized in a given AC benchmark scenario. One common
workaround is to optimize cheap-to-evaluate artificial benchmark functions
(e.g., Branin) instead of actual algorithms; however, these have different
properties than realistic AC problems. Here, we propose an alternative
benchmarking approach that is similarly cheap to evaluate but much closer to
the original AC problem: replacing expensive benchmarks by surrogate benchmarks
constructed from AC benchmarks. These surrogate benchmarks approximate the
response surface corresponding to true target algorithm performance using a
regression model, and the original and surrogate benchmark share the same
(hyper-)parameter space. In our experiments, we construct and evaluate
surrogate benchmarks for hyperparameter optimization as well as for AC problems
that involve performance optimization of solvers for hard combinatorial
problems, drawing training data from the runs of existing AC procedures. We
show that our surrogate benchmarks capture overall important characteristics of
the AC scenarios, such as high- and low-performing regions, from which they
were derived, while being much easier to use and orders of magnitude cheaper to
evaluate.
Principled Option Learning in Markov Decision Processes
Authors: Roy Fox, Michal Moshkovitz, Naftali Tishby
Date: 2016-09-18 00:00:00

It is well known that options can make planning more efficient, among their
many benefits. Thus far, algorithms for autonomously discovering a set of
useful options were heuristic. Naturally, a principled way of finding a set of
useful options may be more promising and insightful. In this paper we suggest a
mathematical characterization of good sets of options using tools from
information theory. This characterization enables us to find conditions for a
set of options to be optimal and an algorithm that outputs a useful set of
options and illustrate the proposed algorithm in simulation.
Taming the Noise in Reinforcement Learning via Soft Updates
Authors: Roy Fox, Ari Pakman, Naftali Tishby
Date: 2015-12-28 00:00:00
Tasks: Q-Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Model-free reinforcement learning algorithms, such as Q-learning, perform
poorly in the early stages of learning in noisy environments, because much
effort is spent unlearning biased estimates of the state-action value function.
The bias results from selecting, among several noisy estimates, the apparent
optimum, which may actually be suboptimal. We propose G-learning, a new
off-policy learning algorithm that regularizes the value estimates by
penalizing deterministic policies in the beginning of the learning process. We
show that this method reduces the bias of the value-function estimation,
leading to faster convergence to the optimal value and the optimal policy.
Moreover, G-learning enables the natural incorporation of prior domain
knowledge, when available. The stochastic nature of G-learning also makes it
avoid some exploration costs, a property usually attributed only to on-policy
algorithms. We illustrate these ideas in several examples, where G-learning
results in significant improvements of the convergence rate and the cost of the
learning process.
Information-Theoretic Methods for Planning and Learning in Partially Observable Markov Decision Processes
Authors: Roy Fox
Date: 2016-09-24 00:00:00

Bounded agents are limited by intrinsic constraints on their ability to
process information that is available in their sensors and memory and choose
actions and memory updates. In this dissertation, we model these constraints as
information-rate constraints on communication channels connecting these various
internal components of the agent. We make four major contributions detailed
below and many smaller contributions detailed in each section. First, we
formulate the problem of optimizing the agent under both extrinsic and
intrinsic constraints and develop the main tools for solving it. Second, we
identify another reason for the challenging convergence properties of the
optimization algorithm, which is the bifurcation structure of the update
operator near phase transitions. Third, we study the special case of
linear-Gaussian dynamics and quadratic cost (LQG), where the optimal solution
has a particularly simple and solvable form. Fourth, we explore the learning
task, where the model of the world dynamics is unknown and sample-based updates
are used instead.
Graph-Structured Representations for Visual Question Answering
Authors: Damien Teney, Lingqiao Liu, Anton Van Den Hengel
Date: 2016-09-19 00:00:00
Proceeding: CVPR 2017 7
Tasks: Multiple-choice, Question Answering, Visual Question Answering, Visual Question Answering (VQA)

This paper proposes to improve visual question answering (VQA) with
structured representations of both scene contents and questions. A key
challenge in VQA is to require joint reasoning over the visual and text
domains. The predominant CNN/LSTM-based approach to VQA is limited by
monolithic vector representations that largely ignore structure in the scene
and in the form of the question. CNN feature vectors cannot effectively capture
situations as simple as multiple object instances, and LSTMs process questions
as series of words, which does not reflect the true complexity of language
structure. We instead propose to build graphs over the scene objects and over
the question words, and we describe a deep neural network that exploits the
structure in these representations. This shows significant benefit over the
sequential processing of LSTMs. The overall efficacy of our approach is
demonstrated by significant improvements over the state-of-the-art, from 71.2%
to 74.4% in accuracy on the "abstract scenes" multiple-choice benchmark, and
from 34.7% to 39.1% in accuracy over pairs of "balanced" scenes, i.e. images
with fine-grained differences and opposite yes/no answers to a same question.
Planecell: Representing the 3D Space with Planes
Authors: Lei Fan, Ziyu Pan, Long Chen, Kai Huang
Date: 2017-03-30 00:00:00
Tasks: Image Segmentation, Semantic Segmentation

Reconstruction based on the stereo camera has received considerable attention
recently, but two particular challenges still remain. The first concerns the
need to aggregate similar pixels in an effective approach, and the second is to
maintain as much of the available information as possible while ensuring
sufficient accuracy. To overcome these issues, we propose a new 3D
representation method, namely, planecell, that extracts planarity from the
depth-assisted image segmentation and then projects these depth planes into the
3D world. An energy function formulated from Conditional Random Field that
generalizes the planar relationships is maximized to merge coplanar segments.
We evaluate our method with a variety of reconstruction baselines on both KITTI
and Middlebury datasets, and the results indicate the superiorities compared to
other 3D space representation methods in accuracy, memory requirements and
further applications.
Data-Mining Textual Responses to Uncover Misconception Patterns
Authors: Joshua J. Michalenko, Andrew S. Lan, Richard G. Baraniuk
Date: 2017-03-24 00:00:00
Tasks: Misconceptions

An important, yet largely unstudied, problem in student data analysis is to
detect misconceptions from students' responses to open-response questions.
Misconception detection enables instructors to deliver more targeted feedback
on the misconceptions exhibited by many students in their class, thus improving
the quality of instruction. In this paper, we propose a new natural language
processing-based framework to detect the common misconceptions among students'
textual responses to short-answer questions. We propose a probabilistic model
for students' textual responses involving misconceptions and experimentally
validate it on a real-world student-response dataset. Experimental results show
that our proposed framework excels at classifying whether a response exhibits
one or more misconceptions. More importantly, it can also automatically detect
the common misconceptions exhibited across responses from multiple students to
multiple questions; this property is especially important at large scale, since
instructors will no longer need to manually specify all possible misconceptions
that students might exhibit.
Lensless Imaging with Compressive Ultrafast Sensing
Authors: Guy Satat, Matthew Tancik, Ramesh Raskar
Date: 2016-10-19 00:00:00
Tasks: Compressive Sensing, Time Series, Time Series Analysis

Lensless imaging is an important and challenging problem. One notable
solution to lensless imaging is a single pixel camera which benefits from ideas
central to compressive sampling. However, traditional single pixel cameras
require many illumination patterns which result in a long acquisition process.
Here we present a method for lensless imaging based on compressive ultrafast
sensing. Each sensor acquisition is encoded with a different illumination
pattern and produces a time series where time is a function of the photon's
origin in the scene. Currently available hardware with picosecond time
resolution enables time tagging photons as they arrive to an omnidirectional
sensor. This allows lensless imaging with significantly fewer patterns compared
to regular single pixel imaging. To that end, we develop a framework for
designing lensless imaging systems that use ultrafast detectors. We provide an
algorithm for ideal sensor placement and an algorithm for optimized active
illumination patterns. We show that efficient lensless imaging is possible with
ultrafast measurement and compressive sensing. This paves the way for novel
imaging architectures and remote sensing in extreme situations where imaging
with a lens is not possible.
Enter the Matrix: Safely Interruptible Autonomous Systems via Virtualization
Authors: Mark O. Riedl, Brent Harrison
Date: 2017-03-30 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Autonomous systems that operate around humans will likely always rely on kill
switches that stop their execution and allow them to be remote-controlled for
the safety of humans or to prevent damage to the system. It is theoretically
possible for an autonomous system with sufficient sensor and effector
capability that learn online using reinforcement learning to discover that the
kill switch deprives it of long-term reward and thus learn to disable the
switch or otherwise prevent a human operator from using the switch. This is
referred to as the big red button problem. We present a technique that prevents
a reinforcement learning agent from learning to disable the kill switch. We
introduce an interruption process in which the agent's sensors and effectors
are redirected to a virtual simulation where it continues to believe it is
receiving reward. We illustrate our technique in a simple grid world
environment.
Semantic Instance Segmentation via Deep Metric Learning
Authors: Alireza Fathi, Zbigniew Wojna, Vivek Rathod, Peng Wang, Hyun Oh Song, Sergio Guadarrama, Kevin P. Murphy
Date: 2017-03-30 00:00:00
Tasks: Instance Segmentation, Metric Learning, Object Proposal Generation, Segmentation, Semantic Segmentation

We propose a new method for semantic instance segmentation, by first
computing how likely two pixels are to belong to the same object, and then by
grouping similar pixels together. Our similarity metric is based on a deep,
fully convolutional embedding model. Our grouping method is based on selecting
all points that are sufficiently similar to a set of "seed points", chosen from
a deep, fully convolutional scoring model. We show competitive results on the
Pascal VOC instance segmentation benchmark.
Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
Authors: Song Mei, Theodor Misiakiewicz, Andrea Montanari, Roberto I. Oliveira
Date: 2017-03-25 00:00:00
Tasks: Stochastic Block Model

A number of statistical estimation problems can be addressed by semidefinite
programs (SDP). While SDPs are solvable in polynomial time using interior point
methods, in practice generic SDP solvers do not scale well to high-dimensional
problems. In order to cope with this problem, Burer and Monteiro proposed a
non-convex rank-constrained formulation, which has good performance in practice
but is still poorly understood theoretically.
  In this paper we study the rank-constrained version of SDPs arising in MaxCut
and in synchronization problems. We establish a Grothendieck-type inequality
that proves that all the local maxima and dangerous saddle points are within a
small multiplicative gap from the global maximum. We use this structural
information to prove that SDPs can be solved within a known accuracy, by
applying the Riemannian trust-region method to this non-convex problem, while
constraining the rank to be of order one. For the MaxCut problem, our
inequality implies that any local maximizer of the rank-constrained SDP
provides a $ (1 - 1/(k-1)) \times 0.878$ approximation of the MaxCut, when the
rank is fixed to $k$.
  We then apply our results to data matrices generated according to the
Gaussian ${\mathbb Z}_2$ synchronization problem, and the two-groups stochastic
block model with large bounded degree. We prove that the error achieved by
local maximizers undergoes a phase transition at the same threshold as for
information-theoretically optimal methods.
Bandit-Based Model Selection for Deformable Object Manipulation
Authors: Dale McConachie, Dmitry Berenson
Date: 2017-03-29 00:00:00
Tasks: Deformable Object Manipulation, model, Model Selection, Object

We present a novel approach to deformable object manipulation that does not
rely on highly-accurate modeling. The key contribution of this paper is to
formulate the task as a Multi-Armed Bandit problem, with each arm representing
a model of the deformable object. To "pull" an arm and evaluate its utility, we
use the arm's model to generate a velocity command for the gripper(s) holding
the object and execute it. As the task proceeds and the object deforms, the
utility of each model can change. Our framework estimates these changes and
balances exploration of the model set with exploitation of high-utility models.
We also propose an approach based on Kalman Filtering for Non-stationary
Multi-armed Normal Bandits (KF-MANB) to leverage the coupling between models to
learn more from each arm pull. We demonstrate that our method outperforms
previous methods on synthetic trials, and performs competitively on several
manipulation tasks in simulation.
Dialectical Rough Sets, Parthood and Figures of Opposition-1
Authors: A. Mani
Date: 2017-03-29 00:00:00
Tasks: Negation

In one perspective, the main theme of this research revolves around the
inverse problem in the context of general rough sets that concerns the
existence of rough basis for given approximations in a context. Granular
operator spaces and variants were recently introduced by the present author as
an optimal framework for anti-chain based algebraic semantics of general rough
sets and the inverse problem. In the framework, various sub-types of crisp and
non-crisp objects are identifiable that may be missed in more restrictive
formalism. This is also because in the latter cases concepts of complementation
and negation are taken for granted - while in reality they have a complicated
dialectical basis. This motivates a general approach to dialectical rough sets
building on previous work of the present author and figures of opposition. In
this paper dialectical rough logics are invented from a semantic perspective, a
concept of dialectical predicates is formalised, connection with dialetheias
and glutty negation are established, parthood analyzed and studied from the
viewpoint of classical and dialectical figures of opposition by the present
author. Her methods become more geometrical and encompass parthood as a primary
relation (as opposed to roughly equivalent objects) for algebraic semantics.