Joël Toussaint
email: joel.toussaint@udamail.fr

Nancy El

Alexandre Guitton
email: alexandre.guitton@univ-bpclermont.fr

Performance analysis of the on-the-air activation in LoRaWAN

Long-range low-power communications are starting to replace short-range low-power communications in monitoring applications based on wireless sensor networks, both in rural and urban environments, due to the small deployment cost of long-range technologies. In this paper, we focus on the MAC layer of the recent LoRaWAN (long-range wide area network) standard, and specifically on the on-the-air activation procedure, which defines how nodes join an existing network. We propose a Markov chain model of the on-the-air activation, and we derive the expected delay and the expected energy required to join the network. We analyze the impact of several parameters on these metrics, including traffic conditions, duty cycles, and channel availability. We also discuss the impact of the regional settings of the standard. To the best of our knowledge, this is the first analysis of the MAC layer of LoRaWAN.

I. INTRODUCTION

Wireless sensor networks (WSNs) are largely used to monitor rural environments [START_REF] Oliveira | Wireless Sensor Networks: a Survey on Environmental Monitoring[END_REF], [START_REF] Rohokale | A cooperative Internet of Things (IoT) for rural healthcare monitoring and control[END_REF] and urban environments [START_REF] Fafoutis | Energy Harvesting -Wireless Sensor Networks for Indoors Applications Using IEEE 802.11[END_REF]. Indeed, WSNs have a strong potential thanks to their low cost, their autonomy in energy, and the disposability of the individual sensors. Wireless sensor networks have also found many applications with the Internet of Things paradigm, where the Internet is coupled with the physical world through sensors and actuators. The IEEE 802.15.4 standard [START_REF]Part 15.4 : low-rate wireless personal area networks (LR-WPANs)[END_REF], initially designed in 2003 [START_REF]Part 15.4 : wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANs)[END_REF], is by far the main standard for wireless communications in WSNs [START_REF] Oliveira | Wireless Sensor Networks: a Survey on Environmental Monitoring[END_REF], [START_REF] Zanella | Internet of Things for Smart Cities[END_REF].

Several researchers have analyzed the performance of the MAC layer of IEEE 802. [START_REF] Centenaro | Long-range communications in unlicensed bands: the rising stars in the IoT and smart city scenarios[END_REF].4, as it has a direct impact on the applications using this standard. Most of the analytical analyses propose a Markov chain model, adapted to different cases. For instance, the behavior of a node during the contention access period of the beacon-enabled mode is studied in [START_REF] Tao | Performance analysis and a proposed improvement for the IEEE 802.15.4 contention access period[END_REF] when the network is saturated, and in [START_REF] Park | A generalized Markov chain model for effective analysis of slotted IEEE 802.15[END_REF] when the network is not saturated. In [START_REF] Ngangue Ndih | An analytical model for the contention access period of the slotted IEEE 802.15.4 with service differentiation[END_REF], the authors study the traffic differentiation during the contention access period. In [START_REF] Striccoli | A Markov model for characterizing IEEE 802.15.4 MAC layer in noisy environments[END_REF], the authors model the impact of a lossy channel (due to interference and poor link quality) on the communication. In [START_REF] Xiao | An analytical model for IEEE 802.15.4 with sleep mode based on time-varying queue[END_REF], the authors model the accumulation of the traffic due to the long inactive periods of the beacon-enabled mode. IEEE 802.15.4 has only short-range capabilities: the communication range traditionally varies between tens of meters (in indoor environment) to up to one hundred meters (in outdoor environment and favorable conditions, such as line of sight). To compensate for this limitation, it is possible to deploy more nodes in order to achieve network connectivity. This comes at an extra cost, which might be prohibitive in large-scale applications such as volcano monitoring, forest monitoring, or large urban deployments.

Recently, long-range low-power wireless standards have emerged, such as Sigfox [START_REF] Sigfox | [END_REF], Ingenu [START_REF] Ingenu | [END_REF] and Lo-RaWAN [START_REF] Sornin | LoRaWAN Specification[END_REF]. These standards enable one-hop communications ranging from 2 km in dense urban environments to 30 km in rural environments. These standards bring high expectations, as they create new possibilities for low-power, largescale monitoring applications. Since most of these standards are proprietary, few research works have focused on them. One of these works is [START_REF] Centenaro | Long-range communications in unlicensed bands: the rising stars in the IoT and smart city scenarios[END_REF], in which the authors have studied the physical layer of LoRaWAN in a real deployment.

In this paper, we study the MAC layer of the LoRaWAN standard (which is open and freely available), and we focus on the on-the-air activation procedure, which allows nodes to join an existing network. To do this, we propose a Markov chain model of the activation procedure, and we derive two important performance metrics: the expected delay to complete the activation, and the required energy. The study is based on the EU863-870 MHz regional setting (also other regional settings are discussed in the paper) for a single gateway. To the best of our knowledge, this is the first analytical study of the MAC layer of LoRaWAN.

The remainder of this paper is organized as follows. Section II describes the LoRaWAN standard and focuses on the activation procedure. Section III proposes our Markov chain model. Section IV presents our performance evaluation for different parameters. Section V initiates a discussion, which includes the impact of the other regional settings of LoRaWAN. Finally, Section VI concludes our work.

II. DESCRIPTION OF THE LORAWAN STANDARD

LoRaWAN [START_REF] Sornin | LoRaWAN Specification[END_REF] is a LPWAN (Low-Power Wide Area Network) communication standard. It aims to exchange data (such as alarms, meters, or monitoring devices) between low-power devices and a network server, through gateways over long distances. LoRaWAN achieves long-range radio communications at small bit rates (from 0.3 to 50 kbps) and is therefore well suited for many applications, including the Internet of Things. Experiments show transmission ranges of up to 1.3 km in an urban environment with a frame loss of 10% [START_REF] Semtech | LoRa TM modulation basics[END_REF], [START_REF] Centenaro | Long-range communications in unlicensed bands: the rising stars in the IoT and smart city scenarios[END_REF], and of up to 21.6 km in line of sight conditions without loss [START_REF] Libelium | Waspmote LoRa 868 MHz 915 MHz SX1272 networking guide[END_REF].

LoRaWAN architecture is based on a star topology. Enddevices exchange frames with gateways. Gateways relay the frames to the network server thanks to a classical internet infrastructure. Long-range radio links are achieved with a proprietary modulation technique called Lora TM , developed by the Semtech company, and based on the Chirp Spread Spectrum (CSS) technology 1 . LoRa uses ISM bands, depending on regional settings: we focus mainly on the European 863-870 MHz band. LoRaWAN also proposes an Adaptive Data Rate (ADR) mechanism in order to adapt the transmission characteristics (data rate, spreading factor, and bandwidth) to the propagation conditions. Data rates range from DR0 (the lowest data rate) to DR7 (the highest data rate).

LoRaWAN defines three classes of end-devices: class A, class B and class C. Class A is the default class, and is mandatory for all devices. Communication is initiated by end-devices: uplink communications (that is, to the gateway) occur when the end-device has data to transmit, and downlink communication (that is, from the gateway) are possible only after an uplink transmission. Uplink communications are performed on a random channel. A long preamble is sent before the payload. Downlink transmissions have to start at the beginning of two receive windows. Downlink communications during the first receive window are performed on the same channel as the uplink transmission, with the same data rate (by default). Downlink communications during the second receive window are performed on a fixed channel and with a fixed data rate. After having sent a frame on a given channel, the node refrains from using any channel of the sub-band during t of f = t air /δ -t air time units, where t air is the time on air of the frame sent, and δ is the duty-cycle for this sub-band (which is limited to 1%). Class B introduces beacons which allow enddevices to be synchronized and enable scheduled downlink communications. Class C removes the energy constraint by allowing nodes to continuously listen to the medium.

An activation procedure is required for end-devices to participate to network activities. LoRaWAN defines two activation procedures: the activation by personalization (ABP), and the on-the-air activation (OTAA). In the ABP, end-devices possess in their memory the required information: thus, no communication is required to join the network. In the OTAA, the enddevice sends a join request2 to the gateway, which forwards the frame to the network server. The network server responds with a join accept 3 , which is forwarded by the gateway. The gateway can transmit this join accept during either the first receive window (which occur five seconds after the end of transmission of the join request) or during the second receive window (which occur six seconds after the end of transmission of the join request). In this paper, we focus on OTAA. Note that the activation procedure is the same for all three classes. Figure 1 depicts the medium access in the class A of LoRaWAN, which is used during the activation procedure, and during the data exchange (with different timers). After a transmission, a first receive window is opened (d 1 = 5 during the activation, and d 1 = 1 once the node is activated). If there is no preamble detected during the first receive window, or if a transmission for another node is detected, the second receive window is opened (d 2 = 6 during the activation, and d 2 = 2 once the node is activated). Independently of the fact that a preamble is received or not, the channel (as well as other channels of the same sub-band) cannot be used for a duration d o , depending on the duty-cycle.

III. MARKOV CHAIN MODEL

In this section, we start by presenting our hypotheses. Then, we present our Markov chain model for the on-theair activation. Finally, we describe the computation of our two performance metrics: the expected delay to complete the activation procedure, and the expected energy required.

A. Hypotheses

We describe our simplification hypotheses in the following. a) Hypotheses concerning the physical layer: We assume that when a transmitter sends a preamble, the receiving node detects this preamble, thanks to the robust CSS modulation which is central in the physical layer design of LoRaWAN. We assume that when several transmitters send a preamble simultaneously, the receiving node detects that the preamble is incorrect. In other words, we ignore the capture effect. Moreover, we assume that collisions between uplink and downlink frames might happen.

b) Hypotheses concerning the gateway: We assume that there is a single gateway. We assume that the gateway is sending only join accept frames (that is, there is no confirmed data requiring acknowledgments), and that the gateway is not sending a frame while a join request frame is sent. c) Hypotheses concerning the nodes: We assume that nodes use the data rate DR0 for the activation procedure (which is the smallest data rate, ensuring the strongest link quality) and the data transmission (of activated nodes). We assume that the MAC payload of data frames is between 13 bytes and 18 bytes (this assumption has a small impact on the Markov chain, and is discussed in Section V). We also assume that the detection of the preamble lasts for the whole duration of the preamble.

B. Model

Figure 2 represents our Markov chain model for the activation procedure of LoRaWAN. In the send request state, the node sends a join request and goes to the receive 1 state. In the receive 1 state, the node opens the first receive window. If a preamble is detected, the node goes to the preamble 1 state, then to the check 1 state if the preamble is correct, and then to the activated state if the join accept is successfully received. Otherwise, the node goes either to the receive 2 state or to the wait state, depending on the duration of the potential preamble and frame received. In the receive 2 state, the node opens the second receive window, and follows a process similar to the receive 1 state. In the wait state, the node waits for a given amount of time until it can reuse a sub-band, and goes back to the send request state. Finally, in the activated state, the node has successfully joined the network and is ready to send data. We use the following notations. n I denotes the number of inactivated nodes (that is, nodes that are requesting to join the network), and n A the number of activated nodes (that is, nodes that have already joined the network). n SB is the number of sub-bands, and n C is the number of channels per sub-band. α ∈ [0; 1] represents the link quality: when α = 1, the frame error rate is 0. γ determines whether the gateway sends the join accept during the first receive window (γ = 1) or during the second receive window (γ = 0). δ ∈ [0; 0.01] is the duty cycle of activated nodes per sub-band (which is limited to 1% per sub-band by the standard). Traffic is generated by activated nodes with probability

pr 1 ,p 1 pr 1 ,r 2 pp 1 ,w pp 1 ,c 1 pp 1 ,r 2 pc 1 ,r 2 pc 1 ,a pc 1 ,w pr 2 ,p 2 pr 2 ,w pp 2 ,w pp 2 ,c 2 pc 2 ,a pc 2 ,w
τ A • δ • n SB , with τ A ∈ [0; 1]: when τ A = 1, the network is saturated.
Several probabilities of Figure 2 depend on the availability of a channel at a given time, which depends on the probability that no other node uses this channel. The probability that an inactivated node does not use a given channel is q I = 1 -0.001 nC •nSB . Indeed, 1 -q I is the probability that the node sends a join request on this channel (out of the n C • n SB possible channels), given the fact that the duty-cycle during the activation procedure is 0.1% 4 . The probability that an activated node does not use a given channel is q A = 1 -δ•τA nC . Indeed, 1 -q A is the probability that the node sends a data frame on this channel (as it produces δ • τ A • n SB data frames per time unit, distributed among n SB sub-bands and n C channels per sub-band). Probability p s,r1 to open the first receive window after having sent a join request (see Equation 1) is equal to 1.

p s,r1 = 1 (1)
Probability p r1,r2 is the probability that the node does not detect any preamble during the first receive window, and is given in Equation 2. It is equal to the probability that there is no transmission from the gateway, from any inactivated node, nor from any activated node. The first factor represents the absence of transmission from the gateway, and is obtained through the computation of the probability that the gateway is sending a join accept, which depends on the fact: (i) that there was no interference with the send request (modeled with q nI I • q nA A ), (ii) that the send request was successfully decoded (modeled with α), and (iii) that the gateway replies during the first receive window (modeled with γ). The second factor represents the absence of transmission from inactivated nodes. The third factor represents the absence of transmission from activated nodes. Probability p r1,p1 is obtained by complementarity (see Equation 3).

p r1,r2 = (1 -α • γ • q nI I • q nA A ) • q nI I • q nA A (2) p r1,p1 = 1 -p r1,r2 (3)
Probability p p1,w is the probability that the preamble received during the first receive window is incorrect and that its duration exceeds the delay of 1 s between the two receive windows. Since the longest preamble duration is 401.41 ms (for DR0, which corresponds to a spreading factor of 12 and a bandwidth of 125 kHz), p p1,w = 0 (see Equation 4). Probability p p1,c1 is the probability that the preamble received is correct, and is given in Equation 5. It is equal to the probability that one preamble exactly is received given the fact that at least one preamble was sent. Let us denote by x the number of preambles sent. p p1,c1 = P(x = 1|x ≥ 1) = P(x = 1)/P(x ≥ 1) = P(x = 1)/p r1,p1 . P(x = 1) is the sum of the following mutually exclusive probabilities: the probability that only the gateway sends a preamble, the probability that only one inactivated node sends a preamble, and the probability that only one activated node sends a preamble. Probability p p1,r2 is obtained by complementarity (see Equation 6).

p p1,w = 0 (4) P(x = 1) = α • γ • q nI I • q nA A • q nI I • q nA A + (1 -α • γ • q nI I • q nA A ) • q nI -1 I (1 -q I )n I • q nA A + (1 -α • γ • q nI I • q nA A ) • q nI I • q nA-1 A (1 -q A )n A p p1,c1 = P(x = 1)/p r1,p1 (5)
p p1,r2 = 1 -p p1,w -p p1,c1 (6)
Probability p c1,a is the probability that the received frame is the expected join accept frame, and is given in Equation 7. It is equal to the fact that the gateway received and decoded the join request, and that the join accept is successfully received and decoded. Probability p c1,r2 is the probability that the received frame is not the correct join accept frame (otherwise, the transition would be p c1,a ), and that it is small enough so that the reception duration does not exceed the delay between the two receive windows (otherwise, the transition would be p c1,w ). It is given in Equation 8. Note that out of the three types of frames which can be received (join accept, join request, and data), only the join accept frames cause the node to open the second receive window. Indeed, the time on air of join accept frames (including the preamble) is 991.23 ms for DR0 (since the MAC payload length is 12 bytes), which means that the node has time to open the second receive window only when an incorrect join accept frame is received. The time on air of join request frames (including the preamble) and data frames of 13 bytes or more (including the preamble) is larger than 1 s for DR0, which means that the node does not have time to open the second receive window when such a frame is received. In this case, the node goes back directly to the wait state, which is modeled in Equation 9.

p c1,a = α • γ • q nI I • q nA A • q nI I • q nA A • α (7) p c1,r2 = α • γ • q nI I • q nA A • q nI I • q nA A (1 -α) (8) p c1,w = 1 -p c1,r2 -p c1,a (9)
Probability p r2,p2 is the probability that the node detects a preamble during the second receive window, and is given in Equation 10. Since the second receive window is opened on a channel that is exclusive to the gateway, it is not possible for other nodes to send on this channel 5 . Thus, p r2,p2 only depends on the fact that the gateway received the join request correctly (modeled with α) and without interference (modeled with q nI I • q nA A ), and that it replied on the second receive window (modeled with 1 -γ). Probability p r2,w is obtained by complementarity (see Equation 11).

p r2,p2 = α(1 -γ)q nI I • q nA A (10) p r2,w = 1 -p r2,p2 (11)
Probability p p2,c2 is the probability that the node detects a preamble during the second receive window, and is given in Equation 12. Since only the gateway is allowed to transmit during the second receive window, it is not possible for the preamble to be received incorrectly. Probability p p2,w is obtained by complementarity (see Equation 13).

p p2,c2 = 1 (12) p p2,w = 0 (13)
Probability p c2,a is the probability that the frame received during the second receive window is a join accept for the node, and is given in Equation 14. Since the gateway is the only node 5 According to the standard for the EU863-870 MHz ISM band, the RX2 receive window is by default on channel 869.525 MHz (see paragraph 7.1.7), and this channel is neither included in the default join request channel list (see Table 13 allowed to send on the channel, and since we assumed that the gateway is always able to send a join accept, p c2,a is equal to the probability that the join accept is successfully received by the node 6 . Probability p c2,w is obtained by complementarity (see Equation 15).

p c2,a = α (14) p c2,w = 1 -α (15)
Probability p w,s to send a join request after the wait state (see Equation 16) is equal to one.

p w,s = 1 (16)

C. Computation of performance metrics

In the following, we use the Markov chain model to compute the expected delay and energy consumption of the activation procedure of LoRaWAN.

Our Markov chain is an absorbing chain, because it is possible to reach the activated state (which is absorbing) from any state. Let us denote by N the fundamental matrix of our Markov chain: N i,j represents the expected number of visits of state j when starting from state i. Since the initial state is the send request state, the expected number of visits V can be computed by V = 1 s • N , where 1 s is a row vector having the first entry (representing the send request state) equal to 1, and all other entries equal to 0. In the remainder of this part, we compute the expected delay of the activation based on V and on the delay of each state. We compute the expected energy of the activation procedure based on V , on the delay of each state, and on the energy of each state.

The expected delay of the activation procedure is equal to V • D, where D is a column vector having each entry representing the expected duration spent in the corresponding state. D s is the duration of the send request state, and is equal to the time between the beginning of the transmission of the send request and the start of the first receive window. Thus, D s is equal to the time on air of the join request plus five seconds. D r1 is at least the time required to detect a preamble (according to paragraph 3.3.3 of the standard): we assumed that D r1 is equal to the duration of a preamble. D p1 is equal to 0, since the preamble 1 state is simply used to determine whether the received preamble was correct or not. D c1 has two terms: the first is the average time on air of received frames minus the duration of the preamble (which was already accounted for in D r1 ), and the second is the time before the second receive window. The first term can be computed using a weighted average, since the probability to receive a small join accept frame is p c1,a /α, and since other frames (join requests or data frames of 13 to 18 bytes) have the same time on air duration. The second term is equal to the delay between the two receive windows minus the average time on air of the received frame. D r2 is equal to the duration of the preamble. D p2 is equal to 0. D c2 is the time on air of the join accept frame minus the duration of the preamble. Finally, D w is the time during which the sub-band is unavailable after having sent a join request, divided by the number of available sub-bands.

The expected energy of the activation procedure is equal to V • E, where E is a column vector having each entry representing the expected energy consumption of the corresponding state. E s is the energy spent while transmitting the join request, plus the energy spent while waiting for the first receive window to open. E r1 (respectively E r2 , and E c2 ) is the energy spent while listening to the potential preamble of the first receive window (respectively potential preamble of the second receive window, and frame of the second receive window). E p1 and E p2 are both equal to 0. E c1 has two terms: the first term is equal to the energy spent while receiving a frame (whose duration is given by the first term of D c1 ) and the second term is equal to the energy spent in idle mode before the second receive window opens (whose duration is the second term of D c1 ). Finally, E w is equal to the energy spent in idle mode while waiting for a channel to become available.

IV. PERFORMANCE EVALUATION

In this section, we evaluate the performance of the activation procedure, in terms of expected delay and expected energy consumption.

A. Parameter settings

We ran our simulations using Scilab, and we considered the following default parameters. The channel quality is high (α = 0.99) and the network is saturated (τ A = 1). There are n C = 3 channels for each of the n SB = 2 sub-bands. There are n I = 10 inactivated nodes (in addition to the node being studied) and n A = 10 activated nodes. The first receive window is used by default (γ = 1), and the duty cycle per sub-band of activated nodes is δ = 0.01.

We used the energy consumption settings of the Semtech SX1272 component, designed for LoRaWAN: the transmit power is 90 mA (at 17 dBm), the reception power is 10.8 mA, and the idle power is 0.1 mA. The voltage is 1.5 V.

From these settings, we obtained the following (rounded) values for vectors D and E (the order of states in the vectors being: send request, receive 1, preamble 1, check 1, receive 2, preamble 2, check 2, and wait): D = 6.16 0.40 0 0.60 0.40 0 0.59 576.96

T , E = 0.08 0.007 0 0.01 0.007 0 0.01 9.10 -5 T .

B. Results

Figure 3 presents the delay as a function of α and γ. The impact of the channel quality α on the expected delay is significant. When the channel quality is low (α = 0.9), join requests or join accepts might be lost, which causes the node to go to the wait state often and induces a large delay. Indeed, the expected number of visits of the wait state is 0.32 when α = 0.9 and γ = 0, 0.07 when α = 1 and γ = 0. As a result, the reduction of delay between α = 0.9 and α = 1 for γ = 0 is 146.9 s (as the wait state has a very large duration, which is 577 s in our setup) 7 . The impact of γ, which determines the choice of receive window, is also significant for the delay. Indeed, when γ = 1, collisions with transmissions from other nodes are likely to occur during either the transmission of the join request, or the transmission of the join accept. These collisions cause the node to go back to the wait state. When γ = 0, collisions can occur during the transmission of the join request, but they cannot occur during the transmission of the join accept, as the gateway is the only node allowed to transmit on the channel dedicated to the second receive window. Thus, the number of expected visits to the wait state reduces, which in turn reduces the expected delay. Figure 4 presents the energy as a function of α and γ. The impact of the channel quality α on the expected energy consumption is important. Indeed, a bad channel quality yields to frame loss and thus forces a node to go back to the wait state often in order to reach the activated state. The larger energy consumption when γ = 1 is the energy cost of retransmitting join requests (and additional listening periods).

Figure 5 presents the delay as a function of the total number of channels and the number of available sub-bands n SB . The x-axis represents the total number of channels, which is the product of n C and n SB . The expected delay decreases with the number of channels as collisions during the transmission of the send request are less likely when there is a large number of channels. The expected delay is impacted by the number of sub-bands in two ways: (i) when the number of sub-bands increases, the time duration of the wait state is reduced as it is directly impacted by the number of sub-bands, and (ii) when the number of sub-bands increases, the traffic increases (as δ and τ A are defined per sub-band), which increases the delay. However, the reduction of the wait duration is more significant than the increase in the number of collisions. Overall, the reduction in delay when n SB varies from one to three is between 19% (for a total number of channels of six) and 49% (for a total number of channels of eighteen). Figure 6 presents the energy consumption of an activation as a function of the total number of channels and on the number of available sub-bands n SB . The energy consumption decreases with the total number of channels as the probability of collisions decreases when the number of channels per subband is large. Moreover, when n SB is large, the node transmits join requests more frequently (as the duration of the wait state depends on the number of sub-bands). Overall, we notice an increase of 6% in energy consumption when two sub-bands are used and an increase of 13% when three sub-bands are used.

Figure 7 presents the delay as a function of the number of nodes and proportion of inactivated nodes, in three scenarios: when no node is activated, when half of the nodes are activated, and when all nodes are activated. The delay increases with the number of nodes in the network for all the scenarios. In the first scenario, the energy increases slightly as all nodes send their join requests with a small duty cycle of 0.1%. Thus, collisions do not happen frequently and the number of visits of the wait state remains small. In the second scenario, the delay increases consistently. Indeed, the activated nodes send data frames with a larger duty cycle δ of 1%. In this case, collisions and interferences appear more frequently and thus the number of visits of the wait state increases. The worst case scenario is the third scenario, in which all nodes are activated. All nodes send data frames with a large duty cycle δ of 1%, and thus, the delay increases drastically. Figure 8 presents the energy as a function of the number of nodes and proportion of inactivated nodes. The energy consumption follows the same behavior as the delay as it depends on the time spent (and the energy consumed) in each state. When the number of activated nodes increases in the network, the energy consumption of an activation increases as the number of visits to the send request state (which is the state consuming the most energy) increases. Moreover, the energy consumption increases with the number of nodes in the network as the number of collisions increases in this case.

V. DISCUSSION

In this section, we discuss the impact of the regional settings on the model, as well as the impact of different data rates.

A. Regional settings

The Markov model described in this paper is based on the EU 863-870MHz ISM band (Section 7.1 of [START_REF] Sornin | LoRaWAN Specification[END_REF]). The standard describes three other regional settings.

The US 902-928 MHz ISM band (Section 7.2 of [START_REF] Sornin | LoRaWAN Specification[END_REF]) presents significant differences with the EU 863-870MHz ISM band. In the US band, there are 64+8=72 default uplink channels and 8 default downlink channels (instead of 6 default channels used for both uplink and downlink, and one specific downlink channel). Because of the dedicated downlink channels, there is no interference between frames from the gateway and frames from other nodes. The probability of interference from other nodes is very small due to the large number of uplink channels. The probability of overhearing a frame from the gateway to another node is small too, due to the relatively large number of downlink channels. Join requests are sent alternatively on one of the 64 uplink channels with DR0, and on one of the 8 channels with a faster data-rate (namely, DR4) 8 . Finally, the data rates are larger than with the EU 863-870MHz setting (since DR0 uses a spreading factor of 10 instead of 12, since DR4 is the minimum data rate for the 8 uplink channels, and since the data rate of downlink channels is much larger than DR0).

The China 779-787MHz ISM band (Section 7.3 of [START_REF] Sornin | LoRaWAN Specification[END_REF]) is similar to the EU 863-870MHz setting. The only difference is the maximum transmission power, which is smaller than with the EU 863-870MHz setting, and thus reduces the energy consumption (as well as the communication range).

The EU 432MHz ISM band (Section 7.4 of [START_REF] Sornin | LoRaWAN Specification[END_REF]) is similar to the EU 863-870MHz setting. The only difference is the number of default channels, which is only three (plus a dedicated channel for the second receive window).

B. Impact of data rates

The Markov model depends on the data rates used for join requests, join accepts and data frames. For instance, the probability p c1,r2 increases with the data rate, as with larger data rates, larger frames can be received and discarded in less than 1 s (which is the time between the two receive windows). The probability of collisions also decreases with the data rate, as frames spend less time on the air. Also, the reduction of the time on air yields a reduction of the wait state duration, which has a significant impact on the overall delay.

VI. CONCLUSIONS

LoRaWAN is a recent, promising technology that is expected to be used in several large-scale monitoring applications in both rural and urban environments. In this paper, we proposed to study its MAC layer performance. To do this, we proposed a Markov chain model for the on-the-air activation

Figure 1 .

 1 Figure 1. Medium access in the class A of LoRaWAN.

Figure 2 .

 2 Figure 2. Markov chain model for the on-the-air activation of LoRaWAN.

Figure 3 .

 3 Figure 3. The expected duration of an activation is greatly impacted by the channel quality α and by γ.

Figure 4 .

 4 Figure 4. The expected energy consumption of an activation depends on the channel quality and γ as well.

Figure 5 .

 5 Figure 5. The expected duration of an activation depends on the total number of channels and the number of sub-bands.

Figure 6 .

 6 Figure 6. The expected energy consumption depends on the total number of channels, and on the number of available sub-bands.

Figure 7 .

 7 Figure 7. The expected delay is mainly impacted by the number of activated nodes.

Figure 8 .

 8 Figure 8. The expected energy consumption increases with the number of activated nodes.

  in paragraph 7.1.2) nor in the default data channel list (see Table 12 in paragraph 7.1.2).

Note that in Europe and China, the highest data rate available (50 kbps) is achieved using an FSK modulation.

The size of the join request payload is 18 bytes, see 6.2.4 of[START_REF] Sornin | LoRaWAN Specification[END_REF].

The size of the join accept payload is 12 bytes, see 6.2.5 of[START_REF] Sornin | LoRaWAN Specification[END_REF].

According to paragraph 7.1.2 of the standard, the duty-cycle limitation of join requests is 0.1%, independently of the number of sub-bands (unlike the data duty-cycle limitation).

Note that it is not possible to receive a join accept intended to another inactivated node, as it would mean that the two join requests were sent simultaneously.

Note that the difference in the number of visits of the wait state accounts for about 145.1 s of these 146.9 s. The extra delay is due to changes in the number of visits of the other, shorter states.

Modeling this alternation would require to split several states (including the send request state) in two in the Markov chain model. procedure of the MAC layer. In this model, we took in account interferences with other nodes sending data frames or join request frames. We showed that the expected delay and energy consumption depend on network parameters such as number of channels per sub-band, number of sub-bands, and gateway configuration. We believe that this first study of the MAC layer of LoRaWAN will improve the understanding of the behavior and performance of this new standard.

Acknowledgment: This work has been partially funded by the Clervolc laboratory of excellence.


Mathieu Lafourcade
email: mathieu.lafourcade@lirmm.fr

Nathalie Le Brun

Alain Joubert
email: alain.joubert@lirmm.fr

LikeIt, un jeu pour construire une ressource lexicale de polarité

Keywords: polarité, sentiment, réseau lexical, crowdsourcing, GWAP polarity, feelings, lexical network, crowdsourcing, GWAP

Introduction

Être capable de caractériser les sentiments est devenu incontournable dans le cadre d'applications dédiées à l'analyse de discours politiques, ou d'opinions relatives à la fourniture de services touristiques, culturels, ou de biens de grande consommation. La constitution d'une ressource lexicale de polarité (associer à un terme une connotation positive, négative, neutre, et éventuellement objective ou subjective) est un préalable à ce type de recherche, que les approches soient statistiques supervisées ou plus linguistiques [START_REF] Brun | Detecting opinions using Deep Syntactic Analysis[END_REF]. Une telle polarité peut être exprimée avec une valeur numérique [START_REF] Taboada | Lexicon-based methods for sentiment analysis[END_REF] ou plusieurs valeurs. Par exemple, [START_REF] Saif | Crowdsourcing a Word-Emotion Association Lexicon[END_REF] ont utilisé deux valeurs (positif/négatif) pour leur ressource (EmoLex) de polarité/sentiment pour l'anglais obtenue par crowdsourcing à l'aide d'Amazon Mechanical Turk (ce qui peut poser problème, voir [START_REF] Fort K | Crowdsourcing for Language Resource Development : Criticisms about Amazon Mechanical Turk Overpowering Use[END_REF]). SentiWordNet [START_REF] Esuli | SentiWordNet: a publicly available lexical resource for opinion mining[END_REF] tout comme WordNet Affect [START_REF] Strapparava | WordNet Affect : an affective extension of WordNet[END_REF]) sont des extensions de WordNet où les termes sont polarisés sur trois valeurs (positif, négatif et objectif) dont la dernière s'oppose aux deux premières. Des approches par propagation à partir d'un noyau manuel (voir, par exemple (Gala et [START_REF] Et Brun C | Propagation de polarités dans des familles de mots : impact de la morphologie dans la construction d'un lexique pour l'analyse d'opinions[END_REF] et [START_REF] Lafourcade | Propa-L: a semantic filtering service from a lexical network created using Games With A Purpose[END_REF]) ont également été utilisées, mais peuvent ne pas refléter exactement l'opinion des locuteurs. Les approches compositionnelles ou par apprentissage sont généralement celles adoptées pour l'utilisation de ce type de données (voir, par exemple (Kim et Hovy, 2004) et [START_REF] Turney | Thumbs up or thumbs down? Semantic orientation applied to unsupervised classification of reviews[END_REF]).

Un réseau lexical, tel celui obtenu grâce au jeu en ligne JeuxDeMots [START_REF] Lafourcade | Making people play for Lexical Acquisition[END_REF], comporte des termes associés par des relations lexico-sémantiques. Le projet JeuxDeMots (JDM) a permis non seulement la constitution d'un réseau lexical en perpétuelle extension et libre d'accès, mais également la validation/vérification des relations qui le constituent via un certain nombre de jeux et contre-jeux [START_REF] Lafourcade | Jeux et intelligence collective -résolution de problèmes et acquisition de données sur le Web[END_REF]. L'expérimentation de méthodes d'acquisition d'informations de polarité peut être réalisée avec une telle ressource.

Il peut être intéressant d'associer à des termes des informations correspondant à des ensembles fermés de valeurs. Par exemple, la polarité peut être définie sur la base de trois valeurs : positif, négatif et neutre. On remarquera que de nombreuses caractéristiques sémantiques peuvent être associées à de tels ensembles de taille variable : les sentiments/émotions (colère, peur, joie, amour, tristesse, …), ou encore les couleurs (rouge, bleu, jaune, vert, orange, violet, noir, blanc, …). Comme ce type d'association ne peut être obtenu via le jeu principal du réseau JDM, nous avons développé plusieurs jeux permettant de tagger les termes selon des critères (j'aime / je n'aime pas, émotion associée, couleur associée …). Les données collectées ont de nombreuses applications, que ce soit en analyse du discours ou en LAFOURCADE, LE BRUN ET JOUBERT désambiguïsation. Une telle annotation est complexe, car souvent subjective et/ou contextuelle : par exemple, une même remarque adressée à un individu peut être considérée comme un trait d'humour, un conseil, une critique, une réprimande … selon l'énonciateur, l'interlocuteur, et le contexte.

Dans cet article, nous commencerons par présenter les principes de la détermination de cette polarisation via le jeu LikeIt, ainsi que les caractéristiques de sa propagation dans le réseau. Nous indiquerons ensuite les résultats obtenus via une analyse quantitative et qualitative. La méthodologie d'évaluation qualitative, qui se fonde sur un croisement entre données de polarité et données de sentiments (c'est-à-dire sentiments que les joueurs associent spontanément à un terme donné) sera approfondie. Nous conclurons en explicitant quelques-unes des perspectives envisagées.

LikeIt, un jeu de polarité

Dans LikeIt, la polarisation consiste, comme sur les réseaux sociaux, à affecter la mention « J'aime » / « Je n'aime pas » (ou encore « neutre ») à un terme. Bien que cette polarisation soit très subjective, en plus d'être étroitement liée au contexte, notre hypothèse de travail est que de nombreux termes et usages de termes possèdent une polarité intrinsèque, qu'il est possible de capturer globalement, en interrogeant un grand nombre de locuteurs : on vérifie ainsi si une polarité majoritaire se dégage, et si oui, laquelle.

Principe de fonctionnement

LikeIt procède par l'appréciation simplifiée, avec des questions simples posées au joueur, sur le modèle : Est-ce que vous aimez l'idée de suivi d'un terme. Les seules réponses possibles sont oui, non et neutre. Ce jeu enrichit ainsi le réseau lexical avec trois types de polarités, ce qui nous a semblé être la manière à la fois la plus souple et la plus exhaustive pour caractériser les termes. Cela permet notamment de distinguer les termes laissant majoritairement indifférent (majorité de neutre) de ceux qui suscitent des avis très partagés (valeurs à peu près égales pour positif et négatif). L'exploitation préliminaire de ces données seules, dans le cadre d'une désambiguïsation lexicale, semble montrer que la polarité prise isolément permet de sélectionner le bon usage d'un terme en contexte dans approximativement 50% des cas. Ce type de données peut aussi être utilisé en analyse d'opinions, par composition des polarités des termes fortement polarisés (i.e. ceux dont la polarité majoritaire représente plus de 50% des valeurs cumulées des trois possibles). La figure 1 est constituée de deux copies d'écran d'une partie de LikeIt. FIGURE 1. Deux écrans consécutifs de LikeIt. Suite à la réponse donnée dans l'écran de gauche (examen scolaire), le joueur voit immédiatement en haut de l'écran suivant (image de droite et zoom du bas), le pourcentage de joueurs qui partagent son avis : le jeu fournit ainsi un retour direct au joueur avec une relance immédiate (nouvelle question). La mention "…et curieusement vous n'avez répondu cela que 33% des fois" indique au joueur qu'il a déjà été confronté à ce mot et qu'il n'a pas été constant dans son choix.

LikeIt est un jeu de consensus à votes dont certaines propriétés sont développées ci-dessous. Concernant son intérêt ludique et ses qualités en tant que GWAP [START_REF] Lafourcade | Jeux et intelligence collective -résolution de problèmes et acquisition de données sur le Web[END_REF], on relève parmi quelques caractéristiques notables qui en font un jeu addictif :



Mécanisme de sélection des termes

Il serait contre-productif de sélectionner un terme à proposer au joueur de façon totalement équiprobable sur l'ensemble des termes du réseau lexical de JDM. En effet, on peut imaginer qu'une grande proportion de ces termes a une polarité globalement neutre. De plus, le réseau comporte des termes très spécialisés, ce qui est à double-tranchant : intéressant si on connait le terme, mais décourageant sinon, d'où la nécessité de minimiser la fréquence de proposition de ce type de terme. Pour ces raisons, la sélection d'un terme à proposer au joueur est effectuée selon une approche par propagation dans le réseau lexical de JDM. Le principe de l'algorithme est le suivant :

 un terme T ayant une valeur de polarité positive et/ou négative est choisi aléatoirement dans le graphe (nous ignorons délibérément les polarités neutres) ;  on propose T au joueur selon une probabilité p (empiriquement fixée à 0.5), ou un voisin V de T selon une probabilité 1-p. V est choisi de façon équiprobable parmi tous les voisins possibles ;  si le nombre de votes toutes polarités confondues pour V dépasse un seuil s (empiriquement fixé à 1000) alors p vaut 0.9. Nous avons donc une probabilité de 90% de proposer T, et non pas V lui-même.  L'amorçage à été effectué uniquement en polarisant à la main les termes bon (1 vote de polarité positif), et mauvais (1 vote de polarité négatif).

Ainsi, cet algorithme très simple (une pseudo marche aléatoire à un pas) effectue une propagation au sein du graphe entre termes potentiellement intéressants pour l'acquisition de valeurs de polarité, à savoir ceux qui ne sont pas neutres, en évitant partiellement ceux qui sont déjà très renseignés. Un terme neutre ne peut être sélectionné que par le voisinage. Un terme ayant un grand nombre de voisins sera plus rapidement polarisé que les autres, car plus souvent atteint par voisinage (tant que le nombre de votes reste sous le seuil s). Une sélection strictement aléatoire au sein du réseau lexical donnerait une proportion trop importante de termes neutres, ce qui diminuerait l'intérêt du jeu. L'échantillonnage des termes est donc réalisé par cet algorithme de propagation en fonction de la topologie du réseau lexical et des données de polarité déjà disponibles (qui viennent des joueurs). En ce qui concerne la polysémie des LAFOURCADE, LE BRUN ET JOUBERT termes, notons que des mots raffinés, donc des sens différents d'un même terme, peuvent être sélectionnés, ainsi que certains termes en contexte existant déjà dans le réseau, tels que chat [carac] pelé. (films, tableaux, etc.) ont très majoritairement une polarité positive, ainsi que la majeure partie du vocabulaire lié à la gastronomie (et particulièrement les noms de plats, de boissons).

Biais observés

Evaluation qualitative et méthodologie

La question de la méthode à adopter pour une évaluation qualitative se pose dans la mesure où il n'existe aucune ressource relative à la polarité à laquelle les données issues de LikeIt pourraient être confrontées. Il est possible d'entreprendre une évaluation manuelle, qui consisterait à regarder une par une un certain nombre d'entrées et à se prononcer sur la pertinence des polarités. Cette perspective est déraisonnable vu la taille des données (plus de 360 000 termes polarisés) et la question de la constitution de l'échantillonnage reste posée (comment sélectionner les termes à inspecter ?).

Nous disposons, avec la mise à disposition des données de JDM, (via le jeu principal, et un jeu spécifique Emothttp://www.jeuxdemots.org/emot.php), d'associations entre termes et termes désignant des sentiments ou des émotions. Emot est un jeu de choix semi-ouvert (choix fermé et réponses libres en mode avancé) qui demande au joueur d'associer des sentiments ou des émotions à un terme donné. Jouer à JDM sur la relation sentiment est complètement ouvert (réponses libres). Les données obtenues pour un terme prennent la forme d'une liste de termes (sentiments) pondérés, par exemple :  cadeau : joie (+) 1712 ; surprise (+):1142 ; bonheur (+) 980 ; amour (+) 780 ; plaisir (+) 741 ; amitié (+) 660 ; reconnaissance (+) 310 ; déception (-) 260 ; étonnement (+) 222 ; gratitude (+) 210 ; générosité (+) 200 ; satisfaction (+) 160 ; content (+) 140 ; contentement (+) 120; envie (+) 100 ; gêne (-) 90 ; émotion (0) 81 ; émerveillement (+) 80 ; impatience (-) 70 ; jalousie (-) 70 ; heureux (+) 60 ; présent (+) 59 ; fête (+) 56; sympathie (+) 55 ; frustration(-) 50 ; confusion (-) 50 ;

 CRS : sécurité (+) 1027 ; peur (-) 1007 ; violence (-) 817 ; haine (-) 357 ; crainte (-) 297 ; colère (-) 186 ; force (0) 137; protection (+) 127 ; répression (-) 127 ; insécurité (-) 127 ; angoisse (-) 117 ; révolte (-):117; injustice (-) 99 ; brutalité (-) 97 ; panique (-) 97 ; respect (+) 93 ; terreur (-) 87 ; agressivité (-) 87 ; rage (-) 87 ; méfiance (-) 87 ; inquiétude (-) 77 ; douleur (-) 77 ; rejet (-) 77 ; trouille (-):67; aveuglement (-) 66 ; défiance (-) 65 ; honte (-) 63 ; incompréhension (-) 57 ; détresse (-) 57 ; soulagement (+) 57; frayeur (-) 32 ; appréhension (-) 32 ;

 bras : force (0) 110 ; protection (+) 100 ; soutien (+) 80 ; union (+) 5 ; indifférence () 4 ; Dans les exemples ci-dessus nous avons indiqué à la suite de chaque terme sa polarité absolument majoritaire (plus de 50% des votes) au moyen d'un symbole entre parenthèses : (+) pour positif, (-) pour négatif et () pour neutre. Le symbole (0) caractérise un terme qui n'a pas de polarité absolument majoritaire ; c'est le cas du terme force associé à bras par exemple.

Comme les exemples présentés ci-dessus le suggèrent, il est possible de calculer une polarisation pour un terme auquel des termes de sentiments ont été associés. Ceci n'est évidement possible que si les termes associés disposent euxmêmes d'une polarisation. Mais on constatera qu'en pratique, c'est forcément le cas : les termes désignant des sentiments ont été les premiers à être polarisés car ils ont été très rapidement atteints par l'algorithme de propagation. Pour un terme, on calcule donc la polarisation en faisant la somme des vecteurs de polarité de chaque sentiment associé.

La polarisation calculée via les sentiments associés peut ainsi être comparée à celle issue du jeu LikeIt. On compare donc une polarité inférée à une polarité directement établie par les joueurs. Il est possible de comparer les deux polarités via une mesure cosinus, ou une mesure du max (1 si les deux polarités maximum coïncident). L'intérêt de cette approche est qu'elle est directement automatisable, et nous permet de réserver l'effort d'inspection manuelle aux cas divergents. Nous avons considéré les mesures cos et max, en ordonnant les 5 000 premiers termes par poids décroissants pour la relation sentiment (donc ceux qui ont été le plus alimentés en termes de sentiments en premier).

n premiers termes

1 000 2 000 3 000 4 000 5 000

Perspectives et conclusion

Au vu de notre expérience sur les différents jeux présentés ci-dessus, nous pouvons envisager un certain nombre de perspectives, à commencer par la poursuite de cette double approche comme moyen d'accroître encore notre ressource lexicale de polarité (librement accessible à http://www.jeuxdemots.org/likeit.php?action=list). Toutes sortes de caractéristiques (dimension, température, importance/prépondérance, temporalité, localisation …) peuvent être soumises à l'appréciation des joueurs, et donc donner lieu à des jeux de type LikeIt, visant à les quantifier. Mais une étude préliminaire pour identifier les plus utiles, les plus informatives doit impérativement être réalisée, afin d'éviter, en multipliant ce type de jeu, de provoquer une lassitude, donc de la démotivation chez les joueurs. Notons que les données produites via ce type de jeux, qui ne nécessitent aucune autre connaissance qu'une relative maîtrise de la langue, sont de qualité, ce qui légitime ce type d'approche.

On peut se poser la question de l'évolution possible de la polarité d'un terme, en particulier dans le temps : un même terme peut inspirer de manière globale des sentiments différents en fonction du temps, du contexte ; par exemple, le terme volcan suscite plutôt de la curiosité ou de l'indifférence, sauf lorsqu'une éruption imminente menace des populations ou le trafic aérien, l'inquiétude ou la peur prenant alors le dessus, dans la diversité des sentiments exprimés.

  UN JEU POUR CONSTRUIRE UNE RESSOURCE LEXICALE DE POLARITE parties très courtes et relance immédiate, ce qui, sur un plan quantitatif, le rend déjà très efficace pour collecter des données.  diversité du vocabulaire et variabilité de la réponse : certains termes suscitent des sentiments très partagés (par exemple, le terme bloc opératoire est positif dans l'absolu : c'est une structure médicale indispensable, qui sert à soigner, mais qui peut être connotée négativement lorsqu'on est personnellement concerné) et ce faisant, l'avis d'un même joueur peut évoluer dans le temps, et en fonction des circonstances. Ainsi, le terme baccalauréat ou examen scolaire peut susciter un sentiment négatif quand on est lycéen, mais il est toujours perçu positivement lorsqu'on l'a obtenu. Le fait de jouer sur du vocabulaire à très large couverture rend le jeu intéressant et varié.Les réponses issues de LikeIt génèrent pour chaque terme un triplet de nombres de votes pour chacune des trois polarités possibles. De ce triplet, on déduit une répartition en pourcentages que l'on nomme polarisation ainsi que des valeurs d'intensité (le nombre de votes total pour le terme, et la norme de la polarisation, alors vue comme un vecteur à trois composantes). Plus l'intensité, et la norme en particulier, sont élevées, plus la polarisation est fiable. Il est difficile de définir un seuil moyen à partir duquel on pourrait considérer que le nombre de votes est suffisant pour générer des pourcentages de polarité fiables. En effet ce nombre est étroitement lié à la nature et aux caractéristiques de chaque terme (polarité unique forte ou très partagée, terme polysémique, etc.). Toutefois, on peut faire empiriquement une approximation et évaluer le nombre minimal de votes garantissant une répartition fiable des polarités à 10 fois le nombre de polarités (soit au moins 10 votes pour une monopolarité, 20 pour une bipolarité, 30 pour une tripolarité). Un terme sera considéré comme étant fortement orienté si une des polarités est majoritaire (au moins supérieure à 50%). La table 1 présente quelques exemples de résultats où le nombre de votes parait suffisant pour juger fiables les polarisations obtenues.

	la simplicité : les réponses positive/négative/neutre, s'apparentent à celles demandées lors d'un sondage ; cependant, d'après les retours, la diversité du vocabulaire et des sujets qu'il évoque est telle, que les joueurs n'ont pas cadeau retraite CRS automne l'impression de répondre à une enquête d'opinion. Terme Distribution de la polarité en %

De plus, la réponse par simple clic rend possible de jouer depuis un smartphone sur des plages temporelles relativement réduites

(tram, salles d'attente, etc.)

. LikeIt est donc un jeu à LIKEIT, 2.2 Nature des données obtenues POS: 82 NEUT: 14 NEG: 4 POS: 48 NEUT: 18 NEG: 34 POS: 29 NEUT: 15 NEG: 56 POS: 37 NEUT: 44 NEG: 18 Intensité Nb votes : 280 norme : 232.73 Nb votes : 303 norme : 190.6 Nb votes : 274 norme : 177.45 Nb votes : 277 norme : 168.34 TABLE 1. Exemples des polarisations avec LikeIt : le terme cadeau présente une quasi-monopolarité, alors que les trois autres termes sont bi, voire tripolarisés. Le terme cadeau est fortement positif, CRS fortement négatif.

des données de polarité obtenues avec LikeIt 3.1 Evaluation quantitative

  Le jeu LikeIt présente un premier biais : pour un terme polysémique, il est possible que la réponse du joueur subisse une contamination par un sens anecdotique fortement polarisé. Par exemple, vache dont le sens premier, l'animal, est globalement neutre (voire légèrement positif) peut être contaminé par le sens de vache (méchant), qui a une forte polarité négative. Ainsi, les joueurs, se trouvant de facto par le jeu dans un contexte de polarité, vont voter en pensant au sens le plus polarisé, et donc choisir une polarité négative pour le terme vache. Il en est de même pour les termes : fumier (sens premier engrais, contaminant insulte), cellule (sens premier biologie, contaminant prison), etc. Cependant, les raffinements de chacun de ces termes, eux, ne subissent aucune contamination et disposent bien d'une polarité conforme à celle attendue. Certains termes ont une polarité double (positive et négative) car les joueurs peuvent les interpréter façon aussi bien diégétique, c'est-à-dire en s'identifiant au personnage ou à l'action, qu'extradiégétique, c'est-à-dire en adoptant un point de vue extérieur. Ainsi, les termes dragon, orc, sorcière, vampire, etc. sont tout à la fois négatifs (quand on les appréhende au niveau diégétique) et positifs (si on les considère de façon extradiégétique). Cette divergence de perception est un second biais.Lors de l'évaluation quantitative des données obtenues, nous avons constaté un troisième biais qui a tendance à favoriser la polarité positive. Ce troisième biais est explicité à la section suivante. ?...OU PAS ? LIKEIT, UN JEU POUR CONSTRUIRE UNE RESSOURCE LEXICALE DE POLARITE davantage partagé. De même, les entités nommées d'oeuvres

	323 292 polarités positives	(38.3 %)	44 762 101 votes positifs	(57.5 %)
	350 536 polarités neutres	(41.6 %)	21 767 725 votes neutres	(28 %)
	169 768 polarités négatives	(20.1 %)	11 276 692 votes négatifs	(14.5 %)
	Total = 843 596 polarités	(100 %)	Total = 77 806 518 votes	(100 %)
	51 151 polarités < 10 votes		792 445 polarités >= 10 votes
	151 847 polarités < 20 votes		691 749 polarités >= 20 votes
	289 886 polarités < 40 votes		553 710 polarités >= 40 votes
	518 624 polarités < 80 votes		324 972 polarités >= 80 votes
	10 515 termes à polarité positive uniquement	(2.9 %)
	11 193 termes à polarité neutre uniquement	(3 %)
	6 498 termes à polarité négative uniquement	(1.8 %)
	177 221 termes à polarité positive et neutre uniquement	(48.1 %)
	1 150 termes à polarité positive et négative uniquement	(0.3 %)
	27 715 termes à polarité neutre et négative uniquement	(7.5 %)
	134 405 termes ayant les trois polarités		(36.5 %)
	Total = 368 697 termes ayant au moins une polarité	(100 %)
	TABLES 2A, 2B ET 2C. Données quantitatives des polarisations obtenues avec LikeIt.
	Les données, présentées aux tables 2a et 2c, semblent présenter un biais vers la polarité positive qui représente plus de
	la moitié des votes. En effet, en interrogeant les joueurs, on s'aperçoit que beaucoup de termes perçus comme
	relativement neutres (comme par exemple odonate -www.jeuxdemots.org/diko.php?gotermrel=odonate),
	peuvent souvent être néanmoins l'objet d'un vote positif. Il semblerait que le biais soit la conséquence d'un adage qui

3 Evaluation

Durant les trois premiers mois, plus de 25 000 termes on été polarisés (c'est-à-dire dotés d'une information de polarité) pour un total dépassant 150 000 votes. Depuis 2008, plus de 360 000 termes ont été polarisés pour un total supérieur à 75 millions de votes (http://www.jeuxdemots.org/likeit.php?action=list) pour plusieurs centaines de milliers de joueurs (nombre d'adresses IP différentes mesuré en janvier 2013). L'ensemble du réseau JDM contient environ 490 000 termes, c'est-à-dire qu'environ 70% des termes du réseau ont été atteints par l'algorithme de propagation. serait « je peux aimer ce que je ne déteste pas ». Dans quelle mesure ce second biais influence-t-il les résultats ? Il est difficile de l'évaluer car on ne connait pas a priori les termes du lexique qui seraient ou positifs ou neutres.

On peut aussi expliquer partiellement ce biais positif en considérant qu'une majorité des termes proposés soit sont des entités nommées soit relèvent de domaines suscitant l'adhésion : par exemple, l'immense majorité des personnes célèbres ont plutôt une polarité positive (les acteurs et actrices notamment). Pour les hommes politiques, cela peut être VOUS AIMEZ

TABLE 3 .

 3 Evaluation qualitative des données de polarisation issues de LikeIt par comparaison avec celles calculées à partir des associations de sentiments produites par Emot et JDM.LAFOURCADE, LE BRUN ET JOUBERTD'après la table 3, on constate une concordance assez élevée entre la polarité définie par les réponses des joueurs et celle induite par les sentiments associés aux termes. La moyenne des polarités maximales issues des données de LikeIt, mpm, représente le taux d'accord maximum que peut atteindre en moyenne l'opinion générale, pour les n termes les plus joués. Nous constatons une variabilité de 15 à 12% (100 -mpm) entre les 1000 et les 5 000 termes les plus renseignés. La variabilité a tendance à augmenter quand le nombre de votes augmente, ce qui semble logique car il y a plus d'opinions divergentes quand le nombre de votes est élevé.Nous avons examiné manuellement les cas de divergence (valeur de la mesure Max égale à 0). Il s'avère que la quasitotalité des termes pour lesquels il y a peu d'accord sont ceux qui sont diégétiquement contrastés, à savoir ceux qui sont négatifs selon une perspective diégétique et positifs selon une perspective extradiégétique. Quelques termes contrastés :

	Moyenne du Cos	Moyenne du Max	Moyenne des polarités max
	0.80	0.76	85.65 %
	0.83	0.79	86.55 %
	0.80	0.75	87.40 %
	0.82	0.77	87.49 %
	0.83	0.79	87.63 %

classe prépa, thèse, pince-oreille, analyses, murène, micropénis, exprimer [sujet] femme, dragon

  Pour le dire autrement, il semblerait que le processus d'association des sentiments tende à mettre le joueur en situation (configuration diégétique) alors que la demande de polarité (LikeIt) est typiquement extradiégétique (le joueur adopte un point de vue externe). Par exemple, si l'on demande à un joueur d'énumérer les sentiments qu'il associe au terme dieu vengeur, il va avoir tendance à le faire en s'impliquant personnellement dans le contexte que lui suggère le mot, et à répondre peur, crainte, soumission… Inversement si il doit dire, via LikeIt, s'il aime cette expression ou pas, il va répondre oui, car dieu vengeur évoque un récit mythologique, donc quelque chose de plutôt distrayant. C'est ainsi que dieu vengeur a une polarité négative lorsqu'on la calcule via les sentiments associés, et positive lorsqu'elle est issue de LikeIt. On notera que tous les cas de divergence observés portent sur un terme polarisé négativement via les sentiments associés, et positivement via LikeIt. Les termes à polarité forte sont insensibles à l'aspect diégétique. Soulignons également que les termes les plus soumis à la subjectivité du jugement montrent des polarités multiples, mais dont la répartition est concordante quel que soit le mode d'évaluation (polarité directe ou polarité induite).

  Les sentiments à l'égard d'une personne publique, d'une oeuvre (entités nommées) peuvent être très fluctuants dans le temps, et si des sentiments contradictoires apparaissent dans le réseau, il pourrait être intéressant pour les représenter d'y associer une notion de contexte, par exemple Depardieu [contexte] cinéma, et Depardieu [contexte] fiscalité. Dans le cadre d'une extension de LikeIt restant dans l'esprit du crowdsourcing, les joueurs pourraient être sollicités pour fournir un ou plusieurs contextes associés à des polarités contrastées.Certains termes pourraient être polarisables automatiquement, en fonction des relations qui les concernent. Par exemple, la relation caractéristique est très porteuse de polarité, veuve [caractéristique] triste permet de polariser le terme veuve négativement. Cependant, l'approche par crowdsourcing est globalement plus fiable et plus rapide, aussi bien pour les termes à forte polarité que pour les termes complexes. L'approche et les outils présentés dans cet article sont relativement récents, et le nombre de termes polarisés représente une proportion non anecdotique (70%) de l'ensemble du réseau lexical. Compte tenu des résultats obtenus présentés ici, nous estimons avoir montré la faisabilité, l'intérêt, et les perspectives d'un tel projet, et très largement commencé à construire la ressource correspondante.


Using Constraints on a general Knowledge lexiCal networK for domain-speCifiC semantiC relation extraCtion and modeling

Keywords: semantic relation retrieval, semantic modeling, domain specific raw text analysis, lexical-semantic network Ключевые слова: семантический анализ, извлечение неиерархических семантических отношений, семантическое моделирование, анализ неструктурированного текста

We introduce a pattern-based approach applied to the semantic relation retrieval and semantic modeling. Our method relies upon the use of a general knowledge lexical semantic network built, shaped, and handled by crowdsourcing and GWAPs (games with a purpose). Implementing constraints on semantic relations available in the network increases the efficiency of the relation extraction process but also opens a semantic modeling perspective. In terms of (mostly horizontal) relation extraction, we tested our method on radiology reports in French. Our results show the interest of using a general knowledge lexical semantic network for the domain specific textual analysis as well as the interest of implementing series of constraints on semantic relations for the relation retrieval. We recently turned to the analysis of cooking recipes that stand for examples of domain specific instructional texts. Thus, in addition to the semantic relation discovery, we are building a method for the semantic modeling and conceptualization of cooking instructions. Its first results are presented below. Today, our results are available for French but we target extending the lexical network coverage to other languages in the next few years.

ИспользованИе огранИченИй в лексИко-семантИческой сетИ для ИзвлеченИя семантИческИх отношенИй Из спецИалИзИрованных текстов И семантИческого моделИрованИя Клере Н. (clairet@lirmm.fr) 1,2,3 , Рамадье Л. (ramadier@lirmm.fr) 1,4 , Лафуркад М. (mathieu.lafourcade@lirmm.fr) 1 1 Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM), Монпелье, Франция 2

Laboratoire d'Informatique Médicale et d'Ingénieurie des

Connaissances en e-Santé (LIMICS), Париж, Франция 3 Lingua et Machina, Boulogne-Billancourt, Франция 4

IMAIOS, Монпелье, Франция

Мы предлагаем подход к извлечению семантических отношений из неструктурированных текстов и семантическому моделированию основанный на использовании лексико-семантической сети общих знаний и семантических шаблонов. Используемая лексико-семантическая сеть развивается и поддерживается пользователями при помощи целевых онлайн игр и прямого участия (краудсорсинга). Специфика её структуры и применение ограничений (правил) к дугам сети повышают эффективность анализа семантики текста, а также открывают новые перспективы для (полу)автоматического семантического моделирования и концептуализации. Мы протестировали наш метод на материале корпуса рентгенологических заключений на французском языке с целью извлечения неиерархических отношений. Параллельно с исследованием этой проблематики, мы используем нашу методику для разработки модели кулинарного рецепта с целью концептуализации так как данный материал является примером процедурального текста. В настоящее время наши результаты касаются французского языка но мы планируем расширить нашу лексико-семантическую сеть включив в неё другие языки и, вместе с ней, возможности семантического анализатора.

Introduction

In recent years, the semantic analysis of the domain specific texts has been conducted on the basis of specific resources often without using any general knowledge repository. Instead of building a specific resource for our analysis, we immersed the domain specific knowledge into a general knowledge lexical semantic network. Then, we added constraints on the relations present in the lexical semantic network which improved our relation extraction results. Finally, we targeted an instructional text perspective and extend our approach to the modeling the sequences of actions corresponding to the cooking instructions. The paper is structured as follows. First, we give an overview of the state of the art and detail the resource we use for our experiments. Second, we introduce the IMAIOS system for semantic relation extraction and its results. Finally, we propose the MAKI system for the instructional text analysis and semantic modeling.

State of the art

In the literature, the "semantic relation" term corresponds to a variety of definitions. In the lexicographic perspective ex. Wordnet [START_REF] Fellbaum | WordNet: An Electronic Lexical Database[END_REF], semantic relations are above all taxonomy relations (hyperonymy, hyponymy, meronymy). The semantic role approach understands semantic relations as roles handled by the terms in a context as proposed by [START_REF] Dong | HowNet and the Computation of Meaning[END_REF] and described by [START_REF] Morris | Non-classical lexical semantic relations[END_REF]. Lexico-semantic networks such as BabelNet [START_REF] Navigli | BabelNet: The Automatic Construction, Evaluation and Application of a Wide-Coverage Multilingual Semantic Network[END_REF], ConceptNet [START_REF] Liu | ConceptNet-a practical commonsense reasoning toolkit[END_REF], and JeuxDeMots (Lafourcade, 2007) 1 implement this kind of approach.

Most research work concerning the extraction of semantic relations focus on domain-independent relations [START_REF] Snow | Semantic taxonomy induction from heterogenous evidence[END_REF][START_REF] Chklovski | Verbocean : Mining the web for fine-grained semantic verb relations[END_REF]. In the paradigm of information retrieval, open information extraction systems such as (Banko and al., 2009) are also able to retrieve unknown relations. In the biomedical domain, there are four main techniques for relation extraction: finding co-occurrences (Jelier et al., 2005), using patterns or rules [START_REF] Auger | Pattern-based approaches to semantic relation extraction: A state-of-the-art[END_REF][START_REF] Song | PKDE4J: Entity and relation extraction for public knowledge discovery[END_REF][START_REF] Rindflesch | Argument identification for arterial branching predications asserted in cardiac catheterization reports[END_REF], implementing supervised learning-based approaches [START_REF] Song | PKDE4J: Entity and relation extraction for public knowledge discovery[END_REF][START_REF] Rink | Automatic extraction of relations between medical concepts in clinical texts[END_REF], and using hybrid approaches [START_REF] Suchanek | Combining linguistic and statistical analysis to extract relations from web documents[END_REF][START_REF] Chowdhury | Combining tree structures, flat features and patterns for biomedical relation extraction[END_REF]. The relation extraction between verbs (based on their arguments) yielded a number of methods. In particular, those of (Brody, 2007) and [START_REF] Chambers | Unsupervised learning of narrative event chains[END_REF] focus respectively on arguments' role and discourse relations and the real order of actions instead of following the textual order. As a GWAP, JeuxDeMots includes a number of games for lexical acquisition and validation. The main word game involves two players who are asked questions to populate some knowledge type (ex. What is the typical characteristic of cake?) their answers are recorded and compared, the terms that appear in both answers are validated and either they are added into the network or their weight is augmented. More details are available in [START_REF] Lafourcade | Making people play for Lexical Acquisition with the JeuxDeMots prototype[END_REF].

The approaches to the semantic analysis of the cooking recipes fall into two major trends. The first one is centered on the concept of aliment, its possible features and adaptation perspectives. The IBM Chef Watson system implements this kind of approach. The second trend is related to the case-based reasoning paradigm. It uses cooking recipes as examples of instructional texts with the scope of analyzing and modeling work-flows. The Taaable [START_REF] Badra | TAAABLE : Text Mining, ontology Engineering, and Hierarchical Claasification for Textual Case-Based Cooking[END_REF] project is being developed in this perspective. Cooking instructions can be considered as short texts such as defined by (Pedersen, 2008 2 ). Their analysis can also be conducted in the mapping instructions to actions perspective. In this paradigm the instructional text can be represented in formal language (Chen and Mooney, 2011), approahced from the machine learning linear policy estimation (Vogel and Jurafsky, 2010) in particular semantic role labeling [START_REF] Malmaud | Cooking with Semantics[END_REF] or alignment-based compositional semantics (Andreas and Klein, 2014) perspectives. In the knowledge engineering domain, a number of dedicated resources and models have been developed for food and nutrition: BBC Food Ontology3 , PIPS Food ontology 4 , SOUR CREAM (Tasse and Smith, 2008) etc.

Crowd-sourced lexical semantic network

The lexical semantic network JeuxDeMots [START_REF] Lafourcade | Making people play for Lexical Acquisition with the JeuxDeMots prototype[END_REF]) is an oriented, typed, weighted graph that contains 40M arcs (relations) linking 800K nodes. Unlike some of the similar resources (such as Wiktionnary), the JeuxdeMots graph features more than 100 relation types and includes various kinds of lexical, morphological, and semantic information. Therefore, it is relevant for the mining of horizontal relations such as location, part-of, synonym, causal and temporal relations, characteristic, manner, and more. The JeuxDeMots graph also implements inference and annotation schemes. The inference scheme [START_REF] Zarrouk | Consolidation endogène de réseaux lexico-sémantiques : inférence et annotation des relations, règles d'inférence et langage dédié[END_REF] for the graph semantic relations spreading introduces deductive, inductive, abductive and refinement approaches. The deduction and the induction mechanisms test the assumption of the transitivity of the is-a relation and use the logical blocking in case of polysemy. The blocking scheme is based upon the refinement concept and the annotation process applied to the premisses (typed and weighted outgoing relations inferred on the basis of hyperonyms/hyponyms of a term). Its final stage is the validation processed by a human expert. The refinement corresponds to the "real life" use of a term and may stand quite far from its lexicographic representation. This feature of our resource helps untangling some knotty problems such as the multi-word term detection and the polysemy management while analyzing raw text. The abduction scheme uses 2 "A short written context consists of one to approximately 200 words of text that is presented to a human reader as a coherent source of information from which a conclusion can be drawn or an action taken" [START_REF] Pedersen | Computational Approaches to Measuring the Similarity of Short Contexts : A Review of Applications and Methods[END_REF]. synonym and similarity relations in order to infer new relations in the graph. To benefit from the inference scheme, a term is supposed to have at least one hyperonym, hyponym, synonym or refinement. The annotation scheme [START_REF] Ramadier | Annotations et inférences de relations dans un réseau lexico-sémantique :application à la radiologie[END_REF] allows defining and spreading the annotations over the relations already existing in the graph. It amplifies the inference scheme described above without adding new relation types into the graph.

The features of our resource grant the use of robust and somehow crude mining algorithms. The identification of compound terms can be made upstream by comparing the entities found in the text to the JeuxDeMots network. We use underscore to aggregate the two parts of a compound word. Thus, it is considered as an entity by the extractor (tibia_fracture). The polysemy resolution is based on the refinement. In the graph, all the refinements are linked to the core term. The disambiguation process is based on a triangular scheme including the term to disambiguate, its context and its refinements. The context is compared to the term refinements found in the graph. If a refinement do have some relation with the context (has at least one ingoing or outgoing relation to/from the context terms and these relation(s) has a weight w > 50) it is retained as it expresses the sense close to the context. The weight of a relation corresponds to the force of association between two words: how many crowdsourcers figured out the second term while considering the first one.

Extracting semantic relations from domain specific unstructured text: the IMAIOS system

The relation extraction approach implements series of semantic patterns. We understand semantic patterns as linguistic patterns similar to [START_REF] Embarek | Learning Patterns for Building Resources about Semantic Relations in the Medical Domain[END_REF] coupled with series of constraints on the relations of the JeuxDeMots graph. In the scope of the radiology report analysis and indexation and after being advised by radiologists, we have chosen 15 semantic relations relevant within this domain. These are in particular r_isa (generic terms), r_synonym (synonyms or quasi synonyms), r_carac (typical characteristics), r_location (typical location), r_target (disease target such as social group, organ), r_part_of (typical parts), r_cause (typical causes) etc. These relations can be of any general purpose. Some authors have already noticed that the use of patterns is an effective method for automatic information extraction from corpora if they are efficiently designed [START_REF] Embarek | Learning Patterns for Building Resources about Semantic Relations in the Medical Domain[END_REF][START_REF] Cimino | Automatic knowledge acquisition from MEDLINE[END_REF]. For each relation type, we build patterns and match them with the sentences to identify the correct relation. These patterns are (for now) manually built through partial analysis of our corpus. In our experiment, we restricted ourselves to 42 semantic patterns, 12 of which are specific to medicine. For some of the relations listed above, we encountered difficulties related to the ambiguity issue. For the location relation, we can distinguish two kinds of possible semantic relations depending on the pattern. The first pattern refers to the r_location relation (hepatocellular carcinoma is at the level of the liver). The second relation is holonomy (femur r_holo lower limb). For some connectors (of in caudate lobe of liver) both relations are correct (caudate lobe r_location liver and caudate lobe r_holo liver). We also make use of immediate co-occurences of entities for characteristic relation. For instance mutifocal hepatocellular carcinoma (HCC) appears five times together, so we consider multifocal as a probable characteristic of HCC (HCC r_characteristic multifocal). Some linguistic patterns are inexpressive and it is hardly possible to determine the kind of the associated relation (ex. the french connector de, "of, from, because of"). Thus, we have added some semantic constraints on linguistic patterns. A semantic constraint is a condition that should verify the reification of one of variable of the pattern. There may be any number of constraints on $x and $y. Basically, a semantic constraint is a rule defined as follows: "if x is related to B than x is related to C" or x, Rb(x, B) =>Rc(x,C).

table 2. Semantic pattern structure

Semantic pattern structure Example

Lexical pattern (linguistic scheme) "$x de $y"

Premisses (conditions or semantic rules) If $x r_isa illness & $y r_isa anatomical_location => Conclusion (action) $x r_location $y

To apply the semantic constraints' principle over our corpus and extract semantic relations, we use the following algorithm: Let S the result set, being the empty set at initialization Finding pattern occurrence in the text by moving a word window of size n

For each pattern occurrence applying constraints to the instantiated variables If cons trains are verified then the associated semantic relation is associated to $x and $y, that is to say added to S Return S From a corpus of more 30,000 medical reports, we extracted a random subset of around 120,000 relation instances for the different relation types 5 . About 800 of these relations were manually checked for evaluating precision. For assessing recall, we manually identified the relations in about 300 medical reports. Then we applied our algorithm. The IMAIOS system has also been applied to other corpora. For a corpus of 45,000 cooking recipes, 245,000 semantic relations have been extracted with a precision of 95% (manually evaluated on a sample of 755 relations). Furthermore, we extracted 789,000 relations for randomly Wikipedia pages with a precision of 92% (manually evaluated on a sample of 1,250 relations). Hyperonym extraction on Wikipedia articles has a precision of about 94%. Even though we target some of the relation types according to our objectives, our system can extract any of the relation types present in the JeuxDeMots network on the basis of appropriate semantic patterns: taxonomic (isa, hypo, has-part), predicative (agent, patient), horizontal (location, place, action place, instrument, manner, cause, consequence, qualia structure [START_REF] Pustejovsky | The Generative Lexicon[END_REF] inspired relations (telic role, agentive role), and more.

table 3. The IMAIOS system: relation extraction results

Relations

Precision w/o constraints

Precision with constraints Recall

F-measure w/o constraints

F-measure with constraints

Contribu

Instructional text analysis, semantic relation extraction, and modeling

The MAKI System focuses on the analysis of cooking recipes taken as examples of instructional text, the extraction of temporal relations, and the modeling of the sequences of actions. Its ultimate goal is to build a conceptualizing work-flow to discover the canonical recipe on the basis of its variants found in the texts of recipes. It extends the use of semantic patterns by introducing the rules with not only two but more variables.

∀X n ∀x, patient(X n , x) ˄ is-a (x, aliment) ∃y, pos (y, Nom) ˄ carac(y, z) ˄ pos(z, Ver:PP) => consequence(X n ,y) ˄ successeur_temps(X n , y) cf. "for each transforming action of the instructional text there is a state such as the consequence and the temporal successor of this action".

The graph corresponding to the representation of the cooking instructions as sequences of actions is a bipartite graph with two types of nodes: states and actions. Our analysis strategy prompts that of (Bonfante et al., 2010) and also that of [START_REF] Poria | Dependency-Based Semantic Parsing for Concept-Level Text Analysis[END_REF]. We move from a syntactic dependency surface representation that can be obtained by using a parser such as Bonsaï PCFG-LA parser and MElt (Denis et Sagot, 2009), or by using the JeuxDeMots graph which contains such information. For each segment of the text we build an oriented, typed acyclic graph such as ⌊G⌋ |=∀x∃(y, z. (edg (x, y, r') ∧ edg (x, z, r'')).

From the linguistic point of view, the MAKI system focuses on the following phenomena (among other): predominance of predicative structures; monotony of the argumental field (from one textual segment to another, we rediscover the same arguments such as patient, instrument, place, quantifier etc.); adjectival value of the past participle forms visible when observing the characteristic semantic feature (ex. légumes blanchis, "blanched vegetables"). These observations corroborate the assumption that any recipe action is spatially situated (utensil, table, kitchen), transforming (each action is followed by some new state of ingredients (patients)), and temporary finite.

In terms of computation, we introduce the dynamic creation of entities (nodes and directed arcs). The general analysis process starts from a surface representation built using the syntactic relation typed as succ (successor). Then, a context free grammar introduces constraints on the JeuxDeMots relations. As the rules (semantic constraints) keep on being applied, the JeuxDeMots graph is browsed and the semantic relations between these nodes keep on being discovered. The reification mechanism defined by [START_REF] Zarrouk | Consolidation endogène de réseaux lexico-sémantiques : inférence et annotation des relations, règles d'inférence et langage dédié[END_REF] is implemented. In this scheme, the graphs of the variables are dynamically built, the nodes typed as "rules" are created and linked to the reifications of a corresponding relation. We extend this scheme as we allow the creation of nodes to type the graphs of variables which facilitates their comparison. The variable graphs are linked to generic alignment entities using the relation type r_head. The lexical shape of these generic entities is that of the domain key terms (and not conceptual entities specifically created for the analysis) present in the JeuxDeMots lexical semantic network. Thus, each generic alignment entity has a syntactic and semantic behavior and we can benefit from the power of our resource and its range of relation types. Main entities of this kind are: action, état (state), préparation, ingrédient. Moreover, we use such elements as grammatical features (parts of speech, gender, number etc.), word order, antecedence and reference markers in the text.

For the modeling of sequences of actions, we consider the instructional graphs built during our recipe analysis. We assume that actions pertaining to the same sequence share a certain number of resources (arguments) such as patient (ingredient), instrument, place (utensils, recipients). Therefore, graphs that do not have any of such resources in common and do not have any similar nodes (synonyms or quasisynonyms otherwise linked by the relations typed as part-of, substance, place of action, location) are not part of a same sequence hyper-graph. We also noticed that the shortest path to the resources or groups of resources in the graph could be an indicator of the order of actions in a sequence.

To test our modeling system, we applied our scheme to 1,500 cooking instructions selected according to their predicative structure (at least one predicate and one patient), grammatical correctness, and length (4 to 12 tokens). For the evaluation purposes, we manually extracted semantic relations from our corpus (we obtained 3,878 relations) and built the generic alignment entities (1,720 entities). Then, we compared our semantic parser's results to this reference. The actions behind the textual instructions have been modeled exactly in 57% of cases (855 graphs have been built with all the expected nodes and all the appropriate semantic relations). 28% of instructions have been partly modeled (which corresponds to 435 instructions modeled). Finally, in 14% of cases our system failed in building alignment hyper-graphs which is due to the need of improving the coverage of the Jeux DeMots graph (new relation types). The semantic relations we extracted and the entities we built according to the rules show the following results:

Conclusion

While the machine learning techniques are dominant in the research field of computational linguistics within the text analysis, the graph based approach with crafted knowledge remains a very promising area for fine semantic analysis of raw text as well as for the terminological and relation retrieval. Indeed, a common knowledge graph gives access to the extra-linguistic information which is not part of the text as a percept and which rarely appears in texts. Thus, this type of resource is relevant for the domain specific texts' analysis.

1

 1

5

 5

table 1 .

 1 Semantic pattern examples

		Examples of patterns	Exemples of patterns
	Relations	in English	in French
	location	E1 on the level of E2	E1 au niveau de E2
	location	E1 in E2	E1 dans E2
	location	E1 is in the E2	E1 se trouve dans E2
	location	E1 passing by E2	E1 passant par E2
	causes	E1 may trigger E2	E1 déclenchant E2
	characteristic	E1 is characterized by E2	E1 est caractérisé par E2
	characteristic	Noun Adj	Nom + Adjectif
	synonym	E1 also called E2	E1 encore appelé
	causes	E1 can produce E2	E1 peut produire E2
	consequence	E1 causes E2	E1 provoque E2
	hyperonym	E1 is a E2	E1 est un E2
	consequence	E1 leading to a E2	E1 menant à E2
	target	E1 touching E2	E1 touchant E2
	treatament	E1 treated by E2	E1 traité par E2
	clinical sign	E1 accompanied by E2	E1 accompagné par E2

table 4 .

 4 The MAKI system: relation extraction and semantic modeling first results

		Refer-	Extrac-	Re-	Preci-
	Relation type	ence	tion	call	sion	F-score Modeling
	patient	1,500	1,700	1	88%	94% action	966
	characteristic	505	570 94%	86%	90% state	70
	manner	378	288 50%	98%	66% event	15
	successor_time	420	67 78%	1	87% set_of_ingredients	210
	has-part	168	145 73%	1	84% mixture ::	63
	quantifier	84	77 83%	1	91%
	place	462	444 69%	88%	77%
	place of action	336	329 61%	82%	70%
	instrument	25	21 68%	1	81%
	agent (not expected)	-	205	-	-	-
	agent-1 (not expected)	-	200	-	-	-
	Totals	3,878	4,152	-	-	-Total	1,324
	average	-	-75% 93%	82% Modeling
						accuracy

http://www.bbc.co.uk/ontologies/fo/1.1

http://cordis.europa.eu/project/rcn/71245en.html