pwc-archive/papers-with-abstracts huggingface dataset:
Compressive Mining: Fast and Optimal Data Mining in the Compressed Domain
Authors: Michail Vlachos, Nikolaos Freris, Anastasios Kyrillidis
Date: 2014-05-22 00:00:00
Tasks: Clustering, Data Compression

Real-world data typically contain repeated and periodic patterns. This
suggests that they can be effectively represented and compressed using only a
few coefficients of an appropriate basis (e.g., Fourier, Wavelets, etc.).
However, distance estimation when the data are represented using different sets
of coefficients is still a largely unexplored area. This work studies the
optimization problems related to obtaining the \emph{tightest} lower/upper
bound on Euclidean distances when each data object is potentially compressed
using a different set of orthonormal coefficients. Our technique leads to
tighter distance estimates, which translates into more accurate search,
learning and mining operations \textit{directly} in the compressed domain.
  We formulate the problem of estimating lower/upper distance bounds as an
optimization problem. We establish the properties of optimal solutions, and
leverage the theoretical analysis to develop a fast algorithm to obtain an
\emph{exact} solution to the problem. The suggested solution provides the
tightest estimation of the $L_2$-norm or the correlation. We show that typical
data-analysis operations, such as k-NN search or k-Means clustering, can
operate more accurately using the proposed compression and distance
reconstruction technique. We compare it with many other prevalent compression
and reconstruction techniques, including random projections and PCA-based
techniques. We highlight a surprising result, namely that when the data are
highly sparse in some basis, our technique may even outperform PCA-based
compression.
  The contributions of this work are generic as our methodology is applicable
to any sequential or high-dimensional data as well as to any orthogonal data
transformation used for the underlying data compression scheme.
MotàMot project: conversion of a French-Khmer published dictionary for building a multilingual lexical system
Authors: Mathieu Mangeot
Date: 2014-05-22 00:00:00
Proceeding: LREC 2014 5

Economic issues related to the information processing techniques are very
important. The development of such technologies is a major asset for developing
countries like Cambodia and Laos, and emerging ones like Vietnam, Malaysia and
Thailand. The MotAMot project aims to computerize an under-resourced language:
Khmer, spoken mainly in Cambodia. The main goal of the project is the
development of a multilingual lexical system targeted for Khmer. The
macrostructure is a pivot one with each word sense of each language linked to a
pivot axi. The microstructure comes from a simplification of the explanatory
and combinatory dictionary. The lexical system has been initialized with data
coming mainly from the conversion of the French-Khmer bilingual dictionary of
Denis Richer from Word to XML format. The French part was completed with
pronunciation and parts-of-speech coming from the FeM French-english-Malay
dictionary. The Khmer headwords noted in IPA in the Richer dictionary were
converted to Khmer writing with OpenFST, a finite state transducer tool. The
resulting resource is available online for lookup, editing, download and remote
programming via a REST API on a Jibiki platform.
Machine Translation Model based on Non-parallel Corpus and Semi-supervised Transductive Learning
Authors: Lijiang Chen
Date: 2014-05-22 00:00:00
Tasks: Machine Translation, Transductive Learning, Translation

Although the parallel corpus has an irreplaceable role in machine
translation, its scale and coverage is still beyond the actual needs.
Non-parallel corpus resources on the web have an inestimable potential value in
machine translation and other natural language processing tasks. This article
proposes a semi-supervised transductive learning method for expanding the
training corpus in statistical machine translation system by extracting
parallel sentences from the non-parallel corpus. This method only requires a
small amount of labeled corpus and a large unlabeled corpus to build a
high-performance classifier, especially for when there is short of labeled
corpus. The experimental results show that by combining the non-parallel corpus
alignment and the semi-supervised transductive learning method, we can more
effectively use their respective strengths to improve the performance of
machine translation system.
Mathematical Programming Strategies for Solving the Minimum Common String Partition Problem
Authors: Christian Blum, José A. Lozano, Pedro Pinacho Davidson
Date: 2014-05-22 00:00:00
Tasks: Combinatorial Optimization

The minimum common string partition problem is an NP-hard combinatorial
optimization problem with applications in computational biology. In this work
we propose the first integer linear programming model for solving this problem.
Moreover, on the basis of the integer linear programming model we develop a
deterministic 2-phase heuristic which is applicable to larger problem
instances. The results show that provenly optimal solutions can be obtained for
problem instances of small and medium size from the literature by solving the
proposed integer linear programming model with CPLEX. Furthermore, new
best-known solutions are obtained for all considered problem instances from the
literature. Concerning the heuristic, we were able to show that it outperforms
heuristic competitors from the related literature.
Interactive Reference Point-Based Guided Local Search for the Bi-objective Inventory Routing Problem
Authors: Sandra Huber, Martin Josef Geiger, Marc Sevaux
Date: 2014-05-22 00:00:00
Tasks: Decision Making

Eliciting preferences of a decision maker is a key factor to successfully
combine search and decision making in an interactive method. Therefore, the
progressively integration and simulation of the decision maker is a main
concern in an application. We contribute in this direction by proposing an
interactive method based on a reference point-based guided local search to the
bi-objective Inventory Routing Problem. A local search metaheuristic, working
on the delivery intervals, and the Clarke & Wright savings heuristic is
employed for the subsequently obtained Vehicle Routing Problem. To elicit
preferences, the decision maker selects a reference point to guide the search
in interesting subregions. Additionally, the reference point is used as a
reservation point to discard solutions outside the cone, introduced as a
convergence criterion. Computational results of the reference point-based
guided local search are reported and analyzed on benchmark data in order to
show the applicability of the approach.
A Comparison of Monte Carlo Tree Search and Mathematical Optimization for Large Scale Dynamic Resource Allocation
Authors: Dimitris Bertsimas, J. Daniel Griffith, Vishal Gupta, Mykel J. Kochenderfer, Velibor V. Mišić, Robert Moss
Date: 2014-05-21 00:00:00
Tasks: Management, Stochastic Optimization

Dynamic resource allocation (DRA) problems are an important class of dynamic
stochastic optimization problems that arise in a variety of important
real-world applications. DRA problems are notoriously difficult to solve to
optimality since they frequently combine stochastic elements with intractably
large state and action spaces. Although the artificial intelligence and
operations research communities have independently proposed two successful
frameworks for solving dynamic stochastic optimization problems---Monte Carlo
tree search (MCTS) and mathematical optimization (MO), respectively---the
relative merits of these two approaches are not well understood. In this paper,
we adapt both MCTS and MO to a problem inspired by tactical wildfire and
management and undertake an extensive computational study comparing the two
methods on large scale instances in terms of both the state and the action
spaces. We show that both methods are able to greatly improve on a baseline,
problem-specific heuristic. On smaller instances, the MCTS and MO approaches
perform comparably, but the MO approach outperforms MCTS as the size of the
problem increases for a fixed computational budget.
ImageSpirit: Verbal Guided Image Parsing
Authors: Ming-Ming Cheng, Shuai Zheng, Wen-Yan Lin, Jonathan Warrell, Vibhav Vineet, Paul Sturgess, Nigel Crook, Niloy Mitra, Philip Torr
Date: 2013-10-16 00:00:00
Tasks: Attribute, Object

Humans describe images in terms of nouns and adjectives while algorithms
operate on images represented as sets of pixels. Bridging this gap between how
humans would like to access images versus their typical representation is the
goal of image parsing, which involves assigning object and attribute labels to
pixel. In this paper we propose treating nouns as object labels and adjectives
as visual attribute labels. This allows us to formulate the image parsing
problem as one of jointly estimating per-pixel object and attribute labels from
a set of training images. We propose an efficient (interactive time) solution.
Using the extracted labels as handles, our system empowers a user to verbally
refine the results. This enables hands-free parsing of an image into pixel-wise
object/attribute labels that correspond to human semantics. Verbally selecting
objects of interests enables a novel and natural interaction modality that can
possibly be used to interact with new generation devices (e.g. smart phones,
Google Glass, living room devices). We demonstrate our system on a large number
of real-world images with varying complexity. To help understand the tradeoffs
compared to traditional mouse based interactions, results are reported for both
a large scale quantitative evaluation and a user study.
New Perspectives in Sinographic Language Processing Through the Use of Character Structure
Authors: Yannis Haralambous
Date: 2014-05-21 00:00:00
Tasks: Relation, text-classification, Text Classification

Chinese characters have a complex and hierarchical graphical structure
carrying both semantic and phonetic information. We use this structure to
enhance the text model and obtain better results in standard NLP operations.
First of all, to tackle the problem of graphical variation we define
allographic classes of characters. Next, the relation of inclusion of a
subcharacter in a characters, provides us with a directed graph of allographic
classes. We provide this graph with two weights: semanticity (semantic relation
between subcharacter and character) and phoneticity (phonetic relation) and
calculate "most semantic subcharacter paths" for each character. Finally,
adding the information contained in these paths to unigrams we claim to
increase the efficiency of text mining methods. We evaluate our method on a
text classification task on two corpora (Chinese and Japanese) of a total of 18
million characters and get an improvement of 3% on an already high baseline of
89.6% precision, obtained by a linear SVM classifier. Other possible
applications and perspectives of the system are discussed.
Spectral Networks and Locally Connected Networks on Graphs
Authors: Joan Bruna, Wojciech Zaremba, Arthur Szlam, Yann Lecun
Date: 2013-12-21 00:00:00
Tasks: Clustering, Translation

Convolutional Neural Networks are extremely efficient architectures in image
and audio recognition tasks, thanks to their ability to exploit the local
translational invariance of signal classes over their domain. In this paper we
consider possible generalizations of CNNs to signals defined on more general
domains without the action of a translation group. In particular, we propose
two constructions, one based upon a hierarchical clustering of the domain, and
another based on the spectrum of the graph Laplacian. We show through
experiments that for low-dimensional graphs it is possible to learn
convolutional layers with a number of parameters independent of the input size,
resulting in efficient deep architectures.
Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations
Authors: H. Brendan McMahan, Francesco Orabona
Date: 2014-03-03 00:00:00

We study algorithms for online linear optimization in Hilbert spaces,
focusing on the case where the player is unconstrained. We develop a novel
characterization of a large class of minimax algorithms, recovering, and even
improving, several previous results as immediate corollaries. Moreover, using
our tools, we develop an algorithm that provides a regret bound of
$\mathcal{O}\Big(U \sqrt{T \log(U \sqrt{T} \log^2 T +1)}\Big)$, where $U$ is
the $L_2$ norm of an arbitrary comparator and both $T$ and $U$ are unknown to
the player. This bound is optimal up to $\sqrt{\log \log T}$ terms. When $T$ is
known, we derive an algorithm with an optimal regret bound (up to constant
factors). For both the known and unknown $T$ case, a Normal approximation to
the conditional value of the game proves to be the key analysis tool.
Projective simulation applied to the grid-world and the mountain-car problem
Authors: Alexey A. Melnikov, Adi Makmal, Hans J. Briegel
Date: 2014-05-21 00:00:00
Tasks: Benchmarking, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

We study the model of projective simulation (PS) which is a novel approach to
artificial intelligence (AI). Recently it was shown that the PS agent performs
well in a number of simple task environments, also when compared to standard
models of reinforcement learning (RL). In this paper we study the performance
of the PS agent further in more complicated scenarios. To that end we chose two
well-studied benchmarking problems, namely the "grid-world" and the
"mountain-car" problem, which challenge the model with large and continuous
input space. We compare the performance of the PS agent model with those of
existing models and show that the PS agent exhibits competitive performance
also in such scenarios.
Towards an ASP-Based Architecture for Autonomous UAVs in Dynamic Environments (Extended Abstract)
Authors: Marcello Balduccini, William C. Regli, Duc N. Nguyen
Date: 2014-05-21 00:00:00
Tasks: Scheduling

Traditional AI reasoning techniques have been used successfully in many
domains, including logistics, scheduling and game playing. This paper is part
of a project aimed at investigating how such techniques can be extended to
coordinate teams of unmanned aerial vehicles (UAVs) in dynamic environments.
Specifically challenging are real-world environments where UAVs and other
network-enabled devices must communicate to coordinate -- and communication
actions are neither reliable nor free. Such network-centric environments are
common in military, public safety and commercial applications, yet most
research (even multi-agent planning) usually takes communications among
distributed agents as a given. We address this challenge by developing an agent
architecture and reasoning algorithms based on Answer Set Programming (ASP).
Although ASP has been used successfully in a number of applications, to the
best of our knowledge this is the first practical application of a complete
ASP-based agent architecture. It is also the first practical application of ASP
involving a combination of centralized reasoning, decentralized reasoning,
execution monitoring, and reasoning about network communications.
Robust Fuzzy corner detector
Authors: Erik Cuevas, Daniel Zaldivar, Marco Perez, Edgar Sanchez, Marte Ramirez
Date: 2014-05-21 00:00:00

Reliable corner detection is an important task in determining the shape of
different regions within an image. Real-life image data are always imprecise
due to inherent uncertainties that may arise from the imaging process such as
defocusing, illumination changes, noise, etc. Therefore, the localization and
detection of corners has become a difficult task to accomplish under such
imperfect situations. On the other hand, Fuzzy systems are well known for their
efficient handling of impreciseness and incompleteness, which make them
inherently suitable for modelling corner properties by means of a rule-based
fuzzy system. The paper presents a corner detection algorithm which employs
such fuzzy reasoning. The robustness of the proposed algorithm is compared to
well-known conventional corner detectors and its performance is also tested
over a number of benchmark images to illustrate the efficiency of the algorithm
under uncertainty.
Fast algorithm for Multiple-Circle detection on images using Learning Automata
Authors: Erik Cuevas, Fernando Wario, Valentin Osuna, Daniel Zaldivar, Marco Perez
Date: 2014-05-21 00:00:00

Hough transform (HT) has been the most common method for circle detection
exhibiting robustness but adversely demanding a considerable computational load
and large storage. Alternative approaches include heuristic methods that employ
iterative optimization procedures for detecting multiple circles under the
inconvenience that only one circle can be marked at each optimization cycle
demanding a longer execution time. On the other hand, Learning Automata (LA) is
a heuristic method to solve complex multi-modal optimization problems. Although
LA converges to just one global minimum, the final probability distribution
holds valuable information regarding other local minima which have emerged
during the optimization process. The detection process is considered as a
multi-modal optimization problem, allowing the detection of multiple circular
shapes through only one optimization procedure. The algorithm uses a
combination of three edge points as parameters to determine circles candidates.
A reinforcement signal determines if such circle candidates are actually
present at the image. Guided by the values of such reinforcement signal, the
set of encoded candidate circles are evolved using the LA so that they can fit
into actual circular shapes over the edge-only map of the image. The overall
approach is a fast multiple-circle detector despite facing complicated
conditions.
Circle detection on images using Learning Automata
Authors: Erik Cuevas, Fernando Wario, Daniel Zaldivar, Marco Perez
Date: 2014-05-21 00:00:00

Circle detection over digital images has received considerable attention from
the computer vision community over the last few years devoting a tremendous
amount of research seeking for an optimal detector. This article presents an
algorithm for the automatic detection of circular shapes from complicated and
noisy images with no consideration of conventional Hough transform principles.
The proposed algorithm is based on Learning Automata (LA) which is a
probabilistic optimization method that explores an unknown random environment
by progressively improving the performance via a reinforcement signal
(objective function). The approach uses the encoding of three non-collinear
points as a candidate circle over the edge image. A reinforcement signal
(matching function) indicates if such candidate circles are actually present in
the edge map. Guided by the values of such reinforcement signal, the
probability set of the encoded candidate circles is modified through the LA
algorithm so that they can fit to the actual circles on the edge map.
Experimental results over several complex synthetic and natural images have
validated the efficiency of the proposed technique regarding accuracy, speed
and robustness.
Multi Modal Face Recognition Using Block Based Curvelet Features
Authors: Jyothi K, Prabhakar C. J
Date: 2014-05-12 00:00:00
Tasks: Face Recognition

In this paper, we present multimodal 2D +3D face recognition method using block based curvelet features. The 3D surface of face (Depth Map) is computed from the stereo face images using stereo vision technique. The statistical measures such as mean, standard deviation, variance and entropy are extracted from each block of curvelet subband for both depth and intensity images independently.In order to compute the decision score, the KNN classifier is employed independently for both intensity and depth map. Further, computed decision scoresof intensity and depth map are combined at decision level to improve the face recognition rate. The combination of intensity and depth map is verified experimentally using benchmark face database. The experimental results show that the proposed multimodal method is better than individual modality.
Off-Policy Shaping Ensembles in Reinforcement Learning
Authors: Anna Harutyunyan, Tim Brys, Peter Vrancx, Ann Nowe
Date: 2014-05-21 00:00:00
Tasks: Computational Efficiency, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Recent advances of gradient temporal-difference methods allow to learn
off-policy multiple value functions in parallel with- out sacrificing
convergence guarantees or computational efficiency. This opens up new
possibilities for sound ensemble techniques in reinforcement learning. In this
work we propose learning an ensemble of policies related through
potential-based shaping rewards. The ensemble induces a combination policy by
using a voting mechanism on its components. Learning happens in real time, and
we empirically show the combination policy to outperform the individual
policies of the ensemble.
Compressive Sampling Using EM Algorithm
Authors: Atanu Kumar Ghosh, Arnab Chakraborty
Date: 2014-05-21 00:00:00

Conventional approaches of sampling signals follow the celebrated theorem of
Nyquist and Shannon. Compressive sampling, introduced by Donoho, Romberg and
Tao, is a new paradigm that goes against the conventional methods in data
acquisition and provides a way of recovering signals using fewer samples than
the traditional methods use. Here we suggest an alternative way of
reconstructing the original signals in compressive sampling using EM algorithm.
We first propose a naive approach which has certain computational difficulties
and subsequently modify it to a new approach which performs better than the
conventional methods of compressive sampling. The comparison of the different
approaches and the performance of the new approach has been studied using
simulated data.
Solving the Minimum Common String Partition Problem with the Help of Ants
Authors: S. M. Ferdous, M. Sohel Rahman
Date: 2014-01-18 00:00:00
Tasks: Combinatorial Optimization

In this paper, we consider the problem of finding a minimum common partition
of two strings. The problem has its application in genome comparison. As it is
an NP-hard, discrete combinatorial optimization problem, we employ a
metaheuristic technique, namely, MAX-MIN ant system to solve this problem. To
achieve better efficiency we first map the problem instance into a special kind
of graph. Subsequently, we employ a MAX-MIN ant system to achieve high quality
solutions for the problem. Experimental results show the superiority of our
algorithm in comparison with the state of art algorithm in the literature. The
improvement achieved is also justified by standard statistical test.
Fast and Fuzzy Private Set Intersection
Authors: Nicholas Kersting
Date: 2014-05-13 00:00:00

Private Set Intersection (PSI) is usually implemented as a sequence of
encryption rounds between pairs of users, whereas the present work implements
PSI in a simpler fashion: each set only needs to be encrypted once, after which
each pair of users need only one ordinary set comparison. This is typically
orders of magnitude faster than ordinary PSI at the cost of some ``fuzziness"
in the matching, which may nonetheless be tolerable or even desirable. This is
demonstrated in the case where the sets consist of English words processed with
WordNet.