pwc-archive/papers-with-abstracts huggingface dataset:
Online Learning with Feedback Graphs Without the Graphs
Authors: Alon Cohen, Tamir Hazan, Tomer Koren
Date: 2016-05-23 00:00:00

We study an online learning framework introduced by Mannor and Shamir (2011)
in which the feedback is specified by a graph, in a setting where the graph may
vary from round to round and is \emph{never fully revealed} to the learner. We
show a large gap between the adversarial and the stochastic cases. In the
adversarial case, we prove that even for dense feedback graphs, the learner
cannot improve upon a trivial regret bound obtained by ignoring any additional
feedback besides her own loss. In contrast, in the stochastic case we give an
algorithm that achieves $\widetilde \Theta(\sqrt{\alpha T})$ regret over $T$
rounds, provided that the independence numbers of the hidden feedback graphs
are at most $\alpha$. We also extend our results to a more general feedback
model, in which the learner does not necessarily observe her own loss, and show
that, even in simple cases, concealing the feedback graphs might render a
learnable problem unlearnable.
Active Uncertainty Calibration in Bayesian ODE Solvers
Authors: Hans Kersting, Philipp Hennig
Date: 2016-05-11 00:00:00

There is resurging interest, in statistics and machine learning, in solvers
for ordinary differential equations (ODEs) that return probability measures
instead of point estimates. Recently, Conrad et al. introduced a sampling-based
class of methods that are 'well-calibrated' in a specific sense. But the
computational cost of these methods is significantly above that of classic
methods. On the other hand, Schober et al. pointed out a precise connection
between classic Runge-Kutta ODE solvers and Gaussian filters, which gives only
a rough probabilistic calibration, but at negligible cost overhead. By
formulating the solution of ODEs as approximate inference in linear Gaussian
SDEs, we investigate a range of probabilistic ODE solvers, that bridge the
trade-off between computational cost and probabilistic calibration, and
identify the inaccurate gradient measurement as the crucial source of
uncertainty. We propose the novel filtering-based method Bayesian Quadrature
filtering (BQF) which uses Bayesian quadrature to actively learn the
imprecision in the gradient measurement by collecting multiple gradient
evaluations.
Compressive Spectral Clustering
Authors: Nicolas Tremblay, Gilles Puy, Remi Gribonval, Pierre Vandergheynst
Date: 2016-02-05 00:00:00
Tasks: Clustering

Spectral clustering has become a popular technique due to its high
performance in many contexts. It comprises three main steps: create a
similarity graph between N objects to cluster, compute the first k eigenvectors
of its Laplacian matrix to define a feature vector for each object, and run
k-means on these features to separate objects into k classes. Each of these
three steps becomes computationally intensive for large N and/or k. We propose
to speed up the last two steps based on recent results in the emerging field of
graph signal processing: graph filtering of random signals, and random sampling
of bandlimited graph signals. We prove that our method, with a gain in
computation time that can reach several orders of magnitude, is in fact an
approximation of spectral clustering, for which we are able to control the
error. We test the performance of our method on artificial and real-world
network data.
Image Restoration and Reconstruction using Variable Splitting and Class-adapted Image Priors
Authors: Afonso M. Teodoro, José M. Bioucas-Dias, Mário A. T. Figueiredo
Date: 2016-02-12 00:00:00
Tasks: Deblurring, Denoising, Image Deblurring, Image Restoration

This paper proposes using a Gaussian mixture model as a prior, for solving
two image inverse problems, namely image deblurring and compressive imaging. We
capitalize on the fact that variable splitting algorithms, like ADMM, are able
to decouple the handling of the observation operator from that of the
regularizer, and plug a state-of-the-art algorithm into the pure denoising
step. Furthermore, we show that, when applied to a specific type of image, a
Gaussian mixture model trained from an database of images of the same type is
able to outperform current state-of-the-art methods.
Convolutional Rectifier Networks as Generalized Tensor Decompositions
Authors: Nadav Cohen, Amnon Shashua
Date: 2016-03-01 00:00:00

Convolutional rectifier networks, i.e. convolutional neural networks with
rectified linear activation and max or average pooling, are the cornerstone of
modern deep learning. However, despite their wide use and success, our
theoretical understanding of the expressive properties that drive these
networks is partial at best. On the other hand, we have a much firmer grasp of
these issues in the world of arithmetic circuits. Specifically, it is known
that convolutional arithmetic circuits possess the property of "complete depth
efficiency", meaning that besides a negligible set, all functions that can be
implemented by a deep network of polynomial size, require exponential size in
order to be implemented (or even approximated) by a shallow network. In this
paper we describe a construction based on generalized tensor decompositions,
that transforms convolutional arithmetic circuits into convolutional rectifier
networks. We then use mathematical tools available from the world of arithmetic
circuits to prove new results. First, we show that convolutional rectifier
networks are universal with max pooling but not with average pooling. Second,
and more importantly, we show that depth efficiency is weaker with
convolutional rectifier networks than it is with convolutional arithmetic
circuits. This leads us to believe that developing effective methods for
training convolutional arithmetic circuits, thereby fulfilling their expressive
potential, may give rise to a deep learning architecture that is provably
superior to convolutional rectifier networks but has so far been overlooked by
practitioners.
Extracting Higher-Order Goals from the Mizar Mathematical Library
Authors: Chad Brown, Josef Urban
Date: 2016-05-23 00:00:00
Tasks: Articles, Automated Theorem Proving

Certain constructs allowed in Mizar articles cannot be represented in
first-order logic but can be represented in higher-order logic. We describe a
way to obtain higher-order theorem proving problems from Mizar articles that
make use of these constructs. In particular, higher-order logic is used to
represent schemes, a global choice construct and set level binders. The
higher-order automated theorem provers Satallax and LEO-II have been run on
collections of these problems and the results are discussed.
Highly Accurate Prediction of Jobs Runtime Classes
Authors: Anat Reiner-Benaim, Anna Grabarnick, Edi Shmueli
Date: 2016-05-02 00:00:00
Tasks: Prediction, Scheduling, Sensitivity, Specificity

Separating the short jobs from the long is a known technique to improve
scheduling performance. In this paper we describe a method we developed for
accurately predicting the runtimes classes of the jobs to enable this
separation. Our method uses the fact that the runtimes can be represented as a
mixture of overlapping Gaussian distributions, in order to train a CART
classifier to provide the prediction. The threshold that separates the short
jobs from the long jobs is determined during the evaluation of the classifier
to maximize prediction accuracy. Our results indicate overall accuracy of 90%
for the data set used in our study, with sensitivity and specificity both above
90%.
Analysis of Vessel Connectivities in Retinal Images by Cortically Inspired Spectral Clustering
Authors: Marta Favali, Samaneh Abbasi-Sureshjani, Bart ter Haar Romeny, Alessandro Sarti
Date: 2015-12-21 00:00:00
Tasks: Clustering, Diagnostic

Retinal images provide early signs of diabetic retinopathy, glaucoma, and
hypertension. These signs can be investigated based on microaneurysms or
smaller vessels. The diagnostic biomarkers are the change of vessel widths and
angles especially at junctions, which are investigated using the vessel
segmentation or tracking. Vessel paths may also be interrupted; crossings and
bifurcations may be disconnected. This paper addresses a novel contextual
method based on the geometry of the primary visual cortex (V1) to study these
difficulties. We have analyzed the specific problems at junctions with a
connectivity kernel obtained as the fundamental solution of the Fokker-Planck
equation, which is usually used to represent the geometrical structure of
multi-orientation cortical connectivity. Using the spectral clustering on a
large local affinity matrix constructed by both the connectivity kernel and the
feature of intensity, the vessels are identified successfully in a hierarchical
topology each representing an individual perceptual unit.
A Riemannian gossip approach to decentralized matrix completion
Authors: Bamdev Mishra, Hiroyuki Kasai, Atul Saroop
Date: 2016-05-23 00:00:00
Tasks: Matrix Completion

In this paper, we propose novel gossip algorithms for the low-rank
decentralized matrix completion problem. The proposed approach is on the
Riemannian Grassmann manifold that allows local matrix completion by different
agents while achieving asymptotic consensus on the global low-rank factors. The
resulting approach is scalable and parallelizable. Our numerical experiments
show the good performance of the proposed algorithms on various benchmarks.
EndoNet: A Deep Architecture for Recognition Tasks on Laparoscopic Videos
Authors: Andru P. Twinanda, Sherif Shehata, Didier Mutter, Jacques Marescaux, Michel de Mathelin, Nicolas Padoy
Date: 2016-02-09 00:00:00
Tasks: Offline surgical phase recognition, Online surgical phase recognition, Scheduling, Surgical tool detection

Surgical workflow recognition has numerous potential medical applications,
such as the automatic indexing of surgical video databases and the optimization
of real-time operating room scheduling, among others. As a result, phase
recognition has been studied in the context of several kinds of surgeries, such
as cataract, neurological, and laparoscopic surgeries. In the literature, two
types of features are typically used to perform this task: visual features and
tool usage signals. However, the visual features used are mostly handcrafted.
Furthermore, the tool usage signals are usually collected via a manual
annotation process or by using additional equipment. In this paper, we propose
a novel method for phase recognition that uses a convolutional neural network
(CNN) to automatically learn features from cholecystectomy videos and that
relies uniquely on visual information. In previous studies, it has been shown
that the tool signals can provide valuable information in performing the phase
recognition task. Thus, we present a novel CNN architecture, called EndoNet,
that is designed to carry out the phase recognition and tool presence detection
tasks in a multi-task manner. To the best of our knowledge, this is the first
work proposing to use a CNN for multiple recognition tasks on laparoscopic
videos. Extensive experimental comparisons to other methods show that EndoNet
yields state-of-the-art results for both tasks.
Elastic Solver: Balancing Solution Time and Energy Consumption
Authors: Barry Hurley, Deepak Mehta, Barry O'Sullivan
Date: 2016-05-23 00:00:00
Tasks: Cloud Computing, Scheduling

Combinatorial decision problems arise in many different domains such as
scheduling, routing, packing, bioinformatics, and many more. Despite recent
advances in developing scalable solvers, there are still many problems which
are often very hard to solve. Typically the most advanced solvers include
elements which are stochastic in nature. If a same instance is solved many
times using different seeds then depending on the inherent characteristics of a
problem instance and the solver, one can observe a highly-variant distribution
of times spanning multiple orders of magnitude. Therefore, to solve a problem
instance efficiently it is often useful to solve the same instance in parallel
with different seeds. With the proliferation of cloud computing, it is natural
to think about an elastic solver which can scale up by launching searches in
parallel on thousands of machines (or cores). However, this could result in
consuming a lot of energy. Moreover, not every instance would require thousands
of machines. The challenge is to resolve the tradeoff between solution time and
energy consumption optimally for a given problem instance. We analyse the
impact of the number of machines (or cores) on not only solution time but also
on energy consumption. We highlight that although solution time always drops as
the number of machines increases, the relation between the number of machines
and energy consumption is more complicated. In many cases, the optimal energy
consumption may be achieved by a middle ground, we analyse this relationship in
detail. The tradeoff between solution time and energy consumption is studied
further, showing that the energy consumption of a solver can be reduced
drastically if we increase the solution time marginally. We also develop a
prediction model, demonstrating that such insights can be exploited to achieve
faster solutions times in a more energy efficient manor.
Deep Neural Networks Under Stress
Authors: Micael Carvalho, Matthieu Cord, Sandra Avila, Nicolas Thome, Eduardo Valle
Date: 2016-05-11 00:00:00
Tasks: Transfer Learning

In recent years, deep architectures have been used for transfer learning with
state-of-the-art performance in many datasets. The properties of their features
remain, however, largely unstudied under the transfer perspective. In this
work, we present an extensive analysis of the resiliency of feature vectors
extracted from deep models, with special focus on the trade-off between
performance and compression rate. By introducing perturbations to image
descriptions extracted from a deep convolutional neural network, we change
their precision and number of dimensions, measuring how it affects the final
score. We show that deep features are more robust to these disturbances when
compared to classical approaches, achieving a compression rate of 98.4%, while
losing only 0.88% of their original score for Pascal VOC 2007.
Generative Choreography using Deep Learning
Authors: Luka Crnkovic-Friis, Louise Crnkovic-Friis
Date: 2016-05-23 00:00:00
Tasks: Deep Learning

Recent advances in deep learning have enabled the extraction of high-level
features from raw sensor data which has opened up new possibilities in many
different fields, including computer generated choreography. In this paper we
present a system chor-rnn for generating novel choreographic material in the
nuanced choreographic language and style of an individual choreographer. It
also shows promising results in producing a higher level compositional
cohesion, rather than just generating sequences of movement. At the core of
chor-rnn is a deep recurrent neural network trained on raw motion capture data
and that can generate new dance sequences for a solo dancer. Chor-rnn can be
used for collaborative human-machine choreography or as a creative catalyst,
serving as inspiration for a choreographer.
Online Learning with Low Rank Experts
Authors: Elad Hazan, Tomer Koren, Roi Livni, Yishay Mansour
Date: 2016-03-21 00:00:00

We consider the problem of prediction with expert advice when the losses of
the experts have low-dimensional structure: they are restricted to an unknown
$d$-dimensional subspace. We devise algorithms with regret bounds that are
independent of the number of experts and depend only on the rank $d$. For the
stochastic model we show a tight bound of $\Theta(\sqrt{dT})$, and extend it to
a setting of an approximate $d$ subspace. For the adversarial model we show an
upper bound of $O(d\sqrt{T})$ and a lower bound of $\Omega(\sqrt{dT})$.
Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
Authors: Sashank J. Reddi, Suvrit Sra, Barnabas Poczos, Alex Smola
Date: 2016-05-23 00:00:00

We analyze stochastic algorithms for optimizing nonconvex, nonsmooth
finite-sum problems, where the nonconvex part is smooth and the nonsmooth part
is convex. Surprisingly, unlike the smooth case, our knowledge of this
fundamental problem is very limited. For example, it is not known whether the
proximal stochastic gradient method with constant minibatch converges to a
stationary point. To tackle this issue, we develop fast stochastic algorithms
that provably converge to a stationary point for constant minibatches.
Furthermore, using a variant of these algorithms, we show provably faster
convergence than batch proximal gradient descent. Finally, we prove global
linear convergence rate for an interesting subclass of nonsmooth nonconvex
functions, that subsumes several recent works. This paper builds upon our
recent series of papers on fast stochastic methods for smooth nonconvex
optimization [22, 23], with a novel analysis for nonconvex and nonsmooth
functions.
DLAU: A Scalable Deep Learning Accelerator Unit on FPGA
Authors: Chao Wang, Qi Yu, Lei Gong, Xi Li, Yuan Xie, Xuehai Zhou
Date: 2016-05-23 00:00:00
Tasks: Deep Learning

As the emerging field of machine learning, deep learning shows excellent
ability in solving complex learning problems. However, the size of the networks
becomes increasingly large scale due to the demands of the practical
applications, which poses significant challenge to construct a high performance
implementations of deep learning neural networks. In order to improve the
performance as well to maintain the low power cost, in this paper we design
DLAU, which is a scalable accelerator architecture for large-scale deep
learning networks using FPGA as the hardware prototype. The DLAU accelerator
employs three pipelined processing units to improve the throughput and utilizes
tile techniques to explore locality for deep learning applications.
Experimental results on the state-of-the-art Xilinx FPGA board demonstrate that
the DLAU accelerator is able to achieve up to 36.1x speedup comparing to the
Intel Core2 processors, with the power consumption at 234mW.
Bridging Category-level and Instance-level Semantic Image Segmentation
Authors: Zifeng Wu, Chunhua Shen, Anton Van Den Hengel
Date: 2016-05-23 00:00:00
Tasks: Image Segmentation, Instance Segmentation, Segmentation, Semantic Segmentation

We propose an approach to instance-level image segmentation that is built on
top of category-level segmentation. Specifically, for each pixel in a semantic
category mask, its corresponding instance bounding box is predicted using a
deep fully convolutional regression network. Thus it follows a different
pipeline to the popular detect-then-segment approaches that first predict
instances' bounding boxes, which are the current state-of-the-art in instance
segmentation. We show that, by leveraging the strength of our state-of-the-art
semantic segmentation models, the proposed method can achieve comparable or
even better results to detect-then-segment approaches. We make the following
contributions. (i) First, we propose a simple yet effective approach to
semantic instance segmentation. (ii) Second, we propose an online bootstrapping
method during training, which is critically important for achieving good
performance for both semantic category segmentation and instance-level
segmentation. (iii) As the performance of semantic category segmentation has a
significant impact on the instance-level segmentation, which is the second step
of our approach, we train fully convolutional residual networks to achieve the
best semantic category segmentation accuracy. On the PASCAL VOC 2012 dataset,
we obtain the currently best mean intersection-over-union score of 79.1%. (iv)
We also achieve state-of-the-art results for instance-level segmentation.
Localizing by Describing: Attribute-Guided Attention Localization for Fine-Grained Recognition
Authors: Xiao Liu, Jiang Wang, Shilei Wen, Errui Ding, Yuanqing Lin
Date: 2016-05-20 00:00:00
Tasks: Attribute, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

A key challenge in fine-grained recognition is how to find and represent
discriminative local regions. Recent attention models are capable of learning
discriminative region localizers only from category labels with reinforcement
learning. However, not utilizing any explicit part information, they are not
able to accurately find multiple distinctive regions. In this work, we
introduce an attribute-guided attention localization scheme where the local
region localizers are learned under the guidance of part attribute
descriptions. By designing a novel reward strategy, we are able to learn to
locate regions that are spatially and semantically distinctive with
reinforcement learning algorithm. The attribute labeling requirement of the
scheme is more amenable than the accurate part location annotation required by
traditional part-based fine-grained recognition methods. Experimental results
on the CUB-200-2011 dataset demonstrate the superiority of the proposed scheme
on both fine-grained recognition and attribute recognition.
Barzilai-Borwein Step Size for Stochastic Gradient Descent
Authors: Conghui Tan, Shiqian Ma, Yu-Hong Dai, Yuqiu Qian
Date: 2016-05-13 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Stochastic Optimization

One of the major issues in stochastic gradient descent (SGD) methods is how
to choose an appropriate step size while running the algorithm. Since the
traditional line search technique does not apply for stochastic optimization
algorithms, the common practice in SGD is either to use a diminishing step
size, or to tune a fixed step size by hand, which can be time consuming in
practice. In this paper, we propose to use the Barzilai-Borwein (BB) method to
automatically compute step sizes for SGD and its variant: stochastic variance
reduced gradient (SVRG) method, which leads to two algorithms: SGD-BB and
SVRG-BB. We prove that SVRG-BB converges linearly for strongly convex objective
functions. As a by-product, we prove the linear convergence result of SVRG with
Option I proposed in [10], whose convergence result is missing in the
literature. Numerical experiments on standard data sets show that the
performance of SGD-BB and SVRG-BB is comparable to and sometimes even better
than SGD and SVRG with best-tuned step sizes, and is superior to some advanced
SGD variants.
Mask-CNN: Localizing Parts and Selecting Descriptors for Fine-Grained Image Recognition
Authors: Xiu-Shen Wei, Chen-Wei Xie, Jianxin Wu
Date: 2016-05-23 00:00:00
Tasks: Fine-Grained Image Recognition

Fine-grained image recognition is a challenging computer vision problem, due
to the small inter-class variations caused by highly similar subordinate
categories, and the large intra-class variations in poses, scales and
rotations. In this paper, we propose a novel end-to-end Mask-CNN model without
the fully connected layers for fine-grained recognition. Based on the part
annotations of fine-grained images, the proposed model consists of a fully
convolutional network to both locate the discriminative parts (e.g., head and
torso), and more importantly generate object/part masks for selecting useful
and meaningful convolutional descriptors. After that, a four-stream Mask-CNN
model is built for aggregating the selected object- and part-level descriptors
simultaneously. The proposed Mask-CNN model has the smallest number of
parameters, lowest feature dimensionality and highest recognition accuracy when
compared with state-of-the-arts fine-grained approaches.