In this post, I would like to introduce you to a problem posed by Bernhard Ganter on the occasion of the 2014 summer school on “Methodology of task design – How to construct exercises for learning”, as well as some code that I wrote in order to get some exemplary solutions.
The following table was handed to all participants of the summer school:
The table displays which of the learners (l1 through l9) managed to solve which test items (a through h). Furthermore, we were told that this table was generated using four different skills, and that each item may be solved by several pair-wise incomparable sets of skills — i.e. if a learner has at least all the skills of one such set, s/he solves the item. The problems posed were the following: Can we reconstruct the skill sets and the learner’s skills, such that the given table results from them? Can we determine the minimal number of skills which are needed in order to produce a given response table?
Get the Code
To do this from the command line, use
git clone https://github.com/Immanuel-Albrecht/analyzeskills.git
In order to compile the program, you have to have libCPROPS 0.1.12 (or newer) installed on your system. Then after cloning or unzipping, do
mkdir build cd build cmake .. make ./analyzeskills ../summerschool.txt
This instructs the program to work on Bernhard Ganter’s example response table.
First, the program test how many learners have pair-wise incomparable response patterns. The result is used to calculate a lower bound of the number of skills involved, due to the fact that learners with comparable skill sets also have comparable response patterns.
Then, the program searches for a skill assignment, such that each item may be solved by several single skills. This is done by the routine
void generate_skill_matrix(matrix *pA, matrix *pB, matrix C) in the following way: A join-base of (partial) responses with respect to the given set of learner’s responses is calculated, then each base element corresponds to a single-skill set which solves all of the respective items. Afterwards, the learner-skill matrix is calculated by assigning every learner all those skills, whose corresponding base vectors contain only items that the learner managed to solve. This solution has the property of having the minimal number of different skill-sets used to explain the resulting response table.
The program produces the following output, first, the matrix A gives the information which item (row) is solved by which skill (column) :
A= ....X ..XX. .XXX. .X.X. XX.X. X.X.. XX... .X...
Second, the matrix B gives the information which learner (row) has which skills (column):
B= ..... ....X .X... X.... ...X. X.XX. ..X.. X.XXX XXXXX
This is a factorization where the given response table M has the form MT = A*BT.
Now, the program tries to reduce the number of different skills involved in the explanation of the response table (which in turn means that there will be more and more-complex skill sets involved) in a step-wise fashion and stops, if no solution exists for some fixed amount of different skills.
The program prints the different possible skill sets that solve each item in the following way:
L1( 0,.) = ..XX L1( 1,.) = X..X \/ X.X. \/ XX.. \/ .XXX L1( 2,.) = .X.X \/ X..X \/ X.X. \/ XX.. L1( 3,.) = .X.X \/ X..X \/ X.X. L1( 4,.) = .X.X \/ .XX. \/ X..X \/ X.X. L1( 5,.) = .XX. \/ X.X. \/ XX.. L1( 6,.) = .X.X \/ .XX. \/ X.X. L1( 7,.) = .X.X
For instance, there is only one way to solve item 0 and it involves the last two skills. Item 1 may be solved by using skill one combined with one of the other skills or by using the last three skills.
Next, the program prints a skill assignment matrix which indicates which learner (row) has which skills (columns).
S1= .... ..XX .X.X .XX. X..X X.X. XX.. X.XX .XXX
In our example, the computation will stop after this solution, since it is impossible to find an explanation of the response with only three skills. (Beware that even if the anti-chain check does not stop the computation, there may be no solution for a given number of skills. In this case, all possibilities will have to be ruled out by the backtracking algorithm that generates the exemplary explanation.)