pwc-archive/papers-with-abstracts huggingface dataset:
The Fundamental Learning Problem that Genetic Algorithms with Uniform Crossover Solve Efficiently and Repeatedly As Evolution Proceeds
Authors: Keki M. Burjorjee
Date: 2013-07-15 00:00:00
Tasks: Two-sample testing

This paper establishes theoretical bonafides for implicit concurrent
multivariate effect evaluation--implicit concurrency for short---a broad and
versatile computational learning efficiency thought to underlie
general-purpose, non-local, noise-tolerant optimization in genetic algorithms
with uniform crossover (UGAs). We demonstrate that implicit concurrency is
indeed a form of efficient learning by showing that it can be used to obtain
close-to-optimal bounds on the time and queries required to approximately
correctly solve a constrained version (k=7, \eta=1/5) of a recognizable
computational learning problem: learning parities with noisy membership
queries. We argue that a UGA that treats the noisy membership query oracle as a
fitness function can be straightforwardly used to approximately correctly learn
the essential attributes in O(log^1.585 n) queries and O(n log^1.585 n) time,
where n is the total number of attributes. Our proof relies on an accessible
symmetry argument and the use of statistical hypothesis testing to reject a
global null hypothesis at the 10^-100 level of significance. It is, to the best
of our knowledge, the first relatively rigorous identification of efficient
computational learning in an evolutionary algorithm on a non-trivial learning
problem.
Multiview Hessian Discriminative Sparse Coding for Image Annotation
Authors: Weifeng Liu, DaCheng Tao, Jun Cheng, Yuanyan Tang
Date: 2013-07-15 00:00:00
Tasks: Denoising, Image Denoising, Image Inpainting, Multiview Learning

Sparse coding represents a signal sparsely by using an overcomplete
dictionary, and obtains promising performance in practical computer vision
applications, especially for signal restoration tasks such as image denoising
and image inpainting. In recent years, many discriminative sparse coding
algorithms have been developed for classification problems, but they cannot
naturally handle visual data represented by multiview features. In addition,
existing sparse coding algorithms use graph Laplacian to model the local
geometry of the data distribution. It has been identified that Laplacian
regularization biases the solution towards a constant function which possibly
leads to poor extrapolating power. In this paper, we present multiview Hessian
discriminative sparse coding (mHDSC) which seamlessly integrates Hessian
regularization with discriminative sparse coding for multiview learning
problems. In particular, mHDSC exploits Hessian regularization to steer the
solution which varies smoothly along geodesics in the manifold, and treats the
label information as an additional view of feature for incorporating the
discriminative power for image annotation. We conduct extensive experiments on
PASCAL VOC'07 dataset and demonstrate the effectiveness of mHDSC for image
annotation.
Probabilistic inverse reinforcement learning in unknown environments
Authors: Aristide C. Y. Tossou, Christos Dimitrakakis
Date: 2013-07-14 00:00:00
Tasks: Bayesian Inference, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We consider the problem of learning by demonstration from agents acting in
unknown stochastic Markov environments or games. Our aim is to estimate agent
preferences in order to construct improved policies for the same task that the
agents are trying to solve. To do so, we extend previous probabilistic
approaches for inverse reinforcement learning in known MDPs to the case of
unknown dynamics or opponents. We do this by deriving two simplified
probabilistic models of the demonstrator's policy and utility. For
tractability, we use maximum a posteriori estimation rather than full Bayesian
inference. Under a flat prior, this results in a convex optimisation problem.
We find that the resulting algorithms are highly competitive against a variety
of other methods for inverse reinforcement learning that do have knowledge of
the dynamics.
A Minimal Six-Point Auto-Calibration Algorithm
Authors: Evgeniy Martyushev
Date: 2013-07-14 00:00:00

A non-iterative auto-calibration algorithm is presented. It deals with a
minimal set of six scene points in three views taken by a camera with fixed but
unknown intrinsic parameters. Calibration is based on the image correspondences
only. The algorithm is implemented and validated on synthetic image data.
Map of Life: Measuring and Visualizing Species' Relatedness with "Molecular Distance Maps"
Authors: Lila Kari, Kathleen A. Hill, Abu Sadat Sayem, Nathaniel Bryans, Katelyn Davis, Nikesh S. Dattani
Date: 2013-07-14 00:00:00

We propose a novel combination of methods that (i) portrays quantitative
characteristics of a DNA sequence as an image, (ii) computes distances between
these images, and (iii) uses these distances to output a map wherein each
sequence is a point in a common Euclidean space. In the resulting "Molecular
Distance Map" each point signifies a DNA sequence, and the geometric distance
between any two points reflects the degree of relatedness between the
corresponding sequences and species.
  Molecular Distance Maps present compelling visual representations of
relationships between species and could be used for taxonomic clarifications,
for species identification, and for studies of evolutionary history. One of the
advantages of this method is its general applicability since, as sequence
alignment is not required, the DNA sequences chosen for comparison can be
completely different regions in different genomes. In fact, this method can be
used to compare any two DNA sequences. For example, in our dataset of 3,176
mitochondrial DNA sequences, it correctly finds the mtDNA sequences most
closely related to that of the anatomically modern human (the Neanderthal, the
Denisovan, and the chimp), and it finds that the sequence most different from
it belongs to a cucumber. Furthermore, our method can be used to compare real
sequences to artificial, computer-generated, DNA sequences. For example, it is
used to determine that the distances between a Homo sapiens sapiens mtDNA and
artificial sequences of the same length and same trinucleotide frequencies can
be larger than the distance between the same human mtDNA and the mtDNA of a
fruit-fly.
  We demonstrate this method's promising potential for taxonomical
clarifications by applying it to a diverse variety of cases that have been
historically controversial, such as the genus Polypterus, the family Tarsiidae,
and the vast (super)kingdom Protista.
On Analyzing Estimation Errors due to Constrained Connections in Online Review Systems
Authors: Junzhou Zhao
Date: 2013-07-14 00:00:00

Constrained connection is the phenomenon that a reviewer can only review a
subset of products/services due to narrow range of interests or limited
attention capacity. In this work, we study how constrained connections can
affect estimation performance in online review systems (ORS). We find that
reviewers' constrained connections will cause poor estimation performance, both
from the measurements of estimation accuracy and Bayesian Cramer Rao lower
bound.
Online Stochastic Optimization with Multiple Objectives
Authors: Mehrdad Mahdavi, Tianbao Yang, Rong Jin
Date: 2012-11-26 00:00:00
Tasks: Stochastic Optimization

In this paper we propose a general framework to characterize and solve the
stochastic optimization problems with multiple objectives underlying many real
world learning applications. We first propose a projection based algorithm
which attains an $O(T^{-1/3})$ convergence rate. Then, by leveraging on the
theory of Lagrangian in constrained optimization, we devise a novel primal-dual
stochastic approximation algorithm which attains the optimal convergence rate
of $O(T^{-1/2})$ for general Lipschitz continuous objectives.
Computational Model of Music Sight Reading: A Reinforcement Learning Approach
Authors: Keyvan Yahya, Pouyan Rafiei Fard
Date: 2010-07-04 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Although the Music Sight Reading process has been studied from the cognitive
psychology view points, but the computational learning methods like the
Reinforcement Learning have not yet been used to modeling of such processes. In
this paper, with regards to essential properties of our specific problem, we
consider the value function concept and will indicate that the optimum policy
can be obtained by the method we offer without to be getting involved with
computing of the complex value functions. Also, we will offer a normative
behavioral model for the interaction of the agent with the musical pitch
environment and by using a slightly different version of Partially observable
Markov decision processes we will show that our method helps for faster
learning of state-action pairs in our implemented agents.
Minimum Error Rate Training and the Convex Hull Semiring
Authors: Chris Dyer
Date: 2013-07-13 00:00:00

We describe the line search used in the minimum error rate training algorithm
MERT as the "inside score" of a weighted proof forest under a semiring defined
in terms of well-understood operations from computational geometry. This
conception leads to a straightforward complexity analysis of the dynamic
programming MERT algorithms of Macherey et al. (2008) and Kumar et al. (2009)
and practical approaches to implementation.
A Data Management Approach for Dataset Selection Using Human Computation
Authors: Alexandros Ntoulas, Omar Alonso, Vasilis Kandylas
Date: 2013-07-13 00:00:00
Tasks: BIG-bench Machine Learning, Management

As the number of applications that use machine learning algorithms increases,
the need for labeled data useful for training such algorithms intensifies.
  Getting labels typically involves employing humans to do the annotation,
which directly translates to training and working costs. Crowdsourcing
platforms have made labeling cheaper and faster, but they still involve
significant costs, especially for the cases where the potential set of
candidate data to be labeled is large. In this paper we describe a methodology
and a prototype system aiming at addressing this challenge for Web-scale
problems in an industrial setting. We discuss ideas on how to efficiently
select the data to use for training of machine learning algorithms in an
attempt to reduce cost. We show results achieving good performance with reduced
cost by carefully selecting which instances to label. Our proposed algorithm is
presented as part of a framework for managing and generating training datasets,
which includes, among other components, a human computation element.
Knowledge Matters: Importance of Prior Information for Optimization
Authors: Çağlar Gülçehre, Yoshua Bengio
Date: 2013-01-17 00:00:00
Tasks: Unsupervised Pre-training

We explore the effect of introducing prior information into the intermediate
level of neural networks for a learning task on which all the state-of-the-art
machine learning algorithms tested failed to learn. We motivate our work from
the hypothesis that humans learn such intermediate concepts from other
individuals via a form of supervision or guidance using a curriculum. The
experiments we have conducted provide positive evidence in favor of this
hypothesis. In our experiments, a two-tiered MLP architecture is trained on a
dataset with 64x64 binary inputs images, each image with three sprites. The
final task is to decide whether all the sprites are the same or one of them is
different. Sprites are pentomino tetris shapes and they are placed in an image
with different locations using scaling and rotation transformations. The first
part of the two-tiered MLP is pre-trained with intermediate-level targets being
the presence of sprites at each location, while the second part takes the
output of the first part as input and predicts the final task's target binary
event. The two-tiered MLP architecture, with a few tens of thousand examples,
was able to learn the task perfectly, whereas all other algorithms (include
unsupervised pre-training, but also traditional algorithms like SVMs, decision
trees and boosting) all perform no better than chance. We hypothesize that the
optimization difficulty involved when the intermediate pre-training is not
performed is due to the {\em composition} of two highly non-linear tasks. Our
findings are also consistent with hypotheses on cultural learning inspired by
the observations of optimization problems with deep learning, presumably
because of effective local minima.
Learning an Integrated Distance Metric for Comparing Structure of Complex Networks
Authors: Sadegh Aliakbary, Sadegh Motallebi, Jafar Habibi, Ali Movaghar
Date: 2013-07-13 00:00:00
Tasks: Clustering, General Classification, Metric Learning

Graph comparison plays a major role in many network applications. We often
need a similarity metric for comparing networks according to their structural
properties. Various network features - such as degree distribution and
clustering coefficient - provide measurements for comparing networks from
different points of view, but a global and integrated distance metric is still
missing. In this paper, we employ distance metric learning algorithms in order
to construct an integrated distance metric for comparing structural properties
of complex networks. According to natural witnesses of network similarities
(such as network categories) the distance metric is learned by the means of a
dataset of some labeled real networks. For evaluating our proposed method which
is called NetDistance, we applied it as the distance metric in
K-nearest-neighbors classification. Empirical results show that NetDistance
outperforms previous methods, at least 20 percent, with respect to precision.
Improving MUC extraction thanks to local search
Authors: Éric Grégoire, Jean-Marie Lagniez, Bertrand Mazure
Date: 2013-07-12 00:00:00

ExtractingMUCs(MinimalUnsatisfiableCores)fromanunsatisfiable constraint
network is a useful process when causes of unsatisfiability must be understood
so that the network can be re-engineered and relaxed to become sat- isfiable.
Despite bad worst-case computational complexity results, various MUC- finding
approaches that appear tractable for many real-life instances have been
proposed. Many of them are based on the successive identification of so-called
transition constraints. In this respect, we show how local search can be used
to possibly extract additional transition constraints at each main iteration
step. The approach is shown to outperform a technique based on a form of model
rotation imported from the SAT-related technology and that also exhibits
additional transi- tion constraints. Our extensive computational
experimentations show that this en- hancement also boosts the performance of
state-of-the-art DC(WCORE)-like MUC extractors.
On-line Bayesian parameter estimation in general non-linear state-space models: A tutorial and new results
Authors: Aditya Tulsyan, Biao Huang, R. Bhushan Gopaluni, J. Fraser Forbes
Date: 2013-07-12 00:00:00
Tasks: Density Estimation, parameter estimation, State Space Models

On-line estimation plays an important role in process control and monitoring.
Obtaining a theoretical solution to the simultaneous state-parameter estimation
problem for non-linear stochastic systems involves solving complex
multi-dimensional integrals that are not amenable to analytical solution. While
basic sequential Monte-Carlo (SMC) or particle filtering (PF) algorithms for
simultaneous estimation exist, it is well recognized that there is a need for
making these on-line algorithms non-degenerate, fast and applicable to
processes with missing measurements. To overcome the deficiencies in
traditional algorithms, this work proposes a Bayesian approach to on-line state
and parameter estimation. Its extension to handle missing data in real-time is
also provided. The simultaneous estimation is performed by filtering an
extended vector of states and parameters using an adaptive
sequential-importance-resampling (SIR) filter with a kernel density estimation
method. The approach uses an on-line optimization algorithm based on
Kullback-Leibler (KL) divergence to allow adaptation of the SIR filter for
combined state-parameter estimation. An optimal tuning rule to control the
width of the kernel and the variance of the artificial noise added to the
parameters is also proposed. The approach is illustrated through numerical
examples.
Energy-aware adaptive bi-Lipschitz embeddings
Authors: Bubacarr Bah, Ali Sadeghian, Volkan Cevher
Date: 2013-07-12 00:00:00
Tasks: Compressive Sensing

We propose a dimensionality reducing matrix design based on training data
with constraints on its Frobenius norm and number of rows. Our design criteria
is aimed at preserving the distances between the data points in the
dimensionality reduced space as much as possible relative to their distances in
original data space. This approach can be considered as a deterministic
Bi-Lipschitz embedding of the data points. We introduce a scalable learning
algorithm, dubbed AMUSE, and provide a rigorous estimation guarantee by
leveraging game theoretic tools. We also provide a generalization
characterization of our matrix based on our sample data. We use compressive
sensing problems as an example application of our problem, where the Frobenius
norm design constraint translates into the sensing energy.
Speedy Object Detection based on Shape
Authors: Y. Jayanta Singh, Shalu Gupta
Date: 2013-07-12 00:00:00
Tasks: Object, object-detection, Object Detection

This study is a part of design of an audio system for in-house object
detection system for visually impaired, low vision personnel by birth or by an
accident or due to old age. The input of the system will be scene and output as
audio. Alert facility is provided based on severity levels of the objects
(snake, broke glass etc) and also during difficulties. The study proposed
techniques to provide speedy detection of objects based on shapes and its
scale. Features are extraction to have minimum spaces using dynamic scaling.
From a scene, clusters of objects are formed based on the scale and shape.
Searching is performed among the clusters initially based on the shape, scale,
mean cluster value and index of object(s). The minimum operation to detect the
possible shape of the object is performed. In case the object does not have a
likely matching shape, scale etc, then the several operations required for an
object detection will not perform; instead, it will declared as a new object.
In such way, this study finds a speedy way of detecting objects.
Thompson Sampling for 1-Dimensional Exponential Family Bandits
Authors: Nathaniel Korda, Emilie Kaufmann, Remi Munos
Date: 2013-07-12 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Thompson Sampling

Thompson Sampling has been demonstrated in many complex bandit models,
however the theoretical guarantees available for the parametric multi-armed
bandit are still limited to the Bernoulli case. Here we extend them by proving
asymptotic optimality of the algorithm using the Jeffreys prior for
1-dimensional exponential family bandits. Our proof builds on previous work,
but also makes extensive use of closed forms for Kullback-Leibler divergence
and Fisher information (and thus Jeffreys prior) available in an exponential
family. This allow us to give a finite time exponential concentration
inequality for posterior distributions on exponential families that may be of
interest in its own right. Moreover our analysis covers some distributions for
which no optimistic algorithm has yet been proposed, including heavy-tailed
exponential families.
Performance Analysis of Clustering Algorithms for Gene Expression Data
Authors: T. Chandrasekhar, K. Thangavel, E. Elayaraja
Date: 2013-07-12 00:00:00
Tasks: Clustering

Microarray technology is a process that allows thousands of genes
simultaneously monitor to various experimental conditions. It is used to
identify the co-expressed genes in specific cells or tissues that are actively
used to make proteins, This method is used to analysis the gene expression, an
important task in bioinformatics research. Cluster analysis of gene expression
data has proved to be a useful tool for identifying co-expressed genes,
biologically relevant groupings of genes and samples. In this paper we analysed
K-Means with Automatic Generations of Merge Factor for ISODATA- AGMFI, to group
the microarray data sets on the basic of ISODATA. AGMFI is to generate initial
values for merge and Spilt factor, maximum merge times instead of selecting
efficient values as in ISODATA. The initial seeds for each cluster were
normally chosen either sequentially or randomly. The quality of the final
clusters was found to be influenced by these initial seeds. For the real life
problems, the suitable number of clusters cannot be predicted. To overcome the
above drawback the current research focused on developing the clustering
algorithms without giving the initial number of clusters.
Unsupervised Gene Expression Data using Enhanced Clustering Method
Authors: T. Chandrasekhar, K. Thangavel, E. Elayaraja, E. N. Sathishkumar
Date: 2013-07-12 00:00:00
Tasks: Clustering, feature selection

Microarrays are made it possible to simultaneously monitor the expression
profiles of thousands of genes under various experimental conditions.
Identification of co-expressed genes and coherent patterns is the central goal
in microarray or gene expression data analysis and is an important task in
bioinformatics research. Feature selection is a process to select features
which are more informative. It is one of the important steps in knowledge
discovery. The problem is that not all features are important. Some of the
features may be redundant, and others may be irrelevant and noisy. In this work
the unsupervised Gene selection method and Enhanced Center Initialization
Algorithm (ECIA) with K-Means algorithms have been applied for clustering of
Gene Expression Data. This proposed clustering algorithm overcomes the
drawbacks in terms of specifying the optimal number of clusters and
initialization of good cluster centroids. Gene Expression Data show that could
identify compact clusters with performs well in terms of the Silhouette
Coefficients cluster measure.
Opinion Mining and Analysis: A survey
Authors: Arti Buche, Dr. M. B. Chandak, Akshay Zadgaonkar
Date: 2013-07-12 00:00:00
Tasks: Opinion Mining, Sentiment Analysis, Survey

The current research is focusing on the area of Opinion Mining also called as
sentiment analysis due to sheer volume of opinion rich web resources such as
discussion forums, review sites and blogs are available in digital form. One
important problem in sentiment analysis of product reviews is to produce
summary of opinions based on product features. We have surveyed and analyzed in
this paper, various techniques that have been developed for the key tasks of
opinion mining. We have provided an overall picture of what is involved in
developing a software system for opinion mining on the basis of our survey and
analysis.
Hierarchical Approach for Total Variation Digital Image Inpainting
Authors: S. Padmavathi, N. Archana, K. P. Soman
Date: 2012-07-16 00:00:00
Tasks: Image Inpainting

The art of recovering an image from damage in an undetectable form is known
as inpainting. The manual work of inpainting is most often a very time
consuming process. Due to digitalization of this technique, it is automatic and
faster. In this paper, after the user selects the regions to be reconstructed,
the algorithm automatically reconstruct the lost regions with the help of the
information surrounding them. The existing methods perform very well when the
region to be reconstructed is very small, but fails in proper reconstruction as
the area increases. This paper describes a Hierarchical method by which the
area to be inpainted is reduced in multiple levels and Total Variation(TV)
method is used to inpaint in each level. This algorithm gives better
performance when compared with other existing algorithms such as nearest
neighbor interpolation, Inpainting through Blurring and Sobolev Inpainting.