Arkadiusz Jarota

Marc Tondusson

Geoffrey Galle

Eric Freysz

Halina Abramczyk

Ultrafast Dynamics of Metal Complexes of Tetrasulphonated Phthalocyanines

A promising material in medicine, electronics, optoelectronics, electrochemistry, catalysis, and photophysics, tetrasulphonated aluminum phthalocyanine (AlPcS 4 ), is investigated by means of steady state and time resolved pump-probe spectroscopies. Absorption and steady state fluorescence spectroscopy indicate that AlPcS 4 is essentially monomeric. Spectrally resolved pump-probe data are recorded on time scales ranging from femtoseconds to nanoseconds. The nature of these fast processes and pathways of the competing relaxation processes from the initially excited electronic states in aqueous and organic (dimethyl sulfoxide) solutions are discussed. The decays and bleaching recovery have been fitted in the ultrafast window (0-10 ps) and later time window extending to nanoseconds (0-1 ns). While the excited state dynamics have been found to be sensitive to the solvent environment, we were able to show that the fast dynamics is described by three time constants in the ranges of 115-500 fs, 2-25 ps, and 150-5 0 0p s .W ew e r ea b l et oa s c r i b e t h e s et h r e e t i m e c o n s t a n t st od i fferent processes. The shortest time constants have been assigned to vibrational wavepacket dynamics. The few picosecond components have been assigned to vibrational relaxation in the excited electronic states. Finally, the 150-500pscomponentsrepresent thedecay from S 1 to the ground state. The experimental and theoretical treatment proposed in this paper provides a basis for a substantial revision of the commonly accepted interpretation of the Soret transition (B transition) that exists in the literature.

INTRODUCTION

Phthlocyanines and metallophthalocyanines are involved in many biological, chemical, and physical processes. The pos sibility to tailor and modify their properties such as absorption, emission, nonlinear optical responses, polarizability, and dipole moment make them extremely important materials in many disciplines of research like biomedicine, electronics, optoelec tronics, electrochemistry, photophysics, and catalysis. The diversity of their functions is due in part to the variety of metals that bind in the "pocket" of the phthalocyanine ring system. They have been proven to be efficient photosensitizers in a number of chemical and photochemical processes, especially photodynamic therapy (PDT).

PDT of cancer is a promising application, particularly for small and superficial tumors as well as benign skin and mouth disorders. At present, PDT is also being tested in the clinic for use to treat cancers of the brain, head and neck, lung, pancreas, intraperitoneal cavity, skin, prostate, and breast. [1][2][3][4][5][6][7][8] Recently, the targeted PDT technique has been tested on breast cancer cells. [9][10][11] aluminum tetrasulphonated phthalocyanine (AlPcS 4 ) has been used in clinical trials [12][13][14] because its triplet state has the ability to react with molecular oxygen to produce highly reactive singlet oxygen. Despite the medical applications, a growing numbers of phthalocyanines play an important role as low gap semiconducting materials. 15 The processes of energy dissipation in phthalocyanines occurring on the nanosecond time scale, such as internal con version, fluorescence, intersystem crossing, and the triplet forma tion, have been studied in many papers. [16][17][18][19][20][21][22][23][24][25][26][27][28][29][30][31][32][33][34][35] There are many fewer papers reporting on primary events in phthalocyanines occurring on femtosecond and picosecond scales, 23,[36][37][38][39][40][41][42][43] which are particularly important in thin films. The effects of aggre gation on the absorption and emission spectra of metalloph thalocyanines in the liquid solutions are well documented [44][45][46][47][START_REF] Ostler | An Investigation of Intracellular PDT Mechanisms[END_REF][START_REF] Liu | [END_REF][50][51][52][53] but much less information has been accumulated on the solid phases. The films of phthalocyanines become relevant in advanced devices like electrochromic displays, optical limiters, light emitting diodes, recordable digital discs, organic conductors, lasers, nonlinear optical elements, and so forth. In these applications, properties such as conductivity, optical absorbance, and photoconductivity in the solid state phase are important. 15,54 In this paper, AlPcS 4 has been chosen to serve as a model phothosenistizer to study the efficiency of primary processes occurring upon excitation of the chromophore that lead to the triplet generation.

In this paper, we wish to elucidate processes responsible for fast dynamics of AlPcS 4 occurring on the time scale from femtoseconds to nanoseconds monitored by the pump-probe transient absorption spectroscopy when induced by femto second laser pulses centered at 677 and 360 nm, corresponding to the absorption maxima of the Soret band and the Q band, respectively.

EXPERIMENTAL SECTION

Aluminum phthalocyanine chloride tetrasulphonic acid was purchased from Frontier Scientific, Inc. (AlPcS 834). Dimethyl sulfoxide (DMSO) was purchased from Sigma Aldrich (34869). They were used without further purification. Water was deionized before preparing the solutions. Briefly, Scheme 1 illustrates the method used for synthesis of AlPcS 4 via sulphonation of the nonsulphonated phthalocyanine. This method leads to a large number of regioisomers.

Steady-State Emission Measurements. Emission spectra were measured with a Ramanor U1000 (Jobin Yvon) and Spectra Physics 2017 04S argon ion laser operating at 514 nm at a power of 100 mW. The spectral slit width was 6 cm -1 , which corresponds to the 500 μm mechanical slit of the spectrometer; a λ/4 wave plate was used to change the linear polarization into the circular one to avoid the different polar ization sensitivity of the gratings. The interference filter has been used to purify the laser line by removing additional natural emission lines that interfere with the Raman lines, especially in the case of the solid samples.

Steady-State UV-Vis Absorption Measurements. UV-vis absorption electronic spectra were measured with Varian Cary 5E spectrophotometer in 2 and 0.10 ± 0.005 mm detachable quartz cells (Hellma). The spectra were recorded at 293 K for the aqueous solutions and in DMSO at con centrations of c = 10 -5 , 10 -4 , and 10 -3 M.

Pump-Probe Transient Absorption Spectroscopy.

The source of the femtosecond pulses was a mode locked titanium sapphire femtosecond laser (MIRA, Coherent, 800 nm, 76 MHz, 9 nJ, <200 fs) pumped with a diode pumped solid state laser (VERDI V5, Coherent, 532 nm). The fundamental beam was amplified with a Ti:Sapphire regenerative amplifier (Coherent Legend USP, 800 nm, 1 kHz, 3 mJ, 50 fs). The regenerative amplifier was pumped with a diode pumped Nd:YLF laser (JADE, Thales Laser, 527 nm, 1 kHz, 20 mJ, <200 ns). The pulse was split in two and further amplified in a dual single pass amplifier (Coherent Elite Duo, 800 nm, 1 kHz, 2 × 4.5 mJ, 50 fs). This amplifier was pumped by a high power Nd:YLF laser (Evolution, Coherent, 527 nm, 50 mJ, <200 ns). The output of the laser system was split, and two 1 mJ laser pulses were used to pump two optical parametric amplifiers (OPA, model TOPAS from Light Conversion). These OPA combined by frequency conversion modules generate femto second pulses tunable in the 300 and 2600 nm ranges. The energy of the pump pulse was adjusted to 2 μJ in water experiments and 700 nJ or less in experiments with DMSO. The energy of the probe pulse was at least 100 times lower than the energy of the pump pulse. The pump and probe pulses were overlapped on a 1 mm optical path of a cell containing the AlPcS 4 solution. The solution was circulated in the cell by a magnetic stirrer in order to minimize the thermal lensing and photoquenching effects. The time delay t between the pump and probe pulses was adjusted by a motorized translation stage that has a spatial resolution of 1.5 μm. Transient absorption signals was measured with two silicon photodiodes (Thorlabs, TDS 1000) placed before and after the sample, which measure initial (I 0 ) and the transmitted intensity of the probe beam (I t ) respectively. The I 0 was normalized with respect to the intensity of the pump beam, which was measured with the same type of the photodiode. The absorption signal S(t) was calculated as log(I 0 /I t ) The transient absorption signal ΔA(t) was computed by subtracting the absorption signal measured with and with out the pump pulse. For that reason, the pump beam was chopped at 40 Hz. The typical measurement error of ΔA was better than 10 -3 .

Computational Method. Geometry optimizations have been performed using Gaussian 03 software [START_REF] Frisch | Gaussian 03[END_REF] on the DFT level with the B3LYP hybrid functional and 6 31G(d) basis set. Additionally, to get more insight into electronic transitions, we have carried out the TD DFT calculations at the B3LYP 6 31G(d) level.

RESULTS

Steady-State Absorption and Emission Measurements. The steady state absorption spectra of AlPcS 4 in water and DMSO as a function of concentration are shown in Figure 1. The Q band (S 0 (a 2u ) → S 1 (e g ) transition) has a sharp maximum at 678 nm as well as weaker bands to the blue side with maxima at 643 and 607 nm. The shape, the positions of the absorption maxima, and the intensity of the bands at 643, 607, and at 678 nm are normalized to the maximum of the band at 678 nm. One can see that the absorption bands are very similar in the concentration range of 10 -5 -10 -3 M, indicating that AlPcS 4 molecules are dominated by a monomeric form in both solvents.

The fluorescence spectrum presented in Figure 2 (λ exc = 514 nm) shows an almost perfect mirror image of the absorption spectrum in the Q band region, indicating that the bands at 643 and 607 nm should be assigned to the vibrational progression.

Scheme 1. Method Used for Synthesis of AlPcS 4 via Sulphonation of the Non Sulphonated Phthalocyanine

The maximum of emission at 685 nm provides a Stokes shift of 8 nm. However, at higher concentrations, the fluorescence spectrum presented in Figure 3 (λ exc = 514 nm) shows no features of the mirror image of the absorption and the emission spectra in the Q band region, indicating that the contribution from reabsorption and aggregation leads to disturbance of the image typical for the monomeric form.

The absorption at high concentrations becomes solvent dependent. Figure 4 shows the absorption of AlPcS 4 at c = 10 -3 M in DMSO and water. The band in DMSO is red shifted from 678 to 685 nm and is substantially narrowed relative to the absorption bands in water. The red shift in organic solvents has been attributed to a shift from aggregates toward mono mers. [START_REF] Harriman | [END_REF]57 The results from Figure 4 indicate that the AlPcS 4 molecules are more aggregated in water, while in DMSO, they are almost monomeric even at high concentrations.

Figure 5 shows the emission of AlPcS 4 at c = 10 -5 and 10 -3 M in DMSO and water. The emission spectra are much more concentration sensitive, particularly at high concentrations. The distinctions observed in the emission spectra at higher con centrations must be related to different paths of energy dissipation.

Excited-State Dynamics of AlPcS 4 in Aqueous and DMSO Solutions. S 0 (a 1u ) → S 1 (e g ) Transition. To get a deeper insight into the mechanisms of energy dissipation in phthalocyanines, we have monitored the excited state dynamics in aqueous and organic (DMSO) solvents upon excitation at 677 nm, which promotes the S 0 (a 1u ) → S 1 (e g ) transition in the Q band (Scheme 2).

Figure 6 shows the transient absorption signals ΔA(t) of AlPcS 4 in aqueous and organic (DMSO) solvents at a con centration of 10 -3 M as a function of the time delay t in the pump-probe experiments. The molecules were excited at 677 nm and probed at different wavelengths (500, 572, 664, and 690 nm). The right panel shows the results in DMSO, and the left panel shows the results in aqueous solution. The results in Figure 6 are presented in the full time window up to 1 ns.

Comparison between Figure 6a and b demonstrates that in DMSO, the excited state dynamics of AlPcS 4 is drastically different from that in water. Directly upon excitation with the laser pump pulse at 677 nm, a negative signal at 664 nm (Figure 6a) has been recorded in the aqueous solution of AlPcS 4 . The latter phenomenon is assigned to the bleaching of the Q transition. The bleach is instantaneous and is laser pulse width limited. In water, the recovery of the bleach at 664 nm is found to be biexponential and is fitted with time constants of 5.09 ± 0.99 and 203.16 ± 18.75 ps. It is important to notice that the recovery goes above the baseline at around 400 ps and the signal becomes positive. The time constants are of the same order as those obtained by Howe et al. 23 for PcS 4 and ZnPcS 4 in DMSO probed at 720, 790, and 820 nm. Even though we slightly shifted the probe wavelength, one can observe the bleaching in water (Figure 6a) but no evidence of bleaching in DMSO (Figure 6b). In DMSO, we recorded a sudden rise instead.

Figure 6a shows that the instantaneous bleach of AlPcS 4 in water at 664 nm is accompanied by a sudden rise at 500 nm that is followed by decay. This decay is found to be biexponential and is fitted with time constants of 3.23 ± 0.68 and 304 ± 39 ps in water (Figure 6a) and 24 ± 19 and 380 ± 178 ps in DMSO (Figure 6b).

Further ultrafast dynamics can be monitored in other regions of the transient absorption spectrum (572 nm in Figure 6a,b). The sudden rise at 572 nm is followed by a decay that is found to be biexponential and that is fitted with time constants of 3.51 ± 0.50 and 220 ± 25 ps in water and 3.44 and 115 ± 95 ps in Figure 7 presents the results for AlPcS 4 in water (Figure 7a) and in DMSO (Figure 7b) in the early time window extending to 10 ps. The initial decays of the signal at 500 nm are monoexponential and can be fitted with a time constant of 244 ± 98 fs in water and 155 ± 51 fs in DMSO. The decays of the signal at 572 nm are monoexponential and can be fitted with a time constant of 560 ± 94 fs in water and 480 ± 384 fs in DMSO. Savolainen and co workers 39 have studied ZnPc in DMSO (0.12 × 10 -3 M). They obtained three time constants, 250 fs, 2.5 ps, and 2.9 ns. Bearing in mind that the study in ref 39 was on ZnPc, not AlPcS 4 , we nonetheless feel that a com parison is worthwhile. We find no evidence of the slow com ponent (2.9 ns) in our measurements of the transient absorption.

The slowest component of dynamics of the order 150-500 ps observed in our paper at different wavelengths is similar to that reported by Howe et al. 23 On the other side, we find that the fast, femtosecond components obtained in this paper, which were demonstrated by the time constant of 244 (in water) and 155 fs (in DMSO) for the 500 nm and of 560 fs (480 fs) in water (DMSO) for 572 nm probing wavelengths, are similar to the time constants reported by Savolainen et al. 39 S 0 (a 2u ) → S 1 (e g ) Transition. The pumping at 360 nm excites the transition S 0 (a 2u ) → S 1 (e g ) and/or the S n state (Scheme 2). Figure 8 compares the transient absorption signals ΔA(t) recorded at 500 nm when the sample is pumped at 677 and 360 nm. In water, the instantaneous rise at 500 nm, limited by the laser pulse duration, is followed by a biexponential decay with time constants of 3.23 ± 0.68 and 304 ± 39 ps for the pumping at 677 nm and 3.18 ± 0.19 and 299.38 ± 24 ps for the pumping at 360 nm. In DMSO, the relevant time constants are 24 ± 19 and 380 ± 17 ps for pumping at 677 nm and 24.06 ± 9.57 and 220 ± 180 fs for pumping at 360 nm. Thus, both components of the dynamics are similar for both pumping wavelengths in both solvents.

Figure 9 compares the transient absorption signals ΔA(t) of AlPcS 4 at the probe wavelength of 572 nm in water (left panel) and in DMSO (right panel) when the sample is pumped at 360 and 677 nm, respectively. In water, when the sample is pumped at 360 nm, the decay of the positive signal of AlPcS 4 at 572 nm is found to be biexponential and is fitted with time constants of 58 ± 24 and 614 ± 378 ps. However, when the sample is pumped at 677 nm, the decay of the signal is found to be biexponential and fitted with time constants of 3.51 ± 0.50 and 220 ± 25 ps. In DMSO, the decay of positive signals of AlPcS 4 at 572 nm is found to be biexponential and is fitted with time constants of 3.44 ± 1.31 and 115 ± 81 ps and 2.00 ± 0.13 and 360 ± 152 ps when the sample is pumped at 667 and 360 nm, respectively. As the positive signals at 500 and 572 nm in Figures 8 and9 appear instantaneously within the femtosecond time scale, we have assigned them to the excited state absorption (ESA).

Figure 10 compares the transient absorption signals ΔA(t) of the sample pumped at 360 and 677 nm and probed at wavelengths of 614 and 752 nm when AlPcS 4 is dissolved in water and 702 and 752 nm when AlPcS 4 is dissolved in DMSO. In water, directly upon excitation, instantaneous bleach (negative signal) is present at 614 and 752 nm. This instantaneous bleach (laser pulse width limited) is followed by a recovery. The recovery of the bleach at 614 nm, when the sample is pumped at 360 nm, is found to be biexponential and is fitted with time constants of 231 ± 26 fs and 2.75 ± 0.10 ps in the early window up to10 ps. In water, when the sample is probed at 752 nm, the recovery of the bleach is found to be biexponential and is fitted with time constants of 490 ± 70 fs and 3.79 ± 1.25 ps for pumping at 677 nm and 480 ± 60 fs and 2.33 ± 0.81 ps for pumping with 360 nm. In DMSO, the bleaching is observed only for pumping at 360 nm. When the probe is set at 702 nm, the bleaching is fitted by a biexponential function with time constants of 450 ± 302 fs and 2.45 ± 10 ps. Contrary, when the sample is pumped at 677 nm and probed at 702 nm, one records a positive signal. Its rise is found to be fitted by a biexponential function with the time constants of 460 ± 60 fs and 6.12 ± 2.12 ps. For all of the signals presented in Figure 10, it is important to notice that the recovery signals at 614, 702, and 752 nm go above the baseline at around 400 ps, and the signal becomes positive. For the probe wavelength at 752 nm, the difference in the signal in water and that in DMSO presented in Figure 10c and d is most likely due to a coincidental cancellation between the bleach and ESA (S 1 → S n ).

DISCUSSION

In order to elucidate further electronic dynamics features that can be rationalized from the signals of the transient absorption ΔA(t) presented in the previous section, we need to under stand the details of the electronic transitions in phthalocyanines that are induced and probed by the laser pulses in the pumpprobe experiments. Scheme 3 shows the molecular orbitals in selected phthalocyanines according to the calculations from the literature 39,[58][59][60] and Kohn-Sham orbitals from our TD DFT calculations (Scheme 3d).

One can see from the Schemes 2 and 3 that the pump pulse at 677 nm excites the S 0 (a 1u ) → S 1 (e g ) transition. The pump pulse at 360 nm can excite either of the higher excited elec tronic states in the S 0 (a 1u ) → S n (b 1u ) transition and the S 0 (a 2u ) → S 1 (e g ) transition (a maximum at 350 nm for AlPcS 4 in water and 360 nm in DMSO). Thus, probing with various spectral components in the visible range makes possible recording of the transient absorption and allows monitoring pf the repopulation of the excited states.

The previous molecular orbitals picture (Scheme 3a) based on the Schaffer, Gouterman, and Davidson considerations 58,60 suggests that the 360 nm promotes the S 0 (a 2u ) → S 1 (e g ) transi tion (B1) and B2 transitions rather than S 0 (a 1u ) → S n transitions to higher excited states. In contrast, the S 0 (a 1u ) → S n transitions have been suggested recently 39 to be dominant contribution in ZnPc.

Our TD DFT calculations for AlPcS 4 (Table 1 and Figure 3d) show that the oscillator strengths for the S 0 (a 1u ) → S 1 (e g ) (Q transition) are f = 0.3830 (Q y ) and 0.3859 (Q x ). For the S 0 (a 2u ) → S 1 (e g ) transition, the oscillator strength is f = 0.1452. The B band consists of a few transitions from lower lying orbitals of the ground state to S 1 (e g ) with f up to 0.3041 (all transitions are gathered in Table 1). However, the transitions to the second excited state S 0 (a 1u ) → S 2 (b 1u ) and to higher excited states S 0 (a 1u ) → S n have similar oscillator strengths. Thus, the B band originates both from the inner molecular orbitals to the first excited state S 1 (e g ) and from the HOMO orbital S 0 (a 1u ) to the second excited state S 2 (b 1u ) as well as to higher excited states S n . It indicates that the pump pulse at 360 nm excites both the first excited electronic state in the S 0 (a 2u ) → S 1 (e g ) transition and the higher excited states in the S 0 (a 1u ) → S 2 (b 1u ) and the S 0 (a 1u ) → S n transitions. The energy difference between S n and S 2 is only 1033 cm -1 . Although much higher than the thermal energy kT, the energy separation corresponds to the vibrational energy. Thus, the nonradiative energy dissipation may occur via energy relaxation between the vibrational states.

The TD DFT results presented so far determine interpre tation of electronic dynamics obtained from our time resolved experimental data. Indeed, the S 0 (a 2u ) → S 1 (e g ) transition pumped by 360 nm promotes the molecules to the same state as pumping at 677 nm for the S 0 (a 1u ) → S 1 (e g ) transition.

Therefore, both pumping wavelengths should demonstrate similar electronic dynamics of AlPcS 4 . In contrast, the S 0 (a 1u ) → S n transition pumped by 360 nm should result in different dynamics than that observed for the S 0 (a 1u ) → S 1 (e g ) transition pumped by 677 nm.

The picture that emerges from the results presented in the paper is the following. The dynamics of AlPcS 4 reveals four different time scales with the time constants of 115-500 fs, 2-12 ps, and 150-500 ps. The fast femtosecond component has been also reported in the literature. 39,59,61 Savolainen et al. 39 have assigned the shortest time constant to inertial response of solvation. Fournier et al. 61 have assigned a constant of <210 fs observed in NiPc and in CuPc to the lifetime S 2 → S 1 internal conversion. Rao et al. 41 have assigned the time constant < 170 fs Scheme 3. Energy Level Diagrams for Selected Metal Complexes of Phthalocyanines (a) ZnPc, 58,60 (b) Various Complexes of Phthalocyanines, 59 (c) ZnPc, 39 (d) AlPcS 4 from TD DFT Calculations in This Paper to phase relaxation of S n states. Our results demonstrate that the fast femtosecond component is not related to the solvation dynamics as the time constants are almost identical in both solvents, water and DMSO. We have obtained results showing that the initial decays of the signal at 500 nm are monoexponential and can be fitted with a time constant of 244 ± 98 fs in water and 155 ± 51 fs in DMSO. The initial decays of the signal at 572 nm are monoexponential and can be fitted with a time constant of 560 ± 94 fs in water and 480 ± 384 fs in DMSO. The recovery of the bleach in water at 752 nm is found to be biexponential and is fitted with time constants of 490 ± 70 fs and 3.79 ± 1.25 ps for pumping with 677 nm and 480 ± 60 fs and 2.33 ± 0.81 ps for pumping with 360 nm. It indicates that the fast femtosecond component does not depend on solvent. Thus, we find it unlikely to assign it to inertial response of solvation. We have assigned the femto second component to vibrational wavepacket dynamics of higher electronic states of AlPcS 4 immediately upon excitation.

The time components in the range of 2-25 ps obtained for AlPcS 4 at different wavelengths are similar to those reported in the literature for many phthalocyanines. 23,39,59 Savolainen et al. 39 have assigned the time constant of 2.5 ps to dielectric response of solvation. Rao et al. 41 have assigned the time constant of 3-5 ps to vibrational relaxation. Howe and Zhang 23 have assigned the time constant of 10 ps to the lifetime for the S 2 → S 1 internal conversion, which seems rather long. The sudden rise at 572 nm followed by a decay (Figure 6a) is found to be biexponential and is fitted with time constants of 3.51 ± 0.50 and 220 ± 25 ps in water and 3.44 and 115 ± 95 ps in DMSO, indicating that the signals observed in the range of 500-572 nm demonstrate similar features of dynamics in both solvents. If dielectric response of solvation governed the dynamics of AlPcS 4 , high dielectric constant solvents such as water (ε = 80) and DMSO (ε = 48) would produce distinctive features of dynamics in contrast to the obtained results. Thus, we have assigned the time constants in the range of 2-25 ps observed in our results to vibrational relaxation.

The longest time constants in the range of 150-500 ps have been assigned to the decay from S 1 to the ground state, as suggested by Howe and Zhang, because we have found dynamics occurring on a similar time scale as that in ref 23. We have found for AlPcS 4 in water time constants of 469 and 299 ps for the decay of the positive signals (ESA) at 500 nm for pumping at 677 and 360 nm, respectively. Therefore, we have assigned them to the decay from S 1 to the ground state. We have found no evidence of the nanosecond component in the dynamics at 500 and 572 nm, in contrast to the results of Savolainen et al. 39 who obtained the component of 7 ns for ZnPc at 480 nm.

CONCLUSIONS

The excited state dynamics of AlPcS 4 have been studied in both aqueous and organic (DMSO) solutions by fluorescence and pump-probe transient absorption laser spectroscopy, providing information about the events occurring o n time scales ranging from femtoseconds to nanoseconds. The dynamics in both solvents is dominated primarily by monomeric molecules up to very high concentrations of 10 -3 M. We have found that the fast dynamics of AlPcS 4 in water and DMSO reveals three time scales, 115-500 fs, 2-25 ps, and 150-500 ps. The shortest time constants have been assigned to vibrational wavepacket dynamics, the few picosecond component has been assigned to vibrational relaxation in the excited electronic states, and the 150-500 ps components represent the decay from S 1 to the ground state. The experimental and theoretical treatment proposed in this paper provides a basis for a substantial revision of the commonly accepted interpretation of the Soret transition (B transition) that exists in the literature. The Soret band in the UV absorption spectrum of phthalocyanines originates both from the electronic transitions from the inner molecular orbitals to the first excited state S 1 (e g ) and from the HOMO orbital S 0 (a 1u ) to the second excited state S 2 (b 1u ) as well as to higher excited states S n .

Figure 1 .

 1 Figure 1. Normalized absorption spectra of AlPcS 4 solutions in the concentration range of 10 -5 -10 -3 M, (a) in water and (b) in DMSO.

Figure 2 .

 2 Figure 2. Normalized absorption and emission spectra of AlPcS 4 in aqueous solution at a concentration of c = 10 -6 M.

Figure 3 .

 3 Figure 3. Normalized absorption and emission spectra of AlPcS 4 in aqueous solution at a concentration of c = 10 -3 M.

Figure 4 .

 4 Figure 4. Absorption spectra of AlPcS 4 solution in water (black line) and in DMSO (red line) for c = 10 -3 M; optical length = 0.1 mm.

Figure 5 .Figure 6 .

 56 Figure 5. Emission spectra of AlPcS 4 in DMSO and in water at c = (a) 10 -5 and (b) 10 -3 M. Scheme 2. Excitation of the Excited Electronic States Pumped with the Pulses at 360 and 677 nm

Figure 7 .

 7 Figure 7. Transient absorption signal ΔA(t) of AlPcS 4 in water (a) and DMSO (b) as a function of time delay in the early time window up to 10 ps, pumped at 677 and probed at 500, 572, 664, and 690 nm; concentration = 10 -3 M.

Figure 8 .

 8 Figure 8. Transient absorption signal ΔA(t) of AlPcS 4 in water (a) and DMSO (b) as a function time delay in the full time window up to 1 ns, probed at 500 nm, pumped at 677 and 360 nm; concentration = 10 -3 M. The insets show the signal ΔA(t) in the time window up to 10 ps.

Figure 10 .

 10 Figure 10. Transient absorption signal ΔA(t) of AlPcS 4 in water (a,c) and DMSO (b,d) as a function time delay in the early time window up to 10 ps, pumped at 360 and 677 nm and probed at 614, 702, and 752 nm; concentration = 10 -3 M.

Figure 9 .

 9 Figure 9. Transient absorption signal ΔA(t) of AlPcS 4 at the probe wavelength of 572 nm in water (a) and in DMSO (b) for pumping at 360 and 677 nm; concentration = 10 -3 M. The insets show the signal ΔA(t) in the time window up to 10 ps.

Table 1 .

 1 Calculated Excitation Energies, Oscillator Strengths f > 0.1, Kohn-Sham Orbital Contributions to Transitions, and the Largest Coefficients of CI Expansion

		E, eV	λ, nm	f a	contributions b	coefficient	E, eV	λ, nm	f a	contributions b	coefficient
	AlPcS 4	1.9875	623.81	0.3830 219 → 229	0.10580	3.5488	349.37	0.3041 215 → 228	0.14721
					221 → 229	0.11607				219 → 229	0.12782
					222 → 229	0.10862				220 → 228	0.25495
					227(HOMO) → 228	0.59031				220 → 229	0.25545
		1.9949	621.50	(LUMO) (S 0 (a 1u ) → S 1 (e g )) 227(HOMO) → 229 (S 0 (a 1u ) → S 1 (e g )) 0.3859 219 → 228	0.12058 0.10102				221 → 228 221 → 229 222 → 228 222 → 229	0.32581 0.10732 0.19750 0.13936
		3.5054	353.69	221 → 228 222 → 228 227(HOMO) → 228 (S 0 (a 1u ) → S 1 (e g )) 227(HOMO) → 229 (S 0 (a 1u ) → S 1 (e g )) 0.1452 218 → 229	0.12107 0.12827 0.12001 0.59097 0.11303	3.6569	339.04	227(HOMO) → 230 (S 0 (a 1u ) → S n ) 227(HOMO) → 232 (S 0 (a 1u ) → S n ) 0.2948 213 → 228 214 → 229 215 → 229	0.14420 0.20454 0.26536 0.19537 0.10117
					219 → 229	0.35226				218 → 229	0.13844
					220 → 228	0.10412				219 → 229	0.36646
					220 → 229	0.20897				220 → 228	0.15522
					221 → 229	0.42233				221 → 229	0.24452
					222 → 229	0.10918				222 → 229	0.17421
					223 → 228 224 → 229 226 → 229 (S 0 (a 2u ) → S 1 (e g )) 227(HOMO) → 231	0.14080 0.12435 0.12200 0.10268	3.9651	312.69	227(HOMO) → 232 (S 0 (a 1u ) → S n ) 0.1932 211 → 229 212 → 229 213 → 228	0.10975 0.12158 0.13335 0.36666
					(S 0 (a 1u ) → S n )					213 → 229	0.39653
		3.5201	352.21	0.1332 219 → 228	0.12967				216 → 228	0.13379
					220 → 228	0.13796				219 → 228	0.11170
					221 → 228	0.13288				227(HOMO) → 234	0.11170
					221 → 229	0.12931				(S 0 (a 1u ) → S n )
					222 → 228	0.25215	3.9731	312.06	0.1375 211 → 228	0.14594
					223 → 229	0.11626				212 → 228	0.17506
					227(HOMO) → 230	0.18964				213 → 228	0.37033
					(S 0 (a 1u ) → S n )					213 → 229	0.37569
					227(HOMO) → 231	0.46735				216 → 229	0.11856
					(S 0 (a 1u ) → S n )					219 → 229	0.10609

a Oscillator strength. b Orbital number.

ACKNOWLEDGMENTS

The research work has been financed from funds for science in 2010-2012 as a research project "Preparation and implemen tation of new fields of studies in response to the needs of a contemporary labour market and requirements of knowledge based economy" UDA POKL.04.01.01. 00 213 /08 00 and NCN Grant Nr 3845/B/T02/2009/37.

AUTHOR INFORMATION

Corresponding Author *E mail: abramczy@mitr.p.lodz.pl.

Notes

The authors declare no competing financial interest.


LFG: Lexical Functional Grammar HPSG: Head-Driven Phrase Structure Grammar TAG: Tree Adjoining Grammar IG: Interaction Grammar FRIG: French Interaction Grammar SVM: Support Vector Machine PCFG: Probabilistic Context Free Grammar LAS: Labelement Attachement Score PA: Passive Aggressive POS: Part Of Speech vi

Keywords:

Solution Ranking for a Symbolic Parser by Tatiana Ekeinhor

Ranking is one of the methods used to improve data-driven parsers. The task of the ranker is to define a function that will assign a score to each parse candidate tree obtained in the parsing process.

We want to apply such models to resolve ambiguity problems in LEOPAR, a grammar-driven parser. LEOPAR produces a high number of parse solutions especially when the size of the input sentence grows. We want to choose the most suitable solutions among the parse candidates proposed by LEOPAR. We have to notice that a scoring system exists already in LEOPAR. It is based on some handcrafted rules.

We present in this document a ranking solution for LEOPAR based on statistical techniques. The candidate parses provided by LEOPAR are used as input for our ranker. We test our approach on the Sequoia TreeBank and obtain an improvement of the system compared to the handcrafted rules.

Introduction

A natural language parser is a program that builds the grammatical structure of natural language input strings. It decomposes sentences from natural language into syntactic parts and defines the relationship between these parts. Parsing is a traditional problem in the Natural Language Processing field and this task reveals to be hard. Indeed, natural language is complex by its ambiguity (human language allows more than one syntactical decomposition), variability (rules do not cover every detail in natural language) and openness (human language is continuously changing) [START_REF] Barbero | Dependency graphs in natural language processing[END_REF].

The core of our work deals especially with the ambiguity problem. All our examples will be in French as the tools we will use are developed for French language. Let us consider an example to get an idea of the problem: The interpretation 1.1 is the most obvious one. The 1.2 comes from the fact that belle can be an adjective and ferme a noun. We then obtain the pretty farm carries it. The last one has the most tricky interpretation with ferme seen like a modifier of belle and porte being a noun. The resulting meaning can be seen in 1.3.

Handling this ambiguity problem consists in choosing the best parse from candidate analyses provided by a parser. Each analysis is built according to different techniques. We distinguish grammar-driven techniques and data-driven techniques for parsing.

Grammar-driven parsers use linguistic resources (grammars) in order to process parsing when data-driven parsers use machine learning methods based on corpora resource to do so. For datadriven parsers, there is a natural way to choose among the candidate solutions because the parsing provides score or probability to each parse according to decisions made during the process.

In our work, we will look for a way to assign a score to the candidate analyses of a grammardriven parser, LEOPAR [START_REF] Guillaume | Interaction grammars[END_REF].

2

From Parsing to Ranking

Parsing

Parsing refers to the process of analysing the syntactic structure of a given input. It consists in decomposing a complex structure into its components. It was first applied to programming languages for their compilation and interpretation. Then it was used on natural language. As it is the case for programming languages, parsing helps the interpretation.

"It is generally accepted that finding the structure of a sentence can be useful in determining its meaning." [START_REF] Charniak | Statistical techniques for natural language parsing[END_REF].

Parsing can be seen as a twofold task. The first one is to determine all the possible syntactic structures of sentences and the second is to select the most suitable ones. Depending on the way descriptions are made, we distinguish two major representations of the syntactic structure of a sentence: the constituent structure, also called phrase-structure (or constituency tree) and the dependency structure (or dependency tree). In phrase-structure representation, sentences are represented by phrases (non-terminal nodes), structural categories (non-terminal labels) and, sometimes, functional categories (grammatical functions). Constituency rules describe how to combine phrases (like noun phrases, verbal phrases...), in order to obtain a sentence. In dependency view, as in figure 2.2, the main verb is the structural center of the representation.

All other syntactic units depend, either directly or indirectly, on this verb.

Even if both approaches (phrase-structure vs dependency structure) are often presented in opposition, we have to notice that they are complementary.

The dependency theory [START_REF] Tesnière | Eléments de syntaxe structurale[END_REF] is based on the idea that the syntactic structure of a sentence consists of binary asymmetrical relations that express functional categories (arc labels) between the words of the sentence. This kind of relation links (directed arcs) a governor (or head) to a dependent (or modifier). In dependency parsing, a dependency tree is the result of the computation, where nodes are the word of the input sentence, and the arcs are the binary relations from head to dependent. On representations, arrows go from governor to dependent. In our example of figure 2.2, the wordform regarde governs fille with the relation obj. Dependency representation is also found more adequate for languages which allow greater freedom in word order.

Some of the criteria for establishing a dependency relation between a head H and a dependent D, in a construction C, are of type [START_REF] Arnold | [END_REF]:

• H determines the syntactic category of C

• H is mandatory, D may be optional

• The form of D depend on H

• ... Natural language parsers are programs that analyse the structure of a sentence. These programs are built in different ways. According to the source of the knowledge involved for the analysis of a sentence there are two main types of parsers: grammar-driven and data-driven. Grammar-oriented and data-oriented systems are not mutually exclusive. There exist grammar-driven parsers that include statistical disambiguation components (like in the XTAG Project (XTAG Research Group, 2001)). LEOPAR parser [START_REF] Guillaume | A toolchain for grammarians[END_REF]) is a grammar-driven parser. In this work, we aim to incorporate statistical information in order to resolve ambiguity problems and rank the output obtained after the parsing phase of LEOPAR.

Grammar-driven Parsing

A grammar-driven parser is a system where grammars are employed to deduce the parses of an input string of a natural language.

How is a sentence structured in natural language? It is in response to this question that grammars have been developed. Grammars are sets of rules that govern how syntactical units (clauses, phrases, ...) are structurally constructed. They also help determining whether a sentence belongs to a language or not. The goal of a grammar is to model a language and to bring out linguistic knowledge involved in that language.

A formalism is a precise specification of a language. A grammar formalism is a linguistic description device. Many grammar formalisms exist like Lexical Functional Grammar (LFG) [START_REF] Ronald | Lexical-functional grammar: A formal system for grammatical representation[END_REF], Head-Driven Phrase Grammar (HPSG) [START_REF] Pollard | Head-driven phrase structure grammar[END_REF],

Tree Adjoining Grammar (TAG) (Joshi and Schabes, 1997) just to mention a few.

In the grammar-driven approach, parsing can be considered as the process of solving a set of constraint problems where the grammatical rules define those constraints. More concretely, a sentence is seen as a sequence of words. By analysing them, the parser assigns lexical functions and defines head-dependent relations. We can cite LEOPAR parser and Link Parser (Sleator and Temperley, 1993) as grammar-driven parsers. One problem of this approach is that the used grammar may not be exhaustive. It is an approximation of the language that it aims to process.

Robustness is defined as the capacity of a parser to analyze any input sentence, and the lack of robustness is a weak point of the grammar-driven parser systems. The last but not least need of this method that makes it hard to implement is that, it requires considerable linguistic and computational expertise.

Interaction Grammars

In the following, we will introduce how the parsing system we want to improve works. LEOPAR is a grammar-based parser that uses a grammar formalism called Interaction Grammar (IG). It is a lexicalized phrase-structure grammar as opposed to dependency structure grammar.

"Interaction grammars combine two key ideas: the grammar is viewed as a constraint system, which is expressed through the notion of tree description, and the resource sensitivity of natural languages is used as a syntactic composition principle by means of a system of polarities" [START_REF] Guillaume | Interaction grammars[END_REF].

IG mixes properties of different grammar formalisms. Therefore this formalism uses the tree description notion of grammars like Tree Adjoining Grammar (TAG). It is inspired by the Categorial Grammars (CGs). Indeed CGs are based on the principle of composition and are organized according to the view that syntactic constituents should generally be combined as functions or according to a function-argument relationship. In IG it is expressed through a polarity system where linguistic resources are considered as consuming resources. The polarity expresses the saturity of syntactic tree, in other words their capacity to be combined with other elementary trees.

A tree description is a set of nodes and hierarchical relations between them. Nodes represent phrases and the hierarchical relations represent how phrases are embedded one inside another. The syntactic properties of the phrases are expressed through features structures. A tree description is then a specification of a set of syntactic trees and each tree is a model of the tree description.

"[...] A positive node represents an available grammatical constituent whereas a negative node represents an expected grammatical constituent". [START_REF] Guillaume | Interaction grammars[END_REF] IG also uses the features structure views of Unification Grammars like Lexical Functional Grammar (LFG) and Head-driven Phrase Structure Grammar (HPSG). IG specifies tree categories and operations like superposition and composition. The tree description is a model of specification that associates a model to a word. It can be viewed as a set of partially specified tree which are superposed under polarity controls. process. An EPTD is an elementary tree defined in the grammar. FRIG (FRench IG) is a set of linguistic resources that embeds a grammar, frigram, and a lexicon, frilex for the French language. There are two levels in the grammar formalism: the source grammar and the object grammar. The source grammar represents linguistic generalisations and is written by a human.

The object grammar is used by a Natural Language Processing (NLP) system and results from the compilation of the first one. The tool used to develop the grammar is called XMG [START_REF] Duchier | The metagrammar compiler: An nlp application with a multi-paradigm architecture[END_REF]. XMG provides a high level language for writing source grammars and a compiler which transforms the grammars into operational object grammars. Frigram is a relatively large coverage grammar that contains about 4,000 EPTDs. Frilex is a lexicon of 528,949 French word entries.1 In figure 2.4, we can see an example of tree associated with the sentence Jean la voit.

LEOPAR

In order to make experiment, a parser based on IG was developed and is named LEOPAR2 .

LEOPAR (eLEctrOstatic PARser) is a syntatic parser based on Interaction Grammar formalism.

In order to parse a sentence, each word of the sentence is associated with an elementary tree (EPTD) contained in the lexicon. This action is denoted by lexical selection. The number of possible lexical selections may present an exponential complexity in the length of the sentence.

Specifics methods were designed to remove most of the wrong lexical selection at a minimal cost.

"The lexical disambiguation module checks the global neutrality of every lexical selection for each polarized feature: a set of trees bearing negative and positive polarities can only be reduced to a neutral tree if the sum of the negative polarities for each feature equals the sum of its positive polarities." [START_REF] Guillaume | A toolchain for grammarians[END_REF] The resulting lexical selections are presented in the form of an automaton, and are sent to LEOPAR. LEOPAR processes the composition of two syntactic tree descriptions. This operation is seen as an electrostatic process during which an elementary operation consists of the identification of two nodes from the anchored grammar.

" [...] Negative nodes tend to merge with positive nodes of the same type and this mechanism of neutralization between opposite polarities drives the composition of syntactic trees to produce trees in which all polarities have been saturated". This operation is called neutralization of polarities"

. [START_REF] Guillaume | Interaction grammars[END_REF] The parsing succeeds if the resulting tree has only neutral polarities. LEOPAR is built to produce phrase-structure trees but It contains a constituency to dependency converter, so It can output dependency structures. In appendix A.1 an example of final tree and its transformation into dependency structure is provided.

LEOPAR has a command line and a graphical user interface. The parsing process can be visualised at each step via LEOPAR in order to check the behaviour of the grammar and the lexicon. LEOPAR allows the user to process the parsing manually and the user can choose himself the lexical selection of the sentence and neutralize the nodes for the selection.

In the two steps of lexical disambiguation and parsing, all possible solutions are kept without discarding even the less probable ones. This leads to a large amount of possible syntactic structures.

We will use dependency structures in our work since the final output of LEOPAR is a dependency tree. Now the goal is to use statistical methods in order to discriminate the solutions of the parsing.

LEOPAR Scoring Method

There is no natural way to choose among parses of a grammar-driven system when it provided several parses in the theory. However by including some statistical information or inference rules, a score or weight can be assigned to parses. LEOPAR uses handcrafted rules to compute score of parses. The weight of a dependency tree as computed by LEOPAR parser is a sum of values of the two operations. The first operation follows rules below:

• the starting value is set to 1,000,

• -50× number of node (of a sentence),

• each dependency tree will receive a weight value.

The value obtained after this computation is then add to the result value of a second operation. This second operation attributes a value according to dependency relation with following configuration, δ = dep position -gov position:

• -|δ| : allow to penalize long dependencies,

• a value given by the label, the part of speech (POS) of governor that follows rules listed in the table 2.1.

Data-driven Parsing

The second framework is the statistical data-driven parsing. We can cite [START_REF] Charniak | A maximum-entropy-inspired parser[END_REF], [START_REF] Klein | Accurate unlexicalized parsing[END_REF] or [START_REF] Nivre | Maltparser: A data-driven parser-generator for dependency parsing[END_REF], just to mention a few of the works in this domain. Here the parsing process is based on machine learning and the knowledge of the language is gained from hand-parsed corpora. The parser is trained on corpora and tries to produce the most accurate analysis. A formal model defines possible analysis. A sample data is used to train the model and an inference is made based on previous assumption for parsing.

In data-driven approaches, another split can be made according to the model used. On one hand we have the graph-based model. Here, dependency trees are seen like graphs. After decomposing a graph into arcs, scores are attributed to arcs. Parsing is processed by looking for the highest scoring graphs. On the second hand we have transition-based models, where dependency trees are seen like transition states. Parsing is performed by constructing the optimal transition sequence using the transition history.

As we said, data-driven methods are machine learning approaches to natural language parsing.

In others words models are built using machine learning on existing data. Before introducing what machine learning is and how parsing is modelled in data-driven systems, we will shortly remind what probability theory is.

Probability Theory

A probability theory can be understood as a mathematical model for the intuitive notion of uncertainty. To represent this notion or uncertainty we need a probability space defined regarding an experiment.

Definition 2.1. A probability space is a triple (Ω, F, P ) consisting of:

• A sample space Ω which is a set of outcomes (Ω is non-empty).

• F ⊂ P(Ω) a set of subsets of Ω called events.

• P a probability measure which is a function from F to [0, 1].

Definition 2.2. A set S is said to be countably infinite, if there is a one-to-one correspondence between N and S.

For all the following definitions Ω is finite or has a contably infinite number of outcomes. This is the discrete probability theory. In the generalized theory called continuous probability theory,

Ω = R k , k ∈ N.
Definition 2.3. An event A ∈ F is a set of elements of Ω. P (A) represents how likely is the outcome to be member of A.

Definition 2.4. We denote by N the number of elements in Ω. An experiment is a countable set of outcomes, together with a function p : Ω → [0, 1] with the property:

p(ω) = 1 N , ω ∈ Ω ω∈Ω p(ω) = 1
The function p is called a probability mass function.

Definition 2.5. For all A ⊆ Ω we define the probability measure P of an event A as:

P (A) = ω∈A p(ω)
P has to obey three rules:

• P (A) ≥ 0 • P (Ω) = 1
• For two disjoint events A and B, P (A ∪ B) = P (A) + P (B).

( .

Ω = {o 1 , o 2 , o 3 , o 4 , o 5 , o 6 }, |Ω| = 6 p(o k ) = 1 6 , k = 1, ...6
There are 2 6 possible events. For instance A 1 = (Obtaining an odd number), A 2 = (Obtaining a prime and even number), A 3 = (Obtaining an odd or even number), A 4 = (Obtaining an odd and even number), A 5 = (Obtaining an even number), A 6 = (Obtain 2, 3, 4 or 5).

The associated probabilities are displayed in table 2.2.

Event Probability

A 1 : odd

3 6
A 2 : prime and even

1 6
A 3 : odd or even 6 6

A 4 : odd and even 0 6

A 5 : even

3 6 A 6 : {o 2 , o 3 , o 4 , o 5 } 4 6
Table 2.2: Table of events and associated probabilities Definition 2.6. Suppose A and B are events in a sample space and suppose that P (B) > 0. The conditional probability of A given B is defined as:

P (A|B) = P (A ∩ B) P (B) P (A ∩ B)
is also denoted by P (A, B).

(2.3) Let us consider our dice example. Suppose that we are looking for the probability that the number 6 comes up, knowing that the outcome is greater than 4.

P (o 6 ) = 1 6 , P ({5, 6}) = 2 6 , P ({o 6 } ∩ {5, 6}) = 1 6 Then P ({o 6 }|{5, 6}) = 1 2
Given A and B, we can introduce two main rules of probability:

• product rule: P (A, B) = P (B|A)P (A).

• sum rule: In the Bayesian theory, we have such interpretation:

P (A) = B P (A, B). x X o 1 -1 o 2 1 o 3 -1 o 4 1 o 5 -1 o 6 1
• P (A) is called the prior, it is the initial degree of belief in A.

• P (A|B) is the posterior, it is the degree of belief having accounted for B.

• The quotient P (B|A) P (B) represents the support B provides for A.

Theorem 2.8. Let A 1 , ..., A n be partitions of Ω such that P (A k ) > 0 and B be any event such that P (B) > 0. The sum rule gives:

P (B) = n j=1 P (B|A j )P (A j )
Then we obtain the generalization of the Bayes rules for all k:

P (A k |B) = P (B|A k )P (A k ) n j=1 P (B|A j )P (A j ) (2.4)
Suppose that we roll a dice. Each time an odd number comes up we lose one euro, and when an even number comes up we win one euro. We write ω = (ω 1 , ..., ω n ) , where ω i = 1 if the i'th roll is an even number and ω i = -1 otherwise. The winning after n rolls is:

S(ω) = n i=1 ω i
The winning S is a mapping from Ω → R. Such mappings are called random variables Definition 2.9. A random variable is a mapping from Ω → R.

We will write {X : x} for {ω : X(ω)} and P (X = x) for P ({ω : X(ω) = x)} Definition 2.10. We describe as the probability mass function of a random variable X the function p X : R → [0, 1] given by:

p X (x) = P (X = x)
Definition 2.11. The distribution function of a random variable X is the function

F X : R → [0, 1]
given by:

F X (x) = P (X ≥ x)
There are many different distributions functions like the normal distribution, the Poisson distribution, the binomial distribution and so on.

Definition 2.12. We consider two random variables

X = (x 1 , ...x n ), Y = (y 1 , ...y m ).
The joint probability of X and Y is denoted by: P (X = x i , Y = y j ) and represents the probability that X takes the value x i and Y the values y j .

The conditional probability of X and Y is denoted by: P (X = x i |Y = y j ) and represents the probability the X takes the value x i knowing that Y took the value y j .

Machine learning

"Machine Learning is a field of study that gives machine the ability to learn without being explicitly programmed". Arthur Samuel "A machine is said to learn from experience E with respect to a task T and a performance measure P, if its performance at tasks in T, as measured by P, improves with experience E". Tom

Mitchell

Consider that we want to predict whether an incoming mail is a spam or not. The goal is to build a machine that will take mails as input and will predict spam or not spam as the output. To do so, a large set of mails marked as spam or not spam is used to set the parameters of an adaptive model. A function is obtained, which takes an input and returns the corresponding output. This is determined during a phase called training phase or learning phase, based on training data. After the training phase, the system has to identify the output of new input data, this is the test phase.

According to the type of data and the problem to solve, we distinguish between:

• Supervised Learning: • Unsupervised Learning: Here, the training data consist of example input without any corresponding output value. We speak about unlabelled data. The goal of this method is to find similarity in data and create groups or classes according to that similarity. This is called clustering (e.g. Image recognition, Voice separation...).

In
• Semi-Supervised Learning: In this case, the training data combines both labelled and unlabelled examples (e.g. some statistical parsers...). It mixes the advantage of both supervised and unsupervised learning. Unlabelled data are used because they are less expensive to build when labelled data bring information used to improve the accuracy of the algorithm.

• Reinforcement Learning: "The problem is to find the suitable action in a given situation in order to maximize a reward. There is no example of optimal output, the system has to discover it by mean of trial and error. A general feature of reinforcement learning is the trade-off between exploration, in which the system tries out new kinds of actions to see how effective they are, and exploitation, in which the system makes use of actions that are known to yield a high reward. Too strong a focus on either exploration or exploitation will yield poor results." [START_REF] Christopher | Pattern Recognition and Machine Learning[END_REF]) (e.g. multi-agent system, flocking simulation...).

In our work, we are interested in supervised methods.

Supervised Methods

In this section, we will talk about the classification problem in supervised machine learning. The reason is that we are so far, only interested in categorical output (parse selection) and not in numerical one.

Definition 2.13. We consider a set V with the addition (+) and multiplication (•) operations.

V is a vector space over a Field F if and only if:

• (V, +) is a commutative group which means that:

-∀ ( u, v) ∈ V × V , u + v = v + u, -∀ ( u, v, w) ∈ V × V × V , u + ( v + w) = ( u + v) + w, -V contains the additive identity element denoted by 0 V , such that ∀ u ∈ V , u + 0 V = 0 V + u = u, -∀ u ∈ V , the equation x + u = 0 V and u + x = 0 V have a solution in V called additive
inverse and denoted by -u.

• (•) verifies the following properties:

-∀ (α, β) ∈ F × F , and u ∈ V , α • (β • u) = (α • β) • u -∀ u ∈ V , 1 F • u = u -∀ (α, β) ∈ F × F , and u ∈ V , (α + β) • u = α • u + β • u, -∀ α ∈ F , ∀( u, v) ∈ V × V , α • ( u + v) = α • u + α • v
An element of V is called vector.

The aim of the classification is to take an input vector x and to assign it one of a K-discrete classes C k where k = 1, ...K. For K = 2 we speak about binary classification. For instance, deciding whether a mail is a spam or not, whether a transaction is fraudulent or not, whether a tumor is benign or malignant.

There are many classes of models for solving classification tasks. The goal of algorithms used in each model is to define a function that will assign to each input vector a value y. We distinguish:

• Model with a discriminant function : y(x) = w T x + w 0 , where w T is the column vector associated to the row vector w w is called weight vector and w 0 is called bias. An input vector x is assigned to class C 1 if y(x) ≥ 0, and to class C 2 otherwise. The decision boundary correspond to y(x) = 0, which corresponds to a (D -1)-dimensional hyperplane within the D-dimensional input space. The perceptron algorithm [START_REF] Rosenblatt | The perceptron[END_REF] belongs to this class of model.

• Another approach is to model the conditional probability distribution p(C k |x) in an inference stage, and subsequently use this distribution to make optimal decisions. Two techniques exist to determine p(C k |x) :

-One technique is to model it directly, for example by representing them as parametric models and then optimizing the parameters using a training set. Those are referred to, as the probabilistic discriminative models.

-Alternatively, a generative approach (generative because it looks for p(x, C k ), the joint probability of x and C k ) can be adopted in which p(x|C k ) is modelled, together with the prior probabilities p(C k ) for the classes, and then the required posterior probabilities using Bayes' theorem will be :

p(C k |x) = p(x|C k )p(C k ) p(x)
This is the probabilistic generative model. Iterative Reweighted Least Squares (IRLS)

is an algorithm of this class of models. It is used to find maximum likelihood3 solution of the parameters of the model.

Supervised data-driven Parsing: Process

As we said before, ambiguity is one of the central problems in Natural Language Parsing. Indeed, one sentence (even a short and simple one) can have a large number of parses. Statistical parsing approaches try to resolve the ambiguity problem by assigning a probability to each parse tree, thereby ranking trees in matter of relevancy.

In many statistical models, the probability for each candidate tree is calculated as a product of terms, each term corresponding to some substructure within the tree. In order to generate the most likely derivation of a sentence a probabilistic model is required. Most employed model theories are generative. A generative model is a model that uses joint probabilities (as opposed to discriminative model where conditional probabilities are used). We will expose a specific kind of generative models, the history-based model as described in [START_REF] Collins | Discriminative reranking for natural language parsing[END_REF]. In historybased models, a parse tree is represented as a sequence of decisions, the decisions being made in some derivations of the tree. Each decision has an associated probability, and the product of these probabilities defines a probability distribution over possible derivations.

We can describe parsing as a machine learning task to induce a function f from X to Y, given a training data.

X is a set of sentences, Y a set of parse trees. Y (X) is defined as the candidate parses for a sentence X, Y (X) ⊂ Y.

We are looking for a model that assigns a probability P (X, Y ) to every pair sentence-parse (X, Y ). Now, the question is how to define P (X, Y ).

In history-based models, a mapping is defined between each (X, Y ) and a decision sequence < d 1 , ..., d n >. A decision sequence can be the sequence of rules or parse moves that build (X, Y ) in some order. Given all that, we can compute the probability of a tree as follows:

P (X, Y ) = n i=1 P (d i |Φ(d 1 , ..., d i-1 )) (d 1 , ..., d i-1
) is the history of the i'th decision. Φ is a function that groups decisions into equivalent classes.

All that can be summarized within three essential components:

• A formal model

• A sample of data set of pairs (X, Y ), where Y is the correct tree of X

• An inducing inference scheme that defines actual analysis of a sentence An example of this model is the Probabilistic Context Free Grammars (PCFG). The inference scheme represents the decisions sequence. For a PCFG, it is the top-down, left most derivation rule of a tree.

Ranking the candidate parses provided by a first parsing process is one solution to improve statistical parsers. It is a solution that uses statistical information downstream of the parsing process. We have to notice that there are other models like in [START_REF] Nivre | Integrating graph-based and transition-based dependency parsers[END_REF],

where different models are combined or like the Supertagger [START_REF] Bangalore | Supertagging: An approach to almost parsing[END_REF], where statistical computations are operated upstream of the process of parsing. We have made the choice to operate downstream the parsing process. We will describe now how the ranking works.

Ranking

Ranking is an ordering relation. Dependency tree ranking is the task of selecting the most plausible dependency tree for a given sentence. In figure 2.5, we can see an example of ambiguity in the syntactic decomposition of the sentence 2.5 : We can see this problem as a machine learning task. There are many applications, the design of search engines, information extraction platforms, movie recommendation systems... This is the same problem when we want to order parse tree results of syntactical derivation process. There are two general settings for this problem: the score-based and the preference-based settings. By using information in data, a learning algorithm will define a ranking prediction function. This predictor is a real-value function called score function: the scores assigned to the input by this function determine their ranking. To do so, many techniques exist: in the score-based system there are: Margin-based algorithm, Support Vector Machine based ranking algorithm or boosting algorithm for ranking... The preferred based settings consist of two stages. In the first stage, a sample of labelled pairs S is used to learn a preference function h that assigns a higher value to a pair (u, v) when u is preferred to v or is to be ranked higher than v, and smaller values in the opposite case. This preference function can be obtained as the output of a standard classification algorithm trained on S. Then, the preference function h is used to determine a ranking on input.

We expect that the methods succeed in making generalizations about features seen in a given corpus and achieve a good performance in order to make accurate predictions. In what follows we will present the score-based method we have chosen.

Reranking is one of the issues that statistical parsing has to handle in order to improve their systems performance. We call it reranking because parsing already provides a ranking for trees with the probabilities computed during the process. In our work, we will refer to this solution as ranking because we are applying this method to the outputs of a grammar-driven parse which are not naturally ranked.

To do so, we will use a model that will allow us to discriminate a good analysis from a worse one. This model differs from the generative one involved in the parsing task. We will focus on finding the features that promote or penalize a dependency tree. In this context we will consider on one hand corpora where the gold standard is unique for every sentence. On the other hand, dependency structures are dependency trees 1 .

Problem Definition

In what follows we will describe the notation and definitions we will use in the rest of the document: Let X be the set of natural language sentences and Y the set of dependency structures.

Parser: We call parse a function which takes a sentence as input and returns a set of dependency structures. For a given x ∈ X , parse(x) ⊂ Y. Note that |parse(x)| varies according to x. So that, some sentences have zero, one or several parses. We are interested in the case where parse(x) = ∅ Annotated Corpus: An Annotated Corpus C is defined as a set of couples (x, y ) ⊂ (X × Y), where x is a sentence and y the dependency structure considered as the correct parse for the sentence x. y is called the gold standard. |C| is the number of sentences in the corpus C.

The Labeled Attachment Score (LAS) of a dependency structure y according to the gold standard y measures the quality of a description tree with respect to the gold standard. It is denoted by: LAS y (y) = number of relations in y equals to y number of relations in y Feature: A f eature is a function that maps a dependency structure into numerical values. f is thus an R-valued function of the set of dependency structures.

f : Y → R A f eature vector f is a m-dimensional vector of numerical features. f = (f 1 , ..., f m ). f (y) = (f 1 (y), ..., f m (y)) ∈ R m , f j (y)
represents the value of the j'th feature on y.

1 dependency structures are such that y and y have the same number of relations

Weight Vector: Given a feature vector f , a weight vector θ is a m-dimensional vector of R m , θ = (θ 1 , ...θ m ). Each θ j represents the weight of a f j .

Score:

The score of a parse tree y is the dot product between the vector θ and the feature function f (y) defined as:

score θ (y) = m j=1 θ j • f j (y)
Knowing that the parser produces a set of candidates we will use a discriminative model to attribute a score to each of them, based on specific features.

Features For Ranking

The features describe a parse in matters of syntactic phenomenon. The performance of a ranker depends on the relevancy of the feature patterns extracted from the inputs. In our case, the inputs are different parses of a sentence.

When selecting a feature, a trade-off must be made between a feature as general as possible, so that it can handle a great number of parses and as specific as possible, in order to be able to distinguish a good parse from a bad one.

A parse is mapped to a feature vector:

f (y) = (f 1 (y), ..., f m (y))
Every f j is associated with a configuration or schema, and the value of f j (y) corresponds to the number of times this configuration appears in y.

For instance f (regarde,V,G,R,suj) counts the number of times that the verb (V) regarde governs (G) the relation suj with an arrow going to the right (R).

We present below some feature schemata as it was proposed in [START_REF] Le Roux | Modèles génératif et discriminant en analyse syntaxique: expériences sur le corpus arboré de Paris 7[END_REF].

Unigram: The instance of this class describes one dependency relation in a sentence. A dependency relation l, between two positions i and j governed by w i is denoted by w i l -→ w j .

We create two sextuplets, one for the governor w i , the other for the dependent w j with this schema [word, lemma, part of speech (pos), status of dependency (governor or head), direction of In order to have features that can be as general as possible we can "underspecify" the previous patterns. To get an idea we consider sentences 3.1 and 3.2.

The dependency obj between regarde and fille will give this configuration for one underspecification:

[ , regarder, V, G, R, obj] and [ , fille, N, D, R, obj].
With two underspecifications we obtain: [ , , V, G, R, obj] and[ , , N, D, R, obj].

Besides, the dependency obj between regarde and mer will give with one underspecification:

[ , regarder, V, G, R, obj] and [ , mer, N, D, R, obj].
With two underspecifications we obtain the same patterns as for sentence 3.1: The underspecification technique can be applied to all the types of schemata. We will avoid mentioning it for the rest of the schemata.

[ , , V, G, R, obj] and [ , , N, D, R, obj].
Bigram: The instances of this schema indicate the two co-occuring members of a dependency relation l.

Given the dependency relation w i l -→ w j , we create one tuple with this configuration:

[word w i , lemma w i , part of speech w i , word w j , lemma w j , part of speech w j , distance between position i and j, direction of the dependency, type of dependency]. (3.3) For the dependency obj between regarde and fille, we have these patterns: [regarde, regarder, V, fille, fille, N, 2, R, obj] Syntactic Context: For the instances of this schema, we consider two dependencies w i l -→ w j m -→ w k . One tuple is created with the configuration: [word w i , lemma w i , part of speech w i , word w j , lemma w j , part of speech w j , word w k , lemma w k , part of speech w k , distance between position i and j, distance between position i and k, direction of the dependency l, type of dependency l, direction of the dependency m, type of dependency m].

(3.4) We consider the dependency obj between regarde and fille, and the dependency det between fille and la. We obtain :

[regarde, regarder, V, fille, fille, N, la, le , D, 2, 1, R, obj, L, det]

A Discriminative model

We will use a score-based model for the ranking. A score is attributed to each parse. We remind that the score is the dot product between the vector θ and the feature function f (y):

score θ (y) = m j=1 θ j • f j (y)
The subset of k best-ranked dependency structure is denoted by Ŷk as below:

Ŷk = argmax y∈parse(x)
score(y)

The vector θ is estimated from the training data. In order to achieve this, machine learning multi-class classification algorithms [START_REF] Collins | Discriminative reranking for natural language parsing[END_REF] or [START_REF] Le Roux | Modèles génératif et discriminant en analyse syntaxique: expériences sur le corpus arboré de Paris 7[END_REF] are used for ranking a parser output. The section below will explain how we estimate the parameters of our model.

3.

3.1 MIRA: Theory [START_REF] Crammer | Ultraconservative online algorithms for multiclass problems[END_REF] presented a learning algorithm for online large margin classification called MIRA (Margin Infused Relaxed Algorithm). In its binary form MIRA is closed to the perceptron algorithm [START_REF] Rosenblatt | The perceptron[END_REF]. We will use its adaptation to the multi-class classification task.

MIRA is an online algorithm. This means that it operates incrementally and adjusts the models parameter progressively. For each sentence it makes a prediction. This prediction is compared to the correct parse (the gold standard) and an update is made if the ranker is wrong. This problem could then be expressed as follows:

min θ subject to: score(y t ) -score(y t ) ≥ L(y t , y t )

∀y t ∈ parse(x t ) (3.5)
L(y t , y t ) is the loss of a parse y t relative to the correct tree y t . It is the distance between y t and the correct one y t . The higher this value, the closer is the parse tree to the reference. In our specific case, we use the Labeled Attachment Score of the parse tree to define the measure L.

L(y t , y t ) = 1 -LAS y (y t )

The largest loss a dependency tree can have is 1 and the minimal is 0. The minimal value expresses that the parse is identical to the gold standard, the maximal value the opposite.

We refer to score(y t ) -score(y t ) as the margin attained on round t. The goal of the algorithm is to achieve a margin at least as large as the loss of the incorrect tree. The more errors a tree has, the farther away its score will be from the score of the correct tree.

The task of MIRA is to incrementally learn the weight vector θ, according to the constraints specified above. On each update, it keeps the smallest norm possible of the changed θ subject to margin specification. This is formalized this way:

min 1 2 θ (t+1) -θ (t)
subject to score(y t ) -score(y t ) ≥ L(y t , y t )

∀y t ∈ parse(x t ) (3.6)
Assuming that the parsing may fail to propose a parse that is identical to the gold standard, we define the oracle o t as the parse y t which is the closest to the reference. In other words the oracle is the parse with the minimal loss L. We redefine equation 3.6 as follows:

min 1 2 θ (t+1) -θ (t)
subject to score(o t ) -score(y t ) ≥ L(y t , y t )

∀y t ∈ parse(x t ) (3.7)
Instead of trying to satisfy the margin constraint for all the parse(x t ) we make the assumption that only the margin which matters is the one that involves the incorrect tree with the highest score. We do so because it may be difficult or impossible to satisfy all the margin constraints knowing that for some sentences the number of parses is quite large.

Then equation (3.7) becomes equation (3.8). The benefit of this last transformation is that the simplification leads to a closed form solution. We finally have the optimization problem expressed as:

min 1 2 θ (t+1) -θ (t)
subject to score(o t ) -score(y (t) ) ≥ L(y t , y t )

∀y t ∈ Y k (3.8)
The algorithm update the weight θ based on the optimization formula above. Going through the dataset once for updating θ is called a turn or iteration. It is advised to perform several turns in order to improve the accuracy of the system.

Resolution

The update makes sure that the prediction of the current instance does not change too radically the prediction made for the previous instances. We consider the case where |Y k | = 1. The equation 3.8 is resolved in [START_REF] Crammer | Ultraconservative online algorithms for multiclass problems[END_REF] by constructing the Lagrangian of equation 3.8 and taking partial derivative. This yield to equation 3.9, using the Hildreth algorithm [START_REF] Censor | Parallel optimization: Theory, algorithms, and applications[END_REF]) that how to determine α t when there is one constraint in the option problem.

The solution of the optimization is then:

θ (t+1) = θ (t) + α t (f (o t ) -f ( ŷt )) with α t = Λ f (o t ) -f ( ŷt ) 2 Λ = max(0, L(y t , y t ) -(score(o t ) -score( ŷt ))) (3.9)
The algorithm is described below: The Sequoia Treebank [START_REF] Candito | Le corpus Sequoia: annotation syntaxique et exploitation pour l'adaptation d'analyseur par pont lexical[END_REF] is a freely available annotated French corpus. It is developed in the Alpage team (Université Paris 7) by Marie Candito and Djamé Seddah. The corpus is freely available under the free license LGPL-LR1 . The Sequoia Treebank contains 3,240 sentences, from the French Europarl, the regional newspaper L'Est Républicain, the French Wikipedia and documents from the European Medicines Agency.

Each sentence is annotated for part-of-speech and phrase-structure following the French Treebank guidelines [START_REF] Abeillé | Enriching a french treebank[END_REF]. The constituency trees were then automatically converted to dependency trees.

The corpus is provided in various forms:

• * + f ct.mrg strict files are files with one sentence per line, with phrase-structure in bracketed format, in which the phrase-structures are strictly compliant to the French Treebank annotation scheme.

Preprocessing

Among the 3,204 sentences of the Sequoia Treebank, we choose 717 sentences that correspond to well formed and short sentences which length is greater than 2 and lower than 14. From the 717 sentences, we retain only sentences for which LEOPAR proposed more than one parse, meaning for 436 sentences. The different parses for a sentence are stored in a .conll file like in figure 4.2.

The weight value is the one computed by LEOPAR during the parsing process.

Experimental Setup

We remind that our goal is to build a specific type of classifier: a ranker, on the output of the parsing of LEOPAR parser. We are using the MIRA algorithm and we want to determine the parameter θ of the system.

score θ (y) = m j=1 θ j • f j (y)

Features

We used the unigram feature schema and a modification of this features to create another class of features by including the distance of the governor-dependent relations. The different configurations are presented below:

• A set of features of the unigram category: [word, lemma, pos, dependency status, dependency direction, dependency type].

• A set of features of the unigram category with the underspecification of the word: [ , lemma, pos, dependency status, dependency direction, dependency type].

• A set of features of the unigram category with underspecification of the word and the lemma: .

• A combination of the these first three features.

• A set of features of the unigram category with dependency length that we will denoted by Unigram DepLength: [ , lemma, pos, dependency status, dependency direction, dependency type, dependency length].

• A set of features of the Unigram DepLength with the underspecification of the word: [ , lemma, pos, dependency status, dependency direction, dependency type, dependency length]].

• A set of features of the unigram DepLength with the underspecification of the word and the lemma: [ , lemma, pos, dependency status, dependency direction, dependency type, dependency length]].

• A set of features of the three features above.

Implementation

We FeatureVector:

A FeatureVector is the object representation of a vector of features.

FileProcess:

This class contains several tools for the file computation task.

Mira:

MIRA is the implementation of the MIRA Algorithm.

Experiment parameters

The experiment was configured to use one oracle and a number of hypotheses that can be chosen for each instantiation of the experiment. We remind that, for one sentence we can have a large number of parses. On one hand, we conducted an experiment on all the parses. On the second hand, we reduced the number of parses to the 5-best list of sentences according to the scoring metric of LEOPAR.

Some simple sentences received fewer than 5 parses. We partitioned and validated our dataset using 10-fold cross-validation rules. We used a null start weight θ = 0 with an average of 4,000 features. We call turn the fact that we iterate over the whole dataset one time, choosing randomly the order of the data examples. For our experiment we made 50 turns. At each turn, the weight is computed recursively as it has been said earlier, and we keep the weight of the last data example of the current turn as the starting weight for the next turn.

Results

The Labeled Attachment Score is an evaluation metric that computes the proportion of "scoring" tokens that are assigned both to the correct head and the correct dependency relation label. The LAS of the corpus is the mean of the LAS of the best ranked parse for each sentence weighted by the length of the sentence. This is the metric we will use for evaluating our work.

In order to compare the prediction performance of our system we consider two reference values:

• Oracle: The best prediction that the ranker can process, the one closer to the gold standard.

• AntiOracle: The worst prediction that the ranker can made, the further to the gold standard.

Oracle and Antioracle are the references for the comparison of the performance of the systems below:

• LEOPAR Prediction: The prediction made by LEOPAR according to its handcrafted rules.

• Ranker: The prediction of our ranker.

The graphics of figure 4.5 and figure 4.6 show the evolution of the LAS through 50 turns.

We notice that the performance of the ranker depends on the used feature schemata. With the Unigram DepLength schema with the 5-best list, we obtain the best results, whereas with the Unigram DepLength with two underspecifications we obtain not really good results. This suggests that the second feature schema, as shown in figure 4.6, is too general to discriminate good parses from the worse ones.

Our ranker is able to select better parses than the evaluator of LEOPAR depending on the chosen feature schemata. The values of the LAS for the 50'th θ for two schemata is presented in table 4.2.

In order to evaluate the convergence of θ, we computed θ i+1 -θ i 2 . As we can see in figure 4.7, no update of θ has been performed from the 33 th turns until the end. On the other side, in figure 4.8, θ is still changing. This suggests that the stopping criterion is not suitable enough. [START_REF] Hasler | Margin infused relaxed algorithm for Moses[END_REF] proposed two stopping criteria: "stop running the algorithm when no update has been formed during a full epoch" or "stop when during three consecutive epochs the sums of all updates in each dimension has not changed by more than a predefined value".

Figure 2 Figure 2 . 1 :

 221 Figure 2.1: Example of constituency tree

Figure 2 . 2 :

 22 Figure 2.2: Example of dependency tree

Figure 2 .

 2 3 shows an example of tree description.

Figure 2 . 3 :

 23 Figure 2.3: Tree description associated with the French relative pronoun qui (who) used inside a prepositional complement

Figure 2 . 4 :

 24 Figure 2.4: PTD associated with the sentence Jean la voit and its minimal saturated model

. 2 )

 2 We consider an experiment which consists in rolling a fair dice. There are six possible outcomes: Obtain 1 (o 1 ), Obtain 2 (o 2 ), Obtain 3 (o 3 ), Obtain 4 (o 4 ), Obtain 5 (o 5 ), Obtain 6 (o 6 )

  this case, the training data include input examples along with their corresponding output values. This kind of data is called labelled data. Cases like predicting the output of input instances, where these outputs are discrete class values, are called a classification task (e.g. Text classification, Part of Speech Tagging...). When the output consists of one or more continuous variables then it is called a regression task.

  at the girl on the balcony.

Figure 2 . 5 :

 25 Figure 2.5: Example of parse tree provided by LEOPAR

  the dependency (left (L) or right (R)), type of dependency]. Here is an example for the sentence in 3.1: (3.1) Jean JOHN regarde LOOK la AT fille. THE GIRL. John is looking at the girl. For the dependency obj between regarde and fille figure 3.1 we have these patterns : [regarde, regarder, V, G, R, obj] and [fille, fille, N, D, R, obj]

Figure 3 . 2 :

 32 Figure 3.1: Example of dependency tree

  • * .xml files are the XML FrenchTreebank version for the * + f ct.mrg strict files • * +f ct.mrg files are the same sentences, still in bracketed format, but with phrase-structures compliant to the ftb-uc Treebank instantiation. • * conll files contain the dependency trees, obtained through automatic conversion, in CoNLL 2006 tabulated format. For our experiments we use the .conll files of the version 5.1 of Sequoia TreeBank. The CoNLL format is a data format for representing dependency tree, which is illustrated by figure 4.1. It was introduced during the CoNLL (Conference on Computational Natural Language Learning), in order to set up a common way to represent dependency structures.

Figure 4 . 1 :

 41 Figure 4.1: Example of a .conll file, with its associated dependency tree

Figure 4 . 2 :Figure 4 . 3 :

 4243 Figure 4.2: Example of the .conll file representing different parses provided by LEOPAR .

  have implemented the MIRA algorithm in JAVA. A overview of the UML class diagram of our architecture is presented below: We represent our corpus by the DepParseTree structure. A DepParseTree stands for different sentences associated with their parses. A parse is a DepTree that is defined as a collection of nodes DepNode together with the list of parents and children. AFeature-Feature-FeatureDistance-FeatureWeight: The AFeature class models the notion of features that Feature, FeatureDistance and Fea-tureWeight extend. Feature represents the schema that we have called Unigram. It contains methods that give the underspecification of Unigram configuration. FeatureDistance represents the Unigram DepLength and inherits the Feature Class. The weight computed by LEOPAR is also used as a feature that we model with the class FeatureWeight.

Figure 4 . 4 :

 44 Figure 4.4: Histogram of number of parses evolution

Figure 4

 4 Figure 4.6: LAS: Unigram DepLength with two underspecifications

Figure 4 Figure 4 . 8 :

 448 Figure 4.7: Norm: Unigram DepLength 5-best

Figure A. 1 :

 1 Figure A.1: Example of ambiguity in trees

Table 2 .

 2 1: Table with the rules used according to dependency type

	Type of dependency	Value
	passive	50
	aff	40
	agt	40
	obj	if gov = v|aux → 40 else 30
	suj	if gov = v|aux → 40 else 30
	iobj	30
	agt	30
	tense	30
		if gov = v and dep = adj → -30 -10 * delta
	mod	else if gov = v|aux and δ > 0 → 20
		else 10
		10

Table 2 .

 2

		3: A random variable with it values
	Theorem 2.7. Bayes' Rules
	P (A|B) =	P (B|A)P (A) P (B)

Table 4

 4

	.1: Number of parses according to sentences

Table 4 . 2 :

 42 LAS for the different Features used

	0.95 1		Oracle Leopar Prediction AntiOracle Ranker
	0.9
	0.85
	LAS
	0.8
	0.75
	0.7
	0.65	0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50
			number of turn
		Figure 4.5: LAS: Unigram DepLength 5-best
	System	Unigram DepLength 5-best Unigram DepLength 5-best 2 underpsecfication
	Oracle	0.864	0.864
	LEOPAR	0.809	0.809
	Ranker	0.838	0.798

For one word we can have many entries. For instance for a verb, one entry defining it as a transitive verb and another as an intransitive one.

LEOPAR is freely available under the CeCILL license at http://www.loria.fr/equipes/calligramme/

The likelihood of a set of parameter values, θ, given outcomes x, is equal to the probability of those observed outcomes given those parameter values, that is L(θ|x) = P (x|θ)

Lesser General Public License For Linguistic Resources

Acknowledgements

I would like to express my gratitude to my supervisor Bruno, for his guidance and availability during all my work. I am also grateful to all those who helped me, with their advice and support during my school year and even more my thesis.

Finally I wish to thank my parents, Nyedji and Faadji, for their support and encouragement throughout my study.

Abbreviations

Conclusions

In this thesis, we focused on machine learning techniques to improve parsers, downstream the parsing process. Indeed, our goal was to incorporate statistical methods on a grammar-driven parser, LEOPAR, in order to rank the different parses that it provides. LEOPAR parser integrated already a scoring method based on handcrafted rules. We investigated multi-class classification methods and chose to apply the online margin algorithm called MIRA to solve our problem. We built a classifier used for the specific task of ranking. We evaluated our ranker on the Sequoia TreeBank.

We noticed that the performance of our ranker is largely related to different parameters like the size of our dataset, the used feature schemata, the stopping criteria... Even though the data set used was small, we achieve slightly better results compared to LEOPAR scoring method. Further works could be to investigate:

• Increasing the size and improving the quality of the used treebanks. Statistical method inferences depend on the treebank used to build their models. The quality of treebanks is crucial is the efficiency of such models.

• Using other feature schemata. As we have seen, our ranker performance depends as well, on the used feature schemata quality. However, we have to notice that there is no automatic way to know if the feature schema has a significant effect on the performance of the system.

As has said Charniak in [START_REF] Charniak | Coarse-to-fine n-best parsing and maxent discriminative reranking[END_REF], "[...] developing feature schemata is much more of an art than a science".

• We have to remind that there are other statistical models for ranking in the literature such as the maximum entropy model [START_REF] Charniak | Coarse-to-fine n-best parsing and maxent discriminative reranking[END_REF], the Markov Randoms Fields, Boosting Approaches [START_REF] Collins | Discriminative reranking for natural language parsing[END_REF] or generative models like the one developed in [START_REF] Sangati | A generative re-ranking model for dependency parsing[END_REF].

In our work, we made cooperate a statistical technique and a handcrafted-grammar parser in order to improve the performance of the parser for the parse selection task. Maybe, the key idea will be to use a hybrid parsing system that will use both two approaches directly during the parsing process. Hybrid parsing systems use probabilistic models during the parsing process, before tree combination, i.e. upstream the parsing process. Recent works, (XTAG Research Group, 2001), [START_REF] Kanayama | A hybrid japanese parser with hand-crafted grammar and statistics[END_REF], [START_REF] Toutanova | Parse disambiguation for a rich hpsg grammar[END_REF], suggest that hybrid systems can contribute to the improvement of the parsing systems accuracy.