pwc-archive/papers-with-abstracts huggingface dataset:
An Efficient Algorithm for Mining Frequent Sequence with Constraint Programming
Authors: John O. R. Aoga, Tias Guns, Pierre Schaus
Date: 2016-04-05 00:00:00
Tasks: Sequential Pattern Mining

The main advantage of Constraint Programming (CP) approaches for sequential
pattern mining (SPM) is their modularity, which includes the ability to add new
constraints (regular expressions, length restrictions, etc). The current best
CP approach for SPM uses a global constraint (module) that computes the
projected database and enforces the minimum frequency; it does this with a
filtering algorithm similar to the PrefixSpan method. However, the resulting
system is not as scalable as some of the most advanced mining systems like
Zaki's cSPADE. We show how, using techniques from both data mining and CP, one
can use a generic constraint solver and yet outperform existing specialized
systems. This is mainly due to two improvements in the module that computes the
projected frequencies: first, computing the projected database can be sped up
by pre-computing the positions at which an symbol can become unsupported by a
sequence, thereby avoiding to scan the full sequence each time; and second by
taking inspiration from the trailing used in CP solvers to devise a
backtracking-aware data structure that allows fast incremental storing and
restoring of the projected database. Detailed experiments show how this
approach outperforms existing CP as well as specialized systems for SPM, and
that the gain in efficiency translates directly into increased efficiency for
other settings such as mining with regular expressions.
Fast Metric Learning For Deep Neural Networks
Authors: Henry Gouk, Bernhard Pfahringer, Michael Cree
Date: 2015-11-19 00:00:00
Tasks: General Classification, Information Retrieval, Metric Learning, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION, Retrieval

Similarity metrics are a core component of many information retrieval and
machine learning systems. In this work we propose a method capable of learning
a similarity metric from data equipped with a binary relation. By considering
only the similarity constraints, and initially ignoring the features, we are
able to learn target vectors for each instance using one of several
appropriately designed loss functions. A regression model can then be
constructed that maps novel feature vectors to the same target vector space,
resulting in a feature extractor that computes vectors for which a predefined
metric is a meaningful measure of similarity. We present results on both
multiclass and multi-label classification datasets that demonstrate
considerably faster convergence, as well as higher accuracy on the majority of
the intrinsic evaluation tasks and all extrinsic evaluation tasks.
Staleness-aware Async-SGD for Distributed Deep Learning
Authors: Wei Zhang, Suyog Gupta, Xiangru Lian, Ji Liu
Date: 2015-11-18 00:00:00
Tasks: Deep Learning, Distributed Computing, image-classification, Image Classification

Deep neural networks have been shown to achieve state-of-the-art performance
in several machine learning tasks. Stochastic Gradient Descent (SGD) is the
preferred optimization algorithm for training these networks and asynchronous
SGD (ASGD) has been widely adopted for accelerating the training of large-scale
deep networks in a distributed computing environment. However, in practice it
is quite challenging to tune the training hyperparameters (such as learning
rate) when using ASGD so as achieve convergence and linear speedup, since the
stability of the optimization algorithm is strongly influenced by the
asynchronous nature of parameter updates. In this paper, we propose a variant
of the ASGD algorithm in which the learning rate is modulated according to the
gradient staleness and provide theoretical guarantees for convergence of this
algorithm. Experimental verification is performed on commonly-used image
classification benchmarks: CIFAR10 and Imagenet to demonstrate the superior
effectiveness of the proposed approach, compared to SSGD (Synchronous SGD) and
the conventional ASGD algorithm.
Less is more: zero-shot learning from online textual documents with noise suppression
Authors: Ruizhi Qiao, Lingqiao Liu, Chunhua Shen, Anton Van Den Hengel
Date: 2016-04-05 00:00:00
Proceeding: CVPR 2016 6
Tasks: Zero-Shot Learning

Classifying a visual concept merely from its associated online textual
source, such as a Wikipedia article, is an attractive research topic in
zero-shot learning because it alleviates the burden of manually collecting
semantic attributes. Several recent works have pursued this approach by
exploring various ways of connecting the visual and text domains. This paper
revisits this idea by stepping further to consider one important factor: the
textual representation is usually too noisy for the zero-shot learning
application. This consideration motivates us to design a simple-but-effective
zero-shot learning method capable of suppressing noise in the text.
  More specifically, we propose an $l_{2,1}$-norm based objective function
which can simultaneously suppress the noisy signal in the text and learn a
function to match the text document and visual features. We also develop an
optimization algorithm to efficiently solve the resulting problem. By
conducting experiments on two large datasets, we demonstrate that the proposed
method significantly outperforms the competing methods which rely on online
information sources but without explicit noise suppression. We further make an
in-depth analysis of the proposed method and provide insight as to what kind of
information in documents is useful for zero-shot learning.
Visualizing Large-scale and High-dimensional Data
Authors: Jian Tang, Jingzhou Liu, Ming Zhang, Qiaozhu Mei
Date: 2016-02-01 00:00:00
Tasks: graph construction, Vocal Bursts Intensity Prediction

We study the problem of visualizing large-scale and high-dimensional data in
a low-dimensional (typically 2D or 3D) space. Much success has been reported
recently by techniques that first compute a similarity structure of the data
points and then project them into a low-dimensional space with the structure
preserved. These two steps suffer from considerable computational costs,
preventing the state-of-the-art methods such as the t-SNE from scaling to
large-scale and high-dimensional data (e.g., millions of data points and
hundreds of dimensions). We propose the LargeVis, a technique that first
constructs an accurately approximated K-nearest neighbor graph from the data
and then layouts the graph in the low-dimensional space. Comparing to t-SNE,
LargeVis significantly reduces the computational cost of the graph construction
step and employs a principled probabilistic model for the visualization step,
the objective of which can be effectively optimized through asynchronous
stochastic gradient descent with a linear time complexity. The whole procedure
thus easily scales to millions of high-dimensional data points. Experimental
results on real-world data sets demonstrate that the LargeVis outperforms the
state-of-the-art methods in both efficiency and effectiveness. The
hyper-parameters of LargeVis are also much more stable over different data
sets.
Partial Membership Latent Dirichlet Allocation
Authors: Chao Chen, Alina Zare, J. Tory Cobb
Date: 2015-11-09 00:00:00
Tasks: parameter estimation, Sand, Topic Models

Topic models (e.g., pLSA, LDA, SLDA) have been widely used for segmenting
imagery. These models are confined to crisp segmentation. Yet, there are many
images in which some regions cannot be assigned a crisp label (e.g., transition
regions between a foggy sky and the ground or between sand and water at a
beach). In these cases, a visual word is best represented with partial
memberships across multiple topics. To address this, we present a partial
membership latent Dirichlet allocation (PM-LDA) model and associated parameter
estimation algorithms. Experimental results on two natural image datasets and
one SONAR image dataset show that PM-LDA can produce both crisp and soft
semantic image segmentations; a capability existing methods do not have.
Science Question Answering using Instructional Materials
Authors: Mrinmaya Sachan, Avinava Dubey, Eric P. Xing
Date: 2016-02-13 00:00:00
Proceeding: ACL 2016 8
Tasks: Question Answering, Science Question Answering

We provide a solution for elementary science test using instructional
materials. We posit that there is a hidden structure that explains the
correctness of an answer given the question and instructional materials and
present a unified max-margin framework that learns to find these hidden
structures (given a corpus of question-answer pairs and instructional
materials), and uses what it learns to answer novel elementary science
questions. Our evaluation shows that our framework outperforms several strong
baselines.
Relative Deviation Learning Bounds and Generalization with Unbounded Loss Functions
Authors: Corinna Cortes, Spencer Greenberg, Mehryar Mohri
Date: 2013-10-22 00:00:00
Tasks: Generalization Bounds, regression

We present an extensive analysis of relative deviation bounds, including
detailed proofs of two-sided inequalities and their implications. We also give
detailed proofs of two-sided generalization bounds that hold in the general
case of unbounded loss functions, under the assumption that a moment of the
loss is bounded. These bounds are useful in the analysis of importance
weighting and other learning tasks such as unbounded regression.
Stochastic Variance Reduction for Nonconvex Optimization
Authors: Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, Alex Smola
Date: 2016-03-19 00:00:00

We study nonconvex finite-sum problems and analyze stochastic variance
reduced gradient (SVRG) methods for them. SVRG and related methods have
recently surged into prominence for convex optimization given their edge over
stochastic gradient descent (SGD); but their theoretical analysis almost
exclusively assumes convexity. In contrast, we prove non-asymptotic rates of
convergence (to stationary points) of SVRG for nonconvex optimization, and show
that it is provably faster than SGD and gradient descent. We also analyze a
subclass of nonconvex problems on which SVRG attains linear convergence to the
global optimum. We extend our analysis to mini-batch variants of SVRG, showing
(theoretical) linear speedup due to mini-batching in parallel settings.
A Dynamic Bayesian Network Model for Inventory Level Estimation in Retail Marketing
Authors: Luis I. Reyes-Castro, Andres G. Abad
Date: 2016-04-04 00:00:00
Tasks: Management, Marketing

Many retailers today employ inventory management systems based on Re-Order
Point Policies, most of which rely on the assumption that all decreases in
product inventory levels result from product sales. Unfortunately, it usually
happens that small but random quantities of the product get lost, stolen or
broken without record as time passes, e.g., as a consequence of shoplifting.
This is usual for retailers handling large varieties of inexpensive products,
e.g., grocery stores. In turn, over time these discrepancies lead to stock
freezing problems, i.e., situations where the system believes the stock is
above the re-order point but the actual stock is at zero, and so no
replenishments or sales occur. Motivated by these issues, we model the
interaction between sales, losses, replenishments and inventory levels as a
Dynamic Bayesian Network (DBN), where the inventory levels are unobserved
(i.e., hidden) variables we wish to estimate. We present an
Expectation-Maximization (EM) algorithm to estimate the parameters of the sale
and loss distributions, which relies on solving a one-dimensional dynamic
program for the E-step and on solving two separate one-dimensional nonlinear
programs for the M-step.
Direct Visual Odometry using Bit-Planes
Authors: Hatem Alismail, Brett Browning, Simon Lucey
Date: 2016-04-04 00:00:00
Tasks: Visual Odometry

Feature descriptors, such as SIFT and ORB, are well-known for their
robustness to illumination changes, which has made them popular for
feature-based VSLAM\@. However, in degraded imaging conditions such as low
light, low texture, blur and specular reflections, feature extraction is often
unreliable. In contrast, direct VSLAM methods which estimate the camera pose by
minimizing the photometric error using raw pixel intensities are often more
robust to low textured environments and blur. Nonetheless, at the core of
direct VSLAM is the reliance on a consistent photometric appearance across
images, otherwise known as the brightness constancy assumption. Unfortunately,
brightness constancy seldom holds in real world applications.
  In this work, we overcome brightness constancy by incorporating feature
descriptors into a direct visual odometry framework. This combination results
in an efficient algorithm that combines the strength of both feature-based
algorithms and direct methods. Namely, we achieve robustness to arbitrary
photometric variations while operating in low-textured and poorly lit
environments. Our approach utilizes an efficient binary descriptor, which we
call Bit-Planes, and show how it can be used in the gradient-based optimization
required by direct methods. Moreover, we show that the squared Euclidean
distance between Bit-Planes is equivalent to the Hamming distance. Hence, the
descriptor may be used in least squares optimization without sacrificing its
photometric invariance. Finally, we present empirical results that demonstrate
the robustness of the approach in poorly lit underground environments.
Clustering Millions of Faces by Identity
Authors: Charles Otto, Dayong Wang, Anil K. Jain
Date: 2016-04-04 00:00:00
Tasks: Clustering

In this work, we attempt to address the following problem: Given a large
number of unlabeled face images, cluster them into the individual identities
present in this data. We consider this a relevant problem in different
application scenarios ranging from social media to law enforcement. In
large-scale scenarios the number of faces in the collection can be of the order
of hundreds of million, while the number of clusters can range from a few
thousand to millions--leading to difficulties in terms of both run-time
complexity and evaluating clustering and per-cluster quality. An efficient and
effective Rank-Order clustering algorithm is developed to achieve the desired
scalability, and better clustering accuracy than other well-known algorithms
such as k-means and spectral clustering. We cluster up to 123 million face
images into over 10 million clusters, and analyze the results in terms of both
external cluster quality measures (known face labels) and internal cluster
quality measures (unknown face labels) and run-time. Our algorithm achieves an
F-measure of 0.87 on a benchmark unconstrained face dataset (LFW, consisting of
13K faces), and 0.27 on the largest dataset considered (13K images in LFW, plus
123M distractor images). Additionally, we present preliminary work on video
frame clustering (achieving 0.71 F-measure when clustering all frames in the
benchmark YouTube Faces dataset). A per-cluster quality measure is developed
which can be used to rank individual clusters and to automatically identify a
subset of good quality clusters for manual exploration.
Writer-independent Feature Learning for Offline Signature Verification using Deep Convolutional Neural Networks
Authors: Luiz G. Hafemann, Robert Sabourin, Luiz S. Oliveira
Date: 2016-04-04 00:00:00

Automatic Offline Handwritten Signature Verification has been researched over
the last few decades from several perspectives, using insights from graphology,
computer vision, signal processing, among others. In spite of the advancements
on the field, building classifiers that can separate between genuine signatures
and skilled forgeries (forgeries made targeting a particular signature) is
still hard. We propose approaching the problem from a feature learning
perspective. Our hypothesis is that, in the absence of a good model of the data
generation process, it is better to learn the features from data, instead of
using hand-crafted features that have no resemblance to the signature
generation process. To this end, we use Deep Convolutional Neural Networks to
learn features in a writer-independent format, and use this model to obtain a
feature representation on another set of users, where we train writer-dependent
classifiers. We tested our method in two datasets: GPDS-960 and Brazilian
PUC-PR. Our experimental results show that the features learned in a subset of
the users are discriminative for the other users, including across different
datasets, reaching close to the state-of-the-art in the GPDS dataset, and
improving the state-of-the-art in the Brazilian PUC-PR dataset.
Part-of-Speech Tagging for Historical English
Authors: Yi Yang, Jacob Eisenstein
Date: 2016-03-10 00:00:00
Proceeding: NAACL 2016 6
Tasks: Domain Adaptation, Part-Of-Speech Tagging, Unsupervised Domain Adaptation, Word Embeddings

As more historical texts are digitized, there is interest in applying natural
language processing tools to these archives. However, the performance of these
tools is often unsatisfactory, due to language change and genre differences.
Spelling normalization heuristics are the dominant solution for dealing with
historical texts, but this approach fails to account for changes in usage and
vocabulary. In this empirical paper, we assess the capability of domain
adaptation techniques to cope with historical texts, focusing on the classic
benchmark task of part-of-speech tagging. We evaluate several domain adaptation
methods on the task of tagging Early Modern English and Modern British English
texts in the Penn Corpora of Historical English. We demonstrate that the
Feature Embedding method for unsupervised domain adaptation outperforms word
embeddings and Brown clusters, showing the importance of embedding the entire
feature space, rather than just individual words. Feature Embeddings also give
better performance than spelling normalization, but the combination of the two
methods is better still, yielding a 5% raw improvement in tagging accuracy on
Early Modern English texts.
Partial Recovery Bounds for the Sparse Stochastic Block Model
Authors: Jonathan Scarlett, Volkan Cevher
Date: 2016-02-02 00:00:00
Tasks: Community Detection, Stochastic Block Model

In this paper, we study the information-theoretic limits of community
detection in the symmetric two-community stochastic block model, with
intra-community and inter-community edge probabilities $\frac{a}{n}$ and
$\frac{b}{n}$ respectively. We consider the sparse setting, in which $a$ and
$b$ do not scale with $n$, and provide upper and lower bounds on the proportion
of community labels recovered on average. We provide a numerical example for
which the bounds are near-matching for moderate values of $a - b$, and matching
in the limit as $a-b$ grows large.
Multi-Field Structural Decomposition for Question Answering
Authors: Tomasz Jurczyk, Jinho D. Choi
Date: 2016-04-04 00:00:00
Tasks: Question Answering

This paper presents a precursory yet novel approach to the question answering
task using structural decomposition. Our system first generates linguistic
structures such as syntactic and semantic trees from text, decomposes them into
multiple fields, then indexes the terms in each field. For each question, it
decomposes the question into multiple fields, measures the relevance score of
each field to the indexed ones, then ranks all documents by their relevance
scores and weights associated with the fields, where the weights are learned
through statistical modeling. Our final model gives an absolute improvement of
over 40% to the baseline approach using simple search for detecting documents
containing answers.
Entity Type Recognition using an Ensemble of Distributional Semantic Models to Enhance Query Understanding
Authors: Walid Shalaby, Khalifeh Al Jadda, Mohammed Korayem, Trey Grainger
Date: 2016-04-04 00:00:00
Tasks: Information Retrieval, Retrieval, World Knowledge

We present an ensemble approach for categorizing search query entities in the
recruitment domain. Understanding the types of entities expressed in a search
query (Company, Skill, Job Title, etc.) enables more intelligent information
retrieval based upon those entities compared to a traditional keyword-based
search. Because search queries are typically very short, leveraging a
traditional bag-of-words model to identify entity types would be inappropriate
due to the lack of contextual information. Our approach instead combines clues
from different sources of varying complexity in order to collect real-world
knowledge about query entities. We employ distributional semantic
representations of query entities through two models: 1) contextual vectors
generated from encyclopedic corpora like Wikipedia, and 2) high dimensional
word embedding vectors generated from millions of job postings using word2vec.
Additionally, our approach utilizes both entity linguistic properties obtained
from WordNet and ontological properties extracted from DBpedia. We evaluate our
approach on a data set created at CareerBuilder; the largest job board in the
US. The data set contains entities extracted from millions of job
seekers/recruiters search queries, job postings, and resume documents. After
constructing the distributional vectors of search entities, we use supervised
machine learning to infer search entity types. Empirical results show that our
approach outperforms the state-of-the-art word2vec distributional semantics
model trained on Wikipedia. Moreover, we achieve micro-averaged F 1 score of
97% using the proposed distributional representations ensemble.
Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning
Authors: Philip S. Thomas, Emma Brunskill
Date: 2016-04-04 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

In this paper we present a new way of predicting the performance of a
reinforcement learning policy given historical data that may have been
generated by a different policy. The ability to evaluate a policy from
historical data is important for applications where the deployment of a bad
policy can be dangerous or costly. We show empirically that our algorithm
produces estimates that often have orders of magnitude lower mean squared error
than existing methods---it makes more efficient use of the available data. Our
new estimator is based on two advances: an extension of the doubly robust
estimator (Jiang and Li, 2015), and a new way to mix between model based
estimates and importance sampling based estimates.
Detecting Engagement in Egocentric Video
Authors: Yu-Chuan Su, Kristen Grauman
Date: 2016-04-04 00:00:00
Tasks: Video Summarization

In a wearable camera video, we see what the camera wearer sees. While this
makes it easy to know roughly what he chose to look at, it does not immediately
reveal when he was engaged with the environment. Specifically, at what moments
did his focus linger, as he paused to gather more information about something
he saw? Knowing this answer would benefit various applications in video
summarization and augmented reality, yet prior work focuses solely on the
"what" question (estimating saliency, gaze) without considering the "when"
(engagement). We propose a learning-based approach that uses long-term
egomotion cues to detect engagement, specifically in browsing scenarios where
one frequently takes in new visual information (e.g., shopping, touring). We
introduce a large, richly annotated dataset for ego-engagement that is the
first of its kind. Our approach outperforms a wide array of existing methods.
We show engagement can be detected well independent of both scene appearance
and the camera wearer's identity.