Christian Rossi

From distribution to preservation of digital documents

This article addresses the issues of conservation of (mostly textual) electronic documents. Its main objective is to describe the problems in terms of hardware and software mediators between the data and the user rather than focusing on formats. The point of view is that of a skeptic.

Introduction

The subject of this paper is the problem of preserving digital documents. It is mainly aimed at describing the problem of preservation in terms of the intermediary hardware and software between the data and the user, rather than in terms of file format. It is particularly focused on text documents and covers various aspects of the problem: hardware and software, migration, file formats, typography, XML, conversion, duration.

A digital document is not directly accessible to a human user

A key characteristic of the digital world is that there are many intermediaries between the medium on which digital information is stored and the user:

• the medium;

• a reader or drive; • the operating system; • a software application;

• the peripherals;

• operating instructions.

In the first place the medium (magnetic disk, cdrom, etc.) on which the information is physically held, then a drive used to convert the physical information into binary information, then the operating system used to group these 0s and 1s into files and directories. Finally, a software application that makes this file accessible to a human being via an audio or video peripheral or a printer, and this covers only the most standard cases. Not forgetting, of course, a person who knows how to use, and sometimes repair, all these intermediaries. This is the major difference in relation to paper, which gives direct access to information.

In terms of preservation, a significant consequence of the existence of these intermediaries is that it is not only the medium itself which must be available, but the entire chain of consultation, and if not the original, then an equivalent. The length of this chain is a problem in itself, but its life expectancy, i.e. that of a computer and its peripherals, is rather short. At present, on average, it is common practice to replace a computer every three years, a new version of a standard operating system is available every year and security patches must be applied every month. And all this is necessary since for "old" equipment official maintenance soon stops or, if it is still available, is charged for at exorbitant rates. Ensuring the preservation of digital documents therefore now means choosing between constantly migrating all media and hardware and software chains, or creating living IT museums in which these intermediaries are kept in working condition.

In fact we can end up having to migrate not because the medium is nearing the limit of its physical life, but because of its technical/commercial obsolescence: the reader or drive is no longer on the market, is no longer maintained, and technical support is out of date. From this point of view there is no point in using a medium with a life expectancy of a hundred years, since in three years' time migration will be necessary. The technical/commercial life expectancy is shorter than the physical life expectancy.

Two other problems should be emphasized. The first is knowing what to migrate to -a decision that cannot be automated. Errors in this respect can give rise to many unnecessary and costly migration operations. The second is simply to guarantee, during successive migration operations, the preservation of document integrity. During migration, files are copied from one medium to another. Tools must then be used to check that the binary content of the files is identical. But if file format conversions are required, an automatic check appears to be impossible. How can a guarantee be given that a PostScript file converted to PDF will give an identical graphic output? The file is no longer the same, and neither is the consultation software.

Other solution: emulation of older technology, but this considerably extends and adds complexity to the chain between the document and the user, adding yet another intermediary. Another problem is the fact that the specifications of the technologies to be emulated are not necessarily in the public domain. But an emulator is also software like any other, which runs on a certain machine with a certain version of a certain operating system. In other words, emulation necessitates migrations of the emulator.

Autonomy and preservation

What will the life expectancy of a paper document be if it has to be de-acidified every three years to Christian Rossi keep it intact? There is just one answer: the time during which the people, the financial resources and the will to do so are all available. The situation is very similar with digital documents.

Taking into account the rapid evolution of techniques, the life expectancy of the hardware, software versions and file formats, it is clear that migrations and conversions of all sorts are inevitable. In other words, an electronic document is highly dependent on human intervention for its preservation -much more dependent than paper documents. We are a long way from the historic document that no one has touched for 200 years and that is rediscovered with great excitement. In an ideal world a document should be autonomous in terms of its preservation.

Moreover, an important constraint is that the preservation cost must be reasonable. This is not at present really compatible with frequent software and hardware migrations and the human operations involved in these migrations. But going beyond the issue of cost, relying on recurring and frequent human operations to ensure the preservation of documents in the long term does not appear to be reasonable.

Ease of use or life expectancy

If we consider the evolution of documentation media over time, we can observe two key points:

• ease of use has increased;

• life expectancy has decreased.

Effectively, while it is easier to use a sheet of paper than a tablet of stone, the life expectancy of the paper is clearly shorter. If we start with clay tablets, moving on to parchment, then paper, this evolution is very clear, an evolution that has also led to the real democratization of access to information, but an evolution that has also given rise to a real reduction in the life expectancy of documents. There has been a price to pay. We can summarize this situation by saying that for traditional media: ease of use × life expectancy = constant Is the situation the same with digital media? In terms of ease of use, it is unquestionably very high. Digital is fantastic for creating, modifying, storing, searching, distributing, etc. But in other respects digital is effectively complex, fragile, unstable . . . and we have not had enough time to stand back and assess it. The high number of intermediaries between the medium and the human user does not make either access to information or its preservation any easier.

The situation therefore appears, for the moment, to be the same. And if we are actually in a universe where it is impossible to have only advantages, where what we gain in ease of use we lose in terms of life expectancy, it is better to use the digital media in full knowledge of the facts.

We are not talking here about stopping the use of digital media -as if we would want to -but of being realistic. For instance, we do not demand that paperback novels last forever, but no one would want to see them disappear. A paperback novel is used simply for its qualities, not criticized for its shortcomings. With digital media the same behaviour is reasonable: using it for its qualities of creation or distribution, while remaining aware of its current shortcomings in terms of preservation.

From the very short term to the long term

If the preservation time required is specific to each type of document type and its planned use, we can at least try to define a timescale for the preservation of digital documents:

• very short term: corresponds to the technical and commercial life expectancy of the consultation chain; in the case of a problem performance is assured by a maintenance service;

• short term: physical life expectancy, it works for as long as it works . . . ;

• medium term: access to data is assured thanks to the implementation of an organisation responsible for migrations or other operations;

• long term: from the moment at which this organisation no longer exists, we return to the physical life expectancy of the consultation chain resulting from the latest migration.

Once we are aware that digital data is not autonomous in terms of preservation and that it must be managed (hyperactive storage), it is possible to guarantee its medium term sustainability. This requires a reliable organisation and considerable human and financial resources. Such an organisation must ensure data collection and preservation and control data access. Of course there is always a possibility of loss, or of migration being forgotten -no organisation is perfect. But this does not give any indication of the possible duration of this medium term, or resolve the problem in the long term. Indeed, while medium term preservation is realistic, long term archiving poses a real problem. What will remain for the historians?

The remainder of this paper is focused on the software chain.

From distribution to preservation of digital documents 6 From source formats to viewable formats Starting with a file, intermediaries are required, notably a software chain, so that a document can then be read.

The following are some of the different format types used for text documents:

• source format (L A T E X, RTF, TEI, HTML);

• viewable vector format (PostScript, PDF);

• viewable bitmap format

And here are the possible stages involved in converting a source file into information that is comprehensible to a human being: pdftex computer>source file =⇒ vector file ms word xpdf vector file =⇒ bitmap data>peripheral>human acrobat

A source file will contain text and information expressed using a given language: typographic information (justification, italics, etc.), information on the structure (title, author, chapter, etc.), or even a mixture of the two. This is the type of file created by an author and therefore oriented towards document creation.

Once processed by tools such as MS Word or pdfL A T E X, the output is a viewable vector file (type PostScript or PDF). This is a file containing text and positioning information: put the letter x on the page in a specified position and use the Times font. It is a geometric description of the page. Draw me a circle of radius 1 in the middle of an A4 page. Of course, the equations involved in drawing a letter are more complicated than for a circle, but the principle is the same.

Tools such as Xpdf, Ghostscript, Acrobat and the PostScript interpreter on a printer are examples of software that can read these PostScript or PDF files and pass on this geometric description to an image on a screen or printer -i.e. a bitmap image identical to an image produced by a scanner. A viewable bitmap file which is "understood" by the peripherals: the pixel is on or off, ink must be deposited at such and such a point on the page. The file has been converted to an image that can be seen by a human.

With WYSIWYG tools such as MS Word or Open-Office, these stages are invisible and hybridized, since all these functions are performed in the same software.

In software terms these stages have varying levels of complexity.

Displaying a bitmap file onscreen requires simple software. No arbitration is required between the content of the file and the final result: with a 0 the pixel stays black, with a 1 it becomes white. All the complex formatting work has already been done. But there is one disadvantage: the text, in the form of code ASCII, ISO-8859, etc.) has disappeared and the files are voluminous.

As for software applications processing vector data, these are of intermediate complexity. They start, for example, with a PDF file to produce bitmap data and send it to the screen. Since a vector format is a mathematical description of a page, in software terms the freedom of interpretation is limited: tracing a circle on a page is not ambiguous. But it is greater than with a bitmap file: pixelization must be processed, the designers have been able to leave some grey areas in the specifications. Vector formats are often complex, as can be seen simply by consulting the description of PostScript or PDF format, and programming errors or difficulties are more frequent. In terms of advantages the text is often present, the file takes up less space than a bitmap file, and zooming is possible. Here too, the formatting has already been done by another application.

A software application that can process a source file is far more complex. Its aim is to obtain a page description in PDF or another format. With these applications the link between the file content and the final result is the most sustained, the artistic component is greater and the programmer has more freedom. In the final analysis a source file contains very little information in terms of the expected result; it is the task of the software to make the difference.

The problem arises from the fact that for these formats very high level commands are used. What does a tag <h1> signify? The link between a tag and the graphic output is completely arbitrary. No two browsers give the same result. This can be seen using browsers with complex formatting, tables, CSS, etc. What does a "justify" type command signify? Behind this command there must be software to implement an algorithm -varying in effectivenessto perform paragraph justification and hyphenation. And the same RTF file (or another source format) read by OpenOffice and by MS Word will not give the same document, since the justification algorithm is not the same. Most of the work of formatting and graphics is done by the software and not by the source file, which contains only text and commands.

So, in short, there are three different format types and three types of software of varying degrees of complexity. Files in source format are at the start Christian Rossi of the software chain and therefore require the most complex processing. Bitmap files are located at the end of this chain. Therefore, from the point of view of file preservation, the bitmap format is of interest, since the software chain is limited to a single software application. Moreover this software is simple, easy to write or to rewrite. Of course in relation to a file in PDF format many possible functions are lost (hypertext links, zoom, full-text search, etc.). But that is the price to be paid: by moving closer to human beings we move away from the machine with all its potential. And while it is possible to print a digital text document, it should be borne in mind that the existence of an analogue version is not always possible or even necessary with digital data (databases, for example). In terms of reaching a compromise between software complexity and functionality, PostScript and PDF appear to be interesting formats.

In general terms, a reasonable hypothesis is to say that a digital document has a life expectancy as long as the software required for its access is simple and the software chain short. The same applies to hardware intermediaries.

Structure and typography

There is a current trend to limit a text document to its structure. This can be viewed as the disappearance of a typographic culture and is often associated with the development of XML. However in areas such as physics, mathematics or computer science, authors may still pay great attention to formatting and to compliance with typographical rules. These are the main areas in which L A T E X is used. Can a document be limited to its text and its structure expressed in command form? A document is both content and form, in other words it is also graphic, and respecting an author's work means respecting both these aspects. In the same way, what the reader wants is a legible document, not a file. Any typography exists to improve legibility. As for the quality of a document, this plays an important role in the potential pleasure of reading. Concentrating on the structural aspect often makes us forget about graphic aspects, and with them the importance of the software applications controlling the graphics.

Of course, from the point of view of preservation, it is legitimate to ask ourselves questions on the input of each of these components. What needs to be preserved?

In fact the problem arises from the fact that in terms of preservation text documents have a polymorphous aspect: document = text + structure + images A text document consists of text represented using coding (ASCII, ISO-8859, Unicode) in a source file and in graphic form in a viewable file. It also consists of the images included in the document. It is a structure that may be expressed in source files in the form of commands associated with the text or directly in graphic form in a viewable document thanks to formatting and typography. software text + structure + images =⇒ graphics reader graphics =⇒ text + structure + images Take the example of the well-known RFC (Request For Comment ) documents describing the Internet standards. Since their creation in 1969 they have been available in the form of simple ASCII files on the site http://www.rfc-editor.org. Of course, with ASCII the graphics are very simple, without any multilingualism, maths, molecules, music, etc. . . . but it works, and that is sufficient since the Internet exists.

In fact, if typography is of no concern and the document does not have any graphic components, a text file is sufficient for saving information. It can be read with text editor software, which is simpler than a word-processing application.

Note that tools are available to extract text from a L A T E X, RTF or PDF file (such as detex, rtf2text and pdftotext). These tools are also used by the fulltext indexers of search engines to process non-HTML files.

Conversely, if the graphic component is important or we want to preserve the author's formatting from a source file, a complex software chain becomes necessary to access the document as it was created by the author. The software used has to be compatible with that used by the author, preferably the same application and the same version.

Generally speaking the question arises: is it essential to guarantee the absolute integrity of a digital recording or can it be modified along with its consultation chain, preserving only the aspects considered essential? 8 XML -a lasting format, and the software?

What signifies that the XML format is lasting, and is that really the case? With a format such as HTML the tags are defined once and for all by an international consortium, W3C, and are not extensible to suit the user's requirements. XML (eXtensible Markup Language), on the other hand, allows users to create their own From distribution to preservation of digital documents tag sets. OpenOffice XML, TEI and XHTML are examples of tag sets in the document domain. It is therefore possible to create XML tag sets describing the structure of a document (such as TEI, Text Encoding Initiative) as well as tags representing typography or formatting (such as XHTML, OpenOffice XML or XSL-FO). XML defines rules which must be complied with when users create their own tags (every start-tag must have an associated end-tag, no intermingled tags, etc.). For each tag set (whose characteristics are defined by a DTD -Document Type Definition -or an XML schema), a software application to process these tags must be associated.

Therefore there is not really one XML format, but rather formats complying with the rules defined by XML; each one will then use a particular DTD. In fact it is an over-simplification of language to use the term "XML format".

That said, what signifies that XML is lasting? If it is a matter of saying that the Extensible Markup Language (XML) 1.0 W3C recommendation is lasting, why not: the rules that must be complied with when creating tags to comply with version 1.0 of the XML recommendation are lasting.

If however that means that whatever the DTD used, from the point at which the format complies with XML, the information is lasting, then that is debatable. Effectively, as we have already seen, between the file and a result accessible to the user there is always a software application. And there is nothing to guarantee the lasting nature of the software.

One format based on XML may be no more or no less lasting than another XML format. In fact we cannot really talk of a lasting format, it is the software which is or is not lasting. And software rarely is.

In 10 years will we be able to read a document using the XML format of OpenOffice or TEI? Yes, if software that can process this format exists -in fact the problem is the same as for RTF or L A T E X. It is true however that knowing the specifications of a format is a plus, and is even necessary. For example, the specifications of the MS Word format are not known. The potential reader is therefore a prisoner of the entity that knows the format and can write the corresponding software. That said, a format specification cannot replace available software, whether because of specifications that may be incomplete and the new software not fully compatible with the original, or because the financial resources required for its redevelopment are excessive. Moreover, nothing obliges the creator of an XML tag set to publish it. Or the DTD/XML schema may be inexact in relation to the available software applications that are supposed to process it.

It is true that XML has a certain advantage, if we comply with the substance of the recommendation, which is that it is not a binary format. The recommendation states that XML documents should be "human-legible and reasonably clear". The obligation to use standard coding such as Unicode for the text is important.

That said, in terms of preservation XML is one formalism among others, even if the aims of its designers are laudable and it is rather well placed in relation to the competition. The problem, where things are really complex, is at software level, and it is not realistic to believe that all the problems of sustainability can be solved by a matter of formalism.

The use of XML is often associated, in a very positive way, with discovery of the possible separation between structure and presentation, and of the problems posed by proprietary formats. But due to an excess of evangelization, we can be led to forget that a file, even based on XML, still needs a hardware and software chain in order to be consulted.

We could even add that this freedom for users to create their own tags while hiding behind the protection of XML compliance can give rise to problems. For example, in the domain of sound and musical scores, music and XML, there are currently no less than 18 different markup proposals: MusicXML, MusiXML, MusicML, etc. (For example, see a list on http://xml.coverpages.org/xmlMusic.html.) From Esperanto to the Tower of Babel . . . 9 From L A T E X to HTML Format conversion often gives rise to the same problems. Since there are tools in existence for conversion from L A T E X to HTML (H E V E A, T E X4ht, Tralics, etc.), we take a look at the situation. Here is a simplified description of how these tools work.

In fact there are two cases: text, which is easy to process, and the rest. Either there is a correspondence between firstly a L A T E X command and secondly an HTML command that a browser can display (title, bold) and the software performs the conversion, or there is no correspondence. In this case the conversion program runs L A T E X to generate a GIF or PNG image which will be inserted into the HTML document in the form of a link. Some years ago mathematical equations were converted in the form of images, but the more recent tools now convert them into MathML as browsers are beginning to support this format. But extensions of L A T E X also represent chemical molecules or music scores. And in these cases converters to HTML Christian Rossi still generate images.

This type of conversion poses two problems. The first arises from the wealth of L A T E X functions compared with the lesser capacities of the HTML format. Structured information is often converted to images. Secondly, the formatting of PostScript or PDF files generated by L A T E X is known for its quality, while for HTML it depends on the browser used.

L A T E X does not use a binary source format, which is good. But the advantage of L A T E X is not its format. Effectively there is not much difference between \title{My title} and <title>My title</title> The advantages of L A T E X lie in the many features of the software. And changing format also means changing software.

Software and developers

PostScript and PDF formats are widely used, not without reason. However there are in fact very few software applications available for consulting these files. The best known are:

• for PostScript: the Adobe interpreter, Ghostscript;

• for PDF: Acrobat, Ghostscript and Xpdf. And few people are involved in developing these applications. For example, Ghostscript employs 16 people, and Xpdf one person (with some twenty contributors).

The operational knowledge is concentrated in a very small number of people -not because they want to maintain a monopoly but because no one else is really interested. There is a pyramid effect: many users faced with few software choices and few developers. At present this is not a problem; these software applications exist, they work and are maintained, but in the long term this could become a real problem.

To conclude

Long term preservation of digital documents is an ongoing problem. More time is certainly required to stand back and assess the situation. And while formats for which the specifications are not known pose a problem, resolving questions of formalism will not solve all the problems. It is important to remember the importance of hardware and software aspects in respect of preservation of digital documents.

Today we must not think too much in terms of everlasting formats. The formats are not everlasting, neither is the software, still less the hardware. But we must think in terms of file migration and hardware migration, as well as conversion of formats. The difficulties involved in preservation are intrinsic to the same technique that allows such marvels in terms of creation or distribution.

What does the future hold? In fact it is very difficult to guess at possible developments or miracles. Some aspects that appear worrying to us at present will no longer be so in the future, not because the problems have been resolved, but because they have simply ceased to be problems -or because workarounds have been developed.

Note: Within the framework of the movement for open access to knowledge, all the documents listed in the bibliography can be consulted freely on the Web.


Stéphan Clémençon
email: stephan.clemencon@telecom-paristech.fr

Sylvain Robbiano
email: sylvain.robbiano@telecom-paristech.fr

Jessica Tressou
email: jessica.tressou@agroparistech.fr

Maximal Deviations of Incomplete U -statistics with Applications to Empirical Risk Sampling

Keywords: Empirical risk minimization, risk sampling, incomplete U -statistics, ranking, minimum-volume set

It is the goal of this paper to extend the Empirical Risk Minimization (ERM) paradigm, from a practical perspective, to the situation where a natural estimate of the risk is of the form of a K-sample U -statistics, as it is the case in the K-partite ranking problem for instance. Indeed, the numerical computation of the empirical risk is hardly feasible if not infeasible, even for moderate samples sizes. Precisely, it involves averaging O(n d 1 +...+d K ) terms, when considering a U -statistic of degrees (d1, . . . , dK ) based on samples of sizes proportional to n. We propose here to consider a drastically simpler Monte-Carlo version of the empirical risk based on O(n) terms solely, which can be viewed as an incomplete generalized U -statistic, and prove that, remarkably, the approximation stage does not damage the ERM procedure and yields a learning rate of order O P (1/ √ n). Beyond a theoretical analysis guaranteeing the validity of this approach, numerical experiments are displayed for illustrative purpose.

Introduction

In statistical learning theory, the paradigmatic approach to predictive problems is to use data-based estimates of the prediction error to select a decision rule from a class of candidates. In classification/regression, such estimates are sample mean statistics and the theory of Empirical Risk Minimization (ERM in abbreviated form) has been originally developed in this situation, relying essentially on the study of maximal deviations between these empirical averages and their expectations. The tools used for this purpose are mainly concentration inequalities for empirical processes; see [START_REF] Ledoux | Probability in Banach Spaces[END_REF] for instance. One may refer to [START_REF] Boucheron | Theory of Classification: A Survey of Some Recent Advances[END_REF] for a recent account of the theory of classification. Recently, a variety of learning issues, where natural empirical risk estimates are no longer basic sample mean statistics, have received a good deal of attention in the machine-learning literature, requiring to extend the ERM approach. Indeed, in certain problems such as supervised ranking [START_REF] Clémençon | Ranking and empirical risk minimization of U -statistics[END_REF], learning on graphs [START_REF] Biau | Statistical inference on graphs[END_REF] or pairwise dissimilarity-based clustering [START_REF] Clémençon | On U -processes and clustering performance[END_REF], statistical counterparts of the risk are of the form of (generalized) U -statistics; see [START_REF] Lee | U -statistics: Theory and practice[END_REF]. Such empirical functionals are computed by averaging over tuples of sampling observations, exhibiting thus a complex dependence structure. Linearization techniques (see [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF]) are the main ingredient in investigating the behavior of empirical risk minimizers in this setting, the latter permitting to establish probabilistic upper bounds for the maximal deviation of collection of centered U -statistics under adequate conditions by reducing the study to that of standard empirical processes. However, while the ERM theory based on minimization of U -statistics is now consolidated, putting this approach in practice generally leads to face significant computational difficulties, not sufficiently well documented in the machine-learning literature. In many concrete cases, the mere computation of the risk involves a summation which extends over an extremely high number of tuples and runs out of time or memory on most machines. It is the major purpose of this paper to study how a simplistic sampling technique (i.e. drawing with replacement) applied to risk estimation, as originally proposed by [START_REF] Blom | Some properties of incomplete U -statistics[END_REF] in the context of asymptotic pointwise estimation, may efficiently remedy this issue without damaging too much the "reduced variance" property of the estimates, while preserving the learning rates (including "fast-rate" situations). Applications to supervised ranking and to minimum volume set learning are considered here in order to illustrate this remarkable phenomenon.

The paper is structured as follows. As a first go, two important situations where the empirical functional of interest in the learning problem considered is of the form of a (generalized) U -statistic, hardly or not computable in most cases encountered in practice, are described at length in section 2 in order to motivate the subsequent study. Section 3 next recalls key concepts of the theory of incomplete generalized U -statistics and states the main result of the paper, establishing a probabilistic upper bound for the maximal deviation related to a finite collection of incomplete U -statistics, under mild assumptions. Finally, the implications of this result for the aforementioned examples from the learning perspective are thoroughly discussed and illustrated by numerical experiments in section 4. Technical details are postponed to the Appendix section.

Motivation

We start off with motivating the study of maximal deviations of collections of incomplete generalized Ustatistics in the statistical learning context, through two problems, supervised and unsupervised respectively, which shall serve as running examples in this paper.

2.1

First example: K-partite ranking In the Kpartite ranking problem, one has K ≥ 1 independent random vectors X (1) , . . . , X (K) taking their values in a subset of a generally high-dimensional euclidean space X , X ⊂ R d with d ≥ 1 say, with respective probability distributions F 1 (dx), . . . , F K (dx). Informally, the goal is to learn, based on a pooled data set (made of independent observations drawn as the X k 's), a preorder on the input space X , characterized by a scoring function s : X → R transporting the natural order on the real line onto X (x ≤ s x ⇔ s(x) ≤ s(x ) for all (x, x ) ∈ X 2 ), so that the random variable s(X (k) ) stochastically increases, as much as possible, with the label k ∈ {1, . . . , K}. A quantitative performance criterion (when neglecting ties for simplicity) is given by: (2.1) L(s) def = P s(X (1) ) < s(X (2) ) < . . . < s(X (K) ) .

If K independent samples, of independent copies of the r.v. X (k) respectively, are available, (2.2)

X (k) 1 . . . , X (k) n k with n k ≥ 1 for 1 ≤ k ≤ K,
a natural empirical counterpart of the ranking performance criterion is:

(2.3) L n (s) = n1 i1=1 • • • n K i K =1 I n s(X (1) i 1
)<...<s(X

(K) i K ) o n 1 × • • • × n K ,
where n = (n 1 , . . . , n K ) and I {E} denotes the indicator function of any event E. The performance of empirical maximizers of the quantity (2.3) (or of variants of the latter performance measure) over a class S of scoring function candidates has been investigated in several papers, mainly in the bipartite context (i.e. for K = 2), under various complexity assumptions for S; see [START_REF] Agarwal | Generalization bounds for the area under the ROC curve[END_REF][START_REF] Clémençon | Ranking and empirical risk minimization of U -statistics[END_REF] among others. In a variety of applications (information retrieval, design of recommender systems for instance), the number of classes K and/or the sample sizes n k are fairly large, so that the number of terms to be summed in (2.3),

n 1 × • • • × n K namely, is prohibitive.
As an illustration, one may refer to the public databases LETOR (available at http://research.microsoft.com/∼letor/), which can be used to evaluate search engines for ranking documents according to their degree of pertinence for specific requests in particular (see [START_REF] Liu | Letor: Benchmark dataset for research on learning to rank for information retrieval[END_REF]), where K = 5 and the sample sizes are very huge for most queries. (2.4)

E m = P p=1 c m,p • Q p .
for 1 ≤ m ≤ M , denoting by Q p the quantity of food item No. p consumed per week by an individual drawn at random in the population studied and by c m,p the (random) contamination level related to food item No. p and pollutant No. m. In the field of food safety, risk assessors are interested in building confidence regions for the risk exposure

E in R M + : (2.5) R α = arg min λ(R) : P {E ∈ R} ≥ α, R ∈ B(R M + ) ,
where Lebesgue measure on R M + is denoted by λ and the set of borelian subsets of R M + by B(R M + ). For values of the level α close to 1, such minimum volume sets (MVsets in short; see [START_REF] Polonik | Minimum volume sets and generalized quantile processes[END_REF]) describe regions where the exposure distribution is most concentrated, exposures lying in their complementary sets being possibly interpreted as "abnormal". The construction of confidence regions for the risk exposure is based on the observation of the dietary behavior of J individuals independently drawn from the population, yielding an i.i.d. sample {Q i = (Q i,1 , . . . , Q i,P ) : 1 ≤ i ≤ J} and on a database where a number L m,p of measures of contamination in pollutant m for food item p, for 1 ≤ p ≤ P and 1 ≤ m ≤ M , are gathered, {c m,p = (c m,p,1 , . . . , c m,p,Lm,p )}. Based on these data, the probability involved in the constraint of the MV-set problem (2.5) is estimated by the empirical quantity given by:

P{E ∈ R} = J M m=1 P p=1 L m,p -1 × J i=1 L1,1 l1,1=1 • • • L M,P l M,P =1 I n ( P P p=1 c m,p,lm,p •Qi,p) 1≤m≤M ∈R o ,
and the level α is replaced by α -φ, where φ is some tolerance level, depending, roughly speaking, on the order of magnitude of sup

R∈R | P{E ∈ R} -P{E ∈ R}|,
where R is the class of Borelian sets over which the search is performed. Refer to [START_REF] Scott | Learning Minimum Volume Sets[END_REF] for precise results following in the footsteps of those in ERM theory. In practice, averaging over the J × M m=1 P p=1 L m,p terms appearing in the formula above is generally infeasible. In [START_REF] Bertail | Incomplete generalized U -statistics for food risk assessment[END_REF] for instance, where estimation of the probability that the risk exposure to Ochratoxin A exceeds a critical threshold is considered, this corresponds to 4 × 10 21 terms!

Uniform approximation of Generalized U -statistics through sampling

As shall be seen below, the statistics considered in the previous section are (generalized) U -statistics, which can be uniformly approximated by Monte-Carlo versions whose computation cost is drastically reduced. This will be next proved to be an essential tool for investigating the performance of decision rules learnt through optimization of such empirical quantities.

Definitions and key properties

For clarity, we recall the definition of generalized U -statistics, the simplest extensions of standard sample mean statistics.

Properties and asymptotic theory of U -statistics can be found in [START_REF] Lee | U -statistics: Theory and practice[END_REF].

Definition 1. (Generalized U -statistic) Let K ≥ 1 and (d 1 , . . . , d K ) ∈ N * K . Let (X (k) 1 , . . . , X (k)
n k ), 1 ≤ k ≤ K, be K independent samples of i.i.d. random variables, taking their values in some space X k with distribution F k (dx) respectively. The generalized (or Ksample) U -statistic of degrees (d 1 , . . . , d K ) with kernel

H : X d1 1 × • • • × X d K K → R, square integrable with respect to the probability distribution µ = F ⊗d1 1 ⊗ • • • ⊗ F ⊗d K K , is defined as (3.6) U n (H) = I1 . . . I K H(X (1) I1 ; X (2) I2 ; . . . ; X (K) I K ) n1 d1 × • • • n K d K ,
where the symbol I k refers to summation over all n k d k subsets X (k)

I k = (X (k) i1 , . . . , X (k) i d k ) related to a set I k of d k indexes 1 ≤ i 1 < . . . < i d k ≤ n k . It is said symmetric when H is permutation symmetric in each set of d k arguments X (k) I k .
Returning to the first example of the previous section, we observe that, for a fixed scoring function s(x), the quantity (2.3) is a K-sample U -statistic of degree (1, 1, . . . , 1) with kernel given by:

H s (x 1 , . . . , x K ) = I {s(x1)<s(x2)<•••<s(x K )}
for (x 1 , . . . , x K ) ∈ X K . In a similar manner, considering the functional involved in the second example, this corresponds to a K = (M × P + 1)-sample U -statistic of degree (1, 1, . . . , 1), with kernel given by: H R (q, c) = I n (

P P p=1 cm,p•qp) 1≤m≤M ∈R o ,
for q = (q 1 , . . . , q P ) ∈ R P Beyond these two examples, many statistics used for pointwise estimation or hypothesis testing are actually U -statistics (e.g. the sample variance, the Gini mean difference, the Wilcoxon Mann-Whitney statistic, Kendall tau), their popularity mainly arise from their "reduced variance" property: the statistic U n (H) has minimum variance among all unbiased estimators of the parameter

θ(H) = E[H(X (1) 1 , . . . , X (1) d1 , . . . , X (K) 1 , . . . , X (K) d k )].
Asymptotics. Classically, the limit properties of these statistics (LLN, CLT, etc.) are investigated in an asymptotic framework stipulating that, as the full sample size

n def = n 1 + . . . + n K
tends to infinity, we have: n k /n → λ k > 0 for k = 1, . . . , K. They can be established by means of a linearization technique (see [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF]), permitting to write U n (H) as a sum of K basic sample mean statistics (of the order O P (1/ √ n) each, after recentering), plus possible degenerate terms (termed degenerate U -statistics). This method is extensively used in [START_REF] Clémençon | Ranking and empirical risk minimization of U -statistics[END_REF] for instance.

As previously seen on the running examples considered in this paper, in practice, the number

K k=1 n k d k
of terms to be summed up to compute (3.6) is generally prohibitive. As a remedy to this computational issue, in the seminal contribution [START_REF] Blom | Some properties of incomplete U -statistics[END_REF], the concept of incomplete generalized U -statistic has been introduced, where the summation in formula (3.6) is replaced by a summation involving much less terms, extending over low cardinality subsets of the n k d k d k -tuples of indices, 1 ≤ k ≤ K, solely. In the simplest formulation, the subsets of indices are obtained by sampling with replacement, leading to the following definition.

Definition 2. (Incomplete Generalized U - statistic) Let B ≥ 1.
The incomplete version of the U -statistic (3.6) based on B terms is defined by:

(3.7) U B (H) = 1 B (I1, ..., I K )∈D B H(X (1)
I1 , . . . , X (K)

I K ),
where D B is a set of cardinality B built by sampling with replacement in the set Λ = {((i

(1) 1 , . . . , i (1)
d1 ), . . . , (i

(K) 1 , . . . , i (K) d K )) : 1 ≤ i (k) 1 < . . . < i (k) d k ≤ n k , 1 ≤ k ≤ K}.
Remark 1. (Alternative sampling schemes.) We point out that, as proposed in [START_REF] Janson | The asymptotic distributions of incomplete U -statistics[END_REF], other sampling schemes could be considered, sampling without replacement or Bernoulli sampling in particular. The results of this paper could be extended to these situations. Due to space limitation, we restrict our attention here to the sampling with replacement scheme.

In practice, B should be chosen much smaller than the cardinality of Λ, namely #Λ = K k=1 n k d k , in order to overcome the computational issue previously mentioned. We emphasize that the cost related to the computation of the value taken by the kernel H at a given point (x (1) I1 , . . . , x (K) I K ) depending on the form of H is not considered here, focus is on the number of terms involved in the summation solely. As an estimator of θ(H), the statistic (3.7) is still unbiased but its variance is naturally larger than that of (3.6). Precisely, we have

Var( U B (H)) = (1 -1/B)Var(U n (H)) + O(1/B),
as B → +∞; refer to [START_REF] Lee | U -statistics: Theory and practice[END_REF] (see p. 193 therein). Incidentally, we underline that the empirical variance of (3.6) is not easy to compute neither since it involves summing approximately #Λ terms and bootstrap techniques should be used for this purpose, as proposed in [START_REF] Bertail | Incomplete generalized U -statistics for food risk assessment[END_REF]. The asymptotic properties of incomplete Ustatistics have been investigated in several articles; see [START_REF] Brown | Reduced U -statistics and the Hodges-Lehmann estimator[END_REF][START_REF] Enqvist | On sampling from sets of random variables with application to incomplete U -statistics[END_REF][START_REF] Janson | The asymptotic distributions of incomplete U -statistics[END_REF]. The angle embraced in the present paper is of quite different nature, the key idea we promote here is to use incomplete versions of collections of U -statistics in learning problems such as those described in section 2. The result established in the next section shows that this approach solves the numerical problem, while not damaging the learning rates.

3.2 Main result -Uniform approximation of Ustatistics by incomplete U -statistics Under certain assumptions on the collection H of (symmetric) kernels H considered, concentration results established for Uprocesses (i.e. collections of U -statistics) may extend to their incomplete versions, as revealed by the following theorem. As the goal of this paper is to present the main ideas rather than formulating results at a high level of generality owing to space limitations, we consider the (not that restrictive) situation where the class H of kernels is a VC major class of functions of finite Vapnik-Chervonenkis dimension; see [START_REF] Dudley | Uniform Central Limit Theorems[END_REF].

Theorem 3.1. (Maximal deviation) Let H be a col- lection of bounded symmetric kernels on Ω = K k=1 X d k k of finite VC dimension V < +∞. We set M H = sup (H,x)∈H×X |H(x)|.
Then, the following assertions hold.

(i) For all η > 0, we have:

∀n = (n 1 , . . . , n K ) ∈ N * K , ∀B ≥ 1, P sup H∈H U B (H) -U n (H) > η ≤ 2(1+#Λ) V × e -Bη 2 /M 2 H .
(ii) For all δ ∈ (0, 1), with probability at least 1 -δ, we have:

∀n k ≥ 1, 1 ≤ k ≤ K, (3.8) 1 M H sup H∈H U B (H) -E U B (H) ≤ 2 2V log(1 + κ) κ + log(2/δ) κ + V log(1 + #Λ) + log(4/δ) B ,
where κ = min{ n 1 /d 1 , . . . , n K /d K } and x denotes the integer part of any real number x.

Refer to the Appendix for the proof. The bounds stated above show that, for a number B = B n of terms tending to infinity as n → +∞ at a rate O(n), the maximal deviation sup

H∈H | U B (H) -θ(H)| is asymptotically of the order O P (n -1/2 ), just like sup H∈H |U n (H) -θ(H)|.
Remarkably, except in the case K = 1 and d K = 1 solely, using such incomplete U -statistics thus yields a significant gain in terms of computational cost and preserves the order of the probabilistic upper bounds for the uniform deviation.

Applications

We now discuss the consequences of Theorem 3.1 through the examples introduced in section 2 (notice that, in both cases, we have M H = 1). Beyond theoretical guarantees, the performance of algorithms based on incomplete versions of the empirical counterpart of the functional of interest is illustrated by numerical results, supporting the efficiency of the sampling approach promoted in this paper in the machine-learning context.

4.1 Sampling the risk in K-partite ranking We place ourselves in the framework described in subsection 2.1. Here, the full sample size is n = n 1 + . . .

+ n K . Let (b 1 , b 2 , . . . , b K ) be a sequence of nonnegative integers such that: ∀k ∈ {1, . . . , K}, b k ∼ n 1/K k ∼ n 1/K as n → +∞.
The sampling scheme consists, for 1

≤ k ≤ K, of drawing with replacement b k observations in the sample No. k: X (k) i1 , . . . , X (k) i b k . Set B = b 1 × • • • × b K .
Based on the sampled data, we compute the following estimate of the ranking performance criterion

L B (s) = 1 B b1 l1=1 • • • b K l K =1 I 8 < : s(X (1)
i (1) l 1

)<...<s(X The following result provides a rate bound for the ranking performance of the scoring function above (neglecting the bias term).

(K) i (K) l K ) 9
Corollary 4.1. Suppose that S is a VC major class of functions of finite VC dimension V < +∞. Then, for all δ ∈ (0, 1), we have with probability at least 1 -δ:

∀n ∈ N * K , (4.10) max s∈S L(s) -L( s B ) ≤ c V log(#Λ/δ) n ,
for some constant c < +∞.

The proof immediately derives from Theorem 3.1, details are left to the reader. One should pay attention to the fact that the deficit of ranking performance of the rule obtained through maximization of statistics computed by averaging O(n) terms is thus of the same order as that of arg max s∈S L n (s), whose computation requires to evaluate averages extending over O(n K ) terms.

Remark 2. (On fast rates) In the bipartite setup (i.e. K = 2), situations where fast rates of convergence can be achieved by arg max s∈S L n (s) have been exhibited; see [START_REF] Clémençon | Ranking and empirical risk minimization of U -statistics[END_REF]. In this regard, we point out that, in these situations, the same rate bounds can be attained by s B , at the price of a higher computational cost (i.e. of a larger asymptotic order for B) however.

A numerical example with K = 5. As an illustration, we display below some results related to the performance of the algorithm SVMrank (implemented with default parameters, linear kernel and C = 20; see [START_REF] Herbrich | Advances in Large Margin Classifiers, chapter Large margin rank boundaries for ordinal regression[END_REF]) using the SVM-light implementation available at http://svmlight.joachims.org/. We simulated a mixture of 5 Gaussian distributions on R 2 with means m 1 , . . . , m 5 respectively, where m i = (i/6, i/6) for 1 ≤ i ≤ 5, and same covariance matrix (1/15, 0; 0, 1/15), so that an optimal scoring function (w.r.t. the criterion (2.1)) is given by: s(x, y) = x + y for all (x, y) ∈ R 2 . We independently drew 50 training samples of size n = 10 000 (2 000 per class) and a test sample of size 10 000. Inside each class, we drew with replacement b observations and formed the dataset D b , for b = 20, 100. The results, averaged over the 50 replications, are reported in Table 1. Figures speak volume. We see that, even for b = 20 (i.e 1% of the data), the performance is close to the optimum L * for a computation time reduced by a factor 10000. For b = 100 (i.e 5% of the data), it is quasi-optimal, with a gain in time of a factor greater than 500.

LETOR4.0 datasets.

We also implemented the approach promoted in this paper on the benchmark LETOR datasets, (see research.microsoft.com/en-us/um/people/letor/), by means of the same ranking algorithm as that used in the previous experiment. To be more precise, we used the two query sets MQ2007 and MQ2008, where pairs "page-query" assigned to a discrete label ranging from 0 to 2 (i.e. "non-relevant" -"relevant" -"extremely relevant") are gathered. In both datasets, 46 features are collected, over 69 623 instances in MQ2007 and over 15 211 instances in MQ2008. In each case, an estimate of the ranking risk L has been computed through 5 replications of a five-fold cross validation procedure, the results (mean and standard error) are reported in Tables 2 and3. We also compute the Kendall τ statistic τ between the resulting rankings (recall that it ranges from -1 "full disagreement" to +1 "full agreement"), when using 1% ,5%, 10%, 20% and 100% of the data in each of the K = 3 samples. The results are reported in the Tables 2 and3. In both experiments, we observe that, as b k /n k increase, the ranking performance of the rules produced by the algorithm gets rapidly closer and closer to that of the ranking rule based on the whole dataset.

Sampling the distribution of risk exposures

We now turn to the second example; see subsection 2.2. In order to avoid the computation of P{E ∈ R}, which involves summing over #Λ = J The result below shows that, if the number B of exposure values computed through the sampling scheme is of the order O(n), the performance of R α is then comparable to that of the region whose selection is based on the quantities P{E ∈ R}, R ∈ R. and

P E ∈ R α ≥ α -2Φ(B, n, δ).
This is a straightforward consequence of Theorem 3.1, details are omitted (refer to the argument of Corollary 6 in [START_REF] Scott | Learning Minimum Volume Sets[END_REF] for further details).

Confidence regions for joint dietary exposure to cadmium, mercury, PCB's and sodium. Below, we present numerical results where approximate solutions of (4.13) are built by means of a dyadic recursive partitioning scheme of the exposure space; see [START_REF] Blanchard | Oracle bounds and exact algorithm for dyadic classification trees[END_REF] as well as section 7 in [START_REF] Scott | Learning Minimum Volume Sets[END_REF]. Dietary exposures to the four substances are built based on French data surveys. Contamination data (cadmium, mercury, PCB's) come from the second French Total Diet Study, [START_REF] Anses | Second french total diet study (tds 2): Report 1 and 2[END_REF], and the sodium level is extracted from the Ciqual table describing French food composition table; see http://www.anses.fr/TableCIQUAL/. Based on those datasets, P = 5 food groups containing either one or more substances were composed (dairy products, meat and eggs, fish, fruit and vegetables, other foods) according to the similarity of their contamination/composition levels totalizing m,p L m,p = 2341 observations. Consumption data for French adults (J = 2488, aged 18-79 yo) was extracted from the INCA2 database, related to a French consumption survey conducted by the French Agency for Food, Environmental and Occupational Health Safety in 2009, [START_REF]Report of the 2006/2007 Individual and National Study on Food Consumption 2 (INCA 2)[END_REF]. Interviewed individuals reported their food consumption over 7 days, together with some sociodemographic variables including their body weights. Vectors of exposure (in R 4 ) were generated by selecting data from the consumption and contamination/composition datasets at random with replacement. Whereas #Λ is equal to 6.9 10 33 in this example, a MV-set of level α = 95% has been learnt with only B = 5000, 10 000, or 20 000 exposure vectors. The resulting region was tested with a much larger sample of exposures (1 000 000). Table 4 summarizes the resulting test mass and volume obtained for the different sampling sizes considering in turn M = 2 (cadmium and mercury), M = 3 (cadmium, mercury, PCB's) or all M = 4 substances; the total number of observations n and the total number of terms involved in the "complete" U -statistic #Λ are given in Table 4. The performance of the algorithm clearly decreases when the dimension of the problem is increased. In the case M = 2, the optimal region related to the exposure to cadmium and mercury is illustrated in Fig. 4.2 (the exposure values are normalized to (0, 1)). In higher dimensions, resulting regions can simply be projected on pairs of substances (the matlab/mex code we used is available at http://web.eecs.umich.edu/∼cscott/code.html).

Conclusion

Though of great simplicity, the results stated in this paper are of crucial importance in practice in the "big data" era. They hopefully shed light on tractable strategies for implementing learning techniques, when the (risk) functional has a statistical counterpart which is of the form of a U -statistic. Whereas the theoretical properties of decision rules based on optimizing such statistics are becoming well-documented in the machinelearning literature, computational issues related to the practical implementation of learning algorithms dedicated to these optimization problems had not been tackled, to the best of our knowledge. The essential contribution of this paper is to provide theoretical/empirical evidence that using incomplete U -statistics as estimates of the criterion of interest may provide a simple and elegant way of dramatically reducing computational cost in practice, while yielding nearly optimal solutions. The analysis, carried out here in a finite VC dimension framework, suggests to investigate next the use of such statistics for model selection issues and to study concentration properties of weighted multinomial random variables involved in the maximal deviation between Ustatistics and their incomplete versions.

  m,1 , . . . , c m,P ), m = 1, . . . , M ) ∈ R P ×M + .

,

  and consider the maximizer over a class S of scoring function candidates: (4.9) s B = arg max s∈S L B (s).

  m,p terms and is based on n = J + M m=1 P p=1 L m,p observations, we draw with replacement B times in the index set {1, . . . , J} × M m=1 P p=1 {1, . . . , L m,p }, so as to get a set of indices D B of cardinality B. For any borelian R ⊂ R M , the probability that exposure lies in the region R is estimated by the incomplete U -statistics: (4.11) P B {E ∈ R} = 1 B × (i,(lm,p))∈D B I n ( P P p=1 e c m,p,lm,p • e Qi,p) 1≤m≤M ∈R o .Suppose that the class R is of finite VC dimension V < +∞. Let α ∈ (0, 1) be the target mass and δ ∈ (0, 1) be the desired confidence level. Define the complexity penalty by: (4.12) Φ(B, n, δ) = 2 2V log(1 + κ) κ + log(2/δ) κ + V log(1 + #Λ) + log(4/δ) B . Consider the solution R α of the constrained optimization problem: (4.13) maximize λ(R) over R subject to P{E ∈ R} ≥ α -Φ(B, n, δ).

Corollary 4 . 2 .

 42 For all δ ∈ (0, 1), we have with probability at least 1 -δ:λ R α ≤ inf R∈R: P{E∈R}≥α λ(R)

Figure 2 :

 2 Figure 2: Cloud of rebuilt bivariate exposures to cadmium (x-axis) and mercury (y axis)and MV-set based on the incomplete criterion (B = 10 000).

Table 1 :

 1 Comparison of the empirical ranking performance : "ranking" experiment -L * = 0.1525

	% of data	1%	5%	100%
	L	0.1497 0.1520 0.1524
	σ	0.0041 0.0008 0.0002
	time (in seconds)	10	200	148523

Table 2 :

 2 Empirical ranking performance : "LETOR 2008".

	%	1%	5%	10%	20%	100%
	L 0.3735 0.3939 0.3992 0.4015 0.4088
	σ 0.0038 0.0040 0.0025 0.0027 0.0006
	τ	0.7648 0.8653 0.8937 0.9154	1

Table 3 :

 3 Empirical ranking performance : "LETOR 2007".

	%	1%	5%	10%	20%	100%
	L 0.2715 0.2894 0.2949 0.2963 0.3000
	σ 0.0077 0.0027 0.0017 0.0019 0.0004
	τ	0.6621 0.7651 0.8328 0.8501	1

Table 4 :

 4 Performance of the MV-set algorithm -M substances. Each cell contains the optimal volume and the test mass for a MV-set of level 95%.

	M	2	3	4
	n	3179	3529	4829
	# Λ	2.96E+14 9.48E+21 6.89E+33
	B = 5 000	0.01481	0.00146	0.00002
		(95.2%)	(93.7%)	(92.3%)
	B = 10 000	0.01423	0.00151	0.00002
		(94.5%)	(94.1%)	(93.2%)
	B = 20 000	0.01412	0.01407	0.00162
		(95.0%)	(95.0%)	(94.5%)

For convenience, we introduce the random sequence = (( k (I)) I∈Λ ) 1≤k≤B , where k (I) is equal to 1 if the tuple I = (I 1 , . . . , I K ) has been selected at the k-th draw and to 0 otherwise: the k 's are i.i.d. random vectors and, for all (k, I) ∈ {1, . . . , B} × Λ, the r.v. k (I) has a Bernoulli distribution with parameter 1/#Λ. We also set X I = (X

Equipped with these notations, observe first that one may write:

where

for any (k, I) ∈ {1, . . . , B} × Λ. It follows from the independence between the X I 's and the (I)'s that, for all H ∈ H, conditioned upon the X I 's, the variables Z 1 (H), . . . , Z B (H) are independent, centered and almost-surely bounded by 2M H (notice that I∈Λ k (I) = 1 for all k ≥ 1). By virtue of Sauer's lemma, since H is a VC major class with finite VC dimension V, we have, for fixed X I 's:

Hence, conditioned upon the X I 's, using the union bound and next Hoeffding's inequality applied to the independent sequence Z 1 (H), . . . , Z B (H), for all η > 0, we obtain that:

which proves the first assertion of the theorem. Notice that this can be formulated: for any δ ∈ (0, 1), we have with probability at least 1 -δ:

The second part of the theorem straightforwardly results from the first part combined with the following result, which extends Corollary 3 in [START_REF] Clémençon | Ranking and empirical risk minimization of U -statistics[END_REF] to the Ksample situation.

Lemma 5.1. Suppose that Theorem 3.1's hypotheses are fulfilled. For all δ ∈ (0, 1), we have with probability at least 1 -δ,

1 , . . . , X (1) n1 , . . . , X

, . . . , X (K)

1 , . . . , X

d1 , . . . , X

, . . . , X

d1+1 , . . . , X

2d1 , . . . , X (K)

κd1-d1+1 , . . . , X (K)

for any H ∈ H. Recall that the K-sample U -statistic U n (H) can be expressed as

σ1(1) , . . . , X

where S m denotes the symmetric group of order m for any m ≥ 1. This representation as an average of sums of κ independent terms is known as the (first) Hoeffding's decomposition; see [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF]. Then, using Jensen's inequality in particular, one may easily show that, for any nondecreasing convex function ψ : R + → R, the quantity

where we set H = H -θ(H) for all H ∈ H. Now, using standard symmetrization and randomization arguments (see [START_REF] Giné | Some limit theorems for empirical processes[END_REF] for instance) and the bound above, we obtain that

where

(l-1)d1+1 , . . . , X

is a Rademacher average based on the Rademacher chaos 1 , . . . , κ (independent random symmetric sign variables), independent from the X (k) i 's.

We now apply the bounded difference inequality (see [START_REF] Mcdiarmid | On the method of bounded differences[END_REF]) to the functional R κ , seen as a function of the i.i.d. random variables ( l , X

(l-1)d1+1 , . . . , X

ld1 , . . . , X (K) (l-1)d K +1 , . . . , X (K) ld K ), 1 ≤ l ≤ κ: changing any of these random variables change the value of R κ by at most M H /κ. One thus obtains from (5.14) with ψ(x) = exp(λx), where λ > 0 is a parameter which shall be chosen later, that: (5.15)

Applying Chernoff's method, one then gets:

(5.16) P sup

Using the bound (see Eq. ( 6) in [START_REF] Boucheron | Theory of Classification: A Survey of Some Recent Advances[END_REF] for instance)

and taking λ = 2κ(η -2E[R κ ])/M 2 H in (5.16) finally establishes the desired result.


B Léger

O Naud

D Gouache

Specifying a strategy for deciding tactical adjustment of crop protection using CPN tools

Keywords: Farm management, Crop protection, Workflow modelling, Decision support system, Coloured Petri net

Crop protection is a key activity for farmers. There is a need to improve the practice and use less chemical pesticides. We hypothesized that farmers may be overwhelmed by the amount of data available. Therefore we proposed the concept of crop protection decision workflow system (CPDeWS) to guide them in interpreting the information in tactical adjustments of treatment decisions. We provide here a short introduction to Petri nets, and show how the CPDeWS concept was mapped onto Petri nets, in the case of wheat. Finally we adopt a broad view to discuss our design and modelling choices, that are applicable to a wide set of crop protection and crop management problems.

Introduction

Modern agriculture is confronted with the seemingly paradoxical challenges of both increasing quantity and raising quality of food production (while the prices should be kept low and the financial aids reduced). Here quality encompasses preserving the environment and the people in order to sustain production infinitely while producing highly healthy and nutritive food. These challenges greatly question the agronomic know how of the whole community. But it is also a driver for a more optimised agriculture, where production factors are used in a rational and justified way, consistent with objectively assessed risks.

In these challenges, the ICT community has already taken up its share, integrating novel technologies from the field scale using data provided by precision agriculture [START_REF] Steinberger | Mobile farm equipment as a data source in an agricultural service architecture[END_REF]) up to the farm information management systems scale and extending further upscale toward the larger agro-business environment using service oriented approaches (SOA). For instance [START_REF] Ntaliani | Agricultural e-government services: An implementation framework and case study[END_REF] illustrate this drive in the implementation of a business process management in e-government. Several case studies from the LEI Wageningen group [START_REF] Verdouw | Process modelling in demanddriven supply chains: A reference model for the fruit industry[END_REF][START_REF] Wolfert | Business Process Modeling of the Pesticide Life Cycle: a service-oriented approach[END_REF][START_REF] Wolfert | Organizing information integration in agri-food--A method based on a service-oriented architecture and living lab approach[END_REF]) illustrate how SOA helps tighter integration of the various levels of the agro-food supply chain.

Another trend is the large effort toward providing Agri-ICT professionals with standards for modern agricultural information systems and data interchange formats between more and more scattered resources -see the Future Farm project1, agroXML2 or Agro EDI Europe 3 .

All these authors show a drive toward a more data intensive agriculture which aims at a more knowledge intensive agriculture. They insist on using information and communication technologies (ICT) to leverage change and innovation among users and on developing reusable business process models. They show that systems analysis and ICT born specification formalisms are very helpful to farm management reengineering [START_REF] Fountas | A model of decision-making and information flows for information-intensive agriculture[END_REF][START_REF] Sørensen | Conceptual model of a future farm management information system[END_REF][START_REF] Nash | Development of a model of data-flows for precision agriculture based on a collaborative research project[END_REF].

Our own research effort is situated along a similar line. For instance, we have shown (Léger & Naud 2009) that ICT specification languages such as Statechart [START_REF] Harel | The RHAPSODY semantics of Statecharts (or, on the executable core of the UML) -(Preliminary version)[END_REF]) can be used to leverage expertise from a pathologists' group. Our general aim is at designing operational decision support systems in crop protection. [START_REF] Clouaire | Modelling and simulating work practices in agriculture[END_REF] have underlined that, compared to the many simulation tools built to study isolated agronomic and technological aspects of the production processes, few works have dealt with the modelling and simulation of farmers' management and work practices. We adopted a design approach which investigates this point of view: "how to design a decision support system as a process, with emphasis on work organisation, given the requirements of the crop?" We name our proposition: Crop Protection Decision Workflow System (CPDeWS). We consider that in many cases in modern crop protection, the main difficulty for farmers to achieve low input protection lies in a lack of methods to organize and interpret the large amounts of available information. Therefore we have proposed to develop tools on the basis of crop protection expertise that will guide the farmer throughout the season to make operational decisions about crop protection sprayings against several target diseases. [START_REF] Fountas | A model of decision-making and information flows for information-intensive agriculture[END_REF] proposed to document the farmer's data flow for each decision. Similarly we integrate crop protection decision making as a decision workflow from the beginning of the season to its end (Léger, et al. 2010). Protecting a crop is a control problem which can be decomposed into a production system, an environment and a control system. Although the overall system is by nature a hybrid system, the controller, i.e. the decision system we designed, can be modelled as a discrete event system (DES) [START_REF] Naud | Discrete event systems: from simulation to the temporal analysis of the decision in agriculture) e-STA-Spécial STIC&Environnement[END_REF]. The DES modelling paradigm has the great advantage of being simpler to analyse than hybrid systems. We have also discussed in (Léger 2008, ch.2) that in the current state of knowledge and under the objective of low input crop protection, optimal control for the crop protection problem cannot necessarily be computed. This means that crop protection experts will be able to propose adjustment strategies that may prove as efficient as any optimal crop protection strategy but may lead to fewer treatments. Indeed the experts may be able to manage risk in a more subtle manner than what is nowadays possible to achieve through quantitative computation. The experts have an intimate knowledge of the epidemics and the crop needs that fundamental epidemiology is yet unable to quantify at operational scale within a farm. The design process begins with an expert design which is elicited from the experts as a decision process specification. In the grapevine case study the elicitation was carried out using UML Statecharts as mentioned previously. This article investigates how coloured Petri nets (CPN) have been used to formalise specifications for a wheat case study. The overall approach for design is presented in [START_REF] Léger | Recueil et Formalisation de procédés experts pour conduire une protection intégrée du vignoble (Elicitation and Formalization of an Expert decision workflow to manage an integrated crop protection of the vineyard)[END_REF]Léger, et al. 2010b) and is similar in both grapevine and wheat cases. The rest of the article is structured as follows: the following section provides a quick refresher on Petri nets (PN) and CPN, then describes the overall architecture of the wheat CPDeWS and provides definitions; the Results section consists in an overview of the transcription of the design features into CPN; the last part discusses the choice of decision process modelling to design a crop protection decision support system. Formal framework and design Coloured Petri nets Petri net is a discrete event system modelling formalism presented by Carl Adam Petri in 1962. Petri nets are traditionally used for describing and analysing systems that are characterized as concurrent, asynchronous, distributed, parallel, non deterministic and/or stochastic. Due to their graphical nature, Petri nets (PN) can be used as a visualization technique like flow charts or block diagrams but with much more scope on concurrency aspects.

We have used Timed Hierarchical Coloured Petri nets with the CPN tools software. A detailed presentation of the formalism can be found in [START_REF] Jensen | Coloured Petri Nets[END_REF]. Figure 1 illustrates on some of its principles: places (circles) associated with tokens (which have a data structure, see rectangle), and transitions which depict events and actions (squares). Needs short explanation on "colour" Figure 1. ploughing two fields, modelled as timed hierarchical coloured Petri net

DeWS Design

In this section we will present the architecture of a CPDeWS, illustrated with the example from the wheat CPDeWS: BLé3 and BLé2. Figure 2 presents the architectural organisation of the system. It is composed of three layers: the outermost containing external ressources, an intermediate level allowing to store certain key variables, and the core of the system itself which holds the experts' decision process modelled as a Petri net. Although a discrete event system, the CPDeWS requires a persistence mechanism to hold the latest state of the environment. This mechanism is provided by the "neighbourhood" layer. It is composed of a set of discrete variables. The decision system has full access to these resources in real time. This persistence layer is necessary as the input data for the decision system may be costly to acquire (e.g. field observations) or may be the result of direct input from the user (i.e. not persistent elsewhere). The second reason for this is that the variables hold a discrete interpretation of continuous underlying variables. For instance, in the case of the BLé3 CPDeWS Septoria is monitored using a forecast model. Each time the model is updated, the internal variable (called ILS) is computed on the basis of thresholds which depend on the phenological stage of the plant. At each computation, our system computes the discrete value and saves it. The continuous value needs not to be accessed again for the decision. The third layer of the system is its environment. The environment updates the neighbourhood variables, but can also send real time input events which are directly handled by the decision system (e.g. rain forecasts). This architecture is in essence similar to that presented in [START_REF] Wolfert | Business Process Modeling of the Pesticide Life Cycle: a service-oriented approach[END_REF] for the three layered SOA Architecture. The decision system Because the decision system is the formal transcription of an expertise, the structure of the model is therefore strongly linked to the design choices made by the expert team and by the elicitation method (Léger, et al. 2010;[START_REF] Léger | Recueil et Formalisation de procédés experts pour conduire une protection intégrée du vignoble (Elicitation and Formalization of an Expert decision workflow to manage an integrated crop protection of the vineyard)[END_REF] CPDeWS are organised to control pest management decisions at the plot scale. To simplify the design process, the system was designed with a single plot in mind; however the system is required to be able to manage a whole farm or more.

CPDeWS are tactical adjustment tools which drive crop protection from the beginning of the season until its end. The season is partitioned in decision stages in order to handle the various development stages of the plant and the changes in the nature of the disease risks they face.. The aim of a stage is essentially to decide for each target disease whether a treatment is necessary or not and when to position it during the period. A decision stage is characterized by:

• Its position in the season defined by a start phenological stage or date and by an end date/ phenological stage or a duration.

• A set of active diseases (not all diseases can cause damages throughout the season).

• An objective: the objective is a higher level requirement formulated so as to help the expert define the stage's specifications. It defines what needs to be achieved during the stage. This allows the experts to link the overall CPDeWS crop protection strategy to the implementation of operational decisions.

Input as events

Neighbourhood

Decision System input events (see figure 2).

• A decision process: It specifies how to use the available information (decision variables) in order to reach the stage's objective. It specifies the need for more information (leading to field observation), details the synchronisation of the reasoning of several diseases (e.g. treat Septoria along with Eyespot), and establishes priority between different disease risks. The outputs of such decision processes are treatment requests against one or several diseases, and/or observation requests.

The number of stages depends on the crop, its diseases and possibly climate, but it also depends on some strategic production choices made by the farmer. For instance, BLé3 is broken down in 6 stages while the BLé2 CPDeWS has 5. The difference between the two is explained mostly by the work load the farmer wishes to invest in the protection of his/her wheat (i.e. the importance of wheat production in his farming system). [START_REF] Allain | Stratégies fongicides dans l'Ouest. Quels sont les critères de décision des agriculteurs ?[END_REF] Observations are also a key structure in a CPDeWS, because the information provided by a fresh observation from the field will gain priority over all model outputs provided the observation of a given disease can be a relevant estimator of the disease risk. Observations requests can be mandatory or conditional, i.e. triggered by specific states of the decision process.

The system also outputs requests which are sent to an operational sub-system which is responsible for the selection of the fungicide mixture (Hernandez et al. 2010) and the grouping of plots in order to realise spraying batches. This sub-system is out of the scope of this presentation. After a spraying the CPDeWS needs to be fed with the applied fungicide active period duration against each disease, as these variables constitute an important aspect of any direct control based crop protection.

Results -Encoding the structures of the DeWS

In this section we will present how the different structures presented were mapped into coloured Petri net specifications using the CPN tools software.

Global structures

The CPDeWS is a workflow and its stages are sub-workflows. Within the CPN modelling framework, stages are mapped onto hierarchical transitions with the stages' decision processes modelled as sub-processes.

The various plots in the system are mapped onto a unique identification colour (id colour).

The id colour is used to retrieve the information relative to a specific plot whenever necessary.

For instance, phenology is stored in a dedicated global place. Global places are a special type of places accessible within any sub-processes of the system. We use these to model global variables.

Figure 3. at the beginning of Stage 1, Phenology control the plots access to the stage concurrent processes

The phenological information for each plot is encrypted in a timed token composed of the plot id colour and the phenological stage colour. In simulation mode, each plot at each phenological stage is loaded into the phenology manager during the initialisation phase. Then the time mechanism ensures that no phenology token can be accessed before the simulation time reaches the date at which the phenological stage is reached.

Stages specific constructs

At the beginning of each stage's sub-process, the start condition is expressed as a guard condition on the stage's initial transition. As shown in figure 3, the transition will fire only if a phenology token with colour Z31 is "active". The transition's inputs are a plot and a phenology token. The transition outputs an identical phenology token and one plot token for each line of reasoning.

Mapping the reasoning.

In the Blé3 CPDeWS, each disease is managed along a line of reasoning which consists in the following ordered decision rules mapped as hierarchical transitions. i) checking the plot's strategic risk (the a priori risk); if the plot is susceptible to a given disease risk, the system ii) will wait until the active period of the previous treatment is over and then iii) it will activate regional risk monitoring. This monitoring leads either to iv) the request of a field observation or simulation of a forecast model or v) to the conclusion that no action was necessary during that stage, at the latest when the end time of the stage is reached. This concluding place is reachable from all the decision steps. Figure 4 illustrates this generic reasoning mechanism. Note that in this simplified expression, the reasoning given above is rather generic in crop protection. One important added value of CPDeWS and decision process modelling lies precisely in the possibility to depart from this general process to adapt to the period and the disease specifics. The a priori variables like the other decision variables (see table 1) are mapped as composite colour tokens identified by the plot id colour and a value colour, which can be either of colour type Boolean or from the colour set {'low', 'medium', 'high'}. Like phenology data, the decision variables are stored in global places which can be accessed anywhere in the net.

Handling decisions

A decision leads to two outputs. On the one hand the plot token moves in the net as its "decisional status" evolves until a final decision is reached for a given disease and a given stage.

On the other hand, the decision may produce an observation request token or a treatment request token.

Observation requests are characterised by plot id token. Treatment requests are modelled as tokens which have a triplet for descriptor: ('plot id', 'current treatment stage', 'target disease').

Observation and treatment requests are each routed to a specific global place. These two places are connected to the operational management sub-system which is responsible for managing the workload and planning operations. That sub-system is independent from the decision system. Therefore time and priority constraints would need to be specified through the requests tokens for it to be taken account of in the planning (but this remains part of our future work). Table 1 summarizes the information provided in this section for the entire BLé CPDeWS.

Discussion

The results given above describe how the CPDeWS concepts were mapped onto the CPN framework. We did not encounter technical limitations due to the framework. However, in the design phase of CPDeWS, we separate the decision part which is modelled, and the biological part which is not. We review in this section reasons and means for the cooperation of models and field experiment in this design stage.

As the proposed design of CPDeWS is the output of expertise (strongly rooted in scientific knowledge and know-how) it is important to assess the validity of the specified adjustment strategies. This should be achieved both through field experiments and through formal methods. Field experiments allow assessing the agronomic efficacy of the decision process [START_REF] Naud | Testing a decision system for Integrated Protection against Mildews -the vine-grower, the adviser, and the computer model[END_REF][START_REF] Naud | Modelling and experimenting crop protection decision workflows: some lessons from GrapeMilDeWS research[END_REF]. However field testing of the efficiency of the proposed crop protection is not sufficient, as we need to show that it is the CPDeWS which is responsible for the level of quality. Therefore, verifying the conformance between the implemented crop protection decisions made and those specified by the CPDeWS is necessary. This is achieved through process conformance checking [START_REF] Rozinat | Conformance checking of processes based on monitoring real behavior[END_REF][START_REF] Cook | Software process validation: quantitatively measuring the correspondence of a process to a model[END_REF]. Two methods have been proposed to assess that the implemented decisions in the field respect the decision process specification (Léger & Naud 2009;Léger 2008 ch.6).

Blending field experiments and formal methods is necessary as there is currently a lack of epidemiological models handling the development of the full complex of diseases a crop is faced with and their control by fungicides (with the notable exception of the work carried out in the DESSAC suite : Parker 2003). In particular, predictive and quantitative modelling of the effects of fungicide sprayings on disease development at the field level is hardly available commercially. Therefore real life experimentation is the best "simulation" available. Unfortunately that solution is slow and expensive. Due to the number of variables and the length of the season, there is a combinatorial explosion that makes it impossible to test in the field all the potential configurations of a CPDeWS. This led us to turn to formal modelling techniques like CPN for their ability to undergo formal verifications. The idea is first to define formally some risk scenarios and some required safety properties for this class of systems.

Then using technique such as model checking [START_REF] Baier | Principles of Model Checking[END_REF] it should be possible to objectively prove the reliability of the proposed CPDeWS under a set of precisely defined conditions.

Table 1. CPDeWS design features and the element used to map them into CPN

Conclusion

The design of decision support systems is an art in the sense that it blends together business knowledge, hard science, knowledge management science, a pinch of artificial intelligence and ergonomics. This makes the project of designing agricultural DSS long and costly [START_REF] Matthews | Wither agricultural DSS? Computers and Electronics in Agriculture[END_REF]. We think that the integrative approach proposed in this article, which balances modelling of decision and field experiment, could quicken such design and integration of pest specific Decision support systems (e.g. pest forecasting models). It should help to establish structured best practice guidelines for pest management. Our work with CPDeWS modelled as Petri nets is an attempt to identify design tools suited to that purpose.

Figure 2 .

 2 Figure 2. Overall architecture of the wheat CPDeWS

Figure 4 .

 4 Figure 4. BLé3 Generic within Stage reasoning (yellow rust) note: this diagram is not a formal CPN, several details are missing. For instance all (but the first) transition in this net are hierarchical transitions and the arc inscriptions are missing.

Author produced version; the original publication is available at http://www.efita.net