Ioannis Baraklianos
email: ioannis.baraklianos@entpe.fr

Patrick Bonnel

Does the accessibility measure influence the results of residential location choice modelling?

Keywords: Accessibility measurement, residential location choice modelling, MNL model, Lyon urban area, LUTI

Accessibility is essential in Land-Use Transport Interaction (LUTI) framework. For residential location choice in particular, it has always been important at theoretical level. At empirical level, the place of accessibility is doubt in some case studies, considering other location characteristics more important, like the social environment and the neighbourhood amenities. However, this result can be caused by the measurement of accessibility. In view of the wealth of approaches, this paper examines whether different accessibility measures can lead to divergent results. Using a residential location choice model for the Lyon urban area, we test various accessibility indicators and we compare the results. Accessibility is an indispensable variable, whatever is the measure. Without it, the model gives inconsistent results. Complex accessibility measures give better results but simple measures are also relevant for residential location choices modelling. The choice depends heavily on the objectives of the application especially if the model is to be used for simulation.

Introduction

Accessibility is central to Land-Use Transport Interaction (LUTI) models [START_REF] Acheampong | Land use -transport interaction modeling : A review of the literature and future research directions[END_REF][START_REF] Bonnel | Croissance urbaine et accessibilité : intérêts et limites de l'approche par les densités dans une perspective de modélisation de l'usage du sol[END_REF][START_REF] Zondag | Accessibility modeling and evaluation: The TIGRIS XL land-use and transport interaction model for the Netherlands[END_REF], playing an important double role. On the one hand, it is one of the main results of the simulation process, facilitating the decision-making. On the other hand, it is one of the key variables in the location choice models of households and firms as it expresses the main effect of the transport system [START_REF] Zondag | Accessibility modeling and evaluation: The TIGRIS XL land-use and transport interaction model for the Netherlands[END_REF] quantifying the potential interaction between land use and transportation system [START_REF] Hansen | How Accessibility Shapes Land Use[END_REF].

At theoretical level, accessibility is an important determinant in residential location choice models [START_REF] Alonso | Location and land use : toward a general theory of land rent[END_REF][START_REF] Lowry | A model of metropolis[END_REF]. In empirical models however, a significant relation between accessibility and residential location choice is rather hard to be proven [START_REF] Blijie | The impact of accessibility on residential choice : Empirical results of a discrete choice model[END_REF][START_REF] Lee | Reexamining the influence of work and nonwork accessibility on residential location choices with a microanalytic framework[END_REF]. Some studies have questioned the importance of accessibility concluding that other location attributes like social environment, neighbourhood amenities and dwelling characteristics are more important [START_REF] Blijie | The impact of accessibility on residential choice : Empirical results of a discrete choice model[END_REF][START_REF] Sener | Accommodating spatial correlation across choice alternatives in discrete choice models: an application to modeling residential location choice behavior[END_REF][START_REF] Zondag | Influence of Accessibility on Residential Location Choice[END_REF]. Others, consider accessibility as essential in the estimation of residential location choice models [START_REF] Eliasson | The Influence of Accessibility on Residential Location[END_REF][START_REF] Srour | Accessibility Indices: Connection to Residential Land Prices and Location Choices[END_REF] and conclude that accessibility is important even in a polycentric urban structure [START_REF] Lee | Reexamining the influence of work and nonwork accessibility on residential location choices with a microanalytic framework[END_REF]. Many factors can contribute to these divergent results like the modelling choices (analysis level, explanatory variables, model structure and market segmentation) or the local particularities (in areas where the transport services are good, the importance of accessibility tends to decrease). These controversial results might be explained by the fact that the definition and measurement of accessibility has not been thoroughly examined in LUTI literature.

In the context of the residential location choice, a great variety of accessibility measures is applied [START_REF] Schirmer | The role of location in residential location choice models: a review of literature[END_REF], from simple to complex ones. A simple definition can be the proximity to transport infrastructure or a Euclidian distance of a location to the city centre, as it was implemented in the first works of [START_REF] Alonso | Location and land use : toward a general theory of land rent[END_REF]. More complex definitions of accessibility, integrate the individual taste, preferences and capabilities to travel and are based on more advanced modelling techniques.

However, "accessibility is often a misunderstood, poorly defined and poorly measured construct" (Geurs and van Wee, 2004, p. 127). Translating its influence in residential location choice context, where the decision depends on various dimensions can be a complex task. Measurement choice of accessibility can potentially influence the conclusions that one draws on the importance of accessibility.

Recent researches have questioned the sensitivity of the modelling results to the accessibility measure in other frameworks. [START_REF] Boisjoly | Daily fluctuations in transit and job availability: A comparative assessment of time-sensitive accessibility measures[END_REF], using public transport share regression models, analysed the influence of time sensitive accessibility measures to the results of modal choice modelling. [START_REF] Bunel | Key Issues in Local Job Accessibility Measurement: Different Models Mean Different Results[END_REF], in the framework of spatial mismatch, examined if the results of local job accessibility modelling depend on the measurement strategy. But in the context of the residential location choice modelling, to our knowledge, little research have analysed the effect of the accessibility measure. One exception is the work of [START_REF] Srour | Accessibility Indices: Connection to Residential Land Prices and Location Choices[END_REF] for Dallas-Fort Worth, who applied two different accessibility measures (cumulative opportunities and logsum from a trip-based model) to three activities (work, park, shopping).

Our objective is to extent [START_REF] Srour | Accessibility Indices: Connection to Residential Land Prices and Location Choices[END_REF] work, analysing the influence of accessibility measurements on the results of a residential location choice model. More precisely we would like first to confirm the importance of accessibility measurement, even if very simple definitions are used, in residential location choice model, and secondly to assess the benefit of using more sophisticated measurement of accessibility. We developed an empirical application for the urban area of Lyon. Our application is based on previous works which allowed to develop a residential location choice [START_REF] Aissaoui | Choix de localisation résidentielle, entre contraintes du marché et préférences individuelles : application à l'aire urbaine de Lyon 1999[END_REF][START_REF] Kryvobokov | Willingness to pay for accessibility under the conditions of residential segregation[END_REF].

Usually, the decision on the best accessibility measurement is based on model statistical indicators. In our work, we will both analyse model statistical indicators but also market share predictions of location choices. When developing models for planning it is important to get good statistical indicators but also to reproduce correctly observed market share. Our work aims to provide guidance to modellers and decision makers on making better and faster decisions regarding the use of accessibility in residential location choice modelling.

The rest of the paper is structured as follows. Section 2 presents accessibility theory in the framework of residential location and applied measurement methods used in residential location choice. Section 3 presents the study area, the data, the accessibility measures, the residential location choice model and our evaluation strategy. Section 4 presents the modelling results while the last 2 sections outline the discussion of the results and the conclusions of the article.

Accessibility and residential location choice: one concept, different approaches, different results?

The concept of accessibility is difficult and complex due to the fact that it is a multicomponent and a multidimensional construct [START_REF] Boisjoly | Daily fluctuations in transit and job availability: A comparative assessment of time-sensitive accessibility measures[END_REF][START_REF] Cascetta | A behavioral model of accessibility based on the number of available opportunities[END_REF][START_REF] Geurs | Accessibility evaluation of land-use and transport strategies: review and research directions[END_REF][START_REF] Niedzielski | Travel Time and Distance as Relative Accessibility in the Journey to Work[END_REF] for which the measurement methods are not yet standardised [START_REF] Acheampong | Land use -transport interaction modeling : A review of the literature and future research directions[END_REF].

The accessibility is a construct of three components, transportation, activities and individuals [START_REF] Niedzielski | Travel Time and Distance as Relative Accessibility in the Journey to Work[END_REF]. Those three components evolve in two dimensions, in space and time [START_REF] Geurs | Accessibility evaluation of land-use and transport strategies: review and research directions[END_REF]. Initially, accessibility was not conceived as a multicomponent and multidimensional concept. It was merely a two-component concept within the spatial dimension [START_REF] Hansen | How Accessibility Shapes Land Use[END_REF], defined as the interaction between transport and land use. Further research then highlighted the importance of individual component [START_REF] Ben-Akiva | Discrete Choice Analysis: Theory and Application to Travel Demand[END_REF] and temporal dimension [START_REF] Hägerstrand | What About People in Regional Science ? 9th[END_REF]. Accessibility gains on theoretical developments were posterior to advances of empirical methods in several fields, particularly in economics and geography. This led to a fragmentation of the applied methods, points of view, methodological processes and assumptions1 .

Residential location choice is heavily influenced by accessibility. Areas with high accessibility provide a better quality of life [START_REF] Niedzielski | Travel Time and Distance as Relative Accessibility in the Journey to Work[END_REF]. Households can make shorter and more optimised travels due to trip-chaining [START_REF] Hu | Job accessibility and employment outcomes: which income groups benefit the most? Transportation[END_REF]. Different components can have different influence on residential locations. Transport infrastructure could be an opportunity for household members as it increases their ability to travel. However, it can create negative externalities such as pollution, which can discourage a household from locating in close proximity. Such long-term decisions, as residential location, are affected by the spatial distribution of the activities in which household's members participate like employment, shopping and leisure [START_REF] Wegener | Land-Use Transport Interaction: State of the Art[END_REF].

More opportunities easily accessible increases potential activity participation, especially for nonmandatory purposes [START_REF] Cordera | Is accessibility relevant in trip generation? Modelling the interaction between trip generation and accessibility taking into account spatial effects[END_REF]. Individual preferences and capabilities influence activity participation and transportation preferences. The access to spatially distributed opportunities from a residential location and the potential need for travel are related to individual caracteristics [START_REF] Ben-Akiva | Discrete Choice Analysis: Theory and Application to Travel Demand[END_REF][START_REF] Wegener | Land-Use Transport Interaction: State of the Art[END_REF]. All these choices are constrained by the individual space-time activity prism [START_REF] Hägerstrand | What About People in Regional Science ? 9th[END_REF], which limits the ability of individuals to participate in all desired activities within the space and the time of the day.

Translating these components and dimensions of accessibility into indicators is not an easy task.

Accessibility indicators that incorporate individual component and temporal dimension, require data and modelling techniques that are not always available. In residential location choice literature, the transport and land use components are integrated through location-based accessibility measures (distance to centre, cumulative opportunities, potential accessibility), which capture mostly the spatial dimension of accessibility. The individual component is integrated either by interacting location-based accessibility measures with households characteristics or by using logsum accessibilities derived by trip-based or activity-based transportation models2 . The temporal dimension is integrated usually within the transport component (peak-on times). In Table 1, we present some empirical studies of residential location choice models to illustrate the diversity of the measures and the conclusions on the importance of accessibility. We have not set out to be exhaustive but to give some representative recent research, which illustrates our research question.

In Paris [START_REF] De Palma | Accessibility and Environmental Quality : Inequality in the Paris Housing Market[END_REF], the distance to motorways and the number of railway and subway stations were significant when the analysis was made at commune level while they were not when the model was calibrated at grid cell level. Distance to the centre was significant only when analysis was conducted at commune level. The authors highlighted that the accessibility to transport infrastructures is more important than the negative externalities they can cause. In Dallas-Fort Worth, [START_REF] Srour | Accessibility Indices: Connection to Residential Land Prices and Location Choices[END_REF] using logsum accessibilities and cumulative opportunities measures, found that accessibility employment is more important than accessibility to shopping and parks and concludes that cumulative opportunities measure is the most appropriate. For the same study area, [START_REF] Guo | Operationalizing the concept of neighborhood: Application to residential location choice analysis[END_REF] found that the perception of accessibility can vary based on the households characteristics. In general, accessibility to employment has negative impact on a location choice, but higher income and oneindividual households tend to choose locations with good accessibility to employment. Eliasson (2010), using logsums, calculated by activity-based model for Stockholm, found that the attractiveness of a location was positively influenced by the accessibility to workplaces and to other activities like services, shopping etc. The author concludes that accessibility is key in location choice models but one must include it to various activities and not only to employment. [START_REF] Cho | The role of employment subcenters in residential location decisions[END_REF] using a logsum accessibility to 10 different employment centres in Mecklenburg County, a polycentric urban form, found that in general accessibility to employment is a determinant factor for a residential location choice. Then, using market segments by income, they found that households appreciate accessibility to different employment centres depending on the specialization of the centre. [START_REF] Lee | Reexamining the influence of work and nonwork accessibility on residential location choices with a microanalytic framework[END_REF] in their application for the Puget Sound region, found that the logsum of trips to work, estimated by an activity-based transport model, was significant for residential location choice, even after controlling for other location, neighbourhood and dwelling attributes. Additionally, to our knowledge, this was the only application that have integrated a space-time measure in a residential location choice model. They used the opportunities-based approach 3 and found that the shopping opportunities on the work-tohome trip had a significant influence. The fact that this type of measure is not commonly applied in residential location choice modelling may be due to empirical difficulties [START_REF] Boisjoly | Daily fluctuations in transit and job availability: A comparative assessment of time-sensitive accessibility measures[END_REF][START_REF] Cascetta | A behavioral model of accessibility based on the number of available opportunities[END_REF][START_REF] Geurs | Accessibility evaluation of land-use and transport strategies: review and research directions[END_REF]. Some studies question the importance of accessibility for residential location choice. In the Netherlands, [START_REF] Blijie | The impact of accessibility on residential choice : Empirical results of a discrete choice model[END_REF] found that the distance to motorway ramps was significant for three household types and that the household's car ownership influences this sensitivity. At the same time, the distance to a railway station was significant for only one household type. The author argues that accessibility has only a marginal influence on residential location choice. [START_REF] Zondag | Influence of Accessibility on Residential Location Choice[END_REF], for the same study area and using similar modelling approach (market segments), found that activitybased logsums for work and education trips did not have significant influence. However, the logsums for "all trip purposes" or "other trips" were significant but only for some household types. Their final conclusion is that accessibility has a minor influence on residential location choice. [START_REF] Sener | Accommodating spatial correlation across choice alternatives in discrete choice models: an application to modeling residential location choice behavior[END_REF], using two different modelling strategies (Multinomial logit and Distance-based Spatially Correlated logit), in their application for the San Francisco Bay Area, found that zonal motorway density was significant only when the Multinomial logit model was used, while the household commute time to work (the sum of working household members) had always significant negative influence. Moreover, 3 For a review of space time accessibility measures see [START_REF] Cascetta | A behavioral model of accessibility based on the number of available opportunities[END_REF] the number of household members with work location within 30 minutes by Public Transport is positive and significant. However, they found that location-based accessibility measures were insignificant, without specifying the applied accessibility measure. The study for the Dallas-Fort Worth metroplex [START_REF] Guo | Residential Location Choice Modeling : Accommodating Sociodemographic , School Quality and Accessibility Effects[END_REF], using potential accessibility measures to employment, shopping and leisure opportunities, found that only accessibility to shopping opportunities was significant for all households while the other two were sensitive to household characteristics (education level of the head and the race of the household). They conclude that accessibility to general employment is not important except for the educated workers.

In this paper, we set a threefold objective. First, we test various measures to examine if accessibility influences the location choice modelling results. The existing studies have applied many different accessibility indicators to different contexts, so their results are not comparable. Potentially, accessibility measures can influence this result. Second, we analyse to what extend different households appreciate accessibility differently and how this fact affects the modelling results. Third, we examine the ability of the model to replicate the observed choices. This indicator of model quality is important when the model is to be used for planning purposes even if not often used in literature.

Methodology and data

Study area

Lyon urban area is the second most populated urban area in France after Paris. In total, the urban area had more than 750,000 jobs in 2006, of which more than 40% were concentrated in the area's central municipalities (Lyon-Villeurbanne) and almost 75% inside so-called "Grand Lyon", which is made up of the city of Lyon and some suburbs (fig. 1).

Accessibility indicators

We consider accessibility as a location characteristic. We use simple indicators, like the proximity to transportation infrastructure, or more complex ones, like the potential accessibility. Concerning activity to which the accessibility was estimated, we retained only the general employment for two reasons. Firstly, accessibility to employment is central to residential location choice modelling at both theoretical [START_REF] Alonso | Location and land use : toward a general theory of land rent[END_REF][START_REF] Lowry | A model of metropolis[END_REF]) and empirical levels [START_REF] Guo | Operationalizing the concept of neighborhood: Application to residential location choice analysis[END_REF][START_REF] Wegener | Land-Use Transport Interaction: State of the Art[END_REF]. It influences the prospect of residents finding a job, facilitates activity participation and affects the quality of life [START_REF] Hu | Job accessibility and employment outcomes: which income groups benefit the most? Transportation[END_REF][START_REF] Niedzielski | Travel Time and Distance as Relative Accessibility in the Journey to Work[END_REF]. Secondly, for our study area, the number of jobs and thus accessibility to employment is highly correlated with shopping or leisure activities (see table 2). In all cases the correlation of the number of jobs is higher than 0.75, so correlation between accessibilities can be much higher depending on the measure. When we have multiple transport modes serving an area, we have to aggregate measures by mode in order to calculate a composite accessibility. Usually, the aggregation is performed at the impedance [START_REF] Geurs | Accessibility measures: review and applications[END_REF]. For the aggregation of the generalised times, we applied a method developed by [START_REF] Bhat | Modeling the Generation and Organization of Household Activity Stops[END_REF]. The result is a composite generalised time, which combines times by car and Public Transportation (PT). This formulation was chosen because it is compatible with the concept of accessibility; the increase in transportation solutions is associated with an increase of accessibility [START_REF] Handy | Measuring accessibility: An exploration of issues and alternatives[END_REF]. The idea is when an Origin-Destination (OD) pair is served by both car and PT, the impedance should be less than the faster mode. This is because more transportation solutions give more mobility options and it is easier to commute between this OD.

Thus, accessibility should be higher. On the contrary, when there is no PT service, only the option of the car is available and composite generalised time is equal to the generalised time by car. There are other methods as well which give composite impedance, like the combination of modes using market shares or keeping only the fastest mode. However, the retained method is theoretically consistent with the concept of accessibility and gives the best results in the residential location choices context. The generalised time by car is the reference time for all pairs of OD. Depending on the availability of modes, the composite generalised time is given by equation 1 (only car available) or by equation 2 (both options available).

: Composite generalised time from i to j : Generalised time for car :Generalised time for PT When there is no PT connection (1)

When there is PT connexion (2)

The selection of the measures was made in order to progressively improve the accessibility quality measurement. The applied measures are:

• Proximity to transportation infrastructure • Proximity to motorways, metro, tramway or railway station as dummy variable that takes the value 1 if the zone disposes one station or a motorways passes through, otherwise is 0

• The linear distance from the centroid of each alternative zone to the centre (equation 3).

(3)

• Generalised time to access by car to city centre (equation 4).

(4)

• Generalised time to access by car to secondary centres (see fig. 2) (5)

• Potential accessibility to employment i.e. the sum of the number of employment opportunities D at location j weighted by an impedance function. Two impedance functions are retained:

• Linear distance as impedance factor (see equation 6.1).

• A negative exponential impedance function using generalised times by car and by PT (see equation 6.2), with a β value of 0.12 for car and 0.10 for PT calibrated using the household travel survey [START_REF] Bouzouina | Inégalités d'accessibilité à l'emploi en Transport Collectif Urbain : Deux décennies d'évolutions en banlieue lyonnaise[END_REF]). This indicator is used with simple generalised times (separate accessibilities by car and PT) and composite generalised times (equation 2). (6.1) (6.2)

Residential location choice model

The modelling method used in this study is based on discrete choices [START_REF] Mcfadden | Modelling the choice of residential location[END_REF]. In discrete choice modelling the decision-maker selects the alternative, from an available choice set, which maximises his utility [START_REF] Schirmer | The role of location in residential location choice models: a review of literature[END_REF]. In residential location choice, the decision-maker is the household, and the alternatives can be large zones, small neighbourhoods or even buildings. The individual utility is composed by a deterministic observable part and a random term (equation 7). The observable utility depends on the characteristics of the alternatives (zonal, dwelling etc.) or the characteristics of the individuals.

: Utility of household n at location i : Deterministic part of the utility : The error term (7) Our residential location choice model is a Multinomial Logit (MNL) model with 6 random choices of alternatives for every observed choice [START_REF] Aissaoui | Choix de localisation résidentielle, entre contraintes du marché et préférences individuelles : application à l'aire urbaine de Lyon 1999[END_REF]. When there is a large number of alternatives, as it is in our case, we can estimate a MNL model using a sample of alternatives of the true choice set and get consistent parameters [START_REF] Mcfadden | Modelling the choice of residential location[END_REF]. After testing for various sample sizes, we concluded that 6 is the best number of alternatives in terms of the stability of the parameters and the estimation speed.

The probability of household i making the choice n is given by the exponential of the utility of the observed choice divided by the sum of the exponential of the utilities of the random alternatives j (Equation 8). For our modelling needs, the Lyon urban area is divided into 432 neighbourhoods4 .

: Deterministic part of the utility of household n at i : Deterministic part of the utility of alternatives j in

: the random choice set (8)

The variables of the model are divided into three categories. The first describe local spatial amenities including basic local shopping opportunities and the education services. The second describe the social environment of the neighbourhood, including variables that reveal income self-segregation effects and a proxy for endogenous amenities along with the sensitivity to social housing capturing the sensitivity to social proximity. Self-segregation variables for 1 st and 2 nd quantile of revenue were not included because they are highly correlated with the social housing variables. The third category includes the variables of the market trade-off, which includes housing price and accessibility. The variables are presented in detail in Table 5. A drawback of the selected accessibility measures is their failure to integrate the individual dimension (see table 6), which is an important dimension of accessibility (Geurs and van Wee 2004) having a significant role in residential location choice. We interact certain household characteristics with accessibility measures in the location choice model in order to capture individual taste variations. The selected characteristics were: status, education level of the head of the household and household size.

The same household characteristics have also been employed in other studies [START_REF] Frenkel | Residential location choice of knowledge-workers: The role of amenities, workplace and lifestyle[END_REF][START_REF] Guo | Operationalizing the concept of neighborhood: Application to residential location choice analysis[END_REF][START_REF] Guo | Residential Location Choice Modeling : Accommodating Sociodemographic , School Quality and Accessibility Effects[END_REF][START_REF] Hu | Job accessibility and employment outcomes: which income groups benefit the most? Transportation[END_REF][START_REF] Millsap | Location choice in early adulthood: Millennials versus Baby Boomers[END_REF]. It is the first global measure because we have a relative value of accessibility for all zones. However, the measure incorporates is a strong assumption at the spatial dimension concerning both the land-use component (all employment to city centre) and the transport component (homogenous space).

Time to centre (car) Model 4

Time represents better the ability to travel to the city centre. We use only the generalised time by car. It relaxes the assumption of the transport component but not for the land-use component. Temporal dimension is present because we are referring to peak-on generalised times.

Time to centre + 2 nd centres (car) Model 5

To bypass the assumption of the influence of the main centre, we integrate a secondary accessibility measure, the time to secondary centres. We maintain the main centre since it must have an effect even with a presence of secondary ones.

This method relaxes the assumption of the spatial distribution of employment opportunities, but not completely.

Cumm. Opp. car Model 6

It is a measure that relaxes the assumptions of the spatial dimension of the landuse, since we do not restrict the influence only on some central areas. However, the a priori definition of the contour threshold poses a strong assumption on the influence of the spatial distribution of land-use. Only employment within the defined threshold counts.

Pot. Acc. Distance Model 7

The potential accessibility measure overcomes the drawbacks of the cumulative opportunities measure. As a first step, we integrate only the linear distance as a friction. It poses a hypothesis that the transport component is homogenous in space.

Pot. Acc. car Model 8

To overcome the simplicity of the linear distance as a friction, we integrate only the car as a transport mean.

Pot. Acc. car + PT Model 9

We add the potential accessibility by PT in order to capture the joint effect of the two means of transportation.

Pot. Acc. Composite Model 10

Because the integration of two accessibility measures creates multicollinearity, we integrate a potential measure using a composite generalised time.

Accessibility * Nb Indiv. Models 3-1, 7-1, 8-1, 10-1

In order to account for individual taste heterogeneity of accessibility, we introduce various interactions between household characteristics and accessibility measures. The first household characteristic is its size. The number of individuals in a household defines the effect of accessibility. The biggest the household, the biggest the need for space. Usually accessible areas lack on available space.

Accessibility * HH Education Models 3-2, 7-2, 8-2, 10-2

The education level of the household head can define the preference for accessibility. Highly educated individuals have a diverse activity programme [START_REF] Frenkel | Residential location choice of knowledge-workers: The role of amenities, workplace and lifestyle[END_REF] and accessibility is important.

Accessibility * HH Status Models 3-3, 7-3, 8-3, 10-3

The status is essential for the impact of accessibility. Students and households with no stable employment status are more sensible to accessibility. They have a diverse activity programme and they do not have a stable job, so high accessibility to employment is essential.

Evaluation method

In order to evaluate and compare the results of the models according to the selected accessibility measures we implemented various indicators:

 The likelihood ratio test (equation 9), using a standard incremental approach in order to analyse the contribution of each variable to the model [START_REF] Ben-Akiva | Discrete Choice Analysis: Theory and Application to Travel Demand[END_REF].

: Log-likelihood of the restricted model : Log-likelihood of the unrestricted model (9)

 The adjusted rho-squared which reveals the quality of the model fit.

 Analysis of the stability of the models' parameters.

 The ability to replicate the observed market shares, which is used to validate the modelling results in other applications [START_REF] Cordera | Is accessibility relevant in trip generation? Modelling the interaction between trip generation and accessibility taking into account spatial effects[END_REF]. For that, we analyse the differences between the observed market shares and the replicated ones using the Root Mean Squared Error (RMSE -equation 8) [START_REF] Fox | Temporal transferability of models of mode-destination choice for the Greater Toronto and Hamilton Area[END_REF][START_REF] Washington | Statistical and econometric methods for transportation data analysis[END_REF]. To apply the RMSE, we aggregated the zoning system in 5 principal zones (fig. 3). It is more convenient to present the results in 5 zones and to identify the source of the error.

: Observed market share in j : Replicated market share in j : Number of alternative zones in (8)

Fig. 3 The zones of the urban area retained for the RMSE analysis

Analysis of the results

In this section, we present the results of the estimated models. Tables 7 and8 summarise the results of the models and tables 9 and 10 present the model performances to replicate the market shares.

Analysis of the model parameters

Nearly all parameters are significant in almost all models. Accessibility affects the other variables of the model but they mostly stay significant. The parameters of proximity to spatial amenities are positive and significant and their values are relatively stable across the models. In the following, we focus mostly on the variables of accessibility and on the group of market trade-off.

In the base model, the parameter of the housing price is positive and significant, which is inconsistent [START_REF] Guevara | Critical assessment of five methods to correct for endogeneity in discrete-choice models[END_REF]. In model 2, the proximity to metro, tramway and railway stations has a positive effect, which confirms the positive effect of the presence of PT stations, while the proximity to motorways has a negative one. The latter may be due to the negative externalities of the motorways such as noise and pollution. Accessibility variables in models 3 to 10 have the expected signs (negative for distance or time to city centre and positive for cumulative opportunities and the potential accessibility measures). The parameters of the housing price is always negative and significant. It seems that the simple definition of accessibility as a proximity to transport infrastructure at local level leads to inconsistent modelling results. When we apply measures that capture the global effect of the accessibility, they give better results regarding the parameters, even simple definitions like the linear distance to city centre.

Table 8 presents the results of the models with the inclusion of individual taste variation of accessibility. We present the results for only four accessibility measures which interact with households characteristics5 . The different parameter values confirm that the preference of accessibility changes depending on household's characteristics. Households with one or two individuals are more sensitive to accessibility than households with three or more individuals (models 3 -1, 7 -1, 8 -1, and 10 -1). Households whose head has low education level are not as sensitive to accessibility as households whose head has medium or high education level (models 3 -2, 7 -2, 8 -2, and 10 -2).

Regarding household head status, students are the ones who are searching for areas with high accessibility, followed by the actives with no stable contract (models 3 -3, 7 -3, 8 -3, and 10 -3), followed by households whose head has a stable job or is not active (mostly retired). These results are consistent for all accessibility measures. The relative sensitivity to accessibility is the same between the models, even for the ones that we have not included in table 8.

Model quality and statistical contribution of accessibility

The likelihood ratio test is always significant, meaning that whatever is the measure, the contribution of accessibility in the model is always significant. The inclusion of secondary employment centres indicators (see Map 2) and accessibility by PT increases the quality of the model significantly as well.

Last, the integration of individual taste variation has also a significant contribution.

Regarding the overall quality of the models, it increases with the improvement of the accessibility measure. The rho-squared of the model 2 (proximity to transportation infrastructure) 0.231 is smaller than models 3 to 10 whose rho-squared varies between 0.235 and 0.255. An exception is the model 6 (cumulative opportunities). The cumulative opportunities measure is generally considered as a better accessibility measure [START_REF] Geurs | Accessibility evaluation of land-use and transport strategies: review and research directions[END_REF] than the proximity to transportation infrastructure or the distance to city centre but the rho-squared does not confirm this result. The model 7, has the best overall rho-squared, even though in theory this indicator is inferior to the ones in models 8 to 10. In the three last models, the inclusion of the PT as a separate indicator increases the quality of the model, from 0.251 for the model 7 and 0.252 for the model 8. Nevertheless, the rho-squared is higher when we use a composite generalised time (0.254).

All the models with individual taste variation have higher rho-squared. The most appropriate household characteristic is the status of the household head and the second best characteristic is the size of the household. Between the models with individual taste variations, the best model in terms of rho-squared in the model 10-3, the one with the potential accessibility using the composite generalised time.

Ability to replicate market shares

In this chapter we analyse the model capability of replicating the market shares. Tables 9 and10 present the results of the model's performance. We present for each model the difference between observed and replicated market shares and the RMSE.

Generally, most of the models struggle to replicate the share of the city centre. There is a relation between model quality measured by rho-squared and replicated market shares, with some exceptions.

Model 1 has the highest RMSE (8.87%) meaning that it gives the worst replications. Most of the error comes from the replication of the share of the centre. When we use the proximity to transport infrastructure, the RMSE is relatively high (7.83%). This definition of accessibility cannot replicate the attractiveness of the city centre neither and it overestimates the shares of the East and West areas.

However, it achieves good replication of the 3 rd belt.

The use of distance to centre (RMSE 5.42%) improves market shares replication in comparison with model 2. It underestimates to a lesser extent the share of the city centre (difference -9.3%) but it underestimates the share of the 3 rd belt. The use of the time by car to city centre, increases the performance of the model (RMSE of 3.97%). Still the most problematic zone is the centre, but the underestimation is decreasing in comparison to previous models. Model 4 replicates better the shares of all the zones in comparison to the model 3. We have seen previously that model 5 had higher rhosquared than model 4. However, the replication of the observations is not better, with RMSE of 4.20%. This is because it increases the underestimation of the share of the centre.

The RMSE of the model 6 is 6,43%, which is the second worst between the analysed models, only better than the RMSE of the model 2. It mostly fails to replicate the share of the city centre (underestimation of 11.4%) and the share of the East Areas (overestimation of 6.6%). Contrary to the cumulative opportunities, the potential accessibility measures give very good replicated market shares, even in the form with the linear distance as a friction parameter. The model 8 gives the best performance between the models without individual taste variations, with RMSE of 1.09. The error is equally distributed between all zones (between 1.3% and -1.5%). This means that there is no particular zone that poses problem. The addition of the potential accessibility by PT in model 9, gives perfect replication for the centre (0% error) but it decreases the quality of replication for the West Areas and consequently the RMSE is 1.16%. The model 10 was the second best in terms of model quality.

However, the RMSE (1.57%) is the worst between the potential accessibility measures. The use of the composite generalised time decreases the quality of the replicated market share of the centre (underestimation of 1.9%) and of the East Areas (overestimation of 2.8%).

The addition of individual taste variations in the model concerning the accessibility does not always increase the performance of the replication of the observed market shares. The inclusion of the household characteristics in model 3, decreases the error of the replications in all cases. Concerning the potential accessibility measures we observe two cases. On the one hand, none of the models with the potential accessibility by distance or by car is able to give a better RMSE than the models without the household characteristics. On the other hand, the inclusion of individual taste variation in the model using the composite generalised time, increases the quality of the replicated market shares, when we use the household status, which gives the best replication between all models. However, the error is not as evenly distributed as it is using the model 8. -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 Log of likelihood

Discussion

The main result of this study is that accessibility remains a key variable in residential location choice modelling whatever is the measure. Even very simplistic measures of accessibility give significant results. The inclusion of accessibility in the model increases significantly its quality in all cases and corrects for the non-intuitive sign of housing price. Generally, the comparison of the different accessibility indicators has shown that the results are not radically different despite the quality differences. All the measures give consistent results, the parameters have stable signs and the selected household characteristics have the same sensitivity to all accessibility measures.

Between the measures that include the land-use component, the potential accessibility measure should be preferable even at its simplest form. On the contrary, the application of the cumulative opportunities measure should be made with care due to sensitivity to contour limit definition6 . In our case, we obtained the best results for the limit of 12 minutes, but there is no behavioural evidence explaining this result.

If we consider that market share replication is an important indicator of model quality for simulation purposes, the best model is not the one with the highest rho-squared. Simple measures of accessibility without the land-use dimension are struggling to replicate the observed market shares. Tests show that even simple employment density is not able to capture this preference7 . When there is a need for simulation, potential accessibility indicators are preferable, even the simplest ones (for example linear distance as a friction). The inclusion of individual taste variations is useful from an analysis point of view but it does not ameliorate the replication of the market shares. In some cases, it even deteriorates the results. This is due to the heterogeneity inside the selected household groups, which sometimes can be very important.

The analysis shows that when a household chooses a location, all the components of accessibility are important. The analysis of the ability of the model to replicate the observed market share reveals that models without accessibility measures fail to replicate the attractiveness of the centre. People choose to live in the city centre for the number of employment and activity participation opportunities.

Accessibility measures, which integrate the combined effect of land-use and transportation, achieve to capture this preference.

Conclusions

The objective of this paper is to give some answers to the question of whether the type of the accessibility measure can influence the estimation results of a residential location choice model. The literature analysis has shown that there is an abundance of accessibility measures but their influence on residential choice behaviour is not easily identified [START_REF] Blijie | The impact of accessibility on residential choice : Empirical results of a discrete choice model[END_REF]. For our analysis, we have selected various measures, from very simplistic to more complex ones. Individual taste variation was introduced by interacting in the model household characteristics with accessibility. We analysed the ability of the different models to replicate the observations.

With regard to the debate around the significance of accessibility in residential location choice, we take the view that transportation and land-use modellers must integrate some sort of accessibility measure in their models. Omission of accessibility measures could lead to erroneous results. The measure it-self does not influence significantly statistical indicators of models quality. In case of absence of data, and especially when there is no simulation objective, the use of simple measures can be justified. However, the results of the forecast will be improved with the use of comprehensive measures. The inclusion of the land-use component is important, even if the transport dimension is simplified. If the objective is to assess transportation policies, where significant travel time changes are expected, a measure sensible to time or cost should be chosen. For simulation, individual characteristics interaction with accessibility should be introduced with care.

The results of our analysis show the importance of the land-use component into the accessibility analysis. From a policy point of view, decision makers should take into consideration that residential policies focusing only on transportation will not be sufficient to attract new households. While it is important to have fast transport means to reach different destinations, residents are searching for employment and activities near their homes. Residents are attracted not only by transportation facilities, but also by activities in which they can participate.

We perform our analysis on cross sectional data. It could be interesting to analyse the temporal and spatial transferability of these results. This work focus only on the employment opportunities, as a general proxy for various land-use opportunities. However, further analysis is needed for different activity purposes. Works focusing on this issue should resolve the problems of multicollinearity between different accessibility to activity measures. Last, the accessibility measure applied in this study has some limitations. Integration of more transportation modes might be important if we want to analyse the inclusion of more environmentally friendly transportation modes such as bicycle or walk.

Fig. 1

 1 Fig. 1 Employment density of the study area by zone (classification in quantiles)

Fig. 2

 2 Fig. 2 Main and secondary employment centres of the urban area of Lyon• Cumulative opportunities to employment by car, i.e. the sum of the employment opportunities

Table 1

 1 Literature review summary

	Source	Study area	Model structure	Multiscale analysis	Market segmentation	Accessibility measures	Interaction accessibility characteristics with household	Conclusion
	Blijie, 2005	The Netherlands	Multinomial Logit	No	6 groups	Distance to railway stations and to motorway ramps	Car ownership	Accessibility has marginal influence
						Number of railway and
	De Palma et al., 2007	Ile-de-France (Paris region)	Multinomial Logit	Yes	No	subway stations, distance to motorways, distance to city centre	N/A	Accessibility to transport infrastructure important
						Location-based
						accessibility, zonal
	Sener et al., 2011	San Francisco Metropolitan Area	Multinomial Logit, Spatially Correlated Logit	No	No	motorway density (km/km²), number of household members with work location in 30 minutes or less by	N/A	Location-based accessibility measures were insignificant
						Public Transportation
	Guo and Bhat, 2007	Dallas-Fort Worth metroplex	Multiscale Logit	Yes	No	Potential accessibility to employment, shopping and recreation	Household income, number of household members	Accessibility to employment significant, different households have different sensibility
						Cumulative opportunities
						and logsum (trip-based)
	Srour et al., 2002	Dallas-Fort Worth metroplex	Multinomial Logit	No	No	accessibilities to employment, to shopping	N/A	Accessibility is a major explanatory variable
						and to park space
	Eliasson, 2010	Stockholm region	Nested Logit	No	No	Logsum (activity-based) for work and other trips	N/A	Accessibility is key in location choice models
						Logsum (activity-based) to
	Zondag and Pieters, 2005	The Netherlands	Nested Logit	No	6 groups	work, education and other trips	N/A	Accessibility has a minor influence
						Cumulative opportunities to		Accessibility was
						shopping, logsum (activity-		significant for residential
	Lee et al., 2010	Puget Sound Region	Multinomial Logit	No	No	based) for work trips, log on shopping in time-space	N/A	location choice, even after controlling for other
						prism for work to home		location, neighbourhood
						trips		and dwelling attributes

Table 2

 2 Correlation of the number of jobs by zone

		Employment	Shopping employment	Leisure employment
	Employment	1.00	0.76	0.77
	Shopping employment	0.76	1.00	0.79
	Leisure employment	0.77	0.79	1.00

Table 5

 5 Variables of the residential location choice model

		Variable	Description
	Spatial	Prox Basic Serv	A binary variable that takes the value of 1 when the zone has at least one basic service like a bakery,
	amenities		supermarket, convenience store etc.
		Prox Pr. Schools	The number of primary schools in the zone
		Prox Sec. Schools	The number of secondary schools in the zone
	Social	%rev3*rev3	Self-segregation variables: Interaction of household income with the percentage of households
	environment	%rev4*rev4	belonging to the same income group (per quantile).
		%rev5*rev5
		%HLM*rev1	Interaction of household income with the percentage of social housing in the zone
		%HLM*rev2
		%HLM*rev3
		%HLM*rev4
		%HLM*rev5
	Market trade-	Housing price	The median zonal price for housing
	off	Accessibility	Accessibility indicators

Table 6

 6 The applied accessibility measures and the estimated models

	Accessibility measure	Model	Notes on accessibility

For a review on the contrasts of the accessibility approaches see[START_REF] Niedzielski | Travel Time and Distance as Relative Accessibility in the Journey to Work[END_REF]

For a general review of accessibility measures see[START_REF] Geurs | Accessibility evaluation of land-use and transport strategies: review and research directions[END_REF] and for a review of the accessibility measures applied in residential location choice models see[START_REF] Schirmer | The role of location in residential location choice models: a review of literature[END_REF]

We are following the zoning system of INSEE based on the « grand quartier » zones, which is essentially a census breakdown

We can provide the detailed results by request

We can provide by request more detailed analysis, which is not presented in this article.

We can provide the detailed results by request

Acknowledgments

The authors wish to acknowledge the feedback from the participants of the European Association for Research in Transportation (hEART) conference of 2016 in Delft and the NECTAR workshop of 2016 in Paris. The corresponding author acknowledges the financial support of a doctoral scholarship award by the Region of Auvergne-Rhône-Alpes.

Observations 102,940 102,940 102,940 102,940 102,940 102,940 102,940 102,940 102,940 102,940 Log of likelihood zero -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 -200,312 Log of likelihood (LL) -163, 899 -154,006 -153,267 -152,671 -152,274 -155,676 -149,305 -150,037 -149,914 -149,491

Conflict of interest statement

On behalf of all authors, the corresponding author states that there is no conflict of interest.

Authors' contribution


Guillaume Melquiond
email: guillaume.melquiond@inria.fr

Proving bounds on real-valued functions with computations

Interval-based methods are commonly used for computing numerical bounds on expressions and proving inequalities on real numbers. Yet they are hardly used in proof assistants, as the large amount of numerical computations they require keeps them out of reach from deductive proof processes. However, evaluating programs inside proofs is an efficient way for reducing the size of proof terms while performing numerous computations. This work shows how programs combining automatic differentiation with floating-point and interval arithmetic can provide some efficient yet guaranteed solvers within the Coq proof system.

Introduction

In traditional formalisms, proofs are usually composed of deductive steps. Each of these steps is the instantiation of a specific theorem. While this may be welladapted for manipulating logic expressions, it can quickly lead to inefficiencies when explicit computations are needed. Let us consider the example of natural numbers constructed from 0 and a successor function S. For example, number 3 is represented by S(S(S(0))). If one needs to prove that 3 × 3 is equal to 9, one can apply Peano's axioms, e.g. a × S(b) = a × b + a and a + S(b) = S(a + b), until 3 × 3 has been completely transformed into 9. The first steps of the proof are: 3 × 3 = 3 × 2 + 3 = (3 × 1 + 3) + 3 = . . . This proof contains about 15 instantiations of various Peano's axioms. Due to the high number of deductive steps, this approach hardly scales to more complicated expressions, even if more efficient representations of integers were to be used, e.g. radix-2 numbers.

While numerical computations are made cumbersome by a deductive approach, they can nonetheless be used in formal proofs. Indeed, type theoretic checkers usually come with a concept of programs which can be expressed in the same language than the proof terms. Moreover, the formalism of these checkers assumes that replacing an expression f (x) of a functional application by the result of the corresponding evaluation does not modify the truth of a statement. As a consequence, one can write computable recursive functions for addition and multiplication of natural numbers and prove that they satisfy Peano's axioms. Deductive steps only occur in these proofs of axiom satisfaction. No deductive steps are needed for proving equality of closed terms, e.g. 3×3 = 9, as evaluating 3 × 3 to 9 and replacing its occurrence in the equality is now sufficient. This new approach scales to complicated expressions, as the number of deductive steps no longer depends on the size of the natural numbers nor on the number of arithmetic operators.

In the Coq proof assistant 1 , this ability to use programs inside proofs is provided by the convertibility rule: Two convertible well-formed types have the same inhabitants. In other words, if p is a proof that the proposition A holds true, then p is also a proof that any B convertible to A also holds true. In particular, as 3 × 3 evaluates to 9, the proof of 9 = 9 (reflexivity of equality) is also a proof of 3 × 3 = 9. As the convertibility rule can be quite efficient in Coq, programs can be designed for automatically proving propositions on expressions of real numbers by simply evaluating programs. An example of such a proposition is the following one, where x and y are universally quantified real numbers:

3 2 ≤ x ≤ 2 ⇒ 1 ≤ y ≤ 33 32 ⇒ 1 + x √ x + y - 144 1000 × x - 118 100 ≤ 71 32768
In order to prove this logical proposition with an existing formal method, one can first transform it into an equivalent system of several polynomial inequalities. Then a resolution procedure, e.g. based on cylindrical algebraic decomposition [START_REF] Mahboubi | Implementing the cylindrical algebraic decomposition within the Coq system[END_REF] or on the Nullstellensatz theorem [START_REF] Harrison | Verifying nonlinear real formulas via sums of squares[END_REF], will help a proof checker to conclude automatically. This paper presents a different approach, based on numerical computations, which can be extended to propositions containing nonalgebraic expressions. Section 2 describes the few concepts needed for making numerical computations and approximations into a formal proof tool. Section 3 describes the particularities of the datatypes and programs used for these computations. Section 4 finally brings those components together in order to provide a user-friendly proof tool which relies on logic programing only.

Mathematical foundations

While both terms "computations" and "real numbers" have been used in the introduction, this work does not involve computational real numbers, e.g. sequences of converging rational numbers. As a matter of fact, it is based on the standard Coq theory of real numbers, which is a pure axiomatization with no computational content.

Extended real numbers

The standard theory of Coq describes real numbers as a complete Archimedean field. As functions have to be total, this formalism may make it a bit troublesome to deal with partial functions such as 1

x and √ x. In order to handle all the arithmetic operators in an uniform way, an element ⊥ is added to represent the "result" of a function outside its definition domain. In the Coq development, this additional element is called NaN (Not-a-Number) as it shares the same properties as the NaN value from the IEEE-754 standard on floating-point arithmetic [START_REF] Stevenson | An American national standard: IEEE standard for binary floating point arithmetic[END_REF]. In particular, value ⊥ is an absorbing element for any arithmetic operators on the extended set R = R ∪ {⊥}.

In order to benefit from the common theorems of real analysis, the functions defined on R have to be brought back in R → R. This can be done by using a projection operator parametrized by a real number a which will be used whenever the extended function would have returned ⊥:

proj a : f ∈ (R → R) → x ∈ R → a if f (x) = ⊥ f (x) otherwise ∈ (R → R)
Then, an extended function f is defined as continuous at a point x = ⊥ if f (x) = ⊥ and if all the projections of f for any a ∈ R are continuous at the point x. Similarly, f is defined as derivable at x = ⊥ if f (x) = ⊥ and if all the projections of f have the same derivative

d f (x) at x. A function f ′ is then considered as a derivative of f if f ′ (x) = d f (x) whenever f ′ (x) = ⊥.
Note that a given extended function may have several derivatives, according to this definition. For example, the function x ∈ R → ⊥ is an acceptable derivative for any function of R → R, though this function is quite useless.

From these definitions and standard analysis, it is easy to formally prove some rules for building derivatives. For example, if f ′ and g ′ are some derivatives of f and g, then the extended function f ′ ×g-g ′ ×f g 2 is a derivative of f g . Note that this theorem does not need to assume that g does not evaluate to zero. Indeed, if g(x) = 0, then the derivative evaluates to ⊥, which is fine. This simplicity of the rules will make it easier to manipulate and compute derivatives later on.

Interval arithmetic

Rather than computing directly with these numbers, closed connected sets of real numbers are considered. They are represented by the set I = R × R of all the pairs of extended numbers:

( ⊥ , ⊥ ) → R ( ⊥ , u ) → {x ∈ R | x ≤ u} ( l , ⊥ ) → {x ∈ R | l ≤ x} ( l , u ) → {x ∈ R | l ≤ x ≤ u}
The last set is the empty set ∅ when the upper bound u is less than the lower bound l. Based on these interpretations, a "contains" ∋ relational operator is defined between intervals and reals. As for the real numbers, the set I is extended to a set I = I ∪ {⊥ I } by adding an element ⊥ I , which propagates along all the computations. The usual acronym for this element is NaI (Not-an-Interval). Interval ⊥ I contains any extended real number. In particular, it contains ⊥, which is not contained in any interval of I. Note that ⊥ I is not the pair (⊥, ⊥), which represents R.

The set I is a lattice for the order defined as: (l 1 , u 1 ) (l 2 , u 2 ) if and only if l 2 ≤ l 1 and u 1 ≤ u 2 . In the previous inequalities, a lower bound is replaced by -∞ if it is ⊥, and an upper bound by +∞. This partial order maps to the set inclusion partial order ⊆ when considering non-empty closed connected sets of R. The lattice operators "meet" ∧ and "join" ∨ are respectively mapped to the set intersection and the convex hull of the set union. As usual, these operators are extended to I by having them propagate ⊥ I . For order , ⊥ I is defined as being strictly bigger than any interval of I.

Interval extensions and operators

A function F ∈ I → I is defined as an interval extension of a function f ∈ R → R, if ∀X ∈ I, ∀x ∈ R, x ∈ X ⇒ f (x) ∈ F (X).
This definition can be adapted to non-unary functions too. Some trivial interval extensions are X ∈ I → ⊥ I and X ∈ I → (⊥, ⊥). The first one extends any function of R → R. The second one extends any total function of R → R.

Note that the result of F (X) has to be ⊥ I if there exists some x ∈ X such that f (x) = ⊥. As a corollary, if F (X) is a pair of numbers, then f has to be the extension of a real function that is defined at each point of X. Another property is that interval extension is compatible with composition: If F and G are extension of f and g respectively, then G • F is an extension of f • g. Now arithmetic operators can be defined on intervals, such that they extend arithmetic operators on R. For example, addition and subtraction are defined as propagating ⊥ I and verifying the following rules:

(l 1 , u 1 ) + (l 2 , u 2 ) = (l 1 + l 2 , u 1 + u 2 ) (l 1 , u 1 ) -(l 2 , u 2 ) = (l 1 -u 2 , u 1 -l 2 )
Except for the particular case of ⊥ meaning an infinite bound, this is traditional interval arithmetic [START_REF] Moore | Methods and Applications of Interval Analysis[END_REF][START_REF] Jaulin | Applied Interval Analysis, with Examples in Parameter and State Estimation, Robust Control and Robotics[END_REF], and defining other arithmetic operators does not cause much difficulty. For example, the division is performed by looking at the sign of the bounds: If l 1 is negative and if both u 1 and l 2 are positive, then

(l 1 , u 1 )/(l 2 , u 2 ) = (l 1 /l 2 , u 1 /l 2 ).
Note that performing an interval division this way requires the ability to decide the signs of the bounds. More generally, the ability to compare bounds is needed. This is solved in Section 3.1 by restricting the bounds to a subset of R.

Bounds on real-valued functions

Properties described in previous sections can now be mixed together for the purpose of bounding real-valued functions. Let us consider a function f of R → R, for which we want to compute an interval enclosure Y such that f (x) ∈ Y for any x in an interval X = ⊥ I . Assuming we have an interval extension F of f , then the interval F (X) is an acceptable answer.

Usually, if X appears several times in the unfolded expression of F (X), the wider the interval X the poorer the bounds obtained from F (X). Ultimately, F (X) may well become (⊥, ⊥) (or worse: ⊥ I ), which does not provide any useful data on the extremal values of function f . A simple example of this loss of correlation is shown by the function

f = x ∈ R → x -x. An immediate interval extension is F = X ∈ I → X -X.
Considering X = (-10, 10), the expression F (X) evaluates to (-20, 20), while a sharp enclosure of f on X would be (0, 0).

Refining intervals

Let us suppose now that we also have an interval extension F ′ of a derivative f ′ of f . By definitions of interval extension and derivability, if F ′ (X) is not ⊥ I , then f is continuous and derivable at each point of X.

Moreover, if F ′ (X) does not contain any negative value, then f is an increasing function on X. If X has real bounds l and u, then an enclosure of f on X is F ((l, l)) ∨ F ((u, u)). As the interval (l, l) contains one single value when l = ⊥, the interval F ((l, l)) should not be much bigger than the set {f (l)} for any F that is a reasonable interval extension of f . As a consequence, the junction F ((l, l)) ∨ F ((u, u)) should be close to a sharp enclosure of f on X. The result is identical if F ′ (X) does not contain any positive values.

When F ′ (X) contains both positive and negative values, it is still possible to find a better enclosure of f , while it may not be sharp any longer. As long as F ′ (X) has finite bounds, variations of f on X are bounded:

∀a, b ∈ X, ∃c ∈ X, f (b) = f (a) + (b -a) • f ′ (c).
Once translated to intervals, this proposition states:

∀a, b ∈ X, f (b) ∈ F ((a, a)) + (X -(a, a)) • F ′ (X).
As F ′ (X) may contain even more occurrences of X than F (X) did, the loss of correlation may be worse when computing an enclosure of f ′ than an enclosure of f . From a numerical point of view, however, we have more leeway: the multiplication by X -(a, a), which is an interval containing only "small" values around zero, will mitigate the loss of correlation.

We now have two ways of computing an enclosure of f on X. As a consequence,

F (x) ∧ (F ((a, a)) + (X -(a, a)) • F ′ (X)) is also an enclosure of f on X.
For an implementation, the value a can be chosen as the midpoint of X.

Computational datatypes

If a function F is an interval extension of f , then any function G is also an interval extension of f as long as ∀X ∈ I, F (x) G(X). As a consequence, instead of choosing the "best" bounds for an interval extension, one can decide to use the most practical ones instead. For example, both intervals ( √ 5, √ 5) and

(2, 3) contain √ 5, but the second is a lot easier to manipulate if one only needs to prove that √ 5 is bigger than 1. Only a subset F β of R will be considered during computations on interval bounds. Radix β is an integer bigger than one. In addition to ⊥, F β will contain all the rational numbers of the form m • β e with m and e relative integers. While F β \ {⊥} is a ring for (+, ×), this property will hardly matter, as interval computations do not need sharp bounds but only outer enclosures.

Floating-point arithmetic

Let us consider the non-⊥ quotient u v of two floating-point numbers. This quotient is often impossible to represent as a floating-point number. If this quotient is meant to be the lower bound of an interval, e.g. because we are performing an interval division, we can chose any floating-point number m • β e less than the ideal quotient. Among these numbers, we can restrict ourselves to numbers with a mantissa m represented with less than p digits in radix β (that is, |m| < β p ). This is an infinite yet discrete set, so it has a maximum w representable with a floating-point number. This is what the IEEE-754 standard calls the result of u/v rounded toward -∞ at precision p.

Computing at fixed precision ensures that the computing time is linear in the number of arithmetic operations. Let us consider the computation of done by n successive squaring. With rational arithmetic, the time complexity is then O(n 3 ), as the size of the numbers double at each step. With floating-point arithmetic at fixed precision, the time complexity is just O(n). The result is no longer exact, but it does not matter when performing interval arithmetic.

There have been two prior formalizations of floating-point arithmetic in Coq, at least. The first one [START_REF] Daumas | A generic library of floating-point numbers and its application to exact computing[END_REF][START_REF] Boldo | Preuves formelles en arithmétiques à virgule flottante[END_REF] defines rounded results with relations, so the value w would be expressed as satisfying the proposition:

w ≤ u v ∧ ∀m, e ∈ Z, |m| < β p ⇒ m • β e ≤ u v ⇒ m • β e ≤ w
While useful and sufficient for proving theorems on floating-point algorithms, such a relation does not provide any computational content, so it cannot be used for performing numerical computations. The second formalization [START_REF] Melquiond | De l'arithmétique d'intervalles à la certification de programmes[END_REF] has introduced effective floating-point operators, but only for addition and multiplication. For floating-point division, an external oracle provides the result and it just has to be checked for validity, which can be achieved with multiplications only.

Implementation So this work relies on a new formalization of floating-point arithmetic, which provides floating-point operators for all the basic operations. This formalization is also further away from IEEE-754 than the two prior ones, as it gets rid of the underflow mechanism. Indeed, while this restriction on the range of exponents is useful when designing processors, it is a hindrance when performing numerical computations. So the exponent range is simply unbounded and there is no loss of precision around zero with this new implementation.

The prototype of the arithmetic operators is

precision → mode → F β → • • • → F β .
So, in addition to the floating-point operands, they also take as arguments a positive integer (bigger than one to avoid degenerate cases) for precision and a rounding mode chosen among the four modes mandated by IEEE-754: to nearest (tie break to even mantissas), toward zero, toward -∞, and toward +∞.

For the purpose of interval arithmetic, only the last two modes are used in this work: Computations are rounded toward -∞ for lower bounds, and toward +∞ for upper bounds. Precision is a global parameter of the algorithms and it is passed down to all the floating-point computations. Setting the precision is a trade-off: A high value can help in proving some propositions, but it also slows down numerical computations.

Interface and specializations

Operators provided by this formalization are somewhat slow. As β is a generic integer, the operators are missing some optimizations. Indeed, an efficient floatingpoint implementation needs fast shifts in radix β: left shifts for aligning mantissas, right shifts for rounding numbers. In the generic operators, these shifts are emulated by multiplication and division by powers of β. But when mantissas are represented in the same radix than β, a left shift can be performed by simply adding zeros at the least significant side of the representation, while a right shift can be performed by deleting the least significant digits. Floating-point arithmetic also needs fast integer logarithm in radix β.

These implementation details do not matter to interval algorithms. In order to abstract them, floating-point arithmetic has been described as an interface (a "Module Type" in Coq syntax) which provides all the operators and their correctness theorems. The interval algorithms are then implemented as module functors that can be parametrized by any module that provides floating-point arithmetic.

There are three such implementations of floating-point arithmetic. The first one simply encapsulates the generic floating-point operators. The two other ones provides fast specializations for β = 2. One is based on the standard integers provided by Coq as little-endian lists of bits. These lists make shifts and logarithms trivial to efficiently implement. The other one is based on integers represented as binary trees with leafs being digits for radix 2 31 [START_REF] Grégoire | A purely functional library for modular arithmetic and its application to certifying large prime numbers[END_REF]. While shifts are slower than for the previous implementation, arithmetic operations are faster, as Coq can delegate arithmetic on leafs to the computer processor [START_REF] Spiwack | Ajouter des entiers machine à Coq[END_REF].

Interval arithmetic is also described as an interface that is used to parametrize all the higher level algorithms. There is one single implementation of interval arithmetic and it uses floating-point bounds. But one could imagine providing implementation with other kinds of bounds (e.g. rational numbers) or other interval representations (e.g. midpoint -radius).

Straight-line programs

For now, we can only perform interval computations; we have yet to prove properties on expressions. A prerequisite is the ability to actually represent these expressions. Indeed, as we want Coq programs to be able to evaluate expressions in various ways, e.g. for bounds or for derivatives, they need a data structure containing an abstract syntax tree of the expressions. More precisely, as it is worth avoiding to recompute each occurrences of a common sub-expression, the expression is stored as a straight-line program. This is a directed acyclic graph with an explicit topological ordering on the nodes which contain arithmetic operators.

The following straight-line program describes the expression

√ x -y • √ x (as long as v -1 is x and v -2 is y). v 0 ← (sqrt, v -1 ) v 1 ← (mul, v -2 , v 0 ) v 2 ← (sub, v 0 , v 1 )
A statement is allowed to access previous results only. So rather than storing the absolute indexes of the previous results for each operations, their relative positions are stored. In other words, during an evaluation, each statement pushes on the top of a stack its result, and the next statements will look into the stack to find their operands.

The evaluation function is generic. It takes a list of statements, the type A of the inputs and outputs (e.g. R or I), a record of functions implementing the operators (functions of type A → A and A → A → A), and a stack of inputs of type A. It returns the stack containing the results of all the statements. Whenever a statement tries to access past the bottom of the evaluation stack, a default value of type A is used, e.g. 0 or ⊥ or ⊥ I .

By passing various sets A and operators on A, the evaluation function will produce an expression on real numbers corresponding to the straight-line program, or an interval enclosing the values of the expression, or an expression of the derivative of the expression, or bounds on this derivatives, etc.

Automatic proofs

The convertibility rule has two main uses. First it helps transforming logical propositions into data structures on which programs can actually compute. Second it gives a meaning to the subsequent numerical computations. The details will be hidden behind "tactics", which are tools available to the user of the Coq proof system.

Converting terms

Convertibility is first used to check that the transformation of propositions into data structures are sound. This process is called reflexion [START_REF] Boutin | Using reflection to build efficient and certified decision procedures[END_REF]. While checking is done by Coq, the transformation itself cannot be performed with Coq's term language, as the syntax of terms is not available at this level. Three solutions can be considered. First, one could ask the user to perform the transformation itself. This may be fine for small terms, but it quickly becomes cumbersome. Second, one could integrating the transformation directly into the Ocaml code of Coq, hence creating a new version of the proof assistant. Several existing reflexive tactics actually depend on Ocaml helpers inside Coq. Third, one could use the tactic language embedded in Coq [START_REF] Delahaye | A tactic language for the system Coq[END_REF], so that the transformation runs on an unmodified Coq interpreter. This third way is the one implemented.

Let us assume that the proposition to prove is

√ x-y • √ x ≤ 9.
In order to use programs, the tactics have to transform the proposition into a data structure.

The left hand side will be transformed into a straight-line program, while the right hand side will be transformed into an interval bound which is a floatingpoint number (with β = 2). Let us consider this last transformation only, as the first one is conceptually similar but with a more complicated parser. So the goal is to find a positive integer that is the mantissa of this number (which we choose to have exponent 0, so the mantissa will actually be the integer 9). The real number 9 is actually 9%R with Coq notations, that is the string 9 parsed with the grammar rules for real numbers R. This is simply a notation which Coq's parser expands to (1 + (1 + 1) * ((1 + 1) * (1 + 1)))%R, as 0 and 1 are the only two integer constants known by Coq. Conversely, Coq's pretty-printer displays this tree of additions, multiplications, and ones, as the compact notation 9%R for the sake of readability.

So the objective is to parse this expanded tree and to find the related integer represented by a list of bits. In the Coq formalization of positive integers, the start of this list is the most-significant bit xH (necessarily 1) while the other items are xO (for 0) and xI (for 1), going down to the least-significant bit. Since the binary decomposition of 9 is 1 + 0 This tactic defines a rec-ursive function aux which is called on a term t. This term is match-ed against several syntactic patterns, potentially containing a hole v matching any term. When a pattern matches, a recursive call is performed on the sub-term v if any, and then an integer is constr-ucted and returned by the function. The returned structure is the expected one, which can also be written as the string 9%positive.

• 2 + 0 • 4 + 8,
As a tactic is not proved, there is no guarantee it did not return a random integer, e.g. 42%positive. This is where convertibility strikes in. The main tactic takes the original proposition and replaces it by (sqrt x -y * sqrt x <= P2R (9%positive))%R. It then tells Coq that proving this new proposition is sufficient. There is no reason for Coq to trust the tactic, so the assistant checks that both propositions are indeed convertible. Here it amounts to checking that the term P2R 9%positive evaluates to the exact same term than 9%R. The function P2R2 is written in the term language of Coq, and hence usable inside proofs:

Fixpoint P2R ( p : positive ) := match p with | xH = > 1% R | xO xH = > 2% R | xO t = > (2 * P2R t )% R | xI xH = > 3% R | xI t = > (1 + 2 * P2R t )% R end .
In the end, the various tactics have converted the proposition √ xy • √ x ≤ 9 into the following convertible proposition. For the sake of readability, some arguments are left out of it:

contains (⊥, +9 • β 0 ) (eval R [Sub 1 0, Mul...] [x, y])
Note that the tactics perform some extra work so that the generated straightline program contains only one occurrence of √ x, instead of the two occurrences of the original proposition.

Proving propositions

The new proposition can then be proved by applying this lemma:

v ∈ A ⇒ A B ⇒ v ∈ B.
It splits the proposition into two parts, with X and Y respectively

(+3 • β -1 , +1 • β 1 ) and (+1 • β 0 , +33 • β -5 ): contains (eval I [Sub 1 0, Mul...] [X, Y]) (eval R [Sub 1 0, Mul...] [x, y]) (eval I [Sub 1 0, Mul...] [X, Y]) (⊥, +9 • β 0 )
The first part is a consequence of the interval arithmetic operators being interval extensions of the arithmetic operators on R, and of the property of interval extension being compatible with function composition. No computations are needed for proving this part.

By defining a suitable subset function, a proof of the second part can be replaced by a proof of subset (eval

I [Sub 1 0, Mul...] [X, Y]) (⊥, +9 • β 0 ) = true
As comparisons between interval bounds are decidable, the subset function is actually a program, and so is eval on floating-point intervals. As a consequence, Coq can convert the left hand side of the equality to either true or false by evaluating these programs. If the result is true, then the reflexivity of equality applies and the proof is concluded: The original proposition holds true.

To summarize, this proof relies almost entirely on convertibility, except for the four deductive steps, which are instantiations of the following theorems:

1. If the result of a formula on extended reals is contained in an interval non-⊥ I , then the same formula on real numbers is well-formed and produces the same result. 2. The interval evaluation of a given straight-line program is an interval extension of the evaluation of the same program on extended reals. 3. If subset A B = true, then any value contained in A is also contained in B.

Boolean equality is reflexive.

Bisection and refined evaluation Actually, because of a loss of correlation, the left hand side evaluates to false on the example of the introduction. This is expected [START_REF] Daumas | Guaranteed proofs using interval arithmetic[END_REF], and two methods experimented with the PVS proof assistant3 can be reused here. First method is the bisection: If the interval evaluation fails to return an interval small enough, split the input interval in two parts and perform the interval evaluation again on each of these parts. As the parts are smaller than the whole interval, the loss of correlation should be reduced, so the interval evaluation produces a sharper result [START_REF] Moore | Methods and Applications of Interval Analysis[END_REF].

In the PVS work, interval splitting is performed by applying a theorem for each sub-interval. Here we keep relying on programs in order to benefit from convertibility and reduce the number of deductive steps. The method relies on a bisect function (hence the method is named bisect in next section) recursively defined as: bisect n F (l, u) target = if n = 0 then false else if subset F ((l, u)) target = true then true else let m be the midpoint of (l, u) in (bisect (n -1) F (l, m) target)&&(bisect (n -1) F (m, u) target)

This function is meant to replace the subset call in the previous proof. Its associated theorem is a bit more complicated though, but its hypotheses are as easy to satisfy: If F is an interval extension of a function f and if bisect ... evaluates to true, then f (x) ∈ target holds true for any x ∈ (l, u). Once again, the complete proof contains only four deductive steps. Everything else is obtained through convertibility.

As long as n is big enough and the floating-point computations are precise enough (the precision is user-settable), this method can solve most of the provable propositions of the form ∀x ∈ (l, u), f (x) ∈ Y with f a straight-line program. The method is guaranteed4 to succeed when l and u are finite and the sharpest enclosure of f on (l, u) is a subset of the interior of Y . The method can also be extended to multi-variate problems, by splitting interval boxes along each dimension iteratively.

While this method often works, it is practical only when the amount of analyzed sub-intervals is small. To prevent its growth, a second method (namely bisect diff) sharpens the interval evaluation by using the derivatives, as described in Section 2.3. However, while it reduces the number of sub-cases, it increases the memory footprint and the amount of floating-point operations per interval evaluation.

Performances

The following Coq script contains the formal proof of the toy proposition mentioned in the introduction of this paper. The first Require imports the standard theory of real numbers, so that the proposition can be expressed. The second one imports the tactics presented in this paper. The Goal statement contains the proposition. The position of the forall quantifiers does not matter, as the intros tactic loads all the hypotheses in the proof context. The interval tactic then applies an interval-based method to solve the goal. Its (i bisect x) parameter indicates that x is the primary variable on which to perform a bisection. This variable will be abstracted in the real-valued functions the programs handle. Finally, Coq checks a second time that the proof is sound and complete, when it encounters the Qed statement.

Table 1 shows the time needed for Coq to check the previous proof script, depending on the interval-based method. The first column contains timings when the tactics use the floating-point arithmetic based on the default integer representation of Coq. The second column contains timings when the tree-based representation of integers in radix 2 31 is used. When a numeric precision is indicated, it means the user manually selected the lowest (hence fastest) precision so that the computations succeed. Otherwise, the default 30-bit precision was used. The timings are relative to the best method, which is the bisection method with derivatives and optimized integers, as expected. The CAD algorithm with fast integers has also been executed on this example, but no results were obtained after a decent amount of time. After replacing y by 1 (hence using a uni-variate degree-5 problem), the algorithm was able to finish, but it was still a lot slower than the bisection algorithms.

The last row of the table corresponds to the 19216-line long proof script generated by the Gappa tool [START_REF] Melquiond | De l'arithmétique d'intervalles à la certification de programmes[END_REF]. As Gappa is primarily aimed at proving propositions on numerical programs, its methods do not take into account the derivatives of the expression. Indeed, due to rounding, programs do not even represent a continuous expression, so the derivative is useless. Anyway, the proposition is no different from a degenerate program (infinitely-precise computations), so Gappa is able to prove it. Moreover, as it acts as an external oracle, checking the proof involves additions and multiplications only, no division nor square root; and the precision of each single numerical operation is the lowest possible. With respect to the amount of interval computations, Gappa approach is similar to the bisect method with Z integers. It performs a lot more deductive steps though, which explains why it does not fare much better although it performs simpler interval computations. Note that the relative timing of Gappa was halved to account that, in practice, the other timings are doubled due to the second proof check performed by Coq at Qed time.

Another example

The previous proposition is just a toy example and its occurrence in a reallife proof might be doubtful. The following one is a more realistic example. Taylor models have been experimented in Coq [START_REF] Zumkeller | Formal global optimisation with Taylor models[END_REF] in order to formally prove some inequalities of Hales' proof5 of Kepler's conjecture. Part of the difficulty with Taylor models lies in handling elementary functions. Indeed, one has to use polynomial approximations for this purpose. Usually, as the name implies, these polynomials are Taylor expansions, since their expansion remainder can be bounded by symbolic methods. Yet Taylor expansions are poor approximations, so high-degree polynomials are needed, which needlessly slow down the proof.

There are much better polynomial approximations, e.g. the ones obtained from Remez' algorithm. Unfortunately, the approximation error is no longer available to symbolic methods. One has to bound it numerically. The following proposition states the error bound between the square root function and its Remez approximation of degree 5 with rational coefficients of width 20 + 20 bits, on the interval (0.5, 2). Since Remez' algorithm returns the best polynomial approximation with real coefficients, checking the error bound is a numerically difficult problem. Yet it only takes a few seconds for Coq to automatically prove it with the bisect diff tactic with BigZ integers on a desktop computer (or half a minute with Z integers). In comparison, the CAD algorithm needs more than ten minutes in Coq. For Hales' proof, one also needs the arctan function, which is in the scope of this tactic. So interval-based methods open the way to using low-degree approximations of elementary functions in Taylor models.

Conclusion

Interval-based methods have been used for the last thirty years whenever a numerical problem (bounding an expression, finding all the zeros of a function, solving a system of differential equations, and so on) needed to be solved in an efficient and reliable way. But due to their computationally-intensive nature, they have been seldom used within formal proofs. With the advent of fast program evaluation in proof checkers, the situation is starting to change [START_REF] Melquiond | De l'arithmétique d'intervalles à la certification de programmes[END_REF][START_REF] Zumkeller | Formal global optimisation with Taylor models[END_REF].

While all the expressions currently handled are written with basic arithmetic operators, this is not an intrinsic limitation of the interval methods. Interval extensions for usual elementary functions (log, sin, arctan, cosh, and so on) are being added, so that propositions containing these functions can be handled automatically too. Moreover, interval-based methods can also deal with functions defined implicitly, e.g. a zero of an expression or a solution of a differential equation. This is another extension under consideration.

Another interesting property of interval-based methods is their scalability: Checking the numerical computations can trivially be split amongst several processing units. Indeed, domains of logical propositions can be split into several parts, as checking one part is a process independent from checking all the other parts. For now, this still requires some user interaction for manually splitting a proposition amongst several proof files and checking these files concurrently [START_REF] Daumas | Guaranteed proofs using interval arithmetic[END_REF].

The Coq development presented in this paper is available at http://www.msr-inria.inria.fr/ ~gmelquio/soft/coq-interval/

5

 5

  it is represented by the structure xI (xO (xO xH)). This structure is generated by the following tactic: Ltac get_mantissa t := let rec aux t := match t with | 1% R = > xH | 2% R = > constr :( xO xH ) | 3% R = > constr :( xI xH ) | (2 * ? v )% R = > let w := aux v in constr :( xO w ) | (1 + 2 * ? v )% R = > let w := aux v in constr :( xI w ) end in aux t .

  Goal forall x , (1/2 <= x <= 2)% R -> ( Rabs ((((((122 / 7397 * x + ( -1733) / 13547) * x + 529 / 1274) * x + ( -767) / 999) * x + 407 / 334) * x + 227 / 925) -sqrt x ) <= 5/65536)% R .

Table 1 .

 1 Relative timings for proving fact about 1 + x

			Z	BigZ
	bisect		45.4	2.22
	bisect	prec = 19	23.0	2.10
	bisect diff		2.66	1.01
	bisect diff prec = 18	1.56	1.00
	CAD		-	∞
	Gappa		17.3	-
				√	x+y .

http://coq.inria.fr/

The standard theory of Coq already provides a function named IZR for converting integers to real numbers. But this function is useless for our purpose, as it evaluates the integer 9 to the real (1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1)%R, which is provably equal yet not convertible to 9%R.

http://pvs.csl.sri.com/

If there is x ∈ (l, u) such that f (x) evaluates to ⊥, Y has to be ⊥I . Otherwise, f is continuous on the compact set (l, u), hence it is also uniform continuous. This uniformity ensures that some suitable precision and n exist.

http://code.google.com/p/flyspeck/