The paper investigates the potential of look-ahead in the con-text of AND/OR search in graphical models using the Mini-Bucket heuristic for combinatorial optimization tasks (e.g., MAP/MPE or weighted CSPs). We present and analyze the complexity of computing the residual (a.k.a Bellman update) of the Mini-Bucket heuristic and show how this can be used to identify which parts of the search space are more likely to benefit from look-ahead and how to bound its overhead. We also rephrase the look-ahead computation as a graphical model, to facilitate structure exploiting inference schemes. We demonstrate empirically that augmenting Mini-Bucket heuristics by look-ahead is a cost-effective way of increasing the power of Branch-And-Bound search.

As a challenge problem for AI systems, I propose the use of hand-constructed multiple-choice tests, with problems that are easy for people but hard for computers. Specifically, I discuss techniques for constructing such problems at the level of a fourth-grade child and at the level of a high-school student. For the fourth grade level questions, I argue that questions that require the understanding of time, impossible or pointless scenarios, of causality, of the human body, or of sets of objects, and questions that require combining facts or require simple inductive arguments of indeterminate length can be chosen to be easy for people, and are likely to be hard for AI programs, in the current state of the art. For the high-school level, I argue that questions that relate the formal science to the realia of laboratory experiments or of real-world observations are likely to be easy for people and hard for AI programs. I argue that these are more useful benchmarks than existing standardized tests such as the SATs or Regents tests. Since the questions in standardized tests are designed to be hard for people, they often leave many aspects of what is hard for computers but easy for people untested

This paper offers a perspective on Symbiotic Cognitive Systems that draws on Distributed Cognition. It argues that representations are the medium of cognition, and that the external representations that are one of the foci of Distributed Cognition are critical to supporting symbiosis. The paper analyzes an instance of a symbiotic cognitive system in which hundreds of human participants – with the support of a digital system – collectively optimize a program. It discusses the roles external representations play in symbiosis, and suggest that the design of external representations that are accessible and legible to both human and digital agents is a critical part of symbiotic cognitive systems.

Analytic systems provide insights to decision makers based on data. Conclusion quality depends on the input data and the reasoning steps made by analysts during exploration. This paper presents CATS, a system able to: (i) Store and leverage information about analytical processes conducted by analysts; (ii) Improve the quality and confidence on analytical reports, by improving how well analysts recall their activities; (iii) Provide ways of comparing different analytical reports; (iv) Help with the dissemination of best practices within analytical teams; (v) Produce the provenance of analytical reports. The use of CATS is illustrated through an example of tracking the work in WISE (Weather InSights Environment) a real tool that combines forecast and observed environmental data to provide an integrated platform to make informed decisions.

Model-Based Diagnosis (MBD) is a principled and domain-independent way of analyzing why a system under examination is not behaving as expected. Given an abstract description (model) of the system's components and their behavior when functioning normally, MBD techniques rely on observations about the actual system behavior to reason about possible causes when there are discrepancies between the expected and observed behavior. Due to its generality, MBD has been successfully applied in a variety of application domains over the last decades. In many application domains of MBD, testing different hypotheses about the reasons for a failure can be computationally costly, e.g., because complex simulations of the system behavior have to be performed. In this work, we therefore propose different schemes of parallelizing the diagnostic reasoning process in order to better exploit the capabilities of modern multi-core computers. We propose and systematically evaluate parallelization schemes for Reiter's hitting set algorithm for finding all or a few leading minimal diagnoses using two different conflict detection techniques. Furthermore, we perform initial experiments for a basic depth-first search strategy to assess the potential of parallelization when searching for one single diagnosis. Finally, we test the effects of parallelizing "direct encodings" of the diagnosis problem in a constraint solver.

The paper focuses on finding the m best solutions to combinatorial optimization problems using best-first or depth-first branch and bound search. Specifically, we present a new algorithm m-A*, extending the well-known A* to the m-best task, and for the first time prove that all its desirable properties, including soundness, completeness and optimal efficiency, are maintained. Since best-first algorithms require extensive memory, we also extend the memory-efficient depth-first branch and bound to the m-best task. We adapt both algorithms to optimization tasks over graphical models (e.g., Weighted CSP and MPE in Bayesian networks), provide complexity analysis and an empirical evaluation. Our experiments confirm theory that the best-first approach is largely superior when memory is available, but depth-first branch and bound is more robust. We also show that our algorithms are competitive with related schemes recently developed for the m-best task.

This paper describes R3 (Reading, Reasoning, and Reporting), our system for deep language understanding and model management for the biomedical domain. Starting from a base BioPAX model, we learn extensions to it by reading biomedical research articles from PubMed Central. We describe the particular issues for text understanding in this domain and how we use pre- and post-analysis reasoning to bridge the differences in how knowledge is packaged in a text and in a biomedical database. We close with brief description of our first year results, where R3 was faster than all other reported systems, reading 1,000 articles in 15 minutes.

Model counting and weighted model counting are key problems in artificial intelligence. Marginal inference can be reduced to model counting in many statistical-relational systems, such as Markov Logic. One common approach used by model counters is splitting a theory into disjoint subtheories, performing model counting on the subtheories, and then caching the result. If an identical subtheory is encountered again in the search, the cached result is used, greatly reducing runtime. In this work we introduce a way to cache symmetric subtheories compactly, which could potentially decrease required cache size, increase cache hits, and decrease runtime of solving.

Artificial Intelligence (AI) has four seasons: hype, disappointment, funding drought, and renewed interest. I've been involved in AI research for quite some time -- I became a fellow of the Association for the Advancement of Artificial Intelligence (AAAI) in 1993 -- and I've weathered several seasonal cycles. What I'm seeing now, however, is the most puzzling cycle yet; either I'm getting old and addled, or the current cycle is unique in its magnitude. In these Big Data days, the big talk about AI's potential reminds me of what happened at the peak of earlier cycles (see, for example, the recent Wall Street Journal article. Once again, the focus is on a single technical component -- deep learning -- and hopes seem to be building that it can solve many very hard problems easily and more or less magically.

A similar arguments can be used for graphs (as in graph theory), non-binary trees, heaps, stacks, linked lists etc. Indeed, before programming languages offered advanced data structures, sophisticated objects and types, recursion (and much more) -- all the data -- had to be stored in (organized) arrays. Trees, hash tables etc. were simulated by using arrays and pointers. In some ways, we are getting back to the old times, with unstructured data, such as member postings on social networks. Although structuring unstructured data (by putting it into clusters and taxonomies) allow it to be manipulated much more easily.