Linqing Gui
email: guilinqing@gmail.com

Xinyu Huang

Member, IEEE Fu Xiao
email: xiaof@njupt.edu.cn

Member, IEEE Yijin Zhang
email: yijin.zhang@gmail.com

Feng Shu
email: shufeng@njust.edu.cn

Jun Wei

Thierry Val
email: val@irit.fr

Fu Xiao Gui

DV-Hop Localization With Protocol Sequence Based Access

Keywords: Localization, range-free, distance vector hop (DV-Hop), protocol sequence

Among typical range-free localization schemes for sensor networks, DV-Hop has its distinguishing advantage of the capability to localize unknown nodes, which have less than three or even no neighbor anchors. However, existing DV-Hop based localization methods have not considered the problem of packet collisions, which can frequently happen during the throughoutwhole-network broadcast of numerous data packets at the first two steps of DV-Hop. In order to effectively improve the success rate of packet transmission between nodes, this paper proposes a medium access control (MAC) method based on Chinese Remainder Theorem (CRT) protocol sequence for DV-Hop localization. First, a broadcasting strategy is designed for the proposed MAC method. Then, dedicated procedures for both anchor nodes and unknown nodes are presented to implement the designed MAC method in DV-Hop localization. Through simulation and evaluation, the performance of DV-Hop localization with the proposed MAC method is thoroughly investigated. Simulation results show that when the number of protocol sequences is larger than a certain number, the proposed MAC method can provide DV-Hop with bet-ter localization accuracy than E-CSMA/CA, while keeping similar localization time.

I. INTRODUCTION

I NTERNET of things (IOT) has been widely deployed in a variety of critical applications, including event detection, disaster relief, home care, object tracking and environment monitoring [START_REF] Zhu | R-TTWD: Robust devicefree through-the-wall detection of moving human with wifi[END_REF]. An IOT consists of tiny, inexpensive, and lowpowered sensor nodes which can dynamically form a network. The limited transmission power of each sensor node restricts its communication range, thus multi-hop transmission is usually required to gather data from remote sensors [START_REF] Zaidi | Accurate range-free localization in multi-hop wireless sensor networks[END_REF]. The received data are often fully or partially meaningless if the location from where they have been measured is unknown, making the localization of sensor nodes an essential task in multi-hop networks [START_REF] Xiao | Noise tolerant localization for sensor networks[END_REF]. Localization is also needed to design new energy-efficient location-based techniques for multi-hop routing, data fusion and automatic calibration in large-scale sensor networks [START_REF] Xiao | One more tag enables fine-grained RFID localization and tracking[END_REF].

A variety of node localization schemes have been proposed for IOT. These schemes can be categorized as either rangebased or range-free [START_REF] Ou | Path planning algorithm for mobile anchor-based localization in wireless sensor networks[END_REF]. Range-based schemes first utilize Received Signal Strength Indicator (RSSI) [START_REF] Xiao | Noise-tolerant wireless sensor networks localization via multinorms regularized matrix completion[END_REF], Time of Arrival (TOA) [START_REF] Despaux | Accurate and platform-agnostic time-of-flight estimation in ultra-wide band[END_REF], Time Difference of Arrival (TDOA) [START_REF] Tiemann | Scalable and precise multi-UAV indoor navigation using TDOA-based UWB localization[END_REF], or Angle of Arrival (AOA) [START_REF] Shu | Low-complexity and high-resolution DOA estimation for hybrid analog and digital massive mimo receive array[END_REF] to measure the distance or angle from a target node to each anchor node, and then apply trilateration, triangulation or maximum likelihood to determine the position of the target node [START_REF] Gui | A cramer-rao lower bound of CSI-based indoor localization[END_REF]. Here anchor nodes are those who are aware of their positions. Range-based schemes are supposed to provide accurate localization results, but they have two major drawbacks. First, the ranging information is easily affected by multipath fading, noise and environment variations. Second, special transceivers are always required to precisely measure TOA or AOA, which consumes more energy and increase the overall cost [START_REF] Gui | Improvement of range-free localization technology by a novel DV-hop protocol in wireless sensor networks[END_REF]. In contrast, range-free schemes don't possess aforementioned drawbacks because they utilize connectivity information between nodes, while normally having lower localization accuracy than range-based schemes. Thus rangefree schemes are preferable for wireless networks which value the cost more than localization accuracy. The cost-effective advantage of range-free schemes makes them attractive for many IOT applications such as the localization of aged people in a large retirement home or clients in a large shopping mall, where localization accuracy of several meters can be accepted especially considering their privacy. Thus in this paper we focus on range-free localization for low-cost sensor networks.

Many range-free schemes have been proposed these years, for example, Centroid [START_REF] Patro | Localization in wireless sensor network with mobile beacons[END_REF], Regulated signature distance (RSD) [START_REF] Zhong | RSD: A metric for achieving range-free localization beyond connectivity[END_REF], Concentric Anchor Beacon (CAB) [START_REF] Vivekanandan | Concentric anchor beacon localization algorithm for wireless sensor networks[END_REF], Hitball [START_REF] Huang | A historical-beacon-aided localization algorithm for mobile sensor networks[END_REF], Multidimensional scaling MAP (MDS-MAP) [START_REF] Shang | Improved MDS-based localization[END_REF], Distance Vector Hop (DV-Hop) [START_REF] Niculescu | DV based positioning in ad hoc networks[END_REF] and other DV-Hop based algorithms [START_REF] Gui | Improvement of range-free localization technology by a novel DV-hop protocol in wireless sensor networks[END_REF], [START_REF] Kumar | An advanced DV-Hop localization algorithm for wireless sensor networks[END_REF]- [START_REF] Sharma | Improved DV-hop localization algorithm using teaching learning based optimization for wireless sensor networks[END_REF]. The former four range-free algorithms have a common feature, i.e., they all require each unknown node should have at least 3 neighbor anchor nodes. However, in this paper, we mainly consider IOT application scenarios with low density anchors distributed sparsely. For example, in a network with total 100 nodes, only 10 are anchors and they are deployed sparsely. Since the ratio of anchors to all nodes is low, many unknown nodes have less than three anchors in their neighborhood, while some unknown nodes even have no neighbor anchors. In this case, the former four localization algorithms cannot work properly because they have restricted requirement on the minimum number of neighbor anchors. Alternatively, flexible and dynamic localization algorithms such as MDS-MAP and DV-Hop are recommended. Since MDS-MAP is known as a centralized algorithm due to its relatively high computation complexity, DV-Hop is preferable for Ad Hoc sensor networks.

The basic principle of original DV-Hop algorithm is that each node first obtains the positions of anchors as well as hop counts to anchors through the flood of information, then each anchor calculates its distance-per-hop and floods this value, finally each unknown node calculates its distance to each anchor and estimates its position. Since the localization accuracy of the original DV-Hop is not satisfying, many algorithms have been proposed to improve the accuracy, for example, Advanced DV-Hop [START_REF] Kumar | An advanced DV-Hop localization algorithm for wireless sensor networks[END_REF], Selective 3-Anchor DV-Hop [START_REF] Gui | Improving localization accuracy using selective 3-anchor DV-Hop algorithm[END_REF], Reference Anchor Selectionbased DV-Hop (RAS DV-Hop) [START_REF] Sharma | Improved DV-hop localization algorithm using teaching learning based optimization for wireless sensor networks[END_REF] and DV-maxHop [START_REF] Shahzad | DV-maxHop: A fast and accurate range-free localization algorithm for anisotropic wireless networks[END_REF]. However, these DV-Hop based algorithms have not considered the problem of packet collisions, which can frequently happen during the throughout-network broadcast of position packets and distance-per-hop packets at the first two steps of DV-Hop.

In order to reduce packet collisions during information exchange between nodes, medium access control (MAC) methods are required. There exist some widely-used methods such as Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) and Time Division Multiple Access (TDMA). However, CSMA/CA cannot function well for DV-Hop because it requires the feedback of acknowledgment (ACK) signals to ensure successful receptions. But ACK signals are not necessary for DV-Hop for the following reason. A node normally has no prior knowledge of all neighbor nodes. Then since all the communication in DV-Hop is broadcast, when a node broadcasts a packet, it doesn't know exactly who should receive the packet. Even if the transmitter got some ACK signals from neighbor nodes, it was still not sure whether all neighbors had successfully received the packet. On the other hand, TDMA as a deterministic method can effectively minimize the collisions. However, TDMA has rigid requirements on the system design [START_REF] Sami | A survey and taxonomy on medium access control strategies for cooperative communication in wireless networks: Research issues and challenges[END_REF], especially the synchronization, including both frame synchronization and slot synchronization. The rigid synchronization increases overall costs of the network, making most TDMA-based methods [START_REF] Alvi | Best-MAC: Bitmap-assisted efficient and scalable TDMAbased WSN MAC protocol for smart cities[END_REF], [START_REF] Jiang | PTMAC : A prediction-based TDMA MAC protocol for reducing packet collisions in vanet[END_REF] not suitable for low-cost and large-scale IOT. Alternatively, in this paper, protocol sequences are recommended, because they have less rigid synchronization requirement than TDMA but provide good and cost-effective performance for DV-Hop.

Protocol sequences are originally proposed to achieve zeroerror capacity of a collision channel without feedback [START_REF] Zhang | Protocol sequences for the multiple-packet reception channel without feedback[END_REF], [START_REF] Shaar | Collision resolution in contention access local area networks using concatenated prime sequences[END_REF]. Several types of protocol sequences have been constructed over these years, such as wobbling sequences [START_REF] Wong | New protocol sequences for random-access channels without feedback[END_REF], shift-invariant sequences [START_REF] Chen | Constructions of robust protocol sequences for wireless sensor and ad hoc networks[END_REF], [START_REF] Shum | Shift-invariant protocol sequences for the collision channel without feedback[END_REF] and Chinese Remainder Theorem (CRT) sequences [START_REF] Shum | Construction and applications of CRT sequences[END_REF], [START_REF] Zhang | Binary sequences for multiple access collision channel: Identification and synchronization[END_REF]. The type of protocol sequences considered in this paper for DV-Hop localization is CRT sequences. Compared to other types of protocol sequences, CRT sequences are able to provide an excellent tradeoff between the worstcase throughput and sequence period [START_REF] Zhang | An energy-aware reliable deterministic broadcast protocol for wireless sensor networks[END_REF], [START_REF] Zhang | A hybrid wavelength reservation scheme for large-scale optical networks[END_REF]. This feature is preferable for DV-Hop localization in which both localization accuracy and delay should meet predefined Quality-of-Service (QoS) requirement.

To the best of our knowledge, this is the first paper discussing protocol sequence based MAC method which can solve the problem about unsuccessful receptions caused by packet collisions in DV-Hop localization. Our proposed method can bring much more successful receptions at the first two steps of DV-Hop, thus effectively improve the localization accuracy. The main contributions of this paper are as follows.

(1) We design a broadcasting strategy for protocol sequence based medium access method. The designed strategy makes protocol sequence applicable to DV-Hop localization. In DV-Hop the nodes not only relay broadcast frames but also have to simultaneously receive frames. Our proposed broadcasting strategy can make the best use of each slot in protocol sequence to fulfill continuous and concurrent transmisstion/reception at half-duplex nodes. Therefore, based on our designed broadcasting strategy, protocol sequence based MAC method can well fit DV-Hop localization.

(2) We implement the proposed CRT sequence based medium access method at the first two steps of DV-Hop localization. Our proposed method can greatly increase successful receptions during the broadcast in DV-Hop, resulting in higher localization accuracy. Since anchors and unknown nodes follow different procedures in DV-Hop, the implementation of our protocol sequence based MAC method has also been devised separately for anchors and unknown nodes.

(3) We have thoroughly investigated the performance of DV-Hop localization with our proposed CRT sequence based MAC method. Our method is compared to Enhanced-CSMA/CA [START_REF] Gui | Improvement of range-free localization technology by a novel DV-hop protocol in wireless sensor networks[END_REF] as well as other protocol sequences such as prime sequences [START_REF] Shaar | Collision resolution in contention access local area networks using concatenated prime sequences[END_REF]. These methods have been evaluated in terms of localization accuracy and localization time. Simulation results show that with adequate protocol sequences, DV-Hop localization using our method can achieve much better accuracy than other methods, while keeping similar localization time.

The rest of this paper is organized as follows. Section II gives a survey of related works. Section III presents the construction of CRT sequences. Then in Section IV our proposed medium access method for DV-Hop localization is illustrated. Section V introduces simulation scenario and parameters as well as the results and analysis. Conclusions and prospectives are provided in Section VI.

II. RELATED WORK

This section first provides an overview of original DV-Hop localization algorithm as well as some typical DV-Hop based algorithms, for example, Advanced DV-Hop, Selective 3-Anchor DV-Hop, RAS DV-Hop and DV-maxHop. Then, in order to solve the problem of packet collisions in DV-Hop localization, candidate medium access methods are introduced including CSMA/CA, Enhanced-CSMA/CA (E-CSMA/CA), TDMA and protocol sequences. The original DV-Hop algorithm consists of three steps [START_REF] Niculescu | DV based positioning in ad hoc networks[END_REF]. At the first step, each anchor A i (shown in Fig. 1) broadcasts a message containing its location and a hop count (0). This hope count will increase during the throughout-network broadcast of the message. The fist time receiving the message, every node records A i 's position, increases the hop count by 1, assigns the increased value to hop i (its minimum hop count to A i ) and broadcasts the message. The node will maintain hop i when it receives the message again. Only when the hop count in the message is lower than hop i , the node updates hop i and broadcasts the message. Through the first step, every node can obtain its minimum hop counts to all anchors.

At the second step, each anchor calculates and broadcast its average distance-per-hop, which is computed as the sum of distances to other anchors divided by the sum of smallest hop counts to other anchors [START_REF] Niculescu | DV based positioning in ad hoc networks[END_REF]. The first time receiving an anchor's distance-per-hop, every node will record it and help to broadcast it. Through the second step, every unknown node can obtain average distance-per-hop of all anchors.

At the third step, using the hop counts and distance-per-hop values received at previous two steps, each unknown node L x can estimate its distances to all anchors. Then with the positions of all anchors, L x can finally calculate its geometrical position through trilateration or multi-lateration.

Although the original DV-Hop algorithm can localize those unknown nodes with less than 3 neighbor anchors, its accuracy is quite low. Many DV-Hop based algorithms [START_REF] Kumar | An advanced DV-Hop localization algorithm for wireless sensor networks[END_REF]- [START_REF] Shahzad | DV-maxHop: A fast and accurate range-free localization algorithm for anisotropic wireless networks[END_REF] have been proposed over these years to improve localization accuracy. However, these algorithms neglected the problems at MAC layer, e.g., packet collisions during the throughoutnetwork broadcast of position/distance-per-hop packets at the first two steps of DV-Hop. In order to reduce packet collisions and improve transmission success rate in DV-Hop localization, medium access methods are required.

CSMA/CA and TDMA are two widely-used methods for accessing the medium. As a random method, although CSMA/CA has been adopted by WiFi and ZigBee, it cannot effectively reduce packet collisions for DV-Hop localization because of two reasons. First, the traffic by throughout-network broadcast in DV-Hop is too heavy. Second, ACK signals are not available. Thus the traditional CSMA/CA is unable to ensure successful data reception in DV-Hop. Then Enhanced-CSMA/CA (E-CSMA/CA) was proposed in [START_REF] Gui | Improvement of range-free localization technology by a novel DV-hop protocol in wireless sensor networks[END_REF] to reduce collisions by lowering the chance of simultaneous transmissions, but at the cost of additional transmission delay. However, there still exist many collisions especially in large-scale networks. On the other hand, aiming to provide collision-free transmission, TDMA is a well-known schedule-based MAC technique [START_REF] Sami | A survey and taxonomy on medium access control strategies for cooperative communication in wireless networks: Research issues and challenges[END_REF]. Although TDMA saves energy loss by avoiding collision, it still has several issues such as rigid requirement on time synchronization, slot wastage in sparse networks [START_REF] Sami | A survey and taxonomy on medium access control strategies for cooperative communication in wireless networks: Research issues and challenges[END_REF] and poor flexibility to handle adaptive data traffic (especially for static TDMA methods).

In ad-hoc sensor networks, well-coordinated transmission and time synchronization may be difficult to achieve because of energy constraints, time-varying channel conditions and user mobility. Thus a simple medium access method is desirable, which requires neither rigid time synchronization nor frequent channel sensing. Protocol sequences, as deterministic coding sequences for accessing a collision channel without feedback, can be a good choice [START_REF] Zhang | Protocol sequences for the multiple-packet reception channel without feedback[END_REF]. Using protocol sequence based medium access method, it is not necessary for the transmitters to synchronize with each other. Thus unlike TDMA, rigid time synchronization is not required. Whereas compared with CSMA/CA, protocol sequences don't require channel monitoring, back off algorithm or packet retransmission.

In order to obtain a good trade-off between the worst-case throughput and sequence period, Chinese Remainder Theorem (CRT) protocol sequences were proposed in [START_REF] Shum | Construction and applications of CRT sequences[END_REF]. Recent applications of CRT sequences can be found in [START_REF] Zhang | Binary sequences for multiple access collision channel: Identification and synchronization[END_REF]- [START_REF] Zhang | A hybrid wavelength reservation scheme for large-scale optical networks[END_REF]. CRT sequences are binary sequences whose pairwise Hamming crosscorrelation is highly concentrated around the mean. With the special Hamming cross-correlation property, CRT sequences can provide a hard guarantee on the worst-case system throughput, which is lower bounded by a positive constant no matter what the delay offsets are [START_REF] Shum | Construction and applications of CRT sequences[END_REF]. CRT sequences have several remarkable advantages. First, CRT sequences possess shorter period than existing protocol sequences with the same throughput performance [START_REF] Shum | Construction of short protocol sequences with worst-case throughput guarantee[END_REF]. Second, the generation of CRT sequences involves only simple modular arithmetic, thus a low-complexity solution can be provided for medium access control in IOT [START_REF] Shum | Construction and applications of CRT sequences[END_REF]. Third, CRT sequences have two capabilities, i.e., user identification and frame-synchronization capability. Due to the aforementioned advantages, CRT sequence-based MAC method can be a good choice for DV-Hop localization.

III. CONSTRUCTION OF CRT PROTOCOL SEQUENCES

As for binary sequences, the characteristic set is defined as the set of locations of the ones in a period of a sequence. So a sequence can be represented in a compact way by specifying the characteristic set of the sequence. Given a sequence a(k) of length L, let I a be the characteristic set of a(k). Then the number k ∈ I a if and only if a(k) = 1. Let Z n be the ring of residues mod n for a positive integer n. If the length of a sequence is L, Z L represents the time indices 0, 1, 2, ..., L -1. Then I a , the characteristic set of a(k), is the subset of Z L .

We construct sequences with length L = pq, where p and q are relatively prime integers. In the following discussions, p is a prime number and q is an integer not divisible by p. Based on Chinese remainder theorem [START_REF] Shum | Construction of short protocol sequences with worst-case throughput guarantee[END_REF], the mapping f : Z pq → Z p ⊕ Z q defined by f (x) := (x mod p, x mod q) is a bijection from Z pq to Z p ⊕ Z q . Since I a is the subset of Z pq , the characteristic set can be mapped to a subset of Z p ⊕ Z q , which consists of ordered pairs in the form (w, v) with 0 ≤ w < p and 0 ≤ v < q. We will construct sequences by specifying characteristic sets in Z p ⊕ Z q .

CRT construction [START_REF] Shum | Construction and applications of CRT sequences[END_REF]: Given the number of sensor nodes K, we set p to be the smallest prime equal to or larger than K and q to be kp -1 (k ≥ 2). For g = 0, 1, p -1, we let

I ′ g ,p,q = {(gt mod p, t) ∈ Z p ⊕ Z q : t = 0, 1, ..., q -1} (1)
Then we obtain the characteristic set I g in Z pq by taking the inverse image f -1 (I ′ g ,p,q ). The CRT construction produces p sequences of sequence period pq and Hamming weight q. Here, the Hamming weight of a sequence is the number of ones in a sequence period.

Definition 1: (CRT sequences) For g = 0, 1, ..., p -1, define the CRT sequence generated by I g , denoted by s g (t), be the binary sequence of length L obtained by setting

s g (t) = 1, if t ∈ I g , 0, otherwise. (2)
We will write s g (t) if the values of p and q are understood. Example 1: p=3 and q=5. The three characteristic sets are

I ′ 0,3,5 = {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)} I ′ 1,3,5 = {(0, 0), (1, 1), (2, 2), (0, 3), (1, 4)} I ′ 2,3,5 = {(0, 0), (2, 1), (1, 2), (0, 3), (2, 4)} (3)
By taking the inverse image of I ′ g ,p,q , we obtain I g as

I 0 = {0, 3, 6, 9, 12} I 1 = {0, 1, 2, 3, 4} I 2 = {0, 3, 7, 11, 14} (4)
The generated CRT sequences are listed as follows:

s 0 = [100100100100100] s 1 = [111110000000000] s 2 = [100100010001001] (5)
IV. PROTOCOL SEQUENCE-BASED MAC METHOD FOR DV-HOP LOCALIZATION This section presents a CRT protocol sequence-based medium access method for DV-Hop localization. The proposed method pre-allocates a CRT sequence for each sensor node and uses this sequence to control packet broadcasting. In this paper, it is assumed that the network is beacon enabled and slots are synchronized.

A. Allocation of CRT Sequences

It is supposed that in a network there are K sensor nodes and the number of CRT sequences is p. These p sequences are allocated by network administrator to the K sensor nodes for data transmission. The period of each sequence is denoted as L which can be calculated as L = pq. Here, p and q are relatively prime numbers and q equals to kp -1.

Conventionally, p can be the smallest prime number greater or equal to the number of sensor nodes K. This can assure that every sensor node has one unique protocol sequence for data transmission. However, in practice the network can have a large number of sensor nodes. If p is still greater or equal than K then the period of CRT sequence will become very long and one successful transmission will take much time which will increase the system delay. Therefore, for a network with a large number of sensor nodes, it is recommended that the number of CRT sequences p is smaller than K.

The allocation of protocol sequences is presented as follows. If S = {S(j), j = 1, 2, ..., p} denote the protocol sequences before allocation, then the protocol sequence allocated to the i th sensor node, denoted as P S i , can be expressed as

P S i = S( mod (i, p) + 1) (6)
Here, mod(i, p) is used because the number of sensor nodes K can be bigger than the number of CRT sequences p.

If p is larger than K, every sensor node can surely have one protocol sequence. In this case the data of each sensor node can be transmitted successfully at least once, i.e., unknown node can successfully receive the data from each sensor node. However when p is smaller than K, there should exist several sensor nodes sharing the same protocol sequence. In this case the data from those sensor nodes may collide with each other if those nodes begin their sequences simultaneously. But the probability of collisions can be reduced if each sensor node randomly cyclicshifts the allocated protocol sequence before transmission. This can be illustrated by the following example.

As an example, p is set to 3, K is 5 and q is 5. Then L becomes 15. At the first step of sequence allocation, CRT sequences are obtained by the construction as Eq. ( 5).

At the second step, according to Eq. ( 6) the protocol sequences are allocated to the five nodes as

At the third step, the sensor nodes will randomly cyclic-shift the allocated protocol sequences. Here, we give two random examples. The first example is that the numbers of slots to be shifted in the protocol sequences of the five sensor nodes are assumed to be 1, 2, 3, 4 and 5 respectively. Then the final protocol sequences for actual transmission are

P S 1 = [011111000000000] P S 2 = [011001000100010] P S 3 = [100100100100100] P S 4 = [000011111000000] P S 5 = [010011001000100] (8)
In this example, the data of the first node will not be successfully received because it transmits at the 2 n d , 3 r d , 4 th , 5 th and 6 th slot and collisions happen at all these slots. (It is assumed that the maximum length of data packets cannot exceed one slot duration.) As for the fifth node, the node has not successfully transmitted data packet on the 2 n d , 5 th , 6 th , 9 th and 13 th slots because of collisions. On the other side, the other three nodes can successfully transmit their data, i.e., the second, third and fourth nodes can successfully transmit the data at the 14 th , 1 st and 8 th slots, respectively. As for the other example, the numbers of slots to be shifted in the protocol sequences of the five nodes are assumed to be 7,

In this case all the five nodes can successfully transmit their data at least once. From these two examples, we can see that when the number of protocol sequences p is smaller than the number of sensor nodes K, data from some nodes may not be successfully received. But if each node randomly cyclic-shifts the allocated protocol sequence, there is a chance for all sensor nodes to transmit the data successfully at least once.

B. Broadcasting Strategy of Protocol Sequence Based MAC Method

Due to multiple transmissions of the same data frame, our proposed MAC method is supposed to effectively increase successful receptions at the first two steps of DV-Hop, thus improve localization accuracy. Then our designed broadcasting strategy can make the proposed MAC method well applicable to DV-Hop localization. The procedure of protocol sequence based broadcasting strategy is shown in Fig. 2. All transmissions are assumed to be half-duplex.

Protocol sequences are used by the nodes for data transmission. Therefore, when a node has a data frame to send, it can start one period of protocol sequence. When a node has no data frame to send, although not yet start a protocol sequence, it can receive data frames from other nodes. So, we divide the procedure into two cases: a node has a data frame to send or has no data frame. The detail procedure corresponding to the two cases are described in the following.

1) A node has a data frame to send In this case, a node has a data frame to send, but whether it can broadcast a data frame at the current slot depends on the value of the current element of the protocol sequence. It should be noted that the duration of each element of the protocol sequence is equivalent to the duration of one time slot. The broadcasting procedure in this case consists of the following two steps.

At the first step, a node checks the value of the current element of the allocated protocol sequence. If this value (denoted as P S i (ID ele )) equals to 1, the node can broadcast the data frame. If the value is 0, the node cannot broadcast the data frame at the current slot, but it can receive a data frame from neighbor nodes. At this time, if the node really receives some data frame from neighbor nodes, then the node puts the received data frame into its queue. The received data will be broadcasted in the next period of the protocol sequence.

At the second step, the node checks whether it reaches the end of the current period of protocol sequence. If the ID of the current element of the sequence (denoted as ID ele ) is less than the length of the sequence, indicating the current period of the protocol sequence has not yet finished, then the node will go into the next slot to continue the current period and run the first step again.

On the other hand, if ID ele equals to the length of the sequence, indicating the end of the current period, then the node will check whether it has any data frame in its queue. If the node has some data frame in the queue, then the node will start a new period of the sequence in the next slot to broadcast this data frame. If there is no data frame in the queue, then the node cannot start a new period of the sequence, thus the procedure goes to the other case which will be introduced next.

2) A node has no data frame to send

In this case, a node has no data to broadcast at the current time slot, but it can receive data frames from neighbor nodes. At this time, if the node really receives a data frame, then the node will start a new period of the protocol sequence in the next slot to broadcast the received frame. On the other hand, if the node does not receive any data frame from neighbor nodes at the current slot, the node will continue in the next slot to check whether it can receive some data frame.

The above two-case procedure has illustrated the broadcasting strategy for protocol sequence-based MAC method. The proposed strategy can make the best use of each slot in protocol sequence to fulfill continuous and concurrent transmisstion/reception at half-duplex nodes. Thus the proposed broadcasting strategy makes protocol sequence based MAC method well applicable to DV-Hop localization.

C. Implementation of Protocol Sequence Based MAC Method in DV-Hop Localization

In DV-Hop localization, anchor nodes follow a different procedure than unknown nodes. During one localization period, each anchor node operates two steps, while each unknown node has an additional calculation step (the third step). At the first step, each anchor node broadcasts throughout the network its position frame which composes of its ID, its position and a hop count value initialized as 0. Meanwhile, at this step every node can receive position frames originated from anchor nodes and help to relay broadcasting these frames. In order to avoid endless relay, the relay broadcasting should obey the update mechanism designed in the original DV-Hop algorithm. Through this wholenetwork broadcast, if there are no collisions, all nodes are able to acquire the position of each anchor as well as their minimum hop counts to each anchor. At the second step, each anchor node broadcasts its distance-per-hop frame which contains the ID of the anchor as well as its distance per hop. Meanwhile, each unknown node can also receive the distance-per-hop frames and help to relay them.

Since anchor nodes and unknown nodes follow aforementioned different procedures, the implementation of protocol sequence based MAC method will be presented for anchor nodes and unknown nodes separately. Figure 3 shows the procedure followed by each anchor node A i . A i begins its localization period at the time T 0 i . Then, according to our protocol sequence based medium access method, if the value of current element of the allocated protocol sequence is 1, A i is allowed to broadcast its position frame to its neighbors. If the value is 0, A i cannot broadcast the position frame to its neighbors at the current slot, but it can receive position frames from neighbor nodes. When A i really receives some position frame from neighbor nodes, the received position frame will be put into the queue. This received position frame will be broadcasted in the next period of protocol sequence.

When A i has received all anchors' position frames, it will immediately end the first step and enters the second step. This time instant is denoted as T r i in Fig. 3. Otherwise, if A i could not receive all anchors' position frames until the deadline T 0 i + T s1 , A i will nevertheless end the first step. With these two cases taken into consideration, A i ends the first step at the time T r i or T 0 i + T s1 .

A i begins the second step by calculating its distance-perhop. Then according to the broadcasting strategy of protocol sequence based medium access, A i broadcasts its distance-perhop frame to its neighbors if the current element of the sequence is 1. If the value is 0, A i is not allowed to broadcast its distanceper-hop frame, but A i can receive other anchors' distance-perhop frames from neighbor nodes. The received distance-per-hop frame will be put into its queue and will be broadcasted in the next period of protocol sequence. When A i ends the second step, it also ends one localization period, because only unknown nodes participate in the third step. Then A i will start a new localization period and repeat the aforementioned steps. Here the maximum duration of one localization period is denoted as T .

Fig. 4 shows the procedure for each unknown node N i . N i begins its localization period at the time T 0 j . During the first two steps, N i receives and relays anchors' data frames including anchors' position frames and distance-per-hop frames. If N i really receives a data frame from its neighbors, it will record the information in the frame and check whether it should relay broadcasting the frame according to the update mechanism designed in the original DV-Hop algorithm. If it needs to relay the frame, it will start a new period of its allocated protocol sequence and transmit the data frame according to the protocol sequence. When N i has received all anchors' position frames and distance-per-hop frames at least once, it will immediately end the first two steps. However, if N i could not receive all anchors' position frames and distance-per-hop frames at least once until the time T 0 j + T s1 + T s2 , N i will nevertheless end the first two steps. Then, N i enters the third step to calculate its position based on the information received at the first two steps. Finally, N i ends one localization period at the time T 0 j + T and restarts a new period.

V. SIMULATION AND ANALYSIS

Using MATLAB, we simulate the DV-Hop localization protocol with three candidate medium access methods. The three methods are CRT sequence based medium access method, prime sequence based medium access method [START_REF] Shaar | Collision resolution in contention access local area networks using concatenated prime sequences[END_REF] and the slotted version of E-CSMA/CA [START_REF] Gui | Improvement of range-free localization technology by a novel DV-hop protocol in wireless sensor networks[END_REF]. In the following, we first introduce the simulation scenario and parameters, then present the simulation results and give the analysis.

A. Simulation Scenario

As listed in Table I, our simulation scenario takes place within a 100 × 100m 2 area. Inside this area, 100 nodes including anchors and unknown nodes are randomly placed with the communication range of 25 m. The ratio of anchor nodes can range from 5% to 40%. An example of the network is given in Fig. 5 where the number of anchor nodes is 10.

As for the synchronization, all the sensor nodes are slot synchronized but not frame synchronized because all nodes may start their protocol sequence at different time. Thus we consider slot synchronous model in which the slot boundaries of nodes are aligned. Two data frames from two different nodes will either overlap completely or not overlap at all. Since the protocol sequences need not to start at the same time, the relative delay offsets between two nodes are integral multiple of the duration of one time slot.

The duration of slot is calculated as follows. Since one slot can transmit not only position frame but also distance-per-hop frame, the length of the longer frame between these two frames will be assigned to the duration of one slot. First, the lengths of both frames are calculated. Conforming to data frame formats in IEEE standard 802.15.4 [START_REF]IEEE Standard for Information Technology-Local and Metropolitan Area Networks-Specific Requirements-Part 15.4[END_REF], the position frame have three parts including frame header (7 bytes), data payload (9 bytes) and check sequence (2 bytes). Here, the data payload has 9 bytes because it contain an 8-byte position of the corresponding anchor node and 1-byte hop count to the anchor. So the length of a position frame is 18 bytes, equivalent to 144 bits if one byte equals 8 bits. The difference between distance-perhop frame and position frame is the content of data payload. Only containing 4-byte distance-per-hop in data payload, each distance-per-hop frame has 13 bytes, equivalent to 104 bits. Since the position frame is longer, the duration of one slot is set to that of a position frame, i.e., 144 bits. If data rate is 250 kbps, then the duration of each slot is 0.576 ms.

The maximum duration of the first step is denoted as T s1 , whereas T s2 is used to represent the maximum duration of the second step. In DV-Hop algorithm, all data broadcast is included at the first two steps, while the third step is dedicated for position calculation. Since the broadcast normally takes much more time than the calculation, the maximum duration of the first two steps is very close to the entire period of localization (denoted as T ). Besides, since the first step and the second step both broadcast data frames, their duration should be similar. As an example, we can set T s1 to be T /2 and T s2 to be 3T /8. Then, the maximum duration of the third step is T -T s1 -T s2 = T /8. We assume T to be 5.76 s, obtained by multiplying the duration of each slot (0.576 ms) by the number of slots assumed as 10000, which should be sufficient to cover the most distant end-to-end transmission in the network at the first two steps of DV-Hop. Then, the maximum durations of the three steps of DV-Hop are calculated to be 2.88 s, 2.16 s and 0.72 s respectively.

As discussed previously, the number of protocol sequences (denoted as p) is supposed to be smaller than the number of sensor nodes K, because a large p would increase the period of protocol sequences and then the transmission over one sequence would take much more time which increases the system delay. Therefore, we set p to 5, 7, and 11.

Dedicated for the slotted version of E-CSMA/CA, the maximum random waiting time of each anchor node before performing CSMA/CA, denoted as t w a , is set to 0.576 s. Here t w a cannot be too small; otherwise, different anchors probably send their position/distance-per-hop frames at similar time, causing more collisions. In addition, the maximum random waiting time of each relay node (either anchor or unknown node) in E-CSMA/CA, denoted as t r , is set to 5.76 ms.

B. Simulation Results and Analysis

In this section, we simulate and compare four DV-Hop localization protocols, i.e., DV-Hop-ideal, DV-Hop-E-CSMA/CA, The average localization error is used to measure the accuracy, while the average localization time is for measuring the average of all localization delays regarding to all unknown nodes. Here, localization delay of an unknown node is represented by the time required to completing its three steps of DV-Hop localization. The localization delay of an unknown node may be smaller than one localization period, because the period equals the maximum duration of the total three steps, while the node may end the first in advance.

Fig. 6 shows how localization errors of different DV-Hop localization protocols change with the number of anchors. As for DV-Hop-CRT-PS, it is observed that the accuracy becomes better when the number of anchors increases. Two reasons are given as follows. First, when more anchors join the network, each unknown node can get more useful information including the positions of the new anchors and the hop counts to them. The second reason is that with more anchors in the same area, an unknown node could be closer to some anchors, then the distance estimation between each anchor and the unknown node should be less erroneous.

As for DV-Hop-ECSMA/CA, when the number of anchors increases (at most 20), the accuracy also improves. But the accuracy becomes worse when the number of anchors increases from 20. The reason is that with so many anchors, the network traffic becomes heavy, causing considerable collisions. These collisions will prevent unknown nodes from receiving the right position frame that has the smallest hop count. The increased collisions can also be deduced from Fig. 7 (a) and (b) on the number of transmitted frames and the number of successful receptions. Both quantities are counted for all nodes during one localization period and then averaged per node. Observed from subfigure (a) and (b), though DV-Hop-E-CSMA/CA has similar number of transmitted frames to DV-Hop-ideal, its successful receptions are much fewer, indicating that many frames have been destroyed by collisions.

In Fig. 6 we notice that DV-Hop-CRT-PS (with p greater than 5) has better accuracy than DV-Hop-E-CSMA/CA. The reason is explained as follows. In DV-Hop-CRT-PS each anchor broadcasts its position frame multiple times during one protocol sequence. Although more collisions may occur, unknown nodes have much more chance to receive the right position frames. This can also be supported by the results shown in Fig. 7(d) where DV-Hop-CRT-PS (with p greater than 5) has much more successful receptions than DV-Hop-ideal. The good performance of DV-Hop-CRT-PS is achieved at the cost of additional transmissions as shown in Fig. 7(c).

From Fig. 6, it is also observed that the localization accuracy of DV-Hop-CRT-PS gets better when p increases. Two reasons can be given. The first reason is that as p increases, with more protocol sequences the possibility of several nodes sharing the same protocol sequence becomes smaller, resulting greater probability to successfully receive data frames. As the second reason, when p increases, the anchors will broadcast more replicas of position frames or distance-per-hop frames during one protocol sequence. Due to these two reasons, unknown nodes can receive more right position frames from anchors, so that they can obtain less erroneous estimated distance. Thus a larger p can bring better accuracy to DV-Hop-CRT-PS. Although not good as DV-Hop-E-CSMA/CA when p is 5, the performance of DV-Hop-CRT-PS becomes better than DV-Hop-E-CSMA/CA when p goes beyond 5. It can also be observed from Fig. 6 that when p equals to 11, the localization accuracy of DV-Hop-CRT-PS is close to DV-Hop-ideal.

Fig. 8 shows that the average localization time of different DV-Hop localization protocols increases with the number of anchor nodes. Two reasons can be given to explain this. As the first reason, since each anchor needs to broadcast its position frame and distance-per-hop frame throughout the network, if there are more anchors, each unknown node will take more time to receive all anchors' frames. The second reason is that when there are more anchors, the traffic in the network increases (as shown in Fig. 7(a) and 7(c)), which leads to more collisions. Due to the increased collisions, nodes lose more frames from some anchors, then they have to wait for additional time to try retrieving the frames from those anchors. Due to these two reasons, when there are more anchors, the localization time of DV-Hop localization protocols increases.

Shown in Fig. 8, from the curve corresponding to p being 5, it can be observed that when the number of anchors is 5, the average localization time of DV-Hop-CRT-PS is short. But when the number of anchors is no less than 10, the average localization time becomes so long that it reaches the maximum duration of the localization protocol, i.e., 5.76 s. The relatively short localization time in the case of 5 anchors can be explained by two reasons. First, with only 5 anchors, although there exist collisions, each unknown node can still receive at least one position frame and one distance-per-hop frame from every anchor node (but the hop count value inside the received position frame may not be the smallest hop count). Thus each unknown node can still end the first and second steps before the deadline of each step. So the real duration of step 1 (also step 2) doesn't exceed the maximum duration of that step. Therefore the localization time of each unknown node is less than 5.76 s. As the second reason, when p is 5, the length of each protocol sequence is short, thus it will take short time to complete the transmission of all replicas of data frames in each protocol sequence. Due to these two reasons, the average localization time is short when there are only 5 anchors. However, when the number of anchors exceeds 10, the average localization time becomes as long as the maximum duration of one localization period. The reason is that with more anchors, the network traffic increases, resulting in more collisions. Increased collisions will prevent unknown nodes to receive data frames from one or more anchors, so unknown nodes will wait until the deadline of each step of DV-Hop.

As depicted in Fig. 8, when p increases from 7 to 11, the average localization time also increases. The reason is that as p increases, the length of each protocol sequence becomes longer, so it will take more time to transmit all replicas of data frames in each protocol sequence.

From Fig. 9 it can be observed that for the same p, the localization accuracy of DV-hop-CRT-PS is better than DV-hop-Prime-PS. The reason is given as follows. The Hamming weight of DV-hop-CRT-PS denoted as q equals to 2p -1, greater than the Hamming weight of DV-hop-Prime-PS. Since Hamming weight is the number of ones in each sequence, increased number of ones will bring more chance to unknown nodes for receiving the right data frames from anchors. Fig. 10 shows that for the same p, the average localization time of DV-Hop-Prime-PS is shorter than DV-Hop-CRT-PS. As the reason, the length of each prime sequence is p 2 , shorter than the length of each CRT sequence which is pq = p(kp -1). Thus DV-Hop-Prime-PS will take shorter time to transmit all replicas of data frames in each protocol sequence and the average localization time of DV-Hop-Prime-PS will become shorter. It can also be observed that in the case of p being 5, when the number of anchors is no less than 10, the average localization time of DV-Hop-Prime-PS as well as that of DV-Hop-CRT-PS reaches the maximum duration. The reason is explained as follows. With more anchors, the traffic in the network increases, resulting in more collisions. Increased collisions will prevent unknown nodes to receive data frames from some anchors, so unknown nodes will have to wait and to try retrieving frames from those anchors until the deadline of each step of DV-Hop. Therefore, the average localization time reaches the maximum duration of one localization period.

VI. CONCLUSION

In this paper, we propose a CRT protocol sequence-based MAC method for DV-Hop localization. First, we design a broadcasting strategy for protocol sequence based MAC method. This method pre-allocates CRT sequences to all sensor nodes, thus each node can use the allocated sequence to control packet broadcasting at the first two steps of DV-Hop. According to whether a sensor node has a data frame to send or not, two different cases are considered in the broadcasting strategy. For each case, we provide a corresponding procedure. Then we implement the designed protocol sequence medium access method in DV-Hop localization. Through simulation and evaluation, we investigate the performance of DV-Hop localization with our proposed MAC method. Our proposed method is compared with ECSMA/CA and other protocol sequences such as prime sequences, in terms of average localization accuracy and average localization time. Simulation results show that when the number of protocol sequences is larger than a certain number, DV-Hop localization protocol with our proposed CRT protocol sequence based MAC method can achieve better accuracy than that using E-CSMA/CA, while keeping similar localization time.

Fig. 1 .

 1 Fig. 1. Example of a small network.

P S 1

 1 = [111110000000000] P S 2 = [100100010001001] P S 3 = [100100100100100] P S 4 = [111110000000000] P S 5 = [100100010001001]

Fig. 2 .

 2 Fig. 2. Procedure of protocol sequence based broadcasting. 2, 3, 4 and 7 respectively. Then the final protocol sequences for actual transmission are P S 1 = [000000011111000] P S 2 = [011001000100010] P S 3 = [100100100100100] P S 4 = [000011111000000] P S 5 = [000100110010001]

Fig. 3 .

 3 Fig. 3. Procedure for each anchor node A i .

Fig. 4 .

 4 Fig. 4. Procedure for each unknown node N i .

Fig. 6 .

 6 Fig. 6. Average localization errors of 3 different DV-Hop localization protocols.

Fig. 7 .

 7 Fig. 7. Average number of transmitted frames and the average number of successful receptions.

Fig. 8 .

 8 Fig. 8. Average localization time of 3 different DV-Hop localization protocols.

Fig. 9 .

 9 Fig. 9. Average localization errors of protocol sequence based DV-Hop localization protocol.

Fig. 10 .

 10 Fig. 10. Average localization time of protocol sequence based DV-Hop localization protocol.

TABLE I SIMULATION

 I PARAMETERS AND THEIR VALUES Fig. 5. Example of a network with 10 anchor nodes.

This work was supported in part by the National Natural Science Foundation of China under Grants 61602245 and 61771244, in part by the Nature Science Foundation of Jiangsu for Distinguished Young Scientist under Grant BK20170039, in part by the Natural Science Foundation of Jiangsu Province under Grant BK20150791, in part by the Open Research Fund of National Mobile Communications Research Laboratory, Southeast University (No. 2017D09), and in part by the Fundamental Research Funds for the Central Universities (No. 30918011318).


Faiza Belbachir

Mohand Boughanem
email: mohand.boughanem@irit.fr

Using language models to improve opinion detection

Keywords:

Opinion mining is one of the most important research tasks in the information retrieval research community. With the huge volume of opinionated data available on the Web, approaches must be developed to differentiate opinion from fact. In this paper, we present a lexicon-based approach for opinion retrieval. Generally, opinion retrieval consists of two stages: relevance to the query and opinion detection. In our work, we focus on the second state which itself focusses on de-tecting opinionated documents . We compare the document to be analyzed with opinionated sources that contain subjective information. We hypothesize that a document with a strong si-milarity to opinionated sources is more likely to be opinionated itself. Typical lexicon-based approaches treat and choose their opinion sources according to their test collection, then cal-culate the opinion score based on the frequency of subjective terms in the document. In our work, we use different open opinion collections without any specific treatment and consider them as a reference collection. We then use language models to determine opinion scores. The analysis document and reference collection are represented by different language models (i.e., Dirichlet, Jelinek-Mercer and two-stage models). These language models are generally used in information retrieval to represent the relationship between documents and queries. However, in our study, we modify these language models to represent opinionated documents. We carry out several ex-periments using Text REtrieval Conference (TREC) Blogs 06 as our analysis collection and Internet Movie Data Bases (IMDB), Multi-Perspective Question Answering (MPQA) and CHESLY as our reference collection. To improve opinion detection, we study the impact of using different language models to represent the document and reference collection alongside different com-binations of opinion and retrieval scores. We then use this data to deduce the best opinion de-tection models. Using the best models, our approach improves on the best baseline of TREC Blog (baseline4) by 30%.

Introduction

The large volume of opinionated data on the Web has caused a recent increase in a number of online phenomena, such as online shopping and online elections. These opinionated data need to be manipulated in order to analyze, deduce or predict users choices in a variety of domains. Unlike traditional topic-based retrieval, the documents returned by opinion mining should not only be relevant to the topic but contain opinions about it.

While blogs are a rich source of opinions, they makes opinion detection more difficult because bloggers have a specific language that incorporates emoticons and does not respect grammatical rules. In 2006, TREC [START_REF] Voorhees | Overview of the TREC 2006[END_REF] debuted a special track with the • We use various open and available subjective resources;

• We use different methods to calculate opinion scores;

• We adapt the language models used for opinion detection;

• We compare different language models for representing the analysis document and reference collection in order to find the models that most improve opinion detection as compared to the best baseline provided by TREC (baseline4). This paper is organized as follows: In Section 2, we describe related work on the opinion retrieval phase. In Sections 3 and 4, we describe our proposed approach in detail. In Section 5, we discuss the experiments and the obtained results. Finally, we conclude the paper and summarize our findings.

Related work

There are several extant studies in the field of opinion mining. Some of these use approaches with a classifier that takes data as its input and produces output against testing data. With these approaches, difficulties include determining the features that represent opinionated documents, identifying the best classifiers for a better result, and choosing the training collection that represents the most subjective words. The features used to represent opinionated documents include, for example, the number of adjectives, verbs and adverbs [START_REF] Bifet | Sentiment knowledge discovery in twitter streaming data[END_REF][START_REF] Li | Extracting verb expressions implying negative opinions[END_REF][START_REF] Pang | Thumbs up?: Sentiment classification using machine learning techniques[END_REF][START_REF] Wang | TREC 2008 at the University at Buffalo: Legal and Blog Track[END_REF][START_REF] Yang | Knowledge transfer and opinion detection in the trec 2006 blog track[END_REF][START_REF] Zhang | UCSC on REC 2006 Blog Opinion Mining[END_REF]. Some studies, meanwhile, examine the grammatical relations between different terms in a document. These studies suggest that subjectivity can only be measured in context, because some words, such as "like", are considered subjective, when they are used in other sentences they may no longer express an opinion, such as in the sentence "it looks like a cat" [START_REF] Agarwal | Sentiment analysis of twitter data[END_REF][START_REF] Liu | Improving opinion aspect extraction using semantic similarity and aspect associations[END_REF][START_REF] Saif | Semantic patterns for sentiment analysis of twitter[END_REF][START_REF] Saif | Contextual semantics for sentiment analysis of twitter[END_REF][START_REF] Seki | Adaptive Subjective Triggers for Opinionated Document Retrieval[END_REF][START_REF] Wang | Mining aspect-specific opinion using a holistic lifelong topic model[END_REF]. Some studies, such as the work of [START_REF] Aidan | Genre classification and domain transfer for information filtering[END_REF], classify features of opinionated documents into two categories: those that depend on the query and incorporate relevance and opinion into the learning phase [START_REF] Saif | Semantic patterns for sentiment analysis of twitter[END_REF][START_REF] Seki | TREC 2007 Blog track experiments at Kobe University[END_REF], and those that use characteristics independent of the topic and do not incorporate relevance into the learning phase. Furthermore, while some studies use a single classifier like support vector machine (SVM), naive bayes or logistic regression to return opinionated documents, others use multiple different classifiers to compare their impacts on opinion detection [START_REF] Balahur | Sentiment analysis -What are we talking about? Proceedings of the 7th workshop on computational approaches to subjectivity, sentiment and social media analysis[END_REF][START_REF] Balahur | Sentiment analysis meets social media -challenges and solutions of the field in view of the current information sharing context[END_REF][START_REF] Bauman | Recommending items with conditions enhancing user experiences based on sentiment analysis of reviews[END_REF][START_REF] Fu | Sentimental spidering: leveraging opinion information in focused crawlers[END_REF][START_REF] Lu | Sentiment-based topic suggestion for micro-reviews[END_REF][START_REF] Mullen | Sentiment analysis using support vector machines with diverse information sources[END_REF][START_REF] Pang | A sentimental education: sentiment analysis using subjectivity summarization based on minimum cuts[END_REF][START_REF] Riloff | Learning extraction patterns for subjective expressions[END_REF][START_REF] Seki | TREC 2007 Blog track experiments at Kobe University[END_REF][START_REF] Tu | Investment recommendation using investor opinions in social media[END_REF]. Finally, some pre-existing approaches use internal collections built directly from the collection to be analyzed for collections training, while others use external collections built from independent collections of the analyzed collection [START_REF] Aidan | Genre classification and domain transfer for information filtering[END_REF][START_REF] Baccianella | Sentiwordnet 3.0: An enhanced lexical resource for sentiment analysis and opinion mining[END_REF][START_REF] Bifet | Sentiment knowledge discovery in twitter streaming data[END_REF][START_REF] Pak | Twitter as a corpus for sentiment analysis and opinion mining[END_REF][START_REF] Seki | TREC 2007 Blog track experiments at Kobe University[END_REF]. Due to their reliance on machine learning, these approaches are dependent on learning the data, features and choices of the classifier being used. Other studies use dictionaries of subjective words to identify opinionated documents, considering documents that contain many subjective words to be opinionated. Sometimes, these dictionaries are directly prepared from the test data collection. Other times, ready-made lexical dictionaries like General Inquiry [START_REF] Stone | The general inquirer: A computer approach to content analysis[END_REF] or SentiWordNet (SWN) [START_REF] Esuli | Sentiwordnet: A publicly available lexical resource for opinion mining[END_REF]) are used, although some studies report that these are less effective than lexicons extracted from the test data collection itself [START_REF] Andreevskaia | Semantic tag extraction from WordNet glosses[END_REF]Lafferty & Zhai, 2001). While many approaches use individual words for processing semantic information, some approaches use natural language processing techniques that consider not only the word but the entire sentence [START_REF] Agarwal | Sentiment analysis of twitter data[END_REF]Castro-Espinoza, Gelbukh, & González-Mendoza, 2013;[START_REF] Liu | Improving opinion aspect extraction using semantic similarity and aspect associations[END_REF][START_REF] Tang | A survey on sentiment detection of reviews[END_REF][START_REF] Thelwall | Sentiment strength detection for the social web[END_REF][START_REF] Thelwall | Sentiment in short strength detection informal text[END_REF]. These approaches are typically based on the presence or absence of a subjective term in a document, and do not incorporate the frequency of the subjective term in question. However, a term that reoccurs several times in a document suggests a stronger opinion than one that appears only once. This issue helps to explain why relatively few studies employ language models to identify opinionated documents. Language modeling has proved its worth in the field of information retrieval [START_REF] Song | A general language model for information retrieval[END_REF] for ad-hoc information retrieval tasks based on probability to represent a model of document and a model of query.

Similarly, researchers have exploited the benefits of language modeling in opinion mining as well. In particular, the authors of [START_REF] Huang | A unified relevance model for opinion retrieval[END_REF] propose a unified opinion-retrieval model based on the Kullback-Leibler (KL) divergence between the two probability distributions of the opinion relevance model and the document model. The authors divide sentiment words into querydependent and query-independent categories by using sentiment expansion techniques, and then integrate them into a mixed model. In order to extract sentiment words, Cornell movie review datasets, the MPQA corpus 1 and TREC Blog 06 [START_REF] Macdonald | The TREC Blog06 collection: Creating and analysing a blog test collectionTechnical Report[END_REF] are used as opinionated collections. The authors of [START_REF] Zhang | A generation model to unify topic relevance and lexicon-based sentiment for opinion retrieval[END_REF] propose a generative model to unify topic relevance and opinion scores. The authors use a language model approach with smoothing to couple retrieval and opinion scores. Different sentiment lexicons like Wornet, General Inquiry and HowNet are used to calculate opinion scores, while binary independent retrieval is used to calculate topic relevance scores. The authors of [START_REF] Mei | Topic sentiment mixture: modeling facets and opinions in weblogs[END_REF] also create a probabilistic model to capture the mixture of topics and sentiments simultaneously present in consumer products. The opinion score for a given product is a mixture of a variety of facets. However, associating a sentiment with products and facets is challenging. This approach has been tested with the small-scale collection OpinMind. 2 The authors of Mei et al. (2007a) propose an opinion retrieval model using the framework of generative language modeling. They model a collection of natural language documents or statements, each containing topic-bearing and sentiment-bearing words. Sentiment is either represented by a group of predefined seed words or extracted from a training sentiment corpus. This model has been demonstrated to be effective on the MPQA corpus. Our approach is based on using language models to identify opinionated documents. In contrast to pre-existing work, we use different open, subjective resources without any prior treatment; adapt the language model of information retrieval in opinion detection and analyze the different factors that impact opinions in order to best represent our documents.

Our opinion finding approach

In our approach, we consider that a document contains an opinion if it is generated by a language model associated with opinionated documents. To construct a model of opinionated language, we rely on a reference collection containing opinionated documents. Similarly, we also model the analysis document in the form of a language model. In order to measure the degree of subjectivity (i.e., the presence of opinions) in the document, we measure the similarity between the two models. In Fig. 1, we describe the steps of our proposed lexical approach. These steps are as follows:

•

Step 1: Determine relevance to the query: The process of opinion detection must return documents containing opinions that are relevant to the given query.

•

Step 2: Perform opinion detection: To identify opinionated documents, we use different subjective resources, such as IMDB, CHESLY, ROTTEN and MPQA. We call these resources the reference collection, and consider it our opinion collection. We then represent the reference and documents collections in a variety of different ways using several language models.

The aim is to represent the collection and the document to be analyzed as accurately as possible. After modeling the analysis document and the reference collection, we measure the similarity of the two models using their opinion scores. The focus of our work is therefore the accurate modeling of the document and reference collection and the calculation of opinion scores. In the following sections, we detail our approach.

Language model to represent document

There are different language models used in the field of Information retrieval. We adapt some of them to the opinion detection by introducing the notion of opinion. For that we consider four models to represent the test document : Maximum Likelihood (ML), Dirichlet (DIR), Jenlinek Merker (JM) and Two Stage (ST).

1. Maximum likelihood (ML) (Jelinek, 1997): In this method we use a simple language model to represent the document θ ML _ D (see Eq. ( 1)).

= = θ ML P w D c w D D _ ( ) # ( , ) D ML (1)
where c w D # ( , ) denotes the number of times the word w occurs in document D, and |D| refers to the number of words in the document D.

To introduce the opinion concept in this model, we smooth the model of document with the model of reference collection. 2. Jelinek Mercer (JM) [START_REF] Bahl | A maximum likelihood approach to continuous speech recognition[END_REF]: In this method, we interpolate the model of Maximum Likelihood P ML (w|D) with the language model of reference collection P ML (w|R) using a coefficient λ d fixed to control smoothing for these two models, where P ML (w|R) represents the probability that a term w appears in the test collection R. This method is expressed by the Eq. ( 2).

= = + - θ JM P w D λ P w D λ P w R _ ( ) * ( ) (1 )* ( ) D JM d ML d ML
(2)

1 http://www.cs.pitt.edu/mpqa/. 2 https://techcrunch.com/tag/opinmind/.

It is clear that if coefficient

= λ 1 d the model of D is an ML model, and if = λ 0 d
it is the same as reference collection's model P (w|R). For any other value of this coefficient, the document's model is generated by the model of the reference collection. This is used to boost the documents containing the terms of reference collection. 3. Dirichlet (DIR) (Zhai & Lafferty, 2001): This method also interpolates the ML model with a model of reference collection to encourage holders of opinion documents, with a dynamic smoothing parameter λ which changes depending on the length of the document. The model is represented by Eq. ( 3) where = + λ D D µ and μ is a fixed parameter. This means that if the document is long, then the smoothing is low.

= = + + + θ DIR P w D D D µ P w D µ D µ P w R _ ( ) ( ) ( ) D DIR ML ML
(3) 4. Two Stage (TS) [START_REF] Zhai | Two-stage language models for information retrieval[END_REF]: In this method, a combination of both smoothing models is made, this combination improves the representation of the document θ D . First the document is estimated using Dirichlet smoothing with a dynamic coefficient = + λ D D µ depending on the size of the document D. But this model penalize longer documents. To remedy for this problem a second smoothing method based on Jenlinek Mercer used with a fixed smoothing coefficient γ D . This combination of two smoothing models can smooth any kind of document, regardless of its size, with the language model of the reference collection. Another advantage of this double smoothing is that the document view is doubly boosted due to the insertion of the R model (of opinion model) in the model Dirichlet and the model of Jenlinek Mercer on a same time. This method is represented by Eq. ( 4).

= = + + + - θ TS P w D γ c w D µP w R D µ γ P w R _ ( ) # ( ) ( ) (1 ) ( ) D TS D ML D ML (4)
To reinforce this concept of subjectivity, we also propose to consider the subjectivity a priori of a term based on the lexical resource SentiWordNet (SWN) [START_REF] Esuli | Sentiwordnet: A publicly available lexical resource for opinion mining[END_REF]). SWN assigns three numerical scores (Obj(s), Pos(s), Neg(s)) to each synset of the WordNet describing how objective, positive or negative the terms within a synset are. The range of three scores lies in interval [0, 1] and sum of all the scores equals to 1. A template of SWN is shown in Fig. 2. Template of SentiWordNet with first column: Parts of Speech (POS) of the Synset, 2nd column: Offset of the Synset in WordNet, 3rd Column: Positive Score of the Synset, 4th Column: Negative Score of the Synset, 5th Column: Entries of a Synset Quantitative analysis of the glosses of the synsets is performed to obtain three scores. The idea behind the creation of SWN was that different senses of a term might have different semantic orientations. For example, the term estimable is objective (i.e. Obj(estimable) = 1.0 with its Pos = Neg = 0.0) corresponding to its sense may be computed or estimated and SWN scores for the same term become as Obj(estimable) = 0.25, Neg(estimable) = 0 and Pos(estimable) = 0.75 when its sense deserving of respect.

A simple way to measure the subjectivity of a term in SWN is taking the average subjectivity (positive and negative) of synsets in which the term appears. In fact, this approach is rather simplistic; it makes no disambiguation of terms. We calculate the subjectivity score of a term by summing the positive and negative scores in all synsets of the term and dividing the total by the number of synset (see Eq. ( 5)).

∑ = + ∈ Subj w Neg si Pos si sens w ( ) ( ( ) ( )) ( ) si sens w ( ) (5)
Where respectively Neg(si) or Pos(si) is the negative/positive score of sense (or synset) si of term w as found in SentiWordNet SWN and |sens(w)| is the total number of senses for term w in SWN.

Considering this subjectivity, the model of document θ D will be represented by Eq. ( 6).

= θ M Subj P w D Subj w _ _ ( )* ( ) D M (6) With M ∈ {ML, DIR, JM, TS}
After representation the model of document, we proceed to modelling the reference collection.

Language model to represent reference collection

The model of reference collection is also estimated in different ways. Eqs. ( 7)-( 11) refers respectively to Eqs. ( 1)-( 4) and ( 6) where some parameters are changed. We explain all equations as following:

The first model is based on a simple probability frequency of terms in the reference collection (see Eq. ( 7)).

= = θ ML P w R c w R R _ ( ) # ( , ) R ML (7)
where c w R # ( , ) denotes the number of times the word w occurs in the reference collection R and |R| refers to the number of words in the reference collection.

If a term of the document does not appear in the reference collection then it will have a probability equal to zero. This model does not boost the terms that belong to the test collection. Thus three smoothing models are used (the same as used previously in the modeling of the document), these models combine the model of the reference collection (R) with the model of the test collection (C).

The first smoothing model is based on the model of Jenlinek Mercer represented by the Eq. ( 8).

= = + - θ JM P w R λ P w R λ P w C _ ( ) * ( ) (1 )* ( ) R JM r ML r ML (8)
Where λ r is smoothing parameter and C is the test collection. This smoothing change with the value given to the variable λ r . This means that it favours large documents containing the terms of the collection.

The second model is based on the Dirichlet smoothing model, represented by the Eq. ( 9), with a smoothing factor equal to

+ R R µ
where μ is a fixed parameter.

= = + + + θ DIR P w R R R µ P w R µ R µ P w C _ ( ) ( ) ( ) R DIR ML ML ( 9
)
Where P ML (w|C) is the probability that term w is in the test collection C. These two models (JM and DIR) solved the problem to end up with a zero probability when a document does not contain the terms of reference collection by adding the probability P ML (w|C).

The third proposed model, called Two Stage, is a combination of the two modeles represented by Eq. ( 10).

= = + - + + θ TS P w R γ P w R γ c w C µP w R C µ _ ( ) ( ) (1 ) # ( , ) ( ) R TS R ML R ML ( 10
)
γ R is coefficient fixed to control smoothing models. This model has the advantage of boosting doubly opinionated documents because it inserts twice probability of P(w|R) in the ML model and in the DIR model. To booster advantage of subjective words, we propose to weight each term with its subjectivity score, as was done for the model document. The model of reference collection is represented by the general Eq. ( 11).

= θ M Subj P w R Subj w _ _ ( )* ( ) R M (11)
With M ∈ {ML, DIR, JM, TS} After modeling the document and the reference collection, we define in the following different opinion scores that we have used to re-rank opinionated documents.

Opinion score

We propose to calculate the score of opinion at document level in various functions. We first use, the Kullback-Leibler divergence (Score KL R D R _ _ ( , )) (Zhai & Lafferty, 2001).

∑ = ∈ Score KL R D R θ log θ θ _ _ ( , ) * w D D D R ( 12
)
Where θ D and θ R are the language models of respectively the document and the collection of opinions as they were defined in the previous sections. This opinion score function computes the divergence between different probability distributions. When the score is lower it means that the document is similar to the reference collection.

A second way to calculate the opinion score is to assess the joint probability of all terms of the document. This amounts to compute the product of the probabilities of weighted terms of the entire document (see Eq. ( 13)):

∏ = ∈ Score prod R D P w D _ _ ( ) ( ) w D (13)
The intuition here is the following: the distribution of words in the document is supposed to model the importance of words in the document and boost the opinion words. This means that more Score prod R D _ _ ( ) is higher more the document contains opinions. The third way to measure the score is given by the following equation:

∑ = ∈ Score mixte R D Opinion w P w D _ _ ( ) ( )* ( ) w D (14)
This score takes into account the opinion score represented by Opinion(w) and the frequency of words in the document represented by P(w|D).

The opinion score is expressed by the terms of the document that must be in the reference collection P(w|R) and in the lexicon SentiWordNet (Subj).

= Opinion w P w R subj w ( ) ( )* ( ) (15)
All scores calculated in this section are not referring to the relevant concept. We recall that our aim is to study the opinion dimension only. Regarding the relevance dimension, we considered that it is calculated also using any information retrieval model. Therefore, to return a list of relevant documents to the query and expressing an opinion about it, we propose to combine in different ways relevance score and opinion score. This is discussed in the last part of the experimental section.

Experimentation results

Data collections

To evaluate our proposition, we conducted experiments using the TREC Blog 2006 data set as our test collection and the IMDB, CHESLY, MPQA and ROTTEN resources as our reference collection data.

Test collection: TREC Blogs track

The TREC Blog 2006 data collection [START_REF] Voorhees | Overview of the TREC 2006[END_REF] consists of more than 3.2 million blogs crawled for a period of 11 weeks from December 2005 to February 2006. The Text REtrieval Conference proposes a set of subjects (50 topics per year) and relevant judgements (qrels) tagged according to the following scheme: 0 for irrelevant blogs, 1 for relevant blogs, 2 for blogs with negative opinions, 3 for those with mixed opinions and 4 for those with positive opinions. In order to facilitate direct comparison between systems, five relevance retrieval baselines have been provided by TREC organizers, selected from the best performing retrieval runs submitted by participating groups. The best baseline is baseline4,3 and we accordingly compare our results with this baseline.

Reference opinion data collection

We used different corpora of opinion collections as our reference collection. The first corpus is provided by [START_REF] Pang | A sentimental education: sentiment analysis using subjectivity summarization based on minimum cuts[END_REF] and contains 1000 positive and 1000 negative full-text movie reviews taken from the IMDB archive. 4 The second corpus constitutes 50,000 subjective sentences from Rotten Tomatoes customer review snippets. 5 The third is the MPQA opinion corpus,6 which contains 10,657 sentences across 535 documents. These documents are extracted from 187 different foreign and U.S. news sources from June 2001 and May 2002. The last corpus, CHESLEY [START_REF] Chesley | Using verbs and adjectives to automatically classify blog sentiment[END_REF], is a manually annotated dataset of objective and subjective documents developed by [START_REF] Chesley | Using verbs and adjectives to automatically classify blog sentiment[END_REF]. It contains 496 subjective and 580 objective documents. Before using these corpora as our test collection and reference opinion data collection, we tagged them for parts of speech (POStagging) using CRFTagger [START_REF] Phan | CRFTagger: CRF English POS Tagger[END_REF]. In keeping with several studies (Bruce & Wiebe, 1999;[START_REF] Wiebe | Development and use of a gold-standard data set for subjectivity classifications[END_REF], we considered only the adjectives, adverbs, verbs and nouns including subjective information.

Results

As previously mentioned, the purpose of our study is to investigate the opinion dimension of opinion retrieval exclusively. In order to evaluate the performance of our approach, we used the list of relevant documents supplied by TREC assessors, TREC Topics 2006. We then reordered the documents based on their opinion scores. Evaluation results are presented in terms of average precision (AP) for queries and mean average precision (MAP) for sets of queries and documents graded 10 for accuracy (i.e., P@10). We conducted some preliminary experiments and set smoothing parameters λ to 0.6 and μ to 0.1.

We evaluated our approach in different ways:

• the impact of SWN-calculated subjectivity on opinion detection;

• the impact of the reference collection on opinion detection;

• the impact of the document model on opinion detection;

• the impact of opinion scores on opinion detection;

• the impact of the method used for combining opinion score and relevance score on opinion detection.

Impact of SentiWordNet on opinion detection

In this experiment, we aimed to measure the impact of SWN calculated subjectivity on opinion detection. In order to do so, we compared the obtained results from the two models (document and reference) when incorporating subjectivity (θ ML Subj _ _ ,

D θ ML Subj _ _ R
) and when not incorporating subjectivity (θ ML _ ,

D θ ML _ R
). We restricted the study to ML language models due to our focus on the role of SWN-calculated subjectivity on models not already improuve by smoothing techniques. The opinion scores were calculated according to the three scores (Score prod R D

_ _ ( ), Score KL R D _ _ ( ), Score mixte R D _ _ ( )).
The best results, shown in Table 1, were obtained using the Score KL R D _ _ ( ). Table 1 shows the MAP and P@10 values obtained for all 50 queries. The results reveal that the model incorporating subjectivity was better than the model that did not (16% improvement on the MAP and 143% on P@10). We conclude that the SWN lexicon is a rich source of opinion words, even in blogs.

Impact of the reference collection model on opinion detection

We also studied the impact of the language model of the reference collection on opinion detection, with the aim of discovering the best model for representing reference collections. In order to do so, we considered the model of the document as a representation (θ ML _ D ) so as not to bias the results and reference model of the three models mentioned previously ((θ

DIR _ R ), (θ JM _ R ) and (θ TS _ R
)). We calculated the opinion score using three scores, the best results shown in Table 2, were obtained using the Score KL R D R _ _ ( , ). Table 2 details the results obtained in terms of the MAP and P@10 for all requests.

We note that the best result was produced by the pair (ML, TS). Specifically, the best representation of the reference collection was a two-stage model, with an improvement of over 39.26 in the MAP and 73.43 in the P@10 compared to other representations. A smoothing reference model with a model of the test document therefore improves opinion detection.

Impact of the document model on opinion detection

In order to study the impact of the test documents language model on opinion detection, we considered the model of the document in the three performances mentioned previously (θ DIR _ 3), because they give better results than the other scores. Table 3 displays the MAP and P@10 results obtained on all requests. The results demonstrate that the two stage model was the best model for representing opinionated documents, with an improvement of more than 4.88% in the MAP and 6.35% in accuracy compared to other representations.

The improvement of the result is until less because we use the best representation of the reference model that is smoothed with the test document model. We can conclude that using a reference model in the model of the test document improves the opinion score.

Impact of opinion scores on opinion detection

Finally, we compared the three scoring functions proposed in the previous section, namely the score based on the KL divergence

(Score KL R D R _ _ ( , )
), the score based on the product of weighted terms (Score Prod R D _ _ ( )) and the mixed score (Score Mixte R D _ _ ( )). We made use of optimal representations for our document and reference collection, as derived from our previous study θ TS 4. We find that the KL divergence produces much better results than those obtained by the (Score Prod R D _ _ ( )) and (Score Mixte R D _ _ ( )) functions. This is explained by the way in which the KL divergence explicitly expresses the concept of opinion in two different ways: in the model of the document θ d and in the reference model θ R . While the score for which is based on the product, the concept of opinion is expressed only in the probability P(w|D), explaining its low performance. The mixed score, meanwhile, also expresses the concept of opinion in two ways with the probabilities P(w|R) and Subj(w) but differs from the KL divergence by including the concept of frequency words, expressed by the probability P(W|D). The poor results obtained by the mixed score as compared to the similarity score reflect the fact that the repetition of a slightly subjective term several times in a document does not guarantee that this document is highly subjective, while a subjective term repeated only once in the document may make it highly opinionated.

Combining relevance and opinion scores

Due to our focus on assessing the opinion dimension exclusively, the results detailed above do not take into account the relevance of documents. In order to find relevant documents expressing an opinion, we propose combining the opinion score Opinion(D) of a document with its relevance score. The opinion score of a document is calculated on Score KL R D _ _ ( ), based on the best performances in previous studies (θ TS _ D and θ TS _

R

). The relevance score of a document to a query Retrieval(D, q) is provided by TREC. We combined the relevance and opinion scores in two different ways: The first score was based on a linear combination given by Eq. ( 16).

= + - Score Final Linear D α Retrieval D q α Opinion D _ _ ( ) * ( , ) (1 )* ( ) (16)
The second was based on a product combination given by Eq. ( 17).

= Score Final Product D Retrieval D q Opinion D _ _ ( ) ( , )* ( ) (17)
Retrieval(D, q) represents the retrieval score of the document D for query q, Opinion(D) represents the opinion score of the document D calculated with the best measure score of opinion detection (Score KL R D R _ _ ( , )), represented in Eq. ( 12) and α represents a smoothing parameter.

Table 1

Result of MAP and P@10 for models that take-do not take a subjectivity SWN. Table 5 lists the results of MAP and P@10 scores of both configurations (Produced and Linear) and the best baseline TREC (baseline 4)7 .

These results demonstrate that both configurations improve baseline4. The lowest result for these two configurations was produced by the product combination. This is most likely explained by the product combinations weighting of the relevance score and the opinion score, as compared to the linear combination, which promotes more opinionated documents by assigning = 0.1. There was an improvement of more than 14.26% in the MAP and 28.48% in the P@10 to linear score compared to the product score. We also observe that the configuration based on the linear score produced an improvement of more than 10.65% in the MAP and 24.84% in the P@10 compared to the best result produced by TREC, baseline4. The significance of these improvements on the baseline were validated with a t-test (with p < 0.05).

We also compared our work with other approaches, such as the work of Ellen Voorhees and al. [START_REF] Song | Dutir at trec 2007 blog track[END_REF], which obtained a MAP of 0.1885 and a P@10 of 0.5120 using TREC evaluation. Our approach improved on this work by more than 43.51% at the MAP level and 24.84% at the P@10 level. In addition, we compared our results against studies that did not participate in TREC but made use of the same collection and topics. In particular, we compared our work with the work of [START_REF] Seki | Adaptive Subjective Triggers for Opinionated Document Retrieval[END_REF], who obtain the best results with a MAP of 0.3221 but no P@10 calculation. With our approach, we improved on the MAP of these results by 3.67%. Compared to the work of [START_REF] Missen | Using passage-based language model for opinion detection in blogs[END_REF], who obtained a MAP of 0.3303 and a P@10 of 0.6340, our results show an improvement of 1.22% and 3.08%, respectively.

Conclusion

In this article, we propose an approach for identifying opinionated documents. In particular, we assume that a document contains opinions if it is similar to the opinionated collection (or reference collection). In order to measure this, we model the document and the reference collection using different language models. We adapt language models used in information retrieval to represent the query and document for opinion detection. In order to do so, we introduce a document model in the reference collection and a reference model in the document model using several smoothing methods. Our study further extends from modelling and improving opinion detection to include an examination of the impact of different factors that influence opinion retrieval. For example, we investigate whether the SWN lexicon is adapted to the language of blogs or contains opinion words that appear in blogs. We also evaluate different language models to identify the best representation of a document or reference collection. Finally, we calculate various scores for re-ranking opinion documents. The conducted experiments validate our hypothesis on the use of opinionated collections without analysis (i.e., subjective words extraction). We also conclude that our smoothing models best represent opinionated documents and scores based on similarity using KL divergence. Our results represent a significant improvement on the obtained TREC baseline, as well as other configurations. Our future work will focus on two main points. Firstly, we will investigate a better method for modeling opinion sources. In our current approach, all the terms in the reference collection are used; it would be valuable to discover a method to boost more subjective terms. Secondly, we will extend our language model to incorporate polarity detection. More specifically, the ability to identify whether the opinion expressed in a document is positive, negative or neutral would enable us to obtain additional information on the given subject. We will also focus on the use of various document information such as date, gender, age, profile and subject category for results validation and recommendations. It may also be valuable to investigate the existence of influencing factors in order to improve opinion detection. In a discussion about makeup, for example, a likely influencing factor is gender; when discussing phones, however, the likely factor is age. Once such factors are determined, their level of confidence will need to be determined.

Fig. 1 .

 1 Fig. 1. Opinion finding approach.

Fig. 2 .

 2 Fig. 2. SentiWordNet.

  deduced from the previous study. The opinion scores considered are those obtained by the Score KL R D R _ _ ( , ) (see Table

Table 2

 2 Results of MAP and P@10 for different models to represent reference collection.

	Configuration	MAP	P@10
	with Subjectivity	0.1488	0.2896
	without Subjectivity	0.1279	0.1187
	Model(document, reference)	MAP	P@10
	(ML, DIR)	0.1231	0.1375
	(ML, JM)	0.1782	0.3646
	(ML, TS)	0.2098	0.4354

Table 3

 3 Result of MAP and P@10 for different model to represent test document.

	Model (document, reference)	MAP	P@10
	(DIR, TS)	0.2122	0.4417
	(JM, TS)	0.2260	0.4750
	(TS, TS)	0.2298	0.4875

Table 4

 4 Result of MAP and P@10 for different opinion score.

	Opinion score	MAP	P@10
	Similarity Score KL R D _ _ ( )	0.2298	0.4875
	Product Score Prod R D _ _ ( )	0.1131	0.1333
	Mixte Score Mixte R D _ _ ( )	0.1654	0.3125

Table 5

 5 Result of MAP and P@10 for product, linear and baseline4 opinion score.

	Configuration	MAP	P@10
	Product	0.3145	0.6354
	Linear	0.3453	0.6729
	Baseline 4	0.3022	0.5240

http://trec.nist.gov/data/blog08.html.

http://www.cs.cornell.edu/people/pabo/movie-review-data/.

https://github.com/cacoderquan/Sentiment-Analysis-on-the-Rotten-Tomatoes-movie-review-dataset.

http://www.cs.pitt.edu/mpqa/.

http://trec.nist.gov/pubs/trec17/papers/BLOG.OVERVIEW08.pdf.

Acknowledgement

All this work has been done at the IRIT Laboratory.