Recent Reinforcement Learning (RL) algorithms, such as R-MAX, make (with high probability) only a small number of poor decisions. In practice, these algorithms do not scale well as the number of states grows because the algorithms spend too much effort exploring. We introduce an RL algorithm State TArgeted R-MAX (STAR-MAX) that explores a subset of the state space, called the exploration envelope ξ. When ξ equals the total state space, STAR-MAX behaves identically to R-MAX. When ξ is a subset of the state space, to keep exploration within ξ, a recovery rule β is needed. We compared existing algorithms with our algorithm employing various exploration envelopes. With an appropriate choice of ξ, STAR-MAX scales far better than existing RL algorithms as the number of states increases. A possible drawback of our algorithm is its dependence on a good choice of ξ and β. However, we show that an effective recovery rule β can be learned on-line and ξ can be learned from demonstrations. We also find that even randomly sampled exploration envelopes can improve cumulative rewards compared to R-MAX. We expect these results to lead to more efficient methods for RL in large-scale problems.

We present a spectrum-based, sequential software debugging approach coined Sequoia, that greedily selects tests out of a suite of tests to narrow down the set of diagnostic candidates with a minimum number of tests. Sequoia handles multiple faults, that can be intermittent, at polynomial time and space complexity, due to a novel, approximate diagnostic entropy estimation approach, which considers the subset of diagnoses that cover almost all Bayesian posterior probability mass. Synthetic experiments show that Sequoia achieves much better diagnostic uncertainty reduction compared to random test sequencing.Real programs, taken from the Software Infrastructure Repository, confirm Sequoia's better performance, with a test reduction up to 80% compared to random test sequences.

Computer Go presents a challenging problem for machine learning agents. With the number of possible board states estimated to be larger than the number of hydrogen atoms in the universe, learning effective policies or board evaluation functions is extremely difficult. In this paper we describe Cortigo, a system that efficiently and autonomously learns useful generalizations for large state-space classification problems such as Go. Cortigo uses a hierarchical generative model loosely related to the human visual cortex to recognize Go board positions well enough to suggest promising next moves. We begin by briefly describing and providing motivation for research in the computer Go domain. We describe Cortigo’s ability to learn predictive models based on large subsets of the Go board and demonstrate how using Cortigo’s learned models as additive knowledge in a state-of-the-art computer Go player (Fuego) significantly improves its playing strength.

Semantic relatedness is the task of finding and quantifying Knowledge-based measures such as L&C (Leacock the strength of the semantic connections that exist between and Chodorow 1998), Lesk (Lesk 1986), Wu&Palmer (Wu textual units, be they word pairs, sentence pairs, or document and Palmer 1994), Resnik (Resnik 1995), J&C (Jiang and pairs. For instance, one may want to determine how Conrath 1997), H&S (Hirst and St Onge 1998), and many semantically related are car and automobile, ornoon and others, employ information extracted from manually constructed string. To make such a judgment, we rely on our accumulated lexical taxonomies like Wordnet (Fellbaum 1998), knowledge and experiences, and utilize our ability Roget (Jarmasz 2003), and Wiktionary (Zesch, Muller, and of conceptual thinking, abstraction, and generalization.

Evolutionary Algorithms (EA) are a branch of heuristic population-based optimization tools that is growing in popularity (especially for combinatorial and other problems with poorly understood landscapes). Despite their many uses, there are no proofs that an EA will always converge to the global optimum for any general problem.

Informed search algorithms such as A* use heuristics to focus exploration on states with low total path cost. To the extent that heuristics underestimate forward costs, a wider cost radius of suboptimal states will be explored. For many weighted graphs, however, a small distance in terms of cost may encompass a large fraction of the unweighted graph. We present a new informed search algorithm, Iterative Monotonically Bounded A* (IMBA*), which first proves that no optimal paths exist in a bounded cut of the graph before considering larger cuts. We prove that IMBA* has the same optimality and completeness guarantees as A* and, in a non-uniform pathfinding application, we empirically demonstrate substantial speed improvements over classic A*.

We introduce the level-ordered edge sequence (LOES), a suc- cinct encoding for state-sets based on prefix-trees. For use in state-space search, we give algorithms for member testing and element hashing with runtime dependent only on state- size, as well as space and memory efficient construction of and iteration over such sets. Finally we compare LOES to binary decision diagrams (BDDs) and explicitly packed set- representation over a range of IPC planning problems. Our results show LOES produces succinct set-encodings for a wider range of planning problems than both BDDs and ex- plicit state representation, increasing the number of problems that can be solved cost-optimally.

We seek informative representations of the processes underlying time series data. As a first step, we address problems in which these processes can be approximated by linear models that vary smoothly over time. To facilitate estimation of these linear models, we introduce a method of dimension reduction which significantly reduces error when models are estimated locally for each point in time. This improvement is gained by performing dimension reduction implicitly through the model parameters rather than directly in the observation space.

Some of these complex queries, such as Q1 or Q2, Recent advances in health and life sciences have led to generation can be represented in a formal query language (e.g., of a large amount of biomedical data. To facilitate access SQL/SPARQL) and then answered using Semantic Web to its desired parts, such a big mass of data has been represented technologies. However, queries, like Q4, that require auxiliary in structured forms, like biomedical ontologies and recursive definitions (such as transitive closure) cannot databases. On the other hand, representing these biomedical be directly represented in these languages; and thus such ontologies and databases in different forms, constructing queries cannot be answered directly using Semantic Web them independently from each other, and storing them at technologies. The experts usually compute auxiliary relations different locations have brought about many challenges for externally, for instance, by enumerating all drug-drug answering queries about the knowledge represented in these interaction chains or gene cliques, and then use these auxiliary ontologies and databases.

The ability to understand natural-language instructions is critical to building intelligent agents that interact with humans. We present a system that learns to transform natural-language navigation instructions into executable formal plans. Given no prior linguistic knowledge, the system learns by simply observing how humans follow navigation instructions. The system is evaluated in three complex virtual indoor environments with numerous objects and landmarks. A previously collected realistic corpus of complex English navigation instructions for these environments is used for training and testing data. By using a learned lexicon to refine inferred plans and a supervised learner to induce a semantic parser, the system is able to automatically learn to correctly interpret a reasonable fraction of the complex instructions in this corpus.