pwc-archive/papers-with-abstracts huggingface dataset:
On the Convergence and Consistency of the Blurring Mean-Shift Process
Authors: Ting-Li Chen
Date: 2013-05-05 00:00:00

The mean-shift algorithm is a popular algorithm in computer vision and image
processing. It can also be cast as a minimum gamma-divergence estimation. In
this paper we focus on the "blurring" mean shift algorithm, which is one
version of the mean-shift process that successively blurs the dataset. The
analysis of the blurring mean-shift is relatively more complicated compared to
the nonblurring version, yet the algorithm convergence and the estimation
consistency have not been well studied in the literature. In this paper we
prove both the convergence and the consistency of the blurring mean-shift. We
also perform simulation studies to compare the efficiency of the blurring and
the nonblurring versions of the mean-shift algorithms. Our results show that
the blurring mean-shift has more efficiency.
Inverting and Visualizing Features for Object Detection
Authors: Carl Vondrick, Aditya Khosla, Tomasz Malisiewicz, Antonio Torralba
Date: 2012-12-11 00:00:00
Tasks: Object, object-detection, Object Detection

We introduce algorithms to visualize feature spaces used by object detectors.
The tools in this paper allow a human to put on `HOG goggles' and perceive the
visual world as a HOG based object detector sees it. We found that these
visualizations allow us to analyze object detection systems in new ways and
gain new insight into the detector's failures. For example, when we visualize
the features for high scoring false alarms, we discovered that, although they
are clearly wrong in image space, they do look deceptively similar to true
positives in feature space. This result suggests that many of these false
alarms are caused by our choice of feature space, and indicates that creating a
better learning algorithm or building bigger datasets is unlikely to correct
these errors. By visualizing feature spaces, we can gain a more intuitive
understanding of our detection systems.
Efficient Estimation of the number of neighbours in Probabilistic K Nearest Neighbour Classification
Authors: Ji Won Yoon, Nial Friel
Date: 2013-05-05 00:00:00
Tasks: Classification, Decision Making, General Classification, Model Selection

Probabilistic k-nearest neighbour (PKNN) classification has been introduced
to improve the performance of original k-nearest neighbour (KNN) classification
algorithm by explicitly modelling uncertainty in the classification of each
feature vector. However, an issue common to both KNN and PKNN is to select the
optimal number of neighbours, $k$. The contribution of this paper is to
incorporate the uncertainty in $k$ into the decision making, and in so doing
use Bayesian model averaging to provide improved classification. Indeed the
problem of assessing the uncertainty in $k$ can be viewed as one of statistical
model selection which is one of the most important technical issues in the
statistics and machine learning domain. In this paper, a new functional
approximation algorithm is proposed to reconstruct the density of the model
(order) without relying on time consuming Monte Carlo simulations. In addition,
this algorithm avoids cross validation by adopting Bayesian framework. The
performance of this algorithm yielded very good performance on several real
experimental datasets.
Forecastable Component Analysis (ForeCA)
Authors: Georg M. Goerg
Date: 2012-05-21 00:00:00
Tasks: Dimensionality Reduction, General Classification, Time Series, Time Series Analysis

I introduce Forecastable Component Analysis (ForeCA), a novel dimension
reduction technique for temporally dependent signals. Based on a new
forecastability measure, ForeCA finds an optimal transformation to separate a
multivariate time series into a forecastable and an orthogonal white noise
space. I present a converging algorithm with a fast eigenvector solution.
Applications to financial and macro-economic time series show that ForeCA can
successfully discover informative structure, which can be used for forecasting
as well as classification. The R package ForeCA
(http://cran.r-project.org/web/packages/ForeCA/index.html) accompanies this
work and is publicly available on CRAN.
A Feature Selection Method for Multivariate Performance Measures
Authors: Qi Mao, Ivor W. Tsang
Date: 2011-03-05 00:00:00
Tasks: feature selection, General Classification, Image Retrieval, Multiple Instance Learning, Retrieval, text-classification, Text Classification

Feature selection with specific multivariate performance measures is the key
to the success of many applications, such as image retrieval and text
classification. The existing feature selection methods are usually designed for
classification error. In this paper, we propose a generalized sparse
regularizer. Based on the proposed regularizer, we present a unified feature
selection framework for general loss functions. In particular, we study the
novel feature selection paradigm by optimizing multivariate performance
measures. The resultant formulation is a challenging problem for
high-dimensional data. Hence, a two-layer cutting plane algorithm is proposed
to solve this problem, and the convergence is presented. In addition, we adapt
the proposed method to optimize multivariate measures for multiple instance
learning problems. The analyses by comparing with the state-of-the-art feature
selection methods show that the proposed method is superior to others.
Extensive experiments on large-scale and high-dimensional real world datasets
show that the proposed method outperforms $l_1$-SVM and SVM-RFE when choosing a
small subset of features, and achieves significantly improved performances over
SVM$^{perf}$ in terms of $F_1$-score.
On Comparison between Evolutionary Programming Network-based Learning and Novel Evolution Strategy Algorithm-based Learning
Authors: M. A. Khayer Azad, Md. Shafiqul Islam, M. M. A. Hashem
Date: 2013-05-04 00:00:00
Tasks: Medical Diagnosis

This paper presents two different evolutionary systems - Evolutionary
Programming Network (EPNet) and Novel Evolutions Strategy (NES) Algorithm.
EPNet does both training and architecture evolution simultaneously, whereas NES
does a fixed network and only trains the network. Five mutation operators
proposed in EPNet to reflect the emphasis on evolving ANNs behaviors. Close
behavioral links between parents and their offspring are maintained by various
mutations, such as partial training and node splitting. On the other hand, NES
uses two new genetic operators - subpopulation-based max-mean arithmetical
crossover and time-variant mutation. The above-mentioned two algorithms have
been tested on a number of benchmark problems, such as the medical diagnosis
problems (breast cancer, diabetes, and heart disease). The results and the
comparison between them are also presented in this paper.
Efficient Multi-Template Learning for Structured Prediction
Authors: Qi Mao, Ivor W. Tsang
Date: 2011-03-04 00:00:00
Tasks: Dependency Parsing, Prediction, Structured Prediction

Conditional random field (CRF) and Structural Support Vector Machine
(Structural SVM) are two state-of-the-art methods for structured prediction
which captures the interdependencies among output variables. The success of
these methods is attributed to the fact that their discriminative models are
able to account for overlapping features on the whole input observations. These
features are usually generated by applying a given set of templates on labeled
data, but improper templates may lead to degraded performance. To alleviate
this issue, in this paper, we propose a novel multiple template learning
paradigm to learn structured prediction and the importance of each template
simultaneously, so that hundreds of arbitrary templates could be added into the
learning model without caution. This paradigm can be formulated as a special
multiple kernel learning problem with exponential number of constraints. Then
we introduce an efficient cutting plane algorithm to solve this problem in the
primal, and its convergence is presented. We also evaluate the proposed
learning paradigm on two widely-studied structured prediction tasks,
\emph{i.e.} sequence labeling and dependency parsing. Extensive experimental
results show that the proposed method outperforms CRFs and Structural SVMs due
to exploiting the importance of each template. Our complexity analysis and
empirical results also show that our proposed method is more efficient than
OnlineMKL on very sparse and high-dimensional data. We further extend this
paradigm for structured prediction using generalized $p$-block norm
regularization with $p>1$, and experiments show competitive performances when
$p \in [1,2)$.
Challenges on Probabilistic Modeling for Evolving Networks
Authors: Jianguo Ding, Pascal Bouvry
Date: 2013-04-30 00:00:00
Tasks: Cloud Computing, Management

With the emerging of new networks, such as wireless sensor networks, vehicle
networks, P2P networks, cloud computing, mobile Internet, or social networks,
the network dynamics and complexity expands from system design, hardware,
software, protocols, structures, integration, evolution, application, even to
business goals. Thus the dynamics and uncertainty are unavoidable
characteristics, which come from the regular network evolution and unexpected
hardware defects, unavoidable software errors, incomplete management
information and dependency relationship between the entities among the emerging
complex networks. Due to the complexity of emerging networks, it is not always
possible to build precise models in modeling and optimization (local and
global) for networks. This paper presents a survey on probabilistic modeling
for evolving networks and identifies the new challenges which emerge on the
probabilistic models and optimization strategies in the potential application
areas of network performance, network management and network security for
evolving networks.
APPLE: Approximate Path for Penalized Likelihood Estimators
Authors: Yi Yu, Yang Feng
Date: 2012-11-02 00:00:00
Tasks: parameter estimation, Variable Selection

In high-dimensional data analysis, penalized likelihood estimators are shown
to provide superior results in both variable selection and parameter
estimation. A new algorithm, APPLE, is proposed for calculating the Approximate
Path for Penalized Likelihood Estimators. Both the convex penalty (such as
LASSO) and the nonconvex penalty (such as SCAD and MCP) cases are considered.
The APPLE efficiently computes the solution path for the penalized likelihood
estimator using a hybrid of the modified predictor-corrector method and the
coordinate-descent algorithm. APPLE is compared with several well-known
packages via simulation and analysis of two gene expression data sets.
Geometrical complexity of data approximators
Authors: E. M. Mirkes, A. Zinovyev, A. N. Gorban
Date: 2013-02-11 00:00:00

There are many methods developed to approximate a cloud of vectors embedded
in high-dimensional space by simpler objects: starting from principal points
and linear manifolds to self-organizing maps, neural gas, elastic maps, various
types of principal curves and principal trees, and so on. For each type of
approximators the measure of the approximator complexity was developed too.
These measures are necessary to find the balance between accuracy and
complexity and to define the optimal approximations of a given type. We propose
a measure of complexity (geometrical complexity) which is applicable to
approximators of several types and which allows comparing data approximations
of different types.
Inference in Kingman's Coalescent with Particle Markov Chain Monte Carlo Method
Authors: Yifei Chen, Xiaohui Xie
Date: 2013-05-03 00:00:00
Tasks: parameter estimation

We propose a new algorithm to do posterior sampling of Kingman's coalescent,
based upon the Particle Markov Chain Monte Carlo methodology. Specifically, the
algorithm is an instantiation of the Particle Gibbs Sampling method, which
alternately samples coalescent times conditioned on coalescent tree structures,
and tree structures conditioned on coalescent times via the conditional
Sequential Monte Carlo procedure. We implement our algorithm as a C++ package,
and demonstrate its utility via a parameter estimation task in population
genetics on both single- and multiple-locus data. The experiment results show
that the proposed algorithm performs comparable to or better than several
well-developed methods.
Group theory, group actions, evolutionary algorithms, and global optimization
Authors: Andrew Clark
Date: 2012-12-27 00:00:00
Tasks: Evolutionary Algorithms, global-optimization

In this paper we use group, action and orbit to understand how evolutionary
solve nonconvex optimization problems.
Learning from Imprecise and Fuzzy Observations: Data Disambiguation through Generalized Loss Minimization
Authors: Eyke Hüllermeier
Date: 2013-05-03 00:00:00
Tasks: Binary Classification, General Classification, Inductive Bias, regression

Methods for analyzing or learning from "fuzzy data" have attracted increasing
attention in recent years. In many cases, however, existing methods (for
precise, non-fuzzy data) are extended to the fuzzy case in an ad-hoc manner,
and without carefully considering the interpretation of a fuzzy set when being
used for modeling data. Distinguishing between an ontic and an epistemic
interpretation of fuzzy set-valued data, and focusing on the latter, we argue
that a "fuzzification" of learning algorithms based on an application of the
generic extension principle is not appropriate. In fact, the extension
principle fails to properly exploit the inductive bias underlying statistical
and machine learning methods, although this bias, at least in principle, offers
a means for "disambiguating" the fuzzy data. Alternatively, we therefore
propose a method which is based on the generalization of loss functions in
empirical risk minimization, and which performs model identification and data
disambiguation simultaneously. Elaborating on the fuzzification of specific
types of losses, we establish connections to well-known loss functions in
regression and classification. We compare our approach with related methods and
illustrate its use in logistic regression for binary classification.
Feature Selection Based on Term Frequency and T-Test for Text Categorization
Authors: Deqing Wang, HUI ZHANG, Rui Liu, Weifeng Lv
Date: 2013-05-03 00:00:00
Tasks: Diversity, feature selection, Text Categorization

Much work has been done on feature selection. Existing methods are based on
document frequency, such as Chi-Square Statistic, Information Gain etc.
However, these methods have two shortcomings: one is that they are not reliable
for low-frequency terms, and the other is that they only count whether one term
occurs in a document and ignore the term frequency. Actually, high-frequency
terms within a specific category are often regards as discriminators.
  This paper focuses on how to construct the feature selection function based
on term frequency, and proposes a new approach based on $t$-test, which is used
to measure the diversity of the distributions of a term between the specific
category and the entire corpus. Extensive comparative experiments on two text
corpora using three classifiers show that our new approach is comparable to or
or slightly better than the state-of-the-art feature selection methods (i.e.,
$\chi^2$, and IG) in terms of macro-$F_1$ and micro-$F_1$.
Anisotropic oracle inequalities in noisy quantization
Authors: Sébastien Loustau
Date: 2013-05-03 00:00:00
Tasks: Clustering, Quantization

The effect of errors in variables in quantization is investigated. We prove
general exact and non-exact oracle inequalities with fast rates for an
empirical minimization based on a noisy sample
$Z_i=X_i+\epsilon_i,i=1,\ldots,n$, where $X_i$ are i.i.d. with density $f$ and
$\epsilon_i$ are i.i.d. with density $\eta$. These rates depend on the geometry
of the density $f$ and the asymptotic behaviour of the characteristic function
of $\eta$.
  This general study can be applied to the problem of $k$-means clustering with
noisy data. For this purpose, we introduce a deconvolution $k$-means stochastic
minimization which reaches fast rates of convergence under standard Pollard's
regularity assumptions.
An Improved EM algorithm
Authors: Fu-qiang Chen
Date: 2013-05-03 00:00:00
Tasks: Sensitivity

In this paper, we firstly give a brief introduction of expectation
maximization (EM) algorithm, and then discuss the initial value sensitivity of
expectation maximization algorithm. Subsequently, we give a short proof of EM's
convergence. Then, we implement experiments with the expectation maximization
algorithm (We implement all the experiments on Gaussion mixture model (GMM)).
Our experiment with expectation maximization is performed in the following
three cases: initialize randomly; initialize with result of K-means; initialize
with result of K-medoids. The experiment result shows that expectation
maximization algorithm depend on its initial state or parameters. And we found
that EM initialized with K-medoids performed better than both the one
initialized with K-means and the one initialized randomly.
CONATION: English Command Input/Output System for Computers
Authors: Kamlesh Sharma, Dr. T. V. Prasad
Date: 2013-05-03 00:00:00
Tasks: speech-recognition, Speech Recognition

In this information technology age, a convenient and user friendly interface
is required to operate the computer system on very fast rate. In the human
being, speech being a natural mode of communication has potential to being a
fast and convenient mode of interaction with computer. Speech recognition will
play an important role in taking technology to them. It is the need of this era
to access the information within seconds. This paper describes the design and
development of speaker independent and English command interpreted system for
computers. HMM model is used to represent the phoneme like speech commands.
Experiments have been done on real world data and system has been trained in
normal condition for real world subject.
Mixed LICORS: A Nonparametric Algorithm for Predictive State Reconstruction
Authors: Georg M. Goerg, Cosma Rohilla Shalizi
Date: 2012-11-15 00:00:00
Tasks: Clustering

We introduce 'mixed LICORS', an algorithm for learning nonlinear,
high-dimensional dynamics from spatio-temporal data, suitable for both
prediction and simulation. Mixed LICORS extends the recent LICORS algorithm
(Goerg and Shalizi, 2012) from hard clustering of predictive distributions to a
non-parametric, EM-like soft clustering. This retains the asymptotic predictive
optimality of LICORS, but, as we show in simulations, greatly improves
out-of-sample forecasts with limited data. The new method is implemented in the
publicly-available R package "LICORS"
(http://cran.r-project.org/web/packages/LICORS/).
Backdoors to Normality for Disjunctive Logic Programs
Authors: Johannes Klaus Fichte, Stefan Szeider
Date: 2013-01-08 00:00:00

Over the last two decades, propositional satisfiability (SAT) has become one
of the most successful and widely applied techniques for the solution of
NP-complete problems. The aim of this paper is to investigate theoretically how
Sat can be utilized for the efficient solution of problems that are harder than
NP or co-NP. In particular, we consider the fundamental reasoning problems in
propositional disjunctive answer set programming (ASP), Brave Reasoning and
Skeptical Reasoning, which ask whether a given atom is contained in at least
one or in all answer sets, respectively. Both problems are located at the
second level of the Polynomial Hierarchy and thus assumed to be harder than NP
or co-NP. One cannot transform these two reasoning problems into SAT in
polynomial time, unless the Polynomial Hierarchy collapses. We show that
certain structural aspects of disjunctive logic programs can be utilized to
break through this complexity barrier, using new techniques from Parameterized
Complexity. In particular, we exhibit transformations from Brave and Skeptical
Reasoning to SAT that run in time O(2^k n^2) where k is a structural parameter
of the instance and n the input size. In other words, the reduction is
fixed-parameter tractable for parameter k. As the parameter k we take the size
of a smallest backdoor with respect to the class of normal (i.e.,
disjunction-free) programs. Such a backdoor is a set of atoms that when deleted
makes the program normal. In consequence, the combinatorial explosion, which is
expected when transforming a problem from the second level of the Polynomial
Hierarchy to the first level, can now be confined to the parameter k, while the
running time of the reduction is polynomial in the input size n, where the
order of the polynomial is independent of k.
Lower Complexity Bounds for Lifted Inference
Authors: Manfred Jaeger
Date: 2012-04-15 00:00:00

One of the big challenges in the development of probabilistic relational (or
probabilistic logical) modeling and learning frameworks is the design of
inference techniques that operate on the level of the abstract model
representation language, rather than on the level of ground, propositional
instances of the model. Numerous approaches for such "lifted inference"
techniques have been proposed. While it has been demonstrated that these
techniques will lead to significantly more efficient inference on some specific
models, there are only very recent and still quite restricted results that show
the feasibility of lifted inference on certain syntactically defined classes of
models. Lower complexity bounds that imply some limitations for the feasibility
of lifted inference on more expressive model classes were established early on
in (Jaeger 2000). However, it is not immediate that these results also apply to
the type of modeling languages that currently receive the most attention, i.e.,
weighted, quantifier-free formulas. In this paper we extend these earlier
results, and show that under the assumption that NETIME =/= ETIME, there is no
polynomial lifted inference algorithm for knowledge bases of weighted,
quantifier- and function-free formulas. Further strengthening earlier results,
this is also shown to hold for approximate inference, and for knowledge bases
not containing the equality predicate.
Testing Hypotheses by Regularized Maximum Mean Discrepancy
Authors: Somayeh Danafar, Paola M. V. Rancoita, Tobias Glasmachers, Kevin Whittingstall, Juergen Schmidhuber
Date: 2013-05-02 00:00:00
Tasks: EEG, Electroencephalogram (EEG), Two-sample testing

Do two data samples come from different distributions? Recent studies of this
fundamental problem focused on embedding probability distributions into
sufficiently rich characteristic Reproducing Kernel Hilbert Spaces (RKHSs), to
compare distributions by the distance between their embeddings. We show that
Regularized Maximum Mean Discrepancy (RMMD), our novel measure for kernel-based
hypothesis testing, yields substantial improvements even when sample sizes are
small, and excels at hypothesis tests involving multiple comparisons with power
control. We derive asymptotic distributions under the null and alternative
hypotheses, and assess power control. Outstanding results are obtained on:
challenging EEG data, MNIST, the Berkley Covertype, and the Flare-Solar
dataset.