Previous work on information extraction from unstructured, ungrammatical text (e.g. classified ads) showed that exploiting a set of background knowledge, called a "reference set," greatly improves the precision and recall of the extractions. However, finding a source for this reference set is often difficult, if not impossible. Further, even if a source is found, it might not overlap well with the text for extraction. In this paper we present an approach to building the reference set directly from the text itself. Our approach eliminates the need to find the source for the reference set, and ensures better overlap between the text and reference set. Starting with a small amount of background knowledge, our technique constructs tuples representing the entities in the text to form a reference set. Our results show that our method outperforms manually constructed reference sets, since hand built reference sets may not overlap with the entities in the unstructured, ungrammatical text. We also ran experiments comparing our method to the supervised approach of Conditional Random Fields (CRFs) using simple, generic features. These results show our method achieves an improvement in F1-measure for 6/9 attributes and is competitive in performance on the others, and this is without training data.

We show how to translate HTN domain descriptions (if they satisfy certain restrictions) into PDDL so that they can be used by classical planners.  We provide correctness results for our translation algorithm, and show that it runs in linear time and space. We also show that even small and incomplete amounts of HTN knowledge, when translated into PDDL using our algorithm, can greatly improve a classical planner's performance. In experiments on several thousand randomly generated problems in three different planning domains, such knowledge speeded up the well-known Fast-Forward planner by several orders of magnitude, and enabled it to solve much larger problems than it could otherwise solve.

An exception is which tracks the extent to which material has our Degrees of Grounding model [Roque and Traum, 2008], reached mutual belief in a dialogue, and conduct which provides a more detailed description of the extent to experiments in which the model is used to manage which material has become a part of the common ground during grounding behavior in spoken dialogues with a virtual a dialogue. In this paper we describe experiments in applying human. We show that the model produces improvements that model to handle explicit grounding behavior in in virtual human performance as measured a virtual human. We begin by describing the model and the by post-session questionnaires.

Feature selection can be conducted in a supervised or unsupervised manner, in terms of whether the label information We consider the problem of semi-supervised feature is utilized to guide the selection of relevant features. Generally, selection, where we are given a small amount supervised feature selection methods require a large of labeled examples and a large amount of unlabeled amount of labeled training data. It however could fail to identify examples. Since a small number of labeled the relevant features that are discriminative to different samples are usually insufficient for identifying the classes, provided the number of labeled samples is small. On relevant features, the critical problem arising from the other hand, while unsupervised feature selection methods semi-supervised feature selection is how to take could work well with unlabeled training data, they ignore advantage of the information underneath the unlabeled the label information and therefore are often unable to identify data. To address this problem, we propose the discriminative features. Given the high cost in manually a novel discriminative semi-supervised feature labeling data, and at the same time abundant unlabeled selection method based on the idea of manifold data are often easily accessible, it is desirable to develop feature regularization. The proposed method selects selection methods that are capable of exploiting both labeled features through maximizing the classification margin and unlabeled data.

Understanding the computational complexity of manipulation in elections is arguably the most central agenda in Computational Social Choice. One of the influential variations of the the problem involves a coalition of manipulators trying to make a favorite candidate win the election. Although the complexity of the problem is well-studied under the assumption that the voters are weighted, there were very few successful attempts to abandon this strong assumption. In this paper, we study the complexity of the unweighted coalitional manipulation problem (UCM) under several prominent voting rules. Our main result is that UCM is NP-complete under the maximin rule; this resolves an enigmatic open question. We then show that UCM is NP-complete under the ranked pairs rule, even with respect to a single manipulator. Furthermore, we provide an extreme hardness-of-approximation result for an optimization version of UCM under ranked pairs. Finally, we show that UCM under the Bucklin rule is in P.

In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks on elections — attempts to improve the election outcome by such actions as adding/deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i.e., multimode) attack.   We do so to more realistically capture the richness of real-life settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks, and by constructing polynomial-time multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time.

Voting theory can provide useful insights for multiagent preference aggregation. However, the standard setting assumes voters with preferences that are total orders, as well as a ballot language that coincides with the preference language. In typical AI scenarios, these assumptions do not hold: certain alternatives may be incomparable for some agents, and others may have their preferences encoded in a format that is different from how the preference aggregation mechanism wants them. We study the consequences of dropping these assumptions. In particular, we investigate the consequences for the important notion of strategy-proofness. While strategy-proofness cannot be guaranteed in the classical setting, we are able to show that there are situations in our more general framework where this is possible. We also consider computational aspects of the problem.

Voting on multiple related issues is an important and difficult problem. The key difficulty is that the number of alternatives is exponential in the number of issues, and hence it is infeasible for the agents to rank all the alternatives. A simple approach is to vote on the issues one at a time, in sequence; however, a drawback is that the outcome may depend on the order in which the issues are voted upon and decided, which gives the chairperson some control over the outcome of the election because she can strategically determine the order. While this is undeniably a negative feature of sequential voting, in this paper we temper this judgment by showing that the chairperson's control problem is, in most cases, computationally hard.

In many practical contexts where a number of agents have to find a common decision, the votes do not come all together at the same time. In such situations, we may want to preprocess the information given by the subelectorate (consisting of the voters who have expressed their votes) so as to ``compile'' the known votes for the time when the latecomers have expressed their votes. We study the amount of space necessary for such a compilation, as a function of the voting rule, the number of candidates, and the number of votes already known. We relate our results to existing work, especially on communication complexity.

Voting is a general method for aggregating the preferences of multiple agents. Each agent ranks all the possible alternatives, and based on this, an aggregate ranking of the alternatives (or at least a winning alternative) is produced. However, when there are many alternatives, it is impractical to simply ask agents to report their complete preferences. Rather, the agents' preferences, or at least the relevant parts thereof, need to be elicited. This is done by asking the agents a (hopefully small) number of simple queries about their preferences, such as comparison queries, which ask an agent to compare two of the alternatives. Prior work on preference elicitation in voting has focused on the case of unrestricted preferences. It has been shown that in this setting, it is sometimes necessary to ask each agent (almost) as many queries as would be required to determine an arbitrary ranking of the alternatives. In contrast, in this paper, we focus on single-peaked preferences. We show that such preferences can be elicited using only a linear number of comparison queries, if either the order with respect to which preferences are single-peaked is known, or at least one other agent's complete preferences are known. We show that using a sublinear number of queries does not suffice. We also consider the case of cardinally single-peaked preferences. For this case, we show that if the alternatives' cardinal positions are known, then an agent's preferences can be elicited using only a logarithmic number of queries; however, we also show that if the cardinal positions are not known, then a sublinear number of queries does not suffice. We present experimental results for all elicitation algorithms. We also consider the problem of only eliciting enough information to determine the aggregate ranking, and show that even for this more modest objective, a sublinear number of queries per agent does not suffice for known ordinal or unknown cardinal positions. Finally, we discuss whether and how these techniques can be applied when preferences are almost single-peaked.