St Éphane Laurent

The reversed discrete hazard rate and the scaled entropy of a discrete measure

Keywords: Entropy, Error probability, Fano's inequality, Reversed hazard rate

, comes down to the calculation of the scaled entropy of (µn) n 0 in the case when µn is the normalised truncation to {0, . . . , n} of an unbounded measure µ on N, and we especially study this case. We provide some results involving the reversed hazard rate of µ, which is useful to investigate the asymptotics of H(Xn).

INTRODUCTION

The original motivation of the present paper is the problem of the calculation of the scaled entropy of the next-jump time filtrations, which is exposed in [START_REF] Laurent | Uniform entropy scalings of filtrations[END_REF]. It is shown in [START_REF] Laurent | Uniform entropy scalings of filtrations[END_REF] that this problem exactly comes down to the problem of the calculation of the scaled entropy h c (µ) of a discrete measure µ on N, which is introduced and studied in the present paper. The problem of the calculation of h c (µ) is interesting in itself, and the present paper is totally independent of [START_REF] Laurent | Uniform entropy scalings of filtrations[END_REF]. This problem is related to the following one. Consider a sequence (X n ) n 0 of random variables (not necessarily defined on the same probability space) taking only finitely many values. When (F n ) n 0 is a sequence of random variables satisfying (i) F n is a measurable function of

X n ; (ii) Pr(X n = F n ) ---→ n→∞ 0;
then does (iii) H(Fn) H(Xn) ---→ n→∞ 1 necessarily hold true? It is not difficult to construct some examples of two sequences of random variables (X n ) n 0 and (F n ) n 0 taking only finitely many values and such that (i) and (ii) hold but not (iii). The above problem is to find some criteria on (X n ) n 0 ensuring that (iii) holds for every sequence (F n ) n 0 satisfying (i) and (ii). This problem is related to the interplay between conditional entropy and error probability, because H(Fn) H(Xn) → 1 follows from (i) and (ii) under conditions like

H(X n | F n ) H(X n ) = O Pr(X n = F n ) , (1.1)
as we will note in Section 2 (Lemma 2.6). The present paper especially addresses this problem in the case when X n is distributed on {0, . . . , n} according to µ(• | 0 : n), the normalised truncation to {0, . . . , n} of a given measure µ on N, because this is the situation appearing in the problem of the calculation of the scaled entropy of the next-jump time filtrations. For example, condition (1.1) holds when X n has the uniform distribution on {0, . . . , n}, that is to say, when µ is the counting measure on N. This is a consequence of Fano's inequality. The generalization of Fano's inequality in a way that would imply property (1.1) is for example addressed in [START_REF] Han | Generalizing the Fano inequality[END_REF]. However the authors of [START_REF] Han | Generalizing the Fano inequality[END_REF] only noted that in Fano's inequality

H(X n | F n ) h Pr(X n = F n ) + Pr(X n = F n ) log(n + 1),
it is not possible in general to replace log(n + 1) (the entropy of X n in the case of the counting measure) with H(X n ), and this is more than desired in order to get (1.1).

The possible failure of (iii) under (i) and (ii) even shows that there is no universal constant C > 0 such that one could replace log(n + 1) with C × H(X n ) in Fano's inequality.

While related to the interplay between conditional entropy and error probability, the present paper is not oriented towards the derivation of conditions such as (1.1). Denoting by µ n the law of X n , we introduce the scaled entropy h c (µ n ) n 0 ) and the lower scaled entropy h - c (µ n ) n 0 ) of the sequence of probability measures (µ n ) n 0 . The index c in this notation is a function c : N → (0, +∞) called an entropy scaling (for short, a scaling). Roughly speaking, the two equalities h c (µ n ) n 0 ) = h - c (µ n ) n 0 ) = 1 occur when it is possible to approximate X n by a random variable F n having entropy H(F n ) ≈ c(n), and this is the optimal approximation in the sense that it is not possible to have an approximation with lower entropy. This property in the case of the scaling c(n) = H(X n ) characterizes the introductory problem: it holds if and only if conditions (i) and (ii) always imply condition (iii) (Proposition 2.5). Our investigations about the scaled entropies h c (µ n ) n 0 ) and h - c (µ n ) n 0 ) for a general sequence (µ n ) n 0 of finitely supported probability measures are the contents of Section 2. In Section 3, we introduce the reversed hazard rate (for short, the RHR) of a measure µ on N. The asymptotic behaviour of the RHR of µ is related to the asymptotic behaviour of the entropy of µ n = µ(• | 0 : n). Section 4 deals with the scaled entropies h c (µ n ) n 0 ) and h - c (µ n ) n 0 ) , shorter denoted by h c (µ) and h - c (µ), in the case when µ n = µ(• | 0 : n) for a measure µ on N. The RHR of µ will be involved in this section: we will give a condition involving the RHR of µ and ensuring the property h - c (µ) = h c (µ) = 1 for the scaling c(n) = H(X n ). We also provide some non-trivial examples for which the property

h - c (µ) = h c (µ) = 1 holds for a scaling c(n) ∼ H(X n ).
Section 5 is not related to the scaled entropy. It provides some complements about the RHR. In particular we show how the monotonicities of the RHR and the (direct) hazard rate of a N-valued random variable X are related to the monotonicities in n of the conditional entropies H(X | X n) and H(X | X n).

SCALED ENTROPY OF A SEQUENCE OF FINITELY

SUPPORTED PROBABILITIES

Throughout this section, we consider a sequence (µ n ) n 0 of probability measures on N. We denote by E n ⊂ N the support of µ n and by X n a random variable distributed on E n according to µ n . We assume that E n is finite and µ n is not degenerate for every n 1, that is to say, #E n 2.

Definitions

Define the ǫ-entropy of a discrete random variable Y by

H ǫ (Y ) = inf H(F ) | Pr(F = Y ) ǫ ,
where the infimum is taken over σ(Y )-measurable (hence discrete) random variables F . When Y takes its values in N, one can restrict the random variables F to those taking their values in N ∪ {∞}. Indeed, if F takes more than one value not belonging to N, one obtains a random variable F ′ having lower entropy than F by grouping these values into a single one 1 , and the probability Pr(F = Y ) does not increase when one replaces F with F ′ . Of course, for the same reason, one can restrict the random variables F to the N-valued random variables, but taking N ∪ {∞} as the state space of F is convenient, as we will see in the examples of Section 4.3. As a consequence, since one can fix the state space of the random variables F , one can replace the infimum with the minimum in H ǫ (Y ) in the case when Y takes only finitely many values. Now, let c : N → [0, +∞) be a function such that c(n) > 0 for n large enough. We say that c is an entropy scaling or, for short, a scaling, and we define the scaled entropy of

(µ n ) n 0 by h c ((µ n ) n 0 ) := lim ǫ→0 lim sup n→∞ H ǫ (X n ) c(n) ,
and the lower scaled entropy of (µ n ) n 0 by

h - c ((µ n ) n 0 ) := lim ǫ→0 lim inf n→∞ H ǫ (X n ) c(n) .
These limits as ǫ goes to 0 exist because H ǫ (X n ) increases as ǫ decreases, hence these are increasing limits. Note the obvious inequality

h - c ((µ n ) n 0 ) h c ((µ n ) n 0 ), and the inequality h c ((µ n ) n 0 ) 1 for the scaling c(n) = log #E n . Also note that h - c ((µ n ) n 0 ) = h - c ′ ((µ n ) n 0 ) and h c ((µ n ) n 0 ) = h c ′ ((µ n ) n 0 ) when c ′ is a scaling equivalent to c, that is to say, when c(n) c ′ (n) → 1 (we denote that by c(n) ∼ c ′ (n)).
The following lemma provides an alternative ǫ-entropy Hǫ that can be used instead of H ǫ in the definition of the scaled entropies. The ǫ-entropy H ǫ is appropriate to derive an upper bound of

h - c ((µ n ) n 0 ) or h c ((µ n ) n 0 ) (Lemma 2.
3). The alternative ǫ-entropy Hǫ is useful to derive a lower bound, which is more difficult. For instance we will prove Lemma 2.9 and Proposition 2.12 with the help of Hǫ .

Lemma 2.1. Define the alternative ǫ-entropy of a discrete random variable Y by

Hǫ (Y ) = inf - i∈B ν(i) log ν(i) -ν(B c ) log ν(B c )
where ν is the law of Y and the infimum is taken over all subsets B of the state space of Y satisfying ν(B c ) ǫ. Then,

for ǫ < 1/2, Hǫ (Y ) -h(ǫ) H ǫ (Y ) Hǫ (Y )
where h is the binary entropy function, defined by

h(ǫ) = -ǫ log ǫ -(1 -ǫ) log(1 -ǫ).
Proof: We denote by H(P ) the right member in the definition of Hǫ (Y ), where it is understood that P is the partition of the state space of Y made of the subset B c and the singletons {i} for i ∈ B. Let P be a such a partition. Define f (y) = y if y ∈ B and f (y) = ∞ if y ∈ B (where ∞ denotes a value outside the support of the law of Y ), and set

F = f (Y ). Then Pr(F = Y ) = ν(B c
) and H(F ) = H(P ). That shows the inequality Hǫ (Y ) H ǫ (Y ). Conversely, take a random variable F having form F = f (Y ) for some function f , and such that Pr(F = Y ) < ǫ. Define the set B = y | f (y) = y}. The law ν of Y can be written as the convex combination

ν = ν(B)ν(• | B) + ν(B c )ν(• | B c ).
Therefore the law of F is the same convex combination of the two image measures

(f * ν)(• | B) = ν(• | B) and (f * ν)(• | B c
), and as a consequence of the concavity of the entropy,

H(F ) ν(B)H ν(• | B) = - i∈B ν(i) log ν(i) + ν(B) log ν(B) = H(P ) -h ν(B) H(P ) -h(ǫ)
as long as ǫ < 1/2. That shows the inequality

H ǫ (Y ) Hǫ (Y ) -h(ǫ).
Note that, obviously, one can replace the infimum with the minimum in the definition of Hǫ (Y ) when Y takes only finitely many values.

Properties

We firstly note a property of the scaled entropy in the case when the sequence of measures converges. In Section 4, where we focus on the case when µ n = µ(• | 0 : n) for a measure µ, this lemma will assist us in arguing that the scaled entropy has no interest in the case when µ is bounded.

Lemma 2.2. Assume that µ n converges to a probability measure µ ∞ as n → ∞. Then h c (µ n ) n 0 = 0 for any scaling c satisfying c(n) → ∞.

Proof: To prove the lemma, we use the ǫ-entropy Hǫ (X n ) defined in Lemma 2.1. Take ǫ > 0 and an integer n 1. Define

G n (ǫ) = min k 0 | µ n (0 : k) 1 -ǫ . For ǫ < exp(-1), Hǫ (X n ) - Gn(ǫ) i=0 µ n (i) log µ n (i) -ǫ log ǫ.

Now, define

G(ǫ) = min k 0 | µ ∞ (0 : k) 1 -ǫ .
One has G n (ǫ) ---→ n→∞ G(ǫ) as long as ǫ is a continuity point of G. Therefore, for such an ǫ, -

Gn(ǫ) i=0 µ n (i) log µ n (i) ---→ n→∞ - G(ǫ) i=0 µ ∞ (i) log µ ∞ (i)
and

Hǫ (Xn) c(n) → 0 whenever c(n) → ∞.
Since there exists a sequence of continuity points of G going to 0, one gets

h c (µ n ) n 0 = 0.
Therefore, with the notations of the previous lemma,

h c (µ n ) n 0 = 0 for the scaling c(n) = H(X n ) when H(µ ∞ ) = ∞, because H(µ n ) → ∞ in this case 2 . In the situation µ n = µ(• | 0 : n) studied in Section 4, we will see that h - c (µ n ) n 0 = 1 for the scaling c(n) = H(X n ) when H(µ ∞ ) < ∞ (Lemma 4.1
), but this is not always true in the general situation. The rest of this section is devoted to giving some properties of the scaled entropies, mainly oriented towards the situation when

h - c (µ n ) n 0 = h c (µ n ) n 0 = 1 for the scaling c(n) = H(X n ). Note that h - c (µ n ) n 0 = h c (µ n ) n 0 = 1 is equivalent to h - c (µ n ) n 0 = 1 for this scaling.
Hereafter, we will say that a sequence (F n ) n 0 of random variables is a lower approximation of (X n ) n 0 if F n is σ(X n )-measurable for every n 0 and Pr(X n = F n ) → 0.

The following lemma provides a way to get upper bounds of the scaled entropies.

Lemma 2.3. Let c be a scaling.

1) For every lower approximation

(F n ) n 0 of (X n ) n 0 , h c (µ n ) n 0 lim sup n→∞ H(F n ) c(n) .
2) Let (n k ) k 1 be a strictly increasing sequence in N. and let (F n k ) k 1 be a sequence of random variables such that

σ(F n k ) ⊂ σ(X n k ) and Pr(X n k = F n k ) → 0 as k → ∞. Then h - c (µ n ) n 0 lim inf k→∞ H(F n k ) c(n k ) .
Proof: Let ǫ ∈ (0, 1). Take an integer N 0 sufficiently large in order that Pr(X n = F n ) < ǫ for every n N . Then H ǫ (X n ) H(F n ) for every n N . The first assertion follows from this inequality. To prove the second assertion, take an integer K 0 sufficiently large in order that Pr(X

n k = F n k ) < ǫ for every k K. Then H ǫ (X n k )
H(F n k ) for every k K, and the second assertion follows from this inequality. The following lemma will help us in the proof of the next proposition.

Lemma 2.4. Assume h

- c (µ n ) n 0 < ∞.
For every δ > 0, there exists a strictly increasing sequence (n k ) k 1 in N, and a sequence

(F n k ) k 1 of random variables such that σ(F n k ) ⊂ σ(X n k ) and Pr(X n k = F n k ) → 0 as k → ∞, such that lim sup k→∞ H(F n k ) c(n k ) h - c (µ n ) n 0 + δ.
Proof: Take a sequence (ǫ k ) k 1 in (0, 1) that goes to 0 as k → ∞, and such that

h - c (µ n ) n 0 = lim k→∞ lim inf n→∞ H ǫ k (X n ) c(n) .
Take δ > 0 and an integer K 1 such that

lim inf n→∞ H ǫ k (X n ) c(n) h - c (µ n ) n 0 + δ 2
for every k K. Now, take a strictly increasing sequence of integers (n k ) k 1 such that

H ǫ k (X n k ) c(n k ) lim inf n→∞ H ǫ k (X n ) c(n) + δ 2
for every k 1. Finally take a random variable

F n k such that H ǫ k (X n k ) = H(F n k ).
The following proposition shows that the introductory problem of Section 1 comes down to the equality

h - c (µ n ) n 0 = 1 for the scaling c(n) = H(X n ).
Proposition 2.5. Let c be the scaling defined by c

(n) = H(X n ). 1) If h c (µ n ) n 0 = 1, then lim sup n→∞ H(F n ) H(X n ) = 1
for every lower approximation

(F n ) n 0 of (X n ) n 0 . 2) If h - c (µ n ) n 0 = 1, then H(F n ) H(X n ) ---→ n→∞ 1
for every lower approximation

(F n ) n 0 of (X n ) n 0 . 3) If H(Fn) H(Xn) ---→ n→∞ 1 for every lower approximation (F n ) n 0 of (X n ) n 0 , then h - c (µ n ) n 0 = h c (µ n ) n 0 = 1.
Proof: Take a lower approximation

(F n ) n 0 of (X n ) n 0 . Given ǫ > 0, the inequality H ǫ (X n ) H(F n ) holds for n large enough, therefore lim sup n→∞ H ǫ (X n ) H(X n ) lim sup n→∞ H(F n ) H(X n ) 1.
The first assertion follows by passing to the limit in ǫ. One also has

lim inf n→∞ H ǫ (X n ) H(X n ) lim inf n→∞ H(F n ) H(X n ) lim sup n→∞ H(F n ) H(X n ) 1.
Assuming h - c (µ n ) n 0 = 1, one gets H(Fn) H(Xn) → 1 by passing to the limit in ǫ, thereby showing the second assertion. Now, in order to prove the third assertion, take δ > 0. Since h - c (µ n ) n 0 1, one can apply Lemma 2.4. One has a strictly increasing sequence

(n k ) k 1 in N and a sequence (F n k ) k 1 of random variables such that σ(F n k ) ⊂ σ(X n k ) and Pr(X n k = F n k ) → 0 as k → ∞, and such that lim sup k→∞ H(F n k ) H(X n k ) h - c (µ n ) n 0 + δ.
For every n 0 that does not belong to the sequence

(n k ) k 1 , set F n = X n . Then (F n ) n 0 is a lower ap- proximation of (X n ) n 0 . By the assumption of the third assertion, H(Fn) H(Xn) ---→ n→∞ 1. Therefore H(Fn k ) H(Xn k ) ---→ k→∞ 1. Thus, h - c (µ n ) n 0 1 -δ. A first sufficient condition for h - c (µ n ) n 0 = 1 in the case of the scaling c(n) = H(X n ),
relating the conditional entropy to the error probability, is given in the following lemma.

Lemma 2.6. If there exists an increasing function g on [0, 1] such that g(0 + ) = 0 and such that for n large enough, the inequality

H(X n | F n ) H(X n ) g Pr(X n = F n ) holds for every σ(X n )-measurable random variable F n , then h - c (µ n ) n 0 = 1 for the scaling c(n) = H(X n ).
Proof: Let ǫ ∈ (0, 1). For every n 0, one has

H ǫ (X n ) = H(F n ) where F n is a σ(X n )-measurable ran- dom variable achieving the minimum in the definition of H ǫ (X n ). By the conditional entropy formula H(X n ) = H(F n )+H(X n | F n )
and by the assumption of the lemma,

1 -g(ǫ) H ǫ (X n ) H(X n ) 1,
for n large enough. The lemma follows by passing to the limits.

The following proposition follows from the previous lemma and Fano's inequality.

Proposition 2.7. If H(X n ) = Ω(log #E n ), then the equality h - c (µ n ) n 0 = 1 holds for the scaling c(n) = H(X n ).
Proof: By Fano's inequality (see [START_REF] Gray | Entropy and Information Theory[END_REF]),

H(X n | F n ) h Pr(X n = F n ) + Pr(X n = F n ) log(#E n ).
Therefore the hypothesis of Lemma 2.6 holds under the hypothesis

H(X n ) = Ω(log #E n ).
Example 2.8 (Uniform probabilities). Let µ n be the uniform probability on {0, . . . , n} for every n 0. Then the previous proposition shows that

h - c (µ n ) n 0 = 1 for the scaling c(n) = H(X n ).
One can also derive Proposition 2.7 from the following lemma. We will not use this lemma, but it provides an interesting sufficient condition for the equality

h - c (µ n ) n 0 = 1 in the case of the scaling c(n) = H(X n ).
Lemma 2.9. Assume that

sup n 1 max Cn⊂En Cn =∅ H µ n (• | C n ) H(µ n ) < ∞. Then h - c (µ n ) n 0 = 1 for the scaling c(n) = H(X n ). Proof: Let n 1 and ǫ ∈ (0, 1). Let B n ⊂ E n achieving the minimum in the definition of the ǫ-entropy Hǫ (X n ) defined in Lemma 2.1. We denote by B c n the complement of B n in E n . One has H(X n ) = - i∈Bn µ n (i) log µ n (i) - i∈B c n µ n (i) log µ n (i), Hǫ (X n ) = - i∈Bn µ n (i) log µ n (i) -µ n (B c n ) log µ n (B c n ),
and

- i∈B c n µ n (i) log µ n (i) = µ n (B c n )H µ n (• | B c n ) -µ n (B c n ) log µ n (B c n ) ǫH µ n (• | B c n ) -µ n (B c n ) log µ n (B c n ). Therefore H(X n ) Hǫ (X n ) + ǫH µ n (• | B c n )
. This implies, denoting by K 0 the finite number of the lemma,

H(X n ) Hǫ (X n ) 1 -Kǫ when ǫ < 1/K. Finally, for ǫ small enough, Hǫ (X n ) H(X n ) 1 1 1 -Kǫ Hǫ (X n ) H(X n ) ,
and the lemma follows by passing to the limits. Remark 2.10. The condition of Lemma 2.9 actually pertain to the ratios

H µn(•|Cn) H(µn)
for the "small" subsets C n ⊂ E n . That is to say, this condition holds whenever the condition

sup n 1 max Cn⊂En Cn =∅ µn(Cn)<ǫ 0 H µ n (• | C n ) H(X n ) < ∞
holds for some ǫ 0 ∈ (0, 1). Indeed, the concavity of the entropy gives the inequality

H(µ n ) µ n (C n )H µ n (• | C n ) .
Therefore the ratios

H µn(•|Cn) H(µn)
are lower than 1 ǫ 0 for the subsets C n such that µ n (C n ) ǫ 0 . The following elementary lemma will help us to prove Proposition 2.12. Both this lemma and this proposition will be used in Section 4.3 to derive some nontrivial examples for which the equality h

- c (µ n ) n 0 = h c (µ n ) n 0 = 1 holds for a scaling c(n) ∼ H(X n ) and to get the values of h - c (µ n ) n 0 and h c (µ n ) n 0 for the scaling c(n) = H(X n ). Lemma 2.11. Let B n be a subset of E n for every n 0 and assume that Pr(X n ∈ B n ) → 1. Define the lower approxima- tion (F n ) n 0 of (X n ) n 0 by setting F n = X n if X n ∈ B n and F n = ∞ otherwise. If lim inf n→∞ H µ n (• | B n ) > 0, then H(F n ) ∼ H µ n (• | B n ) .
Proof: The entropy of F n is

H(F n ) = - i∈Bn Pr(X n = i) log Pr(X n = i) -µ n (B c n ) log µ n (B c n ) = -µ n (B n ) i∈Bn Pr(X n = i) µ n (B n ) log Pr(X n = i) µ n (B n ) -µ n (B n ) log µ n (B n ) -µ n (B c n ) log µ n (B c n ) = µ n (B n )H µ n (• | B n ) + h µ n (B n ) .
The entropies H µ n (• | B n ) are bounded from below by a positive number for all integers n large enough, because of the assumption

lim inf n→∞ H µ n (• | B n ) > 0. Hence H(F n ) H µ n (• | B n ) = µ n (B n ) + h µ n (B n ) H µ n (• | B n ) n→∞ ---→ 1 because µ n (B n ) → 1.
Proposition 2.12. Let B n be a subset of E n for every n 0 and such that Pr(

X n ∈ B n ) → 1. Assume that #B n → ∞ and H µ n (• | B n ) ∼ log #B n . Then h - c (µ n ) n 0 = h c (µ n ) n 0 = 1 for the scaling c(n) = log #B n . Proof: We firstly check the inequality h c (µ n ) n 0 1. Define the lower approximation (F n ) n 0 of (X n ) n 0 by setting F n = X n if X n ∈ B n and F n = ∞ otherwise. By Lemma 2.11, H(F n ) ∼ H µ n (• | B n ) ∼ log #B n , and this implies h c (µ n ) n 0 1 by Lemma 2.3. To show that h - c (µ n ) n 0 1,
we use the ǫ-entropy Hǫ (X n ) defined in Lemma 2.1. Given ǫ ∈ (0, 1), we denote by C n ⊂ E n the subset achieving Hǫ (X n ). One has

Hǫ (X n ) - i∈Cn µ n (i) log µ n (i) - i∈Cn∩Bn µ n (i) log µ n (i).
To estimate the right-hand side, we split the sum:

- i∈Cn∩Bn µ n (i) log µ n (i) = - i∈Bn µ n (i) log µ n (i) + i∈Bn∩C c n µ n (i) log µ n (i).
We transform the first term:

- i∈Bn µ n (i) log µ n (i) = -µ n (B n ) i∈Bn µ n (i) µ n (B n ) log µ n (i) µ n (B n ) -µ n (B n ) log µ n (B n ) = µ n (B n )H µ n (• | B n ) -µ n (B n ) log µ n (B n ).
Therefore, since

H µ n (• | B n ) ∼ log #B n , lim n→∞ -i∈Bn µ n (i) log µ n (i) log #B n = 1.

Now the second term equals

0 if B n ∩ C c n = ∅, otherwise - i∈Bn∩C c n µ n (i) log µ n (i) = -µ n (B n ∩ C c n ) i∈Bn∩C c n µ n (i) µ n (B n ∩ C c n ) log µ n (i) µ n (B n ∩ C c n ) -µ n (B n ∩ C c n ) log µ n (B n ∩ C c n ) = µ n (B n ∩ C c n )H µ n (• | B n ∩ C c n ) -µ n (B n ∩ C c n ) log µ n (B n ∩ C c n ) ǫH µ n (• | B n ∩ C c n ) -ǫ log ǫ for ǫ < exp(-1). Consequently, since H µ n (• | B n ∩C c n ) log #B n , lim sup n→∞ -i∈Bn∩C c n µ n (i) log µ n (i) log #B n ǫ.
Finally,

lim inf n→∞ Hǫ (X n ) log #B n 1 -ǫ,
and taking the limit in ǫ, we get

h - c (µ n ) n 0 1.

REVERSED HAZARD RATE OF A DISCRETE MEA-

SURE

Let µ be a possibly unbounded measure on N = {0, 1, . . .}. In the next section, we will investigate the scaled entropies h - c (µ n ) n 0 and h c (µ n ) n 0 in the case when µ n = µ(• | 0 : n), the normalized truncation of µ to {0, . . . , n}. Our results will involve the reversed hazard rate of µ, which is the object of the present section. We assume that the measure µ is finite in the sense that µ(B) < ∞ for every finite set B ⊂ N, but µ(N) is possibly infinite. Unless we mention something else, we will always assume that the support of µ is {0, . . . , N } for an integer N 1, or the whole set of integers N, which agrees with N = ∞. We will mainly deal with the case N = ∞. When B ⊂ {0, . . . N } is a set such that µ(B) < ∞, we denote by µ(• | B) the probability measure on B obtained by truncating µ to B, and then by normalizing in order to assign a total mass of 1 to B.

The reversed hazard rate

Throughout the paper, when the measure µ is understood, we set

ρ k = µ(k) µ(0 : k) .
for every integer k 0. We say that the sequence (ρ k ) k 0 is the reversed hazard rate of µ (for short, the RHR). There are several papers about the RHR, mainly for continuous distributions (see [START_REF] Di Crescenzo | Extensions of the past lifetime and its connections to the cumulative entropy[END_REF] and references given therein).

Note that ρ 0 = 1 and 0 < ρ k < 1 for every integer k 1, except for integers k > N when µ has a finite support (case N < ∞), because ρ k = 0 when k > N in this case.

The RHR ρ only determines µ up to proportionality. Indeed, it is not difficult to get the equality

µ(k) µ(0) = ρ k (1 -ρ 1 ) • • • (1 -ρ k ) , (3.1)
for k 1, showing that µ is entirely determined by ρ once the value of µ(0) is known. The RHR entirely characterizes µ in the case when µ(N) is finite and known, for example in the probability case µ(N) = 1. Indeed, it is also easy to derive the equality

µ(0 : k) µ(0) = 1 (1 -ρ 1 ) • • • (1 -ρ k ) . (3.2)
Therefore, assuming µ(N) < ∞, letting k → ∞ in the previous equality provides the equality

µ(0) = µ(N) N k=1 (1 -ρ k ), (3.3)
where the product is a convergent infinite product in the case N = ∞. Thus µ(0) and consequently µ are uniquely determined once both the RHR and the finite total mass µ(N) are known.

An appealing convenience of the RHR is its ability to provide all the probability measures µ n = µ(• | 0 : n) by simple formulas. This is shown by the following theorem, which is derived from the previous formulas and by simply noting that the RHR of µ(• | 0 : n) coincides with the RHR of µ for every integer in {0, . . . , n}. Recall that we denote by X n a random variable distributed according to µ n .

Theorem 3.1.

1) The probability masses of X n are given by

Pr(X n = k) = (1 -ρ n ) • • • (1 -ρ k+1 )ρ k ,
and the cumulative probability masses of X n are given by

Pr(X n k) = (1 -ρ n ) • • • (1 -ρ k+1 )
for every k ∈ {0, . . . , n}. 2) In the case N = ∞, there is an equivalence between µ(N) < ∞ and the convergence (non-zero limit) of the product (1 -ρ n ), or equivalently the convergence of the series ρ n . In this case, the above formulas also hold for a random variable X ∞ distributed on N according to µ(• | N), the normalized version of µ.

Proof: The expression of Pr(X n = k) is obtained from equality (3.1) and equality (3.3), and the expression of Pr(X n k) is obtained from equality (3.2) and equality (3.3). The second assertion stems from the expression of Pr(X n k).

In the case when ρ n → 0 and ρ n = ∞, we will pay attention to the convergence of the series ρ 2 n , because of the relation between the present paper and the scaled entropy of the next-jump time filtrations ( [START_REF] Laurent | Uniform entropy scalings of filtrations[END_REF]). The nextjump time filtration F corresponding to the RHR (ρ n ) n 0 is the one defined in [START_REF] Laurent | Standardness and nonstandardness of next-jump time filtrations[END_REF] and [START_REF] Laurent | Uniform entropy scalings of filtrations[END_REF] by the sequence of jumping probabilities (p n ) n 0 given by p n = ρ -n . The divergence ρ n = ∞ is a necessary and sufficient condition for the filtration F to be Kolmogorovian. The case when F is Kolmogorovian and non-standard corresponds to the situation when the two conditions ρ n = ∞ and ρ 2 n < ∞ hold. In this case, as shown in [START_REF] Laurent | Uniform entropy scalings of filtrations[END_REF], the scaled entropy h c (F) of F coincides with the scaled entropy h c (µ) of µ (Section 4). This is why we will pay attention to the convergence of the series ρ 2 n . The following lemma shows that the asymptotic behaviour of the RHR pertains to the tail of µ in the case when µ is not normalisable (hence N = ∞). Given an integer M 1, the measure µ |(M :∞) , in other words the restriction of µ to the tail set (M : ∞), has support {M, M + 1, . . .} and we previously defined the RHR only for measures whose support is an interval of N starting at 0. But it is understood we similarly define the RHR of µ |(M :∞) starting at k = M . Lemma 3.2. When µ(N) = ∞, the RHR of µ and the RHR of its restriction µ |(M :∞) are equivalent at ∞ for any integer M 1.

Proof: The value of the RHR of

µ |(M :∞) at k M is µ(k) µ(M : k) = ρ k 1 1 -µ([0,M [) µ([0,k]) ∼ k→∞ ρ k .
The formula in the above proof also provides the following bounds around the value of the RHR of µ |(M :∞) at k M :

ρ k µ(k) µ(M : k) ρ k 1 1 -µ([0,M [) µ([0,M ]) = ρ k ρ M . ( 3.4)
Below we give some examples when µ is given, and some examples when the RHR is given.

Example 3.3 (Counting measure).

Let µ be the uniform measure on {0, . . . , N }, or the counting measure on N.

Then ρ n = 1 n+1 for every n ∈ {0, . . . , N }. Example 3.4 (Power measure). Let µ be the measure on N defined by µ(n) = (n + 1) a for a > -1. Then ρ n ∼ a+1 n . Example 3.5 (Geometric measure). Let µ be the geometric measure on N given by µ(n) = a n where a > 0 and a = 1. Then

ρ n = (1 -a)a n 1 -a n+1
. The ρ n are decreasing in n and ρ n ∼ (1 -a)a n → 0 when a < 1, whereas ρ n → a-1 a when a > 1. It could be clearer to write ρ n = θ 1-(1-θ) n+1 when a > 1, where θ = a-1 a = lim ρ n . In the case a < 1, the measure µ is proportional to the usual geometric distribution on N with probability of success 1 -a, and then (ρ n ) n 0 is the RHR of the geometric distribution.

Example 3.6 (Constant RHR).

Let ρ n ≡ θ ∈ (0, 1) for every n 1. Then, because of formula (3.1), the corresponding measures µ are the ones satisfying µ(n) = µ(0)θ(1 -θ) -n for n 1. Up to a correction at n = 0, this is the geometric measure of the previous example with a = 1/(1 -θ) > 1.

Expectation representation of the entropy

Throughout this section, it is understood that the X n are the random variables appearing in Theorem 3.1, and, for convenience, we agree with X n = X N for n N in the case N < ∞. The conditional entropy formula gives

H(X n+1 ) = H(X n+1 | 1 X n+1 =n+1 ) + H 1 X n+1 =n+1 = H(X n+1 | X n+1 = n + 1) Pr(X n+1 = n + 1) + H 1 X n+1 =n+1 ,
and since the law of X n is the conditional law of X n+1 given the event {X n+1 = n + 1}, we get the recurrence relation

H(X n+1 ) = (1 -ρ n+1 )H(X n ) + h(ρ n+1 ), (3.5)
where

h(θ) = -θ log θ -(1 -θ) log(1 -θ)
is the entropy of a Bernoulli trial with probability of success θ. It is interesting to view the recurrence formula (3.5) as a weighted average of H(X n ) and h(ρ n+1 ) ρ n+1 :

H(X n+1 ) = (1 -ρ n+1 )H(X n ) + ρ n+1 h(ρ n+1 ) ρ n+1 .
This recurrence relation yields the following proposition, which concerns only measures µ having infinite total mass because ρ n → 0 when µ has a finite total mass.

Proposition 3.7. If ρ n → ρ ∞ > 0 in the case N = ∞, then H(X n ) → h(ρ ∞ ) ρ ∞ .
Proof: Starting with relation (3.5), one gets

lim sup H(X n ) = lim sup ((1 -ρ n+1 )H(X n )) + h(ρ ∞ ) = (1 -ρ ∞ ) lim sup H(X n ) + h(ρ ∞ ),
therefore lim sup H(X n ) = h(ρ∞) ρ∞ , and in the same way one gets the same equality for lim inf H(X n ).

Example 3.8 (Geometric measure). Take the geometric measure of Example 3.5. When a > 1, as we said in this example,

ρ n → θ = a-1 a > 0, therefore we get lim H(X n ) = h(θ)
θ by applying the proposition. We will derive lim n→∞ H(X n ) in the case a < 1 in the next example, with the help of the expectation represen-tation (3.6) we derive now. The recurrence relation (3.5) provides the equality

H(X n ) = h(ρ n ) + (1 -ρ n )h(ρ n-1 ) +(1 -ρ n )(1 -ρ n-1 )h(ρ n-2 ) + • • • + (1 -ρ n ) • • • (1 -ρ 2 )h(ρ 1 )
which can be written

H(X n ) = E h(ρ Xn ) ρ Xn (3.6)
by virtue of the expression of Pr(X n = k) given in Theorem 3.1. Also note that

H(X n ) → H(X ∞ ) in the case when µ is normalisable, just because of H(X n ) = H(X ∞ | X ∞ n) and Pr(X ∞ n) → 1.
For the same reason, the expectation representation (3.6) also holds for n = ∞ in the case of a normalisable measure µ. The function x → h(x)/x is shown on Figure 1. Clearly, it is a continuous function on (0, 1] satisfying h(0 + ) = +∞ and h(1) = 0. In this section we will use the obvious inequality h(x)/x -log x. Also note that this function is decreasing; we will use this fact in Section 5 (to prove Theorem 5.1). Example 3.9 (Geometric measure). Here we derive the entropy of the geometric distribution with the help of the constant RHR measure µ seen in Example 3.6. For this measure, the expectation representation (3.6) straightforwardly provides H(X n ) = h(θ) θ Pr(X n = 0). Now, the distribution of X n conditioned to {1, . . . , n} has the same list of probability masses than the geometric measure of Example 3.5 with a = 1/(1 -θ) normalised to {0, . . . , n -1} as well as the geometric distribution Geom(1 -θ) normalised to {0, . . . , n -1}. Therefore these three distributions have the same entropy, namely H(µ • | 1 : n) , and this entropy goes to the one of Geom(1 -θ) when n → ∞. Using the equality

H(X n ) = Pr(X n = 0)H µ(• | 1 : n) + h Pr(X n = 0)
we get

H(µ • | 1 : n) = h(θ) θ - h Pr(X n = 0) Pr(X n = 0) .
Formula (3.1) gives Pr(X n = 0) = 1 -(1 -θ) n , and we finally get

H(µ • | 1 : n) → h(θ)
θ , the desired entropy of Geom(1 -θ).

Example 3.10 (Geometric measure). The calculations of the previous example give the entropy H(X n ) for the geometric measure of Example 3.5:

H(X n ) = h(θ) θ - h 1 -(1 -θ) n+1 1 -(1 -θ) n+1
where θ = 1-a when a < 1, or θ = (a-1)/a when a > 1.

The following theorem just encapsulates our previous results about H(X n ). Theorem 3.11. The entropy H(X n ) satisfies the recurrence relation

H(X n+1 ) = h(ρ n+1 ) + (1 -ρ n+1 )H(X n )
and enjoys the expectation representation

H(X n ) = E h(ρ Xn ) ρ Xn
for every n 0. The expectation representation also holds for n = ∞ in the case when µ is normalisable.

Asymptotic estimation of H(X n )

In this section we consider only the case N = ∞. In the previous section, we gave a result about the asymptotics of H(X n ) when ρ n has a positive limit (Proposition 3.7).

The results we give in this section concern the case when ρ n → 0.

For non-normalisable measures µ, the following lemma provides a friendly sufficient condition in order to have

H(X n ) → ∞.
Lemma 3.12. For a measure µ with infinite total mass, that is to say, when ρ n = ∞ (Theorem 3.1), the condition

ρ n → 0 implies H(X n ) → ∞ and H(X n ) ∼ H(X n+1 ).
Proof: It is easy to see that X n w -→ ∞ when µ has infinite total mass. Therefore, since we are assuming ρ n → 0, one has The following lemma, useful in the case when ρ n → 0, is derived from an elementary application of the expectation representation (3.6). Lemma 3.13. Let (K n ) n 0 be a sequence of integers such that 0 K n n for every n 0 and lim n→∞ K n = ∞. Assume that log ρ n ∼ log ρ ′ n where (ρ ′ n ) n 0 is a decreasing (0, 1)valued sequence. Then, for any δ ∈ (0, 1), the inequality

h(ρ Xn ) ρ Xn w -→ ∞ because h(x)/x → ∞ when x → 0 + . This implies H(X n ) → ∞
H(X n ) (1 -δ) -log ρ ′
Kn Pr(X n K n ) holds for n large enough.

Proof: By the expectation representation (3.6) and the inequality h(x)/x -log x,

H(X n ) = E h(ρ Xn ) ρ Xn E [-log ρ Xn ] .
Therefore

H(X n ) E [-log ρ Xn 1 Xn Kn ] .
Let δ > 0. Because of the asymptotic equivalence log ρ n ∼ log ρ ′ n , the inequality log ρ k (1 -δ) log ρ ′ k holds when k K n for every n large enough. Therefore

H(X n ) (1 -δ)E -log ρ ′
Xn 1 Xn Kn for n large enough, and consequently

H(X n ) (1 -δ) -log ρ ′ Kn Pr(X n K n ) because it is assumed that ρ ′ k is decreasing in k.
The following proposition is an easy consequence of the previous lemma. Proposition 3.14. Assume the hypotheses of Lemma 3.13.

1) If lim inf n→∞ Pr(X n K n ) > 0, then H(X n ) = Ω(-log ρ Kn ). 2) If Pr(X n K n ) → 1, then lim inf n→∞ H(Xn) -log ρ Kn 1. 3) If Pr(X n K n ) → 1 and -log ρ Kn ∼ log n, then H(X n ) ∼ log n.
Proof: Lemma 3.13 straightforwardly implies the first assertion. If Pr(X n K n ) → 1 and ǫ ∈ (0, 1), it is easy to prove with the help of this lemma that H(Xn) log ρ ′ Kn 1-ǫ for n large enough. That shows the second assertion. Since H(X n ) log(n + 1), the third assertion follows from the second one.

Example 3.15 (Power measure). Take

µ(n) = (n + 1) a . We have seen that ρ n ∼ 1+a n in Example 3.4. When a 0, the mass µ(n) is increasing in n, therefore Pr(X n K n ) 1 2 with K n = ⌊n/2⌋. Thus we know that H(X n ) = Ω(log n) by Proposition 3.14. Since H(X n ) log(n + 1), we finally get H(X n ) = Θ(log n).
In Section 4, we will use the result of this example to show that µ is a full entropy measure. Deriving an asymptotic equivalent of H(X n ) in this example requires more work. We show below that H(X n ) ∼ log n, not by a direct application of Proposition 3.14, but by using Lemma 3.13. it can be shown that

⌊ n m ⌋ k=0 µ(k) n k=0 µ(k) ---→ n→∞ 1 m a+1 . Therefore, with K n = n m , one has Pr(X n > K n ) → 1 -1 m a+1 when n → ∞. Observe that log ρ ′ Kn = log n m -log(a + 1) ∼ -log n.
Take δ ∈ (0, 1). By Lemma 3.13,

H(X n ) (1 -δ) -log ρ ′ Kn Pr(X n K n )
for n large enough. Take ǫ ∈ (0, 1), then take m large enough in order that 1 m a+1 < ǫ, and take M large enough in order that Pr(X n > K n ) > 1 -2ǫ when n M as well as -log ρ ′ Kn (1 -ǫ) log n. Then, for n large enough,

log(n + 1) H(X n ) > (1 -δ)(1 -ǫ)(1 -2ǫ) log n.
Consequently, H(X n ) ∼ log n.

We treat another example below that will be used in Section 4 to derive some examples of measures which do not have full entropy. Example 3.17. For α > 0 consider the non-normalisable measure µ given by

µ(0 : k) = log(k + 2) exp log α (k + 1) ,
that is to say µ(0) = log 2 and µ(k) = log(k+2) exp log α (k+1) -log(k+1) exp log α (k) for k 1. It can be shown that the RHR of µ satisfies

ρ n ∼ α log α-1 (n) n .
Indeed,

ρ n = 1 - log(n + 1) log(n + 2) exp log α (n) -log α (n + 1) = 1 - log(n + 1) log(n + 2) + log(n + 1) log(n + 2) 1 -exp log α (n) -log α (n + 1)
and then the equivalence stems from the case B = 1 in the equivalence

log α (x + B) -log α (x) = log α (x) 1 + log(1 + B/x) log x α - 1
∼ x→∞ α log α-1 (x) log(1 + B/x) ∼ x→∞ Bα log α-1 (x) x , (3.7)
which holds for every B > 0 (we state this equivalence for B > 0 because we will use it for B = 2 later). Now, for α > 1, µ(0 : n) µ(0 : 2n) ∼ exp log α (n + 1) -log α (2n + 1) → 0 because log α (2n + 1) -log α (n + 1)

= log α (2n + 1) 1 -log(n + 1) log(2n + 1) α log α (2n + 1) 1 -log(n + 1) log(2n + 1) = log α-1 (2n + 1) log(2n + 1) -log(n + 1)

∼ n→∞ log 2 × log α-1 (2n + 1) ---→ n→∞ ∞.
Therefore, applying Proposition 3.14 with

K n = n 2 , one gets H(X n ) ∼ log(n) when α > 1.

SCALED ENTROPY OF A DISCRETE MEASURE

This section deals with the scaled entropies h - c ((µ n ) n 0 ) and h c ((µ n ) n 0 ) in the case when µ n = µ(• | 0 : n) for a measure µ on N as in the previous section. We use the same notations as in the previous section. We shorter denote

h - c ((µ n ) n 0 ) by h - c (µ)
and we call it the lower scaled entropy of µ, and we shorter denote h c ((µ n ) n 0 ) by h c (µ) and we call it the scaled entropy of µ. Obviously, we deal with the case when µ has an infinite support (N = ∞). More precisely, we will deal with the case when µ is unbounded, because we will see in Section 4.1 that the scaled entropies are not interesting for measures having a finite total mass (Lemma 4.1). We will also see in this section that the scaled entropy of an unbounded measure pertains to the tail of this measure. We say that the measures µ such that h - c (µ) = h c (µ) = 1 for the scaling c(n) = H(X n ) have full entropy. We will derive from Proposition 3.14 a simple sufficient condition for a measure to have full entropy (Proposition 4.4), involving the RHR.

A quantity about the tail of the measure

In this section, we point out that the scaled entropies h - c (µ) and h c (µ) pertain to the tail of the measure µ when µ is unbounded (Lemma 4.2). Before we prove this, we provide the following lemma which shows that the scaled entropies are not interesting for bounded measures. Lemma 4.1.

In the case µ(N) < ∞, 1) h c (µ) = 0 for any scaling c satisfying c(n) → ∞; 2) h - c (µ) = 1 for the scaling c(n) = H(X n ) when H(X ∞ ) < ∞. Proof: The first point is a consequence of Lemma 2.2.
To prove the second point, we use the ǫ-entropy Hǫ (X n ) defined in Lemma 2.1. We assume without loss of generality that µ(N) = 1. We introduce n 0 (ǫ) = max{n 0 | ∀k n, µ(k) < ǫ}. The integer n 0 (ǫ) is well-defined for ǫ small enough and it goes to ∞ as ǫ → 0, otherwise µ(n) would vanish for some n. In order for a set B ⊂ {0, . . . n} to satisfy Pr(X n ∈ B) ǫ, it is necessary that n > n 0 (ǫ) and B c ⊂ {n 0 (ǫ) + 1, . . . , n}. Therefore,

1 Hǫ (X n ) H(X n ) - n 0 (ǫ) i=0 Pr(X n = i) log Pr(X n = i) H(X n ) ---→ n→∞ - n 0 (ǫ) i=0 µ(i) log µ(i) H(µ) ,
the limit coming from H(X n ) → H(µ) and from the equality

- n 0 (ǫ) i=0 Pr(X n = i) log Pr(X n = i) = - n 0 (ǫ) i=0 µ(i) log µ(i) + µ 0 : n 0 (ǫ) log µ(0 : n) µ(0 : n) .
Letting ǫ → 0, one obtains, as desired,

h - c (µ) = 1 for the scaling c(n) = H(X n ).
In the case µ(N) = ∞, the following lemma says that the scaled entropies h - c (µ) and h c (µ) pertain to the tail of the measure µ. It is understood that we consider scalings starting at n = M for the restricted measure µ |(M :∞) . Lemma 4.2. Let µ be a measure with infinite total mass and let µ ′ = µ |(M :∞) be the restriction of µ to (M : ∞) for some integer M 1. Then h - c (µ) = h - c (µ ′ ) and h c (µ) = h c (µ ′ ) for any scaling c.

Proof: We denote by X n the random variables corresponding to µ as before, and we denote by X ′ n those corresponding to µ ′ . Let ǫ > 0 and take n 0 M sufficiently large in order that Pr(X n 0 M ) > 1-ǫ, and consequently Pr(X n M ) > 1 -ǫ for every n n 0 . Take such a n n 0 . Whenever f is a function whose domain is {0, . . . , n}, the inequality Pr f (

X n ) = X n > 1 -ǫ implies Pr f (X n ) = X n | X n M Pr f (X n ) = X n ∩ X n M 1 -2ǫ. That shows that H ǫ (X n ) H 2ǫ (X ′ n ).
Conversely, let f ′ be a function whose domain is {M, . . . , n} and satisfying

Pr f ′ (X ′ n ) = X ′ n > 1 -ǫ. Define f (x) = f ′ (x) if x ∈ {M, . . . , n} and f (x) = 0 otherwise. Then Pr f (X n ) = X n Pr f (X n ) = X n | X M Pr(X n M ) > (1 -ǫ)(1 -2ǫ) > 1 -3ǫ. That shows that H ǫ (X ′ n ) H 3ǫ (X n ). We finally get H ǫ (X ′ n ) H 3ǫ (X n ) H 6ǫ (X ′ n )
, and the result easily follows.

Full entropy measures

The achievement of this section is Proposition 4.4, a sufficient condition for a measure µ to have full entropy, that is to say h - c (µ) = 1 for the scaling c(n) = H(X n ). Example 4.3 (Continuation of Example 3.17). The condition of Proposition 2.7 holds for the measure µ of Example 3.17 because we have seen H(X n ) ∼ log n.

Thus µ has full entropy and h - c (µ) = 1 for the scaling c(n) = log n.

One can also deduce that the measure µ of Example 3.17 has full entropy from the following proposition. Proof: By Proposition 3.14, we know that H(X n ) = Ω(-log ρ Kn ) = Ω(log n). The result follows from Proposition 2.7.

Example 4.5 (Power measure). In Example 3.15, we have seen that the condition -log ρ Kn = Ω(log n) holds for the power measure µ(n) = (n + 1) a , a > 0. Thus, this measure has full entropy. We also saw H(X n ) ∼ log n in Example 3.16, therefore h - c (µ) = h c (µ) = 1 for the scaling c(n) = log n.

Examples of non-full entropy measures

Here we treat a parametric measure providing examples of non-full entropy measures. Our results provide, for any number r ∈ [0, 1[, an example of a sequence of random variables (X n ) n 0 for which there exists a sequence of random variables

(F n ) n 0 such that Pr(X n = F n ) → 0 but H(Fn)
H(Xn) → r. They will be obtained with the help of Proposition 2.12. Figure 2 depicts the measure µ for which we will study the scaled entropy. Let (a k ) k 1 be a sequence of positive integers and (u k ) k 1 be a sequence of positive real numbers. We denote by (A k ) k 1 and (U k ) k 1 the sequences of the partial sums of (a k ) k 1 and (u k ) k 1 respectively:

A k = k i=1 a i and U k = k i=1 u i .
Setting N k = A k + (k -1), define the measure µ on N by

µ(n) = u k if n = N k for some k 1 1 otherwise . 0 5 10 15 20 • • • u 1 N 1 u 2 N 2 u 3 N 3 a 1 a 2 a 3
Fig. 2. A nonfull entropy measure

The case we treat is the following one:

A k = exp log α (k + 2) , U k = γA k log(k + 3)
with α 2 and γ > 0. For the scaling c defined by

c(n) = H(X n ), we will show that h - c (µ) = h c (µ) = 0 when α > 2 and h - c (µ) = h c (µ) = γ γ+1 when α = 2.
Firstly, let us check that A k is strictly increasing. For α > 1, the function f : x → exp log α (x) is increasing and convex for x 3, because, clearly, its derivative

f ′ : x → αe log α (x) log α-1 (x)
x is positive for x > 1 and, clearly, its second derivative

f ′′ : x → αe log α (x) log α-2 (x) α log α (x) -log(x) + α -1
x 2 is positive for x > exp(1). In order for A k to be strictly increasing, it is enough that f (x + 1) -f (x) 1 for x 3. Since f is convex, f (x + 1) -f (x) f ′ (x), and it is true that f ′ (x) 1 for x 3 because f ′ (x) log α-1 (x). That also shows A k exp log α (k + 1) for k 2. The sequence

(A k ) obviously satisfies A k → ∞ and it satisfies A k ∼ A k+1 because exp log α (k + 1) exp log α (k + 3) A k A k+1 1,
and the left member goes to 1, because

log α (k + 3) -log α (k + 1) ∼ 2α log α-1 (k) k ,
as shown by (3.7).

Consequently, since it is clear that

A k /U k → 0, U k U k + A k+1 → 1. For n N 1 , denote by k(n) the integer k such that N k n < N k+1 . Let B n = {N 1 , . . . , N k(n) } ⊂ {0, 1, . . . , n}, and ǫ n = Pr(X n ∈ B n ). Then ǫ n → 0 because 1 -ǫ n = Pr(X n ∈ B n ) = U k(n) U k(n) + A k(n) + n -N k(n) U k(n) U k(n) + A k(n)+1 ---→ n→∞ 1.
Since ǫ n = Pr(X n = F n ) where the random variable F n is defined by

F n = X n if X n ∈ B n (i.e. X n ∈ {N 1 , . . . , N k(n) }) ∞ otherwise , we get h c (µ) 1 for the scaling c(n) = log k(n) by applying Lemma 2.3, because of the obvious inequality H(F n ) log k(n) + 1 . We set ν k = µ • | {N 1 , . . . , N k } . Then ν k(n) is the conditional law of X n given B n . Now we prove that H(ν k(n) ) ∼ log k(n)
, and then we will get h - c (µ) = 1 by applying Proposition 2.12. This asymptotic equivalence is derived mainly from Example 3.17. The probability measure ν k is the normalisation on {N 1 , . . . , N k } of the measure ν assigning mass u k to N k . The masses of ν are not exactly the same as the ones of the measure µ of Example 3.17 because of the integer part in the expression of A k and because ν(i) corresponds to µ(i + 1) up to the integer part, not to µ(i). However, this latter point is transparent when one adapts the method of Example 3.17 and it is not difficult to deal with the integer part to get H(ν k ) ∼ log k for any α 1 (and whatever the value of γ because it is not involved in ν k ). Therefore, applying Proposition 2.12, we get h

- c (µ) = h c (µ) = 1 for the scaling c(n) = log k(n).
Note that one also gets, as in Example 3.17, the equivalence u k U k ∼ α log α-1 k k about the RHR of ν, which we will use later to estimate the RHR of µ. Now, let us look at the scaled entropy for the scaling c(n) = H(X n ). We will show that H(Fn) H(Xn) → 0 when α > 2, wherefrom h - c (µ) = h c (µ) = 0 by Lemma 2.3, and we will show that log k(n) H(Xn) → γ γ+1 when α = 2, wherefrom h - c (µ) = h c (µ) = γ γ+1 by the above result. We firstly derive an estimate of the conditional entropy

H(X n | F n ). The conditional law of X n given F n = i is uniform on B c n = {0, 1, . . . , n} \ B n if i = ∞ and otherwise it is degenerate, hence ǫ n log(A k(n) ) H(X n | F n ) = ǫ n log(A k(n) + n -N k(n) ) ǫ n log(A k(n)+1 ), therefore H(X n | F n ) ∼ ǫ n log(A k(n) ). Moreover ǫ n ∼ A k(n) U k(n) + A k(n) ∼ A k(n) U k(n) = 1 γ log k(n) + 3 ∼ 1 γ log k(n) and log(A k(n) ) = log α k(n) + 2 ∼ log α k(n) .
Finally,

H(X n | F n ) ∼ 1 γ log α-1 k(n) .

Now, we use the conditional entropy formula

H(X n ) = H(X n | F n ) + H(F n )
to obtain the announced limits:

• if α > 2, H(X n ) ∼ 1 γ log α-1 k(n) because H(F n ) log k(n) + 1
, and consequently

H(Fn) H(Xn) → 0; • if α = 2, H(X n ) ∼ 1 + 1 γ log k(n) because H(F n ) ∼ H(ν k(n) ) ∼ log k(n) by virtue of Lemma 2.11, hence log k(n) H(X n ) → γ γ + 1 .
This achieves our derivation of the scaled entropy.

Finally, let us show that the RHR of µ satisfies ρ n = ∞ and ρ 2 n < ∞ for any α 2. We explained below Theorem 3.1 the reason why we pay attention to the convergence of these series.

If n = N k , ρ n = u k A k + U k ∼ u k U k ∼ α log α-1 k k .
This equivalent stems from

log α (x) -log α (x + 1) ∼ x→∞ - α log α-1 (x) x ,
shown by (3.7). Thus ρ N k = ∞ and this is enough to know ρ n = ∞. Recall that this means µ(N) = ∞ and of course we already knew that. Now,

ρ 2 N k < ∞ and it remains to show n 0,n =N k ρ 2 n < ∞.
This is shown by noting that

ρ n = 1 A k(n) + U k(n) + n -N k(n) < 1 A k(n) + U k(n) when n > N 1 and n = N k , hence n>N 1 ,n =N k ρ 2 n = k 1 N k+1 -1 n=N k +1 ρ 2 n < k 1 a k+1 (A k + U k ) 2 .
Now, using twice the inequality γA k+1 U k+1 ,

a k+1 (A k + U k ) 2 ∼ a k+1 U 2 k+1 < A k+1 U 2 k+1 1 γU k+1 1 γ 2 A k+1 , therefore the sum is convergent because k 2 = o(A k ) when α > 1.

COMPLEMENTS ABOUT THE RHR

This section is devoted to some complements about the RHR. Recall that we assume that µ has support {0, . . . , N } or N (case N = ∞), we denote by X n a random variable following the distribution µ(• | 0 : n), and in the case N = ∞ we also consider a random variable X ∞ ∼ µ(• | N) when µ is normalisable. As before, we denote by (ρ n ) n 0 the RHR of µ. Section 5.1 deals with the monotonicity of H(X n ) as well as the monotonicity of the conditional entropy H(X | X n) in n for N-valued random variables X. The first result involves the RHR and it is new. The second result is already known for absolutely continuous random variables. Section 5.2 provides a representation theorem of the sequence of probability measures µ(• | 0 : n) as a stochastic process (X n ) n 0 with margins X n ∼ µ(• | 0 : n). It will be used in Section 5.3, where we provide a theorem showing that some properties of the RHR of µ are hereditary to the image measures of µ obtained by grouping some blocks of integers.

Monotonicity of the conditional entropy

We firstly prove that H(X n ) is increasing in n whenever the RHR of µ is decreasing in n. Then, using this result, we prove that the residual entropy H(X | X n) of a Nvalued random variable X is decreasing in n whenever its (direct) hazard rate is increasing. This is the discrete analogue of a theorem given in [START_REF] Muliere | A Note on the residual entropy function[END_REF] for absolutely continuous random variables. Theorem 5.1. If ρ n is decreasing in n, then H(X n ) is increasing in n.

Proof: Using the expectation representation (3.6), this easily follows from the fact that the function x → h(x)/x is decreasing and from the fact that X n is stochastically increasing in n. When H(X n ) is increasing, note the interesting inequality

H(X n ) h(ρ n+1 ) ρ n+1 ,
This formula is easily seen by defining the random variable

Y n = ι φ (X φ(n+1)-1 ) ∼ (ι φ * µ)(• | 0 : n),
then by noting that Y n = max k ∈ {0, . . . , n} | ǫ ′ k = 1 where ǫ ′ k = max{ǫ m , m ∈ I k }, and by finally seeing that Pr(ǫ ′ k = 1) = 1 -m∈I k (1 -ρ m ). The second point in the following proposition is obtained by applying Borel-Cantelli's lemmas to the probabilistic representation seen in Section 5.2. Recall that we use the notation µ |B to denote the restriction of µ to a subset B ⊂ N. Proposition 5.4. Say that a function g : [0, 1] → [0, ∞[ is RHR-convergent, respectively RHR-divergent, for the measure µ if g(ρ k ) < ∞, respectively g(ρ k ) = ∞. In the case when g(x) = x α where α 2 is an integer, the following properties hold. 1) The RHR-convergence of g is a tail property of µ, that is to say, it holds for µ if and only if it holds for µ |(M :∞) for every integer M 0, or equivalently for one integer M 0.

2) If g is RHR-divergent for µ, then it is RHR-divergent for every image measure of µ obtained by grouping. Proof: The first point stems from Lemma 3.2 or from the bounds given in (3.4). We check the second point. Consider the probabilistic representation given by the Bernoulli process (ǫ n ) n 0 and the definition (5.1) of the random variables X n . Consider α -1 independent copies of the process (ǫ n ) n 0 . By Borel-Cantelli's second lemma and because of the RHR-divergence of g, the α independent Bernoulli processes simultaneously take the value 1 infinitely times. Now, for each of these processes, one can construct the Bernoulli process (ǫ ′ n ) n 0 corresponding to the given grouping, as seen before. These α independent Bernoulli processes also simultaneously take the value 1 infinitely times, and this implies the RHR-divergence of g for the image measure by Borel-Cantelli's lemma. Note that assertion 1) in the above proposition also holds in the case α = 1 because of Lemma 3.2. Assertion 2) holds too in the case α = 1: it simply means that the grouped measure has an infinite total mass whenever µ has an infinite total mass. Of course, the first assertion of this proposition is more generally true for every function g satisfying

∀σ ∈ ]0, 1[ N , [σ n ∼ ρ n ] =⇒ g(σ n ) ∼ g(ρ n ) .
For instance it is true for the function g = log provided that lim sup ρ n < 1. As an application of Proposition 5.4, assume given two measures µ and ν whose respective RHR ρ and σ satisfy ρ 2 n < ∞ and σ 2 n = ∞. Then the proposition shows that it is not possible to obtain ν by grouping µ, and this even is not possible after restricting µ or ν to a tail subset of N, that is to say, a set of the form (M : ∞).

Fig. 1 .

 1 Fig. 1.x → h(x)/x (solid) and x → -log x (dashed).

  by the expectation representation (3.6), and we deduce from the recursive relation (3.5) that H(X n-1 ) H(Xn) → 1.

Example 3 .

 3 16 (Power measure). For every integer m 1,

Proposition 4 . 4 .

 44 If -log ρ Kn = Ω(log n) in addition to the conditions of the first assertion of Proposition 3.14, then µ has full entropy.

Proof: Take M > 0 arbitrarily high and take an integer N 0 large enough in order that -N i=0 µ∞(i) log µ∞(i) > M . Then H(µn) -N i=0 µn(i) log µn(i) > M for n large enough.

which follows from the recurrence relation (3.5). Now, in the case of a normalisable measure µ only, we denote h X (n) = H(X | X n) where X = X N (= X ∞ if N = ∞) has the normalised version of µ as law. The function h X is defined on {0, . . . , N }. It is named the residual entropy of X in [START_REF] Muliere | A Note on the residual entropy function[END_REF]. We also set r X (n) = Pr(X=n) Pr(X n) . The function r X is well-known under the name of hazard rate of X. The following theorem is shown in [START_REF] Muliere | A Note on the residual entropy function[END_REF] in the case of a continuous random variable X having a density.

is increasing because we are assuming that r X is increasing. The results follows from the equality

for any integers M 1 and n M . Hence r X M is increasing if r X is increasing, and, as we have seen, this implies that

(Geometric measure).

Consider the geometric measure as in Example 3.5. We have seen that ρ n is decreasing in n, hence H(X n ) is increasing by Theorem 5.1. When a < 1, the measure is normalisable and it is easy to check that its hazard rate is constant (it is also well-known that the geometric distribution has a constant hazard rate). The previous theorem shows that H(X | X n) is decreasing in n. In the case a > 1, it is not difficult to check that the hazard rate of X N is increasing for every integer N 1, and then H(X N | X n) is decreasing by the previous theorem.

Probabilistic representation of the X n

Given the RHR of a measure µ, there is an interesting way to construct a sequence (X n ) n 0 of random variables X n ∼ µ(• | 0 : n). This process, up to time reversal and change of signs, appears in [START_REF] Laurent | Standardness and nonstandardness of next-jump time filtrations[END_REF] and [START_REF] Laurent | Uniform entropy scalings of filtrations[END_REF] under the name next-jump time process. We introduce this process for the proof of Proposition 5.4. Take a sequence (ǫ k ) k 0 of independent Bernoulli random variables such that ρ k = Pr(ǫ k = 1). In particular, ǫ 0 = 0, and this allows to define the random variables

for every integer n 0. Obviously, X n is increasing in n.

A trajectory of the process (X n ) n 0 is shown on Figure 3. ǫ n :

The random variable X n has the distribution given in Theorem 3.1, because

for every k ∈ {0, . . . , n}. In the case when µ is normalisable, the series ρ n is convergent (Theorem 3.1). Thus, thanks to Borel-Cantelli's second lemma, it makes sense to define the random variable X ∞ by

whose distribution is the normalised version of µ. In the case when µ is not normalisable, X n almost surely goes to ∞. Indeed, X n takes the value n infinitely many times thanks to Borel-Cantelli's lemma, because the event {X n = n} equals the event {ǫ n = 1} and then it has probability ρ n .

RHR of a grouped measure and RHR-convergent functions

The result of this section is an application of Borel-Cantelli's lemmas to the stochastic process (X n ) n 0 introduced in the previous section. Take a partition of N into non-empty intervals

, where φ : N → N is a strictly increasing function starting at φ(0) = 0. Denote by ι φ (n) the index of the interval I k containing n, and denote by ι φ * µ the image measure of µ by ι φ . We will say that the image measure ι φ * µ is obtained from µ by grouping. The RHR of ι φ * µ is given for every k 0 by

(5.2)


Y Belaïd

A Belaïd

Form Analysis by Neural Classification of Cells

Keywords: Form Cell, Neural Approach, Cell Classification, Form Analysis

Our aim in this paper is to present a methodology for linearly combining multi neural classifier for cell analysis of forms. Features used for the classification are relative to the text orientation and to its character morphology. Eight classes are extracted among numeric, alphabetic, vertical, horizontal, capitals, etc. Classifiers are multi-layered perceptrons considering firstly global features and refining the classification at each step by looking for more precise features. The recognition rate of the classifiers for 3. 500 cells issued from 19 forms is about 91 %.

Introduction

Form analysis becomes with the success of OCR/ICR techniques a very promising domain with different issues and applications. Several administrations and companies are today faced to a fast treatment of their forms in different domains such as order lecture, revenue form capture or multiple choice question paper analysis. Systems designed this last decade for form analysis are numerous and themes are varied. However, all of these systems are oriented towards a full form recognition without a real separation between the different phases. This makes difficult the reuse of systems and leads sometimes, for a new application, to the complete rewriting of the techniques. So, we have considered that for some classes of forms such as the tax forms, cells are the base of the form analysis and cell classification can constitute a generic part of a form analysis system.

Considering cell detection and extraction, the literature mentions mainly two approaches.

The most common one deals with known forms and uses a detailed model for each class of forms [START_REF] Casey | Intelligent Forms Processing System[END_REF][START_REF] Yuan | Four Directional Adjacency Graphs (FDAG) and Their Application in Locating Fields in Forms[END_REF][START_REF] Ishitani | Model Matching Based on Association Graph for Form Image Understanding[END_REF][START_REF] Arai | From Processing Based on Background Region Analysis[END_REF]. Although the systems are efficient on specific forms, they can be hardly applied to other kind of forms. In opposite, the systems, in the other approach, ignore any a priori knowledge on the form and base the analysis mainly on cell analysis [Shimotsiyi96,[START_REF] Hirayama | Analysing Form Images by Using Line-Shared-Adjacent Cell Relations[END_REF]. Although they are more general than the first ones and can be applied on a wide range of forms, their performance is limited because of their lack of knowledge.

Our aim in this paper is to propose an intermediate solution for unknown form analysis based on cell classification. Cells are first extracted from the form and classified according to different criteria based more on the content aspect than on its semantic interpretation.

The cell extraction and classification is a very important step in a form analysis process for several reasons:

• The information contained in the form is mainly located in the cells.

• The cell extraction allows to locate the information and to situate it according to the rows and columns. This leads to find at the same time the layout and the logical structure of the form (correspondence between rows and columns, number of dimensions, etc.).

• The exam of the content of each cell can help to the content classification, first by separating cells containing the information from empty ones, second, by analyzing the type of content (text, digits, etc.) in order to apply on it the adequate treatment.

• At last, the cell extraction and content classification can help to the pre-classification of forms with a modest investigation.

The outline of this paper is as follows. After a brief description of the approach used for the cell location in section 2, we present in section 3 the different classes retained for the classification and give in section 4 the classification schema. Details dealing with the main classification steps will be then exposed in this section. So, we show the different features used for the different classes and the hierarchy of neural architectures. At last, before concluding, some experiments and results will be discussed in section 5.

Cell Extraction

As mentioned in [START_REF] Belaïd | Form item extraction based on line searching[END_REF], cell location and extraction is operated in three steps.

In the first step, lines are detected in the image by applying Hough Transform. This technique was used for its robustness and reliability. It transforms the following line problem in a counting point problem [START_REF] Risse | Hough Transform for Line Recognition : Complexity of Evidence Accumulation and Cluster Detection[END_REF]. In order to avoid a multitude of line candidates, voting points are limited to only those belonging either to the contours or to the black or gray areas.

A recursive cut of the polar parameter space of lines and a fusion of close cells allow to fast locate the accumulation areas.

In the second step, segments associated to the lines, are extracted from the image. The line following is operated by advantaging the closest black pixels of the Hough lines. The lines detected can be simple, double, continuous or discontinuous, contours of black and gray areas, or vertical alignments of parentheses.

The cells are located at the third step. They are represented by a graph which arcs are the horizontal and vertical segments and which nodes are the intersection points between horizontal and vertical lines. Cells are given by the research for minimum circuits of the graph.

This first part of the system has been tested with success on French tax forms as well as on tables. The line extraction takes about 30" per image.

Cell Classes

A detailed study of French tax forms led us to define eight classes for cells described below:

• DIGI: it regroups the set of cells containing only digits. These digits generally correspond to amounts and can be preceded by the sign '+' or '-'.

• GRAY: it corresponds to gray areas which cannot be filled by any kind of data.

• HLET (for horizontal letters): all cells which text is horizontally aligned and which are constituted by alphanumeric chains containing lower-case letters and probably higher-case letters are affected to this class. They correspond essentially to form wordings.

• VLET (for vertical letters): it reassembles the same kind of cells within the class HLET but with text vertically aligned.

• HHCL (for horizontal higher-case letters): cells containing higher-case letters horizontally aligned and some digits or symbols such as parentheses are attributed to this class. These cells often correspond to wordings representing amounts.

• VHCL (for vertical higher-case letters): it corresponds to the class HHCL but considering only cells which text is vertically aligned.

• BLAC: it regroups cells in inverse video (with black foreground). These cells play a particular role in our forms.

• EMPT (for empty classes): this class regroups all the cells containing any data.

The choice of these classes depends of course on our application but can be adapted on other kind of forms. Figure 1 gives an example of a form highlighting these different classes.

Analysis Phases

The analysis schema consists of three main phases (cf. fig. 2

Cell Extraction

For line extraction, we used Hough transform on polar coordinates. Because of its slowness, the original method was improved by a filtering of voting points and a clever clustering of the accumulator cells in the Hough space (depending on line direction).

For filtering, only points belonging to contours vote. Thanks to this filtering, the system is not disturbed by the black strips and can detect accurately their contour. For thick lines, the two edges are merged. The clustering in the polar coordinates is made up by a recursive cutting up algorithm. Figure 3.a shows the Hough straight line, the voting pixel and the current segment followed.

Cell Classification

The cell classification schema can be divided into three steps as shown if fig. 5. The classification is performed progressively in order to discard rapidly the obvious cases and to refine the others. The role of the first step is to give a rapid decision on the simple cases such as GRAY, EMPT and BLAC and to separate the remaining classes into two main categories depending on the alignment: horizontal or vertical. Because of the ill quality of the image, this classification is operated globally on the cell images by using some numeric features.

The objective of the second step is to refine the classification within both categories

The classification is operated directly on the image of the CCs of the cell. Two specific neuronal nets are used at this level.

The third stage is used for some disturbing cases corresponding to cut characters such as the zero which seriously handicaps the straightforward classification of the digits. A specific classifier is used for a possible merging of cut digits.

Classification from CC Parameters

12 simple numerical parameters have been experimentally determined for the classification in the first step.

1. Number of connected components: this is related to the number of CCs after a merging step introduced because of the presence of numerous cut characters (cf. fig. 6). The merging is made within a cell, line by line. Two CCs are merged if they respect the following constraints: they belong to the same text line, they are consecutive in the line, they are superposed (cf. fig. 7a) or overlapped with an important intersection area (cf. fig. 7b) or overlapped with a small intersection and where one of the CC is very small compared to the average size of the Cell's CCs studied.

2. Text alignment: we have observed in the forms studied that the cells which are more wide than tall, contain text horizontally aligned. In opposite, when the cells are more tall then wide, the text can be aligned horizontally or vertically. An analysis of the text is then necessary in this case. Three cases are considered: the number of horizontal CCs , i.e. those which the height is greater than the width, the homogeneity of the height of the text lines, the height of the greater CCs of each line. In the second step, picks found are merged where they are close (separated with less than 3 pixels). In fact, in some cases, a line can be represented by two picks. This is the case for the line of fig. 9 because the letter 'g' of the word 'outillage' is composed of two CCs. 12. Ratio between the number of CCs deleted and the total number of CCs.

The choice of these 12 parameters results from a series of observations and tests realized on a database built up for this problem and from which we have verified the contribution of each one of these parameters in the classification process.

The classifier uses a mono-layer perceptron with 12 neurons on the entry layer (for the 12 parameters) and 5 neurons on the exit layer (for the 5 classes retained).

Classification from Cell CCs

This phase including the steps 2 and 3 of the classification process, tends to classify cells containing text into three classes: DIGI, HLET and HHCL for cells with horizontal alignment into two classes: VLET and VHCL for cells with vertical alignment. In the tax forms, there was not amounts vertically aligned. This explains the class difference in relation with the alignment.

In the second step, the entry data of the classifier is the size normalized image of a CC.

The classifier retained is a perceptron with a hidden layer. It contains 64 neurons on the entry layer (the 64 pixels of the normalized image of a CC), 12 neurons on the hidden layer and 2 or 3 neurons on the output layer according to the alignment of the studied cell. A value is associated to each output. For every output, we compute the product of the values of each CC of the considered cell. The output having the higher product is attributed to the cell.

The results obtained at the end of this step are satisfactory except for the DIGI class.

Errors come essentially from the '0' often bad segmented and cut in two parts. So, cells containing a majority of '0' are bad classified. The solution for this problem is given in the third step.

In this step, CCs presented to the classifier are normalized and grouped by pairs. This treatment is realized for cells which number of height class of CCs is 1 or 2. The classifier used is a perceptron having 128 neurons on the layer (the 128 pixels of the image normalized and merged into 2 CCs), 18 neurons on the hidden layer and 2 neurons on the output layer: one for the '0' class and one for the other characters.

These results are compared with those of the step 2 and a decision is taken for the belonging or not of the cell to the classes DIGI, HLET or HHCL.

A score is determined for one of the three classes and we retain the one which score is the highest. Let notice ScDIGI: the score of the class DIGI for the cell considered, ScHLET: the one of HLET, ScHHCL: the one of HHCL, the output value j of the classifier 2H for the CC i, SjC3cci: the output value j of the classifier 3 for the CC i merged with the CC i+1.

The computations are made as follows:

Begin

ScDIGI, ScHLET, ScHHCL = 1 i = 1 For every CC i of the current cell do If S1C3cc i < S2C3cc i then

ScDIGI = ScDIGI * S1C2Hcci ScHLET = ScHLET * S2C2Hcci ScHHCL = ScHHCL * S3C2Hcci i = i +1 Else ScDIGI = ScDIGI * S1C3cci ScHLET = ScHLET * S2C2Hcci * S2C2Hcci + 1 ScHHCL = ScHHCL * S2C2Hcci * S2C2Hcci + 1 i = i +2 Endif Endfor End

Results and Discussion

The classification process was tested on 19 French tax forms belonging to the General We can remark that the scores are very good for the classes DIGI, VLET, VHCL, GRAY, BLAC and EMPT, but are less good for the classes HLET and HHCL. There are several reasons explaining the confusions:

-The bad quality of images can produce an over-segmentation (cf. fig. 13) or a undersegmentation (cf. fig 14) .

-Some characters have the same morphology in lower-case and higher-case and cannot be differentiated after normalization. It is the case of characters as 'c', 'o', 's', 'u', 'v', 'x' and 'z'. Several solutions can be considered in order to resolve these problems:

creation of a reject class for cells for which it is difficult to make a choice between the classes HLET and HHCL, fusion of the classes HLET and HHCL: this fusion gives a general classification rate equal to 98,32 %, the consideration of the CC height before normalization.

Conclusion

This paper outlines a feasibility study for the classification of form cells into eight classes depending on the presence of information or not, on the text alignment: horizontal or vertical and the character modes higher-case or lower-case.

Fig. 1 .

 1 Fig. 1. Example of Classes.

•

  Fig. 2. Analysis Phases.

  Figure 3.b shows the line extraction by Hough. We can notice that lines made up by brackets and black strips are also found. Finally, Figure 3.c synthesizes the different extraction rates, for well delimitation, under-and over-segmentation, and for omission.

Fig. 3 .

 3 Fig. 3. Cell Extraction.

Fig. 4 .

 4 Fig. 4. Cell Extraction.

Fig. 5 :

 5 Fig. 5: Cell Classification.

Fig. 6 :Fig. 7 :

 67 Fig. 6: Connected Components Before Merging.

Fig. 8 :

 8 Fig. 8 : Example of a Line containing only one Character.

Fig. 9 :

 9 Fig. 9 : Bad Segmented Characters.

Fig. 10 :Fig. 11 :

 1011 Fig. 10 : Very Close Text Lines.

Fig. 12 :

 12 Fig. 12 : An Example of a Form Cell Classification.

Fig. 13 :

 13 Fig. 13 : A Cell with over-segmented Characters.

Fig. 14 :

 14 Fig. 14 : A Cell with under-segmented Characters.

Few systems have been

  developed in this sense. Most of the classification methods developed try to differentiate between text and non text areas. We used a perceptron for the classification. It is mono-layer for the first step which realizes a pre-classification by using numerical parameters. It contains one hidden layer for the steps 2 and 3 which analyze the text areas from normalized images of CCs. The results obtained are acceptable. Improvements and adaptations remain are possible.

Table 1 :

 1 Direction of French Revenue. The classification time for one form is about 1'45'' on a SUN Ultra Spark station, model 140 MHz. The results obtained are detailed in the table and the classification rates are presented in table 2. A classification example of a form is given in fig. 12. The color attributed to each cell indicates the class found (cf. table 3). A classification error is materialized by the presence of a little square on the bottom left. It has the color of the wanted class. Form Classification Results. .

	classes desired	classes obtained	DIGI	HLET	HHCL	VLET	VHCL	GRAY	BLAC	EMPT	Total Number Of Cells
	DIGI	638	9	6	0	0	0		0	0	653
	HLET	5	587	233	0	0	4		0	0	829
	HHCL	4	22	308	4	2	2		0	0	342
	VLET	0	0	0	23	0	0		0	0	23
	VHCL	0	0	0	0	72	0		0	0	72
	GRAY	0	0	1	0	0	23		1	0	25
	BLAC	0	0	0	0	0	0		72	0	72
	EMPT	0	0	2	0	0	7		0	1479	1488
	DIGI	HLET	HHCL	VLET	VHCL	GRAY	BLAC	EMPT	Total
	97.70 % 70.81 % 90.06 % 100.00 % 100.00 % 92.00 % 100.00 % 99.40 % 91.38 %

Table 2 :

 2 Classification Rates.

	Class	Color
	DIGI	red
	HLET	brown
	HHCL	orange
	VLET	clear green
	VHCL	dark green
	GRAY	cyan
	BLAC	yellow
	EMPT	mauve

Table 3 :

 3 Colors of the eight Cell Classes.

Acknowledgements:

The authors wish to thank N. Pican for providing us with his implementation of the perceptron algorithm.


Marçal Rusiñol

Joseph Chazalon

Jean-Marc Ogier

Combining Focus Measure Operators to Predict OCR Accuracy in Mobile-Captured Document Images

come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

Document image acquisition with mobile devices, especially smartphones, is becoming a essential entry-point in digitization workflows for companies. Despite the evident appeal of on-the-go digitization and near-instant transfer of document images, three major challenges are still to overcome to release the potential of mobile capture for document images.

Digitization distortions are, in the case of mobile-captured images of recent documents, the main cause of perturbation of the image signal. Among the most common distortions, out-offocus blur is particularly delicate. It seriously alters legibility, both for humans and OCR systems, and is linked to camera internal behavior, contrary to motion blur, perspective distortion or lightening conditions over which the user has more control. To prevent bad performance in document processing workflow, the legibility of a mobile-captured document image must be controlled as early as possible in the process.

Mobile data transmission fees impose a strict selection on the images to transfer over a network. As a consequence, such legibility control, must be performed on the mobile device, to avoid sending unusable data.

Mobility situation changes the way people capture and archive documents: the availability of some document for digitization may be temporary, and depend on the current location of the mobile user. Any control on the captured images must therefore be performed during or right after the capture, to avoid missing the opportunity for another capture.

Such an efficient control should enable the notification of a poor shot to the user after the capture, and explanations for such evaluation. In the case of a real-time evaluation, it may be possible to automatically trigger the capture when the conditions are optimal, or even to assist the user during the capture with precise direction like "move closer", or "light too low", as suggested in [START_REF] Chen | SmartDCap: semiautomatic capture of higher quality document images from a smartphone[END_REF].

In this paper, we concentrate on the evaluation of the fitness of a mobile-captured machine-printed document image for later OCR recognition, regarding the amount of out-offocus blur it contains. We are then interested in OCR accuracy prediction, which is a particular case of no-reference Document Image Quality Assessment (DIQA), as defined in [START_REF] Ye | Document image quality assessment: A brief survey[END_REF]. Here "noreference" means that only the test image is available.

Our claim is that mobile document image acquisition requires lightweight and robust methods, which can be implemented using a combination of simple focus measures developed in others communities, and not yet applied to document images. This paper is organized as follows: Section 2 reviews existing work and shows that interesting focus measures from the Shape from Focus and Autofocus communities have not been applied on document images yet. Section 3 explains the basic pre-processing we perform on document images before computing those measures. Section 4 presents those measures. Section 5 explains how we normalize and combine them. Section 6 presents our experimental protocol and the results we obtain on a public dataset. Section 7 discusses those results.

II. RELATED WORK

A good introduction to DIQA subcategories is presented in [START_REF] Ye | Document image quality assessment: A brief survey[END_REF]. This study shows that, despite some prior work on OCR accuracy prediction for scanned document images, only a few approaches deal with camera-or mobile-captured images, and even less are considering out-of-focus blur.

In the Document Analysis and Recognition (DAR) community, a major effort to better understand the effects of out-offocus blur on OCR accuracy in presented in [START_REF] Kumar | A dataset for quality assessment of camera captured document images[END_REF]. The authors introduce a dataset of mobile-captured document images with various amounts of out-of-focus blur for which they computed the accuracy of three different OCR systems. They compare the performance of three methods on this dataset: Q (presented in [START_REF] Zhu | Automatic parameter selection for denoising algorithms using a no-reference measure of image content[END_REF]) which relies on singular value decomposition of local image gradient matrix, ∆DoM (presented in [START_REF] Kumar | Sharpness estimation for document and scene images[END_REF]) which is based on the detection of edges with gradient analysis, and CORNIA (presented in [START_REF] Ye | Learning features for predicting OCR accuracy[END_REF], [START_REF] Ye | Unsupervised feature learning framework for no-reference image quality assessment[END_REF]) which is based on an automatic feature selection, sparse representation, and a regression model to construct generic predictors over images.

We believe that, while the CORNIA method is expected to perform better thanks to its strong machine-learned model, it is less suitable for mobile processing due to its memory or CPU usage, and "lightweight" methods should be considered separately in our case. A recent improvement over this method was recently proposed in [START_REF]Real-time no-reference image quality assessment based on filter learning[END_REF], with a real-time feature extraction step. However, the regression step still requires important resources, and, more generally, the authors themselves admit that this kind of approach relies heavily on the quality of the training set. Such dataset is hard to produce, and the coverage of OCR accuracy values, as well as the number of elements, may limit the performances of training methods.

In the field of OCR accuracy prediction for mobileor camera-captured document images, another method was proposed in [START_REF] Peng | Automated image quality assessment for camera-captured OCR[END_REF]. The authors define features based on edge gradient and height-width ratio for words and characters. They use a Support Vector Regression to calculate the word error rate for a given document. While the evaluation method described, focusing on decision making, is highly relevant, the learning step and some dependence to character shapes limits, in our opinion, such method.

An interesting study of available focus measures, for an entirely different purpose, is presented in [START_REF] Pertuz | Analysis of focus measure operators for shape-from-focus[END_REF]. In this work, the authors present more than 30 "focus operators" and their application to recover depth information for each pixel in natural images. The authors not only perform a great comparison of run-time properties, weaknesses and strengths of each method: they also propose to group them in 6 main categories which exhibit consistent behavior under the same perturbations like image contrast, image noise, or image saturation.

We therefore propose to investigate the application of those mature focus measures on document images to estimate outof-focus blur, and its correlation with OCR accuracy. We are particularly interested in evaluating how those measures can be combined: as they are intended to be computationally efficient and were sometimes even used for autofocus systems, it really makes sense to try to form a global method which would be more robust to real capture conditions, and overcome individual weaknesses. To enable the experimental evaluation of our contribution, we used the public dataset presented in [START_REF] Kumar | A dataset for quality assessment of camera captured document images[END_REF].

III. SIMPLE PAGE SEGMENTATION

Since we are dealing with mobile-acquired images, the incoming images do not correspond just to the digitized document page, but usually contain some background that is irrelevant for us. Page segmentation not being the main topic of our research, we just implemented a simple yet effective page detection that performs well enough on the tested images. Color images are first transformed to grayscale by computing the luminance of the image. By applying a median filter with a large enough structuring element we are able to get rid of the text from the page while keeping the white background of the page (c.f. Fig. 1b)). In our experimental setup, the structuring element was a 31 × 31 rectangle. By thresholding this image with Otsu's method and getting the largest connected component we obtain the page's boundingbox that is used for segmenting the page (c.f. Fig. 1c)).

Of course, such simple techniques will fail for severely distorted images presenting highlights and shadows, strong perspective changes, or if the page is not highly contrasted from the background, but provided accurate enough results in our test scenario.

IV. FOCUS MEASURES

In [START_REF] Pertuz | Analysis of focus measure operators for shape-from-focus[END_REF], the authors distinguished 6 families of focus operators. Gradient-based (GRA) and Laplacian-based (LAP) operators estimate the sharpness and the amount of edges in an image using gradient or first derivative, and, respectively, second derivative or Laplacian. Wavelet-based (WAV) and DCT-based operators are based on discrete wavelet transform and discrete cosine transform (DCT) coefficients. Statisticbased (STA) operators are based on local descriptors (texture analysis, in particular). Finally, the miscellaneous (MIS) operators are the ones which do not fit in the previous categories, due to some dependence on global indicators like histograms or image contrast.

Grounding our work on the focus measure operators proposed in [START_REF] Pertuz | Analysis of focus measure operators for shape-from-focus[END_REF], we selected 24 techniques which appeared as most promising. Whereas the techniques used for shape from focus in [START_REF] Pertuz | Analysis of focus measure operators for shape-from-focus[END_REF] need to produce pixel-level measures, we just need a global estimation of the focus for the whole image. We also discarded the DCT-based operators, due to their specificity to some image and video formats, or their processing time. Finally, some preliminary experiments led us to filter out the operators with bad performances on document images.

The Table I lists the focus measures we considered in our experiment, along with the abbreviations from [START_REF] Pertuz | Analysis of focus measure operators for shape-from-focus[END_REF] where their exact formulation can be found.

V. FEATURE FUSION

Even though the measures listed above are state of the art auto-focus techniques, some of them might not correlate well with the output of an OCR engine. However, since it is difficult to a-priori judge which ones will perform better than the rest and which is the best amount of features to will denote the j-th subset having m elements. Such combinations resulted in testing more than 16 million different configurations. Once we have a subset of focus measures to combine, we have to face two different aspects. On the one hand how to normalize the measures so they fall within a similar range and on the other hand, how to combine them into a single number.

A. Measure Normalization

Since each of the different focus measures fall within different numeric ranges, before combining them we must normalize their ranges [START_REF] Kittler | On combining classifiers[END_REF]. In our experiments we have tested four off-the-shelf normalization techniques. Given a set of focus measures T j m with their normalized measures T j m ′ are obtained by the following normalizations.

• Min-max: applies a scaling factor and transforms the measures in a common range [0, 1]. Being min(T j m ) and max(T j m ) the minimum and maximum of the scores respectively,

T j m ′ = T j m -min(T j m ) max(T j m ) -min(T j m )
.

Such method is highly sensitive to outliers in the data used for estimation.

• Z-score: is one of the most common normalization techniques. It is computed using the arithmetic mean µ and standard deviation σ of the given data.

T j m ′ = T j m -µ σ .
By using the arithmetic mean and standard deviation, the method is also sensitive to outliers.

• Tanh: is a more robust and efficient normalization technique that also takes into account the mean and standard deviation.

T j m ′ = 1 2 tanh 0.01 • T j m -µ σ + 1 .
• MAD: the median and median absolute deviation are insensitive to outliers and the points in the extreme tails of the distribution.

T j m ′ = T j m -median(T j m ) M AD ,
where M AD = median(|T j mmedian(T j m )|).

B. Fusion Strategies

After normalizing the response of the focus measures, a subset of focus operators T j m ′ can be easily combined in order to obtain a single indicator by just computing the maximum, minimum, sum, product, average or median values of this subset. Formally, we will denote those fusion strategies as

combM AX = max T j m ′ , combM IN = min T j m ′ , combSU M = ( n m ) j=1 T j m ′ , combP ROD = ( n m ) j=1 T j m ′ , combAV G = mean T j m ′ , combM ED = median T j m ′ .
We will report in the experimental section the results obtained by each normalization technique and each fusion strategy.

VI. EXPERIMENTAL RESULTS

In order to evaluate our proposal, we have used the publicly available DIQA dataset [START_REF] Kumar | A dataset for quality assessment of camera captured document images[END_REF]. This dataset is composed of 25 documents. Each document has been acquired several times by a cellphone camera at different focal lengths: some acquisitions are perfectly focused whereas some others present severe blurring effects. The final dataset is composed of 175 images and each of those have been OCRed by three different engines (ABBYY FineReader, Omnipage and Tesseract). The comparison between the OCR output and a manual transcription of the document permit to obtain the OCR accuracy for each image. Median Pearson (LCC) and Spearman (SROCC) correlation factors are provided in order to assess whether the proposed metrics are in agreement with the obtained OCR accuracies, This proposal is ill-conceived and potentially destructive to my industry, This proposal is El-conceived and potentially destructive to my industry, This proposal is itt-coocerved and potentially destructive to ray industry. This proposal it i conceived and fcWtiBy <teact>vt to ntaby. and thus be useful to predict the OCR behavior. We can see an example of this dataset in Fig. 2.

We can see in Table II the results that we obtained for each normalization and fusion strategies in terms of the median Pearson correlation coefficient (LCC). Results in Table II just report the best feature combination for each normalization and fusion. In most of the cases, the best performance was reached by just combining between two and four of the 24 possible focus measures. We can appreciate that despite the selected normalization, the fusion strategy that performs best is usually the combMIN. Thus, for a given set of focus measures, just taking the most pessimistic one that considers the document more out of focus, is the strategy correlates the best with the OCR accuracies.

In general, the focus measures that worked the best were the ones from the gradient family. In particular, our best configuration used a subset of the four focus measures T j 4 = {GRA1, GRA2, GRA4, ST A8}. The time taken to compute the four measures and its normalization and combination in a desktop PC under an unoptimized Matlab code was 0.61 secs. in average.

In Table III we compare our results with the state-ofthe-art methods presented by Kumar et al. in [START_REF] Kumar | A dataset for quality assessment of camera captured document images[END_REF]. We can appreciate that the proposed method outperforms both Q [START_REF] Zhu | Automatic parameter selection for denoising algorithms using a no-reference measure of image content[END_REF] and ∆DOM [START_REF] Kumar | Sharpness estimation for document and scene images[END_REF] methods in terms of median LCC and median SROCC. However, the CORNIA [START_REF] Ye | Unsupervised feature learning framework for no-reference image quality assessment[END_REF] method that uses machine learning techniques in order to learn how to predict the OCR accuracy still performs better than the metric-based approaches.

We report in Table IV the obtained median LCCs for the three different OCR engines in the DIQA dataset. The fact that no substantial changes can be appreciated between ABBYY and Tesseract despite their huge difference in accuracy (c.f. Figs 4 and 6 in [START_REF] Kumar | A dataset for quality assessment of camera captured document images[END_REF]), might indicate that the evaluation protocol proposed in [START_REF] Kumar | A dataset for quality assessment of camera captured document images[END_REF] is biased to produce overoptimistic results. Finally, we show in Fig. 3 some failure cases. In the image of Fig. 3a), we obtain a rather low focus measure whereas the OCR accuracy is beyond 90%. Such low focus measure is probably provoked by the large white space in this page. Contrarily, in Fig. 3b) the focus measure is rather high but the OCR accuracy is low (25%). In this case, most of the text of the document image is out of focus, but the huge headline provokes that the focus measure is optimistically high.

VII. DISCUSSION AND CONCLUSIONS

In this paper we have presented a metric-based method for quality assessment of mobile-acquired document images able to predict at some extent the accuracy that an OCR engine will yield. Starting with the hypothesis that by combining several focus measures from different families we should reach better performances than just relying on a single metric, we finally found out that gradient-based features are the ones that correlate the best with the response of OCR engines. Although the proposed method outperforms other metrics proposed in the In this paper we have dealt with simple combination of the focus measures, however, maybe better performances could be further reached with more complex combination strategies such as a linear combination of the focus measures with learned weights.

VIII. APPENDIX: SELECTED FOCUS MEASURES

This appendix summarizes the focus measure operators in which we obtain the best performances. We refer the interested reader to [START_REF] Pertuz | Analysis of focus measure operators for shape-from-focus[END_REF] for the details of the rest of the measures.

A. Gaussian Derivative (GRA1)

The Gaussian derivative focus measure is computed by φ = (x,y)

(I × Γ x ) 2 + (I × Γ y ) 2 , (1)
with Γ x and Γ y are the partial derivatives of the gaussian function Γ(x, y, σ) = 1 2πσ 2 exp -

x 2 + y 2 2σ 2 . (2)

B. Gradient Energy (GRA2)

The gradient energy is computed as the sum of squares of the first derivative in the x and y directions φ x,y = (i,j)∈Ω(x,y) (I x (i, j) 2 + I y (i, j) 2 ),

in which Ω(x, y) defines a local neighborhood of the pixel (x, y). The global measure φ for the whole image is obtained by averaging all the φ x,y

C. Squared Gradient (GRA4)

The squared gradient method computes the first derivative of the image in the horizontal dimension, squared in order to increase the influence of larger gradients. φ x,y = (i,j)∈Ω(x,y)

I x (i, j) 2 , |I x (i, j)| ≥ T. (4)

D. Histogram range (STA8)

The histogram range is computed as φ = max(k|H > 0)min(k|H > 0),

begin H the histogram of the image under analysis.

Fig. 1 .

 1 Fig. 1. Simple page segmentation. a) Mobile-acquired document, b) median filtering, c) final page segmentation.

Fig. 2 .

 2 Fig. 2. Example of a portion of a document from the DIQA dataset with different blurring levels and their OCR outputs.

Fig. 3 .

 3 Fig. 3. Failure cases

TABLE I .

 I USED FOCUS MEASURES AND THEIR ABBREVIATIONS FROM[START_REF] Pertuz | Analysis of focus measure operators for shape-from-focus[END_REF]. {F M 1 , F M 2 , . . . , F M n } the set of all n = 24 focus measures F M applied to an incoming image under test, we tested all the possible combinations T of this set. We denote T m , with m ∈ [1, n] all the possible subsets of measures formed by taking m elements from S. Particularly, T j

	Focus operator	Abbr.	Focus operator	Abbr.
	Gaussian derivative	GRA1	Ratio of wavelet coefficients	WAV3
	Gradient energy	GRA2	Gray-level variance	STA3
	Thresholded absolute gradient	GRA3	Gray-level local variance	STA4
	Squared gradient	GRA4	Normalized gray-level variance	STA5
	Tenengrad	GRA6	Histogram entropy	STA7
	Tenengrad variance	GRA7	Histogram range	STA8
	Energy of Laplacian	LAP1	Brenner's measure	MIS2
	Modified Laplacian	LAP2	Image curvature	MIS4
	Diagonal Laplacian	LAP3	Helmli and Scherer's mean	MIS5
	Variance of Laplacian	LAP4	Steerable filters-based	MIS7
	Sum of wavelet coefficients	WAV1	Spatial frequency measure	MIS8
	Variance of wavelet coefficients	WAV2	Vollath's autocorrelation	MIS9
	combine, we have tested all the possible feature combinations.
	Being S =

m , with j ∈ 1, n m

TABLE II .

 II MEDIAN LCC FOR DIFFERENT NORMALIZATIONS AND FUSION STRATEGIES.

	Fusion method	Normalization
		Min-max	Z-score	Tanh	MAD
	CombMAX	0.87439	0.86364	0.86363	0.86679
	CombMIN	0.89791	0.9378	0.93779	0.93092
	CombSUM	0.92056	0.92164	0.92165	0.91945
	CombPROD	0.87073	0.91372	0.92175	0.86989
	CombAVG	0.92056	0.92164	0.92165	0.91945
	CombMED	0.92056	0.92164	0.92165	0.91945

TABLE III .

 III COMPARISON WITH STATE OF THE ART[START_REF] Kumar | A dataset for quality assessment of camera captured document images[END_REF].

	Method	Learning	Med. LCC	Med. SROCC
	Q	Metric-based	0.8271	0.9370
	∆DOM	Metric-based	0.8488	0.9524
	CORNIA	Learning-based	0.9747	0.9286
	Proposed	Metric-based	0.9378	0.96429

TABLE IV .

 IV MEDIAN LCC WITH DIFFERENT OCR ENGINES.LCCs are computed independently document-wise, i.e. just considering the 6 to 8 documents for a given document class. Performance is evaluated then by reporting the median of those 25 LCCs. By reporting the median LCC value, outlier classes in which the methods might not perform well are disregarded. If we compute directly the LCC for all the 175 images we obtain a 0.6467 which compares quite inferiorly to the reached 0.9378.

	Method	ABBYY	Omnipage	Tesseract
	CombMIN+Z-score	0.9378	0.8794	0.9197

ACKNOWLEDGMENT

This work has been partially funded by the Valconum consortium (http://valconum.fr) and the EU-COFUND project TECNIOSPRING AVAL-DOC TECSPR13-1-0017.