D.-T Phan-Huy

Member, IEEE Y Kokar

K Rachedi

P Pajusco

A Mokh

T Magounaki

R Masood

C Buey

P Ratajczak

N Malhouroux-Gaffet

J.-M Conrat

J.- C Prévotet

A Ourir

J De Rosny

M Crussière

M Hélard

Member, IEEE A Gati

T Sarrebourse

M Di Renzo

Single-Carrier Spatial Modulation for the Internet of Things: Design and Performance Evaluation by Using Real Compact and Reconfigurable Antennas

Keywords: Spatial modulation (SM), receive antenna shift keying (RASK), beamforming, multiple input multiple output (MIMO), Reconfigurable Antennas, Compact Antennas

In this paper, for the first time, we propose two new solutions to boost the data rate between small connected objects such as glasses and cams and the 5th generation (5G) mobile network, based on spatial modulation, single carrier waveform, compact reconfigurable antennas at the object side and massive multiple input multiple output (M-MIMO) at the network side. In the first new wireless communication system, a "transmitting object" uses transmit spatial modulation with a compact reconfigurable antenna and a constant envelop amplifier to transmit in high data rate with a low complexity and low power consumption. The space-time digital processing capability of the M-MIMO 5G base station is used to detect such signal. In the second new wireless communication system, a "receiving object" uses receive spatial modulation, a compact multiport antenna and a low complexity detection algorithm to receive in high data rate with a low complexity signal processing. The space-time beamforming capability of the M-MIMO 5G base stations is exploited to deliver a signal that is pre-equalized enough to be detected by the object. For the first time, we present experiments showing that M-MIMO allows for the reintroduction of single carrier modulation waveform. For the first time, we present performance results obtained with real existing compact antennas and compact reconfigurable antennas, showing that the two new communication systems outperform conventional modulation in terms of energy efficiency and complexity.

I. INTRODUCTION

Future mobile networks of the 5th generation (5G) will provide a wireless connection to the Internet-of-Things (IoT) [START_REF] Ijaz | Enabling Massive IoT in 5G and Beyond Systems: PHY Radio Frame Design Considerations[END_REF]. Among connected things, some, like connected glasses, connected cameras and connected watches, will need to transmit or receive video streams at a high data rate. The 3 rd Generation Partnership Project (3GPP) has already started to lower down the cost and the power consumption of devices for connected objects by reducing the number of Radio Frequency (RF) chains (for transmission) and reducing the number of RF amplifiers [START_REF]Cellular system support for ultra-low complexity and low throughput Internet of Things (CIoT) (Release 13)[END_REF].

Recently, it has been shown that, for some high signal to noise ratios values, and still with a single RF chain at the transmitter side, by using transmit spatial modulation [START_REF] Mesleh | Spatial Modulation[END_REF] with conventional arrays of antenna elements [START_REF] Renzo | Spatial modulation for multiple-antenna wireless systems: a survey[END_REF], one can achieve a higher spectral efficiency than by using a conventional modulation with the same single RF chain [START_REF] Stavridis | Energy Evaluation of Spatial Modulation at a Multi-Antenna Base Station[END_REF]. In transmit spatial modulation systems, in addition to the data stream sent using a conventional Pulse shape Amplitude Modulation (PAM), an additional data stream is sent by switching the transmit antenna element, every symbol period. The index of the current transmit antenna element encodes binary information. Previous studies on transmit spatial modulation are focused on conventional arrays: [START_REF] Di Renzo | On Transmit Diversity for Spatial Modulation MIMO: Impact of Spatial Constellation Diagram and Shaping Filters at the Transmitter[END_REF] analyzes solutions based on spatial modulation that exploit the diversity gain of the conventional antenna array and [START_REF] Younis | Performance of Spatial Modulation Using Measured Real-World Channels[END_REF]- [START_REF] Verhaevert | Realization and MIMO-link measurements of a transmit module for spatial modulation[END_REF] provide preliminary results on the performance of transmit spatial modulation based on experimental data obtained with conventional antenna arrays. For more information on transmit spatial modulation, please refer to the survey papers [START_REF] Renzo | Spatial modulation for generalized MIMO: Challenges, opportunities, and implementation[END_REF]- [START_REF] Liu | Performance of Generalized Spatial Modulation MIMO Over Measured 60GHz Indoor Channels[END_REF].

In receive spatial modulation systems such as the ones studied in [START_REF] Phan-Huy | Receive antenna shift keying for time reversal wireless communications[END_REF], in addition to sending a conventional PAM, the transmitter sends an additional data stream by focusing towards one antenna of the receiver among several, every symbol period. The index of the target antenna encodes binary information. A simple receiver can be used to demodulate the two streams [START_REF] Mokh | Performance analysis of the maximum ratio transmission preprocessing for extended receive antenna shift keying[END_REF]- [START_REF] Mokh | Time reversal receive antenna shift keying on MIMO LOS channel[END_REF].

Other works on reconfigurable antennas [START_REF] Alrabadi | MIMO Transmission Using a Single RF Source: Theory and Antenna Design[END_REF]- [START_REF] Di Renzo | Spatial Modulation Based on Reconfigurable Antennas -A New Air Interface for the IoT[END_REF] suggest that one can transport more bits than with a SISO system by using a reconfigurable antenna. In this case, instead of switching between antenna elements, the transmitter switches between radiation patterns. The advantage of these solutions is that they are more compact in size. The limitation of these techniques is the nonorthogonality of the radiation patterns, and up to now, no complete performance study with real and existing compact antennas has been performed to verify the advantage of such antennas.

In parallel, 5G envisions the development of massive arrays [START_REF] Yang | Performance of conjugate and zeroforcing beamforming in large-scale antenna systems[END_REF]- [START_REF] Dubois | Time reversal applied to large MISO-OFDM systems[END_REF] at the network side, with hundreds of antenna elements. These Massive Multiple Input Multiple Output (M-MIMO) antennas benefit from higher beamforming and spatial multiplexing gains [START_REF] Yang | Performance of conjugate and zeroforcing beamforming in large-scale antenna systems[END_REF] [START_REF] Jungnickel | The role of small cells, coordinated multipoint, and massive MIMO in 5G[END_REF], or reduced complexity in the demodulation [START_REF] Dubois | Time reversal applied to large MISO-OFDM systems[END_REF].

In this paper, for the first time, we introduce and make a complete performance evaluation of two new communication systems illustrated in Figure 1, for uplink and downlink communications, respectively, between objects with compact antennas and a base station with M-MIMO antenna array. In the uplink, transmit spatial modulation is used, and the object antenna is a compact reconfigurable antenna (either a multiport switchable antenna or a monoport reconfigurable antenna), whereas in the downlink, receive spatial modulation is used and the object antenna is still a compact antenna but multiport only in the current implementation. These two systems are compared to systems using conventional modulation schemes as well. The paper is organized as follows: Section II recalls the transmit and receive spatial modulation concepts and illustrates these concepts with visual experiments. Section III and IV present the performance evaluation study for transmit spatial modulation and receive spatial modulation, respectively.

The following notation is used throughout the paper. If ∈ ℂ, then | | is its module, arg ( ) is its phase in radians, * is its conjugate, ℛe( ) is its real part and Im( ) is its imaginary part. If ∈ ℂ × , then is the transposeconjugate of and

‖ ‖ = ∑ ∑ , . If ∈ ℂ × , then ‖ ‖ = ∑ . [ , ]
is the set of integers between and , including and . j = -1. We define the set ( ) , , and as follows:

 ( ) = { ( ) ∈ {0,1} × | ∈ [1, ]; = log ( ); ∑ ( ) 2 = };  = { √ , √ , √ , √ };  = ( ) , n ∈ ⟦1; 8⟧ ;  = ( ) √ ∈ [0,3] and ∈ [0,3]}.

II. TRANSMIT AND RECEIVE SPATIAL MODULATION CONCEPTS A. TRANSMIT SPATIAL MODULATION

In this section, we recall the concept of transmit spatial modulation and illustrate this concept with a visual experiment illustrated in Figure 2.

During the communication, the transmitter activates one radiation pattern among = 2 distinct ones. Each radiation pattern is associated with a distinct binary sequence of bits, according to a pre-defined pattern-to-bit mapping rule. The rule is known at both the transmitter and the receiver sides. As in most wireless communication systems, the transmitter sends pilots to train the receiver. More precisely, the transmitter activates each of its radiation patterns alternatively, so that the receiver can estimate and store the propagation channel associated with each pattern. Then, the transmitter performs an actual data transmission as follows.

A long binary sequence is cut into sub-sequences of bits.

To transmit a particular sub-sequence, the transmitter activates the pattern that corresponds to the sub-sequence, using the pattern-to-bit mapping rule. The receiver detects the pattern that has been used by comparing the current received channel with the stored channels. The receiver converts the detected pattern into a sub-sequence of bits using the pattern-to-bit mapping rule. Note that, transmit spatial modulation can be combined with a conventional modulation. As illustrated in Figure 2, our visual experiment involves an 8-port compact antenna at the transmission side and a 64element M-MIMO antenna at the receiver side. The transmitter emits a signal with carrier frequency of 2.45 GHz with one antenna port among the = 8 available, thanks to a switch. In this case, a pattern encodes = 3 bits. As illustrated in Figure 3, the 8 radiation patterns corresponding to the 8 ports of this antenna are distinct. Figure 3 also provides the mapping rule between patterns and 3-bit sequences.

As illustrated in Figure 2, the 64 elements of the M-MIMO antenna are positioned on a grid of 8 lines and 8 columns and connected to a real-time channel sounder. Figure 4 illustrates the graphical interface of the sounder. The top of Figure 4 illustrates the result of a previous channel training phase. For each of the 8 radiation patterns, the spatial signature (i.e., the matrix of 8 by 8 estimated channel amplitudes) is stored and displayed in color scale. Each spatial signature is associated with a pattern and a 3bit sequence. The bottom of Figure 4 illustrates the data transmission. A 3-bit sequence is transmitted by activating one radiation pattern among the 8 available. The channel sounder displays the current spatial signature (i.e., the actual 8 by 8 matrix of amplitudes of the current channel) in a color scale, computes the correlation of this matrix with the 8 stored matrices, determines the pattern that maximizes the correlation, and converts it into the detected 3-bit sequence, using the pattern-to-bit mapping rule. As illustrated in a video [32], all these steps are done in real time. In [32], even though the channel training is done only once at the beginning of the video, the detection remains robust for a long time period. This is thanks to the large size of the 8 by 8 matrices on which the correlation is performed. This illustrates one of the advantages of using M-MIMO at the network side.

Note that the training phase of spatial modulation is equivalent to the channel estimation phase for a conventional single carrier modulation. Both modulations require the transmission of pilot symbols during these phases, with the same periodicity (enough to track the channel variation).

B. RECEIVE SPATIAL MODULATION

In this section, we recall the concept of receive spatial modulation and illustrate this concept with a visual experiment depicted in Figure 5.

The receiver has = 2 antenna ports with distinct associated radiation patterns. Each radiation pattern is associated with a distinct binary sequence of bits, according to a pre-defined pattern-to-bit mapping rule. The rule is known at both the transmitter and the receiver sides. Channel reciprocity based beamforming (BF) as implemented in time division duplex (TDD) mode systems is used in order to target one antenna of the receiver among . As in any channel reciprocity based BF system, during the training phase the receiver sends distinct pilots from its distinct ports so that, for each port, the transmitter can: 1) estimate the channel, and 2) compute and store the precoder that enables to beamform towards this particular port. Then, the transmitter performs data transmission as follows. A long binary sequence is cut into sub-sequences of bits. To transmit a particular sub-sequence, the transmitter uses the stored precoder that beamforms towards the pattern corresponding to the considered sub-sequence. Finally, after detecting the port that is the current target of the beamforming (for instance by identifying the port that receives the strongest power), the receiver converts the detected pattern into a sub-sequence of bits using the pattern-to-bit mapping rule. Note that, this can be combined with a conventional modulation.

In our visual experiment, a transceiver and a receiver detailed in [START_REF] Kokar | Receive antenna shift keying modulation tesbed for wireless communication systems[END_REF] are used with a carrier frequency of 2.48 GHz.

As illustrated in Figure 5, the transmitter is a uniform linear array (ULA) of 4 monopoles and the receiver is a ULA of = 4 "squeezed monopoles". These monopoles are "squeezed" in the sense that they are close to each other by much less than half a wavelength and subject to coupling. In this experiment, the transmitter uses maximum ratio transmission (MRT) beamforming [START_REF] Lo | Maximum ratio transmission[END_REF], and switches at a maximum speed of 125 kHz between the four different stored precoders, each precoder targeting a distinct "squeezed monopole". In this example, the identity of the target "squeezed monopole" encodes = log ( ) = 2 bits. In parallel, the system transmits BPSK symbols. For each category, the same BPSK symbol and the same spatial modulation symbol are detected. One can note that spatial modulation works even with these "squeezed monopoles". This is due to the fact that for one monopole the other monopoles act as parasitic scatterers. This is known to create decorrelation, and is exploited as a design principle for compact multiport antennas as the ones that were presented in [START_REF] Lerosey | Hybridization band gap based smart antennas: Deep subwavelength yet directional and strongly decoupled MIMO antennas[END_REF] [START_REF] Malhouroux-Gaffet | Capacity Gain of MIMO Systems with Microstructured Antenna Arrays[END_REF], and that will be used in the current paper for performance evaluation.

III. MASSIVE MIMO: AN ENABLER FOR SINGLE-CARRIER MODULATIONS

5G is based on multi-carrier modulation. Such modulation is not compatible with spatial modulation [START_REF] Yang | Single-Carrier SM-MIMO: A Promising Design for Broadband Large-Scale Antenna Systems[END_REF]. However, we believe that the introduction of M-MIMO antennas in 5G networks is an enabler for the re-introduction of singlecarrier modulation in the future. In previous works [START_REF] Phan-Huy | Characterization of the confidentiality of a green time reversal communication system: Experimental measurement of the spy BER sink[END_REF] [START_REF] Phan-Huy | Dumb-to-perfect receiver throughput ratio maps of a time reversal wireless indoor system[END_REF], it has been shown that thanks to time reversal focusing with a large number of transmit antennas, the signal at the receiver is nearly echo-free. In [START_REF] Phan-Huy | Dumb-to-perfect receiver throughput ratio maps of a time reversal wireless indoor system[END_REF], a single-tap receiver successfully demodulates a signal using a single carrier modulation, within a 30MHz bandwidth centered at 1 GHz and using a 256 Quadrature Amplitude Modulation (QAM). However, this experiment was performed using an arbitrary waveform generator at the transmission side, and an oscilloscope at the reception side.

In this paper, we show recent experimental results obtained using the open-source hardware and software development platform Open Air Interface (OAI), and a rail moving with a Digital Servo Amplifier, SERVOSTAR 300, along with a Rosier servo motor controlling the movement. OAI is a wireless technology platform that offers an opensource software-based implementation of the Long Term Evolution (LTE) system spanning the full protocol stack of 3 rd Generation Partnership Project (3GPP) standard both in Evolved Universal Terrestrial Radio Access Network (E-UTRAN) and Evolved Packet Core (EPC). The experiments were carried out using orthogonal frequency division multiplex (OFDM) frames at the carrier frequency of 2.68 GHz. Each OFDM symbol consists of 512 carriers, out of which 300 are filled with random QPSK symbols and the rest are set to zero. An extended cyclic prefix (ECP) of 128 samples is added to each OFDM symbol after the 512point Inverse Fast Fourier Transform (IFFT). The sampling rate is 7.68 mega symbols per second, resulting in an effective bandwidth of 4.5 MHz. Ten subframes each with 12 ECP-OFDM symbols compose the TDD OFDM frame. In the experiment, the receiver sends pilots called sounding reference signals (SRS) in the uplink direction. The transmitter uses these pilots to estimate the uplink channel. Channel reciprocity is exploited to deduce the downlink channel. The transmitter precodes its downlink data and pilots with a maximum ratio transmission (MRT) precoder to beamform the signal towards the receiver. Note that MRT is equivalent to time reversal or the transmit matched filter pre-filtering applied to OFDM instead of a single-carrier modulation [START_REF] Kokar | Receive antenna shift keying modulation tesbed for wireless communication systems[END_REF]. During the experiment, 15 different positions of the receiver are tested, along a rail, and all in NLOS of the transmitter. For each position, the receiver measures the frequency response of the received beamformed channel thanks to the downlink precoded pilots. The measurements were carried out inside a controlled laboratory environment. Figure 7 illustrates the measurement setup. Figure 8 illustrates the radiation patterns of the 8 ports of the transmitter. Although, the antenna is compact, it exhibits patterns that are diverse. This antenna is therefore equivalent to an array of 8 low-correlated antennas.

Figure 9 illustrates the propagation environment during the experiments. Non-line-of sight propagation is chosen to create multi-path propagation. In such environment, the channel impulse response has several delayed taps. Hence, a single tap receiver trying to demodulate a single carrier modulation would suffer from inter-symbol interference. Finally, we apply an IFFT to the frequency response of the received beamformed channel, to obtain the corresponding filter in the time domain. Figure 10 illustrates the measured frequency response and the corresponding impulse response, for the received beamformed channel measured at the 15 th position. We observe that the beamformed channel is nearly a single tap channel. We also evaluate the ratio between the useful signal and the inter-symbol interference (SIR) that would be undergone by a single tap-receiver demodulating a single carrier modulation at 5 MHz. As illustrated in Figure 11, for all tested positions, this value exceeds 20 dB. This is largely sufficient to support a single carrier modulation with 16 QAM. More precisely, for the worst case position (position number 3), we simulate the transmission of 1,500,000 random bits over a single carrier modulation transmission with a Raised Root Cosine (RRC) filter, 16 QAM, and a single tap receiver. For this simulation we chose an extreme value of Roll Off factor (0.001), to test the worst case scenario. We use the same simulation methodology detailed in [START_REF] Phan-Huy | Dumb-to-perfect receiver throughput ratio maps of a time reversal wireless indoor system[END_REF], except that we use the current measured beamformed channel impulse response. The resulting measured bit error rate over 1,500,000 bits is zero. This means that the attainable BER, in this case, is estimated to be lower than 10 -5 . This confirms that current standards for mobile networks have the potential to support single carrier modulations, with bandwidths as large as several MHz. Note that, by applying maximum ratio combining (MRC) at the receiver side (instead of MRT at the transmitter side), in an uplink transmission (instead of a downlink transmission) we would have obtained the same result: the channel after equalization would have been single tap. This means that after a receive matched filter, the channel is single tap and compatible with a single carrier modulation and a single-tap detector.

In the next sections, M-MIMO is used with much more antenna elements than in the current sub-section. It is therefore a reasonable assumption to consider that the beamformed or equalized channel (using transmit matched filtering or received matched filtering) will be single tap, i.e., not frequency selective. As a consequence, to derive the beamformed channel, one just needs to study the frequency-flat channel over the carrier frequency. Therefore, in the next sections, we will directly use a frequency-flat channel model for our performance studies and assume that the equalized or pre-equalized channel does not introduce interference between successive symbols in the time domain.

IV. UPLINK TRANSMISSION: FIRST PERFORMANCE EVALUATION OF TRANSMIT SPATIAL MODULATION WITH REAL COMPACT RECONFIGURABLE ANTENNAS

In this section, for the first time, we present a complete performance evaluation of a wireless communication system using transmit spatial modulation with a real and existing compact reconfigurable antenna at the transmitter side and an M-MIMO antenna at the receiver side. The considered carrier frequency in this section is 2.45 GHz.

A. MODELS OF REAL COMPACT RECONFIGURABLE ANTENNAS AND THE PROPAGATION CHANNEL

At the base station side, we consider a ULA of = 64 elements spaced by half a wavelength as an example of M-MIMO antenna.

As for the object, two different real and existing compact reconfigurable antennas are considered and compared:

 A multiport switchable antenna [START_REF] Malhouroux-Gaffet | Capacity Gain of MIMO Systems with Microstructured Antenna Arrays[END_REF] illustrated in Figure 12-a) that can generate = 4 different radiation patterns, and that can therefore transmit = log ( ) = 2 bits by using spatial modulation;  A monoport reconfigurable antenna [START_REF] Ourir | Compact Reconfigurable Antenna with Radiation Pattern Diversity for Spatial Modulation[END_REF] illustrated in Figure 13-a) that can generate = 2 different radiation patterns, and that can therefore transmit = log ( ) = 1 bit by using spatial modulation. The first one is half of the wavelength in size, whereas the second one only occupies one third. For both antennas, only one radiation pattern is activated at a time, either thanks to a RF switch connected to the multiport antenna or by commuting the diodes of the reconfigurable antenna [START_REF] Ourir | Compact Reconfigurable Antenna with Radiation Pattern Diversity for Spatial Modulation[END_REF]. The two-dimensional (2D) propagation models, for the multiport switchable antenna and the monoport reconfigurable antenna are illustrated in Figure 14 and Figure 15, respectively. For the two compact reconfigurable antennas, the complex gain function ( ) ( : ⟶ ) of each pattern p in direction angle is numerically characterized by using Finite Difference Time Domain (FDTD) full wave simulation. The moduli of the radiation patterns are illustrated in Figure 12-b) and Figure 13-b), for the multiport switchable antenna and the monoport reconfigurable antenna, respectively.

The spatial correlation between two radiation patterns and of the same antenna is a key parameter in spatial We consider a single carrier modulation communication. As explained in section III, thanks to the M-MIMO antenna and assuming that a matched filter is used at the receiver, we can limit the study to a frequency-flat channel and assume that the channel does not introduce interference between successive symbols in the time domain. The wireless propagation channel between one antenna port of the transmitter and one antenna element of the receiver can be modeled by a complex gain.

We define ∈ ℂ × as the channel between the object and the base station. More precisely, let , be the channel coefficient between the receive antenna ∈ [1, ] of the base station and the object when it is using the radiation pattern number ∈ [1, ].

, includes both the wireless propagation and the radiation pattern .

Regarding the model used for multi-path propagation, we consider a 2D wireless propagation model, with random scatterers creating angular diversity in the channel. The , is given by:

, = ∑ δ . ( ) , (1)
where is a normalizing factor. We choose such that:

‖ ‖ = 1.
In other terms, the average channel power per SISO antenna link is unitary.

B SYSTEM MODEL

For the compact multiport switchable antenna, we compare five different schemes to send a sequence of bits, where, = … ( ) , and = 4:

- For all schemes, for each symbol period, the object sends a sequence of bits ∈ ( ) with a radiation pattern . Among these > 0 bits, > 0 bits are sent using a complex modulation symbol ∈ , where is the predefined set of complex modulation symbols. ≥ 0 bits are sent using spatial modulation. So, the following holds:

= + .

The definition of S, the values of , and are schemespecific and provided in Table III and Table IV for the schemes with the multiport switchable antenna and the monoport reconfigurable antenna, respectively. Note that, for "16QAM & Pattern " and "8PSK & Pattern ", the radiation pattern p is fixed, and spatial modulation is unused ( = 0). On the contrary, for "QPSK & SM4" and "QPSK & SM2" schemes, the pattern p is variable and spatial modulation is used ( > 0). More precisely, in the "QPSK & SM4" scheme, as illustrated in Figure 16, during each symbol period, is sent using QPSK. Simultaneously, is sent using the corresponding pattern number (based on Table V). In the "QPSK & SM2" scheme, as illustrated in Figure 17, during each symbol period, is sent using QPSK modulation. Simultaneously, is sent using the corresponding pattern number (pattern = 1 corresponding to Bit "0" and = 2 corresponding to Bit "1").

Figure 18 and Figure 19 illustrate the mapping between bits and symbols for the schemes with the multiport antenna and the reconfigurable antenna, respectively. Note that with the chosen definitions, [| | ] = 1 for all schemes. In other terms, all schemes radiate the same transmit power per symbol, on average.

Let ∈

× be the signal received over the elements of the M-MIMO antenna, is given by: = + , where ∈ , ∈ , is the transmit power, ∈ ℂ × is the vector of noise samples over the receiver chains of the base station, and ∈ ℂ × accounts for the MRC receiver. More precisely, for 1 ≤ ≤ and 1 ≤ ≤ , , is given by: , as the average receiver noise power per antenna element at the base station side. We define an arbitrary signal to noise ratio metric that is common to all schemes: = .

We also assume that the receiver has a perfect estimate of thanks to a previous training phase based on pilots. We assume that the receiver has computed and stored the following set of variables: Based on these current results, as illustrated in Figure 22, one path for future improvements is to build a new monoport reconfigurable antenna, that is more compact than the current multiport antenna, and to deliver 4 bits/s/Hz with a constant envelop modulation (the same "QPSK & SM4" scheme for instance).

FIGURE 1 .

 1 FIGURE 1. Transmit and receive spatial modulation for connected objects

FIGURE 2 .

 2 FIGURE 2. Experimental set-up

FIGURE 3 .

 3 FIGURE 3. The 8 ports of the transmitter, their corresponding radiation patterns and their corresponding 3-bit sequences

FIGURE 4 .

 4 FIGURE 4. Graphical interface of the M-MIMO real time channel sounder

FIGURE 5 .

 5 FIGURE 5. Experimental set-up.

Figure 6

 6 Figure 6 illustrates the resulting constellation of receive spatial modulation together with BPSK modulation. The positions of the two BPSK states in the complex I-Q domain are visualized by two drawings of targets. The I-Q symbol received by each of the = 4 monopoles of the receiver is plot for different realizations of the propagation channel. The joint detection of BPSK and the spatial modulation consists in determining the monopole that is closest to one of the two BSPK states. Figure 6 illustrates experimental measurements of the received I-Q symbols. The measurements are classified into 8 different categories illustrated by 8 different figures.For each category, the same BPSK symbol and the same spatial modulation symbol are detected. One can note that spatial modulation works even with these "squeezed monopoles". This is due to the fact that for one monopole the other monopoles act as parasitic scatterers. This is known to create decorrelation, and is exploited as a design principle for compact multiport antennas as the ones that were presented in[START_REF] Lerosey | Hybridization band gap based smart antennas: Deep subwavelength yet directional and strongly decoupled MIMO antennas[END_REF][START_REF] Malhouroux-Gaffet | Capacity Gain of MIMO Systems with Microstructured Antenna Arrays[END_REF], and that will be used in the current paper for performance evaluation.

FIGURE 6 .

 6 FIGURE 6. Experimental observations of the constellations for receive spatial modulation and BPSK modulation.

FIGURE 7 .

 7 FIGURE 7. Experimental set-up, in NLOS.

FIGURE 8 . 8 -

 88 FIGURE 8. 8-port transmit antenna.

FIGURE 9 .

 9 FIGURE 9. NLOS propagation.

FIGURE 10 .

 10 FIGURE 10. Received beamformed channel for the 15th position of the UE.

FIGURE 11 .

 11 FIGURE 11. SIR with single carrier modulation.

FIGURE 12 .

 12 FIGURE 12. Compact multiport switchable antenna model.

b) 2 -

 2 D radiation patterns, where is the angle of arrival or departure and is the antenna gain in the direction of for port p systems. The less correlated the patterns are, the more robust spatial modulation to noise is. The correlation is given by:

b) 2 -:

 2 D radiation patterns, where is the angle of arrival or departure and ) is the antenna gain in the direction of for Angle of departure elements of the M-MIMO antenna are spatially correlated. The path ∈ [1, ] between the receive antenna of the base station and the connected object has a random complex gain ∈ ℂ , a random angle of departure ∈ [0,2π[ and a random angle of arrival ∈ [0,2π[ . is a Rayleigh fader with = 1/Q and and are uniformly distributed over [0,2π[. With these notations, the channel coefficient

  "16QAM & Pattern = 1"; -"16QAM & Pattern = 2"; -"16QAM & Pattern = 3"; -"16QAM & Pattern = 4"; -"QPSK & SM4". For the compact monoport reconfigurable antenna, we compare three different schemes to send a sequence of bits, where = … ∈ ( ) , with = 4: -"8PSK & Pattern = 1"; -"8PSK & Pattern = 2"; -"QPSK & SM2".

FIGURE 19 .

 19 FIGURE 19. Constellations for 8PSK, "QPSK & SM2", with same average radiated power

FIGURE 20 .

 20 FIGURE 20. Performance with the monoport reconfigurable Antenna

Figure 21

 21 Figure21shows that "QPSK & SM4" outperforms all other "16QAM & Pattern p" schemes. As for the previous antenna, "QPSK & SM4" is also more energy efficient than 16QAM, as it uses constant envelop amplifiers. Therefore, there is still room for improvement of the compactness of the antenna before the same BER vs SNR performance as 16QAM is attained.

FIGURE 21 .

 21 FIGURE 21. Performance with the multiport antenna

FIGURE 22 .

 22 FIGURE 22. Path for improvement of the antenna for 4 bits/s/Hz

Table I and

 I Table II provide the correlations for the multiport switchable antenna and the monoport reconfigurable antenna, respectively.

FIGURE 13. Compact monoport reconfigurable antenna model. FIGURE 14. Propagation model for the multiport switchable antenna.

FIGURE 15. Propagation model for the monoport reconfigurable antenna.

TABLE I CORRELATIONS

 I , BETWEEN ANTENNA PORTS P AND Q FOR THE

			MULTIPORT SWITCHABLE ANTENNA
	\q	1	2	3	4
	1	1	0.0722	0.0593	0.0007
	2	0.0772	1	0.0158	0.0522
	3	0.0593	0.0158	1	0.0688
	4	0.007	0.0522	0.0688	1
			TABLE II
	CORRELATIONS , BETWEEN ANTENNA PORTS P AND Q FOR THE
		MONOPORT RECONFIGURABLE ANTENNA
	\q		1	2
	1		1	0.3190
	2		0.3190	1

TABLE III SPECTRAL

 III EFFICIENCY R FOR THE COMPACT MULTIPORT SWITCHABLE ANTENNA (WITH P=4 STATES), IN NUMBER OF BITS PER SYMBOL PERIOD

	Scheme	p	S	u+K=r
	16 QAM with Pattern 1	1		4 + 0 = 4
	16 QAM with Pattern 2	2
	16 QAM with Pattern 3	3
	16 QAM with Pattern 4	4
	QPSM & SM4	1 to 4		2 + 2 = 4

-T. Phan-Huy (This work was supported in part by SpatialModulation project under the French Research Agency Grant ANR-15-CE25-0016.

Upon the reception of a new signal , the receiver compares it to the variables of and determines the signal that minimizes the Mean Square Error:

Then, the detected binary sequence = … is deduced from by using the mapping rules illustrated in Figure 18 and Figure 19. The bit-error-rate (BER) can then be computed as follows:

We perform 250,000 simulation runs. For each simulation run:

 The parameter and the number of scatterers = 10 are fixed.

 We compute a random channel sample based on randomly and independently generated parameters , , , , , , and .

 We generate a random sample of noise .

 For each possible values of the sent sequence , i.e. for all ∈ ℬ ( ) , we compute , and and the BER.

We average these BER values over all sent sequences, during a simulation run, and over all runs (i.e. over 1 million of bits). We then plot the result as a function of in Figure 20 and Figure 21, for the multiport antenna, and the monoport reconfigurable antenna, respectively.

C. SIMULATION RESULTS AND CONCLUSIONS

Figure 20 shows that the compact monoport reconfigurable antenna with "QPSK & SM2" modulation is a solution to provide 3 bits/s/Hz, that is as efficient and as compact in size as another solution using a compact antenna of the same size with a conventional 8PSK modulation. However, the monoport reconfigurable antenna with "QPSK & SM2" is more energy efficient than 8PSK, as it advantageously uses constant envelop power amplifiers [START_REF] Joung | A Survey on Power-Amplifier-Centric Techniques for Spectrum-and Energy-Efficient Wireless Communications[END_REF] [START_REF] Chadwick | Constant Envelop Modulation[END_REF].

A. REAL COMPACT MULTIPORT ANTENNA

At the base station side, we consider a ULA of = 64 elements spaced by half a wavelength as an example of M-MIMO antenna.

The same real and existing compact multiport antenna [START_REF] Malhouroux-Gaffet | Capacity Gain of MIMO Systems with Microstructured Antenna Arrays[END_REF] as the one used in Section III, and illustrated in Figure 12 is used. However, this time, there is no switch, and all the ports are used simultaneously. A similar 2D channel model as the one used in section III-A is used. This time, we define ∈ ℂ × as the channel from the base station to the object, including wireless propagation and antenna radiation patterns. More precisely, let , be the channel coefficient between the transmit antenna ∈ [1, ] of the base station and the antenna port ∈ [START_REF] Ijaz | Enabling Massive IoT in 5G and Beyond Systems: PHY Radio Frame Design Considerations[END_REF][START_REF] Renzo | Spatial modulation for multiple-antenna wireless systems: a survey[END_REF] of the object.

, includes both the wireless propagation and the radiation pattern of the port .

As in Section III-A and as illustrated in

where is a normalizing factor. We choose such that: ‖ ‖ = 1.

The average channel power per single antenna link is unitary. For all schemes, for each symbol period, the base station sends a sequence of 4 bits = ∈ ( ) using a complex modulation symbol and a precoder ( ) , with ∈ [START_REF] Ijaz | Enabling Massive IoT in 5G and Beyond Systems: PHY Radio Frame Design Considerations[END_REF][START_REF] Renzo | Spatial modulation for multiple-antenna wireless systems: a survey[END_REF], picked among 4 stored precoders. The precoder ( ) ∈ ℂ × is based on the MRT precoder and is defined as follows:

where, ( ) is chosen so that:

We denote by the set of complex modulation symbols. The definition of S and the choice of p are scheme-specific and provided hereafter for each scheme.

In "16QAM & Pattern p", the precoder ( ) is fixed, and 16QAM modulation is used, hence:

= .

The pattern-to-bit mapping in Table III is used. In the "QPSK & SM4" scheme, as illustrated in Figure 24, during each symbol period, is sent using QPSK modulation. Simultaneously, is sent using the corresponding precoder ( ) (using the pattern-to-bit mapping rule of Table III), hence:

= . The illustration of the mapping between bits and symbols in Figure 18 and the spectral efficiency given in Table III is still valid for the considered scheme. Note that with the chosen definitions, [| | ] = 1 for all schemes. In other terms, all schemes require the same transmit power per symbol, in average.

We use the same notation as for section III:

Let ∈ × be the signal received over the = 4 ports of the object. With this notation, we obtain the following expression of :

where ∈ , ∈ , is the transmit power and ∈ ℂ × is the vector of noise samples over the ports of the object. We denote = [‖ ‖ ]/ , as the average receiver noise power at the object side per port. We define an arbitrary signal to noise ratio metric that is at least common to all schemes, as follows:

= .

We assume that the receiver has perfect estimates of and ( ) thanks to a previous training phase based on pilots. We assume that the receiver has computed and stored the variables:

Upon the reception of a new signal , the receiver compares it to the set of variables and determines the signal that minimizes the Mean Square Error:

Then, the detected binary sequence = is deduced from by using the mapping rule illustrated in Figure 18.

We perform a large number of simulation runs (100,000 runs) and use the same simulation methodology as in Section IV-B) to derive the average the BER versus curves of Figure 25.

C. SIMULATION RESULTS

Figure 25 shows that "16QAM & SM4" outperforms all other schemes for the considered range of SNR and BER values. This is due to the combination of two effects. On the one hand, "16QAM & SM4" is less dense in the complex domain than the "16QAM & Pattern p" modulations, as illustrated in Figure 18. On the other hand, the patterns of the 4-Port compact antenna are low correlated, as shown by Table I.

We also observe that the BER performance of "QPSK & SM4" will be worse than that of 16 QAM modulation for higher SNR values. This is consistent with earlier studies on spatial modulation with conventional antenna arrays, led by at least two different independent teams in [START_REF] Jeganathan | Space shift keying modulation for MIMO channels[END_REF] (Fig. 5, Fig. 6 and Fig. 9) and in [START_REF] Di Renzo | Bit Error Probability of SM-MIMO Over Generalized Fading Channels[END_REF] (Fig. 9). These studies show that spatial modulation is outperformed by conventional modulations at high SNR.

To summarize the results, "QPSK & SM4" is a new modulation which, compared to 16QAM, is more energy efficient, in the considered ranges of SNR and BER values (larger than 10 -4 ).

VI. CONCLUSIONS AND FUTURE PERSPECTIVES

In this paper, for the first time, we have presented a complete performance evevaluation results of two new wireless communication systems for small connected objects, both based on spatial modulation and real existing compact antennas at the object side, and M-MIMO antennas at the base station side. Based on experimental results, we have shown that introducing M-MIMO in 5G networks enables the potential re-introduction of single carrier modulation based on spatial modulation. Our simulations take into account precise models of several real and existing compact antennas (obtained from actual prototypes designed and implemented for special application to single-carrier spatial modulation systems) at the object side: a compact monoport reconfigurable antenna with two states and a multiport switchable antenna with four states. We have compared the proposed spatial modulation systems with conventional modulations of the same spectral efficiency. Our results show that transmit spatial modulation with the monoport antenna attains the same BER versus SNR performance as 8PSK, but it allows one to use constant envelop amplifiers, which are less complex and more energy efficient. Transmit spatial modulation with the multiport antenna attains a better BER versus SNR than 16QAM, and still with constant envelop power amplifiers. For this higher spectral efficiency, a more compact antenna could still be designed. Our simulations also show that receive spatial modulation with the multiport antenna outperforms 16QAM. Future investigations will focus on the design of antennas providing optimum performance and compactness, for a given target spectral efficiency.


Xavier Baril
email: xavier.baril@airbus.com

Oihana Coustié
email: oihana.coustie@irit.fr

Josiane Mothe
email: josiane.mothe@irit.fr

Olivier Teste
email: olivier.teste@irit.fr

RFreeStem: A multilanguage rule-free stemmer

Keywords: Text mining, information retrieval, Sentiment analysis, Stemmer, NLP MOTS-CLÉS : Fouille de texte, recherche d'information, Analyse de sentiments, racinisation

With the large expansion of available textual data, text mining has become of special interest. Due to their unstructured nature, such data require important preprocessing steps. Among them, stemming is a popularly used preprocessing method that extracts the root of the words. However, the most popular algorithms are based on the application of rules, and therefore highly language-related. We propose a new approach, the RFreeStem, that is rather based on corpus and can therefore be applied on many languages.

RÉSUMÉ. La grande disponibilité de données textuelles a rendu populaire les recherches de fouille de texte. Parmi les importants prétraitements nécessaires, la racinisation s'est imposé comme une étape incontournable. Pourtant, les algorithmes les plus utilisés sont basés sur l'application successives de règles. Cette construction les rend fortement dépendants de la langue d'application. Nous proposons ici une nouvelle approche, le RFreeStem, qui se base sur le corpus étudié et promet de pouvoir être appliqué à plusieurs langues.

Introduction

In the past decades, the overwhelming progress in technologies and Web researches has lead to a high increase of available machine readable documents [START_REF] Moral | A survey of stemming algorithms in information retrieval[END_REF]. Such unstructured data represent a huge potential of information to retrieve. Yet, the absence of structure, along with their high dimensionality make them difficult to process, with an important amount of necessary pre-treatment. Among the numerous pre-processing tasks for text analysis, the idea of stemming the words in the textual data has emerged since the late sixties [START_REF] Lovins | Development of a stemming algorithm[END_REF] and is now almost systematically used (Marcos-Pablos, García-Peñalvo, 2019).

Stemming can be described as the process of replacing a word by its morphological root -the stem. Such an algorithm is referred to as a stemmer. The stem can be a sub-string or a concatenation of sub-strings of the word, or even a modified sub-string, as in [START_REF] Porter | An algorithm for suffix stripping[END_REF], who stems happy to happi. More than the obtain stem itself, the main result of a stemmer stands in the groups created by regrouping words identically stemmed. Such groups are often referred to as conflation groups [START_REF] Frakes | Information retrieval: Data structures & algorithms[END_REF]. For example, [START_REF] Porter | An algorithm for suffix stripping[END_REF] would conflate happy and happier, both stemmed to happi. Having words stemmed together automatically reduces the size of the vocabulary since it removes the morphological variants of the words of a lexicon [START_REF] Jivani | A comparative study of stemming algorithms[END_REF].

The assumption made here is that morphologically related words have similar meanings and represent the same idea. However, this hypothesis is questionable, that is why many research papers decided to work on lemmatizing algorithms instead. [START_REF] Moral | A survey of stemming algorithms in information retrieval[END_REF] describes lemmatization as linguistic-based approach that relies on Part of Speech(PoS) and context. They are less dependants on the morphological variants of the words than stemmers are. To do so, they often draws on dictionaries or thesauri. Even if they offer prospectively more accurate results, their high complexity make them unpopular. Lemmatization will therefore not be detailed furthermore in this paper, since it is another field of research. We will rather focus on stemmers, reputed to be faster and more popular [START_REF] Jivani | A comparative study of stemming algorithms[END_REF].

Indeed, stemming has become an almost inescapable step in some text mining tasks. Among them, Information Retrieval (IR) algorithms automatically analyze documents to extract information to answer user queries [START_REF] Hull | Stemming algorithms: A case study for detailed evaluation[END_REF]: since the stem represents a broader concept than the word, more documents are expected to match the query. Other text mining fields extensively use stemming pre-processing. [START_REF] Jivani | A comparative study of stemming algorithms[END_REF] describes it as a requirement for many Natural Language Processing (NLP) applications, including text clustering and categorization or sentiment analysis -the process to automatically describe the sentiments of the author of a message.

However, the most widely used stemmer are based on rules to be applied on the words, in order to remove irrelevant parts. These rules rely on the morphological forms of the words and thus are necessarily language-specific. Whereas highly-spoken languages have their rules well described, it is difficult to find an implementation of those algorithms for rare languages or dialects. Moreover, the number of rules, as well as the quality of the stemmer, seem to highly depend on the language it is applied on [START_REF] Kraaij | Viewing stemming as recall enhancement[END_REF]. To be more specific, linguistics distinguish two different types of language structures [START_REF] Moral | A survey of stemming algorithms in information retrieval[END_REF]:

-Analytic (or isolating) languages, with little morphology structures, where the variants are more likely to be expressed by helper words than by word variations (e.g. Chinese, Vietnamese, modern English).

-Synthetic languages, with strong morphology structures. Among them we find: (i) The inflective language, like Latin languages (French, Italian) or Germanic languages (German, Dutch, Swedish, [START_REF] Braschler | How effective is stemming and decompounding for german text retrieval?[END_REF]). They have numerous prefixes and suffixes applied to modify the grammatical nature or even the meaning of the words.(ii) The agglutinative language, like Finnish, Japanese or Basque. In those languages the suffixes do not only represent inflections but can also be the concatenation of other morphemes. For example, in basque, exte means house and etxean means in the house.

Regarding those different categories of languages, [START_REF] Jivani | A comparative study of stemming algorithms[END_REF] affirms that stemming has proven more efficient on languages with complex morphology, that is to say on synthetic languages. [START_REF] Braschler | How effective is stemming and decompounding for german text retrieval?[END_REF] come to the same conclusion with its study on Germanic ones. Yet, on such languages, a great number of rules would be needed, in order to remove all the affixes, which would make the stemmer poorly flexible. Furthermore, stemming evaluation can be performed by comparing its results to a set of validated labels. In this case, further than the traditional precision and recall, [START_REF] Paice | An evaluation method for stemming algorithms[END_REF] defines the overstemming and understemming errors. Overstemming error counts the number of words stemmed together whereas they shouldn't have and understemming error census the words with different stems that should have been stemmed together. Paice proposes the calculation of indicators based on such metrics. However, they all assume the access to an objective label set, which is difficult to census in practice, especially on rare languages.

In the light of these observations, our contribution consists in a rule-free stemmer, that can be applied on multiple languages. To cope with the previously mentioned evaluation issues, we will evaluate our stemmer by measuring its impact on the results of data mining tasks. We will also assess what we call compression power -the ability of a stemmer to compress the size of a vocabulary. We will measure it thanks to the famous Index Compression Factor [START_REF] Sirsat | Strength and accuracy analysis of affix removal stemming algorithms[END_REF], that asses the strength of stemmers. Finally, we shall be paying special attention to the stem produced. Although [START_REF] Jivani | A comparative study of stemming algorithms[END_REF] mentions that stemmers do not need to be words from the language, it can nevertheless be crucial that the stems are humanly readable in tasks like query expansion or dictionary look-up [START_REF] Hull | Stemming algorithms: A case study for detailed evaluation[END_REF].

In accordance with those matters, we first propose to census the different types of stemming methods found in the literature in section 2, before describing ours, the RFreeStem in setion 3. We will finally describe, in section 4 an evaluation framework to assess the results of our stemmer on different text mining tasks and languages.

Related work

The literature offers an important variety of stemming algorithms that can mostly be categorized in two types of approach : (a) the rule-based methods, (b) the corpusbased methods. The following subsections propose to census some of the most important studies on stemming algorithms in those two categories.

Rule-based methods

Most of the well-known stemming methods are based on the application of rules. Among them, affix stripping gathers procedures to remove the suffixes and, sometimes, the prefixes of the words. In 1968, [START_REF] Lovins | Development of a stemming algorithm[END_REF] proposed a first suffix stripping method. Aggressive and fast, the algorithm matches the end of the word with the longest element of a suffix list, and applies rules to modify the matching end. Lovins's algorithm is reputed to be unreliable since its list of suffixes is based on a very technical-oriented vocabulary. Yet, technical and scientific words tend to derive from Latin languages and therefore to be highly inflectional, whereas common modern English is rather isolating1 .

The now most popular algorithm was soon proposed by [START_REF] Porter | An algorithm for suffix stripping[END_REF]. With 5 successive steps, it is a bit slower than its 2-step predecessor, but has experimentally proven more accurate [START_REF] Willett | The porter stemming algorithm: then and now[END_REF], [START_REF] Paice | Method for evaluation of stemming algorithms based on error counting[END_REF]. Initially, Porter exclusively defined those successive rules to stem English words. Yet, its popularity motivated the implementation of snowball [START_REF] Porter | Snowball: A language for stemming algorithms[END_REF], a detailed framework that enables users to implement their own version of Porter stemmer in any language. However, it remains a current subject of study to find such implementations for less common or highly inflectional languages (e.g. Bahasa Indonesian [START_REF] Tala | A study of stemming effects on information retrieval in bahasa indonesia[END_REF], Dutch [START_REF] Kraaij | Porter's stemming algorithm for dutch[END_REF]).

Many other rule-based methods were proposed afterwards. Among them, the light S stemming only deals with plural forms, and so presents little compression power. On the other hand, [START_REF] Paice | Another stemmer[END_REF] proposed a strong algorithm that applies successive deletion and replacement rules. [START_REF] Jivani | A comparative study of stemming algorithms[END_REF] argues that this method often presents a high over-stemming error. [START_REF] Dawson | Suffix removal and word conflation[END_REF] implemented an adaptation of Lovins method with much more suffixes and rules, which unfortunately makes the algorithm hardly reusable [START_REF] Jivani | A comparative study of stemming algorithms[END_REF]. [START_REF] Krovetz | Viewing morphology as an inference process[END_REF] proposes an approach based on inflections and derivations, with its Krovetz stemmer, KSTEM. It relies on an inflection-free lexicon to withdraw inflections, before analyzing the derivationsvariants that change the grammatical nature of words. The author acknowledges that the performance strongly depends on the chosen lexicon. We even add that finding such an exhaustive lexicon might not be feasible for rare language or dialect.

Those rule-based methods are undeniably the most recognized and used in information retrieval, thanks to their fast computation skills and easy implementations [START_REF] Harman | How effective is suffixing[END_REF]. Nevertheless, adapting those methods to highly-inflectional languages would lead to a large number of necessary rules. Consequently, recent papers that focus on stemming text from those languages are inclined to look for other approaches than rule-based ones.

Corpus-based methods

In order to cope with the strong language dependence of rule-based stemming techniques, some corpus-based methods were proposed. Most of them rely on statistical principles. [START_REF] Hafer | Word segmentation by letter successor varieties[END_REF]) developed a Successor variety stemmer which cuts the words in two parts : if the first part belongs to the corpus, this first part becomes the stem. The cutting algorithm is based on the evolution, within the word's letters, of the successor variety : the number of distinct characters that follow a string within all the words of the corpus. Thus, the resulting conflations strongly depend on the corpus, and yet, systematically choosing the first part of the word as a stem seems to be a language-dependant approach.

Another method, -the ngram stemmerproposed by [START_REF] Adamson | The use of an association measure based on character structure to identify semantically related pairs of words and document titles[END_REF], uses a common string clustering method to create conflation groups : a hierarchical single linkage clustering of the words. To evaluate the word pairwise distance, the authors used the Dice distance, corresponding to the number of distinct shared digrams -sequence of two consecutive letters. Using an unsupervised clustering method to create conflation groups makes the stemming corpus-dependant but also offers a very flexible way to manage stemming strength. However, single linkage clustering is known for its important algorithm complexity, due to the creation of a quadratic distance matrix. Very similarly, YASS (Yet Another Stripping Stemmer), described in [START_REF] Majumder | Yass: Yet another suffix stripper[END_REF], clusters words with linkage hierarchical methods, but has also implemented word distance metrics that encourage long suffix matching. According to [START_REF] Jivani | A comparative study of stemming algorithms[END_REF], they make the method more adapted for languages that are richly suffixed. As a last interesting example, [START_REF] Soricut | Unsupervised morphology induction using word embeddings[END_REF] proposed an unsupervised corpus-based method that automatically identifies meaningful rules to strip prefixes, with overall good results. The unsupervised learning on the corpus makes this method highly flexible and potentially adaptable to many languages.

From our reading of the literature, some stemming features appear to be interesting and have constituted the baseline of the method we propose. A rule-free method offers the possibility for the stemmer to be applied on many languages. Moreover, an unsupervised hierarchical clustering method does not need any prior knowledge and enables a high flexibility in the stemmer strength. Finally, the use of ngrams seems particularly fit for strings classification. The following section describes how those features were implemented for the RFreeStem algorithm. To answer the detected issues of existing stemmers, we propose a new approach with RFreeStem stemmer. Our corpus-based algorithm clusters the words of a corpus in order to create conflation groups. It is therefore an unsupervised learning method, that does not need any external knowledge. The proposed clustering is hierarchicalwhich allows flexibility in term of stemmer strength -and based on ngram similarity. Moreover, the clustering method promises to be much faster than any distance-matrixbased clustering. Indeed, instead of creating such a quadratic matrix, the algorithm only runs through the ngrams once. The RFreeStem stemmer is divided in two steps: after extracting all the words from the corpus, the group generation step clusters the words into conflation groups, and the dictionary generation step creates a readable dictionary out of the stemmed groups. Those steps are resumed in Figure 1 and describes in the following subsections. The first step of our process consists in clustering the corpus words. After the extraction of all the words of the corpus, they are processed to be regrouped by con-flation. To do so, we use a hierarchical clustering method -generally more adapted for text clustering-with a divisive approach : starting from the whole set of words, we recursively split it into clusters, as illustrated in Figure 2. We call those recursive steps divisive steps, and describe them in the subsection 3.1.1. We therefore discuss the choice of the number of divisive step needed in section 3.1.3. Indeed, deciding how to cut the dendrogram directly impacts the conflation groups and the stemmer strength.

Word clustering

Divisive step algorithm

At each divisive step, a set of several words is divided into several groups. The algorithm 1 formally describes this process. The algorithm uses the functions : (i) findnGram that extracts all the unique ngrams within a set of words (ii) scoreFunction that sorts a set of ngram and returns it. The implementation of that function is described in subsection 3.1.2. (iii) first, last and next which respectively returns the first, last or next element of a set (iv) createGroup that creates a group with words (v) emptyGroup and addGroup which respectively initializes a empty set of clusters and a cluster to a set (vi) grep which returns the words that match a pattern.

In the first divisive step, the input set of words is the whole corpus, whereas in each intermediate ones, the input is an already formed cluster. For an input W , w ∈ W is a word of the set, on an alphabet A. If w = a 1 a 2 ..a k , where k is the length of w and ∀i,

a i ∈ A, then a ngram of w is a subset a i ..a i+n , i ∈ [[1; k -n]].
Notice that w exactly has kn + 1 ngrams. We propose to extract all the distinct ngrams of all the words. Let N be such a set of ngrams. Our method then sorts the ngrams (subsection 3.1.2), which are then browsed exactly once. For each ng ∈ N , all the words that contain ng are clustered together. This one-browse clustering offers an interesting decrease in computational execution time, compared with traditional distance-based clustering algorithms. In addition, the condition size(W ) = 0 -all the words are clustered -is generally reached before the end of the browse, stopping the execution.

Scoring function choice

It appears from the previously described algorithm that the definition of the function that sorts the ngram is crucial -We call it the scoring function. Indeed, it is designed to give a score to each ngram, knowing they will be browsed according to these scores. A ngram with a high score will be responsible for the clustering of all the words that contain this ngram together. We define the generated group of an ngram as the set of words that contain this ngram. Regarding our algorithm, the generated groups of well-scored ngrams will become clusters, and the final generated groups will gather words that will be stemmed together. Hence, if the ngram tion has a better score than clas, then classification will be clustered with the tion-words -like imitation, attention -instead of being united with words like class or classify. To avoid this situation, we discuss interesting features that can define a "good" ngram:

-The number of words containing this ngram, which also is the size of the generated group. A small value only groups a few words together, which conflicts with the divisive approach of our hierarchical clustering. On the other hand, the biggest-size ngrams -the most frequent ones -are often common affixes (e.g. tion). A middle ground size could be the mean size of all the generated groups.

-The homogeneity of the generated group, that can be evaluated with: (i) A string distance within the generated group (e.g. edit distance) (ii) The number of ngrams in the generated group. An homogeneous group is expected to have few ngrams. (iii) A ngram distance on those ngrams, like Dice distance (vi) The number of common letters within the generated group words. This idea relates to the further dictionary creation we propose : a high number of common letters means a longer stem.

-The heterogeneity of the generated group. One measure could be the number of other generated groups that contain the ngram. Indeed, we easily imagine that tion is likely to appear in almost every natural conflation group. However, the relation "ng 1 belongs to the generated group of ng 2 " is reciprocal. Therefore, this quantity is precisely the number of ngrams in the generated group of ng 1 (see homogeneity).

-Another intuition while refining this algorithm on English datasets was to penalize ngrams that were likely to be affixes -ngrams whose positions in the words are often either at the beginning or at the end. We feel however that this criteria is highly language-related and thus, in conflict with our rule-free principle.

We finally propose to score the ngrams with the following function :

s(ng i ) = 1 2 × (mean(DiceDistance(N i )) + ||N i | -id.size|)
where N i ⊂ N is the set of ngrams in ng i 's generated group, id.size is the ideal size of a group, namely the mean size of all the generated groups and DiceDistance function returns all the pairwise Dice distance for a set of ngrams. The first member represents the group homogeneity : a low Dice distance between the ngrams of a generated group reflects a group with similar words. The second member penalizes the gap between the ideal and the real size of a generated group. Based on several experiments, we are confident that this scoring function will grant a good score to the ngrams reflecting the real stem of words.

Cutting the dendrogram into clusters

Once the dendrogram is generated, a valuable question is to know how to deduce the groups. Indeed the example of figure 2 shows three possible variants : the example chooses to stop after the second iteration. Though, we could have stopped at the first one, or continue to split another time. We define the depth of the clustering as the chosen number of iterations. A high depth value leads to a very light stemming, with many words stemmed alone or in small groups. This configuration will decrease the risk of overstemming. On the contrary, a low value of depth leads to large and fewer groups. Such an aggressive stemming decreases the understemming error rate, and increases the compression power of the stemmer. Since we think that depth value is highly data-dependent, we do not fix it, and will rather compare the experimental results obtained for different values of depth.

For this first version of the RFreeStem stemmer, we only consider homogeneous value of depth : the clustering process stops at the same iteration for each group. Though, it could have been more accurate to allow groups to have different depths. This approach would have required the definition and implementation of a stopping criteria, to automatically decide when a cluster is considered homogeneous enough. We let that interesting question for a future work extension.

Dictionary generation

The second step of our algorithm aims to generate a dictionary out of the groups previously created. In each homogeneous group W g , this step consists in finding the fix and variable parts in the words of the conflation group. A fix part is defined as a sequence of consecutive letters that can be found in each word of the group. For instance, the group formed by the two words classification and unclarified has two fix parts : cla and ifi. The variable parts are simply the non-fix parts of the words.

In the example, we would respectively find {ss, cation} and {un, r, ed}. The goal is to obtain a dictionary censusing the stems of the group (fix parts) and all the possible values taken by the variable parts, as shown in the last part of Figure 1. In the minimal example of the words classification and unclarified, we actually want to align the matching variable parts, to obtain :

un _ cla r ss ifi ed cation
Yet, the number of variable is not constant. In order to be able to align them, we refine our definition : a variable part v ij is an ngram between the i th and i + 1 th fix parts, with i ∈ [[0; F ]], where F is the number of fix parts in a group, and j ∈ [[1; |W g |]]. For instance here, we have v 11 = r and v 12 = ss. For a given i, the vector

v i = {v ij , j ∈ [[1; |W g |]]
} is the set of all the value taken by the variable parts.

To illustrate the difficulty of finding the fix parts, we extend our example to W g = { classification, declaration, unclarified, clarity, claimed, cleansing, classic }. Of course, obtaining such a heterogeneous cluster is not desirable. Though, in case the scoring function did not behave as expected, the dictionary generation method has to handle such heterogeneity. To find fix parts, we first look for letters that are in every words of W g . We call message types such fix lettersc, l, a and i in the example. For the word clarity, we can immediately deduce the variable parts. Though, for the words declaration, classification and unclarified multiple occurrences of the message types c, i and a appear and we need to know which one is a real fix part. The following table census the frequencies of the fix parts in each words.

clarity claimed cleansing classical unclarified declaration classification min.

c 1 1 1 1 1 1 2 1 l 1 1 1 1 1 1 1 1 a 1 1 1 1 1 2 2 1 i 1 1 1 1 2 1 3 1
We define the perfect examples as the words with the minimum frequencies of each message type -the first four words of the table. We aim to chose, for the words unclarified, declaration and classification, the occurrences of the message types that are fix parts. We call α i the i th occurrence of letter α in a word : in unclarified, i 1 is the i between the r and the f. To decide which occurrences of the message types to keep, we first look at the order in which the fix parts appear. Based on our perfect examples, the order is always c, l, a, i. This helps us chosing the c 1 occurrence of classification rather than c 2 . However, it does not promote any of the a and i occurrences in the three problematic words. We therefore add another feature to the selection : the gap between the fix parts for each perfect example. This value cannot be calculated for the other words, since we would not know which occurrence to chose.

gap lengths clarity claimed cleansing classical mean interquartile range cl

1 1 1 1 1 0 l -a 1 1 2 1 1.25 0.25 a -i 2 1 3 2 2 0.5
The mean of the gaps can be seen as the ideal gaps that should separate the fix parts.

For unclarified, the gap between a and i 1 is 2, and between a and i 2 is 4. Therefore, we successfully select the i 1 occurrence. Moreover, for classification we have the following gaps between occurrences of a and i :

a-occurrence i-occurrence occurences gap expected gap difference with expected

a 1 i 1 3 2 1 a 1 i 2 5 2 3 a 1 i 3 9 2 7 a 2 i 3 2 2 0
However, the huge gap between a 2 and l will fortunately have us chose a 1 -since we take the mean of the gaps. Nevertheless, it not sufficient for the word declaration :

a-occurrence observed difference with expected mean difference l -a a -i l -a a -i a 1 1 4 0 2 1 a 2 3 2 2 0 1
Indeed, the two occurrences of a are assigned the same score. We therefore add a last feature to our decision method : a measure of gap stability. In the previous example, we observe that the gap between the letters l and a has more stable values than the gap between a and i. Hence, the difference between the real and the ideal values of the gap should take into account the reliability of the gap. Thus, we propose to calculate the interquartile range of each gap (last column of table 2). This interquartile is inversely proportional to the attributed to the gaps. In our example, since the relation l -a is quite stable, it will be highly penalized for a 2 to have an extra gap of 2. The a 2 occurrence will finally be chosen as a fix part. With all the defined process of fix part selection, we simply deduce the variable parts as the variable letters and the unselected common letters. We obtain, in our example, the wanted result :

   un de _ cl e _ a            r ns ss arat _ i                    ty med ng cal fied on fication
The stemmed extracted from this group could then be _cl_a_i_. In practice, we hope not to obtain such an heterogeneous group. In a well-formed group we can hope to have more intelligible stemmers like _classif_ or _clar_. This new version of the generated stem could enhance string comparison results, which might be needed in NLP tasks. Moreover, dictionary look-ups will be easier for the user.

Evaluation

We propose to assess the results of our implementation of the RFreeStem stemmer. We aim to demonstrate that our stemming method offers better accuracy results than the traditionally used Porter stemmer, while proposing a better compression power. To do so, we propose to run our stemmer and Porter's on raw data before the application of a NLP task.

Evaluation framework

Our evaluation is divided in two discussions : the efficiency of our stemmer in two different text mining tasks in English, and the comparison of this efficiency depending on the language of the corpus. For each discussion, we will compare the different versions of our algorithm -due to the possible values of the depth of the cut -with both Porter's and the unstemmed data.

Task 1: Text categorization is a popular text mining task that aims at automatically determining the class of a document within a corpus. To test the efficiency of our stemmer as a preprocessing step for text categorization, we implemented our method on the AustLII case report corpus 2 . We retrieved 6480 citations out of 717 different XML files. Those files contain both the text of the legal citation and a labelled category, among the following : cited referred to applied followed considered discussed Others(12) 2847 1372 715 529 361 323 170

Our dataset is highly imbalanced since 43.9% of the citations have the label cited, whereas half of the classes only contains 1.25% of the data. Imbalanced datasets are reputed to be harder to process, so it will be interesting to see if our stemmer can help in that matter.

Task 2: Sentiment analysis has become a very popular task, in particular with the high expansion of social networks and their textual data. The aim is to evaluate sentiments in human written comments or reviews. To evaluate the ability of RFreeStem to can improve the results of this complex task, we chose the commonly used movie review dataset 3 . Firstly mentioned in [START_REF] Pang | A sentimental education: Sentiment analysis using subjectivity summarization based on minimum cuts[END_REF], the corpus is still popularly used today [START_REF] Ba | Layer normalization[END_REF], [START_REF] Shen | Disan: Directional self-attention network for rnn/cnn-free language understanding[END_REF]. It contains 10662 perfectly balanced reviews of movies, with 18196 different terms.

Since the state-of-the-art seems to agree that stemming is more adapted to inflectional languages, we propose to compare our stemming on related datasets from different languages. We therefore studied the amazon reviews in French and German 4 for sentiment analysis task (Task 2). Among the large amount of available data, we chose, for each language, a sample of 2000 reviews, respectfully of the proportion of positive and negative labels. Since the products are evaluated with a rating from 1 to 5, we extracted the binary labels with the following simple transformation rule : if the rating is strictly over 3, assign to positive class. Otherwise, assign to negative. We obtain the following datasets: Similarly to the full datasets, the reviews are highly imbalanced, which allows us to test the robustness of our stemmer. We also note that German has more than 30% features more than French. Indeed, besides being highly inflective, German language tends to compose new words by juxtaposing two smaller ones. Moreover, it uses declensions to construct its articles and adjectives, which adds a large variety of word variants. German therefore seems like a perfect fit for stemming algorithms.

Language #reviews
Finally, since our method is corpus-based, we claim that it is not language-dependant and could be applied on any language, especially the rarely documented ones, where it is hard to find a Porter-like stemmer. We propose to study a rare Roman Urdu data set 5 for a 3-class sentiment analysis (Task 2): The process we apply is as follow : for each dataset, we apply the different versions of our method to the whole raw data and therefore generate a stemming dictionary where each entry is a {word: stem} couple. As mentioned before, we want to observe the effect of the depth of the cut on the results. Therefore, we generate as many dictionary as we have candidate depths for the cut. Thanks to the study of [START_REF] Harman | How effective is suffixing[END_REF], we have the idea of chosing to use 4-grams, that seem to be the most relevant, both on analytic and inflective languages.

#
We then run a supervised classification algorithm on different versions of the data : the raw data (pre-processed without stemming), the Porter data (pre-processed and stemmed with Porter stemmer) and all the d-RFreeStem data (pre-processed and stemmed with our algorithm, cut with a depth of d). We choose to train a Naive Bayesian classifier on 70% of the data, respecting the proportion of the labels. The 30% left are predicted with the trained classifier and the results are compared with their labels. To select the classifier input features, we simply calculate the documentterm matrix, and sort the features in decreasing frequency order. For each configuration, we run several versions of the feature selection step. While i is less than max(f eature.f requencies), we select the features whose frequency is at least i. Each value of i gives a different number of features as input of the classifier. For each stemmer, we run several times all the features selection step to have a robust mean value.

Results and discussions

By running 20 times all the version of our algorithms, Porter's and the raw version, for all the possible feature selection configurations, we obtain the results presented in that subsection. As a measure of result improvement, we calculate the traditional Fmeasure, as well as the accuracy. We also evaluate the ICF value, to measure the 5. http://archive.ics.uci.edu/ml/datasets/Roman+Urdu+Data+Set, [START_REF] Sharf | Performing natural language processing on roman urdu datasets[END_REF] compression power of the understudied stemmer. Firstly, let us compare the accuracy obtained in the two English mining tasks. We observe slighlty different results on those two evaluations. In the classification task, stemming systematically improves the results. The most aggressive versions of our algorithm 2-RFreeStem performs better than Porter, while 3-RFreeStem and Porter present similar results. Yet, the accuracy range is rather law : multiclass categorization seems to be a hard task to be applied on documents, and stemming can significantly help preserving a correct level of prediction. On the other hand, the sentiment analysis results are lukewarm. Almost all the stemming methods deteriorate the accuracy compared to the unstemmed version, apart from our most aggressive stemmer 2-RFreeStem. The movie review is also reputed to be a difficult task and it seems that stems might have masked the discrimination out of the variant forms of the words. Moreover, as explained before, better results are expected on inflective languages. To prove it, we compare this last result to the Amazon review ones.

Since French is a highly inflective language, each root has many variants and thus many words can be stemmed together while respecting their meanings. However, let us note that this corpus regroups human informal speeches. In informal speech, French tends to be less inflective : we would rather say not happy than unhappy. Nevertheless, our two most aggressive versions perform well and better than Porter (Figure 4). Similar results are observed with German texts, where 4 of our algorithms have at least one configuration where they outperform Porter, which struggles to reach the unstemmed performances. Actually, there is a clear segregation between Porter or the unstemmed version and our methods. This makes us think that our stemming algorithm is well adapted for German. Indeed, Porter stemming does not include any treatment for complex composed words, whereas [START_REF] Braschler | How effective is stemming and decompounding for german text retrieval?[END_REF] argues that decompounding task is an even more decisive factor than stemming for the German language. On the other side, our algorithm is theoretically capable of retrieving such complex linguistic structures, which can explains those encouraging results. Eventu- Amazon reviews dataset for a binary sentiment analysis ally, those two highly inflective languages clearly show the compression power of our stemmer. Indeed, the maximum number of features for the unstemmed version is far greater than for our methods, due to the important vocabulary reduction performed.

We naturally also detect a slight difference in that matter between the d-versions of our algorithms : the lower d value, the lower maximum number of features.

Finally, we propose to see how our method behaves on a poorly documented language as Urdu. For this language, we did not have a Porter version implemented and therefore only compared our results to the unstemmed one in Figure 5. We discover that only our most aggressive version can compete with the raw data. The improvement observed is far from being significant, but at least, we take satisfaction in proposing a method that will not deteriorate the accuracy for this left-behind language. To conclude, the following table summarizes the evaluation features we wanted to observe: (i) F1 is the best F1 measure (over #features), (ii) is similarly the best accuracy value and ICF is the index compression factor of the method. For the English version, we took the AustLII data since it is wider and shows more sensitivity to stemming. The following results are presented in percentage. The best result are often obtained by our 2-RFreeStem version. This fact might be disappointing : in this version, only one clustering step is achieved, and no hierarchical tree is ever created. With this actually flat clustering, our method only consists in clustering the words depending on one of their 4-grams. A very similar method is proposed by [START_REF] Pande | Generation, implementation and appraisal of an n-gram based stemming algorithm[END_REF], yet they sort the ngrams very differently. However, our 3-RFreeStem version has sometimes proven more accurate (accuracy in French, F1-measure in German), and we argue that an even better solution could be found in refining our cutting algorithm. According to the results, for every groups created in the first splitting iteration, we could either chose to stop there or to split one more time, depending on an homogeneity criteria that is still to be defined.

Conclusion

Stemming is still systematically used as preprocessing step for text mining tasks. Since the sensitivity of stemming is highly language-dependant, we have proposed a multilanguage rule-free stemmer, based on corpus data. We have shown that it outperforms the famous Porter algorithm, and that its performance are even more spectacular on inflectional languages. An improvement of our method could be done by refining our dendrogram cutting method, thanks to a group homogeneity criteria. Moreover, instead of always working with 4-grams, we will soon try to enable the variation of the n length. We could also have proposed a wider evaluation framework by (i) analyzing the RFreeStem performance on agglutinative or rare languages (ii) assessing our stemmer accuracy improvement on Informational Retrieval, and even, since it is multilingual, on Cross Language Information Retrieval (iii) confronting our stemmer to other corpus-based methods, like [START_REF] Soricut | Unsupervised morphology induction using word embeddings[END_REF]. We let those interesting questions opened for a future contribution.

  Figure 1. The general approach of RFreeStem stemmer. First step (1) is presented in section 3.1. Second step (2) is detailed in section 3.2

Figure 2 .

 2 Figure 2. The clustering method (1) with (a) the recursive division (see 3.1.1) and (b) the dendrogram cutting (see 3.1.3

Algorithm 1 :

 1 Divisive step algorithm input : A set of (unique) words W , an integer n; // n as in ngram output: A set of word groups 1 ngram.set ← findnGram(words = W , n = n); 2 ngram.set ← scoreFunction(set = ngram.set); 3 ngram ← first(ngram.set); 4 G ← emptyGroup(); 5 while ngram != last(ngram) and size(W) > 0 do 6 matching.words = grep(pattern = ngram, set = W); 7 if 0 < size(matching.words) < size(W) then 8 remove(elementsToRemove = matching.words, set = W); 9 g ← createGroup(elements = matching.words); 10 addGroup(element = g, group = G); 11 end 12 ngram = next(ngram); 13 end 14 return G;

Figure 3 .

 3 Figure 3. Accuracy comparison for different #features between (Task 2) movie reviews binary classifier and (Task 1) AustLII multinomial classifier

Figure 4 .

 4 Figure 4. Accuracy comparison for different #features between French and GermanAmazon reviews dataset for a binary sentiment analysis

Figure 5 .

 5 Figure 5. Comparison of the accuracy of the binary classifier prediction on Roman Urdu data for different #features

English language is actually slightly inflectional, due to its heritage of old English. Thus, modern English is more fit for stemming than purely isolating languages like Mandarin or Indonesian[START_REF] Moral | A survey of stemming algorithms in information retrieval[END_REF].