pwc-archive/papers-with-abstracts huggingface dataset:
From Bandits to Experts: A Tale of Domination and Independence
Authors: Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour
Date: 2013-07-17 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Multi-Armed Bandits

We consider the partial observability model for multi-armed bandits,
introduced by Mannor and Shamir. Our main result is a characterization of
regret in the directed observability model in terms of the dominating and
independence numbers of the observability graph. We also show that in the
undirected case, the learner can achieve optimal regret without even accessing
the observability graph before selecting an action. Both results are shown
using variants of the Exp3 algorithm operating on the observability graph in a
time-efficient manner.
Mammogram Edge Detection Using Hybrid Soft Computing Methods
Authors: I. Laurence Aroquiaraj, K. Thangavel
Date: 2013-07-17 00:00:00
Tasks: Edge Detection, Image Segmentation, Segmentation, Semantic Segmentation

Image segmentation is a crucial step in a wide range of method image
processing systems. It is useful in visualization of the different objects
present in the image. In spite of the several methods available in the
literature, image segmentation still a challenging problem in most of image
processing applications. The challenge comes from the fuzziness of image
objects and the overlapping of the different regions. Detection of edges in an
image is a very important step towards understanding image features. There are
large numbers of edge detection operators available, each designed to be
sensitive to certain types of edges. The Quality of edge detection can be
measured from several criteria objectively. Some criteria are proposed in terms
of mathematical measurement, some of them are based on application and
implementation requirements. Since edges often occur at image locations
representing object boundaries, edge detection is extensively used in image
segmentation when images are divided into areas corresponding to different
objects. This can be used specifically for enhancing the tumor area in
mammographic images. Different methods are available for edge detection like
Roberts, Sobel, Prewitt, Canny, Log edge operators. In this paper a novel
algorithms for edge detection has been proposed for mammographic images. Breast
boundary, pectoral region and tumor location can be seen clearly by using this
method. For comparison purpose Roberts, Sobel, Prewitt, Canny, Log edge
operators are used and their results are displayed. Experimental results
demonstrate the effectiveness of the proposed approach.
The performance of orthogonal multi-matching pursuit under RIP
Authors: Zhiqiang Xu
Date: 2012-10-19 00:00:00

The orthogonal multi-matching pursuit (OMMP) is a natural extension of
orthogonal matching pursuit (OMP). We denote the OMMP with the parameter $M$ as
OMMP(M) where $M\geq 1$ is an integer. The main difference between OMP and
OMMP(M) is that OMMP(M) selects $M$ atoms per iteration, while OMP only adds
one atom to the optimal atom set. In this paper, we study the performance of
orthogonal multi-matching pursuit (OMMP) under RIP. In particular, we show
that, when the measurement matrix A satisfies $(9s, 1/10)$-RIP, there exists an
absolutely constant $M_0\leq 8$ so that OMMP(M_0) can recover $s$-sparse signal
within $s$ iterations. We furthermore prove that, for slowly-decaying
$s$-sparse signal, OMMP(M) can recover s-sparse signal within $O(\frac{s}{M})$
iterations for a large class of $M$. In particular, for $M=s^a$ with $a\in
[0,1/2]$, OMMP(M) can recover slowly-decaying $s$-sparse signal within
$O(s^{1-a})$ iterations. The result implies that OMMP can reduce the
computational complexity heavily.
Universally Elevating the Phase Transition Performance of Compressed Sensing: Non-Isometric Matrices are Not Necessarily Bad Matrices
Authors: Weiyu Xu, Myung Cho
Date: 2013-07-17 00:00:00
Tasks: compressed sensing

In compressed sensing problems, $\ell_1$ minimization or Basis Pursuit was
known to have the best provable phase transition performance of recoverable
sparsity among polynomial-time algorithms. It is of great theoretical and
practical interest to find alternative polynomial-time algorithms which perform
better than $\ell_1$ minimization. \cite{Icassp reweighted l_1}, \cite{Isit
reweighted l_1}, \cite{XuScaingLaw} and \cite{iterativereweightedjournal} have
shown that a two-stage re-weighted $\ell_1$ minimization algorithm can boost
the phase transition performance for signals whose nonzero elements follow an
amplitude probability density function (pdf) $f(\cdot)$ whose $t$-th derivative
$f^{t}(0) \neq 0$ for some integer $t \geq 0$. However, for signals whose
nonzero elements are strictly suspended from zero in distribution (for example,
constant-modulus, only taking values `$+d$' or `$-d$' for some nonzero real
number $d$), no polynomial-time signal recovery algorithms were known to
provide better phase transition performance than plain $\ell_1$ minimization,
especially for dense sensing matrices. In this paper, we show that a
polynomial-time algorithm can universally elevate the phase-transition
performance of compressed sensing, compared with $\ell_1$ minimization, even
for signals with constant-modulus nonzero elements. Contrary to conventional
wisdoms that compressed sensing matrices are desired to be isometric, we show
that non-isometric matrices are not necessarily bad sensing matrices. In this
paper, we also provide a framework for recovering sparse signals when sensing
matrices are not isometric.
Veni Vidi Vici, A Three-Phase Scenario For Parameter Space Analysis in Image Analysis and Visualization
Authors: M. A. El-Dosuky
Date: 2013-07-17 00:00:00

Automatic analysis of the enormous sets of images is a critical task in life
sciences. This faces many challenges such as: algorithms are highly
parameterized, significant human input is intertwined, and lacking a standard
meta-visualization approach. This paper proposes an alternative iterative
approach for optimizing input parameters, saving time by minimizing the user
involvement, and allowing for understanding the workflow of algorithms and
discovering new ones. The main focus is on developing an interactive
visualization technique that enables users to analyze the relationships between
sampled input parameters and corresponding output. This technique is
implemented as a prototype called Veni Vidi Vici, or "I came, I saw, I
conquered." This strategy is inspired by the mathematical formulas of numbering
computable functions and is developed atop ImageJ, a scientific image
processing program. A case study is presented to investigate the proposed
framework. Finally, the paper explores some potential future issues in the
application of the proposed approach in parameter space analysis in
visualization.
Model checking coalitional games in shortage resource scenarios
Authors: Dario Della Monica, Margherita Napoli, Mimmo Parente
Date: 2013-07-17 00:00:00
Tasks: model

Verification of multi-agents systems (MAS) has been recently studied taking
into account the need of expressing resource bounds. Several logics for
specifying properties of MAS have been presented in quite a variety of
scenarios with bounded resources. In this paper, we study a different
formalism, called Priced Resource-Bounded Alternating-time Temporal Logic
(PRBATL), whose main novelty consists in moving the notion of resources from a
syntactic level (part of the formula) to a semantic one (part of the model).
This allows us to track the evolution of the resource availability along the
computations and provides us with a formalisms capable to model a number of
real-world scenarios. Two relevant aspects are the notion of global
availability of the resources on the market, that are shared by the agents, and
the notion of price of resources, depending on their availability. In a
previous work of ours, an initial step towards this new formalism was
introduced, along with an EXPTIME algorithm for the model checking problem. In
this paper we better analyze the features of the proposed formalism, also in
comparison with previous approaches. The main technical contribution is the
proof of the EXPTIME-hardness of the the model checking problem for PRBATL,
based on a reduction from the acceptance problem for Linearly-Bounded
Alternating Turing Machines. In particular, since the problem has multiple
parameters, we show two fixed-parameter reductions.
Parameterized Complexity Results for Plan Reuse
Authors: Ronald de Haan, Anna Roubíčková, Stefan Szeider
Date: 2013-07-16 00:00:00

Planning is a notoriously difficult computational problem of high worst-case
complexity. Researchers have been investing significant efforts to develop
heuristics or restrictions to make planning practically feasible. Case-based
planning is a heuristic approach where one tries to reuse previous experience
when solving similar problems in order to avoid some of the planning effort.
Plan reuse may offer an interesting alternative to plan generation in some
settings.
  We provide theoretical results that identify situations in which plan reuse
is provably tractable. We perform our analysis in the framework of
parameterized complexity, which supports a rigorous worst-case complexity
analysis that takes structural properties of the input into account in terms of
parameters. A central notion of parameterized complexity is fixed-parameter
tractability which extends the classical notion of polynomial-time tractability
by utilizing the effect of structural properties of the problem input.
  We draw a detailed map of the parameterized complexity landscape of several
variants of problems that arise in the context of case-based planning. In
particular, we consider the problem of reusing an existing plan, imposing
various restrictions in terms of parameters, such as the number of steps that
can be added to the existing plan to turn it into a solution of the planning
instance at hand.
A Lipschitz Exploration-Exploitation Scheme for Bayesian Optimization
Authors: Ali Jalali, Javad Azimi, Xiaoli Fern, Ruofei Zhang
Date: 2012-03-30 00:00:00
Tasks: Bayesian Optimization

The problem of optimizing unknown costly-to-evaluate functions has been
studied for a long time in the context of Bayesian Optimization. Algorithms in
this field aim to find the optimizer of the function by asking only a few
function evaluations at locations carefully selected based on a posterior
model. In this paper, we assume the unknown function is Lipschitz continuous.
Leveraging the Lipschitz property, we propose an algorithm with a distinct
exploration phase followed by an exploitation phase. The exploration phase aims
to select samples that shrink the search space as much as possible. The
exploitation phase then focuses on the reduced search space and selects samples
closest to the optimizer. Considering the Expected Improvement (EI) as a
baseline, we empirically show that the proposed algorithm significantly
outperforms EI.
The Fitness Level Method with Tail Bounds
Authors: Carsten Witt
Date: 2013-07-16 00:00:00

The fitness-level method, also called the method of f-based partitions, is an
intuitive and widely used technique for the running time analysis of randomized
search heuristics. It was originally defined to prove upper and lower bounds on
the expected running time. Recently, upper tail bounds were added to the
technique; however, these tail bounds only apply to running times that are at
least twice as large as the expectation.
  We remove this restriction and supplement the fitness-level method with sharp
tail bounds, including lower tails. As an exemplary application, we prove that
the running time of randomized local search on OneMax is sharply concentrated
around n ln n - 0.1159 n.
A Brief Review of Nature-Inspired Algorithms for Optimization
Authors: Iztok Fister Jr., Xin-She Yang, Iztok Fister, Janez Brest, Dušan Fister
Date: 2013-07-16 00:00:00

Swarm intelligence and bio-inspired algorithms form a hot topic in the
developments of new algorithms inspired by nature. These nature-inspired
metaheuristic algorithms can be based on swarm intelligence, biological
systems, physical and chemical systems. Therefore, these algorithms can be
called swarm-intelligence-based, bio-inspired, physics-based and
chemistry-based, depending on the sources of inspiration. Though not all of
them are efficient, a few algorithms have proved to be very efficient and thus
have become popular tools for solving real-world problems. Some algorithms are
insufficiently studied. The purpose of this review is to present a relatively
comprehensive list of all the algorithms in the literature, so as to inspire
further research.
Efficient Mixed-Norm Regularization: Algorithms and Safe Screening Methods
Authors: Jie Wang, Jun Liu, Jieping Ye
Date: 2013-07-16 00:00:00
Tasks: Sparse Learning

Sparse learning has recently received increasing attention in many areas
including machine learning, statistics, and applied mathematics. The mixed-norm
regularization based on the l1q norm with q>1 is attractive in many
applications of regression and classification in that it facilitates group
sparsity in the model. The resulting optimization problem is, however,
challenging to solve due to the inherent structure of the mixed-norm
regularization. Existing work deals with special cases with q=1, 2, infinity,
and they cannot be easily extended to the general case. In this paper, we
propose an efficient algorithm based on the accelerated gradient method for
solving the general l1q-regularized problem. One key building block of the
proposed algorithm is the l1q-regularized Euclidean projection (EP_1q). Our
theoretical analysis reveals the key properties of EP_1q and illustrates why
EP_1q for the general q is significantly more challenging to solve than the
special cases. Based on our theoretical analysis, we develop an efficient
algorithm for EP_1q by solving two zero finding problems. To further improve
the efficiency of solving large dimensional mixed-norm regularized problems, we
propose a screening method which is able to quickly identify the inactive
groups, i.e., groups that have 0 components in the solution. This may lead to
substantial reduction in the number of groups to be entered to the
optimization. An appealing feature of our screening method is that the data set
needs to be scanned only once to run the screening. Compared to that of solving
the mixed-norm regularized problems, the computational cost of our screening
test is negligible. The key of the proposed screening method is an accurate
sensitivity analysis of the dual optimal solution when the regularization
parameter varies. Experimental results demonstrate the efficiency of the
proposed algorithm.
On Nicod's Condition, Rules of Induction and the Raven Paradox
Authors: Hadi Mohasel Afshar, Peter Sunehag
Date: 2013-07-12 00:00:00

Philosophers writing about the ravens paradox often note that Nicod's
Condition (NC) holds given some set of background information, and fails to
hold against others, but rarely go any further. That is, it is usually not
explored which background information makes NC true or false. The present paper
aims to fill this gap. For us, "(objective) background knowledge" is restricted
to information that can be expressed as probability events. Any other
configuration is regarded as being subjective and a property of the a priori
probability distribution. We study NC in two specific settings. In the first
case, a complete description of some individuals is known, e.g. one knows of
each of a group of individuals whether they are black and whether they are
ravens. In the second case, the number of individuals having a particular
property is given, e.g. one knows how many ravens or how many black things
there are (in the relevant population). While some of the most famous answers
to the paradox are measure-dependent, our discussion is not restricted to any
particular probability measure. Our most interesting result is that in the
second setting, NC violates a simple kind of inductive inference (namely
projectability). Since relative to NC, this latter rule is more closely related
to, and more directly justified by our intuitive notion of inductive reasoning,
this tension makes a case against the plausibility of NC. In the end, we
suggest that the informal representation of NC may seem to be intuitively
plausible because it can easily be mistaken for reasoning by analogy.
Modified SPLICE and its Extension to Non-Stereo Data for Noise Robust Speech Recognition
Authors: D. S. Pavan Kumar, N. Vishnu Prasad, Vikas Joshi, S. Umesh
Date: 2013-07-15 00:00:00
Tasks: Robust Speech Recognition, speech-recognition, Speech Recognition

In this paper, a modification to the training process of the popular SPLICE
algorithm has been proposed for noise robust speech recognition. The
modification is based on feature correlations, and enables this stereo-based
algorithm to improve the performance in all noise conditions, especially in
unseen cases. Further, the modified framework is extended to work for
non-stereo datasets where clean and noisy training utterances, but not stereo
counterparts, are required. Finally, an MLLR-based computationally efficient
run-time noise adaptation method in SPLICE framework has been proposed. The
modified SPLICE shows 8.6% absolute improvement over SPLICE in Test C of
Aurora-2 database, and 2.93% overall. Non-stereo method shows 10.37% and 6.93%
absolute improvements over Aurora-2 and Aurora-4 baseline models respectively.
Run-time adaptation shows 9.89% absolute improvement in modified framework as
compared to SPLICE for Test C, and 4.96% overall w.r.t. standard MLLR
adaptation on HMMs.
An alternative Gospel of structure: order, composition, processes
Authors: Bob Coecke
Date: 2013-07-15 00:00:00
Tasks: Survey

We survey some basic mathematical structures, which arguably are more
primitive than the structures taught at school. These structures are orders,
with or without composition, and (symmetric) monoidal categories. We list
several `real life' incarnations of each of these. This paper also serves as an
introduction to these structures and their current and potentially future uses
in linguistics, physics and knowledge representation.
Development of a Hindi Lemmatizer
Authors: Snigdha Paul, Nisheeth Joshi, Iti Mathur
Date: 2013-05-24 00:00:00
Tasks: Lemmatization, Machine Translation, Morphological Analysis, Translation

We live in a translingual society, in order to communicate with people from
different parts of the world we need to have an expertise in their respective
languages. Learning all these languages is not at all possible; therefore we
need a mechanism which can do this task for us. Machine translators have
emerged as a tool which can perform this task. In order to develop a machine
translator we need to develop several different rules. The very first module
that comes in machine translation pipeline is morphological analysis. Stemming
and lemmatization comes under morphological analysis. In this paper we have
created a lemmatizer which generates rules for removing the affixes along with
the addition of rules for creating a proper root word.
Part of Speech Tagging of Marathi Text Using Trigram Method
Authors: Jyoti Singh, Nisheeth Joshi, Iti Mathur
Date: 2013-07-15 00:00:00
Tasks: Part-Of-Speech Tagging, POS, TAG

In this paper we present a Marathi part of speech tagger. It is a
morphologically rich language. It is spoken by the native people of
Maharashtra. The general approach used for development of tagger is statistical
using trigram Method. The main concept of trigram is to explore the most likely
POS for a token based on given information of previous two tags by calculating
probabilities to determine which is the best sequence of a tag. In this paper
we show the development of the tagger. Moreover we have also shown the
evaluation done.
Rule Based Transliteration Scheme for English to Punjabi
Authors: Deepti Bhalla, Nisheeth Joshi, Iti Mathur
Date: 2013-07-15 00:00:00
Tasks: Machine Translation, Translation, Transliteration

Machine Transliteration has come out to be an emerging and a very important
research area in the field of machine translation. Transliteration basically
aims to preserve the phonological structure of words. Proper transliteration of
name entities plays a very significant role in improving the quality of machine
translation. In this paper we are doing machine transliteration for
English-Punjabi language pair using rule based approach. We have constructed
some rules for syllabification. Syllabification is the process to extract or
separate the syllable from the words. In this we are calculating the
probabilities for name entities (Proper names and location). For those words
which do not come under the category of name entities, separate probabilities
are being calculated by using relative frequency through a statistical machine
translation toolkit known as MOSES. Using these probabilities we are
transliterating our input text from English to Punjabi.
Learning Markov networks with context-specific independences
Authors: Alejandro Edera, Federico Schlüter, Facundo Bromberg
Date: 2013-07-15 00:00:00

Learning the Markov network structure from data is a problem that has
received considerable attention in machine learning, and in many other
application fields. This work focuses on a particular approach for this purpose
called independence-based learning. Such approach guarantees the learning of
the correct structure efficiently, whenever data is sufficient for representing
the underlying distribution. However, an important issue of such approach is
that the learned structures are encoded in an undirected graph. The problem
with graphs is that they cannot encode some types of independence relations,
such as the context-specific independences. They are a particular case of
conditional independences that is true only for a certain assignment of its
conditioning set, in contrast to conditional independences that must hold for
all its assignments. In this work we present CSPC, an independence-based
algorithm for learning structures that encode context-specific independences,
and encoding them in a log-linear model, instead of a graph. The central idea
of CSPC is combining the theoretical guarantees provided by the
independence-based approach with the benefits of representing complex
structures by using features in a log-linear model. We present experiments in a
synthetic case, showing that CSPC is more accurate than the state-of-the-art IB
algorithms when the underlying distribution contains CSIs.
Bayesian Structured Prediction Using Gaussian Processes
Authors: Sebastien Bratieres, Novi Quadrianto, Zoubin Ghahramani
Date: 2013-07-15 00:00:00
Tasks: Gaussian Processes, Prediction, Structured Prediction

We introduce a conceptually novel structured prediction model, GPstruct,
which is kernelized, non-parametric and Bayesian, by design. We motivate the
model with respect to existing approaches, among others, conditional random
fields (CRFs), maximum margin Markov networks (M3N), and structured support
vector machines (SVMstruct), which embody only a subset of its properties. We
present an inference procedure based on Markov Chain Monte Carlo. The framework
can be instantiated for a wide range of structured objects such as linear
chains, trees, grids, and other general graphs. As a proof of concept, the
model is benchmarked on several natural language processing tasks and a video
gesture segmentation task involving a linear chain structure. We show
prediction accuracies for GPstruct which are comparable to or exceeding those
of CRFs and SVMstruct.