IAAI Symposium 2008

Saal Auditorium (room 202), Alon Hi-Tech Buiding (37), Ben-Gurion University

The symposium will be held on Thursday, June 19.

Researchers from Academia and Industry as well as graduate and undergraduate students are welcome to attend the symposium. Participation is free to of charge.
However, we request all attendees to pre-register the registration site. This will allow us to prepare tags and lunch for attendees, and is also required to get a car-entry permit, so please pre-register now.


Click on title for abstract or use buttons:  

9:30-10:00 Reception and coffee

Session 1: Technical presentations

10:00-10:10 Opening remarks Prof. Moti Herskowitz ( Vice-President and Dean for R&D, BGU )
10:10-10:30 Extracting a Lexical Entailment Resource from Wikipedia Eyal Shnarch, Libby Barak, Ido Dagan ( Bar Ilan University )
Extracting a Lexical Entailment Resource from Wikipedia
Eyal Shnarch, Libby Barak, Ido Dagan

This presentation describes the construction of a large-scale lexical entailment rule-base extracted from Wikipedia. A Lexical Entailment rule describes a relation between two terms in which one entails the other. This relation, which is broader than synonymy and hyponymy, was proven to be useful for many Natural Language Processing tasks such as Information Retrieval, Question Answering and Text Categorization. We present extraction methods geared to cover a broad range of lexical entailment relations and evaluate them under this target criterion. Most extraction methods yield high precision levels, and our rule-base is shown to perform comparably to WordNet in a real world Text Categorization application.

10:30-10:50 Using Wikipedia Links to Construct Word Segmentation Corpora , David Gabay, Ziv Ben-Eliahu, Michael Elhadad ( Ben Gurion University )
Using Wikipedia Links to Construct Word Segmentation Corpora
David Gabay, Ziv Ben-Eliahu, Michael Elhadad

Tagged corpora are essential for evaluating and training natural language processing tools. The cost of constructing large enough manually tagged corpora is high, even when the annotation level is shallow. We will present a simple method to automatically construct a large partially-tagged corpus, containing information on word segmentation, using Wikipedia hyperlinks. We used our method to construct a corpus of Modern Hebrew. The general method may also be applied to other languages where word segmentation is difficult to determine, such as East and South-East Asian languages. The talk will also briefly describe some recent work in Modern Hebrew part of speech tagging and word segmentation.

10:50-11:10 The Impact of Adversarial Knowledge on Adversarial Planning in Perimeter Patrol Noa Agmon, Vladimir Sadov, Gal A. Kaminka, Sarit Kraus ( Bar Ilan University )
The Impact of Adversarial Knowledge on Adversarial Planning in Perimeter Patrol
Noa Agmon, Vladimir Sadov, Gal A. Kaminka, Sarit Kraus

This paper considers the problem of multi-robot patrolling around a closed area, in the presence of an adversary trying to penetrate the area. Previous work on planning in similar adversarial environments addressed worst-case settings, in which the adversary has full knowledge of the defending robots. It was shown that non deterministic algorithms may be effectively used to maximize the chances of blocking such a full-knowledge opponent, and such algorithms guarantee a ``lower bound'' to the performance of the team. However, an open question remains as to the impact of the knowledge of the opponent on the performance of the robots.

This paper explores this question in depth and provides theoretical results, supported by extensive experiments with 68 human subjects concerning the compatibility of algorithms to the extent of information possessed by the subjects. First, we analytically examine the case of a zero-knowledge opponent---a different extreme---and show that surprisingly, this seemingly best-case scenario (from the point of view of defending robots) is optimally addressed by a deterministic, non-randomizing patrol. Moreover, we show empirically that an optimal algorithm for the full-knowledge opponent fails miserably in this case. We then address the case in which the adversary gained partial information, propose the combine algorithm that maximizes the expected probability of penetration detection along with minimizing the deviation between the probabilities of penetration detection along the perimeter, and support the performance of this algorithm in the experiments.

11:10-11:30 Concept-Based Feature Generation and Selection for Information Retrieval Ofer Egozi, Evgeniy Gabrilovich, Shaul Markovitch ( Technion )
Concept-Based Feature Generation and Selection for Information Retrieval

Traditional information retrieval systems use query words to identify relevant documents. In difficult retrieval tasks, however, one needs access to a wealth of background knowledge. We present a method that uses Wikipedia-based feature generation to improve retrieval performance. Intuitively, we expect that using extensive world knowledge is likely to improve recall but may adversely affect precision. High quality feature selection is necessary to maintain high precision, but here we do not have the labeled training data for evaluating features, that we have in supervised learning. We present a new feature selection method that is inspired by pseudo-relevance feedback. We use the top-ranked and bottom-ranked documents retrieved by the bag-of- words method as representative sets of relevant and non-relevant documents. The generated features are then evaluated and filtered on the basis of these sets. Experiments on TREC data confirm the superior performance of our method compared to the previous state of the art.

11:30-12:00 Coffee Break

Session 2: Keynote and Student Presentations

12:00-12:50 Keynote: Keeping Up With A Changing World, Sven Koenig ( University of Southern California )
Keeping Up With A Changing World
Sven Koenig

Planning systems (for example, for mobile robots or decision-support systems for crisis situations) often need to operate in domains that are only incompletely known or change dynamically. In this case, they need to replan quickly as their knowledge changes. Replanning from scratch is often very time consuming. In this talk, I will discuss ongoing research by us and others on incremental heuristic search. Incremental search methods reuse information from previous searches to find solutions to series of similar search tasks potentially much faster than is possible by solving each search task from scratch, while heuristic search methods use heuristic knowledge in form of approximations of the goal distances to focus the search and solve search problems potentially much faster than uninformed search methods. I will discuss the theory behind incremental heuristic search and several of its applications. This is joint work with my students and ex-students C. Bauer, D. Furcy, M. Likhachev, Y. Liu, A. Ranganathan and X. Sun.

12:50-1:20 Student introductory presentations

1:20-2:20 Lunch break

Session 3: Technical presentations and Invited Talk

2:20-3:00 (Invited talk) Computational Voting Theory: Of the Agents, By the Agents, For the Agents
Jeffrey S. Rosenschein, (Hebrew University )
Computational Voting Theory: Of the Agents, By the Agents, For the Agents
Jeffrey S. Rosenschein

Classical social choice theory deals with the design and analysis of methods for collective decision making. Heterogeneous, self-interested agents may have conflicting preferences, which can be aggregated by voting over possible outcomes. The winning outcome is then designated by a voting rule, a function from the preferences of the voters to the set of candidates.
Recent years have seen a surge of interest in the computational aspects of social choice, motivated by applications of voting theory to electronic commerce, electronic voting, and multiagent systems. The candidates in automated multiagent systems can be beliefs, joint plans, schedules, movies, or indeed entities of almost any conceivable sort. Computational voting theory is concerned both with the application of computer science techniques to the study of social choice mechanisms, and with the importing of social choice concepts into computing.
This talk will present an overview of some of the issues that have been dealt with in recent years within computational voting theory, including distortion, robustness, the use of complexity as a guard against manipulation, the automated design of voting rules, and the calculation of power indices.
This talk covers joint work with Ariel D. Procaccia, Aviv Zohar, Yoram Bachrach, Michael Zuckerman, Reshef Meir, Yoni Peleg, and Gal Kaminka.

3:00-3:20 Efficient Planning for Loosely Coupled Multi-Agent Systems Ronen Brafman, Carmel Domshlak ( Ben-Gurion University, Technion )
Efficient Planning for Loosely Coupled Multi-Agent Systems
Ronen Brafman, Carmel Domshlak

Loosely coupled multi-agent systems are perceived as easier to plan for because they require less coordination between agent sub-plans. In this paper we set out to formalize this intuition. We establish an upper bound on the complexity of multi-agent planning problems that depends exponentially on two parameters quantifying the level of agents' coupling, and on these parameters only. The first parameter is problem-independent, and it measures the inherent level of coupling within the system. The second is problem-specific and it has to do with the minmax number of action-commitments PER AGENT required to solve the problem. Most importantly, the direct dependence on the number of agents, on the overall size of the problem, and on the length of the agents' plans, is only polynomial. This result is obtained using a new algorithmic methodology which we call ``planning as CSP+planning''. We believe this to be one of the first formal results to both quantify the notion of agents' coupling and to demonstrate a tractable planning algorithm for fixed coupling levels.

3:20-3:40 Using Swamps to Improve Optimal Pathfinding Nir Pochter, Aviv Zohar, Jeffrey S. Rosenschein ( Hebrew University of Jerusalem )
Using Swamps to Improve Optimal Pathfinding
Nir Pochter, Aviv Zohar, Jeffrey S. Rosenschein

In a variety of domains, such as computer games and robotics, many shortest paths have to be found quickly in real time. We address the problem of quickly finding shortest paths in large known graphs. We propose a method that relies on identifying areas that tend to be searched needlessly (areas we call swamp-regions), and exploits this knowledge to improve search. The method requires storing only a few bits in memory for each node of the graph, and reduces search cost drastically, while still finding optimal paths. Our method is independent of the heuristics used in the search, and of the search algorithm. We present experimental results that support our claims, and provide an anytime algorithm for the pre-processing stage that identifies swamp-regions.

3:40-4:00 DIWeDa - Detecting Intrusions in Web Databases, Alex Roichman, Ehud Gudes ( Open University, Ben-Gurion University )
DIWeDa - Detecting Intrusions in Web Databases
Alex Roichman and Ehud Gudes

There are many Intrusion Detection Systems (IDS) for networks and operating systems and there are few for Databases- despite the fact that the most valuable resources of every organization are in its databases. The number of database attacks has grown, especially since most databases are accessible from the web and satisfactory solutions to these kinds of attacks are still lacking. We present DIWeDa - a practical solution for detecting intrusions to web databases. Contrary to any existing database intrusion detection method, our method works at the session level and not at the SQL statement or transaction level. We use a novel SQL Session Content Anomaly intrusion classifier and this enables us to detect not only most known attacks such as SQL Injections, but also more complex kinds of attacks such as Business Logic Violations. Our experiments implemented the proposed intrusion detection system prototype and showed its feasibility and effectiveness.

4:00-4:15 Coffee break

4:15-5:30 IAAI general assembly

5:35    Train leaves BGU

Symposium supported by:

Program Co-Chairs:

Transportation: There's a train station within a five-minute walking distance of the auditorium (see directions), with a train from north and center arriving/departing once an hour. For schedule see train site. Get off at "Be'er Sheva North/University" station (NOT Be'er Sheva Merkaz) and simply walk over the bridge to the university. At the gate you'll see the distinctive Alon Hi-Tech Building.
If you plan on arriving by car make sure to fill in the necessary information in the registration form.