Arnaud Vena
email: arnaud.vena@ies.univ-montp2.fr

Etienne Perret
email: etienne.perret@lcis.grenoble-inp.fr

Brice Sorli

Smaïl Tedjini

Theoretical Study on Detection Distance for Chipless RFID Systems According to Transmit Power Regulation Standards

Keywords: chipless RFID, UWB, read range, radar. I

This paper address the problematic of estimating the performance of chipless RFID systems operating in the UWB band from 3.1GHz to 10.6GHz. For this purpose, a model which takes into account chipless tags' characteristics such as RCS and quality factor is proposed to better estimate the theoretical detection distances. Chart showing theoretical detection distances as a function of the frequency and for various RCS levels are derivate from radar equation according to the radiated emission limit set by transmit power regulation authorities. Detection ranges are estimated according to two different approaches, the continuous wave based radar technique, and the impulse radio based radar technique.

INTRODUCTION

Research activity around chipless RFID technology [START_REF] Costa | A Chipless RFID Based on Multiresonant High-Impedance Surfaces[END_REF][START_REF] Mandel | A wireless passive strain sensor[END_REF][START_REF] Amin | A novel EM barcode for humidity sensing[END_REF][START_REF] Vena | Design of Chipless RFID Tags Printed on Paper by Flexography[END_REF][START_REF] Vena | A fully printable chipless rfid tag with detuning correction technique[END_REF][START_REF] Vena | Design of compact and autocompensated single-layer chipless rfid tag[END_REF][START_REF] Vena | A Depolarizing Chipless RFID Tag for Robust Detection and Its FCC Compliant UWB Reading System[END_REF] is getting more intense every year. Researchers are motivated by key features that could make this technology really attractive from the side of major actors of the consumer market, as well as the internet of things (IoT). In the world of identification, the current situation is that industrials see the passive RFID [START_REF] Finkenzeller | Rfid handbook: fundamentals and applications in contactless smart cards, radio frequency identification and near-field communication[END_REF] as a great technology but still too young to propose a true global system able to compete with the optical barcode, which is today the biggest market of identification worldwide with tens of trillion units sold per annum. Indeed, a conventional RFID tag contains an antenna connected to an IC. The estimated unit cost is close to 0.1$. Even if it is low, this price is still too expensive for most of the goods sold in the consumer market. That is why chipless RFID has a key role to play in the coming years. As an alternative to chipped tags, a chipless tag is made of an antenna or scatterer only, so that it can be realized with a single step process, using roll to roll industrial printing techniques. In this case, the achieved unit cost has been recently estimated at 0.004$ with flexography printing technique [START_REF] Vena | Design of Chipless RFID Tags Printed on Paper by Flexography[END_REF]. But the weak point of this technology is the reading system which is still not properly defined, and not standardized. In the state of the art it is very hard to find a study addressing clearly the following points:  What is the expected read range of a specific chipless system?  What it the operating bandwidth? And does it fit the specific power emission limit for these specific operating frequencies so that we could potentially sell this product?

For example, most of chipless tag designs encoded in the frequency domain require an ultra large bandwidth (above 500 MHz) to operate. However, it is quite difficult to develop a reader based on the emission of continuous waves (see Fig. 1 (a)) in the frequency band between 3.1 and 10.6 GHz because we face hurdles regarding the authorized transmitting power for frequencies located outside the ISM bands. These power values are very weak (below -41.3dBm/MHz in the best case). Alternatively, a temporal approach based on impulse radio radar as shown in Fig. 1 (b) has the major advantage of spreading the power over the entire band of interest so that it is possible to detect the whole frequency response of a remote chipless tag with a short single pulse. In this case, the energy is concentrated in a very short time, resulting in a high instantaneous radiated power but a very low average power compatible with usual standards. In section II, we are doing a review of the transmit power regulation standards for UWB devices. Then, in section III, we give a method to estimate the read range of a chipless tag for reading system operating in the frequency domain. Before concluding, in section IV we focus on a mean to estimate detection distance in case of an impulse-radio based approach, in respect of the regulation standards.

II. REVIEW ON THE TRANSMIT POWER REGULATION

STANDARDS

The growth of the chipless RFID is conditioned by the development of a reader meeting the standards. We need to fit the power mask within the bandwidth of interest, that is, from 3.1GHz to 10.6GHz. This mask refers to the level of power one can radiate into space, and without any special authorization. Fig. 2 shows the mask for the authorized transmit powers defined by the regulatory authorities: the FCC (Federal Communications Commission) in the United States; the European Telecommunications Standards Institute (ETSI) in Europe. ISM bands whose use is not subject to licensing and for which relatively high power are available may not be suitable for our application because they are very narrow. On the other hand, to detect typical largely spread electromagnetic chipless tags' signatures over the frequencies, it seems to be judicious to use the Ultra Wide Band (UWB). In this case, the FCC mask defines a transmit power limit of -41.3 dBm / MHz between 3.1 GHz and 10.6 GHz. The Electronic Communication Committee (ECC) mask in Europe is much more restrictive and imposes a very low emission level between 4.8 and 6 GHz, as well as beyond 9 GHz. So we have a bandwidth of 7500 MHz with the FCC, and 4700 MHz with ECC. It is to be noted that for a hypothetical signal for which, the spectral content spreads throughout the full band, that is 7500 MHz, the average power is -2.54 dBm.

If the UWB standard is applied to continuous-wave based radar as that described in the next section, the transmit power is extremely low, namely -41.3dBm for a "monochromatic" wave with a bandwidth of 1MHz. It is true that, the level defined in ETSI EN 302 065 standard [START_REF][END_REF] for UWB short distance devices give a limit of -41.3dBm / MHz for the calculation of average power spectral density. However, the maximum peak power (EIRP) authorizes a value below or equal to -24.4 dBm, when measured with a spectrum analyzer having a resolution bandwidth of 3MHz.

III. FREQUENCY-DOMAIN BASED RADAR SYSTEMS

According to most of the chipless systems, the frequency band of interest is spread between 2 GHz and 10 GHz. Thus, we have to make a power budget for several frequencies within this band. Given the operating frequencies, and the dimensions of the tags, we can assume that the chipless tags operate in farfield zone. Therefore we can use the radar equation to estimate the received power reflected from the tag. This power is correlated with the radar cross section (RCS) of the tag as in (1) [START_REF] Balanis | Antenna theory: analysis and design[END_REF]. It is noteworthy that RCS is a value independent of the distance of detection. An estimation of the detection range can be calculated with (2) derivate from (1).

(1)

(2)

For systems encoding information in the frequency domain, the information is correlated with the variation of the RCS as a function of the frequency. In all cases the receiver must be able to detect a minimum value of the RCS. This is the limiting value that fix, for a given frequency and a given distance, the transmitting power and the reception sensitivity. If the noise level is above the receiver sensitivity, it is necessary to readjust the transmit power value. From (2) we can plot the relationship (see Fig. 3) giving the theoretical detection range as a function of the frequency for several RCS values between -60 and -30 dBm². As aforementioned in previous section, with a CW based detection approach which consists in scanning the overall frequency bandwidth (several GHz), the maximum peak power (EIRP) authorized has to be equal or below -24.4 dBm for a resolution bandwidth of 3MHz. This value is much lower than usual communication systems limits operating in the ISM bands. The power sensitivity Prx is chosen to be equal to the noise floor, measured at -80 dBm for a commonly used radiofrequency receiver. The gain or the receiving antenna is Grx=10, whereas the gain of the transmitting antenna is supposed to be Gtx=1 when dealing with EIRP power.

For a usual chipless tag [START_REF] Costa | A Chipless RFID Based on Multiresonant High-Impedance Surfaces[END_REF][START_REF] Mandel | A wireless passive strain sensor[END_REF][START_REF] Amin | A novel EM barcode for humidity sensing[END_REF][START_REF] Vena | Design of Chipless RFID Tags Printed on Paper by Flexography[END_REF][START_REF] Vena | A fully printable chipless rfid tag with detuning correction technique[END_REF][START_REF] Vena | Design of compact and autocompensated single-layer chipless rfid tag[END_REF][START_REF] Vena | A Depolarizing Chipless RFID Tag for Robust Detection and Its FCC Compliant UWB Reading System[END_REF], the peak magnitude of resonant modes is above -35 dBsm in the worst case. In order to distinguish clearly a peak, a dynamic of 10dB from the maximum level is necessary. Thus, we have to detect a minimum RCS level of -45 dBsm. According to Fig. 3, at 2 GHz, the maximum detection range is close to 0.3 m for a RCS=-45 dBsm. At 10GHz, the detection range is reduced to    0.15 m. In the best case, when the peak magnitude is close to -20 dBsm so that we need to detect a minimum RCS level of -30 dBsm, things are better, but still, the read range is not very large. At 2GHz, we obtain a detection distance of 0.47m, whereas at 10GHz we obtain 0.2m. These values give us an idea on the read range that we are expected to have according to an interpretation of the ETSI standard on UWB systems for continuous waves based radar. We will see in next section that detection systems based on the emission of picosecond pulses, may help to achieve larger reading distance with the same constraints.

IV. TIME-DOMAIN BASED RADAR SYSTEMS

An impulse radio based radar approach has the major advantage of sensing the entire frequency response of the tag with a single pulse. In this case, the energy is concentrated in a very short time, which provides a high instantaneous transmit power while maintaining a low average power, compatible with regulation standards for UWB communication.

A minimum repetition rate, or pulse repetition frequency (PRF) is set at 1 MHz by the ETSI and 400 kHz by the FCC to limit the instantaneous power. If we use a PRF of 1 MHz, that is one pulse per µs, we can find that a power of -2.54 dBm during 1µs gives energy of 557 pJ. It is therefore necessary to optimize the distribution of this energy to fit the transmit power mask shown in Fig. 2. Specific pulse shapes such as the 5 th derivative of a Gaussian pulse (see Fig. 4) can be used to fit the FCC indoor mask dedicated to systems inside the buildings. This waveform covers the whole bandwidth of 7500MHz centered at 6.85 GHz. The amplitude of the peak is 8 V, which corresponds to energy of 113.7pJ that is much lower than the maximum authorized value of 557 pJ.

As shown in Fig. 4, this signal spreads over a time Tp=600 ps. The duty cycle is 600ps/1µs that is 1 per 1667. In terms of power, this gives a gain G RC (3) of 32.2dB within this short duration of 600ps to compare with the same energy consumed in 1µs.

(3) However, we should consider that the response of the tag is not instantaneous so that we need to sample its response for a longer time than 600 ps. To estimate this duration, we need to consider quality factor (4) of tag's resonant modes. First we can say that the response time is longer when the resonance frequency is low. Thus, the longest response time is obtained for the lowest frequency for a given chipless tag. We consider the minimum frequency at 3.1 GHz to operate in the UWB. A resonant mode with a bandwidth of 50 MHz (which is conventionally used in chipless RFID) gives a quality factor equal to 62 at 3.1 GHz according to (4). As stated in [START_REF] Vena | Design Rules For Chipless RFID Tags Based on Multiple Scatterers[END_REF], resonant modes can be modeled by second order transfer functions. For a second order resonant system, using (5) we obtain the response time Trep n% at n% for a given center frequency f 0 and a quality factor Q. For example, for a resonance frequency of 3.1GHz and a quality factor of 62, we obtain a response time of 19 ns. We can therefore conclude that most of resonant modes created by chipless tags operating in the UWB band release most of their energy in less than 20 ns.

(4) [START_REF] Vena | A fully printable chipless rfid tag with detuning correction technique[END_REF] Using (3) with a time Tp =20 ns, we obtain a power gain of 50, that is 17 dB in log scale. Then, in order to extract the received power P rx (f) associated with each spectral component, we multiply the received PSD by the bandwidth (equal to the frequency resolution of the system), and by the duty cycle gain introduced in (3). We obtain [START_REF] Vena | Design of compact and autocompensated single-layer chipless rfid tag[END_REF] replacing the resolution frequency df by its equivalent expression [START_REF] Vena | A Depolarizing Chipless RFID Tag for Robust Detection and Its FCC Compliant UWB Reading System[END_REF] which corresponds to the inverse of the observation time T rx . Using [START_REF] Vena | A Depolarizing Chipless RFID Tag for Robust Detection and Its FCC Compliant UWB Reading System[END_REF] with T rx = 20ns, we find a frequency resolution of 50 MHz.

p RC T PRF G   1 0 f f Q   ) / 100 ( log 0 % n f Q Trep e n  
A power budget can be calculated injecting the PSD and the frequency resolution into the expression of the radar equation ( 1) to obtain a novel equation [START_REF] Finkenzeller | Rfid handbook: fundamentals and applications in contactless smart cards, radio frequency identification and near-field communication[END_REF]. In this equation, we use directly the power spectral density EIRP term PSDeirp so that the gain of the transmitting antenna no longer appears. However the gain of the receiving antenna G rx is still present.

With the pulse previously defined, that is to say compatible with the FCC indoor mask, using [START_REF] Finkenzeller | Rfid handbook: fundamentals and applications in contactless smart cards, radio frequency identification and near-field communication[END_REF] we plotted in Fig. 5, the theoretical detection distance as a function of the frequency for several RCS levels. The gain of the receiving antenna is set to 10 dB. We can observe that ranges between 0.5 m and 1.5 m can be achieved over the entire frequency band for an object with a minimum RCS value of -45 dBm². For a minimum RCS value of -30dBsm, this range rises up to 1m to 2.7m. This is a very interesting result, because it shows that impulse radio UWB based radar, whose transmit power fit the FCC indoor mask, achieves larger detection ranges than continuous wave based greater than 0.5 m.

V. CONCLUSION

We presented a theoretical study on the determination of theoretical detection ranges that we can achieved for chipless RFID systems operating from 3.1 GHz to 10.6GHz, while considering the transmitting power limit values defined by the ETSI and the FCC regulation authorities. We find out, that continuous wave based radar systems can achieved detection range up to 0.47 m in the best case, that is for a tag's RCS of -20dBsm, whereas a detection range up to 2.7 m is possible for an impulse radio based radar system. This better performance is correlated with the high instantaneous power permitted by a picosecond pulse while keeping a low average power. In a future work the proposed theoretical model will be verified by practical measurements for both radar approaches.

Fig. 1

 1 Fig. 1 Basic principle of chipless RFID system baed on (a) Frequency Stepped CW based radar (b) Impulse radio based radar.

Fig. 2

 2 Fig. 2 Emission mask defined by the FCC and the ECC and power spectral density of the 5th derivative of a Gaussian pulse.

Fig. 4 Fig. 3

 43 Fig. 4 Waveform of the fifth temporal derivative of a Gaussian pulse.

Fig. 5 (

 5 Fig. 5 (a) Theoretical detection range chart calculated with (8) as a function of the frequency, and for RCS values set to -60, -50, -40, and -30 dBsm. The pulse shown in Fig. 4 is transmitted to the tag. The noise floor is set at Prxmin=-80 dBm.

ACKNOWLEDGMENT

The authors would like to thanks the University of Montpellier 2 and Grenoble-Inp for their support.


Arnaud Vena
email: arnaud.vena@um2.fr

Etienne Perret
email: etienne.perret@lcis.grenoble-inp.fr

Brice Sorli
email: brice.sorli@um2.fr

Smail Tedjini
email: smail.tedjini@lcis.grenoble-inp.fr

Study on the detection reliability of chipless RFID systems

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

Introduction

For several years, chipless technology [START_REF] Costa | A Chipless RFID Based on Multiresonant High-Impedance Surfaces[END_REF][START_REF] Mandel | A wireless passive strain sensor[END_REF][START_REF] Amin | A novel EM barcode for humidity sensing[END_REF][START_REF] Vena | Design of Chipless RFID Tags Printed on Paper by Flexography[END_REF][START_REF] Vena | A fully printable chipless rfid tag with detuning correction technique[END_REF][START_REF] Vena | Design of compact and auto-compensated single-layer chipless rfid tag[END_REF][START_REF] Vena | A Depolarizing Chipless RFID Tag for Robust Detection and Its FCC Compliant UWB Reading System[END_REF] appears as a new promising field of research of the radio frequency identification (RFID) [START_REF] Finkenzeller | Rfid handbook: fundamentals and applications in contactless smart cards, radio frequency identification and near-field communication[END_REF]. Industrials see chipless RFID as a promising technology but still too young to propose a true global system able to compete with the optical barcode, which is today the biggest market of identification worldwide with ten trillion units sold per annum. Indeed, a conventional RFID tag contains an antenna connected to an IC. The estimated unit cost is close 0.1$. Even if it is low, this price is still too high for most of the goods sold in the consumer market. As opposite to a chipped tag, a chipless tag is made of an antenna only (see Fig. 1 (a), (b) (c)), so that it can be realized with a single process, using roll to roll industrial printing techniques. In this case, the achieved unit cost has been recently estimated at 0.004$ with flexography printing technique [START_REF] Vena | Design of Chipless RFID Tags Printed on Paper by Flexography[END_REF]. Now that we know how to make a chipless tag with a very competitive price, the question is how to detect this tag with a reading system, at least as reliable as for optical barcodes?

In this paper, we propose several techniques to overcome the common hurdles that we encounter when dealing with chipless technology, illustrated in Fig. 1 (a). In section 2, we study a solution to handle the detuning of ungrounded chipless tag. Then in section 3, we present a design optimized for a reliable detection among highly reflective objects such as metallic objects. Finally, in section 4 before concluding we discuss about a technique to remove the effect of concurrent wireless channels that may interfere with the resonant frequencies of chipless tags.

Improving the detuning by using additional sensing scatterers

A tag designed to operate in free space will not likely work when this specific tag is placed on an object having a permittivity higher than one. This is especially true when this tag has no ground plane because the fringing field is spread all around so that most of the electrical field lines generated by the tag's response cross the object. When the ID relies upon the detection of magnitude or phase shifts for a given frequency span, this can be problematic. In this case, a frequency shift of the tag's response means that the ID will be corrupted.

Using a ground plane is obvious to overcome this issue. Indeed if a chipless tag is designed so that it behaves like a patch antenna, the fringing field only stays close to the boundaries of the patch like a dual slot antenna. If the ground plane is large enough, this means that the fringing field will never get into contact with the material back to the ground plane. This technique is well used in most of the design of chipless tags and sensors [START_REF] Costa | A Chipless RFID Based on Multiresonant High-Impedance Surfaces[END_REF].In some other cases, to reach the unit cost of optical barcodes, chipless tags are designed with a single conductive layer, without any ground plane so that we cannot avoid the detuning of the resonant modes. Physically, the resonant mode frequencies are linked to the effective permittivity around the scatterer. Thus depending on the object to identify, this effective permittivity can vary a lot. One way to handle this issue is to add one or more resonators, which do not participate to the coding but play the role of effective permittivity sensors [5;6]. Previous works in [START_REF] Vena | A fully printable chipless rfid tag with detuning correction technique[END_REF] proved that a frequency shift up to 120 MHz can be compensated with an error on the initial resonant frequency of 25 MHz. To explain this technique let's start with a generic relationship between a physical length L of a half-wavelength scatterer and its first resonant frequency f res as in equation [START_REF] Costa | A Chipless RFID Based on Multiresonant High-Impedance Surfaces[END_REF]. The effective permittivity is given in ε eff .

eff res w L c f    (1) 0 0 effres m effres res m res f f          (2) effsens effres k     (3)              0 0 sens m sens res m res f f f f (4)         m sens sens m res res f f f f 0 0 (5)
If we define f m res (respectively ε m effres ) as the frequency (respectively the effective permittivity) value of the resonator subject to the detuning effect of an object, and f 0 res (respectively ε 0 effres ) its value in free space, we can divide both terms to find the equation ( 2). If using one resonator for coding and one resonator for calibration (the index sens is used to note this specific resonator), which is not used to encode information and its frequency changes only if the effective permittivity around it is varying, we can assume that the permittivity between the two resonators is linearly correlated with a constant value k as in [START_REF] Amin | A novel EM barcode for humidity sensing[END_REF]. This is considered to be true whatever the surrounded environment. Based on this assumption, we can equate the two fractional equations as in [START_REF] Vena | Design of Chipless RFID Tags Printed on Paper by Flexography[END_REF]. We obtain the equation ( 5) giving a relationship between the resonant frequency of a coding resonator in free space (f 0 res ), and those measured on an unknown object for both the coding (f m res ) and the calibration resonator (f m sens ). In Fig. 2 (a) we present the measured frequency shift on the first resonant mode (at 2 GHz) of the 20 bits chipless tag as a function of the material, put in contact back to the tag, and for various thicknesses. One can notice a deviation up to 100 MHz for cardboard above 1 mm of thickness. As shown in Fig. 2 (b), the resonant modes of the tag are all shifted toward the lower frequencies to compare with the free space response. One can note that even though the magnitude of the EM response is not recovered, when we apply the aforementioned post-processing technique on the detuned tag's response, all the resonant mode making the ID, get back to their initial frequency value.

Improving the isolation of the tag's response amid the background response

In chipped RFID, the tag backscatters two different powers by modifying dynamically its RCS between two states; meanwhile the response from the environment stays the same. Thus, the effect of the environment is mitigated by the detection of this power variation. A chipless tag sends only one static response making its extraction more difficult when we consider the EM responses of the surrounding objects. Extracting the weak tag's response amid the strong environment response is the biggest challenge in chipless RFID.

Technique of volume gating

The first technique that we can use to lower the tag's response is based on time gating, which means that we limit the measurement time. When the measurement is done in the frequency domain, this technique can be applied by post-processing technique (convolution with the Fourier transform of a rectangle window for example). When combined with a narrow beam antenna we can introduce the concept of volume gating (see Fig. 3 (a)) for which a volume detection is defined by the traveled distance of the tag's EM response within the time gate and the aperture of the antenna. In the top of mitigating the response from the environment, this technique allows removing the multiple echoes of the tag's response, and performs the signal to noise ratio (SNR). However, a tradeoff should be found between the sharpness of the resonant peaks which can be detected and the SNR. As an example, a resonator having a 3 dB bandwidth of 50 MHz at 3.1 GHz delivers 95% of the stored energy in 20 ns, which corresponds to a 3 m roundtrip in free space. The minimum window size in this case is 20 ns for 50 MHz of frequency resolution. The curves shown in Fig. 2 (b) and in Fig. 3 (c) are obtained after having applied a time gating of 200 ns, which is enough in this case to remove ripples on the frequency response.

Using depolarizing scatterers

Another technique that we discuss here has been validated in [START_REF] Vena | A Depolarizing Chipless RFID Tag for Robust Detection and Its FCC Compliant UWB Reading System[END_REF] for some difficult cases, especially when the detection environment is composed with metallic objects or liquids. Indeed, because of their good conductivities and their huge size compared with a usual chipless tag, a metallic object or a bottle filled with liquid have large RCSs. When these objects are located in the same phase plane as for the tag, volume gating cannot be used to separate EM responses. For this case, the use of depolarizing scatterers may provide a solution to detect chipless tags. The reason comes from the fact that usual object such as a metallic plate or a water bottle don't depolarize. In other words, this means that when an EM wave impinges on their surface, they reflect a specific response in the same polarization (co-polarization). With a tag based on depolarizing scatterers, the reflected wave is shared between the co-polarization and the cross-polarization. A receiver which detects the cross-polarized response, as regard as the incident wave, will record mostly the useful EM response form the tag, isolated from the environment response. The environment commonly reflects the incident wave, mainly in the co-polarization. The curves in Fig. 3 (b) confirms this assumption showing the responses from the environment in co-polarization and in cross-polarization for a pack of metallic cans. In Fig. 3 (c) we can observe the EM response of a depolarizing chipless tag put on one of the metallic cans aforementioned. The eight resonant peaks can be detected and decoded in order to give the correct ID. This shows the high reliability of the design to compare with resonators generating a resonant mode only in co-polarization [START_REF] Vena | Design of Chipless RFID Tags Printed on Paper by Flexography[END_REF][START_REF] Vena | A fully printable chipless rfid tag with detuning correction technique[END_REF].

Reducing the interferences from concurrent wireless systems

In many cases, except in an anechoic chamber, concurrent wireless systems using ISM bands may disturb the chipless tag system utilizing the same frequency bands. In chipless technology, there is no intelligence embedded in the tag, so no modulated signals and no anti-collision management are implemented. However the EM response of the tag is supposed to be always the same whatever the interrogation time or the power (a chipless tag is a linear device). Thus, we can use multiple measurements in order to increase the SNR of the desired tag's response. For that, we make the assumption that modulated signals of concurrent systems sharing the same frequency bands vary randomly as a function of the time to compare with the chipless tag response. To remove the effect of the concurrent signals we can apply an averaging filter on N measurements as in [START_REF] Vena | Design of compact and auto-compensated single-layer chipless rfid tag[END_REF] in which Tagresp i (k) is the sample k of the tag's response and Srf i (k,t) is the environment response of the sample k took for the starting time t. When the number N is large enough (N>10), the term Srf i (k,t) is mitigated so that it can be considered as null (like in [START_REF] Vena | A Depolarizing Chipless RFID Tag for Robust Detection and Its FCC Compliant UWB Reading System[END_REF]) to compare with the tag's response which remains the same whatever the starting time of the acquisition. We performed the measurements shown in Fig. 2 (b) and in Fig. 3 (c) based on an averaging on 10 measurements in an indoor environment surrounded by WIFI and GSM wireless systems. We didn't observe the resonant peak at 2.45 GHz due to the WIFI showing the validity of the technique.

Conclusion

In this article, several techniques are studied and implemented in order to perform the detection reliability of chipless tags in real environments. To address the problem of detuning, we introduced and successfully validated an autocompensation technique that relies upon the use of additional calibrating resonators. To make the detection of chipless tags possible in a real environment we studied the concept of volume gating combining the time gating to control the detection depth and the aperture of the antenna. In the case when highly reflective objects such as metallic plates or bottle of water are in the same phase plane, we proposed a design based on depolarizing resonators allowing an efficient separation of environment and tag's response. Finally, using repetitive measurements and with the utilization of an averaging filter, it was possible to detect chipless tags amid concurrent wireless communication systems.

Figure 1 .

 1 Figure 1. (a) Chipless system in indoor environment. (b) Single layer 20 bits chipless tag using two calibration resonators (c) Grounded depolarizing chipless tag [7].

Figure 2 .

 2 Figure 2. (a) Resonant frequency deviation of a single layer chipless tag as a function of the thickness and the permittivity of the tagged object. (b) RCS of the 20 bits based single layer chipless tag (see Fig. 1 (b)) in free space and on the top of a cardboard before and after compensation (measurements are done at 20 cm).

Figure 3 .

 3 Figure 3. (a) Technique of volume gating to isolate the tag's response. (b) EM response of a pack of coffee cans in co (VV) and cross polarization (VH). (c) Tag's EM response of the depolarizing tag (see Fig. 1 (c)) on top of a pack of coffee cans for two different configurations (the first resonant mode only is varying) measured at 20cm.

Acknowledgments

The authors are grateful to the University of Montpellier 2 and University of Grenoble Alpes for supporting this research.


Olivier Gouvert

Thomas Oberlin

Cédric Févotte

Recommendation from Raw Data with Adaptive Compound Poisson Factorization

Count data are often used in recommender systems: they are widespread (song play counts, product purchases, clicks on web pages) and can reveal user preference without any explicit rating from the user. Such data are known to be sparse, over-dispersed and bursty, which makes their direct use in recommender systems challenging, often leading to pre-processing steps such as binarization. The aim of this paper is to build recommender systems from these raw data, by means of the recently proposed compound Poisson Factorization (cPF). The paper contributions are three-fold: we present a unified framework for discrete data (dcPF), leading to an adaptive and scalable algorithm; we show that our framework achieves a trade-off between Poisson Factorization (PF) applied to raw and binarized data; we study four specific instances that are relevant to recommendation and exhibit new links with combinatorics. Experiments with three different datasets show that dcPF is able to effectively adjust to overdispersion, leading to better recommendation scores when compared with PF on either raw or binarized data.

INTRODUCTION

Collaborative filtering (CF) techniques have been achieving state-of-the-art performances in recommendation tasks since the Netflix prize [START_REF] Bennett | The Netflix Prize[END_REF]. CF is based on feedbacks of users interacting with items. These data can either be explicit (ratings, thumbs up/down) or implicit (number of times a user listened to a song, number of clicks on web pages). In particular, historical data are easy to collect and often in the form of count data. They can be stored in a sparse matrix Y of size U × I, where each entry of the matrix y ui is the number of times the user u ∈ {1, . . . , U } interacts with the item i ∈ {1, . . . , I}. For the rest of the paper, we will consider the example of users listening to songs without loss of generality.

Matrix factorization (MF) allows to make recommendations using these feedback data [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. The aim of MF is to infer a low-rank approximation of the observations: Y ≈ WH T , where W of size U × K represents the preferences of users, and H of size I × K represents the attributes of items, with K min(U, I). Therefore, each user or item is represented in the same latent space by a vector of K latent components. The strength of an interaction between a user and an item is measured by the dot product between their representative latent vectors. Among the methods based on MF (Lee andSeung, 1999, 2001;[START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF][START_REF] Ma | Probabilistic factor models for web site recommendation[END_REF][START_REF] Févotte | Algorithms for nonnegative matrix factorization with the beta-divergence[END_REF][START_REF] Liang | Modeling user exposure in recommendation[END_REF], Poisson factorization (PF) (Canny, 2004;[START_REF] Cemgil | Bayesian inference for nonnegative matrix factorisation models[END_REF][START_REF] Gopalan | Scalable recommendation with hierarchical Poisson factorization[END_REF] has become very popular in CF when using implicit feedbacks. Indeed, PF posits that the data are generated from a Poisson distribution, making it well-adapted for count data. PF has reached state-of-the-art results while having favorable properties. (i) PF down-weighs the effect of the zeros present in the data, by implicitly assuming that the users have a limited budget to distribute among the items [START_REF] Gopalan | Scalable recommendation with hierarchical Poisson factorization[END_REF]. (ii) Algorithms for PF scale with the number of non-zero values in the data, leading to fast inference [START_REF] Cemgil | Bayesian inference for nonnegative matrix factorisation models[END_REF]. Many variants of PF have been proposed these last years. Hierarchical structures on the latent variables have been explored [START_REF] Ranganath | Deep exponential families[END_REF]Zhou et al., 2015;[START_REF] Liang | Variational autoencoders for collaborative filtering[END_REF]. Other works have proposed to use additional information in the model to perform hybrid CF approaches [START_REF] Gopalan | Contentbased recommendations with Poisson factorization[END_REF][START_REF] Lu | Learning geo-social user topical profiles with Bayesian hierarchical user factorization[END_REF][START_REF] Salah | Probabilistic collaborative representation learning for personalized item recommendation[END_REF].

However, in many cases, count data are over-dispersed and bursty [START_REF] Kleinberg | Bursty and hierarchical structure in streams[END_REF][START_REF] Schein | Poissongamma dynamical systems[END_REF]. The Poisson distribution fails to fully describe such data. Its modeling capacities are indeed limited since its mean and variance are equal. To avoid this problem, it is of common use to work with binarized data [START_REF] Gopalan | Scalable recommendation with hierarchical Poisson factorization[END_REF][START_REF] Liang | Modeling user exposure in recommendation[END_REF]. This pre-processing step is effective in practice but removes the information contained in the non-zero values. Recent works have focused on directly using the raw data in order to achieve better representation and recommendation results. In [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF][START_REF] Pan | One-class collaborative filtering[END_REF], the raw data are introduced as weights (confidence), which regularize the MF approximation. Other works try to find generative processes which are able to deal with over-dispersed data. In [START_REF] Zhou | Nonparametric Bayesian negative binomial factor analysis[END_REF], the author makes use of the negative binomial (NB) distribution, which is a well-known extension of the Poisson distribution [START_REF] Lawless | Negative binomial and mixed Poisson regression[END_REF]. He exploits the compound Poisson (cP) representation of the NB distribution to preserve the scalability property of the proposed algorithm. cP structure has further been used in [START_REF] Simsekli | Learning the beta-divergence in Tweedie compound Poisson matrix factorization models[END_REF][START_REF] Basbug | Hierarchical compound Poisson factorization[END_REF] to model continuous or discrete sparse data, showing an improved description of the non-zero values.

In this paper, we present novel contributions to discrete compound Poisson factorization (dcPF). dcPF refers to compound Poisson factorization (cPF), as introduced by [START_REF] Basbug | Hierarchical compound Poisson factorization[END_REF], for discrete data. dcPF posits that the listening counts can be grouped in listening sessions which are somewhat more informative for recommendation. It uses the concept of self-excitation [START_REF] Du | Timesensitive recommendation from recurrent user activities[END_REF][START_REF] Hosseini | Recurrent Poisson factorization for temporal recommendation[END_REF][START_REF] Khodadadi | Continuous-time user modeling in the presence of badges: a probabilistic approach[END_REF][START_REF] Zhou | Nonparametric Bayesian negative binomial factor analysis[END_REF], which describes the idea that a user can listen to a song not merely because of his/her attachment to it, but because of a previous interaction. The contributions of the paper are the following:

• We develop a unified framework for dcPF and study four specific distributions to model self-excitation, called element distributions. We exhibit new links between the choice of this distribution and combinatorics.

• We provide simple conditions to preserve scalability and to obtain closed-form updates for the inference of the posterior.

• We show that dcPF is a natural generalization of PF by proving that PF applied to raw data and PF applied to binarized data are two limit cases of dcPF.

• We discuss the choice of the element distribution and in particular consider a new one in the context of compound Poisson models, the shifted negative binomial distribution. We present new methodology for hyper-parameter estimation and report experiments with three datasets.

The paper is organized as follows. In Section 2, we provide preliminary material about PF and exponential dispersion models (EDM). In Section 3, we present Bayesian dcPF and give an intuitive interpretation of the model and its properties. Related works are discussed in Section 4 and a scalable variational algorithm is developed in Section 5. In Section 6, we apply the proposed algorithm to recommendation tasks with three datasets. Section 7 concludes the paper and discusses possible perspectives.

PRELIMINARIES

Poisson factorization. PF is based on non-negative matrix factorization (NMF) (Lee andSeung, 1999, 2001). Each observation is assumed to be drawn from a Poisson distribution:

y ui ∼ Poisson([WH T ] ui ), (1)
with y ui ∈ N = {0, 1, . . . , +∞}. The preferences W and the attributes H are supposed to be non-negative matrices. Non-negativity induces a constructive partbased representation of the observations that is central to so-called topic models [START_REF] Lee | Learning the parts of objects by non-negative matrix factorization[END_REF][START_REF] Blei | Latent Dirichlet allocation[END_REF]. Bayesian extensions of PF typically impose that each entry of the matrices W and H has a gamma prior.

The gamma prior1 imposes non-negativity and is known to induce sparsity when the shape parameter is lower than one. This is a desirable property in the sense that it implies that users and items are represented by only a few patterns. Moreover, it is conjugate with the Poisson distribution, which proves convenient for variational inference.

PF has been very popular in the last decade because of its scalability with sparse data. Sparsity is very common in recommender systems, since subsets of users usually interact with only subsets of items from a large catalog.

Using the superposition property of the Poisson distribution, we can augment the model presented in Equation (1) as follows [START_REF] Cemgil | Bayesian inference for nonnegative matrix factorisation models[END_REF][START_REF] Gopalan | Scalable recommendation with hierarchical Poisson factorization[END_REF]:

y ui = k c uik ; c uik ∼ Poisson(w uk h ik ). (2)
The conditional distribution of this new latent variable follows a multinomial distribution: c ui |y ui ∼ Mult(y ui , φ ui ), where φ ui is a vector of size K with entries φ uik = w uk h ik [WH T ]ui . The latent variable c ui is central to state-of-the-art PF algorithms. y ui = 0 implies that c ui = 0 K , where 0 K is a vector of size K full of zeros. As such, the latent variable c ui only needs to be estimated for the non-zero values of Y, which ensures scalability provided the data is sparse.

One limitation of the Poisson distribution is that its variance is equal to its mean: var(y ui ) = y ui . This makes it ill-suited for over-dispersed data. Moreover, when working with raw data, it appears that PF does not correctly weigh the observations and is too sensitive to large values. The Poisson distribution, parametrized by only one parameter, thus appears too restrictive to model both sparse and heavy-tailed data. To circumvent these issues, data binarization is often used as pre-processing [START_REF] Gopalan | Scalable recommendation with hierarchical Poisson factorization[END_REF][START_REF] Liang | Modeling user exposure in recommendation[END_REF], with the loss of information it induces. The goal of dcPF studied in this paper is to preserve the data while accounting for sparsity and overdispersion in the model. When necessary, we denote by Y b the corresponding binary version of the observations, where

y b ui = 1[y ui > 0].
Exponential dispersion model. A central element of cP models is the distribution used to model the selfexcitation. In this paper, we will assume that it belongs to the well-studied EDM family [START_REF] Jørgensen | Some properties of exponential dispersion models[END_REF][START_REF] Jørgensen | Exponential dispersion models[END_REF].

It is a convenient choice when dealing with cP models [START_REF] Yılmaz | Alpha/beta divergences and Tweedie models[END_REF][START_REF] Simsekli | Learning the beta-divergence in Tweedie compound Poisson matrix factorization models[END_REF][START_REF] Basbug | Hierarchical compound Poisson factorization[END_REF], as explained next. Most discrete random variables can be written in the form of a discrete EDM, denoted by x ∼ ED(θ, κ), and defined by

p(x; θ, κ) = exp(xθ -κψ(θ))h(x, κ), x ∈ S κ , (3)
where θ ∈ Θ ⊂ R is called the natural parameter, κ > 0 is called the dispersion parameter, ψ(θ) is the log-partition function, h(x, κ) is the base measure and S κ is the support of the distribution, which depends of κ. The mean of x is given by x = κψ (θ) and its variance by var(x) = κψ (θ). One of the most interesting properties of EDM is the property of additivity. If x l ∼ ED(θ, κ) and y = n l=1 x l with n ∈ N, then y ∼ ED(θ, nκ). By convention, we assume that ED(θ, 0) is a Dirac distribution in 0.

BAYESIAN DISCRETE COMPOUND POISSON FACTORIZATION

MODEL DESCRIPTION

We consider the framework proposed by [START_REF] Basbug | Hierarchical compound Poisson factorization[END_REF]. The generative model of the observations Y is given by

w uk ∼ G(α W , β W u ), h ik ∼ G(α H , β H i ), (4)
n ui ∼ Poisson [WH T ] ui , (5) x l,ui ∼ ED(θ, κ), ∀l ∈ {1, . . . , n ui }, (6)
y ui = nui l=1
x l,ui .

We here specifically assume that x l,ui is a discrete random variable with support equal to N * = N \ {0}. The rate parameters of the gamma priors are treated as deterministic parameters estimated by maximum likelihood (ML). β W ∈ R U + expresses the activity level of the users and β H ∈ R I + expresses the popularity of the items. A Bayesian treatment of these parameters is also possible and is considered in [START_REF] Gopalan | Scalable recommendation with hierarchical Poisson factorization[END_REF]. Using the additivity property of EDM, we can easily marginalize the latent variables x l,ui , leading to: y ui ∼ ED(θ, n ui κ). Compared to PF, this additional stage in the generative process allows for a flexible description of the observations. There are two additional parameters {θ, κ} which control the variance and tail of the distribution.

Interpretation. In this paragraph, we will suppose that a user/item pair is fixed. For conciseness, we will omit the corresponding indices ui . dcPF introduces new latent variables n and {x l } l for l ∈ {1, . . . , n}. The latent variable n represents the number of listening sessions the user has had for the song. During each session, indexed by l, the user listened to the song a number of times x l which is greater or equal to one. The latent variable x l models the self-excitation induced by a listening interaction. This concept has been used in [START_REF] Zhou | Nonparametric Bayesian negative binomial factor analysis[END_REF][START_REF] Hosseini | Recurrent Poisson factorization for temporal recommendation[END_REF]. Thus, a user can listen to a song, not merely because he/she likes it, but because of a previous listening/excitation. For example, a user can have a summer crush for a song and may listen to it on repeat. The first listening reflects the interest of the user for this song, whereas the following listenings are the consequence of the first one and reflect a short-term behavior. Therefore these listening counts can be grouped in a few listening sessions that will be more able to represent long-term preferences. Finally, the observed variable y is just the aggregation of all the listening counts from all the sessions. The variable n can be viewed as a way to partition the observation y in a smaller number of sessions. This number n better reflects the preferences of the user, since it is deprived of the notion of self-excitation which artificially inflates the number of listening counts. In the following, we will denote by N ∈ N U ×I the exposition matrix with entries [N] ui = n ui .

Joint log-likelihood. The joint log-likelihood of the observations Y and of the latent variables N, W and H can be written as follows:

log p(Y,N, W, H) = log p(Y|N; θ, κ) Mapping (8) + log p(N|[WH T ]) PF structure + log p(W, H) Regularization .
We can decompose this log-likelihood into three terms: a probabilistic mapping term corresponding to the compound structure of the observations, a term corresponding to the PF structure on the latent variable N and a regularization term induced by the gamma priors. Contrary to PF, the factorization is placed on the latent variable N instead of the data itself, allowing for more flexibility. Going back to our interpretation, this latent variable is more likely to inform on user preference than Y. The mapping term can be viewed as a distortion of the true observations, making them "more factorizable" than the raw observations. Therefore, this additional term allows to avoid strong pre-processing stages (such as binarization), letting the data choose their "own distortion".

Scalability and tractability. By imposing that users will listen to a song at least one time during each session, i.e., x l,ui ∈ N * , two important properties can be deduced.

First, we have the following equivalence: y ui = 0 ⇔ n ui = 0. In other words, the observed listening count is equal to zero if and only if the number of listening sessions is equal to zero. Therefore, the latent variable N is partially known and has the same zeros as Y. Thanks to this, we preserve the scalability property of PF (cf Section 2). Moreover, we have that:

P(y ui = 0) = P(n ui = 0) = e -[WH T ]ui . (9)
The latent variables W and H control the sparsity of the matrix Y, while the element distribution and its parameters {θ, κ} only focus on the representation of non-zero values.

The second interesting property is that n ui ≤ y ui . Therefore, given an observation y ui , we know that n ui can only take a finite number of values, bounded by y ui (in particular, y ui = 1 ⇒ n ui = 1). This provides efficient means of calculation for the latent variable N during inference.

EXAMPLES OF ELEMENT DISTRIBUTIONS

Distributions based on Stirling numbers. In this paragraph we focus on three particular distributions: the logarithmic distribution [START_REF] Quenouille | A relation between the logarithmic, Poisson, and negative binomial series[END_REF], denoted by x l ∼ Log(p); the zero-truncated Poisson (ZTP) distribution, denoted by x l ∼ ZT P (p); the (shifted) geometric distribution, denoted by x l ∼ Geo(1p). 2 Examples of probabilistic mass functions (p.m.f.) of the four considered element distributions are displayed on Figure 1.

These three distributions can be written in the form of a discrete EDM with dispersion parameter κ = 1 and support N * . Their base measure is given by h(x l , κ) =

x l ! κ! St j (x l , κ), where St j (x l , κ) is the unsigned Stirling number of one of the three kinds (j ∈ {1, 2, 3}), see 2 We use the following convention for the (shifted) geometric distribution: Geo(x; p) = (1p) x-1 p, with x ∈ N * . 3. The p.m.f. marked with a * are not available in closed form and are represented through a histogram of simulated values.

Table 1. See [START_REF] Johnson | Univariate discrete distributions[END_REF] for more details. It is of particular interest when analyzing the distribution of y|n. This conditional distribution is also a discrete EDM with: h(y, κn) = y! n! St j (y, n). The Stirling numbers of the three kinds are three different ways to partition y elements into n groups [START_REF] Riordan | Introduction to combinatorial analysis[END_REF] (graphical illustrations are given in the supplementary material):

• The Stirling number of the first kind corresponds to the number of ways of partitioning y elements into n disjoints cycles. It can be obtained thanks to a recurrence formula:

St 1 (y + 1, n) = y St 1 (y, n) + St 1 (y, n -1).
• The Stirling number of the second kind corresponds to the number of ways of partitioning y elements into n non-empty subsets. It can be calculated in closed form:

St 2 (y, n) = 1 n! n j=0 (-1) n-j n j j y .
When y is too large, its exact computation can suffer from numerical issues, though reasonable and stable approximations are available [START_REF] Bleick | Asymptotics of Stirling numbers of the second kind[END_REF].

• The Stirling number of the third kind (also known as Lah number) corresponds to the number of ways of partitioning y elements into n non-empty ordered subsets. It is given by: St 3 (y, n) = y-1 n-1 y! n! . Its definition is particularly well adapted if we assume that the grouping results from temporal phenomena.

Shifted negative binomial. The dispersion parameter for the three distributions presented in the previous examples is fixed and equal to one. We now introduce a new distribution, referred to as shifted NB distribution which is parametrized by two parameters: x l -1 ∼ N B(a, p), whose shape parameter a controls the long tail of the distribution, and p ∈ (0, 1) is the probability parameter. The shifted NB is a shifted

Distribution θ Θ θ raw θ bin κ ψ(θ) h(x, κ) x l ∼ Log(p) log(p) R * - -∞ 0 1 log(-log(1 -e θ )) x! κ! St1(x, κ) x l ∼ ZTP(p) log(p) R -∞ +∞ 1 log(e e θ -1) x! κ! St2(x, κ) x l ∼ Geo(1 -p) log(p) R * - -∞ 0 1 log( e θ 1-e θ ) x! κ! St3(x, κ) x l -1 ∼ NB(a, p) log(p) R * - -∞ 0 (1, a) T (θ, -log(1 -e θ )) T Γ(x-κ 1 +κ 2 ) Γ(x-κ 1 +1)Γ(κ 2 )
EDM, which does not exactly fall into the EDM family. However, the conditional distribution y|n can still be written as: p(y|n; θ, κ) = exp(yθnκ T ψ(θ))h(y, nκ), where y ∈ {n, . . . , +∞}, κ = (κ 1 , κ 2 ) T = (1, a) T and ψ(θ) = (θ,log(1e θ )) T . Note that κ and ψ(θ) are now vectors of dimension 2. Parameter κ 1 controls the shifting operation, and is fixed to one to ensure that the support of x l is N * . Shifted NB encompasses two particular cases: the classical NB distribution (κ 1 = 0), and the geometric distribution (κ 1 = κ 2 = 1).

For each distribution, the resulting marginalized distribution of y is displayed on Figure 1 and is compared to the Poisson distribution (which is a cP distribution with a Dirac as element distribution). We can see on this figure that all marginalized distributions have the same mass in 0 (see Section 3.1) but are different otherwise.

A TRADE-OFF BETWEEN RAW AND BINARIZED DATA

In this section, we show that dcPF generalizes PF in the sense that it includes PF applied to raw and binarized data as limit cases. For a given dispersion parameter κ, the natural parameter θ controls the level of information contained in the observations Y:

• When θ tends to a limit θ raw , dcPF becomes equivalent to PF (with original raw data).

• When θ tends to a limit θ bin , the posterior inference of dcPF becomes equivalent to the posterior inference of PF applied to the binarized data. In other words, performing dcPF (with original raw data) becomes equivalent to performing PF on binarized data. Note that the marginal distribution of the observations and the distribution of y|n are both improper distributions, but the posterior distribution is still well-defined [START_REF] Robert | The Bayesian choice: from decisiontheoretic foundations to computational implementation[END_REF].

• Between θ raw and θ bin , θ controls the degree of implicit distortion of the observations.

Our results are formalized in the two following propositions. The proofs are left to the supplementary material.

Proposition 1. If there exists θ raw such that lim θ→θ raw κ T ψ(θ) = -∞, then the posterior of dcPF tends to the posterior of PF as θ goes to θ raw .

Proposition 2. If there exists θ bin such that lim θ→θ bin κ T ψ(θ) = +∞, then the posterior of dcPF tends to the posterior of PF applied to binarized data as θ goes to θ bin , i.e.: lim θ→θ bin p(W, H|Y) = p(W, H|N = Y b ).

The four distributions described in Section 3.2 respect the assumptions of both propositions. The limit cases of the natural parameter θ are given in Table 1.

It is of particular interest to learn the natural parameter θ since its choice characterizes the data. If θ is close to θ raw , the observations do not need to be distorted and PF on raw data is effective. If θ is close to θ bin , the non-zero observations of Y are non-informative and binarization is welcome. In between these extremes, dcPF takes full power and acts as an implicit distortion. Thus, the value of θ gives an indication on the gain brought by dcPF as compared to PF.

RELATED WORKS

Negative binomial factorization. An extension of the Poisson distribution known to model over-dispersion is the NB distribution. The NB distribution depends on two parameters: a shape parameter and a probability parameter p. In [START_REF] Zhou | Nonparametric Bayesian negative binomial factor analysis[END_REF], the author introduces NB matrix factorization, in which he posits that the shape parameter is low-rank, i.e.: y ui ∼ N B([WH T ] ui , p). To preserve scalability of the proposed Gibbs algorithm, the author uses the cP representation of the NB [START_REF] Quenouille | A relation between the logarithmic, Poisson, and negative binomial series[END_REF][START_REF] Fisher | The relation between the number of species and the number of individuals in a random sample of an animal population[END_REF]:

n ui ∼ Poisson(-[WH T ] ui log(1 - p)
) and y ui ∼ SumLog(n ui , p) where SumLog(n, p) is the sum of n identical and independent logarithmic distributions. In this case, the conditional distribution of the n ui is also known: n ui |y ui ∼ CRT (y ui , [WH T ] ui ), where CRT is the number of opened tables in a Chinese restaurant process (CRP). An important difference with our framework is that the parameter p there controls both the sparsity of Y and the distribution of the non-zero values. This introduces a coupling between the factorization WH T and the parameter p which leads to a more difficult interpretation in the context of recommendation.

Compound Poisson models. In [START_REF] Basbug | Hierarchical compound Poisson factorization[END_REF], the authors introduce cPF which is welladapted for continuous or discrete sparse data. For discrete data, the authors present four different distributions but only one (the ZTP distribution) with support N * . Note that, if P(x l,ui = 0) > 0 then the latent variable N is completely unknown and the scalability property does not hold anymore (unless the hypothesis y ui = 0 ⇒ n ui = 0 is arbitrarily imposed during the inference). In terms of inference, [START_REF] Basbug | Hierarchical compound Poisson factorization[END_REF]) describe a stochastic variational inference algorithm that is shown to perform well in terms of log-likelihood computed from held-out data. We will instead evaluate the performance of dcPF with recommendation metrics.

In [START_REF] Yılmaz | Alpha/beta divergences and Tweedie models[END_REF][START_REF] Simsekli | Learning the beta-divergence in Tweedie compound Poisson matrix factorization models[END_REF], a cP structure with a gamma element distribution is used to represent the Tweedie distribution. The Tweedie distribution is the distribution induced by the β-divergence with β ∈ (01) [START_REF] Févotte | Algorithms for nonnegative matrix factorization with the beta-divergence[END_REF]. One importance difference with our setting, besides the fact that the Tweedie distribution is continuous, is that the authors impose that the model is mean-parametrized, i.e., y ui = [WH T ] ui . This is not the case with cPF since by construction:

y ui ≥ n ui = [WH T ] ui .
Weighted MF. In [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF], the authors develop a framework for implicit feedbacks. Implicit data are inherently noisy and may not reflect a direct preference of a user for an item, but rather a confidence in the interaction. In this context, implicit feedbacks can be transformed and incorporated as weights in the cost function which is defined as:

C(W, H) = ui ω ui y b ui -[WH T ] ui 2 2 + µR(W, H),
where ω ui = f (y ui ) is the confidence that can be brought in the binary observation y b ui , f is a fixed mapping function, R(W, H) is a regularization term and µ is an hyperparameter. Here, the mapping function f between the raw data and the confidence is deterministic. Note that some other works focused on introducing probabilistic weights in the data fitting term [START_REF] Liang | Modeling user exposure in recommendation[END_REF][START_REF] Wang | A general method for robust Bayesian modeling[END_REF] but these weights are learned regardless of the raw data. As discussed previously, dcPF encompasses the raw observations via an additional probabilistic mapping term. This term can also be viewed as a probabilistic confidence term, combining the two latter approaches. Indeed, large listening counts y ui will often lead to a large number of sessions n ui , exhibiting a strong confidence in this observation. Nevertheless, this mapping is not deterministic and as such more flexible and robust.

VARIATIONAL BAYES EXPECTATION-MAXIMIZATION

In this section, we develop a variational Bayes expectation-maximization (VBEM) algorithm. We denote by Z = {N, C, W, H} the set of latent variables and by Φ = Φ 1 ∪ Φ 2 the set of parameters, with Φ 1 = {θ, κ} and

Φ 2 = {α W , β W , α H , β H }.
The aim of this algorithm is to estimate both the posterior p(Z|Y; Φ) and the parameters Φ.

VARIATIONAL INFERENCE

Bayesian inference revolves around the characterization of the posterior distribution p(Z|Y; Φ). Unfortunately, this posterior is intractable in our case. Variational inference (VI) [START_REF] Jordan | An introduction to variational methods for graphical models[END_REF][START_REF] Blei | Variational inference: a review for statisticians[END_REF] consists in approximating this intractable posterior by a simpler distribution q parametrized by its own parameters Φ, called variational parameters. Thus, the aim of VI is to minimize the Kullback-Leibler divergence between the true and approximate distributions with respect to (w.r.t.) the variational parameters. In practice, it is simpler to maximize the so-called expected lower bound (ELBO), which is an equivalent problem. A common choice is to assume q to be factorizable (mean-field approximation):

q(Z) = ui q(n ui , c ui ) uk q(w uk ) ik q(h ik ). ( 10
)
Though not explicitly shown for conciseness, the variational distribution of each parameter is governed by its own set of parameters (over which optimization takes place). Note that we choose the latent variables n ui and c ui to remain coupled. We can further decompose the variational distribution of these variables as: q(n ui , c ui ) = q(c ui |n ui )q(n ui ).

The ELBO can be calculated as follow:

L(q, Φ) = log p(Y|N; Φ 1 ) q + log p(N, C|W, H) q + log p(W, H; Φ 2 ) q + H(q), (11)
where x q is the expectation of the variable x w.r.t. the variational distribution q and H(q) is the entropy of the distribution q.

Coordinate ascent VI. We use a coordinate ascent for VI (CAVI) algorithm to maximize the ELBO. The CAVI algorithm consists of sequentially optimizing each of the variational parameters while keeping the others fixed. It can be shown that mean-field variational inference naturally leads to the following choice of variational distributions [START_REF] Bishop | Pattern recognition and machine learning[END_REF], parametrized by Φ = {Λ, αW , βW , αH , βH }:

q(w uk ) = G(α W uk , βW uk ), q(h ik ) = G( αH ik , βH ik ), (12) q(c ui |n ui ) = Mult n ui , Λ uik Λ ui k , q(n ui = n) = 1 Z ui (r ui ) n h(y ui , nκ) n! , ∀n ∈ {1, . . . , y ui },
where θ) and

Λ ui = k Λ uik , r ui = Λ ui e -κψ(
Z ui = yui n=1 (r ui ) n h(yui,nκ) n!
is a normalization constant.

Update rules. CAVI leads to the following set of iterative update rules:

Λ uik ← exp ( log w uk q + log h ik q ) ; (13)
αW uk ← α W + i n ui q Λ uik Λ ui ; βW uk ← β W u + i h ik q αH ik ← α H + u n ui q Λ uik Λ ui ; βH ik ← β H i + u w uk q .
When x ∼ G(α, β), x = α β and log x = Ψ(α)-log β, where Ψ is the digamma function. The statistic n ui q is available in closed form 3 thanks to the properties of Section 3.1. If y ui = 0 then n ui q = 0, otherwise n ui q = yui n=1 n q(n ui = n). As expected, we recover, as limit cases, the algorithms for PF [START_REF] Gopalan | Scalable recommendation with hierarchical Poisson factorization[END_REF] applied to raw data if n ui q = y ui and to binarized data if n ui q = 1[y ui > 0]. The algorithm is stopped when the relative increment of the ELBO gets lower than a value τ .

PARAMETERS ESTIMATION

Activity and popularity parameters. Optimizing the ELBO w.r.t. the parameters Φ 2 is equivalent to solving the sub-problem: argmax Φ2 log p(W, H; Φ 2 ) q . In this article, we suppose that the shape parameters {α W , α H } are known and we want to optimize only the rate parameters {β W , β H }. The interested reader is referred to [START_REF] Cemgil | Bayesian inference for nonnegative matrix factorisation models[END_REF] and [START_REF] Zhou | Negative binomial process count and mixture modeling[END_REF] for the details of ML and Bayesian estimation of the shape parameter of a gamma distribution. ML leads to the following updates for both activity and popularity parameters:

β W u ← k w uk q Kα W ; β H i ← k h ik q Kα H . ( 14
)
Natural parameter. Optimizing the ELBO w.r.t. the natural parameter θ is equivalent to maximizing:

3 When choosing the logarithmic distribution as the element distribution we have: nui q = rui Ψ(yui + rui) -Ψ(rui) [START_REF] Zhou | Nonparametric Bayesian negative binomial factor analysis[END_REF]. log p(Y|N; Φ 1 ) q = ui (y ui θn ui q κψ(θ)) + cst, where cst is a constant w.r.t. the natural parameter θ. It leads to the following equation: ui y uiui n ui q κψ (θ) = 0.

(15)

In the case of the shifted NB distribution, ψ(θ) ∈ R 2 and ψ corresponds to its gradient. The solution of this equation in known in closed form for geometric and shifted NB distributions. We implement a Newton-Raphson algorithm to solve it for logarithmic and ZTP distributions.

Dispersion parameter for shifted NB. When choosing the shifted NB as the element distribution, we have:

y ui -n ui ∼ N B(κ 2 n ui , e θ ). (16)
Optimizing the ELBO w.r.t. the parameter κ 2 which controls the long-tail of the NB distribution is not straightforward. The main issue is that it involves a term of the form h(y ui , n ui κ) q that is computationally expensive to optimize. Therefore, we augment the model like in [START_REF] Zhou | Nonparametric Bayesian negative binomial factor analysis[END_REF], with a latent variable:

m ui |y ui , n ui ∼ CRT (y ui -n ui , n ui κ 2 ) (if y ui = 0 then m ui = 0).
In this augmented model, the optimization of κ 2 is equivalent to finding the ML estimator of m ui |n ui ∼ Poisson(n ui κ 2 (-log(1e θ )). This leads to the following update:

κ 2 ← 1 -log(1 -e θ ) ui m ui q ui n ui q , ( 17
)
where

m ui q = yui n=1 nκ 2 Ψ(y ui -n + nκ 2 ) - Ψ(nκ 2 ) q(n ui = n).

EXPERIMENTAL RESULTS

Datasets. We consider the following datasets, whose structure is summarized in Table 2.

• The Taste Profile dataset [START_REF] Bertin-Mahieux | The Million Song Dataset[END_REF] provided by The Echo Nest contains the listening history of users. The data collected are the number of time the users listened to songs. We pre-process a subset of the data as in [START_REF] Liang | Modeling user exposure in recommendation[END_REF], keeping only users and songs that have more than 20 interactions. The histogram of the listening counts is displayed on Figure 2.

• The Last.fm dataset [START_REF] Celma | Music recommendation[END_REF] contains the listening history of users with additional timestamps information. We select play counts of the year 2008 and apply the same pre-processing as with the Taste Profile dataset.

• The NIPS dataset [START_REF] Perrone | Poisson random fields for dynamic feature models[END_REF] contains bagof-words representations of conference papers published in the NIPS conference from 1987 to 2015. We make an analogy between "users who listened to songs" and "documents written with words". The goal here is to recommend unused words to the author of a paper.

Experimental setup. Each dataset is split into a train set Y train containing 80% of the non-zero of the original dataset and a test set Y test containing the remaining 20% (these values being set to 0 in the train set). All the compared algorithms are trained with the train set and provide a recommendation list for each user. These lists are evaluated with the test set.

For each user, we recommend an ordered list of m songs he/she never listened to, based on Y train . The songs in this list are sorted w.r.t. the prediction score defined by: s ui = K k=1 w uk q h ik q . Note that, in dcPF, the expected number of listening sessions is equal to [WH T ] ui , expressing long-term preference (see Section 3.1).

The quality of the proposed list is measured by the normalized discounted cumulative gain (NDCG) score. NDCG is a metric often used in information retrieval to evaluate lists of ranked items. It is calculated as follows:

DCG u = m i=1 rel(u, i) log 2 (i + 1) , NDCG u = DCG u IDCG u ,
where DCG u is the discounted cumulative gain and rel(u, i) is the relevance to the ground-truth of the ith item of the proposed list. IDCG u is the ideal DCG, i.e., the best DCG score that can be obtained. Therefore NDCG u ∈ [0, 1] with NDCG u = 1 corresponding to the perfect recommended list. For the relevance to the ground-truth, we propose to account for the values in the test set above a fixed threshold: rel(u, i) = 1[y test ui > s]. As mentioned in [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF], small listening counts reflect a preference with little confidence. For example, a user can listen to a song by pure curiosity. Therefore, this threshold leads to a more robust NDCG metric. We denote by NDCGs the NDCG with the threshold s. If s = 0, we recover the classic NDCG0 metric for binary data. Otherwise, for s ≥ 1, NDCGs only considers the songs which have been listened to at least s times and ignores the others. Other metrics such as precision and recall lead to similar conclusions than NDCG0 and will not be displayed in the following.

Compared methods. For the three datasets, we compare dcPF with its limit cases: PF performed on raw (PFraw) or on binarized data (PFbin). PF is known to achieve good performance in recommendation tasks [START_REF] Gopalan | Scalable recommendation with hierarchical Poisson factorization[END_REF]. For the Taste Profile dataset, we considered the hyper-parameters α W = α H among {0.1, 0.3, 1} and K among {50, 100, 200}, and selected the values α W = α H = 0.3 and K = 100 which gave the best NDCG0 for PFbin. For the NIPS and Last.fm datasets, which are smaller than the Taste Profile dataset, we only considered α W = α H = 0.3 and K = 50. The stopping criterion of the algorithms is set to τ = 10 -5 . Evaluation is done using a ranked list of m = 100 items. For all the experiments, algorithms are run five times from random initializations. 4Prediction results. We start by discussing results with the Taste Profile dataset, reported in Table 3. A general observation is that dcPF gives better results than the two baselines PFraw and PFbin for all four metrics and every element distribution, with the exception of ZTP in the case of NDCG0. PFbin returns better scores than PFraw up to s = 5. This confirms the usefulness of the binarization stage when using PF, but only up to a certain threshold s (this is because PFbin does not fully exploit the non-zero values in the original raw data). The performance gap between dcPF and PFbin increases with the threshold s. On the two other datasets (NIPS and Last.fm), Table 4 shows that dcPF outperforms the baseline methods for all element distributions. Note that for the NIPS dataset, a somehow different context from song recommendation, PFraw is effective and performs better than PFbin as soon as the threshold s is larger than one. From both Tables 3 and4 we conclude that the proposed shifted NB element distribution is a good compromise overall.

Natural parameter estimation. As explained in Section 3.3, estimation of the natural parameter tells us about the level of scale information exploited by dcPF. Table 3 shows that dcPF indeed offers a valuable trade-off between PFraw and PFbin, because the estimated parameter θ lies in between the two limit cases θ raw and θ bin . To assess the quality of the estimation procedures for θ in Log, ZTP and Geo described in Section 3.3 (plainly referred as VBEM), Table 3 also displays evaluation metrics obtained with a grid-search. More precisely, we use θ = log p which maximizes NDCG5 from a set of prespecified values. For Log and Geo, p is searched between 0 and 1 with a step of 0.1. For ZTP, p is searched in {0, 0.1, 0.5, 1, 2, 10, 100, +∞}. It appears that VBEM slightly over-estimates the optimal value (in terms of Posterior predictive check (PPC). We provide a PPC of the distribution of the listening counts in the Taste Profile dataset (see Figure 2). A PPC consists in simulating a new dataset Y PPC from the fitted model (for dcPF, we simulate from the generative process described in Section 3.1 with latent variables W, H and parameters inferred in Section 6). Then, we compare the histogram of the values of Y train and Y PPC . The PPC of the two limit cases is very instructive. PFraw tries to fit the long tail of the data, but, by doing so, destroys the representation of the zero values (1.02% of non-zero values versus 0.48% in the real dataset). It can explain the disappointing performances of PFraw for NDCG0. On the contrary, PFbin better fits the sparsity of the data but is not able to describe large counts. In both cases, PF struggles to properly weigh the influence of large counts compared to low counts. Comparatively, dcPF proposes a smoother weighting between large and low values. dcPF respects both the sparsity and the long tail of the data for the four element distributions. ZTP seems to over-estimate the influence of medium counts (from 1 to 5), whereas shifted NB has the best fit to the histogram. We observe that regardless of the model, explaining the large values (> 100) remains difficult, however we may consider that after a certain threshold the counts do not contain useful information.

CONCLUSION

In this paper, we described new contributions to cPF for discrete data. As compared to PF, we showed that dcPF offers more flexibility to model long-tailed data. Inference remains scalable thanks to modeling of the non-zero values only. Numerical experiments confirmed that our adaptive VBEM algorithm efficiently exploits raw data, leading to better recommendation scores when compared to the two limit cases (PF on raw and binarized data). Among the four element distributions presented and experimented in this work, the proposed shifted NB prove particularly efficient thanks to its additional parameter, and often led to the best recommendation scores.

Based on this work, a number of exciting perspectives can be considered, such as investigating more complex element distributions to better fit the extreme observations or to address other forms of data. For instance, it would be of great interest to adapt the model for bounded data such as ratings, which are widespread in CF but cannot be processed with dcPF in its current form.

Figure 1 :

 1 Figure1: On the left, the p.m.f. of the four element distributions presented in Section 3.2. On the right, the p.m.f. of the marginalized distribution of the observations, using the same four element distributions. The values of the natural and dispersion parameters are those presented in Table3. The p.m.f. marked with a * are not available in closed form and are represented through a histogram of simulated values.

Figure 2 :

 2 Figure 2: PPC of the distribution of the non-zero values in the Taste Profile dataset. The blue points (Truth) represents the histogram of the non-zero values in the train set. The colored curves represent the simulated histograms obtained from the different inferred dcPF or PF models. The percentages of non-zero values are written in parentheses.

Table 1 :

 1 Examples of four discrete element distributions. Notation: R

* -= (-∞; 0).

Table 2 :

 2 Datasets structure after pre-processing.

		Taste Profile NIPS	Last.fm
	# rows	16, 301	5, 811	781
	# columns	12, 118	11, 463	11, 172
	# non-zeros 1, 176, 086	4, 033, 830 402, 058
	% non-zeros 0.60%	6.06%	4.61%

Table 3 :

 3 Recommendation performance of dcPF and PF using the Taste Profile dataset. Italic: scores of dcPF when using a grid-search for θ, see text for details. Bold: two best NDCG scores (grid-search excluded).

	Model	Est.	p = e θ	κ	NDCG0	NDCG1	NDCG2	NDCG5
	Log	VBEM Grid	0.803 0 .3	1 1	0.200 (±3.0 10 -3 ) 0 .200 (±4 .1 10 -3 )	0.182 (±2.3 10 -3 ) 0 .186 (±3 .9 10 -3 )	0.166 (±2.0 10 -3 ) 0 .173 (±3 .7 10 -3 )	0.147 (±1.5 10 -3 ) 0 .158 (±3 .7 10 -3 )
	ZTP	VBEM Grid	1.950 1	1 1	0.192 (±4.1 10 -3 ) 0 .190 (±3 .5 10 -3 )	0.178 (±3.7 10 -3 ) 0 .178 (±3 .0 10 -3 )	0.167 (±3.6 10 -3 ) 0 .168 (±3 .1 10 -3 )	0.156 (±3.8 10 -3 ) 0 .158 (±3 .3 10 -3 )
	Geo	VBEM Grid	0.600 0 .3	1 1	0.199 (±2.3 10 -3 ) 0 .199 (±4 .9 10 -3 )	0.182 (±1.8 10 -3 ) 0 .185 (±4 .6 10 -3 )	0.167 (±1.8 10 -3 ) 0 .172 (±4 .2 10 -3 )	0.150 (±1.2 10 -3 ) 0 .159 (±4 .0 10 -3 )
	Sh. NB	VBEM	0.873	(1, 0.2) T	0.201 (±3.1 10 -3 )	0.183 (±2.5 10 -3 )	0.166 (±2.2 10 -3 )	0.147 (±1.5 10 -3 )
	PFraw	.	.	.	0.156 (±3.0 10 -3 )	0.155 (±3.3 10 -3 )	0.150 (±3.5 10 -3 )	0.144 (±5.3 10 -3 )
	PFbin	.	.	.	0.197 (±2.1 10 -3 )	0.177 (±1.5 10 -3 )	0.160 (±1.5 10 -3 )	0.140 (±1.3 10 -3 )

Table 4 :

 4 Performance with NIPS and Last.fm datasets.

			NIPS		Last.fm
	Model	NDCG0	NDCG1	NDCG0	NDCG1
	Log		0.394	0.430	0.142	0.129
	ZTP	0.381	0.422	0.122	0.113
	Geo		0.390	0.429	0.139	0.128
	Sh. NB	0.396	0.431	0.143	0.130
	PFraw	0.358	0.405	0.091	0.088
	PFbin	0.378	0.392	0.122	0.108
		10 6				Truth (0.48) PFraw (1.02)
		10 5				PFbin (0.46) Log (0.47)
	Occurence	10 3 10 4				ZTP (0.52) Geo (0.48) shifted NB (0.48)
		10 2
		10 1
		10 0
		10 0		10 1	Listening count	10 2	10 3

We use the following convention for the gamma distribution: G(x; α, β) = x α-1 e -βx β α Γ(α) -1 where α is the shape parameter and β is the rate parameter.

Algorithms and experiments are available on github: https://github.com/Oligou/dcPF.

Acknowledgements. Supported by the European Research Council (ERC FACTORY-CoG-6681839) and the ANR-3IA (ANITI).


Ben Ali

El Haddad

Mohamed And Boulouard

Zakaria Koutti

Lahcen Bouhafer

Fadwa

OATAO is an open access repository that collects the work of Toulouse researchers and makes it freely available over the web where possible

Keywords: Big Data, Data, Data Classification, Data Extraction, Data visualization tools, Database, Decision Making, Multimedia Database, Relational Database, Semi-Structured Data, Structured Data, Unstructured Data, XML

Data visualization can be defined as data transformation into interactive visual representations. It is very important since it allows users to have an insightful vision on a subject that might interest thems. The Big Data phenomenon has urged scientists to develop and dedicate an entire research field to data visualization since it allows the user to easily have an idea on the content provided by his different data sources, based on his visual abilities. In this paper, we will present an overview of the literature related to this topic starting by its definition then moving to its challenges and later, presenting its methods and comparing some of its most used tools

I. INTRODUCTION

ITH over 2,5 million terabytes of data created on a daily basis nowadays, the human mind has become overwhelmed with the information flood generated from every source we can imagine, from climate sensors to social media posts and scientific publications. In order to overcome this problem, the best solution is to make a better use of our eyes.

Data visualization is a tool that allows us to see the patterns and connections that matter and then designing that information so that it would make more sens or tell a story or help us focus only on the most relevant information.

Data can tell us amazing stories and data visualization is a powerful means to, on the hand, discover and understand these stories, and on the other hand, to share them with others. Whether it concerns politics, sales, sports, , statistical information, usually presented with words and numbers, remains abstract. Yet, we can still display it visually, and in order to do this, we must give it a form.

For example, we would like to discover the evolution of the minimum hourly wage in Morocco over the last decade [1], the numbers in table 1 can certainly describe it but we need to focus on them in order to find a pattern, while the chart in figure 1 can display that same pattern more quickly and more accuratly. Another similar example, we want to find out which Hollywood movies belong to the same genre and which of them made more income or had more budget. We definitely can answer this query by going through the tables and numbers from IMDb, but we easily get overwhelmed by the information glut. Another way to do it, is to translate these qualitative and quantitative data into shapes, colors, sizes, shaped as round bubbles colored according to their genre and sized according to their income, the budget along with more useful displayed in a tip that may show whenever we hover the In the following paragraphs of this survey, we will define the roles of data visualization as well as its challenges, then we will have an overview over its methods and most used tools and technologies

Overview of Data Visualization

II. DATA VISUALIZATION: ROLES AND CHALLENGES

A. Roles of Data Visualization

According to Mao [3], the iterative process of questioning and and as such, the analyst can easily be misleaded. For this reason, EDA relies mostly on efficient and expressive data visualization. This urged Munzner [4] to define rules of effectiveness and expressiveness of data translation. These rules were used by Mao [3] as guidelines in order to ease the EDA process. order to ease the decision process as stated by Larkin and Simon [START_REF] Lar | Ten Thousand -100[END_REF]. It is done by grouping together all relevant information in more efficient way than pure text and thus, avoiding a large number of search of non-relevant information.

B. Challenges of Data Visualization

With the data being more overwhelming, a good data visualization needs to be precise and at the same time able to provide an overall picture of the data it represents.

1) Expressiveness and Effectiveness

According to Munzner [4], a good data visualization needs to have two essential components, marks and channels.

Marks are basic geometric elements that depict data observations. Figure 3 Identity channels describe what the object is and how it is designed, they are more suitable for qualitative variables. Magnitude channels describe how much of an object there is, so they are more suitable for quantitative variables. The

2) Human Perception and Screen Limits

According to Agrawal et al.

[6], human eyes cannot easily get meaningful information when the data exceedes a certain limit, and very few systems available nowadays are able to display it in a manner that would ease the human perception.

Frölich and Plate [7] argued that the growth of data visualization becomes challenging when it gets limited by the screen dimensions or resolution. A statement confirmed by displays, visualizing every data point can lead to over-plotting, cognitive capacities .

3) Performance

Gorodov and Gubarev [START_REF][END_REF] have stated several problems that Big Data Visualization can face, especially when it comes to performance. These challenges are described as follows:

Visual Noise: It happens when the data is too connected to be easily extracted or separated on the screen. Information Loss: Can be caused by the reduction methods used to extract the most relevant data. Large Image Perception: Lower resolution screens can limit the produced visualizations. 4) Data Visualization VS One of the most common definitions of Big Data is the one 10] who defined it as data able to respond to four criteria or axes. These axes are also e following data visualization opportunities:

Volume: The data visualization must be able to derive meaning from large volumes of data. Variety: The data visualization must be able to combine as many data sources as needed. Velocity: The data visualization must enable businesses to replace batch processing with realtime stream processing.

Value: The data visualization must enable users to create business value by gaining insights from big data.

III. DATA VISUALIZATION METHODS

In this section, we will first talk about the data visualization pipeline, then move on to presenting conventional data visualization methods along with the extension of some of them to handling the Big Data challenges introduced earlier.

A. Data Visualization Pipeline

Introduced by Liu et al. [START_REF][END_REF], it describes the process of data visualization and presents it as a pipeline of five modules:

Data Transformation and Analysis: Extracts relevant data out of the input data. data and its comprehension. This pipeline is described in Figure 4.

B. Data Visualization Methods 1) Conventional Methods:

Khan et al. [START_REF] Khan | Data and Information Visualization Methods and Interactive Mechanisms: A Survey[END_REF] have cited many conventional data visualization methods that are often used, such as tables, histograms, scatter plots, line charts, bar charts, pie charts, area charts, flow charts, bubble charts, multiple data series or combination of charts, time line, Venn diagrams, data flow diagrams, and entity relationship They have also mentioned some data visualization methods that have been used although they are less known compared to the other precited ones, such as parallel coordinates, treemaps, cone trees, and semantic networks.

2) Extension to Big Data:

According to Shull [14], an optimized Big Data Visualization should start by giving a general overview, then allowing filters, zooms and any other detailed information on demand.

Gorodov and Gubarev [START_REF][END_REF] have proposed several approaches to visualize big data, such as multiple views per display, dynamic factors alteration and dynamic filtering, These methods were later categorized according to Big classification is as follows: quality of a data visualization method. As such, many attempts to adopt state of the art technologies to these methods were adopted.

Wang et al. [15] have stated that many big data visualization tools were based on Hadoop architecture. These tools provide efficient data analysis, yet, they lack adequate visualization.

Liu et al.

[16] have proposed a web-based data analysis tool based on WebGL in order to process data using GPU.

IV. DATA VISUALIZATION TOOLS

The literature provides us with with many Data Visualization tools, and in this section, we will try to present the most popular ones.

Suda and Hampton-Smith [16] brought a review identifying 38 data visualization tools that are, according to them, the most used in 2016. Among these tools we will choose to cite the ones that were most cited in the recent reviews.

Sharma [17] has classified these tools into simple user oriented and developer oriented.

A. Simple User Oriented Data Visualization Tools 1) Tableau:

Tableau [18] is a commercial data visualization tool that allows users to easily drag and drop data into the system and have a real-time interaction with different types of visualizations ( embedding and team collaboration. 2) RAW:

Raw [19] is an open source customizable tool that lets users create vector-based data visualizations. It allows Data uploads from different sources such as apps and computers. The visualizations are later exported as SVG or PNG and embedded to the webpage.

3) TimelineJS:

TimelineJS [20] is an open source tool that allows users to create rich and interactive timelines based on data sources provided as Google spreadsheets.

B. Developer Oriented Data Visualization Tools 1) D3JS:

rendering amazing charts out of varied data sources using HTML, SVG, and CSS. This library, is capable of some seriously advanced visualizations with complex data sets and allows easy interaction and sharing.

2) FusionCharts: FusionCharts Suite XT [22] comes with more than 90 chart types, over 965 data-driven maps, and ready-made business dashboards and demos. It is based on a JavaScript API that enables integration with any AJAX application or JavaScript framework. FusionCharts is highly interactive, customizable and multiplatform.

3) Google Charts:

Google Charts [23] is a chart visualization solution used by a majority of users throughout the web. It is highly flexible and provides an excellent set of developer tools behind it. It becomes very handy when it comes to specialist visualizations such as geocharts and gauges. It also includes built-in animation and user interaction controls. 4) HighCharts:

HighCharts [24] is a JavaScript charting library that provides the user with a wide range of charts types he might use. The SVG rendering for modern browsers and VML rendering for Internet Explorer. The charts are beautifully animated and the framework supports live data streams. It is free to download and non-commercial use (and licensable for commercial use).

V. A COMPARATIVE REVIEW OF DATA VISUALIZATIONS

TOOLS

With the important number of visualization tools available, it can be confusing to choose the right tool for the right purpose. This section presents some of the most popular open source JavaScript libraries and the possibilities offered by each one of them.

These Data visualizations tools can be provided as services, platforms, widgets or libraries.

A. Data visualization tools types

Leishi Zhang [START_REF] Zhang | Visual analytics for the big data era A comparative review of state-of-the-art commercial systems[END_REF] differentiates two types of tools: 1) Open Source Toolkits

A number of open-source Visual Analytics toolkits exist; each covers a specific set of functionalities for visualization, analysis and interaction.

The functionality of these toolkits is compared according to three criteria: (1) visualization functions, (2) analysis capabilities, and (3) supported development environment [START_REF] Zhang | Visual analytics for the big data era A comparative review of state-of-the-art commercial systems[END_REF].

2) Commercial Visual Analytic Systems An alternative is to resort to software suites which integrate required functionality in software systems that work either standalone, or integrate, more or less seamlessly, into an existing information infrastructure. Example systems include Tableau [18], Spotfire [26] , and QlikView [27]. Commercial toolkits typically require no or only limited configurations or program adjustments, to become operational. The principal goal of the survey is to provide to developers a reference for choosing the adapted library to given problem. We will do it by highlighting the visualizations techniques provided by each of these tools. We divide visualization techniques into graphical representations of data and interaction techniques and we move to compare systems and architectures supported for each tools.

B. Functional comparison:

According to Leishi Zhang [START_REF] Zhang | Visual analytics for the big data era A comparative review of state-of-the-art commercial systems[END_REF], we divide visualization techniques into graphical representations of data and interaction techniques to analyze the visualization functionality of each system. The visual part is related to the form which the data is displayed like: bar chart, line chart, pie chart. Interaction technique like zooming, panning, etc..

1) Graphical representation: a. Numerical data

There are several methods to present the relationship between Numerical data, the most common are: bar chart, line chart, pie chart and scatter plots these methods are especially used for data with low dimensions. However, for data with higher dimensionality, some other methods are used like: parallel coordinates, heat maps and scatter plot matrix.

b. Text web:

the most used way to present the qualitative data because it makes it easy to spot word frequencies. The word that appears in bold in front is the most used in an interview, a document or a text. Usually Tags text is single words shown with font size or color. This method helps to collect quickly the most important and interesting terms. It is appreciated for being more captivating for the audience and make a quick impact, Moreover it is simple, easy to understand and easy to share.

c. Geo related data

Geo-visualization short for Geographic Visualization, is the creation and use of visual representations to facilitate thinking, understanding, and knowledge construction about human and physical environments, at geographic scales of measurement [28]. The important stories that numbers have to tell often involve location [START_REF] Few | Introduction to Geographical Data Visualization -Perceptual Edge[END_REF].So it will be easier for the analyst that they be represented on a map. Visualizations tools are challenged to provide geographical projections methods to respond to user's need.

d. Network data (graph):

Graphs and networks visualization is an important part of data visualization because it is used in many applications to visualize interactions within many networks in different fields including biology (biological network analysis), finance, web sociology (social media networks, friendship and acquaintance networks, collaboration..) network theory, etc.. Networking graph can be based on hierarchical components i.e parent-child relations between data items as well as nonhierarchical components [START_REF] Holten | Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data[END_REF]. In his paper, Danny Holten [START_REF] Holten | Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data[END_REF] proposes some Tree Visualization Techniques to present graph in case of hierarchical structure such as treemap and the hyperbolic view.

2) Interactivity: Having a data visualization interface of allowing the user interaction is a critical need. Muzammil and Sarwar describe on their paper [START_REF] Khan | Data and Information Visualization Methods, and Interactive Mechanisms: A Survey[END_REF] that users can interact with interfaces or visualization in different ways by means of mouse over, single click, double click, or can add multiple interactive options by mouse right button click. There are many interactive techniques available to interact with charts or graphical representation to understand the drill down details. Card et al introduce the interactive mechanism of visualization in 1999. This mechanism describes human interaction indifferent phases as shown in the following diagram. [START_REF] Khan | Data and Information Visualization Methods, and Interactive Mechanisms: A Survey[END_REF] This table summarizes some interactivity action for each tool: In this paper, we have defined the roles of Data Visualization and then dove into its challenges from human perception to performance and to handling big data issues. We have also presented a survey on state of the art Data Visualization methodologies and tools.

As shown, data visualization methods were categorized into conventional and big data oriented, while the tools were classified into simple user oriented and developer oriented.

O

  Fig. 1. A Chart Displaying the Evolution of the Minimum Hourly Wage in Morocco from 1994 to 2015 [1]

  -1 is an example for marks that include points, lines and areas. Channels control the marks described in Figure3-2.

Figure 3 -

 3 Figure 3-3 has categorized channels into identity channels and magnitude channels.Identity channels describe what the object is and how it is designed, they are more suitable for qualitative variables. Magnitude channels describe how much of an object there is, so they are more suitable for quantitative variables. The

Fig. 2 .

 2 Fig. 2. Movies Explorer [2]

  Filtering: Selects the data to be visualized. Mapping: Matches the filtered data with Rendering: Transforms geometric data into image data.

Fig. 4 .

 4 Fig.4. Data Visualization Pipeline[START_REF][END_REF]

Fig. 5 .

 5 Fig. 5. Interactive Mechanism[START_REF] Khan | Data and Information Visualization Methods, and Interactive Mechanisms: A Survey[END_REF]

  Data visualization changes the way people experience information and the way we live since it allows us to have an in-depth exploration regarding several issues: mobility, social media, geolocalization, data mashups, big data, globalization and science communication.

TABLE I .

 I A TABLE DISPLAYING THE EVOLUTION OF THE MINIMUM HOURLY WAGE IN MOROCCO FROM 1994 TO 2015 [1]

	Year	Minimum Wage
		(MAD per Hour)
	1994	7,26
	1996	7,98
	2000	8,78
	2004	9,22
	2004	9,66
	2008	10,14
	2009	10,64
	2011	11,7
	2013	12,24
	2014	12,85
	2015	13,46

TABLE II .

 II CLASSIFICATION OF VISUALIZATION METHODS[START_REF][END_REF]

	Method Name	Big Data Class
	Treemap	Can only be applied to hierarchical data
	Circle Packing	Can only be applied to hierarchical data
	Sunburst	Volume + Velocity
	Parallel Coordinates	Volume + Velocity + Variety
	Streamgraph	Volume + Velocity
	Circular Network Diagram	Volume + Velocity

TABLE IV .

 IV A TABLE DISPLAYING SOME INTERACTIVITY ACTIONS FOR JS

TOOLS

[32]