pwc-archive/papers-with-abstracts huggingface dataset:
Interleaved Text/Image Deep Mining on a Large-Scale Radiology Database for Automated Image Interpretation
Authors: Hoo-chang Shin, Le Lu, Lauren Kim, Ari Seff, Jianhua Yao, Ronald M. Summers
Date: 2015-05-04 00:00:00
Tasks: Diagnostic, Sentence

Despite tremendous progress in computer vision, there has not been an attempt
for machine learning on very large-scale medical image databases. We present an
interleaved text/image deep learning system to extract and mine the semantic
interactions of radiology images and reports from a national research
hospital's Picture Archiving and Communication System. With natural language
processing, we mine a collection of representative ~216K two-dimensional key
images selected by clinicians for diagnostic reference, and match the images
with their descriptions in an automated manner. Our system interleaves between
unsupervised learning and supervised learning on document- and sentence-level
text collections, to generate semantic labels and to predict them given an
image. Given an image of a patient scan, semantic topics in radiology levels
are predicted, and associated key-words are generated. Also, a number of
frequent disease types are detected as present or absent, to provide more
specific interpretation of a patient scan. This shows the potential of
large-scale learning and prediction in electronic patient records available in
most modern clinical institutions.
Model Selection and Overfitting in Genetic Programming: Empirical Study [Extended Version]
Authors: Jan Žegklitz, Petr Pošík
Date: 2015-04-30 00:00:00
Tasks: Model Selection

Genetic Programming has been very successful in solving a large area of
problems but its use as a machine learning algorithm has been limited so far.
One of the reasons is the problem of overfitting which cannot be solved or
suppresed as easily as in more traditional approaches. Another problem, closely
related to overfitting, is the selection of the final model from the
population.
  In this article we present our research that addresses both problems:
overfitting and model selection. We compare several ways of dealing with
ovefitting, based on Random Sampling Technique (RST) and on using a validation
set, all with an emphasis on model selection. We subject each approach to a
thorough testing on artificial and real--world datasets and compare them with
the standard approach, which uses the full training data, as a baseline.
Activity recognition from videos with parallel hypergraph matching on GPUs
Authors: Eric Lombardi, Christian Wolf, Oya Celiktutan, Bülent Sankur
Date: 2015-05-04 00:00:00
Tasks: Activity Recognition, GPU, Graph Matching, Hypergraph Matching, set matching

In this paper, we propose a method for activity recognition from videos based
on sparse local features and hypergraph matching. We benefit from special
properties of the temporal domain in the data to derive a sequential and fast
graph matching algorithm for GPUs.
  Traditionally, graphs and hypergraphs are frequently used to recognize
complex and often non-rigid patterns in computer vision, either through graph
matching or point-set matching with graphs. Most formulations resort to the
minimization of a difficult discrete energy function mixing geometric or
structural terms with data attached terms involving appearance features.
Traditional methods solve this minimization problem approximately, for instance
with spectral techniques.
  In this work, instead of solving the problem approximatively, the exact
solution for the optimal assignment is calculated in parallel on GPUs. The
graphical structure is simplified and regularized, which allows to derive an
efficient recursive minimization algorithm. The algorithm distributes
subproblems over the calculation units of a GPU, which solves them in parallel,
allowing the system to run faster than real-time on medium-end GPUs.
Higher Order Maximum Persistency and Comparison Theorems
Authors: Alexander Shekhovtsov
Date: 2015-05-04 00:00:00

We address combinatorial problems that can be formulated as minimization of a
partially separable function of discrete variables (energy minimization in
graphical models, weighted constraint satisfaction, pseudo-Boolean
optimization, 0-1 polynomial programming). For polyhedral relaxations of such
problems it is generally not true that variables integer in the relaxed
solution will retain the same values in the optimal discrete solution. Those
which do are called persistent. Such persistent variables define a part of a
globally optimal solution. Once identified, they can be excluded from the
problem, reducing its size.
  To any polyhedral relaxation we associate a sufficient condition proving
persistency of a subset of variables. We set up a specially constructed linear
program which determines the set of persistent variables maximal with respect
to the relaxation. The condition improves as the relaxation is tightened and
possesses all its invariances. The proposed framework explains a variety of
existing methods originating from different areas of research and based on
different principles. A theoretical comparison is established that relates
these methods to the standard linear relaxation and proves that the proposed
technique identifies same or larger set of persistent variables.
Estimating the Margin of Victory of an Election using Sampling
Authors: Palash Dey, Y. Narahari
Date: 2015-05-04 00:00:00

The margin of victory of an election is a useful measure to capture the
robustness of an election outcome. It also plays a crucial role in determining
the sample size of various algorithms in post election audit, polling etc. In
this work, we present efficient sampling based algorithms for estimating the
margin of victory of elections.
  More formally, we introduce the \textsc{$(c, \epsilon, \delta)$--Margin of
Victory} problem, where given an election $\mathcal{E}$ on $n$ voters, the goal
is to estimate the margin of victory $M(\mathcal{E})$ of $\mathcal{E}$ within
an additive factor of $c MoV(\mathcal{E})+\epsilon n$. We study the
\textsc{$(c, \epsilon, \delta)$--Margin of Victory} problem for many commonly
used voting rules including scoring rules, approval, Bucklin, maximin, and
Copeland$^{\alpha}.$ We observe that even for the voting rules for which
computing the margin of victory is NP-Hard, there may exist efficient sampling
based algorithms, as observed in the cases of maximin and Copeland$^{\alpha}$
voting rules.
FlowNet: Learning Optical Flow with Convolutional Networks
Authors: Philipp Fischer, Alexey Dosovitskiy, Eddy Ilg, Philip Häusser, Caner Hazırbaş, Vladimir Golkov, Patrick van der Smagt, Daniel Cremers, Thomas Brox
Date: 2015-04-26 00:00:00
Proceeding: ICCV 2015 12
Tasks: Optical Flow Estimation

Convolutional neural networks (CNNs) have recently been very successful in a
variety of computer vision tasks, especially on those linked to recognition.
Optical flow estimation has not been among the tasks where CNNs were
successful. In this paper we construct appropriate CNNs which are capable of
solving the optical flow estimation problem as a supervised learning task. We
propose and compare two architectures: a generic architecture and another one
including a layer that correlates feature vectors at different image locations.
  Since existing ground truth data sets are not sufficiently large to train a
CNN, we generate a synthetic Flying Chairs dataset. We show that networks
trained on this unrealistic data still generalize very well to existing
datasets such as Sintel and KITTI, achieving competitive accuracy at frame
rates of 5 to 10 fps.
Logic of temporal attribute implications
Authors: Jan Triska, Vilem Vychodil
Date: 2014-12-11 00:00:00
Tasks: Attribute

We study logic for reasoning with if-then formulas describing dependencies
between attributes of objects which are observed in consecutive points in time.
We introduce semantic entailment of the formulas, show its fixed-point
characterization, investigate closure properties of model classes, present an
axiomatization and prove its completeness, and investigate alternative
axiomatizations and normalized proofs. We investigate decidability and
complexity issues of the logic and prove that the entailment problem is NP-hard
and belongs to EXPSPACE. We show that by restricting to predictive formulas,
the entailment problem is decidable in pseudo-linear time.
Learning Document Image Binarization from Data
Authors: Yue Wu, Stephen Rawls, Wael Abd-Almageed, Premkumar Natarajan
Date: 2015-05-04 00:00:00
Tasks: Binarization

In this paper we present a fully trainable binarization solution for degraded
document images. Unlike previous attempts that often used simple features with
a series of pre- and post-processing, our solution encodes all heuristics about
whether or not a pixel is foreground text into a high-dimensional feature
vector and learns a more complicated decision function. In particular, we
prepare features of three types: 1) existing features for binarization such as
intensity [1], contrast [2], [3], and Laplacian [4], [5]; 2) reformulated
features from existing binarization decision functions such those in [6] and
[7]; and 3) our newly developed features, namely the Logarithm Intensity
Percentile (LIP) and the Relative Darkness Index (RDI). Our initial
experimental results show that using only selected samples (about 1.5% of all
available training data), we can achieve a binarization performance comparable
to those fine-tuned (typically by hand), state-of-the-art methods.
Additionally, the trained document binarization classifier shows good
generalization capabilities on out-of-domain data.
An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection
Authors: Tianbao Yang, Lijun Zhang, Rong Jin, Shenghuo Zhu
Date: 2015-05-04 00:00:00

In this paper, we consider the problem of column subset selection. We present
a novel analysis of the spectral norm reconstruction for a simple randomized
algorithm and establish a new bound that depends explicitly on the sampling
probabilities. The sampling dependent error bound (i) allows us to better
understand the tradeoff in the reconstruction error due to sampling
probabilities, (ii) exhibits more insights than existing error bounds that
exploit specific probability distributions, and (iii) implies better sampling
distributions. In particular, we show that a sampling distribution with
probabilities proportional to the square root of the statistical leverage
scores is always better than uniform sampling and is better than leverage-based
sampling when the statistical leverage scores are very nonuniform. And by
solving a constrained optimization problem related to the error bound with an
efficient bisection search we are able to achieve better performance than using
either the leverage-based distribution or that proportional to the square root
of the statistical leverage scores. Numerical simulations demonstrate the
benefits of the new sampling distributions for low-rank matrix approximation
and least square approximation compared to state-of-the art algorithms.
Modeling Representation of Videos for Anomaly Detection using Deep Learning: A Review
Authors: Yong Shean Chong, Yong Haur Tay
Date: 2015-05-04 00:00:00
Tasks: Action Recognition, Anomaly Detection, Deep Learning, Temporal Action Localization, Video Anomaly Detection

This review article surveys the current progresses made toward video-based
anomaly detection. We address the most fundamental aspect for video anomaly
detection, that is, video feature representation. Much research works have been
done in finding the right representation to perform anomaly detection in video
streams accurately with an acceptable false alarm rate. However, this is very
challenging due to large variations in environment and human movement, and high
space-time complexity due to huge dimensionality of video data. The weakly
supervised nature of deep learning algorithms can help in learning
representations from the video data itself instead of manually designing the
right feature for specific scenes. In this paper, we would like to review the
existing methods of modeling video representations using deep learning
techniques for the task of anomaly detection and action recognition.
Security Games with Information Leakage: Modeling and Computation
Authors: Haifeng Xu, Albert X. Jiang, Arunesh Sinha, Zinovi Rabinovich, Shaddin Dughmi, Milind Tambe
Date: 2015-04-23 00:00:00

Most models of Stackelberg security games assume that the attacker only knows
the defender's mixed strategy, but is not able to observe (even partially) the
instantiated pure strategy. Such partial observation of the deployed pure
strategy -- an issue we refer to as information leakage -- is a significant
concern in practical applications. While previous research on patrolling games
has considered the attacker's real-time surveillance, our settings, therefore
models and techniques, are fundamentally different. More specifically, after
describing the information leakage model, we start with an LP formulation to
compute the defender's optimal strategy in the presence of leakage. Perhaps
surprisingly, we show that a key subproblem to solve this LP (more precisely,
the defender oracle) is NP-hard even for the simplest of security game models.
We then approach the problem from three possible directions: efficient
algorithms for restricted cases, approximation algorithms, and heuristic
algorithms for sampling that improves upon the status quo. Our experiments
confirm the necessity of handling information leakage and the advantage of our
algorithms.
Computational Baby Learning
Authors: Xiaodan Liang, Si Liu, Yunchao Wei, Luoqi Liu, Liang Lin, Shuicheng Yan
Date: 2014-11-11 00:00:00
Tasks: object-detection, Object Detection

Intuitive observations show that a baby may inherently possess the capability
of recognizing a new visual concept (e.g., chair, dog) by learning from only
very few positive instances taught by parent(s) or others, and this recognition
capability can be gradually further improved by exploring and/or interacting
with the real instances in the physical world. Inspired by these observations,
we propose a computational model for slightly-supervised object detection,
based on prior knowledge modelling, exemplar learning and learning with video
contexts. The prior knowledge is modeled with a pre-trained Convolutional
Neural Network (CNN). When very few instances of a new concept are given, an
initial concept detector is built by exemplar learning over the deep features
from the pre-trained CNN. Simulating the baby's interaction with physical
world, the well-designed tracking solution is then used to discover more
diverse instances from the massive online unlabeled videos. Once a positive
instance is detected/identified with high score in each video, more variable
instances possibly from different view-angles and/or different distances are
tracked and accumulated. Then the concept detector can be fine-tuned based on
these new instances. This process can be repeated again and again till we
obtain a very mature concept detector. Extensive experiments on Pascal
VOC-07/10/12 object detection datasets well demonstrate the effectiveness of
our framework. It can beat the state-of-the-art full-training based
performances by learning from very few samples for each object category, along
with about 20,000 unlabeled videos.
Learning the Structure and Parameters of Large-Population Graphical Games from Behavioral Data
Authors: Jean Honorio, Luis Ortiz
Date: 2012-06-16 00:00:00

We consider learning, from strictly behavioral data, the structure and
parameters of linear influence games (LIGs), a class of parametric graphical
games introduced by Irfan and Ortiz (2014). LIGs facilitate causal strategic
inference (CSI): Making inferences from causal interventions on stable behavior
in strategic settings. Applications include the identification of the most
influential individuals in large (social) networks. Such tasks can also support
policy-making analysis. Motivated by the computational work on LIGs, we cast
the learning problem as maximum-likelihood estimation (MLE) of a generative
model defined by pure-strategy Nash equilibria (PSNE). Our simple formulation
uncovers the fundamental interplay between goodness-of-fit and model
complexity: good models capture equilibrium behavior within the data while
controlling the true number of equilibria, including those unobserved. We
provide a generalization bound establishing the sample complexity for MLE in
our framework. We propose several algorithms including convex loss minimization
(CLM) and sigmoidal approximations. We prove that the number of exact PSNE in
LIGs is small, with high probability; thus, CLM is sound. We illustrate our
approach on synthetic data and real-world U.S. congressional voting records. We
briefly discuss our learning framework's generality and potential applicability
to general graphical games.
Sequential Labeling with online Deep Learning
Authors: Gang Chen, ran Xu, Sargur Srihari
Date: 2014-12-10 00:00:00
Tasks: Deep Learning, Dimensionality Reduction

Deep learning has attracted great attention recently and yielded the state of
the art performance in dimension reduction and classification problems.
However, it cannot effectively handle the structured output prediction, e.g.
sequential labeling. In this paper, we propose a deep learning structure, which
can learn discriminative features for sequential labeling problems. More
specifically, we add the inter-relationship between labels in our deep learning
structure, in order to incorporate the context information from the sequential
data. Thus, our model is more powerful than linear Conditional Random Fields
(CRFs) because the objective function learns latent non-linear features so that
target labeling can be better predicted. We pretrain the deep structure with
stacked restricted Boltzmann machines (RBMs) for feature learning and optimize
our objective function with online learning algorithm, a mixture of perceptron
training and stochastic gradient descent. We test our model on different
challenge tasks, and show that our model outperforms significantly over the
completive baselines.
Revisiting Algebra and Complexity of Inference in Graphical Models
Authors: Siamak Ravanbakhsh, Russell Greiner
Date: 2014-09-25 00:00:00
Tasks: Survey

This paper studies the form and complexity of inference in graphical models
using the abstraction offered by algebraic structures. In particular, we
broadly formalize inference problems in graphical models by viewing them as a
sequence of operations based on commutative semigroups. We then study the
computational complexity of inference by organizing various problems into an
"inference hierarchy". When the underlying structure of an inference problem is
a commutative semiring -- i.e. a combination of two commutative semigroups with
the distributive law -- a message passing procedure called belief propagation
can leverage this distributive law to perform polynomial-time inference for
certain problems. After establishing the NP-hardness of inference in any
commutative semiring, we investigate the relation between algebraic properties
in this setting and further show that polynomial-time inference using
distributive law does not (trivially) extend to inference problems that are
expressed using more than two commutative semigroups. We then extend the
algebraic treatment of message passing procedures to survey propagation,
providing a novel perspective using a combination of two commutative semirings.
This formulation generalizes the application of survey propagation to new
settings.
Concept Drift Detection for Streaming Data
Authors: Heng Wang, Zubin Abraham
Date: 2015-04-04 00:00:00
Tasks: Drift Detection

Common statistical prediction models often require and assume stationarity in
the data. However, in many practical applications, changes in the relationship
of the response and predictor variables are regularly observed over time,
resulting in the deterioration of the predictive performance of these models.
This paper presents Linear Four Rates (LFR), a framework for detecting these
concept drifts and subsequently identifying the data points that belong to the
new concept (for relearning the model). Unlike conventional concept drift
detection approaches, LFR can be applied to both batch and stream data; is not
limited by the distribution properties of the response variable (e.g., datasets
with imbalanced labels); is independent of the underlying statistical-model;
and uses user-specified parameters that are intuitively comprehensible. The
performance of LFR is compared to benchmark approaches using both simulated and
commonly used public datasets that span the gamut of concept drift types. The
results show LFR significantly outperforms benchmark approaches in terms of
recall, accuracy and delay in detection of concept drifts across datasets.
Random Subspace Learning Approach to High-Dimensional Outliers Detection
Authors: Bohan Liu, Ernest Fokoue
Date: 2015-02-16 00:00:00
Tasks: Outlier Detection, Vocal Bursts Intensity Prediction

We introduce and develop a novel approach to outlier detection based on
adaptation of random subspace learning. Our proposed method handles both
high-dimension low-sample size and traditional low-dimensional high-sample size
datasets. Essentially, we avoid the computational bottleneck of techniques like
minimum covariance determinant (MCD) by computing the needed determinants and
associated measures in much lower dimensional subspaces. Both theoretical and
computational development of our approach reveal that it is computationally
more efficient than the regularized methods in high-dimensional low-sample
size, and often competes favorably with existing methods as far as the
percentage of correct outlier detection is concerned.
Risk Bounds For Mode Clustering
Authors: Martin Azizyan, Yen-Chi Chen, Aarti Singh, Larry Wasserman
Date: 2015-05-03 00:00:00
Tasks: Clustering, Nonparametric Clustering

Density mode clustering is a nonparametric clustering method. The clusters
are the basins of attraction of the modes of a density estimator. We study the
risk of mode-based clustering. We show that the clustering risk over the
cluster cores --- the regions where the density is high --- is very small even
in high dimensions. And under a low noise condition, the overall cluster risk
is small even beyond the cores, in high dimensions.
Kernel Spectral Clustering and applications
Authors: Rocco Langone, Raghvendra Mall, Carlos Alzate, Johan A. K. Suykens
Date: 2015-05-03 00:00:00
Tasks: Clustering, Image Segmentation, Model Selection, Semantic Segmentation, Time Series Analysis, Time Series Clustering

In this chapter we review the main literature related to kernel spectral
clustering (KSC), an approach to clustering cast within a kernel-based
optimization setting. KSC represents a least-squares support vector machine
based formulation of spectral clustering described by a weighted kernel PCA
objective. Just as in the classifier case, the binary clustering model is
expressed by a hyperplane in a high dimensional space induced by a kernel. In
addition, the multi-way clustering can be obtained by combining a set of binary
decision functions via an Error Correcting Output Codes (ECOC) encoding scheme.
Because of its model-based nature, the KSC method encompasses three main steps:
training, validation, testing. In the validation stage model selection is
performed to obtain tuning parameters, like the number of clusters present in
the data. This is a major advantage compared to classical spectral clustering
where the determination of the clustering parameters is unclear and relies on
heuristics. Once a KSC model is trained on a small subset of the entire data,
it is able to generalize well to unseen test points. Beyond the basic
formulation, sparse KSC algorithms based on the Incomplete Cholesky
Decomposition (ICD) and $L_0$, $L_1, L_0 + L_1$, Group Lasso regularization are
reviewed. In that respect, we show how it is possible to handle large scale
data. Also, two possible ways to perform hierarchical clustering and a soft
clustering method are presented. Finally, real-world applications such as image
segmentation, power load time-series clustering, document clustering and big
data learning are considered.