pwc-archive/papers-with-abstracts huggingface dataset:
Finding Numerical Solutions of Diophantine Equations using Ant Colony Optimization
Authors: Siby Abraham, Sugata Sanyal, Mukund Sanglikar
Date: 2013-06-04 00:00:00

The paper attempts to find numerical solutions of Diophantine equations, a
challenging problem as there are no general methods to find solutions of such
equations. It uses the metaphor of foraging habits of real ants. The ant colony
optimization based procedure starts with randomly assigned locations to a fixed
number of artificial ants. Depending upon the quality of these positions, ants
deposit pheromone at the nodes. A successor node is selected from the
topological neighborhood of each of the nodes based on this stochastic
pheromone deposit. If an ant bumps into an already encountered node, the
pheromone is updated correspondingly. A suitably defined pheromone evaporation
strategy guarantees that premature convergence does not take place. The
experimental results, which compares with those of other machine intelligence
techniques, validate the effectiveness of the proposed method.
Evolutionary optimization of an experimental apparatus
Authors: I. Geisel, K. Cordes, J. Mahnke, S. Jöllenbeck, J. Ostermann, J. Arlt, W. Ertmer, C. Klempt
Date: 2013-05-17 00:00:00

In recent decades, cold atom experiments have become increasingly complex.
While computers control most parameters, optimization is mostly done manually.
This is a time-consuming task for a high-dimensional parameter space with
unknown correlations. Here we automate this process using a genetic algorithm
based on Differential Evolution. We demonstrate that this algorithm optimizes
21 correlated parameters and that it is robust against local maxima and
experimental noise. The algorithm is flexible and easy to implement. Thus, the
presented scheme can be applied to a wide range of experimental optimization
tasks.
Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances
Authors: Marco Cuturi
Date: 2013-06-04 00:00:00
Proceeding: NeurIPS 2013
Tasks: Retrieval

Optimal transportation distances are a fundamental family of parameterized
distances for histograms. Despite their appealing theoretical properties,
excellent performance in retrieval tasks and intuitive formulation, their
computation involves the resolution of a linear program whose cost is
prohibitive whenever the histograms' dimension exceeds a few hundreds. We
propose in this work a new family of optimal transportation distances that look
at transportation problems from a maximum-entropy perspective. We smooth the
classical optimal transportation problem with an entropic regularization term,
and show that the resulting optimum is also a distance which can be computed
through Sinkhorn-Knopp's matrix scaling algorithm at a speed that is several
orders of magnitude faster than that of transportation solvers. We also report
improved performance over classical optimal transportation distances on the
MNIST benchmark problem.
First-Order Decomposition Trees
Authors: Nima Taghipour, Jesse Davis, Hendrik Blockeel
Date: 2013-06-04 00:00:00
Proceeding: NeurIPS 2013 12

Lifting attempts to speed up probabilistic inference by exploiting symmetries
in the model. Exact lifted inference methods, like their propositional
counterparts, work by recursively decomposing the model and the problem. In the
propositional case, there exist formal structures, such as decomposition trees
(dtrees), that represent such a decomposition and allow us to determine the
complexity of inference a priori. However, there is currently no equivalent
structure nor analogous complexity results for lifted inference. In this paper,
we introduce FO-dtrees, which upgrade propositional dtrees to the first-order
level. We show how these trees can characterize a lifted inference solution for
a probabilistic logical model (in terms of a sequence of lifted operations),
and make a theoretical analysis of the complexity of lifted inference in terms
of the novel notion of lifted width for the tree.
Fast Gradient-Based Inference with Continuous Latent Variable Models in Auxiliary Form
Authors: Diederik P. Kingma
Date: 2013-06-04 00:00:00
Tasks: Form

We propose a technique for increasing the efficiency of gradient-based
inference and learning in Bayesian networks with multiple layers of continuous
latent vari- ables. We show that, in many cases, it is possible to express such
models in an auxiliary form, where continuous latent variables are
conditionally deterministic given their parents and a set of independent
auxiliary variables. Variables of mod- els in this auxiliary form have much
larger Markov blankets, leading to significant speedups in gradient-based
inference, e.g. rapid mixing Hybrid Monte Carlo and efficient gradient-based
optimization. The relative efficiency is confirmed in ex- periments.
Iterated Tabu Search Algorithm for Packing Unequal Circles in a Circle
Authors: Tao Ye, Wenqi Huang, Zhipeng Lu
Date: 2013-06-04 00:00:00
Tasks: Combinatorial Optimization

This paper presents an Iterated Tabu Search algorithm (denoted by ITS-PUCC)
for solving the problem of Packing Unequal Circles in a Circle. The algorithm
exploits the continuous and combinatorial nature of the unequal circles packing
problem. It uses a continuous local optimization method to generate locally
optimal packings. Meanwhile, it builds a neighborhood structure on the set of
local minimum via two appropriate perturbation moves and integrates two
combinatorial optimization methods, Tabu Search and Iterated Local Search, to
systematically search for good local minima. Computational experiments on two
sets of widely-used test instances prove its effectiveness and efficiency. For
the first set of 46 instances coming from the famous circle packing contest and
the second set of 24 instances widely used in the literature, the algorithm is
able to discover respectively 14 and 16 better solutions than the previous
best-known records.
Fault detection system for Arabic language
Authors: Riadh Bouslimi, Houda Amraoui
Date: 2012-03-08 00:00:00
Tasks: Fault Detection

The study of natural language, especially Arabic, and mechanisms for the
implementation of automatic processing is a fascinating field of study, with
various potential applications. The importance of tools for natural language
processing is materialized by the need to have applications that can
effectively treat the vast mass of information available nowadays on electronic
forms. Among these tools, mainly driven by the necessity of a fast writing in
alignment to the actual daily life speed, our interest is on the writing
auditors. The morphological and syntactic properties of Arabic make it a
difficult language to master, and explain the lack in the processing tools for
that language. Among these properties, we can mention: the complex structure of
the Arabic word, the agglutinative nature, lack of vocalization, the
segmentation of the text, the linguistic richness, etc.
Narrative based Postdictive Reasoning for Cognitive Robotics
Authors: Manfred Eppe, Mehul Bhatt
Date: 2013-06-04 00:00:00
Tasks: Anomaly Detection, Translation

Making sense of incomplete and conflicting narrative knowledge in the
presence of abnormalities, unobservable processes, and other real world
considerations is a challenge and crucial requirement for cognitive robotics
systems. An added challenge, even when suitably specialised action languages
and reasoning systems exist, is practical integration and application within
large-scale robot control frameworks.
  In the backdrop of an autonomous wheelchair robot control task, we report on
application-driven work to realise postdiction triggered abnormality detection
and re-planning for real-time robot control: (a) Narrative-based knowledge
about the environment is obtained via a larger smart environment framework; and
(b) abnormalities are postdicted from stable-models of an answer-set program
corresponding to the robot's epistemic model. The overall reasoning is
performed in the context of an approximate epistemic action theory based
planner implemented via a translation to answer-set programming.
Using a bag of Words for Automatic Medical Image Annotation with a Latent Semantic
Authors: Riadh Bouslimi, Abir Messaoudi, Jalel Akaichi
Date: 2013-06-02 00:00:00

We present in this paper a new approach for the automatic annotation of
medical images, using the approach of "bag-of-words" to represent the visual
content of the medical image combined with text descriptors based approach
tf.idf and reduced by latent semantic to extract the co-occurrence between
terms and visual terms. A medical report is composed of a text describing a
medical image. First, we are interested to index the text and extract all
relevant terms using a thesaurus containing MeSH medical concepts. In a second
phase, the medical image is indexed while recovering areas of interest which
are invariant to change in scale, light and tilt. To annotate a new medical
image, we use the approach of "bagof-words" to recover the feature vector.
Indeed, we use the vector space model to retrieve similar medical image from
the database training. The calculation of the relevance value of an image to
the query image is based on the cosine function. We conclude with an experiment
carried out on five types of radiological imaging to evaluate the performance
of our system of medical annotation. The results showed that our approach works
better with more images from the radiology of the skull.
Information Theoretic Learning with Infinitely Divisible Kernels
Authors: Luis G. Sanchez Giraldo, Jose C. Principe
Date: 2013-01-16 00:00:00
Tasks: Metric Learning

In this paper, we develop a framework for information theoretic learning
based on infinitely divisible matrices. We formulate an entropy-like functional
on positive definite matrices based on Renyi's axiomatic definition of entropy
and examine some key properties of this functional that lead to the concept of
infinite divisibility. The proposed formulation avoids the plug in estimation
of density and brings along the representation power of reproducing kernel
Hilbert spaces. As an application example, we derive a supervised metric
learning algorithm using a matrix based analogue to conditional entropy
achieving results comparable with the state of the art.
Provable Inductive Matrix Completion
Authors: Prateek Jain, Inderjit S. Dhillon
Date: 2013-06-04 00:00:00
Tasks: Matrix Completion, Missing Labels, Movie Recommendation

Consider a movie recommendation system where apart from the ratings
information, side information such as user's age or movie's genre is also
available. Unlike standard matrix completion, in this setting one should be
able to predict inductively on new users/movies. In this paper, we study the
problem of inductive matrix completion in the exact recovery setting. That is,
we assume that the ratings matrix is generated by applying feature vectors to a
low-rank matrix and the goal is to recover back the underlying matrix.
Furthermore, we generalize the problem to that of low-rank matrix estimation
using rank-1 measurements. We study this generic problem and provide conditions
that the set of measurements should satisfy so that the alternating
minimization method (which otherwise is a non-convex method with no convergence
guarantees) is able to recover back the {\em exact} underlying low-rank matrix.
  In addition to inductive matrix completion, we show that two other low-rank
estimation problems can be studied in our framework: a) general low-rank matrix
sensing using rank-1 measurements, and b) multi-label regression with missing
labels. For both the problems, we provide novel and interesting bounds on the
number of measurements required by alternating minimization to provably
converges to the {\em exact} low-rank matrix. In particular, our analysis for
the general low rank matrix sensing problem significantly improves the required
storage and computational cost than that required by the RIP-based matrix
sensing methods \cite{RechtFP2007}. Finally, we provide empirical validation of
our approach and demonstrate that alternating minimization is able to recover
the true matrix for the above mentioned problems using a small number of
measurements.
Characterizing Truthful Multi-Armed Bandit Mechanisms
Authors: Moshe Babaioff, Yogeshwer Sharma, Aleksandrs Slivkins
Date: 2008-12-12 00:00:00

We consider a multi-round auction setting motivated by pay-per-click auctions
for Internet advertising. In each round the auctioneer selects an advertiser
and shows her ad, which is then either clicked or not. An advertiser derives
value from clicks; the value of a click is her private information. Initially,
neither the auctioneer nor the advertisers have any information about the
likelihood of clicks on the advertisements. The auctioneer's goal is to design
a (dominant strategies) truthful mechanism that (approximately) maximizes the
social welfare.
  If the advertisers bid their true private values, our problem is equivalent
to the "multi-armed bandit problem", and thus can be viewed as a strategic
version of the latter. In particular, for both problems the quality of an
algorithm can be characterized by "regret", the difference in social welfare
between the algorithm and the benchmark which always selects the same "best"
advertisement. We investigate how the design of multi-armed bandit algorithms
is affected by the restriction that the resulting mechanism must be truthful.
We find that truthful mechanisms have certain strong structural properties --
essentially, they must separate exploration from exploitation -- and they incur
much higher regret than the optimal multi-armed bandit algorithms. Moreover, we
provide a truthful mechanism which (essentially) matches our lower bound on
regret.
Revisiting the Nystrom Method for Improved Large-Scale Machine Learning
Authors: Alex Gittens, Michael W. Mahoney
Date: 2013-03-07 00:00:00
Tasks: BIG-bench Machine Learning

We reconsider randomized algorithms for the low-rank approximation of
symmetric positive semi-definite (SPSD) matrices such as Laplacian and kernel
matrices that arise in data analysis and machine learning applications. Our
main results consist of an empirical evaluation of the performance quality and
running time of sampling and projection methods on a diverse suite of SPSD
matrices. Our results highlight complementary aspects of sampling versus
projection methods; they characterize the effects of common data preprocessing
steps on the performance of these algorithms; and they point to important
differences between uniform sampling and nonuniform sampling methods based on
leverage scores. In addition, our empirical results illustrate that existing
theory is so weak that it does not provide even a qualitative guide to
practice. Thus, we complement our empirical results with a suite of worst-case
theoretical bounds for both random sampling and random projection methods.
These bounds are qualitatively superior to existing bounds---e.g. improved
additive-error bounds for spectral and Frobenius norm error and relative-error
bounds for trace norm error---and they point to future directions to make these
algorithms useful in even larger-scale machine learning applications.
On the Performance Bounds of some Policy Search Dynamic Programming Algorithms
Authors: Bruno Scherrer
Date: 2013-06-03 00:00:00

We consider the infinite-horizon discounted optimal control problem
formalized by Markov Decision Processes. We focus on Policy Search algorithms,
that compute an approximately optimal policy by following the standard Policy
Iteration (PI) scheme via an -approximate greedy operator (Kakade and Langford,
2002; Lazaric et al., 2010). We describe existing and a few new performance
bounds for Direct Policy Iteration (DPI) (Lagoudakis and Parr, 2003; Fern et
al., 2006; Lazaric et al., 2010) and Conservative Policy Iteration (CPI)
(Kakade and Langford, 2002). By paying a particular attention to the
concentrability constants involved in such guarantees, we notably argue that
the guarantee of CPI is much better than that of DPI, but this comes at the
cost of a relative--exponential in $\frac{1}{\epsilon}$-- increase of time
complexity. We then describe an algorithm, Non-Stationary Direct Policy
Iteration (NSDPI), that can either be seen as 1) a variation of Policy Search
by Dynamic Programming by Bagnell et al. (2003) to the infinite horizon
situation or 2) a simplified version of the Non-Stationary PI with growing
period of Scherrer and Lesner (2012). We provide an analysis of this algorithm,
that shows in particular that it enjoys the best of both worlds: its
performance guarantee is similar to that of CPI, but within a time complexity
similar to that of DPI.
Evolutionary Approach for the Containers Bin-Packing Problem
Authors: R. Kammarti, I. Ayachi, M. Ksouri, P. Borne
Date: 2013-06-03 00:00:00
Tasks: Combinatorial Optimization, Management, Scheduling

This paper deals with the resolution of combinatorial optimization problems,
particularly those concerning the maritime transport scheduling. We are
interested in the management platforms in a river port and more specifically in
container organisation operations with a view to minimizing the number of
container rehandlings. Subsequently, we rmeet customers delivery deadlines and
we reduce ship stoppage time In this paper, we propose a genetic algorithm to
solve this problem and we present some experiments and results.
A Description Logic Primer
Authors: Markus Krötzsch, Frantisek Simancik, Ian Horrocks
Date: 2012-01-19 00:00:00

This paper provides a self-contained first introduction to description logics
(DLs). The main concepts and features are explained with examples before syntax
and semantics of the DL SROIQ are defined in detail. Additional sections review
light-weight DL languages, discuss the relationship to the Web Ontology
Language OWL and give pointers to further reading.
The Randomized Dependence Coefficient
Authors: David Lopez-Paz, Philipp Hennig, Bernhard Schölkopf
Date: 2013-04-29 00:00:00
Proceeding: NeurIPS 2013 12

We introduce the Randomized Dependence Coefficient (RDC), a measure of
non-linear dependence between random variables of arbitrary dimension based on
the Hirschfeld-Gebelein-R\'enyi Maximum Correlation Coefficient. RDC is defined
in terms of correlation of random non-linear copula projections; it is
invariant with respect to marginal distribution transformations, has low
computational cost and is easy to implement: just five lines of R code,
included at the end of the paper.
Low-rank optimization with trace norm penalty
Authors: B. Mishra, G. Meyer, F. Bach, R. Sepulchre
Date: 2011-12-11 00:00:00
Tasks: Low-Rank Matrix Completion, Matrix Completion

The paper addresses the problem of low-rank trace norm minimization. We
propose an algorithm that alternates between fixed-rank optimization and
rank-one updates. The fixed-rank optimization is characterized by an efficient
factorization that makes the trace norm differentiable in the search space and
the computation of duality gap numerically tractable. The search space is
nonlinear but is equipped with a particular Riemannian structure that leads to
efficient computations. We present a second-order trust-region algorithm with a
guaranteed quadratic rate of convergence. Overall, the proposed optimization
scheme converges super-linearly to the global solution while maintaining
complexity that is linear in the number of rows and columns of the matrix. To
compute a set of solutions efficiently for a grid of regularization parameters
we propose a predictor-corrector approach that outperforms the naive
warm-restart approach on the fixed-rank quotient manifold. The performance of
the proposed algorithm is illustrated on problems of low-rank matrix completion
and multivariate linear regression.
Test-cost-sensitive attribute reduction of data with normal distribution measurement errors
Authors: Hong Zhao, Fan Min, William Zhu
Date: 2012-09-29 00:00:00
Tasks: Attribute, Decision Making

The measurement error with normal distribution is universal in applications.
Generally, smaller measurement error requires better instrument and higher test
cost. In decision making based on attribute values of objects, we shall select
an attribute subset with appropriate measurement error to minimize the total
test cost. Recently, error-range-based covering rough set with uniform
distribution error was proposed to investigate this issue. However, the
measurement errors satisfy normal distribution instead of uniform distribution
which is rather simple for most applications. In this paper, we introduce
normal distribution measurement errors to covering-based rough set model, and
deal with test-cost-sensitive attribute reduction problem in this new model.
The major contributions of this paper are four-fold. First, we build a new data
model based on normal distribution measurement errors. With the new data model,
the error range is an ellipse in a two-dimension space. Second, the
covering-based rough set with normal distribution measurement errors is
constructed through the "3-sigma" rule. Third, the test-cost-sensitive
attribute reduction problem is redefined on this covering-based rough set.
Fourth, a heuristic algorithm is proposed to deal with this problem. The
algorithm is tested on ten UCI (University of California - Irvine) datasets.
The experimental results show that the algorithm is more effective and
efficient than the existing one. This study is a step toward realistic
applications of cost-sensitive learning.
Minimal cost feature selection of data with normal distribution measurement errors
Authors: Hong Zhao, Fan Min, William Zhu
Date: 2012-11-12 00:00:00
Tasks: feature selection

Minimal cost feature selection is devoted to obtain a trade-off between test
costs and misclassification costs. This issue has been addressed recently on
nominal data. In this paper, we consider numerical data with measurement errors
and study minimal cost feature selection in this model. First, we build a data
model with normal distribution measurement errors. Second, the neighborhood of
each data item is constructed through the confidence interval. Comparing with
discretized intervals, neighborhoods are more reasonable to maintain the
information of data. Third, we define a new minimal total cost feature
selection problem through considering the trade-off between test costs and
misclassification costs. Fourth, we proposed a backtracking algorithm with
three effective pruning techniques to deal with this problem. The algorithm is
tested on four UCI data sets. Experimental results indicate that the pruning
techniques are effective, and the algorithm is efficient for data sets with
nearly one thousand objects.
Cost-Sensitive Feature Selection of Data with Errors
Authors: Hong Zhao, Fan Min, William Zhu
Date: 2012-12-13 00:00:00
Tasks: feature selection

In data mining applications, feature selection is an essential process since
it reduces a model's complexity. The cost of obtaining the feature values must
be taken into consideration in many domains. In this paper, we study the
cost-sensitive feature selection problem on numerical data with measurement
errors, test costs and misclassification costs. The major contributions of this
paper are four-fold. First, a new data model is built to address test costs and
misclassification costs as well as error boundaries. Second, a covering-based
rough set with measurement errors is constructed. Given a confidence interval,
the neighborhood is an ellipse in a two-dimension space, or an ellipsoidal in a
three-dimension space, etc. Third, a new cost-sensitive feature selection
problem is defined on this covering-based rough set. Fourth, both backtracking
and heuristic algorithms are proposed to deal with this new problem. The
algorithms are tested on six UCI (University of California - Irvine) data sets.
Experimental results show that (1) the pruning techniques of the backtracking
algorithm help reducing the number of operations significantly, and (2) the
heuristic algorithm usually obtains optimal results. This study is a step
toward realistic applications of cost-sensitive learning.