Aggregating of Learning Object Units Derived from a Generative Learning Object

Aggregating and sequencing of the content units is at the core of e-learning theories and standards. We discuss the aggregating/sequencing problems in the context of using generative learning objects (GLOs). Proposed by Boyle, Morales. Leeder in 2004. GLOs provide more capabilities, focus on quality issues, and introduce a solid basis for a marked improvement in productivity. We use meta-programming techniques to specify GLOs and then to automatically generate LO units on demand. Aggregating of the generated units to form a compound at a higher granularity level can be performed in various ways depending on the selected criteria or their trade-offs (e.g., complexity, granularity level, semantic density, time constraints, capabilities of modelling the learning process, etc.) that enable to evaluate units in advance. We describe aggregating as an internal sequencing of the content units derived from a GLO. Our contribution is a formal graph-based model to specify the problem when the variability of LO units is large. First we formulate the problem and consider properties of the proposed model; and then we analyze a case study, implementation capabilities, and evaluate the approach for e-learning.

Introduction
In general, learning or teaching process consists of three interrelated elements: competence, activity/process and topic/content. The content is to be learned or delivered within the process which is restricted in time dimension and can be split in time-related phases (e.g., due to the physical and methodological reasons). On the other hand, the content itself is not a monolithic structure, rather it consists of pieces that are known in e-learning as learning objects (further LOs or LO) (McGreal, 2004;Northrup, 2007). One can image that LOs of a given topic are linked (usually implicitly) with learning/teaching phases within the process. LOs and aggregating/sequencing/packaging of the content are the most essential terms through which we express the fundamental issues (i.e., pedagogyrelated, psychology-related aspects) of the process: what is to be learnt/ taught and in which way (i.e., logical sequence) the process is to be delivered and organized. These terms and the processes they describe are at the focus of e-learning standards (e.g., LTSC, 2002;LOM, 2002;SCORM, 2004) and learning theories such as the one proposed by Wiley (2000aWiley ( , 2000b. Typically LOs are dealt with (or should be dealt with) from the reuse perspective because the reuse strategy can ensure a higher productivity, better quality and wider capabilities and effectiveness of use. Indeed today technology advances enable teachers and course designers to create the content in a variety of versions. Modifications, changes and adaptations of the content are common reuse activities. The need for adaptation increases with technology advances and expansion of the e-learning domain. If adaptations are done ad hoc, this may lead to the uncontrolled growth of similar versions causing additional difficulties in storing, sharing and reusing. If adaptations can be done automatically, we have a more powerful kind of reuse, called generative reuse. Recently Boyle, Morales, Leeder et al. (Boyle et al., 2004;Morales, 2005) have proposed the concept of generative learning objects (GLOs), which is based on separating the learning design from the instantiation of the LO content and using templates as a generative technology. The approach provides more capabilities at a larger extent, focuses on quality issues, and introduces a solid basis for a marked improvement in productivity.
We have extended the capabilities of GLOs by introducing meta-programming, a more powerful generative technology (Štuikys and Damaševičius, 2008). Using this technology a designer can, at a larger extent, firstly to specify a family of the related LO units by describing various aspects (through the use of meta-data relevant to the topic, which support modifications of the content). And then, a user can automatically generate from the GLO specification either a concrete LO unit on demand depending on the meta-data values or the whole family (sub-family) of the LO units. Thus GLOs (a) enlarge the space of variants of the content to be delivered substantially, and (b) increase the role of aggregating and sequencing of the content at the larger extent.
The aim of the paper is to consider the aggregating and sequencing problems of the content units (i.e., LOs) within the given topic, which are derived from the specification of the GLO. Our contribution is a formalized graph-based model which brings a solid background for solving the aggregating/sequencing problem when the space of LO units is large. Sequencing is described as a partial case of the aggregating problem (that explains why we use the compound term "aggregating/sequencing" in the paper). The proposed model requires first to evaluate LO units quantitatively, and then it serves as a basis to construct and solve the problem. Furthermore, the model enables to optimize the solution in a delivery process (if criteria of the process are well-defined and an optimization technique is selected). To our knowledge, the aggregating/sequencing problem in the context of GLOs that are described using meta-programming techniques is considered for the first time in the e-learning literature.
The rest of the paper is organized as follows. Section 2 analyzes related works. Section 3 introduces the basic assumptions to the problem under consideration. Section 4 presents definitions of the terms that are important to understand the introduced model. Section 5 formulates the aggregating/sequencing problem. Section 6 describes some properties of the model. Section 7 provides a case study by series of examples in order to approve the theoretic statements of the approach. Section 8 summarizes and evaluates the results. Section 9 provides conclusions and outlines the future work.

Related Works
Since there is a wide spectrum of publications on LOs in the e-learning literature and we deal with a specific topic in the paper, we restrict ourselves with those LO-related publications that either outline the context of the topic or have direct links with the topic. As a result, we use the following categorization scheme of the analyzed sources: 1) general issues (context) related to LOs, such as definition, reuse, taxonomy and design; 2) GLOrelated sources including their technological support; 3) Sequencing-related sources (pedagogy and technology related).
Stream 1. Taxonomy for definitions, characteristics and applications of LOs can be found in Rossano et al. (2005). Papers Nugent et al. (2005), Nortrup (2007) analyze the design, development and validation of learning objects. The paper Altun and Askar (2008) focuses on the granularity aspects and affirms that ontologies provide guideline for instruction designers to address the issue of granularization. Their model proposes a separation of learning expectations as concepts and skills based on their ontological relations. The paper Huddlestone and Pike (2005) proposes a four-tier model (strategic reuse, operational reuse, contextual reuse, structural reuse) for making reuse happen in practice. IEEE Standard for Learning Object Metadata is presented in (LTSC, 2002). The paper Memmel et al. (2007) discusses various approaches to LO oriented instructional design.
Stream 2. As it has been already stated, Boyle et al. Boyle et al. (2004), Morales et al. (2005) are pioneers of the GLO concept. The authors interpret this kind of the e-learning content as the next generation of learning objects because of their capabilities to ensure better quality and higher productivity (Boyle et al., 2004). The other paper Boyle et al. (2008) provides a conceptual framework that can be used to understand, to author and to adapt GLOs. The authors argue that a major pedagogical issue is the desire of tutors to adapt and not merely reuse learning object. In this context, a technological support to specify and implement adaptations and modifications becomes extremely important. The paper Štuikys and Damaševičius (2008) suggests 1) specifying GLOs at a higher abstraction level using feature diagrams and 2) implementing GLOs using meta-programming techniques. One can learn more about feature diagrams in Schobbens et al., (2006) and more about meta-programming techniques in Sheard (2001). Kramer (2009) considers a process for generating Interactive Learning Objects from configurable samples.
Stream 3. The Wiley's sequencing approach is connected to instructional design theories. Sequencing of LOs occurs at 3 levels: sequencing of work models, sequencing of case types, and sequencing of specific problems (Wiley, 2000a(Wiley, , 2000b. The basic principles are "from simplest LOs" to "more complex LOs" and LOs should be "sequenced according to their level and type, and in order to promote transfer when possible". In SCORM R 2004 a new book was added, titled "Sequencing and Navigation", which describes approaches to control the way the learner interacts with the learning object based on the IMS Simple Sequencing specifications (IMS PCK and SS, 2003). The paper Alvarez and Montesinos (2006) considers the sequencing problem at the tool level. In order to better understand our approach presented in this paper one can learn more about basics of the graph theory and sequencing-related algorithms from Cormen et al. (2001).
The related works should be considered as a context to our approach that is described through assumptions, definition of basic terms, problem and model statement, analysis of properties of the aggregating/sequencing model and a case study.

Assumptions
The assumptions relate to the properties of GLOs, which are due to the use of heterogeneous meta-programming techniques. They are as follows: 1. The given GLO is designed for reuse in a much wider context than it is needed for a concrete application. In other words, GLOs describe the space of relative units of learning for possible case uses. 2. The content is highly structured into related pieces called LO units (i.e., units of learning) that are generated on demand through the specification of meta-data values by the user. More specifically, structuring of LOs is also known as a granularization in e-learning. We assume that units of learning are derived from a GLO. 3. It is possible to re-generate units of learning with new aspects (meta-data values), if the GLO specification is complete. Otherwise, the GLO is to be extended or re-designed. 4. It is possible to prune the generated LO units or even to introduce new variants of units externally (i.e., from other sources). 5. In general, a LO unit (either it was derived from the GLO or was introduced externally) has a value which may be considered from different views (social, pedagogical, topic-related, etc.). Even if a user (i.e., teacher or learner) do not estimate the value in advance explicitly, he/she uses some estimates implicitly (e.g., user always estimates the time slot needed for delivering or learning). 6. In general, aggregating/sequencing of the content is undependable of the way in which the LOs are created and upon the space of their units. But when the space of the content variants enlarges (as it is in the case of using GLOs), the problem of aggregating/sequencing becomes more complicated and the necessity to deal with it increases dramatically. The more complicated problem the greater need for its formalization and automation is. 7. Our intention is to focus on technology-based theoretical aspects of aggregating/sequencing problem; however, pedagogy-based aspects are seen as fundamental requirements though they are not always presented explicitly in the paper.

Definitions
Here we define the terms used in our approach. Since it is difficult to define two basic terms, i.e., Generative Learning Object (GLO) and LO unit only from the one perspective precisely, we use a multidimensional scheme for the definition of the terms here. This scheme has already been applied in Štuikys et al. (2009). Note that the terms LO and LO unit are treated as synonymous throughout the paper.
DEFINITION 1. In general, Learning Object is defined as small, stand-alone, mediated unit of a content that can be reused in multiple instructional contexts, serving as building blocks to develop higher-level compounds (e.g., lessons, modules, etc.) (Nugent et al., 2006). Wiley (2000a) defines a learning object clearly as "any digital resource that can be reused to support learning". When reused, such units are combined in various ways leading to the great variability of the learning content.
DEFINITION 2. From the technological perspective, GLO is a higher-level program (meta-program), i.e., an executable specification developed using some generative technology. In that aspect, GLO can be also conceived as a program generator allowing generating LO units on demand (meta-designer's view).
DEFINITION 2A. From the structural viewpoint, GLO is a compound (also can be called meta-program or meta-specification) that consists of two interrelated parts: meta-data (meta-interface) and meta-body. Meta-data are for specifying the meta-parameter values to support generation (this semantics of the term "meta-data" differs from the one used in e-learning literature, where the term describes storing, searching and sharing aspects of LOs). Meta-body describes the content variants dependent on meta-parameter values (see Section 7, for examples).
DEFINITION 2B. From the instructor's (teacher's) and learner's viewpoint (pedagogical perspective), GLO is a set of related LO units (or a qualified in somewhat way sequence of LO units).
DEFINITION 2C. From the methodological viewpoint, GLO is a highly reusable structure that enables ensuring higher productivity and quality of LOs, thus focusing not only on component-based reuse but also moving methodological efforts in the e-learning domain towards generative reuse, which focuses on variability of the domain and generation.
DEFINITION 2D. From the e-learning perspective, GLO is an extension of the LO concept, the fundamental concept of e-learning, in the technological, methodological and pedagogical aspects, thus bringing new capabilities (e.g., in terms of higher productivity and quality for e-learning and also rising new challenges) that should be understood and studied.
DEFINITION 3. LO unit is a concrete LO that is coded within the GLO specification in a specific way using some technology (e.g., meta-programming).
DEFINITION 3A. Derivative LO is a learning unit derived from the given GLO through the generating process that is supported by a given generative technology.
DEFINITION 3B. Model of the derivative LO is a set of (meta-)parameter values which are extracted from the pre-specified meta-data (meta-interface) of the GLO in such a manner that for each meta-parameter there is identified the only one its value. Since the set of parameter values describes the functionality of the LO very abstractly without details about the content, the model is treated as a high-level model.
DEFINITION 4. Set of derivative LOs (further it is denoted as a set S) is a set of LO units generated from the given GLO and then selected for a particular context of use. The selection is needed because, in general, the GLO may specify a much wider space of LO units that are needed for the given context.
DEFINITION 5. Aggregating of learning objects through sequencing is an arrangement of the learning units within the selected derivative set S according to some relation order between any pair of LO units (further we treat the selected derivative set simply as a set S).
DEFINITION 6. Relation order among two objects L i and L j is a propositional relation with the values true (or 1) if the objects are semantically linked and, from the pedagogical view, should appear one after another, and with the value false (or 0), otherwise (see also Definition 10).
DEFINITION 7. Role of a LO is identified as a property of the LO, which is important to the external system or actor to express some particular aspects of using the LO. Two LO units among the selected set of LOs have specific roles. These LOs are called as initial LO and terminal LO, adequately.
is the one which is to be shown (learnt) first in the sequence S within the learning process that per se is identified as a manageable (by an external actor, i.e., learner, teacher, or learning system) sequence of LOs. The role of the initial LO can be changed in the concrete context of use.
is the one which is to be shown (learnt) at the end of the sequence of LOs within the learning process (or its phase). For example, terminal LO L T can be understood as a process of providing the summary or conclusions of a topic. The role of the terminal LO can be changed in the concrete context of use.
DEFINITION 10. Two LOs L i , L j are called to be directly ordered in a given sequence if there is such a logical relation that object L j appears in the sequence only after object L i , otherwise they are not directly ordered or they have not a logical sequence. In terms of the propositional logic, two directly ordered DEFINITION 11. Two LOs L i , L j are called to be mutually ordered in a given sequence S (L i , L j ∈ S) if there is such a logical relation that object L j appears in the sequence after object L i , and object L i appears in the sequence after object L j . In terms of the propositional logic, two mutually ordered , is a measure for estimating and expressing some quantitative characteristics of the given LO L i , where index k indicates a characteristic type from the set P (k ∈ P ) of the given attributes (e.g., granularity level, semantic density, interactivity level, etc. (LTSC, 2002)).
DEFINITION 13. Aggregating/sequencing model of the given set S of LOs is a directed graph G(V, U ), where the set of nodes V represents a member of S, i.e., represents the ordering relationship, i.e., the branch exits only if two LOs L i , L j either are directly ordered or are mutually ordered. (It is important to note that mutual ordering is introduced for generalization purposes admitting its value in other context, but not in this paper).
We identify two kinds of aggregating/sequencing model: the node-weighted graph G(V w , U) and the arc (branch)-weighted graph G(V, U w ).
DEFINITION 15. Aggregate is a set of LO units that lay on the route from the initial LO to the terminal LO. DEFINITION 16. Higher-level granularity aggregate is a compound of a lower-level aggregates that are formed through the concatenation of two or more different routes from L O to L T within the model.
Equivalence property of two models G(V w , U) and G(V, U w ). Let be given the initial graph G(V w , U) without loops (see Fig. 1a). Next, we perform the following transformations of the graph G(V w , U): 1) we draw the arc from the node L T to the node L O (L O , L T ∈ S); 2) we form the model G(V, U w ) by labelling branches with weights as shown (see Fig. 1b). Now we can proof the following statement.

Statement. Two models G(V w , U) and G(V, U w ) are equivalent against some evaluation function that evaluates weighted routes.
The proof is demonstrated by an arbitrary model (see Fig. 1). Indeed it is easy to construct 1) all possible routes from L O to L T that are evaluated by the sum of node weights and 2) all possible arc-weighted loops that starts and ends at the node L O . And then, by comparing evaluating functions, one can be convinced that they are equal against the function value (w 0 + w 3 + w 2 + w T , see the bolded route and loop in Fig. 1a and 1b, respectively). Now it is possible to formulate the aggregating/sequencing problem precisely as it follows below.

Problem Statement
Given the connectivity matrix C of a weighted model G(V w , U)/G(V, U w ), which is derived from the set S (the latter is derived from the given generative LO (GLO)). Two nodes in the model, To find such a route D from the node v O to the node v T in the model G(V w , U) or (find such a loop D that begins and ends at the node v O in the model G(V, U w )) that satisfies the following conditions: 1) x ij = 1, if and only if the path goes from the node where P is a set of weights that identifies the value of LOs; C = c ij n×n , where C is the asymmetric connectivity matrix of the graph is a constraint function dependent on weights w k ij ; and F 0 is the fixed constraint value for the function (e.g., the duration of an academic hour if the time is selected as a constraint argument, etc.). Reader should not be confused by two slightly different notations used: w k i and w k ij . The first means the weight of the node L i , while the second means the weight of an output branch (arc) from the node L i to the node L j . See also the numerical example in Section 7 (Example 6, for more details).

Properties of Aggregating/Sequencing Model
The model introduced in the paper expresses specific aspects of LOs that are slightly different from those LOs that are not derived from the given GLO but are composed in some other way, for example, in ad hoc manner. Of course, some properties of the sequence are orthogonal and do not depend on the way in which they were created. The aim of the Section is to identify the specific properties as well as common properties of series of LO units used in some teaching or learning environment. The emphasis is given to semantic of using the whole series of LOs (i.e., an aggregate) rather than a particular unit.
1. Since the model is based on the use of GLO, some properties of LOs within the model are inherited from the GLO. Namely, the model describes the features of LOs units that are highly interrelated and have a low granularity level (i.e., the units are small objects). Next the cardinality number of the model, that is, the number of vertex |V | of the graph G(V w , U) may vary in a wide extent because of the GLO can be seen as an evolving entity and new features can be easily added and then a new set of units can be automatically generated. 2. The aggregating/sequencing model describes a family of the selected LO units that are arranged according to the needs and intention of a teacher/course designer or a learner. More precisely, the model identifies the possible sequences of the related learning objects; a particular sequence as an aggregate can be identified and then can be used in a given context. The whole model describes a variety of possible variants (i.e., the whole package) for reuse meaning a wide scope of use. 3. A LO derived from the model have three important properties: the role, the value, and the order (or a position within the formed sequence). The properties are interrelated in somewhat way. For example, the initial LO is the first, and the terminal LO is the last in the sequenced list of the LOs described by the model. 4. The role of the initial and the terminal LOs is to specify the beginning and the end of a content delivery process because any well-defined process should first be instantiated, and then, after some time should be terminated. But more importantly, these objects may also be responsible for decision making procedures. 5. The initial and the terminal LOs can be introduced in the model, when the model is created, in two ways: either these are generated from the given GLO directly (if such a feature was anticipated in the GLO design specification), or it is introduced by an actor externally (if such a feature was missed when the GLO was designed).
6. The initial node v O and terminal node v T have the following property: j = 1 ≡ j = v O &j = n ≡ j = v T , where j = 1, 2, . . . , n. 7. The role of the initial LO is to specify such a common data as the topic title, the aim of the topic, the capabilities or possible variants of the sequence. The role of the terminal LO is either to summarize the essential result of learning/teaching, to present some conclusions or to describe some states for the management action (e.g., to initiate the repeat of process from the beginning). 8. The value of a LO within the model is estimated by the weight. In general, the weight is a vector which coordinates may identify various attributes such as time needed to present, size (granularity level), complexity of the LO, readiness or level to which the given object supports the paradigm 'learning by doing', etc. By 'learning by doing' we mean modelling capabilities (e.g., push a bottom and record some result). Some attributes, such as complexity, may differ from the learner's and teacher's viewpoints. Thus the weight where K is a set of pre-defined attributes of LOs. 9. The aggregating/sequencing model, i.e., either the graph G(V w , U) or G(V, U w ) is said to be correctly constructed if the following conditions are valid: ; c) nodes/arcs are weighted and coordinates of the weight vector for each node/arc is ordered according to the same ordering rule (criteria); d) there are no mutually ordered nodes (in order to avoid internal cycles, see Definition 11). 10. Arcs, i.e., oriented branches of the graph, which pre-specify possible routes in the model, are introduced by the course designer keeping in mind learning/teaching theories (Wiley, 2000a). But it should be also taken into account that ordering of the graph highly depends on the context, i.e., on the internal structure of the content to be designed. 11. The weights of the nodes satisfy the following conditions (here we consider the node-weight model): i.e., some coordinates may be zero; where w ko io is a pre-defined value specific for each LO (node) and for each coordinate of the LO (node), k 1 (i.e., as a partial case the weight may have the only one coordinate). 12. Weights are calculated according to the pre-specified rules for each criterion (e.g., time, complexity, semantic density, size, readiness to implement paradigm 'learning by doing', etc.). Some of them may be very simple. For example, if a given LO supports the paradigm 'learning by doing' (it is usually clear from the context, say, when it is needed to solve a problem) then the coordinate is equal to 1, otherwise it is equal to 0. More specifically, the calculation can be seen as a planning task of the content delivery (LTSC, 2002).
13. The route in the model from the initial vertex (node) v O to the terminal node v T is estimated by the same coordinate at a time. The sum of the coordinates (i.e., the sum of the selected weights of vertexes in the route) is a function whose value is to be either minimized or maximized depending on the context. This depends on the selected coordinate or the intention of the teacher/learner. Thus the multiple routes can be identified, each expressing different aspects of learning. 14. Formally the optimized route (or loop) (i.e., the aggregate) in the given model models a learning or teaching sub-process in terms of content delivery. A set of optimized routes (loops) (i.e., compound of aggregates) models the whole learning or teaching delivery process at a higher abstraction (granularity) level, thus creating possibilities to automate the process. 15. The identification of routes (loops) in the aggregating/sequencing model can be also viewed as a weight-based integrating process of combining the smallest LOs (in other words, derivatives from the given GLO) into a higher-level compound (e.g., the content of a lecture or the other form of teaching) according to the prespecified rules relevant to the given context of learning or teaching. 16. Some properties of the aggregating/sequencing model (e.g., a number of units for the use in a concrete context, weights of units or partially an order for the formation of sequences) may be obtained from the specification of the given GLO if such features have been anticipated in the design phase.

A Case Study to Illustrate and Approve the Introduced Theoretical Statements
Let be given the initial specification of a GLO (in our case "Sorting algorithms"), which is described using the notation of feature diagrams (see Fig. 2 and Štuikys and Damaševičius (2008), for more details). The model specifies at the high abstraction level (i.e., in the human readable form) the following aspects of GLO: scope, commonality and variability; essential features of the topic, their relationships and constraints. Note that not all constraints are depicted in the model (for simplicity reasons). For example, to explain the principles of sorting it is needed to use the random arrangement of arrays (Principles <require> Random), while teaching/learning effectiveness of the algorithms require all kinds of population (there is no constraints). The aim is to explain how the theoretical statements work in the context of their use in some virtual setting. The case study provides analysis of examples. As examples are illustrative we try to simplify the problem when describing its implementation. Thus not all constraints of the initial specification (Fig. 2) Fig. 3) explains the technological implementation of the given specification (Fig. 2). The structure of the GLO 'Sorting algorithms' consists of meta-data (meta-interface, Fig. 3a) and meta-body (Fig. 3b). The latter is implemented using: a) Open PROMOL as a meta-language (Štuikys et al., 2002) to describe the variability Fig. 2. Feature-based model of GLO "Sorting algorithms" (taken from a course of Computer Science). and b) JavaScript/HTML to describe the visibility of LO units (while generated) via Internet. The implementation details, however, are hidden for simplicity reasons (i.e., the specification is presented as a black-box model without implementation details). Using the specification, one can generate about 648 derivative LO units (648 = 2· 3· 3· 6· 2· 3, where numbers are variants for each meta-parameter, see Fig. 3a; note that this calculation is made ignoring the constraint: "Principles <require> Block-diagram" because the constraint is not implemented in the meta-interface in Fig. 3). Such a large number of LO units tells us that the specification of the GLO was designed for reuse in a wide context which overpasses the needs of a concrete context. EXAMPLE 2 explains an adaptation of the initial GLO for a narrowed context of use. One can understand the narrowing procedure by comparing meta-interfaces (cf. Fig. 3a and Fig. 4). Note that the specification (Fig. 4) has been changed by adding meta-parameters for generating the beginning (i.e., the initial LO) and the end (i.e., the terminal LO) of a LO unit.
EXAMPLE 3 presents a model of a derivative LO derived from the simplified GLO (see Fig. 3). The model is described as a set of all meta-parameters with one value for each meta-parameter: {EXAMPLE 3: begin := 1; goal := 1; algorithm := 1; language := 1; size := 5; order := 1; pop := 1; end := 1;}. A set of such models (see EXAMPLE 3) enables to specify an aggregate of LO or the pre-specified routes in the given graph, as it will be explained later.
EXAMPLE 4 (see Fig. 5a) gives the content of the unit the model of which is described by Example 3. The first LO unit (note that it has the internal structural units named by bolded titles, see Fig. 5a) demonstrates the following sequencing theory aspects: 1) formulation of learning objectives; 2) a more simple item is to be learnt first (e.g., principles of sorting should be learnt first because of a) sequencing logic and b) simpler array, simpler language, i.e., Pascal is simpler than C++, and c) there is no capabilities for 'learning by doing'; next unit (see Fig. 5b) should be learnt after the first since it is more complex  (e.g., it contains learning of effectiveness of the algorithm with the capabilities 'learning by doing'). For example, two buttons 'Generate', 'Bubble sort' (see Fig. 5b) enable the user to model the sorting process, to write the sorting efficiency values, to compare different values for different arrays, and learn about efficiency that follows from the users actions. NOTE 1. Though learning of sorting principles requires of using the block-diagram (see Fig. 2), the implementation in Fig. 5a is described by showing the Pascal program. This is done for simplicity (in order to save space in Fig. 5a and to reduce the number of units in Table 1 (also in Fig. 6)). EXAMPLE 5 (see Table 1) enumerates LO units, their model, and weights for two criteria. It is assumed that the initial and terminal LOs, i.e., L O , L T ∈ S were introduced externally, but not from the meta-specification (see Fig. 4). It is why we have 18 LO units, but not 16, as it follow from Fig. 4. Note that the initial and terminal LOs identify the beginning and the end of a sequence (aggregate) but not the beginning and the end of a concrete unit (in this implementation, we have introduced the beginning and the end within the LO unit for clearness). The numerical figures (time in minutes) are illustrative. Their calculation depends on the social context, i.e. depends on the teacher's intention, students' previous knowledge of the topic, etc. The other weight ('learning by doing') Fig. 5. Derivative LO units: (a) that has no support for 'learning by doing' and (b) that has a support for 'learning by doing'. is evaluated using the simplest form (i.e., Y/N, or 1/0). In the other context, one can estimate those capabilities using a more complex measure, such as a level (i.e., the extent expressed by a wider numerical range). NOTE 2. L 1 corresponds to the LO unit in Fig. 5a. L 9 corresponds to the LO unit given in Fig. 5b.  Fig. 6) presents the aggregating/sequencing model that corresponds to the set S of derivative LOs units (|S| = 2 * 2 * 1 * 2 * 1 * 2 + 2 = 18, see Fig. 5 and Table 1). For simplicity reasons, weights have the only two coordinates. We use the nodeweighted graph for simplicity reasons (see Fig. 1). In general, the ordering relation, i.e., the directed arcs should be identified according to a learning theory. But a designer of the content can easily change the ordering relation (i.e., he/she can decide what arcs are to be introduced as being the most relevant to his/her context). Thus the ordering within the model by directed arcs (see Fig. 6) should be treated as illustrative. Nevertheless it expresses our view for the delivery of the topic in some virtual setting.
Using the model various optimization tasks can be considered and solved, e.g., those as follow: 1) to minimize the delivery time for explaining principles of sorting algorithms; 2) to maximize the capabilities for 'learning by doing' in learning sorting algorithms, etc. For instance, a solution of task 1 is: L 0 + L 1 + L T = 0 + 15 + 0 = 15. A solution of task 2 is: L 0 + L 5 + L 14 + L 13 + L T = 0 + 0 + 1 + 1 + 0 = 2 (see Fig. 5). In general case, one can apply an algorithm (e.g., Dijkstra algorithm (Cormen et al., 2001)) for the optimal solution of the task.
How to construct and use the aggregating/sequencing model? Summarizing the whole discussion, we state that the following items are at the core of the approach: the initial set of LO units, criteria of weights to estimate the pedagogic/learning value of LOs and Fig. 6. The node-weighted graph as an aggregating/sequencing model that corresponds to attributes given in Table 1. identification of an order among units. The order within the aggregated sequence is to be identified by course designer (teacher) keeping in mind the requirements of e-learning theories, recommendations of e-learning standards and, of course, the internal structure and semantics of the content. It is the responsibility of teacher or learner what aggregate to choose, when the model is used through the adequate means of managing and technological support.

Evaluation and Discussion
The aggregating/sequencing model we have introduced is presented as the nodeweighted/arc-weighted connected graph in which nodes represent derivative LO units derived from the given GLO and arcs (directed branches) represent a logical sequence among the units for their interpreting within the learning/teaching process. The separate route (from the initial LO to the terminal LO in the model) represents one aggregate of the teaching content. All the routes specify the whole space (i.e., a package) of possible aggregates that, again, can be used to combine some aggregates into a higher-level package. The model enables to view learning/teaching as a formal process through identifying of multi-valued routes (loops) from the initial node to the terminal node according to the pre-specified rules (i.e., criteria and constraints that follow from pedagogical theories, e.g., first learn simplest items and then go to more complex ones, etc.).
Since the aggregating/sequencing model is based on properties of the GLO and on a variety of attributes (e.g., weights, roles, and ordering relations) that the model per se describes, the space for identifying the relevant sequences is very wide and optimization techniques can be applied. To do so the attribute values are to be identified first. We have suggested a multi-valued evaluation of LO units. The evaluation is based on using some principles of learning theories (e.g., Wiley, 2000a). Some evaluation attributes are introduced along with the generative technology (i.e., meta-programming because it, e.g., enables to pre-program some capabilities to support the paradigm 'learning by doing'). A set of routes, i.e. solutions of the aggregating/sequencing problem can be obtained automatically using known algorithms (such as Dijkstra algorithm) that model the content delivery process.
Even if the weights are identified imprecisely or a teacher/learner has no intention to use the model and to optimize the process in a real setting, the awareness of boundaries of the process according to some evaluating weights is important from the theory viewpoint (e.g., at the course planning phase).
Advantages of the approach are as follows. The model (when it is used in the context of GLOs) supports reusability aspects at a higher extent because the model extends the scope of reuse and opens the possibility to automate and optimize the process. It also enables to describe explicitly the integration of technology advances with pedagogical and social issues. As a result the proposed aggregating/sequencing model is a solid basis for e-learning theory because the model explicitly (using measurable attributes) describes the fundamental aspects of teaching process and represent the aspects formally. The model can be used not only in the context of GLOs. The model is also beneficial in the case when the related LO units are constructed manually or retrieved from repositories (if the number of related LO units is sufficient).
Restrictions of the approach are as follows. The model is more relevant to such cases when the related LO units are small and their number is high enough. On the other hand, a high extent of variants leads to the increase of complexity; the latter restricts to extend the approach for its use in settings with higher-level components (LOs) (such as a set of lessons, module or the whole course). The approach requires a numerical evaluation of LO units by calculating weights, which, in turn, is a complex socio-technical task because it depends upon the social context. The latter may restrict the use of the approach in practice.

Conclusions and Future Work
The introduced formal aggregating/sequencing model is a result that was obtained from the analysis of learning theories and standards, as well as properties and capabilities of generative learning objects. The model describes and models the content delivery process at a higher abstraction level precisely. The model also extends the reuse aspects of learning objects because it creates wider capabilities for aggregating/sequencing and quality improvement (e.g., through a higher degree of choice of variants, modification and automation) and opens the way for optimization of managing of learning/teaching process, if the criteria of the process are well-specified. From the technology and pedagogy viewpoints, in our view, the aggregating/sequencing model creates a solid basis for contribution to the e-learning theory. Since the approach has not only many advantages but as well some difficulties and restrictions, further research is needed in order to increase the maturity level of the approach and generative learning objects per se. The anticipated work includes the weight calculations strategies, optimal sequencing, and formation of aggregates at the higher granularity level.
V. Štuikys holds PhD degree since 1970 and degree of doctor habilitatis since 2003. Currently he occupies a position of a professor at Kaunas University of Technology, Software Engineering Department. His research interests include domain specific and software reuse, high level domain-specific languages, component-based programming, meta-programming and program generation, interdisciplinary aspects of automation in various domains, including e-learning systems, embedded systems, etc.
I. Brauklytė holds master degree in computer sciences from Klaipėda University since 2002. Currently she is PhD student at Kaunas University of Technology and also a lecturer at Klaipėda University, Faculty of Marine Engineering, Informatics Engineering Department. Her research interests include e-learning, learning objects, generative learning objects, meta-programming, and software reuse. She is an author of several labs and e-learning materials in virtual environment. She contributed in the world, international and republican scientific conferences of young scientists and participated in the methodological-training camps.


Hierarchical Discourse Parsing Based on Similarity Metrics

Attentional State Theory and Rhetorical Structure Theory are two predominant theories of discourse parsing. Combining these two approaches, in this paper, we describe a novel approach for discourse parsing. The resulting discourse tree structure retains following properties: structure of purpose from Attentional State Theory and relations between sentences from Rhetorical Structure Theory. We demonstrate the utility of our model by constructing a summarization system.

Introduction
Discourse parsing is crucial for parsing texts in Natural Language where each sentence has a purpose modelled by relationship with other sentences in the discourse. The main objective of discourse parsing is to generate a valid discourse structure which captures this purpose. Discourse parsing finds its applications in a variety of fields some of which include summarization (focused summaries), dialog systems (language generation) and information retrieval (Question Answering (QA) systems).
A few theories have been proposed for structuring a discourse, two of which are Attentional State Theory (AST) [7] and Rhetorical Structure Theory (RST) [12]. Attentional State Theory (AST) stresses the role of purpose in processing the discourse. It contains three components, namely, a linguistic structure, an intentional structure and an attentional state. The linguistic structure models the structure of a sequence of sentences in a discourse. A sequence of sentences in a discourse are aggregated into discourse segments. Each sentence serves a purpose in a discourse segment and in turn each discourse segment serves a purpose (Discourse Segment Purpose, DSP) with respect to the overall discourse. This structure of purpose of a discourse segment (and in turn the sentence) is modelled by intentional structure. To capture the structure of purpose, discourse segments are related using two relations namely, dominance and satisfaction-precedence.
If the purpose of a discourse segment (DSP1) contributes to the purpose of another discourse segment (DSP2), then, DSP2 dominates DSP1. If the purpose of a discourse segment (DSP1) has to be satisfied before the purpose of another discourse segment (DSP2), then, DSP2 satisfaction-precedes DSP1. At any given point of time, the discourse segment purpose under focus is kept track of by attentional state.
Rhetorical Structure Theory (RST) represents the structure of a discourse as a hierarchical tree diagram based on the relationship between sentences/text spans (nodes). The relation between these nodes can be of two types: symmetric and asymmetric. A symmetric relation relates two or more nodes labelled nuclei, each of which are equally important in realizing the writer's communicative goals. An asymmetric relation relates two nodes, a nucleus and a satellite, the nucleus being more important of the two and the satellite modifying the nucleus based on the particular relation. Due to the hierarchical structure of RST, summarization is fairly simple and efficient with respect to quality of output: the summary generated by omitting satellites of the tree after a certain depth would outline the main points of the text.
Few earlier systems aimed at discourse parsing are: A rule based system RASTA (Rhetorical Structure Theory Analyser) [3] is a component of Microsoft English Grammar that constructs RST analysis of texts. For each relation type, they define a set of rules between nodes, satisfying which, the nodes are related by that relation type. Another rule based system [15], develops a Unified Linguistic Discourse Model (U-LDM) for parsing a discourse. They perform discourse segmentation using discourse semantics and build a discourse tree based on syntactic, semantic and lexical rules. One of the machine learning approaches for discourse parsing [16] learns on discourse annotated corpora. They generate a rhetorical structure tree of a sentence based on the learned models of RST-DT 2002 corpus. Work done in [6] extend LTAG approach to discourse parsing, the D-LTAG. An incremental discourse parsing model has been proposed in [4] which aims at building a rhetorical structure of discourse using veins theory [5]. In [9], an automatic generation of discourse tree has been proposed. The sentences are nodes of the discourse tree and the edges between the sentences define a relation. The relationship type is defined using clue expressions. As per our knowledge, there are no freely available annotated discourse tree banks which makes machine learning approaches in-feasible. Rule based systems require tedious analysis of discourse and the rules might not be generic which restricts the domain of usage of the system. Therefore it is necessary to develop an approach which is generic and is un-supervised.
In this paper we combine the ideas of Attentional State Theory and Rhetorical Structure Theory and propose a novel scheme for discourse parsing. We incorporate the features of RST into AST so that we can understand the role of a sentence better and in turn create a better interpretation of the discourse which increases the quality of applications built on it. The discourse tree we build retains following properties: structure of sequence of sentences (linguistic structure) and structure of purpose (intentional structure) from Attentional State Theory and relations between sentences/text spans from Rhetorical Structure Theory. We develop a discourse tree structure based on similarity measures between sentences, identify discourse segments from the discourse tree structure and define relationships between discourse segments and between sentences of discourse segments. We demonstrate the utility of our model by constructing a summarization system. The paper is structured as follows: First we describe our system of discourse parsing in detail in section 2. In section 3 we develop a simple method of summarization based on our system with results. In section 4, we talk about future work and conclude.

Our Model
We assume a discourse to be a collection of sub-topics which contribute to the main topic of the discourse. The utterances/sentences which speak about a subtopic are aggregated as a discourse segment (DS). These discourse segments together form the discourse. A Discourse segment serves a purpose called discourse segment purpose (type of contribution to the topic of the discourse). We structure the discourse based on the above assumption by relating sentences which speak about the same topic to form discourse segments. Presently, We define the relationship between utterances/sentences within a discourse segment and the relationship between discourse segments as dominance. The relationship specifies the type of contribution to main topic which we refine as a part of future work.
In order to relate sentences which speak about the same topic we use surface information of a sentence and the evidences of cohesion. Two types of cohesion namely coreference and lexical cohesion prove to be vital evidence to find sentences which speak about a same topic. Coreference expressions refer to a previously introduced entity (center). So the sentence with a reference expression referring to a center in another sentence are said to discuss about the same topic (center). Lexical Cohesion is repetition of the same lexeme or a lexeme which is semantically similar (Hyponyms). Sentences which have similar surface information are also said to discuss about the same topic.
In this section we describe our model of parsing a discourse. We process the given discourse in three phases to progressively build a discourse tree structure similar to rhetorical tree structure [12] ,with one rela-tion type Dominance [7], and maintaining the intentional, lexical structure of AST. In the first phase, we use a co-reference module to extract reference expressions (expression which refers to an Object, a Noun Phrase (NP) or a Prepositional Phrase (PP)) and their centers (the Object to which the reference expression refers to). We relate a sentence containing a reference expression to the sentence with the corresponding center as they speak about the same "Object" (topic). In the second phase we relate the remaining sentences using surface information and evidences of lexical cohesion. In the third phase we form discourse segments and find relations among them to generate a tree similar to RST. We now proceed with the description of the system.

First Phase
In the first phase, we use the output of the co-reference module (LingPipe) [1] to create a collection of trees from sentences. Given a discourse text, a co-reference module extracts reference expressions and marks their corresponding centers. For example, in Figure 1 the reference expression he refers to Terry, the center.

a. really goofs sometimes Terry
was excited about trying c.
wanted Tony to join on a sailing expedition He d.  From this output of co-reference module we construct trees as follow: at the beginning, we consider each sentence to be a single node tree. Next, we find a parent to each of the sentences using the reference expressions as the basis. For this, consider a discourse of n sentences say S 1 to S n . We make a sentence S i (i = 1) the child of S i−1 if any of the following hold • There exists at least one reference expression in S i with a center in S i−1 • There exists at least one reference expression in S i and one reference expression in S i−1 with a common center in some sentence At the end of this phase we have a collection of trees, each node with at most one child. Note that there is a possibility that a sentence, say S i may not have a reference expression or may not have a center referred to by any reference expression. In this case, the sentence would remain a single-node tree. It is apparent from our construction that every tree now contains a chain of continuous sentences, each tree can be considered a partially built discourse segment. In the next phase, we merge these trees together into a single tree on the basis of lexical cohesion and surface information.

Second Phase
Suppose after the first phase we have a collection of z trees, T 1 to T z . We maintain a final tree T , initialised to T 1 , into which we merge all the remaining trees. This merging is done using lexical cohesion and surface information (similarity of content) between nodes (sentences) of candidate trees.
For merging T i , i = 1 with T , consider the root sentence of T i , say S j . Extract all the Noun Phrases (NPs) and Prepositional Phrases (PPs) of S j using a parser. We use the standard Stanford parser [8] for parsing. These NPs and PPs constitute Surface Information. We exploit the property of lexical cohesion in a discourse by assuming that the NPs of Subject semantic role and Direct Object semantic role have evidences of lexical cohesion. Therefore, out of all NPs and PPs of S j , we consider the NPs with Subject semantic role (NPSubject) and Direct Object semantic role (NPObject) of the main verb. If the main verb is intransitive, we consider only the NP with Subject semantic role (NPSubject). For merging T i into T , we find the most probable parent of T i by comparing with the NPSubject and NPObject (if any) of S j and the Surface Information of S j−1 , which exists in T , and all the ancestors of S j−1 . Our algorithm for merging T i with T is as follows: • Consider a set U = U 1 , U 2 ,... U k , U 1 the surface information of S j−1 , U 2 to U k the surface information of ancestors of S j−1 , U k the surface information root of T .
• Calculate the similarity between U 1 with NPSubject and NPObject (if any) of S j , the process of similarity calculation being discussed later in the paper.
• For U 1 pick that entity which has maximum similarity (either with NPSubject or with NPObject) and define that entity as the topic between S j and U 1 .
• Repeat for all U i s and find the maximum of maximum similarities.
• If the maximum is unique and belongs to a node say S of T then we make S j the child of S and thus merge T i into T .
• If there is more than one occurrence of the maximum, then a decision based on lexical cohesion is not possible.
-Inorder to find a most probable parent among these maxima, we prioritise the topics based on the importance of that topic. For this purpose, we use TextRank [13], which gives a rank to each topic based on the knowledge from the text. It is a graph based ranking algorithm using Google's Page Rank [2] on text. Out of the maxima, whichever topic has the highest priority, we choose the corresponding sentence as the parent of S j . -If there exists a clash of priorities in this level also, then we resort to sentence similarities.
After calculating the similarity between U i with NPSubject and NPObject, to avoid irrelevant entities, we pick only those entities/topics which have similarity value above a specific threshold (for better results > 0.9). If there is no topic which has value greater than the threshold, then we consider sentence similarities. While considering sentence similarities, out of all the ancestors of S j−1 (including itself), the sentence (node) most similar to S j is made the parent of S j . For example in Figure 2, T 1 and T 2 are the first level trees formed from five sentences S 1 to S 5 . We initialise T 1 to T and for merging T 2 into T , we calculate the similarity value between S 4 with S 3 and all its ancestors. The final similarity measures are shown in the figure, S 4 is made the child of S 2 as it has the maximum similarity measure. The similarity of our construction to that of Attentional State Theory can now be seen easily. In Attentional State theory, each sentence starts a discourse segment or continues a discourse segment or ends a discourse segment. In our case, each time a sentence S j attaches itself as the child of S k , it figuratively means that it either continues the topic of S k or ends the topic of S k . This also means that S j ends all the topics of siblings of S k . Therefore, from now on for a sentence S j+1 , there is no need to consider all the nodes of T . It would suffice to consider S j and its ancestors since it cannot continue an already ended topic. It is apparent that we are refining the partial discourse segments constructed in first phase during the second phase. In the next section, we describe the procedure to find similarity between two sentences.

Similarity between sentences
Given two sentences S 1 and S 2 , we calculate the similarity measure between these two as follows: Extract the NPs and PPs of S 1 and S 2 , identify the common nouns (NN) and proper nouns (NNP) from each NP and PP. Out of these filter out only those NNs and NNPs whose degree of importance (from TextRank) is above a threshold. For calculating the similarity between these two sentences, we use Dynamic Time Warping Algorithm (DTW) [11] on the filtered set of NNs and NNPs. Dynamic Time Warping Algorithm calculates the sentence similarities using dynamic programming, with a matrix whose rows correspond to the words of first sentence and columns correspond to the words of the second sentence, the similarity score between a word of one sentence and a word of another sentence being the elements of the matrix. In our case the rows correspond to the filtered NNs/NNPs of S 1 , columns correspond to the filtered NNs/NNPs of S 2 . For each grid element the following recurrence formula is defined 1. A long time ago, When the Earth was a beautiful young girl floating in space, two powerful kings, the Sun and the Moon, decided that they would rule her.
3. He lived in a splendid golden palace, surrounded by thousands of sunbeams that danced around him.
king, who was waited upon by thousands of twinkling stars.
4. The Moon, who lived in a silver palace was a much gentler glowing light on Earth.
5. He would sail gently through the sky, casting a soft 2. The Sun was strong, bold and hot tempered.
Where m = no. of rows, n = no. of columns, d(a, b) the similarity measure between words a and b. After the execution of DTW, the normalized value at the last element of the last row gives the similarity measure between S 1 and S 2 . The minimum this value, the maximum the similarity between the sentences. We now describe similarity calculation between a pair of words.

Similarity between words
Several similarity metrics have been proposed so far to calculate the similarity between a pair of words. In [10], the similarity is calculated using the formula Where length is the length of the shortest path between two concepts using node-counting, and D is the maximum depth of the taxonomy. According to [17], the similarity metric measures the depth of two given concepts in the WordNet taxonomy, and the depth of the least common subsumer (LCS), and combines these figures into a similarity score In our paper, we define the similarity score of a pair of words as the average of Synonym similarity and Hypernym similarity. We calculate Sim w (w 1 , w2) = e αd − 1 e αd + e βl − 2 for Hypernym similarity [11]. α and β 1 are smoothing factors, l is the shortest path length between w 1 and w 2 ; d is the depth of subsumer in the hierarchy semantic nets extracted from WordNet [14]. For Synonym similarity the normalized value of the number of N-gram (N = 3) matchings between the synonyms of two words is taken.

Third Phase
At this stage we have the discourse tree structure where each sentence (node) has a parent (except the root) and each node can have any number of children.
We can interpret this tree as follows: The root node starts a new topic. If the root node has more than one children then each of the subtrees of the children in turn contribute to the root node ,but independently. Hence the subtrees rooted at these children can be viewed as separate discourse segments. If the root node has only one child then the root node and the child combined together start a topic. This can be performed at all levels of the tree and a hierarchical discourse segment structure can be built. Each node/sentence that starts a discourse segment has a dominance relation to the sentences of that segment.
To make our tree structure similar to that of rhetorical tree structure we identify the nucleus and satellite nodes from the hierarchical discourse segments. Each discourse segment is characterized by a nucleus which is recursively calculated from the sentence(s) starting that segment and the nuclei of the sub-discourse segments of that segment. The nucleus of a segment is the sentence with maximum sum of TextRank values of Noun Phrases (normalized) among the candidate sentences. The remaining sentences are satellites of this sentence.
We demonstrate the algorithm with an example. Figure 3 shows a sample text for which the final tree using the algorithm of second phase described above is shown in Figure 4. Now after the third phase, from the tree in Figure 4, we identify the discourse segments and build RST as shown in Figure 6 A long time ago, when the Earth was a beautiful young girl floating in space, two powerful kings, the Sun and the Moon, decided that they would rule her. The Sun was strong, bold and hot tempered. He lived in a splendid golden palace, surrounded by thousands of sunbeams that danced around him all day. The Moon, who lived in a silver palace was a much gentler king, who was waited upon by thousands of twinkling stars. Since the Sun was by far the greater of the two kings, he established his rule over Earth first. He ruled her throughout the day, shining down upon her with great vigour. His bright rays of sunlight reached into every nook and cranny, and fulled the Earth with warmth. Flowers and plants lifted their faces eagerly towards them. People and animals basked in the sunshine, and they grew and flourished. The Sun would go back to his palace every night, and as he timbled into his bed, the Moon would appear, with all his stars, to begin his rule. He would sail gently through the sky, casting a soft, glowing light on Earth. His courtiers would twinkle around him in the dark night sky, and they would look very beautiful indeed. But very soon the Moon became unhappy. He found that no one on Earth was paying attention to him and to his sparkling courtiers. As soon as he appeared in the sky, everyone on Earth prepared to go to bed. The flowers and plants would bend their heads, and gather their leaves close to their stalks. Birds would fly back to their nests and tuck their heads under their wings. People and animals would hurry back to their homes and shut their eyes. Everything would be very quiet and still and the Moon did not like this at all.
A long time ago, when the Earth was a beautiful young, girl floating in space, two powerful kings, the Sun and the Moon, decided that they would rule her. Since the Sun was by far the greater of the two kings, he established his rule over Earth first. He ruled her throughout the day, shining down upon her with great vigour. His bright rays of sunlight reached into every nook and cranny, and fulled the Earth with warmth.The Sun would go back to his palace every night, and as he timbled into his bed, the Moon would appear, with all his stars, to begin his rule.His courtiers would twinkle around him in the dark night sky, and they would look very beautiful indeed.But very soon the Moon became unhappy. As soon as he appeared in the sky, everyone on Earth prepared to go to bed.Birds would fly back to their nests and tuck their heads under their wings. a. Input text b. Output summary

Summarization and Results
We apply our model of discourse parsing for text summarization. From a given text, we the nuclei of discourse segments upto a certain threshold level which depends on the compression factor. Figure 5 shows a sample English text and the result of summarization. We plan to test our summarization on a standard corpus. We can improve this model using better summarization techniques on the discourse tree.

Future Work
Our first task would be to perform a thorough evalution of the current model. Presently our model supports single relation type, dominance. We aim at accommodating more relation types into our model. Relation types can be extracted by formulating linguistic rules on cue-phrases such as therefore, whereas, On the other hand and so on which would increase the quality of discourse tree further. We can also extend our work to Indian languages such as Hindi which would be a challenging task due to inadequate linguistic resources.
This paper is an outline of system to be developed. The work is still in progress and even though improvements need to be done, we can see that the summary resulting from our rough model is considerably meaningful which in turn signifies the efficacy of our idea.


Conundrums in Noun Phrase Coreference Resolution: Making Sense of the State-of-the-Art

We aim to shed light on the state-of-the-art in NP coreference resolution by teasing apart the differences in the MUC and ACE task definitions, the assumptions made in evaluation methodologies, and inherent differences in text corpora. First, we examine three subproblems that play a role in coreference resolution: named entity recognition, anaphoricity determination, and coreference element detection. We measure the impact of each subproblem on coreference resolution and confirm that certain assumptions regarding these subproblems in the evaluation methodology can dramatically simplify the overall task. Second, we measure the performance of a state-of-the-art coreference resolver on several classes of anaphora and use these results to develop a quantitative measure for estimating coreference resolution performance on new data sets.

Introduction
As is common for many natural language processing problems, the state-of-the-art in noun phrase (NP) coreference resolution is typically quantified based on system performance on manually annotated text corpora. In spite of the availability of several benchmark data sets (e.g. MUC-6 (1995), ACE NIST (2004)) and their use in many formal evaluations, as a field we can make surprisingly few conclusive statements about the state-of-theart in NP coreference resolution.
In particular, it remains difficult to assess the effectiveness of different coreference resolution approaches, even in relative terms. For example, the 91.5 F-measure reported by McCallum and Wellner (2004) was produced by a system using perfect information for several linguistic subproblems. In contrast, the 71.3 F-measure reported by Yang et al. (2003) represents a fully automatic end-to-end resolver. It is impossible to assess which approach truly performs best because of the dramatically different assumptions of each evaluation.
Results vary widely across data sets. Coreference resolution scores range from 85-90% on the ACE 2004 and 2005 data sets to a much lower 60-70% on the MUC 6 and 7 data sets (e.g. Soon et al. (2001) and Yang et al. (2003)). What accounts for these differences? Are they due to properties of the documents or domains? Or do differences in the coreference task definitions account for the differences in performance? Given a new text collection and domain, what level of performance should we expect?
We have little understanding of which aspects of the coreference resolution problem are handled well or poorly by state-of-the-art systems. Except for some fairly general statements, for example that proper names are easier to resolve than pronouns, which are easier than common nouns, there has been little analysis of which aspects of the problem have achieved success and which remain elusive.
The goal of this paper is to take initial steps toward making sense of the disparate performance results reported for NP coreference resolution. For our investigations, we employ a state-of-the-art classification-based NP coreference resolver and focus on the widely used MUC and ACE coreference resolution data sets.
We hypothesize that performance variation within and across coreference resolvers is, at least in part, a function of (1) the (sometimes unstated) assumptions in evaluation methodologies, and (2) the relative difficulty of the benchmark text corpora. With these in mind, Section 3 first examines three subproblems that play an important role in coreference resolution: named entity recognition, anaphoricity determination, and coreference element detection. We quantitatively measure the impact of each of these subproblems on coreference resolution performance as a whole. Our results suggest that the availability of accurate detectors for anaphoricity or coreference elements could substantially improve the performance of state-ofthe-art resolvers, while improvements to named entity recognition likely offer little gains. Our results also confirm that the assumptions adopted in  some evaluations dramatically simplify the resolution task, rendering it an unrealistic surrogate for the original problem.
In Section 4, we quantify the difficulty of a text corpus with respect to coreference resolution by analyzing performance on different resolution classes. Our goals are twofold: to measure the level of performance of state-of-the-art coreference resolvers on different types of anaphora, and to develop a quantitative measure for estimating coreference resolution performance on new data sets. We introduce a coreference performance prediction (CPP) measure and show that it accurately predicts the performance of our coreference resolver. As a side effect of our research, we provide a new set of much-needed benchmark results for coreference resolution under common sets of fully-specified evaluation assumptions.

Coreference Task Definitions
This paper studies the six most commonly used coreference resolution data sets. Two of those are from the MUC conferences (MUC-6, 1995;MUC-7, 1997) and four are from the Automatic Content Evaluation (ACE) Program (NIST, 2004). In this section, we outline the differences between the MUC and ACE coreference resolution tasks, and define terminology for the rest of the paper.
Noun phrase coreference resolution is the process of determining whether two noun phrases (NPs) refer to the same real-world entity or concept. It is related to anaphora resolution: a NP is said to be anaphoric if it depends on another NP for interpretation. Consider the following: John Hall is the new CEO. He starts on Monday.
Here, he is anaphoric because it depends on its antecedent, John Hall, for interpretation. The two NPs also corefer because each refers to the same person, JOHN HALL.
As discussed in depth elsewhere (e.g. van Deemter and Kibble (2000)), the notions of coref-erence and anaphora are difficult to define precisely and to operationalize consistently. Furthermore, the connections between them are extremely complex and go beyond the scope of this paper. Given these complexities, it is not surprising that the annotation instructions for the MUC and ACE data sets reflect different interpretations and simplifications of the general coreference relation. We outline some of these differences below.
Syntactic Types. To avoid ambiguity, we will use the term coreference element (CE) to refer to the set of linguistic expressions that participate in the coreference relation, as defined for each of the MUC and ACE tasks. 1 At times, it will be important to distinguish between the CEs that are included in the gold standard -the annotated CEs -from those that are generated by the coreference resolution system -the extracted CEs.
At a high level, both the MUC and ACE evaluations define CEs as nouns, pronouns, and noun phrases. However, the MUC definition excludes (1) "nested" named entities (NEs) (e.g. "America" in "Bank of America"), (2) relative pronouns, and (3) gerunds, but allows (4) nested nouns (e.g. "union" in "union members"). The ACE definition, on the other hand, includes relative pronouns and gerunds, excludes all nested nouns that are not themselves NPs, and allows premodifier NE mentions of geo-political entities and locations, such as "Russian" in "Russian politicians".
Semantic Types. ACE restricts CEs to entities that belong to one of seven semantic classes: person, organization, geo-political entity, location, facility, vehicle, and weapon. MUC has no semantic restrictions.
Singletons. The MUC data sets include annotations only for CEs that are coreferent with at least one other CE. ACE, on the other hand, permits "singleton" CEs, which are not coreferent with any other CE in the document. These substantial differences in the task definitions (summarized in Table 1) make it extremely difficult to compare performance across the MUC and ACE data sets. In the next section, we take a closer look at the coreference resolution task, analyzing the impact of various subtasks irrespective of the data set differences.

Coreference Subtask Analysis
Coreference resolution is a complex task that requires solving numerous non-trivial subtasks such as syntactic analysis, semantic class tagging, pleonastic pronoun identification and antecedent identification to name a few. This section examines the role of three such subtasks -named entity recognition, anaphoricity determination, and coreference element detection -in the performance of an end-to-end coreference resolution system. First, however, we describe the coreference resolver that we use for our study.

The RECONCILE ACL09 Coreference Resolver
We use the RECONCILE coreference resolution platform (Stoyanov et al., 2009) to configure a coreference resolver that performs comparably to state-of-the-art systems (when evaluated on the MUC and ACE data sets under comparable assumptions). This system is a classification-based coreference resolver, modeled after the systems of Ng and Cardie (2002b) and Bengtson and Roth (2008). First it classifies pairs of CEs as coreferent or not coreferent, pairing each identified CE with all preceding CEs. The CEs are then clustered into coreference chains 2 based on the pairwise decisions. RECONCILE has a pipeline architecture with four main steps: preprocessing, feature extraction, classification, and clustering. We will refer to the specific configuration of RECONCILE used for this paper as RECONCILE ACL09 .
Preprocessing. The RECONCILE ACL09 preprocessor applies a series of language analysis tools (mostly publicly available software packages) to the source texts. The OpenNLP toolkit (Baldridge, J., 2005) performs tokenization, sentence splitting, and part-of-speech tagging. The Berkeley parser (Petrov and Klein, 2007) generates phrase structure parse trees, and the de Marneffe et al. (2006) system produces dependency relations. We employ the Stanford CRF-based Named Entity Recognizer (Finkel et al., 2004)   fairly comprehensive set of 61 features introduced in previous coreference resolution systems (see Bengtson and Roth (2008)). We briefly summarize the features here and refer the reader to Stoyanov et al. (2009) for more details.
Lexical (9): String-based comparisons of the two CEs, such as exact string matching and head noun matching.
Proximity (5): Sentence and paragraph-based measures of the distance between two CEs. Grammatical (28): A wide variety of syntactic properties of the CEs, either individually or as a pair. These features are based on part-of-speech tags, parse trees, or dependency relations. For example: one feature indicates whether both CEs are syntactic subjects; another indicates whether the CEs are in an appositive construction.
Semantic (19): Capture semantic information about one or both NPs such as tests for gender and animacy, semantic compatibility based on Word-Net, and semantic comparisons of NE types.
Classification and Clustering. We configure RECONCILE ACL09 to use the Averaged Perceptron learning algorithm (Freund and Schapire, 1999) and to employ single-link clustering (i.e. transitive closure) to generate the final partitioning. 3

Baseline System Results
Our experiments rely on the MUC and ACE corpora. For ACE, we use only the newswire portion because it is closest in composition to the MUC corpora. Statistics for each of the data sets are shown in Table 2. When available, we use the standard test/train split. Otherwise, we randomly split the data into a training and test set following a 70/30 ratio.
Scoring Algorithms. We evaluate using two common scoring algorithms 4 -MUC and B 3 . The MUC scoring algorithm (Vilain et al., 1995) computes the F1 score (harmonic mean) of precision and recall based on the identifcation of unique coreference links. We use the official MUC scorer implementation for the two MUC corpora and an equivalent implementation for ACE. The B 3 algorithm (Bagga and Baldwin, 1998) computes a precision and recall score for each CE: where R ce is the coreference chain to which ce is assigned in the response (i.e. the system-generated output) and K ce is the coreference chain that contains ce in the key (i.e. the gold standard). Precision and recall for a set of documents are computed as the mean over all CEs in the documents and the F1 score of precision and recall is reported.
B 3 Complications. Unlike the M U C score, which counts links between CEs, B 3 presumes that the gold standard and the system response are clusterings over the same set of CEs. This, of course, is not the case when the system automatically identifies the CEs, so the scoring algorithm requires a mapping between extracted and annotated CEs. We will use the term twin(ce) to refer to the unique annotated/extracted CE to which the extracted/annotated CE is matched. We say that a CE is twinless (has no twin) if no corresponding CE is identified. A twinless extracted CE signals that the resolver extracted a spurious CE, while an annotated CE is twinless when the resolver fails to extract it.
Unfortunately, it is unclear how the B 3 score should be computed for twinless CEs. Bengtson and Roth (2008) simply discard twinless CEs, but this solution is likely too lenient -it doles no punishment for mistakes on twinless annotated or extracted CEs and it would be tricked, for example, by a system that extracts only the CEs about which it is most confident.
We propose two different ways to deal with twinless CEs for B 3 . One option, B 3 all, retains all twinless extracted CEs. It computes the preci-sion as above when ce has a twin, and computes the precision as 1/|R ce | if ce is twinless. (Similarly, recall(ce) = 1/|K ce | if ce is twinless.) The second option, B 3 0, discards twinless extracted CEs, but penalizes recall by setting recall(ce) = 0 for all twinless annotated CEs. Thus, B 3 0 presumes that all twinless extracted CEs are spurious. Table 3, box 1 shows the performance of RECONCILE ACL09 using a default (0.5) coreference classifier threshold. The MUC score is highest for the MUC6 data set, while the four ACE data sets show much higher B 3 scores as compared to the two MUC data sets. The latter occurs because the ACE data sets include singletons.

Results.
The classification threshold, however, can be gainfully employed to control the trade-off between precision and recall. This has not traditionally been done in learning-based coreference resolution research -possibly because there is not much training data available to sacrifice as a validation set. Nonetheless, we hypothesized that estimating a threshold from just the training data might be effective. Our results (BASELINE box in Table 3) indicate that this indeed works well. 5 With the exception of MUC6, results on all data sets and for all scoring algorithms improve; moreover, the scores approach those for runs using an optimal threshold (box 3) for the experiment as determined by using the test set. In all remaining experiments, we learn the threshold from the training set as in the BASELINE system.
Below, we resume our investigation of the role of three coreference resolution subtasks and measure the impact of each on overall performance.

Named Entities
Previous work has shown that resolving coreference between proper names is relatively easy (e.g. Kameyama (1997)) because string matching functions specialized to the type of proper name (e.g. person vs. location) are quite accurate. Thus, we would expect a coreference resolution system to depend critically on its Named Entity (NE) extractor. On the other hand, state-of-the-art NE taggers are already quite good, so improving this component may not provide much additional gain.
To study the influence of NE recognition, we replace the system-generated NEs of  shows that using gold standard NEs leads to improvements on all data sets with the exception of ACE2 and ACE05, on which performance is virtually unchanged. The improvements tend to be small, however, between 0.5 to 3 performance points. We attribute this to two factors. First, as noted above, although far from perfect, NE taggers generally perform reasonably well. Second, only 20 to 25% of the coreference element resolutions required for these data sets involve a proper name (see Section 4).
Conclusion #1: Improving the performance of NE taggers is not likely to have a large impact on the performance of state-of-the-art coreference resolution systems.

Coreference Element Detection
We expect CE detection to be an important subproblem for an end-to-end coreference system. Results for a system that assumes perfect CEs are shown in box 5 of Table 3. For these runs, RECONCILE ACL09 uses only the annotated CEs for both training and testing. Using perfect CEs solves a large part of the coreference resolution task: the annotated CEs divulge anaphoricity information, perfect NP boundaries, and perfect information regarding the coreference relation de-fined for the data set. We see that focusing attention on all and only the annotated CEs leads to (often substantial) improvements in performance on all metrics over all data sets, especially when measured using the MUC score.
Conclusion #2: Improving the ability of coreference resolvers to identify coreference elements would likely improve the state-of-the-art immensely -by 10-20 points in MUC F1 score and from 2-12 F1 points for B 3 . This finding explains previously published results that exhibit striking variability when run with annotated CEs vs. system-extracted CEs. On the MUC6 data set, for example, the best published MUC score using extracted CEs is approximately 71 (Yang et al., 2003), while multiple systems have produced MUC scores of approximately 85 when using annotated CEs (e.g. Luo et al. (2004), McCallum and Wellner (2004)).
We argue that providing a resolver with the annotated CEs is a rather unrealistic evaluation: determining whether an NP is part of an annotated coreference chain is precisely the job of a coreference resolver! Conclusion #3: Assuming the availability of CEs unrealistically simplifies the coreference resolution task.

Anaphoricity Determination
Finally, several coreference systems have successfully incorporated anaphoricity determination modules (e.g. Ng and Cardie (2002a) and Bean and Riloff (2004)). The goal of the module is to determine whether or not an NP is anaphoric. For example, pleonastic pronouns (e.g. it is raining) are special cases that do not require coreference resolution.
Unfortunately, neither the MUC nor the ACE data sets include anaphoricity information for all NPs. Rather, they encode anaphoricity information implicitly for annotated CEs: a CE is considered anaphoric if is not a singleton. 6 To study the utility of anaphoricity information, we train and test only on the "anaphoric" extracted CEs, i.e. the extracted CEs that have an annotated twin that is not a singleton. Note that for the MUC datasets all extracted CEs that have twins are considered anaphoric.
Results for this experiment (box 6 in Table 3) are similar to the previous experiment using perfect CEs: we observe big improvements across the board. This should not be surprising since the experimental setting is quite close to that for perfect CEs: this experiment also presumes knowledge of when a CE is part of an annotated coreference chain. Nevertheless, we see that anaphoricity infomation is important. First, good anaphoricity identification should reduce the set of extracted CEs making it closer to the set of annotated CEs. Second, further improvements in MUC score for the ACE data sets over the runs using perfect CEs (box 5) reveal that accurately determining anaphoricity can lead to substantial improvements in MUC score. ACE data includes annotations for singleton CEs, so knowling whether an annotated CE is anaphoric divulges additional information.
Conclusion #4: An accurate anaphoricity determination component can lead to substantial improvement in coreference resolution performance.

Resolution Complexity
Different types of anaphora that have to be handled by coreference resolution systems exhibit different properties. In linguistic theory, binding mechanisms vary for different kinds of syntactic constituents and structures. And in practice, empirical results have confirmed intuitions that different types of anaphora benefit from different classifier features and exhibit varying degrees of difficulty (Kameyama, 1997). However, performance evaluations rarely include analysis of where stateof-the-art coreference resolvers perform best and worst, aside from general conclusions.
In this section, we analyze the behavior of our coreference resolver on different types of anaphoric expressions with two goals in mind. First, we want to deduce the strengths and weaknesses of state-of-the-art systems to help direct future research. Second, we aim to understand why current coreference resolvers behave so inconsistently across data sets. Our hypothesis is that the distribution of different types of anaphoric expressions in a corpus is a major factor for coreference resolution performance. Our experiments confirm this hypothesis and we use our empirical results to create a coreference performance prediction (CPP) measure that successfully estimates the expected level of performance on novel data sets.

Resolution Classes
We study the resolution complexity of a text corpus by defining resolution classes. Resolution classes partition the set of anaphoric CEs according to properties of the anaphor and (in some cases) the antecedent. Previous work has studied performance differences between pronominal anaphora, proper names, and common nouns, but we aim to dig deeper into subclasses of each of these groups. In particular, we distinguish between proper and common nouns that can be resolved via string matching, versus those that have no antecedent with a matching string. Intuitively, we expect that it is easier to resolve the cases that involve string matching. Similarly, we partition pronominal anaphora into several subcategories that we expect may behave differently. We define the following nine resolution classes: Proper Names: Three resolution classes cover CEs that are named entities (e.g. the PER-SON, LOCATION, ORGANIZATION and DATE classes for MUC and ACE) and have a prior referent 7 in the text. These three classes are distinguished by the type of antecedent that can be resolved against the proper name.
(1) PN-e: a proper name is assigned to this exact string match class if there is at least one preceding CE in its gold standard coreference chain that exactly matches it.
(2) PN-p: a proper name is assigned to this partial string match class if there is at least one preceding CE in its gold standard chain that has some content words in common.
(3) PN-n: a proper name is assigned to this no string match MUC6 class if no preceding CE in its gold standard chain has any content words in common with it.
Common NPs: Three analogous string match classes cover CEs that have a common noun as a head: (4) CN-e (5) CN-p (6) CN-n.
As noted above, resolution classes are defined for annotated CEs. We use the twin relationship to match extracted CEs to annotated CEs and to evaluate performance on each resolution class.

Scoring Resolution Classes
To score each resolution class separately, we define a new variant of the MUC scorer. We compute a MUC-RC score (for MUC Resolution Class) for class C as follows: we assume that all CEs that do not belong to class C are resolved correctly by taking the correct clustering for them from the gold standard. Starting with this correct partial clustering, we run our classifier on all ordered pairs of CEs for which the second CE is of class C, essentially asking our coreference resolver to determine whether each member of class C is coreferent with each of its preceding CEs. We then count the number of unique correct/incorrect links that the system introduced on top of the correct partial clustering and compute precision, recall, and F1 score. This scoring function directly measures the impact of each resolution class on the overall MUC score.   Table 4 shows the average distribution and scores across all data sets. These scores confirm our expectations about the relative difficulty of different types of resolutions. For example, it appears that proper names are easier to resolve than common nouns; gendered pronouns are easier than 1st and 2nd person pronouns, which, in turn, are easier than ungendered 3rd person pronouns. Similarly, our intuition is confirmed that many CEs can be accurately resolved based on exact string matching, whereas resolving against antecedents that do not have overlapping strings is much more difficult. The average scores in Table 4 show that performance varies dramatically across the resolution classes, but, on the surface, appears to be relatively consistent across data sets.

Results
None of the data sets performs exactly the same, of course, so we statistically analyze whether the behavior of each resolution class is similar across the data sets. For each data set, we compute the correlation between the vector of MUC-RC scores over the resolution classes and the average vector of MUC-RC scores for the remaining five data sets. Table 5 contains the results, which show high correlations (over .90) for all six data sets. These results indicate that the relative performance of the resolution classes is consistent across corpora.

Coreference Performance Prediction
Next, we hypothesize that the distribution of resolution classes in a corpus explains (at least partially) why performance varies so much from cor-  We compute the CPP score for each of our six data sets based on the average resolution class performance measured on the other five data sets. The predicted score for each class is computed as a weighted sum of the observed scores for each resolution class (i.e. the mean for the class measured on the other five data sets) weighted by the proportion of CEs that belong to the class. The predicted scores are shown in Table 6 and compared with the MUC scores that are produced by RECONCILE ACL09 . 8 Our results show that the CPP measure is a good predictor of coreference resolution performance on unseen data sets, with the exception of one outlier -the MUC6 data set. In fact, the correlation between predicted and observed scores is 0.731 for all data sets and 0.913 excluding MUC6. RECONCILE ACL09 's performance on MUC6 is better than predicted due to the higher than average scores for the common noun classes. We attribute this to the fact that MUC6 includes annotations for nested nouns, which almost always fall in the CN-e and CN-p classes. In addition, many of the features were first created for the MUC6 data set, so the feature extractors are likely more accurate than for other data sets.
Overall, results indicate that coreference performance is substantially influenced by the mix of resolution classes found in the data set. Our CPP measure can be used to produce a good estimate of the level of performance on a new corpus. 8 Observed scores for MUC6 and 7 differ slightly from Table 3 because this part of the work did not use the OPTIONAL field of the key, employed by the official MUC scorer.

Related Work
The bulk of the relevant related work is described in earlier sections, as appropriate. This paper studies complexity issues for NP coreference resolution using a "good", i.e. near state-of-the-art, system. For state-of-the-art performance on the MUC data sets see, e.g. Yang et al. (2003); for state-ofthe-art performance on the ACE data sets see, e.g. Bengtson and Roth (2008) and Luo (2007). While other researchers have evaluated NP coreference resolvers with respect to pronouns vs. proper nouns vs. common nouns (Ng and Cardie, 2002b), our analysis focuses on measuring the complexity of data sets, predicting the performance of coreference systems on new data sets, and quantifying the effect of coreference system subcomponents on overall performance. In the related area of anaphora resolution, researchers have studied the influence of subsystems on the overall performance (Mitkov, 2002) as well as defined and evaluated performance on different classes of pronouns (e.g. Mitkov (2002) and Byron (2001)). However, due to the significant differences in task definition, available datasets, and evaluation metrics, their conclusions are not directly applicable to the full coreference task.
Previous work has developed methods to predict system performance on NLP tasks given data set characteristics, e.g. Birch et al. (2008) does this for machine translation. Our work looks for the first time at predicting the performance of NP coreference resolvers.