On Learning Web Information Extraction Rules with TANGO
Abstract
The research on Enterprise Systems Integration focuses on proposals to support business processes by re-using existing systems. Wrappers help re-use web ap plications that provide a user interface only. They emulate a human user who interacts with them and extracts the information of interest in a structured for mat. In this article, we present TANGO, which is our proposal to learn rules to extract information from semi-structured web documents with high precision and recall, which is a must in the context of Enterprise Systems Integration. It relies on an open catalogue of features that helps map the input documents into a knowledge base in which every DOM node is represented by means of HTML, DOM, CSS, relational, and user-defined features. Then a procedure with many variation points is used to learn extraction rules from that knowledge base; the variation points include heuristics that range from how to select a condition to how to simplify the resulting rules. We also provide a systematic method to help re-configure our proposal. Our exhaustive experimentation proves that it beats others regarding effectiveness and is efficient enough for practical purposes. Our proposal was devised to be as configurable as possible, which helps adapt it to particular web sites and evolve it when necessary.
Full text
On Learning Web Information Extraction Rules with TANGO Patricia Jiménez∗ Universidad de Sevilla, ETSI Informática. Avda. de la Reina Mercedes, s/n. Sevilla E-41012, Spain. Rafael Corchuelo Universidad de Sevilla, ETSI Informática. Avda. de la Reina Mercedes, s/n. Sevilla E-41012, Spain. Abstract The research on Enterprise Systems Integration focuses on proposals to support business processes by re-using existing systems. Wrappers help re-use web applications that provide a user interface only. They emulate a human user who interacts with them and extracts the information of interest in a structured format. In this article, we present TANGO, which is our proposal to learn rules to extract information from semi-structured web documents with high precision and recall, which is a must in the context of Enterprise Systems Integration. It relies on an open catalogue of features that helps map the input documents into a knowledge base in which every DOM node is represented by means of HTML, DOM, CSS, relational, and user-defined features. Then a procedure with many variation points is used to learn extraction rules from that knowledge base; the variation points include heuristics that range from how to select a condition to how to simplify the resulting rules. We also provide a systematic method to help re-configure our proposal. Our exhaustive experimentation proves that it beats others regarding effectiveness and is efficient enough for practical purposes. Our proposal was devised to be as configurable as possible, which helps adapt it to particular web sites and evolve it when necessary. Keywords: Web information extraction; semi-structured documents; open catalogues of features; learning rules; variation points; configuration method. ∗Corresponding author Email addresses: [email protected] (Patricia Jiménez), [email protected] (Rafael Corchuelo) Preprint submitted to Elsevier June 13, 2016
1. Introduction Enterprise Systems Integration is an engineering discipline that deals with technologies and methods that help engineers devise solutions to support business processes by re-using existing enterprise systems [12]. The problem is challenging insofar web applications are concerned because they are typically designed to be used by people, not by software agents. In many cases, they have to be integrated by emulating the interactions of a human user and then extracting the information of interest from the resulting web documents. Such interactions are performed by means of so-called wrappers, which are typically composed of the following modules: a form filler, which maps queries onto search forms, a navigator, which navigates from the search forms to the appropriate documents, an information extractor, which extracts the information of interest from the previous documents, and an information verifier, which checks the information extracted. Enterprise Systems Integration requires wrappers that can achieve high precision and recall, chiefly when the business processes that they support are mission-critical; the time to learn the rules or to execute them is not an issue as long as it falls within reasonable limits. Our research focuses on information extractors. The literature provides some proposals to extract information from unstructured documents [33], that is, documents that are written in natural language, and others to deal with semistructured documents [6], that is, HTML-based documents in which the information is rendered in tables, lists, forms, and similar regular formats. They can be further classified into heuristic-based information extractors or rule-based information extractors. The former are unsupervised proposals that rely on general heuristics that have proven to work well in many cases; the latter require specific-purpose rules that are learnt from a learning set supervisedly or unsupervisedly, depending on whether the user has to annotate the learning sets with the information to be extracted or not. A number of authors have worked on orthogonal topics, e.g., finding the regions of a document that provide interesting information [27], finding named entities from a small sample [14, 35], or re-learning the rules with as little effort as possible [36]. Lately, the problem of extracting information from unknown sites is getting much attention, but the only conclusive results are regarding unstructured documents [10, 22]. We focus on supervised rule-based proposals to learn rules to extract information from semi-structured web documents. We have surveyed many proposals in this field [3–5, 7, 8, 11, 13, 16–18, 20, 21, 23, 28, 30, 32]. Our conclusion is that the authors have tried to make them very general so that they can be applied to documents from as many web sites as possible. The problem is that most of them are monolithic solutions, that is, there is a tight inter-dependency between the features that are computed from the input documents and the learning procedure, which was not designed to be re-configured. This makes it difficult to evolve them independently so that they can be adapted to particular web sites or to keep with the evolution of HTML. It is not surprising then that web information extraction is an active research field in which new proposals sprout out continuously; unfortunately, they tend to fade away quickly because 2
they are not flexible enough. In our opinion, the research in this field must focus on flexible proposals, which implies that they have to use an open catalogue of features, a learning procedure with variation points, and there must be a method to help re-configure them so that they can be adapted when necessary. The catalogue being open means that the learning procedure does not depend on any particular features, which implies that they can be included, removed, or replaced very easily in order to experiment with them. This allows to adapt a proposal to a particular web site or to changes in the way that HTML is used. A learning procedure with variation points relies on a number of heuristics whose implementation is plugged into the procedure; this makes it very flexible and facilitates adapting the proposal when necessary or trying new alternatives if one thinks that they can result in better performance. Note that adapting a proposal requires to make multi-criteria decisions, which is not intuitive at all; therefore, it is also necessary to have a method to help re-configure it when necessary. None of the proposals that we have surveyed fulfils the previous requirements. A few authors have explored the idea of using an open catalogue of features [3, 11, 13, 18], but they did not identify the variation points of their learning procedures; consequently, none of them produced a method to help re-configure their proposals. In this article, we present TANGO, which is a rule learner that specialises in web information extraction; it relies on an open catalogue of features and a learning procedure in which we have identified eight variation points that implement eleven heuristics; furthermore, we provide a method to help re-configure it. Our detailed conceptual comparison reveals that our proposal clearly diverges from the existing ones and our exhaustive experimental study confirms that it is more effective than other state-of-the-art proposals and that it is efficient enough for practical purposes. In our experiments, we have been able to learn very good rules from as few as six randomly-selected documents. The rest of the article is organised as follows: Section 2 presents a detailed description of our proposal; Section 3 reports on how we have configured it; Section 4 presents the results of our experimental analysis; Section 5 analyses the related work; finally, Section 6 concludes our work. 2. Description of our proposal In this section, we describe our proposal. We first present some definitions and then delve into our catalogue of features, our learning procedure, our variation points, and our configuration method. 2.1. Definitions Definition 1 (Documents). We use the standard notation to represent variables, sets, and logical formulae. We denote sequences as ⟨x1,x2, . . . , xn⟩; given a sequence s, we denote its length as |s|; given two sequences s1and s2, we denote their concatenation as s1⊕s2. 3
Definition 2 (Documents). A document is a character string that adheres to the HTML syntax and can then be represented as the root node of the corresponding DOM tree [15, 34]. Definition 3 (Features). Features are functions that map nodes onto values or other nodes. The former are referred to as attributive features, and they can be based on HTML attributes [15], DOM attributes [34], CSS attributes [2], or user-defined functions; the latter are relational features and they build on the usual relationships amongst the nodes of a DOM tree, e.g., parents or children. Definition 4 (Slots and annotations). A slot is a label that provides a meaning to the information in a node. An annotation is a function that maps a subset of nodes onto a set of slots. We assume that the slots may be organised hierarchically so that there is a first-level slot that contains some nested slots. (Note that it is common to use term slot to refer to both a label and the nodes that are extracted with that label.) Definition 5 (Datasets). A dataset is a ground first-order representation of an annotation and the instantiation of a catalogue of features on a set of documents. The datasets that are used to learn rules are referred to as learning sets and the datasets that are used to test rules are referred to as testing sets. Definition 6 (Rules and conditions). A rule consists of a collection of conditions that characterise the nodes that provide the information to be extracted. We represent them as ⟨h,b1,b2, . . . , bn⟩(n≥0), where h denotes the head, which is a slot instantiator, and bi(i= 1 . . n)denotes the body, which consists of feature instantiators, comparators, and/or further slot instantiators. A slot instantiator is a condition of the form s(N), where s denotes a slot and N is a variable that can be bound to every node in the input documents. A feature instantiator is a condition that binds the value of a feature on a node to a constant or a variable; feature instantiators can be negated, in which case the condition is satisfied if the corresponding feature cannot be instantiated. A comparator is a condition that compares a variable to another variable or a constant using the usual relational operators. A condition is said to be determinate in the context of a rule if it is a feature instantiator, it can be instantiated exactly once on every positive example that is matched by the rule, at most once on every negative example, and does not return the same value on every example. Definition 7 (Scores and gains). We require a rule scorer to assess how good a rule is. Intuitively, it must return high scores for rules that are close to be a solution and low scores for the others. Since our proposal learns rules by adding conditions incrementally, it is also necessary to compute the gain that adding a specific condition achieves. If r represents the current rule and r′represents the rule that results from adding condition c to r, that is, r′=r⊕ ⟨c⟩, then we compute the gain of condition c as p′(s′−s), where p′denotes the number of positive examples matched by rule r′, s′is the score of rule r′, and s is the score of rule r. Realise that we weight the difference of scores with the number 4
ĨŝƌƐƚdŽŬĞŶ ĐŽƵŶƚKĨůĂŶŬƐ ǁŝĚƚŚ ŝƐ^ŝďůŝŶŐ ůĂƐƚdŽŬĞŶ ĐŽƵŶƚKĨhƉƉĞƌĐĂƐĞŝŐƌĂŵƐ ďĂĐŬŐƌŽƵŶĚŽůŽƵƌ ůĞĨƚ ƉĂƌĞŶƚ ŚĞŝŐŚƚ ŝƐ>ŽǁĞƌĐĂƐĞ ŝƐhZ> ůĂƐƚ^ŝďůŝŶŐ ŝƐhƉƉĞƌĐĂƐĞ ďĞŐŝŶƐtŝƚŚWƵŶĐƚƵĂƚŝŽŶ ĐŽƵŶƚKĨhƉƉĞƌĐĂƐĞdŽŬĞŶƐ džWŽƐ ŝƐƵƌƌĞŶĐLJ ŝƐĂƉŝƚĂůŝƐĞĚ ŝƐŵĂŝů LJWŽƐ ĐŽƵŶƚKĨůƉŚĂEƵŵ ĨŽŶƚ^ŝnjĞ ůŝŶĞ,ĞŝŐŚƚ ĨŝƌƐƚ^ŝďůŝŶŐ ĐŽƵŶƚKĨ>ŽǁĞƌĐĂƐĞdƌŝŐƌĂŵƐ ŝƐĂƚĞ ŝƐůĂŶŬ ƚĂŐ ĐŽƵŶƚKĨŚŝůĚƌĞŶ ŝƐ/^E ĞŶĚƐtŝƚŚWĂƌĞŶƚŚĞƐŝƐ ĐŚŝůĚƌĞŶ ĐŽƵŶƚKĨ^ŝďůŝŶŐƐ ďĞŐŝŶƐtŝƚŚWĂƌĞŶƚŚĞƐŝƐ ŚĂƐƵƌƌĞŶĐLJ^LJŵďŽů ůĂƐƚdŽŬĞŶ ŝƐEƵŵďĞƌ ĚŝƐƉůĂLJ ǀĞƌƚŝĐĂůůŝŐŶ ƉĞŶƵůƚŝŵĂƚĞdŽŬĞŶ ŚĂƐƌĂĐŬĞƚĞĚEƵŵďĞƌ ĨŽŶƚtĞŝŐŚƚ ƚĞdžƚůŝŐŶ ƐŝďůŝŶŐ/ŶĚĞdž ĐŽƵŶƚKĨ>ŽǁĞƌĐĂƐĞdŽŬĞŶƐ ŚĂƐƌĂĐŬĞƚĞĚůƉŚĂEƵŵ ďŽƌĚĞƌŽƚƚŽŵtŝĚƚŚ ůĂƐƚdŽŬĞŶ ĐŽƵŶƚKĨ>ĞƚƚĞƌƐ ŝƐzĞĂƌ ďŽƌĚĞƌ>ĞĨƚtŝĚƚŚ ďĞŐŝŶƐtŝƚŚEƵŵďĞƌ ĐŽƵŶƚKĨĂƉŝƚĂůƐ ĐŽƵŶƚKĨ>ŽǁĞƌĐĂƐĞŝŐƌĂŵƐ ŚĂƐYƵĞƐƚŝŽŶDĂƌŬ ŶĞdžƚ^ŝďůŝŶŐ ĐŽƵŶƚKĨŝŐŝƚƐ ŵĂƌŐŝŶŽƚƚŽŵ ŝƐWŚŽŶĞ ůĞŶ ĐŽƵŶƚKĨhƉƉĞƌĐĂƐĞdƌŝŐƌĂŵƐ ďŽƌĚĞƌZŝŐŚƚŽůŽƵƌ ďŽƌĚĞƌŽƚƚŽŵŽůŽƵƌ ŝƐdĞdžƚEŽĚĞ ƚĞdžƚĞĐŽƌĂƚŝŽŶ ĞŶĚƐtŝƚŚWƵŶĐƚƵĂƚŝŽŶ ĐŽƵŶƚKĨŝŐƌĂŵƐ ĚĞƉƚŚ ŚĂƐEŽƚůĂŶŬƐ ŝƐůƉŚĂEƵŵ ĐŽƵŶƚKĨdƌŝŐƌĂŵƐ ĐŽƵŶƚKĨdŽŬĞŶƐ ĐŽƵŶƚKĨ/ŶƚĞŐĞƌƐ ŝƐEƵŵďĞƌ ĂŶĐĞƐƚŽƌ Table 1: Partial catalogue of features. (Sorted by empirical frequency.) of positive examples matched by r′, which helps make a difference that rewards the conditions that match more positive examples. 2.2. Catalogue of features TANGO works on an open catalogue of features, which means that the learning procedure does not require it to provide any specific features. On the contrary, the user can try different features or ways to compute them in order to configure our proposal so that it performs as well as possible. By default, we provide a catalogue that has proven to work well in our experiments. It provides many features that compute the attributes that are defined in the HTML, DOM, and CSS recommendations [2, 15, 34]. It also provides a number user-defined features. The HTML and the CSS features are attributive because they map the DOM nodes onto values that represent their HTML and CSS attributes; the DOM features can be either attributive, e.g., the depth of a node, or relational, e.g., the parent of a node. The user-defined features are typically used to implement simple semantic checks, e.g., whether a node contains a number or not. Table 1 provides an excerpt of our current catalogue. The actual catalogue consists of roughly two hundred features, of which we have shown the most used according to our experimentation. 2.3. Learning procedure The learning procedure works on a learning set that consists of a ground first-order representation of the input documents and their annotation. It then uses a top-down algorithm that learns a rule set for each slot. It starts with an overly-general rule that matches every node in the learning set and then extends it by adding conditions that constraint the subset of nodes that it matches; when 5
1: method TANGO(documents,annotation) 2: – Step 1: initialisation. 3: result =∅ 4: dataset =create a dataset from documents and annotation 5: – Step 2: learn a rule set for every slot. 6: for each different slot in annotation do 7: learningSet =create a learning set for slot from dataset 8: learningSet =preProcessLearningSet(learningSet,slot) 9: ruleset =learnRuleSet(learningSet,slot) 10: result =result ∪ {ruleSet} 11: end 12: return result Figure 1: Main procedure. a rule that matches positive examples only is found, it is considered a solution; the positive examples that it matches are then removed from the learning set and the procedure is re-started until no positive example remains to be matched or it is not possible to find a rule, which is very unlikely in practice. Our proposal also manages a set of savepoints to which it can backtrack if the current search path is not good enough. 2.3.1. Main procedure Figure 1 shows the main procedure, which works on a set of documents and an annotation; it returns a set of rule sets, each of which is specifically tailored to extracting information that belongs to a given slot. The first step consists in initialising the result to an empty set and then creating a dataset from the input documents and their annotation. Basically, we have to loop through a user-provided catalogue of features and try to instantiate them on every node of the input documents. The second step iterates through the set of slots used in the annotation of the input documents. For each slot, it first creates a learning set from the previous dataset, pre-processes it, and then invokes the procedure to learn a rule set; the result is stored in the result variable, which is returned when the loop finishes. Creating the learning set amounts to creating a new dataset in which the positive examples are the nodes that belong to the slot that is being analysed and the negative examples are the remaining nodes. In order to reduce the computational effort, the learning sets that correspond to nested slots have information about the nodes in the enclosing slots only. The resulting learning set must be simplified using a variation point called preProcessLearningSet so that learning is as efficient as possible. Example 1. Figure 2 shows a sample web document with a listing of phone codes; the countries for which the system does not have a code are starred. Table 2 shows a partial instantiation of our catalogue of features and Table 3 shows the corresponding annotation. 6
ŶŽĚĞ ƚĂŐ ƐƚLJůĞ ĚĞƉƚŚ ĐŚŝůĚƌĞŶ LJWŽƐ džWŽƐ ůĞŶ ŝƐEƵŵďĞƌ ƉĂƌĞŶƚ ůĞĨƚ Ŷ ϭ Śƚŵů ϭ Ϯ Ϭ Ϭ ϭϴ ĨĂůƐĞ Ŷ Ϯ ŚĞĂĚ Ϯ ϭ Ϭ Ϭ ϱ ĨĂůƐĞ Ŷ ϭ Ŷ ϯ ƚŝƚůĞ ϯ ϭ Ϭ Ϭ ϱ ĨĂůƐĞ Ŷ Ϯ Ŷ ϰ ϰ Ϭ Ϭ Ϭ ϱ ĨĂůƐĞ Ŷ ϯ Ŷ ϱ ďŽĚLJ Ϯ ϯ Ϭ Ϭ ϭϯ ĨĂůƐĞ Ŷ ϭ Ŷ Ϯ Ŷ ϲ Śϭ ϯ ϭ Ϭ Ϭ Ϯ ĨĂůƐĞ Ŷ ϱ Ŷ ϳ ϰ Ϭ Ϭ Ϭ Ϯ ĨĂůƐĞ Ŷ ϲ Ŷ ϴ Ƶů Ă ϯ ϯ ϭϲ Ϭ ϵ ĨĂůƐĞ Ŷ ϱ Ŷ ϲ Ŷ ϵ ůŝ ϰ ϯ ϭϲ Ϭ ϯ ĨĂůƐĞ Ŷ ϴ Ŷ ϭϬ ƐƉĂŶ ϱ ϭ ϭϲ Ϭ ϭ ĨĂůƐĞ Ŷ ϵ Ŷ ϭϭ ϲ Ϭ ϭϲ Ϭ ϭ ĨĂůƐĞ Ŷ ϭϬ Ŷ ϭϮ ϱ Ϭ ϭϲ ϯϮ ϭ ĨĂůƐĞ Ŷ ϵ Ŷ ϭϬ Ŷ ϭϯ ƐƉĂŶ ϱ ϭ ϭϲ ϯϲ ϭ ƚƌƵĞ Ŷ ϵ Ŷ ϭϮ Ŷ ϭϰ ϲ Ϭ ϭϲ ϯϲ ϭ ƚƌƵĞ Ŷ ϭϯ Ŷ ϭϱ ůŝ ϰ ϯ ϯϮ Ϭ ϯ ĨĂůƐĞ Ŷ ϴ Ŷ ϵ Ŷ ϭϲ ϱ Ϭ ϯϮ Ϭ ϭ ĨĂůƐĞ Ŷ ϭϱ Ŷ ϭϳ ϱ Ϭ ϯϮ ϮϬ ϭ ĨĂůƐĞ Ŷ ϭϱ Ŷ ϭϲ Ŷ ϭϴ ϱ Ϭ ϯϮ ϰϬ ϭ ĨĂůƐĞ Ŷ ϭϱ Ŷ ϭϳ Ŷ ϭϵ ůŝ ϰ ϯ ϰϴ Ϭ ϯ ĨĂůƐĞ Ŷ ϴ Ŷ ϭϱ Ŷ ϮϬ ƐƉĂŶ ϱ ϭ ϰϴ Ϭ ϭ ĨĂůƐĞ Ŷ ϭϵ Ŷ Ϯϭ ϲ Ϭ ϰϴ Ϭ ϭ ĨĂůƐĞ Ŷ ϮϬ Ŷ ϮϮ ϱ Ϭ ϰϴ ϯϮ ϭ ĨĂůƐĞ Ŷ ϭϵ Ŷ ϮϬ Ŷ Ϯϯ ƐƉĂŶ ϱ ϭ ϰϴ ϯϲ ϭ ƚƌƵĞ Ŷ ϭϵ Ŷ ϮϮ Ŷ Ϯϰ ϲ Ϭ ϰϴ ϯϲ ϭ ƚƌƵĞ Ŷ Ϯϯ Ŷ Ϯϱ Ƶů ď ϯ ϭ ϲϰ Ϭ Ϯ ĨĂůƐĞ Ŷ ϱ Ŷ ϴ Ŷ Ϯϲ ůŝ ϰ Ϯ ϲϰ Ϭ Ϯ ĨĂůƐĞ Ŷ Ϯϱ Ŷ Ϯϳ ƐƉĂŶ ϱ ϭ ϲϰ Ϭ ϭ ĨĂůƐĞ Ŷ Ϯϲ Ŷ Ϯϴ ϲ Ϭ ϲϰ Ϭ ϭ ĨĂůƐĞ Ŷ Ϯϳ Ŷ Ϯϵ ƐƉĂŶ ϱ ϭ ϲϰ ϯϲ ϭ ƚƌƵĞ Ŷ Ϯϲ Ŷ Ϯϳ Ŷ ϯϬ ϲ Ϭ ϲϰ ϯϲ ϭ ƚƌƵĞ Ŷ Ϯϵ ZĞůĂƚŝŽŶĂůĨĞĂƚƵƌĞƐ ,dD> ZĞŶĚĞƌŝŶŐ hƐĞƌͲĚĞĨŝŶĞĚ KD ƚƚƌŝďƵƚŝǀĞĨĞĂƚƵƌĞƐ Table 2: Sample feature instantiation. ŶŽĚĞ ƐůŽƚ ŶŽĚĞ ƐůŽƚ ŶŽĚĞ ƐůŽƚ Ŷ ϭ Ŷ ϭϭ ĐŽƵŶƚƌLJ Ŷ Ϯϭ ĐŽƵŶƚƌLJ Ŷ Ϯ Ŷ ϭϮ Ŷ ϮϮ Ŷ ϯ Ŷ ϭϯ Ŷ Ϯϯ Ŷ ϰ Ŷ ϭϰ ĐŽĚĞ Ŷ Ϯϰ ĐŽĚĞ Ŷ ϱ Ŷ ϭϱ ƌĞĐŽƌĚ Ŷ Ϯϱ Ŷ ϲ Ŷ ϭϲ Ŷ Ϯϲ Ŷ ϳ Ŷ ϭϳ ĐŽƵŶƚƌLJ Ŷ Ϯϳ Ŷ ϴ Ŷ ϭϴ Ŷ Ϯϴ Ŷ ϵ ƌĞĐŽƌĚ Ŷ ϭϵ ƌĞĐŽƌĚ Ŷ Ϯϵ Ŷ ϭϬ Ŷ ϮϬ Ŷ ϯϬ ŶŶŽƚĂƚŝŽŶ ŶŶŽƚĂƚŝŽŶ ŶŶŽƚĂƚŝŽŶ ^ƚƌƵĐƚƵƌĞŽĨƐůŽƚƐ ƌĞĐŽƌĚ 0000000000000000000000000000000000000 0000000000000000000000000000000000000 0000000000000000000000000000000000000 0000000000000000000000000000000000000 0000000000000000000000000000000000000 ĐŽƵŶƚƌLJ 0000000000000000000000000000000000000 0000000000000000000000000000000000000 0000000000000000000000000000000000000 0000000000000000000000000000000000000 ĐŽĚĞ Table 3: Sample annotation. 7
Śƚŵů ŚĞĂĚ ďŽĚLJ Śϭ Ƶů ƐƚLJůĞсΗĂΗ Ƶů ƐƚLJůĞсΗďΗ ůŝ ƐƉĂŶ ƐƉĂŶ ƐƉĂŶ ƐƉĂŶ WŚŽŶĞĐŽĚĞƐ ^ƉĂŝŶ ϯϰ ŽƉLJƌŝŐŚƚ ϮϬϭϱ Ŷ ϭ Ŷ Ϯ Ŷ ϱ Ŷ ϲ Ŷ ϴ Ŷ Ϯϱ Ŷ ϭϵ Ŷ ϮϮ Ŷ Ϯϳ Ŷ Ϯϵ ƚŝƚůĞ WŚŽŶĞͲĐŽĚĞƐĐŽŵ Ŷ ϯ DĂůŝ Ŷ ϰ Ŷ ϳ Ŷ Ϯϭ Ŷ Ϯϯ Ŷ Ϯϴ Ŷ ϯϬ Ͳ Ŷ ϭϴ ůŝ Ŷ ϭϱ Ύ Ŷ ϭϳ Ŷ ϮϬ Ŷ Ϯϰ ůŝ ƐƉĂŶ ƐƉĂŶ ůďĂŶŝĂ ϯϱϱ Ŷ ϵ Ŷ ϭϮ Ŷ ϭϭ Ŷ ϭϰ Ͳ Ŷ ϭϬ Ύ Ŷ ϭϯ Ŷ ϭϲ ůŝ Ŷ Ϯϲ WŚŽŶĞĐŽĚĞƐ ůďĂŶŝĂͲ ϯϱϱ ΎDĂůŝΎ ^ƉĂŝŶͲ ϯϰ ŽƉLJƌŝŐŚƚϮϬϭϱ E ^ůŽƚ ƌĞĐŽƌĚ ^ůŽƚ ĐŽƵŶƚƌLJ ^ůŽƚ ĐŽĚĞ Figure 2: Sample web document. Regarding slot record, TANGO first creates a learning set in which the nodes that belong to that slot are positive examples and the others are negative ones; the instantiation of the features remains the same. Regarding slots country and code, which are nested within the previous slot, TANGO creates similar learning sets, the difference being that features are instantiated only on the nodes that belong to a sub-tree that is known to be a record. Since this example is very simple, it is not actually necessary to perform any pre-processing. From those learning sets, TANGO learns the following rule sets: {⟨record(N0),tag(N0,‘li’),parent(N0,N1),style(N1,‘a’)⟩}, {⟨country(N0),xPos(N0,A1),A1≤20,¬left(_,N0)⟩, ⟨country(N0),xPos(N0,20)⟩}, {⟨code(N0),¬tag(N0,_),isNumber(N0)⟩} 2.3.2. Learning a rule set Figure 3 presents the procedure to learn a rule set, which works on a learning set and a slot; it returns a set of rules that are specifically tailored to extracting information that belongs to that slot. As usual, the first step is an initialisation step that simply sets the resulting rule set to the empty set. The second step is a loop that iterates until no new rule is found or no positive example remains in the learning set. In each iteration, the procedure to learn a rule is invoked using the current learning set and the input slot as parameters. If this procedure returns null, then it means that it has not been able to find a rule that matches the positive examples in the learning set; otherwise, it 8
1: method learnRuleSet(learningSet,slot) 2: – Step 1: initialisation. 3: ruleSet =∅ 4: – Step 2: learn rules. 5: repeat 6: rule =learnRule(learningSet,slot) 7: if rule =null then 8: ruleSet =ruleSet ∪ {rule} 9: learningSet =learningSet \(positive examples matched by rule) 10: end 11: until rule =null ∨there are no positive examples in learningSet 12: – Step 3: post-process the rule set. 13: ruleSet =postProcessRuleSet(ruleSet) 14: return ruleSet Figure 3: Procedure to learn a rule set. returns a rule that matches some positive examples and no negative one, that is, a solution. If a rule is returned, then the resulting rule set is updated, the learning set is subtracted the positive examples that are matched by that rule, and the procedure is re-started if the learning set is not empty. The third step relies on variation point postProcessRuleSet, which simplifies the resulting rule set so that it can be executed as efficiently as possible. Example 2. Let us focus on slot country. In the first iteration of Step 2, it learns a rule that matches countries with a phone code, namely: ⟨country(N0),depth(N0,A2),children(N0,A3),yPos(N0,A4),xPos(N0,A5), A5≤20,¬left(N4,N0)⟩ The procedure then removes the positive examples matched by the previous rule from the learning set and invokes the procedure to learn a rule again. Now, it returns a rule that matches starred countries, namely: ⟨country(N0),depth(N0,A2),children(N0,A3),yPos(N0,A4),xPos(N0,A5), A5= 20⟩ Since the previous rules match every positive example, they are then postprocessed, which results in the following simplified rule set: {⟨country(N0),xPos(N0,A1),A1≤20,¬left(_,N0)⟩, ⟨country(N0),xPos(N0,20)⟩} 2.3.3. Learning a rule Figure 4 presents the procedure to learn a rule, which works on a learning set and a slot. It returns a solution if possible, that is, a rule that matches 9
1: method findBestSavepoint(savepoints) 2: (r,s) = select a savepoint (r,s)with maximum score from savepoints 3: sp =savepoints \ {(r,s)} 4: return (r,sp) Figure 7: Procedure to find the best savepoint. 1: method findBetterSavepoint(savepoints,rule,score,learningSet) 2: (r,s) = select a savepoint (r,s)from savepoints such that 3: isSolution(r,learningSet) 4: if r=null ∧s>score then 5: rule =r 6: end 7: return rule Figure 8: Procedure to find a better savepoint. one, if any, and findBetterSavepoint, to find one that is better than a given solution, if any. Next, we provide additional explanations on each procedure. Figure 6 shows the procedure to update the savepoints. It works on the current set of savepoints, the current rule (before it is extended with the best candidates), the set of candidates that have been selected to update the savepoints, and the learning set. It returns an updated set of savepoints that fulfils two properties, namely: a) it has at most ksavepoints, where kis a user-defined parameter; b) and there is at most one savepoint that is a solution (note that if TANGO backtracks to such a savepoint, then it returns it immediately; thus, it suffices to keep one savepoint that is a solution). The procedure iterates over the set of candidates and proceeds in three steps. In the first step, it creates a new rule by adding the condition in the current candidate and computes its score. In the second step, it searches for a savepoint to replace, namely: if the new rule is a solution, then it searches for the only savepoint that is a solution, if any; if it is not a solution, then it retrieves the savepoint with the minimum score if the set of savepoints is full (since, otherwise, there is no need to replace any savepoint). We assume that if the search for a savepoint fails, then the rule returned is null and the corresponding score is −∞. The third step updates the savepoints as follows: if there is a savepoint to replace and its score is smaller than the score of the new rule, then it is replaced; otherwise, if there is not a savepoint to replace, the new rule is added to the set of savepoints. This guarantees that there are no more than ksavepoints, of which only one can be a solution. Figure 7 shows the procedure to find the best savepoint. It works on the current set of savepoints and returns a tuple of the form (r,sp), where rdenotes the rule associated with the savepoint that has the maximum score or null if no such savepoint exists, and sp denotes the updated set of savepoints. Figure 8 shows the procedure to find a better savepoint, as long as it is a solution. It works on the current set of savepoints, a rule that is a solution, 16
its corresponding score, and the learning set. It first searches for the savepoint that is a solution; if it exists, then it replaces the current rule by the rule that is associated with that savepoint if it scores better; otherwise, it returns the input rule. 2.4. Variation points Our learning procedure relies on a number of variation points, each of which groups one or more heuristics that can be implemented using several alternatives. We describe them in the following subsections. 2.4.1. Variation point VP1: selectCandidates The goal of this variation point is twofold: select the most promising candidates to expand the current rule and some of the remaining ones to create savepoints. This should help TANGO learn very effective extraction rules whose efficiency does not degrade significantly when they are executed. Heuristic H1: select best candidates. We have considered the following alternatives: A0) Select the candidate that provides the maximum gain to extend the current rule and then select the following k= 20 candidates to create savepoints. A1) Select the candidate with the maximum gain as long as it is at least 80% the maximum gain that a condition can achieve on the current rule; else, select every determinate condition; if no such condition is a candidate, then select the one with the highest gain. To create the savepoints, we select the candidate with the highest gain out of the candidates that result in a solution, if any; if it corresponds to a non-determinate condition, then we also select the candidates whose gain is at least 80% the gain of that condition; otherwise, no more candidates are selected. The first alternative is a simple approach that has been used many times in the literature. Although it is very simple and might work well in some cases, our intuition was that there would be cases in which the candidates selected would lead to local maxima and would not help learn good rules. The rationale behind the second alternative is that the candidate with the maximum gain can be added to the current rule as long as its gain is high enough with regard to the maximum gain that a condition may achieve; otherwise, it is better to add determinate conditions because they help expand the search space; if no determinate conditions exists, then we have to resort to the condition that provides the maximum gain, like in Alternative A0. Note that there might be still cases in which we need to perform backtracking. Thus, we think that it makes more sense to select a candidate that results in a solution, unless there is another candidate that results in more gain, in which case the former might be kept as a savepoint, if possible. Now, if the candidates selected to extend the current rule are not determinate, we then select the candidates that achieve a gain that is high enough in comparison with that candidate; otherwise, if the selected candidates were determinate, no more candidates are selected to create savepoints. The rationale behind this idea is that if determinate conditions are selected, it then means that there were no conditions whose gain exceeded 17
80% the maximum gain since, otherwise, they would have been selected instead of determinate conditions. Thus, in this case, we are not interested in using conditions that do not provide enough gain to create savepoints. If a nondeterminate condition is selected to expand the rule, we can be less demanding regarding the candidates that should be selected to create new savepoints so that we shall only select the kbest candidates as long as their gain exceeds 80% the gain of the non-determinate condition selected to extend the current rule. The reason why we selected k= 20 candidates and 80% the maximum gain is purely experimental, but we cannot report on all of our results due to space constraints; thus, we decided to report on the best ones only. 2.4.2. Variation point VP2: preProcessLearningSet This variation point deals with simplifying a learning set so that the learning process is more efficient; the simplification might also have a positive impact on the effectiveness and the efficiency of the resulting rules. Heuristic H2: reduce negative examples. We have considered the following alternatives: A0) Work with the whole learning set. A1) Select a subset of negative examples that are in the neighbourhood of every positive example. A2) Select a subset of negative examples that are in the neighbourhood of every positive example plus a random subset of the remaining negative examples. A3) Select a subset with the most similar negative examples that correspond to every positive example. A5) Select a subset with the most similar negative examples that correspond to every positive example plus a random subset of the remaining negative examples. The first alternative is a simple approach in which every negative example is considered in the learning process. Our intuition was that this would not be efficient because there are typically many negative examples. Our hypothesis was that it would be possible to discard many such negative examples from the learning set without a negative impact on the effectiveness of the resulting rules, as long as the negative examples that are kept are still representative of the whole set of negative examples. The other alternatives were intended to find that subset. The rationale behind Alternative A1 is to discard the negative examples that are not in the neighbourhood of the nodes that correspond to the positive examples. By neighbourhood, we refer to the nodes that can be reached within a given radius by applying relational features transitively. We experimented with radius r= 10 when computing the neighbourhood of a given positive example. Alternative A2 is based on A1, but it includes a set of negative examples that are selected randomly; we set the radius to compute the neighbours to r= 10 and the percentage of nodes selected randomly to p= 10%. Alternative A3 searches for the most similar negative examples and discards the remaining ones. We measured the similarity between any two nodes using the well-known Euclidean distance on the attributive features; in the case of non-numeric features, we computed the difference between two different values as 1.00 and the difference between equal values as 0.00. We experimented with the k= 50 most similar negative examples to each positive example. Alternative A4 explores the kmost 18
similar negative examples for each positive example but it includes a small percentage of negative examples that are selected randomly; we selected the k= 50 most similar negative examples to each positive example and p= 50% of the remaining negative examples. We experimented with many different radiuses and percentages, but we cannot report on them all due to space constraints; this is the reason why we report on the best values only. Heuristic H3: binarise features. We have considered the following alternatives: A0) Work with the original features. A1) Binarise them. When TANGO selects a feature instantiator to extend the current rule, it makes a blind decision: thus far, that instantiator is the best condition that can be added to the rule, but the value of the feature is not constrained at all; if necessary, it can be constrained later using a comparator. In other words, constraining the value of a feature is a two-step procedure. Binarising features is a process by means of which a single step suffices to instantiate a feature and constraint its value. Obviously, only attributive features can be binarised because they are the only ones that provide values that can be constrained by means of comparators. The binarisation process works as follows: a discrete feature fthat ranges over the set of values {v1,v2, . . . , vn}is transformed into a collection of new features of the form fv1,fv2, . . . , fvn; simply put, fvi(N)is satisfied as long as f(N,A)∧A=viis satisfied, where Nranges over the set of nodes, A ranges over the set of values of feature f, and iranges in interval 1. . n. A numeric feature fthat ranges over the set of values {v1,v2, . . . , vn}is transformed into a collection of new features of the form fθ v1,fθ v2, . . . , fθ vn, where θrepresents a comparison operator; simply put, fθ vi(N)is satisfied as long as f(N,A)∧Aθviis satisfied, where Ndenotes a variable that ranges over the set of nodes, A is a variable that ranges over the set of values of feature f,θis a comparison operator, and iranges in interval 1. . n. 2.4.3. Variation point VP3: isPromisingCandidate This variation point deals with determining if a candidate is good enough to stop the search for new candidates. The goal is to configure TANGO so that it can learn rules more efficiently without degrading their effectiveness or increasing the time required to execute them. Heuristic H4: check promising candidates. We have considered the following alternatives: A0) No condition is considered promising enough to stop the search unless it leads to a rule that matches all of the positive examples matched by the current rule and discards all of the negative examples that it matches. A1) Stop the search when the gain achieved by a condition is at least 80% the maximum possible gain on the current rule. A2) Like Alternative A1, but we also require the resulting rule to be a solution. Alternative A0 is the safest one, since almost every condition is analysed and transformed into a candidate to extend the current rule or to create a savepoint. The only case in which not all of the candidates are evaluated is when the best solution is found. The rationale behind Alternative A1 is that Heuristic H1 19
selects a candidate whose gain is at least 80% the maximum possible gain on the current rule; thus, we might stop the search for candidates when such a candidate is found; the only problem would be that if that candidate proved not to be good enough in the forthcoming iterations, then we would miss some better candidates that would have been evaluated later in the same iteration. Alternative A2 is a bit more demanding since it requires the candidate on which the search stops to result in a solution. 2.4.4. Variation point VP4: ruleScorer This variation point deals with assessing rules. The goal is to configure TANGO so that it learns extraction rules that are more effective and efficient. Heuristic H5: compute scores. We have considered the following alternatives, where tp,tn,fp, and fn denote the components of a confusion matrix and N= tp+fp+tn+fn: A0) Information Content, which computes the score as log tp tp+fp . A1) Accuracy-based Information Content, which computes it as log tp+tn tp+fp+fn+tn . A2) Satisfaction, which computes it as tp tp+fp −tp+fn N 1−tp+fn N . A3) Laplace Estimate, which computes it as tp+1 tp+fp+2 . A4) Piatetski-Shapiro’s measure, which computes it as tp tn−fp fn N2. Alternative A0 computes the score as the logarithm of precision, which penalises very much conditions that reduce the number of positive examples matched by the current rule. Alternative A1 is similar, but it computes the logarithm of accuracy, which takes both the number of false negatives and true negatives into account. Intuitively, the higher the number of true positive and true negatives, the better; contrarily, the higher the number of false positive and false negatives, the worse. Satisfaction reaches its maximum when precision is close to 1.00 and decreases steadily as the number of positive examples matched decreases. Alternative A3 penalises rules that match few positive examples; if a rule does not match any examples, then the result is 0.50, which is as effective as a random guess; contrarily, if it matches many examples, it tends to the precision. Finally, Alternative A4 tends to give higher scores when there are more true positives and true negatives than false negatives and false positives, respectively. 2.4.5. Variation point VP5: bound This variation point deals with determining whether a condition deserves to be selected as a candidate to extend the current rule or to create a savepoint. The goal is to configure TANGO so that it learns extraction rules more efficiently without degrading their effectiveness or increasing their execution time. Heuristic H6: prune candidates. We have considered the following alternatives: A0) Do not prune at all. A1) Prune every condition that does not result in a gain that is at least 80% the gain of the best condition found so far, unless it is a determinate condition; if a determinate condition is found, then the pruning 20
threshold is changed to 80% the maximum gain that a condition can achieve on the current rule. Alternative A0 is the safest one because it does not prune any of the conditions that result from branching the current rule; that is, the search is exhaustive. The second alternative prunes the conditions that do not achieve a high enough gain with regard to the best condition found so far; intuitively, one might think that if the first condition achieves a given gain, then we might trivially discard every condition that does not exceed that gain, but we guessed that this would be too stringent, not to mention that we need to keep a few ones to create savepoints. Note that determinate conditions are never pruned because they help expand the search space and avoid local maxima. The key is that when such a condition is found, we know that there is at least a condition that can be used to extend the current rule. Actually, Heuristic H1 is not going to select any candidates that do not achieve 80% the maximum gain once a determinate condition is found, so we can make our heuristic much more stringent safely, that is, we can prune every non-determinate condition that cannot achieve the minimum gain. 2.4.6. Variation point VP6: postProcessRuleSet This variation point attempts to simplify a rule set so that it is more efficient. Heuristic H7: post-process rule sets. We have considered the following alternatives: A0) The rule set is not simplified. A1) The rules are simplified by removing useless conditions, subsumed rules, and folding constants. Simplifying a rule set might help execute the rules more efficiently. We guessed that it would be common to find useless conditions in the rules learnt by TANGO. This happens when determinate conditions are added to a rule; such conditions typically provide little or no gain and they are added to escape local maxima; it is in the next iteration that they are expected to introduce new comparators or further feature instantiators, but there are cases in which they are neglected forever because there are other features that result in conditions that provide more gain. We also guessed that some rules might subsume other rules, that is, the examples that they match are a subset of the examples that another rule matches; in such cases, the former rule can be discarded. This happens because every rule is learnt independently from the others. Finally, we also thought that folding constants might help make the rules a little more efficient and easier to understand. Typically, TANGO learns many pairs of conditions of the form f(N,A)∧A=v, where fdenotes an attributive feature, Na variable that can be bound to a node, Aa variable that is bound to the value of feature fon node N, and vis one of the values in the range of that feature; such pairs of conditions may be easily simplified as f(N,v)if variable Ais not used anywhere else. 2.4.7. Variation point VP7: branch This variation point deals with computing the set of conditions that can possibly be added to the current rule. The goal is to configure TANGO so that 21
it can learn extraction rules more efficiently without degrading their effectiveness or increasing the time required to execute them. Heuristic H8: allow recursion. We have considered the following alternatives: A0) No recursion is allowed. A1) Rules are allowed to be recursive. Alternative A0 is very simple, as usual. Alternative A1 is a little more involved because we have to make sure that making a rule recursive does not result in infinite recursion. Such a recursion occurs when a recursive condition includes a variable that is instantiated with the same example that is going to be extracted. The simplest solution to solve this problem is to determine if there exists a complete order amongst the variable used in the recursive condition and the variable in the head of the rule, both of which must be bound to nodes. If such an order exists, then it means that the variable in the recursive condition and the variable in the head cannot be instantiated with the same examples, which guarantees that the recursion is safe; if no such order exists, then the recursion is unsafe and must be avoided. This check can be implemented very efficiently using Ajwani et al.’s algorithm [1], for instance. Heuristic H9: sort conditions. We have considered the following alternatives: A0) Conditions are generated in a random order. A1) Comparators are generated first, then slot instantiators (if recursion is allowed), and then feature instantiators in random order. A2) Comparators are generated first, then slot instantiators (if recursion is allowed), and then the feature instantiators are generated using an empirical frequency-based order. Alternative A0 is the simplest one, as usual. Alternative A1 simply makes it explicit that we guessed that comparators would typically result in higher gains than feature instantiators. Alternative A2 relies on an order that we have computed empirically, cf. Table 1. Note that we have performed hundreds of experiments and that we have used TANGO to learn thousands of rules. What we have done is to compute the frequency with which each feature was used in a rule; we guessed that generating the feature instantiators using that empirical order might help learn rules more efficiently. Heuristic H10: consider input/output modes. We have considered the following alternatives: A0) Do not take input/output modes into account. A1) Take them into account. Alternative A0 is the simplest one and it helps explore as many feature instantiators as possible. Alternative A1 restricts the relational feature instantiators so that the first parameter is a bound variable and the second one is an unbound variable. Note that such a restriction may have a subtle implication regarding the catalogue of features and some relational features. For instance, recall that our running example includes relational features parent and left. If input/output modes are not taken into account, then parent(N,M)helps navigate from a node to its parent if Nis bound and Mis unbound or from a node to its children if Nis unbound and Mis bound; similarly, left(N,M)helps navigate from a node to its left sibling or from a node to its right sibling. Note 22
that this is not possible if input/output modes are taken into account; in such cases, features right and child must be provided explicitly in the catalogue of features or, otherwise, TANGO will not be able to find the children of a node or its right sibling. 2.4.8. Variation point VP8: isTooComplex This variation point deals with preventing TANGO from learning very specific rules, which is expected to have a positive impact on efficiency. Heuristic H11: check complexity of rules. We have considered the following alternatives: A0) Do not use any complexity criteria. A1) Use the Minimum Description Length principle [26]. The idea behind the Minimum Description Length principle is that a rule that requires more bits to be encoded than to encode the examples that it matches is too complex to be explored. The number of bits to encode a rule is computed as the sum of the bits required to encode every condition in its body, which is computed as the number of bits required to encode the features in the catalogue, plus the number of combinations that would result from combining their parameters, the built-in comparators, and the target slot instantiator (if recursion is allowed). 2.5. Configuration method Our proposal relies on an open catalogue of features and many variation points. In order to configure it, it is necessary to use a sound method that allows to explore the different alternatives systematically, so that we can make informed decisions. Our configuration method is purely experimental. We suggest that a repository of datasets from different web sites should be assembled. In order for the conclusions to be statistically solid, the repository must provide a sufficiently large number of documents from different web sites on different domains. The proposal should be run on this repository and the usual effectiveness and efficiency measures should be computed, namely: precision (P), recall (R), the F1score (F1), learning time (LT), and extraction time (ET). Let Mdenote the previous set of performance measures. We assume that the experimenter provides a map βthat assigns a weight in range [0.00 . . 1.00] to every measure in M. Obviously, the weights must sum up to 1.00 so that they are consistent. Now, assume that we are dealing with a performance measure m, that we have gathered a set of values Wregarding it, that adenotes the minimum value in set W, and that bdenotes the maximum value. If mhas to be maximised, then we define its set of normalised values as W′={w′| ∃w·w∈W∧ w′= (w−a) div (b−a)}; otherwise, we define its set of normalised values as W′={w′| ∃w·w∈W∧w′= 1.00 −(w−a) div (b−a)}. (xdiv yequals x/yif y= 0.00; otherwise, it equals 1.00.) The values in W′range in interval [0.00 . . 1.00], so that the closer a value to the lower bound the worse and the closer to the upper bound the better. Let M′denote a set of new measures that are in one-to-one correspondence with the measures in M, but are normalised according to the previous procedure. 23
Let pdenote a configuration of our system in which we have made some decisions regarding the alternative to implement a heuristic in a variation point. Our proposal is to compute its rank as follows: Kp=∑ m′∈M′ β(m)Kp m′ Kp m′=MDRp m′ MDRmax m′ where MDRp m′denotes the mean-to-deviation ratio of alternative pwith regard to normalised performance measure m′and MDRmax m′denotes the maximum mean-to-deviation ratio of performance measure m′across all of the alternatives. This ratio is defined as follows: MDRp m={(µp m)2 σp mif σp m= 0.00 µp motherwise where mdenotes an arbitrary performance measure, µp mdenotes its mean value regarding alternative p, and σp mits standard deviation regarding alternative p. Note that this ratio maps every measure onto a value that weights its mean value with the inverse coefficient of variation (µp m/σp m) as long as the standard deviation is not zero; intuitively, the smallest the coefficient of variation with respect to the mean value, the better that measure because it is more stable. If the standard deviation is zero, the mean-to-deviation ratio is then trivially defined as the mean value. We would also like to mention that our experimental analysis has revealed that some alternatives fail when they are applied to some datasets. Sometimes, the reason is that they consume too much memory; sometimes, they cannot learn a rule in a reasonable time; sometimes, the dataset has some characteristics that make it impossible to execute the learner on it. That means that we also need to compute a failure ratio for every alternative under consideration, which is defined as follows: FR =F D, where Fdenotes the number of datasets on which an alternative did not work, and Ddenotes the number of datasets on which the alternative was run. Intuitively, the closer to 0.00 the better and the closer to 1.00 the worse. We obviously, are not willing to accept an alternative whose failure ratio is different from 0.00, since that means that it is not generally applicable. 3. Configuring our proposal In this section, we report on how we have configured our proposal. Our experimentation environment was set up as follows: 24
ĂƚĞŐŽƌLJ ^ŝƚĞ ^ůŽƚƐ EƵŵďĞƌ ŽĨĚŽĐͲ ƵŵĞŶƚƐ EƵŵďĞƌ ŽĨ,dD> ƌƌŽƌƐ EƵŵďĞƌŽĨ ƉŽƐŝƚŝǀĞ ĞdžĂŵƉůĞƐ EƵŵďĞƌŽĨ ŶĞŐĂƚŝǀĞ ĞdžĂŵƉůĞƐ ŶŶŽƚĂƚŝŽŶ ĞĨĨŽƌƚ /ŶƐŝŐŚƚŝŶƚŽŝǀĞƌƐŝƚLJ :ŽďĐŽŵƉĂŶLJůŽĐĂƚŝŽŶĐĂƚĞŐŽƌLJ ϯϬ ϲϳϬϳ ϯϬϬϬ ϭϮϵϬϱϱϬ ϬϬϰϱϬϬ ϰ:ŽďƐ :ŽďĐŽŵƉĂŶLJůŽĐĂƚŝŽŶĐĂƚĞŐŽƌLJ ϯϬ ϭϭϬϰϳ ϯϬϬϬ ϵϲϱϳϳϱ ϬϬϱϬϬϬ ϲ&ŝŐƵƌĞ:ŽďƐ :ŽďĐŽŵƉĂŶLJůŽĐĂƚŝŽŶĐĂƚĞŐŽƌLJ ϯϬ ϭϲϵϯϳ ϯϬϬϬ ϭϴϲϴϳϮϱ ϬϭϭϱϬϬ ĂƌĞĞƌƵŝůĚĞƌ :ŽďĐŽŵƉĂŶLJůŽĐĂƚŝŽŶĐĂƚĞŐŽƌLJ ϯϬ ϵϯϵϳ ϯϬϬϬ ϭϬϬϱϱϬϬ ϬϬϱϬϬϬ :ŽďŽĨDŝŶĞ :ŽďĐŽŵƉĂŶLJůŽĐĂƚŝŽŶĐĂƚĞŐŽƌLJ ϯϬ ϰϭϬϯ ϯϬϬϬ ϳϮϭϬϳϱ ϬϬϱϬϬϬ ϯϬϬϬ ϵϲϯϴ ϯϬϬϬ ϭϭϳϬϯϮϱ ϬϬϱϰϬϬ ƵƚŽdƌĂĚĞƌ ĂƌĐŽůŽƌĚŽŽƌƐĞŶŐŝŶĞŵŝůĞĂŐĞŵŽĚĞůƉƌŝĐĞ ƚƌĂŶƐŵŝƐƐŝŽŶƚLJƉĞ ϯϬ ϮϳϯϮϯ ϯϬϬϬ ϭϮϰϲϮϲϳ ϬϮϭϯϬϬ ĂƌDĂdž ĂƌĐŽůŽƌŵŝůĞĂŐĞŵŽĚĞůƉƌŝĐĞƚƌĂŶƐŵŝƐƐŝŽŶ LJĞĂƌƚLJƉĞ ϯϬ ϭϵϭϰϳ ϯϬϬϬ ϵϮϮϮϲϯ ϬϭϱϳϬϬ ĂƌŽŶĞ ĂƌĐŽůŽƌĚŽŽƌƐĞŶŐŝŶĞůŽĐĂƚŝŽŶŵĂŬĞŵŝůĞĂŐĞ ŵŽĚĞůƉƌŝĐĞƚƌĂŶƐŵŝƐƐŝŽŶLJĞĂƌƚLJƉĞ ϯϬ ϭϭϴϴϬ ϯϬϬϬ ϳϮϭϭϮϱ ϬϮϭϳϬϬ ůĂƐƐŝĐĂƌƐĨŽƌ^ĂůĞ ĂƌĐŽůŽƌůŽĐĂƚŝŽŶŵĂŬĞŵŽĚĞůƉƌŝĐĞƚƌĂŶƐŵŝƐƐŝŽŶ LJĞĂƌƚLJƉĞ ϯϬ ϮϱϬϯ ϮϴϵϬ ϭϬϲϳϴϱϬ ϬϮϯϳϬϬ /ŶƚĞƌŶĞƚƵƚŽŐƵŝĚĞ ĂƌĐŽůŽƌĚŽŽƌƐĞŶŐŝŶĞůŽĐĂƚŝŽŶŵŝůĞĂŐĞƉƌŝĐĞ ƚƌĂŶƐŵŝƐƐŝŽŶƚLJƉĞ ϯϬ ϭϲϯϵϬ ϯϬϬϬ ϵϲϱϲϳϴ ϬϮϬϱϬϬ ϯϬϬϬ ϭϱϰϰϵ Ϯϵϳϴ ϵϴϰϲϯϲ ϬϮϭϯϰϴ ,ĂĂƌƚ WƌŽƉĞƌƚLJĂĚĚƌĞƐƐďĞĚƌŽŽŵƐƉƌŝĐĞ ϯϬ ϰϬϬϬ ϵϬϬ ϵϲϲϮϬϬ ϬϭϬϬϬϬ ,ŽŵĞƐ WƌŽƉĞƌƚLJĂĚĚƌĞƐƐďĞĚƌŽŽŵƐďĂƚŚƌŽŽŵƐƐŝnjĞƉƌŝĐĞ ϯϬ ϵϵϵϯ ϯϬϬϬ ϱϵϳϰϯϯ ϬϭϯϰϬϬ ZĞŵĂdž WƌŽƉĞƌƚLJĂĚĚƌĞƐƐďĞĚƌŽŽŵƐďĂƚŚƌŽŽŵƐƐŝnjĞƉƌŝĐĞ ϯϬ ϳϱϳϬ ϯϬϬϬ ϭϮϬϵϳϱϬ ϬϭϱϬϬϬ dƌƵůŝĂ WƌŽƉĞƌƚLJĂĚĚƌĞƐƐďĞĚƌŽŽŵƐďĂƚŚƌŽŽŵƐƐŝnjĞƉƌŝĐĞ ϯϬ ϯϭϮϳϯ ϯϬϬϬ ϮϳϯϮϬϬϬ ϬϮϭϬϬϬ ϯϬϬϬ ϭϯϮϬϵ Ϯϰϳϱ ϭϯϳϲϯϰϲ ϬϭϯϴϯϬ tĞďD ŽĐƚŽƌŶĂŵĞĂĚĚƌĞƐƐƉŚŽŶĞƐƉĞĐŝĂůƚLJ ϯϬ ϮϰϭϬ ϯϬϬϬ ϭϮϴϳϮϬϬ ϬϮϯϱϬϬ ŵĞDĞĚŝĐĂůƐƐŽĐ ŽĐƚŽƌŶĂŵĞĂĚĚƌĞƐƐƉŚŽŶĞƐƉĞĐŝĂůƚLJ ϯϬ ϯϲϬϬ ϯϬϬϬ ϴϲϴϮϬϬ ϬϯϰϬϬϬ ĞŶƚŝƐƚƐ ŽĐƚŽƌŶĂŵĞĂĚĚƌĞƐƐƉŚŽŶĞĨĂdžƐƉĞĐŝĂůƚLJ ϯϬ ϭϬϯϮϳ ϮϴϬϬ ϮϳϱϮϱϬ ϬϮϭϵϬϬ ƌ^ĐŽƌĞ ŽĐƚŽƌŶĂŵĞĂĚĚƌĞƐƐƉŚŽŶĞƐƉĞĐŝĂůƚLJ ϯϬ ϯϯϬϳ Ϯϳϭϰ ϱϲϳϵϬϬ ϬϮϭϮϬϬ ^ƚĞĂĚLJ,ĞĂůƚŚ ŽĐƚŽƌŶĂŵĞĂĚĚƌĞƐƐƐƉĞĐŝĂůƚLJ ϯϬ ϮϰϬϬ ϯϬϬϬ ϮϰϴϭϭϬϬ ϬϯϭϮϬϬ ϯϬϬϬ ϰϰϬϵ ϮϵϬϯ ϭϬϵϱϵϯϬ ϬϮϰϳϯϲ >ŝŶŬĞĚ/Ŷ ǀĞŶƚĚĂƚĞƉůĂĐĞƚŝƚůĞƵƌů ϯϬ Ϯϯϲϳ ϮϵϬϬ ϵϬϳϳϴϬ ϬϮϬϯϬϬ ůůŽŶĨĞƌĞŶĐĞƐ ǀĞŶƚĚĂƚĞƉůĂĐĞƚŝƚůĞƵƌů ϯϬ ϯϬϰϳ ϯϬϬϬ ϭϮϳϯϵϰϬ ϬϯϰϱϬϬ DďĞŶĚŝ ǀĞŶƚĚĂƚĞƉůĂĐĞƚŝƚůĞƵƌů ϯϬ ϮϳϬϬ ϯϬϬϬ ϲϭϮϬϬϬ ϬϭϭϴϬϬ Z>ĞĂƌŶŝŶŐ ǀĞŶƚĚĂƚĞƉůĂĐĞƚŝƚůĞƵƌů ϯϬ ϭϰϬϬ ϯϬϬϬ ϯϯϴϴϴϬ ϬϭϮϰϬϬ ϯϬϬϬ Ϯϯϳϵ Ϯϵϳϱ ϳϴϯϭϱϬ ϬϮϬϳϯϬ ůďĂŶŝĂDŽǀŝĞƐ &ŝůŵƚŝƚůĞĚŝƌĞĐƚŽƌĂĐƚŽƌLJĞĂƌƌƵŶƚŝŵĞ ϯϬ ϮϬϵϬ ϮϯϱϬ ϲϲϵϴϯϯ ϬϭϮϯϬϬ ůůDŽǀŝĞƐ &ŝůŵƚŝƚůĞĚŝƌĞĐƚŽƌĂĐƚŽƌLJĞĂƌƌƵŶƚŝŵĞ ϯϬ ϯϮϯϯ ϳϴϯϯ ϯϲϰϮϴϯϯ ϬϭϰϲϬϬ ŝƐŶĞLJDŽǀŝĞƐ &ŝůŵƚŝƚůĞĂĐƚŽƌLJĞĂƌƌƵŶƚŝŵĞ ϯϬ ϱϵϰϬ ϯϬϬϬ ϲϲϮϳϬϬ ϬϭϬϮϬϬ /D &ŝůŵƚŝƚůĞĚŝƌĞĐƚŽƌĂĐƚŽƌLJĞĂƌƌƵŶƚŝŵĞ ϯϬ ϭϮϬϬ ϰϬϯϯ ϭϴϬϮϯϲϳ ϬϭϭϴϬϬ ^ŽƵů&ŝůŵƐ &ŝůŵƚŝƚůĞĚŝƌĞĐƚŽƌĂĐƚŽƌLJĞĂƌ ϯϬ ϲϲϭϯ ϲϱϰϬ ϭϳϵϴϱϬϬ ϬϬϱϰϬϬ ϯϬϬϬ ϯϴϭϱ ϰϳϱϭ ϭϳϭϱϮϰϳ Ϭϭϭϲϯϲ ďĞŽŽŬƐ ŽŽŬƚŝƚůĞĂƵƚŚŽƌƉƌŝĐĞŝƐďŶ ϯϬ ϱϴϳϯ ϯϱϲϬ ϴϯϳϬϰϬ ϬϭϰϳϬϬ ǁĞƐŽŵĞŽŽŬƐ ŽŽŬƚŝƚůĞĂƵƚŚŽƌƉƌŝĐĞŝƐďŶLJĞĂƌ ϯϬ ϰϯϮϳ ϯϳϭϳ ϲϲϭϮϴϯ ϬϭϱϳϬϬ ĞƚƚĞƌtŽƌůĚŽŽŬƐ ŽŽŬƚŝƚůĞĂƵƚŚŽƌƉƌŝĐĞ ϯϬ ϰϲϬϬ ϯϰϱϬ ϭϵϳϭϲϱϬ ϬϭϰϵϬϬ DĂŶLJŽŽŬƐ ŽŽŬƚŝƚůĞĂƵƚŚŽƌLJĞĂƌ ϯϬ ϭϯϬϬϬ ϯϬϱϬ ϭϯϱϭϱϮϱ ϬϭϱϰϬϬ tĂƚĞƌƐƚŽŶĞƐ ŽŽŬƚŝƚůĞĂƵƚŚŽƌƉƌŝĐĞ ϯϬ ϭϮϵϭϬ ϯϭϱϬ ϭϯϴϱϲϬϬ ϬϮϭϳϬϬ ϯϬϬϬ ϴϭϰϮ ϯϯϴϱ ϭϮϰϭϰϮϬ Ϭϭϱϲϰϴ WůĂLJĞƌWƌŽĨŝůĞƐ WůĂLJĞƌŶĂŵĞďŝƌƚŚŚŝŐŚƚǁĞŝŐŚƚĐůƵď ϯϬ ϯϱϬϳ ϯϬϬϬ ϯϬϴϰϬϬϬ ϬϮϭϬϬϬ h& WůĂLJĞƌŶĂŵĞďŝƌƚŚĐŽƵŶƚƌLJƉŽƐŝƚŝŽŶ ϯϬ ϯϭϴϬ ϯϬϬϬ ϴϵϱϲϲϬ ϬϮϮϮϬϬ dWtŽƌůĚdŽƵƌ WůĂLJĞƌŶĂŵĞďŝƌƚŚĂŐĞŚŝŐŚƚǁĞŝŐƚŚĐŽƵŶƚƌLJ ϯϬ ϵϮϬϯ ϯϬϬϬ ϭϱϮϴϰϱϳ ϬϭϱϳϬϬ E&> WůĂLJĞƌŶĂŵĞďŝƌƚŚŚŝŐŚƚǁĞŝŐƚŚĂŐĞĐŽůůĞŐĞ ϯϬ ϴϰϭϲ ϯϬϬϬ ϭϮϲϱϰϳϭ ϬϮϯϱϬϬ ^ŽĐĐĞƌĂƐĞ WůĂLJĞƌŶĂŵĞďŝƌƚŚĂŐĞŚŝŐŚƚǁĞŝŐƚŚĐŽƵŶƚƌLJĐůƵď ϯϬ ϭϱϲϯϳ ϯϬϬϬ ϳϯϳϭϮϳϴ ϬϯϭϵϬϬ ϯϬϬϬ ϳϵϴϵ ϯϬϬϬ ϮϴϮϴϵϳϯ ϬϮϮϴϯϲ :ŽďƐĂƌƐZĞĂůƐƚĂƚĞŽĐƚŽƌƐǀĞŶƚƐ ^ƵŵŵĂƌLJ ^ƵŵŵĂƌLJ ^ƵŵŵĂƌLJ ^ƵŵŵĂƌLJ ^ƵŵŵĂƌLJ ^ƵŵŵĂƌLJ ^ƵŵŵĂƌLJ ^ƵŵŵĂƌLJ &ŝůŵƐŽŽŬƐWůĂLJĞƌƐ Table 4: Description of our datasets (Part 1). 25
we have found that the learning time is 24.93 ±107.13 minutes slower with Alternative A1. Contrarily, the time to execute the rules is, as expected, better, since it is 2.05±12.04 minutes faster than the baseline. However, this difference is not enough when compared to the time spent in the learning process. What makes the learning process slower in Alternative A1 is the evaluation process once the rules are learnt. That is, analysing every single condition in the context of a rule to check if removing it can have a negative impact on their effectiveness. Furthermore, analysing every single rule in a rule set to find out subsumed rules also has a negative impact on effectiveness. Thus, our conclusion is that post-processing the resulting rule sets is not really worth. 3.7. Variation point VP7: branch Heuristic H8: allow recursion. The differences in effectiveness are not very significant. What makes a big difference is the learning time, which is 20.43 ± 115.14 minutes slower in Alternative A1. This had a very negative impact on the computation of the rank and made us select the baseline as the best alternative in this heuristic. The reason why Alternative A1 took longer during the learning phase is because it has to compute if there is an order between any two variables that can be instantiated with nodes, which took very long and the rules did not improve because there was not a single case in which the slot instantiator was included in the body of the rule, so there were not any improvements regarding making rules more simpler and/or general. Heuristic H9: sort conditions. Note that it is Alternative A2 the one that performs the best according to our rank, which was not surprising. The baseline seems to perform a little better than Alternative A2 regarding effectiveness but the differences are negligible. Alternative A0 results in a precision that is 0.01 ±0.13 higher, a recall that is 0.00 ±0.10 higher, and an F1score that is 0.01 ±0.12 higher than the corresponding ones in Alternative A2. However, both alternatives A1 and A2 are faster than the baseline when learning rules, namely: Alternative A1 is 3.54 ±68.91 minutes faster and Alternative A2 is 5.86 ±79.74 minutes faster. However, regarding the extraction time, Alternative A2 beats both Alternatives A0 and A1 since it is 2.28±12.02 minutes faster. The improvement in both learning and extraction times led us to select Alternative A2 as the best one. It makes sense that sorting the features according to their empirical frequencies results in better timings since the features that have proven to work better at making a difference amongst the positive and the negative examples are prioritised and this helps find the best conditions faster. Heuristic H10: consider input/output modes. Again, the differences in effectiveness are not very significant. Regarding the efficiency, it was expected that Alternative A1 reduced the learning time since there are some conditions that are not generated during the branching procedure; our experimental results confirm this idea because Alternative A1 is 2.08 ±62.98 minutes faster than Alternative A0. Unfortunately, the extraction time worsened because it was 1.74 ±2.57 minutes slower in Alternative A1. Thus, the only improvement on 32
learning time of Alternative A1 regarding A0 is not enough to select it. As a conclusion, we keep Alternative A0 as the best one. 3.8. Variation point VP8: isTooComplex Heuristic H11: check complexity of rules. There are no differences in effectiveness since the rules learnt are exactly the same. It seems that the rules never become very complex since, in most of the cases, just one rule was enough to match the whole set of positive examples in the learning set. Consequently, there are not any differences regarding extraction time. However, computing the bits to encode each condition that is added to a rule and encoding the examples that it matches makes the learning process a bit more inefficient. This is why the learning time in Alternative A1 is 6.85 ±95.31 minutes slower. As a conclusion, we prefer to keep Alternative A0 as the best one. 4. Experimental analysis In this section, we report on the results of our experimental analysis and provide an insight into the difficult cases that we have found. We used the same experimental environment as we used to configure our proposal. We found an implementation for SoftMealy [17] and Wien [21], which are classical proposals, and RoadRunner [9], FiVaTech [19], and Trinity [29], which are recent proposals; we also experimented with an approach that is based on Aleph [31]. We used Iman-Davenport’s test to find out if there are statistically significant differences in the empirical ranks and then Hommel’s test to compare the best ranked proposal to the others. We used Kendall’s Tau test to check if there is a significant correlation between the number of errors in the input documents and the effectiveness of our proposal. The statistical tests were performed at the standard significance level α= 0.05. 4.1. Effectiveness analysis Table 8 reports on the raw effectiveness data that we got from our experimentation. The first two lines also provide a summary of the results in terms of mean value and standard deviation. Table 9 summarises the results of our statistical analysis. Regarding precision, TANGO seems to be the best proposal; furthermore, it is the most stable because its standard deviation is the smallest one. The other proposals can also achieve good results regarding precision, but their deviation with respect to the mean is larger. Note, however, that some other proposals can achieve results that are very good, too, chiefly Aleph. Iman-Davenport’s test returns a p-value that is nearly zero, which is a strong indication that there are differences in rank amongst the proposals that we have compared. Since TANGO ranks the first regarding precision, we now have to compare it to the others using Hommel’s test. It confirms that the differences in rank amongst TANGO and Trinity, SoftMealy, FivaTech, Wien, and RoadRunner, are statistically significant because it returns adjusted p-values that are very small with 33
W Z & ϭ W Z & ϭ W Z & ϭ W Z & ϭ W Z & ϭ W Z & ϭ W Z & ϭ DĞĂŶ ϬϳϬ Ϭϲϭ Ϭϲϯ Ϭϱϵ Ϭϲϴ Ϭϱϴ ϬϱϮ Ϭϲϵ Ϭϱϯ ϬϲϮ ϬϴϮ Ϭϲϴ ϬϴϬ ϬϵϬ Ϭϴϰ Ϭϵϭ ϬϵϬ ϬϵϬ Ϭϵϲ Ϭϵϲ Ϭϵϱ ^ƚĚĞǀŝĂƚŝŽŶ Ϭϭϳ Ϭϯϯ Ϭϯϭ ϬϮϮ Ϭϯϯ ϬϮϳ ϬϮϵ Ϭϯϳ Ϭϯϭ ϬϮϱ Ϭϭϵ ϬϮϰ ϬϭϮ ϬϭϬ ϬϬϵ ϬϭϬ Ϭϭϭ ϬϭϬ ϬϬϴ ϬϬϱ ϬϬϴ /ŶƐŝŐŚƚŝŶƚŽŝǀĞƌƐŝƚLJ Ϭϰϱ Ϭϰϱ Ϭϰϱ Ϭϳϲ Ϭϵϳ Ϭϴϱ ϬϰϮ Ϭϰϴ Ϭϰϱ Ϭϵϴ Ϭϲϳ ϬϴϬ Ϭϲϯ ϭϬϬ Ϭϳϳ Ϭϵϴ ϬϵϮ Ϭϵϱ Ϭϵϳ ϬϵϮ Ϭϵϰ ϰ:ŽďƐ ϬϰϮ Ϭϭϱ ϬϮϮ Ϭϴϲ Ϭϴϱ Ϭϴϱ ϬϭϬ ϭϬϬ Ϭϭϴ Ϭϴϳ ϬϲϬ Ϭϳϭ ϬϴϮ ϬϵϬ Ϭϴϲ ϬϴϮ Ϭϳϳ ϬϴϬ Ϭϵϳ Ϭϳϴ Ϭϴϰ ϲ&ŝŐƵƌĞ:ŽďƐ Ϭϱϯ ϭϬϬ Ϭϲϵ ϬϮϭ ϭϬϬ Ϭϯϱ ϬϮϯ ϭϬϬ Ϭϯϴ Ϭϵϯ ϬϵϮ Ϭϵϯ ϬϳϬ Ϭϵϱ Ϭϴϭ Ϭϴϲ Ϭϴϴ Ϭϴϳ ϬϴϮ Ϭϵϯ Ϭϴϯ ĂƌĞĞƌƵŝůĚĞƌ ϬϳϬ ϬϬϵ Ϭϭϲ Ϭϰϴ ϭϬϬ Ϭϲϱ ϬϬϮ ϬϬϳ ϬϬϯ Ϭϱϵ ϭϬϬ Ϭϳϰ Ϭϴϱ ϬϵϮ Ϭϴϴ ϭϬϬ ϬϵϮ Ϭϵϲ Ϭϵϯ Ϭϴϵ ϬϵϬ :ŽďŽĨDŝŶĞ Ϭϰϲ ϬϬϱ ϬϭϬ Ϭϯϰ ϬϰϮ Ϭϯϴ Ϭϲϭ Ϭϲϲ Ϭϲϯ Ϭϱϯ ϬϱϮ Ϭϱϯ Ϭϲϳ Ϭϵϵ ϬϴϬ Ϭϴϵ Ϭϵϵ Ϭϵϰ Ϭϵϵ Ϭϵϲ Ϭϵϳ ƵƚŽdƌĂĚĞƌ Ϭϳϱ ϭϬϬ Ϭϴϲ Ϭϲϰ ϬϬϬ ϬϬϬ Ͳ Ͳ ͲͲ Ͳ ͲϬϴϭ Ϭϴϭ Ϭϴϭ ϬϵϬ Ϭϵϭ Ϭϵϭ Ϭϵϲ Ϭϵϲ Ϭϵϲ ĂƌDĂdž Ϭϳϴ ϬϴϬ Ϭϳϵ Ϭϳϲ Ϭϳϴ Ϭϳϳ Ϭϳϲ Ϭϵϱ Ϭϴϰ ϬϯϮ ϬϴϮ Ϭϰϲ Ϭϴϯ ϬϴϬ Ϭϴϭ ϬϴϬ Ϭϴϭ Ϭϴϭ ϭϬϬ ϭϬϬ ϭϬϬ ĂƌŽŶĞ Ϭϲϳ ϬϬϮ ϬϬϰ Ϭϳϯ Ϭϳϳ Ϭϳϱ Ϭϱϲ ϭϬϬ ϬϳϮ Ϭϴϯ Ϭϵϵ ϬϵϬ Ϭϵϭ Ϭϵϭ Ϭϵϭ Ϭϴϵ Ϭϴϯ Ϭϴϲ Ϭϵϱ Ϭϵϳ Ϭϵϱ ůĂƐƐŝĐĂƌƐĨŽƌ^ĂůĞ Ϭϴϲ Ϭϴϵ Ϭϴϴ ϬϭϬ ϭϬϬ Ϭϭϵ Ϭϯϲ Ϭϰϲ ϬϰϬ Ͳ Ͳ Ͳ Ϭϲϭ Ϭϴϰ Ϭϳϭ ϬϵϮ Ϭϴϯ Ϭϴϳ Ϭϵϭ Ϭϵϳ ϬϵϮ /ŶƚĞƌŶĞƚƵƚŽŐƵŝĚĞ Ϭϰϲ Ϭϰϯ Ϭϰϰ Ϭϭϳ ϬϬϮ ϬϬϰ ϬϵϬ Ϭϵϵ Ϭϵϰ Ϭϴϱ Ϭϵϯ Ϭϴϵ Ϭϳϲ Ϭϵϵ Ϭϴϲ Ϭϴϯ Ϭϴϴ Ϭϴϱ ϬϵϮ Ϭϵϱ Ϭϵϰ ,ĂĂƌƚ Ϭϳϵ ϬϵϬ Ϭϴϰ Ϭϲϳ Ϭϲϴ Ϭϲϴ Ϭϱϲ Ϭϳϴ Ϭϲϱ Ϭϲϳ Ϭϵϱ Ϭϳϴ Ϭϴϴ Ϭϵϱ Ϭϵϭ ϬϵϬ ϭϬϬ Ϭϵϱ ϭϬϬ Ϭϵϵ ϭϬϬ ,ŽŵĞƐ Ϭϳϳ ϬϳϮ Ϭϳϰ ϬϴϮ Ϭϴϴ Ϭϴϱ Ϭϵϵ Ϭϵϱ Ϭϵϳ Ͳ Ͳ Ͳ Ϭϵϲ Ϭϵϴ Ϭϵϳ Ϭϴϯ Ϭϴϭ ϬϴϮ ϭϬϬ ϭϬϬ ϭϬϬ ZĞŵĂdž Ϭϱϵ Ϭϳϵ Ϭϲϴ ϬϴϬ ϭϬϬ Ϭϴϵ ϬϮϲ ϬϬϱ ϬϬϴ ϬϳϬ Ϭϳϭ Ϭϳϭ Ϭϰϳ Ϭϵϱ Ϭϲϯ Ϭϵϵ Ϭϵϴ Ϭϵϴ Ϭϵϵ Ϭϵϴ Ϭϵϵ dƌƵůŝĂ Ϭϳϴ Ϭϴϱ Ϭϴϭ Ϭϳϲ Ϭϴϳ Ϭϴϭ ϬϮϭ ϬϬϰ ϬϬϲ Ͳ Ͳ Ͳ Ϭϰϲ Ϭϵϵ Ϭϲϯ Ϭϵϯ Ϭϵϯ Ϭϵϯ Ϭϵϴ Ϭϵϱ Ϭϵϲ tĞďD Ϭϳϲ ϬϰϬ ϬϱϮ Ϭϱϵ Ϭϱϳ Ϭϱϴ ϬϮϮ ϬϬϰ ϬϬϳ Ϭϱϰ Ϭϵϱ Ϭϲϵ Ϭϵϲ Ϭϵϰ Ϭϵϱ Ϭϵϯ Ϭϵϰ Ϭϵϯ Ϭϳϵ Ϭϵϯ ϬϴϮ ŵĞDĞĚŝĐĂůƐƐŽĐ Ϭϱϯ Ϭϯϭ Ϭϯϵ Ϭϱϱ Ϭϱϲ Ϭϱϱ Ͳ Ͳ Ͳ Ϭϭϭ Ϭϭϵ Ϭϭϰ Ϭϳϯ Ϭϵϯ ϬϴϮ ϬϴϬ Ϭϳϵ ϬϴϬ Ϭϵϵ Ϭϵϰ Ϭϵϳ ĞŶƚŝƐƚƐ Ϭϱϲ ϬϲϬ Ϭϱϴ Ϭϴϴ Ϭϵϵ Ϭϵϯ Ϭϴϰ ϭϬϬ ϬϵϮ ϬϰϬ Ϭϵϱ Ϭϱϲ Ϭϴϲ Ϭϵϵ ϬϵϮ ϭϬϬ Ϭϴϵ Ϭϵϰ ϭϬϬ ϬϵϮ Ϭϵϱ ƌ^ĐŽƌĞ Ϭϳϯ ϬϴϬ Ϭϳϳ Ϭϳϭ Ϭϳϴ Ϭϳϰ Ϭϲϱ Ϭϵϴ Ϭϳϴ Ϭϲϳ Ϭϵϱ Ϭϳϵ ϬϳϮ Ϭϵϱ ϬϴϮ Ϭϲϭ Ϭϲϰ ϬϲϮ ϬϵϮ Ϭϴϰ Ϭϴϱ ^ƚĞĂĚLJ,ĞĂůƚŚ Ϭϱϲ Ϭϭϵ ϬϮϴ ϬϲϮ Ϭϲϲ Ϭϲϰ Ϭϴϭ Ϭϵϵ Ϭϴϵ Ϭϳϱ ϭϬϬ Ϭϴϲ Ϭϳϵ Ϭϵϰ Ϭϴϲ ϭϬϬ Ϭϴϵ Ϭϵϰ ϭϬϬ ϭϬϬ ϭϬϬ >ŝŶŬĞĚ/Ŷ Ϭϳϴ Ϭϱϯ Ϭϲϯ Ϭϱϲ ϬϮϬ ϬϮϵ Ϭϯϴ Ϭϰϵ Ϭϰϯ Ϭϳϴ Ϭϴϳ Ϭϴϯ Ϭϴϵ Ϭϴϲ Ϭϴϳ ϬϵϮ ϭϬϬ Ϭϵϲ ϭϬϬ Ϭϵϴ Ϭϵϵ ůůŽŶĨĞƌĞŶĐĞƐ Ϭϵϲ Ϭϭϳ ϬϮϴ Ϭϳϴ Ϭϯϱ Ϭϰϴ Ϭϲϭ ϭϬϬ Ϭϳϲ Ϭϳϭ ϬϴϬ Ϭϳϱ Ϭϵϳ Ϭϵϲ Ϭϵϲ Ϭϵϵ Ϭϵϱ Ϭϵϳ Ϭϵϰ Ϭϵϵ Ϭϵϲ DďĞŶĚŝ ϭϬϬ Ϭϱϱ Ϭϳϭ Ϭϲϲ ϬϰϬ ϬϱϬ ϬϲϮ ϬϴϮ Ϭϳϭ Ϭϲϭ Ϭϵϵ Ϭϳϲ Ϭϴϭ Ϭϵϳ Ϭϴϴ Ϭϵϲ Ϭϵϲ Ϭϵϲ ϬϵϬ ϭϬϬ Ϭϵϯ Z>ĞĂƌŶŝŶŐ Ϭϯϰ Ϭϯϯ Ϭϯϯ Ϭϯϱ ϭϬϬ ϬϱϮ Ϭϳϯ ϭϬϬ Ϭϴϱ Ϭϴϲ Ϭϳϰ ϬϴϬ Ϭϳϱ Ϭϵϰ Ϭϴϯ Ϭϵϴ ϭϬϬ Ϭϵϵ Ϭϵϵ ϭϬϬ Ϭϵϵ ůďĂŶŝĂDŽǀŝĞƐ ϭϬϬ Ϭϯϳ Ϭϱϰ ϬϳϮ ϭϬϬ Ϭϴϯ Ϭϰϴ Ϭϳϳ Ϭϱϵ Ϭϳϱ Ϭϳϯ Ϭϳϰ Ϭϴϭ Ϭϳϲ Ϭϳϴ ϬϵϮ Ϭϵϰ Ϭϵϯ ϭϬϬ Ϭϵϳ Ϭϵϴ ůůDŽǀŝĞƐ Ϭϳϴ ϬϮϬ ϬϯϮ ϬϬϮ ϬϬϰ ϬϬϯ ϬϮϯ ϭϬϬ Ϭϯϴ ϬϲϮ Ϭϲϲ Ϭϲϰ ϬϵϮ Ϭϴϭ Ϭϴϲ Ϭϵϭ ϬϴϬ Ϭϴϱ ϬϵϮ Ϭϵϱ ϬϵϮ ŝƐŶĞLJDŽǀŝĞƐ Ϭϵϯ ϬϵϮ ϬϵϮ ϬϲϬ ϭϬϬ Ϭϳϱ Ϭϰϭ ϭϬϬ Ϭϱϴ Ϭϲϴ Ϭϱϴ ϬϲϮ Ϭϳϴ Ϭϳϲ Ϭϳϳ Ϭϵϳ Ϭϵϲ Ϭϵϲ Ϭϳϵ Ϭϵϵ Ϭϴϰ /D Ϭϲϵ Ϭϳϴ Ϭϳϰ Ϭϭϵ ϬϯϬ ϬϮϯ ϬϮϬ ϭϬϬ Ϭϯϯ Ϭϲϴ Ϭϳϯ ϬϳϬ ϬϴϬ Ϭϴϭ ϬϴϬ Ϭϵϯ Ϭϵϯ Ϭϵϯ ϭϬϬ Ϭϵϵ ϭϬϬ ^ŽƵů&ŝůŵƐ ϬϵϬ ϭϬϬ Ϭϵϱ ϬϳϮ ϭϬϬ Ϭϴϯ Ϭϰϵ Ϭϰϱ Ϭϰϳ Ϭϰϭ Ϭϵϲ Ϭϱϴ Ϭϴϲ Ϭϵϭ Ϭϴϴ Ϭϵϱ ϬϵϮ Ϭϵϰ ϭϬϬ Ϭϵϰ Ϭϵϳ ďĞŽŽŬƐ Ϭϲϯ ϭϬϬ Ϭϳϳ ϬϱϬ ϬϬϵ Ϭϭϱ ϬϲϬ Ϭϱϯ Ϭϱϲ Ϭϳϱ ϭϬϬ Ϭϴϲ ϬϵϬ Ϭϵϲ Ϭϵϯ Ϭϵϰ ϬϵϮ Ϭϵϯ ϭϬϬ Ϭϵϰ Ϭϵϳ ǁĞƐŽŵĞŽŽŬƐ Ϭϴϱ Ϭϯϳ ϬϱϮ Ϭϳϳ ϬϮϬ Ϭϯϭ ϬϳϬ Ϭϰϯ Ϭϱϰ ϬϴϬ Ϭϵϲ Ϭϴϳ Ϭϵϭ Ϭϴϲ Ϭϴϴ Ϭϵϵ Ϭϵϭ Ϭϵϱ Ϭϵϵ ϭϬϬ Ϭϵϵ ĞƚƚĞƌtŽƌůĚŽŽŬƐ Ϭϳϴ Ϭϵϲ Ϭϴϲ Ϭϯϳ Ϭϯϰ Ϭϯϲ Ͳ Ͳ Ͳ Ϭϵϭ Ϭϵϯ ϬϵϮ Ϭϳϭ ϬϳϬ ϬϳϬ Ϭϵϱ Ϭϵϱ Ϭϵϱ ϭϬϬ ϭϬϬ ϭϬϬ DĂŶLJŽŽŬƐ ϬϳϬ ϭϬϬ Ϭϴϯ ϬϬϭ ϬϮϮ ϬϬϮ Ϭϴϴ ϭϬϬ Ϭϵϰ Ϭϱϰ ϭϬϬ ϬϳϬ Ϭϳϳ ϬϵϬ Ϭϴϯ Ϭϵϵ Ϭϵϵ Ϭϵϵ Ϭϵϳ Ϭϵϴ Ϭϵϳ tĂƚĞƌƐƚŽŶĞƐ ϭϬϬ ϬϵϮ Ϭϵϲ Ϭϲϴ Ϭϲϳ Ϭϲϴ Ϭϳϭ Ϭϳϳ Ϭϳϰ Ϭϳϯ Ϭϴϲ Ϭϳϵ Ϭϴϳ Ϭϴϵ Ϭϴϴ Ϭϵϲ ϭϬϬ Ϭϵϴ ϭϬϬ ϭϬϬ ϭϬϬ WůĂLJĞƌWƌŽĨŝůĞƐ Ϭϲϲ ϬϬϲ Ϭϭϭ ϬϵϬ Ϭϵϵ Ϭϵϰ Ͳ Ͳ ͲϬϬϴ Ϭϵϯ Ϭϭϰ Ϭϴϭ ϭϬϬ Ϭϴϵ Ϭϵϳ Ϭϵϱ Ϭϵϲ Ϭϵϲ Ϭϵϰ Ϭϵϱ h& Ϭϳϱ ϭϬϬ Ϭϴϲ Ϭϴϯ Ϭϵϰ Ϭϴϴ Ϭϴϲ Ϭϵϭ Ϭϴϴ Ͳ Ͳ Ͳ Ϭϵϳ ϬϵϮ Ϭϵϰ ϭϬϬ ϭϬϬ ϭϬϬ ϭϬϬ ϭϬϬ ϭϬϬ dWtŽƌůĚdŽƵƌ Ϭϳϴ ϭϬϬ Ϭϴϴ Ϭϰϴ Ϭϲϳ Ϭϱϲ ϬϳϮ Ϭϴϵ ϬϴϬ Ϭϵϭ ϭϬϬ Ϭϵϱ Ϭϳϵ ϬϵϬ Ϭϴϰ Ϭϵϯ Ϭϵϳ Ϭϵϱ Ϭϵϴ Ϭϵϳ Ϭϵϴ E&> Ϭϱϲ ϭϬϬ Ϭϳϭ ϬϲϮ ϭϬϬ Ϭϳϳ Ϭϴϯ ϬϵϮ Ϭϴϳ ϬϰϬ Ϭϳϴ Ϭϱϯ ϬϳϮ ϭϬϬ Ϭϴϰ Ϭϳϲ Ϭϲϱ ϬϳϬ ϭϬϬ ϭϬϬ ϭϬϬ ^ŽĐĐĞƌĂƐĞ Ϭϳϰ Ϭϴϳ ϬϴϬ Ϭϲϰ ϭϬϬ Ϭϳϴ Ϭϲϲ Ϭϵϱ Ϭϳϳ Ͳ Ͳ Ͳ Ϭϵϲ Ϭϵϳ Ϭϵϳ Ϭϴϵ ϬϵϬ Ϭϴϵ Ϭϵϴ ϭϬϬ Ϭϵϵ ŵĂnjŽŶĂƌƐ Ϭϳϲ Ϭϵϭ Ϭϴϯ ϬϳϮ Ϭϵϱ ϬϴϮ ϭϬϬ ϬϭϬ Ϭϭϴ Ϭϯϳ Ϭϲϯ Ϭϰϳ Ϭϲϯ Ϭϲϱ Ϭϲϰ Ϭϵϳ ϭϬϬ Ϭϵϵ ϭϬϬ ϭϬϬ ϭϬϬ h&WůĂLJĞƌƐ ϬϴϬ Ϭϴϳ Ϭϴϯ Ϭϳϯ Ϭϰϴ Ϭϱϴ Ϭϴϭ Ϭϵϲ Ϭϴϴ Ϭϲϱ ϭϬϬ Ϭϳϵ Ϭϳϰ Ϭϴϯ Ϭϳϴ ϭϬϬ Ϭϵϵ Ϭϵϵ ϬϱϬ ϭϬϬ ϬϲϬ ŵĂnjŽŶWŽƉƌƚŝƐƚƐ Ϭϴϴ Ϭϲϴ Ϭϳϳ Ϭϳϰ ϭϬϬ Ϭϴϱ ϬϮϯ ϬϬϳ ϬϭϬ Ϭϵϰ ϭϬϬ Ϭϵϳ Ϭϴϲ ϭϬϬ ϬϵϮ Ͳ Ͳ Ͳ ϭϬϬ ϭϬϬ ϭϬϬ h&dĞĂŵƐ ϬϴϬ Ϭϴϰ ϬϴϮ Ϭϯϴ Ϭϳϱ Ϭϱϭ Ϭϴϲ ϭϬϬ Ϭϵϯ Ϭϴϳ Ϭϵϭ Ϭϴϵ Ϭϵϭ ϬϵϮ Ϭϵϭ Ϭϱϰ ϬϱϬ ϬϱϮ ϭϬϬ ϭϬϬ ϭϬϬ ƵƐKƉĞŶWůĂLJĞƌƐ ϬϰϬ ϬϮϮ ϬϮϵ Ϭϰϳ ϬϮϱ Ϭϯϯ Ϭϲϭ ϭϬϬ Ϭϳϲ ϬϬϰ Ϭϳϳ ϬϬϴ ϬϳϬ Ϭϵϰ Ϭϴϭ ϭϬϬ Ϭϵϯ Ϭϵϲ ϭϬϬ Ϭϵϲ Ϭϵϴ ͲĂLJŝĚƐ Ϭϲϯ ϬϬϳ Ϭϭϯ Ϭϲϱ ϬϬϵ Ϭϭϱ ϬϳϬ Ϭϳϵ Ϭϳϰ Ϭϲϴ Ϭϵϵ Ϭϴϭ ϬϳϬ Ϭϵϲ Ϭϴϭ Ϭϲϰ Ϭϲϲ Ϭϲϱ Ϭϴϯ ϬϳϮ ϬϳϬ DĂũŽƌ>ĞĂŐƵĞĂƐĞďĂůů Ϭϴϳ Ϭϯϳ ϬϱϮ Ϭϰϳ ϬϮϴ Ϭϯϱ Ϭϭϵ ϭϬϬ ϬϯϮ Ϭϳϯ ϭϬϬ Ϭϴϰ Ϭϳϱ Ϭϰϴ Ϭϱϴ ϭϬϬ Ϭϵϴ Ϭϵϵ Ϭϵϴ ϭϬϬ Ϭϵϵ EĞƚĨůŝdž&ŝůŵƐ Ϭϲϱ Ϭϳϴ Ϭϳϭ Ϭϳϵ Ϭϵϳ Ϭϴϳ Ϭϱϰ Ϭϳϰ Ϭϲϯ Ϭϳϳ Ϭϳϯ Ϭϳϰ Ϭϳϵ ϭϬϬ Ϭϴϵ Ϭϵϵ Ϭϵϯ Ϭϵϲ ϭϬϬ Ϭϵϱ Ϭϵϳ ZWD&ŝŶĚWĂĐŬĂŐĞƐ Ϭϳϭ ϬϬϰ ϬϬϴ Ϭϴϰ Ϭϵϰ Ϭϴϴ ϬϬϭ ϬϬϳ ϬϬϮ ϬϬϮ Ϭϲϯ ϬϬϰ Ϭϳϱ ϭϬϬ Ϭϴϲ ϭϬϬ Ϭϵϯ Ϭϵϲ ϭϬϬ Ϭϵϵ ϭϬϬ ŝŐŬ Ϭϳϵ Ϭϳϱ Ϭϳϳ Ϭϱϴ Ϭϵϭ ϬϳϬ ϬϮϵ ϬϬϯ ϬϬϱ Ͳ Ͳ Ͳ Ϭϴϳ ϬϵϮ Ϭϴϵ ϬϴϬ ϬϴϬ ϬϴϬ ϭϬϬ ϭϬϬ ϭϬϬ /& ϬϮϴ Ϭϰϭ Ϭϯϰ Ϭϳϰ ϭϬϬ Ϭϴϱ Ϭϴϳ ϬϬϴ Ϭϭϱ ϬϮϱ Ϭϲϳ Ϭϯϳ ϬϲϬ ϭϬϬ Ϭϳϱ ϬϵϮ Ϭϴϳ ϬϵϬ Ϭϵϰ Ϭϵϵ Ϭϵϲ KŬƌĂ Ϭϲϲ ϭϬϬ ϬϴϬ Ϭϯϲ Ϭϲϯ Ϭϰϲ ϬϬϭ ϬϬϯ ϬϬϮ Ϭϯϭ Ϭϯϯ ϬϯϮ Ϭϵϴ Ϭϳϴ Ϭϴϳ Ϭϵϲ Ϭϵϱ Ϭϵϱ ϭϬϬ Ϭϵϵ ϭϬϬ >tĞĞŬůLJ Ϭϰϰ Ϭϱϲ ϭϯϬ Ϭϲϯ Ϭϳϵ ϬϳϬ ϬϬϲ ϭϬϬ Ϭϭϭ ϬϲϮ Ϭϰϳ Ϭϱϰ Ϭϳϳ Ϭϴϴ ϬϴϮ Ϭϵϵ Ϭϴϯ Ϭϵϭ Ϭϵϵ Ϭϵϳ Ϭϵϴ ĂŐĂƚ ϬϲϬ ϬϲϮ ϭϱϬ Ϭϱϯ ϭϬϬ ϬϳϬ ϬϮϰ ϭϬϬ Ϭϯϵ Ϭϴϳ Ϭϵϰ ϬϵϬ Ϭϵϱ Ϭϴϱ ϬϵϬ ϭϬϬ Ϭϵϳ Ϭϵϴ ϭϬϬ ϭϬϬ ϭϬϬ ĂƚĂƐĞƚ dƌŝŶŝƚLJ dE'K ^ŽĨƚDĞĂůLJ tŝĞŶ ZŽĂĚZƵŶŶĞƌ &ŝǀĂdĞĐŚ ůĞƉŚ Table 8: Effectiveness results. 34
/ŵĂŶͲĂǀĞŶƉŽƌƚΖƐ dĞĐŚŶŝƋƵĞ ZĂŶŬ ƉͲǀĂůƵĞ dĞĐŚŶŝƋƵĞ ZĂŶŬ dE'K ϭϲϬ ůĞƉŚ dƌŝŶŝƚLJ ^ŽĨƚDĞĂůLJ &ŝsĂdĞĐŚ tŝĞŶ ZŽĂĚZƵŶŶĞƌ dE'K ϭ ůĞƉŚ Ϯϯϯ ůĞƉŚ ϭ dƌŝŶŝƚLJ ϯϱϰ dƌŝŶŝƚLJ Ϯ ^ŽĨƚDĞĂůLJ ϰϱϯ ^ŽĨƚDĞĂůLJ Ϯ &ŝsĂdĞĐŚ ϱϬϳ &ŝsĂdĞĐŚ Ϯ tŝĞŶ ϱϯϴ tŝĞŶ Ϯ ZŽĂĚZƵŶŶĞƌ ϱϱϳ ZŽĂĚZƵŶŶĞƌ Ϯ /ŵĂŶͲĂǀĞŶƉŽƌƚΖƐ dĞĐŚŶŝƋƵĞ ZĂŶŬ ƉͲǀĂůƵĞ dĞĐŚŶŝƋƵĞ ZĂŶŬ dE'K ϮϱϮ dƌŝŶŝƚLJ ůĞƉŚ ZŽĂĚZƵŶŶĞƌ &ŝsĂdĞĐŚ tŝĞŶ ^ŽĨƚDĞĂůLJ dE'K ϭ dƌŝŶŝƚLJ ϯϰϯ dƌŝŶŝƚLJ Ϯ ůĞƉŚ ϯϵϭ ůĞƉŚ Ϯ ZŽĂĚZƵŶŶĞƌ ϰϮϭ ZŽĂĚZƵŶŶĞƌ Ϯ &ŝsĂdĞĐŚ ϰϯϭ &ŝsĂdĞĐŚ Ϯ tŝĞŶ ϰϱϭ tŝĞŶ Ϯ ^ŽĨƚDĞĂůLJ ϱϭϭ ^ŽĨƚDĞĂůLJ Ϯ /ŵĂŶͲĂǀĞŶƉŽƌƚΖƐ dĞĐŚŶŝƋƵĞ ZĂŶŬ ƉͲǀĂůƵĞ dĞĐŚŶŝƋƵĞ ZĂŶŬ dE'K ϭϱϯ ůĞƉŚ dƌŝŶŝƚLJ &ŝsĂdĞĐŚ ^ŽĨƚDĞĂůLJ tŝĞŶ ZŽĂĚZƵŶŶĞƌ dE'K ϭ ůĞƉŚ Ϯϱϲ ůĞƉŚ Ϯ dƌŝŶŝƚLJ ϯϰϱ dƌŝŶŝƚLJ Ϯ &ŝsĂdĞĐŚ ϰϴϭ ^ŽĨƚDĞĂůLJ Ϯ ^ŽĨƚDĞĂůLJ ϰϵϲ &ŝsĂdĞĐŚ Ϯ tŝĞŶ ϱϯϰ tŝĞŶ Ϯ ZŽĂĚZƵŶŶĞƌ ϱϯϲ ZŽĂĚZƵŶŶĞƌ Ϯ ϰϮϭͲϮϬ ZĞĐĂůů ^ĂŵƉůĞƌĂŶŬŝŶŐ ^ƚĂƚŝƐƚŝĐĂůƌĂŶŬŝŶŐ ϲϭϲͲϬϵ ,ŽŵŵĞůΖƐ ĂĚũƵƐƚĞĚƉͲǀĂůƵĞƐ dE'K ϲϰϮͲϬϵ ϯϭϭͲϬϮ ϮϬϬͲϬϯ ϭϵϰͲϬϰ ϵϳϭͲϬϱ ϭϯϭͲϬϱ WƌĞĐŝƐŝŽŶ & ϭ ƐĐŽƌĞ ^ĂŵƉůĞƌĂŶŬŝŶŐ ,ŽŵŵĞůΖƐ ^ƚĂƚŝƐƚŝĐĂůƌĂŶŬŝŶŐ ^ĂŵƉůĞƌĂŶŬŝŶŐ ,ŽŵŵĞůΖƐ ^ƚĂƚŝƐƚŝĐĂůƌĂŶŬŝŶŐ ĂĚũƵƐƚĞĚƉͲǀĂůƵĞƐ ϱϳϲͲϰϲ dE'K ϴϰϱͲϬϮ ϵϭϬͲϬϲ ϭϯϯͲϭϭ ϭϬϮͲϭϱ ϮϯϰͲϭϴ ĂĚũƵƐƚĞĚƉͲǀĂůƵĞƐ ϳϯϯͲϰϮ dE'K ϭϱϮͲϬϮ ϭϭϯͲϬϱ ϯϬϬͲϭϰ ϮϭϱͲϭϱ ϭϮϲͲϭϴ ϴϯϱͲϭϵ Table 9: Statistical ranks regarding effectiveness. 35
regard to the standard significance level. In the case of Aleph, the statistical test did not find any significant differences since the corresponding adjusted p-value is greater than the standard significance level. In other words, our experimental data provides enough evidence to reject the hypothesis that TANGO behaves similarly to Trinity, SoftMealy, FivaTech, Wien, and RoadRunner, regarding precision; that is, it supports the idea that TANGO can learn rules that are more precise than the other proposals, but we cannot reject the hypothesis that TANGO behaves similarly to Aleph. Regarding recall, TANGO seems to be the best proposal; furthermore, it is the most stable because its deviation is the smallest one. Note, however, that the other proposals can achieve results that are very good, too, chiefly Trinity and Aleph. Iman-Davenport’s test returns a p-value that is very close to zero, which is a strong indication that there are differences in rank amongst the proposals that we have compared. Hommel’s test confirms that the differences in rank between TANGO and the other proposals are statistically significant at the standard significance level. As a conclusion, the experimental data provides enough evidence to reject the hypothesis that TANGO behaves similarly to the other proposals regarding recall; that is, it supports the idea that TANGO ranks at the first position. Regarding the F1score, TANGO is the best one and the most stable. Trinity and Aleph are also very stable, but their results regarding F1are a bit poorer. Iman-Davenport’s test returns a p-value that is nearly zero, which strongly supports the hypothesis that there are statistically significant differences in rank. Hommel’s test returns adjusted p-values that are clearly smaller than the significance level in every case, which supports the hypothesis that the differences in rank between TANGO and every other proposal are statistically significant, too; that is, we can safely assume that it ranks the first. Since TANGO works on the tree representation of the input documents, we need to parse them and correct their HTML errors. It was then necessary to perform a statistical analysis to find out if our experiments provide enough evidence to conclude that the presence of errors in the input documents has an impact on the effectiveness of our proposal. Kendall’s Tau test returned τ=−0.10 with p-value 0.59. Since τis very close to zero and that the p-value is clearly greater than the standard significance level, then the experimental data does not provide enough evidence to reject the hypothesis that the correlation is zero. In other words, our experiments do not provide any evidences that the effectiveness of our proposal may be biased by the errors in the HTML code of the input documents. Our conclusions are that TANGO outperforms the other proposals regarding effectiveness and that it is the proposal whose results are more stable. The statistical tests that we have performed have found enough evidence in our experimental data to support the hypothesis that the differences in the empirical rank amongst TANGO and the other proposals are significant at the standard significance level, except for the case of precision, in which case the experimental data does not provide enough evidence to conclude that TANGO and Aleph perform differently. Note, too, that proposals like RoadRunner, FiVaTech, and 36
Aleph cannot deal with all of our datasets; such situations are indicated with a dash in Table 8. The reason is that they took more than 1 CPU day to learn a rule or that they raised an exception; in both cases, we could not compute any effectiveness measures for the corresponding datasets. 4.2. Efficiency analysis Table 10 reports on the raw efficiency data that we got from our experimentation. The first two lines also provide a summary of the results in terms of mean value and standard deviation. Table 11 summarises the results of our statistical test. Regarding learning times, it seems that Trinity is the proposal that takes less time to learn a rule set. In most cases, it does not take more than a tenth of a second. It is followed by RoadRunner, SoftMealy, and Wien, whose learning times are very similar; then come Aleph and FivaTech; finally, TANGO ranks at the last position. Iman-Davenport’s test returns a p-value that is very close to zero, which clearly supports the hypothesis that there are differences in rank amongst these proposals. Hommel’s test also returns adjusted p-values that are very small with respect to the significance level, which also reveals that the experimental data provides enough evidence to support the hypothesis that Trinity performs better than the other proposals. Regarding extraction times, Wien, SoftMealy, Aleph, and TANGO seem to be the proposals that have the worst performance; RoadRunner and Trinity seem to be very similar; finally, FivaTech seems to be in the middle and its extraction time is still competitive. The timings regarding TANGO are the worst, since applying the rules learnt takes roughly 221.68 seconds in average; neither is its standard deviation small, which means that the results are not as stable as we wished. Iman-Davenport’s test returns a p-value that is nearly zero, which clearly indicates that there are statistically significant differences in the empirical rank. Hommel’s test returns adjusted p-values that are not smaller than the standard significance level regarding the comparisons of Trinity, RoadRunner, and FivaTech. Therefore, we cannot reject the hypothesis that they behave statistically similarly regarding extraction times, that is, we have to assume that they all rank at the first position. The test, however, finds enough evidence to reject the hypothesis that the previous proposals and the others behave similarly regarding the extraction time. Note that we report on the efficiency figures regarding a research prototype of TANGO. It was implemented in Java and relies on a free Prolog engine to implement rules; we think that an ad-hoc implementation would be more efficient because it would avoid wasting resources at exchanging data with the Prolog engine and going through its compilation and unification processes. Recall that we focus on web information extraction problems in the context of Enterprise Systems Integration, where the challenge is to learn rules with very high precision and recall, and our experimentation confirms that we have succeeded regarding this issue. Thus, we think that the penalty to learn more effective rules is not a serious drawback. 37
>d d >d d >d d >d d >d d >d d >d d DĞĂŶ ϱϬϬ ϯϱϱϭ ϱϮϴ ϴϱϴ ϱϮϰ Ϭϯϲ ϲϰϮϱ Ϭϰϰ ϬϭϬ Ϭϯϰ Ϯϳϲϭ ϱϯϬϲ ϵϳϴϭϵ ϮϮϭϲϴ ^ƚĚĞǀŝĂƚŝŽŶ ϰϯϯ ϯϴϯϱ ϯϴϴ ϵϳϴ ϲϮϬ Ϭϰϴ ϭϬϰϭϳ Ϭϱϴ Ϭϭϰ Ϭϰϳ ϯϲϳϯ ϰϳϯϰ Ϯϯϳϳϲϭ Ϯϴϵϳϳ /ŶƐŝŐŚƚŝŶƚŽŝǀĞƌƐŝƚLJ ϰϵϬ ϭϭϲϳ ϯϮϬ ϰϵϵ Ϯϰϭ ϭϬϬ ϵϯϱ ϬϬϴ ϬϬϱ ϭϬϬ ϭϯϰϬ ϱϬϱϳ ϭϴϱϱϵϮ ϮϮϵϴϬ ϰ:ŽďƐ ϰϬϳ ϯϲϲϬ ϲϬϵ ϲϱϳ ϭϰϬ ϭϬϬ ϴϯϮ ϬϬϳ ϬϬϰ ϬϬϭ ϭϳϬϴ ϯϳϰϰ ϮϴϵϬϴ ϭϬϰϮϮ ϲ&ŝŐƵƌĞ:ŽďƐ ϳϲϱ ϭϴϱϭ ϳϰϰ ϴϯϮ ϭϯϴϯ ϭϬϬ ϱϯϮϭ ϬϮϰ ϬϬϮ ϬϬϭ ϭϮϮϬ ϳϭϭϳ ϮϯϰϮϴϮ ϮϴϱϮϰ ĂƌĞĞƌƵŝůĚĞƌ ϱϮϬ ϯϱϰϰ ϱϲϮ ϱϯϵ ϱϳϱ ϬϬϭ ϭϯϲϬϯ ϬϮϮ ϬϬϯ ϭϬϬ ϭϲϮϰ ϯϰϭϮ ϮϱϵϮϬ ϭϬϭϭϬ :ŽďŽĨDŝŶĞ ϯϲϯ ϭϱϲϭ Ϯϴϲ ϯϯϮ ϭϰϵ ϬϬϭ ϯϬϯϯ Ϭϭϰ ϬϬϯ ϬϬϭ ϭϱϰϮ ϯϬϮϯ Ϯϰϲϰϴ ϴϯϳϲ ƵƚŽdƌĂĚĞƌ ϲϳϴ ϳϮϯϵ ϲϬϳ ϵϳϯ Ͳ Ͳ Ͳ Ͳ ϬϭϮ ϬϬϮ ϭϴϰϬ ϰϭϴϭ ϴϭϭϲϴ ϮϲϳϬϬ ĂƌDĂdž ϵϳϮ ϮϮϵϭ ϯϱϬ ϱϯϰ ϭϯϮϳ ϬϬϭ ϭϵϮϰ Ϭϭϰ Ϭϭϰ ϬϬϭ ϭϱϱϰ ϯϮϵϭ ϰϮϲϵϲ ϭϳϱϬϮ ĂƌŽŶĞ ϯϰϯ Ϯϴϴϴ ϱϳϲ ϯϯϮ ϮϳϮ ϭϬϬ ϭϵϴϳϵ Ϭϰϭ ϬϬϮ ϭϬϬ ϭϱϮϯ ϯϬϯϱ ϰϱϱϮϮ Ϯϰϭϳϰ ůĂƐƐŝĐĂƌƐĨŽƌ^ĂůĞ ϭϯϳϰ ϳϴϱϱ ϭϭϴϵ ϳϭϵ ϮϴϰϬ ϬϬϭ Ͳ Ͳ Ϭϭϯ ϬϬϭ ϮϮϬϭ ϭϮϵϱϵ ϰϭϭϲϲ ϰϭϳϰϮ /ŶƚĞƌŶĞƚƵƚŽŐƵŝĚĞ ϰϯϯ ϲϴϮϰ ϰϬϭ ϲϮϲ ϰϰϮ ϭϬϬ ϳϭϱϬ ϭϬϬ ϬϬϱ ϭϬϬ ϭϱϳϯ ϯϭϯϴ ϰϳϱϴϬ ϭϳϴϲϴ ,ĂĂƌƚ ϰϬϯ ϲϵϴϬ ϯϮϳ ϰϴϮ ϯϭϮ ϬϬϭ ϵϰϬ ϬϬϲ ϬϬϮ ϭϬϬ ϭϳϯϲ ϰϭϴϮ ϵϴϲϰ ϭϬϯϯϴ ,ŽŵĞƐ ϰϯϲ ϰϱϱϳ ϰϴϬ ϴϭϴ Ϯϰϯ ϬϬϭ Ͳ Ͳ Ϭϭϭ ϬϬϭ ϭϯϳϵ Ϯϯϲϰ ϴϰϳϮ ϵϮϬϰ ZĞŵĂdž ϯϬϵ ϭϳϴϬ ϴϯϬ ϱϭϳ ϳϴϱ ϬϬϭ ϰϳϳϯ ϬϬϳ ϬϮϮ ϬϬϭ ϭϲϰϬ ϯϲϳϳ ϵϰϰϰ ϭϰϲϬϰ dƌƵůŝĂ ϭϭϴϳ ϭϵϲϲϯ ϭϮϵϰ Ϯϱϯϳ ϭϵϵϳ ϭϬϬ Ͳ Ͳ Ϭϰϴ ϭϬϬ ϭϴϵϱ ϭϭϵϱϲ ϰϵϯϯϮϬ ϲϬϵϰϮ tĞďD ϰϱϰ ϮϬϴϱ ϭϬϰϳ ϭϬϭϳ ϭϰϰϵ ϬϬϭ ϳϲϰ ϭϬϬ ϬϬϭ ϬϬϭ ϭϴϮϰ ϰϲϰϮ ϮϰϭϲϮ ϭϱϰϮϲ ŵĞDĞĚŝĐĂůƐƐŽĐ ϰϭϲ ϳϯϬ ϯϲϴ ϳϯϵ Ͳ Ͳ ϭϱϯ ϬϮϬ ϬϬϯ ϭϬϬ ϭϲϬϱ ϯϯϱϲ ϮϬϳϵϬ ϭϬϰϯϰ ĞŶƚŝƐƚƐ ϭϱϲ ϱϲϳ ϭϯϲ ϭϮϴ Ϭϯϵ ϬϬϭ ϰϴϲ ϬϬϱ ϬϬϭ ϭϬϬ ϭϮϳϴ ϵϰϬ ϮϵϴϮ ϯϬϱϰ ƌ^ĐŽƌĞ Ϯϴϭ ϭϳϱϭ ϮϬϳ Ϯϱϭ ϭϬϭ ϭϬϬ ϯϮϮϵ ϭϬϬ ϬϬϭ ϬϬϭ ϭϯϴϵ ϭϳϳϮ ϯϵϬϵϬ ϵϳϮϲ ^ƚĞĂĚLJ,ĞĂůƚŚ ϰϴϱ ϰϬϬϬ ϱϵϱ ϲϳϴ ϳϲϭ ϬϬϮ ϱϳϭ ϬϬϴ ϬϯϬ ϬϬϭ ϯϰϬϱ ϵϳϱϯ ϭϬϭϬϱϴ ϯϭϮϯϬ >ŝŶŬĞĚ/Ŷ ϲϬϲ Ϯϵϭϴ ϭϴϳ ϯϯϰ ϭϲϲ ϬϬϭ ϯϰϱϲ Ϯϯϱ ϬϬϮ ϬϬϭ ϭϲϭϱ ϮϲϯϮ ϭϴϵϳϴ ϴϰϵϲ ůůŽŶĨĞƌĞŶĐĞƐ ϲϯϰ ϰϯϬϭ ϯϲϴ ϯϯϮ ϭϴϴ ϬϬϭ ϭϴϱϰ ϭϬϬ ϬϬϱ ϬϬϭ ϭϴϰϵ ϯϲϱϳ ϮϴϵϯϮ ϭϮϵϲϬ DďĞŶĚŝ ϭϲϰ ϯϵϴ ϮϬϴ ϭϮϴ Ϭϳϱ ϭϬϬ Ϭϵϳ ϬϬϮ ϬϬϬ ϬϬϭ ϭϯϴϮ ϭϵϬϲ ϭϲϱϲϬ ϱϴϲϮ Z>ĞĂƌŶŝŶŐ ϮϮϰ ϰϵϲ ϭϰϰ ϭϯϲ Ϭϯϯ ϬϬϭ ϯϱϭ ϬϬϭ ϬϬϭ ϬϬϭ ϭϮϰϯ ϭϭϯϭ ϭϳϮϲϮ ϯϱϴϴ ůďĂŶŝĂDŽǀŝĞƐ ϮϬϴ ϯϰϱ ϭϯϲ ϭϭϲ Ϭϵϭ ϬϬϭ ϭϴϴ ϬϬϭ ϬϬϭ ϭϬϬ ϭϱϭϵ ϲϳϰϭ ϮϬϯϯϰ ϭϬϲϯϮ ůůDŽǀŝĞƐ ϭϭϱϰ ϯϴϴϳ ϯϮϯ ϰϭϭ ϭϵϬ ϬϬϭ ϲϮϯ ϭϬϬ ϬϮϳ ϬϬϭ ϭϮϱϭϵ ϯϳϮϭ ϳϳϳϳϴ ϰϵϵϭϰ ŝƐŶĞLJDŽǀŝĞƐ ϰϯϱ ϯϭϭϰ ϮϬϬ Ϯϲϳ ϭϵϵ ϬϬϭ ϭϮϭϮϴ ϬϬϱ Ϭϲϳ ϬϬϭ ϳϰϳϭ Ϯϱϵϭ ϯϳϰϳϬ ϭϬϳϰϬ /D ϭϵϴϵ ϲϯϮϱ ϭϵϰϳ ϭϭϰϳ ϵϵϮ ϬϬϭ ϯϮϭϯ ϮϯϮ ϬϮϰ ϭϬϬ ϭϭϭϬϵ ϲϴϰϳ ϮϮϲϯϰϰ ϯϴϯϴϴ ^ŽƵů&ŝůŵƐ ϲϲϴ ϮϲϬϵ ϰϬϯ ϵϯϳ ϭϵϭ ϬϬϭ ϭϬϲϰ ϬϬϯ ϬϬϮ ϬϬϭ Ϯϳϱϭ ϭϮϮϲϱ ϮϰϮϮϲϮ Ϯϰϯϭϴ ďĞŽŽŬƐ ϵϵϱ ϭϴϳϭ ϭϬϳϰ ϭϬϮϳ ϯϮϵ ϬϬϭ ϵϳϴ ϬϬϵ ϬϬϮ ϬϬϭ ϭϱϬϲ ϯϮϭϮ ϮϬϲϰϲ ϭϭϮϲϮ ǁĞƐŽŵĞŽŽŬƐ Ϯϱϯ ϭϭϰϵ ϯϮϱ ϲϮϴ ϭϱϱ ϬϬϭ ϯϲϳ ϬϭϬ ϬϬϮ ϬϬϭ ϭϰϵϮ Ϯϱϴϭ ϭϯϲϮϲ ϭϬϰϴϴ ĞƚƚĞƌtŽƌůĚŽŽŬƐ ϭϵϱϱ Ϯϴϴϯ ϳϵϯ ϭϭϴϵ Ͳ Ͳ ϰϳϱϰ ϬϮϳ ϬϭϬ ϬϬϭ ϭϮϮϭ ϳϯϳϰ ϭϲϴϰϴ ϭϵϯϲϮ DĂŶLJŽŽŬƐ ϳϯϵ ϮϭϬϯ ϮϴϮ ϱϲϮ ϭϯϭ ϬϬϭ ϴϮϳϭ ϬϬϵ Ϭϭϯ ϬϬϭ ϭϬϬϴ ϰϵϳϴ ϱϭϴϭϬ ϭϱϰϵϴ tĂƚĞƌƐƚŽŶĞƐ ϱϬϬ ϱϯϰϲ ϱϱϴ ϲϬϯ ϯϰϳ ϭϬϬ Ϯϵϯϳ ϭϯϴ ϬϬϰ ϬϬϭ ϭϭϰϱ ϰϵϰϵ ϰϭϵϲϰ ϭϰϯϳϲ WůĂLJĞƌWƌŽĨŝůĞƐ ϮϵϮ ϭϳϰϯ ϱϴϯ ϯϰϯ Ͳ Ͳ ϴϬϲ ϭϬϬ ϬϬϲ Ϭϭϲ ϭϵϵϬ ϭϬϯϴϭ ϱϭϱϳϲ ϰϯϵϯϮ h& ϰϬϬ ϮϯϬϴ Ϯϲϵ ϯϵϳ ϲϴϵ ϬϬϮ Ͳ Ͳ ϬϬϯ ϬϬϭ ϭϴϮϬ ϯϭϵϯ ϱϳϯϬ ϭϬϮϳϮ dWtŽƌůĚdŽƵƌ ϵϯϭ ϭϮϱϴϲ ϭϭϴϭ ϭϮϳϲ ϴϴϳ ϬϬϯ ϱϬϬϭ Ϭϱϴ Ϭϯϴ ϬϬϮ ϭϵϲϬ ϱϲϲϬ ϰϬϯϲϴ ϮϳϲϬϬ E&> ϲϯϰ Ϯϳϲϲ ϵϲϵ ϲϲϰ ϭϵϴϴ ϬϬϮ ϳϮϰϵ ϭϬϬ ϬϬϴ ϬϬϭ ϭϲϱϱ ϰϯϱϬ ϭϮϮϴϴ ϭϵϳϬϰ ^ŽĐĐĞƌĂƐĞ ϴϬϳ ϯϯϯϬ ϭϮϵϱ ϳϱϲ ϭϬϬϲ ϭϬϬ Ͳ Ͳ Ϭϯϰ ϭϬϬ ϱϭϯϲ Ϯϳϳϲϳ ϭϲϰϰϰϰϰ ϭϵϲϮϱϰ ŵĂnjŽŶĂƌƐ Ϭϲϴ ϳϬϮ ϴϰϭ ϱϲϲ ϬϴϬ ϭϬϬ Ϯϱϱ ϭϬϬ ϬϬϭ ϭϬϬ ϭϯϯϵ ϭϭϬϬ ϮϮϲϮ ϮϱϵϮ h&WůĂLJĞƌƐ ϭϰϯ ϭϭϲϰ ϯϳϵ Ϯϱϴ Ϭϰϭ ϬϬϭ ϭϮϱϴ ϬϬϯ ϬϬϭ ϬϬϭ ϭϲϵϯ ϭϴϲϴ ϱϯϳϯϲ ϮϵϮϮ ŵĂnjŽŶWŽƉƌƚŝƐƚƐ ϯϲϭ ϭϲϮϬ ϳϵϲ ϭϬϮϮ ϭϬϯ ϭϬϬ ϭϬϳϬϰ ϬϬϴ ϬϬϭ ϬϬϭ Ͳ Ͳ ϮϬϮϲϴ ϭϱϯϵϲ h&dĞĂŵƐ Ϭϰϵ ϯϯϯ ϬϴϬ ϮϮϴ Ϭϰϳ ϬϬϭ Ϭϱϰ ϬϬϭ ϬϬϮ ϭϬϬ ϭϭϳϰ ϭϱϮϯ ϭϳϬϳϲ ϴϵϲϰ ƵƐKƉĞŶWůĂLJĞƌƐ Ϭϴϭ ϭϱϮϳ ϱϮϲ ϭϲϵϲ ϯϭϮ ϭϬϬ ϴϬϳϬ Ϭϭϴ Ϭϭϰ ϭϬϬ Ϯϭϲϳ ϭϰϳϱϮ ϮϲϭϯϯϬ ϳϴϮϳϬ ͲĂLJŝĚƐ ϭϭϰ ϭϭϭϭ ϱϱϵ ϭϯϲϱ Ϯϭϭ ϬϬϭ ϯϵϳϵϴ Ϭϯϰ ϬϮϱ ϬϬϲ ϮϮϲϬ ϭϭϵϵϲ ϱϵϬϰϲ ϯϯϲϴϰ DĂũŽƌ>ĞĂŐƵĞĂƐĞďĂůů ϭϯϯ ϭϯϲϳ ϰϯϵ ϰϮϴ ϭϳϱ ϬϬϭ ϭϴϰϰϳ ϭϬϬ ϬϬϮ ϬϬϭ ϮϭϮϴ ϭϯϳϵ ϭϭϴϴϳϴ ϲϮϮϮ EĞƚĨůŝdž&ŝůŵƐ ϮϮϲ Ϯϯϴϴ ϰϴϱ ϯϭϱϱ ϰϳϯ ϬϬϭ ϯϵϵϬϭ Ϭϱϯ ϬϬϴ ϬϬϭ ϭϳϲϬ ϭϬϱϮϲ ϵϰϭϰϲ ϯϰϴϭϴ ZWD&ŝŶĚWĂĐŬĂŐĞƐ Ϭϴϯ ϭϴϮϯ ϭϯϵ ϭϬϰϮ Ϭϳϱ ϭϬϬ Ϯϴϱϵ ϬϬϲ ϬϬϮ ϭϬϬ ϭϰϵϯ ϲϴϭϲ ϮϭϲϲϬ ϭϴϯϳϴ ŝŐŬ ϭϲϭ ϭϭϰϴϱ ϭϳϴ ϲϮϮϵ ϭϰϮϳ ϭϬϬ Ͳ Ͳ ϬϬϲ ϭϬϬ ϭϳϴϭ ϰϴϴϴ ϯϳϮϴϰ ϭϲϴϯϲ /& ϭϳϳ ϵϮϯ ϬϵϬ ϭϲϳ Ϭϰϰ ϬϬϭ ϳϬϬ ϬϬϰ ϬϬϳ ϬϬϭ ϲϴϮϭ ϭϳϭϱ ϮϴϱϱϮϮ ϭϮϯϭϴ KŬƌĂ Ϭϳϴ ϭϱϬϬϭ ϭϭϯ Ϯϰϰϴ ϭϬϯϵ ϭϬϬ ϰϮϱϯϲ ϬϮϲ ϬϬϲ ϬϬϭ ϮϮϴϰϭ Ϯϴϳϲ ϱϰϱϮϴ ϴϭϭϮ >tĞĞŬůLJ ϭϯϬ Ϯϯϰϱ Ϭϱϳ ϭϴϵ Ϭϰϴ ϬϬϭ Ϯϲϵ ϬϬϯ ϬϬϭ ϬϬϭ ϭϯϮϳ ϭϲϲϬ ϱϰϯϲ Ϯϲϯϰ ĂŐĂƚ ϭϱϬ ϭϰϭϭ ϱϴϯ ϭϯϳϱ ϯϴϱ ϭϬϬ ϳϯϱϭ ϬϬϰ ϬϬϳ ϭϬϬ ϭϯϱϰ ϭϵϲϭ ϯϱϮϴ ϰϱϵϬ ĂƚĂƐĞƚ dƌŝŶŝƚLJ dE'K ^ŽĨƚDĞĂůLJ tŝĞŶ ZŽĂĚZƵŶŶĞƌ &ŝǀĂdĞĐŚ ůĞƉŚ Table 10: Efficiency results. 38
/ŵĂŶͲĂǀĞŶƉŽƌƚΖƐ dĞĐŚŶŝƋƵĞ ZĂŶŬ ƉͲǀĂůƵĞ dĞĐŚŶŝƋƵĞ ZĂŶŬ dƌŝŶŝƚLJ ϭϬϬ ZŽĂĚZƵŶŶĞƌ ^ŽĨƚDĞĂůLJ tŝĞŶ ůĞƉŚ &ŝǀĂdĞĐŚ dE'K dƌŝŶŝƚLJ ϭ ZŽĂĚZƵŶŶĞƌ ϯϬϬ ZŽĂĚZƵŶŶĞƌ Ϯ ^ŽĨƚDĞĂůLJ ϯϭϮ ^ŽĨƚDĞĂůLJ Ϯ tŝĞŶ ϯϯϳ tŝĞŶ Ϯ ůĞƉŚ ϱϮϳ ůĞƉŚ Ϯ &ŝǀĂdĞĐŚ ϱϯϳ &ŝǀĂdĞĐŚ Ϯ dE'K ϲϴϴ dE'K Ϯ /ŵĂŶͲĂǀĞŶƉŽƌƚΖƐ dĞĐŚŶŝƋƵĞ ZĂŶŬ ƉͲǀĂůƵĞ dĞĐŚŶŝƋƵĞ ZĂŶŬ dƌŝŶŝƚLJ ϭϲϳ ZŽĂĚZƵŶŶĞƌ &ŝsĂdĞĐŚ tŝĞŶ ^ŽĨƚDĞĂůLJ ůĞƉŚ dE'K dƌŝŶŝƚLJ ϭ ZŽĂĚZƵŶŶĞƌ ϭϴϳ ZŽĂĚZƵŶŶĞƌ ϭ &ŝǀĂdĞĐŚ Ϯϰϲ &ŝǀĂdĞĐŚ ϭ tŝĞŶ ϰϭϬ tŝĞŶ Ϯ ^ŽĨƚDĞĂůLJ ϱϮϯ ^ŽĨƚDĞĂůLJ Ϯ ůĞƉŚ ϱϳϭ ůĞƉŚ Ϯ dE'K ϲϵϲ dE'K Ϯ ϭϴϮͲϭϲ ϳϲϵͲϮϭ ϱϱϲͲϯϱ >ĞĂƌŶŝŶŐƚŝŵĞ ϮϳϵͲϮϯ ϯϯϴͲϮϰ ϰϯϳͲϰϯ ^ĂŵƉůĞƌĂŶŬŝŶŐ ^ƚĂƚŝƐƚŝĐĂůƌĂŶŬŝŶŐ,ŽŵŵĞůΖƐ ĂĚũƵƐƚĞĚƉͲǀĂůƵĞƐ ϰϳϴͲϭϭϭ dƌŝŶŝƚLJ ϮϯϱͲϬϲ ϭϭϵͲϬϲ ϳϬϴͲϬϴ ϲϮϱͲϭϱϵ dƌŝŶŝƚLJ ϲϱϬͲϬϭ ϭϮϱͲϬϭ ϯϮϭͲϬϴ džƚƌĂĐƚŝŽŶƚŝŵĞ ^ĂŵƉůĞƌĂŶŬŝŶŐ ,ŽŵŵĞůΖƐ ^ƚĂƚŝƐƚŝĐĂůƌĂŶŬŝŶŐ ĂĚũƵƐƚĞĚƉͲǀĂůƵĞƐ Table 11: Statistical ranks regarding efficiency. 4.3. An insight into the difficult cases Although effectiveness is generally close to 100%, there are some datasets in which our proposal could not reach at least 90% precision and/or recall, which we consider the minimum sensible threshold nowadays. We have gone through these cases and we have found that the reason is not related to the structure of the documents, but to the six documents that were randomly selected for the learning set and/or the alternatives that we selected in our default configuration. Precision is poor regarding datasets 6 Figure Jobs and UEFA Players. The problem was due to the fact that we selected Alternative A2 to implement Heuristic H9, namely: sort conditions according to our empirical order. This alternative led to a tie amongst several feature instantiators when extending a partially constructed rule, which was broken arbitrarily. This resulted in adding a feature instantiator that was more general than it would have been using Alternative A1 or breaking the tie differently; the problem with that feature instantiator is that it matched some negative examples, which obviously had a negative impact on precision. There was also a problem with precision in dataset E-Bay Bids, namely: we could learn rules with precision 1.00 when we explored Alternative A1 in Heuristic H1 to select the best candidate conditions to extend the current rule and to create savepoints; the precision remained 1.00 when we explored Alternative A2 in Heuristic H2 to reduce the number of negative examples. Unfortunately, Alternative A1 in Heuristic H6 removed some slot instantiators that were very specific. As a consequence, the resulting rule was more general than expected, which contributed to increasing recall from 0.72 to 0.86, but reduced precision from 1.00 to 0.87. The problem regarding precision in the Web MD and the Disney Movies datasets was the same as in the E-Bay Bids dataset: recall was improved at the expense of extracting some false positives, which had a negative impact on precision. Recall is poor regarding datasets 4 Jobs,Career Builder, and Dr. Scores; the 39
reason is that the documents in the learning set did not account for enough variability regarding a few slots; as a result, the rules that TANGO learnt were not appropriate for some testing documents, which had a negative impact on recall. In the case of Career Builder, there was an additional problem with the implementation of Heuristic H9: there was a tie when selecting the feature instantiator to extend a rule, and it was broken in favour of a candidate that resulted in a rule that was more specific than it should have been: precision improved from 0.92 to 0.93, but recall worsened from 0.91 to 0.89. In the case of dataset E-Bay Bids, the recall is poor solely due to the six random documents that were selected for the learning set, which did not account for enough variability. We also went through the cases in which our proposal took more than 100 minutes to learn a rule set. Our first intuition was that there might have been some errors in the annotations. Our experience proves that such errors have an important negative impact on efficiency because TANGO typically explores the search space exhaustively before concluding that no rule can match both the correct and the incorrect positive examples and discard both the correct and the incorrect negative examples. After checking our datasets, we did not find any annotation errors. The problem was simpler: for instance, in datasets Auto Trader and Soccer Base, we had to learn rules for roughly ten different slots, whereas in dataset Amazon Pop Artists there are only two slots, which clearly justifies the extra learning time; in datasets like Trulia,IAF,IMDB, and Soul Films the problem was not with the number of slots, but with the many different formats in which they are rendered, which complicated the search for a rule set that takes them all into account. 5. Related work In the introduction, we provided a short survey of the many existing proposals to extract information from web documents. In this section, we focus on the proposals that are most closely-related to ours, namely: SRV [13], Irmak and Suel’s proposal, L-Wrappers [3], and Fernández-Villamor et al.’ proposal. In the following subsections, we compare them to TANGO along the following dimensions: their catalogues of features, their learning procedures, their variation points, and their configuration method; we conclude with some additional miscellaneous comparisons. 5.1. Catalogue of features For a machine learner to work, it has to be fed with a representation of the input documents that maps them onto a number of features from which it is possible to discern the difference between the information to be extracted and the information to be ignored. It does not make sense to believe that a single catalogue of features can deal with every web site or that it shall be appropriate forever. For instance, there are web sites that use intricate formats to make it difficult for software agents to extract information from them; furthermore, ten years ago it was usual to use HTML tables to render information, which 40
is nowadays a deprecated technique. As a conclusion, it is expected that the catalogue of features needs to be replaced or at least adapted from time to time. That it is why it is of uttermost importance that it is open and that the proposal is not bound with the specific features that it provides. SRV relies on a limited catalogue of features that includes some HTML features and a few user-defined ones, but no DOM or CSS features; it also includes relational features to navigate from one token to the next or the previous one, or to the first token of the next column, the previous column, the next row, the previous row, or the header when dealing with tables. SRV features can only be computed on tokens, not on sequences of tokens or nodes. Irmak and Suel’s proposal builds on a catalogue that includes a subset of HTML and DOM features, plus some user-defined features; unfortunately, the authors did not provide many details on them. L-Wrappers relies on a unique attributive feature to map nodes onto their corresponding tags and four relational features: next sibling, parent, first child, and last child. As a result, the conditions in the rules basically attempt to classify nodes by means of their tags and the tags of their neighbours. Fernández-Villamor et al.’ proposal considers a feature that classifies HTML tags into links, images, and other tags, a subset of DOM features regarding bounding boxes, widths, heights, font size, font weight, and font family (which are narrowed to serif, sans-serif, and monospace families), plus a relational feature that allows to fetch the parent of a node. TANGO relies on an extensive catalogue of attributive features that includes every HTML, DOM, and CSS feature defined by the W3C recommendations plus user-defined features; the catalogue of relational features includes features to fetch the parent of a node, its ancestors, its children, and siblings. The features are computed on nodes, which means that some of them work on their tokens. The catalogue has been designed so that it can be easily replaced, since there is nothing in our proposal that is bound with the specific features provided by the catalogue. The catalogues of features that are provided by other proposals are very limited. In the case of SRV, it is open and can be replaced because there is nothing in the proposals that is specific to the features in the catalogue; in the case of Irmak and Suel’s proposal, the catalogue seems to be open, too, but the authors did not provide many details; in the case of L-Wrappers or Fernández- Villamor et al.’ proposal the catalogue cannot be considered open because there are subtle inter-dependencies with the learning procedure. 5.2. Learning procedure Learning procedures can be top-down or bottom-up. In the former case, the search for rules starts with overly-general rules that match every example in the learning set; it then adds conditions that constraint the examples that are matched, and the process continues until a rule that matches at least a positive example and no negative example is found. In the latter case, the search starts with overly-specific rules that match a single positive example; it then generalises or drops some conditions so that the resulting rules match as many positive examples as possible, and the process continues until no further generalisation is possible. In practice, both approaches have proven to work 41
[10] O. Etzioni, A. Fader, J. Christensen, S. Soderland, and Mausam. Open information extraction: the second generation. In IJCAI, pages 3–10, 2011. URL http://ijcai.org/papers11/Papers/IJCAI11-012.pdf. [11] J. I. Fernández-Villamor, C. Ángel Iglesias, and M. Garijo. First-order logic rule induction for information extraction in web resources. International Journal on Artificial Intelligence Tools, 21(6), 2012. doi: 10.1142/S0218213012500327. [12] D. R. Ferreira. Enterprise Systems Integration: a Process-Oriented Approach. Springer, 2013. doi: 10.1007/978-3-642-40796-3. [13] D. Freitag. Machine learning for information extraction in informal domains. Machine Learning, 39(2/3):169–202, 2000. doi: 10.1023/A:1007601113994. [14] Y. He and D. Xin. SEISA: set expansion by iterative similarity aggregation. In WWW, pages 427–436, 2011. doi: 10.1145/1963405.1963467. [15] I. Hickson, R. Berjon, S. Faulkner, T. Leithead, E. D. Navara, E. O’Connor, and S. Pfeiffer. HTML 5: a vocabulary and associated APIs for HTML and XHTML. Technical report, W3C, 2014. URL http://www.w3.org/TR/2014/REC-html5-20141028/. [16] A. W. Hogue and D. R. Karger. Thresher: automating the unwrapping of semantic content from the world wide web. In WWW, pages 86–95, 2005. doi: 10.1145/1060745.1060762. [17] C.-N. Hsu and M.-T. Dung. Generating finite-state transducers for semistructured data extraction from the Web. Inf. Syst., 23(8):521–538, 1998. doi: 10.1016/S0306-4379(98)00027-1. [18] U. Irmak and T. Suel. Interactive wrapper generation with minimal user effort. In WWW, pages 553–563, 2006. doi: 10.1145/1135777.1135859. [19] M. Kayed and C.-H. Chang. FiVaTech: page-level web data extraction from template pages. IEEE Trans. Knowl. Data Eng., 22(2):249–263, 2010. doi: 10.1109/TKDE.2009.82. [20] R. Kosala, H. Blockeel, M. Bruynooghe, and J. V. den Bussche. Information extraction from structured documents using k-testable tree automaton inference. Data Knowl. Eng., 58(2):129–158, 2006. doi: 10.1016/j.datak.2005.05.002. [21] N. Kushmerick, D. S. Weld, and R. B. Doorenbos. Wrapper induction for information extraction. In IJCAI (1), pages 729–737, 1997. URL http://homes.cs.washington.edu/ weld/papers/kushmerick-ijcai97.pdf. 48
[22] T. M. Mitchell, W. W. Cohen, E. R. Hruschka, P. P. Talukdar, J. Betteridge, A. Carlson, B. D. Mishra, M. Gardner, B. Kisiel, J. Krishnamurthy, N. Lao, K. Mazaitis, T. Mohamed, N. Nakashole, E. A. Platanios, A. Ritter, M. Samadi, B. Settles, R. C. Wang, D. T. Wijaya, A. Gupta, X. Chen, A. Saparov, M. Greaves, and J. Welling. Never-ending learning. In AAAI, pages 2302–2310, 2015. doi: 10.3233/978-1-61499-098-7-5. [23] I. Muslea, S. Minton, and C. A. Knoblock. Hierarchical wrapper induction for semistructured information sources. Autonomous Agents and Multi- Agent Systems, 4(1/2):93–114, 2001. doi: 10.1023/A:1010022931168. [24] J. R. Quinlan and M. Cameron-Jones. Induction of logic programs: FOIL and related systems. New Generation Comput., 13(3&4):287–312, 1995. doi: 10.1007/BF03037228. [25] A. M. R. Quintero, P. Jiménez, and R. Corchuelo. A novel approach to web information extraction. In BIS, pages 152–161, 2015. doi: 10.1007/978-3- 319-19027-3_13. [26] J. Rissanen. The Minimum Description Length principle. In Encyclopedia of Machine Learning, pages 666–668. Springer, 2010. doi: 10.1007/978-0- 387-30164-8_540. [27] H. A. Sleiman and R. Corchuelo. A survey on region extractors from web documents. IEEE Trans. Knowl. Data Eng., 25(9):1960–1981, 2013. doi: 10.1109/TKDE.2012.135. [28] H. A. Sleiman and R. Corchuelo. A class of neural-network-based transducers for web information extraction. Neurocomputing, 135:61–68, 2014. doi: 10.1016/j.neucom.2013.05.057. [29] H. A. Sleiman and R. Corchuelo. Trinity: on using trinary trees for unsupervised web data extraction. IEEE Trans. Knowl. Data Eng., 26(6): 1544–1556, 2014. URL 10.1109/TKDE.2013.161. [30] S. Soderland. Learning information extraction rules for semi-structured and free text. Machine Learning, 34(1-3):233–272, 1999. doi: 10.1023/A:1007562322031. [31] A. Srinivasan. The Aleph manual. Technical report, University of Oxford, 2004. URL http://www.cs.ox.ac.uk/activities/machlearn/Aleph. [32] W. Su, J. Wang, and F. H. Lochovsky. ODE: ontology-assisted data extraction. ACM Trans. Database Syst., 34(2), 2009. doi: 10.1145/1538909.1538914. [33] J. Turmo, A. Ageno, and N. Català. Adaptive information extraction. ACM Computing Surveys, 38(2), 2006. doi: 10.1145/1132956.1132957. 49
[34] A. van Kesteren, A. Gregor, A. Russell, and R. Berjon. Document Object Model 4. Technical report, W3C, 2014. URL http://www.w3.org/TR/2014/WD-dom-20140710/. [35] R. C. Wang and W. W. Cohen. Iterative set expansion of named entities using the web. In ICDM, pages 1091–1096, 2008. doi: 10.1109/ICDM.2008.145. [36] Y. Xia, Y. Yang, S. Zhang, and H. Yu. Automatic wrapper generation and maintenance. In PACLIC, pages 90–99, 2011. URL http://www.aclweb.org/anthology/Y11-1010. 50 View publication statsView publication stats