pwc-archive/papers-with-abstracts huggingface dataset:
Geometric lattice structure of covering and its application to attribute reduction through matroids
Authors: Aiping Huang, William Zhu
Date: 2013-12-16 00:00:00
Tasks: Attribute

The reduction of covering decision systems is an important problem in data
mining, and covering-based rough sets serve as an efficient technique to
process the problem. Geometric lattices have been widely used in many fields,
especially greedy algorithm design which plays an important role in the
reduction problems. Therefore, it is meaningful to combine coverings with
geometric lattices to solve the optimization problems. In this paper, we obtain
geometric lattices from coverings through matroids and then apply them to the
issue of attribute reduction. First, a geometric lattice structure of a
covering is constructed through transversal matroids. Then its atoms are
studied and used to describe the lattice. Second, considering that all the
closed sets of a finite matroid form a geometric lattice, we propose a
dependence space through matroids and study the attribute reduction issues of
the space, which realizes the application of geometric lattices to attribute
reduction. Furthermore, a special type of information system is taken as an
example to illustrate the application. In a word, this work points out an
interesting view, namely, geometric lattice to study the attribute reduction
issues of information systems.
Properties of phoneme N -grams across the world's language families
Authors: Taraka Rama, Lars Borin
Date: 2014-01-04 00:00:00

In this article, we investigate the properties of phoneme N-grams across half
of the world's languages. We investigate if the sizes of three different N-gram
distributions of the world's language families obey a power law. Further, the
N-gram distributions of language families parallel the sizes of the families,
which seem to obey a power law distribution. The correlation between N-gram
distributions and language family sizes improves with increasing values of N.
We applied statistical tests, originally given by physicists, to test the
hypothesis of power law fit to twelve different datasets. The study also raises
some new questions about the use of N-gram distributions in linguistic
research, which we answer by running a statistical test.
From Kernel Machines to Ensemble Learning
Authors: Chunhua Shen, Fayao Liu
Date: 2014-01-04 00:00:00
Tasks: Ensemble Learning, Translation

Ensemble methods such as boosting combine multiple learners to obtain better
prediction than could be obtained from any individual learner. Here we propose
a principled framework for directly constructing ensemble learning methods from
kernel methods. Unlike previous studies showing the equivalence between
boosting and support vector machines (SVMs), which needs a translation
procedure, we show that it is possible to design boosting-like procedure to
solve the SVM optimization problems.
  In other words, it is possible to design ensemble methods directly from SVM
without any middle procedure.
  This finding not only enables us to design new ensemble learning methods
directly from kernel methods, but also makes it possible to take advantage of
those highly-optimized fast linear SVM solvers for ensemble learning.
  We exemplify this framework for designing binary ensemble learning as well as
a new multi-class ensemble learning methods.
  Experimental results demonstrate the flexibility and usefulness of the
proposed framework.
Context-Aware Hypergraph Construction for Robust Spectral Clustering
Authors: Xi Li, Weiming Hu, Chunhua Shen, Anthony Dick, Zhongfei Zhang
Date: 2014-01-04 00:00:00
Tasks: Clustering, hypergraph partitioning

Spectral clustering is a powerful tool for unsupervised data analysis. In
this paper, we propose a context-aware hypergraph similarity measure (CAHSM),
which leads to robust spectral clustering in the case of noisy data. We
construct three types of hypergraph---the pairwise hypergraph, the
k-nearest-neighbor (kNN) hypergraph, and the high-order over-clustering
hypergraph. The pairwise hypergraph captures the pairwise similarity of data
points; the kNN hypergraph captures the neighborhood of each point; and the
clustering hypergraph encodes high-order contexts within the dataset. By
combining the affinity information from these three hypergraphs, the CAHSM
algorithm is able to explore the intrinsic topological information of the
dataset. Therefore, data clustering using CAHSM tends to be more robust.
Considering the intra-cluster compactness and the inter-cluster separability of
vertices, we further design a discriminative hypergraph partitioning criterion
(DHPC). Using both CAHSM and DHPC, a robust spectral clustering algorithm is
developed. Theoretical analysis and experimental evaluation demonstrate the
effectiveness and robustness of the proposed algorithm.
Data Smashing
Authors: Ishanu Chattopadhyay, Hod Lipson
Date: 2014-01-03 00:00:00

Investigation of the underlying physics or biology from empirical data
requires a quantifiable notion of similarity - when do two observed data sets
indicate nearly identical generating processes, and when they do not. The
discriminating characteristics to look for in data is often determined by
heuristics designed by experts, $e.g.$, distinct shapes of "folded" lightcurves
may be used as "features" to classify variable stars, while determination of
pathological brain states might require a Fourier analysis of brainwave
activity. Finding good features is non-trivial. Here, we propose a universal
solution to this problem: we delineate a principle for quantifying similarity
between sources of arbitrary data streams, without a priori knowledge, features
or training. We uncover an algebraic structure on a space of symbolic models
for quantized data, and show that such stochastic generators may be added and
uniquely inverted; and that a model and its inverse always sum to the generator
of flat white noise. Therefore, every data stream has an anti-stream: data
generated by the inverse model. Similarity between two streams, then, is the
degree to which one, when summed to the other's anti-stream, mutually
annihilates all statistical structure to noise. We call this data smashing. We
present diverse applications, including disambiguation of brainwaves pertaining
to epileptic seizures, detection of anomalous cardiac rhythms, and
classification of astronomical objects from raw photometry. In our examples,
the data smashing principle, without access to any domain knowledge, meets or
exceeds the performance of specialized algorithms tuned by domain experts.
Quantitative methods for Phylogenetic Inference in Historical Linguistics: An experimental case study of South Central Dravidian
Authors: Taraka Rama, Sudheer Kolachina, Lakshmi Bai B
Date: 2014-01-03 00:00:00

In this paper we examine the usefulness of two classes of algorithms Distance
Methods, Discrete Character Methods (Felsenstein and Felsenstein 2003) widely
used in genetics, for predicting the family relationships among a set of
related languages and therefore, diachronic language change. Applying these
algorithms to the data on the numbers of shared cognates- with-change and
changed as well as unchanged cognates for a group of six languages belonging to
a Dravidian language sub-family given in Krishnamurti et al. (1983), we
observed that the resultant phylogenetic trees are largely in agreement with
the linguistic family tree constructed using the comparative method of
reconstruction with only a few minor differences. Furthermore, we studied these
minor differences and found that they were cases of genuine ambiguity even for
a well-trained historical linguist. We evaluated the trees obtained through our
experiments using a well-defined criterion and report the results here. We
finally conclude that quantitative methods like the ones we examined are quite
useful in predicting family relationships among languages. In addition, we
conclude that a modest degree of confidence attached to the intuition that
there could indeed exist a parallelism between the processes of linguistic and
genetic change is not totally misplaced.
Sparse Signal Estimation by Maximally Sparse Convex Optimization
Authors: Ivan W. Selesnick, Ilker Bayram
Date: 2013-02-22 00:00:00

This paper addresses the problem of sparsity penalized least squares for
applications in sparse signal processing, e.g. sparse deconvolution. This paper
aims to induce sparsity more strongly than L1 norm regularization, while
avoiding non-convex optimization. For this purpose, this paper describes the
design and use of non-convex penalty functions (regularizers) constrained so as
to ensure the convexity of the total cost function, F, to be minimized. The
method is based on parametric penalty functions, the parameters of which are
constrained to ensure convexity of F. It is shown that optimal parameters can
be obtained by semidefinite programming (SDP). This maximally sparse convex
(MSC) approach yields maximally non-convex sparsity-inducing penalty functions
constrained such that the total cost function, F, is convex. It is demonstrated
that iterative MSC (IMSC) can yield solutions substantially more sparse than
the standard convex sparsity-inducing approach, i.e., L1 norm minimization.
A type theoretical framework for natural language semantics: the Montagovian generative lexicon
Authors: Christian Retoré
Date: 2013-01-21 00:00:00

We present a framework, named the Montagovian generative lexicon, for
computing the semantics of natural language sentences, expressed in many sorted
higher order logic. Word meaning is depicted by lambda terms of second order
lambda calculus (Girard's system F) with base types including a type for
propositions and many types for sorts of a many sorted logic. This framework is
able to integrate a proper treatment of lexical phenomena into a Montagovian
compositional semantics, including the restriction of selection which imposes
the nature of the arguments of a predicate, and the possible adaptation of a
word meaning to some contexts. Among these adaptations of a word's sense to the
context, ontological inclusions are handled by an extension of system F with
coercive subtyping that is introduced in the present paper. The benefits of
this framework for lexical pragmatics are illustrated on meaning transfers and
coercions, on possible and impossible copredication over different senses, on
deverbal ambiguities, and on "fictive motion". Next we show that the
compositional treatment of determiners, quantifiers, plurals,... are finer
grained in our framework. We then conclude with the linguistic, logical and
computational perspectives opened by the Montagovian generative lexicon.
Plurals: individuals and sets in a richly typed semantics
Authors: Bruno Mery, Richard Moot, Christian Retoré
Date: 2014-01-03 00:00:00

We developed a type-theoretical framework for natural lan- guage semantics
that, in addition to the usual Montagovian treatment of compositional
semantics, includes a treatment of some phenomena of lex- ical semantic:
coercions, meaning, transfers, (in)felicitous co-predication. In this setting
we see how the various readings of plurals (collective, dis- tributive,
coverings,...) can be modelled.
Multi-Topic Multi-Document Summarizer
Authors: Fatma El-Ghannam, Tarek El-Shishtawy
Date: 2014-01-03 00:00:00
Tasks: Document Summarization, Multi-Document Summarization

Current multi-document summarization systems can successfully extract summary
sentences, however with many limitations including: low coverage, inaccurate
extraction to important sentences, redundancy and poor coherence among the
selected sentences. The present study introduces a new concept of centroid
approach and reports new techniques for extracting summary sentences for
multi-document. In both techniques keyphrases are used to weigh sentences and
documents. The first summarization technique (Sen-Rich) prefers maximum
richness sentences. While the second (Doc-Rich), prefers sentences from
centroid document. To demonstrate the new summarization system application to
extract summaries of Arabic documents we performed two experiments. First, we
applied Rouge measure to compare the new techniques among systems presented at
TAC2011. The results show that Sen-Rich outperformed all systems in ROUGE-S.
Second, the system was applied to summarize multi-topic documents. Using human
evaluators, the results show that Doc-Rich is the superior, where summary
sentences characterized by extra coverage and more cohesion.
Particle Gibbs with Ancestor Sampling
Authors: Fredrik Lindsten, Michael. I. Jordan, Thomas B. Schön
Date: 2014-01-03 00:00:00
Tasks: State Space Models

Particle Markov chain Monte Carlo (PMCMC) is a systematic way of combining
the two main tools used for Monte Carlo statistical inference: sequential Monte
Carlo (SMC) and Markov chain Monte Carlo (MCMC). We present a novel PMCMC
algorithm that we refer to as particle Gibbs with ancestor sampling (PGAS).
PGAS provides the data analyst with an off-the-shelf class of Markov kernels
that can be used to simulate the typically high-dimensional and highly
autocorrelated state trajectory in a state-space model. The ancestor sampling
procedure enables fast mixing of the PGAS kernel even when using seemingly few
particles in the underlying SMC sampler. This is important as it can
significantly reduce the computational burden that is typically associated with
using SMC. PGAS is conceptually similar to the existing PG with backward
simulation (PGBS) procedure. Instead of using separate forward and backward
sweeps as in PGBS, however, we achieve the same effect in a single forward
sweep. This makes PGAS well suited for addressing inference problems not only
in state-space models, but also in models with more complex dependencies, such
as non-Markovian, Bayesian nonparametric, and general probabilistic graphical
models.
Minimax sparse principal subspace estimation in high dimensions
Authors: Vincent Q. Vu, Jing Lei
Date: 2012-11-02 00:00:00
Tasks: Vocal Bursts Intensity Prediction

We study sparse principal components analysis in high dimensions, where $p$
(the number of variables) can be much larger than $n$ (the number of
observations), and analyze the problem of estimating the subspace spanned by
the principal eigenvectors of the population covariance matrix. We introduce
two complementary notions of $\ell_q$ subspace sparsity: row sparsity and
column sparsity. We prove nonasymptotic lower and upper bounds on the minimax
subspace estimation error for $0\leq q\leq1$. The bounds are optimal for row
sparse subspaces and nearly optimal for column sparse subspaces, they apply to
general classes of covariance matrices, and they show that $\ell_q$ constrained
estimates can achieve optimal minimax rates without restrictive spiked
covariance conditions. Interestingly, the form of the rates matches known
results for sparse regression when the effective noise variance is defined
appropriately. Our proof employs a novel variational $\sin\Theta$ theorem that
may be useful in other regularized spectral estimation problems.
Adaptive-Rate Compressive Sensing Using Side Information
Authors: Garrett Warnell, Sourabh Bhattacharya, Rama Chellappa, Tamer Basar
Date: 2014-01-03 00:00:00
Tasks: Compressive Sensing

We provide two novel adaptive-rate compressive sensing (CS) strategies for
sparse, time-varying signals using side information. Our first method utilizes
extra cross-validation measurements, and the second one exploits extra
low-resolution measurements. Unlike the majority of current CS techniques, we
do not assume that we know an upper bound on the number of significant
coefficients that comprise the images in the video sequence. Instead, we use
the side information to predict the number of significant coefficients in the
signal at the next time instant. For each image in the video sequence, our
techniques specify a fixed number of spatially-multiplexed CS measurements to
acquire, and adjust this quantity from image to image. Our strategies are
developed in the specific context of background subtraction for surveillance
video, and we experimentally validate the proposed methods on real video
sequences.
More Algorithms for Provable Dictionary Learning
Authors: Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma
Date: 2014-01-03 00:00:00
Tasks: Dictionary Learning

In dictionary learning, also known as sparse coding, the algorithm is given
samples of the form $y = Ax$ where $x\in \mathbb{R}^m$ is an unknown random
sparse vector and $A$ is an unknown dictionary matrix in $\mathbb{R}^{n\times
m}$ (usually $m > n$, which is the overcomplete case). The goal is to learn $A$
and $x$. This problem has been studied in neuroscience, machine learning,
visions, and image processing. In practice it is solved by heuristic algorithms
and provable algorithms seemed hard to find. Recently, provable algorithms were
found that work if the unknown feature vector $x$ is $\sqrt{n}$-sparse or even
sparser. Spielman et al. \cite{DBLP:journals/jmlr/SpielmanWW12} did this for
dictionaries where $m=n$; Arora et al. \cite{AGM} gave an algorithm for
overcomplete ($m >n$) and incoherent matrices $A$; and Agarwal et al.
\cite{DBLP:journals/corr/AgarwalAN13} handled a similar case but with weaker
guarantees.
  This raised the problem of designing provable algorithms that allow sparsity
$\gg \sqrt{n}$ in the hidden vector $x$. The current paper designs algorithms
that allow sparsity up to $n/poly(\log n)$. It works for a class of matrices
where features are individually recoverable, a new notion identified in this
paper that may motivate further work.
  The algorithm runs in quasipolynomial time because they use limited
enumeration.
Simple Deep Random Model Ensemble
Authors: Xiao-Lei Zhang, Ji Wu
Date: 2013-05-05 00:00:00
Tasks: Clustering, Clustering Ensemble, Deep Learning, Dictionary Learning, model, Representation Learning

Representation learning and unsupervised learning are two central topics of
machine learning and signal processing. Deep learning is one of the most
effective unsupervised representation learning approach. The main contributions
of this paper to the topics are as follows. (i) We propose to view the
representative deep learning approaches as special cases of the knowledge reuse
framework of clustering ensemble. (ii) We propose to view sparse coding when
used as a feature encoder as the consensus function of clustering ensemble, and
view dictionary learning as the training process of the base clusterings of
clustering ensemble. (ii) Based on the above two views, we propose a very
simple deep learning algorithm, named deep random model ensemble (DRME). It is
a stack of random model ensembles. Each random model ensemble is a special
k-means ensemble that discards the expectation-maximization optimization of
each base k-means but only preserves the default initialization method of the
base k-means. (iv) We propose to select the most powerful representation among
the layers by applying DRME to clustering where the single-linkage is used as
the clustering algorithm. Moreover, the DRME based clustering can also detect
the number of the natural clusters accurately. Extensive experimental
comparisons with 5 representation learning methods on 19 benchmark data sets
demonstrate the effectiveness of DRME.
Learning Deep Representation Without Parameter Inference for Nonlinear Dimensionality Reduction
Authors: Xiao-Lei Zhang
Date: 2013-08-22 00:00:00
Tasks: Clustering, Dimensionality Reduction, Representation Learning

Unsupervised deep learning is one of the most powerful representation
learning techniques. Restricted Boltzman machine, sparse coding, regularized
auto-encoders, and convolutional neural networks are pioneering building blocks
of deep learning. In this paper, we propose a new building block -- distributed
random models. The proposed method is a special full implementation of the
product of experts: (i) each expert owns multiple hidden units and different
experts have different numbers of hidden units; (ii) the model of each expert
is a k-center clustering, whose k-centers are only uniformly sampled examples,
and whose output (i.e. the hidden units) is a sparse code that only the
similarity values from a few nearest neighbors are reserved. The relationship
between the pioneering building blocks, several notable research branches and
the proposed method is analyzed. Experimental results show that the proposed
deep model can learn better representations than deep belief networks and
meanwhile can train a much larger network with much less time than deep belief
networks.
Low-Complexity Particle Swarm Optimization for Time-Critical Applications
Authors: Muhammad Saqib Sohail, Muhammad Omer Bin Saeed, Syed Zeeshan Rizvi, Mobien Shoaib, Asrar Ul Haq Sheikh
Date: 2014-01-02 00:00:00
Tasks: Stochastic Optimization

Particle swam optimization (PSO) is a popular stochastic optimization method
that has found wide applications in diverse fields. However, PSO suffers from
high computational complexity and slow convergence speed. High computational
complexity hinders its use in applications that have limited power resources
while slow convergence speed makes it unsuitable for time critical
applications. In this paper, we propose two techniques to overcome these
limitations. The first technique reduces the computational complexity of PSO
while the second technique speeds up its convergence. These techniques can be
applied, either separately or in conjunction, to any existing PSO variant. The
proposed techniques are robust to the number of dimensions of the optimization
problem. Simulation results are presented for the proposed techniques applied
to the standard PSO as well as to several PSO variants. The results show that
the use of both these techniques in conjunction results in a reduction in the
number of computations required as well as faster convergence speed while
maintaining an acceptable error performance for time-critical applications.
Solving Poisson Equation by Genetic Algorithms
Authors: Khalid Jebari, Mohammed Madiafi, Abdelaziz El Moujahid
Date: 2014-01-02 00:00:00
Tasks: Form

This paper deals with a method for solving Poisson Equation (PE) based on
genetic algorithms and grammatical evolution. The method forms generations of
solutions expressed in an analytical form. Several examples of PE are tested
and in most cases the exact solution is recovered. But, when the solution
cannot be expressed in an analytical form, our method produces a satisfactory
solution with a good level of accuracy
A Hybrid NN/HMM Modeling Technique for Online Arabic Handwriting Recognition
Authors: Najiba Tagougui, Houcine Boubaker, Monji Kherallah, Adel M. ALIMI
Date: 2014-01-02 00:00:00
Tasks: Handwriting Recognition

In this work we propose a hybrid NN/HMM model for online Arabic handwriting
recognition. The proposed system is based on Hidden Markov Models (HMMs) and
Multi Layer Perceptron Neural Networks (MLPNNs). The input signal is segmented
to continuous strokes called segments based on the Beta-Elliptical strategy by
inspecting the extremum points of the curvilinear velocity profile. A neural
network trained with segment level contextual information is used to extract
class character probabilities. The output of this network is decoded by HMMs to
provide character level recognition. In evaluations on the ADAB database, we
achieved 96.4% character recognition accuracy that is statistically
significantly important in comparison with character recognition accuracies
obtained from state-of-the-art online Arabic systems.8