Many AI tasks can be formulated as constraint-satisfaction problems (CSP), i.e., the assignment of values to variables subject to a set of constraints. While some CSPs are hard, those that are easy can often be mapped into sparse networks of constraints which, in the extreme case, are trees. This paper identifies classes of problems that lend themselves to easy solutions, and develops algorithms that solve these problems optimally. The paper then presents a method of generating heuristic advice to guide the order of value assignments based on both the sparseness found in the constraint network and the simplicity of tree-structured CSPs. The advice is generated by simplifying the pending subproblems into trees, counting the number of consistent solutions in each simplified subproblem, and comparing these counts to decide among the choices pending in the original problem.

New York: Springer-Verlag

"Knowledge-Based Tutoring describes the advantages and difficulties of adapting an expert system for use in teaching and problem solving. In this case the well-known rule-based expert system, MYCIN, which has been widely used in medical artificial intelligence to do infectious disease diagnosis and therapy selection, is used as a base for the instructional program GUIDON. MYCIN's rules are interpreted by GUIDON in order to evaluate a student's problem solving and provide assistance as the student gathers information about a patient and makes a diagnosis. The book describes what GUIDON does, how it is constructed, and the benefits and limitations of its design."

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity.

Chapman and Hall. See also: Influence diagrams for Bayesian decision analysis, European Journal of Operational Research, Volume 40, Issue 3, 15 June 1989, Pages 363–376 (http://www.sciencedirect.com/science/article/pii/0377221789904293). Bayesian Decision Analysis: Principles and Practice, Cambridge University Press, 2010 (https://books.google.com/books/about/Bayesian_Decision_Analysis.html?id=O1lXnQAACAAJ).

We distinguish diagrammatic from sentential paper-and-pencil representationsof information by developing alternative models of information-processing systems that are informationally equivalent and that can be characterized as sentential or diagrammatic. Sentential representations are sequential, like the propositions in a text. Dlogrammotlc representations ore indexed by location in a plane. Dio-grommatic representations also typically display information that is only implicit in sententiol representations and that therefore has to be computed, sometimes at great cost, to make it explicit for use. We then contrast the computational efficiency of these representotions for solving several illustrative problems in mothe-matics and physics. When two representotions are informationally equivolent, their computational efficiency depends on the information-processing operators that act on them. Two sets of operators may differ in their copobilities for recognizing patterns, in the inferences they con carry out directly, and in their control strategies (in portitular. Diogrommotic ond sentential representations sup port operators that differ in all of these respects. Operators working on one representation moy recognize feotures readily or make inferences directly that are difficult to realize in the other representation. Most important, however, are differences in the efficiency of scorch for information and in the explicitness of information. In the representotions we call diagrammatic. Therefore problem solving con proceed through o smooth traversal of the diagram, and may require very little search or computation of elements that hod been implicit. "a picture is worth 10,OOO words" is a Chinese proverb. On inquiry, we find that the Chinese seem not to have heard of it, but the proverb is certainly widely known and widely believed in our culture. To understand why it is advantageous to use diagrams-and when it is-we must find some way to contrast diagrammatic and non-diagrammatic representations in an information-processing system.

Annual Review of Computer Science

These algorithms are part of the "folk culture",

This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are efficiently learnable from examples. More precisely, this result is established for k-DL the set of decision lists with conjunctive clauses of size k at each decision. Since k-DL properly includes other well-known techniques for representing Boolean functions such as k-CNF (formulae in conjunctive normal form with at most k literals per clause), k-DNF (formulae in disjunctive normal form with at most k literals per term), and decision trees of depth k, our result strictly increases the set of functions that are known to be polynomially learnable, in the sense of Valiant (1984). Our proof is constructive: we present an algorithm that can efficiently construct an element of k-DL consistent with a given set of examples, if one exists.

Please be advised that ecommerce services will be unavailable for an estimated 6 hours this Saturday 13 November (12:00 – 18:00 GMT).