Estelle Delpech

Patrick Saint-Dizier

Investigating the Structure of Procedural Texts: identification of titles and instructions

This paper presents ongoing work dedicated to parsing the textual structure of procedural texts. We propose here a model for the intructional structure and criteria to identify its main components: titles, instructions, warnings and prerequisites. The main aim of this project, besides a contribution to text processing, is to be able to answer procedural questions (How-to? questions), where the answer is a well-formed portion of a text, not a small set of words as for factoid questions.

Résumé

Nous présentons ici un travail en cours dédié à l'analyse syntaxique et sémantique de la structure textuelle des textes procéduraux Nous proposons ici un modèle et des critères pour identifier les principaux composants de cette structure : titres, instructions, avertissements et pré-requis. L'objectif principal du projet, à côté d'une contribution à l'analyse textuelle est de permettre de répondre à des questions procédurales dans le cadre des systèmes question-réponses en Comment faire ? où la réponse est une portion bien formée de texte et non pas une information ponctuelle comme c'est le cas pour les questions factoïdes.

Mots-clés : syntaxe et sémantique textuelle, systèmes question-réponses.

Situation and Aims

The main goal of this work is to be able to answer procedural questions, which are questions whose induced response is typically a fragment, more or less large, of a procedure, i.e., a set of coherent instructions designed to reach a goal. Recent informal observations from queries to Web search engines show that procedural questions is the second largest set of queries after factoid questions [START_REF] De Rijke | Question Answering: What's Next[END_REF].

Answering procedural questions thus requires to be able to extract not simply a word in a text fragment, as for factoid questions, but a well-formed text structure which may be quite large. Analysing a procedural text requires a dedicated discourse analysis, e.g. by means of a grammar. Such grammars are not very common yet due to the complex intertwinning of lexical, syntactic, semantic and pragmatic factors they require to get a correct analysis. Discourse grammars have basically a top-down organization, they take discourse acts as their basic units, instead of just words, they account for the structure and for the interactions between these acts and they require a relatively elaborated conceptual representation as output. Such a grammar must capture the discourse cohesion, possibly the communicative intentions, as well as the discourse organization, e.g. in terms of plans.

Procedural texts are organized sets of instructions, they may also be sets of advices, as in social behavior texts. In our perspective, procedural texts range from apparently simple cooking recipes to large maintenance manuals. They also include documents as diverse as teaching texts, medical notices, social behavior recommendations, directions for use, assembly notices, do-it-yourself notices, itinerary guides, advice texts, savoir-faire guides etc. Even if procedural texts adhere more or less to a number of structural criteria, which may depend on the author's writing abilities and on traditions associated with a given domain, we observed a very large variety of realisations, which makes identifying the structure of such texts quite challenging.

Procedural texts explain how to realize a certain goal by means of actions which may be temporally organized. Procedural texts can indeed be a simple, ordered list of instructions to reach a goal, but they can also be less linear, outlining different ways to realize something, with arguments, advices, conditions, hypothesis, preferences. They also often contain a number of recommendations, warnings, and comments of various sorts.The organization of a procedural text is in general made visible by means of linguistic and typographic marks. Another feature is that procedural texts tend to minimize the distance between language and action. Plans to realize a goal are made as immediate and explicit as necessary, the objective being to reduce the inferences that the user will have to make before acting. Texts are thus oriented towards action, they therefore combine instructions with icons, images, graphics, summaries, preventions, advices, etc.

Research on procedural texts was initiated by works in psychology, cognitive ergonomics, and didactics. Several facets, such as temporal and argumentative structures have then been subject to general purpose investigations in linguistics, but they need to be customized to this type of text. There is however very little work done in Computational Linguistics circles. The present work is based on a preliminary experiment we carried out (Delpech et ali. 07), [START_REF] Aouladomar | An Exploration of the Diversity of Natural Argumentation in Instructional Texts, 5th International Workshop on Computational Models of Natural Argument[END_REF] where a preliminary structure was proposed. From a methodological point of view, our approach is based on (1) a conceptual and linguistic analysis of the notion of procedure and (2) a mainly manual corpus-based analysis, whose aim is to validate and enrich the former.

In this short paper, we summarize our results, focussing (1) on the conceptual notion of intructional compounds, which does capture the complexity just advocated, and (2) on the recognition of titles, instructions and instructional compounds. An quite comprehensive evaluation was carried out that we breifly report here. This work is part of the ANR TextCoop project.

The structure of procedural texts: Instructional Compounds

Procedural texts contain two basic structures: titles, analyzed as goals (with which questions will match), and instructions serving these goals. However, in most types of texts, we do not have just sequences of simple instructions but much more complex compounds. We noted that these compounds are organized around a few main instructions, to which a number of subordinate instructions, warnings, arguments, and explanations of various sorts are adjoined. Procedural texts also contain general purpose prerequisites and warnings, besides those included into instructional compounds.

Let us essentially, in this contribution, focus on the instructional compound structure, which is, by far, the most complex element. It has a relatively well organized discourse structure, composed of several layers, which are:

-The justification and explanation structure, which has wider scope over the remainder of the compound, indicates motivations for doing actions that follow in the compound (e.g. in your bedroom, you must clean regularly the curtains..., which here motivates actions to undertake). It may also indicate the goal of the instructions that follow. It may play a role quite close to the causal structure described below.

-The instruction kernel structure, which contains the main instructions. These can be organized temporally or just be sets of actions. Actions are identified most frequently via the presence of action verbs (in relation to the domain) in the imperative form, or in the infinitive form introduced by a modal. We observed also a number of forms of subordinated instructions adjoined to the main instructions. These are in general organized within the compound by means of rhetorical relations, that we introduce below.

-The deontic and illocutionary force structures: consist of marks that operate over instructions, outling two different parameters: (1) deontic: obligatory, optional, forbidden or impossible, alternates (or), (2) illocutionary and related aspects: stresses on actions: necessary, advised, recommended, to be avoided, etc.

-A causal structure that indicates, within the compound the use or the motivation of an instruction. We identify several types of causes, such as: intend-to (push the button to start the engine), instrumented (use a 12 inch ket to dismount the equipment), facilitation and continue (keep the liquid warm till its color changes).

-The conditional structure: introduces conditions over instructions within the compound or even over the whole instructional compound. Some conditions may have the form of case structures, based on exclusive conditions (as in programming languages). Some conditions also introduce possible actions (if you are an expert, ...) -The rhetorical structure whose goal is to enrich the kernel structure by means of a number of subordinated aspects (realized as propositions, possibly instructions) among which, most notably: enablement, motivation, argument for, circumstance, elaboration, instrument, precaution, manner. The rhetorical structure is in general composed of instructions (satellites) related to the instructions in the kernel. A specific structure, of much importance is the argumentative structure, where arguments are given to motivate the user (prevention, threats, rewards, etc. [START_REF] Aouladomar | An Exploration of the Diversity of Natural Argumentation in Instructional Texts, 5th International Workshop on Computational Models of Natural Argument[END_REF] Let us now give an illustrative example, extracted from the 'Do-It-Yourself Home' domain:

In a bedroom, it is necessary to clean curtains. These are cleaned first with a vacuum-cleaner to remove dust, then, if they are in cotton, they can be washed in the washing machine at 60 degrees; if they are white, it is even recommended to add some bleech so that they look whiter. With some starch, they can be easily ironed.

In this text, the sequence: In the bedroom, it is necessary to clean curtains is analyzed as a justification of the actions to undertake. The next portion: These are cleaned first with a vacuum-cleaner to remove dust, then, if they are in cotton, they can be washed in the washing machine at 60 degrees. is the instruction kernel, where the last instruction is associated with a condition. Finally, If they are white, it is even recommended to add some bleech so that they look whiter. With some starch, they can be easily ironed. are two subordinated clauses, analyzed as advices.

Here is another example, in French, using the bracketed notation to indicate relative scope of elements: [instruction aspirez la couleur avec un chiffon sec en tissus éponge.

[facilitation [instruction Vous devez déborder un peu de la zone à préserver:

[explication la couleur peut passer sous le chiffon par capillarité ]]]]].

In this example, a condition has wider scope over the whole instructional compound. The kernel is composed of a single instruction, modified by a subordinate instruction (a facilitation in rhetorical terms), itself modified by an explanation (which is not an instruction).

Recognizing Titles, Instructions and Instructional Compounds

Let us now develop in more depth the different phases of our system. Prelimany steps include cleaning and labelling text objects. Then title and instructions can be recognized.

Cleaning Web texts and tagging

The input of our system are raw Web pages. From these pages, we need (1) to extract relevant text, that is, any kind of text that is not navigation help, advertisements or comments posted by cybernauts (2) to select and simplify the html tags so as to keep the main typodispositional information (paragraph breaks, subdivisions of paragraphs into lines, lists and their subdivision into elements, emphasis). Although (2) was quite an easy task, we had some difficulties achieving (1). We designed an algorithm that returns, foreach paragraph, if its text can be considered relevant or not. It mainly uses paragraph length and proportion of closeclass words criteria. We evaluated it on 100 Web pages, coming from 12 different web sites. The results were : 0,95 precision and 0,76 recall. This cleaning process is not maintained in our implementation. We evaluate the recognition of titles and instruction on a hand-cleaned corpus. Although the results seem good at first sight, one has to keep in mind that it is a preliminary step. Yielding a 0,76 recall means that only three fourths of relevant text is kept, which we consider too low for a pre-processing step. This part of the project will be udertaken by our industrial parners.

The next stage is to tag the different lexical objects of the text, so that the segmentation of titles and instructions can be done properly. For that purpose, we use the Treetagger, that labels all the objects (syntactic category, morphological features). We also add some semantic considerations about action verbs. Of particular interest to us is the recognition of verbs, some nouns and adjectives, modals and connectors of various kinds.

Recognizing Titles

For answering How-to questions it is obviously of much importance to recognize titles and possibly hierarchies of titles in complex texts. A first observation is that html encodings are, by far, not homogeneous. Titles are coded with the tag <hi> in only 20% of the cases over the 600 titles observed. In most cases the tag  is used, possibly also <emp>,  and a few others (macros...). Encodings may be quite homogeneous within a given web site, but heterogeneity prevails over different sites, even in the same domain.

We identify titles in two steps. First, the algorithm processes the paragraphs of the text one by one, and give them one of these tags : title, text or ambiguous. This first step processes easy cases. For example, an easy case for a title is a paragraph composed of a unique sequence of JADT 2008 : 9 es Journées internationales d'Analyse statistique des Données Textuelles words, less than 12 words long and bearing emphasis. The tag text will be given without doubt if the paragaph is subdivided into smaller units or is longer than 12 words. Ambiguous parapraphs are mainly short sequences of words (12 words or less) with no emphasis.

The second step desambiguates the ambiguous paragraphs one by one, using the tags given by the first step to its surrounding paragraphs. For example, an ambiguous paragraph between two paragraphs tagged as text will be considered a title. Similarly, an ambiguous paragraph followed by a title is labelled text. We have elaborated about 7 such rules that raises ambiguities. This second step also operates some repairs on the tags yielded by the first step. For example, any sequence marked title at the end of the text will be repaired as text. Each desambiguation/repair rule is applied sequentially and in a specific order to the list of tags.

The title hierarchy is very difficult to identify without content analysis. However, standard procedural texts are not very long and tend to be relatively linear. This means that, besides the page title, we observed in 80% of our texts not more than 2 levels of titles (exluding the main title). We observed two regular types of titles that can be correlated to some form of hierarchy. Type 1 is a title separated from its following paragraph by a
 tag. Type 2 is a title separated from its following paragraph by a
 tag. Although we still have no means to tell the exact level titles, we can quite confidently say that a type 2 title will be at a lower level than a type 1 title, whatever the website or the domain. This information may be useful for question-title matching : type 2 titles are expected to introduce paragraphs that deal with more specific aspects of the procedure than paragraphs introduced by a type 1 title. Type 2 titles could help answering specific questions. One remaining difficulty for question-title matching is that titles have often a very elliptic structure.

Recognizing instructions and instructional compounds

While working on corpora, we noted that what is usally called an instruction ranges from clearly injonctive clauses to implicit prescriptions (this complexity is reflected in the complexity of manual annotation tasks, see below). Instructions are recognized on the basis of two factors: contents, around action verbs in certain forms to identify an instruction and typographic factors for its delimitation (beginning and end) via html tags, punctuation marks or connectors. Currently, we use a set of only 14 lexico-morphological patterns, that encompass the most prototypical ways of expressing instructions. We use lexical ressources such as action verbs, incentive verbs, nouns and adjectives.. They must have in French specific forms: imperative, infinitive, modal + infinitive, dummy pronoun 'on' + finite verb (this pattern has a semantic restriction: only action verbs are allowed) , middle reflexive constructions, and gerundive forms. The frequency usage of each of these forms largely varies across domains (e.g. coocking recipes mainly use imperative while video game solutions make high usage of the dummy pronouns 'on' or even of finite forms in the first person singular). The recognizer (also called the segmenter) includes 14 morphosyntactic generic patterns. The segmenter is implemented in standard Perl. Note that English seems to have a simpler set of forms while Spanish has a lot of finite forms, making instructions slightly more difficult to recognize.

Instructional compounds are composed of instructions. They are delimited as follows: by means of typographic marks: ending of enumeration (e.g.
 sequences) or by 'strong' marks in long paragraphs. These marks are in general temporal (Two hours later,...), conditional expressions or goal expressions.

Evaluation

The evaluation we have carried out allows us to have an estimate of the overall quality and accuracy of the recognition mechanisms, outlining problems and gaps for future evolutions. From that point of view, it is an indicative evaluation.

Evaluation process and results

The first step was a manual annotation carried out by two independent annotators of 78 Web pages over 5 domains: coocking recipes, do it yourself, video game solutions, social life, and medical recommendations. This corresponds to 1641 instructions over 4560 sequences JADT 2008 : 9 es Journées internationales d'Analyse statistique des Données Textuelles
  <titre>Gâteau au chocolat gourmand</titre>
 <prerequis>
 <titre> Ingrédients</titre>

 150 g de chocolat noir

 75 g de beurre doux

 210 g de lait condensé
 ……….</prerequis>
Utilisé depuis la nuit des temps, le chocolat .... si vous souhaitez l'inclure dans la composition de votre oeuvre .

temps: 2 heures, assez facile.

<titre> la préparation :</titre>

 <compinstr> <instr> 1. Tapisser un petit moule rectangulaire de papier aluminium.</instr></compinstr>

<compinstr> <instr> 2.

A l'aide d'un couteau tranchant, concasser les amandes. </instr></compinstr>
 .... <compinstr> <instr> Dans une casserole à fond épais, placer le chocolat cassé en morceaux, le beurre, le lait et la cannelle.</instr> <instr> Chauffer doucement à feu doux pendant 3 à 4 minutes en remuant avec 1 cuillère en bois.</instr> <instr> Bien battre le mélange. <instr> Incorporer les amandes, les biscuits et les abricots en remuant bien. </instr> .... </compinstr> <compinstr> <instr> Au bout d'une heure, .... </instr> ...... </compinstr> .......
 potential instructions and 511 titles. The total number of words is 61159, this not very large, but we feel sufficient for an indicative evaluation, giving us directions to improve the system. Evaluators had to indicate whether a sequence is:

-a title, -an instruction, with the possibility to give certainty of judgement on 2 values.

The total work took about 15 hours of manual work. Decisions were quite often difficult to make for some types of texts where quite a lot of knowledge of the domain is required, as for video games. Kappa measures were carried out to evaluate agreement and give an indication of the complexity of the tasks. In terms of inter-annotator agreements, we got for instructions, per domain: coocking recipes (0.82), do it yourself (0.76), social life (0.71), video games (0.45) and medical recommendations (0.42). This gives an idea of the complexity of the task (and therefore modulates the results) and of the uncertainty of some measures. Then the two annotators had discussions (about 5 hours) to reach a consensus and propose a unique annotation for all files, and give again a degree of certainty.

The result was then compared to the annotations realized by the programme. These are summarized in the array below for instructions and titles. Our strategy was in general to favor precision over recall, since even if some instructions are not recognized here and there, the question-answering system can still respond accurately. We have not tried at this level to implement an efficient system, however, we can fully parse 50 Mo of web pages in 8.1 seconds, on a pentium3 3GhZ machine with 4 Go RAM. The first three domains give quite good results, while for the last two, results are less good. This is mainmly due to the fact that we designed patterns from prototypical procedural texts, like coocking recipes. Obviously texts like video game solutions have a more unexpected form that would require the development of specific patterns, a solution that we foresee.. As can be noted, title recognition gives sligthly better results.

Finally, for instructional compounds, for the three best domains, and with respect to the results obtained in each of these domains, we have the following results, based on a small corpus of data, due to the complexity of the manual analysis:

Discussion

A point which is worth noticing is that the identification of instructions can be a challenging task for humans too. Apart from domains which mainly use clearly injonctive patterns (cooking recipes, do-it-yourself), instructions can be expressed in a variety of means which are by far less straightforward than imperative or infinive forms. These ambiguous formulations are, for example, the use of passive voice (i), middle reflexives (ii), future tense (iii) :

(i)Les bonnes manières sont inculquées dès le plus jeune âge.

(ii)Les bonnes manières s'inculquent dès le plus jeune âge.

(iii)On inculquera les bonnes manières dès le plus jeune âge.1

In the context of a procedural text, a difficulty is that formulations may range from injunctive forms to more neutral statements (X is realized by doing...). Therefore, it is not trivial to identify instructions among other statements such as advices.

Even more ambiguous is the use of implicit/open-to-interpretation formulations such as : Le diagnostic de cancer de la prostate repose sur un examen histologique, préalable indispensable à toute décision de traitement. (~Prostatis cancer diagnosis is based on an histologic examination, which is preliminary to any treatment decision).

The kappa-coefficient and the degree of certainty give an insight about the more or less ambiguous nature of instructions. What is important to notice is that the results of the recognizer decreases quite proportionnally to the results of the worse annotator (evaluated against the common annotation) -except for the video games domain on which the recognizer performs relatively well despite the ambiguity of the instructions : This is the main explanation for the lower rates in the video games / medical notices / social life domains. For example, implicit/open-to-interpretation formulations account for 0,4 % of silence in medical notices.

Other causes of silence are, for instance, the taking into account of instructions that spread over several adjoining sequences (0,34% of video games silences ; 0,18% in medical notices): (seq1) Il vous suffit ensuite de créer ce sort :2 (seq2)

1. charme 1 pt 5 sec sur contact (seq3) 2. fortification magie 100 pts pour 20 sec sur soit Regarding titles, most errors are caused by short sequences bearing no emphasis which induce both noise and silence. In silence cases, these are just titles bearing no emphasis ; noise cases are small sequences such as picture caption or any short sequence between two long paragraphs of text mistakenly interpreted as a title.

A Few Perspectives

This work is still under research. However, the linguistic structure of texts and the methods to recognize titles, instructions and instructional compounds and the global text structure seem to be on the right track. We obviously need to deepen evaluation for compounds as well as for whole texts, but this is much more difficult due to the complexity of annotations.

To improve the domains with low level results, one direction would be to design dedicated recognizers, with specific patterns. Some more efforts are also necessary in large texts to identify title hierarchies. At the moment, we do not see any simple solution which does not involve pragmatic or domain factors. The last step of the project is to explore how How-to questions can match with titles (goals), and what kind of results must be returned to the user (the instructions below the title, more data containing prerequisites, several documents, etc.). This project being an ANR-RNTL project, the perspectives include the development of a industrial system and its integration into these partners systems.

  JADT 2008 : 9 es Journées internationales d'Analyse statistique des Données Textuelles [[Cond Si vous souhaitez préserver quelques blancs sur le papier, ]

Finally

  , a grammar, based on a simple transposition of a few Minimalist Theory principles allows us to bind all the parts of the text. The grammar runs in Prolog in our prototype. The output is an XML file that reflects the text structure. Here is an extract of what we get before the grammar application, where terminal elements are tagged:
  <titre>Gâteau au chocolat gourmand</titre>
 <prerequis>
 <titre> Ingrédients</titre>

 150 g de chocolat noir

 75 g de beurre doux

 210 g de lait condensé
 ……….</prerequis>
Utilisé depuis la nuit des temps, le chocolat .... si vous souhaitez l'inclure dans la composition de votre oeuvre .

temps: 2 heures, assez facile.

<titre> la préparation :</titre>

 <compinstr> <instr> 1. Tapisser un petit moule rectangulaire de papier aluminium.</instr></compinstr>

<compinstr> <instr> 2. A l'aide d'un couteau tranchant, concasser les amandes. </instr></compinstr>
 .... <compinstr> <instr> Dans une casserole à fond épais, placer le chocolat cassé en morceaux, le beurre, le lait et la cannelle.</instr> <instr> Chauffer doucement à feu doux pendant 3 à 4 minutes en remuant avec 1 cuillère en bois.</instr> <instr> Bien battre le mélange. <instr> Incorporer les amandes, les biscuits et les abricots en remuant bien. </instr> .... </compinstr> <compinstr> <instr> Au bout d'une heure, .... </instr> ...... </compinstr> .......

JADT 2008 : 9 es Journées internationales d'Analyse statistique des Données Textuelles

(i) Good manners are taught at an early age (ii) no middle-reflexive equivalence (ii) Good manners will be taught at an early age.JADT

: 9 es Journées internationales d'Analyse statistique des Données Textuelles

All you need is to create this spell : 1. charm 1pt for 5secs on touch 2. fortify magicka 100 pts for 20 secs on self

Acknowledgements: This project is supported by the ANR under the RNTL programme, project TextCoop, we thank the ANR and our partners: Syllabs, Sinequa and Université de Paris Nord.


Clémentine Adam
email: clementine.adam@gmail.com

Estelle Delpech
email: delpech_estelle@yahoo.fr

Patrick Saint Dizier

Patrick Saint-Dizier

Identifying and Tagging Titles in Web Texts

Keywords: structure analysis, text semantics, text

come

INTRODUCTION

Recognizing and tagging titles in web documents is a difficult but necessary task. Indeed titles are realized in a large number of ways which do not follow in most cases the standards. Titles found in Web texts may also have different roles: some are related to the page main contents, whereas others deal with external considerations such as advertising, links to blogs, hints and advices of various kinds, just to cite a few. In this project, we are basically interested in identifying titles which are related to the document contents. For that purpose, we will consider both surface (e.g. typographical) and contents marks.

Titles in text play a large variety of roles. They obviously structure documents [START_REF] Vallduvi | The linguistic realization of information packaging[END_REF], outlining the main topics addressed. They can be viewed also as denoting goals, as in procedural texts, the area we are concerned with here. Question answering systems, for How-to questions need to refer to this latter type of title, whereas tutoring systems need to refer quite accurately to both types. We will not address here the complex roles titles may play, but this would certainly be a very useful investigation. To our knowledge, little work has been done on tagging titles, besides what has been elaborated in the Text Encoding Initiative. Titles have been studied in psycholinguistic circles, in linguistics [START_REF] Jacques | Approche en discours de la réduction des termes complexes dans les textes spécialisés[END_REF][START_REF] Vallduvi | The linguistic realization of information packaging[END_REF] and in didactics.

Web texts produced by non-professionals do not have in general a very strict encoding in html. We conducted our investigations on procedural texts [START_REF] Aouladomar | Towards Answering Procedural Questions[END_REF][START_REF] Delpech | Investigating the Structure of Procedural Texts for Answering How-to Questions[END_REF] which include a large variety of domains and document types, including documents as diverse as teaching texts, medical notices, social behavior recommendations, directions for use, assembly notices, do-it-yourself notices, itinerary guides, advice texts, cooking recipes and video games solutions. In those documents we noted a large variety of titles: titles related to the text contents, but also a number of other elements encoded as titles such as adds, email addresses, hyperlinks, web navigation instructions, etc. The next problem is that titles are often incomplete, up to 65% in some procedural texts such as cooking recipes. It is obviously of much interest to be able to reconstruct those titles for an optimal use of those texts by users. Another illustration of this need is, for example, in a how-to question answering context, questions (How to change my mothercard ?) that have to match with a comprehensive title, where the response is the procedure that follows. If we go further, in some areas, it may even be useful to be add titles when sections are very long, however reconstructing (or inferring) missing titles is a different issue that may need techniques such as e.g. text tiling.

In this short document, we first address the issue of title identification and tagging in a large variety of types of procedural texts, next we show how titles can be reconstructed via a learning mechanism and how index can be added to titles to allow for question matching. Titles express indeed goals 'changing a bike wheel' which must match with how to questions 'how to change my bike wheel?' to get the answer which is the text that follows, a set of instructions.

RECOGNIZING AND TAGGING TITLES 2.1 Cleaning Web texts

The input of our system are raw Web pages. To be able to correctly tag titles, it is necessary to eliminate useless information (advertising, summaries, links to blogs, comments, etc.). This useless information can represent up to 66% of the text. To carry this out, we need 1. to extract relevant text, that is, any kind of text that is not navigation help, advertisements or comments posted by cybernauts and 2. to select and to simplify the html tags in so as to keep the main typo-dispositional information (para-graph breaks, subdivisions of paragraphs into lines, lists and their subdivision into elements, emphasis).

Although [START_REF] Cruse | lexical Semantics[END_REF] was quite an easy task, we had some difficulties achieving [START_REF] Aouladomar | Towards Answering Procedural Questions[END_REF]. We designed an algorithm that returns, for each paragraph, if its contents can be considered as relevant or not. It mainly uses paragraph length and proportion of closed-class words criteria. We evaluated it on 100 Web pages, from 12 different web sites. The results compared to a manual treatment are quite good, we have 0,95 precision and 0,76 recall.

When the text is 'clean', we apply the Treetagger on it to identify its morpho-syntactic terms. We just keep some categories of interest to us (e.g. verbs, connectors). We also make some revisions since, in French, the imperative form, which is central to our system of extraction patterns, is often identified as present indicative tense.

Recognizing Titles

For answering How-to questions it is obviously of much importance to recognize titles, which, in fact, mostly express goals of various levels. A second challenge is to possibly identify title hierarchies in complex or long texts. Automatically identifying titles is quite challenging and has been seldom addressed in the past. Obviously criteria depends on the type of text (pdf, word, html, etc.), the quality of the encoding, the type of text (procedural, roman, news, etc.) and the domain at stake.

Let us concentrate here on procedural texts, encoded in html format, from various sources, styles and domains. As advocated above, a problem for us is that a number of titles in web pages are irrelevant with respect to the procedure at stake, they are rather advertising, web services ('click here for more') or summaries, to cite just a few. Besides recognizing titles as such, our task is in fact to concentrate on titles related to a procedure, so that these can be used for answering questions.

Titles are short text sequences, highlighted (bold, color, underlined, large size or different type of font, etc.). A first observation is that html encodings are, by far, not homogeneous. Titles are coded with the tag < hn > in only 20% of the cases over the 600 titles observed. In most cases, the tag < b > is used, possibly also < emp >, < u > and a few others (macros...). Low level titles even have more unexpected encodings. Encodings may be quite homogeneous within a given web site, but heterogeneity prevails over different sites, even in the same domain.

To be more precise, we observed that, roughly:

• 80% of titles are encoded with < b >

• 57% of the total of < b > used in texts encode titles

• 64% of the total of < h > used in texts encode titles.

This means that we need to consider additional criteria, among which:

• typography (spacing w.r.t. paragraphs before and after),

• the contents (number of words, inflected verbs) in the segment assumed to be a title,

• the type of elements after the title (e.g. instructions, which are a good indicator of a procedural title).

Titles are identified in two steps. First, an algorithm traverses paragraphs of a text one by one, and assigns them one of the following tags: title, text or ambiguous. This first step is quite straightforward. From our investigations on procedural texts, a title is a paragraph composed of a sequence of words of less than 12 words long and bearing emphasis. The tag text will be assigned without any doubt if the paragaph is subdivided into smaller units or is longer than 12 words. Ambiguous parapraphs are mainly short sequences of words (12 words or less) with no emphasis.

The second step disambiguates the ambiguous paragraphs one by one, using the tags assigned by the first step to their surrounding paragraphs. For example, an ambiguous paragraph between two paragraphs tagged as text will be considered as a text. Similarly, we have the following rules: 'an ambiguous paragraph between two titles is a text', 'an ambiguous paragraph followed by a title becomes a text' 'an ambigous paragraph becomes a title if it is the first paragraph of the text', etc.

This second step also operates some repairs on the tags yielded by the first step. For example, any sequence of more than two titles, i.e : "title title title", will be changed to "title title text".

The title hierarchy is very difficult to identify without content analysis. In fact, it is often largely pragmatic in nature.

For example in 'The pizza Margarita .... the paste .... the topings .... the serving ...'. It is impossible a priori to hierarchically organize those subtitles if you do not know what pizzas look like.

However, standard procedural texts are not very long and tend to be relatively linear. This means that, besides the page title, we observed in 80% of our texts not more than 2 levels of titles (exluding the main title). We observed two regular types of titles that can be correlated to some form of hierarchy. Type 1 is a title separated from the paragraph that follows by a < p > tag. Type 2 is a title separated from the paragraph that follows by a < br > tag. Although we still have no means to tell the exact level for titles, we can quite confidently say that a type 2 title will be at a lower level than a type 1 title, whatever the website or the domain. This information may be useful for question-title matching: type 2 titles are expected to introduce paragraphs that deal with more specific aspects of a procedure than paragraphs introduced by a type 1 title. Type 2 titles could help answering specific questions.

Evaluation

The evaluation corpus is composed of 78 Web pages over 5 domains: coocking recipes, do-it-yourself, video game solutions, social life, and medical recommendations. The total number of words is 61159, this not very large, but we feel sufficient for an indicative evaluation, giving us directions to improve the system. For each sequence, two annotators, doing the same task, had to decide whether it is a title or not. The corpus contains 4560 sequences, among which 511 titles and 1641 sentences containing at least one instruction.

The title recognition algorithm yields the following results over 5 different domains. Precision was given priority over recall to avoid errors as much as possible. We report here the recognition of titles related to text contents.

Filtering out non-relevant titles

The next step is to filter out as much as possible titles which are not relevant w.r.t. the contents of the page. The number of useless titles may vary quite largely depending on the domain. In general, we observed about 20 to 25% of irrelevant titles.

For that purpose, we consider two techniques that we are investigating at the moment:

• define a 'stop list' of typical terms found titles which are not relevant (e.g. click, see, consult, confirm, buy, advice, recommendation, etc.). So far, with a short stop list of 163 words, 59% of irrelevant titles are filtered out and only 4 titles out of 276 informative titles have been erroneously filtered out. This list may clearly be extended since so far the noise introduced is marginal.

• keep titles that have common contents with the paragraphs that follow. In particular, we are evaluating the fact that a relevant title must contain words, or related terms (synonyms, holonyms) [START_REF] Cruse | lexical Semantics[END_REF], that appear frequently in the paragraphs that follows. A technique based on text tiling can be used.

RECONSTRUCTING ELLIPTICAL TITLES 3.1 The problem and the situation

In procedural texts, there are domains like cooking recipes where we observed an average of 56% and up to 65% of the titles which are incomplete, i.e. w.r.t. the basic form: 'predicate + object argument' either the predicate or the argument is missing. For the reader, the reconstruction of the missing element is often straightforward due to context. Our goal is to identify the elements in the text that allow us to reconstruct titles, and possibly, as a side effect, to index them for information retrieval or question answering purposes. In general, elliptical situations do not really depend on the domain, there are however slightly more such titles in cooking recipes (references are probably more straightforward), and slightly less in the 'pratical life' domain. Also, the deeper the titles are in the hierarchy, the more elliptical they are (from 31% for top titles to 86% in average for the lower level titles). Finally, texts which have a large number of titles have a slightly higher rate of elliptical titles (ranging from 40% to 60% in average for texts with more than 6 titles).

missing argument

The case where subtitles have a missing object is relatively simple to resolve: in most cases, the object of the main title is inherited by the lower titles. In general, we observed that this form of inheritance only concerns those titles which are just one level below. This simple strategy has 94% accuracy.

missing predicate

The case where the predicate is missing is the most frequent and the most complex to resolve. An approach is to deploy a learning mechanism, where, roughly, we consider a sample of titles which are fully realized (predicate + argument). The principle is then to collect all the verbs that appear in the instructions below this title. Learning consist then, roughly, in making a distributional analysis of the verbs that appear under a certain title verb. For that purpose, we considered a development corpus of 3000 web texts over various domains. Via the TextCoop text tagger [START_REF] Delpech | Investigating the Structure of Procedural Texts for Answering How-to Questions[END_REF], those texts are annotated.

From each title which is complete, we created the structure: <verb of title> -[list + frequency of the verbs in the instructions under the scope of that title]. Then, summing over all texts and titles, we have a structure such as:

<verb of title + frequency> -[list of verbs + frequency],
where the frequency associated with the 'verb of title' is the number of times this verb has been found in titles and the 'list of verbs' is the union of all verbs encountered under the 'verb of title', with frequencies for each verb. This list is obviously dependent on the domains considered, or the group of domains, as in our case where closely related domains have been considered alltogether.

We then constructed the inverse list, where an entry is a verb from the 'list of verbs': <verb in instructions, frequency> -[list of title verbs associated, with frequencies]. This inverse list is used to reconstruct missing verbs in titles.

Then, to reconstruct a verb in a title with no verb, we proceed as follows. Given a title with a missing verb, we construct the list of verbs in the instructions in the scope of that title. From the inverse list above, we select potential title verbs, construct the union + frequencies set and, finally, keep the three most prominent verbs (those with the highest frequency) or deverbals.

This simple approach gives the following rates, via a manual analysis, considering again complete titles (but simulating lack of predicate), so that we have the solution accessible: in 48% of the cases, the correct verb has been proposed, and in 65% of the cases a good verb, closely related, has been proposed. Now, we can pair this algorithm with an endogenous search: we search in the paragraphs below the title if the argument which is the title is used and combined with a verb. This happens in 29% of the texts. If we combine the two techniques, learning and endogenous search, then, the results are really satisfactory: the correct verb is proposed in the list < procedure > < titlelevel = "0"index = "embellish, paint, decorate" > How to embellish your balcony < /title > < P rerequisites > An interesting feature is that the verbs present in 90% of titles are not so different: we have about 52 recurrent verbs which are quite generic for the group of domains we considered: choose, maintain, use, make, put, clean, paint, replace, prepare, manage, plant, etc. We also have a small number of deverbals derived from those verbs (replacement, preparation, etc.). Obviously for domains like health or video games, this list would be notably different.

Indexing titles

Finally, we can, based on the list of proposed verbs and deverbals, index all titles (complete or not) by means of that list, for question answering purposes. Consequently, in our representation, any title recieves a list of closely related verbs and deverbals as indexes, which will be used when attempting to match the terms of an How-to question with a title. So, instead of searching quasi-synonyms [START_REF] Cruse | lexical Semantics[END_REF] via a lexicon or an ontology as it is often the case in question matching procedures, resource which is not readily available for verbs in most domains, we have a list of predefined indexes which can be used directly with a good relevance score.

The representation of a title is as follows: <title index="w1, w2, w3"> ... title .... < /title> where w1, w2 and w3 are indexes, ranked by decreasing frequency.

PERSPECTIVES

In this short paper, we have presented the way titles in web pages, in a large variety of procedural texts, can be identified and tagged. We have also shown how to filter out titles which are not relevant w.r.t. the text contents. Finally, we have shown how to reconstruct titles which are elliptical, and how this reconstruction allows the production of dedicated indexes. These indexes are used for question matching since titles represent goals, similarly to questions.

In the near future, we need to evaluate the quality of the matching question-answer. Preliminary analysis seems to give quite good results. Also we want to provide the user with a few responses, not just one, so that he can choose the one that corresponds the best to his expectations.

The transposition of these techniques to other domains, such as news and technical documents does not seem so straightforward, but this is certainly one of our goals: to be able to identify titles and reconstruct them when incomplete in a number of situations. Another application, more oriented towards didactics and tutoring systems is to be able to suggest additional subtitles when a long text lacks titles.

  1 lattice, window boxes, etc.< /prerequisites > .... < titlelevel = "1"index = "cleaning, sweep, wash"missingarg = "balcony" > Cleaning < /title > ....... (instructions)..... < titlelevel = "1", index = "adding, including, decoratingwith"missingverb = "adding" > plants < /title > ....... (instructions)..... < titlelevel = "1", index = "spreading, painting, choosing"missingverb = "spreading" > the paint < /title > ....... (instructions).....

	.....
	< /procedure >
	Figure 1: Annotated titles in a procedure, (gloss from French)
	in 62% of the cases and a closely related verb is proposed in
	86% of the cases.

Acknowledgements This work is funded by the French ANR programme, RNTL section. This is part of the TextCoop project. We thanks all project members who contribuetd to discussions around the problem of titles.


Estelle Delpech

Patrick Saint-Dizier

Investigating the Structure of Procedural Texts for Answering How-to Questions

This paper presents ongoing work dedicated to parsing the textual structure of procedural texts. We propose here a model for the intructional structure and criteria to identify its main components: titles, instructions, warnings and prerequisites. The main aim of this project, besides a contribution to text processing, is to be able to answer procedural questions (How-to? questions), where the answer is a well-formed portion of a text, not a small set of words as for factoid questions.

Situation and Aims

The main goal of this work is to be able to answer procedural questions, which are questions whose induced response is typically a fragment, more or less large, of a procedure, i.e., a set of coherent instructions designed to reach a goal. Recent informal observations from queries to Web search engines show that procedural questions is the second largest set of queries after factoid questions [START_REF] De Rijke | Question Answering: What's Next?[END_REF].

Answering procedural questions thus requires to be able to extract not simply a word in a text fragment, as for factoid questions, but a well-formed text structure which may be quite large. Analysing a procedural text requires a dedicated discourse analysis, e.g. by means of a grammar. Such grammars are not very common yet due to the complex intertwinning of lexical, syntactic, semantic and pragmatic factors they require to get a correct analysis. Discourse grammars have basically a top-down organization, they take discourse acts as their basic units, instead of just words, they account for the structure and for the interactions between these acts and they require a relatively elaborated conceptual representation as output. Such a grammar must capture the discourse cohesion, possibly the communicative intentions, as well as the discourse organization, e.g. in terms of plans.

Procedural texts are organized sets of instructions, they may also be sets of advices, as in social behavior texts. In our perspective, procedural texts range from apparently simple cooking recipes to large maintenance manuals. They also include documents as diverse as teaching texts, medical notices, social behavior recommendations, directions for use, assembly notices, do-it-yourself notices, itinerary guides, advice texts, savoir-faire guides etc. Even if procedural texts adhere more or less to a number of structural criteria, which may depend on the author's writing abilities and on traditions associated with a given domain, we observed a very large variety of realisations, which makes parsing such texts quite challenging.

Procedural texts explain how to realize a certain goal by means of actions which may be temporally organized. Procedural texts can indeed be a simple, ordered list of instructions to reach a goal, but they can also be less linear, outlining different ways to realize something, with arguments, advices, conditions, hypothesis, preferences. They also often contain a number of recommendations, warnings, and comments of various sorts. The organization of a procedural text is in general made visible by means of linguistic and typographic marks. Another feature is that procedural texts tend to minimize the distance between language and action. Plans to realize a goal are made as immediate and explicit as necessary, the objective being to reduce the inferences that the user will have to make before acting. Texts are thus oriented towards action, they therefore combine instructions with icons, images, graphics, summaries, preventions, advices, etc.

Research on procedural texts was initiated by works in psychology, cognitive ergonomics, and didactics. Several facets, such as temporal and argumentative structures have then been subject to general purpose investigations in linguistics, but they need to be customized to this type of text. There is however very little work done in Computational Linguistics circles. The present work is based on a preliminary experiment we carried out (Delpech et ali. 07), [START_REF] Aouladomar | An Exploration of the Diversity of Natural Argumentation in Instructional Texts[END_REF] where a preliminary structure was proposed.

From a methodological point of view, our approach is based on (1) a conceptual and linguistic analysis of the notion of procedure and (2) a mainly manual corpus-based analysis, whose aim is to validate and enrich the former.

In this short paper, we summarize our results, focussing (1) on the conceptual notion of intructional compounds, which does capture the complexity just advocated, and (2) on the recognition of titles, instructions and instructional compounds. An quite comprehensive evaluation was carried out that we breifly report here. This work is part of the ANR TextCoop project. 1

The structure of procedural texts: Instructional Compounds

Procedural texts contain two basic structures: titles, analyzed as goals (with which questions will match), and instructions serving these goals. However, in most types of texts, we do not have just sequences of simple instructions but much more complex compounds. We noted that these compounds are organized around a few main instructions, to which a number of subordinate instructions, warnings, arguments, and explanations of various sorts are adjoined. Procedural texts also contain general purpose prerequisites and warnings, besides those included into instructional compounds.

Let us essentially, in this contribution, focus on the instructional compound structure, which is, by far, the most complex element. It has a relatively well organized discourse structure, composed of several layers, which are:

• The justification and explanation structure, which has wider scope over the remainder of the compound, indicates motivations for doing actions that follow in the compound (e.g. in your bedroom, you must clean regularly the curtains..., which here motivates actions to undertake).

• The instruction kernel structure, which contains the main instructions. These can be organized temporally or just be sets of actions. Actions are identified most frequently via the presence of action verbs (in relation to the domain) in the imperative form, or in the infinitive form introduced by a modal. We observed also a number of forms of subordinated instructions adjoined to the main instructions. These are in general organized within the compound by means of rhetorical relations, that we introduce below.

• The deontic and illocutionary force structures: consist of marks that operate over instructions, outling different parameters:

-deontic: obligatory, optional, forbidden or impossible, alternates (or), -illocutionary and related aspects: stresses on actions: necessary, advised, recommended, to be avoided, etc.

• The conditional structure: introduces conditions over instructions within the compound or even over the whole instructional compound.

• The rhetorical structure whose goal is to enrich the kernel structure by means of a number of subordinated aspects (realized as propositions, possibly instructions) among which, most notably: causality, enablement, motivation, argument for, circumstance, elaboration, instrument, precaution, manner. The rhetorical structure is in general composed of instructions (satellites) related to the instructions in the kernel.

Let us now give an illustrative example (translated from French), extracted from the 'Do-It-Yourself Home' domain: In the bedroom, it is necessary to clean curtains.

These are cleaned first with a vacuum-cleaner to remove dust, then, if they are in cotton, they can be washed in the washing machine at 60 degrees; if they are white, it is even recommended to add some bleech so that they look whiter. With some starch, they can be easily ironed.

In this text, the sequence: In the bedroom, it is necessary to clean curtains is analyzed as a justification of the actions to undertake. The next portion: These are cleaned first with a vacuum-cleaner to remove dust, then, if they are in cotton, they can be washed in the washing machine at 60 degrees. is the instruction kernel, where the last instruction is associated with a condition. Finally, If they are white, it is even recommended to add some bleech so that they look whiter. With some starch, they can be easily ironed. are two subordinated clauses, analyzed as advices.

Recognizing Titles, Instructions and Instructional Compounds

Cleaning Web texts: our system has Web pages as inputs. For an optimal parse, the first task is to remove a number of useless elements (tags and noise like advertising, chats or navigation links), while keeping tags and text portions which are a priori of interest. This is not an easy task, (results under submission). The evaluation of this procedure, designed to be fast and simple, carried out over 100 texts from 8 different domains gives a precision of 0.78, a recall of 0.90 and an f-measure of 0.83. These results are satisfactory w.r.t. our purpose.

Recognizing Titles: for answering How-to questions it is obviously of much importance to recognize titles and possibly hierarchies of titles in complex texts. A first observation is that html encodings are, by far, not homogeneous. Titles are coded with the tag < h. > in only 20% of the cases over the 600 titles observed. In most cases the tag < b > is used, possibly also < emp >, < u > and a few others (macros...). Low level titles even have more unexpected encodings. Encodings may be quite homogeneous within a given web site, but heterogeneity prevails over different sites, even in the same domain.

To recognize titles, we first made a simple selection that consists in keeping all those sequences in a text between < b > or < h > tags which are below 6 words long. Then we applied two selectional criteria: positional: immediate precedence of a set of instructions (when these are recognized) and contents: similarity of the terms in the title with respect to those most frequently used in the paragraph that follows (thematic cohesion). This measures the lexical similarity between an assumed title and the paragraph that follows. Our results show that this similarity is 6 times higher for titles than for sequences in bold which are not titles. We however observed a quite high standard deviation. Final evaluation is given in the section below.

The title hierarchy is very difficult to identify without content analysis. However, standard procedural texts are not very long and tend to be relatively linear. This means that, besides the page title, we observed in 95% of our texts not more than 2 levels of titles. While level 1 is often well delimited from the text part, level 2 is often closely associated, as e.g. a bold sequence followed by a semi-colon, or a short spacing. To answer How-to questions, it seems that only level 0 and 1 titles are relevant. One remaining difficulty is that titles have often a very elliptic structure.

Recognizing instructions and instructional compounds: instructions are recognized on the basis of two factors: contents, around action verbs in certain forms to identify an instruction and typographic factors for its delimitation (beginning and end) via html tags, punctuation marks or connectors. Verbs must be action verbs (this may depend on the domain and subsets can be defined for each domain to improve accuracy). They must have in French specific forms, in decreasing frequency order: imperative, infinitive, modal + infinitive, dummy pronoun 'on' + finite verb, middle reflexive constructions, and gerundive forms. The frequency usage of each of these forms largely varies across domains (e.g. coocking receipes mainly use imperative while video game solutions make high usage of the dummy pronouns 'on' or even of finite forms in the first person singular). The recognizer (also called the segmenter) includes 25 generic patterns. The segmenter is implemented in standard Perl. Note that English seems to have a simpler set of forms while Spanish has a lot of finite forms, making instructions slightly more difficult to recognize.

Instructional compounds are composed of instructions. They are delimited as follows: by means of typographic marks: ending of enumeration (e.g. < li > sequences) or by 'strong' marks in long paragraphs. These marks are in general temporal (Two hours later,...), conditional expressions or goal expressions.

Finally, a grammar, based on a simple transposition of a few Minimalist Theory principles allows us to bind all the parts of the text. The grammar runs in Prolog in our prototype. The output is an XML file that reflects the text structure.

Evaluation

The evaluation we have carried out allows us to have an estimate of the overall quality and accuracy of the recognition mechanisms, outlining problems and gaps for future evolutions. From that point of view, it is an indicative evaluation.

The first step was a manual annotation carried out by two independent annotators of 78 Web pages over 5 domains: coocking recipes, do it yourself, video game solutions, social life, medical recommendations. This corresponds to 1641 instructions over 4560 sequences potential instructions and 511 titles. Total number of words is 61159, this not very large, but we feel sufficient for an indicative evaluation, giving us directions to improve the system. Evaluators had to indicate whether a sequence is:

-a title, -an instruction, with the possibility to give certainty of judgement on 3 values.

The total work took about 15 hours of manual work. Decisions were quite often difficult to make for some types of texts where quite a lot of knowledge of the domain is required, as for video games. Kappa measures were carried out to evaluate agreement and have a measure of the complexity of the tasks. In terms of inter-annotator agreements, we got for instructions, per domain: coocking recipes (82%), do it yourself (76%), social life (71%), video games (45%) and medical recommendations (42%). This gives an idea of the complexity of the task (and therefore modulates the results) and of the uncertainty of some measures. Then the two annotators had discussions (about 5 hours) to reach a consensus and propose a unique annotation for all files.

The result was then compared to the annotations realized by the programme. These are summarized in the array below for instructions and titles. Our strategy was in general to favor precision over recall, since even if some instructions are not recognized here and there, the questionanswering system can still respond accurately. We have not tried at this level to implement an efficient system, however, we can fully parse 1 Mo of web pages in 7.25 seconds, on a pentium3 3GhZ machine with 4 Go RAM.

Instructions recognition: The first three domains give quite good results, while for the last two, the poor quality of texts and their high diversity explains the moderately good results, which was expected. As can be noted, title recognition gives sligthly better results.

A Few Perspectives

This work is still under research. However, the linguistic structure of texts and the methods to recognize titles, instructions and instructional compounds and the global text structure seem to be on the right track. We obviously need to deepen evaluation for compounds as well as for whole texts, but this is much more difficult due to the complexity of annotations.

To improve the domains with low level results, one direction would be to design dedicated recognizers, with specific patterns. Some more efforts are also necessary in large texts to identify title hierarchies. At the moment, we do not see any simple solution which does not involve pragmatic or domain factors.

The last step of the project is to explore how How-to questions can match with titles (goals), and what kind of results must be returned to the user (the instructions below the title, more data containing prerequisites, several documents, etc.).


Estelle Delpech
email: delpechestelle@yahoo.fr

Elixabete Murguia
email: emurguia@yahoo.com

Patrick Saint-Dizier

A Two-Level Strategy for Parsing Procedural Texts

This paper presents ongoing work dedicated to parsing the textual structure of procedural texts. This work is based on a two level approach: first, basic structures in texts are segmented using automata techniques and then a text grammar is applied to assemble these fragments. The grammar is based on X-bar syntax, transposed to text structure.

Introduction

The main goal of this work is to be able to answer procedural questions, which are questions whose induced response is typically a fragment, more or less large, of a procedure, i.e., a set of coherent instructions designed to reach a goal. Recent informal observations from queries to Web search engines tend to show that procedural questions is the second largest set of queries after factoid questions (de [START_REF] De Rijke | Question Answering: What's Next?[END_REF]. This is confirmed by another detailed study carried out by [START_REF] Yin | Topic Analysis and Answering Procedural Questions[END_REF]. Procedural question-answering systems are of much interest both to the large-public via the Web, and to more technical staff, for example to query large textual databases dedicated to various types of procedures, including economic and commercial procedures (legal, know-how, etc.).

Answering procedural questions thus requires to be able to extract not simply a word in a text fragment, as for factoid questions, but a well-formed text structure which may be quite large. Thus, the techniques used for factoid questions do not seem adequate to deal with the problem at hand. We propose that a different approach should be adopted. We propose that the use of text grammars is a more appropriate and precise manner for representing and recognizing procedural knowledge in a text.

Analysing a procedural text requires a dedicated discourse grammar. Such grammars are not very common yet due to the complex intertwinning of lexical, syntactic, semantic and pragmatic factors they require (see e.g. functional discourse grammars and systemic grammars) to get a correct analysis. Discourse grammars have basically a top-down organization, they take discourse acts as their basic units, instead of just words, they account for the structure and the interactions between these acts and they require a relatively elaborated conceptual representation as output. Such a grammar must capture the discourse cohesion, including the communicative intentions as well as the discourse organization, e.g. in terms of plans.

Procedural texts explain how to execute procedures. In our perspective, procedural texts range from apparently simple cooking recipes to large maintenance manuals (whose paper versions are measured in tons e.g. for aircraft maintenance). They also include documents as diverse as teaching texts, economic regulations and know-how texts, medical notices, social behavior recommendations, directions for use, advice texts, savoir-faire guides etc. Even if procedural texts adhere more or less to a number of structural criteria, which may depend on the author's writing abilities and on traditions associated with a given domain, we observed a very large variety of realisations, which makes parsing such texts quite challenging.

Procedural texts explain how to realize a certain goal by means of actions which are at least partially temporally organized. Procedural texts can indeed be a simple, ordered list of instructions to reach a goal, but they can also be less linear, outlining different ways to realize something, with arguments, advices, conditions, hypothesis, preferences. They also often contain a number of recommendations, warnings, and comments of various sorts. The organization of a procedural text is in general made visible by means of linguistic and typographic marks. Another feature is that procedural texts tend to minimize the distance between language and action. Plans to realize a goal are made as immediate and explicit as necessary, the objective being to reduce the inferences that the user will have to make before acting. Texts are thus oriented towards action, they therefore combine instructions with icons, images, graphics, summaries, preventions, advices, etc.

Research on procedural texts was initiated by works in psychology, cognitive ergonomics, and didactics. Several facets, such as temporal and argumentative structures have then been subject to general purpose investigations in linguistics, but they need to be customized to this type of text. There is however very little work done in Computational Linguistics circles. The present work is based on a preliminary experiment we carried out (Aouladomar and Saint-Dizier 2005), where a preliminary structure was proposed.

From a methodological point of view, our approach is based on (1) a conceptual and linguistic analysis of the notion of procedure and (2) a mainly manual corpus-based analysis, whose aim is to validate and enrich the former. The originality of our work lies at the level of the objects parsed in discourse, and on the way linguistic principles and norms are inserted to deal with the large variety of forms procedural texts may have. The paper is structured as follows: we first present our generative approach to text processing, we then develop the two steps of the treatment: segmentation and grammar application.

Text Grammars

The answer to a procedural question is a well-formed fragment of a text, it might include a sequence of n instructions linked by various markers (e.g, coordinators, temporal marks) or typographical cues (e.g., comma, dot, newline). Thus, the answer cannot be found locally, like in the case of factoid questions.

The Structure of Procedural Texts

The structure of procedural texts can be more or less complex. There are certain types of procedural texts (e.g. recipes) which are not very structured, in other words, what we generally find is a goal (e.g. How to cook a paella) followed by a sequence of steps to follow in the form of instructions for the user. Nevertheless, this is not always the case. In some other texts (e.g. do-it yourself, maintenance manuals), the structure is not so flat, what we find is a more hierarchized division of the text in subprocedures to reach the goal. For example, a text about Maintainance of your swimming pool can be divided in the following subsections: Emptying the swimming pool, Cleaning the swimming pool, Mantainance after cleaning and control of the pH level, Avoid the formation of fungus. All of these subgoals are followed as well by a sequence of instructions. In general, we can say that the longer or more complex the procedure is, the more divisions the text is going to have.

In [START_REF] Aouladomar | An Exploration of the Diversity of Natural Argumentation in Instructional Texts[END_REF] an analysis of procedural texts is presented. This work identifies different elements, among them: instructions, goals, warnings, prerequisites, and pictures. We assume this classification for this work. Among these building elements, the central unit is Instruction, together with Goal. They both constitute the core of a procedural text. This work showed that a constituent in a procedural text may occupy a large variety of positions, and a number of them may be optional. Writing a text grammar of this kind results in a set of rules with little constraints and with a low predictive and explanatory power. To circumvent these problems to a certain extend, we explored the possibility of defining a set of principles, constraints and norms that would account for procedural text structure in a better way. We borrowed some of these principles to Generative Grammar. This led to the development of specific parsing strategies, presented hereafter.

A Grammar for Procedural Texts

In order to define our grammar, we borrow some notions from generative grammars and transpose them to the problem we have in hand. For example, we adopt the notion of head which is the central element in a syntactic phrase, and combines with other elements to the right (a complement) and to the left (specifier) to project structure. We transfer X-bar syntax to text structure. We also borrow the distinction between complements and adjuncts, or obligatory and optional material. Depending on whether an element belongs to one category or the other, it occupies a different position in the structure. We also aim at a slight shift from 'classical' grammar descriptions to a principled-based approach, using principles, parameters, but also norms that capture the different types of realizations observed over genres and domains, used as heuristics (e.g. average length of titles and instructions, most frequent verb classes used, etc.). A clear di-vision between central and peripherial (or obligatory and optional) elements is made and reflected in the final structure. Also, the relations between the different building blocks in a text (e.g. scope relations) are more clearly delimited, since the resulting structure is not flat but rich in terms of hierarchical structure.

We conceive the structure of a procedural text as the projection of a Goal (i.e. the title of the text) and its complement which can either be a sequence of instructions or a sequence of tasks. Thus, the root grammar rule is:

Procedure --> Goal seqInstr Procedure --> Goal seqTasks
We continue defining our grammar from the lower level units up to the root grammar rule. For the purpose of this work, we assume that the basic unit is the Instruction. Instructions, however, do not come in isolation, but as we already said combined with other instructions. We call these combinations sequences of instructions (seqInstr), and we analyze them as a coordination of instructions, where the head of the phrase is a sequence marker. We include below the rules that identify this type of structure: seqInstr --> Instr seq' seq' --> seqmarker Instr seq' --> seqmarker seqInstr If the first and the second rule apply, a structure like the following could be recognized: Hold the bracket down on the tabletop, then screw one of the screws through the hole in the bracket. The third rule takes care of recursivity, and it will recognize any sequence formed of more than two instructions, such as: Turn on the access point, and activate the wireless connections for your devices. Verify that they are all transmitting a wireless signal.... A sequence of instructions is the complement of a Goal. Thus, it is obligatory (we cannot have a Goal without a seqInst associated, it will result in an ill-formed structure). Goals are the heads of their phrase, they project up a Task. In the specifier position of this phrase, we can optionally find some prerequisites (e.g. the ingredients in a recipe).

Task --> (spec) G' G' --> Goal seqInstr G' --> Goal seqTasks

With the first and second rule, we can recognize structures such as (i) Fixing the top rails to the table top. Place the table top upside down on an even floor, saw stools or workbench. Position the top rails on the underside of the table top ... and (ii) To get dried oil paint off a brush, soak it in nail-polish remover for a minute or two, after that you wipe off what remains and clean your brushes with soap and water as usual. In the first example the Goal is the first sentence, which is a subtitle. This is followed by its complement, a sequence of instructions, and together they project a Task. In the second example, the Goal is the preposed purpose clause introduced by To, which is also followed by a sequence of instructions. The third rule describes the situation where the complement of a Goal is a sequence of tasks rather than of instructions. An example of this type of structure is the one provided in the previous section of Maintainance of a swimming pool, where the main procedure is divided in different subprocedures or subtasks, each followed by a seqInstr, building a seqTasks. We analyze sequences of Tasks in the same way as sequences of instructions. The first and second rule represent basic cases, the third recursivity: seqTasks --> Task seq' seq' --> seq Task seq' --> seq seqTasks Optional elements are adjoined to different levels of the structure, depending on their scope. For example, we can have a condition linked to one instruction as in If it is not soft, boil it for ten more minutes, but also adjoined to a sequence of instructions If you have Windows 95 installed in your computer, turn on the computer and follow the instructions on the screen. Other elements like warnings or pictures can also be adjoined to those nodes, or to Tasks or sequences of tasks. The rules for adjuncts follow, adjuncts can either appear to the right or the left, that is what the symbol + codes:

Instr --> Adjunct + Instr seqInstr --> Adjunct + seqInstr Task --> Adjunct + Task seqTasks --> Adjunct + seqTasks

Parsing with Text Grammars

The grammar defined above identifies text structures relevant for answering procedural questions. Obviously, we do not aim at making a full parse of those texts. We need to identify 'terminal' structures (such as titles and instructions), and then to assemble them together.

The parsing of procedural texts is realized in two steps. First a segmentor, comparable to a lexical tagging component for sentence words, identifies basic structures and then the X-bar grammar presented above assembles these basic structures. The segmentor makes an initial proposal to the grammar. In case of a failure of the grammar, backtracking is possible, but to a limited extend, so that relatively optimal segmentations are kept.

The starting point of our system are web pages, these are cleaned so that only relevant tags for the segmentor or the grammar are kept. They are then tagged with the TreeTagger, in order to incorporate category and relevant morphological information. A final step identifies the semantic class of the verbs, according to a classification we carried out, largely inspired from WordNet classification. Our classification is composed of a hierarchy of 186 classes, among which: verbs of change, verbs of cleaning, maintenance, etc.

The segmentor

The segmentor has several goals:

• First, to tag terminal discourse elements: instructions, titles (viewed as the expression of goals), warnings stated outside instructions, prerequisites, some forms of arguments and connectors. This is useful to reduce the non-determinism in the grammar.

• Via the tagging, to allow for the identification in a large text of zones which are more procedural than others (large texts may be verbose and contain non procedural elements such as comments or historical considerations), allowing then to focus the search of responses on a certain text area.

It is clear that the form of those terminal objects and the criteria required to define them largely varies over application domains, textual genres and the targeted audiences. Our strategy was to define several sets of criteria, valid for a group of domains that share common discourse forms for describing procedures. Our approach was to proceed by 'domain aggregation'. For example we first considered samples from coocking recipes texts, and defined the segmentation criteria. Then, we considered other domains which turn out to have a close structure: 'do it yourself' and video game solutions. At a certain stage, we get a stable set of criteria which can be implemented as an automaton. We plan to have in the end a small number of automata, each encoding the discourse structure of a group of domains.

Finally, each type of object we have to segment requires a different approach of segmentation, because the identification criteria are very different. We briefly present them below.

Dealing with Instructions

As far as instructions are concerned, the model is relatively straightforward finite state automaton, with some little tricks, since some marks may be common to two adjacent instructions, such as punctuation. The main marks for instructions are:

1. typographic and punctuation marks, and temporal marks, used for delimiting instructions, 2. verbs, together with their morphology (basically infinitive and imperative forms are quite frequent incoocking recipes, but other tenses are found in other domains), and their semantic class (action verbs and subclasses) since semantic class may be used to identify different types of instructions; deverbals and predicative nouns are also relevant, 3. various classes of marks, such as: modal marks ('you must do'), reminders ('do not forget to'), performance marks ('care about doing'), marks describing optionality or advices ('it is preferable to'), injunctive forms, and adverbs of manner. Besides these elements used to identify instructions, instructions may contain a lot of elements such as: low level goals, pictures, local warnings, hyperlinks, etc.

Recognizing Titles

Recognizing titles is much more challenging. They have in general the form of an instruction (e.g. mounting your computer), but with a different layout. Recognizing titles is crucial for answering questions.

Titles are first identified by the typography: bold font, possibly underlined, or via the use of dedicated html marks (h1, etc.). Finally, we can also rely on the level of generality of the verbs used in titles, which are more generic than those found in instructions (we use the Volem verb base for that purpose). In fact, titles can be viewed as 'super-instructions', this distinction being highly domain dependent.

Prerequisites as well as warnings may also have titles. However, these two latter objects have a different typology (although they may also contain instructions), which allows us to make the distinction among types of titles, and to isolate those effectively governing instructions, to be interpreted as denoting goals.

A second problem is to identify the hierarchy of titles, which is important in most texts of a certain length. Identifying such a hierarchy allows us to associate more precisely sequences of instructions to a goal. Since dedicated html tags are not so frequent to discriminate titles, we must rely on other factors, among which:

• presence of capital letters, or size in number of words (quite frequently 4 to 5 words, with no pronominal references), • level of the verbs in titles: higher titles contain more generic verbs, • identification of islands of instructions which share a quite large number of common words (entailing a certain thematic cohesion of instructions below a title, as in Centering Theory). • identification of summaries or introductions below titles which contain words present in subtitles. This is however still a very tentative option.

Another kind of difficulty is that titles are often elliptic (e.g. the verb is missing). In some situation they may be just absent, therefore, we may need, to answer questions, to be able to reconstruct these.

Dealing with Warnings

Warnings as well as arguments are introduced by a range of specific verbs often in the imperative form or by negative connectors, which is quite easy to identify in French. Here are a few examples:

• negative connectors: sous peine de, sinon, car sinon, sans quoi, etc. (otherwise, under the risk of), • risk verbs: risquer, causer, nuire, commettre, etc.

• prevention verbs: éviter, prévenir, etc.

• negative expressions: de facon à ne pas, pour ne pas, pour que ... ne ...pas, etc. (in order not to).

Indentifying Discursive marks

Temporal marks are the most frequent marks, they include: precedence, overlap, inclusion, parallelism, etc. They are mainly realized by means of adverbs, prepositions, conjunctions, aspectual verbs and propositions describing the realization of an event. Marks are annotated by the TreeTagger and typed via a predefined list we have elaborated.

Causal marks are particularly rich and diverse. They are used to relate a goal to a set of instructions, or to specify within an instruction its aim; causal marks are also used to identify objectives, warnings and various forms of preventions, consequences and some forms of conclusions.

Besides these two main classes of marks, we noted a few conditionals and alternative marks. These are often prepositions or semantically closely related to the semantic typology specific of prepositions. To identify and interpret them, we use the PrepNet framework (www.irit.fr/recherches/ILPL/prepnet.html).

Global Architecture

The automaton first recognises instructions, then titles, warnings and prerequisites. Segmentation is confronted to several difficulties, among which:

• ambiguities of various sorts: coordination or punctuation in instructions: for that purpose we must develop some very local grammars that check the status of these elements and decide whether they are inside an instruction or must be considered as a delimitation mark.

• several partially overlapping structures candidates to be an instruction, this is the case for instructions that contain e.g. warnings or advices that may or may not be also considered as separate instructions. At this stage, we can recognize them, but keep them in a single instruction.

• shared items between adjacent instructions, entails some forms of either partial parsing (making e.g. the hypothesis that an instruction may lack a begining mark) or stacks to keep track of elements which may be shared (e.g. shared arguments in ellipsis).

• a few unexpected forms, e.g. using the future tense.

The result of the segmentor is a representation of the following form (simplified for readability): <procedure> <title> poser une tringle rideaux </title> <warning> attention a ne pas perdre des elements </warning> <prereq> les regles de base .... </prereq> <seqinstr> <warning> disposez de suffisemment d'espace </warning> <instr> 1. tracer la hauteur de la tringle, </instr> <instr> 2. couper la tringle a la bonne longueur. </instr> etc. </seqinstr> </procedure>

The grammar implementation

The grammar is used to bind the elements identified by the segmentor. It gives a global structure to the text, which is necessary and sufficient to answer how-to questions. One of its goals is to give a precise scope to each element. It also binds adjuncts at appropriate places, giving these a priori a minimal attachment.

The grammar produces an XML output, usable for the search of responses. In particular, titles, viewed as goals, are considered for unification with the question body. Some instruction fragments may also be considered to identify subtopics. XML tags therefore identify indexes used by the question-answering system.

We have designed a prototype in Prolog, implementing a topdown engine. In spite of its relative inefficiency, we have adopted so far an interpreter mode so that every step of the system can be evaluated. Another goal of this first implementation is to be able to add heuristics quite easily and to test their impact. These heuristics capture the notion of norm introduced above; they contribute to resolving ambiguities and to compensate for structures not recognized by the segmentor. For example, we have:

• resolving ambiguous attachment of constructions: a typical case is the attachment of pre-requisites, which can be bound to a number of specifier positions: our norm is to have a maximal attachment, i.e. to have prerequisites attached as high as possible in the tree. An opposite case are warnings, which need to be as close as possible to instructions: they undergo a minimal attachment, being adjoined at the lowest level possible.

• going over structures not recognized by the segmentor: a typical situation is when the segmentor does not have recognized a title (it is incomplete, illformed w.r.t. the segmentor, or it does not exist and needs to be infered for answering questions). Each domain being associated with a small number of norms (average instruction size, average number of instructions per task, per sequence of instructions, etc.), when for example, an unexpectedly large number of instructions is found without any structure binding it (sequence of instruction tag or title), our norms allow us to suggest that, based on specific typographical marks, a title has possibly been skipped at a certain position.

Finally, the engine is flexible enough so that partial parses can be carried out, especially on large texts, where there is a lot of useless text or where there are some risks of failure. This short paper relates ongoing work on parsing procedural texts via the pairing of a segmentor, capable of recognizing, basically, terminal text structures, and a grammar, inspired from generative principles, that better captures the variability of procedural styles over domains and authors.

The implementations proposed so far are preliminary and allow us to explore the various types of problems one may encounter when dealing with text grammars. The corpus considered is of a rather modest size, but with quite diverse structures. It is a development corpus, allowing us to better analyse the behavior of the different components we have developed. Outputs are checked manually: this is a quite challenging task, since most texts include more than one hundred tags.

Since this project is designed to become an industrial project, it is clear that we need to investigate other forms of implementations once the linguistic quality of the segmentor and of the grammar is satisfactory. A possible direction is to develop learning mechanisms trained on the outputs of our parser. These would produce probably slightly less good results, but would allow for the processing of large amounts of texts over a limited period of time.

We thank the ANR-RNTL program trough the TextCoop project for supporting this research.