pwc-archive/papers-with-abstracts huggingface dataset:
Local Rademacher Complexity for Multi-label Learning
Authors: Chang Xu, Tongliang Liu, DaCheng Tao, Chao Xu
Date: 2014-10-26 00:00:00
Tasks: Multi-Label Learning

We analyze the local Rademacher complexity of empirical risk minimization
(ERM)-based multi-label learning algorithms, and in doing so propose a new
algorithm for multi-label learning. Rather than using the trace norm to
regularize the multi-label predictor, we instead minimize the tail sum of the
singular values of the predictor in multi-label learning. Benefiting from the
use of the local Rademacher complexity, our algorithm, therefore, has a sharper
generalization error bound and a faster convergence rate. Compared to methods
that minimize over all singular values, concentrating on the tail singular
values results in better recovery of the low-rank structure of the multi-label
predictor, which plays an import role in exploiting label correlations. We
propose a new conditional singular value thresholding algorithm to solve the
resulting objective function. Empirical studies on real-world datasets validate
our theoretical results and demonstrate the effectiveness of the proposed
algorithm.
Fully Automated Myocardial Infarction Classification using Ordinary Differential Equations
Authors: Getie Zewdie, Momiao Xiong
Date: 2014-10-26 00:00:00
Tasks: Classification, Diagnostic, General Classification, Specificity

Portable, Wearable and Wireless electrocardiogram (ECG) Systems have the
potential to be used as point-of-care for cardiovascular disease diagnostic
systems. Such wearable and wireless ECG systems require automatic detection of
cardiovascular disease. Even in the primary care, automation of ECG diagnostic
systems will improve efficiency of ECG diagnosis and reduce the minimal
training requirement of local healthcare workers. However, few fully automatic
myocardial infarction (MI) disease detection algorithms have well been
developed. This paper presents a novel automatic MI classification algorithm
using second order ordinary differential equation (ODE) with time varying
coefficients, which simultaneously captures morphological and dynamic feature
of highly correlated ECG signals. By effectively estimating the unobserved
state variables and the parameters of the second order ODE, the accuracy of the
classification was significantly improved. The estimated time varying
coefficients of the second order ODE were used as an input to the support
vector machine (SVM) for the MI classification. The proposed method was applied
to the PTB diagnostic ECG database within Physionet. The overall sensitivity,
specificity, and classification accuracy of 12 lead ECGs for MI binary
classifications were 98.7%, 96.4% and 98.3%, respectively. We also found that
even using one lead ECG signals, we can reach accuracy as high as 97%.
Multiclass MI classification is a challenging task but the developed ODE
approach for 12 lead ECGs coupled with multiclass SVM reached 96.4% accuracy
for classifying 5 subgroups of MI and healthy controls.
Notes on using Determinantal Point Processes for Clustering with Applications to Text Clustering
Authors: Apoorv Agarwal, Anna Choromanska, Krzysztof Choromanski
Date: 2014-10-26 00:00:00
Tasks: Clustering, Point Processes, Text Clustering

In this paper, we compare three initialization schemes for the KMEANS
clustering algorithm: 1) random initialization (KMEANSRAND), 2) KMEANS++, and
3) KMEANSD++. Both KMEANSRAND and KMEANS++ have a major that the value of k
needs to be set by the user of the algorithms. (Kang 2013) recently proposed a
novel use of determinantal point processes for sampling the initial centroids
for the KMEANS algorithm (we call it KMEANSD++). They, however, do not provide
any evaluation establishing that KMEANSD++ is better than other algorithms. In
this paper, we show that the performance of KMEANSD++ is comparable to KMEANS++
(both of which are better than KMEANSRAND) with KMEANSD++ having an additional
that it can automatically approximate the value of k.
Parameterizing the semantics of fuzzy attribute implications by systems of isotone Galois connections
Authors: Vilem Vychodil
Date: 2014-10-25 00:00:00
Tasks: Attribute

We study the semantics of fuzzy if-then rules called fuzzy attribute
implications parameterized by systems of isotone Galois connections. The rules
express dependencies between fuzzy attributes in object-attribute incidence
data. The proposed parameterizations are general and include as special cases
the parameterizations by linguistic hedges used in earlier approaches. We
formalize the general parameterizations, propose bivalent and graded notions of
semantic entailment of fuzzy attribute implications, show their
characterization in terms of least models and complete axiomatization, and
provide characterization of bases of fuzzy attribute implications derived from
data.
A Framework for On-Line Devanagari Handwritten Character Recognition
Authors: Sunil Kumar Kopparapu, Lajish V. L
Date: 2014-10-25 00:00:00

The main challenge in on-line handwritten character recognition in Indian
lan- guage is the large size of the character set, larger similarity between
different characters in the script and the huge variation in writing style. In
this paper we propose a framework for on-line handwitten script recognition
taking cues from speech signal processing literature. The framework is based on
identify- ing strokes, which in turn lead to recognition of handwritten on-line
characters rather that the conventional character identification. Though the
framework is described for Devanagari script, the framework is general and can
be applied to any language.
  The proposed platform consists of pre-processing, feature extraction, recog-
nition and post processing like the conventional character recognition but ap-
plied to strokes. The on-line Devanagari character recognition reduces to one
of recognizing one of 69 primitives and recognition of a character is performed
by recognizing a sequence of such primitives. We further show the impact of
noise removal on on-line raw data which is usually noisy. The use of Fuzzy
Direc- tional Features to enhance the accuracy of stroke recognition is also
described. The recognition results are compared with commonly used directional
features in literature using several classifiers.
Modified Mel Filter Bank to Compute MFCC of Subsampled Speech
Authors: Kiran Kumar Bhuvanagiri, Sunil Kumar Kopparapu
Date: 2014-10-25 00:00:00
Tasks: Speaker Recognition

Mel Frequency Cepstral Coefficients (MFCCs) are the most popularly used
speech features in most speech and speaker recognition applications. In this
work, we propose a modified Mel filter bank to extract MFCCs from subsampled
speech. We also propose a stronger metric which effectively captures the
correlation between MFCCs of original speech and MFCC of resampled speech. It
is found that the proposed method of filter bank construction performs
distinguishably well and gives recognition performance on resampled speech
close to recognition accuracies on original speech.
Choice of Mel Filter Bank in Computing MFCC of a Resampled Speech
Authors: Laxmi Narayana M., Sunil Kumar Kopparapu
Date: 2014-10-25 00:00:00
Tasks: Speaker Recognition

Mel Frequency Cepstral Coefficients (MFCCs) are the most popularly used
speech features in most speech and speaker recognition applications. In this
paper, we study the effect of resampling a speech signal on these speech
features. We first derive a relationship between the MFCC param- eters of the
resampled speech and the MFCC parameters of the original speech. We propose six
methods of calculating the MFCC parameters of downsampled speech by
transforming the Mel filter bank used to com- pute MFCC of the original speech.
We then experimentally compute the MFCC parameters of the down sampled speech
using the proposed meth- ods and compute the Pearson coefficient between the
MFCC parameters of the downsampled speech and that of the original speech to
identify the most effective choice of Mel-filter band that enables the computed
MFCC of the resampled speech to be as close as possible to the original speech
sample MFCC.
Screening Rules for Overlapping Group Lasso
Authors: Seunghak Lee, Eric P. Xing
Date: 2014-10-25 00:00:00

Recently, to solve large-scale lasso and group lasso problems, screening
rules have been developed, the goal of which is to reduce the problem size by
efficiently discarding zero coefficients using simple rules independently of
the others. However, screening for overlapping group lasso remains an open
challenge because the overlaps between groups make it infeasible to test each
group independently. In this paper, we develop screening rules for overlapping
group lasso. To address the challenge arising from groups with overlaps, we
take into account overlapping groups only if they are inclusive of the group
being tested, and then we derive screening rules, adopting the dual polytope
projection approach. This strategy allows us to screen each group independently
of each other. In our experiments, we demonstrate the efficiency of our
screening rules on various datasets.
The Quantum Nature of Identity in Human Thought: Bose-Einstein Statistics for Conceptual Indistinguishability
Authors: Diederik Aerts, Sandro Sozzo, Tomas Veloz
Date: 2014-10-24 00:00:00

Increasing experimental evidence shows that humans combine concepts in a way
that violates the rules of classical logic and probability theory. On the other
hand, mathematical models inspired by the formalism of quantum theory are in
accordance with data on concepts and their combinations. In this paper, we
investigate a novel type of concept combination were a number is combined with
a noun, e.g., `Eleven Animals. Our aim is to study 'conceptual identity' and
the effects of 'indistinguishability' - in the combination 'Eleven Animals',
the 'animals' are identical and indistinguishable - on the mechanisms of
conceptual combination. We perform experiments on human subjects and find
significant evidence of deviation from the predictions of classical statistical
theories, more specifically deviations with respect to Maxwell-Boltzmann
statistics. This deviation is of the 'same type' of the deviation of quantum
mechanical from classical mechanical statistics, due to indistinguishability of
microscopic quantum particles, i.e we find convincing evidence of the presence
of Bose-Einstein statistics. We also present preliminary promising evidence of
this phenomenon in a web-based study.
Clustering Words by Projection Entropy
Authors: Işık Barış Fidaner, Ali Taylan Cemgil
Date: 2014-10-24 00:00:00
Tasks: Clustering

We apply entropy agglomeration (EA), a recently introduced algorithm, to
cluster the words of a literary text. EA is a greedy agglomerative procedure
that minimizes projection entropy (PE), a function that can quantify the
segmentedness of an element set. To apply it, the text is reduced to a feature
allocation, a combinatorial object to represent the word occurences in the
text's paragraphs. The experiment results demonstrate that EA, despite its
reduction and simplicity, is useful in capturing significant relationships
among the words in the text. This procedure was implemented in Python and
published as a free software: REBUS.
On the Challenges of Physical Implementations of RBMs
Authors: Vincent Dumoulin, Ian J. Goodfellow, Aaron Courville, Yoshua Bengio
Date: 2013-12-18 00:00:00

Restricted Boltzmann machines (RBMs) are powerful machine learning models,
but learning and some kinds of inference in the model require sampling-based
approximations, which, in classical digital computers, are implemented using
expensive MCMC. Physical computation offers the opportunity to reduce the cost
of sampling by building physical systems whose natural dynamics correspond to
drawing samples from the desired RBM distribution. Such a system avoids the
burn-in and mixing cost of a Markov chain. However, hardware implementations of
this variety usually entail limitations such as low-precision and limited range
of the parameters and restrictions on the size and topology of the RBM. We
conduct software simulations to determine how harmful each of these
restrictions is. Our simulations are designed to reproduce aspects of the
D-Wave quantum computer, but the issues we investigate arise in most forms of
physical computation.
Online and Stochastic Gradient Methods for Non-decomposable Loss Functions
Authors: Purushottam Kar, Harikrishna Narasimhan, Prateek Jain
Date: 2014-10-24 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Incremental Learning, LEMMA

Modern applications in sensitive domains such as biometrics and medicine
frequently require the use of non-decomposable loss functions such as
precision@k, F-measure etc. Compared to point loss functions such as
hinge-loss, these offer much more fine grained control over prediction, but at
the same time present novel challenges in terms of algorithm design and
analysis. In this work we initiate a study of online learning techniques for
such non-decomposable loss functions with an aim to enable incremental learning
as well as design scalable solvers for batch problems. To this end, we propose
an online learning framework for such loss functions. Our model enjoys several
nice properties, chief amongst them being the existence of efficient online
learning algorithms with sublinear regret and online to batch conversion
bounds. Our model is a provable extension of existing online learning models
for point loss functions. We instantiate two popular losses, prec@k and pAUC,
in our model and prove sublinear regret bounds for both of them. Our proofs
require a novel structural lemma over ranked lists which may be of independent
interest. We then develop scalable stochastic gradient descent solvers for
non-decomposable loss functions. We show that for a large family of loss
functions satisfying a certain uniform convergence property (that includes
prec@k, pAUC, and F-measure), our methods provably converge to the empirical
risk minimizer. Such uniform convergence results were not known for these
losses and we establish these using novel proof techniques. We then use
extensive experimentation on real life and benchmark datasets to establish that
our method can be orders of magnitude faster than a recently proposed cutting
plane method.
On The Effect of Hyperedge Weights On Hypergraph Learning
Authors: Sheng Huang, Ahmed Elgammal, Dan Yang
Date: 2014-10-24 00:00:00
Tasks: Clustering, Graph Learning

Hypergraph is a powerful representation in several computer vision, machine
learning and pattern recognition problems. In the last decade, many researchers
have been keen to develop different hypergraph models. In contrast, no much
attention has been paid to the design of hyperedge weights. However, many
studies on pairwise graphs show that the choice of edge weight can
significantly influence the performances of such graph algorithms. We argue
that this also applies to hypegraphs. In this paper, we empirically discuss the
influence of hyperedge weight on hypegraph learning via proposing three novel
hyperedge weights from the perspectives of geometry, multivariate statistical
analysis and linear regression. Extensive experiments on ORL, COIL20, JAFFE,
Sheffield, Scene15 and Caltech256 databases verify our hypothesis. Similar to
graph learning, several representative hyperedge weighting schemes can be
concluded by our experimental studies. Moreover, the experiments also
demonstrate that the combinations of such weighting schemes and conventional
hypergraph models can get very promising classification and clustering
performances in comparison with some recent state-of-the-art algorithms.
On the Complexity of Optimization Problems based on Compiled NNF Representations
Authors: Daniel Le Berre, Emmanuel Lonca, Pierre Marquis
Date: 2014-10-24 00:00:00

Optimization is a key task in a number of applications. When the set of
feasible solutions under consideration is of combinatorial nature and described
in an implicit way as a set of constraints, optimization is typically NP-hard.
Fortunately, in many problems, the set of feasible solutions does not often
change and is independent from the user's request. In such cases, compiling the
set of constraints describing the set of feasible solutions during an off-line
phase makes sense, if this compilation step renders computationally easier the
generation of a non-dominated, yet feasible solution matching the user's
requirements and preferences (which are only known at the on-line step). In
this article, we focus on propositional constraints. The subsets L of the NNF
language analyzed in Darwiche and Marquis' knowledge compilation map are
considered. A number of families F of representations of objective functions
over propositional variables, including linear pseudo-Boolean functions and
more sophisticated ones, are considered. For each language L and each family F,
the complexity of generating an optimal solution when the constraints are
compiled into L and optimality is to be considered w.r.t. a function from F is
identified.
Augmenting Ordered Binary Decision Diagrams with Conjunctive Decomposition
Authors: Yong Lai, Dayou Liu, Minghao Yin
Date: 2014-10-24 00:00:00

This paper augments OBDD with conjunctive decomposition to propose a
generalization called OBDD[$\wedge$]. By imposing reducedness and the finest
$\wedge$-decomposition bounded by integer $i$
($\wedge_{\widehat{i}}$-decomposition) on OBDD[$\wedge$], we identify a family
of canonical languages called ROBDD[$\wedge_{\widehat{i}}$], where
ROBDD[$\wedge_{\widehat{0}}$] is equivalent to ROBDD. We show that the
succinctness of ROBDD[$\wedge_{\widehat{i}}$] is strictly increasing when $i$
increases. We introduce a new time-efficiency criterion called rapidity which
reflects that exponential operations may be preferable if the language can be
exponentially more succinct, and show that: the rapidity of each operation on
ROBDD[$\wedge_{\widehat{i}}$] is increasing when $i$ increases; particularly,
the rapidity of some operations (e.g., conjoining) is strictly increasing.
Finally, our empirical results show that: a) the size of
ROBDD[$\wedge_{\widehat{i}}$] is normally not larger than that of the
equivalent \ROBDDC{\widehat{i+1}}; b) conjoining two
ROBDD[$\wedge_{\widehat{1}}$]s is more efficient than conjoining two
ROBDD[$\wedge_{\widehat{0}}$]s in most cases, where the former is NP-hard but
the latter is in P; and c) the space-efficiency of
ROBDD[$\wedge_{\widehat{\infty}}$] is comparable with that of d-DNNF and that
of another canonical generalization of \ROBDD{} called SDD.
Probabilistic ODE Solvers with Runge-Kutta Means
Authors: Michael Schober, David Duvenaud, Philipp Hennig
Date: 2014-06-10 00:00:00
Proceeding: NeurIPS 2014 12

Runge-Kutta methods are the classic family of solvers for ordinary
differential equations (ODEs), and the basis for the state of the art. Like
most numerical methods, they return point estimates. We construct a family of
probabilistic numerical methods that instead return a Gauss-Markov process
defining a probability distribution over the ODE solution. In contrast to prior
work, we construct this family such that posterior means match the outputs of
the Runge-Kutta family exactly, thus inheriting their proven good properties.
Remaining degrees of freedom not identified by the match to Runge-Kutta are
chosen such that the posterior probability measure fits the observed structure
of the ODE. Our results shed light on the structure of Runge-Kutta solvers from
a new direction, provide a richer, probabilistic output, have low computational
cost, and raise new research questions.
Median Selection Subset Aggregation for Parallel Inference
Authors: Xiangyu Wang, Peichao Peng, David Dunson
Date: 2014-10-24 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: feature selection, Model Selection, Variable Selection

For massive data sets, efficient computation commonly relies on distributed
algorithms that store and process subsets of the data on different machines,
minimizing communication costs. Our focus is on regression and classification
problems involving many features. A variety of distributed algorithms have been
proposed in this context, but challenges arise in defining an algorithm with
low communication, theoretical guarantees and excellent practical performance
in general settings. We propose a MEdian Selection Subset AGgregation Estimator
(message) algorithm, which attempts to solve these problems. The algorithm
applies feature selection in parallel for each subset using Lasso or another
method, calculates the `median' feature inclusion index, estimates coefficients
for the selected features in parallel for each subset, and then averages these
estimates. The algorithm is simple, involves very minimal communication, scales
efficiently in both sample and feature size, and has theoretical guarantees. In
particular, we show model selection consistency and coefficient estimation
efficiency. Extensive experiments show excellent performance in variable
selection, estimation, prediction, and computation time relative to usual
competitors.
A Novel Visual Word Co-occurrence Model for Person Re-identification
Authors: Ziming Zhang, Yu-Ting Chen, Venkatesh Saligrama
Date: 2014-10-24 00:00:00
Tasks: Person Re-Identification

Person re-identification aims to maintain the identity of an individual in
diverse locations through different non-overlapping camera views. The problem
is fundamentally challenging due to appearance variations resulting from
differing poses, illumination and configurations of camera views. To deal with
these difficulties, we propose a novel visual word co-occurrence model. We
first map each pixel of an image to a visual word using a codebook, which is
learned in an unsupervised manner. The appearance transformation between camera
views is encoded by a co-occurrence matrix of visual word joint distributions
in probe and gallery images. Our appearance model naturally accounts for
spatial similarities and variations caused by pose, illumination &
configuration change across camera views. Linear SVMs are then trained as
classifiers using these co-occurrence descriptors. On the VIPeR and CUHK Campus
benchmark datasets, our method achieves 83.86% and 85.49% at rank-15 on the
Cumulative Match Characteristic (CMC) curves, and beats the state-of-the-art
results by 10.44% and 22.27%.
Justifying and Improving Meta-Agent Conflict-Based Search
Authors: David Tolpin
Date: 2014-10-23 00:00:00
Tasks: Multi-Agent Path Finding

The Meta-Agent Conflict-Based Search~(MA-CBS) is a recently proposed
algorithm for the multi-agent path finding problem. The algorithm is an
extension of Conflict-Based Search~(CBS), which automatically merges
conflicting agents into meta-agents if the number of conflicts exceeds a
certain threshold. However, the decision to merge agents is made according to
an empirically chosen fixed threshold on the number of conflicts. The best
threshold depends both on the domain and on the number of agents, and the
nature of the dependence is not clearly understood.
  We suggest a justification for the use of a fixed threshold on the number of
conflicts based on the analysis of a model problem. Following the suggested
justification, we introduce new decision policies for the MA-CBS algorithm,
which considerably improve the algorithm's performance. The improved variants
of the algorithm are evaluated on several sets of problems, chosen to underline
different aspects of the algorithms.
Non-parametric Bayesian Learning with Deep Learning Structure and Its Applications in Wireless Networks
Authors: Erte Pan, Zhu Han
Date: 2014-10-16 00:00:00

In this paper, we present an infinite hierarchical non-parametric Bayesian
model to extract the hidden factors over observed data, where the number of
hidden factors for each layer is unknown and can be potentially infinite.
Moreover, the number of layers can also be infinite. We construct the model
structure that allows continuous values for the hidden factors and weights,
which makes the model suitable for various applications. We use the
Metropolis-Hastings method to infer the model structure. Then the performance
of the algorithm is evaluated by the experiments. Simulation results show that
the model fits the underlying structure of simulated data.