pwc-archive/papers-with-abstracts huggingface dataset:
Message Passing and Combinatorial Optimization
Authors: Siamak Ravanbakhsh
Date: 2015-08-20 00:00:00
Tasks: Clustering, Combinatorial Optimization, Traveling Salesman Problem

Graphical models use the intuitive and well-studied methods of graph theory
to implicitly represent dependencies between variables in large systems. They
can model the global behaviour of a complex system by specifying only local
factors. This thesis studies inference in discrete graphical models from an
algebraic perspective and the ways inference can be used to express and
approximate NP-hard combinatorial problems.
  We investigate the complexity and reducibility of various inference problems,
in part by organizing them in an inference hierarchy. We then investigate
tractable approximations for a subset of these problems using distributive law
in the form of message passing. The quality of the resulting message passing
procedure, called Belief Propagation (BP), depends on the influence of loops in
the graphical model. We contribute to three classes of approximations that
improve BP for loopy graphs A) loop correction techniques; B) survey
propagation, another message passing technique that surpasses BP in some
settings; and C) hybrid methods that interpolate between deterministic message
passing and Markov Chain Monte Carlo inference.
  We then review the existing message passing solutions and provide novel
graphical models and inference techniques for combinatorial problems under
three broad classes: A) constraint satisfaction problems such as
satisfiability, coloring, packing, set / clique-cover and dominating /
independent set and their optimization counterparts; B) clustering problems
such as hierarchical clustering, K-median, K-clustering, K-center and
modularity optimization; C) problems over permutations including assignment,
graph morphisms and alignment, finding symmetries and traveling salesman
problem. In many cases we show that message passing is able to find solutions
that are either near optimal or favourably compare with today's
state-of-the-art approaches.
AdaDelay: Delay Adaptive Distributed Stochastic Convex Optimization
Authors: Suvrit Sra, Adams Wei Yu, Mu Li, Alexander J. Smola
Date: 2015-08-20 00:00:00

We study distributed stochastic convex optimization under the delayed
gradient model where the server nodes perform parameter updates, while the
worker nodes compute stochastic gradients. We discuss, analyze, and experiment
with a setup motivated by the behavior of real-world distributed computation
networks, where the machines are differently slow at different time. Therefore,
we allow the parameter updates to be sensitive to the actual delays
experienced, rather than to worst-case bounds on the maximum delay. This
sensitivity leads to larger stepsizes, that can help gain rapid initial
convergence without having to wait too long for slower machines, while
maintaining the same asymptotic complexity. We obtain encouraging improvements
to overall convergence for distributed experiments on real datasets with up to
billions of examples and features.
High-Contrast Color-Stripe Pattern for Rapid Structured-Light Range Imaging
Authors: Changsoo Je, Sang Wook Lee, Rae-Hong Park
Date: 2015-08-20 00:00:00
Tasks: Vocal Bursts Intensity Prediction

For structured-light range imaging, color stripes can be used for increasing
the number of distinguishable light patterns compared to binary BW stripes.
Therefore, an appropriate use of color patterns can reduce the number of light
projections and range imaging is achievable in single video frame or in "one
shot". On the other hand, the reliability and range resolution attainable from
color stripes is generally lower than those from multiply projected binary BW
patterns since color contrast is affected by object color reflectance and
ambient light. This paper presents new methods for selecting stripe colors and
designing multiple-stripe patterns for "one-shot" and "two-shot" imaging. We
show that maximizing color contrast between the stripes in one-shot imaging
reduces the ambiguities resulting from colored object surfaces and limitations
in sensor/projector resolution. Two-shot imaging adds an extra video frame and
maximizes the color contrast between the first and second video frames to
diminish the ambiguities even further. Experimental results demonstrate the
effectiveness of the presented one-shot and two-shot color-stripe imaging
schemes.
Introducing Geometry in Active Learning for Image Segmentation
Authors: Ksenia Konyushkova, Raphael Sznitman, Pascal Fua
Date: 2015-08-20 00:00:00
Proceeding: ICCV 2015 12
Tasks: Active Learning, Image Segmentation, Semantic Segmentation

We propose an Active Learning approach to training a segmentation classifier
that exploits geometric priors to streamline the annotation process in 3D image
volumes. To this end, we use these priors not only to select voxels most in
need of annotation but to guarantee that they lie on 2D planar patch, which
makes it much easier to annotate than if they were randomly distributed in the
volume. A simplified version of this approach is effective in natural 2D
images. We evaluated our approach on Electron Microscopy and Magnetic Resonance
image volumes, as well as on natural images. Comparing our approach against
several accepted baselines demonstrates a marked performance increase.
Duration and Interval Hidden Markov Model for Sequential Data Analysis
Authors: Hiromi Narimatsu, Hiroyuki Kasai
Date: 2015-08-20 00:00:00
Tasks: Retrieval, Time Series, Time Series Analysis

Analysis of sequential event data has been recognized as one of the essential
tools in data modeling and analysis field. In this paper, after the examination
of its technical requirements and issues to model complex but practical
situation, we propose a new sequential data model, dubbed Duration and Interval
Hidden Markov Model (DI-HMM), that efficiently represents "state duration" and
"state interval" of data events. This has significant implications to play an
important role in representing practical time-series sequential data. This
eventually provides an efficient and flexible sequential data retrieval.
Numerical experiments on synthetic and real data demonstrate the efficiency and
accuracy of the proposed DI-HMM.
The ABACOC Algorithm: a Novel Approach for Nonparametric Classification of Data Streams
Authors: Rocco De Rosa, Francesco Orabona, Nicolò Cesa-Bianchi
Date: 2015-08-20 00:00:00
Tasks: General Classification

Stream mining poses unique challenges to machine learning: predictive models
are required to be scalable, incrementally trainable, must remain bounded in
size (even when the data stream is arbitrarily long), and be nonparametric in
order to achieve high accuracy even in complex and dynamic environments.
Moreover, the learning system must be parameterless ---traditional tuning
methods are problematic in streaming settings--- and avoid requiring prior
knowledge of the number of distinct class labels occurring in the stream. In
this paper, we introduce a new algorithmic approach for nonparametric learning
in data streams. Our approach addresses all above mentioned challenges by
learning a model that covers the input space using simple local classifiers.
The distribution of these classifiers dynamically adapts to the local (unknown)
complexity of the classification problem, thus achieving a good balance between
model complexity and predictive accuracy. We design four variants of our
approach of increasing adaptivity. By means of an extensive empirical
evaluation against standard nonparametric baselines, we show state-of-the-art
results in terms of accuracy versus model size. For the variant that imposes a
strict bound on the model size, we show better performance against all other
methods measured at the same model size value. Our empirical analysis is
complemented by a theoretical performance guarantee which does not rely on any
stochastic assumption on the source generating the stream.
Histogram of gradients of Time-Frequency Representations for Audio scene detection
Authors: Alain Rakotomamonjy, Gilles Gasso
Date: 2015-08-20 00:00:00
Tasks: General Classification, Scene Classification

This paper addresses the problem of audio scenes classification and
contributes to the state of the art by proposing a novel feature. We build this
feature by considering histogram of gradients (HOG) of time-frequency
representation of an audio scene. Contrarily to classical audio features like
MFCC, we make the hypothesis that histogram of gradients are able to encode
some relevant informations in a time-frequency {representation:} namely, the
local direction of variation (in time and frequency) of the signal spectral
power. In addition, in order to gain more invariance and robustness, histogram
of gradients are locally pooled. We have evaluated the relevance of {the novel
feature} by comparing its performances with state-of-the-art competitors, on
several datasets, including a novel one that we provide, as part of our
contribution. This dataset, that we make publicly available, involves $19$
classes and contains about $900$ minutes of audio scene recording. We thus
believe that it may be the next standard dataset for evaluating audio scene
classification algorithms. Our comparison results clearly show that our
HOG-based features outperform its competitors
Semi-supervised Learning with Regularized Laplacian
Authors: Konstantin Avrachenkov, Pavel Chebotarev, Alexey Mishenin
Date: 2015-08-20 00:00:00
Tasks: General Classification

We study a semi-supervised learning method based on the similarity graph and
RegularizedLaplacian. We give convenient optimization formulation of the
Regularized Laplacian method and establishits various properties. In
particular, we show that the kernel of the methodcan be interpreted in terms of
discrete and continuous time random walks and possesses several
importantproperties of proximity measures. Both optimization and linear algebra
methods can be used for efficientcomputation of the classification functions.
We demonstrate on numerical examples that theRegularized Laplacian method is
competitive with respect to the other state of the art semi-supervisedlearning
methods.
Review and Perspective for Distance Based Trajectory Clustering
Authors: Philippe Besse, Brendan Guillouet, Jean-Michel Loubes, Royer François
Date: 2015-08-20 00:00:00
Tasks: Clustering, Trajectory Clustering

In this paper we tackle the issue of clustering trajectories of geolocalized
observations. Using clustering technics based on the choice of a distance
between the observations, we first provide a comprehensive review of the
different distances used in the literature to compare trajectories. Then based
on the limitations of these methods, we introduce a new distance : Symmetrized
Segment-Path Distance (SSPD). We finally compare this new distance to the
others according to their corresponding clustering results obtained using both
hierarchical clustering and affinity propagation methods.
Sequence-to-Sequence Neural Net Models for Grapheme-to-Phoneme Conversion
Authors: Kaisheng Yao, Geoffrey Zweig
Date: 2015-05-31 00:00:00
Tasks: Grapheme-to-Phoneme Conversion, Image Captioning, Language Modeling, Language Modelling, Machine Translation, Translation

Sequence-to-sequence translation methods based on generation with a
side-conditioned language model have recently shown promising results in
several tasks. In machine translation, models conditioned on source side words
have been used to produce target-language text, and in image captioning, models
conditioned images have been used to generate caption text. Past work with this
approach has focused on large vocabulary tasks, and measured quality in terms
of BLEU. In this paper, we explore the applicability of such models to the
qualitatively different grapheme-to-phoneme task. Here, the input and output
side vocabularies are small, plain n-gram models do well, and credit is only
given when the output is exactly correct. We find that the simple
side-conditioned generation approach is able to rival the state-of-the-art, and
we are able to significantly advance the stat-of-the-art with bi-directional
long short-term memory (LSTM) neural networks that use the same alignment
information that is used in conventional approaches.
Multi-criteria Similarity-based Anomaly Detection using Pareto Depth Analysis
Authors: Ko-Jen Hsiao, Kevin S. Xu, Jeff Calder, Alfred O. Hero III
Date: 2015-08-20 00:00:00
Tasks: Anomaly Detection

We consider the problem of identifying patterns in a data set that exhibit
anomalous behavior, often referred to as anomaly detection. Similarity-based
anomaly detection algorithms detect abnormally large amounts of similarity or
dissimilarity, e.g.~as measured by nearest neighbor Euclidean distances between
a test sample and the training samples. In many application domains there may
not exist a single dissimilarity measure that captures all possible anomalous
patterns. In such cases, multiple dissimilarity measures can be defined,
including non-metric measures, and one can test for anomalies by scalarizing
using a non-negative linear combination of them. If the relative importance of
the different dissimilarity measures are not known in advance, as in many
anomaly detection applications, the anomaly detection algorithm may need to be
executed multiple times with different choices of weights in the linear
combination. In this paper, we propose a method for similarity-based anomaly
detection using a novel multi-criteria dissimilarity measure, the Pareto depth.
The proposed Pareto depth analysis (PDA) anomaly detection algorithm uses the
concept of Pareto optimality to detect anomalies under multiple criteria
without having to run an algorithm multiple times with different choices of
weights. The proposed PDA approach is provably better than using linear
combinations of the criteria and shows superior performance on experiments with
synthetic and real data sets.
Efficient Computation of Exact IRV Margins
Authors: Michelle Blom, Peter J. Stuckey, Vanessa J. Teague, Ron Tidhar
Date: 2015-08-20 00:00:00

The margin of victory is easy to compute for many election schemes but
difficult for Instant Runoff Voting (IRV). This is important because arguments
about the correctness of an election outcome usually rely on the size of the
electoral margin. For example, risk-limiting audits require a knowledge of the
margin of victory in order to determine how much auditing is necessary. This
paper presents a practical branch-and-bound algorithm for exact IRV margin
computation that substantially improves on the current best-known approach.
Although exponential in the worst case, our algorithm runs efficiently in
practice on all the real examples we could find. We can efficiently discover
exact margins on election instances that cannot be solved by the current
state-of-the-art.
Warehouse Layout Method Based on Ant Colony and Backtracking Algorithm
Authors: Ardy Wibowo Haryanto, Adhi Kusnadi, Yustinus Eko Soelistio
Date: 2015-08-20 00:00:00
Tasks: Management

Warehouse is one of the important aspects of a company. Therefore, it is
necessary to improve Warehouse Management System (WMS) to have a simple
function that can determine the layout of the storage goods. In this paper we
propose an improved warehouse layout method based on ant colony algorithm and
backtracking algorithm. The method works on two steps. First, it generates a
solutions parameter tree from backtracking algorithm. Then second, it deducts
the solutions parameter by using a combination of ant colony algorithm and
backtracking algorithm. This method was tested by measuring the time needed to
build the tree and to fill up the space using two scenarios. The method needs
0.294 to 33.15 seconds to construct the tree and 3.23 seconds (best case) to
61.41 minutes (worst case) to fill up the warehouse. This method is proved to
be an attractive alternative solution for warehouse layout system.
Recursive Training of 2D-3D Convolutional Networks for Neuronal Boundary Detection
Authors: Kisuk Lee, Aleksandar Zlateski, Ashwin Vishwanathan, H. Sebastian Seung
Date: 2015-08-20 00:00:00
Proceeding: NeurIPS 2015
Tasks: 3D Architecture, Boundary Detection, CPU

Efforts to automate the reconstruction of neural circuits from 3D electron
microscopic (EM) brain images are critical for the field of connectomics. An
important computation for reconstruction is the detection of neuronal
boundaries. Images acquired by serial section EM, a leading 3D EM technique,
are highly anisotropic, with inferior quality along the third dimension. For
such images, the 2D max-pooling convolutional network has set the standard for
performance at boundary detection. Here we achieve a substantial gain in
accuracy through three innovations. Following the trend towards deeper networks
for object recognition, we use a much deeper network than previously employed
for boundary detection. Second, we incorporate 3D as well as 2D filters, to
enable computations that use 3D context. Finally, we adopt a recursively
trained architecture in which a first network generates a preliminary boundary
map that is provided as input along with the original image to a second network
that generates a final boundary map. Backpropagation training is accelerated by
ZNN, a new implementation of 3D convolutional networks that uses multicore CPU
parallelism for speed. Our hybrid 2D-3D architecture could be more generally
applicable to other types of anisotropic 3D images, including video, and our
recursive framework for any image labeling problem.
Listen, Attend and Spell
Authors: William Chan, Navdeep Jaitly, Quoc V. Le, Oriol Vinyals
Date: 2015-08-05 00:00:00
Tasks: Decoder, Language Modeling, Language Modelling, Reading Comprehension, Speech Recognition

We present Listen, Attend and Spell (LAS), a neural network that learns to
transcribe speech utterances to characters. Unlike traditional DNN-HMM models,
this model learns all the components of a speech recognizer jointly. Our system
has two components: a listener and a speller. The listener is a pyramidal
recurrent network encoder that accepts filter bank spectra as inputs. The
speller is an attention-based recurrent network decoder that emits characters
as outputs. The network produces character sequences without making any
independence assumptions between the characters. This is the key improvement of
LAS over previous end-to-end CTC models. On a subset of the Google voice search
task, LAS achieves a word error rate (WER) of 14.1% without a dictionary or a
language model, and 10.3% with language model rescoring over the top 32 beams.
By comparison, the state-of-the-art CLDNN-HMM model achieves a WER of 8.0%.
Who are the Devils Wearing Prada in New York City?
Authors: Kuan-Ting Chen, Kezhen Chen, Peizhong Cong, Winston H. Hsu, Jiebo Luo
Date: 2015-08-19 00:00:00

Fashion is a perpetual topic in human social life, and the mass has the
penchant to emulate what large city residents and celebrities wear. Undeniably,
New York City is such a bellwether large city with all kinds of fashion
leadership. Consequently, to study what the fashion trends are during this
year, it is very helpful to learn the fashion trends of New York City.
Discovering fashion trends in New York City could boost many applications such
as clothing recommendation and advertising. Does the fashion trend in the New
York Fashion Show actually influence the clothing styles on the public? To
answer this question, we design a novel system that consists of three major
components: (1) constructing a large dataset from the New York Fashion Shows
and New York street chic in order to understand the likely clothing fashion
trends in New York, (2) utilizing a learning-based approach to discover fashion
attributes as the representative characteristics of fashion trends, and (3)
comparing the analysis results from the New York Fashion Shows and street-chic
images to verify whether the fashion shows have actual influence on the people
in New York City. Through the preliminary experiments over a large clothing
dataset, we demonstrate the effectiveness of our proposed system, and obtain
useful insights on fashion trends and fashion influence.
Time Series Clustering via Community Detection in Networks
Authors: Leonardo N. Ferreira, Liang Zhao
Date: 2015-08-19 00:00:00
Tasks: Clustering, Community Detection, Time Series, Time Series Analysis, Time Series Clustering

In this paper, we propose a technique for time series clustering using
community detection in complex networks. Firstly, we present a method to
transform a set of time series into a network using different distance
functions, where each time series is represented by a vertex and the most
similar ones are connected. Then, we apply community detection algorithms to
identify groups of strongly connected vertices (called a community) and,
consequently, identify time series clusters. Still in this paper, we make a
comprehensive analysis on the influence of various combinations of time series
distance functions, network generation methods and community detection
techniques on clustering results. Experimental study shows that the proposed
network-based approach achieves better results than various classic or
up-to-date clustering techniques under consideration. Statistical tests confirm
that the proposed method outperforms some classic clustering algorithms, such
as $k$-medoids, diana, median-linkage and centroid-linkage in various data
sets. Interestingly, the proposed method can effectively detect shape patterns
presented in time series due to the topological structure of the underlying
network constructed in the clustering process. At the same time, other
techniques fail to identify such patterns. Moreover, the proposed method is
robust enough to group time series presenting similar pattern but with time
shifts and/or amplitude variations. In summary, the main point of the proposed
method is the transformation of time series from time-space domain to
topological domain. Therefore, we hope that our approach contributes not only
for time series clustering, but also for general time series analysis tasks.
New Limits for Knowledge Compilation and Applications to Exact Model Counting
Authors: Paul Beame, Vincent Liew
Date: 2015-06-08 00:00:00

We show new limits on the efficiency of using current techniques to make
exact probabilistic inference for large classes of natural problems. In
particular we show new lower bounds on knowledge compilation to SDD and DNNF
forms. We give strong lower bounds on the complexity of SDD representations by
relating SDD size to best-partition communication complexity. We use this
relationship to prove exponential lower bounds on the SDD size for representing
a large class of problems that occur naturally as queries over probabilistic
databases. A consequence is that for representing unions of conjunctive
queries, SDDs are not qualitatively more concise than OBDDs. We also derive
simple examples for which SDDs must be exponentially less concise than FBDDs.
Finally, we derive exponential lower bounds on the sizes of DNNF
representations using a new quasipolynomial simulation of DNNFs by
nondeterministic FBDDs.