Samir Allaoui

Zoheir Aboura

Malk Benzeggagh

STUDY OF THE HYGRO-MECHANICAL BEHAVIOR OF CORRUGATED CARDBOARD

Keywords: corrugated cardboard, hygro-mechanical behavior, modeling. 1

Corrugated cardboard is very sensitive to atmospheric conditions. The aim of this work is to study the effects of these parameters, especialy the relative humidity (RH), on the mechanical behavior of corrugated cardboard sandwich structure. Tensile and three-point bending tests were used under various rates of relative humidity. An analytical model based on the classical laminate plate theory is used to predict the elastic behavior of the corrugated cardboard under different atmosphere conditions. The model is then extended to predict the inelastic behavior of the corrugated cardboard from the behavior of its components.

INTRODUCTION

Corrugated cardboard pertaining to papers family is one of the most used packing currently. Its employment does not cease increasing each year and covering the various types of packing, such containers and pallets, and extending to other fields such as the dwellings. This success is due to the various virtues of this material: good protection of the product, low cost and can be recycled as well as biodegradable. Biodegradable product are more and more demanding as being a major concern again the protection of the environment and hence respect a durable development.

For a better optimization and diversification of the use of corrugated cardboard, knowledge of its mechanical characteristics and failure, as well as the apprehension of its behavior, is necessary.

The corrugated cardboard is an orthotropic sandwich with the surface plies (facing) providing bending stiffness, separated by a lightweight bending core (fluting) that provides shear stiffness. Two main directions characterize this material. The first noted MD (machine direction) corresponds to the direction of manufacturing of the material. The second noted CD (cross direction) corresponds to the transverse direction and coincides with the y axis (Figure 1). Aboura at al. have developed an approach regarding corrugated cardboard as monolithic material and have adapted simple's mechanical tests to characterize this material [START_REF] Aboura | Elastic behavior of corrugated cardboard: Experiments and Modeling[END_REF][START_REF] Aboura | Etude et modélisation du comportement èlastique d'une structure sandwich de type carton ondulé[END_REF]. The tests were carried out under a controlled atmosphere (23 • C and 50% RH) according to the recommendations of French standard NF Q 03-010. They developed an analytical model to predict elastic and inelastic behavior of the material [START_REF] Aboura | Elastic behavior of corrugated cardboard: Experiments and Modeling[END_REF][START_REF] Allaoui | Elastic and inelastic modeling of corrugated cardboard[END_REF]. This model is based on the classical laminate plate theory and was inspired by different studies [START_REF] Ishikawa | Stiffness and strength behavior of woven fabric composites[END_REF][START_REF] Aboura | Analytical model of woven composite laminate. Superposition effect of two plies[END_REF][START_REF] Scida | Prediction of elastic behavior of hybrid and non-hybrid woven composite[END_REF].

This work purposes to study the effect of the atmosphere conditions, in particular the effect of moisture, on the mechanical behavior of the corrugated cardboard.

First, the study the moisture equilibrium corresponding to the water content in each layer and the sandwich is done. Once the moisture equilibrium achieved, the corrugated cardboard was tested in tensile and three-point bending tests at controlled atmosphere. The relative humidity levels used vary from dry conditions (35% RH) to severe conditions (90% RH). The difficulty at these conditions consists in handling the least possible the specimens. Methodology of measurement developed in a previous study [START_REF] Allaoui | Effets des conditions environnementales sur le comportement mécanique de structures sandwich de type carton ondulé[END_REF] is used. Finally the analytical model developed by Aboura et al. was used to predict the elastic properties of the material at different atmospheres.

MOISTURE EQUILIBRIUM OF THE MATERIAL

Two layers and one flute compose the corrugated cardboard used in this study. All the constituents are composed with 100% cellulose recycled fibers. Table 1 shows the constituents geometrical and mechanical characteristics. The thickness of the sandwich is 4.1 mm. Mechanical tests will be made under various controlled atmospheres. Specimens must be preliminary conditioned to reach a state of moisture equilibrium in these conditions. Standard French norm NFQ 03-010 recommends 24 hours conditioning for any kind of paperboards.

Square specimens of 5 cm of the corrugated cardboard and its components were made. They were conditioned in a climatic chamber under conventional conditions (23 • C and 50% RH) during 24 hours. Once the equilibrium is reached, the specimens were weighed and these measurements were used as references. It assumed that the equilibrium at 50% RH corresponds to a moisture content of 6% (dry basis) in each specimen [START_REF] Gendron | A numerical study of the hygro-mechanical deformation of two cardboard layups[END_REF]. Then, a rate of 95% RH is imposed followed by a regular weighing of specimens to evaluate the moisture content. The balance used has a precision of 0.01 mg.

After 100 minutes the moisture equilibrium was achieved. This state corresponds to moisture content of 8% at 9% for corrugated cardboard and its components (Figure 2). If the dry basis is considered, the moisture content will be 15%.

MECHANICAL TESTS UNDER VARIOUS RH

Tensile and three-points bending tests were carried out on specimens of corrugated cardboard on a tensile testing machine, which is equipped with a climatic chamber. The temperature is fixed at 23 • C and the atmospheric conditions vary between 35% to 90% RH. Before the tests, specimens were conditioned in a climatic chamber under each value of RH, during 24 hours to reach a state of moisture equilibrium. A thermo-hygrometer (precision of ±3% RH) was used to control the rate of humidity.

Tests conditions

The difficulty of the tests consists in handling the least possible the specimens. For that, the methodology of measurement witch are developed in previous study is used.

A particularly attention is done at high level of moisture. Indeed, a phenomenon of condensation occurs which produce a water drop and then risk to wet the paperboard. This effect is shown on Figure 3. The Young's modulus and the maximum stress and strain are strongly affected by this phenomenon. It is then important at high RH to check before each test that the specimen is not wet.

Another phenomenon is observed during the conditioning of the specimens. By increasing RH, a deformation of the cardboard is observed inducing a curvature. This phenomenon has been modeled for the case of paperboard by Gendron [START_REF] Gendron | A numerical study of the hygro-mechanical deformation of two cardboard layups[END_REF]. This phenomenon is more pronounced in the CD.

These shapes did not affect the tensile tests. For the three-points bending tests, specimens were tested in two configurations. The load is applied on the convex part of the specimen in the first configuration and on the concave part for the second one. It was found that the elastic behavior is the same one for the two cases. On the other hand the stress and deflexion of collapse are more significant for the specimens tested on the concave part (Figure 4) and this under all the atmospheres. For the follow bending tests, we will alternate between the two configurations, and an average of mechanical results will be done.

Results and discussion

Table 2 shows the results obtained during tensile and bending tests. The conventional conditions (23 • C and 50% RH) are used as references. Parameter Er, which is a relative deviation from references conditions, is calculated as In dry conditions (35% RH), the elastic characteristics do not change and remain in the field of dispersion (Er < 4%), except for the corrugated cardboard in the CD tensile test where Er = 12, 83%.

The increase of moisture makes fall the elastic characteristics. This fall is more significant on the bending tests. Indeed, by increasing the moisture content at 70% RH, the Young modulus do not change in the two directions of material. Contrary to tensile tests, the bending stiffness falls under these conditions. The maximum value of fall is 16% in the CD. In the very wet conditions (90% RH), the elastic characteristics break down. The falls of these parameters vary from 33,15% for the Young's modulus in the MD to a maximum of 54% for the bending stiffness in the CD.

The elastic limit and the failure stress change according to the rate of moisture in the cross and machine direction (Figures 5 and6).

The effect of moisture is more significant in the cross dirsection than in the machine direction. This can be explained by the fact that the behavior of material in the cross direction depends on the hydrogen lies between the cellulose fibers which change when the paperboard was subjected to a change in humidity content.

ANALYTICAL MODELING

An analytical model of the elastic behavior of corrugated cardboard was developed [START_REF] Aboura | Elastic behavior of corrugated cardboard: Experiments and Modeling[END_REF][START_REF] Aboura | Etude et modélisation du comportement èlastique d'une structure sandwich de type carton ondulé[END_REF]. It takes into account mechanical properties and geometrical parameters (core thickness, fluting step, skin thickness) of the components. This model, based on the classical laminate plate theory, was extended to pre- dict the inelastic behavior of the material [START_REF] Allaoui | Elastic and inelastic modeling of corrugated cardboard[END_REF]. This study purpose to test the validity of this approach under different atmospheres conditions.

Elastic properties

The model need as input the elastic properties of the skins an flute obtained by tensile tests under different rates of 50%, 70% and 90% of RH (Table 3). The predicted properties at each rate of RH are compared to the experimental results (Table 4).

At 50% HR, the model estimates the Young modulus with an error of 10% compared to the experiment. This error is caused by the fact that the model does not take account of the effect of the manufacture process. During this process the skins lose some of their rigidity.

The model results at each rate of RH compared to the experimental ones gives practically the same error. This error is about 10% in the MD. In the CD we note a light fall of the error in estimation of the elastic characteristics. However this fall remains in the field of dispersion (2%). From that we deduce that the interface between the skins and flute does not affect the behavior of corrugated cardboard. We note that the model predict correctly the elastic properties.

Inelastic behavior

To predict the inelastic behavior of the corrugated cardboard, the model requires the knowledge of the behavior laws of the components of corrugated cardboard [START_REF] Allaoui | Elastic and inelastic modeling of corrugated cardboard[END_REF]. Considering the assumption of iso-strain, in a first approach, the model will be fed by the experimental results of tests carried out on the skins and flute under different atmospheric conditions. The inelastic predict behavior of the model in the MD is shown on the Figure 7.

On the whole of the rates of humidity, a good correlation between the results of the model and experimental ones is noted. At 50% RH, and 70% RH the inelastic predicted behavior over estimate the experiment one contrary at 90% HR. This is probably due to the effect of the interfaces which are not taking into account on the model.

The prospect for this study is to develop a macro-micro law of the behavior of cellulose fibers. This law will make it possible to predict the behavior of the skins and thereafter that of the corrugated cardboard.

CONCLUSION

The paperboard is a very sensitive material to the environmental conditions, especially moisture, but also with any handling. The corrugated cardboard showed sensitivity to the relative humidity of the environment tests. A particular attention must be made during these tests in order to not perturb the results.

Concerning elastic properties, they change significantly beyond 70% RH. This effect is more perceptible on bending characteristics than the tensile ones. Thus bending stiffness falls by 54% when the RH reaches 90%.

For the behavior beyond elastic phase, it has been shown that the failure characteristics, stress and strain failure, are even more sensitive to the effect of moisture.

The effect of the moisture in the cross direction is more significant than in the machine direction because of privileged orientation of the cellulose fibers.

An analytical model developed in previous study was applied to predict the behavior of the corrugated cardboard under atmospheric conditions. It has been found that this approach can predict correctly the elastic an inelastic behavior.

Figure 1 .

 1 Figure 1. Cardboard panel geometry.

Figure 2 .

 2 Figure 2. Moisture content at equilibrium for corrugated cardboard and its constituents.

Figure 3 .

 3 Figure 3. Tensile test of dry layer an wet one at 90% RH (CD).

Figure 4 .

 4 Figure 4.Bending test on convex and concave configuration under different rates of RH (corrugated cardboard in CD).

Figure 5 .

 5 Figure 5. Three-point bending curves under different rates of RH.

Figure 6 .

 6 Figure 6. Tensile curves under different rates of RH.

Figure 7 .

 7 Figure 7. Modeling of the mechanical behavior of the corrugated cardboard under different rates of RH.

Table 1 .

 1 Mechanical and geometrical characteristics of the constituent of the corrugated cardboard.

		H (mm)	E MD (Mpa)	E CD (Mpa)	ν xy	ν yx
	Upper layer	0.235	4514.53	1895.83	0.282	0.215
	Flute	0.19	4458.6	1944.5	0.277	0.115
	Lower layer	0.235	4703.75	1854.3	0.353	0.088

Table 2 .

 2 Results of tensile and bending tests under different rates of RH.

Table 4 .

 4 Model results under different rates of RH.


S Allaoui
email: samir.allaoui@univ-orleans.fr.

Z Aboura

M L Benzeggagh

CONTRIBUTION TO THE MODELLING OF THE CORRUGATED CARDBOARD BEHAVIOUR

The current paper summarizes studies undertaken on the corrugated cardboard. In these studies, a new approach considering the corrugated cardboard as an orthotropic material is developed. This approach permits after homogenization to simplify the numerical calculations and then use a 2D meshing of the corrugated cardboard, instead of a 3D meshing. This will makes it possible to obtain less heavy and less expensive numerical dimensioning studies. The first stage of the studies was a determination of the behaviours of the sandwich and its constituents, which passes by the definition of experimental protocols. Thereafter, an analytical model was proposed and permits to predict the homogenized behaviour of the corrugated cardboard. Finally a tool of decision-making aid was proposed.

Homogenisation of the structure

Homogeneous material

Corrugated cardboard sandwich structure

INTRODUCTION

Corrugated cardboard pertaining to papers family is one of the most used packing currently. This success is due to the various virtues of this material: good protection of the product, low cost and can be recycled as well as biodegradable. Biodegradable product are more and more demanding as being a major concern again the protection of the environment and hence respect a durable development. In addition, the new European provisions concerning environmental protection impose a reduction of weight as well as quotas of recyclability of various packing materials. Actually, to optimize the packing (cases), the manufacturer proceed with their knowledge. They carried out mechanical tests on the final product. This causes a raw materials loss, and requires a considerable investment in human and materials means. The possibility of acting upstream is desirable and would make it possible to develop a rigorous and cheaper method. This demarche needs a tool of decision-making aid using simple model.

The corrugated cardboard is an orthotropic sandwich with the surface plies (facing) providing bending stiffness, separated by a lightweight bending core (fluting) that provides shear stiffness. Two main directions characterise this material. The first noted MD (machine direction) corresponds to the direction of manufacturing of the material. It coincides with the "x" axis (Figure 1). The second noted CD (cross direction) corresponds to the transverse direction and coincides with the "y" axis. To refer to the out-of-plane direction (through-thickness), a third direction ZD is introduced as depicted by figure 1. It is generally composed by three paperboard constituents: upper layer, lower layer and fluting. We observe the same directions for the paperboard, where the machine direction corresponds to the feel orientation of the cellulose fibres. This privileged orientation is due to the continuous nature of the material process.

The Approach used in different studies, consider the corrugated cardboard as structure. These studies used norms relative to the composite or metallic sandwich structure to apprehend mechanical behaviour of the corrugated cardboard. The main tests are three or four points bending (ASTM C393-62), as well as shear tests (ASTM C273-61). Norstrand et al. [START_REF] Nordstrand | Evaluation of transverse shear stiffness of structural core sandwich plates[END_REF] have evaluated the transverse shear stiffness of corrugated cardboard by ASTM block shear test and by three-point bending test. Nevertheless, this approach does not allow determining the stiffness matrix of such a material and makes therefore its homogenization for a finite elements calculation impossible. It is obvious that the possibility exists always to mesh the structure completely (skins and core) [START_REF] Damatty | Finite element modelling and analysis of a cardboard shelter[END_REF][START_REF] Patel | Local buckling and collapse of corrugated cardboard under biaxial stress[END_REF][START_REF] Gilchrist | Nonlinear finite element modeling of corrugated cardboard[END_REF] leading to an extremely expensive process. In this study, another alternative being well developed consists to replacing the corrugated cardboard by an equivalent orthotropic layer [START_REF] Aboura | Elastic behavior of corrugated cardboard: Experiments and Modeling[END_REF]. This approach will permit after homogenization to simplify the numerical calculations and then use a 2D meshing of the corrugated cardboard (figure 2), instead of a 3D meshing extensively used in the literature. This will makes it possible to obtain less heavy and less expensive numerical dimensioning studies of cases for example.

Figure 2: Homogenization approach

This approach is articulating around two points:

• The first point is to dedicate the different experimental protocols finalized for the sake of determination the mechanical behaviour of the constituents (skins and core) as well as those of the corrugated cardboard. The main difficulty resides in the experimental precautions in order to identify the necessary parameters in the absence of the preworkbenches protocols.

• The second point is dedicate to the analytical modelling. Thus, by using the mechanical properties and geometrical parameters of the constituents (step of fluting, thickness of skins and core), this model should be able to predict the homogenized behaviour of the corrugated cardboard.

A comparison between the experimental observations, analytic model and finite elements prediction allows judging the performances of the proposed model.

EXPERIMENTAL TESTS

The first part of the study stuck to the establishment of specific experimental procedures tests that considering the corrugated cardboard like a material and not a structure. They are extending to the case of the paperboard in order to obtain their behaviour, which will be used in the modelling method. These procedures are inspired by the norms relative to the composite and metallic sandwich structure [START_REF] Aboura | Elastic behavior of corrugated cardboard: Experiments and Modeling[END_REF]. One of the significant points in these procedures is the rigidification of the specimen heads by injecting a polyester resin between fluting and cardboard skins to fill the existing emptiness or by impregnating the extremities in the resin for the paperboard specimens. Indeed, this permit to avoid the bruising of the specimen heads at the griping time and thus the use of work-holding device. In the other hand, the instrumentation required a particular attention because the material becomes sensitive to any handling during the mechanical tests. Several means were used and the optical method using marks tracking technique was validated because it is the most adapted for tests at different atmospheric conditions [START_REF] Allaoui | Effects of the environmental conditions on the mechanical behaviour of the corrugated cardboard[END_REF].

After having established the various protocols, mechanical tests were carried out on corrugated cardboard and the paperboard. Initially tensile, twisting, shear and three point bending tests were carried out in order to determine the elastic and failure parameters of the paperboard and the sandwich. Figure 3 represents some examples of the corrugated cardboard behaviour under uni-axial solicitations. Generally, we have noted that the behaviour in the cross direction and the machine direction are different. For each material and in each direction, we have determined the mechanical parameters but also the chronology of these behaviours.

Figure 3: Examples of the corrugated cardboard under uni-axial solicitations

In the case of the tensile test, table 1 illustrates elastic and failure properties obtained. We note that these mechanical parameters are twice more significant in the machine direction than in the cross direction, which correspond to the celluloses fibres orientation and the flute one. Concerning the corrugated cardboard, it appears that the load failure, in MD, is equal to the sum of the maximum failure loadings of the two main layers. On the other hand, in CD, it is equal to the sum of those of the three constituent's failures loads (layers and flute). This illustrates the principal teaching of the different tests, where the corrugated cardboard behaviour is governed by the layers in the machine direction and by all the constituents in the cross direction. 1: elastic and failure parameters of the corrugated cardboard and its constituents As we can see on the Characteristic stress-strain curves (figure 3a), mechanical behaviour of the corrugated cardboard (in the two in-plane directions) is composed by linear part followed-up by non-linear part. We note that the same behaviour phases were found in the case of the paperboard. The non-linearity is accentuated in the cross direction. This phenomenon depends on the cellulose fibres, the hydrogen bonds and the rate of the moisture content. This more marked non-linearity in the cross direction can be due to the fact that the paperboard mechanical behaviour, therefore the sandwich one, are more governed by hydrogen bonds that are more requested in CD than the cellulose fibres.

To highlight this viscous behaviour, uni-axial tensile tests at different strain rate ( ε& going from 6 x 10 -5 s -1 to 12 x 10 -3 s -1 ) and other with strain recoveries were carried out. These tests make us able to identify that the elastic and failure parameters evolve more in CD with the strain rate solicitation [START_REF] Allaoui | Phenomena governing uniaxial behaviour of paperboard and corrugated cardboard[END_REF]. This evolution is more significant in the case of the layers which have a more significant coating. This coating, constituted by a polymer material, is a surface treatment used to improve the printing quality but also to have a better surface aspect. So, the coating undoubtedly interferes on the material behaviour.

Loading-unloading-holding tensile tests carried out on the skins, in the two directions, revealed a residual plastic strain. Thus, non-linearity of the paperboard is governed by a viscoplastic phenomenon. The slopes of unloading shows a curved shape, which indicate the presence of energy dissipation, so a loss of stiffness. This dissipation is due to the presence of a damage coupled with the viscoplastic phenomenon. This damage has been highlighted by cyclic tests on the paperboard and the sandwich.

After that, relaxation tensile tests under SEM were carried out in order to identify the coupled damage-viscous-plasticity. During these tests carried out on microspecimens of the paperboard, fractographies were taken to show the mechanisms which govern this damage. Mechanical parameters obtained by theses tests were not exploited because of the scale effect. Only physical phenomena have been considered. These tests confirm the presence of viscoelastic phenomenon at the elastic phase where we note a stress relaxation with the first strain holding (figure 4). This phenomenon is more significant in the cross direction than in the machine direction. This is due to the fact that the hydrogen bonds between fibres, which can have a viscous behaviour, are more requested in CD. These observations confirm those make in the precedent static tests. The damage intervenes at the linear part of the behaviour by the locally appearance of microscopic cracks. By increasing load level, microscopic cracks appear in greater number before starting of macroscopic crack, which causes the final failure of material (figure 4). The damage of the paperboard intervenes in several forms. We note fibre skirting, fibres failures or even coating damage. These mechanisms are found in the two in-plane directions (MD and CD), but with more or less significant proportions [START_REF] Allaoui | Phenomena governing uniaxial behaviour of paperboard and corrugated cardboard[END_REF]. Mechanical tests carried on the corrugated cardboard and its constituents allowed us to identify their elastic and failure parameters. In addition, we have highlighted the complexity of the material behaviour, which is governed by a coupled phenomenon (viscous-plastic-damage). However, these behaviours evolve with the rate relative humidity, phenomenon in which we were interested [START_REF] Allaoui | Effects of the environmental conditions on the mechanical behaviour of the corrugated cardboard[END_REF]. Indeed, we have noted a loss of performance of more than 50% while passing from 50%RH to 90RH. The whole of the obtained experimental results constitutes an essential database to the development of an analytical model, which will be able to predict the mechanical behaviour of the sandwich.

ANALYTICAL MODELLING

An analytical model was developed. It is based on the classical laminate theory was feed by mechanical and geometrical characteristics of the sandwich constituents. In the first time, the model was applied to predict elastic behaviour of the sandwich.

Formulation of the analytical model

To analyse the elastic behaviour of the corrugated cardboard, the proposed approach is based on the classical laminate theory. The model is inspired from Ishikawa et al [START_REF] Ishikawa | Stiffness and strength behavior of woven fabric composites[END_REF], Aboura [START_REF] Aboura | Analytical model of woven composite laminate. Superposition effect of two plies[END_REF] and Scida et al. [START_REF] Scida | Prediction of elastic behaviour of hybrid and non-hybrid woven composite[END_REF] related to the elastic behaviour modelling of woven composites materials. A unit cell representative of the corrugated cardboard is defined as in figure 5 and considered the skins and the undulated fluting as an assembling of many infinitesimal elements dx of unidirectional lamina oriented at different angles. The classical laminate theory is then applied to each element.

⎭ ⎬ ⎫ ⎩ ⎨ ⎧ ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ j j ij ij ij ij i i k D B B A M N ε (i,j =1,
∫ - = 2 : 2 / 2 ) , , 1 ( ) , , ( h
h ij dz Q z z D B A (2)
in which

⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ - - - - =
ij G E E E E Q 0 0 0 1 1 0 1 1 ν ν ν ν ν ν ν ν ν ν (i,j = 1,2,6) (3)
Q ij is evaluated for each constituent of the corrugated cardboard unit cell. This means that the superior and inferior skins and the fluting undulation are taken into account.

The local stiffness of each infinitesimal element depends on the constituent elastic properties as well as on the fluting orientation defined by the local off-axis angle θ(x). This angle is calculated from the fluting median fibre function Ht(x):

) ) ( ( tan ) ( 1 dx x dHt x - = θ (4)
Ht(x) is assumed to be of sinusoidal form with a maximum thickness of hc:

) 2 ( sin 2 ) ( P x hc x Ht π = (5)
Once the Q ij terms are calculated, the in-plane stiffness coefficients can be evaluated for each element in different regions of the unit cell by using equation [START_REF] Damatty | Finite element modelling and analysis of a cardboard shelter[END_REF]. The global matrices A global , B global and D global for the corrugated cardboard unit cell are calculated numerically from the local matrices A, B and D evaluated for each infinitesimal element with an average in the "x" direction by:

∫ = P global dx x D x B x A P D B A 0 ) ( ), ( ), ( 1 ) , , ( (6)
From the global matrices [A], [B] and [D], the effective Young's modulus, shear modulus and Poisson's ratio of the corrugated cardboard can be obtained.

Results of homogeneous elastic properties

Two layers and one flute compose the corrugated cardboard used for the model validation. The mechanical characteristics of the constituents are obtained by tensile tests according to experimental protocols developed in precedent studies [START_REF] Aboura | Elastic behavior of corrugated cardboard: Experiments and Modeling[END_REF][START_REF] Allaoui | Effects of the environmental conditions on the mechanical behaviour of the corrugated cardboard[END_REF] After that, the model was used to evaluate the homogeneous characteristics of the sandwich. Table 3 shows the results of the homogenization. We note that the model results are in good agreement with the experience. All the analytical homogeneous characteristics are given with an error less than 9% compared to the experimental ones. This error is due to the effect of the corrugated cardboard manufacture process and the fact that the Unit cell representative (VER) doesn't take account of the interface between the skins and the fluting. To evaluate the effect of the process, we determined the mechanical characteristics of the skins before and after manufactured of the corrugated cardboard. We carried out micro tensile tests on skins gives by the manufacturer and skins extracted on the structure. Tests were carried out in the cross and machine direction. We found that the manufactured process does not affect the characteristics of the lower layer and the flute, when the upper layer loses 13% of its characteristics in the machine direction. After that we have use the news mechanics characteristics of the upper layer as inputs for the analytical model. We note that the error in estimation of the Young modulus in the machine direction passes from 8.53% to 3.06%. In the same time the other characteristics do not evolve significantly

Modelling of the inelastic behaviour

The analytical model developed was carried out in the elastic range and permit to predict Homogeneous mechanical characteristics in good agreement with those obtained by experimental tests. Beyond this elastic part, the corrugated cardboard has non-linear behaviour. The extension of the analytical model to the prediction of the behaviour beyond elasticity requires the knowledge of the behaviour laws of the corrugated cardboard components. In this approach, the model will be fed by experimental results resulting from tests carried out on the layers and the flute. The model will be extending to the prediction of non-linear uniaxial tensile behaviour of the material. This extension needs to know the stress-strain curve in MD and CD of the sandwich constituents. Assuming strain continuity, the local stress is computed in each element of the unit cell at every increment of macroscopic stress by using the stressstrain curves of the skins and fluting. A new stiffness is then determined. By homogenisation on all unit cell, the global stiffness can be calculated and then the prediction of non-linear behaviour of the corrugated cardboard.

Figure 6 shows a good agreement between the behaviour simulated by the model in the machine direction and the experimental results one. On the other hand, the agreement is worse in the cross direction (figure 6b). Indeed after having approached elastic phase correctly, the model over-estimates the inelastic phase. This phenomenon is due to the effect of the interface between the two skins and the flute. This interface intervenes when the material is requested mechanically. It is made up of starch, which is used as adhesive between the tops of the flute and the skins. During the tensile test, the request of the interface causes a local damage due to the high rigidity of the starch compared to the paperboard. This phenomenon does not interfere in the machine direction.

Figure6: Comparison between experimental and model results of the uni-axial tensile behaviour.

Modelling of the global behaviour of the sandwich was then used to predict the behaviour of the sandwich at different atmospherics conditions. The results obtained are in good agreement with the experimental ones. However, a parametrical study was done in order to evaluate the geometrical parameters (like layers thickness, core thickness, fluting step …etc.), which influence more the sandwich behaviour.

NUMERICAL SIMULATION

In order to assess the relevance of the homogenization method developed for this purpose, a finite element analysis was used using the homogeneous mechanical parameters obtained by the model. The main goal is to verify the possibility to use a 2D meshing of the corrugated cardboard, instead of a 3D meshing extensively used in the literature. A finite element models were created for mechanical tests such as the three points bending and free vibration tests. The results of the three points bending with an applied load of 5N are presented in this study. The geometrical characteristics of this model are chosen similar to those used in the corresponding experiments. The used element is the basic triangular 3-nodes flat shell. Table 4 presents a comparison between experimental and the two finite element approaches results. The agreement between experimental and the two FE approaches is correct. We note that the bending stiffness are estimate with a maximum error of 12% the cross direction. For the 3D meshing the stiffness is estimate with an error of 7.86% in the cross direction. However, for an overall behaviour, the time calculation of the 2D approach is 10 times lower than that of the 3D approach. It appears that the simplified homogenisation procedure is adequately accurate and fast for effectively analysing corrugated cardboard panel in the preliminary and optimisation design stages. For this aim, a tool of decision-making aid using the results obtained by this various work is developed. This tool makes it possible to predict the homogenized mechanical parameters of the corrugated cardboard, but also to choose the adequate constituents (layers and flute) in order to avoid over sizing the packing (case for example).

CONCLUSIONS

This work summarizes different studies devoted to the study of the mechanical behaviour of the corrugated cardboard. The approach adopted considers the sandwich as an orthotropic material and not a structure. Different experimental protocols were developed in order to characterize the homogenized behaviour of the sandwich. The tests carried out makes it possible to better apprehend this behaviour which is more complex than as described in the literature. Thus we have highlighted a coexistence of viscous, plastic and damage phenomenon.

After that, an analytical model has been proposed. It permits to predict the homogeneous mechanic parameters in a good agreement with those obtained with the experimental tests. This model have been extend to the global behaviour of the sandwich and gives satisfaction.

In order to assess the relevance of the homogenisation method developed for this purpose, a finite element analysis is used. The main goal of this work is to verify the possibility to use a 2D meshing of the corrugated cardboard, instead of a 3D meshing. It was found that the simplified homogenisation procedure is adequately accurate and fast for effectively analysing corrugated cardboard panel in the preliminary and optimum design stages. A tool of decision-making aid was then proposed in order to help the engineers of engineering department, in the choice of the corrugated cardboard constituents. This makes it possible to not oversize the final product (like case) and thus a raw material profit.

Figure 1 :

 1 Figure 1: Cardboard panel geometry

  Shear test in MD

Figure 4 :

 4 Figure 4: Cross direction relaxation tensile test under SEM of the paperboard.

2 and 6 ) ( 1 )Figure 5 :

 615 Figure 5: Unit cell representative (VER) of the corrugated cardboard

Figure 7 :

 7 Figure 7: Interface of the tool of decision-making aid

Table 2 :

 2 . They are shown with the geometrical characteristics in the table 2. Mechanical and geometrical characteristics of the sandwich constituents

		h (mm)	E MD (Mpa)	E CD (Mpa)	νxy	νyx
	Upper layer	0.235	4514.53 1895.83	0.282	0.215
	Flute	0.235	4703.75	1854.3	0.353	0.088
	Lower layer	0.19	4458.6	1944.5	0.277	0.115

Table 3 :

 3 Comparison between experimental and model results

		E MD (Mpa)	E CD (Mpa)	νxy	νyx
	Experimental characteristics	656	412.38	0.251	0.125
	Model results	711.99	391.47	0.246	0.135
	Model / Exp. (%)	8.53	-5.07	-1.87	8.33
	Model results after correction	676.1	390.78	0.246	0.142
	Model after correction / Exp. (%)	3.06	5.24	-1.87	13.88

Table 4 :

 4 Comparison between FE and experimental results


Thomas Peel
email: thomas.peel@lif.univ-mrs.fr

Sandrine Anthoine
email: anthoine@cmi.univ-mrs.fr

Liva Ralaivola
email: liva.ralaivola@lif.univ-mrs.fr

Empirical Bernstein Inequalities for U-Statistics

. Our result subsumes other existing empirical Bernstein inequalities, as it reduces to them when U-statistics of order 1 are considered. In addition, it is based on a rather direct argument using two applications of the same (non-empirical) Bernstein inequality for U-statistics. We discuss potential applications of our new inequalities, especially in the realm of learning ranking/scoring functions. In the process, we exhibit an efficient procedure to compute the variance estimates for the special case of bipartite ranking that rests on a sorting argument. We also argue that our results may provide test set bounds and particularly interesting empirical racing algorithms for the problem of online learning of scoring functions.

Introduction

The motivation of the present work lies in the growing interest of the machine learning community for learning tasks that are richer than now well-studied classification and regression. Among those, we especially have in mind the task of ranking, where one is interested in learning a ranking function capable of predicting an accurate ordering of objects according to some attached relevance information. Tackling such problems generally implies the use of loss functions other than the 0-1 misclassification loss such as, for example, a misranking loss [START_REF] Clémenc ¸on | Ranking and empirical minimization of u -statistics[END_REF] or a surrogate thereof. For (x, y) and (x , y ) two pairs from some space Z := X × Y (e.g., X = R d and Y = R) the misranking loss rank and a surrogate convex loss sur may be defined for a scoring function f ∈ Y X as: rank (f, (x, y), (x , y )) := 1 {(y-y )(f (x)-f (x ))<0} , [START_REF] Agarwal | Generalization Bounds for the Area under the ROC Curve[END_REF] sur (f, (x, y), (x , y )) := (1 -(y -y )(f (x) -f (x ))

2 .

(

) 2
Given such losses or, more generally, a loss : Y X × Z × Z → R, and a training sample Z n = {(X i , Y i )} n i=1 of independent copies of some random variable Z := (X, Y ) distributed according to D, the learning task is to derive a function f ∈ X Y such that the expected risk R (f ) of f R (f ) := E Z,Z ∼D (f, Z, Z ) = E Z,Z ∼D (f, (X, Y ), (X , Y )) 1 is as small as possible. In practice, this naturally brings up the empirical estimate R (f,

Z n ) R (f, Z n ) := 1 n(n -1) i =j (f, (X i , Y i ), (X j , Y j )), (3)
which is a U-statistic [START_REF] Clémenc ¸on | Ranking and empirical minimization of u -statistics[END_REF][START_REF] Hoeffding | A Class of Statistics with Asymptotically Normal Distribution[END_REF].

An important question is to precisely characterize how R (f, Z n ) is related to R (f ) and, more specifically, one may want to derive an upper bound on R (f ) that is expressed in terms of R (f, Z n ) and other quantities such as a measure of the capacity of the class of functions f belongs to and the size n of Z n -in other words, we may talk about generalization bounds [START_REF] Boucheron | Theory of classification : A survey of some recent advances[END_REF]. Pivotal tools to perform such analysis are tail/concentration inequalities, which say how probable it is for a function of several independent variables to deviate from its expectation; of course, the sharper the concentration inequalities the more accurate the characterization of the relation between the empirical estimate and its expectation. It is therefore of the utmost importance to have at hand tail inequalities that are sharp; it is just as important that these inequalities rely as much as possible on empirical quantities.

Here, we propose new empirical Bernstein inequalities for U-statistics. As indicated by the name (i) our results are Bernstein-type inequalities and therefore make use of information on the variance of the variables under consideration, (ii) instead of resting on some assumed knowledge about this variance, they only rely on empirical related quantities and (iii) they apply to U-statistics. Our new inequalities generalize those of [START_REF] Audibert | Tuning bandit algorithms in stochastic environments[END_REF] and [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF], which also feature points (i) and (ii) (but not (iii)), while based on simple arguments. To the best of our knowledge, these are the first results that fulfill (i), (ii) and (iii); they may give rise to a few applications, of which we describe two in the sequel.

The paper is organized as follows. Section 2 introduces the notations and briefly recalls the basics of U-statistics as well as tail inequalities our results are based upon. Our empirical Bernstein inequalities are presented in Section 3; we also provide an efficient way of computing the empirical variance when the U-statistics considered are based on the misranking loss rank of (1). Section 4 discusses two applications of our new results: test set bounds for bipartite ranking and online ranking.

Background

Notation

The following notation will hold from here on. Z is a random variable of distribution D taking values in Z := X × Y; Z , Z 1 , . . . , Z n are independent copies of Z and

Z n := {Z i = (X i , Y i )} n i=1 and Z p:q := {Z i } q i=p . A m n denotes the set A m n := {(i 1 , . . . , i m ) : 1 ≤ i 1 = . . . = i m ≤ n} , with 0 ≤ m ≤ n.
Finally, a function q : Z m → R is said to be symmetric if the value of q(z) = q(z 1 , . . . , z m ) is independent of the order of the z i 's in z.

U-statistics and Tail Inequalities

Definition 1 (U-statistic, Hoeffding [START_REF] Hoeffding | A Class of Statistics with Asymptotically Normal Distribution[END_REF]). The random variable Ûq (Z n ) defined as

Ûq (Z n ) := 1 |A m n | i∈A m n q(Z i1 , . . . , Z im ),
is a U-statistic of order m with kernel q, when q : [START_REF] Hoeffding | A Class of Statistics with Asymptotically Normal Distribution[END_REF]. Also, reusing some notation from the introduction, R (f, Z n ) of Eq. ( 3) is a U-statistic of order 2 with kernel q f (Z, Z ) := (f, Z, Z ). Remark 2. Two peculiarities of U-statistics that entail a special care are the following: (i) they are sums of identically distributed but dependent variables: special tools need be resorted to in order to deal with these dependencies to characterize the deviation of Ûq (Z n ) from Eq, and (ii) from an algorithmic point of view, their direct computations may be expensive, as it scales as O(n m ); in Section 3, we show for the special case of bipartite ranking how this complexity can be reduced. We now recall three tail inequalities (Eq. ( 5), ( 6), [START_REF] Freund | An efficient boosting algorithm for combining preferences[END_REF]) that hold for U-statistics with symmetric and bounded kernels q. Normally, these inequalities make explicit use of the length q max -q min of the range [q min , q max ] of q. To simplify the reading, we will consider without loss of generality that q has range [0, 1] (an easy way of retrieving the results for bounded q is to consider q/ q ∞ ).

Z m → R is a measurable function on Z m . Remark 1. Obviously, E Z m q(Z 1 , . . . , Z m ) = E Z n Ûq (Z n ); in addition, E Z n Ûq (Z n ) is a lowest variance estimate of E Z m q(Z 1 , . . . , Z m ) based on Z n
One key quantity that appears in the original versions of tail inequalities ( 5) and ( 6) below is n/m , the integer part of the ratio n/m -this quantity might be thought of as the effective number of data.

To simplify the notation, we will assume that n is a multiple of m and, therefore, n/m = (n/m).

Theorem 1 (First order tail inequality for Ûq , [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF].). Hoeffding proved the following:

∀ε > 0, P Z n E Z n Ûq (Z n ) -Ûq (Z n ) ≥ ε ≤ 2 exp -(n/m)ε 2 , (4)
Hence ∀δ ∈ (0, 1], with probability at least 1 -δ over the random draw of Z n :

E Z n Ûq (Z n ) -Ûq (Z n ) ≤ 1 (n/m) ln 2 δ . (5)
To go from the tail inequality ( 4) to the bound version [START_REF] Cesa-Bianchi | On the generalization ability of online learning algorithms[END_REF], it suffices to make use of the elementary inequality reversal lemma (Lemma 1) provided in section 3, used also for the bounds given below. Theorem 2 (Bernstein Inequalities for Ûq , [START_REF] Arcones | A bernstein-type inequality for u-statistics and u-processes[END_REF][START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]). Hoeffding [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] and, later, Arcones [START_REF] Arcones | A bernstein-type inequality for u-statistics and u-processes[END_REF] refined the previous result in the form of Bernstein-type inequalities of the form

∀ε > 0, P Z n E Z n Ûq (Z n ) -Ûq (Z n ) ≥ ε ≤ a exp - (n/m)ε 2 2ϑ q,m + b m ε ,
For Hoeffding, a = 2, ϑ q,m = Σ 2 q where, Σ 2 q is the variance of q(Z 1 , . . . , Z m ) and b m = 2/3. Hence, ∀δ ∈ (0, 1], with probability at least 1 -δ:

E Z n Ûq (Z n ) -Ûq (Z n ) ≤ 2Σ 2 q (n/m) ln 2 δ + 2 3(n/m) ln 2 δ . (6)
For Arcones, a = 4, ϑ q,m = mσ 2 q where σ 2

q is the variance of E Z2,...,Zm q(Z 1 , Z 2 , . . . , Z m ) (this is a function of Z 1 ) and b m = 2 m+3 m m-1 + (2/3)m -2 . ∀δ ∈ (0, 1]
, with probability at least 1 -δ:

E Z n Ûq (Z n ) -Ûq (Z n ) ≤ 2mσ 2 q (n/m) ln 4 δ + b m (n/m) ln 4 δ . (7)
With a slight abuse, we will now refer to Eq. ( 5), ( 6) and ( 7) as tail inequalities. In essence, these

are confidence intervals at level 1 -δ for E Z m q(Z m ) = E Z n Ûq (Z n ).
Remark 3. Eq. ( 7) is based on the so-called Hoeffding decomposition of U-statistics [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]. It provides a more accurate Bernstein-type inequality than that of Eq. ( 6), as mσ 2 q is known to be smaller than Σ 2 q (see [START_REF] Serfling | Approximation theorems of mathematical statistics[END_REF]). However, for moderate values of n/m (e.g. n/m < 10 5 ) and reasonable values of δ (e.g. δ = 0.05), the influence of the log terms might be such that the advantage of ( 7) over (6) goes unnoticed. Thus, we detail our results focusing on an empirical version of [START_REF] Clémenc ¸on | Ranking and empirical minimization of u -statistics[END_REF]. Example 1. To illustrate how the use of the variance information provides smaller confidence intervals, consider the kernel q m := m i=1 z i and two distributions D uni and D Ber (p). D uni is the uniform distribution on [0, 1], for which 1 shows the behaviors of ( 6) and ( 5) for various values of m as functions of n. Observe that the variance information renders the bound smaller.

Σ 2 = 1 3 m -1 4 m . D Ber (p) is the Bernoulli distribution with parameter p ∈ [0, 1], for which Σ 2 = p m (1 -p m ). Figure

Main Results

This section presents the main results of the paper. We first introduce the inequality reversal lemma, which allows to transform tail inequalities into upper bounds (or confidence intervals), as in ( 5)- [START_REF] Freund | An efficient boosting algorithm for combining preferences[END_REF].

Lemma 1 (Inequality Reversal lemma). Let X be a random variable and a, b > 0, c, d ≥ 0 such that

∀ε > 0, P X (|X| ≥ ε) ≤ a exp - bε 2 c + dε , (8)
then, with probability at least 1 -δ

|X| ≤ c b ln a δ + d b ln a δ . (9)
Proof. Solving for ε such that the right hand side of ( 8) is equal to δ gives:

ε = 1 2b d ln a δ + d 2 ln 2 a δ + 4bc ln a δ . Using √ a + b ≤ √ a + √ b
gives an upper bound on ε and provides the result.

Empirical Bernstein Inequalities

Let us now define the empirical variances we will use in our main result.

Definition 2. Let Σ2 q be the U-statistic of order 2m defined as:

Σ2 q (Z n ) := 1 |A 2m n | i∈A 2m n q(Z i1 , . . . , Z im ) -q(Z im+1 , . . . , Z i2m ) 2 , (10)
and σ2 q be the U-statistic of order 2m -1 defined as:

σ2 q (Z n ) := 1 |A 2m-1 n | i∈A 2m-1 n q(Z i1 , Z i2 , . . . , Z im )q(Z i1 , Z im+1 , . . . , Z i2m-1 ), (11)
It is straightforward to see that (cf. the definitions of Σ 2 q in (6) and σ 2 q in (7))

E Z n Σ2 q (Z n ) = Σ 2 q , and E Z n σ2 q (Z n ) = σ 2 q + E 2 Z m q(Z 1 , . . . , Z m ).
We have the following main result.

Theorem 3 (Empirical Bernstein Inequalities/Bounds). With probability at least 1 -δ over Z n ,

E Z n Ûq (Z n ) -Ûq (Z n ) ≤ 2 Σ2 q (n/m) ln 4 δ + 5 (n/m) ln 4 δ . ( 12
)
And, also, with probability at least 1 -δ, (b m is the same as in ( 7))

E Z n Ûq (Z n ) -Ûq (Z n ) ≤ 2mσ 2 q (n/m) ln 8 δ + 5 √ m + b m (n/m) ln 8 δ . (13)
Proof. We provide the proof of [START_REF] Maron | Hoeffding races: Accelerating model selection search for classification and function approximation[END_REF] for the upper bound of the confidence interval; the same reasoning carries over to prove the lower bound. The proof of ( 13) is very similar.

First, let us call Q the kernel of Σ2 q :

Q(Z 1 , . . . , Z 2m ) := (q(Z 1 , . . . , Z m ) -q(Z m+1 , . . . , Z 2m )) 2 .
Q is of order 2m, has range [0, 1] but it is not necessarily symmetric. An equivalent symmetric kernel for Σ2 q is Q sym :

Q sym (Z 1 , . . . , Z 2m ) := 1 (2m)! ω∈P2m q(Z ω(1) , . . . , Z ω(m) ) -q(Z ω(m+1) , . . . , Z ω(2m) )
2 where P m is the set of all the permutations over {1, . . . , m}. This kernel is symmetric (and has range [0, 1]) and Theorem 2 can be applied to bound Σ 2 as follows: with prob. at least 1 -δ

Σ 2 = E Z 2m Q sym (Z 2m ) = E Z n Σ2 q (Z n ) ≤ Σ2 q (Z n ) + 2V(Q sym ) (n/2m) ln 2 δ + 2 3(n/2m) ln 2 δ , where V(Q sym ) is the variance of Q sym . As Q sym has range [0, 1], V(Q sym ) = EQ 2 sym -E 2 Q sym ≤ EQ 2 sym ≤ EQ sym = Σ 2 ,
and therefore

Σ 2 ≤ Σ2 q (Z n ) + 4Σ 2 (n/m) ln 2 δ + 4 3(n/m) ln 2 δ .
(To establish [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF] we additionally use σ2

q (Z n ) ≥ σ 2 q ).
Following the approach of [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF], we introduce

√ Σ 2 -(m/n) ln(2/δ) 2
and we get

√ Σ 2 -(m/n) ln(2/δ) 2 ≤ Σ2 q (Z n ) + 7 3(n/m) ln 2 δ ,
and taking the square root of both side, using 1 + 7/3 < 3 and

√ a + b ≤ √ a + √ b again gives √ Σ 2 ≤ Σ2 q (Z n ) + 3 1 (n/m) ln 2 δ .
We now apply Theorem 2 to bound |E Z n Ûq (Z n )-Ûq (Z n )|, and plug in the latter equation, adjusting δ to δ/2 so the obtained inequality still holds with probability 1 -δ. Bounding appropriate constants gives the desired result.

Remark 4. In addition to providing an empirical Bernstein bound for U-statistics based on arbitrary bounded kernels, our result differs from that of Maurer and Pontil [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF] by the way we derive it. Here, we apply the same tail inequality twice, taking advantage of the fact that estimates for the variances we are interested in are also U-statistics. Maurer and Pontil use a tail inequality on self bounded random variables and do not explicitly take advantage of the estimates they use being U-statistics.

Efficient Computation of the Variance Estimate for Bipartite Ranking

We have just showed how empirical Bernstein inequalities can be derived for U-statistics. The estimates that enter into play in the presented results are U-statistics with kernels of order 2m (or 2m -1), meaning that a direct approach to practically compute them would scale as O(n 2m ) (or O(n 2m-1 )). This scaling might be prohibitive as soon as n gets large.

Here, we propose an efficient way of evaluating the estimate Σ2 q (a similar reasoning carries over for σ2 q ) in the special case where Y = {-1, +1} and the kernel q f induces the misranking loss (1):

q f ((x, y), (x , y )) := 1 {(y-y )(f (x)-f (x ))<0} , ∀f ∈ R X ,
which is a symmetric kernel of order m = 2 with range [0, 1]. In other words, we address the bipartite ranking problem. We have the following result.

Proposition 1 (Efficient computation of Σ2 q f ). ∀n, the computation of

Σq f (z n ) = 1 |A 4 n | i∈A 4 n 1 {(yi 1 -yi 2 )(f (xi 1 )-f (xi 2 ))<0} -1 {(yi 3 -yi 4 )(f (xi 3 )-f (xi 4 ))<0}
2 can be performed in O(n ln n).

Proof. We simply provide an algorithmic way to compute Σ2 q f (z n ). To simplify the reading, we replace i 1 , i 2 , i 3 , i 4 by i, j, k, l, respectively. We also drop the normalization factor |A 4 n | -1 (hence the use of ∝ instead of = in the first line below). We have

Σ2 q f (zn) ∝ i,j,k,l i =j =k =l (q f (zi, zj) -q f (z k , z l )) 2 = i,j,k,l i =j =k =l q 2 f (zi, zj) -2q f (zi, zj)q f (z k , z l ) + q 2 f (z k , z l ) , = 2(n -2)(n -3) i,j q f (zi, zj) -2 i,j,k,l i =j =k =l q f (zi, zj)q f (z k , z l ) since q 2 f =q f q f (z,z)=0 .
The first term of the last line is proportional to the well-known Wilcoxon-Mann-Whitney statistic [START_REF] Hanley | The meaning and use of the area under a receiver operating characteristic (roc) curve[END_REF]. There exist efficient ways (O(n ln n)) to compute it, based on sorting the values of the f (x i )'s.

We show how to deal with the second term, using sorting arguments as well. Note that i,j,k,l i =j =k =l

q f (zi, zj)q f (z k , z l ) = i,j q f (zi, zj) 2 -4 i =j =k q f (zi, zj)q f (zi, z k ) -2 i,j q 2 f (zi, zj).
We have subtracted from the square of i,j q f (z i , z j ) all the products q f (z i , z j )q f (z k , z l ) such that exactly one of the variables appears both in q f (z i , z j ) and q f (z k , z l ), which happens when i = k, i = l, j = k, j = l; using the symmetry of q f then provides the second term (together with the factor 4). We also have subtracted all the products q f (z i , z j )q f (z k , z l ) where i = k and j = l or i = l and j = k, in which case the product reduces to q 2 f (z i , z j ) (hence the factor 2) -this gives the last term. Thus (using q 2 f = q f ), defining R(z n ) := ij q f (z i , z j ) and doing some simple calculations:

Σq f (zn) = 1 |A 4 n |   -2R 2 (zn) + 2(n 2 -5n + 8)R(zn) + 8 i =j =k q f (zi, zj)q f (zi, z k )   (14)
The only term that now requires special care is the last one (which is proportional to σ2 q f (z n )).

Recalling that q f (z i , z j ) = 1 {(yi-yj )(f (xi)-f (xj ))<0} , we observe that

q f (z i , z j )q f (z i , z k ) = 1 ⇔ y i = -1, y j = y k = +1 and f (x i ) > f (x j ), f (x k ), or y i = +1, y j = y k = -1 and f (x i ) < f (x j ), f (x k ). ( 15
)
Let us define E + (i) and E -(i) as

E + (i) := {j : y j = -1, f (x j ) > f (x i )} , and E -(i) := {j : y j = +1, f (x j ) < f (x i )} .
and their sizes κ

+ i := |E + (i)|, and κ - i := |E -(i)|. For i such that y i = 1, κ +
i is the number of negative instances that have been scored higher than x i by f . From [START_REF] Rudin | Margin-based ranking and an equivalence between AdaBoost and RankBoost[END_REF], we see that the contribution of i to the last term of ( 14) corresponds to the number κ + i (κ + i -1) of ordered pairs of indices in E + (i) (similarly for κ - i , with y i = -1). Henceforth:

i =j =k q f (zi, zj)q f (zi, z k ) = i:y i =+1 κ + i (κ + i -1) + i:y i =-1 κ - i (κ - i -1).
A simple way to compute the first sum (on i such that y i = +1) is to sort and visit the data by descending order of scores and then to incrementally compute the κ + i 's and the corresponding sum: when a negative instance is encountered, κ + i is incremented by 1 and when a positive instance is visited, κ + i (κ + i -1) is added to the current sum. An identical reasoning works for the second sum. The cost of computing Σq f is therefore that of sorting the scores, which has cost O(n ln n).

Applications and Discussion

Here, we mention potential applications of the new empirical inequalities we have just presented.

Test Set Bounds

A direct use of the empirical Bernstein inequalities is to draw test set bounds. In this scenario, a sample Z n is split into a training set Z train := Z 1:ntrain of n train data and a hold-out set Z test := Z ntrain+1:n of size n test . Z train is used to train a model f that minimizes an empirical risk based on a U-statistic inducing loss (such as in ( 1) or ( 2)) and Z test is used to compute a confidence interval on the expected risk of f . For instance, if we consider the bipartite ranking problem, the loss is rank , the corresponding kernel is q f (Z, Z ) = rank (f, Z, Z ), and, with probability at least

1 -δ R rank (f ) ≤ R rank (f, Z test ) + 4 Σ2 q f (Z test ) ln(4/δ) n test + 10 n test ln 4 δ , (16)
where Σ2 q f (Z test ) is naturally the empirical variance of q f computed on Z test . Figure 2 displays the behavior of such test set bounds as n test grows for the UCI banana dataset. To produce this plot, we have learned a linear scoring function f (•) = w, • by minimizing

λ w 2 + i =j (1 -(Y i -Y j ) w, X i -X j ) 2
for λ = 1.0. Of course, a purely linear scoring function would not make it possible to achieve good ranking accuracy so we in fact work in the reproducing kernel hilbert space associated with the Gaussian kernel k(x, x ) = exp(-x-x 2 /2). We train our scoring function on n train = 1000 data points and evaluate the test set bound on n test = 100, 500, 1000, 5000, 10000 data points. Figure 2 (right) reports the size of half the confidence interval of the Hoeffding bound [START_REF] Cesa-Bianchi | On the generalization ability of online learning algorithms[END_REF] and that of the empirical Bernstein bound given in [START_REF] Serfling | Approximation theorems of mathematical statistics[END_REF]. Just as in the situation described in Example 1, the use of variance information gives rise to smaller confidence intervals, even for moderate sizes of test sets.

Online Ranking and Empirical Racing Algorithms

Another application that we would like to describe is online bipartite ranking. Due to space limitation, we only provide the main ideas on how we think our empirical tail inequalities and the efficient computation of the variance estimates we propose might be particularly useful in this scenario.

First, let us precise what we mean by online bipartite ranking. Obviously, this means that Y = {-1, +1} and that the loss of interest is rank . In addition, it means that given a training set Z = {Z i := (X i , Y i )} n i=1 the learning procedure will process the data of Z incrementally to give rise to hypotheses f 1 , f 2 , . . . , f T . As rank entails a kernel of order m = 2, we assume that n = 2T and that we process the data from Z pairs by pairs, i.e. (Z 1 , Z 2 ) are used to learn f 1 , (Z 3 , Z 4 ) and f 1 are used to learn f 2 and, more generally, (Z 2t-1 , Z 2t ) and f t-1 are used to produce f t (there exist more clever ways to handle the data but this goes out of the scope of the present paper). We do not specify any learning algorithm but we may imagine trying to minimize a penalized empirical risk based on the surrogate loss sur : if linear functions f (•) = w, • are considered and a penalization like w 2 is used then the optimization problem to solve is of the same form as in the batch case:

λ w 2 + i =j (1 -(Y i -Y j ) w, X i -X j ) 2 ,
but is solved incrementally here. Rank-1 update formulas for inverses of matrices easily provide means to incrementally solve this problem as new data arrive (this is the main reason why we have mentioned this surrogate function).

As evoked by [START_REF] Cesa-Bianchi | On the generalization ability of online learning algorithms[END_REF], a nice feature of online learning is that the expected risk of hypothesis f t can be estimated on the n -2t examples of Z it was not trained on. Namely, when 2τ data have been processed, there exist τ hypotheses f 1 , . . . , f τ and, for t < τ , with probability at least 1 -δ:

R rank (f t ) -R rank (f t , Z 2t:2τ )) ≤ 2 Σ2 q f (Z 2t:2τ ) ln(4/δ) τ -t + 5 τ -t ln 4 δ .
If one wants to have these confidence intervals to simultaneously hold for all t and all τ with probability 1 -δ, basic computations to calculate the number of pairs (t, τ ), with 1 ≤ t < τ ≤ n show that it suffices to adjust δ to 4δ/(n + 1) 2 . Hence, with probability at least 1 -δ:

∀1 ≤ t < τ ≤ n, R rank (f t ) -R rank (f t , Z 2t:2τ )) ≤ 4 Σ2 q f (Z 2t:2τ ) ln((n + 1)/δ) τ -t + 10 τ -t ln n + 1 δ . (17)
We would like to draw the attention of the reader on two features: one has to do with statistical considerations and the other with algorithmic ones. First, if the confidence intervals simultaneously hold for all t and all τ as in (17), it is possible, as the online learning process goes through, to discard the hypotheses f t which have their lower bound (according to (17)) on R rank (f t ) that is higher than the upper bound (according to (17) as well) on R rank (f t ) for some other hypothesis f t . This corresponds to a racing algorithm as described in [START_REF] Maron | Hoeffding races: Accelerating model selection search for classification and function approximation[END_REF]. Theoretically analyzing the relevance of such a race can be easily done with the results of [START_REF] Mnih | Empirical bernstein stopping[END_REF], which deal with empirical Bernstein racing, but for non-U-statistics. This full analysis will be provided in a long version of the present paper. Second, it is algorithmically possible to preserve some efficiency in computing the various variance estimates through the online learning process: these computations rely on sorting arguments, and it is possible to take advantage of structures like binary search trees such as AVL trees, that are precisely designed to efficiently maintain and update sorted lists of numbers. The remaining question is whether it is possible to have shared such structures to summarize the sorted lists of scores for various hypotheses (recall that the scores are computed on the same data). This will be the subject of further research.

Conclusion

We have proposed new empirical Bernstein inequalities designed for U-statistics. They generalize the empirical inequalities of [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF] and [START_REF] Audibert | Tuning bandit algorithms in stochastic environments[END_REF] while they merely result from two applications of the same non-empirical tail inequality for U-statistics. We also show how, in the bipartite ranking situation, the empirical variance can be efficiently computed. We mention potential applications, with illustrative results for the case of test set bounds in the realm of bipartite ranking. In addition to the possible extensions discussed in the previous section, we wonder whether it is possible to draw similar empirical inequalities for other types of rich statistics such as, e.g., linear rank statistics [START_REF] Hájek | Theory of Rank Tests[END_REF]. Obviously, we plan to work on establishing generalization bounds derived from the new concentration inequalities presented. This would require to carefully define a sound notion of capacity for U-statistic-based classes of functions (inspired, for example, from localized Rademacher complexities). Such new bounds would be compared with those proposed in [START_REF] Agarwal | Generalization Bounds for the Area under the ROC Curve[END_REF][START_REF] Clémenc ¸on | Ranking and empirical minimization of u -statistics[END_REF][START_REF] Freund | An efficient boosting algorithm for combining preferences[END_REF][START_REF] Rudin | Margin-based ranking and an equivalence between AdaBoost and RankBoost[END_REF] for the bipartite ranking and/or pairwise classification problems. Finally, we also plan to carry out intensive simulations -in particular for the task of online ranking-to get even more insights on the relevance of our contribution.

Figure 1 :

 1 Figure 1: First two plots: values of the right-hand size of (5) and (6), for D uni and kernel q m for m = 2 and m = 10 (see Example 1) as functions of n. Last two plots: same for D Ber (0.15).

Figure 2 :

 2 Figure 2: Left: UCI banana dataset, data labelled +1 (-1) in red (green). Right: half the confidence interval of the Hoeffding bound and that of the empirical Bernstein bound as functions of n test .

Acknowledgments

This work is partially supported by the IST Program of the EC, under the FP7 Pascal 2 Network of Excellence, ICT-216886-NOE. LR is partially supported by the ANR project ASAP.