OpenRaiser/Intern-Atlas huggingface dataset:
Machine Learning of Generic and User-Focused Summarization
Venue: Conference AAAI 1998
Year: 1998

A key problem in text summarization is finding a salience function which determines what information in the source should be included in the summary. This paper describes the use of machine learning on a training corpus of documents and their abstracts to discover salience functions which describe what combination of features is optimal for a given summarization task. The method addresses both "generic" and user-focused summaries.
Learning to Resolve Natural Language Ambiguities: A Unified Approach
Venue: Conference AAAI 1998
Year: 1998

We analyze a few of the commonly used statistics based and machine learning algorithms for natural language disambiguation tasks and observe that they can be re-cast as learning linear separators in the feature space. Each of the methods makes a priori assumptions, which it employs, given the data, when searching for its hypothesis. Nevertheless, as we show, it searches a space that is as rich as the space of all linear separators. We use this to build an argument for a data driven approach which merely searches for a good linear separator in the feature space, without further assumptions on the domain or a specific problem. We present such an approach - a sparse network of linear separators, utilizing the Winnow learning algorithm - and show how to use it in a variety of ambiguity resolution problems. The learning approach presented is attribute-efficient and, therefore, appropriate for domains having very large number of attributes. In particular, we present an extensive experimental comparison of our approach with other methods on several well studied lexical disambiguation tasks such as context-sensitive spelling correction, prepositional phrase attachment and part of speech tagging. In all cases we show that our approach either outperforms other methods tried for these tasks or performs comparably to the best.
Anytime Coalition Structure Generation with Worst Case Guarantees
Venue: Conference AAAI 1998
Year: 1998

Coalition formation is a key topic in multiagent systems. One would prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coalition structures is too large to allow exhaustive search for the optimal one. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? We show that none of the previous coalition structure generation algorithms can establish any bound because they search fewer nodes than a threshold that we show necessary for establishing a bound. We present an algorithm that establishes a tight bound within this minimal amount of search, and show that any other algorithm would have to search strictly more. The fraction of nodes needed to be searched approaches zero as the number of agents grows. If additional time remains, our anytime algorithm searches further, and establishes a progressively lower tight bound. Surprisingly, just searching one more node drops the bound in half. As desired, our algorithm lowers the bound rapidly early on, and exhibits diminishing returns to computation. It also drastically outperforms its obvious contenders. Finally, we show how to distribute the desired search across self-interested manipulative agents.
A Flexible Framework for Defeasible Logics
Venue: Conference AAAI 2000
Year: 2000

Logics for knowledge representation suffer from over-specialization: while each logic may provide an ideal representation formalism for some problems, it is less than optimal for others. A solution to this problem is to choose from several logics and, when necessary, combine the representations. In general, such an approach results in a very difficult problem of combination. However, if we can choose the logics from a uniform framework then the problem of combining them is greatly simplified. In this paper, we develop such a framework for defeasible logics. It supports all defeasible logics that satisfy a strong negation principle. We use logic meta-programs as the basis for the framework.
A Consistency-Based Model for Belief Change: Preliminary Report
Venue: Conference AAAI 2000
Year: 2000

We present a general, consistency-based framework for belief change. Informally, in revising K by A, we begin with A and incorporate as much of K as consistently possible. Formally, a knowledge base K and sentence A are expressed, via renaming propositions in K, in separate languages. Using a maximization process, we assume the languages are the same insofar as consistently possible. Lastly, we express the resultant knowledge base in a single language. There may be more than one way in which A can be so extended by K: in choice revision, one such ``extension'' represents the revised state; alternately revision consists of the intersection of all such extensions. The most general formulation of our approach is flexible enough to express other approaches to revision and update, the merging of knowledge bases, and the incorporation of static and dynamic integrity constraints. Our framework differs from work based on ordinal conditional functions, notably with respect to iterated revision. We argue that the approach is well-suited for implementation: the choice revision operator gives better complexity results than general revision; the approach can be expressed in terms of a finite knowledge base; and the scope of a revision can be restricted to just those propositions mentioned in the sentence for revision A.
DATALOG with Constraints - An Answer-Set Programming System
Venue: Conference AAAI 2000
Year: 2000

Answer-set programming (ASP) has emerged recently as a viable programming paradigm well attuned to search problems in AI, constraint satisfaction and combinatorics. Propositional logic is, arguably, the simplest ASP system with an intuitive semantics supporting direct modeling of problem constraints. However, for some applications, especially those requiring that transitive closure be computed, it requires additional variables and results in large theories. Consequently, it may not be a practical computational tool for such problems. On the other hand, ASP systems based on nonmonotonic logics, such as stable logic programming, can handle transitive closure computation efficiently and, in general, yield very concise theories as problem representations. Their semantics is, however, more complex. Searching for the middle ground, in this paper we introduce a new nonmonotonic logic, DATALOG with constraints or DC. Informally, DC theories consist of propositional clauses (constraints) and of Horn rules. The semantics is a simple and natural extension of the semantics of the propositional logic. However, thanks to the presence of Horn rules in the system, modeling of transitive closure becomes straightforward. We describe the syntax and semantics of DC, and study its properties. We discuss an implementation of DC and present results of experimental study of the effectiveness of DC, comparing it with CSAT, a satisfiability checker and SMODELS implementation of stable logic programming. Our results show that DC is competitive with the other two approaches, in case of many search problems, often yielding much more efficient solutions.
cc-Golog: Towards More Realistic Logic-Based Robot Controllers
Venue: Conference AAAI 2000
Year: 2000

High-level robot controllers in realistic domains typically deal with processes which operate concurrently, change the world continuously, and where the execution of actions is event-driven as in ``charge the batteries as soon as the voltage level is low''. While non-logic-based robot control languages are well suited to express such scenarios, they fare poorly when it comes to projecting, in a conspicuous way, how the world evolves when actions are executed. On the other hand, a logic-based control language like \congolog, based on the situation calculus, is well-suited for the latter. However, it has problems expressing event-driven behavior. In this paper, we show how these problems can be overcome by first extending the situation calculus to support continuous change and event-driven behavior and then presenting \ccgolog, a variant of \congolog which is based on the extended situation calculus. One benefit of \ccgolog is that it narrows the gap in expressiveness compared to non-logic-based control languages while preserving a semantically well-founded projection mechanism.
Logic Programming with Ordered Disjunction
Venue: Conference AAAI 2002
Year: 2002

Logic programs with ordered disjunction (LPODs) combine ideas underlying Qualitative Choice Logic (Brewka et al. KR 2002) and answer set programming. Logic programming under answer set semantics is extended with a new connective called ordered disjunction. The new connective allows us to represent alternative, ranked options for problem solutions in the heads of rules: A \times B intuitively means: if possible A, but if A is not possible then at least B. The semantics of logic programs with ordered disjunction is based on a preference relation on answer sets. LPODs are useful for applications in design and configuration and can serve as a basis for qualitative decision making.
Complexity of Manipulating Elections with Few Candidates
Venue: Conference AAAI 2002
Year: 2002

In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable. One could try to avoid manipulation by using voting protocols where determining a beneficial manipulation is hard. Especially among computational agents, it is reasonable to measure this hardness by computational complexity. Some earlier work has been done in this area, but it was assumed that the number of voters and candidates is unbounded. We derive hardness results for practical multiagent settings where the number of candidates is small but the number of voters can be large. We show that with complete information about the others' votes, individual manipulation is easy, and coalitional manipulation is easy with unweighted voters. However, constructive coalitional manipulation with weighted voters is intractable for all of the voting protocols under study, except for the nonrandomized Cup. Destructive manipulation tends to be easier. Randomizing over instantiations of the protocols (such as schedules of the Cup protocol) can be used to make manipulation hard. Finally, we show that under weak assumptions, if weighted coalitional manipulation with complete information about the others' votes is hard in some voting protocol, then individual and unweighted manipulation is hard when there is uncertainty about the others' votes.
Vote Elicitation: Complexity and Strategy-Proofness
Venue: Conference AAAI 2002
Year: 2002

Preference elicitation is a central problem in AI, and has received significant attention in single-agent settings. It is also a key problem in multiagent systems, but has received little attention here so far. In this setting, the agents may have different preferences that often must be aggregated using voting. This leads to interesting issues because what, if any, information should be elicited from an agent depends on what other agents have revealed about their preferences so far. In this paper we study effective elicitation, and its impediments, for the most common voting protocols. It turns out that in the Single Transferable Vote protocol, even knowing when to terminate elicitation is mathcal NP-complete, while this is easy for all the other protocols under study. Even for these protocols, determining how to elicit effectively is NP-complete, even with perfect suspicions about how the agents will vote. The exception is the Plurality protocol where such effective elicitation is easy. We also show that elicitation introduces additional opportunities for strategic manipulation by the voters. We demonstrate how to curtail the space of elicitation schemes so that no such additional strategic issues arise.
Robust Global Localization Using Clustered Particle Filtering
Venue: Conference AAAI 2002
Year: 2002

Global mobile robot localization is the problem of determining a robot's pose in an environment, using sensor data, when the starting position is unknown. A family of probabilistic algorithms known as Monte Carlo Localization (MCL) is currently among the most popular methods for solving this problem. MCL algorithms represent a robot's belief by a set of weighted samples, which approximate the posterior probability of where the robot is located by using a Bayesian formulation of the localization problem. This article presents an extension to the MCL algorithm, which addresses its problems when localizing in highly symmetrical environments; a situation where MCL is often unable to correctly track equally probable poses for the robot. The problem arises from the fact that sample sets in MCL often become impoverished, when samples are generated according to their posterior likelihood. Our approach incorporates the idea of clusters of samples and modifies the proposal distribution considering the probability mass of those clusters. Experimental results are presented that show that this new extension to the MCL algorithm successfully localizes in symmetric environments where ordinary MCL often fails.
Regression with Respect to Sensing Actions and Partial States
Venue: Conference AAAI 2004
Year: 2004

In this paper, we present a state-based regression function for planning domains where an agent does not have complete information and may have sensing actions. We consider binary domains and employ the 0-approximation [Son & Baral 2001] to define the regression function. In binary domains, the use of 0-approximation means using 3-valued states. Although planning using this approach is incomplete with respect to the full semantics, we adopt it to have a lower complexity. We prove the soundness and completeness of our regression formulation with respect to the definition of progression. More specifically, we show that (i) a plan obtained through regression for a planning problem is indeed a progression solution of that planning problem, and that (ii) for each plan found through progression, using regression one obtains that plan or an equivalent one. We then develop a conditional planner that utilizes our regression function. We prove the soundness and completeness of our planning algorithm and present experimental results with respect to several well known planning problems in the literature.
Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively
Venue: Conference AAAI 2005
Year: 2005

To test incomplete search algorithms for constraint satisfaction problems such as 3-SAT, we need a source of hard, but satisfiable, benchmark instances. A simple way to do this is to choose a random truth assignment A, and then choose clauses randomly from among those satisfied by A. However, this method tends to produce easy problems, since the majority of literals point toward the ``hidden'' assignment A. Last year, Achlioptas, Jia and Moore proposed a problem generator that cancels this effect by hiding both A and its complement. While the resulting formulas appear to be just as hard for DPLL algorithms as random 3-SAT formulas with no hidden assignment, they can be solved by WalkSAT in only polynomial time. Here we propose a new method to cancel the attraction to A, by choosing a clause with t > 0 literals satisfied by A with probability proportional to q^t for some q < 1. By varying q, we can generate formulas whose variables have no bias, i.e., which are equally likely to be true or false; we can even cause the formula to ``deceptively'' point away from A. We present theoretical and experimental results suggesting that these formulas are exponentially hard both for DPLL algorithms and for incomplete algorithms such as WalkSAT.
From Qualitative to Quantitative Proofs of Security Properties Using First-Order Conditional Logic
Venue: Conference AAAI 2008
Year: 2008

A first-order conditional logic is considered, with semantics given by a variant of epsilon-semantics, where p -> q means that Pr(q | p) approaches 1 super-polynomially --faster than any inverse polynomial. This type of convergence is needed for reasoning about security protocols. A complete axiomatization is provided for this semantics, and it is shown how a qualitative proof of the correctness of a security protocol can be automatically converted to a quantitative proof appropriate for reasoning about concrete security.
Propagating Conjunctions of AllDifferent Constraints
Venue: Conference AAAI 2010
Year: 2010

We study propagation algorithms for the conjunction of two AllDifferent constraints. Solutions of an AllDifferent constraint can be seen as perfect matchings on the variable/value bipartite graph. Therefore, we investigate the problem of finding simultaneous bipartite matchings. We present an extension of the famous Hall theorem which characterizes when simultaneous bipartite matchings exists. Unfortunately, finding such matchings is NP-hard in general. However, we prove a surprising result that finding a simultaneous matching on a convex bipartite graph takes just polynomial time. Based on this theoretical result, we provide the first polynomial time bound consistency algorithm for the conjunction of two AllDifferent constraints. We identify a pathological problem on which this propagator is exponentially faster compared to existing propagators. Our experiments show that this new propagator can offer significant benefits over existing methods.
An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games
Venue: Conference AAAI 2010
Year: 2010

This paper presents a technique for approximating, up to any precision, the set of subgame-perfect equilibria (SPE) in discounted repeated games. The process starts with a single hypercube approximation of the set of SPE. Then the initial hypercube is gradually partitioned on to a set of smaller adjacent hypercubes, while those hypercubes that cannot contain any point belonging to the set of SPE are simultaneously withdrawn. Whether a given hypercube can contain an equilibrium point is verified by an appropriate mathematical program. Three different formulations of the algorithm for both approximately computing the set of SPE payoffs and extracting players' strategies are then proposed: the first two that do not assume the presence of an external coordination between players, and the third one that assumes a certain level of coordination during game play for convexifying the set of continuation payoffs after any repeated game history. A special attention is paid to the question of extracting players' strategies and their representability in form of finite automata, an important feature for artificial agent systems.
Reformulation of Global Constraints in Answer Set Programming
Venue: Conference AAAI 2010
Year: 2010

We show that global constraints on finite domains like all-different can be reformulated into answer set programs on which we achieve arc, bound or range consistency. These reformulations offer a number of other advantages beyond providing the power of global propagators to answer set programming. For example, they provide other constraints with access to the state of the propagator by sharing variables. Such sharing can be used to improve propagation between constraints. Experiments with these encodings demonstrate their promise.
Reinforcement Learning via AIXI Approximation
Venue: Conference AAAI 2010
Year: 2010

This paper introduces a principled approach for the design of a scalable general reinforcement learning agent. This approach is based on a direct approximation of AIXI, a Bayesian optimality notion for general reinforcement learning agents. Previously, it has been unclear whether the theory of AIXI could motivate the design of practical algorithms. We answer this hitherto open question in the affirmative, by providing the first computationally feasible approximation to the AIXI agent. To develop our approximation, we introduce a Monte Carlo Tree Search algorithm along with an agent-specific extension of the Context Tree Weighting algorithm. Empirically, we present a set of encouraging results on a number of stochastic, unknown, and partially observable domains.
Parameterized Complexity of Problems in Coalitional Resource Games
Venue: Conference AAAI 2011
Year: 2011

Coalition formation is a key topic in multi-agent systems. Coalitions enable agents to achieve goals that they may not have been able to achieve on their own. Previous work has shown problems in coalitional games to be computationally hard. Wooldridge and Dunne (Artificial Intelligence 2006) studied the classical computational complexity of several natural decision problems in Coalitional Resource Games (CRG) - games in which each agent is endowed with a set of resources and coalitions can bring about a set of goals if they are collectively endowed with the necessary amount of resources. The input of coalitional resource games bundles together several elements, e.g., the agent set Ag, the goal set G, the resource set R, etc. Shrot, Aumann and Kraus (AAMAS 2009) examine coalition formation problems in the CRG model using the theory of Parameterized Complexity. Their refined analysis shows that not all parts of input act equal - some instances of the problem are indeed tractable while others still remain intractable. We answer an important question left open by Shrot, Aumann and Kraus by showing that the SC Problem (checking whether a Coalition is Successful) is W[1]-hard when parameterized by the size of the coalition. Then via a single theme of reduction from SC, we are able to show that various problems related to resources, resource bounds and resource conflicts introduced by Wooldridge et al are 1. W[1]-hard or co-W[1]-hard when parameterized by the size of the coalition. 2. para-NP-hard or co-para-NP-hard when parameterized by |R|. 3. FPT when parameterized by either |G| or |Ag|+|R|.
Co-Evolution of Selection and Influence in Social Networks
Venue: Conference AAAI 2011
Year: 2011

Many networks are complex dynamical systems, where both attributes of nodes and topology of the network (link structure) can change with time. We propose a model of co-evolving networks where both node at- tributes and network structure evolve under mutual influence. Specifically, we consider a mixed membership stochastic blockmodel, where the probability of observing a link between two nodes depends on their current membership vectors, while those membership vectors themselves evolve in the presence of a link between the nodes. Thus, the network is shaped by the interaction of stochastic processes describing the nodes, while the processes themselves are influenced by the changing network structure. We derive an efficient variational inference procedure for our model, and validate the model on both synthetic and real-world data.
Dominating Manipulations in Voting with Partial Information
Venue: Conference AAAI 2011
Year: 2011

We consider manipulation problems when the manipulator only has partial information about the votes of the nonmanipulators. Such partial information is described by an information set, which is the set of profiles of the nonmanipulators that are indistinguishable to the manipulator. Given such an information set, a dominating manipulation is a non-truthful vote that the manipulator can cast which makes the winner at least as preferable (and sometimes more preferable) as the winner when the manipulator votes truthfully. When the manipulator has full information, computing whether or not there exists a dominating manipulation is in P for many common voting rules (by known results). We show that when the manipulator has no information, there is no dominating manipulation for many common voting rules. When the manipulator's information is represented by partial orders and only a small portion of the preferences are unknown, computing a dominating manipulation is NP-hard for many common voting rules. Our results thus throw light on whether we can prevent strategic behavior by limiting information about the votes of other voters.