Hernán Mella
email: hmella@uc.cl

Hui Wang
email: hui.wang1@philips.com

Cristian Montalba
email: cristian.montalba@uc.cl

Sergio Uribe
email: suribe@uc.cl

An Off-Resonance Insensitive Orthogonal CSPAMM sequence (ORI-O-CSPAMM) for the acquisition of CSPAMM and MICSR grids in half scan time

Keywords: Off-resonance insensitive, CSPAMM, tagging, MICSR, cardiac MRI

Purpose: To develop an Off-Resonance Insensitive Orthogonal CSPAMM sequence for the acquisition of CSPAMM and MICSR grids in half of the acquisition time.

Methods:

Phantom and mid-level LV short-axis tagged images were acquired using CSPAMM, ORI-CSPAMM, O-CSPAMM, and the proposed ORI-O-CPAMM sequences to interrogate and compare its behavior under off-resonance effects produced by vegetable oil and subcutaneous and epicardial fat.

The images were compared in terms of signal and the capacity to obtain complex difference and MICSR images. Results: Like ORI-CSPAMM, the proposed ORI-O-CSPAMM sequence removed almost completely the off-resonance artifacts produced during the tagging preparation. Tagging grids without DC components were obtained with ORI-O-CSPAMM using complex difference and MICSR from only two complementary images, which reduced the scan time to a half compared to CSPAMM and ORI-CSPAMM. The removal of off-resonance effects and the capacity to obtain MICSR images are advantages of ORI-O-CSPAMM over the O-CSPAMM sequence.

Conclusion:

We developed a novel and fast tagging sequence designed to remove off-resonance effects during the tagging preparation, and to obtain complex difference and MICSR grids in half of the scan time compared to CSPAMM and ORI-CSPAMM sequences, which could allow its application to clinical protocols.

1) INTRODUCTION

Tagged Magnetic Resonance Imaging has been used extensively to study the function of the heart as well as other organs. After its introduction, several techniques have been proposed to improve the original idea, leading to new sequences with improved image quality [START_REF] Ibrahim | Myocardial tagging by Cardiovascular Magnetic Resonance: evolution of techniques--pulse sequences, analysis algorithms, and applications[END_REF][START_REF] Axel | Tagged magnetic resonance imaging of the heart: A survey[END_REF]. The first and still widely used tagging technique was Spatial Modulation of Magnetization (SPAMM) [START_REF] Axel | MR imaging of motion with spatial modulation of magnetization[END_REF], which employed a spatial encoding gradient and two non-selective RF pulses to rapidly modulate the magnetization. One of the most notable improvements was the development of the Complementary SPAMM (CSPAMM) sequence [START_REF] Fischer | Improved myocardial tagging contrast[END_REF], which was introduced to improve the tagging contrast in later phases of the cardiac cycle and remove the unwanted DC signal of SPAMM images, leading to a zero mean sinusoid suitable for motion estimation techniques such as Harmonic Phase-based analysis (HARP) [START_REF] Osman | Cardiac motion tracking using CINE harmonic phase (HARP) magnetic resonance imaging[END_REF][START_REF] Osman | Imaging heart motion using harmonic phase MRI[END_REF][START_REF] Tecelão | Extended harmonic phase tracking of myocardial motion: Improved coverage of myocardium and its effect on strain results[END_REF][START_REF] Liu | Shortest path refinement for motion estimation from tagged MR images[END_REF][START_REF] Liu | HARP tracking refinement using seeded region growing[END_REF][START_REF] Mella | HARP-I: A Harmonic Phase Interpolation Method for the Estimation of Motion from Tagged MR Images[END_REF], Sine-Wave Modeling (SinMod) [START_REF] Arts | Mapping displacement and deformation of the heart with local sine-wave modeling[END_REF][START_REF] Wang | Cardiac deformation analysis using 3D SinMod from 3D CSPAMM tagged MRI[END_REF][START_REF] Wang | Cardiac motion tracking with multilevel B-splines and SinMod from tagged MRI[END_REF], and Gabor filter banks [START_REF] Qian | Extraction and tracking of MRI tagging sheets using a 3D gabor filter bank[END_REF][START_REF] Chen | Using gabor filter banks and temporal-spatial constraints to compute 3D myocardium strain[END_REF]. A Magnitude Image CSPAMM Reconstruction (MICSR) [START_REF] Nessaiver | Magnitude image CSPAMM reconstruction (MICSR)[END_REF] method was introduced later as an alternative reconstruction procedure to combine SPAMM acquisitions using only magnitude images. The resulting signal shared similar characteristics with CSPAMM (zero mean sinusoid) but with improved tag persistence and enhanced contrast during most of the acquisition window. Moreover, MICSR cancelled out any spurious phase gained during the readout from complex SPAMM data. However, due to the doubled acquisition time, the use of both CSPAMM and MICSR remain restricted for clinical applications, and both CSPAMM and MICSR images are prone to off-resonance effects during the tagging preparation, which can impact the motion estimation in presence of tissue with fat content [START_REF] Fahmy | Inherent fat cancellation in complementary spatial modulation of magnetization[END_REF][START_REF] Reyhan | Off-resonance insensitive complementary SPAtial Modulation of Magnetization (ORI-CSPAMM) for quantification of left ventricular twist[END_REF].

To overcome the acquisition time issue, Wang et al. [START_REF] Wang | Orthogonal CSPAMM (OCSPAMM) MR tagging for imaging ventricular wall motion[END_REF][START_REF] Wang | Cardiac deformation analysis from orthogonal CSPAMM (OCSPAMM) tagged MRI[END_REF] introduced the Orthogonal CSPAMM sequence (O-CSPAMM), which allowed to obtain a CSPAMM image with orthogonal taglines using only two acquisitions instead of four. By rotating in 90° the tagging gradient in the complementary SPAMM acquisition, O-CSPAMM removed the DC component while generating an orthogonal grid after complex subtraction (i.e., O-CSPAMM is the sum of two orthogonal zero-mean sinusoids).

While this methodology allowed the acquisition of data that can be optimally used for motion estimation [START_REF] Wang | Cardiac deformation analysis from orthogonal CSPAMM (OCSPAMM) tagged MRI[END_REF], O-CSPAMM is not compatible with MICSR reconstructions and is prone to offresonance effects. To fix the off-resonance sensitivity issue, Fahmy et al. [START_REF] Fahmy | Inherent fat cancellation in complementary spatial modulation of magnetization[END_REF] proposed a new method to cancel the off-resonance effects of the fat in CSPAMM acquisitions by inverting the tagging gradient of the second SPAMM image and adjusting its duration. However, this approach was limited to one chemical specie (fat) and was inapplicable at field strengths bigger than 1.5T, especially for closely spaced tag lines. Reyhan et al. [START_REF] Reyhan | Off-resonance insensitive complementary SPAtial Modulation of Magnetization (ORI-CSPAMM) for quantification of left ventricular twist[END_REF] introduced an Off-Resonance Insensitive CSPAMM (ORI-CSPAMM) sequence to compensate for all forms of off-resonance, in which the tagging gradient was split into two parts separated by a 180° refocusing hard pulse, removing the off-resonance effects of any chemical specie at the cost of some intensity changes. Nonetheless, the last two approaches share the same time restrictions than conventional CSPAMM.

In this work, we propose an Off-Resonance Insensitive O-CSPAMM (ORI-O-CSPAMM) sequence, which takes the best of O-CSPAMM and ORI-CSPAMM. The proposed sequence allows the obtention of orthogonally tagged CSPAMM images free of off-resonance artifacts and suitable for MICSR reconstructions in half of the acquisition time compared to CSPAMM and ORI-CSPAMM. In the ORI-CSPAMM sequence, the spurious phase gained during the tagging preparation is rewound by splitting the tagging gradient into two parts separated by a 180° refocusing hard pulse.

2) METHODS

2.1) Sequence development

Figure 1 shows the pulse sequence diagram for the CSPAMM, O-CSPAMM, ORI-CSPAMM, and the proposed ORI-O-CSPAMM sequences. For CSPAMM, the transversal magnetization of each image after the readout is given by:

, = ( , 1, , ) -( , 1, ) ( + ) sin , ( 1a
) , = ( , 1, , ) + ( , 1, ) ( + ) sin , (1b)
where and are increasing and decreasing functions (respectively) which depend on the time , the relaxation time 1, the magnetization in the thermal equilibrium , and the flip angle of the imaging RF pulse (in following equations, the dependency on , 1, , and will be dropped to simplify the equations); = √-1 the complex unit, the encoding frequency produced by the tagging gradient, the tissue position at a reference frame (usually at end-diastole in cardiac imaging), and and denote spurious phases induced due to off-resonance effects during the application of the tagging gradient and the read-out, respectively. Then, the complex difference and MICSR images are obtained by:

In the previous expressions, the complex difference taken in Eq. 2a does not remove the spurious phase gained during the readout, while the MICSR does.

The magnetization expression for each image in a O-CSPAMM scan are given by:

, = ( , 1, ) -( , 1, ) ( + ) sin( ), (3a)
, = ( , 1, ) + ( , 1, ) ( + ) sin( ), (3b)
= sin( ) ( + ) + ( + ) . (3c)
= 2 sin ( )

+ + + + sin ( ) + + + (3d)
In Eq. 3c, the image obtained by complex difference is a grid consisting of the sum of two sinusoids, while in Eq. 3d, the MICSR image contains unwanted higher order terms.

In ORI-CSPAMM, the tagging gradient during each image's preparation is split into two parts with opposite polarities and separated by a refocusing hard RF pulse (see Figure 1C). The last makes that the spurious phase gained during the first gradient application be completely rewound after applying the second gradient. Thus, the longitudinal magnetization after the third pulse of each SPAMM acquisition is:

, = { - ( )} sin( ), (4a)
, = { + ( )} sin( ), (4b)
In this investigation, we could not reproduce the results of (18), as the spurious phase gained during the read-out was not transformed into a cosine modulation by the subtraction operation (as will be demonstrated later). Therefore, the complex difference and MICSR images obtained with ORI-CSPAMM are:

= 2 sin( ) ( ), (5a)
= 4 sin ( ) ( ), (5b)
which contain motion in one direction without off-resonance effects.

With both O-CSPAMM and ORI-CSPAMM, a tagging grid without DC frequencies can be obtained by acquiring 2 and 4 images, respectively. In both cases, the magnetization is shifted by , which induces a distortion in the complex image that can be removed by taking its magnitude or using MICSR. However, the first procedure generates low (DC component) and high harmonic frequencies, and the second is restricted only to ORI-CSPAMM because of the presence of higher order terms (see Eq. 3d).

To overcome these issues, in ORI-O-CSPAMM we applied the ORI preparation used in ORI-CSPAMM (see Figure 1C) twice in two orthogonal directions to obtain a SPAMM grid within each image (see Figure 1D). The pair of images obtained with ORI-O-CSPAMM follows:

, = { -cos( ) ( )} sin( ), (6a)
, = { + cos( ) ( )} sin( ), (6b)
which can be combined taking the complex difference or using MICSR, obtaining:

= 2 sin( ) cos( ) ( ), (7a)
= 4 sin ( ) cos( ) ( ), (7b)
In Eq. 7a, still contains the phase shift gained during the read-out, but this is fixed in Eq. 7b by the MICSR reconstruction. In both Eqs. 7a and 7b the obtained result is a grid.

The expressions given in Eq. 7 can be re-written using the identity cos sin = (sin( + )sin( -))/2, as:

= sin( ) ( ( + ) - ( - )), (8a)
= 2 sin ( ) ( ( + ) - ( - )). (8b)
From Eq. 8, three important observations can be done: It is important to notice that using the two complementary images scanned with CSPAMM and ORI-CSPAMM sequences, only 1D motion information can be obtained, while with the same data scanned with O-CSPAMM and ORI-O-CSPAMM, 2D motion information can be recovered.

2.2) Phantom and in-vivo data acquisition

A phantom consisting of a bottle filled with the same amount of water and vegetable oil was scanned.

For the in-vivo acquisition, three healthy male volunteers with age 27, 28, and 35 years old, weight 60, 74, and 68 kg, and heart rate 51, 68, and 71 beats/min were studied. Each volunteer provided a written informed consent approved by the local institutional review board. ECG triggered images were acquired at end-expiration in a bread-hold condition. Mid-level short-axis views of the heart were obtained using a four-element cardiac coil. The phantom and in-vivo protocols consisted of the acquisition of bSSFP, CSPAMM, ORI-CSPAMM, O-CSPAMM and ORI-O-CSPAMM images. For the ORI-O-CSPAMM scans, tagging gradients 1/√2 times weaker were applied in the directions X+Y and X-Y to achieve the user-defined tag-period in the directions and .

All the sequences for both phantom and in-vivo acquisitions were acquired on a 1.5T Achieva system (Philips, Best, The Netherlands) using a multi-shot Turbo-Field-Echo (TFE) with imaging parameters listed in the Table 1, setting the shortest trigger delay time and the maximum number of cardiac phases. Abbreviations: ETL, echo-train-length; FA, flip angle.

2.3) Image analysis

To compare the signal characteristics of ORI-O-CSPAMM, we normalized the signal of each complementary image before the complex difference and MICSR reconstructions and compared the normalized mean signals of ORI-O-CSPAMM and ORI-CSPAMM in both fat and water regions of the phantom. The images were normalized by the of the fat, which has the biggest magnitude at the first cardiac phase (see Figure 2). was estimated by calculating the mean signal inside a ROI in the fat region of one of the complementary acquisitions of the ORI-CSPAMM sequence (see Figure 1b and Eq. 1), as proposed by NessAiver et al. [START_REF] Nessaiver | Magnitude image CSPAMM reconstruction (MICSR)[END_REF].

To obtain the normalized mean signal, two rectangular ROIs with the same dimensions were placed in the fat and water regions. Then, the maximum signal of the magnitude of the complex difference images inside each ROI was found and used to define a threshold. This procedure was applied to the first cardiac phase, masking the pixels where the signal was greater than 0.65 times the maximum value obtained inside each rectangular ROI, obtaining the fat and water masks shown in Figure 2.

Finally, the normalized mean signal was calculated with the pixels inside the fat and water masks. 3) RESULTS Figure 3 shows the first frame of the complex difference and MICSR images obtained from CSPAMM, ORI-CSPAMM, O-CSPAMM, and ORI-O-CSPAMM data. The differences in the trigger delay time between acquisitions is due to the different duration of the preparation pulses. The resulting images show that those acquired without using the ORI preparation (see Figures 3B and3D), presented a shift at the fat-water interface. Images obtained using complex difference showed a higher signal than MICSR, which is the expected behavior. MICSR images were possible to obtain using CSPAMM, ORI-CSPAMM, and ORI-O-CSPAMM scans, while using O-CSPAMM was not possible.

3.1) Phantom acquisition

The complex difference and MICSR images obtained with O-CSPAMM showed distorted grids in the water region produced by high-frequency spectral peaks. water part of the phantom image (see Figure 3). Although 45° rotated and weaker gradients were applied using ORI-O-CSPAMM, the same encoding frequency (tag period) was achieved compared to the other sequences (see blue vertical arrows in (B)).

Figure 4 shows the k-spaces of the first complementary image and the complex difference reconstructions (see Figure 3) obtained in the phantom with the four acquisition sequences. Highfrequency spectral peaks are present in all the k-spaces of the first complementary images, but their intensity is reduced with ORI-O-CSPAMM (see Figure 4A). The additional spectral peaks are generated by the reduced k-space in the phase direction (see Table 1). In the case of O-CSPAMM, the most energetic high-frequency peaks were not removed after taking the complex difference (see Figure 4B), which curiously only distorted the water part of the phantom image (see Figure 3D). For the acquisition of the ORI-O-CSPAMM data, the tagging gradients were rotated in 45° into the direction X+Y and X-Y and made weaker by a factor of 1/√2. However, the same period and direction of the tagging lines was observed as stated by the Eq. 8.

Figure 5 shows the normalized mean signal for the fat and water regions. The signal curves obtained from complex-difference showed the expected behavior in both fat and water, with the highest signal in the first cardiac phase and decaying through the acquired temporal window. The signals measured from MICSR images also behaved as expected although there were evident differences between fat and water curves. In the fat (see Figure 5A), the MICSR signals increased at the very beginning of the acquisition window, reaching higher values than those obtained by complex difference, and decaying until the end, which follows the characteristic signal behavior of MICSR images. In the water (see

3.2) In-vivo acquisition

Figure 6 shows the first cardiac phase of complex difference and MICSR images obtained with O-CSPAMM and ORI-O-CSPAMM for the three volunteers. MICSR images obtained from O-CSPAMM acquisitions produced distorted grid as predicted by the Eq. 3d, which was not the case of ORI-O-CSPAMM acquisitions. The signal of complex difference images was higher than MICSR images for the three volunteers, which was also observed in the phantom (see Figures 3 and5) and it is the expected behavior. The three volunteers presented epicardial and subcutaneous fat (see bSSFP images in Figure 6), which distorted the tagging grids in O-CSPAMM (see red arrows in Figure 6) but not in ORI-O-CSPAMM images.

Figure 7 shows the same results described for the Figure 6 but for an end-systolic cardiac phase. The signal of MICSR obtained from ORI-O-CSPAMM was higher than complex difference images in all the cases, which was also observed in the phantom (see Figure 3 and5) and it is the expected behavior.

DISCUSSION AND CONCLUSIONS

Although the CSPAMM sequence provides images that are suitable to assess not only the cardiac function but also to evaluate other organs, its use remains limited for clinical applications due to the prolonged scan times. Additionally, images obtained from CSPAMM data can suffer from offresonance effects generated during the tagging preparation. In this investigation a new acquisition sequence called ORI-O-CSPAMM was proposed to tackle these issues. ORI-O-CSPAMM allows the acquisition of a tagging grid free of DC frequencies and free of off-resonance effects in half of the acquisition time compared to the CSPAMM and ORI-CSPAMM sequences. Furthermore, ORI-O-CSPAMM is suitable to obtain MICSR images, which cannot be obtained with O-CSPAMM and could be beneficial to improve the tagging contrast for some clinical applications.

In healthy people, the primary source of off-resonance artifacts in cardiac tagged MR images is the epicardial fat, which can bias the cardiac twist's estimation regardless of ORI tagging sequences.

However, in patients with fatty infiltration of the LV, ORI sequences could improve the cardiac motion and strain estimations. Moreover, a recent study has demonstrated that the strain estimated from tagged MR images is a valuable marker for staging non-invasively liver fibrosis [START_REF] Lefebvre | MRI cine-tagging of cardiac-induced motion for noninvasive staging of liver fibrosis[END_REF] in Non-Alcoholic Fatty Liver Disease (NAFLD) patients. As the NAFLD stages are an inflammatory process in the presence of fat, we hypothesize that the use of ORI sequences can be helpful at the early stages of the disease. Even more, ORI-O-CSPAMM can be used in clinical protocols without excessively increasing the scan time than commonly used SPAMM sequences.

In phantom and in-vivo data, ORI-CSPAMM and the proposed ORI-O-CSPAMM sequences corrected the distortions generated by the vegetable oil and epicardial and subcutaneous fat (see Figures 3,[START_REF] Osman | Imaging heart motion using harmonic phase MRI[END_REF][START_REF] Tecelão | Extended harmonic phase tracking of myocardial motion: Improved coverage of myocardium and its effect on strain results[END_REF]. Also, we found that O-CSPAMM was particularly sensitive to unwanted highfrequency spectral peaks, which distorted the grid in the water part of the phantom images (see Figure 3). The same behavior was not observed on in-vivo data. We hypothesize that although the complex difference did not remove these spectral peaks, the distortion generated in the water part of the phantom was not visible in tissues with shorter relaxation times such as those scanned in the in-vivo experiments due to the signal decay. Additionally, we demonstrated that the signal obtained with the ORI-O-CSPAMM sequence was comparable to ORI-CSPAMM and no major differences were observed (see Figure 5).

In this investigation we could not reproduce the results obtained in [START_REF] Reyhan | Off-resonance insensitive complementary SPAtial Modulation of Magnetization (ORI-CSPAMM) for quantification of left ventricular twist[END_REF] for ORI-CSPAMM in which the spurious phase gained during the readout was converted into a cosine modulation in complex difference images. However, this was also an issue with the three other sequences. In Figure 8, the phase of the complex difference phantom images is non-zero due to the off-resonance effects and nonidealities during the readout. Here we showed that this adverse condition can only be corrected using MICSR. In complex difference images the phase is always non-zero while in MICSR images the phase is zero and (the last is due that MICSR images have only real part that varies from positive to negative values).

When the maximum gradient of an MR system is limited by the hardware, ORI-O-CSPAMM also allowed the reduction of the gradient amplitude (or duration) into a 70% of the strength needed to generate the same tag periods with the other sequences. This was predicted by Eqs. 8a and 8b and confirmed by the phantom and in-vivo acquisitions (see Figures 3,[START_REF] Fischer | Improved myocardial tagging contrast[END_REF][START_REF] Osman | Imaging heart motion using harmonic phase MRI[END_REF][START_REF] Tecelão | Extended harmonic phase tracking of myocardial motion: Improved coverage of myocardium and its effect on strain results[END_REF].

For the imaging parameters described in Table 1 for the acquisition of the volunteers, the average breath-hold duration with O-CSPAMM and ORI-O-CSPAMM sequences was 16 seconds, which is tolerable for almost any person, including patients with cardiopathies. With the CSPAMM and ORI-CSPAMM sequences, on the other hand, the average breath-hold needed to obtain 2D information would be around the 32 seconds (twice the time needed for the CSPAMM and ORI-CSPAMM scans in this investigation). The 16 seconds breath-hold duration could be further reduced using acceleration techniques such as half-scan [START_REF] Feinberg | Halving MR imaging time by conjugation: Demonstration at 3.5 kG[END_REF][START_REF] Macfall | Correction of spatially dependent phase shifts for partial Fourier imaging[END_REF], SENSE [START_REF] Pruessmann | SENSE: Sensitivity encoding for fast MRI[END_REF], and compressed sensing [START_REF] Lustig | Sparse MRI: The application of compressed sensing for rapid MR imaging[END_REF], or using faster readouts such as spirals [START_REF] Ahn | High-Speed Spiral-Scan Echo Planar NMR Imaging-I[END_REF][START_REF] Börnert | Improvements in spiral MR imaging[END_REF].

It must be noticed that the tagging preparation time needed to acquire ORI-O-CSPAMM data is a few milliseconds longer than with the other sequences due to the duplicated preparation. This is better appreciated in Figures 3,6, and 7, were the trigger delay time of the first cardiac phase of the data acquired using ORI-O-CSPAMM was 5 ms longer than the CSPAMM and ORI-CSPAMM sequences. The total duration of the ORI-O-CSPAMM preparation for the imaging parameters given in Table 1 was 7.8 ms, whereas for CSPAMM, ORI-CSPAMM, and O-CSPAMM was 3.1, 3.9, and 3.1 ms respectively.

Although not considered in this study, ORI-O-CSPAMM can be made more robust by adding sliceselective RF pulses during the tagging preparation to obtain a Slice-Following sequence [START_REF] Fischer | True myocardial motion tracking[END_REF], which handles the through-plane motion of the heart during the acquisition. Additionally, variable flip angle strategies can be used in the readout to improve the tagging contrast at the end of the scanned temporal window.

In conclusion, we introduced a novel and fast sequence designed to remove off-resonance effects during the tagging preparation, obtain complex difference grids, and obtain MICSR grids in half of the scan time, which could allow its application to clinical protocols. The proposed ORI-O-CSPAMM sequence could be especially useful to study the function of organs suffering from diseases involving fat, such as fatty LV infiltration or NAFLD.

Figure 1 :

 1 Figure 1: (A) CSPAMM, (B) O-CSPAMM, (C) ORI-CSPAMM, and (D) ORI-O-CSPAMM tagging preparations. In all the figures, M, P, and S denote the measurement, phase, and slice axes.

  (a) ORI-O-CSPAMM gives images with the same contrast as CSPAMM and O-CSPAMM (considering that the absolute value of the sum of two sinusoids is bounded from above by 2. See Eq. 3c, 3d, and 8). (b) Although the tagging gradients were applied towards the X and Y directions, the tagging patterns obtained with ORI-O-CSPAMM are rotated in 45° into the X+Y and X-Y directions (i.e., to obtain tag lines pointing towards the directions X and Y, the ORI-O-CSPAMM gradients must be applied in the directions X-Y and X+Y). And (c), in ORI-O-CSPAMM smaller tagging gradient areas (by a factor of 1/√2), i.e. tagging encoding frequencies, are needed to generate the same tag period as in CSPAMM, ORI-CSPAMM, and O-CSPAMM (this is more evident if we consider the frequency of the wave sin( ⋅ ), where = ( , ), = ( , ), and ‖ ‖ = √2 ).

Figure 2 :

 2 Figure 2: Fat and water masks used for the estimation of the Normalized Mean Signal in (a) ORI-CSPAMM and (b) ORI-O-CSPAMM images.

Figure 3 :

 3 Figure 3: Water and fat phantom images obtained using complex difference (CD. Upper row) and MICSR (bottom row). The images were acquired using (A) bSSFP, (B) CSPAMM, (C) ORI-CSPAMM, (D) O-CSPAMM, and (E) ORI-O-CSPAMM sequences. The trigger delay of each image is shown in the figures and varies due to the different duration of the preparation pulses. The images acquired without ORI preparation showed a shift in the tagging pattern at the water-fat interface. The MICSR image obtained from O-CSPAMM lost the grid pattern as predicted in Eq. 3d.

Figure 4 :

 4 Figure 4: k-spaces of the (A) first complementary image acquired by each sequence and (B) the complex difference (CD) reconstructions. High-frequency spectral peaks are present on all the images in (A) although are less visible with ORI-O-CSPAMM (see red arrows). In the complex difference images, the most energetic high-frequency peaks are completely removed with all the sequences but not with O-CSPAMM (see red arrows in (B)), which generate distortions in the

Figure

  Figure5B), however, the decaying part of the MICSR signals are not appreciable in the acquisition

Figure 5 :

 5 Figure 5: Normalized mean signal in the fat (A) and water (B) obtained from images reconstructed using complex difference (CD) and MICSR, from data acquired using ORI-CSPAMM and ORI-O-CSPAMM sequences. The normalized signal from an ORI-CSPAMM acquisition is shown using a blue and red continuous line respectively, while curves obtained from an ORI-O-CSPAMM acquisition are displayed using blue and red square markers.

Figure 6 :

 6 Figure 6: Images acquired using the O-CSPAMM (second column) and ORI-O-CSPAMM (third column) sequences and reconstructed using complex difference (CD) and MICSR for (A) volunteer 1, (B) volunteer 2, and (C) volunteer 3. Each volunteer has a bSSFP image as reference. The displayed images correspond to the end-diastolic cardiac phase. The discrepancies in the trigger delay times are due to the difference in the duration of the preparation pulses. The red arrows show the places where the grid is distorted by the presence of epicardial and subcutaneous fat. The images acquired with ORI-O-CSPAMM did not show any distortion in the places indicated by arrows.

Figure 7 :

 7 Figure 7: Images acquired using the O-CSPAMM (second column) and ORI-O-CSPAMM (third column) sequences and reconstructed using complex difference (CD) and MICSR for (A) volunteer 1, (B) volunteer 2, and (C) volunteer 3. Each volunteer has a bSSFP image as reference. The displayed images correspond to the end-systolic cardiac phase. The discrepancies in the trigger delay times are due to the difference in the duration of the preparation pulses and the cardiac cycle. The red arrows show the places where the grid is distorted by the presence of epicardial and subcutaneous fat. The images acquired with ORI-O-CSPAMM did not show any distortion in the places indicated by arrows.

Figure 8 :

 8 Figure 8: Phase of the complex difference (upper row) and MICSR images (bottom row) obtained from (A) CSPAMM, (B) ORI-CSPAMM, (C) O-CSPAMM, and (D) ORI-O-CSPAMM sequences.

Figures captionsFigure 1 :

 1 Figures captions

Figure 2 :

 2 Figure 2: Fat and water masks used for the estimation of the Normalized Mean Signal in (a) ORI-CSPAMM and (b) ORI-O-CSPAMM images.

Figure 3 :

 3 Figure 3: Water and fat phantom images obtained using complex difference (CD. Upper row) and MICSR (bottom row). The images were acquired using (A) bSSFP, (B) CSPAMM, (C) ORI-CSPAMM, (D) O-CSPAMM, and (E) ORI-O-CSPAMM sequences. The trigger delay of each image is shown in the figures and varies due to the different duration of the preparation pulses. The images acquired without ORI preparation showed a shift in the tagging pattern at the water-fat interface. The MICSR image obtained from O-CSPAMM lost the grid pattern as predicted in Eq. 3d.

Figure 4 :

 4 Figure 4: k-spaces of the (A) first complementary image acquired by each sequence and (B) the complex difference (CD) reconstructions. High-frequency spectral peaks are present on all the images in (A) although are less visible with ORI-O-CSPAMM (see red arrows). In the complex difference images, the most energetic high-frequency peaks are completely removed with all the sequences but not with O-CSPAMM (see red arrows in (B)), which generate distortions in the water part of the phantom image (see Figure3). Although 45° rotated and weaker gradients were applied using ORI-O-CSPAMM, the same encoding frequency (tag period) was achieved compared to the other sequences (see blue vertical arrows in (B)).

Figure 5 :

 5 Figure 5: Normalized mean signal in the fat (A) and water (B) obtained from images reconstructed using complex difference (CD) and MICSR, from data acquired using ORI-CSPAMM and ORI-O-CSPAMM sequences. The normalized signal from an ORI-CSPAMM acquisition is shown using a blue and red continuous line respectively, while curves obtained from an ORI-O-CSPAMM acquisition are displayed using blue and red square markers.

Figure 6 :

 6 Figure 6: Images acquired using the O-CSPAMM (second column) and ORI-O-CSPAMM (third column) sequences and reconstructed using complex difference (CD) and MICSR for (A) volunteer 1, (B) volunteer 2, and (C) volunteer 3. Each volunteer has a bSSFP image as reference. The displayed images correspond to the end-diastolic cardiac phase. The discrepancies in the trigger delay times are due to the difference in the duration of the preparation pulses. The red arrows show the places where the grid is distorted by the presence of epicardial and subcutaneous fat. The images acquired with ORI-O-CSPAMM did not show any distortion in the places indicated by arrows.

Figure 7 :

 7 Figure 7: Images acquired using the O-CSPAMM (second column) and ORI-O-CSPAMM (third column) sequences and reconstructed using complex difference (CD) and MICSR for (A) volunteer 1, (B) volunteer 2, and (C) volunteer 3. Each volunteer has a bSSFP image as reference. The displayed images correspond to the end-systolic cardiac phase. The discrepancies in the trigger delay times are due to the difference in the duration of the preparation pulses and the cardiac cycle. The red arrows show the places where the grid is distorted by the presence of epicardial and subcutaneous fat. The images acquired with ORI-O-CSPAMM did not show any distortion in the places indicated by arrows.

Figure 8 :

 8 Figure 8: Phase of the complex difference (upper row) and MICSR images (bottom row) obtained from (A) CSPAMM, (B) ORI-CSPAMM, (C) O-CSPAMM, and (D) ORI-O-CSPAMM sequences. In complex difference images the phase is always non-zero while in MICSR images the phase is zero and (the last is due that MICSR images have only real part that varies from positive to negative values).

Table 1 :

 1 Imaging

		Phantom	Volunteers
	ETL (TFE
		5	5
	Factor)
	Acq. Matrix	160 × 120	160 × 75
	Recon. Matrix	160 × 160	160 × 160
	FOV (mm 2 )	175 × 175	260 × 260
	Tag-period
		17.5	17.5
	(mm)
	Slice thickness
		8	8
	(mm)
	FA	10°	10°
	Cardiac phases	21	23, 24, 31
	TR/TE (ms)	7.0/3.4	5.3/2.6

parameters used during the acquisition of the in-silico and in-vivo data. All the volunteers shared the same imaging parameters, only differing in the number of cardiac phases.

ACKNOWLEDGMENTS

The authors thankfully acknowledge the financial support of the ANID Ph. D. Scholarship 21170592 as well as the project ANID-FONDECYT 1181057 and the ANID-Millennium Science Initiative Program -NCN17_129.


Zhila Amini
email: zhilaaminirs@gmail.com

Mohammad Mohammadamini
email: mohammad.mohammadamini@univ-avignon.fr

Hawre Hosseini
email: hawre.hosseini@ryerson.ca

Mehran Mansouri
email: mehranmansouri9191@gmail.com

Daban Q Jaff
email: daban.jaff@koyauniversity.org

CENTRAL KURDISH MACHINE TRANSLATION: FIRST LARGE SCALE PARALLEL CORPUS AND EXPERIMENTS

Keywords: CCS CONCEPTS, Computing methodologies, Artificial intelligence, Natural language processing, Machine translation Parallel corpus, Central Kurdish, Neural machine translation

While the computational processing of Kurdish has experienced a relative increase, the machine translation of this language seems to be lacking a considerable body of scientific work. This is in part due to the lack of resources especially curated for this task. In this paper, we present the first large scale parallel corpus of Central Kurdish-English, Awta, containing 229,222 pairs of manually aligned translations. Our corpus is collected from different text genres and domains in an attempt to build more robust and real-world applications of machine translation. We make a portion of this corpus publicly available in order to foster research in this area. Further, we build several neural machine translation models in order to benchmark the task o f Kurdish machine translation. Additionally, we perform extensive experimental analysis of results in order to identify the major challenges that Central Kurdish machine translation faces. These challenges include language-dependent and -independent ones as categorized in this paper, the first group of which are aware of Central Kurdish linguistic properties on different morphological, syntactic and semantic levels. Our best performing systems achieve 22.72 and 16.81 in BLEU score for Ku→EN and En→Ku, respectively.

INTRODUCTION

Existence of corpora, especially parallel ones, is crucial for the purpose of machine translation. Such resources are useful in the transition from rule-based and dictionary-based machine translation to statistical and neural approaches to this task which are less language-dependent [START_REF] Koehn | Statistical machine translation[END_REF][13] [START_REF] Klein | Opennmt: Neural machine translation toolkit[END_REF]. The need for such corpora is even more dire in the case of languages which have not benefited from NLP practitioners and researchers developing and formalizing linguistically inspired rules and heuristics. Despite having an abundant number of speakers, Kurdish language still remains a low resource language which has not been subject to extensive computational processing. This is in part due to the variety in its dialects; however, the main reason might be the fact that Kurdish is not the official language of states (except for Iraq, only recently). This has resulted in a lack of funding and/or initiative for NLP research [START_REF] Veisi | Toward Kurdish language processing: Experiments in collecting and processing the AsoSoft text corpus[END_REF]. Recently, there have been attempts by NLP researchers to create resources as well as to perform NLP research on this language [START_REF] Veisi | Toward Kurdish language processing: Experiments in collecting and processing the AsoSoft text corpus[END_REF] [START_REF] Veisi | Jira: a Kurdish Speech Recognition System Designing and Building Speech Corpus and Pronunciation Lexicon[END_REF][1] [START_REF] Esmaili | Towards kurdish information retrieval[END_REF]. However, to the best of our knowledge, there is no relatively large-scale parallel corpus for any dialect of this language. The only parallel corpus for Central Kurdish-English is that of Ahmadi et al. [START_REF] Ahmadi | Leveraging Multilingual News Websites for Building a Kurdish Parallel Corpus[END_REF]. In this work, along with two other parallel corpora, a parallel corpus of English-Central Kurdish that only contains 650 translation pairs is presented. This has resulted in a lack of significant research on Kurdish NLP in general and Kurdish machine translation, in particular.

The objectives of this paper are two-fold: (1) constructing the first relatively large-scale parallel corpus for Central Kurdish machine translation; and, (2) endeavoring to identify the major challenges that Kurdish machine translation faces. Therefore, we construct the Awta1 corpus containing various genres of texts from different domains. This corpus contains 229,222 sentence pairs and 2.1 M and 2.2 M tokens in the Kurdish and English corpora, respectively. Statistics of the corpus are elaborated on in Section 3. In order to foster research for Central Kurdish machine translation, we publicly share a portion of the Awta corpus containing 100 K translation pairs, randomly chosen while respecting the topic ratio of our corpus. This sample and other resources can be found at the project's web page 2 . In addressing the second objective, we perform experiments in order to benchmark the task of machine translation for Central Kurdish. We build various neural machine translation models with our data and using its different domain-based subset and evaluate the obtained results to extract insights. Our best performing models achieve 22.72 and 16.81 in BLEU score for Ku→En and En→Ku, respectively. Additionally, we design experiments in order to identify the challenges that Central Kurdish machine translation faces as related to its linguistic, inherent properties. Such challenges are observed on morphological, syntactic and semantic levels. In doing so, we perform a comprehensive error analysis of our system's output and provide linguistically inspired details for each. In short, the major challenges that Central Kurdish faces include data sparsity and agglutinative nature of the language. There are other sources of error based on the BLEU score as a metric; such errors do not result in a wrong translation, yet decrease performance statistics. The contributions of this work can be enumerated as follows:

(1) We propose the first relatively large-scale parallel corpus for Central Kurdish-English;

(2) We carefully categorize corpus data into text genres and domains;

(3) Various models are built for Central Kurdish machine translation and detailed statistics are provided; and, (4) We perform an explanatory error analysis of our system in order to shed light on nuance of Kurdish machine translation. The rest of this paper is organized as follows. In section 2, we draw upon the relevant body of knowledge to our study. In Section 3, the corpus building process as well as the methodology for building models is elaborated on. This is followed by the evaluation of the systems and analysis of the obtained results in Section 4. In Section 5, we provide an in-depth error analysis of our systems. We conclude our paper by identifying future directions of work.

PRIOR ART

Relevant literature to this work falls into two major categories. The first includes works that attempt to build corpora for machine translation, especially more recent attempts and in particular corpora for low resource languages. These works are particularly important as they contain insights into building proper corpora that enable research as well as real world applications of machine translation. The second category encompasses works that focus on Kurdish MT.

Parallel corpora have been developed for many languages over the past decades. The most recent examples of corpora that are closely related to our work and/or widely used in the literature are Tian et al. [START_REF] Tian | UM-Corpus: A Large English-Chinese Parallel Corpus for Statistical Machine Translation[END_REF], Hikaridai et al. [START_REF] Utiyama | A Japanese-English patent parallel corpus[END_REF] and Toshiaki Nakazawa et al. [START_REF] Nakazawa | Aspec: Asian scientific paper excerpt corpus[END_REF]. These parallel corpora contain 15 M, 2 M and 3 M sentence pairs, respectively. The work by Nakazawa et al. [START_REF] Nakazawa | Aspec: Asian scientific paper excerpt corpus[END_REF] describes the first large-size parallel corpus of scientific domain in three languages (Japanese, Chinese and English) including 8 scientific fields. Scientific fields include Medicine, Information, Biology, Environmentology, Chemistry, Materials, Agriculture, and Energy. Another example is the corpus presented by Eisels et al [START_REF] Eisele | MultiUN: A Multilingual Corpus from United Nation Documents[END_REF] which is available in 6 official UN languages. The data has been collected from the ODS website of the United Nations and it consists of ∼81 M sentences in total with the average of 326 M tokens for five out of six official languages. The work by Tian et al. [START_REF] Tian | UM-Corpus: A Large English-Chinese Parallel Corpus for Statistical Machine Translation[END_REF] is particularly of interest to us as it uses resources of different genres in order to construct a balanced Chinese-English parallel corpus. Genres include News, Spoken, Laws, Thesis, Education, Science, Subtitle, and Microblog. This corpus, denoted UM-Corpus, contains more than 15 M parallel sentences, a part of which including 2 M pairs has been made publicly available. More importantly, for low resource languages, there have been attempts to build parallel corpora and machine translation systems in recent years [START_REF] Ahmadi | Leveraging Multilingual News Websites for Building a Kurdish Parallel Corpus[END_REF] [START_REF] Ezeani | Igbo-english machine translation: An evaluation benchmark[END_REF]. The work by Choudhary et al. [START_REF] Choudhary | Neural Machine Translation for Low-Resourced Indian Languages[END_REF] builds several parallel corpora containing sentence pairs between English and such other low resource Indian languages as Tamil, Malayalam, Telugu, Bengali and Urdu. Their corpus contains the following number of sentence pairs for each of those languages, respectively: ∼187 K, ∼554 K, ∼83 K, ∼665 K and ∼41 K. Authors in this work introduce the agglutinative nature of those languages and OOV tokens as major challenges of their neural machine translation system. Their system manages to outperform Google translator significantly for Tamil and Malayalam. In the work by Rayson et al. [START_REF] Ezeani | Igbo-english machine translation: An evaluation benchmark[END_REF], a benchmark evaluation dataset that contains about 10 K Igbo-English sentence pairs is created. Igbo is one of the largest languages of West Africa, spoken by over 50 million people globally. The corpus is mostly extracted from news Domain. In this work no machine translation model has been built. In the work by Duygu Ataman [START_REF] Ataman | Bianet: A parallel news corpus in turkish, kurdish and english[END_REF], a parallel corpus of Northern Kurdish, Turkish and English containing content from news domain is presented. Number of sentences in Turkish-English, English-Kurdish and Turkish-Kurdish corpora are nearly 35 K, 6.5 K and 7.4 K, respectively. To evaluate the quality of the collected corpora, bilingual and multilingual NMT systems are trained. The BLEU scores of bilingual English-Kurdish and English-Turkish models are 5.41 and 11.5, respectively. Most related to our work are works on Central Kurdish machine translation. There have been very few studies in the field of Kurdish MT due to lack of parallel corpora. The only published or reviewed attempts are Kaka-Khan [START_REF] Kaka-Khan | English to Kurdish Rule-based Machine Translation System[END_REF] and inKurdish 3 , and most recently Ahamdi and Masoud [START_REF] Ahmadi | Towards Finite-State Morphology of Kurdish[END_REF] as well as Ahmadi et al. [START_REF] Ahmadi | Leveraging Multilingual News Websites for Building a Kurdish Parallel Corpus[END_REF]. None of these attempts prepare parallel corpora of significant size curated especially for the task of machine translation. The only work on building Kurdish parallel corpora is that of Ahmadi et al. [START_REF] Ahmadi | Leveraging Multilingual News Websites for Building a Kurdish Parallel Corpus[END_REF]. Authors build a corpus of 12,372 pairs between two Kurdish dialects of Central Kurdish (Sorani) and Northern Kurdish (Kurmanji) alongside a small corpus of 1,797 and 650 translation pairs of English-Northern Kurdish and English-Central Kurdish, respectively. As this is the first attempt to build an English-Central Kurdish corpus, we review this work in more depth. The average number of tokens in each sentence is 17 to 20. A statistical MT model has been developed in order to test and evaluate the corpus, where 10% of the corpus has been chosen randomly in order to be used as a test set. The BLUE score of the statistical machine translation for Central Kurdish-English, Central Kurdish-Northern Kurdish, and Northern Kurdish-English corpus are 17.74, 17.08, and 11.06, respectively. In [START_REF] Ezeani | Igbo-english machine translation: An evaluation benchmark[END_REF], Kaka-Khan provides such tools and resources as morphological dictionary and bilingual dictionaries to develop a rule-based MT Kurdish-English MT system. This system is developed based on the open-source MT framework, Apertium, developed by Forcada et al. [START_REF] Esmaili | Towards kurdish information retrieval[END_REF]. The inKurdish MT system, as reviewed by Kaka-Khan and Taher [START_REF] Qi | When and why are pre-trained word embeddings useful for neural machine translation[END_REF], is a dictionary-based MT system, reportedly the first to offer online translation services. However, this system performs very poorly in dealing with such linguistically complex forms as long sentences, proverbs and idioms. Lastly, Ahmadi and Masoud [START_REF] Ahmadi | Towards Finite-State Morphology of Kurdish[END_REF] describe three available Central Kurdish-English domain-specific parallel corpora that are available online though not especially curated for the task of machine translation. They develop two neural machine translation models with different hyper parameters to report the challenges of MT for Central Kurdish.

The available and used parallel corpora are Tanzil Corpus with 92,354 sentence pairs, TED Talks with 2,358 parallel sentences, and Kurd-Net, a lexical-semantic resource with 4,663 definitions. This work uses in-domain data for testing purposes. Additionally, the relatively limited number of translation pairs can result in less generalizability.

Our work extends the current literature in several ways. First and foremost, we provide the first relatively largescale Central Kurdish-English parallel corpus, the Awta corpus, with 229,222 pairs. This corpus is nearly 353 times as large as the existing corpus [START_REF] Ahmadi | Leveraging Multilingual News Websites for Building a Kurdish Parallel Corpus[END_REF]. Secondly, we build various models and evaluate the model performances extensively. In doing so, we provide qualitative analysis of our NMT systems drawing insights with respect to language-specific properties of Central Kurdish which can be considered for building more robust MT systems.

PARALLEL CORPUS

In this section, we elaborate on the collection and processing of the Awta parallel corpus. We endeavor to relieve some of the known problems of Central Kurdish digital content, as elaborated on in the following. Additionally, the corpus statistics is presented in detail.

Data Source Gathering

The Central Kurdish-English parallel corpus was constructed from various resources covering the following domains: ∼141 K sentence pairs of TED Talks subtitles collected from the web 4 , ∼15 K sentence pairs extracted from digital books with four different genres after getting permission from authors, and ∼73 K sentence pairs gathered from mixed sources, with domains including academic content (Table 1). Our book data includes Biography, Politics, Literature and Philosophy with ∼7 K, ∼6 K, ∼1.5 K and ∼0.3 K pairs, respectively. TED Talks have the minimum and books have the maximum average token per line in both Kurdish and English corpora, with 7.24 and 15.53 in the Kurdish corpus and 7.89 and 16.28 in the English corpus, respectively. The final corpus has the average of 12.11 tokens per line in the Kurdish corpus, and 12.55 tokens in the English corpus. The vocabulary size in the Kurdish corpus is about 200 K words which is almost 130 K words more than the vocabulary size in the English. Table 2 shows the general specifications of the parallel corpus. The finalized Kurdish Parallel Corpus consists of about 230 K sentence pairs and over 2 M tokens.

Content Alignment

In this section, we discuss the alignment process of the Awta corpus and the major challenges we have faced in doing so, including the various solutions and steps we acquired to align files with different formats. Since the corpus raw data has been collected from diverse sources with different formats, the alignment process of each domain of resources was different. The alignment process has been a combination of automatic alignment at paragraph and sentence level where possible followed by a manual review and correction by human annotators. We exploited InterText [START_REF] Vondricka | Aligning parallel texts with InterText[END_REF] for the manual alignment. Intertext is a parallel text alignment editor for building bilingual sentence pairs, providing various editing tools and functions such as splitting and merging aligned elements and editing and re-positioning elements. Here, we present the alignment process in more detail. The alignment process of books involved three main steps. First, paragraphs were aligned one-to-one manually. Second, automatic sentence alignment was applied on each paragraph. Lastly, we checked on the aligned corpus in the InterText one more time to make sure it is all aligned in a one-to-one level. The TED Talks were mostly aligned automatically followed by a review and manual correction of errors by human annotators. There have been many errors arising from non-matching time information. Human annotators have rectified all such instances manually. With respect to the mixed data sources, we first removed all the special tags and also empty lines or lines with no translation. And then, we performed automatic sentence alignment of the content. Finally, we converted all the aligned datasets into plain text and combined them.

Text Normalization and Preprocessing

Normalization is an essential step in order to prepare our corpus for later preprocessing. This is different from model specific preprocessing of textual content that is purposefully done in order to achieve better results. This normalization is to relieve the challenges that Central Kurdish textual (particularly digital) content faces generally. Such challenges are mainly due to the non-standardized typography. We resolved several issues during the normalization procedure of our Kurdish corpus. Firstly, we standardized and unified the script based on widely accepted Unicode codes for Central Kurdish Arabic-based script [3][24]. This step is important as a great portion of the Kurdish corpus contents were written using non-Unicode Kurdish keyboards or Unicode keyboards that use non-Kurdish Unicode characters. Secondly, due to the Central Kurdish typography similarities to Persian and Arabic, non-Kurdish forms of characters happen in the text. As an instance, the character ك and ک both have the same sound which is /k/, whilst the character ك is Arabic and ک is the correct form of the Kurdish character. The Arabic ي which resembles the Kurdish ی is another instance. We unified all such instances. On the phoneme level, the phonemes /r/ and /rr/ as well as /l/ and /ll/ look very similar, distinguished only by a special accent under and above such characters, respectively. The writing forms are as follows: /r/ ,'ر' /rr/ ,'ڕ' /l/ ,'ل' and /ll/ .'ڵ' These phonemes are incorrectly interchangeably used in Kurdish writing.

In order to deal with the aforementioned challenges, we use AsoSoft normalizer [START_REF] Mahmudi | Automated Kurdish Text Normalization[END_REF] which is a very useful tool for normalizing Central Kurdish text.

In what follows, we review the preprocessing steps we have performed before building models. Diversity of writing forms in Central Kurdish is a major challenge that we have to deal with in the preprocessing step. The Central Kurdish language has a non-standardized writing form causing lexical variations based on scripting guidelines as well as subdialect-based variations. The first category of variations happen since there is not a unified set of rules as to how words are written in their different morphological forms. For instance, the verb دامانگرتن 'we downloaded them' can be written as گرتن دامان or .دامانگرتن Additionally, another set of lexical variations happen due to subdialect-based differences in pronunciation as well as formal and informal writing forms. For example, words ناشکێت and ناشکێ both mean 'it won't break'; however, the first form has a ت attached to the end of it and usually happens in formal text. Another example is with regards to the imperfective aspect in Central Kurdish, whose formal and informal forms are different. For instance, the word 'should' can be written as ئەبێ and ,دەبێت the latter of which is the formal form. This difference can occur in different sub-dialects of Central Kurdish. These words can be replaced by one unique form of the word. Finally, named entities can be written in many different forms since the Central Kurdish is a phonemic language and writing is correspondent to how words are pronounced. We unify instances of such named entities. Further, we resolve the issue of conjunctive و in Central Kurdish [START_REF] Veisi | Toward Kurdish language processing: Experiments in collecting and processing the AsoSoft text corpus[END_REF]. The conjunctive و is an independent Kurdish word which means 'and' in English. It should be written separately, however sometimes the writers join it to the previous word without any white space in between. That is against Kurdish typography rules. For instance, in پیاوان ژنانو 'men and women', the conjunctive و follows the previous word ,ژنان while it should be written as پیاوان و .ژنان We used AsoSoft Correction Table [START_REF] Veisi | Jira: a Kurdish Speech Recognition System Designing and Building Speech Corpus and Pronunciation Lexicon[END_REF] with the size of nearly 20,000 pairs of the corrected forms of common errors, extracted from a large text corpus. This has allowed for replacement with the correct and/or a unique spelling of the Kurdish words. Overall, about 92 K words were replaced by their correct font in the Correction Table. و follows the previous word ,ژنان while it should be written as پیاوان و .ژنان We used AsoSoft Correction Table [START_REF] Veisi | Jira: a Kurdish Speech Recognition System Designing and Building Speech Corpus and Pronunciation Lexicon[END_REF] with the size of nearly 20,000 pairs of the corrected forms of common errors, extracted from a large text corpus. This has allowed for replacement with the correct and/or a unique spelling of the Kurdish words. Overall, about 92 𝐾 words were replaced by their correct font in the Correction Table .  Punctuation normalization is the next step. We put spaces before each punctuation except for the apostrophes which are not supposed to be disjoint from the words. We also put white spaces between numbers and words if there was not any, to make sure numbers would be detected automatically. Then, we converted them to words. We also removed all the extra white spaces and the empty lines. Finally, the pairs with more than 50 tokens as well as pairs that are exactly identical on both sides were removed.

EXPERIMENTAL AETUP AND EVALUATION

Models and Metrics

Here, for the sake of reproducibility, we describe the specifications of our train and test sets, model hyperparameters as well as metrics used for evaluation purposes. The final version of the Awta text corpus used for experiments includes 229,222 sentence pairs. We separated 5000 samples for testing and 5000 samples were used for validation. The remaining part is used to train the NMT system. We prepared a second dataset to evaluate our system on out-of-domain data. We collected sentence pairs posted on a social platform consisting of mainly brief explanations of English-Kurdish news articles. The final version of the aforementioned collected test set contains 1000 sentence pairs. For all our models, we employ the RNN Encoder-Decoder architecture, implemented in OpenNMT machine translation library [START_REF] Forcada | Apertium: a free/open-source platform for rule-based machine translation[END_REF]. The architecture used in our experiments has two hidden LSTM layers with 512 neurons in the encoder and the same architecture is used in the decoder. The system was trained with the Adagrad optimization algorithm.

In the case of not sufficient data available for training, using pre-trained embeddings with monolingual text corpus can help the training of the DNN based NMT systems [START_REF] Pouget-Abadie | Overcoming the curse of sentence length for neural machine translation using automatic segmentation[END_REF]. In our experiments we tested both cases: joint training of word embeddings and Encoder Decoders, using pre-trained word embeddings for both source and target languages. On both sides, we used the GloVe word embeddings [START_REF] Pouget-Abadie | Overcoming the curse of sentence length for neural machine translation using automatic segmentation[END_REF]. For English, the vectors were acquired from the web 5 . We trained the Glove embeddings leveraging the AsoSoft text corpus [START_REF] Veisi | Jira: a Kurdish Speech Recognition System Designing and Building Speech Corpus and Pronunciation Lexicon[END_REF]. The AsoSoft text corpus contains 183 M tokens. In the trained embeddings, all unique tokens are included to cover the maximum number of tokens in the machine translation corpus.

In our experiments we use the BLEU (BiLingual Evaluation Understudy) score which is proposed in [START_REF] Papineni | Bleu: a method for automatic evaluation of machine translation[END_REF]. The BLEU metric ranks machine translation sentences by function of same n-grams between the MT translation and the human translation. Because the BLEU score needs the exact matching of words between human and machine translation, for an agglutinative language such as central Kurdish the values of BLEU is lower in comparison to Ku→EN translations. This is discussed in more detail in the qualitative analysis section.

Evaluation

In this section, we present the results obtained by the NMT systems we have built. We build our systems with Kurdish both as target and source language. For such models, we obtain results while varying sentence length, lexicon sizes, embedding dimension sizes, and so forth, in order to draw insights for Kurdish machine translation and help identify error types and reasons, as elaborated on in the next section.

As seen in Table 3, our best models achieve a BLEU of 16.81 for En→Ku translation and 22.72 for Ku→En. We present results obtained with systems where word embeddings are jointly learned with the system as well as with exploitation of pre-trained word embeddings. Pre-trained word embeddings are a common way to improve the performance of NMT systems as they reduce the number of trainable parameters that helps to train the network with a smaller dataset. In our experiments we used Glove word embeddings for both sides (Ku and En). The results show that we have an improvement in terms of BLEU, improving En→Ku performance from 16.16 to 16.81 and Ku→En from 21.6 to 22.72.

As indicated in Table 3, the performance of En→Ku translation is worse than Ku→En in all of the models. One possible reason for this could be the fact that when Kurdish is the target language, the number of OOV is higher in comparison to Ku→En translation. We increased the size of the lexicon from 50 K to 100 K Kurdish language. While the ratio of OOV decreases, the overall performance of our system does not improve. The results for this experiment are presented in Table 4. We believe that this lack of improvement arises from two factors. Firstly, lexicon size increase means a huge increase in trainable parameters. Secondly, for the added lexicon, there are not enough training instances for the system to learn the context. This can be viewed as a trade-off between lexicon size and data-sparsity which can be resolved employing larger parallel corpora.

Further, we investigate our best model's performance on test sets built with varying sentence lengths. We present results of this experiment in Figure 1. As can be seen in the figure, there is a visible pattern where the model's performance increases with increasing sentence length up to a certain value; after reaching the peak performance at the (30, 40] bin with a BLEU of 23.8, the model's performance experiences a downfall almost everywhere. The model performs worst on the test set containing the longest sentences. This is in line with literature indicating that the performance of NMT systems for long sentences decreases [START_REF] Papineni | Bleu: a method for automatic evaluation of machine translation[END_REF]. An interesting observation is that the performance of the models for both En→Ku and Ku→En converges with increasing sentence lengths.

The performance of the MT translation system is closely related to the domain of training data [START_REF] Klein | Opennmt: Neural machine translation toolkit[END_REF]. In another experiment, we tried to evaluate our best model on an out-of-domain test. We collected 1000 En→Ku sentences that came from new stories. The results obtained by our system reduce dramatically in comparison to the indomain test set. We did the same experiment with Microsoft Bing Translator, the only available commercial MT system for the Kurdish language. However, the data used to train Microsoft models is not documented and we don't know if the news data is used in their training data. The results for this experiment are presented in Table 5.

QUALITATIVE ERROR ANALYSIS

Apart from the methodological approaches to machine translation and the challenges due to data sparsity for training such systems, translating between a language pair involves difficulties that have to do with linguistic complexities. The challenges that machine translation systems face can be regarded as language-dependent and -independent ones. Language independent challenges usually involve universal linguistic properties, occurring in almost any language. For instance, which synonym should the system choose for translating a certain token based on the context, if the synonyms have different connotations? On the other hand, translating between languages that have different sentence structures or morphological systems can be challenging, where MT systems can find it difficult to capture these intricacies. In this section, we perform a detailed error analysis of our MT system endeavoring to achieve a better understanding of our system's performance. Also, we aim at recognizing major language-dependent challenges Central Kurdish MT systems face. A summary of such error types is presented in Table 6. As can be seen, we categorize our system's major sources of error into lexical, semantic and syntactic types. Each of these types have some subtypes. While these challenges affect system's performance based on the evaluation metric (here BLEU), sometimes the translated sentence conveys the source sentence's meaning perfectly. We identify such cases where the difference is due to the Kurdish language properties.

Lexical errors consist of those that arise from the Kurdish writing forms practiced by authors. As mentioned earlier, Although Kurdish language academy, writers and publishers have made several attempts to standardize Kurdish language writing, there is yet to be a widely accepted set of regulations. In [23][14], several aspects of Kurdish language are discussed that cause lexical variations. Dialect based variations, loan-words and foreign names are among the common sources of lexical variations that caused errors in the current study. We categorize such errors as follows:

• Writing Regulations: Central Kurdish is an agglutinative language which results in numerous morphological forms. For such a language and considering its Arabic-based script, each morphological form can be written is various ways with regards to joining components of the morphological components. For instance, the word دایانگرت (they downloaded it) can be written as گرت دایان and .دایانگرت While there is not a widely accepted set of regulations, in many cases there are conventional procedures. However, a great body of writers of Central Kurdish do not follow such conventionally accepted set of regulations. Such variations do not harm the meaning, while they result in a lower BLEU score. Post-processing can be done in the pipeline of Central Kurdish MT systems in order to uniform such cases. However, such components require NLP tools which are yet to be developed and widely accessible.

•

Subdialect-based Variation: Due to lack of standardization in writing, words can be pronounced and written differently by speakers of different dialects [START_REF] Mohammadamini | Challenges in Standardization of Kurdish Language: A Corpus based approach[END_REF]. This happens more often in the case of named entities as well as loan-words. For example, foreign named entities are pronounced and written differently by speakers of different dialects. Take 'Switzerland' for an example, which has at least two written forms of سویس and سویسرا in Central Kurdish. It is probable that speakers who write Switherland in those forms have borrowed it from Arabic and Persian, respectively. Another example is the long /u/ versus short /u/; speakers of different regions pronounce words containing such a letter differently. The long /uu/ is written as وو in Kurdish, while the short /u/ should be written as و ; however, majority of Kurdish writers are not aware of this difference. Therefore, errors like the following are abundant: /sudan/ سودان is translated into /suudan/ سوودان by the machine, and while the reader understands it, this affects the performance negatively. Semantic category of error types encompasses those errors that arise from morpho-semantic properties of language and, sometimes, of Kurdish language, specifically.

•

Synonymy: This type of error refers to those where the system outputs a correct synonym of a token instead of our gold standard human translation. Such errors can happen in any language translation system with any given pair of languages. As an example, the word پیاو in the sentence جانتاکەی پیاوەی ئەو بوو پێcan be translated as 'man' and also 'guy'. In our system, a considerable number of errors can be attributed to this challenge.

•

Named Entities: Named entities are among common out of vocabulary (OOV) errors in MT. Automatic transliteration as a post editing technique, can improve the quality of MT systems. The automatic detection of named entities in Central Kurdish is a serious challenge as they cannot be signified by and instead of recognizing the verb in the first person plural کەم مرۆڤایەتی ژانەکانی کە بووە ئەوەمان خەمی ,بکەینەوە the system recognizes it as first person singular ب ۆ مر ئازاری ئەوەی ۆ بکەمەوە کەم ڤەکان .

• Word order: There are many linguistic components whose order of appearance are different than English. Such components include preposition, circumfix, noun head, relative clause, sequence of adjectives, sequence of adverbs and adjectives of degree. The word order flexibility in Kurdish is very high. Besides, in terms of case inflection and verbal inflection, Kurdish has a lot of equipment. Sometimes, the translation system cannot identify correctly the sequence of nouns and adjectives which come together and identifies them conversely and incorrectly. For example, instead of پالندانان ی شاری ,تەندروستی system outputs تەندروست شاری پالندانانی as the translation of 'healthy urban planning'.

•

Izafe: Izafe Is a grammatical particle which connects words or phrases together. In Kurdish, izafe particles occur between the head and its dependent, which can have different categories and functions. For example, head can be nominal, adjectival or adpositinal. Therefore, izafe in kurdish has three types of allomorphs one of which appears based on definiteness and phonology conditions. Our system sometimes cannot identify the izafe marker. For instance, تڕ کاریگەری ۆ ڕابردوو ومای should include the izafe marker ,ی resulting in the correct form تڕ کاریگەریی ۆ ڕابردوو ومای .

CONCLUDING REMARKS AND FUTURE WORK

In this work, we presented the Awta Central Kurdish-English parallel corpus containing 229,222 translation pairs. The Awta corpus contains content from several various genres. We publicly share 100 K translation pairs in an attempt to foster research in this field. We also designed and performed experiments in order to understand the intricacies of Central Kurdish machine translation. In doing so, we performed extensive exploratory analysis of errors made by our system. Future work can encompass several lines of work including the following. Firstly, a larger corpus including more genres as well as translation pairs would be helpful in creating more robust MT systems. This will provide resources that are more suitable for drawing more reliable insights. Moreover, the challenges outlined in this paper can be subject of future research for development of better performing systems. Lastly, evaluation metrics can be explored in order to determine the most suitable ones for evaluation of Kurdish MT systems.

Figure 1 .

 1 Figure 1. BLEU results based on sentence length

Table 1 .

 1 Token number of raw data sources categorized by source type and their topics

	TED	Politics Literature Biography Philosophy Scientific Mixed	All
	Number of Pairs 141,024 6,057	1,570	7,082	311	6,510	66,668 229,222

Table 2 .

 2 General specifications of the Awta parallel corpus

			Kurdish			English
		TED	Books	Mixed	All	TED	Books	Mixed	All
	Number Of pairs	141,024	15,020	73,178	229,222	141,024	15,020	73,178	229,222
	Number of Tokens	1,021,036 241,682 866,590 2,129,308 1,113,449 253,714 846,978 2,214,141
	Vocabulary size	100,816	46,062	71,839	218,717	32,475	24,004	34,347	90,826
	Average token per	7.27	15.53	9.06	12.11	7.89	16.28	9.04	12.55
	pair

Table 3 .

 3 Model performance

	Joint Training GLOVE-100 GLOVE-200
	En→Ku 16.16	16.3	16.81
	En→Ku 21.6	21.75	22.72

Table 4 .

 4 The size of lexicon

	Size	OOV BLUE
	50k	6%	16.16
	100k 3%	15.83

Table 5 .

 5 Comparison to Microsoft Bing translator

	Our best model Microsoft Bing
	En→Ku 4.79	7.4
	En→Ku 6.82	13.59

Awta in central Kurdish means 'synonym' or 'equal'

https://github.com/mihemmed/Kurdish-Machine-Translation-Project-KMTP-1

https://www.inkurdish.com/

https://amara.org/en/

https://nlp.stanford.edu/projects/glove/

ACKNOWLEDGMENTS

We would like to thank the following individuals for providing us with resources or advice throughout the composition of the paper: Kourosh Abdi, Dr. Alan Dilani, Aso Mahmudi, Dr. Manijeh Mirmokri, Abdulkhaleq Yaqubi, Davoud Osmanzadeh, Shafiq Haji Khedr, Kosar Abdulla, Huma Hiwa, and Halo Fariq.

uppercase letters similar to English language. Therefore, the integration of NER systems with NMTs can help to improve the quality of En→Ku machine MT systems. Lastly, the syntactic type of errors includes those which arise from Kurdish language syntactic properties such as sentence structure, inflections, clitics and so forth. Such syntactic properties which can affect the MT system's performance drastically are described in the following.

•

Prodropness: Kurdish is one of the prodrop languages in which subjects can be eliminated in independent and subordinate clauses, and the information about person and number of this subject pronoun, can be represented through agreement marker in verbs. For instance, 'we need to' in the sentence 'we need to compensate for the fluid loss' can be translated as دەبێت .ئێمە However, it also can be translated as دەبێت in which the subject ئێمە is dropped. The person information is added as an inflectional affix to the verb.

•

Agreement: Subject Agreement in transitive verbs which are made from past stem is fulfilled through enclitic. Such an agreement is fulfilled via a clitic, representing the subject, added to the object.

Additionally, the verb represents the person and number in Kurdish. Sometimes the system cannot capture these agreement structures. As an instance, the system cannot identify the number of subjects


Stevo Todorcevic

COLOURING FINITE PRODUCTS

Keywords: MSC 2020 Primary 03E02, 03E10, 05D10 colourings, products, ρ-functions

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

It is well known that if X 1 , X 2 , ..., X n is a finite sequence of countable infinite sets then there is a colouring of their product n i=1 X i with n! colours each of which shows up in any subproduct n i=1 Y i with Y i ⊆ X i are infinite. For example, letting X i = N for all i and colouring a given one-to-one sequence (k 1 , k 2 , ..., k n ) of integers by the permutation σ of {1, 2, ..., n} such that σ(i) < σ(j) is equivalent to k i < k j for all i < j, it is clear that all permutations show up in any n-product of infinite subsets of N. On the other hand, a simple application of Ramsey's theorem shows that for every finite colouring of n i=1 X i there exist infinite Y i ⊆ X i such that the subproduct n i=1 Y i uses no more than n! colours. In this note we investigate this phenomenon in the case when some of the sets X i are uncountable. The following is an interpretation of a result of R. Laver (see page 31 of [START_REF] Erdős | Unsolved problems in set theory[END_REF]) showing that in this case the critical number n! drops to (n -1)!.

1.1 Theorem (Laver). Suppose X 1 , X 2 , ..., X n is a finite sequence of infinite sets with at least one of them uncountable. Then for every finite colouring of n i=1 X i there exist infinite Y i ⊆ X i (i = 1, 2, ..., n) such that the subproduct uses no more than (n -1)! colours.

Here, we supplement this result by proving the following.

1.2 Theorem. Let Ω denote the set of countable ordinals and let n be a positive integer. Then there is a finite colouring of Ω n which has at least (n -1)! colours on any subproduct

n i=1 Y i with Y i ⊆ Ω infinite.
The case n = 3 of Theorem 1.2 (see page 108 of [START_REF] Williams | Combinatorial set theory[END_REF]) is an unpublished result of K. Prikry and C. Mills but, as we shall see from the analysis below, the higher dimensional case is a bit more challenging.

An operation on the set Ω of countable ordinals

We start this section by listing some properties of the mapping 1 ρ : Ω 2 → ω which can be found in Section 3.2 of [START_REF] Todorcevic | Walks on ordinals and their characteristics[END_REF]. In order to simplify the notation, we write αβ instead of ρ(αβ) and ξ ∨ η instead of max{ξ, η}. From now on we analyze the behaviour of this operation on infinite subsets A, B, C, D, ... of Ω of order-type ω which we enumerate increasingly as (α i ), (β i ), (γ i ), (δ i ), ..., respectively.

2.2 Lemma. By refining A and B, we may assume that either for every i the sequence (α i β k ) k>i is constant, or for every i the sequence (α i β k ) k>i is strictly increasing. Moreover, if for every i the sequence (α i β k ) k>i is constant then for i < j the constant value of (α i β k ) k>i is strictly smaller than the constant value of (α j β k ) k>j .

Proof. Note that if sup(A) > sup(B) the conclusion follows easily from Lemma 2.1 (1) (giving us refinement with the property that (α i β k ) k>i is strictly increasing for all i), so we may assume that sup(A) ≤ sup(B). Colouring a triple i < k < l by three colours according whether α i β k is smaller, equal, or larger than α i β l and applying the Ramsey theorem to refine A and B, we may assume that for all i < k < l exactly one of the following three possibilities happen,

α i β k < α i β l , α i β k = α i β l , or α i β k > α i β l .
Since α i β k > α i β l cannot hold for all i < k < l, we are left with the first two possibilities which is exactly the conclusion of the first sentence of the lemma. Towards the conclusion of the second sentence, we assume that α i β k = α i β l holds for all i < k < l and apply the Ramsey theorem again to refine further and get that for all i < j < k, exactly one of the following three possibilities happen,

α i β k < α j β k , α i β k = α j β k , or α i β k > α j β k .
Since the conclusion of the second sentence is equivalent to the first possibility, we have to eliminate the other two. Note that α i β k = α j β k contradicts the property (1) of Lemma 2.1, so towards a contradiction let us assume that we have

α i β k > α j β k for all i < j < k. Let n 0 be the constant value of the sequence (α 0 β k ) k>0 . Fix a k > n 0 + 2. Then α j β k (0 < j < k) is a sequence of distinct integers below n 0 , a contradiction.
Note that the proof of the second sentence of Lemma 2.2 also shows the following 2.3 Lemma. Assume that for some A, B, C with sup(A) ≤ sup(B) ≤ sup(C), we have that for every i the sequences (α i γ k ) k>i and (β i γ k ) k>i are constant. Then by refining, we may assume that for i < j the constant value of (α i γ k ) k>i is strictly smaller than the constant value of (β j γ k ) k>j .

2.4 Lemma. Suppose that sup(A) ≤ sup(B) ≤ sup(C). Then by refining the sets, we may assume that α i γ k < β j γ k for all i < j < k.

Proof. By refining the three sets we assume that they satisfy the conclusion of Lemma 2.3, and moreover, that each of the pairs (A, B), (A, C) and (B, C) satisfies the conclusion of Lemma 2.2. Suppose towards contradiction that the refinement of the Lemma does not exist. Then applying Ramsey's theorem, we can find a refinement such that α i γ k > β j γ k for all i < j < Our assumption sup(A) ≤ sup(B) ≤ sup(C) and a further refinement of these three sets allow us to assume that the enumerations (α i ), (β i ), (γ i ) of these sets have the property that α i ≤ β i ≤ γ i for all i. So, in particular i < j implies α i < β j , so the properties ( 2) and (3) of Lemma 2.1, give us

α i β j ≤ α i γ k ∨ β j γ k = α i γ k ,
and

α i γ k ≤ α i β j ∨ β j γ k
Note that since α i γ k > β j γ k , from the last inequality, we conclude that

α i β j ∨ β j γ k = α i β j .
Combining the two inequalities, we conclude that

α i β j = α i γ k for all i < j < k.
It follows, in particular, that for every i, the sequences (α i γ k ) k>i and (α i β k ) k>i are constant with the same constant values. Note that by our assumption β j γ k < α i γ k for all i < j < k, we conclude that for every j the sequence (β j γ k ) k>j is also constant and its constant value is bounded by the constant value of the sequence (α i γ k ) k for any i < j. This contradicts Lemma 2.3 2.5 Lemma. Suppose that for some A, B, C with sup(A) ≤ sup(B) ≤ sup(C), we have that α j γ k < β i γ k for all i < j < k. Suppose that A is an infinite set with sup(A ) ≤ sup(A). Then these sets can be refined in such a way such that α j γ k < β i γ k for all i < j < k.

Proof. Suppose that such refinements cannot be found. Applying Ramsey's theorem, we may assume that α j γ k > β i γ k for all i < j < k. Applying Lemma 2.4 to A , A and C and going to refinements, we may assume that α i γ k < α j γ k for all i < j < k. So, for every i < j -1 < j < k, we have

α j-1 γ k < α j γ k < β i γ k .
It follows that α j-1 γ k < β i γ k , contradicting our assumption that α j γ k > β i γ k for all i < j < k .

2.6 Lemma. Suppose that for some A, B, C with sup(A) ≤ sup(B) ≤ sup(C), we have that α j γ k < β i γ k for all i < j < k. Let B be an infinite set such that sup(B) ≤ sup(B ) ≤ sup(C). Then these sets can be refined in such a way that α j γ k < β i γ k for all i < j < k.

Proof. Applying Lemma 2.4 to B, B and C, by refining the sets, we may assume that β i γ k < β j γ k for all i < j < k. Combining this with the assumption of the Lemma we that α j γ k < β i γ k < β i+1 γ k for all i < i + 1 < j < k. It follows that the triple i + 1 < j < k satisfies the conclusion of the Lemma. Since such triple can be found in any refinement of these sets, an application of Ramsey's theorem will give us refinements satisfying the conclusion of the Lemma.

2.7 Lemma. Suppose that for some A, B, C with sup(A) ≤ sup(B) ≤ sup(C), we have that α j γ k < β i γ k for all i < j < k. Then the sets can be refined in such way that for every i the sequence (β i γ k ) k>i is strictly increasing.

Proof. We assume that the sets have already been refined in such way that for every i, the sequence (β i γ k ) k>i is either constant or strictly increasing. So suppose that for all i the sequence (β i γ k ) k>i is constant. Fix i. Let l be the constant value of the sequence (β i γ k ) k>i . Choose k > l + i + 1. Then by the assumption of the Lemma α j γ k < l for all i < j < k. So there must be i < j < j < k such that α j γ k = α j γ k , contradicting the property (1) of the operation ξη of Ω.

Conclusion.

A given finite sequence X 1 , X 2 , ..., X n of infinite subsets of Ω can be refined in such a way that for every three sets A, B and C in the refinement with property that sup(A) ≤ sup(B) ≤ sup(C) we have that α i γ k < β j γ k for all i < j < k. If for some A, B and C in the refinement with sup(A) ≤ sup(B) ≤ sup(C) we have that β i γ k > α j γ k for some i < j < k then this holds for all i < j < k. Moreover, if for some A, B and C in the refinement with sup(A) ≤ sup(B) ≤ sup(C) we have that β i γ k > α j γ k holds for all i < j < k, then this is true for A , B and C in place of A, B and C provided that sup(A ) ≤ sup(A) and sup(B) ≤ sup(B ). Moreover, when this happens, the sequence (β i γ k ) k>i is strictly increasing for every i.

Proof of Theorem 1.1

We shall show that for every positive integer n and for every finite colouring c of the product Ω × N n there exist infinite X ⊆ Ω and M ⊆ N such that the range of c on the product X × M n has cardinality at most ((n + 1) -1)! = n!. To prove this, fix a selective ultrafilter U on N. Note that for every ξ ∈ Ω the section c ξ (ξ 1 , ξ 2 , ..., ξ n ) = c(ξ, ξ 1 , ξ 2 , ..., ξ n ) is a finite colouring of N n , so an application of the selective version of Ramsey's theorem (see Chapter 7 of [START_REF]Todorcevic Introduction to Ramsey spaces[END_REF]), we can fix M ξ ∈ U such that the colouring c ξ on the power M n ξ has range F ξ of cardinality at most n!. Find an uncountable set Γ of Ω and a subset F of the range of c such that F ξ = F for all ξ ∈ Γ. Since the directed set [Ω] <ω is not Tukey reducible to U, there is an infinite subset X of Γ such that the set M = ξ∈X M ξ belongs to U. Then the colouring c on the product X × M n has range F whose cardinality is at most n!.

Proof of Theorem 1.2

Fix a positive integer n. We may assume n ≥ 3. Let S n-1 be the permutation group of a set with n -1 elements. Given a sequence (ξ 1 , ξ 2 , ..., ξ n ) of elements of Ω, we let c(ξ 1 , ξ 2 , ..., ξ n ) be the sequence (i,

σ i ) (1 i ≤ n) of elements of n i=1 {i} × S n-1
, where for each i, the permutation σ i codes in the natural way the mapping j → ξ i ξ j from the ordered set {1, ..., i -1, i + 1, ..., n} into the ordered set ω. Let X 1 , X 2 , ..., X n be a sequence of infinite subsets of Ω. We have to show that the range of c on n i=1 X i has cardinality at least (n -1)! Note that we may assume that sup(X i ) ≤ sup(X j ) whenever i < j. We also assume that the sets X i are refined in order to satisfy the Conclusion of the previous section. Let m ≤ n be minimal such that sup(X m ) = sup(X n ).

Case 1. For all A, B, C ∈ {X 1 , ..., X n } with sup(A) ≤ sup(B) ≤ sup(C) and C = X n , we have that α j γ k > β i γ k for all i < j < k. Let ξ n be the nth element of X n according to the increasing enumeration. Let σ be a given permutation of the set {1, 2, ..., n -1} viewed as bijection from this set into itself. For 1 ≤ i < n, let ξ i be the σ(i)th element of the set X i according to the increasing enumeration of this set. Then the nth term of the sequence c(ξ 1 , ξ 2 , ...., ξ n ) is equal to (n, σ). Since there are (n -1)! such σ's, we are done.

Case 2. There exist A, B, C ∈ {X 1 , ..., X n } with sup(A) ≤ sup(B) ≤ sup(C) and C = X n such that α j γ k < β i γ k for all i < j < k. 2 Note that by Lemma 2.4 the set A cannot be in {X m , ..., X n }, so if we let ξ n be the first element of X n , then from the Conclusion of previous section, we know that for every m ≤ i ≤ n the map ξ → ξξ n is strictly increasing on X i \ {min(X i )}. Moreover, note that by the property (1) of the operation and the Conclusion, this map is strictly increasing on X i \ {min(X i )} also for 1 ≤ i < m. So it is clear that for every permutation σ of {1, 2, ..., n -1} we can find ξ i ∈ X i (1 ≤ i < n) such that σ(i) < σ(j) is equivalent to ξ i ξ n < ξ j ξ n for all 1 ≤ i < j < n. It follows that the nth term of the sequence c(ξ 1 , ξ 2 , ...., ξ n ) is equal to (n, σ). So, as before, this shows that the range of c on n i=1 X i has cardinality at least (n -1)! and we are done also in this case. 4.1 Remark. As we have indicated in the Introduction there is indeed difference between the case n = 3 and the case when n is large. In this case a given triple (ξ 1 , ξ 2 , ξ 3 ) is coloured by the permutation σ of the two-element set I = {1, 2, 3} \ {k} where k ∈ {1, 2, 3} is such that ξ k is the maximal ordinal in the sequence (ξ 1 , ξ 2 , ξ 3 ) , or more precisely, σ(i) < σ(j) is equivalent to ξ i ξ k < ξ j ξ k for i < j in I. Then it is clear from the argument above that every permutation of a two-element set shows up in any product of three infinite subsets of Ω.

2 It is worth mentioning that such a triple A, B, C can be guaranteed not just with C = Xn but also for any C ∈ {Xm, ..., Xn-1} since otherwise we end up with Case 1 after reindexing the sets. Then the second to last sentence of the Conclusion ensures that the choice B = Xn is compatible with every C ∈ {Xm, ..., Xn-1}.

1

 1

2. 1

 1 Lemma ([2]; Section 3.2). For all α < β < γ, (1) αγ = βγ and αβ = βγ, (2) αγ ≤ αβ ∨ βγ, (3) αβ ≤ αγ ∨ βγ.

Acknowledgement. The research on this paper is partially supported by grants from NSERC(455916) and CNRS(UMR7586).