pwc-archive/papers-with-abstracts huggingface dataset:
Generative Maximum Entropy Learning for Multiclass Classification
Authors: Ambedkar Dukkipati, Gaurav Pandey, Debarghya Ghoshdastidar, Paramita Koley, D. M. V. Satya Sriram
Date: 2012-05-03 00:00:00
Tasks: Binary Classification, Classification, feature selection, General Classification

Maximum entropy approach to classification is very well studied in applied
statistics and machine learning and almost all the methods that exists in
literature are discriminative in nature. In this paper, we introduce a maximum
entropy classification method with feature selection for large dimensional data
such as text datasets that is generative in nature. To tackle the curse of
dimensionality of large data sets, we employ conditional independence
assumption (Naive Bayes) and we perform feature selection simultaneously, by
enforcing a `maximum discrimination' between estimated class conditional
densities. For two class problems, in the proposed method, we use Jeffreys
($J$) divergence to discriminate the class conditional densities. To extend our
method to the multi-class case, we propose a completely new approach by
considering a multi-distribution divergence: we replace Jeffreys divergence by
Jensen-Shannon ($JS$) divergence to discriminate conditional densities of
multiple classes. In order to reduce computational complexity, we employ a
modified Jensen-Shannon divergence ($JS_{GM}$), based on AM-GM inequality. We
show that the resulting divergence is a natural generalization of Jeffreys
divergence to a multiple distributions case. As far as the theoretical
justifications are concerned we show that when one intends to select the best
features in a generative maximum entropy approach, maximum discrimination using
$J-$divergence emerges naturally in binary classification. Performance and
comparative study of the proposed algorithms have been demonstrated on large
dimensional text and gene expression datasets that show our methods scale up
very well with large dimensional datasets.
Structure-Aware Dynamic Scheduler for Parallel Machine Learning
Authors: Seunghak Lee, Jin Kyu Kim, Qirong Ho, Garth A. Gibson, Eric P. Xing
Date: 2013-12-19 00:00:00
Tasks: BIG-bench Machine Learning, Distributed Computing

Training large machine learning (ML) models with many variables or parameters
can take a long time if one employs sequential procedures even with stochastic
updates. A natural solution is to turn to distributed computing on a cluster;
however, naive, unstructured parallelization of ML algorithms does not usually
lead to a proportional speedup and can even result in divergence, because
dependencies between model elements can attenuate the computational gains from
parallelization and compromise correctness of inference. Recent efforts toward
this issue have benefited from exploiting the static, a priori block structures
residing in ML algorithms. In this paper, we take this path further by
exploring the dynamic block structures and workloads therein present during ML
program execution, which offers new opportunities for improving convergence,
correctness, and load balancing in distributed ML. We propose and showcase a
general-purpose scheduler, STRADS, for coordinating distributed updates in ML
algorithms, which harnesses the aforementioned opportunities in a systematic
way. We provide theoretical guarantees for our scheduler, and demonstrate its
efficacy versus static block structures on Lasso and Matrix Factorization.
Consensus Sequence Segmentation
Authors: Tamal Chowdhury, Rabindra Rakshit, Arko Banerjee
Date: 2013-08-18 00:00:00
Tasks: Segmentation

In this paper we introduce a method to detect words or phrases in a given
sequence of alphabets without knowing the lexicon. Our linear time unsupervised
algorithm relies entirely on statistical relationships among alphabets in the
input sequence to detect location of word boundaries. We compare our algorithm
to previous approaches from unsupervised sequence segmentation literature and
provide superior segmentation over number of benchmarks.
Ant Colony Optimization and Hypergraph Covering Problems
Authors: Ankit Pat, Ashish Ranjan Hota
Date: 2011-05-14 00:00:00
Tasks: Combinatorial Optimization

Ant Colony Optimization (ACO) is a very popular metaheuristic for solving
computationally hard combinatorial optimization problems. Runtime analysis of
ACO with respect to various pseudo-boolean functions and different graph based
combinatorial optimization problems has been taken up in recent years. In this
paper, we investigate the runtime behavior of an MMAS*(Max-Min Ant System) ACO
algorithm on some well known hypergraph covering problems that are NP-Hard. In
particular, we have addressed the Minimum Edge Cover problem, the Minimum
Vertex Cover problem and the Maximum Weak- Independent Set problem. The
influence of pheromone values and heuristic information on the running time is
analysed. The results indicate that the heuristic information has greater
impact towards improving the expected optimization time as compared to
pheromone values. For certain instances of hypergraphs, we show that the MMAS*
algorithm gives a constant order expected optimization time when the dominance
of heuristic information is suitably increased.
A Novel Method for Automatic Segmentation of Brain Tumors in MRI Images
Authors: Saeid Fazli, Parisa Nadirkhanlou
Date: 2013-12-29 00:00:00
Tasks: Brain Tumor Segmentation, Segmentation, Tumor Segmentation

The brain tumor segmentation on MRI images is a very difficult and important
task which is used in surgical and medical planning and assessments. If experts
do the segmentation manually with their own medical knowledge, it will be
time-consuming. Therefore, researchers propose methods and systems which can do
the segmentation automatically and without any interference. In this article,
an unsupervised automatic method for brain tumor segmentation on MRI images is
presented. In this method, at first in the pre-processing level, the extra
parts which are outside the skull and don't have any helpful information are
removed and then anisotropic diffusion filter with 8-connected neighborhood is
applied to the MRI images to remove noise. By applying the fast bounding
box(FBB) algorithm, the tumor area is displayed on the MRI image with a
bounding box and the central part is selected as sample points for training of
a One Class SVM classifier. A database is also provided by the Zanjan MRI
Center. The MRI images are related to 10 patients who have brain tumor. 100
T2-weighted MRI images are used in this study. Experimental results show the
high precision and dependability of the proposed algorithm. The results are
also highly helpful for specialists and radiologists to easily estimate the
size and position of a tumor.
Actions in the Eye: Dynamic Gaze Datasets and Learnt Saliency Models for Visual Recognition
Authors: Stefan Mathe, Cristian Sminchisescu
Date: 2013-12-29 00:00:00
Tasks: Action Recognition, Temporal Action Localization

Systems based on bag-of-words models from image features collected at maxima
of sparse interest point operators have been used successfully for both
computer visual object and action recognition tasks. While the sparse,
interest-point based approach to recognition is not inconsistent with visual
processing in biological systems that operate in `saccade and fixate' regimes,
the methodology and emphasis in the human and the computer vision communities
remains sharply distinct. Here, we make three contributions aiming to bridge
this gap. First, we complement existing state-of-the art large scale dynamic
computer vision annotated datasets like Hollywood-2 and UCF Sports with human
eye movements collected under the ecological constraints of the visual action
recognition task. To our knowledge these are the first large human eye tracking
datasets to be collected and made publicly available for video,
vision.imar.ro/eyetracking (497,107 frames, each viewed by 16 subjects), unique
in terms of their (a) large scale and computer vision relevance, (b) dynamic,
video stimuli, (c) task control, as opposed to free-viewing. Second, we
introduce novel sequential consistency and alignment measures, which underline
the remarkable stability of patterns of visual search among subjects. Third, we
leverage the significant amount of collected data in order to pursue studies
and build automatic, end-to-end trainable computer vision systems based on
human eye movements. Our studies not only shed light on the differences between
computer vision spatio-temporal interest point image sampling strategies and
the human fixations, as well as their impact for visual recognition
performance, but also demonstrate that human fixations can be accurately
predicted, and when used in an end-to-end automatic system, leveraging some of
the advanced computer vision practice, can lead to state of the art results.
Nonparametric Inference For Density Modes
Authors: Christopher Genovese, Marco Perone-Pacifico, Isabella Verdinelli, Larry Wasserman
Date: 2013-12-29 00:00:00
Tasks: valid

We derive nonparametric confidence intervals for the eigenvalues of the
Hessian at modes of a density estimate. This provides information about the
strength and shape of modes and can also be used as a significance test. We use
a data-splitting approach in which potential modes are identified using the
first half of the data and inference is done with the second half of the data.
To get valid confidence sets for the eigenvalues, we use a bootstrap based on
an elementary-symmetric-polynomial (ESP) transformation. This leads to valid
bootstrap confidence sets regardless of any multiplicities in the eigenvalues.
We also suggest a new method for bandwidth selection, namely, choosing the
bandwidth to maximize the number of significant modes. We show by example that
this method works well. Even when the true distribution is singular, and hence
does not have a density, (in which case cross validation chooses a zero
bandwidth), our method chooses a reasonable bandwidth.
Implementation of Hand Detection based Techniques for Human Computer Interaction
Authors: Amiraj Dhawan, Vipul Honrao
Date: 2013-12-29 00:00:00
Tasks: Hand Detection

The computer industry is developing at a fast pace. With this development
almost all of the fields under computers have advanced in the past couple of
decades. But the same technology is being used for human computer interaction
that was used in 1970s. Even today the same type of keyboard and mouse is used
for interacting with computer systems. With the recent boom in the mobile
segment touchscreens have become popular for interaction with cell phones. But
these touchscreens are rarely used on traditional systems. This paper tries to
introduce methods for human computer interaction using the users hand which can
be used both on traditional computer platforms as well as cell phones. The
methods explain how the users detected hand can be used as input for
applications and also explain applications that can take advantage of this type
of interaction mechanism.
A Novel Retinal Vessel Segmentation Based On Histogram Transformation Using 2-D Morlet Wavelet and Supervised Classification
Authors: Saeid Fazli, Sevin Samadi
Date: 2013-12-29 00:00:00
Tasks: General Classification, Retinal Vessel Segmentation, Segmentation

The appearance and structure of blood vessels in retinal images have an
important role in diagnosis of diseases. This paper proposes a method for
automatic retinal vessel segmentation. In this work, a novel preprocessing
based on local histogram equalization is used to enhance the original image
then pixels are classified as vessel and non-vessel using a classifier. For
this classification, special feature vectors are organized based on responses
to Morlet wavelet. Morlet wavelet is a continues transform which has the
ability to filter existing noises after preprocessing. Bayesian classifier is
used and Gaussian mixture model (GMM) is its likelihood function. The
probability distributions are approximated according to training set of manual
that has been segmented by a specialist. After this, morphological transforms
are used in different directions to make the existing discontinuities uniform
on the DRIVE database, it achieves the accuracy about 0.9571 which shows that
it is an accurate method among the available ones for retinal vessel
segmentation.
A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain
Authors: Robin Scheibler, Saeid Haghighatshoar, Martin Vetterli
Date: 2013-10-07 00:00:00

A new iterative low complexity algorithm has been presented for computing the
Walsh-Hadamard transform (WHT) of an $N$ dimensional signal with a $K$-sparse
WHT, where $N$ is a power of two and $K = O(N^\alpha)$, scales sub-linearly in
$N$ for some $0 < \alpha < 1$. Assuming a random support model for the non-zero
transform domain components, the algorithm reconstructs the WHT of the signal
with a sample complexity $O(K \log_2(\frac{N}{K}))$, a computational complexity
$O(K\log_2(K)\log_2(\frac{N}{K}))$ and with a very high probability
asymptotically tending to 1.
  The approach is based on the subsampling (aliasing) property of the WHT,
where by a carefully designed subsampling of the time domain signal, one can
induce a suitable aliasing pattern in the transform domain. By treating the
aliasing patterns as parity-check constraints and borrowing ideas from erasure
correcting sparse-graph codes, the recovery of the non-zero spectral values has
been formulated as a belief propagation (BP) algorithm (peeling decoding) over
a sparse-graph code for the binary erasure channel (BEC). Tools from coding
theory are used to analyze the asymptotic performance of the algorithm in the
very sparse ($\alpha\in(0,\frac{1}{3}]$) and the less sparse
($\alpha\in(\frac{1}{3},1)$) regime.
Learning Temporal Logical Properties Discriminating ECG models of Cardiac Arrhytmias
Authors: Ezio Bartocci, Luca Bortolussi, Guido Sanguinetti
Date: 2013-12-29 00:00:00
Tasks: Diagnostic

We present a novel approach to learn the formulae characterising the emergent
behaviour of a dynamical system from system observations. At a high level, the
approach starts by devising a statistical dynamical model of the system which
optimally fits the observations. We then propose general optimisation
strategies for selecting high support formulae (under the learnt model of the
system) either within a discrete set of formulae of bounded complexity, or a
parametric family of formulae. We illustrate and apply the methodology on an
in-depth case study of characterising cardiac malfunction from
electro-cardiogram data, where our approach enables us to quantitatively
determine the diagnostic power of a formula in discriminating between different
cardiac conditions.
A Novel Scheme for Generating Secure Face Templates Using BDA
Authors: Shraddha S. Shinde, Prof. Anagha P. Khedkar
Date: 2013-12-29 00:00:00
Tasks: Management

In identity management system, frequently used biometric recognition system needs awareness towards issue of protecting biometric template as far as more reliable solution is apprehensive. In sight of this biometric template protection algorithm should gratify the basic requirements viz. security, discriminability and cancelability. As no single template protection method is capable of satisfying these requirements, a novel scheme for face template generation and protection is proposed. The novel scheme is proposed to provide security and accuracy in new user enrolment and authentication process. This novel scheme takes advantage of both the hybrid approach and the binary discriminant analysis algorithm. This algorithm is designed on the basis of random projection, binary discriminant analysis and fuzzy commitment scheme. Publicly available benchmark face databases (FERET, FRGC, CMU-PIE) and other datasets are used for evaluation. The proposed novel scheme enhances the discriminability and recognition accuracy in terms of matching score of the face images for each stage and provides high security against potential attacks namely brute force and smart attacks. In this paper, we discuss results viz. averages matching score, computation time and security for hybrid approach and novel approach.
A General Algorithm for Deciding Transportability of Experimental Results
Authors: Elias Bareinboim, Judea Pearl
Date: 2013-12-29 00:00:00

Generalizing empirical findings to new environments, settings, or populations
is essential in most scientific explorations. This article treats a particular
problem of generalizability, called "transportability", defined as a license to
transfer information learned in experimental studies to a different population,
on which only observational studies can be conducted. Given a set of
assumptions concerning commonalities and differences between the two
populations, Pearl and Bareinboim (2011) derived sufficient conditions that
permit such transfer to take place. This article summarizes their findings and
supplements them with an effective procedure for deciding when and how
transportability is feasible. It establishes a necessary and sufficient
condition for deciding when causal effects in the target population are
estimable from both the statistical information available and the causal
information transferred from the experiments. The article further provides a
complete algorithm for computing the transport formula, that is, a way of
combining observational and experimental information to synthesize bias-free
estimate of the desired causal relation. Finally, the article examines the
differences between transportability and other variants of generalizability.
Generalized Ambiguity Decomposition for Understanding Ensemble Diversity
Authors: Kartik Audhkhasi, Abhinav Sethy, Bhuvana Ramabhadran, Shrikanth. S. Narayanan
Date: 2013-12-28 00:00:00
Tasks: Diversity, General Classification, regression

Diversity or complementarity of experts in ensemble pattern recognition and
information processing systems is widely-observed by researchers to be crucial
for achieving performance improvement upon fusion. Understanding this link
between ensemble diversity and fusion performance is thus an important research
question. However, prior works have theoretically characterized ensemble
diversity and have linked it with ensemble performance in very restricted
settings. We present a generalized ambiguity decomposition (GAD) theorem as a
broad framework for answering these questions. The GAD theorem applies to a
generic convex ensemble of experts for any arbitrary twice-differentiable loss
function. It shows that the ensemble performance approximately decomposes into
a difference of the average expert performance and the diversity of the
ensemble. It thus provides a theoretical explanation for the
empirically-observed benefit of fusing outputs from diverse classifiers and
regressors. It also provides a loss function-dependent, ensemble-dependent, and
data-dependent definition of diversity. We present extensions of this
decomposition to common regression and classification loss functions, and
report a simulation-based analysis of the diversity term and the accuracy of
the decomposition. We finally present experiments on standard pattern
recognition data sets which indicate the accuracy of the decomposition for
real-world classification and regression problems.
Proceedings of Answer Set Programming and Other Computing Paradigms (ASPOCP 2013), 6th International Workshop, August 25, 2013, Istanbul, Turkey
Authors: Michael Fink, Yuliya Lierler
Date: 2013-12-28 00:00:00

This volume contains the papers presented at the sixth workshop on Answer Set
Programming and Other Computing Paradigms (ASPOCP 2013) held on August 25th,
2013 in Istanbul, co-located with the 29th International Conference on Logic
Programming (ICLP 2013). It thus continues a series of previous events
co-located with ICLP, aiming at facilitating the discussion about crossing the
boundaries of current ASP techniques in theory, solving, and applications, in
combination with or inspired by other computing paradigms.
Stopping Rules for Bag-of-Words Image Search and Its Application in Appearance-Based Localization
Authors: Kiana Hajebi, Hong Zhang
Date: 2013-12-28 00:00:00
Tasks: Image Retrieval, Quantization, Retrieval

We propose a technique to improve the search efficiency of the bag-of-words
(BoW) method for image retrieval. We introduce a notion of difficulty for the
image matching problems and propose methods that reduce the amount of
computations required for the feature vector-quantization task in BoW by
exploiting the fact that easier queries need less computational resources.
Measuring the difficulty of a query and stopping the search accordingly is
formulated as a stopping problem. We introduce stopping rules that terminate
the image search depending on the difficulty of each query, thereby
significantly reducing the computational cost. Our experimental results show
the effectiveness of our approach when it is applied to appearance-based
localization problem.
Positive definite matrices and the S-divergence
Authors: Suvrit Sra
Date: 2011-10-08 00:00:00

Positive definite matrices abound in a dazzling variety of applications. This
ubiquity can be in part attributed to their rich geometric structure: positive
definite matrices form a self-dual convex cone whose strict interior is a
Riemannian manifold. The manifold view is endowed with a "natural" distance
function while the conic view is not. Nevertheless, drawing motivation from the
conic view, we introduce the S-Divergence as a "natural" distance-like function
on the open cone of positive definite matrices. We motivate the S-divergence
via a sequence of results that connect it to the Riemannian distance. In
particular, we show that (a) this divergence is the square of a distance; and
(b) that it has several geometric properties similar to those of the Riemannian
distance, though without being computationally as demanding. The S-divergence
is even more intriguing: although nonconvex, we can still compute matrix means
and medians using it to global optimality. We complement our results with some
numerical experiments illustrating our theorems and our optimization algorithm
for computing matrix medians.
lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
Authors: Kevin Jamieson, Matthew Malloy, Robert Nowak, Sébastien Bubeck
Date: 2013-12-27 00:00:00
Tasks: Multi-Armed Bandits

The paper proposes a novel upper confidence bound (UCB) procedure for
identifying the arm with the largest mean in a multi-armed bandit game in the
fixed confidence setting using a small number of total samples. The procedure
cannot be improved in the sense that the number of samples required to identify
the best arm is within a constant factor of a lower bound based on the law of
the iterated logarithm (LIL). Inspired by the LIL, we construct our confidence
bounds to explicitly account for the infinite time horizon of the algorithm. In
addition, by using a novel stopping time for the algorithm we avoid a union
bound over the arms that has been observed in other UCB-type algorithms. We
prove that the algorithm is optimal up to constants and also show through
simulations that it provides superior performance with respect to the
state-of-the-art.
A Novel Feature-based Bayesian Model for Query Focused Multi-document Summarization
Authors: Jiwei Li, Sujian Li
Date: 2012-12-10 00:00:00
Proceeding: TACL 2013 1
Tasks: Document Summarization, Multi-Document Summarization, Sentence, Topic Models

Both supervised learning methods and LDA based topic model have been
successfully applied in the field of query focused multi-document
summarization. In this paper, we propose a novel supervised approach that can
incorporate rich sentence features into Bayesian topic models in a principled
way, thus taking advantages of both topic model and feature based supervised
learning methods. Experiments on TAC2008 and TAC2009 demonstrate the
effectiveness of our approach.