pwc-archive/papers-with-abstracts huggingface dataset:
Surrogate regret bounds for generalized classification performance metrics
Authors: Wojciech Kotłowski, Krzysztof Dembczyński
Date: 2015-04-27 00:00:00
Tasks: Binary Classification, Classification, General Classification

We consider optimization of generalized performance metrics for binary
classification by means of surrogate losses. We focus on a class of metrics,
which are linear-fractional functions of the false positive and false negative
rates (examples of which include $F_{\beta}$-measure, Jaccard similarity
coefficient, AM measure, and many others). Our analysis concerns the following
two-step procedure. First, a real-valued function $f$ is learned by minimizing
a surrogate loss for binary classification on the training sample. It is
assumed that the surrogate loss is a strongly proper composite loss function
(examples of which include logistic loss, squared-error loss, exponential loss,
etc.). Then, given $f$, a threshold $\widehat{\theta}$ is tuned on a separate
validation sample, by direct optimization of the target performance metric. We
show that the regret of the resulting classifier (obtained from thresholding
$f$ on $\widehat{\theta}$) measured with respect to the target metric is
upperbounded by the regret of $f$ measured with respect to the surrogate loss.
We also extend our results to cover multilabel classification and provide
regret bounds for micro- and macro-averaging measures. Our findings are further
analyzed in a computational study on both synthetic and real data sets.
Optimization of Convolutional Neural Network using Microcanonical Annealing Algorithm
Authors: Vina Ayumi, L. M. Rasdi Rere, Mohamad Ivan Fanany, Aniati Murni Arymurthy
Date: 2016-10-07 00:00:00

Convolutional neural network (CNN) is one of the most prominent architectures
and algorithm in Deep Learning. It shows a remarkable improvement in the
recognition and classification of objects. This method has also been proven to
be very effective in a variety of computer vision and machine learning
problems. As in other deep learning, however, training the CNN is interesting
yet challenging. Recently, some metaheuristic algorithms have been used to
optimize CNN using Genetic Algorithm, Particle Swarm Optimization, Simulated
Annealing and Harmony Search. In this paper, another type of metaheuristic
algorithms with different strategy has been proposed, i.e. Microcanonical
Annealing to optimize Convolutional Neural Network. The performance of the
proposed method is tested using the MNIST and CIFAR-10 datasets. Although
experiment results of MNIST dataset indicate the increase in computation time
(1.02x - 1.38x), nevertheless this proposed method can considerably enhance the
performance of the original CNN (up to 4.60\%). On the CIFAR10 dataset,
currently, state of the art is 96.53\% using fractional pooling, while this
proposed method achieves 99.14\%.
Data-driven Rank Breaking for Efficient Rank Aggregation
Authors: Ashish Khetan, Sewoong Oh
Date: 2016-01-21 00:00:00

Rank aggregation systems collect ordinal preferences from individuals to
produce a global ranking that represents the social preference. Rank-breaking
is a common practice to reduce the computational complexity of learning the
global ranking. The individual preferences are broken into pairwise comparisons
and applied to efficient algorithms tailored for independent paired
comparisons. However, due to the ignored dependencies in the data, naive
rank-breaking approaches can result in inconsistent estimates. The key idea to
produce accurate and consistent estimates is to treat the pairwise comparisons
unequally, depending on the topology of the collected data. In this paper, we
provide the optimal rank-breaking estimator, which not only achieves
consistency but also achieves the best error bound. This allows us to
characterize the fundamental tradeoff between accuracy and complexity. Further,
the analysis identifies how the accuracy depends on the spectral gap of a
corresponding comparison graph.
Learning Macro-actions for State-Space Planning
Authors: Sandra Castellanos-Paez, Damien Pellier, Humbert Fiorino, Sylvie Pesty
Date: 2016-10-07 00:00:00

Planning has achieved significant progress in recent years. Among the various
approaches to scale up plan synthesis, the use of macro-actions has been widely
explored. As a first stage towards the development of a solution to learn
on-line macro-actions, we propose an algorithm to identify useful macro-actions
based on data mining techniques. The integration in the planning search of
these learned macro-actions shows significant improvements over four classical
planning benchmarks.
Learning Grimaces by Watching TV
Authors: Samuel Albanie, Andrea Vedaldi
Date: 2016-10-07 00:00:00
Tasks: Emotion Recognition, Face Verification, Facial Expression Recognition, Facial Expression Recognition (FER)

Differently from computer vision systems which require explicit supervision,
humans can learn facial expressions by observing people in their environment.
In this paper, we look at how similar capabilities could be developed in
machine vision. As a starting point, we consider the problem of relating facial
expressions to objectively measurable events occurring in videos. In
particular, we consider a gameshow in which contestants play to win significant
sums of money. We extract events affecting the game and corresponding facial
expressions objectively and automatically from the videos, obtaining large
quantities of labelled data for our study. We also develop, using benchmarks
such as FER and SFEW 2.0, state-of-the-art deep neural networks for facial
expression recognition, showing that pre-training on face verification data can
be highly beneficial for this task. Then, we extend these models to use facial
expressions to predict events in videos and learn nameable expressions from
them. The dataset and emotion recognition models are available at
http://www.robots.ox.ac.uk/~vgg/data/facevalue
Automated Detection of Individual Micro-calcifications from Mammograms using a Multi-stage Cascade Approach
Authors: Zhi Lu, Gustavo Carneiro, Neeraj Dhungel, Andrew P. Bradley
Date: 2016-10-07 00:00:00
Tasks: Clustering, General Classification

In mammography, the efficacy of computer-aided detection methods depends, in
part, on the robust localisation of micro-calcifications ($\mu$C). Currently,
the most effective methods are based on three steps: 1) detection of individual
$\mu$C candidates, 2) clustering of individual $\mu$C candidates, and 3)
classification of $\mu$C clusters. Where the second step is motivated both to
reduce the number of false positive detections from the first step and on the
evidence that malignancy depends on a relatively large number of $\mu$C
detections within a certain area. In this paper, we propose a novel approach to
$\mu$C detection, consisting of the detection \emph{and} classification of
individual $\mu$C candidates, using shape and appearance features, using a
cascade of boosting classifiers. The final step in our approach then clusters
the remaining individual $\mu$C candidates. The main advantage of this approach
lies in its ability to reject a significant number of false positive $\mu$C
candidates compared to previously proposed methods. Specifically, on the
INbreast dataset, we show that our approach has a true positive rate (TPR) for
individual $\mu$Cs of 40\% at one false positive per image (FPI) and a TPR of
80\% at 10 FPI. These results are significantly more accurate than the current
state of the art, which has a TPR of less than 1\% at one FPI and a TPR of 10\%
at 10 FPI. Our results are competitive with the state of the art at the
subsequent stage of detecting clusters of $\mu$Cs.
Starting Small -- Learning with Adaptive Sample Sizes
Authors: Hadi Daneshmand, Aurelien Lucchi, Thomas Hofmann
Date: 2016-03-09 00:00:00
Tasks: BIG-bench Machine Learning

For many machine learning problems, data is abundant and it may be
prohibitive to make multiple passes through the full training set. In this
context, we investigate strategies for dynamically increasing the effective
sample size, when using iterative methods such as stochastic gradient descent.
Our interest is motivated by the rise of variance-reduced methods, which
achieve linear convergence rates that scale favorably for smaller sample sizes.
Exploiting this feature, we show -- theoretically and empirically -- how to
obtain significant speed-ups with a novel algorithm that reaches statistical
accuracy on an $n$-sample in $2n$, instead of $n \log n$ steps.
Challenges of Computational Processing of Code-Switching
Authors: Özlem Çetinoğlu, Sarah Schulz, Ngoc Thang Vu
Date: 2016-10-07 00:00:00
Proceeding: WS 2016 11
Tasks: Automatic Speech Recognition, Automatic Speech Recognition (ASR), Dependency Parsing, Language Identification, Language Modelling, Machine Translation, Part-Of-Speech Tagging, speech-recognition, Speech Recognition, Translation

This paper addresses challenges of Natural Language Processing (NLP) on
non-canonical multilingual data in which two or more languages are mixed. It
refers to code-switching which has become more popular in our daily life and
therefore obtains an increasing amount of attention from the research
community. We report our experience that cov- ers not only core NLP tasks such
as normalisation, language identification, language modelling, part-of-speech
tagging and dependency parsing but also more downstream ones such as machine
translation and automatic speech recognition. We highlight and discuss the key
problems for each of the tasks with supporting examples from different language
pairs and relevant previous work.
Automatic Liver and Lesion Segmentation in CT Using Cascaded Fully Convolutional Neural Networks and 3D Conditional Random Fields
Authors: Patrick Ferdinand Christ, Mohamed Ezzeldin A. Elshaer, Florian Ettlinger, Sunil Tatavarty, Marc Bickel, Patrick Bilic, Markus Rempfler, Marco Armbruster, Felix Hofmann, Melvin D'Anastasi, Wieland H. Sommer, Seyed-Ahmad Ahmadi, Bjoern H. Menze
Date: 2016-10-07 00:00:00
Tasks: Lesion Segmentation, Segmentation

Automatic segmentation of the liver and its lesion is an important step
towards deriving quantitative biomarkers for accurate clinical diagnosis and
computer-aided decision support systems. This paper presents a method to
automatically segment liver and lesions in CT abdomen images using cascaded
fully convolutional neural networks (CFCNs) and dense 3D conditional random
fields (CRFs). We train and cascade two FCNs for a combined segmentation of the
liver and its lesions. In the first step, we train a FCN to segment the liver
as ROI input for a second FCN. The second FCN solely segments lesions from the
predicted liver ROIs of step 1. We refine the segmentations of the CFCN using a
dense 3D CRF that accounts for both spatial coherence and appearance. CFCN
models were trained in a 2-fold cross-validation on the abdominal CT dataset
3DIRCAD comprising 15 hepatic tumor volumes. Our results show that CFCN-based
semantic liver and lesion segmentation achieves Dice scores over 94% for liver
with computation times below 100s per volume. We experimentally demonstrate the
robustness of the proposed method as a decision support system with a high
accuracy and speed for usage in daily clinical routine.
Deep Reinforcement Learning From Raw Pixels in Doom
Authors: Danijar Hafner
Date: 2016-10-07 00:00:00
Tasks: Deep Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Using current reinforcement learning methods, it has recently become possible
to learn to play unknown 3D games from raw pixels. In this work, we study the
challenges that arise in such complex environments, and summarize current
methods to approach these. We choose a task within the Doom game, that has not
been approached yet. The goal for the agent is to fight enemies in a 3D world
consisting of five rooms. We train the DQN and LSTM-A3C algorithms on this
task. Results show that both algorithms learn sensible policies, but fail to
achieve high scores given the amount of training. We provide insights into the
learned behavior, which can serve as a valuable starting point for further
research in the Doom domain.
Direct Sparse Odometry
Authors: Jakob Engel, Vladlen Koltun, Daniel Cremers
Date: 2016-07-09 00:00:00
Tasks: Visual Odometry

We propose a novel direct sparse visual odometry formulation. It combines a
fully direct probabilistic model (minimizing a photometric error) with
consistent, joint optimization of all model parameters, including geometry --
represented as inverse depth in a reference frame -- and camera motion. This is
achieved in real time by omitting the smoothness prior used in other direct
methods and instead sampling pixels evenly throughout the images. Since our
method does not depend on keypoint detectors or descriptors, it can naturally
sample pixels from across all image regions that have intensity gradient,
including edges or smooth intensity variations on mostly white walls. The
proposed model integrates a full photometric calibration, accounting for
exposure time, lens vignetting, and non-linear response functions. We
thoroughly evaluate our method on three different datasets comprising several
hours of video. The experiments show that the presented approach significantly
outperforms state-of-the-art direct and indirect methods in a variety of
real-world settings, both in terms of tracking accuracy and robustness.
There's No Comparison: Reference-less Evaluation Metrics in Grammatical Error Correction
Authors: Courtney Napoles, Keisuke Sakaguchi, Joel Tetreault
Date: 2016-10-07 00:00:00
Proceeding: EMNLP 2016 11
Tasks: Benchmarking, Grammatical Error Correction, Sentence

Current methods for automatically evaluating grammatical error correction
(GEC) systems rely on gold-standard references. However, these methods suffer
from penalizing grammatical edits that are correct but not in the gold
standard. We show that reference-less grammaticality metrics correlate very
strongly with human judgments and are competitive with the leading
reference-based evaluation metrics. By interpolating both methods, we achieve
state-of-the-art correlation with human judgments. Finally, we show that GEC
metrics are much more reliable when they are calculated at the sentence level
instead of the corpus level. We have set up a CodaLab site for benchmarking GEC
output using a common dataset and different evaluation metrics.
Shape Interaction Matrix Revisited and Robustified: Efficient Subspace Clustering with Corrupted and Incomplete Data
Authors: Pan Ji, Mathieu Salzmann, Hongdong Li
Date: 2015-09-09 00:00:00
Proceeding: ICCV 2015 12
Tasks: Clustering, Face Clustering, Motion Segmentation

The Shape Interaction Matrix (SIM) is one of the earliest approaches to
performing subspace clustering (i.e., separating points drawn from a union of
subspaces). In this paper, we revisit the SIM and reveal its connections to
several recent subspace clustering methods. Our analysis lets us derive a
simple, yet effective algorithm to robustify the SIM and make it applicable to
realistic scenarios where the data is corrupted by noise. We justify our method
by intuitive examples and the matrix perturbation theory. We then show how this
approach can be extended to handle missing data, thus yielding an efficient and
general subspace clustering algorithm. We demonstrate the benefits of our
approach over state-of-the-art subspace clustering methods on several
challenging motion segmentation and face clustering problems, where the data
includes corrupted and missing measurements.
Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling
Authors: Michael B. Cohen, Cameron Musco, Christopher Musco
Date: 2015-11-23 00:00:00

We present a new algorithm for finding a near optimal low-rank approximation
of a matrix $A$ in $O(nnz(A))$ time. Our method is based on a recursive
sampling scheme for computing a representative subset of $A$'s columns, which
is then used to find a low-rank approximation.
  This approach differs substantially from prior $O(nnz(A))$ time algorithms,
which are all based on fast Johnson-Lindenstrauss random projections. It
matches the guarantees of these methods while offering a number of advantages.
  Not only are sampling algorithms faster for sparse and structured data, but
they can also be applied in settings where random projections cannot. For
example, we give new single-pass streaming algorithms for the column subset
selection and projection-cost preserving sample problems. Our method has also
been used to give the fastest algorithms for provably approximating kernel
matrices [MM16].
Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks
Authors: Nancy Lynch, Cameron Musco, Merav Parter
Date: 2016-10-06 00:00:00
Tasks: All, Distributed Computing

We initiate a line of investigation into biological neural networks from an
algorithmic perspective. We develop a simplified but biologically plausible
model for distributed computation in stochastic spiking neural networks and
study tradeoffs between computation time and network complexity in this model.
Our aim is to abstract real neural networks in a way that, while not capturing
all interesting features, preserves high-level behavior and allows us to make
biologically relevant conclusions.
  In this paper, we focus on the important `winner-take-all' (WTA) problem,
which is analogous to a neural leader election unit: a network consisting of
$n$ input neurons and $n$ corresponding output neurons must converge to a state
in which a single output corresponding to a firing input (the `winner') fires,
while all other outputs remain silent. Neural circuits for WTA rely on
inhibitory neurons, which suppress the activity of competing outputs and drive
the network towards a converged state with a single firing winner. We attempt
to understand how the number of inhibitors used affects network convergence
time.
  We show that it is possible to significantly outperform naive WTA
constructions through a more refined use of inhibition, solving the problem in
$O(\theta)$ rounds in expectation with just $O(\log^{1/\theta} n)$ inhibitors
for any $\theta$. An alternative construction gives convergence in
$O(\log^{1/\theta} n)$ rounds with $O(\theta)$ inhibitors. We compliment these
upper bounds with our main technical contribution, a nearly matching lower
bound for networks using $\ge \log\log n$ inhibitors. Our lower bound uses
familiar indistinguishability and locality arguments from distributed computing
theory. It lets us derive a number of interesting conclusions about the
structure of any network solving WTA with good probability, and the use of
randomness and inhibition within such a network.
Places: An Image Database for Deep Scene Understanding
Authors: Bolei Zhou, Aditya Khosla, Agata Lapedriza, Antonio Torralba, Aude Oliva
Date: 2016-10-06 00:00:00
Tasks: BIG-bench Machine Learning, Classification, Diversity, General Classification, Scene Classification, Scene Recognition, Scene Understanding

The rise of multi-million-item dataset initiatives has enabled data-hungry
machine learning algorithms to reach near-human semantic classification at
tasks such as object and scene recognition. Here we describe the Places
Database, a repository of 10 million scene photographs, labeled with scene
semantic categories and attributes, comprising a quasi-exhaustive list of the
types of environments encountered in the world. Using state of the art
Convolutional Neural Networks, we provide impressive baseline performances at
scene classification. With its high-coverage and high-diversity of exemplars,
the Places Database offers an ecosystem to guide future progress on currently
intractable visual recognition problems.
Scalable Machine Translation in Memory Constrained Environments
Authors: Paul Baltescu
Date: 2016-10-06 00:00:00
Tasks: Machine Translation, Translation

Machine translation is the discipline concerned with developing automated
tools for translating from one human language to another. Statistical machine
translation (SMT) is the dominant paradigm in this field. In SMT, translations
are generated by means of statistical models whose parameters are learned from
bilingual data. Scalability is a key concern in SMT, as one would like to make
use of as much data as possible to train better translation systems.
  In recent years, mobile devices with adequate computing power have become
widely available. Despite being very successful, mobile applications relying on
NLP systems continue to follow a client-server architecture, which is of
limited use because access to internet is often limited and expensive. The goal
of this dissertation is to show how to construct a scalable machine translation
system that can operate with the limited resources available on a mobile
device.
  The main challenge for porting translation systems on mobile devices is
memory usage. The amount of memory available on a mobile device is far less
than what is typically available on the server side of a client-server
application. In this thesis, we investigate alternatives for the two components
which prevent standard translation systems from working on mobile devices due
to high memory usage. We show that once these standard components are replaced
with our proposed alternatives, we obtain a scalable translation system that
can work on a device with limited memory.
Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
Authors: Carlo Baldassi, Christian Borgs, Jennifer Chayes, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, Riccardo Zecchina
Date: 2016-05-20 00:00:00

In artificial neural networks, learning from data is a computationally
demanding task in which a large number of connection weights are iteratively
tuned through stochastic-gradient-based heuristic processes over a
cost-function. It is not well understood how learning occurs in these systems,
in particular how they avoid getting trapped in configurations with poor
computational performance. Here we study the difficult case of networks with
discrete weights, where the optimization landscape is very rough even for
simple architectures, and provide theoretical and numerical evidence of the
existence of rare - but extremely dense and accessible - regions of
configurations in the network weight space. We define a novel measure, which we
call the "robust ensemble" (RE), which suppresses trapping by isolated
configurations and amplifies the role of these dense regions. We analytically
compute the RE in some exactly solvable models, and also provide a general
algorithmic scheme which is straightforward to implement: define a
cost-function given by a sum of a finite number of replicas of the original
cost-function, with a constraint centering the replicas around a driving
assignment. To illustrate this, we derive several powerful new algorithms,
ranging from Markov Chains to message passing to gradient descent processes,
where the algorithms target the robust dense states, resulting in substantial
improvements in performance. The weak dependence on the number of precision
bits of the weights leads us to conjecture that very similar reasoning applies
to more conventional neural networks. Analogous algorithmic schemes can also be
applied to other optimization problems.