Exploiting Device Heterogeneity in Grant-Free Random Access: A Data-Driven Approach Alix Jeannerot, Malcolm Egan and Jean-Marie Gorce

Abstract-Grant-free random access (GFRA) is now a popular protocol for large-scale wireless multiple access systems in order to reduce control signaling. Resource allocation in GFRA can be viewed as a form of frame slotted ALOHA, where a ubiquitous design assumption is device homogeneity. In particular, the probability that a device seeks to transmit data is common to all devices. Recently, there has been an interest in designing frame slotted ALOHA algorithms for networks with heterogeneous activity probabilities. These works have established that the throughput can be significantly improved over the standard uniform allocation. However, the algorithms for optimizing the probability a device accesses each slot require perfect knowledge of the active devices within each frame. In practice, this assumption is limiting as device identification algorithms in GFRA rarely provide activity estimates with zero errors. In this paper, we develop a new algorithm based on stochastic gradient descent for optimizing slot allocation probabilities in the presence of activity estimation errors. Our algorithm exploits importance weighted bias mitigation for stochastic gradient estimates, which is shown to provably converge to a stationary point of the throughput optimization problem. Numerical results show significant performance improvement both over standard frame slotted ALOHA and existing algorithms that do not account for activity estimation errors.

Index Terms-Grant-Free Random Access, Slotted ALOHA, Heterogeneous Activity, Stochastic Optimization

I. INTRODUCTION

A challenge in large-scale multiple access is ensuring reliable transmissions while efficiently utilizing resources and limiting latency. One approach to this challenge in cellular systems is grant-free random access [START_REF] Shahab | Grant-free non-orthogonal multiple access for the IoT: a survey[END_REF]- [START_REF] Ding | A survey on non-orthogonal multiple access for 5G networks: research challenges and future trends[END_REF], where active devices transmit a preamble immediately followed by data transmission. In contrast with the random access channel (RACH) procedure, grant-free random access does not require a response from a base station before transmitting a data packet. As a consequence, the access delay is reduced.

While the RACH procedure provides devices with reserved resources, this is not the case for grant-free random access. As such, devices must select their own resources, such as the time slot they will use for data transmission. Contention resolution is therefore a critical problem in grant-free random access, requiring a careful selection of slots by devices in order to reduce re-transmissions.

Due to the lack of coordination in grant-free random access and limited information about the statistics of the network, slot A. Jeannerot, M. Egan, L. Chetot, and J.-M. Gorce are with Univ Lyon, Inria, INSA-Lyon, CITI, Villeurbanne, France. This work was presented in part in IEEE VTC-Spring 2023 [START_REF] Jeannerot | Mitigating user identification errors in resource optimization for grant-free random access[END_REF]. This work was funded in part by the ANR grant IADoc@UDL at the University of Lyon under grant number ANR-20-THIA-0007. selection policies are often based on variants of frame slotted ALOHA [START_REF] Roberts | ALOHA packet system with and without slots and capture[END_REF]. In the original form of frame slotted ALOHA [START_REF] Wieselthier | An exact analysis and performance evaluation of framed ALOHA with capture[END_REF], active devices randomly select a single slot within a frame in a uniform fashion. In principle, frame slotted ALOHA reduces the chance that two active devices simultaneously access the same slot.

Other variants of frame slotted ALOHA have also been proposed where devices may utilize more than one slot in a single frame including irregular repetition slotted ALOHA (IRSA) [START_REF] Liva | Graphi-based analysis and optimization of contention resolution diversity slotted ALOHA[END_REF] and coded slotted ALOHA (CSA) [START_REF] Paolini | Codes slotted ALOHA: a graphbased method for uncoordinated multiple access[END_REF]. Nevertheless, slotted ALOHA remains the de facto MAC protocol to coordinate massive access in IoT applications, such as machine-to-machine communications [START_REF] Yu | Stablizing frame slotted Aloha-based IoT systems: a geometric ergodicity perspective[END_REF], [START_REF] Yue | Age of information under frame slotted ALOHAbased status updating protocol[END_REF].

A. Related Work

A ubiquitous assumption in the design of random access protocols is that devices are homogeneous; namely, each device is active independently within a frame with a common probability. This assumption applies to the classical frame slotted ALOHA protocols [START_REF] Wieselthier | An exact analysis and performance evaluation of framed ALOHA with capture[END_REF], as well as recent work focusing on stability [START_REF] Yu | Stablizing frame slotted Aloha-based IoT systems: a geometric ergodicity perspective[END_REF] and age-of-information (AoI) minimization [START_REF] Yue | Age of information under frame slotted ALOHAbased status updating protocol[END_REF], [START_REF] Huang | Age of information minimization for frameless ALOHA in grant-free massive access[END_REF].

The homogeneity assumption is also the basis of variants of frame slotted ALOHA. In the contention resolution diversity slotted ALOHA (CRDSA) scheme [START_REF] Casini | Contention resolution diversity slotted ALOHA (CRDSA): an enhanced random access scheme for satellite access packet networks[END_REF], two identical copies of a data packet are transmitted in two different slots. Due to the repetitions, the reception of a single packet is sufficient to decode the data. The performance can be improved further by utilizing successive interference cancellation (SIC) [START_REF] Verdú | Multiuser Detection[END_REF], where successfully decoded packets can be subtracted from other slots allowing for additional packets from other devices to be decoded. The IRSA scheme [START_REF] Liva | Graphi-based analysis and optimization of contention resolution diversity slotted ALOHA[END_REF] improves upon CRDSA by allowing for additional repetitions, with the quantity selected from a probability distribution known to the base station. Decoding of data packets is achieved via message passing algorithms analogous to decoding of low-density parity-check codes (LDPC) [START_REF] Gallager | Low-density parity-check codes[END_REF]. In recent work, the impact of SIC has been investigated [START_REF] Shieh | Enhanced irregular repition slotted ALOHA under SIC limitation[END_REF] and tailored user identification algorithms [START_REF] Srivatsa | User activity detection for irregular repetition slotted ALOHA based MMTC[END_REF].

CSA [START_REF] Paolini | Codes slotted ALOHA: a graphbased method for uncoordinated multiple access[END_REF] generalizes IRSA by splitting a data block into several packets and applying a packet-level linear block code. This yields coded packets instead of repetitions as in CRDSA and IRSA. The code for each device is selected from a predefined set according to a code probability distribution. As for IRSA, decoding at the base station is achieved via message passing algorithms. Recent work has investigated code distribution design for erasure channels [START_REF] Zhang | Performance bounds of coded slotted ALOHA over erasure channels[END_REF], the impact of interference cancellation errors [START_REF] Dumas | Design of coded slotted ALOHA with interference cancellation errors[END_REF], optimization of the power distribution [START_REF] Su | NOMA-based coded slotted ALOHA for machine-type communications[END_REF], and the impact of time-dependence in packet arrivals for individual devices [START_REF] Sousa-Vieira | Study of coded ALOHA with multi-user detection under heavy-tailed and correlated arrivals[END_REF].

In practice, the homogeneity assumption may not hold, either due to heterogeneous activity probabilities or statistical dependence in the activity of multiple devices. For example, devices may be sensors that observe different phenomena and have heterogeneous activity probabilities. Sensors may also observe a common phenomena, which induces correlation in their activity.

As the homogeneity assumption is ubiquitous, a key question is whether any heterogeneity in device activities can be exploited in order to improve the performance of slotted ALOHA schemes. As frame slotted ALOHA is the basis of modern multiple access systems in the context of the IoT [START_REF] Yu | Stablizing frame slotted Aloha-based IoT systems: a geometric ergodicity perspective[END_REF], it is natural to first relax the homogeneity assumption for this family of protocols.

To this end, in [START_REF] Kalor | Random access schemes in wireless systems with correlated user activity[END_REF], a new variant of frame slotted ALOHA has been proposed in order to account for heterogeneity in the activity of devices. In this scheme, the probability that a given active device accesses each slot is optimized based on the joint probability distribution of the device activities. The main benefit of this approach is that devices with high activity probabilities or correlation can be allocated in different slots. As a consequence, the probability of contention can be significantly reduced, leading to an improved throughput.

Two key difficulties arising in the approach proposed in [START_REF] Kalor | Random access schemes in wireless systems with correlated user activity[END_REF] are: (i) obtaining knowledge of the activity distribution; and (ii) optimizing the slot allocation probabilities for each device. In [START_REF] Kalor | Random access schemes in wireless systems with correlated user activity[END_REF], these difficulties were addressed by assuming known pairwise correlations between device activities and utilizing a heuristic method to optimize the allocation probabilities based on upper and lower bounds on the expected throughput.

In [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF], the two key difficulties (i) and (ii) were addressed via a data-driven approach. In each frame, the activity of each device, rather than the probability distribution, was assumed to be known. The slot allocation probabilities were then updated frame after frame via stochastic gradient ascent. In [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF], [START_REF]Stochastic resource allocation for outage minimization in random access with correlated activation[END_REF], contention was further managed by exploiting SIC at the physical layer. The slot allocation probabilities were then chosen that maximize the expected sum-rate or the expected number of devices with a signal-to-interference and noise ratio (SINR) exceeding a desired threshold.

B. Main Contributions

The schemes in [START_REF] Kalor | Random access schemes in wireless systems with correlated user activity[END_REF]- [START_REF]Stochastic resource allocation for outage minimization in random access with correlated activation[END_REF] were shown to significantly improve the performance compared with the standard frame slotted ALOHA scheme by exploiting heterogeneity in the distribution of the device activities. However, it was assumed that either the probability distribution of device activities or the device activity in each frame is perfectly known.

In practice, preamble detection and packet decoding is rarely error-free in large-scale multiple access systems [START_REF] Ke | Compressive sensingbased adaptive active user detection and channel estimation: massive access meets massive MIMO[END_REF], [START_REF] Zou | Message passing based joint channel and user activity estimation for uplink grant-free massive MIMO systems with low-precision ADCs[END_REF], even when device heterogeneity is accounted for [START_REF] Chetot | Joint identification and channel estimation for fault detection in industrial IoT with correlated sensors[END_REF], [START_REF]Active user detection and channel estimation for grant-free random access with Gaussian correlated activity[END_REF]. Moreover, the impact of imperfect knowledge of device activities in each frame affects system performance is poorly understood, as well as how to mitigate the impact of activity estimation errors on the optimization of slot allocation probabilities.

In this paper, we propose a throughput maximization algorithm to optimize slot allocation probabilities in frame slotted ALOHA accounting for imperfect knowledge of device activities. Our main contributions are as follows:

(i) We demonstrate that the algorithms recently proposed in [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF], [START_REF]Stochastic resource allocation for outage minimization in random access with correlated activation[END_REF] can be highly sensitive to activity estimation errors, leading to a suboptimal throughput. This is significant as, in the absence of activity estimation errors, these algorithms achieve a high performance in the absence of errors. Moreover, we show that the suboptimality arises from bias in gradient estimates due to estimation errors. (ii) To mitigate the impact of the bias arising from activity estimation errors, we exploit importance weighting in a manner analogous to sample bias correction [START_REF] Zadrozny | Learning and evaluating classifiers under sample selection bias[END_REF] and bias reduction in private synthetic data [START_REF] Ghalebikesabi | Mitigating statistical bias within differentially private synthetic data[END_REF]. We prove that by weighting the gradient estimates in the stochastic optimization algorithm in [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF], [START_REF]Stochastic resource allocation for outage minimization in random access with correlated activation[END_REF], the slot allocation probabilities converge to a stationary point with probability one. (iii) In practice, the weight on the gradient estimates requires the evaluation of the true activity distribution and the imperfect activity distribution induced by erroneous activity estimation. As these distributions may be difficult to obtain, we propose heuristic weights that are readily available in practical systems, leading to new stochastic optimization algorithms for the slot allocation probabilities. (iv) The proposed algorithms are validated by an extensive numerical study under different type of errors. Several models of activity estimation errors are considered, including independent and symmetric or asymmetric errors and a realistic error model based on generalized approximate message passing (GAMP) [START_REF] Chetot | Joint identification and channel estimation for fault detection in industrial IoT with correlated sensors[END_REF] arising in pilotbased device identification. Under each model for activity estimation errors, numerical results show that our algorithm is robust to activity estimation errors. Moreover, our algorithm leads to performance improvements over the algorithms in [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF], [START_REF]Stochastic resource allocation for outage minimization in random access with correlated activation[END_REF], which do not account for activity estimation errors.

C. Organization of the Paper

The paper is organised as follows. In Section II we detail the system model. In Section III, we recall the stochastic resource optimization algorithm in [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF], [START_REF]Stochastic resource allocation for outage minimization in random access with correlated activation[END_REF], which does not account for activity estimation errors. In Section IV, we study the impact of activity estimation errors and develop a new stochastic resource optimization algorithm to mitigate the errors. In Section V, we present a numerical study comparing our new algorithm with existing methods that do not account for activity estimation errors. In Section VI, we conclude.

II. SYSTEM MODEL

Consider a network consisting of an access point (AP) equipped with N A antennas and N devices equipped with a single antenna. As in common cellular standards (e.g., NB-IoT [START_REF] Hoglund | Overview of 3GPP release 14 enhanced NB-IoT[END_REF] or NR-REDCAP [START_REF] Veedu | Toward smaller and lower-cost 5G devices with longer battery life: an overview of 3GPP release 17 Redcap[END_REF]), transmissions by active devices occur in frames via orthogonal frequency division multiplexing (OFDM). Each frame consists of R time-frequency resources, where a single time-frequency resource corresponds to R T time slots and one or more subcarriers. In NB-IoT, one subcarrier is typically utilized per time-frequency resource [START_REF] Hoglund | Overview of 3GPP release 14 enhanced NB-IoT[END_REF], which will be assumed in the remainder of this paper. We refer to a group of R T time slots for a single subcarrier, corresponding to a single time-frequency resource, as a time resource. We assume there are M time resources for each subcarrier.

A. Device Activity and Resource Selection

Within a given frame, each of the N devices are either active or inactive. The activity of device i in frame t is represented by the binary Bernoulli distributed random variable

X t i ∼ Ber(p i ). That is, X t i ∈ {0, 1} with X t i = 1
if device i is active and X t i = 0 otherwise. The activity vector in frame t is then denoted by X t ∈ {0, 1} N and we write p = [p 1 , . . . , p N ] T . We make the following assumptions for X t , t = 1, 2, . . .:

(i) X t i is independent of X t j , j ̸ = i. (ii) X t is independent of X t ′ , t ′ ̸ = t, t ∈ N.
(iii) p is not perfectly known to the access point.

In grant-free random access, each active device select the time-frequency resources utilized for data transmission without coordinating with the access point nor any other devices. In the absence of any coordination, a common policy for resource selection is the classical frame slotted ALOHA protocol [START_REF] Wieselthier | An exact analysis and performance evaluation of framed ALOHA with capture[END_REF]. In this case, devices select time-frequency resources uniformly at random. A more general policy that has recently been considered in [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF], [START_REF]Stochastic resource allocation for outage minimization in random access with correlated activation[END_REF] allows devices to select resources with different probabilities. In this policy, the probability device i selects each resource is given in the i-th row of the matrix A ∈ R N ×M + . That is, the elements of the matrix A are defined by

A ik = Pr(device i selects resource k|X i = 1) (1)
As such, A ∈ R N ×M + and K k=1 A ik = 1, i = 1, . . . , N , which ensures that each active device transmits using exactly one resource per frame.

B. Grant-Free Random Access Protocols and Device Identification

A generic resource selection and data transmission protocol using a pilot-based identification is given in Alg. 1. Specific protocols vary in how device identification information is communicated to the access point. In the sequel, device identification is critical for optimization of frame slotted ALOHA with heterogeneous device activity distributions. We consider two types of protocols where device identification information is included within the preamble or in the data packet.

1) Device Identification in the Preamble: A common strategy in grant-free random access is to assign each device i with a unique preamble of length T , s i ∈ C T . In each frame, the preamble of each active device is then transmitted over the Algorithm 1: Grant-Free Random Access Protocol

Y t = SH t + W t , (2)
where S = [s 1 , . . . , s N ] is the matrix of preambles, H t ∈ C N ×N A is the matrix of channel coefficients for all devices and AP antennas, and

W t ∈ C T ×N A is additive white Gaussian noise.
Given the control channel output Y t , the channel coefficients H t and the activities X t of the devices can be estimated. This is typically achieved via approximate message passing algorithms such as the generalized approximate message passing (GAMP) algorithm in [START_REF] Chetot | Joint identification and channel estimation for fault detection in industrial IoT with correlated sensors[END_REF]. Active devices then transmit their data by randomly selecting a data slot based on the allocation matrix A. Data decoding is carried out by exploiting the estimate of the channels Ĥt obtained from the approximate message passing algorithm. As the active devices have been identified from the preambles, it is not necessary to include this information within the data packet.

2) Device Identification in the Data: An alternative approach is to utilize the preambles only for the purpose of channel estimation. In this case, the protocol proceeds in the same fashion as in Sec. II-B1; however, the control channel output Y t is only used to estimate the channel coefficients, Ĥt , of the active users.

As in Sec. II-B1, active devices then transmit their data by randomly selecting a data slot based on the allocation matrix A. The key difference is that data decoding reveals both the data of the active devices and also their identification. As a consequence, the activity estimate Xt is only obtained after data decoding.

C. Feedback of the Allocation Matrix A

The grant-free random access protocol in Alg. 1 does not require a multi-step handshake procedure as is the case for the RACH procedure. However, it is necessary to inform devices of the allocation matrix A in order to select the resource to be used in each frame. We assume that the activity statistics of the devices typically do not change significantly over a large number of frames. As a consequence, it is only necessary to communicate the matrix A to the devices every F frames, where the choice F accounts for downlink usage constraints.

On the other hand, the AP obtains new information about the activity of each device every frame. This information can be utilized to update the matrix A every frame at the AP, as is discussed in the following section. We emphasize that the AP does not communicate the updated allocation matrix every frame.

III. STOCHASTIC RESOURCE ALLOCATION PROBLEM

The stochastic resource allocation protocol described in Alg. 1 is common in frame slotted ALOHA systems and their variants. For example, in the simplest form of ALOHA, an equal probability is assigned to each time slot for all devices. In IRSA and CSA, the slot or code allocation is also randomized [START_REF] Liva | Graphi-based analysis and optimization of contention resolution diversity slotted ALOHA[END_REF], [START_REF] Paolini | Codes slotted ALOHA: a graphbased method for uncoordinated multiple access[END_REF]. However, these protocols have been designed under the assumption of an equal activity probability for all devices.

In this section, we formalize the problem of stochastic resource allocation in frame slotted ALOHA for devices with heterogeneous activity probabilities. We present an algorithm based on [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF] to optimize the allocation under the assumption of perfect knowledge of the activities X t for the throughput objective. A new algorithm to mitigate the impact of imperfect knowledge of X t due to preamble detection or data decoding errors is developed in Sec. IV.

A. Objective

In frame slotted ALOHA, a key performance metric is the expected number of collision-free transmissions in each frame, often known in this context as the throughput. Given an allocation matrix A and activity vector X, the instantaneous throughput for device i is given by

T i (A; X) = K k=1 X i A ik N m=1 m̸ =i (1 -X m A mk ), (3)
and the total instantaneous throughput by

T X (A) = N i=1 T i (A; X). (4)
After averaging over the activity vector X, the throughput is then

T (A) = E X [T X (A)]. (5)
In the case that the activity of each device is independent, the throughput is simplified as

T (A) = N i=1 K k=1 p i A ik N m=1 m̸ =i (1 -p m A mk ). (6)
In order to compare the performance of the algorithms in scenarios with different activity probability, we define the normalized throughput as

T N (A) = 1 N i=1 p i T (A).

B. Stochastic Optimization Problem

An optimal allocation A * is a solution to the stochastic optimization problem

A * ∈ arg max A∈R N ×K + : K k=1 A ik =1, i=1,...,N T (A). (7)
In general, the objective T (A) is non-convex in A. Moreover, solutions A * may often admit non-binary binary solutions, particularly when p i < 1 2 , i = 1, . . . , N . If the distribution P X is known to the AP, it is in principle possible to obtain solutions to [START_REF] Wieselthier | An exact analysis and performance evaluation of framed ALOHA with capture[END_REF] via gradient descent. However, this approach has a very high complexity due to the fact that the throughput has 2 N terms. Indeed,

T (A) = x∈{0,1} N Pr(X = x)T X (A). (8)
In practice, only limited knowledge of P X is available as it must be estimated based on the activity estimates Xt obtained from the preamble or data decoding. An alternative approach is to directly utilize the activity estimates Xt to solve the allocation problem in [START_REF] Wieselthier | An exact analysis and performance evaluation of framed ALOHA with capture[END_REF]. As observed in [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF], this can be achieved via projected stochastic gradient ascent.

Suppose, for the moment, that the activity vectors X 1 , X 2 , . . . for each frame are perfectly known to the AP. The projected stochastic gradient ascent algorithm (summarized in Alg. 2) updates the allocation matrix A each frame via the recursion

A t+1 = Π H A t + γ t+1 g(A t ; X t+1 ) , (9)
where (ϵ t ) is a positive step size sequence, Π H denotes the Euclidean projection on the constraint set

H = {A ∈ R N ×K + : K k=1 A ik = 1, i = 1, . . . , N }, (10)
and g(A t ; X t+1 ) is a stochastic gradient estimate based on the activity vector X t+1 . In particular, the gradient estimate for the throughput objective is given by (the superscript t is dropped for the shake of clarity).

g(A; X) = N n=1 g n (A; X), (11)
g(A; X) ql = N n=1 g n (A; X) ql = X q N m=1 m̸ =q (1 -X m A ml ) - N n=1 n̸ =q X q X n A nl N m=1 m̸ =n m̸ =q (1 -X m A ml ) (12)
where

g n (A; X) ql =      X q N m=1 m̸ =q (1 -X m A ml ) if q = n -X q X n A nl N m=1 m̸ =n m̸ =q (1 -X m A ml ) if q ̸ = n
Note that in this case, g(A; X) ∈ R N ×K is an unbiased estimate of ∇T (A) = E X [g(A; X)] due to the absence of user identification errors. As such, under appropriate conditions on the step size sequence {γ t } and perfect knowledge of X 1 , X 2 , . . ., the iterates {A t } converge almost surely to a stationary point of T (•) [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF].

Algorithm 2: Stochastic optimization algorithm when user identification is error-free.

1 Choose initial allocation matrix

A 1 ∈ R N ×K such that K k=1 A 1 n,k = 1, n = 1, . . . ,
(A t ; X t+1 ) of ∇ A t T (A t ) 5 A t+1 ← Π H [A t + γ t+1 g(A t ; X t+1 )] 6 t ← t + 1 7 end
In practice, however, perfect knowledge of X 1 , X 2 , . . . is not available to the AP due to errors in device identification. As we discuss in the following section, this can lead to a significant degradation in performance.

IV. MITIGATING ERRORS IN ACTIVITY ESTIMATION A. Impact of Activity Estimation Error

As noted in the previous section, perfect knowledge of device activities X 1 , X 2 , . . . is not available to the AP. A key question is then the impact on the performance of Alg. 2. In fact, errors in the activity estimates can lead to a significant performance degradation, even in small networks as illustrated in the following example.

Example 1. Consider a network consisting of 3 devices sharing two time slots. The true activity probabilities of the devices are p = 0.3 0.4 0.9 . Suppose that the user identification algorithm is not always able to distinguish between the first and last users. In particular, with probability ϵ, the estimated user activity vector available to the AP is in fact governed by p = 0.9 0.4 0.3 . The observed distribution is thus

p ′ = ϵp + (1 -ϵ)p
Fig. 1 shows the impact of ϵ on the network throughput T (A) after optimizing A with Alg. 2 for 500 frames. The throughput of standard frame slotted ALOHA is also plotted, where every element of the allocation matrix A is 1 2 ). The case ϵ = 0 corresponds to the case of perfect user identification and ϵ = 1 to the case where the activity vector is always drawn from p.

Observe that as ϵ increases (corresponding to a higher probability of errors in the estimation of X), the throughput significantly decreases compared with the baseline where X has been perfectly estimated. If the average number of errors is too large, then the resulting throughput is worse than ALOHA.

B. Unbiasing Gradient Estimates

In order to develop an algorithm to mitigate the impact of user identification errors, we first examine the impact of the errors on the SGA algorithm in Alg. 2. To this end, consider the update rule

A t+1 = Π A t + γ t+1 g(A t ; Xt+1 ) = A t + γ t+1 g(A t ; Xt+1 ) + γ t+1 Z t+1 , (13)
where γ t+1 Z t+1 is the smallest vector (w.r.t the Euclidean norm) needed to project A t + γ t+1 g(A t ; X t+1 ) into the constraint set H. We then have

A t+1 = A t + γ t+1 E X [g(A t ; Xt+1 )] + β t+1 + ∂M t+1 + γ t+1 Z t+1 , (14)
where

β t+1 = E X[g(A t ; Xt+1 )] -E X [g(A t ; X t+1 )] ∂M t+1 = g(A t ; Xt+1 ) -β t+1 -E X [g(A t ; X t+1 )]. (15)
Note that E X[∂M t+1 ] = 0.

In the case that there are no user identification errors, β t+1 = 0, g(A t ; X t+1 ) is an unbiased estimate of the gradient. Moreover, Alg. 2 is guaranteed to converge to a stationary point under the hypotheses in Theorem 5.2.10 of [START_REF] Kushner | Stochastic Approximation and Recursive Algorithms and Applications[END_REF]. However, when β t+1 ̸ = 0, the gradient estimate is biased. As a consequence, there is no guarantee of convergence, even to a stationary point. The resulting performance reduction is illustrated in Fig. 1.

C. Proposed Algorithm

As the cause of the performance reduction is due to biased gradient estimates, it is necessary to utilize a bias reduction method. Bias reduction algorithms have been exploited in various machine learning problems; e.g., sample selection bias correction [START_REF] Zadrozny | Learning and evaluating classifiers under sample selection bias[END_REF] and privacy [START_REF] Ghalebikesabi | Mitigating statistical bias within differentially private synthetic data[END_REF]. We now adapt these methods to our problem.

Consider the weighting function w : x → w(x) for x ∈ {0, 1} consisting of the ratio between a target distribution and a proposal distribution, it is defined by

w(x) = Pr(X = x) Pr( X = x) , ( 16
)
where X is the true activity vector and X is the estimated activity vector. Suppose that w(x) < ∞, x ∈ {0, 1} N where we adopt the convention that 0 0 = 0. For the purposes of bias reduction, a key property of w(x) is then that for all A ∈ H,

E X [g(A; X)] = x∈{0,1} N g(A; x)Pr(X = x) = x∈{0,1} N g(A; x)w(x)Pr( X = x) = E X[w( X)g(A; X)]. (17)
In other words, w( X)g(A; X) is an unbiased estimate of E X [g(A; X)] as long as w(x) < ∞ for all x such that Pr(X = x) > 0. As such, as we rigorously establish in Theorem 1, this choice of weight overcomes the key problem preventing convergence of Alg. 2.

Algorithm 3: Stochastic optimization algorithm with user identification errors

1 Choose initial allocation matrix A 1 ∈ R N ×K such that K k=1 A 1 n,k = 1, n = 1, . . . ,
(i) γ t > 0, t > 0; (ii) ∞ t=1 γ t = ∞; (iii) ∞ t=1 (γ t ) 2 < ∞, and w(x) < ∞ for all x ∈ {0, 1} N .
Proof. See Appendix A.

D. Computing the Importance Weight

Theorem 1 shows that even when there are errors in X, Alg. 3 converges to a stationary point for the problems in [START_REF] Wieselthier | An exact analysis and performance evaluation of framed ALOHA with capture[END_REF]. This is in contrast to the standard SGA algorithm in Alg. 2, for which these guarantees hold only when there are no errors.

However, the implementation of Alg. 3 requires knowledge of both p and p in order to compute the weight w(x) in [START_REF] Shieh | Enhanced irregular repition slotted ALOHA under SIC limitation[END_REF].

In practice, the AP does not have perfect knowledge of p nor p. Nevertheless, estimates can be obtained as follows:

(i) Estimation of the target distribution p: In principle the true activity distribution can be estimated from channel outputs Y t and the input-output relation in [START_REF] Shahab | Grant-free non-orthogonal multiple access for the IoT: a survey[END_REF]. Typically, this is achieved via expectation-maximization algorithms exploiting the posterior distributions obtained from the GAMP algorithm for user identification and channel estimation [START_REF] Vila | Expectation-maximization Gaussian-mixture approximate message passing[END_REF]. We model the resulting estimated distribution, accounting for errors, by adding a Gaussian perturbation to the true distribution, p = p + η, with η ∼ N (0, σ 2 I), where p is clipped, if needed, to be between 0 and 1. We denote X ∼ Ber(p) and w(x) = Pr( X=x) Pr( X=x) estimated importance weight. (ii) Estimation of the proposal distribution p: The estimation of p can be achieved by empirical distribution estimation via the outputs of the user identification algorithm (e.g., GAMP). As a consequence, the weight w(x) in ( 16) is not perfectly known in practical systems. Nevertheless, as we show in the following section, an imperfect estimate of the weight w(x) still yields improved performance over Alg. 2, which ignored the impact of user identification errors. Moreover, if Pr( X = x) is close to 0, w(x) will be very large. This mean that the optimization algorithm can take very large steps, pushing the optimization towards undesired local maxima. To increase the stability of the algorithm, we clip the weight to a maximal value of κ > 0. The optimization algorithm used in V is as follows:

Algorithm 4: Stochastic optimization algorithm with user identification errors, approximate target distribution and weight clipping.

1 Choose initial allocation matrix A 1 ∈ R N ×K such that K k=1 A 1 n,k = 1, n = 1, .
. . , N , clipping parameter κ > 0, and step-size sequence {γ t } with γ t > 0, t = 1, 2, . . .

2 t ← 1. 3 while not converged do 4 Based on the estimate Xt+1 , compute a biased estimate g(A t ; Xt+1 ) of ∇ A t T (A t ) 5 w( Xt+1 ) = min κ, Pr( X=x) Pr( X=x) 6 A t+1 = Π H [A t + γ t+1 w( Xt+1 )g(A t ; Xt+1 )] 7 t ← t + 1 8 end

V. NUMERICAL RESULTS

A. Parameters and Baseline Methods

To support our theoretical analysis, we provide simulation results for different type of errors introduced by the user detection algorithms. We compare the throughput given by several methods:

• Optimization of A using Alg. 2 with perfect detection of users, as baseline, where the true activity vector X is known,

• Optimization of A using Alg. 2 with imperfect user detection representing the optimization obtained when using the error prone activity vector X, • Optimization of A using Alg. 4 with true weight w for Fig. 2 and Fig. 4 (with true target p empirically estimated proposal p for Fig. 5) • Optimization of A using Alg. 4 with an imperfect weight due to a target distribution p that is known up to a Gaussian perturbation of different standard deviations σ, • A greedy allocation A h obtained via Alg. 5: the users that are the most likely to transmit are allocated their own slot, while all the others users share a single slot.

Algorithm 5: Construction of greedy allocation matrix

A h 1 Given a sorted vector of activity probabilities p in the network and K slots

2 k ← 1 3 A ← 0 N ×K 4 for i ← 1; i ≤ N -K; i ← i + 1 do 5 A i,1 ← 1 6 end 7 for k ← 2; k ≤ K; k ← k + 1 do 8 A N -k+1,k ← 1 9 end
• The Frame Slotted ALOHA allocation, a constant matrix having A ik = 1 K as elements, • A 0 representing the initial random matrix that was used. In the following figures, we plot the normalized throughput, corresponding to the expected throughput per frame of the optimized matrix A for a given network of N users with activity probability p i . It should be noted that this policy is implemented for a large number of frames and thus a small difference in the per-frame throughput can lead to significant differences in the number of successfully decoded packets over long time periods. We test our method on two different models of user detection (with symmetric and asymmetric errors) and with an active user detection algorithm based on GAMP [START_REF] Rangan | Generalized approximate message passing for estimation with random linear mixing[END_REF]. For any type of user detection algorithms, the choice of the initial matrix A 0 is difficult; the problem ( 7) is non-convex and typically has local maxima with poor performance. As the diameter of the constraint set H is large, a badly chosen initial matrix might lead to poorly performing local maxima. To overcome this issue we assume that the access point can compute the network throughput for a given matrix. As such, the AP can keep track of several initial matrices and choose to send in the downlink the best one. For our simulations, 14 initial matrices A 0 are drawn uniformly at random in H. The simulated networks consists in N = 20 users and K = 5 slots. The activity of the devices is drawn once from a uniform distribution between 0 and 0.45 (for Section V-B) or 1 (for Sections V-C and V-D). Each method is simulated using the same random sequence of activity vectors and we repeat the simulations 20 times, allowing to isolate the effect of the detection errors on the resulting allocation. For the weight w in Alg. 4, a new target distribution p is drawn for each run according to the description in IV-D. The step size in the different algorithms is set constant across all simulation and type of channels γ t = 1 50 . In our following figures, the shaded area represent ± the standard deviation.

B. Symmetric Errors

Consider a detection algorithm where the false alarm and miss-detection probabilities for each device are equal and given to p flip ∈ [0, 0.5]. In other words, if device i is active, the probability it is not detected is p flip . Similarly, if device i is not active, it is detected with probability p flip . In this case,

pi = p i + p flip -2p flip p i , i = 1, . . . , N. (18)
Fig. 2 shows the impact of the error probability p flip on the Observe in Fig. 2 that A h (in orange) has the worst performance. This is due to the fact that the activity probabilities are low and allocating only a single device to a slot is inefficient. For small values of p flip the random initial allocation A 0 and the ALOHA allocation A ALOHA are poorly performing. This is due to the fact that neither account for the throughput objective in (3). However, for higher values of errors (p flip ≥ 0.4), the steps taken by the algorithms are lead to a poor solution. The yellow curve corresponds to Alg. 2 with perfect user activity estimation. For small and large values of p flip , the yellow curve is higher than any of the curves corresponding to proposed Alg. 3 and Alg. 2 with user identification errors. In particular, observe that applying Alg. 2 ignoring user identification errors (blue curve) leads to significant degradation in the throughput. The proposed Alg. 3 with perfect knowledge of the weight in ( 16) (orange curve) and with imperfect weight (green, red, purple, brown and pink) always outperforms Alg. 2 with identification errors when p flip ≥ 0.1. This highlights the utility of our proposed algorithm as it mitigates the effect of user identification errors. Fig. 3 shows the trajectories for each method for p flip = 0.15.

We can see that the Alg. 3 tend to converge faster. This explains why Alg. 3 with a perfect weight slightly outperforms Alg. 2 with perfect activity estimates (yellow curve), for moderate values of p flip . The green, red, purple, and brown curves correspond to the proposed Alg. 3 with imperfect knowledge of the weight, obtained by perturbing the true weight by Gaussian noise. As the standard deviation of the noise increases, the throughput performance degrades. This is due to the fact that the noise introduces bias in the gradient estimates. Nevertheless, Alg. 3 with weights corrupted by noise still outperforms Alg. 2 (blue curve), which does not account for user identification errors.

C. Asymmetric Errors

We now consider a detection algorithm that has Pr(false alarm) = 0 and Pr(miss detection) = p miss for p miss ∈ [0, 0.5] common to each device. In other words, if device i is active, the probability that it is not detected is p miss . In contrast to the scenario of Fig. 2, if device i is not active, then the probability of it being detected is zero.

pi = p miss p i , i = 1, . . . , N. (19)
Fig. 4 shows the impact of the error probability p miss on the throughput achieved by each algorithm. The optimization is run for 1500 frames of the algorithms. The activity probability of each device i, p i , is drawn independently from the uniform distribution Unif[0, 1]. That is, there is a high probability that many devices will have an activity probability p i > 1 2 . Observe in Fig. 4, the initial random allocation A 0 and the ALOHA allocation A ALOHA have the worst performance. Due to the high heterogeneity of the network, the gap between A ALOHA and the best performing method is larger than in the previous scenario. In this case, as some users have a probability of activity p i > 0.5, the greedy heuristic (in For small and large values of p miss , the yellow curve is higher than any of the curves corresponding to proposed Alg. 3 and Alg. 2 with user identification errors. In particular, observe that, as for the symmetric errors, applying Alg. 2 while ignoring user identification errors (blue curve) leads to significant degradation in the throughput. Alg. 3 with perfect knowledge of the weight in [START_REF] Shieh | Enhanced irregular repition slotted ALOHA under SIC limitation[END_REF] to mitigate user identification errors (orange curve) always outperforms Alg. 2.

Similarly to the case with symmetric errors, Alg. 3 with perfect knowledge of the weight in [START_REF] Shieh | Enhanced irregular repition slotted ALOHA under SIC limitation[END_REF] to mitigate user identification errors (orange curve) always outperforms Alg. 2. Again, the green, red, purple, and brown curves show that the throughput degrades when the standard deviation of the prior increase but they still outperform Alg. 2 (blue curve), which does not account for user identification errors.

D. Errors Arising from GAMP-Based Detection

Finally, we consider the use of an active user detection algorithm based on GAMP [START_REF] Rangan | Generalized approximate message passing for estimation with random linear mixing[END_REF]. As described in Section II-B1, each user i is given a unique complex preamble (or pilot) s i of length T = 10 with s i,j ∼ CN (0, 1), for j = 1 . . . 10. Pilots are sent with a unit transmit power and are received by a single antenna (i.e., N A = 1 in this scenario). For each channel use, the channel coefficient h i of each user i is randomly chosen according to a complex normal distribution: h i ∼ CN (0, 1). Due to the presence of additive Gaussian noise, errors are introduced at the output of the active user detector. As the posterior distribution p of GAMP is difficult to compute it is estimated using a Monte Carlo approximation by running the network for 6000 frames and this estimation is used as the denominator of the importance weight. Fig. 5 shows the effect of the additive Gaussian noise on the throughput of the resulting allocation given by each algorithm. The algorithms are run for 4000 frames. The activity probability of each device i, p i , is drawn independently from the uniform distribution Unif[0, 1]. In Fig. 5, as for the asymmetric errors, the random initial allocation A 0 and the ALOHA allocation A ALOHA have the worst performance. In this case, the greedy heuristic (in orange, dashed line) performs the best as some users have a probability of activity p i > 0.5. For small and large values of SNR the yellow curve representing the weight made of the true target and the empirical distribution estimation is above the curves of the algorithm of Alg. 3. For high values of SNR, almost no errors are introduced by the GAMP algorithm. Hence all algorithms achieve a similar throughput. For smaller values of SNR (≤ -2), the Alg. 2 with imperfect detection (blue curve) has degraded performance. Note that the proposed Alg. 4 (green, red, purple, and brown curves) outperform Alg. 2 (blue curve).

VI. CONCLUSIONS

A problem arising in the design of frame slotted ALOHA algorithms with heterogeneous devices is the need for perfect activity estimates in each frame. In this paper, we have studied the impact of imperfect activity estimation and observed a significant throughput performance degradation in existing algorithms. To overcome this problem, we have proposed an importance weighted bias mitigation strategy. This algorithm is shown to be capable of guaranteeing almost sure convergence of stochastic gradient methods to a stationary point of the throughput maximization problem. A numerical study shows that our method outperforms existing algorithms which do not account for imperfect activity estimation. Moreover, our approach is robust to uncertainty in the importance weights.

APPENDIX A PROOF OF THEOREM 1

Observe that the update rule can be written as A t+1 = A t + γ t+1 E Xt+1 [w( Xt+1 )g(A t ; Xt+1 )] w( Xt+1 )g(A t ; Xt+1 ) -E Xt+1 [w( Xt+1 )g(A t ; Xt+1 )]

+ γ t+1 Z t+1 = A t + γ t+1 E X t+1 [g(A t ; X t+1 )] + ∂ Mt+1 + γ t+1 Z t+1 = A t+1 + γ t+1 ∇ A T (A t ) + ∂ Mt+1 + γ t+1 Z t+1 , (20)
where

∂ Mt+1 = w( Xt+1 )g(A t ; Xt+1 ) -E Xt+1 [w( Xt+1 )g(A t ; Xt+1 )] (21)
satisfies E t+1 [∂ Mt+1 ] = 0, where E t+1 [•] is the conditional expectation on with respect to the σ-algebra generated by the iterates up to time t. The last equality then follows from the identity in [START_REF] Srivatsa | User activity detection for irregular repetition slotted ALOHA based MMTC[END_REF].

To establish convergence, we apply Theorem 5.2.1 in [START_REF] Kushner | Stochastic Approximation and Recursive Algorithms and Applications[END_REF]. To do so, we verify the following conditions:

• A.5.2.1:

sup t E Xt+1 [w( Xt+1 )g(A t ; Xt+1 )] < ∞, (22)
which holds under the assumption that w(x) < ∞ for all x ∈ {0, 1} N . • A.5.2.2: There exists g : R N ×M → R such that E Xt+1 [w( Xt+1 )g(A t ; Xt+1 )] = g(A t ), [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF] which holds by setting g(A t ) = ∇ A T (A t ). • A.5.2.3: ∇ A T (A) is continuous, which immediately follows from the definition of T (A). • A.5.2.5: The gradient estimate w( Xt+1 )g(A t ; Xt+1 ) is unbiased, which follows from [START_REF] Srivatsa | User activity detection for irregular repetition slotted ALOHA based MMTC[END_REF]. A further condition on the constraint must also hold. As the same constraint is present in [START_REF] Zheng | Stochastic resource optimization of random access for transmitters with correlated activation[END_REF] for the case without errors, the same argument can be applied to complete the proof.

Fig. 1 .

 1 Fig. 1. Expected throughput with user identification errors for a network of 3 devices sharing two slots. Baseline, in blue, corresponds to ϵ = 0. Drawing samples Xt with probability ϵ from p instead of p (in orange) can reduce the throughput by up to 35%.

Fig. 2 .

 2 Fig. 2. Resulting throughput after 2000 frames for different values of p flip throughput achieved by each algorithm. The algorithms are run for 2000 iterations (i.e., frames) and the activity probability of each device i, p i , is drawn independently from the uniform distribution Unif[0, 0.45].Observe in Fig.2that A h (in orange) has the worst performance. This is due to the fact that the activity probabilities are low and allocating only a single device to a slot is inefficient. For small values of p flip the random initial allocation A 0 and the ALOHA allocation A ALOHA are poorly performing. This is due to the fact that neither account for the throughput objective in (3). However, for higher values of errors (p flip ≥ 0.4), the steps taken by the algorithms are lead to a poor solution. The yellow curve corresponds to Alg. 2 with perfect user activity estimation. For small and large values of p flip , the yellow curve is higher than any of the curves corresponding to proposed Alg. 3 and Alg. 2 with user identification errors. In particular, observe that applying Alg. 2 ignoring user identification errors (blue curve) leads to significant degradation in the throughput. The proposed Alg. 3 with perfect knowledge of the weight in (16) (orange curve) and with imperfect weight (green, red, purple, brown and pink) always outperforms Alg. 2 with identification errors

Fig. 3 .

 3 Fig. 3. Trajectories of the different method presented in Fig. 2 with p flip = 0.15

Fig. 4 .

 4 Fig. 4. Resulting throughput after 1500 frames for different values of p miss

Fig. 5 .

 5 Fig. 5. Resulting throughput after 4000 frames for different values of SNR. Shaded area represent ± standard deviation

  Downlink) Sync signal sent by the AP to indicate beginning of the first frame and inform devices about the allocation matrix A. 2 while True do 3 (Uplink) Each active device i sends their preamble s i on a common control channel. channel consisting of T symbols. The output of the control channel in frame t, Y t ∈ C T ×N A , is given by

	6	(Local at AP) AP decodes data present in each slot
			k.
	7	(Local at devices) Wait for beginning of next
	8 end	frame.
	block fading control

1 (

4 (Local at devices) Each active device i randomly selects the slot k i with probability A ik .

5

(Uplink) Each active device i sends their data on the drawn slot k i .

  N , and step-size sequence {γ t } with γ t > 0, t = 1, 2, . . . Based on X t+1 , compute an unbiased estimate g

2 t ← 1. 3 while not converged do 4

  N , and step-size sequence {γ t } with γ t > 0, t = 1, 2, . . . The iterates A t of Alg. 3 converge almost surely as t → ∞ to a stationary point provided that the step size sequence {γ t } satisfies

	6 7 end t ← t + 1
	Incorporating the weight w(x) in (16) into Alg. 2 leads
	to Alg. 3. This algorithm has the following convergence
	guarantee.
	Theorem 1.

2 t ← 1. 3 while not converged do 4 Based on the estimate Xt+1 , compute a biased estimate g(A t ; Xt+1 ) of ∇ A t T (A t ) 5 A t+1 = Π H [A t + γ t+1 w( Xt+1 )g(A t ; Xt+1 )]


Benoît Sagot
email: benoit.sagot@inria.fr

Lionel Clément
email: lionel.clement@labri.fr

Villemonte Éric

La De

Clergerie

Pierre Boullier
email: pierre.boullier@inria.fr

The Lefff 2 syntactic lexicon for French: architecture, acquisition, use

In this paper, we introduce a new lexical resource for French which is freely available as the second version of the Lefff (Lexique des formes fléchies du franc ¸ais -Lexicon of French inflected forms). It is a wide-coverage morphosyntactic and syntactic lexicon, whose architecture relies on properties inheritance, which makes it more compact and more easily maintainable and allows to describe lexical entries independantly from the formalisms it is used for. For these two reasons, we define it as a meta-lexicon. We describe its architecture, several automatic or semi-automatic approaches we use to acquire, correct and/or enrich such a lexicon, as well as the way it is used both with an LFG parser and with a TAG parser based on a meta-grammar, so as to build two large-coverage parsers for French. The web site of the Lefff is http://www.lefff.net/.

Introduction

Precision and recall of a natural language processing chain is influenced not only by the grammar. Other components, including the pre-syntactic processing and the parser generator, play a major role. However, by its importance at all levels, the lexicon is particularly important.

But a large-coverage lexicon is a very rich and very large set of highly structured information. Moreover, it describes linguistic properties of linguistic items. Hence, a linguistically justified and operationally efficient structuration is required. Moreover, appropriate acquisition, supplementation and correction methods are needed, that have to be as automatic as possible.

In this paper, we introduce a new syntactic lexicon for French that satisfies these criteria. In particular, it relies on an original properties inheritance model. This lexicon, the Lefff 2 (Lexique des formes fléchies du franc ¸ais 1 ), partly originates in the morphological lexicon of French verbs, the Lefff 1, whose automatic acquisition has been presented in [START_REF] Clément | Morphology Based Automatic Acquisition of Largecoverage Lexica[END_REF].

Architecture

The Lefff 2 is described in an intentional way that allows for factorization of information, thanks to a hierarchical inheritance structure. The intentional lexicon is a lexicon of lemmas, whereas the extensional lexicon is a lexicon of inflected forms. In order to describe this architecture, we will describe the process of compilation from this intentional form to the extensional form used by parsers, summed up in Figure 1.

This compilation process can be divided into two steps: a morphological step and a syntactic step. Both steps start from the lemmas files that associate to each lemma a morphological class and a syntactic class. These files contain most of the lexical information that is stored in the Lefff.

The morphological step uses also a morphological description of French, which describes each morphological class, in order to inflect all lemmas. Moreover, a file of 1 Lexicon of French inflected forms special inflected forms allows to add extra forms to lemmas when needed (orthographic variants, abbreviations, etc. . . ). Thus, the result of this morphological step is a set of 4-uples (the role of the morphosyntactic flag is described below): (lemma, form, morphosyntactic tag, morphosyntactic flag). Table 1 shows the information associated with lemma boire ("to drink") in the intensional lexicon. Table 1: Lexical entry for lemma boire ("to drink") in the intensional lexicon. Morphological class v-re3 is the standard class for so-called third group verbs with an infinitive ending -re2 , and @verbe standard is the syntactic class of transitive verbs with an optional direct object and possible pronominalization (although pronominalization phenomena are not yet treated with a satisfying level of detail).

The syntactic step works as follow. A first file describes a set of syntactic classes by an inheritance graph: each class is a disjunction of inherited classes or atomic properties. An example thereof, namely the syntactic class @commencer, is given in Table 2. Each atomic property, described in a second file, defines a part of the syntactic information represented by classes that inherit from this property. It can define a part of speech, give a lexical weight, or add some information to the syntactic structure itself (sub-categorization properties, realization properties of sub-categorized complements, phenomena like control or attributives, etc.). Morphosyntactic flags coming from the morphological step are special atomic properties. They encode the (small) part of the syntactic structure that depends from the morphosyntactic tag of a form, and not only from its lemma (e.g., the subject of a verb is mandatory, except at the infinitive form; most forms have the flag "De- fault" that adds no tag-dependent atomic property). Each inflected form receives the syntactic structure obtained by combining all atomic properties it inherits from.

We recently added a mechanism to handle derivational morphology, thus taking advantage of the frequent parallelism that exists between morphology and syntax in this mechanism. Indeed, one can indicate in a lemmas file, below a given lemma, a certain amount of derivations. Each derivation can itself be followed by secondary derivations, and so on. A derivation is modeled by only one identifier, which denotes both:

• the morphologic mechanism that generates the derived lemma from the base lemma (these mechanisms are described in the morphological description that is used),

• a syntactic functor which defines the transformation that has to be applied to the syntactic structure of the base lemma in order to get the syntactic structure of the derived lemma (these syntactic functors are described in the same way than syntactic classes).

An example thereof is provided in Table 3.

Content

The Lefff 2 contains 404,483 inflected forms representing 625,720 entries, some of them being factorized (for example, the first and the third person of the present of -er verbs are grouped in one entry). This corresponds, among others, to 6,798 verbal lemmas, 37,673 nominal lemmas (excluding proper nouns), and 10,053 adjectival lemmas.

Our lexicon can be seen as a meta-lexicon, because the information it contains is stored in an inheritance graph and in a formalism-independent way. An entry consists of:

• an inflected form,

• sometimes a lexical weight, that allows to represent, for example, the fact that support verb constructions or idiosyncrasies should be preferred to normal constructions during parsing 3 , 3 As for now, these lexical weights are set manually, or by rulebased methods, e.g., for multi-word units that get a weight which is higher than the sum of their components'. We intend, in a near future, to extract automatically these weights from (manually or automatically) annotated corpora.

• a part of speech,

• a predicate (which can be seen as the lemma of several formalisms, or as the pred of LFG),

• a sub-categorization frame (represented in an LFGlike way that is easily convertible in other formats),

• a list of morphosyntactic and syntactic "macros", whose expansion can differ from one formalism to another, but whose semantics is formalismindependent (e.g., morphological tags, or macros such as @CtrlSubj or @Impersonal).

A few examples are shown in Table 4.

Acquisition, extension and correction

Building and maintaining a lexicon is a difficult task, both because of the number of entries needed to achieve a large coverage and because of the complexity of the information associated with each entry. Hence the need for automatic or semi-automatic techniques to acquire, extend and correct lexical information.

In the case of the Lefff 2, we used several different techniques:

• Automatic acquisition and extension of the morphological lexicon, according to the method described in [START_REF] Clément | Morphology Based Automatic Acquisition of Largecoverage Lexica[END_REF][START_REF] Sagot | Automatic acquisition of a Slovak lexicon from a raw corpus[END_REF]. This method has been especially used to automatically acquire the verbal part of the lexicon, including the previously cited Lefff 1, but also in order to include derivational information about deverbal derivatives.

• Automatic detection of unknown words in large corpora. This has been done thanks to the spelling error corrector SXSPELL described in [START_REF] Sagot | From raw corpus to word lattices: robust pre-parsing processing[END_REF], which helps to distinguish between unknown words and spelling errors.

• Automatic acquisition of multi-word units, according to techniques similar to those described in [START_REF] Dias | Extraction automatique d'unités lexicales complexes: Un enjeu fondamental pour la recherche documentaire[END_REF].

• Automatic detection of entries with erroneous or incomplete syntactic description, thanks to error mining in the results provided by Lefff -based deep parsers on a large corpora ( [START_REF] Sagot | Trouver le coupable : fouille d'erreurs sur des sorties d'analyseurs syntaxiques[END_REF], see also [START_REF] Van Noord | Error mining for wide-coverage grammar engineering[END_REF]). The basic idea underlying this work is to analyze a large corpus (several million words) and study with statistical tools what differentiates sentences for which parsing succeeded from sentences for which it failed, and in particular which forms lead significantly more often than others to a parsing failure. This allows to identify automatically which forms are erroneously or only partially described in the lexicon.

• Automatic acquisition of atomic syntactic information, in particular about support verbs and prepositional phrases sub-categorized by verbs. This is performed thanks to a statistical analysis of form and tag patterns in very large tagged corpora.

Use

Our lexicon is used by at least two very different parsing systems for French. The first one is FRMG (Villemonte de la Clergerie, 2005), a TAG parser based on a meta-grammar that generates a factorized TAG. Lefff entries are used as hypertags to anchor quasi-trees.

The second one is SXLFG (Boullier and [START_REF] Sagot | Automatic acquisition of a Slovak lexicon from a raw corpus[END_REF], an efficient LFG parser, which uses Lefff entries as LFG lexical entries. Both systems have been used recently with Lefff in several experiments, e.g., during the French parsers evaluation campaign EASy and for large-scale deep parsing experiments on multi-million word corpora [START_REF] Sagot | Deep nonprobabilistic parsing of large corpora[END_REF].

It is very difficult to give an idea of the precision and the coverage of the Lefff, since the influence of the grammar is also extremely important in parsing precision and parsing coverage. However, we are developing a rule-based parser4 that relies on the Lefff. Applied on the constituents boundaries and kind detection task of the EASy parsing evaluation campaign for French [START_REF] Paroubek | EASy : campagne d'évaluation des analyseurs syntaxiques[END_REF], it leads to an f-measure as high as 78.5%, which is very good (only one participant got a higher mark during the campaign).

Conclusion

We have introduced a new large-coverage syntactic lexicon for French, the Lefff 2, which is freely available on http://www.lefff.net/. It contains more than 500,000 entries, and has been successfully used in largescale parsers using various linguistic formalisms. It is represented in a compact way, thanks to an graph of inheritance of atomic properties. Moreover, automatic and semiautomatic methods have been used to acquire, supplement and correct this lexicon. Some of these methods, as well as the overall architecture, could be used to develop similar lexicon for other languages, including languages for which no large-coverage lexicon is available.

Boullier, Pierre and Benoît [START_REF] Sagot | Automatic acquisition of a Slovak lexicon from a raw corpus[END_REF]. Efficient and robust LFG parsing: SXLFG. In Proceedings of IWPT'05. Vancouver, Canada. Table 2: Description of the syntactic class @commencer, which is associated with lemmas commencer ("to begin"), continuer ("to go on") and recommencer ("to start anew") in the intensional lexicon. 1<subj,(obj|scomp|de-vcomp),(à-obj)>', cat=v,@SCompSubj,@CtrlAObjDe,@PS13s] souhaite v [pred='souhaiter 1<subj,(obj|scomp|vcomp)>', cat=v, @SCompSubj,@CtrlSubj,@PS13s] ... passer v [pred="passer<(subj|ssubj|vsubj),(obj),(à-obj)>", cat=v, @W]; passer v [pred="passer<(subj|ssubj|vsubj),acomp>", cat=v, @W, @AASubj]; passer v [pred="passer<(subj|ssubj|vsubj),pour-acomp>", cat=v, @W, @AAPourSubj]; passer v [pred="passerSe<(subj),(de-obj)>obj", cat=v,@pron, @W]; passer v [pred="passerSe<(subj),de-vcomp>obj", cat=v,@pron, @W, @CtrlSubjDe];

... petit à petit 500 adv [pred="petit-à-petit", cat=adv];

Table 4: A few lexical entries for inflected forms of the lemmas boire ("to drink") souhaiter ("to wish") in the extensional lexicon. As can be seen, the active and the passive past participle are distinguished, since they differ, among others, by their subcategorization frames. The @SCompSubj macro tells that the scomp, if present, must be at the subjunctive mood.

The @CtrlSubj indicates a subject control verb, whereas @CtrlAObjDe indicates that the à-obj is the subject of the de-vcomp, if present. Default lexical weight (when not indicated) is 100.

Figure 1 :

 1 Figure 1: Overview of the compilation process that builds the extensional version of the Lefff from its intensional factorized version.

  blanc adj-c @adj couleur [base lemma] > adjectif nominalisé (un) blanc > péjoratif-âtre blanchâtre > causatif déadjectival-ir blanchir >> agentif-eur (le/la) blanchisseur/euse >> nom d action-age (le) blanchissage >> participe présent adjectivé blanchissant(e)(s) > nom déadjectival-eur (la) blancheur

Table of

 of

	syntactic properties
	Lexical entries
	Table of syntactic functors

Table 3 :

 3 Lexical entry for the adjectival lemma blanc ("white") in the intensional lexicon, with some of its morphological derivatives.

	bois	v	[pred='boire	1<subj,(obj)>',cat=v,@P12s]
	bu	v	[pred='boire	1<subj,(obj)>',cat=v,@active,@Kms]
	bu	v	[pred='boire	1<(par-obj),subj>',cat=v,@passive,@être,@Kms]
	...
	souhaite	v	[pred='souhaiter

We do not describe here our morphological formalism. The verb boire is usually considered as irregular. However, with appropriate collision rules to manage phenomena that happen at the boundary between the stem and the suffix, it is possible to fit boire's inflection into the general class of -re third class verbs.

This parser is based on a context-free grammar and nonprobabilistic disambiguation heuristics.