Knowledge Spaces

A student is facing a teacher, who is probing her¹ knowledge of high school mathematics. The student, a new recruit, is freshly arrived from a foreign country, and important questions must be answered: to which grade should the student be assigned? What are her strengths and weaknesses? Should the student take a remedial course in some subject? Which topics is she ready to learn? The teacher will ask a question and listen to the student’s response. Other questions will then be asked. After a few questions, a picture of the student’s state of knowledge will emerge, which will become increasingly sharper in the course of the examination.

Suppose that some complex system is assessed by an expert, who checks for the presence or absence of some revealing features. Ultimately, the state of the system is described by the subset of features (from a possibly large set) which are detected by the expert. This concept is very general, and becomes powerful only on the background of specific assumptions, in the context of some applications. We begin with the combinatoric underpinnings of the theory.

The knowledge state of an individual may vary over time. For example, the following learning scheme is reasonable. A novice student is in the empty state and thus knows nothing at all. Then, one or a few items are mastered; next, another batch is absorbed, etc., up to the eventual mastery of the full domain of the knowledge structure. There may be many possible learning sequences, however. Forgetting may also take place. More generally, there may be many ways of traversing a knowledge structure, evolving at each step from one state to another closely resembling one, and various reasons for doing so.

When a knowledge structure is a quasi ordinal space, it can be faithfully represented by its surmise relation (cf. Theorem 1.49). In fact, as illustrated by Example 1.46, an ordinal space is completely recoverable from the Hasse diagram of the surmise relation. However, for knowledge structures in general, and even for knowledge spaces, the information provided by the surmise relation may be incomplete. In this chapter, we introduce the ‘surmise system’, a concept generalizing that of a surmise relation, and allowing more than one possible learning history for an item¹. We then derive, in the style of Theorem 1.49, a one-to-one correspondence between knowledge spaces and surmise systems. The surmise systems are closely related to the AND/OR graphs encountered in artificial intelligence. A section of this chapter is devoted to clarifying the relationship between the two concepts. This chapter also contains a discussion of the particular surmise systems which arise from well-graded knowledge spaces. Other highlights are: a generalization of the concept of a Hasse diagram, and a study of intractable ‘cyclic’ histories which leads us to formulate conditions precluding such situations.

So far, cognitive interpretations of our mathematical concepts have been limited to the use of mildly evocative words such as ‘knowledge state’, ‘learning path’ or ‘gradation.’ This makes sense since, as suggested by our Examples in 0.9, 0.10 and 0.11, many of our results are potentially applicable to widely different fields. It must be realized, however, that our basic concepts are consistent with traditional explanatory features of psychometric theory, such as ’skills’ or ‘latent trait’ (cf. Lord and Novick, 1974; Weiss, 1983; Wainer and Messick, 1983). Some possible relationships between knowledge states and skills, and other features of the items, are explored in this chapter.

In practice, how can we build a knowledge structure for a specific body of information? The first step is to select the items forming a domain Q. For real-life applications, we will typically assume this domain to be finite. The second step is then to construct a list of all the subsets of Q that are knowledge states. To secure such a list, we could in principle rely on one or more experts in the particular body of information. However, if no assumption is made on the structure to be uncovered, the only exact method consists in the presentation of all subsets of Q to the expert, so that he can point out the states. As the number of subsets of Q grows exponentially with the size ∣Q∣ of Q, this method becomes impractical even for relatively small sets Q (e.g., for only 20 items we would have to present 2²⁰ − 2 = 1,048,574 subsets to the expert).

In vaxious preceding chapters, several one-to-one correspondences were established between particular collections of mathematical structures. For instance, Birkhoff’s Theorem 1.49 asserts the existence of a one-to-one correspondence between the collection of all quasi ordinal spaces on a domain Q, and the collection of all quasi orders on Q. All these correspondences will be shown to derive from natural constructions. Each derivation will be obtained from the application of a general result about ‘Galois connections.’ A compendium of the notation for the various collections and the three ‘Galois connections’ of main interest to us is given at the end of the chapter, before the Sources section. We star the whole chapter because its content is more abstract, and not essential to the rest of this book.

The concept of a knowledge structure is a deterministic one. As such, it does not provide realistic predictions of subjects’ responses to the problems of a test. There are two ways in which probabilities must enter in a realistic model. For one, the knowledge states will certainly occur with different frequencies in the population of reference. It is thus reasonable to postulate the existence of a probability distribution on the collection of states. For another, a subject’s knowledge state does not necessarily specify the observed responses. A subject having mastered an item may be careless in responding, and make an error. Also, in some situations, a subject may be able to guess the correct response to a question not yet mastered. In general, it makes sense to introduce conditional probabilities of responses, given the states. A number of simple probabilistic models will be described in this chapter. They will be used to illustrate how probabilistic concepts can be introduced within knowledge space theory. These models will also provide a precise context for the discussion of some technical issues related to parameter estimation and statistical testing. In general, this material must be regarded as a preparation for the stochastic theories discussed in Chapters 8, 10 and 11.

The stochastic theory presented in this chapter is more ambitious than those examined in Chapter 7. The description of the learning process is more complete and takes place in real time, rather than in a sequence of discrete trials. This theory also contains a provision for individual differences. Nevertheless, its basic intuition is similar, in that that any student progresses through some learning path. As time passes, the student successively masters the items—or the associated concepts—encountered along the learning path. The exposition of the theory given here follows closely Falmagne (1993, 1996). As before, we shall illustrate the concepts of the theory in the framework of an example.

How can we economically describe a state in a knowledge structure? The question is inescapable because realistic states will typically be quite large. In such cases, it is impractical to describe a state by giving the full list of items that it contains. It is also unnecessary: because of the redundancy in many real-life knowledge structures¹, a state will often be characterizable by a relatively small set of features. This idea is not new. In Chapter 2, we proved that any state in a well-graded knowledge structure could be fully described by simply listing its inner and outer fringes (cf. Theorem 2.9 and Remark 2.10(a)). Here, we consider this issue more systematically. This chapter is somewhat eccentric to the rest of this book and can be skipped without harm at first reading. We begin by illustrating the main ideas in the context of a simple example encountered before (see e.g. 3.1).

Suppose that, having applied the techniques described in the preceding chapters, we have obtained a particular knowledge structure. We now ask: how can we uncover, by appropriate questioning, the knowledge state of a particular individual? Two broad classes of stochastic assessment procedures are described in this chapter and the next one.

This chapter presents an assessment procedure that is similar in spirit to those described in Chapter 10, but different in a key aspect: it is based on a finite Markov chain rather than on a Markov process with an uncountable set of Markov states. As a consequence, the procedure requires less storage and computation and can thus be implemented on a small machine.

In Chapter 5, we established the equivalence of two seemingly quite different concepts: on the one hand the knowledge spaces, and on the other hand the entailments for Q. Recall that the latter are the relations {IE275-1} that satisfy the following two conditions: for all q ∈ Q and A, B ∈ 2^Q\{∅},