Acknowledgement

The various apps were developed by participants as part of the TquanT and QHELP programs and often extended by Cord Hockemeyer. For a more consistent tutorial experience, they were adjusted and redundant content was removed. For more informations, the original apps and background information please have a look at the linked web pages.

The texts are partly taken from a talk by Jürgen Heller and Florian Wickelmaier, which was presented during TquanT.

Many thanks to all the students who developed the apps as part of the QHELP and TquanT mobility events and Alice Maurer for helpful comments and corrections.

If you want to learn more exciting concepts of KST, check out the pages of TquanT and QHELP. There you will find more student-developed apps related to KST.

Basic terms

The basis is the characterisation of a knowledge domain through tasks that test knowledge in a specific area. The tasks are dichotomous, i.e. they can be considered either solved or unsolved.

Formally, a knowledge domain is defined by a non-empty set \(Q\) of tasks.

E.g.: \(Q = \{a, b, c, d, e, f\}\)

The knowledge state of a person is represented by the subset \(K\) of tasks from \(Q\) that the person can solve, \(K \subseteq Q\). For example, if a person is able to solve items \(a\), \(c\) and \(d\), then he or she is in the knowledge state \(\{a, c, d\}\)

In principle, \(2^{|Q|}\) potential knowledge states exist. However, the number of knowledge states that actually occur is reduced, since not all subsets of \(Q\) are plausible due to dependencies between the tasks:

• Logical dependencies: the same solution steps that are required for a task also lead to the solution of another task.
• dependencies of the kind that if one (supposedly difficult) task is solved, it is practically certain that another (supposedly easy) task will also be solved (e.g. conveyed by the sequence of the corresponding content in the curriculum).

Formally, a knowledge structure is defined by the pair \((Q, \mathcal{K})\)

• \(Q\): a domain of knowledge
• \(\mathcal{K}\): the set of all plausible knowledge states \(K \in \mathcal{K}\), \(\mathcal{K} \subseteq \mathcal{P}(Q)\) containing at least \(\emptyset, Q \in \mathcal{K}\)

For a formal description of the dependency relations between the tasks in a knowledge domain \(Q\) one can, in the simplest case, define a binary relation \(\preccurlyeq\) on \(Q\) such that \(p \preccurlyeq q\) if and only if based on the correct answer of task \(q\) the correct answer of task \(p\) can be deduced.

The relation \(\preccurlyeq\) is called the precedence relation (or the surmise relation).

Due to the definition of the precedence relation \(\preccurlyeq\) on \(Q\), the following properties arise

• \(\forall p \in Q: p \preccurlyeq p\) (reflexive)
• \(\forall p, q, r \in Q: p \preccurlyeq q \land q \preccurlyeq r \Rightarrow p \preccurlyeq r\) (transitive).

A precedence relation \(\preccurlyeq\) on \(Q\) can therefore be regarded as a quasi-order (a generalisation of the weak order and the partial order).

A knowledge structure \((Q, \mathcal{K})\) that is closed with respect to set union is called a knowledge space.

Assumptions about the underlying learning process are:

• If a person is ready to learn an item, then a person who can solve additional items has already learned the item or is also ready to learn the item (alternatively, if a person is ready to learn an item, then he or she remains so).
  • This implies closure with respect to set union.
• From each knowledge state, the solution of new items can be learned one at a time.
  • This implies a property that allows going from any knowledge state to any other in the knowledge structure in steps of one item (“well-graded”). Not every knowledge space is necessarily well-graded.

If the structure is closed with respect to set union and set intersection, then it is called a quasi-ordinal knowledge space.

For quasi-ordinal knowledge spaces there is a one-to-one correspondence between the knowledge structure and precedence relation.

Motivation

• In practical applications we cannot assume that a student’s response to an item is correct if and only if the student masters it (i.e. if the item is an element of the respective knowledge state).
• There are two types of response errors:
  • careless error, i.e. the response is incorrect although the item is contained in the knowledge state
  • lucky guess, i.e. the response is correct although the item is not contained in the knowledge state.
• In any case, we need to dissociate knowledge states and response patterns.
  • \(R\) denotes a response pattern, which is a subset of \(Q\)
  • \(\mathcal{R} = 2^Q\) denotes the set of all possible response patterns
• In this approach
  • the knowledge state K is a latent construct
  • the response pattern R is a manifest indicator to the knowledge state.
• The conclusion from the observable response pattern to the unobservable knowledge state can only be of a stochastic nature.
• This requires to introduce a probabilistic framework.

A probabilistic knowledge structure (PKS) is defined by specifying

• a knowledge structure \(K\) on a knowledge domain \(Q\) (i.e. a collection \(K \subseteq 2^Q\) with \(\emptyset, Q \in K\))
• a (marginal) distribution \(P(K)\) on the knowledge states \(K \in \mathcal{K}\)
• the conditional probabilities \(P(R | K)\) to observe response pattern \(R\) given knowledge state \(K\) \[P(R | K) = \frac{P(R, K)}{ P(K)}\]

The probability of the response pattern \(R \in \mathcal{R} = 2^Q\) is predicted by (cf. law of total probability)

\[P(R) = \sum\limits_{K \in \mathcal{K}} P(R | K) \cdot P(K)\]

Local Stochastic Independence

Assumptions:

• Given the knowledge state \(K\) of a person
  • the responses are stochastically independent over problems
  • the response to each problem \(q\) only depends on the probabilities
    • \(\beta_q\) of a careless error
    • \(\eta_q\) of a lucky guess
• The probability of the response pattern \(R\) given the knowledge state \(K\) reads

\[P(R | K) = \left(\prod\limits_{q \in K \setminus R} \beta_q \right) \cdot \left(\prod\limits_{q \in K \cap R} (1 - \beta_q) \right) \cdot \left(\prod\limits_{q \in R \setminus K} \eta_q \right) \cdot \left(\prod\limits_{q \in \overline{R} \cap \overline{K}} (1 - \eta_q) \right) \cdot\]

A PKS satisfying these assumptions is called a basic local independence model (BLIM).

Maximum Likelihood Estimation

Basics:

• The data consist of a vector specifying for each subject in a sample of size \(N\) the given response pattern.
• From this we can derive the absolute frequencies \(N_R\) of the patterns \(R \in \mathcal{R}\).
• For a given knowledge structure \(K\) the likelihood is given by \[\mathcal{L}(\beta, \eta; \pi | x) = \prod\limits_{R \in \mathcal{R}} P(R | \beta, \eta, \pi)^{N_R}\] \(\beta = (\beta_q)_{q \in Q}\)
  \(\eta = (\eta_q)_{q \in Q}\)
  \(\pi = (\pi_K)_{K \in \mathcal{K}} \;\; \text{with} \;\; \pi_K = P(K)\)

Determining the maximum likelihood estimates (MLEs) requires to compute the partial derivatives of the log-likelihood with respect to each of the parameters collected in the vectors \(\beta, \eta, \pi\).

• The problems concerning the analytical tractability of this derivation arise from the fact that \(P(R| \mathcal{K}, \beta,\eta, \pi)\) actually is the sum \[P(R | \beta, \eta, \pi) = \sum\limits_{K \in \mathcal{K}} P(R, K | \beta, \eta, \pi)\]
• Doignon & Falmagne (1999) thus resort to numerical optimization techniques.
• A (partial) solution to this problem is provided by the so-called EM algorithm (Heller & Wickelmaier, 2013; Stefanutti & Robusto, 2009).

EM algorithm

• The EM algorithm is an iterative optimization method for providing MLEs of unknown parameters, which proceeds within a so-called incomplete-data framework.

• Considering the given data as incomplete, and (artificially) extending them by including actually unobservable variables (‘unknown data’) often facilitates the computation of the MLEs considerably.

• In the present context we assume that for each subject we observe both the given response pattern \(R\) and the respective knowledge state \(K\) (complete data), thus having available the absolute frequencies \(M_{RK}\) of subjects who are in state \(K\) and produce pattern \(R\).

• The likelihood of the complete data then reads

\[\mathcal{L}(\beta, \eta; \pi | x, y) = \prod\limits_{R \in \mathcal{R}} \prod\limits_{K \in \mathcal{K}} P(R, K | \beta, \eta, \pi)^{M_RK}\]

• The terms containing \(\beta, \eta\) and \(\pi\) respectively, can be maximized independently and MLEs \(\beta^{(t)}, \eta^{(t)}\) and \(\pi^{(t)}\) are obtained.

• In a second step the expected frequencies \(M_{RK}\) are calculated with the updated MLEs \(\beta^{(t)}, \eta^{(t)}\) and \(\pi^{(t)}\) \[\mathcal{E}(M_{RK} ) = N_R · P(K | R, \beta^{(t)}, \eta^{(t)}, \pi^{(t)})\]

• By repeating these two steps, the MLEs converge and the final estimators are obtained.

References

Congratulations

You have finished the tutorial. If you want to learn more exciting concepts of KST, check out the pages of TquanT and QHELP. There you will find more student-developed apps related to KST.