If (T + V ) ψ E = E ψ E then χ = δn δV = E •F <0 (f E -f F ) ψ E (r )ψ F (r )ψ F (r ′ )ψ E (r ′ ) ω -(E -F ) + iε
Erwin Schrödinger Walter Kohn

V = V ext V = V eff = V ext + V Hxc

Theory

TDDFT linear response theory

Kohn-Sham response χ 0 and interacting response χ are connected 1

χ 0 = δn δV eff χ = δn δV ext V eff = V ext + V Hxc ⇒ δV eff δn = δV ext δn + δV Hxc δn ⇒ χ -1 0 = χ -1 + Σ ⇒ χ = 1 1 -χ 0 Σ χ 0 .
The problem is to effectively compute the interacting polarizability

P ik = r i |χ|r k .
1 Petersilka, Gossmann and Gross, Phys. Rev. Lett., 76 (1996) 1212

Suitable basis for non interacting response

Kohn-Sham density response reads

χ = δn δV = E •F <0 (f E -f F ) ψ E (r )ψ F (r )ψ F (r ′ )ψ E (r ′ ) ω -(E -F ) + iε
Note: formula contains products of eigenstates ψ E (r )ψ F (r )

Using method of LCAO (linear combination of atomic orbitals), we get

ψ E (r ) = a X E a f a (r ) ⇒ ψ E (r )ψ F (r ) = ab X E a X F b f a (r )f b (r )
There are

O(N) localized products f a (r )f b (r )
O(N 2 ) products of eigenstates ψ E (r )ψ F (r )

Basis of dominant products

Dominant products 2

Set of localized products f a (r )f b (r ) linearly dependent ⇒ redundant ◮ find most important linear combinations of original products

◮ use these linear combinations as a basis Compute a Gram matrix or metric

g ab,cd = f a (r )f b (r )f c (r )f d (r ) d 3 r Diagonalize metric gX λ = λX λ Form orthogonal products F λ (r ) = ab X λ ab f a (r )f b (r ) Find vertex V = X -1 = X T f a (r )f b (r ) = λ V ab λ F λ (r )
Use eigenvalue λ to define important dominant products

Dominant products: constrains

◮ Dominant products must preserve a simple form:

F λ (r ) = j F λ j (r )Y jm (Rr )
⇒ expand the dominant products about a midpoint ⇒ define the dominant products in a rotated frame R ◮ Metric g must be easily diagonalizable (small): ⇒ define metric g within a given atomic pair Implication: vertex becomes a sparse object

f a (r )f b (r ) = λ V ab λ F λ (r )
For a given product index λ only few V ab λ will be non zero.

◮ Ansatz f a (r )f b (r ) = µ V ab µ F µ (r ) leads to χ 0 µν (ω) = E <0,F >0 pqrs X E p X F q X E r X F s V pq µ V rs ν ω -(E -F ) + iε ◮ Spectral function aµν = Imχ 0 µν aµν (λ) = E <0,F >0 δ(λ -(E -F )) pqrs X F q X F s X E p X E r V pq µ V rs ν ◮ aµν (λ) via convolution aµν (λ) = F pqrs ρ qs -(-F ) * ρ pr + (λ -F )V pq µ V rs ν electronic spectral function ρ qs -(F ) = ν<0 δ(ν -F )X F q X F s ◮ Discretise λ = E -F ⇒ χ 0 µν (ω) is again convolution χ 0 µν (ω) = λ aµν (λ) • (ω -λ + iε) -1
Spectral function: discretisation ◮ FFT needs equidistant grid, but energy differences do not fit any equidistant grid Solution: "occupy" adjacent nodes ✓ Result: χ 0 exact up to discretisation ◮ Spectral range of DFT eigenenergies is large: ≈ 110 eV for benzene ◮ Only low energy relevant ⇒ need χ 0 (ω) in a small target window ◮ a(λ) outside of target window contributes to χ 0 (ω) inside

χ 0 (ω) = ∞ -∞ dλ a(λ) ω -λ
Solution: resonant and non-resonant spectral functions

χ 0 (ω) = -ωmax -∞ dλ b(λ) ω -λ + iε + +ωmax -ωmax dλ a(λ) ω -λ + iε + +∞ ωmax dλ b(λ) ω -λ + iε
Σ µν H = dr dr ′ F µ (r ) |r -r ′ | -1 F ν (r ′ ).
Dominant functions F µ (r ) are either local or bilocal.

◮ Generally F µ (r ) = j F µ j (r ′ )S jm (R µ r ′ ), r ′ = r -C µ .
◮ Radial functions F µ j (r ′ ) are given on a logarithmic grid.

E jm,j ′ m ′ (c, c ′ ) = dr dr ′ g jm (r -c)g j ′ m ′ (r ′ -c ′ ) |r -r ′ | g jm (r ) = g j (r )S jm (r ) ◮ E jm,j ′ m ′ (c, c ′ ) = g jm |p -2 |g j ′ m ′ in momentum space.
◮ Conversion to momentum space by Talman's fast Bessel transform4 .

Coulomb self energy Σ H : CPU cost

◮ For small molecules Σ µν H costs O(N 2 ) ◮ For large molecules Σ µν H costs O(N), because non overlapping F µ (r ), F ν (r )
interact via their multipoles.

✓ No 4-center integrals involved

Calculation of self energies Σ Exchange-correlation self energy Σ xc ALDA: f xc (r ) ≡ δ(t -t ′ )δ(r -r ′ ) dV xc dn (r ) ⇒ Σ µν xc = dr F µ (r )f xc (r )F ν (r )
◮ Spherical coordinates dr = r 2 drdΩ ◮ Lebedev method for solid angle dΩ, Gauss-Legendre for r 2 dr .

◮ Organize calculation in batches.

✓ Σ xc costs O(N).

Polarizability: CPU costs

◮ Non interacting response χ 0 O(N 2 N ω ) ◮ Self energies Σ H , Σ xc O(N) ◮ Solving χ -1 = χ -1 0 -Σ with direct methods O(N 3 N ω ) Fortunately P ik = d i χd k can be calculated iteratively ◮ Thanks to iterative methods O(N 2 N iter N ω ) ✓ Interacting polarizability P ik , total CPU O(N 2 N ω )
Iterative method for interacting polarizability P ik (ω)

Polarizability: method

P ik = d i 1 1 -χ 0 Σ χ 0 d k ⇒ avoid O(N 3 ) inversion.
◮ Bi-orthogonal Lanczos method for non-hermitian matrices

1. A = 1 -χ 0 Σ → tridiagonal form tnm A = |n tnm m| 2. A -1 is easy because tnm is tridiagonal A -1 = |n t -1
nm m| 3. Interacting polarizability reads P = P 0 t -1

11

◮ GMRES allows to control precision during iterations

1. Solve by GMRES (1 -χ 0 Σ)x = χ 0 di 2. Compute polarizability P ii = di |x 3.
Mean polarizability is trace of P ii .

Spectra

Dominant products basis: compression

How many dominant products F µ (r ) needed?

◮ Compare with exact result in the conventional basis. ◮ Input data from DFT calculation H, S, f a (r )

◮ χ 0 EF ,PQ is diagonal , but interaction kernel costs O(N 3 ) interaction kernel K via self
◮ Diagonalize H, check S X E a , E ◮ Construct product basis f a (r )f b (r ) = V ab µ F µ (r ) ◮ Compute response matrix χ 0 (r , r ′ , ω) = F µ (r )χ 0 µν (ω)F ν (r ′ ) ◮ . . . self-energies Σ µν = dr dr ′ F µ (r )Σ(r , r ′ )F ν (r ′ ) ◮ . . . electronic excitation spectrum P ik = d i (1 -χ 0 Σ) -1 χ 0 d k ◮ Input data from DFT calculation H, S, f a (r ) ◮ Diagonalize H, check S X E a , E ◮ Construct product basis f a (r )f b (r ) = V ab µ F µ (r ) ◮ Compute response matrix χ 0 (r , r ′ , ω) = F µ (r )χ 0 µν (ω)F ν (r ′ ) ◮ . . . self-energies Σ µν = dr dr ′ F µ (r )Σ(r , r ′ )F ν (r ′ ) ◮ . . . electronic excitation spectrum P ik = d i (1 -χ 0 Σ) -1 χ 0 d k Points to

◮

  In the basis of dominant products Σ H reads

◮

  energy Σ, vertex V and density matrix D: K = (DV )Σ(V T D) Original basis 5832 products f a (r )f b (r ) Dominant basis 1236 products F µ (r ). Spectra Dominant products basis: Coulomb versus Cartesian metric r )f b (r )f c (r )f d (r ) Coulomb 921 816.8 f a (r )f b (r )f c (r ′ )f d (r ′ )/|rr ′ | Ross Brown, IPREM unpublished (2008)

Algorithm 2 :

 2 Calculation of response matrixGenerate Fourier transform of density matrices ρ ± (τ ) forall atom quadruplets do1. Multiply ρ ± (τ ) with vertices V rho = V ρ ± (τ ) 2. Find Fourier transform of spectral function a(τ ) = V rho • V rhoDo steps 1 and 2 for ω max 2 -compute spectral function b(τ ) Nullify b(τ ) in first (target) window Prepare second convolution χ 0 (τ ) = a(τ ) * FFT (ω -λ + iε) Fourier transform of response χ 0 (ω) = FFT (χ 0 (tau)) Interpolation of second window response χ 0 2 (ω), update χ 0 (ω) Store the generated data ◮ Response matrix takes much memory (currently 11 GB for indigo) ◮ Although O(N 2 N ω ), calculation is long (3 hours for indigo) ◮ Calculation of matrix elements is independent task ◮ Available machines contain few CPU on one node (16 on M3PEC) ◮ Available machines consists of many nodes (hundreds) ◮ Response matrices to be parallelized with OpenMP and MPI ◮ Amount of work is different for atom quadruplets: load balancing ◮ Reorder quadruplets to obtain a good schedule for OpenMP ◮ Iterative method requires matrix-vector products ◮ There are MPI parallelized BLACS implementations: use them ◮ Give up the "natural" blocks in favor of block-cyclic decomposition (c,d) (a,b) Implementation: algorithm/benchmarks/parallelization Compute response matrix: OpenMP parallelization Algorithm 3: OpenMP parallelization of quadruplet loop !$OMP PARALLEL allocate private and threadprivate variables here !$OMP DO SCHEDULE(DYNAMIC,10) forall atom quadruplets do Compute block of response matrix Store the generated data !$OMP END DO deallocate private and threadprivate variables here !$OMP END PARALLEL ✓ OpenMP parallelization is done.

  mention for each step of the program

						Implementation: algorithm/benchmarks/parallelization Implementation: algorithm/benchmarks/parallelization
	Construct product basis: timing with indigo Compute response matrix: algorithm
	OMP NUM THREADS Dell laptop Grid5000 M3PEC OMP NUM THREADS Grid5000 M3PEC
	Sequential Sequential		4.58 20.7		4.30 38.8	7.99
	1	1			8.60 21.3		4.51 42.3	9.01
	2	2			2.60 10.8		2.24 21.3	4.58
	8	8			-	2.88		0.913 5.58	1.35
	16	16			-	-		-3.28	0.924
	Max speedup Max speedup		3.30 7.40		4.94 12.9	9.75
	16 16
	Allocate intermediate storage for dominant products and vertex Store the generated data 2 4 6 8 10 12 14 Speedup factor Observed Ideal 2 4 6 8 10 12 14 Observed Speedup factor Ideal
	0 0
	0 0	2 2	4 4	6 6	8 8	10 10	12 12	14 14	16 16
				Number of threads Number of threads

◮ Sketch the algorithm and implementation ◮ Type of parallelization chosen/implemented ◮ Improvements done (since June 2009) ◮ Wall time and speedup factors on Grid5000 / M3PEC / Dell Laptop Implementation: algorithm/benchmarks/parallelization Construct product basis: algorithm Algorithm 1: Generation of bilocal vertex forall atom pairs do Compute an expansion of f a (r )f b (r ) = j F j (r )Y jm (r ) (Talman) Convert the expansion to momentum space F j (r ) → F j (p) (Talman) Build Coulomb metric g using F j (p) Diagonalize the metric gX λ = λX λ Build dominant products and vertex with λ = λ/10

  Threadprivate variables for temporary arrays✓ At least factor 6 speedup. OpenMP scaling on Grid5000 improved.

								Implementation: algorithm/benchmarks/parallelization Implementation: algorithm/benchmarks/parallelization Implementation: algorithm/benchmarks/parallelization Implementation: algorithm/benchmarks/parallelization Implementation: algorithm/benchmarks/parallelization Implementation: algorithm/benchmarks/parallelization Implementation: final benchmark
	Compute response matrix: improvements Compute response matrix: timing with benzene Compute response matrix: timing with indigo Interaction matrices: improvements Coulomb interaction: timing with benzene Coulomb interaction: timing with indigo Exchange-correlation interaction: timing with indigo Sequential remnants in the code: indigo Conclusions
	◮ Sparse data storage for vertex (less memory & more speed) OMP NUM THREADS Dell laptop Grid5000 M3PEC OMP NUM THREADS Grid5000 M3PEC OMP NUM THREADS Dell laptop Grid5000 M3PEC OMP NUM THREADS Grid5000 M3PEC OMP NUM THREADS Dell laptop Grid5000 M3PEC OMP NUM THREADS Grid5000 M3PEC
	◮ Quadruplets of atoms introduced (half of second convolutions ✗) Sequential 709 725 752 Sequential 9351 10701 Sequential 42.7 38.2 78.6 Sequential 393 757 Sequential 79.29 97.22 141.2 Sequential 365 524
	1 1 1 Subprogram Grid5000, 8 threads M3PEC, 16 threads 646 734 751 1 9664 10697 42.5 37.4 210 1 365 2765 80.45 99.20 190.4 1 368 583
	V ab µ	2 2 2		2 2 2		2.88	625 4840 21.4 181 41.86 186		375 5346 18.6 1380 49.61 293 3.28	376 105 96.37
	χ 0 µν	8 8 8		8 8 8		1479	---	1479 45.6 50.9		108 1351 4.71 346 13.12 74.7 741	95.0 26.7 24.81
	Σ H	16 16 16	16 16 16		45.6	---	---		-741 -174 -40.3 174	53.0 13.5 13.34
	Max speedup Max speedup Max speedup Max speedup Max speedup Max speedup Σxc	50.9	1.03 6.32 1.98 8.04 1.92 7.23		6.79 14.4 7.93 15.9 7.56 13.0 40.3	14.2 15.6 14.27
	Speedup factor Speedup factor Speedup factor Speedup factor Speedup factor Total time 2 4 6 8 10 12 14 16 2 4 6 8 10 12 14 16 2 4 6 8 10 12 14 16 P ik Speedup factor Remnants	Observed Ideal Observed Ideal Observed Ideal Observed Ideal Observed Ideal Observed Ideal		755 2345 11.6				686 1677 32.4
	0 0 0
		0 0 0 0 0 0		2 2 2 2 2 2	4 4 4 4 4 4	6 6 6 6 6 6	8 8 8 8 8 8	10 10 10 10 10 10	12 12 12 12 12 12	14 14 14 14 14 14	16 16 16 16 16 16
					Number of threads Number of threads Number of threads Number of threads Number of threads Number of threads

◮ Result is saved in single precision (halves memory requirement) ◮ Skip unnecessary vertex-matrix multiplications in diagonal blocks ✗ ◮ Automatic arrays removed✗ ◮ Storage of intermediate vertex-matrix products shaped ◮ Single precision in vertex-matrix products ◮ OpenMP parallelization of the main loop ◮ ◮ Quadruplets of atoms introduced ◮ OpenMP parallelization of the main loop ◮ Automatic arrays removed✗ ◮ Threadprivate variables for temporary arrays ◮ Indexing array is remove ✗ ✓ Some speedup. Good scaling on Grid5000. ◮ Fast algorithm allows for a O(N 2 N ω ) scaling in true polarizability ✓ Most of improvements have been done in response ✓ Current implementation is faster than ADF in indigo molecule ✓ Most of the program is parallelized with OpenMP MPI parallelization remains to do

D. Foerster, J. Chem. Phys. 128,034108 (2008)

D. Foerster, P. Koval, J. Chem. Phys. 131,044103 (2009)

Talman J. D., Comput. Phys. Commun. 180 332 (2009)

(Dell laptop, one thread)

ADF with one thread on Dell laptop; TDDFT LR with one thread on Grid5000.

Acknowledgments ◮ James Talman, London, Canada ◮ Mark Casida, Grenoble, France ◮ Ross Brown, Pau, France $$ Work supported by ANR-project NOSSI Nouveaux Outils pour la Simulation des Solides et des Interfaces

Construct product basis: parallelization


Fadi Badra
email: badra@loria.fr

Amélie Cordier
email: amelie.cordier@liris.cnrs.fr

Jean Lieber
email: lieber@loria.fr

Opportunistic Adaptation Knowledge Discovery

Adaptation has long been considered as the Achilles' heel of case-based reasoning since it requires some domain-specific knowledge that is difficult to acquire. In this paper, two strategies are combined in order to reduce the knowledge engineering cost induced by the adaptation knowledge (AK) acquisition task: AK is learned from the case base by the means of knowledge discovery techniques, and the AK acquisition sessions are opportunistically triggered, i.e., at problem-solving time.

Introduction

Case-based reasoning (CBR [START_REF] De Mántaras | Case-Based Reasoning: An Overview[END_REF]) is a reasoning paradigm based on the reuse of previous problem-solving experiences, called cases. A CBR system often has profit of a retrieval procedure, selecting in a case base a source case similar to the target problem, and an adaptation procedure, that adapts the retrieved source case to the specificity of the target problem. The adaptation procedure depends on domain-dependent adaptation knowledge (AK, in the following). Acquiring AK can be done from experts or by using machine learning techniques. An intermediate approach is knowledge discovery (KD) that combines efficient learning algorithms with human-machine interaction.

Most of previous AK acquisition strategies are off-line: they are disconnected from the use of the CBR system. By contrast, recent work aims at integrating AK acquisition from experts to specific reasoning sessions: this opportunistic AK acquisition takes advantage of the problem-solving context. This paper presents an approach to AK discovery that is opportunistic: the KD is triggered at problem-solving time.

The paper is organized as follows. Section 2 introduces some basic notions and notations about CBR. Section 3 presents the CBR system Taaable, which constitutes the application context of the study, and motivates the need for adaptation knowledge acquisition in this application context. Section 4 presents the proposed opportunistic and interactive AK discovery method. In Sect. 5, this method is applied to acquire adaptation knowledge in the context of the Taaable system. Section 6 discusses this approach and situates it among related work. Section 7 concludes and presents some future work.

In the following, problems are assumed to be represented in a language L pb and solutions in a language L sol . A source case represents a problem-solving episode by a pair (srce, Sol(srce)), in which srce ∈ L pb is the representation of a problem statement and Sol(srce) ∈ L sol is the representation of its associated solution. CBR aims at solving a target problem tgt using a set of source cases CB called the case base. The CBR process is usually decomposed in two main steps: retrieval and adaptation. Retrieval selects a source case (srce, Sol(srce)) from the case base such that srce is judged to be similar to tgt according to a given similarity criterion. Adaptation consists in modifying Sol(srce) in order to propose a candidate solution Sol(tgt) for tgt to the user. If the user validates the candidate solution Sol(tgt), then Sol(tgt) is considered to be a solution Sol(tgt) for tgt.

Application Context: the Taaable System

The Taaable system [START_REF] Badra | Taaable: Text Mining, Ontology Engineering, and Hierarchical Classification for Textual Case-Based Cooking[END_REF] is a cooking CBR system. In the cooking domain, CBR aims at answering a query using a set of recipes. In order to answer a query, the system retrieves a recipe in the recipe set and adapts it to produce a recipe satisfying the query. The Taaable system was proposed to participate to the Computer Cooking Contest (CCC) challenge in 2008 [START_REF]ECCBR[END_REF]. In the CCC challenge, queries are given in natural language and express a set of constraints that the desired recipe should satisfy. These constraints concern the ingredients to be included or avoided, the type of ingredients (e.g., meat or fruit), the dietary practice (e.g., nut-free diet), the type of meal (e.g., soup) or the type of cuisine (e.g., chinese cuisine). An example of query is: "Cook a chinese soup with leek but no peanut oil." Recipes are given in textual form, with a shallow XML structure, and include a set of ingredients together with a textual part describing the recipe preparation. The Taaable system is accessible online (http://taaable.fr).

Representation Issues

A Cooking Ontology. The system makes use of a cooking ontology O represented in propositional logic. Each concept of O corresponds to a propositional variable taken from a finite set V of propositional variables. O is mainly composed of a set of concepts organized in a hierarchy, which corresponds, in propositional logic, to a set of logical implications a ⇒ b. For example, the axiom leek ⇒ onions of O states that leeks are onions.

Problem and Solution Representation. In Taaable, a problem pb ∈ L pb represents a query and a solution Sol(pb) of pb represents a recipe that matches this query. L pb and L sol are chosen fragments of propositional logic defined using the vocabulary V introduced in the cooking ontology O. One propositional variable is defined in L pb and L sol for each concept name of O and the only logical connective used in L pb and L sol is the conjunction ∧. For example, the representation tgt ∈ L pb of the query mentioned above is:

tgt = chinese ∧ soup ∧ leek ∧ ¬ peanut oil
The case base CB contains a set of recipes. Each recipe is indexed in the case base by a propositional formula R ∈ L sol . For example, the index R of the recipe Wonton Soup is:

R = chinese ∧ soup ∧ green onion ∧ . . . ∧ peanut oil ∧ Nothing else
Nothing else denotes a conjunction of negative literals ¬ a for all a ∈ V such that chinese ∧ soup ∧ green onion ∧ . . . ∧ peanut oil O a. This kind of "closed world assumption" states explicitly that for all propositional variable a ∈ V, either R O a (the recipe contains the ingredient represented by a) or R O ¬ a (the recipe does not contain the ingredient represented by a).

Each recipe index R represents a set of source cases: R represents the set of source cases (srce, Sol(srce)) such that Sol(srce) = R and srce is solved by R, i.e., srce is such that R O srce.

Adaptation Knowledge. In Taaable, adaptation knowledge is given by a set of reformulations (r, A r ) in which r is a binary relation between problems and A r is an adaptation function associated with r [START_REF] Melis | Reformulation in Case-Based Reasoning[END_REF]. A reformulation has the following semantics: if two problems pb 1 and pb 2 are related by r -denoted by pb 1 r pb 2then for every recipe Sol(pb 1 ) matching the query pb 1 , A r (pb 1 , Sol(pb 1 ), pb 2 ) = Sol(pb 2 ) matches the query pb 2 .

In this paper, binary relations r are given by substitutions of the form σ = α β, where α and β are literals (either positive or negative). For example, the substitution σ = leek onions generalizes leek into onions. Adaptation functions A r are given by substitutions of the form Σ = A B in which A and B are conjunctions of literals. For example, the substitution Σ = soup ∧ pepper soup ∧ ginger states that pepper can be replaced by ginger in soup recipes. A substitution Σ can be automatically generated from a substitution σ: Σ = b a if σ is of the form a b and Σ = ∅ ¬ a if σ is of the form ¬ a ∅. The main source of adaptation knowledge is the ontology O. A substitution σ = a b is automatically generated from each axiom a ⇒ b of O and correspond to a substitution by generalization. A substitution σ = a b can be applied to a query pb if pb O a. σ generates a new query σ(pb) in which the propositional variable a has been substituted by the propositional variable b. For example, the substitution σ = leek onions is generated automatically from the axiom leek ⇒ onions of O. σ can be applied to the query tgt to produce the query σ(tgt) = chinese ∧ soup ∧ onions ∧ ¬ peanut oil, in which leek has been substituted by onions. For each propositional variable a of V, an additional substitution of the form σ = ¬ a ∅ is generated. Such a substitution can be applied to a problem pb if pb O ¬ a and generates a new problem σ(pb) in which the negative literal ¬ a is removed. This has the effect to loosen the constraints imposed on a query e.g., by omitting in the query an unwanted ingredient. For example, the substitution ¬ peanut oil ∅ applied to tgt generates the query σ(tgt) = chinese ∧ soup ∧ leek, in which the condition on the ingredient peanut oil is omitted.

However, when O is the only source of adaptation knowledge, the system is only able to perform simple adaptations, in which the modifications made to Sol(srce) correspond to a sequence of substitutions that can be used to transform srce into tgt. Therefore, an additional adaptation knowledge base AKB is introduced. AKB contains a set of reformulations (σ, Σ) that capture more complex adaptation strategies.

The CBR Process in Taaable

Retrieval. The retrieval algorithm is based on a smooth classification algorithm on an index hierarchy. Such an algorithm aims at determining a set of modifications to apply to tgt in order to obtain a modified query srce that matches at least one recipe Sol(srce) of the case base. The algorithm computes a similarity path, which is a composition of substitutions SP = σ q • σ q-1 • • • • • σ 1 such that there exists at least one recipe Sol(srce) matching the modified query srce = σ q (σ q-1 (. . . σ 1 (tgt) . . .)), i.e., such that Sol(srce) O srce holds. Thus, a similarity path SP can be written:

Sol(srce) O srce σ q ← - σ q-1 ←--• • • σ 1 ← -tgt
For example, to solve the above query tgt, the system generates a similarity path SP = σ 2 • σ 1 , with:

tgt = chinese ∧ soup ∧ leek ∧ ¬ peanut oil σ 1 = ¬ peanut oil ∅, σ 2 = leek onions srce = chinese ∧ soup ∧ onions Sol(srce) = chinese ∧ soup ∧ green onion ∧ . . . ∧ peanut oil ∧ Nothing else
In this similarity path, Sol(srce) is the propositional representation of the recipe Wonton Soup. Since the ontology O contains the axiom green onion ⇒ onions, the modified query srce = σ 2 • σ 1 (tgt) verifies Sol(srce) O srce.

Adaptation. To a similarity path is associated an adaptation path AP, which is a composition of substitutions

AP = Σ 1 • Σ 2 • • • • • Σ q such that
the modified recipe Sol(tgt) = Σ 1 (Σ 2 (. . . Σ q (Sol(srce)) . . .)) solves the initial query tgt, i.e., verifies Sol(tgt) O tgt. Thus, an adaptation path AP can be written

Sol(srce) Σ q -→ Σ q-1 ---→ • • • Σ 1 -→ Sol(tgt) O tgt
The adaptation path AP is constructed from the similarity path SP by associating a substitution Σ i to each substitution σ i . To determine which substitution Σ i to associate to a given substitution σ i , the external adaptation knowledge base AKB is searched first. For a substitution σ i = α β, the system looks for a substitution Σ = A B such that A O β and B O α. For example, if σ 2 = leek onions is used in SP and AKB contains the reformulation (σ, Σ) with σ = σ 2 and Σ = green onion leek ∧ ginger, Σ will be selected to constitute the substitution Σ 2 in AP since green onion O onions and leek ∧ ginger O leek. If no substitution Σ is found in AKB for a given substitution σ i then Σ i is generated automatically from σ i .

In the previous example, AKB is considered to be empty so Σ 1 and Σ 2 are generated automatically from the substitutions σ 1 and σ 2 :

Σ 1 = ∅ ¬ peanut oil since σ 1 = ¬ peanut oil
∅ and Σ 2 = onions leek since σ 2 = leek onions. According to the axiom green onion ⇒ onions of O, the system further specializes the substitution Σ 2 into the substitution green onion leek and the user is proposed to replace green onions by leek in the recipe Wonton Soup and to suppress peanut oil. The generated adaptation path is AP = Σ 1 • Σ 2 (Fig. 1), with:

Sol(srce) = chinese ∧ soup ∧ green onion ∧ . . . ∧ peanut oil ∧ Nothing else Σ 2 = green onion leek, Σ 1 = ∅ ¬ peanut oil Sol(tgt) = chinese ∧ soup ∧ leek ∧ . . . ∧ ¬ peanut oil ∧ Nothing else tgt = chinese ∧ soup ∧ leek ∧ ¬ peanut oil
The inferred solution Sol(tgt) solves the initial query tgt: Sol(tgt

) O tgt. srce Sol(srce) pb Sol(pb) tgt Sol(tgt) σ 1 σ 2 Σ 2 Σ 1
Fig. 1. A similarity path and the associated adaptation path.

Why Learning Adaptation Knowledge in Taaable?

In the version of the Taaable system that was proposed to participate in the CCC challenge, AKB = ∅ so adaptation knowledge is inferred from the ontology O. The main advantage of this approach lies in its simplicity: no external source of adaptation knowledge is needed and the system is able to propose a solution to any target problem. However, the system's adaptation capabilities (simple substitutions) appear to be very limited and the user has no means to give some feedback on the quality of the proposed adaptation. For example, the substitution Σ 1 = ∅ ¬ peanut oil suggests to remove the ingredient peanut oil in the retrieved recipe, but as the oil is used in this recipe to saute the bok choy, the adapted recipe turns out to be practically unfeasible. A better adaptation would suggest to replace peanut oil by e.g., sesame oil, which can be modeled by the substitution Σ 1 = peanut oil sesame oil. To generate this substitution automatically, the system could for example exploit the fact that the concepts peanut oil and sesame oil are both sub-concepts of the concept oil in O. But still, some additional knowledge would be needed to express the fact that peanut oil should be replaced by sesame oil, and not by olive oil or hot chili oil, as olive oil and hot chili oil are also sub-concepts of oil in O. Besides, the system should be aware that this substitution is recommended only in Asian cuisine, which can be modeled by the more precise substitution Σ 1 = asian ∧ peanut oil asian ∧ sesame oil. Furthermore, the second substitution Σ 2 = green onions leek suggests to solely replace sliced green onions by uncooked leek. But the green onion was used in the original Wonton Soup for garniture, so the user might consider that raw leek added as garniture alters too much the taste of a soup. A better adaptation would consist in frying leek with e.g., tempeh and red bell pepper to prepare the garniture. Such an adaptation can be modeled by the substitution Σ 2 = green onions leek ∧ tempeh ∧ red bell pepper. This substitution, which reflects a cooking know-how, can hardly be generated automatically from the ontology.

These examples show that in order to improve its adaptation capabilities, the system would greatly benefit from the availability of a set of adaptation rules that would capture more complex adaptation strategies. These adaptation rules cannot be generated automatically from the ontology and need to be acquired from other knowledge sources. These examples also show that the human expert plays a major role in adaptation knowledge acquisition and that in the cooking domain, adaptation rules are often highly contextual.

Opportunistic Adaptation Knowledge Discovery

The presented AK acquisition method combines two previous approaches of AK acquisition. The first one was implemented in the CabamakA system [START_REF] D'aquin | Case Base Mining for Adaptation Knowledge Acquisition[END_REF] and learns AK from differences between cases by the means of knowledge discovery techniques (section 4.1). The second one was implemented in the IakA system [START_REF] Cordier | Opportunistic Acquisition of Adaptation Knowledge and Cases -The IakA Approach[END_REF] and acquires adaptation knowledge at problem-solving time through interactions with the user (section 4.2).

Adaptation Knowledge Discovery from the Case Base

Machine learning algorithms aim at extracting some regularities from a set of observations. Knowledge discovery techniques combine efficient machine learning algorithms with human-machine interaction. In [START_REF] D'aquin | Case Base Mining for Adaptation Knowledge Acquisition[END_REF], AK is learned from differences between cases by the means of knowledge discovery techniques. A set of pairs of sources cases is taken as input of a frequent itemset extraction algorithm, which outputs a set of itemsets. Each of these itemsets can be interpreted as an adaptation rule. This approach of AK learning was motivated by the original idea proposed by Kathleen Hanney and Mark T. Keane in [START_REF] Hanney | The Adaptation Knowledge Bottleneck: How to Unblock it By Learning From Cases[END_REF], in which the authors suggest that AK may be learned from differences between cases. The main assumption is that the differences that occur between cases in the case base are often representative of differences that will occur between future problems and the case base.

To learn adaptation rules from differences between cases, representing variations between cases is essential. In [START_REF] Badra | Representing Case Variations for Learning General and Specific Adaptation Rules[END_REF], expressive representation formalisms are proposed and it is shown that defining a partial order on the variation language can help organizing the learned rules by generality.

Opportunistic and Interactive Knowledge Acquisition

Experiential knowledge, or know-how, can often be acquired on-line, when users are using CBR tools. It is the aim of interactive and opportunistic knowledge acquisition strategies to support such an acquisition. In these strategies, the system exploits its interactions with its user to build new pieces of knowledge, to test them and, in case of success, to retain them. Moreover, the knowledge acquisition process is often opportunistic, i.e, triggered by a previous reasoning failure: reasoning failures highlight missing knowledge and thus constitute a guidance for the acquisition process. A major advantage of interactive knowledge acquisition strategies is that they ensure that the user is in a favorable context when he participates to the acquisition process. In [START_REF] Cordier | Interactive and Opportunistic Knowledge Acquisition in Case-Based Reasoning[END_REF], a review of interactive and opportunistic knowledge acquisition approaches is proposed, and two strategies are developed. This work illustrates the efficiency of interactive and opportunistic knowledge acquisition approaches to acquire specific knowledge. On the other hand, it shows that such approaches only allow the systems to acquire small pieces of knowledge at a time.

Combining the two Approaches

When properly used, knowledge discovery techniques may have the strong advantage of automating a part of the knowledge acquisition process. In these approaches, dedicated human-machine interfaces allow the expert, through predefined interactions, to provide feedback on a set of suggestions generated automatically by the system. The role of the expert is thus reduced to the validation of a pre-selected set of knowledge pieces. The acquired knowledge is directly usable by the system, without the need for an additional formalization step. Automatic approaches also benefit from efficient machine learning algorithms that can be applied, as in [START_REF] Badra | Representing Case Variations for Learning General and Specific Adaptation Rules[END_REF], to learn adaptation rules at different levels of generality. However, these approaches still produce a large number of candidate knowledge units that have to be validated by a domain expert out of any context, which constitutes an important drawback.

Acquiring adaptation knowledge offline, i.e., independently of a particular problem-solving session, appears to be problematic. Offline AK acquisition forces the system's designer to anticipate the need for adaptation knowledge in problem-solving and to acquire it in advance, which can be very tedious, if not impossible. Offline acquisition of adaptation knowledge also makes difficult to come up with fine-grained adaptation rules, since adaptation knowledge is often highly contextual. For example, in the cooking domain, an egg can sometimes be substituted by 100 grams of tofu, but this adaptation rule may be applied only to certain types of dishes, like cakes or mayonnaise, and has proved to be irrelevant in order to adapt a mousse recipe or an omelet recipe. Acquiring such a rule would require to circumscribe its domain of validity in order to avoid over-generalization.

Moreover, initial acquisition of adaptation knowledge prevents the system from learning from experience. A CBR system with fixed adaptation knowledge has no way to improve its problem-solving capabilities, except by retaining in the case base a new experience each time a problem has been solved, as it is usually done in traditional CBR systems [START_REF] De Mántaras | Case-Based Reasoning: An Overview[END_REF].

On the other hand, interactive and opportunistic knowledge acquisition approaches heavily rely on the human expert but ensure that the expert is "in context" when validating knowledge units that are to be acquired. Combining knowledge discovery techniques and interactive approaches, as it is proposed here, could overcome one of the limitations of KD by dramatically reducing the number of candidate adaptation rules presented to the expert. By triggering the process in an opportunistic manner, the expert is able to parametrize the KD in order to focus on specific knowledge to acquire in context. The resulting AK discovery process:

is performed on-line, i.e., in the context of a problem-solving session, -is interactive as adaptation knowledge is learned by the system through interactions with its user who acts as an expert, -is opportunistic as it is triggered by reasoning failure, and, consequently, often helps repairing a failed adaptation, -makes use of knowledge discovery techniques to provide assistance to the user in the formulation of new knowledge: the user is presented with a set of suggestions that are generated automatically from the case base.

Applying Opportunistic AK Discovery to Taaable

In this section, an opportunistic AK discovery process is applied to the context of the Taaable system.

AK Discovery

In Taaable, the AK discovery process consists in learning a set of substitutions from the case base by comparing two sets of recipes.

The Training Set. The training set TS is formed by selecting from the case base a set of pairs of recipes (R k , R ℓ ) ∈ CB × CB and by representing for each selected pair of recipes (R k , R ℓ ) the variation ∆ kℓ from R k to R ℓ . The choice of the training set TS results from a set of interactions with the user during which he/she is asked to formulate the cause of the adaptation failure and to pick up a repair strategy.

Representing Variations. The variation ∆ kℓ from a recipe R k to a recipe R ℓ is represented in a language L ∆ by a set of properties. Three properties a -, a + and a = are defined in L ∆ for each propositional variable a of V, and ∆ kℓ ∈ L ∆ contains:

-the property a -if R k O a and R ℓ O a, -the property a + if R k O a and R ℓ O a, -the property a = if R k O a and R ℓ O a.
For example, if: The inclusion relation ⊆ constitutes a partial order on L ∆ that can be used to organize variations by generality: a variation ∆ is more general than a variation

R k = chinese ∧ soup ∧ . . . ∧ peanut oil ∧ Nothing else R ℓ = chinese ∧ soup ∧ . . . ∧
∆ ′ if ∆ ⊆ ∆ ′ .
Mining. The learning process consists in highlighting some variations ∆ ∈ L ∆ that are more general than a "large" number of elements ∆ kℓ of TS. More formally, let

support(∆) = card {∆ kℓ ∈ TS | ∆ ⊆ ∆ kℓ }
card TS Learning adaptation rules aims at finding the ∆ ∈ L ∆ such that support(∆) ≥ σ s , where σ s ∈ [0; 1] is a learning parameter called the support threshold. It can be noticed that if ∆ 1 ⊆ ∆ 2 then support(∆ 1 ) ≥ support(∆ 2 ). The support threshold also has an influence on the number of generated variations. The number of generated variations increases when σ s decreases. Thus, specifying a high threshold restricts the generation of variations to the most general ones, which can limit the number of generated variations and save computation time but has the effect to discard the most specific ones from the result set.

Each learned variation ∆ = {p 1 , p 2 , . . . , p n } ∈ L ∆ is interpreted as a substitution of the form A B such that:

-A O a and B O a if a -∈ ∆, -A O a and B O a if a + ∈ ∆, -A O a and B O a if a = ∈ ∆.
For example, the variation ∆ = {oil = , peanut oil -, olive oil + } is interpreted as the substitution Σ = peanut oil olive oil. The conjunct oil is not present neither in A nor in B since it is useless: peanut oil O oil and olive oil O oil.

Filtering. For a retrieved recipe Sol(srce), the result set can be filtered in order to retain only the substitutions Σ = A B that can be applied to modify Sol(srce), i.e., such that Sol(srce) O A.

Validation. Knowledge discovery aims at building a model of reality from a set of observations. But as a model of a part of reality is only valid with respect to a particular observer, any learned substitution has to be validated by a human expert in order to acquire the status of piece of knowledge.

Opportunistic Adaptation Knowledge Discovery

The AK discovery process turns the case base into an additional source of adaptation knowledge. This new source of knowledge is used during a problemsolving session to provide the CBR system with adaptation knowledge "on demand". A set of variations ∆ is learned from the case base by comparing two sets of recipes and each learned variation ∆ is interpreted as a substitution Σ that can be used to repair the adaptation path AP. Each learned substitution Σ is presented to the user for validation together with the corrected solution Sol(tgt) resulting from its application. When the user validates the corrected solution, a new reformulation (σ, Σ) is added to the adaptation knowledge base AKB so that the learned substitution Σ can be later reused to adapt new recipes. The AK discovery process is triggered either during the adaptation phase, to come up with suggestions of gradual solution refinements (see section 5.4 for an example), or during the solution test phase to repair a failed adaptation in response to the user's feedback (see section 5.5 for an example).

Implementation

To test the proposed adaptation knowledge acquisition method, a prototype was implemented that integrates the Taaable system [START_REF] Badra | Taaable: Text Mining, Ontology Engineering, and Hierarchical Classification for Textual Case-Based Cooking[END_REF] and the CabamakA system [START_REF] D'aquin | Case Base Mining for Adaptation Knowledge Acquisition[END_REF]. The case base contains 862 recipes taken from the CCC 2008 recipe set. The Taaable system is used to perform retrieval and adaptation. The CabamakA system is used to learn a set of substitutions Σ from the case base from the comparison of two sets of recipes. As in [START_REF] D'aquin | Case Base Mining for Adaptation Knowledge Acquisition[END_REF], the mining step is performed thanks to a frequent closed itemset extraction algorithm.

A First Example: Cooking a Chocolate Cake

An example is presented to illustrate how the case base is used as an additional source of adaptation knowledge. The AK discovery process is parametrized automatically and is used to provide assistance to the user by suggesting some gradual refinements for the proposed solution.

1. Representing the Target Problem. In this example, the user wants to cook a chocolate cake with baking chocolate and oranges. The target problem is:

tgt = cake ∧ baking chocolate ∧ orange
In the Taaable interface, the field "Ingredients I Want" is filled in with the tokens baking chocolate and orange and the field "Types I Want" is filled in with the token cake. 2. Retrieval. The retrieval procedure generates the similarity path SP = σ 1 in which the substitution σ 1 = baking chocolate chocolate is generated automatically from the ontology O from the axiom baking chocolate ⇒ chocolate. SP is applied to tgt in order to produce the modified query srce = cake∧chocolate∧orange. The system retrieves the recipe Ultralight Chocolate Cake, whose representation Sol(srce) is:

Sol(srce) = cake ∧ cocoa ∧ orange ∧ . . . ∧ Nothing else
Since the ontology O contains the axiom cocoa ⇒ chocolate, Sol(srce) solves the query srce: Sol(srce) is such that Sol(srce) O srce. 3. Adaptation. AKB is assumed to be empty, so to construct the adaptation path AP, the substitution chocolate baking chocolate is generated automatically from σ 1 . This substitution is further specialized into the substitution Σ 1 = cocoa baking chocolate, according to the axiom cocoa ⇒ chocolate of O. A first solution Sol(tgt) is computed by applying to Sol(srce) the adaptation path AP = Σ 1 . The user suggests that an ingredient is missing in Sol(tgt) but could not identify a repair strategy. An AK discovery is triggered in order to suggest gradual refinements of Sol(tgt).

Choosing the Training Set.

The training set TS is chosen from Σ 1 : AK is learned by comparing the recipes containing cocoa with the recipes containing baking chocolate. TS is composed of the set of variations ∆ kℓ ∈ L ∆ between pairs of recipes (R k , R ℓ ) ∈ CB × CB such that {cocoa -, baking chocolate + } ⊆ ∆ kℓ . 5. Mining and Filtering. A value is given to the support threshold σ s and the mining step outputs a set of variations. A filter retains only the variations that correspond to substitutions applicable to modify Sol(srce). 6. Solution Test and Validation. The user selects the learned variation ∆ = {cocoa -, baking chocolate + , oil -} from the result set. ∆ is interpreted as the substitution Σ = cocoa ∧ oil baking chocolate, which suggests to replace cocoa by baking chocolate in the retrieved recipe and to remove oil. The user explains this rule by the fact that baking chocolate contains more fat than cocoa, and therefore substituting cocoa by baking chocolate implies to reduce the quantity of fat in the recipe. Further solution refinements are proposed to the user. The set of learned variations is filtered in order to retain only the substitutions ∆ ′ that are more specific than ∆, i.e., such that ∆ ⊆ ∆ ′ . Among the retained variations is the variation ∆ ′ = {cocoa -, baking chocolate + , oil -, vanilla -}, which is interpreted as the substitution Σ ′ = cocoa∧oil∧vanilla baking chocolate. Σ ′ suggests to also remove vanilla in the recipe Ultralight Chocolate Cake. The user is satisfied with the refined solution Sol(tgt) resulting from the application of the adaptation path AP = Σ ′ to Sol(srce), so the reformulation

(baking chocolate chocolate, cocoa ∧ oil ∧ vanilla baking chocolate)
is added to the adaptation knowledge base AKB.

A Second Example: Cooking a Chinese Soup

A second example is presented in which the AK discovery process is triggered in response to the user feedback in order to repair the adaptation presented in Sect. 3. In this example, the user is encouraged to formulate the cause of the adaptation failure. A repair strategy is chosen that is used to parametrize the AK discovery process.

1. Representing the Target Problem. In this example, the target problem tgt is:

tgt = chinese ∧ soup ∧ leek ∧ ¬ peanut oil
In the Taaable interface, the field "Ingredients I Want" is filled in with the token leek, the field "Ingredients I Don't Want" is filled in with the token peanut oil and the field "Types I Want" is filled in with the tokens chinese and soup. 2. Retrieval. As in Sect. 3, two substitutions σ 1 = ¬ peanut oil ∅ and σ 2 = leek onions are generated automatically from the ontology O. The similarity path SP = σ 2 • σ 1 is applied to tgt in order to produce the modified query srce = chinese ∧ soup ∧ onions. The system retrieves the recipe Wonton Soup, whose representation Sol(srce) solves the query srce: Sol(srce) is such that Sol(srce) O srce. 3. Adaptation. Initially, AKB = ∅, so to construct the adaptation path AP, two substitutions Σ 1 = ∅ ¬ peanut oil and Σ 2 = green onion leek are automatically generated from σ 1 and σ 2 . 4. Solution Test and Validation. The solution Sol(tgt) is presented to the user for validation, together with the adaptation path AP = Σ 1 • Σ 2 that was used to generate it. 5. The User is Unsatisfied! The user complains that the adapted recipe is practically unfeasible because the proposed solution Sol(tgt) does not contain oil anymore, and oil is needed to saute the bok choy. 6. What has Caused the Adaptation Failure? The cause of the adaptation failure is identified through interactions with the user. The user validates the intermediate solution Sol(pb) that results from the application of the substitution Σ 2 = green onion leek to Sol(srce). But the user invalidates the solution Sol(tgt) that results from the application of Σ 1 = ∅ ¬ peanut oil to Sol(pb). The substitution Σ 1 is identified as responsible for the adaptation failure since its application results in the removal of oil in the recipe. 7. Choosing a Repair Strategy. A repair strategy is chosen according to the user's feedback. The user expresses the need for oil in the adapted recipe, so the repair strategy consists in replacing peanut oil by another oil. An AK discovery process is triggered to decide which oil to replace peanut oil with. 8. Choosing the Training Set. A set of recipes that contain peanut oil is compared with a set of recipes containing other types of oil. The training set TS is composed of the set of variations ∆ kℓ ∈ L ∆ between pairs of recipes (R k , R ℓ ) ∈ CB × CB such that {oil = , peanut oil -} ⊆ ∆ kℓ . 9. Mining and Filtering. A value is given to the support threshold σ s and the mining step outputs a set of variations. A filter retains only the variations that correspond to substitutions applicable to modify Sol(pb). 10. Solution Test and Validation. The user selects the learned variation ∆ = {oil = , peanut oil -, olive oil + } from the result set. ∆ is interpreted as the substitution Σ = peanut oil olive oil, which suggests to replace peanut oil by olive oil in the retrieved recipe. The adaptation path AP = Σ • Σ 2 is computed and the repaired solution Sol(tgt) is presented to the user for validation. The user is satisfied with the corrected solution Sol(tgt), so the reformulation (∅ ¬ peanut oil, peanut oil olive oil) is added to the adaptation knowledge base AKB.

Discussion and Related Work

AK acquisition is a difficult task that is recognized to be a major bottleneck for CBR system designers due to the high knowledge-engineering costs it generates. To overcome these knowledge-engineering costs, a few approaches (e.g., [START_REF] D'aquin | Case Base Mining for Adaptation Knowledge Acquisition[END_REF][START_REF] Craw | Learning Adaptation Knowledge to Improve Case-Based Reasoning[END_REF][START_REF] Hanney | The Adaptation Knowledge Bottleneck: How to Unblock it By Learning From Cases[END_REF]) have applied machine learning techniques to learn AK offline from differences between cases of the case base. In [START_REF] Hanney | The Adaptation Knowledge Bottleneck: How to Unblock it By Learning From Cases[END_REF], a set of pairs of source cases is selected from the case base and each selected pair of source cases is considered as a specific adaptation rule. The featural differences between problems constitute the antecedent part of the rule and the featural differences between solutions constitute the consequent part. Michalski's closing interval rule algorithm is then applied to generalize adaptation rule antecedents. In [START_REF] Craw | Learning Adaptation Knowledge to Improve Case-Based Reasoning[END_REF], adaptation knowledge takes the form of a set of adaptation cases. Each adaptation case associates an adaptation action to a representation of the differences between the two source problems. Machine learning algorithms like C4.5 or RISE are applied to learn generalized adaptation knowledge from these adaptation cases in order to improve the system's case-based adaptation procedure.

When applying machine learning techniques to learn adaptation knowledge from differences between cases, one main challenge concerns the choice of the training set: which cases are worth comparing? Arguing that (1) the size of the training set should be reduced to minimize the cost of the adaptation rule generation process and that (2) the source cases that are worth comparing should be the ones that are more similar, only the pairs of source cases that were judged to be similar according to a given similarity measure are selected in [START_REF] Craw | Learning Adaptation Knowledge to Improve Case-Based Reasoning[END_REF] and [START_REF] Hanney | The Adaptation Knowledge Bottleneck: How to Unblock it By Learning From Cases[END_REF]. However, committing to a particular similarity measure might be somewhat arbitrary. Therefore, in [START_REF] D'aquin | Case Base Mining for Adaptation Knowledge Acquisition[END_REF], the authors decided to include in the training set all the pairs of distinct source cases of the case base. This paper introduces a third approach: the choice of the training set is determined interactively and according to the problem-solving context, taking advantage of the fact that the AK discovery process is triggered on-line. This approach appears to be very promising since the learning algorithm can be parametrized in order to learn only the knowledge that is needed to solve the target problem.

The examples presented above also show that knowledge discovery techniques allow to come up with more complex adaptation strategies than the simple one-to-one ingredient substitutions generated from the ontology O. In particular, these techniques can help identifying interactions between the different ingredients that appear in the recipes (like e.g., that cocoa contains less fat than baking chocolate, so oil should be removed) as well as co-occurrences of ingredients (like say, that cinnamon is well-suited with apples). Besides, adaptation knowledge is learned at different levels of generality, so the user can be guided into gradual solution refinements.

Several CBR systems make use of interactive and/or opportunistic knowledge acquisition approaches to improve their learning capabilities. For example, in Creek, an approach that combines case-based and model-based methods, general knowledge is acquired through interactions with the user [START_REF] Aamodt | Knowledge-Intensive Case-Based Reasoning in Creek[END_REF]. This knowledge acquisition process is provided in addition to the traditional case acquisition and allows the system to acquire knowledge that cannot be captured through cases only. In the Dial system, adaptation knowledge is acquired in the form of adaptation cases: when a case has to be adapted, the adaptation process is memorized in the form of a case and can be reused to adapt another case. Hence, adaptation knowledge is acquired through a CBR process inside the main CBR cycle. It must be remarked that adaptation cases can either be built automatically by adaptation of previous adaptation cases or manually by a user who interactively builds the adaptation case in response to a problem by selecting the appropriates operations to perform [START_REF] Leake | Acquiring Case Adaptation Knowledge: A Hybrid Approach[END_REF]. Hence, knowledge acquisition in Dial appears to be both interactive and opportunistic. Chef is obviously related to the work described here [START_REF] Hammond | CHEF: A model of case-based planning[END_REF]. Chef is a case-based planner in the cooking domain, its task is to build recipes on the basis of a user's request. The input of the system is a set of goals (tastes, textures, ingredients, types of dishes) and the output is a plan for a single recipe that satisfies all the goals. To solve this task, Chef is able to build new plans from old ones stored in memory. The system is provided with the ability to choose plans on the basis of the problems that they solve as well as the goals they satisfy, but it is also able to predict problems and to modify plans to avoid failures (plans are indexed in memory by the problems they avoid). Hence, Chef learns by providing causal explanations of failures thus marking elements as "predictive" of failures. In other words, the acquired knowledge allows the system to avoid identical failures to occur again. In our approach, we propose to go one step further by using failure to acquire knowledge that can be more widely used.

Conclusion and Future Work

In this paper, a novel approach for adaptation knowledge acquisition is presented in which the knowledge learned at problem-solving time by knowledge discovery techniques is directly reused for problem-solving. An application is proposed in the context of the cooking CBR system Taaable and the feasibility of the approach is demonstrated on some use cases. Future work will include developing a graphical user interface and doing more extensive testing. Opportunistic and interactive knowledge discovery in Taaable implies that the user plays the role of the domain expert, which raises several issues. For example, how to be sure that the knowledge expressed by a particular user is valuable? How to ensure that the adaptation knowledge base will remain consistent with time? Besides, Taaable is meant to be multi-user, so if the system's knowledge evolves with experience, some synchronization problems might occur. Therefore, the envisioned multi-user, ever-learning Taaable system needs to be thought of as a collaborative tool in which knowledge acquired by some users can be revised by others.


Matthieu Glachant
email: glachant@ensmp.fr

Keywords: Road pricing, Distributional effects, Income effects, Equity

The starting point of this paper is to consider that there is no general answer to the question of the equity of urban road pricing. We therefore simulate and compare the distributional effects on commuters of nine toll scenarios for Paris, assuming that utility is nonlinear in income. We show that the distributional pattern across income groups depends crucially on the level of traffic reduction induced by tolling. Stringent tolls are more favourable to low-income motorists. Equity effects also vary with toll design. Compared to a reference scenario which uniformly charges all motorists driving within Paris, an inbound cordon toll is detrimental to low-incomes. Conversely, granting a rebate to low CO2 emission cars slightly improves their situation while an exemption for Paris residents is neutral. Surprisingly, it matters little for social equity whether toll revenues are allocated to all commuters or solely to public transport users.

Introduction

The success of the London congestion charging scheme, set up in February 2003, has modified the views of many European policymakers on road pricing. Most of them now consider that it is a credible instrument to tackle urban congestion, although the legal framework in some EU countries still prohibits its implementation (e.g., France). However, many stakeholders criticise urban tolls on equity grounds, arguing that it disproportionately burdens low-income travellers.

This argument has some theoretical foundations as high-income travellers have generally higher values of travel time than low-income ones. Accordingly, they tend to value more the reduced travel times induced by the implementation of tolls. Furthermore, they value less the financial loss of the toll as the marginal utility of income is decreasing.

Arguments leading to opposite conclusions are also available. For instance, motorists usually have higher incomes than the other travellers. 1 Most importantly, the overall distributional impacts of road pricing ultimately depend on the allocation of the toll revenues.

To sum up, the answer to the question of urban tolls' equity is indeterminate in general. It depends on the scheme considered, on the use of the toll revenues, and on the urban context in which tolling is introduced. Accordingly, the relevant approach consists in comparing the distributional effects of different toll scenarios. This paper analyzes nine scenarios for Paris using disaggregated data from the Global Transport Survey carried out in 2001-2002(Enquête Globale Transport Ile-de-France 2001-2002). The reference scenario is a toll requiring vehicles driven within Paris to pay a uniform fee per trip which induces a 20% traffic reduction. Then, we consider several variants: different levels of traffic reduction (10%, 30% and 50%); a cordon toll which only applies to vehicles entering Paris, a toll in which residents are partially exempted, a toll with discounts for low CO2 emitting cars. We also study two scenarios of revenue recycling.

We restrict the analysis to commuters and to the direct effects of road pricing: the monetary cost of the toll and the changes in travel time. We derive three indicators reflecting the distributional properties of the scenarios. First, we measure the mean commuters' compensating variation due to the introduction of the toll. In this way, we try to work out the degree of political acceptability of the different scenarios. Second, we characterize the relationship between individual compensating variations, expressed in euros per trip, and income. The aim is to identify the magnitude of the potential redistribution between income groups. Third, we study the relationship between the individual compensating variations, expressed as a percentage of income, and income. The last indicator is usually referred to as regressiveness in public economics.

The empirical literature dealing with the distributional effects of road pricing is developing very quickly. [START_REF] Eliasson | Equity Effects of Congestion Pricing[END_REF] examine the equity effects of a cordon toll in Stockholm. 2 Teubel (2000) does the same in Dresden, while [START_REF] Santos | Distributional Impacts of Road Pricing: The Truth behind the Myth[END_REF] assess the potential distributional impacts of a cordon toll in three English towns (Cambridge, Northampton and Bedford). [START_REF] Franklin | The Equity Effects of Roadway Tolls: An Application of Hicksian Welfare Measures with Income Effects[END_REF] analyses the equity effects of a toll bridge in the State of Washington, USA. [START_REF] Raux | The acceptability of urban road pricing[END_REF] examine the distributional effects of an urban toll motorway in Lyon. These five studies analyse a particular form of urban pricing: a bridge toll in [START_REF] Franklin | The Equity Effects of Roadway Tolls: An Application of Hicksian Welfare Measures with Income Effects[END_REF], a link toll on a ring road in [START_REF] Raux | The acceptability of urban road pricing[END_REF], and a simple inbound cordon toll in the other studies. The results that they give are only valid for the studied scenarios.

In contrast with these papers, we compare nine scenarios. We believe that a comparative approach is better-suited to derive policy implications. By considering different variants, we are able to investigate the drivers of the distributional impacts. In this regards, our paper is closer to [START_REF] Safirova | Welfare and Distributional Effects of Road Pricing Schemes for Metropolitan Washington DC[END_REF], or to [START_REF] Maruyama | Efficiency and equity comparison of cordon-and areabased road pricing schemes using a trip-chain equilibrium model[END_REF] who examine different forms of road pricing in Washington, DC. and in Utsunomiya, Japan, respectively. However, their results are not easily transferable to European cities as the geography of urban areas, the spatial distribution of income and the relative importance of public transport (PT hereafter) are completely different. In particular, Safirova et al.'s results depend crucially on the pre-existence of restricted high-occupancy vehicles (HOV) lanes on major freeways in the DC area. Such HOV lanes hardly ever exist in European cities.

From a methodological point of view, we use a random utility model that is nonlinear in income. This leads us to calculate exact compensating variations for each commuter using the formula recently derived by [START_REF] Dagsvik | Compensating Variation and Hicksian Choice Probabilities in Random Utility Models that are Nonlinear in Income[END_REF]. This is of most interest since, as argued by Jara-Díaz and Videla (1989), traditional mode choice models which assume a constant marginal utility of income tend to under-estimate regressiveness. To the best of our knowledge, [START_REF] Franklin | The Equity Effects of Roadway Tolls: An Application of Hicksian Welfare Measures with Income Effects[END_REF] is the only other work which implements this new method to the equity of urban tolls.

The paper is organized as follows. The first section presents the mode choice model which will provide the basis for the econometric estimations. The second section deals with econometric aspects and the third section presents the results. The last section concludes.

An income-sensitive mode choice model

In this section, we develop a random-utility model describing the mode choice of individuals making trips which is not linear in income and describe how we calculate individual compensating variations induced by tolling.

Consider a population of individuals who are forced to make a trip, for example to go to work or to University. This assumption will lead us to make our estimations on a sample of individuals doing home-to-work trips. An individual faces two alternatives j = A, B. A describes the option "take the car" and B the option "use PT". The generalised costs associated with the two alternatives are

ε ε Γ = Ω + Γ = Ω + A A A B B B
(1)

where ε A and ε B are random variables whose realization is only known to the individual. In order to address income effects, we consider a model which is not linear in income. More specifically, assuming budget exhaustion, we write

α α α β γ φ β γ φ ϕ Ω = + - + + Ω = + - + + A A A B B B T y C T y C A B X Y X Y ϕ (2)
with:

α: a superscript equal to 1 if a toll is introduced, 0 otherwise.

T j : the duration of the trip with alternative j.

C j : the monetary cost of alternative j.

y: the individual's income.

X: a vector of characteristics of the individual.

Y j : a vector of characteristics of the alternative j.

, , , β γ φ ϕ : the parameters or the vectors of parameters to be estimated.

Note that the duration of the trip by car, T A , and the cost C A depend on α as the toll reduces congestion and increases the monetary cost of this alternative. But we assume that the duration of the trip by PT, T B , is not affected by the introduction of the toll. This assumption is B clearly restrictive for trips made by bus that also benefit from the congestion reduction. These trips represent solely 9% of the trips made by PT in our sample.

Interestingly, the marginal utility of income is not constant under specification (2) as it writes

j j C y y - - = ∂ Ω ∂ - 2 γ ,
Assuming that γ is negative -meaning that the generalised cost of alternative j increases with the monetary cost of j -the marginal utility of income decreases with income. Similarly, the unit value of time is

2 j j j j j j T y C C ∂ ∂ β λ ∂ ∂ γ Ω ≡ =- Ω - . (3)
If one realistically assumes that γ < 0 and β > 0, the value of time increases with income.

Before proceeding, let us discuss further assumptions underlying (2). To begin with, (2) implies that a motorist facing a toll has only two options: to continue to use a car or to switch to PT. Hence, we forego at least three other possibilities: (i) to refrain from doing the trip, (ii) to modify the departure time and (iii) to change the route to avoid tolling. To dismiss the first option does not raise particular difficulties because we estimate the mode choice of individuals making home-to-work trips. The second alternative is not very relevant in our case for two reasons. First, we concentrate on home-to-work trips which are not very flexible. Second, this option would be interesting if modifying the departure time permitted to avoid or to reduce the toll payment. But we will not study any scenarios involving a time-varying toll. To neglect the third option is probably more problematic. Studying this option would require a sophisticated traffic model. However, it is only relevant for the trips through Paris; those trips represent a mere 15% of the trips in our sample.

Turning next to the calculations of individual surpluses, let U denote the individual's utility. As the individual opts for the least-costly alternative, it is given by:

( ) { } ( ) max , α α ≡ -Γ -Γ A B U (4)
Consider now a change from the initial state without toll ( 0 α = ) to the new state with a toll ( 1 α = ). The individual's compensating variation is the amount of money cv such that ( 0)

U α = = { } 1 1 max , A A A B B T y cv C T y cv C β γ φ ϕ ε β γ φ ϕ ε ⎡ ⎤ B ⎡ ⎤ - + -- + + + - + -- + + + ⎣ ⎦ ⎣ ⎦ A B X Y X Y (5)
This expression simply says that cv is the amount of money that, when subtracted from income in the new state, equates maximum utility in the new state with maximum utility in the initial state. In this context, compensating variations also vary as a function of income, as one would expect.

The problem is that U is observed by the individual but not by the researcher who can only calculate E [cv]. Let us now adopt the researcher's perspective. We consider a traditional logit model in which the probability that individual prefers the car is

( ) ( ) P Pr Pr α α ε ε ε ε = Ω + <Ω + = -<Ω -Ω A A A B B A B B A
where ε ε -A B follows a logistic distribution while the functional form of P A is given by P ( , )

α α α -Ω -Ω -Ω Ω Ω = + A A B A A B e e e ( 6
)
If j α Ω was linear in income, one would simply use the well-known log sum formula to calculate E [cv]. However, the presence of income effects makes the calculation much more complex. Fortunately, [START_REF] Dagsvik | Compensating Variation and Hicksian Choice Probabilities in Random Utility Models that are Nonlinear in Income[END_REF] have recently provided an exact formula for the expected compensating variation.3 It writes:

[ ] ( ) ( ) j j j j j j E cv y P z dP z μ μ μ μ ⎧ ⎫ ⎪ = - - ⋅ ⎨ ⎪ ⎪ ⎩ ⎭ ∑ ∫ ⎪ ⎬ A ( 7
)
where P j (z) is the choice probability:

0 ( ( ), ( )) if ( ) ( ( ), ( )) if A A B j B A B P y g z j P z P g z y j B ⎧ Ω = ⎪ = ⎨ Ω = ⎪ ⎩ and μ j is implicitly defined by 0 0 0 1 1 1 ( , , ) ( , , ) j j j j j j j y T C T C μ Ω =Ω { } min , A B μ μ μ = 0 1 ( ) max[ ( ), ( )] j j j g z y = Ω Ω z

Simulation model and data description

Having described how we model mode choice and calculate compensating variations (cv), we now describe how we simulate the different toll scenarios.

Simulation procedures

We proceed in five stages.

• We estimate econometrically the parameters , , , and β γ φ ϕ of equation (2) using data from the 2001-2002 Global Transport Survey.

• We estimate a speed-flow function that links the traffic level to speed in order to calculate the car travel time 1 A T once a toll is introduced.

• Using an iterative process, we use the estimated parameters ˆ, , , and β γ φ ϕ and the estimated travel time to predict the mode choice of motorists with and without the toll.

1 ˆA T

• We use the formula (7) to calculate the individual compensating variations.

Data description

We use disaggregated data from the 2001-2002Global Transport Survey (Enquête Globale Transport Ile-de-France 2001-2002). This survey has been carried out regularly for 25 years. It allows us to follow and analyse trip patterns in Ile-de-France. Ile-de-France is a vast area of 12,072 sq km and 10.9 millions inhabitants. The city of Paris is only a small part of that area with a surface of 105 sq km and 2.1 millions inhabitants.

The sample surveyed is representative of the Ile-de-France population with respect to social and geographical characteristics. 10,500 households were surveyed between October 2001 and April 2002. Each member of the household, older than 6, is interviewed about all the trips she/he made the day before the survey. For each trip, a broad variety of data is available, for example: time of departure and arrival, trip purpose, origin, destination and mode(s) used.

General household characteristics are also described (e.g., size, location, income) as well as characteristics of each member (e.g., age, sex, profession).

As stated above, our estimations are limited to home-to-work trips. Those trips represent about one third of car and PT trips in Paris intra muros. Moreover, we only consider travellers possessing a driving licence and belonging to a household owning at least one car.

We also focus only on trips made by private car or PT. Non-motorised two-wheel or pedestrian trips are therefore excluded considering that urban tolls pertain to an alternative "car versus PT". We also exclude taxi and motorised two-wheel trips as well as trips made by car as a passenger. Concerning home-to-work trips, the latter options are very rarely chosen (3.6% on the trips considered). In the end, our estimations are carried out using a sample of 1032 trips.

Finally, we use control variables that are commonly used (see for example [START_REF] Teubel | The welfare effects and distributional impacts of road user charges on commuters: an empirical analysis of Dresden[END_REF]:

FEMALE = 1 if

Estimation of mode choice and unit values of time

Table 2 presents the results of the mode choice estimation. Coefficients of the model are clearly significant and present signs that are not absurd. For instance, the number of cars in the household and the availability of a car park for free clearly increase the propensity to travel by car.

Recall that our specification allows us to define thoroughly the relationship between income and unit value of time. Additional details are given in the appendix. The appendix also includes a table giving average travel time reductions for all the scenarios.

Scenarios considered

Table 4 describes the 9 scenarios. As a benchmark, we use the so-called Zone scenario. It is a toll which charges uniformly for internal trips within Paris, trips in Paris with an origin or a destination in the suburbs and through trips with both an origin and a destination outside Paris5 .

It is calibrated to lead to a 20% reduction of the whole traffic within the zone (inbound, outbound or internal). Furthermore, we assume no distribution of toll revenues to commuters.

Then, we consider different variations of this reference scenario:

• Other levels of traffic reduction (10%, 30%, 50%).

• The introduction of exemptions: the Inbound Cordon scenario in which the toll only applies to vehicles entering Paris; the Residents scenario where people living within the charging zone (i.e., Paris residents) only pay 10% of the toll level as in London; the Green scenario where drivers of cars emitting less than 180 gCO2 per km get a 50% rebate.

We also consider two variants of the Zone scenario where toll revenues are redistributed to commuters. In a first scenario (PT funding), revenues are used to cut PT fares. In a second scenario (Uniform Redistribution), each commuter receives a uniform lump sum payment.6

In Table 4, we see that the toll unsurprisingly increases with the level of traffic reduction.

It also rises when some motorists are partially or totally exempted (Inbound Cordon, Residents

or Green) while it is reduced when the toll revenues are used to cut PT fares as shifting to PT becomes less costly. Interestingly, the toll fee increases slightly when the toll revenues are evenly redistributed to all commuters (Uniform Redistribution). This is a simple income effect: redistribution makes individuals (slightly) richer. Hence, they value less an increase of the car travel costs, thereby requiring a higher toll to achieve the same level of traffic reduction.

Results and discussion

We present our results in two steps. First, we study the average individual welfare changes induced by the different scenarios. In doing this, we seek to compare the overall degree of political acceptability of different tolls. Then, we assess the distributional effects across different income groups for each scenario.

Average compensating variations

Table 5 describes the average compensating variations induced by the different scenarios as well as the percentage of winners in each scenario. We focus on the scenarios involving a 20% traffic reduction as the impact on average cv of different reduction rates is easily predictable.

The most important result is that, whatever the scenario, the average compensating variation of motorists is significantly negative. In other words, motorists taken as a whole tend to lose when a toll is introduced. The percentage of winners is even zero for the Zone scenario which does not include exemptions. This is not surprising given the values of travel time presented in Table 3. At most, they reach 11.4 euros per hour. This implies that, for instance, a toll of 2 euros per day would need to reduce per day travel times by 11 minutes just to compensate for the toll. This time saving is unlikely in a charging zone of 105 sq km where the duration of trips is necessarily limited (22 minutes on average for car trips inside Paris).

If average cvs are all negative, the magnitude of the loss varies across scenarios. For instance, Residents induces lower losses than Zone (€0.81 versus €1.01). This is so because the exemption yields two opposite effects. On the one hand, residents pay less (€0.255 instead of €2.55). On the other hand, this partial exemption requires increasing the toll to keep the same traffic reduction level, thereby rising individual losses for the rest of the population (€2.55 for Residents instead of €1.70 for Zone). Our simulations show that the former dominates the latter, probably because the proportion of residents among the motorists who stay on the road once the toll is introduced under the Zone scenario is quite high (around 50%).

Conversely, the average losses induced by Inbound Cordon and Green are similar to the benchmark (€1.03 and €1.02 versus €1.01 for Zone) suggesting that the two effects compensate each other.

Turning next to the scenarios PT funding and Uniform Redistribution, the recycling of revenues towards commuters obviously decreases losses. The two recycling scenarios produce similar results in terms of average loss (€0.68). To begin with, tolling is clearly politically risky as the proportion of gainers is low in most cases. Then, if reducing potential political opposition of motorists is crucial, redistributing revenues to commuters is obviously adequate.

Distributional effects across income groups

Having compared the average cv induced by the different scenarios, we now consider equity issues by examining how the cv varies across income groups.

Traffic reduction

Table 6 focuses on the Zone scenario and considers the influence of different levels of traffic reduction on equity. We express cvs in euros per trip and in proportion of income.

Let us first discuss the value of cvs expressed in euros per trip. Table 6 immediately shows that low-income motorists loose more than richer motorists when the reduction rate is low (10% or 20%). But the reverse is true for higher reduction rates.

In order to explain this result, recall first that high income motorists -who are also individuals with high value of time -tend to place more value on congestion reduction and are less affected by the toll's financial burden (because the marginal utility of income is decreasing). This is why, in theory, they would tend to lose less than low-income motorists when they keep using their car ex post. This scenario only applies to the motorists who continue to use their cars once the toll is introduced.

What about the income profile and cv of those who switch to PT? Table 7 compares their cv and income with those of the ex post motorists' group under the Zone scenario. We can see that they lose much less than the other group and that they have lower income.

To sum up, we have two opposite effects. On the one hand, the richest individuals lose less than the poorest within the group of motorists who continue to use their car. On the other hand motorists who shift to PT are poorer than the motorists staying on the road, and lose less.

According to Table 6, the first effect dominates the second when motorists continuing to use their cars are numerous -that is, when tolling reduce the traffic by 10, 20% -while the reverse is true for higher levels of traffic reduction (50%). Under the 30% reduction scenario both effects compensate each other so that cvs do not change across income groups.

Finally, when considering cv in percentage of income, Table 6 shows that low-income individuals lose more than richer individuals whatever the scenario. Therefore, all scenarios are regressive.

Exemptions

We now investigate the impact of different exemptions. Table 8 shows the difference between the average cv under Inbound Cordon, Residents, and Green and the average cv under Zone.

Figures are given for the income group 1 which gathers the 20% of individuals with the lowest income. We focus on cv in €/trip as there is no reason why patterns would significantly change with cv expressed in proportion to income.

The ranking between the different scenarios is not ambiguous. The scenario Inbound Cordon is the worst option for low-income individuals. The scenario Residents is similar to Zone while Green makes low-income motorists slightly better off. In order to understand why this is, Table 8 displays the percentage of motorists who enjoy a rebate or an exemption in income group 1 as compared to the whole population. Under Cordon, the share of poor motorists travelling within Paris (7%) is half that of the whole population (15%). On the other hand, about 36% of motorists drive low CO2 emitting cars in income group 1 -a proportion slightly higher than in the whole population, while Residents is an intermediate case. This is consistent with the ranking given by Table 8.

We complete the analysis of the influence of exemptions by examining how the level of losses varies with the level of income. Figure 1 and 2 shows cv as a function of income for the motorists and the commuters respectively. Using this indicator, Green is again the best scenario for the poorest. Then, Zone is in intermediate position while Residents and Inbound Cordon are the less equitable options.

Note also that, except for Residents, the welfare losses are an increasing function of income for the whole population of commuters while it is generally the opposite within the motorists' group. The explanation is straightforward. Low-income individuals tend to use PT much more than high-income individuals: 70% of those in quintile 1 use PT, but only 37% of those in quintile 5.

Recycling of toll revenues

Until now, we have discussed scenarios in which revenues are not redistributed to commuters, meaning that recycling has no impacts on the distributional profile. Here, we consider the scenario where revenues are used to cut PT fares (PT Funding) and the scenario in which revenues are evenly redistributed to all commuters (Uniform Redistribution).

Table 9 gathers the main figures. It shows that the two scenarios have the same distributional profile. This might be surprising as low-income commuters opt more frequently for the PT mode. Given this, one would expect smaller losses for them under the PT funding scenario which allocates all the revenues to PT. But this is not the end of the story. Reducing the cost of PT increases the incentives for motorists to withdraw their car. Therefore, the toll rate necessary for a 20% traffic reduction is smaller than without redistribution to PT.7 Hence, motorists also gain, albeit indirectly, when the revenues are allocated to PT.

Conclusion

We have developed an econometric model to simulate the distributional effects of various urban road pricing scenarios in Paris. The methodology is based on a mode choice model that is nonlinear in income. This is particularly suitable for assessing distributional effects as it relaxes the assumption of constant marginal utility of income made in traditional models.

Nevertheless, two methodological limits should be kept in mind when interpreting the results.

First, we only deal with home-to-work trips. Second, we rely on a basic traffic model -a simple speed-flow relationship -to calculate the time reductions induced by tolling.

That being said, the analysis brings out four types of results. First, we show that motorists endure average welfare losses ranging from €0.7 to €1.0 per trip when a toll that induces a 20% traffic reduction is implemented. In other words, motorists taken as a whole tend to lose when a toll is introduced. This result is not surprising when one considers their Although all the scenarios imply welfare losses on average for motorists, those losses do not have the same magnitude. They are smaller when residents are partially exempted. Thus, the political acceptability of tolling could be improved with this exemption. On the other hand, an inbound cordon toll exempting those who make car trips within Paris generates the highest average loss.

Concerning the distributional effects of tolls across different income groups, conclusions primarily depend on whether the losses induced by tolling are measured in absolute terms, i.e., in euros per trip, or in relative terms, i.e., as a percentage of income. In relative terms, tolls are always more detrimental to low-income individuals, meaning that tolling is regressive.

In absolute terms, results are much less clear-cut. In fact, the distributional pattern depends crucially on the level of traffic reduction. When it is low (10% or 20%), the poorest motorists lose more than the richest ones. But the reverse is true for higher reduction rates. The reason for this is that the motorists who switch to PT lose less and are poorer on average than the other motorists. As the size of this subpopulation increases with the level of traffic reduction, stringent tolls tend to be more favourable to low-income individuals.

Turning next to the impacts of various exemptions, an interesting result is that granting When taking into account the allocation of toll revenues, we obtain the somewhat surprising result that there is no significant difference between a scenario which allocates receipts to PT users and a scenario which evenly distributes receipts to all commuters. One would expect PT funding to be more favourable to low-income individuals as motorists are significantly richer than PT users. However, allocating money to PT increases the incentives for motorists to withdraw their car. Therefore, for a given traffic reduction rate, the level of the toll is lower, implying indirect gains for motorists.

In our view, the major policy lesson of this analysis is that the design of the road pricing scheme and the level of traffic reduction strongly influence equity patterns. Note that the same is probably true for social efficiency. But this is out of the scope of the present paper. Sensitivity analysis shows that our results are pretty robust to changes in distances covered in the charging zone. For instance, the assumption that motorists travelling partially in the charging zone -those whose origin or destination is outside the zone -cover a distance equal to the average of distances covered by motorists that travel exclusively in the charging zone (3,171 meters) is robust. Doubling this distance (6,342 meters) -which means doubling the distance for which motorists enjoy travel time savings -does not modify the final distributional patterns significantly.

Finally, Table A1 gives the average travel time reduction and the average speed variation for the different toll scenarios. The table only considers motorists driving before and after the toll is introduced. a "Motorists only" refer to those travelling by car before the toll has been introduced whatever their mode choice after tolling. b "All commuters" refer to all the members of our sample (i.e., motorists and non-captive PT users) plus captive PT users (i.e., those without a driver's license or access to a car). A null cv is assigned to the latter.

  calculated using a speed-flow function estimated econometrically on a sample that describes traffic levels and speeds for 19 time slots. For each slot, we calculate the total traffic by car and the average speed of car trips in Paris. The regression of the logarithm of traffic on the average speed presents a R2 of 0.58 and gives the following relationship:SPEED = -69.0 × ln(TRAFFIC) + 877.4where SPEED is the average speed of car trips in meters per minute in a given slot and TRAFFIC is the total number of trips per slot 4 .We use this equation to calculate times savings by making two simplifying assumptions: (i) motorists travelling partially in the charging zone -those whose origin or destination is outside the zone -cover a distance equal to the average of distances covered by motorists that travel exclusively in the charging zone (namely 3,171 meters for Paris intra muros); (ii) the traffic reduction rate induced by tolling equals the traffic reduction rate predicted for motorists making home-to-work trips. This amounts to assuming that all the motorists generally behave like motorists making home-to-work trips. The first hypothesis is necessary as the Global Transport Survey does not describe the length of the part of the trip made in Paris. The second is necessary because we only estimate mode choices for commuters.

  values of travel time. They reach €11.4 per hour at the most, which would require a travel time reduction of around 11 minutes to outweigh a €2 toll, for example. For scenarios geographically limited to Paris, such large time savings are almost always impossible.

a

  rebate to low CO2 emission cars slightly improves the situation of low-income individuals relative to high-income individuals while the inbound cordon scenario has opposite effects. This is because motorists entering Paris have lower incomes. The distributional pattern of the scenario in which Paris residents only pay 10% of the toll is contrasted. Clearly, the poorest individuals lose more than the richest ones, because residents are far richer than suburban individuals. But they endure the same losses as under the reference scenario without exemption.

Figure 1 :Figure 2 :

 12 Figure 1: Average cv of motorists (€/trip) by income group under Zone, Inbound Cordon,

  the individual is a woman, 0 otherwise; FREE_PARK = 1 if the individual gets a car park for free at her place of work, 0 otherwise;

TWO_CARS =1 if the household owns two cars or more, 0 otherwise; TWO_KIDS = 1 if the household has two children or more, 0 otherwise. Table

1

presents the main descriptive statistics of our sample and the variables used for the estimation. For instance, it can be seen that motorists represent around 29% of the sample, that on average car trips last 3.79 minutes less than trips by PT and that woman are in a minority (45%).

  Table 3 presents these values by quintile of income. Income group 1 includes the 20% of individuals having the lowest income; quintiles 1 and 2 include the

40% of individuals having the lowest income, etc. These figures show a strong and positive relationship between income and value of time.

Table A1 : Travel time reduction and speed increase for the nine scenarios

 A1

	Scenario	Avg. initial	Avg. travel time	Avg.	Avg. speed increase
		travel time	reduction induced by	initial	induced by tolling
			tolling		speed
		minutes	minutes	%	km/h	km/h	%
	Zone 20%	36.2	-1.9	-5%	16.3	1.0	6%
	Zone 10%	37.3	-0.9	-2%	16.1	0.4	3%
	Zone 30%	35.6	-2.9	-8%	16.4	1.5	9%
	Zone 50%	33.3	-4.8	-14%	16.1	3.6	23%
	Inbound Cordon	35.2	-1.9	-6%	15.8	1.0	6%
	Residents	35.6	-2.0	-6%	15.6	1.0	6%
	Green	36.6	-1.9	-5%	16.3	1.0	6%
	PT funding	36.2	-1.9	-5%	16.3	1.0	6%
	Uniform	36.2	-1.9	-5%	16.3	1.0	6%
	redistribution

Table 1 : Descriptive statistics

 1 In order to estimate C B , we use season ticket prices in force in July 2001. In order to estimate C A , we use an average kilometric cost of €0.269 per kilometre. This average cost is computed by the Ile-de-France public transport regulator (STIF) for 2001 and includes fuel, maintenance and parking costs. c Ideally, it would have been better to use income available once the accommodation spending have been paid rather than income per capita, as an evident relationship exists between accommodation spending and transport spending. Unfortunately, this information is not available. d CO2 emissions are not recorded directly in the Global Transport Survey. Details on the methodology and on the additional data references used to estimate CO2 emissions are available on request.

	Variable	Definition			Number of observations	Mean	Standard Deviation
	A		= 1 if a private car is used. 0 if	1030	0.29	0.45
			PT is used
	0 A T T B -	Time differential between PT	1030	3.79	20.38
			and car (minutes)
	C B B	(euros) a Monetary cost of a PT trip	1030	0.67	0.22
	C	0 A	trip (euros) b Monetary cost of a private car	1030	3.77	2.53
	y		Daily household income per	1030	104.38	58.86
			capita c (euros)
	DC	y C -	B	-	y C -	0 A	1030	0.18	0.17
	FEMALE	= 1 if the individual is a	1030	0.45	0.50
			woman. 0 otherwise
	FREE_PARK	= 1 if the individual gets a car	1030	0.41	0.49
			park for free at her place of
			work, 0 otherwise
	NB_CARS	Number of cars in the	1030	1.41	0.60
			household
	TWO_CARS	=1 if the individual belongs to	1030	0.35	0.48
			a household that owns two cars
			or more, 0 otherwise
	TWO_KIDS	= 1 if the individual belongs to	1030	0.19	0.40
			a household with two children
			or more, 0 otherwise
	RESIDENT	= 1 if the individual lives in	1030	0.27	0.44
			Paris, 0 otherwise
	CO2	CO2 emissions of the car used d	296	187.92	11.23
			(g/Km) (specific to car users)

a B b

Table 9 : Average cv (€/trip) under PT Funding and Uniform Redistribution by income groups PT Funding Uniform Redistribution Quintile

 9 Motorists only a All commuters b Motorists only a All commuters b

	1	-0.71	0.12	-0.71	0.12
	2	-0.69	0.06	-0.69	0.06
	3	-0.68	0.00	-0.68	0.00
	4	-0.67	-0.09	-0.67	-0.09
	5	-0.67	-0.22	-0.67	-0.21
	All	-0.68	-0.01	-0.68	-0.01

For instance, the income of motorists circulating in Paris is 30% higher than the income of individuals using PT (source: EGT

[2001][2002].

Their scenario is a modified version of the scheme actually implemented in Stockholm in 2006. Note that they analyze different allocations of toll revenues.

Although an exact formula was not previously available, less satisfactory approximations of E[cv] had been suggested in the literature. For instance,[START_REF] Mcfadden | Computing willingness-to-pay in random utility models[END_REF] has developed a Monte Carlo simulator for computing cv in random utility models which converges to the true distribution of cv.

The level of traffic taken into account is the total traffic observed in the Global Transport Survey, i.e., the traffic due to individual trips. It excludes deliveries and freight.

Note that our benchmark scenario differs from a zone toll of the London type. In London, one payment allows the vehicle to be used for as many journeys as the driver wishes in the charging zone. In our scenario, a fee is imposed on each single trip in the charging zone.

In both scenarios, redistribution also concerns captive PT users -defined as PT users without a driver's license or access to a car. These commuters represent around 43% of total PT users making home-to-work trips in Paris.

According to our simulations, the toll is €1.40 under PT funding as compared to €1.70 under Zone.

Acknowledgments

We gratefully acknowledge financial support from the French Interministerial Task-Force on Climate Change (MIES). We are also grateful to the Ile-de-France Regional Directorate for the Equipment (DREIF) for the provision of data.

Appendix

For a given individual trip, we calculate the new car travel time 1 A T after the introduction of the toll with the formula:

if the trip is exclusively made inside Paris a "Motorists only" refer to those travelling by car before the toll has been introduced whatever their mode choice after tolling. b "All commuters" refer to all the members of our sample (i.e., motorists and non-captive PT users) plus captive PT users (i.e., those without a driver's license or access to a car). A null cv is assigned to the latter. All commuters 0.01 NB: "Motorists only" refer to those travelling by car before the toll has been introduced whatever their mode choice after tolling. "All commuters" refer to all the members of our sample (i.e., motorists and non-captive PT users) plus captive PT users (i.e., those without a driver's license or access to a car). A null cv is assigned to the latter.

3,171 1 , otherwise