pwc-archive/papers-with-abstracts huggingface dataset:
CT Image Denoising with Perceptive Deep Neural Networks
Authors: Qingsong Yang, Pingkun Yan, Mannudeep K. Kalra, Ge Wang
Date: 2017-02-22 00:00:00
Tasks: Denoising, Diagnostic, Image Denoising

Increasing use of CT in modern medical practice has raised concerns over
associated radiation dose. Reduction of radiation dose associated with CT can
increase noise and artifacts, which can adversely affect diagnostic confidence.
Denoising of low-dose CT images on the other hand can help improve diagnostic
confidence, which however is a challenging problem due to its ill-posed nature,
since one noisy image patch may correspond to many different output patches. In
the past decade, machine learning based approaches have made quite impressive
progress in this direction. However, most of those methods, including the
recently popularized deep learning techniques, aim for minimizing
mean-squared-error (MSE) between a denoised CT image and the ground truth,
which results in losing important structural details due to over-smoothing,
although the PSNR based performance measure looks great. In this work, we
introduce a new perceptual similarity measure as the objective function for a
deep convolutional neural network to facilitate CT image denoising. Instead of
directly computing MSE for pixel-to-pixel intensity loss, we compare the
perceptual features of a denoised output against those of the ground truth in a
feature space. Therefore, our proposed method is capable of not only reducing
the image noise levels, but also keeping the critical structural information at
the same time. Promising results have been obtained in our experiments with a
large number of CT images.
Unsupervised Learning of Morphological Forests
Authors: Jiaming Luo, Karthik Narasimhan, Regina Barzilay
Date: 2017-02-22 00:00:00
Proceeding: TACL 2017 1
Tasks: Clustering

This paper focuses on unsupervised modeling of morphological families,
collectively comprising a forest over the language vocabulary. This formulation
enables us to capture edgewise properties reflecting single-step morphological
derivations, along with global distributional properties of the entire forest.
These global properties constrain the size of the affix set and encourage
formation of tight morphological families. The resulting objective is solved
using Integer Linear Programming (ILP) paired with contrastive estimation. We
train the model by alternating between optimizing the local log-linear model
and the global ILP objective. We evaluate our system on three tasks: root
detection, clustering of morphological families and segmentation. Our
experiments demonstrate that our model yields consistent gains in all three
tasks compared with the best published results.
Synthesising Dynamic Textures using Convolutional Neural Networks
Authors: Christina M. Funke, Leon A. Gatys, Alexander S. Ecker, Matthias Bethge
Date: 2017-02-22 00:00:00
Tasks: Object Recognition

Here we present a parametric model for dynamic textures. The model is based
on spatiotemporal summary statistics computed from the feature representations
of a Convolutional Neural Network (CNN) trained on object recognition. We
demonstrate how the model can be used to synthesise new samples of dynamic
textures and to predict motion in simple movies.
Large-Scale Stochastic Learning using GPUs
Authors: Thomas Parnell, Celestine Dünner, Kubilay Atasu, Manolis Sifalakis, Haris Pozidis
Date: 2017-02-22 00:00:00
Tasks: CPU, GPU

In this work we propose an accelerated stochastic learning system for very
large-scale applications. Acceleration is achieved by mapping the training
algorithm onto massively parallel processors: we demonstrate a parallel,
asynchronous GPU implementation of the widely used stochastic coordinate
descent/ascent algorithm that can provide up to 35x speed-up over a sequential
CPU implementation. In order to train on very large datasets that do not fit
inside the memory of a single GPU, we then consider techniques for distributed
stochastic learning. We propose a novel method for optimally aggregating model
updates from worker nodes when the training data is distributed either by
example or by feature. Using this technique, we demonstrate that one can scale
out stochastic learning across up to 8 worker nodes without any significant
loss of training time. Finally, we combine GPU acceleration with the optimized
distributed method to train on a dataset consisting of 200 million training
examples and 75 million features. We show by scaling out across 4 GPUs, one can
attain a high degree of training accuracy in around 4 seconds: a 20x speed-up
in training time compared to a multi-threaded, distributed implementation
across 4 CPUs.
Theoretical and Experimental Analysis of the Canadian Traveler Problem
Authors: Doron Zarchy
Date: 2017-02-22 00:00:00

Devising an optimal strategy for navigation in a partially observable
environment is one of the key objectives in AI. One of the problem in this
context is the Canadian Traveler Problem (CTP). CTP is a navigation problem
where an agent is tasked to travel from source to target in a partially
observable weighted graph, whose edge might be blocked with a certain
probability and observing such blockage occurs only when reaching upon one of
the edges end points. The goal is to find a strategy that minimizes the
expected travel cost. The problem is known to be P$\#$ hard. In this work we
study the CTP theoretically and empirically. First, we study the Dep-CTP, a CTP
variant we introduce which assumes dependencies between the edges status. We
show that Dep-CTP is intractable, and further we analyze two of its subclasses
on disjoint paths graph. Second, we develop a general algorithm Gen-PAO that
optimally solve the CTP. Gen-PAO is capable of solving two other types of CTP
called Sensing-CTP and Expensive-Edges CTP. Since the CTP is intractable,
Gen-PAO use some pruning methods to reduce the space search for the optimal
solution. We also define some variants of Gen-PAO, compare their performance
and show some benefits of Gen-PAO over existing work.
Moving Beyond the Turing Test with the Allen AI Science Challenge
Authors: Carissa Schoenick, Peter Clark, Oyvind Tafjord, Peter Turney, Oren Etzioni
Date: 2016-04-14 00:00:00
Tasks: Question Answering

Given recent successes in AI (e.g., AlphaGo's victory against Lee Sedol in
the game of GO), it's become increasingly important to assess: how close are AI
systems to human-level intelligence? This paper describes the Allen AI Science
Challenge---an approach towards that goal which led to a unique Kaggle
Competition, its results, the lessons learned, and our next steps.
On Polynomial Time Methods for Exact Low Rank Tensor Completion
Authors: Dong Xia, Ming Yuan
Date: 2017-02-22 00:00:00

In this paper, we investigate the sample size requirement for exact recovery
of a high order tensor of low rank from a subset of its entries. We show that a
gradient descent algorithm with initial value obtained from a spectral method
can, in particular, reconstruct a ${d\times d\times d}$ tensor of multilinear
ranks $(r,r,r)$ with high probability from as few as
$O(r^{7/2}d^{3/2}\log^{7/2}d+r^7d\log^6d)$ entries. In the case when the ranks
$r=O(1)$, our sample size requirement matches those for nuclear norm
minimization (Yuan and Zhang, 2016a), or alternating least squares assuming
orthogonal decomposability (Jain and Oh, 2014). Unlike these earlier
approaches, however, our method is efficient to compute, easy to implement, and
does not impose extra structures on the tensor. Numerical results are presented
to further demonstrate the merits of the proposed approach.
Heavy-Tailed Analogues of the Covariance Matrix for ICA
Authors: Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher
Date: 2017-02-22 00:00:00

Independent Component Analysis (ICA) is the problem of learning a square
matrix $A$, given samples of $X=AS$, where $S$ is a random vector with
independent coordinates. Most existing algorithms are provably efficient only
when each $S_i$ has finite and moderately valued fourth moment. However, there
are practical applications where this assumption need not be true, such as
speech and finance. Algorithms have been proposed for heavy-tailed ICA, but
they are not practical, using random walks and the full power of the ellipsoid
algorithm multiple times. The main contributions of this paper are:
  (1) A practical algorithm for heavy-tailed ICA that we call HTICA. We provide
theoretical guarantees and show that it outperforms other algorithms in some
heavy-tailed regimes, both on real and synthetic data. Like the current
state-of-the-art, the new algorithm is based on the centroid body (a first
moment analogue of the covariance matrix). Unlike the state-of-the-art, our
algorithm is practically efficient. To achieve this, we use explicit analytic
representations of the centroid body, which bypasses the use of the ellipsoid
method and random walks.
  (2) We study how heavy tails affect different ICA algorithms, including
HTICA. Somewhat surprisingly, we show that some algorithms that use the
covariance matrix or higher moments can successfully solve a range of ICA
instances with infinite second moment. We study this theoretically and
experimentally, with both synthetic and real-world heavy-tailed data.
Approximations of the Restless Bandit Problem
Authors: Steffen Grunewalder, Azadeh Khaleghi
Date: 2017-02-22 00:00:00

The multi-armed restless bandit problem is studied in the case where the
pay-off distributions are stationary $\varphi$-mixing. This version of the
problem provides a more realistic model for most real-world applications, but
cannot be optimally solved in practice, since it is known to be PSPACE-hard.
The objective of this paper is to characterize a sub-class of the problem where
{\em good} approximate solutions can be found using tractable approaches.
Specifically, it is shown that under some conditions on the $\varphi$-mixing
coefficients, a modified version of UCB can prove effective. The main challenge
is that, unlike in the i.i.d. setting, the distributions of the sampled
pay-offs may not have the same characteristics as those of the original bandit
arms. In particular, the $\varphi$-mixing property does not necessarily carry
over. This is overcome by carefully controlling the effect of a sampling policy
on the pay-off distributions. Some of the proof techniques developed in this
paper can be more generally used in the context of online sampling under
dependence. Proposed algorithms are accompanied with corresponding regret
analysis.
Stochastic Neighbor Embedding separates well-separated clusters
Authors: Uri Shaham, Stefan Steinerberger
Date: 2017-02-09 00:00:00
Tasks: Dimensionality Reduction

Stochastic Neighbor Embedding and its variants are widely used dimensionality
reduction techniques -- despite their popularity, no theoretical results are
known. We prove that the optimal SNE embedding of well-separated clusters from
high dimensions to any Euclidean space R^d manages to successfully separate the
clusters in a quantitative way. The result also applies to a larger family of
methods including a variant of t-SNE.
A Realistic Dataset for the Smart Home Device Scheduling Problem for DCOPs
Authors: William Kluegel, Muhammad Aamir Iqbal, Ferdinando Fioretto, William Yeoh, Enrico Pontelli
Date: 2017-02-22 00:00:00
Tasks: Scheduling

The field of Distributed Constraint Optimization has gained momentum in
recent years thanks to its ability to address various applications related to
multi-agent cooperation. While techniques to solve Distributed Constraint
Optimization Problems (DCOPs) are abundant and have matured substantially since
the field inception, the number of DCOP realistic applications and benchmark
used to asses the performance of DCOP algorithms is lagging behind. To contrast
this background we (i) introduce the Smart Home Device Scheduling (SHDS)
problem, which describe the problem of coordinating smart devices schedules
across multiple homes as a multi-agent system, (ii) detail the physical models
adopted to simulate smart sensors, smart actuators, and homes environments, and
(iii) introduce a DCOP realistic benchmark for SHDS problems.
An Algebraic Formalization of Forward and Forward-backward Algorithms
Authors: Ai Azuma, Masashi Shimbo, Yuji Matsumoto
Date: 2017-02-22 00:00:00

In this paper, we propose an algebraic formalization of the two important
classes of dynamic programming algorithms called forward and forward-backward
algorithms. They are generalized extensively in this study so that a wide range
of other existing algorithms is subsumed. Forward algorithms generalized in
this study subsume the ordinary forward algorithm on trellises for sequence
labeling, the inside algorithm on derivation forests for CYK parsing, a
unidirectional message passing on acyclic factor graphs, the forward mode of
automatic differentiation on computation graphs with addition and
multiplication, and so on. In addition, we reveal algebraic structures
underlying complicated computation with forward algorithms. By the aid of the
revealed algebraic structures, we also propose a systematic framework to design
complicated variants of forward algorithms. Forward-backward algorithms
generalized in this study subsume the ordinary forward-backward algorithm on
trellises for sequence labeling, the inside-outside algorithm on derivation
forests for CYK parsing, the sum-product algorithm on acyclic factor graphs,
the reverse mode of automatic differentiation (a.k.a. back propagation) on
computation graphs with addition and multiplication, and so on. We also propose
an algebraic characterization of what can be computed by forward-backward
algorithms and elucidate the relationship between forward and forward-backward
algorithms.
Adversarial Delays in Online Strongly-Convex Optimization
Authors: Daniel Khashabi, Kent Quanrud, Amirhossein Taghvaei
Date: 2016-05-20 00:00:00

We consider the problem of strongly-convex online optimization in presence of adversarial delays; in a T-iteration online game, the feedback of the player's query at time t is arbitrarily delayed by an adversary for d_t rounds and delivered before the game ends, at iteration t+d_t-1. Specifically for \algo{online-gradient-descent} algorithm we show it has a simple regret bound of \Oh{\sum_{t=1}^T \log (1+ \frac{d_t}{t})}. This gives a clear and simple bound without resorting any distributional and limiting assumptions on the delays. We further show how this result encompasses and generalizes several of the existing known results in the literature. Specifically it matches the celebrated logarithmic regret \Oh{\log T} when there are no delays (i.e. d_t = 1) and regret bound of \Oh{\tau \log T} for constant delays d_t = \tau.
Realization of Ontology Web Search Engine
Authors: Olegs Verhodubs
Date: 2017-02-22 00:00:00

This paper describes the realization of the Ontology Web Search Engine. The
Ontology Web Search Engine is realizable as independent project and as a part
of other projects. The main purpose of this paper is to present the Ontology
Web Search Engine realization details as the part of the Semantic Web Expert
System and to present the results of the Ontology Web Search Engine
functioning. It is expected that the Semantic Web Expert System will be able to
process ontologies from the Web, generate rules from these ontologies and
develop its knowledge base.
Distributed Representation of Subgraphs
Authors: Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, B. Aditya Prakash
Date: 2017-02-22 00:00:00
Tasks: Community Detection, Node Classification

Network embeddings have become very popular in learning effective feature
representations of networks. Motivated by the recent successes of embeddings in
natural language processing, researchers have tried to find network embeddings
in order to exploit machine learning algorithms for mining tasks like node
classification and edge prediction. However, most of the work focuses on
finding distributed representations of nodes, which are inherently ill-suited
to tasks such as community detection which are intuitively dependent on
subgraphs.
  Here, we propose sub2vec, an unsupervised scalable algorithm to learn feature
representations of arbitrary subgraphs. We provide means to characterize
similarties between subgraphs and provide theoretical analysis of sub2vec and
demonstrate that it preserves the so-called local proximity. We also highlight
the usability of sub2vec by leveraging it for network mining tasks, like
community detection. We show that sub2vec gets significant gains over
state-of-the-art methods and node-embedding methods. In particular, sub2vec
offers an approach to generate a richer vocabulary of features of subgraphs to
support representation and reasoning.
Convergence rates for pretraining and dropout: Guiding learning parameters using network structure
Authors: Vamsi K. Ithapu, Sathya Ravi, Vikas Singh
Date: 2015-06-10 00:00:00
Tasks: Denoising

Unsupervised pretraining and dropout have been well studied, especially with
respect to regularization and output consistency. However, our understanding
about the explicit convergence rates of the parameter estimates, and their
dependence on the learning (like denoising and dropout rate) and structural
(like depth and layer lengths) aspects of the network is less mature. An
interesting question in this context is to ask if the network structure could
"guide" the choices of such learning parameters. In this work, we explore these
gaps between network structure, the learning mechanisms and their interaction
with parameter convergence rates. We present a way to address these issues
based on the backpropagation convergence rates for general nonconvex objectives
using first-order information. We then incorporate two learning mechanisms into
this general framework -- denoising autoencoder and dropout, and subsequently
derive the convergence rates of deep networks. Building upon these bounds, we
provide insights into the choices of learning parameters and network sizes that
achieve certain levels of convergence accuracy. The results derived here
support existing empirical observations, and we also conduct a set of
experiments to evaluate them.
On the interplay of network structure and gradient convergence in deep learning
Authors: Vamsi K. Ithapu, Sathya N. Ravi, Vikas Singh
Date: 2015-11-17 00:00:00
Tasks: Denoising

The regularization and output consistency behavior of dropout and layer-wise
pretraining for learning deep networks have been fairly well studied. However,
our understanding of how the asymptotic convergence of backpropagation in deep
architectures is related to the structural properties of the network and other
design choices (like denoising and dropout rate) is less clear at this time. An
interesting question one may ask is whether the network architecture and input
data statistics may guide the choices of learning parameters and vice versa. In
this work, we explore the association between such structural, distributional
and learnability aspects vis-\`a-vis their interaction with parameter
convergence rates. We present a framework to address these questions based on
convergence of backpropagation for general nonconvex objectives using
first-order information. This analysis suggests an interesting relationship
between feature denoising and dropout. Building upon these results, we obtain a
setup that provides systematic guidance regarding the choice of learning
parameters and network sizes that achieve a certain level of convergence (in
the optimization sense) often mediated by statistical attributes of the inputs.
Our results are supported by a set of experimental evaluations as well as
independent empirical observations reported by other groups.
liquidSVM: A Fast and Versatile SVM package
Authors: Ingo Steinwart, Philipp Thomann
Date: 2017-02-22 00:00:00
Tasks: General Classification, GPU, regression

liquidSVM is a package written in C++ that provides SVM-type solvers for
various classification and regression tasks. Because of a fully integrated
hyper-parameter selection, very carefully implemented solvers, multi-threading
and GPU support, and several built-in data decomposition strategies it provides
unprecedented speed for small training sizes as well as for data sets of tens
of millions of samples. Besides the C++ API and a command line interface,
bindings to R, MATLAB, Java, Python, and Spark are available. We present a
brief description of the package and report experimental comparisons to other
SVM packages.
EVE: Explainable Vector Based Embedding Technique Using Wikipedia
Authors: M. Atif Qureshi, Derek Greene
Date: 2017-02-22 00:00:00

We present an unsupervised explainable word embedding technique, called EVE,
which is built upon the structure of Wikipedia. The proposed model defines the
dimensions of a semantic vector representing a word using human-readable
labels, thereby it readily interpretable. Specifically, each vector is
constructed using the Wikipedia category graph structure together with the
Wikipedia article link structure. To test the effectiveness of the proposed
word embedding model, we consider its usefulness in three fundamental tasks: 1)
intruder detection - to evaluate its ability to identify a non-coherent vector
from a list of coherent vectors, 2) ability to cluster - to evaluate its
tendency to group related vectors together while keeping unrelated vectors in
separate clusters, and 3) sorting relevant items first - to evaluate its
ability to rank vectors (items) relevant to the query in the top order of the
result. For each task, we also propose a strategy to generate a task-specific
human-interpretable explanation from the model. These demonstrate the overall
effectiveness of the explainable embeddings generated by EVE. Finally, we
compare EVE with the Word2Vec, FastText, and GloVe embedding techniques across
the three tasks, and report improvements over the state-of-the-art.
Recognition of Visually Perceived Compositional Human Actions by Multiple Spatio-Temporal Scales Recurrent Neural Networks
Authors: Haanvid Lee, Minju Jung, Jun Tani
Date: 2016-02-05 00:00:00

The current paper proposes a novel neural network model for recognizing
visually perceived human actions. The proposed multiple spatio-temporal scales
recurrent neural network (MSTRNN) model is derived by introducing multiple
timescale recurrent dynamics to the conventional convolutional neural network
model. One of the essential characteristics of the MSTRNN is that its
architecture imposes both spatial and temporal constraints simultaneously on
the neural activity which vary in multiple scales among different layers. As
suggested by the principle of the upward and downward causation, it is assumed
that the network can develop meaningful structures such as functional hierarchy
by taking advantage of such constraints during the course of learning. To
evaluate the characteristics of the model, the current study uses three types
of human action video dataset consisting of different types of primitive
actions and different levels of compositionality on them. The performance of
the MSTRNN in testing with these dataset is compared with the ones by other
representative deep learning models used in the field. The analysis of the
internal representation obtained through the learning with the dataset
clarifies what sorts of functional hierarchy can be developed by extracting the
essential compositionality underlying the dataset.