Marie-Estelle Binet
email: marie-estelle.binet@univ-rennes1.fr.

Francois Facchini
email: francois.facchini@univ-paris1.fr

OKUN'S LAW IN THE FRENCH REGIONS: A CROSS-REGIONAL COMPARISON

Keywords: Okun's law, regional labour markets, panel data. JEL classification: C23, O18, R23

This article tackles one central issue in the regional science literature: the persistence of regional disparities in unemployment within national economies. Our approach is original as Okun's coefficients are estimated for each of the 22 administrative French regions over the period 1990-2008, taking into account cross-regional disparities in a panel data specification. Estimates show that the coefficients exhibit regional differences. Indeed, Okun's law is confirmed in fourteen regions, although it does not hold in the other eight regions. Finally, region-specific factors that explain the results that are not significant are identified, and policies to reduce unemployment in French regions are examined.

INTRODUCTION

The implementation of adequate policies to reduce unemployment is crucial for national and regional authorities. Indeed, as cross-regional disparities are large and persistent in most countries, unemployment policy cannot only be considered from a national perspective. Obviously, the success of policy measures depends on the regional labour market conditions.

The most widely used variable for explaining the unemployment rate is per capita gross product. More precisely, one major issue is the analysis of the functional relationship between unemployment and Gross Domestic Product (GDP). This rather complex relationship has been formalized by [START_REF] Okun | Potential GNP: Its measurement and significance[END_REF] who related deviations from the natural rate of unemployment to changes in real output, and provided policy makers with a guide to the employment effects of higher output growth. He showed that every percentage point that the unemployment rate falls below the natural unemployment rate corresponds to a rise in real output of three per cent a year. Since Okun's seminal contribution, this law has been frequently found to hold at the country level, in macroeconomic empirical studies. But there are very few studies analysing the relationship at the regional level. In this paper, we estimate Okun's coefficients using regional panel data for France over the period 1990-2008. France is an interesting case study since the country exhibits a persistently high dispersion of unemployment rates across its regions.

The contribution of the paper to literature is twofold. As well as estimating Okun's law at the regional level in France for the first time, to the best of our knowledge, it also explicitly introduces spatial heterogeneity into the model to be estimated. To do so, the specification used includes one specific Okun's coefficient for each region.

Our findings show that the law holds for only fourteen regions, and that Okun's coefficients are not statistically significant for the eight other French regions. On this empirical basis, the implementation of an economic policy more appropriate for the reduction of unemployment in each region must be analysed.

For the regions in which the law holds, conventional nationwide policies to stimulate GDP might be sufficient. In contrast, region-specific policies should be implemented in those regions where the law does not hold (such as interregional labour mobility, public spending in terms of transport infrastructures to reduce the costs of spatial mobility, education and apprenticeship policies or a combination of these). In France, all these policies are provided by the decentralized regional authorities. But regional structures have dissimilar features. Therefore, the implementation of the appropriate policies to reduce unemployment must differ from one region to another.

The rest of this paper proceeds as follows. In Section 2, the literature analysing Okun's law at the regional level is reviewed. In Section 3, the specification of the model is discussed. Data used in the empirical analysis are described in Section 4. In Section 5, regional specific efficient policies to tackle unemployment are discussed and the issue of the lack of correlation between unemployment and GDP fluctuations in eight regions is addressed. Section 6 provides some conclusions.

EMPIRICAL EVIDENCE ON OKUN'S LAW AT THE REGIONAL LEVEL

Following the seminal papers by [START_REF] Okun | Potential GNP: Its measurement and significance[END_REF] and [START_REF] Prachowny | Theoretical foundations and revised estimates[END_REF], a large number of empirical studies have analysed Okun's law at the national level. They generally provide support for the empirical validity of the law. Since [START_REF] Freeman | Regional tests of Okun's Law[END_REF], few articles have investigated this issue at the regional level. The existing literature can be summarized as follows.

FREEMAN (2000) tested Okun's law for eight US regional economies during the period 1958-1998 to analyse the regional differences in the responsiveness of output to reductions in unemployment. He concluded there are slight interregional differences in the magnitude of Okun's coefficients, in the range of -1.84 to -3.57. APERGIS and REZITIS (2003) estimated Okun's coefficients using annual data for eight regions in Greece over the period 1960-1997. They asserted that the coefficients do not exhibit interregional differences except for the cases of two regions with coefficients of -2.97 and -3.56 respectively. However, these two articles give little interpretation of their results. CHRISTOPOULOS (2004) also investigated Okun's law for thirteen Greek regions and provided evidence that the relationship can be confirmed for only six regions under study (Okun's coefficients are in the range of -0.37 to -1.70). The high proportion of long-term unemployed people might explain why changes in unemployment and output do not move together in the seven other regions.

Next, ADANU (2005) estimated Okun's coefficients for ten Canadian provinces over the period 1981-2001 and found values ranging from -0.30 to -2.14. He concluded that the coefficients are higher, in absolute value, in the relatively more industrialized provinces with higher populations and output. In these regions, the loss in real GDP when a trained person loses his or her job exceeds that of a less trained person. VILLAVERDE andMAZA (2007, 2009) found different quantitative values of Okun's coefficients (ranging from -0.32 to -1.55, with two non-significant values) for seventeen Spanish regions over the period 1980-2004. They also found a positive correlation between the evolution of productivity and the coefficients. [START_REF] Bande | Regional disparities in the unemployment rate: The role of the wage-setting mechanism in Spain, 1987-92[END_REF] provided further explanation of the regional disparities in the distribution of unemployment in Spain.

To summarize, most of those empirical studies show substantial regional differences in the coefficient values. On this empirical basis, few authors give prescriptions for reducing unemployment in the regions under study. From the Keynesian perspective, CHRISTOPOULOS ( 2003) suggested the adoption of demand management policies to reduce the level of unemployment in regions where the law holds. He proposed subsidizing employment or financing the local infrastructure in regions where the law is not observed. From a neoclassical perspective, [START_REF] Apergis | An examination of Okun's law: Evidence from regional areas in Greece[END_REF] suggested improving labour market flexibility to increase the productivity of the overall economy and decrease unemployment in all regions. In addition, [START_REF] Villaverde | The robustness of Okun's law in Spain, 1980-2004: Regional evidence[END_REF] concluded that a nationwide supply policy to increase labour flexibility should be combined with specific local policies to increase interregional mobility in regions for which the law does not hold.

EMPIRICAL METHODOLOGY

After describing the gap specification that we used for this study, specific econometric issues are discussed.

Gap specification

Two specifications are generally used in the literature to estimate Okun's coefficients: difference model or the gap model. [START_REF] Okun | Potential GNP: Its measurement and significance[END_REF] used the difference model. But we have opted for the gap model, as have numerous recent studies.

Output and unemployment variables are expressed in terms of the cyclical components or deviations from long-term trends. The specification commonly used in the literature is provided by the following expression:

it it it u y       ) (u ) (y ) 1 ( * it * it
The index i refers to a region and the index t to a time period. y is the logarithm of observed or actual output and y* is the logarithm of equilibrium output. u* is the natural unemployment rate and u is the actual unemployment rate, expressed as a percentage. The left-hand side term (y ity* it ) is the output gap which represents the cyclical level of output. In the same way (u itu* it ) measures the unemployment gap and captures the cyclical unemployment rate. it  is the error term. If Okun's law is valid, the coefficient  is negative: for every 1% increase in unemployment rate, the GDP will be at an additional  % lower than its potential GDP. But Okun's coefficients may not be statistically significant, which means that unemployment is not responsive to changes in output. This can be explained in different ways.

First, a rise in labour force participation will tend to increase unemployment if the growth in production is lower than the increase in the labour force. In this case, a regional policy to subsidize labour mobility is efficient. Second, when labour market flexibility is low, growth fails to create jobs. Labour market rigidities are explained by national legislation (for example a large tax wedge or a minimum wage). But, Okun's coefficient can also vary according to the skill levels of employees and labour productivity. An increase in labour productivity can mean that real net output grows without net unemployment rates falling (the phenomenon of "jobless growth").

Econometric issues

There are two important issues to consider in estimating the expression (1). Firstly, as y* and u* cannot be observed we have to estimate them, using available filtering techniques to separate the trend from cycles (Beveridge-Nelson, Baxter-King bandpass filters or the Hodrick-Prescott filter). In our study, the cyclical components are extracted by using the HODRICK-PRESCOTT (1980) filter as it has become the standard method for detrending in the literature. One advantage of using this filter is that the resulting detrended series is stationary [START_REF] Adanu | A cross-province comparison of Okun's coefficient for Canada[END_REF]. Time series decomposition is applied to the level of the unemployment rate and to the logarithm of real GDP for each region.

The second issue is whether or not the error terms are serially autocorrelated. When the null hypothesis of no autocorrelation in the error term is rejected, estimation methods to deal with serial correlation must be implemented.

DATA DESCRIPTION

The local public sector in France comprises four overlapping administrative divisions. In order, from the lowest level up, there are 36,680 municipalities, 2,599 groups of municipalities, 100 departments, and 22 metropolitan regions. French regions, which were created by decentralization laws in 1982, form the highest level of local government in France and are specialized in economic policy.

Annual data on unemployment and output covering the period 1990-2008 have been taken from the National Institute of Statistical and Economic Studies (INSEE) for the 22 French administrative regions, and this corresponds to the regional division of Eurostat at the NUTS 2 level. Real GDP per capita is measured at 2000 prices. A panel data specification is chosen due to the small time dimension of our data.

Unemployment is a major problem in France, as the unemployment rate has risen from an average of 7.5 per cent in 2008 to 9.4 per cent in 2011. But these average values conceal heterogeneous situations in regional labour markets, as shown in Table 1.

Data sources: INSEE, local data

In France, unemployment rates differ between the regions from an average of 6.33 per cent in Alsace to 13.19 per cent in Languedoc-Roussillon between 1990 and 2008. Therefore, unemployment policies have to deal with disparities in the regional labour market situation.

Table 2 exhibits the basic statistics for describing real per capita GDP (measured at 2000 prices).

Table 2 Average regional per capita GDP in Euros in France (1990France ( -2008) ) Greater than 90,000 Euros Between 40,000 and 90,000 Euros

Less than 40,000 Euros

Data sources: INSEE Local Data

French regional per capita GDP also varies from one region to another. The comparisons provide insight into the very important weight of a few regions in terms of gross domestic product: Ile-de-France, Rhône-Alpes and Provence-Alpes-Côte-d'Azur.

Table 3 provides the yearly average growth rate of the GDP for the 22 French regions between 1990 and 2008.

Table 3 Average yearly regional per capita GDP growth rates in France, (1990)(1991)(1992)(1993)(1994)(1995)(1996)(1997)(1998)(1999)(2000)(2001)(2002)(2003)(2004)(2005)(2006)(2007)(2008) Greater than 2% 1.5%-2% Less than 1.5% These figures show persistent regional differentials in GDP growth over the period 1990-2008. They also point out the separation between south-western regions and the north-eastern industrialized regions. Except for Bretagne and Pays de Loire, the most dynamic French regions are located in the south of the country.

REGIONAL ESTIMATES OF OKUN'S COEFFICIENTS

In a preliminary step, Okun's parameter is assumed to be constant across regions and the corresponding pooled estimation of (1) with ordinary least squares (OLS) gives a significant value 21 . 0 ˆ   . This value is in line with the previous times series approach of MOOSA (1997) who reported a coefficient equal to -0.369 for France. But the Breush-Pagan test reveals the presence of heteroscedasticity with a p-value equal to 0.0041, which can be interpreted as spatial heterogeneity. Therefore, the cross-regional variations of Okun's parameter are included in the specification.

Estimates obtained with OLS are reported in Table 4. As the Wooldridge test for panel data reveals first-order autocorrelation (AR(1)), we also implemented the generalized least squares (GLS) procedure developed by [START_REF] Baltagi | Unequally spaced panel data regressions with AR (1) disturbances[END_REF]. The results of this are shown in the last row of the table. high Okun's coefficient (in absolute value) exhibit per capita private R&D spending that is at least twice as great as the regional average (source Regio, Eurostat). Therefore, the loss in real GDP when highly skilled workers lose their jobs is probably higher than in other regions. For the regions in which the law holds, conventional nationwide policies to stimulate GDP might be sufficient to reduce unemployment. [START_REF] Dixon | The relationship between regional and national unemployment[END_REF] go further into this topic, and discuss how regional unemployment can move in relation to national unemployment.

Empirical results show that output is not responsive to changes in unemployment for eight French regions where Okun's coefficients are not statistically significant. Obviously, spatial variations in the coefficient might reflect specific regional configurations. Indeed, the structure of the regional economy, population and labour market conditions might contribute to the explanation of these mixed results. Thus, it is instructive to propose to gain an understanding of the regional patterns where the law does not hold, in order to develop appropriate policy responses to reduce regional unemployment.

As shown in Table 1, two of these regions (Bretagne and Limousin) exhibit lower than average unemployment rates (respectively 7.79 and 7.22 per cent during the 1990-2008 period). But three of the regions have high unemployment which is persistently above the national average over the period of the study (Languedoc-Roussillon, Nord-Pas-de-Calais and Picardie). [START_REF] Christopoulos | The Relationship between output and unemployment: Evidence from Greek regions[END_REF] suggests that in these regions a high proportion of long-term unemployed people might explain why levels of unemployment and output do not move together.

More generally, unemployment might result from changes in production that are not matched to changes in education; and, the spatial mismatch between where workers live and where jobs are located accounts not only for individuals who are unemployed but also for individuals who are underemployed [START_REF] Croce | Overeducation and Spatial flexibility in Italian local labour markets[END_REF]. Over-education is a multifaceted phenomenon in the labour market of advanced economies [START_REF] Croce | Overeducation and Spatial flexibility in Italian local labour markets[END_REF]. If wages are not flexible enough or firms do not adapt their jobs to workers characteristics, a mismatch will tend to persist, so regional apprenticeship policies might be helpful in giving people the skills they need to do the available jobs.

Furthermore, a region can face a persistent unemployment problem if its labour force growth rate exceeds the employment growth rate. Again, in this situation, a regional policy to help workers move to other regions in order to get jobs can help reduce regional unemployment. That might be the case for Bretagne and Languedoc-Roussillon which experienced high population growth levels during the period under study, with average yearly growth rates of 0.67 per cent and 1.14 per cent respectively, which are greater than the national average growth rate of 0.42 per cent each year (source Regio, Eurostat).

Finally, the percentage of people employed in the public sector could also explain why the results obtained are not significant, as this is relatively high for the eight regions where the law does not hold (greater than 35 per cent of total regional employment). Therefore, labour market rigidities might partly be explained by a high proportion of the total workforce in public employment (source Regio, Eurostat).

CONCLUSION

In this article, the link between unemployment and growth from a regional perspective are considered. More precisely, Okun's law at the French regional level has been investigated for the first time. This relationship has important implications for economic policy, particularly in considering prescriptions for reducing unemployment.

Using a panel dataset including all the 22 French administrative regions for the period 1990-2008, the question of whether Okun's coefficients exhibit regional differences is examined. A generalized least squares estimator to deal with first-order serial autocorrelation to estimate a specific Okun's coefficient for each region is implemented. The results support the empirical validity of Okun's law for fourteen administrative French regions. For these regions, policies which favour economic growth and entrepreneurship are most appropriate.

But, Okun's law does not hold for the eight other regions as the corresponding coefficient is not statistically significant. In these regions policies that favour economic growth are not sufficient, and other policies have to be tried.

Indeed, one common factor in the regions where the law does not hold is identified: that is, they all exhibit a high percentage of public sector employment. But these regions also have distinctive features. Among the eight regions under consideration, two are regions that have grown relatively rapidly. Regional subsidies which favour mobility out of the region or investment in transport infrastructure at the local level might be increased in these regions. Furthermore, three other regions exhibit persistently high unemployment rates, and education and apprenticeship policies might be helpful in these regions to give people the right skills to do the available jobs.

Finally, our results suggest that any attempt to reduce regional unemployment must address regional labour market specificities. And our findings highlight the role played by decentralized regional authorities in implementing specific regional policies.

Table 1

 1

	Average Unemployment rate in French regions (1990-2008)
	Lower than 8%	8%-9%	9%-10% and more
	Alsace (6.33)	Bourgogne (8.08)	Poitou-Charentes (9.03)
	Limousin (7.22)	Pays de Loire (8.15)	Aquitaine (9.33)
	Franche-Comté (7.44)	Ile-de-France (8.19)	Champagne-Ardenne (9.44)

Table 4

 4 Okun's coefficients for each of the 22French regions, 1990French regions, -2008

	Region	OLS	GLS with AR(1)
		Coefficient	disturbances
			Coefficient
		(t-statistic)	(t-statistic)

Ile- 995) Rhône-Alpes (132,401) Provence-Alpes- 508) Nord-Pas- 440) Pays de Loire (66,734) Aquitaine (60,946) Bretagne (55,744) Midi-Pyrénées (53,056) Centre (50,565) Lorraine (44,862) FRANCE (62,222) Alsace (39,341) 416) Picardie (34,951) Bourgogne (32,435) Champagne-Ardenne (28,272) Basse-Normandie (27,200) Auvergne (25,144) Limousin (13,497) Corse (4,690)

First, the results are fairly stable across the estimation methods. Second, our specification permits heteroscedasticity to be removed, as suggested by the Breush-Pagan test. Heteroscedasticity observed in the preliminary estimates can stem from the structural instability of Okun's coefficients. Finally, the main regression results are summarized in Table 5. Table 5 Regional heterogeneity: Okun's coefficients value and significance at the 10% level

Insignificant Significant

Basse-Normandie, Bretagne, Languedoc-Roussillon, Lorraine, Limousin, Nord-Pas-de-Calais, Picardie and Poitou-Charentes.

Aquitaine (-0.91), Alsace (-0.97), Provences-Alpes-Côte-d'Azur (-1.03), Midi-Pyrénées (-1.04), Haute-Normandie (-1.06), Centre (-1.08), Champagne-Ardenne (-1.17), Corse (-1.25), Rhône-Alpes (-1.28), Bourgogne (-1.32), Ile-de-France (-1.35), Pays de Loire (-1.47), Auvergne ).

Okun's coefficients always have the correct negative sign. Our results are significant for fourteen regions only where output is responsive to unemployment changes, and in the range of -0.91 to -1.81. The largest effect of the variation in the cost of unemployment in terms of the loss in real GDP is observed in the region of Franche-Comté where a reduction of unemployment by 1% leads to an increase of regional output by 1.81%. All the regions with a


Anders Thorin
email: anders.thorin@polytechnique.edu

Xavier Boutillon

Xavier Merlhiot

J Lozada

A non-smooth simulation of the dynamics of the grand piano action

  L'archive ouverte pluridisciplinaire

Introduction

The piano action is made of seven rotating bodies (Fig. 1) with parallel axes and felts at contact zones. Simulating the dynamics of the key mechanism (we retain this term for clarity purposes) has several purposes: to validate a mechanical model, to run numerical experiments which account for the effect of the mechanism on the player's finger, to study how modifications are "felt" by the player. Bottom: rigid bodies model.

Model complexity and simulation input

The key motion y(t) and the force F (t) on the key are given by the dynamics of the mechanism and by the action imposed by the pianist (whose dynamics is also limited). If one does not describe the whole coupled system {mechanism -pianist}, which seems presently out of reach, the simulation of the mechanism only must be driven either by force data or by motion data. However, it has never been clarified whether the mechanism is better described as pseudoimpedance (force reacting to a motion imposed by the pianist) or as a pseudo-mobility (motion resulting from a force imposed by the pianist).

In order to validate a mechanical model, it is customary to compare simulation results with experimental observations. Since the dynamics of the mechanism is dominated by inertia, it appears that one can reduce the model of the whole mechanism to one single degree-of-freedom (following a dynamical equation of the form given by Eq. [START_REF] Lozada | Modélisation, contrôle haptique et nouvelles réalisation de claviers musicaux[END_REF]) and yet obtain an excellent match between experimental measurements and force-driven simulation results. However, the corresponding motion-driven simulation results do not compare well with experiments: fine details in the time-evolution of the reacting force F (t) are ignored. In other words, because of the inertia dominance, a force-driven simulation is not sufficient for accounting the details of the piano key mechanism.

Non-smooth formulation

Since an elementary model is not fully satisfactory, we used a model based on that proposed by Lozada [START_REF] Lozada | Modélisation, contrôle haptique et nouvelles réalisation de claviers musicaux[END_REF]. The 7 bodies are considered as 6 rotating solids with dry and viscous friction on their axes and 13 non-linear and localized coupling springs representing the felts (Fig. 1). Any spring force is generically given by F (g) = k g r + b g 2 ġ, where g is the compression length of the spring (felt). The equation describing the dynamics of any rigid body in the model is of generic form:

J θ + c v θ + c d sign( θ) + F (g(x)) l + α = 0 (1)
where J is the inertia of the rigid body, c v is a viscous friction coefficient, c d is a dry friction coefficient, x is the vector of generalized coordinates (i.e. the 6 angles), F (g(x)) l is the moment of the felt force (several such terms may be necessary when more than one felt act upon the considered rigid body) and α contains time-invariant terms such as the moment of gravity, in the small angles approximation. As usual, sign is the set-valued function defined by:

sign( θ) =    1 : θ > 0 [-1, 1] : θ = 0 -1 : θ < 0 (2)
so that the dry friction is described by the Coulomb model.

Because of dry friction and intermittent contacts, the simulation of the model is complex. One difficulty is that Eq. ( 1) is not an ODE. Regularizing the sign set-valued function yields ODEs but the convergence to a physical solution when reducing the time step is not ensured. An example can be seen in the equilibrium position: null-velocities imply vanishing regularized friction forces whereas the Coulomb friction generally lets non-zero forces in the system. Another difficulty is that stick-slip transitions induce velocity discontinuities. Furthermore, the evaluation of the moment of the reaction contact forces F (g(x)) is tedious. These difficulties can be overcome by using methods of non-smooth contact dynamics (NSCD).

Instead of writing the dynamics in the form of six coupled equations of the form (1), we use a Measure Differential Inclusion formulation [START_REF] Merlhiot | On some industrial applications of time-stepping methods for nonsmooth mechanical systems: issues, successes and challenges[END_REF]:

   Mdv = F * (t)dt + H(x)di v + = ( ẋ) + (g(x), H T (x).v + , di) ∈ K (3)
The first equation formulates the non-smooth dynamics where M is the mass matrix, v is the generalized velocity, F * is the regular part of the sum of external forces, including gravity. dv and di are vector-valued measures on R and can therefore be non-smooth. H relates the relative velocities to the generalized coordinates. The non-smooth laws (Coulomb and articular friction, impacts) and equality constraints are written as an inclusion in the fixed set K.

Eqs. (3) are discretized using a time-stepping scheme. Its solution is computed with an implicit scheme. As for smooth ODEs, it requires a root-finding algorithm (Newton's algorithm in our case). The time-discretization of the non-smooth dynamics and the non-smooth laws leads to a One-Step Non-Smooth Problem (OSNSP) [START_REF] Acary | Numerical methods for nonsmooth dynamical systems: applications in mechanics and electronics[END_REF]. This OSNSP is reformulated using a non-smooth augmented Lagrangian approach and solved using an iterative projective Gauss-Seidel-like method.

Results

We used XDE (eXtended Dynamic Engine), a software component developed at CEA, LIST. The inputs of the software are the geometrical and inertial descriptions of the pieces (here: the rigid bodies), the properties of the pivots (here: dry and viscous friction) and the contact laws (here: the coupling forces of the springs and the Coulomb friction). The software implements internally the non-smooth formulation of the dynamics and its solution, as described in Sec. 2.

An additional spring/damper association, aimed at representing the softness of the finger, has been inserted between the key mechanism and the (forceor motion-)driver of the mechanism. We measured the position of the key and the force applied by the pianist for several nuances, on one individual key. As for the results obtained with the one-degree-offreedom model (Sec. 1), the results of a force-driven simulation compare correctly with the measured motion. Contrary to the results obtained with the onedegree-of-freedom model, the results of the motiondriven simulation compare also correctly with the measured force.

The calculation time (≈ 20× real-time) on an ordinary laptop computer could be largely improved by taking into account the particularities of the model of the key mechanism.

Figure 1 :

 1 Figure 1: Top: scheme of the grand piano action.Bottom: rigid bodies model.


Serge Abiteboul

Émilien Antoine

Gerome Miklau
email: miklau@cs.umass.edu

Julia Stoyanovich
email: stoyanovich@drexel.edu

Jules Testard
email: jules.testard@mail.mcgill.ca

Rule-Based Application Development using Webdamlog *

We present the WebdamLog system for managing distributed data on the Web in a peer-to-peer manner. We demonstrate the main features of the system through an application called Wepic for sharing pictures between attendees of the sigmod conference. Using Wepic, the attendees will be able to share, download, rate and annotate pictures in a highly decentralized manner. We show how WebdamLog handles heterogeneity of the devices and services used to share data in such a Web setting. We exhibit the simple rules that define the Wepic application and show how to easily modify the Wepic application.

Introduction

Information management on the Internet relies on a wide variety of systems, each specialized for a particular task. A user's data and favorite applications are often distributed, making the management of personal data and knowledge (i.e., programs) a major challenge. Consider Joe, a typical Web user who has a blog on Wordpress.com, a Facebook account, a Dropbox account, and also stores data on his smartphone and laptop. Joe is a movie fan and he wants to post on his blog a review of the last movie he watched. He also wishes to advertise his review to his Facebook friends and to include a link to his Dropbox folder where the movie has been uploaded. This is a cumbersome task to carry out manually, yet automating it, for example by writing a script, is far beyond the skills of most Web users. Some systems attempt to provide integrated services to support such needs. For instance, Facebook provides a wrapper service to integrate Dropbox accounts and blogs. However, such services are often limited in the functionality they support. Also, by delegating such services to systems like Facebook, a user needs to trust more and more of his information to one particular system. Our goal is to enable the user to easily specify distributed data management tasks in place (i.e., without centralizing his data to a single provider), while allowing him to keep full control over his own data [START_REF] Abiteboul | Viewing the Web as a Distributed Knowledge Base[END_REF]. Our system is not a replacement for Facebook, or any centralized system, but it allows users to launch their customized peers on their machines with their own personal data, and to collaborate using Web services.

This demonstration presents the Wepic application, a distributed picture manager. The Wepic application is specified using simple rules written in a declarative language called Web-damLog [START_REF] Abiteboul | A rule-based language for Web data management[END_REF] and it runs on the WebdamLog system, demonstrated here for the first time. WebdamLog is a rule-based datalog-style language that emphasizes cooperation between autonomous peers by allowing both data, and programs that compute on data, to be easily exchanged. The declarative approach alleviates the conceptual complexity on the user while, at the same time, allowing for powerful performance optimizations on the part of the system.

A central issue in such a setting is the ease with which a casual user can write WebdamLog rules. We conducted a user study, showing that users are able to both understand and write simple WebdamLog programs with a minimal amount of training [5]. This demonstration further argues for the simplicity of using WebdamLog for designing applications that handle personal data.

sigmod attendees will use Wepic to share, download, rate and annotate pictures taken at the conference. Attendees will use the application via a Web GUI or launch their own Wepic peer. They will first inspect the basic WebdamLog rules of the provided application and will then be invited to customize the application by modifying or adding rules.

Language and System

body is not relevant. Although negation is supported by the language, it is not yet implemented in the WebdamLog system.

WebdamLog peers, in brief Each peer runs a WebdamLog program, i.e., a set of rules, using a WebdamLog engine. The evaluation of datalog has been studied for decades but a renewed interest in datalog [START_REF] Abiteboul | The active xml project: an overview[END_REF][START_REF] Hellerstein | The declarative imperative: experiences and conjectures in distributed logic[END_REF]9] has led to the recent development of the Bud [6] datalog engine, which we use as part of our implementation. The Bud system supports efficient communication between peers and updates of base facts.

A computation stage of the WebdamLog engine is broken down into three steps. First, the peer loads the inputs received from the remote peers since the previous stage. Second, the peer runs a fixpoint computation of its program. Third, the peer sends facts (updates) and rules (delegations) to other peers. A main novelty is the possibility for WebdamLog rules to have variables as relation and peer names. Another main novelty is delegation, which leads to installing, at run-time rules, at other peers. As a result, WebdamLog programs may be very dynamic, peers may discover new peers and new relations and they may acquire new rules as the result of delegations.

The WebdamLog system follows prior work on a P2P system for sharing data called WebdamExchange [START_REF] Abiteboul | Web information management with access control[END_REF][START_REF] Antoine | Demo] Social Networking on top of the WebdamExchange System[END_REF]. The present focus is very different (declarative specification and delegation in WebdamLog vs. security in WebdamExchange), so little of the previous system could be re-used.

Wrappers

The WebdamLog system has been designed for integration with the personal data of regular Web users who already use popular Web systems such as Facebook, Picasa or Dropbox. The WebdamLog system supports the management of data in these systems by using wrappers. A wrapper to some existing system X provides software that exports to Web-damLog one or more relations corresponding to the data in X, as well as rules to access/update this data.

For example, in the demonstration we will use a Facebook wrapper. For a given Facebook user Émilien, our wrapper will simulate a peer ÉmilienFB with two relations: friends@ÉmilienFB($userID, $friendName) pictures@ÉmilienFB($picID, $owner, $URL) These two relations provide an abstract view of Émilien's Facebook data relevant to this particular application, and can then be used in WebdamLog rules.

Access control Since many WebdamLog applications will manage personal or social data, access to sensitive information must be carefully controlled. Access control in WebdamLog is particularly challenging because of the distributed nature of computation and the ability of peers to delegate rules to other peers. We describe in the next section the features included in the demonstration for controlling the delegation of rules, in which a peer is asked to explicitly accept delegations initiated by other peers.

A complete access control model for WebdamLog is under active investigation and is not included in the demonstration. In that model, access to stored or derived relations is controlled by a novel combination of both discretionary methods (in which users have the power to grant rights to data they own) and mandatory methods (in which access rights are derived according to system-wide conventions). Users directly specify the accessibility of stored relations that they own. For derived relations (i.e. views), a user may rely on a default access control policy that is derived automatically from the provenance of the base relations. Alternatively, a user may override this policy in order to grant access to views, effectively "declassifying" some data. This flexible model subsumes the view-based access control of the standard SQL authorization model.

The Wepic application

To demonstrate the WebdamLog system, we introduce an application called Wepic, a conference picture manager for the sigmod conference. This application allows conference attendees to share their pictures and to rate, annotate and download the pictures of others.

Wepic consists of a small set of rules that we discuss further. In addition, the application uses two standard wrappers we implemented, one for Facebook, and one for email communications. The WebdamLog system provides a graphical interface, which has been customized to provide a user interface for Wepic. It is shown in Figure 1.

A user connected to a Wepic peer can:

1. Upload a picture from a file or a URL; 2. View pictures provided by a particular attendee; We now illustrate how some of these units of functionality are implemented with WebdamLog rules. To view pictures uploaded by a particular sigmod attendee, we use a relation selectedAttendees that contains one fact for each currently highlighted attendee (see right-hand side column in Figure 1). We also use a derived relation pictures, which is the view of all the pictures of a particular attendee. To obtain the pictures of all selected attendees, we use the rule:

attendeePictures@Jules($id, $name, $owner, $data) :-selectedAttendee@Jules($attendee), pictures@$attendee($id, $name, $owner, $data) Note that this rule uses delegation, a feature novel to Web-damLog, to retrieve the contents of relation pictures of each attendee. The result of executing this rule is shown in the Attendee pictures frame at the bottom of Figure 1. To transfer pictures between peers, we assume that each attendee specifies some preferred communication protocols in relation communicate, stating, e.g., whether he prefers to receive pictures by email, by posting on Facebook, or directly in his Wepic peer. The following rule is executed when Jules sends some pictures to some attendees:

$protocol@$attendee($attendee, $name, $id, $owner) :-selectedAttendee@Jules($attendee), communicate@$attendee($protocol), selectedPictures@Jules($name, $id, $owner) Rules of this kind, and other rules implementing the basic functionality of Wepic, are available for inspection and customization through the user interface, see Figure 3.

Delegation and access control

As noted in Section 2, by using delegation a user may write a rule and ask another peer to process it remotely. Consider again the previous rule:

attendeePictures@Jules($id, $name, $owner, $data) :-selectedAttendee@Jules($attendee), pictures@$attendee($id, $name, $owner, $data) Suppose we have the facts: selectedAttendee@Jules("Émilien") The evaluation of the rule leads to delegating the following rule to Émilien: attendeePictures@Jules($id, $name, $owner, $data) :pictures@Émilien($id, $name, $owner, $data) to send all the facts in his relation pictures to Jules. This is a simple case of delegation, which be controlled by inferring access from the specifications described above. However delegated rules can be more complex, and general methods for effectively controlling delegation are a topic of continued investigation. The demonstration of Wepic will provide a simplified model for control of delegation, in which each delegation sent by an untrusted peer will be pending in a queue until the user explicitly accepts it via the Web interface. A notification of a pending delegation can be seen at the top of Figure 3, where Julia is sending a rule to Jules. By default, all peers except the sigmod peer will be considered untrusted.

Demonstration Scenarios

We now describe the general proceedings of the demonstration. The goal will be to share pictures taken during the sigmod conference. Émilien and Jules are attendees of the conference.

They have used Wepic to install locally on their laptops a collection of pictures. They demonstrate how to use Wepic with the native functionalities described in Section 3 and how to customize the application. They will also allow a user at the conference to run his own Wepic peer to explore the system. This scenario will demonstrate the various aspects of WebdamLog, notably distribution, delegation and control of delegation.

Setup

In the beginning of the demo, three peers are established: one on each of the laptops of Émilien and Jules, connected via a local network, and a third, the sigmod peer, hosted on Webdam cloud. To simplify the presentation, we will assume that Émilien and Jules organize their data and behave similarly. They both store their photos in pictures@Émilien and pictures@Jules on their respective Wepic peers. Both have Facebook accounts and are members of the SigmodFB group, the official Facebook group of the conference. Finally, both users are subscribed to the sigmod peer, which stores the list of registered Wepic users.

The Wepic peers Émilien, Jules and sigmod are depicted in Figure 2. We will start the demonstration by quickly going over the setup, and will then ask the user to interact with Wepic according to the following scenarios.

Interaction via Facebook

To illustrate the interaction between a Wepic peer and other Web services, we use a Facebook wrapper. For instance, the following rule is used by the sigmod peer to automatically publish, on the Facebook group of sigmod, the pictures belonging to sigmod attendees who have authorized this action:

pictures@SigmodFB($id, $name, $owner, $data) :pictures@sigmod($id, $name, $owner, $data), authorized@$owner("Facebook", $id, $owner) Conversely, the sigmod peer will automatically retrieve the pictures with their comments and tags from the Facebook group and publish them to sigmod peer. Note that the system thus allows any Wepic user to see or publish (via Wepic) pictures in SigmodFB even without having a Facebook account. A user only needs to appropriately populate his authorized relation to control Facebook publication.

We will explain the WebdamLog rules that implement these interactions to audience members. We will then show that a photo uploaded by Émilien into his local relation pictures@Émilien is instantly published to pictures@sigmod, and then propagated to pictures@SigmodFB.

Customizing rules

The main advantage of a peer-to-peer system such as WebdamLog is the ability to customize a peer's behavior. Therefore the most novel trait of Wepic is that it lets the user customize existing rules and add his own rules. For example, a user who is interested only in the pictures that have a rating of 5 would customize the rule of the application as follows:

attendeePictures@Jules($id, $name, $owner, $data) :-selectedAttendee@Jules($attendee), pictures@($id, $name, $owner, $data), rate@$owner($id, 5) Redefining this rule will change the contents of the frame Attendee pictures in Figure 1, which we will demonstrate. We will explain this rule and its effect to audience members, and will then allow them to customize the rule further, retrieving, e.g., only pictures that were taken by a certain sigmod attendee, or in which only certain attendees appear.

Illustration of the control of delegation

To illustrate the control of delegation, Émilien will attempt to install a rule at Jules' peer. We will demonstrate that the system requires the approval of Jules before installing the rule, and that the program of Jules is changed once the approval is granted and the rule is installed.

Interaction via the Web Finally, we will invite audience members to launch their own autonomous Wepic peers in the Webdam cloud, and to interact with their peer through a UI, using their smartphone or a tablet that we provide. From that point on, they will be able to use all features of Wepic described in Section 3, e.g., upload their conference photos to their own peer. In addition, they will be able to use the Query tab to launch one of the pre-defined queries, or to write their own WebdamLog queries and rules with the assistance of the demo authors.

3 .

 3 Transfer pictures: a) send them by email to the sigmod group on Facebook, or to another Wepic peer, b) get pictures from another Wepic peer or from the sigmod group on Facebook; 4. Annotate pictures with ratings, comments or name tags (names of attendees appearing in the picture); 5. Select and rank photos based on their annotations.

Figure 1 :

 1 Figure 1: A screenshot of the Wepic user interface.

Figure 2 :

 2 Figure 2: The distribution of peers in the network.

Figure 3 :

 3 Figure 3: The interface to a WebdamLog program running Wepic.

* This work has been partially funded by the European Research Council under the European Community's Seventh Framework Program (FP7/2007-2013); ERC grant Webdam, agreement 226513. http://webdam.inria.fr/


Jean François

Djoufak Kengue

Jérôme Euzenat
email: jerome.euzenat@inrialpes.fr

Petko Valtchev
email: valtchev.petko@uqam.ca

OLA in the OAEI 2007 Evaluation Contest

Similarity has become a classical tool for ontology confrontation motivated by alignment, mapping or merging purposes. In the definition of an ontologybased measure one has the choice between covering a single facet (e.g., URIs, labels, instances of an entity, etc.), covering all of the facets or just a subset thereof. In our matching tool, OLA, we had opted for an integrated approach towards similarity, i.e., calculation of a unique score for all candidate pairs based on an aggregation of all facet-wise comparison results. Such a choice further requires effective means for the establishment of importance ratios for facets, or weights, as well as for extracting an alignment out of the ultimate similarity matrix. In previous editions of the competition OLA has relied on a graph representation of the ontologies to align, OL-graphs, that reflected faithfully the syntactic structure of the OWL descriptions. A pair of OL-graphs was exploited to form and solve a system of equations whose approximate solutions were taken as the similarity scores. OLA2 is a new version of OLA which comprises a less integrated yet more homogeneous graph representation that allows similarity to be expressed as graph matching and further computed through matrix multiplying. Although OLA2 lacks key optimization tools from the previous one, while a semantic grounding in the form of WORDNET engine is missing, its results in the competition, at least for the benchmark test suite, are perceivably better.

Introduction

Ontologies, i.e., explicit conceptualizations of a domain involving representations of domain concepts and relations, are now the standard way to approach data heterogeneity on the Web and insure application interoperability. However, the existence of independently built ontologies for the same domain is a source of heterogeneity on its own and therefore calls for the design of methods and tools restoring interoperability through ontology matching.

Similarity has become a classical tool for ontology matching. In the definition of an ontology-based similarity measure one has the choice between covering a single facet (e.g., URIs, labels, instances of an entity, etc.), covering all of the facets or just a subset thereof. Typically, a distinction is made between the way ontology entities are named and the way these are related to other entities within the ontology, the former being termed depending on the context "lexical", "linguistic", "terminological", etc. while the latter is usually qualified as "structural". Structural similarity measurement is performed as a form of graph matching whereas lexical one boils down to either string comparison or matching of representations of the semantic of terms in entity names.

Our matching tool OLA [START_REF] Euzenat | An integrative proximity measure for ontology alignment[END_REF][START_REF] Euzenat | Similarity-based ontology alignment in OWL-Lite[END_REF] targets OWL-DL (formerly OWL-LITE) ontologies. It applies an integrated approach towards similarity, i.e., calculation of a unique score for all entity pairs based on an aggregation of all facet-wise comparison results (facets here stand for the relationships between OWL entities). Computation is exhaustive on entity descriptions meaning that all facets are covered. The similarity is defined through a category-sensitive3 yet universal operator that basically computes a linear combination of facet similarities. As facets mostly represent entities of their own, the similarity definition gets circular and hence cannot be directly computed. OLA considers such definitions as equations to solve and approximates their solutions through an iterative fixed-point-bound process. As initial values are based on name comparison while iterations basically perform similarity exchange between pairs of neighbor entities, OLA similarity is a trade-off between the aforementioned structural and lexical aspects.

Previous participation of OLA in the alignment competitions [START_REF] Euzenat | Ontology alignment with OLA[END_REF][START_REF] Euzenat | OLA in the OAEI 2005 alignment contest[END_REF], despite globally positive outcome, have put the emphasis on a certain lack of homogeneity among the computational mechanisms at different levels of the similarity model that harm efficiency. These were traced back to the somewhat overloaded structure of the OL-graphs, the graph-based representation of OWL ontologies that was used to support the similarity computation.

Restoring homogeneity and improving efficiency was the motivation behind the OLA2 version that is developed jointly by UQÀM and INRIA. It introduced a flattened version of the OL-graph model where at most one scalar value is admitted in vertices while all the remaining information is in the edges. This allowed the iterative re-calculation of the similarity scores to be modeled as matrix operation without losing the valuable properties of the result nor the process.

To that end, the ontology graphs are combined into a product-like construct, the match graph, where vertices and edges are products of counterpart elements from the ontology graphs. Similarity computation represents an iterative value propagation across the match graph starting with initial values yielded by name comparison. The innovation is the matrix product used in re-calculations: the adjacency matrix of the match graph is used as the multiplicative factor leading to a fixed point. The resulting method is a step further towards structure-domnated similarity computation as it encompasses all relationships of an ontology entity whereas the previous version tended to disregard non-descriptive relationships (e.g., the one between a OWL class and a relation whose range the class represents).

Our new method has outperformed the initial version of OLA on both competition tests (benchmark) and efficiency, although many of the optimizations from previous years have not been implemented in it. More dramatically, its modular implementation eases future improvements.

System Overview

OLA is an open-source tool, implementing the OLA algorithm (for OWL-Lite Alignment [START_REF] Euzenat | Similarity-based ontology alignment in OWL-Lite[END_REF]), jointly developed by teams at University of Québec at Montréal and INRIA Rhône Alpes.

General purpose statement

The primary goal behind the OLA tool design is to perform alignment of ontologies expressed in OWL [START_REF] Euzenat | An integrative proximity measure for ontology alignment[END_REF][START_REF] Euzenat | Similarity-based ontology alignment in OWL-Lite[END_REF], with an emphasis on OWL-DL (formerly OWL-LITE). The system offers similarity-based alignment on graph-like ontology representations. Beside alignment, it features a set of auxiliary services supporting the manipulation of alignment results.

Ontology graph model

Traditionally, an ontology is viewed as a set of entities and a set of relationships between those entities. This view underlies the translation of the ontologies into a graphs structure where entities become vertices and relationships edges. Yet in the new settings, beside language entity categories such as classes, objects, relations, properties, property instances, and data types, data values, less traditional ones are considered, i.e., tokens (including comments on entities) and cardinalities. The list of relationships is accordingly completed: together with previously existing in the OL-graph format subsumption, instantiation, attribution, domain, range, restriction, valuation, and all relationships, we exploit card and name. Fig. 1 provides an overview of the meta-model for the ontology graph format.

Both vertices and edges in the graph are labeled by their respective entity category/relationship.

As a support for similarity computation, the product of both ontology graphs, or their match graph, is composed. The vertices of the match graphs are pairs of vertices from opposite ontology graphs. In its basic version, the match graphs comprises the cartesian product of both vertex sets, i.e., same category is not required for vertices v 1 and v 2 to form a product vertex. Clearly, product vertices correspond to the variables of the equation system in the previous version of OLA. They embed a "weight" value which stands for the similarity and is computed iteratively (see below).

In contrast, match graph edges require strict correspondence: An edge labeled l exists between compound vertices (v 1 , v 2 ) and (v ′ 1 , v ′ 2 ) iff there exist an edge labeled l between v 1 and v ′ 1 in the first graph another one between v 2 and v ′ 2 in the second graph. Edges in the match graph are also weighted yet their weights are effective as they correspond to the weights on neighboring sets in the OL-graphs in version one.

Similarity model Similarity between entities of the initial graphs is reflected by the weight or importance index of the corresponding match graph node. The underlying computational model is the value propagation as described in [START_REF] Blondel | A measure of similarity between graph vertices. with applications to synonym extraction and web searching[END_REF] (and used in a range of alignment methods starting with [START_REF] Hu | GMO: A graph matching for ontologies[END_REF]) across the graph. We recall that, the adjacency Relationships between ontology entities with respect to the cluster to which they belong matrices of the initial graphs are used to produce a larger matrix M reflecting both the inbound and the outbound neighbors of a match vertex. M is then used as a multiplier for the similarity vector V . Thus, starting with initial values, typically 1 for all entity pairs, V evolves according to the following iterative dependency: V k = M × V k-1 (k = 1, 2, 3...), until a fixed point is reached.

Yet the model has been adapted -and even somewhat spoiled -as to compute the similarity defined in the reference OLA version. Recall that for a category X together with the set of relationships it is involved in, N (X), the similarity measure Sim X : X 2 → [0, 1] is defined as follows:

Sim X (x, x ′ ) = F ∈N (X) π X F M Sim Y (F(x), F(x ′ )).
The function is normalized, i.e., the weights π X F sum to one, F ∈N (X) π X F = 1. Moreover, the set functions M Sim Y compare two sets of nodes of the same category and extract a maximal pairing thereof that further optimizes the total similarity (see [START_REF] Euzenat | Similarity-based ontology alignment in OWL-Lite[END_REF] for details).

In order to simulate the above family of functions, the graph-based model introduces first-class weights on relationship sets adjacent to a match vertex. Hence the adjacency matrix of the match graph that is central to the value propagation is not purely Boolean: values between 0 and 1 appear. Moreover, the above equation is modified to reflect the evolving contribution of neighbor nodes:

V k = M k × V k-1 (k = 1, 2, 3... and M k = f (M k-1 , V k-1 ))
Here M k reflects possible changes in pairings between contributing vertices within a set of neighbors, a recalculation that is done at each iteration in basic OLA. Hence f involves the current solution vector, as well.

Further adaptation of the original method is the initialization of V 0 with the results from name comparison for entities in a match vertex. This corresponds strictly to the initialization of the equation system in OLA.

The last adaptation completely changes the ideology of the method as it plays against the very basic principle of propagation: at each step a value at a vertex is replaced by a combination of the values of all its neighbors. Our understanding is that this is a major reason for the convergence of the computed values only for even steps.

In our model, the stabilizing role of name similarity (which is computed only once) has been secured by a representation trick. In fact, the vertices representing the sources of stable similarity, i.e., token, cardinality, data type, etc. are provided with a local looping edge while fixing their weights till the end of the process. Hence the respective OWL entity node that is identified by the token gets the same value at each iteration.

The above process provenly converges towards a solution vector V ∞ .

Past optimizations A number of optimizations have been implemented within the system mainly aimed at making the weights -matching -similarity scheme more flexible. First, mechanisms for weight adaptation, both at entity and ontology level have been designed. The goal is to insure that the absence of a specific facet locally, i.e., for an entity pair, or globally, i.e., for all pairs, does not result in unbalanced similarity scores. An extension thereof based on simple statistics provides the basis for an even further adaptation of initial facet weights that in a way reflective of the relative importance of each facet. The nature of the name measure to use, i.e., string-based or term-based, is heuristically determined based on similar reasoning. Many of the optimizations could not be implemented in the current version. Yet a new optimization could be designed to help offset the impact of meaningless names. It consists in replacing the label of a token vertex with the set of labeled paths that head towards that vertex. -Alteration/suppresion of specialization hierarchy -Suppression of some properties and/or instances -Mean Precision = 0.97 and Mean Recall = 1.00 #248-266:

Link to

-Alteration of all names -Suppression of all comments -Alteration of specialization hierarchy (in most cases) -Suppression of some instances and/or properties -Mean Precision = 0.77 and Mean Recall = 0.51 #301-304:

-Real-world ontologies -Mean Precision = 0.63 and Mean Recall = 0.73

Conference

-We align every possible couple of ontologies -We ran OLA2 with the set of parameters used for the benchmarks test case

Directory

We ran OLA2 with the set of parameters used for the benchmarks test case.

Others

OLA2 was unable to run because of the large size of matrices extracted from ontology graphs.

General Comments

Results

OLA2 significantly improves on the previous version of OLA. This may be seen on the benchmark results which are better. The additional benefits of the new implementation are extensibility and modularity of code.

Yet the method heavily relies on similarity of vertice labels (entity names or paths). A look on the tests where OLA scored poorly reveals that. 1. Factorization of ontology graphs to run OLA on large-size ontologies [START_REF] Papadopoulos | Drawing graphs using modular decomposition[END_REF][START_REF] Ryan | Graph decomposition for efficient multi-robot path planning[END_REF]; 2. Search for the set of optimal of weight values; 3. Integration of semantic string distances [START_REF] Euzenat | Ontology matching[END_REF] within the OLA matching process; 4. Integration of explicit inheritance edges among classes and among properties.

Conclusion

OLA2 is arguably better now than two years ago. The progress on real-world ontologies (30X), a class the previous version had difficulties dealing with, is encouraging. Yet more encouraging is the fact that these results have been obtained with very few adaptation tricks. In this respect, our next target will be the weight computing mechanisms of previous OLA.

  Fig.1. Relationships between ontology entities with respect to the cluster to which they belong

-

  OLA: https://gforge.inria.fr/frs/?group_id=271 Link to alignments and parameters file : http://ola.gforge.inria.fr/results/OAEI-2007-OLA.zip 3 Results of Execution on Test Cases 3Mean Precision = 1.00 and Mean Recall = 1.00 #201-204: -Alteration of names and/or suppresion of comments -Mean Precision = 0.92 and Mean Recall = 0.92 #205-210: -Synonyms and/or foreign language -Mean Precision = 0.90 and Mean Recall = 0.90 #221-223: -Alteration of specialization hierarchy -Mean Precision = 0.99 and Mean Recall = 1.00 #224-228: -Absence of instances, properties and/or restrictions -Mean Precision = 1.00 and Mean Recall = 1.00 #230-231: -Classes expanded or flattened -Mean Precision = 0.96 and Mean Recall = 1.00 #232-247:

-

  #201-204 & #248-266: choice among entities having similar roles within their respective ontology graphs (e.g., test #253), -#205-210 & #301-304: lack of semantic string distance and language translator, -#221-223 & #230-231 & #232-247: no explicit inheritance edge between classes and properties 4.2 Future Improvements

Entity categories, e.g., OWL class, property, object, data type, value, etc., compare to metaclasses of language meta-model

Acknowledgments

This work was partly supported by the NSERG Discovery grant of the third author. The second author has been supported by the European integrated project NeOn (IST-2005-027595) and the RNTL project Web-Content. A short term visit by the first author at EXMO research team, INRIA Rhône-Alpes, France was jointly supported by the NSERG and NeOn grants.


Jérôme Euzenat
email: jerome.euzenat@inrialpes.fr

Semantic Precision and Recall for Ontology Alignment Evaluation

In order to evaluate ontology matching algorithms it is necessary to confront them with test ontologies and to compare the results with some reference. The most prominent comparison criteria are precision and recall originating from information retrieval. Precision and recall are thought of as some degree of correction and completeness of results. However, when the objects to compare are semantically defined, like ontologies and alignments, it can happen that a fully correct alignment has low precision. This is due to the restricted set-theoretic foundation of these measures. Drawing on previous syntactic generalizations of precision and recall, semantically justified measures that satisfy maximal precision and maximal recall for correct and complete alignments is proposed. These new measures are compatible with classical precision and recall and can be computed.

Introduction

Ontology matching is an important problem for which many algorithms have been provided [START_REF] Euzenat | Ontology matching[END_REF]. Given a pair of ontologies, these algorithms compute a set of correspondences between entities of these ontologies, called alignment.

In order to evaluate such algorithms, they are confronted with ontologies to match and the resulting alignment (A)i s compared to a reference alignment (R) based on some criterion. The usual approach for evaluating the returned alignments is to consider them as sets of correspondences and to apply precision and recall originating from information retrieval [START_REF] Van Rijsbergen | Cornelis Joost (Keith) van Rijsbergen. Information retrieval[END_REF] and adapted to the matching task. Precision and recall are the ratio of the number of true positive (|R ∩ A|) on that of the retrieved correspondences (|A|) and those expected (|R|) respectively. These criteria are well understood and widely accepted.

There are problems with using precision and recall in this context. As reported in [START_REF] Ehrig | [END_REF], these measures have the drawback to be of the all-or-nothing kind. An alignment may be very close to the expected result and another quite remote from it and both sharing the same precision and recall values. The reason for this is that the criteria only compare two sets of correspondences without considering if these correspondences are close or remote to each other: if they are not the same exact correspondences, they score zero. They both score identically low, despite their different quality.

Moreover, there can be semantically equivalent alignments which are not identical. A fair measure of alignment quality should rank these alignments with the same values (or at least, closer values than non equivalent alignments). It is thus necessary to design semantically grounded alignment measures instead of measures based on their syntactic equality.

In this paper we investigate some measures that generalize precision and recall in order to overcome the problems presented above. We first provide the basic definitions of alignments, semantics, precision and recall as well as a motivating example ( §2). We then present the framework for generalizing precision and recall introduced in [START_REF] Ehrig | [END_REF]] ( §3). From that point we investigate and propose new semantically justified evaluation versions of precision and recall. We discuss their properties and define complementary measures ( §4). We show on the motivating example that the proposed measures improve on previous ones ( §5).

Foundations

We first precisely define what are alignments through their syntax ( §2.1) and semantics ( §2.2) before introducing precision and recall adapted to alignments ( §2.3).

We will consider ontologies as logics. The languages used in the semantics web such as RDF or OWL are indeed logics. The semantics of the ontologies are given through their set of models.

Alignments

The result of matching, called an alignment, is a set of pairs of entities e, e ′ from two ontologies o and o ′ that are supposed to satisfy a certain relation r with a certain confidence n.

Definition 1 (Alignment, correspondence). Given two ontologies o and o ′ , an alignment between o and o ′ is a set of correspondences (i.e., 4-uples): e, e ′ ,r,n with e ∈ o and e ′ ∈ o ′ being the two matched entities, r being a relationship holding between e and e ′ , and n expressing the level of confidence in this correspondence.

IJCAI-07

For the sake of simplicity, we will here only consider correspondences as triples e, e ′ ,r . The best way to compare results with confidence is to plot their precision/recall functions. The examples are only provided for simple ontologies, which are class hierarchies but do not depend on this simple language.

Figure 1 presents two ontologies together with five alignments R, A 1 , A 2 , A 3 , and A 4 . R is the reference alignment and can be expressed by the following equations:

R = Employee = Worker Accounting = Headquarters Production ≤ Japan Marketing ≤ Spain
The other alignments share the first two correspondences with the reference alignment and have additional ones:

A 1 = Employee = Worker Accounting = Headquarters Electronics ≤ Japan Computer ≤ Spain A 3 = Employee = Worker Accounting = Headquarters Electronics ≤ Worker Computer ≤ Worker A 4 = Employee = Worker Accounting = Headquarters Optics ≥ Spain Marketing ≥ Saleforce
Alignment A 2 contains more correspondences than the others, it is made of the following:

A = Employee ≤ Worker Accounting ≤ Headquarters Employee ≥ Worker Accounting ≥ Headquarters Production ≤ Japan Marketing ≤ Spain

Semantics of alignments

In the line of the work on data integration [START_REF] Ghidini | [END_REF]], we provide a first-order model theoretic semantics. It depends on the semantics of ontologies but does not interfere with it. In fact, given a set of ontologies and a set of alignments between them, we can evaluate the semantics of the whole system in function of the semantics of each individual ontology. The semantics of an ontology is given by its set of models. Definition 2 (Models of an ontology). Given an ontology o,a model of o is a function m from elements of o to elements of a domain of interpretation ∆. The set of models of an ontology is noted M(o).

Because the models of various ontologies can have different interpretation domains, we use the notion of an equalising function, which helps making these domains commensurate. Definition 3 (Equilising function). Given a family of interpretations I o , ∆ o o∈Ω of a set of ontologies Ω, an equalising function for I o , ∆ o o∈Ω is a family of functions γ = (γ o :∆ o -→ U ) o∈Ω from the domains of interpretation to a global domain of interpretation U . The set of all equalising functions is called Γ.

When it is unambiguous, we will use γ as a function. The goal of this γ function is only to be able to (theoretically) compare elements of the domain of interpretation. It is simpler than the use of domain relations in distributed first order logics [START_REF] Ghidini | [END_REF]] in the sense that there is one function per domain instead of relations for each pair of domains.

The relations used in correspondences do not necessarily belong to the ontology languages. As such, they do not have to be interpreted by the ontology semantics. Therefore, we have to provide semantics for them.

Definition 4 (Interpretation of alignment relations). Given r an alignment relation and U a global domain of interpretation, r is interpreted as a binary relation over U , i.e., r U ⊆ U × U .

The definition of correspondence satisfiability relies on γ and the interpretation of relations. It requires that in the equalised models, the correspondences be satisfied.

Definition 5 (Satisfied correspondence). A correspondence c = e, e ′ ,r is satisfied for an equalising function γ by two models m, m ′ of o, o ′ if and only if γ o • m ∈M(o), γ o ′ • m ′ ∈ M(o ′ ) and γ o (m(e)),γ o ′ (m ′ (e ′ )) ∈r U This is denoted as m, m ′ |= γ c.
For instance, in the language used as example, if m and m ′ are respective models of o and o ′ :

m, m ′ |= γ c, c ′ , = iff γ o (m(c)) = γ o ′ (m ′ (c ′ )) m, m ′ |= γ c, c ′ , ≤ iff γ o (m(c)) ⊆ γ o ′ (m ′ (c ′ )) m, m ′ |= γ c, c ′ , ≥ iff γ o (m(c)) ⊇ γ o ′ (m ′ (c ′ )) m, m ′ |= γ c, c ′ , ⊥ iff γ o (m(c)) ∩ γ o ′ (m ′ (c ′ )) = ∅ IJCAI-07 Definition 6 (Satisfiable alignment). An alignment A of two ontologies o and o ′ is said satisfiable if and only if ∃m ∈M(o), ∃m ′ ∈M(o ′ ), ∃γ ∈ Γ; ∀c ∈ A, m, m ′ |= γ c
Thus, an alignment is satisfiable if there are models of the ontologies that can be combined in such a way that this alignment makes sense.

Definition 7 (Models of aligned ontologies). Given two ontologies o and o ′ and an alignment A between these ontologies, a model of these aligned ontologies is a triple

m, m ′ ,γ ∈M (o) ×M(o ′ ) × Γ, such that A is satisfied by m, m ′ ,γ .
In that respect, the alignment acts as a model filter for the ontologies. It selects the interpretation of ontologies which are coherent with the alignments. Note, this allows to transfer information from one ontology to another since reducing the set of models will entail more consequences in each aligned ontology.

In this paper we consider those consequences of aligned ontologies that are correspondences. For α-consequences, A 2 is strictly equivalent to R (i.e., A 2 |= R and R |= A 2 ). In fact, the aligned ontologies with A 2 and R have exactly the same models.

It is noteworthy that, given an alignment, the αconsequences of this alignment can be larger than it. If the alignment is not satisfiable, then any correspondence is a αconsequence of it.

Such a formalism helps defining the meaning of alignments: it tells what are the consequences of ontologies with alignments. It is particularly useful for deciding if delivered alignments are consistent and for specifying what is expected from matching algorithms and how they should be designed or evaluated. It can be naturally extended to distributed systems in the sense of [START_REF] Ghidini | [END_REF]], i.e., sets of ontologies and alignments.

Precision and recall

Precision and recall are commonplace measures in information retrieval. They are based on the comparison of an expected result and the effective result of the evaluated system. These results are considered as a set of items, e.g., the documents to be retrieved.

Since these measures are commonly used and well understood, they have been adapted for ontology alignment evaluation [START_REF] Do | Comparison of schema matching evaluations[END_REF]. In this case, sets of documents are replaced by sets of correspondences, i.e., alignments. The alignment (A) returned by the system to evaluate is compared to a reference alignment (R).

Like in information retrieval, precision measures the ratio of correctly found correspondences (true positives) over the total number of returned correspondences (true positives and false positives). In logical terms this is supposed to measure the correctness of the method. Recall measures the ratio of correctly found correspondences (true positives) over the total number of expected correspondences (true positives and true negatives). In logical terms, this is a completeness measure. This is displayed in Figure 2. Definition 9 (Precision and recall). Given a reference alignment R, the precision of some alignment A is given by

AR C × C ′ False positives = R -A True positives = A ∩ R False negatives = A -R True negatives =(C × C ′ ) -(A ∪ R)
P (A, R)= |R ∩ A| |A| .
and recall is given by

R(A, R)= |R ∩ A| |R| .
Other measures, such as fallout, F-measure, noise, silence, etc. can be derived from precision and recall [START_REF] Do | Comparison of schema matching evaluations[END_REF].

For the examples of Figure 1, the two first columns of Table 1 display precision and recall. As expected, evaluating the reference against itself yields a maximal precision and recall. All the other alignments share the two first correspondences with R and miss the two other ones so they have a precision and recall of 50% (but A 2 which is handicapped by having more than 4 correspondences).

The semantics of alignments has not been taken into account since an alignment, like A 2 equivalent to R score worse than an incorrect and incomplete alignment, like A 4 .

Generalizing precision and recall

Even if they are well understood and widely accepted measures, precision and recall have the drawback that whatever correspondence has not been found is definitely not considered. As a result, they do not discriminate between a bad and a better alignment.

Indeed, when considering the example of Figure 1, alignment A 4 is arguably worse than the others, because its additional correspondences are measurably more different from the reference ones, but it scores the same as the other alignments.

As precision and recall are easily explained measures, it is useful to maintain the precision and recall structure when looking for new measures. This also ensures that measures derived from precision and recall (e.g., F-measure) still can IJCAI-07 be computed easily. [START_REF] Ehrig | [END_REF] proposed an abstract generalization of precision and recall that has been instantiated with syntactic measures. This allows to take into account "near misses", i.e., incorrect correspondences that are close to the target (and that, for instance, can be more easily repaired).

Instead of comparing alignments set-theoretically, [START_REF] Ehrig | [END_REF] proposes to measure the proximity of correspondence sets rather than the strict size of their overlap. Instead of taking the cardinal of the intersection of the two sets (|R ∩ A|), the natural generalizations of precision and recall measure their proximity (ω(A, R)). Definition 10 (Generalized precision and recall). Given a reference alignment R and an overlap function ω between alignments, the precision of an alignment A is given by

P ω (A, R)= ω(A, R) |A| and recall is given by R ω (A, R)= ω(A, R) |R| .
In order, for these new measures to be true generalizations, ω has to share some properties with |R ∩ A|. In particular, the measure should be positive:

∀A, B, ω(A, B) ≥ 0 (positiveness) and should not exceed the minimal size of both sets:

∀A, B, ω(A, B) ≤ min(|A|, |B|) (maximality)
This guarantees that the given values are within the unit interval [0 1]. Further, this measure should only add more flexibility to the usual precision and recall so their values cannot be worse than the initial evaluation:

∀A, B, ω(A, B) ≥|A ∩ B| (boundedness) Hence, the main constraint faced by the proximity is:

|A ∩ R|≤ω(A, R) ≤ min(|A|, |R|)
This is indeed a true generalization because, ω(A, R)= |A ∩ R| satisfies all these properties.

Semantic precision and recall and other measures

Our main goal is to design a generalization of precision and recall that is semantically grounded. In consequence, those correspondences that are consequences of the evaluated alignments have to be considered as recalled and those that are consequence of the reference alignments as correct.

For that purpose we will attempt to follow the guidelines introduced in [START_REF] Ehrig | [END_REF] as far as possible. We add some more constraints to a semantic precision and recall which consider correctness and completeness of an alignment as their limit: The classical positiveness depends on A = R, it is replaced here by its semantic counterpart. In addition, we rephrase the previous properties by applying them to precision and recall instead of ω (M is any of precision and recall and M ′ its generalized counterpart):

R |= A ⇒P sem (A, R)=1 (max-correctness) A |= R ⇒R sem (A, R)=1 (max-completeness) Cn(A)=Cn(R) iff P sem (A, R)=1 and R sem (A, R)=1 (definiteness) AR C × C ′ Cn(A) Cn(R)
M ′ (A, R) ≥ 0 (positiveness) M ′ (A, R) ≤ 1 (maximality) M ′ (A, R) ≥ M (A, R) (boundedness)

Ideal model

The natural semantic extension of these measures consists of using the set of α-consequences (or deductive closure on the prover side) instead of |A ∩ R|. This corresponds to taking as ω the size of the set identified by d instead of that identified by a in Figure 3. In this case, the true positive becomes the correspondences that are consequences of both alignments and the usual definitions of true and false positives and negatives are only extended to alignment consequences. Definition 11 (Ideal semantic precision and recall). Given a reference alignment R, the precision of some alignment A is given by

P ideal (A, R)= |Cn(R) ∩ Cn(A)| |Cn(A)| = P (Cn(A),Cn(R))
and recall is given by

R ideal (A, R)= |Cn(R) ∩ Cn(A)| |Cn(R)| = R(Cn(A),Cn(R))
This ideal way of dealing with semantic precision and recall can be applied to any language with a semantics. It is not restricted to alignments and as soon as the notion of consequence is defined from an alignment, it can be applied.

These measures are different from the extensions of [START_REF] Ehrig | [END_REF] because the divisor has changed. However, for a language with a well-defined semantics this measure is a natural extension of precision and recall. Most of the required properties are satisfied by these ideal measures:

IJCAI-07

Property 1. P ideal and R ideal satisfy:

-positiveness; -maximality; -completeness-maximality; -correctness-maximality; -definiteness; P ideal and R ideal do not necessarily satisfy boundedness.

This extension has two drawbacks: (1) both numerator and divisor could be infinite, yielding an undefined result, and (2) contrary to the objective of [START_REF] Ehrig | [END_REF], these measures do not guarantee to provide better results than precision and recall in general, i.e., we do not have

P (A, R) ≤ P ideal (A, R) nor R(A, R) ≤ R ideal (A, R
). This is because there is no direct relation between the size of an alignment (or a set of axioms) and the size of its α-consequences.

Semantic precision and recall

In order to deal with the problems raised by the infinite character of the set of α-consequences, a natural way would be to compare the deductive reductions instead of the deductive closures. Unfortunately, the deductive reduction is usually not unique. We thus propose to use the deductive closure bounded by a finite set so that the result is finite. It is based on different sets of true positives as :

TP P (A, R)={δ ∈ A; R |= δ} = A ∩ Cn(R) and TP R (A, R)={δ ∈ R; A |= δ} = Cn(A) ∩ R
These two sets correspond respectively to the sets b and c in Figure 3. They are obviously finite since they are the intersection of a set of α-consequences with a finite alignment. They are not, however, a real count of the true positive by any means.

The semantic precision and recall are based on these sets: Definition 12 (Semantic precision and recall). Given a reference alignment R, the precision of some alignment A is given by

P sem (A, R)= |A ∩ Cn(R)| |A| and recall is given by R sem (A, R)= |Cn(A) ∩ R| |R|
Both values are defined when the alignments are finite. Moreover, the considered values can be computed if there exists a complete and correct prover for the languages because there is always a finite set of assertions to check (i.e., Cn(A) ∩ R = {δ ∈ R; A |= δ}). Property 2. P sem and R sem satisfy:

-positiveness; -maximality; -boundedness; -completeness-maximality; -correctness-maximality; -definiteness;

These measures satisfy positiveness and boundedness (since it is clear that Cn(X) ⊇ X). They have the classically expected values: P sem (R, R)=1and R sem (R, R)= 1. They do not satisfy anymore, if A ∩ R = ∅, then P sem (A, R)=0which is replaced by if Cn(A) ∩ Cn(R)= ∅, then P sem (A, R)=0.

Compactness and independence

Now we can find that a particular alignment is semantically equivalent to some reference alignment. However, what makes that the reference alignment has been chosen otherwise? Are there criteria that enable to measure the quality of these alignments so that some of them are better than others? Indeed, more compact alignments seem to be preferable. Compactness can be measured as the number of correspondences. So it is possible to measure either, this absolute number or the ratio of correspondences in the reference alignments and the found alignments:

Compactness(A, R)= |R| |A|
There is no reason that this measure cannot be higher than 1 (if the found alignment is more compact than the reference alignment).

Compactness depends on the raw set of correspondences is however primitive and non semantically grounded (it is especially useful for complete and correct alignments). A more adapted measure is that of independence.

Ind(A)= |{c ∈ A; A -{c} |= c}| |A|
which checks that alignments are not redundant.

It measures the ratio of independent correspondences in an alignment independently of a reference. If we want to measure independence with regard to the reference alignment, it is possible to measure the independence of correspondences that do not appear in the reference alignment:

Ind(A, R)= |{c ∈ A -R; A -{c} |= c}| |A -R|
In the examples considered here independence measures return 1. for all alignments.

Examples

In order to compare the behavior of the proposed measure, we compare it with previously provided measures on the examples of Figure 1. Additionally to standard precision and recall we compare them with two measures introduced in [START_REF] Ehrig | [END_REF]: symmetry considers as close a correspondence in which a class is replaced by its direct sub-or super-class; effort takes as proximity the measure of the effort to produce for correcting the alignment. A third measure, oriented, is not defined in this context (because of the presence of non-equivalent correspondences).

The results are provided in Table 1. As can be expected, the results of the semantic measures match exactly the correctness and completeness of the alignment. These results are far more discriminating than the other ones as far as A 4 is concerned. The equivalent alignment A 2 which did not stand out with the other measures is now clearly identified as equivalent. An interesting aspect for A 1 which is correct but incomplete, is that the other measures fail to recognize this asymmetry. A 1 and A 3 are both correct and incomplete, they thus have the same semantic values while A 1 is arguably more complete than A 3 (in fact A 1 |= A 3 ): this is accounted better by the syntactic measures.

IJCAI-07

No redundancy was present in the selected alignments, so they all score 100% in independence. A 2 is less compact than R (and the others) as expected.

Related work

Relevant related work is that of [START_REF] Langlais | [END_REF]] in computational linguistics, [START_REF] Sun | Hierarchical text classification and evaluation[END_REF] in information retrieval and [START_REF] Ehrig | [END_REF] in artificial intelligence. All rely on a syntactic distance between entities of the ontologies (or words or documents). They have been compared in [START_REF] Ehrig | [END_REF]. However, these work tackle the problem of measuring how far is a result from the solution.

Here, the semantic foundations only consider valid solutions: the semantic definitions account for the semantically equivalent but syntactically different results.

This explains why, with regard to [START_REF] Ehrig | [END_REF], we used different but compatible properties not fully relying on a proximity measure ω. Hence, it should be possible to combine the semantic precision and recall with the proposed syntactic relaxed measures.

The results of Table 1 show how the semantic approach compares with [START_REF] Ehrig | [END_REF] on a small example. One important difference is that the syntactic measures can be easily computed because they only work on the syntax of the alignments while the semantic measures require a prover for the ontology languages (and even for the alignment semantics).

Discussion

Evaluation of matching results is often made on the basis of the well-known and well-understood precision and recall measures. However, these measures are based on the syntax of alignments and are not able to take into account the semantics of the formalism.

In this paper we provided a semantics for alignments based on the semantics of ontologies and we designed semantic precision and recall measures that take advantage of this semantics. The definition of these measures is thus independent from the semantics of ontologies. We showed that these measures are compliant with (an adapted version of) constraints put on precision and recall generalization of [START_REF] Ehrig | [END_REF] and that they behave as expected in the motivating example.

In particular, the new measures have the expected behavior:

-they are still maximal for the reference alignment; -they correspond to correctness and completeness; -they help discriminating between irrelevant alignments and not far from target ones. The examples have been given based on the alignment of simple taxonomies with very limited languages. However, all the definitions are independent from this language. We plan to implement these measures and apply them to larger sets of data (results of the OAEI1 evaluation campaigns for instance). This requires the use of a correct and complete prover for the considered ontology languages.

Figure 1 :

 1 Figure 1: Five class alignments between two ontologies (only the classes involved in correspondences are displayed).

  Definition 8 (α-Consequence of aligned ontologies). Given two ontologies o and o ′ and an alignment A between these ontologies, a correspondence δ is a α-consequence of o, o ′ and A (noted A |= δ) if and only if for all models m, m ′ ,γ of o, o ′ and A, m, m ′ |= γ δ (the set of α-consequences is noted by Cn(A)).

Figure 2 :

 2 Figure 2: Two alignments seen as sets of correspondences and their relations.

Figure 3 :

 3 Figure 3: Two alignments and their relations through the set of their consequences.

Table 1 :

 1 Precision and recall results on the alignments of Figure 1.

http://oaei.ontologymatching.org IJCAI-07

Acknowledgements

This work has been partially supported by the Knowledge Web European network of excellence (IST-2004-507482). Thanks to Mark Ehrig for pushing me on this track, to Stefano Zanobini for complaining about OAEI-2005 results and to Antoine Zimmermann for his comments.