pwc-archive/papers-with-abstracts huggingface dataset:
Interactive Cost Configuration Over Decision Diagrams
Authors: Henrik Reif Andersen, Tarik Hadzic, David Pisinger
Date: 2014-01-16 00:00:00

In many AI domains such as product configuration, a user should interactively
specify a solution that must satisfy a set of constraints. In such scenarios,
offline compilation of feasible solutions into a tractable representation is an
important approach to delivering efficient backtrack-free user interaction
online. In particular,binary decision diagrams (BDDs) have been successfully
used as a compilation target for product and service configuration. In this
paper we discuss how to extend BDD-based configuration to scenarios involving
cost functions which express user preferences.
  We first show that an efficient, robust and easy to implement extension is
possible if the cost function is additive, and feasible solutions are
represented using multi-valued decision diagrams (MDDs). We also discuss the
effect on MDD size if the cost function is non-additive or if it is encoded
explicitly into MDD. We then discuss interactive configuration in the presence
of multiple cost functions. We prove that even in its simplest form,
multiple-cost configuration is NP-hard in the input MDD. However, for solving
two-cost configuration we develop a pseudo-polynomial scheme and a fully
polynomial approximation scheme. The applicability of our approach is
demonstrated through experiments over real-world configuration models and
product-catalogue datasets. Response times are generally within a fraction of a
second even for very large instances.
RoxyBot-06: Stochastic Prediction and Optimization in TAC Travel
Authors: Amy Greenwald, Seong Jae Lee, Victor Naroditskiy
Date: 2014-01-16 00:00:00
Tasks: Prediction, Stochastic Optimization

In this paper, we describe our autonomous bidding agent, RoxyBot, who emerged
victorious in the travel division of the 2006 Trading Agent Competition in a
photo finish. At a high level, the design of many successful trading agents can
be summarized as follows: (i) price prediction: build a model of market prices;
and (ii) optimization: solve for an approximately optimal set of bids, given
this model. To predict, RoxyBot builds a stochastic model of market prices by
simulating simultaneous ascending auctions. To optimize, RoxyBot relies on the
sample average approximation method, a stochastic optimization technique.
Efficient Planning under Uncertainty with Macro-actions
Authors: Ruijie He, Emma Brunskill, Nicholas Roy
Date: 2014-01-16 00:00:00

Deciding how to act in partially observable environments remains an active
area of research. Identifying good sequences of decisions is particularly
challenging when good control performance requires planning multiple steps into
the future in domains with many states. Towards addressing this challenge, we
present an online, forward-search algorithm called the Posterior Belief
Distribution (PBD). PBD leverages a novel method for calculating the posterior
distribution over beliefs that result after a sequence of actions is taken,
given the set of observation sequences that could be received during this
process. This method allows us to efficiently evaluate the expected reward of a
sequence of primitive actions, which we refer to as macro-actions. We present a
formal analysis of our approach, and examine its performance on two very large
simulation experiments: scientific exploration and a target monitoring domain.
We also demonstrate our algorithm being used to control a real robotic
helicopter in a target monitoring experiment, which suggests that our approach
has practical potential for planning in real-world, large partially observable
domains where a multi-step lookahead is required to achieve good performance.
Training a Multilingual Sportscaster: Using Perceptual Context to Learn Language
Authors: David L. Chen, Joohyun Kim, Raymond J. Mooney
Date: 2014-01-16 00:00:00
Tasks: Descriptive, Translation

We present a novel framework for learning to interpret and generate language
using only perceptual context as supervision. We demonstrate its capabilities
by developing a system that learns to sportscast simulated robot soccer games
in both English and Korean without any language-specific prior knowledge.
Training employs only ambiguous supervision consisting of a stream of
descriptive textual comments and a sequence of events extracted from the
simulation trace. The system simultaneously establishes correspondences between
individual comments and the events that they describe while building a
translation model that supports both parsing and generation. We also present a
novel algorithm for learning which events are worth describing. Human
evaluations of the generated commentaries indicate they are of reasonable
quality and in some cases even on par with those produced by humans for our
limited domain.
Reasoning About the Transfer of Control
Authors: Wiebe van der Hoek, Dirk Walther, Michael Wooldridge
Date: 2014-01-16 00:00:00

We present DCL-PC: a logic for reasoning about how the abilities of agents
and coalitions of agents are altered by transferring control from one agent to
another. The logical foundation of DCL-PC is CL-PC, a logic for reasoning about
cooperation in which the abilities of agents and coalitions of agents stem from
a distribution of atomic Boolean variables to individual agents -- the choices
available to a coalition correspond to assignments to the variables the
coalition controls. The basic modal constructs of DCL-PC are of the form
coalition C can cooperate to bring about phi. DCL-PC extends CL-PC with dynamic
logic modalities in which atomic programs are of the form agent i gives control
of variable p to agent j; as usual in dynamic logic, these atomic programs may
be combined using sequence, iteration, choice, and test operators to form
complex programs. By combining such dynamic transfer programs with cooperation
modalities, it becomes possible to reason about how the power of agents and
coalitions is affected by the transfer of control. We give two alternative
semantics for the logic: a direct semantics, in which we capture the
distributions of Boolean variables to agents; and a more conventional Kripke
semantics. We prove that these semantics are equivalent, and then present an
axiomatization for the logic. We investigate the computational complexity of
model checking and satisfiability for DCL-PC, and show that both problems are
PSPACE-complete (and hence no worse than the underlying logic CL-PC). Finally,
we investigate the characterisation of control in DCL-PC. We distinguish
between first-order control -- the ability of an agent or coalition to control
some state of affairs through the assignment of values to the variables under
the control of the agent or coalition -- and second-order control -- the
ability of an agent to exert control over the control that other agents have by
transferring variables to other agents. We give a logical characterisation of
second-order control.
Generation, Implementation and Appraisal of an N-gram based Stemming Algorithm
Authors: B. P. Pande, Pawan Tamta, H. S. Dhami
Date: 2013-12-17 00:00:00

A language independent stemmer has always been looked for. Single N-gram
tokenization technique works well, however, it often generates stems that start
with intermediate characters, rather than initial ones. We present a novel
technique that takes the concept of N gram stemming one step ahead and compare
our method with an established algorithm in the field, Porter's Stemmer.
Results indicate that our N gram stemmer is not inferior to Porter's linguistic
stemmer.
On the Estimation of Pointwise Dimension
Authors: Shohei Hidaka, Neeraj Kashyap
Date: 2013-12-09 00:00:00

Our goal in this paper is to develop an effective estimator of fractal
dimension. We survey existing ideas in dimension estimation, with a focus on
the currently popular method of Grassberger and Procaccia for the estimation of
correlation dimension. There are two major difficulties in estimation based on
this method. The first is the insensitivity of correlation dimension itself to
differences in dimensionality over data, which we term "dimension blindness".
The second comes from the reliance of the method on the inference of limiting
behavior from finite data.
  We propose pointwise dimension as an object for estimation in response to the
dimension blindness of correlation dimension. Pointwise dimension is a local
quantity, and the distribution of pointwise dimensions over the data contains
the information to which correlation dimension is blind. We use a "limit-free"
description of pointwise dimension to develop a new estimator. We conclude by
discussing potential applications of our estimator as well as some challenges
it raises.
Structured Priors for Sparse-Representation-Based Hyperspectral Image Classification
Authors: Xiaoxia Sun, Qing Qu, Nasser M. Nasrabadi, Trac. D. Tran
Date: 2014-01-16 00:00:00
Tasks: Classification, General Classification, Hyperspectral Image Classification, image-classification, Image Classification

Pixel-wise classification, where each pixel is assigned to a predefined
class, is one of the most important procedures in hyperspectral image (HSI)
analysis. By representing a test pixel as a linear combination of a small
subset of labeled pixels, a sparse representation classifier (SRC) gives rather
plausible results compared with that of traditional classifiers such as the
support vector machine (SVM). Recently, by incorporating additional structured
sparsity priors, the second generation SRCs have appeared in the literature and
are reported to further improve the performance of HSI. These priors are based
on exploiting the spatial dependencies between the neighboring pixels, the
inherent structure of the dictionary, or both. In this paper, we review and
compare several structured priors for sparse-representation-based HSI
classification. We also propose a new structured prior called the low rank
group prior, which can be considered as a modification of the low rank prior.
Furthermore, we will investigate how different structured priors improve the
result for the HSI classification.
Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurability
Authors: Heather Patsolic, Sancar Adali, Joshua T. Vogelstein, Youngser Park, Carey E. Friebe, Gongkai Li, Vince Lyzinski
Date: 2014-01-16 00:00:00
Tasks: Graph Matching

We present a novel approximate graph matching algorithm that incorporates seeded data into the graph matching paradigm. Our Joint Optimization of Fidelity and Commensurability (JOFC) algorithm embeds two graphs into a common Euclidean space where the matching inference task can be performed. Through real and simulated data examples, we demonstrate the versatility of our algorithm in matching graphs with various characteristics--weightedness, directedness, loopiness, many-to-one and many-to-many matchings, and soft seedings.
Coordinate Descent with Online Adaptation of Coordinate Frequencies
Authors: Tobias Glasmachers, Ürün Dogan
Date: 2014-01-15 00:00:00
Tasks: BIG-bench Machine Learning, General Classification, regression

Coordinate descent (CD) algorithms have become the method of choice for
solving a number of optimization problems in machine learning. They are
particularly popular for training linear models, including linear support
vector machine classification, LASSO regression, and logistic regression.
  We consider general CD with non-uniform selection of coordinates. Instead of
fixing selection frequencies beforehand we propose an online adaptation
mechanism for this important parameter, called the adaptive coordinate
frequencies (ACF) method. This mechanism removes the need to estimate optimal
coordinate frequencies beforehand, and it automatically reacts to changing
requirements during an optimization run.
  We demonstrate the usefulness of our ACF-CD approach for a variety of
optimization problems arising in machine learning contexts. Our algorithm
offers significant speed-ups over state-of-the-art training methods.
Use Case Point Approach Based Software Effort Estimation using Various Support Vector Regression Kernel Methods
Authors: Shashank Mouli Satapathy, Santanu Kumar Rath
Date: 2014-01-14 00:00:00
Tasks: regression

The job of software effort estimation is a critical one in the early stages
of the software development life cycle when the details of requirements are
usually not clearly identified. Various optimization techniques help in
improving the accuracy of effort estimation. The Support Vector Regression
(SVR) is one of several different soft-computing techniques that help in
getting optimal estimated values. The idea of SVR is based upon the computation
of a linear regression function in a high dimensional feature space where the
input data are mapped via a nonlinear function. Further, the SVR kernel methods
can be applied in transforming the input data and then based on these
transformations, an optimal boundary between the possible outputs can be
obtained. The main objective of the research work carried out in this paper is
to estimate the software effort using use case point approach. The use case
point approach relies on the use case diagram to estimate the size and effort
of software projects. Then, an attempt has been made to optimize the results
obtained from use case point analysis using various SVR kernel methods to
achieve better prediction accuracy.
Hrebs and Cohesion Chains as similar tools for semantic text properties research
Authors: D. Tatar, M. Lupea, E. Kapetanios
Date: 2014-01-15 00:00:00

In this study it is proven that the Hrebs used in Denotation analysis of
texts and Cohesion Chains (defined as a fusion between Lexical Chains and
Coreference Chains) represent similar linguistic tools. This result gives us
the possibility to extend to Cohesion Chains (CCs) some important indicators
as, for example the Kernel of CCs, the topicality of a CC, text concentration,
CC-diffuseness and mean diffuseness of the text. Let us mention that nowhere in
the Lexical Chains or Coreference Chains literature these kinds of indicators
are introduced and used since now. Similarly, some applications of CCs in the
study of a text (as for example segmentation or summarization of a text) could
be realized starting from hrebs. As an illustration of the similarity between
Hrebs and CCs a detailed analyze of the poem "Lacul" by Mihai Eminescu is
given.
Modeling Concept Combinations in a Quantum-theoretic Framework
Authors: Diederik Aerts, Sandro Sozzo
Date: 2014-01-15 00:00:00

We present modeling for conceptual combinations which uses the mathematical
formalism of quantum theory. Our model faithfully describes a large amount of
experimental data collected by different scholars on concept conjunctions and
disjunctions. Furthermore, our approach sheds a new light on long standing
drawbacks connected with vagueness, or fuzziness, of concepts, and puts forward
a completely novel possible solution to the 'combination problem' in concept
theory. Additionally, we introduce an explanation for the occurrence of quantum
structures in the mechanisms and dynamics of concepts and, more generally, in
cognitive and decision processes, according to which human thought is a well
structured superposition of a 'logical thought' and a 'conceptual thought', and
the latter usually prevails over the former, at variance with some widespread
beliefs
Intelligent Systems for Information Security
Authors: Ayman M. Bahaa-Eldin
Date: 2014-01-15 00:00:00
Tasks: Cryptanalysis, Scheduling

This thesis aims to use intelligent systems to extend and improve performance
and security of cryptographic techniques. Genetic algorithms framework for
cryptanalysis problem is addressed. A novel extension to the differential
cryptanalysis using genetic algorithm is proposed and a fitness measure based
on the differential characteristics of the cipher being attacked is also
proposed. The complexity of the proposed attack is shown to be less than
quarter of normal differential cryptanalysis of the same cipher by applying the
proposed attack to both the basic Substitution Permutation Network and the
Feistel Network. The basic models of modern block ciphers are attacked instead
of actual cipher to prove that the attack is applicable to other ciphers
vulnerable to differential cryptanalysis. A new attack for block cipher based
on the ability of neural networks to perform an approximation of mapping is
proposed. A complete problem formulation is explained and implementation of the
attack on some hypothetical Feistel cipher not vulnerable to differential or
linear attacks is presented. A new block cipher based on the neural networks is
proposed. A complete cipher structure is given and a key scheduling is also
shown. The main properties of neural network being able to perform mapping
between large dimension domains in a very fast and a very small memory compared
to S-Boxes is used as a base for the cipher.
Improving Performance Of English-Hindi Cross Language Information Retrieval Using Transliteration Of Query Terms
Authors: Saurabh Varshney, Jyoti Bajpai
Date: 2014-01-15 00:00:00
Tasks: Information Retrieval, Retrieval, Transliteration

The main issue in Cross Language Information Retrieval (CLIR) is the poor
performance of retrieval in terms of average precision when compared to
monolingual retrieval performance. The main reasons behind poor performance of
CLIR are mismatching of query terms, lexical ambiguity and un-translated query
terms. The existing problems of CLIR are needed to be addressed in order to
increase the performance of the CLIR system. In this paper, we are putting our
effort to solve the given problem by proposed an algorithm for improving the
performance of English-Hindi CLIR system. We used all possible combination of
Hindi translated query using transliteration of English query terms and
choosing the best query among them for retrieval of documents. The experiment
is performed on FIRE 2010 (Forum of Information Retrieval Evaluation) datasets.
The experimental result show that the proposed approach gives better
performance of English-Hindi CLIR system and also helps in overcoming existing
problems and outperforms the existing English-Hindi CLIR system in terms of
average precision.
Predicting the Performance of IDA* using Conditional Distributions
Authors: Uzi Zahavi, Ariel Felner, Neil Burch, Robert C. Holte
Date: 2014-01-15 00:00:00

Korf, Reid, and Edelkamp introduced a formula to predict the number of nodes
IDA* will expand on a single iteration for a given consistent heuristic, and
experimentally demonstrated that it could make very accurate predictions. In
this paper we show that, in addition to requiring the heuristic to be
consistent, their formulas predictions are accurate only at levels of the
brute-force search tree where the heuristic values obey the unconditional
distribution that they defined and then used in their formula. We then propose
a new formula that works well without these requirements, i.e., it can make
accurate predictions of IDA*s performance for inconsistent heuristics and if
the heuristic values in any level do not obey the unconditional distribution.
In order to achieve this we introduce the conditional distribution of heuristic
values which is a generalization of their unconditional heuristic distribution.
We also provide extensions of our formula that handle individual start states
and the augmentation of IDA* with bidirectional pathmax (BPMX), a technique for
propagating heuristic values when inconsistent heuristics are used.
Experimental results demonstrate the accuracy of our new method and all its
variations.
Text Relatedness Based on a Word Thesaurus
Authors: George Tsatsaronis, Iraklis Varlamis, Michalis Vazirgiannis
Date: 2014-01-15 00:00:00
Tasks: Clustering, Retrieval, Sentence, Sentence Similarity, Text Retrieval, Word Similarity

The computation of relatedness between two fragments of text in an automated
manner requires taking into account a wide range of factors pertaining to the
meaning the two fragments convey, and the pairwise relations between their
words. Without doubt, a measure of relatedness between text segments must take
into account both the lexical and the semantic relatedness between words. Such
a measure that captures well both aspects of text relatedness may help in many
tasks, such as text retrieval, classification and clustering. In this paper we
present a new approach for measuring the semantic relatedness between words
based on their implicit semantic links. The approach exploits only a word
thesaurus in order to devise implicit semantic links between words. Based on
this approach, we introduce Omiotis, a new measure of semantic relatedness
between texts which capitalizes on the word-to-word semantic relatedness
measure (SR) and extends it to measure the relatedness between texts. We
gradually validate our method: we first evaluate the performance of the
semantic relatedness measure between individual words, covering word-to-word
similarity and relatedness, synonym identification and word analogy; then, we
proceed with evaluating the performance of our method in measuring text-to-text
semantic relatedness in two tasks, namely sentence-to-sentence similarity and
paraphrase recognition. Experimental evaluation shows that the proposed method
outperforms every lexicon-based method of semantic relatedness in the selected
tasks and the used data sets, and competes well against corpus-based and hybrid
approaches.
Cross-lingual Annotation Projection for Semantic Roles
Authors: Sebastian Pado, Mirella Lapata
Date: 2014-01-15 00:00:00

This article considers the task of automatically inducing role-semantic
annotations in the FrameNet paradigm for new languages. We propose a general
framework that is based on annotation projection, phrased as a graph
optimization problem. It is relatively inexpensive and has the potential to
reduce the human effort involved in creating role-semantic resources. Within
this framework, we present projection models that exploit lexical and syntactic
information. We provide an experimental evaluation on an English-German
parallel corpus which demonstrates the feasibility of inducing high-precision
German semantic role annotation both for manually and automatically annotated
English data.
ParamILS: An Automatic Algorithm Configuration Framework
Authors: Frank Hutter, Thomas Stuetzle, Kevin Leyton-Brown, Holger H. Hoos
Date: 2014-01-15 00:00:00
Tasks: Hyperparameter Optimization

The identification of performance-optimizing parameter settings is an
important part of the development and application of algorithms. We describe an
automatic framework for this algorithm configuration problem. More formally, we
provide methods for optimizing a target algorithm's performance on a given
class of problem instances by varying a set of ordinal and/or categorical
parameters. We review a family of local-search-based algorithm configuration
procedures and present novel techniques for accelerating them by adaptively
limiting the time spent for evaluating individual configurations. We describe
the results of a comprehensive experimental evaluation of our methods, based on
the configuration of prominent complete and incomplete algorithms for SAT. We
also present what is, to our knowledge, the first published work on
automatically configuring the CPLEX mixed integer programming solver. All the
algorithms we considered had default parameter settings that were manually
identified with considerable effort. Nevertheless, using our automated
algorithm configuration procedures, we achieved substantial and consistent
performance improvements.