Web-scale data has been used in a diverse range of language research. Most of this research has used web counts for only short, fixed spans of context. We present a unified view of using web counts for lexical disambiguation. Unlike previous approaches, our supervised and unsupervised systems combine information from multiple and overlapping segments of context. On the tasks of preposition selection and context-sensitive spelling correction, the supervised system reduces disambiguation error by 20-24% over the current state-of-the-art.

Skat is Germany's national card game played by millions of players around the world. In this paper, we present the world's first computer skat player that plays at the level of human experts. This performance is achieved by improving state evaluations using game data produced by human players and by using these state evaluations to perform inference on the unobserved hands of opposing players. Our results demonstrate the gains from adding inference to an imperfect information game player and show that training on data from average human players can result in expert-level playing strength.

Early research in heuristic search discovered that using inconsistent heuristics with A* could result in an exponential increase in the number of node expansions. As a result, the use of inconsistent heuristics has largely disappeared from practice. Recently, inconsistent heuristics have been shown to be effective in IDA*, especially when applying the bidirectional pathmax (BPMX) enhancement. This paper presents new worst-case complexity analysis of A*'s behavior with inconsistent heuristics, discusses how BPMX can be used with A*, and gives experimental results justifying the use of inconsistent heuristics in A* searches.

In many scenarios, quickly solving a relatively small search problem with an arbitrary start and arbitrary goal state is important (e.g., GPS navigation). In order to speed this process, we introduce a new class of memory-based heuristics, called true distance heuristics, that store true distances between some pairs of states in the original state space can be used for a heuristic between any pair of states. We provide a number of techniques for using and improving true distance heuristics such that most of the benefits of the all-pairs shortest-path computation can be gained with less than 1% of the memory. Experimental results on a number of domains show a 6-14 fold improvement in search speed compared to traditional heuristics.

Moving target search (MTS) or the game of cops and robbers has a broad field of application reaching from law enforcement to computer games. Within the recent years research has focused on computing move policies for one or multiple pursuers (cops). The present work motivates to extend this perspective to both sides, thus developing algorithms for the target (robber). We investigate the game with perfect information for both players and propose two new methods, named TrailMax and Dynamic Abstract Trailmax, to compute move policies for the target. Experiments are conducted by simulating games on 20 maps of the commercial computer game Baldur's Gate and measuring survival time and computational complexity. We test seven algorithms: Cover, Dynamic Abstract Minimax, minimax, hill climbing with distance heuristic, a random beacon algorithm, TrailMax and DATrailMax. Analysis shows that our methods outperform all the other algorithms in quality, achieving up to 98% optimality, while meeting modern computer game computation time constraints.

Alpha-Beta is the most common game tree search algorithm, due to its high-performance and straightforward implementation. In practice one must find the best trade-off between heuristic evaluation time and bringing the subset of nodes explored closer to a minimum proof graph. In this paper we present a series of structural properties of minimum proof graphs that help us to prove that finding such graphs is NP-hard for arbitrary DAG inputs, but can be done in linear time for trees. We then introduce the class of fastest-cut-first search heuristics that aim to approximate minimum proof graphs by sorting moves based on approximations of sub-DAG values and sizes. To explore how various aspects of the game tree (such as branching factor and distribution of move values) affect the performance of Alpha-Beta we introduce the class of ``Prefix Value Game Trees'' that allows us to label interior nodes with true minimax values on the fly without search. Using these trees we show that by explicitly attempting to approximate a minimum game tree we are able to achieve performance gains over Alpha-Beta with common extensions.

Equilibrium or near-equilibrium solutions to very large extensive form games are often computed by using abstractions to reduce the game size. A common abstraction technique for games with a large number of available actions is to restrict the number of legal actions in every state. This method has been used to discover equilibrium solutions for the game of no-limit heads-up Texas Hold'em. When using a solution to an abstracted game to play one side in the un-abstracted (real) game, the real opponent actions may not correspond to actions in the abstracted game. The most popular method for handling this situation is to translate opponent actions in the real game to the closest legal actions in the abstracted game. We show that this approach can result in a very exploitable player and propose an alternative solution. We use probabilistic mapping to translate a real action into a probability distribution over actions, whose weights are determined by a similarity metric. We show that this approach significantly reduces the exploitability when using an abstract solution in the real game.

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.

Boosting is a well-known method for improving the accuracy of many learning algorithms. In this paper, we propose a novel boosting algorithm, VipBoost (voting on boosting classifications from imputed learning sets), which first generates multiple incomplete datasets from the original dataset by randomly removing a small percentage of observed attribute values, then uses an imputer to fill in the missing values.  It then applies AdaBoost (using some base learner) to produce classifiers trained on each of the imputed learning sets, to produce multiple classifiers. The subsequent prediction on a new test case is the most frequent classification from these classifiers. Our empirical results show that VipBoost produces very effective classifiers that significantly improve accuracy for unstable base learners and some stable learners, especially when the initial dataset is incomplete.

A general practice in the research of metaphor has been to investigate its behavior and function in different contexts. This current study aims to investigate the notion that verbs possess a metaphor-making potential, this being an initiatory context-free experiment with metaphor. The goal of this paper is to carry out an in-depth case study of a group of English core verbs using WordNet and SUMO ontology. In order to operationalize the measurement of an English verb’s metaphor making potential, a new algorithm has been developed, and a program made to realize the computation. At last, it has been observed that higher frequency verbs generally possess greater metaphor making potential; while a verb’s metaphor making potential on the other hand is also strongly influenced by its functional category.