Techniques for Sampling Quasi-orders

In educational theories, e.g., learning spaces, mastery dependencies between test items are represented as reflexive and transitive binary relations, i.e., quasi-orders, on the item set of a knowledge domain. Item dependencies can be used for efficient adaptive knowledge assessment and derived through exploratory data analysis, for example by algorithms of item tree analysis. To compare item tree analysis methods, typically large-scale simulation studies are employed, with samples of randomly generated quasi-orders at their basis and assumed to underlie the data. In this context, a serious problem is the fact that all of the algorithms are sensitive to the underlying quasi-order structure. Thus, it is crucial to base any simulation study that aims at comparing the algorithms in a reliable manner on representative samples, meaning that each quasi-order in the population is equally likely to be selected as part of a sample. Suboptimal sampling strategies were considered in previous studies leading to biased conclusions. In this paper, we discuss sampling techniques that allow us to generate representative, or close to representative, random quasi-orders. The item tree analysis methods are compared on ten items with a representative, large sample of quasi-orders, thereby supporting their invariant ordering