Building automatic strategies for organising knowledge contained in textbooks has a tremendous potential to enhance meaningful learning. Automatic identi cation of prerequisite relation (PR) between concepts in a textbook is a well-known way for knowledge structuring, yet it is still an open issue. Our research contributes for better understanding and exploring the phenomenon of PR in textbooks, by providing a collection of visualisation techniques for PR exploration and analysis, that we used for the design of and then the re nement of our algorithm for PR extraction.
In our age we are experiencing an increasing availability of learning resources and
self-regulated learning. In this scenario, the development of automatic strategies
for structuring knowledge is motivated by the need of curricula planning. In
particular, organising the knowledge contained in a textbook and structuring it as a
knowledge map that makes an explicit representation of prerequisite
dependencies between concepts has a formidable potential for building intelligent content,
authoring systems for instructional design and e-learning applications [
The PR relation is a dependency relation de ning precedence between two concepts tu and tv: it represents what a learner must know/study (concept tu) before approaching concept tv, where a concept can be seen as an atomic piece of knowledge of the subject domain. By de nition, the main properties of a PR relation are the followings: (1) binary relation: it involves pairs of concepts; (2) anti-re exive relation: concept tu cannot be a prerequisite of itself; (3) transitive relation: if tu tv and tv tz, than tu tz. As a result of these conditions, the key concepts of the textbook can be represented as nodes in a directed acyclic graph G related to each other by means of PR relations.
The e ective integration of visualisation technologies in curricula with the
purpose of facilitating teaching and learning of abstract concepts has been
already investigated (see for instance [
Our research on PR extraction from textbooks is enhanced by the use of Information Visualisation techniques in the following phases: (i) Exploring and discovering insights of PR; (ii) Re ning the algorithm of PR extraction by means of visual analysis of patterns and comparison between gold standard PR graphs vs extracted PR graph.
In the rst phase (i), visualisation analysis techniques were applied to a concept
map manually created by experts. The purpose of map creation was to make
explicit the pedagogical relations among concepts in the textbook, while the aim
of visualisation analysis was to discover new insights into PR. The dataset was
explored through matrix and graph visualisations, both enhanced with ltering
and ordering functions. This analysis supported the de nition of the algorithm
in [
In the second phase (ii), visualisation analysis was applied on a map
automatically extracted from a textbook using the strategy described in [
Most of the information visualisation analysis tools that we propose are
meant for the analyst (e.g., researcher) who intends to discover new insights
or con rm existing hypotheses on the PR. Nevertheless, some of these
techniques/tools give a graphical visualisation that can be potentially useful also
for learners, teachers or instructional designers [
In the following we describe our approach, techniques and data used for visualisation analysis for both the phases described above (i.e., PR exploration in Section 2 and PR extraction and algorithm re nement in Section 3), and for each phase we discuss the results. The visualisation analysis tools proposed in this paper are available at (teldh.dibris.unige.it/projects/). 2
Gold Dataset Five experts were asked to read a network related chapter from
a Computer Science textbook [
Concept Graphs. Several variants of network-like representations (see for instance Fig. 1) have been used during PR exploration to visually detect elements such as loops (as resulting from human errors during the process of annotation) and transitive edges. However, as the dataset becomes larger, a concept graph becomes harder to explore, especially if no ltering functions are implemented. In this case, other forms of visualisation are more e ective.
Concept Matrix Chart. This is a dynamic and interactive representation of a jT j jT j asymmetric adjacency matrix M , where each colored cell Mi;j represents a prerequisite relation between concepts i and j (see Fig. 2). Di erent colors can help to visually di erentiate clusters of concepts, as they have been recognised by a community detection algorithm 1. Intuitively these clusters shows 1 In our implementation depicted in Fig.2 we used the Infomap algorithm. the membership of a concept within a thematic unit (e.g., concepts related to network security, or to network classi cation, and so on). Di erent shades of the same color can be used to encode di erent degrees of inter-agreement among annotators (if M is used to visually depict a gold standard) or di erent scores (if M represents the output of an automatic method). The matrix arrangement is dynamic, i.e. the concepts along the matrix can be sorted according to di erent criteria: order of rst appearance in the text, alphabetical order, frequency and cluster membership.
Discussions and Results. The analysis performed on the concept graph built from the gold standard allowed to reveal interesting properties concerning graph's transitivity, topology and connectivity. By comparing subgraphs belonging to di erent experts, we discovered that the number of transitive edges largely varies from annotator to annotator. Thanks to this observation, we discussed the phenomenon with the annotators, ascertaining that their choices depend on a di erent interpretation given to the meaning of a distant or weak prerequisite relation. Some of the experts tend to think in terms of graph paths, while others in terms of didactic sequences. As an example, the relation between \computer" and \local area network" (LAN) can be seen on the one hand as a transitive relation (if one has in mind the path in the graph connecting the rst concept to the second by means of several bridging concepts in the middle), but on the other hand it can also be seen as a direct prerequisite relation (if one realises that \computer" is a fundamental notion, without which a student cannot possibly hope to understand what a LAN is). Concerning the topology, graph visualisation con rmed our intuition that prerequisite relations do not necessarily replicate ontological relations. As an example, let us take a pair of concepts such as \client side" and \server side": in a domain ontology these would very probably be represented as sibling nodes, but we cannot always expect the same behaviour when approaching a didactic text. In similar contexts, even if a co-requisite relation would seem the most natural choice of presenting these kind of concepts (i.e., the author explains them together, and the former is not a prerequisite of the latter, nor vice versa), a prerequisite relation is still possible (e.g., if the author rst explains the former and then relies on the knowledge gained by the reader to explain the latter). As can be noted in the graph, hypernym-hyponym and holonym-meronym relations deserve a similar discussion. External lexical resources would typically categorise pairs of words such as \device" (broader, hence at top-level) and \hub" (narrower, hence at bottom-level) or \byte" (the whole) and \bit" (the part of) in a hierarchical manner. Conversely, in textbooks (sometimes even in the same textbook) we can easily nd both top-down and bottom-up explanations. Lastly, the connectivity of the graph (which we discussed above as in uenced by the annotators' perception of what a prerequisite relation is) also largely depends on the annotator's level of domain knowledge.
The analysis performed on the Concept Matrix Chart built from the gold dataset revealed an important insight for the direction of the prerequisite relation. After applying the rst sorting criterion (i.e., order of rst appearance), the matrix tends towards an upper triangular, with colored cells mostly concentrated in the area that is slightly above the diagonal. This pattern con rms the hypothesis that prerequisite relation is highly correlated with co-occurrence and temporal order . Consequently, the temporal order of concepts is a reliable criterion to assign a direction to relations that are automatically extracted by an algorithm. The most notable exception in this pattern is represented by concepts such as \computer" or \network", which tend to be spread across the entire row of the matrix. However, this phenomenon is due to the fact that these are the main concepts of the whole chapter of the textbook, hence they frequently reoccur along the entire text and moreover they could commonly be prerequisites (rather than subsidiaries) of many other concepts.
The analyses above supported the de nition of the algorithm presented in [
Burst Dataset The method devised to obtain the Burst Map dataset exploits
burst analysis [
Burst Gantt Chart. This is a Gantt diagram showing bursts of concepts along the horizontal temporal axis (time can be measured in sentences or tokens), while concepts are arranged along the vertical axis, according to their temporal order (see Fig. 4). The main purpose of this visualisation is facilitating the analysis of temporal patterns between intervals of di erent concepts.
Moreover, as the chart incorporates data taken from three di erent sources (the output of the burst algorithm, the gold dataset and the textbook itself), we can use it to perform further kinds of analysis and textbook exploration. For instance, by clicking on a concept label in the vertical axis, we can compare Allen's temporal relations and gold relations and thus investigate possible matches (see Fig. 5).
By clicking on a burst we can instead read the portion of the textbook covered by that interval (see Fig. 6). This procedure enables us to easily nd blocks of sentences where a concept is introduced for the rst time, then resumed (with or without another concept) and eventually left behind. Vertical partition lines have been drawn to indicate boundaries between sections, while other sorts of markers can be traced near the temporal axis to identify sequences of sentences that according to experts are particularly rich of prerequisite relations.
Concept Graph with Allen's Relations. For investigating Allen's temporal patterns and prerequisite relations, we also propose to transform the Burst Gantt Chart into a weighted directed and edge-labeled graph GA, where edges are labelled using Allen's algebra. For each two distinct concepts X and Y in the Burst Gantt Chart, if a pair of bursts Bx;i and By;j is related n times by Allen's relation a, we represent this con guration in GA as X !(a;n) Y , where (a; n) are the edge label and edge weight respectively.
In this representation, bursts are collapsed into one node for each concept, while multiple edges are maintained and a weight is assigned to them according to how many times that temporal relation occurs between bursts of those two concepts. The aim of this conversion is producing a graph that can be compared with the gold standard graph, as a means for achieving more con dence on the weights that should be assigned to the di erent Allen's patterns. The result of the conversion is a highly connected graph which needs to be explored with lters, e.g., ltering concepts that have di erent relevance, or ltering by speci c Allen's relation or combination of relations, as well as ltering according to edges or nodes weights. As displayed in Fig. 7, di erent colors for edges show di erent Allen's relations, while the width is proportional to the number of times an Allen's relation is founded between two concepts. The dimension of a node is proportional to the importance of the concept (this value can be measured using frequency, relevance or summing all the lengths of its bursting periods in the text). In our implementation we also used di erent colors to encode concepts that in the gold standard are sources, sinks or internal nodes. In the rst case the node has zero indegree and this means that for annotators it represents a primary notion|a concept already known by the learner; in the second case the node has zero outdegree and thus it may be intended as a nal learning outcome.
Discussions and Results. Allen's patterns allow to capture PR relations
quite well [
Therefore, the Burst Gantt Chart was used to analyse possible combinations of Allen's patterns and more sophisticated conditions that should be satis ed between bursts of two concepts. As a result of the aforementioned analyses, we observed that Allen's Algebra, as used in our Burst-based algorithm, is likely to fail when an Allen relation is identi ed between bursts of concepts X and Y, but no bursts of X are present in the text before that relation. This is consistent with the intuitive consideration that concept X should be introduced before Y in order to be a prerequisite of Y, and thus for two concepts X and Y, a necessary but not su cient condition in order to have X prerequisite of Y is that X should be previously explained, i.e., jBX j > 1. Considering bursts instead of simple occurrences of a term allows to exclude cases where X occurs before Y and X is not really explained but rather simply introduced (the analysis of the text showed for example several cases where the content of the next section is mentioned before, as a guide for the reader).
As future work, we plan to implement re nements of the algorithm that take this into account. This is not trivial, since for instance the condition jBX j > 1 does not apply in cases where X is a primary notion, namely a concept already known by the learner as background knowledge.
Furthermore, we plan to use Concept Allen Graph to explore combinations of Allen's patterns by ltering them in conjunction or disjunction and comparing the results with the gold standard. 4
In this paper we presented a collection of visualisation techniques conceived to help researchers and analysts in their e ort of better understanding the issue of prerequisite dependencies in textbooks and developing more powerful strategies for the automatic extraction, with the nal aim of giving a contribution to the eld of intelligent textbooks. The results of our analysis support the hypotheses regarding the correlation between PR direction and temporal concept ordering. Furthermore, visual analysis of the PR algorithm provides valid insights on the burst patterns combination. The tools for PR exploration presented in this paper are available online2 as a support for the community of researchers working on the analysis of prerequisite relations.
Our future work includes enhancing these techniques with further functionalities and applying them, in conjunction with new techniques as well, in di erent contexts of use and a larger variety of educational texts. New functionalities can be implemented in order to broaden the scope of practice allowed by the visualisation tools. For instance, the Gantt Chart could also be used as an instrument 2 Prerequisite Extraction from TextBooks at http://teldh.dibris.unige.it/projects/ for doing validation, i.e. thanks to it the expert can validate the individual patterns revealed by the algorithm. The Matrix Chart can be used not only for exploring PR in the experts' annotation (i.e. phase (i)), but also for algorithm re nement (phase (ii)), for example in cases of co-occurrence and/or temporal based algorithms. Finally, we are also working on techniques that more directly address the needs of learners and teachers in their common activities of selecting, accessing, exploring and organising learning materials.