pwc-archive/papers-with-abstracts huggingface dataset:
On Strong NP-Completeness of Rational Problems
Authors: Dominik Wojtczak
Date: 2018-02-26 00:00:00
Tasks: All

The computational complexity of the partition, 0-1 subset sum, unbounded
subset sum, 0-1 knapsack and unbounded knapsack problems and their multiple
variants were studied in numerous papers in the past where all the weights and
profits were assumed to be integers. We re-examine here the computational
complexity of all these problems in the setting where the weights and profits
are allowed to be any rational numbers. We show that all of these problems in
this setting become strongly NP-complete and, as a result, no pseudo-polynomial
algorithm can exist for solving them unless P=NP. Despite this result we show
that they all still admit a fully polynomial-time approximation scheme.
Unsupervised Neural Machine Translation
Authors: Mikel Artetxe, Gorka Labaka, Eneko Agirre, Kyunghyun Cho
Date: 2017-10-30 00:00:00
Proceeding: ICLR 2018 1
Tasks: Decoder, Machine Translation, NMT, Translation, Unsupervised Machine Translation

In spite of the recent success of neural machine translation (NMT) in
standard benchmarks, the lack of large parallel corpora poses a major practical
problem for many language pairs. There have been several proposals to alleviate
this issue with, for instance, triangulation and semi-supervised learning
techniques, but they still require a strong cross-lingual signal. In this work,
we completely remove the need of parallel data and propose a novel method to
train an NMT system in a completely unsupervised manner, relying on nothing but
monolingual corpora. Our model builds upon the recent work on unsupervised
embedding mappings, and consists of a slightly modified attentional
encoder-decoder model that can be trained on monolingual corpora alone using a
combination of denoising and backtranslation. Despite the simplicity of the
approach, our system obtains 15.56 and 10.21 BLEU points in WMT 2014
French-to-English and German-to-English translation. The model can also profit
from small parallel corpora, and attains 21.81 and 15.24 points when combined
with 100,000 parallel sentences, respectively. Our implementation is released
as an open source project.
Stochastic Approximation for Canonical Correlation Analysis
Authors: Raman Arora, Teodor V. Marinov, Poorya Mianjy, Nathan Srebro
Date: 2017-02-22 00:00:00
Proceeding: NeurIPS 2017 12

We propose novel first-order stochastic approximation algorithms for
canonical correlation analysis (CCA). Algorithms presented are instances of
inexact matrix stochastic gradient (MSG) and inexact matrix exponentiated
gradient (MEG), and achieve $\epsilon$-suboptimality in the population
objective in $\operatorname{poly}(\frac{1}{\epsilon})$ iterations. We also
consider practical variants of the proposed algorithms and compare them with
other methods for CCA both theoretically and empirically.
Deep Learning is Robust to Massive Label Noise
Authors: David Rolnick, Andreas Veit, Serge Belongie, Nir Shavit
Date: 2017-05-30 00:00:00
Proceeding: ICLR 2018 1
Tasks: Deep Learning, image-classification, Image Classification

Deep neural networks trained on large supervised datasets have led to
impressive results in image classification and other tasks. However,
well-annotated datasets can be time-consuming and expensive to collect, lending
increased interest to larger but noisy datasets that are more easily obtained.
In this paper, we show that deep neural networks are capable of generalizing
from training data for which true labels are massively outnumbered by incorrect
labels. We demonstrate remarkably high test performance after training on
corrupted data from MNIST, CIFAR, and ImageNet. For example, on MNIST we obtain
test accuracy above 90 percent even after each clean training example has been
diluted with 100 randomly-labeled examples. Such behavior holds across multiple
patterns of label noise, even when erroneous labels are biased towards
confusing classes. We show that training in this regime requires a significant
but manageable increase in dataset size that is related to the factor by which
correct labels have been diluted. Finally, we provide an analysis of our
results that shows how increasing noise decreases the effective batch size.
Self-organizing maps and generalization: an algorithmic description of Numerosity and Variability Effects
Authors: Valentina Gliozzi, Kim Plunkett
Date: 2018-02-26 00:00:00
Tasks: Decision Making

Category, or property generalization is a central function in the human
cognition. It plays a crucial role in a variety of domains, such as learning,
everyday reasoning, specialized reasoning, and decision making. Judging the
content of a dish as edible, a hormone level as healthy, a building as
belonging to the same architectural style as previously seen buildings, are
examples of category generalization. In this paper, we propose self-organizing
maps as candidates to explain the psychological mechanisms underlying category
generalization. Self-organizing maps are psychologically and biologically
plausible neural network models that learn after limited exposure to positive
category examples, without any need of contrastive information. Just like
humans. They reproduce human behavior in category generalization, in particular
for what concerns the well-known Numerosity and Variability effects, which are
usually explained with Bayesian tools. Where category generalization is
concerned, self-organizing maps are good candidates to bridge the gap between
the computational level of analysis in Marr's hierarchy (where Bayesian models
are situated) and the algorithmic level of aanalysis in Marr's hierarchy (where
Bayesian models are situated) and the algorithmic level of analysis in which
plausible mechanisms are described.
The Development of Darwin's Origin of Species
Authors: Jaimie Murdock, Colin Allen, Simon DeDeo
Date: 2018-02-26 00:00:00
Tasks: Topic Models

From 1837, when he returned to England aboard the $\textit{HMS Beagle}$, to
1860, just after publication of $\textit{The Origin of Species}$, Charles
Darwin kept detailed notes of each book he read or wanted to read. His notes
and manuscripts provide information about decades of individual scientific
practice. Previously, we trained topic models on the full texts of each
reading, and applied information-theoretic measures to detect that changes in
his reading patterns coincided with the boundaries of his three major
intellectual projects in the period 1837-1860. In this new work we apply the
reading model to five additional documents, four of them by Darwin: the first
edition of $\textit{The Origin of Species}$, two private essays stating
intermediate forms of his theory in 1842 and 1844, a third essay of disputed
dating, and Alfred Russel Wallace's essay, which Darwin received in 1858. We
address three historical inquiries, previously treated qualitatively: 1) the
mythology of "Darwin's Delay," that despite completing an extensive draft in
1844, Darwin waited until 1859 to publish $\textit{The Origin of Species}$ due
to external pressures; 2) the relationship between Darwin and Wallace's
contemporaneous theories, especially in light of their joint presentation; and
3) dating of the "Outline and Draft" which was rediscovered in 1975 and
postulated first as an 1839 draft preceding the Sketch of 1842, then as an
interstitial draft between the 1842 and 1844 essays.
Self Super-Resolution for Magnetic Resonance Images using Deep Networks
Authors: Can Zhao, Aaron Carass, Blake E. Dewey, Jerry L. Prince
Date: 2018-02-26 00:00:00
Tasks: Super-Resolution

High resolution magnetic resonance~(MR) imaging~(MRI) is desirable in many
clinical applications, however, there is a trade-off between resolution, speed
of acquisition, and noise. It is common for MR images to have worse
through-plane resolution~(slice thickness) than in-plane resolution. In these
MRI images, high frequency information in the through-plane direction is not
acquired, and cannot be resolved through interpolation. To address this issue,
super-resolution methods have been developed to enhance spatial resolution. As
an ill-posed problem, state-of-the-art super-resolution methods rely on the
presence of external/training atlases to learn the transform from low
resolution~(LR) images to high resolution~(HR) images. For several reasons,
such HR atlas images are often not available for MRI sequences. This paper
presents a self super-resolution~(SSR) algorithm, which does not use any
external atlas images, yet can still resolve HR images only reliant on the
acquired LR image. We use a blurred version of the input image to create
training data for a state-of-the-art super-resolution deep network. The trained
network is applied to the original input image to estimate the HR image. Our
SSR result shows a significant improvement on through-plane resolution compared
to competing SSR methods.
Classification of breast cancer histology images using transfer learning
Authors: Sulaiman Vesal, Nishant Ravikumar, Amirabbas Davari, Stephan Ellmann, Andreas Maier
Date: 2018-02-26 00:00:00
Tasks: Classification, Classification Of Breast Cancer Histology Images, General Classification, image-classification, Image Classification, Transfer Learning

Breast cancer is one of the leading causes of mortality in women. Early
detection and treatment are imperative for improving survival rates, which have
steadily increased in recent years as a result of more sophisticated
computer-aided-diagnosis (CAD) systems. A critical component of breast cancer
diagnosis relies on histopathology, a laborious and highly subjective process.
Consequently, CAD systems are essential to reduce inter-rater variability and
supplement the analyses conducted by specialists. In this paper, a
transfer-learning based approach is proposed, for the task of breast histology
image classification into four tissue sub-types, namely, normal, benign,
\textit{in situ} carcinoma and invasive carcinoma. The histology images,
provided as part of the BACH 2018 grand challenge, were first normalized to
correct for color variations resulting from inconsistencies during slide
preparation. Subsequently, image patches were extracted and used to fine-tune
Google`s Inception-V3 and ResNet50 convolutional neural networks (CNNs), both
pre-trained on the ImageNet database, enabling them to learn domain-specific
features, necessary to classify the histology images. The ResNet50 network
(based on residual learning) achieved a test classification accuracy of 97.50%
for four classes, outperforming the Inception-V3 network which achieved an
accuracy of 91.25%.
Do latent tree learning models identify meaningful structure in sentences?
Authors: Adina Williams, Andrew Drozdov, Samuel R. Bowman
Date: 2017-09-04 00:00:00
Proceeding: TACL 2018 1
Tasks: Sentence, Sentence Classification

Recent work on the problem of latent tree learning has made it possible to
train neural networks that learn to both parse a sentence and use the resulting
parse to interpret the sentence, all without exposure to ground-truth parse
trees at training time. Surprisingly, these models often perform better at
sentence understanding tasks than models that use parse trees from conventional
parsers. This paper aims to investigate what these latent tree learning models
learn. We replicate two such models in a shared codebase and find that (i) only
one of these models outperforms conventional tree-structured models on sentence
classification, (ii) its parsing strategies are not especially consistent
across random restarts, (iii) the parses it produces tend to be shallower than
standard Penn Treebank (PTB) parses, and (iv) they do not resemble those of PTB
or any other semantic or syntactic formalism that the authors are aware of.
Improving Graph Convolutional Networks with Non-Parametric Activation Functions
Authors: Simone Scardapane, Steven Van Vaerenbergh, Danilo Comminiello, Aurelio Uncini
Date: 2018-02-26 00:00:00
Tasks: Knowledge Graphs

Graph neural networks (GNNs) are a class of neural networks that allow to
efficiently perform inference on data that is associated to a graph structure,
such as, e.g., citation networks or knowledge graphs. While several variants of
GNNs have been proposed, they only consider simple nonlinear activation
functions in their layers, such as rectifiers or squashing functions. In this
paper, we investigate the use of graph convolutional networks (GCNs) when
combined with more complex activation functions, able to adapt from the
training data. More specifically, we extend the recently proposed kernel
activation function, a non-parametric model which can be implemented easily,
can be regularized with standard $\ell_p$-norms techniques, and is smooth over
its entire domain. Our experimental evaluation shows that the proposed
architecture can significantly improve over its baseline, while similar
improvements cannot be obtained by simply increasing the depth or size of the
original GCN.
Progressive Growing of GANs for Improved Quality, Stability, and Variation
Authors: Tero Karras, Timo Aila, Samuli Laine, Jaakko Lehtinen
Date: 2017-10-27 00:00:00
Proceeding: ICLR 2018 1
Tasks: Face Generation, Image Generation

We describe a new training methodology for generative adversarial networks.
The key idea is to grow both the generator and discriminator progressively:
starting from a low resolution, we add new layers that model increasingly fine
details as training progresses. This both speeds the training up and greatly
stabilizes it, allowing us to produce images of unprecedented quality, e.g.,
CelebA images at 1024^2. We also propose a simple way to increase the variation
in generated images, and achieve a record inception score of 8.80 in
unsupervised CIFAR10. Additionally, we describe several implementation details
that are important for discouraging unhealthy competition between the generator
and discriminator. Finally, we suggest a new metric for evaluating GAN results,
both in terms of image quality and variation. As an additional contribution, we
construct a higher-quality version of the CelebA dataset.
VAE with a VampPrior
Authors: Jakub M. Tomczak, Max Welling
Date: 2017-05-19 00:00:00

Many different methods to train deep generative models have been introduced
in the past. In this paper, we propose to extend the variational auto-encoder
(VAE) framework with a new type of prior which we call "Variational Mixture of
Posteriors" prior, or VampPrior for short. The VampPrior consists of a mixture
distribution (e.g., a mixture of Gaussians) with components given by
variational posteriors conditioned on learnable pseudo-inputs. We further
extend this prior to a two layer hierarchical model and show that this
architecture with a coupled prior and posterior, learns significantly better
models. The model also avoids the usual local optima issues related to useless
latent dimensions that plague VAEs. We provide empirical studies on six
datasets, namely, static and binary MNIST, OMNIGLOT, Caltech 101 Silhouettes,
Frey Faces and Histopathology patches, and show that applying the hierarchical
VampPrior delivers state-of-the-art results on all datasets in the unsupervised
permutation invariant setting and the best results or comparable to SOTA
methods for the approach with convolutional networks.
Efficient Large Scale Clustering based on Data Partitioning
Authors: Malika Bendechache, Nhien-An Le-Khac, M-Tahar Kechadi
Date: 2017-04-11 00:00:00
Tasks: Clustering

Clustering techniques are very attractive for extracting and identifying
patterns in datasets. However, their application to very large spatial datasets
presents numerous challenges such as high-dimensionality data, heterogeneity,
and high complexity of some algorithms. For instance, some algorithms may have
linear complexity but they require the domain knowledge in order to determine
their input parameters. Distributed clustering techniques constitute a very
good alternative to the big data challenges (e.g.,Volume, Variety, Veracity,
and Velocity). Usually these techniques consist of two phases. The first phase
generates local models or patterns and the second one tends to aggregate the
local results to obtain global models. While the first phase can be executed in
parallel on each site and, therefore, efficient, the aggregation phase is
complex, time consuming and may produce incorrect and ambiguous global clusters
and therefore incorrect models. In this paper we propose a new distributed
clustering approach to deal efficiently with both phases, generation of local
results and generation of global models by aggregation. For the first phase,
our approach is capable of analysing the datasets located in each site using
different clustering techniques. The aggregation phase is designed in such a
way that the final clusters are compact and accurate while the overall process
is efficient in time and memory allocation. For the evaluation, we use two
well-known clustering algorithms, K-Means and DBSCAN. One of the key outputs of
this distributed clustering technique is that the number of global clusters is
dynamic, no need to be fixed in advance. Experimental results show that the
approach is scalable and produces high quality results.
Learning Anonymized Representations with Adversarial Neural Networks
Authors: Clément Feutry, Pablo Piantanida, Yoshua Bengio, Pierre Duhamel
Date: 2018-02-26 00:00:00
Tasks: Representation Learning, Sentiment Analysis

Statistical methods protecting sensitive information or the identity of the
data owner have become critical to ensure privacy of individuals as well as of
organizations. This paper investigates anonymization methods based on
representation learning and deep neural networks, and motivated by novel
information theoretical bounds. We introduce a novel training objective for
simultaneously training a predictor over target variables of interest (the
regular labels) while preventing an intermediate representation to be
predictive of the private labels. The architecture is based on three
sub-networks: one going from input to representation, one from representation
to predicted regular labels, and one from representation to predicted private
labels. The training procedure aims at learning representations that preserve
the relevant part of the information (about regular labels) while dismissing
information about the private labels which correspond to the identity of a
person. We demonstrate the success of this approach for two distinct
classification versus anonymization tasks (handwritten digits and sentiment
analysis).
Using Curvilinear Features in Focus for Registering a Single Image to a 3D Object
Authors: Hatem A. Rashwan, Sylvie Chambon, Pierre Gurdjos, Géraldine Morin, Vincent Charvillat
Date: 2018-02-26 00:00:00
Tasks: Pose Estimation

In the context of 2D/3D registration, this paper introduces an approach that
allows to match features detected in two different modalities: photographs and
3D models, by using a common 2D reprensentation. More precisely, 2D images are
matched with a set of depth images, representing the 3D model. After
introducing the concept of curvilinear saliency, related to curvature
estimation, we propose a new ridge and valley detector for depth images
rendered from 3D model. A variant of this detector is adapted to photographs,
in particular by applying it in multi-scale and by combining this feature
detector with the principle of focus curves. Finally, a registration algorithm
for determining the correct viewpoint of the 3D model and thus the pose is
proposed. It is based on using histogram of gradients features adapted to the
features manipulated in 2D and in 3D, and the introduction of repeatability
scores. The results presented highlight the quality of the features detected,
in term of repeatability, and also the interest of the approach for
registration and pose estimation.
DropLasso: A robust variant of Lasso for single cell RNA-seq data
Authors: Beyrem Khalfaoui, Jean-Philippe Vert
Date: 2018-02-26 00:00:00

Single-cell RNA sequencing (scRNA-seq) is a fast growing approach to measure
the genome-wide transcriptome of many individual cells in parallel, but results
in noisy data with many dropout events. Existing methods to learn molecular
signatures from bulk transcriptomic data may therefore not be adapted to
scRNA-seq data, in order to automatically classify individual cells into
predefined classes. We propose a new method called DropLasso to learn a
molecular signature from scRNA-seq data. DropLasso extends the dropout
regularisation technique, popular in neural network training, to esti- mate
sparse linear models. It is well adapted to data corrupted by dropout noise,
such as scRNA-seq data, and we clarify how it relates to elastic net
regularisation. We provide promising results on simulated and real scRNA-seq
data, suggesting that DropLasso may be better adapted than standard regularisa-
tions to infer molecular signatures from scRNA-seq data.
Word sense disambiguation: a complex network approach
Authors: Edilson A. Correa Jr., Alneu de Andrade Lopes, Diego R. Amancio
Date: 2016-06-25 00:00:00
Tasks: Attribute, Word Sense Disambiguation

In recent years, concepts and methods of complex networks have been employed
to tackle the word sense disambiguation (WSD) task by representing words as
nodes, which are connected if they are semantically similar. Despite the
increasingly number of studies carried out with such models, most of them use
networks just to represent the data, while the pattern recognition performed on
the attribute space is performed using traditional learning techniques. In
other words, the structural relationship between words have not been explicitly
used in the pattern recognition process. In addition, only a few investigations
have probed the suitability of representations based on bipartite networks and
graphs (bigraphs) for the problem, as many approaches consider all possible
links between words. In this context, we assess the relevance of a bipartite
network model representing both feature words (i.e. the words characterizing
the context) and target (ambiguous) words to solve ambiguities in written
texts. Here, we focus on the semantical relationships between these two type of
words, disregarding the relationships between feature words. In special, the
proposed method not only serves to represent texts as graphs, but also
constructs a structure on which the discrimination of senses is accomplished.
Our results revealed that the proposed learning algorithm in such bipartite
networks provides excellent results mostly when topical features are employed
to characterize the context. Surprisingly, our method even outperformed the
support vector machine algorithm in particular cases, with the advantage of
being robust even if a small training dataset is available. Taken together, the
results obtained here show that the proposed representation/classification
method might be useful to improve the semantical characterization of written
texts.
Scalable Recollections for Continual Lifelong Learning
Authors: Matthew Riemer, Tim Klinger, Djallel Bouneffouf, Michele Franceschini
Date: 2017-11-17 00:00:00
Tasks: Lifelong learning

Given the recent success of Deep Learning applied to a variety of single
tasks, it is natural to consider more human-realistic settings. Perhaps the
most difficult of these settings is that of continual lifelong learning, where
the model must learn online over a continuous stream of non-stationary data. A
successful continual lifelong learning system must have three key capabilities:
it must learn and adapt over time, it must not forget what it has learned, and
it must be efficient in both training time and memory. Recent techniques have
focused their efforts primarily on the first two capabilities while questions
of efficiency remain largely unexplored. In this paper, we consider the problem
of efficient and effective storage of experiences over very large time-frames.
In particular we consider the case where typical experiences are O(n) bits and
memories are limited to O(k) bits for k << n. We present a novel scalable
architecture and training algorithm in this challenging domain and provide an
extensive evaluation of its performance. Our results show that we can achieve
considerable gains on top of state-of-the-art methods such as GEM.