Minimizing the Costs of the Training Data for Learning Web Wrappers

Abstract

Data extraction from the Web represents an important issue. Several approaches have been developed to bring the wrapper generation process at the web scale. Although they rely on di erent techniques and formalisms, they all learn a wrapper given a set of sample pages. Unsupervised approaches require just a set of sample pages, supervised ones also need training data. Unfortunately, the accuracy obtained by unsupervised techniques is not su cient for many applications. On the other hand, obtaining training data is not cheap at the web scale. This paper addresses the issue of minimizing the costs of collecting training data for learning web wrappers. We show that two interleaved problems a ect this issue: the choice of the sample pages, and the expressiveness of the wrapper language. We propose a solution that leverages contributions in the eld of learning theory, and we discuss the promising results of an experimental evaluation of our approach.

1. INTRODUCTION

The huge amount of information available on the web inspired several researches towards the development of tools and techniques to infer web wrappers for extracting data from script-generated HTML pages.

Unsupervised approaches take as input a set of sample pages and analyze regularities and di erences to infer a wrapper based on the underlying HTML template [ 6, 2 ]. They could scale on the number of sources, but the accuracy of the generated wrappers is limited. Supervised approaches can produce accurate wrappers, but their scalability is limited because they need training data, i.e. annotations over the values published in the pages. In early approaches these data were provided by means of a human intervention [ 9 ]. More recently, solutions that rely on data stored in existing repositories have been proposed [ 7 ]. Unfortunately, in many domains suitable training data does not exist at all (consider VLDS’12 August 31, 2012. Istanbul, Turkey.

Copyright c 2012 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. pages that publish subjective values, such as customer ratings, or real time data, such as stock quote prices), or they might be biased over speci c instances (typically the most popular). This prevents the generation of a correct wrapper around the broader set of instances, and thus raises the need of additional training data.

Overall, obtaining training data represents a relevant cost in the wrapper inference process. This paper presents a framework to minimize the the cost of generating a wrapper expressed as the number of membership queries (MQ) needed by a supervised inference system for the training [ 1 ]. Membership queries are the simplest form of queries since they admit only a yes/no answer, e.g. \is [e-mail] a value to extract?". It is worth observing that the simplicity of these queries make them suitable to be answered through crowdsourcing platforms, that make the training costs explicit.

As the following example illustrates, these costs depend on two interrelated features: the representativeness of the sample and the expressiveness of the extraction language. The Sampling Problem. Suppose we are interested to wrap pages containing information about professors. For the sake of simplicity, let us represent pages as tables, where data is organized in rows and columns. Figure 1(a) shows sample pages depicted according to the above simpli cation. A wrapper can be described as a set of extraction rules. In our abstraction, an extraction rule speci es the cell containing the relevant data, and it can be expressed by absolute coordinates (e.g. rst row, second column), or by relative coordinates, that is, with respect to another cell (e.g. the rst cell located at the right of the cell containing `Email'). Correspondingly, suppose that we choose to adopt only XPath extraction rules of one form out of two possible: absolute extraction rules (e.g. /html[ 1 ]/table[ 1 ]/tr[x]/td[y]) that we denote abs(x,y); relative extraction rules (e.g. //tr[td[contains(.,'x')]]/td[ 2 ]) that we denote right-of(`x').

For example, according to Rick's page, candidate extraction rules for Name are abs(1,1) and above(`Home'). Similarly, rules for Position are abs(5,2) and right-of(`Position').

Now suppose that the Position of professors is a relevant attribute to extract. If the sample set is composed only of awarded professors (such as Rick), inferred rules could not work for the broader set of all professors, including those without any award (such as Mark and Bill). For example, the rule abs(5,2) for Position might work for all the awarded (a) sample pages r2 [e-mail] [e-mail] [e-mail] professors, but it does not extract the position for other professors.

The usual approach to address this issue is to work with a large set of annotations that hopefully covers all the possible types of target pages. However, according to our cost model, this strategy is ine cient.

The Expressiveness Problem. Consider again the running example and suppose we are interested to extract professors' Name and Home. We now show that the size of the sample set actually depends on the expressiveness of the language used to specify the rules, and hence on the set of available rules.

Suppose that we choose to adopt only absolute extraction rules: a correct rule for Name is abs(1,1). Note that only one labeled sample would su ce to infer this rule. Suppose now to adopt a more expressive language, which also includes relative rules. Using just one page, say Rick's, several rules are generated to extract Name: abs(1,1), above(`Home'), above(`rick.usr.edu'). To determine the correct rule at least another well chosen example is required: only with the help of Mark's page we have the evidence that the rule above(`Home') does not work.

To summarize, the more expressive is the model, the larger is the size of the representative sample set [ 1 ] [ 5 ] (intuitively, the space of hypotheses is larger and thus more examples are needed to discard the incorrect ones). However, the additional expressiveness should be carefully handled, since its actual need depends on the input pages and on the desired attributes, whereas it always entails additional costs.

The usual approach to address this issue is to work with overly expressive languages to cover all needs. However, as made explicit by our cost model, this strategy is ine cient. Overview. In this paper we address the above issues. We show that they cannot be tackled separately, and propose an approach that carefully handles the expressiveness of the wrapping language, and the choice of the samples (i.e. the pages to be annotated).

We propose an approach, inspired by a statistical learning technique [ 14, 13 ], in which the expressiveness of the language is enlarged at runtime. We organize the class of candidate rules R into a hierarchy of classes fRhg0 h m of increasing size: initially the correct rule is searched only 0 within R , and then the set of available extraction rules might be expanded to a larger class Rh.

The goal is to achieve the expressiveness of the largest classes only whenever it is detected as actually needed. For all those cases that can be solved within the smaller classes of rules, the algorithm will save many samples.

The approach is independent of the details of the formalism used to express extraction rules. Our hierarchy fRhg makes use of simple rules, as follows: R0 is the class of absolute XPath rules as described before; Rh, for 0 < h m, is obtained by adding to Rh 1 the class of relative XPath rules with distance at most h from a pivoting leaf to the value.1 However this is just one possibility: the hierarchy can be built with other of rules.

A landmark decision is whether and when expanding the set of candidate rules. We introduce a probabilistic model to dynamically characterize the probability of correctness for rules in the current class of candidate rule Rh. We propose an original active learning algorithm [ 12 ] that exploits the probabilistic model for deciding to enlarge Rh lazily, i.e. only whenever there is enough evidence that the correct rule is not amongst the current set of candidates. The algorithm actively chooses the next membership query to nd a representative sample set: it selects a sample page and poses a membership query on an extracted value. By accurately choosing this value, the number of queries can be minimized.

The paper is organized as follows: Section 2 discusses related work; Section 3 formalizes our setting and states the problem de nition; Section 4 develops a probamilistic model to characterize the correctness of extraction rules; Section 5 presents an active learning algorithm for extraction rules based on the model; nally, Section 6 discusses our preliminary experiments with a set of sources from the Web. 2.

RELATED WORK

In machine learning, the number of labeled samples needed by a supervised learning algorithm to infer a good hypothesis is called sample complexity, and has been studied from several perspectives. For instance, similarly to our setting, [ 1 ] discusses the problem of exactly inferring a concept, i.e. a set of elements, by means of membership queries, i.e. question 1In the current prototype all textual leaves are used as candidate pivot. The distance from the pivot to the extracted node is measured according to the number of edges crossed in the DOM representation of the HTML pages but considering contiguous siblings at distance 1. of the type \is this an element of the target concept?". However, the main idea underlying our approach has been proposed by the statistical learning community [ 14 ], in which a loss function is given in order to characterize the quality of the produced hypothesis. The structural risk minimization (SRM) technique [ 13 ], i.e. the decomposition of the set of hypotheses into a hierarchy of subclasses, aims at avoiding the over tting problem: since the class of hypotheses studied by this community might be so expressive to be able to arbitrarily reduce the loss, a trade-o with other quality criteria is needed to avoid that the learning algorithm selects the hypothesis describing the training data perfectly, rather than their underlying patterns.

Many researchers have proposed several variations of the learning paradigm to make it practically feasible in di erent applicative contexts: the learning approaches in which the inference algorithm is free to choose which sample to label next are usually de ned active [ 12 ]. These have recently gained interest, since, as clari ed in [ 3 ], that they might produce exponential improvements over the number of samples wrt traditional supervised approaches.

To the best of our knowledge and di erently from our proposal, all the approaches for inferring wrappers over structured websites developed by the researchers in the wrapper community [ 6, 2, 9, 4, 15 ], de ne the set of hypotheses statically, i.e. before performing the inference, and once set, the set of candidate rules cannot be changed without seriously revisiting the inference algorithm. Therefore they oversize the expressiveness of the formal language used to specify the extraction rules and additional samples are required only to compensate with the excess of expressiveness.

Active learning approaches for wrapper induction have been proposed in [ 11, 10 ]. However, also in these works the expressiveness is statically de ned. Moreover, the latter approach requires complex user interaction, since the user has to choose the correct wrapper within a set of ranked proposals.

A few recent proposals try to scale the wrapper inference to the web scale [ 7, 8 ]. In [ 7 ] the authors leverage an available dataset, but it is not clear how they can ignore the presence of biased samples (as suggested by its running example based on popular objects itself), while in [ 8 ] it is needed domain knowledge that only an human expert can provide.

3. PROBLEM DEFINITION

Preliminary De nitions: Let U = fp1; p2 : : : png be a set of pages. Every page publishes several attributes of interest (e.g. professor Position, Email, etc.). For simplicity, we develop the discussion concentrating on one attribute, and we assume that its values are either a textual leaf of the DOM tree representation of the pages, or a distinguished nil value. We write v 2 p to denote that v is a value of the page p, pv to denote the page in which the value v is located, and jpj to denote the number of values in p.

We refer to a generic extraction rule (or simply rule) r over the set of pages U as a concrete tool to build a vector of values indexed by the pages in U such that r(p) 2 p [ fnilg. Every rule extracts one vector of values from U denoted r(U ). Figure 1(c) shows the vectors extracted by the rules r1, r2, r3, r4 in Figure 1(b). We denote with R(U ) the set of vectors obtained by applying a set of rules R over U , and blur the distinction between a rule and the vector it extracts from U . Note that jR(U )j jRj, with the strict inequality holding whenever a vector is extracted by di erent rules.

We denote with fRhg the hierarchy of classes of all the generable rules, i.e. the extraction rules that can be generated to extract vectors from U . The classes of this family are countable but potentially not nite. We will manage to work with a nite restriction of them, called the set of generated rules, as discussed in the following.

Labeled Sample Sequences: we introduce the concept of labeled sample vl where v 2 pv is a value from a page pv, and l 2 f+; g is either a positive or a negative label. In the following v+ and v denote a positive sample (or annotation) or a negative sample, respectively, that is the two possible answers to a MQ.

A rule r is admissible wrt to a set of samples L (denoted L(r)) i :

L(r) , 8vl 2 L; ll == + !! rr((ppvv)) =6= vv that is, it is compliant with the labels in the set.

The concept can be trivially extended to set of rules R, and we denote with RL = fr 2 R : L(r)g the subset of admissible rules in R wrt L and with VbLR(U ) all the values they extract from U : VbLR(U ) = fv : v = r(p); r 2 RL; p 2 U g.

Example: Let pr, pm and pb be the pages in Figure 1(a) and let U = fpr; pm; pbg. The attribute Email is extracted by the rule r2 =right-of(`Email'): two positive samples are v0+ =`[e-mail]' and v1+ =`[e-mail]', a negative sample is v2 =`123-454-3210'. Observe that r2 is admissible wrt to L = fv0; v1; v2g. Now consider another rule r1=abs(5,2) and the set of rules R = fr1; r2g. Then r1 is not admissible wrt to L since r1(pb) = `123 454 32100 which is the negative sample v2 . Hence, RL = fr2g and VbLR(U ) = fv0; v1g.

In the following, given a set of rules R, we will only consider special ordered sets of samples, called labeled sample sequences, which are formed by an initial annotation, and then by adding only new values which are still admissible with respect to the samples already seen. Intuitively, a labeled sample sequence is the list of answers to the MQ posed to learn a rule: De nition: A Labeled Sample Sequence (l.s.s.) L wrt to a set of rules R and a set of pages U is speci ed by a sequence of labeled sample v0; : : : ; vk; : : : that de nes a sequence of such that: (i) it begins with an an[nfovtkagtio=n fvv0+0+;6=v1;n:i:l:, ;avnkdg (observed) sets Lk with Lk+1 = Lk (ii) 8k > 0; vk 2 VLRk (U ) = VbLRk (U ) n Lk.

The constraint (i) on the rst annotation v0+ of the sequence is useful to get nite2 RL1 , whereas the constraint (ii) on the remaining samples entails that the new sample vk that forms Lk+1 from Lk leads to smaller and smaller admissible sets: RLk+1 RLk . It is worth noting that RLk+1 plays the role of what the learning communities call the versionspace [ 12 ], i.e. the set of hypotheses still plausible after having considered an input set of labeled samples.

In the following we will uniformly refer to both L and one of its observed subsets Lk blurring the di erences between the two concepts whenever the context clari es which one is actually involved. 2The rst annotation can also be conveniently seen as the speci cation of the desired attribute.

It can always be decided whether a rule extracting the desired vector exists. However, since it is not known in advance whether that rule was in the set of all candidate rules, the only certain way to be sure of its presence is by checking every single page [ 1 ]. In order to minimize the number of MQ, we develop a probabilistic characterization of the rules, and restate our problem in that sense. Problem De nition: Given a hierarchy of classes of extraction rules fRhg0 h m over a set of pages U , and a threshold , nd either a correct rule r 2 Rm, or conclude that no rule is correct in any Rh with probability greater than 1 , by minimizing the length of the input l.s.s. L.

A PROBABILISTIC MODEL FOR

STRUCTURAL RISK MINIMIZATION We introduce a probabilistic model for evaluating the correctness of an extraction rule, given a l.s.s. L, and a class of rules R. As a consequence, the model is able to compute the probability that a correct extraction rule has not been generated.

The notations used for main events covered by our analysis, and their probabilities, are summarized in Table 1. 5 We assume that the probability of an extraction rule is determined by the extracted values r1(U ) = r2(U ) ) P (r1) = P (r2).

Given a new labeled sample vkl to form Lk+1 = fvklg [ Lk, we denote with P (Lk+1) the probability P (vkl; Lk). By applying Bayes' theorem, the probabilities of the two main events of interest are:

P (rjLk+1) = P (RjLk+1) =

P (vkljr; Lk)P (rjLk)

P (vkljLk)

P (vkljR; Lk)P (RjLk)

P (vkljLk)

(1) (2) where P (vkljLk) is a normalization factor that can be expressed as:

X r2RLk

P (vkljri; Lk)P (rijLk) + P (vkljR; Lk)P (RjLk)

For any k, P (rjLk+1) and P (RjLk+1) can be de ned iteratively by means of P (vkljr; Lk), P (vkljR; Lk), P (RjLk) and P (rjLk). P (vkljr; Lk) and P (vkljR; Lk) can be de ned by abstracting the actual process that leads to the observed l.s.s into a simple generative model. This is essentially equivalent to de ne a p.d.f. over every l.s.s..

By repeatedly applying the bayesian updating rules expressed by equations 1 and 2, the model allows the computation of P (RjLk+1) and P (rjLk+1) for any k, starting from prior-probabilities P (RjL0) = P(R) of having generated a correct rule, and P (rjL0) = P(r) of r being a correct rule. The iteration continues until admissible rules exist, i.e. until RLk 6= ;. 4.1

Generative Model

In this section we describe a simple generative model for the k lt.hsa.st.,ru(Use)fuisl tfohre dcoerrirveicntgvethcteorpotosteerxitorracptroobnacbeialitly.s.Ps.(rLjLk+1) has been observed. This vector is not known in advance, but the values forming the l.s.s. Lk+1 will be labeled as either positive or negative according to it.

Let P(R) be the prior probability that the correct vector can be extracted by a rule belonging to R. We suppose that the acquisition of a new labeled sample vk to form Lk+1 from Lk follows a uniform p.d.f. amongst all values still queryable, i.e. the values in VLRk (U ) = VbLRk (U ) n Lk.

Similarly, given a correct rule r, let V +(Lk; r) = VLRk (U ); r(U ) denote the set of all and only the values that can form new positive samples, and V (Lk; r) = VLRk (U ) n V +(Lk; r) the set of values that can form negative samples. It follows: P (vkljr; Lk) = (

1 jVLRk (U)j 0 ; i vk 2 V l(Lk; r) ; otherwise

Similarly, we can compute P (vkljR; Lk) following an approach based on a uniform p.d.f. over all possible values. These are essentially all the values in VLRk (U ) but only the values in VLRk (U ) \ RLk (U ) can be labeled either positive or negative (and we assume with the same probability) while the values in VLRk (U ) n RLk (U ) will surely be labeled negative. Therefore, it follows that P (vkljR; Lk) = 8 P (vkljR; Lk) = 2 jVLRk (U)1\RLk (U)j ; i vk 2 VLRk (U ) \ RLk (U ) > >< P (vk jR; Lk)= jVLRk (U)n1RLk (U)j ; i vk 2 VLRk (U ) n RLk (U ) > >: 0 ; i vk 62 VLRk (U ) Note that the exact computation of the set RLk (U ) can be expensive, since given a value v 2 VLRk (U ), in order to gure out whether v 2 RLk (U ), we should enumerate a potentially very large number of vectors in RLk (U ).

We adopt an approximate and e cient solution based on the assumption that the equivalences holding for k = 0:3 VLRk (U ); RLk (U ) = VLRk (U ) and VLRk (U ) n RLk (U ) = ;, also hold for any k > 0. Hence, it can be rewritten as: P (vkljR; Lk) ' (

1 2 jVLRk (U)j 0 ; i vk 2 VLRk (U ) ; i vk 62 VLRk (U ) (3)

Actually, this is an oversimpli cation when k gets bigger and approaches jU j: both RLk (U ) and VLRk (U ) gets smaller and smaller and VLRk (U ) n RLk (U ) 6= ;. Since our algorithm look for the correct rule while minimizing k, in our setting this sempli cation does not signi cantly a ect the results. 4.2

A-priori Probabilities

Our probabilistic model is based on the following priors: the prior probability P(Rh) that a correct rule has been generated in the set of rules Rh; the prior probability P(r) that the extraction rule r does extract the correct vector of values from the input set of pages U . As regards the former prior p.d.f. P(r), it is set by using a uniform p.d.f. over all rules in RL1 .

For the latter priors P(Rh), we follow a standard approach, and estimate the priors on a su ciently large set of attributes the frequency of the involved events.

P(Rh) has been set equals to nh where nh is the number N of attributes extracted by a rule in Rh and not in Rh+1, and N is the number of attributes used in our estimation (we sampled N = 356 attributes). 3Admitting that every value is extracted at least by one rule. For example, 95% of the attributes can be extracted by 3 rules in R , while to cover the remaining 5% of attributes we should stretch our set of candidate rules to R10.

LEARNING EXTRACTION RULES The probabilistic model just developed aims at at computing, observed an l.s.s. Lk+1, the probability P (rjLk+1) that a given extraction rule r within a set of candidate rules R is correct, and the probability P (RLk+1 ) that the correct rule has not been generated at all, i.e. it is not inside R.

Here, we start presenting an active learning algorithm that exploits these probabilities (Sec. 5.1); then, we describe a strategy to choose the next sample to be labeled (Sec. 5.2); nally, we discuss how the set of candidate rules is dynamically expanded according to the \observed need of expressiveness" rather than statically predetermined (Sec. 5.3). 5.1

Active Learning Algorithm

As shown by the pseudo-code in Listing 1, our algorithm takes as input a labeled sample sequence L built by actively [ 12 ] asking to an oracle (here modeled by means of the subprogram oracle()) the label of a sample chosen by the subprogram chooseSample(). The algorithm is parametric wrt a class of extraction rules decomposed into a hierarchy h , and it makes use of the probabilistic of subclasses fR g model detailed before (lines 8-9).

Initially, R0 is taken as initial set of candidate rules, and 0 the set of rules admissible wrt the initial sample RL1 is computed (lines 1-2). In every iteration, the oracle is asked to label a new sample vk (lines 4-5) and the l.s.s. is updated to obtain Lk+1 (6). Then, the set of admissible rules is updated (7) (recall that RLk+1 RLk ), and the probabilities P (rjLk+1) and P (RLk+1 ) are consequently updated (8-9). expandRuleSet() has to decide whether the set of candidate rule should be expanded (line 10).

This algorithm can be instantiated by appropriately choosing the semantics of three subprograms: chooseSample(), which selects the next sample to be labeled for the user; halt(), which establishes an exit criterion before the l.s.s. naturally expires (i.e. R becomes empty); and nally, expandRuleSet(), which decides at runtime whether Rh should be expanded with new candidate rules by incrementing h. h The latter decision is usually based on P (RLk+1 ): the higher its value, the more likely that new candidate rules are needed. The implementation of halt() strongly depends on the overall goal of the search strategy. We leave further investigation on this aspect to future work; in the present paper, for illustrative purposes, we use a minimum threshold r on the probability of the best rule: halt(R, L) f return (argmaxr2RL P (rjL) > r); g Listing 1 An active learning algorithms for extraction rules Input: set of sample pages U = fp1; : : : ; p+jUjg Input: an initial positive sample L1 = fvo g Parameter: a hierarchy of generable rules fRhg over U h Output: P (rjLk+1) over r 2 RhLk+1 , P (RLk+1 ); 1: let k 1; let h 0; 2: let R Rh; R RL1 ; 3: while (R 6= ; and not halt(R; Lk)) do 4: vk chooseSample(R; Lk); 5: l oracle(vk); 6: Lk+1 Lk [ fvklg; 7: R RhLk+1 ; 8: compute P (rjLk+1); 8r 2 R according to eq. 1; 9: compute P (RhjLk+1) according to eq. 2; 10: h h + expandRuleSet(R; Lk+1); 11: k k + 1; 12: end while 13: if (R 6= ;) then 14: return RhLk+1 , P (rjLk+1) and P (RhjLk+1); 15: end if 16: return ?;

In the following, we detail chooseSample() and expandRuleSet(), respectively. 5.2

Choosing the Right Samples

For instantiating chooseSample() we propose two variants: Entropy plus a baseline algorithm Random.

Random: It chooses a random admissible sample: chooseSample(R,L) f return a random v 2 VLR(U ); g and it serves two purposes: as a baseline against other strategies, and as a measure of the sample complexity of its extraction.

Entropy: It bases the sample choice on the p.d.f. of the extracted value: a simple strategy is to choose the sample on which rules most disagree, appropriately weighted according to their probability. This is equivalent to compute the vote entropy [ 12 ] for each v 2 RLk (U ): H(v) = [P (v+jLk) log P (v+jLk) + P (v jLk) log P (v jLk)] (4) where: and:

P (v+jLk) = Pr2fr2RLk :r(pv)=vg P (rjLk) P (v jLk) = Pr2fr2RLk :r(pv)6=vg P (rjLk) are the probabilities that v is respectively either a value to extract or an incorrect value.

The next sample is the one maximizing the vote entropy: chooseSample(R,L) f return argmaxv2VLR(U) H(v); g Note that this choice essentially removes the most uncertain sample. 5.3

Dynamically Expanding the Rule Set expandRuleSet() is in charge of deciding whether and when expanding the hierarchy of candidate rules Rh. It h makes use of the probability P (RLk ) of the correct rule not being present in the current set of candidate rules Rh after observing as input a given l.s.s. Lk.

We leave a thoroughly discussion of the best criteria underlying this analysis to future work, while in this paper we use a trivial implementation expandRuleSet() based on a prede ned xed threshold R over P (RLk ): expandRuleSet(R, L) f if (R = Rm) return 0; // max expansion reached else if (P (RL) > R ) return +1; else return 0; g

The set of rules is therefore enlarged lazily, i.e. only whenever according to P (RL) there is evidence that a correct rule is not amongst the currently available candidate rules.

EXPERIMENTS AND FUTURE WORKS We built a Java prototype implementation of our algorithms.We report the results of some preliminary experiments mainly focused on evaluating the e ectiveness of the SRM technique. We downloaded pages from 101 websites publishing information in several domain. For each website, we downloaded a small set of sample pages (about 20) sharing a common HTML template, and considered as relevant 2 4 attributes, for which we manually crafted a golden extraction rule to get as a reference the correct values, totally considering 240 attributes.

The results have been collected running our prototype with r = 0:99 and R = 0:95. Table 6 reports: the (rounded) average number of MQ by Random over 10 executions (Rnd);4 the aggregated number of attributes extracted by Random (#A); the number of MQ posed by Entropy with R5 and SRM disabled, (H); the number of MQ when SRM starts from the class of extraction rules Ri with i = 0; 1; 2; 3 (SRM-Ri). The last row reports the average precision of the values extracted by the output rules.

SRM always saves MQ. Whenever the initial expressiveness is low, the precision su ers, and the number of MQ saved is higher. This can be explained by expandRuleSet making wrong decisions, i.e. it trusts on current imprecise rules rather than betting on more expressive classes. Note that even Entropy cannot reach 100% since there exist at5 tributes that need rules out of R .

Since our dataset consists of a small number of pages per site and it is not suitable for evaluating the sampling issue, we leave it to future work. To overcome the precision loss with the SRM approach, it is possible to add additional informations, e.g. types analysis (to weight more vectors 4These values represent the sample complexity.

H 4 4.12 4.08 3.86 3.5 3.58 3.45 3.01 2.27 96.2% R 1.90 1.56 1.66 1.26 1.55 1.46 1.55 1.76 1.59 86.7% R 2.33 1.78 1.69 1.58 2.06 1.96 2.06 1.54 1.65 93.79% R 2.89 3.22 2.7 3.22 2.39 2.48 2.52 2.11 1.71 95.85% R 3.56 3.25 3.63 3.40 2.77 3.13 3.14 2.38 1.76 96.2% with homogeneous type). Also, we aim at integrating SRM with automatic annotators that rely on data available on external sources, such as Freebase, and with crowdsourcing platforms.

References

[1] D. Angluin . Queries revisited . Theor. Comput. Sci. , 313 ( 2 ): 175 { 194 , 2004 .

[2] A. Arasu and H. Garcia-Molina . Extracting structured data from web pages . In SIGMOD 2003 .

[3] M.-F. Balcan , S. Hanneke , and J. W. Vaughan . The true sample complexity of active learning . Machine Learning , 80 ( 2-3 ), 2010 .

[4] C.-H. Chang and S.-C. Lui . IEPAD: information extraction based on pattern discovery . In WWW 2001 .

[5] V. Crescenzi and G. Mecca . Automatic information extraction from large websites . J. ACM , 51 ( 5 ): 731 { 779 , 2004 .

[6] V. Crescenzi and P. Merialdo . Wrapper inference for ambiguous web pages . JAAI , 22 ( 1 &2): 21 { 52 , 2008 .

[7] N. N. Dalvi , R. Kumar , and M. A. Soliman . Automatic wrappers for large scale web extraction . PVLDB , 4 ( 4 ): 219 { 230 , 2011 .

[8] T. Furche , G. Gottlob, G. Grasso , O. Gunes , X. Guo , A. Kravchenko , G. Orsi, C. Schallhart , A. J. Sellers , and C. Wang . Diadem: domain-centric, intelligent, automated data extraction methodology . In WWW (Companion Volume) 2012 .

[9] G. Gottlob , C. Koch , R. Baumgartner , M. Herzog , and S. Flesca . The lixto data extraction project - back and forth between theory and practice . In PODS 2004 .

[10] U. Irmak and T. Suel . Interactive wrapper generation with minimal user e ort . In WWW 2006 .

[11] I. Muslea , S. Minton , and C. A. Knoblock . Active learning with multiple views . JAIR , 27 : 203 { 233 , 2006 .

[12] B. Settles . Active learning literature survey . CS T.R. 1648, Univ. of Wisconsin{Madison , 2009 .

[13] J. Shawe-Taylor , P. L. Bartlett , R. C. Williamson , and M. Anthony . Structural risk minimization over data-dependent hierarchies . IEEE Transactions on Information Theory , 44 ( 5 ): 1926 { 1940 , 1998 .

[14] V. Vapnik . An overview of statistical learning theory . IEEE Transactions on Neural Networks , 10 ( 5 ): 988 { 999 , 1999 .

[15] Y. Zhai and B. Liu . Structured data extraction from the web based on partial tree alignment . IEEE Trans. Knowl . Data Eng., 18 ( 12 ): 1614 { 1628 , 2006 .