Pierre Gloaguen
email: pierre.gloaguen@gmail.com

Marie-Pierre Etienne

Sylvain Le Corff

Stochastic differential equation based on a multimodal potential to model movement data in ecology

Keywords: Movement model, GPS data, Stochastic differential equation, Exact simulation, Local linearization, Pseudo-likelihood methods

This paper proposes a new model for individuals movement in ecology. The movement process is defined as a solution to a stochastic differential equation whose drift is the gradient of a multimodal potential surface. This offers a new flexible approach among the popular potential based movement models in ecology. To perform parameter inference, the widely used Euler method is compared with two other pseudo-likelihood procedures and with a Monte Carlo Expectation Maximization approach based on exact simulation of diffusions. Performances of all methods are assessed with simulated data and with a data set of fishing vessels trajectories. We show that the usual Euler method performs worse than the other procedures for all sampling schemes.

Introduction

Statistical inference of movement models provides many insights on the ecological features that explain population-level dynamics. These analyses are crucial to wildlife managers to understand complex animal behaviors [START_REF] Chavez | Landscape Use and Movements of Wolves in Relation to Livestock in a Wildland-Agriculture Matrix[END_REF]. In fisheries science, understanding the underlying patterns responsible for spatial use of the ocean is a key aspect of a sustainable management [START_REF] Chang | Application of a vessel monitoring system to advance sustainable fisheries management-Benefits received in Taiwan[END_REF]. Both fields promote now large programs to deploy Global Positioning System (GPS) device. For instance, we might mention, among others, the Tagging of Pelagic Predators program (TOPP, www.gtopp. org), the TORSOOI (www.torsooi.com) program for marine animals, the Elephant without Borders (www.elephantswithoutborders.org/tracking.php) or WOLF GPS (www.wolfgps.com) programs for terrestrial wildlife. In the European Union, since the 1st of January 2012, fishing vessels above 12m are mandatory equipped with a Vessel Monitoring System which has become a standard tool of fisheries monitoring worldwide.

As a result, such programs produce huge datasets which have been largely used to understand, explain and predict animals or vessels movements. The GPS-type loggers can be set with several acquisition frequencies which should be adjusted to the experimental setting.

In the last few years, growing attention has been dedicated to continuous time and continuous space Markovian models as a realistic and flexible framework to model such data [START_REF] Blackwell | Random diffusion models for animal movement[END_REF][START_REF] Brillinger | Employing stochastic differential equations to model wildlife motion[END_REF][START_REF] Preisler | Modeling animal movements using stochastic differential equations[END_REF]. These papers focus on stochastic differential equations (SDE) to describe and analyze animal trajectories. Since the model based on a pure diffusion process introduced in [START_REF] Skellam | Random dispersal in theoretical populations[END_REF] a large variety of SDE has been proposed to model wildlife behavior, see [START_REF] Preisler | Modeling animal movements using stochastic differential equations[END_REF] for references about elephant-seal or birds migrations. In Brillinger et al. (2001a), the authors introduces SDE based on a potential surface to capture the directional bias of animal patterns. This potential function is assumed to reflect the attractiveness of the environment and regions where species are likely to travel to. In the framework proposed by [START_REF] Brillinger | Chapman and Hall/CRC Handbooks of Modern Statistical Methods[END_REF], the drift of the SDE is given by the gradient of a potential map P η which depends on an unknown parameter η while the diffusion coefficient is a smooth function. This flexible framework has been widely used in movement ecology for the last 20 years [START_REF] Blackwell | Random diffusion models for animal movement[END_REF]Brillinger et al., 2001a[START_REF] Brillinger | Employing stochastic differential equations to model wildlife motion[END_REF][START_REF] Brillinger | Modeling particles moving in a potential field with pairwise interactions and an application[END_REF][START_REF] Harris | Flexible continuous-time modeling for heterogeneous animal movement[END_REF][START_REF] Preisler | Modeling animal movements using stochastic differential equations[END_REF][START_REF] Preisler | Analyzing animal movement patterns using potential functions[END_REF]. In [START_REF] Blackwell | Random diffusion models for animal movement[END_REF], [START_REF] Blackwell | Exact Bayesian inference for animal movement in continuous time[END_REF], and [START_REF] Harris | Flexible continuous-time modeling for heterogeneous animal movement[END_REF], the authors introduce a quadratic potential function which corresponds to a bivariate Ornstein-Uhlenbeck process to model the position of an animal. The Ornstein-Ulhenbeck process offers a convenient framework to represent attractiveness of a given area but it remains restrictive as animals are not prone to revert to a single attractive zone. This process owes its popularity to the simple form of the maximum likelihood estimator of η and of the diffusion coefficient as its transition density is Gaussian. In [START_REF] Preisler | Analyzing animal movement patterns using potential functions[END_REF], the authors propose different potential functions, with more complex features such as multiple attractive regions, as a baseline of a flexible framework to describe animal movement.

In this paper, we propose a new model where the potential function is a mixture of Gaussian shaped functions. This model was suggested in [START_REF] Preisler | Analyzing animal movement patterns using potential functions[END_REF], but, to the best of our knowledge, it has never been used in movement ecology or applied to practical cases. Each attractive region is modeled as a Gaussian shaped function with its own mean location and information matrix characterizing its dispersion. The drift of the SDE ruling animal movement is a mixture of these functions, with unknown weights, centers and information matrices that should be inferred from movement data.

Designing efficient procedures to infer this model is a very challenging task as some elementary properties, such as the transition density of the solution to the SDE, are not available in closed form. Different statistical methods have been proposed to perform maximum likelihood estimation with unknown transition densities (see [START_REF] Iacus | Simulation and inference for stochastic differential equations: with R examples[END_REF][START_REF] Kessler | Statistical methods for stochastic differential equations[END_REF]. The most convenient procedures to estimate discretely observed diffusion processes rely on discretization schemes to approximate the SDE between two observations and use a surrogate of the likelihood function to compute an approximate maximum likelihood estimator of η. The simplest likelihood approximation is the Euler-Maruyama method which uses constant drift and diffusion coefficients on each interval. To the best of our knowledge, maximum likelihood inference procedures in movement ecology in the case of unknown transition densities are only based on the Euler-Maruyama method (see [START_REF] Brillinger | Chapman and Hall/CRC Handbooks of Modern Statistical Methods[END_REF][START_REF] Preisler | Analyzing animal movement patterns using potential functions[END_REF]. The maximum likelihood estimator computed with this method may be proved to be consistent under some assumptions on the total number of observations n and on the time step ∆ n between observations (which is assumed to vanish as n goes to infinity). However, there is no guarantee that using GPS tagging in ecology provides observations at a sufficiently high sampling rate and it might produce a highly biased estimator. Indeed, the chosen frequency is a crucial parameter to monitor animal behaviors over a given time horizon since GPS batteries depend on the number of recorded relocations. Therefore, depending on the needs of the given study, the recording frequency can be small. Moreover, real life experiments in complex environments (water for marine mammals for instance) might result in strongly irregular time step acquisitions. Therefore, alternatives to the Euler-Maruyama method should be considered to estimate parameters in potential based movement models. For instance, the bias of the Euler-Maruyama method may be reduced using higher order discretization schemes.

A particularly interesting higher order scheme is given by the Ozaki discretization which proposes a linear approximation of the drift coefficient combined with a constant approximation of the diffusion term [START_REF] Ozaki | A bridge between nonlinear time series models and nonlinear stochastic dynamical systems: a local linearization approach[END_REF]Shoji and Ozaki, 1998a). More recently, [START_REF] Kessler | Estimation of an ergodic diffusion from discrete observations[END_REF], [START_REF] Kessler | Statistical methods for stochastic differential equations[END_REF] and Uchida and Yoshida (2012) introduced another Gaussian based approximation of the transition density between two consecutive observations using higher order expansions of the conditional mean and variance of an observation given the observation at the previous time step. Another approach to approximate the likelihood of the observations based on Hermite polynomials expansion was introduced by Ait-Sahalia (1999,2002,2008) and extended in several directions recently, see [START_REF] Li | Maximum-likelihood estimation for diffusion processes via closed-form density expansions[END_REF] and all the references therein. However these methods also induce, theoretically, a bias due to the likelihood approximation.

To avoid this systematic bias associated with every discretization procedure, [START_REF] Beskos | Exact simulation of diffusions[END_REF] and Beskos et al. (2006a) proposed an exact algorithm to draw samples from finite-dimensional distributions of potential based diffusion processes. This sampling method is based on a rejection sampling step and may be used to sample from any finite dimensional distribution of the target SDE. This algorithm is a pivotal tool to obtain an unbiased estimate of the intermediate quantity of the Expectation Maximization (EM) [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. As a byproduct, this also allows to sample trajectories exactly distributed according to the estimated model which is not possible with the three other methods. However, the computational complexity of the acceptance rejection step of these exact algorithms, which requires to sample skeletons of trajectories between each pair of observations, grows with the time step between observations.

There is no theoretical nor practical studies to choose the method which achieves the best trade off between fast convergence and accuracy in movement ecology. We investigate the performance of four different estimation methods for the new model proposed in this paper:

-the Euler-Maruyama method ; -the Ozaki local linearization method, proposed in [START_REF] Ozaki | A bridge between nonlinear time series models and nonlinear stochastic dynamical systems: a local linearization approach[END_REF] and Shoji and Ozaki (1998a) ;

-the Kessler high order Gaussian approximation method, proposed in [START_REF] Kessler | Estimation of an ergodic diffusion from discrete observations[END_REF] and refined using an adaptive procedure in Uchida and Yoshida (2012) ;

-the Exact Algorithm based Monte Carlo EM method, proposed in Beskos et al. (2006b).

The paper is organized as follows. The potential based model is introduced in Section 2 and the inference methods used in the paper are presented in Section 3. A simulation study to evaluate the robustness of the statistical methods with the specific potential function proposed in the paper is given in Section 4.1. In order to evaluate the impact of the sampling rate, three sampling scenarios are considered, high frequency, intermediate frequency, and low frequency. Finally, an application of our new model to real data, together with an evaluation of the performance of each inference method, is done in Section 4.2 for the estimation of attractive zones of two different French fishing vessels.

Potential based movement model

In this section, we propose a new model to describe the position process of an individual. The latter modelled as is a stochastic process (X t ) 0≤t≤T observed between times 0 and T . (X t ) 0≤t≤T is assumed to be the solution to the following time homogeneous SDE:

X 0 = x 0 and dX t = b η (X t )dt + γdW t , (1)
where (W t ) 0≤t≤T is a standard Brownian motion on R 2 , and γ ∈ R + is an unknown diffusion parameter. Moreover, we assume that the drift follows the gradient of mixture function, i.e.:

b η (x) := ∇P η (x) , (2)
P η (x) = K i=1 π k ϕ η k (x) with ϕ η k (x) := exp - 1 2 (x -µ k ) T C k (x -µ k ) , (3)
where:

-K is the number of components of the mixture;

-π k ∈ R + is the relative weight of the k-th component, with K k=1 π k = 1; -µ k ∈ R 2 is the center of the k-th component; -C k ∈ S +
2 is the information matrix of the k-th component, where S + 2 is the set of 2 × 2 symmetric positive definite matrices.

Equations ( 1) and (2) define a potential based continuous time movement model, and follows a popular idea in movement ecology [START_REF] Blackwell | Random diffusion models for animal movement[END_REF]Brillinger et al., 2001a[START_REF] Brillinger | Employing stochastic differential equations to model wildlife motion[END_REF][START_REF] Preisler | Modeling animal movements using stochastic differential equations[END_REF][START_REF] Brillinger | Chapman and Hall/CRC Handbooks of Modern Statistical Methods[END_REF][START_REF] Preisler | Analyzing animal movement patterns using potential functions[END_REF][START_REF] Harris | Flexible continuous-time modeling for heterogeneous animal movement[END_REF]. In this framework, the movement is supposed to reflect the attractiveness of the environment, which is modeled using a real valued potential function defined on R 2 . Equation (3) describes the new potential function proposed in this paper. This function is a smooth multimodal surface, having K different components. In this paper, K is supposed to be known one we need to infer η from movement data where:

η = {(π k ) k=1,...,K-1 , (µ k ) k=1,...,K , (C k ) k=1,...,K } ∈ R 6K-1 .
Potential based continuous time movement model have been widely studied in ecology for the last twenty years. The two most popular SDE based models in movement ecology are:

-the Brownian motion, with or without drift, corresponding to a constant b η (corresponding to a linear potential function), as in [START_REF] Skellam | Random dispersal in theoretical populations[END_REF] ;

-the Ornstein-Uhlenbeck process, corresponding to a linear drift function b η (corresponding to a linear potential function), as in [START_REF] Blackwell | Random diffusion models for animal movement[END_REF].

These two models are appealing as their transition density function is available explicitly, and the inference in these case is straightforward. However, it contains only a very restricted class of potential functions P η (linear, or quadratic) that might be unrealistic in ecological applications (unimodal attractiveness surfaces, for instance). The model introduced in this paper is an extension of one of those suggested in [START_REF] Preisler | Analyzing animal movement patterns using potential functions[END_REF], it has multiple modes and is flexible enough to accomodate a wide range of situations. However, the process solution to the SDE (1) with the potential function (3) has no explicit transition density so that approximate maximum likelihood procedures such as the methods presented in Section 3 may be considered.

Maximum likelihood estimation procedures

The aim of this section is to present four maximum likelihood inference procedures to estimate the parameter θ = (η, γ) using a set of discrete time observations. Among them, the Euler-Maruyama method is the only one used so far in movement ecology, regardless of its potential weaknesses. The performance of these methods are evaluated in Section 4.

The observations are given by G independent realizations of the continuous process given by equations ( 1)-( 3) . The set of observations is then the collection of trajectories (x g ) g=1,...,G where each trajectory x g is made of n g + 1 exact observations at times

t g 0 = 0 < t g 1 < • • • < t g n g = T g
and starting at x g 0 . The probability density of the distribution of X ∆ given X 0 (i.e., the transition density) is denoted by q ∆ θ when the model is parameterized by θ: for all bounded measurable function h on R 2 :

E θ [h(X ∆ )|X 0 ] = h(y)q ∆ θ (X 0 , y)dy ,
where E θ is the expectation when the model is driven by θ.

As the G trajectories (x g ) g=1,...,G are independent, and by the Markov property of the solution to (1), the likelihood function may be written:

L(θ; x) = G g=1 n g -1 i=0 q ∆ g i θ (x g i , x g i+1 ) , (4)
where ∆ g i := t g i+1 -t g i . The maximum likelihood estimator of θ is defined as: θ := argmax θ L(θ; x) .

In the cases of the Brownian motion and Ornstein-Uhlenbeck processes, the function q ∆ θ is the probability density function of a Gaussian random variable with known mean and covariance so that the direct computation of θ is an easy task. However, in more general settings such as in the model considered in Section 2, q ∆ θ is unknown. While many statistical methods have been proposed to compute approximations of θ, the only statistical method used in movement ecology is the Euler-Maruyama discretization procedure. It is known that the quality of this approximation highly depends on the sampling rate which means that this method might therefore not be well suited to real life animal GPS tags. Therefore, several alternatives are investigated in the remainder of this paper to compute approximations of θ. Since all g trajectories are exchangeable, for the sake of clarity, the aforementioned approximation methods are detailed for a given trajectory and references to g are omitted.

Euler-Maruyama method The Euler-Maruyama discretization is an order 0 Taylor expansion of the drift function (as the diffusion coefficient is constant no expansion is required). The drift is therefore assumed to be constant between two observations. For any 0 ≤ i ≤ n -1 the target process is approximated by the process (X E t ) ti≤t<ti+1 , solution to the SDE:

X E ti = x i and, for t i ≤ t ≤ t i+1 , dX E t = b η (x i )dt + γdW t .
For all 0 ≤ i ≤ n -1, the transition density q ∆i θ (x i , x i+1 ) is approximated by the transition density of the process (X E t ) ti≤t≤ti+1 , denoted by q ∆i,E θ , evaluated for the observations (x i , x i+1 ). This is the probability density function of a Gaussian random variable with mean µ E i and variance Σ E i :

µ E i = x i + ∆ i b η (x i ) , Σ E i = γ 2 ∆ i ,
where I k denotes the k × k identity matrix. Hence, the Euler-Maruyama estimate is given by maximizing (4) when q

∆ g i θ is replaced by q ∆ g i ,E θ .
Ozaki method The Ozaki method, proposed in [START_REF] Ozaki | A bridge between nonlinear time series models and nonlinear stochastic dynamical systems: a local linearization approach[END_REF] and Shoji and Ozaki (1998a), provides a local linearization of the drift term in order to improve the Euler scheme. For any 0 ≤ i ≤ n -1 the target process is approximated by the process (X O t ) ti≤t<ti+1 , solution to the SDE:

X O ti = x i and, for t i ≤ t ≤ t i+1 , dX O t = J i,η X O t -x i + b η (x i ) dt + γdW t ,
where J i,η is the 2×2 Jacobian matrix of the drift function b η evaluated at x i . Therefore, the target process is now approximated between each pair of observations by a twodimensionnal Ornstein-Uhlenbeck process. For all 0 ≤ i ≤ n -1, the transition density

q ∆i θ (x i , x i+1
) is approximated by the transition density of the process (X O t ) ti≤t≤ti+1 , denoted by q ∆i,O θ , evaluated for the observations (x i , x i+1 ). If the potential function is such that, for all 0 ≤ i ≤ n -1 and all θ, J i,θ is nonsingular and symmetric (as it is the case of the potential introduced in Section 2), following Shoji and Ozaki (1998b), this transition density is the probability density function of a Gaussian random variable with mean µ O i and variance Σ O i :

µ O i = x i + (exp (J i,η ∆ i ) -I 2 )(J i,η ) -1 b η (x i ) , vec(Σ O i ) = (J i,η ⊕ J i,η ) -1 e (Ji,η⊕Ji,η)∆i -I 4 vec γ 2 I 2 ,
where vec is the stack operator and ⊕ is the Kronecker sum. The local linearisation estimate is then given by maximizing (4) when q

∆ g i θ is replaced by q ∆ g i ,O θ .
Kessler method This procedure, proposed in [START_REF] Kessler | Estimation of an ergodic diffusion from discrete observations[END_REF], generalizes the Euler-Maruyama method using a higher order approximation of the transition density. Following the same steps as Euler or Ozaki discretizations, [START_REF] Kessler | Estimation of an ergodic diffusion from discrete observations[END_REF] proposed to consider a Gaussian approximation of the transition density between consecutive observations. The procedure aims at replacing q ∆i θ (x i , x i+1 ) by a Gaussian probability density function with mean and variance given by the exact mean µ target i and variance Σ target i of the target process at time t i+1 conditionally on the value of the target process at time t i . This leads to an approximation with the same first two moments as the target transition density. This approximation can be written similarly to the previous discretization schemes by defining, for any 0 ≤ i ≤ n -1, the process (X target t ) ti≤t<ti+1 as the solution to the SDE:

X target ti = x i and, for t i ≤ t ≤ t i+1 , dX target t = µ target i -x i ∆ i dt + Σ target i ∆ i 1/2 dW t .
However, the transition density of the target process being unknown, µ target i and Σ target i are not available in closed form. Nonetheless, Taylor expansions of these two conditionnal moments are available (see [START_REF] Florens-Zmirou | Approximate discrete-time schemes for statistics of diffusion processes[END_REF], or Uchida and Yoshida (2012) for the multidimensional case). [START_REF] Kessler | Estimation of an ergodic diffusion from discrete observations[END_REF] proposed to replace µ target i and Σ target i by these approximations. For all 0 ≤ i ≤ n -1, the transition density q ∆i θ (x i , x i+1 ) is approximated by the transition density of the process (X K t ) ti≤t≤ti+1 (approximated with these expansions). These expansions can be computed directly from the drift and diffusion functions and their partial derivatives. The order of the expansion of the true conditional moments is left to the user and the performance of the estimator highly depends on this parameter, order one being the Euler-Maruyama method. In this paper, it was performed up to the second order. In this case, and for the process defined by ( 1) and (2), the function q ∆i,K θ (x i , •) is the probability density function of a Gaussian random variable with mean µ K i and variance Σ K i :

µ K i = x i + ∆ i b η (x i ) , Σ K i = γ 2 ∆ i (I 2 + ∆ i J i,η ) . (5)
Note that µ K i = µ E i . For numerical stability, (Σ K i ) -1 and its determinant can be replaced by a Taylor expansion, the associated contrast function to optimize in multidimensional cases is given in Uchida and Yoshida (2012). A drawback of this method is the fact that (5) does not necessarily define a positive semi-definite matrix. For instance, if Tr(J i,η ) < -2/∆ i , then Tr(Σ K i ) < 0, which is likely to occur when ∆ i is large. In the following applications, whenever Σ K i is not positive definite, the associated observation is thrown out from the computation of the likelihood, as proposed in [START_REF] Iacus | Simulation and inference for stochastic differential equations: with R examples[END_REF]. Kessler estimate is then given by maximizing (4) when q

∆ g i θ is replaced by q ∆ g i ,K θ .
Exact Algorithm based Monte Carlo EM (EA MCEM) method The EA MCEM proposed by Beskos et al. (2006b) does not use Gaussian approximations of the transition densities to compute the maximum likelihood estimator. Details of the method are given in Beskos et al. (2006b) and the important results for the experiments are given online as a supplementary material.

Applying the exact algorithm to estimate θ requires the target SDE to be reducible to a unit diffusion using the Lamperti transform which is obtained in our case by setting (Y t := γ -1 X t ) 0≤t≤T . Then,

dY t = α θ (Y t )dt + dW t where α θ (•) := γ -1 b η (γ •) = γ -1 ∇P η (γ •) . (6)
The EA MCEM approach used in this work relies on the following assumptions.

-Conservative assumption: for all θ = (η, γ) ∈ R d+1 , there exists

H θ : R 2 → R such that for all x ∈ R 2 , α θ (x) = ∇H θ (x) . (7)
-Boundedness condition: for all θ ∈ R d+1 , there exist m θ , M θ , such that for all x ∈ R 2 ,

m θ ≤ α θ (x) 2 + ∆H θ (x) ≤ M θ , ( 8
)
where ∆ is the Laplace operator:

∆H θ : x → ∂α θ,1 ∂x 1 (x) + ∂α θ,2 ∂x 2 (x) .
Both conditions are somehow restrictive in general, however, the first one turns out to be satisfied automatically for potential based models studied in ecology, and described in Section 2. Given the model described by equations ( 1)-( 3), H θ is given as:

H θ : x → K k=1 π k ϕ η k (γx)/γ , with θ = (η, γ).
The second condition can be relaxed at the cost of additional computations (Beskos et al., 2006b), but is satisfied by the potential function of equation ( 3). This method offers the advantage of avoiding approximation errors due to time discretization of the SDE. The only error comes from the Monte Carlo simulations used to approximate the expectation in the E-step (see details in the supplementary material).

In theory, if the conditions ( 7) and ( 8) are satisfied, it is always possible to perform these simulations. However, the simulation algorithm is based on rejection sampling and the acceptance probability is equal to:

exp - 1 2 (M θ -m θ ) ti+1 ti φ θ (Y s )ds , (9)
where m θ and M θ are defined as in (8), and φ θ (x) := ( α θ (x) 2 +∆H θ (x)-m θ )/2 ≥ 0. Then, the integral in (9) increases with the time step, and the acceptance probability decreases to 0. Therefore, in practice, this method also depend on the sampling step to be used in a reasonnable time.

In order to compare the performance of the three methods, an approximated likelihood criterion is used. The loglikelihood of two given estimates θ1 and θ2 cannot be computed exactly. However, in the case where ( 7) and ( 8) hold, and following Beskos et al. (2009), an unbiased estimator EA of the loglikelihood based on Monte Carlo simulations may be computed. This estimator has no intrinsic bias as the error only comes from the Monte Carlo procedure. In the following, this criterion allowed us to compare the quality of the different estimations resulting from the four different methods.

Application

Simulation study

The performance of the four estimation methods presented in this paper is evaluated using different sampling schemes. The hidden potential map has K = 2 components and is represented in Figure 1a. All simulated trajectories start from the same x 0 and are sampled from the true distribution of the process (X t ) t≥0 with parameters η * and γ * using the acceptance rejection procedure proposed in [START_REF] Beskos | Exact simulation of diffusions[END_REF]. G = 10 independent trajectories are simulated with n g = 500 recorded points. Three different sampling time steps are considered, respectively with high frequency (∆ = 0.1), intermediate frequency (∆ = 1) and low frequency (∆ = 10). In an actual sampling design, this would correspond to three different GPS tags settings with a limited number of emissions. For each method and in each scenario, this procedure is repeated independently to produce 30 different datasets.

The optimization problem associated with the M-step of the EM algorithm is performed using the CMA-ES algorithm proposed by [START_REF] Hansen | Completely derandomized self-adaptation in evolution strategies[END_REF]. For each estimation method, 30 initial parameters θ 0 are used and the parameter estimate with the maximum objective function is considered as the estimator θ. Figures 2,3 and 4 display the parameter estimate for the three sampling cases. The best estimate for all parameters and techniques is obtained with the intermediate frequency sampling rate. As illustrated by Figure 1, this frequency allows a good exploration of the map by the process with 500 observations and all methods provide reliable estimates. When ∆ = 0.1 with only 500 observations per trajectory, the time horizon 50 might be insufficient for a good parameter estimation using this model. On the other hand, when ∆ = 10, there is a strong bias in the estimation of the shape parameters C k , k = 1, 2, and the diffusion coefficient for all methods. The potential map driving the movement is shown in Figure 1a, dark zones present high potential whereas white zones have low potential. On the three other panels, ten simulated trajectories with three different sampling schemes are given. The white dot represents the starting point x 0 of each trajectory.

The Euler method performs much worse than the other methods when ∆ = 1 and ∆ = 10 whereas the three other methods are more robust to the sampling frequency. The Ozaki method provides similar results to the EA MCEM method. The Kessler estimation method provides results which may differ for some parameters (for instance µ

(1)

1 or C (1) 11
in Figure 4) as about 50% of the observations lead to a non positive semi-definite matrix in equation ( 5) and are therefore dropped. This is a major drawback of this method as it induces a supplementary bias. Finally, note that the EA MCEM method has a much larger computation cost than all other procedures but it is less sensitive to the starting point of the algorithm. The mean acceptance rate decreases from 99.6% (∆ = 0.1) to 97.6 (∆ = 1) and 67.5% (∆ = 10) respectively.

Figure 5 displays the absolute estimation errors |P η(x) -P η * (x)| for each method. The map is produced using the median of all estimated values as a set of parameters. The Euler method performs much worse than the other methods when ∆ = 1 and ∆ = 10.

Figure 6 shows the distribution of the relative integrated error

|Pη(x)-P η * (x)|dx |P η * (x)|dx
for each method. According to this simulation study, it seems preferable not to use the Euler method in comparison to any of the three other procedures.

Inferring fishing zones

Delimiting fishing zones with high potential represents a key step in fisheries management, for instance to set up some marine protected areas. In order to illustrate the performance of each method to define such zones using actual GPS data, the model presented in Section 2 is estimated using two sets of trajectories of two French fishing vessels named V1 and V2. The two sets of trajectories are represented in Figure 7. V1 (Black in Figure 7) The dataset of vessel 1 is composed of 15 short trajectories with a total of 724 GPS locations and a sampling time step of around 12 minutes, with some irregularities up to 1 hour.

V2 (Grey in Figure 7) The dataset of vessel 2 is composed of 25 trajectories with a total of 3111 GPS locations and an irregular sampling time step mostly between 15 and 50 minutes, with some irregularities up to 4 hours.

For each dataset, the four methods presented above were used to estimate θ. The number of components K is not assumed to be known anymore and has to be estimated. We do not focus on this problem which has already been addressed in the case of discretely observed SDE (see [START_REF] Uchida | AIC for ergodic diffusion processes from discrete observations[END_REF], for instance) and assume K 1 = 1 (respectively K 2 = 3) for V1 (resp. V2). In the following, this approximation of the likelihood proposed by Beskos et al. (2009) is used to choose which estimation method provides the best estimated map.

Results for V1 Results for the vessel 1 are presented in Figure 8. The best estimate in the sense of the greatest approximated log-likelihood is given by the map estimated with the MCEM EA method, followed by Ozaki, Kessler and Euler (see Table 1 for the values of each log-likelihood, for each estimated parameter). Again θK is unstable as the correction term for the variance (given in equation ( 5)) leads to a non positive semidefinite matrix for 28% of the observations. However, the estimated map is similar to

0.2 0.4 0.6 π 1 2.5 3.0 3.5 µ 1 (1)
-5.5 -4.5 -3.5 -2.5

µ 1

(2)

-1.0 0.0 1.0 µ 2 (1)
-0.5 0.5

1.5 µ 2
(2)

0.1 0.3 0.5 C 11 (1) 0.2 0.6 1.0 C 11 (2) 0.1 0.3 0.5 C 22
(1) (1)

0.5 1.5 2.5 C 22 (2)
-5.5 -4.5 -3.5 -2.5

µ 1

(2)

-1.0 0.0 1.0 µ 2 (1)
-0.5 0.5

1.5 µ 2
(2)

0.1 0.3 0.5 C 11 (1) 0.2 0.6 1.0 C 11 (2) 0.1 0.3 0.5 C 22
(1) The axis of the resulting Gaussian form are conform to the trawling directions of the vessels.

0.5 1.5 2.5 C 22 (2)
Results for V2 Results for the vessel 2 are presented in Figure 9. As in the case of V1, the best estimate in the sense of the greatest approximated loglikelihood is given by the map estimated with the EA MCEM method, followed by Ozaki, Kessler and Euler (see Table 1 for the values of each log-likelihood, for each estimated parameter). Again, θK is unstable, as the correction term for the variance leads to a non positive semi-definite matrix for 48% of observations. The acceptance rate for the conditional simulation of the EA MCEM method is 6.2%. As for vessel 1, Euler method produces a smooth estimated map, where attractive zones are connected and wrap almost all observed points. Kessler, Ozaki and EA MCEM methods lead to maps where zones are disconnected: one close to to the harbour and an offshore zone. In the case of the Kessler method, the extension and the relative weight of this first zone is larger than for the two other methods. For the three methods, the second offshore zone is a mixture of a general attractive zone with an East-West orientation, and a smaller hot spot that gathers a large amount of observed points. Here, a natural extension would be to use a larger K. The Gaussian model proposed by [START_REF] Preisler | Analyzing animal movement patterns using potential functions[END_REF] would have imposed a potential function whose orientation is given by the x and y axis, with circular contour lines as a consequence of the independence between directions. The generalization proposed in this paper models more complex attractive zones. The contour lines of the potential might be used to define more realistic high potential fishing zones. The darker a zone is, the more attractive it is for the given vessel. Observed points are plotted in white in order to see the superposition between maps and trajectories. The darker a zone is, the more attractive it is for the given vessel. Observed points are plotted in white in order to see the superposition between maps and trajectories.

Conclusions

This paper proposes a new model based on a stochastic differential equation to describe movement in ecology. The proposed model belongs to the popular class of continuous time model described by SDE, whose drift is supposed to be the gradient of a potential function. This potential function is assumed to reflect the attractiveness of the environment in which the moving individual evolves. We propose a model where this potential is a mixture of smooth Gaussian shaped functions, giving a flexible framework to describe multimodal potential surfaces. As a counterpart, this model leads to a difficult inference task, as some key quantities to express the likelihood are unknown. This lead us explore different possible approaches for parameters estimation.

Several extensions of the proposed potential based model could be considered to capture sharply the individuals dynamics. For instance, in this paper, the first part of the fishing vessels trajectories, which consists in steaming toward a fishing zone, seems to be more deterministic than the second part, when the vessel is in the fishing zone. We could use a Markov switching SDE where the state might follow several dynamics depending on a regime indicator given by a finite state space hidden Markov chain. In the case presented here, this deterministic phase contains a small proportion of the trajectory, and therefore does not affect the inference result, but a better model for this first phase might be preferable.

We also make the assumptions that observed trajectories are independent. In many cases, this is likely to be false. Therefore, the G observed trajectories could also be modeled as the solution to a 2G dimensional SDE with interactions in the drift function and the diffusion matrix. As the individuals are not observed at the same time, a partially observed SDE can be defined which implies additional challenges to estimate all parameters using algorithms designed for hidden Markov models.

Finally, an undesirable property of the potential introduced in the paper is that, far from the attractive zones, the process behaves like a Brownian motion. This can be easily overcome for instance by adding another component in the mixture proportional to -x-G 1/2 , where G is a fixed attractive point. This ensures that even if an individual is far from the attractive zones, he is likely to revert around G. We used this potential and obtained very similar numerical results. We decided not to add this component in the model as it seemed artificial to ensure stationarity for theoretical reasons.

From the inference point of view, this work explores the performance of four inference methods to estimate the parameters in such potential based movement models. The first three methods are pseudo likelihood approaches, including the widely used Euler-Maruyama procedure, with similar implementations and requiring little assumptions on the model. The fourth method, based on a Monte Carlo EM using the Exact Algorithm, requires additional mathematical assumptions on the model and is more technically and computationally intensive, but has the nice property of not using Gaussian approximations, inducing a structural bias.

Numerical experiments with simulated data illustrate that the Euler discretization method is not robust to low sampling rates, which is a common situation in movement ecology, and that the three other approximate maximum likelihood methods perform better, suggesting that the Euler approach might not be well suited to movement ecology. These four methods were also compared to estimate potential maps (from a specific model) using actual movement data of two fishing vessels. It is clear here that the different methods can lead to different maps with various interpretations. Specifically, in the examples presented here, we would like to point out that the Euler-Maruyama results lead to a totally different map, implying different interpretations, than the three other methods. Therefore, users should be careful when using this method, and ensures that their conclusions are not biased by the choice of the Euler discretization. Moreover, using the criterion of the unbiased approximated likelihood of Beskos et al. (2009), the Euler method shows the worst results.

Among the alternative likelihood approaches the Kessler approximate method was more unstable than the Ozaki discretization as the proposed approximation of the covariance matrix can be non positive semi-definite for some observed points. The Kessler method is only used in this work with an expansion of conditional moments up to order two and higher order expansions could lead to more robust estimates. The Ozaki method showed results similar to the unbiased EA MCEM approach, which were the best according to the approximated likelihood criterion.

Overall, the EA MCEM based method seems to be the most appealing as it does not introduce any bias, and, in our study, was much less sensitive to the starting point than the pseudo likelihood methods. However, the difficulty of its implementation and the computation cost might reduce its interest. Moreover, its application is restricted to a specific kind of potential functions.

Based on simulations and the real dataset presented in this paper, the Ozaki method seems to provide close estimate to the one given by the EA MCEM method, and is as easy as the Euler approach to implement. In addition, it requires only weak assumptions (the drift must have an invertible Jacobian matrix at observed points) and, unlike the Kessler approach, this method is numerically stable. Therefore, we suggest to users in movement ecology the use of the Ozaki method to estimate parameters from movement data.

Figure 1 :

 1 Figure 1: Simulation of the process solution to (1) with a potential as in equation (3).The potential map driving the movement is shown in Figure1a, dark zones present high potential whereas white zones have low potential. On the three other panels, ten simulated trajectories with three different sampling schemes are given. The white dot represents the starting point x 0 of each trajectory.

Figure 2 :

 2 Figure 2: Estimation of the parameters in the case where ∆ = 0.1. The dot represents the median, the whiskers provide the 95% range of estimations. The dashed line represents the true value.

Figure 3 :Figure 4 :

 34 Figure 3: Estimation of the parameters in the case where ∆ = 1. The dot represents the median, the whiskers provide the 95% range of estimations. The dashed line represents the true value.

Figure 5 :

 5 Figure 5: Error between the median map estimate and the true map. Results are presented for each method with ∆ = 0.1 (left), 1 (center) and 10 (right).

Figure 6 :

 6 Figure 6: Distribution of the relative integrated error between the estimated map and the true one. Results are presented for each method with ∆ = 0.1 (left), 1 (center) and 10 (right).

Figure 7 :

 7 Figure 7: Left: the two sets of trajectories are presented with a different color, grey or black, depending on the vessel. Right: distribution of sampling time step for GPS tags are presented for both datasets. For confidentiality reasons, the actual recorded positions may not be shown and therefore no labels are presented on the axes.

Figure 8 :

 8 Figure8: Estimated map for the dataset of the vessel 1 (see Figure7), using four different estimation methods. The cross at the bottom right of each map is the departure harbour. The darker a zone is, the more attractive it is for the given vessel. Observed points are plotted in white in order to see the superposition between maps and trajectories.

Figure 9 :

 9 Figure 9: Estimated map for the data set of the vessel 2 (see Figure 7,) using four different estimation methods. The cross at the bottom right of each map is the departure harbour.The darker a zone is, the more attractive it is for the given vessel. Observed points are plotted in white in order to see the superposition between maps and trajectories.

Table 1 :

 1 Value of the contrast function to maximize for each estimated parameter, for each data set. Each entry is the value of the contrast function (given in column) evaluated for an estimation of θ (given in line). Highest value for each column is on the diagonal. Values are normalized contrasts (divided by the number of segments of trajectories).the one given by Ozaki and EA MCEM methods although less concentrated around the data. The acceptance rate for the conditional simulation of the EA MCEM method is 1.4%. Euler discretization method estimates a potential map with a much more spread attractive zone than the three other methods. Moreover, the orientation of this zone does not follow what seems to be the main axis of trawling (mainly East-West). Both Ozaki and MCEM EA methods provide a similar estimated map (in terms of parameters and of likelihood): a Gaussian form wrapping what appears to be the main trawling zone.

			V1				V2
	Estimate \ Contrast	E	O	K	EA	E	O	K	EA
	θ E	-1.32 -1.29 -0.37 -1.29 -2.17 -2.16 -1.07 -2.16
	θ O	-1.50 -0.91 0.39 -0.93 -2.21 -2.09 -0.90 -2.09
	θ K	-1.50 -0.96 0.70 -0.99 -2.26 -2.18 -0.67 -2.10
	θ EA	-1.49 -0.92 0.06 -0.92 -2.21 -2.11 -0.98 -2.07

Acknowledgements:

The authors would like to thank the associate editor and the anonymous referees for their meaningful comments which led to a major reorientation of this work. Meeting expenses between the three authors have been supported by the GdR EcoStat. The real data application would not have been possible without all contributors to the RECOPESCA project. The authors express their warm thanks to the leaders of this project Patrick Berthou and Émilie Leblond and to all the voluntary fishermen. The authors have also benefited from insightful discussions with Valentine Genon-Catalot and Catherine Laredo.


Sylvain Pogodalla
email: sylvain.pogodalla@inria.fr

Abstract Categorial Grammars as a Model of the Syntax-Semantics Interface for TAG

come   L'archive ouverte pluridisciplinaire

Introduction

Type System Definition (Typing Judgment) Γ; ∆ ⊢ Σ t ∶ α where: Γ is a finite set of non-linear variable typing declarations of the form x ∶ β;

∆ is a finite multi-set of linear variable typing declarations of the form x ∶ β.

Typing rules

(const.) Γ; ⊢ Σ c ∶ τ (c) (lin. var.) Γ; x ∶ α ⊢ Σ x ∶ α (var.) Γ, x ∶ α; ⊢ Σ x ∶ α Γ; ∆, x ∶ α ⊢ Σ t ∶ β (lin. abs.) Γ; ∆ ⊢ Σ λ o x.t ∶ α ⊸ β Γ; ∆ 1 ⊢ Σ t ∶ α ⊸ β Γ; ∆ 2 ⊢ Σ u ∶ α (lin. app.) Γ; ∆ 1 , ∆ 2 ⊢ Σ (t u) ∶ β Γ, x ∶ α; ∆ ⊢ Σ t ∶ β (abs.) Γ; ∆ ⊢ Σ λx.t ∶ α → β Γ; ∆ ⊢ Σ t ∶ α → β Γ; ⊢ Σ u ∶ α (app.) Γ; ∆ ⊢ Σ (t u) ∶ β
▶ an infix operator + = λ o f g .λ o z.f (g z) ∶ σ ⊸ σ ⊸ σ ▶ = λ o x.x ∶ σ
Example ( is neutral for +)

a + = + a = (λ o f g .λ o z.f (g z)) a → β (λ o g .λ o z.a(g z)) → β λ o z.a ( z) → β λ o z.a z = a Example Remark (t + u) z = ((λ o f g .λ o z ′ .f (g z ′ )) t u) z → β (λ o z ′ .t (u z ′ )) z → β t (u z)
Example (Associativity of +)

f + (g + h) = (λ o f ′ g ′ .λ o z.f ′ (g ′ z)) f (g + h) → β λ o z.f ((g + h) z) → β λ o z.f (g (h z)) (f + g ) + h = (λ o f ′ g ′ .λ o z.f ′ (g ′ z)) (f + g ) h → β λ o z.(f + g )(h z) = λ o z.f (g (h z))
Example: John of arity 0 (terminal) (Higher-Order) Signature

s 2 ∶ τ ⊸ τ ⊸ τ np 1 ∶ τ ⊸ τ vp 1 ∶ τ ⊸ τ , vp 2 ∶ τ ⊸ τ ⊸ τ

Affiliations (II)

Two levels for the grammatical architecture (Curry 1961)

Tectogrammatics: "the study of [abstract] grammatical structure in itself" (e.g., the derivations)

Phenogrammatics: "the study of the way [abstract] phrases are represented by expressions" (e.g., the yields)

The combinatorial properties of words (e.g., transitive verbs expect two np) are not described at the same place as their combinations are (e.g., SVO, SOV, etc.).

The functorial types can be undirected.

Applications

Type theoretical grammar and GF [START_REF] Ranta | Type Theoretical Grammar[END_REF][START_REF] Ranta | Grammatical Framework: A Type-Theoretical Grammar Formalism[END_REF]) Labeled categorial systems [START_REF] Bibliographie Ix Oehrle | Term-Labeled Categorial Type Systems[END_REF][START_REF] Oehrle | Ambiguïté de portée et approche fonctionnelle des TAG[END_REF]), λ-grammars [START_REF] Bibliographie | Lambda Grammars and the Syntax-Semantics Interface[END_REF][START_REF] Muskens | Lambdas, Language, and Logic[END_REF] etc.

Relating Λ(Σ trees ) to Σ strings with L yield

Σ trees ∶ τ ∶ type John, sleeps ∶ τ np 1 , . . . ∶ τ ⊸ τ vp 2 , . . . ∶ τ ⊸ τ ⊸ τ np 1 John ∶ τ λ o x.np 1 x ∶ τ ⊸ τ λ o P.P np 1 ∶ ((τ ⊸ τ ) ⊸ α) ⊸ α Λ(Σ trees ) Σ strings ∶ o ∶ type σ = o ⊸ o ∶ type John, sleeps ∶ σ + ∶ σ ⊸ σ ⊸ σ John ∶ σ λ o P.P(John + sleeps) ∶ (σ ⊸ σ) ⊸ σ Λ(Σ strings ) L yield (τ ) = σ L yield (John) = John L yield (np 1 ) = λx.x L yield (vp 2 ) = λx y .x + y L yield (α ⊸ β) = L yield (α) ⊸ L yield (β) L yield (t u) = L yield (t) L yield (u) L yield (λ o x.t) = λ o x.L yield (t) L yield (λx.t) = λx.L yield (t) L yield (α → β) = L yield (α) → L yield (β) (de Groote 2001)
Definition (Abstract Categorial Grammar)

An abstract categorial grammar is a quadruple G = ⟨Σ 1 , Σ 2 , L, s⟩ where:

Σ 1 and Σ 2 are higher-order signatures L ∶ Σ 1 → Σ 2 is a lexicon. s ∈ T A 1 is the distinguished type of the grammar.

Notations:

L(α) = β G(α) = β α ∶= β α = β ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭
all denote that the interpretation of α is β

q 0 q 1 q 2 a b b a a,b
A signature Σ FSA for transitions to q 2 Atomic Types q 0 , q 1 , and q 2

Constants δ q 0 ,a ∶ q 1 ⊸ q 0 δ q 1 ,a ∶ q 1 ⊸ q 1 δ q 2 ,a ∶ q 2 ⊸ q 2 δ q 0 ,b ∶ q 0 ⊸ q 0 δ q 1 ,b ∶ q 2 ⊸ q 1 δ q 2 ,b ∶ q 2 ⊸ q 2 F ∶ q 2 δ q 0 ,a

q 1 (δ q 1 ,a q 1 (δ q 1 ,b F )) ∶ q 0
Remark q 2 is reachable from q i iff there exists t ∶ q i ∈ Λ(Σ FSA ) FSA Example (cont'd)

q 0 q 1 q 2 a b b a a,b Σ FSA ∶ δ q 0 ,a ∶ q 1 ⊸ q 0 δ q 1 ,a ∶ q 1 ⊸ q 1 δ q 2 ,a ∶ q 2 ⊸ q 2 δ q 0 ,b ∶ q 0 ⊸ q 0 δ q 1 ,b ∶ q 2 ⊸ q 1 δ q 2 ,b ∶ q 2 ⊸ q 2 F ∶ q 2 Σ strings ∶ a, b ∶ o ⊸ o # ∶ o The G FSA ACG Type interpretation q 0 , q 1 , q 2 ∶= FSA o Constant interpretation δ q 0 ,a ∶= FSA λz.a z δ q 1 ,a ∶= FSA a δ q 2 ,a ∶= FSA a δ q 0 ,b ∶= FSA b δ q 1 ,b ∶= FSA b δ q 2 ,b ∶= FSA b F ∶= FSA # Distinguished type q 0 δ q 1 ,b F FSA = δ q 1 ,b FSA F FSA δ q 1 ,a (δ q 1 ,b F )) ∶= FSA a(b #) = b # δ q 0 ,a (δ q 1 ,a (δ q 1 ,b F )) ∶= FSA a(a(b #))
Languages of an ACG Definition (Abstract and Object Languages)

Let G = ⟨Σ 1 , Σ 2 , L, s⟩ be an ACG.
The abstract language is defined by

A(G) = {t ∈ Λ(Σ 1 ) | ⊢ Σ 1 t ∶ s is derivable}
The object language is defined by

O(G) = {u ∈ Λ(Σ 2 ) | ∃t ∈ A(G) s.t. u = L(t)} ACG parsing u ∈ Λ(Σ 2 ) Does t ∈ Λ(Σ 1 ) exists such that L(t) = u? CFG into ACG Encoding Example (CFG) ρ 0 ∶ s → np vp ρ 1 ∶ vp → vt np ρ 2 ∶ np → John ρ 3 ∶ np → Mary ρ 4 ∶ vp → left ρ 5 ∶ vt → saw ρ 0 ∶ s ρ 2 ∶ np John ρ 1 ∶ vp ρ 5 ∶ vt saw ρ 3 ∶ np Mary Σ Rules Σ Strings np, vp, vt, s ∶ atomic types ∶= CFG σ ρ 0 ∶ np ⊸ vp ⊸ s ∶= CFG λxy .x + y ∶ σ ⊸ σ ⊸ σ ρ 1 ∶ vt ⊸ np ⊸ vp ∶= CFG λxy .x + y ∶ σ ⊸ σ ⊸ σ ρ 2 ∶ np ∶= CFG John ∶ σ ρ 3 ∶ np ∶= CFG Mary ∶ σ ρ 4 ∶ vp ∶= CFG left ∶ σ ρ 5 ∶ vt ∶= CFG saw ∶ σ CFG into ACG Encoding (cont'd) CFG as ACG Σ Rules Σ Strings np, vp, vt, s ∶ atomic types ∶= CFG σ ρ 0 ∶ np ⊸ vp ⊸ s ∶= CFG λxy .x + y ∶ σ ⊸ σ ⊸ σ ρ 1 ∶ vt ⊸ np ⊸ vp ∶= CFG λxy .x + y ∶ σ ⊸ σ ⊸ σ ρ 2 ∶ np ∶= CFG John ∶ σ ρ 3 ∶ np ∶= CFG Mary ∶ σ ρ 4 ∶ vp ∶= CFG left ∶ σ ρ 5 ∶ vt ∶= CFG saw ∶ σ L CFG (ρ 0 ρ 2 (ρ 1 ρ 5 ρ 3 ) ∶ s) = (λxy .x + y )John((λxy .x + y )saw Mary) → β (λy .John + y )((λy .saw + y )Mary) → β (λy .John + y )(saw + Mary) → β John + (saw + Mary)
About Linearity

Can we generate {ωω|ω ∈ L}? Yes

Example (L is the langage of any sequence of a's and b's)

s ′ ∶ type ∶= Dup σ s ∶ type ∶= Dup (σ ⊸ σ ⊸ σ) ⊸ σ ε ∶ s ∶= Dup λf .f A ∶ s ⊸ s ∶= Dup λ o f .λ o g .f (λ o x y .g (a + x) (a + y )) B ∶ s ⊸ s ∶= Dup λ o f .λ o g .f (λ o x y .g (b + x) (b + y )) C ∶ s ⊸ s ′ ∶= Dup λ o f .f (λ o x y .x + y ) C (A (B (B ε))) ∶ s ′ ACG:
∧ ∶ t ⊸ t ⊸ t ∨ ∶ t ⊸ t ⊸ t ⇒ ∶ t ⊸ t ⊸ t ¬ ∶ t ⊸ t ∃ ∶ (e → t) ⊸ t ∀ ∶ (e → t)
⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ λ o x. s x vp sleeps ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎝ np John ⎞ ⎟ ⎟ ⎠ → β s np John vp sleeps (λ o x.s 2 x (vp 1 sleeps)) (np 1 John) → β s 2 (np 1 John) (vp 1 sleeps)
seemingly vp sleeps ⎛ ⎜ ⎜ ⎜ ⎝ λ o x. vp seemingly x ⎞ ⎟ ⎟ ⎟ ⎠ vp sleeps → β vp seemingly vp sleeps ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ λa. s np a ⎛ ⎜ ⎜ ⎜ ⎝ vp sleeps ⎞ ⎟ ⎟ ⎟ ⎠ ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎝ λ o x. vp seemingly x ⎞ ⎟ ⎟ ⎟ ⎠ Adjunction as Functional Application ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ λ o a. s np a ⎛ ⎜ ⎜ ⎝ vp sleeps ⎞ ⎟ ⎟ ⎠ ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (λ o a.s 2 np a(vp 1 sleeps)) ⎛ ⎜ ⎜ ⎜ ⎝ λ o x. vp seemingly x ⎞ ⎟ ⎟ ⎟ ⎠ (λ o x.vp 2 seemingly x) → β s np ⎛ ⎜ ⎜ ⎜ ⎝ λ o x. vp seemingly x ⎞ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎝ vp sleeps ⎞ ⎟ ⎟ ⎟ ⎠ s 2 np ((λ o x.vp 2 seemingly x)(vp 1 sleeps)) → β s np vp seemingly vp sleeps s 2 np (vp 2 seemingly (vp 1 sleeps))
Terms (of Λ(Σ trees )) for TAG Operations

γ John = np 1 John ∶ τ np John γ sleeps = λ o S a s.S (s 2 s (a (vp 1 (v 1 sleeps)))) s np vp v sleeps ∶ (τ ⊸ τ ) ⊸ (τ ⊸ τ ) ⊸ τ ⊸ τ γ seemingly = λ o a v .a (vp 2 (adv 1 seemingly) v ) vp adv seemingly vp * ∶ (τ ⊸ τ ) ⊸ τ ⊸ τ I = λ o x.x ∶ τ ⊸ τ γ sleeps I (γ seemingly I) γ John → β s 2 (np 1 John) (vp 2 (adv 1 seemingly) (vp 1 (v 1 sleeps)))
γ sleeps I (γ seemingly I) γ John ∶= yield John + seemingly + sleeps TAG as ACG (1st part)

Category Induced Constraints

The site of an adjunction has the same category as the root (and foot) node of the auxiliary tree

The site of a substitution has the same category as the root node of the substituted tree

Σ derivations Λ(Σ trees ) c John ∶ np ∶= derived trees γ John ∶ τ c seemingly ∶ (vp ⊸ vp) ⊸ vp ⊸ vp ∶= derived trees γ seemingly ∶ (τ ⊸ τ ) ⊸ τ ⊸ τ np,

Control on the Derived Trees

G derived trees = ⟨Σ derivations , Σ trees , L derived trees , s⟩ Long-Distance Dependencies

c seemingly ∶ (vp ⊸ vp) ⊸ vp ⊸ vp ∶= derived trees λ o ax.a ⎛ ⎜ ⎜ ⎜ ⎝ s seemingly x ⎞ ⎟ ⎟ ⎟ ⎠ c sleeps ∶ (s ⊸ s) ⊸ (vp ⊸ vp) ⊸ np ⊸ s ∶= derived trees λ o Sas.S ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ s s a ⎛ ⎜ ⎜ ⎜ ⎝ vp sleeps ⎞ ⎟ ⎟ ⎟ ⎠ ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ I vp ∶ vp ⊸ vp
I vp 0 1 c John 2 c likes ∶ (s ⊸ s) 0 ⊸ (vp ⊸ vp) 2 ⊸ np 1 Building a Semantic Representation Σ derivations c John ∶ np c seemingly ∶ (vp ⊸ vp) ⊸ vp ⊸ vp c sleeps ∶ (s ⊸ s) ⊸ (vp ⊸ vp) ⊸ np ⊸ s I vp ∶ vp ⊸ vp Σ logic ∧, ∨, ⇒ ∶ t ⊸ t ⊸ t ¬ ∶ t ⊸ t ∃, ∀ ∶ (e → t)
⊤[det = +] n[-] ⊸ n[+] (n[-] ⊸ n[+]) ⊸ n[+] (s ⊸ s) ⊸ (vp ⊸ vp) ⊸ n[+] ⊸ n[+] ⊸ s n ⊸ np (n ⊸ np) ⊸ np (s ⊸ s) ⊸ (vp ⊸ vp) ⊸ np ⊸ np ⊸ s
Multiple Modification

Multiple Adjunction

The ACG way G TAG = ⟨Σ TAG , Σ derivations , L TAG , s⟩ (de [START_REF] Bibliographie Iii De Groote | Tree-Adjoining Grammars as Abstract Categorial Grammars[END_REF] Types and constants of Σ TAG Their interpretations in Λ(Σ derivations ) np, s, . . . np, s, . . .

c big ∶ (n ⊸ np) ⊸ n ⊸ np ∶= sem. λ o Q n.Q (λx.(n x) ∧ (big x)) c black ∶ (n ⊸ np) ⊸ n ⊸ np ∶= sem. λ o Q n.Q (λx.(n x) ∧ (black x)) c dog ∶ (n ⊸ np) ⊸ np ∶= sem. λ o Q.Q dog λ o D.
vp A vp ⊸ vp s A s ⊸ s n A n ⊸ np C sleeps ∶ s A ⊸ vp A ⊸ np ⊸ s c sleeps ∶ (s ⊸ s) ⊸ (vp ⊸ vp) ⊸ np ⊸ s C seemingly ∶ vp A ⊸ vp A c seemingly ∶ (vp ⊸ vp) ⊸ vp ⊸ vp I s ∶ s A I s ∶ s ⊸ s I vp ∶ vp A I vp ∶ vp ⊸ vp C matters ∶ vp A ⊸ s ⊸ s c matters ∶ (vp ⊸ vp) ⊸ s ⊸ s G TAG is 2nd-order:
Parsing results apply Both from strings and from logical formulas! See the demo

Λ(Σ derivations ) Λ(Σ TAG ) G TAG Λ(Σ CoTAG ) G CoTAG np (np ⊸ s) ⊸ s Λ(Σ trees ) G derived trees Λ(Σ strings ) G yield Λ(Σ logic ) G sem.
G co-sem.

Synchronous TAG (Nesson and

  Notationsλx.λy .t = λx y .t((t u) v ) w ) = t u v w α → (β → (γ → δ)) = α → β → γ → δ infix notation: if + is a constant, (+ f ) g = f + g Introduction AbstractCategorial Grammars TAG as ACG Discussion Example: The Vocabulary of Strings Σ strings Σ strings Types o is the unique atomic type σ = o ⊸ o the type of strings (defined) Constants John, sleeps, a, b, . . . ∶ σ # ∶ o we define

cc

  likes I s (c seemingly I vp ) c John ∶ s ∶= derived trees sleeps I s (c seemingly I vp ) c John =

Example ( 1 )

 1 Paul claims John loves Mary (2) Paul claims John seems to love Mary (3) Who does Peter think Paul claims John seems to love seem john (λx.love x mary))

  (λx.obj (λy .love x y )))) See the demo! c loves (c claims I s I vp c Paul ) I vp c John c Mary ∶= sem. claim paul (love john mary) c to love (c claims I s I vp c Paul ) (c seems I vp ) c Mary c John ∶= sem. claim paul (seem john (λx.love x mary))(4) every man loves some woman ∀x.man(x) ⇒ ∃y .woman(x) ∧ love(x , y )

( 5 )

 5 big black dog black(x ) ∧ big(x ) ∧ dog(x ) (6) black big dog black(x ) ∧ big(x ) ∧ dog(x )

  c dog (c black (c big D)) ∶= sem. λ o D.D (λx.((big x) ∧ (black x)) ∧ (dog x)) λ o D.c dog (c big (c black D)) ∶= sem. λ o D.D (λx.((black x) ∧ (big x)) ∧ (dog x)) TAG as ACG: Completing the Encoding Example (To arrive on time matters) ∶ (vp ⊸ vp) ⊸ s ⊸ s Not 2nd-order! c matters I vp ∶ s ⊸ s has the type of an auxilary tree. Overgeneration Λ(Σ derivations ) Λ(Σ TAG ) G TAG Λ(Σ trees ) G derived trees Λ(Σ strings ) G yield Λ(Σ logic ) G sem.

  The Vocabulary of Trees Σ trees

	Trees Built on a Ranked Alphabet
	Alphabet
	s of arity 2 (non-terminal)
	np of arity 1 (non-terminal)
	vp? vp 1 of arity 1 and vp 2 of
	arity 2 (non-terminals)

s np John vp likes np Mary s np John vp sleeps s 2 (np 1 John) (vp 2 likes (np 1 Mary)) s 2 (np 1 John) (vp 1 sleeps)

  Formal Properties

	Higher Order Logic as an Object Language
	(Groote and Pogodalla 2004; Salvati 2006; Kanazawa and Salvati 2007; Kanazawa 2009),
	(Salvati 2007; Kanazawa 2007; Kanazawa 2008; Kanazawa 2017)
	Generative Power The Σ logic vocabulary
	Types e, t	String language	Tree language
	ACG (1,n) ACG (2,1) Constants Logical constants finite regular	finite regular
	ACG (2,2)		context-free	linear contex-free
	ACG (2,3)	non-duplicating macro well-nested multiple context-free	⊂ 1-visit attribute grammar
	ACG (2,4)		mildly context-sensitive (multiple context-free)	hyperedge replacement gram.
	ACG (2,4+n)		ACG (2,4)	ACG (2,4)
	ACG (3,n)		MELL decidability	MELL decidability
	Complexity
	ACG (2,n) parsing is polynomial, equivalent to datalog querying
	Reduces to best cases with standard techniques (magic set rewriting) with correct
	prefix Earley algorithms

  The ACG Way c claims ∶= sem. λ o adv s adv vp subj comp.adv s (subj (adv vp (λx.claim x comp))) c seems ∶= sem. λ o mod pred.mod (λx.seem x pred) c loves ∶= sem. λ o adv s adv vp subj obj.adv s (subj (adv vp (λx.obj (λy .love x y )))) c to love ∶= sem. λ o adv s adv vp obj subj.adv s (subj (adv vp

  [START_REF] Nesson | Simpler TAG Semantics Through Synchronization[END_REF][START_REF] Nesson | Synchronous and Multicomponent Tree-Adjoining Grammars: Complexity, Algorithms, and Applications[END_REF] How to go from a logical formula f (β-reduced) to some possible semantic tree that gets interpreted as f ? Similar with Interpreted Regular Tree Grammars[START_REF] Bibliographie | A Generalized View on Parsing and Translation[END_REF] Koller and Kuhlmann 2012) Curry, Haskell Brooks (1961). "Some Logical Aspects of Grammatical Structure". In: Structure of Language and its Mathematical Aspects: Proceedings of the Twelfth Symposium in Applied Mathematics. Ed. by Roman Jakobson. American Mathematical Society, pp. 56-68. Danlos, Laurence, AleksandreMaskharashvili, and Sylvain Pogodalla (2016). "Interfacing Sentential and Discourse TAG-based Grammars". In: The 12th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+12). Proceedings of the 12th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+12). Düsseldorf, Germany.de Groote, Philippe (2001). "Towards Abstract Categorial Grammars". In: Association for Computational Linguistics, 39th Annual Meeting and 10th Conference of the European Chapter, Proceedings of the Conference, pp. 148-155. ACL anthology: P01-1033.

	Conclusion Bibliographie II
	Syntactic and semantic derivations are performed synchronously: ACGs
	Flexible framework
	np Interesting computational properties , e s		t
	John Modularity by composition, and type-checking j np vp 1 Provides a unified way to extend other formalisms	e ⊸ t	e	1
	loves Integrate well with type-theoretic base semantic modelling (discourse np 2 e ⊸ e ⊸ t 2 Reversible e
	dynamics, intensionalization, etc.)	λ o os.love(s, o)
	Work in progress
	Need to interpret the semantic tree as love(j, m) Tractable 3rd-order fragments
	Logical equivalence (theoretically and practically)
	Optimization
	Semantics conservativity

FSMLNP'17 & TAG+13, Sep. 4, 2017

ACG Hierarchy

Definition (Order) The order ord(τ ) of a type τ ∈ T A is inductively defined as:

Definition (Order and complexity of an ACG; ACG hierarchy)

The order of an ACG is the maximum of the orders of its abstract constants.

The complexity of an ACG is the maximum of the orders of the realizations of its atomic types.

ACG Architecture

Composition Ability

Functional composition

Abstract language sharing (bimorphism) Parsing and generation (syntactic realization) in the usual sense: function inversion (TAG derived trees) (TAG string language) (TAG derivation trees)

Tree Adjoining Grammars

Main features

Tree grammars with two operations

Allows for an extended domain of locality [START_REF] Joshi | Preface[END_REF]): locally specify (syntactic and semantic) dependencies between parts that can occur arbitrarily far from each other at the surface level at the end of a derivation

So far. . .

A vocabulary for strings Σ strings

A vocabulary for trees Σ trees Yield of a tree as an ACG G yield TAG operations on trees as applications of terms of Λ(Σ trees )

PB: Not only TAG derived trees (e.g., γ seemingly I ∶ τ ⊸ τ and γ John ∶ τ )

TAG as ACG

A Note on Feature Structures

The ACG way corresponds to specifying adjunction constraints by enumeration

Vijay-Shanker and Joshi (1988, p. 718): ". . . if we think of the auxiliary tree as corresponding to functions over feature structures (by λ-abstracting the variable corresponding to the feature structure for the tree that will appear below the foot node). Adjunction corresponds to applying this function to the feature structure corresponding to the subtree below the node where [it] takes place."

Quantification

The ACG Way The ACG toolkit (http://calligramme.loria.fr/acg#Software)

Signatures, lexicons, and scripts available from my publication page as related file to this presentation (http://hal.inria.fr/hal-01583962/file/examples.zip)

Principles:

Semantic features are added (typically [Ind = x], [P = l] where l is the label of some logical formula)

A representation language specifying the relations between the labels is used to plug together the logical formulas Limitations:

No control on whether a feature that is asked at some node will be provided by another node (no static typing)

Need to handle variable naming on-line (no α-conversion)

The lack of functional application requires using labels (first-order unification)

How to inverse the process?