In order to allow automation in the achievement of complex problems we should like a general solution with the following characteristics:
As a motivating example we consider the task (i.e., goal) of parametric design , which can be defined over:
Design space – the space that contains all possible designs;
Requirements – a finite set of which are assumed to be provided by the user;
Constraints – a finite set of which model additional conditions for a valid design;
Preference – a function over the design space which can be used to discriminate between different solutions.
Domain knowledge is implicit in the parametric design description in several places:
Design space – the concrete definition of the design space is domain specific knowledge
Constraints – domain knowledge concerning regularities in the domain in which the design is constructed;
Formally, a design artifact is described by a set of attribute-value pairs.
Let A1, ..., An be a fixed set of parameters with fixed ranges R1, ..., Rn:
Design space is the cartesian product R1 × ... × Rn;
Requirements – a relation R which defines a subset of this space;
Constraints – a relation C which defines a subset of this space;
Preference – a partial function P having all possible designs as its domain and preference values as its range.
An inefficient naive approach to parametric design is called generate & test , which depends on the following inferences:
generate – requires knowledge that describes what constitutes a possible design (i.e., the design space);
R-test – requires knowledge that describes which possible designs are desired (i.e. the user requirements);
C-test – requires knowledge that describes which possible designs are valid (i.e., the domain constraints);
select – requires knowledge that evaluates solutions (i.e., knowledge that describes what constitutes a preferred design).
DEVELOPMENT OF KNOWLEDGE-BASED SYSTEMS TOWARDS PROBLEM-SOLVING METHODS
General Problem Solver
3a. Newell’s 3 levels of knowledge
3b. Brachman’s 5 levels of knowledge
Problem Solving Methods
The General Problem Solver (GPS) is a universal problem solving approach.
GPS is the first approach that makes the distinction between knowledge of problems domains and how to solve problems
GPS is domain and task independent approach.
GPS does not put any restrictions both on the domain knowledge and on the task.
Examples of GPS are: automated theorem proving and generic search methods
Generic Search Methods are GPS for which every problem can be expressed as search
One particular example of a Generic Search Method is the A* algorithm.
A* works for problems that can be represented as a state space i.e. a graph of states. Initial conditions of the problem are represented as start state , goal conditions are represented as end state
A* is an informed search or heuristic search approach that uses the estimation function:
g(n) the cost to get from the star state to current state n
h(n) estimated cost to get from current state n to end state
f(n) estimated total cost from start state through current state n to the end state
See Lecture 5
However, GPS has a set of limitations :
It works in theory but in practice works only on toy problems (e.g. Tower of Hanoi)
Could not solve real-world problems because search was easily lost in the combinatorial explosion of intermediate states
Knowledge-is-power hypothesis , also called the Knowledge Principle was formulated by E.A. Feigenbaum in 1977:
“knowledge of the specific task domain in which the program is to do its problem solving was more important as a source of power for competent problem solving than the reasoning method employed” [Feigenbaum, 1977]
The Knowledge-is-power hypothesis shifted the focus on how to build intelligent systems from inference to the knowledge base .
Problem solving is guided by experiential, qualitative, heuristic knowledge.
The meaning of intelligence as knowledge is the common meaning in English world.
The Central Intelligence Agency (CIA) defines intelligence as knowledge.
The Knowledge-is-power hypothesis lead to the emergence of a new filed i.e. expert systems and a new profession i.e. knowledge engineer
3a. Newell’s 3 levels of knowledge
3b. Brachman’s 5 levels of knowledge
In his work from 1981, Newell tried to answer questions such as:
How can knowledge be characterised?
What is the relation of this characterisation and the representation of knowledge?
What is characteristic about a system which holds knowledge?
Newell distinguished 3 levels in the context of knowledge representation:
The most abstract level of representing knowledge.
Concerns the total knowledge contained in the Knowledge Base
Example:The automated DB-Information system knows that a trip from Innsbruck to Vienna costs 120€
Encoding of knowledge in a formal language.
Example:Price(Innsbruck, Vienna, 120)
The internal representation of the sentences.
As a value in a matrix
The primitives are pointers and memory cells.
Allows the construction of data structures with no a priori semantics
The primitives are logical predicates, operators, and propositions.
An index is available to structure primitives.
A formal semantic is given to primitives in terms of relations among objects in the real world
No particular assumption is made however as to the nature of such relations
The primitives are concept types and structuring relations.
Structuring relations provide structure in a network of conceptual types or units. (i.e. inheritance: conceptual units, conceptual sub-units)
The epistemological level links formal structure to conceptual units
It contains structural connections in our knowledge needed to justify conceptual inferences.
The primitives are conceptual relations, primitive objects and actions.
The primitives have a definite cognitive interpretation, corresponding to language-independent concepts like elementary actions or thematic roles
The primitives are words, and (lingustic) expressions.
The primitives are associated directly to nouns and verbs of a specific natural language
Arbitrary relations and nodes that exist in a domain
Problem Solving Methods (PSM) abstract from details of the implementation of the reasoning process.
Knowledge roles determine which role the domain knowledge plays in each inference action.
“Reasoning strategies that gain efficiency through
We consider again the task of parametric design.
revise – tries to improve an incorrect design based on the feedback of the C-test step.
In other words, instead of proposing a complete design which is then repaired, we can also incrementally develop a design and repair it at each step where a constraint violation occurs.
revise delivers designs that are desired or that requirement violations that it does not x must be accepted.
It assumes that the propose step and the revise step deliver acceptable (or optimal) solutions or that the functionality of the task is reduced to finding an arbitrary solution.
the task – specifies the goals that should be solved in order to solve a given problem. A second part of a task specification is the definition of requirements on domain knowledge;
the problem-solving method – describes an reasoning steps to perform a task as an operational specification separately from a description of the competence, and a description of the requirements on domain knowledge;
the domain model – usually ontology-based description in three parts, a meta-level characterisation of properties, the domain knowledge, and (external) assumptions of the domain model;
the adapter – maps the different terminologies of the task definition, problem-solving method and domain model. Moreover, gives further requirements and assumptions needed to relate the competence of the PSM with the functionality of the task.
Local search can be represented in the following operational specification:
|operational specification local search
output := recursion(currents);
successors := generate(X);
new := select2(X, successors);
then output := select3(X);
select1(x) ⊆ x
ILLUSTRATION BY A LARGER EXAMPLE
The Sisyphus-I office allocation problem was the first of a series of test applications for approaches to building knowledge-based systems.
The aim is to automate the problem-solving behaviour of ‘Siggi’, a hypothetical domain expert .
Specifically Siggi is required to make assignments of the staff of a research group ‘YQT’ to offices.
The 4-page problem statement describes the office layout and relevant data about the 15 group members.
A ‘protocol’ is provided, describing the steps Siggi takes.
From the protocol can be drawn data such as:
The approach used rests on mapping from task concepts to method concepts as shown [Motta, 1999] :
From the protocol can be drawn value ranges, based on given justifications in the protocol:
From the protocol can be drawn the following requirements and constraints:
From the protocol can be drawn the following preferences:
< n1, n2, n3, n4 > , where:
n1 measures the distance between the room of the head of group and that of the secretaries;
n2 measures the distance between the manager’s room and the rooms of the head of group and the secretaries;
n3 measures the distance between the heads of projects and the head of group and secretaries;
n4 provides a measure of the ‘project synergy’ afforded by a solution.
A design model in the Sisyphus-I domain d1, with cost function
< n11, n12, n13, n14 > is cheaper than a design model d2, with cost
< n21, n22, n23, n24 > , iff one or more of the following conditions are satisfied:
n11 < n21
n11 = n21 and n12 < n22
n11 = n21 and n12 = n22 and n13 < n23
n11 = n21 and n12 = n22 and n13 = n23 and n14 < n24
A standard language was developed for the description of PSMs called the Unified Problem-Solving Method Language (UPML) [Fensel et al, 2002]
UPML was applied to the modelling of Web Services in the Web Service Modelling Framework (WSMF) [Fensel & Bussler, 2002]
The WSMF approach was encoded in the Web Service Modeling Ontology (WSMO) – wherein ontology-based models are builts for goals (~tasks), services (~methods) and these are linked by mediators (~adapters) [Fensel et al., 2007]
WSMO was encoded in a family of ontology languages, WSML, and an open-source implementation was carried out in WSMX.
Problem-solving methods offer a means to structure and reuse elements of knowledge-based systems by abstracting from their domain.
Efficiency is achieved by introducing assumptions that either restrict the size of the problem or that postulate strong requirements on the available domain knowledge.
Adapters link tasks and PSMs to domains, allowing reuse of both, and express refinements between PSMs, allowing libraries to be built of these.
[Fensel, 2000] “Problem-Solving Methods: Understanding, Description, Development and Reuse”, D. Fensel, Springer LNAI 1791, 2000
[Stefik et al., 1983] “Basic Concepts for Building Expert Systems”, M. Stefik, J. Aitkins, R. Balzer, J. Benoit, L. Birnbaum, F. Hayes-Roth, and E. Sacerdoti in Building Expert Systems , Addison-Wesley, 1983
[Smith & Lowry, 1990] “Algorithm Theories and Design Tactics”, D. R. Smith and M. R. Lowry in Science of Computer Programming , 14:305–321Addison-Wesley, 1990
[Fensel et al, 2002] “The Unified Problem-solving Method Development Language UPML”, D. Fensel, E. Motta, R. Benjamins, M. Crubezy, S. Decker, M. Gaspari, R. Groenboom, W. Grosso, F. van Harmelen, M. Musen, E. Plaza, G. Schreiber, R. Studer, B. Wielinga, Knowledge and Information Systems, 5(1), 83–131, 2002
[Fensel & Bussler, 2002] “The Web Service Modeling Framework (WSMF)”, D. Fensel and C. Bussler, Electronic Commerce Research and Applications, 1(2), 2002
[Fensel et al., 2007] “Enabling Semantic Web Services:The Web Service Modeling Ontology (WSMO)”, D. Fensel, H. Lausen, A. Polleres, J. de Bruijn, M. Stollberg, D. Roman, and J. Domingue, Springer, 2007
[Brachman, 1979] “On the Epistemological Status of Semantic Networks” R. J. Brachman. In: N.V. Findler (ed.): Associative Networks: Representation and Use of Knowledge by Computers. New York: Academic Press, 1979, 3-50.
[Birmingham&Klinker, 1993] “Knowledge Acquisition Tools with Explicit Problem-Solving Methods”, W. Birmingham and G. Klinker. The Knowledge Engineering Review 8, 1 (1993), 5-25
[Feigenbaum, 1977] “The Art of Artificial Intelligence: Themes and Case Studies of Knowledge Engineering,” E.A. Feigenbaum. Proceedings of the International Joint Conference on Artificial Intelligence, Cambridge, MA, 1977
[Newell, 1981] “The Knowledge Level” Newell, AI Magazine 2 (2), 1981, p. 1-20
Wikipedia and other links: