[Jairsubscribers] 11 new articles published by JAIR

[jair-ed@isi.edu]

Dear JAIR subscriber:
 This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see instructions at the end of this message.)

----------------------------------------------------------------
I. New JAIR Articles

S.  Katrenko, P.  W. Adriaans and M.  van Someren (2010)
  "Using Local Alignments for Relation Recognition",
   Volume 38, pages 1-48

   For quick access go to <http://www.jair.org/papers/paper2964.html>

Abstract:
This paper discusses the problem of marrying structural similarity with semantic relatedness for Information Extraction from text. Aiming at accurate recognition of relations, we introduce local alignment kernels and explore various possibilities of using them for this task. We give a definition of a local alignment (LA) kernel based on the Smith-Waterman score as a sequence similarity measure and proceed with a range of possibilities for computing similarity between elements of sequences. We show how distributional similarity measures obtained from unlabeled data can be incorporated into the learning task as semantic knowledge. Our experiments suggest that the LA kernel yields promising results on various biomedical corpora outperforming two baselines by a large margin. Additional series of experiments have been conducted on the data sets of seven general relation types, where the performance of the LA kernel is comparable to the current state-of-the-art results.


C.  Cayrol, F.  Dupin de Saint-Cyr and M.  Lagasquie-Schiex (2010)
  "Change in Abstract Argumentation Frameworks: Adding an Argument",
   Volume 38, pages 49-84

   For quick access go to <http://www.jair.org/papers/paper2965.html>

Abstract:
In this paper, we address the problem of change in an abstract argumentation system. We focus on a particular change: the addition of  a new argument which interacts with previous arguments. We study the impact of such an addition on the outcome of the argumentation system, more particularly on the set of its extensions. Several properties for this change operation are defined by comparing the new set of extensions to the initial one, these properties are called structural when the comparisons are based on set-cardinality or set-inclusion relations. Several other properties are proposed where comparisons are based on the status of some particular arguments: the accepted arguments; these properties refer to the evolution of this status during the change, e.g., Monotony and Priority to Recency. All these  properties may be more or less desirable according to specific applications. They are studied under two particular semantics: the grounded and preferred semantics.


W.  Yeoh, A.  Felner and S.  Koenig (2010)
  "BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm",
   Volume 38, pages 85-133

   For quick access go to <http://www.jair.org/papers/paper2849.html>

Abstract:
Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. A DCOP problem is a problem where several agents coordinate their values such that the sum of the resulting constraint costs is minimal. It is often desirable to solve DCOP problems with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search algorithm that uses the message-passing and communication framework of ADOPT (Modi, Shen, Tambe, & Yokoo, 2005), a well known memory-bounded asynchronous DCOP search algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a memory-bounded synchronous DCOP search algorithm, for most of these DCOP problems. Additionally, it is often desirable to find bounded-error solutions for DCOP problems within a reasonable amount of time since finding cost-minimal solutions is NP-hard. The existing bounded-error approximation mechanism allows users only to specify an absolute error bound on the solution cost but a relative error bound is often more intuitive. Thus, we present two new bounded-error approximation mechanisms that allow for relative error bounds and implement them on top of BnB-ADOPT.


I.  Androutsopoulos and P.  Malakasiotis (2010)
  "A Survey of Paraphrasing and Textual Entailment Methods",
   Volume 38, pages 135-187

   For quick access go to <http://www.jair.org/papers/paper2985.html>

Abstract:
Paraphrasing methods recognize, generate, or extract phrases, sentences, or longer natural language expressions that convey almost the same information. Textual entailment methods, on the other hand, recognize, generate, or extract pairs of natural language expressions, such that a human who reads (and trusts) the first element of a pair would most likely infer that the other element is also true. Paraphrasing can be seen as bidirectional textual entailment and methods from the two areas are often similar. Both kinds of methods are useful, at least in principle, in a wide range of natural language processing applications, including question answering, summarization, text generation, and machine translation. We summarize key ideas from the two areas by considering in turn recognition, generation, and extraction methods, also pointing to prominent articles and resources.


M.  Michelson and C.  A. Knoblock (2010)
  "Constructing Reference Sets from Unstructured, Ungrammatical Text",
   Volume 38, pages 189-221

   For quick access go to <http://www.jair.org/papers/paper2937.html>

Abstract:
Vast amounts of text on the Web are unstructured and ungrammatical, such as classified ads, auction listings, forum postings, etc. We call such text “posts.” Despite their inconsistent structure and lack of grammar, posts are full of useful information. This paper presents work on semi-automatically building tables of relational information, called “reference sets,” by analyzing such posts directly. Reference sets can be applied to a number of tasks such as ontology maintenance and information extraction. Our reference-set construction method starts with just a small amount of background knowledge, and constructs tuples representing the entities in the posts to form a reference set. We also describe an extension to this approach for the special case where even this small amount of background knowledge is impossible to discover and use. To evaluate the utility of the machine-constructed reference sets, we compare them to manually constructed reference sets in the context of reference-set-based information extraction. Our results show the reference sets constructed by our method outperform manually constructed reference sets. We also compare the reference-set-based extraction approach using the machine-constructed reference set to supervised extraction approaches using generic features. These results demonstrate that using machine-constructed reference sets outperforms the supervised methods, even though the supervised methods require training data.


J.  Wittocx, M.  Mari&#235;n and M.  Denecker (2010)
  "Grounding FO and FO(ID) with Bounds",
   Volume 38, pages 223-269

   For quick access go to <http://www.jair.org/papers/paper2980.html>

Abstract:
Grounding is the task of reducing a first-order theory and finite domain to an equivalent propositional theory. It is used as preprocessing phase in many logic-based reasoning systems. Such systems provide a rich first-order input language to a user and can rely on efficient propositional solvers to perform the actual reasoning. 

Besides a first-order theory and finite domain, the input for grounders contains in many applications also additional data. By exploiting this data, the size of the grounder's output can often be reduced significantly. A common practice to improve the efficiency of a grounder in this context is by manually adding semantically redundant information to the input theory, indicating where and when the grounder should exploit the data. In this paper we present a method to compute and add such redundant information automatically. Our method therefore simplifies the task of writing input theories that can be grounded efficiently by current systems.
	
We first present our method for classical first-order logic (FO) theories. Then we extend it to FO(ID), the extension of FO with inductive definitions, which allows for more concise and comprehensive input theories. We discuss implementation issues and experimentally validate the practical applicability of our method.


D.  Lesaint, D.  Mehta, B.  O'Sullivan, L.  Quesada and N.  Wilson (2010)
  "Developing Approaches  for Solving a Telecommunications Feature Subscription Problem",
   Volume 38, pages 271-305

   For quick access go to <http://www.jair.org/papers/paper2992.html>

Abstract:
Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their  service. The configuration of a feature subscription involves choosing and sequencing features from a catalogue and is subject to  constraints that prevent undesirable feature interactions at run-time. When the subscription requested by a user is inconsistent, one  problem is to find an optimal relaxation,  which is a generalisation of the feedback vertex  set problem on directed graphs, and thus it is an NP-hard task. We present several constraint programming formulations of the problem. We also present formulations using partial  weighted maximum Boolean satisfiability and mixed integer linear programming.  We study all these formulations by experimentally comparing them  on a variety of randomly generated instances of the feature subscription problem.


G.  Gange, P.  J. Stuckey and V.  Lagoon (2010)
  "Fast Set Bounds Propagation Using a BDD-SAT Hybrid",
   Volume 38, pages 307-338

   For quick access go to <http://www.jair.org/papers/paper3014.html>

Abstract:
Binary Decision Diagram (BDD) based set bounds propagation is a powerful approach to solving set-constraint satisfaction problems. However, prior BDD based techniques in- cur the significant overhead of constructing and manipulating graphs during search. We present a set-constraint solver which combines BDD-based set-bounds propagators with the learning abilities of a modern SAT solver. Together with a number of improvements beyond the basic algorithm, this solver is highly competitive with existing propagation based set constraint solvers.


M.  Babaioff, M.  Feldman and N.  Nisan (2010)
  "Mixed Strategies in Combinatorial Agency",
   Volume 38, pages 339-369

   For quick access go to <http://www.jair.org/papers/paper2961.html>

Abstract:
In many multiagent domains a set of agents exert effort towards a joint outcome, yet the individual effort levels cannot be easily observed. A typical example for such a scenario is routing in communication networks, where the sender can only observe whether the packet reached its destination, but often has no information about the actions of the intermediate routers, which influences the final outcome.  We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome.  In a companion paper we devise and study a  basic ''combinatorial agency'' model for this setting, where the principal is restricted to inducing a pure Nash equilibrium.  Here we study various implications of this restriction. First, we show that, in contrast to the case of observable efforts, inducing a mixed-strategies equilibrium may be beneficial for the principal. Second, we present a sufficient condition for technologies for which no gain can be generated. Third, we bound the principal's gain for various families of technologies. Finally, we study the robustness of mixed equilibria to coalitional deviations and the computational hardness of the optimal mixed equilibria.


A.  Feldman, G.  Provan and A.  van Gemund (2010)
  "Approximate Model-Based Diagnosis Using Greedy Stochastic Search",
   Volume 38, pages 371-413

   For quick access go to <http://www.jair.org/papers/paper3025.html>

Abstract:
We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which trades off guarantees of computing minimal diagnoses for computational efficiency. We empirically demonstrate, using the 74XXX and ISCAS-85 suites of benchmark combinatorial circuits, that SAFARI achieves several orders-of-magnitude speedup over two well-known deterministic algorithms, CDA* and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is optimal for a range of propositional fault models, such as the widely-used weak-fault models (models with ignorance of abnormal behavior). We discuss the optimality of SAFARI in a class of strong-fault circuit models with stuck-at failure modes. By modeling the algorithm itself as a Markov chain, we provide exact bounds on the minimality of the diagnosis computed. SAFARI also displays strong anytime behavior, and will return a diagnosis after any non-trivial inference time.


J.  Wu and E.  H. Durfee (2010)
  "Resource-Driven Mission-Phasing Techniques for Constrained Agents in Stochastic Environments",
   Volume 38, pages 415-473

   For quick access go to <http://www.jair.org/papers/paper3004.html>

Abstract:
Because an agent's resources dictate what actions it can possibly take, it should plan which resources it holds over time carefully, considering its inherent limitations (such as power or payload restrictions), the competing needs of other agents for the same resources, and the stochastic nature of the environment. Such agents can, in general, achieve more of their objectives if they can use --- and even create --- opportunities to change which resources they hold at various times.  Driven by resource constraints, the agents could break their overall missions into an optimal series of phases, optimally reconfiguring their resources at each phase, and optimally using their assigned resources in each phase, given their knowledge of the stochastic environment.

In this paper, we formally define and analyze this constrained, sequential optimization problem in both the single-agent and multi-agent contexts. We present a family of mixed integer linear programming (MILP) formulations of this problem that can optimally create phases (when phases are not predefined) accounting for costs and limitations in phase creation.  Because our formulations multaneously also find the optimal allocations of resources at each phase and the optimal policies for using the allocated resources at each phase, they exploit structure across these coupled problems. This allows them to find solutions significantly faster(orders of magnitude faster in larger problems) than alternative solution techniques, as we demonstrate empirically.




----------------------------------------------------------------
II. Unsubscribing from our Mailing List

To remove yourself from the JAIR subscribers mailing list, visit our
Web site (http://www.jair.org/), follow the link "notify me of new
articles", enter your email address in the form at the bottom of the
page, and follow the directions.  In the event that you've already
deleted yourself from the list and we keep sending you messages like
this one, send mail to jair-ed at isi.edu.

----------------------------------------------------------------