Clément Levrard

MARGIN CONDITIONS FOR VECTOR QUANTIZATION

Keywords: localization, fast rates, margin conditions 1

come

1. Introduction. Quantization, also called lossy data compression in information theory, is the problem of replacing a probability distribution with an efficient and compact representation, that is a finite set of points. To be more precise, let P denote a probability distribution over R d and k a positive integer. A so-called k-quantizer Q is a map from R d to R d , whose image set is made of exactly k points, that is Q(R d ) = k. For such a quantizer, every image point c i ∈ Q R d is called a code point, and the vector composed of the code points (c 1 , . . . , c k ) is called a codebook. By considering the preimages of its code points, a quantizer Q partitions the Euclidean space R d into k groups, and assigns each group a representative. General references on the subject are to be found in [START_REF] Graf | Foundations of quantization for probability distributions[END_REF], [START_REF] Gersho | Vector quantization and signal compression[END_REF] and [START_REF] Linder | Learning-theoretic methods in vector quantization[END_REF] among others.

The quantization theory was originally developed as a way to answer signal compression issues in the late 40's (see, e.g., [START_REF] Gersho | Vector quantization and signal compression[END_REF]). However, unsupervised classification is also in the scope of its application. Isolating meaningful groups from a cloud of data is a topic of interest in many fields, from social science to biology. Classifying points into dissimilar groups of similar items is as more interesting as the amount of accessible data is large. In many cases data need to be preprocessed through a quantization algorithm in order to be exploited.

If the distribution P has a finite second moment, the performance of a quantizer Q is measured by the risk, or distortion R(Q) := P x -Q(x) 2 , where P f means integration of the function f with respect to P . The choice of the Euclidean squared norm is convenient, since it takes advantages of the Euclidean space structure of R d . Nevertheless, it is worth pointing out that several authors deal with more general distortion functions. For further information on this topic, the interested reader is referred to [START_REF] Graf | Foundations of quantization for probability distributions[END_REF] or [START_REF] Fischer | Quantization and clustering with Bregman divergences[END_REF].

In order to minimize the distortion introduced above, it is clear that only quantizers of the type x → arg min c 1 ,...,c k xc i 2 are to be considered. Such quantizers are called nearest-neighbor quantizers. With a slight abuse of notation, R(c) will denote the risk of the nearest-neighbor quantizer associated with a codebook c.

Provided that P x 2 < ∞, there exist optimal codebooks minimizing the risk R (see, e.g., Lemma 8 in [START_REF] Pollard | Quantization and the method of k -means[END_REF] or Theorem 4.12 in [START_REF] Graf | Foundations of quantization for probability distributions[END_REF]). The aim is to design a codebook ĉn , according to a n-sample drawn from P , whose distortion is as close as possible to the optimal distortion R(c * ), where c * denotes an optimal codebook.

To solve this problem, most approaches to date attempt to implement the principle of empirical risk minimization in the vector quantization context. Let X 1 , . . . , X n denote an independent and identically distributed sample with distribution P . According to this principle, good code points can be found by searching for ones that minimize the empirical distortion over the training data, defined by

Rn (c) := 1 n n i=1 X i -Q(X i ) 2 = 1 n n i=1 min j=1,...,k X i -c j 2 .
If the training data represents the source well, then ĉn will hopefully also perform near optimally on the real source, that is

ℓ(ĉ n , c * ) = R(ĉ n )-R(c * ) ≈ 0.
The problem of quantifying how good empirically designed codebooks are, compared to the truly optimal ones, has been extensively studied, as for instance in [START_REF] Linder | Learning-theoretic methods in vector quantization[END_REF].

It has been proved in [START_REF] Linder | Rates of convergence in the source coding theorem, in empirical quantizer design, and in universal lossy source coding[END_REF] that Eℓ(ĉ n , c * ) = O(1/ √ n), provided that P has a finite second moment. However, this upper bound can be tightened whenever the source distribution satisfies additional assumptions.

For the special case of finitely supported distributions, it is shown in [START_REF] Antos | Individual convergence rates in empirical vector quantizer design[END_REF] that Eℓ(ĉ n , c * ) = O(1/n). There are much more results in the case where P is assumed to have a density.

In fact, different sets of assumptions have been introduced in [START_REF] Antos | Individual convergence rates in empirical vector quantizer design[END_REF], [START_REF] Pollard | A central limit theorem for k-means clustering[END_REF] or [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF], for the loss Eℓ(ĉ n , c * ) to decrease at the rate O(1/n) in the density case. As shown in [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF], these different sets of assumptions turn out to be equivalent to a technical condition, similar to that used in [START_REF] Massart | Risk bounds for statistical learning[END_REF] to derive fast rates of convergence in the statistical learning framework.

Thus, a question of interest is to know whether some margin type conditions can be derived for the source distribution to satisfy the technical condition mentioned above, as has been done in the statistical learning framework in [START_REF] Mammen | Smooth discrimination analysis[END_REF]. Theorem 3.2 of [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF] offers a partial answer, proving that a sufficient condition is that P is divided into k well separated areas. However, this condition is not fully satisfactory, since it consists in a bound on the density located at the d -1 dimensional region between optimal code cells, whereas margin conditions in the statistical learning framework are bounds on the weight with respect to P of the ε-neighborhood of the critical value 1/2 for the regression function.

Next, the scope of Theorem 3.2 of [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF] is constrained to distributions with continuous densities, whereas margin conditions in [START_REF] Mammen | Smooth discrimination analysis[END_REF] do not require regularity of the regression function.

This paper addresses both these issues, providing a condition which can clearly be thought of as a margin condition in the quantization framework, under which the loss Eℓ(ĉ n , c * ) = O(1/n).

Moreover, some explicit oracle inequality is derived in this case, that is an upper bound of the form Eℓ(ĉ n , c * ) ≤ C(k, d, P )/n, where the dependency of C(k, d, P ) on its parameters is explicit, developing the technique used in [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF] or [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF]. It is worth pointing out that the parameters mentioned in this result, such as the smaller distance between two optimal code points, are rather natural from the quantization point of view.

In addition, this result allows to partially answer the problem mentioned in [START_REF] Antos | Improved minimax bounds on the test and training distortion of empirically designed vector quantizers[END_REF] about the minimax rates over distributions satisfying Pollard's condition. This rate has been proved in [START_REF] Antos | Improved minimax bounds on the test and training distortion of empirically designed vector quantizers[END_REF] to be 1/ √ n, which is at first sight contradictory with the individual convergence rate of 1/n derived for every distribution in this case. The paper is organized as follows. In Section 2 some notation and definition are introduced, as well as the so-called margin conditions. The main results are exposed in Section 3: firstly an oracle inequality on the loss is stated, along with a minimax result, then it is shown that Gaussian mixtures are in the scope of the margin conditions. Finally, proofs are gathered in Section 4, and the proofs of technical intermediate results are to be found in Section 5.

Notation and Definitions.

Throughout the paper, for M > 0 and a in R d , B(a, M ) will denote the closed Euclidean ball with center a and radius M . With a slight abuse of notation, P is said to be M -bounded if its support is included in B(0, M ).

To frame the quantization issue as an empirical risk minimization issue, the following contrast function γ is introduced as

γ : R d k × R d -→ R (c, x) -→ min j=1,...,k x -c j 2 ,
where c = (c 1 , . . . , c k ) denotes a codebook, that is a kd-dimensional vector.

The risk R(c) then takes the form R(c) = R(Q) = P γ(c, .), where we recall that P f denotes the integration of the function f with respect to P . Similarly, the empirical risk Rn (c) can be defined as Rn (c) = P n γ(c, .), where P n is the empirical distribution associated with X 1 , . . . , X n , in other words

P n (A) = 1/n |{i|X i ∈ A}|, for every measurable subset A ⊂ R d .
It is worth pointing out that, if P x 2 < ∞, then there exist such minimizers ĉn and c * (see, e.g., Theorem 4.12 in [START_REF] Graf | Foundations of quantization for probability distributions[END_REF]). In the sequel the set of minimizers of the risk R(.) will be denoted by M.

Let c 1 , . . . , c k be a sequence of code points. A central role is played by the set of points which are closer to c i than to any other c j 's. To be more precise, the Voronoi cell, or quantization cell associated with c i is the closed set defined by

V i (c) = x ∈ R d | ∀j = i x -c i ≤ x -c j .
It may be noted that (V 1 (c), . . . , V k (c)) does not form a partition of R d , since V i (c) ∩ V j (c) may be non empty. To address this issue, a Voronoi partition associated with c is defined as a sequence of subsets (W 1 (c), . . . , W k (c)) which forms a partition of R d , and such that for every i = 1, . . . , k,

Wi (c) = V i (c),
where Wi (c) denotes the closure of the subset W i (c). The open Voronoi cell is defined the same way by

o V i (c) = x ∈ R d | ∀j = i x -c i < x -c j . Given a Voronoi partition W (c) = (W 1 (c), . . . , W k (c)), the following in- clusion holds, for i in {1, . . . , k}, o V i (c) ⊂ W i (c) ⊂ V i (c),
and the risk R(c) takes the form

R(c) = k i=1 P x -c i 2 ½ W i (c) (x) ,
where ½ A denotes the indicator function associated with A. In the case where (W 1 , . . . , W k ) are fixed subsets such that P (W i ) = 0, for every i = 1, . . . , k, it is clear that

P ( x -c i 2 ½ W i (c) (x)) ≥ P ( x -η i 2 ½ W i (c) (x)),
where η i denotes the conditional expectation of P over the subset W i (c), that is

η i = P (x½ W i (c) (x)) P (W i (c)) .
Moreover, it is proved in Theorem 4.1 of [START_REF] Graf | Foundations of quantization for probability distributions[END_REF] that, for every Voronoi partition W (c * ) associated with an optimal codebook c * , and every i = 1, . . . , k, P (W i (c * )) = 0. Consequently, any optimal codebook satisfies the so-called centroid condition (see, e.g., Section 6.2 of [START_REF] Gersho | Vector quantization and signal compression[END_REF]), that is

c * i = P (x½ W i (c * ) (x)) P (W i (c * )) .
As a remark, the centroid condition ensures that, for every c * in M and i = j,

P (V i (c * ) ∩ V j (c * )) = P x ∈ R d | x -c * i = x -c * j = 0.
A proof of this statement can be found in Theorem 4.2 of [START_REF] Graf | Foundations of quantization for probability distributions[END_REF]. According to this remark, it is clear that, for every optimal Voronoi partition (W 1 (c * ), . . . , W k (c * )),

P (W i (c * )) = P (V i (c * )) P n (W i (c * )) = a.s. P n (V i (c * )). (1)
The following quantities are of importance in the bounds exposed in Section 3.1:

B = min c * ∈M,i =j c * i -c * j p min = min c * ∈M,i=1,...,k P (V i (c * )). ( 2
)
The role of the boundaries between optimal Voronoi cells may be compared to the role played by the critical value 1/2 for the regression function in the statistical learning framework. To draw this comparison, the following set is introduced, for any c * ∈ M,

N (c * ) = i =j V i (c * ) ∩ V j (c * ).
Next, the critical region N * is defined as

N * = c * ∈M N (c * ).
This region seems to be of importance when considering the conditions under which the empirical risk minimization strategy for the quantization issue achieves faster rates of convergence, as exposed in [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF]. However, to fully draw the comparison between the margin conditions for the statistical learning issue (see, e.g., [START_REF] Mammen | Smooth discrimination analysis[END_REF]) and quantization, the neighborhood of this region has to be introduced. For this purpose the t-neighborhood of the critical region is defined as

N * t = x ∈ R d | d(x, N * ) ≤ t .
Intuitively, if P (N * t ) is small enough, then the source distribution P is concentrated around its optimal codebook, and may be thought of as a slight modification of the probability distribution with finite support made of an optimal codebook c * . To be more precise, let introduce the following key assumption: Definition 2.1 (Margin condition). Denote by p(t) = P (N * (t)). Then P satisfies a margin condition with radius r 0 if and only if

i) P is bounded by M , ii) M is finite, iii) For all 0 ≤ t ≤ r 0 , p(t) ≤ Bp min 128M 2 t. (3)
Contrary to the conditions required in [START_REF] Mammen | Smooth discrimination analysis[END_REF] in the framework of supervised classification, the margin condition introduced here only requires a local control of the weight of the neighborhood of the critical region. It is quite obvious that a global margin condition of the type p(t) ≤ Bp min /128M 2 t for every t > 0 implies the condition defined above. However, requiring only a local control of the weight function p(t) enlarges the scope of our results, since it allows to deal with non continuous probability distributions. This point is illustrated in the following example:

Example 1: Assume that there exists r > 0 such that p(x) = 0 if x ≤ r (for instance if P is supported on k points). Then P satisfies a margin condition with radius r.

It is also worth pointing out that the condition mentioned in [START_REF] Mammen | Smooth discrimination analysis[END_REF] requires a control of the weight of the neighborhood of the critical value 1/2 with a polynomial function with degree larger than 1. In the quantization framework, the special role played by the exponent 1 leads to only consider linear controls of the weight function. This point is explained by the following example:

Example 2: Assume that P is bounded by M , and that there exists Q > 0 and q > 1 such that p(x) ≤ Qx q . Then P satisfies (3), with

r 0 = B 4 √ 2M p min B 16 √ 2M Q 1/(q-1)
.

In the case where P has a density, the condition (3) can be thought of as a generalization of the condition mentioned in Theorem 3.2 of [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF], which requires the density of the distribution to be small enough over the critical region. In fact, provided that P has a continuous density, a uniform bound on the density over the critical region provides a local control of the weight function with a polynomial function of degree 1. This idea is developed in the following example:

Example 3(Continuous densities): Assume that P has a continuous density f , is bounded by M , and that M is finite. Moreover, assume that

N * f (u)du < Bp min 128M 2 . (4)
Then, by considering the derivative at 0 of the map t → p(t), there exists r 0 > 0 such that P satisfies a margin condition with radius r 0 > 0. It can easily be deduced from (4) that an uniform bound on the density located at the critical region can provide a sufficient condition for a distribution P to satisfy a margin condition. Such a result has to be compared to Theorem 3.2 of [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF], where it was required that

f |N * ∞ ≤ Γ d 2 B 2 d+5 M d+1 π d/2 p min ,
where Γ denotes the Gamma function.

Another interesting parameter of the quantization issue is the following separation factor, which quantifies the difference between optimal codebooks and local minimizers of the risk. Definition 2.2. Denote by M the set of local minimizers of the map c -→ P γ(c, .). Then P is said to be ε-separated if

inf c∈ M∩M c ℓ(c, c * ) = ε. (5)
It may be noticed that local minimizers of the risk function satisfy the centroid condition. Whenever P has a density and P x 2 < ∞, it can be proved that the set of minimizers of R coincides with the set of codebooks satisfying the centroid condition, also called stationary points (see, e.g., Lemma A of [START_REF] Pollard | A central limit theorem for k-means clustering[END_REF]). However, this result cannot be extended to non continuous distributions, as proved in Example 4.11 of [START_REF] Graf | Foundations of quantization for probability distributions[END_REF].

The main results of the present paper are based on the following proposition, which connects the margin condition stated in Definition 2.1 to the condition introduced in Theorem 2 of [START_REF] Antos | Individual convergence rates in empirical vector quantizer design[END_REF].

Proposition 2.1. Assume that P satisfies a margin condition with radius r 0 , and is ε-separated. Then, for every codebook c in

B(0, M ) k , c -c * (c) 2 ≤ κ 0 ℓ(c, c * ),
where c * (c) ∈ arg min c * ∈M cc * , and

κ 0 = 4kM 2 1 ε ∨ 64M 2 p min B 2 r 2 0 .
As mentioned in [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF] or [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF], the connection between the loss and the Euclidean squared distance can be thought of as a technical margin condition. It is worth pointing out that the dependency of κ 0 on different parameters of the quantization issue is explicit. This point allows us to derive explicit upper bounds on the excess risk in the following section.

Results.

3.1. Risk bound. The main result of this paper is the following: Theorem 3.1. Assume that P satisfies a margin condition with radius r 0 , and is ε-separated. Let κ 0 be defined as

κ 0 = 4kM 2 1 ε ∨ 64M 2 p min B 2 r 2 0 .
If ĉn is an empirical risk minimizer, then, with probability larger than 1 -

2e -x , ℓ(ĉ n , c * ) ≤ C 0 κ 0 |M| 2 R(c * ) n + κ 3 0 C 1 n 2 + κ 0 C 2 n x + C 3 n x, (6)
where C 0 is an absolute constant, C 1 is a combination of square roots of polynomial functions in k, log(k), d, B and M , C 2 is polynomial in k and M , C 3 is polynomial in M and √ k. Moreover, under the same conditions, with probability larger than 1-2e -x ,

ℓ(ĉ n , c * ) ≤ C ′ 0 κ 0 M 2 kd log(4|M| √ kd) + 1 n + κ 0 144M 2 n x + 64M 2 n x, (7)
where C ′ 0 is an absolute constant.

This result is in line with Theorem 3.1 in [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF] or Theorem 1 in [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF], concerning the dependency on the sample size n of the loss ℓ(ĉ n , c * ). The main advance lies in the dependency on other parameters of the loss of ĉn , which provides a non-asymptotic bound for the excess risk.

In fact, [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF] derives from chaining arguments such as one used in [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF] or [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF], and involves a classical dimension term of kd. When considering [START_REF] Blanchard | Statistical performance of support vector machines[END_REF], it seems that this kd term disappears from the dominant term of the upper bound. This suggests that the dimension of the Euclidean space in the finitedimensional case plays a minor role, as pointed out in Theorem 2.1 in [START_REF] Biau | On the performance of clustering in Hilbert spaces[END_REF]. An open question is to know whether such fast rates bounds can be derived in the infinite dimensional case.

However, (6) may be thought of as a semi-asymptotic bound, since it involves a dominant term and a residual term with respect to the sample size n. Although the dependency on other parameters of the dominant term is sharper in [START_REF] Blanchard | Statistical performance of support vector machines[END_REF] than in [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF], the residual term C 1 /n 2 in (6) still involves the dimension d. Consequently, (6) only guarantees that Eℓ(ĉ n , c * ) can be bounded from above with a dimension-free term when n grows to infinity.

Another interesting point is that Theorem 3.1 does no require P to have a density, contrary to the requirements of previous results in [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF] or [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF]. This remark makes the link between bounds obtained for point-wise distributions in [START_REF] Antos | Individual convergence rates in empirical vector quantizer design[END_REF] and bounds for distributions with densities as in [START_REF] Antos | Individual convergence rates in empirical vector quantizer design[END_REF] or [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF].

It is also worth mentioning that the dependency in ε surprisingly turns out to be sharp, as will be shown in Proposition 3.1. In fact, tuning this separation factor is the core of the demonstration of the minimax results in [START_REF] Bartlett | The minimax distortion redundancy in empirical quantizer design[END_REF] or [START_REF] Antos | Improved minimax bounds on the test and training distortion of empirically designed vector quantizers[END_REF]. [START_REF] Bartlett | The minimax distortion redundancy in empirical quantizer design[END_REF] ensures that the minimax convergence rate over the distributions bounded by M of any empirically designed codebook can be bounded from below by O(1/ √ n). A question of interest is to know whether this lower bound can be refined when considering only distributions satisfying some fast-convergence condition. A partial answer is given by Corollary 2 in [START_REF] Antos | Improved minimax bounds on the test and training distortion of empirically designed vector quantizers[END_REF], where it is proved that the minimax rate over distributions with continuous densities with individual convergence rate of O(1/n) for the empirical risk minimizer is still O(1/ √ n). However, since no non-asymptotic upper bound has been provided for these distributions, to understand which parameter is varying in this minimax result remains a hard issue. Consequently, this subsection is devoted to obtaining a minimax lower bound on the excess risk over the set of distributions satisfying the margin condition defined in Definition 2.1, in which some parameters are fixed. Throughout this subsection, ĉn will denote an empirically designed codebook, that is a map from (R d ) n to (R d ) k . Let k be an integer such that k ≥ 3, and M > 0. For simplicity, k is assumed to be divisible by 3. Let us introduce the following quantities:

Minimax lower bound. Theorem 1 in

m = 2k 3 ∆ = 15M 96m 1/d .
To focus on the dependency on the separation factor ε, the quantities involved in Definition 2.1 are fixed as:

   B = ∆ r 0 = 7∆ 16 p min ≥ 1 2k . (8)
Denote by D(ε) the set of probability distributions which are ε-separated, and which satisfies a margin condition with parameters defined in [START_REF] Fischer | Quantization and clustering with Bregman divergences[END_REF]. The minimax result is the following:

Proposition 3.1. Assume that k ≥ 3.
Then, for any empirically designed codebook,

E sup P ∈D(c 1 / √ n) ℓ(ĉ n , c * ) ≥ c 0 M 2 k 1-4 d √ n ,
where c 0 is an absolute constant, and

c 1 = (15M ) 2
4(96m

1 4 + 1 d ) 2
. Proposition 3.1 can be thought of as an extension of Theorem 1 in [START_REF] Bartlett | The minimax distortion redundancy in empirical quantizer design[END_REF]. This minimax lower bound has to be compared to the upper risk bound obtained in Theorem 3.1 for the empirical risk minimizer ĉn over the set of distributions D(c 1 / √ n). To be more precise, Theorem 3.1 ensures that, provided that n is large enough,

E sup P ∈D(c 1 / √ n) ≤ g(k, d, M ) √ n ,
where g(k, d, M ) depends only on k, d and M . In other words, the dependency of the upper bounds stated in Theorem 3.1 on ε turns out to be sharp whenever ε ∼ n -1 2 . Unfortunately, Proposition 3.1 can not be easily extended to the case where ε ∼ n -α , with 0 < α < 1/2. Consequently an open question is whether the upper bounds stated in Theorem 3.1 remains accurate with respect to ε in this case.

3.3. Quasi-Gaussian mixture example. The aim of this subsection is to illustrate the results offered in Section 3 with Gaussian mixtures in dimension d = 2. The Gaussian mixture model is a typical and well-defined clustering example. However we will not deal with the clustering issue but rather with its theoretical background.

In general, a Gaussian mixture distribution P is defined by its density

f (x) = k i=1 θ i 2π |Σ i | e -1 2 (x-m i ) t Σ -1 i (x-m i ) ,
where k denotes the number of component of the mixture, and the θ i 's denote the weights of the mixture, which satisfy k i=1 θ i = 1. Moreover, the m i 's denote the means of the mixture, so that m i ∈ R 2 , and the Σ i 's are the 2 × 2 variance matrices of the components.

We restrict ourselves to the case where the number of components k is known, and match the size k of the codebooks. To ease the calculation, we make the additional assumption that every component has the same diagonal variance matrix Σ i = σ 2 I 2 . Note that a similar result to Proposition 3.2 can be derived for distributions with different variance matrices Σ i , at the cost of more computing.

Since the support of a Gaussian random variable is not bounded, we define the "quasi-Gaussian" mixture model as follows, truncating each Gaussian component. Let the density f of the distribution P be defined by

f (x) = k i=1 θ i 2πσ 2 N i e -x-m i 2 2σ 2 ½ B(0,M ) ,
where N i denotes a normalization constant for each Gaussian variable.

To ensure this model to be close to the Gaussian mixture model, we assume that there exists a constant ε ∈ [0, 1] such that, for i = 1, . . . , k, N i ≥ 1ε.

Denote by B = inf i =j m im j the smallest possible distance between two different means of the mixture. To avoid boundary issues we assume that, for all i = 1, . . . , k, B(m i , B/3) ⊂ B(0, M ).

It is worth noticing that the two assumptions N i ≥ 1-ε and B(m i , B/3) ⊂ B(0, M ) can easily be satisfied as soon as M is chosen large enough. For such a model, Proposition 3.2 offers a sufficient condition for P to satisfy a margin condition.

Proposition 3.2. Let θ min = min i=1,...,k θ i , and θ max = max i=1,...,k θ i . Assume that

θ min θ max ≥ max 2048kσ 2 (1 -ε) B2 (1 -e -B2 /2048σ 2 ) , 2048k 2 M 3 (1 -ε)7σ 2 B(e B2 /32σ 2 -1) . (9)
Then P satisfies a margin condition with radius B 8 .

The condition (9) can be decomposed as follows. If

θ min θ max ≥ 2048kσ 2 (1 -ε) B2 (1 -e -B2 /2048σ 2 ) ,
then the optimal codebook c * is close to the vector of means of the mixture m = (m 1 , . . . , m k ). Therefore, it is possible to locate the critical region associated with the optimal codebook c * , and to derive an upper bound on the weight function defined in Definition 2.1. This leads to the second term of the maximum in [START_REF] Gersho | Vector quantization and signal compression[END_REF]. This condition can be interpreted as a condition on the polarization of the mixture. A favorable case for vector quantization seems to be when the poles of the mixtures are well separated, which is equivalent to σ is small compared to B, when considering Gaussian mixtures. Proposition 3.2 gives details on how σ has to be small compared to B, in order to satisfy the requirements of Proposition 2.1. This ensures that the loss ℓ(ĉ n , c * ) reaches an improved convergence rate of 1/n.

It may be noticed that Proposition 3.2 offers almost the same condition than Proposition 4.2 in [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF]. In fact, since the Gaussian mixture distributions have a continuous density, making use of (4) in Example 3 ensures that the margin condition for Gaussian mixtures is equivalent to a bound on the density over the critical region.

It is important to note that this result is valid when k is known and match exactly the number of components of the mixture. When the number of code points k is different from the number of components k of the mixture, we have no general idea of where the optimal code points can be located.

Moreover, suppose that there exists only one optimal codebook c * , up to reindexing, and that we are able to locate this optimal codebook c * . As mentioned in Proposition 2.1, the key quantity is in fact

B = inf i =j c * i - c * j .
In the case where k = k, there is no simple relation between B and B. Consequently, a condition like in Proposition 3.2 could not involve the natural parameter of the mixture B.

It is also worth pointing out that there exist cases where the set of optimal codebooks is not finite. For example, assume that P is a truncated rotationally symmetric Gaussian distribution, and k = 2. Since every rotation of an optimal codebook leads to another optimal codebook, there exists an infinite set of optimal codebooks. Since, in this case, N * = B(0, M ), obviously P does not satisfy a margin condition.

4.1. Let x ∈ V i (c * ) ∩ V j (c), for i = j. Then x - c i + c j 2 , c i -c j ≤ 4 √ 2M c -c * , (10) d(x, ∂V i (c * )) ≤ 4 √ 2M B c -c * . (11)
The two statements of Lemma 4.1 emphasize the fact that, provided that c and c * are quite similar, the areas on which the label may differ with respect to c and c * should be close to the boundary of Voronoi diagrams. This idea is mentioned in the proof of Corollary 1 in [START_REF] Antos | Individual convergence rates in empirical vector quantizer design[END_REF]. Nevertheless we provide here a simpler proof.

Proof of Lemma 4.1. Let x ∈ V i (c * )∩V j (c), then x-c j 2 ≤ x-c i 2 ,
which leads to c ic j , x -

c i +c j 2 ≤ 0. Since x -c * i ≤ x -c * j , we may write x -c i ≤ x -c j + c i -c * i + c j -c * j .
Taking square on both sides leads to 10) is proved. To prove [START_REF] Koltchinskii | Local Rademacher complexities and oracle inequalities in risk minimization[END_REF], remark that, since

x -c i 2 -x -c j 2 ≤ 2 x -c j ( c i -c * i + c j -c * j ) + c i -c * i + c j -c * j 2 ≤ 8M ( c i -c * i + c j -c * j ) ≤ 8 √ 2M c -c * . Since x -c i 2 -x -c j 2 = 2 x - c i +c j 2 , c i -c j , (
x ∈ V i (c * ), d(x, V i (c * )) ≤ d(x, h * i,j ), where h * i,j is the hyperplane defined by x ∈ B(0, M )| x -c * i = x -c * j .
Using quite simple geometric arguments, we deduce that

d(x, h * i,j ) = x - c * i + c * j 2 , c * i -c * j c * i -c * j .
The same arguments as in the proof of ( 10) guarantee that

x - c * i + c * j 2 , c * i -c * j c * i -c * j = x - c * i + c * j 2 , c * i -c * j c * i -c * j ≤ 4 √ 2M B c -c * .
Equipped with Lemma 4.1, we are in a position to prove Proposition 2.1. Let c ∈ M, and (W 1 (c), . . . , W k (c)) be a Voronoi partition associated to c, as defined in Section 2. Then ℓ(c, c * ) can be decomposed as follows:

P γ(c, .) = k i=1 P ( x -c i 2 ½ W i (c) ) = k i=1 P ( x -c i 2 ½ V i (c * ) ) + k i=1 P ( x -c i 2 (½ W i (c) -½ V i (c * ) )) .
Since, for all i = 1, . . . k, P (x½

V i (c * ) (x)) = P (V i (c * ))c * i (centroid condi- tion), we may write P ( x -c i 2 ½ V i (c * ) ) = P (V i (c * )) c i -c * i 2 + P ( x -c * i 2 ½ V i (c * ) ),
from which we deduce P γ(c, .) = P γ(c * , .)+

k i=1 P (V i (c * )) c i -c * i 2 + k i=1 P ( x -c i 2 (½ W i (c) -½ V i (c * ) )) , which leads to ℓ(c, c * ) ≥ p min c -c * 2 + k i=1 j =i P ( x -c j 2 -x -c i 2 )½ V i (c * )∩W j (c) . Since x ∈ W j (c) ⊂ V j (c), x -c j 2 -x -c i 2 ≤ 0. Thus it remains to bound from above k i=1 j =i P ( x -c i 2 -x -c j 2 )½ V i (c * )∩W j (c) .
Noticing that

x -c i 2 -x -c j 2 = 2 c j -c i , x i,j - c i + c j 2 ,
and using Lemma 4.1, we get

k i=1 P ( x -c i 2 (½ W i (c) -½ V i (c * ) )) ≥ -8 √ 2M c -c * p 4 √ 2M B c -c * . Consequently, if P satisfies (3), then, if c -c * ≤ Br 0 4 √ 2M , ℓ(c, c * ) ≥ p min 2 c -c * 2 .
Now turn to the case where cc * (c)

≥ Br 0 4 √ 2M . Since the support of P is included on B(0, M ), the function c -→ P γ(c, .) is continuous , its minimum on (R d ) k ∩ c * ∈M B(0, M ) c is attained. Such a minimizer is a local minimizer, or is at the boundary c-c * (c) = Br 0 4 √ 2M . Hence we deduce ℓ(c, c * ) ≥ ε ∧ p min Br 2 0 64M 2 ≥ ε ∧ p min Br 2 0 64M 2 c -c * 2 4kM 2 .
This proves Proposition 2.1 4.2. Proof of Theorem 3.1. Throughout this subsection P is assumed to satisfy a margin condition with radius r 0 , and to be ε-separated. A non decreasing map Φ :

R → R + is called sub-α if x → Φ(x)
x α is non increasing. The following localization theorem, derived from Theorem 6.1 in [START_REF] Blanchard | Statistical performance of support vector machines[END_REF], is the main argument of our proof.

Theorem 4.1. Let F be a class of bounded measurable functions such that there exist b > 0 and ω :

F -→ R + satisfying (i) ∀f ∈ F f ∞ ≤ b, (ii) ∀f ∈ F Var(f ) ≤ ω(f ).
Let K be a positive constant, Φ a sub-α function, α ∈ [1/2, 1[. Then there exists a constant C(α) such that, if D is a constant satisfying D ≤ 6KC(α), and r * is the unique solution of the equation Φ(r) = r/D, the following holds. Assume that

∀r ≥ r * E sup ω(f )≤r |(P -P n )f | ≤ Φ(r).
Then, for all x > 0, with probability larger than 1e -x ,

∀f ∈ F P f -P n f ≤ K -1 ω(f ) + 6KC(α) D 1 1-α r * + (9K 2 + 16Kb)x 4n .
A proof of Theorem 4.1 is given in Section 5.3 of [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF]. Notice that an explicit calculation of C(α) is given by C(α) = inf [START_REF] Blanchard | Statistical performance of support vector machines[END_REF]. The proof of (6) follows from the combination of Proposition 2.1 and a direct application of Theorem 4.1. To be more precise, let F 1 denote the set

x>1 1 + x α 1 2 + 1 x 1-α -1 . 4.2.1. Proof of
F 1 = γ(c, .) -γ(c * (c), .)| c ∈ B(0, M ) k .
Since, for all i ∈ {1, . . . , k}, 2 . It remains to bound from above the complexity term. This is done in the following proposition, derived from the proof of Theorem 1 in [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF].

x -c i 2 -x -c * i (c) 2 ≤ 4M c i -c * i (c) , it follows that, for every f ∈ F 1 , f ∞ ≤ 8M 2 Var P (f ) ≤ 16M 2 c -c * (c) 2 . Define ω 1 (f ) = 16M 2 c -c * (c)
Proposition 4.1. One has

E sup f ∈F 1 ,ω 1 (f )≤δ |(P -P n )f | ≤ (2 √ 2 + 64) √ kd √ n log(4|M| √ kd) + 1 √ δ. (12)
The proof of Proposition 4.1 derives from classical chaining arguments, and is given in Section 5.1. Let Φ 1 be defined as the right-hand side of [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF]. Observing that Φ 1 (δ) takes the form Φ 1 (δ) = Ξ 1 δ/n, the solution δ * 1 of the equation Φ 1 (δ) = δ/D may be written, for any D > 0,

δ * 1 = D 2 Ξ 2 1 n .
Let K > 0 and choose D = 6KC(1/2). Applying Theorem 4.1 to F 1 leads to, with probability larger than 1e -x ,

(P -P n )(γ(c, .) -γ(c * (c), .)) ≤ K -1 16M 2 c -c * (c) 2 + 36KC(1/2) 2 Ξ 2 1 n + 9K + 128M 2 4n x.
Introducing the inequality κ 0 ℓ(c, c * ) ≥ c-c * (c) 2 provided by Proposition 2.1, choosing K = 32M 2 κ 0 and taking into account that C(1/2) ≤ 4 leads to (6).

4.2.2. Proof of [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF]. The proof of (7) also relies on an application of Theorem 4.1. Let the loss of ĉn be decomposed as follows,

P (γ(ĉ n ) -γ(c * )) ≤ (P -P n )(γ(ĉ n ) -γ(c * )) ≤ (P -P n ) ĉn -c * (ĉ n ), ∆(c * (ĉ n ), .) + (P -P n ) ĉn -c * (ĉ n ) R(ĉ n , c * (ĉ n ), .), (13)
where

∆(c * , x) = -2((x -c * 1 )½ V 1 (c * ) , ..., (x -c * k )½ V k (c * ) ), and
R(c, c * , x) = i,j=1,...,k ½ V i (c * )∩W j (c) c -c * -1 c i -c * i 2 +2 x - c i + c j 2 , c i -c j ,
where we recall that W i (c) denotes an element of a Voronoi partition, such that Wi (c) ⊂ V i (c). The proof of (7) consists in applying Theorem 4.1 to the two terms in the right-hand side of [START_REF] Linder | Learning-theoretic methods in vector quantization[END_REF].

The first term on the right-hand side of ( 13) may be thought of as the dominant term in the decomposition of the loss. Define

F 2 = { c -c * (c), ∆(c * (c), .) )| c ∈ B(0, M )} .
In order to apply Theorem 4.1, the following lemmas are needed.

Lemma 4.2. Let f ∈ F 2 , then f ∞ ≤ 8M Var P (f ) ≤ 4 c -c * (c) 2 R(c * ).
Proof of Lemma 4.2. Elementary calculation shows that

Var( c -c * , ∆(c * , .) ) =P ( c -c * , ∆(c * , .) ) 2 -(P ( c -c * , ∆(c * , .) )) 2 = k i=1 P c i -c * i , -2(x -c * i ) 2 ½ V i (c * ) (x) ≤4 c -c * 2 R(c * ).
Let ω 2 (f ) be defined as 4 cc * (c) 2 R(c * ). It remains to bound from above the expectation of the maximum deviation between P and P n over the set F 2 .

Lemma 4.3. One has

E sup f ∈F 2 ,ω 2 (f )≤δ |(P -P n )f | ≤ 2|M| √ n √ δ (14)
Proof. This proof is inspired from the proof of Lemma 4.3 in [START_REF] Biau | On the performance of clustering in Hilbert spaces[END_REF]. The first step is the following

E sup f ∈F 2 ,ω 2 (f )≤δ |(P -P n )f | ≤ E sup c * ∈M, c-c * ≤ √ δ/4R(c * ) |(P -P n ) c -c * , ∆(c * , .) | .
For a general function h(Z) depending on a random map Z, we denote by E Z h the expectation of h taken with respect to Z. Introducing some Rademacher independent random variables σ i and using a symmetrization inequality such as in Section 2.2 of [START_REF] Koltchinskii | Local Rademacher complexities and oracle inequalities in risk minimization[END_REF] leads to

E sup c-c * ≤ √ δ/4R(c * ),c * ∈M |(P -P n ) c -c * , ∆(c * , .) | ≤ 2E X E σ sup c-c * ≤ √ δ/4R(c * ),c * ∈M c -c * , 1 n n i=1 σ i ∆(c * , X i ) ≤ δ/4R(c * )2E X E σ sup c * ∈M 1 n n i=1 σ i ∆(c * , X i ) ,
using Cauchy-Schwarz inequality. Eventually,

E X E σ sup c * ∈M 1 n n i=1 σ i ∆(c * , X i ) ≤ c * ∈M E X E σ 1 n n i=1 σ i ∆(c * , X i ) ≤ c * ∈M E X E σ 1 n n i=1 σ i ∆(c * , X i ) 2 ≤ c * ∈M 1 √ n E X ∆(c * , X) 2 ≤ 2|M| R(c * ) √ n ,
where Jensen's inequality has been used to obtain the second line. This gives the desired result.

The contribution of the first term in the right-hand side of ( 13) is described by the following proposition. Proposition 4.2. Let K 2 be a positive constant and x > 0. Then, with probability larger than 1e -x

(P -P n ) ĉn -c * (ĉ n ), ∆(c * (ĉ n ), .) ≤ K -1 2 4R(c * ) ĉn -c * (ĉ n ) 2 + 48 2 |M| 2 K 2 2 n + 9K 2 2 + 128M 2 √ kK 2 4n
x .

The proof follows from a direct application of Theorem 4.1 to the set F 2 , replacing the value C(1/2) with 4 to ease the calculation.

The second term in the right-hand side of ( 13) may be thought of as a residual term. Deriving sharper bounds on this term requires more accurate chaining techniques, as exposed below. Define

F 3 = { c -c * (c) R(c, c * (c), .)|c ∈ B(0, M )} .
In order to apply Theorem 4.1, the following intermediate results are needed.

Lemma 4.4. Let f ∈ F 3 , then f ∞ ≤ 2M √ kC ∞ Var P (f ) ≤ C 2 ∞ c -c * (c) 2 , with C ∞ = (2 √ k + 8 √ 2)M.
Proof of Lemma 4.4. The proof of Lemma 4.4 follows from a bound on R(c, c * (c), x), namely

|R(c, c * , x)| = c -c * -1 i,j ½ V i (c * )∩W j (c) c i -c * i 2 + 2 x - c i + c j 2 , c i -c j ≤ c -c * -1 i c i -c * i 2 ½ V i (c * ) + i =j 2 x - c i + c j 2 , c i -c j ½ V i (c * )∩W j (c)   .
Since, for all j in {1, . . . , k}, W j (c) ⊂ V j (c), applying Lemma 4.1 leads to

|R(c, c * , x)| ≤ c -c * -1 c -c * 2 + 8 √ 2M c -c * ½ N * ( 4 √ 2M B c-c * ) ≤ c -c * + 8 √ 2M ½ N * ( 4 √ 2M B c-c * ) := F c-c * (x). ( 15
)
Elementary calculations show that, for any δ > 0,

F δ ∞ ≤ (2 √ k + 8 √ 2)M = C ∞ ,
from which we deduce the desired upper bounds on Var P (f ) and f ∞ , for f in F 3 .

Let ω 3 (f ) be defined as C 2 ∞ cc * (c) 2 . The complexity term associated with the class of functions F 3 can be bounded as follows.

Proposition 4.3.

E sup f ∈F 3 ,ω 3 (f )≤δ |(P -P n )f | ≤ 8Q(k, d) √ C ∞ n C 2 ( √ δ/C ∞ ) √ δ, where      C 2 (r) = r + 8 √ 2M p 4 √ 2M B r Q(k, d) = 8 K 0 P (k, d) log(k 2 (4k -2)) P (k, d) = k 2 (2(k -1)(d + 1) + 24(3d + 4)),
and K 0 is an absolute constant.

The proof of Proposition 4.3 is based on a result of Mendelson and Vershynin in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] and its application to a more accurate version of Dudley's integral. For clarity, the proof is postponed to Section 5.2. Since P satisfies a margin condition with parameters (r 0 , κ), with κ ≤ Bp min 128M 2 , considering the two cases 4 √ 2M r/B ≤ r 0 and 4

√ 2M r/B ≥ r 0 yields that 8 √ 2M p( 4 √ 2M B r) ≤ 64M 2 Br 0 r,
for r ≥ 0. Using this inequality to bound C 2 from above in Proposition 4.3 leads to the following complexity result

E sup f ∈F 3 ,ω 3 (f )≤δ |(P -P n )f | ≤ Ξ 3 √ n δ 3 4 , (16)
where

Ξ 3 = 8M Q(k, d) C ∞ √ Br 0 .
Let Φ 3 be defined as Ξ 3 √ n δ 3 4 . Remark that Φ 3 is a sub-3/4 function. Consequently, for any D > 0, the solution of the equation Φ

3 (δ) = δ/D is δ * 3 = (DΞ 3 ) 4 n 2 .
Choosing K 3 > 0, and D = 6K 3 C(3/4) in Theorem 4.1 and taking into account that C(3/4) ≤ 10 leads to the following proposition.

Proposition 4.4. Let K 3 > 0. Then, with probability larger than 1e -x ,

(P -P n ) ( ĉn -c * (ĉ n ) R(ĉ n , c * (ĉ n ), .)) ≤ K -1 3 C 2 ∞ ĉn -c * (ĉ n ) 2 + 60 4 K 4 3 Ξ 4 3 n 2 + 9K 2 3 + 32M √ kC ∞ K 3 4n
x ,

with Ξ 3 = 8M Q(k,d) C∞ √ Br 0
, and Q is a function composed of products of square roots of polynomial functions in k, d, and log(k).

We are now in position to prove [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF]. Proposition 2.1 provides κ 0 such that

κ 0 ℓ(c, c * ) ≥ c -c * (c) 2 . Choosing K 2 = 8R(c * )κ 0 in Proposition 4.2, K 3 = 2C 2
∞ κ 0 in Proposition 4.4 and summing the two resulting inequalities leads to (7), valid on a set which has probability larger than 1 -2e -x . 4.3. Proof of Proposition 3.1. Throughout this subsection, for a codebook c, let Q denote the associated nearest-neighbor quantizer. In the general case, such an association depends on how the boundaries are allocated. However, since the distributions involved in the minimax result have a density, how boundaries are allocated will not matter.

Let k ≥ 3 be an integer. For convenience k is assumed to be divisible by 3. Let m = 2k/3. Let z 1 , . . . , z m denote a 6∆-net in B(0, Mρ), where ∆ > 0, and w 1 , . . . , w m a sequence of vectors such that w i = ∆. Finally, denote by U i the ball B(z i , ρ) and by U ′ i the ball B(z i , ρ). Slightly anticipating, define ρ = ∆ 16 . To get the largest ∆ such that for all i = 1, . . . , k U i and U ′ i are included in B(0, M ), it suffices to get the largest ∆ such that there exists a 6∆-net in B(0, M -∆/16). Since the cardinal of a 6∆-net is larger than the largest number of balls of radius 6∆ which can be packed into B(0, M -∆/16), a sufficient condition on ∆ to guarantee that a 6∆-net can be found is given by

m ≤ M -∆/16 6∆ d .
Since ∆ ≤ M , ∆ can be chosen as

∆ = 15M 96m 1/d .
For such a ∆, ρ takes the value ρ = ∆ 16 = 15M 1536m 1/d . Therefore, it only depends on k, d, and M . Let z = (z i ) i=1,...,m and w = (w i ) i=1,...,m be sequences as described above, such that, for i = 1, . . . , k, U i and U ′ i are included in B(0, M ). For a fixed σ ∈ {-1, +1} m such that m i=1 σ i = 0, let P σ be defined as

           P σ (U i ) = 1+σ i δ 2m P σ (U ′ i ) = 1+σ i δ 2m P σ ∼ U i (ρ -x -z i )½ x-z i ≤ρ dλ(x) P σ ∼ U ′ i (ρ -x -z i -w i )½ x-z i -w i ≤ρ dλ(x),
where λ denote the Lebesgue measure. These cone-shaped distributions are designed to have a continuous density, as done in [START_REF] Antos | Improved minimax bounds on the test and training distortion of empirically designed vector quantizers[END_REF]. To be more precise, for τ in {-1, +1} m 2 , σ(τ ) is defined as the sequence in {-1, +1} m such that

σ i (τ ) = τ i σ i+ m 2 (τ ) = -σ i (τ ), for i = 1, . . . , m 2 .
Finally, for a quantizer Q let R(Q, P σ ) denote the distortion of Q in the case where the source distribution is P σ .

Similarly, for

σ in {-1, +1} m satisfying m i=1 σ i = 0, let Q σ denote the quantizer defined by Q σ (U i ) = Q σ (U ′ i ) = z i + ω i /2 if σ i = -1, Q σ (U i ) = z i and Q σ (U ′ i ) = z i + ω i if σ i = +1
. Let Q denote the set of such quantizers. It can be proved that only quantizers in Q have to be considered. Proposition 4.5. Assume that A ≥ 6, δ ≤ 1/3, ∆ > 0, and ρ ≤ ∆ 16 . Then, for every quantizer Q there exists a quantizer Q σ in Q such that

∀P σ ′ R(Q σ , P σ ′ ) ≤ R(Q, P σ ′ ).
The proof of Proposition 4.5 follows the proof of Step 3 of Theorem 1 in [START_REF] Bartlett | The minimax distortion redundancy in empirical quantizer design[END_REF], replacing distributions supported on a finite set with distributions supported on small balls. Provided that the radius of these balls are small enough, the results are nearly the same in the two cases. The proof of Proposition 4.5 is given in Section 5.4.

For any σ and

σ ′ in {-1, 1} m , denote by ρ(σ, σ ′ ) = m i=1 |σ i -σ ′ i |,
and by H(P σ , P σ ′ ) the Hellinger distance between P σ and P σ ′ . To apply Assouad's Lemma to the set {P σ(τ ) } τ ∈{-1,+1} m 2 , the following lemma is needed: Lemma 4.5. Let τ and τ ′ denote two sequences in {-1, +1} m 2 such that ρ(τ, τ ′ ) = 2, then

H(P ⊗n σ(τ ) , P ⊗n σ(τ ′ ) ) ≤ 4nδ 2 m ,
where P ⊗n denotes the product law of a n-sample drawn from P . Furthermore, for any σ and

σ ′ in {-1, +1} m , R(Q σ ′ , P σ ) = R(Q σ , P σ ) + ∆ 2 δ 8m ρ(σ, σ ′ ).
Equipped with Lemma 4.5, a direct application of Assouad's Lemma as in Theorem 2.12 of [START_REF] Tsybakov | Introduction to nonparametric estimation[END_REF] yields that, provided that δ

= √ m 2 √ n , E sup τ ∈{-1,+1} m 2 R( Qn , P σ(τ ) ) -R(Q σ(τ ) , P σ(τ ) )) ≥ c 0 M 2 k 1-4 d n ,
for any empirically designed quantizer Qn , where c 0 is an explicit constant. Finally, it may be noticed that, for every δ ≤ 1 3 and σ, P σ satisfies a margin condition as in [START_REF] Fischer | Quantization and clustering with Bregman divergences[END_REF], and is ε-separated, with

ε = ∆ 2 δ 2m .
This concludes the proof of Proposition 3.1.

As a remark, it is worth mentioning that, whenever ε ∼ 1/n α , with α < 1/2, no interesting minimax lower bound can be derived using the distributions {P σ }'s. In fact, it can be proved, making use of the approach exposed in [START_REF] Bartlett | The minimax distortion redundancy in empirical quantizer design[END_REF], that the empirical risk minimization strategy Qn achieves the uniform rate sup

{Pσ} σ∈{-1,+1} m R( Qn , P σ ) -R(Q σ , P σ ) ≤ C(M, k, d)n -α e -c(k)n 1-2α ,
where C(M, k, d) and c(k) are constants. Consequently, in order to get a minimax lower bound matching the bound offered in Theorem 3.1, more general probability distributions should be used.

θ min θ max ≥ 2048kσ 2 (1 -ε) B2 (1 -e -B2 /2048σ 2 ) ,
ensures that, for every j in {1, . . . , k}, there exists i in {1, . . . , k} such that c * im j ≤ B/16. To be more precise, let m denote the vector of means (m 1 , . . . , m k ), then

R(m) ≤ k i=1 θ i 2πσ 2 N i V i (m) x -m i 2 e -x-m i 2 2σ 2 dx ≤ p max 2(1 -ε)πσ 2 k i=1 R 2 x -m i 2 e -x-m i 2 2σ 2 dx ≤ 2kp max σ 2 1 -ε .
Assume that there exists i in {1, . . . , k} such that, for all c * j -m i ≥ B/16. Then

R(c) ≥ θ i 2πσ 2 B(m i , B/32) B2 1024 e -x-m i 2 2σ 2 ≥ B2 θ min 2048πσ 2 B(m i , B/32) e -x-m i 2 2σ 2 > B2 θ min 1024 1 -e - B2 2048σ 2 > R(m).
Hence the contradiction. Up to relabeling, it is now assumed that for i = 1, . . . , k, m ic * i ≤ B/16. Take y in N * (x), for x ≤ B 8 , then, for every i in {1, . . . , k},

y -m i ≥ B 4 , which leads to k i=1 θ i 2πσ 2 N i y -m i 2 e -y-m i 2 2σ 2 ≤ kθ max (1 -ε)2πσ 2 e - B2 32σ 2 .
Since the Lebesgue measure of N * (x) is smaller than 4kπM x, it follows that

P (N * (x)) ≤ 2k 2 M θ max (1 -ε)σ 2 e - B2 32σ 2 x.
On the other hand, m ic * i ≤ B/16 yields that

B(m i , 3 B/8) ⊂ V i (c * ).
Therefore,

P (V i (c * )) ≥ θ i 2πσ 2 N i B(m i ,3 B/8) e -x-m i 2 2σ 2 dx ≥ θ i 1 -e -9 B2 128σ 2 , hence p min ≥ θ min 1 -e -9 B2 128σ 2
. Consequently, provided that

θ min θ max ≥ 2048k 2 M 3 (1 -ε)7σ 2 B(e B2 /32σ 2 -1) ,
direct calculation shows that

P (N * (x)) ≤ Bp min 128M 2 x.
5. Technical results.

5.1.

Proof of Proposition 4.1. The proof of Proposition 4.1 is derived from the proof of Lemma 3 in [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF]. Let c * be an optimal codebook, and c be a codebook. We denote by f c * ,c the function γ(c, .)γ(c * , .), so that

F 1 = f c * (c),c | c ∈ B(0, M ) k . Let Ψ 1 (r) denote the function Ψ 1 (r) = E sup c * ∈M, c-c * (c) ≤r (P -P n )f c * (c),c . Since {(c * (c), c * )| c -c * (c) ≤ r} ⊂ {(c * , c)| c * ∈ M, c -c * ≤ r} ,
it is easy to see that

Ψ 1 (r) ≤ E sup c * ∈M, c-c * ≤r |(P -P n )f c * ,c |.
The rest of the proof is derived from a chaining technique, used in the proof of Proposition 5.1 in [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF] or Lemma 3 in [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF]. Set ε j = 2 -j r, for j ≥ 0, and for every c * in M, denote by N j (c * ) an ε j net of B(c * , r), such that for every c in B(c * , r) there exists c j in N j (c * ) such that c jc ≤ ε j .

According to the proof of Theorem 2 in [START_REF] Antos | Individual convergence rates in empirical vector quantizer design[END_REF] or Lemma 3 in [START_REF] Chichignoud | Adaptive Noisy Clustering[END_REF], such an N j (c * ) can be defined, with

|N j (c * )| ≤ 2r √ kd ε j := n(ε j ).
By a dominated convergence Theorem, for any fixed c * in M and c,

f c * ,c j L 1 (P ),a.s. -→ j→∞ f c * ,c .
This allows us to decompose the expression of Ψ 1 as follows.

Ψ 1 (r) ≤ E sup c * ∈M, c-c * ≤r |(P -P n )f c * ,c | ≤ E sup c * ∈M,c 0 ∈N 0 (c * ) |(P -P n )f c * ,c 0 | + j>1 E sup c * ∈M,c j ∈N j (c * ),c j-1 ∈N j-1 (c * ) (P -P n )(f c * ,c j -f c * ,c j-1 ) , := A 1 + A 2 .
It remains to bound from above these two terms.

Bound on A 1 Introducing some Rademacher random variables σ i , i = 1, . . . , n and using the symmetrization principle as in [START_REF] Koltchinskii | Local Rademacher complexities and oracle inequalities in risk minimization[END_REF] leads to

E sup c * ∈M,c 0 ∈N 0 (c * ) |(P -P n )f c * ,c 0 | ≤ 2E X E σ sup λ=±1,c * ∈M,c 0 ∈N 0 (c * ) 1 n n i=1 σ i λf c * ,c 0 (X i ).
Let introduce here a maximal inequality derived from Lemma 2.3 in [START_REF] Massart | Concentration inequalities and model selection[END_REF].

Lemma 5.1. Let x 1 , . . . , x n denote a sequence of points in X , and let σ 1 , . . . , σ n denote a sequence of independent Rademacher random variables. Let F be a set of real valued functions over X such that |F| < ∞, and

sup f ∈F 1 n n i=1 f 2 (x i ) ≤ v. Then E σ sup f ∈F 1 n n i=1 σ i f (x i ) ≤ 2v log(|F|).

C. LEVRARD

In our case, for all c * in M and c 0 in N 0 (c * ),

1 n n i=1 f 2 c * ,c 0 (X i ) ≤ 16M 2 r 2 n ,
and |{λ = ±1, c * ∈ M, c 0 ∈ N 0 (c * )}| ≤ |M|(4 √ kd) kd .
Therefore, a direct application of Lemma 5.1 yields that

A 1 ≤ 8 √ 2M √ n kd log(4|M| √ kd).
Bound on A 2 Let j > 1. Using the same symmetrization argument as above leads to 1) , and

A 2,j := E sup c * ∈M,c j ∈N j (c * ),c j-1 ∈N j-1 (c * ) (P -P n )(f c * ,c j -f c * ,c j-1 ) ≤ E X E σ sup λ = ±1,c * ∈ M, c j ∈ N j (c * ),c j-1 ∈ N j-1 (c * ) 1 n n i=1 σ i λ(f c * ,c j (X i ) -f c * ,c j-1 (X i )). Since f c * ,c j (.) -f c * ,c j-1 (.) ∞ ≤ 8M r2 -(j-
|{λ = ±1, c * ∈ M, c j ∈ N j (c * ), c j-1 ∈ N j-1 (c * )}| ≤ 2|M|n(ε j ) 2 ,
a direct application of Lemma 5.1 leads to 1) .

A 2,j ≤ 64M r kd log(|M| √ kd2 j+2 )2 -(j-
Comparing a sum with an integral, and observing that

1 0 log(-x)dx ≤ 1 ensures that A 2 = j>1 A 2,j ≤ 256M r √ n log(|M| √ kd) + 1 .
Combining the two bounds and remarking that

E sup f ∈F 1 ,ω 1 (f )≤δ |(P -P n )f | ≤ Ψ 1 √ δ 4M
gives the result of Proposition 4.1.

5.2.

Proof of Proposition 4.3. The proof of Proposition 4.3 is based on a sharper chaining technique than the one used in Proposition 5.1 in [START_REF] Levrard | Fast rates for empirical vector quantization[END_REF]. We intend to bound from above the complexity term

E sup ω 3 (f )≤δ,f ∈F 3 |(P -P n )f |.
To this aim, define

Ψ 3 (r) = E sup c-c * (c) ≤r |(P -P n )R(c, c * , .)|,
where we recall that

R(c, c * , x) = i,j=1,...,k ½ V i (c * )∩W j (c) c -c * -1 c i -c * i 2 +2 x - c i + c j 2 , c i -c j ,
where (W 1 (c), . . . , W k (c)) is a Voronoi partition, defined in Section 2. For technical reasons, this Voronoi partition must be specified. Denote by C(p) the set of subsets of R d made of intersections of at most p half spaces (closed or open). Since R(c, c * , .) does not depend on how ties are broken, or, in other words, R(c, c * , .) does not depend on the choice of W j (c)'s among the partition cells satisfying

o V j (c) ⊂ W j (c) ⊂ V j (c),
we choose a Voronoi partition such that every

W j ∈ C(k -1). For instance, if H i,j denotes the closed half-space { x -c i ≤ x -c j } and o H i,j the open half space { x -c i < x -c j }. It is possible to build a Voronoi partition such that every cell is in C(k -1), choosing W j (c) = i<j o H i,j ∩ i>j H i,j .
In short, this convention consists in allocating points on boundaries between V j 's to the smallest possible index. As a consequence, it is immediate that

Ψ 3 (r) = E sup c-c * (c) ≤r,W j (c)∈C(k-1) |(P -P n )R(c, c * , .)|.
The following set of function of interest is then introduced.

G(r) = {0} ∪ 1 F r    λ c -c * -1 i,j ½ V i (c * )∩W j (c)∩B(0,M ) c i -c * i 2 + 2 x - c i + c j 2 , c i -c j | λ = ±1, c ∈ B(0, M ) k , c * ∈ M, W j ∈ C(k -1)    ,
where F r is defined in [START_REF] Mammen | Smooth discrimination analysis[END_REF] as an envelope of G(r).

Let σ 1 , . . . , σ n denote a sequence of independent Rademacher variables. As developed in the proof of Proposition 4.1, the first step is a symmetrization inequality

Ψ 3 (r) ≤ E sup c * ∈M, c-c * ≤r |(P -P n )R(c, c * , .)| ≤ 2E X E σ sup λ=±1,c * ∈M, c-c * ≤r 1 n n i=1 λσ i R(c, c * , X i ) ≤ 2E X E σ sup g∈G(r) 1 n n i=1 σ i F r (X i )g(X i ) := 2E X R n .
The next step is to chain the set G(r). To this aim, define for any set of real valued function F, any norm on F and any ε > 0, the covering number N (F, , ε) as the cardinal of the smallest covering of F with balls of radius ε for the norm . To be more precise, for any g in G(r), and any finite subset S ⊂ R, we define

g L 2 (S) = 1 |S| s∈S g 2 (s),
and, with a slight abuse of notation, g L 2 (Pn) = 1/n n i=1 g 2 (X i ). The technical result concerning the covering numbers of G(r) is the following. Proposition 5.1. Let S be a finite set, and 0 < ε < 1. There exists some constant K > 0, not depending on S, such that

N (G(r), ε, L 2 (S))) ≤ k 2 (4k -2) ε KP (k,d) , with P (k, d) = k 2 (2(k -1)(d + 1) + 24(3d + 4)).
For clarity, the proof of Proposition 5.1 is postponed to the following subsection. An immediate consequence of Proposition 5.1 is that

N (G(r), ε, L 2 (P n )) ≤ k 2 (4k -2) ε KP (k,d) := n(ε),
for any n-sample X 1 , . . . , X n . Consequently, let X 1 , . . . , X n be fixed, and set ε 0 = 1, ε j = 2 -2j ε 0 , for j > 1.

For j = 0, since F r is an envelope of G(r), a 1 covering of G(r) for the L 2 (P n ) norm is the ball of center g 0 = 0 and radius 1.

For j > 1, Proposition 5.1 provides a ε j covering G j (r) of G(r) for the L 2 (P n ) norm with cardinality at most n(ε j ). For any g in G(r), denote by g j the projection of g onto this covering, so that gg j L 2 (Pn) ≤ ε j . For short we will write n j = n(ε j ).

It is easy to see that for every i in {1, . . . , n},

g j (X i ) -→ j→∞ g(X i ).
Then R n may be decomposed as follows:

R n = E σ sup λ=±1,c * ∈M, c-c * ≤r 1 n n i=1 λσ i R(c, c * , X i ) ≤ j>1 E σ sup g∈G 1 n n i=1 σ i F r (X i )(g j (X i ) -g j-1 (X i )) := j>1 b j .
A direct application of Lemma 5.1 for every b j yields that

b j ≤ 1 √ n 2 sup g∈G(r) (g j -g j-1 )F r 2 L 2 (Pn) log(n j n j-1 ) ≤ 1 √ n 2 log(n j n j-1 ) sup g∈G(r) 2C ∞ F r L 2 (Pn) g j -g j-1 L 2 (Pn) ≤ 4 √ C ∞ √ n F r L 2 (Pn) log(n(ε j )) √ ε j-1 .
Denote by ε ′ j the quantity √ ε j = 2 -j . Since x → log(n(x 2 )) is nonincreasing, it is quite easy to see that log(n(ε

′ 2 j ))ε ′ j-1 4 = log(n(ε ′ 2 j ))ε ′ j+1 ≤ ε ′ j ε ′ j+1 log(n(x 2 ))dx.
From this we deduce that

j>1 ε j-1 log(n(ε j )) ≤ 4 1/2 0 log(n(x 2 ))dx ≤ 1/2 0 KP (k, d) log( k 2 (4k -2) x 2 )dx ≤ 2 KP (k, d) log(k 2 (4k -2)) + 4 KP (k, d) 1/2 0 log(1/x 2 ).
Since

1/2 0 log(1/x 2 ) ≤ 1, we get j>1 ε j-1 log(n(ε j )) ≤ 8 KP (k, d) log(k 2 (4k -2)) := Q(k, d). Thus R n ≤ 4Q(k, d) √ C ∞ √ n F r L 2 (Pn) .
It remains now to take expectations with respect to the n-sample X 1 , . . . , X n . Since x → √ x is a concave map,

E X ( F r L 2 (Pn) ) ≤ F r L 2 (P ) = C 2 (r).
Gathering all terms leads to , where K and c are constants, and vc(F, ct) denotes the t-shattering dimension of F, as defined in [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF].

Ψ 3 (r) ≤ 8Q(k, d) C ∞ C 2 (r) √ n . Substituting √ δ/C ∞ with
Remark that, for every t > 0, vc(F, ct) ≤ d p (F), where d p (F) denotes the pseudo-dimension of F, that is the largest integer p such that there exists x 1 , . . . , x p ∈ Ω, and t 1 , . . . , t p real numbers, satisfying the following property: for every σ ∈ {-1, 1} p there exists f σ ∈ F such that, for i = 1, . . . , p, σ i (f σ (x i )t i ) > 0. As a consequence, the quantity of interest is d p (G(r)).

Recalling that every g in G can be written

R(c, c * , x) = c -c * -1 i,j ½ V i (c * )∩W j (c)∩B(0,M ) c i -c * i 2 +2 x - c i + c j 2 , c i -c j ,
where, for every j in {1, . . . , k}, W j (c) is in C(k -1), it may be noticed that g takes the form of a sum of k 2 maps of the type ℓ½ C ½ B(0,1) , where ℓ denotes an affine map, and C is an element of C(2(k -1)). Let Af f (R d , R) denote the space of affine maps between R d and R.

It is worth pointing out that every map ℓ½ C ½ B(0,1) involved in the above decomposition of R(c, c * , .) admits F r as an envelop.

Denote by

G ′ (r) = ℓ½ C ½ B (0, M ) F r ; ℓ ∈ Af f (R d , R), C ∈ C(2(k -1)) .
We immediately deduce that

N (G(r), ε) ≤ N (G ′ (r), ε/k 2 ) k 2 .
Consider now the set of functions N (G ′ (r), ε). The following lemma offers a decomposition of N (G ′ (r), ε). In order to apply Lemma 5.2, a crucial point is to only deal with maps taking values in [-1, 1]. To this aim, we define the set

H = f ½ {|f |≤Fr } F r ,
where f is in Af f (R d , R), and the set

P d = ½ {ℓ≤a} |ℓ ∈ L(R d , R), a ∈ R ∪ ½ {ℓ<a} |ℓ ∈ L(R d , R), a ∈ R ,
where L(R d , R) denotes the set of linear maps from R d to R. We may write

G ′ (r) ⊂ H × 2(k-1) i=1 P d × ½ B(0,M ) ,
It is well known that

d p (P d ) = d.
Since every set of functions in this decomposition is composed of functions taking values in [-1, 1], we intend to apply Theorem 5.1 to every set. Consequently it remains to bound from above the pseudo-dimensions of these sets of functions. First we deal with H:

Lemma 5.3. One has

d p (H) = d p f ½ {|f |≤Fr } |f ∈ Af f (R d , R) ≤ 24(3d + 4).
Proof of Lemma 5.3. The first equality is obvious, so we only have to deal with the inequality. We recall that the pseudo-dimension of the set of functions f ½ {|f |≤Fr } |f ∈ Af f (R d , R) is the Vapnik dimension of the set of functions

H ′ = ½ {f ½ {|f |≤Fr} -t≤0} |f ∈ Af f (R d , R), t ∈ R . Let x 1 , . . . , x 2m denote 2m points in R d . Since F r (x) = c 1 + c 2 ½ N * (x)
, where c 1 et c 2 are constants, at least m points fall in an area on which F r takes the form F r (x) = c, for some constant c. Without loss of generality, we assume that x 1 , . . . , x m fall in such an area. Consequently, we have to bound from above the quantity

½ {f ½ {|f |≤c} -t≤0} (x 1 , . . . , x m ) . Observing that ½ {|f |≤c} = ½ {f ≤c} × ½ {f ≥-c} ,
we deduce that

½ {f ½ {|f |≤c} -t≤0} (x 1 , . . . , x m ) ≤ ½ {f ½ {f ≤c} -t≤0} (x 1 , . . . , x m ) × ½ {f ½ {f ≥-c} -t≤0} (x 1 , . . . , x m ) . Noticing that d V C ½ {f ≤c} |f ∈ Af f (R d , R) = d + 1
and making use of Sauer's lemma leads to, provided that m ≥ d + 1,

½ {f ≤c} (x 1 , . . . , x m ) = ½ {f ≥-c (x 1 , . . . , x m ) ≤ em d + 1 (d+1)
, which ensures that

½ {|f |≤c} (x 1 , . . . , x m ) ≤ em d + 1 2(d+1)
.

Choose a configuration of ½ |f (x 1 )|≤c , . . . , ½ |f (xm )|≤c , for instance by indexing the x i 's so that |f (x 1 )| > c, . . . , |f (x r )| > c and |f (x r+1 )| ≤ c, . . . , |f (x m )| ≤ c. For the r first x i 's, only two configurations remains for H ′ (x 1 , . . . , x r ), the configuration (0, . . . , 0) and (1, . . . , 1). Considering the Consequently, a sufficient condition on m is given by

m -r + 1 last x i 's, |H ′ (x m-r+1 , . . . , x m )| ≤ ½ {f -t≤0} (x m-r+1 , . . . , m) . Next, ½ {f -t≤0} (x m-r+1 , . . . , m) ≤ ½ {f -t≤0} (x 1 , . . . , m) . Eventually, Sauer's lemma guarantees that ½ {f -t≤0} (x 1 , . . . , m) ≤ em d+2 (d+2) , pro- vided that m ≥ d + 2. Consequently, we get, for m ≥ d + 2, H ′ (x 1 , . . . , x 2m ) = ½ {f ½ {|f |≤Fr} -t≤0} (x 1 , . . . , x 2m ) ≤ 2 m × ½ {f ½ {|f |≤c} -t≤0} (x 1 , . . . , x m ) ≤ 2 m × ½ {|f |≤c} (x 1 , . . . , x m ) × 2 em d + 2 d+2 ≤ 2 m × 2 em d + 1
3em 3d + 4 3d+4 ≤ 2 m-1 .
Using the same method as in [START_REF] Baum | What size net gives valid generalization?[END_REF], the choice m = ⌈3(3d + 4) log 2 (3e)⌉ turns out to be adequate. At last, noticing that 2m ≤ 24(3d + 4), we immediately deduce that d p (H) ≤ 2m ≤ 24(3d + 4).

Applying Lemma 5.2 and Theorem 5.1 yields that

N G ′ (r), ε ≤ N (H, ε/(2k -1)) × N (P d , ε/(2k -1)) 2k-2 ≤ 4k -2 ε K[24(3d+4)+(d+1)(2k-2)]
.

At last, the result of Proposition 5.1 is given by

N (G(r), ε) ≤ N G ′ (r), ε/k 2 k 2 ≤ 2(2k -1)k 2 ε Kk 2 [24(3d+4)+2(d+1)(k-1)]
.

5.4. Proof of Proposition 4.5. The proof of Proposition 4.5 is based on elementary properties of distributions with finite support, which are extended to the case where the source distribution is supported on small balls. Throughout this subsection, a source distribution P σ ′ is fixed, so that R(Q, P σ ′ ) may be denoted by R(Q). Lemma 5.4. Let z 1 and z 2 be points in R d , denote by R the quantity z 1z 2 , by U i the ball B(z i , ρ). At last, let P denote the cone-shaped distribution with density

2(d + 1) V ( x-z i ≤ρ (ρ -x -z i ),
over each ball U i , where V denote the volume of the unit ball. Then, if

(R/2 -3ρ) 2 ≥ ρ 2 2d(d + 1) (d + 2)(d + 3) and ρ ≤ R 2 , then the best 2-quantizer Q * 2 is such that Q * 2 (U i ) = z i for i = 1, 2. Further- more, the best 1-quantizer Q * 1 is such that Q * 1 (U 1 ∪ U 2 ) = (z 1 + z 2 )/2.
Proof of Lemma 5.4. Let V i denote the Voronoi cell associated with z i in the Voronoi diagram generated by (z 1 , z 2 ). Denote by 2 dx the contribution of the cell i to the distortion of Q. Denote by V the volume of the unit ball, and by S its surface. Recalling that S = d × V , an elementary calculation shows that

Q * 2 the quantizer satisfying Q * 2 (U i ) = z i for i = 1, 2. For any quantizer Q denote by R i (Q) = V i x -Q(x)
R i (Q * 2 ) = 1 2 d + 1 ρ d+1 V ρ 0 S(ρr d+1 -r d+2 )dr = ρ 2 d(d + 1) 2(d + 2)(d + 3) . Let m in i = |Q(U i )∩V i | and m out i = |Q(U i ))∩V c i |
denote the number of images of U i sent inside and outside V i . For a given i, there are three situations of interest, which are described below.

1.

m out i = 0 and m in i = 1, then it is clear that R i (Q * 2 ) ≤ R i (Q). 2. m out i = 0 and m in i = 2, then R i (Q) ≥ 0 = R i (Q * ) -ρ 2 d(d+1) 2(d+2)(d+3) . 3. m out i ≥ 1, then there exists z ∈ U i such that Q(z) / ∈ V i . Consequently, z -Q(z) ≥ R 2 -ρ. Let z ′ ∈ B(z i , ρ), then z ′ -Q(z ′ ) ≥ z -Q(z ′ ) -2ρ ≥ z -Q(z) -2ρ ≥ R 2 -3ρ.
Hence we deduce

R i (Q) ≥ 1/2( R 2 -3ρ) 2 = R i (Q * 2 )+1/2 ( R 2 -3ρ) 2 -ρ 2 d(d + 1) (d + 2)(d + 3) .
Since Q is a 2-quantizer, it is easy to see that

| i; m in i ≥ 2 | ≤ | i; m out i ≥ 1 |.
From this we deduce that

R(Q) = {i;m in i ≥2,m out i =0} R i (Q) + {i;m out i ≥1} R i (Q) + {i;m in i =1,m out i =0} R i (Q) ≥ R(Q * 2 ) + {i;m in i ≥2,m out i =0} 1 2 R 2 -3ρ 2 -ρ 2 d(d + 1) (d + 2)(d + 3) . Taking (R/2 -3ρ) 2 ≥ ρ 2 2d(d+1) (d+2)(d+3) ensures that R(Q) ≥ R(Q * 2 ).
Considering the distributions P σ , σ in {-1, +1} m , taking ρ ≤ ∆ 16 ensures that the conditions of Lemma 5.4 are satisfied when considering P σ|U i ∪U ′ i . We turn now to the proof of Proposition 4.5.

Let Q be a k-quantizer. The following construction provides

Q σ ∈ Q such that R(Q σ ) ≤ R(Q). Let V i
denote the union of the Voronoi cells associated with z i and z i + ω i , in the Voronoi diagram generated by the sequences z and ω. We adopt the following notation

             n i (Q) = |Q(B(0, M )) ∩ V i | n out i (Q) = |Q(V i ) ∩ V c i | I j (Q) = {i; n i (Q) = j} i j (Q) = |I j (Q)| i ≥j (Q) = i≥j i j (Q).
The first step is to add code points to empty cells. From the k-quantizer Q, a quantizer Q 1 is built as follows

• If n i (Q) ≥ 1, then we take Q 1|V i ≡ Q |V i . • If n i (Q) = 0, then we set Q 1 (U i ) = Q 1 (U ′ i ) = z i + w i 2 .
Notice that Q 1 is a (k + i 0 (Q))-quantizer. Denote k 1 = k + i 0 and p ± = 1±δ 2m , then R(Q 1 ) can be bounded as follows.

Let i be an integer between 1 and m. We denote by R i (Q) the contribution of V i to the risk R(Q).

If i ∈ I ≥1 , then R i (Q) = R i (Q 1 ). Otherwise, if i ∈ I 0 (Q), R i (Q 1 ) = 2p ± ρ 2 d(d + 1) (d + 2)(d + 3) + p ± ∆ 2 2 .
Furthermore, if i ∈ I 0 , then n out i (Q) ≥ 1, which ensures that, as in the proof of Lemma 5.4,

R i (Q) ≥ p ± (A -2)∆ 2 -2ρ 2 .
Since A ≥ 6 and ρ ≤ ∆ 16 , we may write

R i (Q) -R i (Q 1 ) ≥ p ± (2∆ -2ρ) 2 -4ρ 2 - ∆ 2 2 ≥ p ± 2∆( 3∆ 4 ) - ∆ 2 2 ≥ p - 3∆ 2 2 .
Summing all the contributions of V i 's leads to

R(Q 1 ) ≤ R(Q) -i 0 (Q)p - 3∆ 2 2
Next, we build the quantizer Q 2 according to the following rule:

• If n i (Q 1 ) ≥ 2, then Q 2 (U i ) = z i and Q 2 (U ′ i ) = z i + w i . • If n i (Q 1 ) = 1, then Q 2 (U i ) = Q 2 (U ′ i ) = z i + w i 2 .
Since for i = 1, . . . , k, n i (Q 1 ) ≥ 1, Q 2 is defined on every V i . Notice that, since I j (Q 1 ) = I j (Q) for j ≥ 2, Q 2 has k 2 = k + i 0 (Q) -p≥3 (p -2)i p (Q) code points. The following lemma offers a relation between R(Q 2 ) and R(Q 1 ). Lemma 5.5. One has

R(Q 2 ) ≤ R(Q 1 ) + i ≥3 (Q) p + ∆ 2 128 .
Proof of Lemma 5.5. Let i be an integer between 1 and m. Several cases may occur, as described below.

• Assume that n i (Q 1 ) = 1.

-If n out i (Q 1 ) = 0, then R i (Q 1 ) ≥ R i (Q 2 ), according to Lemma 5.4. -If n out i (Q 1 ) ≥ 1, then, using the same technique as mentioned to bound R(Q 1 ) from above,

R i (Q 1 )-R i (Q 2 ) ≥ p ± 3∆ 2 2 , which leads to R i (Q 1 ) ≥ R i (Q 2 ).
• Assume that n i (Q 1 ) = 2.

-If n out i (Q 1 ) = 0, then R i (Q 1 ) ≥ R i (Q 2 ), according to Lemma 5.4.

-If n out i (Q 1 ) ≥ 1, then, since R i (Q 2 ) = 2p ± ρ 2 d d+2 ≤ p + ∆ 2 128 , R i (Q 1 ) - R i (Q 2 ) ≥ ∆ 2 ≥ 0. • At last, assume that n i (Q i ) ≥ 3. If n out i (Q 1 ) ≥ 1, then R i (Q 1 ) ≥ R i (Q 2 ). If n out i (Q 1 ) = 0, then R i (Q 1 ) ≥ 0 = R i (Q 1 ) -2p ± ∆ 2 128 . In both cases R(Q 2 ) ≤ R(Q 1 ) + p + ∆ 2
128 . Noticing that I ≥3 (Q 1 ) = I ≥3 (Q), and summing the contributions R i (Q 2 ) leads to the desired result.

The last step is to build a quantizer Q σ from Q 2 with exactly k code points.

• If k 2 = k, set Q σ = Q 2 . • If k 2 < k, choose (k -k 2 ) V i such that n i (Q 2 ) = 1 (
elementary calculation shows that there exist at least kk 2 such V i 's). For every such

V i , set Q σ (U i ) = z i and Q σ (U ′ i ) = z i + ω i . Then R(Q σ ) ≤ R(Q 2 ) -(k -k 2 )p - ∆ 2 2 . • If k 2 > k, choose (k 2 -k) cells V i such that n i (Q 2 ) = 2. For every such V i , define Q σ (U i ) = Q σ (U ′ i ) = z i + ω i 2 . Then R(Q σ ) ≤ R(Q 2 ) + (k 2 -k)p + ∆ 2 2 .
By construction, Q σ has exactly k code points, and is an element of Q.

Finally, a result on the risk of Q σ is given by the following proposition.

Proposition 5.2. Let Q be a quantizer and Q σ built as mentioned above. Then, R(Q σ ) ≤ R(Q).

Proof of Proposition 5.2. Since δ ≤ 1 3 , easy calculation ensures that 1 -p - p + ≤ 1 2 . Suppose that k 2 ≤ k. Comparing the risk of Q to the risks of Q 1 , Q 2 and Q σ leads to

R(Q σ ) ≤ R(Q) -i 0 p - 3∆ 2 2 + (i 0 + 2i ≥3 - p≥3 pi p )p - ∆ 2 2 + i ≥3 p + ∆ 2 128 .
Since p≥3 pi p ≥ 3i ≥3 , it is clear that

R(Q σ ) ≤ R(Q) -p -i 0 ∆ 2 2 + ∆ 2 i ≥3 ( p + 128 - p - 2 ) ≤ R(Q).
Next, suppose that k 2 > k. Then

R(Q σ ) ≤ R(Q) +   i 0 + 2i ≥3 - p≥3 pi p   p + ∆ 2 2 + i ≥3 p + ∆ 2 128 -i 0 p - 3∆ 2 2 ≤ R(Q) + i 0 ∆ 2 2 (p + -3p -) + p + i ≥3 ∆ 2 ( 1 128 - 1 2
), which yields that R(Q σ ) ≤ R(Q).

5.5. Proof of Lemma 4.5. Let introduce, for distributions P and Q with densities f and g the affinity α(P, Q) = f g, so that H 2 (P, Q) = 2(1α(P, Q)). Elementary calculation shows that, if ρ(σ, σ ′ ) = 4, then

α(P σ , P σ ′ ) = 1 + 2 m 1 -δ 2 -1 ≥ 1 - 2δ 2 m .
Hence we deduce H 2 (P ⊗n σ , P ⊗n σ ′ ) = 2(1α(P ⊗n σ , P ⊗n σ ′ )) = 2(1α n (P σ , P σ ′ ))

≤ 4nδ 2 m .
Finally, since ρ(τ, τ ′ ) = 2 implies ρ(σ(τ ), σ(τ ′ )) = 4, for τ , τ ′ in {-1, +1} m 2 , the first part of Lemma 4.5 is proved.

Next, for simplicity assume that σ is such that σ 1 = . . . σ m 2 = +1 and σ m 2 +1 = . . . = σ m = -1. Let S -and S + denote the set of mistakes of σ ′ , that is

S -= {i = 1, . . . , m 2 | σ ′ i = -1} S + = {i = m 2 + 1, . . . , m| σ ′ i = +1}.
Finally let s + and s -respectively denote |S + | and |S -|. Since m i=1 σ ′ i = 0, it is clear that s + = s -:= s.

As in Subsection 5.4, let R i (Q σ ′ ) denote the contribution of U i ∪ U ′ i to the distortion. Then, for i in S -, elementary calculation shows that

R i (Q σ ′ ) = R i (Q σ ) + (1 + δ)∆ 2 4m .
Symmetrically, for i in S + ,

R i (Q σ ′ ) = R i (Q σ ) - (1 -δ)∆ 2 4m .
Summing with respect to i and taking into account that s + = s -= s leads to

R(Q σ ′ ) = R(Q σ ) + s ∆ 2 δ 2m .
Remarking that s = ρ(σ,σ ′ ) 4 concludes the proof of Lemma 4.5.

4. Proofs. 4 . 1 .

 41 Proof of Proposition 2.1. The proof of Proposition 2.1 is based on the following lemma.

Lemma

4. 4 .

 4 Proof of Proposition 3.2. As mentioned below Proposition 3.2, the inequality

5 . 3 . 2 t

 532 r gives the result of Proposition 4.3. Proof of Proposition 5.1. Let S be a finite subset of R d , and denote by C(p) the set of subsets of R d which are intersections of at most p half spaces (closed or open). For short, N (F, ε) will denote N (F, L 2 (S), ε). The proof of Proposition 5.1 is based on the following result, Theorem 1 in [18]. Theorem 5.1. Let P denote a measure on Ω. Let F be a set of maps from Ω into [-1, 1]. Then, for every 0 < t < 1, N (F, t, L 2 (P )) ≤ Kvc(F ,ct)

Lemma 5 . 2 .N

 52 Denote by F s s = 1, . . . , p a collection of set of functions taking values in [-1, 1]. Then N (F s , ε/p).


Brigitte Bigi
email: brigitte.bigi@lpl-aix.fr

A Multilingual Text Normalization Approach

Keywords: LRL, text normalization, corpus, xml, under-resourced languages

The creation of text corpora requires a sequence of processing steps in order to constitute, normalize, and then to directly exploit it by a given application. This paper presents a generic approach for text normalization and concentrates on the aspects of methodology and linguistic engineering, which serve to develop a multipurpose multilingual text corpus. This approach was applied to French, English, Spanish, Vietnamese, Khmer and Chinese. It consists in splitting the text normalization problem in a set of minor sub-problems as language-independent as possible. A set of text corpus normalization tools with linked resources and a document structuring method are proposed.

Introduction

There are more than 6000 languages in the world but only a small number possess the resources required for implementation of Human Language Technologies (HLT). Thus, HLT are mostly concerned by languages which have large resources available or which suddenly became of interest because of the economic or political scene. On the contrary, languages from developing countries or minorities were less treated in the past years. Among HLT, this paper focuses on text normalization which is a well known problem in Natural Language Processing (NLP). The first task faced by any NLP system is the conversion of input text into a linguistic representation. Texts contain a variety of "non-standard" token types such as digit sequences, words, acronyms and letter sequences in all capitals, mixed case words, abbreviations, roman numerals, URL's and e-mail addresses... Normalizing or rewriting such texts using ordinary words is an important issue for various applications.

Text normalization is commonly considered as language-dependent and/or task-dependent. In the Machine Translation community, we can cite [START_REF] Graliński | Text Normalization as a Special Case of Machine Translation[END_REF]. In the ASR community for English, the Linguistic Data Consortium tools (LDC, 1998) are widely used for the text normalization task. The LDC tools perform text normalization using a set of ad hoc rules, converting numerals to words and expanding abbreviations listed in a table. The Johns Hopkins University Summer Workshop research project (Sproat et al., 2001) made a systematic effort to build a general solution to the text normalization problem for English. The text normalization process involves first splitting complex tokens using a simple set of rules, and then classifying all tokens as one of their 23 categories using a decision tree. JTok is a configurable tokenizer for German, developed at DFKI by Joerg Steffen. It is part of "Heart of Gold", a XML-based middleware for integrating shallow and deep NLP components. It is a package comprising 4 tokenizers: White Space, Regex, Break Iterator and Sentence Tokenizer. [START_REF] Papageorgiou | A Unified Tagging Architecture and its Application to Greek[END_REF] discuss a regex-based tokenizer and sentence splitter that contains a list of abbreviations for Greek texts. [START_REF] Martínez | Text handling as a Web Service for the IULA processing pipeline[END_REF] have developed the IULA Processing Tool, a system for sentence splitting, tokenization and named-entity recognition of Spanish. The tool is based on rules which depend on a series of resources to improve obtained results: a grammatical phrase list, a foreign expression list, a follow-up abbreviation list, a word-form lexical database and a stoplist to increase lexical-lookup efficiency. Less-resourced languages are also investigated, as Hindi in [START_REF] Panchapagesan | Hindi Text Normalization[END_REF].

There is a greater need for work on text normalization, as it forms an important component of all areas of language and speech technology. The text normalization development can be carried out specifically for each language and/or task but this work is laborious and time consuming. However, for many languages there has not been any concerted effort on text normalization. In the context of genericity, producing reusable components for language-and-task-specific development is an important goal. The aim of this study was to create tools that would represent the common text normalization for many languages including less-resourced languages.

The primary goal of this paper is to present techniques and methods that can be used to efficiently develop text normalization resources and tools for new languages based on existing tools and resources. This study develops a method to normalize texts using a set of tools as language-and-task-independent as possible. This lets the possibility to add new languages with a significant time-reduction compared to the entire development of such tools. Current development involves: French, English, Spanish, Vietnamese, Khmer and Chinese.

The method is implemented in a toolkit which consists of a set of tools that are applied sequentially to the text corpora. The advantage of this modular approach is that we can develop easily and rapidly. Moreover, it is also possible to add some new tools, even modify and remove existent tools from the toolkit. The portability to a new language consists of heritage of all language independent tools and rapid adaptation of other language dependent tools. In the same way, for a new task, we can inherit from general processing tools, and adapt rapidly to create specific other tools. A specific XML scheme was designed for this purpose.

Next section describes the proposed text normalization workflow and implemented tools, section 3 describes the XML format used to work with these tools and section 4 is dedicated to the resource description and examples.

Text normalization

Overview

For normalization, rule-and regular expression-based systems are the norm, including the tokenizers in the RASP system [START_REF] Briscoe | The second release of the RASP system[END_REF], the LT-TTT tools [START_REF] Grover | LT TTT -A Flexible Tokenisation Tool[END_REF], the FreeLing tools [START_REF] Atserias | FreeLing 1.3: Syntactic and semantic services in an open-source NLP library[END_REF], and the Stanford tokenizer, which is based on Penn Treebank tokenization (included as part of the Stanford parser, [START_REF] Klein | Accurate Unlexicalized Parsing[END_REF].

The proposed text normalization solution undergoes a set of levels: these was divided in a set of modules which can be shared by various languages. Of course, in some cases a language implies to develop a specific module. In this case, this module is inserted in the generic process. First thing that should be made was to determine modules which are shared modules (the modules which do not depend on the language) and variable modules (the modules which depend on each language). This splitting and determination work is really important. For a new language modeling, we will inherit the shared modules and fastly adapt the variable modules to that language. It will economize the time consuming to build a complete corpus normalization. The key idea is to concentrate the language knowledge in a set of dictionaries and to develop modules which implement rules to deal with these knowledges.

Figure 1 summarizes the entire text normalization workflow. Gray boxes represent tools and White boxes represent resources. Normal fonts are used to mention shared modules or resourced while italic font is dedicated to language-specific entities.

A set of shared modules 2.2.1. Utterance segmentation

The first module implements an algorithm to split the text in utterances. It is a rule-based algorithm using punctuations and/or whitespace. The major part of rules are shared by many languages, and some specific rules are added for some languages. For example, the Chinese punctuation 。 is a non-ambiguous utterance segmentation mark.

Basic unit splitting

This module consists in a basic tokenization. Whitespace is used for some languages as French, Spanish or English. Like English and some South Asian languages Vietnamese also uses whitespace to tokenize a string of characters into a separate syllable. Then, for Vietnamese, this module splits into syllables which is the minimal unit. Character-based languages as Chinese are splitted into characters which is the minimal unit for this language. However, this basic segmentation is not adapted to the Khmer language.

Replacement

This module implements a dictionary look-up algorithm to replace a string by an other one. This module can be optionally used during the text normalization process. It can be used to replace some specific characters as for example:

• ° replaced by degrees (English), degrés (French), grados (Spanish), m c đ ứ ộ (Vietnamese), ដឺ េ្ក (Khmer), 度 (Chinese)

• is replaced by square (English), carré (French), quadrados (Spanish), bình ph ng ươ (Vietnamese), កេរ (Khmer), 平方 (Chinese) depending on the input language dictionary. This module can also be used to convert the character case when the 'upper/lower' function of the toolbox does not support the character encoding of the language. Here is a part of the Vietnamese dictionary used to lower characters:

• Ơ ơ • Ờ ờ • Ớ ớ • Ở ở • Ỡ ỡ • Ợ ợ
Obviously this upper/lower conversion is not relevant for Chinese. It is also not possible to apply this conversion if the upper (or lower) font or encoding does not exists for the given language.

Word Tokenization

This module fixes a set of rules to segment strings including punctuation marks. The algorithm split strings into words based on a dictionary and a set of rules which was established manually. For example, in French "trompe-l'oeil" (sham) is an entry in the vocabulary and it will not be segmented. On the other way, an entry like "l'oeil" (the eye) have to be segmented in 2 words. module is language-independent. Obviously, it is not relevant to apply it for Chinese.

Sticking

This module implements an algorithm to concatenate strings into words based on a dictionary with an optimization criteria: longest matching. This module can be applied only if a phrase vocabulary is created for the target language. Here is a set of words which are sticked with the character '_' by this algorithm:

• English: once_upon_a_time, game_over • French: au_fur_et_à_mesure, prix_nobel,

• Vietnamese: tính_nh m, câu_l c_b ẩ ạ ộ Chinese characters are grouped without adding a character to stick them:

• Chinese: 登记簿. Khmer character clusters are grouped using the '-' character:

• Khmer: សិ -ទ្ -ញ ្ -ណ. Unlike the character to stick, the algorithm of this module is completely language-independent.

Removing

This module can be applied to remove strings of a text. The list of strings to remove is fixed in a vocabulary file. This module is relevant for example to remove punctuation marks. The punctuation list is only encodingdependent (UTF8, iso-8859-1, etc) but not languagedependent.

Other tools

Text normalization is also a technical problem. Then, some other language-independent tools are necessary to format data depending on the input format: html, ascii or some other specific input format and encoding.

Language-specific modules

Unfortunately, the basic splitting (subsection 2.2.2) is not relevant to the Khmer language: there are no whitespace or other segmentation marks and characters are a too small unit. The character-cluster is a good basic unit as its segmentation is trivial because of its nonambiguities atomic structure. Then for this language, a character cluster (CC) segmentation is applied using rules created with linguistic knowledge, as illustrated in Figure 2. Word segmentation is then obtained by using the language-independent longuest matching algorithm to stick character clusters. The number to letter module is also an optional language-specific module. Current version includes 6 languages; for example, the number "123" is normalized as:

• French: cent vingt trois • English: one hundred twenty-three • Spanish: ciento veintitres • Vietnamese: m t trăm hai m i ba ộ ươ • Khmer: មួ យ រយ ៃម្ បី • Chinese: 一 百 二 十 三 Consequently, it is necessary to implement this module for each new language. However, algorithms to perform the transformation are close and a new implementation can be very fast with the help of already done tools.

Data format

The data format is based on the XML standard as it is currently a common practice. Among others we can cite that of LDC: the "LCTL Tokenized Text XML Files" 1 . An important feature in our XML format development was genericity: the proposed XML format can be used in various applications like: language modeling, statistical linguistics, information retrieval, machine translation... for any language. Then, for example, the LCTL proposes to fix the language name and the corresponding encoding as attributes of the entire text corpus. In our case, they are attributes of each sentence: <sent num="4"> <orig> Vi t Nam </ ệ orig> <elts id="word" length="1" lang="VN"> <wd num="1"><str> Vi t_Nam ệ </str></wd> </elts> <elts id="word" length="1" lang="FR"> <wd num="1"><str> Vietnam </str></wd> </elts> </sent> It is also possible to add alignments between the series of elements, with an alignment score, to deal with the machine translation application, for example: <sent num="1"> <orig> mot </orig> <elts id="target" length="1" lang="CN"> <wd num="1"> <str> 文字</str> </wd> </elts> <elts id="source" length="1" lang="FR"> <wd num="1"><str> mot </str></wd> </elts> <align idtgt="target" idsrc="source">  </align> </sent> To facilitate the technical tool development and also to facilitate queries on the corpus, we concentrated linguistic informations in elements and attributes are often used only to define properties like id. numbers, types, etc.

Results

Language resources

This modular approach implies to develop the following resources:

• a list of words: the vocabulary, used by the tool to tokenize (section 2.2.4); • optionally a list of phrases, used by the tool to stick (section 2.2.5); • optionally a list of character to replaced, used by the tool to replace (section 2.2.3); • optionally an upper-lower mapping dictionary, used by the tool to lower (section 2.2.3). All created resources described in this section was collected from free data on the web or free tools. The French vocabulary is made of 785k words (with upper and lower cases). The phrases vocabulary is made of 32k phrases created from frequent entries, and words containing spaces like "pomme de terre" (potato) and "petit à petit" (gradually) or city names like "Aix en Provence".

Text normalization resources are frequent for English, then, we did not focused on this language. The English vocabulary is made of 87k entries plus 500 phrases. The Spanish vocabulary is made of 370k words with only lower cases. The phrase vocabulary should be done in future work.

The Vietnamese vocabulary was collected and created from broadcast news on the web. It is made of about 13000 syllables (with upper and lower cases) and 600 words with several syllables separated with a '-' like "cavát" (tie). We also created a vocabulary made of 68k words. It includes words corresponding to several sticked syllables like " o t ng" ( Ả ưở illusion). The Khmer vocabulary we collected is made of 20,000 words. 16,000 was obtained from a numerical version of the official Khmer dictionary "Chhoun Nat". We also added 4000 words extracted from the manual segmentation of 1000 Khmer sentences. Similar to Chinese and Thai, Khmer is written without spaces between words. A sentence in Khmer ពណេសមដចេថខ could be segmented into ពណ|ស|េេមដច|ថ| េេខ (color | white | why | say | black) or ពណ|េសមដច|ថ| េេខ (color | king | say | black). A correct segmentation of a sentence into words requires the full knowledge of the vocabulary and of the semantics of the sentence. We estimated that the segmentation based on this vocabulary gives 95% of correct word segmentation.

The Chinese vocabulary is made of only 21k words and it will have to be improved in the future.

Output examples

The output of this work is an xml file with a text in a normalized form. First example of this paper is a French text with a tokenized utterance. We also included POStags to show that the xml format can easily be extended.

<?xml version="1.0" encoding="iso-8859-1"?> As a word tokenization can be ambiguous the data format proposed in this paper lets the possibility to keep all possible tokenizations, and eventually to provide some kind of links (or alignments) between tokenization variants. Next is a French example : <sent num="3"> <orig> Pomme de terre </orig> <elts id="target" length="3"> <wd num="1"><str> pomme </str></wd> <wd num="2"><str> de </str></wd> <wd num="3"><str> terre </str></wd> </elts> <elts id="source" length="1"> <wd num="1"><str> pomme_de_terre </str></wd> </elts> <align idtgt="target" idsrc="source">    </align> </sent>

Here is an example with a Vietnamese word made of 2 syllables which can be grouped into one word: <sent num="4"> <orig> Vi t Nam </ ệ orig> <elts id="syll" length="2"> <wd num="2"><str> Vi t ệ </str></wd> <wd num="3"><str> Nam </str></wd> </elts> <elts id="word" length="1"> <wd num="1"><str> Vi t_Nam ệ </str></wd> </elts> <align idtgt="syll" idsrc="word">   </align> </sent> Next example is the Chinese sentence: "August 29". In this example, numbers are transformed in their literal form:

Toolkit distribution and applications

The system (tools and resources) is available online [START_REF] Bigi | [END_REF] as open source under the terms of the GNU GPL license. The tool was designed for research purposes so it is presented as a set of scripts using the gawk language. The major benefit of such a tool is that it allows to rapidly process a very large text corpus with several millions of documents from different sources. For example, one year of the French newspaper "Le Monde" (about 20 million words) was normalized in about 2 hours 30 minutes with a 2009-Desktop PC (Intel Xeon 2.6 Ghz with hard drive SATA 7200 RPM).

This toolkit was successfully applied for statistical language modeling in Automatic Speech Recognition systems: in French [START_REF] Lamy | Premiers pas du CLIPS sur les données d'évaluation ESTER[END_REF], in Vietnamese [START_REF] Le | Recent advances in Automatic Speech Recognition for Vietnamese[END_REF] and in Khmer [START_REF] Seng | Which unit for acoustic and language modeling for Khmer Automatic Speech Recognition[END_REF]. It was also used for the development of a French-Vietnamese translation system [START_REF] Do | Mining a comparable text corpus for a Vietnamese-French machine translation system Fourth Workshop on Statistical Machine Translation (WMT)[END_REF].

Conclusion

In principle, any system that deals with unrestricted text need the text to be normalized. Text normalization is a very important issue for Natural Language Processing applications. This paper presented a text normalization system entirely designed to handle multiple languages and/or tasks with the same algorithms and the same tools. Hence, we hope this work will be helpful in the future to open to new practices in the methodology and tool developments: thinking problems with a generic multilingual aspect.

Fig 1 :

 1 Fig 1: Text normalization workflow

Fig 2 :

 2 Khmer segmentation example

http://www.ldc.upenn.edu/Creating/creating_annotated.shtml#DTDs