Malika Ammam
email: m78ammam@yahoo.fr

Dung Di Caprio

Laurent Gaillon

Laurent Gaillo

Interfacial properties of mercury/ethylammonium nitrate ionic liquid + water system: electrocapillarity, surface charge and differential capacitance

Keywords: Dropping mercury electrode, Ethylammonium nitrate ionic liquid, Interfacial properties

published or not. The documents may come     Interfacial properties of mercury/ethylammonium nitrate ionic liquid+water system: Electrocapillarity, surface charge and differential capacitance

Introduction

Ionic liquids, or room temperature ionic liquids (Ils), constitute one of the most widely investigated material groups today both for their fundamental and enormous range of possible applications [1][START_REF] Tsuda | The electrochemical Society Interface[END_REF]. The synthesis of the first IL, ethylammonium nitrate (abbreviated as EAN) was described by Paul Walden in 1914 [START_REF] Walden | [END_REF]. The salt involves dissociable protons, which makes it a protic ionic liquid (PIL) [4]. Even thought, this first paper by Walden [START_REF] Walden | [END_REF] did not receive much resonance in the scientific world at its time, today EAN is the most extensively studied PIL. The interest in this salt has been largely driven by its many similarities in properties and behavior to water. In view of this, early work from the 1980s by Evans and coworkers showed many similarities between EAN and water, based strongly on the ability of EAN to promote aggregation of surfactants [5][6][7]. However, later work by Mirejovsky and coworkers showed that there are key differences between EAN and water, based on their heat capacities [8]. The main water like properties of EAN are: i) it can promote the formation of micelles [5], ii) has a high cohesive energy density [8][9], iii) is highly polar with solvophobic behavior [5,10] and iv) has water like properties in its enthalpy and entropy changes for the transfer of nonpolar gases to EAN [7]. On the other hand, both water and EAN have hydrogen bonding acceptor and donor sites, thus can form a hydrogen-bonded network structure [5].

However, the nature of the structure is different because EAN has a negligible heat capacity for dissolving nonpolar gases compared to that of water [8].

The large similarities between the properties of EAN to that of water gave rise to a wide range of applications. For example, EAN is used in biology for proteins renaturation and crystallization [11][12][13][14], as a reaction media for enzymes such as Candida Antarctica lipase B [11] and, to generate useful immunotoxins by modification of toxic protein such as mistletoe lectin 1 by EAN [15][16][START_REF] Pfuller | Patent DD262042-A[END_REF]. In the field of electrochemistry, EAN was found very useful as a nonaqueous electrolyte because it exhibits a wide potential window compared water [1,[START_REF] Schneider | [END_REF]. It is also used as electrolyte solutions for cyclic voltammetry experiments on ferrocene based complexes [19], reduction of uranium complexes [20], and reduction of a variety of metal ions [START_REF] Schneider | [END_REF]. In this context, it has been reported that hexavalent uranium was irreversibly reduced by EAN at 20 °C, while tetravalent uranium was unstable and formed hexavalent uranium within 5 h [20][21]. Also, the metal cations Cd 2+ , Zn 2+ , Cu 2+ , Pb 2+ , and Tl + all reversibly reduced in EAN, while Ni 2+ was irreversibly reduced, with very stable potentials [START_REF] Schneider | [END_REF]. It was also observed that the addition of water to EAN shift the redox potentials from -0.228 V to 0.327 V for ferrocene [19]. More recently, it has been reported that polyaniline films with improved characteristics can successfully be deposited from EAN solutions [22].

Ethylammonium nitrate is miscible with water to form a mixture of any composition, and both ions, C2H5H3N + and NO3 -, can favorably form hydrogen bonds with water molecules.

Physicochemical properties, such as molar volumes [23], heat capacity [23][24], vapor pressure [25] and, acidity/basicity [26] have been examined over the range of solvent composition. The studied quantities showed that EAN-water mixture is almost an ideal model system to study high concentrated electrolyte solutions. Ethylammonium cation involves three -NH protons capable of forming hydrogen-bonds, and the NO3 -anion can be bonded to the proton through the O atom. Ions in pure EAN are linked together to form a hydrogen-bonded network structure. On the other hand, in an EAN-water mixture, the hydrogen bonded network structure may be broken, and other kind of hydrogen-bonded structure involving cations, anions and water may be formed. The physicochemical properties may thus be strongly dependent on the EAN-solvent composition.

Interfacial phenomena of mixtures water-EAN is one of the electrolyte properties to take into consideration when interfacial electrochemical processes from these media are involved.

This study investigates the electrochemical properties at the interface between mercury electrode and EAN aqueous solutions at various concentrations, which might be relevant for eventual applications of electrode/EAN solutions in electrochemical processes such as electrodeposition of metal ions from these solutions [27]. On the other hand, while considerable data are available on diluted electrolyte solutions, the knowledge is still little for concentrated electrolyte solutions. The strong interactions between the charged species as well as the low solubility lead to complications, especially at the interface electrode/solution.

In this study, dropping mercury electrode (DME) is used because it is a useful tool to access interfacial properties between the electrode and the EAN solutions. More importantly, it behaves as an ideally polarized electrode in a wide range of potentials. Using DME, we have measured the surface tension of mercury/EAN solutions as a function of the potential. The first and the second derivative of the surface tension data led respectively to surface charge and differential capacitance. Analysis of these quantities provided information about the ionic structure at the interface mercury/EAN solutions.

Experimental

Materials

Ultrapure water milliQ grade with a resistivity of 18.

Equipment and procedures

The experiments were carried out using DME system schematically displayed in Fig. 1.

To prevent external mechanical vibrations, the system of Fig. 1 was set on an anti-vibration table. The height of the mercury column over the tip of the capillary was kept at a constant height. The three electrodes system was connected to a potentiostat that is in turn connected to a computer for data acquisition. To prevent the system from eventual contamination with KCl of the reference electrode, a ceramic frit  junction  is used to separate the reference electrode from the EAN studied solutions (Fig. 1). To remove dissolved gases such as O2, which may be reduced at the mercury electrode and interfere with the measurements, the studied solutions were degassed with Argon for at least 30 min prior to measurements. Finally, in order to prevent the system from eventual adsorption of contaminants, all material is rinsed with diluted nitric acid, ultrapure water and acetone prior to use.

The range of the potentials where DME is ideally polarized for the investigated solutions of (propylammonium nitrate (PAN), ethylammoniun nitrate (EAN), ammonium nitrate (AN) and potassium nitrate (PN)) was determined by linear sweep voltammetry and found to be in the range of -1600 to 500 mV vs. SCE. Beyond, electrochemical reactions can be produced.

The experiments consist of applying a constant potential and measure the time of 20 mercury drops. Near the potential of zero charge (PZC), the measurements were varied by 20 mV and outside this region; the measurements were swept by 50 mV. This is primarily carried out with the calibration solution (0.1 M KNO3), then with the EAN solutions at various concentrations ranging from 10 -2 M to pure EAN. The time of the mercury drops is recorded with a chronometer (  0.005s) and all the measurements were performed at 25  0.1 o C.

Theoretical considerations and reminders

Dropping mercury electrode (DME)

In work with a dropping mercury electrode, the height of the mercury column above the capillary tip governs the pressure driving mercury through the DME (Fig. 1), thus it is a key determinant of the mass m. In turn, m controls the drop time tmax, because the maximum mass that the surface tension can support (mtmax) is a constant defined by [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF]:

mtmaxg = 2r ( 1
)
where g is the gravitational acceleration, r is the radius of the capillary, and  is the surface tension of the interface mercury/solution.

Eq. (1) gives the relationship between the drop time, a parameter that is experimentally measurable and surface tension. Thus, surface tension can be deduced from Eq. (1) as:  = mtmaxg/2r and, m can be replaced by the Archimedes Principle (Buoyancy) to yield:

 = Vtmaxg(Hg-sol)/2r ( 2
)
where V is the volume, Hg is the density of mercury and, sol is the density of the solution.

In Eq. ( 2) volume, V, and the radius of the capillary r, which is more precisely the radius of the link between the mercury drop and the capillary at the time when the drop falls are usually unknown. To overcome this problem as well as to obtain reproducible results, the DME apparatus is calibrated with a solution that have a known surface tension. In this study, 0.1 M KNO3 was selected as a calibration solution because KNO3 has the same anion as EAN (NO3 -

). The concentration of 0.1 M is selected for calculus simplification reasons. Because it is a diluted solution, its density can be assimilated to the density of water. Accordingly, for 0.1 M KNO3, Eq. ( 2) can be written as:

KNO3 = Vtmaxg(Hg-water)/2r (3)
The ratio of Eq. ( 2) to Eq. ( 3) gives the final formula, which allows calculating the surface tension of the mercury/EAN solutions:

EAN = tmax(EAN)KNO3(Hg-sol)/ tmax(KNO3)(Hg-eau) (4)
where Hg equals 13.534 g/cm 3

Ideally polarized electrode (IPE)/solution

An electrode or an interface electrode/solution is called ideally polarized when no charge transfer at the interface of the electrode/solution can occur regardless of the applied potential.

While no real electrode can behave as an IPE over the whole range of the potential available in a solution, some electrode/solution systems such as DME can approach ideal polarizability over limited potential ranges. Although in this region, reduction of water is thermodynamically possible, it occurs at a very low rate at DME. Hence, the only Fradaic current that flows in this region is due to charge-transfer reactions of trace impurities such as metal ions, oxygen, and organic species, and this current is quite negligible in clean systems.

Since charge cannot cross IPE interface when the potential across it is changed, the behavior of the electrode/solution interface is analogous to that of a capacitor. A capacitor is an electrical circuit element composed of two metal sheets separated by a dielectric material.

Its behavior is governed by the equation [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF]:

C = q/E ( 5
)
where q is the charge stored on the capacitor (in coulombs, С), Е is the potential across the capacitor (in volts, V), and С is the capacitance (in farads, F).

During the charging process, a current (called the charging current) will flow. The charge on the capacitor consists of an excess of electrons on one sheet and a deficiency of electrons on the other side. The electrode/solution interface has been shown experimentally to behave like a capacitor, and a model of the interfacial region somewhat resembling a capacitor can be given [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF]. At a given potential, there will exist a charge on the metal electrode, qm, and a charge in the solution, qsol. Whether the charge on the metal is negative or positive with respect to the solution depends on the potential across the interface and the composition of the solution. At all times, however, qm=-qsol, or often divided by the surface area of the electrode and expressed as charge densities, m = -sol, usually given in C/cm 2 . The charge density on the metal, m, represents an excess or deficiency of electrons and resides in a very thin layer (<0.1 Å) on the metal surface. The charge density in solution, sol, is made up of an excess of either cations or anions in the vicinity of the electrode surface. The whole array of charged species and oriented dipoles existing at the metal/solution interface is called the electrical double layer. At a given potential, the electrode/solution interface is characterized by a double layer capacitance, Cd, typically in the range of 10 to 40 F/cm 2 . However, unlike real capacitors, whose capacitances are independent of the voltage across them, Cd, is often a function of potential [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF].

Description of the electrical double layer

Metal side

The side of the double layer on the metal side can be modeled by the so-called Jellium model [START_REF] Kittel | Quatum theory of solids[END_REF]. The latter considers the metal side of the double layer as a jelly of positive ions with a uniform charge distribution and, in which a cloud of mobile electrons behave as a gas.

The metal side is overall electrically neutral. Despite the kinetics, the electrons cannot move farther from the metal because of the strong forces exercised by the cations. The latter yields a potential gap which prevents the electrons from moving farther from the surface.

Solution side

The solution side of the double layer is thought to be made up of several "layers". That closest to the electrode, the inner layer, contains solvent molecules and sometimes other species (ions or molecules) that are said to be specifically adsorbed [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF]. This inner layer is also called the compact, Helmholtz, or Stern layer. The locus of the electrical centers of the specifically adsorbed ions is called the inner Helmholtz plane, which is at a distance x1. The total charge density from specifically adsorbed ions in this inner layer is i (С/сm 2 ).

Solvated ions can approach the metal only to a distance x2(x2>x1); the locus of centers of these nearest solvated ions is called the outer Helmholtz plane. The interaction of the solvated ions with the charged metal involves only long-range electrostatic forces, so that their interaction is essentially independent of the chemical properties of the ions. These ions are said to be nonspecifically adsorbed. Because of thermal agitation in the solution, the nonspecifically adsorbed ions are distributed in a three dimensional region called the diffuse layer, which extends from the outer Helmholtz plane into the bulk of the solution. The excess charge density in the diffuse layer is d, hence the total excess charge density on the solution side of the double layer, sol, is given by:

sol = i + d = -m (6)

Electrocapillarity

Eq. ( 4) illustrated the relationship between the surface tension and drop time. In turn, the relationship between surface tension and potential is given by Lippman's equation, resulting from the general equation of electrocapillarity at constant chemical potential, µi, temperature, T, and pressure, P [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF][START_REF] Lippmann | [END_REF]:

(-d = mdE)i,T,P (7)
The plot of the curve of surface tension as a function of potential ( = f(E)) called electrocapillarity curve, has the nearly parabolic shape that is usually characteristic of these curves, although there are significant variations in the curves as the electrolyte is changed. A feature common to all of the curves is the existence of a maximum in surface tension. The potential at which it occurs is the electrocapillarity maximum (ECM) and is an extremely important point in the system. Since the slope of the curve is zero there, it is the potential of zero charge (PZC), where m = sol = 0. At more negative potentials, the electrode surface has a negative excess charge, and at more positive potentials there is a positive surface charge.

The units of the electronic charge composing any excess repel each other, hence they counteract the usual tendency of the surface to contract, and they weaken the surface tension.

Usually, the electrocapillarity curves do not yield enough information about the ionic structure at the interface. More information can be obtained from surface charge and differential capacitance data [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF]. Surface charge is obtained from the derivative of the electrocapillarity curve:

m = -/Ei,T,P (8)
In turn, differential capacitance is obtained from the derivative of surface charge curve:

Cd = m/Ei,T,P (9)

Results and discussion

Electrocapillarity curves of mercury/EAN solutions

In this study, after obtaining experimentally the curves of drop time as a function of potential, polynomial regression fittings of different orders, 6, 7 and 8 have been employed.

Overall, no significant difference in the form, shape or position between the resulting fitted curves was noticed. Accordingly, a polynomial fitting of degree 6 was selected and using Eq.

(4) which relate the surface tension to drop time, the electrocapillarity curves ( = f(E)) of the investigated EAN-water compositions were obtained as shown in Fig. 3A. One can clearly see the parabolic shape of the curves. Also, all the curves show the presence of surface tension maximum around -500 mV vs. SCE, corresponding to the potential of zero charge (PZC). At high or low potentials from PZC, the surface tension decreases due to the accumulation of charges on both sides of the metal/solution as described in paragraph (3.4).

The surface tension of pure air/EAN equals 47.3 mN/m [32][33], that of water/air is reported as 71.97 mN/m (equilibrium at 25 o C) [34] and, the surface tension of mercury/air equals 487 mN/m (15 o C) [34]. Fig. 3A reveals that the recorded surface tensions are close to the reported value for mercury/air. This means that a large part of the surface tension of mercury/EAN solutions would be attributed to the metal mercury, rather than to EAN. Fig. 3A also depicts that the shifts in surface tension is more significant at potentials higher than PZC than at lower potentials and, the shifts become more pronounced at elevated EAN In order to examine the eventual effects of the ethyl group of the EAN cation on these components, the results will be examined and compared with respect to ammonium nitrate (AN) [35]. the number of the hydrogen bonds [36], the surface tension of mercury/pure PAN is reduced compared to that of EAN. Fig. 4B clearly shows that the surface tension at PZC decreases when the number of carbon atoms of the ammonium cation (AN, EAN and PAN) increases.

Effect of the EAN concentration on surface tension at PZC

Effect of the EAN concentration on PZC

Fig. 5A compares the curves of variation of PZC as a function of the concentration of EAN with respect to AN. At c=0, the two curves should point to the same PZC value, which is the PZC of mercury/water interface. However, a slight shift can be observed in Fig. 5A, which will be assigned to errors in the measurements. Fig. 5A depicts that the two substances EAN and AN behave differently at high concentrations (c4 M). For 0c11.2 M, large shifts in PZC can be noticed and reaches 160 mV for mercury/saturated AN. The reason for that may have to do with: i) the effect of the liquid-liquid junction and/or, ii) the effect of the specific adsorption.

Effects of the liquid-liquid junction occurs between the reference electrode SCE and the EAN or AN solutions when the concentration changes from pure water to pure molten salt for EAN or saturated solution for AN. The liquid-liquid junction potential is influenced by several parameters including nature of the solvent, nature of the ions and their activities in solution. With regard to nature of the ions, it is generally assumed that KCl is equitransferent [37] and, we think that it might be the case for EAN ions. The liquid-liquid junction potential is thus ion concentration independent and will only be influenced by the nature of the solvent on both sides of the junction. For EAN concentrations (0<c 4M), the molar ratio of EAN to water is <0.1. Consequently, it can be assumed that water is the solvent on both sides of the junction and the liquid-liquid junction potential is constant in that range of concentrations. For higher EAN concentrations (c>4M), theoretically, it would be incorrect to consider water as a solvent. But, since the structure of these concentrated solutions as well as the chemical potentials of the ions are unfortunately unknown, hence, we will assume that the liquid-liquid junction potential is constant for the whole range of the explored concentrations and only the change in the specific adsorption will be considered.

Shifts in PZC as a function of the concentration may also be assigned to specific adsorption of the charged species, called Esin-Markov effect [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF][START_REF] Esin | Ada Physicochem[END_REF]. If we consider a system in which the anion is specifically adsorbed and the electrode is being held at the PZC. If we introduce more of the same electrolyte substance, more anions will be adsorbed; hence sol becomes nonzero and must be balanced. Since the electrode is more polarizable than the solution, the counter charge is induced there. To regain the condition m = 0, the potential must be shifted to a more negative value, so that the charge excess of specifically adsorbed anions is exactly counterbalanced by an opposing excess charge in the diffuse layer. Thus specific adsorption of anions is indicated by negative shifts in potential at constant charge density, whereas specific cationic adsorption is revealed by positive shifts, as the electrolyte concentration is elevated [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF]. Fig. 5A displays that at c<4 M, the PZC reduces as the concentration increases for both substances EAN and AN. This would be attributed to the adsorption of excess nitrate anions in the inner Helmholtz plane. Furthermore, it can be noticed that the shift is more pronounced for AN compared to that of EAN, suggesting that the excess adsorbed nitrate anions at the interface are more important for AN than for EAN.

The reason for that may have to do with the presence of the ethyl group in EAN that creates some kind of competition between the nitrate anion and the ethylammonium cation. However, in this range of concentrations, this effect is nevertheless not sufficient to reverse the adsorption of the excess anions into excess cations. By contrast, for c>4 M, the curve corresponding to AN continues to decrease suggesting a dominant specific anionic adsorption of nitrate ions, while the EAN curve shows an increase. Assuming a liquid-liquid junction potential that is constant for the whole range of the explored concentrations, the increase observed in the EAN curve would be related to the adsorption of excess ethyl ammonium cations. In this context, if presence of the ethyl group creates an excess cationic adsorption at higher concentrations, one can wonder the consequences of a longer hydrocarbon chain. Fig. 5B displays the relationship between PZC and the number of carbon atoms introduced within the ammonium cation (AN, EAN and PAN). It is clear that the more the hydrocarbon chain becomes longer, the more the PZC increases. This demonstrates that elongation of the hydrocarbon chain within the ammonium cation favors the adsorption of excess cations.

Generally speaking, the electrocapillarity curves do not give enough information about the interfacial structure. The first and the second derivative of the electrocapillarity curves yield respectively the surface charge and the differential capacitance, two important quantities to examine in order to have a better idea on the behavior of the cationic and the anionic species at the interface.

Surface charge of mercury/EAN solutions

Fig. 6A shows the surface charge curves (m-E) of the various studied EAN-water compositions. Around the PZC, no significant shift between the curves obtained at various EAN concentrations can be noticed. At more positive or negative potentials, shifts between the curves can be observed. However, at these potentials, it is important to remind that the curves are very sensitive to edge effects of the polynomial regression fittings employed in the electrocapillarity curves. Hence, their interpretations will not be very useful. A zoom of Fig.

6A around PZC yields Fig. 6B with a better view. It is clear from Fig. 6B that PZC for the investigated concentrations are located between -470 and -508.4 mV vs. SCE. A slight difference between the positive and the negative surface charges with respect to PZC of each concentration can also be noticed. In the range of potentials located at -600 to -380 mV vs.

SCE, the highest positive charge with respect to PZC is recorded as 4 C/cm 2 and, the highest negative charge is around 3.4 C/cm 2 . With respect to the recorded positive charge, the charge on the metal mercury is positive, thus, the excess charge on the solution side will be negative, which would essentially be induced by an excess of the nitrate anions. By contrast, at potentials below PZC, the excess charge on the metal mercury is negative; hence the excess charge on the solution side is positive induced essentially by the presence of excess ethylammonium cations. At PZC for each concentration, it is clear that the charge on both sides mercury and EAN solution is zero. The latter can be interpreted by the presence of both ion species, nitrate anion and ethylammonium cation on the EAN solution side, without neglecting water molecule that will preferably be adsorbed in the inner Helmholtz plane. For pure EAN, ion pairs are the species present on the solution side of the interface.

Differential capacitance of mercury/EAN solutions

Fig. 7A displays the differential capacitance curves (Cd-E) for the various explored EAN concentrations. The double layer capacitance, Cd, can be assumed of two components series that are attributable to two layers: i) Helmholtz layer, CH, and, ii) diffuse layer, CD. This model known as the Gouy-Chapman-Stern (GCS) model gives predictions that account for the gross features of behavior in real systems that might be useful to access some information about the mercury/EAN solutions interfaces [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF]39]:

1/Cd = 1/CH + 1/CD ( 10
)
Generally speaking, the value of СH is independent of potential, but CD varies in the V-shaped fashion that displays a minimum at PZC called the Gouy-Chapman minimum [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF]. The composite capacitance, Cd, should have a complex behavior that is governed by the smaller of the two components of Eq. (10). Near the PZC in systems with larger electrolyte concentrations and small ions size, CD, is so large that it no longer contributes to, Cd, and one sees only the constant capacitance of, CH. Accordingly, at low EAN concentrations, one can expect to observe a V-shaped fashion characteristic of, CD. Here, the lowest explored EAN concentration equals 10 -2 M, and unfortunately no minimum can be seen in Fig. 7A around the PZC. However, it is possible that 10 -2 M is not low enough to yield a V-shaped fashion of capacitance around PZC. Theoretically, the concentration has to be lower than 10 -2 M.

Nevertheless from the experimental standpoint, the latter is definitely not an easy task because the more the concentration becomes lower, the more the conductivity decreases. There is another factor that may be the reason for the absence of the Gouy-Chapman minimum and the latter has to do with the polynomial regression fitting order. With respect to this, our analysis of the data showed no significant change in the position of the curves minima with the polynomial regression fitting order up to 8. Thus, the absence of the minimum around PZC for the whole range of the explored EAN concentrations suggest that the double layer capacity of mercury/EAN solutions would essentially be attributed to Helmholtz capacity, CH. On the other hand, two minima on both sides of the PZC for each EAN concentration can clearly be observed in Fig. 7A. The values of the differential capacitance recorded for the minima located at higher potential of PZC are more important than those observed at lower potentials.

This difference can be related to different factors including surface charge, thickness of the double layer and the dielectric constant. If we assume that, CD, is negligible, the double layer capacitance that is attributable to, CH, can be assimilated to a parallel electric capacitor [START_REF] Bard | Electrochemical methods: fundamentals and applications[END_REF]:

Cd = 0/d (11)
Where, d, represents the distance between the metal surface and the Helmholtz layer, , is the relative dielectric constant in the Helmholtz layer and, 0, is dielectric constant of vacuum.

Accordingly, the large capacitance values recorded at potentials higher than PZC in Fig. 7A can be attributed either to a small distance, d, or to a large dielectric constant, . The distance, d, essentially depends on the dimensions of the adsorbed species and their orientations at the interface, while the dielectric constant depends on the solvent properties in the inner layer.

With regard to nitrate, the specie is symmetric with a trigonal planar geometry. However, ethylammonium cation has a tetrahedral geometry with an asymmetry that is related to the presence of the ethyl group. The behavior of the differential capacitance observed in Fig. 7A can be related either to the radius of the nitrate anion that is smaller than the radius of the ethylammoinium cation or, to ethylammonium cation that oriented its hydrocarbon chain towards the mercury metal, thus resulting in a larger distance, d, compared to that of the nitrate anion. With respect to dielectric constant, the discussion would only be possible for pure EAN because there will be no water molecules in the inner layer. In that case, the low capacitance values observed for potentials below PZC might be attributed to the weak polarization of the ethylammonium cation from the hydrocarbon chain side, which will consequently be oriented towards the metal mercury.

A zoom of Fig. 7A The two curves depict an initial increase in capacitance at low concentrations (c1 M) followed by a decrease at higher concentrations (c>1 M). Fig. 8 also reveals a particular drop in capacitance at 7 M for the EAN curve compared to the rest of the concentrations. Analysis of the data at 7 M revealed that the results obtained using different polynomial regression fittings are not stable as shown in Fig. 9A. In contrast, for other concentrations, the results are quite stable as evidenced by Fig. 9B for 5 M as an example. This suggests that the experimental results obtained at 7 M EAN may contain errors. If we delete it from Fig. 8 and assume that the particularly elevated value obtained at 1 M is also due to errors (Fig. 10), one can propose that the differential capacitance values of EAN would overall be lower than those corresponding to AN and, this would essentially be related to presence of the ethyl group in EAN cation. In this context, if we assume that the two ionic species, the anion and the cation, for each interface mercury/EAN and mercury/AN are adsorbed, this difference can be explained by a larger thickness of the Helmholtz layer for mercury/EAN interface, which can be understood by the preferential orientation of ethyl group of the EAN cation towards the metal mercury.

Concluding remarks

In this account, the surface tensions between mercury electrode and EAN-water mixtures at various compositions have been measured. Electrocapillarity, surface charge as well as the differential capacitance curves have been obtained. Assumptions that are based on simple hypotheses and comparison of the EAN behavior with respect to that of AN provided information about the ionic structure at the interface mercury/EAN solutions. Influence of the hydrocarbon chain of the ammonium cation is clearly visible on the electrocapillarity maximum. The surface tension reduces as the hydrocarbon chain is elongated (AN, EAN and PAN). The latter has been attributed to two factors: i) replacement of a hydrogen atom with a hydrocarbon chain within the ammonium cation decreases the number of the hydrogen bonds and, ii) elongation of the hydrocarbon chain increases the adsorption of excess cations at the interface. In regard to specific adsorption it is found that the adsorption phenomena become more important as the NEA concentration increases and the maximum effect is observed for pure EAN. Assumption based on liquid-liquid junction potential that is constant for the whole range of the studied concentrations allowed to study the specific adsorption phenomena induced at PZC as a function of the concentration. For low EAN concentrations (c<4 M), the excess adsorption was found to be anionic and reverses to cationic at higher concentrations.

The latter differs from the behavior of AN where excess anionic adsorption dominants the whole range of the studied concentrations. The differential capacitance data of mercury/EAN and mercury/AN solutions at PZC as a function of the concentration are found to follow similar trends. However, the capacitance values of mercury/EAN are overall lower than those of mercury/AN. The latter has been interpreted by the preferential orientation of ethyl group of the EAN cation towards the metal mercury.

  at 20 o C, water equals 0.996 g/cm 3 at 20 o C and, the density of the EAN solution, sol, is determined from Fig. 2 obtained from the partial molar volumes reported in literature at 25 o C [23] by, assuming equal densities at 20 o C and 25 o C. The surface tension of the calibration solution, KNO3, is taken as 424 mN/m [29].

  concentrations. Careful analysis of Fig.3Aaround PZC reveals a change in position of the PZC as a function of the EAN concentration. It is worth reminding that the position of zero charge is characterized by two components maximum surface tension and potential of zero charge. Each component will separately be addressed as a function of the EAN concentration.

Fig. 3B compares

  Fig.3Bcompares the curves of variation of surface tension at PZC as a function of the concentration of EAN with respect to AN. At c=0, the curves of EAN and AN should indicate the surface tension of water and point to the same value. However, a slight shift can be noticed in Fig.3Bwhich will be assigned to experimental errors. Fig.3Balso shows that the surface tension of EAN and AN decreases as the concentration increases. Furthermore the decrease obtained with EAN is more significant than that of AN and, the shift between the two curves, becomes more pronounced as the concentration is getting higher. The surface tension results from the change in the surrounding environment of the species located close to surface compared to those located in bulk. The species close to the surface are influenced by two kinds of interactions i) those exercised by the solution and, ii) those induced by the metal. The interactions that might be present in EAN and AN solutions would essentially be electrostatic and hydrogen bonds. It turn out that microscopically the significant decrease in the surface tension obtained with EAN compared to that of AN would particularly be attributed to substitution of one hydrogen atom in AN by an ethyl group in EAN. This leads to a decrease in the number of the hydrogen bonds. The latter is supported by Fig.4A, which compares the variation of the surface tension as a function of potential of mercury/propylammonium nitrate (PAN) with respect to EAN. PAN is a protic ionic liquid with a melting temperature of 4 o C and a density of 1.1568. As one can expect from the strong amphiphilic nanostructure due to presence of the propyl group in PAN and, which may reduce

  around PZC yields Fig. 7B which shows a better view about the influence of the EAN concentration on differential capacitance. The relationship between the differential capacitance at PZC and the EAN concentration in comparison with AN are gathered in Fig. 8. It will be noted that the two curves of EAN and AN follow similar trend.

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. Schematic representation of the dropping mercury electrode (DME) system used in this study.

Fig. 4 .

 4 Fig. 4. (A) Comparison between the electrocapillarity curves of pure EAN with respect to pure PAN, (B) Relationship between surface the tension at PZC and number of the carbon atoms present within the ammonium cation (AN, EAN and PAN).

Fig. 5 .

 5 Fig. 5. (A) Variation of PZC as a function of the EAN concentration with respect to that of AN, (B) Relationship between PZC and number of the carbon atoms present within the ammonium cation (AN, EAN and PAN).

Fig. 7 .Fig. 8 .

 78 Fig. 7. (A) Differential capacitance as a function of the potential for the various EAN concentrations, (B) Zoom of (A) around PZC.

2 )Fig. 9 .

 29 Fig. 9. Variation of the differential capacitance with the polynomial regression fitting order of 6, 7 and 8 for EAN at 7 M (A) and 5 M (B).

Fig. 10 .

 10 Fig. 10. Corrected Fig. 8

Acknowledgements

The authors acknowledge the support of CNRS and the University of Paris VI (France) and Natural Sciences and Engineering Research Council of Canada and UOIT (Canada).


Jérôme Bodin

Antoine Beylot

Jacques Villeneuve

Kathy Bru

Augustin Chanoine

Pierre-Alexis Duvernois

Françoise Bodénan

Coupling simulation of mineral processing with Life Cycle Assessment to assess the environmental impacts of copper production

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Coupling simulation of mineral processing with Life Cycle Assessment to assess the environmental impacts of copper production

Jérôme Bodin 1 , Antoine Beylot 1 , Jacques Villeneuve 1 , Kathy Bru 1 , Augustin Chanoine 2 , Pierre-Alexis Duvernois 2 , Françoise Bodénan 1 1 BRGM. 3 avenue Claude Guillemin, 45060 Orléans, France 2 Deloitte. 185 avenue Charles de Gaulle, 92200 Neuilly-sur-Seine, France Key-words: process simulation, LCA, copper production, USIM PAC™ Life Cycle Assessment (LCA) has been recently intensively used to quantify the environmental impacts of metal production, in particular considering copper. In this context, this study aims at coupling simulation of mineral processing with LCA to assess the environmental performance of metal production in a life cycle perspective. Process simulation builds on reported experimental data measured from a complete sampling campaign, so that process flowrates and composition for all the water and material circuit streams are assessed. However, standard process simulation usually primarily focuses at resource efficiency (how much metal is recovered?). The coupling with LCA is implemented to additionally account for the process "eco-efficiency" in the assessment of its performance (what are the environmental impacts that the process induces?).

Coupling process simulation and LCA could have several benefits: it would allow providing a consistent view of the whole process chain, in particular by covering the upscaling step and filling the data gaps. The coupling of both methods is applied to the case of a process chain for copper production from a black shale rich ore. This process chain includes standard concentration operations (comminution, classification and flotation) and further operations in hydrometallurgy (bioleaching and metal recovery).

Experimental work has namely been performed with a view to optimizing the recovery of metals in some flotation steps. In this study, the mass balance is calculated, operation by operation. A process simulation is performed by using the process simulation software USIM PAC™, including complete flow sheet definition, choice of models for the unit operations and adjustment of the simulator to the operation mass balances. For the simulation outputs to be complete for the derivation of the process chain Life Cycle Inventory (LCI), the models already implemented in USIM PAC™ are complemented by additional models that link emissions to the environment and consumptions of reagents to the processed ore all along the process chain. The inputs/outputs relative to each operation are accordingly calculated through mineral processing simulation. These data are further used as inputs to LCI modeling and subsequent Life Cycle Impact Assessment, by using standard LCA database software (i.e. ecoinvent & SimaPro). The calculated environmental impact indicators enable to determine the key environmental issues related to the developed process chain, in particular through a hotspot analysis (highlighting which operations and which emissions are the highest contributors to the environmental impacts of the analyzed system). Finally, the potentialities for applying simulation of mineral processing coupled with LCA in support to the environmental assessment of mineral processing chains is demonstrated by modeling the effect of ore changes and technological innovations through sensitivity analysis, by taking into account their related specific parameters when performing their environmental assessment.


Méthodes à noyaux appliquées

aux textes structurés Sujeevan Aseervatham, Emmanuel Viennet

Introduction

De nombreuses techniques d'apprentissage numérique appliquées au traitement de données textuelles utilisent une représentation du texte en "sac de mot". Ce codage, qui a l'avantage de la simplicité, n'utilise que les fréquences d'apparition des mots dans les documents et perd toute information liée à l'ordre des éléments (ordre des mots, structure en paragraphes ou sections, etc). Depuis une petite dizaine d'années, une nouvelle famille d'algorithme d'apprentissage, basée sur la notion de noyaux, fait l'objet d'intenses recherches. Ces noyaux permettent de définir des mesures de similarité utilisables dans de nombreux algorithmes d'apprentissage statistique (de l'analyse discriminante de Fisher aux machines à vecteur de support). Récemment, l'utilisation de noyaux spécifiques pour le traitement de données textuelles structurées a commencé à faire l'objet de recherches. Dans le cadre de la sous-tâche 3.12 du projet InfoM@gic, le LIPN a décidé de travailler sur l'application de ces méthodes à noyau au traitement de données textuelles structurées. Ce rapport intermédiaire présente un bref état de l'art dans ce domaine. Nous passons en revue les principaux types de noyaux proposés ces dernières années pour le traitement des séquences et plus généralement des données structurées (arbres, graphes).

Le noyau de convolution

Le noyau de convolution appelé R-noyau [START_REF] Haussler | Convolution kernels on discrete structures[END_REF] permet de définir un cadre général pour les noyaux appliqués aux données structurées telles que les arbres et les graphes. Les données structurées sont des objets pouvant être décomposés en sous-objets jusqu'à atteindre une unité atomique. L'idée du R-noyau est de calculer la similarité entre deux éléments x et y en effectuant une décomposition de x et de y. Plus formellement, soit x un élément appartenant à un ensemble X d'éléments structurés de même type, x peut être décomposé en sous éléments (x 1 , . . . , x D ) où x d peut être un élément structuré ou non appartenant X d . On définit la relation binaire R : X 1 × . . . × X D → X qui associe les parties d'un élément x à x et la relation inverse R -1 : {x = (x 1 , . . . , x D )|R(x, x)} qui retourne pour x l'ensemble de toutes les décompositions possibles. Le noyau de convolution (R-noyau) pour deux éléments x et y de X est alors :

k R (x, y) = x∈R -1 (x) y∈R -1 (y) d i=1 k i (x i , y i )
Le noyau p-Spectrum a été utilisé par Leslie et al. [START_REF] Leslie | The spectrum kernel : A string kernel for svm protein classification[END_REF] pour la classification de séquences de protéines avec l'algorithme SVM (Séparateur à Vaste Marge). Les résultats obtenus sur la base de données SCOP (Structural Classification of Proteins) ont montré que la classification par SVM avec le noyau p -Spectrum donne des résultats semblables aux méthodes génératives basées sur les modèles de Markov cachés. Cependant, la méthode SVM avec le noyau Fisher reste la plus performante pour la classification de séquences de protéines.

Le noyau All-SubSequences

Le noyau All-SubSequences [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF] permet de tenir compte des sous-séquences non contiguës de toutes tailles. Ainsi, la fonction Φ A (s) permet de plonger la séquence s dans un espace vectoriel dans lequel le u ième composant de Φ A (s) indique la fréquence d'occurrence de la séquence u dans s. On dira que u est une sous-séquence non contiguë de s, s'il existe un ensemble I = {i 1 , . . . , i |u| } tel que ∀j ∈ {2, . . . , |u|}, i j-1 < i j et ∀j ∈ {1, . . . , |u|}, u(j) = s(i j ) (u(j) désignant le j ième élément de u). On notera s[I] = u pour désigner le fait que chaque élément de u(j) est identique à l'élément s(i j ) avec i j ∈ I.

Φ A u (s) = I:s[i]=u 1 D'où : k A (s, t) = (I 1 ,I 2 ):s[I 1 ]=t[I 2 ]
1 Il est possible de définir ce noyau de manière récursive. En effet, il suffit de remarquer que toute sous-séquence de s contenant le dernier caractère a de s, tel que s = s ′ a, ne peut apparaître dans t qu'entre le premier caractère de t et la dernière occurrence de a dans t. Ainsi, on a :

k A (s, ǫ) = 1 k A (s ′ a, t) = k A (s ′ , t) + k:t[k]=a k A (s ′ , t[1 . . . k -1])
L'avantage de ce noyau est qu'il est capable de capturer tous les motifs communs à deux séquences. Le désavantage est que l'espace de projection est de très haute dimension entraînant un temps de calcul important.

Le noyau p-Fixed length SubSequence

Le noyau p-Fixed length SubSequence [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF] est un compromis entre le noyau p-Spectrum et le noyau All-SubSequences. Il permet de limiter la recherche de sous-séquences à des sousséquences non contiguës de taille p. Ainsi, la fonction de projection Φ F (s) sera composée des éléments Φ A u (s) tels que |u| = p. De même que précédemment, on pourra définir ce noyau par récursion en notant que la récursion sera définie sur la séquence, en retirant à chaque étape le dernier élément de la séquence, mais aussi sur la taille p du motif. En effet, si le dernier caractère du motif a été fixé, le préfixe du motif ne peut être constitué que de p -1 éléments.

k 0 (s, t) = 1 k p (s, ǫ) = 0 pour p > 0 k p (s ′ a, t) = k p (s ′ , t) + k:t[k]=a k p-1 (s ′ , t[1 . . . k -1])

Le noyau String Subsequence (SSK)

L'un des inconvénients des noyaux traitant les sous-séquences non contiguës précédemment vus est qu'ils ne tiennent pas compte de la distance séparant les éléments non contiguë. En effet, prenons l'exemple de deux séquences "aaab" et "aab", la séquence "ab" est une sous-séquence des deux premières mais elle est plus similaire à la deuxième qu'à la première. Or, les noyaux All-SubSequences et p-Fixed length SubSequence attribueront la même valeur aux couples ("aaab", "ab") et ("aab", "ab").

Le noyau String Subsequence [START_REF] Lodhi | Text classification using string kernels[END_REF] permet de tenir compte de la discontinuité dans le calcul de la similarité en pondérant les séquences en fonction de leur taille. Pour une séquence s, la fonction de projection Φ SSK (s) sera défini pour tout u ∈ Σ n par :

Φ SSK u (s) = I:u=s[I] λ card(I)
Le noyau SSK, de paramètre n, pour deux séquences s et t est alors :

k n SSK (s, t) = u∈Σ n I:u=s[I] J:u=t[J] λ card(I)+card(J)
Comme pour les noyaux précédents, en utilisant la programmation dynamique, on peut réduire la complexité à O(n.|s|.|t|).

Des expérimentations ont été menées dans [START_REF] Lodhi | Text classification using string kernels[END_REF] pour évaluer les noyaux SSK, p-Spectrum et le noyau standard Bag Of Words [START_REF] Th | Learning to Classify Text Using Support Vector Machines : Methods, Theory and Algorithms[END_REF]. La base de données utilisée est la base Reuters-21578 contenant des documents en langage naturel. L'expérience consistait a effectuer un classement binaire des documents après avoir effectué un apprentissage sur les données prévues à cet effet. Les documents ont été pré-traités en éliminant les mots d'arrêts et les signes de ponctuations. Les résultats ont montrés que les string kernels sont plus performants que l'approche standard du Bag Of Words. De plus, le noyau SSK est le plus performant lorsque la valeur de pondération est choisie judicieusement. De même, lorsque la taille p est choisie convenablement, le noyau p-Spectrum donne les meilleurs résultats. Les deux inconvénients pour l'utilisation de ces noyaux dont d'une part le temps de calcul et d'autre part le choix des paramètres qui doivent être fait de manière spécifique à chaque application.

Le noyau Séquence marginalisée

Le noyau marginalisé pour les séquences a été introduit par Kashima et al. [START_REF] Kashima | Kernel-based discriminative learning algorithms for labeling sequences, trees, and graphs[END_REF]

y i = argmax y P (y i = y|x i ) = argmax y y:y i =y P (y|x)
Partant de cette dernière approche, Kashima et al. [START_REF] Kashima | Kernel-based discriminative learning algorithms for labeling sequences, trees, and graphs[END_REF] propose une méthode pour étiqueter une séquence. Cette méthode se base sur l'utilisation d'un perceptron à noyau [START_REF] Shawe-Taylor | Kernel Methods for Pattern Analysis[END_REF]. L'idée étant d'étiqueter les éléments individuellement, une séquence (x, y) est décomposé en triplés (x, t, y t ) où y t est le t ime élément de x. Pour cela, le perceptron à noyau est entraîné avec des séquences étiquetées auxquelles ont été rajoutés des exemples négatifs. Les exemples négatifs sont obtenus pour chaque couple (x, y) en modifiant les valeurs de y. Ainsi pour ce couple on obtient un ensemble de positifs {(x, i, y i ) : 1 ≤ i ≤ dim(x)} et un ensemble de négatifs {(x, i, z) : 1 ≤ i ≤ dim(x) ∀z ∈ Σ y }. Après apprentissage, on affecte à un élément u t d'une séquence u l'étiquette y qui maximise le score calculé par le perceptron avec un noyau marginalisé.

Le noyau marginalisé proposé est le suivant :

k(x, x ′ , τ, t, y τ , y ′ t ) = z:zτ =yτ z ′ :z ′ t =y ′ t P (z|x)P (z ′ |x ′ ) Φ(x, z; τ ), Φ(x ′ , z ′ ; t) (1)
y τ et y ′ t étant les étiquettes respectives des éléments x τ et x ′ t ; φ f (x, y; t) indiquant la fréquence d'occurrence de f dans (x, y) incluant la t ième position. La combinatoire induit par le noyau de l'équation 1 peut-être diminuée en effectuant une recherche bidirectionnelle au sein d'une séquence. En effet, la composante φ f (x, y; t) du vecteur Φ(x, y; t) indique le nombre d'occurrence de f dans (x, y) incluant la t ième position de (x, y) ((x t , y t )). Il est alors possible de décomposer f en f u et f d tel que ((x t , y t )) soit le dernier élément de f u et le premier élément de f d . Le calcul se limitera alors à évaluer les deux ensembles

F u = {(x i , x i+1 , . . . , x t )|1 ≤ i ≤ t} et F d = {(x t , x t+1 , . . . , x k )|t ≤ k ≤ dim(x)}.
Les autres composantes de l'espace seront obtenues par combinaison de F u et de

F d i.e. F = F u × F d .
La figure 1 illustre ce principe : le couple de séquences (a) peut être obtenu en combinant (b) et (c). Afin d'effectuer la décomposition d'une séquence en fonction de la position t, on supposera que :

N V Det N N V V Det N Jeff mange la pomme Jeff mange mange la pomme (a) (b) (c) t t t
P (y|x) = t P (y t |x t )
On posant x u (t) = (x 0 , . . . , x t ) et x d (t) = (x t , . . . , x T ), de même pour y u (t) et y d (t), on obtient :

P (y|x) = P (y u (t)|x u (t)). P (y t |x t ) (P (y t |x t )) 2 .P (y d (t)|x d (t))
En décomposant, l'équation 1 on obtient :

k(x, x ′ , τ, t, y τ , y ′ t ) = k u (x, x ′ , τ, t).k p (x, x ′ , τ, t, y τ , y ′ t ).k d (x, x ′ , τ, t)
avec :

k u (x, x ′ , τ, t) = yu(τ ) y ′ u (t) P (y u (τ )|x u (τ ))P (y ′ u (t)|x ′ u (t)). Φ(x u (τ ), y u (τ ); τ ), Φ(x ′ u (t), y ′ u (t); t) k d (x, x ′ , τ, t) = y d (τ ) y ′ d (t) P (y d (τ )|x d (τ ))P (y ′ d (t)|x ′ d (t)). Φ(x d (τ ), y d (τ ); τ ), Φ(x ′ d (t), y ′ d (t); t) k p (x, x ′ , τ, t, y τ , y ′ t ) = P (y τ |x τ )P (y ′ t |x ′ t ). Φ(x τ , y τ ; τ ), Φ(x ′ t , y ′ t ; t) ( zτ z ′ t P (z τ |x τ )P (z ′ t |x ′ t ). Φ(x τ , z τ ; τ ), Φ(x ′ t , z ′ t ; t) ) 2 (2)
La complexité pour l'évaluation de ces noyaux peut être ramenée à O(T.T ′ ) avec T et T ′ la taille des séquences en utilisant la programmation dynamique. On obtient alors les noyaux suivants :

k u (x, x ′ , τ, t) = 0 si τ = 0 ou t = 0 c 2 k(x τ , x ′ t )(k u (x, x ′ , τ -1, t -1) + 1) k d (x, x ′ , τ, t) = 0 si τ > dim(x) ou t > dim(x ′ ) c 2 k(x τ , x ′ t )(k d (x, x ′ , τ + 1, t + 1) + 1) k(x τ , x ′ t ) = 0 si x τ = x ′ t y P (y|x τ )P (y|x ′ t ) k p (x, x ′ , τ, t, y τ , y ′ t ) = 0 si (x τ , y τ ) = (x ′ t , y ′ t ) c 2 P (yτ |xτ )P (y ′ t |x ′ t ) (c 2 k(xτ ,x ′ t ) 2
La constante c est utilisée pour pondérer les termes φ f selon la taille de f . Il est aussi possible de permettre des discontinuités dans les sous-séquences comme dans le cas du noyau String Subsequence. Il suffit alors, juste, de modifier k u et k d (voir [START_REF] Kashima | Kernel-based discriminative learning algorithms for labeling sequences, trees, and graphs[END_REF] pour plus de détails).

Ce noyau, combiné au noyau polynomial de degré deux, a été utilisé avec un perceptron pour résoudre un problème de reconnaissance d'entités nommées et un problème d'extraction d'information. La loi uniforme est utilisé pour modéliser P (y t |x t ). Les expériences ont été menées en utilisant la validation croisée à 3 blocs. En outre, pour chaque expérience le noyau marginalisé est comparé à un perceptron utilisant le modèle de markov caché [START_REF] Collins | Discriminative training methods for hidden markov models : Theory and experiments with perceptron algorithms[END_REF]. L'idée de base de cet algorithme est d'utiliser l'algorithme de Viterbi sur un modèle de markov caché afin d'attribuer la meilleure séquence d'étiquettes à une séquence de terme. Le perceptron est utilisé pour calculer un score à une séquence étiquetée. Ce score sera utilisé par l'algorithme de Viterbi pour trouver la séquence d'étiquettes optimale.

Pour la reconnaissance d'entités nommées, les données utilisées sont un sous-ensemble d'un corpus espagnol fourni par CoNLL2002. Ce corpus est composé de 300 phrases comprenant au total 8541 termes. L'objectif est d'attribuer à chaque terme un des neuf labels désignant le type d'entité nommée (un des neufs labels correspond au type "non-entité nommée). Les résultats montrent que le noyau marginalisé à un taux de reconnaissance, tant au niveau de la précision que du rappel, supérieur à celui du modèle de markov caché.

La deuxième expérience consistait à extraire des informations concernant l'utilisation de produits. A partir d'une base de 184 phrases (soit 3570 termes) en japonais, l'objectif est de reconnaître le nom du produit, le vendeur, le nombre de produit acheté, les raisons de l'achat etc. Ainsi, il s'agit d'attribuer à chaque terme une des 12 étiquettes correspondants aux informations citées. Les termes ont été annotés en effectuant une analyse lexicale. En outre, un noyau marginalisé sur les arbres (voir la section sur les arbres)a été utilisé. Pour ce noyau, les données ont été structurées en arbre lexical de dépendance représentant la structure linguistique de la phrase en terme de dépendance entre les mots. Les expériences montrent que les noyaux marginalisés sont plus performants que le perceptron utilisant le modèle de markov caché. De plus, le noyau marginalisé sur les arbres obtient de meilleurs résultats que le noyau sur les séquences. Ce résultat peut être expliqué par le fait que le noyau sur les arbres tire avantage de l'information structurelle contrairement au noyau sur les séquences.

Les noyaux pour les arbres

Les arbres sont des structures de données permettant de représenter efficacement des données organisées de manière hiérarchique. Ainsi, ils sont communément utilisés dans de nombreux domaines. La majorité des documents structurés et semi-structurés, tels que les documents XML, sont représentés de manière arborescente. Ainsi, il peut être intéressant de tenir compte de cette structure dans l'évaluation des critères de similarités entre ces différents documents.

le noyau Tree kernel

Le noyau Tree Kernel (appelé aussi parse tree kernel) [START_REF] Collins | Convolution kernels for natural language[END_REF] a été défini pour le calcul de similarité entre les arbres grammaticaux (ou arbres syntaxiques). Un arbre syntaxique est obtenu à partir d'une phrase en la décomposant en groupe grammatical. La figure 2 montre l'arbre syntaxique associé à la phrase "Jeff mange la pomme". La notion de sous-arbre co-enraciné permet de garantir la consistance des règles grammaticales. Par exemple, pour l'arbre T de la figure 2, il existe des arbres co-enracinés de T qui produisent : "N V la N", "Jeff mange GN", "GN V GN", ... Toutefois, il n'existe pas d'arbres co-enracinés de T produisant "Jeff mange Det", "GN mange N", ... Soit Γ l'ensemble de tous les arbres propres possibles, un arbre T peut être plongé, par une fonction Φ r , dans un espace vectoriel de caractéristique (feature-space). Le u ème composant de Φ r , associé à S u ∈ Γ, donne le nombre de noeud n de T tel que S u est un sous-arbre co-enraciné de τ T (n) (Rf req T (S u )), soit :

Φ r Su (T ) = Rf req T (S u ) = n∈T I Su (τ T (n)) (3)
Avec I Su (τ T (n)) = 1 si l'arbre S u est un sous-arbre co-enraciné de τ T (n) et 0 sinon. Le noyau permettant de calculer la similarité entre deux arbres T 1 et T 2 est :

k tree (T 1 , T 2 ) = Φ r (T 1 ), Φ r (T 2 ) = Su∈Γ Φ r Su (T 1 ).Φ r Su (T 2 ) = Su∈Γ ( n 1 ∈T 1 I Su (τ T 1 (n 1 ))).( n 2 ∈T 2 I Su (τ T 2 (n 2 ))) = n 1 ∈T 1 n 2 ∈T 2 Su∈Γ I Su (τ T 1 (n 1 ))).I Su (τ T 2 (n 2 ))) = n 1 ∈T 1 n 2 ∈T 2 k r tree (τ T 1 (n 1 ), τ T 2 (n 2 )) (4)
k r tree (T 1 , T 2 ) indique le nombre de sous-arbres co-enracinés qu'ont en commun les arbres T 1 et T 2 . Cette fonction retourne 0 si 1) les racines sont différentes, ou 2) si le nombre de fils de T 1 et de T 2 ne correspondent pas ou 3) si ∃i, f ils i (T 1 ) = f ils i (T 2 ). Dans les autres cas, on peut définir k r tree (T 1 , T 2 ) par récurrence. En effet, cette fonction sera égale au produit des nombres de sous-arbres co-enracinés communs à chacun des fils de T 1 et de T 2 . Il est à noter que si k r tree (T 1 , T 2 ) = 0 mais que k r tree (τ T 1 (f ils i (rac(T 1 )), f ils i (rac(T 2 ))) = 0, il existe un unique sousarbre co-enraciné commun à T 1 et T 2 pour la partie du sous-arbre induit par f ils i . On peut ainsi définir k r tree (T 1 , T 2 ) dans le cas non nul :

k r tree (T 1 , T 2 ) = i (k r tree (τ T 1 (f ils i (rac(T 1 ))), τ T 2 (f ils i (rac(T 2 )))) + 1) La complexité temporelle du noyau k tree (T 1 , T 2 ) est O(|T 1 ||T 2 |) [1]
avec |T | le nombre de noeuds dans T . Collins et al. ont utilisé ce noyau pour associer à une phrase l'arbre syntaxique le plus plausible (parsing) [START_REF] Collins | Convolution kernels for natural language[END_REF]. La décomposition d'une phrase en arbre syntaxique est un problème difficile. En effet, l'ambiguïté sous-jacente au langage naturel entraîne plusieurs décompositions possibles pour une même phrase. L'objectif proposé par Collins et al. est de sélectionner l'arbre le plus probable par une approche discriminante. Soit F une fonction permettant de générer un ensemble d'arbres syntaxiques pour une phrase, les données sont représentés par un doublet (s, F (s)). Pour l'ensemble d'apprentissage, l'arbre syntaxique correct pour chaque s est connu dans F (s). Un séparateur est alors "appris" en utilisant un perceptron. Pour une phrase s, on lui associe l'arbre T s i de F (s) tel que :

T s i = argmax T ∈F (s) (w * .Φ r (T ))
Avec w * le vecteur optimal associé à :

w = s,j>1 α s,j (Φ r (T s i ) -Φ r (T s j ))
Avec s i une phrase d'apprentissage, s 1 ∈ F (s) l'arbre syntaxique correct de s et s j ∈ F (s). Les expériences sur le corpus Penn treebank ATIS, qui est un corpus anglais annoté sous forme arborescente, ont montré que l'utilisation de cette méthode améliore de prés de 4% les résultats obtenus par une méthode conventionnelle stochastique (Probabilistic Context Free Grammar).

le noyau Tree kernel généralisé

Le noyau Tree Kernel a été essentiellement développé pour traiter des arbres spécifiques telles que les arbres syntaxiques. Le Tree Kernel se base donc sur les propriétés :

1. les descendants d'un noeud n'ont jamais les mêmes étiquettes que les noeuds ancêtres 2. le noyau utilise la définition de sous-arbre co-enraciné pour calculer la similitude entre deux arbres.

Une généralisation de ce noyau a été proposée dans [START_REF] Kashima | Kernels for semi-structured data[END_REF] pour traiter des arbres complexes tels que les arbres XML et HTML. Toutefois, on impose que l'arbre soit étiqueté et ordonné (tel que c'était le cas pour les arbres syntaxiques). Le cadre général du noyau Tree Kernel reste valide. En effet, pour généraliser le noyau, il suffit de modifier la fonction I S (T ) et de changer le noyau spécifique k r tree (T 1 , T 2 ). Dans le cas d'un arbre quelconque étiqueté et ordonné T , I S (T ) retournera la fréquence d'occurrence du sous-arbre S dans T . Definition 4 (Sous-arbre) Un arbre S (possédant au moins un noeud) est un sous-arbre de T si et seulement si il existe un noeud n de T tel que l(n) = l(rac(S)) (l(n) correspondant à l'étiquette du noeud n) et une liste ordonnée d'indexes {j 1 , . . . , j k } tel que ∀i, l(f ils i (rac(S))) = l(f ils j i (τ T (n))) avec i < j i et τ S (f ils i (rac(S))) soit, soit une feuille soit un sous-arbre de τ T (f ils j i (τ T (n))) partageant la même racine.

Étant donnée cette définition de sous-arbre, le noyau k r tree (T 1 , T 2 ) peut être défini comme étant la fonction qui retourne le nombre de sous-arbres commun à T 1 et T 2 avec pour racine rac(T 1 ), en tenant compte de la fréquence d'occurrence dans chaque arbre. Autrement dit, il s'agit de la somme, pour chaque sous-arbre possible S de racine rac(T 1 ), des produits des nombres d'occurrences de S dans T 1 et dans T 2 . Les arbres étant ordonnés, le noyau sur T 1 et T 2 peut être calculé en introduisant une récurrence sur le nombre de fils de T 1 (nf (rac(T 1 ))) et le nombre de fils de T 2 . Ainsi, la fonction S T 1 ,T 2 (i, j) est introduite pour calculer k r tree (T 1i , T 2j ) tel que T 1i est le sous-arbre de T 1 obtenu en supprimant tous les fils d'index supérieurs à i, ainsi que leurs descendants, de même pour T 2j .

k r tree (T 1 , T 2 ) = 0 si l(rac(T 1 )) = l(rac(T 2 )) S T 1 ,T 2 (nf (rac(T 1 )), nf (rac(T 2 ))) (5)
avec

S T 1 ,T 2 (0, 0) = S T 1 ,T 2 (i, 0) = S T 1 ,T 2 (0, j) = 1 S T 1 ,T 2 (i, j) = S T 1 ,T 2 (i -1, j) + S T 1 ,T 2 (i, j -1) (6)
-S T 1 ,T 2 (i -1, j -1) + S T 1 ,T 2 (i -1, j -1).k r tree (τ T 1 (f ils i (rac(T 1 ))), τ t 2 (f ils j (rac(T 2 ))
)) Le noyau peut être généralisé en introduisant deux concepts : la similarité entre les étiquettes et les sous-arbres non-contigus [START_REF] Kashima | Kernels for semi-structured data[END_REF]. Soit Σ l'ensemble de toutes les étiquettes et f : Σ × Σ → [0, 1] indiquant un score de "mutation" entre deux étiquettes tel que f (e, a) indique la probabilité d'acceptation de la mutation de l'étiquette a vers e, la fonction de similarité entre deux étiquettes de deux noeuds n 1 et n 2 est :

Sim(l(n 1 ), l(n 2 )) = a∈Σ f (l(n 1 ), a).f (l(n 2 ), a)
En introduisant la fonction de similarité dans l'équation 5, on obtient :

k r tree (T 1 , T 2 ) = Sim(l(n 1 ), l(n 2 )).S T 1 ,T 2 (nf (rac(T 1 )), nf (rac(T 2 ))) (7)
Le deuxième cadre de généralisation est l'intégration, au niveau du noyau, de la notion d'élasticité des sous-arbres. Ainsi, la définition de sous-arbre se voit élargie en permettant la non contiguïté au niveau des noeuds d'un chemin. En effet, il n'est plus nécessaire qu'un chemin d'un sous-arbre apparaisse de manière contiguë dans un arbre. Cependant, la contrainte d'arbre ordonné reste valable.

Definition 5 (Sous-arbre non contigu) Un arbre S (possédant au moins un noeud) est un sous-arbre de T si et seulement si il existe un noeud n de T tel que l(n) = l(rac(S)) (l(n) et une liste ordonnée d'indexes {j 1 , . . . , j k } tel que ∀i, τ S (f ils i (rac(S))) soit un sous arbre de τ T (f ils j i (τ T (n))).

Afin de prendre en compte la définition de sous-arbre non-contigu, il est nécessaire de généraliser la formule de k r tree (T 1 , T 2 ) (équations 5 et 7). En effet, cette formule retourne une valeur nulle (ou faible selon la similarité) si les étiquettes des racines sont différentes. En d'autre terme, tout sous-arbre commun à T 1 et T 2 doit être enraciné aux noeuds racines de T 1 et T 2 impliquant ainsi que les arbres possèdent la même racine. Or, dans le cas des sous-arbres non-contigus, un sous-arbre commun à T 1 et T 2 peut être construit par combinaison (ordonnée) à partir de sous-arbres enracinés à n'importe quelles noeuds descendants de T 1 et T 2 .

Soit k r old le noyau définit par l'équation 5, le noyau spécifique pour les arbres élastiques utilisés par le noyau Tree Kernel (équation 4) est :

k r tree (T 1 , T 2 ) = n 1 ∈T 1 n 2 ∈T 2 k r old (τ T 1 (n 1 ), τ T 2 (n 2 ))
Cette formule peut être calculée efficacement de manière récursive :

k r tree (T 1 , T 2 ) = k r old (T 1 , T 2 ) + n i =f ils i (T 1 ) k r tree (τ T 1 (n i ), T 2 ) + n j =f ils j (T 2 ) k r tree (T 1 , τ T 2 (n j )) - n i =f ils i (T 1 ) n j =f ils j (T 2 ) k r tree (τ T 1 (n i ), τ T 2 (n j ))
De même que dans le cas du noyau parse tree kernel vu dans la section précédente, la complexité du noyau tree kernel est O(|T 1 |.|T 2 |) dans les différents cas de généralisation.

Kashima et al [START_REF] Kashima | Kernels for semi-structured data[END_REF] ont utilisé les noyaux généralisés élastiques et non élastiques, sans tenir compte des mutations d'étiquettes, pour la classification et l'extraction d'information à partir de documents HTML. Les performances ont été évaluées en utilisant la méthode de validation croisée leave-one-out. L'apprentissage a été effectué en utilisant l'algorithme du perceptron "kernelisé".

Pour la classification de documents, une base de données comprenant 30 documents HTML en japonais et 30 documents HTML en anglais a été construite en extrayant les documents aléatoirement sur le site, américain resp. japonais, d'IBM. La classification devant être structurelle, seules les balises HTML ont été préservées, éliminant ainsi les attributs et les données. De plus, les noyaux sur arbres ont été combinés avec le noyau polynomial. Les résultats ont montrés que le noyau non élastique était de 12% plus performant que le noyau élastique en atteignant prés de 80% de bon classement. Ces résultats ont été obtenus avec un noyau polynomial d'ordre 4 (resp. 3).

L'extraction d'information consiste à apprendre et à reconnaître une information précise dans des documents HTML. Il s'agit ici du marquage des noeuds pertinents. Le problème du marquage consiste à apprendre à partir d'arbres correctement marqués puis à marquer les noeuds pertinents des arbres non traités. Ce problème peut être ramené à un problème de classification en effectuant une transformation du marquage. En effet, pour un noeud marqué, on insère entre le noeud concerné et le noeud père, un noeud portant une étiquette appropriée pour signaler le marquage. Puis, un ensemble d'arbres négatifs est générés à partir des arbres corrects en retirant le marquage et en les plaçant sur des noeuds non initialement marqués. Un apprentissage peut ensuite être effectué sur ces données. Pour le marquage sur un arbre, on effectue pour chacun de ses noeuds un marquage puis on le classe. Pour l'expérimentation, une base a été créée à partir de 54 pages HTML extraites d'un catalogue de vente d'ordinateurs portables d'IBM Japon. L'objectif de l'expérience était de retrouver l'image de l'ordinateur à vendre. Pour cela, les noeuds contenants les images pertinentes ont été marqués et les données textuelles présentes dans les pages ont été éliminées. Les résultats ont montré que le noyau élastique a permis d'extraire l'information avec une précision de 99.3% et un rappel de 68.6% contre une précision de 11.9% et un rappel de 79.6% pour le noyau non élastique. Ces résultats ont été obtenus sans la combinaison avec le noyau polynomial. En effet, ce dernier n'a pas permis d'améliorer les résultats.

le noyau Tree kernel marginalisé

Le noyau marginalisé pour les arbres a été introduit par Kashima et al. [START_REF] Kashima | Kernel-based discriminative learning algorithms for labeling sequences, trees, and graphs[END_REF] pour répondre aux problèmes d'étiquetages (voir la section sur le noyau marginalisé sur les séquences). L'objectif de ce noyau est de permettre de calculer la similarité entre deux arbres étiquetés. Un arbre étiqueté étant simplement un arbre où chaque noeud représente un élément observable (un terme) et à chaque noeud est associé une étiquette. L'avantage de résoudre un problème d'étiquetage en utilisant un modèle de donnée arborescent, plutôt que séquentiel, est qu'il est possible d'exploiter l'information structurelle pour améliorer la discrimination.

Le noyau marginalisé sur les arbres est obtenu en intégrant le noyau Tree kernel généralisé dans le cadre théorique du noyau marginalisé définit par la série d'équation 2. Ainsi, k d (T 1 , T 2 , τ, t) est le noyau ne prenant en compte que les sous-arbres ayant la même racine rac(T 1τ ) (T 1τ indique ici le sous-arbre de T 1 induit par le noeud d'index τ ). De même, k u (T 1 , T 2 , τ, t) ne prend en compte que les sous-arbres ayant une feuille correspondant au noeud d'index τ de T 1 (rac(T 1τ )).

Pour le calcul de k d , on se base sur les équations 5 et 6. L'équation 6 calcul la somme des contributions des sous-arbres communs à T 1 et T 2 en explorant à chaque niveau les fils de droite à gauche. En modifiant cette équation on obtient :

S F (T 1 , T 2 , τ, t, 0, 0) = S F (T 1 , T 2 , τ, t, i, 0) = S F (T 1 , T 2 , τ, t, 0, j) = 1 S F (T 1 , T 2 , τ, t, i, j) = S F (T 1 , T 2 , τ, t, i -1, j) + S F (T 1 , T 2 , τ, t, i, j -1) -S F (T 1 , T 2 , τ, t, i -1, j -1) + S F (T 1 , T 2 , τ, t, i -1, j -1).k d (T 1 , T 2 , ch(T 1 , τ, i), ch(T 2 , t, j))
Avec ch(T 1 , τ, i) l'index, dans T 1 , du i ième fils de la racine de T 1τ .

Le noyau k d devient alors :

k d (T 1 , T 2 , τ, t) = c 2 k(T 1τ , T 2t ).(1 + S F (T 1 , T 2 , τ, t, nf (rac(T 1τ )), nf (rac(T 2t ))))
Pour k u , le calcul s'effectue de la feuille vers la racine. Ainsi, on utiliser la fonction pa(T 1 , τ ) qui retournera l'index du père du τ ième noeud dans T 1 . En outre, il faut aussi tenir compte des frères gauches et des frères droits du τ ième noeud de T 1 . Pour la contribution des frères gauches, la fonction S F pourra être utilisée. Quant aux frères droits, il faudra les explorer de la gauche vers la droite. On utilisera la fonction n = chID(T 1 , τ ) pour indiquer que le noeud d'index τ est le n ième fils de son père. On définit, donc, une fonction symétrique à S F :

S B (T 1 , T 2 , τ, t, i, j) = 1 si i ≥ nf (rac(T 1τ )) ou si j ≥ nf (rac(T 2t )) S B (T 1 , T 2 , τ, t, i, j) = S B (T 1 , T 2 , τ, t, i + 1, j) + S B (T 1 , T 2 , τ, t, i, j + 1)
-S B (T 1 , T 2 , τ, t, i + 1, j + 1)

+ S B (T 1 , T 2 , τ, t, i + 1, j + 1).k d (T 1 , T 2 , ch(T 1 , τ, i), ch(T 2 , t, j))
L'expression de k u est :

k u (T 1 , T 2 , τ, t) = c 2 k(T 1τ , T 2t ).(1 + k u (T 1 , T 2 , τ, t)) . S F (pa(T 1 , τ ), pa(T 2 , t), τ, t, chID(T 1 , τ ) -1, chID(T 2 , t) -1)
. S B (pa(T 1 , τ ), pa(T 2 , t), τ, t, chID(T 1 , τ ) + 1, chID(T 2 , t) + 1)

Les expériences menées sur ce noyau sont décrites dans la section sur le noyau marginalisé pour les séquences.

Les noyaux pour les graphes

Le graphe est une structure de donnée très utilisée dans le domaine informatique pour modéliser des informations structurées complexes. En effet, les séquences et les arbres vus précédemment sont, en réalité, des graphes acycliques orientés. De plus, dans le cas de la séquence, le graphe est de degré maximum 1. Nous définirons un graphe étiqueté G par le triplé (V, E, σ) où V est l'ensemble des noeuds de G, σ l'ensemble des étiquettes tel que sigma i représente l'étiquette du noeud i (il est aussi possible d'étiqueter les arcs : on notera sigma (i,j) l'étiquette de l'arc reliant le noeud i à j) et E, une matrice d'adjacence tel que E ij = 1 si et seulement si il existe un arc reliant le noeud i au noeud j (afin de simplifier l'écriture on utilisera la même notation i, j pour désigner les indexes dans E que pour designer les noeuds de V ). L'une des propriétés de la matrice d'adjacence est que [E n ] ij indique le nombre de chemin de longueur n reliant le noeud i au noeud j.

La conception d'un noyau nécessite une définition de la similarité entre deux graphes. Pour cela, il existait deux approches standards [START_REF] Gärtner | A survey of kernels for structured data[END_REF][START_REF] Gärtner | A short tour of kernel methods for graphs[END_REF]. La première consiste à déterminer si les deux graphes sont isomorphes (ils ne se distinguent que par l'ordre des noeuds) ou à déterminer le nombre de sous-graphes isomorphes communs. Cependant, il est connu que ce problème est fortement combinatoire. La deuxième approche consiste à projeter le graphe G dans un espace vectoriel où chaque dimension est indexée par un graphe H tel que la valeur de la projection de G sur cet axe représente la fréquence d'occurrence de H, en tant que sous-graphe, dans G. Il est alors possible de concevoir un noyau qui identifie certaines propriétés dans les sous-graphes H. En particulier, il est possible de concevoir un noyau qui effectue le produit scalaire dans l'espace vectoriel en se limitant aux sous-graphes qui sont des chemins hamiltoniens (H est un chemin hamiltonien de G si et seulement si H est un sous-graphe de G et si H est de même ordre que G i.e. H contient tous les noeuds de G exactement une fois). De même que pour la première approche, le problème du chemin hamiltonien est NP-difficile. Afin de réduire la complexité dans l'évaluation de la similarité d'autres approches ont été explorées. L'approche la plus répandue consiste à calculer la similarité en se basant sur les chemins parcourus [START_REF] Gärtner | Graph kernels and gaussian processes for relational reinforcement learning[END_REF][START_REF] Gärtner | A short tour of kernel methods for graphs[END_REF][START_REF] Kashima | Kernels for graph classification[END_REF][START_REF] Kashima | Marginalized kernels between labeled graphs[END_REF]. L'un des problèmes principaux de cette approche est qu'il existe une infinité de chemins possibles dès lors qu'il existe dans le graphe un cycle. On a alors le noyau :

k(G, G ′ ) = lim n→∞ n i=1 p∈P i (G) p ′ ∈P i (G ′ ) λ i .k p (p, p ′ ) (8)
Avec P l (G) l'ensemble des chemins de G de longueur l, lambda l un réel pondérant les chemins de longueur l (on fixera λ l = λ l ) et k p un noyau définit sur les chemins. Il existe plusieurs façons de définir k p selon qu'on veuille tenir compte des étiquettes sur les noeuds, sur les arcs ou encore permettre des discontinuités (gap).

Dans [START_REF] Gärtner | Graph kernels and gaussian processes for relational reinforcement learning[END_REF][START_REF] Gärtner | A short tour of kernel methods for graphs[END_REF], k p est définit sur des chemins contiguës en tenant compte des étiquettes sur les noeuds et sur les arcs. Ainsi, le noyau sur les arcs revient à énumérer le nombre de chemins communs aux deux graphes. De plus, l'équation 8 est réécrite plus élégamment en utilisant la propriété de la matrice d'adjacence. Pour cela, un nouveau graphe G × : (V × , E × , σ × ) est introduit en effectuant le produit direct des graphes G : (V, E, σ) et G ′ : (V ′ , E ′ , σ ′ ) :

V × = {(v, v ′ ) ∈ V × V ′ |σ v = σ v ′ } σ × k=(v,v ′ ) = σ v Pour (i, j) correspondant à ((u, u ′ ), (v, v ′ )) ∈ V 2 × [E × ] i,j = 1 si [E] u,v = [E ′ ] u,v ′ = 1 et σ (u,v) = σ ′ (u ′ ,v ′ ) 0 sinon σ × (i,j) = sigma (u,v) L'équation 8 devient : k(G, G ′ ) = lim n→∞ n i=1 |V × | u,v λ i .[E i × ] u,v
L'expression E i × peut être simplifiée si la matrice E × est diagonalisable. Dans le cadre d'un graphe non-orienté, la matrice E × étant une matrice réelle et symétrique, elle peut être diagonalisée. Ainsi, si E × peut être exprimé sous la forme T -1 .D.T alors E× i = T -1 .D i .T . On peut alors réécrire le noyau sous la forme :

k(G, G ′ ) = |V × | u,v (T -1 .( lim n→∞ n i=1 λ i .D i ).T ) u,v
Pour calculer la limite [START_REF] Gärtner | Graph kernels and gaussian processes for relational reinforcement learning[END_REF], propose d'utiliser une décomposition en série exponentielle ou en série géométrique. La décomposition en série exponentielle se base sur le principe que :

e β.E = lim n→∞ n i=0 (βE) i i! Ainsi, en fixant λ i = β i i! , on obtient : k(G, G ′ ) = |V × | u,v (T -1 .e β.D .T ) u,v
De même, la décomposition en série géométrique se base sur, pour γ < 1 :

lim n→∞ n i=0 γ i = 1 1 -γ En fixant γ = λ.D et en veillant à ce que λ.D < I, on a : k(G, G ′ ) = |V × | u,v (T -1 .(I -λ.D) -1 .T ) u,v
Dans [START_REF] Kashima | Kernels for graph classification[END_REF], Kashima et al. ont décomposé la similarité de deux graphes par une somme de similarité entre noeuds :

k(G, G ′ ) = 1 |V |.|V ′ | v i ∈V,v j ∈V ′ k n (v i , v j ) Avec V et V ′ l'ensemble de noeuds de G et respectivement de G ′ .
La similarité de deux noeuds sera d'autant plus importante qu'il existera des chemins longs communs aux deux graphes issus de ces noeuds. Pour assurer la terminaison du calcul, une probabilité 1λ est fixée pour terminer le chemin et une probabilité λ pour continuer vers un successeur du noeud courant. Ainsi, plus le chemin sera long et plus la probabilité de terminer le chemin deviendra importante. On obtient, ainsi, le noyau suivant :

k n (u, u ′ ) = I(u, u ′ ).((1 -λ) + λ. (v,v ′ )∈A G (u)×A G ′ (u ′ ) I A ((u, v), (u ′ , v ′ )) |A G (u)|.|A G ′ (u ′ )| .k n (v, v ′ ))
Avec A G (u) = {v ∈ V |E uv = 1}, I(u, u ′ ) = 1 si les étiquettes des noeuds u de G et u ′ de G ′ sont identiques ou 0 sinon et de même pour I A ((u, v), (u ′ , v ′ )) qui retourne 1 si l'étiquette de l'arc reliant u et v de G est identique à l'étiquette de l'arc reliant u ′ et v ′ de G ′ .

Dans [START_REF] Kashima | Marginalized kernels between labeled graphs[END_REF], un noyau marginalisé sur tous les chemins possible est proposé en ne considérant que des graphes orientés. Ainsi, le noyau est défini par :

k(G, G ′ ) = lim L→∞ L l=1 h h ′ k z (G, G ′ ,
h, h ′ ).P (h|G).P (h ′ |G ′ ) La probabilité a posteriori d'avoir un chemin h de G de longueur l (P (h|G)) est défini en fonction de la probabilité de débuter un chemin par un noeud h 1 (P s (h 1 )), la probabilité de terminer ce chemin par un noeud h l (P q(h l )) et les probabilités d'effectuer une transition d'un noeud h i vers un noeud h i+1 (P t (h i+1 |h i )). D'où : P (h|G) = P s (h 1 ). l=|h| i=2 P t (h i |h i-1 ).P q (h l ) Le noyau k z effectue la comparaison des deux chemins h et h ′ des graphes respectifs G et G ′ . Pour cela, le noyau calcule le produit des similarités entre les étiquettes des noeuds et des arcs du chemins :

k z (G, G ′ , h, h ′ ) = 0 si |h| = |h ′ | k e (σ h 1 , σ ′ h ′ 1 ) l i=2 k e (σ (h i-1 ,h i ) , σ ′ (h ′ i-1 ,h ′ i ).k e (σ h l , σ ′ h ′ l )
On rappelle que σ h i indique l'étiquette du noeud h i de G et que σ (h i ,h i+1 ) indique l'étiquette de l'arc reliant le noeud h i à h i+1 . Étant données deux étiquettes e et e ′ , on peut définir k e comme étant un noyau retournant 1 si e = e ′ ou 0 sinon. Toutefois, on peut définir un noyau un peu complexe si les étiquettes sont des réelles avec une certaine métrique. On pourrait alors définir un noyau gaussien qui tolérerait certaines différences entre les étiquettes.

Outre les graphes que nous venons de voir, Suzuki et al. ont introduit dans [START_REF] Suzuki | Hierarchical directed acyclic graph kernel : methods for structured natural language data[END_REF][START_REF] Suzuki | Kernels for structured natural language data[END_REF] la notion de graphe acyclique orienté hiérarchique (HDAG). Les HDAG sont des graphes dont certains noeuds contiennent des graphes acycliques orientés. Cette structure a été proposée pour permettre la représentation de documents textuels ainsi que d'informations connexes. En effet, un document textuel peut subir de multiple pré-traitement et des informations grammaticales et sémantiques peuvent lui être ajoutées. Ces informations combinées entre elles forment des structures hiérarchiques complexes. En outre, un noyau a été proposé pour calculer la similarité entre les HDAG. Ce noyau a été évalué sur un problème de classification multi-classe avec l'algorithme SVM et la méthode "un contre tous" (un classifieur SVM par classe). Une base de données de 3000 questions divisées en 148 classes a été utilisée pour l'expérimentation. Les questions ont été pré-traitées à l'aide d'un parser. En outre, les entités nommées ont été étiquetées et les informations sémantiques ajoutés. Les résultats ont montrés que le noyau HDAG était plus performant que le noyau SubString Kernel et le noyau "sac de mots".

Fig. 1 :

 1 Fig. 1: (a) Exemple de couple de séquences (x, y). (b) sous-séquences de (a) où les x i avec i > t ont été éliminés. (c) sous-séquences de (a) obtenu en éliminant les x i de (a) pour i < t.

Fig. 2 :

 2 Fig. 2: Arbre syntaxique pour la phrase "Jeff mange la pomme"

  afin d'étiqueter des structures complexes tels que les séquences, les arbres et les graphes. Le problème de l'étiquetage consiste à affecter à une donnée x = (x 1 , . . . , x T ) un groupe d'étiquettes y = (y 1 , . . . , y T ) ∈ Σ T y . Par exemple, en langage naturel x peut représenter une phrase, et le problème consiste à attribuer à chaque mot de x une étiquette désignant son groupe grammatical (Part Of Speech tagging).La figure 1(a) montre un exemple de couple (x, y) où les noeuds noirs représentent les éléments x i et les noeuds blancs les étiquettes y i associées à x i . Pour résoudre le problème de l'étiquetage, l'approche standard consiste à attribuer à x la séquence d'étiquettes y tel que : y=argmax y i logP (y i |x i ). Il s'agit ici de maximiser la probabilité que la séquence entière soit correcte. Une autre approche consiste à maximiser individuellement la probabilité qu'une étiquette y i corresponde à l'élément x i . Soit :

Conclusion

Nous avons présenté une collection de méthodes assez variées, adaptées aux différents cas rencontrés lors du traitement des données structurées. La diversité de ces méthodes rend pour l'instant délicate toute évaluation comparative de leurs performances respectives. Le caractère très récent de ces travaux fait qu'il n'existe pas pour l'instant d'étude expérimentale comparative sérieuse des comportements de ces différents algorithmes sur des données issues du monde réel et plus particulièrement du langage naturel. Insistons sur le fait que la souplesse des méthodes à noyaux facilite la construction de méthodes ad-hoc adaptées à la structure du problème à traiter.