pwc-archive/papers-with-abstracts huggingface dataset:
Clustering using Vector Membership: An Extension of the Fuzzy C-Means Algorithm
Authors: Srinjoy Ganguly, Digbalay Bose, Amit Konar
Date: 2013-12-14 00:00:00
Tasks: Clustering, Image Segmentation, Semantic Segmentation

Clustering is an important facet of explorative data mining and finds
extensive use in several fields. In this paper, we propose an extension of the
classical Fuzzy C-Means clustering algorithm. The proposed algorithm,
abbreviated as VFC, adopts a multi-dimensional membership vector for each data
point instead of the traditional, scalar membership value defined in the
original algorithm. The membership vector for each point is obtained by
considering each feature of that point separately and obtaining individual
membership values for the same. We also propose an algorithm to efficiently
allocate the initial cluster centers close to the actual centers, so as to
facilitate rapid convergence. Further, we propose a scheme to achieve crisp
clustering using the VFC algorithm. The proposed, novel clustering scheme has
been tested on two standard data sets in order to analyze its performance. We
also examine the efficacy of the proposed scheme by analyzing its performance
on image segmentation examples and comparing it with the classical Fuzzy
C-means clustering algorithm.
Closed-set lattice of regular sets based on a serial and transitive relation through matroids
Authors: Qingyin Li, William Zhu
Date: 2012-09-25 00:00:00
Tasks: All, Relation

Rough sets are efficient for data pre-processing in data mining. Matroids are
based on linear algebra and graph theory, and have a variety of applications in
many fields. Both rough sets and matroids are closely related to lattices. For
a serial and transitive relation on a universe, the collection of all the
regular sets of the generalized rough set is a lattice. In this paper, we use
the lattice to construct a matroid and then study relationships between the
lattice and the closed-set lattice of the matroid. First, the collection of all
the regular sets based on a serial and transitive relation is proved to be a
semimodular lattice. Then, a matroid is constructed through the height function
of the semimodular lattice. Finally, we propose an approach to obtain all the
closed sets of the matroid from the semimodular lattice. Borrowing from
matroids, results show that lattice theory provides an interesting view to
investigate rough sets.
CACO : Competitive Ant Colony Optimization, A Nature-Inspired Metaheuristic For Large-Scale Global Optimization
Authors: M. A. El-Dosuky
Date: 2013-12-14 00:00:00
Tasks: global-optimization

Large-scale problems are nonlinear problems that need metaheuristics, or
global optimization algorithms. This paper reviews nature-inspired
metaheuristics, then it introduces a framework named Competitive Ant Colony
Optimization inspired by the chemical communications among insects. Then a case
study is presented to investigate the proposed framework for large-scale global
optimization.
Identifying Influential Entries in a Matrix
Authors: Abhisek Kundu, Srinivas Nambirajan, Petros Drineas
Date: 2013-10-14 00:00:00
Tasks: Matrix Completion

For any matrix A in R^(m x n) of rank \rho, we present a probability
distribution over the entries of A (the element-wise leverage scores of
equation (2)) that reveals the most influential entries in the matrix. From a
theoretical perspective, we prove that sampling at most s = O ((m + n) \rho^2
ln (m + n)) entries of the matrix (see eqn. (3) for the precise value of s)
with respect to these scores and solving the nuclear norm minimization problem
on the sampled entries, reconstructs A exactly. To the best of our knowledge,
these are the strongest theoretical guarantees on matrix completion without any
incoherence assumptions on the matrix A. From an experimental perspective, we
show that entries corresponding to high element-wise leverage scores reveal
structural properties of the data matrix that are of interest to domain
scientists.
Achieving Fully Proportional Representation: Approximability Results
Authors: Piotr Skowron, Piotr Faliszewski, Arkadii Slinko
Date: 2013-12-14 00:00:00

We study the complexity of (approximate) winner determination under the
Monroe and Chamberlin--Courant multiwinner voting rules, which determine the
set of representatives by optimizing the total (dis)satisfaction of the voters
with their representatives. The total (dis)satisfaction is calculated either as
the sum of individual (dis)satisfactions (the utilitarian case) or as the
(dis)satisfaction of the worst off voter (the egalitarian case). We provide
good approximation algorithms for the satisfaction-based utilitarian versions
of the Monroe and Chamberlin--Courant rules, and inapproximability results for
the dissatisfaction-based utilitarian versions of them and also for all
egalitarian cases. Our algorithms are applicable and particularly appealing
when voters submit truncated ballots. We provide experimental evaluation of the
algorithms both on real-life preference-aggregation data and on synthetic data.
These experiments show that our simple and fast algorithms can in many cases
find near-perfect solutions.
High-Dimensional Covariance Decomposition into Sparse Markov and Independence Models
Authors: Majid Janzamin, Animashree Anandkumar
Date: 2012-11-05 00:00:00
Tasks: Vocal Bursts Intensity Prediction

Fitting high-dimensional data involves a delicate tradeoff between faithful
representation and the use of sparse models. Too often, sparsity assumptions on
the fitted model are too restrictive to provide a faithful representation of
the observed data. In this paper, we present a novel framework incorporating
sparsity in different domains.We decompose the observed covariance matrix into
a sparse Gaussian Markov model (with a sparse precision matrix) and a sparse
independence model (with a sparse covariance matrix). Our framework
incorporates sparse covariance and sparse precision estimation as special cases
and thus introduces a richer class of high-dimensional models. We characterize
sufficient conditions for identifiability of the two models, \viz Markov and
independence models. We propose an efficient decomposition method based on a
modification of the popular $\ell_1$-penalized maximum-likelihood estimator
($\ell_1$-MLE). We establish that our estimator is consistent in both the
domains, i.e., it successfully recovers the supports of both Markov and
independence models, when the number of samples $n$ scales as $n = \Omega(d^2
\log p)$, where $p$ is the number of variables and $d$ is the maximum node
degree in the Markov model. Our experiments validate these results and also
demonstrate that our models have better inference accuracy under simple
algorithms such as loopy belief propagation.
ECOC-Based Training of Neural Networks for Face Recognition
Authors: Nima Hatami, Reza Ebrahimpour, Reza Ghaderi
Date: 2013-12-14 00:00:00
Tasks: Classification, Face Recognition, General Classification

Error Correcting Output Codes, ECOC, is an output representation method capable of discovering some of the errors produced in classification tasks. This paper describes the application of ECOC to the training of feed forward neural networks, FFNN, for improving the overall accuracy of classification systems. Indeed, to improve the generalization of FFNN classifiers, this paper proposes an ECOC-Based training method for Neural Networks that use ECOC as the output representation, and adopts the traditional Back-Propagation algorithm, BP, to adjust weights of the network. Experimental results for face recognition problem on Yale database demonstrate the effectiveness of our method. With a rejection scheme defined by a simple robustness rate, high reliability is achieved in this application.
Classifiers With a Reject Option for Early Time-Series Classification
Authors: Nima Hatami, Camelia Chira
Date: 2013-12-14 00:00:00
Tasks: Classification, Decision Making, Early  Classification, General Classification, Time Series, Time Series Analysis, Time Series Classification

Early classification of time-series data in a dynamic environment is a
challenging problem of great importance in signal processing. This paper
proposes a classifier architecture with a reject option capable of online
decision making without the need to wait for the entire time series signal to
be present. The main idea is to classify an odor/gas signal with an acceptable
accuracy as early as possible. Instead of using posterior probability of a
classifier, the proposed method uses the "agreement" of an ensemble to decide
whether to accept or reject the candidate label. The introduced algorithm is
applied to the bio-chemistry problem of odor classification to build a novel
Electronic-Nose called Forefront-Nose. Experimental results on wind tunnel
test-bed facility confirms the robustness of the forefront-nose compared to the
standard classifiers from both earliness and recognition perspectives.
Balancing bike sharing systems (BBSS): instance generation from the CitiBike NYC data
Authors: Tommaso Urli
Date: 2013-12-13 00:00:00

Bike sharing systems are a very popular means to provide bikes to citizens in
a simple and cheap way. The idea is to install bike stations at various points
in the city, from which a registered user can easily loan a bike by removing it
from a specialized rack. After the ride, the user may return the bike at any
station (if there is a free rack). Services of this kind are mainly public or
semi-public, often aimed at increasing the attractiveness of non-motorized
means of transportation, and are usually free, or almost free, of charge for
the users. Depending on their location, bike stations have specific patterns
regarding when they are empty or full. For instance, in cities where most jobs
are located near the city centre, the commuters cause certain peaks in the
morning: the central bike stations are filled, while the stations in the
outskirts are emptied. Furthermore, stations located on top of a hill are more
likely to be empty, since users are less keen on cycling uphill to return the
bike, and often leave their bike at a more reachable station. These issues
result in substantial user dissatisfaction which may eventually cause the users
to abandon the service. This is why nowadays most bike sharing system providers
take measures to rebalance them. Over the last few years, balancing bike
sharing systems (BBSS) has become increasingly studied in optimization. As
such, generating meaningful instance to serve as a benchmark for the proposed
approaches is an important task. In this technical report we describe the
procedure we used to generate BBSS problem instances from data of the CitiBike
NYC bike sharing system.
An Extensive Evaluation of Filtering Misclassified Instances in Supervised Classification Tasks
Authors: Michael R. Smith, Tony Martinez
Date: 2013-12-13 00:00:00
Tasks: General Classification

Removing or filtering outliers and mislabeled instances prior to training a
learning algorithm has been shown to increase classification accuracy. A
popular approach for handling outliers and mislabeled instances is to remove
any instance that is misclassified by a learning algorithm. However, an
examination of which learning algorithms to use for filtering as well as their
effects on multiple learning algorithms over a large set of data sets has not
been done. Previous work has generally been limited due to the large
computational requirements to run such an experiment, and, thus, the
examination has generally been limited to learning algorithms that are
computationally inexpensive and using a small number of data sets. In this
paper, we examine 9 learning algorithms as filtering algorithms as well as
examining the effects of filtering in the 9 chosen learning algorithms on a set
of 54 data sets. In addition to using each learning algorithm individually as a
filter, we also use the set of learning algorithms as an ensemble filter and
use an adaptive algorithm that selects a subset of the learning algorithms for
filtering for a specific task and learning algorithm. We find that for most
cases, using an ensemble of learning algorithms for filtering produces the
greatest increase in classification accuracy. We also compare filtering with a
majority voting ensemble. The voting ensemble significantly outperforms
filtering unless there are high amounts of noise present in the data set.
Additionally, we find that a majority voting ensemble is robust to noise as
filtering with a voting ensemble does not increase the classification accuracy
of the voting ensemble.
Efficient coordinate-descent for orthogonal matrices through Givens rotations
Authors: Uri Shalit, Gal Chechik
Date: 2013-12-02 00:00:00
Tasks: Tensor Decomposition

Optimizing over the set of orthogonal matrices is a central component in
problems like sparse-PCA or tensor decomposition. Unfortunately, such
optimization is hard since simple operations on orthogonal matrices easily
break orthogonality, and correcting orthogonality usually costs a large amount
of computation. Here we propose a framework for optimizing orthogonal matrices,
that is the parallel of coordinate-descent in Euclidean spaces. It is based on
{\em Givens-rotations}, a fast-to-compute operation that affects a small number
of entries in the learned matrix, and preserves orthogonality. We show two
applications of this approach: an algorithm for tensor decomposition that is
used in learning mixture models, and an algorithm for sparse-PCA. We study the
parameter regime where a Givens rotation approach converges faster and achieves
a superior model on a genome-wide brain-wide mRNA expression dataset.
A Methodology for Player Modeling based on Machine Learning
Authors: Marlos C. Machado
Date: 2013-12-13 00:00:00
Tasks: BIG-bench Machine Learning, Binary Classification

AI is gradually receiving more attention as a fundamental feature to increase
the immersion in digital games. Among the several AI approaches, player
modeling is becoming an important one. The main idea is to understand and model
the player characteristics and behaviors in order to develop a better AI. In
this work, we discuss several aspects of this new field. We proposed a taxonomy
to organize the area, discussing several facets of this topic, ranging from
implementation decisions up to what a model attempts to describe. We then
classify, in our taxonomy, some of the most important works in this field. We
also presented a generic approach to deal with player modeling using ML, and we
instantiated this approach to model players' preferences in the game
Civilization IV. The instantiation of this approach has several steps. We first
discuss a generic representation, regardless of what is being modeled, and
evaluate it performing experiments with the strategy game Civilization IV.
Continuing the instantiation of the proposed approach we evaluated the
applicability of using game score information to distinguish different
preferences. We presented a characterization of virtual agents in the game,
comparing their behavior with their stated preferences. Once we have
characterized these agents, we were able to observe that different preferences
generate different behaviors, measured by several game indicators. We then
tackled the preference modeling problem as a binary classification task, with a
supervised learning approach. We compared four different methods, based on
different paradigms (SVM, AdaBoost, NaiveBayes and JRip), evaluating them on a
set of matches played by different virtual agents. We conclude our work using
the learned models to infer human players' preferences. Using some of the
evaluated classifiers we obtained accuracies over 60% for most of the inferred
preferences.
Parkinson's Disease Motor Symptoms in Machine Learning: A Review
Authors: Claas Ahlrichs, Michael Lawo
Date: 2013-12-13 00:00:00
Tasks: BIG-bench Machine Learning

This paper reviews related work and state-of-the-art publications for
recognizing motor symptoms of Parkinson's Disease (PD). It presents research
efforts that were undertaken to inform on how well traditional machine learning
algorithms can handle this task. In particular, four PD related motor symptoms
are highlighted (i.e. tremor, bradykinesia, freezing of gait and dyskinesia)
and their details summarized. Thus the primary objective of this research is to
provide a literary foundation for development and improvement of algorithms for
detecting PD related motor symptoms.
Efficient Baseline-free Sampling in Parameter Exploring Policy Gradients: Super Symmetric PGPE
Authors: Frank Sehnke
Date: 2013-12-13 00:00:00
Tasks: Policy Gradient Methods

Policy Gradient methods that explore directly in parameter space are among
the most effective and robust direct policy search methods and have drawn a lot
of attention lately. The basic method from this field, Policy Gradients with
Parameter-based Exploration, uses two samples that are symmetric around the
current hypothesis to circumvent misleading reward in \emph{asymmetrical}
reward distributed problems gathered with the usual baseline approach. The
exploration parameters are still updated by a baseline approach - leaving the
exploration prone to asymmetric reward distributions. In this paper we will
show how the exploration parameters can be sampled quasi symmetric despite
having limited instead of free parameters for exploration. We give a
transformation approximation to get quasi symmetric samples with respect to the
exploration without changing the overall sampling distribution. Finally we will
demonstrate that sampling symmetrically also for the exploration parameters is
superior in needs of samples and robustness than the original sampling
approach.
ARIANNA: pAth Recognition for Indoor Assisted NavigatioN with Augmented perception
Authors: Pierluigi Gallo, Ilenia Tinnirello, Laura Giarré, Domenico Garlisi, Daniele Croce, Adriano Fagiolini
Date: 2013-12-13 00:00:00
Tasks: Navigate

ARIANNA stands for pAth Recognition for Indoor Assisted Navigation with
Augmented perception. It is a flexible and low cost navigation system for vi-
sually impaired people. Arianna permits to navigate colored paths painted or
sticked on the floor revealing their directions through vibrational feedback on
commercial smartphones.
Consistent selection of tuning parameters via variable selection stability
Authors: Wei Sun, Junhui Wang, Yixin Fang
Date: 2012-08-16 00:00:00
Tasks: regression, Variable Selection

Penalized regression models are popularly used in high-dimensional data
analysis to conduct variable selection and model fitting simultaneously.
Whereas success has been widely reported in literature, their performances
largely depend on the tuning parameters that balance the trade-off between
model fitting and model sparsity. Existing tuning criteria mainly follow the
route of minimizing the estimated prediction error or maximizing the posterior
model probability, such as cross-validation, AIC and BIC. This article
introduces a general tuning parameter selection criterion based on a novel
concept of variable selection stability. The key idea is to select the tuning
parameters so that the resultant penalized regression model is stable in
variable selection. The asymptotic selection consistency is established for
both fixed and diverging dimensions. The effectiveness of the proposed
criterion is also demonstrated in a variety of simulated examples as well as an
application to the prostate cancer data.
A Latent Source Model for Nonparametric Time Series Classification
Authors: George H. Chen, Stanislav Nikolov, Devavrat Shah
Date: 2013-02-14 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Classification, General Classification, Time Series, Time Series Analysis, Time Series Classification

For classifying time series, a nearest-neighbor approach is widely used in
practice with performance often competitive with or better than more elaborate
methods such as neural networks, decision trees, and support vector machines.
We develop theoretical justification for the effectiveness of
nearest-neighbor-like classification of time series. Our guiding hypothesis is
that in many applications, such as forecasting which topics will become trends
on Twitter, there aren't actually that many prototypical time series to begin
with, relative to the number of time series we have access to, e.g., topics
become trends on Twitter only in a few distinct manners whereas we can collect
massive amounts of Twitter data. To operationalize this hypothesis, we propose
a latent source model for time series, which naturally leads to a "weighted
majority voting" classification rule that can be approximated by a
nearest-neighbor classifier. We establish nonasymptotic performance guarantees
of both weighted majority voting and nearest-neighbor classification under our
model accounting for how much of the time series we observe and the model
complexity. Experimental results on synthetic data show weighted majority
voting achieving the same misclassification rate as nearest-neighbor
classification while observing less of the time series. We then use weighted
majority to forecast which news topics on Twitter become trends, where we are
able to detect such "trending topics" in advance of Twitter 79% of the time,
with a mean early advantage of 1 hour and 26 minutes, a true positive rate of
95%, and a false positive rate of 4%.
Oracle Inequalities for Convex Loss Functions with Non-Linear Targets
Authors: Mehmet Caner, Anders Bredahl Kock
Date: 2013-12-12 00:00:00
Tasks: Econometrics, Variable Selection

This paper consider penalized empirical loss minimization of convex loss
functions with unknown non-linear target functions. Using the elastic net
penalty we establish a finite sample oracle inequality which bounds the loss of
our estimator from above with high probability. If the unknown target is linear
this inequality also provides an upper bound of the estimation error of the
estimated parameter vector. These are new results and they generalize the
econometrics and statistics literature. Next, we use the non-asymptotic results
to show that the excess loss of our estimator is asymptotically of the same
order as that of the oracle. If the target is linear we give sufficient
conditions for consistency of the estimated parameter vector. Next, we briefly
discuss how a thresholded version of our estimator can be used to perform
consistent variable selection. We give two examples of loss functions covered
by our framework and show how penalized nonparametric series estimation is
contained as a special case and provide a finite sample upper bound on the mean
square error of the elastic net series estimator.
A novel local search based on variable-focusing for random K-SAT
Authors: Rémi Lemoy, Mikko Alava, Erik Aurell
Date: 2013-10-09 00:00:00

We introduce a new local search algorithm for satisfiability problems. Usual
approaches focus uniformly on unsatisfied clauses. The new method works by
picking uniformly random variables in unsatisfied clauses. A Variable-based
Focused Metropolis Search (V-FMS) is then applied to random 3-SAT. We show that
it is quite comparable in performance to the clause-based FMS. Consequences for
algorithmic design are discussed.
Knowing Whether
Authors: Jie Fan, Yanjing Wang, Hans van Ditmarsch
Date: 2013-11-30 00:00:00

Knowing whether a proposition is true means knowing that it is true or
knowing that it is false. In this paper, we study logics with a modal operator
Kw for knowing whether but without a modal operator K for knowing that. This
logic is not a normal modal logic, because we do not have Kw (phi -> psi) ->
(Kw phi -> Kw psi). Knowing whether logic cannot define many common frame
properties, and its expressive power less than that of basic modal logic over
classes of models without reflexivity. These features make axiomatizing knowing
whether logics non-trivial. We axiomatize knowing whether logic over various
frame classes. We also present an extension of knowing whether logic with
public announcement operators and we give corresponding reduction axioms for
that. We compare our work in detail to two recent similar proposals.