Corinne Curt
email: corinne.curt@cemagref.fr

Aurélie Talon

Gilles Mauris

A DAM ASSESSMENT SUPPORT SYSTEM BASED ON PHYSICAL MEASUREMENTS, SENSORY EVALUATIONS AND EXPERT JUDGEMENTS

Keywords: sensory evaluation, expert assessment, uncertainty, possibility theory, dam safety

A dam assessment support system based on physical measurements, sensory evaluations and expert judgements

Introduction

Modelling complex phenomena and providing data for their subsequent use in decisionmaking are crucial and challenging tasks that necessarily involve not only interdisciplinary but also expert knowledge [1-2-3-4]. Human beings can play various roles in such system control procedures (measurement, assessment, decision-making).

In particular, operators in charge of running the system concerned often have to propose corrective actions to guarantee that it runs correctly. For example, in civil engineering, these actions concern major reconstruction, rehabilitation or safety projects, emergency actions and so forth. They aim at preventing accidents and maintaining the infrastructure, subject to unavoidable ageing, in good and serviceable condition at minimum cost. Corrective actions rely on human ability to perform global assessments of processes. Usually, several data aggregation steps are performed due to the large variety and quantity of data available on a system. Indeed, systems are often assessed on the basis of only a few global data that provide a synthetic view of low level system data. In the case of dam safety assessment, it is important to perform a global assessment of dam safety deterioration related to different failure modes along with evaluations of the reliability of different technical functions, such as sealing and drainage [START_REF] Cigb | Ageing of dams and appurtenant works -Review and recommendations[END_REF] that can be viewed as intermediary assessments. The objective is to detect and correct phenomena that, if no action is carried out, can lead to (i) various deteriorations that may result in accelerated ageing, additional operational and maintenance costs, significant loss of water in dams and (ii) failures liable to cause dramatic events such as dam failure. These deteriorations are caused by many more or less interdependent dynamic processes, such as clogging, internal erosion, sliding, having various and often multiple sources [START_REF] Cigb | Ageing of dams and appurtenant works -Review and recommendations[END_REF]. Finally, experts can play an important role in the sensory evaluations involved in global or intermediary assessments. Indeed, numerous examples of system control indicate that models of complex phenomena cannot be supplied only with Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement,44,[START_REF] Mak | Aggregating and updating experts' knowledge: an experimental evaluation of five classification techniques[END_REF][192][193][194][195][196][197][198][199][200][201] Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042 physical measurements, for example in food processing [6-7-8-9] and in civil engineering [10-11-12-13] but also require quantities evaluated by human beings. These have become an inherent part of many complex system analyses [14-15-16-17].

As human knowledge is seldom formalised, it is necessary to develop methods for collecting and modelling the information and knowledge involved in such complex assessments. This paper focuses on methods that allow a coherent representation of the different data (sensory evaluations, physical measurements, outputs of mathematical models, etc.) used in the global dam assessment process (Section 2). These data are heterogeneous in nature: symbolic or numerical, real-time or delayed, absolute values or trends, level of uncertainty different from one variable to another, etc. In order to facilitate information processing, physical measurements, sensory evaluations and expert judgements on quantities must be considered as assessments with similar representations, in particular concerning the associated uncertainties [START_REF] Cook | Experts in Uncertainty[END_REF][START_REF] Denguir-Rekik | Propagation of uncertainty by the possibility theory in Choquet integral based decision making: application to an E-business website choice support[END_REF]. As the latter are often expressed in either a qualitative way, or in the form of partial knowledge of probability, we used a possibility theory based approach to represent all the different uncertain pieces of information [20-21-22-23-24]. Then, local and intermediary assessments have to be aggregated to obtain a global assessment of the complex system considered, i.e. a dam [START_REF] Curt | Using physical measurements, sensory evaluations and expert judgements in a dam assessments support system[END_REF] (Section 3). Finally, for decision-making and communication purposes, the global possibility assessment has to be appropriately defuzzified (Section 4).

Human beings as assessment devices

The roles of experts in dam assessment

In many cases, experts can assess system characteristics thanks to their knowledge and experience. For instance, in civil engineering, visual inspection is a key item, for example in the case of dam surveillance, cracking, differential movements, seepage, and the presence of [START_REF] Poupard | La surveillance des barrages[END_REF]. These visual assessments are used in addition to instrumental measurements from in situ sensors (piezometry, crack measurements, leakage, etc.), design and construction data (slopes, top width, permeability, etc.), and outputs of mechanical models (hydraulic gradient, seismic resistance, spillway capacity, etc.) (cf. Figure 1).

Dam characteristics

Geometry

Material properties Design, Construction Hydrology, Hydraulics

Data calculated from models

Monitoring measurements

Visual observations

Formalisation of data as Indicators

Indicators Agregation

(expert approach)

Safety and reliability assessment

Dam characteristics

Geometry Material properties Design, Construction Hydrology, Hydraulics

Data calculated from models

Monitoring measurements

Visual observations

Formalisation of data as Indicators

Indicators Agregation (expert approach)

Safety and reliability assessment embankment or the decrease of the drainage flow indicates a degradation of the drainage function. Moreover, at a higher level of decision, these data have to be aggregated and interpreted with respect to their influence on the proper functioning of the system or on subsequent structural or functional deteriorations, or failures. Thus, the different levels of expert assessment have to be structured in a common space of representation, leading to the concept of indicator [START_REF] Curt | Formalisation of at-line human evaluations to monitor product changes during processing. Integration of human decision in the dry sausage ripening process[END_REF]. The indicator structure is notably defined with a degradation scale allowing the assessment of the system degradation. The scale is here within the range [0, 10]. Moreover, the representation given by this indicator must encompass the uncertainty inherent to human perception and incomplete knowledge.

The notion of degradation scale (identical to a notion of performance scale ) raises certain philosophical issues in the context of measurement theory [START_REF] Finkelstein | Problems of measurement in soft systems[END_REF][START_REF] Mari | The problem of foundation of measurement[END_REF]. Indeed, degradation is not a physical measurement and is subject to subjective assessments. However, as the aim of this paper is to propose operational processing for expert dam assessment, we will not study the concept of degradation "measurability" [31][START_REF] Urbanski | Fuzzy measurement theory[END_REF], but consider that a small group of experts agrees on a commensurate meaning of dam degradation scores.

Hereafter, we first present the situation where the system variables are directly assessed by the expert, followed by the situation in which the system variables are measured by an instrument and interpreted by experts.

2.2.

Direct expert assessment of system variables Some characteristics or properties of a system are very difficult to quantify with instruments due to their cost or the lack of reliable sensors. Human perception is thus widely accepted as a solution for evaluation in different fields. A methodology aimed at capitalizing the skill of operators or experts in making sensory evaluations has already been proposed and has led to the concept of "sensory indicators" [START_REF] Curt | Formalisation of at-line human evaluations to monitor product changes during processing. Integration of human decision in the dry sausage ripening process[END_REF]. This methodology is based on a grid composed of seven The scores provided by all the indicators are in fact deterioration level scores and are defined on a 0-10 scale. 0 means no deterioration at all while 10 means a high deterioration level. For the purposes of interpretation, the degradation scale is divided into six categories from "excellent" (0 -no deterioration) to "unacceptable" (10-considerable deterioration), ranging through "good" (1-2), "passable" (3-4), "poor" (5-6), and "bad" (7-8-9).

References are key elements for ensuring the meaningfulness of the assessments: they are anchorage points on the scale that facilitate comparison between situations. The aim is to specify the different possible situations so that an assessment performed by several experts, or by the same expert at different times, leads to the same score. They can be photographs, diagrams or textual descriptions. To illustrate this, let us consider the visual indicator "Sinkhole, subsidence cone": a score of 0 corresponds to an absence of sinkhole or subsidence cone, scores from 7 to 9 to an isolated, small sinkhole (several dm), a new sinkhole (less than 1 year) or an isolated, very large or old (several years) sinkhole. A score of 10 corresponds to a very large, new (less than 1 year) sinkhole. Spatial characteristics are essential. It is very important to specify where the measurement must be made: crest, foundations, downstream fill, upstream fill and so forth.

Indeed, scoring changes as a function of location: the seriousness of a leak depends on the height at which it occurs. Usually, a spatial characteristic is associated with the indicator name:

for instance, "leakage on upstream fill".

Two temporal characteristics can be distinguished:

• the frequency of measurement which varies between the various kinds of measurement:

temperature and rainfall are collected daily, piezometry and flow are collected weekly, extensometer measurements are carried out monthly; displacement measurements yearly, etc.;

• the time interval for data processing: monitoring data are processed once a year and trends are analysed by considering a period of several years;

For the complete dam assessment, 60 different visual variables were identified and formalised as sensory indicators. They concern the different components of the dam that can be assessed visually: upstream and downstream shoulders, foundations, drains, external sealing structures (facing), crest, spillway and downstream toe. The sensory indicators were collected and formalized during elicitation sessions that involved five experts, i.e. people involved for at least ten years in dam reviews or analysis.

2.3.

Indirect expert assessment of system variables

Experts also have to convert physical measurements (stemming from sensors or models) into assessments in relation with the global information sought, e.g. safety or reliability deterioration. The scale for the monitoring and computed indicators is the same as that used for the sensory indicators: a 0-10 scale with 0 means no deterioration at all while a score of 10 means a high deterioration level. It should be noted that four categories (instead of six) are considered for the interpretation of such design and construction indicators: "low deviation" (0,1,2), "medium deviation" [START_REF] Liao | Expert system with methodologies and applications -a decade review from 1995 to 2004[END_REF][START_REF] Cigb | Ageing of dams and appurtenant works -Review and recommendations[END_REF][START_REF] Perrot | Optimal control of the microfiltration of sugar product using a controller combining fuzzy and genetic algorithms[END_REF], "high deviation" [START_REF] Davidson | Fuzzy control system for peanut roasting[END_REF][START_REF] Curt | Dry sausage ripening control -Integration of sensory-related properties[END_REF][START_REF] Ioannou | Development of a control system using the fuzzy set theory applied to a browning process-a fuzzy symbolic approach for the measurement of product browning: development of a diagnosis model-Part I[END_REF] and "non-conformity" [START_REF] Foo | Prototype knowledge-based system for corrective maintenance of pavements[END_REF]. Table 2 describes the instrumental monitoring piezometry indicator.

Possibility expression of imperfect assessments

Data handled by experts are frequently "imperfect": they contain uncertainty, imprecision, incompleteness. Examples quoted from dam review reports are: "This stair is quite large and reaches several decimetres" or "Piezometer faulty" or "Dike apparently built on granite".

Therefore, it is of great importance to take imperfections into account in the assessment procedure. This leads to an assessment of indicators that represents perception better than a precise numerical value. Indeed, forcing the indicators to provide precise scores in the case of uncertainty can lead the expert to give a very bad score in order to conform to the principle of caution. Consequently, corrective actions are more drastic than they should be.

Generally, the probability theory is used to deal with uncertainty. However, this means that uncertainty pertaining to the parameters representing physical processes can be described by a single probability distribution, but this requires substantial knowledge to determine the probability law associated with each parameter. Moreover, information regarding parameters is often vague, imprecise or incomplete. This lack of knowledge may stem from a partial lack of data, either because collecting this data is too difficult or costly, or because only experts can provide certain items of imprecise information. In this case, the possibility theory provides tools that are better adapted to represent imperfections through the use of possibility distributions [33- [START_REF] Baudrit | Practical representation of incomplete probabilistic information[END_REF][START_REF] Dubois | Possibility theory and statistical reasoning[END_REF]. Imperfections were modelled during assessment sessions that gathered a session leader and an expert. These sessions were composed of two phases: a brief presentation was performed by the session leader before the expert began the assessment of the variable considered. The presentation aimed at explaining the objectives of the session, the meanings of possibility distributions ("a distribution of possibility depicts the possibility that a variable takes the value x"), the types of distribution proposed and the expected results of the session. It also allowed the expert to ask questions to clarify possibly obscure points. Next, descriptive worksheets were successively distributed to the experts. The expert had at her/his disposal the description grid for each indicator assessed (i.e. grids such as presented in Table 1 and Table 2).

The experts scored an indicator as a distribution of possibility (equivalent to a normalised fuzzy subset) denoted π Ι . The core Cor(π Ι ) and the support Supp(π Ι ) are defined by:

{ } ( ) ( ) 1 I I Cor x X x π π = ∈ = (1)
{ } ( ) ( ) 0

I I Supp x X x π π = ∈ > (2)
The possibility distribution is built considering that the core represents the more likely values while the support represents the possible values. A linear interpolation is then carried out. Types of useful possibility distributions include triangle, trapezoid, interval shapes, etc. To quantify the amount of uncertainty of the possibility distribution, a specificity index S defined by the surface under the distribution can be used [START_REF] Dubois | Possibility Theory: an Approach to Computerized Processing of Uncertainty[END_REF]:

10 0 ( ) ( ) S x dx π π = ∫
. All the types of sensory, monitored and computed indicators are expressed with this single representation format. Figure 2 shows an example of a possibility distribution given by an expert for the indicator "Leakage of clean water through the embankment".

Comments on expert assessments carried out

In this subsection we discuss the results obtained during an assessment session in October 2008. Three Cemagref experts assessed fifteen indicators as possibility distributions. Thirteen cases were dedicated to visual sensory indicators while the two others were monitoring indicators. Indicator references were described as typical situations built from completed dam reports written at the end of detailed dam reviews performed by experts. The typical situations are described by a small number of paragraphs (dam description: height, first filling date, reservoir capacity, sealing type, etc.), information from visual inspection or monitoring data and photographs in case of visual indicators. For the assessment, experts used the description grid (cf. Tables 1 and2 for example) and the references. Various types of possibility distribution were expressed by the experts: trapezoid, triangle-shaped, precise interval and precise score (cf.

Table 3). Preference is given to a trapezoidal distribution. It represents slightly over 40% of the cases. The other three types of distribution each represented about 20%. The proposed possibility representation was quickly accepted by the experts and it was seen to be useful for assessing indicators. Moreover, in the first analysis, the experts who performed the exercise found the approach relevant for future application during dam diagnosis and analysis. Considering the whole set of possibility distributions, the maximal length used to define the support was 5 units (for instance F0 = [START_REF] Hutton | Expert decision making[END_REF][START_REF] Lightfoot | Expert knowledge acquisition and the unwilling expert: a knowledge engineering perspective[END_REF][START_REF] Liao | Expert system with methodologies and applications -a decade review from 1995 to 2004[END_REF][START_REF] Cigb | Ageing of dams and appurtenant works -Review and recommendations[END_REF][START_REF] Perrot | Optimal control of the microfiltration of sugar product using a controller combining fuzzy and genetic algorithms[END_REF]) while the maximal length to define the core was 2 units (for instance, F1 = [START_REF] Cigb | Ageing of dams and appurtenant works -Review and recommendations[END_REF][START_REF] Perrot | Optimal control of the microfiltration of sugar product using a controller combining fuzzy and genetic algorithms[END_REF]) on a scale from 0 to 10.

The three experts did not give exactly the same uncertainty for a given indicator. Table 4 provides the specificity of the possibility distributions (denoted Ei S and corresponding to the surface under the distribution) of each indicator and each expert Ei, considering that a precise score leads to a surface equal to 0. The specificity represents the dispersion of the expert's assessment. On average, E1 gives the smallest margin of uncertainty while E2 gives the largest.

Moreover, E1 and E3 give more frequently precise scores (cf. Table 3 and Table 4).

The differences between two possibility distributions can be quantified by the difference of the specificities: three differences were calculated for each indicator, i.e.

1 2 E E S S - , 1 3 E E S S - and 2 3 E E S S -
. These differences range from 0 to 3. Over 60% are less than or equal to 1 while over 90 % are less than or equal to 2. The mean values of these differences are about 1. These results indicate good agreement between the experts considering that the support length of the interpretation categories ("excellent" (0), "good" (1-2), "passable" (3-4), "poor" (5-6), "bad" (7-8-9), "unacceptable") is between 1 and 3. The cases for which compatibility is weak or null correspond to weak reference descriptions composed of only a few paragraphs. The references are not precise enough and can lead to interpretations that differ from one expert to another. The second explanation comes from the fact the reference descriptions were made on the basis of completed dam reports written at the end of detailed dam reviews performed by one Cemagref expert. The expert who carried out the review and wrote the completed report obtains more information than the other experts. This can lead to differences in the assessment.

Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

Human beings and global assessment

The amount of variables involved in a complex system can be quite considerable. Managers in charge of dam control often try to obtain a more synthetic assessment of the system by aggregating the available data. This global assessment allows the expert to propose corrective actions if necessary. For example, in civil engineering, these actions concern major reconstruction, rehabilitation or safety projects.

The main problem is to break down the global assessment into causal networks involving elementary measurements and intermediary assessments. This stage relies on expert knowledge capable of providing a diagnosis of the state of the dam and identifying the most probable scenario that would give rise to the measurements indicating abnormal values.

3.1.

Hierarchical dam system model

In the dam safety model considered, the global assessment relates to the deterioration of dam safety linked to different failure modes (denoted µFM), that depend on the reliability of different technical functions (denoted Fi), such as sealing, drainage, internal erosion protection and sliding protection, that are themselves assessed by different indicators (denoted Ii). An example of such a breakdown is illustrated in Figure 3. The mathematical justification of this operator used to aggregate indicators at the lower level of the hierarchy is linked to the principle of caution relating to these functions. All the indicators are assessed on the same scale ranging from 0 ("excellent") to 10 ("unacceptable").

Using the maximum operator, the worst situation is taken into account.

Fuzzy rules for the determination of φ 1 are: (R1) IF "Clean water seepage" > 2 AND "Piezometry" > 2 THEN φ 1 = MAX ("Clean water seepage", "Piezometry") (4) (R2) IF "Clean water seepage" ≤ 2 AND "Piezometry " ≤2 AND µF Sealing ≤ 2 THEN φ 1 = µF Sealing (5) (R3) IF "Clean water seepage"≤2 AND "Piezometry"≤2 AND µF Sealing > 2 THEN φ 1 = µF Drainage [START_REF] Perrot | Optimal control of the microfiltration of sugar product using a controller combining fuzzy and genetic algorithms[END_REF] where "Clean water seepage" and "Piezometry" are two direct indicators.

A model using the template presented in Figure 3 was described for each failure or degradation mode: internal erosion through the embankment, sliding of embankment or embankment and foundations, internal erosion initiated around or near a conduit, overtopping, internal erosion through soil foundations, settlement of soil foundations, dissolution of material or leaching of rock foundations. Figure 4 shows part of the model corresponding to the internal erosion.

Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

3.2.

Propagation of imperfections

Imperfections represented by possibility distribution must be propagated in the safety degradation model. The propagation of possibility distributions via an operation f obeys Zadeh's extension principle [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF]: In our context, function f is either a direct mathematical operation (max, mean) or a function stemming from fuzzy rules. A symbolic conjunctive approach for rule processing (with the product and the bounded sum as combination and projection operators), followed by defuzzification based on the height method, leads to a piece-wise linear expression for function f associated with the set of fuzzy rules [START_REF] Ioannou | Development of a control system using the fuzzy set theory applied to a browning process-a fuzzy symbolic approach for the measurement of product browning: development of a diagnosis model-Part I[END_REF].

An illustration of the propagation of possibility distributions declared by the experts in the global dam assessment is provided in Figure 5.

Experimental validation of the global assessment

To perform an experimental validation of the global assessment, the precise score given directly by the experts was compared to the result of the propagation of imperfections in the hierarchical model. The assessment was carried out by three experts on the basis of the indicator references presented in § 2.3. The failure mode considered here is internal erosion through the embankment. Three dams were evaluated by the three experts. For eight cases out of nine, the precise score given by the experts intersects with the possibility distribution obtained by the propagation in the hierarchic model. For one case, the precise score given by the expert was equal to 8 and the possibility distribution was calculated as a trapezoidal distribution whose support is [START_REF] Lightfoot | Expert knowledge acquisition and the unwilling expert: a knowledge engineering perspective[END_REF][START_REF] Perrot | Optimal control of the microfiltration of sugar product using a controller combining fuzzy and genetic algorithms[END_REF]. The precise score was out of the possibility distribution support. The expert explained the difference between these two assessments by the fact that the information available was not sufficient in the reference descriptions. The need to comply with the need to express the assessment of indicators as precise scores, albeit with imperfections, led the expert to give a very severe score in line with cautious behaviour

Communication and decision making on dam safety

The results obtained at the end of the imperfection propagation are useful for communication and decision-making concerning dam safety.

4.1.

Communication

Experts have to communicate results concerning dam safety to other safety actors, for instance, the dam owner or reservoir operator. This leads to two kinds of information (qualitative and quantitative descriptions) and two kinds of data (score and dispersion).

The quantitative score is obtained by the assessment of the upper bound of α-cut at 0.8. This α-cut value was chosen by the experts by considering the correspondence between the membership level and the fractile of a probability distribution [START_REF] Vick | Dam safety risk assessment: new directions[END_REF][START_REF] Baudrit | Représentation de la connaissance probabiliste incomplète[END_REF] and the analysis of defuzzification methods that provide real values [START_REF] Leekwijck | Defuzzification: criteria and classification[END_REF]. Indeed, the experts wanted to select the defuzzification value that corresponded to a value between a "mean probable" and "probable", i.e. between 50 and 90%.

The qualitative description consisted of membership degrees in the six categories of "excellent", "good", "passable", "poor", "bad" and "unacceptable" defined by intervals, i.e. rectangular fuzzy sets (cf. Figure 6).

For each πk, six compatibility degrees are calculated (one considering each category). An example is given in Table 5.

The qualitative dispersion is based on the interpretation of a quantitative dispersion assessed by using the relative specificity. The relative specificity corresponds to the specificity of the possibility distribution obtained divided by the specificity of the possibility distribution Four categories of qualitative dispersion were considered: "no dispersion", "low dispersion", "high dispersion" and "very high dispersion". Then, typical fuzzy sets for each category were defined. Typical fuzzy sets associated with qualitative dispersion categories and the corresponding relative specificity are presented in Table 6. Table 5 presents an example of the communicated results for a possibility distribution of safety deterioration obtained by using the hierarchical safety model.

Decision-making

Decision-making aims at proposing corrective actions to restore the dam to standard operating conditions. The objective is to guarantee that safety and reliability criteria are satisfied. Corrective actions are of various types:

• emergency action: partial or complete emptying of the reservoir;

• major reconstruction, rehabilitation or safety projects;

• maintenance actions such as drain outlet cleaning, scraping of the downstream slope, renewal of monitoring devices, etc.

• upgrading dam safety monitoring: increasing measurement frequency, performing laboratory tests, etc.

As a dam can be affected by several failure modes, a possibility distribution is obtained for each failure mode. A defuzzification method that allows comparing possibility distributions with each other [39-40-41-42] was selected with experts in order to rank these possibility distributions. Defuzzification consisted in reducing the possibility distributions into single values. The method considered is based on the mean of the α-cut at 0.8. A correspondence between this score for decision-making and the score for communication (upper bound of the αcut at 0.8) was chosen by the experts. This choice was carried out in order to obtain the same interpretation of the results from both cases, that is to say higher membership values were preferred, without taking into account the core of the fuzzy set. This defuzzification approach allows ranking the safety related to the various failure modes and thus prioritizing corrective actions.

Conclusion

This paper focused on the roles that human beings can play in complex systems, such as dam safety assessment, especially when assessing the entities involved. A unified and structured representation based on a formalisation grid and possibility distributions was proposed to offset the imperfections of measurements and expert assessments, aggregate them in a hierarchical model composed of different simple operations (max, min, average, etc.) and then synthesize them by using defuzzification methods. All the failure modes of embankment dams were dealt with. The method was applied by three experts on simplified cases: the representation scheme was quickly accepted by the experts and showed that it is useful for assessing indicators. The comparison of the results provided by several experts showed that good agreement was obtained between them, apart from a few indicators. The methods proposed were applied to a civil engineering application, i.e. dam safety assessment, but they could be applied to other fields in which human beings also play an important role in global measurement, assessment and decision-making.

2. 1 .

 1

  Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042 vegetation and sinkholes are all examples of visual characteristics assessed by experts during dam reviews

Figure 1 :

 1 Figure 1: Data used by experts for the assessment of dam safety

For the complete dam

  assessment, 14 monitoring indicators, 8 computed indicators and 150 design and construction indicators were identified and formalised. Therefore, with the 60 visual indicators, 232 indicators were considered for the assessment of the different types of dam. 2.4.

Figure 2 :

 2 Figure 2: Possibility distribution of the indicator "Leakage of clean water through the

Figure 3 :FlowFlowFigure 4 : 3 )

 343 Figure 3: Structure of the hierarchical model of one failure mode

  degradation indicator score and F s the technical function degradation score.

  , Differential settlements, Local and muddy seepage] OR Logical equations (φ Insufficiency of drainage capacity, µF Erosion Defence) , Differential settlements, Local and muddy seepage] OR Logical equations (φ Insufficiency of drainage capacity, µF Erosion Defence) , Differential settlements, Local and muddy seepage] OR Logical equations (φ Insufficiency of drainage capacity, µF Erosion Defence) , Differential settlements, Local and muddy seepage] OR Logical equations (φ Insufficiency of drainage capacity, µF Erosion Defence)

Figure 5 :

 5 Figure 5: Example of imperfection propagation in the global dam assessment

Figure 6 :

 6 Figure 6: Fuzzy sets for the calculus of membership percentage

S

  is the surface associated with the reference fuzzy set i ( S π is the surface associated with the degradation assessment and I S is the surface of the subset

4. 2 .

 2

Figure 1 :Figure 2 :Figure 3 :Figure 4 :

 1234 Figure 1: Data used by experts for the assessment of dam safety

Figure 5 :

 5 Figure 5: Example of imperfection propagation in the global dam assessment

Figure 6 :Table 1 :Table 2 :

 612 Figure 6: Fuzzy sets for the calculus of membership percentage

  Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

  Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

  Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

  Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

	1
	0,8
	0,6
	0,4
	0,2
	0
	0	1	2	3	4	5	6	7	8	9	10

  Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

  C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

	φ Insufficiency of drainage capacity	µ µ µ µF Erosion defence
		Sinkhole
		Differential settlements

The possibility distribution obtained by the aggregation of µF Sealing and µF Drainage i.e. φ Insufficiency of drainage capacity, is then aggregated with µF Erosion Protection to obtain µMR Internal Erosion.

Curt

  Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

  Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

  Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042 corresponding to complete ignorance (i.e. having a membership degree of 1 on the whole scale. 0-10). It is therefore defined by:

  Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

  Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

Table 3 : Number and types of possibility distributions used by the experts

 3 Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

	Experts	Precise	Precise	Trapezoidal	Triangle	Total
		score	interval	distribution	distribution
	E1	3	5	2	5	15
	E2	1	1	12	1	15
	E3	4	4	5	2	15
	Total	8	10	19	8	45

Table 4 : Specificities of the possibility distributions declared by experts

 4 Curt C., Talon A., and Mauris G. (2010) A dam assessment support sytem based on physical measurements, sensory evaluations and expert judgements, Measurement, 44,1, 192-201. Author-produced version of the final draft post-refeering the original publication is available at http://www.sciencedirect.com/ -DOI: 10.1016/j.measurement.2010.09.042

		S	E	1	S	E	2	S	E	3	S	E	1	-	S	E	2	S	E	1	-	S	E	3	S	E	2	-	S	E	3
	I1	1.5	1.5	1			0							0.5					0.5
	I2	0			1			2			1							2							1
	I3	0			2.5	3			2.5					3							0.5
	I4	1			1.5	0			0.5					1							1.5
	I5	2.5	2			0			0.5					2.5					2
	I6	0			2			0			2							0							2
	I7	1			2.5	2			1.5					1							0.5
	I8	1.5	3.5	3.5	2							2							0
	I9	1			0			2			1							1							2
	I10	2			2			2.5	0							0.5					0.5
	I11	1			2			0			1							1							2
	I12	0 5	2			2			1.5					1.5					0
	I13	0.5	2.5	2.5	2							2							0
	I14	1			2			1.5	1							0.5					0.5
	I15	1			2			1			1							0							1
	Mean	0.97	1.93	1.53	1.17				1.23				0.93


Rémi Gilleron

Patrick Marty

Marc Tommasi

Fabien Torre

Interactive Tuples Extraction from Semi-Structured Data

This paper studies from a machine learning viewpoint the problem of extracting tuples of a target n-ary relation from tree structured data like XML or XHTML documents. Our system can extract, without any post-processing, tuples for all data structures including nested, rotated and cross tables. The wrapper induction algorithm we propose is based on two main ideas. It is incremental: partial tuples are extracted by increasing length. It is based on a representation-enrichment procedure: partial tuples of length i are encoded with the knowledge of extracted tuples of length i -1. The algorithm is then set in a friendly interactive wrapper induction system for Web documents. We evaluate our system on several information extraction tasks over corporate Web sites. It achieves state-of-theart results on simple data structures and succeeds on complex data structures where previous approaches fail. Experiments also show that our interactive framework significantly reduces the number of user interactions needed to build a wrapper.

Introduction

In less than ten years, XML has become a standard for semi-structured data exchange and storage. From its preliminary usage in Internet technologies, XML influence has grown to become widely used now for corporate data 1 . XML usage includes document-like data produced for instance by word processors and spreadsheets, data for software interoperability (UDDI, WSDL). In the meantime, with the generalization of decision support systems, high valued corporate data such as economic statistics are generated by reporting tools 2 and are published as semi-structured documents. All such data participates in a new source of information that end-users want to query in an easy way.

But end-user accessibility of XML or XHTML data, by means of query tools, is more problematic than in the 1 See for instance www.oasis-open.org 2 See for instance jasperreports.sourceforge.net classical and long-standing experienced case of relational databases. This situation is due either to the lack of explicit and coercive data types or due to the extensibility nature of XML that allows great heterogeneity of data.

Therefore, in spite of standardized query languages like XPATH, a common attitude is to develop specific programs for each query over semi-structured data. Recently, techniques have appeared to assist end-users in designing such programs. For instance, the Lixto system [START_REF] Baumgartner | Visual web information extraction with lixto[END_REF] allows to define queries or so-called wrappers over semi-structured data in a visual and interactive framework. Unfortunately, specifying wrappers with such systems can be too difficult for end-users. Alternate or complementary approaches relying on machine learning techniques have been considered. As in a query by example system, an end-user annotates data to extract and the system induces an appropriate wrapper. Machine learning approaches have been widely developed for Web information extraction [START_REF] Carme | Interactive learning of node selecting tree transducer[END_REF][START_REF] Cohen | Web Document Analysis: Challenges and Opportunities, chapter A Flexible Learning System for Wrapping Tables and Lists in HTML Documents[END_REF][START_REF] Hsu | Generating finite-state transducers for semi-structured data extraction from the web[END_REF][START_REF] Kushmerick | Wrapper Induction for Information Extraction[END_REF][START_REF] Muslea | Active learning with strong and weak views: a case study on wrapper induction[END_REF][START_REF] Raeymaekers | Learning (k,l)-contextual tree languages for information extraction[END_REF][START_REF] Thomas | Bottom-up learning of logic programs for information extraction from hypertext documents[END_REF]. These systems are limited so far to simple Web pages containing lists of results à la Google or tables.

But data organizations in tree structured documents may be intricate. For instance, let us consider as a running example a (part of a) page of the BEA Web site from www.bea.gov in Fig. 1. The corresponding HTML tree is given in Fig. 2. Let us consider the target relation (Country, Year, Exports, Balance). The tuples (France, 1986, 10.130, 7.119) and (France, 1987, 11.701, 7.947) are intertwined in the HTML tree. Thus extracting tuples in the document order should fail. Also it could be noted that values for the component Country are factorized over several tuples.

Our objective is a friendly system for extracting tuples from XML or XHTML documents whatever the structure used to store tuples is. We follow the wrapper induction approach which is licensed because the generation process implies regularities of semi-structured data. We first study, in Section 2, different ways to encode n-ary relations in XML, that is the manner to store tuples in XML trees. We define five base cases: lists, tables, rotated tables, nested tables and cross tables. Related work is described in Section 3. It is shown that existing systems for extracting tuples from Web documents only deal with lists and tables. Other systems 2. Writing such a post processing procedure is not easy for an end-user. Moreover, writing by hand such a procedure is in conflict with the example-based approach.

Thus a machine learning approach for extracting tuples should allow to extract tuples for all data organizations. The number of tuples in a tree is exponential in the length of tuples. Therefore, direct approaches fail and we propose a system based on two main ideas. It is incremental: partial tuples are extracted by increasing length. It is based on a representation-enrichment procedure: partial tuples of length i are encoded with the knowledge of extracted tuples of length i -1. In Section 4, we present the extraction algorithm. At each step of the incremental process, a binary classification procedure is used. The attribute-value representation schemas use both the DOM view (tree structure) and the yield view (textual contents) of XML data. The induction procedure from completely annotated documents, in which all tuples to be extracted are annotated, is given in Section 5. At each step i of the incremental process, a classifier is learned from examples. Positive examples are encodings of partial tuples which are projections of tuples to be extracted. Negative examples are encodings of partial tuples not to be extracted while the i -1-th partial tuple is to be extracted. This ensures that the number of examples is linear in the number of annotated tuples.

The system suffers of one main flaw: completely annotated examples are required. As our objective is to build a friendly end-user system for wrapper generation with machine learning techniques, it is mandatory to be able to build accurate wrappers in a minimal amount of time. In Section 6, we integrate our approach in an interactive framework in order to reduce the number of user actions. This implies to modify the algorithms to learn from partially annotated examples, in which some tuples to be extracted are annotated as positive examples and some tuples not to be extracted are annotated as negative.

In Section 7, we present experimental results of our prototype. It has been evaluated on standard RISE [START_REF]Rise, a repository of online information sources used in information extraction tasks[END_REF] data sets and corporate Web sites in the domains of statistics, meteorology and economics. These data sets cover the simplest organizations (lists and tables) and more complex ones (rotated tables, nested tables and cross tables). First, we consider the case of completely annotated examples. Our system achieves excellent results without any postprocessing. On simple datasets it reaches state-of-the-art results and it succeeds on intricate ones where other systems fail. Second, we study the behaviour of our algorithm in an interactive framework. We show that this interactive approach significantly improves the time needed to build wrappers when the number of tuples in each document is large. It also reduces the quantity of information provided by the user to define accurate wrappers.

Tuples in XML data

We discuss how tuples can be embedded in XML data. Our case study was done for XHTML data from different Web sites. We present the five base cases:

Case 1. Tuples can be stored consecutively in the same order. For instance consider a list of search results like Google or eBay. Tuples do not overlap in the XHTML document. Two cases should be distinguished. In the first one, the tree structure of the XHTML document is poor and the problem is equivalent to a problem for sequences. In the second one, the list constructor of XHTML is used. In this case, each tuple is in a different item. The case of nested lists is quite similar to the case of tables we present now.

Case 2. A second structure is a table with component names in the first row and data in the following rows 3 3 . Tuples again do not overlap in the XHTML document. In the DOM view the least common ancestors of each tuple are distinct. So it is easy to distinguish between tuples using the tree structure or the XHTML tags in the document. Nested lists lead to similar properties.

Case 3. For relations with more components than data instances, the previous organization is often rotated. Slot names are in the first column and data are in the following columns 4 . Another example is given by the tables from www.bea.gov in Fig. 1 Case 4. A nested structure is used to avoid repetitions and to shorten the data presentation. This is common when issued from reporting tools. Consider for instance the address report from JASPERREPORTS 5 where the city name is factorized among several citizens records. Another example is given by the tables from www.bea.gov in Fig. 1 for Cross-tables are used to present multidimensional relations. This is frequent for statistics and reports. This case shares properties with the two preceding cases: a subset of the component values are stored as in the case 3 but the rest is stored according to case 4. An example from BLS www.bls.gov is given in Fig. 3. The DOM tree is given in Fig. 4. Let us consider for instance the target relation (Year, Quarter, Unit Labor Costs). Examples of tuples are (1992, Qtr1, 0.3) and (1993, Qtr3, 1.0).

For the two first cases, tuples are stored consecutively while, for the three last cases, tuples are intertwined both in the sequential view and in the DOM view. For the three last cases, it is necessary to count in order to construct tuples because component values occur at the same position in different subtrees. It should be noted that variants are frequent in XML or XHTML data. They consist in mixing several possible layouts, merging some leaves of the tree or placing several relations in the same structure. Also, building tuples can be more intricate when there are missing values. The supervised wrapper induction problem has been addressed by many authors. Several systems have emerged from this active research field, working from manually annotated documents. Let us cite WIEN [START_REF] Kushmerick | Wrapper Induction for Information Extraction[END_REF], SOFT MEALY [START_REF] Hsu | Generating finite-state transducers for semi-structured data extraction from the web[END_REF], BWI [START_REF] Freitag | Boosted wrapper induction[END_REF], STALKER [START_REF] Muslea | Active learning with strong and weak views: a case study on wrapper induction[END_REF], SQUIRREL [START_REF] Carme | Interactive learning of node selecting tree transducer[END_REF], among others. They achieve very good performance on unary extraction tasks. Wrapper induction approaches for n-ary tuples extraction include Kushmerick seminal works [START_REF] Kushmerick | Wrapper Induction for Information Extraction[END_REF] with LR wrappers and transducers induction in [START_REF] Hsu | Generating finite-state transducers for semi-structured data extraction from the web[END_REF]. More recently Thomas proposes an approach based on Inductive Logic Programming [START_REF] Thomas | Bottom-up learning of logic programs for information extraction from hypertext documents[END_REF]. These systems are designed for HTML documents generated from a back-end database, such as commercial sites and online shops. For instance, LR wrappers work when tuples are stored consecutively in the sequential view of HTML documents. Thus, to the best of our knowledge, wrapper induction systems for n-ary relations are able to deal with the most simple cases: lists, nested lists and tables.

For n-ary extraction, it is often argued that a postprocessing that builds tuples from components extracted by n unary wrappers is sufficient to solve the n-ary extraction problem. Indeed, this post processing is easy for cases 1 or 2 when there are no missing values. With missing values, user interactions are required to label data or to correctly re-associate tuple components [START_REF] Cohen | Web Document Analysis: Challenges and Opportunities, chapter A Flexible Learning System for Wrapping Tables and Lists in HTML Documents[END_REF][START_REF] Jensen | Grouping extracted fields[END_REF]. We argue that this is unsatisfactory for at least two reasons. First, we have shown in the introduction that, even with perfect unary wrappers, the post-processing procedure may be complex. Second, learning-based solutions have been promoted to avoid writing wrappers by hand. Thus it is not fair to ask the end user to write programs for constructing tuples from the outputs of several unary wrappers.

The unsupervised approach is automatically trying to avoid manual labeling. Unsupervised learning methods are based on document alignment [START_REF] Arasu | Extracting structured data from web pages[END_REF][START_REF] Chang | IEPAD: Information extraction based on pattern discovery[END_REF][START_REF] Lerman | Automatic data extraction from lists and tables in web sources[END_REF][START_REF] Zhai | Web data extraction based on partial tree alignment[END_REF] or grammatical inference techniques [START_REF] Crescenzi | Roadrunner: Towards automatic data extraction from large web sites[END_REF]. However, as indicated by Zhai and Liu in [START_REF] Zhai | Extracting web data using instancebased learning[END_REF], these automatic methods are less accurate than the systems that ask the user to label training pages. Manual post-processing is needed for the user to identify what he/she is interested in. For instance, consider the tables from www.bea.gov in Fig. 1, the system presented in [START_REF] Zhai | Web data extraction based on partial tree alignment[END_REF] identifies the two data regions corresponding to the two tables. But if we consider the target relation (Country, Year, Exports, Balance), the problem of extracting tuples is still present. Moreover, in case 4, factorized values may not be found by an unsupervised system. Therefore, extracting tuples of records from the output of automatic systems can be as difficult as wrapping original documents. Nevertheless, automatic systems could be a useful preprocessing for large documents with few data records in order to identify the data regions.

To sum-up, existing systems based on machine learning techniques solve simple data organizations (Cases 1 and 2), but fail on complex data organizations (Cases 3-5).

The extraction process

We present the incremental extraction procedure which is based on data enrichment. The first component of the target n-ary relation is called the seed. The seed extraction is cast as a binary classification problem, which consists in deciding whether a leaf is to be extracted or not. Figure 5 briefly describes the 56 attributes used by rep 1 to encode a leaf. The reader should note that attributes are defined from several views over XML or XHTML documents: nodes properties over the DOM view; textual values over the yield view which is the concatenation of text leaves' contents obtained with a depth-first left-right exploration of the DOM view.

Extraction of partial tuples of length i (i = 1) is cast as a binary classification problem, which consists in deciding whether a tuple of length i should be extracted or not. Tuples of length i are encoded in an attribute-value representation denoted by rep i . Let us consider a tuple (l 0 , . . . , l i-1 , l i ), rep i includes an encoding of dependencies between l i and the partial tuple (l 0 , . . . , l i-1 ). For encoding dependencies, we use node couples attributes which are presented in Fig. 6. Again node couples attributes are defined over the DOM view and the yield view. In order to have a fixed number of attributes whatever the length of the partial tuple is, rep i encodes a partial tuple (l 0 , . . . , l i-1 , l i ) by the leaf representation of l i , node couples attributes for node couples attributes: for a pair of nodes (p, m) attributes are: attributes for the node representation of the nearest common ancestor a between p and m; the length of the shortest path between p and a, between p and m and between a and m in the DOM view and in the binary tree encoding of the DOM view; the number of textual leaves between p and m in the yield view; and for each 1 ≤ k ≤ 5; the difference between the position of the k th ancestor of p and of the k th ancestor of m in their father's children sequence. There are 21 attributes for each pair of nodes.

Figure 6. Attributes for pairs of nodes

the pair (l 0 , l i ) (dependency with the seed) and node couples attributes for the pair (l i-1 , l i ) (dependency with the previous component). There are 98 attributes for a tuple representation and they are all independent of i.

The extraction algorithm for a target n-ary relation is the algorithm 1. It takes as input a document d and n classifiers c 1 , . . . , c n according to the representation schemas rep 1 , . . . , rep n . First, tuples of length 1 are extracted. Then, for each i, in line 4 a set S i of candidate tuples to be extracted is defined by adding a leaf to every extracted tuple of length i -1. Tuples of length i are extracted in line 5: the representation procedure rep i issues a record; records are then given to a classification procedure c i that labels each of them as positive or negative. Every tuple of length i classified as positive is extracted. This allows us to handle factorized values. Indeed, when one of the i -1 components is a factorized values, several tuples of length i, constructed with the same tuple t i-1 of length i-1, must be extracted. Line 6 allows us to handle missing values. When no tuple t i , constructed from some t i-1 , is extracted, then the component i is assumed to be missing, and the tuple

(t i-1 , null) is extracted.
The complexity of algorithm 1 depends on the complexity of computing rep i for candidate partial tuples at each step i. The computation of tuple representations is efficient. Indeed, leaf and node attributes are computed while reading the input document. Couple nodes attributes must be computed at each step of the incremental extraction process. They are computed only from extracted tuples at the previous step. Calculating node couples attributes involves finding the nearest common ancestor of a pair of nodes. This can be done in constant time after a linear preprocessing of the input tree structured document [START_REF] Harel | Fast algorithms for finding nearest common ancestors[END_REF]. It should also be noted that a classifier c i may only use a subset of attributes reducing the computation time for the extraction process.

S 1 = {(l) | l ∈ L(d)}; 2: S + 1 = {t 1 ∈ S 1 | c 1 (rep 1 (t 1 )) = +1} 3: for i = 2 to n do 4: S i = {t i = (t i-1 , l) | t i-1 ∈ S + i-1 , l ∈ L(d)} 5: S + i = {t i ∈ S i | c i (rep i (t i )) = +1}
6:

S + i = S + i ∪ {(t i-1 , null) | t i-1 ∈ S + i-1 , ∀l ∈ L(d), c i (rep i ((t i , l))) = -

Interactive wrapper induction system

Algorithm 2 suffers from one main flaw: it requires a set of documents where all tuples to extract are annotated. In this section, we propose to adapt this algorithm for learning from partially annotated examples in order to plug it in an interactive system. The aim is to reduce the number of user interactions to build n-ary wrappers.

In an interactive process, an end user first labels some examples to extract. Then we enter a loop where the system

S + i = ∪ d∈D S + i (d)
3:

S - i = ∪ d∈D Neg(d, S + i (d))
4:

c i = W (rep i (S + i ), rep i (S - i )) 5: end for Output: the sequence (c 1 , . . . , c n ) of classifiers
proposes a new hypothesis wrapper and the user corrects this hypothesis until a good one is built. We have integrated the interactive process in the wrapper induction system following the incremental approach developed so far: for every i, wrappers for partial tuples are constructed in an interactive process.

We simulate an end user by an oracle U . The oracle U is given access to a pool of documents. Given as input a hypothesis wrapper w i = (c 1 , . . . , c i ) where each c j is a classifier for partial tuples of length j, the oracle U (w i ) returns true if w i is correct and returns new annotations otherwise. We suppose a working document dc and that U returns new annotations according to the following scenario. If U (w i ) does not return true and if w i is not correct on dc, U returns a false negative example (a tuple not extracted by w i while it should be extracted) and a false positive example (a tuple extracted by w i while it should not be extracted) from dc. We should note that a false positive or a false negative may not exist. If U (w i ) does not return true and w i is correct on dc, then U returns a new document with two partial tuples of length i to be extracted.

The interactive wrapper induction system is the algorithm 3. It iterates over the length of partial tuples. At each step i, it learns from a set of completely annotated documents D i and a current working document dc, which is partially annotated. In the working document dc, S + i (dc) (respectively S - i (dc)) denotes the set of partial tuples of length i to be extracted (respectively tuples not to be extracted) given by the oracle U .

When U returns a new document, it is supposed, according to the above scenario, that the current wrapper is correct over dc. Then, we add dc to the set of completely annotated documents and the new working document is the document returned by U .

The sets S + i (dc) and S - i (dc) are updated according to the annotations given by U .

Positive examples are partial tuples of length i to be extracted in the documents of D i and in the set S +

while not U (c 1 , . . . , c i ) do 6: if d(U (c 1 , . . . , c i )) = dc then 7:
{a new document to be processed} 8:

D i = D i ∪ {dc} {dc is completely annotated} 9: dc = d(U (c 1 , . . . , c i )); S + i (dc) = S - i (dc) = ∅ 10:
end if 11:

S + i (dc) = S + i (dc) ∪ d + (U (c 1 , . . . , c i ))
12:

S - i (dc) = S - i (dc) ∪ d -(U (c 1 , . . . , c i ))
13:

S + i = (∪ d∈Di S + i (d)) ∪ S + i (dc)
14:

S - i = ( ∪ d∈Di Neg(d, S + i (d))) ∪ Negp(i, dc, S + i (dc), S - i (dc))
15:

c i = W (rep i (S + i ), rep i (S - i )) 16:
end while 17: end for Output: the sequence

(c 1 , . . . , c n ) of classifiers rithm 2.
Negative examples for dc should be carefully defined because dc is partially annotated. For instance, let us consider the case i = 1, that is the induction of the wrapper for the seed. In the first interaction: there are only two positive examples available for learning. Thus we have to guess negative examples. The function Neg, used in the case of completely annotated documents, would give us all leaves in the current document which are not explicitly labeled as positive and the classifier learned would classify positive only leaves which are already known as positive!

To compute negative examples in the working document dc, we define the function Negp. It takes as input the index i, the working document dc, and the sets S + i (dc) and S - i (dc). When i = 1, it returns all leaves in S - 1 (dc) together with all leaves whose path in the DOM tree is not the path of any leaf in S + 1 (dc). When i > 1, two cases are to be distinguished: the first i -1 components may be factorized or not other several tuples of length i. In the first case, several tuples of length i are constructed over the same partial tuple of length i -1. The function Neg would generate false negative examples. Thus we need to guess which leaves may be good candidates to complete an (i -1)-ary tuple. Therefore, Negp returns all partial tuples of length i in S - i (dc) together with all partial tuples of length i such that the partial tuple of length i -1 is in S + i-1 and the path of the i th component is not the path of any i th component in S + i (dc). In the second case, Negp returns all partial tuples of length i in S - i (dc) together with Neg(dc, S + (dc)). Then the set of negative examples is computed in Line 14.

A classifier c i is induced with the base supervised learning algorithm W updating the current partial wrapper w i = (c 1 , . . . , c i ). And the process iterates over calls to U and over i when U agrees with the current partial wrapper.

Experimental results

Evaluation Protocol An extracted tuple is correct if all its component values are correct. A component value is correct if it matches exactly the target component value. Performance of our wrapper induction system is evaluated using the average of precision (P ), recall (R) and f-measure (F ). They are computed with cross-validation techniques. In all experiments, the base learner for binary classifiers is Quinlan's C5.0 [START_REF] Quinlan | Data mining tools see5 and c5.0[END_REF].

Experiments on RISE datasets

Data sets in RISE correspond to the first two cases according to Section 2. Table 1 presents the experimental results where TD is the average number of tuples per document, and D is the number of documents used in the induction process. In this section and in the next section as well, at most two documents are given to the learner.

On BIGBOOK, OKRA and S20, Algorithm 2 obtain 100 of f-measure. For the problem S1 with the target relation (company, price, product), WIEN achieves 100 of f-measure while our system does not achieve 100 of f-measure because parts of textual values in leaves are needed for correct extraction. In the IAF dataset, with the target relation (name, email, lastupdate, organization, altname, serviceprovider), three of the six components of the target relation have missing values. Our system outperforms LIPX [START_REF] Thomas | Bottom-up learning of logic programs for information extraction from hypertext documents[END_REF] (which has 46 of f-measure) and WIEN which fails because it can not deal with missing values. On n-ary extraction tasks, we can not compare with systems like STALKER because it uses n unary wrappers and does not evaluate on tuples recombination. Further more it uses a post-processing, defined by the end-user, to construct tuples from component values. On unary extraction tasks, our system reaches the performances of STALKER (except on S1 as mentioned before). In particular on IAF, the f-measure of our system varies from 84 to 100, whereas it obtains 64 in the n-ary case. Indeed on IAF tuples recombination is more difficult than components extraction.

Experiments on Web datasets

We now consider datasets 6 obtained from several corporate Web sites. They were chosen to be representative of the tree organizations presented in Section 2. For the EXCITE 1 dataset, the relation to extract is (town, day, weather, high, low). There are five tuples, the component town is factorized while the others are stored in a rotated table. In BBC, the relation to extract is (town, day, high, low). The component town is factorized and the others are stored in a table. There are several datasets built from BLS with a target 3-ary relation. In BLS 1, BLS 2 and BLS 4, tuples are stored in a cross table, while in BLS 3 they are stored in a rotated table. In the BEA 1 benchmark (see Fig. 1), the target relation is the 4-ary relation (balance,year,country,export). For each document of BEA 1, there are six tuples to extract. The component country is factorized among the six tuples. The other components are stored in a rotated table. In the BEA 2 benchmark, the target relation is the 3-ary relation (year,balance,export) stored in a rotated table. In the rotated table of BTS, the relation to extract is (year,highway,oil).

Experimental results are presented in Table 2. They show that Algorithm 2 succeeds with one or two completely annotated Web pages. Two pages were needed when there are large variations in the size of the tables and in the number of tuples to be extracted from one page to another.

Experiments in the interactive system

We consider the interactive wrapper induction algorithm of Section 6 with its user simulator U . We compare the number of interactions in the completely annotated case and in the interactive framework. We denote by #F the number of interactions performed by the user with algorithm 2. It is defined to be n × m where m is the number of annotated tuples and n is the arity of tuples. In the interactive system, we denote by #I the number of component values selected or unselected by the user U , and we denote by #P the number of interactions performed by the user U . The selection of an example requires one interaction for the seed and two interactions for a partial tuple of length i (the tuple of length i -1 and the i th component value). Thus a correction requires: 1 or 2 interactions for the seed; 2 or 4 interactions for the next steps.

We present in table 3 the number of interactions required in the two scenarios to achieve perfect wrappers on corporate Web sites. The number #I of examples selected or unselected by the user in the interactive framework is smaller than the number #F of interactions for a complete annotation. The number of interactions #P in the interactive framework is smaller than #F on datasets with many tuples per document. For benchmarks with few tuples to extract per document, like BLS 2, #P can be greater than #F because negative examples must be selected and because many partial tuples must be selected per tuple to be extracted.

We made experiments where the components are taken in different orders and we do not notice significant variations of the performances.

Conclusion

We have presented a machine learning approach for n-ary relation extraction from semi-structured documents. Our algorithm combines the advantage that component extraction and tuples construction are made simultaneously in the wrapping procedure and in the induction process, without any post-processing.

The effectiveness of our approach is evident with completely annotated documents: we achieve state-of-the-art results on simple data organizations and also succeeds on intricate organizations like pivot table, rotated table and cross table where previous systems fail. Extraction and learning are fast. Furthermore, we have proposed an interactive framework in order to reduce the number of user actions and shown that our method is again improved: we are able to learn equally performant wrappers, with less effort for the user.

Figure 1 .

 1 Figure 1. Part of a sample page of BEA web site. html body h2 France

Figure 2 .

 2 Figure 2. Simplified HTML tree for a page of the BEA Web site (Fig. 1). It corresponds to rotated tables with pivot values

  for the target relation (Year, Exports, Balance) for France. It is shown in Fig. 2 that tuples (1986, 10.130,7.119) and (1987, 11.701, 7.947) are intertwined. It should also be noted that different components of a tuple occur at the same position in the DOM tree. For instance, 1987, 11.701 and 7.947 are below the third td of the tr tags of the table.

Figure 3 .

 3 Figure 3. Part of a sample page of BLS web site.

Figure 4 .

 4 Figure 4. Tree organization for a cross-table from BLS Web site presented in Fig. 3 restricted to the three first quarters.

  Node representation label, position in father's children sequence, depth and height, number of children, size of the subtree under the node, the label of its previous and next siblings, the value of the class XHTML attribute. There are 9 attributes. Leaf representation node representation of the leaf plus node representation of its 5 ancestors in the DOM view plus the previous and next leaves' contents (without tokenisation) in the yield view. There are 56 attributes.

Figure 5 .

 5 Figure 5. Attributes for leaf representation.

1} 7 : 5

 75 end for Output: the set of extracted n-ary tuples S + n The induction process Let us consider a target n-ary relation. The learning process is incremental similarly to the extraction process. Given a set D of completely annotated documents, algorithm 2 loops from 1 to the number n of components. At each step i, it computes a classifier c i for tuples of length i. The number of positive examples is bounded by the number of tuples in ∪ d∈S S + (d), that is the number of tuples to be extracted in D. On the opposite, the number of negative examples can be exponential in n. So we only use a subset of negative examples to train each classifier c i . The selection of negative examples is driven by the schema of the extraction process as well: at each step i of the process, candidate tuples are built from positive examples of step i -1. Negative examples are computed by the function Neg taking as input a document d in D and a set of tuples to be extracted from d. It is defined by: Neg(d, S) = {(x, l) ∈ S|l ∈ L(d), ∃l ∈ L(d)|(x, l ) ∈ S} where L(d) is the set of leaves of the document d. Then, examples are represented via rep i and the base supervised classification algorithm W is applied. Algorithm 2 outputs a sequence of classifiers. This sequence will be the input of algorithm 1 for the extraction process.

Algorithm 2

 2 Induction algorithm Input: a sample D = ∪{d} of annotated documents Notation: S + (d) is the set of tuples to be extracted in d; S + i (d) is the projection of S + (d) over the first i components 1: for i = 1 to n do 2:

  i (dc). Negative examples for completely annotated documents in D i are defined according to function Neg as in Algo-Algorithm 3 interactive wrapper induction system Notation: an oracle U is an end user simulator; d(U (c 1 , . . . , c i )) is the document returned by U ; d + (U (c 1 , . . . , c i )) is the set of tuples to be extracted returned by U ; d -(U (c 1 , . . . , c i )) is the set of tuples not to be extracted returned by U ; 1: for i = 1 to n do 2: D i = ∅ {set of completely annotated documents} 3: c i = null {classifier} 4: dc = null {current working document} 5:

  6 http://www.grappa.univ-lille3.fr/ marty/corpus.html Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2006 Main Conference Proceedings)(WI'06) 0-7695-2747-7/06 $20.00 © 2006

Algorithm 1

 1 Extraction algorithm Input: document d; n classifiers c 1 , . . . , c n according to representation schemas rep 1 , . . . , rep n Notation: L(d) is the set of leaves of d, S i is the set of candidate partial tuples of length i, S + i is the set of selected partial tuples of length i.

1:

Table 1 . Experimental results on RISE datasets.

 1

	Corpus	TD		D	P	R	F
	BIGBOOK	18.29	1	100	100	100
	OKRA	13,23	1	100	100	100
	S20	32.7		1	100	100	100
	S1	40.3		1	88.65	88.57	88.61
	IAF	9		2	61.51	67.66	64.22
	Corpus	Case	TD	D	P	R	F
	EXCITE 1	3,4	5	1	100	100	100
	BBC	2,4	5	1	100	100	100
	BLS 1	3	29	1	100	100	100
	BLS 2	5	3.56	1	100	100	100
	BLS 3	3	6	1	100	100	100
	BLS 4	5	24	2	100	90	93.33
	BEA 1	4,3	8.30	2	97.11	88.58	92.58
	BEA 2	3	5.2	2	86.47	100	89.78
	BTS	3	20	1	100	100	100

Table 2 . Experiments on corporate Web sites.

 2

Table 3 . Interactive experiments

 3

	Corpus	TD	# I	# P	# F
	EXCITE 1	5	13	25	25
	BBC	5	7	13	15
	BLS 1	29	25.8	32.40	87
	BLS 2	3.56	7.60	12.20	10.68
	BLS 3	6	13.60	21.60	18
	BLS 4	24	16.40	30.20	288
	BEA 1	8.30	32	56.40	66.40
	BEA 2	5.2	9.4	15.20	31.2
	BTS	8.30	29	45.00	60

Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2006 Main Conference Proceedings)(WI'06) 0-7695-2747-7/06 $20.00 © 2006

see the table of market indices on quotes.nasdaq.com/aspx/ marketindices.aspx

see the table of http://www.bls.gov/eag/eag.IA.htm

jasperreports.sourceforge.net/samples/DataSourceReport.html

Related workWe relate to[START_REF] Laender | A brief survey of web data extraction tools[END_REF] for a survey on Web data extraction tools. Here we focus on wrapper induction tools for Web documents. We discuss the supervised and unsupervised approaches. Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2006 Main Conference Proceedings)(WI'06) 0-7695-2747-7/06 $20.00 © 2006