Luc Pronzato
email: pronzato@i3s.unice.fr

Henry P Wynn
email: h.wynn@lse.ac.uk

Anatoly A Zhigljavsky
email: zhigljavskyaa@cf.ac.uk

An extended Generalised Variance, with Applications

Keywords: Primary 94A17; secondary 62K05 keyword: dispersion, generalised variance, quadratic entropy, maximum-entropy measure, design of experiments, optimal design

  L'archive ouverte pluridisciplinaire

Introduction

The idea of dispersion is fundamental to statistics and with different terminology, such as potential, entropy, information and capacity, stretches over a wide area. The variance and standard deviation are the most prevalent for a univariate distribution, and Wilks generalised variance is the term usually reserved for the determinant of the covariance matrix, V , of a multivariate distribution. Many other measures of dispersion have been introduced and a rich area comprises those that are orderpreserving with respect to a dispersion ordering; see [START_REF] Shaked | Dispersive ordering of distributions[END_REF][START_REF] Oja | Descriptive statistics for multivariate distributions[END_REF][START_REF] Giovagnoli | Multivariate dispersion orderings[END_REF]. These are sometimes referred to as measures of peakness and peakness ordering, and are related to the large literature on dispersion measures which grew out of the Gini coefficient, used to measure income inequality [START_REF] Gini | Measurement of inequality of incomes[END_REF] and diversity in biology, see [START_REF] Rao | Diversity and dissimilarity coefficients: a unified approach[END_REF], which we will discuss briefly below.

In the definitions there are typically two kinds of dispersion, those measuring some kind of mean distance, or squared distance, from a central value, such as in the usual definition of variance, and those based on the expected distance, or squared distance, between two independent copies from the same distribution, such as the Gini coefficient. It is this second type that will concern us here and we will generalise the idea in several ways by replacing distance by volumes of simplices formed by k independent copies and by transforming the distance, both inside the expectation and outside.

The area of optimal experimental design is another which has provided a range of dispersion measures. Good designs, it is suggested, are those whose parameter estimates have low dispersion. Typically, this means that the design measure, the spread of the observation sites, maximises a measure of dispersion and we shall study this problem.

We think of a dispersion measure as a functional directly on the distribution. The basic functional is an integral, such as a moment. The property we shall stress for such functionals most is concavity: that a functional does not decrease under mixing of the distributions. A fundamental theorem in Bayesian learning is that we expect concave functionals to decrease through taking of observations, see Section 2.2 below.

Our central result (Section 3) is an identity for the mean squared volume of simplices of dimension k, formed by k+1 independent copies, in terms of the eigenvalues of the covariance matrices or equivalently in terms of sums of the determinants of k-marginal covariance matrices. Second, we note that after an appropriate (exterior) power transformation the functional becomes concave. We can thus (i) derive properties of measures that maximise this functional (Section 4.1), (ii) use this functional to measure the dispersion of parameter estimates in regression problems, and hence design optimal experiments which minimise this measure of dispersion (Section 4.2).

Dispersion measures 2.1 Concave and homogeneous functionals

Let X be a compact subset of R d , M be the set of all probability measures on the Borel subsets of X and φ : M -→ R + be a functional defined on M . We will be interested in the functionals φ(•) that are (see Appendix for precise definitions) (a) shift-invariant, (b) positively homogeneous of a given degree q, and (c) concave: φ[(1 -α)µ 1 + αµ 2 ] ≥ (1 -α)φ(µ 1 ) + αφ(µ 2 ) for any α ∈ (0, 1) and any two measures µ 1 , µ 2 in M .

For d = 1, a common example of a functional satisfying the above properties, with q = 2 in (b), is the variance

σ 2 (µ) = E (2) µ -E 2 µ = 1 2 (x 1 -x 2 ) 2 µ(dx 1 ) µ(dx 2 )
,

where

E µ = E µ (x) = x µ(dx) and E (2) µ = x 2 µ(dx). Concavity follows from linearity of E (2) µ , that is, E (2) (1-α)µ1+αµ2 = (1-α)E (2) µ1 +αE (2)
µ2 , and Jensen's inequality which implies

E 2 (1-α)µ1+αµ2 ≤ (1 -α)E 2 µ1 + αE 2 µ2
. Any moment of µ ∈ M is a homogeneous functional of a suitable degree. However, the variance is the only moment which satisfies (a) and (c). Indeed, the shift-invariance implies that the moment should be central, but the variance is the only concave functional among the central moments, see Appendix. In this sense, one of the aims of this paper is a generalisation of the concept of variance.

In the general case d ≥ 1, the double variance 2σ 2 (µ) generalises to

φ(µ) = x 1 -x 2 2 µ(dx 1 ) µ(dx 2 ) = 2 x -E µ 2 µ(dx) = 2 trace(V µ ) , (2.1)
where • is the L 2 -norm in R d and V µ is the covariance matrix of µ. This functional, like the variance, satisfies the conditions (a)-(c) with q = 2. The functional (2.1) is the double integral of the squared distance between two random points distributed according to the measure µ. Our main interest will be concentrated around the general class of functionals defined by

φ(µ) = φ [k],δ,τ (µ) = . . . V δ k (x 1 , . . . , x k+1 ) µ(dx 1 ) . . . µ(dx k+1 ) τ , k ≥ 2 (2.
2) for some δ and τ in R + , where V k (x 1 , . . . , x k+1 ) is the volume of the k-dimensional simplex (its area when k = 2) formed by the k + 1 vertices x 1 , . . . , x k+1 in R d , with k = d as a special case. Property (a) for the functionals (2.2) is then a straightforward consequence of the shift-invariance of V k , and positive homogeneity of degree q = k δτ directly follows from the positive homogeneity of V k with degree k. Concavity will be proved to hold for δ = 2 and τ ≤ 1/k in Section 3. There, we show that this case can be considered as a natural extension of (2.1) (which corresponds to k = 1), with φ [k],2,τ (µ) being expressed as a function of V µ , the covariance matrix of µ. The concavity for k = τ = 1 and all 0 < δ ≤ 2, follows from the Schoenberg theory, which will be discussed briefly below. The functionals (2.2) with δ = 2 and τ > 0, 1 ≤ k ≤ d, can be used to define a family of criteria for optimal experimental design, concave for τ ≤ 1/k, for which an equivalence theorem can be formulated.

Quadratic entropy and learning

In a series of papers [START_REF] Rao | Diversity and dissimilarity coefficients: a unified approach[END_REF][START_REF] Rao | Diversity: Its measurement, decomposition, apportionment and analysis[END_REF][START_REF] Rao | Convexity properties of entropy functions and analysis of diversity[END_REF] C.R. Rao and co-workers have introduced a quadratic entropy which is a generalised version of the k = 2 functional of this section but with a general kernel K(x 1 , x 2 ) in R d :

Q R = K(x 1 , x 2 )µ(dx 1 )µ(dx 2 ) . (2.3)
For the discrete version

Q R = N i=1 N j=1 K(x i , x j ) p i p j ,
Rao and co-workers developed a version of the Analysis of Variance (ANOVA), which they called Anaysis of Quadratic Entropy (ANOQE). The Gini coefficient, also used in the continuous and discrete form is a special case with d = 1 and

K(x 1 , x 2 ) = |x 1 -x 2 |.
As pointed in [START_REF] Rao | Convexity properties of entropy functions and analysis of diversity[END_REF]Chap. 3], a necessary and sufficient condition for the functional Q R to be concave is

K(x 1 , x 2 )ν(dx 1 )ν(dx 2 ) ≤ 0 (2.4)
for all measures ν with ν(dx) = 0. The discrete version of this is

N i=1 N j=1 K(x i , x j ) q i q j ≤ 0
for any choice of real numbers q 1 , . . . , q N such that N i=1 q i = 0. Schoenberg [START_REF] Schoenberg | Metric spaces and positive definite functions[END_REF] solves the general problem of finding for what class of functions B(•) on x 1 -x 2 2 does the kernel K(x 1 , x 2 ) = B x 1 -x 2 2 satisfy (2.4). The solution is that B must be a so-called Bernstein function, see [START_REF] Schilling | Bernstein Functions: Theory and Applications[END_REF]. We do not develop these ideas here, but note that B(λ) = λ α is a Bernstein function for all 0 < α ≤ 1. This is the reason that, above, we can claim concavity for k = 1 and all 0 < δ ≤ 2 in (2.2).

Hainy et al [START_REF] Hainy | Learning functions and approximate bayesian computation design: ABCD[END_REF] discuss the link to embedding and review some basic results related to Bayesian learning. One asks what is the class of functionals ψ on a distribution µ(θ) of a parameter in the Bayesian statistical learning such that for all µ(θ) and all sampling distributions π(x|θ) one expects to learn, in the preposterior sense: ψ(µ(θ)) ≤ E ν ψ(π(θ|X)), with X ∼ ν. The condition is that ψ is convex, a result which has a history but is usually attributed to De Groot [START_REF] Degroot | Bayes estimation with convex loss[END_REF]. This learning is enough to justify calling such a functional a generalised information functional, or a general learning functional. Shannon information falls in this class, and earlier versions of the result were for Shannon information. It follows that wherever, in this paper, we have a concave functional then its negative is a learning functional.

Functionals based on squared volume

In the rest of the paper we focus our attention on the functional

µ ∈ M -→ ψ k (µ) = φ [k],2,1 (µ) = E µ {V 2 k (x 1 , . . . , x k+1 )} ,
which corresponds to the mean squared volume of simplices of dimension k formed by k + 1 independent samples from µ. For instance,

ψ 2 (µ) = V 2 2 (x 1 , x 2 , x 3 ) µ(dx 1 ) µ(dx 2 ) µ(dx 3 ) , (3.1)
with V 2 (x 1 , x 2 , x 3 ) the area of the triangle formed by the three points with coordinates x 1 , x 2 and x 3 in R d , d ≥ 2. Functionals φ [k],δ,τ (µ) for δ = 2 will be considered elsewhere, including the case of negative δ and τ in connection with space-filling design for computer experiments. Theorem 3.1 of Section 3.1 indicates how ψ k (µ) can be expressed as a function of V µ , the covariance matrix of µ, and shows that φ [k],2,1/k (•) satisfies properties (a), (b) and (c) of Section 2.1. The special case of k = d was known to Wilks [START_REF] Wilks | Certain generalizations in the analysis of variance[END_REF][START_REF] Wilks | Multidimensional statistical scatter[END_REF] in his introduction of generalised variance, see also [START_REF] Van Der | A note on Wilks' internal scatter[END_REF]. The connection with U-statistics is exploited in Section 3.2, where an unbiased minimum-variance estimator of ψ k (µ) based on a sample x 1 , . . . , x n is expressed in terms of the empirical covariance matrix of the sample.

Expected squared k-simplex volume

Theorem 3.1. Let the x i be i.i.d. with the probability measure µ ∈ M . Then, for any k ∈ {1, . . . , d}, we have

ψ k (µ) = k + 1 k! i1<i2<•••<i k det[{V µ } (i1,...,i k )×(i1,...,i k ) ] (3.2) = k + 1 k! i1<i2<•••<i k λ i1 [V µ ] × • • • × λ i k [V µ ] , (3.3)
where λ i [V µ ] is the i-th eigenvalue of the covariance matrix V µ and all i j belong to {1, . . . , d}. Moreover, the functional ψ The proof uses the following two lemmas. Lemma 3.1. Let the k + 1 vectors x 1 , . . . , x k+1 of R k be i.i.d. with the probability measure µ, k ≥ 2. For i = 1, . . . , k + 1, denote z i = (x ⊤ i 1) ⊤ . Then

1/k k (•) is shift-invariant,
E µ det k+1 i=1 z i z ⊤ i = (k + 1)! det[V µ ] .
Proof. We have

E µ det k+1 i=1 z i z ⊤ i = (k + 1)! det E µ (x 1 x ⊤ 1 ) E µ E ⊤ µ 1 = (k + 1)! det[V µ ] ,
see for instance [START_REF] Pronzato | On a property of the expected value of a determinant[END_REF]Theorem 1].

Lemma 3.2. The matrix functional µ → V µ is Loewner-concave on M , in the sense that, for any µ 1 , µ 2 in M and any α ∈ (0, 1),

V (1-α)µ1+αµ2 (1 -α)V µ1 + αV µ2 , (3.4)
where A B means that A -B is nonnegative definite.

Proof. Take any vector z of the same dimension as x.

Then z ⊤ V µ z = var µ (z ⊤ x), which is a concave functional of µ, see Section 2.1. This implies that z ⊤ V (1-α)µ1+αµ2 z = var (1-α)µ1+αµ2 (z ⊤ x) ≥ (1-α)var µ1 (z ⊤ x)+αvar µ2 (z ⊤ x) = (1-α)z ⊤ V µ1 z+αz ⊤ V µ2 z,
for any µ 1 , µ 2 in M and any α ∈ (0, 1) (see Section 2.1 for the concavity of var µ ). Since z is arbitrary, this implies (3.4).

Proof of Theorem 3.1. When k = 1, the results follow from ψ 1 (µ) = 2 trace(V µ ), see (2.1). Using Binet-Cauchy formula, see, e.g., [3, vol. 1, p. 9], we obtain

V 2 k (x 1 , . . . , x k+1 ) = 1 (k!) 2 det           (x 2 -x 1 ) ⊤ (x 3 -x 1 ) ⊤ . . . (x k+1 -x 1 ) ⊤      [(x 2 -x 1 ) (x 3 -x 1 ) • • • (x k+1 -x 1 )]      = 1 (k!) 2 i1<i2<•••<i k det 2    {x 2 -x 1 } i1 • • • {x k+1 -x 1 } i1 . . . . . . . . . {x 2 -x 1 } i k • • • {x k+1 -x 1 } i k    = 1 (k!) 2 i1<i2<•••<i k det 2      {x 1 } i1 • • • {x k+1 } i1 . . . . . . . . . {x 1 } i k • • • {x k+1 } i k 1 • • • 1      ,
where {x} i denotes the i-th component of vector x. Also, for all

i 1 < i 2 < • • • < i k , det 2      {x 1 } i1 • • • {x k+1 } i1 . . . . . . . . . {x 1 } i k • • • {x k+1 } i k 1 • • • 1      = det   k+1 j=1 z j z ⊤ j  
where we have denoted by z j the k+1-dimensional vector with components {x j } i ℓ , ℓ = 1, . . . , k, and 1. When the x i are i.i.d. with the probability measure µ, using Lemma 3.1 we obtain (3.2), (3.3). Therefore

ψ k (µ) = Ψ k [V µ ] = k + 1 k! E k {λ 1 [V µ ], . . . , λ d [V µ ]} , (3.5) with E k {λ 1 [V µ ], . . . , λ d [V µ ]
} the elementary symmetric function of degree k of the d eigenvalues of V µ , see, e.g., [11, p. 10]. Note that

E k [V µ ] = E k {λ 1 [V µ ], . . . , λ d [V µ ]} = (-1) k a d-k ,
with a d-k the coefficient of the monomial of degree d -k of the characteristic polynomial of V µ ; see, e.g., [11, p. 21]. We have in particular

E 1 [V µ ] = trace[V µ ] and E d [V µ)] = det[V µ ].
The shift-invariance and homogeneity of degree 2 of ψ [11, p. 116] (take p = k in eq. [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF], with E 0 = 1). From [START_REF] López-Fidalgo | Characteristic polynomial criteria in optimal experimental design[END_REF], the Ψ 1/k k (•) are also Loewner-increasing, so that from Lemma 3.2, for any µ 1 , µ 2 in M and any α ∈ (0, 1), From the well-known expression of the coefficients of the characteristic polynomial of a matrix V , we have

1/k k (•) follow from the shift-invariance and positive homogeneity of V k with degree k. Con- cavity of Ψ 1/k k (•) follows from
ψ 1/k k [(1 -α)µ 1 + αµ 2 ] = Ψ 1/k k {V (1-α)µ1+αµ2 } ≥ Ψ 1/k k [(1 -α)V µ1 + αV µ2 ] ≥ (1 -α)Ψ 1/k k [V µ1 ] + αΨ 1/k k [V µ2 ] = (1 -α)ψ 1/k k (µ 1 ) + αψ 1/k k (µ 2 ) . The functionals µ -→ φ [k],2,τ (µ) = ψ τ k (µ) are thus concave for 0 < τ ≤ 1/k, with τ = 1/k yielding positive homogeneity of degree 2. The functional ψ 1 (µ) is a quadratic entropy Q R , see (2.3), ψ d (µ)
Ψ k (V ) = k + 1 k! E k (V ) (3.6) = k + 1 (k!) 2 det       trace(V ) k -1 0 • • • trace(V 2 ) trace(V ) k -2 • • • • • • • • • • • • • • • trace(V k-1 ) trace(V k-2 ) • • • 1 trace(V k ) trace(V k-1 ) • • • trace(V )       ,
see, e.g., [10, p. 28], and the E k (V ) satisfy the recurrence relations (Newton identities):

E k (V ) = 1 k k i=1 (-1) i-1 E k-i (V ) E 1 (V i ) , (3.7)
see, e.g., [3, Vol. 1, p. 88] and [START_REF] López-Fidalgo | Characteristic polynomial criteria in optimal experimental design[END_REF]. Particular forms of ψ k (•) are

k = 1 : ψ 1 (µ) = 2 trace(V µ ) , k = 2 : ψ 2 (µ) = 3 4 [trace 2 (V µ ) -trace(V 2 µ )] , k = 3 : ψ 3 (µ) = 1 9 [trace 3 (V µ ) -3 trace(V 2 µ )trace(V µ ) + 2 trace(V 3 µ )] , k = d : ψ d (µ) = d + 1 d! det(V µ ) .

The empirical version and unbiased estimates

Let x 1 , . . . , x n be a sample of n vectors of R d , i.i.d. with the measure µ. This sample can be used to obtain an empirical estimate ( ψ 1 ) n of ψ k (µ), through the consideration of the n k+1 k-dimensional simplices that can be constructed with the x i . Below we show how a much simpler (and still unbiased) estimation of ψ k (µ) can be obtained through the empirical variance-covariance matrix of the sample. See also [START_REF] Wilks | Certain generalizations in the analysis of variance[END_REF][START_REF] Wilks | Multidimensional statistical scatter[END_REF]. Denote

x n = 1 n n i=1 x i , V n = 1 n -1 n i=1 (x i -x n )(x i -x n ) ⊤ = 1 n(n -1) i<j (x i -x j )(x i -x j ) ⊤ ,
respectively the empirical mean and variance-covariance matrix of x 1 . Note that both are unbiased. We thus have

( ψ 1 ) n = 2 n(n -1) i<j x i -x j 2 = 2 trace[ V n ] = Ψ 1 ( V n ) = ψ 1 (µ n ) ,
with µ n the empirical measure of the sample, and the estimator ( ψ 1 ) n is unbiased. More generally, for k ≥ 1 we have the following.

Theorem 3.2. For x 1 , . . . , x n a sample of n vectors of R d , i.i.d. with the measure µ, and for any k ∈ {1, . . . , d}, the quantity

( ψ k ) n = (n -k -1)!(n -1) k (n -1)! Ψ k ( V n ) = (n -k -1)!(n -1) k (n -1)! ψ k (µ n ) , (3.8)
forms an unbiased estimator of ψ k (µ) and has minimum variance among all unbiased estimators.

Proof. Denote

( ψ k ) n = n k + 1 -1 j1<j2<•••<j k+1 V 2 k (x j1 , . . . , x j k+1 ) . (3.9)
It forms a U-statistics for the estimation of ψ k (µ) and is thus unbiased and has minimum variance, see, e.g., [START_REF] Serfling | Approximation Theorems of Mathematical Statistics[END_REF]Chap. 5]. We only need to show that it can be written as (3.8). We can write

( ψ k ) n = n k + 1 -1 × j1<j2<•••<j k+1 1 (k!) 2 i1<i2<•••<i k det 2      {x j1 } i1 • • • {x j k+1 } i1 . . . . . . . . . {x j1 } i k • • • {x j k+1 } i k 1 • • • 1      , = n k + 1 -1 1 (k!) 2 i1<i2<•••<i k det   n j=1 {z j } i1,...,i k {z j } ⊤ i1,...,i k   ,
where we have used Binet-Cauchy formula and where {z j } i1,...,i k denotes the k + 1 dimensional vector with components {x j } i ℓ , ℓ = 1, . . . , k, and 1. This gives

( ψ k ) n = n k + 1 -1 n k+1 (k!) 2 i1<i2<•••<i k det   1 n n j=1 {z j } i1,...,i k {z j } ⊤ i1,...,i k   , = n k + 1 -1 n k+1 (k!) 2 × i1<i2<•••<i k det (1/n){ n j=1 x j x ⊤ j } (i1,...,i k )×(i1,...,i k ) { x n } i1,...,i k { x n } ⊤ i1,...,i k 1 , = n k + 1 -1 n k+1 (k!) 2 i1<i2<•••<i k det n -1 n { V n } (i1,...,i k )×(i1,...,i k ) ,
and thus (3.8).

Using the notation of Theorem 3.1, since

E k (V ) = (-1) k a d-k (V ), with a d-k (V ) the coefficient of the monomial of degree d -k of the characteristic polynomial of V , for a nonsingular V we obtain E k (V ) = det(V ) E d-k (V -1 ) , (3.10)
see also [START_REF] López-Fidalgo | Characteristic polynomial criteria in optimal experimental design[END_REF]Eq. 4.2]. Therefore, we also have

( ψ d-k ) n = (n -d + k -1)!(n -1) d-k (n -1)! (d -k + 1)k! (k + 1)(d -k)! det( V n ) Ψ k ( V -1 n ) , (3.11)
which forms an unbiased and minimum-variance estimator of ψ d-k (µ). Note that the estimation of ψ k (µ) is much simpler through (3.8) or (3.11) than using the direct construction (3.9). One may notice that ψ 1 (µ n ) is clearly unbiased due to the linearity of Ψ 1 (•), but it is remarkable that ψ k (µ n ) becomes unbiased after a suitable scaling, see (3.8). Since Ψ k (•) is highly nonlinear for k > 1, this property would not hold if V n were replaced by another unbiased estimator of V µ .

The value of ( ψ k ) n only depend on V n , with E{( ψ k ) n } = ψ k (V µ ), but its variance depends on the distribution itself. From [20, Lemma A, p. 183], the variance of (

ψ k ) n satisfies var[( ψ k ) n ] = (k + 1) 2 n ω + O(n -2 ) ,
where

ω = var[h(x)], with h(x) = E{V 2 k (x 1 , x 2 , . . . , x k+1 )|x 1 = x}.
Obviously, E[h(x)] = ψ k (µ) and calculations similar to those in the proof of Theorem 3.1 give

ω = 1 (k!) 2 I,J det[{V µ } I×I ] det[{V µ } J×J ] (3.12) × E (E µ -x) ⊤ I {V µ } -1 I×I (E µ -x) I (E µ -x) ⊤ J {V µ } -1 J×J (E µ -x) J -k 2
, where I and J respectively denote two sets of indices i

1 < i 2 < • • • i k and j 1 < j 2 < • • • j k in {1, .
. . , k + 1}, the summation being over all possible such sets. Simplifications occur in some particular cases. For instance, when µ is a normal measure, then

ω = 2 (k!) 2 I,J det[{V µ } I×I ] det[{V µ } J×J ] × trace {V µ } -1 J×J {V µ } J×I {V µ } -1 I×I {V µ } I×J .
If, moreover, V µ is the diagonal matrix diag{λ 1 , . . . , λ d }, then

ω = 2 (k!) 2 I,J β(I, J) I λ i J λ j ,
with β(I, J) denoting the number of coincident indices between I and J (i.e., the size of I ∩ J). When µ is such that the components of x are i.d.d. with variance σ 2 , then V µ = σ 2 I d , with I d the d-dimensional identity matrix, and

E (E µ -x) ⊤ I {V µ } -1 I×I (E µ -x) I (E µ -x) ⊤ J {V µ } -1 J×J (E µ -x) J = E    i∈I z 2 i   j∈J z 2 j      ,
where the z i = {x -E µ } i /σ are i.i.d. with mean 0 and variance 1. We then obtain

ω = σ 4k (k!) 2 (E{z 4 i } -1) β d,k ,
where

β d,k = I,J β(I, J) = k i=1 i d i d -i k -i d -i -(k -i) k -i = (d -k + 1) 2 d d k -1 2 .
Example 1 We generate 1, 000 independent samples of n points for different measures µ. Figure 1 presents a box-plot of the ratios ( ψ k ) n /ψ k (µ) for various values of k and n = 100 (left), n = 1, 000 (right), when µ = µ 1 uniform in [0, 1] 10 . Figure 2 presents the same information when µ = µ 2 which corresponds to the normal distribution N (0, I 10 /12) in R 10 . Note that V µ1 = V µ2 but the dispersions are different in the two figures. Table 1 gives (10 3 ×) the values of E{( ψ k ) n }/ψ k (µ)-1 for µ = µ 1 , µ 2 and the same series of values for k, with E{( ψ k ) n } denoting the empirical mean over the 1,000 independent repetitions. In particular, ( ψ k ) n is asymptotically normal N (ψ k (µ), (k + 1) 2 ω/n), with ω given by (3.12). This is illustrated in Figure 3-left below for µ uniform in [0, 1] 10 , with n = 1, 000 and k = 3. The distribution is already reasonably close to normality for small values of n, see Figure 3-right for which n = 20.

1: δ(n, k) = 10 3 ×[ E{( ψ k )n}/ψ k (µ)-1] for different values of n and k; µ1 is uniform in [0, 1] 10 , µ2 is normal N (0, I10/12). k 1 2 3 d -3 d -2 d -1 d µ1 n = 100 0.

Maximum-entropy measures and optimal designs

In this section we consider two types of optimisation problems on M related to the functions Ψ k (•) introduced in Theorem 3.1. First, in Section 4.1, we are interested in the characterisation and construction of maximum-entropy measures; that is, measures µ * k ∈ M which maximize ψ k (µ) = Ψ k (V µ ). The existence of an optimal measure follows from the compactness of X and continuity of V k (x 1 , . . . , x k+1 ) in each x i , see [1, Th. 1]; the concavity and differentiability of the functional ψ 1/k k (•) allow us to derive a necessary and sufficient condition for optimality.

In Section 4.2 we consider the problem of optimal design of experiments, where the covariance matrix V is the inverse of the information matrix M (ξ) for some regression model.

Maximum-entropy measures

Necessary and sufficient condition

Since the functionals ψ 1/k k (•) are concave and differentiable, for all k = 1, . . . , d, we can easily derive a necessary and sufficient condition for a probability measure µ * k on X to maximise ψ k (µ), in the spirit of the celebrated Equivalence Theorem of Kiefer and Wolfowitz [START_REF] Kiefer | The equivalence of two extremum problems[END_REF].

Denote by ∇ Ψ k [V ] the gradient of Ψ k (•) at matrix V (a matrix of the same size as V ) and by F ψ k (µ; ν) the directional derivative of ψ k (•) at µ in the direction ν;

F ψ k (µ; ν) = lim α→0 + ψ k [(1 -α)µ + αν] -ψ k (µ) α .
From the expression (3.6) of Ψ k (V ), we have

∇ Ψ k [V ] = k + 1 k! ∇ E k [V ]) ,
where ∇ E k [V ] denotes the gradient of E k (•) at V , which, using (3.7), can be shown by induction to satisfy

∇ E k [V ] = k-1 i=0 (-1) i E k-i-1 (V ) V i , (4.1)
see [START_REF] López-Fidalgo | Characteristic polynomial criteria in optimal experimental design[END_REF]. We thus obtain in particular

k = 1 : ∇ Ψ1 [V ] = 2 I d , k = 2 : ∇ Ψ2 [V ] = 3 2 [trace(V ) I d -V ] , k = 3 : ∇ Ψ3 [V ] = 1 3 [trace 2 (V ) -trace(V 2 )] I d - 2 3 trace(V ) V + 2 3 V 2 , k = d : ∇ Ψ d [V ] = d + 1 d! det(V ) V -1 .
Using the differentiability of Ψ k (•), direct calculation gives

F ψ k (µ; ν) = trace ∇ Ψ k [V µ ] dV (1-α)µ+αν dα α=0 , with dV (1-α)µ+αν dα α=0 = [xx ⊤ -(E µ x ⊤ +xE ⊤ µ )] ν(dx)-xx ⊤ µ(dx)+2E µ E ⊤ µ . (4.2)
Notice that dV (1-α)µ+αν /dα α=0 is linear in ν.

Then, from the concavity of ψ

1/k k (•), µ * k maximises ψ k (µ) with respect to µ ∈ M if and only if ψ k (µ * k ) > 0 and F ψ k (µ * k ; ν) ≤ 0 for all ν ∈ M , that is trace ∇ Ψ k [V µ * k ] dV (1-α)µ * k +αν dα α=0 ≤ 0 , ∀ν ∈ M . (4.3)
We obtain the following.

Theorem 4.1. The probability measure µ * k such that ψ k (µ * k ) > 0 is ψ k -optimal, that is, maximises ψ k (µ) with respect to µ ∈ M , k ∈ {1, . . . , d}, if and only if

max x∈X (x -E µ * k ) ⊤ ∇ Ψ k [V µ * k ] Ψ k (V µ * k ) (x -E µ * k ) ≤ k . (4.4)
Moreover,

(x -E µ * k ) ⊤ ∇ Ψ k [V µ * k ] Ψ k (V µ * k ) (x -E µ * k ) = k (4.5)
for all x in the support of µ * k . Proof. First note that the Newton equations (3.7) and the recurrence (4.1) for

∇ E k [•] imply that trace(V ∇ Ψ k [V ]) = kΨ k (V ) for all k = 1, . . . , d.
The condition (4.4) is sufficient. Indeed, suppose that µ * k such that ψ k (µ * k ) > 0 satisfies (4.4). We obtain

(x -E µ * k ) ⊤ ∇ Ψ k [V µ * k ](x -E µ * k ) ν(dx) ≤ trace V µ * k ∇ Ψ k [V µ * k ]
for any ν ∈ M , which gives (4.3) when we use (4.2). The condition is also necessary since (4.3) must be true in particular for δ x , the delta measure at any x ∈ X , which gives (4.4). The property (4.5) on the support of µ * k follows from the observation that (x

-E µ * k ) ⊤ ∇ Ψ k [V µ * k ](x -E µ * k ) µ * k (dx) = trace V µ * k ∇ Ψ k [V µ * k ] . Note that for k < d, the covariance matrix V µ * k of a ψ k -optimal measure µ * k
is not necessarily unique and may be singular; see, e.g., Example 1 below. Also, ψ k (µ) > 0 implies that ψ k-1 (µ) > 0, k = 2, . . . , d.

Remark 4.1. As a natural extension of the concept of potential in case of ordertwo interactions (k = 1), we call P k,µ (x) = ψ k (µ, . . . , µ, δ x ) the potential of µ at x, where

ψ k (µ 1 , . . . , µ k+1 ) = . . . V 2 k (x 1 , . . . , x k+1 ) µ 1 (dx 1 ) . . . µ k+1 (dx k+1 ) .
This yields

F ψ k (µ; ν) = (k + 1) [ψ k (µ, . . . , µ, ν) -ψ k (µ)]
, where µ appears k times in ψ k (µ, . . . , µ, ν). Therefore, Theorem 4.4 states that µ * k is ψ k -optimal if and only if

ψ k (µ * k , . . . , µ * k , ν) ≤ ψ k (µ * k ) for any ν ∈ M , or equivalently P k,µ * k (x) ≤ ψ k (µ * k ) for all x ∈ X .
Remark 4.2. Consider Kiefer's Φ p -class of orthogonally invariant criteria and their associated functional ϕ p (•), defined by

ϕ p (µ) = Φ p (V µ ) =        λ max (V µ ) for p = ∞ , { 1 d trace(V p µ )} 1/d for p = 0, ±∞ , det 1/d (V µ ) for p = 0 , λ min (V µ ) for p = -∞ ,
where V µ is a d × d matrix; see, e.g., [START_REF] Pukelsheim | Optimal Experimental Design[END_REF]Chap. 6]. From a result in [START_REF] Harman | Lower bounds on efficiency ratios based on φ p -optimal designs[END_REF], if a measure µ p optimal for some ϕ p (•) with p ∈ (-∞, 1] is such that V µp is proportional to the identity matrix I d , then µ p is simultaneously optimal for all orthogonally invariant criteria. A measure µ p having this property is therefore ψ k -optimal for all k = 1, . . . , d. Notice that ψ 1 (•) and ψ

Ψ k (V ) = (k + 1)(d -k)! (d -k + 1)k! det(V ) Ψ d-k (V -1 )
which implies that maximising Ψ k (V ) is equivalent to maximising log det(V ) + log Ψ d-k (V -1 ). Therefore, Theorem 4.4 can be reformulated as:

µ * k maximises ψ k (µ) if and only if max x∈X (x -E µ * k ) ⊤ V -1 µ * k -V -1 µ * k ∇ Ψ d-k [V -1 µ * k ] Ψ d-k (V -1 µ * k ) V -1 µ * k (x -E µ * k ) ≤ d -k ,
with equality for x in the support of µ * k . When k is large (and d -k is small), one may thus check the optimality of µ * k without using the complicated expressions of

Ψ k (V ) and ∇ Ψ k [V ].

A duality property

The characterisation of maximum-entropy measures can also be approached from the point of view of duality theory.

When k = 1, the determination of a ψ 1 -optimal measure µ * 1 is equivalent to the dual problem of constructing the minimum-volume ball B * d containing X . If this ball has radius ρ, then ψ 1 (µ * 1 ) = 2ρ 2 , and the support points of µ * 1 are the points of contact between X and B * d ; see [START_REF] Björck | Distributions of positive mass, which maximize a certain generalized energy integral[END_REF]Th. 6]. Moreover, there exists an optimal measure with no more than d + 1 points.

The determination of an optimal measure µ * d is also dual to a simple geometrical problem: it corresponds to the determination of the minimum-volume ellipsoid E * d containing X . This is equivalent to a D-optimal design problem in R d+1 for the estimation of β = (β 0 , β ⊤ 1 ) ⊤ , β 1 ∈ R d , in the linear regression model with intercept β 0 + β ⊤ 1 x, x ∈ X , see [START_REF] Titterington | Optimal design: some geometrical espects of D-optimality[END_REF]. Indeed, denote

W µ = X (1 x ⊤ ) ⊤ (1 x ⊤ ) µ(dx)
.

Then E * d+1 = {z ∈ R d+1 : z ⊤ W -1 µ * d z ≤ d + 1}, with µ * d maximising det(W µ )
, is the minimum-volume ellipsoid centered at the origin and containing the set {z ∈ R d+1 : z = (1 x ⊤ ) ⊤ , x ∈ X }. Moreover, E * d corresponds to the intersection between E * d+1 and the hyperplane {z} 1 = 1; see, e.g., [START_REF] Shor | New algorithms for constructing optimal circumscribed and inscribed ellipsoids[END_REF]. This gives

ψ d (µ * d ) = (d + 1)/d! det(W µ * d ).
The support points of µ * d are the points of contact between X and E * d , there exists an optimal measure with no more than d(d + 3)/2 + 1 points, see [START_REF] Titterington | Optimal design: some geometrical espects of D-optimality[END_REF].

The property below generalises this duality property to any k ∈ {1, . . . , d}.

Theorem 4.2.

max µ∈M Ψ 1/k k (V µ ) = min M,c: X ⊂E (M,c) 1 φ ∞ k (M )
,

where

E (M, c) denotes the ellipsoid E (M, c) = {x ∈ R d : (x -c) ⊤ M (x -c) ≤ 1} and φ ∞ k (M ) is the polar function φ ∞ k (M ) = inf V 0: trace(MV )=1 1 Ψ 1/k k (V ) . ( 4.6)
The proof is given in Appendix. The polar function φ ∞ k (•) possesses the properties of what is called an information function in [START_REF] Pukelsheim | Optimal Experimental Design[END_REF]Chap. 5]; in particular, it is concave on the set of symmetric non-negative definite matrices. This duality property has the following consequence.

1) d+1 /[d d (d!) 2 ]. We also have V µ d = ρ 2 I d /d,
so that µ d is ψ d -optimal too. In view of Remark 4.2, µ 0 and µ d are ψ k -optimal for all k in {1, . . . , d}.

Let now µ k be the measure that allocates mass 1/(k + 1) at each vertex of a k regular simplex P k , centered at the origin, with its vertices on S d (0, ρ). The squared volume of

P k equals ρ 2k (k+1) k+1 /[k k (k!) 2 ]
. Without any loss of generality, we can choose the orientation of the space such that V µ k is diagonal, with its first k diagonal elements equal to ρ 2 /k and the other equal to zero. Note that ψ k ′ (µ k ) = 0 for k ′ > k. Direct calculations based on (3.6) give

ψ k (µ k ) = k + 1 k! ρ 2k k k ≤ ψ k (µ 0 ) = k + 1 k! d k ρ 2k d k ,
with equality for k = 1 and k = d, the inequality being strict otherwise. Figure 4 presents the efficiency [ψ k (µ k )/ψ k (µ 0 )] 1/k as a function of k when d = 20.

Optimal design in regression models

In this section we consider the case when V = M -1 (ξ), where M (ξ) is the information matrix

M (ξ) = T f (t)f ⊤ (t) ξ(dt)
in a regression model Y j = θ ⊤ f (t j ) + ε j with parameters θ ∈ R d , for a design measure ξ ∈ Ξ. Here Ξ denotes the set of probability measures on a set T such that {f (t) : t ∈ T} is compact, and M -1 (ξ) is the (asymptotic) covariance matrix of an estimator θ of θ when the design variables t are distributed according to ξ.

The value ψ k (µ) of Theorem 3.1 defines a measure of dispersion for θ, that depends on ξ through V µ = M -1 (ξ). The design problem we consider consists in choosing ξ that minimises this dispersion, as measured by Ψ k [M -1 (ξ)], or equivalently that maximises Ψ -1 k [M -1 (ξ)].

Properties

It is customary in optimal design theory to maximise a concave and Loewnerincreasing function of M (ξ), see [START_REF] Pukelsheim | Optimal Experimental Design[END_REF]Chap. 5] for desirable properties of optimal design criteria. Here we have the following.

(M -1 ) = k + 1 k! -1/k det 1/k (M ) E 1/k d-k (M ) (4.8)
which is a concave function of M , see Eq. ( 10) of [11, p. 116]. Since Ψ k (•) is Loewner-increasing, see [START_REF] López-Fidalgo | Characteristic polynomial criteria in optimal experimental design[END_REF], the function

M -→ Ψ -1/k k (M -1
) is Loewner-increasing too. Its orthogonal invariance follows from the fact that it is defined in terms of the eigenvalues of M .

Note that Theorems 3.1 and 4.3 imply that the functions M -→ -log Ψ k (M ) and M -→ log Ψ k (M -1 ) are convex for all k = 1, . . . , d, a question which was left open in [START_REF] López-Fidalgo | Characteristic polynomial criteria in optimal experimental design[END_REF].

As a consequence of Theorem 4.3, we can derive a necessary and sufficient condition for a design measure ξ * k to maximise Ψ

-1/k k [M -1 (ξ)] with respect to ξ ∈ Ξ, for k = 1, . . . , d. Theorem 4.4. The design measure ξ * k such that M (ξ * k ) ∈ M + maximises ψk (ξ) = Ψ -1/k k [M -1 (ξ)] with respect to ξ ∈ Ξ if and only if max t∈T f ⊤ (t)M -1 (ξ * k ) ∇ Ψ k [M -1 (ξ * k )] Ψ k [M -1 (ξ * k )] M -1 (ξ * k )f (t) ≤ k (4.9)
or, equivalently,

max t∈T f ⊤ (t)M -1 (ξ * k )f (t) -f ⊤ (t) ∇ Ψ d-k [M (ξ * k )] Ψ d-k [M (ξ * k )] f (t) ≤ d -k . (4.10)
Moreover, there is equality in (4.9) and (4.10) for all t in the support of ξ * k .

Proof. From (4.8), the maximisation of ψk (ξ) is equivalent to the maximisation of φk

(ξ) = log det[M (ξ)]-log Ψ d-k [M (ξ)].
The proof is similar to that of Theorem 4.4 and is based on the following expressions for the directional derivatives of these two functionals at ξ in the direction ν ∈ Ξ,

F ψk (ξ; ν) = trace 1 k M -1 (ξ) ∇ Ψ k [M -1 (ξ)] Ψ k [M -1 (ξ)] M -1 (ξ) [M (ν) -M (ξ)]
and

F φk (ξ; ν) = trace M -1 (ξ) - ∇ Ψ d-k [M (ξ)] Ψ d-k [M (ξ)] [M (ν) -M (ξ)] ,
and on the property trace{M ∇ Ψj [M ]} = j Ψ j (M ).

In particular, consider the following special cases for k (note that Ψ 0 (M ) = E 0 (M ) = 1 for any M ).

k = d : ψd (ξ) = log det[M (ξ)] , k = d -1 : ψd-1 (ξ) = log det[M (ξ)] -log trace[M (ξ)] -log 2 , k = d -2 : ψd-2 (ξ) = log det[M (ξ)] -log trace 2 [M (ξ)] -trace[M 2 (ξ)] -log(3/4) .
The necessary and sufficient condition (4.10) then takes the following form:

k = d : max t∈T f ⊤ (t)M -1 (ξ * k )f (t) ≤ d , k = d -1 : max t∈T f ⊤ (t)M -1 (ξ * k )f (t) - f ⊤ (t)f (t) trace[M (ξ * k )] ≤ d -1 , k = d -2 : max t∈T f ⊤ (t)M -1 (ξ * k )f (t) -2 trace[M (ξ * k )]f ⊤ (t)f (t) -f ⊤ (t)M (ξ * k )f (t) trace 2 [M (ξ * k )] -trace[M 2 (ξ * k )] ≤ d -2 .
Also, for k = 1 condition (4.9) gives

max t∈T f ⊤ (t) M -2 (ξ * 1 ) trace[M -1 (ξ * 1 )] f (t) ≤ 1
(which corresponds to A-optimal design), and for k = 2

max t∈T trace[M -1 (ξ * 2 )]f ⊤ (t)M -2 (ξ * 2 )f (t) -f ⊤ (t)M -3 (ξ * 2 )f (t) trace 2 [M -1 (ξ * 2 )] -trace[M -2 (ξ * 2 )] ≤ 1 .
Finally, note that a duality theorem, in the spirit of Theorem 4.2, can be formulated for the maximisation of Ψ [START_REF] Pukelsheim | Optimal Experimental Design[END_REF]Th. 7.12] for the general form a such duality properties in optimal experimental design.

-1/k k [M -1 (ξ)]; see

Examples

Example 4 For the linear regression model on θ 0 + θ 1 x on [-1, 1], the optimal design for ψk (•) with k = d = 2 or k = 1 is

ξ * k = -1 1 1/2 1/2 ,
where the first line corresponds to support points and the second indicates their respective weights.

Example 5 For linear regression with the quadratic polynomial model θ 0 + θ 1 t + θ 2 t 2 on [-1, 1], the optimal designs for ψk (•) have the form .

ξ * k = -1 0 1 w k 1 -2w k w k , with w 3 = 1/3, w 2 = ( √ 33 -
Table 2 gives the efficiencies Eff k (ξ * j ) for j, k = 1, . . . , d = 3. The design ξ * 2 , optimal for ψ2 (•), appears to make a good compromise between A-optimality (which corresponds to ψ1 (•)) and D-optimality (which corresponds to ψ3 (•)).

Example 6 For linear regression with the cubic polynomial model θ 0 + θ 1 t + θ 2 t 2 + θ 3 t 3 on [-1, 1], the optimal designs for ψk (•) have the form with z = z 3 . For k = d -2 = 2, the numbers z 2 and w 2 are too difficult to express analytically. Table 3 gives the efficiencies Eff k (ξ * j ) for j, k = 1, . . . , d. Here again the design ξ * 2 appears to make a good compromise: it maximises the minimum efficiency min k Eff f (•) among the designs considered. one has ∂ 2 ∆ q [(1 -α)µ 1 + αµ 2 ]/∂α 2 α=0 ≥ 0 for all q ≥ 1.84, the equality being obtained at q = 2 only. Counterexamples are easily constructed for values of q smaller than 1.84. k (V µ ). Note that we do not have an explicit form for φ ∞ k (M ) and that the infimum in (4.6) can be attained at a singular V , not necessarily unique, so that we cannot differentiate φ ∞ k (M ). Also note that compared to the developments in [START_REF] Pukelsheim | Optimal Experimental Design[END_REF]Chap. 7], here we consider covariance matrices instead of moment matrices.

ξ * k = -1 -z k z k 1 w k 1/2 -w k 1/2 -w k w k ,
Consider the maximisation of log φ ∞ k (M ) with respect to M and c such that X ⊂ E (M, c), with Lagrangian

L(M, c, β) = log φ ∞ k (M ) + x∈X β x [1 -(x -c) ⊤ M (x -c)] , β x ≥ 0 for all x in X .
For the sake of simplicity we consider here X to be finite, but

β
α x (x -c * )(x -c * ) ⊤ = -log Ψ 1/k k (V * k ) ,
where we have denoted γ = x∈X β x and α x = β x /γ for all x. Therefore T * ≤ -log Ψ

1/k k (V * k ), that is, log min M,c: X ⊂E (M,c) 1/φ ∞ k (M ) ≥ log Ψ 1/k k (V * k ).

homogeneous of degree 2

 2 and concave on M .

2 2 3 3

 23 is proportional to Wilks generalised variance, and ψ 1/(µ), see (3.1), and ψ 1/(µ) can be respectively considered as particular versions of cubic and quartic entropies.

Figure 1 :Figure 2 :

 12 Figure 1: Box-plot of ( ψ k ) n /ψ k (µ) for different values of k: µ is uniform in [0, 1] 10 , n = 100 (Left) and n = 1, 000 (Right) -1,000 repetitions; minimum, median and maximum values are indicated, together with 25% and 75% quantiles. Other properties of U-statistics apply to the estimator ( ψ k ) n , including almostsure consistency and the classical law of the iterated logarithm, see [20, Section 5.4].

Table

Figure 3 :

 3 Figure 3: Dots: empirical distribution of ( ψ k ) n (histogram for 10,000 independent repetitions); solid line: asymptotic normal distribution N (ψ k (µ), (k + 1) 2 ω/n); µ is uniform in [0, 1] 10 and k = 3; left: n = 1, 000; right: n = 20.

d

  (•) respectively coincide with ϕ 1 (•) and ϕ 0 (•) (up to a multiplicative scalar).

Remark 4 . 3 .

 43 Using (3.10), when V is nonsingular we obtain the property

Figure 4 :

 4 Figure 4: Efficiency [ψ k (µ k )/ψ k (µ 0 )] 1/k as a function of k when d = 20 in Example 3.

Theorem 4 . 3 .

 43 The functions M -→ Ψ -1/k k (M -1 ), k = 1, . . . , d, are Loewnerincreasing, concave and differentiable on the set M + of d × d symmetric positivedefinite matrices. The functions Ψ k (•) are also orthogonally invariant. Proof. The property (3.10) yields Ψ -1/k k

  1)/16 ≃ 0.2965352 and w 1 = 1/4. Define the efficiency Eff k (ξ) of a design ξ as Eff k (ξ) = ψk (ξ) ψk (ξ * k )

  Proof of Theorem 4.2 (i) The fact that max µ∈M Ψ1/k k (V µ ) ≥ min M,c: X ⊂E (M,c) 1/φ ∞ k (M ) is a consequence of Theorem 4.4. Indeed, the measure µ * k maximises Ψ 1/k k (V µ ) if and only if (x -E µ * k ) ⊤ M * (V µ * k )(x -E µ * k ) ≤ 1 for all x in X . (4.11) Denote M * k = M * (V µ * k ), c * k = E µ * k , and consider the Lagrangian L(V, α; M ) for the maximisation of (1/k) log Ψ k (V ) with respect to V 0 under the constraint trace(M V ) = 1: L(V, α; M ) = (1/k) log Ψ k (V ) -α[trace(M V ) -1] . We have ∂L(V, 1; M * k ) ∂V V =V µ * k = M * k -M * k = 0 and trace(M * k V µ * k ) = 1, with V µ * k 0. Therefore, V µ * k maximises Ψ k (V ) under the constraint trace(M * k V ) = 1,and, moreover, X ⊂ E (M * k , c * k ) from (4.11). This implies Ψ We prove now that min M,c: X ⊂E (M,c) 1/φ ∞ k (M ) ≥ max µ∈M Ψ 1/k

x - 1 .

 1 may denote any positive measure on X otherwise. Denote the optimum by T * = max M,c:X ⊂E (M,c) log φ ∞ k (M ) . It satisfies T * = max M,c min β≥0 L(M, c, β) ≤ min β≥0 max M,c L(M, c, β), and max M,c L(M, c, β) is attained for any c such that M c = M x∈X β x x/( x∈X β x ), that is, in particular for c * = x∈X β x x x∈X β x , and for M * such that 0 ∈ ∂ M L(M, c * , β) M=M * , the subdifferential of L(M, c * , β)with respect to M at M * . This condition can be written asx∈X β x (x -c * )(x -c * ) ⊤ = Ṽ ∈ ∂ log φ ∞ k (M ) M=M * , with ∂ log φ ∞ k (M ) the subdifferential of log φ ∞ k (M ), ∂ log φ ∞ k (M ) = {V 0 : Ψ 1/k k (V )φ ∞ k (M ) = trace(M V ) = 1} , see [14, Th. 7.9]. Since trace(M V ) = 1 for all V ∈ ∂ log φ ∞ k (M ), trace(M * Ṽ ) = 1 and thus x∈X β x (x -c * ) ⊤ M * (x -c * ) = 1 . Also, Ψ 1/k k ( Ṽ ) = 1/φ ∞ k (M * ), which gives L(M * , c * , β) = -log Ψ 1/k k x∈X β x (x -c * )(x -c * ) ⊤ + x∈X β x (x -c * )(x -c * ) ⊤ + γ -log(γ) -1 ,

Table 2 :

 2 Efficiencies Eff k (ξ * j ) for j, k = 1, . . . , d in Example 5.

		Eff1	Eff2	Eff3
	ξ * 1	1	0.9770 0.9449
	ξ * 2	0.9654	1	0.9886
	ξ * 3	0.8889 0.9848	1

Table 3 :

 3 Efficiencies Eff k (ξ *

				j ) for j, k = 1, . . . , d in Example 6.
			Eff1	Eff2	Eff3	Eff4
		ξ * 1	1	0.9785 0.9478 0.9166
		ξ * 2	0.9694	1	0.9804 0.9499
		ξ * 3	0.9180 0.9753	1	0.9897
		ξ * 4	0.8527 0.9213 0.9872	1
	where	z 4 = 1/ z 3 ≃ 0.4350486 , √ 5 ≃ 0.4472136 , z 2 ≃ 0.4240013 , z 1 = 3 √ 7 -6/3 ≃ 0.4639509 , w 1 = (4 -w 4 = 0.25 , w 3 ≃ 0.2149859 , w 2 ≃ 0.1730987 , √ 7)/9 ≃ 0.1504721 ,

with z 3 satisfying the equation 2z 6 -3z 5 -45z 4 + 6z 3 -4z 2 -15z + 3 = 0 and

w 3 = 5 z 6 + 5 z 4 + 5 z 2 + 1 -√ z 12 + 2 z 10 + 3 z 8 + 60 z 6 + 59 z 4 + 58 z 2 + 73 12(z 6 + z 4 + z 2 -3) ,

Corollary 4.1. The determination of a covariance matrix V * k that maximises Ψ k (V µ ) with respect to µ ∈ M is equivalent to the determination of an ellipsoid E (M * k , c * k ) containing X , minimum in the sense that M * k maximizes φ ∞ k (M ). The points of contact between E (M * k , c * k ) and X form the support of µ * k . For any V 0, denote by M * (V ) the matrix

Note that M * (V ) 0, see [START_REF] Pukelsheim | Optimal Experimental Design[END_REF]Lemma 7.5], and that

the optimal ellipsoid is then such that trace 2 (M )/(d -1) -trace(M 2 ) is maximised.

i=1 δ vi , with δ v the Dirac delta measure at v. Then, V µ * = I d /4 and one can easily check that µ * is ψ 1 -optimal. Indeed, E µ * = 1 d /2, with 1 d the d-dimensional vector of ones, and max x∈X (x-

Note that the two-point measure µ

Example 3 Take X = B d (0, ρ), the closed ball of R d centered at the origin 0 with radius ρ. Let µ 0 be the uniform measure on the sphere S d (0, ρ) (the boundary of B d (0, ρ)). Then, V µ0 is proportional to the identity matrix I d , and trace

so that µ 0 is ψ d -optimal from (4.4). Let µ d be the measure that allocates mass 1/(d + 1) at each vertex of a d regular simplex having its d + 1 vertices on S d (0, ρ), with squared volume ρ 2d (d +

Appendix

Shift-invariance and positive homogeneity Denote by M the set of probability measures defined on the Borel subsets of X , a compact subset of R d . For any µ ∈ M , any θ ∈ R d and any λ ∈ R + , respectively denote by T -θ [µ] and H λ -1 [µ] the measures defined by:

The variance is the only concave central moment For q = 2, the q-th central moment ∆ q (µ) =

x -E µ q µ(dx) is shift-invariant and homogeneous of degree q, but it is not concave on M (X ). Indeed, consider for instance the two-point probability measures 201 q-1 -202q + 405 201 q-1 -101q + 102


Christina Unger
email: cunger@cit-ec.uni-bielefeld.decimiano@cit-ec.uni-bielefeld.deswalter@techfak.uni-bielefeld.de

Corina Forascu

Vanessa Lopez
email: vanlopez@ie.ibm.com

Axel-Cyrille Ngonga Ngomo

Elena Cabrio
email: elena.cabrio@inria.fr

Philipp Cimiano

Sebastian Walter

Question Answering over Linked Data (QALD-4)

come

Introduction

With the increasing amount of semantic data available on the web there is a strong need for systems that allow common web users to access this body of knowledge. Especially question answering systems have received wide attention, as they allow users to express arbitrarily complex information needs in an easy and intuitive fashion (for an overview see [START_REF] Lopez | Is question answering fit for the semantic web?: A survey[END_REF]). The key challenge lies in translating the users' information needs into a form such that they can be evaluated using standard Semantic Web query processing and inferencing techniques. Over the past years, a range of approaches have been developed to address this challenge, showing significant advances towards answering natural language questions with respect to large, heterogeneous sets of structured data. However, only few systems yet address the fact that the structured data available nowadays is distributed among a large collection of interconnected datasets, and that answers to questions can often only be provided if information from several sources are combined. In addition, a lot of information is still available only in textual form, both on the web and in the form of labels and abstracts in linked data sources. Therefore approaches are needed that can not only deal with the specific character of structured data but also with finding information in several sources, processing both structured and unstructured information, and combining such gathered information into one answer.

The main objective of the open challenge on question answering over linked data 6 [3] (QALD) is to provide up-to-date, demanding benchmarks that establishe a standard against which question answering systems over structured data can be evaluated and compared. QALD-4 is the fourth instalment of the QALD open challenge, comprising three tasks: multilingual question answering, biomedical question answering over interlinked data, and hybrid question answering.

Task description

Task 1: Multilingual question answering

Task 1 is the core task of QALD and aims at all question answering systems that mediate between a user, expressing his or her information need in natural language, and semantic data. Given the English DBpedia 3.9 dataset7 and a natural language question or set of keywords in one of seven languages (English, Spanish, German, Italian, French, Dutch, Romanian), the participating systems had to return either the correct answers, or a SPARQL query that retrieves these answers.

To get acquainted with the dataset and possible questions, a set of 200 training questions was provided. These questions were compiled from the QALD-3 training and test questions, slightly modified in order to account for changes in the DBpedia dataset. Later, systems were evaluated on 50 different test questions. These questions were mainly devised by the challenge organizers.

All training questions were manually annotated with keywords, corresponding SPARQL queries and with answers retrieved from the provided SPARQL endpoint. Annotations were provided in an XML format. Each of the questions specifies an ID for the question together with a range of other attributes explained below, the natural language string of the question in the seven languages, keywords in the same languages, a corresponding SPARQL query, as well as the answers this query returns. Along with a unique ID, the following attributes were specified for each question:

answertype specifies the answer type, which can be one the following: resource (one or many resources, for which the URI is provided), string (a string value), number (a numerical value such as 47 or 1.8), date (a date provided in the format YYYY-MM-DD, e.g. 1983-11-02), boolean (either true or false). aggregation indicates whether any operations beyond triple pattern matching are required to answer the question (e.g., counting, filters, ordering). onlydbo is given only for DBpedia questions and reports whether the query relies solely on concepts from the DBpedia ontology.

Here is an example from the training set:

< question id ="36" answertype =" resource " aggregation =" false " onlydbo =" false " > < string lang =" en " > Through which countries does the Yenisei river flow ? </ string > < string lang =" de " > Durch welche Länder fließt der Yenisei ? </ string > < string lang =" es " > ¿Por qué países fluye el río Yenisei ? </ string > ... Of the 200 training questions, 38 questions require aggregation and 74 questions require namespaces other than from the DBpedia ontology. Of the 50 test questions, 15 questions require aggregation and 10 cannot be answered with the DBpedia ontology only. As an additional challenge, 12 training and 2 test questions are out of scope, i.e. they cannot be answered with respect to the dataset.

<

Task 2: Biomedical question answering over interlinked data

Also for the life sciences, linked data plays a bigger and bigger role. Already a tenth of the Linked Open Data cloud8 consists of biomedical datasets. Especially biomedical data is distributed among a large collection of interconnected datasets, and answers to questions can often only be provided if information from several sources are combined. Task 2 therefore focuses on interlinked data. Given the following three biomedical datasets and a natural language question or set of keywords in English, the participating systems had to return either the correct answers or a SPARQL query that retrieves the answers.

-SIDER, describing drugs and their side effects http://sideeffects.embl.de -Diseasome, encompassing description of diseases and genetic disorders http://wifo5-03.informatik.uni-mannheim.de/diseasome/ -Drugbank, describing FDA-approved active compounds of medication http://www.drugbank.ca

The training question set comprised 25 questions over those datasets. All training questions were provided in an XML format similar to the one used for Task 1. Since the focus of the task is on interlinked data, most of the questions require the integration of information from at least two of those datasets. Here is an example query (ommitting prefix definitions), representing the question What are the side effects of drugs used for Tuberculosis? Note that the drugs used for Tuberculosis are retrieved from Diseasome, and their side effects are retrieved from SIDER. The link between the relevant resources in these datasets (bound to ?v2 and ?v3) is established using the OWL property sameAs.

Later, participating systems were evaluated on 25 similar test questions.

Task 3: Hybrid question answering

A lot of information is still available only in textual form, both on the web and in the form of labels and abstracts in linked data sources. Task 3 therefore focuses on the integration of both structured and unstructured information in order to gather answers. Given English DBpedia 3.9, containing both RDF data and free text available in the DBpedia abstracts, and a natural language question or keywords, participating systems had to retrieve the correct answer(s).

A set of 25 training questions was provided in an XML format that is very similar to the one used for Tasks 1 and 2. However, for this task, not only the RDF triples are relevant, but also the English abstracts, related to a resource by means of the property abstract.

All questions are annotated with a pseudo query and the correct answers. The pseudo query is like an RDF query but can contain free text as subject, property, or object of a triple. This free text is marked as text:"...". Here is an example pseudo query for the question Give me the currencies of all G8 countries: PREFIX dbo : < http :// dbpedia . org / ontology / > SELECT DISTINCT ? uri WHERE { ? x text :" member of " text :" G8 " . ? x dbo : currency ? uri . } This pseudo query contains two triples: One is an RDF triple retrieving the currency of a country, which is information that is only available as RDF data, not in the abstracts. And the other contains free text reducing the list of countries to those that are a member of the G8, which is information that is contained only in the abstracts, not in the RDF data. For example, the abstract for Canada contains the following sentence:

Canada is a recognized middle power and a member of many international institutions , including the G7 , G8 , G20 , NATO , NAFTA , OECD , WTO , Commonwealth of Nations , Francophonie , OAS , APEC , and the United Nations .

Evaluation measures

The results submitted by participating systems were automatically compared to the gold standard results and evaluated with respect to precision and recall. For each question q, precision, recall and F-measure were computed as follows:

Recall(q) = number of correct system answers for q number of gold standard answers for q Precision(q) = number of correct system answers for q number of system answers for q F-Measure(q) = 2 * Precision(q) × Recall(q) Precision(q) + Recall(q)

On the basis of these measures, overall precision and recall values as well as an overall F-measure value were computed as the average mean of the precision, recall and F-measure values for all questions. In the results reported below, precision, recall and F-measure values refer to the averaged values.

Participating systems

Eight teams participated in QALD-4: four teams from Europe (one from France, one from Germany and two from Romania) and four teams from Asia (three from China and one from South Korea). Six participants took part in Task 1, three participants took part in Task 2, and there was one participant for Task 3 that later withdrew his submission. In the following, we give some details on those participating systems that are also described in working note papers.

Xser [START_REF] Xu | Answering natural language questions via phrasal semantic parsing[END_REF] takes as input a natural language question in English, and retrieves an answer in two steps. First the user query is linguistically analyzed in order to detect predicate argument structures through a semantic parser. Second the query is instantiated with respect to the knowledge base. Besides the DAG dependency parsing it relies on a structured prediction approach implemented using a Collins-style hidden perceptron. The system requires training data but among all participants obtained the highest precision and recall values.

gAnswer [START_REF] Zou | Natural langauge question answering over RDF -a graph data driven approach[END_REF] is a graph-driven question answering system that processes questions in two stages. First, based on the dependency parse of the question, a graph is build that represents the semantic structure of the question. Second, this graph is matched with subgraphs in the RDF dataset. Disambiguation takes place when evaluating subgraph matches. The system achieves real-time performance, requiring an average of 972 miliseconds to answer a question.

CASIA [START_REF] Shizhu | CASIA@V2: A MLN-based question answering system over linked data[END_REF] proposes an algorithm based on Markov Logic Networks for learning a joint model for detecting phrases, mapping phrases to semantic items, and grouping semantic items into a graph. As a result, each step can be subject to global optimization. The system does not yet process questions which contain numbers and aggregation operations (such as filters, comparisons, or ordering), but shows very promising results on non-aggregation questions. It makes use of the Stanford Named Entity Recognizer, the PATTY and ReVerb resources, as well as thebeast tool9 for weight learning and MAP inferencing.

Intui3 [START_REF] Dima | Answering natural language questions with Intui3[END_REF] accepts as input a natural language question and constructs its interpretation using syntactic and semantic cues in the question and a target triple store. First, the question is syntactically analyzed and chunked, and the named entities are identified. Then each chunk receives one or more interpretation depending on its type and on additional semantic and syntactic information available for that chunk. The interpretation of the question is then constructed by combining the interpretations assigned to each chunk, based on a set of combination rules that are attached to each type of interpretation. Finally, the question interpretation is mapped to a corresponding SPARQL query, which is then run against a SPARQL endpoint to retrieve the answers.

ISOFT [START_REF] Park | ISOFT at QALD-4: Semantic similarity-based question answering system over linked data[END_REF] follows a template-based approach for transforming natural language questions into SPARQL queries. Based on a linguistic analysis of the input question, query templates and slots are determined, which are then filled by searching for appropriate concepts in the knowledge base, based on string similarity and Explicit Semantic Analysis.

The Faculty of Computer Science at Alexandru Ioan Cuza University of Iasi, Romania, participated with two systems (RO FII), one tackling question answering over DBpedia and one tackling interlinked biomedical datasets. 10 The former builds on Quepy 11 , a Python tool for transforming natural language questions into SPARQL or MQL queries. The latter comprises three components, based on Service Oriented Architecture principles: a text annotator that receives the question in plain text and returns a list of compound words annotated with POS tags and lemmas (using Standford Core NLP), the triple builder that builds a list of triples given a list of keywords and URIs (currently assembled manu-ally), and a query builder that builds the final SPARQL query on the basis of the list of annotated words and the list of triples.

GFMed [START_REF] Marginean | GFMed: Question answering over biomedical linked data with Grammatical Framework[END_REF] follows a controlled natural language approach for biomedical question answering. It builds on a Grammatical Framework12 (GF) grammar for the biomedical datasets DrugBank, Diseasome, and SIDER. GF is a specialpurpose programming language for writing multilingual grammars. For GFMed, an abstract syntax for the biomedical domain, spanning the concepts of the three datasets, as well as two concrete syntaxes that provide linearizations of those concepts, one for English and one for SPARQL, were created manually. In addition, a lexicon for both languages that covers all resource names was automatically constructed based on their labels. The resulting grammar allows to transform English questions into SPARQL queries by parsing the English input, yielding an abstract syntax representation that can then be linearized using the SPARQL concrete syntax. The approach can deal with complex questions and achieves a very high precision, but as any controlled language its coverage is limited, especially it does not easily scale to other domains.

POMELO [START_REF] Thierry Hamon | Description of the POMELO system for the task 2 of QALD-2014[END_REF] POMELO operates (in contrast to most other approaches) on frames. First, the RDF dataset is converted to frames: The predicates of the RDF triples are mapped to frame predicates while the subjects and objects are mapped to core frame elements. Each question is transformed to a SPARQL query using a four-step approach: First, the query is annotated with semantic and linguistic information using the converted resources. For example, numbers and resources from different datasets are tagged as such. Thereafter, in the question abstraction step, argument and predicate descriptions are used to generate a query template. This template is completed by using owl:sameAs and used to construct a SPARQL query skeleton, which is finally used to generate a final SPARQL query.

Results

Tables 1 and2 report on the results obtained by the participating systems on Tasks 1 and 2, respectively. The column proc. states for how many of the questions the system provided an answer, right specifies how many of these questions were answered with an F-measure of 1, and part. specifies how many of the questions were answered with an F-measure strictly between 0 and 1.

The results in Task 1 are comparable to results achieved in earlier challenges, with an average F-measure of 0.33, showing that the level of complexity of the questions is still very demanding. But what has changed with respect to earlier challenges is that question answering systems have become more versatile: There is no particular type of questions anymore that systems struggle with, rather most of them can handle all answer types as well as aggregation. The biggest problem, however, remains the matching of natural language questions to correct vocabulary elements. For example, the questions that all systems struggled with are surprisingly simple with respect to the linguistic structure and the structure of the target query:

-How deep is Lake Placid? SELECT ?n WHERE { res:Lake Placid (Texas) dbo:depth ?n . } -Which spaceflights were launched from Baikonur?

SELECT ?uri WHERE { ?uri dbo:launchPad res:Baikonur Cosmodrome . } 6 Future perspectives QALD-4, the fourth edition of the QALD challenge, has attracted a higher number of participants than previous editions, showing that there is a growing interest among researchers to provide end users with an intuitive and easy-to-use access to the huge amount of data present on the Semantic Web. Although one of the aspects of Task 1 was multilinguality, all participating systems worked on English data only. This shows that the multilingual scenario is not yet broadly addressed, although it is starting to attract attention. Similarly, research teams start to look at hybrid question answering, although Task 3 did not have participating systems yet.

In future challenges, we want to emphasize further aspects of question answering over linked data, such as including statistical question answering (e.g. How much money was spent for public transport in Berlin in 2014?), introducing spoken language in addition to written language (an aspect that is interesting especially for search engines) as well as dialogue-based interaction into the challenge, allowing the system to ask for feedback or clarification, as well as the user to refer to previous questions and answers, thus moving to question answering systems that can exploit the previous interaction context in interpreting new questions.

Table 1 .

 1 Results for Task 1: Multilingual question answering over DBpedia Total Proc. Right Part. Recall Precision F-measure

	Xser	50	40	34	6	0.71	0.72	0.72
	gAnswer 50	25	16	4	0.37	0.37	0.37
	CASIA	50	26	15	4	0.40	0.32	0.36
	Intui3	50	33	10	4	0.25	0.23	0.24
	ISOFT	50	28	10	3	0.26	0.21	0.23
	RO FII 50	50	6	0	0.12	0.12	0.12

Table 2 .

 2 Results for Task 2: Biomedical question answering over interlinked data

		Total Proc. Right Part. Recall Precision F-measure
	GFMed	25	25	24	1	0.99	1.0	0.99
	POMELO 25	25	19	3	0.87	0.82	0.85
	RO FII	25	25	4	0	0.16	0.16	0.16

http://www.sc.cit-ec.uni-bielefeld.de/qald

http://dbpedia.org

http://lod-cloud.net

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

The former was built by Andrei Micu, the latter was built by Claudiu Epure, both supervised by Adrian Iftene.

http://quepy.machinalis.com

http://www.grammaticalframework.org


Elena Cabrio

Vivek Sachidananda

Raphael Troncy

Boosting QAKiS with multimedia answer visualization

We present an extension of QAKiS, a system for Question Answering over DBpedia language specific chapters, that allows to complement textual answers with multimedia content from the linked data, to provide a richer and more complete answer to the user. For the demo, English, French and German DBpedia chapters are the RDF data sets to be queried using a natural language interface. Beside the textual answer, QAKiS output embeds i) pictures from Wikipedia Infoboxes, ii) OpenStreetMap, to visualize maps for questions asking about a place, and iii) YouTube, to visualize pertinent videos (e.g. movie trailers).

Multimedia Question Answering

The goal of a Question Answering (QA) system is to return precise answers to users' natural language questions, extracting information from both documentary text and advanced media content. The research area on QA, and especially on scaling up QA to the linked data, is a wide and emergent research area that still needs an in-depth study to benefit from the rich linked data resources on the web. Up to now, QA research has largely focused on text, mainly targeting factual and list questions (for an overview on ontology-based Question Answering systems, see [START_REF] Lopez | Is question answering fit for the semantic web?: A survey[END_REF]). 1 However, a huge amount of increasingly multimedia contents are now available on the web on almost any topic, and it would be extremely interesting to consider them in the QA scenario, in which the best answers may be a combination of text and other media answers [START_REF] Hong | Multimedia question answering[END_REF].

This demonstration presents an extension of QAKiS [START_REF] Cabrio | QAKiS: an open domain qa system based on relational patterns[END_REF], a Question Answering system over DBpedia [START_REF] Bizer | DBpedia -a crystallization point for the web of data[END_REF], that allows to exploit the structured data and metadata describing multimedia content on the linked data to provide a richer and more complete answer to the user, combining textual information with other media content. A first step in this direction consists in determining the best sources and media (image, audio, video, or a hybrid) to answer a query. For this reason, we have carried out an analysis of the questions provided by the Question Answering over Linked Data (QALD) challenge, and we have categorized them according to the possible improved multimedia answer visualization. Then, we have extended QAKiS output to include i) pictures from Wikipedia Infoboxes, for instance to visualize images of people or places (for questions as Who is the President of the United States? ); ii) OpenStreetMap, to visualize maps for questions asking about a place (e.g. What is the largest city in Australia? ) and iii) YouTube, to visualize videos related to the answer (e.g. a trailer of a movie, for questions like Which films starring Clint Eastwood did he direct himself ? ).

2 Extending QAKiS to visualize multimedia answers QAKiS system description. QAKiS (Question Answering wiKiFrameworkbased System) [START_REF] Cabrio | QAKiS: an open domain qa system based on relational patterns[END_REF] addresses the task of QA over structured knowledge-bases (e.g. DBpedia) [START_REF] Cabrio | Querying multilingual dbpedia with qakis[END_REF], where the relevant information is expressed also in unstructured forms (e.g. Wikipedia pages). It implements a relation-based match for question interpretation, to convert the user question into a query language (e.g. SPARQL). More specifically, it makes use of relational patterns (automatically extracted from Wikipedia and collected in the WikiFramework repository [START_REF] Cabrio | QAKiS: an open domain qa system based on relational patterns[END_REF]), that capture different ways to express a certain relation in a given language. QAKiS is composed of four main modules (Fig. 1): i) the query generator takes the user question as input, generates the typed questions, and then generates the SPARQL queries from the retrieved patterns; ii) the pattern matcher takes as input a typed question, and retrieves the patterns (among those in the repository) matching it with the highest similarity; iii) the sparql package handles the queries to DBpedia; and iv) a Named Entity (NE) Recognizer. The actual version of QAKiS targets questions containing a Named Entity related to the answer through one property of the ontology, as Which river does the Brooklyn Bridge cross?. Such questions match a single pattern (i.e. one relation).

Before running the pattern matcher component, the question target is identified combining the output of Stanford NE Recognizer, with a set of strategies that compare it with the instances labels in the DBpedia ontology. Then a typed question is generated by replacing the question keywords (e.g. who, where) and the NE by the types and supertypes. A Word Overlap algorithm is then applied to match such typed questions with the patterns for each relation. A similarity score is provided for each match: the highest represents the most likely relation. A set of patterns is retrieved by the pattern matcher component for each typed question, and sorted by decreasing matching score. For each of them, a set of SPARQL queries is generated and then sent to the endpoints of language specific DBpedia chapters that the user has selected. If no results are found the next pattern is considered, and so on. Currently, the results of a SPARQL query on the different language specific DBpedia chapters are aggregated by the set union.

QAKiS multimedia. While providing the textual answer to the user, the multimedia answer generator module queries again DBpedia to retrieve additional information about the entity contained in the answer. To display the images, it extracts the properties foaf:depiction and dbpedia-owl:thumbnail, and their value (i.e. the image) is shown as output. To display the maps (e.g. when the answer is a place), it retrieves the GPS co-ordinates from DBpedia (properties geo:geometry, geo:lat and geo:long), and it injects them dynamically into OpenStreetMap2 to display the map. Given the fact that DBpedia data can be inconsistent or incomplete, we define a set of heuristics to extract the co-ordinates: in case there are several values for the latitude and longitude, i) we give priorities to negative values (indicating the southern hemisphere3 ), and ii) we take the value with the highest number of decimal values, assuming it is the most precise. Finally, to embed YouTube4 videos, first the Freebase5 ID of the entity is retrieved through the DBpedia property owl:sameAs. Then, such ID is used via YouTube search API (v3) (i.e. it is included in the embed code style <iframe>, that allows users to view the embedded video in either Flash or HTML5 players, depending on their viewing environment and preferences). Moreover, since we want to have pertinent videos (i.e. showing content related to the answer in the context of the question only), we remove stopwords from the input question, and we send the remaining words as search parameters. For instance, for the question Give me the actors starring in Batman Begins, the words "actors", "starring", "Batman Begins" are concatenated and used as search parameters, so that the videos extracted for such actors are connected to the topic of the question (i.e. the actors in their respective roles in Batman Begins).

QAKiS demonstrator

Figure 2 shows QAKiS demo interface (http://qakis.org/). The user can select the DBpedia chapter she wants to query besides English (that must be selected as it is needed for NER), i.e. French or German DBpedia. Then the user can either write a question or select among a list of examples, and click on Get Answers!. As output, in the tab Results QAKiS provides: i) the textual answer (linked to its DBpedia page), ii) the DBpedia source, iii) the associate image in Wikipedia Infobox, iv) a more details button. Clicking on that button, both the entity abstract in Wikipedia, the map and the retrieved videos (if pertinent) are shown. In the tab Technical details, QAKiS provides i) the user question (the recognized NE is linked to its DBpedia page), ii) the generated typed question, iii) the pattern matched, and iv) the SPARQL query sent to the DBpedia SPARQL endpoint. The demo we will present follows these stages for a variety of queries, described in the next section.

Queries and datasets for demonstration

In order to determine the best sources and media (image, audio, video, or a hybrid) to answer a query, we have carried out an analysis on a subset of the questions provided by the QALD-3 challenge. 6 The goal was to categorize them according to the possible improved multimedia answer visualization, and to extract some heuristics to be exploited by QAKiS to provide the most complete answer to a certain question. In this analysis, we discarded the questions for which no additional multimedia content would be pertinent, e.g. questions whose answer is a number (e.g. How many students does the Free University in Amsterdam have? ), or boolean questions (e.g. Did Tesla win a nobel prize in physics? ). In future work we could provide multimedia content on the entity in the question, but in the current work we are focusing on boosting the answer visualization only. Table 1 shows the categories of multimedia content for answer visualization on which we are focusing, together with an example of question for which such kind of multimedia content would be appropriate.

Multimedia Example question

Picture

Give me all female Russian astronauts. Picture + video Give me all movies directed by Francis Ford Coppola. Picture + map In which country does the Nile start? Map + barchart Give me all world heritage sites designated within the past 5 years.

Statcharts

What is the total amount of men and women serving in the FDNY?

Timelines

When was Alberta admitted as province?

Table 1. QALD-3 questions improved answer visualization

Future perspectives

The work we present in this demonstration is ongoing, and represents a first step in the direction of dealing with the huge potential amount of available multimedia data. As a short-term improvement, we are planning to add other sources of images. For instance, Ookaboo RDF Data contains pictures with topics derived from Freebase and DBpedia, and can therefore be coupled with the output of QAKiS, to provide additional images describing the answer. For other available datasets, metadata could be RDF-ized (e.g. MIRFLICKR, IMAGENET 7 ) and the interlinking of such structured sources with DBpedia can be explored to provide to the user semantically enriched multimedia presentations. As a longterm improvement, we plan to address types of questions that have been less investigated in the literature (e.g. how to and why questions), and for which multimedia answers seem to be more intuitive and appropriate [START_REF] Hong | Multimedia question answering[END_REF]. Moreover, a natural language answer should be generated and presented to the user in a narrative form for an easy consumption, supported by multimedia elements [START_REF] Vocht | Discovering meaningful connections between resources in the web of data[END_REF].

Fig. 1 .

 1 Fig.1. QAKiS workflow[START_REF] Cabrio | QAKiS: an open domain qa system based on relational patterns[END_REF]

Fig. 2 .

 2 Fig. 2. QAKiS demo interface

See the Question Answering over Linked Data (QALD) challenges http:// greententacle.techfak.uni-bielefeld.de/ ~cunger/qald/

www.openstreetmap.org

We verified that when both a positive and a negative value are proposed, the negative is the correct one (the letter S, i.e. South, is not correctly processed.)

www.youtube.com/

www.freebase.com

http://doi.org/10.4119/unibi/citec.2013.6

Acknowledgements. The work of E. Cabrio is funded by the ANR-11-LABX-0031-01 Program. We thank Amine Hallili for contributing to images extraction.


Amine Hallili
email: amine.hallili@inria.fr

Elena Cabrio
email: elena.cabrio@inria.fr

Catherine Faron Zucker

QALM: a Benchmark for Question Answering over Linked Merchant Websites Data

This paper presents a benchmark for training and evaluating Question Answering Systems aiming at mediating between a user, expressing his or her information needs in natural language, and semantic data in the commercial domain of the mobile phones industry. We first describe the RDF dataset we extracted through the APIs of merchant websites, and the schemas on which it relies. We then present the methodology we applied to create a set of natural language questions expressing possible user needs in the above mentioned domain. Such question set has then been further annotated both with the corresponding SPARQL queries, and with the correct answers retrieved from the dataset.

Introduction

The evolution of the e-commerce domain, especially the Business To Client (B2C), has encouraged the implementation and the use of dedicated applications (e.g. Question Answering Systems) trying to provide end-users with a better experience. At the same time, the user's needs are getting more and more complex and specific, especially when it comes to commercial products whose questions concern more often their technical aspects (e.g. price, color, seller, etc.). Several systems are proposing solutions to answer to these needs, but many challenges have not been overcome yet, leaving room for improvement. For instance, federating several commercial knowledge bases in one knowledge base has not been accomplished yet. Also, understanding and interpreting complex natural language questions also known as n-relation questions seems to be one of the ambitious topics that systems are currently trying to figure out.

In this paper we present a benchmark for training and evaluating Question Answering (QA) Systems aiming at mediating between a user, expressing his or her information need in natural language, and semantic data in the commercial domain of the mobile phone industry. We first describe the RDF dataset that we have extracted through the APIs of merchant sites, and the schemas on which it relies. We then present the methodology we applied to create a set of natural language questions expressing possible user needs in the above mentioned domain.

Such question set has then be further annotated both with the corresponding SPARQL queries, and with the correct answers retrieved from the dataset.

A Merchant Sites Dataset for the Mobile Phones Industry

This section describes the QALM (Question Answering over Linked Merchant websites) ontology (Section 2.1), and the RDF dataset (Section 2.2) we built by extracting a sample of data from a set of commercial websites.

QALM Ontology

The QALM RDF dataset relies on two ontologies: the Merchant Site Ontology (MSO) and the Phone Ontology (PO). Together they build up the QALM Ontology.4 MSO models general concepts of merchant websites, and it is aligned to the commercial part of the Schema.org ontology. MSO is composed of 5 classes: mso:Product, mso:Seller, mso:Organization, mso:Store, mso:ParcelDelivery, and of 29 properties (e.g. mso:price, mso:url, mso:location, mso:seller) declared as subclasses and subproperties of Schema.org classes and properties. We added to them multilingual labels (both in English and in French), that can be exploited by QA systems in particular for property identification in the question interpretation step. We relied on WordNet synonyms [START_REF] Fellbaum | WordNet: An Electronic Lexical Database[END_REF] to extract as much labels as possible. For example, the property mso:price has the following English labels: "price", "cost", "value", "tariff", "amount", and the following French labels: "prix", "coût", "coûter", "valoir", "tarif", "s'élever". PO is a domain ontology modeling concepts specific to the phone industry. It is composed of 7 classes (e.g. po:Phone, po:Accessory) which are declared as subclasses of mso:Product, and of 35 properties (e.g. po:handsetType, po:operatingSystem, po:phoneStyle).

QALM RDF Dataset

Our final goal is to build a unified RDF dataset integrating commercial product descriptions from various e-commerce websites. In order to achieve this goal, we analyze the web services of the e-commerce websites regardless of their type (either SOAP or REST). To feed our dataset, we create a mapping between the remote calls to the web services and the ontology properties, that we store in a separate file for reuse. In particular, we built the QALM RDF dataset by extracting data from eBay 5 and BestBuy 6 commercial websites through BestBuy Web service and eBay API. The extracted raw data is transformed into RDF triples by applying the above described mapping between the QALM ontology and the API/web service. For instance, the method getPrice() in the eBay API is mapped to the property mso:price in the QALM ontology. Currently, the QALM dataset comprises 500000 product descriptions and up to 15 millions triples extracted from eBay and BestBuy. 7

QALM Question Set

In order to train and to evaluate a QA system mediating between a user and semantic data in the QALM dataset, a set of questions representing users requests in the phone industry domain is required. Up to our knowledge, the only available standard sets of questions to evaluate QA systems over linked data are the ones released by the organizers of the QALD (Question Answering over Linked Data) challenges.8 However such questions are over the English DBpedia dataset9 , and therefore cover several topics. For this reason, we created a set of natural language questions for the specific commercial domain of the phone industry, following the guidelines described by the QALD organizers for the creation of their question sets [START_REF] Cimiano | Multilingual question answering over linked data (qald-3): Lab overview[END_REF]. More specifically, these questions were created by 12 external people (students and researchers in other groups) with no background in question answering, in order to avoid a bias towards a particular approach. To accomplish the task of question creation, each person was given i) the list of the product types present in the QALM dataset (mainly composed of IT products as phones and accessories); ii) the list of the properties of the QALM ontology presented as product features in which they could be interested in; and they were asked to produce i) both 1-relation and 2-relation questions, and ii) at least 5 questions each. The questions were designed to present potential user questions and to include a wide range of challenges such as lexical ambiguities and complex syntactical structures. Such questions were then annotated with the corresponding SPARQL queries, and the correct answers retrieved from the dataset, in order to consider them as a reliable goldstandard for our benchmark.

The final question set comprises 70 questions; it is divided into a training set 10 and a test set of respectively 40 and 30 questions. Annotations are provided in XML format, and according to QALD guidelines, the following attributes are specified for each question along with its ID: aggregation (indicates whether any operation beyond triple pattern matching is required to answer the question, e.g., counting, filtering, ordering), answertype (gives the answer type: resource, string, boolean, double, date). We also added the attribute relations, to indicate whether the question is connected to its answer through one or more properties of the ontology (values: 1, n). Finally, for each question the corresponding SPARQL query is provided, as well as the answers this query returns. Examples 1 and 2 show some questions from the collected question set, connected to their answers through 1 property or more than 1 property of the ontology, respectively. In particular, questions 14 and 50 from Example 2 require also to carry out some reasoning on the results, in order to rank them and to produce the correct answer.

Example 1. 1-relation questions.

id=36. Give me the manufacturers who supply on-ear headphones. id=52. What colors are available for the Samsung Galaxy 5 ? id=61. Which products of Alcatel are available online?

Example 2. n-relations questions.

id=14. Which cell phone case (any manufacturer) has the most ratings? id=50. What is the highest camera resolution of phones manufactured by Motorola? id=58. I would like to know in which stores I can buy Apple phones.

Conclusions and Ongoing Work

This paper presented a benchmark to train and test QA systems, composed of i) the QALM ontologies; ii) the QALM RDF dataset of product descriptions extracted from eBay and BestBuy; and iii) the QALM Question Set, containing 70 natural language questions in the commercial domain of phones and accessories.

As for future work, we will consider aligning the QALM ontology to the GoodRelations ontology to fully cover the commercial domain, and to benefit from the semantics captured in this ontology. We also consider improving the QALM RDF dataset by i) extracting RDF data from additional commercial websites that provide web services or APIs; and ii) directly extracting RDF data in the Schema.org ontology from commercial websites whose pages are automatically generated with Schema.org markup (e.g. Magento, OSCommerce, Genesis2.0, Prestashop), to extend the number of addressed commercial websites.

In parallel, we are currently developing the SynchroBot QA system [START_REF] Hallili | Toward an ontology-based chatbot endowed with natural language processing and generation[END_REF], an ontology-based chatbot for the e-commerce domain. We will evaluate it by using the proposed QALM benchmark.

Available at www.i3s.unice.fr/qalm/ontology

http://www.ebay.com/

http://www.bestbuy.com/

Available at www.i3s.unice.fr/QALM/qalm.rdf

http://greententacle.techfak.uni-bielefeld.de/ ~cunger/qald/

http://dbpedia.org

Available at www.i3s.unice.fr/QALM/training_questions.xml

Acknowledgements

We thank Amazon, eBay and BestBuy for contributing to this work by sharing with us public data about their commercial products. The work of E. Cabrio was funded by the French Government through the ANR-11-LABX-0031-01 program.