pwc-archive/papers-with-abstracts huggingface dataset:
On the Quality of the Initial Basin in Overspecified Neural Networks
Authors: Itay Safran, Ohad Shamir
Date: 2015-11-13 00:00:00

Deep learning, in the form of artificial neural networks, has achieved
remarkable practical success in recent years, for a variety of difficult
machine learning applications. However, a theoretical explanation for this
remains a major open problem, since training neural networks involves
optimizing a highly non-convex objective function, and is known to be
computationally hard in the worst case. In this work, we study the
\emph{geometric} structure of the associated non-convex objective function, in
the context of ReLU networks and starting from a random initialization of the
network parameters. We identify some conditions under which it becomes more
favorable to optimization, in the sense of (i) High probability of initializing
at a point from which there is a monotonically decreasing path to a global
minimum; and (ii) High probability of initializing at a basin (suitably
defined) with a small minimal objective value. A common theme in our results is
that such properties are more likely to hold for larger ("overspecified")
networks, which accords with some recent empirical and theoretical
observations.
A Hierarchical Latent Variable Encoder-Decoder Model for Generating Dialogues
Authors: Iulian Vlad Serban, Alessandro Sordoni, Ryan Lowe, Laurent Charlin, Joelle Pineau, Aaron Courville, Yoshua Bengio
Date: 2016-05-19 00:00:00
Tasks: Decoder, Response Generation

Sequential data often possesses a hierarchical structure with complex
dependencies between subsequences, such as found between the utterances in a
dialogue. In an effort to model this kind of generative process, we propose a
neural network-based generative architecture, with latent stochastic variables
that span a variable number of time steps. We apply the proposed model to the
task of dialogue response generation and compare it with recent neural network
architectures. We evaluate the model performance through automatic evaluation
metrics and by carrying out a human evaluation. The experiments demonstrate
that our model improves upon recently proposed models and that the latent
variables facilitate the generation of long outputs and maintain the context.
Multiresolution Recurrent Neural Networks: An Application to Dialogue Response Generation
Authors: Iulian Vlad Serban, Tim Klinger, Gerald Tesauro, Kartik Talamadupula, Bo-Wen Zhou, Yoshua Bengio, Aaron Courville
Date: 2016-06-02 00:00:00
Tasks: Dialogue Generation, Response Generation, Text Generation

We introduce the multiresolution recurrent neural network, which extends the
sequence-to-sequence framework to model natural language generation as two
parallel discrete stochastic processes: a sequence of high-level coarse tokens,
and a sequence of natural language tokens. There are many ways to estimate or
learn the high-level coarse tokens, but we argue that a simple extraction
procedure is sufficient to capture a wealth of high-level discourse semantics.
Such procedure allows training the multiresolution recurrent neural network by
maximizing the exact joint log-likelihood over both sequences. In contrast to
the standard log- likelihood objective w.r.t. natural language tokens (word
perplexity), optimizing the joint log-likelihood biases the model towards
modeling high-level abstractions. We apply the proposed model to the task of
dialogue response generation in two challenging domains: the Ubuntu technical
support domain, and Twitter conversations. On Ubuntu, the model outperforms
competing approaches by a substantial margin, achieving state-of-the-art
results according to both automatic evaluation metrics and a human evaluation
study. On Twitter, the model appears to generate more relevant and on-topic
responses according to automatic evaluation metrics. Finally, our experiments
demonstrate that the proposed model is more adept at overcoming the sparsity of
natural language and is better able to capture long-term structure.
Micro-interventions in urban transport from pattern discovery on the flow of passengers and on the bus network
Authors: Carlos Caminha, Vasco Furtado, Vládia Pinheiro e Caio Ponte
Date: 2016-06-14 00:00:00

In this paper, we describe a case study in a big metropolis, in which from
data collected by digital sensors, we tried to understand mobility patterns of
persons using buses and how this can generate knowledge to suggest
interventions that are applied incrementally into the transportation network in
use. We have first estimated an Origin-Destination matrix of buses users from
datasets about the ticket validation and GPS positioning of buses. Then we
represent the supply of buses with their routes through bus stops as a complex
network, which allowed us to understand the bottlenecks of the current scenario
and, in particular, applying community discovery techniques, to identify
clusters that the service supply infrastructure has. Finally, from the
superimposing of the flow of people represented in the OriginDestination matrix
in the supply network, we exemplify how micro-interventions can be prospected
by means of an example of the introduction of express routes.
Causal Discovery for Manufacturing Domains
Authors: Katerina Marazopoulou, Rumi Ghosh, Prasanth Lade, David Jensen
Date: 2016-05-13 00:00:00
Tasks: Causal Discovery

Yield and quality improvement is of paramount importance to any manufacturing
company. One of the ways of improving yield is through discovery of the root
causal factors affecting yield. We propose the use of data-driven interpretable
causal models to identify key factors affecting yield. We focus on factors that
are measured in different stages of production and testing in the manufacturing
cycle of a product. We apply causal structure learning techniques on real data
collected from this line. Specifically, the goal of this work is to learn
interpretable causal models from observational data produced by manufacturing
lines.
  Emphasis has been given to the interpretability of the models to make them
actionable in the field of manufacturing. We highlight the challenges presented
by assembly line data and propose ways to alleviate them.We also identify
unique characteristics of data originating from assembly lines and how to
leverage them in order to improve causal discovery. Standard evaluation
techniques for causal structure learning shows that the learned causal models
seem to closely represent the underlying latent causal relationship between
different factors in the production process. These results were also validated
by manufacturing domain experts who found them promising. This work
demonstrates how data mining and knowledge discovery can be used for root cause
analysis in the domain of manufacturing and connected industry.
Modal-set estimation with an application to clustering
Authors: Heinrich Jiang, Samory Kpotufe
Date: 2016-06-13 00:00:00
Tasks: Clustering

We present a first procedure that can estimate -- with statistical
consistency guarantees -- any local-maxima of a density, under benign
distributional conditions. The procedure estimates all such local maxima, or
$\textit{modal-sets}$, of any bounded shape or dimension, including usual
point-modes. In practice, modal-sets can arise as dense low-dimensional
structures in noisy data, and more generally serve to better model the rich
variety of locally-high-density structures in data.
  The procedure is then shown to be competitive on clustering applications, and
moreover is quite stable to a wide range of settings of its tuning parameter.
Using Virtual Humans to Understand Real Ones
Authors: Katie Hoemann, Behnaz Rezaei, Stacy C. Marsella, Sarah Ostadabbas
Date: 2016-06-13 00:00:00

Human interactions are characterized by explicit as well as implicit channels
of communication. While the explicit channel transmits overt messages, the
implicit ones transmit hidden messages about the communicator (e.g., his/her
intentions and attitudes). There is a growing consensus that providing a
computer with the ability to manipulate implicit affective cues should allow
for a more meaningful and natural way of studying particular non-verbal signals
of human-human communications by human-computer interactions. In this pilot
study, we created a non-dynamic human-computer interaction while manipulating
three specific non-verbal channels of communication: gaze pattern, facial
expression, and gesture. Participants rated the virtual agent on affective
dimensional scales (pleasure, arousal, and dominance) while their physiological
signal (electrodermal activity, EDA) was captured during the interaction.
Assessment of the behavioral data revealed a significant and complex three-way
interaction between gaze, gesture, and facial configuration on the dimension of
pleasure, as well as a main effect of gesture on the dimension of dominance.
These results suggest a complex relationship between different non-verbal cues
and the social context in which they are interpreted. Qualifying considerations
as well as possible next steps are further discussed in light of these
exploratory findings.
Zero-Resource Translation with Multi-Lingual Neural Machine Translation
Authors: Orhan Firat, Baskaran Sankaran, Yaser Al-Onaizan, Fatos T. Yarman Vural, Kyunghyun Cho
Date: 2016-06-13 00:00:00
Proceeding: EMNLP 2016 11
Tasks: Machine Translation, Translation

In this paper, we propose a novel finetuning algorithm for the recently
introduced multi-way, mulitlingual neural machine translate that enables
zero-resource machine translation. When used together with novel many-to-one
translation strategies, we empirically show that this finetuning algorithm
allows the multi-way, multilingual model to translate a zero-resource language
pair (1) as well as a single-pair neural translation model trained with up to
1M direct parallel sentences of the same language pair and (2) better than
pivot-based translation strategy, while keeping only one additional copy of
attention-related parameters.
A Gaussian Mixture MRF for Model-Based Iterative Reconstruction with Applications to Low-Dose X-ray CT
Authors: Ruoqiao Zhang, Dong Hye Ye, Debashish Pal, Jean-Baptiste Thibault, Ken D. Sauer, Charles A. Bouman
Date: 2016-05-12 00:00:00
Tasks: CT Reconstruction, Denoising, Image Denoising, parameter estimation

Markov random fields (MRFs) have been widely used as prior models in various
inverse problems such as tomographic reconstruction. While MRFs provide a
simple and often effective way to model the spatial dependencies in images,
they suffer from the fact that parameter estimation is difficult. In practice,
this means that MRFs typically have very simple structure that cannot
completely capture the subtle characteristics of complex images.
  In this paper, we present a novel Gaussian mixture Markov random field model
(GM-MRF) that can be used as a very expressive prior model for inverse problems
such as denoising and reconstruction. The GM-MRF forms a global image model by
merging together individual Gaussian-mixture models (GMMs) for image patches.
In addition, we present a novel analytical framework for computing MAP
estimates using the GM-MRF prior model through the construction of surrogate
functions that result in a sequence of quadratic optimizations. We also
introduce a simple but effective method to adjust the GM-MRF so as to control
the sharpness in low- and high-contrast regions of the reconstruction
separately. We demonstrate the value of the model with experiments including
image denoising and low-dose CT reconstruction.
Sample Complexity of Automated Mechanism Design
Authors: Maria-Florina Balcan, Tuomas Sandholm, Ellen Vitercik
Date: 2016-06-13 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Combinatorial Optimization, Learning Theory

The design of revenue-maximizing combinatorial auctions, i.e. multi-item
auctions over bundles of goods, is one of the most fundamental problems in
computational economics, unsolved even for two bidders and two items for sale.
In the traditional economic models, it is assumed that the bidders' valuations
are drawn from an underlying distribution and that the auction designer has
perfect knowledge of this distribution. Despite this strong and oftentimes
unrealistic assumption, it is remarkable that the revenue-maximizing
combinatorial auction remains unknown. In recent years, automated mechanism
design has emerged as one of the most practical and promising approaches to
designing high-revenue combinatorial auctions. The most scalable automated
mechanism design algorithms take as input samples from the bidders' valuation
distribution and then search for a high-revenue auction in a rich auction
class. In this work, we provide the first sample complexity analysis for the
standard hierarchy of deterministic combinatorial auction classes used in
automated mechanism design. In particular, we provide tight sample complexity
bounds on the number of samples needed to guarantee that the empirical revenue
of the designed mechanism on the samples is close to its expected revenue on
the underlying, unknown distribution over bidder valuations, for each of the
auction classes in the hierarchy. In addition to helping set automated
mechanism design on firm foundations, our results also push the boundaries of
learning theory. In particular, the hypothesis functions used in our contexts
are defined through multi-stage combinatorial optimization procedures, rather
than simple decision boundaries, as are common in machine learning.
Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
Authors: Jean Barbier, Mohamad Dia, Nicolas Macris, Florent Krzakala, Thibault Lesieur, Lenka Zdeborova
Date: 2016-06-13 00:00:00
Proceeding: NeurIPS 2016 12
Tasks: Community Detection

Factorizing low-rank matrices has many applications in machine learning and
statistics. For probabilistic models in the Bayes optimal setting, a general
expression for the mutual information has been proposed using heuristic
statistical physics computations, and proven in few specific cases. Here, we
show how to rigorously prove the conjectured formula for the symmetric rank-one
case. This allows to express the minimal mean-square-error and to characterize
the detectability phase transitions in a large set of estimation problems
ranging from community detection to sparse PCA. We also show that for a large
set of parameters, an iterative algorithm called approximate message-passing is
Bayes optimal. There exists, however, a gap between what currently known
polynomial algorithms can do and what is expected information theoretically.
Additionally, the proof technique has an interest of its own and exploits three
essential ingredients: the interpolation method introduced in statistical
physics by Guerra, the analysis of the approximate message-passing algorithm
and the theory of spatial coupling and threshold saturation in coding. Our
approach is generic and applicable to other open problems in statistical
estimation where heuristic statistical physics predictions are available.
De-biasing the Lasso: Optimal Sample Size for Gaussian Designs
Authors: Adel Javanmard, Andrea Montanari
Date: 2015-08-11 00:00:00

Performing statistical inference in high-dimension is an outstanding
challenge. A major source of difficulty is the absence of precise information
on the distribution of high-dimensional estimators. Here, we consider linear
regression in the high-dimensional regime $p\gg n$. In this context, we would
like to perform inference on a high-dimensional parameters vector
$\theta^*\in{\mathbb R}^p$. Important progress has been achieved in computing
confidence intervals for single coordinates $\theta^*_i$. A key role in these
new methods is played by a certain debiased estimator $\hat{\theta}^{\rm d}$
that is constructed from the Lasso. Earlier work establishes that, under
suitable assumptions on the design matrix, the coordinates of
$\hat{\theta}^{\rm d}$ are asymptotically Gaussian provided $\theta^*$ is
$s_0$-sparse with $s_0 = o(\sqrt{n}/\log p )$. The condition $s_0 = o(\sqrt{n}/
\log p )$ is stronger than the one for consistent estimation, namely $s_0 =
o(n/ \log p)$. We study Gaussian designs with known or unknown population
covariance. When the covariance is known, we prove that the debiased estimator
is asymptotically Gaussian under the nearly optimal condition $s_0 = o(n/ (\log
p)^2)$. Note that earlier work was limited to $s_0 = o(\sqrt{n}/\log p)$ even
for perfectly known covariance. The same conclusion holds if the population
covariance is unknown but can be estimated sufficiently well, e.g. under the
same sparsity conditions on the inverse covariance as assumed by earlier work.
For intermediate regimes, we describe the trade-off between sparsity in the
coefficients and in the inverse covariance of the design. We further discuss
several applications of our results to high-dimensional inference. In
particular, we propose a new estimator that is minimax optimal up to a factor
$1+o_n(1)$ for i.i.d. Gaussian designs.
Graph-Community Detection for Cross-Document Topic Segment Relationship Identification
Authors: Pedro Mota, Maxine Eskenazi, Luisa Coheur
Date: 2016-06-13 00:00:00
Tasks: Clustering, Community Detection

In this paper we propose a graph-community detection approach to identify
cross-document relationships at the topic segment level. Given a set of related
documents, we automatically find these relationships by clustering segments
with similar content (topics). In this context, we study how different
weighting mechanisms influence the discovery of word communities that relate to
the different topics found in the documents. Finally, we test different mapping
functions to assign topic segments to word communities, determining which topic
segments are considered equivalent.
  By performing this task it is possible to enable efficient multi-document
browsing, since when a user finds relevant content in one document we can
provide access to similar topics in other documents. We deploy our approach in
two different scenarios. One is an educational scenario where equivalence
relationships between learning materials need to be found. The other consists
of a series of dialogs in a social context where students discuss commonplace
topics. Results show that our proposed approach better discovered equivalence
relationships in learning material documents and obtained close results in the
social speech domain, where the best performing approach was a clustering
technique.
On the exact learnability of graph parameters: The case of partition functions
Authors: Nadia Labai, Johann A. Makowsky
Date: 2016-06-13 00:00:00

We study the exact learnability of real valued graph parameters $f$ which are
known to be representable as partition functions which count the number of
weighted homomorphisms into a graph $H$ with vertex weights $\alpha$ and edge
weights $\beta$. M. Freedman, L. Lov\'asz and A. Schrijver have given a
characterization of these graph parameters in terms of the $k$-connection
matrices $C(f,k)$ of $f$. Our model of learnability is based on D. Angluin's
model of exact learning using membership and equivalence queries. Given such a
graph parameter $f$, the learner can ask for the values of $f$ for graphs of
their choice, and they can formulate hypotheses in terms of the connection
matrices $C(f,k)$ of $f$. The teacher can accept the hypothesis as correct, or
provide a counterexample consisting of a graph. Our main result shows that in
this scenario, a very large class of partition functions, the rigid partition
functions, can be learned in time polynomial in the size of $H$ and the size of
the largest counterexample in the Blum-Shub-Smale model of computation over the
reals with unit cost.
A modified single and multi-objective bacteria foraging optimization for the solution of quadratic assignment problem
Authors: Saeid Parvandeh, Parya Soltani, Mohammadreza Boroumand, Fahimeh Boroumand
Date: 2016-06-13 00:00:00

Non-polynomial hard (NP-hard) problems are challenging because no polynomial-time algorithm has yet been discovered to solve them in polynomial time. The Bacteria Foraging Optimization (BFO) algorithm is one of the metaheuristics algorithms that is mostly used for NP-hard problems. BFO is inspired by the behavior of the bacteria foraging such as Escherichia coli (E-coli). The aim of BFO is to eliminate those bacteria that have weak foraging properties and maintain those bacteria that have breakthrough foraging properties toward the optimum. Despite the strength of this algorithm, most of the problems reaching optimal solutions are time-demanding or impossible. In this paper, we modified single objective BFO by adding a mutation operator and multi-objective BFO (MOBFO) by adding mutation and crossover from genetic algorithm operators to update the solutions in each generation, and local tabu search algorithm to reach the local optimum solution. Additionally, we used a fast nondominated sort algorithm in MOBFO to find the best-nondominated solutions in each generation. We evaluated the performance of the proposed algorithms through a number of single and multi-objective Quadratic Assignment Problem (QAP) instances. The experimental results show that our approaches outperform some previous optimization algorithms in both convergent and divergent solutions.
Online Optimization Methods for the Quantification Problem
Authors: Purushottam Kar, Shuai Li, Harikrishna Narasimhan, Sanjay Chawla, Fabrizio Sebastiani
Date: 2016-05-13 00:00:00
Tasks: Epidemiology, Sentiment Analysis

The estimation of class prevalence, i.e., the fraction of a population that
belongs to a certain class, is a very useful tool in data analytics and
learning, and finds applications in many domains such as sentiment analysis,
epidemiology, etc. For example, in sentiment analysis, the objective is often
not to estimate whether a specific text conveys a positive or a negative
sentiment, but rather estimate the overall distribution of positive and
negative sentiments during an event window. A popular way of performing the
above task, often dubbed quantification, is to use supervised learning to train
a prevalence estimator from labeled data.
  Contemporary literature cites several performance measures used to measure
the success of such prevalence estimators. In this paper we propose the first
online stochastic algorithms for directly optimizing these
quantification-specific performance measures. We also provide algorithms that
optimize hybrid performance measures that seek to balance quantification and
classification performance. Our algorithms present a significant advancement in
the theory of multivariate optimization and we show, by a rigorous theoretical
analysis, that they exhibit optimal convergence. We also report extensive
experiments on benchmark and real data sets which demonstrate that our methods
significantly outperform existing optimization techniques used for these
performance measures.
Multimodal Pivots for Image Caption Translation
Authors: Julian Hitschler, Shigehiko Schamoni, Stefan Riezler
Date: 2016-01-15 00:00:00
Proceeding: ACL 2016 8
Tasks: Image Retrieval, Machine Translation, Reranking, Retrieval, Translation

We present an approach to improve statistical machine translation of image
descriptions by multimodal pivots defined in visual space. The key idea is to
perform image retrieval over a database of images that are captioned in the
target language, and use the captions of the most similar images for
crosslingual reranking of translation outputs. Our approach does not depend on
the availability of large amounts of in-domain parallel data, but only relies
on available large datasets of monolingually captioned images, and on
state-of-the-art convolutional neural networks to compute image similarities.
Our experimental evaluation shows improvements of 1 BLEU point over strong
baselines.